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

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?

(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)

• It seems easy to see at least that $P$ must be of even degree. – Seva Jun 14 at 18:53
• Very probably something very much like what you claim is true, except it can't be completely correct since $P(x)=x^2+x$ also works, which satisfies $P(x) = P(-1-x)$. There is a subtlety in that the symmetry-axis can oocur for a half-integral $x$-value. – RP_ Jun 14 at 19:02
• @RP_ so, $M=-1$. – Konstantinos Gaitanas Jun 14 at 19:11
• @KonstantinosGaitanas That is clear. My point was that the formula given earlier in the post does not apply in that case. – RP_ Jun 14 at 19:16

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

• The limit argument is not quite right, because the function $\lfloor x/2 \rfloor$ satisfies this limit condition but doesn't have finitely many solutions. But of course your overall point is right - you just need to say in addition that the function is monotonic outside a bounded interval, for instance. – Will Sawin Jun 18 at 19:39
• Thank you Will, you are of course absolutely right. I will fix this at some point, together with the omitted argument for the statement in the final paragraph. – RP_ Jun 19 at 8:18

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.