Bug in computation of moliens series

[sagetrac-nborie]

Using a new algorithm from the hells, I try to check my results with the current implementation of Moliens series... And I fall on this

sage: G = PermutationGroup([[(1,2,3,4)]])
sage: S4 = SymmetricGroup(4)
sage: secondary_enumeration_polynomial(G)
q^5 + 2*q^4 + q^3 + q^2 + 1
sage: G.molien_series() / S4.molien_series()
x^5 + 2*x^4 + x^3 + x^2 + 1
sage: G = PermutationGroup([[(1,2)],[(3,4)]])
sage: secondary_enumeration_polynomial(G)
q^4 + q^3 + 2*q^2 + q + 1
sage: G.molien_series() / S4.molien_series()
-x^5 - x^3 + x^2 + 1

secondary_enumeration_polynomial is my new function (which I hope, compute the degree of secondary invariants polynomial associated to the symmetric polynomial as primary invariants)... The quotient of the two series MUST BE a polynomial with positive coefficients since the theory says that for any subgroup G of S_n, the ring of invariant under the action of G is a free module over the ring of symmetric polynomials.

CC: @sagetrac-sage-combinat

Component: group theory

Keywords: moliens series

Author: Frédéric Chapoton

Branch/Commit: 74c8162

Reviewer: Nicolas Borie

Issue created by migration from https://trac.sagemath.org/ticket/15817

[sagetrac-nborie]

comment:1

I precise that, in first approximation, my feeling is that the method moliens_series returns wrong result for non transitive group...

I am also very sorry to not taking care of this bug but :

• I really don't know the pieces of Gap which are used to compute moliens_series (or I don't understand the source code of the method in other words...)
• My another approach is for sure not so efficient compare to that Gap probably provide and depends on very large pieces of personal and drafty code I only wrote for personal research.

[fchapoton]

comment:5

The problem may come from the fact that the GAP function ConstituentsOfCharacter does not return the decomposition into irreducible characters, but only the set of irreducible characters that appear in the decomposition. In other words, it forgets the multiplicities.

[sagetrac-nborie]

comment:6

Thanks you for this pointer, that's probably a nice first point to investigate.

I also admit on my side that I am not on the way to fix that. Also, this ticket is not a defect on my point of view (Yeah, I wrongly opened it...) since :

• One can re-status this ticket to enhancement since one can want to add the Moliens series for non transitive group. That would constitute a new enhancement.
• The documentation (when you write it before opening ticket, as I should do!!!!!!!) tells clearly :

Returns the Molien series of a transitive permutation group.

So, the only things one can do to prevent dummy user to open ticket is to add a check that make the call explicitly crashing. I worngly opened this ticket since that works :

sage: G = PermutationGroup([[(1,2)],[(3,4)]])
sage: G.molien_series()
1/(-x^5 + x^4 + 2*x^3 - 2*x^2 - x + 1)

Perhaps a check making that would be fine :

sage: G = PermutationGroup([[(1,2)],[(3,4)]])
sage: G.molien_series()
Traceback :
...
Valuerror : G = (bla bla bla) must be a transitive group. (please implement me if you can for the general case ...)

[fchapoton]

Author: Frédéric Chapoton

[fchapoton]

Commit: 6149bbd

[fchapoton]

comment:7

Here is a git branch, where I have removed the useless call to Constituents.

could you please check that it works in more complicated cases ?

---

New commits:

6149bbd

trac #15817 better code for Molien series

[fchapoton]

Branch: u/chapoton/15817

[sagetrac-nborie]

comment:8

Thanks you very much !

I try to do this very shortly. Today is for me correction day since the second session of last exams were this last week. I am downloading the last source, I will compile this evening and review that tomorrow... I will test it on my large collection of data.

[sagetrac-nborie]

comment:9

Hello,

I am terribly sorry but I REALLY NEED more sage days to review that. For the math review, I am OK with the fix but my computer is in a state (severals gcc version in concurrence...) in which I do not manage to build sage from source. I manage to upgrade a Sage 6.2.beta7 to Sage 6.3 but a git trac checkout 15817 make this upgrade broken... I need to visit Florent and Nicolas to get help with git and sage (or perhaps I need to reinstall a clear Linux system...). Sorry.

Here is 3 typical tests (quotient of Moliens series by the Hilbert series of the ring of symmetric polynomials) which I engage myself to be true math results :

sage: load("invariants.py")
sage: G = PermutationGroup([[(1,2,3)], [(5,6)]])
sage: secondary_enumeration_polynomial(G)
q^14 + 2*q^13 + 4*q^12 + 7*q^11 + 10*q^10 + 13*q^9 + 15*q^8 + 16*q^7 + 15*q^6 + 13*q^5 + 10*q^4 + 7*q^3 + 4*q^2 + 2*q + 1
sage: G = PermutationGroup([[(1,2,3)], [(2,3,4)], [(5,6)]])
sage: secondary_enumeration_polynomial(G)
q^14 + q^13 + 2*q^12 + 2*q^11 + 3*q^10 + 2*q^9 + 3*q^8 + 2*q^7 + 3*q^6 + 2*q^5 + 3*q^4 + 2*q^3 + 2*q^2 + q + 1
sage: G = PermutationGroup([[(5,)]])
sage: secondary_enumeration_polynomial(G)
q^10 + 4*q^9 + 9*q^8 + 15*q^7 + 20*q^6 + 22*q^5 + 20*q^4 + 15*q^3 + 9*q^2 + 4*q + 1

I will stay around but if someone can REALLY try the branch on a working sage install, it will be better.

[fchapoton]

comment:10

First one does not work.

Second one does work correctly.

The third example does not work. This is the trivial group.

sage: G = PermutationGroup([[(5,)]])
sage: G
Permutation Group with generators [()]
sage: G.cardinality()
1
sage: G.molien_series()
0

which does not look correct to me, should be (1-x)**5

Maybe the current algo only work for groups with no fixed points ?

[sagetrac-nborie]

comment:11

--> Maybe the current algo only work for groups with no fixed points ?

Yes, I think that is why the last code was restricted to transitive group. Anyway, the Moliens series is WELL defined for a finite group of matrices. So, for the trivial group, it depends how you see it as a group of matrices.

Here, my PermutationGroup([[(5,)]]) forces to see it as a subgroup of the symmetric group of order 5 and my result correspond exactly to the q analogue of n! for n=5 (which give the dimension degree by degree of the co-invariant of S_5)

sage: G = PermutationGroup ([[(5,)]])
sage: secondary_enumeration_polynomial(G)
q^10 + 4*q^9 + 9*q^8 + 15*q^7 + 20*q^6 + 22*q^5 + 20*q^4 + 15*q^3 + 9*q^2 + 4*q + 1
sage: from sage.combinat.q_analogues import q_factorial
sage: q_factorial(5)
q^10 + 4*q^9 + 9*q^8 + 15*q^7 + 20*q^6 + 22*q^5 + 20*q^4 + 15*q^3 + 9*q^2 + 4*q + 1

My last one example should be check with

sage: G = PermutationGroup([[(5,)]])
sage: G.degree()
5
sage: G.molien_series() / SymmetricGroup(5).molien_series()
.....

If I remember correctly, there are some other place in Sage in which fixed point did produce problems.

[sagetrac-git]

Changed commit from 6149bbd to 74c8162

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

74c8162

trac #15817 taking care of lost fixed points

[fchapoton]

comment:13

Everything works now. I have taken care of the missing fixed points, that are excluded by Gap from the NaturalCharacter.

[sagetrac-nborie]

Reviewer: Nicolas Borie

[sagetrac-nborie]

comment:14

I reinstalled a fresh Ubuntu 2 days ago... I build a fresh sage install and now I am able to set it to positive review. Volker was right with my Sage problem install (I had several GCC dev versions installed in concurrence...). I also have to hit myself for noting suggestions of improvement of the documentation around git in Sage (and git-trac).

Thanks you very much for this fix. It was IMHO a silent but dangerous bug (which made me believe some hours that my last 3 months of research works was good for the trash...). This is a not a so much complicated fix but I know the cost of searching GAP doc and how things works around permutation group.

[vbraun]

Changed branch from u/chapoton/15817 to 74c8162