group theory: strong presentation based on Sims Verify algorithm #13698
Conversation
Implementation of Sims Verify algorithm and a function for computing strong presentations of permutation groups. This is more efficient than obtaining a strong presentation by just using `presentation` on the strong generators. `_verify` can be eventually used to obtain a base and a strong generating set for a group by generating a candidate randomly and amending missing generators which would be faster than Schreier-Sims for large groups.
sympy/combinatorics/perm_groups.py
Outdated
|
|
||
| # orbit representatives of K_beta | ||
| gammas = [alpha, beta] | ||
| orbits = list(uniq(K_beta.orbit(o) for o in orbit)) |
There was a problem hiding this comment.
Is it possible to use set instead of calling uniq?
There was a problem hiding this comment.
Yes, the order isn't important. Somehow I felt that using uniq would be faster but now that I actually tried it in python shell, using set on lists is significantly faster. I'll change this in other places as well.
| gammas = [alpha, beta] | ||
| orbits = list(uniq(K_beta.orbit(o) for o in orbit)) | ||
| orbit_reps = [list(orb)[0] for orb in orbits] | ||
| for rep in orbit_reps: |
There was a problem hiding this comment.
Is it clear that alpha would be the first element, list(orb)[0], of the K_beta-orbit orb of alpha? If not, then we should probably remove that orbit from orbits (and also the orbit of beta).
There was a problem hiding this comment.
K_beta stabilizes beta (by definition) and alpha (because K == H.stabilizer(alpha)) so they are the only things in their orbits. Though excluding them when orbits are computed would probably be a little faster.
There was a problem hiding this comment.
Of course. I forgot that K_beta also stabilizes alpha. This should be OK then.
sympy/combinatorics/perm_groups.py
Outdated
| # is the same as | ||
| return H.presentation(eliminate_gens=False) | ||
| # H is a group on one generator and this is the relator for it | ||
| rels = [F.generators[-1]**H.generators[0].order()] |
There was a problem hiding this comment.
I have not succeeded in proving this. What would happen with Klein's 4-group?
There was a problem hiding this comment.
It's not the case in general but I was under a strong impression that schreier_sims orders the base in a way that this always happens because somehow this was the case with all of the random tests I ran (which was many). But turns out it was a wrong impression (and also silly of me to not verify, sorry about that).
Klein's 4-group always has a base of length 1 so there is only one stabilizer and it doesn't get to this point in the algorithm. But if you throw in a disjoint permutation into the generating set and order the generators in a specific way, it gives a counterexample. E.g.
>>> a = Permutation(0, 1)(2, 3)
>>> b = Permutation(0, 2)(3, 1)
>>> c = Permutation(4, 5)
>>> V = PermutationGroup(c, a, b)
(but not PermutationGroup(a, b, c)).
I'll make sure that if there are more than one generators, the stabilizer is completed by the main for loop. Also, should probably add it to the tests.
The last stabilizer in the chain isn't always cyclic and this commit accounts for it. Also, the case in the strong_presentation algorithm where the relators are found in the block action was slightly corrected as the domain of one of the homomorphism should be the whole group, otherwise composition doesn't work properly. Additionally a new test was added and `uniq` replaced by `set` everywhere in the new functions.
|
Found another problem later on in the code so pushed the changes now. |
| rel = rel*phi.invert(g)**-1 | ||
| new_rels = [rel] | ||
| elif len(orbit_k) == 1: | ||
| success, new_rels = K_s._verify(K, phi, z, alpha) |
There was a problem hiding this comment.
Shouldn't success be checked somewhere?
There was a problem hiding this comment.
The way the function is written, we know that success will always be true because we start with a strong generating set. Theoretically, later this could be changed so that we start with a randomly generated (potential) BSGS, and then append new elements to it whenever success is false.
There was a problem hiding this comment.
OK. Maybe a comment could be added to that effect for future maintenance.
There was a problem hiding this comment.
Otherwise, I think this is ready to be merged.
|
Thanks! I think this is ready to be merged. |
2 participants
This PR implements Sims Verify algorithm (see the docstring of
_verifyfor description) and a function for computing strong finite presentations of permutation groups (strong_presentation). This new function is typically more efficient than obtaining a strong presentation by just usingpresentationon a group whose generators are already strong._verifycan be used to obtain a base and a strong generating set for a group by generating a candidate randomly (maybe usingschreier_sims_random) and amending missing strong generators. This could be faster than regular Schreier-Sims for large groups, and a separate function to do that could be written in the future.Other changes include fixing a minor bug in the
ordermethod forFpGroups (use absolute value so that the order is non-negative), excluding identity from the generating set when aPermutationGroupis constructed, allowing application of homomorphisms to tuples and the new homomorphism functioncomposefor returning a composition of two homomorphisms.