Francais | English | Espanõl

From Wikipedia, the free encyclopedia

The Pólya Conjecture is a mathematical conjecture which claims that 'most' (i.e. more than 50%) of the natural numbers have an odd number of prime factors. The conjecture was posited by the Hungarian mathematician George Pólya in 1919. It has been disproved, i.e. shown to be false.

[edit] Statement

Polya's conjecture states that for any n (>1), if we divide the natural numbers less than 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

<math>L(n) = \sum_{k=1}^n \lambda(k) \leq 0 </math>

for all n. Here, <math>\lambda(k)=(-1)^{\Omega(k)}</math> is positive if the number of prime factors of the integer k is even, and is negative if its odd. The big Omega function counts the total number of prime factors of an integer.

[edit] Disproof

Polya's conjecture was disproved by C. B. Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10³⁶¹. The extraordinarily high value of this counterexample serves to show the dangers of relying on apparently impressive bounds set by computer searches.

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

[edit] References

• G. Polya, "Verschiedene Bemerkungen zur Zahlentheorie." Jahresbericht der deutschen Math.-Vereinigung 28 (1919), 31-40.
• Haselgrove, C.B. (1958). "A disproof of a conjecture of Polya". Mathematika 5: 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.
• Weisstein, Eric W., Polya Conjecture at MathWorld.it:Congettura di Pólya