## Thursday, August 15, 2024

### The Trouble With Big Numbers

This is part of my series on the scientific method, but it's a bit of a tangent, an interlude if you will, so I'm not giving it a number.  As you will see, that will turn out to be metaphorically significant.  I'm writing this because my muse Publius raised the problem of infinity in comments on earlier installments in this series, and so I thought it would be worth discussing why these are problematic for mathematics but not for science.

(BTW, the title of this post is an allusion to something I wrote five years ago, which itself was an allusion to something I wrote fifteen years ago.  I guess I'm just good at finding trouble.)

There is an old joke that goes something like this: one cave man says to another, "I'll bet you that I can name a bigger number than you."  The second cave man responds, "You're on.  What's your number?"  The first caveman says triumphantly, "Four!"  The second cave man thinks for a while and finally says, "You win."

The joke is not just that the second cave man couldn't count to five, but that it was a silly game to begin with because second player can (it would seem) always win by simply taking the number that the first player names and adding one.  It seems obvious that you should be able to do that no matter what the first player says because otherwise there would have to exist a counter-example, a number to which it is not possible to add 1, and obviously there is no such counterexample, right?

Well, sort of.  There are systems of arithmetic where four actually is the biggest number.  For example, in modulo-5 arithmetic it is possible to add 1 to 4, but the result is zero.  In modulo-5 arithmetic, four actually is the biggest number.

But this is obviously silly, notwithstanding that modular arithmetic really is a legitimate mathematical thing with lots of practical applications.  There is obviously a number greater than four, namely five, the very number we had to deploy to describe the system in which there is no number greater than four.  In fact, to describe a system of modular arithmetic whose biggest number is N we have to use a number one bigger than N.  So this argument seems self-defeating.

There is another way to construct a system of arithmetic with a biggest number, and that is to simply stipulate that there is a biggest number, and that adding one to this number is just not allowed.  Again, this might feel like cheating, but if we are using numbers to count actual physical objects, then there is already a smallest number: zero.  So why could there not be a biggest one?

But this still feels like cheating, because if we can name the number that we want to serve as the biggest number, we can obviously (it would seem) name a number that is one more than that.  So unlike zero, which is kind of a "natural" choice for a smallest number, there is no apparent "natural" choice for a biggest number.  We can try playing tricks like "one more than the biggest number that we can actually name", but that is simply a fun paradox, not an actual number.

So it would appear that logic leaves us no choice but to accept that there is no biggest number, and so we have to somehow deal with apparently inescapable fact that there are an infinite number of numbers.  But that leads to problems of its own.

Imagine that you have three buckets, each of which is capable of holding an infinite number of balls.  Bucket #1 starts out full of balls while the other two are empty.  You now proceed to execute the following procedure:

1.  Take three balls out of bucket 1 and put them in bucket 2.

2.  Take one ball out of bucket 2 and put it in bucket 3.

3.  Repeat until bucket 1 is empty.

That third step should make you a little suspicious.  I stipulated at the outset that bucket 1 starts out with an infinite number of balls, and so if you try to empty it three balls at a time it will never be empty.  But we can fix that by speeding up the process: every time you go through the loop you have to finish it in half the time you took on the previous step.  That will let you perform an infinite number of iterations in a finite amount of time.  Again, you need to suspend disbelief a little to swallow the idea of doing every step twice as fast as the previous one, but you needed to do that when I asked you to imagine a bucket that contained an infinite number of balls in the first place, so having to deploy your imagination is already part of the game.

The puzzle is: when you finish, how many balls are in bucket #2?

The "obvious" answer is that there are an infinite number of balls in bucket #2.  For every ball that gets removed from B2 and put in B3 there are two balls left behind in B2.  So after every step there must be twice as many balls in B2 as B3.  At the end there are an infinite number of balls in B3, so there must be even more -- twice as many in fact -- left behind in B2.

And this is our first hint of trouble, because there is no such thing as "twice infinity".  If you multiply the number of counting numbers by 2 -- or any other finite number -- the result is equal to (the technical term is "can be put in one-to-one correspondence with") the number of counting numbers.

But now imagine that as we take the balls out of B1 and put them in B2 we mark them to keep track of the order in which we processed them.  The first ball gets numbered 1, the second one gets numbered 2, and so on.  Now when we pull them out in step 2, we pull them out in order: ball number 1 gets pulled out first, ball #2 gets pulled next, and so on.  If we do it this way, then bucket 2 will be EMPTY at the end because every ball will have been pulled out at some point along the way!  (In fact, we can modify the procedure to leave any number of balls in bucket 2 that we want.  Details are left as an exercise.)

So clearly things get weird when we start to think about infinity.  But actually, when dealing with large numbers, things get weird long before we get anywhere close to infinity.

There is a famously large number called a googol (the name of the Google search engine is a play on this).  It is a 1 followed by 100 zeros, i.e.:

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Things are already getting a little unwieldy here.  Is that really 100 zeros?  Did you count them?  Are you sure you didn't miss one or count one twice?  To make things a little more manageable this number is generally written using an exponent: 10^100.  But notice that we had to pay a price for shortening a googol this way: we lost the ability to add one!  In order to write down the result of adding 1 to a googol we need to write 99 zeros:

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

One could argue for writing 10^100+1 instead, but that doesn't work in general.  Consider adding 1 to:

3276520609964131756207215092068230686229472208995125701975064355186510619201918716896974491640125539

which is less than a third of a googol.

But a googol is not even close to the biggest number the human mind can conjure up.  Next up is a googolplex, which is a 1 followed by a googol of zeros, i.e. 10^(10^100).  Adding one to that without cheating and just writing 10^(10^100)+1 is completely hopeless.  There are fewer than a googol elementary particles in our universe (about 10^80 in fact) so it is simply not physically possible to write out all of the digits in a googolplex.  Even if we allowed ourselves to re-use material we couldn't do it.  Our universe is only about 13 billion years old, which is less than 10^18 seconds.  The fastest conceivable physical process operates on a scale called the Planck time, which is the time it takes for light to travel the diameter of a proton, about 10^-43 seconds.  A single photon with a cycle time this short would have an energy of about 6.6 gigajoules, a little under two megawatt-hours, the energy equivalent of about one and a half tons of TNT.  So even if we could build a computer that ran this fast it could not process the digits of a googolplex in the life span of the universe.

An obvious pattern emerges here: after 10^100 (a googol) and 10^(10^100) (a googolplex) comes 10^(10^(10^100)), a one followed by a googolplex of zeros.  That number doesn't have a name, and there's not really any point in giving it one because this is clearly a Sisyphean task.  We can keep carrying on forever creating bigger and bigger "power towers": 10^(10^(10^100)), 10^(10^(10^(10^100))) and so on.

What happens if we start to write power towers with large numbers of terms, like 10^10^10^10... repeated, say, 1000 times?  To keep those from getting out of hand we have invent yet another new notation.  Designing such a notation gets deep into the mathematical weeds which I want to steer clear of, so I'm just going to adopt (a minor variant of) something invented by Donald Knuth called up-arrow notation: A↑B means A^(A^(... <== B times.  So 10↑5 means 10^(10^(10^(10^(10^10)))).  10↑10 is already too unwieldy for me to want to type out.  But even at 5 iterations it is already challenging to communicate just how vast this number is.  I can explicitly expand it out one level (10^(10^(10^(10^10000000000)))) but not two -- that would require about ten gigabytes of storage.  Expanding it out to three levels would require more resources than exist in this universe.  Four is right out.

But we are nowhere near done stretching the limits of our imagination.  Up-arrow notation can be iterated: A↑↑B means A↑(A↑(A... <== B times.  A↑↑↑B means A↑↑(A↑↑(A... <== B times, and so on.  And this allows us to arrive -- but just barely -- at one of the crown jewels of big numbers, the famous Graham's number, which uses a number of up-arrows so big that it itself needs to be described using up-arrow notation.

Graham's number is already mind-bogglingly vast, but it's a piker compared to TREE(3).  I'm not even going to try to explain that one.  If you're interested there's a lot of material about it on the web.  And even that is only just getting started.  Everything I've described so far is still computable in principle (though not in practice).  If we had a big enough computer and enough time then we could in principle actually write out all the digits of Graham's number or even TREE(3), or even TREE(TREE(3)) -- these patterns go on and on and on.  But beyond these lie even bigger numbers which are uncomputable even in principle, though it's easy to show that they must exist.  That will have to wait until I get around to discussing the halting problem.  For now you will just have to take my word for it that there are a series of numbers called busy beavers which are provably larger than any number I've described so far, or even any number that can be constructed by any combination of techniques I've described so far.  TREE(TREE(TREE.... iterated Graham's number of times?  Busy beavers are bigger, but every one of them is nonetheless finite, exactly as far away from infinity as zero is.

And it gets even crazier than that.  Let's suspend disbelief and imagine that we can actually "get to infinity" somehow.  We're still not done, not by a long shot.  It turns there are different kinds of infinity.  The smallest one is the number of counting numbers or, equivalently, the number of ways you can arrange a finite set of symbols into finite-length strings.  If you allow your strings to grow infinitely long then the number of such strings is strictly larger than the number of finite-length strings.  And you can keep playing this game forever.  The number of infinite two-dimensional arrays of symbols is strictly larger than the number of one-dimensional infinite strings of symbols, and so on and so one.

But wait, there's more!  All this is just what we get when we treat numbers as measures of quantity.  Remember the balls-and-buckets puzzle above, and how things got really strange when we allowed ourselves to paint numbers on the balls so we could distinguish one ball from another?  It turns out that if we think about adding one as not just an indicator of quantity but of position that we can squeeze different kinds of infinities in between the ones we just constructed above.  If we think of adding one as producing "the number after" rather than just the number that is "one more than" then we can introduce a number that is "the number after all the regular counting numbers".  Mathematicians call that ω (the lower-case Greek letter omega).  Then we can introduce the number after that (ω+1) and the number after that (ω+2) and so on until we get to ω+ω=2ω.  And of course we can go on from there to 2ω+1, 2ω+2... 3ω, 4ω... ω*ω, ω^3, ω^4, ω^ω, ω↑ω, ω↑↑ω and so on until we get to ω with ω up-arrows, which mathematicians call ε0.  And then the whole game begins anew with ε0+1, ε0+ω, ε00...

These kinds of infinities are called transfinite ordinals, and they have two interesting features.  First, the "size" of each of these numbers, that is, the number of numbers between zero and any one of them, is exactly the same as the number of regular counting numbers.  If we think about numbers as referring to position, then each ordinal is "bigger" than the one before, but if we think about them as referring to quantity then each one is exactly the same "size".  And second, the game of inventing new ordinals does not have a regular pattern to it.  It requires creativity.  The bigger you get, the harder it becomes to define what "add one" means.  It gets so hard, that mathematicians who figure out how to do it have the resulting numbers named after them.

The study of big numbers, both finite and infinite, is a deep, deep rabbit hole, one that ultimately leads to Turing machines and the theory of computation, which is the deepest rabbit hole of all.  It's fascinating stuff, and well worth studying for its own sake.  But is any of this relevant for science or is it just an intellectual curiosity?

Until and unless we develop a "theory of everything" that allows us to predict the result of any experiment, we cannot rule out the possibility that this theory will involve very large numbers (by which I mean numbers that require power towers or beyond to represent), and possibly even infinities.  But so far this has not been the case.  There are only two situations in our current best theories where infinities arise, and in both of those cases there is every reason to believe that this is an indication of a problem with the theory and not a reflection of anything real.

Just in case you were wondering, those two situations are singularities inside black holes and self-interactions in quantum mechanics.  In the case of singularities, general relativity predicts their existence while at the same time predicting that they can never be observed because they always lie inside the event horizon of a black hole.  In the case of self-interactions, it just turns out that you can basically just ignore them.  If you simply throw out the infinities when they pop up, everything works out and the predictions made by the theory just turn out to be 100% accurate.  No one knows why, but that's the way it is.

But there is another situation where a kind of infinity pops up which is not so easily dismissed.

Suppose you travel exactly one mile in a straight line, then turn exactly 90 degrees and travel another mile, again in a straight line.  If you then want to return to your starting point by traveling in a straight line, how far would you have to go?

This innocuous-seeming question is the gateway to a whole series of major mathematical and philosophical problems.  You can get the answer by applying Pythagoras's theorem (which, BTW, was almost certainly not discovered by Pythagoras, but that's another story): it's the square root of 2.  The problem arises when you actually try to write this quantity out as a number.  The answer obviously has to be somewhere between 1 and 2, so it's not a whole number.  It also has to be somewhere between 14/10 and 15/10 because (14/10)^2 is 196/100, which is a little less than 2, and (15/10)^2 is 225/100, which is a little more than 2.  We can keep narrowing down this range to smaller and smaller intervals, but we can never find a ratio of two integers whose square is exactly 2.  The square root of 2 is an irrational number.  If we wanted to write it out exactly, we would need an infinite number of digits.  We haven't even gotten past the number 2 and simple multiplication, and yet somehow infinity has managed to rear its ugly head.

I opened this post with a joke, so I'll close with another: a farmer hired a physicist to design a machine to shear sheep.  After a few weeks the physicist submitted his report.  It began, "Assume a spherical sheep."

It's funny because, of course, sheep aren't spherical.  But there is a metaphorical spherical sheep hiding in our problem statement.  It's in the phrase, "exactly one mile"  (and also "exactly 90 degrees").  In order for the mathematical irrationality of the square root of 2 to matter in the physical situation I have described it really is critical to travel exactly one mile.  If you deviate from this in the slightest then the distance back to your starting point can become a rational number, representable numerically with no error in a finite number of symbols.  For example, if either leg of your journey is exactly one part in 696 longer than a mile then the return trip will be exactly 985/696 miles.

In fact, for any number you care to name, no matter how small, I can give you a smaller number such that adding that much distance to one leg of the trip will make the return distance be a rational number.  That means that if you odometer has any error at all, no matter how small, the return distance could be rational.

Of course, "could be" is not the same as "is".  It's possible that the actual underlying physical (or even metaphysical) reality is truly continuous, and actually does require an infinite number of symbols to describe.  But here is the important question: how could you ever possibly know?  What experiment could possibly demonstrate this?  In order to know whether physical reality is truly continuous you would need to somehow obtain an infinite amount of data!  To be able to tell, for example, whether our three-dimensional space is truly continuous, you would need to be able to measure a length to infinite precision.  How would you do that?  Forget the problems with actually designing such a device and how you would get around (say) thermal fluctuations and the Heisenberg uncertainty principle.  I grant you arbitrarily advanced technology and even new physics, and simply ask: what would the output of such a measuring device look like?  It can't be a digital display; those can only output a finite number of possible outputs.  So it would have to be some kind of analog output, like an old-school volt meter.  But that doesn't help either, because to read an analog gauge you still have to look at it, and your eye doesn't have infinite resolution.  And even if your eye had infinite resolution, you would still have to contend with the fact that the needle of the gauge is made of atoms which are subject to thermal fluctuations.  And if you tried to solve that problem by cooling the gauge down to absolute zero, you still ultimately have to contend with the Heisenberg uncertainty principle.  (Yes, I know I granted you new physics, but you still have to be consistent with quantum mechanics.)

The ultimate fact of the matter is that no matter how hard we try, no matter what technology we invent, no matter how many resources we deploy, we will only ever have a finite amount of data, and so we can always account for that data with finite explanations.  We can imagine infinities.  They might even pop up unbidden in our mathematical models.  But when they do, that will almost certainly be an indication that we've done something wrong because we can know for sure that neither infinite quantities nor infinite precision can ever be necessary to explain our observations.  In fact, we can calculate pretty easily the amount of data our universe can possibly contain, and it's a tiny number compared to what the human imagination is capable of conceiving.

Infinities are like wizards and unicorns.  They're fun to think about, but they aren't real.