Is $h(x)$ a linear polynomial?

[Ackbach]

Here is this week's POTW:

-----

Let $p$ be a prime number. Let $h(x)$ be a polynomial with integer coefficients such that $h(0), \, h(1), \, \dots, \, h(p^2-1)$ are distinct modulo $p^2$. Show that $h(0), \, h(1), \, \dots, \, h(p^3-1)$ are distinct modulo $p^3$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to castor28 for his correct solution to this week's POTW, which was Problem B-4 in the 2008 Putnam Archive. The solution follows.

[sp]We are told that the function $h(x)$ is injective on $\mathbb{Z}/p^2$ and asked to prove that the same is true on $\mathbb{Z}/p^3$. Since, in either case, the domain and co-domain are the same finite set, injective is equivalent to surjective (and bijective). We will prove that $h(x)$ is surjective on $\mathbb{Z}/p^3$.

Choose $a\in\mathbb{Z}$. We must prove that the congruence $h(x)\equiv a\pmod{p^3}$ has a solution, or that $g(x)$ has a root modulo $p^3$, where $g(x)=h(x)-a$; $g(x)$ is also bijective.

Because $g(x)$ is also bijective on $\mathbb{Z}/p$, there is a $b$ such that $g(b)\equiv0\pmod{p}$. If we write $f(x)=g(x+b)$ (another bijective function), we have $f(0)\equiv0\pmod{p}$.

Since $p$ is prime, we have the factorization:

$$f(x)\equiv x^k t(x) \pmod{p}$$
​

Because $f(x)$ is bijective, $x=0$ is the only root, and $t(x)\not\equiv0\pmod{p}$ for all $x\not\equiv0\pmod{p}$.

We show now that $k=1$. Since $f(x)$ is surjective modulo $p^2$, there must be a $y$ with $f(y)\equiv p\pmod{p^2}$. Since $t(y)\not\equiv0\pmod{p}$ for all $y\not\equiv0\pmod{p}$, we have $y\equiv0\pmod{p}$; if $k>1$, $f(y)\equiv0\pmod{p^2}$, a contradiction.

Because $k=1$, $x=0$ is a simple root modulo $p$, and we can use Hensel's lifting to lift that root to a root modulo $p^3$.

Conjecture: Could it be true that $h(x)$ must be linear ?
[/sp]