3
$\begingroup$

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.

Any suggestions, answers, comments, edits will be appreciated.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.