2
$\begingroup$

Let $p$ be a prime, $n$ be a positive integer, and let $\mathbb{Z}_{p^n}$ denote the set of congruence classes modulo $p^n.$ How can one determine the number of functions $f: \mathbb{Z}_{p^n} \to \mathbb{Z}_{p^n}$ satisfying the condition $f(a)+f(b) \equiv f(a+b+pab) \pmod{p^n} $ for all $a,b \in \mathbb{Z}_{p^n}$?

  • 0
    Tiny note @Sasha: here in the comments, you could use the backtick character \` instead of the `
    ` tag, like so: `EnumerateFunctions[n_?Positive, p_?PrimeQ] := Block[{f},Solve[(Flatten[ Outer[f[#1]+f[#2]-f[Mod[#1+#2+p #1 #2, p^n]] &, Range[0,$p^n$- 1], Range[0, p^n-1]]] // Union) == 0, Modulus -> p^n]]` – 2011-08-15
     

1 Answers 1

16

The function $* : (a,b) \mapsto a + b + pab$ is an associative and commutative operation with $0$ as identity element, and since the function $x \mapsto a + (1+pa)x$ is bijective (because $1+pa$ is invertible in $\mathbb{Z}_{p^n}$), it's a group law. Now a simple calculation shows $1$ is of order $p^n$ in this group. This means $(\mathbb{Z}_{p^n}, *)$ is isomorphic to $(\mathbb{Z}_{p^n}, +)$.

So it turns out you're counting group morphisms form $(\mathbb{Z}_{p^n}, *)$ to $(\mathbb{Z}_{p^n}, +)$. This is the same as counting group endomorphisms of $(\mathbb{Z}_{p^n}, +)$ (chose any bijection $\varphi$ such that $\varphi(x+y) = \varphi(x)*\varphi(y)$, then if $f$ satisfies $f(a*b) = f(a) + f(b)$ then $g = f \circ \varphi$ satisfies $g(x+y) = g(x) + g(y)$). There are $p^n$ of those, corresponding to multiplication by a given element of $\mathbb{Z}_{p^n}$.