CHANGE OF BASIS, MONOMIAL RELATIONS, AND PtsBASES FOR THE STEENROD ALGEBRA KENNETH G. MONKS July 1995 Abstract. The relationship between several common bases for the mod 2 Ste* *enrod algebra is explored and a new family of bases consisting of monomials in * *distinct Pst's is developed. A recursive change of basis formula is produced to c* *onvert between the Milnor basis and each of the bases for which the change of ba* *sis matrix in every grading is upper triangular. In particular, it is shown that the* * basis of admissible monomials, the new Pstbases, and two bases due to D. Arnon, are all bases having this property, and the corresponding change of basis for* *mula is produced for each of them. Some monomial relations for the mod 2 Steenrod algebra are then obtained by exploring the change of basis transformation* *s. 1. Introduction There are many descriptions of bases for the mod 2 Steenrod algebra, A; in the literature. In addition to the classical basis of admissible monomials, there a* *re the bases developed by Milnor [Mil] and Wall [Wall] as well as the more recent bases developed by D. Arnon [Arn ] and R. Wood [Wo ]. In this article we investigate the relationship between these bases, and add a family of new bases consisting * *of monomials in distinct Pts's to the existing collection. These bases are all des* *cribed in detail in Section 3. Given so many different bases, a natural question to ask is: how can we conve* *rt from one basis to the other? Since almost all of the bases under consideration* * are described in terms of unevaluated products of A, such simple linear algebraic i* *nfor- mation actually can yield information about the product structure of A as well. All of the bases we consider can be described in terms of unevaluated monomia* *ls in Milnor basis elements. Thus it is a simple matter to convert from one of these * *bases, call it B, to the Milnor basis, BMil, by using the product formula (3.1) develo* *ped by Milnor [Mil]. A difficulty arises when trying to convert in the other direction* *: from ___________ 1991 Mathematics Subject Classification. Primary 55S10, 55S05; Secondary 57T0* *5. Key words and phrases. Steenrod Algebra. 1 2 KENNETH G. MONKS the Milnor basis to back the basis B. Having such a formula for every basis wou* *ld then allow us to convert between any two bases, indirectly, via the Milnor basi* *s. A brute force approach might be to compute the change of basis matrix, M, from B to BMil in a given grading using the Milnor product formula and compute M-1 to obtain the change of basis matrix in the opposite direction. But this appro* *ach is extremely inefficient and is unworkable in all but the lowest gradings where* * the vector space dimension is quite small. Suppose, however, that we have the following situation. Definition 1.1.Suppose there exists orderings, and _; of bases B and BMil re- spectively, such that the change of basis matrix M (with respect to these order* *ings) is upper triangular in every grading. In this situation we say the basis B is tria* *ngular with respect to the Milnor basis. This will be the situation if and only if there is an order preserving biject* *ion fl : BMil ! B such that fl () is the -largest summand of Milnor element when expressed in basis B. Remark 1.1. If B is triangular with respect to the Milnor basis, then we have * *a well defined recursive formula to convert a Milnor basis element to the basis B: Nam* *ely, for any 2 BMil, we have X (1.1) B = fl () + (i)B i P where xB denotes the representation of x in basis B and fl () = + ii is the Milnor representation of fl ()Mil obtained via the Milnor product formula. This is a well defined recursive formula because all of the Milnor basis elem* *ents i must be strictly _-less than and so the recursion must eventually end when we * *reach elements for which fl () = holds. Since A is finite dimensional in each gradin* *g, we must have fl () = for the which is the _ -smallest Milnor basis element in a * *given grading. Thus in order to show that B is triangular with respect to the Milnor basis a* *nd determine the change of basis formula (1.1) for converting an element from the * *Milnor basis to basis B it suffices to: 1. Define a bijection fl : BMil ! B. 2. Define the ordering _ on BMil. Then let be the unique ordering of B such that fl is order preserving. 3. Prove that fl () is the -largest summand of the representation of B for a* *ny 2 BMil. We will follow this procedure several times in what follows. Note that requir* *ement #3 can also be satisfied by showing fl-1 () is the _-largest Milnor basis summ* *and of the Milnor basis representation of for any 2 B; since fl is order preservi* *ng and CHANGE OF BASIS IN THE STEENROD ALGEBRA 3 the inverse of a triangular matrix is also triangular. Also in place of require* *ment #2 we can define the ordering on B and then let _ be the unique ordering of BMil such that fl is order preserving. In this article we will accomplish three things. First, we will construct a * *new family of bases for the Steenrod algebra A consisting of monomials in distinct * *Pts's and add these new bases to the list of bases being considered in this article. * *Second, we will determine which of the bases being considered are triangular with respe* *ct to the Milnor basis, and determine the change of basis formula of the form (1.1* *) for each basis that is. Finally, we will show how such information may lead to prod* *uct information by determining an infinite family of elements which are both admiss* *ible monomial and Milnor basis elements. 2. Summary of Main Results In this section we give a general overview of the main results which are cont* *ained in this paper. The details, notation, background and proofs will be presented l* *ater in the paper. Our first result is the construction of an infinite family of new* * bases for A. Let R denote right lexicographic order (Definition 3.1). Theorem 2.1. The set, BPR , of all monomials of the form Pts00Pts11.P.s.ptpsuc* *h that (s0; t0)R (s1; t1)R . .R. (sp; tp)is a basis for A. In addition, any set BP obtained by changing the order of the factors of any of the monomials in BPR is* * also a basis for A: Adding these bases to the list of bases mentioned above (those of Wall, Arnon* *, and Wood and the basis of admissible monomials) we can completely determine which of these bases are triangular with respect to the Milnor basis and determine the c* *hange of basis formula of the form (1.1) by specifying the required fl: Theorem 2.2. (1) The following bases are triangular with respect to the Milnor basis and h* *ave change of basis formula (1.1) for the value of fl shown in the table: _____________________________________|| | || Basis ||fl required for|| |______________________|formula(1.1)__| | Admissible monomials |Definition 4.1 | || s || || ||Any Pt basis |Definition|5.1 || ||Arnon C ||Definition 6.1|| |_Arnon_A_____________|Definition__7.1|___ (2) Wall's basis, Wood's Y basis, and Wood's Z basis are not triangular with respect to the Milnor basis. 4 KENNETH G. MONKS It should be noted that in each case there is a simple heuristic for computin* *g fl which makes these change of basis formulas quite easy to use in practice. We g* *ive both these heuristics and sample calculations along with the proofs in later se* *ctions of the article. Of some interest in its own right is the unusual ordering of the Milnor basis* * elements used in the proof of Theorem 2.2 for the Arnon A basis. This ordering is given* * in Definition 7.3. One way to improve on the recursive change of basis formulas given in Theorem 2.2, would be to determine explicit non-recursive formulas. As a first step in* * this direction one might ask what elements two bases have in common. For example, it is well known that the Sq (n)= Sqn are common to both the Milnor and admissible monomial bases. Our final result determines an infinite family of elements whic* *h are common to these two bases. Theorem 2.3. If ri -1 mod 2!(ri+1)for all 1 i < m then Sq(r1; : :;:rmi)s an e* *l- ement of both the Milnor and admissible monomial bases. In this case Sq(r1; : :* *;:rm=) Sqt1Sqt2. .S.qtmwhere tm = rm and ti= ri+ 2ti+1 for 1 i < m. We point out that this linear algebra result is actually providing us with in* *formation about monomial products in A. Based on computer calculations we conjecture that these are the only elements common to the Milnor and admissible monomial bases. It is hoped that results of this sort would provide the first step in determini* *ng non- recursive change of basis formulas for these bases. 3. Bases for A: Old and New We begin by describing the bases to be discussed in this article. Algebraica* *lly the Steenrod algebra can be described as the quotient of the free associative g* *raded algebra over the field with two elements, F2, on symbols Sqn in grading n; by t* *he ideal generated by the Adem relations: ba_2cX ! b - n - 1 a+b-n n SqaSq b= Sq Sq (fora < 2b) n=0 a - 2n where the binomial coefficients are taken mod 2 and Sq0 = 1, the multiplicati* *ve identity. In order to describe the bases we wish to consider we first define the follow* *ing. Definition 3.1.Let R = r1; : :;:rm and S = s1; : :;:sn be finite sequences of i* *nte- gers. Write R R S if R is less than S in lexicographic order from the right, i.* *e. if either m < n or else m = n and there exists i such that ri < si and rj = sj for* * all j > i . If R R S we will say R is rlex less than S. We make a similar definition for left lexicographic order, i.e. R L S if there exists i such that ri< si and* * rj = sj CHANGE OF BASIS IN THE STEENROD ALGEBRA 5 for all j < i (where we take rk = 0 for k > m and sk = 0 for k > n). If R L S we will say R is llex less than S. The bases we consider in this article are: (1) Admissible monomials: A monomial of the form Sqt1Sqt2. .S.qtmis said to be admissible if ti 2ti+1for 1 i < m: The set of all admissible monomials forms a basis for A which we will denote by BAdm : Whether Sqt1Sqt2. .S.q* *tm is admissible or not, we will often abbreviate Sqt1Sqt2. .S.qtmby Sqt1;::* *:;tmand in addition if T = t1; : :;:tm we will write Sqfor Sqt1;:::;tm. (2) Milnor [Mil]: Milnor showed that A is also a Hopf algebra whose dual, A*,* * is the polynomial algebra F2[1; 2; : :]:on generators n in grading 2n - 1. T* *he basis of A which is dual to the basis of monomials in A* is called the Mi* *lnor basis and will be denoted BMil. The element dual to r11r22. .r.mmin this * *basis is denoted Sq(r1; : :;:rm.)Comparing with the notation given above we have Sq (n)= Sqn : If R = r1; : :;:rm is a finite sequence of nonnegative inte* *gers, we will often use multi-index notation and write Sq for the Milnor ba* *sis element Sq (r1; : :;:rm.) The algebra structure on A in this basis can be described by the product formula given by Milnor. Namely, X (3.1) Sq (r1; r2; :S:):q(s1; s2;=: :):Sq(t1; t2; : :): X where the sum is taken over all matrices X = satisfying: X (3.2) xij= sj X i (3.3) 2jxij= ri j Y (3.4) (xh0; xh-1;1; : :;:x0h) 1 (mod 2) h where (n1; : :;:nmi)s the multinomial coefficient (n1+. .+.nm )!= (n1! . * *.n.m!). (The value of x00is never used an may be taken to be 0.) Each such allowa* *ble matrix produces a summand Sq (t1; t2; :g:):iven by X (3.5) th = xij: i+j=h In such a situation we say that X is a Sq Sq -allowable matrix which produces Sq : We will also find it convenient to say that X produces * *the sequence T if T satisfies (3.5) regardless of whether or not X is allowab* *le. n 2n-1 2k (3) Arnon A [Arn , Theorem 1A]: Define Xnk= Sq2 Sq . .S.q . Then the set of all monomials of the form Xn0k0Xn1k1.X.n.pkpsuch that (n0; k0)L (n1; k* *1)L . .L.(np; kp)forms a basis for A which we will denoted by BArA: 6 KENNETH G. MONKS k 2k+1 2n (4) Wall [Wall, pg. 433]: Define Qnk= Sq2 Sq . .S.q : Then the set of all monomials of the form Qn0k0Qn1k1.Q.n.pkpsuch that (np; kp)L (np-1; kp-1)L . .L.(n0; k0)forms a basis for A which we will denoted by BWall: This bas* *is was also discussed in [Arn , Theorem 1B]. (5) Arnon C [Arn , Theorem 1C]: A monomial of the form Sqtm Sqtm-1. .S.qt1 is said to be C-admissible if ti+1 2ti for 1 i < m and ti is divisible * *by 2i-1: The set of all C-admissible monomials forms a basis for A which we * *will denote by BArC: n(2k+1-1) (6) Wood Y [Wo , Theorem 1]: Define Ykn = Sq2 . Then the set of all monomials of the form Ykn00Ykn11. .Y.npkpsuch that (np; kp)L (np-1; kp-1)L . .L.(n0; k0)forms a basis for A which we will denote by BWdY : Wood shows that this basis has a nice property with respect to the Hopf subalgebras * *An of i A generated by the Sq2 with i n . Namely if any factor of any summand of WdY is not in An then itself is not in An. n(2k+1-1) (7) Wood Z [Wo , Theorem 2]: Let Ykn = Sq 2 as above. Then the set of all monomials of the form Ykn00Ykn11. .Y.npkpsuch that (np + kp; n* *p)L (np-1+ kp-1; np-1)L . .L.(n0 + k0; n0)forms a basis for A which we will denoted by BWdZ : Wood shows that this basis also has the same nice prope* *rty with respect to the Hopf subalgebras An that was mentioned above for the Y basis. (8) Pts-bases: In this article we will prove that the following is a basis fo* *r A: Let Pts= Sq(r1; : :;:rt)where rt= 2s and ri= 0 for i < t . For each finite se* *t, S; of Pts's choose an ordering of the elements of S; and let M(S) be the mon* *omial formednby taking the productoof the elements of S in increasing order, i* *.e. if S = Pts00; Pts11; : :;:Ptsppand we order the elements of S in the order * *shown then M (S)= Pts00Pts11.P.s.ptp: The monomials M (S) form a basis for A: T* *his gives us an infinite family of bases, one for each choice of ordering the* * sets S (not all of them are distinct, of course). For example, the set of all monomials of the form Pts00Pts11.P.s.ptpsuch * *that (s0; t0)R (s1; t1)R . .R.(sp; tp)is one such basis which we will denote by BPR : Before leaving this section we give a few elementary definitions and notation* * that will be needed later on. Definition 3.2.If BName is one of the bases of A described above and 2 A then Name will denote the representation of in that basis. i j For example, Sq2Sq 1 Mil= Sq(3) + Sq(0; 1)while Sq (0; 1)Adm= Sq2Sq 1+ Sq3: For any Milnor basis consists of element, Sq (r1; : :;:rm;)itPis clear from t* *he defi- nition that the grading or degree of Sq (r1; : :;:rmi)s mi=1(2i- 1)ri: For an* *y of the CHANGE OF BASIS IN THE STEENROD ALGEBRA 7 other bases, the degree of a monomial is thePsum of the degrees of its Milnor b* *asis factors. The excess of Sq (r1; : :;:rmi)s mi=1riPand its length is m. The e* *xcess of an admissible monomial Sqt1;:::;tmis tm + m-1i=1(ti- 2ti+1): We will denot* *e the excess of 2 BMil by ex() : Note that Sq (r1; : :;:rmi)s not uniquely determined by its degree, excess, and length as can be seen by the elements Sq (0; 1; 2; 0* *;a1)nd Sq(2; 0; 0; 1;:1) We can extend the definitions of left and right lexicographic order to both M* *ilnor basis elements and monomials in Sqn in the obvious manner, i.e. if R R S then Sq R Sq and SqR R Sq Sand similarly if R L S then Sq L Sq and SqR L SqS . For any positive integerPn, let ffi(n) be the coefficient of 2i in the binary* * expan- sion of n, i.e. n = 1i=0ffi(n)2i and ffi(n) 2 {0; 1}for all i. We say that m * *and n are disjoint and write m n if ffi(m) + ffi(n) 1 for all i. It isiwelljknown * *that this is equivalent to the condition that the binomial coefficient m+nm is odd.* * Con- sequently, the multinomial coefficient (n1; : :;:nmi)s odd if and only if the i* *ntegers n1; : :;:nm are pairwise disjoint. This fact is used frequently throughout the * *article when evaluating condition (3.4). We often write 2i 2 n for ffi(n) = 1 since the meaning is clear from the cont* *ext. The following fact will be used implicitly several times and is an elementary e* *xercise in binary arithmetic. Let 0 b < 2t. Then (3.6) 2l2 b , 2l2 2ta + b and l < t: Finally let (n)be the largest integer such that n 0 mod 2(n) (and take (0)= 1 ). Let ! (n)be the smallest integer such that 2!(n)> n: Notice that for n > 0* * we always have 2(n) 2 n and also that (n)< ! (n). 4.Milnor vs. Admissible We begin by focusing on the relationship between BMil and BAdm . The elements Sq(n) (= Sq n) are common to both the Milnor and admissible monomial bases. Therefore to express an admissible monomial in the Milnor basis, we only need u* *se the product formula (3.1) for multiplying Milnor basis elements. To convert a element from the Milnor basis to the basis of admissible monomia* *ls we now show that the basis of admissible monomials is triangular with respect t* *o the Milnor basis and define the fl and ordering needed for the recursive formula (* *1.1). To satisfy requirement #1 following (1.1) we make the following definition. Definition 4.1.Let Sq = Sq (r1; : :;:rmb)e a Milnor basis element. Define fl (Sq(r1; : :;:rm))= Sqt1Sqt2. .S.qtmwhere mX (4.1) ti= 2k-irk: k=i 8 KENNETH G. MONKS (Abbreviation: we will sometimes write fl for fl () ). Note that the ti can quickly be computed by starting with tm = rm and then applying the simple recursion (4.2) ti= ri+ 2ti+1: It follows immediately that fl Sq is an admissible monomial for any Sq 2 * *BMil: The map fl is clearly a bijection on A in each degree and preserves both excess* * and rlex order. So we take both and _ to be R in this case to satisfy requirement * *#2 following (1.1). So in order to satisfy requirement #3 following (1.1) we show: Theorem 4.1. fl Sq is the rlex-largest summand of Sq Adm. Hence BAdm is triangular with respect to BMil: As a result we have a recursive formula of the form (1.1) for converting an element of A from the Milnor basis * *to the basis of admissible monomials. P Corollary 4.2. Let Sq 2 BMil and suppose fl (Sq)Mil= Sq + iSq : Then X SqAdm = fl Sq + SqAdm i is a well defined recursive formula for computing Sq Adm. Note that fl (Sq)Mil can easily be obtained from the Milnor product formula (3.1). All of the elements Sq are strictly rlex-less than Sq which is* * why the recursive formula is well defined. This makes the formula quite easy to us* *e in practice. For example, to convert Sq(2; 2)to the basis of admissible monomials using Co* *rol- lary 4.2 we first compute fl Sq(2; 2)= Sq 6Sq2. By the Milnor product formula, Sq(6)Sq (2) = Sq (2; 2)+ Sq (5; 1): The error term, Sq (5; 1)is smaller than the original term Sq (2; 2)in rlex order and we invoke Corollary 4.2 again. This t* *ime fl Sq(5; 1)= Sq7Sq 1; but by the Milnor product formula we find that Sq (7)Sq(1* *)= Sq(5; 1): Thus we have shown that Sq (2; 2)= Sq6Sq 2+ Sq7Sq1 which provides the conversion we desired. In order to prove these results we begin by proving a useful lemma. CHANGE OF BASIS IN THE STEENROD ALGEBRA 9 Let Sq (r1; : :;:rm,)Sq (s1; : :;:sn)2 BMil: Let X = be the matrix ______*______||0_||0_||._.|.|0_ ______r1______||0_||0_||._.|.|0_ .. . . . . _______.______||..||..||..||.._ _____rm-1_____||0_||0_||._.|.|0_X rm - 2ksk ||s1s||2||. .|.|sn We will call X the rlex champion matrix for Sq (r1; : :;:rmS)q(s1; : :;:sn). Lemma 4.3. If the rlex champion matrix for Sq Sq produces T , then eve* *ry other Sq Sq-allowable matrix produces a sequence which is rlex-less than* * T: Proof . By (3.2) and (3.3), any other such matrix must have xij6= 0 for some 0 i < m and 1 j n: Let j be the largest such value. Then by (3.2) we have xmj < sj: Therefore the element Sq(u1; : :;:um+np)roduced by the new matrix must have uk = sk = tk for m + j < k m + n and um+j = xmj < sj = tj: Thus Sq R Sq : As an immediate consequence we have Corollary 4.4. Let T be the sequence produced by the rlex champion matrix for Sq Sq . If U R S then for every Milnor summand Sq of the product Sq Sq we have V R T: This follows from Lemma 4.3 and the fact that the sequence T 0produced by the rlex champion matrix for Sq Sq is easily seen to be rlex less than T: We are now ready to prove Theorem 4.1. Proof of Theorem 4.1. We wish to show that fl Sq is the rlex-largest summa* *nd of Sq Adm . Since fl is bijective and preserves rlex order, itisufficesjto s* *how that for any admissible monomial Sqthe Milnor basis element fl-1 Sq is the rl* *ex i j largest summand of Sq Mil: i * * j Let T = t1; : :;:tm be an admissible sequence. Recall that by (4.2) fl-1 Sq<* *T> = Sq(r1; : :;:rmw)here rm = tm and ri= ti- 2ti+1for i < m: We proceed by induction on m . i j i j If m = 1 then Sq Mil= Sq (t1)and fl-1 Sq = Sq (t1), so the base case holds. Now for the inductive hypothesisiassumejthat for any admissible monomialiSqj of length less than m , fl-1 Sq is the rlex-largest summand of SqMil. T* *hen in i j i * * j particular, fl-1 Sqt2;:::;tm= Sq(r2; : :;:rmi)s the rlex-largest summand of S* *qt2;:::;tmMil: So we can write i j X Sqt2;:::;tmMil= Sq(r2; : :;:rm+) Sq 10 KENNETH G. MONKS where Sq R Sq (r2; : :;:rmf)or all i: Thus we have i j i j Sqt1;:::;tmMil= Sq (t1) Sqt2;:::;tmMil i X j = Sq (t1) Sq(r2; : :;:rm+) Sq X = Sq (t1)Sq(r2; : :;:rm+) Sq(t1)Sq : The rlex champion matrix X for Sq (t1)Sq(r2; : :;:rmi)s ________*________||0_||0_||._.|.|0__P t1 - mk=22k-1rkr||2||r3.||.|.|rm: Clearly X is admissible. To see that it produces Sq (r1; : :;:rmw)e need only v* *erify that mX mX t1 - 2k-1rk= t1 - 2 2k-2rk k=2 k=2 = t1 - 2t2 = r1: Therefore by Lemma 4.3 every other Sq (t1)Sq(r2; : :;:rm )-allowable matrix pro- duces Milnor elements which are rlex-less than Sq (r1; : :;:rm.) So Sq (r1; : :* *;:rm ) is the rlex-largest summand of Sq(t1)Sq(r2; : :;:rm ). In addition, every summa* *nd of Sq(t1)Sq is rlex less than Sq (r1; : :;:rmb)y Corollary 4.4. 5. Milnor vs. Pts We now turn our attention to the relationship between BMil and BPR . All of t* *he results and arguments in this section carry over to any Ptsbasis, but we illust* *rate them for this particular ordering of the monomial factors. The elements Ptsare common to both the Milnor and Ptsbases. Therefore to express an element of BPR * *in the Milnor basis, we only need use the product formula (3.1) for multiplying Mi* *lnor basis elements. Notice that we have not yet shown that BPR is a basis for A although we have defined it as a set. To see that BPR is in fact a triangular basis with respect* * to the Milnor basis we begin by defining a grading preserving bijection fl : BMil ! BP* *R . Definition 5.1.Let Sq (r1; : :;:rm2)BMil. Define fl (Sq(r1; : :;:rm))= Pts00Pts11.P.s.ptp where the right hand side is the unique monomial in BPR satisfying Pjiis a factor ofPts00Pts11.P.s.ptp, ffi(rj)= 1 for all i and j: CHANGE OF BASIS IN THE STEENROD ALGEBRA 11 The map fl is clearly a bijection on A in each grading. There is a useful heuristic device for computing the fl Sq(r1; : :;:rm:)We de* *fine the binary chart of Sq (r1; : :;:rmt)o be the array: .. . . . . || .. .. .. 2 ||ff2(r1)ff2(r2)ff2(r3) . . . s 1 ||ff1(r1)ff1(r2)ff1(r3) . . . 0 ||ff0(r1)ff0(r2)ff0(r3)_._._. 1 2 3 . . . t In other words simply write the binary expansions or the numbers r1; : :;:rm ve* *rti- cally next to each other. Then Ptsis a factor of fl Sq(r1; : :;:rmi)f and only * *if there is a 1 in location (s; t)in the binary chart. The factors are then multiplied * *in the correct order for whichever Ptsbasis we are considering. For example, to compute fl Sq(2; 5; 1)we make the chart: 1 1 0 0 1 1 and read off the factors P11; P20; P22, and P30: Multiplying them in the correc* *t order for BPR we get fl Sq(2; 5; 1)= P11P20P22P30: Now define an ordering E on BMil as follows. Definition 5.2.For any Sq ; Sq 2 BMil; we say Sq E Sq if ex(Sq )< ex(Sq ) or else ex (Sq) = ex(Sq )and Sq R Sq : The second condition is simply used to make a total ordering out of the parti* *al ordering induced by excess and is never used. Finally let be the ordering induced on BPR induced by the bijection fl and E* * : Then we have: Theorem 5.1. fl Sq is the -largest summand of Sq PR. It follows immediately that the elements of BPR are linearly independent in e* *ach grading and since fl is a bijection, BPR is, indeed, a basis as claimed. Furthe* *r, with this definition of fl and E we have satisfied requirements #1-3 in Section 1 an* *d so BPR is triangular with respect to BMil: As a result we have a recursive formula* * of the form (1.1) for converting an element of A from the Milnor basis to the basi* *s of admissible monomials. 12 KENNETH G. MONKS P Corollary 5.2. Let Sq 2 BMil and suppose fl (Sq)Mil= Sq + iSq : Then X SqPR = fl Sq + SqPR i is a well defined recursive formula for computing Sq PR. Note that fl (Sq)Mil can easily be obtained from the Milnor product formula (3.1). All of the elements Sq are strictly E -less than Sq which is why* * the recursive formula is well defined. For example, to convert Sq(4; 2)to the basis BPR using Corollary 5.2 we first* * com- pute fl Sq(4; 2)= P12P21. By the Milnor product formula, P12P21= Sq (4)Sq(0; 2)= Sq(4; 2)+ Sq(0; 1; 1): The error term, Sq (0; 1; 1)is smaller than the original* * term Sq(4; 2)in E order and so we invoke Corollary 5.2 again. This time fl Sq(0; 1; * *1)= P20P30; but by the Milnor product formula we find that P20P30= Sq(0; 1)Sq(0; 0;* * 1)= Sq(0; 1; 1): Thus we have shown that Sq(4; 2)= P12P21+ P20P30 which provides the conversion we desired. In order to prove these results we begin by proving a few useful lemmas. Let Sq (r1; : :;:rm,)Sq (s1; : :;:sn)2 BMil: Let X = be the matrix _*__||s1s||2||._.|.|sn_ _r1_||0_||0_||._.|.|0_ .. . . . . __._||..||..||..||.._ rm ||0 ||0.||.|.|0 We will call X the excess champion matrix for Sq (r1; : :;:rmS)q(s1; : :;:sn). Let R = r1; r2; : :a:nd S = s1; s2; : :.:Then we define the obvious sum R + S = r1 + s1; r2 + s2; : :;:ri+ si; : ::: In this notation we see that the excess champion matrix for Sq Sq produc* *es Sq : Notice that ex(Sq )= ex(Sq )+ ex(Sq ): Lemma 5.3. If X is an allowable Sq Sq matrix which produces Sq then ex(Sq)< ex(Sq ): P Proof . Since the excess of Sq = Sq (t1; t2; :i:):s ti and by (3.5)Peac* *h ti is the sum of the ithdiagonal of X = , it follows that ex(Sq )= xij; i.* *e. it is i;j the sum of all of the entriesPof the matrix. By (3.2) the sum of the entries in* * columns to the right of column 0; j>0xijmust equal ex (Sq): By (3.3) xi0 ri for ea* *ch i so that thePentries in column 0 must have a sum less than or equal to the exc* *ess of Sq, i.e. j=0xij ex(Sq ): But since X is not the excess champion matrix, CHANGE OF BASIS IN THE STEENROD ALGEBRA 13 we must have xuv 6= 0 for some u > 0 and v > 0: But by (3.3) it follows that xu* *0 < ru and so the sum of column 0 is strictly less than ex(Sq ): Hence X ex (Sq) = xij i;j X X = xi;j+ xi;j j=0 j>0 < ex (Sq) + ex(Sq ) = ex (Sq) as claimed. As an immediate consequence we have Corollary 5.4. If ex(Sq ) < ex(Sq ) then every Milnor summand Sq of the product Sq Sq (or Sq Sq ) has excess less than ex(Sq ): We are now ready to prove Theorem 5.1. Proof of Theorem 5.1. We wish to show that fl Sq is the -largest sum- mand ofiSq PR. Itjsuffices to show that for any elementiPts00Pts11.P.s.ptpi* *njBPR , fl-1 Pts00Pts11.P.s.ptpis the E -largest summand of Pts00Pts11.P.s.ptpMil: We* * will show i sj * * i sj something slightly stronger, namely that fl-1 Pts00Pts11.P.t.ppis a summand of* * Pts00Pts11.P.t.ppMil i sj and every other Milnor summand of Pts00Pts11.P.t.ppMilwill have excess strictl* *y less i i sjj than ex fl-1 Pts00Pts11.P.t.pp: i sj Let = Pts00Pts11.P.s.ptp2 BPR and let Sq(r1; : :;:rm=)fl-1 Pts00Pts11.P.t.p* *pwhere P s ri= tj=i2 j. We proceed by induction on p . If p = 0 then (Pts00)Mil= Pts00and fl-1 (Pts00)= Pts00, so the base case hold* *s. Now for the inductive hypothesis assume that for any element 2 BPR having fe* *wer than p + 1 factors, fl-1 () is the rlex-largest summand of Mil. Then in particu* *lar, i s j fl-1 Pts00Pts11.P.t.p-1p-1= Sq(r1; : :;:rm-1 ; rm - 2sp) i sj is a summand of Pts00Pts11.P.t.ppMiland every other summand has excess less th* *an ex(Sq(r1; : :;:rm-1 ; rm - 2sp)): So we can write i sj X Pts00Pts11.P.t.ppMil= Sq(r1; : :;:rm-1 ; rm - 2sp)+ Sq where ex(Sq )< ex(Sq (r1; : :;:rm-1 ; rm -)2sp)for all i: 14 KENNETH G. MONKS Thus we have i sj i s j s Pts00Pts11.P.t.ppMil= Pts00Pts11.P.t.p-1p-1MilPtpp i X j s = Sq(r1; : :;:rm-1 ; rm - 2sp)+ SqPtpp X sp = Sq(r1; : :;:rm-1 ; rm - 2sp)Ptspp+ SqPtp: P sp Now each of the Milnor summands of Sq Ptp must have excess strictly less * *than ex(Sq(r1; : :;:rm))by Corollary 5.4. Every summand of Sq(r1; : :;:rm-1 ; rm - 2* *sp)Ptspp other than Sq (r1; : :;:rmm)ust have excess strictly less than ex(Sq (r1; : :;:* *rm))by Lemma 5.3. Finally, it is easy to see that the excess champion matrix associate* *d with Sq(r1;i: :;:rm-1j; rm - 2sp)Ptsppis allowable and thus Sq (r1; : :;:rmi)s a sum* *mand of Pts00Pts11.P.s.ptpMil. 6. Milnor vs. Arnon C We now turn to the relationship between BMil and BArC. In many ways this relationship is similar to the situation we find for BAdm : The elements Sq(n) * *are again common to both bases, so to express 2 BArC in the Milnor basis, we only need use the product formula (3.1). To convert a element from the Milnor basis to the Arnon C basis we follow the* * now familiar path of showing that the basis of C-admissible monomials is triangular* * with respect to the Milnor basis by defining the appropriate fl and ordering needed* * for the recursive formula of the form (1.1). Definition 6.1.Let Sq = Sq (r1; : :;:rmb)e a Milnor basis element. Define fl (Sq(r1; : :;:rm))= SqtmSq tm-1. .S.qt1where Xm (6.1) ti= 2i-1 rk: k=i Note that fl (Sq(r1; : :;:rm))can easily be computed by the following heurist* *ic. First, write the sequence r1; : :;:rm in a vertical column with r1 on top. Then* * working to the left, construct the following triangular shaped diagram in which each co* *lumn contains entries which are twice the entry to its right: r1 2r2 r2 .. . . .. 2m-2 rm-1 . . .2rm-1 rm-1 2m-1_rm___2m-2_rm__._._._2rm____rm___ tm tm-1 . . . t2 t1 the value of ti is then simply the sum of the ithcolumn from the right as indic* *ated. CHANGE OF BASIS IN THE STEENROD ALGEBRA 15 It is clear from the definition that ti is divisible by 2i-1and also that (6.2) ti+1= 2ti- 2iri holds for 1 i < m. Hence ti+1 2ti so that fl Sq is indeed in BArC. The map fl is a bijection on A in each grading and by (6.2) i j fl-1 Sqtm ;:::;t1= Sq(r1; : :;:rm ) where ri= 2ti-ti+1_2ifor 1 i < m and rm = _tm_2m-1: For this basis we choose R for the ordering of BMil and let be the ordering induced by fl on BArC: Then we have Theorem 6.1. fl Sq is the -largest summand of Sq ArC. Hence BArC is triangular with respect to BMil and we have a recursive formula* * of the form (1.1) for converting an element of A from the Milnor basis to the basi* *s of C-admissible monomials. P Corollary 6.2. Let Sq 2 BMil and suppose fl (Sq)Mil= Sq + iSq : Then X Sq ArC= fl Sq + SqArC i is a well defined recursive formula for computing Sq ArC. Note that once again fl (Sq)Milcan easily be obtained from the Milnor prod* *uct formula (3.1) and all of the elements Sq are strictly rlex-less than Sq * * which is why the recursive formula is well defined. For example, to convert Sq (3; 2)to the basis of C-admissible monomials using Corollary 6.2 we first compute fl Sq(3; 2)= Sq4Sq 5. By the Milnor product form* *ula, Sq(4)Sq (5) = Sq (3; 2)+ Sq (6; 1): The error term, Sq (6; 1)is smaller than the original term Sq (3; 2)in rlex order and so we invoke Corollary 6.2 again. This* * time fl Sq(6; 1)= Sq2Sq 7; but by the Milnor product formula we find that Sq (2)Sq(7* *)= Sq(6; 1): Thus we have shown that Sq (3; 2)= Sq4Sq 5+ Sq2Sq7 which provides the conversion we desired. We are now ready to prove Theorem 6.1. Proof of Theorem 6.1. Once again it sufficesitojshow that for any C-admissib* *le monomial Sqthe Milnor basis element fl-1 Sq is the rlex largest summand * *of i j SqMil: Let Sq= Sqtm ;:::;t1be a C-admissible monomial. Then i j fl-1 Sqtm ;:::;t1= Sq(r1; : :;:rm ) 16 KENNETH G. MONKS where ri= 2ti-ti+1_2ifori1j i < m and rm = _tm_2m-1:iWejproceed by induction on* * m . If m = 1 then Sq Mil= Sq (t1)and fl-1 Sq = Sq (t1), so the base case holds. Now for the inductive hypothesisiassumejthat for any admissible monomialiSqj of length less than m , fl-1 Sq is the rlex-largest summand of Sq Mil. * *Then in particular, we can compute i j fl-1 Sqtm-1;:::;t1= Sq(r1; : :;:rm-2 ; rm-1 + rm ) i j which must be the rlex-largest summand of Sqtm-1;:::;t1Mil: So we can write i j X Sqtm ;:::;t1Mil= Sq(r1; : :;:rm-2 ; rm-1 + rm+) Sq where Sq R Sq (r1; : :;:rm-2 ; rm-1 +frmo)r all i: Thus we have i j i j Sqtm ;:::;t1Mil= Sq(tm ) Sqtm-1;:::;t1Mil i X j = Sq(tm ) Sq(r1; : :;:rm-2 ; rm-1 + rm+) Sq X = Sq(tm )Sq(r1; : :;:rm-2 ; rm-1 + rm+) Sq(tm )Sq: The rlex champion matrix for Sq (tm )Sq(r1; : :;:rm-2 ; rm-1 +irms)not allowa* *ble in this case so instead we let X be the matrix _*_||r1.||.|.|rm-2r||m-1___ 0 ||0 ||. .|.|0 ||rm: Clearly X is allowable and produces Sq (r1; : :;:rm:)To see that X is indeed a Sq(tm )Sq(r1; : :;:rm-2 ; rm-1 + rmm)atrix we need only note that rm = _tm_2m-1: Now every other Sq (tm )Sq(r1; : :;:rm-2 ; rm-1 +-rma)llowable matrix produces Milnor elements which are rlex-less than Sq (r1; : :;:rms)ince by (3.3) any oth* *er such matrix must produce Sq (t1; : :;:tmw)ith tmP< rm : So it remains to show that every summand of Sq (tm )Sqis rlex less than Sq(r1; : :;:rm.) Let Sq = Sq (u1; : :;:un)be one of the summands. We know Sq is rlex less than Sq (r1; : :;:rm-2 ; rm-1 +.rmI)f n < m - 1 then every summand of Sq (tm )Sqhas length less than m and is therefore rlex less than Sq(r1; : :;:rm.) On the other hand, if n = m - 1 then there exists j such that uj < rj and Sq (u1; : :;:um-1=)Sq(u1; : :;:uj; rj+1; : :;:rm-2 ; rm-1:+ rm ) In this case the matrix _*_||u1_||._.|.|ujrj+1._._.rm-2_||rm-1__ 0 ||0 ||. .|.|0 0 . . . 0 ||rm CHANGE OF BASIS IN THE STEENROD ALGEBRA 17 produces the sequence (u1; : :;:uj; rj+1; : :;:rm-1(;wrmh)ether or not it is al* *lowable) which is clearly rlex less than (r1; : :;:rm:)By the same argument as above, an* *y other Sq(tm )Sq-allowable matrix must produce Sq for which V R U which is in turn rlex less than (r1; : :;:rm.) 7. Milnor vs. Arnon A The strangest of the bases discussed here which are triangular with respect t* *o the Milnor bases has to be BArA due to the unusual ordering _ on BMil that is used for the proof. Since elements of BArA are monomials in the elements Sq (2n);we * *can express an admissible monomial in the Milnor basis by using the product formula (3.1) for multiplying Milnor basis elements. To convert a element from the Milnor basis to the basis of admissible monomia* *ls we show that the Arnon A basis is triangular with respect to the Milnor basis a* *nd define the fl and ordering _needed for the recursive formula of the form (1.1)* *. For fl we make the following: Definition 7.1.Let Sq = Sq (r1; : :;:rmb)e a Milnor basis element. Define fl (Sq(r1; : :;:rm))= Xn0k0Xn1k1.X.n.pkpwhere (1) (n0; k0)L (n1; k1)L . .L.(np; kp)and (2) Xnkis a factor of Xn0k0Xn1k1.X.n.pkpif and only if ffk (rn-k+1)= 1. A heuristic for easily computing this gamma is very similar to that used for * *BPR : First, write down the binary chart for Sq (r1; : :;:rm.)Then for each chart loc* *ation (i; j) where there is a 1; we have an associated factor Xi+j-1jof fl Sq(r1; : :* *;:rm.) These factors are then multiplied in the correct order. For example, to compute fl Sq(2; 5; 6)we make the chart: 1 1 0 0 1 1 and read off the factors X11; X10; X32, and X20: Multiplying them in the correc* *t order we get fl Sq(2; 5; 6)= X10X11X20X32: The order _ on BMilwhich we require is quite unusual. We begin with an orderi* *ng on pairs of integers. Definition 7.2.Define an ordering on N x N by (a; b) (c; d)if (1) a + b < c + d or (2) a + b = c + d and b < d: For example, (0; 0)is the smallest element in this ordering and the ordering * *begins with (0; 0) (1; 0) (0; 1) (2; 0) (1; 1) (0; 2) (3; 0) . .:. 18 KENNETH G. MONKS The purpose of this ordering is to order the entries on our binary charts which* * will then provide an ordering on BMil: Definition 7.3.Let Sq (r1; : :;:rma)nd Sq (s1; : :;:sn)be elements of BMil: We * *say Sq(s1; : :;:sn)A Sq (r1; : :;:rmi)f there exists (h; k)such that (1) ffi(rj)= ffi(sj)for all (i; j) (h; k)and (2) ffk (rh)< ffk (sh): In other words, we compare the entries of the binary charts of Sq (r1; : :;:r* *ma)nd Sq(s1; : :;:sn)in increasing order until we find the first location (h; k)wher* *e they differ. Whichever element has the 0 at (h; k)is the larger element. (Note that * *the second condition is equivalent to the condition ffk (rh)= 0 and ffk (sh)= 1:) Armed with this fl and ordering A on BMil we can now prove: Theorem 7.1. Sq (r1; : :;:rmi)s the A-largest summand of fl Sq(r1; : :;:rmM)il: Thus the Arnon A basis is triangular with respect to the Milnor basis and we * *have the recursive formula (1.1) for converting an element of A from the Milnor basi* *s to the basis BArA. P Corollary 7.2. Let Sq 2 BMil and suppose fl (Sq)Mil= Sq + iSq : Then X Sq ArA= fl Sq + SqArA i is a well defined recursive formula for computing Sq ArA. For example, to compute Sq (2; 2)ArAwe first compute fl Sq(2; 2)= X11X21: By * *the Milnor product formula X11X21 = Sq (2)Sq(4) Sq(2) = Sq (2; 2)+ Sq(5; 1): Applying Corollary 7.2 to the error term we find fl Sq(5; 1)= X00X10X22: So by * *the product formula X00X10X22 = Sq (1)Sq (2)Sq(1)Sq (4) = Sq (5; 1): Thus we have the desired answer Sq (2; 2)= X11X21+ X00X10X22: In order to prove these results we begin by defining some notation that will * *be convenient. Definition 7.4.Let Sq(r1; : :;:rmb)e any Milnor basis element. We say Sq(r1; : * *:;:rm ) is zero up to (h; k)if ffi(rj)= 0 for all (i; j) (h; k): CHANGE OF BASIS IN THE STEENROD ALGEBRA 19 Definition 7.5.Let Sq(r1; : :;:rmb)e any Milnor basis element. We say Sq(r1; : * *:;:rm ) has a 1 at (h; k)if ffk (rh)= 1: Clearly if Sq is zero through (h; k)and Sq is not, then Sq A Sq : This notation is very intuitive when considering the ordering A and the binary charts of Milnor basis elements, as in the following technical lemma. Lemma 7.3. Let = Xn0k0Xn1k1.X.n.pkp2 BArA and let Sq (r1; : :;:rm=)fl-1 () : Then (1) Sq (r1; : :;:rmh)as a 1 at (n0 - k0 + 1; k0): (2) Sq (r1; : :;:rmi)s zero up to (n0 - k0 + 1; k0) (3) Xn0k0Xn1k1.X.n.pkp= Sq (2n0)Xn0-1k0Xn1k1.X.n.pkpand Xn0-1k0Xn1k1.X.n.pkp2* * BArA (takeiXn0-1k0= 1 if n0j= k0). i * * j (4) fl-1 Xn0-1k0Xn1k1.X.n.pkp= Sq r1; : :;:rh-1; rh + 2k0; rh+1 - 2k0; rh+2* *; : :;:rm whereih = n0 - k0 ( if h =j0 we interpreting the right hand expression as Sq r1 - 2k0; r2; : :;:rm). Proof: (1) By definition of fl; Xn0k0being a factor of implies that ffk0(rn0* *-k0+1)= 1 which in turn implies that Sq (r1; : :;:rmh)as a 1 at (n0 - k0 + 1; k0): (2) Assume the contrary. Then there must be (i; j) (n0 - k0 + 1; k0)such that Sq(r1; : :;:rmh)as a 1 at (i; j); i.e. such that ffj(ri)= 1: Thus by definition* * of fl; Xi+j-1jmust be a factor of : Now (i; j) (n0 - k0 + 1; k0)implies that either i+* *j < n0+1 or else i+j = n0+1 and j < k0 so that in either case (i + j - 1; j)L (n0; * *k0): But this contradicts the factor Xn0k0must be the smallest factor in left lexico* *graphic order of its indices by definition of BArA: (3) This follows trivially from (n0 - 1; k0)L (n0; k0)L . .L.(nm ; km ) i j and Xn0k0= Sq(2n0)Sq (2n0-1). .S.q2k0 = Sq(2n0)Xn0-1k0: (4) Since Xn0k0Xn1k1.X.n.pkpand Xn0-1k0Xn1k1.X.n.pkponlyidifferjin the first * *factor, then by definition of fl, Sq (r1; : :;:rma)nd fl-1 Xn0-1k0Xn1k1.X.n.pkpmust have id* *entical binary charts with the exception of the 1's corresponding to theileading factor* *s.j By (1), Sq (r1; : :;:rmh)as a 1 at (n0 - k0 + 1; k0)and fl-1 Xn0-1k0Xn1k1.X.n.* *pkphas a 1 at (n0 - k0; k0): But byi(2) Sq (r1; : :;:rmd)oesjnot have a 1 at (n0 - k0;* * k0) and it is clear that fl-1 Xn0-1k0Xn1k1.X.n.pkpdoes not have a 1 at (n0 - k0 + * *1; k0) sinceiXn0k0is not a factorj(remembering that (n0; k0)L (n1; k1)). Thus to obta* *in fl-1 Xn0-1k0Xn1k1.X.n.pkpfrom Sq(r1; : :;:rmw)e simply remove the 1 at (n0 - k* *0 + 1; k0) by subtracting 2k0from rn0-k0+1and create a 1 at (n0 - k0; k0)by adding 2k0to r* *n0-k0: 20 KENNETH G. MONKS Thus i n j i * * j fl-1 Xn0-1k0Xn1k1.X.p.kp= Sq r1; : :;:rn0-k0+ 2k0; rn0-k0+1- 2k0; : :;:rm as required. We are now ready to prove Theorem 7.1. i j Proof of Theorem 7.1. It suffices to show that fl-1 Xn0k0Xn1k1.X.n.pkpis th* *e A- i n j n largest summand of Xn0k0Xn1k1.X.p.kpMil: So let Xn0k0Xn1k1.X.p.kp2 BArA: Then i n j fl-1 Xn0k0Xn1k1.X.p.kp= Sq (r1; : :;:rmw)here ffk (rn-k+1)= 1 if and only if X* *nk P p is a factor of Xn0k0Xn1k1.X.n.pkp. Let q = i=0(ni- ki+ 1) which is the total * *number of factors of the form Sq (2i)in the product Xn0k0Xn1k1.X.n.pkpwhen expanded us* *ing the definition of Xnk. We proceed by inductionion q. j If q = 1 then p = 0 and n0 = k0 so that Xn0k0Xn1k1.X.n.pkpMil= Sq (2n0)Mil= i j Sq(2n0)and fl-1 Xn0n0= Sq(2n0) and hence the theorem holds. Assume that the theorem is true for all in BArA having less than q factors o* *f the form Sq (2i). Then by Lemma 7.3 i n j i j fl Xn0-1k0Xn1k1.X.p.kp= Sq r1; : :;:rh + 2k0; rh+1 - 2k0; : :;:rm where h = n0 - k0. For brevity let "R= r1; : :;:rh + 2k0; rh+1 - 2k0; : :;:rm : So by our inductive hypothesis we have i n j i n j Xn0k0Xn1k1.X.p.kpMil= Sq(2n0)Xn0-1k0Xn1k1.X.p.kpMil i D E X j = Sq(2n0) Sq "R + Sq D E X = Sq(2n0)Sq "R + Sq(2n0)Sq D E where Sq A Sq "R for all i. Now the matrix X _*_||r1.||.|.|rhr||h+1-_2k0.||.|.|rm_ (7.1) 0 ||0 ||. .|.|2k0 ||0 ||. .|.|0 D E is Sq (2n0)Sq R" -admissible since it clearly satisfies (3.2), (3.3) (because 2* *h2k0 = 2n0-k02k0 = 2n0), and (3.4) (since 2k0 2 rh+1 by Lemma 7.3 (1) it follows that * *2k0 =2 rh+1 - 2k0 ). The matrix X produces Sq (r1; : :;:rma)s desired. CHANGE OF BASIS IN THE STEENROD ALGEBRA 21 D E Let X be any other Sq(2n0)Sq "R -allowable matrix which produces Sq(t1; : * *:;:tn). Then X has the form _*__||x1x||2||.|.|.xw_ (7.2) : y0 ||y1 ||y2.||.|.|yw We consider two cases: h 6= 0 and h = 0. Case 1: h 6= 0: P Since X is admissible, 2iyi= 2n0 and hence yh 2k0: But yh 6= 2k0 sin* *ce we are assuming this matrix is not the same as (7.1). So yh < 2k0: Thus by* * (3.2) xh = rh+2k0-yh: But since yh < 2k0there exists u k0 such that 2u 2 xh * *(this follows from the fact that 2i2=rh for i k0 since Sq (r1; : :;:rmi)s ze* *ro up to (h + 1; k0)by Lemma 7.3). But also th = xh + yh-1 and so by (3.4) 2u 2 * *th also. Thus Sq(t1; : :;:tn)has a 1 at (h; u): But h + u h + k0 < h + k0* *+ 1 so that (h; u) (h + 1; k0): But Sq (r1; : :;:rmi)s zero up to (h + 1; k0)s* *o that Sq (t1; : :;:tn)A Sq (r1; : :;:rm:) Case 2: h = 0: P In this case n0 = k0. Since X is admissible, 2iyi = 2n0 and thus the* *re must be some v such that yv 6= 0 and consequently some u such that 2u 2* * yv with u + v n0: Notice also that we have u < k0 since we are assuming t* *his matrix is not the same as (7.1). By (3.4) 2u 2 yv implies 2u 2 tv+1: T* *hus Sq (t1; : :;:tn)has a 1 at (v + 1; u): But u + v + 1 n0 + 1 and u < k0* * so that (v + 1; u) (1; k0): By Lemma 7.3 Sq (r1; : :;:rmi)s zero up to (1;* * k0) so that Sq (t1; : :;:tn)A Sq (r1; : :;:rm:) D E So in both cases we have shown that any other Sq (2n0)Sq "R-allowable matr* *ix other than (7.1) produces Sq(t1; : :;:tn)which is strictly ADlessEthan Sq(r1;* * : :;:rm:) Thus Sq (r1; : :;:rmi)s a summand of the product Sq (2n0)Sq "R : So all that remains to be demonstrated is that Sq (r1;D:E:;:rmi)s not a sum- mand of Sq (2n0)Sqfor any of the terms Sq A Sq "R . So let Sq = Sq(s1; : :;:sn)be any such term. We again consider two cases. Case 1: h = 0. In this case n0 = k0. Let X be a SqP(2n0)Sq-allowable matrix (which must be of the form (7.2)). Since 2iyi= 2n0 there must be some v such* * that yv 6= 0 and consequently some u such that 2u 2 yv with u + v n0: By (3* *.4) 2u 2 yv implies 2u 2 tv+1: Thus Sq (t1; : :;:tn)has a 1 at (v + 1; u): * *Since u + v n0 it follows that u + v + 1 n0 + 1: Case 1.1:u + v + 1 < n0 + 1 or u + v + 1 = n0 + 1 and u < n0: In this case (v + 1; u) (1; n0): But Sq(r1; : :;:rmi)s zero up to * *(1; n0) so that Sq (t1; : :;:tn)A Sq (r1; : :;:rm:) Case 1.2:u + v + 1 = n0 + 1 and u = n0. 22 KENNETH G. MONKS In this case v = 0: Since X is allowable, 2n0 =2s1 (by (3.4)). Th* *us X produces Sq (t1; : :;:tn)where t1 = s1 + 2n0; and ti= si for i > 1* *: Thus it is easy to see that the binary chart of Sq (t1; : :;:tn)is iden* *tical to that of Sq (s1; : :;:sn)with the exception of the 1 at location (1* *; n0)of Sq(t1; : :;:tn): Similarly,DtheEbinary chart of Sq (r1; : :;:rmi)s* * identi- cal to that of Sq "R with the exception of the 1 at location (1; * *n0)of D E Sq(r1; : :;:rm()since Sq "R is zero up to (n1 - k1 + 1; k1) (1; k* *0)). D E Then the fact that Sq (s1; : :;:sn)A Sq "R implies that there ex* *ists D E (a; b)such that the binary charts of Sq(s1; : :;:sn)and Sq "R mat* *ch at all locationsD(i;Ej) (a; b)and that Sq (s1; : :;:sn)has a 1 at (a;* * b) while Sq "R has a 0 at (a; b): Simply changing the 0 at (1; n0)on both charts to a 1 does not affect this situation so that once aga* *in Sq(t1; : :;:tn)A Sq (r1; : :;:rm:) Case 2: h > 0: Let X be a Sq (2n0)Sq-allowable matrix which producesPSq (t1; : :;:* *tn) (and must be of the form (7.2)). Once again since 2iyi = 2n0 there m* *ust be some v such that yv 6= 0 and consequently some u such that 2u 2 yv w* *ith u + v n0: By (3.4) 2u 2 yv implies 2u 2 tv+1: Thus Sq (t1; : :;:tn)has* * a 1 at (v + 1; u): Case 2.1:u + v < n0 or (u + v = n0 and u < k0). In this case (v + 1; u) (n0 - k0 + 1; k0): But Sq(r1; : :;:rmi)s z* *ero up to (n0 - k0 + 1; k0)so that Sq (t1; : :;:tn)A Sq (r1; : :;:rm:) Case 2.2 u + v = n0 and u k0: Then X has the form _*_||s1.||.|.|sv-1s||v-_2us||v+1||.|.|.sn_ 0 ||0 ||. .|.|0 ||2u ||0 ||. .|.|0 Case 2.2.1:2u =2sv. In this case 2u 2 sv-2u which implies that 2u 2 tv: Thus Sq(t1* *; : :;:tn) has a 1 at (v; u): But u + v = n0 < n0 + 1 so that (v; u) (n0 - k0 + 1; k0): But Sq (r1; : :;:rmi)s zero up to (n0 - k0 * *+ 1; k0) so that Sq (t1; : :;:tn)A Sq (r1; : :;:rm:) Case 2.2.2:2u 2 sv: In this case we have Sq (t1; : :;:tn)= Sq(s1; : :;:sv - 2u; sv+1 + 2u; sv+2; :::* *;:sn) Notice that 2u =2sv+1 since X is admissible, so that the only * *differ- ence between the binary charts of Sq(t1; : :;:tn)and Sq(s1; : * *:;:sn) is that the 1 at (v; u)in Sq(s1; : :;:sn)is moved to location * *(v + 1; u) in Sq (t1; : :;:tn): Also the difference between the binary ch* *arts of CHANGE OF BASIS IN THE STEENROD ALGEBRA 23 D E * *D E Sq "R and Sq(r1; : :;:rmi)s that the 1 at location (h; k0)in Sq* * R" is moved to location (hD+E1; k0)in Sq (r1; : :;:rm:)By definition Sq (s1; : :;:sn)A Sq "R implies that there exists (a; b)such th* *at D E the binary charts of Sq (s1; : :;:sn)and Sq "R match at all loc* *a- tionsD(i;Ej) (a; b)and that Sq (s1; : :;:sn)has a 1 at (a; b)whi* *le Sq "R has a 0 at (a; b): Case 2.2.2.1:u = k0. In this case (v; u)= (h; k0). It is clear that simply moving* * the 1 at (h; k0)to location (h + 1; k0)on both binary charts to a 1 does not affect the fact that (a; b)is the first location * *where the charts differ and does not change the values of the char* *ts at (a; b), so that once again Sq (t1; : :;:tn)A Sq (r1; : :;* *:rm:) Case 2.2.2.2:u > k0:D E Since Sq "R has a 1 at (h; k0)and is zero up to (h; k0)and * *also D E Sq A Sq "R then either Sq (s1; : :;:sn)is not zero up to (h; k0)or else it is and it has a 1 at (h; k0)also. Case 2.2.2.2.1:Sq(s1; : :;:sn)is not zero up to (h; k0). In this case there is a 1 at (i; j)for some (i; j) (h; k0) (v; u): As the binary charts of Sq(t1; : :;:tn)and Sq(s1; : * *:;:sn) only differ at locations (v; u)and (v + 1; u), Sq(t1; : :;:t* *n)must also have a 1 at (i; j) (h; k0) (h + 1; k0): Thus since Sq (r1; : :;:rmi)s zero up to (h + 1; k0)we have Sq(t1; : :;* *:tn)A Sq (r1; : :;:rm:) Case 2.2.2.2.2:Sq(s1; : :;:sn)is zero up to (h; k0)and has a 1 at (h; k0). Since the binary charts of Sq (t1; : :;:tn)and Sq (s1; : :;:* *sn) only differ at locations (v; u)and (v + 1; u)and (h; k0) (v;* * u), Sq (t1; : :;:tn)must also have a 1 at (h; k0) (h + 1; k0): Thus since Sq (r1; : :;:rmi)s zero up to (h + 1; k0)we have Sq (t1; : :;:tn)A Sq (r1; : :;:rm:) 8. Non-triangular Bases The remaining bases, BWall, BWdY , and BWdZ are not triangular with respect * *to the Milnor basis. There is an interesting relationship between the BWalland BWdZ bases however, which we note in this section. To see that BWall is not triangular with respect to the Milnor basis we consi* *der grading 9: In this grading the elements of BWallare Sq8;1, Sq1;2;4;2, Sq2;4;1;2* *, Sq2;4;2;1, 24 KENNETH G. MONKS and Sq4;2;1;2. By the Milnor product formula these equal: Sq 8;1 = Sq (9)+ Sq(6; 1) Sq1;2;4;2= Sq (3; 2) Sq2;4;1;2= Sq (6; 1)+ Sq(0; 3)+ Sq(3; 2) Sq2;4;2;1= Sq (3; 2)+ Sq(0; 3)+ Sq(2; 0; 1) Sq4;2;1;2= Sq (6; 1)+ Sq(0; 3)+ Sq(2; 0; 1): Clearly, any bijection fl mapping BWall to BMil must have fl Sq1;2;4;2= Sq (3; * *2): Now suppose we wantPto find an ordering of BMil in grading 9 and extend fl so that Mil = fl () + Sq where each Sq fl () : Then among the elements Sq(6; 1), Sq(0; 3), and Sq(2; 0; 1)we must decide which element is greatest in * *terms of : Suppose we choose Sq (6; 1)to be the largest. Then the condition that fl * *map to the largest summand forces fl Sq2;4;1;2= fl Sq4;2;1;2= Sq (6; 1)which contr* *adicts the injectivity of fl: A similar argument shows that we cannot choose either Sq* * (0; 3) or Sq(2; 0; 1)for the largest element. Thus no such ordering and gamma exist, * *and we conclude BWall is not triangular with respect tot the Milnor basis. An exac* *tly analogous argument in grading 9 proves that both BWdY and BWdZ are not triangu* *lar with respect to the Milnor basis either. The Wood bases are related to each other in the same sense that the Ptsbases described above are: one basis can be obtained from the other by simply changing the order of the factors in the monomials. There also is an interesting relatio* *nship of sorts between the Wall basis and the Wood Z basis. We have the following: Theorem 8.1. Ynk-kis the E largest summand of (Qnk)Mil. The proof of this theorem is very similar to the proof of Theorem 5.1 and wil* *l not be presented here. Thus we are naturally led to consider the bijection fl : BWall!* * BWdZ by i n j k fl Qn0k0Qn1k1.Q.p.kp= Ynk00-k0Ynk11-k1.Y.n.pp-kp: It is a simple matter to verify that the order of the factors is such that the * *right hand side is indeed an element of BWdZ as claimed. We close this section by commenting that it is conceivable that these three b* *ases are triangular with respect to one another, but knowing this would not provide * *us with a recursive change of basis formula of the form (1.1) since this relies on* * the Milnor product formula to convert from the given basis to the Milnor basis, and* * we have no analogous product formula for these bases. CHANGE OF BASIS IN THE STEENROD ALGEBRA 25 9. Product Relations In order to improve on the change of basis formulas derived above, we would l* *ike to obtain explicit non-recursive formulas. As a first step in this direction it* * would be desirable to know which elements are common to two given bases. For example, it* * is well known that the elements Sq (n)are common to both the Milnor and admissible monomial bases. But are these the only such elements? The answer is no, and fur* *ther investigation yields an infinite subset of BMil\ BAdm . By Theorem 4.1 any elem* *ent 2 BMil\ BAdm must satisfy fl () = , i.e. it must be an eigenvector of fl (ext* *ended to a linear transformation of A). Theorem 9.1. If ri -1 mod 2!(ri+1)for all 1 i < m then Sq (r1; : :;:rm2) BMil\ BAdm (and in this case Sq (r1; : :;:rm=)fl Sq(r1; : :;:rm)). We point out that this linear algebra result is also providing us with inform* *ation about products, i.e. Sqt1Sqt2. .S.qtm= Sq (r1; : :;:rmw)here ri = ti- 2ti+1 (t* *ake tm+1 = 0 ) if ri -1 mod 2!(ri+1)for all 1 i < m: We also note out that the condition ri -1 mod 2!(ri+1)can easily be checked by writing the ordinary binary representations of numbers r1; r2; : :;:rm in horiz* *ontally above one another (with r1 on top) and checking that no digit ever appears belo* *w a 0: This is because of the following trivial fact which we state without proof: (9.1) r -1 mod 2w , 2k 2 r for allk < w: For example, Sq (13; 5; 1)is not equal to an admissible monomial because writ* *ing the indices in base 2 yields: 13 = 1 1 0 12 5 = 1 0 12 1 = 12 and the 0 in the two's column of the 5 is beneath the 0 in the same column for * *13 . On the other hand, Sq(7; 5; 1)does satisfy the required condition and so by The* *orem 9.1 we deduce that Sq (7; 5; 1)= Sq21Sq7 Sq1: We will also need to make use of the following fact whose verification is an * *elemen- tary exercise in binary arithmetic. Lemma 9.2. Let x; y; r; w be nonnegative integers. If r -1 mod 2w and x + y * *= r then for any k < w either 2k 2 x or 2k 2 y but not both, i.e. ffk (x)+ ffk (y)=* * 1. We now turn our attention to proving Theorem 9.1. Proof of Theorem 9.1. Let R = r1; : :;:rm be any sequence satisfying ri -1 mod 2!(ri+1)for all i: We would like to show that fl Sq = Sq : We pro- ceed by induction on m. If m = 1 then fl Sq(r1)= Sq(r1) by definition of fl: 26 KENNETH G. MONKS Now for the inductive hypothesis assume that for any Sq (s1; : :;:sk)2 BMil w* *ith k < m; if si -1 mod 2!(si+1)for all i then fl Sq = Sq : In particular, we* * have fl Sq(r2; : :;:rm=)Sq(r2; : :;:rm:) Let Sq= fl (R)where T = t1; : :;:tm . Then clearly fl Sq(r2; : :;:rm=)Sqt2* *. .S.qtm so that fl Sq = Sq (t1)Sq(t2). .S.q(tm ) = Sq (t1)fl Sq(r2; : :;:rm ) = Sq (t1)Sq(r2; : :;:rm:) So it suffices to show that Sq (t1)Sq(r2; : :;:rm=)Sq (r1; : :;:rmb)y the Milnor product formula. Let X be a Sq (t1)Sq(r2; : :;:rm-)allowable matrix. Then X is of the form _*__||x2x||3||||.x.m.||_ y1 ||y2 ||y3||||.y.|.|m such that for 2 i m (9.2) xi+ yi= ri (9.3) xi yi-1 and also satisfying mX (9.4) t1 = 2i-1yi: i=1 Let j > 2 and suppose 2i 2 xj: We would like to show that 2i 2 xj-1 also. Now 2i 2 xj implies that 2i xj rj < 2!(rj)by (9.2) and rj-1 -1 mod 2!(rj)implies that 2k 2 rj-1 for all k < ! (rj)by (9.1). Combining these facts shows 2i2 rj-1* *. So by (9.2) and Lemma 9.2 either 2i 2 xj-1 or 2i 2 yj-1: But 2i =2yj-1 by condition (9.3), so 2i 2 xj-1 . Thus we have shown that 2i 2 xj implies 2i 2 xj-1 . So * *by induction we have 2i2 xj implies 2i2 x2. In particular, (xj) (x2)for all j: Now suppose x2 6= 0: Then 2(x2) 2 x2: By Lemma 9.2 this implies that 2(x2) 2 * *r2 which in turn implies that 2(x2) 2 r1 by (9.1). Now since (xj) (x2)if follows that 2(x2) divides xj for all j; i.e. that (9.5) xj = 2(x2)hj CHANGE OF BASIS IN THE STEENROD ALGEBRA 27 for some nonnegative integer hj. Solving (9.4) for y1; substituting for t1 usin* *g (4.1) and applying (9.5) gives us mX y1 = t1 - 2k-1yk k=2 Xm mX = 2k-1rk - 2k-1yk k=1 k=2 mX = r1 + 2k-1(rk - yk) k=2 mX = r1 + 2k-1xk k=2 mX = r1 + 2k-12(x2)hk k=2 mX ! = r1 + 2(x2)+1 2k-2hk k=2 Combining this with the fact that 2(x2) 2 r1, it follows by (3.6) that 2(x2) 2 * *y1: Thus 2(x2) 2 y1 and 2(x2) 2 x2 which contradicts (9.3). Therefore our assumption that x2 6= 0 must be false. So x2 = 0: But (xj) (x2)for all j , so it follows that xj = 0 for all j . H* *ence X must be the matrix _*_||0_||0_||._.|.|0_ r1 ||r2r||3||.|.|.rm which is clearly admissible and produces Sq (r1; : :;:rm.) References [Arn]Arnon, D.; Monomial Bases in the Steenrod Algebra, Journal of Pure and App* *lied Algebra 96 (1994), 215-223 [Wall]Wall, C. T. C.; Generators and Relations for the Steenrod Algebra, Ann. o* *f Math. (3) 72 (1960), 429-444 [Wo] Wood, R. M. W.; A note on Bases and Relations in the Steenrod Algebra, to * *appear in Bull. London Math. Soc. [Mil]Milnor, J.; The Steenrod algebra and its dual, Ann. of Math. (2) 67 (1958)* *, 150-171 Department of Mathematics, University of Scranton, Scranton, PA 18510 E-mail address: monks@uofs.edu