Does there exists an integer-coefficient polynomial that extracts the highest digit of an integer in base p? [closed]

Question

Given an odd prime $p$, a positive integer $1 \lt n$, and an integer $x \in \mathbb{Z}/p^n\mathbb{Z}$, does there exist an an integer-coefficient polynomial that extracts the highest digit of $x$?

The extracted digit can be (1) $mod-p^n$ or (2) $mod-p$.

(1) For example, if the result is $mod-p^n$, $f(x)=x-(x\ mod\ p^{n-1})\ (mod p^n)$. This $f(x)$ actually clears the lower digits of $x$. Suppose $x=\sum_{i=0}^{n-1}x_ip^i$ where $x_i \in \mathbb{Z}/p\mathbb{Z}$ is each digit of $x$, then $f(x)$ maps $x=(x_{n-1},x_{n-2},...,x_1,x_0)$ to $(x_{n-1},0,...,0,0)$.

(2) If the result is $mod-p$, then $f(x)$ maps $x=(x_{n-1},x_{n-2},...,x_1,x_0)$ to $x_{n-1}$.

Does either of these polynomials $f(x)$ exist? Thanks in advance.

Answer 1

It is still not clear to me what exactly is being asked because the question mixes binary mods (=the remainder function) and quotient rings, and the range of the variable is unclear. Anyway, the point of this answer is to explain why certain things are impossible.

Fact. If $f(x)=\sum_{i=0}^n a_ix^i$ is a polynomial with integer coefficients, $p$ is a prime number, and $m\equiv n\pmod p$, then $$f(m)\equiv f(n)\pmod p.$$

Proof. Raising to a power preserves a congruence, so we have $m^i\equiv n^i\pmod p$ for all $i$. Congruences also preserve integer linear combinations, and the claim follows.

Corollary. It is impossible to find a polynomial $f(x)\in\Bbb{Z}[x]$ such that for all choices of base-$p$ digits $n_i\in\{0,1,\ldots,p-1\}$, $0\le i<m$, we would have $$ f(\sum_{i=0}^{m-1}n_ip^i)=n_{m-1}. $$

Proof. The base-$p$ expansions the integers $x_1=p^{m-1}$ and $x_2=p^{m-1}-p$ have disting top digits: with $x_1$ we have $n_{m-1}=1$ but with $x_2<p^{m-1}$ the "leading digit" is equal to zero. Yet $x_1\equiv x_2\pmod p$, so the Fact implies that $f(x_1)\equiv f(x_2)\pmod p$. But $1\not\equiv0\pmod p$, so we have run into a contradiction.

---

As Greg Martin explained, it is also impossible to find a polynomial $f(x)\in\Bbb{Z}[x]$ such that for all natural numbers $$ n=\sum_{i=0}^{m-1}n_ip^i, \quad n_i\in\{0,1,\ldots,p-1\}, $$ we would have $$f(n)=n_{m-1}p^{m-1}.\qquad(*)$$ Recapping the reason: $(*)$ implies that $0\le f(n)/n \le 1$ for all natural numbers. Hence $f(n)$ has linear growth, implying that $f(n_1)>f(n_2)$ whenever $n_1>n_2$, which is a contradiction.

On the other hand, if we fix a prime $p$, and a natural number $m$, then it is possible to find a polynomial $f(x)\in\Bbb{Q}[x]$ such that for all $n$ in the range $0\le n<p^m$ we have $f(n)=n_{m-1}p^{m-1}$. Again $n=\sum_in_ip^i$ with $n_i\in\{0,\ldots,p-1\}$. This is a simple application of Lagrange interpolation. For example with $p=m=2$ the polynomial $$ f(x)=\frac13(-7x+9x^2-2x^3) $$ has the prescribed values $f(0)=f(1)=0$, $f(2)=f(3)=2$. Here

• I don't know right away, if it might be possible to replace $f$ with another polynomial with integer coefficients.
• In the linked MO-thread the answer seems to produce a polynomial with rational $p$-adic integers as its coefficients. Basically it allows rational coefficients as longs as the numerators are not divisible by $p$.

Answer 2

No. In the first case, $f(x)/x$ is bounded between $1/2$ and $1$; any polynomial with that property must be a linear polynomial, but no linear polynomial can work. In the second case, $f(x)$ is itself bounded; any polynomial with that property must be constant, but those can't work either.

Answer 3

The ring $\mathbb{Z}_{p^n}$ is not a field. So it may fail to interpolate a polynomial in $\mathbb{Z}_{p^n}[X]$. This failure means that you can not find $f(X) \in \mathbb{Z}_{p^n}[X]$ to extract the highest digit.

To explain case (1) in detail, we explain the interpolation theory in the language of linear algebra. Suppose $\deg{d} = f(X)$. Then

$$ f(p_1) = a_1, \dots, f(p_{d+1}) = a_{d+1} $$

just means

$$ \begin{bmatrix} 1 & p_1 & \dots & p_1^d \\ \vdots & \dots & & \dots \\ 1 & p_{d+1} & \dots & p_{d+1}^d \end{bmatrix} \cdot \mathbf{f} = \begin{bmatrix} a_1 \\ \vdots \\ a_{d+1} \end{bmatrix} $$ where $\mathbf{f}$ is the coefficient vector of $f(X)$. Denote the above Vandermonde matrix by $Van_{d}(p_1, \dots, p_{d+1})$, whose determinant is $\Pi_{j > i} (p_j - p_i)$.

Lemma Let $R$ be a commutative ring. For a square matrix $M$ over $R$, $M$ is invertible in $M_n(R)$ $\Leftrightarrow$ $\det{M}$ is invertible in $R$.

Part of the interpolation theory says that $\mathbf{f}$ can be computed from $a_1, \dots ,a_{d+1}$ if $Van_{d}(p_1, \dots, p_{d+1})$ is invertible.

There are many zerodivisors in $\mathbb{Z}_{p^n}$, for example $p^{n-1} p = 0$. The matrix $Van_{p^{n}}(0,1,2, \dots, p^n - 1)$ is not invertible since its determinant is $0$. Therefore the interpolation theory fails.

Case (1) and (2) are actually the same on whether $f(X) \in \mathbb{Z}_{p^n}[X]$ exists. It can be solved using linear algebra.