We prove that the $S_n$ have integer coefficients by induction on $n$ with base case $n=1$ obvious. For the inductive step, suppose $S_1,S_2,\dots, S_{n-1}$ all have integer coefficients. Let $p$ be a prime with $v_p (n)=k>0$; it suffices to show that $p^k \mid \displaystyle\sum_{d\mid n} d \cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid n,d\neq n} dS_d^{n/d}$ and repeating over all $p$ will finish. Let $n=pm$, so every $d$ which is not a divisor of $m$ will vanish from the above sum when taken modulo $p^k$; thus it's enough to show $p^k\mid \displaystyle\sum_{d\mid m} d\cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid m} dS_d^{n/d}$. Let $T_i (x_1,x_2,\dots, y_1,y_2,\dots) = S_i (x_1^p, x_2^p, \dots, y_1^p, y_2^p, \dots)$ for every $i$, so by the problem hypotheses applied to the $T_i, x_i^p,y_i^p$ the previous sum equals $\displaystyle\sum_{d\mid m} d \cdot ( x_d^{pm/d} + y_d^{pm/d} ) - \displaystyle\sum_{d\mid m} dS_d^{pm/d} = \displaystyle\sum_{d\mid m} d \left( T_d^{m/d} - S_d^{pm/d}\right)$. Now I claim that $p^k$ divides each term of this final sum. Indeed, let $\dfrac{m}{d} = p^lq$ for some $p\nmid q$, so it's enough to show $p^{l+1} \mid T_d^{p^lq}- S_d^{p^{l+1}q}$. Then by the inductive hypothesis $A = S_d^{pq}$ is an integer polynomial, and by the Frobenius Endomorphism we have that $T_d^q = A + Bp$ for some polynomial $B$ with integer coefficients, so we'd like to show $p^{l+1} \mid (A+Bp)^{p^l} - A^{p^l} = \displaystyle\sum_{1\le i\le p^l} (Bp)^i A^{p^l-i} \binom{p^l}{i}$. In fact $p^{l+1}$ now divides every term of this final sum, because $v_p \left(p^i \binom{p^l}{i}\right) = v_p \left( p^i \cdot \dfrac{p^l}{i} \binom{p^l-1}{i-1} \right) \ge i + l - v_p (i) \ge l+1\iff i\ge v_p (i)+1$, which is clearly true for $i\ge 1$, so we're done. (Clarification for below posts: All divisibility here refers to polynomial divisibility in $\mathbb Z[x]$. )

tastymath75025 wrote: . Let $p$ be a prime with $v_p (n)=k>0$; it suffices to show that $p^k \mid \displaystyle\sum_{d\mid n} d \cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid n,d\neq n} dS_d^{n/d}$ and repeating over all $p$ will finish. Here you only proved that $S_n$ is integer for all integer values of $x1,...$, but this is not enough. A simple example would be $S(x)=\frac{x^2+x}{2}$ that is integer for all integer values of $x$ but does not have integer coefficients.

Gomes17 wrote: tastymath75025 wrote: . Let $p$ be a prime with $v_p (n)=k>0$; it suffices to show that $p^k \mid \displaystyle\sum_{d\mid n} d \cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid n,d\neq n} dS_d^{n/d}$ and repeating over all $p$ will finish. Here you only proved that $S_n$ is integer for all integer values of $x1,...$, but this is not enough. A simple example would be $S(x)=\frac{x^2+x}{2}$ that is integer for all integer values of $x$ but does not have integer coefficients. I'm pretty sure he's using polynomial divisibility rather than integer divisibility here... eg. the polynomial $2$ is not considered to divide the polynomial $x^2+x$ in $\mathbb Z[x]$.

Where did he mention that he was using polynomial divisibility?

He is trying to prove $S_n$ has integer coefficients by showing that $n$ divides the coefficients in some polynomial sum (i.e. the polynomial $n$ divdies some other polynomial). Of course he is using polynomial divisiblity Regardless, I don't understand what the complaint is, as the rest of the solution is still valid replacing integer with polynomial divisibility at every point

tastymath75025 wrote: We prove that the $S_n$ have integer coefficients by induction on $n$ with base case $n=1$ obvious. For the inductive step, suppose $S_1,S_2,\dots, S_{n-1}$ all have integer coefficients. Let $p$ be a prime with $v_p (n)=k>0$; it suffices to show that $p^k \mid \displaystyle\sum_{d\mid n} d \cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid n,d\neq n} dS_d^{n/d}$ and repeating over all $p$ will finish. Let $n=pm$, so every $d$ which is not a divisor of $m$ will vanish from the above sum when taken modulo $p^k$; thus it's enough to show $p^k\mid \displaystyle\sum_{d\mid m} d\cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid m} dS_d^{n/d}$. Let $T_i (x_1,x_2,\dots, y_1,y_2,\dots) = S_i (x_1^p, x_2^p, \dots, y_1^p, y_2^p, \dots)$ for every $i$, so by the problem hypotheses applied to the $T_i, x_i^p,y_i^p$ the previous sum equals $\displaystyle\sum_{d\mid m} d \cdot ( x_d^{pm/d} + y_d^{pm/d} ) - \displaystyle\sum_{d\mid m} dS_d^{pm/d} = \displaystyle\sum_{d\mid m} d \left( T_d^{m/d} - S_d^{pm/d}\right)$. Now I claim that $p^k$ divides each term of this final sum. Indeed, let $\dfrac{m}{d} = p^lq$ for some $p\nmid q$, so it's enough to show $p^{l+1} \mid T_d^{p^lq}- S_d^{p^{l+1}q}$. Then by the inductive hypothesis $A = S_d^{pq}$ is an integer polynomial, and by the Frobenius Endomorphism we have that $T_d^q = A + Bp$ for some polynomial $B$ with integer coefficients, so we'd like to show $p^{l+1} \mid (A+Bp)^{p^l} - A^{p^l} = \displaystyle\sum_{1\le i\le p^l} (Bp)^i A^{p^l-i} \binom{p^l}{i}$. In fact $p^{l+1}$ now divides every term of this final sum, because $v_p \left(p^i \binom{p^l}{i}\right) = v_p \left( p^i \cdot \dfrac{p^l}{i} \binom{p^l-1}{i-1} \right) \ge i + l - v_p (i) \ge l+1\iff i\ge v_p (i)+1$, which is clearly true for $i\ge 1$, so we're done. (Clarification for below posts: All divisibility here refers to polynomial divisibility in $\mathbb Z[x]$. ) Congratulations! Nobody solved this problem in the test!