Enough is Never Enough

Nothing drives a professor nuts like a student who “proves” something by doing a bunch of examples, or an “induction” where they just do the first few and then write “…” or “etc.”

Why does this drive them crazy?  Because no matter how many you do, a counterexample could always be just over the horizon!

Here Be Dragons!

These students usually try to argue that if they’ve done the first 10 or 100 or 100,000 or 100,000,000, then how could anything go wrong after that?

That’s what George Pólya thought.

In 1919 he made the following famous conjecture.  For any natural number we can look at the prime factorization of that number and count the total number of primes in the factorization.  We will call a number EP if it has an even number of primes in its factorization, and OP if it has an odd number of primes in its factorization.  So 12 is OP and 24 is EP.

Polya conjectured that if you look at all the numbers between 1 and any number, n, then the number of EP numbers is always less than the number of OP numbers.   For example, if n=10, then 4,6,9 are EP and 2,3,5,7,8 are all OP.

Pick some numbers for n and check it out yourself.  We’ll wait.

Unless you are very ambitious you probably used numbers less than n = 906,150,256 and Polya’s conjecture worked!

If you are in physics or engineering, then you are ready to declare the conjecture true for all numbers and get with your life.

There’s a slight hitch, though.  The conjecture fails for n = 906,150,257.  And, in fact, it fails for a whole lot of numbers.  For example, for n = 906,316,571 there are 829 more EP numbers than OP numbers!  The first counterexample was found in 1960 (40 years after Polya made his conjecture!) and lots have been found since.

\text{A Billion Examples} \neq \text{Proof}

Advertisements