Innumber theory, thePólya conjecture (orPólya's conjecture) stated that "most" (i.e., 50% or more) of thenatural numbersless than any given number have anodd number ofprime factors. Theconjecture was set forth by the Hungarian mathematicianGeorge Pólya in 1919,[1] and proved false in 1958 byC. Brian Haselgrove. Though mathematicians typically refer to this statement as the Pólya conjecture, Pólya never actually conjectured that the statement was true; rather, he showed that the truth of the statement would imply theRiemann hypothesis. For this reason, it is more accurately called "Pólya's problem".
The size of the smallestcounterexample is often used to demonstrate the fact that a conjecture can be true for many cases and still fail to hold in general,[2] providing an illustration of thestrong law of small numbers.
The Pólya conjecture states that for anyn > 1, if thenatural numbers less than or equal ton (excluding 0) are partitioned into those with anodd number of prime factors and those with aneven number of prime factors, then the former set has at least as many members as the latter set. Repeated prime factors are counted repeatedly; for instance, we say that 18 = 2 × 3 × 3 has an odd number of prime factors, while 60 = 2 × 2 × 3 × 5 has an even number of prime factors.
Equivalently, it can be stated in terms of the summatoryLiouville function, with the conjecture being that
for alln > 1. Here, λ(k) = (−1)Ω(k) is positive if the number of prime factors of the integerk is even, and is negative if it is odd. The big Omega function counts the total number of prime factors of an integer.
The Pólya conjecture was disproved byC. Brian Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10361.[3]
A (much smaller) explicit counterexample, ofn = 906,180,359 was given byR. Sherman Lehman in 1960;[4] the smallest counterexample isn = 906,150,257, found by Minoru Tanaka in 1980.[5]
The conjecture fails to hold for most values ofn in the region of 906,150,257 ≤n ≤ 906,488,079. In this region, the summatoryLiouville function reaches a maximum value of 829 atn = 906,316,571.