A177865 Polya-Vinogradov numbers: a(n) is the maximum over all k > 0 of |#(quadratic residues modulo p up to k) - #(quadratic nonresidues modulo p up to k)| where p is the n-th prime and n > 1.

1, 1, 2, 3, 2, 2, 3, 5, 3, 6, 4, 4, 5, 8, 5, 9, 4, 6, 10, 5, 10, 9, 6, 6, 7, 10, 9, 6, 6, 10, 15, 7, 9, 7, 14, 8, 9, 18, 9, 15, 7, 19, 8, 11, 18, 12, 15, 15, 9, 10, 22, 8, 21, 10, 21, 11, 22, 14, 10, 13, 11, 14, 25, 11, 13, 14, 12, 17, 12, 12, 27, 19, 16, 15, 27, 12, 12, 12, 12, 27, 11, 30

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

Table of n, a(n) for n=2..83.

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]).

Cf. also A095102, A165580, A165977, A207291, A207292.

Sequence in context: A096258 A049879 A053812 * A307835 A341651 A017828

Adjacent sequences: A177862 A177863 A177864 * A177866 A177867 A177868

Keyword

easy,nonn

Author

Jonathan Sondow, May 17 2010

Status

approved