Israel Journal of Mathematics, Volume 2, Issue 2 (1964)

DOUBLE NORMALS OF CONVEX BODIES(1) BY

NICOLAAS H. KUIPER

ABSTRACT

In this paper we study the set of double normals of a solid convex body in E n (e.g. n-simplex). There are at least n double normals. The lengths form a set of measure zero in R for n < 3, not necessarily so for n > 3.

1. The problem. A bounded point in euclidean n-dimensional Its boundary is denoted by dB. p,q e dB. It is called a double vectors in E , (x-p)(q-p)~O

compact convex set B with at least one interior vector space E = E n will be called a convex body. A chord is a line segment [p, q] with end points normal in case, in terms of inner products of

and (x - q) (p - q) __>O for a l l x e B .

1. What can be said about the set of double normals of a convex body? In particular: 2. Must a convex body in E n admit at least n double normals?(2) 2. Examples. The polar coordinate values of a vector v ~ E are by definition r = ~/~- and co = v/r. The unit vector co is a point of the unit sphere S "-1 c E. The antipodal equivalence class z = n(co) = ( c o , - co} of the unit vector co is a point of the real projective ( n - 1 ) - s p a c e p , - 1 , of which the unit sphere S "-1 is covering space under the double covering n : S " - 1 . _ ) p , - t . I f co is a unit vector in the direction of a double normal [p,q] of B, then so is The set of such unit

co=(q-P)/[q-Pl

-co=(P-q)/[P-ql.

Received August 18, 1964. (1) a. Research partially supported by the N.S.F.b. Lecture in the conference on differential geometry, June 1964, at Oberwohlfach, Germany. (2) This last question was problem 1 in "Unsolved problems in intuitive geometry" by V. Klee (Mimeographed notes, University af Washington (1960)). Some mathematicians, e.g. T. Ganea, have been aware that the solution of this problem is essentially contained in work of L. Lyusternik, L. Schnirelmann [5] and M. Morse. V. Klee and B. Griinbaum suggested that publication, in particular for the case that B is not known to be C2, is desirable anyhow.

For thetreatment of an analogous Coo-problemin a space with a Riemannian metric see Bos [3] 71

72

N.H. KUIPER

[June

vectors is therefore invariant under the antipodal map and it defines the unique set of double normal directions K ( B ) c F -1 which it covers. THEOREM 1. I f f : P n - t - ~ R is any real C2.function ( = with continuous second derivatives), then there exists a symmetric convex body B in E" with centre O, for which the set of double normal directions is

K(B) = K ( f ) c P " - t , where K ( f ) is the critical set

r ( f ) = {z I z ~ e " - t, (df)z = 0). Proof. For t > O, t sufficiently small, the point set defined in terms of polar coordinates (r, co) by r = 1 + tf@@)) is a hypersurface OB,, boundary of a body B t in E . For t converging to zero this hypersurface converges to the unit sphere S"-t, and the continuous first and second derivatives are included in this convergence. By compactness of P " - t it follows that a > 0 exists such that the hypersurface aB, has at each point all normal curvatures positive, as has s " - t , and is therefore strictly convex. Because B, is symmetric with respect to 0 and strictly convex, every chord that connects two tangent points on parallel tangent hyperplanes, passes through 0. All double normal directions are then found from the equation (1)

dr = d[1 + ,f(Tr(¢o))] = 0,

or

d f = O.

Consequently K ( B , ) = K ( f ) and the theorem is proved. THE CONDITION C2-. A function f : R"--, R will be called C 2- in case it is C a (continuous first derivatives) and for any Xo in the domain there exist 6 and N such that (2)

If ( x + h) - f ( x ) - (dfL(h)[ < N.

I hl 2

for all x with [x - xo I < 6 and h < 6. (df)x is the derivative of f at x. It sends the vector h into (df)~(h). If a function f on a C°-m-manifold (like P=) has for any C°°-chart I<: U--, R m a composition f x -1 which is C 2-, then f is called C 2-"

With these definitions we may replace in Theorem 1 C2-function f by C 2-function f, with the same conclusions. A special example is obtained as follows. If xt, ...,x, are orthonormal coorn -Xi, 2 then the restriction of g to S "-1 has 2n dinates for E" and g = ~7=xJ critical points and it is invariant under the antipodal map. The well defined function f = f r o - : : P~- 1 __, R, which is the composition of the relations 7c- 1 and f, has exactly n critical points, Yx,'",Yn.

1964]

DOUBLE NORMALS OF CONVEX BODIES

73

For any n given distinct points z 1, ..., z. on P " - t there exists a C~°-diffeomorphism x carrying these points onto the n points Yl, "",Y. respectively. But then f z : P " - I - ~ R is a function with z~, ..., z, as critical points. With Theorem 1 we obtain for the corresponding convex bodies: COROLLARY. Given n arbitrary distinct straight lines through 0 ~ E" (n >_ 2), for example for n = 3 all in one 2-plane, there exists a convex body B with exactly n double normals, and such that these are on the n given lines. REMARK. If all double normal directions are close to each other, then the boundary of the body lies between two concentric spheres with radii-ratio close to one. EXERCISE. Consider also the geometry of the case defined by g = .'~ra Lj=~Xj2 with m < n. 3. A converse to theorem 1. TrmOREM 2. Given a convex body B in E", there exists a centrally symmetric convex body B' with C2--boundary ~B', and there exists a C2--function f: W - I _, R such that

K(B) = K(B') = K Or). Proof.

For any sets B and C in a vectorspace, let -B = {x]-x~B}

and B + C = {x +

ylx B,y c}.

Consider a convex body B in E". Take any hyperplane in E" and call all parallel hyperplanes "horizontal". Define the symmetric convex body B" by B" = B + ( - B ) The tangent hyperplanes at u s OB" and - u are parallel. If and only if these hyperplanes are horizontal, then there exist p and q in OB with u = 2 ( p - q ) , at which the tangent planes are horizontal. The corresponding chords in B and B" are double normal if and only if p - q is vertical. Consequently a vector has the direction of a double normal of B if and only if it has the direction o f a double normal of B", and K ( B ) = K(B"). Observe that the length of a double normal of B" is twice the length of a corresponding double normal of B. Let B' be the set of all points of E that have a distance smaller or equal to one to the convex body B". B' is a symmetric convex body, whose boundary OB' is "parallel" to OB". Clearly K(B') = K(B"). The length of a double normal of B' is 2 more than the length of the corresponding double normal of B% Now if z E OB', than there exists y ~ OB" such that z - y has length 1. OB' has no point in common with the open ball with radius 1 and centre y . B' also contains no point at the other side from T(z), the hyperplane through z orthogonal to z - y . Then we conclude that T(z) is the uniquely defined tangent hyper-

74

N.H. KUIPER

[June

plane of ,~B' at z. The surface ~B' is differentiable at every point, and it is the boundary of a convex body. Then it follows (see Bonnesen-Fenchel, Theorie der konvexen Ktirper, p. 26)that ~B' is a Cl-hypersurface. Equivalently the unit normal vector at z s 8B' is a continuous function of z. If ~B' is given in polarcoordinates by r = r(c0)= r(-co) then the function f:pn-l_~ R required in theorem 2 is defined by r(co) =f(n(co)). f is clearly a Cl-function. Moreover

K ( f ) = K(B') = K(B") = K(B) For each point z e 8B' it follows from the fact that some neighborhood of z in OB' is pinched between a hyperplane and a sphere both tangent to aB' at z, that the condition for C2- (see (2)) is fulfilled for f . This proves theorem 2. In the next section we study K ( f ) and obtain conclusions which, applied to K(B), give among others the affirmative answer to the problem in the introduction.

4. Critical points of a continuous (or C 1) function on a closed topological (or C~) manifold. Let M be a closed (compact and without boundary) n-manifold and f : M - ~ R a C o (continuous) or Cl-function. A point z ~ M is called noncritical if there exists a C o or C 1 (resp.) coordinate system ~: U(z) ~ R n covering some neighborhood U(z) of z, such that the last coordinate is the restriction of f to U(z). A point is called critical if it is not noncritical. Let K(J) be the set of all critical points of f. K ( f ) is a closed set in M , because its complement is open. In the Cl-case the critical points z are those for which (d J)= = 0. DEFI~TION. The relative Lyusternik-Schnirelmann (L.S.-)category) ~(A, M) of a closed subset A in M, is the minimal number of open contractible (in M) sets of M that can cover A. The absolute L.S.-category of M is ~,(M) = T(M,M). THEOREM 3. Let F be a component of the set of critical points in a level set of the C o- or Cl-function f on the compact closed manifold M.~F is a component of K ( f ) N { z l f ( z ) = c } for some c. Then E r r ( F , M ) > 7(M),

where the summation extends over all components of each critical set in each level set. As ~(M) is finite, the conclusion is valid in case the summation extends over an infinite number of non-zero terms. Hence we may exclude this and assume that there are only a finite number of critical levels, and that each level set has a finite number of components. LEMMA. Let c be the only critical value o f f in the half open interval (b,e] ¢-R. Suppose fb = {zlf(z) <=b) is covered by p contractible (in M) open sets V~, ..., Vp with union V, and suppose the critical set at level c is covered

1964]

DOUBLE NORMALS OF CONVEX BODIES

75

by q contractible in (M) open sets Vp+D...,Vp+q with union V ' . (z If(z) =< e} can be covered by p + q contractible open sets.

Then

f~ =

Proof of the theorem from the lemma. Applying the lemma inductively, while

starting from a value smaller than the minimal value of f as first example of b, we can go up to any value smaller than the maximum m of f . But the maximal value critical set is covered by a given minimal number of open contractible sets, which cover M - f m - 2 ~ for some e > 0 . After going up to the value m - e we can just add these open sets to cover M completely. This implies Theorem 3. Proof of the lemma. (Compare Kuiper [4]). If b is a critical value, and the compact set fb is covered by some open sets, then these sets also cover fb ~ for some e > 0. Hence we can replace b by b + e and we then can assume that b is not a critical value. This we will do now. For every non-critical point z ~ M and neighbourhood V~ there exists a homeomorphism h~ of M and a neighborhood U~ of z, with U~ c / . ~ c V~, such that f(h~(u)) > f ( u )

for u E M

h~(u) = u

for u ~ V~

f(h~(u)) > f ( u )

for u ~ U~

With the local coordinate system in which the last coordinate is f , this can be seen from the following model for such a homeomorphism in coordinate space R" with coordinates x l , ' " , x , , at the point 0 and f = x,. Let : R ~ R be a C°°-function for which =

1

1

O=<¢(s)__
for s e R .

¢(s) = 0

for I s ] > 2 .

Consider the Coo-map ho given by ho(xl,...,x,) =

xl,...,xn_l,x~+t

x

.

For ). large the support of this map is in a small ball about 0 as centre. For t small enough h is a diffeomorphism, and it lifts any point at most to a xn-level which is t higher. Any compact set W = M - K ( f ) can be covered by a finite number of neighbourhoods U~, each obtained as above with some non-critical point z, neighbourhood V, and homeomorphism h,. Let h be the product of these homeomorphisms in some arbitrary order. By a suitable choice (small) of the para-

76

N . H . KUIPER

[June

meter t in each homeomorphism h:, it can be attained that 0 0 and every u e M . Finally let: 2e = inf,~ w [f(h(u)) - f ( u ) ] > 0.

(3)

We consider two examples for W to be called W and W~ (See figure). W is the set W = f , - - i n t f b - - V ' , with the corresponding homeomorphism h, and = 8 (h). The choice is made such that 8 < 6 < ½(c- b), so that

h(fb) c fc_,

(4)

The other example depends on s and is as follows: W1 = (;re - int f~+,) +

,..

"///

Y/Ill,

C +~

(f~_, -

int fb).

V/// Y/J

C C-5

b Wl

W

The corresponding homeomorphism is hi, and 2el = 2e(hl) = inf,~w (f(hl(u))- f ( u ) ) . For every z e M we have

f(h(z)) > f(z) and f(hl(z)) >=f(z) If z e f t - , , then h~ 1(z) e f t _ , . Suppose moreover h~ 1 z ~fb, then

f(h~lz) < f(z) - 2el. Consequently one finds that h~TM (f~_,) Cfb

~ integer and 2~ el > c - b

Or, as V ~ f b , (5)

h~(V) D h~ (fb) D f c - ,

for 2~tel > c -- b

Analogously

(6)

h~(f~+~)Dfe

for 213ei > e - c

If hz e f t + , - f ~ _ , then z e f t + , - - f b by (4). If moreover hz¢ hV', that is z ~ V', then f ( h z ) - f ( z ) ~ 2e hence zefc-,. Consequently for any point hzef¢+,:

DOUBLE NORMALS OF CONVEX BODIES

19641

either

hzef~_,,

then zef~_,;

or

hz e h V ' ,

then z~ V';

or

hzefc+~ -f~_~ and h z ~ h V ' - then zef~_~.

77

This implies

(7)

h(fc-, U V') Df¢+,

From (5), (6) and (7) follows:

fe c hPt(fc+,)c h~h(f¢_~ U V ' ) c h~h(h~V UV') and fe is covered by the p + q contractible open sets

and

h~hh~(V~)

for i = 1, ...,p

h~hh(Vj')

for j = 1,-.-, q

q.e.d.

If M is the real projective n - 1-space/~- 1, then it is known that y(M) = y(P"- 1) = n and so for a function f : P " - l ~ R we have: COROLLARY

y ( F , P " - ' ) >_-n. F

In particular if y(F,P ~-~) = 1 for each F, for example if each F is one point, then the total number of these components is greater or equal to n. 5. Application to the double normals problem. Combining the results of section 4 with those of section 3 we get: THEOREM 4. A convex body B in E" has at least n double normals. I f K ( B ) c p , - i consists of a finite number of components F each belonging to a set of double normals of constant length, then (8)

]~ ?(F, pn-,) >= n F

For example if B is an ellipsoid in E 3 with two equal axes, then K(B) ~ p2 consists of a point and a projective line and the left hand side in (8) is 1 + 2 which is >_3. PROBLEM. Let O be the family of all convex symmetric bodies B in euclidean 3-space E 3, that have all double normals in a plane. Is there an upper bound to the ratio between the largest and smallest width of B for B in O? How much is it? The ratio is max g(to) min g(to) in case r < g(to) defines B in polar coordinates r and to.

78

N.H. KUIPER

[June

6. On the length of the double normals of a convex body. THEOREM 5. For n > 4 there exists a convex body in E of non-constant width, such that every width (a real value) is attained as the length of some double normal. The body can be chosen such that there is an arc in p~-i consisting of directions of double normals connecting a minimal width double normal direction to a maximal width double normal direction. Proof. Whitney [7] has given examples of C n- 2-functions f on the n - 1-cube i n- 1 < Rn- t with values in I = {t [ 0 < t < 1}, such that d f is zero at each point of an (non rectifiable) arc connecting two points with different f-values. This function can be carried over to P~-1 by imbedding I ~- i in P~-1 and extending the function suitably (Whitney [8])(3). The construction of section 2 then gives the convex body required in the theorem.

PROBLEM. In Theorem 4 it remains open whether the set of all double normal directions (not decomposed in constant length parts) obeys an analogous relation If F represents a component of this set, is then again ~ r y ( F , P "-1) > n? A special problem in the same direction is: Is there on the two-sphere a C1-function f such that the set {x I (df ) x = 0} is an arc? F o r n = 3 we get a conclusion different from that in Theorem 5: TrIEOREM 6. The lengths of the double normals of a convex body B in E 3 form a set of measure zero in R. Proof. This mainly consists in an application of the theorem of A. P. Morse and Sard. As in section 3 we replace B by B" and then by B', and we denote the latter again by B . Let this symmetric body B be defined by the inequality in polar coordinates r < f(og). Some neighbourhood of any boundary point z e ~B in ~B is pinched (3) By a suitable modification of the example of Whitney [7l (see also Besicovith-Schoenberg [I]) one can obtain for 0 > 0 a real C1 function f on 12 = {(xl,x2)~ I1210 < xl < 1, 0 ~ x 2 < 1} such that the set of critical values

f(K) = f({x

l(df)=

o})

is the interval I = {t I 0 < t < 1} but for which f is a function rather close to being C 2 in the following sense. There is a closed set J (in the examples it is an arc) and for x ~ J, y ~ 12 one has, writing r = ~/(y--x) 2 , A f = f ( y ) - f ( x ) , that Af is bounded (6 > 0) r2(lnr) 2+~ and f is C ~ outside J. PROBLEM. Does there exist an example 0 = 0?

1964]

DOUBLE NORMALS OF CONVEX BODIES

79

between a unit ball and the tangent plane, mutually tangent at z, as we observed in section 3. Let n(to) be the unit outside normal vector at the point (r, t o ) = ()(co), to) of ~3B. From the assumptions about B it follows geometrically that In(to1) -- n(to2)[

Itol-to21 is bounded. The function n : S 2 ~ $2 which assigns to to the value n(co) is then totally differentiable almost everywhere by a theorem of Rademacher (see Saks [-9]). By a theorem of Federer (see Whitney [-8]) for any e > 0 there exists then a " b i g " closed set Q c S 2 such that S 2 - Q has measure < e, and such that n(to) is a Cl-function on Q. Geometrically one finds: dl-f(co).to] = f ( t o ) . ( n d t o ) t o + o r t h o g o n a l

component. The left hand side is:

f dco + (df)to The inner product with to yields, with to2 = 1 and dto 2 = 2todto = 0 , d f =f(co)(ndto)

The coefficient f(to), n(co) of dto is C 1 for to ~ Q. Hence f is C z for to e Q c S 2, and it can be extended to a C2-function g: S 2 ~ S 2 with g(to) = f ( t o ) for to ~ Q. By the theorem of A. P. Morse-Sard [6, 10] the critical values of g form a set of measure zero. The critical points of f in Q therefore give a contribution zero to the measure of the set of critical values o f f . On the other hand the critical points o f f outside Q have (Hausdorff-)measure < 5. Hence they can be covered by circular small discs with critical points as centres and with the sum of the areas smaller than 2e. Any such disc of small radius 6 in dB is again pinched between a tangent plane and a ball with radius one (section 3), and it contributes at most 2 ( 1 - c o s 6 ) < 262 to the set of values of widths of the body. The sum of these contributions is then smaller than 2/re times the sum of the areas of the discs m, hence < e. This being true for any 5, the theorem follows. REFERENCES 1. A. S. Besicovitch and I. J. Schoenberg, On J6rdan arcs and Lipschitz classes of functions defined on them, Acta Math. 106 (1961), 114-136. 2. T. Bonnesen and W. Fenchel, Theorie der konvexen K6rper, Berlin 1933. 3. W. Bos, Kritische Schnen auf Riemannschen EIementarraumstiicken, Math. Ann. lSl (1963), 434--451. 4. N. H. Kuiper, A continuous function with two criticalpoints, Bull. Amer. Math. Soc. 67 (1961), 281-285.

80

N . H . KUIPER

5. L. Lyusternik and L. Schnirelmann, Mdthodes topologiques darts les probldmes variationels, Paris, 1934. 6. A. P. Morse, The behaviour of a function on its criticalset, Ann. Math. 40 (1939), 62-70. 7. H. Whitney, A function not constant on a connected set of critical points, Duke Math. J. 1 (1935), 514-517. 8. H. Whitney, On totally differentiable and smooth functions, Pacific J. Math. I (1951), 143-159. 9. S. Saks, Theory o f the Integral, New York, 1937, p. 311. 10. A. Sard, Images ofcritlcalsets, Ann. Math. 68 (1953), 247-259. UNIVERSITY OF AMSTERDAM

OPTIMAL

SELECTION BASED ON RELATIVE (the "Secretary Problem")

RANK*

BY

Y. S. CHOW, S. MORIGUTI, H. ROBBINS AND S. M. SAMUELS ABSTRACT

n rankable persons appear sequentially in random order. At the ith stage we observe the relative ranks of the first i persons to appear, and must either select the itb person, in which case the process stops, or pass on to the next stage. For that stopping rule which minimizes the expectation of the absolute rank of the person selected, it is shown that as n --~ oO this tends to the value j=x - - 7

~ 3.8695.

1. Introduction. n girls apply for a certain position. If we could observe them all we could rank them absolutely with no ties, from best (rank 1) to worst (rank n). However, the girls present themselves one by one, in random order, and Iwhen the ith girl appears we can observe only her rank relative to her i - 1 predecessors, that is, 1 + the number of her predecessors who are better than she. We may either select the ith girl to appear, in which case the process ends, or reject her and go on to the (i + 1)th girl; in the latter case the ith girl cannot be recalled. We must select one of the n girls. Let X denote the absolute rank of the girl selected. The values o f X are 1,..., n, with probabilities determined by our selection strategy. What selection strategy (i.e. stopping rule) will minimize the expectation E X = expected absolute rank of the girl selected? To formulate the problem mathematically, let xl, ...,x, denote a random permutation of the integers 1,..., n, all n ! permutations being equally likely. The integer 1 corresponds to the best girl, ..., n to the worst. For any i = 1,-.., n let y~=l + number of terms xx, " ' , x ~ - i which are < x~ (yi=relative rank of ith girl to appear). It is easy to see that the random variables Yx, "", Y, are independent, with the distribution 1 (1) P(Yf = J ) = 7 (j ,= 1, ... ,i), and that (2) P(x, = k[ Yl =Jl, "",Yt-1 =J,-1,Y, = J ) = P(x, = =(k-1

k I y,

=j) n

Received August 22, 1964 *Research supported by Ott~ce of Naval Research and Aerospace Research Laboratories. Reproduction in whole or in part is permitted for any purpose of the United States Government. 81

Y.S. CHOW et al.

82

[June

so that

(3)

e(xi [Yi = J ) = k~=t kP(xi = kl Yi = J ) = ni___++___1_i.j.

For any stopping rule z the expected absolute rank of the girl selected is therefore

EX=E(

n+l ) . We wish to minimize this value by optimal choice of T. ---~-~y,

To find an optimal z by the usual method of backward induction we define for i = O, 1, ..., n - 1, c, = c~(n) = minimal possible expected absolute rank of girl selected if we must confine ourselves to stopping rules ~ such that v > i + 1. We are trying to find the value Co. Now

(.+

c'~-a=E

(4)

) =_1

- n - ~ l y"

n

j= a

2

'

and for i = n - 1, n - 2,..., 1,

(5)

ci- a = E

~Yi,

min

ci

= -7- ~ min

Z--,---i-J,c~

j=a

o

These equations allow us to compute successively the values c,_ a, c,_ 2 , ' " , ca, Co and contain the implicit definition of an optimal stopping rule. Equation (5) can be rewritten more simply if we denote by Ix] the greatest integer < x and set

si =

(6)

i + l ci ]J -ff--~'~

(i=n--l,...,1);

then (5) becomes (7)

I [n+l

ci-1 = -T //---+-1-(1 + 2 + ... + si) + (i - s~)ci si(si+l)

1 {n+l = -:t

i+1

2

+ (i - s3ei

}

}

.

Defining s, = n, an optimal stopping rule is, stop with the first i > 1 such that Yi < si; the expected absolute rank of the girl selected using this rule is Co. We observe from (4) and (5) that n+l (8) C0 < ¢ 1 < == "'" =<~Cn-1 = - -2 ' and from(6) and (8) that s i x i and

(9)

sl<-s2<

...

1964]

OPTIMAL SELECTION BASED ON RELATIVE RANK

83

For example, let n = 4. Then from (4), (6),and(7), c3 = - ~ - , s 3 = 2 , c a = ~ -

q =

3-"

+~

"-~+

= ~-~,s2=l, 15

S1 = 0 ,

= T'

Co = C 1 = - ~ - ,

and an optimal stopping rule is given by the vector (s 1, " " , S 4 ) = (0, 1,2,4). The values of Co for n = 10, 100, 1000 are found by similar computation to be respectively 2.56, 3.60, 3.83. D. V. Lindley [1] has treated this problem heuristically for large n by replacing (7) by a single differential equation. His results indicate that for n ~ o% Co should approach a finite limit, but his method is too rough to give the value of this limit. A more adequate but still heuristic approach involves replacing (7) by an infinite sequence of differential equations, one for each value 0, 1,... of si. This method indicates that Iim Co (all limits as n ~ c~) has the value (10)

f i (j____~_2)l/j+ 1 ~- 3.8695. j=l

It is not clear how to make this heuristic argument rigorous by appealing to known theorems on the approximation of difference equations by differential equations. Instead, we shall give a direct proof that Co tends to the value (10). 2. The basic inequalities. We shall derive rather crude upper and lower bounds for the constants ci which will permit the evaluation of lira Co. To this end we define the constants i+1 (1) t~ -1 c~ (i = 0, 1,--., n -- i). n+ From (1.8) it follows that

(2)

//

to
n_l = - - f

and (1.7) becomes

(3)

ti-1 = si(si + 1) + 2(i - s3t i 2(i+ 1) ,

si = ['tJ (i = 1,..., n - 1).

For fixed i set

(4)

t~ = s ~ + 7,

0 < ~ < 1;

then (3) becomes

(5)

t~_l -

h(1 + 2i - t3 2(i+ 1)

~(1 - ~) 2(i + 1)'

84

Y.S. CHOW et al.

[June

Put (6)

T(x) - x(1 + 2i - x) . 2(i + 1) '

then for x < i + ½, (7)

1 + 2i - 2x >0 2(i + 1)

T'(x) =

so T(x) is increasing for x < i + ½, and by (5), (8)

tl-1 ~ T(h).

We now prove the first basic inequality. LEMMA 1. (9)

2n n--i+3

ti

(i = 0,..., n - 1).

Proof. (9) is true for i~, n - 1 since by (2) t.-1 -

n 2n 2 -4"

Assume (9) holds for some 1 < i ~ n - 1; we shall prove that it holds for i - 1. We know by (1.8) and (1) that i i h - I =h--'-+-i"c~-1 <- n +- l -

(10) •

n+l 2

i =--'2

°

2n 4 then (9) holds for i - 1. If ~-- > - n-i+4 so by (8), since T(x) is increasing for x < i + ½,

If2<=n-i2+

-

=

n-i--I- 3

=

(i + l ) ( n

-

then i + ~ > 2n =n-i+3'

i + 3) 2

<= n

- - i +

4'

since the last inequality is equivalent to ( n - i + 3) 2 + ( 2 n - 2 i - 1 ) ( n - i + 3) + 2n >= 0, which is true for n - i > 1. Hence (9) holds for i - 1 in this case also, and the lemma is proved. COROLLARY I. (12)

Co < 8

Proof. In (9) set i = [ 2 ] (13)

(n = 1, 2, ...).

. Then

n+l n+l c o _< c~ = / - - ~ T t ~ =< - - i + 1

_

_2n <

2n(n + 1) < 8.

1964]

OPTIMAL SELECTION BASED ON RELATIVE RANK

85

We next observe that (14)

t,_ 1 ~ ~

1

(i =-- 1,-.-, n - 1).

2(i + 1)

This inequality follows from (5) if we show that

ti(l+2i-ti)

~(1 - ~) i 2~(/-~1) ->- i ~ - l t i

2(i+1)

{ 1

h } 2(i+1) '

which reduces to (15)

ti 1

i +t,1

] _>_a(t /

= h - [td),

and this is true if t~ > 1, since t i < i +2 1....by (10), and if t~ < 1, since then h = ~. We now establish the second basic inequality. LEMMA 2 . 3(i + 1) tt ~_ 2(n -- i + 2)

(16)

(i = 0,..., n - 1).

Proof. (16) is true for i = n - 1; suppose it is true for some 1 < i < n - 1. Define

r(x)=x

1

2(i+1)

'

i+1 which is increasing for x < i + 1. Since by (10) h < ~ ,

ti-1 >

i

=

i+1

T(ti)>

i__~T(

= i+1

3(i+1)

we have by (14), )

2(n-i+2)

3i(4n - 4i + 5) > 3i 8(n-i+2)2 =2(n-i+3)" which is equivalent to i < n - 1. This proves the lemma. We have seen (1.9) that for any positive integer k, if n > 2k then sn-t ~ k. We now define for each k = 1,2, ..- and each n > 2k,

(17)

ik

----

smallest integer j >_ 1 such that sj > k.

We note that s ~ - I = 0 and hence from (1.7), (18)

Co = cl . . . . .

c , _ I.

86

Y.S.

CHOW

et

[June

al.

COROLLARY 2. (19)

lim i ! > 1 ..... n

Proof.

=8

•

If ix > In/2] then ix > In/2] + 1 > n/2, ( q / n ) > ½. If i x < In/2] then

by (13), l < si~ < ti: -- i~--+ l

=

i 1 +1

ia + l

n + l Cil = < n + l C [ " / 2 ] < - - n. 8+.l

=

n+l (We remark that i 1 > 1 for n > 2, since if i x = 1 then sl = 1 and Co = --~---, which only holds for n =< 2.) C O R O L L A R Y 3.

On

every set

(20)

{ ~ < - - = n i< f l ; 0 < ~ < f l < l } ,

(21)

lim (ti - t _ 1) = 0

uniformly.

Proof. From (14) and (9), 0 =< t , - q_~ =< t~

ti

i i + 1 fi

< (1 + ti) 2 < ( = 2(i + 1) =

1

}

ti

2(i+1)

-- i + 7

1 +---

l+] <

2(i + 1)

it2 + --------~ 2(i+1)

--Z-2~

n

COROLLARY 4. For k = 1,2,... a n d n > 12k, ik__> 1 _ 2

(22)

'

n

i__L < 1 _

(23)

n =

1

-~/~

Proof. By (9), Sik > k ~ tik > k => ~ =

=

2n

>- k =>

n -- ik --

tk> 1 n

which proves (22). (23) holds if ik < [ 2 ] , for then

i__Lk< __1 < 1 n = 2 =

1 2k'

1 • --

2 - -k'

---~ O.

1964l

87

OPTIMAL SELECTION BASED ON RELATIVE RANK

a n d i f ik > [ 2 ] then by (16), slk_x
3ik 3ik
>

3 /__k+3 ~-~ < 1-n

/~< 1

n

n

3 - ~ + n

3 --<1--

3n 3:~-k
k + 3

for n > 12k. =

COROLLARY 5.

(24)

lira hk = lira t~k_~ = k

(k, ?, = 1,2, ...).

Proof. t~_~ < k _<_ttk. 1

1

Choose ~, fl so that 0 < u < -8-, 1 - ~ < fl < 1. Then by (19) and (23),

(25)

~ <

f~ - ~

n

<

~
for sufficiently large n. Hence by Corollary 3, lim(hk -- hk-r) = 0. COROLLARY 6. For k = 1,2,... (26)

sik = k for sufficiently large n,

(27)

lim(ik+l -- ik) = oo.

Proof. k _<-s,k -<_ti~ together with (24) proves (26). lim (t~ +~ - fi~) = 1 and lim(t~k+, - ttk +1- ~) = 0 by (24), and these relations imply (27). 3. P r o o f of the Theorem. Choose and fix a positive integer k and let n by (2.26) be so large that sik =k, sik+t = k + 1. For ik =< i < i t + l define k v~= t, - ~ .

(1) Substituting in (2.3) we find that k

k(k+l)+2(/-k)

%-1 + -~- = (2)

vt =

2(/+ 1) i+1

i--kv~-l"

v~+~-

k

i-k

= T + TFT v''

88

Y. S. CHOW

Hence for

ik <

[June

i < ik+l,

i+1

i

i+1 ik

q- 1

ik

ik

ik-t-2 ik--k+l

i i-k-1

i+1

vi = i - - k O t - l - i - k

(3)

et al.

vik

i+l-k k+l~ i + j - k ~ + 1 - k " vik = vikj =~Il \ ~ j ~ k '

and hence

tl

(4) Set i

--

ik+1

- -

=

k ( t t ~ - - ~ ) kH ( i + j - k -~+ j=,

~

?F~jr:--k/"

1; then

H

_

From (2.19) and (2.24) it follows that / ) k k k+l l--[ lim/ik+~ +j -- k - 1 = k + l =-2- + T j=, \ ffk~-7 L---kk

"2k+ k_--lim k + (ik+l) 1- - 2 \ ik

and hence

From (2.22) (7)

(1--~-)kfil(

j___~/j+l

j = ~ j + 2 /

< l i m - - < l - ~ - - i ~ il <~-1~11[ j =

, n

=

n

.=

\j%-T/

Letting k-+ o%

--

(8)

/I

~

"

j=l

Now by (2.24) and (2.18), 1 =limt/l_ 1 = lim(

ix

(9)

j .i=1

Thus we have proved the THEOREM.

,) lim( o)

j=l

~1/j+1.

~l/J+l "

1964]

OPTIMAL SELECTION BASED ON RELATIVE RANK

89

4. Remarks. 1. It is interesting to note that co = co(n ) is a strictly increasing function of n; thus in view of the Theorem, (1)

co(n) < 3.87

(n = 1, 2,...).

A direct proof that co(n) is strictly increasing based on the formulas of Section 1 is difficult, since there is no obvious relation between the c~for different values of n. However, a direct probabilistic proof can be given which involves no use of the recursion formulas. Let ( s l , . . . , s , , n + 1) be any stopping rule for the case of n + 1 girls such that st < i for i = 1, ..., n (any optimal stopping rule has this property). Define for i = 1, ..., n ={sj (2)

for j = l , . . . , i - 1 ,

tj(i) Sj+x for j

=

i,...,n,

and for j = 1 , . . . , n - 1,

(3)

t l ( n + i) = ( ~ for j = n.

It is easy to see that at least one of the stopping rules defined by (tl(i),..., t,(i)), i = 1, ..., n + 1 must give a value of co for the case n which is less than that given by (sl,..., sn, n + 1) for the case n + 1. Hence Co(n) < co(n + 1). 2. We assumed that the n girls appear in random order, all n! permutations being equally likely. The minimal expected absolute rank of the girl chosen is then Co < 3.87 for all n. Suppose now that the order in which the girls are to appear is determined by an opponent who wishes to maximize the expected absolute rank of the girl we choose. No matter what he does, by choosing at random the first, second, ..., last girl to appear we can achieve the value E X = (1 + 2 + ... + n)/n =(n + 1)/2.

And in fact there exists an opponent strategy such that, no matter what stopping rule we use, E X = (n + 1)/2. Let Xl = 1 or n, each with probability 1/2; let Xt÷l = either the largest or the smallest of the integers remaining after x~, ...,x~ have been chosen, each with probability 1/2. If we define for i = 1,..., n

(4)

z I = E(x~ [Yl, "", Y~), ~ = &(Yl, "", Y~),

then it is easy to see that {z~,&~(i = 1, ...,n)} is a martingale, so that for any stopping rule ~, (5)

g ( x ) -- E ( z 0 = e ( z l ) = (n + 1)/2.

90

Y.S. CHOW et al.

Many extensions and generalizations of the problem considered in this paper suggest themselves at once. Some further results will be presented elsewhere.

REFERENCE 1. D. Y. Lindley, Dynamic programming and decision theory, Applied Statistics 10 (1961), 39-51. P~RD~'~ U~uv~srry UNIVERSITYOF TOKYO COLUMmAUNIVERSITY PURDUEUNDJF...RsrrY

ADDITION AND DECOMPOSITION OF CONVEX POLYTOPES(t'2) BY

WILLIAM J. FIKEY AND BKANKO GRONBAUM ABSTRACT

A new addition of convex polytopes is defined and the possibility of representing each polytope as a sum of "standard" polytopes is established Introduction. Vector addition of convex bodies is very useful in different investigations. However there are problems for which vector addition, though appropriate in the plane case, becomes unsuitable in higher dimensions. An example is the question of decomposability of polytopes. In the plane every polygon is the sum of finitely many summands of a simple type (segments and triangles), and every convex set is the limit, in the Hausdorff metric, of finite sums of triangles; both assertions fail to have analogues in higher dimensions. Blaschke in [3, p. 112] suggested another composition process for convex bodies which involves the pointwise addition of the products of the principal radii of curvature as functions of the outer normal in the case of sufficiently smooth convex bodies. Even earlier Minkowski [10, pp. 116-117], discussed a corresponding process of composition for polyhedral bodies. Cf. also 14, p. 124]. In the present paper we shall define a new addition for convex polytopes which is a modification of that mentioned by Minkowski and which may be considered as a special case of the addition of generalized curvature functions. Our approach is elementary except that, in section 4, we discuss the generalization of this addition to arbitrary convex sets.

The new addition is such that the known results on planar decomposition in terms of vector addition have valid analogues in higher dimensions. Further, the addition coincides with vector addition in the case of non degenerate polygons and so planar theorems similar to the usual ones are included in a natural way. Received April 24, 1964. (1) The research reported in this paper was supported in part by the National Science Foundation NSF-G 19838, and by the Air Force Officeof ScientificResearch grant AF EOAR 63-63. (z) Lecture delivered by the second author at a symposium on Series and Geometry in Linear Spaces, held at the Hebrew University of Jerusalem from March 16 till March 24, 1964. 91

92

W.J. FIREY AND B. GRONBAUM

[June

In section 1 we define the new addition which rests on Minkowski's theorem about the determination of a convex polytope by the directions and areas of its faces of maximal dimension. Some related notions are discussed. Sections 2 and 3 contain decomposition results, while section 4 is devoted to variants and generalizations of the addition. 1. The new addition of convex bodies. Let P be a k-dimensional convex polytope in Euclidean d-space E a such that the origin is in the relative interior of P . Let E k be the k-space spanned by P and let f ( P ) > k + 1 denote the number of ( k - 1)-dimensional faces of P. With each such face F~, 1 <=i < f ( P ) , we associate a vector N l as follows: (i) If k = 1, i.e. if P is a segment with end points F1 and F2, we set N~ = (-1)i(F2 - F1).* (ii) If k _->2, then Nt e E k, its direction is that of the outer normal to Fl and its length ]N~] equals the (k-1)-dimensional content of F~. This definition associates a system ~f'(P) = {N~I 1 < i <_-f(P)} of vectors with every polytope P containing the origin in its relative interior. We extend this association. Clearly if two translation-equivalent polytopes PI and P2 contain the origin as a common relative interior point, then .3<'(P1)= .A/'(P2). Hence, for any convex polytope P , we may define JV(P) to be ~ f ' ( P - Q) where Q is any relative interior point of P. A system ~e- = {Vii I _< i _< n} of non-zero vectors in E k is called equilibrated if ~7= 1 V~= 0 and if no two members are positively proportional. ~e" is called fully equilibrated in E k when it is equilibrated and E k is the span of ~¢'. The following result is well-known and easily proved, cf. [10]: (M1) If P is a convex polytope in E d, then JV(P) is equilibrated; moreover if 0 ~ int P and P spans E k, then ~/'(P) is fully equilibrated in E k Minkowski's existence and uniqueness theorem is much deeper, cf. [10], [11] and also [2], [4]: (M2) If ~ is a fully equilibrated system of vectors in E k , k ~- 2, there exists a convex polytope P , unique to within a translation, such that ~¢" = .£'(P). Clearly P is k-dimensional. The above facts make it possible to define a composition of convex polytopes called #-addition. More precisely, we define #-addition between the classes of translation-equivalent polytopes (however, see remark 2 of section 4) in the following way: Let Pj,j = 1, 2, be convex polytopes of dimension kj in E d and let the indexing of their associated systems

,W'(Pi) = {N~J)[ 1 < i < nj = f(Pj)} * We do not distinguish a point and the radius vector of the point.

1964]

ADDITION AND DECOMPOSITION OF CONVEX POLYTOPES

93

/~T(2) are positively proportional for i satisbe chosen so that the vectors ]~j(1) ..~ ,.,~ fying 1 _< i _< no < n. while no other pair of vectors from ~r(Pi)w ;ff(Pz) are positively proportional. Then the system

"P~

=

{~l l
defined by

~=

r •~T(I) ~T(z) , ,~ s~., , ~

for

~N} I), /

for n o < i < n i ,

L M~2-)l+no,

for nl < i < n l + n2 - no,

t
is equilibrated since each Jff(Pj) is equilibrated. Moreover, the linear span of ~//"is of dimension k which satisfies k > max (kl, k2). Hence ~ is fully equilibrated in some E k. According to Minkowski's theorem (M2) there exists a convex polytope P in this E k such that ~e~= eft(P) and P is unique to within a translation. We define P

=

P1 ~:P2.

It is convenient to define an associated multiplication by a scalar factor 2. If 2 = 0, we define 2 × P to be a point; otherwise 2 x P is that convex polytope for which Jff(2 x P ) = {2Nil Ni e.A/'(P)}. Again, by (M2), the existence and uniqueness up to a translation are assured. Clearly ( - 1) x P is the image of P under a central reflection and, if P is k-dimensional for k > 2, then 2 X P = q-121 tl(k- l)p where the last is the usual scalar multiplication associated with vector addition and the indeterminate sign is that of 2. For k = 1, ;t x P

=121P The properties of ~-addition and its associated x-multiplication which are listed below are easily verified: PI~P2

= P2~P1,

P1 @ (P2 @ P3) = (P1 @ Pz) ~: P3, 2 X ( P t @ P 2 ) = 2 x P 1 :~ 2 x P2,

(21).2) x P

= 21 x ( 2 2 x P ) ,

(21+22) x P = 2 1 x P ~ : 2 2 x P

when 2122>0.

We shall also use the notation i=l

Pz = Pl ~ P2 ~ ... ~ P,.

REMARK. In the plane the vector sum P1 + P2 of two non-degenerate polygons has the property that the length of any edge e is the sum of the lengths of

94

W.J.

F I R E Y A N D B. G R U N B A U M

[June

those edges of PI and P2 which have the same outer normal as e. Hence P1 + P2 = Pz 4~ P2 in the plane. 2. A decomposition theorem. Our first decomposition result is essentially a geometric formulation of the algebraic fact that an equilibrated system of vectors is a superposition of minimal equilibrated systems. THEOREM 1. Every convex polytope P is expressible in the form m

(*)

P =

4~ P~, t=1

where each P~ is a simplex. Further, if P is d-dimensional and f ( P ) = n >=d + 1, then there is a representation (*) with m <=n - d. Proof. We use induction. The assertion is obvious for d = 1 and also for d > 1 when n = d + 1. Thus we may assume from here on that d > 1, n > d + 1. Without loss of generality we may assume further that the origin 0 is in the relative interior of P. Let C be the convex hull of .,4r(P) and let N~o e eft(P). Then, for a suitable % > 0, we have -~oN~o ~ b d r y C and so, by Carath6odory's theorem, d

-~ON~o =

~, =,N,~,

v=l

=, ~_ O.

In other words, some positive combination of at most d + I vectors from ,/((P) is zero: IT

(1)

~ ~,N, = O. v=0

We suppose the indexing to be chosen so that 0tv ~ 0 when 0 < v < do where do < d and ~v = 0 for v > do. We also assume that the vectors N~ and weights ct, were such as to make do minimal. Then - % N t o is a relative interior point of the (do-1)-simplex determined by the points Nt,, 1 < v < do. Set (x =

max a v, o~v__.do

and fl, = a,/~ for 0 < v < do; then O
max Oa_v~_~o

f l ~ = 1.

1964]

ADDITION AND DECOMPOSITION OF CONVEX POLYTOPES

95

By equation (1): do

/Vviv = o, v=0

and therefore the system ~o = {flvN~vI 0 < v < do} is equilibrated. Hence the system ~ obtained from

{ ( 1 - f l , ) N , v l O < v<do} U

{N, l i~{i, l O<_v<_do}}

by omitting the null vectors is also equilibrated. By (M2), d o and ~ each determines a polytope p d - d 1 + 1 . For, if q => 0 is the number of fl, # l, then

n = n~+l+do-q. On the other hand, the q non-zero vectors in { ( 1 v _ do} are linearly independent since ~o is associated with a simplex p~O). Thus the dimensionality of the intersection of the spaces E a° and E al is at least q and so d < dl - d o - q. This establishes the observation. On applying the induction assumption to pO), we find that pO) is representable as the ~-sum of no more than n~ - d~ simplices. Therefore P is decomposable into at most 1 + n x - dl < n - d simplices as claimed. REMAmC 1. The vector-sum analogue of Theorem 1 is well known for poly, gons (see [14]); however, even in E 3 , there are infinitely many types of polyhedra P which are indecomposable under vector addition, i.e. such that, if P = P1 + P2, then each P, must be homothetic to P. See Gale [8], Shephard [12]. REMARK 2. Since every d-dimensional convex polytope may be approximated in the Hausdorff metric arbitrarily well by polytopes, no d of whose outer normals are linearly dependent, the proof of Theorem 1 yields immediately the following THEOREM 2. Every d-dimensional convex polytope P may be approximated in the Hausdorff metric arbitrarily well be finite ~--sums of d-simplices. I f P has n faces of dimension d - l , the number of summands need be no more than n - d . It is remarkable that the analogous assertion for vector-sums is false for d > 3; in E 3 e v e n the regular octahedron is not the limit of finite vector sums of simplexes, cf. Asplund I-9, p. 264], Shephard 113].

96

W.J. FIREY AND B. GRONBAUM

[June

REMARK 3. We omit the simple proof of the following result which has no analogue in the case of vector-addition for d > 3. We let Ix] be the greatest integer not larger than x.

Every centrally symmetric polytope P is a #-sum of parallelotopes. More precisely, if P is k-dimensional and has 2refaces, m >=k, then P is representable as a sum of - [ - r e ~ p ] p-dimensional parallelotopes where 1 < p < k. 3. A representation theorem. In a certain sense, ~:-addition seems more natural if the summands and the sum all have the same dimensions; in other words if the systems ~Ar(P~), ~A/'(P) are all fully equilibrated in the same E k. Following this idea, one is led to the question as to whether every polytope in an E k may be represented as a ~-sum of k-simplices in E k, or other "standard" polytopes of the dimension k. Without loss of generality, we may take k = d . The example of the cube shows that simplices alone will not suffice for the purpose. Indeed for every representation of the d-cube P as P = P1 ~ P2 with PI and P2 d-dimensional, we have

f(P1) = f(P2) = f P ) . Thus the bound 2d in our next theorem is the best possible. THEOREM 3. Every d-polytope P is representable in the form P= ~ "=1 Pi

where each P~ is a d-polytope with f(Pi) <=2d. Proof. We prove the theorem by induction. The assertion is trivially true for the cases d = 1 and d > 1, f ( P ) < 2d. Thus we may assume d > 1, f(P) > 2d. The vectors in ./if(P) span E a, i.e. the origin 0 belongs to the interior of the convex hull of the points {N, I 1 < i < f(P)}. By a Carathdodory type theorem on the interior points of the convex hull of a set, (see e.g. [6], Theorem 3.2) there exists a subset I of {1, 2,. . ., f (P)} which contains at most 2d integers and is such that 0 is in the interior of the convex hull of {N~[i ~ I}. Therefore, for suitable ~i > 0, the system ~ = {aiNi[ i~I) is fully equilibrated in E d. Obviously we may assume that the a, are such that maxi e lOgI 1. Let uff2 = { M j [ j ~ J } be the system obtained from =

{ ( 1 - a i ) N , ] i ~ I } U {N, liq~I } by the omission of zero-vectors. Since .#'(P) and ~4rl are fully equilibrated, ¢ff2 is equilibrated. Let Px and P2 be polytopes such that .A/'(P1)= .A/"x , ~g'(P2)= "#'2. If ¢ff2 is fully equilibrated, that is if P2 is d-dimensional, then the proof is completed by induction since f(P2):
1964]

ADDITION AND DECOMPOSITION OF CONVEX POLYTOPES

Suppose, however, that ~/'2 is not

97

fully equilibrated; let E k, where

1 < k < d - 1, be the space spanned by -~2. Since P2 is k-dimensional, by the

inductive assumption it is representable in the form q

P2 =

~R

where each R~ is k-dimensional and f(R~) < 2k. But P=PI~P2=

~

R~

xP1

;

s----1

thus the theorem will be proved if we establish it in the case that f(P2) < 2k, i.e. provided J has at most 2k elements. Let p be that projection of E d onto E d-k which carries E k onto 0. The projection of a fully equilibrated system is fully equilibrated. Thus {p(N~)I i ~ I} is fully equilibrated in Ed-k; possibly some p(N,) are zero vectors and have to be omitted. As before, there exists a set 10 c 1 which has at most 2 ( d - k ) integers, as well as a collection of positive numbers fl, < ~ / 2 such that

~, fl~p(Ni) = 0 I~lo

where {p(N~)I ielo} is fully equilibrated in E d-k. Now the vector N =

/ iN, le Io

is in E k. Since ~

is fully equilibrated in Ek, there is a fl, 0 < fl < 1, for which - fiN =

~ ?jM~

where 7y > 0 and 0 < max,, ~r 7j = ~ < 1. Consequently, the two systems obtained by the deletion of any zero vectors from the two systems

if7 =

ielo} w {(I

-

~

-

?,)M/ljeJ}

and

are both fully equilibrated in E and each contains less than f(P) vectors. Hence, the inductive assumption may be applied to the d-polytopes PI* and P2* corresponding to the systems eft1* and ¢4r2*. Clearly P = PI* ~ P2* and so this completes the proof of Theorem|3.

98

w . J . F1REY AND B. GR0"NBAUM

[June

4. REMARKS. (1) By a slight change in definitions, @-addition in the plane may be made to coincide with vector addition of polygons and segments. Only the definition of JI/'(P) for the case of a segment P needs to be modified to read: If P is a segment, alP(P) is a pair of opposite vectors, each of length equal to that of P and perpendicular to the carrier line of P. The definition of J/'(P) for proper polygons and the definition of @-addition in terms of the associated equilibrated systems remains unchanged. Then it is easily seen that P1 + P2 = P1 @ P2 for all proper or improper polygons PI and P2. Theorems 1 and 3 remain valid and become only reformulations of well-known results. In the first case: Every polygon is a vector sum of segments and triangles. In the second case the representation involves triangles and quadrangles. (2) Let a(P) denote a point valued function, defined for all convex polytopes P , which is translation invariant, that is

a(P + X) = a(P) + X for any point X. For example, take a(P) to be the area centroid of P. Minkowski's theorem (M2) implies that if q/" is an equilibrated system there exists a unique convex polytope P for which eft(P) = f and a(P) is a preassigned point. Let f(P) =n and

i=1

Then an addition of convex polytopes (as opposed to classes of translationequivalent polytopes) can be defined by taking the composite of PI and P2 to be that translate of P1 ~: P2 for which a(P) has the value [w(P1) a(el) + w(P2)a(P2)]/[w(P1) + w(P2)] • This composition is commutative and associative. (3) The ~-addition is a specialization to convex polytopes of an operation which may be defined for all convex bodies. For simplicity we discuss only the case of d-dimensional bodies in E ~. The area function SK(og) of a convex body K is a non-negative, totally additive set-function defined for the Borel sets co of the surface f~ = {~} of the unit sphere of E d by the following condition. SK(og) is the (d-1)-dimensional content of the set of boundary points of K each of which has a supporting hyperplane with outer normal in co.

1964]

ADDITION AND DECOMPOSITION OF CONVEX POLYTOPES

99

Minkowski's theorem (M2) has the following generalization, (see [1], [5], [7]): A non-negative, totally additive set-function ~b(og) over the Borel sets of f/ is the area function S~(o9) of a convex body K if and only if ~bis positive for each open hemisphere and f a ~dp(df~) = 0

i.e. the centroid of the mass-loading of f~ specified by q~ is at the centre of f~. Moreover, if ~b satisfies these conditions, K is determined to within a translation. Now if K1 and K2 are convex bodies in E d, it follows that there exists a convex body K~ ~ K 2 unique to within a translation, which has area function

s ,(co) + This #-addition of general convex bodies reduces to the composition process suggested by Blaschke which we mentioned at the beginning of this paper if the bodies are sufficiently smooth. It may have applications to different problems. As a minor instance, we mention the following. The ~%-sum of convex bodies of constant brightness is clearly of constant brightness. Now the only such convex bodies which have been explicitly described are the sphere and a special figure of revolution Ko, see [3, p. 153]. The existence of bodies of constant brightness which are not figures of revolution is assured: for we may let K 0 and K~ be two bodies of the type described by Blaschke which are not coaxial. Then it is easily shown that Ko # K~ is not a figure of revolution, but it is a body of constant brightness. One more observation along these lines: a central-symmetric body of constant brightness must be a sphere. This gives the curious result that, if K is of constant brightness, K # ( - K ) is a sphere. The analogous result for vector addition is: if K is of constant width, then K + ( - K ) is a sphere.

REFERENCES 1. A. D. Aleksandrov, On the theory of mixed volumes of convex bodies, Mat. Sb., 2 (1937) 947-972, 1205-1238; 3 (1938), 27-46, 227-251 (Russian). 2. A. D. Aleksandrov, Convex polyhedra, Moscow, 1950, (Russian; German translation under title: Konvexe Polyeder, Berlin, 1958). 3. W. Blaschke, Kreis und Kugel, 1st ed., Leipzig, 1916. 4. T. Bonnesen and W. Fenchel, Theorie der konvexen Ki~rper, Berlin, 1934. 5. H. Buseman, Convex surfaces, New York, 1958. 6. L. Danzer, B. Griinbaum and V. Klee, Helly's theorem and its relatives, Proc. Symp. Pure Math., VII (1963), 101-180. 7. W. Fenchel and B. Jessen, Mengenfunktionen undkonvexe K~rper, Danske Videnskabernes Selskab. Math-fys. Meddelelser, XVI, No. 3. (1938). 8. D. Gale, Irreducible convex sets, Proc. Internat. Congress Math., vol. 2, 217-218, Amsterdam, 1954.

I00

W.J. FIREY A N D

B. G R O N B A U M

9. B. Griinbaum, Measures of syrametryfor convex sets,Proc. Syrup. Pure Math, VII (1963), 233-27O. 10. H. Minkowski, AIIgemeineLehrsiitzeiiberkonvexe Polyeder,Nachr. Ges. Wiss. G6ttingcn (1897), 198-219. (Ges. Abh., vol. 2, 103-121, Leipzig and Berlin, 1911). 11. H. Minkowski, VoIumen und Oberfl~iche,Math. Ann., 57 (1903), 447-495 (Gcs. Abh., vol. 2, 230-276, Leipzig and Berlin, 1911). 12. G. C. Shephard, Decomposable convex polyhedra, Mathcmatika, 10 (1963), 89-95. 13. G. C. Shephard, Approximation problems for eonvexpolyhedra, Mathematika, 11 (1964), 9-18. u 14. I. M. Yaglom and V. G. Boltyanskil, Convex figures, Moscow and Leningrad, 1951. (Russian; German translation 1956; English translation 1961). OREGON STATE UNIVERSITY, CORVALLIS, ORE.GON, U.S.A.

THE HEBREW UNIVERSITY OF JERUSALEM

WEAK COMPACTNESS AND REFLEXIVITY(1) BY

ROBERT C. JAMES ABSTRACT

Several characterizations of weak-compactness are given for subsets of complete locally convex linear topolegical spaces and of Banach spaces. Some are new and some are generalizations of known facts. Introduction. The purpose of this paper is to study characterizations o f weak compactness of bounded sets in complete real locally convex linear topological spaces and in real Banach spaces and to use these characterizations o f weak compactness to obtain characterizations of reflexive Banach spaces. Some of the characterizations are new, many are improved or established for more general cases than previously, and some are known but are proved here both as useful steps in sequences of implications and to demonstrate relations to other characterizations. Only properties equivalent to w-compactness will be discussed. For bounded w-closed subsets E of a locally convex linear topological space, each of (1)-(17) is equivalent to w-compactness. If E also is convex, we can include (18)-(25) as well, and also (26) if E contains 0. For bounded w-closed subsets of a Banach space, each of (1)-(17) and (27)-(28) is equivalent to w-compactness. Each of (1)-(38) is a necessary and sufficient condition for reflexivity of a Banach space, with E understood to be the unit ball. The symbols X + Y and X - Y will denote the sets of all sums x + y and all differences x - y with x in X and y in Y. The abbreviations "w-closed" and "w-compact" will be used for weakly closed and weakly compact (i.e., closed and compact relative to the weak topology). Also, "we-compact" will be used for weakly countably compact and "ws-compact" for weakly sequentially compact. Since all spaces used are T 1 (and in fact Hausdorff), countably compact can mean either that any countable open cover contains a finite cover or that each infinite subset has an accumulation point in the set. A weakly sequentially compact set is a set such that each sequence in the set contains a subsequence that converges weakly to a point in the set. The closure of a set E will be denoted by el(E) and the linear span of a set E by lin(E). The convex span of E will be Received August 19, 1964. (1) Lecture delivered at a symposium on Series and Geometry in Linear Spaces, held at tho Hebrew University of Jerusalem from March 16, till March 24, 1964. 101

102

R.C. JAMES

[June

denoted by cony(E) and is the set of all finite sums ~,~ix~ with each ~l nonnegative, ~ c~i= 1, and each xi in E. The circled span of E will be denoted by cir(E) and is the set of all finite sums ~,aix, with Ela, ] <=1 and each x, in E. The fiat span of E will be denoted by fiat(E) and is the set of all finite sums ~aix~ with ~ a i = 1 and each x~ in E. Several applications will be made of the following elementary facts. THEOREMON STRONGSEPARATION [12, Theorem 14.3, p. 118]. I f T is a locally convex linear topological space and X and Y are nonempty disjoint convex subsets of T, then 0 is not a member of c l [ Y - X] iff there is a continuous linear functional f such that s u p { f ( x ) : x E X } < inf{f(y): y~ Y}.

A useful special case of this theorem states that if K is a closed convex subset of T, then for any member x of T not in K there is a continuous linear functional f with f ( x ) > s u p { f ( y ) : y ~ K } [2, Theorem 5, p. 22]. HELLY'S CONDITION (see [2, Theorem 3, p. 38], and [12, pp. 151-2]). I f T is a normed linear space and f l, "",f~ are linear functionals on T, then for numbers cl, ..., cn and ~ > 0 there exists an x in T with II xll < M + 8 and fk(X) = Ck for each k iff 1

I

for all numbers a~,...,a~.

LEMMA. For any bounded sequence (x,} in a normed linear space T, there is an F in T** such that lim f(xn) < F ( f ) <= lim f(x~) for all f in T*. Proof. Let # be a linear functional of unit norm on the space re(co) of bounded sequences with the property that lim tn =< #(t) =< lira t~ for all t = {tl, ...}. Then we can define F that satisfies the desired inequality by letting F ( f ) = # ( ( f ( x l ) , ' " } ) for all f in T*. The functional # can be any linear functional of unit norm on m(og) with #(0 = lim tn whenever this limit exists, or p can be a Banach limit [2, Theorem 2, p. 83]. 1. Bounded w-closed subsets of complete locally convex linear topological spaces.

Most of the conditions listed as (1)-(9) of Theorem 1 have been studied previously, but some only for less general cases. It has long been known that

1964]

WEAK COMPACTNESS AND REFLEXIVITY

103

a Banach space is reflexive iff (3) is satisfied for E the unit sphere and {x,} an arbitrary transfinite sequence in E [5], and iff (4) is satisfied for E the unit sphere (see [15] and [20]). However, the equivalence of (1) with each of (2), (3) and (4) is now well known (see [2, Corollary 2, p. 51], and [12, Theorem 17.12, p. 159]). Condition (6) is closely related to the well known condition (5) (see [6, pp. 177 and 185], and [12, Theorem 17.12, p. 159]). Conditions of type (7) and (8) were developed first for the unit sphere of a Banach space [8, Lemma 1, p. 159] and later for bounded closed convex subsets of a Banach space [11, Theorems 1 and 2, pp. 130-131]. Condition (9) was developed first for the unit sphere of a Banach space [9, Theorem 1, p. 206] and is closely related to the later concept of a cone isomorphic to the cone spanned by unit members of 1a discussed in [16] as a condition for nonreflexivity of Banach spaces. Condition (9) has also been studied for bounded closed convex subsets of a Banach space [11, Theorem 3, p. 132]. THEOREM 1. Let T be a complete locally convex linear topological space and let E be a bounded w-closed subset of T. Then the following are equivalent: (1) E is w-compact. (2) E is we-compact. (3) For each sequence {x,,} in E there is an x in E such that, for all continuous linear functionals f , lim f(x,) < f(x) < lim f(x,). (4) I f {K,} is a nested sequence of closed convex sets and E f) K, is nonempty for each n, then E [3(0 K,) is nonempty. (5) For each sequence {x,} in E and each equicontinuous sequence {fn} of linear functionals, lim lira f,(xk) = lim lim f,,(Xk) n

k

k

n

whenever all of these limits exist. (6) For each sequence {x.} in E and each equicontinuous sequence {f~} of linear functionals, inf{f.(Xk): n < k} < sup{f.(Xk): n > k}.

(7) For each sequence {x.} in E, the member 0 of T belongs to cl [O___l (conv{xi, "",x.} l conv(x.+ l, ""}) ] •

(8) For each sequence {xn} in E, the member 0 of T belongs to cl[d=l(lin{xl,...,x.}-conv{x.+l, ""})] •

104

R.C. JAMES

[June

(9) There does not exist a positive number O, a sequence {zn} in E, and an equicontinuous sequence (g,} of linear functionals such that

g~(Zk) > 0 if n <__k,

g,(Zk) = 0 if n > k.

Proof. Clearly (1) ::> (2), since any Tl-space is countably compact if it is compact; (2) :~ (3) follows from the fact if x is an accumulation point of {x~}, then the inequality in (3) is satisfied for all f. To show that (3) ~ (4), let {Kn} be a nested sequence of closed convex sets and E 0 K~ be nonempty for each n. Choose x, from E N Kn for each n. If x in E satisfies the inequality in (3) for all f, then x ~ 0 K~. For if there is an n such that x ~ K,, then there is a continuous linear functional • with ~ ( x ) > sup {~(y): y ~ K,}.This contradicts (3), since then limtI)(x.) < ~(x). We shall complete the proof of Theorem i by showing that: (4) ~ (5) :,- (6) =~ (9),

(4) ~ (7) =~ (8) =~ (9),

(9) =~(1).

To show that (4) =~ (5), let {x.} be a sequence in E, let {fn} be an equicontinuous sequence of linear functionals for which all the limits in (5) exist, and use (4) to obtain an x that belongs to cll-conv{xn+l,-..}] for all n. Then limkf.(Xk)=f.(x) for all n, and therefore

lira lira f,,(Xk) = limf,(x). n

k

n

If L = limk lim~fn(Xk) and for a positive number 8 we choose K so that I L - limf~(x~) I < e

if k > K,

n

then I L - lim.f.(x) I _-<e. Therefore L = limJ,(x). The implication (5) =~ (6) is easy. For if {x,} is a sequence in E and (f.} is an equicontinuous sequence of linear functionals, then is bounded and there is a subsequence {(x.',f')} of {(x~,f,)} for which all the limits in (5) exist. Then the equality in (5) for {x',} and {/~} implies the inequality in (6). To show that (6) => (9), we suppose (9) is false and let 0, {z,}, and {g,} be as described in (9). Then

lYn(xk)l

inf {g~(zk): n < k} > 0 > 0 = sup {g.(Zk): n > k}, which contradicts (6). The implication ( 4 ) ~ (7) has a direct proof: If {x,} is a sequence in T, then using (4) there is an x thatis a member of cl[conv {x~+l,'"}] for all n. Then for an arbitrary neighborhood W of 0, we choose a neighborhood U of 0 such that U - U c W. For some n, there is an r in conv {xx, ...,x,} with x - r in U. For this (and any other) n, there is an s in conv {x,,+ 1,'"} with x - s in U. Then W contains r - s and (7) is verified. The implication (7) ~ (8) is formal. To show that (8) :~ (9), we suppose (9) is false and let 0, {z,}, and {g,,} be as described in (9). Let W be a

1964]

WEAK COMPACTNESS AND REFLEXIVITY

105

neighborhood of 0 chosen so that [gn(x) [ < 0 for all n if x ~. W. Then for any numbers {ai} and any nonnegative numbers {cq} with ~n+l ~, = 1, we have

Therefore W N [ U ~ = , (lin {xl,'", x,} - cony {x,+ 1,'"})] is empty. It remains to show that (9) implies (1). First we use the fact that T can be represented as a subspace of a product IIB~ of Banach spaces [12, pp. 46-47]. The weak topology of IIB~ is the same as the product topology when each B~ is given its weak topology. Since T is complete, T is strongly closed in IIB~. Since T also is convex, T is w-closed in IIBa. The canonical projection E~ of E into B~ is bounded in B~. If wcl (E~), the weak closure of E~ as a subset of B~, were w-compact for each 2, it would follow from theTychonoff theorem that the product II[wcl(E~)] is compact in the product topology when each B~ is given its weak topology. This would imply that E is w-compact, since E being w-closed in this product follows from E being w-closed in T and T being w-closed in IIBa. Thus at least one wcl(E~) is not w-compact in the corresponding B~. We can identify this Ba with a subset of a space re(A) of bounded functions by letting x be {f~(x)}, where for a suitable index set A the set {f,: 0c~ A} is the set of all linear functionals on B~ with IIf, II < 1. Since Ea is bounded, wcl (Ea) is bounded and is contained in a subset of re(A) that is a product of compact intervals and therefore is compact in the product topology. On B~, the product topology of re(A) is the weak topology of B~. Thus wcl(Ea) is not closed in re(A) with the product topology, since wcl(E~) is not w-compact. Let w be a member of re(A) that does not belong to wcl(E;.), but belongs to the closure of wcl (Ex) using the product topology. Then w also belongs to the closure of E~ using the product topology. But w is not in B~, since wcl (Ea) is w-closed in B~. Let

A = d(w, B~) in the norm (sup) topology for m(A), and choose 0 with 0 < 0 < A. We shall show that it is possible to choose a sequence {(x~,f~,)} inductively so that each f~, is one of the members of {f~: ~te A} and, with the ~ component of w in m(A) denoted by w~: (i) xn ~ E~,

(iii) f~,,,(Xk) > 0 if n < k,

(ii) f~°(Xk) = 0 if n > k,

(iv) w~, > 0.

Since II w II > 0 and w is in the product-closure of E;., it follows that w~ is a component of w iff - w~ is a component, that there is a w~, with w~, > 0, and there is an xl in Ex with f,,(xl) > 0. Now suppose that all (Xk,JJ have been chosen for k < p in such a way that (i)-(iv) are satisfied for k and n less than p. We shall choose % so that w,, > 0 and f~,(xk) = 0 if k < p. To do this, we note first that we can define continuous linear funetionals x~ (k < p) and W on B* by letting

106

R.C. JAMES

x[(f) =f(x~) iff~B~,

[June

W(kL) = kw~ if ~6A.

Then it follows from +

,, = sup

aix~(f~) + W(f~) : ~

1

= sup

f~

aix k

+ w~ : ~ e A

=

aix k +

W

~

A,

that for any number @ with 0 < @ < A the Helly's condition

°H Z

+ <= X

!

° w

aixt~ +

I

is satisfied for all numbers (a,}, and therefore there is an f i n B,~for which

Ilfll

1,

w(f) = , ,

xz(j) = 0 if k

<

p.

T h e n f = f ~ . for some % in A and W ( f ) = w,, = @>0 and f~.(Xk) = 0 for k < p . We now have w~. > 0 if n < p and it follows from w being in the product-closure of Ex in re(A) that there is an xp in re(A) with f~.(x~,) > 0 if n < p. Then (i)-(iv) are satisfied for k < p and n < p. Now that we have the sequence {(x,,f~.)}, let g, be defined for each n by gn(X) =f~.(Xx), where xx is the component of x in Bx. Also, for each x, choose z, in Ex for which x, is the component of z, in B~. Then g,(Zk) > 0 if n < k, and g,,(z k) = 0 if n > k. The sequence {g,} is equicontinuous, since for any e > 0 we have I g,,(x) ] < e if the component of x in Ba has norm less than e. There are other sequences of implications among (1)-(9) of Theorem 1 that can be proved easily. In particular, it would be easy to shorten the sequences used and show that (1) ~ (2) :~ (3) => (4) ~(9) =>(1). Also, Theorem 2 could have been combined with Theorem 1. This was not done because it seemed best not to interrupt the chain of implications used in Theorem 1 and because Theorem 1 is long enough as it is. The equivalence of (1) and (10) is proved in [18] for E bounded, closed and convex. Condition (12) is known [11, Theorem 6, p. 139]. Condition (14) was studied first for Banach spaces [14, Theorem 24, p. 581], but its equivalence with (1) for locally convex linear topological spaces is now well known [12, Theorem 17.12, p. 159]. Condition (16) is an interesting variation of the definition of weak sequential completeness in that limg(x,) is required to exist only for one g. Condition (17) is known for T a Banach space and K an arbitrary w-closed subset of T (see [10, Theorem 1]). THEOREM 2. Let T be a complete locally convex linear topological space and le E be a bounded w-closed subset of T. Then the following are equivalent and each is equivalent to each of(1)-(9) of Theorem 1.

1964]

WEAK COMPACTNESS AND REFLEXIVITY

107

(10) Each w-continuous functional on E is bounded. (11) Each bounded w-continuous functional on E attains its supremum on E. (12) Each continuous linear functional attains its supremum on E. (13) The closure of cir (E) is w-compact. (14) The closure of cony (E) is w-compact. (15) I f {xn) is a sequence in E and limg(xn) exists for a particular w-continuous functional g, then there is an x in E with lira g(xn) = g(x). (16) I f {x~} is a sequence in g and limg(x~) exists for a particular continuous linear functional g, then there is an x in E with limg(x~)= g(x). (17) I f K is a closed convex subset o f T and E and K are disjoint, then 0 is not a member of c l [ E - K]. Proof. If ~r is an unbounded w-continuous functional on E, then the set of inverse images of the open intervals ( - n, n) is a w-open cover of E that cannot be reduced to a finite cover. Thus (1) of Theorem 1 implies (10). The implication (10) =>(11) is trivial, since if rc is bounded and w-continuous and does not attain its supremum on E, then 1 ~*(x) = sup {~(t): t ~ E} - ~(x)

defines a w-continuous functional re* that is not bounded on E. The implication (11) :~ (12) is formal, since a continuous linear functional is w-continuous. If each continuous linear functional attains its supremum on E, then this also is true for cir (E). This follows from the fact that the supremum o f f on cir (E) is equal to the supremum of If[ on E, which follows from f ( E a , x , ) < supJf(x,) I if E ] a , ] < 1.

Thus to prove (12) * (13), we could show that cir(E) is w-compact if each continuous linear functional attains its supremum on cir(E). The proof of this is difficult and known and will not be given here (see [11, Theorem 6, p. 139]). The implications (13) * (14) * (1) follow from the fact that a closed subset of a compact set is compact. Now the proof of (10) through (14) is complete. To show that (1) ~ (15), we assume E is compact and choose an arbitrary sequence {x,,) in E and suppose that g is a w-continuous functional for which lira g(x~) exists. Let this limit be L, and for each positive integer n let U,, =

/

x:lL-g(x)]

')

> n

"

Then there is an x in E with g(x) = L, since otherwise the collection of all such sets U~ would be a w-open cover of E that cannot be reduced to a finite cover. The

108

R.C. JAMES

[June

implication (15) ~ (16) is purely formal and it is clear that (16) :~ (12). Thus (15) and (16) are proved. We shall show now that (1) =~ (17). For each continuous linear functional f and number • with sup {f(y): y e K} < ~, let W~ be the w-open set {x: f ( x ) > ~}. For any x in E, there is a continuous linear functional f with sup {J(y): y e K} < f(x). Therefore the set of all W~ is a w-open cover of E. If E is w-compact, this can be reduced to a finite cover. Choose e > 0 so that tI) - sup {f(y): y ~ K} > for each (f, ~) used in defining the finite cover and let U be a neighborhood of 0 such that for each s u c h f we have < ~ if x ~ u. Then it is impossible to have x - y ~ U with x in E and y in K, since we would then have x e W~ for some ( f , ~ ) and y) l < but also f(x) > • > f ( y ) + ~. Thus 0 is not a member of cl [E - K] and (1) ~ (17). To complete the proof of (17), we show that (17) ~ (12). This is easy, since if f is a continuous linear functional that does not attain its sup on E and this sup is m, then we can let K be {y: f ( y ) = m} and it is easy to show that 0 is a member of cl [E - K].

If(x) l

IS(x

-

2. Convex bounded closed subsets of complete locally convex linear topological spaces. Since a convex set is closed iff it is w-closed [12, Theorem 17.1, p. 154] we require that E be closed and convex rather than w-closed and convex. Condition (19) of Theorem 3 is a generalization of a criterion given by Pt~ik [19] for reflexivity of a Banach space, namely, that a Banach space is reflexive iff for each biorthogonal bounded sequence {(x~,fn)} the sequence {x I + - . . + xn} is unbounded. If (20) is modified by replacing O H,, by E O ( O Hn), then the equivalence of (1) and (20) becomes another theorem of Pt~k [18]. Clearly the modified (20) can be sandwiched between (4) and (20). Condition (22) with E the unit ball has been used as a characterization for reflexivity of a Banach space [16, Theorem 2, p. 1250]. Condition (23) is a strengthened form of (9), valid for closed convex sets. THEOREM 3. Let T be a complete locally convex linear topological space and let E be a convex bounded closed subset of T. Then the following are equivalent and each is equivalent to each of (1)-(17) of Theorems 1 and 2. (18) I f {(x~,f,)} is a biorthogonal sequence for which some subsequence of {f~} is equicontinuous, then there is at least one value of n for which xl + "" + x~ is not in E. (19) I f {(xn,f~)} is a biorthogonal sequence for which {x~} is bounded and {f,,} is equicontinuous, then there is at least one value of n for which xl + ' " + Xn is not in E. (20) I f {Hn} is a sequence of closed hyperplanes and E N H1 fi "" fi Hn is nonempty for each n, then N Hn is nonempty. (21) For each sequence {x~} in E, the member 0 of T belongs to

1964]

WEAK COMPACTNESS AND REFLEXIVITY cl

U(lin{x,,...,x,}-

ttat {x,+ l, ... })

109

.

n=l

(22) Each affine continuous map of a nonempty, closed convex subset of E into itself has a fixed point. (23) There does not exist a positive number O, a sequence {zn} in E, and an equicontinuous sequence {gn} of linear functionals such that

g,(zk) = 0 if n < k,

g,(Zk) = 0 if n > k.

Proof. Clearly (18):~ (19). Let us prove that (5)=~ (18). Suppose (18) is false and {(x,,f,)} is as described in (18) with {fp.} an equicontinuous subsequence of {f,}, but that xl + . . . + x, is in E for all n. Then (5) is false, since lim limfv.(x I + .-. + n

Xk) =

1 ¢ 0 = lim lim fp.(Xl + ... + xk).

k

k

n

N o w note that (20) is implied formally by (4) of Theorem 1, and (21) is implied by (8). Also, (22) is implied by (1). To see this, we use the fact that a continuous map o f a convex compact subset of a locally convex linear topological space into itself has a fixed point [2, Theorem 1, p. 82]. Since T is locally convex with the weak topology, to use (1) we need only know that a continuous affine map rc of a closed convex set K into itself is w-continuous. This can be shown easily, since if x is in K and f is a continuous linear functional, then the inverse image under rc o f {t: f(t) > f [Tt(x)] + e} is a closed convex subset o f K that can be separated strongly from x by a hyperplane. We shall show next that each of(19), (20), (21) and (22) implies (23), and that (23) implies (9) of Theorem 1. Suppose first that (23) is false and there is a positive number 0, a sequence {z,} in E, and an equicontinuous sequence {g,,} of linear functionals with gn(Zk)-----0 if n < k and gn(Zk)----0 if n > k. Let x 1 = z 1 and x~ = z n - z ~ _ 1 if n > 1. Then the sequence {x,,} is bounded and xl + "" + x:, equals z n and therefore belongs to E for all n. Also, g~(x~) = 0 and g,,(Xk) = 0 ff n v~ k, so the sequence {x,, g~/O} is biorthogonal. Thus (19) is false. N o w let go(x) be defined as lim g,,(x) for all x in T for which this limit exists and then extended so as to be continuous on all of T [12, Theorem 14.1 (iii), p. 118]. Let Ho be the null set of go and for each n > 0 let H~ be the set of all x in T with g,,(x) = O. Then z~ belongs to Ho tq H1 N ... A H~ for all n, but if x belongs to all H,,, then gn(x) = 0 for all n > 0 and therefore go(x) = 0 and x ~ Ho. Thus (20) is false. N o w suppose that W is a neighborhood of zero such that Ig,(x) I < 0 for all n if x ~ W. Also suppose that u - v is in W and

u=

~ aizi, 1

v=

~, bizi, n+l

~. b i = l . n+l

Then g~+l(U - v) = gn+x( - v) = - 0 and u - v ¢ W, so we conclude that (21) is

110

R.C. JAMES

[June

false. To contradict (22), we first show that if x is in cl[conv {z.}] then x = ~ o ~ . z . with each ~n nonnegative and ~ . = 1. For each x in cl[conv{z.}], we define ~. for each n to be [g,,(x) - g.+l(x)]/O. Since gl(w) = 0 if w = ~ / ~ . z . with Y,/~. = 1, and all of [gl(x) and I~. - / ~ . [ for n > 0 can be made small by a suitable choice of w with each/~,, nonnegative, it follows that each ~. is nonnegative, ~ . < 1 and Y.~a,z, is convergent, and 0 = g l ( x ) = 0- ~ o . Thus ~ . = 1 and it follows that x = ~ . z . . Now let

g~(w)]

O~nZn 1

~

~ O~nZn+1. 1

Clearly rc has no fixed points. To show that ~ is continuous on cl [conv {z.}], choose a particular sequence {~,,} with each ~. nonnegative and ~ = 1. For an arbitrary neighborhood W of zero, choose a positive number 6 and a circled neighborhood Wo of zero such that Wo + Wo c W,

a " cl [conv {z.)] = Wo if I a l < fi"

By approximating a.'s in a finite set whose sum is nearly one, we can see that there is a neighborhood U of zero such that if ~fl. = 1 and each ft. is nonnegative, then El a . - fl,,I < fi if ~ ( a . - fln)Z.~ U. Then if ~-'(an -- fl.)Z.~ U, we can write this sum as the sum of those terms with positive coefficients plus the sum of those terms with negative coefficients and obtain

E ( ~ . - / ~ . ) z . + l ~ Wo + W0 = W. We must now show that (23) =~ (9). To do this, we shall assume that E is convex and (9) is false and then show that if {z.} is a sequence in E and {g.} is an equicontinuous sequence of linear functionals with g.(zk) > 0 if n <=k and g.(zk) = 0 if n > k, then there is a sequence {u.} in E and a sequence {h.} such that h.(uk)=½0 if n < k, hn(u,) 0"if n > k, and each h. is equal to ~.gp for some p and some positive number ~. < 1. This can be done inductively as follows. Let li_m gx(zk) = 0'. If gl(Zk)= 0' for all k, let ul = zl and h i = (O/20')gl. If gl(zp)~ 0', choose a subsequence {zp~} of {zk} with Pk > P and [ 0 ' - gi(zp~)[ small enough for each k that there is a number 0" near 0' and between 0' and gl(zp) such that if z~ is chosen for each k so that =

z~ = aZp + ( 1 - a)Zp~ with 0 < a < 1 and gl(z~) = 0", then a is small enough that

gp.(z~) > to if n <= k. Now the new sequence {z~ } and the corresponding sequence {g~} of linear functionals from {g.} have all the original properties and in addition g~(z~)= O" for all k. Now let ul = z~ and hi = (O/20")g~. We can then work with the new

1964]

WEAK COMPACTNESS AND REFLEXIVITY

111

sequences {Zk1 : k > 1) and {gkl: k > 1) in exactly the same way to define u2 and h2, except that in the preceding inequality we replace 3/4 by 5/8. Continuing in this way, we get the desired sequences (u,) and {h,}. Several separation criteria are given in Theorems 4 and 5. These are closely related to (I7) of Theorem 2. A condition similar to (25) is known to be a characterization of w-compactness for closed convex subsets of a Banach space (see [10, Theorem 2]). Condition (26) is closely related to a theorem that follows from results of Tukey [21] and Klee [13, p. 881]: A Banach space is reflexive iff each pair of disjoint bounded closed convex subsets can be separated by a hyperplane. THEOREM 4. Let T be a complete locally convex linear topological space and let E be a convex bounded closed subset of T. Then the following are equivalent and each is equivalent to each of(1)-(23) of the preceding theorems. (24) I f closed convex subsets X and Y of E are disjoint, then 0 is not a member of cl [X - e]. (25) I f closed convex subsets X and Y of E are disjoint, then there is a continuous linear functional f such that sup {f(x): x ~ X } < inf{f(y): y ~ Y}. Proofi Since a closed convex set is w-closed, it follows from (1) that X is w-compact. Then (24) follows from the equivalence of (1)and (17)when E is replaced by X. We shall show that (24)=~ (23). Suppose that (23) is false and therefore for some positive number 0 there is a sequence {z.} in E and an equicontinuous sequence {g.} of linear functionals such that g.(zk) = 0 if n < k and g.(zk) = 0 if n > k. As for the set { ]~a.z.} discussed in the proof of the contradiction of (22) in the proof of Theorem 3, the following convex subsets of E are closed: X =

x

a.

~'z2.+

1 + ~'z2. n+2 Y =

, 1 an -n-T-2 Z2n--I + ~ ' ~

z2,

'

where each ~, is nonnegative and ] ~ . = 1. Then X fl Y is empty, but 0 is a member of el [X - Y]. The equivalence of (24) and (25) follows from the theorem on strong separation stated in the introduction. THEOREM 5. Let T be a complete locally convex linear topological space and let E be a convex bounded closed subset of T that contains O. Then the following is equivalent to each of (1)-(25) of the preceding theorems. (26) I f closed convex subsets X and Y of E are disjoint, then there is a continuous linear functional f and a nonzero number • such that f ( x ) < ¢p if x e X and f (y) > ¢p if y ~ Y.

112

R.C. JAMES

[June

Proof. Clearly (25)=~ (26). The proof that (26) implies (23) is similar to the part of the proof of Theorem 4 in which we showed that (24) =~ (23), only now we let X =

1 ~zn ~

z2"+t + ~

z2"

'

{

Y

1)}

where each e. is nonnegative and ½ < ~ e . < 1. Again X and Y are disjoint. Suppose there is a continuous linear functional f and a nonzero number 4 such thatf(x) < 4 if x e X a n d f ( y ) > 4 if y e Y. Then for all n we have f

(n+l n--~-~ z2._ t + ~-~--~ z2.

>4,

f

-~Z2n_l"~-~---'~Z2n ~f~.

This gives

f [ -nU 4+- z l

Z 2,, _

+ - f f -14 - 2 z , .

)

+

[

4

_ f ( _~__~2 z 2, _ l + _ ~2_ ~ z 2. ) ] > 2 4 "

and f[(z=._ a - Za.)/(n + 2)] > 4 for all n, so that 4 < 0. Similarly,

l(n

) <__4, f (n+l

andf[(z2. - z2.- O/(n + 2)] < 4 for all n, so that 4 > O. Since 4 # O, we conclude that (26) is false if (23) is false. 3. Bounded w-closed subsets of Banaeh spaces. The equivalence of condition (27) of Theorem 6 and (1) of Theorem 1 is the classic Eberlein theorem 13]. As will be clear from the proof, if we had wished only to obtain the Eberlein theorem we could easily have proved (1) ~ (2) =~ (3) ~(27) ~ (9) ~ (1). Condition (28) is known [10, Theorem 1, p. 204] and is included here largely because of its relation to (12) and to conditions for reflexivity given in Theorem 9.

THEOREM 6. Let E be a bounded w-closed subset of a Banach space. Then the following are equivalent and each is equivalent to each of (1)-(17) of Theorems 1 and 2. (27) E is ws-compact. (28) I f S is a w-closed set and E f~ S is empty, then d(E, S) > O. Proof. First we assume (3) and let {x,} be an arbitrary sequence in E. Then there is an x in E such that limf(x,) < f ( x ) < limf(x,)

19641

WEAK COMPACTNESS AND REFLEXIVITY

113

for all continuous linear functionals f. Clearly x is in cl [cony {xn}]. Let {gk} be a sequence that is total over the closure of conv{xn}, and let {~} be a subsequence of {x~} for which lim, gk(~n) exists for each k. Then limg k (~,) = gk(X) for all k. n

Also, x is a weak limit of {~}, since otherwise there would be a continuous linear functional g for which lim g(~,) does not exist or does not equal g(x). Then we could choose a subsequence {t/,,} of {4 } for which limg(r/n) exists and is not g(x), and choose y for which lim f(r/~) < f(y) < lim f(r/~) for all continuous linear functionals f. Then y is in cl [conv {~/~}]. But also, lim, gk(rln) = gk(X) for all k, lim~ gk(~/,) = gk(Y), and gk(X -- y) = 0 for all i. This is impossible, since {gk} is total over cl [conv{x,}] and x ~ y follows from the two true statements: lim g(r/n) ~ g(x), and lim g(~/,) = g(y). To show that (27)=~ (9), we let {z~} be an arbitrary sequence in E and assume (27) so that some subsequence {(,} of {z,} has a weak limit w. Then w is in cl [cony {z~+l, "" }] for all n, since otherwise there would be an n and a continuous linear functional f with sup {f(Zk): k > n + l } < f ( w ) a n d thus limf((n) ~ f(w). Therefore for {z,} there can be no positive 0 and bounded sequence {gn} of linear functionals such as described in (9), since then g~(Zk)> 0 for n < k would imply g~(w) > 0 for all n, and g~(Zk) = 0 if n > k would imply g~(w) = O. Condition (28) is an easy consequence of (27), since if lim []x~ - y~ [] = 0 with x, in E and yn in S, then a weak limit of a subsequence of {x,} must belong both to E and S. Also, (28) =~ (12). For i f f is a continuous linear functional that does not attain its sup on E and m is the sup o f f on E, then the set of all x with f(x) = m is w-closed and at zero distance from E. 4. Reflexivity of Banach spaces. Theorem 7 gives many characterizations of reflexivity for Banach spaces, since each of (1)-(28) can be used as a characterization of reflexivity if E is taken to be the unit ball. The classical theorem that a Banach space is reflexive iff its unit ball is ws-compact is part of Theorem 7. The first step toward this theorem is given in Banach's book [1, Theorem 13, p.189] in which it is shown that if B is separable and the unit ball is ws-compact, then B is reflexive. In [5], it was proved that the unit ball of B is ws-compact if B is reflexive. The theorem was completed much later by Eberlein [3]. The proof given here that (31) =~ (29) was suggested by M. M. Day. A similar argument was used by Pthk to prove theorems analogous to (19) (see [19, p.321]). A weaker form of (31) is known for which g,(zk) = 0 is replaced by g~(zk) > 0 (see [9, Theorem 1, p. 206]). Condition (31) can also be stated in the following form (see [9, Corollary 1, p. 208]): It is false that for each number 0 < 1 it is possible

114

R.C. JAMES

[June

to embed B in a space of bounded functions defined on a set A in such a way that A contains the positive integers and, for each positive integer n, there is a member z,, of B with z.=(O,O,'",O,O,O,'";{tna}), where the first n components of z n all are 0 and I t~l < a for all a in A.

THEOREM 7. For a Banach space B, the following are equivalent and each is equivalent to each of (1)-(28) of the preceding theorems with E the unit ball. (29) B is reflexive. (30) It is false that for some positive number ~ there is a bounded sequence {z.} such that

d(conv {zl, ...,z,}, cony {z,,+l, ...}) >

for all n.

(31) It is false that for each number 0 < 1 there are sequences {Zn} and {g.} with I[zn[[ =< 1, I[gn[] ~ 1 , and gn(Zk) = 0 if n < k, g,(Zk) = 0 if n > k.

Proof. With E the unit sphere of B, it is clear that (30) is equivalent to (7). Therefore it is sufficient to show that (29) =:- (30) =~ (31) =~ (29). To show that (29) ~- (30), suppose that (30) is false and that {z.} is a bounded sequence with d(conv {zl, ...,z,}, conv (z,+ 1, ...}) > a for all n. Then for any x in B, there is a p such that d(x, conv{zp+l, ...}) is positive and therefore there is an f in B* with sup {f(z,): n > p} < f(x). Let F be the member of B** described in the introductory lemma, so that limf(z,,) < F ( f ) < limf(z,) if f ~ B*. Then B is not reflexive, since if there is an x with F ( f ) = f ( x ) for all f i n B*, then limf(z.) < f ( x ) < limf(z.) if f e B*, and this contradicts the fact that there is an integer p and an f i n B* with sup {f(z.): n > p} < f(x). Now suppose that (31) is false. Choose a positive number 0 < 1 and let {z.} and {g.} be as described in (31). Then (30) is contradicted by {z.} with cr any positive number less than 0, since

To prove that (31) =~ (29), we suppose that B is not reflexive and let B c denote the canonical image of B in B**. Also, for each x in B let x c denote the canonical

19641

WEAK COMPACTNESS AND REFLEXIVITY

115

image of x in B**. Let 0 satisfy 0 < 0 < 1 and F be a member of B** for which IIF II < i and d(F, B~) > 0. The proof will be complete if we show that it is possible to choose the sequence {(zn, g,)} inductively so that (a) I1Zn]1 < 1 and I1g, II ~ 1, (b) F(g,) = 0 for all n, (c) g~(Zk)= 0 if n > k, (d) g,(zk) = 0 if n < k. The first step is to note that since IIF It > 0, there exists g~ with IIg' [l z 1 and F(gl) = 0. Then IIel II > 0 and there exists z 1 with [[ zl II z i and gl(zl) = 0. Now suppose that (Zk,gk) has been chosen for k < p so that (a)-(d) are satisfied for n and k less than p. Then we choose gp so that IIg, IIz 1, F(g~)=O, and Z~k(gp)=gp(Zk)=O for k < p. This is possible, since the following Helly's condition is satisfied:

°1"-1

I

0 < d(F, Bc) ~ aix7 + F for all numbers {ai}, 1

where O/d(F,B c) < 1. Now we must choose Zp so that if n < p. To show this is possible, we use the fact that condition:

Izp II 1 and gn(Zp)

=

0

F t1< 1 and the Hetly's

[ ~ aiO ] = ] ~ a,F(g,) = F ( ~ a~g,) t < I{F [{ ~a~g,]]. The following theorem gives several criteria for reflexivity that are closely related and might be called "flatness criteria" for the unit ball. These are closely related to conditions (7), (8), (21) and (30). Condition (32) has long been known. It is the same as Lemma 1 of [8]. It is closely related to a necessary condition for reflexivity given by Milman and Milman [16, Corollary, p. 1252] which can be stated in the following form: If B is non-

reflexive, then for any a < 1 and any n there is a sequence {zl, ..., zn} such that a < II u II < 1 if u ~ conv {Zk} and, for all k < n, tr < d (conv

{z 1,..., Zk}, cony {zk+l,..., z,}) < 1.

To change the Milman-Milman condition and obtain the necessary and sufficient condition (32), one can replace the finite sequence {zl, ...,z,} by an infinite sequence and replace the 1 in the last inequality by 2 (which is equivalent to discarding it altogether). Condition (35) is almost equivalent to the theorem of Pdczyfiski that a Banach space is nonreflexive iff some nonreflexive subspace has a basis [17, Theorem 1, p. 372], since the inequality being satisfied for some positive number ½a is a necessary and sufficient condition for {z,} to be a basis for its closed linear span (see [1, p . l l l ] , and [7]).

116

R.C. JAMES

[June

Condition (35) also is related closely to Corollary 2 of [23], since a sequence is a "basic sequence of type 1+" iff it satisfies the conditions in (35) with I[ u II = 1 replaced by IIu II = M for some positive number M. THEOREM 8. For a Banach space, the following are equivalent and each is equivalent to each of(I)-(31) of the preceding theorems with E the unit ball. (32) It is false that for each number tr < 1 there is a sequence {z,} such that < Ilull-<- 1 ifueconv{z.} and, for all n, d(conv {zD ..., z,}, conv {z.+ 1, ,..}) > tr. (33) It is false that for each number a < 1 there is a sequence {z.} such that

< II u I! ---- 1 if u e conv {z.} and, for all n,

~,...})

d(lin {zl, ..., z,}, flat {z,+

> a.

(34) It is false that for each number a < 1 there is a sequence {z.} such that a < Hu l[ < 1 if u e conv {z.} and, for all n, d(flat {zl, "", z,,}, lin {z.+ 1, "", }) > ½tr. (35) It is false that for each number < 1 there is a sequence {z,,} such that 1 i f u e c o n v { z . ) a n d , forall n < p and all numbers {a,}. n÷p ½ff ~ aizi ! • 1 t

< Ilull

Proof. Clearly (30) implies (32), (33), (34) and (35). Also, (32) =~ (33). We shall complete the proof by showing that each of (33) and (34) implies (31) and that (35) implies (29). Suppose first that (31) is false and for 0 < 1 let {z,} and {g,} be as described in (31). We contradict (33) by using the first of the equalities g " + l ( ~ a ' z ' - .+1 ~" b~z') = - 0 "

!

n+!

.+, ]~

1

n+l

with ~.+x b~ = 1 and 0 > a. Then (34) is contradicted by letting ~a~ = 1 and noting that it is impossible to have both 01 ~.+1 b, I and 011 - ~.÷1 b, I less than aif0>a. To prove that (35) * (29), we suppose B is not reflexive and denote by B c the canonical image of B in B**. For A between 0 and 1, let F be a member of B** for which IlFll < 1 and d(F,B ~) > A. The proof will consist of showing inductively that there is a linear functional • with domain B and sequences {z,} and {H,} such that II• I[ = 1, F(q~) = A, and: (i) II z. [l -<- 1 and , ( z . ) = A for all n.

1964]

WEAK COMPACTNESS AND REFLEXIVITY

117

(ii) {H.} is an increasing sequence of finite sets of linear functionals with domains B and norms less than 2/A, (iii) F(h) = h(zp) = 0 if h ~ H. and n < p, (iv) If zelin{zx,...,z.}, there is an h in H. with [ h(z)[ _>_All ztl. First choose • so that I1~ 1[ = 1 and V(q3) = A. Now suppose that {z a, ...,zp} and {Hx, ..., Hp} have been chosen to satisfy (i)-(iv) when n < p, where p may be zero. Then z,+l must be chosen so that ][ z.+l 1[ < 1, ~ ( z p + l ) = A, and h(z.+ 0 = 0 if h ~ H . (if p = 0, then H p is to be the empty set). This is possible, since II F l[ < 1 and the Helly's condition A < F 11[1h + ¢ [I follows from

II

A<

Al[Fl[llh+-~ll-[F(h+~)l--

[Ivlll[h÷~l[

if

h~H e.

Now let Gp be a finite set of linear functionals with unit norms and domains lin{zl,...,zp} which contains suitable linear functionals that for each z in lin {zl, "-', zp} there is a g in G~ with I g(z) I ~ A I!z II, xf g ~ ae and z: is the canonical image of z~ in B**, then for all numbers {a~} we have

aiz~(g ) ] = f~ aig(zi) ] = g ( ~. a,z,) < 1

1

a,z,[I =

[1 ~

1

~e aiz~ [

1

1 P

<

F+

Y~ aizi

+

F .

1 P

c

Since d(F,B c) > A and Ilfll < ~, we have AIIF]I < IIF + :Cla,z, ll and therefore

l fZa'zT'g)l < ( ' +~

F ÷ ~ aiz7

This is a Helly's condition that gives the existence of an h in B* with 1[h 1[ < 2/A, = 0, and z~(h) = z~(g), or h(z~) = g(zi), for 1 < i _ p. Then h is an extension of g to B. Let each member of Ge be extended in this way and then let H e be the union of H e_ 1 and all such extensions of members of Ge. Now that we have sequences {z.} and {H.} that satisfy (i)-(iv), it follows from (i) that ~(u) = A and IIu II > A if u ~conv {z.}, and it follows from (iv) that for any sum ~ aiz i there is an h in H. such that

F(h)

Using 11h II < 2/A and (iii), we then have

~e

A

~x aizi)

A h ~ aizi

=---2

1

This contradicts (35), since for any a < 1 we can choose A so that tr < A2. All of the conditions in Theorem 9 are known; for (36) and (37) see [10, Theorems 3 and 4]; (38) is a consequence of results of Klee [13, p. 881] and Tukey [21].

118

R.J. JAMES

[June

Condition (36) is closely related to (17), (24) and (28). Conditions (37) and (38) are closely related to (25) and (26). TrmOREM 9. For a Banach space, the following are equivalent and each is equivalent to each of (1)-(35) o f the preceding theorems with E the unit ball. (36) I f w-closed subsets X and Y are disjoint and one set is bounded, then

d(X, Y) > O. (37) I f closed convex subsets X and Y are disjoint and one set is bounded, then there is a continuous linear functional f such that sup {f(x): x e X }

< inf{f(y): y ~ Y}.

(38) I f closed bounded convex subsets X and Y are disjoint, then there is a continuous linear functional f and a nonzero n u m b e r • such that f ( x ) < ¢P if x e X and f (y) >=• if y e Y. Proof. Assuming (1) is true with E the unit ball, the bounded set in (36) is w-compact and it then follows from (28) that d ( X , Y) > 0. I f X and Y also are convex and d ( X , Y ) > e, then it follows from the theorem on strong separation stated in the introduction that (36) => (37). Clearly (37) :~ (38) and (38) is equivalent to (26) if E is the unit ball.

REFERENCES 1. S. Banach, Th~orie des opdrations lindaires, Warsaw, 1932. 2. M. M. Day, Normed linear spaces, Academic Press, New York, 1962. 3. W. F. Eberlein, Weak compactness in Banach spaces, Proc. Nat. Acad. Sci. U.S.A. 33 (1947), 51-53. 4. M. Eidelheit, Zur Theorie der konvexen Mengen in linearten normierten Riiumen, Studia Math. 6 (1963), 104-111. 5. V. Gantmaher and V. Smu|'yan, Sur les espaces lindaires dent la sphere unitaire est faiblement compacte, Dokl. Akad. Nauk SSSR 17 (1937), 91-94. 6. A. Grothendieck, Crit~res de compacticitd clans les espaces fonctionnels gdndraux, Amer. J. Math. 74 (1952), 168-186. 7. M. M. Grunblum, Certain thdor~mes sur la base dans un espace de type (B) , Dokl. Akad. Nauk SSSR, 31 (1941), 428-432. 8. R. C. James, Reflexivity and the supremum of linearfunctionals, Ann. of Math. 66 (1957), 159-169. 9. R. C. James, Characterizations of reflexivity, Studia Math. 23 (1964), 205-216. 10. R. C. James, Weak compactness and separation, Canad. J. Math. 16 (1964), 204-206. 11. R. C. James, Weakly compact sets, Trans. Amer. Math. Soc. 113 (1964), 129-140. 12. J. L. Kelley and I. Namioka, Linear topologicalspaces, Van Nostrand, Princeton, 1963. 13. V. L. Klee, Jr., Convex sets in linear spaces, Duke Math. J. 18 (1951), 875-883. 14. M. Krein and V. Smul'yan, On regularly convex sets in the space conjugate to a Banach space, Ann. of Math. 41 (1940), 556-583. 15, D. Milman, On some criteria for the regularity of spaces of the type (B), Dokl. Akad, Nauk SSSR 20 (1938), 243-246.

1964]

WEAK COMPACTNESS AND REFLEXIVITY

119

16. D. P. Milman and V. D. Milman, Some geometric properties of nonreflexive spaces, Soviet Math. 4 (1963), 1250-1252. 17. A. Pe|czyfiski, A note on the paper of I. Singer "Basic sequences and reflexivity of Banc~ch spaces," Studia Math. 21 (1962), 371-374. 18. V. Pt~k, Two remarks on weak compactness, Czechoslovak Math. J. 5 (1955), 532-545. 19. V. Ptfik, Biorthogonal systems and reflexivity of Banach spaces, Czechoslovak Math. J. 9 (1959), 319-326. 20. V. Smuryan, On the prineiple of inclusion in the space of type (B), Mat. Sb. 5 (1939), 317-328. 21. J. W. Tukey, Some notes on the separation of convex sets, Portugal. Math. 3 (1942), 95-102. v 22. K. Pelczyfiski, d proof of Eberlein-Smulian theorem by an application of basic sequences, Bull. Acad. Polon. Sci. S6r. Sci. Math. Astronom. Phys. 12 (1964), 539-544. 23. I. Singer, Basic sequences and reflexivity of Banach spaces, Studia Math. 21 0962), 351-369. HARVEY MUDD COLLEOB,

CLAREMONT, CALIFORNIA

ON CERTAIN HOMOMORPHISMS OF QUOTIENTS OF GROUP ALGEBRAS BY K A R E L DE L E E U W A N D Y I T Z H A K K A T Z N E L S O N ABSTRACT I.~t ,4 be t h e algebra o f functions on the circle group T = {z : I z I = 1 } having

absolutely convergent Fourier series. For a subset E of A, the algebra of restrictions to E of functions in A is denoted by A(E). It is shown that for sets that are "thick" in one of several senses, algebra homomorphisms of the A(E) having norm I must arise from point mappings having a certain amount of rigidity. Introduction. Let T be the circle group {z: I zl = I} and A the algebra of those functions on T having absolutely convergent Fourier series. A theorem of Beurling and Helson (see [1]) states that the only algebra automorphisms of A arise from a rigid motion of the circle T, that is, a rotation of T, or a reflection of T followed by a rotation. If E is a closed subset of T, we denote by A(E) the algebra of restrictions to E of the functions in A. Inspired by the result of Beurling and Helson one may inquire whether an algebra isomorphism of A(E1) and A(E2) must arise from a point mapping of E1 and E z having a certain amount of rigidity. If E~ and E 2 are intervals, this is indeed the case, as can be established by a modification of the argument of [1]. However, this technique yields no information for more general sets. As a step in the direction of identifying algebra homomorphisms in the case of arbitrary closed subsets of T, we here investigate isomorphisms of norm 1. Although the results are not complete, we are able to show for a large class of closed sets, which are "thick" in one of several senses, that such an isomorphism must be induced by an affine point mapping. A specialization of one of our results is the fact that if E~ and E2 are Cantor type sets with constant ratio of dissection, A(EI) and A(Ez) cannot be isometrically isomorphic unless the ratios are the same. It seems likely that this continues to hold for algebra isomorphisms that are not necessarily isometric, but our methods shed no light on this problem. 1. Notations and statement of results. We denote by T the circle group and by Z the group of integers. A is the Banach algebra of all continuous functions on T having an absolutely convergent Fourier series, the norm being defined by

Received January I9, 1964. 120

1964]

HOMOMORPHISMS OF QUOTIENTS OF GROUP ALGEBRAS

II EaJn'll ,t =

(1.1)

•la.}

121

•

The dual space of A is known to be the space of all pseudomeasures on T, i.e. distributions on T having bounded Fourier coefficients. For f e A and S e A* we put

if

f(n) = ~

f(t)e-'ntdt, S(n) = < e -~nt, S >,

and since

f(t) = ~,f(n)e 'n' we have oo

(1.2)

< f , S > = ~, f ( - n)~(n), --00

and

(1.3)

I l s h . = supl n

(1.1) and (1.3) permit us to identify A and A* with 11 and l °°respectively. Let E c T be closed. We denote by I(E) the ideal of all the functions in A that vanish on E, by N(E) the space of all pseudo-measures orthogonal to I(E) and by A(E) the quotient algebra Aft(E). A(E) can be realized as the algebra of continuous functions on E which are restrictions to E of functions in A. Since I(E) is closed, A(E) is canonically a Banach algebra, its dual being N(E). Suppose that E and F are closed subsets of T and that

H : A(F) --, A(E) is an algebraic homomorphism of A(F) into A(E). The sets E and F can be canonically identified with the maximal ideal spaces of A(E) and A(F) respectively, so by a familiar argument (see 12] p. 76) there is a continuous ~b from E to F such that, for f e A(F), (1.4)

H(f) = f o q~.

DEFINITION. : ~b is affine on E if there exists an integer n and a complex number c of modulus 1 such that ~b(e") = ce ~n', e ~' ~ E.

122

K. DE LEEUW AND Y. KATZNELSON

[June

will be called generalized aJ~ne on E if there exists a multiplicative mapping X : T ~ T and a complex number c of modulus 1 such that ¢(e u) = cx(eU), eu e E. We assume throughout this paper I[ H [] = 1 and prove the following results: THEOREM 1.1 : ¢ is always generalized affine. THEOREM 1.2 : I f E is a basis ¢ is aJfine. By the definition of the norm in A(E) for every f e A(E) and e > 0 there exists g e A, g =-f on E such that

IIg IIA< IIfll ( , + We shall say that E has the extension property if for every f e A(E) there exists g ¢ A, g - - f on E and

IIg flA = II:ll E has the restricted extension property if norm preserving extension is required only f o r f e A ( E ) o f norm 1 and modulus 1. THEOREM 1.3. I f E has the restricted extension property, ¢ is affine. A pseudo-function is an element of A* with Fourier coefficients tending to zero at infinity. DEFINITION: E is an M* set if N(E) contains non-trivial pseudo-functions. E is a UM* set (uniformly M*) if E n J is either empty or M* set for every open interval J. THEOREM 1.4. I f E is UM* it has the extension property. COROLLARY. I f E is

UM*, ¢ is affine.

THEOREM 1.5. Suppose that for some ~ > 0 there exists a positive measure tt of total mass 1 with arbitrarily small support contained in E such that I--.

xl

lim sup l l~(n) I < 1 - ~. Inl--, oo

Then E has the restricted extension property COROLLARY. Under the condition of Theorem 1.5, ¢ is affine. Note that the condition of Theorem 1.5 is of a different nature than that of Theorem 1.4. A UM* set can not be too thin at any of its points while the condition of Theorem 1.5 just implies thickness somewhere.

1964]

HOMOMORPHISMS OF QUOTIENTS OF GROUP ALGEBRAS

123

2. Norm-preserving extensions and affine mappings. The proofs of Theorems 1.1 and 1.3 depend essentially on the following well known Lemma:

LEMMA 2.1. Let G be a locally compact abelian group, ~ a continuous, positive positive-definite function on G, ~b(1) = 1. Then (2.1)

G, = {~; ~ G , I ~(~)1 -- a}

is a closed subgroup of G and on it @ is multiplicative. Proof. ~ = p where • denotes a positive measure on G. Now [ ~b(cr)[ = 1 if and only if a, considered as character on ~, is constant (hence = ~(a)) on the support of #. Let us return now to the situation of §l. We have ~b: E - ~ F s u c h that for f e A(F), f o dpe A(E) and

(2.2)

IlSo ~ II A,~,_-< llsll,,,r,.

S(e")= e" we obtain So I'¢'1 = ~, II '¢' II ~','~, = 1.

Taking

,~ = ,¢,, hence ,~ ~ A ( ~ and

I1'¢' II--< 1;

and since

PROPOSITION 2.2. Suppose that (a has a norm preserving extension. Then dp must be affine. Proof. By rotating E and F we may assume that ¢(1) = 1. Let ~k be a norm preserving extension of ¢, that is

¢(e") = Z(k(n)e"' satisfying (2.3)

{

~O(e~') = ¢(e i') for etteE ~l~(n)l

= 1.

Since ~b(1) = ¢(1) = 1, that is (2.4)

] ~ ( n ) = ]~1 ~(n)[,

~(n) > 0 for all n and ~b is positive definite. T~, defined by (2.1), is a closed subgroup of T, containing E, on which ~b is multiplicative; hence, for some n, ~(flt) = ei,, on T~ and the theorem is proved. As an immediate corollary to Proposition 2.2 we obtain Theorem 1.3. 3. Generalized norm preserving extensions. Let E and F be finite sets containing N linearly independent points each. Let ¢ be any mapping of E onto F. Then by Kronecker's theorem, f - - , f o ~b is an isometry of A(F)onto A(E). Clearly ¢ need not be affine and therefore has no norm preserving extension in A. In this case

124

K. DE LEEUW A N D Y. KATZNELSON

[June

it is clear, however, that ~b is generalized affine. And we prove next that such is the case in general. We shall denote by m the second dual of A (that is, the dual of yo). For a e m define

#(e") = < {e~t},a >. An element a e m is called an extension ofa f u n c t i o n f defined on some subset E of T, if

#(e l') = f ( e t') for et' e E. LEMMA 3.1. Let f e A ( E ) . Then there exists in m an extension a of f such that

[ITIIA ) --

II

II.

Proof. f defines canonically a linear functional of norm IIflIA, , on the subspace N(E) of l °°. By the Hahn-Banach theorem this functional has a norm preserving extension a e m . Now if e ~' e E, {e~n'} e N(E), and

f ( e i') = < {e'nt},f> = < {e i~t }, a> = O(e"). We turn now to the proof of Theorem 1.1. As in the proof of Proposition 2.2 we can assume ¢(1) = 1. Let tre m be a norm preserving extension of ¢, that is II II = 1, and 0 ( e " ) = ~b(e~') on E. We claim that 0(e") is positive definite on TD, To being the circle group with the discrete topology. In order to see this we can restrict tr to the closed subspace of l°° generated by the exponentials {(eint}, eUe T}, i.e., the uniformly almost periodic sequences; as such, a is a measure of mass 1 on B, the Bohr compactification of Z (and the dual of To). Since #(1) = 1, the measure corresponding to tr is positive and 0(e ~t) is positive definite. By Lemma 2.1 a(e ~t) is multiplicative on some subgroup G of T containing E; it is easy to see ([3] Th. 37) that O(e")16 can be extended to be multiplicative on T, and ¢ is generalized affine as claimed. Theorem 1.2 is an immediate consequence of Theorem 1.I and of the following: LEMMA 3.2. Let E be closed in T and a basis, Z a character of T such that Z I n is continuous. Then X is continuous. Proof. Put E , = (e~t: t = ~'~ t j, eit~ ~ E}. Since E is a basis T = U mEre, and since Em is closed for all m, we obtain, using the theorem of Baire, T =Em for m > m0. In order to show that Z is continuous we have to show that, given e > 0, there exists some interval I on T such that the variation of Z on I is smaller than 8. Put et = e/mo and E = U kj=l E~ E j being portions of E on which the variation of X is smaller than el. Clearly, for an appropriate choice of jl, "",Jmo, E' = {e~t : t = ] ~ ° t v, e it~ E E j~} contains an interval I and the variation of X on E' is smaller than mos~ = e.

1964]

HOMOMORPHISMS OF QUOTIENTS OF GROUP ALGEBRAS

125

4. Sufficient conditions for the existence of norm-preserving extensions. Let E be closed in T. For 0 < e < 1 we denote by N~(E) the following set: (4.1)

N,(E)={S:SeN(E),IiSIi=I,limsupI~(n)I
PROPOSmON 4.1. Let f s A(E), 0 <e< 1. Suppose that

Ilfh<~,: supl

(4.2)

< f , s > I, S~N,(E)

Then f has a norm preserving extension in A. Proof. Let a ~ m = (l°°) * be a generalized norm preserving extension of f (cf. Lemma 3.1). Because of the canonical identification of l °° with the space of all continuous functions on the ~ech compactification fl(Z) of Z, a can be identified with a measure# on/7(Z) and II~ll = Sl d.l ~ has a decomposition/x=lx i + ~2, with #1 concentrated on Z and ix2 vanishing on every finite subset of Z, such that

fl~,l= f i~,,l+ f i~,:l.

(4.3)

Denote by trj the elements in m corresponding to #s, so a = 41 + 42 and

I1~ II = II~, II + II~2 II

(4.4) Now for every {h(n)} e l Go

(4.5)

I<

{h(n)}, 42 >

I ~ II~ II

lim sup I h(n) 1. h:l-->Go

SO that if S ~ N,(E) we have



= <S,a>

= < S, at > + < S, tr2 >

and (4.6)

<s, s > I --< I! ~, II + (1 - ~)II ~ II = Ilfll

~<~, - ~

II ~: II

which is compatible with (4.2) only if II ~2 II = 0 This means p = p, and hence a e 11. We have shown therefore, not only that a norm preserving extension in A exists, but that every norm preserving extension is necessarily in A.

Proof of Theorem 1.5. Let f ~ A ( E ) , llfll = 1, [f(eit)l = 1. Since f is continuous on E it is clear that if/~ is a positive measure which has a very small support contained in E, and f d# = 1, [ j" will be very close to 1 --][fl[" This remark and the assumptions of Theorem 1.5 imply (4.2), and the result follows from Proposition 4.1. We conclude with the proof of Theorem 1.4. This can be done via Proposition 4.1 but it is almost as easy to give a direct proof, and that is what we do.

fd#[

126

K. DE LEEUW AND Y. KATZNELSON

P r o o f of Theorem 1.4. We denote, as is usual, by co the subspace of l °° of those sequences that converge to zero. Canonically c* = 11. Put L ( E ) = N(E)c~ Co. If f e A ( E ) , f defines a linear functional of norm }ifll' on L(E), where clearly Ilfll'_<_ IIflIA, ," By the Hahn-Banach theorem this functional can be extended to a functional of the same norm on Co; there exists, therefore, an element h ~ l x, I[ h II = [!fll ', such that for every S ~ L(E),

< f , S > = < S,h > = ~,~q( - n)h(n). We contend that if E is UM* we have f ( e " ) = h(eU)( = ~h(n)e tnt) for eitEE. That is,/~(e tt) is the extension we seek. Assume f ~ h on E. For some e "° e E, f ( e it°) -/~(e t~°) # 0, and by continuity there exists an interval J containing e ~to such that f - h is bounded away from zero on J n E. Let S # 0 be a pseudo-function carried by J n E. Let g ~ A such that g(e t') = [ f ( e ~t) -h(e~')] - t for eit~ J n E, and n be an arbitrary integer, ge ~t S ~ L(E), so < f - h, ge~ntS > = O. But < f - It, g e ~ t S > = < eint, S > = ,~( - n),

and consequently S(n) - 0 and S = O, which gives the desired contradiction. BIBLIOGRAPHY 1. A Beurling and H. Helson, Fourier-Stieltjes transforms with bounded powers, Math. Scand. 1 (1953), 120-126.

2. L. Loomis, Introduction to abstract harmonic analysis, Van Nostrand, 1953. 3. L. Pontrjagin, Topologicalgroups, Princeton, 1946. STANFORD UNIVERSITY YALE UNIVERSITY

CONNECTEDNESS IN TOPOLOGICAL LINEAR SPACES* BY

VICTOR KLEE ABSTRACT

The following properties, well known for normed linear spaces of dimension >_ 2, are established for an arbitrary topological linear space of dimension 2 : (a) every neighborhood of 0 contains one whose complement is connected; (b) the complement of a bounded set has exactly one unbounded component. By a topological linear space we mean a real linear space with an admissible topology; that is, one with respect to which both vector addition and scalar multiplication are jointly continuous. The T~ separation axiom is assumed throughout. For each normed linear space of dimension > 2, it is obvious that (a) every neighborhood of 0 contains one whose complement is connected; (b) the complement of a bounded set has exactly one unbounded component. These properties play an important role in the study of mappings in normed linear spaces, and in line with efforts to extend the theory Andrzej Granas has asked whether (a) and (b) are valid in an arbitrary topological linear space. We show here that they are. There is an attempt to proceed under minimal hypotheses, so that the results will apply also to certain topologized linear spaces in which the algebraic operations are not jointly continuous. Henceforth, E will denote a linear space of dimension > 2 over the real number field 9t, and z will denote a topology for E. Any assumption about z's relationship to the algebraic structure of E will be stated explicitly. As is well known [5], each finite-dimensional linear space has a unique admissible topology. This will be called its natural topology, and the notion is extended by translation to all finite-dimensional affine subspaces of a linear space. In treating (a), we make the following assumptions about the topology ~: (1) There is a neighborhood N of 0 such that N + N ~ E. (2) Every neighborhood of 0 contains a symmetric starshaped neighborhood of 0. (3) In every (two-dimensional) plane P through 0, the relative topology induced by z is identical with the natural topology of P. By an n-gon we mean an arc composed of n or fewer line segments. Received September 9, 1964. * Research supported by the National Science Foundation, U.S.A. (NSF-GP-378). 127

128

V. KLEE

[June

THrOREM A. Suppose that (E, z) is a topologized linear space of dimension > 2 in which the conditions (1), (2), and (3) are satisfied. Then every neighborhood U of 0 contains a neighborhood W of 0 such that E ~ W is connected. Indeed, W can be chosen so that each pair of points of E ~ W is joined by an 8-gon in E ~ W. Proof. Let N be as in (1) and choose p ~ E ~ (N+ N). Choose a plane (2 which contains the line ~ p , and let J be a 2-gon which joins p to - p in Q. By (2), there is a neighborhood V of 0 in E such that V n J = ¢, and by (3) there is a symmetric starshaped neighborhood W of 0 such that Wc N n U n V. We will show that each point x of E ~ (WU ~Rp) can be joined to p or to - p by a 3-gon in E ~ W, and from this the desired conclusion follows. Let P be the plal-e which contains the lines ~ p and ~ x , whence W n P is a symmetric starshaped subset of P. If the closure cl(W n P) of W n P in P does not contain any line through 0, then W n P is bounded with respect to the natural topology of P; in this case, x can be joined both to p and to - p by 3-gons in P ~ W. Suppose, on the other hand, that the set cl(W n P) does contain a line L through 0. Then there is exactly one such line, for the existence of two would imply that ( W n P ) + ( W n P ) = P , whereas W c N and p e P ~ ( N + N ) . Now assume that the points x and p lie on the same side of L in P, and let Z denote the part of P which is bounded by the rays [0, oo [x and [0, ~ [ p and which intersects L only at 0. Then W n Z is bounded and starshaped, so x can be joined to p by a 3-gon in Z ~ W. Similarly, x can be joined to - p by a 3-gon in P ~ W if x and p lie on opposite sides of L. This completes the proof. (When E is locally convex, the neighborhood W may be chosen so as to be convex, whence the 8-gons of Theorem A are replaced by 2-gons if W is closed and 3-gons if W is open. These numbers cannot be reduced. When E is locally bounded, W may be chosen so as to be bounded and starshaped, whence the 8-gons are replaced by 3-gons if W is closed and 4-gons if W is open. Can these numbers be reduced? Can the number 8 in Theorem A be reduced for general topological linear spaces?) In treating (b), we consider a family g of subsets of E, subject to the following restrictions: (4)

IfXcYand

Y e ~ , then X ~ g .

(5)

If Ye ~ , then U y ~ r[0,y] ~ ~ .

(6) If Ye N , and P is a plane through 0, then with respect to the natural topology of P there is exactly one unbounded component of P ~ Y. TI-mORnN B. Suppose that (E,z) is a topologized linear space of dimension > 2, ~ is a family of subsets of E, and conditions (3), (4), (5) and (6) are satisfied. Then for each member Y of ~ , exactly one component of E ~ Y fails to be a member of ~ .

1964]

CONNECTEDNESS IN TOPOLOGICAL LINEAR SPACES

129

Proof. Let J = U v E r [ 0 , y ] , whence J e ~ by (5). We claim that for each plane P through 0, the set P ,-~ J is connected and nonempty. Indeed, P,~ J is a union of rays collinear with 0, where each of the rays is unbounded and connected with respect to the natural topology of P and hence lies in an unbounded component of P ~ J . By (6), there is exactly one such component, so P ~ J is connected. Since this is true for every plane P through 0 and since any two points of E ,-, J lie together in some such plane, it follows that E ,-~J is connected. Now let U be the component of E ~ Y which contains E ~ J , and consider any other component C of E ,~ Y. Then o f course C does not intersect U, whence C c j and (by (4)) C e ~ . It remains only to show that U is not a member of ~ . Let K = U u Ev[O,u] and suppose that U e ~ , whence K e ~ by (5). From the definitions of J and K it follows that every ray issuing from 0 is contained in J or in K or in both, and hence one of the sets must contain two such rays Rx and R2. Since R1U R2 e ~ by (4), it follows from (6) that if P is a plane containing R t U R 2 , then P ~ (R 1 U R2) has exactly one unbounded component in the natural topology of P . But this is obviously impossible, and the contradiction completes the proof. COROLLARY. Suppose that (E,z)and ~ are as in Theorem B, that the space (E, z) is locally connected, and that each member of ~ is nowhere dense in E. Then E ~ Y is connected whenever cl Y~ ~ . Proof.

Since Y is nowhere dense, we have E ~ cl Y c E ~ Y c cl(E ~ e l Y ) .

Thus it suffices to show that the set E ~ cl Y is connected. Suppose the contrary, whence from Theorem B it follows that some component T of E ~ Y is a member of ~ . Since E is locally connected and E ~ cl Y is open, the set T is open and this contradicts the fact that the members of ~ are nowhere dense. Theorems A and B apply to many topologies for linear spaces, and to many choices for the family ~ . Some of these are quite "pathological." Note, however, that if dim E > d > 2 and if z is the finest topology for E which agrees with the natural topology on every d-dimensional affine subspace of E , then conditions (1) and (3) are satisfied but (2) is not. (See [4] for discussion of a similar topology.) We do not know whether the conclusion of Theorem A is valid in this case. In addition to the admissible topologies for a linear space, we consider also thefinite topology, which is defined as the finest topology agreeing with the natural topology on every finite-dimensional affine subspace. (It appeared under a different name in 11]. The present term was used in [2] and [3].) It is not admissible when d i m e > No, for then the vector addition is not jointly continuous [3]. Among the many ways in which the members Y of the family & may be selected we mention the following:

130

V. KLEE

[June

(7)

For each neighborhood U of 0, there exists p e ~R such that #U D Y.

(8)

The set Y is contained in a linearly bounded convex set.

(9) The intersection of Y with any finite-dimensional affine subspace is bounded in the natural topology. (10)

The closure of Y is compact.

TrmogrM C. Suppose that (E,T) is a topologized linear space of dimension > 2, where z is an admissible topology or thefinite topology. For i = 7, 8, 9, 10, let ~ denote the family of all subsets Y of E which satisfy the condition (i). Then Theorem A applies to the space (E,z) and Theorem B applies to the system

Proof. It is obvious that conditions (1), (3), (4) and (6) are satisfied in each case. For condition (2), consider an arbitrary neighborhood U of 0. By the joint continuity of scalar multiplication (established for the finite topology in [2]), there exist e > 0 and a neighborhood V of 0 in E such that ] - e , e [ V c U. But the set ] - e , e[ V is a symmetric starshaped neighborhood of 0. If ~ is defined by (8) or (9), the fact that (5) holds is immediate from the relevant definitions. If & is defined by (7) or (10), it is well known that (5) holds when z is an admissible topology. Thus to complete the proof, it suffices to establish (5) when ~ is defined by (7) or (10) and • is the finite topology. For this, in turn, it evidently suffices to prove the following: (*) If Y satisfies condition (7) for the finite topology, then Y is contained in a finite-dimensional linear subspace of E. In order to prove (*), let us suppose that Y contains an infinite linearly independent set X. Let H be a Hamel basis for E such that X c H , let xl,x2,"" be an infinite sequence of distinct members of X , and let el, e2, "" be a sequence of positive numbers converging to zero. Finally, let U denote the convex hull of the set

(n~

...}) u

...}.

Then U is a neighborhood of 0 for the finite topology, and yet Y is not contained in any multiple of U. The contradiction completes the proof of (*) and hence of Theorem C. Since (7) is the usual notion of boundedness in topological linear spaces, our results supply an affirmative answer to the question of Granas. From the Corollary it follows that if Y is a subset of a topological linear space E, then E ,,~ Y is connected if any of the following statements is true: E is infinite dimensional and cl Yis compact; E is not locally bounded and Yis bounded; E does not admit a separating family of continuous linear forms and cl Y lies in a linearly bounded convex set.

1964]

CONNECTEDNESS IN TOPOLOGICAL LINEAR SPACES

131

REFERENCES 1..1. Dugundji, Note on CWpolytopes, Portugal Math. 11 (1952), 7-10. 2. E. Hille and R. Phillips, Functional analysis and semigroups, Amer. Math. Soc. Colloq. Publ., vol. 31 (1957). 3. S. Kakutani and V. Klee, The finite topology of a linear space, Archly Math. 14 (1963), 55-58. 4. V. Klee, Some finite-dimensional affine topological spaces, Portugal Math. 14 (1955), 27-30. 5. A. Tychonoff, Ein Fixpunktsatz, Math. Ann. 111 (1935), 767-776. UNIVERSITY OF WASHINGTON SEATTLE, WASHINGTON.

SOME PROBLEMS ON BASES IN B A N A C H A N D FRECHET SPACES* BY

!

A. PELCZYNSKI ABSTRACT

This paper is a revised version of the author's report during the Symposium "On Series and Geometry in Linear Spaces" held at The Hebrew University of Jerusalem, March 16-24, 1964. Some problems of the existence (for a given Frechet space) of closed linear subspaces and quotient spaces with bases are discussed. In this report we present some results of the forthcoming papers of M. I. Kadec and the author [17] and I. Singer and the author [21] and discuss some open questions concerning bases in Banach and Frechet space. 1. Subspaces and over-spaces with bases. Let X be a separable infinite-dimensional Frdchet space. Then there exist infinite-dimensional Frdchet spaces X o and X1 with bases and embedding isomorphisms io and ix such that the diagram il io X x ~ X -~ Xo

(1)

holds. We can put X0 = C for X being a Banach space and Xo = (C x C x ...)s for arbitrary separable Frdchet space(I): The existence of XI (for Banach spaces) is mentioned in the monograph of Banach [2, p. 238]. There are several proofs of this result: Bessaga and Petczyfiski [4], [5], Gelbaum [13], Day [9]. The p r o o f of Day gives something more. It is shown that in every infinite-dimensional Banach space X there is a biorthogonal system (x*,x~) such that *

I1x. II = 11x.l! = 1 and

(x,,)


is a basic sequence ,i.e. is a basis for a subspace of X. The proofs of

Received July 27, 1964. * Lecture delivered at a symposium on Series and Geometry in Linear Spaces, held at the Hebrew University of Jerusalem from March 16 till March 24, 1964. (1) By Fr6chet space we mean a linear-metric, complete, locally-convex space. The symbol C denotes the Banach space of all real valued continuous functions on the closed interval [1 ;0] s denotes the Fr6chet space of all real valued sequences: (C × C × ... ), denotesthe space of all sequences with elements in (7.

132

1964]

SOME PROBLEMS ON BASES IN BANACH AND FRECHET SPACES

133

Bessaga and Petczyfiski are valid for Fr6chet spaces. If X is a Fr6chet space which is not isomorphic to any Banach space, then it is possible to choose X1 nuclear [8-]. We do not know how " n i c e " one can choose Xo for a given X. P.1. Let X be a separable Fr6chet space (in particular a Banach space) having one the of properties (As) (i = 1, 2, 3, 4, 5, 6). Is X isomorphically embeddable in a Fr6chet space (respectively in a Banach space) with a basis and having the same property (As)? The properties considered are: (Al) X is reflexive; (A2) X is weakly complete; (A3) X is isomorphic to a conjugate space; (A4) bounded sets (2) in X are weakly conditionally sequentially compact; (As) bounded sets in X are precompact ( = X is a Montel space); (A6) X is nuclear. In an arbitrary Fr6chet space there are many different basic sequences. Recent results of M. I. Kadec and Petczyfiski [17] give rather satisfactory information in what cases in a given set of vectors there exist basic sequences. Definition. Let X be a Fr6chet space and let X* be the conjugate space to X.A set F c X * is said to be norming for X if for every fundamental system of bounded sets (B,) in X* the sequence with Ilxll,.~r=sup for x e X is an admissible system of pseudonorms in X, i.e. consistent with the topology of X.

(1! [I.onr),

{Ix*xl:

r}

We shall write x ~ 0 iff x*x, ~ 0 for every x* in F. r THEOREM 1. A subset M in an arbitrary Frdchet space X contains an infinite basic sequence if and only if there is a norming set F c X * for X and a sequence (x,) of elements of M such that x, ~ 0 (n = 1, 2,...) and t,x, ~ 0 for every sequence of scalars (t,). THEOREM 2. Let (x,,) be a sequence in a Fr~chet space X which does not converge to 0 and let x, ~ 0 for some subset FcX* which is norming for X. Then (xO contains an infinite basic sequence. THEOREM 3. Let M be a bounded non compact set in a Frdchet space X. Then there exists in X a subspace with basis, which is spanned by an infinite part of M. THEOREM 4. A Frdchet space X has one of the properties A~for i = 1,2,4,5, if and only if every subspace of X with a basis has the same property A s (cf. [20]). THEOREM 5. Let M be a bounded set in a Fr~chet space X . Then the following conditions are equivalent: (2) We recall that a set B in a topological space X is said to be bounded if the function f : [1 ; 1] × B ~ X, with f(t, x) = t x, is uniformly continuous.

r

134

A. PELCZYNSKI

[June

(1) The weak closure of M is not weakly compact in X. (2) There is a closed linear subspace E of X with a basis, such that the weak closure of E N M is not weakly compact. (3) There is a basic sequence (x,) in M and a linear functional x o in X* such that lira infn x~xn > O. Some results of R. C. James (Theorems 1-3 in [22]) can be easily deduced from our Theorem 5 (cf. [25]). We note (compare with Theorem 3) that if it were true that every subset M of a Frdchet space X contains an infinite part which spans a subspace with a basis, then in every separable Frdchet space there would exist a basis. This follows from the fact that in every separable Frdchet space there is a sequence of elements such that each infinite subsequence of it spans the whole space X [23]. This remark is due to V. I. Gurarij. P.2a. Is a Frdchet space nuclear if and only if each of its subspaces with a basis is nuclear? P.2b. Is a Banach space isomorphic to a Hilbert space if and only if each of its subspaces with a basis is isomorphic to a Hilbert space? The next two problems concern conjugate spaces (the property A3) P.3. Does every infinite-dimensional conjugate Banach space contain an infinitedimensional subspaee isomorphic to a conjugate space and having a basis (in particular, a boundedly complete basis)? P.4. Does every separable, non quasi-reflexive, conjugate space contain a subspace which is not isomorphic to a conjugate space? Recently J. Lindenstrauss has constructed in the space l a subspace non isomorphic to a conjugate space [24]. 2. The dual problem. It is natural to consider the dual diagram to (1). Namely P.5. Do there exist, for every infinite-dimensional separable Frdchet space X, infinite-dimensional Frdchet spaces X o and X 1 with bases, and linear operators onto ho and hi such that the diagram (1)

1hi

ho o

X ~.X,,-.X

holds? The only result known on P.5. is: If X is a Banach space then we can put X ° = 1, and if X is a Frdchet space not isomorphic to a Banach space then we can put X 1 = s (this uses a result of Eidelheit 112]). For every reflexive space X a space X 1 exists (using standard dual arguments and applying diagram (1) for conjugate spaces). Thus a space X 1, and hi, exist for every Banach space which admits a linear mapping onto a reflexive space (this property is equivalent to the fact that X* contains a reflexive subspace).

1964]

SOME PROBLEMS ON BASES IN BANACH AND FRECHET SPACES

135

P.6. Is it true that every reflexive space is a linear image of a reflexive space with a basis? For Banach spaces P.6 is equivalent to the problem P.I for the property AI. The next problem is connected with P.1. for A6. P.7. Is it true that every nuclear space is a linear image of a nuclear space with a basis? 3. Conditional and unconditional basic sequences. We recall that a basic sequence (x,,) in X is called unconditional if it is an unconditional basis for a subspace of X. A non unconditional basic sequence is called conditional. An important and rather difficult question is (cf. [6], [9]) P.8. Does there exist in every infinite dimensional Banach space X an infinite dimensional subspace with an unconditional basis? If X is a Fr6chet space which is not isomorphic to a Banach space then X contains an infinite-dimensional subspace with an unconditional basis (either (s) or a Kothe space, cf. [8, Theorem 1]). The answer on P.8. is positive in the case where X is isomorphically embeddable into a Banach space with an unconditional basis [5, p. 157]. It is perhaps easier to find a (positive) solution of P.8. under the additional assumption that X is uniformly convex or that X admits a linear mapping onto a space with an unconditional basis. The problem P.8. is important from the point of view of the topological classification of separable Banach spaces (cf. [7]). For this purpose it is sufficient to answer affirmatively the following P.9. Does every hereditary non reflexive Banach space contain a subspace either isomorphic to I or to Co? From a result of R.C. James [14] it follows that P.9. is a particular case of P.8. Altough we do not know whether there exist unconditional basic sequences in every Fr6chet space, the construction of basic sequences about which we can establish that the are conditional is also difficult. To show that in every infinitedimensional Banach space there exist conditional basic sequences V. I. Gurarij [,15] used the deep result of Dvoretzky [10] on the spherical sections of convex bodies and the heavily analytic construction of Babienko [-i] of a conditional basis in 12. Recently I. Singer and the author [21] have obtained a considerably stronger result than that of Gurarij. THEOREM 6. In every infinite-dimensional Banach space with a basis there exist continuum non equivalent normalized bases from which at least one is conditional. The proof of Theorem 6 given in [21], though not simple, does not make use of the result of Dvoretzky [10].

136

A. PELCZYIqSKI

[June

We recall that bases (x,) and (y~) are said to be equivalent if ~ t,x, converges if and only if ~,tny, converges for every sequence of scalars (t,). If =1 (n = 1, 2,.-.) then a basis (x,,) is called normalized.

[lx ll

By a theorem of Dynin and Mitjagin [11] (see also [18]) every basic sequence in a nuclear Fr6chet space is unconditional. It seems to be very probable that the results of Gurararij and Petczyfiski-Singer quoted above can be generalized to a new characterization of nuclearity of Fr6chet spaces. Namely P.10. Let X be a Fr&het space (with a basis). Is it true that X is nuclear if and only if every basic sequence (every basis) in X is unconditional? It is well known that in 12 all normalized unconditional bases are equivalent (Bari [3], Gelfand [14]). P.11. Is it true that an infinite-dimensional Banach space X with an uncon ditional basis having the property that all normalized unconditional bases in X are equivalent is isomorphic to 12? However we are not able at present to construct any normalized unconditional basis in the spaces l and Co non equivalent with that consisting of unit vectors. Such bases for the spaces l v (1 < p < + ~ ) were constructed in [19]. Let us mention THEOREM 7 (Petczyfiski-Singer [21]). I f X is a Banach space with an unconditional basis and all normalized infinite unconditional basic sequences in X are equivalent, then X is either isomorphic to 12 or is of finite dimension. 4. Hilbertian and BesseHan bases and basic sequences. DEFINITOIq. A normalized basis (xR)(basic sequence) in a Banach space X is called Hilbertian (Besselian) provided that ~n tnx~ converges for every (t,) E 12 (if ~, tnXn converges, then (t,,) ~ 12). It is rather easy, using the method of Gurarij [15], to show that every Banach space in which all normalized basic sequences are Hilbertian (Besselian) is of finite dimension. We are not able to establish the result analogous to Theorem 6. Hence P.12. Let X be a Banach space with a basis and let all normalized bases in X be Hilbertian (Basselian). Is it then true that X is of a finite dimension? Let us mention P.13. Does there exist in the space C (in the space L) a normalized Besselian (resp. Hilbertian) basis? In particular, does there exist in C an orthonormal system of continuous and uniformly bounded functions which is a basis for C? We conjecture that the answer on P.13 is " n o " .

1964]

SOME PROBLEMS ON BASES IN BANACH AND FRECHET SPACES

137

REFERENCES 1. K. I. Babienko, On conjugate functions, Dokl. Akad. Nank. SSSR 62 (1948), 157-160 (in Russian). 2. S. Banach, Thdorie des opdrations lindaires, Warszawa, 1932. 3. N. K. Bari, Biorthogonalsystems and bases in Hilbert space, U~en. Zap. Moskov. Gos, Univ., 148 (1951), 69-107 (in Russian). 4. C. Bessaga and A. Petczyfiski, On bases and unconditional convergence of series in Banach spaces, Studia Math. 17 (1958), 151-164. 5. C. Bessaga and A. Petczyfiski, Properties of bases in Bo spaces, Prace Mat. 3 (1959), 123-142 (in Polish). 6. C. Bessaga and A. Pelczyfiski,A generalization of results of R. C. James concerning absolute bases in Ban~h spaces, Studia Math. 17 (1958), 165-174. 7. C. Bessaga and A. Petezyfiski, Some remarks on homeomorphism of Banach spaces, Bull. Acad. Polon. Sci., Sbr. sci. math., astr. et phys. 8 (1960), 757-761. 8. C. Bessaga, A. Pe|czyfski and S. Rolewicz, On diametral approximative dimension and linear homogenity ofF-spaces, Bull. Acad. Polon. Sci., Sbr. sci. math., astr. et phys. 9 1961), 677-683. 9. M. M. Day, On basis problem in Banach spaces, Proc. Amer. Math. Soc. 13 (1962). 655-658. 10. A. Dvoretzky, Some results on convex bodies and Banach spaces, Proc. of the International Symposium on Linear Spaces, Jerusalem 1961, 123-160. 1I. A. S. Dynin and B. S. Mitiagin, Criterion for nuclearity in terms of approximative dimension, Bail. Acad. Polon. Sci., Sbr. sci. math., astr. et phys. 8 (1960), 535-540. 12. M. Eidelheit, Zur Theorie der Systeme linearer Gleichungen, Studia Math. 6 (1936), 139-148. 13. B. R. Gelbaum, Banach sp~ces ant bases, An. Aead. Brasil. Ci. 30 (1958), 29-36. 14. I. M. Gelfand, A remark to the paper of N. If. Bari "Biorthogonal systems and bases tn Hilbert sptlce," U~en.en. Zap. Moskov. Gos. Univ. 148 (1951), 224--225. (in Russian). 15. V. I. Gurarij, On slopes of subspaces and conditional bases in Banach spaces, Dokl. Akad. Nauk. SSSR 145 (1962), 504--506. (in Russian). 16. R. C. James, Bases and reflexivity of Banach spaces, Ann. of Math. 52 (1950), 518-527. 17. M. I. Kadec and A. Petczyhski, Basic sequences and norming sets in Banach and Frdchet spaces, Studia Math. (to appear) (in russian). 18. B. S. Mitiagin, Approximative dimension andbases in nuclear spaces, Uspehi Mat. Nauk. 14 (100) (1961), 63-132. 19. A. Pe~czyfiski, Projections in certain Banach spaces, Studia Math. 19 (1960), 209-228. 20. A. Petczyfski, A note on the paper of l. Singer "Basic sequences and reflexivity of Banach spaces", Studia Math. 21 (1962), 371-374. 21. A. Petczyfiski and I. Singer, On non equivalent bases and conditional bases in Bunach spaces, Studia Math. 25 (1965), 5-25.

22. R. C. James, Weakly compact sets, Trans. Amer. Math. Soc. 113 (1964), 129-140 23. V. Klee Jr., On the Borelian projeetive types of linear subspaces, Math. Scand. 6 (1958), 189-199.

138

A. PELCZY~qSKI 24. J. Lindenstrauss, On a subspaee of the space l, Bull. Acad. Polon. Sci. des Sci. Math.

astr. et phys. 12 (1964), 539-542. 25. A. Pe|czyfiski, A proof of Eberlein-Smulian theorem by an application of basic sequences. Bull. Acad. Polon. Sci., S6r. des Sci. Math. astr. et phys. 12 (1964), 543-548. DEPARTMENTOF MATHEMATICS UNIVERSITYOF WARSAW

ON STEINER SYSTEMS" BY

H. HANANI AND J. SCHONHEIM ABSTRACT

Steiner's "combinatorial problems" have so far been solved only for k=3 [5, 3] and for k---4 [1, 2]. In this paper a complete solution of the problem is given for "closed" Steiner systems, i.e. systems having n=2 k-1 --1 elements. Use is made of methods developed by Zaremba [7] for abelian groups. 1. Introduction. Let E be a given set of n elements, and let Rt(t = 3,4, ..., k) be a system of nonempty subsets of E having t elements each, i.e. the elements of R, are certain t-tuples of E. A t-tuple (t = 4, 5, ..., k) will be called free in respect o f Ra,R4, "",R,-1 (briefly: free) if it does not contain as a subset any j-tuple of R j, (j = 3, 4,---, t - 1). Pairs and triples of elements of E are considered to be free. DEFINITION 1. A system S k = U j =k 3 Rj will be called a Steiner k-system for E if the following conditions hold: (A) every element of S k is free; (B) every free t-tuple of E (t = 2, 3,..., k - 1) which is not an element of Rt is contained as a subset in exactly one element ofRt+ 1. As early as 1852, Steiner [6] formulated the following problem: given an integer k, (k = 3, 4,...), what conditions should be imposed on n in order to ensure the existence of a k-system Sk? It may be easily verified (see e.g. [4]) that a necessary condition for the existence of a Steiner k-system S~ is t-2

(1)

n = l (mod 2) and (t!) -1 I-I (n + 1 - 2 z) = integer

t =3,4,...,k.

i=0

So far, condition (1) has been proved to be also sufficient for k = 3 by Reiss [5] and Moore [3] and for k = 4 by Hanani [1, 2]. For k > 4 the problem is still open. Received February 26, 1964. * This research was supported by the United States Air Force under Grant No. AF-EOAR6360 and monitored by the European Officeof Aerospace Research. 139

140

H. HANANI AND J. SCHONHEIM

[June

2. Closed Steiner systems. DEFINITION 2. A Steiner k-system Sk for E is closed if every free k-tuple of E is an element of Rk. The number of free k-tuples which are not elements of Sk is k-1

(2)

(k!) -1 1-[ (n + 1 - 2'). i=0

In a closed Steiner k-system, this number is zero and therefore necessarily (3)

n = 2 k- 1 _ 1.

We shall prove that condition (3) is also sufficient, namely that THEOREM 1. I f E is a set o f n = 2 k- 1 _ 1 elements, then there exists a closed Steiner k-system Sk f o r E.

Proof. Let there be given an abelian additive group G, having a base B = {bo)}7= 1 consisting of n elements, each of order 2. Denote the elements of E by e ~ ( i = l , 2 , . . . , n ) . Consider the 1-1 correspondence e ~ b t ~ ) . It generates the usual 1-1 correspondence between the subsets of E and the elements of G in which the empty subset of E corresponds to the zero element of G and the t-tuple {e~,,% ... e~+} to the element ] ~ = 1 b(~j) of G. Let G, denote the subset of G composed of the elements gt corresponding to the t-tuples in E. We shall denote gt ~ gs if the inclusion holds for the corresponding subsets of E; we shall also denote gt as a free element if the corresponding t-tuple is free. Zaremba [7] proved that there exists a subgroup H of G such that every element g e G is representable uniquely as a sum of an element h ~ H and a base-element b e B or zero (4)

g = h + b (or 0).

Let H t = H t~ G t and let ht denote a general element of H r From (4) follows: (5)

H1 = H2 = ~, ht- 2 + b' + b" ~ h t ~ h~_ 1 + b, (b, b', b" ~ B).

Further, we obtain the unique representation: (6)

gt = b, g2 = ha + b, ga = h3, or h 4 + b,

gt-1 = hi-2 + b, or ht-~, or ht + b,

(b e B, t > 4).

Let us now construct a family of subsets P~ c H t (t = 3, 4,..., k) of G, such that the corresponding systems Rt will form a dosed Steiner k-system for E. Put Pa = Ha and P4 = H4. By (6), the systems S a correponding to Pa is a Steiner 3-system and $4, corresponding to Pa L)P4, is a Steiner 4-system.

1964]

ON STEINER SYSTEMS

141

Suppose that S t corresponding to [..Jt,=a Pi, (t < k) forms a Steiner t-system. We I t + l p will shall construct a set Pt+l c Ht+l such that St+ 1, corresponding to Itd~=3-~ form a Steiner (t + 1)-system. Denote by p~ a general element of Pi and by qz a general element of H~ - Pi (if such elements exist). By (2), there exist free elements "gt 6 P,. Let g* be such an element. We prove

g* ~ h,. By definition, g* # Pv Suppose g* = qt ; Ithere exists g*_ 1 ~ Gt- 1 satisfying g*- 1 = g* + b = qt + b with b c gt*. But since g*_ 1 c gt, g*- 1 is free and according to (B) g*_ 1 = Pt + b' in contradiction to the uniqueness of (6). Similarly, we prove (8)

g* # ht-1 + b.

g* is free, hence g* # Pt-~ + b. Suppose g* = qt-1 + b. There exists gt-2 ~ Gt-2 such that g*_ z = g* + b + b' = qt-1 + b'. On the other hand g*_ 2 is free and by (B), g?-2 = P t - 1 "I- b~P, which contradicts the uniqueness of (6). From (6), (7) and (8) there follows (9)

g* = ht + 1 + b.

Denote by Pt+ 1 the set of elements hi+ 1 obtainable by (9) from all free elements gtl¢Pv Then the system St+ 1 corresponding to Iu It+lp i=3-i has the property (B). In order to show that the system St + x has property (A) as well, suppose to the contrary that some Pt+ ~ satisfies (10)

Pt+l = P*+I-j + g*

for some j. From (5) follows 3 < j < t - 2 and by (9) we have (11)

g* = Pt+l + b = P*+l-j + g* + b*

with p*+ 1-~ e Pt+ 1-j, g* e Gj and b* e B. Clearly b* c Pt+ 1 and therefore either

(12)

p*+ ~_: + b* = g~_j

or~ (13)

g* +b* = g j - l .

Both possibilities lead to a contradiction. Indeed (12) and (11) imply g * c g*, consequently g* is free and g* ¢ Px and therefore g* = p~+ t + b'. On the other hand, we know that H is a group and therefore by (10) g* e H:, which contradicts (5). Further, (13) and (11) imply gt* = P*+ 1-j + gj-1, contradicting the assumption that g* is free. This proves the induction from t to t + 1 for t < k. For t = k, the system Sk is clearly a closed Steiner k-system.

142

H. HANANI AND J. SCHONHEIM

REFERENCES 1. H. Hanani, On quadruple systems, C.anad. J. Math., 12 (1960), 145-157. 2. H. Hanani, On some tactical configurations, Canad. J. Math., 15 (1963), 702-722. 3. E. H. Moore, Concerning triple systems, Math. Ann., 43 (1893), 271-285. 4. E. Netto, Lehrbuch der Combinatorik, zweite Auflage, Leipzig, 1927, pp. 202-204. 5. M. Reiss, Ueber eine Steinersche combinatorische Aufgabe, J. Reine Angew. Math., 56, (1859), 326-344. 6. J. Steiner, Combinatorische Aufgabe, J. Reine Angew. Math., 45 (1853), 181-182. 7. S. K. Zaremba, A covering theorem for abelian groups, J. London, Math. Sot., 26 (1950), 71-72. TECHNION-ISRAELINSTITUTEOF TECI-INOLOGY, HAtFA TEL-AvIv UNIVERSITY