How to find the symmetry group of a polynomial

Question

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.

Answer 1

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.