Polynomials $P$ with integer roots near to $X^{\mathrm{deg}(P)}$

Question

Let $d$ be a positive integer. My question is: can we then find a positive integer $r$ (dependent on $d$) with integers $\alpha_1, \alpha_2, ..., \alpha_r$ and $\beta_1, \beta_2, ..., \beta_r$ such that the Polynomials $P(X) = (X - \alpha_1) \cdots (X - \alpha_r)$ and $Q(X) = (X - \beta_1) \cdots (X - \beta_r)$ satisfy $$ \frac{P(X)}{Q(X)} = 1 + O(\frac{1}{X^d})$$ as $X$ tends to $\infty$ but also $P \not= Q$? For example, if $d=1$ we easily find $r=1$, $\alpha_1 = 1$ and $\beta_1=0$ is a solution. Similarly, if $d=2$ we have $r = 2$ and $\alpha_{1/2} = \pm 1$ and $\beta_1 = \beta_2 = 0$ since then $$ \frac{P(X)}{Q(X)} = \frac{X^2 - 1}{X^2} = 1 - \frac{1}{X^2}. $$

Answer 1

One can take $r = 1 + \frac{d(d-1)}{2}$. Indeed, one can consider the map $$ (\alpha_i)_{i=1}^r \in [|1,N|]^{r} \mapsto (\sum_{i=1}^r \alpha_i^k)_{k=1}^{d-1} \in \prod_{i=1}^{d-1} [|1,rN^k|]. $$ The source has cardinality $N^r$ while the target has cardinality $r^{d-1} N^{\frac{d(d-1)}{2}}$. If $$ (*) \quad N^r > r! r^{d-1} N^{\frac{d(d-1)}{2}}, $$ then we obtain by the pigeonhole principle a tuple $(s_k)_{k=1}^{d-1}$ with $> r!$ preimages. Among these preimages one can find $(\alpha_i)_{i=1}^r$ and $(\beta_i)_{i=1}^r$ which are not permutations of each other. Thus the polynomials $P(X) = \prod_i (X-\alpha_i)$ and $Q(X) = \prod_i (X-\beta_i)$ are distinct, but satisfy $P(X) = Q(X) + O(X^{r-d})$.

The condition $(*)$ is satisfied for large $N$ whenever $r > \frac{d(d-1)}{2}$.

Answer 2

Quoting from Wikipedia,

In mathematics, the Prouhet–Tarry–Escott problem asks for two disjoint multisets $A$ and $B$ of $n$ integers each, whose first $k$ power sum symmetric polynomials are all equal. That is, the two multisets should satisfy the equations $\sum _{{a\in A}}a^{i}=\sum _{{b\in B}}b^{i}$ for each integer $i$ from $1$ to a given $k$. It has been shown that $n$ must be strictly greater than $k$. Solutions with ${\displaystyle k=n-1}$ are called ideal solutions. Ideal solutions are known for ${\displaystyle 3\leq n\leq 10}$ and for ${\displaystyle n=12}$. No ideal solution is known for ${\displaystyle n=11}$ or for ${\displaystyle n\geq 13}$

The relation to the current question is that if those sums are equal then the leading $k+1$ coefficients of $\prod_{a\in A}(x-a)$ and $\prod_{b\in B}(x-b)$ are equal.

Bounds similar to the answer of js21 go back to L Bastien, Sphinx-Oedipe 8 (1913) 171-172, see E. M. Wright, Prouhet's 1851 Solution of the Tarry-Escott Problem of 1910, The American Mathematical Monthly Vol. 66, No. 3 (Mar., 1959), pp. 199-201, DOI: 10.2307/2309513, Stable URL: http://www.jstor.org/stable/2309513