number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

, the Pólya conjecture (or Pólya's conjecture) stated that "most" (i.e., 50% or more) of the

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

s less than any given number have an ''odd'' number of prime factors. The

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...

was set forth by the Hungarian mathematician

George Pólya George Pólya (; hu, Pólya György, ; December 13, 1887 – September 7, 1985) 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 fundamenta ...

in 1919, and proved false in 1958 by

C. Brian Haselgrove Colin Brian Haselgrove (26 September 1926 – 27 May 1964) was an England, English mathematician who is best known for his disproof of the Pólya conjecture in 1958. Haselgrove was educated at Blundell's School and from there won a scholar ...

. 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 the

Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...

. For this reason, it is more accurately called "Pólya's problem". The size of the smallest

counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is a ...

is often used to demonstrate the fact that a conjecture can be true for many cases and still fail to hold in general, providing an illustration of the

strong law of small numbers In mathematics, the "strong law of small numbers" is the humorous law that proclaims, in the words of Richard K. Guy (1988): In other words, any given small number appears in far more contexts than may seem reasonable, leading to many apparent ...

Statement

The Pólya conjecture states that for any ''n'' > 1, if the

natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

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 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 summatory

Liouville function The Liouville Lambda function, denoted by λ(''n'') and named after Joseph Liouville, is an important arithmetic function. Its value is +1 if ''n'' is the product of an even number of prime numbers, and −1 if it is the product of an odd number of ...

, with the conjecture being that :

L(n) = \sum_^n \lambda(k) \leq 0

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

in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10³⁶¹. 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 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

reaches a maximum value of 829 at ''n'' = 906,316,571.

References

External links

* {{DEFAULTSORT:Polya conjecture Disproved conjectures Conjectures about prime numbers