Opened 9 years ago
Closed 8 years ago
#15817 closed defect (fixed)
Bug in computation of moliens series
Reported by:  nborie  Owned by:  

Priority:  critical  Milestone:  sage6.4 
Component:  group theory  Keywords:  moliens series 
Cc:  Sage Combinat CC user  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Nicolas Borie 
Report Upstream:  N/A  Work issues:  
Branch:  74c8162 (Commits, GitHub, GitLab)  Commit:  74c81623054d564d8008d6d692a4f5809a9a0c9f 
Dependencies:  Stopgaps: 
Description
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.
Change History (15)
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
Type:  PLEASE CHANGE → defect 

comment:3 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:4 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:5 Changed 8 years ago by
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.
comment:6 Changed 8 years ago by
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 restatus 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 ...)
comment:7 Changed 8 years ago by
Authors:  → Frédéric Chapoton 

Branch:  → u/chapoton/15817 
Commit:  → 6149bbdc55692816d9df2308d0c02d2028f3a37f 
Status:  new → needs_review 
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

comment:8 Changed 8 years ago by
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.
comment:9 Changed 8 years ago by
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.
comment:10 Changed 8 years ago by
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 (1x)**5
Maybe the current algo only work for groups with no fixed points ?
comment:11 Changed 8 years ago by
> 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 coinvariant 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.
comment:12 Changed 8 years ago by
Commit:  6149bbdc55692816d9df2308d0c02d2028f3a37f → 74c81623054d564d8008d6d692a4f5809a9a0c9f 

Branch pushed to git repo; I updated commit sha1. New commits:
74c8162  trac #15817 taking care of lost fixed points

comment:13 Changed 8 years ago by
Everything works now. I have taken care of the missing fixed points, that are excluded by Gap
from the NaturalCharacter
.
comment:14 Changed 8 years ago by
Reviewers:  → Nicolas Borie 

Status:  needs_review → positive_review 
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 gittrac).
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.
comment:15 Changed 8 years ago by
Branch:  u/chapoton/15817 → 74c81623054d564d8008d6d692a4f5809a9a0c9f 

Resolution:  → fixed 
Status:  positive_review → closed 
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 :