cp's OEIS Frontend

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.

%I A177865 #33 Feb 16 2025 08:33:12
%S A177865 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,
%T A177865 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,
%U A177865 10,13,11,14,25,11,13,14,12,17,12,12,27,19,16,15,27,12,12,12,12,27,11,30
%N 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.
%C A177865 In 1918 Polya and Vinogradov (independently) proved an upper bound for a(n) and Schur proved a lower bound:
%C A177865 sqrt(p)/2*pi < a(n) < sqrt(p)*log(p), where p is the n-th prime.
%C A177865 Named after the Hungarian mathematician George Pólya (1887-1985) and the Soviet mathematician Ivan Matveevich Vinogradov (1891-1983). - _Amiram Eldar_, Jun 22 2021
%D A177865 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.
%D A177865 I. M. Vinogradov, Elements of Number Theory, 5th revised ed., Dover, 1954, p. 200.
%H A177865 PlanetMath, <a href="https://planetmath.org/polyavinogradovinequality">Polya Vinogradov Inequality</a>.
%H A177865 G. Polya, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002504952">Über die Verteilung der quadratischen Reste und Nichtreste</a>, Goettingen Nachr. (1918), 21-29.
%H A177865 I. Schur, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002504960">Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Polya: Über die Verteilung der quadratischen Reste und Nichtreste</a>, Goettingen Nachr. (1918), pp. 30-36.
%H A177865 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Polya-VinogradovInequality.html">Polya-Vinogradov Inequality</a>.
%H A177865 Wikipedia, <a href="http://en.wikipedia.org/wiki/Character_sum">Character Sum</a>.
%H A177865 Wikipedia, <a href="http://en.wikipedia.org/wiki/Legendre_symbol">Legendre symbol</a>.
%H A177865 Wikipedia, <a href="http://en.wikipedia.org/wiki/Quadratic_residue">Quadratic residue</a>.
%F A177865 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.
%e A177865 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.
%t A177865 Table[Max[ Table[Abs[Sum[JacobiSymbol[i, Prime[n]], {i, 1, k}]], {k, 1, Prime[n] - 1}]], {n, 2, 100}]
%o A177865 (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
%Y A177865 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]).
%Y A177865 Cf. also A095102, A165580, A165977, A207291, A207292.
%K A177865 easy,nonn
%O A177865 2,3
%A A177865 _Jonathan Sondow_, May 17 2010