# Determine all pairs$(P, d)$ of a polynomial $P$ with integer coefficients

Determine all pairs$$(P, d)$$ of a polynomial $$P$$ with integer coefficients and an integer $$d$$ such that the equation $$P(x)−P(y) = d$$ has infinitely many solutions in integers $$x$$ and $$y$$ with $$x \ne y$$,

I think d has to equal zero for there to be infinite solutions but im not sure

Also I know that d is divisible by $$x-y$$ because the difference between the polynomials results in a multiple of $$x-y$$

from the 2017 SAMO senior round 3 http://www.samf.ac.za/content/files/QuestionPapers/s3q2017.pdf

• multivariate, univariate, degree 2 or higher ?
– user645636
Commented Aug 10, 2019 at 15:12
• @Roddy MacPhee: From the context, assume $P\in\mathbb{Z}[x]$, but no other restictions. Commented Aug 10, 2019 at 15:38
• I wasn't really asking that @quasi . I was asking why it was so complicated for the OP.
– user645636
Commented Aug 10, 2019 at 15:40
• @Roddy MacPhee: The OP gave a link to the actual contest, so with regard to your question about restrictions, you can refer to the actual contest question. Commented Aug 10, 2019 at 15:41
• No. It would refer to the fact that it has a simple answer. Anyone , not thinking only of what I talked about, would have an instant answer. @quasi
– user645636
Commented Aug 10, 2019 at 15:45

For $$P\in\mathbb{Z}[t]$$ and $$d\in\mathbb{Z}$$, let $$S(P,d)$$ be the set of pairs $$(x,y)$$ of distinct integers such that $$P(x)-P(y)=d$$.

The goal is to find all pairs $$(P,d)$$ such that $$S(P,d)$$ is infinite.

I'll give a solution for the case $$d\ne 0$$, and a partial solution for the case $$d=0$$ . . .

Case $$(1)$$:$$\;d\ne 0$$.

Thus, let $$d$$ be a nonzero integer, and let $$K$$ be the set of integer divisors of $$d$$.

Claim:$$\;S(P,d)$$ is infinite if and only if $$P=at+b$$ for some integer $$b$$ and some $$a\in K$$.

First suppose $$P=at+b$$ for some integer $$b$$ and some $$a\in K$$.

Write $$d=ak$$, for some $$k\in K$$.

Then for $$x,y\in\mathbb{Z}$$, we have \begin{align*} &P(x)-P(y)=d \qquad\qquad\qquad\qquad\qquad\qquad \\[4pt] \iff\;&(ax+b)-(ay+b)=d\\[4pt] \iff\;&a(x-y)=d\\[4pt] \iff\;&x-y=k\\[4pt] \end{align*} hence $$(y+k,y)\in S(P,d)$$ for all integers $$y$$, so $$S(P,d)$$ is infinite.

Conversely, suppose $$S(P,d)$$ is infinite.

Then for $$x,y\in\mathbb{Z}$$ with $$x\ne y$$, \begin{align*} &P(x)-P(y)=d \qquad\qquad\qquad\qquad\qquad\qquad \\[4pt] \implies\;&(x-y){\,\mid\,}d\\[4pt] \implies\;&x=y+k,\;\text{for some}\;k\in K\\[4pt] \end{align*} Since $$S(P,d)$$ is infinite and $$K$$ is finite, it follows that there is some $$k\in K$$ such that the equation $$P(y+k)-P(y)=d \qquad\qquad\qquad\qquad$$ holds for infinitely many integers $$y$$.

Then letting $$f\in\mathbb{Z}[t]$$ be given by $$f(t)=P(t+k)-P(t)-d$$, we get that $$f$$ has infinitely many zeros, hence $$f$$ must be identically $$0$$. \begin{align*} \text{Then}\;&f=0\\[4pt] \implies\;&P(t+k)-P(t)-d=0\\[4pt] \implies\;&P'(t+k)-P'(t)=0\\[4pt] &\;\;\;\text{[where P'\in\mathbb{Z}[t] is the formal derivative of P]}\\[4pt] \implies\;&P'=a,\;\text{for some integer}\;a\\[4pt] \implies\;&P=at+b,\;\text{for some integers}\;a,b\\[4pt] \end{align*} Then letting $$x,y$$ be distinct integers such that $$P(x)-P(y)=d$$, we get \begin{align*} &P(x)-P(y)=d\\[4pt] \implies\;&(ax+b)-(ay+b)=d \qquad\qquad\qquad\qquad\qquad \\[4pt] \implies\;&a(x-y)=d\\[4pt] \implies\;&a\in K\\[4pt] \end{align*} so $$P=at+b$$ for some integer $$b$$ and some $$a\in K$$, as claimed.

This completes the analysis for case $$(1)$$.

Case $$(2)$$:$$\;d=0$$.

For this case, I'll identify a class of polynomials $$f\in\mathbb{Z}[t]$$ such that $$S(f,0)$$ is infinite, and I'll conjecture that there are no others.

Let $$V$$ be the set of all polynomials $$f\in\mathbb{Z}[t]$$ such that $$S(f,0)$$ is infinite.

Some properties of the set $$V$$ . . .

Property $$(0)$$:$$\;$$If $$f\in\mathbb{Z}[t]$$ and $$\deg(f)$$ is odd, then $$f\not\in V$$.

Proof:$$\;$$Since $$\deg(f)$$ is odd, there exists $$\theta\in (0,\infty)$$ such that if $$x,y\in\mathbb{R}$$ with $$x\ne y$$ satisfy the equation $$f(x)=f(y)$$, then $$x,y\in (-\theta,\theta)$$.

Thus $$(x,y)\in S(f,0)$$ implies $$x,y\in (-\theta,\theta)$$, hence $$S(f,0)$$ is finite, so $$f\not\in V$$.

Property $$(1)$$:$$\;t^2\in V$$.

Proof:$$\;$$For all nonzero integers $$y$$, we have $$(-y,y)\in S(t^2,0)$$, hence $$S(t^2,0)$$ is infinite, so $$t^2\in V$$.

Property $$(2)$$:$$\;t^2+t\in V$$.

Proof:$$\;$$Let $$f=t^2+t$$.

Let $$y\in\mathbb{Z}$$ and let $$x=-y-1$$.

Then we have $$x\ne y$$ and $$f(x)=x^2+x=(-y-1)^2+(-y-1)=(y^2+2y+1)-(y+1)=y^2+y=f(y)$$ thus for all $$y\in\mathbb{Z}$$, we have $$(-y-1,y)\in S(t^2+t,0)$$, hence $$S(f,0)$$ is infinite, so $$t^2+t\in V$$.

Property $$(3)$$:$$\;$$If $$f\in V$$, then $$f(t+a)\in V$$ for all $$a\in\mathbb{Z}$$.

Proof:$$\;$$Let $$a\in\mathbb{Z}$$ and let $$g=f(t+a)$$.

Then $$(x,y)\in S(f,0)$$ implies $$(x-a,y-a)\in S(g,0)$$, hence $$S(g,0)$$ is infinite, so $$g\in V$$.

Property $$(4)$$:$$\;$$If $$f\in V$$ and $$g\in\mathbb{Z}[t]$$, then $$g\circ f\in V$$.

Proof:$$\;$$Let $$(x,y)\in S(f,0)$$. \begin{align*} \text{Then}\;\;&(x,y)\in S(f,0) \qquad\qquad\qquad\qquad\qquad\qquad\qquad \\[4pt] \implies\;&f(x)=f(y)\\[4pt] \implies\;&g(f(x))=g(f(y))\\[4pt] \implies\;&(g\circ f)(x)=(g\circ f)(y)\\[4pt] \implies\;&(x,y)\in S(g\circ f,0)\\[4pt] \end{align*} hence $$S(g\circ f,0)$$ is infinite, so $$g\circ f\in V$$.

Combining properties $$(1),(2),(3),(4)$$, we get

Property $$(*)$$:$$\;$$If $$f=g\bigl((t+a)^2\bigr)$$ or $$f=g\bigl((t+a)^2+(t+a)\bigr)$$ where $$g\in\mathbb{Z}[t]$$ and $$a\in\mathbb{Z}$$, then $$f\in V$$.

What about the converse of property $$(*)$$?

Conjecture:$$\;$$If $$f\in V$$, then for some $$g\in\mathbb{Z}[t]$$ and some $$a\in\mathbb{Z}$$, either $$f=g\bigl((t+a)^2\bigr)$$ or $$f=g\bigl((t+a)^2+(t+a)\bigr)$$.