Pólya conjecture

In number theory, the Pólya conjecture stated that "most" (i.e., 50% or more) of the natural numbers less than any given number have an odd number of prime factors. The conjecture was posited by the Hungarian mathematician George Pólya in 1919,[1] and proved false in 1958 by C. Brian Haselgrove.

Summatory Liouville function L(n) up to n = 107. The readily visible oscillations are due to the first non-trivial zero of the Riemann zeta function.
Closeup of the summatory Liouville function L(n) in the region where the Pólya conjecture fails to hold.
Logarithmic graph of the negative of the summatory Liouville function L(n) up to n = 2 × 109. The green spike shows the function itself (not its negative) in the narrow region where the conjecture fails; the blue curve shows the oscillatory contribution of the first Riemann zero.

The size of the smallest counterexample is often used to show how a conjecture can be true for many cases, and still be false,[2] providing an illustration for the strong law of small numbers.

Statement

Pólya conjecture states that for any n (> 1), if the natural numbers less than or equal to n (excluding 0) are partitioned into those with an odd number of prime factors, and those with an even number of prime factors, then the former set has at least as many members as the latter set. (Repeated prime factors are counted the requisite number of times—thus 18 = 21 × 32 has 1 + 2 = 3 prime factors i.e. an odd number, while 60 = 22 × 3 × 5 has 4 prime factors, i.e. an even number.)

Equivalently, it can be stated in terms of the summatory Liouville function, with the conjecture being that

for all n > 1. Here, λ(k) = (−1)Ω(k) is positive if the number of prime factors of the integer k is even, and is negative if it is odd. The big Omega function counts the total number of prime factors of an integer.

Disproof

The Pólya conjecture was disproved by C. Brian Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10361.[3]

An explicit counterexample, of n = 906,180,359 was given by R. Sherman Lehman in 1960;[4] the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.[5]

The conjecture fails to hold for most values of n in the region of 906,150,257 ≤ n ≤ 906,488,079. In this region, the summatory Liouville function reaches a maximum value of 829 at n = 906,316,571.

References
  1. Pólya, G. (1919). "Verschiedene Bemerkungen zur Zahlentheorie". Jahresbericht der Deutschen Mathematiker-Vereinigung (in German). 28: 31–40. JFM 47.0882.06.
  2. Stein, Sherman K. (2010). Mathematics: The Man-Made Universe. Courier Dover Publications. p. 483. ISBN 9780486404509..
  3. Haselgrove, C. B. (1958). "A disproof of a conjecture of Pólya". Mathematika. 5 (02): 141–145. doi:10.1112/S0025579300001480. ISSN 0025-5793. MR 0104638. Zbl 0085.27102.
  4. Lehman, R. S. (1960). "On Liouville's function". Mathematics of Computation. Mathematics of Computation. 14 (72): 311–320. doi:10.2307/2003890. JSTOR 2003890. MR 0120198.
  5. Tanaka, M. (1980). "A Numerical Investigation on Cumulative Sum of the Liouville Function". Tokyo Journal of Mathematics. 3 (1): 187–189. doi:10.3836/tjm/1270216093. MR 0584557.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.