Prove or disprove that $f$ is a polynomial if $f(a+x)-f(x)$ is a polynomial for each fixed $a$ 
Prove or disprove that if $f:\mathbb{R}\to \mathbb{R}$ satisfies that $f_a (x) := f(x+a)-f(x)$ is a polynomial in $x$ for each fixed $a$, then $f$ is a polynomial.

I saw this closely related post.
Based on the proof I've added some more details to better understand the proof which are shown below.
Let $f_a(x) := f(x+a)-f(x)$ for all real a. Note that $f_a(x+b) - f_a(x) = f(x+b+a)-f(x+b)-f(x+a)+f(x)= f_b(x+a)-f_b(x)$ for all $x,a,b\neq 0$. Fix $a,b\neq 0$. Let the degree of $f_a(x)$ be $n>0$. The equation above implies the degrees of $f_a$ and $f_b$ are the same since if , then the degrees of both sides of the equation equal $n-1$ and otherwise both sides of the equation equal $0$ so both $f_a$ and $f_b$ are constant polynomials.
Claim 1: The leading coefficient of $f_a$ equals $ac$ and the leading coefficient of $f_b$ equals $bc$ for some real number c, provided $n > 0$. If the leading coefficient of $f_a$ is $ac$ for some real $c$ and $f_a$ has degree $n > 0$, then the leading coefficient of $f_a(x+b)-f_a(x)$ is $ac n b x^{n-1}.$ Similarly, if the leading coefficient of $f_b$ is $bd$ for some real $d$, then the leading coefficient of $f_b(x+a)-f_b(x)$ is $bd  n a x^{n-1},$ and equating coefficients and dividing both sides by $abn\neq 0$ yields that $c=d$. This proves the claim.
For nonzero a, $f_a$ is a polynomial of degree n if and only if $g_a$ is and has degree one less than $f_a$, where $g_a(x) = g(x+a)-g(x)$ and $g(x) = f(x) - c\dfrac{(x^{n+1}}{n+1}$. We thus define the sequence of functions obtained to go from $f$ to a function $h$ with $h_a$ being constant, starting from $f_0 = f$ to $f_n = h$ as follows. First for convenience, for all $i\ge 0,$ let $f_{i,a}(x) := f_i(x+a)-f_i(x)$ for all $a\in\mathbb{R}$. Also for a polynomial $p(x)$ and $i\ge 0,$ let $[x^i]p(x)$ denote the coefficient of $x^i$ in p(x). For $i\ge 1,$ if $f_{i-1,a}(x)$ has coefficient $ac_{i-1}$ where $c_{i-1}$ does not depend on $a$, we define $f_i(x) := f_{i-1}(x) - c_{i-1} x^{n+2-i}/(n+2-i).$ We claim that $, f_{i,a}(x)$ is a polynomial and if $i < n$ it has leading coefficient equal to $ac_i$ for some $c_i$ independent of $a$ and $f_{i,a}(x)$ has degree $n-i$ for all $i\ge 0.$ This holds for $i=0$ as $f_{i,a}(x) = f_a(x)$ in that case. Assume it holds for all $0\leq k < i$ where $i>0$. Then it holds for $f_i$ because for nonzero a, $f_{i,a}(x) = f_{i-1,a}(x) - c_{i-1}((x+a)^{n+2-i} - x^{n+2-i})/(n+2-i)$, which has degree $n-i$. Indeed, the coefficient of $x^{n+2-i}$ is zero because $[x^{n+2-i}](x+a)^{n+2-i} = [x^{n+2-i}](x^{n+2-i})$ and the coefficient of $x^{n+1-i}$ is zero because $[x^{n+i-1}]f_{i-1,a}(x) = ac_{i-1} = [x^{n+1-i}]c_{i-1}((x+a)^{n+2-i} - x^{n+2-i})/(n+2-i)$. Finally, since $f_i$ satisfies the same property as $f$ and for $i<n$ it has degree at least one, for $i<n$ we may define $c_i$ so that $f_{i,a}(x) $ has leading coefficient $ac_i$ for all $a\neq 0$. Now note that $f_{n,a}(x) = h_a(x)$ is constant for nonzero a by the above inductive claim, and this along with the continuity of $h$ (each $f_i$ above is continuous by induction) implies $h$ is of degree at most one.  $h(x+a)-h(x) = h(a)-h(0)$ for all $x, a$, which is known to imply that $h(x)$ is of the form $cx+b$ for some $c\in\mathbb{R}$. We have shown above that $f_n$ is a polynomial of degree at most one. Assume inductively that $f_{n-j}$ is a polynomial of degree at most $j+2$ for all $0\leq j < i,$ some $i>0.$ Then $f_{n-i+1} (x) = f_{n-i}(x) - c_{n-i} x^{i+1}/(i+1)$ implies that $f_{n-i}(x)$ is a polynomial of degree at most $i+1$, completing the inductive proof. So $f$ is a polynomial of degree at most $n+1$.

So is there a counterexample to the problem and if so, what would be such a counterexample?

 A: The result is not true without continuity (probably some weaker assumptions like measurability or local boundness are enough) since if we take any additive function $f(x+y)=f(x)+f(y)$ then $f_a(x)=f(a)$ is constant so is a polynomial in $x$ and obviously we can take $g(x)=x^2+f(x)$ so we get $g(x+a)-g(x)=2ax+a^2+f(a)$ has degree $1$ in $x$ for $a \ne 0$ etc
But it is well known that we have lots of additive functions that are not linear (eg using a basis or $\mathbb R$ over $\mathbb Q$)
Edit later: One can easily give a proof by induction that $f(x)=P(x)+f_1(x)$ where $P$ is a polynomial and $f_1$ is additive so indeed any regularity condition on $f$ (eg measurable, locally bounded at a point etc) implies that $f_1$ is linear, hence $f$ is a polynomial
A: If $f(x+a)-f(x)$ is a polynomial for every $a\in\Bbb R$, then $\frac{f(x+a)-f(x)}{a}$ is also a polynomial for all $a\in\Bbb R_{\neq 0}$. Therefore taking the limit we have $\lim_{a\to 0}\frac{f(x+a)-f(x)}{a}=f'(x)$ is a polynomial, which implies $f(x)$ should be a polynomial.
A: We must assume $f$ is continuous. An easy counterexample when this is not the case is the following function $h$: let $b_1,b_2,\cdots$ be an infinite basis over the vector space of real numbers over the field $\mathbb{Q}$. The basis turns out to be infinite because otherwise the span of B would be at most countable (with its cardinality being bounded by $|\mathbb{Q}|^k$ for some positive k) and the real numbers are uncountable. Define a function $f:\mathbb{R}\to\mathbb{R}^+$ as follows. Let $f(e^{b_i}) = 1$ for all even $i$ and $f(e^{b_i}) = 2$ for all odd i.
Then for any $x\in\mathbb{R},$ write $x=a_1b_{i_1}+\cdots + a_n b_{i_n}$ for some $n\ge 1$ and distinct $b_{i_1},\cdots, b_{i_n},$ where each $b_{i_j}\in\mathbb{Q}$ for $1\leq j\leq n,$ and let $f(e^x) := \prod_{1\leq j\leq n} f(e^{b_{i_j}})^{a_j}.$
Then note that for all $x,y \in \mathbb{R}, f(e^{x+y}) = f(e^x)f(e^y).$
Indeed, we know that $f(e^{a_1 b_{i_1}}) = f(e^{b_{i_1}})^{a_1}.$ Assume inductively that for all $1\leq k < s,s\ge 2 $ all $a_1,\cdots, a_k\in\mathbb{Q}$ and any $k$ indices $i_1,\cdots, i_k$, $f(e^{\sum_{j=1}^k a_j b_{i_j}}) = \prod_j f(e^{b_{i_j}})^{a_j}.$
Then let $a_1,\cdots, a_s\in\mathbb{Q}$ and choose any $s$ indices $i_1,\cdots, i_s$.
We just need to show $f(e^{\sum_{j=1}^s a_j b_{i_j}}) = f(e^{\sum_{j=1}^{s-1} a_j b_{i_j}}) f(e^{ b_{i_s}})^{a_s}$, since the inductive claim follows from this step and the inductive hypothesis.
Let WLOG $i_1,\cdots, i_t$ be the indices among $i_1,\cdots, i_{s-1}$ equal to $i_s.$ Among the remaining indices, let their distinct values be $c_1,\cdots, c_q$ where $q\leq s-1-t$ and let for each $1\leq d\leq q, s_d := \sum_{t+1\leq d_1\leq s-1, b_{d_1} = c_d} a_{d_1}$. Then $f(e^{\sum_{j=1}^{s-1} a_j b_{i_j}}) = f(e^{\sum_{j=1}^{t} a_j b_{i_s} + \sum_{j=1}^q s_j c_j}) = f(e^{b_{i_s}})^{\sum_{j=1}^{t} a_j} \prod_{j=1}^q f(e^{c_j})^{s_j},$ and hence $f(e^{\sum_{j=1}^{s} a_j b_{i_j}}) = f(e^{b_{i_s}})^{\sum_{j=1}^{t} a_j + a_s} \prod_{j=1}^q f(e^{c_j})^{s_j} = f(e^{\sum_{j=1}^{s-1} a_j b_{i_j}}) f(e^{ b_{i_s}})^{a_s},$ as required.
The claim that for all $x,y \in \mathbb{R}, f(e^{x+y}) = f(e^x)f(e^y)$ now follows easily from the above proof.  Hence if we let $h:\mathbb{R}\to\mathbb{R}, h(x) = \ln f(e^x),$ then $h(x+y) = h(x)+h(y)$ for all $x,y\in\mathbb{R}.$ Hence for fixed $y, h(x+y)-h(x) = h(y)$ is a constant polynomial. But $h$ is clearly not a polynomial, because $h(b_{2i+1}) = 0$ for all $i\ge 0$ and $h(b_{2i+2}) = \ln 2$ for all $i\ge 0,$ which means that if $h$ is a polynomial, then $h$ is constant. Let $f_a(x) := f(x+a)-f(x)$ for all real a. Note that $f_a(x+b) - f_a(x) = f(x+b+a)-f(x+b)-f(x+a)+f(x)= f_b(x+a)-f_b(x)$ for all $x,a,b\neq 0$. Fix $a,b\neq 0$. Let the degree of $f_a(x)$ be $n>0$. The equation above implies the degrees of $f_a$ and $f_b$ are the same since if , then the degrees of both sides of the equation equal $n-1$ and otherwise both sides of the equation equal $0$ so both $f_a$ and $f_b$ are constant polynomials.
