# counting points on unit sphere mod p

Let $f(n)$ be the number of points on the unit sphere $x^2 + y^2 + z^2 = 1\; (\mod n)$ with $x,y,z \in \mathbb{Z}/n\mathbb{Z}$

This is sequence A087784 in the Online Encyclopedia of Integer sequences:

1, 4, 6, 24, 30, 24, 42, 96, 54, 120...

There is a (due to Bjorn Poonen) indicating some regularity to the solutions to this congurence

$$f(n) = n^2* \left\{\begin{array}{cl}3/2&\text{if}\quad\quad 4|n \\ 1 &\text{otherwise} \end{array}\right\}*\prod_{\substack{p|n \\ 1 \mod 4}} \left( 1 + \frac{1}{p}\right)* \prod_{\substack{p|n \\ 3 \mod 4}} \left( 1 - \frac{1}{p}\right)$$

What are some proofs to this identity ?

Sequence A060968 is the number of points on the unit circle $x^2 + y^2 \equiv 1\; (\mod n)$

1, 2, 4, 8, 4, 8, 8, 16, 12, 8, 12,...

with a similar multiplicative formula: $$g(n) = n* \left\{\begin{array}{cl}2&\text{if}\quad\quad 4|n \\ 1 &\text{otherwise} \end{array}\right\}*\prod_{\substack{p|n \\ 1 \mod 4}} \left( 1 + \frac{1}{p}\right)* \prod_{\substack{p|n \\ 3 \mod 4}} \left( 1 - \frac{1}{p}\right)$$

Perhaps there is a tower of such identities.

The multiplicative structure of these formulas could have an algorithmic interpretation. The formula for the Euler phi function

$\phi(n) = n \prod_{p|n} \left( 1 - \frac{1}{p} \right)$

This suggests a sieving algorithm to generate the list of numbers relatively prime to n

• write down the numbers 1 thru n
• for reach prime $p|n$ cross out multiples

I'd be especially interested if this type of algorithm existed for $f(n), g(n)$.

-
I wonder if these functions have appeared in the "serious" number theory literature and why. I had thought of this while trying to answer mathoverflow.net/questions/136131/calculus-over-finite-fields on this site. –  john mangual Jul 10 '13 at 13:06
The formula must be a multiplicative function, by CRT (since you're counting number of solutions to some congruence). So you need to compute the number of solutions mod prime powers $p^k$. Do this for $k = 1$ and then use Hensel (if $p = 2$, you might have to start with $k = 3$). This sort of "mass" formula is common when you consider representation numbers of quadratic forms. For instance, see the book "Rational quadratic forms" by Cassels. –  Abhinav Kumar Jul 10 '13 at 13:28
For the number of solutions mod $p$ to $\sum_{i=1}^n x_i^2 = 1$, see mathoverflow.net/questions/69576/sum-of-squares-modulo-a-prime –  Noam D. Elkies Jul 10 '13 at 13:40
Typo: the formula for a circle should be $x^2+y^2=1$ (or $\equiv 1$), not $x^2+y^2+z^2=1$. –  Noam D. Elkies Jul 10 '13 at 13:41
Yet another MO source for counting solutions of $\sum_{i=1}^n x_i^2 \equiv 1 \bmod p$: mathoverflow.net/questions/1420/… –  Noam D. Elkies Jul 10 '13 at 14:24