Baltic Way shortlist

Answer: the generating polynomials are exactly the polynomials of odd degree. Take an arbitrary polynomial $f$. We call a polynomial good if it can be represented as $\sum f(g_i(x))$ for some polynomials $g_i$. It is clear that the sum of good polynomials is good, and if $\phi$ is a good polynomial then each polynomial of the form $\phi (g(x))$ is good also. Therefore for the proof that $f$ is generating it is sufficient to show that $x$ is good polynomial. Consider two cases.

1) Let the degree $n$ of $f$ is odd. Check that $x$ is good polynomial. Observe that by substitutions of the form $f(ux)$ we can obtain a good polynomial ${\varphi }_n$ of degree $n$ with leading coefficient $1$, and a good polynomial ${\psi }_n$ of degree $n$ with leading coefficient $-1$ (because $n$ is odd). Then for each $a$ a polynomial ${\varphi }_n(x+a)+{\psi }_n(x)$ is good. It is clear that its coefficient of $x^n$ equals $0$; moreover, by choosing appropriate $a$ we can obtain a good polynomial ${\varphi }_{n-1}$ of degree $n-1$ with leading coefficient $1$, and a good polynomial ${\psi }_{n-1}$ with leading coefficient $-1$. Continuing in this way we will obtain a good polynomial ${\varphi }_1(x)=x+c$. Then ${\varphi }_1(x-c)=x$ is also good.

2) Let the degree $n$ of $f$ is even. Prove that $f(x)$ is not generating. It follows from the observation that the degree of every good polynomial is even in this case. Indeed, the degree of each polynomial $f(g_i)$ is even and the leading coefficient has the same sign as the leading coefficient of $f$. Therefore the degree of polynomial $\sum f(g_i(x))$ is even.