$p | f(x)$ if and only if $p^k | x$.

Question

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$.

Answer 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.