Bounding the outputs of a polynomial

Question

Let $p(x)$ be a polynomial with integer coefficients and $k\geq 6$ a positive integer.

Given that $x_1,x_2,\ldots,x_k$ are distinct integers such $p(x_1),p(x_2),\ldots,p(x_{k})\in\{1,2,\ldots,k-1\}$, prove that $p(x_1)=p(x_2)=\cdots=p(x_k)$.

Not really sure how to proceed. It's obvious for degree $1$ and $2$ polynomials. I just want a hint. The condition $k \ge 6$ is rather mysterious.

I tried to do it by induction on $k$. Even the base case is not obvious, but lets suppose we demonstrated its true for $k=6$. If none of $p(x_1),...p(x_k)$ are equal to $k-1$, we are done since there are $k$ outputs in $\{1,..,k-2\}$, they are all equal by the inductive hypothesis.

If exactly one of the outputs is $k-1$, wlog it is $p(x_k)$ we still have $k-1$ outputs in the set $\{1,...,k-2\}$, and they are all equal to some number $a$, so we can write

$p(x)=a+q(x)(x-x_1)...(x-x_{k-1})$

Then $p(x_k)=a+q(x_k)(x_k-x_1)...(x_k-x_{k-1})=k-1$. But clearly

$k-2 \ge |a-(k-1)|=|q(x_k)(x_k-x_1)...(x_k-x_{k-1})| \ge 2^{k-3}$

a contradiction for $k \ge 5$. Maybe I was lazy with the bounding and I can get a contradiction for $k \ge 6$. I would be surprised if this is not where the condition comes from.

What if there is more than one output equal to $k-1$? I'm thinking about that.

I guess we can assume WLOG that $p(x_i)=i \forall i=1,2,..k-1$? Or am I misreading this? — MathematicianByMistake, Mar 29 '16 at 16:21
@MathematicianByMistake I can't think of any reason for that to be true. — Robert Israel, Mar 29 '16 at 16:23
@MathematicianByMistake Note that at least to value should be the same, so you can't assume this. — DiegoMath, Mar 29 '16 at 16:24
If the problem has been relayed to me correctly, then that is not a requirement of the problem. — math_lover, Mar 29 '16 at 16:27

MT_ · Answer 1 · 2016-03-29T17:12:18.443

Too long for a comment. This is a collection of thoughts that might lead to the right track. I also agree that it should hold true for $k \geq 5$ also.

Fix $k$. Suppose $x_1, \dots, x_{k-1}$ are all the same and $x_k$ is distinct. Then we can say Let $p(x) = a(x - x_1)^{e_1}(x - x_2)^{e_2}\dots(x - x_{k-1})^{e_3} + b$ with $0 < b < k$.

But the product $|p(x_k)| = |a(x_k -x_1)^{e_1}(x_k - x_2)^{e_2} \dots (x_k - x_{k-1})^{e_{k-1}}| + b$ is too big. Indeed, when $k = 6$ and $n = 5$ we have it minimized when the roots are $x_{k} - 1, x_k - 2, x_k + 1, x_k + 2, x_k + 3$, the multiplicities are one, and $a = 1$. The product minimum is $12$ in that case, so all of the $x_i$ must be equal. This clearly holds when $k$ is larger as well.

This also works for $k=5$, but not for $k=4$ (take $p(x) = (x-2)(x-1)(x+1) + 1$).

Bounding the outputs of a polynomial

1 Answers1