Opened 8 years ago

Closed 7 years ago

#15817 closed defect (fixed)

Bug in computation of moliens series

Reported by: nborie Owned by:
Priority: critical Milestone: sage-6.4
Component: group theory Keywords: moliens series
Cc: sage-combinat 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:

Status badges

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 8 years ago by nborie

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.

comment:2 Changed 8 years ago by nborie

  • Type changed from PLEASE CHANGE to defect

comment:3 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 7 years ago by chapoton

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 7 years ago by nborie

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 ...)

comment:7 Changed 7 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/15817
  • Commit set to 6149bbdc55692816d9df2308d0c02d2028f3a37f
  • Status changed from new to 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:

6149bbdtrac #15817 better code for Molien series

comment:8 Changed 7 years ago by nborie

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 7 years ago by nborie

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 7 years ago by chapoton

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 ?

comment:11 Changed 7 years ago by nborie

--> 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.

comment:12 Changed 7 years ago by git

  • Commit changed from 6149bbdc55692816d9df2308d0c02d2028f3a37f to 74c81623054d564d8008d6d692a4f5809a9a0c9f

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

74c8162trac #15817 taking care of lost fixed points

comment:13 Changed 7 years ago by chapoton

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

comment:14 Changed 7 years ago by nborie

  • Reviewers set to Nicolas Borie
  • Status changed from needs_review to 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 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.

comment:15 Changed 7 years ago by vbraun

  • Branch changed from u/chapoton/15817 to 74c81623054d564d8008d6d692a4f5809a9a0c9f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.