Sunday, March 26, 2017

229: When Numbers Change

Audio Link

In the last episode we discussed the Collatz Conjecture, a simple yet unsolved problem in elementary number theory.   During the podcast, I mentioned that it had been checked for specific values up to 10 to the 60th power, and no counterexample has been found.   Now, for common day-to-day purposes, you might say we can take the conjecture as true, since we’re unlikely to deal in real life with any number that large, unless perhaps we are doing advanced work in physics or chemistry.    Most likely I won’t be filling my car with 10 to the 61st gallons of gasoline & needing to rely on its obscure mathematical properties.   But beyond that, you might wonder if it’s possible at all for the conjecture to be false— after all, why would regular numbers start behaving differently once we get above a certain threshold?  We need to be careful though.   In fact, there are various mathematical conjectures that have been shown to be true up to some immensely large bound, but then suddenly fail.   Today we’ll discuss a few examples.   

Actually, if you think about it a bit, it’s not too hard to construct artificial cases of a conjecture that’s true up to some large number, then fails afterwards.   Here’s an easy one:  “All numbers are less than 10 to the 60th power.”   I dare you, try any number less than 10 to the 60th, and you’ll see this theorem seems miraculously true!  But just try a single larger number, and it will fail.     OK, you may consider that one to be cheating, as of course it’s possible to do this by mentioning a specific limit.   But here’s another artificial case that doesn’t mention a specific limit:   For any number N, that number does not represent the ASCII-encoded text of a Math Mutation podcast.   You may recall that modern computers represent any text document as a long series of numbers, which could be mashed together to represent one large number.   If the shortest episode of this podcast has, say, 500 characters in it, with each character represented by a 8 binary digits, then the smallest counterexample is around 2 to the 4000th power.     Try any smaller number, and it will obey the theorem.   We should point out that even if the artificial nature of these two examples makes them unsatisfying, they are still valid as existence proofs, showing that it is possible for a theorem to prove true for a huge range of numbers and then fail.

The world of mathematics, however,  provides no shortage of “real” conjectures, some created by brilliant mathematicians who just happened to interpolate incorrectly on a handful of topics.   Probably the most famous is one by Pierre de Fermat, the creator of Fermat’s Last Theorem.   I’m sure you remember this Theorem, where in the 1600s, Fermat conjectured that there are no whole number solutions to a^n + b^n = c^n for n greater than two,   That one turned out to be true for all possible numbers, as proven by Andrew Wiles in the 1990s.   But Fermat also came up with many other conjectures.   (He actually had a somewhat pretentious habit of writing down his conjectures along with comments that he had a proof, but not writing down the proof; that’s probably a story for another podcast though.)   Anyway, Fermat examined a set of numbers of the form 2(2n) + 1, which came to be known as Fermat numbers.   The first five of these are 3, 5, 17, 257, and 65537, which he noticed are all prime.   So he hypothesized that all Fermat Numbers are prime.  It seemed like a pretty good guess, though due to the rapid exponential growth it was hard to check for too many values.   But within 70 years after Fermat’s death, Leonhard Euler found a factorization for the 5th Fermat number, which is up in the 4-billions range, showing that it was not prime.  This was actually a pretty impressive accomplishment in a pre-computer age.

Fermat got his posthumous revenge though.   One of the longest-standing serious conjectures that has ended up being disproved was an analog of Fermat’s Last Theorem that Euler proposed in 1769, Euler’s sum-of-powers conjecture.   This basically set up a family of equations related to Fermat’s famous theorem, which Euler thought would all be unsolvable with whole numbers.  One example is a5 + b5 + c5 + d5 = e5..    This actually stood for several centuries, until finally in 1966 a brute-force search with modern computer technology enabled L. J. Lander and T.R. Parkin to find a solution:  275 + 845 + 1105 + 1335 = 1445.      Those numbers may not seem that large, but remember that when combining five 3-digit numbers, you have a truly immense number of possibilities, 10 to the 15th power, again virtually unsearchable in a pre-computer era.

Anyway, in the show notes you can find links to various other cases where a conjecture was thought to be true, and held true for millions of examples or beyond— but then in the end, was discovered to be incorrect.     We shouldn’t feel bad about these:  that’s how all math and science advances, by trying to interpolate new truths about the universe from what has been discovered so far.  Sometimes we are right, and sometimes even the best of us are wrong.   So even though we’ve tested the Collatz Conjecture for a massive range of possible values, there still could be a hidden counterexample lurking somewhere in the far reaches of exponential values, waiting to catch us by surprise a few centuries down the road.

And this has been your math mutation for today.