Chebyshev's Bias

In number theory, Chebyshev's bias is the phenomenon that most of the time, there are more primes of the form 4''k'' + 3 than of the form 4''k'' + 1, up to the same limit. This phenomenon was first observed by Russian mathematician Pafnuty Chebyshev in 1853.

Description

Let π(''x''; ''n'', ''m'') denote the number of primes of the form ''nk'' + ''m'' up to ''x''. By the prime number theorem (extended to arithmetic progression),

:$\pi(x;4,1)\sim\pi(x;4,3)\sim \frac\frac.$

That is, half of the primes are of the form 4''k'' + 1, and half of the form 4''k'' + 3. A reasonable guess would be that π(''x''; 4, 1) > π(''x''; 4, 3) and π(''x''; 4, 1) < π(''x''; 4, 3) each also occur 50% of the time. This, however, is not supported by numerical evidence — in fact, π(''x''; 4, 3) > π(''x''; 4, 1) occurs much more frequently. For example, this inequality holds for all primes ''x'' < 26833 except 5, 17, 41 and 461, for which π(''x''; 4, 1) = π(''x''; 4, 3). The first ''x'' such that π(''x''; 4, 1) > π(''x''; 4, 3) is 26861, that is, π(''x''; 4, 3) ≥ π(''x''; 4, 1) for all ''x'' < 26861.

In general, if 0 < ''a'', ''b'' < ''n'' are integers, GCD(''a'', ''n'') = GCD(''b'', ''n'') = 1, ''a'' is a quadratic residue mod ''n'', ''b'' is a quadratic nonresidue mod ''n'', then π(''x''; ''n'', ''b'') > π(''x''; ''n'', ''a'') occurs more often than not. This has been proved only by assuming strong forms of the Riemann hypothesis. The stronger conjecture of Knapowski and Turán, that the density of the numbers ''x'' for which π(''x''; 4, 3) > π(''x''; 4, 1) holds is 1 (that is, it holds for almost all ''x''), turned out to be false. They, however, do have a logarithmic density, which is approximately 0.9959....(Rubinstein—Sarnak, 1994)

Generalizations

This is for ''k'' = −4 to find the smallest prime ''p'' such that $\sum_\left(\frac\right)>0$ (where $\left(\frac\right)$ is the Kronecker symbol), however, for a given nonzero integer ''k'' (not only ''k'' = −4), we can also find the smallest prime ''p'' satisfying this condition. By the prime number theorem, for every nonzero integer ''k'', there are infinitely many primes ''p'' satisfying this condition.

For positive integers ''k'' = 1, 2, 3, ..., the smallest primes ''p'' are

:2, 11100143, 61981, 3, 2082927221, 5, 2, 11100143, 2, 3, 577, 61463, 2083, 11, 2, 3, 2, 11100121, 5, 2082927199, 1217, 3, 2, 5, 2, 17, 61981, 3, 719, 7, 2, 11100143, 2, 3, 23, 5, 11, 31, 2, 3, 2, 13, 17, 7, 2082927199, 3, 2, 61463, 2, 11100121, 7, 3, 17, 5, 2, 11, 2, 3, 31, 7, 5, 41, 2, 3, ... ( is a subsequence, for ''k'' = 1, 5, 8, 12, 13, 17, 21, 24, 28, 29, 33, 37, 40, 41, 44, 53, 56, 57, 60, 61, ... )

For negative integers ''k'' = −1, −2, −3, ..., the smallest primes ''p'' are

2, 3, 608981813029, 26861, 7, 5, 2, 3, 2, 11, 5, 608981813017, 19, 3, 2, 26861, 2, 643, 11, 3, 11, 31, 2, 5, 2, 3, 608981813029, 48731, 5, 13, 2, 3, 2, 7, 11, 5, 199, 3, 2, 11, 2, 29, 53, 3, 109, 41, 2, 608981813017, 2, 3, 13, 17, 23, 5, 2, 3, 2, 1019, 5, 263, 11, 3, 2, 26861, ... ( is a subsequence, for ''k'' = −3, −4, −7, −8, −11, −15, −19, −20, −23, −24, −31, −35, −39, −40, −43, −47, −51, −52, −55, −56, −59, ... )

For every (positive or negative) nonsquare integer ''k'', there are more primes ''p'' with $\left(\frac\right)=-1$ than with $\left(\frac\right)=1$ (up to the same limit) more often than not.

Extension to higher power residue

Let ''m'' and ''n'' be integers such that ''m''≥0, ''n''>0, GCD(''m'', ''n'') = 1, define a function $f(m,n)=\sum_\left(\frac\right)$, where $\phi$ is the Euler's totient function.

For example, ''f''(1, 5) = ''f''(4, 5) = 1/2, ''f''(2, 5) = ''f''(3, 5) = 0, ''f''(1, 6) = 1/2, ''f''(5, 6) = 0, ''f''(1, 7) = 5/6, ''f''(2, 7) = ''f''(4, 7) = 1/2, ''f''(3, 7) = ''f''(5, 7) = 0, ''f''(6, 7) = 1/3, ''f''(1, 8) = 1/2, ''f''(3, 8) = ''f''(5, 8) = ''f''(7, 8) = 0, ''f''(1, 9) = 5/6, ''f''(2, 9) = ''f''(5, 9) = 0, ''f''(4, 9) = ''f''(7, 9) = 1/2, ''f''(8, 9) = 1/3.

It is conjectured that if 0 < ''a'', ''b'' < ''n'' are integers, GCD(''a'', ''n'') = GCD(''b'', ''n'') = 1, ''f''(''a'', ''n'') > ''f''(''b'', ''n''), then π(''x''; ''n'', ''b'') > π(''x''; ''n'', ''a'') occurs more often than not.

References

* P.L. Chebyshev: Lettre de M. le Professeur Tchébychev à M. Fuss sur un nouveaux théorème relatif aux nombres premiers contenus dans les formes 4''n'' + 1 et 4''n'' + 3, ''Bull. Classe Phys. Acad. Imp. Sci. St. Petersburg'', 11 (1853), 208.
*
* J. Kaczorowski: On the distribution of primes (mod 4), ''Analysis'', 15 (1995), 159–171.
* S. Knapowski, Turan: Comparative prime number theory, I, '' Acta Math. Acad. Sci. Hung.'', 13 (1962), 299–314.
*

External links

*
* (where prime race 4n+1 versus 4n+3 changes leader)
* {{OEIS, A007352 (where prime race 3n+1 versus 3n+2 changes leader)

Theorems in analytic number theory
Prime numbers