Strong generating system returns heavy error for non transitive group

[nborie]

My fault from #6647

The method from Gap work only for transitive group.

sage: G = PermutationGroup([[(3,4)]])
sage: G.strong_generating_system()
[[()], [()], [()], [()]]
sage: G.strong_generating_system(base_of_group=[3,1,2,4])
[[(), (3,4)], [()], [()], [()]]

If the first position is not moved by the permutation Group. Errors appears...

[nborie]

I added a patch which solve the problem...

I just changed the stabilizer method because the old version probably didn't point the right record of GAP for StabChain?. The new stabilizer method is based form the Schreier's subgroup lemma.

I ran some:

sage: G = SymmetricGroup(10)
sage: H = PermutationGroup([G.random_element() for i in range(randrange(1,3,1))])
sage: prod(map(lambda x : len(x), H.strong_generating_system()),1) == H.cardinality()
True

everytimes, it was ok... For the speed, the method strong_generating_system is pretty slow! But I have no better idea and I still misunderstand records from GAP.

[nborie]

I uploaded a new version. There was also a mistake in the doc... That's an ugly bug...

[nborie]

I change the title hoping someone will pass to check that...

[nthiery]

Hi Nicolas!

The tests are running.

For the record: I tried to compare the results in the new doctests with GAP, and I get the following difference:

gap> G := Group([ (1,2) (3,4), (1,2,3,4,10) ]);
Group([ (1,2)(3,4), (1,2,3,4,10) ])
gap> Stabilizer(G, 10);                        
Group([ (1,2)(3,4), (2,3,4) ])

sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]]) 
sage: G.stabilizer(10) 
Permutation Group with generators [(), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), (1,3,4), (1,4,2)] 

Well, in fact the results are equal:

sage: G2 = PermutationGroup( [ [(1,2),(3,4)], [(2,3,4)] ])
sage: G.stabilizer(10) == G2
True

but GAP's result is nicer.

[nborie]

Stay around, I am going to improve my "horrible" fix shortly...

[nborie]

Ok, now all the job is made in gap. The number of tests (including a random one) must help these methods to give right answer!

All tests passes including the optional one...

[nthiery]

The new implementation does the simplest thing: to just call GAP; and that fixes the problem at hand.The patch also adds a lots of doctests. All tests pass on 4.4.1. Positive review!

[nthiery]

Fix a trivial typo, and add hg header. Apply only this one.

[rbeezer]

Standalone doctring improvements, reviewer patch

[rbeezer]

Somehow I thought this needed review, but obviously didn't look close enough.

In any event, I made some improvements to the docstring, which I just added. I'm going to move them to a new ticket, so as to not mess this up. Sorry for the confusion.

Release manager - you can remove trac_8030-reviewer-doc-edit.patch - it'll appear elsewhere with a new name.

Rob

[mpatel]

It seems that trac_8030-reviewer-doc-edit.patch made it into 4.4.3.alpha2. From building the PDF reference manual:

[2668] [2669] [2670] [2671] [2672] [2673] [2674] [2675] [2676] [2677]
! Undefined control sequence.
l.217693 ...als}(\mathrm{pos}_{i+1})]_{1 \leqslant
                                                   i \leqslant n}$
? 

I suppose #9102 is the place to fix this?

[rbeezer]

Replying to mpatel:

It seems that trac_8030-reviewer-doc-edit.patch made it into 4.4.3.alpha2. From building the PDF reference manual: {{{ [2668] [2669] [2670] [2671] [2672] [2673] [2674] [2675] [2676] [2677] ! Undefined control sequence. l.217693 ...als}(\mathrm{pos}_{i+1})]_{1 \leqslant i \leqslant n}$ ? }}} I suppose #9102 is the place to fix this?

Hi Misha,

That was a new macro to me, and worked fine in the HTML version of the docs. Looks like it is part of the AMS packages. I'll work on a patch as part of #9102, but long-term, does the PDF version need amsmath or amssymb packages to be included? I can investigate later, but have a busy day today, so I'll get a quick fix up first.

Rob