CHANGE OF BASIS, MONOMIAL RELATIONS, AND P_{t}^{s} BASES FOR THE STEENROD ALGEBRA

KENNETH G. MONKS

Abstract. The relationship between several common bases for the mod 2 Steenrod algebra is explored and a family of bases consisting of monomials in distinct P_{t}^{s}’s is developed. A recursive change of basis formula is produced to convert between the Milnor basis and each of the bases for which the change of basis matrix in every grading is upper triangular. In particular, it is shown that the basis of admissible monomials, the P_{t}^{s} bases, and two bases due to D. Arnon, are all bases having this property, and the corresponding change of basis formula is produced for each of them. Some monomial relations for the mod 2 Steenrod algebra are then obtained by exploring the change of basis transformations.

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 are 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 bases consisting of monomials in distinct P_{t}^{s}’s to the existing collection. These bases are all described in detail in Section 3.

Given so many different bases, a natural question to ask is: how can we convert 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 information 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 monomials in Milnor basis elements. Thus it is a simple matter to convert from one of these bases, call it B, to the Milnor basis, B_{Mil}, by using the product formula (2) developed by Milnor [Mil]. A difficulty arises when trying to convert in the other direction: from the Milnor basis to back the basis B. Having such a formula for every basis would then allow us to convert between any two bases, indirectly, via the Milnor basis.

A brute force approach might be to compute the change of basis matrix, M, from B to B_{Mil} 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 approach is extremely inefficient and is unworkable in all but the lowest gradings where the vector space dimension is quite small.

1991 Mathematics Subject Classification. Primary 55S10, 55S05; Secondary 57T05.

Key words and phrases. Steenrod Algebra.

Suppose, however, that we have the following situation.

Definition 1.1. Suppose there exists orderings, ≺ and ˙≺, of bases B and B_{Mil} respectively, such that the change of basis matrix M (with respect to these orderings) is upper triangular in every grading. In this situation we say the basis B is triangular with respect to the Milnor basis.

This will be the situation if and only if there is an order preserving bijection γ : B_{Mil} → B such that γ (θ) 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. Namely, for any θ ∈ B_{Mil}, we have

θ_{B} = γ (θ) + ∑_{i} (θ_{i})_{B} (1)

where x_{B} denotes the representation of x in basis B and γ (θ) = θ + ∑_{i} θ_{i} is the Milnor representation of γ (θ)_{Mil} obtained via the Milnor product formula.

This is a well defined recursive formula because all of the Milnor basis elements θ_{i} must be strictly ˙≺-less than θ and so the recursion must eventually end when we reach elements for which γ (θ) = θ holds. Since A is finite dimensional in each grading, we must have γ (θ) = θ 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 and determine the change of basis formula (1) for converting an element from the Milnor basis to basis B it suffices to:

1. Define a bijection γ : B_{Mil} → B.

2. Define the ordering ˙≺ on B_{Mil}. Then let ≺ be the unique ordering of B such that γ is order preserving.

3. Prove that γ (θ) is the ≺-largest summand of the representation of θ_{B} for any θ ∈ B_{Mil}.

We will follow this procedure several times in what follows. Note that requirement #3 can also be satisfied by showing γ^{−1} (θ) is the ˙≺-largest Milnor basis summand of the Milnor basis representation of θ for any θ ∈ B, since γ is order preserving and the inverse of a triangular matrix is also triangular. Also in place of requirement #2 we can define the ordering ≺ on B and then let ˙≺ be the unique ordering of B_{Mil} such that γ is order preserving.

In this article we will accomplish three things. First, we will construct a family of bases for the Steenrod algebra A consisting of monomials in distinct P_{t}^{s}’s and add these bases to the list of bases being considered in this article. Second, we will determine which of the bases being considered are triangular with respect to the Milnor basis, and determine the change of basis formula of the form (1) for each basis that is. Finally, we will show how such information may lead to product information by determining an infinite family of elements which are both admissible monomial and Milnor basis elements.

2. Summary of Main Results

In this section we give a general overview of the main results which are contained in this paper. The details, notation, background and proofs will be presented later in the paper. Our first result is the construction of an infinite family of bases for A, using ideas similar to those discussed in [Mar, Chapter 15]. Let ≺_{R} denote right lexicographic order (Definition 3.1).

Theorem 2.1. The set, B_{P R}, of all monomials of the form P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}} such that (s_{0}, t_{0}) ≺_{R} (s_{1}, t_{1}) ≺_{R} ⋯ ≺_{R} (s_{p}, t_{p}) is a basis for A. In addition, any set B_{P} obtained by changing the order of the factors of any of the monomials in B_{P R} 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 change of basis formula of the form (1) by specifying the required γ.

Theorem 2.2.

1. The following bases are triangular with respect to the Milnor basis and have change of basis formula (1) for the value of γ shown in the table:

Basis  γ required for

formula(1)

Admissible monomials Definition 4.1
Any P_{t}^{s} 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.

It should be noted that in each case there is a simple heuristic for computing γ which makes these change of basis formulas quite easy to use in practice. We give both these heuristics and sample calculations along with the proofs in later sections 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) = Sq^{n} are common to both the Milnor and admissible monomial bases. Our final result determines an infinite family of elements which are common to these two bases. Let ω (n) be the smallest integer such that 2^{ω(n)} > n.

Theorem 2.3. If r_{i} ≡ −1 mod 2^{ω(r_{i+1})} for all 1 ≤ i < m then Sq (r_{1}, …, r_{m}) is an element of both the Milnor and admissible monomial bases. In this case Sq (r_{1}, …, r_{m}) = Sq^{t_{1}} Sq^{t_{2}} ⋯ Sq^{t_{m}} where t_{m} = r_{m} and t_{i} = r_{i} + 2t_{i+1} for 1 ≤ i < m.

We point out that this linear algebra result is actually providing us with information 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 determining nonrecursive 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. Algebraically the Steenrod algebra can be described as the quotient of the free associative graded algebra over the field with two elements, 𝔽_{2}, on symbols Sq^{n} in grading n, by the ideal generated by the Adem relations:

Sq^{a} Sq^{b} = \begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ n=0 \end{matrix} \binom{b − n − 1}{a − 2n} Sq^{a+b−n} Sq^{n} (for a < 2b)

where the binomial coefficients are taken mod 2 and Sq^{0} = 1, the multiplicative identity.

In order to describe the bases we wish to consider we first define the following.

Definition 3.1. Let R = r_{1}, …, r_{m} and S = s_{1}, …, s_{n} be finite sequences of nonnegative integers. Define r_{k} = 0 for k > m and s_{k} = 0 for k > n. Write R ≺_{R} S if R is less than S in lexicographic order from the right, i.e. if there exists i such that r_{i} < s_{i} and r_{j} = s_{j} 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 r_{i} < s_{i} and r_{j} = s_{j} for all j < i (where we take r_{k} = 0 for k > m and s_{k} = 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 Sq^{t_{1}} Sq^{t_{2}} ⋯ Sq^{t_{m}} is said to be admissible if t_{i} ≥ 2t_{i+1} for 1 ≤ i < m. The set of all admissible monomials forms a basis for A which we will denote by B_{Adm}. Whether Sq^{t_{1}} Sq^{t_{2}} ⋯ Sq^{t_{m}} is admissible or not, we will often abbreviate Sq^{t_{1}} Sq^{t_{2}} ⋯ Sq^{t_{m}} by Sq^{t_{1},... ,t_{m}} and in addition if T = t_{1}, …, t_{m} we will write Sq^{⟨T ⟩} for Sq^{t_{1},... ,t_{m}}.

2. Milnor [Mil]: Milnor showed that A is also a Hopf algebra whose dual, A^{∗}, is the polynomial algebra 𝔽_{2} [ξ_{1}, ξ_{2}, …] on generators ξ_{n} in grading 2^{n} − 1. The basis of A which is dual to the basis of monomials in A^{∗} is called the Milnor basis and will be denoted B_{Mil}. The element dual to ξ_{1}^{r_{1}}ξ_{2}^{r_{2}} ⋯ ξ_{m}^{r_{m}} in this basis is denoted Sq (r_{1}, …, r_{m}). Comparing with the notation given above we have Sq (n) = Sq^{n} . If R = r_{1}, …, r_{m} is a finite sequence of nonnegative integers, we will often use multi-index notation and write Sq ⟨R⟩ for the Milnor basis element Sq (r_{1}, …, r_{m}).

The algebra structure on A in this basis can be described by the product formula given by Milnor. Namely,

Sq (r_{1}, r_{2}, …) Sq (s_{1}, s_{2}, …) = ∑_{X} Sq (t_{1}, t_{2}, …) (2)

where the sum is taken over all matrices X = ⟨x_{ij}⟩ satisfying:

∑_{i} x_{ij} = s_{j} (3)

∑_{j} 2^{j}x_{ij} = r_{i} (4)

∏_{h} (x_{h0}, x_{h−1,1}, …, x_{0h}) ≡ 1 (mod 2) (5)

where (n_{1}, …, n_{m}) is the multinomial coefficient (n_{1} + ⋯ + n_{m})!/ (n_{1}! ⋯ n_{m}!). (The value of x_{00} is never used and may be taken to be 0.) Each such allowable matrix produces a summand Sq (t_{1}, t_{2}, …) given by

t_{h} = ∑_{i+j=h} x_{ij}. (6)

In such a situation we say that X is a Sq ⟨R⟩ Sq ⟨S⟩-allowable matrix which produces Sq ⟨T ⟩ . We will also find it convenient to say that X produces the sequence T if T satisfies (6) regardless of whether or not X is allowable.

3. Arnon A [Arn, Theorem 1A]: Define X_{k}^{n} = Sq^{2^{n}} Sq^{2^{n−1}} ⋯ Sq^{2^{k}}. Then the set of all monomials of the form X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} such that (n_{0}, k_{0}) ≺_{L} (n_{1}, k_{1}) ≺_{L} ⋯ ≺_{L} (n_{p}, k_{p}) forms a basis for A which we will denoted by B_{ArA}.

4. Wall [Wall, pg. 433]: Define Q_{k}^{n} = Sq^{2^{k}} Sq^{2^{k+1}} ⋯ Sq^{2^{n}} . Then the set of all monomials of the form Q_{k_{0}}^{n_{0}}Q_{k_{1}}^{n_{1}} ⋯ Q_{k_{p}}^{n_{p}} such that (n_{p}, k_{p}) ≺_{L} (n_{p−1}, k_{p−1}) ≺_{L} ⋯ ≺_{L} (n_{0}, k_{0}) forms a basis for A which we will denoted by B_{W all}. This basis was also discussed in [Arn, Theorem 1B].

5. Arnon C [Arn, Theorem 1C]: A monomial of the form Sq^{t_{m}} Sq^{t_{m−1}} ⋯ Sq^{t_{1}} is said to be C-admissible if t_{i+1} ≤ 2t_{i} for 1 ≤ i < m and t_{i} is divisible by 2^{i−1}. The set of all C-admissible monomials forms a basis for A which we will denote by B_{ArC}.

6. Wood Y [Wo, Theorem 1]: Define Y_{k}^{n} = Sq^{2^{n}(2^{k+1}−1)}. Then the set of all monomials of the form Y_{k_{0}}^{n_{0}}Y_{k_{1}}^{n_{1}} ⋯ Y_{k_{p}}^{n_{p}} such that (n_{p}, k_{p}) ≺_{L} (n_{p−1}, k_{p−1}) ≺_{L} ⋯ ≺_{L} (n_{0}, k_{0}) forms a basis for A which we will denote by B_{W dY} . Wood shows that this basis has a nice property with respect to the Hopf subalgebras A_{n} of A generated by the Sq^{2^{i}} with i ≤ n . Namely if any factor of any summand of θ_{W dY} is not in A_{n} then θ itself is not in A_{n}.

7. Wood Z [Wo, Theorem 2]: Let Y_{k}^{n} = Sq^{2^{n}(2^{k+1}−1)} as above. Then the set of all monomials of the form Y_{k_{0}}^{n_{0}}Y_{k_{1}}^{n_{1}} ⋯ Y_{k_{p}}^{n_{p}} such that (n_{p} + k_{p}, n_{p}) ≺_{L} (n_{p−1} + k_{p−1}, n_{p−1}) ≺_{L} ⋯ ≺_{L} (n_{0} + k_{0}, n_{0}) forms a basis for A which we will denoted by B_{W dZ}. Wood shows that this basis also has the same nice property with respect to the Hopf subalgebras A_{n} that was mentioned above for the Y basis.

8. P_{t}^{s}-bases: In this article we will prove that the following is a basis for A. Let P_{t}^{s} = Sq (r_{1}, …, r_{t}) where r_{t} = 2^{s} and r_{i} = 0 for i < t . For each finite set, S, of P_{t}^{s}’s choose an ordering of the elements of S, and let M(S) be the monomial formed by taking the product of the elements of S in increasing order, i.e. if S = {P_{t_{0}}^{s_{0}}, P_{t_{1}}^{s_{1}}, …, P_{t_{p}}^{s_{p}}} and we order the elements of S in the order shown then M (S) = P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}}. The monomials M (S) form a basis for A. This 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 P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}} such that (s_{0}, t_{0}) ≺_{R} (s_{1}, t_{1}) ≺_{R} ⋯ ≺_{R} (s_{p}, t_{p}) is one such basis which we will denote by B_{P R}.

Before leaving this section we give a few elementary definitions and notation that will be needed later on.

Definition 3.2. If B_{Name} is one of the bases of A described above and θ ∈ A then θ_{Name} will denote the representation of θ in that basis.

For example, (Sq^{2} Sq^{1})_{Mil} = Sq (3) + Sq (0, 1) while Sq (0, 1)_{Adm} = Sq^{2} Sq^{1} + Sq^{3} . For any Milnor basis element, Sq (r_{1}, …, r_{m}) , it is clear from the definition that

the grading or degree of Sq (r_{1}, …, r_{m}) is ∑_{i=1}^{m}(2^{i} − 1)r_{i}. For any of the other bases, the degree of a monomial is the sum of the degrees of its Milnor basis factors. The excess of Sq (r_{1}, …, r_{m}) is ∑_{i=1}^{m} r_{i} and its length is m. The excess of an admissible monomial Sq^{t_{1},... ,t_{m}} is t_{m} + ∑_{i=1}^{m−1} (t_{i} − 2t_{i+1}) . We will denote the excess of θ ∈ B_{Mil} by ex (θ) . Note that Sq (r_{1}, …, r_{m}) is not uniquely determined by its degree, excess, and length as can be seen by the elements Sq (0, 1, 2, 0, 1) and Sq (2, 0, 0, 1, 1) .

We can extend the definitions of left and right lexicographic order to both Milnor basis elements and monomials in Sq^{n} in the obvious manner, i.e. if R ≺_{R} S then Sq ⟨R⟩ ≺_{R} Sq ⟨S⟩ and Sq^{R} ≺_{R} Sq^{S} and similarly if R ≺_{L} S then Sq ⟨R⟩ ≺_{L} Sq ⟨S⟩ and Sq^{R} ≺_{L} Sq^{S} .

For any positive integer n, let α_{i}(n) be the coefficient of 2^{i} in the binary expansion of n, i.e. n = ∑_{i=0}^{∞} α_{i}(n)2^{i} and α_{i} (n) ∈ {0, 1} for all i. We say that m and n are disjoint and write m ≍ n if α_{i}(m) + α_{i}(n) ≤ 1 for all i. It is well known that this is equivalent to the condition that the binomial coefficient \binom{m+n}{m} is odd. Consequently, the multinomial coefficient (n_{1}, …, n_{m}) is odd if and only if the integers n_{1}, …, n_{m} are pairwise disjoint. This fact is used frequently throughout the article when evaluating condition (5).

We often write 2^{i} ∈ n for α_{i}(n) = 1 since the meaning is clear from the context. The following fact will be used implicitly several times and is an elementary exercise in binary arithmetic. Let 0 ≤ b < 2^{t}. Then

2^{l} ∈ b ⇔ 2^{l} ∈ 2^{t}a + b and l < t. (7)

Finally let ν (n) be the largest integer such that n ≡ 0 mod 2^{ν(n)} (and take ν (0) = ∞ ). Let ω (n) be the smallest integer such that 2^{ω(n)} > n. Notice that for n > 0 we always have 2^{ν(n)} ∈ n and also that ν (n) < ω (n).

4. Milnor vs. Admissible

We begin by focusing on the relationship between B_{Mil} and B_{Adm} . 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 use the product formula (2) for multiplying Milnor basis elements.

To convert a element from the Milnor basis to the basis of admissible monomials we now show that the basis of admissible monomials is triangular with respect to the Milnor basis and define the γ and ordering ≺ needed for the recursive formula (1). To satisfy requirement #1 following (1) we make the following definition.

Definition 4.1. Let Sq ⟨R⟩ = Sq (r_{1}, …, r_{m}) be a Milnor basis element. Define γ (Sq (r_{1}, …, r_{m})) = Sq^{t_{1}} Sq^{t_{2}} ⋯ Sq^{t_{m}} where

t_{i} = ∑_{k=i}^{m} 2^{k−i}r_{k}. (8)

(Abbreviation: we will sometimes write γθ for γ (θ) ).

Note that the t_{i} can quickly be computed by starting with t_{m} = r_{m} and then applying the simple recursion

t_{i} = r_{i} + 2t_{i+1}. (9)

It follows immediately that γ Sq ⟨R⟩ is an admissible monomial for any Sq ⟨R⟩ ∈ B_{Mil}. The map γ 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). So in order to satisfy requirement #3 following (1) we show:

Theorem 4.1. γ Sq ⟨R⟩ is the rlex-largest summand of Sq ⟨R⟩_{Adm}.

Hence B_{Adm} is triangular with respect to B_{Mil}. As a result we have a recursive formula of the form (1) for converting an element of A from the Milnor basis to the basis of admissible monomials.

Corollary 4.2. Let Sq ⟨R⟩ ∈ B_{Mil} and suppose γ (Sq ⟨R⟩)_{Mil} = Sq ⟨R⟩+∑_{i} Sq ⟨R_{i}⟩ . Then

Sq ⟨R⟩_{Adm} = γ Sq ⟨R⟩ + ∑_{i} Sq ⟨R_{i}⟩_{Adm}

is a well defined recursive formula for computing Sq ⟨R⟩_{Adm}.

Note that γ (Sq ⟨R⟩)_{Mil} can easily be obtained from the Milnor product formula (2). All of the elements Sq ⟨R_{i}⟩ are strictly rlex-less than Sq ⟨R⟩ which is why the recursive formula is well defined. This makes the formula quite easy to use in practice.

For example, to convert Sq (2, 2) to the basis of admissible monomials using Corollary 4.2 we first compute γ Sq (2, 2) = Sq^{6} Sq^{2}. 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 time γ Sq (5, 1) = Sq^{7} Sq^{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) = Sq^{6} Sq^{2} + Sq^{7} Sq^{1}

which provides the conversion we desired.

In order to prove these results we begin by proving a useful lemma.

Let Sq (r_{1}, …, r_{m}), Sq (s_{1}, …, s_{n}) ∈ B_{Mil}. Let X = ⟨x_{ij}⟩ be the matrix

\begin{matrix}* & 0 & 0 & ⋯ & 0 \\ r_{1} & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ r_{m−1} & 0 & 0 & ⋯ & 0 \\ r_{m} − ∑ 2^{k}s_{k} & s_{1} & s_{2} & ⋯ & s_{n} \end{matrix}

We will call X the rlex champion matrix for Sq (r_{1}, …, r_{m}) Sq (s_{1}, …, s_{n}).

Lemma 4.3. If the rlex champion matrix for Sq ⟨R⟩ Sq ⟨S⟩ produces T, then every other Sq ⟨R⟩ Sq ⟨S⟩-allowable matrix produces a sequence which is rlex-less than T.

Proof . By (3) and (4), any other such matrix must have x_{ij} ≠ 0 for some 0 ≤ i < m and 1 ≤ j ≤ n. Let j be the largest such value. Then by (3) we have x_{mj} < s_{j}. Therefore the element Sq (u_{1}, …, u_{m+n}) produced by the new matrix must have u_{k} = s_{k} = t_{k} for m + j < k ≤ m + n and u_{m+j} = x_{mj} < s_{j} = t_{j}. Thus Sq ⟨U⟩ ≺_{R} Sq ⟨T ⟩ . □

As an immediate consequence we have Corollary 4.4. Let T be the sequence produced by the rlex champion matrix for Sq ⟨R⟩ Sq ⟨S⟩. If U ≺_{R} S then for every Milnor summand Sq ⟨V ⟩ of the product Sq ⟨R⟩ Sq ⟨U⟩ we have V ≺_{R} T.

This follows from Lemma 4.3 and the fact that the sequence T′ produced by the rlex champion matrix for Sq ⟨R⟩ Sq ⟨U⟩ 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 γ Sq ⟨R⟩ is the rlex-largest summand of Sq ⟨R⟩_{Adm} . Since γ is bijective and preserves rlex order, it suffices to show that for any admissible monomial Sq^{⟨T ⟩} the Milnor basis element γ^{−1} (Sq^{⟨T ⟩}) is the rlex

largest summand of (Sq^{⟨T ⟩})_{Mil} .

Let T = t_{1}, …, t_{m} be an admissible sequence. Recall that by (9) γ^{−1} (Sq^{⟨T ⟩}) = Sq (r_{1}, …, r_{m}) where r_{m} = t_{m} and r_{i} = t_{i} −2t_{i+1} for i < m. We proceed by induction on m .

If m = 1 then (Sq^{⟨T ⟩})_{Mil} = Sq (t_{1}) and γ^{−1} (Sq^{⟨T ⟩}) = Sq (t_{1}), so the base case holds.

Now for the inductive hypothesis assume that for any admissible monomial Sq^{⟨S⟩} of length less than m, γ^{−1} (Sq^{⟨S⟩}) is the rlex-largest summand of (Sq^{⟨S⟩})_{Mil}. Then in

particular, γ^{−1} (Sq^{t_{2},... ,t_{m}}) = Sq (r_{2}, …, r_{m}) is the rlex-largest summand of (Sq^{t_{2},... ,t_{m}})_{Mil} . So we can write

(Sq^{t_{2},... ,t_{m}})_{Mil} = Sq (r_{2}, …, r_{m}) + ∑ Sq ⟨R_{i}⟩

where Sq ⟨R_{i}⟩ ≺_{R} Sq (r_{2}, …, r_{m}) for all i.

Thus we have

(Sq^{t_{1},... ,t_{m}})_{Mil} = Sq (t_{1}) (Sq^{t_{2},... ,t_{m}})_{Mil}
= Sq (t_{1}) (Sq (r_{2}, …, r_{m}) + ∑ Sq ⟨R_{i}⟩)
= Sq (t_{1}) Sq (r_{2}, …, r_{m}) + ∑ Sq (t_{1}) Sq ⟨R_{i}⟩ .

The rlex champion matrix X for Sq (t_{1}) Sq (r_{2}, …, r_{m}) is

\begin{matrix}* & 0 & 0 & ⋯ & 0 \\ t_{1} − ∑_{k=2}^{m} 2^{k−1}r_{k} & r_{2} & r_{3} & ⋯ & r_{m} \end{matrix} .

Clearly X is admissible. To see that it produces Sq (r_{1}, …, r_{m}) we need only verify that

t_{1} − ∑_{k=2}^{m} 2^{k−1}r_{k} = t_{1} − 2 ∑_{k=2}^{m} 2^{k−2}r_{k}
= t_{1} − 2t_{2}
= r_{1}.

Therefore by Lemma 4.3 every other Sq (t_{1}) Sq(r_{2}, …, r_{m})-allowable matrix produces Milnor elements which are rlex-less than Sq (r_{1}, …, r_{m}). So Sq (r_{1}, …, r_{m}) is the rlex-largest summand of Sq (t_{1}) Sq(r_{2}, …, r_{m}). In addition, every summand of Sq (t_{1}) Sq ⟨R_{i}⟩ is rlex less than Sq (r_{1}, …, r_{m}) by Corollary 4.4. □

5. Milnor vs. P_{t}^{s}

We now turn our attention to the relationship between B_{Mil} and B_{P R} . We use methods and ideas similar to those discussed in [Mar, Chapter 15].

All of the results and arguments in this section carry over to any P_{t}^{s} basis, but we illustrate them for this particular ordering of the monomial factors. The elements P_{t}^{s} are common to both the Milnor and P_{t}^{s} bases. Therefore to express an element of B_{P R} in the Milnor basis, we only need use the product formula (2) for multiplying Milnor basis elements.

Notice that we have not yet shown that B_{P R} is a basis for A although we have defined it as a set. To see that B_{P R} is in fact a triangular basis with respect to the Milnor basis we begin by defining a grading preserving bijection γ : B_{Mil} → B_{P R} .

Definition 5.1. Let Sq (r_{1}, …, r_{m}) ∈ B_{Mil}. Define

γ (Sq (r_{1}, …, r_{m})) = P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}}

where the right hand side is the unique monomial in B_{P R} satisfying

P_{j}^{i} is a factor of P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}} ⇔ α_{i} (r_{j}) = 1

for all i and j.

The map γ is clearly a bijection on A in each grading.

There is a useful heuristic device for computing the γ Sq (r_{1}, …, r_{m}) . We define the binary chart of Sq (r_{1}, …, r_{m}) to be the array:

s \begin{aligned}⋮ & ⋮ & ⋮ & ⋮ \\ 2 & α_{2} (r_{1}) & α_{2} (r_{2}) & α_{2} (r_{3}) & ⋯ \\ 1 & α_{1} (r_{1}) & α_{1} (r_{2}) & α_{1} (r_{3}) & ⋯ \\ 0 & α_{0} (r_{1}) & α_{0} (r_{2}) & α_{0} (r_{3}) & ⋯ \\ & 1 & 2 & 3 & ⋯ \end{aligned}

t

In other words simply write the binary expansions of the numbers r_{1}, …, r_{m} vertically next to each other. Then P_{t}^{s} is a factor of γ Sq (r_{1}, …, r_{m}) if 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 P_{t}^{s} basis we are considering.

For example, to compute γ Sq (2, 5, 1) we make the chart:

1 1 0 0 1 1 and read off the factors P_{1}^{1}, P_{2}^{0}, P_{2}^{2}, and P_{3}^{0}. Multiplying them in the correct order for B_{P R} we get γ Sq (2, 5, 1) = P_{1}^{1}P_{2}^{0}P_{2}^{2}P_{3}^{0}.

Now define an ordering ≺_{E} on B_{Mil} as follows.

Definition 5.2. For any Sq ⟨R⟩ , Sq ⟨S⟩ ∈ B_{Mil}, we say Sq ⟨R⟩ ≺_{E} Sq ⟨S⟩ if

ex (Sq ⟨R⟩) < ex (Sq ⟨S⟩)

or else

ex (Sq ⟨R⟩) = ex (Sq ⟨S⟩) and Sq ⟨R⟩ ≺_{R} Sq ⟨S⟩ .

The second condition is simply used to make a total ordering out of the partial ordering induced by excess and is never used.

Finally let ≺ be the ordering induced on B_{P R} induced by the bijection γ and ≺_{E} . Then we have:

Theorem 5.1. γ Sq ⟨R⟩ is the ≺-largest summand of Sq ⟨R⟩_{P R}.

It follows immediately that the elements of B_{P R} are linearly independent in each grading and since γ is a bijection, B_{P R} is, indeed, a basis as claimed. Further, with this definition of γ and ≺_{E} we have satisfied requirements #1-3 in Section 1 and so B_{P R} is triangular with respect to B_{Mil}. As a result we have a recursive formula of the form (1) for converting an element of A from the Milnor basis to the basis of admissible monomials.

Corollary 5.2. Let Sq ⟨R⟩ ∈ B_{Mil} and suppose γ (Sq ⟨R⟩)_{Mil} = Sq ⟨R⟩+∑_{i} Sq ⟨R_{i}⟩ . Then

Sq ⟨R⟩_{P R} = γ Sq ⟨R⟩ + ∑_{i} Sq ⟨R_{i}⟩_{P R}

is a well defined recursive formula for computing Sq ⟨R⟩_{P R}.

Note that γ (Sq ⟨R⟩)_{Mil} can easily be obtained from the Milnor product formula (2). All of the elements Sq ⟨R_{i}⟩ are strictly ≺_{E}-less than Sq ⟨R⟩ which is why the recursive formula is well defined.

For example, to convert Sq (4, 2) to the basis B_{P R} using Corollary 5.2 we first compute γ Sq (4, 2) = P_{1}^{2}P_{2}^{1}. By the Milnor product formula, P_{1}^{2}P_{2}^{1} = 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 γ Sq (0, 1, 1) = P_{2}^{0}P_{3}^{0}, but by the Milnor product formula we find that P_{2}^{0}P_{3}^{0} = Sq (0, 1) Sq (0, 0, 1) = Sq (0, 1, 1) . Thus we have shown that

Sq (4, 2) = P_{1}^{2}P_{2}^{1} + P_{2}^{0}P_{3}^{0}

which provides the conversion we desired.

In order to prove these results we begin by proving a few useful lemmas.

Let Sq (r_{1}, …, r_{m}), Sq (s_{1}, …, s_{n}) ∈ B_{Mil}. Let X = ⟨x_{ij}⟩ be the matrix

\begin{matrix}* & s_{1} & s_{2} & ⋯ & s_{n} \\ r_{1} & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ r_{m} & 0 & 0 & ⋯ & 0 \end{matrix}

We will call X the excess champion matrix for Sq (r_{1}, …, r_{m}) Sq (s_{1}, …, s_{n}).

Let R = r_{1}, r_{2}, … and S = s_{1}, s_{2}, . . .. Then we define the obvious sum

R + S = r_{1} + s_{1}, r_{2} + s_{2}, …, r_{i} + s_{i}, ….

In this notation we see that the excess champion matrix for Sq ⟨R⟩ Sq ⟨S⟩ produces Sq ⟨R + S⟩ . Notice that ex (Sq ⟨R + T ⟩) = ex (Sq ⟨R⟩) + ex (Sq ⟨T ⟩) .

Lemma 5.3. If X is an allowable Sq ⟨R⟩ Sq ⟨S⟩ matrix which produces Sq ⟨T ⟩ then ex (Sq ⟨T ⟩) < ex (Sq ⟨R + S⟩) .

Proof . Since the excess of Sq ⟨T ⟩ = Sq (t_{1}, t_{2}, …) is ∑ t_{i} and by (6) each t_{i} is the sum of the i^{th} diagonal of X = ⟨x_{ij}⟩, it follows that ex (Sq ⟨T ⟩) = ∑_{i,j} x_{ij}, i.e. it is

the sum of all of the entries of the matrix. By (3) the sum of the entries in columns to the right of column 0, ∑_{j>0} x_{ij} must equal ex (Sq ⟨S⟩) . By (4) x_{i0} ≤ r_{i} for each i so that the entries in column 0 must have a sum less than or equal to the excess of Sq ⟨R⟩, i.e. ∑_{j=0} x_{ij} ≤ ex (Sq ⟨R⟩) . But since X is not the excess champion matrix, we must have x_{uv} ≠ 0 for some u > 0 and v > 0. But by (4) it follows that x_{u0} < r_{u} and so the sum of column 0 is strictly less than ex (Sq ⟨R⟩) . Hence

ex (Sq ⟨T ⟩) = ∑_{i,j} x_{ij}
= ∑_{j=0} x_{i,j} + ∑_{j>0} x_{i,j}
< ex (Sq ⟨R⟩) + ex (Sq ⟨S⟩)
= ex (Sq ⟨R + S⟩)

as claimed. □ As an immediate consequence we have

Corollary 5.4. If ex (Sq ⟨U⟩) < ex (Sq ⟨R⟩) then every Milnor summand Sq ⟨T ⟩ of the product Sq ⟨U⟩ Sq ⟨S⟩ (or Sq ⟨S⟩ Sq ⟨U⟩) has excess less than ex (Sq ⟨R + S⟩) .

We are now ready to prove Theorem 5.1.

Proof of Theorem 5.1. We wish to show that γ Sq ⟨R⟩ is the ≺-largest summand of Sq ⟨R⟩_{P R}. It suffices to show that for any element P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}} in B_{P R}, γ^{−1} (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}}) is the ≺_{E}-largest summand of (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})_{Mil} . We will show something slightly stronger, namely that γ^{−1} (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}}) is a summand of (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})_{Mil} and every other Milnor summand of (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})_{Mil} will have excess strictly less than ex (γ^{−1} (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})) .

Let θ = P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}} ∈ B_{P R} and let Sq (r_{1}, …, r_{m}) = γ^{−1} (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}}) where r_{i} = ∑_{t_{j}=i} 2^{s_{j}}. We proceed by induction on p .

If p = 0 then (P_{t_{0}}^{s_{0}})_{Mil} = P_{t_{0}}^{s_{0}} and γ^{−1} (P_{t_{0}}^{s_{0}}) = P_{t_{0}}^{s_{0}}, so the base case holds.

Now for the inductive hypothesis assume that for any element θ ∈ B_{P R} having fewer than p + 1 factors, γ^{−1} (θ) is the rlex-largest summand of θ_{Mil}. Then in particular,

γ^{−1} (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p−1}}^{s_{p−1}}) = Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}})

is a summand of (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})_{Mil} and every other summand has excess less than ex (Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}})) . So we can write

(P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})_{Mil} = Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}}) + ∑ Sq ⟨R_{i}⟩

where ex (Sq ⟨R_{i}⟩) < ex (Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}})) for all i.

Thus we have

(P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})_{Mil} = (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p−1}}^{s_{p−1}})_{Mil} P_{t_{p}}^{s_{p}}
= (Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}}) + ∑ Sq ⟨R_{i}⟩) P_{t_{p}}^{s_{p}}
= Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}}) P_{t_{p}}^{s_{p}} + ∑ Sq ⟨R_{i}⟩ P_{t_{p}}^{s_{p}}.

Now each of the Milnor summands of ∑ Sq ⟨R_{i}⟩ P_{t_{p}}^{s_{p}} must have excess strictly less than ex (Sq (r_{1}, …, r_{m})) by Corollary 5.4. Every summand of Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}}) P_{t_{p}}^{s_{p}} other than Sq (r_{1}, …, r_{m}) must have excess strictly less than ex (Sq (r_{1}, …, r_{m})) by Lemma 5.3. Finally, it is easy to see that the excess champion matrix associated with Sq (r_{1}, …, r_{m−1}, r_{m} − 2^{s_{p}}) P_{t_{p}}^{s_{p}} is allowable and thus Sq (r_{1}, …, r_{m}) is a summand of (P_{t_{0}}^{s_{0}}P_{t_{1}}^{s_{1}} ⋯ P_{t_{p}}^{s_{p}})_{Mil}. □

6. Milnor vs. Arnon C

We now turn to the relationship between B_{Mil} and B_{ArC}. In many ways this relationship is similar to the situation we find for B_{Adm}. The elements Sq(n) are again common to both bases, so to express θ ∈ B_{ArC} in the Milnor basis, we only need use the product formula (2).

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 γ and ordering ≺ needed for the recursive formula of the form (1).

Definition 6.1. Let Sq ⟨R⟩ = Sq (r_{1}, …, r_{m}) be a Milnor basis element. Define γ (Sq (r_{1}, …, r_{m})) = Sq^{t_{m}} Sq^{t_{m−1}} ⋯ Sq^{t_{1}} where

t_{i} = 2^{i−1} ∑_{k=i}^{m} r_{k}. (10)

Note that γ (Sq (r_{1}, …, r_{m})) can easily be computed by the following heuristic. First, write the sequence r_{1}, …, r_{m} in a vertical column with r_{1} on top. Then working to the left, construct the following triangular shaped diagram in which each column contains entries which are twice the entry to its right:

r_{1}
2r_{2}  r_{2}
⋮  ⋮
2^{m−2}r_{m−1} ⋯ 2r_{m−1} r_{m−1}
2^{m−1}r_{m} 2^{m−2}r_{m} ⋯ 2r_{m} r_{m}
t_{m}  t_{m−1} ⋯ t_{2}  t_{1}

the value of t_{i} is then simply the sum of the i^{th} column from the right as indicated. It is clear from the definition that t_{i} is divisible by 2^{i−1}and also that

t_{i+1} = 2t_{i} − 2^{i}r_{i} (11)

holds for 1 ≤ i < m. Hence t_{i+1} ≤ 2t_{i} so that γ Sq ⟨R⟩ is indeed in B_{ArC}. The map γ is a bijection on A in each grading and by (11)

γ^{−1} (Sq^{t_{m},... ,t_{1}}) = Sq (r_{1}, …, r_{m})

where r_{i} = \frac{2t_{i}−t_{i+1}}{2^{i}} for 1 ≤ i < m and r_{m} = \frac{t_{m}}{2^{m−1}} .

For this basis we choose ≺_{R} for the ordering of B_{Mil} and let ≺ be the ordering induced by γ on B_{ArC}. Then we have

Theorem 6.1. γ Sq ⟨R⟩ is the ≺-largest summand of Sq ⟨R⟩_{ArC}.

Hence B_{ArC} is triangular with respect to B_{Mil} and we have a recursive formula of the form (1) for converting an element of A from the Milnor basis to the basis of C-admissible monomials.

Corollary 6.2. Let Sq ⟨R⟩ ∈ B_{Mil} and suppose γ (Sq ⟨R⟩)_{Mil} = Sq ⟨R⟩+∑_{i} Sq ⟨R_{i}⟩ . Then

Sq ⟨R⟩_{ArC} = γ Sq ⟨R⟩ + ∑_{i} Sq ⟨R_{i}⟩_{ArC}

is a well defined recursive formula for computing Sq ⟨R⟩_{ArC}.

Note that once again γ (Sq ⟨R⟩)_{Mil} can easily be obtained from the Milnor product formula (2) and all of the elements Sq ⟨R_{i}⟩ are strictly rlex-less than Sq ⟨R⟩ 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 γ Sq (3, 2) = Sq^{4} Sq^{5}. By the Milnor product formula, 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 γ Sq (6, 1) = Sq^{2} Sq^{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) = Sq^{4} Sq^{5} + Sq^{2} Sq^{7}

which provides the conversion we desired.

We are now ready to prove Theorem 6.1.

Proof of Theorem 6.1. Once again it suffices to show that for any C-admissible monomial Sq^{⟨T ⟩} the Milnor basis element γ^{−1} (Sq^{⟨T ⟩}) is the rlex largest summand of

(Sq^{⟨T ⟩})_{Mil} .

Let Sq^{⟨T ⟩} = Sq^{t_{m},... ,t_{1}} be a C-admissible monomial. Then

γ^{−1} (Sq^{t_{m},... ,t_{1}}) = Sq (r_{1}, …, r_{m})

where r_{i} = \frac{2t_{i}−t_{i+1}}{2^{i}} for 1 ≤ i < m and r_{m} = \frac{t_{m}}{2^{m−1}} . We proceed by induction on m .

If m = 1 then (Sq^{⟨T ⟩})_{Mil} = Sq (t_{1}) and γ^{−1} (Sq^{⟨T ⟩}) = Sq (t_{1}), so the base case holds.

Now for the inductive hypothesis assume that for any admissible monomial Sq^{⟨S⟩} of length less than m , γ^{−1} (Sq^{⟨S⟩}) is the rlex-largest summand of (Sq^{⟨S⟩})_{Mil}. Then in particular, we can compute

γ^{−1} (Sq^{t_{m−1},... ,t_{1}}) = Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m})

which must be the rlex-largest summand of (Sq^{t_{m−1},... ,t_{1}})_{Mil} . So we can write

(Sq^{t_{m},... ,t_{1}})_{Mil} = Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m}) + ∑ Sq ⟨R_{i}⟩

where Sq ⟨R_{i}⟩ ≺_{R} Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m}) for all i.

Thus we have

(Sq^{t_{m},... ,t_{1}})_{Mil} = Sq (t_{m}) (Sq^{t_{m−1},... ,t_{1}})_{Mil}
= Sq (t_{m}) (Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m}) + ∑ Sq ⟨R_{i}⟩)
= Sq (t_{m}) Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m}) + ∑ Sq (t_{m}) Sq ⟨R_{i}⟩ .

The rlex champion matrix for Sq (t_{m}) Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m}) is not allowable in this case so instead we let X be the matrix

\begin{matrix}* & r_{1} & ⋯ & r_{m−2} & r_{m−1} \\ 0 & 0 & ⋯ & 0 & r_{m} \end{matrix} .

Clearly X is allowable and produces Sq (r_{1}, …, r_{m}) . To see that X is indeed a Sq (t_{m}) Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m}) matrix we need only note that r_{m} = \frac{t_{m}}{2^{m−1}} .

Now every other Sq (t_{m}) Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m})-allowable matrix produces Milnor elements which are rlex-less than Sq (r_{1}, …, r_{m}) since by (4) any other such matrix must produce Sq (t_{1}, …, t_{m}) with t_{m} < r_{m}.

So it remains to show that every summand of ∑ Sq (t_{m}) Sq ⟨R_{i}⟩ is rlex less than Sq (r_{1}, …, r_{m}). Let Sq ⟨R_{i}⟩ = Sq (u_{1}, …, u_{n}) be one of the summands. We know Sq ⟨R_{i}⟩ is rlex less than Sq (r_{1}, …, r_{m−2}, r_{m−1} + r_{m}). If n < m − 1 then every summand of Sq (t_{m}) Sq ⟨R_{i}⟩ has length less than m and is therefore rlex less than Sq (r_{1}, …, r_{m}). On the other hand, if n = m−1 then there exists j such that u_{j} < r_{j} and

Sq (u_{1}, …, u_{m−1}) = Sq (u_{1}, …, u_{j}, r_{j+1}, …, r_{m−2}, r_{m−1} + r_{m}) .

In this case the matrix

\begin{matrix}* & u_{1} & ⋯ & u_{j} & r_{j+1} & ⋯ & r_{m−2} & r_{m−1} \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 & r_{m} \end{matrix}

produces the sequence (u_{1}, …, u_{j}, r_{j+1}, …, r_{m−1}, r_{m}) (whether or not it is allowable) which is clearly rlex less than (r_{1}, …, r_{m}) . By the same argument as above, any other Sq (t_{m}) Sq ⟨R_{i}⟩-allowable matrix must produce Sq ⟨V ⟩ for which V ≺_{R} U which is in turn rlex less than (r_{1}, …, r_{m}). □

7. Milnor vs. Arnon A

The strangest of the bases discussed here which are triangular with respect to the Milnor bases has to be B_{ArA} due to the unusual ordering ˙≺ on B_{Mil} that is used for the proof. Since elements of B_{ArA} are monomials in the elements Sq (2^{n}) ,we can express an admissible monomial in the Milnor basis by using the product formula (2) for multiplying Milnor basis elements.

To convert a element from the Milnor basis to the basis of admissible monomials we show that the Arnon A basis is triangular with respect to the Milnor basis and define the γ and ordering ˙≺ needed for the recursive formula of the form (1). For γ we make the following:

Definition 7.1. Let Sq ⟨R⟩ = Sq (r_{1}, …, r_{m}) be a Milnor basis element. Define γ (Sq (r_{1}, …, r_{m})) = X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} where

1. (n_{0}, k_{0}) ≺_{L} (n_{1}, k_{1}) ≺_{L} ⋯ ≺_{L} (n_{p}, k_{p}) and

2. X_{k}^{n} is a factor of X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} if and only if α_{k} (r_{n−k+1}) = 1.

A heuristic for easily computing this gamma is very similar to that used for B_{P R}. First, write down the binary chart for Sq (r_{1}, …, r_{m}). Then for each chart location (i, j) where there is a 1, we have an associated factor X_{j}^{i+j−1} of γ Sq (r_{1}, …, r_{m}). These factors are then multiplied in the correct order.

For example, to compute γ Sq (2, 5, 1) we make the chart:

1 1 0 0 1 1

and read off the factors X_{1}^{1}, X_{0}^{1}, X_{2}^{3}, and X_{0}^{2}. Multiplying them in the correct order we get γ Sq (2, 5, 1) = X_{0}^{1}X_{1}^{1}X_{0}^{2}X_{2}^{3}.

The order ˙≺ on B_{Mil} which we require is quite unusual. We begin with an ordering on pairs of integers.

Definition 7.2. Define an ordering ≪ on ℕ × ℕ 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) ≪ · · · .

The purpose of this ordering is to order the entries on our binary charts which will then provide an ordering on B_{Mil}.

Definition 7.3. Let Sq (r_{1}, …, r_{m}) and Sq (s_{1}, …, s_{n}) be elements of B_{Mil}. We say Sq (s_{1}, …, s_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) if there exists (h, k) such that

1. α_{i} (r_{j}) = α_{i} (s_{j}) for all (i, j) ≪ (h, k) and

2. α_{k} (r_{h}) < α_{k} (s_{h}) .

In other words, we compare the entries of the binary charts of Sq (r_{1}, …, r_{m}) and Sq (s_{1}, …, s_{n}) in increasing ≪ order until we find the first location (h, k) where they differ. Whichever element has the 0 at (h, k) is the larger element. (Note that the second condition is equivalent to the condition α_{k} (r_{h}) = 0 and α_{k} (s_{h}) = 1.)

Armed with this γ and ordering ≺_{A} on B_{Mil} we can now prove:

Theorem 7.1. Sq (r_{1}, …, r_{m}) is the ≺_{A}-largest summand of γ Sq (r_{1}, …, r_{m})_{Mil} .

Thus the Arnon A basis is triangular with respect to the Milnor basis and we have the recursive formula (1) for converting an element of A from the Milnor basis to the basis B_{ArA}.

Corollary 7.2. Let Sq ⟨R⟩ ∈ B_{Mil} and suppose γ (Sq ⟨R⟩)_{Mil} = Sq ⟨R⟩+∑_{i} Sq ⟨R_{i}⟩ . Then

Sq ⟨R⟩_{ArA} = γ Sq ⟨R⟩ + ∑_{i} Sq ⟨R_{i}⟩_{ArA}

is a well defined recursive formula for computing Sq ⟨R⟩_{ArA}.

For example, to compute Sq (2, 2)_{ArA} we first compute γ Sq (2, 2) = X_{1}^{1}X_{1}^{2}. By the Milnor product formula

X_{1}^{1}X_{1}^{2} = Sq (2) Sq (4) Sq (2)
= Sq (2, 2) + Sq (5, 1) .

Applying Corollary 7.2 to the error term we find γ Sq (5, 1) = X_{0}^{0}X_{0}^{1}X_{2}^{2}. So by the product formula

X_{0}^{0}X_{0}^{1}X_{2}^{2} = Sq (1) Sq (2) Sq (1) Sq (4)
= Sq(5, 1).

Thus we have the desired answer

Sq (2, 2) = X_{1}^{1}X_{1}^{2} + X_{0}^{0}X_{0}^{1}X_{2}^{2}.

In order to prove these results we begin by defining some notation that will be convenient.

Definition 7.4. Let Sq (r_{1}, …, r_{m}) be any Milnor basis element. We say Sq (r_{1}, …, r_{m}) is zero up to (h, k) if α_{i} (r_{j}) = 0 for all (i, j) ≪ (h, k) .

Definition 7.5. Let Sq (r_{1}, …, r_{m}) be any Milnor basis element. We say Sq (r_{1}, …, r_{m}) has a 1 at (h, k) if α_{k} (r_{h}) = 1.

Clearly if Sq ⟨R⟩ is zero through (h, k) and Sq ⟨S⟩ is not, then Sq ⟨S⟩ ≺_{A} Sq ⟨R⟩ . 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 θ = X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} ∈ B_{ArA} and let Sq (r_{1}, …, r_{m}) = γ^{−1} (θ) . Then

1. Sq (r_{1}, …, r_{m}) has a 1 at (n_{0} − k_{0} + 1, k_{0}) .

2. Sq (r_{1}, …, r_{m}) is zero up to (n_{0} − k_{0} + 1, k_{0})

3. X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} = Sq (2^{n_{0}}) X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} and X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} ∈ B_{ArA} (take X_{k_{0}}^{n_{0}−1} = 1 if n_{0} = k_{0}).

4. γ^{−1} (X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) = Sq (r_{1}, …, r_{h−1}, r_{h} + 2^{k_{0}}, r_{h+1} − 2^{k_{0}}, r_{h+2}, …, r_{m}) where

h = n_{0}−k_{0} ( if h = 0 we interpret the right hand expression as Sq (r_{1} − 2^{k_{0}}, r_{2}, …, r_{m})).

Proof: (1) By definition of γ, X_{k_{0}}^{n_{0}} being a factor of θ implies that α_{k_{0}} (r_{n_{0}−k_{0}+1}) = 1 which in turn implies that Sq (r_{1}, …, r_{m}) has a 1 at (n_{0} − k_{0} + 1, k_{0}) .

(2) Assume the contrary. Then there must be (i, j) ≪ (n_{0} − k_{0} + 1, k_{0}) such that Sq (r_{1}, …, r_{m}) has a 1 at (i, j) , i.e. such that α_{j} (r_{i}) = 1. Thus by definition of γ, X_{j}^{i+j−1} must be a factor of θ. Now (i, j) ≪ (n_{0} − k_{0} + 1, k_{0}) implies that either i+j < n_{0} +1 or else i+j = n_{0} +1 and j < k_{0} so that in either case (i + j − 1, j) ≺_{L} (n_{0}, k_{0}) . But this contradicts the factor X_{k_{0}}^{n_{0}} must be the smallest factor in left lexicographic order of its indices by definition of B_{ArA}.

(3) This follows trivially from

(n_{0} − 1, k_{0}) ≺_{L} (n_{0}, k_{0}) ≺_{L} ⋯ ≺_{L} (n_{m}, k_{m})

and X_{k_{0}}^{n_{0}} = Sq (2^{n_{0}}) Sq (2^{n_{0}−1}) ⋯ Sq (2^{k_{0}}) = Sq (2^{n_{0}}) X_{k_{0}}^{n_{0}−1}.

(4) Since X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} and X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} only differ in the first factor, then

by definition of γ, Sq (r_{1}, …, r_{m}) and γ^{−1} (X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) must have identical binary charts with the exception of the 1’s corresponding to the leading factors. By (1), Sq (r_{1}, …, r_{m}) has a 1 at (n_{0} − k_{0} + 1, k_{0}) and γ^{−1} (X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) has a 1 at (n_{0} − k_{0}, k_{0}) . But by (2) Sq (r_{1}, …, r_{m}) does not have a 1 at (n_{0} − k_{0}, k_{0}) and it is clear that γ^{−1} (X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) does not have a 1 at (n_{0} − k_{0} + 1, k_{0}) since X_{k_{0}}^{n_{0}} is not a factor (remembering that (n_{0}, k_{0}) ≺_{L} (n_{1}, k_{1})). Thus to obtain

γ^{−1} (X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) from Sq (r_{1}, …, r_{m}) we simply remove the 1 at (n_{0} − k_{0} + 1, k_{0}) by subtracting 2^{k_{0}} from r_{n_{0}−k_{0}+1} and create a 1 at (n_{0} − k_{0}, k_{0}) by adding 2^{k_{0}} to r_{n_{0}−k_{0}}. Thus

γ^{−1} (X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) = Sq (r_{1}, …, r_{n_{0}−k_{0}} + 2^{k_{0}}, r_{n_{0}−k_{0}+1} − 2^{k_{0}}, …, r_{m})

as required. □ We are now ready to prove Theorem 7.1. Proof of Theorem 7.1. It suffices to show that γ^{−1} (X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}})is the ≺_{A}-

largest summand of (X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}})_{Mil} . So let X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} ∈ B_{ArA}. Then

γ^{−1} (X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) = Sq (r_{1}, …, r_{m}) where α_{k} (r_{n−k+1}) = 1 if and only if X_{k}^{n} is a factor of X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}. Let q = ∑_{i=0}^{p} (n_{i} − k_{i} + 1) which is the total number of factors of the form Sq (2^{i}) in the product X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}} when expanded using the definition of X_{k}^{n}. We proceed by induction on q.

If q = 1 then p = 0 and n_{0} = k_{0} so that (X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}})_{Mil} = Sq (2^{n_{0}})_{Mil} =

Sq (2^{n_{0}}) and γ^{−1} (X_{n_{0}}^{n_{0}}) = Sq (2^{n_{0}}) and hence the theorem holds.

Assume that the theorem is true for all θ in B_{ArA} having less than q factors of the form Sq (2^{i}). Then by Lemma 7.3

γ (X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}}) = Sq (r_{1}, …, r_{h} + 2^{k_{0}}, r_{h+1} − 2^{k_{0}}, …, r_{m})

where h = n_{0} − k_{0}. For brevity let

R̃ = r_{1}, …, r_{h} + 2^{k_{0}}, r_{h+1} − 2^{k_{0}}, …, r_{m}.

So by our inductive hypothesis we have

(X_{k_{0}}^{n_{0}}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}})_{Mil} = (Sq (2^{n_{0}}) X_{k_{0}}^{n_{0}−1}X_{k_{1}}^{n_{1}} ⋯ X_{k_{p}}^{n_{p}})_{Mil}
= Sq (2^{n_{0}}) (Sq \left⟨{ \atop R̃}\right⟩ + ∑ Sq ⟨S_{i}⟩)
= Sq (2^{n_{0}}) Sq \left⟨{ \atop R̃}\right⟩ + ∑ Sq (2^{n_{0}}) Sq ⟨S_{i}⟩

where Sq ⟨S_{i}⟩ ≺_{A} Sq \left⟨{ \atop R̃}\right⟩ for all i.

Now the matrix X

\begin{matrix}* & r_{1} & ⋯ & r_{h} & r_{h+1} − 2^{k_{0}} & ⋯ & r_{m} \\ 0 & 0 & ⋯ & 2^{k_{0}} & 0 & ⋯ & 0 \end{matrix} (12)

is Sq (2^{n_{0}}) Sq \left⟨{ \atop R̃}\right⟩-admissible since it clearly satisfies (3), (4) (because 2^{h}2^{k_{0}} = 2^{n_{0}−k_{0}}2^{k_{0}} = 2^{n_{0}}), and (5) (since 2^{k_{0}} ∈ r_{h+1} by Lemma 7.3 (1) it follows that 2^{k_{0}} ∉ r_{h+1} − 2^{k_{0}} ). The matrix X produces Sq (r_{1}, …, r_{m}) as desired.

Let X be any other Sq (2^{n_{0}}) Sq \left⟨{ \atop R̃}\right⟩ -allowable matrix which produces Sq (t_{1}, …, t_{n}). Then X has the form

\begin{matrix}* & x_{1} & x_{2} & ⋯ & x_{w} \\ y_{0} & y_{1} & y_{2} & ⋯ & y_{w} \end{matrix} . (13)

We consider two cases: h ≠ 0 and h = 0.

Case 1: h ≠ 0.

Since X is admissible, ∑ 2^{i}y_{i} = 2^{n_{0}} and hence y_{h} ≤ 2^{k_{0}}. But y_{h} ≠ 2^{k_{0}} since we are assuming this matrix is not the same as (12). So y_{h} < 2^{k_{0}}. Thus by (3) x_{h} = r_{h} + 2^{k_{0}} − y_{h}. But since y_{h} < 2^{k_{0}} there exists u ≤ k_{0} such that 2^{u} ∈ x_{h} (this follows from the fact that 2^{i} ∉ r_{h} for i ≤ k_{0} since Sq (r_{1}, …, r_{m}) is zero up to (h + 1, k_{0}) by Lemma 7.3). But also t_{h} = x_{h} + y_{h−1} and so by (5) 2^{u} ∈ t_{h} also. Thus Sq (t_{1}, …, t_{n}) has a 1 at (h, u) . But h + u ≤ h + k_{0} < h + k_{0} + 1 so that (h, u) ≪ (h + 1, k_{0}) . But Sq (r_{1}, …, r_{m}) is zero up to (h + 1, k_{0}) so that Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

Case 2: h = 0.

In this case n_{0} = k_{0}. Since X is admissible, ∑ 2^{i}y_{i} = 2^{n_{0}} and thus there must be some v such that y_{v} ≠ 0 and consequently some u such that 2^{u} ∈ y_{v} with u + v ≤ n_{0}. Notice also that we have u < k_{0} since we are assuming this matrix is not the same as (12). By (5) 2^{u} ∈ y_{v} implies 2^{u} ∈ t_{v+1}. Thus Sq (t_{1}, …, t_{n}) has a 1 at (v + 1, u) . But u + v + 1 ≤ n_{0} + 1 and u < k_{0} so that (v + 1, u) ≪ (1, k_{0}) . By Lemma 7.3 Sq (r_{1}, …, r_{m}) is zero up to (1, k_{0}) so that Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

So in both cases we have shown that any other Sq (2^{n_{0}}) Sq \left⟨{ \atop R̃}\right⟩-allowable matrix other than (12) produces Sq (t_{1}, …, t_{n}) which is strictly ≺_{A} less than Sq (r_{1}, …, r_{m}) . Thus Sq (r_{1}, …, r_{m}) is a summand of the product Sq (2^{n_{0}}) Sq \left⟨{ \atop R̃}\right⟩ .

So all that remains to be demonstrated is that Sq (r_{1}, …, r_{m}) is not a summand of Sq (2^{n_{0}}) Sq ⟨S_{i}⟩ for any of the terms Sq ⟨S_{i}⟩ ≺_{A} Sq \left⟨{ \atop R̃}\right⟩. So let Sq ⟨S_{i}⟩ = Sq (s_{1}, …, s_{n}) be any such term. We again consider two cases.

Case 1: h = 0.

In this case n_{0} = k_{0}. Let X be a Sq (2^{n_{0}}) Sq ⟨S_{i}⟩-allowable matrix (which must be of the form (13)). Since ∑ 2^{i}y_{i} = 2^{n_{0}} there must be some v such that y_{v} ≠ 0 and consequently some u such that 2^{u} ∈ y_{v} with u + v ≤ n_{0}. By (5) 2^{u} ∈ y_{v} implies 2^{u} ∈ t_{v+1}. Thus Sq (t_{1}, …, t_{n}) has a 1 at (v + 1, u) . Since u + v ≤ n_{0} it follows that u + v + 1 ≤ n_{0} + 1.

Case 1.1: u + v + 1 < n_{0} + 1 or u + v + 1 = n_{0} + 1 and u < n_{0}. In this case (v + 1, u) ≪ (1, n_{0}) . But Sq (r_{1}, …, r_{m}) is zero up to (1, n_{0}) so that Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

Case 1.2: u + v + 1 = n_{0} + 1 and u = n_{0}.

In this case v = 0. Since X is allowable, 2^{n_{0}} ∉ s_{1} (by (5)). Thus X produces Sq (t_{1}, …, t_{n}) where t_{1} = s_{1}+2^{n_{0}}, and t_{i} = s_{i} for i > 1. Thus it is easy to see that the binary chart of Sq (t_{1}, …, t_{n}) is identical to that of Sq (s_{1}, …, s_{n}) with the exception of the 1 at location (1, n_{0}) of Sq (t_{1}, …, t_{n}) . Similarly, the binary chart of Sq (r_{1}, …, r_{m}) is identical to that of Sq \left⟨{ \atop R̃}\right⟩ with the excep-

tion of the 1 at location (1, n_{0}) of Sq (r_{1}, …, r_{m}) (since Sq \left⟨{ \atop R̃}\right⟩ is zero up to

(n_{1} − k_{1} + 1, k_{1}) ≫ (1, k_{0})). Then the fact that Sq (s_{1}, …, s_{n}) ≺_{A} Sq \left⟨{ \atop R̃}\right⟩ implies that there exists (a, b) such that the binary charts of Sq (s_{1}, …, s_{n}) and Sq \left⟨{ \atop R̃}\right⟩ match at all locations (i, j) ≪ (a, b) and that Sq (s_{1}, …, s_{n})

has a 1 at (a, b) while Sq \left⟨{ \atop R̃}\right⟩ has a 0 at (a, b) . Simply changing the 0 at (1, n_{0}) on both charts to a 1 does not affect this situation so that once again Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

Case 2: h > 0.

Let X be a Sq (2^{n_{0}}) Sq ⟨S_{i}⟩-allowable matrix which produces Sq (t_{1}, …, t_{n}) (and must be of the form (13)). Once again since ∑ 2^{i}y_{i} = 2^{n_{0}} there must be some v such that y_{v} ≠ 0 and consequently some u such that 2^{u} ∈ y_{v} with u + v ≤ n_{0}. By (5) 2^{u} ∈ y_{v} implies 2^{u} ∈ t_{v+1}. Thus Sq (t_{1}, …, t_{n}) has a 1 at (v + 1, u) .

Case 2.1: u + v < n_{0} or (u + v = n_{0} and u < k_{0}).

In this case (v + 1, u) ≪ (n_{0} − k_{0} + 1, k_{0}) . But Sq (r_{1}, …, r_{m}) is zero up to (n_{0} − k_{0} + 1, k_{0}) so that Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

Case 2.2 u + v = n_{0} and u ≥ k_{0}. Then X has the form

\begin{matrix}* & s_{1} & ⋯ & s_{v−1} & s_{v} − 2^{u} & s_{v+1} & ⋯ & s_{n} \\ 0 & 0 & ⋯ & 0 & 2^{u} & 0 & ⋯ & 0 \end{matrix}

Case 2.2.1: 2^{u} ∉ s_{v}. In this case 2^{u} ∈ s_{v} − 2^{u} which implies that 2^{u} ∈ t_{v}. Thus Sq (t_{1}, …, t_{n}) has a 1 at (v, u) . But u+v = n_{0} < n_{0}+1 so that (v, u) ≪ (n_{0} − k_{0} + 1, k_{0}) . But Sq (r_{1}, …, r_{m}) is zero up to (n_{0} − k_{0} + 1, k_{0}) so that Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

Case 2.2.2: 2^{u} ∈ s_{v}. In this case we have

Sq (t_{1}, …, t_{n}) = Sq (s_{1}, …, s_{v} − 2^{u}, s_{v+1} + 2^{u}, s_{v+2}, …, s_{n}) .

Notice that 2^{u} ∉ s_{v+1} since X is admissible, so that the only difference between the binary charts of Sq (t_{1}, …, t_{n}) and Sq (s_{1}, …, s_{n}) is that the 1 at (v, u) in Sq (s_{1}, …, s_{n}) is moved to location (v + 1, u) in Sq (t_{1}, …, t_{n}) . Also the difference between the binary charts of Sq \left⟨{ \atop R̃}\right⟩

and Sq (r_{1}, …, r_{m}) is that the 1 at location (h, k_{0}) in Sq \left⟨{ \atop R̃}\right⟩ is moved to location (h + 1, k_{0}) in Sq (r_{1}, …, r_{m}) . By definition Sq (s_{1}, …, s_{n}) ≺_{A} Sq \left⟨{ \atop R̃}\right⟩ implies that there exists (a, b) such that the binary charts of

Sq (s_{1}, …, s_{n}) and Sq \left⟨{ \atop R̃}\right⟩ match at all locations (i, j) ≪ (a, b) and

that Sq (s_{1}, …, s_{n}) has a 1 at (a, b) while Sq \left⟨{ \atop R̃}\right⟩ has a 0 at (a, b) . Case 2.2.2.1: u = k_{0}.

In this case (v, u) = (h, k_{0}). It is clear that simply moving the 1 at (h, k_{0}) to location (h + 1, k_{0}) 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 charts at (a, b), so that once again Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

Case 2.2.2.2: u > k_{0}. Since Sq \left⟨{ \atop R̃}\right⟩ has a 1 at (h, k_{0}) and is zero up to (h, k_{0}) and also

Sq ⟨S_{i}⟩ ≺_{A} Sq \left⟨{ \atop R̃}\right⟩ then either Sq (s_{1}, …, s_{n}) is not zero up to (h, k_{0}) or else it is and it has a 1 at (h, k_{0}) also.

Case 2.2.2.2.1: Sq (s_{1}, …, s_{n}) is not zero up to (h, k_{0}). In this case there is a 1 at (i, j) for some (i, j) ≪ (h, k_{0}) ≪ (v, u) . As the binary charts of Sq (t_{1}, …, t_{n}) and Sq (s_{1}, …, s_{n}) only differ at locations (v, u) and (v + 1, u), Sq (t_{1}, …, t_{n}) must also have a 1 at (i, j) ≪ (h, k_{0}) ≪ (h + 1, k_{0}) . Thus since Sq (r_{1}, …, r_{m}) is zero up to (h + 1, k_{0}) we have Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

Case 2.2.2.2.2: Sq (s_{1}, …, s_{n}) is zero up to (h, k_{0}) and has a 1 at (h, k_{0}). Since the binary charts of Sq (t_{1}, …, t_{n}) and Sq (s_{1}, …, s_{n}) only differ at locations (v, u) and (v + 1, u) and (h, k_{0}) ≪ (v, u), Sq (t_{1}, …, t_{n}) must also have a 1 at (h, k_{0}) ≪ (h + 1, k_{0}) . Thus since Sq (r_{1}, …, r_{m}) is zero up to (h + 1, k_{0}) we have Sq (t_{1}, …, t_{n}) ≺_{A} Sq (r_{1}, …, r_{m}) .

□

8. Non-triangular Bases

The remaining bases, B_{W all}, B_{W dY}, and B_{W dZ} are not triangular with respect to the Milnor basis. There is an interesting relationship between the B_{W all} and B_{W dZ} bases however, which we note in this section.

To see that B_{W all} is not triangular with respect to the Milnor basis we consider grading 9. In this grading the elements of B_{W all} are Sq^{8,1}, Sq^{1,2,4,2}, Sq^{2,4,1,2}, Sq^{2,4,2,1}, and Sq^{4,2,1,2}. By the Milnor product formula these equal:

Sq^{8,1} = Sq (9) + Sq (6, 1)
Sq^{1,2,4,2} = Sq (3, 2)
Sq^{2,4,1,2} = Sq (6, 1) + Sq (0, 3) + Sq (3, 2)
Sq^{2,4,2,1} = Sq (3, 2) + Sq (0, 3) + Sq (2, 0, 1)
Sq^{4,2,1,2} = Sq (6, 1) + Sq (0, 3) + Sq (2, 0, 1) .

Clearly, any bijection γ mapping B_{W all} to B_{Mil} must have γ Sq^{1,2,4,2} = Sq (3, 2) . Now suppose we want to find an ordering ≺ of B_{Mil} in grading 9 and extend γ so that θ_{Mil} = γ (θ) + ∑ Sq ⟨R_{i}⟩ where each Sq ⟨R_{i}⟩ ≺ γ (θ) . 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 γ map θ to the largest summand forces γ Sq^{2,4,1,2} = γ Sq^{4,2,1,2} = Sq (6, 1) which contradicts the injectivity of γ. 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 B_{W all} is not triangular with respect tot the Milnor basis. An exactly analogous argument in grading 9 proves that both B_{W dY} and B_{W dZ} are not triangular with respect to the Milnor basis either.

The Wood bases are related to each other in the same sense that the P_{t}^{s} bases 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 relationship of sorts between the Wall basis and the Wood Z basis. We have the following:

Theorem 8.1. Y_{n−k}^{k} is the ≺_{E} largest summand of (Q_{k}^{n})_{Mil}.

The proof of this theorem is very similar to the proof of Theorem 5.1 and will not be presented here. Thus we are naturally led to consider the bijection γ : B_{W all} → B_{W dZ} by

γ (Q_{k_{0}}^{n_{0}}Q_{k_{1}}^{n_{1}} ⋯ Q_{k_{p}}^{n_{p}}) = Y_{n_{0}−k_{0}}^{k_{0}}Y_{n_{1}−k_{1}}^{k_{1}} ⋯ Y_{n_{p}−k_{p}}^{k_{p}}.

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 B_{W dZ} as claimed.

We close this section by commenting that it is conceivable that these three bases 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) 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.

9. Product Relations

In order to improve on the change of basis formulas derived above, we would like 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 further investigation yields an infinite subset of B_{Mil} ∩ B_{Adm}. By Theorem 4.1 any element θ ∈ B_{Mil} ∩ B_{Adm} must satisfy γ (θ) = θ , i.e. it must be an eigenvector of γ (extended to a linear transformation of A).

Theorem 9.1. If r_{i} ≡ −1 mod 2^{ω(r_{i+1})} for all 1 ≤ i < m then Sq (r_{1}, …, r_{m}) ∈ B_{Mil} ∩ B_{Adm} (and in this case Sq (r_{1}, …, r_{m}) = γ Sq (r_{1}, …, r_{m}) ).

We point out that this linear algebra result is also providing us with information about products, i.e. Sq^{t_{1}} Sq^{t_{2}} ⋯ Sq^{t_{m}} = Sq (r_{1}, …, r_{m}) where r_{i} = t_{i} − 2t_{i+1} (take t_{m+1} = 0 ) if r_{i} ≡ −1 mod 2^{ω(r_{i+1})} for all 1 ≤ i < m.

We also note out that the condition r_{i} ≡ −1 mod 2^{ω(r_{i+1})} can easily be checked by writing the ordinary binary representations of numbers r_{1}, r_{2}, …, r_{m} in horizontally above one another (with r_{1} on top) and checking that no digit ever appears below a 0. This is because of the following trivial fact which we state without proof:

(14) r ≡ −1 mod 2^{w} ⇔ 2^{k} ∈ r for all k < w.

For example, Sq (13, 5, 1) is not equal to an admissible monomial because writing the indices in base 2 yields:

13 = 1 1 0 1_{2}
5 =  1 0 1_{2}
1 =  1_{2}

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 Theorem 9.1 we deduce that Sq (7, 5, 1) = Sq^{21} Sq^{7} Sq^{1} .

We will also need to make use of the following fact whose verification is an elementary exercise in binary arithmetic.

Lemma 9.2. Let x, y, r, w be nonnegative integers. If r ≡ −1 mod 2^{w} and x + y = r then for any k < w either 2^{k} ∈ x or 2^{k} ∈ y but not both, i.e. α_{k} (x) + α_{k} (y) = 1.

We now turn our attention to proving Theorem 9.1.

Proof of Theorem 9.1. Let R = r_{1}, …, r_{m} be any sequence satisfying r_{i} ≡ −1 mod 2^{ω(r_{i+1})} for all i. We would like to show that γ Sq ⟨R⟩ = Sq ⟨R⟩ . We proceed by induction on m.

If m = 1 then γ Sq (r_{1}) = Sq (r_{1}) by definition of γ.

Now for the inductive hypothesis assume that for any Sq (s_{1}, …, s_{k}) ∈ B_{Mil} with k < m, if s_{i} ≡ −1 mod 2^{ω(s_{i+1})} for all i then γ Sq ⟨S⟩ = Sq ⟨S⟩ . In particular, we have γ Sq (r_{2}, …, r_{m}) = Sq (r_{2}, …, r_{m}) .

Let Sq^{⟨T ⟩} = γ (R) where T = t_{1}, …, t_{m}. Then clearly γ Sq (r_{2}, …, r_{m}) = Sq^{t_{2}} ⋯ Sq^{t_{m}} so that

γ Sq ⟨R⟩ = Sq (t_{1}) Sq (t_{2}) ⋯ Sq (t_{m})
= Sq (t_{1}) γ Sq (r_{2}, …, r_{m})
= Sq (t_{1}) Sq (r_{2}, …, r_{m}) .

So it suffices to show that Sq (t_{1}) Sq (r_{2}, …, r_{m}) = Sq (r_{1}, …, r_{m}) by the Milnor product formula.

Let X be a Sq (t_{1}) Sq (r_{2}, …, r_{m})-allowable matrix. Then X is of the form

\begin{matrix}* & x_{2} & x_{3} & ⋯ & x_{m} \\ y_{1} & y_{2} & y_{3} & ⋯ & y_{m} \end{matrix}

such that for 2 ≤ i ≤ m

x_{i} + y_{i} = r_{i} (15) x_{i} ≍ y_{i−1} (16)

and also satisfying

t_{1} = ∑_{i=1}^{m} 2^{i−1}y_{i}. (17)

Let j > 2 and suppose 2^{i} ∈ x_{j}. We would like to show that 2^{i} ∈ x_{j−1} also. Now 2^{i} ∈ x_{j} implies that 2^{i} ≤ x_{j} ≤ r_{j} < 2^{ω(r_{j})} by (15) and r_{j−1} ≡ −1 mod 2^{ω(r_{j})} implies that 2^{k} ∈ r_{j−1} for all k < ω (r_{j}) by (14). Combining these facts shows 2^{i} ∈ r_{j−1}. So by (15) and Lemma 9.2 either 2^{i} ∈ x_{j−1} or 2^{i} ∈ y_{j−1}. But 2^{i} ∉ y_{j−1} by condition (16), so 2^{i} ∈ x_{j−1} . Thus we have shown that 2^{i} ∈ x_{j} implies 2^{i} ∈ x_{j−1} . So by induction we have 2^{i} ∈ x_{j} implies 2^{i} ∈ x_{2}. In particular, ν (x_{j}) ≥ ν (x_{2}) for all j.

Now suppose x_{2} ≠ 0. Then 2^{ν(x_{2})} ∈ x_{2}. By Lemma 9.2 this implies that 2^{ν(x_{2})} ∈ r_{2} which in turn implies that 2^{ν(x_{2})} ∈ r_{1} by (14). Now since ν (x_{j}) ≥ ν (x_{2}) if follows that 2^{ν(x_{2})} divides x_{j} for all j, i.e. that

x_{j} = 2^{ν(x_{2})}h_{j} (18)

for some nonnegative integer h_{j}. Solving (17) for y_{1}, substituting for t_{1} using (8) and applying (18) gives us

y_{1} = t_{1} − ∑_{k=2}^{m} 2^{k−1}y_{k}

= ∑_{k=1}^{m} 2^{k−1}r_{k} − ∑_{k=2}^{m} 2^{k−1}y_{k}

= r_{1} + ∑_{k=2}^{m} 2^{k−1} (r_{k} − y_{k})

= r_{1} + ∑_{k=2}^{m} 2^{k−1}x_{k}

= r_{1} + ∑_{k=2}^{m} 2^{k−1}2^{ν(x_{2})}h_{k}

= r_{1} + 2^{ν(x_{2})+1} (∑_{k=2}^{m} 2^{k−2}h_{k})

Combining this with the fact that 2^{ν(x_{2})} ∈ r_{1}, it follows by (7) that 2^{ν(x_{2})} ∈ y_{1}. Thus 2^{ν(x_{2})} ∈ y_{1} and 2^{ν(x_{2})} ∈ x_{2} which contradicts (16). Therefore our assumption that x_{2} ≠ 0 must be false.

So x_{2} = 0. But ν (x_{j}) ≥ ν (x_{2}) for all j , so it follows that x_{j} = 0 for all j . Hence X must be the matrix

\begin{matrix}* & 0 & 0 & ⋯ & 0 \\ r_{1} & r_{2} & r_{3} & ⋯ & r_{m} \end{matrix}

which is clearly admissible and produces Sq (r_{1}, …, r_{m}). □

References

[Arn] Arnon, D.; Monomial Bases in the Steenrod Algebra, Journal of Pure and Applied Algebra 96 (1994), 215-223

[Mar] Margolis, H. R.; Spectra and the Steenrod Algebra, North Holland, 1983, ISBN: 0-444-86516-0 [Wall] Wall, C. T. C.; Generators and Relations for the Steenrod Algebra, Ann. of Math. (3) 72

(1960), 429-444

[Wo] Wood, R. M. W.; A note on Bases and Relations in the Steenrod Algebra, Bull. London Math. Soc., 27 (1995), 380-386

[Mil] Milnor, J.; The Steenrod algebra and its dual, Ann. of Math. (2) 67 (1958), 150-171

CHANGE OF BASIS IN THE STEENROD ALGEBRA 27

Department of Mathematics, University of Scranton, Scranton, PA 18510

E-mail address: monks@uofs.edu