Thomas R. Nicely
Last updated 0453 GMT 21 August 2009.
See "A table of prime counts pi(x) to 1e16" for an explanation of the functions pi(x), Li(x), and R(x) discussed in this paper.
Gauss and Riemann conjectured that Li(n) > pi(n) for all sufficiently large integers n. Excluded trivial exceptions include all n < 2; n=2,3,4,5,7 if Li(2, n) is used; and scattered values of n as large as n=23 if a rounded or truncated value of Li(2, n) is used. The inequality is true for all other integers for which pi(n) has been computed to date. However, it was proven by J. E. Littlewood (1914) that it is false for infinitely many values of n; more specifically, there exists a strictly monotonically increasing infinite sequence of integers over which the sign of Li(n) - pi(n) is strictly alternating. Thus there must exist an integer N > 23 such that Li(n) > pi(n) for all integers n, 23 < n < N, but Li(N) <= pi(N).
However, Littlewood's proof was not constructive, and the problem of determining an upper bound for N was first attacked by S. Skewes, who proved (1933) that the Riemann Hypothesis implies N < exp(exp(exp(79))) < 10^(10^(10^34)))---the infamous "Skewes' number." Skewes also proved a weaker (even larger) upper bound unconditionally (1955), namely N < exp(exp(exp(exp(7.7)))) < 10^(10^(10^1000))) (the final exponent can in fact be replaced by 959). In consequence, the problem of determining N, or at least confining it within ever narrower bounds, is often referred to as "Skewes' problem." R. S. Lehman (1966) improved the upper bound to N < 1.65e1165, and H. J. J. te Riele (1986) improved it to N < 6.69e370. Most recently, Carter Bays and Richard H. Hudson (2000) proved that N < 1.39822e316.
It is not entirely clear which of these upper bounds were established for Li(0, N) and which ones were established for Li(2, N). More likely than not, each one is valid for both quantities; and in any case, an upper bound valid for Li(0, N) would also be valid for the smaller quantity Li(2, N). It is also unlikely that the distinction between Li(x) < pi(x) and Li(x) <= pi(x) is relevant; indeed, I would conjecture that Li(x) cannot be an integer for any integer x > 2.
Lower bounds for N (applicable to both Li(0, N) and Li(2, N)) have been less well investigated. Apparently Gauss himself verified that N > 3000000. J. B. Rosser and L. Schoenfeld extended this to N > 1e8 ("Approximate formulas for some functions of prime numbers," Illinois J. Math. 6 (1962), 64-94). Richard P. Brent verified that N > 1e11 ("Irregularities in the distribution of primes and twin primes, " Math. Comp. 29:129 (1975), 43-56, MR 51 #5522; also Corrigendum, ibid. 30:133 (1976), 198, MR 53 #302, and Addendum, "Tables concerning irregularities in the distribution of primes and twin primes to 1e11," (August, 1975), reviewed ibid. 30:379 (1976)). Andrew Odlyzko improved the lower bound to N > 1.59e13 (1993, unpublished). Most recently, Tadej Kotnik has verified computationally that N > 10^14; see "The prime-counting function and its analytic approximations," Adv. Comput. Math. 29:55-70 (Springer, 2008, DOI 10.1007/s10444-007-9039-2). Kotnik also contributed some of the information herein presented.
Douglas A. Stoll reports the following results concerning extreme values of the discrepancies dL = Li(x) - pi(x) and dR = R(x) - pi(x). Function domains are taken to be only those integers > 1. Domains, intervals, and regions have been determined by Thomas R. Nicely.
x = 604346776188
pi(x) = 23167757274
R(x) = 23167757274.0000000025880346109002343123324439...
R(x) - pi(x) = 2.5880346109002343123324439e-9