From: victor@ccr-p.ida.org (Victor Miller)
Newsgroups: sci.math.numberthy
Subject: Re: A result of Chowla
Date: 18 Jun 97 22:25:43 GMT

Dipankar Gupta (dgupta@acm.org) asked:

        In his paper `The least quadratic nonresidue', Ann. Math. 55(1),
        (1952), Ankeny remarks that

        ``S. Chowla has proved that there exist infinitely many primes k where
        the first c1 log k residues (mod k) are all quadratic residues.''

        Could someone provide me with a reference for this result?


Three responses were received.  Eric Bach (bach@cs.wisc.edu) and Sid
Graham (swgraham@nsf.gov) both said that to their knowledge Chowla
never published the result [But Bach was interested if anybody could
tell him otherwise].  They both remarked that the result was
discovered independently by Fridlender and Sali\`e. The references
are:

V. R. Fridlender, "On the least nth-power non-residue", Dokl. Akad. Nauk
SSSR 66 (1949) pp. 351-352.

Hans Sali\`e, "\:Uber den kleinsten positiven quadratischen Nichtrest nach
einer Primzahl", Math. Nachr. 3 (1949) pp. 7-8.

Sid Graham remarked:

I am not surprised that Chowla also proved this result independently. It is
a simple corollary of Linnik's theorem on the least prime in an arithmetic
progression.

Eric Bach said:

The proof uses quadratic reciprocity and Linnik's theorem.
We have it as an exercise (with solution -- see p. 372) in the
book Algorithmic Number Theory, vol. 1, by E. Bach and J. Shallit,
MIT Press, 1996.

and also pointed to:

        P. Tura'n, Mat. Lapok 1, 1950, 243-267.


Bach, Andrew Odlyzko (odlyzko@research.att.com) and Graham all
referred to the imporvement:

Chris Ringrose and Graham made an unconditional improvement on the
Fridlender-Salie-Chowla result; their result is that there are
infinitely many primes k with the first

c_3 (log k) (log log log k) residues all quadratic residues.  The reference is

S. W. Graham and C. Ringrose, "Lower Bounds for Least Quadratic
Non-Residues", Analytic Number Theory, Proceedings of a Conference in Honor
of Paul T. Bateman, (B. C. Berndt, H.G. Diamond, H. Halberstam, and A.
Hildebrand, editors), Birkhauser (Boston) 1990, pp. 270-309.

Finally, Odlyzko and Graham also said:

Hugh Montgomery proved the if the General Riemann Hypothesis is true, then
there are infinitely many primes k with the first c_2 (log k) (log log k)
residues all quadratic residues. The reference is

H.L. Montgomery, {\it  Topics in Multiplicative Number Theory }, Lecture
Notes in Mathematics 227 , Springer-Verlag (New York), 1971, pp. 122, 128.


               Victor Miller -- moderator Number Theory Net