# Interesting equation $P(x)=Q(y)$, with infinite integer solutions $(x,y)$

An equation $$P(x)=Q(y)$$ is called Interesting if $$P$$ and $$Q$$ are polynomials with degree at least one and integer coefficients and the equation has an infinite number of answers in $$\mathbb{N} \times \mathbb{N}$$.

An interesting equation $$P(x)=Q(y)$$ yields in interesting equation $$F(x)=G(y)$$ if there exists polynomial $$R(x) \in \mathbb{Q} [x]$$ such that $$F(x) \equiv R(P(x))$$ and $$G(x) \equiv R(Q(x))$$.

a. Suppose that $$S$$ is an infinite subset of $$\mathbb{N} \times \mathbb{N}$$. $$S$$ is an answer of interesting equation $$P(x)=Q(y)$$ if each element of $$S$$ is an answer of this equation. Prove that for each $$S$$ there's an interesting equation $$P_0(x)=Q_0(y)$$ such that if there exists any interesting equation that $$S$$ is an answer of it, $$P_0(x)=Q_0(y)$$ yields in that equation.

b. Define the degree of an interesting equation $$P(x)=Q(y)$$ by $$max\{deg(P),deg(Q)\}$$. An interesting equation is called primary if there's no other interesting equation with lower degree that yields in it. Prove that if $$P(x)=Q(y)$$ is a primary interesting equation and $$P$$ and $$Q$$ are monic then $$gcd(deg(P),deg(Q))=1$$.

The two problems are originated from the 2013 Iranian Math Olympiad, 3rd Round. I have not been able to solve any of the problems, and I cannot find the solutions elsewhere.

Here is my current sketch for problem a. :

Step 1: Suppose that $$S$$ is an answer of infinitely many interesting equations, including the two interesting equations $$P(x)=Q(y)$$ and $$F(x)=G(y)$$.

Lemma 1.1: Without loss of generality assume that the leading coefficients of $$P$$ and $$F$$ are positive integers. Then the leading coefficients of $$Q$$ and $$G$$ must also be positive integers.

• If not, then $$\lim Q(y) = - \infty$$, $$\lim P(x) = + \infty$$, so the equation has a finite number of answers in $$\mathbb{N} \times \mathbb{N}$$, a contradiction.

Lemma 1.2: Without loss of generality assume that $$deg(P) \leq deg(Q)$$. Then $$deg(F)$$ must be less than or equal to $$deg(G)$$.

• Since $$deg(P) \leq deg(Q)$$, there are infinite answers $$(x, y)$$ in $$S$$, such that $$x < y$$. Therefore, since $$F(x)=G(y)$$ has infinite solutions $$(x, y)$$ in $$S$$, $$deg(F)$$ must be less than or equal to $$deg(G)$$

Lemma 1.3: Without loss of generality assume that $$deg(P) \leq deg(Q)$$ and $$deg(P) \leq deg(F)$$. Then $$deg(P) < deg(F)$$ if and only if $$deg(Q) < deg(G)$$. Moreover $$deg(P) = deg(F)$$ if and only if $$deg(Q) = deg(G)$$.

• Consider the case in which $$deg(P) < deg(F)$$.

• If $$deg(Q) > deg(G) \geq deg(F) > deg(P)$$ then the leading coefficient of $$F-P$$ is positive, while the leading coefficient of $$G-Q$$ is negative. This contradicts Lemma 1.1 (Note that $$S$$ is also an answer of the interesting equation $$F(x)-P(x)=G(y)-Q(y)$$).

• If $$deg(Q) = deg(G)$$, then the leading coefficient of $$F-aP$$ is positive, while the leading coefficient of $$G-aQ$$ is negative ($$a$$ is the positive integer such that the leading coefficient of $$aQ$$ is greater than $$G$$'s). This also contradicts Lemma 1.1 (Note that $$S$$ is an answer of the interesting equation $$F(x)-aP(x)=G(y)-aQ(y)$$).

• Therefore $$deg(P) < deg(F)$$ if and only if $$deg(Q) < deg(G)$$.

• With arguments similar to the above, it can be proven that $$deg(P) = deg(F)$$ if and only if $$deg(Q) = deg(G)$$.

Lemma 1.4: $$\frac{deg(P)}{deg(Q)}=\frac{deg(F)}{deg(G)}$$, regardless of whether $$deg(P)$$ is less than $$deg(Q)$$, $$deg(F)$$ or not.

• Note that $$S$$ is the answer of the interesting equations $$P^{deg(F)}(x)=Q^{deg(F)}(y)$$ and $$F^{deg(P)}(x)=G^{deg(P)}(y)$$.
• Thus according to Lemma 1.3 , $$deg(Q^{deg(F)}) = deg(G^{deg(P)})$$; in other words, $$deg(Q) \times deg(F) = deg(P) \times deg(G)$$, or $$\frac{deg(P)}{deg(Q)}=\frac{deg(F)}{deg(G)}$$.

Step 2: Lemma 2: Assume that $$P(x)=Q(y)$$ is the equation with the smallest degree, of all equations of which $$S$$ is the answer. Then $$deg(P)|deg(F)$$ and $$deg(Q)|deg(G)$$

• I wasn't able to prove Lemma 2. But if problem b. is proven, then Lemma 2 might be able to be proven with the similar techniques.

Step 3: Lemma 3: If $$deg(P)|deg(F)$$ and $$deg(Q)|deg(G)$$, then $$P(x)=Q(y)$$ yields in the equation $$F(x)=G(y)$$ (With definition of $$P,Q,F,G$$ similar to Step 1 and 2).

• Let $$k = \frac{deg(F)}{deg(P)} = \frac{deg(G)}{deg(Q)}$$. Let $$p,q,f,g$$ be the leading coefficient of $$P,Q,F,G$$ respectively, and without loss of generality assume that $$gcd(p,q)=gcd(f,g)=1$$. It can be seen that $${f} \times P^k(x)={f}\times Q^k(y)$$ and $${p^k} \times F(x)={p^k}\times G(y)$$ are interesting equations, and according to Lemma 1.3, it can be proven that $$f = p^k, g = q^k$$. Therefore $$U(x) = {f} \times P^k(x) - {p^k} \times F(x) = {f}\times Q^k(y) - {p^k}\times G(y) = V(y)$$ is an interesting equation, with $$deg(U) < deg(F)$$ and $$deg(V) < deg(G)$$. From Lemma 2, it can be seen that $$deg(P)|deg(U)$$ and $$deg(Q)|deg(V)$$.

• Continuing the process similar to the above by changing $$F$$ with $$U$$, $$G$$ with $$V$$, with the fact that $$S$$ is also the answer of $$U(x)=V(y)$$, it can be achieved that $$P(x)=Q(y)$$ yields in $$F(x)=G(y)$$, and problem a. is solved.

To conclude, here are my questions:

How can I solve the two original problems ?

Can I solve them using my ideas above ?

If a solution or the question has been posted, please let me know.

This is a full solution for a.

Let $$S$$ be an infinite subset of $$\mathbb{N}^2$$ and $$P(x)=Q(y)$$ be an interesting equation for which $$S$$ is an answer.

Write $$S=\{(x_i,y_i)|i \geq 1\}$$ any enumeration.

So we have $$P(x_i)=Q(y_i)$$. Assume $$y_{\varphi(i)}$$ is constant: then $$P(x_{\varphi(i)})$$ is constant, so since $$x_{\varphi(i)}$$ is injective, $$P$$ is constant, a contradiction.

So (similarly) $$x_i$$ and $$y_i$$ both go to infinity.

Let then $$p$$ be the degree of $$P$$ ($$\alpha$$ the dominant coefficient), $$q$$ be the degree of $$Q$$ ($$\beta$$ the dominant coefficient), then $$\frac{P(x_i)}{\alpha x_i^p}$$ and $$\frac{Q(y_i)}{\beta y_i^q}$$ go to $$1$$ as $$i$$ goes to infinity.

Therefore, $$\frac{\alpha}{\beta}\frac{x_i^p}{y_i^q}$$ goes to $$1$$ as $$i$$ goes to infinity.

This shows that $$\alpha$$ and $$\beta$$ have the same sign, and that $$p/q$$, $$(|\alpha|/|\beta|)^{1/q}$$ have to be constants (say, $$r$$ and $$\delta$$), depending only on $$S$$ (and more precisely on any infinite subset of $$S$$)

So assume now that $$P(x)=Q(y)$$ is an interesting equation with answer any cofinite subset of $$S$$ such that the degree of $$Q$$ is minimal.

Let $$P_1(x)=Q_1(y)$$ be an interesting equation with answer a cofinite subset of $$S$$ such that $$P(x)=Q(y)$$ does not yield to it, such that $$Q_1$$ has minimal degree (and among these, such that $$|\alpha|+|\beta|$$ is minimal).

If $$Q_1$$ and $$Q$$ have the same degree, then so do $$P_1$$ and $$P$$, and by the above (with the same notations) $$(\alpha_1,\beta_1)$$ and $$(\alpha,\beta)$$ are proportional: let $$c,c_1$$ be nonzero integers such that $$c_1\alpha_1=c\alpha$$ (same for $$\beta$$).

Then $$(cP-c_1P_1,cQ-c_1Q_1)$$ has a cofinite subset of $$S$$ as an answer, and a lower degree, so it cannot be interesting and thus the polynomials are constants, so $$(P,Q)$$ yields in $$(P_1,Q_1)$$, a contradiction.

So $$Q_1$$ has a higher degree than $$Q$$. Let us write Euclidean divisions in $$\mathbb{Q}[X]$$, $$P_1=A_1P+A_2$$, $$Q_1=B_1Q+B_2$$. Up to multiplication by an integer constant, we may assume that all the polynomials have integer coefficients.

So we have on a cofinite subset of $$S$$, $$(A_1(x_i)-B_1(y_i))P(x_i)=A_2(x_i)-B_2(y_i)$$.

Since $$A_2,B_2$$ have lower degrees than $$P,Q$$, $$A_2(x_i)$$ and $$B_2(y_i)$$ are negligible before $$P(x_i)=Q(y_i)$$. So their difference is negligible before $$(A_1(x_i)-B_1(y_i))P(x_i)$$ (on the subset of $$i$$ such that $$A_1(x_i) \neq B_1(y_i)$$).

As a conclusion, on a cofinite subset of $$S$$, $$A_1(x_i)=B_1(y_i)$$ and thus $$A_2(x_i)=B_2(y_i)$$. By minimality of $$P,Q$$, $$A_2$$ and $$B_2$$ are constants, and $$A_1,B_1$$ (by mininality of $$P_1,Q_1$$) are yielded in by $$P,Q$$. We get a contradiction.