# How to find the symmetry group of a polynomial

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.

• – adrianN Oct 7 '16 at 14:45
• 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 – davik Oct 7 '16 at 14:47
• 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? – David Richerby Oct 7 '16 at 15:05
• 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. – D.W. Oct 7 '16 at 19:01

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.