Pólya conjecture

---

title: "Pólya conjecture" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["disproved-conjectures", "conjectures-about-prime-numbers"] description: "Disproven conjecture in number theory" topic_path: "general/disproved-conjectures" source: "https://en.wikipedia.org/wiki/Pólya_conjecture" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Disproven conjecture in number theory ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/d/d0/Liouville-big.svg" caption="Summatory Liouville function ''L''(''n'') up to ''n'' = 10⁷. The (disproven) conjecture states that this function is always negative. The readily visible oscillations are due to the first non-trivial zero of the [[Riemann zeta function]]."] ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/f/f7/Liouville-polya.svg" caption="Closeup of the summatory Liouville function ''L''(''n'') in the region where the Pólya conjecture fails to hold."] ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/4/42/Liouville-log.svg" caption="Logarithmic graph of the negative of the summatory Liouville function ''L''(''n'') up to ''n'' = 2 × 10⁹. The green spike shows the function itself (not its negative) in the narrow region where the conjecture fails; the blue curve shows the oscillatory contribution of the first Riemann zero."] ::

In number theory, the Pólya conjecture (or Pólya's conjecture) stated that "most" (i.e., 50% or more) of the natural numbers less than any given number have an odd number of prime factors. The conjecture was set forth by the Hungarian mathematician George Pólya in 1919,{{cite journal |last=Pólya |first=G. |authorlink=George Pólya |date=1919 |title=Verschiedene Bemerkungen zur Zahlentheorie |language=German |journal=Jahresbericht der Deutschen Mathematiker-Vereinigung |jfm=47.0882.06 |volume=28 |pages=31–40

The size of the smallest counterexample 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.

Statement

The Pólya conjecture states that for any n1, if the natural numbers 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, with the conjecture being that

:L(n) = \sum_{k=1}^n \lambda(k) \leq 0

for all n1. Here, \lambda(k)=(-1)^{\Omega(k)}, where \Omega(k) counts the total number of prime factors of k. Thus \lambda(k) is positive if the number of prime factors of k is even, and is negative if it is odd.

Disproof

The Pólya conjecture was disproven by C. Brian Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10361.{{cite journal | last = Haselgrove | first = C. B. | authorlink = C. Brian Haselgrove | date = 1958 | title = A disproof of a conjecture of Pólya | journal = Mathematika | issn=0025-5793 | doi = 10.1112/S0025579300001480 | mr = 0104638 | zbl=0085.27102 | volume = 5 | issue = 2 | pages = 141–145

A (much smaller) explicit counterexample, of n = 906,180,359 was given by R. Sherman Lehman in 1960;{{cite journal |last=Lehman |first=R. S. |date=1960 |title=On Liouville's function |journal=Mathematics of Computation |doi=10.1090/S0025-5718-1960-0120198-5 | doi-access=free |mr=0120198 |jstor=2003890 |volume=14 |issue=72 |pages=311–320}} the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.{{cite journal |last=Tanaka |first=M. |date=1980 |title=A Numerical Investigation on Cumulative Sum of the Liouville Function |journal=Tokyo Journal of Mathematics |doi=10.3836/tjm/1270216093 |mr=0584557 |volume=3 |issue=1 |pages=187–189 |doi-access=free}}

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 Liouville function reaches a maximum value of 829 at n = 906,316,571.

References

References

1. Stein, Sherman K.. (2010). "Mathematics: The Man-Made Universe". Courier Dover Publications.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::