Sum of squares modulo a prime - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T07:53:44Z http://mathoverflow.net/feeds/question/69576 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69576/sum-of-squares-modulo-a-prime Sum of squares modulo a prime unknown (google) 2011-07-05T22:15:46Z 2011-07-07T00:26:37Z <p>What is the probability that the sum of squares of n randomly chosen numbers from $Z_p$ is a quadratic residue mod p?</p> <p>That is, let $a_1$,..$a_n$ be chosen at random. Then how often is $\Sigma_i a^2_i$ a quadratic residue?</p> http://mathoverflow.net/questions/69576/sum-of-squares-modulo-a-prime/69577#69577 Answer by Gerry Myerson for Sum of squares modulo a prime Gerry Myerson 2011-07-05T22:31:39Z 2011-07-06T04:24:19Z <p>.5</p> <p>Let me atone for giving too few details by giving too many. </p> <p>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. </p> http://mathoverflow.net/questions/69576/sum-of-squares-modulo-a-prime/69580#69580 Answer by Noam D. Elkies for Sum of squares modulo a prime Noam D. Elkies 2011-07-05T22:51:56Z 2011-07-05T22:58:40Z <p>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 <code>$$p \gamma(1) = \sum_{a \bmod p} \exp(2\pi i a^2/p),$$</code> 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.</p> <p>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.</p> http://mathoverflow.net/questions/69576/sum-of-squares-modulo-a-prime/69583#69583 Answer by GH for Sum of squares modulo a prime GH 2011-07-05T23:04:14Z 2011-07-05T23:13:09Z <p>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. </p> <p>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}.$$</p> <p>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.</p> http://mathoverflow.net/questions/69576/sum-of-squares-modulo-a-prime/69598#69598 Answer by Georges for Sum of squares modulo a prime Georges 2011-07-06T03:25:30Z 2011-07-07T00:26:37Z <p>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})$.</p>