12
$\begingroup$

A standard way to find solutions to a finite set of equations in a finite symmetric group ${\rm S}_n$ is to take the equations as relators of a finitely presented group, to use the low index subgroups algorithm to find all subgroups of index $\leq n$ of that group, and to compute the permutations induced by the generators on the right cosets of these subgroups by multiplication from the right. The drawback of this approach is that the time taken by the low index subgroups algorithm grows in general faster than exponentially with $n$.

Now, finite permutation groups are objects which in many respects can be handled computationally very well, while finitely presented groups tend to be a lot more cumbersome when it comes to computation. So moving to finitely presented groups in order to solve a permutation group problem seems like a strange indirection.

Question: Is there an efficient genuine permutation group method for solving a set of equations in a finite symmetric group, i.e. one which does not use finitely presented groups and coset enumeration? -- Here "efficient" means "practical for degrees at least in the hundreds", or "with at least similar range of applicability as stabilizer chain methods".

Improve this question
$\endgroup$
6
  • $\begingroup$ Could you give an example of your equations? E.g., can you have constants in your equations, i.e. something like $x_1^{i_1} a_1 x_2^{i_2} a_2...=1$, with $i_1$ fixed integers, $a_i$ fixed elements of $S_n$, and $x_i$ - variables? $\endgroup$
    – Dima Pasechnik
    Mar 1, 2015 at 14:46
  • $\begingroup$ @DimaPasechnik: The basic setting is without constants in ${\rm S}_n$, i.e. an example would be $aba^{-3}b^{-3}=a^7=1$ (example taken from Problem 8.10(a) in the Kourovka Notebook) -- but of course a method which can efficiently deal with such constants would be fine as well! $\endgroup$
    – Stefan Kohl ♦
    Mar 1, 2015 at 15:31
  • $\begingroup$ An old theorem of Mauer and Rhodes shows any n-ary mapping on a finite simple group is given by a word in n-variables and constants which means allowing constants should make this hard. $\endgroup$
    – Benjamin Steinberg
    Mar 1, 2015 at 15:55
  • $\begingroup$ @BenjaminSteinberg: Interesting. -- Though by cardinality considerations, most such words must have length at least about the order of the group, which means a gigantic input length -- or in other words, the brute force method which simply checks for every $k$-tuple of group elements whether it is a solution would still be polynomial time in the input length(!) -- For my purposes, I assume that the sum of the lengths of the equations which are to be solved in ${\rm S}_n$ is SMALLISH in comparison with $n!$. $\endgroup$
    – Stefan Kohl ♦
    Mar 1, 2015 at 17:21
  • 2
    $\begingroup$ It's an interesting question, but I would guess that the answer is no. Or, rather, I suspect that what you are asking is essentially equivalent to asking whether there is a faster low index subgroups algorithm. It is possible that some improvements could be made but I would be surprised if its complexity could be improved upon. $\endgroup$
    – Derek Holt
    Mar 1, 2015 at 22:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.