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
(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
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
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
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
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
For example when \(p=5\), we have
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.
The Adem relations and admissible sequences
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\),
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\),
Also, if \(a \leq pb\),
The admissible monomials at an odd prime are products of the form
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.
- sage.algebras.steenrod.steenrod_algebra_mult.adem(b, c=0, p=2, generic=None)#
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 sage: adem(2,2) # indirect doctest {(3, 1): 1} sage: adem(4,2) {(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} sage: adem(3,0,1, p=3) {(0, 3, 0, 1, 0): 1} sage: adem(1,0,1, p=7) {(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
- sage.algebras.steenrod.steenrod_algebra_mult.make_mono_admissible(p=2, generic=None)#
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 sage: make_mono_admissible((12,)) # already admissible, indirect doctest {(12,): 1} sage: make_mono_admissible((2,1)) # already admissible {(2, 1): 1} sage: make_mono_admissible((2,2)) {(3, 1): 1} sage: make_mono_admissible((2, 2, 2)) {(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