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 equations has an infinite number of answers in $\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 $(deg(P),deg(Q))=1$. Time allowed for this question was 2 hours.
Problem
Source: Iran 3rd round 2013 - final exam problem 7
Tags: algebra, polynomial, algebra unsolved
30.05.2020 11:41
Bump does this one have elementary solution?
31.05.2020 19:56
a) Consider a sequence $(x_i,y_i)\in S, i=1,2,\dots$ with $\lim_{i\to\infty}x_i=\infty, \lim_{i\to\infty}y_i=\infty$. Otherwise $P=Q=\text{const}$. Let $P_0,Q_0$ be interesting with degrees $n_0,m_0$ and senior coefficients $p_0,q_0$ correspondingly. Then, it easily follows $$\displaystyle \lim_{i\to\infty}\frac{x_i^{n_0}}{y_i^{m_0}}=\frac{q_0}{p_0}\quad (1)$$Suppose $n_0$ is minimal among all interesting pairs. Since any other interesting pair $P,Q$ with degrees $n,m$ and senior coefficients $p,q$ also satisfies $(1)$ we have $$n=kn_0, m=km_0; p=\ell p_0^k, q=\ell q_0^k$$where $k\in\mathbb{N}, \ell\in\mathbb{Q}$. Consider $$P_1(x):=P(x)-\ell(P_0(x))^k\,,\, Q_1(x):=Q(x)-\ell(Q_0(x))^k$$Then $P_1, Q_1$ are also interesting, and with less degrees than $P,Q$. Applying the same argument we get that the polynomials: $$P_2(x):=P(x)-\ell(P_0(x))^k-\ell_1(P_0(x))^{k_1}, Q_1(x):=Q(x)-\ell(Q_0(x))^k-\ell_1(Q_0(x))^{k_1}$$are also interesting, where $k_1<k$. Proceeding this way, we finally get $P_r=Q_r=\text{const}$ for some $r\in\mathbb{N}.$ Thus $$P(x)=R(P_0(x))\,,\, Q(x)=R(Q_0(x))$$where $R(x)\in \mathbb{Q}[x]$.