OFFSET
2,3
COMMENTS
In 1918 Polya and Vinogradov (independently) proved an upper bound for a(n) and Schur proved a lower bound:
sqrt(p)/2*pi < a(n) < sqrt(p)*log(p), where p is the n-th prime.
Named after the Hungarian mathematician George Pólya (1887-1985) and the Soviet mathematician Ivan Matveevich Vinogradov (1891-1983). - Amiram Eldar, Jun 22 2021
REFERENCES
I. M. Vinogradov, Über eine asymptotische Formel aus der Theorie der binaeren quadratischen Formen, J. Soc. Phys. Math. Univ. Permi, Vol. 1 (1918), pp. 18-28.
I. M. Vinogradov, Elements of Number Theory, 5th revised ed., Dover, 1954, p. 200.
LINKS
PlanetMath, Polya Vinogradov Inequality.
G. Polya, Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 21-29.
I. Schur, Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Polya: Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), pp. 30-36.
Eric Weisstein's World of Mathematics, Polya-Vinogradov Inequality.
Wikipedia, Character Sum.
Wikipedia, Legendre symbol.
Wikipedia, Quadratic residue.
FORMULA
a(n) = max_{0<k<p} |Sum_{i=1..k} L(i/p)|, where p is the n-th prime, n>1, and L(i/p) is the Legendre symbol.
EXAMPLE
The initial term is a(2) = 1 because the 2nd prime is 3 and L(1/3) = 1 and L(2/3) = -1, so |Sum_{i=1..k} L(i/3)| = 1 and 0 for k = 1 and 2, resp., and so max = 1.
MATHEMATICA
Table[Max[ Table[Abs[Sum[JacobiSymbol[i, Prime[n]], {i, 1, k}]], {k, 1, Prime[n] - 1}]], {n, 2, 100}]
PROG
(PARI) a(n) = my(p=prime(n)); vecmax(vector(p-1, k, vecsum(vector(k, i, issquare(Mod(i, p)))) - vecsum(vector(k, i, !issquare(Mod(i, p)))))); \\ Michel Marcus, Mar 03 2023
CROSSREFS
Cf. A055088 (Triangle of generalized Legendre symbols L(a/b), with 1's for quadratic residues and 0's for quadratic non-residues [replace the 0's with -1's]).
KEYWORD
easy,nonn
AUTHOR
Jonathan Sondow, May 17 2010
STATUS
approved