Opened 11 years ago
Last modified 10 years ago
#10052 closed enhancement
Improve the implementation of the Steenrod algebra — at Version 10
Reported by: | jhpalmieri | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.1 |
Component: | algebra | Keywords: | steenrod, notebook |
Cc: | jvkersch, niles | Merged in: | |
Authors: | John Palmieri | Reviewers: | |
Report Upstream: | N/A | Work issues: | minor docstring issues, problems with sub-Hopf algebras |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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 methodan_element
varies depending on the values ofbasis
andp
, 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
- Patch from #9370.
- trac_10052-steenrod.v3.patch.
Change History (13)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Description modified (diff)
- Keywords steenrod notebook added
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Cc jvkersch added
comment:3 follow-up: ↓ 4 Changed 11 years ago by
- Cc niles added
- Status changed from needs_review to needs_info
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?
comment:4 in reply to: ↑ 3 Changed 11 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
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.)
comment:5 Changed 11 years ago by
(I attached the same patch so I could add the note about it depending on #9370.)
comment:6 Changed 11 years ago by
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...)
comment:7 Changed 11 years ago by
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.
comment:8 follow-up: ↓ 9 Changed 11 years ago by
- Status changed from needs_review to needs_work
- Work issues set to minor docstring issues, problems with sub-Hopf algebras
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, trysage: 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 theQ_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 degreen
, 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.
comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 11 years ago by
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 theQ_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 degreen
, 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.
comment:10 in reply to: ↑ 9 Changed 11 years ago by
- Description modified (diff)
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.
patch for sagenb repo