The Fundamental Theorem on Symmetric Polynomials, together with the Vieta's Formulas, give us the following conclusion:
For every symmetric polynomial $f \in \Bbb Q[X_1, \dots ,X_n]$ there is a polynomial $g \in \Bbb Q[X_1, \dots ,X_n]$ such that the polynomial identity (in $\overline{\mathbb{Q}}[t]$) $$a_0+a_1t+\cdots + a_{n-1}t^{n-1}+t^n = (t-x_1) \cdots (t-x_n)$$ implies $$f(x_1,…,x_n)=g(a_0,…,a_{n-1})$$
For example, if $f(X,Y)=X^2+Y^2$, then
$$ t^2+ bt + c = (t-x_1) (t-x_2) \quad \Rightarrow \quad f(x_1,x_2) = b^2-2c$$ (To see this, note that $x_1^2 + x_2^2 = (x_1+x_2)^2 – 2x_1x_2$.) So $g(X,Y)= Y^2 – 2X$.
If our polynomial $f$ is not symmetric, there's still hope. For example, suppose $f \in \Bbb Q[X_1, \dots ,X_n]$ is anti-symmetric. Then $f \cdot f$ is a symmetric polynomial, and therefore there is a polynomial $\hat g \in \Bbb Q[X_1, \dots ,X_n]$ such that
$$f(x_1,\dots,x_n) = \pm \sqrt{\hat g(a_0,…,a_{n-1})}$$
For example, if $f(X,Y) = X – Y$, then
$$ t^2 + bt +c = (t-x_1)(t-x_2) \quad \Rightarrow \quad f(x_1,x_2)^2 = b^2-4c$$ (This follows by essentially the same argument as the previous example.)
Another way to say this is that, in the antisymmetric case, calculating $f(x_1,…,x_n)$ is still as hard as calculating the roots of the polynomial $t^2-\hat g(a_0,…,a_{n-1})\in\mathbb{Q}(\hat{g})[t]$.
So my question is: given a polynomial $f \in \Bbb Q[X_1, \dots ,X_n]$, can we determine if there is a polynomial $Q \in \Bbb Q[t]$ (of positive degree) such that $Q \circ f \in \mathbb{Q}[X_1, \dots ,X_n]$ is a symmetric polynomial? This would mean that calculating $f(x_1,…,x_n)$ is as hard as calculating the roots of $Q$.
—Edit: The Polynomial $f$ should have positive degree in each variable. i think it's a reasonable simplification of the problem to ask the polynomial $f$ to be homogeneous.
Best Answer
If we make the further assumption that $f$ is homogeneous, then the solutions are the alternating polynomials, as I show below (the general case seems much harder). Note that those polynomials always have a symmetric square.
Suppose $f$ is an homogeneous solution, with total degree $d \gt 0$. Then, for any $k\geq 0$, $f^k$ is also homogeneous with total degree $kd$. If we write $Q=\sum_{j=0}^d q_jx^j$ and $q_d\neq 0$, we see that the components $q_jf^j$ do not overlap, so that $f$ is symmetric iff each $q_jf^j$ is. In particular, $q_df^d$ is symmetric and we may assume $Q=x^d$.
So we have the identity $f(x_1,x_2,\ldots,x_n)^d = f(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})^d$ in ${\mathbb Q}[x_1,x_2,\ldots,x_n]$ for every $\sigma\in {\mathfrak S}_n$, whence $f(r_{\sigma(1)},\ldots,r_{\sigma(n)})=\pm f(r_1,r_2,\ldots,r_n)$ for any $(r_1,r_2,\ldots,r_n)\in {\mathbb Q}^n$. So there is a map $\lambda:{\mathfrak S}_n \times {\mathbb Q}^n \to \lbrace \pm 1 \rbrace$ such that
$$ f(r_{\sigma(1)},\ldots,r_{\sigma(n)})=\lambda(\sigma,r_1,r_2,\ldots,r_n) f(r_1,r_2,\ldots,r_n) \tag{1} $$
Now, fix $\sigma\in {\mathfrak S}_n$ and $s=(r_1,\ldots,r_{n-1})\in {\mathbb Q}^{n-1}$, and consider the partial map $\lambda_{\sigma,s}:{\mathbb Q} \to \lbrace \pm 1 \rbrace$ defined by $\lambda_{\sigma,s}(r_n)=\lambda(r_1,\ldots,r_{n-1},r_n,\sigma)$. Since the image of $\lambda_{\sigma,s}$ is finite and $\mathbb Q$ is infinite, there is a value $\mu(\sigma,s)\in \lbrace \pm 1 \rbrace$ that is attained infinitely often. The identity $f(s.\sigma,r_{\sigma(n)})=\mu(\sigma,s)f(s,r_n)$ then holds for infinitely many $r_n$, and hence holds for all $r_n$ since $f$ is a polynomial.
Repeating this argument and using induction on $n$, we eventually see that we can take $\lambda$ to be dependent on $\sigma$ only and not on $r_1,\ldots,r_n$ :
$$ f(r_{\sigma(1)},\ldots,r_{\sigma(n)})=\lambda(\sigma) f(r_1,r_2,\ldots,r_n) \tag{2} $$
Since we assume $f\neq 0$, there is a $(\rho_1,\rho_2,\ldots,\rho_n)$ with $f(\rho_1,\rho_2,\ldots,\rho_n)\neq 0$. Then we can write :
$$ \lambda(\sigma)=\frac{f(\rho_{\sigma(1)},\rho_{\sigma(2)},\ldots,\rho_{\sigma(n)})}{f(\rho_1,\rho_2,\ldots,\rho_n)} \tag{3} $$
and it easily follows that $\lambda$ is a group homomorphism ${\mathfrak S}_n\to \lbrace \pm 1 \rbrace$. So, $\lambda$ either the identity or the signature homomorphism, and $f$ is an alternating polynomial.