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,
See Milnor’s paper [Mil] for proofs, etc.
To multiply Milnor basis elements and
at the prime 2, form all possible matrices
with rows and columns indexed starting at 0, with position (0,0)
deleted (or ignored), with
equal to the sum of column
for
each
, and with
equal to the ‘weighted’ sum of row
. The
weights are as follows: elements from column
are multiplied by
. For example, to multiply
and
,
form the matrices
(The is the ignored (0,0)-entry of the matrix.) For each such
matrix
, compute a multinomial coefficient, mod 2: for each
diagonal
, compute
. Multiply these together for all
. (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
and
: they
both have a summand of 2.)
Now, for each matrix with multinomial coefficient 1, let be
the sum of the nth diagonal in the matrix; then
The function milnor_multiplication()
takes as input two tuples
of non-negative integers, and
, which represent
and
; it returns as output a
dictionary whose keys are tuples
of non-negative
integers, and for each tuple the associated value is the coefficient
of
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 case, see Milnor’s paper [Mil] for proofs.
Fix an odd prime . There are three steps to multiply Milnor basis
elements
and
: first, use the formula
Second, use the fact that the ‘s form an exterior algebra:
for all
, and if
, then
and
anticommute:
. After these two steps, the product is a linear
combination of terms of the form
Finally, use Milnor matrices to multiply the pairs of
terms, as at the prime 2: form all possible
matrices
with rows and columns indexed starting at 0, with
position (0,0) deleted (or ignored), with
equal to the sum of
column
for each
, and with
equal to the weighted sum of
row
: elements from column
are multiplied by
. For
example when
, to multiply
and
, form the matrices
For each such matrix , compute a multinomial coefficient, mod
:
for each diagonal
, compute
. Multiply these together for
all
.
Now, for each matrix with nonzero multinomial coefficient , let
be the sum of the
-th diagonal in the matrix; then
For example when , we have
The function milnor_multiplication()
takes as input two pairs of
tuples of non-negative integers, and
, which represent
and
. It returns as output a
dictionary whose keys are pairs of tuples
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 , then the mod 2 Steenrod algebra is generated by Steenrod
squares
for
(equal to the Milnor basis element
). The Adem relations are as follows: if
,
A monomial is called admissible if
for all
. 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
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 , the Steenrod algebra is generated by the pth
power operations
(the same as
in the
Milnor basis) and the Bockstein operation
(=
in the
Milnor basis). The odd primary Adem relations are as follows: if
,
Also, if ,
The admissible monomials at an odd prime are products of the form
where for all
. 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:
- [Mil] J. W. Milnor, “The Steenrod algebra and its dual”, Ann. of Math. (2) 67 (1958), 150–171.
- [SE] N. E. Steenrod, “Cohomology operations (Lectures by N. E. Steenrod written and revised by D. B. A. Epstein)”. Annals of Mathematics Studies, No. 50, 1962, Princeton University Press.
-
sage.algebras.steenrod.steenrod_algebra_mult.
adem
(a, b, c=0, p=2, generic=None)¶ The mod
Adem relations
INPUT:
,
,
(optional) - nonnegative integers, corresponding to either
or (if
present) to
- positive prime number (optional, default 2)
- whether to use the generic Steenrod algebra, (default: depends on prime)
OUTPUT:
a dictionary representing the mod
Adem relations applied to
or (if
present) to
.
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
Adem relations for the mod
Steenrod algebra are as follows: if
, then if
,
If
is odd, then if
,
Also for
odd, if
,
EXAMPLES:
If two arguments (
and
) are given, then computations are done mod 2. If
, then the dictionary {(a,b): 1} is returned. Otherwise, the right side of the mod 2 Adem relation for
is returned. For example, since
, 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
is given and is odd, then with two inputs
and
, the Adem relation for
is computed. With three inputs
,
,
, the Adem relation for
is computed. In either case, the keys in the output are all tuples of odd length, with
(i_1, i_2, ..., i_m)
representingFor 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}
-
sage.algebras.steenrod.steenrod_algebra_mult.
binomial_mod2
(n, k)¶ The binomial coefficient
, computed mod 2.
INPUT:
,
- integers
OUTPUT:
choose
, 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
, computed mod
.
INPUT:
,
- integers
- prime number
OUTPUT:
choose
, mod
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
(mono, 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
, the sequence (and hence the corresponding monomial)
is admissible if
for all
.
When
is odd, the sequence
is admissible if
for all
.
INPUT:
mono
- a tuple of non-negative integers- prime number, optional (default 2)
- 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
is odd, each tuple must have an odd length: it should be of the form
where each
is either 0 or 1 and each
is a positive integer: this corresponds to the admissible monomial
ALGORITHM:
Given
, apply the Adem relations to the first pair (or triple when
is odd) where the sequence is inadmissible, and then apply this function recursively to each of the resulting tuples
, 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
-
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
and
, computes their multinomial coefficients, and for each matrix whose coefficient is 1, add
to the output, where
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.
-
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
and
.
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.
-
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
, this computes the multinomial coefficient
, mod 2. The method is roughly this: expand each
in binary. If there is a 1 in the same digit for any
and
with
, 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
, this computes the multinomial coefficient
, mod
. The method is this: expand each
in base
:
. Do the same for the sum of the
‘s, which we call
:
. Then the multinomial coefficient is congruent, mod
, to the product of the multinomial coefficients
.
Furthermore, any multinomial coefficient
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