3
$\begingroup$

Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. Example: $x^2+y^2+z$ has the subgroup $\langle(x,y)\rangle$. Given such a polynomial, what is the best way to find such a polynomial.

Usage Note: I need this algorithm to terminate in "a short amount of time" for $n$ about 15, $m$ about 10. Short being, I guess, less than 1 minute.

Partial progress: If all I do is test particular elements of $S_n$, this problem is basically intractable as I need roughly $(n-2)!$ tests. Current implementation does basic checks such as the following. In my example $x$ cannot map to $z$ because $z^2$ terms do not exist. In this way we can eliminate much larger fractions of permutations. However, since $S_n$ is so large, this approach is still too slow.

$\endgroup$
4
  • 2
    $\begingroup$ Maybe mathoverflow.net/questions/232076/… $\endgroup$
    – adrianN
    Oct 7, 2016 at 14:45
  • $\begingroup$ This is equivalent to graph isomorphism? Does that mean the new discovery can be applied to make this faster, or is 15 too small of a number $\endgroup$
    – davik
    Oct 7, 2016 at 14:47
  • $\begingroup$ Actually, a little more clarification is needed. Your example is rather trivial, since the monomials of your polynomial are all in a single variable. In this case, the problem is trivial: the automorphism group is generated by the permutations that exchange two variables if they appear in the same monomials. If you're allowed monomials in more than one variable, then the post at mathoverflow shows it is equivalent to GI. However, Babai's new algorithm isn't necessarily useful for that: it's asymptotically fast but who knows if it beats other approaches for small instances? $\endgroup$ Oct 7, 2016 at 15:05
  • 1
    $\begingroup$ It's worth pointing out that, in practice, there are existing graph isomorphism solvers that can solve most instances of graph isomorphism very efficiently. So if this problem can be reduced to graph isomorphism that's probably a very good sign that indicates it's likely you'll be able to find a good solution for your problem. See, e.g., the nauty solver. $\endgroup$
    – D.W.
    Oct 7, 2016 at 19:01

1 Answer 1

3
$\begingroup$

There is a reduction from your problem to graph isomorphism, as explained in this question on Math Overflow. In particular, that answer shows how to obtain a random automorphism of the polynomial, i.e., a random permutation in the symmetric group. For example, you can start by randomly picking a pair of variables $x_i,x_j$ and testing whether there exists an automorphism that sends $x_i \mapsto x_j$; if so, you can search to find another variable $x_k$ such that there exists an automorphism that sends $x_i \mapsto x_j$ and $x_j \mapsto x_k$; and so on until you obtain a complete permutation.

To obtain a set of generators for the symmetry group, you can repeat this search many times to obtain multiple random permutations known to be in the symmetry group; if you repeat enough times, with high probability, the resulting set will generate the entire symmetry group. Or, you can systematically enumerate the space of all permutations that are in the symmetry group; if the symmetry group is small enough, this will be efficient.

This requires us to have an oracle for solving graph isomorphism. Fortunately, there are existing graph isomorphism solvers that can solve typical instances of graph isomorphism very rapidly. For instance, you can take a look at nauty, a graph isomorphism solver that typically finishes within seconds on graphs with at most 100 vertices or so. The question on Math Overflow describes how to reduce the problem to isomorphism of colored hypergraphs; the nauty manual describes how you can convert this to an ordinary graph isomorphism problem, at the cost of some small increase in the size of the graph.

If you put all of this together, I expect it will be possible to construct an algorithm for your problem that is pretty efficient in practice, for polynomials of the size you describe.

$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.