It seems pretty hard. I think the answer is \[\{f\in\mathbb{R}[x]\colon 2\mid \deg f+1\}. \] If $2\mid \deg f$, the coefficient of the highest power cannot be zero, thus $x$ cannot be expressed. If exists $g_1,\cdots,g_k$ such that \[P(x)=f(g_1(x))+f(g_2(x))+\cdots+f(g_k(x))\]we call $P(x)$ is $f-good$. We can use induction to prove if $\deg f=2m+1$, then $x$ is $f-good$. We use the idea that for polynomials $A,B$, if $x$ is $A-good$, $A$ is $B-good$, then $x$ is $B-good$. Thus we only need to prove there exists a polynomial $P$ with degree $2m-1$ is $f-good$, which is trivial.

smy2012 wrote: Thus we only need to prove there exists a polynomial $P$ with degree $2m-1$ is $f-good$, which is trivial. Sorry but how is this trivial? I can see that it is probably true and could be worked out but I don't quite see how it is obvious.

Interestingly, a special case of this already appeared in Baltic Way 2006.

Gryphos wrote: Interestingly, a special case of this already appeared in Baltic Way 2006. Nice observation! However, this special case seems to be much easier than this problem in at least two aspects: First of all, of course because it is just a special case and thus can be solved very concretely. Second and more interesting: It belongs to a larger class where the problem is much easier to approach, namely it is an odd polynomial: For odd polynomials we can w.l.o.g. make the $+$ signs in the linear combination considered into $+$ or $-$ signs. And this makes life a lot easier because we can write down finite differences. This proves the claim for odd polynomials on the nose. For instance, for a third degree polynomial $f$ we would like to consider $f(x)-2f(x+1)+f(x+2)$ which is linear. For a fifth degree polynomial $f$, again $f(x)-4f(x+1)+6f(x+2)-4f(x+3)+f(x+4)$ is linear and so on. However, this trick does no longer work when $f$ is allowed to contain even terms such as $f(x)=x^3+x^2$.

\[x^3+x^2=\left(x+\frac13\right)^3-\frac{1}3 \left( x+\frac{1}3 \right)+\frac8{27}.\]

smy2012 wrote: \[x^3+x^2=\left(x+\frac13\right)^3-\frac{1}3 \left( x+\frac{1}3 \right)+\frac8{27}.\] Nice. But can you rigorously prove that any polynomial can be converted into an odd polynomial like this. It seems to be true to me.

AnArtist wrote: smy2012 wrote: \[x^3+x^2=\left(x+\frac13\right)^3-\frac{1}3 \left( x+\frac{1}3 \right)+\frac8{27}.\] Nice. But can you rigorously prove that any polynomial can be converted into an odd polynomial like this. It seems to be true to me. I've edited my post.

smy2012 wrote: We use the idea that for polynomials $A,B$, if $x$ is $A-good$, $A$ is $B-good$, then $x$ is $B-good$. Excuse me. May you explain how to prove it?

Henry_2001 wrote: smy2012 wrote: We use the idea that for polynomials $A,B$, if $x$ is $A-good$, $A$ is $B-good$, then $x$ is $B-good$. Excuse me. May you explain how to prove it? That's very easy: If \[x=A(g_1(x))+\dots+A(g_k(x))\]and \[A(x)=B(p_1(x))+\dots+B(p_m(x)),\]you can just plug in the second equation into the first and obtain \[x=\sum_{i=1}^k \sum_{j=1}^m B(p_j(g_i(x))).\]