2

I have an integer polynomial $p(x)$ such that $p(n)>n$ for all natural numbers and for some positive integer $c,m$, $p^{m+1}(c)-p^{m}(c)= p^{m+2}(c)-p^{m+1}(c)=...$. I have to determine if this polynomial is linear or not. ($p^k(c)$ is $p$ composed with itself $c$ times)

I think the polynomial has to be linear. Now, if the polynomial wasn't linear, say of $\deg \geq 2$, then the "rate of increase in the interval" would have been constantly increasing, unlike in our case where it is constant. I'm think we can make a sort of derivative argument here, but I can't think of how to put this rigorously. Please help

zaemon_23
  • 465
  • 1
    Do the $\cdots$ go to infinity ? If so this quantity is $0$ at some point, and all $p^k(c)$ are equal for $k\ge m$. Or is it power and not $k$ derivative ? – zwim Nov 12 '23 at 19:20
  • 1
    @zwim yes it goes to infinity. And very sorry, I should have mentioned it in the problem, but $p^k(c)$ is $p$ composed with itself $c$ times – zaemon_23 Nov 12 '23 at 19:51

1 Answers1

4

Suppose $p,c,m$ satisfy the specified conditions, and let $a=p^{m+1}(c)-p^m(c)$.

Let the polynomial $q$ be given by $q(x)=p(x)-x$.

Letting $b=p^m(c)$ it follows that $$ q(p^k(b))=p(p^k(b))-p^k(b)=p^{m+k+1}(c)-p^{m+k}(c)=a $$ holds for all nonnegative integers $k$.

But we have $$ b < p(b) < p^2(b) < p^3(b) < \cdots $$ and since $q(p^k(b))=a$ for all nonnegative integers $k$, we get that the polynomial $q(x)-a$ has infinitely many roots, so $q(x)=a$.

Thus $p(x)-x=a$,$\;$so $p(x)=x+a$.

quasi
  • 58,772