USA Tstst

Let $d = \nu_p(a)$, so $a = p^d \cdot b$ with $p \nmid b$. We call a function $f: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ essential if $\Delta^k f = f$ for some $k \ge 1$.

Claim (Characterization of essential functions):
A function $f$ is essential if and only if
$$f(x) + f(x + p^d) + \dots + f(x + (b-1)p^d) = 0 \tag{1}$$
for all $x$.

Proof that essential implies the equation:
Suppose $f$ is essential, with $\Delta^N f = f$. Then $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.

Lemma:
Let $g: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ 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$.

Proof of Lemma. 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 $\binom{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{aligned} & 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{aligned}$$
so the lemma is proved.

Corollary:
Let $g: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ 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$.

This immediately settles this direction, since $f$ is in the image of $\Delta^{ep^d}$.

Proof the equation implies essential:
Let $S$ be the set of all functions satisfying (1); then it's easy to see that $\Delta$ is a function on $S$. To show that all functions in $S$ are essential, it's equivalent to show that $\Delta$ is a permutation on $S$.

We will show that $\Delta$ is injective on $S$. Suppose otherwise, and consider two functions $f$, $g$ in $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(p^d) + \dots + g((b-1)p^d) \\ &= (f(0) + \lambda) + (f(p^d) + \lambda) + \dots + (f((b-1)p^d) + \lambda) \\ &= (f(0) + f(p^d) + \dots + f((b-1)p^d)) + 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
$$p^{a-p^d}$$
for the number of essential functions when $e = 1$.

---

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.

**The case $e=1$:**
Represent functions $f$ as elements
$$\alpha_f := \sum_{k \in \mathbb{Z}/a\mathbb{Z}} f(-k)x^k \in \mathbb{F}_p[x]/(x^a - 1)$$
Then, since $\alpha_{\Delta f} = (x-1)\alpha_f$, we wish to find the number of $\alpha \in \mathbb{F}_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 \mathbb{F}_p[y]/(P(y))$ such that $y^m\alpha = \alpha$ for some $m$.

If we write $P(y) = y^dQ(y)$ with $Q(0) \neq 0$, then by the Chinese Remainder Theorem we have the ring isomorphism
$$\mathbb{F}_p[y]/(P(y)) \cong \mathbb{F}_p[y]/(y^d) \times \mathbb{F}_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.

The general problem:
The general idea is as follows: call a $f: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ e-good if $\Delta^m f = f$ for some $m$. Our result above allows us to count the 1-good functions. Then, if $e \ge 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 \ge 1$, and we now wish to solve it for $e+1$. For any function $g: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^{e+1}\mathbb{Z}$, let $\bar{g}: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ 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:

Claim 1: If $f$ is e-good, then $n(f) > 0$.

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 $\mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^{e+1}\mathbb{Z}$, 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 $\overline{\Delta^k g} = \Delta^k \bar{g}$, we must have $\overline{\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. $\square$

Claim 2: 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)}}$.

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 $\overline{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 $h: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$, and it is not hard to show that $g_1 - g$ being $(e+1)$-good means that $h$ is 1-good. $\square$

Final answer:

The number of functions $f: \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ such that $\Delta^k f = f$ for some $k \ge 1$ is
$$p^{e(a-p^{v_p(a)})}$$