I think that it would be true when d is even

Yup it is.

We let $k$ denote the degree instead of $d$. We shall prove the problem for all degree $k$. Note that $P(x)$ satisfies the conditions if and only if $mP(x)$ does for any integer $m$. Let $$P(x) = a_k x^k + a_{k-1}x^{k-1} + \cdots + a_0$$be a polynomial that works. Then by changing $x$ to $x + \frac{a_{k-1}}{k a_k}$ and clearing denominators, we get a polynomial which works whose $x^{n-1}$ coefficient is zero. We can also multiply by a suitable multiple such that the $x^k$ coefficient is a $k^{th}$ power and we can absorb it in. Hence we can assume that $a_k = 1, a_{k-1} = 0$. Also, we further assume that all $x_i$ are positive as at least half the $x_i$'s have the same sign and we can consider those with the negative case being similar. Now let $$\frac{P(x_1)}{P(x_i)} = \frac{p_1^k}{p_i^k}$$where $p_1,p_i$ are naturals such that $\gcd(p_1,p_i) = 1$. Then we have $p_i^kP(x_1) = p_1^kP(x_i)$ which rearranges into $$(p_ix_1)^k - (p_1x_i)^k= a_{k-2}(p_1^k x_i^{k-2} - p_i^k x_1^{k-2}) + \cdots + a_0(p_1^k - p_i^k)$$$$\implies (p_ix_1 - p_1x_i)( (p_ix_1)^{k-1} + (p_ix_1)^{k-2}p_1x_i + \cdots + (p_1x_i)^{k-1})$$$$= a_{k-2}(p_1^k x_i^{k-2} - p_i^k x_1^{k-2}) + \cdots + a_0(p_1^k - p_i^k).$$Now if $p_ix_1 - p_1x_i \not = 0$, the LHS is $O((p_ix_i)^{k-1})$ while the RHS is $O(p_i^kx_i^{k-2})$ since $p_1^k < 2p_i^k$ where our bound depends only on the coefficients. Hence if we can show that for any constant $C > 0$, there must exist $i$ such that $p_i < \frac{x_i}{C}$ then it must be that $p_ix_1 = p_1x_i$. We show this as a lemma. Lemma: If $\frac{x_i}{p_i} \not = \frac{x_j}{p_j}$ for all $i,j$, then for any constant $C > 0$, when $n$ is sufficiently large, there exists $i$ such that $p_i < \frac{x_i}{C}$. Proof: Assume otherwise. Since $p_i^kP(x_1) = p_1^kP(x_i)$ and $p_1,p_i$ are pairwise coprime, we must have $p_i^k | P(x_i)$ and so for each $i$ we have $P(x_i) = cp_i^k$ for some natural $c < C$. If $c$ is a perfect $k^{th}$ power, then simple bounding tells us that there are only finitely many solutions and so we assume that it isn't. Hence $$x_i^k + a_{n-2}x_i^{k-2} + \cdots + a_0 = cp_i^k \implies \bigl( \frac{x_i}{p_i} \bigr)^k + \frac{ a_{k-2} x_i^{k-2}}{p_i^k} + \cdots + \frac{a_0}{p_i^k} = c$$which gives us $$\bigl (\frac{x_i}{p_i} \bigr)^k - (|a_{k-2}| + 1) \frac{x_i^{k-2}}{p_i^k} < c < \bigl (\frac{x_i}{p_i} \bigr)^k + (|a_{k-2}| + 1) \frac{x_i^{k-2}}{p_i^k}$$when $x_i$ is large enough which happens when $n$ is large enough and hence $$|\sqrt[k]{c} - \frac{x_i}{p_i}| < \frac{C'}{p_i^2}$$for some constant $C' > 0$ since $p_i > \frac{x_i}{C}$. As each $p_i$ is $> \frac{x_i}{C}$ and is $< x_i$, each of them are within a multiple of $2C$ of each other and we get $$|\sqrt[k]{c} - \frac{x_i}{p_i}| < \frac{C'}{p_i^2} < \frac{4C^2C'}{\min \{p_1^2,\ldots,p_n^2 \}}.$$ If we WLOG $p_1^2$ to be the minimum, then each $\frac{x_i}{p_i}$ lies in the interval $[\sqrt[k]{c} - \frac{4C^2C'}{p_1^2}, \sqrt[k]{c} + \frac{4C^2C'}{p_1^2}]$ and if $n$ is large enough, there must be $i,j$ such that $\frac{x_i}{p_i}$ and $\frac{x_j}{p_j}$ are of distance less than $\frac{1}{4C^2p_1^2}$ from each other. Since the two fractions are not equal by assumption, we have $$|\frac{x_i}{p_i} - \frac{x_j}{p_j}| \geq \frac{1}{p_i p_j} \geq \frac{1}{4C^2 p_1^2}$$which is a contradiction and our lemma is proven. $\square$ Now by our lemma, we must have $x_1p_1 = x_ip_i$ for some $i$ or $\frac{x_i}{x_j} = \frac{p_i}{p_j}$ for some $i,j$. Either way, we get for some $i,j$, $$\frac{P(x_i)}{P(x_j)} = \bigl( \frac{x_i}{x_j} \bigr)^k .$$Standard bounding then shows that when $x_i,x_j$ is large enough, our polynomial must be of the form $x^k$. Reversing our transformations, we get that all polynomials that satisfies the conditions must be of the form $c(ax+b)^k$ where $c,a,b$ are rationals such that $c(ax+b)^k$ have integer coefficients. Clearly all such polynomials work and we are done. Comments: Trying to prove the problem for simple cases such as $P(x) = x^k + 1$, it is clear that factorizing and bounding as we did should be the way to proceed. But we run into two problems: 1) Our bounding fails when there is a $x^{k-1}$ coefficient. 2) The condition $p_1x_1 = p_ix_i$ fails to capture all solutions, giving us only $cx^k$ as a solution and not those of the form $c(ax+b)^k$. The step of depressing the polynomial to make the $x^{n-1}$ coefficient vanish although might seem trivial, is the key step in overcoming these two obstacles.

As with fattypiggy123's solution, we only consider polynomials of the form \[ P(x)=cx^n+dx^{n-2}+O(x^{n-3})\] Note that for any $\epsilon > 0$, can find $x_1$ and $x_2$ such that $x_2<x_1<(1+\epsilon)x_2$ and $P(x_1)/P(x_2)$ is rational $d$-th power. We have \[ \frac{P(x_1)}{P(x_2)} = \frac{cx_1^n+dx_1^{n-2}}{cx_2^n+dx_2^{n-2}} + O(x_1^{-3})+O(x_2^{-3}) = \frac{x_1^n}{x_2^n}\left(1+\left[\frac{d}{c}+o(1)\right](x_1^{-2}-x_2^{-2})\right) = \frac{x_1^n}{x_2^n}\left(1+O(\epsilon x_1^{-2})\right) \] Now let \[ \frac{P(x_1)x_2^n}{P(x_2)x_1^n}=(1+q)^n \]for some rational $q$. Suppose $q \neq 0$, then the denominator of $q$ is bounded above by $Mx_2x_1$ for some constant $M$ independent of $x$ and therefore $|q| \geq Mx_1x_2$. On the other hand, by setting $\epsilon$ small enough, the error term becomes smaller than $|q|$, and thus we are forced to conclude that $q=0$. The rest can be easily finished off (for example, by noting that $P(x)/x^n$ is monotone after a certain point, and thus needs to be constant).

fattypiggy123 wrote:

It's the even degree still ok with the conditions ?

I wonder what is the motivation behind the odd degree, given that not one solution uses it...

Today I reviewed some analytic methods and got this problem in one hour. Note last year I solved this problem in nearly four hours. Replace $d$ with $k$. The answer is $P(x)=c(ax+b)^k$ (even if $k$ is even) where $a,b,c\in \mathbb{Z}$. We first depress $P(x)$ and WLOG it is $a_0x^k+a_2x^{k-2} + \cdots + a_k$. Consider $Q(x)=x^{-k}P(x)=a_0+a_2x^{-2}+\cdots+a_nx^{-k}$. Suppose $Q(x_j)=cy_j^k$. I contend that there exists $n>k$ such that $y_1=y_2=\cdots=y_n$, which solves the problem. WLOG, $c\in \mathbb{Z}$ and $y_jx_j\in \mathbb{Z}$ for all $1\le j\le n$. If $y_i$ is nonconstant, we can see that $y_i$ is strictly increasing (or decreasing). Claim: If $y_j\ne y_i$ then $\frac{x_i}{x_j}$ is lower bounded by a constant >1 Note $y_j^k Q(x_i)=y_i^k Q(x_j)$ $y_j^k (a_0+a_2x_i^{-2}+\cdots+a_kx_i^{-k}) = y_i^k (a_0+a_2x_j^{-2}+\cdots+a_kx_j^{-k})$ $a_0 (y_j^k - y_i^k) = y_j^k (a_2x_i^{-2}+\cdots+a_kx_i^{-k})-y_i^k (a_2x_j^{-2}+\cdots+a_kx_j^{-k}) $ If $y_j\ne y_i$, absolute value of LHS is at least $a_0 \frac{1}{x_ix_j} \sum\limits_{t=0}^{k-1} y_j^t y_i^{k-1-t}$. The key insight is that $\frac{x_{i+1}}{x_i}$ is at least $C$ for some $C>1$. If we prove this we are done. Otherwise, we have $a_2(1+\epsilon)(y_j^k x_i^{-2}-y_i^k x_j^{-2})$. If $\frac{x_i}{x_j}<1+\delta$ then this is at most $\delta a_0 \frac{1}{x_ix_j} \sum\limits_{t=0}^{k-1} y_j^t y_i^{k-1-t}$. Taking $\delta\to 0$ finishes the claim. This implies $y_1,\cdots,y_n$ can take finitely many values because $y_n$ is monotone and $\frac{x_n}{x_1} < 2$ is bounded. When $n$ is large, there exist at least $k+1$ solutions to $y_t=m$, so $P(x)\equiv c(xm)^k$, as needed.

Very elegant problem, the following solution will have many ideas, including, picking suitable rational approximations of irrational numbers and using the final equality case to our advantage. We do not require the condition on the parity of $d$ which seems to have been imposed so that the official solution on the shortlist packet works. Let a $d$-th power free integer $k$ be one such that $\nu_p(k) < d$ for all primes $p$, for example, a squarefree integer is $2$-th power free. We claim that only the polynomials of the form $P(x) = c(x+\frac{p}{q})^d$ for $a \neq 0$, $p \in \mathbb{N}, q \in \mathbb{Z}$ such that $P(x) \in \mathbb{Z}[x]$ which in fact means that only the polynomials of the form $P(x) = a(rx+s)^d$ for $a,s \in \mathbb{Z}$, $r \in \mathbb{N}$, $a \neq 0$ work by the Rational Root Theorem. Even though the latter description is cleaner, we will focus on the first description. Firstly, let $P(x) = a_dx^d+a_{d-1}x^{d-1}+ \cdots + a_1x+a_0$ for $a_i \in \mathbb{Z}$ for all $i \in \{0, \cdots, d\}$ and $a_d \neq 0$, assume without loss of generality also that $a_d > 0$ because taking $P \to -P$ clearly still satisfies the problem conditions. We shall now use the equality case by writing $$P(x) = a_d(x+q)^d+Q(x)$$for some $Q(x) \in \mathbb{Q}[x]$ with $deg(Q) \leq d-2$ which can be done by taking $q = \frac{da_{d-1}}{a_{d}}$ because then the coefficient of $x^{d-1}$ in $a_d(x+q)^d$ will be $a_{d-1}$ by the Binomial Theorem. We will for now assume that the leading of coefficient of $Q$ is positive, the proof for when $Q$ has negative leading coefficient is the same where all the ceiling functions in the following proof are replaced by the floor function. Notice that we can take out the $d$-th power free part of each $P(x_i)$ to conclude that $P(x_i) = T \cdot y_i^d$ for $y_i \in \mathbb{N}$ with $T$ being $d$-th power free. We now have the main analytic claim which is definitely the more routine part of the problem. $\textbf{Lemma 1:}$ For all sufficiently large $x_1, \cdots, x_n \in \mathbb{N}$ that satisfy the condition, $$y_i = \lceil \sqrt[d]{\frac{a_d}{T}} \cdot (x_i+q) \rceil$$for all $i \in \{1, \cdots, n\}$ $\textbf{Proof)}$ Assume for the sake of contradiction otherwise, that is, $$y_i \geq \lceil \sqrt[d]{\frac{a_d}{T}} \cdot (x_i+q) \rceil+1 \geq \sqrt[d]{\frac{a_d}{T}} \cdot (x_i+q)+1$$Then $$a_d(x+q)^d + Q(x) = T \cdot y_i^d > T \cdot \left(\sqrt[d]{\frac{a_d}{T}}(x_i+q)+1\right)^d$$ Using the Binomial Theorem, $$Q(x_i) > T \cdot \sum_{i=1}^{d-1} \binom{d}{i} \cdot \left(\frac{a_d}{T}\right)^{\frac{i}{d}} (x_i+q)^i = \sum_{i=0}^{d-1} \binom{d}{i} \cdot a_d^{\frac{i}{d}} \cdot T^{\frac{d-i}{d}} \cdot (x_i+q)^i$$ Then if $x_i+q > 0$, we have that $$\binom{d}{i} \cdot a_d^{\frac{i}{d}} \cdot T^{\frac{d-i}{d}} \cdot (x_i+q)^i > 0$$for all $i \in \{0, \cdots, d-2\}$ meaning that $$Q(x_i) > \sum_{i=0}^{d-1} \binom{d}{i} \cdot a_d^{\frac{i}{d}} \cdot T^{\frac{d-i}{d}} \cdot (x_i+q)^i > d \cdot a_d^{\frac{d-1}{d}} \cdot T^{\frac{1}{d}} \cdot (x_i+q)^{d-1} > d \cdot a_d^{\frac{d-1}{d}} \cdot (x_i+q)^{d-1}$$On the other hand, $$R(x_i) = d \cdot a_d^{\frac{d-1}{d}} \cdot (x_i+q)^{d-1} - Q(x_i) > 0$$for all sufficiently large $x_i$ because the leading coefficient of $R$ is positive contradicting the previous inequality. $\blacksquare$ $\color{red} \boxed{\textbf{Appropriate Approximation }}$ Our intuition is now that the ceiling function does not act similar to polynomials, it's too noncontinuous. We therefore would like to pick some rational $r \in \mathbb{Q}$ such that $$\lceil \sqrt[d]{\frac{a_d}{T}} \cdot (x_i+q) \rceil = \lceil r \cdot (x_i+q) \rceil$$for all $i \in \{1, \cdots, n\}$ which we can clearly do. In this case, we can easily determine the ceiling of a rational number which will make things easier to deal with, yet, intuitively, we would like to pick $r$ to have as small a denominator as possible because this will reduce the freedom in the fractional part and hence our approximation will be sufficiently strong for bounding arguments because $\lfloor y_i \rfloor - y_i < \frac{1}{s}$ for some small enough $s \in \mathbb{N}$ will be true. Keeping this in mind, let us construct such an $r$ and use $\textbf{Lemma 1}$ in order to prove that in fact $Q$ must in fact identically be the $0$ polynomial. We firstly select a sufficiently good rational approximation, we will later optimize this rational approximation. Firstly, notice that there can be at most $d+1$ integers among the $n$ integers such that $\sqrt{\frac{a_d}{T}}(x_i+q) \in \mathbb{Z}$ because in that case we have that $P(x) = a_d(x+q)^d$ as an identity of polynomials which would immediately finish, hence, we can assume that $x_1, \cdots, x_{n-d-1}$ satisfy $\sqrt{\frac{a_d}{T}}(x_i+q) \not\in \mathbb{Z}$ $\textbf{Lemma 2:}$ There exists some $r \in \mathbb{Q}$ such that $\lceil r \cdot (x_i+q) \rceil = \lceil \sqrt[d]{\frac{a_d}{T}} \cdot (x_i+q) \rceil$ for all $i \in \{1, \cdots, n-d-1\}$ $\textbf{Proof)}$ Take some arbitrarily small $\varepsilon \in \mathbb{R}^{+}$ such that $r = \epsilon+ \sqrt[d]{\frac{a_d}{T}}$ for $r \in \mathbb{Q}$ using the density of the rationals in $\mathbb{R}$, then $r \cdot (x_i+q)- \sqrt[d]{\frac{a_d}{T}}(x_i+q) = \varepsilon(x_i+q)$, taking for each $i \in \{1, \cdots, n-d-1\}$, $$\epsilon < \frac{||\sqrt[d]{\frac{a_d}{T}}(x_i+q)||}{x_i+q}$$we get that $r(x_i+q) \in (\sqrt[d]{\frac{a_d}{T}}(x_i+q), \lfloor \sqrt[d]{\frac{a_d}{T}}(x_i+q) \rfloor)$. $\blacksquare$ Now, the idea is that the denominator of $r$ is not easy to control, but luckily we can! This is where we used the fact that $\frac{P(x_i)}{P(x_j}) \in (\frac{1}{2},2)$, as well. Assume that $x_1 < x_2 < \cdots < x_n$, then, clearly there exist some constant $K_c$ (no, not the equilibrium constant) such that $x_i \in (N, K_c \cdot N)$ for all large enough $n \in \mathbb{N}$ ($K_c$ is independent of $n$, in fact, any $K_c$ that is sufficiently close to $\sqrt[d]{2}$ will work in this case because we know that $P(x \cdot \sqrt[d]{2}) \sim 2 \cdot P(x)$), we will only need the existence of such a $K_c$, the fact that $\frac{P(x_i)}{P(x_j)} \in (a_1,b_1)$ for some $0 < a_1 < b_1$ is sufficient for the problem, in general. $\textbf{Lemma 3:}$ There exist some absolute $C \in \mathbb{R}^{+}$ such that $r = \frac{a}{b}$ for $a,b \in \mathbb{N}$ such that $b < CN$ $\textbf{Proof)}$ The idea is similar to the previous lemma but now we optimize the rational approximation. Here is the punchline of the problem. $\color{red} \textbf{Main Lemma:}$ We can pick $r \in \mathbb{Q}$ such that for one of the $i \in \{1, \cdots, n-d-1\}$, $r(x_i+q) \in \mathbb{Z}$ with the property in $\textbf{Lemma 2}$. $\textbf{Proof)}$ Pick $$r = \max_{i \in \{1, \cdots, n-d-1\}}(\frac{\lceil \sqrt[d]{\frac{a_d}{T}}(x_i+q) \rceil }{x_i+q})$$Now, clearly there is at least one $i \in \{1, \cdots, n-d-1\}$ such that $r(x_i+q) \in \mathbb{Z}$ and as in $\textbf{Lemma 2}$, $\lceil r \cdot (x_i+q) \rceil = \lceil \sqrt[d]{\frac{a_d}{T}} \cdot (x_i+q) \rceil$ for all $i \in \{1, \cdots, n-d-1\}$. $\blacksquare$ Now, with the Main Lemma in mind, notice that $r(x_i+q) \in \mathbb{Z}$ means that if we write $r = \frac{a}{b}$ with $gcd(a,b) = 1, a \in \mathbb{Z}, b \in \mathbb{N}$; with $x_i < K_cN$ and $q = \frac{da_{d-1}}{a_{d}}$ in mind, $b \mid a_dx_i+da_{d-1}$, in particular $b \leq a_d \cdot K_c \cdot N+da_{d-1} \leq O(N)$ which readily proves our lemma. $\blacksquare$ This is now very powerful, we know that $P(x_i) = T \cdot (\lceil r \cdot (x_i+q) \rceil)^d$ for all $i \in \{1, \cdots, n-d-1 \}$ by $\textbf{Main Lemma}$ proven within $\textbf{Lemma 3}$ and that $r = \frac{a}{b}$ with $a,b \in \mathbb{N}$ and $b = cN$ with $c \in (0,C)$ and $q$ is a rational constant. Now, firstly notice that if there are $d+1$ different values of $i \in \{1, \cdots, n-d-1\}$ such that $r(x_i+q) \in \mathbb{Z}$, then we have that $$P(x_i) = T \cdot (r(x_i+q))^d$$holds for at least $d+1$ different values and is then a polynomial identity, which is indeed what we strove to prove, otherwise we have that, without loss of generality $r(x_i+q) \not\in \mathbb{Z}$ for all $i \in \{1, \cdots, n-2d-1\}$, similarly, we can see that for each $l \in \{2, \cdots, ba_d\}$, there can be at most $d$ different $i \in \{1, \cdots, n-2d-1\}$ such that $\lceil r(x_i+q) \rceil = r(x_i+q)+\frac{l}{ba_d}$, then we can take $n$ sufficiently large, such that, we have the above equality does not hold for any $l \in \{1, \cdots, t-1\}$ and $i \in \{1, \cdots, n-td-1\}$ for some sufficiently large $t$ of our choice (the unboundedness of these $t$'s will allow us to conclude eventually). Then notice that $$ \lceil \sqrt[d]{\frac{a_d}{T}}(x_i+q) \rceil = \lceil r \cdot (x_i+q) \rceil = \lceil \frac{a}{b} \cdot (x_i+\frac{da_{d-1}}{a_d}) \rceil = \lceil \frac{ax_ia_d+bda_{d-1}}{ba_d} \rceil \geq \frac{ax_ia_d+bda_{d-1}}{b_ad}+\frac{t}{ba_d}$$for all $i \in \{1, \cdots, n-td-1\}$ because and $d,a_d,a_{d-1},a,b$ are all integers which means that $$\lceil \sqrt[d]{\frac{a_d}{T}}(x_i+q) \rceil \geq \sqrt[d]{\frac{a_d}{T}}(x_i+q)+\frac{t}{ba_d} \geq \sqrt[d]{\frac{a_d}{T}}(x_i+q)+\frac{1}{Ca_d}$$by $\textbf{Lemma 3}$. Now, we have that $$P(x_i) = T \cdot y_i^d = T \cdot (\lceil \sqrt[d]{\frac{a_d}{T}}(x_i+q) \rceil)^d \geq T \cdot (\sqrt[d]{\frac{a_d}{T}}(x_i+q)+\frac{t}{Ca_dN})^d$$$$ =a_d(x_i+q)^d + dT^{\frac{1}{d}}a_d^{-\frac{1}{d}} \cdot t \cdot (x_i+q)^{d-1} \cdot (CN)^{-1}+f(x_i)$$where for all sufficiently large $\varepsilon \in \mathbb{R}^{+}$ $f(x_i) \leq \varepsilon \cdot x_i^{d-2}$ for all sufficiently large $x_i \in \mathbb{Z}$, similarly, we can see that for all $\varepsilon \in \mathbb{R}^{+}$ $Q(x_i) \leq \varepsilon \cdot x_i^{d-1}$ for all sufficiently large $x_i \in \mathbb{Z}$, as $Q$ is a polynomial of degree $d-2$. Then, also remembering that $Q(x_i) = P(x_i)-T(x_i+q)^d$, we can see that given any sufficiently large $\epsilon \in \mathbb{R}^{+}$ $$\varepsilon \cdot x_i^{d-2} \geq Q(x_i)-f(x_i) \geq M \cdot T^{\frac{1}{d}} \cdot t \cdot N^{-1}(x_i+q)^{d-1}$$for all sufficiently large $x_i \in \mathbb{Z}$ for some absolute constant $M \in \mathbb{R}^{+}$. Recalling that $x_i \in (N, K_c \cdot N)$, we have that $N^{-1} \geq \frac{1}{x_i}$ and $T^{\frac{1}{d}} \geq 1$ means that $$\varepsilon \cdot x_i^{d-2} \geq Mt \cdot \frac{(x_i+q)^{d-1}}{x_i}$$Then, as $lim_{x_i \to \infty} \frac{(x_i+q)^{d-1}}{x_i} = R(x_i)$ for some $R(x) \in \mathbb{Q}[x]$ with $deg(R) = d-2$, we can take $t$ and $x_i$ both arbitrarily large which is a contradiction, as desired. Hence, we can conclude that $Q$ is identically the zero-polynomial which indeed gives us our initially proposed solution set. $\blacksquare$ $\blacksquare$

mmmmm We claim that $P$ which have a rational root of degree $d$ work. Let $P(x) = a_dx^d + a_{d-1}x^{d-1} + \dots + a_0$. Note that if $P(x)$ works, then \[ Q(x) = P\left(da_{d-1}x - a_d\right) \]also works similarily and satifies $a_{d-1} = 0$, so WLOG assume that $a_{d-1} = 0$. Claim: $\frac{c + O(x^{-1})}{1 + O(x^{-1})}$ converges to $c$ at a rate of $O(x^{-1})$ Proof. Laurent series. $\blacksquare$ Claim: Fix a suffiently large prime $p$ such that $\gcd(p-1, d) = 1$. For sufficiently large $x \equiv y \pmod{p}$ with $y = \Theta(x)$, such that $\frac{P(x)}{P(y)} = \left(\frac{a}{b}\right)^d$, then $\frac{a}{b} = \frac{x}{y}$. Proof. First suppose that $P(x) \equiv P(y) \not\equiv 0 \pmod{p}$. It thus follows that $a^d \equiv b^d \pmod{p}$ so $a \equiv b \pmod{p}$. Let $\frac12 < \frac{P(x)}{P(y)} = \frac{a^d}{b^d} < 2$ for relatively prime $a$ and $b$. Then note that \[ \frac{a_dx^d + a_{d-2}x^{d-2} + \dots + a_0}{a_dy^d + a_{d-2}y^{d-2} + \dots + a_0} = \frac{a^d}{b^d}. \]Since \[ \frac{a_dx^d + a_{d-2}x^{d-2} + \dots + a_0}{a_dy^d + a_{d-2}y^{d-2} + \dots + a_0} = \frac{a_d\left(\frac{x}{y}\right)^d + O\left(y^{-2}\right)}{a_d + O\left(y^{-2}\right)} \]it thus follows that $\frac{P(x)}{P(y)}$ gets arbitrarily close to $\left(\frac{x}{y}\right)^d$ at a rate of $O\left(y^{-2}\right)$. This thus also holds when the $d$ exponents are deleted by binomial theorem. As such, if $\left|\frac{x}{y} - \frac{a}{b}\right| < O\left(y^{-2}\right)$ it follows that \[ \left|bx - ay\right| < by \cdot O\left(y^{-2}\right) \]is bounded in terms of $\frac{b}{y}$ which for sufficiently large $y$ is bounded by a constant. Taking large enough $p$ finishes. Next, suppose that $P(x) \equiv P(y) \equiv 0 \pmod{p}$. If $\nu_p(P(x)) = \nu_p(P(y))$ we finish immediately due to similar logic as earlier, so assume WLOG $\nu_p(P(y)) - \nu_p(P(x)) > 0$. FTSOC suppose that they are not equal. Note that since $\frac{1}{by} \le \left| \frac{x}{y} - \frac{a}{b} \right| < O\left(y^{-2}\right)$ it follows that $b = \Theta(y)$, and thus $b = \Theta(y^d)$ and $a = \Theta(x^d)$. It remains to sufficiently large $p$ such that neither of $\frac{P(x)}{a}, \frac{P(x)}{b}$ can have a factor of $p^d$. $\blacksquare$ Anyways, it now follows that taking such a large prime $p$ and considering $N = p + 1$ cases we get that $\frac{P(x)}{P(y)} = \frac{x^d}{y^d}$ for arbitrarily large $x \ne y$. This expands as $y^d \cdot (a_dx^d + a_{d-2}x^{d-2} + \dots + a_0) = x^d \cdot (a_dy^d + a_{d-2}y^{d-2} + \dots + a_0)$. Asymptotically, it follows that $a_{d-2} = \dots = a_0 = 0$. This can be generalized to even $d$ by taking $N = 2p + 1$ and getting two with the same parity $d$th power.

cjquines0 wrote: Find all polynomials $P(x)$ of odd degree $d$ and with integer coefficients satisfying the following property: for each positive integer $n$, there exists $n$ positive integers $x_1, x_2, \ldots, x_n$ such that $\frac12 < \frac{P(x_i)}{P(x_j)} < 2$ and $\frac{P(x_i)}{P(x_j)}$ is the $d$-th power of a rational number for every pair of indices $i$ and $j$ with $1 \leq i, j \leq n$. Proposed by Navid Safaei, Iran

WLOG $P$ is monic and have rational coefficient, let $P(x)=(x+A)^d+Q(x),$ here $Q(x)\in\mathcal O(x^{d-2}),$ where $A=p/q,$ $p,q$ are relatively prime. For $\forall 1\le i,j\le n,$ if $P(x_i)/P(x_j)=(R/S)^d,$ on one hand $$\frac{R^d}{S^d}-\frac{X^d}{Y^d}=\frac{(RY)^d-(SX)^d}{S^dY^d}\ge \frac{d(SX)^{d-1}}{S^dY^d}=\frac{dX^{d-1}}{SY^d},$$where $X,Y\in\mathbb Z$ and $R/S>X/Y.$ Therefore $$ \frac{P(x_i)}{P(x_j)}-\frac{(x_i+A)^d}{(x_j+A)^d}=\frac{R^d}{S^d}-\frac{(qx_i+p)^d}{(qx_j+p)^d}\ge\frac{d(qx_i+p)^{d-1}}{S(qx_j+p)^d}.$$Note that $S^d\le P(x_j)$ gives $S\le x_j+\mathcal O(1).$ On the other hand $$\frac{P(x_i)}{P(x_j)}-\frac{(x_i+A)^d}{(x_j+A)^d}=\frac{(x_i+A)^d+Q(x_i)}{(x_j+A)^d+Q(x_j)}-\frac{(x_i+A)^d}{(x_j+A)^d}=\frac{Q(x_i)(x_j+A)^d-Q(x_j)(x_i+A)^d}{(Q(x_i)+(x_j+A)^d)(x_j+A)^d}.$$When $n$ is sufficiently large, by $\frac12 < \frac{P(x_i)}{P(x_j)} < 2,$ $x_i\sim x_j\sim x.$ Then $$Q(x_i)(x_j+A)^d-Q(x_j)(x_i+A)^d\in \mathcal O(x^{2d-3}).$$$$(Q(x_i)+(x_j+A)^d)(x_j+A)^d\in\Theta (x^{2d}),\quad\frac{d(qx_i+p)^{d-1}}{S(qx_j+p)^d}\in\Omega (x^{-2}).$$This immediately leads to contradiction since $\mathcal O(x^{-3})<\Omega (x^{-2}).\Box$