Balti Tee 2018 · Ülesanne 5

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 $\varphi$ is a good polynomial then each polynomial of the form $\varphi(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 $\phi_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 $\phi_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 $\phi_{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 $\phi_1(x) = x + c$. Then $\phi_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.