Return to Answer

First it is clear (assuming throughout that $P$ is a solution to your problem) that $P$ should have even degree, for if $P$ has odd degree we have $\lim\limits_{n \rightarrow -\infty}P(n) = -\infty$ and $\lim\limits_{n \rightarrow \infty}P(n) = \infty$, which means $P(x)=P(y)$ can only happen when $x$ and $y$ are contained in a bounded interval. So $P=\sum_{i=0}^d a_i x^i$ has even degree, and we may assume by flipping the sign and/or applying a translation if necessary, that $a_d>0$ and $-da_d/2 < a_{d-1} \leq da_d/2$.

First we show that $P(x) > P(-x+1)$ for $x$ sufficiently large. Therefore we calculate $P(x)-P(-x+1)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (1 - x)^d + a_{d-1}(1 - x)^{d-1} + \ldots)$ whose leading term will be $(da_d + 2a_{d-1})x^{d-1}$. which will ensure that $P(x)-P(-x+1)$ tends to infinity when $x$ does, by the lower bound on $a_{d-1}$.

Likewise, we show that $P(x) < P(-x-2)$ for $x$ sufficiently large. This is the same type of calculation: we get $P(x)-P(-x-2)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (-x -2)^d + a_{d-1}(-x - 2)^{d-1} + \ldots)$, which now has leading term $(- 2da_d + 2a_{d-1})x^{d-1}$, which again clearly tends to negative infinity as $x$ grows.

These two inequalities combined mean that we must have either $P(x)=P(-x)$ or $P(x)=P(-x-1)$ for infinitely many $x$. In the first case, write $P=P_{\textrm{even}}+P_{\textrm{odd}}$, then this gets us that $P_{\textrm{odd}}(x)=0$ for infinitely many $x$, so we must have $P_{\textrm{odd}} \equiv 0$, so $P(x)=Q(x^2)$ for some polynomial $Q$. In the second case, we can play the same trick since this time $R(x) := P(x-1/2)$ satisfies $R(x)=R(-x)$, ergo by the same argument we must have $P(x)=Q((x+1/2)^2)$ for some polynomial $Q$.

In conclusion: as the entire solution set to your problem is given by translates of these two types of solutions, we get that all solutions are of the form $Q((x+k/2)^2)$, where $k$ is any integer and $Q$ is any polynomial (to be more accurate of course, I should say the subset of all polynomials of this form that have integer coefficients).

Morover I think it should be easy to prove that this description coincides with the set of polynomials of the form $Q(x^2+ax+b)$, with $a$ and $b$ integers and again $Q$ any polynomial, which avoids dealing with half-integers altogether, but I will leave this as an exercise...

First it is clear (assuming throughout that $P$ is a solution to your problem) that $P$ should have even degree, for if $P$ has odd degree we have $\lim\limits_{n \rightarrow -\infty}P(n) = -\infty$ and $\lim\limits_{n \rightarrow \infty}P(n) = \infty$ (or the same but with the signs of both of the limits reversed of course) which means $P(x)=P(y)$ can only happen when $x$ and $y$ are contained in a bounded interval. So $P=\sum_{i=0}^d a_i x^i$ has even degree, and we may assume by flipping the sign and/or applying a translation if necessary, that $a_d>0$ and $-da_d/2 < a_{d-1} \leq da_d/2$.

First we show that $P(x) > P(-x+1)$ for $x$ sufficiently large. Therefore we calculate $P(x)-P(-x+1)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (1 - x)^d + a_{d-1}(1 - x)^{d-1} + \ldots)$ whose leading term will be $(da_d + 2a_{d-1})x^{d-1}$. which will ensure that $P(x)-P(-x+1)$ tends to infinity when $x$ does, by the lower bound on $a_{d-1}$.

Likewise, we show that $P(x) < P(-x-2)$ for $x$ sufficiently large. This is the same type of calculation: we get $P(x)-P(-x-2)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (-x -2)^d + a_{d-1}(-x - 2)^{d-1} + \ldots)$, which now has leading term $(- 2da_d + 2a_{d-1})x^{d-1}$, which again clearly tends to negative infinity as $x$ grows.

These two inequalities combined mean that we must have either $P(x)=P(-x)$ or $P(x)=P(-x-1)$ for infinitely many $x$. In the first case, write $P=P_{\textrm{even}}+P_{\textrm{odd}}$, then this gets us that $P_{\textrm{odd}}(x)=0$ for infinitely many $x$, so we must have $P_{\textrm{odd}} \equiv 0$, so $P(x)=Q(x^2)$ for some polynomial $Q$. In the second case, we can play the same trick since this time $R(x) := P(x-1/2)$ satisfies $R(x)=R(-x)$, ergo by the same argument we must have $P(x)=Q((x+1/2)^2)$ for some polynomial $Q$.

In conclusion: as the entire solution set to your problem is given by translates of these two types of solutions, we get that all solutions are of the form $Q((x+k/2)^2)$, where $k$ is any integer and $Q$ is any polynomial (to be more accurate of course, I should say the subset of all polynomials of this form that have integer coefficients).

Morover I think it should be easy to prove that this description coincides with the set of polynomials of the form $Q(x^2+ax+b)$, with $a$ and $b$ integers and again $Q$ any polynomial, which avoids dealing with half-integers altogether, but I will leave this as an exercise...

First it is clear (assuming throughout that $P$ is a solution to your problem) that $P$ should have even degree, for if $P$ has odd degree we have $\lim\limits_{n \rightarrow -\infty}P(n) = -\infty$ and $\lim\limits_{n \rightarrow \infty}P(n) = \infty$, which means $P(x)=P(y)$ can only happen when $x$ and $y$ are contained in a bounded interval. So $P=\sum_{i=0}^d a_i x^i$ has even degree, and we may assume by flipping the sign and/or applying a translation if necessary, that $a_d>0$ and $-da_d/2 < a_{d-1} \leq da_d/2$.

First we show that $P(x) > P(-x+1)$ for $x$ sufficiently large. Therefore we calculate $P(x)-P(-x+1)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (1 - x)^d + a_{d-1}(1 - x)^{d-1} + \ldots)$ whose leading term will be $(da_d + 2a_{d-1})x^{d-1}$. which will ensure that $P(x)-P(-x+1)$ tends to infinity when $x$ does, by the lower bound on $a_{d-1}$.

Likewise, we show that $P(x) < P(-x-2)$ for $x$ sufficiently large. This is the same type of calculation: we get $P(x)-P(-x-2)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (-x -2)^d + a_{d-1}(-x - 2)^{d-1} + \ldots)$, which now has leading term $(- 2da_d + 2a_{d-1})x^{d-1}$, which again clearly tends to negative infinity as $x$ grows.

These two inequalities combined mean that we must have either $P(x)=P(-x)$ or $P(x)=P(-x-1)$ for infinitely many $x$. In the first case, write $P=P_{\textrm{even}}+P_{\textrm{odd}}$, then this gets us that $P_{\textrm{odd}}(x)=0$ for infinitely many $x$, so we must have $P_{\textrm{odd}} \equiv 0$, so $P(x)=Q(x^2)$ for some polynomial $Q$. In the second case, we can play the same trick since this time $R(x) := P(x-1/2)$ satisfies $R(x)=R(-x)$, ergo by the same argument we must have $P(x)=Q((x+1/2)^2)$ for some polynomial $Q$.

In conclusion: as the entire solution set to your problem is given by translates of these two types of solutions, we get that all solutions are of the form $Q((x+k/2)^2)$, where $k$ is any integer and $Q$ is any polynomial (to be more accurate of course, I should say the subset of all polynomials of this form that have integer coefficients).

First it is clear (assuming throughout that $P$ is a solution to your problem) that $P$ should have even degree, for if $P$ has odd degree we have $\lim\limits_{n \rightarrow -\infty}P(n) = -\infty$ and $\lim\limits_{n \rightarrow \infty}P(n) = \infty$, which means $P(x)=P(y)$ can only happen when $x$ and $y$ are contained in a bounded interval. So $P=\sum_{i=0}^d a_i x^i$ has even degree, and we may assume by flipping the sign and/or applying a translation if necessary, that $a_d>0$ and $-da_d/2 < a_{d-1} \leq da_d/2$.

First we show that $P(x) > P(-x+1)$ for $x$ sufficiently large. Therefore we calculate $P(x)-P(-x+1)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (1 - x)^d + a_{d-1}(1 - x)^{d-1} + \ldots)$ whose leading term will be $(da_d + 2a_{d-1})x^{d-1}$. which will ensure that $P(x)-P(-x+1)$ tends to infinity when $x$ does, by the lower bound on $a_{d-1}$.

Likewise, we show that $P(x) < P(-x-2)$ for $x$ sufficiently large. This is the same type of calculation: we get $P(x)-P(-x-2)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (-x -2)^d + a_{d-1}(-x - 2)^{d-1} + \ldots)$, which now has leading term $(- 2da_d + 2a_{d-1})x^{d-1}$, which again clearly tends to negative infinity as $x$ grows.

These two inequalities combined mean that we must have either $P(x)=P(-x)$ or $P(x)=P(-x-1)$ for infinitely many $x$. In the first case, write $P=P_{\textrm{even}}+P_{\textrm{odd}}$, then this gets us that $P_{\textrm{odd}}(x)=0$ for infinitely many $x$, so we must have $P_{\textrm{odd}} \equiv 0$, so $P(x)=Q(x^2)$ for some polynomial $Q$. In the second case, we can play the same trick since this time $R(x) := P(x-1/2)$ satisfies $R(x)=R(-x)$, ergo by the same argument we must have $P(x)=Q((x+1/2)^2)$ for some polynomial $Q$.

In conclusion: as the entire solution set to your problem is given by translates of these two types of solutions, we get that all solutions are of the form $Q((x+k/2)^2)$, where $k$ is any integer and $Q$ is any polynomial (to be more accurate of course, I should say the subset of all polynomials of this form that have integer coefficients).

Morover I think it should be easy to prove that this description coincides with the set of polynomials of the form $Q(x^2+ax+b)$, with $a$ and $b$ integers and again $Q$ any polynomial, which avoids dealing with half-integers altogether, but I will leave this as an exercise...

First it is clear (assuming throughout that $P$ is a solution to your problem) that $P$ should have even degree, for if $P$ has odd degree we have $\lim\limits_{n \rightarrow -\infty}P(n) = -\infty$ and $\lim\limits_{n \rightarrow \infty}P(n) = \infty$, which means $P(x)=P(y)$ can only happen when $x$ and $y$ are contained in a bounded interval. So $P=\sum_{i=0}^d a_i x^i$ has even degree, and we may assume by flipping the sign and/or applying a translation if necessary, that $a_d>0$ and $-da_d/2 < a_{d-1} \leq da_d/2$.

First we show that $P(x) > P(-x+1)$ for $x$ sufficiently large. Therefore we calculate $P(x)-P(-x+1)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (1 - x)^d + a_{d-1}(1 - x)^{d-1} + \ldots)$ whose leading term will be $(da_d + 2a_{d-1})x^{d-1}$. which will ensure that $P(x)-P(-x+1)$ tends to infinity when $x$ does, by the lower bound on $a_{d-1}$.

Likewise, we show that $P(x) < P(-x-2)$ for $x$ sufficiently large. This is the same type of calculation: we get $P(x)-P(-x-2)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (-x -2)^d + a_{d-1}(-x - 2)^{d-1} + \ldots)$, which now has leading term $(- 2da_d + 2a_{d-1})x^{d-1}$, which again clearly tends to negative infinity as $x$ grows.

These two inequalities combined mean that we must have either $P(x)=P(-x)$ or $P(x)=P(-x-1)$ for infinitely many $x$. In the first case, write $P=P_{\textrm{even}}+P_{\textrm{odd}}$, then this gets us that $P_{\textrm{odd}}(x)=0$ for infinitely many $x$, so we must have $P_{\textrm{odd}} \equiv 0$, so $P(x)=Q(x^2)$ for some polynomial $Q$. In the second case, we can play the same trick since this time $R(x) := P(x-1/2)$ satisfies $R(x)=R(-x)$, ergo by the same argument we must have $P(x)=Q((x+1/2)^2)$ for some polynomial $Q$.

In conclusion: as the entire solution set to your problem is given by translates of these two types of solutions, we get that all solutions are of the form $Q((x+k/2)^2)$, where $k$ is any integer and $Q$ is any polynomial.

First it is clear (assuming throughout that $P$ is a solution to your problem) that $P$ should have even degree, for if $P$ has odd degree we have $\lim\limits_{n \rightarrow -\infty}P(n) = -\infty$ and $\lim\limits_{n \rightarrow \infty}P(n) = \infty$, which means $P(x)=P(y)$ can only happen when $x$ and $y$ are contained in a bounded interval. So $P=\sum_{i=0}^d a_i x^i$ has even degree, and we may assume by flipping the sign and/or applying a translation if necessary, that $a_d>0$ and $-da_d/2 < a_{d-1} \leq da_d/2$.

First we show that $P(x) > P(-x+1)$ for $x$ sufficiently large. Therefore we calculate $P(x)-P(-x+1)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (1 - x)^d + a_{d-1}(1 - x)^{d-1} + \ldots)$ whose leading term will be $(da_d + 2a_{d-1})x^{d-1}$. which will ensure that $P(x)-P(-x+1)$ tends to infinity when $x$ does, by the lower bound on $a_{d-1}$.

Likewise, we show that $P(x) < P(-x-2)$ for $x$ sufficiently large. This is the same type of calculation: we get $P(x)-P(-x-2)=(a_d x^d + a_{d-1}x^{d-1} + \ldots) - (a_d (-x -2)^d + a_{d-1}(-x - 2)^{d-1} + \ldots)$, which now has leading term $(- 2da_d + 2a_{d-1})x^{d-1}$, which again clearly tends to negative infinity as $x$ grows.

These two inequalities combined mean that we must have either $P(x)=P(-x)$ or $P(x)=P(-x-1)$ for infinitely many $x$. In the first case, write $P=P_{\textrm{even}}+P_{\textrm{odd}}$, then this gets us that $P_{\textrm{odd}}(x)=0$ for infinitely many $x$, so we must have $P_{\textrm{odd}} \equiv 0$, so $P(x)=Q(x^2)$ for some polynomial $Q$. In the second case, we can play the same trick since this time $R(x) := P(x-1/2)$ satisfies $R(x)=R(-x)$, ergo by the same argument we must have $P(x)=Q((x+1/2)^2)$ for some polynomial $Q$.

In conclusion: as the entire solution set to your problem is given by translates of these two types of solutions, we get that all solutions are of the form $Q((x+k/2)^2)$, where $k$ is any integer and $Q$ is any polynomial (to be more accurate of course, I should say the subset of all polynomials of this form that have integer coefficients).