Sage: Ticket #14542: Implement arithmetic product of cycle index series
https://trac.sagemath.org/ticket/14542
<p>
In a 2008 paper (see below), Maia and Méndez define an operation on combinatorial species which they dub the "arithmetic product". This operation corresponds to a nice combinatorial operation: the arithmetic product F⊡G corresponds to the species of "F-assemblies of cloned G-structures", which are structures of the partitional composite species F∘G with the additional requirement that all the G-structures be isomorphic.
</p>
<p>
As shown in the paper, the cycle index of the arithmetic product F⊡G can be computed in terms of the cycle indices of the species F and G. The attached patch adds code to calculate the result of this operation. It includes a doctest which verifies a nontrivial computation related to the species of "regular octopuses".
</p>
<ul><li>Maia, Manuel and Méndez, Miguel. On the arithmetic product of combinatorial species. 1 February 2008. <a class="ext-link" href="http://arxiv.org/abs/math/0503436"><span class="icon"></span>http://arxiv.org/abs/math/0503436</a>
</li></ul><p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14542/trac_14542_cycle_index_arithmetic_product.patch" title="Attachment 'trac_14542_cycle_index_arithmetic_product.patch' in Ticket #14542">trac_14542_cycle_index_arithmetic_product.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14542/trac_14542_cycle_index_arithmetic_product.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14542/trac_14542-review-dg.patch" title="Attachment 'trac_14542-review-dg.patch' in Ticket #14542">trac_14542-review-dg.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14542/trac_14542-review-dg.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14542
Trac 1.1.6agdMon, 06 May 2013 20:45:34 GMTstatus, description changed
https://trac.sagemath.org/ticket/14542#comment:1
https://trac.sagemath.org/ticket/14542#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14542?action=diff&version=1">diff</a>)
</li>
</ul>
TicketdarijWed, 15 May 2013 04:43:15 GMT
https://trac.sagemath.org/ticket/14542#comment:2
https://trac.sagemath.org/ticket/14542#comment:2
<p>
Huh -- can you explain the very first edit in the patch? This looks like an inadvertent page-down or a case of trying to use search but forgetting to press Ctrl+F...
</p>
TicketagdThu, 16 May 2013 15:10:41 GMT
https://trac.sagemath.org/ticket/14542#comment:3
https://trac.sagemath.org/ticket/14542#comment:3
<p>
Yikes! Sorry about that. I've replaced the patch with a version without that line.
</p>
<p>
Thanks for looking it over!
</p>
TicketdarijSat, 08 Jun 2013 09:17:58 GMT
https://trac.sagemath.org/ticket/14542#comment:4
https://trac.sagemath.org/ticket/14542#comment:4
<p>
line 602: "g" should be inside double backticks.
</p>
<p>
line 620: Where does the "1 +" come from? Is there a regular octopus on 0 vertices? (I don't think so.)
</p>
<p>
line 623: xrange will be deprecated in Python 3.0; just saying.
</p>
<p>
line 643: Please explain what the arithmetic product of partition is supposed to mean. The Maia-Mendez paper defines the arithmetic product of polynomials; as far as I understand, by the arithmetic product of two partitions \lambda and \mu you mean the partition obtained by writing down gcd(\lambda_i, \mu_j) times the integer lcm(\lambda_i, \mu_j) for every i and every j, and then sorting the resulting sequence in nonincreasing order. That's fine, but you should clarify the relation between
</p>
<ul><li>this operation on partitions,
</li><li>the Maia-Mendez operation on polynomials, and
</li><li>the operation on symmetric functions that you have actually implemented.
</li></ul><p>
(You are interpreting the x_i of Maia-Mendez as the i-th power sum, as far as I understand, and the partition \lambda corresponds to the product p_\lambda = p_{\lambda_1} p_{\lambda_2} ....)
</p>
<p>
About your implementation of <code>arith_prod_of_partitions</code>: I'm not sure how fast it is. It computes each lcm and each gcd very often (maxval times), whereas the definition I gave would only have to compute it once. On the other hand, the definition I gave requires sorting (or, better, insort) and probably handles repeated entries suboptimally.
</p>
<p>
line 685: I disagree with this, as on line 620.
</p>
<p>
line 690: Why do you put a p.zero() after res? (I'm new to the <a class="missing wiki">CycleIndexSeries?</a> class, so maybe it's important...)
</p>
<p>
On another note rather unrelated to Sage: The species viewpoint on the arithmetic product shows that the arithmetic product on the ring of symmetric functions (the one given by
</p>
<p>
p_\lambda \boxdot p_\mu = \prod_{i,j} p_{\lcm(\lambda_i, \mu_j)}<sup>{\gcd(\lambda_i, \mu_j)}
</sup></p>
<p>
for all partitions \lambda and \mu) is defined over the integers, not just over the rationals (despite the p_\lambda not forming a Z-basis of Symm). Is there an algebraic proof of this? It looks like a nice application of species to proving a nontrivial algebraic result. Is there a species-theoretical proof of the integrality of \Delta_3 in <a class="ext-link" href="http://mathoverflow.net/questions/120924/is-the-renormalized-third-comultiplication-on-mathbfsymm-integral"><span class="icon"></span>http://mathoverflow.net/questions/120924/is-the-renormalized-third-comultiplication-on-mathbfsymm-integral</a> as well?
</p>
<p>
<strong>EDIT:</strong> This patch made me aware that I have no idea what the <code>sum_generator</code> method in <code>sage/combinat/species/series.py</code> does. Is it possible to have a docstring for it that actually explains its behavior? The examples given only confuse me.
</p>
TicketagdSat, 08 Jun 2013 15:27:18 GMT
https://trac.sagemath.org/ticket/14542#comment:5
https://trac.sagemath.org/ticket/14542#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14542#comment:4" title="Comment 4">darij</a>:
</p>
<p>
Thanks so much for your thorough review! I'm currently in the middle of writing and grading final exams, but I'll dig into your comments and the code next week.
</p>
TicketagdSat, 15 Jun 2013 19:50:10 GMTattachment set
https://trac.sagemath.org/ticket/14542
https://trac.sagemath.org/ticket/14542
<ul>
<li><strong>attachment</strong>
set to <em>trac_14542_cycle_index_arithmetic_product.patch</em>
</li>
</ul>
<p>
Patch to implement arithmetic product of cycle indices
</p>
TicketagdSat, 15 Jun 2013 19:50:56 GMT
https://trac.sagemath.org/ticket/14542#comment:6
https://trac.sagemath.org/ticket/14542#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14542#comment:4" title="Comment 4">darij</a>:
</p>
<p>
Thanks again for your review! I've had a chance now to go back and look over your comments more closely.
</p>
<blockquote class="citation">
<p>
line 602: "g" should be inside double backticks.
</p>
</blockquote>
<p>
Fixed.
</p>
<blockquote class="citation">
<p>
line 620: Where does the "1 +" come from? Is there a regular octopus on 0 vertices? (I don't think so.)
</p>
</blockquote>
<p>
I've gotten into the rather unfortunate habit of ignoring the situation at n=0, but you're right about this one. I've updated the code to reflect this.
</p>
<blockquote class="citation">
<p>
line 623: xrange will be deprecated in Python 3.0; just saying.
</p>
</blockquote>
<p>
Since the numbers involved here are small, just using range instead won't hurt anything, so I've switched it over.
</p>
<blockquote class="citation">
<p>
line 643: Please explain what the arithmetic product of partition is supposed to mean. The Maia-Mendez paper defines the arithmetic product of polynomials; as far as I understand, by the arithmetic product of two partitions \lambda and \mu you mean the partition obtained by writing down gcd(\lambda_i, \mu_j) times the integer lcm(\lambda_i, \mu_j) for every i and every j, and then sorting the resulting sequence in nonincreasing order. That's fine, but you should clarify the relation between
</p>
<ul><li>this operation on partitions,
</li><li>the Maia-Mendez operation on polynomials, and
</li><li>the operation on symmetric functions that you have actually implemented.
</li></ul><p>
(You are interpreting the x_i of Maia-Mendez as the i-th power sum, as far as I understand, and the partition \lambda corresponds to the product p_\lambda = p_{\lambda_1} p_{\lambda_2} ....)
</p>
<p>
About your implementation of <code>arith_prod_of_partitions</code>: I'm not sure how fast it is. It computes each lcm and each gcd very often (maxval times), whereas the definition I gave would only have to compute it once. On the other hand, the definition I gave requires sorting (or, better, insort) and probably handles repeated entries suboptimally.
</p>
</blockquote>
<p>
On review, I think your way is much better; if nothing else, it results in much cleaner and (to my eye) more mathematical code. I've added comments explaining what happens in each method and how they connect to the paper.
</p>
<blockquote class="citation">
<p>
line 685: I disagree with this, as on line 620.
</p>
</blockquote>
<p>
Also fixed.
</p>
<blockquote class="citation">
<p>
line 690: Why do you put a p.zero() after res? (I'm new to the <a class="missing wiki">CycleIndexSeries?</a> class, so maybe it's important...)
</p>
</blockquote>
<p>
The sum_generator method takes finite lists, but they need to represent infinite objects, so it assumes that the last element of the list is meant to repeat. Thus, the zero.
</p>
<blockquote class="citation">
<p>
On another note rather unrelated to Sage: The species viewpoint on the arithmetic product shows that the arithmetic product on the ring of symmetric functions (the one given by
</p>
<p>
p_\lambda \boxdot p_\mu = \prod_{i,j} p_{\lcm(\lambda_i, \lambda_j)}<sup>{\gcd(\lambda_i, \lambda_j)}
</sup></p>
<p>
for all partitions \lambda and \mu) is defined over the integers, not just over the rationals (despite the p_\lambda not forming a Z-basis of Symm). Is there an algebraic proof of this? It looks like a nice application of species to proving a nontrivial algebraic result. Is there a species-theoretical proof of the integrality of \Delta_3 in <a class="ext-link" href="http://mathoverflow.net/questions/120924/is-the-renormalized-third-comultiplication-on-mathbfsymm-integral"><span class="icon"></span>http://mathoverflow.net/questions/120924/is-the-renormalized-third-comultiplication-on-mathbfsymm-integral</a> as well?
</p>
</blockquote>
<p>
I'll need to give this some more thought, but I wanted to go ahead and get the revised code up. I'm much more a combinatorialist than an algebraist, so I may not be the best person for the job, but I will definitely give it a thinking-over.
</p>
<blockquote class="citation">
<p>
<strong>EDIT:</strong> This patch made me aware that I have no idea what the <code>sum_generator</code> method in <code>sage/combinat/species/series.py</code> does. Is it possible to have a docstring for it that actually explains its behavior? The examples given only confuse me.
</p>
</blockquote>
<p>
This would definitely be helpful. My understanding of it is very limited; I seem to have managed to bend it to my will, but I'm quite far from mastery. The basic idea seems to be that it formally constructs a <a class="missing wiki">LazyPowerSeries?</a> by adding over an infinite iterable of "generators", but the details are buried deep in Stream and <a class="missing wiki">LazyPowerSeries?</a>.
</p>
TicketdarijSun, 16 Jun 2013 10:06:02 GMT
https://trac.sagemath.org/ticket/14542#comment:7
https://trac.sagemath.org/ticket/14542#comment:7
<p>
Thanks for the update! I'll have to take a closer look at it.
</p>
<p>
Meanwhile, are you sure you want those <code>assert</code>s in lines 606-607? I don't know what a typical use case of this method should be, but I can imagine applying it in a case where the <strong>base ring</strong> is not discrete (i. e., you cannot check for equality) and these <code>assert</code>s will throw a <a class="missing wiki">NotImplemented?</a>. Think of a lazy power series ring in 2 variables implemented as a lazy power series ring over a lazy power series ring; then the base ring itself is lazy and this stuff breaks. I have a similar issue with your <a class="closed ticket" href="https://trac.sagemath.org/ticket/14543" title="enhancement: Implement compositional inverses of cycle index series (closed: fixed)">#14543</a> patch. Maybe add a <code>check_input=True</code> keyword which can optionally be set to <code>False</code> to avoid these <code>assert</code>s?
</p>
<p>
In other news:
</p>
<pre class="wiki">sage: L = LazyPowerSeriesRing(QQ)
sage: L.sum_generator([L([0]),L([1])]).coefficients(10)
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: L.sum_generator([L([0]),L([1]),L([0])]).coefficients(10)
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
</pre><p>
I don't think the 1 repeats because it's the last element -- it is not, in the second case. I think it repeats because of the "sum" in "sum_generator". But like you, I don't have a clue what's going on with <code>sum_generator</code> really (I actually think I have less of a clue than you do). I'll try to ask around in Orsay...
</p>
TicketagdMon, 22 Jul 2013 03:14:38 GMTbranch set
https://trac.sagemath.org/ticket/14542#comment:8
https://trac.sagemath.org/ticket/14542#comment:8
<ul>
<li><strong>branch</strong>
set to <em>u/agd/cis_arith_prod</em>
</li>
</ul>
TicketdarijMon, 29 Jul 2013 17:54:30 GMTattachment set
https://trac.sagemath.org/ticket/14542
https://trac.sagemath.org/ticket/14542
<ul>
<li><strong>attachment</strong>
set to <em>trac_14542-review-dg.patch</em>
</li>
</ul>
<p>
review patch
</p>
TicketdarijMon, 29 Jul 2013 18:00:00 GMT
https://trac.sagemath.org/ticket/14542#comment:9
https://trac.sagemath.org/ticket/14542#comment:9
<p>
I've attached a review patch. Sorry for it taking that long; I was waiting for a thorough explanation of <code>sum_generator</code>, which now has been added to the otherwise unrelated ticket <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/13433" title="defect: Lazy power series: fix bad handling of base ring and categorification (needs_work)">#13433</a>. The explanation shows that it is *not* necessary to pad a sequence with zeroes to use <code>sum_generators</code> on it; <code>sum_generator([a,b])</code> does precisely the same as <code>sum_generator([a,b,0])</code>. But this isn't really relevant to this ticket here. What is correct that <code>L([a,b])</code> is *not* the same as <code>L([a,b,0])</code>, and the latter syntax is the correct one in most realistic cases. This has nothing to do with <code>sum_generator</code>. Sorry for the confusion.
</p>
<p>
I have added some more info to the docstring and the comments, replaced the arXiv link by the proper syntax for arXiv identifiers (hopefully correctly), improved PEP 8 compliance (it's <code>def f(n)</code>, not <code>def f (n)</code>), and replaced <code>n/d</code> for <code>n//d</code> (both do the same when d divides n, but the latter is faster). If you agree with these all, please mark this ticket as positive_review.
</p>
<p>
For the patchbot:
</p>
<p>
Apply trac_14542_cycle_index_arithmetic_product.patch trac_14542-review-dg.patch
</p>
TicketagdTue, 30 Jul 2013 03:05:09 GMT
https://trac.sagemath.org/ticket/14542#comment:10
https://trac.sagemath.org/ticket/14542#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14542#comment:9" title="Comment 9">darij</a>:
</p>
<p>
Thanks for the review!
</p>
<blockquote class="citation">
<p>
I've attached a review patch. Sorry for it taking that long; I was waiting for a thorough explanation of <code>sum_generator</code>, which now has been added to the otherwise unrelated ticket <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/13433" title="defect: Lazy power series: fix bad handling of base ring and categorification (needs_work)">#13433</a>. The explanation shows that it is *not* necessary to pad a sequence with zeroes to use <code>sum_generators</code> on it; <code>sum_generator([a,b])</code> does precisely the same as <code>sum_generator([a,b,0])</code>. But this isn't really relevant to this ticket here. What is correct that <code>L([a,b])</code> is *not* the same as <code>L([a,b,0])</code>, and the latter syntax is the correct one in most realistic cases. This has nothing to do with <code>sum_generator</code>. Sorry for the confusion.
</p>
</blockquote>
<p>
Yes, the semantics of <code>sum_generator</code> and <code>LazyPowerSeriesRing</code> are quite mysterious. I did some investigating while working on <a class="closed ticket" href="https://trac.sagemath.org/ticket/14906" title="enhancement: Implement method to expand cycle index series as symmetric function in ... (closed: fixed)">#14906</a> and learned a bit about working with them. I now think the correct way to handle this kind of construction is with <code>LazyPowerSeriesRing.term</code>, but unfortunately I am away from my build machine for the rest of the week (I'm at <a class="missing wiki">MathFest?</a>), so I won't be able to update this until I get back.
</p>
<p>
Alternately, if you'd be willing to put together a new patch, the correction is simple. The lines
</p>
<pre class="wiki"> # Build a list which has res in the nth slot and 0's before and after
# to feed to sum_generator
res_in_seq = [p.zero()]*n + [res, p.zero()]
return self.parent(res_in_seq)
</pre><p>
should be replaced by the single line
</p>
<pre class="wiki"> return self.parent.term(res, n)
</pre><blockquote class="citation">
<p>
I have added some more info to the docstring and the comments, replaced the arXiv link by the proper syntax for arXiv identifiers (hopefully correctly), improved PEP 8 compliance (it's <code>def f(n)</code>, not <code>def f (n)</code>), and replaced <code>n/d</code> for <code>n//d</code> (both do the same when d divides n, but the latter is faster). If you agree with these all, please mark this ticket as positive_review.
</p>
</blockquote>
<p>
These changes all look great. Thanks for the help! I'm not sure whether it's appropriate to mark the patch as positive_review with the issue above still outstanding, so for now I'll just say it:
</p>
<p>
Positive review!
</p>
TicketdarijTue, 30 Jul 2013 19:22:04 GMT
https://trac.sagemath.org/ticket/14542#comment:11
https://trac.sagemath.org/ticket/14542#comment:11
<p>
You want <code>self.parent().term</code>, not <code>self.parent.term</code>. The fact that <code>self.parent(res_in_seq)</code> works (and is equivalent to <code>self.parent()(res_in_seq)</code>) is due to syntactic sugar.
</p>
<p>
You are correct that <code>self.parent.term(res, n)</code> works and makes more sense, but it's also 3 times slower than <code>self.parent(res_in_seq)</code> (not sure why), so I'd keep what I've written.
</p>
TicketdarijTue, 30 Jul 2013 19:22:16 GMTstatus changed
https://trac.sagemath.org/ticket/14542#comment:12
https://trac.sagemath.org/ticket/14542#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketdarijTue, 30 Jul 2013 19:23:45 GMTdescription changed
https://trac.sagemath.org/ticket/14542#comment:13
https://trac.sagemath.org/ticket/14542#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14542?action=diff&version=13">diff</a>)
</li>
</ul>
TicketagdWed, 31 Jul 2013 02:32:42 GMT
https://trac.sagemath.org/ticket/14542#comment:14
https://trac.sagemath.org/ticket/14542#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14542#comment:11" title="Comment 11">darij</a>:
</p>
<blockquote class="citation">
<p>
You want <code>self.parent().term</code>, not <code>self.parent.term</code>. The fact that <code>self.parent(res_in_seq)</code> works (and is equivalent to <code>self.parent()(res_in_seq)</code>) is due to syntactic sugar.
</p>
</blockquote>
<p>
Whoops! This is what I get from trying to write code from a browser after a day of workshops.
</p>
<blockquote class="citation">
<p>
You are correct that <code>self.parent.term(res, n)</code> works and makes more sense, but it's also 3 times slower than <code>self.parent(res_in_seq)</code> (not sure why), so I'd keep what I've written.
</p>
</blockquote>
<p>
How strange! I'll add this to my pile of things to investigate once I get back on my feet. Using <code>res_in_seq</code> for this is fine for now, though.
</p>
<p>
Once again, thanks for the feedback and the review!
</p>
TicketjdemeyerWed, 31 Jul 2013 12:52:11 GMTmilestone changed
https://trac.sagemath.org/ticket/14542#comment:15
https://trac.sagemath.org/ticket/14542#comment:15
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
<p>
Please fill in the real names of the Authors and Reviewers.
</p>
TicketdarijWed, 31 Jul 2013 12:54:23 GMTreviewer, author set
https://trac.sagemath.org/ticket/14542#comment:16
https://trac.sagemath.org/ticket/14542#comment:16
<ul>
<li><strong>reviewer</strong>
set to <em>Darij Grinberg</em>
</li>
<li><strong>author</strong>
set to <em>Andrew Gainer-Dewar</em>
</li>
</ul>
TicketjdemeyerMon, 19 Aug 2013 06:38:20 GMT
https://trac.sagemath.org/ticket/14542#comment:17
https://trac.sagemath.org/ticket/14542#comment:17
<p>
I am assuming the patches should be merged and the git branch is just there for reference.
</p>
TicketjdemeyerTue, 20 Aug 2013 12:56:06 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14542#comment:18
https://trac.sagemath.org/ticket/14542#comment:18
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.12.beta3</em>
</li>
</ul>
TicketagdTue, 20 Aug 2013 21:24:22 GMTbranch deleted
https://trac.sagemath.org/ticket/14542#comment:19
https://trac.sagemath.org/ticket/14542#comment:19
<ul>
<li><strong>branch</strong>
<em>u/agd/cis_arith_prod</em> deleted
</li>
</ul>
Ticket