Large Counterexample

A positive integer is said to be of even type if its factorization into primes has an even number of primes. Otherwise it is said to be of odd type. Examples: 4=2*2 is even type, 18=2*3*3 is odd type. (We say 1 has 0 primes and is therefore of even type.)

Let E(n)= the number of positive integers <= of even type.
Let O(n)= the number of positive integers <= n of odd type.
What can be said about the relative size of E(n) and O(n)? Are there more of one than the other?

Perhaps O(n) >= E(n) for all n>=2? After all, products of primes come "before" products of two primes...

This statement is known as Polya's conjecture, and dates back from 1919. After it was checked for all n <= a million, many people believed it had to be true. But a belief is not a proof... and in fact the conjecture is false!

In 1962, Lehman found a counterexample: at n=906180359, it is the case that O(n)=E(n)-1.

Presentation Suggestions:
Students may be able to come up with the conjecture if you start with some examples. You may wish to make the conjecture more plausible with some other "heuristic" arguments.

The Math Behind the Fact:
This example drives home the point that "obvious" facts, checked for many cases, to not constitute a proof for all integers!

How to Cite this Page:
Su, Francis E., et al. "Large Counterexample." Mudd Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References: H. Stark, An Introduction to Number Theory, MIT Press, 1987. Keywords:    number theory Subjects:    number theory Level:    Medium Fun Fact suggested by:   Lesley Ward Suggestions? Use this form. 4.15 current rating Click to rate this Fun Fact...     *   Awesome! I totally dig it!     *   Fun enough to tell a friend!     *   Mildly interesting     *   Not really noteworthy and see the most popular Facts!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!