Sage: Ticket #3397: [with patch, positive review] Steenrod algebra calculations
https://trac.sagemath.org/ticket/3397
<p>
The attached patch adds files to sage.algebras to do Steenrod algebra calculations. See the files for full documentation. The only other package for this kind of thing of which I am aware is a Maple package:
</p>
<p>
<a class="ext-link" href="http://math.scranton.edu/monks/software/Steenrod/steen.html"><span class="icon"></span>http://math.scranton.edu/monks/software/Steenrod/steen.html</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/3397
Trac 1.1.6jhpalmieriWed, 11 Jun 2008 05:50:40 GMTattachment set
https://trac.sagemath.org/ticket/3397
https://trac.sagemath.org/ticket/3397
<ul>
<li><strong>attachment</strong>
set to <em>3397.patch</em>
</li>
</ul>
<p>
Steenrod algebra calculations
</p>
TicketcraigcitroSun, 15 Jun 2008 21:17:11 GMTsummary changed
https://trac.sagemath.org/ticket/3397#comment:1
https://trac.sagemath.org/ticket/3397#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Steenrod algebra calculations</em> to <em>[with patch, under review by Roed, before 6/18] Steenrod algebra calculations</em>
</li>
</ul>
TicketcraigcitroSun, 15 Jun 2008 21:25:24 GMTkeywords changed
https://trac.sagemath.org/ticket/3397#comment:2
https://trac.sagemath.org/ticket/3397#comment:2
<ul>
<li><strong>keywords</strong>
<em>editor_craigcitro</em> added
</li>
</ul>
TicketroedFri, 20 Jun 2008 03:53:40 GMTsummary changed
https://trac.sagemath.org/ticket/3397#comment:3
https://trac.sagemath.org/ticket/3397#comment:3
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, under review by Roed, before 6/18] Steenrod algebra calculations</em> to <em>[with patch, pending changes and coercion, under review by Roed, before 6/23] Steenrod algebra calculations</em>
</li>
</ul>
TicketjhpalmieriTue, 15 Jul 2008 17:49:08 GMTattachment set
https://trac.sagemath.org/ticket/3397
https://trac.sagemath.org/ticket/3397
<ul>
<li><strong>attachment</strong>
set to <em>3397-with-odd-primes.patch</em>
</li>
</ul>
TicketjhpalmieriTue, 15 Jul 2008 18:01:56 GMT
https://trac.sagemath.org/ticket/3397#comment:4
https://trac.sagemath.org/ticket/3397#comment:4
<p>
Hi David,
</p>
<p>
I don't know how far the review has gone, but I have the odd primary Steenrod algebras working now. This patch replaces the old one. There are a few other small changes, too, such as adding a 'Sq' method and a 'pst' method to the <code>SteenrodAlgebra</code> class, so you can do things like <code>A = SteenrodAlgebra(2); A.Sq(5,1)</code> to define elements. Also, there were minor fixes and some coercion issues which I've more or less straightened out -- see the discussion here:
<a class="ext-link" href="http://groups.google.com/group/sage-support/browse_frm/thread/991cc3d21feddcf4/38b6e42d29b0f3d8?lnk=gst&q=coercion#38b6e42d29b0f3d8"><span class="icon"></span>http://groups.google.com/group/sage-support/browse_frm/thread/991cc3d21feddcf4/38b6e42d29b0f3d8?lnk=gst&q=coercion#38b6e42d29b0f3d8</a>
</p>
<p>
If you've made a lot of progress on changes, etc., then ignore this, and I'll work on incorporating my changes into your version when it's ready.
</p>
<p>
If I recall our conversation from late June correctly, the main thing still to be done here is to incorporate the default basis into the definition of a Steenrod algebra, so you would say
</p>
<pre class="wiki"> A = SteenrodAlgebra(2, 'milnor')
</pre><p>
and then all elements of A will print in the Milnor basis (and similarly for other choices of basis). Then the 'basis' method (which right now just prints a string) would be rewritten to coerce the element into a <code>SteenrodAlgebra</code> with the chosen basis, hence returning an actual element, not just printing a string. I can work on this, if you don't have the time right now.
</p>
TicketjhpalmieriFri, 18 Jul 2008 15:49:10 GMT
https://trac.sagemath.org/ticket/3397#comment:5
https://trac.sagemath.org/ticket/3397#comment:5
<p>
I had some spare time, so I've made the following changes: from the file 'steenrod_algebra.py', I split off another file: 'steenrod_algebra_element.py' -- this seems to be the style in sage/algebras. I also now have the bases working as described in the previous comment.
</p>
<p>
Things still to be done: convert Milnor multiplication to Cython. There are some minor coercion issues, also, which are minor enough that they don't need to be dealt with. My previous comment has a thread describing one issue. The other is with multiplication: if you multiply an element from <code>SteenrodAlgebra(2, 'milnor')</code> with an element from <code>SteenrodAlgebra(2, 'adem')</code>, it's not clear to me how the parent of the result is determined. See this thread:
<a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_frm/thread/f223018be64680d5"><span class="icon"></span>http://groups.google.com/group/sage-devel/browse_frm/thread/f223018be64680d5</a>
</p>
<p>
I also have not implemented anything of the form
</p>
<pre class="wiki">with steenrod.basis_serre_cartan:
blah blah blah
</pre><p>
but I'm not sure how important this is. Having
</p>
<pre class="wiki">A = SteenrodAlgebra(2, 'serre_cartan')
x = Sq(2) * Sq(4)
A(x) # or A(Sq(2)) * A(Sq(4)), or A.Sq(2) * A.Sq(4)
</pre><p>
might be good enough.
</p>
<p>
I'm wondering if it is worth while defining different methods for defining elements of the Steenrod algebra, depending on the basis.
</p>
<p>
Other than that, I have some more changes in mind, but they are for some time in the distant future (certainly after this has been reviewed, probably not for a while after that): implementing some other bases at odd primes, maybe implementing sub-Hopf algebras of the Steenrod algebra.
</p>
TicketjhpalmieriFri, 18 Jul 2008 15:49:29 GMTattachment set
https://trac.sagemath.org/ticket/3397
https://trac.sagemath.org/ticket/3397
<ul>
<li><strong>attachment</strong>
set to <em>3397-2008-07-18.patch</em>
</li>
</ul>
TicketwasTue, 29 Jul 2008 21:41:30 GMTmilestone, summary changed
https://trac.sagemath.org/ticket/3397#comment:6
https://trac.sagemath.org/ticket/3397#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-3.1.1</em> to <em>sage-3.1</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, pending changes and coercion, under review by Roed, before 6/23] Steenrod algebra calculations</em> to <em>[with patch, positive review pending changes] Steenrod algebra calculations</em>
</li>
</ul>
<p>
REFEREE REPORT:
</p>
<p>
It is frickin' awesome that this code is going to be in Sage!!
</p>
<p>
Here are some comments in order to make sure the code is absolutely the best quality.
</p>
<p>
STEENROD_ALGEBRA.PY
</p>
<ul><li>At the top of streenrod_algebra.py you do this:
<pre class="wiki">r"""
Defining the mod $p$ Steenrod algebra.
AUTHORS:
- John H. Palmieri (2008-07-17: version 0.8)
This package defines the mod $p$ Steenrod algebra, some of its
properties, and ways to define elements of it. In this package,
elements in the Steenrod algebra are represented, by default, using
the Milnor basis.
</pre></li></ul><p>
Could you add a brief description here about what the Steenrod algebra is? E.g., something like in Wikipedia that says "More precisely, for a given prime number p, it is a graded algebra over the field Z/p, the integers modulo p. Briefly, it is the algebra of all stable cohomology operations for mod p singular cohomology. It is generated by the Steenrod reduced pth powers, or Steenrod squares if p=2. The requirements of calculations of homotopy groups mean that homological algebra over the Steenrod algebra must be considered."
</p>
<ul><li>It would be nice if this returned a <a class="missing wiki">NotImplementedError?</a> instead of a <a class="missing wiki">TypeError?</a>, since presumably it will get implemented when there is a more general version of Generators:
<pre class="wiki">sage: A5 = SteenrodAlgebra(5); A5
mod 5 Steenrod algebra
sage: A5.gens()
---------------------------------------------------------------------------
TypeError
</pre></li></ul><p>
</p>
<ul><li>" The following bases have been implemented in this package." I don't like the passive voice. Could you change it to: "In this package we implement the following bases:"
</li></ul><ul><li>The line
<pre class="wiki">Internal documentation:
</pre></li></ul><p>
in steenrod_algebra.py should be all caps for consistency with REFERENCES, etc.
</p>
<ul><li>The references section(s):
<pre class="wiki">REFERENCES:
[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.
[Woo] R. M. W. Wood, "Problems in the Steenrod algebra," Bull. London
Math. Soc. 30 (1998), no. 5, 449--517.
</pre></li></ul><p>
will get converted by latex to a single nasty line I think.
</p>
<ul><li>Just fyi you do not have to give me copyright at all if you don't want to.
<pre class="wiki">...
# Copyright (C) 2008 William Stein <wstein@gmail.com>
</pre></li></ul><ul><li>This seems like a bug or very bad error message to me:
<pre class="wiki">sage: adem = SteenrodAlgebra(2, 'adem')
sage: adem.gen(100)
<type 'long'>
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
/Users/was/s/devel/sage-review/sage/algebras/<ipython console> in <module>()
/Users/was/s/local/lib/python2.5/site-packages/sage/algebras/steenrod_algebra.py in gen(self, i)
381 raise ValueError, "%s is not a non-negative integer" % i
382 if self.prime == 2:
--> 383 return self.Sq(self.prime**i)
384 else:
385 if i == 0:
/Users/was/s/local/lib/python2.5/site-packages/sage/algebras/steenrod_algebra.py in Sq(self, *nums)
804 if self.prime == 2:
805 dict = {nums: 1}
--> 806 return SteenrodAlgebraElement(dict, p=2, basis=self._basis_name)
807 else:
808 raise ValueError, "Sq is only defined at the prime 2"
/Users/was/s/local/lib/python2.5/site-packages/sage/algebras/steenrod_algebra_element.py in __init__(self, poly, p, basis)
595 if p == 2:
596 # when p=2, mono is a tuple of integers
--> 597 trimmed = check_and_trim(mono)
598 if new_poly.has_key(trimmed):
599 coeff = F(poly[mono] + new_poly[trimmed])
/Users/was/s/local/lib/python2.5/site-packages/sage/algebras/steenrod_algebra_element.py in check_and_trim(nums)
391 if not (isinstance(nums[i], (Integer, int)) and nums[i] >= 0):
392 print type(nums[i])
--> 393 raise ValueError, "%s is not a non-negative integer" % nums[i]
394 return nums[:index]
395
ValueError: 1267650600228229401496703205376 is not a non-negative integer
</pre></li></ul><ul><li>The doctest coverage is not 100% but needs to be:
<pre class="wiki">D-69-91-158-184:algebras was$ sage -coverage .
...
steenrod_algebra.py: 100% (25 of 25)
steenrod_algebra_bases.py: 73% (14 of 19)
steenrod_algebra_element.py: 88% (44 of 50)
steenrod_milnor_multiplication.py: 100% (2 of 2)
steenrod_milnor_multiplication_odd.py: 66% (2 of 3)
</pre></li></ul><p>
so there are maybe some missing doctests for steenrod_algebra_bases.py and steenrod_algebra_element.py and steenrod_milnor_multiplication_odd.py. (That said, GEES, you have an incredibly good number and quality of doctests overall in this package! Lauditory!)
</p>
<ul><li>I'm guessing the TeX here is wrong:
<pre class="wiki"> The element $Q_n0 Q_n1 ...$, given by specifying the subscripts.
</pre></li></ul><ul><li>It seems like you give the full text for the different Steenrod bases twice -- once at the top of the file steenrod_algebra.py and once in the function <a class="missing wiki">SteenrodAlgebra?</a>. Choose one place and refer to the other.
</li></ul><ul><li>In the source code in steenrod_algebra.py you have this:
<pre class="wiki">"""
These are the recognized basis names. For the Milnor and Serre-Cartan
bases, give a list of synonyms:
"""
_steenrod_milnor_basis_names = ['milnor']
_steenrod_serre_cartan_basis_names = ['serre_cartan', 'serre-cartan', 'sc',
'adem', 'admissible']
</pre></li></ul><p>
I think the """'d part should be replaced by comments. At least that's what I would do. This isn't really a big deal
</p>
<pre class="wiki"># These are the recognized basis names. For the Milnor and Serre-Cartan
# bases, give a list of synonyms:
</pre><p>
STEENROD_ALGEBRA_BASES.PY
</p>
<ul><li>Heh, a long list of all the bases seems to be given a third time.
</li></ul><ul><li>Otherwise this file looks good. Some of the comments about steenrod_algebra.py apply here, e.g., to the list of references.
</li></ul><p>
STEENROD_ALGEBRA_ELEMENT.PY
</p>
<ul><li>The documentation for Sq says it takes as input a "list", but it doesn't:
<pre class="wiki">sage: Sq([4,3])
---------------------------------------------------------------------------
TypeError
</pre></li></ul><p>
In fact, one would have to do
</p>
<pre class="wiki">sage: Sq(*[4,3])
Sq(4,3)
</pre><p>
or
</p>
<pre class="wiki">sage: Sq(4,3)
Sq(4,3)
</pre><p>
This could cause confusion. Clear things up in the docs or also allow a list as input.
</p>
<p>
Overall positive review pending addressing the above issues.
</p>
TicketjhpalmieriWed, 30 Jul 2008 01:48:46 GMT
https://trac.sagemath.org/ticket/3397#comment:7
https://trac.sagemath.org/ticket/3397#comment:7
<p>
Thanks for all of the comments. Two questions about doctests: if I write the gens() method so that it raises a <code>NotImplementedError</code>, how do I write a doctest for that?
</p>
<p>
Also, if I have one function nested inside another:
</p>
<pre class="wiki">def outer(x)
"""
lots of documentation here, including examples
"""
def inner(y)
return y^2 + 1
return inner(x) - 2
</pre><p>
how do I write doctests for <code>inner</code>? That is, how do I tell sage to call inner? I don't know how to access that function...
</p>
TicketwasWed, 30 Jul 2008 12:36:38 GMT
https://trac.sagemath.org/ticket/3397#comment:8
https://trac.sagemath.org/ticket/3397#comment:8
<blockquote class="citation">
<p>
Thanks for all of the comments. Two questions about doctests: if I write the gens()
method so that it raises a <a class="missing wiki">NotImplementedError?</a>, how do I write a doctest for that?
</p>
</blockquote>
<p>
Here is how to format exceptions for doctests:
</p>
<pre class="wiki">sage: a = 5
sage: a.gens()
Traceback (most recent call last):
...
AttributeError: 'sage.rings.integer.Integer' object has no attribute 'gens'
</pre><p>
If you use the notebook and click on "Text" in the upper right, it will do this automatically with exceptions.
</p>
<p>
Regarding nested functions, we should remove those from being tested by coverage. You don't have to doctest them. It is planned to change the coverage script to address this.
</p>
TicketjhpalmieriThu, 31 Jul 2008 03:24:25 GMT
https://trac.sagemath.org/ticket/3397#comment:9
https://trac.sagemath.org/ticket/3397#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/3397#comment:6" title="Comment 6">was</a>:
</p>
<blockquote class="citation">
<p>
Could you add a brief description here about what the Steenrod algebra is?
</p>
</blockquote>
<p>
I've done this.
</p>
<blockquote class="citation">
<ul><li>It would be nice if this returned a <a class="missing wiki">NotImplementedError?</a> instead of a <a class="missing wiki">TypeError?</a>, since presumably it will get implemented when there is a more general version of Generators:
</li></ul></blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<ul><li>" The following bases have been implemented in this package." I don't like the passive voice.
</li></ul></blockquote>
<p>
Changed.
</p>
<blockquote class="citation">
<ul><li>The line "Internal documentation:" in steenrod_algebra.py should be all caps for consistency with REFERENCES, etc.
</li></ul></blockquote>
<p>
Okay.
</p>
<blockquote class="citation">
<ul><li>The references section(s) will get converted by latex to a single nasty line I think.
</li></ul></blockquote>
<p>
Fixed.
</p>
<blockquote class="citation">
<ul><li>Just fyi you do not have to give me copyright at all if you don't want to.
</li></ul></blockquote>
<p>
Okay, I've take you out. (I don't care that much, but this way, people are less likely to think you wrote it, so they won't direct any technical questions about the package to you.)
</p>
<blockquote class="citation">
<ul><li>This seems like a bug or very bad error message to me:
</li></ul></blockquote>
<p>
Fixed (and included a new doctest verifying this).
</p>
<blockquote class="citation">
<ul><li>The doctest coverage is not 100% but needs to be:
</li></ul></blockquote>
<p>
Now the only missing doctests are for nested functions.
</p>
<blockquote class="citation">
<ul><li>I'm guessing the TeX here is wrong:
<pre class="wiki"> The element $Q_n0 Q_n1 ...$, given by specifying the subscripts.
</pre></li></ul></blockquote>
<p>
Fixed (along with various other little TeX problems).
</p>
<blockquote class="citation">
<ul><li>It seems like you give the full text for the different Steenrod bases twice.
</li></ul></blockquote>
<p>
Now only one time: in the docs for 'steenrod_algebra_basis', and the other places now just refer to this.
</p>
<blockquote class="citation">
<p>
"""
These are the recognized basis names. For the Milnor and Serre-Cartan
bases, give a list of synonyms:
"""
</p>
</blockquote>
<blockquote class="citation">
<p>
I think the """'d part should be replaced by comments. At least that's what I would do. This isn't really a big deal
</p>
</blockquote>
<p>
Done
</p>
<blockquote class="citation">
<p>
STEENROD_ALGEBRA_ELEMENT.PY
</p>
</blockquote>
<blockquote class="citation">
<ul><li>The documentation for Sq says it takes as input a "list", but it doesn't:
</li></ul></blockquote>
<p>
Fixed the documentation.
</p>
<blockquote class="citation">
<p>
Overall positive review pending addressing the above issues.
</p>
</blockquote>
<p>
Other changes: miscellaneous rewordings and TeX fixes in the documentation, and I added a few INPUT and OUTPUT blocks where they were missing before. I now have a doc patch which inserts relevant sections into the reference manual, and running this through the reference manual helped me to find various TeX errors. I found one pretty serious bug in steenrod_algebra_bases.convert_to_milnor_matrix, and fixed that. (The only other changes in the actual code, as opposed to the documentation: (1) I found one little function which I had written twice, once in the elements file and once in the bases file, so now I just have one and import it in the other. (2) In steenrod_algebra_bases, I was using a @memoize decorator, but it was messing up my docstrings, so I now do the memoization by hand, by explicitly defining dictionaries in which to cache things.)
</p>
TicketjhpalmieriThu, 31 Jul 2008 03:24:58 GMTattachment set
https://trac.sagemath.org/ticket/3397
https://trac.sagemath.org/ticket/3397
<ul>
<li><strong>attachment</strong>
set to <em>3397-2008-07-30-doc.patch</em>
</li>
</ul>
<p>
doc patch: add Steenrod algebra stuff to reference manual
</p>
TicketjhpalmieriThu, 31 Jul 2008 03:25:33 GMTattachment set
https://trac.sagemath.org/ticket/3397
https://trac.sagemath.org/ticket/3397
<ul>
<li><strong>attachment</strong>
set to <em>3397-2008-07-30-main.patch</em>
</li>
</ul>
<p>
new version of Steenrod algebra package, incorporating changes suggested by was
</p>
TicketwasSun, 10 Aug 2008 04:27:02 GMTattachment set
https://trac.sagemath.org/ticket/3397
https://trac.sagemath.org/ticket/3397
<ul>
<li><strong>attachment</strong>
set to <em>sage-3397-apply_after-3397-2008-07-30-main.patch</em>
</li>
</ul>
TicketwasSun, 10 Aug 2008 04:45:53 GMTsummary changed
https://trac.sagemath.org/ticket/3397#comment:10
https://trac.sagemath.org/ticket/3397#comment:10
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, positive review pending changes] Steenrod algebra calculations</em> to <em>[with patch, positive review] Steenrod algebra calculations</em>
</li>
</ul>
<p>
Excellent. Positive review. This is ready to go in!
</p>
<p>
I added a small patch that changes LaTeX to latex, and fixes a few latex typos.
</p>
<p>
Mabshoff, to apply this apply:
</p>
<ul><li>3397-2008-07-30-doc.patch
</li><li>3397-2008-07-30-main.patch
</li><li>sage-3397-apply_after-3397-2008-07-30-main.patch
</li></ul>
TicketmabshoffSun, 10 Aug 2008 08:59:00 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/3397#comment:11
https://trac.sagemath.org/ticket/3397#comment:11
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Merged the above patches as William suggested in Sage 3.1.alpha1
</p>
Ticket