Problem: Let $p$ be a fixed prime and let $a \ge 2$ and $e \ge 1$ be fixed integers.
Given a function $f \colon \ZZ/a\ZZ \to \ZZ/p^e\ZZ$
and an integer $k \ge 0$, the \emph{$k$th finite difference},
denoted $\Delta^k f$, is the function from $\ZZ/a\ZZ$ to $\ZZ/p^e\ZZ$
defined recursively by
\begin{align*}
  \Delta^0 f(n) &= f(n) \\
  \Delta^k f(n) &= \Delta^{k-1} f(n+1) - \Delta^{k-1} f(n)
  \qquad \text{for } k = 1, 2, \dots.
\end{align*}

Determine the number of functions $f$ such that there exists some
$k \ge 1$ for which $\Delta^k f = f$.

\end{enumerate}

Solution: The answer is
\[ (p^e)^a \cdot p^{-ep^{\nu_p(a)}} = p^{e(a - p^{\nu_p(a)})}. \]

\paragraph{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\colon \ZZ/a\ZZ \to \ZZ/p^e\ZZ$ be \emph{essential}
if it equals one of its iterated finite differences.

The key claim is the following.
\begin{claim*}[Characterization of essential functions]
  A function $f$ is essential if and only if
  \begin{equation}\label{p3:ess}
    f(x) + f(x + p^d) + \dots + f(x + (b-1)p^d) = 0
  \end{equation}
  for all $x$.
\end{claim*}
As usual, we split the proof into two halves.

\subparagraph{Proof that essential implies the equation}
First, suppose that $f$ is essential, with $\Delta^N f = f$.
Observe that $f$ is in the image of $\Delta^k$ for any $k$, because $\Delta^{mN} f = f$ for any $m$.
The following lemma will be useful.
\begin{lemma*}
  Let $g \colon \ZZ/a\ZZ \to \ZZ/p^e\ZZ$ be any function, and let $h = \Delta^{p^d} g$. Then
  \[ h(x) + h(x + p^d) + \dots + h(x + (b-1)p^d) \equiv 0 \pmod p \]
  for all $x$.
\end{lemma*}
\begin{proof}
  By definition,
  \[ h(x) = \Delta^{p^d} g(x) = \sum_{k = 0}^{p^d} (-1)^k \binom{p^d}k g(x + p^d - k). \]
  However, it is known that $\tbinom{p^d}k$ is a multiple of $p$ if $1 \le k \le p^d - 1$, so
  \[ h(x) \equiv g(x + p^d) + (-1)^{p^d} g(x) \pmod p. \]
  Using this, we easily obtain
  \begin{align*}
    & \phantom{\equiv}\;\; h(x) + h(x + p^d) + \dots + h(x + (b-1)p^d)\\
    & \equiv
    \begin{cases*}
      0 & $p > 2$\\
      2(g(x) + g(x + p^d) + \dots + g(x + (b-1)p^d)) & $p = 2$
    \end{cases*}\\
    & \equiv 0 \pmod p,
  \end{align*}
  as desired.
\end{proof}

\begin{corollary*}
  Let $g \colon \ZZ/a\ZZ \to \ZZ/p^e\ZZ$ be any function, and let $h = \Delta^{ep^d} g$. Then
  \[ h(x) + h(x + p^d) + \dots + h(x + (b-1)p^d) = 0 \]
  for all $x$.
\end{corollary*}
\begin{proof}
  Starting with the lemma, define
  \[ h_1(x) = \frac{h(x) + h(x  + p^d) + \dots + h(x + (b-1)p^d)}{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$.
\end{proof}
This immediately settles this direction, since $f$ is in the image of $\Delta^{ep^d}$.

\subparagraph{Proof the equation implies essential}
Let $\mathcal S$ be the set of all functions satisfying \ref{p3:ess};
then it's easy to see that $\Delta$ is a function on $\mathcal S$.
To show that all functions in $\mathcal S$ are essential,
it's equivalent to show that $\Delta$ is a permutation on $\mathcal S$.

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{align*}
  & \phantom{=}\;\; g(0) + g(p^e) + \dots + g((b-1)p^e)\\
  & = (f(0) + \lambda) + (f(p^e) + \lambda) + \dots + (f((b-1)p^e) + \lambda)\\
  & = b\lambda.
\end{align*}
This should also be zero. Since $p \nmid b$, we obtain $\lambda = 0$, as desired.

\subparagraph{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
\[ (p^e)^{a - p^d} = p^{e(a - p^{\nu_p(a)})}, \]
as promised.

\paragraph{Second solution by Daniel Zhu.}
There are two parts to the proof:
solving the $e = 1$ case, and using the $e=1$ result to solve the general problem
by induction on $e$. These parts are independent of each other.

\subparagraph{The case $e = 1$}
Represent functions $f$ as elements
\[ \alpha_f \coloneq
  \sum_{k \in \ZZ/a\ZZ} f(-k)x^k \in \FF_p[x]/(x^a - 1) \]
Then, since $\alpha_{\Delta f} = (x - 1) \alpha_f$,
we wish to find the number of $\alpha \in \FF_p[x]/(x^a - 1)$
such that $(x-1)^m\alpha = \alpha$ for some $m$.

Now, make the substitution $y = x - 1$ and let $P(y) = (y+1)^a - 1$;
we want to find $\alpha \in \FF_p[y]/(P(y))$ such that $y^m\alpha = \alpha$ for some $m$.

If we write $P(y) = y^d Q(y)$ with $Q(0) \neq 0$,
then by the Chinese Remainder Theorem we have the ring isomorphism
\[ \FF_p[y]/(P(y)) \cong \FF_p[y]/(y^d) \times \FF_p[y]/(Q(y)). \]
Note that $y$ is nilpotent in the first factor,
while it is a unit in the second factor.
So the $\alpha$ that work are exactly those that are zero in the first factor;
thus there are $p^{a-d}$ such $\alpha$.
We can calculate $d = p^{v_p(a)}$ (via, say, Lucas's Theorem), so we are done.

\subparagraph{The general problem}
The general idea is as follows:
call a $f \colon \ZZ/a\ZZ \to \ZZ/p^e\ZZ$ \emph{$e$-good}
if $\Delta^m f = f$ for some $m$.
Our result above allows us to count the $1$-good functions.
Then, if $e \geq 1$, every $(e+1)$-good function, when reduced mod $p^e$,
yields an $e$-good function, so we count $(e+1)$-good functions by counting
how many reduce to any given $e$-good function.

Formally, we use induction on $e$, with the $e = 1$ case being treated above.
Suppose now we have solved the problem for a given $e \geq 1$,
and we now wish to solve it for $e + 1$.
For any function $g \colon \ZZ/a\ZZ \to \ZZ/p^{e+1}\ZZ$,
let $\bar g \colon \ZZ/a\ZZ \to \ZZ/p^e\ZZ$ be its reduction mod $p^e$.
For a given $e$-good $f$, let $n(f)$ be the number of $(e+1)$-good $g$ with $\bar g = f$.
The following two claims now finish the problem:

\begin{claim*}
  If $f$ is $e$-good, then $n(f) > 0$.
\end{claim*}
\begin{proof}
  Suppose $m$ is such that $\Delta^m f = f$.
  Pick any $g$ with $\bar g = f$, and consider the sequence of functions
  \[ g, \Delta^m g, \Delta^{2m} g, \dots. \]
  Since there are finitely many functions $\ZZ/a\ZZ \to \ZZ/p^{e+1}\ZZ$,
  there must exist $a < b$ such that $\Delta^{am} g = \Delta^{bm} g$.
  We claim $\Delta^{am} g$ is the desired $(e+1)$-good function.
  To see this, first note that since $\ol{\Delta^k g} = \Delta^k \bar g$,
  we must have $\ol{\Delta^{am} g} = \Delta^{am} f = f$.
  Moreover,
  \[ \Delta^{(b-a)m} (\Delta^{am} g) = \Delta^{bm} g = \Delta^{am} g, \]
  so $\Delta^{am} g$ is $(e+1)$-good.
\end{proof}

\begin{claim*}
  If $f$ is $e$-good, and $n(f) > 0$,
  then $n(f)$ is exactly the number of $1$-good functions,
  i.e.\ $p^{a - p^{v_p(a)}}$.
\end{claim*}
\begin{proof}
  Let $g$ be any $(e+1)$-good function with $\bar g = f$.
  We claim that the $(e+1)$-good $g_1$ with $\bar g_1 = f$
  are exactly the functions of the form $g + p^e h$ for any $1$-good $h$.
  Since these functions are clearly distinct,
  this characterization will prove the claim.

  To show that this condition is sufficient,
  note that $\ol{g + p^e h} = \bar g = f$.
  Moreover, if $\Delta^m g = g$ and $\Delta^{m'} h = h$, then
  \[ \Delta^{mm'}(g + p^e h)
    = \Delta^{mm'} g + p^e \Delta^{mm'} h = g + p^e h. \]

  To show that this condition is necessary,
  let $g_1$ be any $(e+1)$-good function such that $\bar g_1 = f$.
  Then $g_1 - g$ is also $(e+1)$-good, since if $\Delta^m g = g$,
  $\Delta^{m'} g_1 = g_1$, we have
  \[ \Delta^{mm'}(g_1 - g) = \Delta^{mm'} g_1 - \Delta^{mm'} g = g_1 - g. \]
  On the other hand, we also know that $g_1 - g$ is divisible by $p^e$.
  This means that it must be $p^e h$ for some function
  $f \colon \ZZ/a\ZZ \to \ZZ/p\ZZ$, and it is not hard to show
  that $g_1 - g$ being $(e+1)$-good means that $h$ is $1$-good.
\end{proof}