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.


Monday, February 20, 2017

228: So Easy It's Hard

Audio Link

Let’s try an experiment.  Think of a positive whole number.   Any number will do.   Now, follow this simple rule:  if the number is even, divide it by two.   If it’s odd, multiply by 3 and add 1.   Repeat this process until your resulting number is 1.    So, for example, suppose we start with 5.   We multiply by 3 and add 1, to get 16.   Then, following the same rule, we divide by 2 to get 8.  Then we divide by 2 to get 4, and divide by 2 again to get 2, then 1.   If you try this with a few numbers, you’ll see that although you may go up and down a few times, you always seem to end up at 1.  But are you always guaranteed to arrive at 1, no matter what number you started with?   

Believe it or not, this simple question has not been solved.  It’s a famous open problem of mathematics, known as the Collatz Conjecture, or the “3n+1 problem”.     If we define the stopping time as the number of steps to get to 1, this conjecture can be stated as follows:  all positive whole numbers have a finite Collatz stopping time.   Despite being simple enough to explain to an elementary school student, this problem has defied the efforts of mathematicians and hobbyists for nearly a century.  The late quirky mathematician Paul Erdos once offered a $500 bounty for anyone who solves this problem, but this vast fortune has not yet been claimed.

By experimenting manually with a few numbers, you can easily convince yourself that the conjecture is true— it seems like you really do always end up back at 1, no matter how you started.   Yet your path to get there can vary wildly.   If you start with a power of 2, you can see that you’ll dive straight back to 1.   Some well-positioned odd numbers are almost as easy:  for example, if you start with 85, you’ll then jump to 256, which is a power of 2, and head straight back from there to 1.  On the other hand, if you start with the seemingly innocent number of 27, you will find the total stopping time is 111 steps, during with you visit numbers as high as 9232.  The Wikipedia page has some nice graphs showing how the stopping time varies:  its maximum value seems to slightly increase as the starting numbers increase, but there is no simple pattern that can be established to prove the conjecture.    Computers have experimentally shown that the conjecture holds for numbers up to 2^60, but of course that does not prove that it will remain true forever.

This Collatz stopping time function can also be seen as an example of chaos, a case where a very slight change in initial conditions can cause a dramatic difference in the result.   Why is it that starting with 26 will enable you to finish in a mere 10 steps, while increasing to 27 takes 111 steps, and then many higher numbers have far fewer steps?   It’s a good example to keep in mind when someone claims they have made accurate predictions about some iterative physical system using computer models.  Can they make the case that their model is somehow simpler than the Collatz process, of either halving or tripling and incrementing a single number at a time?   If not, what makes them think their modeling is less chaotic than the Collatz problem, or that their initial conditions are so accurate that they have ruled out chaos effects?     

As with many unsolved problems, this problem is also attractive to many slightly self-deluded amateurs, who every few years publish an article or make an online post claiming to have proven it.   One simple way to test any proposed proof is to see if it also applies to very similar problems for which the conjecture is false.  For example, instead of multiplying odd numbers by 3, multiply them by 5 before adding 1, turning the question into the “5n+1 problem”.   In that case, if we start with the number 13, the sequence is 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13.   Since we got back to the number we started with, this means we repeat forever, without ever getting back to 1!   Thus, any attempted proof of the Collatz 3n+1 problem would have to also have some built-in reason for why it doesn’t apply to the 5n+1 version.    Why is the number 3 so special compared to 5?   Well, if I could answer that, I would be riding away in a limo paid for by Erdos’s $500.   

Still, even if you don’t expect to solve it, it is kind of fun to play with example values and look for patterns.   The way that this simple formula can seem to cause numbers to wander away from you, circle around and tease you temptingly, or race straight down to 1, can seem almost lifelike at times.   An intriguing online abstract claims to describe the problem as “an ecological process of competing organisms”, made of 1s in bit strings.  (Sadly, the full paper for that one is hidden behind a paywall, so I wasn’t able to read it.)     But I think my favorite summary of the problem is the one in the XKCD web comic:   “The Collatz Conjecture states that if you pick a number, and if it’s even divide it by two and if it’s odd multiply by three and add one, and you repeat this procedure long enough, eventually your friends will stop calling to see if you want to hang out.”

And this has been your math mutation for today.


Sunday, January 29, 2017

227: Heads In The Clouds

Audio Link

A few days ago I was flipping channels on the TV, and saw a few minutes of one of the horrible movie adaptations of Jonathan Swift’s classic 1726 satirical novel, Gulliver’s Travels.  When you hear that title, you probably think of a man being tied up on the beach and being captured by an army of tiny Liiluputians.   Most adaptations of the novel focus on that nation of tiny people, which actually comprised only the first section of the Travels.   Although mainly a political satire, even that part of the book had an influence on modern mathematics and computer science—  the Lilliputians were fighting a war over which end of an egg to crack first, with the Big Endians vs the Little Endians.   We now use those terms when describing whether the highest or lowest byte comes first in each multi-byte ‘word’ that forms a computer memory.   But that’s not our main topic today.   What I want to talk about is one of Gulliver’s later voyages, which directly satirized the mathematics and science of Swift’s day:    the voyage to Laputa.

Laputa was a city built on a floating island, populated by a highly educated race of men who spent all day contemplating advanced ideas of music, mathematics and science, almost completely disconnected from any practical matters.   These were a group of people who literally had their “heads in the clouds”.   According to at least one website, this metaphor was already in use by the 1600s, so Swift may have had it in mind when designing this city.  In fact, Laputans are always so deep in thought that they must hire an assistant to alert them when they need to interact with the real world.   As Swift described it:  

It seems the minds of these people are so taken up with intense speculations, that they neither can speak, nor attend to the discourses of others, without being roused by some external taction upon the organs of speech and hearing; for which reason, those persons who are able to afford it always keep a flapper … in their family, as one of their domestics; nor ever walk abroad, or make visits, without him.  And the business of this officer is, when two, three, or more persons are in company, gently to strike … the mouth of him who is to speak, and the right ear of him or them to whom the speaker addresses himself.  This flapper is likewise employed diligently to attend his master in his walks, and upon occasion to give him a soft flap on his eyes; because he is always so wrapped up in cogitation, that he is in manifest danger of falling down every precipice, and bouncing his head against every post; and in the streets, of justling others, or being justled himself into the kennel.   

Somehow all this contemplation never translates in practice to real world usefulness.  Gulliver admires the elaborate care which their tailor takes to measure every detail of his body, but the clothes then delivered are ill-fitted.  Their houses are all poorly put together, with walls at odd angles, because their precise geometric instructions are too refined for the uneducated servants who end up having to do the actual building.    They serve their food cut carefully into various geometrical shapes or representing musical instruments, with no relevance towards whether that is an appropriate or useful presentation for actual consumption.   He summarizes the situation with “I have not seen a more clumsy, awkward, and unhandy people, nor so slow and perplexed in their conceptions upon all other subjects, except those of mathematics and music.” 

A question you might now be asking is:  why does Swift seem so hostile to advanced science and mathematics, which by our time have resulted in amazing improvements to human comfort, productivity, and lifespan?   We need to keep in mind that back in the early 1700s, it was not at all obvious that all the effort spent by the elites on pursuing advanced studies of mathematics and science were actually leading anywhere.   One of the few practical abilities the Laputans did have was the power to lower their floating city and crush rebellious townspeople on the ground, perhaps a hint at the worry that new science was too often used to develop instruments of war rather than advance humanity.  Here is one of Swift’s comments on the unfulfilled promises of scientific leaders:  “ All the fruits of the earth shall come to maturity at whatever season we think fit to choose, and increase a hundred fold more than they do at present; with innumerable other happy proposals.  The only inconvenience is, that none of these projects are yet brought to perfection; and in the mean time, the whole country lies miserably waste, the houses in ruins, and the people without food or clothes. “   In fact, these promises were largely fulfilled by the sciences in the 20th century— too bad Swift never lived to meet Norman Borlaug and see the massive agricultural productivity increases of his Green Revolution.

Swift also was particularly sensitive to the suspicious claims that scientific understanding of mathematical laws governing the natural world would somehow enable a corresponding scientific and mathematical reorganization of society to benefit mankind.   He’s actually pretty explicit about this, stepping back from the satire to address the real world directly at one point:  

But what I chiefly admired, and thought altogether unaccountable, was the strong disposition I observed in them towards news and politics, perpetually inquiring into public affairs, giving their judgments in matters of state, and passionately disputing every inch of a party opinion.  I have indeed observed the same disposition among most of the mathematicians I have known in Europe, although I could never discover the least analogy between the two sciences; unless those people suppose, that because the smallest circle has as many degrees as the largest, therefore the regulation and management of the world require no more abilities than the handling and turning of a globe; 

Here I think Swift was on to something, when we consider that the major mass-murdering totalitarian movements of the 20th century all had intellectuals at their core who believed they needed to scientifically re-engineer society.    On the other hand, since I’m actually an engineer who now serves in elected political office, I should probably stop the podcast at this point before getting myself into trouble.   

f you’re a fellow math geek and haven’t read Gulliver’s voyage to Laputa, I think you’ll really enjoy it.   Since it’s so old it’s out of copyright, you can follow a link in the show notes and read it for free at Project Gutenburg.
And this has been your math mutation for today.