AUTHORS:
Milnor multiplication, \(p=2\)
See Milnor’s paper [Mil] 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 the element is omitted from the dictionary altogether).
Milnor multiplication, odd primes
As for the \(p=2\) case, see Milnor’s paper [Mil] 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_() (and in practice, one should use the cached version, 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.
REFERENCES:
The mod \(p\) Adem relations
INPUT:
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\).
Note
Users should use adem() instead of this function (which has a trailing underscore in its name): adem() is the cached version of this one, and so will be faster.
The mod \(p\) Adem relations for the mod \(p\) Steenrod algebra are as follows: if \(p=2\), then if \(a < 2b\),
If \(p\) is odd, then if \(a < pb\),
Also for \(p\) odd, if \(a \leq pb\),
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}
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
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}
sage: adem(1,1,2, p=5)
{(0, 3, 1): 1, (1, 3, 0): 2}
The binomial coefficient \(\binom{n}{k}\), computed mod 2.
INPUT:
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
The binomial coefficient \(\binom{n}{k}\), computed mod \(p\).
INPUT:
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:
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
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.
Note
Users should use make_mono_admissible() instead of this function (which has a trailing underscore in its name): make_mono_admissible() is the cached version of this one, and so will be faster.
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 trac ticket #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
Product of Milnor basis elements r and s at the prime 2.
INPUT:
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}
sage: milnor_multiplication((4,), (2,1))
{(0, 3): 1, (2, 0, 1): 1, (6, 1): 1}
sage: milnor_multiplication((2,4), (0,1))
{(2, 0, 0, 1): 1, (2, 5): 1}
These examples correspond to the following product computations:
This uses the same algorithm Monks does in his Maple package: see http://mathweb.scranton.edu/monks/software/Steenrod/steen.html.
Product of Milnor basis elements defined by m1 and m2 at the odd prime p.
INPUT:
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: milnor_multiplication_odd(((0,2),(5,)), ((1,),(1,)), 5)
{((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: milnor_multiplication_odd(((),(6,)), ((),(2,)), 3)
{((), (0, 2)): 1, ((), (4, 1)): 1, ((), (8,)): 1}
These examples correspond to the following product computations:
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 #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.
Multinomial coefficient of list, mod 2.
INPUT:
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
Multinomial coefficient of list, mod p.
INPUT:
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
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