Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$?

share|improve this question
1  
Computer experimentation seems to indicate that generically there will be $p^n$ of such functions. They are parametrized by free value of $f(1)$. I used the following Mathematica code: <pre>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]]</pre> –  Sasha Aug 12 '11 at 14:30
    
Tiny note @Sasha: here in the comments, you could use the backtick character ` instead of the <pre> 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]] –  J. M. Aug 15 '11 at 4:56

1 Answer 1

up vote 14 down vote accepted

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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.