Sum of Quadratic Residues

Date: 07/22/99 at 09:42:27
From: Einar Andresen
Subject: Number Theory / Sum of quadratic residues

Dear Dr. Math, 

Maybe this is a bit to advanced - I'll try anyway.

I'm an ex-mathematician trying to refresh my maths on my own. Now I've 
read Niven - Zuckerman - Montgomery, _Introduction to the Theory of 
Numbers_, 5th edition - and enjoy it.

I solved the problem 3.1.15, essentially showing that if prime
p = 4k+1, then the sum of the quadratic residues in (0,p) equals the 
sum of the non-residues.

Question: What happens if p = 4k+3? The difference

     d = (sum nonresidues) - (sum residues)

must be divisible by p if p > 3. I used a spreadsheet and found that
d > 0 for n < 1200. The minimum value of d/p, 1, is obtained only for 
a few values of p, the largest one being p = 163.

Is it known or easy to prove that d > 0 for all p?
Is it known or easy to prove that d -> infinity when p -> infinity?

Yours sincerely
Einar Andresen, Oslo, Norway

Date: 07/23/99 at 08:53:11
From: Doctor Rob
Subject: Re: Number Theory / Sum of quadratic residues

Thanks for writing to Ask Dr. Math.

Your question is very interesting. The quantity you have discovered is 
quite famous and well known. It is called the class number of the 
quadratic number field Q(sqrt[-p]), and is denoted by the letter h. 
This is the order of a finite abelian group, called the class group.

Proving this fact is beyond elementary number theory, but can be found 
in Borevich and Shafarevich, _Number Theory_, where it is a 
consequence of formula (4.3) on p. 344, together with formula (8.5) on 
p. 237, by setting d = D = -p = 1 (mod 4), and chi(x) = (x/p), the 
Legendre symbol.

Yes, it is known that h > 0, since it is the order of a group, and 
must be a positive integer. It is also known that h -> infinity as 
p -> infinity. This is a consequence of the fact that for any value 
of h, there are only a finite number of p that correspond to it. This 
last fact is hard, and only recently proven.

To define the class group of a number field F = Q(alpha), start with 
the ring Z[alpha]. Find its integral closure, that is, the set of all 
elements of F which are roots of monic polynomials in Z[x]. That is 
denoted O_F. That will include Z[alpha], and may be larger or equal to 
it. O_F is a commutative ring with 1.

In O_F, look at the set of all ideals. There is a natural way to 
define the product of two ideals I and J: I*J is the set of all finite 
sums of products formed by an element of I times an element of J. 
Under this operation, the ideals form a semigroup.

Define an equivalence relation on the set of ideals in the following 
way: if I and J are ideals, then I ~ J iff there exist a and b in O_F 
such that (a)*I = (b)*J. This partitions the set of ideals into 
equivalence classes. All the principal ideals lie in one of the 
classes.

There is a natural multiplicative structure on the classes induced by 
multiplication of ideals. If I and J are ideals, and [I] and [J] are 
their equivalence classes, then [I]*[J] = [I*J]. You have to check 
that this is well-defined (doesn't depend on which I and J in the 
class you pick). You can also prove that the set of equivalence 
classes with this operation form an abelian group. That's not too 
hard.  The hard part is showing that this group is finite. This is the 
class group of F mentioned above, and h is its order.

In the case of a quadratic number field F = Q(sqrt[-p]) with p = 3 
(mod 4), it turns out that

     O_F = Z[sqrt(-p)] = {u+v*sqrt[-p]:u,v in Z}.

Every ideal I can be generated by two elements:

     I = (t, u+v*sqrt[-p])

where t, u, and v are in Z, and t | u^2+p*v^2. Now the class number 
counts the number of equivalence classes of ideals. All the principal 
ideals lie in one class, so h = 1 if and only if every ideal is 
principal if and only if there is unique factorization in the ring
O_F = Z[sqrt(-p)]. As you noticed, it turns out that the largest p for 
which this ring has unique factorization is p = 163. (This is also 
hard to prove, and was done only in the last 20 years, although 
something equivalent was conjectured by Gauss [and maybe even Euler].)

Much interesting mathematics springs from the study of class numbers 
and class groups. Perhaps you'll see this if you ever study Algebraic 
Number Theory.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/