Multiplication for elements of the Steenrod algebra#

AUTHORS:

• John H. Palmieri (2008-07-30: version 0.9) initial version: Milnor multiplication.

• John H. Palmieri (2010-06-30: version 1.0) multiplication of Serre-Cartan basis elements using the Adem relations.

• Simon King (2011-10-25): Fix the use of cached functions.

Milnor multiplication, $$p=2$$

See Milnor’s paper [Mil1958] for proofs, etc.

To multiply Milnor basis elements $$\text{Sq}(r_1, r_2, ...)$$ and $$\text{Sq}(s_1, s_2,...)$$ at the prime 2, form all possible matrices $$M$$ with rows and columns indexed starting at 0, with position (0,0) deleted (or ignored), with $$s_i$$ equal to the sum of column $$i$$ for each $$i$$, and with $$r_j$$ equal to the ‘weighted’ sum of row $$j$$. The weights are as follows: elements from column $$i$$ are multiplied by $$2^i$$. For example, to multiply $$\text{Sq}(2)$$ and $$\text{Sq}(1,1)$$, form the matrices

$\begin{split}\begin{Vmatrix} * & 1 & 1 \\ 2 & 0 & 0 \end{Vmatrix} \quad \text{and} \quad \begin{Vmatrix} * & 0 & 1 \\ 0 & 1 & 0 \end{Vmatrix}\end{split}$

(The $$*$$ is the ignored (0,0)-entry of the matrix.) For each such matrix $$M$$, compute a multinomial coefficient, mod 2: for each diagonal $$\{m_{ij}: i+j=n\}$$, compute $$(\sum m_{i,j}!) / (m_{0,n}! m_{1,n-1}! ... m_{n,0}!)$$. Multiply these together for all $$n$$. (To compute this mod 2, view the entries of the matrix as their base 2 expansions; then this coefficient is zero if and only if there is some diagonal containing two numbers which have a summand in common in their base 2 expansion. For example, if 3 and 10 are in the same diagonal, the coefficient is zero, because $$3=1+2$$ and $$10=2+8$$: they both have a summand of 2.)

Now, for each matrix with multinomial coefficient 1, let $$t_n$$ be the sum of the nth diagonal in the matrix; then

$\text{Sq}(r_1, r_2, ...) \text{Sq}(s_1, s_2, ...) = \sum \text{Sq}(t_1, t_2, ...)$

The function milnor_multiplication() takes as input two tuples of non-negative integers, $$r$$ and $$s$$, which represent $$\text{Sq}(r)=\text{Sq}(r_1, r_2, ...)$$ and $$\text{Sq}(s)=\text{Sq}(s_1, s_2, ...)$$; it returns as output a dictionary whose keys are tuples $$t=(t_1, t_2, ...)$$ of non-negative integers, and for each tuple the associated value is the coefficient of $$\text{Sq}(t)$$ in the product formula. (Since we are working mod 2, this coefficient is 1 – if it is zero, the element is omitted from the dictionary altogether).

Milnor multiplication, odd primes

As for the $$p=2$$ case, see Milnor’s paper [Mil1958] for proofs.

Fix an odd prime $$p$$. There are three steps to multiply Milnor basis elements $$Q_{f_1} Q_{f_2} ... \mathcal{P}(q_1, q_2, ...)$$ and $$Q_{g_1} Q_{g_2} ... \mathcal{P}(s_1, s_2,...)$$: first, use the formula

$\mathcal{P}(q_1, q_2, ...) Q_k = Q_k \mathcal{P}(q_1, q_2, ...) + Q_{k+1} \mathcal{P}(q_1 - p^k, q_2, ...) + Q_{k+2} \mathcal{P}(q_1, q_2 - p^k, ...) + ...$

Second, use the fact that the $$Q_k$$’s form an exterior algebra: $$Q_k^2 = 0$$ for all $$k$$, and if $$i \neq j$$, then $$Q_i$$ and $$Q_j$$ anticommute: $$Q_i Q_j = -Q_j Q_i$$. After these two steps, the product is a linear combination of terms of the form

$Q_{e_1} Q_{e_2} ... \mathcal{P}(r_1, r_2, ...) \mathcal{P}(s_1, s_2, ...).$

Finally, use Milnor matrices to multiply the pairs of $$\mathcal{P}(...)$$ terms, as at the prime 2: form all possible matrices $$M$$ with rows and columns indexed starting at 0, with position (0,0) deleted (or ignored), with $$s_i$$ equal to the sum of column $$i$$ for each $$i$$, and with $$r_j$$ equal to the weighted sum of row $$j$$: elements from column $$i$$ are multiplied by $$p^i$$. For example when $$p=5$$, to multiply $$\mathcal{P}(5)$$ and $$\mathcal{P}(1,1)$$, form the matrices

$\begin{split}\begin{Vmatrix} * & 1 & 1 \\ 5 & 0 & 0 \end{Vmatrix} \quad \text{and} \quad \begin{Vmatrix} * & 0 & 1 \\ 0 & 1 & 0 \end{Vmatrix}\end{split}$

For each such matrix $$M$$, compute a multinomial coefficient, mod $$p$$: for each diagonal $$\{m_{ij}: i+j=n\}$$, compute $$(\sum m_{i,j}!) / (m_{0,n}! m_{1,n-1}! ... m_{n,0}!)$$. Multiply these together for all $$n$$.

Now, for each matrix with nonzero multinomial coefficient $$b_M$$, let $$t_n$$ be the sum of the $$n$$-th diagonal in the matrix; then

$\mathcal{P}(r_1, r_2, ...) \mathcal{P}(s_1, s_2, ...) = \sum b_M \mathcal{P}(t_1, t_2, ...)$

For example when $$p=5$$, we have

$\mathcal{P}(5) \mathcal{P}(1,1) = \mathcal{P}(6,1) + 2 \mathcal{P}(0,2).$

The function milnor_multiplication() takes as input two pairs of tuples of non-negative integers, $$(g,q)$$ and $$(f,s)$$, which represent $$Q_{g_1} Q_{g_2} ... \mathcal{P}(q_1, q_2, ...)$$ and $$Q_{f_1} Q_{f_2} ... \mathcal{P}(s_1, s_2, ...)$$. It returns as output a dictionary whose keys are pairs of tuples $$(e,t)$$ of non-negative integers, and for each tuple the associated value is the coefficient in the product formula.

If $$p=2$$, then the mod 2 Steenrod algebra is generated by Steenrod squares $$\text{Sq}^a$$ for $$a \geq 0$$ (equal to the Milnor basis element $$\text{Sq}(a)$$). The Adem relations are as follows: if $$a < 2b$$,

$\text{Sq}^a \text{Sq}^b = \sum_{j=0}^{a/2} \binom{b-j-1}{a-2j} \text{Sq}^{a+b-j} \text{Sq}^j$

A monomial $$\text{Sq}^{i_1} \text{Sq}^{i_2} ... \text{Sq}^{i_n}$$ is called admissible if $$i_k \geq 2 i_{k+1}$$ for all $$k$$. One can use the Adem relations to show that the admissible monomials span the Steenrod algebra, as a vector space; with more work, one can show that the admissible monomials are also linearly independent. They form the Serre-Cartan basis for the Steenrod algebra. To multiply a collection of admissible monomials, concatenate them and see if the result is admissible. If it is, you’re done. If not, find the first pair $$\text{Sq}^a \text{Sq}^b$$ where it fails to be admissible and apply the Adem relations there. Repeat with the resulting terms. One can prove that this process terminates in a finite number of steps, and therefore gives a procedure for multiplying elements of the Serre-Cartan basis.

At an odd prime $$p$$, the Steenrod algebra is generated by the pth power operations $$\mathcal{P}^a$$ (the same as $$\mathcal{P}(a)$$ in the Milnor basis) and the Bockstein operation $$\beta$$ (= $$Q_0$$ in the Milnor basis). The odd primary Adem relations are as follows: if $$a < pb$$,

$\mathcal{P}^a \mathcal{P}^b = \sum_{j=0}^{a/p} (-1)^{a+j} \binom{(b-j)(p-1)-1}{a-pj} \mathcal{P}^{a+b-j} \mathcal{P}^j$

Also, if $$a \leq pb$$,

$\mathcal{P}^a \beta \mathcal{P}^b = \sum_{j=0}^{a/p} (-1)^{a+j} \binom{(b-j)(p-1)}{a-pj} \beta \mathcal{P}^{a+b-j} \mathcal{P}^j + \sum_{j=0}^{a/p} (-1)^{a+j-1} \binom{(b-j)(p-1)-1}{a-pj-1} \mathcal{P}^{a+b-j} \beta \mathcal{P}^j$

The admissible monomials at an odd prime are products of the form

$\beta^{\epsilon_0} \mathcal{P}^{s_1} \beta^{\epsilon_1} \mathcal{P}^{s_2} ... \mathcal{P}^{s_n} \beta^{\epsilon_n}$

where $$s_k \geq \epsilon_{k+1} + p s_{k+1}$$ for all $$k$$. As at the prime 2, these form a basis for the Steenrod algebra.

The main function for this is make_mono_admissible(), which converts a product of Steenrod squares or pth power operations and Bocksteins into a dictionary representing a sum of admissible monomials.

The mod $$p$$ Adem relations

INPUT:

• $$a$$, $$b$$, $$c$$ (optional) - nonnegative integers, corresponding to either $$P^a P^b$$ or (if $$c$$ present) to $$P^a \beta^b P^c$$

• $$p$$ - positive prime number (optional, default 2)

• $$generic$$ - whether to use the generic Steenrod algebra, (default: depends on prime)

OUTPUT:

a dictionary representing the mod $$p$$ Adem relations applied to $$P^a P^b$$ or (if $$c$$ present) to $$P^a \beta^b P^c$$.

The mod $$p$$ Adem relations for the mod $$p$$ Steenrod algebra are as follows: if $$p=2$$, then if $$a < 2b$$,

$\text{Sq}^a \text{Sq}^b = \sum_{j=0}^{a/2} \binom{b-j-1}{a-2j} \text{Sq}^{a+b-j} \text{Sq}^j$

If $$p$$ is odd, then if $$a < pb$$,

$P^a P^b = \sum_{j=0}^{a/p} (-1)^{a+j} \binom{(b-j)(p-1)-1}{a-pj} P^{a+b-j} P^j$

Also for $$p$$ odd, if $$a \leq pb$$,

$P^a \beta P^b = \sum_{j=0}^{a/p} (-1)^{a+j} \binom{(b-j)(p-1)}{a-pj} \beta P^{a+b-j} P^j + \sum_{j=0}^{a/p} (-1)^{a+j-1} \binom{(b-j)(p-1)-1}{a-pj-1} P^{a+b-j} \beta P^j$

EXAMPLES:

If two arguments ($$a$$ and $$b$$) are given, then computations are done mod 2. If $$a \geq 2b$$, then the dictionary {(a,b): 1} is returned. Otherwise, the right side of the mod 2 Adem relation for $$\text{Sq}^a \text{Sq}^b$$ is returned. For example, since $$\text{Sq}^2 \text{Sq}^2 = \text{Sq}^3 \text{Sq}^1$$, we have:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import adem
{(3, 1): 1}
{(4, 2): 1}
sage: adem(4,4) == {(6, 2): 1, (7, 1): 1}
True


If $$p$$ is given and is odd, then with two inputs $$a$$ and $$b$$, the Adem relation for $$P^a P^b$$ is computed. With three inputs $$a$$, $$b$$, $$c$$, the Adem relation for $$P^a \beta^b P^c$$ is computed. In either case, the keys in the output are all tuples of odd length, with (i_1, i_2, ..., i_m) representing

$\beta^{i_1} P^{i_2} \beta^{i_3} P^{i_4} ... \beta^{i_m}$

For instance:

sage: adem(3,1, p=3)
{(0, 3, 0, 1, 0): 1}
{(0, 3, 0, 1, 0): 1}
{(0, 2, 0): 2}
sage: adem(1,1,1, p=5) == {(0, 2, 1): 1, (1, 2, 0): 1}
True
sage: adem(1,1,2, p=5) == {(0, 3, 1): 1, (1, 3, 0): 2}
True

sage.algebras.steenrod.steenrod_algebra_mult.binomial_mod2(n, k)#

The binomial coefficient $$\binom{n}{k}$$, computed mod 2.

INPUT:

• $$n$$, $$k$$ - integers

OUTPUT:

$$n$$ choose $$k$$, mod 2

EXAMPLES:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import binomial_mod2
sage: binomial_mod2(4,2)
0
sage: binomial_mod2(5,4)
1
sage: binomial_mod2(3 * 32768, 32768)
1
sage: binomial_mod2(4 * 32768, 32768)
0

sage.algebras.steenrod.steenrod_algebra_mult.binomial_modp(n, k, p)#

The binomial coefficient $$\binom{n}{k}$$, computed mod $$p$$.

INPUT:

• $$n$$, $$k$$ - integers

• $$p$$ - prime number

OUTPUT:

$$n$$ choose $$k$$, mod $$p$$

EXAMPLES:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import binomial_modp
sage: binomial_modp(5,2,3)
1
sage: binomial_modp(6,2,11)  # 6 choose 2 = 15
4


Given a tuple mono, view it as a product of Steenrod operations, and return a dictionary giving data equivalent to writing that product as a linear combination of admissible monomials.

When $$p=2$$, the sequence (and hence the corresponding monomial) $$(i_1, i_2, ...)$$ is admissible if $$i_j \geq 2 i_{j+1}$$ for all $$j$$.

When $$p$$ is odd, the sequence $$(e_1, i_1, e_2, i_2, ...)$$ is admissible if $$i_j \geq e_{j+1} + p i_{j+1}$$ for all $$j$$.

INPUT:

• mono - a tuple of non-negative integers

• $$p$$ - prime number, optional (default 2)

• $$generic$$ - whether to use the generic Steenrod algebra, (default: depends on prime)

OUTPUT:

Dictionary of terms of the form (tuple: coeff), where ‘tuple’ is an admissible tuple of non-negative integers and ‘coeff’ is its coefficient. This corresponds to a linear combination of admissible monomials. When $$p$$ is odd, each tuple must have an odd length: it should be of the form $$(e_1, i_1, e_2, i_2, ..., e_k)$$ where each $$e_j$$ is either 0 or 1 and each $$i_j$$ is a positive integer: this corresponds to the admissible monomial

$\beta^{e_1} \mathcal{P}^{i_2} \beta^{e_2} \mathcal{P}^{i_2} ... \mathcal{P}^{i_k} \beta^{e_k}$

ALGORITHM:

Given $$(i_1, i_2, i_3, ...)$$, apply the Adem relations to the first pair (or triple when $$p$$ is odd) where the sequence is inadmissible, and then apply this function recursively to each of the resulting tuples $$(i_1, ..., i_{j-1}, NEW, i_{j+2}, ...)$$, keeping track of the coefficients.

EXAMPLES:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import make_mono_admissible
{(12,): 1}
{(2, 1): 1}
{(3, 1): 1}
{(5, 1): 1}
sage: make_mono_admissible((0, 2, 0, 1, 0), p=7)
{(0, 3, 0): 3}


Test the fix from github issue #13796:

sage: SteenrodAlgebra(p=2, basis='adem').Q(2) * (Sq(6) * Sq(2)) # indirect doctest
Sq^10 Sq^4 Sq^1 + Sq^10 Sq^5 + Sq^12 Sq^3 + Sq^13 Sq^2

sage.algebras.steenrod.steenrod_algebra_mult.milnor_multiplication(r, s)#

Product of Milnor basis elements r and s at the prime 2.

INPUT:

• r – tuple of non-negative integers

• s – tuple of non-negative integers

OUTPUT:

Dictionary of terms of the form (tuple: coeff), where ‘tuple’ is a tuple of non-negative integers and ‘coeff’ is 1.

This computes Milnor matrices for the product of $$\text{Sq}(r)$$ and $$\text{Sq}(s)$$, computes their multinomial coefficients, and for each matrix whose coefficient is 1, add $$\text{Sq}(t)$$ to the output, where $$t$$ is the tuple formed by the diagonals sums from the matrix.

EXAMPLES:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import milnor_multiplication
sage: milnor_multiplication((2,), (1,)) == {(0, 1): 1, (3,): 1}
True
sage: sorted(milnor_multiplication((4,), (2,1)).items())
[((0, 3), 1), ((2, 0, 1), 1), ((6, 1), 1)]
sage: sorted(milnor_multiplication((2,4), (0,1)).items())
[((2, 0, 0, 1), 1), ((2, 5), 1)]


These examples correspond to the following product computations:

\begin{align}\begin{aligned}\text{Sq}(2) \text{Sq}(1) = \text{Sq}(0,1) + \text{Sq}(3)\\\text{Sq}(4) \text{Sq}(2,1) = \text{Sq}(6,1) + \text{Sq}(0,3) + \text{Sq}(2,0,1)\\\text{Sq}(2,4) \text{Sq}(0,1) = \text{Sq}(2, 5) + \text{Sq}(2, 0, 0, 1)\end{aligned}\end{align}

This uses the same algorithm Monks does in his Maple package: see http://mathweb.scranton.edu/monks/software/Steenrod/steen.html.

sage.algebras.steenrod.steenrod_algebra_mult.milnor_multiplication_odd(m1, m2, p)#

Product of Milnor basis elements defined by m1 and m2 at the odd prime p.

INPUT:

• m1 - pair of tuples (e,r), where e is an increasing tuple of non-negative integers and r is a tuple of non-negative integers

• m2 - pair of tuples (f,s), same format as m1

• p – odd prime number

OUTPUT:

Dictionary of terms of the form (tuple: coeff), where ‘tuple’ is a pair of tuples, as for r and s, and ‘coeff’ is an integer mod p.

This computes the product of the Milnor basis elements $$Q_{e_1} Q_{e_2} ... P(r_1, r_2, ...)$$ and $$Q_{f_1} Q_{f_2} ... P(s_1, s_2, ...)$$.

EXAMPLES:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import milnor_multiplication_odd
sage: sorted(milnor_multiplication_odd(((0,2),(5,)), ((1,),(1,)), 5).items())
[(((0, 1, 2), (0, 1)), 4), (((0, 1, 2), (6,)), 4)]
sage: milnor_multiplication_odd(((0,2,4),()), ((1,3),()), 7)
{((0, 1, 2, 3, 4), ()): 6}
sage: milnor_multiplication_odd(((0,2,4),()), ((1,5),()), 7)
{((0, 1, 2, 4, 5), ()): 1}
sage: sorted(milnor_multiplication_odd(((),(6,)), ((),(2,)), 3).items())
[(((), (0, 2)), 1), (((), (4, 1)), 1), (((), (8,)), 1)]


These examples correspond to the following product computations:

\begin{align}\begin{aligned}p=5: \quad Q_0 Q_2 \mathcal{P}(5) Q_1 \mathcal{P}(1) = 4 Q_0 Q_1 Q_2 \mathcal{P}(0,1) + 4 Q_0 Q_1 Q_2 \mathcal{P}(6)\\p=7: \quad (Q_0 Q_2 Q_4) (Q_1 Q_3) = 6 Q_0 Q_1 Q_2 Q_3 Q_4\\p=7: \quad (Q_0 Q_2 Q_4) (Q_1 Q_5) = Q_0 Q_1 Q_2 Q_3 Q_5\\p=3: \quad \mathcal{P}(6) \mathcal{P}(2) = \mathcal{P}(0,2) + \mathcal{P}(4,1) + \mathcal{P}(8)\end{aligned}\end{align}

The following used to fail until the trailing zeroes were eliminated in p_mono:

sage: A = SteenrodAlgebra(3)
sage: a = A.P(0,3); b = A.P(12); c = A.Q(1,2)
sage: (a+b)*c == a*c + b*c
True


Test that the bug reported in github issue #7212 has been fixed:

sage: A.P(36,6)*A.P(27,9,81)
2 P(13,21,83) + P(14,24,82) + P(17,20,83) + P(25,18,83) + P(26,21,82) + P(36,15,80,1) + P(49,12,83) + 2 P(50,15,82) + 2 P(53,11,83) + 2 P(63,15,81)


Associativity once failed because of a sign error:

sage: a,b,c = A.Q_exp(0,1), A.P(3), A.Q_exp(1,1)
sage: (a*b)*c == a*(b*c)
True


This uses the same algorithm Monks does in his Maple package to iterate through the possible matrices: see http://mathweb.scranton.edu/monks/software/Steenrod/steen.html.

sage.algebras.steenrod.steenrod_algebra_mult.multinomial(list)#

Multinomial coefficient of list, mod 2.

INPUT:

• list – list of integers

OUTPUT:

None if the multinomial coefficient is 0, or sum of list if it is 1

Given the input $$[n_1, n_2, n_3, ...]$$, this computes the multinomial coefficient $$(n_1 + n_2 + n_3 + ...)! / (n_1! n_2! n_3! ...)$$, mod 2. The method is roughly this: expand each $$n_i$$ in binary. If there is a 1 in the same digit for any $$n_i$$ and $$n_j$$ with $$i\neq j$$, then the coefficient is 0; otherwise, it is 1.

EXAMPLES:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import multinomial
sage: multinomial([1,2,4])
7
sage: multinomial([1,2,5])
sage: multinomial([1,2,12,192,256])
463


This function does not compute any factorials, so the following are actually reasonable to do:

sage: multinomial([1,65536])
65537
sage: multinomial([4,65535])
sage: multinomial([32768,65536])
98304

sage.algebras.steenrod.steenrod_algebra_mult.multinomial_odd(list, p)#

Multinomial coefficient of list, mod p.

INPUT:

• list – list of integers

• p – a prime number

OUTPUT:

Associated multinomial coefficient, mod p

Given the input $$[n_1, n_2, n_3, ...]$$, this computes the multinomial coefficient $$(n_1 + n_2 + n_3 + ...)! / (n_1! n_2! n_3! ...)$$, mod $$p$$. The method is this: expand each $$n_i$$ in base $$p$$: $$n_i = \sum_j p^j n_{ij}$$. Do the same for the sum of the $$n_i$$’s, which we call $$m$$: $$m = \sum_j p^j m_j$$. Then the multinomial coefficient is congruent, mod $$p$$, to the product of the multinomial coefficients $$m_j! / (n_{1j}! n_{2j}! ...)$$.

Furthermore, any multinomial coefficient $$m! / (n_1! n_2! ...)$$ can be computed as a product of binomial coefficients: it equals

$\binom{n_1}{n_1} \binom{n_1 + n_2}{n_2} \binom{n_1 + n_2 + n_3}{n_3} ...$

This is convenient because Sage’s binomial function returns integers, not rational numbers (as would be produced just by dividing factorials).

EXAMPLES:

sage: from sage.algebras.steenrod.steenrod_algebra_mult import multinomial_odd
sage: multinomial_odd([1,2,4], 2)
1
sage: multinomial_odd([1,2,4], 7)
0
sage: multinomial_odd([1,2,4], 11)
6
sage: multinomial_odd([1,2,4], 101)
4
sage: multinomial_odd([1,2,4], 107)
105