steenrod_algebra.py

r"""
The Steenrod algebra

AUTHORS:

- John H. Palmieri (2008-07-30): version 0.9: Initial implementation.
- John H. Palmieri (2010-06-30): version 1.0: Implemented sub-Hopf
  algebras and profile functions; direct multiplication of admissible
  sequences (rather than conversion to the Milnor basis); implemented
  the Steenrod algebra using CombinatorialFreeModule; improved the
  test suite.

This module defines the mod `p` Steenrod algebra `\mathcal{A}_p`, some
of its properties, and ways to define elements of it.

From a topological point of view, `\mathcal{A}_p` is the algebra of
stable cohomology operations on mod `p` cohomology; thus for any
topological space `X`, its mod `p` cohomology algebra
`H^*(X,\mathbf{F}_p)` is a module over `\mathcal{A}_p`.

From an algebraic point of view, `\mathcal{A}_p` is an
`\mathbf{F}_p`-algebra; when `p=2`, it is generated by elements
`\text{Sq}^i` for `i\geq 0` (the *Steenrod squares*), and when `p` is
odd, it is generated by elements `\mathcal{P}^i` for `i \geq 0` (the
*Steenrod reduced pth powers*) along with an element `\beta` (the *mod
p Bockstein*). The Steenrod algebra is graded: `\text{Sq}^i` is in
degree `i` for each `i`, `\beta` is in degree 1, and `\mathcal{P}^i`
is in degree `2(p-1)i`.

The unit element is `\text{Sq}^0` when `p=2` and
`\mathcal{P}^0` when `p` is odd. The generating
elements also satisfy the *Adem relations*. At the prime 2, these
have the form

.. math::

     \text{Sq}^a \text{Sq}^b   = \sum_{c=0}^{[a/2]} \binom{b-c-1}{a-2c} \text{Sq}^{a+b-c} \text{Sq}^c. 

At odd primes, they are a bit more complicated; see Steenrod and
Epstein [SE] or :mod:`sage.algebras.steenrod.steenrod_algebra_bases`
for full details. These relations lead to the existence of the
*Serre-Cartan* basis for `\mathcal{A}_p`.

The mod `p` Steenrod algebra has the structure of a Hopf
algebra, and Milnor [Mil] has a beautiful description of the dual,
leading to a construction of the *Milnor basis* for
`\mathcal{A}_p`. In this module, elements in the Steenrod
algebra are represented, by default, using the Milnor basis.

.. rubric:: Bases for the Steenrod algebra

There are a handful of other bases studied in the literature; the
paper by Monks is a good reference.  Here is a quick summary:

- The *Milnor basis*. When `p=2`, the Milnor basis consists of symbols
  of the form `\text{Sq}(m_1, m_2, ..., m_t)`, where each `m_i` is a
  non-negative integer and if `t>1`, then the last entry `m_t > 0`.
  When `p` is odd, the Milnor basis consists of symbols of the form
  `Q_{e_1} Q_{e_2} ... \mathcal{P}(m_1, m_2, ..., m_t)`, where `0 \leq
  e_1 < e_2 < ...`, each `m_i` is a non-negative integer, and if
  `t>1`, then the last entry `m_t > 0`.

  When `p=2`, it can be convenient to use the notation
  `\mathcal{P}(-)` to mean `\text{Sq}(-)`, so that there is consistent
  notation for all primes.

- The *Serre-Cartan basis*.  This basis consists of 'admissible
  monomials' in the Steenrod operations. Thus at the prime 2, it
  consists of monomials `\text{Sq}^{m_1} \text{Sq}^{m_2}
  ... \text{Sq}^{m_t}` with `m_i \geq 2m_{i+1}` for each `i`.  At odd
  primes, this basis consists of monomials `\beta^{\epsilon_0}
  \mathcal{P}^{s_1} \beta^{\epsilon_1} \mathcal{P}^{s_2} ...
  \mathcal{P}^{s_k} \beta^{\epsilon_k}` with each `\epsilon_i` either
  0 or 1, `s_i \geq p s_{i+1} + \epsilon_i`, and `s_k \geq 1`.
    
Most of the rest of the bases are only defined when `p=2`.  The only
exceptions are the `P^s_t`-bases and the commutator bases, which are
defined at all primes.
    
- *Wood's Y basis*.  For pairs of non-negative integers `(m,k)`, let
  `w(m,k) = \text{Sq}^{2^m (2^{k+1}-1)}`. Wood's `Y` basis consists of
  monomials `w(m_0,k_0) ... w(m_t, k_t)` with `(m_i,k_i) >
  (m_{i+1},k_{i+1})`, in left lex order.

- *Wood's Z basis*. For pairs of non-negative integers `(m,k)`, let
  `w(m,k) = \text{Sq}^{2^m (2^{k+1}-1)}`. Wood's `Z` basis consists of
  monomials `w(m_0,k_0) ... w(m_t, k_t)` with `(m_i+k_i,m_i) >
  (m_{i+1}+k_{i+1},m_{i+1})`, in left lex order.
    
- *Wall's basis*. For any pair of integers `(m,k)` with `m \geq k \geq
  0`, let `Q^m_k = \text{Sq}^{2^k} \text{Sq}^{2^{k+1}}
  ... \text{Sq}^{2^m}`.  The elements of Wall's basis are monomials
  `Q^{m_0}_{k_0} ... Q^{m_t}_{k_t}` with `(m_i, k_i) > (m_{i+1},
  k_{i+1})`, ordered left lexicographically.
    
  (Note that `Q^m_k` is the reverse of the element `X^m_k` used in
  defining Arnon's A basis.)
    
- *Arnon's A basis*. For any pair of integers `(m,k)` with `m \geq k
  \geq 0`, let `X^m_k = \text{Sq}^{2^m} \text{Sq}^{2^{m-1}}
  ... \text{Sq}^{2^k}`.  The elements of Arnon's A basis are monomials
  `X^{m_0}_{k_0} ... X^{m_t}_{k_t}` with `(m_i, k_i) < (m_{i+1},
  k_{i+1})`, ordered left lexicographically.

  (Note that `X^m_k` is the reverse of the element `Q^m_k` used in
  defining Wall's basis.)

- *Arnon's C basis*. The elements of Arnon's C basis are monomials of
  the form `\text{Sq}^{t_1} ... \text{Sq}^{t_m}` where for each `i`,
  we have `t_i \leq 2t_{i+1}` and `2^i | t_{m-i}`.

- `P^s_t` *bases*.  Let `p=2`.  For integers `s \geq 0` and `t > 0`,
  the element `P^s_t` is the Milnor basis element `\mathcal{P}(0, ...,
  0, p^s, 0, ...)`, with the nonzero entry in position `t`. To obtain
  a `P^s_t`-basis, for each set `\{P^{s_1}_{t_1}, ...,
  P^{s_k}_{t_k}\}` of (distinct) `P^s_t`'s, one chooses an ordering
  and forms the monomials

  .. math::

      (P^{s_1}_{t_1})^{i_1} ... (P^{s_k}_{t_k})^{i_k}

  for all exponents `i_j` with `0 < i_j < p`.  When `p=2`, the set of
  all such monomials then forms a basis, and when `p` is odd, if one
  multiplies each such monomial on the left by products of the form
  `Q_{e_1} Q_{e_2} ...` with `0 \leq e_1 < e_2 < ...`, one obtains a
  basis.

  Thus one gets a basis by choosing an ordering on each set of
  `P^s_t`'s.  There are infinitely many orderings possible, and we
  have implemented four of them:

  - 'rlex': right lexicographic ordering

  - 'llex': left lexicographic ordering

  - 'deg': ordered by degree, which is the same as left lexicographic
    ordering on the pair `(s+t,t)`

  - 'revz': left lexicographic ordering on the pair `(s+t,s)`, which
    is the reverse of the ordering used (on elements in the same
    degrees as the `P^s_t`'s) in Wood's Z basis: 'revz' stands for
    'reversed Z'. This is the default: 'pst' is the same as
    'pst_revz'.

- *Commutator bases*.  Let `c_{i,1} = \mathcal{P}(p^i)`, let `c_{i,2}
  = [c_{i+1,1}, c_{i,1}]`, and inductively define `c_{i,k} =
  [c_{i+k-1,1}, c_{i,k-1}]`. Thus `c_{i,k}` is a `k`-fold iterated
  commutator of the elements `\mathcal{P}(p^i)`, ...,
  `\mathcal{P}(p^{i+k-1})`. Note that `\dim c_{i,k} = \dim P^i_k`.

  Commutator bases are obtained in much the same way as `P^s_t`-bases:
  for each set `\{c_{s_1,t_1}, ..., c_{s_k,t_k}\}` of (distinct)
  `c_{s,t}`'s, one chooses an ordering and forms the resulting
  monomials

  .. math::

      c_{s_1, t_1}^{i_1} ... c_{s_k,t_k}^{i_k}

  for all exponents `i_j` with `0 < i_j < p`.  When `p` is odd, one
  also needs to left-multiply by products of the `Q_i`'s.  As for
  `P^s_t`-bases, every ordering on each set of iterated commutators
  determines a basis, and the same four orderings have been defined
  for these bases as for the `P^s_t` bases: 'rlex', 'llex', 'deg',
  'revz'.

.. rubric:: Sub-Hopf algebras of the Steenrod algebra

The sub-Hopf algebras of the Steenrod algebra have been
classified.  Milnor proved that at the prime 2, the dual of the
Steenrod algebra `A_*` is isomorphic to a polynomial algebra

.. math::

   A_* \cong \GF{2} [\xi_1, \xi_2, \xi_3, ...].

The Milnor basis is dual to the monomial basis.  Furthermore, any sub-Hopf
algebra corresponds to a quotient of this of the form

.. math::

   A_* /(\xi_1^{2^{e_1}}, \xi_2^{2^{e_2}}, \xi_3^{2^{e_3}}, ...).

The list of exponents `(e_1, e_2, ...)` may be considered a function
`e` from the positive integers to the extended non-negative integers
(the non-negative integers and `\infty`); this is called the *profile
function* for the sub-Hopf algebra.  The profile function must satisfy
the condition

- `e(r) \geq \min( e(r-i) - i, e(i))` for all `0 < i < r`.

At odd primes, the situation is similar: the dual is isomorphic to the
tensor product of a polynomial algebra and an exterior algebra,

.. math::

   A_* = \GF{p} [\xi_1, \xi_2, \xi_3, ...] \otimes \Lambda (\tau_0, \tau_1, ...),

and any sub-Hopf algebra corresponds to a quotient of this of the form

.. math::

   A_* / (\xi_1^{p^{e_1}}, \xi_2^{p^{e_2}}, ...; \tau_0^{k_0}, \tau_1^{k_1}, ...).

Here the profile function has two pieces, `e` as at the prime 2, and
`k`, which maps the non-negative integers to the set `\{1, 2\}`.
These must satisfy the following conditions:

- `e(r) \geq \min( e(r-i) - i, e(i))` for all `0 < i < r`.

- if `k(i+j) = 1`, then either `e(i) \leq j` or `k(j) = 1` for all `i
  \geq 1`, `j \geq 0`.

(See Adams-Margolis, for example, for these results on profile
functions.)

This module allows one to construct the Steenrod algebra or any of its
sub-Hopf algebras, at any prime.  When defining a sub-Hopf algebra,
you must work with the Milnor basis or a `P^s_t`-basis.

.. rubric:: Elements of the Steenrod algebra

Basic arithmetic, `p=2`. To construct an element of the mod 2 Steenrod
algebra, use the function ``Sq``::

    sage: a = Sq(1,2)
    sage: b = Sq(4,1)
    sage: z = a + b
    sage: z
    Sq(1,2) + Sq(4,1)
    sage: Sq(4) * Sq(1,2)
    Sq(1,1,1) + Sq(2,3) + Sq(5,2)
    sage: z**2          # non-negative exponents work as they should
    Sq(1,2,1) + Sq(4,1,1)
    sage: z**0
    1

Basic arithmetic, `p>2`. To construct an element of the mod `p`
Steenrod algebra when `p` is odd, you should first define a Steenrod
algebra, using the ``SteenrodAlgebra`` command::

    sage: A3 = SteenrodAlgebra(3)

Having done this, the newly created algebra ``A3`` has methods ``Q``
and ``P`` which construct elements of ``A3``::

    sage: c = A3.Q(1,3,6); c
    Q_1 Q_3 Q_6
    sage: d = A3.P(2,0,1); d
    P(2,0,1)
    sage: c * d
    Q_1 Q_3 Q_6 P(2,0,1)
    sage: e = A3.P(3)
    sage: d * e
    P(5,0,1)
    sage: e * d
    P(1,1,1) + P(5,0,1)
    sage: c * c
    0
    sage: e ** 3
    2 P(1,2)

Note that one can construct an element like ``c`` above in one step,
without first constructing the algebra::

    sage: c = SteenrodAlgebra(3).Q(1,3,6)
    sage: c
    Q_1 Q_3 Q_6

And of course, you can do similar constructions with the mod 2
Steenrod algebra::

    sage: A = SteenrodAlgebra(2); A
    mod 2 Steenrod algebra, milnor basis
    sage: A.Sq(2,3,5)
    Sq(2,3,5)
    sage: A.P(2,3,5)   # when p=2, P = Sq
    Sq(2,3,5)
    sage: A.Q(1,4)     # when p=2, this gives a product of Milnor primitives
    Sq(0,1,0,0,1)

Associated to each element is its prime (the characteristic of the
underlying base field) and its basis (the basis for the Steenrod
algebra in which it lies)::

    sage: a = SteenrodAlgebra(basis='milnor').Sq(1,2,1)
    sage: a.prime()
    2
    sage: a.basis_name()
    'milnor'
    sage: a.degree()
    14

It can be viewed in other bases::

    sage: a.milnor() # same as a
    Sq(1,2,1)
    sage: a.change_basis('adem')
    Sq^9 Sq^4 Sq^1 + Sq^11 Sq^2 Sq^1 + Sq^13 Sq^1
    sage: a.change_basis('adem').change_basis('milnor')
    Sq(1,2,1)

Regardless of the prime, each element has an ``excess``, and if the
element is homogeneous, a ``degree``. The excess of
`\text{Sq}(i_1,i_2,i_3,...)` is `i_1 + i_2 + i_3 + ...`; when `p` is
odd, the excess of `Q_{0}^{e_0} Q_{1}^{e_1} ... \mathcal{P}(r_1, r_2,
...)` is `\sum e_i + 2 \sum r_i`. The excess of a linear combination
of Milnor basis elements is the minimum of the excesses of those basis
elements.

The degree of `\text{Sq}(i_1,i_2,i_3,...)` is `sum (2^n-1) i_n`, and
when `p` is odd, the degree of `Q_{0}^{\epsilon_0} Q_{1}^{\epsilon_1}
... \mathcal{P}(r_1, r_2, ...)` is `\sum \epsilon_i (2p^i - 1) + \sum
r_j (2p^j - 2)`.  The degree of a linear combination of such terms is
only defined if the terms all have the same degree.

Here are some simple examples::

    sage: z = Sq(1,2) + Sq(4,1)
    sage: z.degree()
    7
    sage: (Sq(0,0,1) + Sq(5,3)).degree()
    Traceback (most recent call last):
    ...
    ValueError: Element is not homogeneous.
    sage: Sq(7,2,1).excess()
    10
    sage: z.excess()
    3
    sage: B = SteenrodAlgebra(3)
    sage: x = B.Q(1,4)
    sage: y = B.P(1,2,3)
    sage: x.degree()
    166
    sage: x.excess()
    2
    sage: y.excess()
    12

Elements have a ``weight`` in the May filtration, which (when `p=2`)
is related to the ``height`` function defined by Wall::

    sage: Sq(2,1,5).may_weight()
    9
    sage: Sq(2,1,5).wall_height()
    [2, 3, 2, 1, 1]
    sage: b = Sq(4)*Sq(8) + Sq(8)*Sq(4)
    sage: b.may_weight()
    2
    sage: b.wall_height()
    [0, 0, 1, 1]

Odd primary May weights::

    sage: A5 = SteenrodAlgebra(5)
    sage: a = A5.Q(1,2,4)
    sage: b = A5.P(1,2,1)
    sage: a.may_weight()
    10
    sage: b.may_weight()
    8
    sage: (a * b).may_weight()
    18
    sage: A5.P(0,0,1).may_weight()
    3

Since the Steenrod algebra is a Hopf algebra, every element has a
coproduct and an antipode.

::

    sage: Sq(5).coproduct()
    1 # Sq(5) + Sq(1) # Sq(4) + Sq(2) # Sq(3) + Sq(3) # Sq(2) + Sq(4) # Sq(1) + Sq(5) # 1
    sage: Sq(5).antipode()
    Sq(2,1) + Sq(5)
    sage: d = Sq(0,0,1); d
    Sq(0,0,1)
    sage: d.antipode()
    Sq(0,0,1)
    sage: Sq(4).antipode()
    Sq(1,1) + Sq(4)
    sage: (Sq(4) * Sq(2)).antipode()
    Sq(6)
    sage: SteenrodAlgebra(7).P(3,1).antipode()
    P(3,1)

Applying the antipode twice returns the original element::

    sage: y = Sq(8)*Sq(4)
    sage: y == (y.antipode()).antipode()
    True

Internal representation: you can use any element as an iterator (``for
x in a: ...``), and the method :meth:`monomial_coefficients` returns a
dictionary with keys tuples representing basis elements and with
corresponding value representing the coefficient of that term::

    sage: c = Sq(5).antipode(); c
    Sq(2,1) + Sq(5)
    sage: for mono, coeff in c: print coeff, mono
    1 (5,)
    1 (2, 1)
    sage: c.monomial_coefficients()
    {(5,): 1, (2, 1): 1}
    sage: c.monomials()
    [Sq(2,1), Sq(5)]
    sage: c.support()
    [(2, 1), (5,)]
    sage: Adem = SteenrodAlgebra(basis='adem')
    sage: (Adem.Sq(10) + Adem.Sq(9) * Adem.Sq(1)).monomials()
    [Sq^9 Sq^1, Sq^10]

    sage: A7 = SteenrodAlgebra(p=7)
    sage: a = A7.P(1) * A7.P(1); a
    2 P(2)
    sage: a.leading_coefficient()
    2
    sage: a.leading_monomial()
    P(2)
    sage: a.leading_term()
    2 P(2)
    sage: a.change_basis('adem').monomial_coefficients()
    {(0, 2, 0): 2}

The tuple in the previous output stands for the element `\beta^0
P^2 \beta^0`, i.e., `P^2`.  Going in the other direction, if you
want to specify a basis element by giving the corresponding tuple,
you can use the :meth:`monomial` method on the algebra::

    sage: SteenrodAlgebra(p=7, basis='adem').monomial((0, 2, 0))
    P^2
    sage: 10 * SteenrodAlgebra(p=7, basis='adem').monomial((0, 2, 0))
    3 P^2

In the following example, elements in Wood's Z basis are certain
products of the elements `w(m,k) = \text{Sq}^{2^m (2^{k+1}-1)}`.
Internally, each `w(m,k)` is represented by the pair `(m,k)`, and
products of them are represented by tuples of such pairs. ::

    sage: A = SteenrodAlgebra(basis='wood_z')
    sage: t = ((2, 0), (0, 0))
    sage: A.monomial(t)
    Sq^4 Sq^1

See the documentation for :func:`SteenrodAlgebra` for more details and
examples.

REFERENCES:

- [AM] J. F. Adams, and H. R. Margolis, "Sub-Hopf-algebras of the
  Steenrod algebra," Proc. Cambridge Philos. Soc. 76 (1974), 45-52.

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

- [Mon] K. G. Monks, "Change of basis, monomial relations, and
  `P^s_t` bases for the Steenrod algebra," J. Pure Appl.
  Algebra 125 (1998), no. 1-3, 235-260.

- [SE] N. E. Steenrod and D. B. A. Epstein, Cohomology operations,
  Ann. of Math. Stud. 50 (Princeton University Press, 1962).
"""

#*****************************************************************************
#  Copyright (C) 2008-2010 John H. Palmieri <[email protected]>
#  Distributed under the terms of the GNU General Public License (GPL)
#*****************************************************************************

from sage.combinat.free_module import CombinatorialFreeModule, \
    CombinatorialFreeModuleElement
from sage.misc.lazy_attribute import lazy_attribute
from sage.categories.all import ModulesWithBasis, tensor, Hom

######################################################
# the main class
######################################################

class SteenrodAlgebra_generic(CombinatorialFreeModule):
    r"""
    The mod `p` Steenrod algebra.
    
    Users should not call this, but use the function
    :func:`SteenrodAlgebra` instead. See that function for
    extensive documentation.
    
    EXAMPLES::
    
        sage: sage.algebras.steenrod.steenrod_algebra.SteenrodAlgebra_generic()
        mod 2 Steenrod algebra, milnor basis
        sage: sage.algebras.steenrod.steenrod_algebra.SteenrodAlgebra_generic(5)
        mod 5 Steenrod algebra, milnor basis
        sage: sage.algebras.steenrod.steenrod_algebra.SteenrodAlgebra_generic(5, 'adem')
        mod 5 Steenrod algebra, serre-cartan basis
    """
    @staticmethod
    def __classcall__(self, p=2, basis='milnor', **kwds):
        """
        This normalizes the basis name and the profile, to make unique
        representation work properly.

        EXAMPLES::

            sage: SteenrodAlgebra(basis='adem') is SteenrodAlgebra(basis='serre-cartan')
            True
            sage: SteenrodAlgebra(profile=[3,2,1,0]) is SteenrodAlgebra(profile=lambda n: max(4-n,0), truncation_type=0)
            True
        """
        from steenrod_algebra_misc import get_basis_name, normalize_profile
        profile = kwds.get('profile', None)
        precision = kwds.get('precision', None)
        truncation_type = kwds.get('truncation_type', 'auto')

        std_basis = get_basis_name(basis, p)
        std_profile, std_type = normalize_profile(profile, precision=precision, truncation_type=truncation_type, p=p)
        return super(SteenrodAlgebra_generic, self).__classcall__(self, p=p, basis=std_basis, profile=std_profile, truncation_type=std_type)

    def __init__(self, p=2, basis='milnor', **kwds):
        r"""
        INPUT:

        - ``p`` - positive prime integer (optional, default 2)
        - ``basis`` - string (optional, default = 'milnor')
        - ``profile`` - profile function (optional, default ``None``)
        - ``truncation_type`` - (optional, default 'auto')
        - ``precision`` - (optional, default ``None``)

        OUTPUT: mod `p` Steenrod algebra with basis, or a sub-Hopf
        algebra of the mod `p` Steenrod algebra defined by the given
        profile function.

        See :func:`SteenrodAlgebra` for full documentation.

        EXAMPLES::

            sage: SteenrodAlgebra()   # 2 is the default prime
            mod 2 Steenrod algebra, milnor basis
            sage: SteenrodAlgebra(5)
            mod 5 Steenrod algebra, milnor basis
            sage: SteenrodAlgebra(2, 'milnor').Sq(0,1)
            Sq(0,1)
            sage: SteenrodAlgebra(2, 'adem').Sq(0,1)
            Sq^2 Sq^1 + Sq^3

        TESTS::

            sage: TestSuite(SteenrodAlgebra()).run()
            sage: TestSuite(SteenrodAlgebra(profile=[4,3,2,2,1])).run()
            sage: TestSuite(SteenrodAlgebra(basis='adem')).run()
            sage: TestSuite(SteenrodAlgebra(basis='wall')).run()
            sage: TestSuite(SteenrodAlgebra(basis='arnonc')).run() # long time
            sage: TestSuite(SteenrodAlgebra(basis='woody')).run() # long time
            sage: A3 = SteenrodAlgebra(3)
            sage: A3.category()
            Category of graded hopf algebras with basis over Finite Field of size 3
            sage: TestSuite(A3).run()
            sage: TestSuite(SteenrodAlgebra(basis='adem', p=3)).run()
            sage: TestSuite(SteenrodAlgebra(basis='pst_llex', p=7)).run() # long time
            sage: TestSuite(SteenrodAlgebra(basis='comm_deg', p=5)).run() # long time
        """
        from sage.rings.arith import is_prime
        from sage.categories.graded_hopf_algebras_with_basis import GradedHopfAlgebrasWithBasis
        from sage.rings.infinity import Infinity
        from sage.sets.family import Family
        from sage.sets.non_negative_integers import NonNegativeIntegers
        from functools import partial
        from steenrod_algebra_bases import steenrod_algebra_basis
        from sage.rings.all import GF
        profile = kwds.get('profile', None)
        truncation_type = kwds.get('truncation_type', 'auto')

        if not is_prime(p):
            raise ValueError("%s is not prime." % p)
        self._prime = p
        base_ring = GF(p)
        self._profile = profile
        self._truncation_type = truncation_type
        NN = NonNegativeIntegers()
        if ((p==2 and ((len(profile) > 0 and profile[0] < Infinity)))
            or (p>2 and profile != ((), ()) and len(profile[0]) > 0
                and profile[0][0] < Infinity)
            or (truncation_type < Infinity)):
            if basis != 'milnor' and basis.find('pst') == -1:
                raise NotImplementedError("For sub-Hopf algebras of the Steenrod algebra, only the Milnor basis and the pst bases are implemented.")
        self._basis_name = basis
        self._basis_fcn = partial(steenrod_algebra_basis,
                                  p=p,
                                  basis=basis,
                                  profile=profile,
                                  truncation_type=truncation_type)
        # name the basis function so different Steenrod algebras have
        # different basis functions... (see __eq__ for LazyFamily?)
        self._basis_fcn.func_name = "basis_%s_%s_%s_%s" % (p, basis, profile, truncation_type)
        CombinatorialFreeModule.__init__(self,
                                         base_ring,
                                         Family(NN, self._basis_fcn),
                                         prefix=self._basis_name,
                                         element_class=self.Element,
                                         category = GradedHopfAlgebrasWithBasis(base_ring),
                                         scalar_mult = ' ')

    def prime(self):
        r"""
        The prime associated to self.

        EXAMPLES::

            sage: SteenrodAlgebra(p=2, profile=[1,1]).prime()
            2
            sage: SteenrodAlgebra(p=7).prime()
            7
        """
        return self.base_ring().characteristic()

    def basis_name(self):
        r"""
        The basis name associated to self.

        EXAMPLES::

            sage: SteenrodAlgebra(p=2, profile=[1,1]).basis_name()
            'milnor'
            sage: SteenrodAlgebra(basis='serre-cartan').basis_name()
            'serre-cartan'
            sage: SteenrodAlgebra(basis='adem').basis_name()
            'serre-cartan'
        """
        return self.prefix()

    def _has_nontrivial_profile(self):
        r"""
        True if the profile function for this algebra seems to be that
        for a proper sub-Hopf algebra of the Steenrod algebra.

        EXAMPLES::

            sage: SteenrodAlgebra()._has_nontrivial_profile()
            False
            sage: SteenrodAlgebra(p=3)._has_nontrivial_profile()
            False
            sage: SteenrodAlgebra(profile=[3,2,1])._has_nontrivial_profile()
            True
            sage: SteenrodAlgebra(profile=([1], [2, 2]), p=3)._has_nontrivial_profile()
            True

        Check that a bug in #11832 has been fixed::

            sage: P3 = SteenrodAlgebra(p=3, profile=(lambda n: Infinity, lambda n: 1))
            sage: P3._has_nontrivial_profile()
            True
        """
        from sage.rings.infinity import Infinity
        profile = self._profile
        trunc = self._truncation_type
        if self.prime() == 2:
            return ((len(profile) > 0 and len(profile) > 0
                     and profile[0] < Infinity)
                    or (trunc < Infinity))
        return ((profile != ((), ()) and
                  ((len(profile[0]) > 0 and profile[0][0] < Infinity)
                     or (len(profile[1]) > 0 and min(profile[1]) == 1)))
                or (trunc < Infinity))

    def _repr_(self):
        r"""
        Printed representation of the Steenrod algebra.
        
        EXAMPLES::
        
            sage: SteenrodAlgebra(3)
            mod 3 Steenrod algebra, milnor basis
            sage: SteenrodAlgebra(2, basis='adem')
            mod 2 Steenrod algebra, serre-cartan basis
            sage: B = SteenrodAlgebra(2003)
            sage: B._repr_()
            'mod 2003 Steenrod algebra, milnor basis'

            sage: SteenrodAlgebra(profile=(3,2,1,0))
            sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [3, 2, 1]
            sage: SteenrodAlgebra(profile=lambda n: 4)
            sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [4, 4, 4, ..., 4, 4, +Infinity, +Infinity, +Infinity, ...]
            sage: SteenrodAlgebra(p=5, profile=(lambda n: 4, lambda n: 1))
            sub-Hopf algebra of mod 5 Steenrod algebra, milnor basis, profile function ([4, 4, 4, ..., 4, 4, +Infinity, +Infinity, +Infinity, ...], [1, 1, 1, ..., 1, 1, 2, 2, ...])
        """
        def abridge_list(l):
            """
            String rep for list ``l`` if ``l`` is short enough;
            otherwise print the first few terms and the last few
            terms, with an ellipsis in between.
            """
            if len(l) < 8:
                l_str = str(l)
            else:
                l_str = str(l[:3]).rstrip("]") + ", ..., " + str(l[-2:]).lstrip("[")
            return l_str

        from sage.rings.infinity import Infinity
        profile = self._profile
        trunc = self._truncation_type
        p = self.prime()
        if self._has_nontrivial_profile():
            if p == 2:
                pro_str = abridge_list(list(profile))
                if trunc != 0:
                    pro_str = pro_str.rstrip("]") + ", " + str([Infinity] * 3).strip("[]") + ", ...]"
            else:
                e_str = abridge_list(list(profile[0]))
                k_str = abridge_list(list(profile[1]))
                if trunc != 0:
                    e_str = e_str.rstrip("]") + ", " + str([Infinity] * 3).strip("[]") + ", ...]"
                    k_str = k_str.rstrip("]") + ", " + str([2] * 2).strip("[]") + ", ...]"
                pro_str = "(%s, %s)" % (e_str, k_str)
            return "sub-Hopf algebra of mod %d Steenrod algebra, %s basis, profile function %s" % (self.prime(), self._basis_name, pro_str)
        return "mod %d Steenrod algebra, %s basis" % (self.prime(), self._basis_name)

    def _latex_(self):
        r"""
        LaTeX representation of the Steenrod algebra.
        
        EXAMPLES::
        
            sage: C = SteenrodAlgebra(3)
            sage: C
            mod 3 Steenrod algebra, milnor basis
            sage: C._latex_()
            '\\mathcal{A}_{3}'
        """
        return "\\mathcal{A}_{%s}" % self.prime()

    def _repr_term(self, t):
        r"""
        String representation of the monomial specified by the tuple ``t``.

        INPUT:

        - ``t`` - tuple, representing basis element in the current basis.

        OUTPUT: string

        This is tested in many places: any place elements are printed
        is essentially a doctest for this method.  Also, each basis
        has its own method for printing monomials, and those are
        doctested individually.  We give a few doctests here, in
        addition.

        EXAMPLES::

            sage: SteenrodAlgebra()._repr_term((3,2))
            'Sq(3,2)'
            sage: SteenrodAlgebra(p=7)._repr_term(((0,2), (3,2)))
            'Q_0 Q_2 P(3,2)'
            sage: SteenrodAlgebra(basis='adem')._repr_term((14,2))
            'Sq^14 Sq^2'
            sage: SteenrodAlgebra(basis='adem', p=3)._repr_term((1,3,0))
            'beta P^3'
            sage: SteenrodAlgebra(basis='pst')._repr_term(((0,2), (1,3)))
            'P^0_2 P^1_3'
            sage: SteenrodAlgebra(basis='arnon_a')._repr_term(((0,2), (1,3)))
            'X^0_2 X^1_3'

            sage: A7 = SteenrodAlgebra(7)
            sage: x = A7.Q(0,3) * A7.P(2,2)
            sage: x._repr_()
            'Q_0 Q_3 P(2,2)'
            sage: x
            Q_0 Q_3 P(2,2)
            sage: a = SteenrodAlgebra().Sq(0,0,2)
            sage: a
            Sq(0,0,2)
            sage: A2_adem = SteenrodAlgebra(2,'admissible')
            sage: A2_adem(a)
            Sq^8 Sq^4 Sq^2 + Sq^9 Sq^4 Sq^1 + Sq^10 Sq^3 Sq^1 +
            Sq^10 Sq^4 + Sq^11 Sq^2 Sq^1 + Sq^12 Sq^2 + Sq^13 Sq^1
            + Sq^14
            sage: SteenrodAlgebra(2, 'woodz')(a)
            Sq^6 Sq^7 Sq^1 + Sq^14 + Sq^4 Sq^7 Sq^3 + Sq^4 Sq^7
            Sq^2 Sq^1 + Sq^12 Sq^2 + Sq^8 Sq^6 + Sq^8 Sq^4 Sq^2
            sage: SteenrodAlgebra(2, 'arnonc')(a)
            Sq^4 Sq^2 Sq^8 + Sq^4 Sq^4 Sq^6 + Sq^4 Sq^6 Sq^4 +
            Sq^6 Sq^8 + Sq^8 Sq^4 Sq^2 + Sq^8 Sq^6
            sage: SteenrodAlgebra(2, 'pst_llex')(a)
            P^1_3
            sage: SteenrodAlgebra(2, 'comm_revz')(a)
            c_0,1 c_1,1 c_0,3 c_2,1 + c_0,2 c_0,3 c_2,1 + c_1,3
        """
        from steenrod_algebra_misc import milnor_mono_to_string, \
            serre_cartan_mono_to_string, wood_mono_to_string, \
            wall_mono_to_string, wall_long_mono_to_string, \
            arnonA_mono_to_string, arnonA_long_mono_to_string, \
            serre_cartan_mono_to_string, pst_mono_to_string, \
            comm_long_mono_to_string, comm_mono_to_string
        p = self.prime()
        basis = self.basis_name()
        if basis == 'milnor':
            s = milnor_mono_to_string(t, p=p)
        elif basis == 'serre-cartan':
            s = serre_cartan_mono_to_string(t, p=p)
        elif basis.find('wood') >= 0:
            s = wood_mono_to_string(t)
        elif basis == 'wall':
            s = wall_mono_to_string(t)
        elif basis == 'wall_long':
            s = wall_long_mono_to_string(t)
        elif basis == 'arnona':
            s = arnonA_mono_to_string(t)
        elif basis == 'arnona_long':
            s = arnonA_long_mono_to_string(t)
        elif basis == 'arnonc':
            s = serre_cartan_mono_to_string(t)
        elif basis.find('pst') >= 0:
            s = pst_mono_to_string(t, p=p)
        elif basis.find('comm') >= 0 and basis.find('long') >= 0:
            s = comm_long_mono_to_string(t, p=p)
        elif basis.find('comm') >= 0:
            s = comm_mono_to_string(t, p=p)
        s = s.translate(None, "{}")
        return s

    def _latex_term(self, t):
        """
        LaTeX representation of the monomial specified by the tuple ``t``.

        INPUT:

        - ``t`` - tuple, representing basis element in the current basis.

        OUTPUT: string

        The string depends on the basis over which the element is defined.

        EXAMPLES::

            sage: A7 = SteenrodAlgebra(7)
            sage: A7._latex_term(((0, 3), (2,2)))
            'Q_{0} Q_{3} \\mathcal{P}(2,2)'
            sage: x = A7.Q(0,3) * A7.P(2,2)
            sage: x._latex_()  # indirect doctest
            'Q_{0} Q_{3} \\mathcal{P}(2,2)'
            sage: latex(x)
            Q_{0} Q_{3} \mathcal{P}(2,2)
            sage: b = Sq(0,2)
            sage: b.change_basis('adem')._latex_()
            '\\text{Sq}^{4} \\text{Sq}^{2} + \\text{Sq}^{5} \\text{Sq}^{1} +
            \\text{Sq}^{6}'
            sage: b.change_basis('woody')._latex_()
            '\\text{Sq}^{2} \\text{Sq}^{3} \\text{Sq}^{1} + \\text{Sq}^{6} +
            \\text{Sq}^{4} \\text{Sq}^{2}'
            sage: SteenrodAlgebra(2, 'arnona')(b)._latex_()
            'X^{1}_{1} X^{2}_{2}  + X^{2}_{1}'
            sage: SteenrodAlgebra(p=3, basis='serre-cartan').Q(0)._latex_()
            '\\beta'
            sage: latex(Sq(2).change_basis('adem').coproduct())
            1 \otimes \text{Sq}^{2} + \text{Sq}^{1} \otimes \text{Sq}^{1} + \text{Sq}^{2} \otimes 1
        """
        import re
        s = self._repr_term(t)
        s = re.sub(r"\^([0-9]*)", r"^{\1}", s)
        s = re.sub("_([0-9,]*)", r"_{\1}", s)
        s = s.replace("Sq", "\\text{Sq}")
        s = s.replace("P", "\\mathcal{P}")
        s = s.replace("beta", "\\beta")
        return s

    def __eq__(self, right):
        r"""
        Two Steenrod algebras are equal iff their associated primes,
        bases, and profile functions (if present) are equal.  Because
        this class inherits from :class:`UniqueRepresentation`, this
        means that they are equal if and only they are identical: ``A
        == B`` is True if and only if ``A is B`` is True.

        EXAMPLES::

            sage: A = SteenrodAlgebra(2)
            sage: B = SteenrodAlgebra(2, 'adem')
            sage: A == B
            False
            sage: C = SteenrodAlgebra(17)
            sage: A == C
            False

            sage: A1 = SteenrodAlgebra(2, profile=[2,1])
            sage: A1 == A
            False
            sage: A1 == SteenrodAlgebra(2, profile=[2,1,0])
            True
            sage: A1 == SteenrodAlgebra(2, profile=[2,1], basis='pst')
            False
        """
        return self is right

    def __ne__(self, right):
        r"""
        The negation of the method ``__eq__``.

        EXAMPLES::

            sage: SteenrodAlgebra(p=2) != SteenrodAlgebra(p=2, profile=[2,1])
            True
        """
        return not self.__eq__(right)

    def profile(self, i, component=0):
        r"""
        Profile function for this algebra.

        INPUT:

        - `i` - integer
        - ``component`` - either 0 or 1, optional (default 0)

        OUTPUT: integer or `\infty`

        See the documentation for
        :mod:`sage.algebras.steenrod.steenrod_algebra` and
        :func:`SteenrodAlgebra` for information on profile functions.

        This applies the profile function to the integer `i`.  Thus
        when `p=2`, `i` must be a positive integer.  When `p` is odd,
        there are two profile functions, `e` and `k` (in the notation
        of the aforementioned documentation), corresponding,
        respectively to ``component=0`` and ``component=1``.  So when
        `p` is odd and ``component`` is 0, `i` must be positive, while
        when ``component`` is 1, `i` must be non-negative.

        EXAMPLES::

            sage: SteenrodAlgebra().profile(3)
            +Infinity
            sage: SteenrodAlgebra(profile=[3,2,1]).profile(1)
            3
            sage: SteenrodAlgebra(profile=[3,2,1]).profile(2)
            2

        When the profile is specified by a list, the default behavior
        is to return zero values outside the range of the list.  This
        can be overridden if the algebra is created with an infinite
        ``truncation_type``::

            sage: SteenrodAlgebra(profile=[3,2,1]).profile(9)
            0
            sage: SteenrodAlgebra(profile=[3,2,1], truncation_type=Infinity).profile(9)
            +Infinity

            sage: B = SteenrodAlgebra(p=3, profile=(lambda n: n, lambda n: 1))
            sage: B.profile(3)
            3
            sage: B.profile(3, component=1)
            1
        """
        # determine the tuple t to use
        p = self.prime()
        if p == 2:
            t = self._profile
        elif component == 0:
            t = self._profile[0]
        else:
            t = self._profile[1]
        # case 1: exponents of the xi's
        if p == 2 or component == 0:
            if i <= 0:
                return 0
            try:
                return t[i-1]
            except IndexError:
                return self._truncation_type
        else:
            # case 2: exponents of the tau's
            if i < 0:
                return 1
            try:
                return t[i]
            except IndexError:
                if self._truncation_type > 0:
                    return 2
                else:
                    return 1

    def homogeneous_component(self, n):
        """
        Return the nth homogeneous piece of the Steenrod algebra.

        INPUT:

        - `n` - integer

        OUTPUT: a vector space spanned by the basis for this algebra
        in dimension `n`

        EXAMPLES::

            sage: A = SteenrodAlgebra()
            sage: A.homogeneous_component(4)
            Vector space spanned by (Sq(1,1), Sq(4)) over Finite Field of size 2
            sage: SteenrodAlgebra(profile=[2,1,0]).homogeneous_component(4)
            Vector space spanned by (Sq(1,1),) over Finite Field of size 2

        The notation A[n] may also be used::

            sage: A[5]
            Vector space spanned by (Sq(2,1), Sq(5)) over Finite Field of size 2
            sage: SteenrodAlgebra(basis='wall')[4]
            Vector space spanned by (Q^1_0 Q^0_0, Q^2_2) over Finite Field of size 2
            sage: SteenrodAlgebra(p=5)[17]
            Vector space spanned by (Q_1 P(1), Q_0 P(2)) over Finite Field of size 5

        Note that A[n] is just a vector space, not a Hopf algebra, so
        its elements don't have products, coproducts, or antipodes
        defined on them.  If you want to use operations like this on
        elements of some A[n], then convert them back to elements of A::

            sage: A[5].basis()
            Finite family {(5,): milnor[(5,)], (2, 1): milnor[(2, 1)]}
            sage: a = list(A[5].basis())[1]
            sage: a  # not in A, doesn't print like an element of A
            milnor[(5,)]
            sage: A(a) # in A
            Sq(5)
            sage: A(a) * A(a)
            Sq(7,1)
            sage: a * A(a) # only need to convert one factor
            Sq(7,1)
            sage: a.antipode() # not defined
            Traceback (most recent call last):
            ...
            AttributeError: 'CombinatorialFreeModule_with_category.element_class' object has no attribute 'antipode'
            sage: A(a).antipode() # convert to elt of A, then compute antipode
            Sq(2,1) + Sq(5)

            sage: G = SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]], basis='pst')

        TESTS:

        The following sort of thing is also tested by the function
        :func:`steenrod_basis_error_check
        <sage.algebras.steenrod.steenrod_algebra_bases.steenrod_basis_error_check>`::

            sage: H = SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]])
            sage: G = SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]], basis='pst')
            sage: max([H[n].dimension() - G[n].dimension() for n in range(100)])
            0
        """
        from sage.rings.all import GF
        basis = self._basis_fcn(n)
        M = CombinatorialFreeModule(GF(self.prime()), basis,
                                       element_class=self.Element,
                                       prefix=self._basis_name)
        M._name = "Vector space spanned by %s"%(tuple([self.monomial(a) for a in basis]),)
        return M

    __getitem__ = homogeneous_component

    def one_basis(self):
        """
        The index of the element 1 in the basis for the Steenrod algebra.

        EXAMPLES::

            sage: SteenrodAlgebra(p=2).one_basis()
            ()
            sage: SteenrodAlgebra(p=7).one_basis()
            ((), ())
        """
        p = self.prime()
        basis = self.basis_name()
        if basis == 'serre-cartan' or basis == 'arnonc':
            return (0,)
        if p == 2:
            return ()
        return ((), ())

    def product_on_basis(self, t1, t2):
        """
        The product of two basis elements of this algebra

        INPUT:

        - ``t1``, ``t2`` -- tuples, the indices of two basis elements of self

        OUTPUT: the product of the two corresponding basis elements,
        as an element of self

        ALGORITHM: If the two elements are represented in the Milnor
        basis, use Milnor multiplication as implemented in
        :mod:`sage.algebras.steenrod.steenrod_algebra_mult`.  If the two
        elements are represented in the Serre-Cartan basis, then
        multiply them using Adem relations (also implemented in
        :mod:`sage.algebras.steenrod.steenrod_algebra_mult`).  This
        provides a good way of checking work -- multiply Milnor
        elements, then convert them to Adem elements and multiply
        those, and see if the answers correspond.

        If the two elements are represented in some other basis, then
        convert them both to the Milnor basis and multiply.

        EXAMPLES::

            sage: Milnor = SteenrodAlgebra()
            sage: Milnor.product_on_basis((2,), (2,))
            Sq(1,1)
            sage: Adem = SteenrodAlgebra(basis='adem')
            sage: Adem.Sq(2) * Adem.Sq(2) # indirect doctest
            Sq^3 Sq^1

        When multiplying elements from different bases, the left-hand
        factor determines the form of the output::

            sage: Adem.Sq(2) * Milnor.Sq(2)
            Sq^3 Sq^1
            sage: Milnor.Sq(2) * Adem.Sq(2)
            Sq(1,1)

        TESTS::

            sage: all([Adem(Milnor.Sq(n) ** 3)._repr_() == (Adem.Sq(n) ** 3)._repr_() for n in range(10)])
            True
            sage: Wall = SteenrodAlgebra(basis='wall')
            sage: Wall(Adem.Sq(4,4) * Milnor.Sq(4)) == Adem(Wall.Sq(4,4) * Milnor.Sq(4))
            True

            sage: A3 = SteenrodAlgebra(p=3, basis='adem')
            sage: M3 = SteenrodAlgebra(p=3, basis='milnor')
            sage: all([A3(M3.P(n) * M3.Q(0) * M3.P(n))._repr_() == (A3.P(n) * A3.Q(0) * A3.P(n))._repr_() for n in range(5)])
            True
        """
        p = self.prime()
        basis = self.basis_name()
        if basis == 'milnor':
            if p == 2:
                from steenrod_algebra_mult import milnor_multiplication
                d = milnor_multiplication(t1, t2)
            else:
                from steenrod_algebra_mult import milnor_multiplication_odd
                d = milnor_multiplication_odd(t1, t2, p)
            return self._from_dict(d, coerce=True)
        elif basis == 'serre-cartan':
            from steenrod_algebra_mult import make_mono_admissible
            if p > 2:
                # make sure output has an odd number of terms.  if both t1
                # and t2 have an odd number, concatenate them, adding the
                # middle term...
                # 
                # if either t1 or t2 has an even number of terms, append a
                # 0.
                if (len(t1) % 2) == 0:
                    t1 = t1 + (0,)
                if (len(t2) % 2) == 0:
                    t2 = t2 + (0,)
                if t1[-1] + t2[0] == 2:
                    return self.zero()
                mono = t1[:-1] + (t1[-1] + t2[0],) + t2[1:]
                d = make_mono_admissible(mono, p)
            else: # p=2
                mono = t1 + t2
                while len(mono) > 1 and mono[-1] == 0:
                    mono = mono[:-1]
                d = make_mono_admissible(mono)
            return self._from_dict(d, coerce=True)
        else:
            x = self({t1: 1})
            y = self({t2: 1})
            A = SteenrodAlgebra(basis='milnor', p=p)
            return self(A(x) * A(y))

    def coproduct_on_basis(self, t, algorithm=None):
        r"""
        The coproduct of a basis element of this algebra

        INPUT:

        - ``t`` -- tuple, the index of a basis element of self

        - ``algorithm`` -- None or a string, either 'milnor' or
          'serre-cartan' (or anything which will be converted to one
          of these by the function :func:`get_basis_name
          <sage.algebras.steenrod.steenrod_algebra_misc.get_basis_name>`.
          If None, default to 'milnor' unless current basis is
          'serre-cartan', in which case use 'serre-cartan'.

        ALGORITHM: The coproduct on a Milnor basis element `P(n_1,
        n_2, ...)` is `\sum P(i_1, i_2, ...) \otimes P(j_1, j_2,
        ...)`, summed over all `i_k + j_k = n_k` for each `k`.  At odd
        primes, each element `Q_n` is primitive: its coproduct is `Q_n
        \otimes 1 + 1 \otimes Q_n`.

        One can deduce a coproduct formula for the Serre-Cartan basis
        from this: the coproduct on each `P^n` is `\sum P^i \otimes
        P^{n-i}` and at odd primes `\beta` is primitive.  Since the
        coproduct is an algebra map, one can then compute the
        coproduct on any Serre-Cartan basis element.

        Which of these methods is used is controlled by whether
        ``algorithm`` is 'milnor' or 'serre-cartan'.

        OUTPUT: the coproduct of the corresponding basis element,
        as an element of self tensor self.

        EXAMPLES::

            sage: A = SteenrodAlgebra()
            sage: A.coproduct_on_basis((3,))
            1 # Sq(3) + Sq(1) # Sq(2) + Sq(2) # Sq(1) + Sq(3) # 1

        TESTS::

            sage: all([A.coproduct_on_basis((n,1), algorithm='milnor') == A.coproduct_on_basis((n,1), algorithm='adem') for n in range(9)]) # long time
            True
            sage: A7 = SteenrodAlgebra(p=7, basis='adem')
            sage: all([A7.coproduct_on_basis((0,n,1), algorithm='milnor') == A7.coproduct_on_basis((0,n,1), algorithm='adem') for n in range(9)]) # long time
            True
        """
        def coprod_list(t):
            """
            if t = (n0, n1, ...), then return list of terms (i0, i1,
            ...) where ik <= nk for each k.  From each such term, can
            recover the second factor in the coproduct.
            """
            if len(t) == 0:
                return [()]
            if len(t) == 1:
                return [[a] for a in range(t[0] + 1)]
            ans = []
            for i in range(t[0] + 1):
                ans.extend([[i] + x for x in coprod_list(t[1:])])
            return ans

        from steenrod_algebra_misc import get_basis_name
        p = self.prime()
        basis = self.basis_name()
        if algorithm is None:
            if basis == 'serre-cartan':
                algorithm = 'serre-cartan'
            else:
                algorithm = 'milnor'
        else:
            algorithm = get_basis_name(algorithm, p)
        if basis == algorithm:
            if basis == 'milnor':
                if p == 2:
                    left = coprod_list(t)
                    right = [[x-y for (x,y) in zip(t, m)] for m in left]
                    old = list(left)
                    left = []
                    # trim trailing zeros:
                    for a in old:
                        while len(a) > 0 and a[-1] == 0:
                            a = a[:-1]
                        left.append(tuple(a))
                    old = list(right)
                    right = []
                    for a in old:
                        while len(a) > 0 and a[-1] == 0:
                            a = a[:-1]
                        right.append(tuple(a))
                    tens = dict().fromkeys(zip(left, right), 1)
                    return self.tensor_square()._from_dict(tens)
                else: # p odd
                    from sage.combinat.permutation import Permutation
                    from steenrod_algebra_misc import convert_perm
                    from sage.sets.set import Set
                    left_p = coprod_list(t[1])
                    right_p = [[x-y for (x,y) in zip(t[1], m)] for m in left_p]
                    old = list(left_p)
                    left_p = []
                    # trim trailing zeros:
                    for a in old:
                        while len(a) > 0 and a[-1] == 0:
                            a = a[:-1]
                        left_p.append(tuple(a))
                    old = list(right_p)
                    right_p = []
                    for a in old:
                        while len(a) > 0 and a[-1] == 0:
                            a = a[:-1]
                        right_p.append(tuple(a))
                    all_q = Set(t[0])
                    tens_q = {}
                    for a in all_q.subsets():
                        left_q = sorted(list(a))
                        right_q = sorted(list(all_q - a))
                        sign = Permutation(convert_perm(left_q + right_q)).signature()
                        tens_q[(tuple(left_q), tuple(right_q))] = sign
                    tens = {}
                    for l, r in zip(left_p, right_p):
                        for q in tens_q:
                            tens[((q[0], l), (q[1], r))] = tens_q[q]
                    return self.tensor_square()._from_dict(tens)
            elif basis == 'serre-cartan':
                from sage.categories.tensor import tensor
                result = self.tensor_square().one()
                if p == 2:
                    for n in t:
                        s = self.tensor_square().zero()
                        for i in range(0, n+1):
                            s += tensor((self.Sq(i), self.Sq(n-i)))
                        result = result * s
                    return result
                else:
                    bockstein = True
                    for n in t:
                        if bockstein:
                            if n != 0:
                                s = tensor((self.Q(0), self.one())) + tensor((self.one(), self.Q(0)))
                            else:
                                s = self.tensor_square().one()
                            bockstein = False
                        else:
                            s = self.tensor_square().zero()
                            for i in range(0, n+1):
                                s += tensor((self.P(i), self.P(n-i)))
                            bockstein = True
                        result = result * s
                    return result
        else:
            from sage.categories.tensor import tensor
            A = SteenrodAlgebra(p=p, basis=algorithm)
            x = A(self._change_basis_on_basis(t, algorithm)).coproduct(algorithm=algorithm)
            result = self.tensor_square().zero()
            for (a,b), coeff in x:
                result += coeff * tensor((A._change_basis_on_basis(a, basis),
                                          A._change_basis_on_basis(b, basis)))
            return result

    def coproduct(self, x, algorithm='milnor'):
        r"""
        Return the coproduct of an element ``x`` of this algebra.

        INPUT:

        - ``x`` -- element of self

        - ``algorithm`` -- None or a string, either 'milnor' or
          'serre-cartan' (or anything which will be converted to one
          of these by the function :func:`get_basis_name
          <sage.algebras.steenrod.steenrod_algebra_misc.get_basis_name>`.
          If None, default to 'serre-cartan' if current basis is
          'serre-cartan'; otherwise use 'milnor'.

        This calls :meth:`coproduct_on_basis` on the summands of ``x``
        and extends linearly.

        EXAMPLES::

            sage: SteenrodAlgebra().Sq(3).coproduct()
            1 # Sq(3) + Sq(1) # Sq(2) + Sq(2) # Sq(1) + Sq(3) # 1

        The element `\text{Sq}(0,1)` is primitive::

            sage: SteenrodAlgebra(basis='adem').Sq(0,1).coproduct()
            1 # Sq^2 Sq^1 + 1 # Sq^3 + Sq^2 Sq^1 # 1 + Sq^3 # 1
            sage: SteenrodAlgebra(basis='pst').Sq(0,1).coproduct()
            1 # P^0_2 + P^0_2 # 1

            sage: SteenrodAlgebra(p=3).P(4).coproduct()
            1 # P(4) + P(1) # P(3) + P(2) # P(2) + P(3) # P(1) + P(4) # 1
            sage: SteenrodAlgebra(p=3).P(4).coproduct(algorithm='serre-cartan')
            1 # P(4) + P(1) # P(3) + P(2) # P(2) + P(3) # P(1) + P(4) # 1
            sage: SteenrodAlgebra(p=3, basis='serre-cartan').P(4).coproduct()
            1 # P^4 + P^1 # P^3 + P^2 # P^2 + P^3 # P^1 + P^4 # 1
            sage: SteenrodAlgebra(p=11, profile=((), (2,1,2))).Q(0,2).coproduct()
            1 # Q_0 Q_2 + Q_0 # Q_2 + Q_0 Q_2 # 1 - Q_2 # Q_0
        """
        # taken from categories.coalgebras_with_basis, then modified
        # to allow the use of the "algorithm" keyword
        coprod = lambda x: self.coproduct_on_basis(x, algorithm)
        return Hom(self, tensor([self, self]), ModulesWithBasis(self.base_ring()))(on_basis = coprod)(x)

    def antipode_on_basis(self, t):
        r"""
        The antipode of a basis element of this algebra

        INPUT:

        - ``t`` -- tuple, the index of a basis element of self

        OUTPUT: the antipode of the corresponding basis element,
        as an element of self.

        ALGORITHM: according to a result of Milnor's, the antipode of
        `\text{Sq}(n)` is the sum of all of the Milnor basis elements
        in dimension `n`. So: convert the element to the Serre-Cartan
        basis, thus writing it as a sum of products of elements
        `\text{Sq}(n)`, and use Milnor's formula for the antipode of
        `\text{Sq}(n)`, together with the fact that the antipode is an
        antihomomorphism: if we call the antipode `c`, then `c(ab) =
        c(b) c(a)`.

        At odd primes, a similar method is used: the antipode of
        `P(n)` is the sum of the Milnor P basis elements in dimension
        `n*2(p-1)`, multiplied by `(-1)^n`, and the antipode of `\beta
        = Q_0` is `-Q_0`. So convert to the Serre-Cartan basis, as in
        the `p=2` case.

        EXAMPLES::

            sage: A = SteenrodAlgebra()
            sage: A.antipode_on_basis((4,))
            Sq(1,1) + Sq(4)
            sage: A.Sq(4).antipode()
            Sq(1,1) + Sq(4)
            sage: Adem = SteenrodAlgebra(basis='adem')
            sage: Adem.Sq(4).antipode()
            Sq^3 Sq^1 + Sq^4
            sage: SteenrodAlgebra(basis='pst').Sq(3).antipode()
            P^0_1 P^1_1 + P^0_2
            sage: a = SteenrodAlgebra(basis='wall_long').Sq(10)
            sage: a.antipode()
            Sq^1 Sq^2 Sq^4 Sq^1 Sq^2 + Sq^2 Sq^4 Sq^1 Sq^2 Sq^1 + Sq^8 Sq^2
            sage: a.antipode().antipode() == a
            True

            sage: SteenrodAlgebra(p=3).P(6).antipode()
            P(2,1) + P(6)
            sage: SteenrodAlgebra(p=3).P(6).antipode().antipode()
            P(6)

        TESTS::

            sage: Milnor = SteenrodAlgebra()
            sage: all([x.antipode().antipode() == x for x in Milnor.basis(11)]) # long time
            True
            sage: A5 = SteenrodAlgebra(p=5, basis='adem')
            sage: all([x.antipode().antipode() == x for x in A5.basis(25)])
            True
            sage: H = SteenrodAlgebra(profile=[2,2,1])
            sage: H.Sq(1,2).antipode() in H
            True
        """
        p = self.prime()
        if self.basis_name() == 'serre-cartan':
            antipode = self.one()
            if p == 2:
                for n in t:
                    antipode = self(sum(SteenrodAlgebra().basis(n))) * antipode
            else:
                from sage.misc.functional import is_even
                for index, n in enumerate(t):
                    if is_even(index):
                        if n != 0:
                            antipode = -self.Q(0) * antipode
                    else:
                        B = SteenrodAlgebra(p=p).basis(n * 2 * (p-1))
                        s = self(0)
                        for b in B:
                            if len(b.leading_support()[0]) == 0:
                                s += self(b)
                        antipode = (-1)**n * s * antipode
            return antipode
        return self(self._change_basis_on_basis(t, 'serre-cartan').antipode())

    def _milnor_on_basis(self, t):
        """
        Convert the tuple t in the current basis to an element in the
        Milnor basis.

        INPUT:

        - t - tuple, representing basis element in the current basis.

        OUTPUT: element of the Steenrod algebra with the Milnor basis

        ALGORITHM: there is a simple conversion from each basis to the
        Milnor basis, so use that.  In more detail:

        - If the current basis is the Milnor basis, just return the
          corresponding element.

        - If the current basis is the Serre-Cartan basis: when `p=2`,
          the element `\text{Sq}^a` equals the Milnor element
          `\text{Sq}(a)`; when `p` is odd, `\mathcal{P}^a =
          \mathcal{P}(a)` and `\beta = Q_0`. Hence for any
          Serre-Cartan basis element, represent it in the
          Milnor basis by computing an appropriate product using
          Milnor multiplication.

        - The same goes for Arnon's C basis, since the elements are
          monomials in the Steenrod squares.

        - If the current basis is Wood's Y or Z bases, then each basis
          element is a monomial in the classes `w(m,k) =
          \text{Sq}^{2^m (2^{k+1}-1)}`.  So again, multiply the
          corresponding Milnor elements together.

        - The Wall basis: each basis element is a monomial in the
          elements `Q^m_k = Sq(2^k) Sq(2^{k+1}) ... Sq(2^m)`.

        - Arnon's A basis: each basis element is a monomial in the
          elements `X^m_k = Sq(2^m) ... Sq(2^{k+1}) Sq(2^k)`.

        - The `P^s_t` bases: when `p=2`, each basis element is a
          monomial in the elements `P^s_t`.  When `p` is odd, each
          basis element is a product of elements `Q_i` and a monomial
          in the elements `(P^s_t)^n` where `0 < n < p`.

        - The commutator bases: when `p=2`, each basis element is a
          monomial in the iterated commutators `c_{i,j}`, defined by
          `c_{i,1} = \text{Sq}(2^i)` and `c_{i,j} = [c_{i,j-1},
          \text{Sq}(2^{i+j-1})]`.  When `p` is odd, each basis element
          is a product of elements `Q_i` and a monomial in the
          elements `c_{i,j}^n` where `0 < n < p`, `c_{i,1} =
          P(p^i)` and `c_{i,j} = [P(p^{i+j-1}), c_{i,j-1}]`.

        EXAMPLES::

            sage: Adem = SteenrodAlgebra(basis='serre-cartan')
            sage: Adem._milnor_on_basis((2,1)) # Sq^2 Sq^1
            Sq(0,1) + Sq(3)
            sage: Pst = SteenrodAlgebra(basis='pst')
            sage: Pst._milnor_on_basis(((0,1), (1,1), (2,1)))
            Sq(7)
        """
        basis = self.basis_name()
        p = self.prime()
        A = SteenrodAlgebra(p=p)
        # milnor
        if basis == 'milnor':
            return A({t: 1})

        ans = A(1)
        # serre-cartan, arnonc
        if p == 2 and (basis == 'serre-cartan' or basis == 'arnonc'):
            for j in t:
                ans = ans * A.Sq(j)

        elif p > 2 and basis == 'serre-cartan':
            bockstein = True
            for j in t:
                if bockstein:
                    if j != 0:
                        ans = ans * A.Q(0)
                    bockstein = False
                else:
                    ans = ans * A.P(j)
                    bockstein = True
        # wood_y:
        elif basis == 'woody' or basis == 'woodz':
            # each entry in t is a pair (m,k), corresponding to w(m,k), defined by
            # `w(m,k) = \text{Sq}^{2^m (2^{k+1}-1)}`.
            for (m,k) in t:
                ans = ans * A.Sq(2**m * (2**(k+1) - 1))

        # wall[_long]
        elif basis.find('wall') >= 0:
            # each entry in t is a pair (m,k), corresponding to Q^m_k, defined by
            #`Q^m_k = Sq(2^k) Sq(2^{k+1}) ... Sq(2^m)`.
            for (m,k) in t:
                exponent = 2**k
                ans = ans * A.Sq(exponent)
                for i in range(m-k):
                    exponent = exponent * 2
                    ans = ans * A.Sq(exponent)

        # pst...
        elif basis.find('pst') >= 0:
            if p == 2:
                # each entry in t is a pair (i,j), corresponding to P^i_j
                for (i,j) in t:
                    ans = ans * A.pst(i,j)
            else:
                # t = (Q, P) where Q is the tuple of Q_i's, and P is a
                # tuple with entries of the form ((i,j), n),
                # corresponding to (P^i_j)^n
                if len(t[0]) > 0:
                    ans = ans * A.Q(*t[0])
                for ((i, j), n) in t[1]:
                   ans = ans * (A.pst(i,j))**n

        # arnona[_long]
        elif basis.find('arnona') >= 0:
            # each entry in t is a pair (m,k), corresponding to X^m_k, defined by
            # `X^m_k = Sq(2^m) ... Sq(2^{k+1}) Sq(2^k)`
            for (m,k) in t:
                exponent = 2**k
                X = A.Sq(exponent)
                for i in range(m-k):
                    exponent = exponent * 2
                    X = A.Sq(exponent) * X
                ans = ans * X

        # comm...[_long]
        elif basis.find('comm') >= 0:
            if p == 2:
                # each entry in t is a pair (i,j), corresponding to
                # c_{i,j}, the iterated commutator defined by c_{i,1}
                # = Sq(2^i) and c_{i,j} = [c_{i,j-1}, Sq(2^{i+j-1})].
                for (i,j) in t:
                    comm = A.Sq(2**i)
                    for k in range(2, j+1):
                        y = A.Sq(2**(i+k-1))
                        comm = comm * y + y * comm
                    ans = ans * comm
            else:
                # t = (Q, P) where Q is the tuple of Q_i's, and P is a
                # tuple with entries of the form ((i,j), n),
                # corresponding to (c_{i,j})^n.  Here c_{i,j} is the
                # iterated commutator defined by c_{i,1} = P(p^i) and
                # c_{i,j} = [P(p^{i+j-1}), c_{i,j-1}].
                if len(t[0]) > 0:
                    ans = ans * A.Q(*t[0])
                for ((i, j), n) in t[1]:
                    comm = A.P(p**i)
                    for k in range(2, j+1):
                        y = A.P(p**(i+k-1))
                        comm = y * comm - comm * y
                    ans = ans * comm**n
        return ans

    @lazy_attribute
    def milnor(self):
        """
        Convert an element of this algebra to the Milnor basis

        INPUT:

        - x - an element of this algebra

        OUTPUT: x converted to the Milnor basis

        ALGORITHM: use the method ``_milnor_on_basis`` and linearity.

        EXAMPLES::

            sage: Adem = SteenrodAlgebra(basis='adem')
            sage: a = Adem.Sq(2) * Adem.Sq(1)
            sage: Adem.milnor(a)
            Sq(0,1) + Sq(3)
        """
        A = SteenrodAlgebra(p=self.prime(), basis='milnor')
        return self._module_morphism(self._milnor_on_basis, codomain=A)

    def _change_basis_on_basis(self, t, basis='milnor'):
        """
        Convert the tuple t to the named basis.

        INPUT:

        - ``t`` - tuple, representing basis element in the current basis.

        - ``basis`` - string, the basis to which to convert, optional
          (default 'milnor')

        OUTPUT: an element of the Steenrod algebra with basis ``basis``.

        ALGORITHM: it's straightforward to convert to the Milnor basis
        (using :meth:`milnor` or :meth:`_milnor_on_basis`), so it's
        straightforward to produce a matrix representing this
        conversion in any degree.  The function
        :func:`convert_from_milnor_matrix
        <steenrod_algebra_bases.convert_from_milnor_matrix>` provides
        the inverse operation.

        So: convert from the current basis to the Milnor basis, then
        from the Milnor basis to the new basis.

        EXAMPLES::

            sage: Adem = SteenrodAlgebra(basis='adem')
            sage: a = Adem({(2,1): 1}); a
            Sq^2 Sq^1
            sage: a.change_basis('adem')  # indirect doctest
            Sq^2 Sq^1
            sage: a.change_basis('milnor')
            Sq(0,1) + Sq(3)
            sage: a.change_basis('pst')
            P^0_1 P^1_1 + P^0_2
            sage: a.change_basis('milnor').change_basis('adem').change_basis('adem')
            Sq^2 Sq^1
            sage: a.change_basis('wall') == a.change_basis('woody')
            True

        TESTS::

            sage: a = sum(SteenrodAlgebra(basis='comm').basis(10))
            sage: a.change_basis('adem').change_basis('wall').change_basis('comm')._repr_() == a._repr_()
            True
            sage: a.change_basis('pst').change_basis('milnor').change_basis('comm')._repr_() == a._repr_()
            True
            sage: a.change_basis('woody').change_basis('arnona').change_basis('comm')._repr_() == a._repr_()
            True

            sage: b = sum(SteenrodAlgebra(p=3).basis(41))
            sage: b.change_basis('adem').change_basis('adem').change_basis('milnor')._repr_() == b._repr_()
            True
        """
        from sage.matrix.constructor import matrix
        from sage.rings.all import GF
        from steenrod_algebra_bases import steenrod_algebra_basis,\
            convert_from_milnor_matrix
        from steenrod_algebra_misc import get_basis_name
        basis = get_basis_name(basis, self.prime())
        if basis == self.basis_name():
            return self({t: 1})
        a = self._milnor_on_basis(t)
        if basis == 'milnor':
            return a
        d = a.monomial_coefficients()
        p = self.prime()
        deg = a.degree()
        A = SteenrodAlgebra(basis=basis, p=p)
        if deg == 0:
            return A(a.leading_coefficient())
        Bnew = steenrod_algebra_basis(deg, basis, p)
        Bmil = steenrod_algebra_basis(deg, 'milnor', p)
        v = []
        for a in Bmil:
            v.append(d.get(a, 0))
        out = (matrix(GF(p), 1, len(v), v) *
               convert_from_milnor_matrix(deg, basis, p))
        new_d = dict(zip(Bnew, out[0]))
        return A(new_d)

    def _change_basis(self, x, basis='milnor'):
        """
        Convert an element of this algebra to the specified basis

        INPUT:

        - ``x`` - an element of this algebra.

        - ``basis`` - string, the basis to which to convert, optional
          (default 'milnor')

        OUTPUT: an element of the Steenrod algebra with basis ``basis``.

        ALGORITHM: use :meth:`_change_basis_on_basis` and linearity

        EXAMPLES::

            sage: Adem = SteenrodAlgebra(basis='adem')
            sage: a = Adem({(2,1): 1}); a
            Sq^2 Sq^1
            sage: a.change_basis('adem')  # indirect doctest
            Sq^2 Sq^1
            sage: a.change_basis('milnor')
            Sq(0,1) + Sq(3)
            sage: a.change_basis('pst')
            P^0_1 P^1_1 + P^0_2
        """
        if basis == 'milnor':
            return x.milnor()
        A = SteenrodAlgebra(p=self.prime(), basis=basis)
        change = lambda y: self._change_basis_on_basis(y, basis)
        f = self._module_morphism(change, codomain=A)
        return f(x)

    def degree_on_basis(self, t):
        r"""
        The degree of the monomial specified by the tuple ``t``.

        INPUT:

        - ``t`` - tuple, representing basis element in the current basis.

        OUTPUT: integer, the degree of the corresponding element.

        The degree of `\text{Sq}(i_1,i_2,i_3,...)` is

        .. math::

            i_1 + 3i_2 + 7i_3 + ... + (2^k - 1) i_k + ....

        At an odd prime `p`, the degree of `Q_k` is `2p^k - 1` and the
        degree of `\mathcal{P}(i_1, i_2, ...)` is

        .. math::

            \sum_{k \geq 0} 2(p^k - 1) i_k.

        ALGORITHM: Each basis element is represented in terms relevant
        to the particular basis: 'milnor' basis elements (at the prime
        2) are given by tuples ``(a,b,c,...)`` corresponding to the
        element `\text{Sq}(a,b,c,...)`, while 'pst' basis elements are
        given by tuples of pairs ``((a, b), (c, d), ...)``,
        corresponding to the product `P^a_b P^c_d ...`.  The other
        bases have similar descriptions.  The degree of each basis
        element is computed from this data, rather than converting the
        element to the Milnor basis, for example, and then computing
        the degree.

        EXAMPLES::

            sage: SteenrodAlgebra().degree_on_basis((0,0,1))
            7
            sage: Sq(7).degree()
            7

            sage: A11 = SteenrodAlgebra(p=11)
            sage: A11.degree_on_basis(((), (1,1)))
            260
            sage: A11.degree_on_basis(((2,), ()))
            241
        """
        def p_degree(m, mult=1, prime=2):
            """
            For m=(n_1, n_2, n_3, ...), Sum_i (mult) * n_i * (p^i - 1)
            """
            i = 0
            deg = 0
            for n in m:
                i += 1
                deg += n*mult*(prime**i - 1)
            return deg

        def q_degree(m, prime=3):
            """
            For m=(n_0, n_1, n_2, ...), Sum_i 2*p^(n_i) - 1
            """
            deg = 0
            for n in m:
                deg += 2*prime**n - 1
            return deg

        p = self.prime()
        basis = self.basis_name()
        # milnor
        if basis == 'milnor':
            if p == 2:
                return p_degree(t)
            else:
                return q_degree(t[0], prime=p) + p_degree(t[1], prime=p, mult=2)
        # serre-cartan, arnonc
        if p == 2 and (basis == 'serre-cartan' or basis == 'arnonc'):
            return sum(t)
        if p > 2 and basis == 'serre-cartan':
            bockstein = True
            n = 0
            for j in t:
                if bockstein:
                    if j != 0:
                        n += 1
                    bockstein = False
                else:
                    n += 2 * j * (p - 1)
                    bockstein = True
            return n

        # wood_y:
        if basis == 'woody' or basis == 'woodz':
            # each entry in t is a pair (m,k), corresponding to w(m,k), defined by
            # `w(m,k) = \text{Sq}^{2^m (2^{k+1}-1)}`.
            return sum(2**m * (2**(k+1)-1) for (m,k) in t)

        # wall, arnon_a
        if basis.find('wall') >= 0 or basis.find('arnona') >= 0:
            # Wall: each entry in t is a pair (m,k), corresponding to
            # Q^m_k, defined by `Q^m_k = Sq(2^k) Sq(2^{k+1})
            # ... Sq(2^m)`.
            #
            # Arnon A: each entry in t is a pair (m,k), corresponding
            # to X^m_k, defined by `X^m_k = Sq(2^m) ... Sq(2^{k+1})
            # Sq(2^k)`
            return sum(2**k * (2**(m-k+1)-1) for (m,k) in t)

        # pst, comm
        if basis.find('pst') >= 0 or basis.find('comm') >= 0:
            if p == 2:
                # Pst: each entry in t is a pair (i,j), corresponding to P^i_j
                #
                # Comm: each entry in t is a pair (i,j), corresponding
                # to c_{i,j}, the iterated commutator defined by
                # c_{i,1} = Sq(2^i) and c_{i,j} = [c_{i,j-1},
                # Sq(2^{i+j-1})].
                return sum(2**m * (2**k - 1) for (m,k) in t)
            # p odd:
            #
            # Pst: have pair (Q, P) where Q is a tuple of Q's, as in
            # the Milnor basis, and P is a tuple of terms of the form
            # ((i,j), n), corresponding to (P^i_j)^n.
            #
            # Comm: similarly (Q, C) with Q as above and C a tuple
            # with each entry in t is of the form ((s,t), n),
            # corresponding to c_{s,t}^n.  here c_{s,t} is the the
            # iterated commutator defined by c_{s,1} = P(p^s) and
            # c_{s,t} = [P(p^{s+t-1}), c_{s,t-1}].
            q_deg = q_degree(t[0], prime=p)
            p_deg = sum(2 * n * p**s * (p**t - 1) for ((s,t), n) in t[1])
            return q_deg + p_deg

    # coercion methods:

    def _coerce_map_from_(self, S):
        r"""
        True if there is a coercion from ``S`` to ``self``, False otherwise.

        INPUT:

        -  ``S`` - a Sage object.

        The algebras that coerce into the mod p Steenrod algebra are:

        - the mod p Steenrod algebra `A`
        - its sub-Hopf algebras
        - its homogeneous components
        - its base field `GF(p)`
        - `ZZ`

        Similarly, a sub-Hopf algebra `B` of `A` coerces into another
        sub-Hopf algebra `C` if and only if the profile function for
        `B` is less than or equal to that of `C`, pointwise.

        EXAMPLES::

            sage: A = SteenrodAlgebra()
            sage: A1 = SteenrodAlgebra(profile=[2,1])
            sage: A2 = SteenrodAlgebra(profile=[3,2,1])
            sage: B = SteenrodAlgebra(profile=[1,2,1])
            sage: A._coerce_map_from_(A1)
            True
            sage: A2._coerce_map_from_(A1)
            True
            sage: A1._coerce_map_from_(A)
            False
            sage: A1._coerce_map_from_(B)
            False
            sage: B._coerce_map_from_(A1)
            False

            sage: A._coerce_map_from_(A[12])
            True

            sage: A3 = SteenrodAlgebra(p=3)
            sage: A31 = SteenrodAlgebra(p=3, profile=([1], [2, 2]))
            sage: B3 = SteenrodAlgebra(p=3, profile=([1, 2, 1], [1]))
            sage: A3._coerce_map_from_(A31)
            True
            sage: A31._coerce_map_from_(A3)
            False
            sage: A31._coerce_map_from_(B3)
            False
            sage: B3._coerce_map_from_(A31)
            False
        """
        from sage.rings.all import ZZ, GF
        from sage.rings.infinity import Infinity
        p = self.prime()
        if S == ZZ or S == GF(p):
            return True
        if (isinstance(S, SteenrodAlgebra_generic) and p == S.prime()):
            # deal with profiles.
            if p == 2:
                self_prec = len(self._profile)
                S_prec = len(S._profile)
                return all([self.profile(i) >= S.profile(i)
                            for i in range(1, max(self_prec, S_prec)+1)])
            self_prec = len(self._profile[0])
            S_prec = len(S._profile[0])
            return (all([self.profile(i) >= S.profile(i)
                         for i in range(1, max(self_prec, S_prec)+1)])
                    and all([self.profile(i, 1) >= S.profile(i, 1)
                         for i in range(1, max(self_prec, S_prec)+1)]))
        if (isinstance(S, CombinatorialFreeModule)
            and S.dimension() < Infinity and p == S.base_ring().characteristic()):
            from steenrod_algebra_misc import get_basis_name
            try:
                get_basis_name(S.prefix(), S.base_ring().characteristic())
                # return all([a in self for a in S.basis()])
                return True
            except ValueError:
                return False
        return False

    def _element_constructor_(self, x):
        r"""
        Try to turn ``x`` into an element of ``self``.

        INPUT:

        - ``x`` - an element of some Steenrod algebra or an element of
          `\ZZ` or `\GF{p}` or a dict

        OUTPUT: ``x`` as a member of ``self``.

        If ``x`` is a dict, then call :meth:`_from_dict` on it,
        coercing the coefficients into the base field.  That is, treat
        it as having entries of the form ``tuple: coeff``, where
        ``tuple`` is a tuple representing a basis element and
        ``coeff`` is the coefficient of that element.

        EXAMPLES::

            sage: A1 = SteenrodAlgebra(profile=[2,1])
            sage: A1(Sq(2))  # indirect doctest
            Sq(2)
            sage: A1._element_constructor_(Sq(2))
            Sq(2)
            sage: A1(3)  # map integer into A1
            1
            sage: A1._element_constructor_(Sq(4)) # Sq(4) not in A1
            Traceback (most recent call last):
            ...
            ValueError: Element does not lie in this Steenrod algebra
            sage: A1({(2,): 1, (1,): 13})
            Sq(1) + Sq(2)
        """
        from sage.rings.all import ZZ, GF
        if x in GF(self.prime()) or x in ZZ:
            return self.from_base_ring_from_one_basis(x)

        if isinstance(x, dict):
            A = SteenrodAlgebra(p=self.prime(), basis=self.basis_name())
            x = A._from_dict(x, coerce=True)
        if x in self:
            if x.basis_name() == self.basis_name():
                if x.parent() is self:
                    return x
                return self._from_dict(x.monomial_coefficients(), coerce=True)
            else:
                a = x.milnor()
                if self.basis_name() == 'milnor':
                    return a
                return a.change_basis(self.basis_name())
        raise ValueError("Element does not lie in this Steenrod algebra")

    def __contains__(self, x):
        r"""
        True if self contains x.

        EXAMPLES::

            sage: Sq(3,1,1) in SteenrodAlgebra()
            True
            sage: Sq(3,1,1) in SteenrodAlgebra(p=5)
            False

            sage: A1 = SteenrodAlgebra(profile=[2,1])
            sage: Sq(3) in A1
            True
            sage: Sq(4) in A1
            False
            sage: Sq(0,2) in A1
            False

            sage: A_3 = SteenrodAlgebra(p=3)
            sage: B_3 = SteenrodAlgebra(p=3, profile=([1], [2,2,1,1]))
            sage: A_3.P(2) in B_3
            True
            sage: A_3.P(3) in B_3
            False
            sage: A_3.Q(1) in B_3
            True
            sage: A_3.P(1) * A_3.Q(2) in B_3
            False
        """
        from sage.rings.all import GF
        p = self.prime()
        if (GF(p).__contains__(x)):
            return True
        if (isinstance(x, self.Element)
            and x.prime() == p):
            A = SteenrodAlgebra(p=p, basis=self.basis_name())
            if self._has_nontrivial_profile():
                return all([self._check_profile_on_basis(mono)
                            for mono in A(x).support()])
            return True  # trivial profile, so True
        return False

    def basis(self, d=None):
        """
        Returns basis for self, either the whole basis or the basis in
        degree `d`.

        INPUT:

        - `d` - integer or None, optional (default None)

        OUTPUT: If `d` is None, then return a basis of the algebra.
        Otherwise, return the basis in degree `d`.

        EXAMPLES::

            sage: A3 = SteenrodAlgebra(3)
            sage: A3.basis(13)
            Family (Q_1 P(2), Q_0 P(3))
            sage: SteenrodAlgebra(2, 'adem').basis(12)
            Family (Sq^12, Sq^11 Sq^1, Sq^9 Sq^2 Sq^1, Sq^8 Sq^3 Sq^1, Sq^10 Sq^2, Sq^9 Sq^3, Sq^8 Sq^4)

            sage: A = SteenrodAlgebra(profile=[1,2,1])
            sage: A.basis(2)
            Family ()
            sage: A.basis(3)
            Family (Sq(0,1),)
            sage: SteenrodAlgebra().basis(3)
            Family (Sq(0,1), Sq(3))
            sage: A_pst = SteenrodAlgebra(profile=[1,2,1], basis='pst')
            sage: A_pst.basis(3)
            Family (P^0_2,)

            sage: A7 = SteenrodAlgebra(p=7)
            sage: B = SteenrodAlgebra(p=7, profile=([1,2,1], [1]))
            sage: A7.basis(84)
            Family (P(7),)
            sage: B.basis(84)
            Family ()
            sage: C = SteenrodAlgebra(p=7, profile=([1], [2,2]))
            sage: A7.Q(0,1) in C.basis(14)
            True
            sage: A7.Q(2) in A7.basis(97)
            True
            sage: A7.Q(2) in C.basis(97)
            False

        With no arguments, return the basis of the whole algebra.
        This doesn't print in a very helpful way, unfortunately::

            sage: A7.basis()
            Lazy family (Term map from Lazy family (<functools.partial object at ...>(i))_{i in Non negative integers} to mod 7 Steenrod algebra, milnor basis(i))_{i in Lazy family (<functools.partial object at ...>(i))_{i in Non negative integers}}
        """
        from sage.sets.family import Family
        if d is None:
            return Family(self._basis_keys, self.monomial)
        else:
            return Family([self.monomial(tuple(a)) for a in self._basis_fcn(d)])

    def _check_profile_on_basis(self, t):
        """
        True if the element specified by the tuple ``t`` is in this
        algebra.

        INPUT:

        - ``t`` - tuple of ...


        EXAMPLES::

            sage: A = SteenrodAlgebra(profile=[1,2,1])
            sage: A._check_profile_on_basis((0,0,1))
            True
            sage: A._check_profile_on_basis((0,0,2))
            False
            sage: A5 = SteenrodAlgebra(p=5, profile=([3,2,1], [2,2,2,2,2]))
            sage: A5._check_profile_on_basis(((), (1,5)))
            True
            sage: A5._check_profile_on_basis(((1,1,1), (1,5)))
            True
            sage: A5._check_profile_on_basis(((1,1,1), (1,5,5)))
            False
        """
        if self.basis_name() != 'milnor':
            A = SteenrodAlgebra(p=self.prime(),
                                   profile=self._profile,
                                   truncation_type=self._truncation_type)
            return all([A._check_profile_on_basis(a[0])
                        for a in self._milnor_on_basis(t)])

        from sage.rings.infinity import Infinity
        p = self.prime()
        if not self._has_nontrivial_profile():
            return True
        profile = self.profile
        if p == 2:
            return all([self.profile(i+1) == Infinity
                        or t[i] < 2**self.profile(i+1)
                        for i in range(len(t))])
        # p odd:
        if any([self.profile(i,1) != 2 for i in t[0]]):
            return False
        return all([self.profile(i+1,0) == Infinity
                    or t[1][i] < p**self.profile(i+1,0)
                    for i in range(len(t[1]))])

    def P(self, *nums):
        r"""
        The element `P(a, b, c, ...)`

        INPUT:

        -  ``a, b, c, ...`` - non-negative integers

        OUTPUT: element of the Steenrod algebra given by the Milnor
        single basis element `P(a, b, c, ...)`

        Note that at the prime 2, this is the same element as
        `\text{Sq}(a, b, c, ...)`.

        EXAMPLES::

            sage: A = SteenrodAlgebra(2)
            sage: A.P(5)
            Sq(5)
            sage: B = SteenrodAlgebra(3)
            sage: B.P(5,1,1)
            P(5,1,1)
            sage: B.P(1,1,-12,1)
            Traceback (most recent call last):
            ...
            TypeError: entries must be non-negative integers

            sage: SteenrodAlgebra(basis='serre-cartan').P(0,1)
            Sq^2 Sq^1 + Sq^3
        """
        from sage.rings.all import Integer
        if self.basis_name() != 'milnor':
            return self(SteenrodAlgebra(p=self.prime()).P(*nums))
        while len(nums) > 0 and nums[-1] == 0:
            nums = nums[:-1]
        if len(nums) == 0 or (len(nums) == 1 and nums[0] == 0):
            return self.one()
        for i in nums:
            try:
                assert Integer(i) >= 0
            except (TypeError, AssertionError):
                raise TypeError("entries must be non-negative integers")

        if self.prime() == 2:
            t = nums
        else:
            t = ((), nums)
        if self._check_profile_on_basis(t):
            A = SteenrodAlgebra_generic(p=self.prime())
            a = A.monomial(t)
            return self(a)
        raise ValueError("Element not in this algebra")

    def Q_exp(self, *nums):
        r"""
        The element `Q_0^{e_0} Q_1^{e_1} ...` , given by
        specifying the exponents.

        INPUT:

        - ``e0, e1, ...`` - sequence of 0s and 1s

        OUTPUT: The element `Q_0^{e_0} Q_1^{e_1} ...`

        Note that at the prime 2, `Q_n` is the element
        `\text{Sq}(0,0,...,1)` , where the 1 is in the
        `(n+1)^{st}` position.

        Compare this to the method :meth:`Q`, which defines a similar
        element, but by specifying the tuple of subscripts of terms
        with exponent 1.

        EXAMPLES::

            sage: A2 = SteenrodAlgebra(2)
            sage: A5 = SteenrodAlgebra(5)
            sage: A2.Q_exp(0,0,1,1,0)
            Sq(0,0,1,1)
            sage: A5.Q_exp(0,0,1,1,0)
            Q_2 Q_3
            sage: A5.Q(2,3)
            Q_2 Q_3
            sage: A5.Q_exp(0,0,1,1,0) == A5.Q(2,3)
            True
        """
        if not set(nums).issubset(set((0,1))):
            raise ValueError("The tuple %s should consist " % (nums,) + \
                "only of 0's and 1's")
        else:
            if self.basis_name() != 'milnor':
                return self(SteenrodAlgebra(p=self.prime()).Q_exp(*nums))
            while nums[-1] == 0:
                nums = nums[:-1]
            if self.prime() == 2:
                return self.P(*nums)
            else:
                mono = ()
                index = 0
                for e in nums:
                    if e == 1:
                        mono = mono + (index,)
                    index += 1
                return self.Q(*mono)

    def Q(self, *nums):
        r"""
        The element `Q_{n0} Q_{n1} ...` , given by specifying the
        subscripts.

        INPUT:

        - ``n0, n1, ...`` - non-negative integers

        OUTPUT: The element `Q_{n0} Q_{n1} ...`

        Note that at the prime 2, `Q_n` is the element
        `\text{Sq}(0,0,...,1)` , where the 1 is in the
        `(n+1)^{st}` position.

        Compare this to the method :meth:`Q_exp`, which defines a
        similar element, but by specifying the tuple of exponents.

        EXAMPLES::

            sage: A2 = SteenrodAlgebra(2)
            sage: A2.Q(2,3)
            Sq(0,0,1,1)
            sage: A5 = SteenrodAlgebra(5)
            sage: A5.Q(1,4)
            Q_1 Q_4
            sage: A5.Q(1,4) == A5.Q_exp(0,1,0,0,1)
            True
            sage: H = SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]])
            sage: H.Q(2)
            Q_2
            sage: H.Q(4)
            Traceback (most recent call last):
            ...
            ValueError: Element not in this algebra
        """
        if len(nums) != len(set(nums)):
            return self(0)
        else:
            if self.basis_name() != 'milnor':
                return self(SteenrodAlgebra(p=self.prime()).Q(*nums))
            if self.prime() == 2:
                if len(nums) == 0:
                    return self.one()
                else:
                    list = (1+max(nums)) * [0]
                    for i in nums:
                        list[i] = 1
                    return self.Sq(*tuple(list))
            else:
                answer = self.one()
                for i in nums:
                    answer = answer * self.monomial(((i,), ()))
                t = answer.leading_support()
                if self._check_profile_on_basis(t):
                    return answer
                raise ValueError("Element not in this algebra")

    def an_element(self):
        """
        An element of this Steenrod algebra. The element depends on
        the basis and whether there is a nontrivial profile function.
        (This is used by the automatic test suite, so having different
        elements in different bases may help in discovering bugs.)

        EXAMPLES::

            sage: SteenrodAlgebra().an_element()
            Sq(2,1)
            sage: SteenrodAlgebra(basis='adem').an_element()
            Sq^4 Sq^2 Sq^1
            sage: SteenrodAlgebra(p=5).an_element()
            4 Q_1 Q_3 P(2,1)
            sage: SteenrodAlgebra(basis='pst').an_element()
            P^3_1
            sage: SteenrodAlgebra(basis='pst', profile=[3,2,1]).an_element()
            P^0_1
        """
        from sage.rings.all import GF
        basis = self.basis_name()
        p = self.prime()

        if self._has_nontrivial_profile():
            if self.ngens() > 0:
                return self.gen(0)
            else:
                return self.one()

        if basis == 'milnor' and p == 2:
            return self.monomial((2,1))
        if basis == 'milnor' and p > 2:
            return self.term(((1,3), (2,1)), GF(p)(p-1))
        if basis == 'serre-cartan' and p == 2:
            return self.monomial((4,2,1))
        if basis == 'serre-cartan' and p > 2:
            return self.term((1,p,0,1,0), GF(p)(p-1))
        if basis == 'woody' or basis == 'woodz':
            return self._from_dict({((3,0),): 1, ((1, 1), (1, 0)): 1}, coerce=True)
        if basis.find('wall') >= 0:
            return self._from_dict({((1,1), (1,0)): 1, ((2, 2), (0, 0)): 1}, coerce=True)
        if basis.find('arnona') >= 0:
            return self._from_dict({((3,3),): 1, ((1, 1), (2, 1)): 1}, coerce=True)
        if basis == 'arnonc':
            return self._from_dict({(8,): 1, (4, 4): 1}, coerce=True)
        if basis.find('pst') >= 0:
            if p == 2:
                return self.monomial(((3, 1),))
            return self.term(((1,), (((1,1), 2),)), GF(p)(p-1))
        if basis.find('comm') >= 0:
            if p == 2:
                return self.monomial(((1, 2),))
            return self.term(((), (((1,2), 1),)), GF(p)(p-1))

    def pst(self,s,t):
        r"""
        The Margolis element `P^s_t`.

        INPUT:

        -  ``s`` - non-negative integer

        -  ``t`` - positive integer

        -  ``p`` - positive prime number

        OUTPUT: element of the Steenrod algebra

        This returns the Margolis element `P^s_t` of the mod
        `p` Steenrod algebra: the element equal to
        `P(0,0,...,0,p^s)`, where the `p^s` is in position
        `t`.

        EXAMPLES::

            sage: A2 = SteenrodAlgebra(2)
            sage: A2.pst(3,5)
            Sq(0,0,0,0,8)
            sage: A2.pst(1,2) == Sq(4)*Sq(2) + Sq(2)*Sq(4)
            True
            sage: SteenrodAlgebra(5).pst(3,5)
            P(0,0,0,0,125)
        """
        from sage.rings.all import Integer
        if self.basis_name() != 'milnor':
            return self(SteenrodAlgebra(p=self.prime()).pst(s,t))
        if not isinstance(s, (Integer, int)) and s >= 0:
            raise ValueError("%s is not a non-negative integer" % s)
        if not isinstance(t, (Integer, int)) and t > 0:
            raise ValueError("%s is not a positive integer" % t)
        nums = (0,)*(t-1) + (self.prime()**s,)
        return self.P(*nums)

    def ngens(self):
        r"""
        Number of generators of self.

        OUTPUT: number or Infinity

        The Steenrod algebra is infinitely generated.  A sub-Hopf
        algebra may be finitely or infinitely generated; in general,
        it is not clear what a minimal generating set is, nor the
        cardinality of that set.  So: if the algebra is
        infinite-dimensional, this returns Infinity.  If the algebra
        is finite-dimensional and is equal to one of the sub-Hopf
        algebras `A(n)`, then their minimal generating set is known,
        and this returns the cardinality of that set.  Otherwise, any
        sub-Hopf algebra is (not necessarily minimally) generated by
        the `P^s_t`'s that it contains (along with the `Q_n`'s it
        contains, at odd primes), so this returns the number of
        `P^s_t`'s and `Q_n`'s in the algebra.

        EXAMPLES::

            sage: A = SteenrodAlgebra(3)
            sage: A.ngens()
            +Infinity
            sage: SteenrodAlgebra(profile=lambda n: n).ngens()
            +Infinity
            sage: SteenrodAlgebra(profile=[3,2,1]).ngens() # A(2)
            3
            sage: SteenrodAlgebra(profile=[3,2,1], basis='pst').ngens()
            3
            sage: SteenrodAlgebra(p=3, profile=[[3,2,1], [2,2,2,2]]).ngens() # A(3) at p=3
            4
            sage: SteenrodAlgebra(profile=[1,2,1,1]).ngens()
            5
        """
        from sage.rings.infinity import Infinity
        if self._truncation_type == Infinity:
            return Infinity
        n = self.profile(1)
        p = self.prime()
        if p == 2 and self._profile == AA(n-1, p=p)._profile:
            return n
        if p > 2 and self._profile == AA(n, p=p)._profile:
            return n+1
        if p == 2:
            return sum(self._profile)
        return sum(self._profile[0]) + len([a for a in self._profile[1] if a == 2])

    def gens(self):
        r"""
        Family of generators for this algebra.

        OUTPUT: family of elements of this algebra

        At the prime 2, the Steenrod algebra is generated by the
        elements `\text{Sq}^{2^i}` for `i \geq 0`.  At odd primes, it
        is generated by the elements `Q_0` and `\mathcal{P}^{p^i}` for
        `i \geq 0`.  So if this algebra is the entire Steenrod
        algebra, return an infinite family made up of these elements.

        For sub-Hopf algebras of the Steenrod algebra, it is not
        always clear what a minimal generating set is.  The sub-Hopf
        algebra `A(n)` is minimally generated by the elements
        `\text{Sq}^{2^i}` for `0 \leq i \leq n` at the prime 2.  At
        odd primes, `A(n)` is minimally generated by `Q_0` along with
        `\mathcal{P}^{p^i}` for `0 \leq i \leq n-1`.  So if this
        algebra is `A(n)`, return the appropriate list of generators.

        For other sub-Hopf algebras: return a non-minimal generating
        set: the family of `P^s_t`'s and `Q_n`'s contained in the
        algebra.

        EXAMPLES::

            sage: A3 = SteenrodAlgebra(3, 'adem')
            sage: A3.gens()
            Lazy family (<bound method SteenrodAlgebra_generic_with_category.gen of mod 3 Steenrod algebra, serre-cartan basis>(i))_{i in Non negative integers}
            sage: A3.gens()[0]
            beta
            sage: A3.gens()[1]
            P^1
            sage: A3.gens()[2]
            P^3
            sage: SteenrodAlgebra(profile=[3,2,1]).gens()
            Family (Sq(1), Sq(2), Sq(4))

        In the following case, return a non-minimal generating set.
        (It is not minimal because `\text{Sq}(0,0,1)` is the
        commutator of `\text{Sq}(1)` and `\text{Sq}(0,2)`.) ::

            sage: SteenrodAlgebra(profile=[1,2,1]).gens()
            Family (Sq(1), Sq(0,1), Sq(0,2), Sq(0,0,1))
            sage: SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]]).gens()
            Family (Q_0, P(1), P(5))
            sage: SteenrodAlgebra(profile=lambda n: n).gens()
            Lazy family (<bound method SteenrodAlgebra_mod_two_with_category.gen of sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [1, 2, 3, ..., 98, 99, +Infinity, +Infinity, +Infinity, ...]>(i))_{i in Non negative integers}

        You may also use ``algebra_generators`` instead of ``gens``::

            sage: SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]]).algebra_generators()
            Family (Q_0, P(1), P(5))
        """
        from sage.sets.family import Family
        from sage.sets.non_negative_integers import NonNegativeIntegers
        from sage.rings.infinity import Infinity
        n = self.ngens()
        if n < Infinity:
            return Family([self.gen(i) for i in range(n)])
        return Family(NonNegativeIntegers(), self.gen)

    algebra_generators = gens

    def gen(self, i=0):
        r"""
        The ith generator of this algebra.

        INPUT:

        - ``i`` - non-negative integer

        OUTPUT: the ith generator of this algebra

        For the full Steenrod algebra, the `i^{th}` generator is
        `\text{Sq}(2^i)` at the prime 2; when `p` is odd, the 0th generator
        is `\beta = Q(0)`, and for `i>0`, the `i^{th}` generator is
        `P(p^{i-1})`.

        For sub-Hopf algebras of the Steenrod algebra, it is not
        always clear what a minimal generating set is.  The sub-Hopf
        algebra `A(n)` is minimally generated by the elements
        `\text{Sq}^{2^i}` for `0 \leq i \leq n` at the prime 2.  At
        odd primes, `A(n)` is minimally generated by `Q_0` along with
        `\mathcal{P}^{p^i}` for `0 \leq i \leq n-1`.  So if this
        algebra is `A(n)`, return the appropriate generator.

        For other sub-Hopf algebras: they are generated (but not
        necessarily minimally) by the `P^s_t`'s (and `Q_n`'s, if `p`
        is odd) that they contain.  So order the `P^s_t`'s (and
        `Q_n`'s) in the algebra by degree and return the `i`-th one.

        EXAMPLES::

            sage: A = SteenrodAlgebra(2)
            sage: A.gen(4)
            Sq(16)
            sage: A.gen(200)
            Sq(1606938044258990275541962092341162602522202993782792835301376)
            sage: SteenrodAlgebra(2, basis='adem').gen(2)
            Sq^4
            sage: SteenrodAlgebra(2, basis='pst').gen(2)
            P^2_1
            sage: B = SteenrodAlgebra(5)
            sage: B.gen(0)
            Q_0
            sage: B.gen(2)
            P(5)

            sage: SteenrodAlgebra(profile=[2,1]).gen(1)
            Sq(2)
            sage: SteenrodAlgebra(profile=[1,2,1]).gen(1)
            Sq(0,1)
            sage: SteenrodAlgebra(profile=[1,2,1]).gen(5)
            Traceback (most recent call last):
            ...
            ValueError: This algebra only has 4 generators, so call gen(i) with 0 <= i < 4

            sage: D = SteenrodAlgebra(profile=lambda n: n)
            sage: [D.gen(n) for n in range(5)]
            [Sq(1), Sq(0,1), Sq(0,2), Sq(0,0,1), Sq(0,0,2)]
            sage: D3 = SteenrodAlgebra(p=3, profile=(lambda n: n, lambda n: 2))
            sage: [D3.gen(n) for n in range(9)]
            [Q_0, P(1), Q_1, P(0,1), Q_2, P(0,3), P(0,0,1), Q_3, P(0,0,3)]
            sage: D3 = SteenrodAlgebra(p=3, profile=(lambda n: n, lambda n: 1 if n<1 else 2))
            sage: [D3.gen(n) for n in range(9)]
            [P(1), Q_1, P(0,1), Q_2, P(0,3), P(0,0,1), Q_3, P(0,0,3), P(0,0,0,1)]
            sage: SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]], basis='pst').gen(2)
            P^1_1
        """
        from sage.rings.infinity import Infinity
        from sage.rings.all import Integer
        p = self.prime()
        if not isinstance(i, (Integer, int)) and i >= 0:
            raise ValueError("%s is not a non-negative integer" % i)
        num = self.ngens()
        if num < Infinity:
            if i >= num:
                raise ValueError("This algebra only has %s generators, so call gen(i) with 0 <= i < %s" % (num, num))
            # check to see if equal to A(n) for some n.
            n = self.profile(1)
            if p == 2 and self._profile == AA(n-1, p=p)._profile:
                return self.pst(i,1)
            if p > 2 and self._profile == AA(n, p=p)._profile:
                if i == 0:
                    return self.Q(0)
                return self.pst(i-1, 1)
            # if not A(n), return list of P^s_t's in algebra, along with Q's if p is odd
            idx = -1
            if p == 2:
                last_t = len(self._profile)
            else:
                last_t = max(len(self._profile[0]), len(self._profile[1]))
            last_s = self.profile(last_t)
            for j in range(1, last_s + last_t + 1):
                if p > 2 and self.profile(j-1, 1) == 2:
                    guess = self.Q(j-1)
                    idx += 1
                if idx == i:
                    elt = guess
                    break
                for t in range(1, min(j, last_t) + 1):
                    s = j - t
                    if self.profile(t) > s:
                        guess = self.pst(s,t)
                        idx += 1
                    if idx == i:
                        elt = guess
                        break
            return elt

        # entire Steenrod algebra:
        if self.profile(1) == Infinity:
            if p == 2:
                return self.Sq(p**i)
            elif self.profile(0,1) == 2:
                if i == 0:
                    return self.Q(0)
                else:
                    return self.P(p**(i-1))

        # infinite-dimensional sub-Hopf algebra
        idx = -1
        tot = 1
        found = False
        A = SteenrodAlgebra(p=p)
        while not found:
            if p > 2:
                test = A.Q(tot-1)
                if test in self:
                    idx += 1
                    if idx == i:
                        found = True
                        break
            for t in range(1, tot+1):
                s = tot - t
                test = A.pst(s,t)
                if test in self:
                    idx += 1
                    if idx == i:
                        found = True
                        break
            tot += 1
        return test

    def is_commutative(self):
        r"""
        True if ``self`` is graded commutative, as determined by the
        profile function.  In particular, a sub-Hopf algebra of the
        mod 2 Steenrod algebra is commutative if and only if there is
        an integer `n>0` so that its profile function `e` satisfies

        - `e(i) = 0` for `i < n`,
        - `e(i) \leq n` for `i \geq n`.

        When `p` is odd, there must be an integer `n \geq 0` so that
        the profile functions `e` and `k` satisfy

        - `e(i) = 0` for `i < n`,
        - `e(i) \leq n` for `i \geq n`.
        - `k(i) = 1` for `i < n`.

        EXAMPLES::

            sage: A = SteenrodAlgebra(p=3)
            sage: A.is_commutative()
            False
            sage: SteenrodAlgebra(profile=[2,1]).is_commutative()
            False
            sage: SteenrodAlgebra(profile=[0,2,2,1]).is_commutative()
            True

        Note that if the profile function is specified by a function,
        then by default it has infinite truncation type: the profile
        function is assumed to be infinite after the 100th term.  ::

            sage: SteenrodAlgebra(profile=lambda n: 1).is_commutative()
            False
            sage: SteenrodAlgebra(profile=lambda n: 1, truncation_type=0).is_commutative()
            True

            sage: SteenrodAlgebra(p=5, profile=([0,2,2,1], [])).is_commutative()
            True
            sage: SteenrodAlgebra(p=5, profile=([0,2,2,1], [1,1,2])).is_commutative()
            True
            sage: SteenrodAlgebra(p=5, profile=([0,2,1], [1,2,2,2])).is_commutative()
            False
        """
        if not self._has_nontrivial_profile() or self._truncation_type > 0:
            return False
        p = self.prime()
        if p == 2:
            n = max(self._profile)
            return all([self.profile(i) == 0 for i in range(1, n)])
        n = max(self._profile[0])
        return (all([self.profile(i,0) == 0 for i in range(1, n)])
                and all([self.profile(i,1) == 1 for i in range(n)]))

    def is_finite(self):
        r"""
        True if this algebra is finite-dimensional.

        Therefore true if the profile function is finite, and in
        particular the ``truncation_type`` must be finite.
        
        EXAMPLES::
        
            sage: A = SteenrodAlgebra(p=3)
            sage: A.is_finite()
            False
            sage: SteenrodAlgebra(profile=[3,2,1]).is_finite()
            True
            sage: SteenrodAlgebra(profile=lambda n: n).is_finite()
            False
        """
        return self._has_nontrivial_profile() and self._truncation_type == 0

    def dimension(self):
        r"""
        The dimension of this algebra as a vector space over `\GF{p}`.

        If the algebra is infinite, return ``+Infinity``.  Otherwise,
        the profile function must be finite.  In this case, at the
        prime 2, its dimension is `2^s`, where `s` is the sum of the
        entries in the profile function.  At odd primes, the dimension
        is `p^s * 2^t` where `s` is the sum of the `e` component of
        the profile function and `t` is the number of 2's in the `k`
        component of the profile function.

        EXAMPLES::
        
            sage: SteenrodAlgebra(p=7).dimension()
            +Infinity
            sage: SteenrodAlgebra(profile=[3,2,1]).dimension()
            64
            sage: SteenrodAlgebra(p=3, profile=([1,1], [])).dimension()
            9
            sage: SteenrodAlgebra(p=5, profile=([1], [2,2])).dimension()
            20
        """
        from sage.rings.infinity import Infinity
        if not self.is_finite():
            return Infinity
        p = self.prime()
        if p == 2:
            return 2**sum(self._profile)
        return p**sum(self._profile[0]) * 2**len([a for a in self._profile[1] if a == 2])

    def order(self):
        r"""
        The order of this algebra.

        This is computed by computing its vector space dimension `d`
        and then returning `p^d`.

        EXAMPLES::
        
            sage: SteenrodAlgebra(p=7).order()
            +Infinity
            sage: SteenrodAlgebra(profile=[2,1]).dimension()
            8
            sage: SteenrodAlgebra(profile=[2,1]).order()
            256
            sage: SteenrodAlgebra(p=3, profile=([1], [])).dimension()
            3
            sage: SteenrodAlgebra(p=3, profile=([1], [])).order()
            27
            sage: SteenrodAlgebra(p=5, profile=([], [2, 2])).dimension()
            4
            sage: SteenrodAlgebra(p=5, profile=([], [2, 2])).order() == 5**4
            True
        """
        from sage.rings.infinity import Infinity
        if not self.is_finite():
            return Infinity
        return self.prime() ** self.dimension()

    def is_division_algebra(self):
        r"""
        The only way this algebra can be a division algebra is if it
        is the ground field `\GF{p}`.
        
        EXAMPLES::
        
            sage: SteenrodAlgebra(11).is_division_algebra()
            False
            sage: SteenrodAlgebra(profile=lambda n: 0, truncation_type=0).is_division_algebra()
            True
        """
        return self.is_field()

    def is_field(self, proof = True):
        r"""
        The only way this algebra can be a field is if it is the
        ground field `\GF{p}`.

        EXAMPLES::
        
            sage: SteenrodAlgebra(11).is_field()
            False
            sage: SteenrodAlgebra(profile=lambda n: 0, truncation_type=0).is_field()
            True
        """
        return self.dimension() == 1

    def is_integral_domain(self, proof = True):
        r"""
        The only way this algebra can be an integral domain is if it
        is the ground field `\GF{p}`.

        EXAMPLES::
        
            sage: SteenrodAlgebra(11).is_integral_domain()
            False
            sage: SteenrodAlgebra(profile=lambda n: 0, truncation_type=0).is_integral_domain()
            True
        """
        return self.is_field()

    def is_noetherian(self):
        """
        This algebra is noetherian if and only if it is finite.

        EXAMPLES::

            sage: SteenrodAlgebra(3).is_noetherian()
            False
            sage: SteenrodAlgebra(profile=[1,2,1]).is_noetherian()
            True
            sage: SteenrodAlgebra(profile=lambda n: n+2).is_noetherian()
            False
        """
        return self.is_finite()

    ######################################################
    # element class
    ######################################################

    class Element(CombinatorialFreeModuleElement):
        r"""
        Class for elements of the Steenrod algebra.  Since the
        Steenrod algebra class is based on
        :class:`CombinatorialFreeModule
        <sage.combinat.free_module.CombinatorialFreeModule>`, this is
        based on :class:`CombinatorialFreeModuleElement
        <sage.combinat.free_module.CombinatorialFreeModuleElement>`.
        It has new methods reflecting its role, like :meth:`degree`
        for computing the degree of an element.
    
        EXAMPLES:
    
        Since this class inherits from
        :class:`CombinatorialFreeModuleElement
        <sage.combinat.free_module.CombinatorialFreeModuleElement>`,
        elements can be used as iterators, and there are other useful
        methods::

            sage: c = Sq(5).antipode(); c
            Sq(2,1) + Sq(5)
            sage: for mono, coeff in c: print coeff, mono
            1 (5,)
            1 (2, 1)
            sage: c.monomial_coefficients()
            {(5,): 1, (2, 1): 1}
            sage: c.monomials()
            [Sq(2,1), Sq(5)]
            sage: c.support()
            [(2, 1), (5,)]

        See the documentation for this module (type
        ``sage.algebras.steenrod.steenrod_algebra?``) for more
        information about elements of the Steenrod algebra.
        """
        def prime(self):
            """
            The prime associated to self.
    
            EXAMPLES::
    
                sage: a = SteenrodAlgebra().Sq(3,2,1)
                sage: a.prime()
                2
                sage: a.change_basis('adem').prime()
                2
                sage: b = SteenrodAlgebra(p=7).basis(36)[0]
                sage: b.prime()
                7
                sage: SteenrodAlgebra(p=3, basis='adem').one().prime()
                3
            """
            return self.base_ring().characteristic()

        def basis_name(self):
            """
            The basis name associated to self.
    
            EXAMPLES::
    
                sage: a = SteenrodAlgebra().Sq(3,2,1)
                sage: a.basis_name()
                'milnor'
                sage: a.change_basis('adem').basis_name()
                'serre-cartan'
                sage: a.change_basis('wood____y').basis_name()
                'woody'
                sage: b = SteenrodAlgebra(p=7).basis(36)[0]
                sage: b.basis_name()
                'milnor'
                sage: a.change_basis('adem').basis_name()
                'serre-cartan'
            """
            return self.parent().prefix()

        def is_homogeneous(self):
            """
            Return True iff this element is homogeneous.
    
            EXAMPLES::
    
                sage: (Sq(0,0,1) + Sq(7)).is_homogeneous()
                True
                sage: (Sq(0,0,1) + Sq(2)).is_homogeneous()
                False
            """
            monos = self.support()
            if len(monos) <= 1:
                return True
            degree = None
            deg = self.parent().degree_on_basis
            for mono in monos:
                if degree is None:
                    degree = deg(mono)
                elif deg(mono) != degree:
                    return False
            return True

        def degree(self):
            r"""
            The degree of self.
    
            The degree of `\text{Sq}(i_1,i_2,i_3,...)` is
    
            .. math::
    
                i_1 + 3i_2 + 7i_3 + ... + (2^k - 1) i_k + ....
    
            At an odd prime `p`, the degree of `Q_k` is `2p^k - 1` and the
            degree of `\mathcal{P}(i_1, i_2, ...)` is
    
            .. math::
    
                \sum_{k \geq 0} 2(p^k - 1) i_k.
    
            ALGORITHM: If :meth:`is_homogeneous` returns True, call
            :meth:`SteenrodAlgebra_generic.degree_on_basis` on the leading
            summand.
    
            EXAMPLES::
    
                sage: Sq(0,0,1).degree()
                7
                sage: (Sq(0,0,1) + Sq(7)).degree()
                7
                sage: (Sq(0,0,1) + Sq(2)).degree()
                Traceback (most recent call last):
                ...
                ValueError: Element is not homogeneous.
    
                sage: A11 = SteenrodAlgebra(p=11)
                sage: A11.P(1).degree()
                20
                sage: A11.P(1,1).degree()
                260
                sage: A11.Q(2).degree()
                241
    
            TESTS::
    
                sage: all([x.degree() == 10 for x in SteenrodAlgebra(basis='woody').basis(10)])
                True
                sage: all([x.degree() == 11 for x in SteenrodAlgebra(basis='woodz').basis(11)])
                True
                sage: all([x.degree() == x.milnor().degree() for x in SteenrodAlgebra(basis='wall').basis(11)])
                True
                sage: a = SteenrodAlgebra(basis='pst').basis(10)[0]
                sage: a.degree() == a.change_basis('arnonc').degree()
                True
                sage: b = SteenrodAlgebra(basis='comm').basis(12)[1]
                sage: b.degree() == b.change_basis('adem').change_basis('arnona').degree()
                True
                sage: all([x.degree() == 9 for x in SteenrodAlgebra(basis='comm').basis(9)])
                True
                sage: all([x.degree() == 8 for x in SteenrodAlgebra(basis='adem').basis(8)])
                True
                sage: all([x.degree() == 7 for x in SteenrodAlgebra(basis='milnor').basis(7)])
                True
                sage: all([x.degree() == 24 for x in SteenrodAlgebra(p=3).basis(24)])
                True
                sage: all([x.degree() == 40 for x in SteenrodAlgebra(p=5, basis='serre-cartan').basis(40)])
                True
            """
            if len(self.support()) == 0:
                raise ValueError("The zero element does not have a well-defined degree.")
            try:
                assert self.is_homogeneous()
                return self.parent().degree_on_basis(self.leading_support())
            except AssertionError:
                raise ValueError("Element is not homogeneous.")

        def milnor(self):
            """
            Return this element in the Milnor basis; that is, as an
            element of the appropriate Steenrod algebra.
    
            This just calls the method
            :meth:`SteenrodAlgebra_generic.milnor`.
    
            EXAMPLES::
    
                sage: Adem = SteenrodAlgebra(basis='adem')
                sage: a = Adem.basis(4)[1]; a
                Sq^3 Sq^1
                sage: a.milnor()
                Sq(1,1)
            """
            A = self.parent()
            return A.milnor(self)

        def change_basis(self, basis='milnor'):
            r"""
            Representation of element with respect to basis.
    
            INPUT:
    
            - ``basis`` - string, basis in which to work.
    
            OUTPUT: representation of self in given basis
    
            The choices for ``basis`` are:
    
            - 'milnor' for the Milnor basis.
            - 'serre-cartan', 'serre_cartan', 'sc', 'adem', 'admissible'
              for the Serre-Cartan basis.
            - 'wood_y' for Wood's Y basis.
            - 'wood_z' for Wood's Z basis.
            - 'wall' for Wall's basis.
            - 'wall_long' for Wall's basis, alternate representation
            - 'arnon_a' for Arnon's A basis.
            - 'arnon_a_long' for Arnon's A basis, alternate representation.
            - 'arnon_c' for Arnon's C basis.
            - 'pst', 'pst_rlex', 'pst_llex', 'pst_deg', 'pst_revz' for
              various `P^s_t`-bases.
            - 'comm', 'comm_rlex', 'comm_llex', 'comm_deg', 'comm_revz'
              for various commutator bases.
            - 'comm_long', 'comm_rlex_long', etc., for commutator bases,
              alternate representations.
            
            See documentation for this module (by browsing the
            reference manual or by typing
            ``sage.algebras.steenrod.steenrod_algebra?``) for
            descriptions of the different bases.
            
            EXAMPLES::
            
                sage: c = Sq(2) * Sq(1)
                sage: c.change_basis('milnor')
                Sq(0,1) + Sq(3)
                sage: c.change_basis('serre-cartan')
                Sq^2 Sq^1
                sage: d = Sq(0,0,1)
                sage: d.change_basis('arnonc')
                Sq^2 Sq^5 + Sq^4 Sq^2 Sq^1 + Sq^4 Sq^3 + Sq^7
            """
            A = self.parent()
            return A._change_basis(self, basis)

        def _basis_dictionary(self,basis):
            r"""
            Convert self to ``basis``, returning a dictionary of terms of
            the form (mono: coeff), where mono is a monomial in the given
            basis.
    
            INPUT:
    
            - ``basis`` - string, basis in which to work
    
            OUTPUT: dictionary
    
            This just calls :meth:`change_basis` to get an element of the
            Steenrod algebra with the new basis, and then calls
            :meth:`monomial_coefficients` on this element to produce its
            dictionary representation.
    
            EXAMPLES::
    
                sage: c = Sq(2) * Sq(1)
                sage: c._basis_dictionary('milnor')
                {(0, 1): 1, (3,): 1}
                sage: c
                Sq(0,1) + Sq(3)
                sage: c._basis_dictionary('serre-cartan')
                {(2, 1): 1}
                sage: c.change_basis('serre-cartan')
                Sq^2 Sq^1
                sage: d = Sq(0,0,1)
                sage: d._basis_dictionary('arnonc')
                {(7,): 1, (2, 5): 1, (4, 3): 1, (4, 2, 1): 1}
                sage: d.change_basis('arnonc')
                Sq^2 Sq^5 + Sq^4 Sq^2 Sq^1 + Sq^4 Sq^3 + Sq^7
            
            At odd primes::
            
                sage: e = 2 * SteenrodAlgebra(3).P(1,2)
                sage: e._basis_dictionary('milnor')
                {((), (1, 2)): 2}
                sage: e
                2 P(1,2)
                sage: e._basis_dictionary('serre-cartan')
                {(0, 7, 0, 2, 0): 2, (0, 8, 0, 1, 0): 2}
                sage: e.change_basis('adem')
                2 P^7 P^2 + 2 P^8 P^1
            """
            a = self.change_basis(basis)
            return a.monomial_coefficients()

        def basis(self, basis):
            r"""
            Representation of element with respect to basis.
            
            INPUT:
    
            - ``basis`` - string, basis in which to work.
    
            OUTPUT: Representation of self in given basis
    
            .. warning::
    
                Deprecated (December 2010). Use :meth:`change_basis` instead.

            EXAMPLES::

                sage: c = Sq(2) * Sq(1)
                sage: c.basis('milnor')
                doctest:...: DeprecationWarning: (Since Sage 4.6.2) The .basis() method is deprecated.  Use .change_basis() instead.
                Sq(0,1) + Sq(3)
            """
            from sage.misc.misc import deprecation
            deprecation('The .basis() method is deprecated. Use .change_basis() instead.',
                        version='Sage 4.6.2')
            return self.change_basis(basis)

        def coproduct(self, algorithm='milnor'):
            """
            The coproduct of this element.
    
            INPUT:
    
            - ``algorithm`` -- None or a string, either 'milnor' or
              'serre-cartan' (or anything which will be converted to
              one of these by the function :func:`get_basis_name
              <sage.algebras.steenrod.steenrod_algebra_misc.get_basis_name>`).
              If None, default to 'serre-cartan' if current basis is
              'serre-cartan'; otherwise use 'milnor'.
    
            See :meth:`SteenrodAlgebra_generic.coproduct_on_basis` for
            more information on computing the coproduct.
    
            EXAMPLES::
    
                sage: a = Sq(2)
                sage: a.coproduct()
                1 # Sq(2) + Sq(1) # Sq(1) + Sq(2) # 1
                sage: b = Sq(4)
                sage: (a*b).coproduct() == (a.coproduct()) * (b.coproduct())
                True
    
                sage: c = a.change_basis('adem'); c.coproduct(algorithm='milnor')
                1 # Sq^2 + Sq^1 # Sq^1 + Sq^2 # 1
                sage: c = a.change_basis('adem'); c.coproduct(algorithm='adem')
                1 # Sq^2 + Sq^1 # Sq^1 + Sq^2 # 1
    
                sage: d = a.change_basis('comm_long'); d.coproduct()
                1 # s_2 + s_1 # s_1 + s_2 # 1
    
                sage: A7 = SteenrodAlgebra(p=7)
                sage: a = A7.Q(1) * A7.P(1); a
                Q_1 P(1)
                sage: a.coproduct()
                1 # Q_1 P(1) + P(1) # Q_1 + Q_1 # P(1) + Q_1 P(1) # 1
                sage: a.coproduct(algorithm='adem')
                1 # Q_1 P(1) + P(1) # Q_1 + Q_1 # P(1) + Q_1 P(1) # 1
            """
            A = self.parent()
            return A.coproduct(self, algorithm=algorithm)

        def excess(self):
            r"""
            Excess of element.
    
            OUTPUT: ``excess`` - non-negative integer
    
            The excess of a Milnor basis element `\text{Sq}(a,b,c,...)` is
            `a + b + c + ...`. When `p` is odd, the excess of `Q_{0}^{e_0}
            Q_{1}^{e_1} ... P(r_1, r_2, ...)` is `\sum e_i + 2 \sum r_i`.
            The excess of a linear combination of Milnor basis elements is
            the minimum of the excesses of those basis elements.
    
            See [Kra] for the proofs of these assertions.
    
            REFERENCES:
    
            - [Kra] D. Kraines, "On excess in the Milnor basis," Bull. London
              Math. Soc. 3 (1971), 363-365.
    
            EXAMPLES::
    
                sage: a = Sq(1,2,3)
                sage: a.excess()
                6
                sage: (Sq(0,0,1) + Sq(4,1) + Sq(7)).excess()
                1
                sage: [m.excess() for m in (Sq(0,0,1) + Sq(4,1) + Sq(7)).monomials()]
                [1, 5, 7]
                sage: [m for m in (Sq(0,0,1) + Sq(4,1) + Sq(7)).monomials()]
                [Sq(0,0,1), Sq(4,1), Sq(7)]
                sage: B = SteenrodAlgebra(7)
                sage: a = B.Q(1,2,5)
                sage: b = B.P(2,2,3)
                sage: a.excess()
                3
                sage: b.excess()
                14
                sage: (a + b).excess()
                3
                sage: (a * b).excess()
                17
            """
            def excess_odd(mono):
                """
                Excess of mono, where mono has the form ((s0, s1, ...), (r1, r2,
                ...)).
                
                Returns the length of the first component, since that is the number
                of factors, plus twice the sum of the terms in the second
                component.
                """
                if len(mono) == 0:
                    return 0
                else:
                    return len(mono[0]) + 2 * sum(mono[1])
    
            p = self.prime()
            a = self.milnor()
            if p == 2:
                excesses = [sum(mono) for mono in a.support()]
            else:
                excesses = [excess_odd(mono) for mono in a.support()]
            return min(excesses)

        def is_unit(self):
            """
            True if element has a nonzero scalar multiple of P(0) as a summand,
            False otherwise.
            
            EXAMPLES::
            
                sage: z = Sq(4,2) + Sq(7,1) + Sq(3,0,1)
                sage: z.is_unit()
                False
                sage: u = Sq(0) + Sq(3,1)
                sage: u == 1 + Sq(3,1)
                True
                sage: u.is_unit()
                True
                sage: A5 = SteenrodAlgebra(5)
                sage: v = A5.P(0)
                sage: (v + v + v).is_unit()
                True
            """
            return self.parent().one() in self.monomials()

        def is_nilpotent(self):
            """
            True if element is not a unit, False otherwise.
            
            EXAMPLES::
            
                sage: z = Sq(4,2) + Sq(7,1) + Sq(3,0,1)
                sage: z.is_nilpotent()
                True
                sage: u = 1 + Sq(3,1)
                sage: u == 1 + Sq(3,1)
                True
                sage: u.is_nilpotent()
                False
            """
            return not self.is_unit()

        def may_weight(self):
            r"""
            May's 'weight' of element.
    
            OUTPUT: ``weight`` - non-negative integer
    
            If we let `F_* (A)` be the May filtration of the Steenrod
            algebra, the weight of an element `x` is the integer `k` so
            that `x` is in `F_k(A)` and not in `F_{k+1}(A)`. According to
            Theorem 2.6 in May's thesis [May], the weight of a Milnor
            basis element is computed as follows: first, to compute the
            weight of `P(r_1,r_2, ...)`, write each `r_i` in base `p` as
            `r_i = \sum_j p^j r_{ij}`. Then each nonzero binary digit
            `r_{ij}` contributes `i` to the weight: the weight is
            `\sum_{i,j} i r_{ij}`. When `p` is odd, the weight of `Q_i` is
            `i+1`, so the weight of a product `Q_{i_1} Q_{i_2} ...` equals
            `(i_1+1) + (i_2+1) + ...`. Then the weight of `Q_{i_1} Q_{i_2}
            ...P(r_1,r_2, ...)` is the sum of `(i_1+1) + (i_2+1) + ...`
            and `\sum_{i,j} i r_{ij}`.
    
            The weight of a sum of Milnor basis elements is the minimum of
            the weights of the summands.
    
            When `p=2`, we compute the weight on Milnor basis elements by
            adding up the terms in their 'height' - see
            :meth:`wall_height` for documentation. (When `p` is odd, the
            height of an element is not defined.)
    
            REFERENCES:
    
            - [May]: J. P. May, "The cohomology of restricted Lie algebras and of
              Hopf algebras; application to the Steenrod algebra." Thesis,
              Princeton Univ., 1964.
    
            EXAMPLES::
    
                sage: Sq(0).may_weight()
                0
                sage: a = Sq(4)
                sage: a.may_weight()
                1
                sage: b = Sq(4)*Sq(8) + Sq(8)*Sq(4)
                sage: b.may_weight()
                2
                sage: Sq(2,1,5).wall_height()
                [2, 3, 2, 1, 1]
                sage: Sq(2,1,5).may_weight()
                9
                sage: A5 = SteenrodAlgebra(5)
                sage: a = A5.Q(1,2,4)
                sage: b = A5.P(1,2,1)
                sage: a.may_weight()
                10
                sage: b.may_weight()
                8
                sage: (a * b).may_weight()
                18
                sage: A5.P(0,0,1).may_weight()
                3
            """
            from sage.rings.infinity import Infinity
            from sage.rings.all import Integer
            p = self.prime()
            if self == 0:
                return Infinity
            elif self.is_unit():
                return 0
            elif p == 2:
                wt = Infinity
                for mono in self.milnor().monomials():
                    wt = min(wt, sum(mono.wall_height()))
                return wt
            else: # p odd
                wt = Infinity
                for (mono1, mono2) in self.milnor().support():
                    P_wt = 0
                    index = 1
                    for n in mono2:
                        P_wt += index * sum(Integer(n).digits(p))
                        index += 1
                    wt = min(wt, sum(mono1) + len(mono1) + P_wt)
                return wt

        def is_decomposable(self):
            r"""
            Return True if element is decomposable, False otherwise.
            That is, if element is in the square of the augmentation ideal,
            return True; otherwise, return False.
    
            OUTPUT: boolean
    
            EXAMPLES::
    
                sage: a = Sq(6)
                sage: a.is_decomposable()
                True
                sage: for i in range(9):
                ...       if not Sq(i).is_decomposable():
                ...           print Sq(i)
                1
                Sq(1)
                Sq(2)
                Sq(4)
                Sq(8)
                sage: A3 = SteenrodAlgebra(p=3, basis='adem')
                sage: [A3.P(n) for n in range(30) if not A3.P(n).is_decomposable()]
                [1, P^1, P^3, P^9, P^27]
    
            TESTS:
    
            These all test changing bases and printing in various bases::
    
                sage: A = SteenrodAlgebra(basis='milnor')
                sage: [A.Sq(n) for n in range(9) if not A.Sq(n).is_decomposable()]
                [1, Sq(1), Sq(2), Sq(4), Sq(8)]
                sage: A = SteenrodAlgebra(basis='wall_long')
                sage: [A.Sq(n) for n in range(9) if not A.Sq(n).is_decomposable()]
                [1, Sq^1, Sq^2, Sq^4, Sq^8]
                sage: A = SteenrodAlgebra(basis='arnona_long')
                sage: [A.Sq(n) for n in range(9) if not A.Sq(n).is_decomposable()]
                [1, Sq^1, Sq^2, Sq^4, Sq^8]
                sage: A = SteenrodAlgebra(basis='woodz')
                sage: [A.Sq(n) for n in range(20) if not A.Sq(n).is_decomposable()] # long time
                [1, Sq^1, Sq^2, Sq^4, Sq^8, Sq^16]
                sage: A = SteenrodAlgebra(basis='comm_long')
                sage: [A.Sq(n) for n in range(25) if not A.Sq(n).is_decomposable()] # long time
                [1, s_1, s_2, s_4, s_8, s_16]
            """
            return self.may_weight() > 1

        def wall_height(self):
            r"""
            Wall's 'height' of element.
    
            OUTPUT: list of non-negative integers
    
            The height of an element of the mod 2 Steenrod algebra is a
            list of non-negative integers, defined as follows: if the
            element is a monomial in the generators `\text{Sq}(2^i)`, then
            the `i^{th}` entry in the list is the number of times
            `\text{Sq}(2^i)` appears. For an arbitrary element, write it
            as a sum of such monomials; then its height is the maximum,
            ordered right-lexicographically, of the heights of those
            monomials.
    
            When `p` is odd, the height of an element is not defined.
    
            According to Theorem 3 in [Wall], the height of the Milnor
            basis element `\text{Sq}(r_1, r_2, ...)` is obtained as
            follows: write each `r_i` in binary as `r_i = \sum_j 2^j
            r_{ij}`. Then each nonzero binary digit `r_{ij}` contributes 1
            to the `k^{th}` entry in the height, for `j \leq k \leq
            i+j-1`.
    
            REFERENCES:
    
            - [Wall]: C. T. C. Wall, "Generators and relations for the Steenrod
              algebra," Ann. of Math. (2) **72** (1960), 429-444.
    
            EXAMPLES::
    
                sage: Sq(0).wall_height()
                []
                sage: a = Sq(4)
                sage: a.wall_height()
                [0, 0, 1]
                sage: b = Sq(4)*Sq(8) + Sq(8)*Sq(4)
                sage: b.wall_height()
                [0, 0, 1, 1]
                sage: Sq(0,0,3).wall_height()
                [1, 2, 2, 1]
            """
            from sage.rings.all import Integer
            if self.prime() > 2:
                raise NotImplementedError("Wall height is not defined at odd primes.")
            if self == 0 or self == 1:
                return []
            result = []
            deg = self.parent().degree_on_basis
            for r in self.milnor().support():
                h = [0]*(1 + deg(r))
                i = 1
                for x in r:
                    if x > 0:
                        for j in range(1+Integer(x).exact_log(2)):
                            if (2**j & x) != 0:
                                for k in range(j,i+j):
                                    h[k] += 1
                    i=i+1
                h.reverse()
                result = max(h, result)
            result.reverse()
            while len(result) > 0 and result[-1] == 0:
                result = result[:-1]
            return result

        def additive_order(self):
            """
            The additive order of any nonzero element of the mod p
            Steenrod algebra is p.
    
            OUTPUT: 1 (for the zero element) or p (for anything else)
    
            EXAMPLES::
    
                sage: z = Sq(4) + Sq(6) + 1
                sage: z.additive_order()
                2
                sage: (Sq(3) + Sq(3)).additive_order()
                1
            """
            if self == 0:
                return 1
            return self.prime()

class SteenrodAlgebra_mod_two(SteenrodAlgebra_generic):
    """
    The mod 2 Steenrod algebra.

    Users should not call this, but use the function
    :func:`SteenrodAlgebra` instead. See that function for extensive
    documentation. (This differs from :class:`SteenrodAlgebra_generic`
    only in that it has a method :meth:`Sq` for defining elements.)
    """
    def Sq(self, *nums):
        r"""
        Milnor element `\text{Sq}(a,b,c,...)`.

        INPUT:

        - ``a, b, c, ...`` - non-negative integers

        OUTPUT: element of the Steenrod algebra

        This returns the Milnor basis element
        `\text{Sq}(a, b, c, ...)`.

        EXAMPLES::

            sage: A = SteenrodAlgebra(2)
            sage: A.Sq(5)
            Sq(5)
            sage: A.Sq(5,0,2)
            Sq(5,0,2)

        Entries must be non-negative integers; otherwise, an error
        results.
        """
        if self.prime() == 2:
            return self.P(*nums)
        else:
            raise ValueError("Sq is only defined at the prime 2")

def SteenrodAlgebra(p=2, basis='milnor', **kwds):
    r"""
    The mod `p` Steenrod algebra

    INPUT:

    - ``p`` - positive prime integer (optional, default = 2)
    - ``basis`` - string (optional, default = 'milnor')
    - ``profile`` - a profile function in form specified below (optional, default ``None``)
    - ``truncation_type`` - 0 or `\infty` or 'auto' (optional, default 'auto')
    - ``precision`` - integer or ``None`` (optional, default ``None``)

    OUTPUT: mod `p` Steenrod algebra or one of its sub-Hopf algebras,
    elements of which are printed using ``basis``

    See below for information about ``basis``, ``profile``, etc.

    EXAMPLES:

    Some properties of the Steenrod algebra are available::

        sage: A = SteenrodAlgebra(2)
        sage: A.order()
        +Infinity
        sage: A.is_finite()
        False
        sage: A.is_commutative()
        False
        sage: A.is_noetherian()
        False
        sage: A.is_integral_domain()
        False
        sage: A.is_field()
        False
        sage: A.is_division_algebra()
        False
        sage: A.category()
        Category of graded hopf algebras with basis over Finite Field of size 2

    There are methods for constructing elements of the Steenrod
    algebra::

        sage: A2 = SteenrodAlgebra(2); A2
        mod 2 Steenrod algebra, milnor basis
        sage: A2.Sq(1,2,6)
        Sq(1,2,6)
        sage: A2.Q(3,4)  # product of Milnor primitives Q_3 and Q_4
        Sq(0,0,0,1,1)
        sage: A2.pst(2,3)  # Margolis pst element
        Sq(0,0,4)
        sage: A5 = SteenrodAlgebra(5); A5
        mod 5 Steenrod algebra, milnor basis
        sage: A5.P(1,2,6)
        P(1,2,6)
        sage: A5.Q(3,4)
        Q_3 Q_4
        sage: A5.Q(3,4) * A5.P(1,2,6)
        Q_3 Q_4 P(1,2,6)
        sage: A5.pst(2,3)
        P(0,0,25)

    You can test whether elements are contained in the Steenrod
    algebra::

        sage: w = Sq(2) * Sq(4)
        sage: w in SteenrodAlgebra(2)
        True
        sage: w in SteenrodAlgebra(17)
        False

    .. rubric:: Different bases for the Steenrod algebra:

    There are two standard vector space bases for the mod `p` Steenrod
    algebra: the Milnor basis and the Serre-Cartan basis. When `p=2`,
    there are also several other, less well-known, bases. See the
    documentation for this module (type
    ``sage.algebras.steenrod.steenrod_algebra?``) and the function
    :func:`steenrod_algebra_basis
    <sage.algebras.steenrod.steenrod_algebra_bases.steenrod_algebra_basis_>`
    for full descriptions of each of the implemented bases.

    This module implements the following bases at all primes:

    - 'milnor': Milnor basis.

    - 'serre-cartan' or 'adem' or 'admissible': Serre-Cartan basis.

    - 'pst', 'pst_rlex', 'pst_llex', 'pst_deg', 'pst_revz': various
      `P^s_t`-bases.

    - 'comm', 'comm_rlex', 'comm_llex', 'comm_deg', 'comm_revz', or
      these with '_long' appended: various commutator bases.

    It implements the following bases when `p=2`:

    - 'wood_y': Wood's Y basis.

    - 'wood_z': Wood's Z basis.

    - 'wall', 'wall_long': Wall's basis.

    - 'arnon_a', 'arnon_a_long': Arnon's A basis.

    - 'arnon_c': Arnon's C basis.

    When defining a Steenrod algebra, you can specify a basis. Then
    elements of that Steenrod algebra are printed in that basis::

        sage: adem = SteenrodAlgebra(2, 'adem')
        sage: x = adem.Sq(2,1)  # Sq(-) always means a Milnor basis element
        sage: x
        Sq^4 Sq^1 + Sq^5
        sage: y = Sq(0,1)    # unadorned Sq defines elements w.r.t. Milnor basis
        sage: y
        Sq(0,1)
        sage: adem(y)
        Sq^2 Sq^1 + Sq^3
        sage: adem5 = SteenrodAlgebra(5, 'serre-cartan')
        sage: adem5.P(0,2)
        P^10 P^2 + 4 P^11 P^1 + P^12

    If you add or multiply elements defined using different bases, the
    left-hand factor determines the form of the output::

        sage: SteenrodAlgebra(basis='adem').Sq(3) + SteenrodAlgebra(basis='pst').Sq(0,1)
        Sq^2 Sq^1
        sage: SteenrodAlgebra(basis='pst').Sq(3) + SteenrodAlgebra(basis='milnor').Sq(0,1)
        P^0_1 P^1_1 + P^0_2
        sage: SteenrodAlgebra(basis='milnor').Sq(2) * SteenrodAlgebra(basis='arnonc').Sq(2)
        Sq(1,1)

    You can get a list of basis elements in a given dimension::

        sage: A3 = SteenrodAlgebra(3, 'milnor')
        sage: A3.basis(13)
        Family (Q_1 P(2), Q_0 P(3))

    Algebras defined over different bases are not equal::

        sage: SteenrodAlgebra(basis='milnor') == SteenrodAlgebra(basis='pst')
        False

    Bases have various synonyms, and in general Sage tries to figure
    out what basis you meant::

        sage: SteenrodAlgebra(basis='MiLNOr')
        mod 2 Steenrod algebra, milnor basis
        sage: SteenrodAlgebra(basis='MiLNOr') == SteenrodAlgebra(basis='milnor')
        True
        sage: SteenrodAlgebra(basis='adem')
        mod 2 Steenrod algebra, serre-cartan basis
        sage: SteenrodAlgebra(basis='adem').basis_name()
        'serre-cartan'
        sage: SteenrodAlgebra(basis='wood---z---').basis_name()
        'woodz'

    As noted above, several of the bases ('arnon_a', 'wall', 'comm')
    have alternate, sometimes longer, representations. These provide
    ways of expressing elements of the Steenrod algebra in terms of
    the `\text{Sq}^{2^n}`.

    ::

        sage: A_long = SteenrodAlgebra(2, 'arnon_a_long')
        sage: A_long(Sq(6))
        Sq^1 Sq^2 Sq^1 Sq^2 + Sq^2 Sq^4
        sage: SteenrodAlgebra(2, 'wall_long')(Sq(6))
        Sq^2 Sq^1 Sq^2 Sq^1 + Sq^2 Sq^4
        sage: SteenrodAlgebra(2, 'comm_deg_long')(Sq(6))
        s_1 s_2 s_12 + s_2 s_4

    .. rubric:: Sub-Hopf algebras of the Steenrod algebra:

    These are specified using the argument ``profile``, along with,
    optionally, ``truncation_type`` and ``precision``.  The
    ``profile`` argument specifies the profile function for this
    algebra.  Any sub-Hopf algebra of the Steenrod algebra is
    determined by its *profile function*.  When `p=2`, this is a map `e`
    from the positive integers to the set of non-negative integers,
    plus `\infty`, corresponding to the sub-Hopf algebra dual to this
    quotient of the dual Steenrod algebra:

    .. math::

        \GF{2} [\xi_1, \xi_2, \xi_3, ...] / (\xi_1^{2^{e(1)}}, \xi_2^{2^{e(2)}}, \xi_3^{2^{e(3)}}, ...).

    The profile function `e` must satisfy the condition

    - `e(r) \geq \min( e(r-i) - i, e(i))` for all `0 < i < r`.

    This is specified via ``profile``, and optionally ``precision``
    and ``truncation_type``.  First, ``profile`` must have one of the
    following forms:

    - a list or tuple, e.g., ``[3,2,1]``, corresponding to the
      function sending 1 to 3, 2 to 2, 3 to 1, and all other integers
      to the value of ``truncation_type``.
    - a function from positive integers to non-negative integers (and
      `\infty`), e.g., ``lambda n: n+2``.
    - ``None`` or ``Infinity`` - use this for the profile function for
      the whole Steenrod algebra.

    In the first and third cases, ``precision`` is ignored.  In the
    second case, this function is converted to a tuple of length one
    less than ``precision``, which has default value 100.  The
    function is truncated at this point, and all remaining values are
    set to the value of ``truncation_type``.

    ``truncation_type`` may be 0, `\infty`, or 'auto'.  If it's
    'auto', then it gets converted to 0 in the first case above (when
    ``profile`` is a list), and otherwise (when ``profile`` is a
    function, ``None``, or ``Infinity``) it gets converted to `\infty`.

    For example, the sub-Hopf algebra `A(2)` has profile function
    ``[3,2,1,0,0,0,...]``, so it can be defined by any of the
    following::

        sage: A2 = SteenrodAlgebra(profile=[3,2,1])
        sage: B2 = SteenrodAlgebra(profile=[3,2,1,0,0]) # trailing 0's ignored
        sage: A2 == B2
        True
        sage: C2 = SteenrodAlgebra(profile=lambda n: max(4-n, 0), truncation_type=0)
        sage: A2 == C2
        True

    In the following case, the profile function is specified by a
    function and ``truncation_type`` isn't specified, so it defaults
    to `\infty`; therefore this gives a different sub-Hopf algebra::

        sage: D2 = SteenrodAlgebra(profile=lambda n: max(4-n, 0))
        sage: A2 == D2
        False
        sage: D2.is_finite()
        False
        sage: E2 = SteenrodAlgebra(profile=lambda n: max(4-n, 0), truncation_type=Infinity)
        sage: D2 == E2
        True

    The argument ``precision`` only needs to be specified if the
    profile function is defined by a function and you want to control
    when the profile switches from the given function to the
    truncation type.  For example::

        sage: D3 = SteenrodAlgebra(profile=lambda n: n, precision=3)
        sage: D3
        sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [1, 2, +Infinity, +Infinity, +Infinity, ...]
        sage: D4 = SteenrodAlgebra(profile=lambda n: n, precision=4); D4
        sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [1, 2, 3, +Infinity, +Infinity, +Infinity, ...]
        sage: D3 == D4
        False

    When `p` is odd, ``profile`` is a pair of functions `e` and `k`,
    corresponding to the quotient

    .. math::

        \GF{p} [\xi_1, \xi_2, \xi_3, ...] \otimes \Lambda (\tau_0,
        \tau_1, ...) / (\xi_1^{p^{e_1}}, \xi_2^{p^{e_2}}, ...;
        \tau_0^{k_0}, \tau_1^{k_1}, ...).

    Together, the functions `e` and `k` must satisfy the conditions

    - `e(r) \geq \min( e(r-i) - i, e(i))` for all `0 < i < r`,

    - if `k(i+j) = 1`, then either `e(i) \leq j` or `k(j) = 1` for all `i
      \geq 1`, `j \geq 0`.

    Therefore ``profile`` must have one of the following forms:

    - a pair of lists or tuples, the second of which takes values in
      the set `\{1,2\}`, e.g., ``([3,2,1,1], [1,1,2,2,1])``.

    - a pair of functions, one from the positive integers to
      non-negative integers (and `\infty`), one from the non-negative
      integers to the set `\{1,2\}`, e.g., ``(lambda n: n+2, lambda n:
      1 if n<3 else 2)``.

    - ``None`` or ``Infinity`` - use this for the profile function for
      the whole Steenrod algebra.

    You can also mix and match the first two, passing a pair with
    first entry a list and second entry a function, for instance.  The
    values of ``precision`` and ``truncation_type`` are determined by
    the first entry.

    More examples::

        sage: E = SteenrodAlgebra(profile=lambda n: 0 if n<3 else 3, truncation_type=0)
        sage: E.is_commutative()
        True

        sage: A2 = SteenrodAlgebra(profile=[3,2,1]) # the algebra A(2)
        sage: Sq(7,3,1) in A2
        True
        sage: Sq(8) in A2
        False
        sage: Sq(8) in SteenrodAlgebra().basis(8)
        True
        sage: Sq(8) in A2.basis(8)
        False
        sage: A2.basis(8)
        Family (Sq(1,0,1), Sq(2,2), Sq(5,1))

        sage: A5 = SteenrodAlgebra(p=5)
        sage: A51 = SteenrodAlgebra(p=5, profile=([1], [2,2]))
        sage: A5.Q(0,1) * A5.P(4) in A51
        True
        sage: A5.Q(2) in A51
        False
        sage: A5.P(5) in A51
        False

    For sub-Hopf algebras of the Steenrod algebra, only the Milnor
    basis or the various `P^s_t`-bases may be used. ::

        sage: SteenrodAlgebra(profile=[1,2,1,1], basis='adem')
        Traceback (most recent call last):
        ...
        NotImplementedError: For sub-Hopf algebras of the Steenrod algebra, only the Milnor basis and the pst bases are implemented.

    TESTS:

    Testing unique parents::

        sage: S0 = SteenrodAlgebra(2)
        sage: S1 = SteenrodAlgebra(2)
        sage: S0 is S1
        True
        sage: S2 = SteenrodAlgebra(2, basis='adem')
        sage: S0 is S2
        False
        sage: S0 == S2
        False
        sage: A1 = SteenrodAlgebra(profile=[2,1])
        sage: B1 = SteenrodAlgebra(profile=[2,1,0,0])
        sage: A1 is B1
        True
    """
    if p == 2:
        return SteenrodAlgebra_mod_two(p=2, basis=basis, **kwds)
    else:
        return SteenrodAlgebra_generic(p=p, basis=basis, **kwds)


def AA(n=None, p=2):
    r"""
    This returns the Steenrod algebra `A` or its sub-Hopf algebra `A(n)`.

    INPUT:

    - `n` - non-negative integer, optional (default None)
    - `p` - prime number, optional (default 2)

    OUTPUT: If `n` is None, then return the full Steenrod algebra.
    Otherwise, return `A(n)`.

    When `p=2`, `A(n)` is the sub-Hopf algebra generated by the
    elements `\text{Sq}^i` for `i \leq 2^n`.  Its profile function is
    `(n+1, n, n-1, ...)`.  When `p` is odd, `A(n)` is the sub-Hopf
    algebra generated by the elements `Q_0` and `\mathcal{P}^i` for `i
    \leq p^{n-1}`.  Its profile function is `e=(n, n-1, n-2, ...)`
    and `k=(2, 2, ..., 2)` (length `n+1`).

    EXAMPLES::

        sage: from sage.algebras.steenrod.steenrod_algebra import AA as A
        sage: A()
        mod 2 Steenrod algebra, milnor basis
        sage: A(2)
        sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [3, 2, 1]
        sage: A(2, p=5)
        sub-Hopf algebra of mod 5 Steenrod algebra, milnor basis, profile function ([2, 1], [2, 2, 2])
    """
    if n is None:
        return SteenrodAlgebra(p=p)
    if p == 2:
        return SteenrodAlgebra(p=p, profile=range(n+1, 0, -1))
    return SteenrodAlgebra(p=p, profile=(range(n, 0, -1), [2]*(n+1)))

def Sq(*nums):
    r"""
    Milnor element Sq(a,b,c,...).

    INPUT:

    -  ``a, b, c, ...`` - non-negative integers

    OUTPUT: element of the Steenrod algebra

    This returns the Milnor basis element
    `\text{Sq}(a, b, c, ...)`.

    EXAMPLES::

        sage: Sq(5)
        Sq(5)
        sage: Sq(5) + Sq(2,1) + Sq(5)  # addition is mod 2:
        Sq(2,1)
        sage: (Sq(4,3) + Sq(7,2)).degree()
        13
    
    Entries must be non-negative integers; otherwise, an error
    results.
    
    This function is a good way to define elements of the Steenrod
    algebra.
    """
    return SteenrodAlgebra(p=2).Sq(*nums)