Pólya conjecture

In mathematics, the Pólya conjecture states that 'most' (i.e. more than 50%) 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, and disproven, i.e. shown to be false, in 1958. The size of the smallest counter-example is often used to show how a conjecture can be true for many numbers, and still be false.

tatement

Pólya's conjecture states that for any "n" (> 1), if we divide the natural numbers less than or equal to "n" (excluding 0) into those which have an "odd" number of prime factors, and those which have an "even" number of prime factors, then the former set has more members than the latter set, or the same number of members. (Repeated prime factors are counted the requisite number of times - thus 24 = 2³ × 3¹ has 3 + 1 = 4 factors i.e. an even number of factors, while 30 = 2 × 3 × 5 has 3 factors, i.e. an odd number of factors.)

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

:$L(n)\; =\; sum\_\{k=1\}^n\; lambda(k)\; leq\; 0$

for all "n". Here, $lambda(k)=(-1)^\{Omega(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

Pólya's conjecture was disproven by C. B. Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10³⁶¹.

An explicit counterexample, of "n" = 906180359 was given by R. S. Lehman in 1960; the smallest counterexample is "n" = 906150257, found by Minoru Tanaka in 1980.

The Pólya conjecture fails to hold for most values of $n$ in the region of 906150257 ≤ "n" ≤ 906488079. In this region, the function reaches a maximum value of 829 at "n" = 906316571.

References

* G. Pólya, "Verschiedene Bemerkungen zur Zahlentheorie." "Jahresbericht der deutschen Math.-Vereinigung" 28 (1919), 31-40.
*cite journal
first = C.B.
last = Haselgrove
year = 1958
title = A disproof of a conjecture of Pólya
journal = Mathematika
volume = 5
pages = 141–145
* R.S. Lehman, "On Liouville's function." Math. Comp. 14 (1960), 311-320.
* M. Tanaka, "A Numerical Investigation on Cumulative Sum of the Liouville Function." Tokyo Journal of Mathematics 3, (1980) 187-189.
*