#14542: Implement arithmetic product of cycle index series
----------------------------------------+-----------------------------------
Reporter: agd | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Keywords: species, cycle index | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
----------------------------------------+-----------------------------------
Comment (by agd):
Replying to [comment:4 darij]:
Thanks again for your review! I've had a chance now to go back and look
over your comments more closely.
> line 602: "g" should be inside double backticks.
Fixed.
> line 620: Where does the "1 +" come from? Is there a regular octopus on
0 vertices? (I don't think so.)
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.
> line 623: xrange will be deprecated in Python 3.0; just saying.
Since the numbers involved here are small, just using range instead won't
hurt anything, so I've switched it over.
> 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
> - this operation on partitions,
> - the Maia-Mendez operation on polynomials, and
> - the operation on symmetric functions that you have actually
implemented.
> (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} ....)
>
> About your implementation of {{{arith_prod_of_partitions}}}: 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.
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.
> line 685: I disagree with this, as on line 620.
Also fixed.
> line 690: Why do you put a p.zero() after res? (I'm new to the
CycleIndexSeries class, so maybe it's important...)
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.
> 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_\lambda \boxdot p_\mu = \prod_{i,j} p_{\lcm(\lambda_i,
\lambda_j)}^{\gcd(\lambda_i, \lambda_j)}
>
> 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
http://mathoverflow.net/questions/120924/is-the-renormalized-third-
comultiplication-on-mathbfsymm-integral as well?
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.
> **EDIT:** This patch made me aware that I have no idea what the
{{{sum_generator}}} method in {{{sage/combinat/species/series.py}}} does.
Is it possible to have a docstring for it that actually explains its
behavior? The examples given only confuse me.
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
LazyPowerSeries by adding over an infinite iterable of "generators", but
the details are buried deep in Stream and LazyPowerSeries.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14542#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
