10
$\begingroup$

What is the probability that the sum of squares of n randomly chosen numbers from $Z_p$ is a quadratic residue mod p?

That is, let $a_1$,..$a_n$ be chosen at random. Then how often is $\Sigma_i a^2_i$ a quadratic residue?

$\endgroup$
5
  • 2
    $\begingroup$ Speaking as a non-expert, I should think that for n much larger than, say, log(p) (or maybe even 4), the probability should approach 1/2. Are you interested in the answer for n << p, or p << n, or is there some other relationship between n and p which would make answering the question easier? Gerhard "Email Me About System Design" Paseman, 2011.07.05 $\endgroup$ Jul 5, 2011 at 22:34
  • $\begingroup$ Also, I assume p is prime from your title, but it would help to call that out in the body of the question. Gerhard "Email Me About System Design" Paseman, 2011.07.05 $\endgroup$ Jul 5, 2011 at 22:37
  • $\begingroup$ Yes, $p$ prime — and odd — is implicit both in the title and in the use of "quadratic residue". $\endgroup$ Jul 5, 2011 at 22:53
  • $\begingroup$ This is my intuition as well. n should be at most polynomial in log(p) and p is meant to be a prime. Is there a standard theorem for this? $\endgroup$
    – user16203
    Jul 5, 2011 at 22:54
  • $\begingroup$ As you can see, if $p \rightarrow \infty$ then already $n=3$ is enough to get near-equidistribution (and $n=2$ fails only because 0 is over- or under-represented depending on whether $p$ is $+1$ or $−1 \bmod 4$). $\endgroup$ Jul 6, 2011 at 2:36

4 Answers 4

26
$\begingroup$

This probability can be calculated exactly, and indeed it approaches $1/2$ rather quickly — more precisely, for each $p$ it approaches the fraction $(p-1)/(2p)$ of quadratic residues $\bmod p$. This can be proved by elementary means, but perhaps the nicest way to think about it is that if you choose $n$ numbers $a_i$ independently and sum $a_i^2 \bmod p$, the resulting distribution is the $n$-th convolution power of the distribution of a random single square — so its discrete Fourier transform is the $n$-th power of the D.F.T., call it $\gamma$, of the distribution of $a^2 \bmod p$. For this purpose $\gamma$ is normalized so $\gamma(0)=1$. Then for $k \neq 0$ we have $\gamma(k) = (k/p) \gamma(1)$ [where $(\cdot/p)$ is the Legendre symbol], and $$ p \gamma(1) = \sum_{a \bmod p} \exp(2\pi i a^2/p), $$ which is a Gauss sum and is thus a square root of $\pm p$. It follows that $|\gamma(k)| = p^{-1/2}$, from which we soon see that each value of the convolution approaches $1/p$ at the exponential rate $p^{-n/2}$, and the probability you asked for approaches $(p-1)/(2p)$ at the same rate.

As noted above, this result, and indeed the exact probability, can be obtained by elementary means, yielding a (known but not well-known) alternative proof of Quadratic Reciprocity(!). But that's probably too far afield for the present purpose.

$\endgroup$
10
  • $\begingroup$ From your answer I infer 0 does not count as a quadratic residue mod p. (I definitely agree it is not as interesting as a quadratic residue, but should it be really ostracized from the set of squares?) Gerhard "Supports The Rights of Zero" Paseman, 2011.07.05 $\endgroup$ Jul 5, 2011 at 23:12
  • 6
    $\begingroup$ While 0 is indeed a square, it does not count as a "quadratic residue" (nor as a "quadratic nonresidue" — though this term should really have been "nonquadratic residue"). Properly 0 should count as half square and half non-square (think about the number of square roots), and then the limit would really be 1/2. $\endgroup$ Jul 5, 2011 at 23:55
  • 5
    $\begingroup$ For quadratic reciprocity: let $n$ be an odd prime prime $l \neq p$, and $N$ the number of solutions of $\sum_{i=1}^l a_i^2 = 1 \bmod p$. Cyclic permutation of the coordinates has two fixed points or none according as $N \equiv 2$ or $0 \bmod l$. From the formula for $N$ it soon follows that $(l/p) \equiv {p^*}^{(l-1)/2} \bmod l$ where $p^* = \gamma(1)^2 = p$ or $-p$ according as $p \equiv 1$ or $-1 \bmod 4$. By Legendre's formula this means $(l/p) = (p^*/l)$. Exercise: modify this to determine $(2/p)$ from the count of solutions of $x_1^2 + x_2^2 \equiv 1 \bmod p$. [Original source?] $\endgroup$ Jul 6, 2011 at 0:01
  • 1
    $\begingroup$ :-) If no reference turns up here I'll post a reference request as a question... It worked quite well for my one previous M.O. query (on the integral for $\frac{22}{7} - \pi$). $\endgroup$ Jul 6, 2011 at 3:17
  • 5
    $\begingroup$ This idea can also be used to get at a few memorable cases of higher reciprocity. For example: if $p \equiv 1 \bmod 3$, and you already know that the number of solutions of $x^3 + y^3 = 1 \bmod p$ is $p - 2 - a$ where $4p = a^2 + 27 b^2$ for some integers $a,b$, then it follows at once that $2$ is a cubic residue iff $a$ is even, that is, iff $p$ itself can be written as $a^2 + 27b^2$. [NB the count is $p-2-a$, not the familiar $p+1-a$, because for this purpose we must exclude the three points at infinity.] $\endgroup$ Jul 6, 2011 at 14:41
9
$\begingroup$

The probability depends on the parity of $n$ and the residue of $p$ modulo $4$: it can be calculated in a straightforward way using Gauss sums.

Let $n$ be $2k$ or $2k+1$, and let $p\equiv r\pmod{4}$ where $r=\pm 1$. Then, assuming I made no mistake, the probability equals $$ \frac{p+1}{2p}+\frac{p-1}{2p}(rp)^{-k}. $$

Note that in my calculation I regarded zero as a quadratic residue. If we exclude zero then the final answer will look slightly different, with a main term $\frac{p-1}{2p}$ as Noam Elkies said.

$\endgroup$
1
  • $\begingroup$ Hah! A fellow Zero supporter. Welcome, Zero-brother! Gerhard "Sound The Drums And Cannon" Paseman, 2011.07.05 $\endgroup$ Jul 5, 2011 at 23:59
7
$\begingroup$

.5

Let me atone for giving too few details by giving too many.

Let $$S=\sum_{a_1=0}^{p-1}\dots\sum_{a_n=0}^{p-1}\sum_{t=0}^{p-1}\sum_{m=0}^{p-1}e^{2\pi im(a_1^2+\cdots+a_n^2-t^2)/p} $$ The innermost sum is $p$ if $a_1^2+\cdots+a_n^2-t^2\equiv0\pmod p$ and zero otherwise, so $S$ counts $2p$ whenever $a_1^2+\cdots+a_n^2$ is a (nonzero) quadratic residue, $p$ whenever it's zero. On the other hand, $$ S=\sum_{m=0}^{p-1}\sum_{a_1=0}^{p-1}\dots\sum_{a_n=0}^{p-1}\sum_{t=0}^{p-1}e^{2\pi im(a_1^2+\cdots+a_n^2-t^2)/p} $$ so $$ S=p^{n+1}+\sum_{m=1}^{p-1}\sum_{a_1=0}^{p-1}\dots\sum_{a_n=0}^{p-1}\sum_{t=0}^{p-1}e^{2\pi im(a_1^2+\cdots+a_n^2-t^2)/p} $$ so $$ S=p^{n+1}+\sum_{m=1}^{p-1}\left(\left(\sum_{a_1=0}^{p-1}e^{2\pi ima_1^2/p}\right)\cdots\left(\sum_{a_n=0}^{p-1}e^{2\pi ima_n^2/p}\right)\left(\sum_{t=0}^{p-1}e^{2\pi imt^2/p}\right)\right) $$ Each of those inner sums is a Gauss sum and known to equal $\sqrt p$ in modulus (more detail: the sum is ${m\overwithdelims()p}\sqrt{{-1\overwithdelims()p}p}$), so $|S-p^{n+1}|\le(p-1)p^{(n+1)/2}$. For $n\gt1$, the main term beats the error term, and you get a good estimate.

$\endgroup$
4
  • 1
    $\begingroup$ If you're going for the shortest answer, I recommend changing character sets. Gerhard "Brevity Is The Soul" Paseman, 2011.07.05 $\endgroup$ Jul 5, 2011 at 22:48
  • $\begingroup$ Also $\frac12$ is not quite right if $p$ is fixed and only $n$ grows. $\endgroup$ Jul 5, 2011 at 23:00
  • $\begingroup$ Or "Levity is the role of wit"... $\endgroup$ Jul 5, 2011 at 23:57
  • $\begingroup$ The answer is worth the question. +1 $\endgroup$ Jul 6, 2011 at 2:55
1
$\begingroup$

Here is a slightly different argument: Let $Q$ be a non degenerate quadratic form over $\mathbb{F}_q$ of rang $n$ and determinant $d$. Let $A(n,d)=|\{x\in \mathbb{F}_q^n:Q(x)=0\}|$. The claim is that $A(n,d)=q^{n-1}+O(q^{n/2})$. For $n>2$ we can write $Q(X)=Q_0(X_1,\ldots,X_{n-2}) +X_{n-1}X_n$, where $Q_0$ is a form of rank $n-2$ in the variables $X_1,\ldots,X_{n-2}$. This decomposition shows instantly that that $A(n,d)=(2 q-1) A(-d,n-2) +(q-1) (q^{n-2}-A(-d,n-2))$. Proceeding by induction we get the estimate $A(n,d)=q^{n-1}+O(q^{n/2})$. (The error term can be computed exactly using Gauss sums). Applying this to the forms $X_1^2+\cdots +X_n^2-X_{n+1}^2$ and $X_1^2+\cdots+ X_n^2$ we get that the desired probability is $(A(n+1,-1)-A(n,1))/(2 q^n)= (q-1)/(2q) +O(q^{-n/2})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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