Note that $ x^2 - 2xy + y^2 = (x - y)^2 $ and that $ x^3 + y^3 + z^3 - 3xyz = (x + y + z)(x^2 + y^2 + z^2 - xy - yz - zx) $ so the relevant polynomial is factorable for $ n = 2 $ and $ n = 3 $ Now I shall prove that for $ n \geq 4 $ this polynomial is irreducible. Treating it as a polynomial in $ a_n $ it suffices to show that its constant term, the polynomial $ a_{1}^n + a_{2}^n + \dots + a_{n-1}^n $, is irreducible. Treating this new polynomial as a polynomial in $ a_{n-1} $ and then in $ a_{n-2} $ and so on it suffices to show that $ a_{1}^n + a_{2}^n + a_{3}^n $ is irreducible for all $ n \geq 4 $. Note that $ a_{1}^n + a_{2}^n + a_{3}^n = \prod_{k = 1}^n\left(a_1 + \omega_{k}\sqrt [n] {a_{2}^n + a_{3}^n}\right) $ where $ \omega_{k} = e^{\frac{2\pi{i}k}{n}} $ for all $ k $. Looking at this as a polynomial in $ a_1 $, if it was reducible then one of its factors must have constant term of the form $ \omega\left(a_{2}^n + a_{3}^n\right)^{\frac{j}{n}} $ for some $ n $-th root of unity $ \omega $ and some integer $ 0 < j < n $. But this itself must be some polynomial $ P(a_2, a_3) $. Therefore $ \left(a_{2}^n + a_{3}^n\right)^j = P(a_2, a_3)^n $. Now, take $ a_3 = 1 $. It now suffices to show that there is no polynomial $ f $ such that $ \left(x^n + 1\right)^j = f(x)^n $. But note that the roots of the RHS all have multiplicity a multiple of $ n $ and since the roots of the LHS are precisely the $ 2n $-th roots of unity that are not $ n $-th roots of unity, all roots of the LHS have multiplicity $ j < n $ so we have the desired result. Now, I would like to include some motivation. Dealing with irreducibility of multivariable polynomials is much more difficult than with normal polynomials... certain criterion like that of Eisenstein still work but usually the first thing one should try is to reduce the problem to a single variable polynomial problem. Moreover, when looking for irreducibility over the reals as opposed to the rationals, looking at roots (bounding them, multiplicities, etc...) is usually the way to go. The combination of these ideas motivates the above solution (at least, that's how I was motivated).

Yet another peoblem about Eherenfeucht criterion in ELMO. (Both are actually its special cases.) Why the proposers always stick on the same idea?

K_Mirrorheart wrote: Yet another peoblem about Eherenfeucht criterion in ELMO. (Both are actually its special cases.) Why the proposers always stick on the same idea? What is this criterion?

Quote: What is this criterion? For univariate polynomials $f,g,h$ in $C[x]$, $f(x)+g(y)+h(z)$ is irreducible in $C[x,y,z]$. Also $f(x)+g(y)$ is irreducible provided that their degree is coprime.

K_Mirrorheart wrote: Quote: What is this criterion? For univariate polynomials $f,g,h$ in $C[x]$, $f(x)+g(y)+h(z)$ is irreducible in $C[x,y,z]$. Also $f(x)+g(y)$ is irreducible provided that their degree is coprime. How does it apply to the problem?

Quote: How does it apply to the problem? Those who know this criterion in advance would see immediately $x_1^n+x_2^n+x_3^n$ is irreducible, thus trivializing the proof for $n\ge 4$.

Galois Theory Solution Claim: if $n\ge 4$ then $Q(a_1,\cdots,a_n)=a_1^n +\cdots+a_n^n - n a_1 \cdots a_n$ is irreducible. Let $E = \mathbb{C}[a_1,\cdots,a_n]$ be a (transcendental) field extension, where $P(a_1,\cdots,a_n)=0$ imply $P$ is the zero polynomial. The key is to consider automorphisms of $E/ \mathbb{C}$ that fix $Q(a_1,\cdots,a_n)=a_1^n +\cdots+a_n^n - n a_1 \cdots a_n$ (ie this is an automorphism of $E$ that fixes $\mathbb{C}$ and $Q$) Let $\omega$ be a primitive $n$th root of unity. An automorphism $\sigma$ that fix $Q$ must first map $a_k$ to $\omega^{c_k}a_{\pi(k)}$ for some $c_k \in \{0,\cdots,n-1\}$ and $n\mid c_1+\cdots+c_n$. Observe that if $R$ is an irreducible polynomial in $E$, then $\sigma R$ is merely a reversible change of variables and is also irreducible in $E$. Clearly all irreducible factors of $Q$ are homogeneous. Let $R(a_1,\cdots,a_n)$ be an irreducible factor of minimal degree. Clearly $d=\deg R \le n/2$. We first make an observation: fix indices $j,k$. Let $$S_{j,k} = \{ u-v \mid R \text{ has a term with } a_j^u a_k^v\}$$ Let $d_{j,k}$ be the gcd of $n$ and differences of pairs of elements in $S_{j,k}$. Note $S_{j,k}$ must contain at least two different elements. If not, then (possibly permuting $j,k$) $R$ can be written as $a_j^e P(\underbrace{a_1,\cdots,a_n}_{j,k \text{ not included}}, a_ja_k)$. Since $a_j\nmid Q, e=0$; but if I fix $a_ja_k$ but change $a_j$, $Q$ can change, contradiction! The key observation is that there are at least $\frac{n}{d_{j,k}}$ automorphisms that fix $Q$, change only $a_j,a_k$ but changes $R$ (by not just a unit (aka a constant factor)); I change $a_j,a_k$ to $\omega^c a_j, \omega^{-c} a_k$ where $0\le c<\frac{n}{d_{j,k}}$. Assume FTSOC somehow that all terms in $R$ have multiplied by $\omega^t$ for some $t$. Then I can see that for all $s\in S_{j,k}, sc\equiv t(\bmod\; n)$, which means for all $y\in S_{j,k} - S_{j,k}, yc\equiv 0(\bmod\; n)$. This implies that $c$ is divisible by $\frac{n}{d_{j,k}}$, so $c=0$ is forced. Furthermore, they produce $\frac{n}{d_{j,k}}$ p/w distinct irreducible polynomials that are a factor of $Q$. Since $\deg R \le \frac n2$ there exists indices $u,v$ such that a term of $R$ doesn’t include $a_u$ or $a_v$. Then $d_{u,v} \le d$ and shifting as per the key observation gives $\frac nd$ p/w coprime polynomials that divide $Q$. The product of these polynomials has degree $n = \deg Q$. Equality holds only if $d\mid n$ and $d_{u,v}=d \to R$ is a polynomial in $\underbrace{a_1,\cdots,a_n}_{u,v \text{ not included}}, a_u^d, a_v^d, a_ua_v$. There is a $a_u^d a_v^0 T(\underbrace{a_1,\cdots,a_n}_{u,v \text{ not included}})$ monomial in $R$, and comparing degrees suggest it is $ca_u^d$ for some $c\in \mathbb{C}$. Thus I can apply the same argument on all pairs of indices that don’t include $u$. Same with $v$. It’s not difficult to see that this implies $R$ is a polynomial in $a_1^d, \cdots, a_n^d$. The $a_1\cdots a_n$ term in $Q$ imply $d=1$. The finish is left to the reader as an exercise.