Opened 9 years ago

Closed 8 years ago

# Bug in computation of moliens series

Reported by: Owned by: nborie critical sage-6.4 group theory moliens series Sage Combinat CC user Frédéric Chapoton Nicolas Borie N/A 74c8162 74c81623054d564d8008d6d692a4f5809a9a0c9f

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

### comment:1 Changed 9 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 9 years ago by nborie

Type: PLEASE CHANGE → defect

### comment:3 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:4 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:5 Changed 8 years ago by Frédéric 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 8 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 8 years ago by Frédéric Chapoton

Authors: → Frédéric Chapoton → u/chapoton/15817 → 6149bbdc55692816d9df2308d0c02d2028f3a37f 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 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 8 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 8 years ago by Frédéric 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 8 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 8 years ago by git

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 Frédéric Chapoton

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 nborie

Reviewers: → Nicolas Borie 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 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 8 years ago by Volker Braun

Branch: u/chapoton/15817 → 74c81623054d564d8008d6d692a4f5809a9a0c9f → fixed positive_review → closed
Note: See TracTickets for help on using tickets.