Pólya conjecture
Encyclopedia
In number theory
, the Pólya conjecture stated that 'most' (i.e. more than 50%) of the natural number
s less than any given number have an odd number of prime factor
s. The conjecture
was posited by the Hungarian mathematician George Pólya
in 1919, and proved 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.
Equivalently, it can be stated in terms of the summatory Liouville function, 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.
in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10361.
An explicit counterexample, of n = 906,180,359 was given by R. Sherman Lehman in 1960; the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.
The Pólya conjecture fails to hold for most values of n in the region of 906,150,257 ≤ n ≤ 906,488,079. In this region, the Liouville function reaches a maximum value of 829 at n = 906,316,571.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the Pólya conjecture stated that 'most' (i.e. more than 50%) of the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s less than any given number have an odd number of prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s. The conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
was posited by the Hungarian mathematician George Pólya
George Pólya
George Pólya was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory...
in 1919, and proved 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.
Statement
Pólya's conjecture states that for any n (> 1), if we partition the natural numbers less than or equal to n (excluding 0) 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 24 = 23 × 31 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
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
Pólya's conjecture was disproven by C. B. HaselgroveC. Brian Haselgrove
Colin Brian Haselgrove was an English mathematician who is best known for his disproof of the Pólya conjecture in 1958....
in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10361.
An explicit counterexample, of n = 906,180,359 was given by R. Sherman Lehman in 1960; the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.
The Pólya conjecture fails to hold for most values of n in the region of 906,150,257 ≤ n ≤ 906,488,079. In this region, the Liouville function reaches a maximum value of 829 at n = 906,316,571.