Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
5  
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
1  
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
2  
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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.