Don’t trust the small numbers

In mathematics, the Pólya conjecture is true for every natural number up to 906,150,256… and then it’s not.

russellstreet, CC BY-SA 2.0, via Wikimedia Commons

I’ve written before about proof in mathematics. Mathematicians love coming up with conjectures (a.k.a. interesting guesses) about how numbers behave. You can set a computer to test many of these conjectures: cycle through numbers, for example, and see if the guess holds true.

Where the number of conditions to be checked is finite, a computer may actually be able to prove a conjecture. The first time a computer successfully proved a conjecture in this way was in 1976 (the four colour theorem). But for many other conjectures, the number of conditions is infinite. A computer can keep testing numbers for as long as it has power and time – but it’ll never get to the end. If it finds a counterexample, it can disprove a conjecture. But if no counterexample is forthcoming, it still cannot be sure that no such counterexample exists. Maybe the computer just hasn’t gotten far enough yet.

Despite this, longer tests breed more certainty. If you check every number up to a billion and the conjecture holds, you’d be inclined to think that it’s probably true. But without a proof, you may still be completely wrong.

Consider the Pólya conjecture. In 1919 a Hungarian mathematician named George Pólya suggested an interesting property of natural numbers. Every natural number has a number of prime factors – prime numbers that multiply together to produce that natural number. The number 12, for example, has three prime factors: 2, 2, and 3 (2 times 2 times 3 equals 12). The number 87 has two prime factors: 3 and 29 (3 times 29 is 87).

Still with me? Some natural numbers have an odd number of prime factors (like 12); some natural numbers have an even number of prime factors (like 87). Pólya suggested that if you picked a natural number and check all the numbers up to that point, more of them would have an odd number of prime factors than an even number. This is the Pólya conjecture.

So, let’s check this conjecture with the first twelve natural numbers (excluding 0):

Natural numberPrime factorsNumber of prime factors
111 (odd)
221 (odd)
331 (odd)
42, 22 (even)
551 (odd)
62, 32 (even)
771 (odd)
82, 2, 23 (odd)
93, 32 (even)
102, 52 (even)
11111 (odd)
122, 2, 33 (odd)

If we check as far as 12, there are eight odds and only four evens. More than half are odd, so the Pólya conjecture holds. If we kept checking, it would continue to be true up to a thousand. And up to a hundred thousand. Up to a million. A hundred million. Things are looking good for the Pólya conjecture!

But here’s the thing: all this testing is not proof. In this case, you cannot trust the small numbers. Because, at exactly 906,150,257, the numbers with an even amount of prime factors finally outnumber the numbers with an odd amount. The conjecture is false. It just takes a long time to get there.

In most fields, checking something up to a hundred billion times is quite enough to feel certain. But in mathematics, the only certainties are absolute certainties. Absent a counterexample or a definitive proof, the conjectures remain just good guesses.

3 Replies to “Don’t trust the small numbers”

  1. It says Polya holds true up to 100 billion. But the number given where it stops being true is only 906 million. Typo?

  2. The pretty readable paper “Fun with very large numbers” https://arxiv.org/abs/1105.3943 has the abstract
    “We give an example of a formula involving the sinc function that holds for every N = 0, 1, 2, …, up to about 10^102832732165, then fails for all larger N. We give another example that begins to fail after about N ~ exp(exp(exp(exp(exp(exp(e)))))). This number is larger than the Skewes numbers.”

Leave a Reply