# Burgess on quadratic residues and non-residues

Has any of you guys gone through Burgess's paper The distribution of quadratic residues and non-residues?

I'm having a hard time trying to disentangle his Lemma 2 (on page 108).

Do you know if there is a simpler presentation of it somewhere? For instance, is there a way to rephrase the following paragraph without resorting to the word "class"? I don't even know for sure what he is referring to by it...

"Divide the sets of values of $m_{1}, \ldots, m_{2r}$ into two classes, putting in the first class those which consist of at most $r$ distinct integers, each occurring an even number of times, and putting into the second class all other sets. The number of sets in the first class is less than $(2r)^{r}h^{r}$, and for each set the inner sum over $x$ is at most $p.$... The number of sets in the second class is at most $h^{2r}$ (trivially)."

I would really appreciate any suggestions you wish to make. If you have written about this and gained some intuition on those portions of the article (lemma 2 and lemma 3), I would be more than glad to have an opportunity to take a look at your write-ups.

Thanks.

Reference: D. A. Burgess. The distribution of quadratic residues and non-residues. Mathematika 4 (1957), 106-112.

-
"Class" is just a synonym for "set" here; often people prefer to say "class" when speaking of a set whose elements are themselves sets. – Greg Martin Apr 17 '12 at 1:56

Fix an integer $h$ and let $$S_h(x) = \sum_{t=0}^{h-1}\;\left(\frac{x+t}{p}\right)$$ Where the $(\cdot/p)$ representes the Legendre symbol. We want to prove that $$\sum_{x=0}^{p-1}S_h(x)^{2r} < (2r)^r p h^r + 4rh^{2r}\sqrt{p}$$ Developping the powers in the left and inverting summations we obtain the sum $$\sum_{m_1\dots m_{2r} = 1}^h \sum_{x=0}^{p-1} \left( \frac{(x+m_1)(x+m_2)\dots(x+m_r)}{p} \right )$$

The outer sum is over the $h^{2r}$ tuples $(m_1,\dots,m_{2r})$ where each $m_i$ varies independently from $1$ to $h$. In order to bound above this sum we divide the outer sum in two sets of tuples, in the first set we pick first the tuples $(m_1,\dots,m_{2r})$ for which the polynomial $$(x-m_1)(x-m_2) \dots (x-m_{2r})$$ is a square, in this case we have $$\sum_{x=0}^{p-1} \left( \frac{(x+m_1)(x+m_2)\dots(x+m_{2r})\,}{p} \right ) \le p$$ because the value of the polynomial is a square for every $x$ and in consequence the value of the Legendre symbol inside the sum is always 0 or 1.

Now if the polynomial is a square that means that we can group the $m_i$'s of a tuple in $r$ pairs with the same value in each pair. So the number of tuples which lead to a square polynomial can be bounded above by the number of partitions of the $2r$ positions in $r$ pairs, times the number of independent $r$-tuples of values from 1 to $h$.

The number of partitions of $1,2,\dots, 2r$ in $r$ pairs is simply $$(2r-1)(2r-3)\dots 5\cdot 3\cdot 1$$ just observe that the first index can be paired with any of the other $2r-1$ positions, and now the first free index can be paired with any of the $2r-3$ free positions, and so on. But $$(2r-1)(2r-3)\dots 5\cdot 3\cdot 1 < (2r)^r$$ as there are $r$ factors all smaller than $2r$.

Now to each pair we can assign any integer from 1 to $h$, as there are $r$ pairs we have $h^r$ possible asignations. So finally the number of tuples $m_1,\dots,m_{2r}$ wich lead to a square polynomial $(x+m_1)(x+m_2)\dots(x+m_{2r})$ is bounded by $(2r)^rh^r$

Note that the estimation of the number of tuples leading to a square polynomial is a little rough, for example with $r=2$ and $h=3$ there are only 21 tuples in this group (starting with (1,1,1,1),(1,1,2,2),(1,1,3,3),(1,2,1,2),(1,2,2,1),(1,3,1,3),(1,3,3,1),$\dots$ ), but $(2r)^rh^r= 1296$.

In the second group we pick the tuples $(m_1,\dots, m_{2r})$ for wich $(x+m_1)\dots(x+m_{2r}$ is not a square. This means that we can write them as a product $g(x)^2F(x)$ where $F(x)$ is squarefree. For the Legendre symbol we have then $$\left(g(x)^2F(x) \over p \right ) = \left( F(x) \over p \right)$$ except possibly when $g(x) = 0$, as $g(x)$ has at most degree $r$ this means that the sums $$\sum_{x=1}^p \left(g(x)^2F(x)\over p\right) \quad\text{and}\quad \sum_{x=1}^p \left(F(x)\over p\right)$$ differ at most by $r$. For the right sum we can use now the bound (André Weil) $$\left \lvert \sum_{x=0}^{p-1} \left( F(x) \over p \right ) \right \rvert \leq (\deg F -1) \sqrt{p}$$ and so $$\left \lvert \sum_{x=0}^{p-1} \left( g(x)^2F(x) \over p \right ) \right \rvert \leq 2r + 2r\sqrt{p}< 4r\sqrt{p}$$

As the number of tuples in this case is at most $h^{2r}$ (the total number of tuples) we finally have the toal upper bound of $h^{2r}\sqrt{p}$ to the sum limited to this second set of tuples giving the lemma.

EDIT 2: I have rewritten the proof to make it more clear.

-
Would you explain this part : "there are at most (2r)^r ways to pick r pairs out of 2r quantities..." ? What's the exact link between those 2r-tuples we are considering and the number of pairs you mention? By a pair you mean something like (a,b), don't you? – absalon Apr 18 '12 at 21:48
I have edited the answer to make it more clear. I hope this helps. – Esteban Crespi Apr 19 '12 at 11:40
Thanks... I'll take a look at the new version of your post. – absalon Apr 19 '12 at 20:03
One quick question: when you write "...(x−m_1)(x−m_2)…(x−m_2r) is a square", do you actually mean the - sign? – absalon Apr 19 '12 at 20:12
No that's an error I correct it – Esteban Crespi Apr 19 '12 at 21:04

You would need to give much more detail for anyone to be sure what is being discussed. However, from later articles that refer to Burgess, it seems he is generally bounding the first quadratic residue modulo some fixed prime. See http://oeis.org/A053760 and http://mathworld.wolfram.com/QuadraticNonresidue.html

The significance of "most r distinct integers, each occurring an even number of times," is that an actual square, call it $m^2,$ when reduced $\pmod p,$ gives a "quadratic residue." So I think he is saying squares where the prime factorization is restricted.

Well, I have never seen the paper. However, the size of the smallest quadratic residue $\pmod p$ for some prime $p$ is found in practice to be quite small, and this is reflected in the consequences of assuming a Generalized Riemann Hypothesis, see the reference by Wedeniwski 2001. However, it may be that Burgess has one of the very best bounds that has actually been proved. See Hildebrand 1987

Here is a list that gives, more or less, primes with surprisingly large first quadratic nonresidues, OEIS

-