lowest degree of polynomial that removes the first digit of an integer in base p

Question

Let $p$ be an odd prime and $n \geq 2$.

(1) Does there exist an integer-coefficient polynomial $f$ such that $f(x) = x - (x \bmod p)$ for all $x \in \mathbb{Z}/p^n \mathbb{Z}$? The polynomial effectively removes the first base-$p$ digit of $x$. For example, if $n = 2$, then the defining property is $f(a+bp) = bp$.

(2) If so, then how can we find such a polynomial with lowest possible degree? How does this lowest degree change with $n$?

UPDATE: I am super amazed. Because the reason I asked the question is because by trial and error I have an algorithm to construct polynomials of degree $(n-1)(p-1) + 1$ that works for small $n$, but can't quite finish the proof by induction to all $n$. This has been bugging me for past few days. Seeing the answers confirm with my heuristic is just thrilling!

SECOND UPDATE: Can we generalize this to functions that removes the lower $k$-digits, i.e., $f(x) = x - (x \mod p^k)$ for all $x \in \mathbb{Z}/p^n \mathbb{Z}$?

Thank you all for your nice answers!

Answer 1

Yes, this can be done, and the bound for the degree given by Neil Strickland (that is, $(n-1)\cdot(p-1)+1$ holds.

Let $F_A(x)$ be the formal sum in binomial coefficients $$ F_A(x):=\sum_{j=0}^\infty (-1)^j \begin{pmatrix}A-1+j\\j\end{pmatrix}\begin{pmatrix}x\\A+j\end{pmatrix}.$$

Then $F_A(x)$ converges on every integer, and for $M\in \mathbb Z$ we have $$ F_A(M)=\begin{cases}1 & M\geq A\\ 0 & \text{otherwise.}\end{cases} $$ The 'otherwise' part of the claim is easy. The rest follows by noticing that $F_A(M)$ is the same as coefficient of $X^{M-A}$ found by taking the product of the Taylor series of $(1+X)^{-A}$ and the polynomial $(1+X)^M$. The result is of course $1$.

Let $$G(x):= p\cdot \sum_{j=1}^\infty F_{j\cdot p}(x)=\sum_{m=0}^\infty a(m)\begin{pmatrix}x\\m\end{pmatrix},$$ where $$a(m):= p\sum_{k=0}^\infty (-1)^{m-kp} \begin{pmatrix}m-1\\m-kp\end{pmatrix}.$$ Then for $M$ a positive integer, we have $0\leq M-G(M)<p$ and $M-G(M)\equiv M \pmod{p}.$

We then define $\tilde G(x)$ to be the same sum, truncated at $m=(n-1)(p-1)+1.$ I claim this polynomial has $p$-integral coefficients, and satisfies the desired properties, and so reduces to a polynomial with integer coefficients satisfying the properties.

Using the identity $$(-1)^k\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}k-n-1\\k\end{pmatrix},$$ we find that $a(m)$ is the coefficient of $X^m$ in the Taylor expansion of $$ p\sum_{k=0}^\infty \left(\frac{X}{1+X}\right)^{rp}=p\frac{(1+X)^p}{(1+X)^p-X^p}.$$ The denominator on the right can be written as $1+B(X)$ where $B(X)$ is divisible by $px$ and has degree $p-1.$ From here it is not hard to see that $a(m)\equiv 0 \pmod{p^n}$ when ever $m>(n-1)(p-1)+1$. Thus, truncating the sum as described above does not change the valuer, mod $p^n$.

We now just need to show that $\tilde G$ can be expanded in a polynomial with $p$-integral coefficients. Each binomial coefficient $\begin{pmatrix}x\\m\end{pmatrix}$ introduces a denominator of $m!$, which has $p$-adic valuation bounded by $$v_p(m!)<\frac{m}{p-1}$$. But as we already saw, $v_p(a(m))>\frac{m}{p-1}$ so the coefficient of $\tilde G(x)$ are indeed $p$-integral.

Answer 2

There is a nice answer to a slightly modified question, which may or may not be useful for you. You want to write elements $k\in\mathbb{Z}/p^n$ in base $p$, ie as $k=\sum_{i=0}^{n-1}a_ip^i$ with $a_i\in D=\{0,1,\dotsc,p-1\}$. However, in many ways it is more natural to use the set of Teichmuller representatives: $$ T = \{x\in \mathbb{Z}/p^n:x^p=x\} $$ There is a bijection $\phi:D\to T$ given by $\phi(x)=x^{p^n}\pmod{p^n}$ and $\phi^{-1}(y)=y\pmod{p}$. Any element $k\in\mathbb{Z}/p^n$ can be written uniquely as $k=\sum_{i=0}^{n-1}a_ip^i$ with $a_i\in T$. This gives $k^{p^n}=a_0$, so the polynomial $f(x)=x-x^{p^n}$ removes the first Teichmuller digit.

The key to proving all this is the following standard lemma: if $x=y\pmod{p^r}$, then $x^p=y^p\pmod{p^{r+1}}$.

Reverting to the original question, the polynomial $f(x)=-x^3+3x^2-2x$ has the required property for $(p,n)=(3,2)$, and the degree here is minimal. I obtained this by a rather messy calculation which I will not reproduce here.

UPDATE: I now have Maple code that calculates the minimal degree for all $p$ and $n$ (but is not very fast except for the smallest cases). In all cases that I have checked, the minimal degree is $(n-1)(p-1)+1$, which I find a rather surprising answer; I would have guessed something much bigger. Specifically, the above formula is correct for $p\leq 7$ and $2\leq n\leq 5$, and also for $p=3$ and $n\leq 8$. When $(p,n)=(3,8)$ we can take $$ f(x) = -1524\,{x}^{15}+153\,{x}^{14}-252\,{x}^{13}+2562\,{x}^{12}+351\,{x}^{ 11}-108\,{x}^{10}+1592\,{x}^{9}+2250\,{x}^{8}-1260\,{x}^{7}-3279\,{x}^ {6}+1701\,{x}^{2}-2186\,x $$ or in machine-friendly notation

-1524*x^15+153*x^14-252*x^13+2562*x^12+351*x^11-108*x^10+1592*x^9+2250*x^8-1260*x^7-3279*x^6+1701*x^2-2186*x