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

COMPLEXES OF RINGS BY

S. A. AMITSUR* ABSTRACT

Homology group of complexes of finitely generated projective modules are shown to be torsion groups, and a simplified proof of the vanishing of the cohomology groups n > 3 of insepaxable extensions is given. This paper contains results on two different topics concerning complexes of rings: 1) Homology groups for complexes of finitely generated projective Ralgebras, and 2) Cohomology groups of inseparable extensions. The complexes of fields which have been introduced in [1], were extended by Rosenberg and Zelinsky to arbitrary commutative R-algebras, and their cohomology groups have been studied. In [2], homology groups have been introduced using the notation of a norm but this could be applied only for free algebras and, in particular, for field extensions. Recently, O. Goldman [4] has given a satisfactory definition for determinant of endomorphisms of finitely generated projective R-modules (R--a commutative ring). This seems to be the right background for defining a norm for arbitrary finitely generated projectives R-algebra $, and after proving the basic properties of this norm--the result on the homology group of [2] are generalized to this case. As a consequence it is shown that the cohomology group are of torsion groups with exponent depending on the maximum of the p-ranks of S, which are the dimension of the spaces S ® Rp where Rp is the local ring of quotients of R with respect to the prime ideals p of R. The second part contains a different proof of a result of Berkson [3] that Hn(F/C) = 0, n ~ 3 for inseparable extensions F of C of exponent 1. The proof is simpler and probably can be carried over to a more general case but no attempt has been made here. 1. Determinants and Norms. Let E be a finitely generated ( f . g) projective R-module, and u e Hom R(E, E). If E is free then the determinant det ~ is a welldefined element of R, and in the general case we adopt Goldman's defintion ([4]) of the determinant which is obtained as follows: Let E ~ E 1 = F, and F a f.g. free R-module. If e 1 denotes the identity transformation of E 1 and ~t = • • et, then set det cc = det ~1 where the latter is defined Re~ived April 9, 1964. • This work has been sponsored by NSF Grant No. 1964whilethe author was at Northwestern University and by Grant AF EOAR 63-70 of the European Office of Aerospace Research, U.S. Air Force. 143

144

S.A. AMITSUR

[September

in the classical way. It is show n in [4] that det ct is independent on E1 or F and it has most of the properties of the determinant. Let R[x] be the ring of polynomials in one indeterminate over R, then the characteristic polynomial of ~ is defined as d e t ( x - c t ® l ) = q ~ ( c ~ , E , x ) , where ® 1 is the R[x] endomorphism of E ® R[x]. If p is a prime ideal in R, and Rp is the local ring of R at p, then E ® Rp is free of finite rank--which is called the p-rank of E. We shall use the following result on the characteristic polynomial of the zero ([4, Proposition 2.2, Theorem 3.1]): (1.1)

(a(O,E,x) = ~ eix i, i=0

where the ej are mutual orthogonal idempotents and 1 = ]~ei. For every prime ideal p, there exists exactly one ej 6 P, and then the p-rank of E is j; and for each ej # 0 there exists a p such the p-rank of E is j. We shall need the following additional properties of the determinants: PROPOSITION 1 : (a) ~b(a,E, O) = det ( - ct).

(b) For every ). ~ R, qS(0t- 2, E, x) = ~b(ct,E, x + 2). (c) I f 2 e F then det2 = ]~,"=o ei2~. Proof. The basic tool in the proof is the application of [4. Proposition 1.4] which states: (1.2) If f : R ~ S is a ring homomorphism, and ~ ® 1 ~ Homs (E ® S, E ® S), where S is given the structure of an R-module by f, then det(~ ® 1) =f(det~). Consider the homomorphism f : R[x] ~ R given by setting f[~b(x)] = ~b(0), and then (E ® R[x']) @ R is identified with E, then det( - ~) = det [(x - ~ ® 1) ® 11 = = f . det(x - ~@ 1) = $(~,E,0) which proves (a). The proof of (b) is obtained similarly by considering the homomorphism f l : R[x] ~ R [ x ] , by setting f[~b(x)] = tk(x + ;t). Here (E®R[x])QR[x] '~ E®R Ix] by identifying v ® 1 ® ~b[x] with v ® q~[x] and Ix - ~ ® 1] ® 1 is identified with x+2-~®l, since [ ( x - o ~ ® l ) ® l ] ( v ® l ® l ) = v ® x ® l - o w ® l ® l = v® l®fx-~v® I® I =v®l®(x + 2)-~v® I ® I =v® 1 ®x - (~ - 2) v ® 1 ® x so that applying (1.2) we obtain det(x - (~ - 2) ® 1) = f det(x - ~ ® 1) = dp(ot,E,x + 2) which proves (b). The last result is a simple consequence of (a) and (b) obtained by setting ct -- 0, x = 0 and using (1.1). Next we turn to the notion of the Norm, and we consider henceforth two commutative rings S ~ R with the same unit, and such that S is f. g. R-module and

1964]

COMPLEXES OF RINGS

145

R projective. Let a e S and a,: u ~ ua be the R-endomorphism of S obtained by multiplication by a. We define DEFINITION. Norm (S/R; a) = det at. The following properties of the Norm will be used: PROPOSITION 2. (a) Let S be an R-algebra, S' and R':algebra and tr: S ~ S' a ring isomorphism which maps R on R' then tr Norm (S/R; a) = Norm (S'/R'; tra). (b) Let E be a f.g. S-projective module, and • E Homs (E, E). Consider E also as an R-module, then E is f.g. and R-projective. If dets~, det~t denote the determinants of ct considered as an element of Horns(E, E) and HomR(E, E) respectively, then detR ~ = Norm (S/R, dets ~t). ProoL Let R' be given the structure of an R-algebra by tr, i.e., r • r' = tr(r)r', r ~ R and r ' e R'. Then S ®a R' can be identified with S' by setting s ® r' = tr(s)r' and with this identification a, ® 1 = a(a)r. Hence, it follows by (1.2) that Norm (S'/R'; tr(a)) = det [a(a)r] = det (a, ® 1) = tr det a, = a Norm (S/R; a)(1) If E is S-free and S is R-free then part (b) is well known ([6, Proposition 7, p. 140]). The general case will be obtained by reduction to the free case: First we note that E is also a f.g. projective R-module. Indeed, clearly it is f.g. over R; and if E @ E' = Y_,Su~ is free S-module, then since Su~ ~-S, and S is R-projective it follows that Su~ @ St is R-free for some R-module Si, and consequently E t~ E' ~) ]ES~ = ~,(Su~ O) Si) is R-free which proves that E is Rprojective. Next we observe that it suffices to consider only free S-modules. For, assume that (b) holds for free modules, and E be an arbitrary projective module, then E ~ E' = F and F a f.g. and free over S, for some E'. Then, ~x = ct ~ el and dets~ = dets ~1 by definition. It follows now by [4] proposition 1.5, that detR~l = detRctdetae~, and since e~ is the identity detRe~ = 1 so that detR~t = dets~. Hence dets • = deta ~1 = Norm (S/R; dets 0~1) = Norm (S/R; dets ~) since (b) was assumed to be valid for ~t. Consider now the element r = deta ~ - Norm(SIR; dets~t). Let . / / b e a maximal idea in R, and R ~ be the local ring at J [ . Thus, S ~ = S ® R/a is R.~-free and Eja = E ® R~ can be considered as an S~-module, and assuming that E is S-free then E.~ is also S ~ free. (1) This simplified proof is due to the referee.

146

S.A. AMITSUR

[September

Let f : R ~ R ~ and its extension f: S-* S ® R ~ . It follows by (1.2) that d e t ~ ( ~ ® 1)=/(detRc0 and dets(~® 1 ) = f ( d e t s ~ ), where ~ ® 1 in both cases is taken as an endomorphism of E.~. Now E~, S~ are free over R~a, hence: Norm [S~/R.~; dets~ (~ @ 1)] = detR~ (ct ® 1). Consequently:

f(r) = f (det~ ~) - f Norm (SIR; det s ~) = detg~ (~ ® 1) = f(det [(dets ~), ® 1]) = dets~ (~ ® 1) - f [det [(dets 0t @ 1),] ] = detR~ (~ ® 1) -- Norm [ S ~ / R ~ ; f(dets ~)] = detR~ (~ @ 1) -- Norm (S.~/R~a ; dets~ ~) = 0 This being true for every maximal ideal .///, yields by [4, lemma 1] that ~ = 0, which completes the proof of (b). A simple corollary of (b) is the transitivity property of the Norm: COROLLARY3. Let T ~ S D R each f.g. and projective over the preceding ring then Norm (T/R; a) = Norm [T/S; Norm (S/R, a)]. 2. Homology of Rings.. The complex C*(S/R) was defined in [2] for fields S which are extensions of R, with the aid of the Norm, and this can be extended to arbitrary f.g. R-projective rings S as follows: Let Sn= S ® ... @ S(n... terms and ® taken with respect to R), the homomorphism e~:S"-l~ S" are defined by setting: (2.1)

ei(al®...®an_l)=al®...®at_l®l®a~®...®a~_x.

S n is also a f.g. projective eiS ~- Lmodule and we set (2.2)

vi(a ) = e~ - 1Norm (S~/eiS ~- 1; a),

a ~ (S~) *

where ( )* denotes the corresponding multiplicative group of the invertible elements. The complex C*(S/R) is the sequence of groups, R , - S* , - (S2) *

with the derivation d

,- ... ,-

(Sn) * - . ( S ~ + b *

: (S~) * --> (S n- 1). defined by:

.~" (a) = [vl(~) v~C,~) -.. ] Ivy(a)

~, -.. 3-'.

The last mapS* ~ R is ~ = Norm(S/R); • ). The Mappings ./ff are well defined since a is invertible and therefore, [4, Proposition 1.3] implies that vi(a)is invertible and so vi(a)- i exists.

1964]

COMPLEXES OF RINGS

147

The following relations hold between the v~, ei : LEMMA 4. (2.3)ViVj = VjVi+I (2.4) eivj = Vj+le t

e,~vj = vj~t+l

for i > j for

i < j and

for i > j.

The proof of (23) follows similarly to the proof of (1.7) of [2] using the transitivity of the Norm which holds also in our case by Corollary 3. To prove (2.4), we use the relation (2.5)

eiej = ej + leZ,

i<j

and (1.2) in the following situation: Consider S" as ejS n- 1 module, and first let i < j , then it follows by (2.5) that ei induces a map of : ejS ~- 1 ... ej+ 1S". Apply now (1.2) with f = ei and E = S" then we have det(ela)r = e i d e t a , for a e S ~. Since a ® 1 in our case is readily seen to be e~a. Thus: det (eta), = Norm (S ~+ 1/ej + 1S", eia) = ej+ ivy + 18i(a) eideta, = eiNorm(S"/ejS",a)=eisjvj(a). Hence by (2.5) we get: ej+ aVj+ tei(a) = eiejvj(a) = ej+ teiva(a). Cancelling ej+ a of both sides yields the first part of (2.4). The second part follows similarly: Let i > j , so that (2.5) yields eiej = eyet- 1 by interchanging i with j + 1 and j with i. Here el: ~jS "-x ~ e j S "-x, and as before the relation det(e~a), = ei det a~, a ~ S" will yield: det (8ia)r = Norm (S" + 1/ejS"; e:a) = ~jvfi(a ) s t det a, = ei Norm (S"/sjS" ; a) = eiajvj(a). Hence, ejvjei(a ) = eiejvj(a ) = ejei_lvj(a ) which yields by cancelling ej the second part of (2.4), by replacing i - 1 by i. The property (2.3) yields as in [2] p. 4, the fact that C . ( S / R ) is a complex, and thus the homology groups H,(S/R) are well defined for arbitrary f.g. R-projective modules S. Next we show that the 'restriction' and 'transfer' work for the general case as well. Let T be an algebra which is a f.g. projective R-module, then the restriction p * : H , ( S / R ) ~ H , ( S ® T / T ) was defined as the map induced by the complex homomorphism p : C , ( S / R ) ~ C . ( S ® T / T ) where p : S" ~ S" ® T is given by p"(a) = a ® 1, followed by the isomorphism of the complexes C.(S/R, ® T) and C , ( S ® T[T), where the first consists of the groups ( S " ® e T ) * and the latter

148

S.A. AMITSUR

[September

consists of the groups [(S @e T)T]* with the obvious derivations. The proof of this result as given in [2] depends on a choice of a base of the corresponding modules and in our case it will be replaced by (1.2). THEOREM 5A. The mappings a ": S" ® T ~ (S ® T)~ given by

~"(Sl®...®s,®t)=(sl®l)®r...®r(S,®t),

st~S,

t ~ T yield a complex isomorphism ~r: C ( S / R ® T ) ~ C ( S ® T/T) and the mappings p" : S ~~ S" ® T, given by p"(a) = a ® 1 yield a complex homomorphism p : C,(S/R) --, C,(S/R, ® T). The first part is an immediate consequence of the fact that a is an isomorphism which commutes with the 8j, and part (a) of proposition 2 yields cr[Norm (S" ® T/S"- 1 ® T, a)] = Norm ((S ® T)"/(S ® T)n- ~, aa) from which we readily verify that av~ = v~a. In the proof of the second part we apply (1.2) to the homomorphisms p~ : eiS "- 1~ eiS n- 1® T which replaces f and S being considered as an e~S"-1-module. Thus we get: det pa = det (a ® 1) = p det a,

a e S"

from which it follows that Norm (S n® T/(eiS"- i ® T); a) = p[Norm (S"/eiS "- 1; a)], and since e, commutes with p, one readily verifies that p is a complex homomorphism. The map ~: C(S/R, ® T) ~ C(S/R)(2) is defined by z"(a) = Norm (S" ® T/S ~, a) for a e S ~ ® T , and it yields the transfer map (Ta-x)*:H(S® T / T ) ~ H ( S / T ) . This is also true in the general case as we show that: THEOREM 5B. ~ is a complex homomorphism. Indeed z commutes with Ca; for apply (1.2) with e j : S " ~ S "+~ and E = Sn® T, so that E ® S "+1 = S "+1 @ T since S "+1 is considered as S~-module with the use of ej. Thus (1.2) implies that deteja = Norm (S"+1® T/S"+1; eia) = ~ Norm (S ~+ 1/S"; a), i.e., ~ej = ejz. The proof of zv~ = vjx follows as in [-2, p. 6] with the use of the transitivity of the Norm (Corollary 4). REMARK. Theorem 2.6 of I'2] considers also the homomorphism # : S ® T ~ T when T _ S, and it is given by/z(j ® t) = it. Nevertheless, # induces only a homomorphism for the cohomology groups: H*(S® T / T ) ~ H * ( S / T ) and the proof for homology group fails. The relation between the transfer and restriction, namely, that x'p* = dimension of S over R, is not true in this form. But: (2) This is defined for both C,( logy and cohomology groups.

, ) and C*( , ), and the results are valid for both homo-

1964]

COMPLEXES OF R I N G S

149

THEOREM 5C. z*p*(a) = ~,eja ~ where the idempotents ej are given in (1.1). In particular, if all p-ranks of S over R are n then z*p*(a) = a ~. This is an immediate consequence of (c) of proposition 1. An important application of the Norm is the following: THEOREM 6. I f S is a f.g. projective R-algebra; and if the p-rank of S is m for every prime ideal p of R then the elements of H(S/R)(2) are of order dividing m. In the general case if m is the maximal p-rank of S, then the elements of H(S/R) are of order dividing m !. Proof. As in the proof of [-2] Theorem 2.10, we consider the homotopy v : S "+l ~ S", which is defined as v = v.+l = e.~l Norm (S"+l/e.+lS",a). It follows from (2.4) that eiv.= v.+lel, and therefore (when written additively): 6 = Av. - v.+lA = ( ]~( - 1)it/)v. - v.+ i E ( - 1)½~ = ( - 1)"+lv.+le.+l where A: (S")* ~ (S"+~) * is the derivation of C*(S/R). Proposition 1 yields that v.+is.+l(a) = ~,eia ~ and if the p-rank S is m for every m, e,. = 1 and all ej = 0; hence v.+ xe.+ ~(a) = a" which proves the first part of the theorem since v.+ le.+ 1 is homotopic with zero. To prove the second part, we note that ~e~a~= Ab for some b since v.+ xe.+ l(a) = ~_,eia~ and v.+ le.+ x is homotopic with zero. Now eieja = ejeia for e , ~ R , and let ivl = m!, thus set w = ]Ee,vv'. Clearly w has an inverse and Aw = ~,ei(Ab)"'= ]~ei(~ejaJ) ut= ~,eia m!= a mz. The proof for homology groups follows the proof of [2] theorem 2.10 using the homotopy e = e,+ l , and first observing that Nw = ~ei(Nb)U'sinceeyj(a) = v~(eia) for idempotents e i of the base ring R, and finally considering S" = ejS" ~) (1 - ej)S" as modules over ejR @ (1 - ej)R. 3. T h e i n s e p a r a b l e c a s e . Let F be an inseparable field extension o f a field C of characteristic p. The purpose of this section is to give an alternative proof for the following theorem of Berkson [3]. THEOREM 7. Hk(F/C) = Ofor k >=3. First we reduce the theorem to the case that F = C(~) is generated by a single element ~ satisfying an equation ~9 - c = 0. Indeed, if F is not of this form, then F = I D C for some K which is also inseparable over C, and F is inseparable over K. It follows by [5] Theorem 4.3 that there is an exact sequence. •.. ~ Hk(K/C) ~ Hk(K/C) -~ Hk(F/K) ~ H k +i(K/C) ~ . . . and a simple induction process on the degree of the extensions will yield that Hk(K/C) = Hk(F/K) = 0 for k ->_3; hence, the exactness yields that Hk(F/C) = 0 for k ~ 3 .

150

S.A. AMITSUR

[September

In case F = C(~), then the mapping It : F ® F ~ F given by #(a ® b) = ab has a kernel N which is an 1 ® F = F-algebra generated by the single element = ~ ® 1 - 1 ® ~; furthermore N p = 0 and Hk(F/C) = 0 for k > 3 is a consequence from the following general result: LFMMA 8. Let S be an R-algebra of characteristic p # 0 for which the map

splits as an R-module map. Let It: S ® S --* S be the multiplication homomorphism i.e., I~(a ® b) = ab, and let N = K e r i t . If N p = 0 then Hk(S/R) = 0 for k>=3.

R ~ S

ProoL Consider the complex CI(S/R): (s2) *

*

-, (sb* -*-..

which is obtained from C*(S/R) by chopping its first term S. Let It = Iti : Sk ~ s k - l (k > 2) be given by: pl(al @ a z @ a3 ® "" ® an) = ala2 @ aa ® "'" ® an ; that is, It1 = # @ 1 @ - - . ® 1 . First we show that ~1 yields the following exact sequence: (8.1)

1 ~ (1 + ~ r ) , ~ C~(S/R)

Its, > Cx*(S/R, ® S) ~ 1

and where we denote by C*(S/R, @ S) is the complex composed of the groups S* ~ (S @ S)* ~ (S ® S 2)* - * . . . -~ (S ® S k- 1), ~ . . . with the derivation is given by (written additively) A 1 = 5 2 - 53 + "" _+ 5n and thus does not affect the first term; and (1 + ~t/')* = Ker It1 is the complex: (8.2)

(1 + N)* ~ (1 + N @ S)* ~ . . - ~ (1 + N ® Sk-2) * ~ " "

Indeed, since #~51 = Itle2 and pxSi = 5i- 1 for i >= 2, it follows that /ZlA = p1(51 - 52 "1~ 53 - - 54 + " " ) = (52 - 53 -I- " " ) i t 1

= AIItl

and hence /q is a complex homomorphism, and from which we get the exact sequence (8.1). It follows now by [2] theorem 2.9 that the homology groups of CI(S/R, ® S) are zero; hence, the exactness of (8.1) yields that Hk[(1 +,/ff)*] ~ Hk[cI(S/R)] = H k+ 1(S/R). The latter follows from the fact that the groups of Cx(S/R) are those o f C*(S/R) but shifted by 1. To compute Hk[(1 + ~4r) *] we pass to an additive complex d/" by considering the following two maps(a): (3) This method is the same as in [l,p, 103], but there it was misused (as pointed out by Zelinsky-Rosenberg) since generally E and L have not the standard properties of the exponential and logarithm, even if every element is nilpotent of exponent p. Nevertheless, these properties hold if Np = 0 and when this assumption is not applicable, a different method for computation should be applied.

1964]

COMPLEXES OF RINGS

151

For every n • N ® S k - 2 ( k ~ 2), we define: n2

n p-1

E(n) = 1 + n + ~. + . . . + ( p _ 1)!

we define L(l+n)=n-

/,12

T

+...+(-1)Pp

rip-1

1

and we prove first that E maps the additive group of Nk = N ® S k-2 onto the multiplicative group (1 + Nk)*, and its inverse is the map L. Consider the ring of power series in two indeterminates t, s with coefficients in the field Q of all rational numbers, and let tv ~.v and Log (l + t) = ~ ( - 1 ) v-t t-~

Expt = ~ v=O

v=O

V

then we have Exp t . Exps = Exp(t + s) and Log(1 + t) + Log(1 + s) = Log([l + t)(1 + s)] and ExpLog(1 + t) = 1 + t, Log Expt = t. Now, E ( t ) = E x p t - R ( t ) , L(1 + t ) = L o g ( 1 + t ) - S(t), where R(t) and S(t) are power series in t containning powers of t with exponents > p. Thus, (8.2a) E(t)E(s) = [Exp t - R(t)] [Exp s - g(s)] = Exp (t + s) + U(t, s) =E(t + s) + V(t, s) and V(t, s) =R[t + s ] - R ( t ) E x p s - E x p t • R(s)+R(t)R(s) - 0 (mod[t p, sP,(t + s)P]). Hence identifying coefficients of both sides of (8.1a) we get that E(t)E(s) = E(t + s) +

Z

2~t's ~

i+j~_p

and the coefficient 2~j are rational numbers. The coefficient on the left side do not have denominators prime to p, hence so are the 2 ; consequently the last equality will hold also in any algebra over a field of characteristic p. In particular, in our case, where N~ = 0 , we obtain E ( n ) E ( m ) = E ( n + m) as ~,~+j~p2ijn~mJ~N~ for n, m E N k .

Using the other properties of Exp, Log quoted above, one obtains the proof of the facts that L:(1 + Nk)* --} Nk and it is the inverse orE. By applying E on each of the component of the complex (1 + ~¥')* given in (8.2) we obtain that (1 +.A")* is isomorphic to the complex .A". (8.3)

N - * N ® S-* . . . - } N ® S ~ - * ...

whose groups are the additive groups Nk = N ® S k-2 and with a derivation 6 =LA*E, where A* =~a+l is the derivation of the multiplicative groups (1 + Nk)*.

152

S.A. AMITSUR

[September

Our next aim is to show that:

(8.4)

6 = A + + ~ = 51 - - 8 2 q- 5 3 "'" all- ( - -

1)ks~ +

X

and where 2(n) =

v-1

1

[

1

]~ ( - 1)" (e~n)~(82n) ~-~ ~ = -~jr(5~ - 82)]v - (~n) p) ,-~1 v!(p - v)! 1"" +

and the last equality is to be considered only in a formal way, where the binomial expansion and division by p t should be applied first. Indeed, if q ~ 1 + N ® $ ~-2, then 5jq for j > 3 belongs to 1 + N ® S k-1 since #15j = 5~/q ; but elq will not necessarily belong to 1 + N ® S ~-1. Nevertheless, the relation p : l = ~152 implies that (51q)(82q) - 1 E Ker/t I = 1 + N ® S k-l ; hence 8152-1: I + N ® S k - 2 ~ I + N ® S k-1. Thus for every m e N ® S k-2 we have E m i l + N ® S k- 2 and f o r j > 3 L ~ sjEm = LEejm = sjm. Consequently (8.4a) ~m = LA*E(m) = (L51e~IE)(m) + 5s(m) - + ." + 5k(m) = =

(L815;I E)

+ A (m)

( m ) -- (51 -- 82) m -}- A ( m ) = 2 ( m )

where 2 = L515z- IE - (st - t2). Finally we show that 2 has the form given in (8.4). To this end we consider two commutative indeterminates t, s over a prime field GF(p) o f p elements. Let:

L ( E t . Es) = Q[t, y] + xVM, + yPM~

(8.4b)

where Q contains all monomials of degree at most p - 1 in t and the same in s and Mr, Ms contain the other terms. Let D = (d/dO be the formal derivation with respect to t, then note that D j p = 0 in a ring of characteristic p. Apply D on both sides of (8.4b) and obtain:

[ P-' (Et. Es-1)'.] DQ[t, s] + t'OM, + sPDM, = D L(EtEs)] = O ~, ( - 1)*- 1 1

"#

p-1

=

~ ( - 1 ) ' - l ( E t • Es - 1 ) ' - I D l E r • Es - 1]. 1

Now, D ( E t ) = E t - ( t P - l / ( p modulo ( F - x, sp):

- 1)!). Hence we obtain the following relation

p-1

DQ =- Y~ ( -

p-1 1)~-l(Et

" Es -

1 ) ~ - l E t • Es =

1

~, ( - 1 ) ' - I ( E t E s 1

=

1 -

(1 -

EtEs) p - 1.

1) "-1

19641

COMPLEXES OF RINGS

Next we use the relation, (u + v) v- 1 =

(u + v)p

153

~uV

u+t~

+ vp

~

U+t~

p~- I

uv/) p - I - v

v=o

(which holds in every ring of characteristic p), and the properties of E, to obtain that rood (t p- 1, s p) p-1

D Q = I - ( 1 - EtEs) p- I ~ I -

p-I

~, (Et" E s ) ' = 1 -

~, E(vt)" E(vs)

v=O

v=O

p-I

p-1

v=l

k,h=0

1- 1 + Z

Z

(vt)~ (vs)h

k!

hi

Z

t~s h p - t

~

E v ~+h ,=x "

But ]~ ] - J v k+h = ( m o d p ) only if k + h = 0 (p - 1). Thus, the last sum will contain possible non zero terms when k + h --- 0, p - 1, 2p - 1. The first is equal to 1 and the last is a term containing monomial of degree p - 1 in x. Hence tk $h

DQ = 1 +

~,

k~.h! mOd(tV-l, sV).

k+h=p-1

We actually have here an equality, since DQ contains only monomials of degree =< p - 2 in t and of degree = p - 1 in s. Hence, by integrating, it follows that tk+ 1 sk

Q= t+

~

k+h=p-1

(k + 1)!hi + f ( s )

and where f does not contain monomials in t. It follows immediately from the de finition of Q in (8.4b) that it must the symmetric in t and s, so we must have f(s) = a

1[

p-I

Q[t,s] = t + s +

v=l

v!~-~!

= t + , + ~ , (t + , ) " - t ' - s"

])

.

the last form of Q together with (8.4b) can be applied to our case, in the following way: set t = e , m , s = - e 2 m .

Since

(elm)V=(e2m)P=O,w e

have [ E ( e 2 m ) ] - l = E ( - t z m ) ,

and be (8.4b)

(Lele-~ XE)m = L[(e,IEm ) (f,2Em)-I] = L[

(E~Ira)e ( -- e2m)]

= Q[elm , -

e2m] p-1

= e l m - e,2m + Z ( e l m ) ( - e2m)p - ' • =1 v!(p-v)!

and this completes the proof of (8.4). Finally, we return to the computation of the groups of the complex given in (8.3):

154

S.A. AMITSUR

Note that it follows by the formula for 2, that for every n e N and a ~ sk-2, 2(n®a)=2(n)a p~N®S®I®'''®I, since e~(n®a)=8~n®a for i = 1 , 2 . This being true for all generators of N ® S k- 2 implies that the mapping 2 maps N ® S k - 2 into the sub-ring N ® S ® 1 ® ... ® 1 of N ® S k-1. Consider now the map t/: S - R which splits the R-map: R-+ S and extend it to a contraction map t/: S--+ S k-1 by setting ~l(al ® " . ® a k ) = ( - - 1 ) ~ - t a 1 ® " ' ® ak_t tl(ak). Then clearly ./ff maps N ® S k- 1 ._+ N ® S ~- 2 for k > 2; it does not affect the first two factors. One readily verifies that t/ei = ed/for i = 1,2, ...,k - 1 and r/ek -----( -- 1)k - t . Hence, ~/A - A r / = 1. Moreover, /~;t = + 2 and 2 ~/(m) = ~ 2(m) for every m ¢ N ® S ® 1 ® ... ® 1. From which we conclude what if b e N ® S k-2 is a cocycle, i.e., fib = (A + 2)b = 0, then b +

-

=

+ 4) -

(A +

=

-

(A +

is cohomologous to b o = ( t l 2 - 2 t l ) b e N ® S ® l ® . . . ® l . So if b e N ® S k-2 and k_>_3, we can choose in the class of n of Hk-Z(t/) a representative bo in N ® S ® I ® . . . ® I . But then again bov-Ol&-2tl)bo, and for these elements (t/~ - 2~/)bo = + 2bo - 2bo = 0, which proves that b ~ bo "" 0, i.e., Hk-2(dff) = 0 for k > 4. Hence 0 = Hk-2(Jff)---H k-2 ((1 +a~')*) ~ Hk-I(S/R), which completes the proof of lemma 8, and theorem 7.

Thus b

R.EFERENCES

1. S.A. Amitsur, Simple algebras and cohomology groups for arbitrary complexes, Trans. Amer. Math. Soc. 90 (1959), 73-112. 2. S. A. Amitsur, Homology groups and double complexes for arbitrary fields, J. Math. Soc. of Japan, 14 (1962), 1-25. 3. A.J. Berkson, On Amitsur's' complex and restricted Lie Algebras. Trans. Amer. Math. Soc. 109 (1963), 430-443. 4. O. Goldman, Determinants in projective modules, Nagoya Math. J. 18 (1961), 27-36. 5. A. Rosenberg and D. Zelinsky, Amitsur's complex for inseparable fields, Osaka Math. J. 14 (1962), 219-240. 6. N. Bourbaki, Alg~bre, Ch. 8 Herman, Paris (1958). Tins HEBREWUNIVERSITYOF JERUSALEM AND NORTHWESTERNUNIVERSITY,EVANSTON,ILIJNOIS

ON THE MINIMAL BASIS OF A COMPLETELY SEPARATING M A T R I X G) BY

JACQUELINE SHALHEVET ABSTRACT

We prove that there is essentially only onep × 2s incidence matrix satisfying a given separation condition, which is of minimal degree, and we find that matrix. Introduction. A matrix (m~) whose entries are either 0 or 1 is called completely separating if for every pair of columns Jl, J2 there are two rows il, i2 such that m~:= m/22 = 0 and m/: = m t 2j1__1. In [2] M. Maschler and B. Peleg proved that the degree of such a matrix of n columns is > '~n where ;t~ = 2 + [ l o g 2 ( n - 1/2)] and gave an example of a completely separating matrix of n columns whose degree is precisely 2~. In this paper we offer a different proof of the above result, and in addition we show that for n = 2' the example given in 1-2] is the only matrix of minimal degree, up to addition of superfluous columns. This combinatorial problem, in addition to its intrinsic interest, may be useful in studying the properties of those kernels which have a maximal dimension. 1. Definitions and Notation. DEFINITION 1.1. A matrix M p×n = (m/) of p rows and n columns is called a completely separating incidence matrix (c.s.i.m.) if m{ = 0 or 1 for all i = 1,..., p; i = 1,..., n, and if for every pair of columns m jl , m y~ there exists a pair of rows ms:, m~ such that m { ~ = m i2 y ~ = I and m y~ il = m[~ = O. DEFINITION 1.2. A matrix B q×~ =(b{) is called a completely separating incidence basis (c.s.i.b.) if b{ = 0 or 1, i = 1, ...,q a n d j = 1, ...,n and if there exists some completely separating incident matrix M p×n for which B q×~ is a basis. DEFINITION 1.3. Bq×~is called a minimal completely separating incidence basis if it is a c.s.i.b, and if B ~' ×~ is any other c.s.i.b., then q' > q. DEFXNITION1.4. A matrix B ~×~ will be said to satisfy a 2 condition if any two rows of B have at most 2~-2identical components; i.e. if bit , b~2 are any 2 rows o f n then the set J = {j: b{, = b:2} has at most 2~-~ components. DEFINITION 1.5.A matrix B q×2,= B will be said to satisfy a O-condition if every row of B has at most 2"- ~ zero components. Received October 5, 1964. (1) This work is part of the author's doctoral thesis, being written under the supervision of Dr. M. Maschler, at the Hebrew University. 155

156

JACQUELINE SHALHEVET

[September

NOTATION. 1 . 6 - We shall denote the ith row of the matrix B q×~= (bD by bt and the j t h column by bJ. 1.7 - - We shall denote by A "the set of all the 2' possible column vectors of length s whose components are either zero or one. Thus a 2 =

{(1)1, 00. ( 1, ) (10 ), ( 0 ) }

1 . 8 - We shall denote by Ba<*+1)×2" = (bD the following matrix: bi = (1, ..., 1, 0, ..-,0, ..., 1, ..., 1,0, ... ,0) for i =. 1, ..., s where we have 2 *-I ones followed by 2 "-~ zeroes, repeated 2~-t times, and b~+l = 1 for all j. For example, if s = 3, B2 ~ 8 is the matrix 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1.9 - - We shall denote by B(2s+1)×2" the matrix whose first s rows are identical to the first s rows of B( ~+1)×2" and whose last row b~+t = (0,1,0,1, ..-, 0,1,0, 1); 2j = 1 , j = 1,2, ...,2 '-1. i.e., ,,s+l-2J-11= 0, b,+l 1.10 ~ We shall write B ,,, C if the matrix C can be obtained from the matrix B by column and row permutations. In the following section we prove that the degree of a minimal c.s.i.b, with n = 2' columns is s + 1. In section 4 we determine the degree of a minimal c.s.i.b. for any n. We also prove that for n = 2 ~ columns there is only one c.s.i.m. M of minimal degree, which is itself minimal in the sense that no proper subset of rows of M is completely separating, and we characterize that matrix completely.

2. Properties of a Completely Separating Basis. LEMMA 2.1. Let bJl and b J2 be any two columns of a c.s.i.b. B =- B qxn. Then the vector sum (b ~1) + (b ~2) is n o t a column orB. Proof by contradiction. B is a basis of a c.s.i.m. M; let b Jl, b j2, b j3 be three columns of B such that (b jl) + (b j2) = (b J3). Then b{~= 1 ~-b{~= 1 for all i = 1,..., q. Since M is completely separating and B is its basis, there exists a row vector m k = r , , c ~ b , = ( m l , . . . , m ~ M such that mkj2 = 1 and m~~ = 0 . But m~~ + m~" = ~ c~(b[~ + b~~) = ~,~ c~b~3 = m~3 = 0. Therefore m ~ ' = - 1 contrary to definition of M as an incidence matrix. ILEUMA 2.2. Let B ~Xn = B be a c.s.i.b. Then (I) no two columns of B are identical and (2) no column of B is identically O.

1964]

MINIMAL BASIS OF A COMPLETELY SEPARATING MATRIX

157

Proof by contradiction. B is a basis of a c.s.i.m.M. (1) Suppose (b s) =- (b~), j ~ k. Then (m j) =---(mS), j ~= k are two columns o f M, contrary to the definition of M as completely separating. (2) Suppose (0,...,0)'E B. Then (0, ...,0)' is a column of M contrary to the definition of a c.s.i.m. L E n A 2.3. Let B q×z" = B be a c.s.i.b. Then q >=s + 1. Proof. Suppose q < s. Consider Aq = set of 2 q < 2 s different possible columns of length q. Since B has 2 s columns, it must have two identical columns, contrary to lemma 2.2. Suppose q = s. Then 2 q = 2 ~. Therefore either B contains two identical columns or it contains all the 2 s columns of A s. But (0,--.,0)'~AS; therefore we have a contradiction to lemma 2.2. Thus q > s + 1. LEMMA 2.4. B~(s+l)×2s, i = 1,2 (see notation 1.8) are completely separating incidence bases. Proof. Consider B~S+l)×2( Define the matrix M ( 2 S + l ) × 2 ~ = M = ( m ~ ) by m~ = bi, i = 1,..., s + 1. ms+ t +~ = bs÷ l - b~, i = 1,..., s. The rows of B~*+ 1) x 2s are linearly independent. Indeed, suppose there exist c~ such that ~,,c~b~ = (0, ...,0). Then since B~t~+ ~)×2s contains every possible column vector of length s + 1 whose last component is one, and whose other components are either zero or one, we have: c~+cs+l = c i + c j + c s + l = O f o r a l l j = 2 , . . . , s , and a l l i ~ j , s + l . Therefore c; = 0 f o r j = 2 , . . . , s , and c~+1 = 0 = Cl. Obviously B is a basis of M. Let m J~, m J~ be any two columns of M. Since no two columns of B are identical, there exists some row bio = mio in which miJ~ = 1 and mioJ2_- 0, (or mio~= 0; and mJ~io= 1), io =< s + 1. Therefore m s+l+io j~ =l-m/J

~---

0 and m sj~ +l+io

Therefore M is completely separating. Bt2~+1)×2s is also a basis of the above defined M. are completely separating bases.

=1

~

mio

J ~- -- l .

Therefore

B}s+t)×2s, i

=

1,2

LEMMA 2.5. I f B q×2s is a m i n i m a l c.s.i.b., then q = s + 1. The proof follows immediately from the two preceding lemmas. [,EMMA 2.6. Let the incidence c.s.i.m. M
matrix B(S+l)×2S=_B= ( b / ) Then

m=

be a basis o f the ~ i c i b l e M = : , c i = O , 1 or - 1 for

Proof. Let B, be the matrix obtained from B by deleting row b~. Let (bP)t = b;_ 1, b~+t, "")' ; i.e., the pth column of Bt. We distinguish two cases: Case (1): B~ has no two identical columns; thus all 2 ~ different columns of A s belong to B t. In particular (bP')t=(O ...,0)' for some Pi. Therefore, by

158

JACQUELINE SHALHEVET

[September

Lemma 2.2, (O,...,O,l,0,...,O)'=b p~. Let m k = ~ , , c , b ~ = ( m k t , . . . , m 2 " ) e M . m~'= ~,,csb~ ~= c~b~'= c~. Therefore, since M is an incidence matrix, c~ is equal to 0 or 1. CASE (2). B~ has two identical columns, say (bP')z = (bq')z, Pi ~ q~. By Lemma 2.2 we can assume that b~"= 1, bT' =0. Let m k . .(m~, . . ,mk2o) = Es csb~eM. Since m ~ = 0 or 1 for all j = l , . . . , 2 s we have I m : ' - m e ' l = 0 or 1. But [ m r ' - m~'} = [ Y~scs(b~'I = Ic,(bp- b~') l =}cil = 0 or 1. Therefore c, = 0 , 1 or - 1 . LEMMA 2.7. Let B (s+l)×2s -- B be any matrix containing two row vectors b~, bj whose sum is the unit vector. Let B~ be the matrix obtained from B by deleting the row vector b~. If no two columns of B z are identical, then B ,~ B(2s+l)x2s. See 1.10). Proof. The 2~ columns of Bt comprise the set As (See 1.7) because no two columns are identical. Thus appropriate row and column permutation will bring B into the form B (s+l)x2s . The most difficultpart of this work is TI-IEOREM 2.8. B (~+1)×2~ , i = 1,2, and those matrices obtained from B~ (~+~)~2s

by row and column permutations, are the o n l y m i n i m a l c.s.i.b, having n = 2~ columns. Since the proof of this theorem begins in this section and continues in section 4, we shall first give an outline of the proof. We restrict ourselves to those c.s.i.b, which satisfy a 0-condition and a 2-condition, this involves no loss of generality, because we shall prove that any c.s.i.b. having 2 s columns must satisfy these conditions. Under this restriction we consider the following cases, where in each case B s+l)x2s = B is a c.s.i.b.: Case a. The unit row vector (1,... 1)eB. (2) B ,-, Btxs+ 1) ×2'

(I_emma 2.9)

Case b. The unit column vector (1,... 1)' e B. B ,,,B(1~+ I)~ 2~ (I.emma 2.10) Case c. There exists a row vector bl e B such that ~,~b/= 2 s-t. B ,,,B~ ~+ i)× 2~ for i = I or 2 (Theorem 2.8, part B) Case d. There exists a row vector b~ e B such that ~ b / < 2 s- i This case cannot occur. (Theorem 2.8, part A) Case e. There exists a row vector b~eB such that ~ b / > This case cannot occur. (Theorem 2.8, part E)

2 s-x

(2) W e shallwriteb k ~ B ifb k is a row vector in the matrix B, and similarlybkE B if bk is column vector in B.

1964]

MINIMAL BASIS OF A COMPLETELY SEPARATING MATRIX

LEMMA 2.9. I f B t S + l ) × 2 S - B is a n y c.s.i.b, containing the u n i t row (1,-.-, 1), then B~s+ l)×zs ~ B.

159 vector

Proof. Permute rows o f B so that (1, ..., 1) is the last row. B contains 2 ~different columns, all o f which belong to A '+1. But A '+1 has exactly 2 s columns whose last c o m p o n e n t s is one. Therefore B contains exactly those 2 s columns. Similarly B~~+ 1)× 2 s contains the same 2 ~ columns. Therefore B~S+1~× 2 s " ~ B. LEMMA 2.10. I f B (s+l)×2s - B is a c.s.i.b, satisfying a O-condition (Def. 1.5) and containing the unit column vector (1, ..., 1)', then B ~ B~S+)~ 2 s Proof. W i t h o u t loss o f generality we can assume that b l = ( 1 , . . . , 1 ) ' e B . Then b k ~ B = ~ b 1 - b k ~ B ( L e m m a 2.1). But A s+l is composed o f 2 s pairs of columns o f the type b k, b 1 - b k. Thus B contains exactly one of each pair; i.e., b k ~. B'¢~ b 1 - b k ~ B for all b ke A s+ 1. B is a basis o f some completely separating M. Therefore, for any fixed j, j ¢ 1, there exists an m, = (m~, ..., m 2~) 1 ~"~s + 1 = "Eicib,~M such that mt = 0 = ,..,i=lci and m ~ = 1 for some j ~ l . We shall establish three propositions: PROPOSITION I. There exist io, Jo such that Cio = 1, Cjo = - 1, ci = 0 for all i ~ i o , Jo. Indeed, there exist i o, Jo such that Cio = 1, cjo = - 1, because ~ i c i = 0, some c i ~ O, and all c i = 0, 1 or - 1 (Lemma 2.7). Suppose proposition I is not true. Then there exists ci, -- 1, ii ~ io (or there exists ci, -- - 1, j ~ Jo). F o r simplicity permute rows so that io = 1, Jo = 2, i~ = 3. Let b k -- (1,0, 1,0,0, ...,0,0). Then b t - b ~ = (0,1,0,1, 1,-.-, 1, 1). b k E B =~ m k = c 1 + c a = 2.

bl--bkeB=~mk=

~., i~l,

ci = 3

~ ci--cl--c3=0--2=--2. i

But either b k o r b ~ - b k must belong to B, and in either case we get a contradiction since M is an incidence matrix. A similar argument shows there does not exist cj~ = - 1 , j 1 ~ J o . PROPOSITION II. B contains 2 s- 1 columns b k such that big = 1 and bko = 0, where io, Jo are as defined above. Let a k be any o f the 2 -1

column vectors in A s- l, such that ako = 1 and a k = 0.

Then a k ~ B (because a k e B ~ i n k = Cyo = -- 1). Therefore all o f the 2 ~-1 columns o f form 1 - a k = b k, where bjko = 0 and b~o = 1, belong to B. PROPOSITION I I I . bio = (1,..., 1) ~ B. By Proposition II, bjo has at least 2 ~- ~ zeroes. By the 0-condition satisfied by B, bjo has at most 2 ~- 1 zeroes. Therefore bjo has exactly 2~- ~ zeroes. I.e., there

160

JACQUELINE SHALHEVET

[September

exist exactly 2 s- ~ columns in B such that bko = 1, and therefore in these columns k k b~k=l; there also exist 2 s-1 columns b k such that bjo = 0 and b~o-1. I.e., bio = (1,..-, 1). P r o o f of L e m m a

2.10. Since (1, ..., 1)e B, B ,-, Bits+ t)×2 s . ( L e m m a 2.9).

L e m m a 2.11. I f B (s+l)×2s = B is a c.s.i.b, satisfying the 2 condition and the 0-condition (Def. 1.4-5) and if (1,--., 1) ¢ B and if B contains some column vector which is everywhere zero except in one component, then B ~ B2 is+ 1) × 2s Proof. Without loss of generality, let b 1 = ( 1 , 0 , 0 , - . . , 0 ) ' e B . Let a k be any column o f A s+l for which a k = 1. Let a k*= a k - b 1. Then, by L e m m a 2.1, ak~.B .~ak*~B. Let B] be the matrix obtained from B by deleting row 1 of B. Then since B~ has no two identical columns, it contains all 2 s columns of A s, and in particular (1,..., 1)' e B~" ; therefore b j° = (0, 1,1,..., 1)' e B, for some Jo, since (1,.-., 1) ¢ B (1,-.., 1)' c B . ( L e m m a 2.10). We will prove b~ = (1, . . . , 1 ) - bk, which will complete the proof, applying L e m m a 2.7. We distinguish two cases. Case (1). There exists a column b p :~ b y° = (0, 1, ..., 1)', b g e B s u c h t h a t b~' = 0. Case (2). b~ -- 1, all p # J o . Case (1). Since B is the basis of a completely separating M, there exists 2s mR = ( m ~ , . . . , m R ) = ]~eib i e M such that m~ = 1 and m~° = 0. We shall prove three propositions:

PROPOSITION. I. e I = 1. F r o m the beginning o f the p r o o f of this lemma, we know that there exists (bq)~ ebb" s u c h t h a t b f + bfl= 1, all i # 1. But m~° = Z, eib~ ° = Y~+le2 i - 0, and m~ = ]~+1 e,b~ = z'~2CiViVs+lLp= 1. Therefore ~s2+l cib~= - 1. But r n ~ = Z ] -1 c,b q , = - l + c ~ b ~ = O or 1. Therefore elb ~ = 1 or 2; i.e., b~ -- 1 and e 1 = 1 or 2. But (1,0, . . . , O ) ' e B :~ m~ = e I = 0 or 1. Therefore c a = 1. PROPOSITION II. There exists exactly one Cio which is equal to - 1. Obviously there exists at least one Cio = - 1. Suppose eio = ci, = - 1, io # it. Since n~ contains all the columns of A s, there exists (b k) ] G e for which b~o = b~, = 1 and b~ = 0, all i # i o, il, 1. m tR= ClblR + Ciobiko + ci,b k = b k -

kbio-b k = b k - 2 < 0 ,

because b k = 0 or 1. But m k = 0 or 1 and we have a contradiction. PROPOSITION III. b I = (1,..., 1) - bko for some ko, 1 < ko < s + 1. Indeed, i=2 e i = O a n d c i o = - l , 2
1964]

MINIMAL BASIS OF A COMPLETELY SEPARATING MATRIX

161

there exists a k o such that Cko=l, 2 < k o < s + l , and c ~ = 0 , i # l , Since B2 contains all the 2 ~ columns o f A ' we know that there exist:

io, ko.

a) 2 s-z columns bke B such that bko = 1 and b~o = 0 b)

. . . . . . . .

btok = 0

c)

. . . . . . . .

b~ko = 1 and b~o = 1

d)

. . . . . . . .

bko = 0

In case (a) m,k = clbkt + c,ob,ko = b t -

b ko =

1

b~o = O.

1 =

0 or 1 ~, b] = 1.

=

0 or 1 ~, b] = O.

(b) m,k = cxb] +Ckobkko = b k + l

Therefore rows bio and b~ have at least 2 ' - x identical components, and since B satisfies a 2-condition they have at most T - ~ identical components. Therefore in case (c) b/ko = 1 ~ b] = 0 (d) b,ko = O # b ]

= 1.

Therefore bko + b I = (1,..., 1).

Case(2). Consider somecolumn (bP). Thereexists(bq)7 eB; suchthat(bP)] +(bq)2 2s = (1, ..., 1)'. There exists m k = ~,c~bi = (m~, ..., mk ) e M such that m~ = 1 and m ~ = O. m~ = Zc,b] = c,b a = c, = 1. s+ l

m~=O=

s+ l

s+ l

]~ eib~+cabPt= Y. c,b~ + 1 ~ 2

2

s+l

]~ e i b ~ = - l . 2

s+l

ct(bl~+b~ = 2

]E c ~ = m j ° = O

or 1.

2

Therefore Z "+t2 c~b7 = 1 or 2, and ]~+lctbiq=clb~+ Z~+lcib~ = m~ = 2 or 3. Thus we get a contradiction since M is an incidence matrix, and Case (2) cannot occur. 3. Inequalities. We now list a few inequalities involving integers which are needed to complete the p r o o f of theorem 2.8. The proofs are simple and will be omitted. LEMMA 3.1. I f O <

( 2p;k]<22P+~for

are integers, a n d i f ( k - 2+r )\ 2v T <'2I p=

some P = P o ,

where p, k and r

k + 2, t h e n ( 2P a +l r k )l < p22~+s + for

P~Po.

Proof. By induction on p. LEMMA 3.2. If q, k are integers and a = 0 or a = 1, then q(q - 1) + (k - q) (k - q - a) >= k(k - a - 1)/2. l f a = 0 equality holds if and only if q = [ ( k + 1)/2].

162

JACQUELINE SHALHEVET

[September

I f a = 1 equality holds if and if q = k/2. LEMMA 3.3. I f q, k are integers then ( q - l ) 2 + ( k - q + l ) (k-q-a) > k ( k - a - 1)/2) f o r a = 0 and all q, and f o r a = 1 and all q v~ (k + 1)/2. I f a = 0 equality holds if and only if q = I-(k+2)/2]. I f a = 1 equality holds if and only if q = k / 2 or q = ( k / 2 ) + l. For a = l, q = ( k + l)/2, ( q - l ) 2 + ( k - q + l ) (k - q - 1) = {k(k - 2) - 1}/2.

4. Dimension and characterization ot minimal completely separating bases and matrices. We shall complete the p r o o f o f theorem 2.8 b y induction, in this section. Before proceeding, however, we must first m a k e use of the induction hypothesis in order to generalize L e m m a 2.5 to matrices having n columns, where n is not necessarily a p o w e r o f 2. LEMMA 4.1. Let s be a f i x e d positive integer. I f it is true that B/(s+l)×2s, and those matrices obtained by p e r m u t i n g the rows and columns of B, (s+l)x2s , i = 1 or 2, are the o n l y m i n i m a l completely separating incidence bases f o r a m a t r i x having 2 ~ columns, and if B ~ ×" is a m i n i m a l c.s.i.b, f o r n, 2 ~ < n < 2 s+l, then q =s+2. Proof. Obviously q < s + 2. Indeed by L e m m a 2.4, Bi t~+ 1)× 2s is a c.s.i.b.; hence any restriction of Bi(s+2)× 2s+ 1 to n columns is a c.s.i.b., i = 1 or 2. It suffices to prove q > s + 1 for n ~ = 2 ~ + 1, since were there a c.s.i.b. B(S+ 1)x (2S+k)for any k > 1, a restriction of this matrix to 2 ~ + 1 columns would be completely separating for k = 1. Suppose B - B q x ( 2 s + l ) is a c.s.i.b, and q < s + 1. Let b~eB, b~ ~ (1, 1,..., 1). Then b/1 = 1, b~"2 = 0 for some J r , J 2 . Let B* be the matrix obtained from B by deleting column J l . Then B* has q rows and 2 ~ columns, where q __<s + I; hence it is a minimal c.s.i.b. Therefore if the only minimal c.s.i.b, for n = 2 ~ are permutations of B~ (~+1)×2~, then B* must be such a permutation. Therefore, any row of B* not identically one has exactly 2 ~-1 ones and 2 ~-1 zeroes. Thus the ith row of B has 2 ~- 1 + 1 ones and 2 ~- 1 zeroes (since b{ 1 = 1). Similarly, if we delete column J 2 , w e find that the ith row of B has 2 s- 1 ones and 2 ~- 1+ 1 zeroes (since b,j~ = 0), and we arrive at a contradiction, thereby proving that q = s + 2. LEMMA 4.2. Let B ¢×~ by a c.s.i.b. Then if n > 2 ~, q > s + 2. T h e proof is trivial and will be omitted. We shall now complete the p r o o f o f theorem 2.8 by induction on s. F o r s = 1, the only possible row vectors of a basis are (1, 1), (0, 1), and (1, 0), and any two ~2x2 such vectors f o r m a minimal basis of the form ~J~ , i -- 1, 2. Suppose the theorem is true for matrices having 2 t columns, t < s. We shall prove the theorem for matrices having 2 ~ columns, dividing the p r o o f into five parts; PARTA. A n y c . s . i . b . B (~+1)×2~ - B satisfies b o t h the 0-condition and the 2 condition. (See Definitions 1.4 and 1.5).

1964]

NIMIMAL BASIS OF A COMPLETELY SEPARATING MATRIX

163

Proof of Part A. Suppose B does not satisfy the 0-condition. Then, without loss of generality we may assume that there exists a row bi in B such that b / = 0 for all j < 2 s - t + k , 0 < k < 2 s - l , a n d b / = l for all j > 2 ~ - l + k . B i s a basis of a c.s.i.m.M. Let B* be the matrix obtained by restricting B to the first 2 ~- a + k coluumns, with the ith row deleted. Let M* be the matrix obtained by restricting M to the first 2 ~- a + k columns. Then B* is a c.s.i.b, of M* having the dimensions s x (2s- 1 + k) which, by the induction hypothesis and Lemma 4.2, is impossible. Suppose B does not satisfy the 2-condition. Then, without loss of generality we may assume that there exists 2 row vectors bl, b2 such that b / = b~ for j = 1,...,2 ~-1 + p , p > 0 . Let B* be obtained by restricting B to the first 2 s- 1 + p columns, with the first row deleted. Let M* be obtained by restrincting M to the first 2s- t + p columns. Then B* is a c.s.i.b. (of M*) of dimension (s) x (2~-1 + p), which, by the induction hypothesis and Lemma 4.2, is impossible. Therefore B satisfies both the 0-condition and the 2-condition. PART B. I f B (~+l)x2s = B is a c.s.i.b, and if there is a bi~B such that bi has exactly 2~-t components equal to zero, B ~ B~(*+ x)× zs, i = 1, 2. Proof of part B. Without loss of generality we may assume that bl e B and 1 j > 2~- 1

Let B* be obtainedby restricting B to the first 2~- 1 columns

with the first row deleted. Let M* be obtained by restricting M to the first 2 s- 1columns. Then B* is a c.s.i.b, of dimension s x 2 -a, and therefore by the induction hypothesis, B* ~ B~×2 s - ' , i = 1 or 2. Therefore there exists a column vector in B* which is everywhere zero except in one component which component is equal to one. Therefore there is also a column vector in B which is everywhere zero except in one component, which component is equal to one. Thus by Lemmas 2.9 and 2.11, B B}s+l)x2s, i = 1 or 2. ~

PARTC. Let B - B (~+l)×2s be a basis of a c . s . i . m . M . If there exists a row vector b~oeB such that 2s> ] ~ i b / > 2 *-x, then 2 " > ] ~ j b { > T -x for all 2s i = 1,...,s + 1, and if mk =(m~,...,mk )eM then 2 ~> ~,jm~> 2 s-x. Proof of Part C. Suppose there exists a b,o ~ B such that 2 s > ]~j b~ > 2 ~- t. Xj bj > 2~- 1 for every i, by part A. If ]~y b] = 2 ~- x or 2 ~ for some i, then by Part B and Lamma 2.9 we know that B ~ B~s+x)×2" , i = 1 or 2 and then for each i, including io, ~-,jbj, = 2 *-i or 2 , contrary to our assumption. Therefore 2 ' > ~,jb/> 2 ~-a for every i. Let mk= XZicib,=(m~,'",rn2kS)~M, ink# bio. Then there exists a Jo, Jo # io,

164

JACQUELINE SHALHEVET

[September

such that cj~ ~ O, and {bl,...,bjo_ t, mk, bjo+l,...,bs+2) is also a c.s.l.b, containing bio. Therefore by the first half of this proof, 2 s > ~ j m ~ > 2 s- 2 PART D. If B - B C~+1~× 2s is a c.s.i.b, of a c.s.i.m. M and if there exists a b~ E B such that 2 ~ > ~ j b[ > 2 ~- x then there is an m k 6 M, such that m k -- ~,icib~ where c2=-land Z, c i = 0 , 1 o r 2 . P r o o f of Part D. ( 1 , 0 , . . . , 0 ) ' ¢ B and ( 0 , 0 , . . . , 0 ) ' CB, L e m m a s 2.2, 2.9 and 2.11. Let B* be obtained by deleting the first row of B. B* zb A s since (0, ..., 0)' ¢ B*, and therefore B* has two identical columns (bJ') * = (bJ2) *. Since by L e m m a 2.2 B does not have two identical columns, we m a y assume that btJ~= 1, bxJ' = 0. By the definition of a completely separating matrix, there must exist a row m k ~ M where m k = ~,qbi with m ~ ' = 0, and mkj 2 = 1. Consequently m ~ ' - m~ 2= - 1 = ~ , c , ( b / ' - b/~) = c a . By L e m m a s 2.10 and 2.2, (1, ..., 1)' CB and (0, ...,0)' q~B. Therefore, there must be some pair of columns b p and b q, both in B, whose sum is the unit vector, for if not we would have in B, exactly one column o f each o f the 2 ~ such pairs. But we have exhibited one such pair, namely (1, ..., 1)' and (0, ...,0)',lneither of which is in B. It follows that ]~ic~=0, 1 or 2 since mk = 0 o r 1 for every j, and m ~ + m q = ~,ci(b~ + b~) = ~2ici. PART E. I f B ~'+2)×2~ = B is a basis of a c.s.i.m. M then for any b ~ B and B ~ B,(~+1)×2~, i = 1 or 2.

~,jb/= 2 ~-2 or 2 ~

P r o o f of P a r t E. (by contradiction). Suppose there exists a b~e B such that ]~j b{ ~ 2 s- 2, and Y_,jb{ ~ 2 ~. We k n o w ]~j b{ > 2 ' - 2 (Part A, by the 0-condition) 2 2~ Therefore 2 ~> ]~j b / > 2 ~- 2. Then there exists an m~ = ]~j cjbj = ( m , , ..., m o ) e M such that 2 ~ > ]~j m{ > T - 2 and c2 = - 1, ~ , ci = 0, 1 or 2 (by Parts C and D). Thus there must be more than 2 ~- 2 columns b p in B for which ]Ei ct b~' = moU-- 1. We shall prove that there are at most 2 ~-~ such columns. Before proceeding, we shall first give an example. EXAUPLF. Let ]~ic~ = 1, and let there be only one ci which is equal to - 1 . Without loss of generality we m a y assume that c2 = - 1, c2 = ca = 1 and c~ = 0 for i > 3. Let b p be a column in B. Then ~,~cib~ = 0 or 1. I f VZ~c,b~ = 1, the first three c o m p o n e n t s of b p must be as in, one of the following three cases: (1) b p = ( 1 1 1 ...)', (2) b ~ = ( 0 1 0 ..-)', or (3) b p = ( O 0 1 . . . ) ' and if Z~cibf=O, the first three components must be as in: (4) b ~ = ( 0 0 0 ...)', (5)b p = (1 1 0 ... )' or (6) b ~ = (1 0 1 ...)'. We shall say that a column is of type i if and only if its first three components are as in case (i). Suppose B has t~ columns o f type i, i = 1,... 6. (1.1) t~ < 2 s-2 for all i; since each column type has three fixed components, a n d the remaining s - 2 components m a y be either 0 or 1.

19641

MINIMAL BASIS OF A COMPLETELY SEPARATING MATRIX

165

(1.2) ~E~t~ = 2*. The matrix B has the following form:

B =

bi

1...0...0...0.-.1...1...

¢1=--1

b2

1...1...0...0...1...0...

e2=l

ba

1...0...1..,0...0...1...

c3 = 1

bs+ 1 ~Ec~bi = my =

•

•

•

•

•

•

•

,

•

,

•

•

•

•

•

°

•

°

Ci = 0

(1...1.-.1...0...0...0...)

i

where each column type (i) appears t~ times. Thus the nunmber of components in rows bl and b2 which are identical is tl + t3 + t4 + ts ; the number of components in rows b 1 and b 3 which are identical is t 1 + t2 + t4 + t6. By Part A, the 2-condition, we find that 2t 1 + t2 + t3 ÷ 2t4 + ts + t6 ~ 2 s. Together with equation (1.2) this gives tl = t4 = 0. Using inequality (1.1) we find that there are at most t2 + ta < 2 s-1 columns bp in B such that ~E,cib/'= 1, contradictory to our assumption that Z j m{ > 2 ' - 1. We now proceed to the proof of part E. We may assume, without loss of genenerality, that the rows of B are so ordered that c, = - 1 for 1 < i < h, c, = 1 for h h + k . Let I i = { i : c ~ = j }, I P = { i : b [ = l } . Let I A I denote the number of elements in the set A. By Lemma 2.6 and part D of this theorem, 1/_1 [ = h # 0, 111 [ = k >_-h and [Ij [ = 0 i f j ~ 0, 1, - i. Let X be the set of all possible column vectors ~J of length s ÷ 1, satisfying (a) ~[ = 0 or 1 for 1 _< i -< s + 1, and (b) ~i ~i '= 0 or 1. The columns of B form a proper subset of X. We shall define a partition of X into equivalence classes called types; two columns ctp, ~t in X belong to the same type if and only if 0t~' = ~ for all i ~ 11UI_ 1. This is obviously an equivalence relation. Let A = {7} be the family of types. We shall now partition A into two equivalence classes Ao and A1, where A i = { ~ : ~ A and if ~Vis a representative of type ct, then ~ j ej~ff = i}. This definition is independent of the choice of a representative, for if ~P and t are both of type ~, then ~jej~j = ~jcj~ i. AortA1 = ~ , and A 0 U A 1 = A, since by definition ~Ej c j ~ = 0 or 1. If ~ ' ~ A o then there exists an integer q, 1 _-
166

JACQUELINE SHALHEVET

[September

independent of the choice of representative, for if gP and ~ tboth belonge to the class ~, IP=I t. The sets A(q,i), l=
columns i ~ X which are of type g is (1.6)Ig[ = 2s+l-O'+k)" We shall denote by B 1 the set of columns b P 6 B for winch ~.,cib~ = m ~ - - 1. Obviously B1 -- {gP: gP is a representative of~, ~x~A(q, 1) for some q, 1 __
type. Let t, be the number of columns of type a which are in the matrix B. Consider any pair of row vectors bj, bw in B such that j e I_ 1, w e 11. If by = b~ for some column b p e B, then by = b~ for every column b" in B of the same type as bp. Thus we may define the set C,,~ of all the types a for which the jth and wth cornP ponents of any column of type a are equal. Thus C,,~ _- {~.• b~P _ _- b~, if b p is of types}. By part A, the 2-condition, we find that the number of identical components in rows bj and b,, is (1.8)

Y~ t,-<_2 ~-1. ECwj

Summing over all kh pairs (w,j), we arrive at

]E

(1.9)

well jet-1

~. t~= E a~t~< kh2 s-I ~eCwj

cteA

where a~ simply denotes the numerical coefficientof t~ in the expansion. The total number of columns in B is (1.10)

]~ t, = 2 s. ~teA

For any ~, a~ is actually the number of pairs (w,j) for which ~ e C~,~. Let ~ ~ A(q, i) and let b p be a representative of ~. Then ~t e C~j if and only ff " b~, P = b~. P There are P__ exactly (q - 1)(q - 1 + i) pairs (w,j) such that bg = b i - 1 and (k - q + 1 - i) (h - q + 1) pairs such that b~ = bff = 0. Thus, for any q. (1.11) (1.12)1

a,=q(q-1)+(k-q)(h-q+l) a,=(q-1)

2+(k-q+l)(h-q+l)

if~a(q,1) if~eA(q,0).

We shall distinguish three cases: q-1

Z ~ ( q _ l ) ( q ) = ( kk2 k l k

_

) < 2 2 k - 2 ( L e m m a 3 . 1 ) ( S e e [ 1 ] p . 48). Therefore

I Ba [ <= 2s- ~ (Equation 1.7) contrary to the assumption that 1~, m~ > 2 ' - t.

1964]

MINIMAL BASIS OF A COMPLETELY SEPARATING MATRIX

167

Case (2). ~ici = 1. Here h = k - 1 and equations (1.11) and (1.12) become: a~=q(q-1)+(k-q)2 i f 0 t s A ( q , 1) and a ~ = ( q - 1 ) 2 + ( k - q + l ) ( k - q ) if c~e A (q, 0). By Lemmas 3.2 - 3, a~ a~ =

2

>___k(~_- 1) for all c~e A, while for e E A (q, 1),

if and only if q =

. Using equation (1.10) we find that

~ , ~ a a ~ t ~ > k ( k - 1 ) 2 ~-1 which, together with (1.9) means that ~ A a ~ t ~ = =k(k-1)2

~-1

and thus if e s A ( q , 1),

. Consequently if b~eBx, bp must be of type e, e e A ( q , 1). If k is

q =

even, then q = ~ - - a n d l A

andl l

a ~ - k ( k2- l !

Therefore t ~ ¢ 0 ~

= 2 s+l-(2k-1)

tion that

~,pmPv > k + 1

, 1 l=

< 2 2k-a (Lemma 3.1),

Therefore B~ < 2 ~-x contrary to the assump(k + 1) ~k+l' 2 ~-1. If k is odd, q 2 and I A ( 1 ) = 2 s+2-2k

< 2 2k-a 0-emma

3.1),

1 1---2

and IB I 2

which, as above, is a contradiction. Case (3). ]~,c~ = 2. In this case h = k - 2 and equations (1.11) and (1.12) become a ~ = q ( q - 1 ) + ( k - q - 1 ) ( k - q ) if ~ A ( q , 1) and a ~ = ( q - 1 ) z + + (k - q - 1) (k - q + 1) if ~ e A(q, 0). For k even, a~ > k(k - 2)an d if ~ ~ A(q, 1) = 2 k equality holds if and only if q = - ~ (Lemmas 3.2-3.) Thus t~ ~ 0 and

e~A(q, 1)~a~-~~eeA < 2 2k-4(Lemma 3.1), and I~l

--~,1

. A

= 2 s+l-(2k-2)=

-~,1 2

s-2k+3

= __k _ 1

--k

=

2 2 Therefore I B 1 1 < 2 ~-1.

If k is odd a, > ~ k ( k - 2) for ~ E A (q, 1). Therefore a, - 1 > k(k2- 2)

21 for

e A (q, 1). Also a~ > k(k - 22) - 1 if ~ ~ A (q, 0), by Lemmas 3.2-3. Consequently ~A1

[a~--l]

t~+ ~,~Aoa~t~ > k ( k - 2 ) - I = 2

. 2s"

But

k(k - 2)2 -1

=

[k(k - 2) - 1] . 2s + 2~_1, and by equation (1.9) ~,,~aa,t, < k(k - 2)2 '-1. 2 = Therefore E , ~A, t, < 2 ~- a, and [ B~ I --< 2~- ~, which contradicts the assumption that Zp m~ > 2 - 1

168

JACQUELINE SHALHEVET

[September

We have proved in each case that the assumption that there exists a b~e B such that ~y b{ ~ 2 s-~ and ]~j b / ~ 2 s leads to a contradiction, completing the p r o o f of part E. To conclude the proof of the theorem we note that since there is only one row vector b~, namely the unit vector, for which ]~j b / = 2 s, there must be a vector b~ in B such that ~ j b / = 2 s- 1. We then apply part B to complete the p r o o f by induction. Theorem 2.8 and Lemma 4.1 may be combined into: THEOREM 4.3. I f B ~×n = B is a m i n i m a l c.s.i.b, and 2 s-1 < n <-_2 s, q = s + 1. I f n = 2* then B ,,~ Bt(S+t)x28for i --- 1 or 2.

then

THEOREM 4.4. There is only one c.s.i.m. M ( u p to row and column permutations) having 2 s columns which is m i n i m a l in the sense that both its basis is m i n i m a l and that no subset o f rows of M is completely separating. M is the m a t r i x whose first s rows m l , " " ms are identical to the first s rows o f B(Is + t×2,) and whose remaining s rows are ms+~ = (1,... 1) - mi, i = 1,... s. Proof. Let N be any c.s.i.m, having 2 s columns, whose basis is minimal. Then B~S+l × 2s) = B is a basis of N, for B~s+t× 2s) is the only other minimal basis, and if B~2S+t × 2 s) is a basis of N, then so is B~ + 1 × 2,) . Let bi, i = 1,-.. s + I, be the rows of B as defined in (1.8). We shall first prove that for any row nk of N, nk = b~ or n k = b s + l - b i for some i, i = 1 , - . , s, where bs+t is the unit vector, nk = Y~c~bi and since ( 0 , . . . 0 , 1 ) ' ~ B and cl = 0 , 1 or - 1 by L e m m a 2.6, we have c,÷1 = 0 or 1. Suppose c~+ 1 = 1 and suppose c~ = 1 for some i # s + 1. Then there is some column b j in B which is everywhere 0 except in the ith and s + 1st components, giving nkj = 2, which is impossible. Similarly there is at most one c~ which is equal to - 1, for if there wre more than one such c~ we should get n~ = - 1 for some j, which is impossible. Therefore if cs+l = 1, then nk = bs+t, or nk = bs+t - b~ for some i < s. Similarly if cs+~ = 0, then no c~ can be equal to - 1 and at most one c~ can be equal to 1. Thus nk = b~ for some i < s. We have proved that the rows of N form a subset of the rows of M with the unit vector added, we shall now show that if N is a proper subset of M, it is not completely separating. Suppose N is a proper subset of M. By symmetry, we may assume that ml is not in N. Then if nk = bl, n k1=1 = n k2s-l+l = 1 and if n k ----- b , + l - b t , then nkt = 0 . Therefore there does not exist an nk in N such that nkt = 1 and n y -~+1 = 0, which means that N is not a completely separating matrix. In Lemma 2.4 we proved that M with the unit vector added is completely separating. Obviously the unit vector is superfluous, and we have proved that if N is any e.s.i.m, whose basis is minimal and which itself is minimal in the sense that no subset of its rows is completely separating, then N ~ M.

1964]

MINIMAL BASIS OF A COMPLETELY SEPARATING MATRIX

169

REFERENCES ]°

W. FELLER,Introduction to Probability Theor.v, Wiley & Sons, New York (1950).

2. M. MASCnLERANDB. P~LF~,A Characterization, Existence Proof and Dimension Bounds for the Kernel of a Game; Applications to the Study of Simple Games. Research Program in Game Theory and Mathematical Economics, Research Memorandum No. 9. Jerusalem: Hebrew University, (1964). BAR-rLAN UNIVERSITY-RAMAT GAN AND HEBREW UNIVERSITY OF JERUSALEM.

NOTE ON THE SELF-DUALITY OF THE UNRESTRICTED DISTRIBUTIVE LAW IN COMPLETE LATTICES BY

H. F. J. LOWIG ABSTRACT

In this article, a complete lattice in which meets are completely distributive with respect to joins is defined in such a way that the indefinitely wide class of all sets is not involved. It is proved that the concept of such a lattice is self-dual. The following theorem is well-known: (1) In a lattice, joins are distributive with respect to meets if and only if meets are distributive with respect to joins. In his paper l-l], George N. Raney proved a theorem containing the following statement: (2) In a complete lattice, joins are completely distributive with respect to meets if and only if meets are completely distributive with respect to joins. The author of the present note wishes to give another proof of (2), using a method similar to that by which (1) is usually proved. NOTATION. L and I are sets, and At is a subset of L for every element i of I. (ci [ie I) is the function on I whose value at i is ci for every element i of I, and {ct] i e I} is the range of this function. I f f is a function, Ry is its range. If F is a mapping of I onto a set of sets, I-I F is the cartesian product of F, i.e., the set o f all mappings f of / such that f ( i ) ~ F(i) for every element i of I. The sign I-I t ~i At means the same as the sign I I ( A i If X is a subset of a complete lattice, c~ X and L) X are, respectively, the meet and the join of X. If a~(i ~ I) are elements of a complete lattice, the signs c~t ~ ta~ and w t ~ xa~ mean the same as the signs n I} and w I}, respectively. We shall not write I-IAt, n a i or U a, instead of I-I, ~ t Ai, n i ~ ~ at or u i ~ i ai, respectively. If M is a set of sets, 1--IM is the set of all mappings t of M such that t(X) ~ X for every element X of M. This

li

{a,[ie

{atli~

implies that 1-I M = I I (x] x e M) = I-Ix ~M X. LEMMA 1. Let g be an element of element i of I such that A i C=R e .

I-I(RfIf I-I,

o,A,). Then there exists an

Proof. Assume the contrary. Then A ~ - Rg is non-empty for every element i of 1. Hence there exists an element f0 of IIt ~ 1 At such that fo(i) ~ Ai - R~ for every element i of I. Received October 19, 1964. 170

1964] SELF-DUALITYOF DISTRIBUTIVE LAW IN COMPLETE LATTICES This implies that

171

fo(i) ~ g ( f ) for i ~ I , f ~ I - I Aj; jEI

hence g(fo) ~fo(i) for i ~ I , and g ( f o) ¢ R s o , contrary to g ~ 1-[ (R f ; f e 11 ~ l Ai). This proves the lemma. Henceforth, it is understood that L is a complete lattice. LEMMA 2.

u ieI

"

"

I

a,}.

(It should be observed n Ai is the meet of the set Ai for a fixed i), Proof. If i E I and f ~ I-Ij ~IAj, then f ( i ) ~ Ai, and

NA i
DEFI~TION 1. We say that meets are completely distributive with respect to joins in L if

~, ux= U

(3)

t eFIM

M t(x)

X cM

or every set M of subsets of L. We say that joins are completely distributive with respect to meets in L if (4)

U

X eM

nx=

t

~0

M

U

X ~M

t(x)

for every set M of subsets of L. If this definition is accepted the following statement becomes a theorem: I f meets are completely distributive with respect to joins in L then

(5)

i~ l

I"

"

I AJ

"

I f joins are completely distributive with respect to meets in L then

.

{ uFo%n

}.

The following proof of (2) will include a proof of (5). ((5) does not immediately follow from Definition 1 because the sets Ai(i e I) need not be all different.)

172

H.F.J.

LOWIG

Let meets be completely distributive with respect to joins in L. Let

Then (3) holds with M replaced by N. Hence

n

(6)

{ U R.,,.lfe ]-JAi} = U N t(x). ,

, e ,i~

~,

Let t ~ I I N. Then

t(Rj.) e R t for f e I-I A,. I

el

Hence

By Lemma 1, there exists an element i of I such that

A,C__{t(R);fE

I I Aj}

./el

or, equivalently,

A, c={t(x); X~N}, 1"] fiX) < ~A~.

whence

XeN

Hence

U

(7)

,•ns

-

U,

n{,V/(i)If~A,}

~_ U n A

By(6)and(7), Because of Lemma 2,

(8)

U

iel

,,, =

Ius ~ lel

,)lJ

n A,/.t

jel

Let M be any set of subsets of L. Then, for the case that I = M, and Ax = X for X e M, (8) obviously becomes (4). Hence joins are completely distributive with respect to meets in L. By duality, if joins are completely distributive with respect to meets in L, then the dual of (8) holds, and meets are completely distributive with respect to joins in L. Hence (2) and (5) hold. REFERENCE

[1] George N. Raney, Completely distributive complete lattices, Proc. Amer. Math. Soc. 3 (1952), 677-680. UNIVERSITYOF ALBERTA, EDMONTON, CANADA.

A NOTE ON CLOSED MAPS AND COMPACT SETS BY

E. MICHAEL ABSTRACT

Some results relating closed maps to compact sets, which are already known for metrizable spaces, are here proved in a more general setting. Examples are given to indicate barriers to further improvements. 1. Introduction.

The purpose of this note is to prove the following results.

THEOREM 1.1. Let X be paracompact, Y locally compact or first-countable, and f : X ~ Y continuous and closed. Then 8 f - l ( y ) (the boundary of f - l ( y ) ) is compact for every y e Y. (i) COROLLARY 1.2. Let X be paracompact and f : X--, Y continuous, closed and onto. Then every compact subset of Y is the image of some compact subset of X. For metrizable X, these results are known. In fact, in that case Theorem 1.1 was proved by Vainstein [9] for first countable Y, and hence follows for locally compact Y from a result of Arhangel'skii [1, Theorem 21] which implies that Y must then be metrizable. Corollary 1.2, for metrizable X, was announced by Arhangel'skii [2, Theorem 15]. For paracompact X, our results seem to be new, and Corollary 1.2 will be applied in [6]. Theorem 1.1 (in somewhat sharpened form) and Corollary 1.2 are proved in section 2, while section 3 contains some counterexamples to various plausible conjectures. 2. Proofs. We will obtain Theorem 1.1 as a consequence of a somewhat stronger result (Theorem 2.1). Let us call a point y ~ Ya q-point if it has a sequence of neighborhoods N~ such that, if y~ e N~ and the y~ are all distinct, then y~, Y2, "'" has an accumulation point in Y. Call Y a q-space if every y ~ Y is a q-point. Clearly first-countable spaces and locally countably compact spaces are q-spaces; more generally, all p-spaces in the sense o f A . Arhangel'skii [1] and all M-spaces in the sense of K. Morita I7] are q-spaces. THEOREM 2.1. Let f : X ~ Y be continuous, closed, and onto, where X is T 1. I f y ~ Y is a q-point, then every continuous, real-valued function on X is bounded on d f - (y). Received October 30, 1964. (1) That some restriction must be made on Y is seen by taking X to be the reals, Y the quotient space obtained from X by identifying all integers, and f the quotient map. 173

174

E. MICHAEL

[September

Proof. Suppose h: X ~ R is continuous, and unbounded on Of-l(y). Pick xl,x2,...in Of-l(y) such that

] h(xn+ x ) ] > [ h(x,,) ] -I- 1. Let Vi = {x ~ X : [ h(x) - h(x,) [ < 1/2}.

Then 11/is open, xie Vi, and {Vi}i is discrete (i.e. every x e X intersectiong at most one Vi).

has a neighborhood

Let us now pick a sequence z i ~ V~ r3f-1 (Ni) (where Ni is as in the definition of q-point) such that all the f(zi) are distinct. This is easilY done by induction: Let z I = x t . Suppose suitable zl,...,zi_ 1 have been found. Let Wi = [11/¢3f- X(N,°.)] - f - 1({f(z2), ... ,f(zi_ 1) } ), and

pick

zi~

_f-l(y);

this

is possible,

since

~

is

open

and

xi~ Win Of-l(y). This zi clearly satisfies all requirements. Let Z = {zl,z2,... }. Since zi~ Vi, every subset of Z is closed, and hence so is every subset o f f ( Z ) . But f(zi)~ Ni and the f(zi) are all distinct, so that f ( Z ) must have an accumulation point. This contradiction completes the proof. COROLLARY 2.2. If X is normal in Theorem 2.1, then 0 f - l ( y ) iscountably

compact. Proof. Suppose not. Then Of-l(y) has a subset S = {xl,x2, "'} (all distinct) with no accumulation points in Of-~(y), and hence none in X because f - l ( y ) is closed (since f is closed). Define g:S --* R by f(x,) = n. Then g is continuous on the closed set S, and hence has a continuous extension h: X - , R. Since h is unbounded on Of-l(y), this contradicts Theorem 2.1.

Proof of Theorem 1.1. As observed above, first-countable spaces compact spaces are q-spaces, so that every Of-l(y) is countably Corollary 2.2. But Of-l(y) is closed in X, and hence paracompact. compact, countably compact spaces are compact r3], it follows Of- 1(y) is compact.

and locally compact by Since parathat every

Proof of Corollary 1.2. Without loss of generality, we may assume that g is itself compact, and we must find a compact C c X such that f(C) = Y. For all y ¢ Y, pick p y e f - l ( y ) , and let

Let

Cy = ~f-1(y)

if Of-l(y) ¢ tk

C, = {p,}

if Of-l(y) = ~p.

c=U,,yc,,

and let g = f ] C. Then f(C) = Y, and g is closed since C is closed in X. Also, for

1964]

A NOTE ON CLOSED MAPS AND COMPACT SETS

175

each y e Y we have g - l(y) = C , so each g- l(y) is compact. Since Y is compact, this implies that C = g-Z(y) is compact (see, for instance, [-5; Theorem 1]), and that completes the proof. There is an analogue of Corollary 1.1 for normal X, obtained by everywhere changing "compact" to "countably compact" ; the proof is based on Corollary 2.2. For arbitrary Tl-spaces X, the best I can do is to show (using Theorem 2.1) that every countably compact subset of Y is the image of a closed subset of X on which every continuous f : X--+ R is bounded. There ought to be something better. 3. EXA_MPLKS. The following examples indicate some limits to improving our results. EXAMPLE 3.1. X is normal, Y is compact metric, and f : X ~ Y is continuous and closed, but some df-l(yo) is not compact. Let Y be the set of ordinals < to, and let Z be the set of all countable ordinals, both with the order topology. Let X = Y x Z, and let f : X ~ Y be the projection. Then X is normal; also X is countably compact, so f is closed. Finally, ~f-a(co) = f - l ( c o ) is homeomorphic to Z, and is therefore not compact. EXAMPLES 3.2. X is completely regular, Y is compact metric and f : X --} Y is continuous, closed and onto, but some ~f-t(Yo) is not even pseudocompact. (2) Moreover, there is no countably compact C c X such that f(C) = Y. Let R be the reals, N the integers, and 29 the closure of N in fiR. Let x = ~R - ( 2 9 - N) A=X-(R

-iV).

(This X seems to go back to Kat~'tov, and is the space described in [4; p.97, 6P]). Let Ybe the quotient space X / A , and f : X-+ Ythe quotient map. Let Yo =f(A); then ~ f - l ( y o ) = f - l ( y o ) = A, and A is not pseudocompact since it contains N as an open-closed subset. It remains to check that Y is compact metric, which we do by showing that it is the one-point compactification of R - N ( = X - A). To do that, we must verify that every closed (in X) subset E of R - N is compact. Since N and E are disjoint closed subsets of R, their closures N and E in pR are also disjoint. This implies that E c X; since E is closed in X, we have E =/~, and hence E is compact. Suppose, finally thatf(C) = Y, and let us check that C is not countably compact. If/V c C, then C is not countably compact since N has no limit point in C. If n ¢ C for some n e N, then C is not countably compact either, because a sequence (2) A space X is pseudocompact if every real-valued continuous function on it is bounded. Countably compact spaces are pseudocompact,and the converse is true in normal spaces.

176

E. MICHAEL

in R - N converging to A will then have no limit point in C. (Note that C D R - N). That completes the proof. EXAMPLE 3.3. X is normal, Y is compact Hausdor.ff, f : X .o Y is continuous, closed and onto, but Y is not the image of any compact subset of X. Let X be the set of countable ordinals, with the order topology, and let A be the set of limit-ordinals in X. Let Y be the quotient space X / A , and f : X - * Y the quotient map. Then X is normal a n d f i s closed; i f f ( C ) = Yfor some C c X, then C c (X - A), so C is dense in X, and hence C cannot be compact (since X is not). To show that Y is compact metric, we need only check that it is the onepoint compactification of X - A, and for that it suffices to prove that any closed (in X) subset S of X - A is compact. But any such S must, in fact, befinite (since X is countably compact), and that completes the proof. If the continuum hypothesis is assumed, then a recent example of M.E. Rudin [8] implies that "Hausdorff" can be strengthened to "metric" in Example 3.3: EXAMPLE 3.4. (Assume continuum hypothesis). X is normal, Y is compact metric, f : X ~ Y is continuous, closed, and onto, but Y is not the image of any compact subset of X. In I-8; Example2], M.E. Rudin constructs a normal, countably compact, noncompact space X, containing a dense open subset M which is separable metric and locally compact. Let A = X - M , let Y be the quotient space X / A , and let f : X --* Ybe the quotient map. Since every open U D A has a compact complement in X, it follows that Yis essentially the one-point compactification of M, so that Y is compact metric. Since X is countably compact, f must be closed. I f f ( C ) = Y for some C = X, then C ~ M, hence C is dense in X, and therefore C cannot be compact (since X is not compact). That completes the proof. REFERENCES 1. A. Arhangel'skii, On a class of spaces containing all metric and all locally bicompact spaces, Dokl. Akad. Nauk SSSR 151 (1963), 751-754 ( = Soviet Math. Dokl. 4 (1963), 1051-1055). 2. A. Arha~gel'skii, Factor mappings of metric spaces, Dokl. Akad. Nauk SSSR 155 (1964).

(247-250~ (=Soviet Math. Dokl. 5 (1964), 368-371. 3. R. Arens and J. Dugundji, Remark on the concept of compactness,Portugaliae Math. 9 (1950), 141-143. 4. L. Gillman and M. Jerison, Rings of continuousfunctions, van Nostrand (1960). 5. E. Halfar, Compact mappings, Proc. Amer. Math. Soc. 8 (1957), 828--830. 6. E. Michael, ~o-spaces, to appear in J. Math. Mech. 7. K. Morita, Productsofnormalspaces with metricspaces, Math. Ann. 154 (1964), 365-382. 8. M.E. Rudin, A techniquefor constructing examples,to appear in Proc. Amer. Math. Soc. 9. I. A. Vainstein, On closed mappings of metric spaces, Dokl. Akad. Nauk SSSR 57 (1947), 319-321. UNIVERSITYOF WASHINGTON SEATTLE, WASHINGTON

WEAK* SUPPORT POINTS OF CONVEX SETS IN E* BY

R. R. PHELPS0 ABSTRACT

Density theorems are obtained fcr weak* support points and support functionals of certain convex subsets of the dual of a Banach space. Suppose that C is a closed convex nonempty subset of a real topological vector space E. A point x of C is said to be a support point of C if there exists a closed hyperplane H containing x such that Cis on one side of H. Equivalently, x is a support point of C provided there exists a nontrivial continuous linear functional f on E such t h a t f ( x ) = sup {f(y): y E C} - supf(C). (Such a functional is called a support functional of C.) Unless there are further hypotheses on the set C or the space E, there might be no support points in C. For instance, Klee [3] has shown the existence of a nonempty closed convex unbounded subset C of a certain metrizable, separable complete locally convex space (the space of all real sequences, in the product topology) such that C contains no support points. On the other hand, if E is a Banach space, then it is known [1] that the support points of C are dense in the boundary of C and that the support functionals of C are norm dense among those which are bounded above on C. (Furthermore, the latter assertion is valid in a normed linear space E only if E is complete.) It remains an open question whether a bounded closed convex subset of a metrizable complete locally convex space necessarily has support points. In the present note, we will prove two results, analogous to the two main theorems of [1], for certain special locally convex spaces, namely, the space E* in its weak* topology, where E is a Banach space. (In its norm topology, of course, E* is a Banach space and the results from [1] are applicable; they also apply in the weak* topology if E is reflexive.) Thus, the dual of E* is E itself, so that our closed hyperplanes will be weak* closed and they will be determined by functionals of the form f ~ f ( x ) , for some x ~ 0 in E. It follows, then, that a support point (which, for emphasis, we will call a weak* support point) of a weak* closed convex subset C of E* is an element f of C such that f(x) = sup {g(x): g ~ C} = sup C(x) for some x # 0 in E. Such an element x will be called a weak* support functional of C. The first of our two theorems may then be stated as follows. Received October 28, 1964. 1) Supported by National Science Foundation Grant GP 378. 177

178

R.R. PHELPS

[September

THEOREM 1. If E is a Banach space and C is a weak* closed convex subset of E* then the weak* support points of C are norm-dense in the norm-boundary of C. lit is easily seen that the choice of topologies (norm-dense in the norm-boundary) in the conclusion to this result is the best among the four possible combinations of norm and weak* topologies.] Our second theorem is not as simple, but it has some simply stated corollaries. Geometrically, it says that if C can be strictly separated from a bounded weak* closed set A by a weak* closed hyperplane H, then it can be strictly separated from A by one of its weak* supporting hyperplanes H1, with H1 nearly parallel to H. There is no loss in generality in assuming that A is convex. THEOREM2. Suppose that E is a Banach space, that C and A are weak* closed convex subsets of E*, that A is bounded and that for some x in E sup C(x) < infA(x). Then for any 8 > 0 there exists a weak* support functional, x o of C such that IIx - xo rl < and sup C(xo) < infA(xo). COROLLARY 1. If E is a Banach space and C is a weak* closed convex subset of E*, then the weak* support functionals of C are dense in E among those x for which sup C(x) < oo. A weak* supporting half space for C is a set of the form {g:g(x)< supC(x)} where x is a weak* support functional for C. COROLLARY 2. If E is a Banach space and C is a weak* closed convex subset of E*, then C is the intersection of its weak* supporting half-spaces. The proofs of these corollaries are immediate from Theorem 2. At the end of this note we will discuss examples which show that Theorem 1 may fail (even for bounded sets) if C is merely assumed to be norm closed, or if E is not assumed to be compIete. Also, the fact that weak* closed convex subsets of E* have a certain local weak* compactness property clearly does not imply that every weak* continuous functional which is bounded above on C is a support functional; consider the convex set defined by a hyperbola in the plane. The methods of proof are closely related to those in [1], with one exception. In [1], the final step in producing support points was an application of the separation theorem in E; in the present note, it is applied in E x R to convex sets associated with the graphs of appropriate convex functions. This idea was suggested by A. BrCndsted and R. T. Rockafellar [2], who used it in their work on support points of the graphs of convex functions. The first step in our proof is a lemma which is a bit more general than the corresponding lemma in [1] and less general than the one in 1"4]. We include the proof for the sake of completeness.

1964] LE~

WEAK* SUPPORT POINTS OF CONVEX SETS IN E*

179

1. Suppose that ~p is an upper semicontinuous function on the Banach

space E, w i t h - ov <=dp < oo. I f k>O, partially order the set X = {x: ~b(x)> - c~} by (1) x >- y if and only if k II x - y l] < ~b(x) - q~(y). I f ~p is bounded above on X then for any z in X there exists a m a x i m a l element Xo in X such that Xo >-z. Proof. Since the ordering defined in (1) is proper, we can apply Zorn's lemma to the set Z = { x : x ~ X , x >- z}. If W is any linearly ordered subset of Z, let a = sup {(k(w): w e W}; this is finite since ~b is bounded above on X. Since W is linearly ordered we can choose a sequence {w.} c W with w.÷l >-w. for n = 1, 2, 3,... such that ~b(w.) ~ a. It follows that if m > n, then Wm>- W, and hence k II Wm -- w. I1 <=c~(Wm) -- dp(w.). Since (k(w.) converges, this shows that {w,} is a Cauchy sequence in E and hence converges to an element x in E. Since ~b is upper semicontinuous, q~(x)=> lim sup~b(w.)= a, so x ~ X. To see that x is an upper bound for W, first note that for any n, k II x - w. JI = lim k II w m - w. II ~ lira sup ~b(wm) - (k(w.) : a - ~b(w,) < m~n

m~n

__< ¢(x) - ¢(w~),

so x >- w.. Finally, for any w in W, w # x, there exists n with w. >- w. (If not, then for all n, k II w - w. II ---- ~(wn) <__a - ~b(w,) ~ 0, hence w = lim Wn = X.) Thus, Zorn's lemma is applicable and Z has a maximal element Xo, If x e X and x>- xo, then x >- Xo >" z so x ~ Z and hence x = xo, i.e. Xo is a maximal element o f X such that Xo >- z. The next lemma formalizes the use of the separation theorem in E x R referred to above. Recall that a function f is convex [concave, affine] if for each x, y in E and 0 < 2 < 1 , f ( 2 x + (1 - 2 ) y ) < [ > , = ] 2 f ( x ) + (1 -)~)[(y). LEMMA 2. Suppose that ~b, is a lower semicontinuous convex function on E with - oo < d/, < oo (~k1 ~ o0), and that ~b2 is a continuous concave function on E(ff 2 ~ - ~ ) . I f d/1 >=~k2, then there exists a continuous affine functional h on E such that ~b1 > h > d/2. Proof. In the space E x R (product topology) Jet C1 = {(x, r) : r > ~kl(x)} and let C2 = {(x, r): r < ~b2(x)}. Then C, and C2 are closed convex sets and since ~'2 is continuous, the interior of C2 is the nonempty set {(x, r): r < ~2(x)}. This latter set misses Ca, so the separation theorem can be applied to yield a closed hyperplane H which separates C1 and C2. To see that H is the graph of a continuous at}ine function h (defined by h(x) = r if and only if (x, r ) e H), we need only show that for at least one point Xo, the line {Xo} x R is not contained in H. Any point Xo such that ~q(Xo) < oo will suffice, since (Xo,~l(Xo))~ C1 and will be o n one side of H while (Xo, ~b2(Xo) - 1)e int C 2 and will be strictly on the other

180

R.R. PHELPS

[September

side. Finally, for any x, ( x , h ( x ) ) e H , so if ~bl(x) < h(x) then (x,~b1(x)) will be strictly on one side of H, and in C~. For r > h(x) > ~l(x), (x, r) is strictly on the other side of H and also in C1, an impossibility which implies that h < ~1. Similarly, ¢2 < h and the proof is complete. The functions ¢1 and ~k2 which we will use in the proofs are certain combinations of linear functionals, the norm, and one other classical convex function, the support functional Sc for a weak* closed convex subset C of E*. For x in E define Sc(X)= s u p { f ( x ) : f e C} =-sup C(x). This function is clearly convex and positive-homogeneous (i.e. Sc(2X)= ;~Sc(X) if ;t > 0), and it follows from the separation theorem (applied in E* in its weak* topology) that f e C if (and only if) f < Sc. It is not di~cult to see that Sc is lower semicontinuous. Finally, if C is bounded, with Ilfll < M, say, for f e C, then for any such f and any x, y in E, we have f ( x ) = f ( x - y) + f ( y ) < sup C(x - y) + sc(y) < M 1[x - y II + sc(y). Thus, I sc(x) - Sc(y) l <=M II x - y II for all x, y, so that Sc is (uniformly) continuous on E. THEOREM l. I f C is a weak* closed convex subset of E*, then the weak* support points of C are norm-dense in the norm-boundary of C. Proof. Given f in the boundary of C and 5 > 0, choose./'1 in E* ~ C such that ] I f - f l II < e/2 and use the separation theorem to choose z in E, lie II = 1, such that sup C(z) < f l ( z ) . Then f ( z ) > f l ( z ) - e/2 > sup C(z) - e/2 = Sc(Z) - 5[2 and f < Sc. Let ~b = f - Sc, so that ~b is upper semicontinuous and q~ < 0. By applying Lemma 1 (with k = 5) we can obtain Xo in E such that Xo >- z and Xo is maximal in the (nonempty) set where q5 > - ~ . The first assertion implies that II xo - = II --< ,¢,(xo) - ,~(z) __< - ,¢,(=) = s~(=) - f(=)

=< ~/2, so II go - z I1 --< 1/2, and

hence (recall that II= II = ~)Xo ¢ 0 The maximality of Xo implies that for any y # x o such that ~b(y) > - ~ (equivalently, Sc(y) < ~ ) we have e I[ Y - Xo 11> > qb(y) - ~b(Xo) = f ( y - Xo) - [sc(y) - Sc(Xo)]. Let ~kI = Sc - Sc(Xo), ~k2(y)= = f ( y - Xo) - e II y - xoll. By Lemma 2 there exist a continuous atiine functional h on E such that ~kt > h > ~k2. Since 0 = •l(Xo) ~ h(xo) > ~b2(Xo) ~ 0, there exists a continuous linear functional g on E such that h = g - g(Xo). Thus sc(y) - g(y) > Sc(Xo) - g(xo) for any y; since Sc and g are positive-homogeneous, this implies that sc - g > 0 and Sc(Xo) - g(Xo) = 0, i.e. g e C and g(xo) = sup C(xo). The inequality h > Cz means, on the other hand, that for all y, g ( y - Xo) > ~_f(y-xo)-~lly-xoll. Thus, for any x, so that LIf- g II z~ and the proof is complete.

(f-g)(x)<=~llxll,

THEOREM 2. Suppose that C and A are weak* closed convex subsets of E*, that A is bounded, and that for some x in E, sup C(x) < infA(x). Then for any

1964l

WEAK* SUPPORT POINTS OF CONVEX SETS IN E*

0 there exists Xo in E which supports sup C(xo) < infA(xo).

C such that

IlX-Xol I <e

181 and

Proof. Choose f in C such that f ( x ) > sup C(x) - 1. Let B = - A ( = { - g: g e A } ) ; we can assume without loss of generality that 0 e A so that ss > 0. Since f e C, f - s c < O, and hence 0 > ¢ = f - s c - s B. Furthermore, ¢(x) > - 1 - ss(x). Since ~b is upper semicontinuous, it follows from Lemma 1 (with k > 0 to be chosen later) that there exists Xo in E such that k [IX o - x II < ¢(Xo)- ¢ ( x ) < <= - c~(x) < 1 + sB(x) and k IIy - Xo II > - ~(Xo) for y in E, y # Xo. Let ~bl = Sc - Sc(Xo) and ~b2(y) = f ( y - Xo) - k I[Y - Xo [l - ]s~(y) - sB(xo)]; then ~kI and ~k2 satisfy the hypotheses to Lemma 2 and ~kl(y) > ~k2(y) if y ¢ x o. Thus, there exists a continuous affine functional h on E such that ~1 __>h __>~k2. Exactly as in the proof of Theorem 1, we have h = g - g(xo) for some continuous linear functional g on E, and S c - g _ - > 0 = s c ( X o ) - g ( x o ) , so that g e C and g(xo) = sup C(xo). Since k I]Xo - x l[ -<- 1 + sB(x), for sufficiently large k we have II Xo - x [1 < ~. Finally, since ¢(Xo) - ¢ (x) > k 11x0 - x H > 0, we have f ( x o ) - Sc(Xo) - ss(Xo) > f ( x ) - Sc(X) - s s ( x ) = f ( x ) + fl, where fl = - Sc(X) - ss(x) = - sup C(x) + infA(x) is positive by hypothesis. Thus, inf A ( x o ) - s u p C(xo) = - Sc(Xo) - Ss(Xo) ~ f (x - Xo) + fl >=fl - I[ f l[ I[ x - X o [I >=f l Ilfll k - ' [ l + s,(x)]. For sufficiently large k this is positive and the proof is complete. We conclude with some examples which show that Theorem 1 may fail if certain of the hypotheses are weakened. For instance, it is not enough to assume merely that C is norm closed. Indeed, suppose that E is not reflexive and choose an element F in E**, IIF II = 1, which is not in the canonical image of E. Let C = {f: feE*, [[fll z 1 and IF(f) I __<1/2}; clearly, C is norm closed, convex, bounded and has nonempty norm-interior. It is easily verified that the set a = {y: F(f)= 1/2 Ilfll < 1} is open in the norm boundary of C, but contains no weak* support points of C. (Any functional which supports C at a point of A is necessarily a constant multiple of F, hence not weak* continuous.) In Theorem 3 of [1] it is shown that in any incomplete normed linear space E there exists a symmetric bounded closed convex set A with nonempty interior such that the support functionals of A are not dense in E* (hence those which lie in the boundary B of the polar A ° of A are not dense in B). The polar C = A ° of A is therefore a weak* compact convex subset of E*, but its weak* support points are not dense in its norm-boundary, which shows that completeness of E is essential to Theorem 1. (It is interesting to note that we do not require completeness of E* in the weak* topology; this occurs only when E is finite dimensional.)

182

R . R . PHELPS

BIBLIOGRAPHY I. Errett Bishop and R. R. Phelps, The support functionals of a convex set, Proc. Syrup. Pure Math., Amer. Math. Soc. 7 (Convexity) (1963), 27-35. 2, A. BrOndsted and R. T. Rockafellar, On the subdifferentiability of convex functions, Proc. Amer. Math. Soc. (to appear). 3. V. L. Klee, On a question of Bishop andPhelps, Amer. J. Math. 85 (1963), 95-98. 4. R. R. Phelps, Support cones andtheir generalizations, Proc. Syrnp. Pure. Math., Amer. Math. Soc. 7 (Convexity) (1963), 393-401. UNIVERSITY OF WASHINGTON SF~TTLE, WASHINGTON

ON EXTREMAL PROBLEMS OF GRAPHS AND GENERALIZED GRAPHS BY

P. ERDOS ABSTRACT An r-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to every I and r there is an e(l, r) so that for n > n 0 every r-graph ofn vertices and n ' - ~(t, ,) r-tuples contains r . I vertices x(J),l < j < r, 1 < i _< 1, so that allthe r-tuples (xl(1), xt2(2),..., xi(r)) occur in the r-gr~-ph. = - -

By an r-graph G (')(r > 2) we shall mean a graph whose basic elements are its vertices and r-tuples; for r = 2 we obtain the ordinary graphs. These generalised graphs have not yet been investigated very much. G(')(n; m) will denote an r-graph of n vertices and m r-tuples; G(')(n;(rn)), the complete r-graph of n vertices, will be denoted by K(')(n), i.e., Kt')(n) contains all the r-tuples formed from n elements. K(')(nl,..., n,) will denote the r-graph of ~ = 1 nl vertices and 1-I~= 1 nl r-tuples defined as follows: The vertices are

x~j), 1 <=j <=r, 1 ~_ i ~_ nj and the r-tuples of our r-graph are the I-I~--1 n~ r-tuples (X~:),

v(a)

v(r)~

1<

i/<-- nj,

1 < j < r.

Thus K(2)(2, 2) is simply a rectangle. Denote byfz(')(n) the smallest integer so that every G(')(n;f~(')) contains a complete r-graph of I vertices. As is well known Turin [5] determinedf~t2)(n) for every I and n and also proved that there is a unique G(2)(n;f~2)(n) - 1) which contains no complete 2-graph of I vertices (ordinary graphs have to be denoted as 2-graphs here). In particular fta2(n)= [n2/4] + 1. For r > 2 the determination of f~'~(n) seems to be a very difficult question which is unsolved for all r > 2, l > r. (This question was also posed by TuHm. Tuffm in particular conjectured that

f(53)(n) = n2(n - 1).

(1) Received August 18, 1964.

183

184

P. ERDOS

[September

Vera T. S6s observed that if (1) is true then the extreme graphs are certainly not unique, and this may be one reason why the proof of (1) is difficult. It is easy to see that

exists,but the value of c~") is not known for any r > 2, l > r. Denote byf(n; K(')(I,...,I,)) the smallest integer so that every

G(')(n ;f (n ; K(')(ll , ... , I,)) contains a K(')(ll, ..., l,). If ~ . [ = l l , > n we define: f ( n ; K(')(ll, ..., l,))= ( n ) +

1.

/

In particular, f ( n ; K(2)(2, 2)) is the smallest integer so that every G(2)(n ;f(n;K(2)(2, 2)) contains a rectangle. E. Klein and I [1] proved that Cl n 3/2 < f ( n ; K(2)(2, 2)) < c2n 3/2.

(2) Very likely

(3)

lira f(n; K(2)(2, 2))]n 3/2 = 2 x / 2 " n~00

but it is not even known that the limit in (3) exists. Ktivfid, the Turfins [4] and I showed that f ( n ; Kt2)(/,/)) < cn 2-1/~

Probabby f(n; K(2)(I,/)) > c' n 2-01o,

(4)

but we are unable to prove (4) for l > 2. Stone and I [2] proved that for every 8 > 0 and a sufficiently small c, and n > no( )

(4')

f(n; K(2)([c,log hi, [c,log hi)) < ~n2.

It can be shown by probabilistic methods (similar to those used in [4] that for sufficiently large ~, (4 #)

f(n;Kt2)([~,logn],[~,logn]))

> (1 - ~ ) ( 2 )"

In the present paper we first of all shall prove the following

1964] EXTREMAL PROBLEMS OF GRAPHS AND GENERALISED GRAPHS

185

THEOREM 1. Let n > n o (r, l), l > 1. Then for sufficiently large C = (C is independent of n, r, l)

(5)

n,-C(/t'-') < f(n;K(')(l, ...,/)) < n,-(t/l'-~).

We only prove the upper bound and will discuss the lower bound later. We use induction with respect to r. First we prove the right side inequality of (5) for r = 2, (this is substantially contained in [6], then we use induction with respect to r. Consider now the case r = 2. Denote the vertices of our graph G(2)(n; t), t > n 2-1]z by xl,...,x,,, and by v(xi) we denote the valence of x~ (i.e. v(xi) denotes the number of edges incident to x~). Clearly

~ v(x~) > 2n 2-ul •

(6)

t=1

Let x~S,, ..., ~o(~,~'A°be those xj's which are joined to xi. Form all the l-tuples from these vertices for all i, 1 < i < n. The number of these l-tuples (each counted with the proper multiplicity) clearly equals

~ ( v(xi))

(7)

i=1

1

"

An elementary inequality states that the sum (7) is a minimum if all the v(xi) are

equal(~'~=lv(x~)satisfies(6)((Y)= O i f y < l ) l

. Thus by a simple computation

for n > no(/)

Hence there are l vertices Yl, "",Ys which are all joined to the same l vertices x j,, ... x j,, which means that our graph contains a K(2)(l,/) as stated. Assume now that the right side inequality of (5) holds for r - 1, we shall prove it for r. First we need the following LEMMA. Let S be a set of N elements Yl, "",YN and let A~, l <_i
f. (Assume that tl(,~ denotes the number oJ elements o.f Al)

(8)

~ ~ ~ nN I=I

W

186

Then

P. ERDOS

ifn ~212wt

there are

1 distinct A's, |

(9)

[~eptembor

A~t,...,At ,, so that

N

Pl-=At, ~_ 2-~w~"

Denote byfl(y) the characteristic function of At (i.e., f~(Yi) = 1 if yj is in At, and is 0 otherwise). Put

F(y) = '~f~(y). IJl

Clearly by (8) N

(I0)

]~ F(y#) > 1=1

- -

nN W

Thus from (10) we obtain by an elementary inequality that N J-1

is minimal if for all j F(yj) = n/w, or

(11) )=1

On the other hand we obtain by a simple argument N

(12)

~ F(Yj) t = ~ At1 ~ Ata n . . . n At, j=l

where the summation in (12) is extended over all the choices of i,, ..., it(1 _-
Nnt 2wt

The number of the summands in (12) where not all the indices are distinct is easily seen to be less than 12n1-1. The contribution of each of these terms to the right side of (12) is clearly at most N. Thus finally from (12) and (13)

1964]

E X T R E M A L PROBLEMS O F GRAPHS A N D G E N E R A L I S E D G R A P H S

N F(Ys) t < Nnt + 12n1-1N Y~

(14)

J=l

2--7

I87

"

Now since n > 21Zw I (14) contradicts (11). Thus (9) must hold for at least one choice of distinct A:s, 1 < i < I which completes the proof of the Lemma. The Lemma is clearly not best possible, but is good enough for our purpose. Now we are ready to prove the right hand inequality of (5) for r > 2. Assume that it has already been proved for r - 1 if n > no(r - 1, l), and we are going to prove it for r if n > no(r,l ). Suppose then that we have a G(')(n; 0 with t > n r-(z/t'-D. Denote by x~,...,x, the vertices of our G (') and by Yt,'",YN, N-= ( n r _ l ) , the set of all ( r - 1)-tuples formed from the x,,1 _
~ = rt~_rn "-l/t'-I

> n N r l n -1/t'-1

t=l

Thus our Lemma applies with N - ( r

._n)1 , w---nt/t'-'/r v., since for

n > no(r, l) n ~_ 21Zw ~ is clearly satisfied. We thus obtain that there are/distinct A's At1, "', A . for which

(15)

s.zAo

1( n )

~- -2

r-

I

(r!

n_Z/t,_,)l

> n'-

t-(za'-~)

By (15) there are more than n '-1-1/t'-* ( r - 1)-tuples

(16)

p~,-1)

p~;-1)

tI > n r-l-l]l'-I

so that all the r-tuples

(17)

(xt. ¢ Ptj'-') x,.uPJ '-'), 1 < s < l, 1 _gj 6 t1

is clearly satisfiedby our construction) are one of the P~°'s of our Gt')(n;t). These (r - 1)-tuplesdefine a G (r-l)

(n

--

l;tt), tt

> n -t-(i/t~'-=)

which by our induction hypothesis contains a K ('- 1)(/, ...,/) if n > I + no(r - 1, l). By (17) this implies that our G(')(n;t) contains a K(')(l,...,l) which proves the right side inequality of

(5).

188

P. ERDOS

[September

Theorem 1 easily implies the following COROLLARY. Let n > no (r, 1), ti >- n, i = 1,..., r. Let G (')

(

~ ti ; U

)

'r'fi

, U >

nl/Z,-t

=1

ti

i=1

be s subgraph of K (') (ti,..., t,). Then G(°( ~ ' = t ti ; U) contains a K(')(l, ..., l) A set of tt elements can be decomposed into the (non-disjoint) union of [h/[(n/r)]] + 1 sets having In~r] elements. Hence clearly a K(')(tt, ..., t,) can be decomposed into the union of at most

i=1

+1 _ r


1-It, ,-1

K (" ([n/r],..., [n/r])'s (the union is non-disjoint but every r-tuple of K(O(tl, ..., t,) occurs in at least one of the K(')([n/r], ..., [n/r])'s). Thus at least one of these Kt')([n/r], ..., [n/r]'s say Ki ') contains at least n'-tar-lr-tuples. Our K~t') has r[n]r] < n vertices, hence the corollary follows from theorem 1 (the right side inequality of (5)). The corollary has applications in number theory, this will be discussed in a subsequent paper. Without much change in the proof of Theorem 1 we could show that the right side inequality of (5) holds for every n ~ rl. But in fact the right side of (5) is trivial if l > 2 (log n) t/'- 1 , for then

(7) 0 be any number, n > no(ot, l,r), 2 < l < ct(logn) t/('-l). Then we have for a sufficiently large absolute constant C t

We do not prove the upper bound of (18) since it is similar to that of (5), we have only to carry out the estimations and the induction with respect to r a little more carefully. The most interesting special cases are those which correspond to (4') and (40. For every e > 0 and a sufficiently small c~ ) (18')

f(n;K(°([c(~)(logn)l/('-t)], ".., [c (a')(logn) t/('- 1)] < 8n ~.

1964] EXTREMAL PROBLEMS OF GRAPHS AND GENERAL1SED GRAPHS

189

(18') in fact follows from the fact that the right side inequality of (5) holds for every n ~ lr. Further we have for a sufficiently large ~(')

(18")f(n;K(r)(['~)(logn)l/(r-l)])...:)[';r)(logn)I/(r-l)]))> (I-8)(~) To give the reader an illustration how to prove the lower bound of (5) and (18) we prove in full detail (18") for 8 = ½. In fact we prove a stronger result. If G(')(n;m) is an r-graph then G(')(n; m) will denote its complementary graph i.e. the G<')( n"'~[ rn~J _ m) whose r-tuples are precisely those which do not occur in G(')(n ; m). THEOREM 3. Put t = [4(logn) 1/c,- 1)] + 1. For every n there is a G(')(n) * so that neither G(')(n) nor G(')(n) contains a K(')(t, ..., t). The proof will follow very closely the method used in [3]. The total number of r-graphs G(')(n) is clearly 2(n/').The number of those r-graphs for which either G(')(n) or G(°(n) contains a K(')(t, ..., t) having the vertices x} j), 1 < i < t; 1 <: j < r clearly equals

2 " 2 (nlr)-t', since the t" r-tuples of our K(')(t, ..., t) either all have to belong to our G(°(n), or none of them belong to our G(')(n). The number of choices for our K(')(t, ..., t) is clearly less than n"/r ! < ½ n't. Therefore the number of graphs G(')(n) for which G¢')(n) or G("(n) contains a K (')(t,-.-, t) is clearly less than n rt . 2 ( n / r ) - - t r

<

2 (n/r) .

Thus there is a G(')(n) so that neither G(r)(n) nor G(r)(n) contains a K (')(t,..., 0, as stated. The proof of the lower bound of (5) and (18) uses the same methods combined with the methods of [4]. It is possible that lim f(n;K(r)(l, ..., l))/n ,-(1/i,- 1) ?J ~ O0

exists and is different from 0 (by (5) it is < A 1), but as stated in (3) this is not even known for r = l = 2. R~RENC~g 1. P. ErdSs, On sequences of integers no one of which divides the product of two others and on some related problems. Izv. Nauk Mat. i Mech. Tomsk 2 (1938), 74-82. (The best estimation off(n; K2(2, 2)) is due to I. Reiman, Ober ein Problem yon K. Zaranbievicz, Aeta Math. Hung. Acad. Sci., 9 (1958), 269--273.

* G(r)(n) is an ~-graph having n vertices, the number of its r-tuples is not specified.

190

P. ERDOS

2. P. Erd6s and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. So¢. 52 (1946), 1087-1091. 3. P. ErdOs, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294. 4. P. ErdSs and A. R~.nyi, On the evolution of random graphs, Publ. Inst. Hung. Acad. Sci. 5 (1960), 17-61. 5. P. Tur~ln, On the theory o f graphs, Colloqium Math. 3 (1954), 19-30. 6. T. K6vfiri, S6s V.T. and P. Turfin, On a problem ofK. Zarankiewicz, Colloquium Math. 3 (1954), 50-57. MATHEMATICALINSTITUTE UNIVERSITY OF BUDAPEST

UTILITY FUNCTIONS AND THE 'lin' OPERATION FOR CONVEX SETS BY

VICTOR KLEE ABSTRACT F o r an l~o-dimensional space E o f altelnatives, t h e r e is described a preference relation ~, such that (in a very strong sense) no information about

~, can be expressed in terms of finite-dimensional linear transformations of E. The same construction shows that for each countable ordinal fl, E contains a convex cone K such that lin/~ K = E but lin~K ~ E for a < ~. This note contributes to utility theory by shrapening a recent example of Kannai I5] and Perles, and to the geometry of infinite-dimensional convex sets by settling a problem raised in [11] concerning the iteration of the 'lin' operation. The reduction of the first matter to the second is described in Section 1 below, and the actual construction appears in Section 2. Section 3 mentions two unsolved problems. 1. Utility theory. An l~-dimensional preference relation is a transitive and reflexive relation ~ on an v-dimensional real linear space E such that the following conditions are satisfied for all x, y and z e E: (1) i f x ~ y , then x + z ~ y + z; (2) if x ~ y and 2 > 0, then 2x ~ 2y; (3) if x ~ kz for all positive integers k, then not z > 0. The preference relation is called pure provided it satisfies the follow ng condition: (4) if x ~ 0, then x = 0. Here x ~ - y (x is preferred to y) means that x ~ y but not y ~ x, while x ~ y (x is indifferent to y) means that x ~ y and y ~ x. A convex cone is a set K such that K + K c K and ]0, ~ [ K c K. Now consider a relation ~ on a (real) linear space, and let S = {x: x ~ 0}. I f the relation ~ is transitive and reflexive and satisfies conditions (1) and (2), then S is a convex cone with 0 e S, and (5) x ~ y if and only if x - y e S. Conversely, if S is a convex cone with 0 e S and the relation ~ is defined by (5), then ~ is transitive and reflexive and satisfies conditions (1) and (2). Received September 29, 1964. 191

192

VICTOR KLEE

[September

For a subset X of a linear space, lin X or lin 1 X will denote the union of X with the set of all endpoints of line segments contained in X. We then define lin2X --lin(linlX),...,lin~X--lin(lino-lX) if f l - 1 exists, and linPX--u~oLin~X if fl is a limit ordinal. PROPOSITON. Suppose that S is a convex cone in a linear space E, with Oe S. Let the relation ~ be defined by (7), and let T = {x: x ~- 0}. Then the following four assertions are equivalent: (i) (ii) (iii) (iv)

the relation ~ satisfies condition (3); (-S) fllinScS; ( - T) fl lin S = ¢; ( - T) fl lin T-- ¢.

Proof. Suppose first that condition (3) holds, and consider an arbitrary point x ~ - S N lin S. From the definition of lin S it follows that ]x, s ] c S for some s e S, whence for each positive integer k we have (1 - ( 1 / k ) ) x + ( 1 / k ) se S. But this implies that (s - x) + kx ~ S, whence s - x ~ k( - x) and consequently (by (3)) not - x ;>-0. But - x ~ 0 (for - x ~ S ) , and thus not - x >-0 implies - x N0, whence x ,,~ 0 and x e S. Thus (i) implies (ii). If (ii) holds, then for each x e ( - T) f) lin S we have - x >- 0 (since x ~ - T) and x ~ 0 (since x ~ S by (ii)), whence - x >- 0 ~ - x. But this is impossible, so no such x exists and (ii) implies (iii). Obviously (iii) implies (iv). Finally, let us suppose that (iv) holds, and consider points x and z of E such that x ~ kz for all positive integers k. For all k, we have x ~ (k + 1)z and hence x - kz ~ z. Suppose z ~-0, whence x - kz >-0 and (since ]0,oo [ T o T) i x - pz ~ T for all 2 > 0 < p. In particular, 2x + (I - 2) ( - z) ~ T for all 2 ¢ ]0,1[, and consequently - z ~ lin T. Thus - z e ( - T) f) lin T, and since this is impossible by (iv) it follows that not z ),- 0. Hence (iv) implies (i) and the proof is complete. An n-dimensional utility function for the preference relation ~ is a linear transformation v of E onto 91~ which satisfies the following two conditions for all x , y ~ E : (6) if x ~ y, then v(x) ~ v(y); (7) if x>-y, then v(x) >- v(y). Here the lexicographic ordering is employed in 9ln[3]. When E is finite-dimensional (and conditions (1) and (2) are assumed), condition (3) guarantees the existence of a numerical utility function (Atmaann [1]). This can be traced to the fact that finite-dimensionality of E is equivalent to idempotency of the 'lin' operation for convex sets [6]. When E is finite-dimensional, lin2X = lin X for each convex X = E, and lin X is merely the closure of X in the natural topology of E. In the infinite-dimensional case, condition (3) loses much

1964]

UTILITY FUNCTIONS AND 'L1N' OPERATION FOR CONVEX SETS

193

o f its significance and must be replaced by explicit closure conditions in order to assure the existence o f utility functions [5, 12]. N o w suppose that dim E = I~o, and let ~ be a relation on E satisfying condition (3). A n example of K a n n a i 1-5] and Perles shows that the weak archimedean principle (3) (or, equivalently, the requirement that ( - T ) f l l i n l T = 0 ) is not sufficient for the existence of a utility function. On the other hand, K a n n a i ' s main result asserts that the stronger archimedean principle, ( - T ) N l i n n T = 0 , is sufficient.Q) F r o m a construction in Section 2, it follows that f~ cannot be replaced by any countable ordinal. Indeed, for 1 < 8 < f~ there exists an Ro-dimensional preference relation ~ a such that ( - T ) N linaT = ¢ for all ~ < 8, and yet linPT= E. The latter condition implies that for each element y of the space E of alternatives and for each linear transformation v of E onto 9t n, every element of ~ " appears as the value v(x) for some alternative x which is preferred to y.(2)(a) Thus in a very strong sense, we m a y say that no useful information a b o u t ~ can be conveyed by means of v. (In particular, the only function v satisfying condition (6) is the identically zero function.) 2. Iteration of the 'lin' operation. W h e n X is a convex subset of a linear space E, let us define the order o f X (ord X) as the smallest ordinal n u m b e r ~ such that lin~X = lin X for all 8 > ct, and the level of X (lev X) as the set of all ordinal numbers 8 such that there exists a convex set C with linaC = X but lin*C # X if ~t < 8. It is k n o w n that ord X ~_ f~ [11,13], and that dim E < ~to if and only if ord X < t) for all convex X c E; indeed, if dim E = 1~0 then every countable ordinal is realized as ord X for some convex X c E I l l , 14]. A new and simpler p r o o f of the latter result is given below, and a question raised in [11] is answered by showing that lev E consists of all countable ordinals when E is ~t0-dimensional. In addition, the construction promised in Section 1 is carried out. (1) Here f~ is the first uncountable cardinal. Kannai's Theorem B asserts that a utility function exists if (--T) OclT = ~, where el T is the closure of T in a certain topology zk for E. It is known [4, 7] that lin~'T is the closure of T in the finite topology ~s for E, where a set is Ts-open provided its intersection with each finite-dimensional fiat Fin Eis open in the natural topology for F. But for dim E =< Ro, it can be verified that Kannai's topology *k is identical with the finest locally convex topology zc for E, and it is known [4, 7] that 3o is identical with ~t.

. (2) For let Ty =: {x : x >- y~. Then Tv = T + y, and hence vTv is a subset of ~n with linp oT~ = ~1~n. Since vTy is convex, this implies that oTy = ~}{n. (3) For another example of this phenomenon, let E be the space of all (equivalence classes in the usual way, of) measurable functions on [0, 1], topologized by means ofthemetric

p (x,y) =

f[

Ix(t) - y(t) 1 dt 1 + Ix(t)- y(t)]

(corresponding to convergence in measure). Then dim E = 2~°, but E is a complete separable metric linear space. Say that x ~ y provided x(t) >=y(1) for almost all t~ [0, 11. Then ~ is a pure preference relation, and in fact ( - T) ~ linnT = 0. Nevertheless, vTy = ~ " for each y ~ E and each linear transformation v of E onto ~n. This follows from the fact that E does not admit any nonzero linear form which is nonnegative on T [81.

194

VICTOR KLEE

[September

A convex cone K will be called proper provided K N - K c {0}. LEMMA. I f dim E < g0 and the convex cone K in E is an F¢ set with Oe K, then K is the union of an increasing sequence of closed convex cones. Proof. Let L = K 0 - K , a linear subspac,e of E, and let K + = K , ~ L , a proper convex cone. Then K + is an F~ set and hence is the union of an increasing sequence Z1 c Z2 c ... of compact sets. For each i, the convex hull of Z~ is a compact convex subset of K + and hence the set [0, oo [ con Z i is a proper closed convex cone in K. For each i, let Ji = L + [0, oo [ con Z i. Clearly K is the union of the J~'s, and it can be verified that each J~ is closed. (Use 7.5 of [6] or 2.1 of [9] ). LEMMA Suppose that dim E = go, and that K is an infinite-dimensional convex cone in E with 0 ~ K. Suppose that K is closed or that K is proper and an F¢ set (in the finite topology for E). Then there exist a linearly independent sequence bl, b2,'" of points of K and an increasing sequence Ka c K2 c ... of closed convex cones in K such that K = ~Ji~=tKi and always { b l , ' " , b,} c K , ~ L,, where L n is the linear hull of {bl, ..., b,}. Proof. Let L denote the linear hull of K, whence K contains a basis {bl, b2, "" } for L. For each n, let C, = K N L,. If K is closed, we simply take K , = C,. Suppose, then, that K is proper and is an F,, set. It follows from the preceding lemma that for each n, C, is the union of an increasing sequence C~ c C 2 c - . . of closed convex cones such that {bx,...,b,, } cC~. For each n, let K. =

+

+...

Then it is evident that K is the union of the the cones K , must be closed [9].

+

Ki'S, and since K is proper each of

TI-IEO~M. Suppose that E and K are as in the preceding lemma. Then there exists a proper convex cone K' such that K' is an F~ set, O ~ K ' ~ K , and lin K ' = K . Proof. Let the closed convex cones Ks be as in the lemma, and for each i let K~ = K ~ + ] 0 , oo [b~+l • Let K ' = {0} U [,.Ji~K;. Since K~ = K~ = ... and since each set K; is a convex cone, it is evident that K ' is a convex cone. Also, we have oo

oo

K = i=[~Jl= Ks = i=1 ['j lin K[ ~ lin K', and it remains only to show that lin K ' c K. Consider an arbitrary point x o f lin K'. There exists y e K ' such that Ix, y] ~" K', and then for each i there exist r(i), ks ~ K,(l, and z~ > 0 such that

(,_

1964]

UTILITY FUNCTIONS AND 'LIN' OPERATION FOR CONVEX SETS

195

Further, there exists n such that {x,y} c Ln, whence r(i)< n for all i and k, + z,b,(o+ 1 c Kn. Since K. is closed, it follows that x e K. = K and the proof is complete. COROLLARY. I f X is an ~o-dimensional convex F, set, then lev X includes all finite ordinal numbers. Proof. We may assume that the affine hull H of X is a hyperplane in E ~ {0}, where E is an l%-dimensional linear space. Let K o = {0} U ]0, ov [X, an F, proper cone in E, and consider an arbitrary finite ft. By successive applications of the Theorem we can produce Fo proper convex cones K ~ such that always lin K ~ = K ~- ~ and Let X P= K PN H. Since lin~K g = K o but lin~- ~KP#K 0, it follows that lin°X~= X but lin ~- ~Xp # X. Thus fl ~ lev X and the proof is complete. COROLLARY. Supposethat X is an ~o-dimensional convex F~ set with 0 ~ X. I f X is the direct sum of ~o isomorphs of X, then lev X consits of all countable ordinal numbers. Proof. Let .~ denote the set of all ordinal numbers B for which there exists a convex F~ set Y having linBY= X but lin=Y# X if ~ < ft. From the proof of the preceding corollary, it follows that [-1,o [ ~ ~ and that fl ~ ~ implies fl + I e ~'. From a result in [-11] (p. 233) in conjunction with the "direct sum" property of X, it follows that if fl < f~ a n d , ~ ~ for all a < #, then # E ~ . Hence lev X = [0, fl[" by transfinite induction. COROLLhgY. I f E is a linear space, then

lev E =

¢

if dim E < ~ o ]

[1,fl[

if dim E = ~ o t

"

if dim E > Ro COROLLARY. Suppose that E is an l%-dimensional linear space and fl is an ordinal number with 1 < fl < f]. Then there exists a pure preference relation on E such that the convex cone T = { x : x > - O } is an F¢ set and linBT= E, although ( - T) fl lin=T= 0 for all ~ < ft. Proof. Let M denote the set of all ordinals fl ~ ] 1, f~[ for which the statement is true. We note first that 2 ~ M. Indeed, let {bl, b2." } be a basis for E and let K be the set of all points x of the form x = I27=12~b~ with 4. > 0. (That is, the last nonzero coordinate of x is positive.) Then K is a proper convex cone and is an F, set, so the Theorem guarantees the existence of an Fo|convexl cone K ' such that li K' = K UJ{O}.

196

VICTOR KLEE

[September

Let x ~ y provided x - y e K ' U {0}. Then ~ is a pure preference relation for which T = K ' , l i n l T = K 0 {0}, and lin2T=lin K = E . It follows that 2 ~ . Now suppose that 2 < y < fZ and that fl~ ~ whenever 1 p a pure preference relation on Ep such that T~ is an F~, set, linPT~ = Ea, and ( - T~) fl lin*T~ = ~ for all ~ < ft. We may assume without loss of generality that E is the direct sum of the spaces E r Let Tv be the direct sum of the convex cones T~, and say that x >~ y provided x - y a Tv U {0}. Then the easily verified properties of Tv show that 3' E ~ . It now follows by transfinite induction that .~ = ] 1, DI, so the proof is complete. 3. Unsolved problems. (a) If C is a convex set in an t%-dimensional linear space E, then lin C is an F~ set. It follows, for a convex set X ,'- E, that lev X = ¢ unless X is an F~ set. We have seen that lev X = [1, to[ for every infinite-dimensional convex F,, set in E, while for certain sets of this sort, lev X = [1,~[. Is the latter equality valid for every ~o-dimensional convex F~ set X? (b) Let E and Tbe as in footnote(3), so that vT=F whenever v is a linear transformation of E onto a finite-dimensional linear space F. Is the same conclusion valid (for this particular choice of E and T) when dim F = t~o?(4)

REFERENCES 1. R. J. Aumann, Utility theory without the completeness axiom, Econometrica 30 (1962), 445--462 and 32 (1964), 210-212. 2. P. C. Hammer, Maximal convex sets, Duke Math. J. 22 (1955), 103-106. 3. M. Hausner, Multidimensional utilities, in Decision Processes, edit. by Thrall, Coomb and Davis, Wiley, New York, (1954) 167-180. 4. S. Kakutani and V. Klee, The finite topology of a linear space, Arch. Math. 14 (1963) 55-58. 5. Y. Kannai, Existence o f a utility infinite dimensional partially ordered spaces, Israel J. Math. 1 (1963), 229-234. 6. V. Klee, Convex sets in linear spaces, Duke Math. J. 18 (1951), 443-466. , Convex sets in linear spaces. III, Duke Math. J. 20 (1953), 105-112. 7. (4) In this connection, the following consequence of a theorem in [10] (p. 58) may be useful If Tis a convex cone in a linear space E and if E admits a linear transformation v onto a space F of countable dimension such that v T # F , then there is a linearly ordered set ( ~ , ~ ) o f nonzero linear forms on E such that the following conditions are all satisfied: (i) 1 --< c a r d # _< ~o~ (ii) for'-each x ~ E-',q~(x) ~ 0 for all but finitely many ~0~ # ; (iii) for each x ~ T, either 9~(x) = 0 for all ~ or there exists 9 ' E # such that 9'(x) > 0 but 9~(x) = 0 for all 9~ -< ~0". The theorem in [101 is concerned with the structure of seraispaces [2, 10], a notion which maybe employed to define various infinite-dimensionalanalogues of the lexicographie ordering in ~R=.

1964] 8. 9.

UTILITY FUNCTIONS AND 'LIN' OPERATION FOR CONVEX SETS ., , , ., .,

197

Boundedne ss and continuity of linear funct ionals , D u k e Math.J. 22(1955),263-270. Separation properties o f convex cones, Proc. Amer. Math. Soc. 6 (1955), 313-318. The structure o f semispaces, Math. Scand. 4 (1956), 54-64. Iteratio~ o f the "lin" operation fGr convex sets, Math. Scand. 4 (1956), 231-238. On representing a reference relation by means o f a set u ility functions.

10. 11.---12.~ (to appear). 13. O. M. Nikodym, On transfinite iterations o f the weak linear closure o f convex sets in linear spaces. Part A. Two notions oflinear closure, Rend. Circ. Mat. Palermo (ser. 2) 2 (1953,) 85-105. 14. , On transfinite iterations o f the weak linear closure o f convex sets in linear spaces Part B. An existence theorem in weak linear closure, Rend. Circ. Mat. Palermo (ser. 2) 3 (1954), 5-75. UN~V~TY OF W ~ O T O N BOEINO SC~NTn~c R ~ R C H LABORATORIES, Sa~rrL~, WASmNGTON, U.S.A.

INVARIANT SUBSPACES OF A MEASURE PRESERVING TRANSFORMATION* BY

S. R. FOGUEL ABSTRACT

We consider, in this note, some invariant subspaces of a unitary operator induced by a measure preserving transformation. For these subspaces two problems are studied: a. Is the subspace generated by characteristic functions ? b. When is an invariant subspace a reducing subspace ? 1. Introduction. Let (f~, ]~,# ) be a measure space with #(~) = 1. Let q~ be a one-to-one measure preserving transformation. The transformation q~ induces a unitary operator U, on L2(f~, ~,, I~). We shall consider the following subspaces of L2(f~, ~ , p ) : Ho = { x l x ~ L 2 , weak

lim Unx=O}

H1 = H~ H 2 = span H~, where H~ = {xl x ~ L 2 , lim sup

I(u x,x)l--II x It

H3 = {x [ x ~ L 2, the orbit Unx, n = 1, 2, ..., is conditionally compact}. Let us summarize some properties of these spaces: 1. The subspaces reduce the operators U. Theorem 3.1 of I-2]. 2. H a c H 2 c H 1. See Theorem 1.3 of 12]. 3. The subspace H3 is generated by eigenfunctions of U. This is a well-known result (see 16] page 24) let us sketch its proof: Clearly every eigenfunction belongs to H a. Let x be orthogonal to all eigenfunctions of U. By [5] page 40 there exist dense (complements of sets of zero density) sequences n~k) with lim(U n'~k~x, UkX) = 0. Since the intersection of two dense sequences is dense it is possible to emplyo the diagonal method to find a sequence n~ with lim(U~'x, Ukx) = 0, k = 1,2, .... Thus weak lim Un'x = O. Let y be any element of H3. We may assume that U"'y (or a subsequence) converges strongly to z. Then:

II u*n'z - y II2 = 211 y II2 - 2 R e ( z , u " y ) ~ O. Therefore

(x, y) = lim (x, U*~'z) = lim ( U~'x,z) = O. * This work was partially supported by N.S.F. Grant No. GP 2491. Received October 2, 1964. 198

1964]

MEASURE PRESERVING TRANSFORMATION

199

4. The operator U is strongly mixing if and only if H 1 = constant functions, and is weakly mixing if and only if H 3 = constant functions. See [5] for definitions of mixing properties. 2. The space H 2. Let xeriC, then there exists a subsequence, ni of the integers, such that lim U"x = x. (Theorem 1.3 of [2]) Define K = {y I lim U"'y = y) = {y I lim (Un'y, y) = It Y 112)• Thus K = Hi. If y is a function in K then so are the real and imaginary parts of y. Also if y is a real valued function in K then so is its absolute value: lim (U" l y],] yl)>__ lim]

(u"'y,y) I = II Y 112= IllYl II2

Thus K satisfies the conditions of Lemma 1 of [3]. Therefore K is spanned by the characteristic functions that belong to it. This also proved: THEOREM 2.1. The set Hi is generated by the characteristic functions that belong to it. Given a set A e ~ let I(A) be its characteristic function. Then I(A) e H i if and only if lim sup/~(~-".4 n A) =/~(A). D. Austin suggested the following conjecture: I f lim sup p(9-"A r~A)
200

S.R. FOGUEL

to y then y ~ M. We wish to show that this implies that (x, x 2 ) = Ux2 IIz -O. Let x = Yl + Y2 where (Yl, U"x2) = 0 n = O, + 1, + 2, ... and Y2 is in the subspac¢ generated by U"x2 n = O, + 1, + 2,.... It is enough to show that Y2 = O: By assumption lim (U"y2,x2)= 0 hence lim

(U'Y2,UkX2)=

n-4OO

lira ( u n - k y 2 , x 2 ) ~---0

k = O , "4" |, "~ 2, " " .

n--~ OO

By taking linear combinations and passing to limit one gets lira (U"Y2, Y2) = 0 or y2e Ho(U). On the other hand Y2 e HI(U) since x2 ¢H1 and U"x2 ¢H1 for every n, thus Y2 = 0. REMARK. We have reproduced in this proof, for the sake of completeness, parts of Theorem 1 of [4] and Theorem 3.1 of [2]. COROLLARY. Every invariant subspace of HI reduces U. In Corollary of Proposition 3 of [1] this result is proved for subspaces of Ha. If x e H1 then U~x ~ M for any integer k, since M is invariant under U k. A similar characterization exists for HI. THEOREM 3.3. Let K be the close convex hull of the weak limits of the sequence U"x. Then x ~ H~ if and only if x ~ K. Proof. If x e HI then it is the strong limit of U"tx, for some subsequence of the integers, by Theorem 1.3 of [2]. Conversely if x e 'HI let lira sup I (U"x,x) ] = ~ < ]] x II2 If y l . . . y~ are in K and as are positive numbers whose sum is 1 then

l

a,I

< [[ x][ 2

and no such s u m can approximate x.

REFERENCE 1. R. L. Adler, lnvariant and reducing subalgebras o f measure preservlngtransformations, Trans. Amer. Math. Soc. 110 (1964), 350--361. 2. R. S. Fogel, Powers o f a contraction in Hilbert space, Pacific J. Math. 13 (1963), 551-562. 3. , On order perserving contractions, Israel J. Math. 1 (1963), 54-59. 4. ., Weak limits o f powers o f a contraction in Hilbert space, Proc. Amer. Math. Soc. (to appear). 5. R. P. Halmos, Lectures on ergodic theory, Math. Soc. Japan, No. 3 (1956). 6. K. Jacobs, Ergodentheorie, Springer, Berlin 1960. NORTHWESTERN UNIVERSITY, EVANSTON,ILLINOIS AND THE HEBREW UNIVERSITYOF JERUSALI~M

A SELECTION THEOREM BY

JORAM LINDENSTRAUSS(t)

ABSTRACT

It is showa that under certain assumptions the existence of a continuous selection on cvery compact subset of a metric space implies the existence of a continuous selection on the whole space. An application of this result to a problem concerning the extension of compact operators is given.

Let ~b be a m a p from a metric space M to the set 2 a consisting of all nonempty subsets of a Banach space B. Wc say that t~ admits a continuous selection if there exists a continuous function f from M to B (in the norm topology) such that f ( m ) e c~(m) for every m e M. This notion was investigated by E. Michael in a long series of papers. Wc shall here use one of Michael's results to prove the following THEOREM. Let M be a metric space and let B be a Banach space. Let c~ be a map from M to 2 a such that qb(m) is a closed, convex and separable subset of B for every m ~ M. Assume that for every countable compact subset K of M the restriction of c~ to K admits a continuous selection. Then c~ admits a continuous selection. NOTATIONS. Let Y be a metric space, let y o e Y and let r->_ 0. The cell {y; y e Y, d(y, yo) <_ r) is denoted by Sy(yo, r). ,4 denotes the closure of the set A. Proof of the Theorem. Let m E M. For every countable compact subset K of M containing m, put ~ ( m , K ) = {x; there is a continuous function f from K to B with f ( m ) = x and f ( k ) e ~(k) for all k e K.} By our assumptions ~b(m,K) ~ t~ for every K containing m. It is easily verified that ~(m, K) is a convex subset of ~b(m). Let {K~)~°=1 be a sequence of countable compact subsets of M such that m e {')l~ 1 Ks. Let oo

K =~

U (Kt n SM(m,1/i)). l-I

Received October 28, 1964. Research supported in part by th~ National Science Foundation, U.S.A. (NSF-GP-378). 201

202

JORAM LINDENSTRAUSS

[September

K is a countable compact set containing m and we claim that oo

(1)

~b(m,K) c

n

~k(m,Ks).

Indeed, let f be a continuous function from K to B such that f(k)E ¢~(k), for aU k ~ K. Put x = f(m) and fix an i, 1 =< i < oo. We shall show that x e ~b(rn, Ks). By our assumptions there is a continuous function g from Ks to B such that g(k) ~ c~(k) fo; ~ ]]k ~ K s. Let ~ (k) be a continuous real-valued function on Ks such that 0 ~ ~(k) <= 1 for every k, ~(m) = 1 and ~(k) = 0 if k ~ SM(m, 1/0. Let F be the function from K, to B defined by

ct(k)f(k) + (1 - ct(k))g(k) if k E K s C~ Su(m, 110 F(k) g(k)

if k ~ K s and k~ SM(m, 110.

It is clear that F is continuous, F(m) = x and F(k) ~ dp(k) for every k e K s. This proves (1). Since q~(m) is separable, it follows from (1) that

~b(m) =

n

$(m, K) ~ ¢1.

rnEK

(The intersection is taken over all countable compact K which contain m.) We show next that the mapping m ~ ¢(m) from M to 2 B is lower semi-continuous in the terminology of Michael [2]. That is, we have to show that, for every m ~ M, every x ~ if(m) and every sequence {ms}~.°=1 c M with ms ~ m, there are x s ~ 4/(ms) (i = 1, 2, ...) satisfying xs ~ x. Suppose this were false. Then there are an m ~ M , an x ~ ( m ) , a sequence rn t --* m and an e > 0 such that ~(m,) n S~(x, e) = ¢ for every i. From the fact that ~b(mi)n SB(x, ~) is separable and from (1) we infer that for every i there is a countable compact set Ks, with m s ~ K s such that (2)

¢/(m~, Ks) ~ SB(x, ~) = O .

The arguments used above show also that if K[ and K[' are two countable compact sets such that ms s K~ n K~' and such that there is a neighborhood G of ms satisfying G n K~ = G n K " then g/(mi, K~)= ~(ms, K~'). Hence it is possible to choose the sets Ks which satisfy (2) so that also Ks c SB(m~, 1]i). Let K = {m} u U ~o=1 Ks. K is a counta le compact set and hence there is a continuous f u n c t i o n f f r o m K to B such that ]If(m) - x I] < ~/2 a n d f ( k ) ~ ~(k), k ~ K. Hence ]If(ms) - x II < e for large enough i and this contradicts (2). We can now apply Theorem 3.2" of [2] to obtain a continuous function f from M to B with f(m) ~ ~b(m) c r~(m) for every m ~ M. This concludes the proof of the theorem.

1964]

A SELECTION THEOREM

203

The theorem will hold also in more general situations. For example the proof we gave above remains valid if B is a general Fr6chet space (since Theorem 3.2" of 12] is valid for such B). Using other selecti on theorems of Michael it is possible to obtain results similar to the theorem proved here. We shall not go here into the details of the possible generalizations. We give only a few examples which show the role of some of the assumptions appearing in the statement of the theorem. EXAMPLE 1. Let B = M be the real line R. For every r ~ R let ~b(r) be the set of all the integers which are greater than r. For every compact subset K of R the restriction of ~b to K admits a continuous selection, but q~ itself does not admit a continuous selection. Here qS(r) is closed and separable for every r but not convex. EXAMPLE 2. Let I be an uncountable set and let B = M = 1~(I) (the space of all real-valued functions 0e defines on I and satisfying x,l 0)l--I1 1/< oo) For 0,~ ll(I) denote by s(~) the set {i; i e I , ~(i) ~ 0}, and put

,(=)={a;

s(a)ns(=)= ¢, Ilall =1,

fl>0).

Every ~b(~)is closed and convex. If X is a separable subspace of M then there is an io ~ I such that ~(io) = 0 for every oce X. Let Po be the elementt of ll(I) defined by Po(io) = 1 and/~(i) = 0 if i # io./70 ~ ~b(~) for every ~ ~ X and hence the restriction of ~b to X admits a continuous selection (the function identically equal to #7o). However ~b itself does not admit a continuous selection. To see this suppose that f(~) e~b(~) for every ~ E 11(I), and let ~o =f(0). Then C~o/n~ 0 but [If(°~o/n)-f(0)I[ = 2 for every n (since IIs(o)II = Ilf(~ol n) II = 1 and s(f(O)) n s(f(ocoln)) = ¢ ). EXAMPLE 3. Let M be the subset of R 2 (the Euclidean plane) consisting of the points (1/n, 1]m), 1 < n,m < oo, the points (l/n,0) 1 _-.6n < oo and the origin (0,0). Let B = R 2. Let $(1/n, l/m), 1 < n, m < oo, be the line segment joining the point (0, l/n) with the point (1, 0), let q~(l/n, 0), 1 < n < oo, be the line segment joining the point (0, 0) with the point (1, 0) and let ~b(0, 0) = {(0,0)}. ~b(p) is a compact convex set for every p ~ M. It is easily checked that the resvriction of q~ to every convergent sequence K in M admits a continuous selection but ~b itself does not admit a continuous selection. We shall apply now the theorem which was proved above to a question which was considered in Chapter VII of [1]. Let X c Y be a Banach spaces. We say that there is a continuous norm-preserving extension (C. N. P. E) map from X* to Y* if there is a continuous function f from X* to Y* (in the norm topologies) such that for every x*~ X*, we have [if(x*)I[ = [[x* [[ and the restriction of S(x*) to X is equal to x*. The following corollary is an immediate consequence

204

JORAM LINDENSTRAU$$

of the selection theorem proved here and the familiar representation o f compact operators with range in a C(K) space (cf. also 11, Lemma 7.2]). COROLLARY.Let X c Y be Banach spaces and assume that for every x*~X* the set of its norm-preserving extensions to Y is separable (in the norm topology of Y*). Then the following statements are equivalent. (i) There is a C. N. P. E. map from X* to Y*. (ii) For every compact Hausdorff space K, every compact linear operator from X to C(K) has a compact and norm-preserving extension from Y to C(K). (iii) For every countable compact metric space K every compact linear operator from X to C(K) has a compact norm preserving extension from Y to C(K). We do not know whether the corollary will still hold if we drop the separability assumption appearing in its statement. I am very grateful to Professor E. Michael for some helpful comments. Remarks added in proof. (1) It is easily seen from the proof of the theorem that it will still hold if we replace the assumption that tk(m) is separable for every m by the assumption that q~(m) is Lindelof in the w topology for every m. The same is true for the corollary. In particular the corollary holds whenever Y/X is reflexive even if we drop the separability assumption. (2) In the selection problem appearing in the corollary the sets q~(m), m ~ M , are mutually disjoint (to different functionals on X correspond disjoint sets of extensions to Y). In example 2 the sets qS(00 are very far from being disjoint (any countable number of them intersect). One may be inclined to think that the separability assumption in the theorem may be removed or relaxed if we make the additional assumption that the sets ~b(m) are mutually disjoint. However, as pointed out by E. Michael, this is not the case--in fact every selection problem can be reformulated as a selection problem with disjoint sets ~(m) Let tk: M ~ 2 ~ with M a metric space and B a Banach space. Let Bo be a Banach space containing M (isometrically). Define ~: M ~ 2 ~+B° by putting ~k(m) = {y; y = (x, m), x ~ ~b(m)}. Then ~k admits a continuous selection iff admits a continuous selection and the sets ~b(m) are mutually disjoint,

REFERENCES 1. J. Lindenstrauss, Extension of compact operators, Memoirs of the Amer. Math. Soc. 48 (1964). 2. E. Michael, Continuous selections 1, Ann. of Math. 63 (1956), 361-382. UNIVERSITYOF V~/ASHINOTON ~EATTLE~ V~/ASHINGTON

BERKSON'S THEOREM* BY

DANIEL ZELINSKY

ABSTRACT

We give a new proof of the theorem that Amitsur's complexfor purely inseparable field extensions has vanishing homologyin dimensionshigher than 2. This is accomplished by computing the kernel and cokernel of the logarithmic derivative t ~ Dt/t mappingthe multiplicativeAmitsur complex to the acyclicadditive one (D is a derivation of the extensionfield).

In [1], Amitsur introduced complexes ~ ( F / C ) and cg+(F/C) definable for any commutative algebra F with unit over a commutative ring C (with the same unit). The first has cohomology groups denoted by Hn(F/C). The second has cohomology groups which usually vanish, so need no special notation. THEOREM. If F is a purely inseparable extension field of C then Hn(F / C) ---0 for n > 2 . This theorem was proved in [8; Theorem 6.1] (the restriction there to finite exponent is unnecessary) by a reduction, sketched below, to the case of extensions of finite degree and exponent one. This case is then handled by a theorem of Berkson [3]. However, the same reduction reduces to the case of simple extensions of exponent one. By treating this special case explicitly, the present note achieves a slightly shorter proof than Berkson, avoids the machinery of regular, restricted Lie algebra extensions, and makes more transparent where the restriction n > 2 enters. S. Yuan in his Ph.D. dissertation (Northwestern University 1964) has extended the method in the present note to prove most of the results in [8] as well. Thus the appeal to [8] which we make for our reductions in fact need not appeal to any techniques (specifically, spectral sequences) less elementary than those already used here. We begin by recalling the definitions of Amitsur's complexes. They both arise from the (co-)semisimplicial object )

F ,----'~ F ®c F

~- F ®c F @c F

7...

Received July 22, 1964. * This research was supported by National Science Foundation grant NSF GP 1649. 205

206

DANIEL ZELINSKY

[September

We shall denote the repeated tensor product F ® c ' " ® c F by F ~ and the maps F"--. F n+ ~ by %, s~, ..., e,; these maps are C-algebra homomorphisms defined by si(xl ® ... ® x,) = xl ® ... ® x i - l ® 1® xi® ... ® xn and satisfy the identities of face maps in semisimplicial complexes [-7; (3.3)]. Degeneracy maps also exist, but play almost no role in the present paper. If we consider the 8's as homomorphisms of the additive groups of these F", we can add and subtract them to form a boundary operator d + = eo - sl + "" + ( - 1)~e,. This forms a complex called cg+(F/C). Similarly the e's induce homomorphisms of the multiplicative group U ( F " ) o f units o f F ~. The complex Cg(F/C) consists of the groups {U(F ~) ] n = 1,2, ... } with boundary maps d = eo • (1/el)" s2 . . . . . (en)±1 from U(F') to U(F"+ I). We shall need a third complex ~ , which is formed of the additive groups of F z, F3, ... but with boundary map from F" to F "+1 defined by d + - So = - (sl - s2 + "'" + s,) We agree to label the dimensions in c¢, ~ , and c¢ + so that the n-dimensional cochain groups are U(F"+I), F "+2, and F n+1 respectively. Thus in all cases the boundary of an n-cochain involves n + 2 s's. If C is a field, then :¢+ and ~ have homology groups equal to zero in all positive dimensions 17; Lemma 4.1] because a contracting homotopy may be defined by s(xl ® " " ® Xn) = XX ® " " ® Xn_ 2 ®Xn- lfl(X~) where fl: F ~ C is any C-linear map with/~(1) = 1. Furthermore, H°(fg +) and H ° ( ~ ) a r e isomorphic to the additive groups of C and F, respectively. In fact, ~ may be identified with

c~+(F ® F / C ® F). Note that in [7] the complexes g' and cg + were defined to have nonzero terms in dimension - 1, designed to make Cg+acyclic in all dimensions. The present convention is somewhat more standard and more appropriate. Since every purely inseparable extension of a field C is a direct limit of extensions of finite degree, and since H"(lim Fi / C) = lim H"(Fi / C) (cf. [7; p. 345]), it is sufficient to prove H"(F / C) = 0 when F Is purely inseparable and of fimte degree over C. This can in turn be reduced to the case of simple extensions F = C(0t) with ape C (p is the characteristic of C): Every purely inseparable F of finite degree is the top of a tower C = F o c F 1 c ' " c / 7 , = F with F~+I =Fi(0~t), ~tiPeF~, and by 1.8; Theorem 4.3] there is an exact sequence •

---'k

.

H"(F~ / C) ~ H"(F~+ I / C) ~ H"(Ft + I /F,) so that if we know H"(Fi+t/F3 = 0, an induction on i will prove H " ( F / C ) =0. PROPOSITIO~r. I f F = C(~), otPe C where F and C are fields, there is an exact sequence of complexes

1964]

BERKSON'S THEOREM 2 0-~eo~(F/C) ~ ~ ~ ~+(F/C)~O,

207

2 is of degree - 1, ? is of degree O, and ~o¢~, ~ , and¢~+(F/C) have homology groups equal to zero in all positive dimensions. COROLLARY.Hn(F / C) = 0 for n > 2. Proof of Corollary: The exactness of 0 ~ K e r ~,-~ ~ - ~ + - ~ 0 implies Hn-2(~ +) --. Hn-t(Ker ~)-~ H n - l ( ~ ) exact. If n > 2, the theorem asserts that the extreme terms of the latter sequence vanish, so H " - t ( K e r ~ ) = 0 . Then 0 --. eo@-~ $' ~ Ker ? -~ 0 exact imples H"(eo~) ~ H"(F/C) -~ H ~- l(Ker ~) exact. Thus H"(F[C)= O. Proof of Proposition. Let D be the derivation of F over C defined by D(ct) = 1, i.e., D( Xci~¢t) = ~,icp~~- 1 (this derivation has D p -- 0 and Ker O = C). Extend D to a derivation D~ of F" over C @ F n - t by defining O~(xx ® ' " ® x,) = D ( X l ) (~ X 2 (~"" ~

X n.

DEFINITION. If t is a unit in F", define 2~(t) = D~(t)/t; and 2 = {;t~I n = 1,2, ... } As in elementary calculus, 2,(tt')=2n(t)+2~(t'); furthermore, 2,+l(ezt) = el2~(t) for i > 0, and 2,+1(Cot)= 0 since D(1)= 0. Thus 2: ~ ( F / C ) ~ ~ is a homomorphism commuting with the boundary maps: 2d = ( d + -Co)2. That is, 2 is a mapping of complexes. To compute Ker 2 we need Ker D~, since D,(t)/t = 0 if and only if Dn(t) = 0. Tensoring the exact sequence 0 ~ Ker D ~ F ~ F with F ~- t we find that Ker Dn = ( K e r D ) ® F n-t = C ® F "-1 =~o Fn-t. Thus Ker 2 =eo~. Now compute Im 2. If q ~ F ~, let L(q) denote the mapping F~---~Fn produced by multiplication by q. If q = D,(t)/t, then O, + L(q) = L(t)-l(L(t)O~ + L(On(t) ) ) = L(t)-lO,L(t), the last equality merely expressing the derivation property of Dn. Therefore, (D~ + L(q) )P = L(t)- 1D,PL(t) = 0 because D o = 0. Conversely, if (Dn + L(q) p) = O, then Cartier proved, inter alia (t! that the ideal of Fngenerated by Ker (D,, + L(q)) is all of F". In our case, F n is a local ring (there is only one homomorphism of F ~ to a field; it is the natural one F"-~ F), so Ker ( D , + L(q)) must contain a unit, u. If t = u - t , we have D n ( O = - u - 2 D ~ ( u ) = - t 2 ( - q u ) = q t , so q = D.(t)/t. Thus Im 24 = {q ~F~l (On + L(q)) ~= 0} However, using an old calculation ([4; Ch. 2, (36)], [5], [6]) and Dff= 0, we have (1) D+ L (q))o=0 is all that is needed to make F n a"regular, restricted module" over the regular, restricted Lie algebra A of C-derivations of F. Cartier proves that every such module is FW where W is the submodule on which A acts as 0 [4; Chapter 2, Proposition 3]. Here W Ker(D + L(q)) and F acts as L (F(~ Cn- 1),so certainly FnKer (Dn + L(q) ) = F5

208

DANIEL ZELINSKY

[September

(D. + L(q))" = L(O~-l(q) + qn). We have now shown Im ,~ = {qeF~l D~-l(q)+ qn ~0}. DEFINITION. If q e F ~, define y~(q) = eo 1 (D~P-I(q) + qP)~F n-l, and = { ( - 1 ) " ? ~ n = 2 , 3 , . . - ] mapping ~ to 5 +. Note that D~- l(q) e e0F~- 1 because D~(Dp- l(q) ) = D~(q) = 0 and Ker D, = SoF'- 1 as before; and that q P ~ C ® . . . ® C c C®F~-I = soF"-l.! Thus ~, is defined, and is ~,single-valued because % is a monomorphism. To show y is a mapping of complexes ~ - * 5 +, recall that D,s~ = szD, or 0 according as i > 0 or i = 0, so the same is true with D~ replaced by D~-1. The simplicial identity eoe~_1 = etso gives s~_lSo 1 eolSt on Im e0, and hence s l _ l s o l D n p - 1 = % i D a - I s l for i > 1 . Thus d+(solD~-l)=(eolD~-l)(eo-d+). Besides, since qP~C ~, s~qP=soq p for all i; so d+(solq p) = ( ( e o - d + ) q ) p . Thus both q~solD~-l(q) and q -+ eolq p are mappings of ~ to 5 + which anticommute with the boundary maps; so also does their sum. It follows that { ( - 1)"y~} commutes with the boundary map. Since s0 is a monomorphism, Ker y = {qeF"] D~-l(q)+ qV= 0} = I m 2~. To complete the exact sequence of the proposition, it remains to prove Im y = 5 +. Given y e F "-l, we can produce s e F ~ such that y~(s) = eol(D~-l(s) + sp) ~ y. It suffices to take =

s = - g v - l ® y + l®ctV-ly where ~P- 1~ F multiplies y E F ~- 1 using any of the obvious F-module structures on F "-1. For then D~-l(s) = - (p - 1)!® y + 0 = 1® y = toy and sp = ( _ ~p-l)p ®yp + 1® (~P-I)Pyn = 0 since (~p-1) e C and the tensor product is taken over C. The acyclicity of ~ and 5+was pointed out above. That % 5 has vanishing homology is well-known for semisimplicial complexes. ~o I maps the complex So5 isomorphically to a complex ~ ' which is the multiplicative analog of ~ , viz., the complex S but with boundary sl(1/e2)e3 ".'. This ~ ' is acyclicl because the first degeneracy xl® ".. ®x,--. xlx2®x3® "" ®x,, is a contracting homotopy. This completes the proof. REMARKS. 1. Without reference to [8] we could use the techniques in the proof of our proposition to get Berkson's full theorem, which allows any F which is purely inseparable of exponent one and finite degree. In this case 2n(t) = D,(t)/t would have to be considered for all D, induced by all derivations D of F over C; i.e., 2 maps 5 into th acyelie additive complex {Horny(A, F~)} where A is the derivation algebra of F over C, thought of as a left F-module. The Cartier operator analogous to y is actually designed to fit this more general situation.

1964]

BERKSON'S THEOREM

209

2. By using the same computations, one can compute HZ(F/C). Just as for n > 2, H2(F/C) ~- H t ( K e r 7) and H ° ( ~ ) ~ H ° ( C ~ + ) ~ H t ( K e r ? ) ~ H t ( ~ ) = 0 is exact. Since H°(C~+) = C + and H ° ( ~ ) = F + (where we denote the additive group of C by C+), this gives the same result as in [6; Theorem 7]: H2(F / C) = C +/7F + where yF + = {Dp-I(x) + x° [ x ~ F}.

REFERENCES 1. S. A. Amitsur, Simple algebras and cohomology groups of arbitrary fields, Trans. Amer. Math. Soc. 90 (1959), 73-112. 2. S. A. Amitsur, Homology groups and double complexes for arbitrary fields, J. Math. Soc. Japan 14 (1962), 1-25. 3. A. J. Berkson, On Amitsur's complex and restricted Lie algebras, Trans. Amer. Math. Soc. 109 (1963), 430-443. 4. P. Cartier, Questions de rationaliM des diviseurs en g~ometrie algdbrique, Bull. Soc. Math. France 86 (1958), 177-251. 5. N. Jacobson, Abstract derivations and Lie algebras, Trans. Amcr. Math. Soc. 42 (1937), 206-224. 6. G. Hoehschild, Simple algebras with purely inseparable splitting fields of exponent 1, Trans. Amer. Math. Soc. 79 (1955), 477--489. 7. A. Rosanberg and D. Zelinsky, On Amltsur's complex, Trans. Amer. Math. Soe. 97 (1960), 327-356. 8. A. Rosenberg and D. Zelinsky, Amitsur's complexfor inseparablefields, Osaka Math. J. 14 (1962), 219-240. NORTHWESTERNUNIVERSITY EVAmTON, ILLINOIS,U.S.A.