Given a prime number $p$ and a positive integer $k$. Consider integer-valued polynomials $f$ satisfying the property that $p | f(x) \Leftrightarrow p^k | x$.

Question. What is the smallest degree of such $f$?

I can construct such an $f_k$ with degree $2p^{k-1} - 1$. The idea is to use induction with $f_1 = x$ and $$f_{k+1} = f_k + \sum_{j = 0}^{p^k-1} (-1)^{j} \binom{x}{p^k+j}.$$ Using Lucas' theorem, it can be shown that the sum $\sum_{j = 0}^{p^k-1} (-1)^{j} \binom{x}{p^k+j}$ is 0 $mod~p$ when $p^k \nmid x$, and it is $r~mod~p$ when $p^k | x$, where $r$ is defined to be the residue of $\frac{x}{p^k}$ $mod~p$. Thus when $p^k \nmid x$, $f_{k+1}(x) \equiv f_{k}(x)$ is not divisible by $p$ by induction hypothesis. And when $p^k \mid x$, $f_{k+1}(x) \equiv f_k(x) + r \equiv r~(mod~p)$. It is divisible by $p$ precisely when $p | r$, or $p^{k+1} | x$.

I can also show this construction is optimal for $k = 1, 2$. The case $k = 1$ is trivial. For $k = 2$, write any such $f$ as $\frac{g}{p^l}$ where $g$ is a primitive polynomial with integer coefficients and $l \in\mathbb{Z}$. Ignoring other possible factors in the numerator/denominator is without loss. The condition implies $l$ cannot be negative, and $l$ cannot be zero because then we deduce from $p|g(0)$ that $p|g(p) = f(p)$. Moreover, if $l \geq 2$ then the degree of $f$ must be $2p$, due to Polya's result that $d!f(x) \in Z[x]$. Thus we can assume $l = 1$. By condition we have $p| g(x)$ for every integer $x$ but $p^2| g(x)$ only when $p^2 | x$. Hensel's lemma then yields $p | g'(x)$ whenever $p \nmid x$. Therefore $g$ has double roots at every $x \in F_p^*$ and at least one root at $x = 0$, suggesting its degree must at least be $2p-1$.

I'm not sure how far this method can be extended to larger $k$, although I do suspect $2p^{k-1}-1$ is the right answer. In general I can only show $d \geq \frac{p^k-1}{p-1}$ by noting that $1-f^{p-1}$ vanishes at $x = 1, 2, \dots, p^{k}-1$ but not at $x = 0$. This implies for $p = 2$ the answer is indeed $2^k-1$.


Your construction is optimal, that is, the degree of $f$ is always at least $2p^{k-1}-1$. Note that if $m,x$ have $p$-base expansions $m=\sum_{i}m_i p^i$, $x=\sum_{i}x_i p^i$, we have $\binom{x}{m}\equiv \prod \binom{x_i}{m_i} \pmod p$ by Lucas' theorem, and any integer-valued polynomial is an integer linear combinations of binomials $\binom{x}{m}$ (whose result is it, by the way?). So your question is essentially about polynomials in $k$ variables $x_0,\dots,x_{k-1}$ over $\mathbb{F}_p$, which are reduced (have degree at most $p-1$ in each variable). Assume that degree of $f$ is strictly less than $2p^{k-1}-1$. It means that the corresponding polynomial $F\in \mathbb{F}_p[x_0,\dots,x_{k-1}]$ is at most linear in $x_{k-1}$ and its coefficient of $x_{k-1}x_0^{p-1}\dots x_{k-2}^{p-1}$ equals 0. Denote $F=g(x_0,\dots,x_{k-2})+x_{k-1}h(x_0,\dots,x_{k-2})$ and write $y=(x_0,\dots,x_{k-2})$. We have $g(0)=0$, $g(y)\ne 0$ for $y\ne 0$, $h(0)\ne 0$, $h(y)=0$ for $y\ne 0$ (else we may set $x_{k-1}=-g(y)/h(y)$ and find another root of $F$.) But then we may reconstruct the coefficient of $x_0^{p-1}\dots x_{k-2}^{p-1}$ in the polynomial $h(x_0,\dots,x_{k-2})$, and it is non-zero: the sum contains unique non-negative summand (I guess, it is a partial case of Alon-Füredi theorem). A contradiction.

  • $\begingroup$ That is a wonderful argument, Fedor $\endgroup$ – Xiaosheng Mu Jun 4 '16 at 1:22
  • $\begingroup$ And that result about integer-valued polynomials is due to Polya, I believe $\endgroup$ – Xiaosheng Mu Jun 4 '16 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.