$P(x)$ is a monoic polynomial with integer coefficients so that there exists monoic integer coefficients polynomials $p_1(x),p_2(x),\dots ,p_n(x)$ so that for any natural number $x$ there exist an index $j$ and a natural number $y$ so that $p_j(y)=P(x)$ and also $deg(p_j) \ge deg(P)$ for all $j$.Show that there exist an index $i$ and an integer $k$ so that $P(x)=p_i(x+k)$.
Problem
Source: Iranian third round 2019 Finals Algebra exam problem 2
Tags: algebra, polynomial
24.08.2019 17:52
<Sketch of the Proof> Let the degree of $P$ be $A$ and $p_i$ be $a_i$. The idea is simple, we want to choose some consecutive numbers big enough so that 1. For $a_i>A$, $P(x)=p_i(y)$ cannot appear twice. 2. For $a_i=A$, $P(x_1)=p_i(y_1), P(x_2)=p_i(y_2)$ implies $x_1 - y_1 = x_2 - y_2$. This can be done by careful scaling argument by using $Q(x)=P(x)-P(x-1)$ and $q_i (x)=p_i (x)-p_i (x-1)$. By 1 and 2, there exists some $i$ such that $a_i=A$ and $P(x_0+m)=p_i(y_0+m)$ for at least $A+1$ natural numbers. Therefore, $P(x_0+z)-p_i(y_0+z)=0$ is the identity and $P(x)=p_i(x+k)$ where $k=y_0-x_0$. Comment: Monic is necessary since $P(x)=x, p_1(x)=2x, p_2(x)=2x+1$ satisfy the condition. <Explicit Proof> When $\epsilon>0$ is given, there exists $M$ satisfying followings. (Same for $p_i$ and $q_i$) Con1. $B=\left\{ x : P(x)>M \right\}$ is a set of consecutive numbers and $P$ is strictly increasing in $B$. Con2. For $P(x)>M$, $x^A (1-\epsilon) <P(x) < x^A (1+\epsilon)$. Con3. For $P(x)>M$, $x^{A-1} (1-\epsilon) <Q(x)/A < x^{A-1} (1+\epsilon)$. Con4. For $P(x)>M$, $P(x+An)/P(x)<1+\epsilon$. From Con2 and Con3, we get following inequality. $(1-\epsilon) \times (P(x)/(1+\epsilon))^{1-1/A}<Q(x)/A<(1+\epsilon) \times (P(x)/(1-\epsilon))^{1-1/A} $ Choose any $x, x+1, ..., x+An$ in $B$ with sufficiently large $x$. 1. $a_i \ne A$. If $P(x+s)=p_i(y)$ and $P(x+t)=p_i(z)$ for $s>t$, $P(x+s)-P(x+t)=Q(x+s)+...+Q(x+t+1)$ $<(s-t)(1+\epsilon) \times ((P(x+s)/(1-\epsilon))^{1-1/A}$ and $p_i(y)-p_i(z) \ge p_i(y)-p_i(y-1)=q_i(y) >(1-\epsilon) \times (p_i(y)/(1+\epsilon))^{1-1/a_i}$. Choose $M$ sufficiently large, then $P(x+s)-P(x+t)<p_i (y)-p_i(z)$. 2. $a_i = A$. If $P(x+s)=p_i(y)$ and $P(x+t)=p_i(z)$ for $s>t$, $(s-t)(1-\epsilon) \times ((P(x+t)/(1+\epsilon))^{1-1/A} < P(x+s)-P(x+t) <(s-t)(1+\epsilon) \times ((P(x+s)/(1-\epsilon))^{1-1/A}$ and $(y-z)(1-\epsilon) \times ((p_i(z)/(1+\epsilon))^{1-1/A} < p_i(y)-p_i(z)<(y-z)(1+\epsilon) \times ((p_i(y)/(1-\epsilon))^{1-1/A}$ By Con4, $y-z=s-t$. Therefore 1 and 2 on Sketch holds and the problem is solved.
22.08.2022 14:03
Lemma 1:if the polynomials $P(x)$ and $Q(x)$ with integer coefficients are monic and with the same degree , then there exist a number $k \in \mathbb {Z}$ such that for each big enough real number $x$ , we have : $$Q(x+k-1)<P(x)<Q(x+k+1)$$ Proof: Suppose that $P(x)=x^n+a_{n-1}x^{n-1}+...+a_0$ and $Q(x)=x^n+b_{n-1}x^{n-1}+...+b_0$. so one can easily see that the coefficient of $x^{n-1}$ in polynomials $Q(x+k-1)$ and $Q(x+k+1)$ is $k+b_{n-1}-1$ and $k+b_{n-1}+1$ respectively. so if we put $k=a_{n-1}-b_{n-1}$ , then we have $k+b_{n-1}-1 < a_{n-1} < k+b_{n-1}+1$ and as the result for every big enough real $x$ , we have $Q(x+k-1)<P(x)<Q(x+k+1)$. so we're done. Lemma 2:for monic polynomials $P(x)$ and $Q(x)$ with $deg(Q)>deg(P)$ , suppose that for each natural number $x$ , $x_{Q(x)}$ be the biggest natural number such that $Q(x_{Q(x)}) \le P(x)$. Then if $r \in \mathbb{N}$ is constant, for each natural number $M$ and big enough number $x$ we have : $$\frac{x-r}{x_{Q(x)}} \ge M$$ Proof:Since $Q(x)$ is monic , so this polynomial will eventually be increasing and if for a big enough $x$ we have $x_{Q(x)} \ge \frac{x-r}{M}$ , then one can see that : $$Q(\frac{x-r}{M})<Q(x_{Q(x)}) \le P(x)$$while we have $deg(Q)>deg(P)$ and for each big enough $x$ , there is $Q(\frac{x-r}{M})>P(x)$ which is a contradiction. So we're done. Now , firstly one can suppose that for each $i\le n$ , there is infinitely many $x \in \mathbb{N}$ such that for a natural $y$ , $P(x)=P_i(y)$. ( ignore the others and suppose that there are $r$ natural numbers $x$ such that $P(x)$ equals to value of one of these polynomials in a natural point. ) So we'll show that there is a number $i \le n$ such that $deg(P_i)=deg(P)$. Suppose not and for each $i$ , $deg(P_i)>deg(P)$ , now by lemma 2 , for each big enough natural $x$ and each $i$ , we have : $$\frac{x-r}{x_{P_i(x)}} \ge n(deg(P)+1) (I)$$now notice that by Pigeonhole principle , there exist a $i\le n$ such that there are at least $\frac{x-r}{n}$ natural values from $1$ to $x$ like $t$ , such there exist a $y_t \in \mathbb{N}$ which $P(t)=P_i(y_t)$. Also since $y_t \le x_{P_i(x)}$ so by inequality $I$ and Pigeonhole principle again , there are naturals $x_1 , x_2 , ... , x_{deg(P)+1}$ less than $x$ , such that : $$P(x_1)=P(x_2)=...=P(x_{deg(P)+1})$$So as the result , the polynomial $P(x)$ is constant , which is a contradiction. So there is a $i\le n$ such that $deg(P_i)=deg(P)$. Now by lemma 1 , there is an integer $k$ such that for each big enough real $x$ we have : $$P_i(x+k-1)<P(x)<P_i(x+k+1)$$So choosing a big enough $x$ such that for $y \ge x$ values ,$ P_i(y)$ be increasing , then for each $y \le x+k-1$ , $P_i(y)<P(x)$ and for each $y \ge x+k+1$ , we have $P_i(y)>P(x)$. As the result for infinitely many naturals $x$ , we get $P(x)=P_i(x+k)$ and so $P(x) \equiv P_i(x+k)$. So we're done.
22.09.2022 09:45
An easier problem with similar main idea : Suppose that for polynomial $P(x) \in \mathbb Z[x]$ , there exist infinitely many distinct integers $x ,y \in \mathbb{Z}$ such that : $$xP(x)=yP(y)$$Prove that the polynomial $P(x)$ , has an integer root.