Let be a positive integer and the number of (not necessarily distinct) prime factors of (with ). Let be the number of positive integers with an odd number of prime factors, and the number of positive integers with an even number of prime factors. Pólya conjectured that

is , where is the Liouville function.

The conjecture was made in 1919, and disproven by Haselgrove (1958) using a method due to Ingham (1942). Lehman (1960) found the first explicit counterexample, , and the smallest counterexample was found by Tanaka (1980). The first for which are , 4, 6, 10, 16, 26, 40, 96, 586, 906150256, ... (Tanaka 1980, Sloane's A028488). It is unknown if changes sign infinitely often (Tanaka 1980).

Haselgrove, C. B. "A Disproof of a Conjecture of Pólya." Mathematika 5, 141-145, 1958.

Ingham, A. E. "On Two Conjectures in the Theory of Numbers." Amer. J. Math. 64, 313-319, 1942.

Lehman, R. S. "On Liouville's Function." Math. Comput. 14, 311-320, 1960.

Sloane, N. J. A. Sequence A028488 in "The On-Line Encyclopedia of Integer Sequences."

Tanaka, M. "A Numerical Investigation on Cumulative Sum of the Liouville Function" [sic]. Tokyo J. Math. 3, 187-189, 1980.

CITE THIS AS:

Weisstein, Eric W. "Pólya Conjecture." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PolyaConjecture.html