Improve the implementation of the Steenrod algebra

[jhpalmieri]

The attached patch does several things:

• it moves the Steenrod algebra code to a subdirectory of algebras. For one thing, there are already 4 files, and for another, I hope that more will be added: several people are working on related projects.

• it reimplements the Steenrod algebra using CombinatorialFreeModule, which provides a number of conveniences: scalar multiplication is already defined, as are tensor products, etc. Then for example the antipode or the coproduct can be defined just on basis elements, and the linear extension to all elements is handled automatically.

• it implements another way of computing products, using admissible sequences and the Adem relations. This provides a good way of checking for bugs: with two completely different algorithms for computing products, one can compute the same product two ways and compare answers.

• it implements sub-Hopf algebras of the Steenrod algebra. These were classified 35 years ago, and for some applications people want to use sub-Hopf algebras rather than the whole thing.

• the TestSuite has been improved: all components now pass, whereas before, we had some failures. From the old steenrod_algebra.py:

              sage: TestSuite(A).run() # todo: fix category inheritance for elements of A
                Failure in _test_category:
                ...
                ------------------------------------------------------------
                The following tests failed: _test_category
              Failure in _test_elements
              The following tests failed: _test_elements
  

  From the new one:

              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
  

  Not only are there no failures, but there are many more executions of the suite. This yields some repetition, but the method an_element varies depending on the values of basis and p, so there are also new tests run with each execution.

Unfortunately, since the patch moves files around, it is large. It also trivially affects a few doctests in sageinspect, which means that it requires a patch to sagenb.

Apply

1. trac_10052-steenrod.rebased.patch​
2. trac_10052-sagenb.patch​

[jhpalmieri]

patch for sagenb repo

[niles]

I seem to be missing something; here's what I get after applying trac_10052-steenrod.patch​ to sage 4.6.alpha2:

sage: SteenrodAlgebra(5)
Traceback (most recent call last)
...
TypeError: __init__() got an unexpected keyword argument 'scalar_mult'

Are there other patches I should have applied?

Moreover, the notebook patch doesn't apply at all -- I don't know where the directory sagenb is, let alone the file sageinspect.py. Any ideas what I could be missing?

[jhpalmieri]

Replying to niles:

I seem to be missing something; here's what I get after applying trac_10052-steenrod.patch​ to sage 4.6.alpha2:

Oops, sorry, my fault. This patch depends on the one at #9370, so please apply that first.

Moreover, the notebook patch doesn't apply at all -- I don't know where the directory sagenb is, let alone the file sageinspect.py. Any ideas what I could be missing?

As of Sage 4.6.alpha2, this is a little complicated, but with 4.6.alpha3, you can do hg_sagenb.import_patch("...path_to_patch_file...") from within Sage to apply it. (The sagenb patch on this ticket is pretty minor, just to make some doctests pass: there are some doctests in the patched file which return the path to one of the files which implements the Steenrod algebra, and since the files got moved around, the doctests fail without the sagenb patch.)

[jhpalmieri]

depends on #9370

[jhpalmieri]

(I attached the same patch so I could add the note about it depending on #9370.)

[jhpalmieri]

Also re the sagenb patch: the patched file "sagenb/misc/sageinspect.py" is a modified version of "sage/misc/sageinspect.py", present so that sagenb can function as a standalone project, independent of the rest of Sage. So any changes to the sage file necessitate corresponding changes to the sagenb file. So without actually applying the sagenb patch, you should be able to verify that the patch looks okay. (Eventually, of course, you should apply it and run "make ptestlong" to run the sagenb tests as well as the sage ones...)

[jhpalmieri]

I just attached a new version of the patch. This should be essentially equivalent, except that the new version records the fact that various files have been renamed, and so in theory the change history for the files (like the old algebras/steenrod_algebra.py, now renamed to algebras/steenrod/steenrod_algebra.py) should remain intact. Two files (steenrod_milnor_multiplication.py and steenrod_milnor_multiplication_odd.py) were combined, and this was recorded as the first being renamed and the second removed.

[jhpalmieri]

version 2. depends on #9370

[niles]

Hi John,

I've finally had a chance to look over this patch. The functionality is really great, and I think the documentation is fantastic! I noticed a couple of minor issues, and then some larger problems related to sub-Hopf algebras; here goes:

• I really like the ​sage.misc.misc.verbose module; I just wanted to remind you about it for steenrod_algebra_bases.steenrod_basis_error_check. For a lengthy demonstration, try

  sage: set_verbose(1)
  sage: EllipticCurve('11a1').sha().an_padic(5)
  

• Two minor doctest failures; the first occurs because -1 = 10 in GF(11), and Sage prints 10; the second occurs because the way dicts are printed may vary -- to fix that one I suggest testing that the output of the function is equal to the given dict.

  sage -t  sage/algebras/steenrod/steenrod_algebra.py
  **********************************************************************
  File "/Applications/sage/devel/sage-main/sage/algebras/steenrod/steenrod_algebra.py", line 1340:
      sage: SteenrodAlgebra(p=11).Q(0,2).coproduct()
  Expected:
      1 # Q_0 Q_2 + Q_0 # Q_2 + Q_0 Q_2 # 1 - Q_2 # Q_0
  Got:
      1 # Q_0 Q_2 + Q_0 # Q_2 + Q_0 Q_2 # 1 + 10*Q_2 # Q_0
  **********************************************************************
  File "/Applications/sage/devel/sage-main/sage/algebras/steenrod/steenrod_algebra.py", line 3080:
      sage: d._basis_dictionary('arnonc')
  Expected:
      {(7,): 1, (2, 5): 1, (4, 2, 1): 1, (4, 3): 1}
  Got:
      {(7,): 1, (2, 5): 1, (4, 3): 1, (4, 2, 1): 1}
  **********************************************************************
  

• The docstring for .gens(), last sentence before EXAMPLES::, should mention the Q_n's too, since both .gen() and .ngens() mention them.

• .gen() fails for pst basis: The following returns an error:

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

• In the docstring for .milnor_multiplication_odd(), could you give a reference for Monks Maple package?

• I think the description of .homogeneous_component() is a little misleading: I expected it to return the vector space of elements of homogeneous degree n, and thus was surprised to get different answers depending on which basis I used. Of course this was clarified by the description of the algorithm, but maybe the description could be clarified.

  sage: G = SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]], basis='pst')
  sage: H = SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]])
  sage: [H[n].dimension() - G[n].dimension() for n in range(100)]
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 1, 4, 2, 0, 0, 0, 0, 0, 1, 4, 3, 0, 0, 0, 0, 0, 1, 4, 3, 0, 0, 0, 0, 0, 1, 4, 3, 0, 0, 0, 0, 0, 1, 4, 3, 0, 0, 0, 0, 0, 2, 6, 4, 0]
  

• .an_element() sometimes returns an element which may not be in sub algebra:

  sage: H = SteenrodAlgebra(profile=[1,2,1,1])
  sage: H.an_element()
  Sq(2,1)
  sage: H.an_element() in H
  False
  

• For sub algebras, .Q() should throw an error for elements not in the sub algebra (as with .P()):

  sage: H = SteenrodAlgebra(p=5, profile=[[2,1], [2,2,2]])
  sage: H.Q(4) in H
  False
  sage: H.Q(4)
  Q_4
  sage: H.Q(4).parent() is H
  True
  

• There is a problem with .antipode() for sub algebras:

  sage: A = SteenrodAlgebra(2)
  sage: A.Sq(2,1).antipode()
  Sq(2,1)
  sage: H = SteenrodAlgebra(profile=[2,2,1])
  sage: H.Sq(2,1).antipode()
  Traceback (most recent call last):
  ...
  ValueError: Element does not lie in this Steenrod algebra
  

• problems with coercion:

  sage: H.Sq(2,1) == A.Sq(2,1)
  True
  sage: H.Sq(2,1).coproduct() == A.Sq(2,1).coproduct()
  False
  
  sage: A.Sq(2,1).coproduct().parent() is A.tensor_square()
  sage: A.tensor_square()(H.Sq(2,1).coproduct())
  Traceback (most recent call last):
  ...
  NotImplementedError: 
  

• printing of elements: to be consistent with the rest of sage, perhaps multiplication should print as *:

  sage: A = SteenrodAlgebra(13)
  sage: A.an_element()
  12 Q_1 Q_3 P(2,1)
  
  sage: PolynomialRing(GF(13),'x',5).random_element()
  5*x1^2 + x0*x2 + x2*x4 - x4^2 - 5*x2
  

• it's too bad that elements do not print in a way that can be typed directly into Sage (I think I read somewhere that this should be done whenever possible). This could be fixed by allowing the user to declare Sq, P, Q as global functions (e.g. P = A.P) -- perhaps by using the .inject_variables() function -- and changing the Q_i to print as Q(i). Of course this would work for only one Steenrod algebra (or sub algebra) at a time, but would still be useful for basic testing/playing.

[jhpalmieri]

Replying to niles:

Thanks a lot for all the work and careful comments. Among other things, you've found some bugs in the code, which I think I've fixed. I'm attaching a new patch, but I'm leaving it as "needs work" while I keep looking at it to see if I can see other issues which need fixing.

• I really like the ​sage.misc.misc.verbose module; I just wanted to remind you about it for steenrod_algebra_bases.steenrod_basis_error_check.

That's a good idea; I've implemented it.

• Two minor doctest failures; the first occurs because -1 = 10 in GF(11), and Sage prints 10; the second occurs because the way dicts are printed may vary

I don't see these, on either sage.math or on OS X. What platform are you using?

• The docstring for .gens(), last sentence before EXAMPLES::, should mention the Q_n's too, since both .gen() and .ngens() mention them.

Fixed.

• .gen() fails for pst basis:

Fixed, plus a new doctest for it.

• In the docstring for .milnor_multiplication_odd(), could you give a reference for Monks Maple package?

Done, and also in milnor_multiplication().

• I think the description of .homogeneous_component() is a little misleading: I expected it to return the vector space of elements of homogeneous degree n, and thus was surprised to get different answers depending on which basis I used.

Me, too. It should give vector spaces of the same dimension regardless of the basis. This turned out to be a bug in the basis algorithm (with profile functions, I was accidentally setting a variable n inside a loop "for n in range(...)", so n was being reset in the middle of the loop, causing it to end too early). This is fixed, and I've added some tests for it, both in homogeneous_component and in steenrod_basis_error_check.

• .an_element() sometimes returns an element which may not be in sub algebra:

Fixed. If the algebra has a profile function, return 1 if the algebra is just the base field, and otherwise return its first generator. The old behavior, returning some arbitrarily chosen element, is still there for the full Steenrod algebra.

• For sub algebras, .Q() should throw an error for elements not in the sub algebra (as with .P()):

Fixed, along with a new doctest.

• There is a problem with .antipode() for sub algebras:

I don't see this one, although it may have been fixed by one of the other fixes. I've added a doctest for it anyway.

• problems with coercion:

sage: H.Sq(2,1) == A.Sq(2,1)
True
sage: H.Sq(2,1).coproduct() == A.Sq(2,1).coproduct()
False
 
sage: A.Sq(2,1).coproduct().parent() is A.tensor_square()
sage: A.tensor_square()(H.Sq(2,1).coproduct())
Traceback (most recent call last):
...
NotImplementedError: 

I don't know how to fix this: it has to do with the implementation (or lack thereof) of tensor products. I don't think it's particular to the Steenrod algebra, so I'd like to have it dealt with on another ticket.

• printing of elements: to be consistent with the rest of sage, perhaps multiplication should print as *:

I understand what you're saying, but I think that printing this way is ugly. (This was one of the reasons for #9370.) If you really want, I can change it, but I'd rather not.

• it's too bad that elements do not print in a way that can be typed directly into Sage (I think I read somewhere that this should be done whenever possible). This could be fixed by allowing the user to declare Sq, P, Q as global functions (e.g. P = A.P) -- perhaps by using the .inject_variables() function -- and changing the Q_i to print as Q(i). Of course this would work for only one Steenrod algebra (or sub algebra) at a time, but would still be useful for basic testing/playing.

This is a very interesting idea, but I don't know how to do it right now. Can inject_variables be used to define functions, not just variables? I'll think about it, but I may want to defer it to a later ticket.

[niles]

Replying to jhpalmieri:

Replying to niles:

Thanks a lot for all the work and careful comments. Among other things, you've found some bugs in the code, which I think I've fixed. I'm attaching a new patch, but I'm leaving it as "needs work" while I keep looking at it to see if I can see other issues which need fixing.

Glad to help; I'll keep looking too. For now, some continued discussion of printing and .inject_variables() . . .

• Two minor doctest failures

I don't see these, on either sage.math or on OS X. What platform are you using?

I'm using OS X, but Sage 4.5.2 for the first round of reviewing -- maybe recent changes have fixed these problems.

• problems with coercion:

I don't know how to fix this: it has to do with the implementation (or lack thereof) of tensor products. I don't think it's particular to the Steenrod algebra, so I'd like to have it dealt with on another ticket.

That sounds reasonable -- I'll try to work out the issue and put up a ticket (unless you already know what the problem is).

• printing of elements: to be consistent with the rest of sage, perhaps multiplication should print as *:

I understand what you're saying, but I think that printing this way is ugly. (This was one of the reasons for #9370.) If you really want, I can change it, but I'd rather not.

Well, I'm not sure if this is a decision that should depend solely on my opinion or yours; my thinking is that we should opt for consistency over aesthetics unless there is a really good reason not to. Every other ring in Sage prints multiplication as * -- do you have a good reason to reverse that convention for the Steenrod algebra? (As you point out, this is related to the question of whether or not #9370 is a good idea -- something I'm not sure of yet.) In particular, printing * is consistent with the way Sage requires input to be typed (although note my further comments on that topic below).

• it's too bad that elements do not print in a way that can be typed directly into Sage (I think I read somewhere that this should be done whenever possible).

After some looking, I think what I was remembering is this section of the ​interactive shell tutorial, which mentions this idea as a possible way for printing objects, but one which Sage does not enforce -- rather it suggests using un/pickling to store and retrieve objects. Nevertheless, I think printing as closely as possible to valid input is useful, especially for new users.

Can inject_variables be used to define functions, not just variables? I'll think about it, but I may want to defer it to a later ticket.

Fair enough; something like this does work for ​infinite polynomial rings:

sage: R = InfinitePolynomialRing(ZZ,'t')
sage: R
Infinite polynomial ring in t over Integer Ring
sage: R.inject_variables()
Defining t
sage: R.gens()
(t_*,)
sage: t[2]
t_2
sage: t[3]
t_3
sage: t[2]*t[3] - 4*t[11] + 8
-4*t_11 + t_3*t_2 + 8
sage: t[2]*t[3] - 4*t[11] + 8 in R
True

I think the way this is implemented is by defining a __getitem__ method for the generator, but the same should work by defining a __call__ method. (And I did notice, by the way, that the objects don't print in the same way that they have to be input.) For infinite polynomial rings, .inject_variables() is inherited from sage.structure.category_object.CategoryObject:

    def inject_variables(self, scope=None, verbose=True):
        """
        Inject the generators of self with their names into the
        namespace of the Python code from which this function is
        called.  Thus, e.g., if the generators of self are labeled
        'a', 'b', and 'c', then after calling this method the
        variables a, b, and c in the current scope will be set
        equal to the generators of self.

        NOTE: If Foo is a constructor for a Sage object with generators, and
        Foo is defined in Cython, then it would typically call
        ``inject_variables()`` on the object it creates.  E.g.,
        ``PolynomialRing(QQ, 'y')`` does this so that the variable y is the
        generator of the polynomial ring.
        """
        vs = self.variable_names()
        gs = self.gens()
        if scope is None:
           scope = globals()
        if verbose:
           print "Defining %s"%(', '.join(vs))
        for v, g in zip(vs, gs):
           scope[v] = g

So if you want to use it, you would have to re-think what is returned by .gens(), especially in the case of finitely-generated sub algebras. Of course you could make a new definition of .inject_variables(), but it's not clear this is a good idea either . . . I think this is worth a little more thought, but shouldn't derail the rest of this ticket.

[jhpalmieri]

Replying to niles:

• problems with coercion:

I don't know how to fix this: it has to do with the implementation (or lack thereof) of tensor products. I don't think it's particular to the Steenrod algebra, so I'd like to have it dealt with on another ticket.

That sounds reasonable -- I'll try to work out the issue and put up a ticket (unless you already know what the problem is).

I don't know what the ticket is, although some of the sage-combinat people probably do.

• printing of elements: to be consistent with the rest of sage, perhaps multiplication should print as *:

I understand what you're saying, but I think that printing this way is ugly. (This was one of the reasons for #9370.) If you really want, I can change it, but I'd rather not.

Well, I'm not sure if this is a decision that should depend solely on my opinion or yours; my thinking is that we should opt for consistency over aesthetics unless there is a really good reason not to. Every other ring in Sage prints multiplication as * -- do you have a good reason to reverse that convention for the Steenrod algebra?

I would interpret this another way: you include a * when you need to in order to prevent ambiguity. In a situation where you can have polynomial generators called 'xy' and 'yx' (which would be terrible choices, but anyway), you have to include * so that you you can read xy * yx properly. So you need * in a polynomial algebra, or in any algebra in which the generators have user-specified names. But for the Steenrod algebra, there are no such possibilities of ambiguity, so you don't need the *.

That's my justification, anyway.

A different way to interpret it: symbols like "Q_{0} Q_{1} P(1,3,2)" could be viewed as atomic: they are basis elements for the Steenrod algebra. So it's reasonable to print them without asterisks. Then the question is whether to insist on a * between a scalar and a basis element, which I just think looks bad, although it is mostly the convention in Sage.

A third view: the existing implementation of the Steenrod algebra doesn't use *. I haven't heard any comment about this before, so I don't think it's confused anyone so far. So for consistency :), we should keep it as is.

---

I'll keep thinking about the inject_variables issue, also. Meanwhile, I'm attaching a revised version of the v3 patch; compared to the last one, this just fixes some typos and cleans up the documentation a little. It also changes the file sage/categories/coalgebras_with_basis.py, to get rid of a warning when building the docs. This passes all tests on sage.math, and it passes selected tests on OS X and Solaris. (I haven't had time to run a full test suite on these other platforms, but tests pass on all files which I think should be affected.)

[jhpalmieri]

Replying to jhpalmieri:

I don't know what the ticket is, although some of the sage-combinat people probably do.

Sorry, I meant to say "I don't know what the issue is..."

[jhpalmieri]

For the buildbot:

apply trac_10052-steenrod.v3.patch, trac_10052-sagenb.patch

[niles]

For the buildbot:

Depends on #9370

[niles]

Replying to jhpalmieri:

I would interpret this another way: you include a * when you need to in order to prevent ambiguity. In a situation where you can have polynomial generators called 'xy' and 'yx' (which would be terrible choices, but anyway), you have to include * so that you you can read xy * yx properly. So you need * in a polynomial algebra, or in any algebra in which the generators have user-specified names. But for the Steenrod algebra, there are no such possibilities of ambiguity, so you don't need the *.

ok, fair enough

I've started looking at this again, and I get two errors trying to apply the v3 patch (sage 4.6); here are the contents of the .rej file:

--- coalgebras_with_basis.py
+++ coalgebras_with_basis.py
@@ -91,7 +91,7 @@
         @lazy_attribute
         def coproduct(self):
             """
-            If :meth:`.coproduct_on_basis` is available, construct the
+            If :meth:`coproduct_on_basis` is available, construct the
             coproduct morphism from ``self`` to ``self`` `\otimes`
             ``self`` by extending it by linearity
 
@@ -115,7 +115,7 @@
         @lazy_attribute
         def counit(self):
             """
-            If :meth:`.counit_on_basis` is available, construct the
+            If :meth:`counit_on_basis` is available, construct the
             counit morphism from ``self`` to ``self`` `\otimes`
             ``self`` by extending it by linearity

I'll keep looking at the patch, since these won't affect the functionality.

[jhpalmieri]

The patch bot can't seem to apply that patch either. I think I based this on 4.6.1.alpha2, so there must be some additional dependency. I'll try to track it down today.

[jhpalmieri]

Depends on #9370 and #8589.

(The second of these was merged into 4.6.1.alpha0.)

[jhpalmieri]

Diff between v2 and v3 (for reference only)

[jhpalmieri]

Here is a slightly modified v3 patch, fixing a little documentation and (more importantly) a bug in the validity checking for profile functions, pointed out by Bob Bruner.

[jhpalmieri]

version 3. depends on #9370

[jhpalmieri]

The "delta2to3" patch is now slightly out of date. If I have time, I'll fix this, but for now, the last line in

        if truncation_type > 0:
            k = k + [2]
        else:
            k = k + [1]

(from is_valid_profile in steenrod_algebra_misc.py) has been changed:

        if truncation_type > 0:
            k = k + [2]
        else:
            k = k + [1]*len(profile[0])

[niles]

For the buildbot:

Depends on #9370, #8589.

Apply trac_10052-steenrod.v3.patch​, trac_10052-sagenb.patch​

(p.s. I haven't forgotten about this :)

[niles]

Apply trac_10052-steenrod.v3.patch, trac_10052-sagenb.patch

[niles]

I'm ready to give this a positive review, but now (Sage 4.6.2) I'm getting a failing doctest with latex on a coproduct (note the missing 1 at the end of the latex string):

sage: A7 = SteenrodAlgebra(7)
sage: c = Sq(2).change_basis('adem').coproduct()
sage: c
1 # Sq^2 + Sq^1 # Sq^1 + Sq^2 # 1
sage: latex(c)
1 \otimes \text{Sq}^{2} + \text{Sq}^{1} \otimes \text{Sq}^{1} + \text{Sq}^{2} \otimes 

This is probably related to bugs in the code for tensor products of algebras, but I haven't been able to track down the precise problem.

[jhpalmieri]

Thanks for keeping an eye on this. The latex/coproduct bug is because of #9370, not because of anything here. I think I know how to fix it.

Meanwhile, there may be a bug in profile functions for the odd primary Steenrod algebra, so give me a few days to check it out and fix it. (I'm leaving this as "needs work" until I get it straightened out.)

[jhpalmieri]

#9370 has a positive review, and the most recent patch there fixes the coproduct bug. Meanwhile, there was a bug with profile functions. The new "v4" patch fixes it. I've also included a delta patch to help with reviewing. (The delta patch may not be completely accurate; I may have tinkered with some doctests for normalize_profile and those changes may not be recorded in the delta patch because I got lazy.)

Apply only trac_10052-steenrod.v4.patch.

Depends on #9370.

[jhpalmieri]

Diff between v3 and v4 (for reference only)

[jhpalmieri]

version 4. depends on #9370

[niles]

Patchbot: apply trac_10052-steenrod.v4.patch

[niles]

Ok, I've finally gotten back to looking at this. With the following, I'm giving this a positive review

• The patchs apply cleanly to Sage 4.7, and pass all (long) tests for me.

• The documentation builds without warning, looks good

• Complete doctest coverage

• The previous issues I noticed (comment:8) have all been addressed, as well as some others, and now I see no problems with the functionality

• The code is free from obvious inefficiencies (e.g. in memory management, error handling)

• In general, this is well-written, well-documented, and a substantial improvement!

[jdemeyer]

This needs to be rebased to sage-4.7.1.alpha2.

[jhpalmieri]

rebased to 4.7.1.alpha2