Let $p$ be a fixed prime and let $a \geq 2$ and $e \geq 1$ be fixed integers. Given a function $f: \mathbb{Z} / a \mathbb{Z} \rightarrow \mathbb{Z} / p^{e} \mathbb{Z}$ and an integer $k \geq 0$, the $k$ th finite difference, denoted $\Delta^{k} f$, is the function from $\mathbb{Z} / a \mathbb{Z}$ to $\mathbb{Z} / p^{e} \mathbb{Z}$ defined recursively by  $$ \begin{aligned} & \Delta^{0} f(n)=f(n) \\ & \Delta^{k} f(n)=\Delta^{k-1} f(n+1)-\Delta^{k-1} f(n) \quad \text { for } k=1,2, \ldots \end{aligned} $$  Determine the number of functions $f$ such that there exists some $k \geq 1$ for which $\Delta^{k} f=f$.
Let $p$ be a fixed prime and let $a \geq 2$ and $e \geq 1$ be fixed integers. Given a function $f: \mathbb{Z} / a \mathbb{Z} \rightarrow \mathbb{Z} / p^{e} \mathbb{Z}$ and an integer $k \geq 0$, the $k$ th finite difference, denoted $\Delta^{k} f$, is the function from $\mathbb{Z} / a \mathbb{Z}$ to $\mathbb{Z} / p^{e} \mathbb{Z}$ defined recursively by  $$ \begin{aligned} & \Delta^{0} f(n)=f(n) \\ & \Delta^{k} f(n)=\Delta^{k-1} f(n+1)-\Delta^{k-1} f(n) \quad \text { for } k=1,2, \ldots \end{aligned} $$  Determine the number of functions $f$ such that there exists some $k \geq 1$ for which $\Delta^{k} f=f$.  The answer is  $$ \left(p^{e}\right)^{a} \cdot p^{-e p^{\nu} p(a)}=p^{e\left(a-p^{\nu_{p}(a)}\right)} $$ 【 First solution by author. For convenience in what follows, set $d=\nu_{p}(a)$, let $a=p^{d} \cdot b$, and let a function $f: \mathbb{Z} / a \mathbb{Z} \rightarrow \mathbb{Z} / p^{e} \mathbb{Z}$ be essential if it equals one of its iterated finite differences.  The key claim is the following. Claim (Characterization of essential functions) - A function $f$ is essential if and only if  $$ f(x)+f\left(x+p^{d}\right)+\cdots+f\left(x+(b-1) p^{d}\right)=0 $$  for all $x$.  ## Lemma  Let $g: \mathbb{Z} / a \mathbb{Z} \rightarrow \mathbb{Z} / p^{e} \mathbb{Z}$ be any function, and let $h=\Delta^{p^{d}} g$. Then  $$ h(x)+h\left(x+p^{d}\right)+\cdots+h\left(x+(b-1) p^{d}\right) \equiv 0 \quad(\bmod p) $$  for all $x$.   $$ h(x)=\Delta^{p^{d}} g(x)=\sum_{k=0}^{p^{d}}(-1)^{k}\binom{p^{d}}{k} g\left(x+p^{d}-k\right) $$  However, it is known that $\binom{p^{d}}{k}$ is a multiple of $p$ if $1 \leq k \leq p^{d}-1$, so  $$ h(x) \equiv g\left(x+p^{d}\right)+(-1)^{p^{d}} g(x) \quad(\bmod p) . $$  Using this, we easily obtain  $$ \begin{aligned} & h(x)+h\left(x+p^{d}\right)+\cdots+h\left(x+(b-1) p^{d}\right) \\ \equiv & \begin{cases}0 & p>2 \\ 2\left(g(x)+g\left(x+p^{d}\right)+\cdots+g\left(x+(b-1) p^{d}\right)\right) & p=2\end{cases} \\ \equiv & 0 \quad(\bmod p) \end{aligned} $$  as desired.  ## Corollary  Let $g: \mathbb{Z} / a \mathbb{Z} \rightarrow \mathbb{Z} / p^{e} \mathbb{Z}$ be any function, and let $h=\Delta^{e p^{d}} g$. Then  $$ h(x)+h\left(x+p^{d}\right)+\cdots+h\left(x+(b-1) p^{d}\right)=0 $$  for all $x$.   $$ h_{1}(x)=\frac{h(x)+h\left(x+p^{d}\right)+\cdots+h\left(x+(b-1) p^{d}\right)}{p} . $$  Applying the lemma to $h_{1}$ shows the corollary for $e=2$, since $h_{1}(x)$ is divisible by $p$, hence the numerator is divisible by $p^{2}$. Continue in this manner to get the result for general $e>2$.  This immediately settles this direction, since $f$ is in the image of $\Delta^{e p^{d}}$.   We will show that $\Delta$ is injective on $\mathcal{S}$. Suppose otherwise, and consider two functions $f$, $g$ in $\mathcal{S}$ with $\Delta f=\Delta g$. Then, we obtain that $f$ and $g$ differ by a constant; say $g=f+\lambda$. However, then  $$ \begin{aligned} & g(0)+g\left(p^{e}\right)+\cdots+g\left((b-1) p^{e}\right) \\ = & (f(0)+\lambda)+\left(f\left(p^{e}\right)+\lambda\right)+\cdots+\left(f\left((b-1) p^{e}\right)+\lambda\right) \\ = & b \lambda \end{aligned} $$  This should also be zero. Since $p \nmid b$, we obtain $\lambda=0$, as desired.  Counting Finally, we can count the essential functions: all but the last $p^{d}$ entries can be chosen arbitrarily, and then each remaining entry has exactly one possible choice. This leads to a count of  $$ \left(p^{e}\right)^{a-p^{d}}=p^{e\left(a-p^{\nu_{p}(a)}\right)}, $$  as promised.