Symmetry Group of a Polynomial

Question

Given a polynomial $P \in \mathbb{Z}[X_1,\ldots,X_n]$, is there a poly-time algorithm which computes the group of permutations of variables that leaves $P$ unchanged? (Clearly, the trivial $O(n!)$-time algorithm is not poly-time.)

Answer 1

If the input has fully-expanded polynomials, then this is equivalent to graph isomorphism.

In one direction, given a graph, create a variable for each vertex and consider the polynomial $\prod_{vw\in E(G)} (1 + x_vx_w)$. Unique factorization assures that this representation is reversible.

In the other direction, given a polynomial there are multiple ways of encoding it as a graph. I'll use a coloured bipartite graph, which can be converted to a uncoloured simple graph by standard means. Vertex colors are numbers that appear as coefficients and edge colours are numbers that appear as powers of variables. Make one vertex for each variable. For each monomial, make a new variable coloured by the coefficient and join it to each variable it contains by an edge coloured by the degree of that variable in the monomial. (Eg., monomial $6x^2y$ is a vertex coloured "6" joined to vertex "$x$" by an edge of colour "2" and to vertex "$y$" by an edge of colour "1".) This representation is also reversible.

I'll explain how the second example works, assuming you have an oracle that provides one (colour-preserving) isomorphism between two coloured graphs or says that there is none. Let $P_1,P_2$ be two polynomials and $G(P_1),G(P_2)$ their corresponding graphs. The construction ensures that any isomorphism between $P_1$ and $P_2$ can be converted to an isomorphism between $G(P_1)$ and $G(P_2)$, and vice versa. Now consider one polynomial $P$ and two of its variables $x,y$. Say $n$ is the total degree of $P$. Then $P$ has an automorphism (symmetry as in the original question) that maps $x$ onto $y$ iff $G(P+x^{n+1})$ is isomorphic to $G(P+y^{n+1})$, and the oracle will give you such an automorphism if there is one. By continuing this process by marking more variables, you can build up a strong generating set for the automorphism group of $P$. For example, comparing $G(P+x^{n+1}+u^{n+2})$ to $G(P+y^{n+1}+v^{n+2})$ will get you an automorphism, if any, that maps $x$ onto $y$ and $u$ onto $v$.