The Pólya Conjecture

I have finally memorized one simple mathematical statement that is true for pretty much any number you can think of, but is in fact verifyably false, with known counterexamples. The Pólya conjecture is true for any number up to about 900 million, but is false for the next 300,000 or so numbers, and is ultimately false in general.

It is well known that any integer can be represented as a product of one or more prime numbers, and only one such representation exists for each integer. E.g. 21 = 7*3, 999=37*3*3*3, etc. The Pólya conjecture states that for any integer N, at least half of the numbers between 2 and N have odd number of prime factors.

For example, for N=10 there are five integers with odd number of prime factors (2,3,5,7,8) and four integers with even number of prime factors (4,6,9,10). Number 8 has 3 prime factors, because 8=2*2*2.

The smallest counter-example for the conjecture is 906,150,257. This is a very strong philosophical argument against the statements like “we checked this for the first 10,000 numbers, this cannot possibly be false”.

Of course, everyone understands that it is possible to define a function that is true for all numbers up to SOME_BIG_NUMBER and false after that. In fact, it can be as simple as f(n) = n<SOME_BIG_NUMBER. However, we seem to intuitively believe that if the algorithm is simple, does not have a “built-in” explicit threshold or trend, and is true for the fist few thousand numbers, then it must be true for all numbers. If it is true for the first million numbers, this conviction becomes virtually absolute.

Delving too much into infinitely small probabilities and theoretical curiousities is ultimately harmful to one’s well-being, as in real life decisions must be often made quickly and with limited information. Those who ignored it had been eaten by the sabertooth tigers long time ago and did not leave any heirs.

The graph below plots the difference between even-factor numbers and odd-factor numbers for N between 2 and about 10 million. It leaves very little for imagination: even-factor numbers clearly lose.

If the Pólya conjecture were decided in the court of law, I don’t think the pro-conjecture side would have any trouble winning the case after they produce a math professor who would truthfully testify that he ran the calculations for the fisrt 10 million numbers and they are all true. And yet, the court would be wrong, mathematically speaking.

Leave a Reply

Your email address will not be published. Required fields are marked *