$P(x)=P(y)$ has infinitely many integer solutions

Question

Determine all polynomials $P(x)$ with integer coefficients such that $P(x)=P(y)$ has infinitely many integer solutions in integer $x$ and $y$ with $x \neq y$.

Choose $P(x)=a_n(x-k)^{2n}+a_{n-1}(x-k)^{2n-2}+...+a_0$, with integers $k,n,a_n,a_{n-1}, ...,a_0$ Then $P(x)=P(2k-x)$ for every integer $x \neq k$, thus satisfy the condition.

Now, I have a gut feeling that if $P(x)=P(y)$ and $x+y=M$, then for every integer $x$, $P(x)=P(M-x)$, but I cannot analyze any futher.

So my question is: Are there any other types of polynomials $P(x)$ that satisfy the orange question above?

(Any answers or comments will be appreciated!)

(If this question should be closed or off topic, please let me know. If this site cannot answer this question, let me know, I will delete this question immediately)

Answer 1

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...

Answer 2

Here's a more abstract proof:

If $P(x) - P(y) =0$ but $x \neq y$ then $ (P(x) - P(y) )/(x-y)=0$. Because this is a polynomial of degree $n-1$, when this identity is satisfied its leading terms $ (x^{n} - y^{n} )/ (x-y)$ must be equal to minus its remaining terms, and thus must be $O( \max(x,y)^{n-2})$.

Now if $n$ is odd, $ (x^{n} - y^{n} )/ (x-y)$ is a homogeneous polynomial of degree $n-1$ with no nozero real roots. Because it has no nonzero real roots, its absolute value has some minimum value $C$ on the boundary of the unit square. Then homogeneity gives $ | (x^{n} - y^{n} )/ (x-y)| \geq C \max(x,y)^{n-1}$ and thus can be $O( \max(x,y)^{n-2})$ for only finitely many $x,y$.

If $n$ is even, $(x^n-y^n)/(x^2-y^2)$ is a homogeneous polynomial of degree $n-2$ with no real roots. By the same logic, we have $| (x^{n} - y^{n} )/ (x^2-y^2)| \geq C \max(x,y)^{n-2}$. Thus if $| (x^{n} - y^{n} )/ (x-y)| = O ( \max(x,y)^{n-2})$ then $C |x+y| = O(1)$. So this can happen for only finitely many values of $|x+y|$.

Thus if it happens infinitely often, it happens infinitely often for one particular value of $x+y$, say $M$, thus $P(x) - P(M-x)$ vanishes for infinitely many $x$ and thus is zero.