show/hide this revision's text 4 fixed latex bug

Edit: In fact, we can show that a polynomial in $n$ produces an average-integral sequence if and only if it can be expressed as a $\mathbb{Z}_{(p)}$-linear combination of terms of the form $p^{d(k)}n^k$, or equivalently if it can be expressed as a $\mathbb{Z}_{(p)}$-linear combination of terms of the form $p^{d(k)}n^{\underline{k}}$.

The second claim is much easier to prove: we have $\frac{\Delta^{p-1}p^{d(k)}n^{\underline{k}}}{p} = p^{d(k)-1}k^{\underline{p-1}}n^{\underline{k-(p-1)}}$, which is an integer relatively prime to $p$ times $p^{d(k-(p-1))}n^{\underline{k-(p-1)}}$. Also, if $k < p-1$, then $d(k) = 0$ and we can recover the coefficient of $n^{\underline{k}}$ from the first $p-1$ values of the polynomial without doing any multiplication or division by $p$.

For the first claim, take a polynomial which is not an integer combination of terms of the form $p^{d(k)}n^k$, and look at the largest $k$ such that the coefficient on $n^k$ is not a multiple of $p^{d(k)}$. By subtracting off a polynomial that we already know to be average-integral (ignoring denominators other than $p$), we can assume that this is the leading term of the polynomial. Now convert to the falling power basis, and note that the leading term remains the same, to show that this polynomial is not average-integer.
show/hide this revision's text 3 fixed markup(?) bug

Ok, here's how to show that $(1+n^{p+1})^p$ always gives a counterexample for $p > 3$.

Set $d(k) = \lfloor \frac{k}{p-1} \rfloor - v_p(k!)$. Note that $d(k)$ is equal to the sum of the base-$p$ digits of $k$, divided by $p-1$, and rounded down, so for instance if $k$ is a nonzero multiple of $p-1$ then we have $d(k) \ge 1$. We have

$p^{d(k)}(F_pn^k - n^k) = \sum_{j=0}^{k-1}(p^{d(k)-1}{k\choose j}\sum_{i=0}^{p-1}i^{k-j})n^j,$

and we have

$d(k)-1 + v_p({k\choose j}) + v_p(\sum_{i=0}^{p-1}i^{k-j}) - d(j) $

$= \lfloor \frac{k}{p-1} \rfloor - \lfloor \frac{j}{p-1} \rfloor - v_p((k-j)!) - 1 + v_p(\sum_{i=0}^{p-1}i^{k-j})$

$ = (d(k-j) + v_p(\sum_{i=0}^{p-1}i^{k-j})-1) + (\lfloor \frac{k}{p-1} \rfloor-\lfloor \frac{j}{p-1} \rfloor-\lfloor \frac{k-j}{p-1} \rfloor) \ge 0$,

so by induction on $k$ we can show that $p^{d(k)}n^k$ is average-integral for any $k$.

We have $d(k(p+1)) \le 1$ for $k = 1, ..., p-2$, $d(p^2-1) = 2$, and $d(p^2+p) = 0$. Thus, we easily see that $(1+n^{p+1})^p = 1 + \sum_{k=1}^{p-2}{p \choose k}n^{k(p+1)} + pn^{p^2-1} + n^{p^2+p}$ is average-integral if and only if $pn^{p^2-1}$ is. Next, note that $pn^{p^2-1}-pn^{\underline{p^2-1}}$ is a sum of multiples of $p$ times monomials $n^k$ with $k < p^2-1$, and that for $k < p^2-1$ we have $d(k) \le 1$, so $pn^{p^2-1}$ is average-integral if and only if $pn^{\underline{p^2-1}}$ is.

Now note that we can express $\frac{\Delta^{p-1}f}{p}$ as an integral linear combination of $F_pf$ and the shifts of $f$, since we have $(-1)^k{p-1 \choose k} \equiv 1 \pmod{p}$. Thus, if $pn^{\underline{p^2-1}}$ was average-integral then we would have $\frac{\Delta^{p^2-1}pn^{\underline{p^2-1}}}{p^{p+1}} = \frac{p(p^2-1)!}{p^{p+1}}$ an integer, but this is obviously not the case, so we're done. (And thus, $(1+n^{p+1})^p$ fails to be average-integral by the $p+1$st iteration.)
show/hide this revision's text 2 fixed a stupid mistake

Ok, here's how to show that $(1+n^{p+1})^p$ always gives a counterexample for $p > 3$.

Set $d(k) = \lfloor \frac{k}{p-1} \rfloor - v_p(k!)$. Note that $d(k)$ is equal to the sum of the base-$p$ digits of $k$, divided by $p-1$, and rounded down, so for instance if $k$ is a nonzero multiple of $p-1$ then we have $d(k) \ge 1$. We have

$p^{d(k)}(F_pn^k - n^k) = \sum_{j=0}^{k-1}(p^{d(k)-1}{k\choose j}\sum_{i=0}^{p-1}i^{k-j})n^j,$

and we have

$d(k)-1 + v_p({k\choose j}) + v_p(\sum_{i=0}^{p-1}i^{k-j}) - d(j) = \lfloor \frac{k}{p-1} \rfloor - \lfloor \frac{j}{p-1} \rfloor - v_p((k-j)!) - 1 + v_p(\sum_{i=0}^{p-1}i^{k-j})$ $ = (d(k-j) + v_p(\sum_{i=0}^{p-1}i^{k-j})-1) + (\lfloor \frac{k}{p-1} \rfloor-\lfloor \frac{j}{p-1} \rfloor-\lfloor \frac{k-j}{p-1} \rfloor) \ge 0$,

so by induction on $k$ we can show that $p^{d(k)}n^k$ is average-integral for any $k$.

We have $d(k(p+1)) = \le 1$ for $k = 1, ..., p-2$, $d(p^2-1) = 2$, and $d(p^2+p) = 0$. Thus, we easily see that $(1+n^{p+1})^p = 1 + \sum_{k=1}^{p-2}{p \choose k}n^{k(p+1)} + pn^{p^2-1} + n^{p^2+p}$ is average-integral if and only if $pn^{p^2-1}$ is. Next, note that $pn^{p^2-1}-pn^{\underline{p^2-1}}$ is a sum of multiples of $p$ times monomials $n^k$ with $k < p^2-1$, and that for $k < p^2-1$ we have $d(k) \le 1$, so $pn^{p^2-1}$ is average-integral if and only if $pn^{\underline{p^2-1}}$ is.

Now note that we can express $\frac{\Delta^{p-1}f}{p}$ as an integral linear combination of $F_pf$ and the shifts of $f$, since we have $(-1)^k{p-1 \choose k} \equiv 1 \pmod{p}$. Thus, if $pn^{\underline{p^2-1}}$ was average-integral then we would have $\frac{\Delta^{p^2-1}pn^{\underline{p^2-1}}}{p^{p+1}} = \frac{p(p^2-1)!}{p^{p+1}}$ an integer, but this is obviously not the case, so we're done. (And thus, $(1+n^{p+1})^p$ fails to be average-integral by the $p+1$st iteration.)
show/hide this revision's text 1