Pi-ed to the galaxy

You may have heard that yesterday, March 14th, was 'Pi Day', or possibly 'American Pi Day', since it's in the usual American format that the date: 3/14/15 9.26:53 reads as the first ten digits of the number represented by the Greek letter pi. Usually the representation would be something like 3/14 1.59:26, but this year was of special interest to enthusiasts - and the precise time of the celebration was altered - because it is the only year of the century in which the two-digit year number can be incorporated, increasing the precision of the approximation.

But anyway. All this talk of pi reminds me of something that happened to a couple of friends one lazy Saturday afternoon...

Adam and Doug were sitting in the living room drinking tea when a package arrived at the door. Of course, it didn't arrive directly, but Adam watched through the window as the delivery man approached the door and posted a 'sorry we missed you' card, which is essentially the same thing. After a short sprint down the driveway and a forcibly-polite conversation in which Adam found himself conceding that the notion of 'being in' is fraught at the first hurdle with ill-defined notions of 'being', he returned with a small white box that Doug eyed gleefully as Adam slammed the door shut. It was funny, because he felt pretty 'in' right now.

"It's here! Open it up!" said Doug. Adam did so, producing a small card with a disc in the jacket.

"What is it?" he asked.

"It's the Answer to the Great Question, of Life, the Universe and Everything!" exclaimed Doug. "Quick, let me see!"

"I thought we already settled that?" said Adam, handing over the card. "Isn't it-"

"Yes, yes, that's just how they market it. But this is so much more than that - look!"

Doug showed Adam the card. On the cover was the single Greek letter, pi. On the inside it read:

"CONGRATULATIONS on your purchase of the Answer to the Great Question, of Life, the Universe and Everything - and so much more! Contained in this innocuous little number is the answer to every question you could possibly imagine - and even some you can't! Simply load up the software, which contains an algorithm for calculating pi to whatever degree of accuracy you need. Enter your question and watch in amazement as the answer appears before your very eyes!*

*(Some computation time required).

HOW DOES IT WORK? Pi is perhaps the most famous of many numbers conjectured to be 'NORMAL', which means that its INFINITE decimal expansion contains every imaginable sequence of digits, however long, infinitely many times! THAT MEANS THE ANSWER TO YOUR BURNING QUESTION LIES HIDDEN DEEP WITHIN THE VERY FABRIC OF MATHEMATICS ITSELF! Simply assign a code, such as 'A' = '01', 'B' = '02', 'C' = '03' to all the letters and symbols in your language, then wonder as the SECRETS OF PI REVEAL THEMSELVES TO YOU. Try it now!"

Adam was bemused. "So it's saying we can read pi like some sort of message from the universe?" he asked.

"Exactly!" replied Doug. "And every conceivable answer is contained it in, because SOMEWHERE in there, the correct sequence of digits appears. We just need to pick a code. I suppose we may as well try the one they suggest. So my name, DOUG, would be coded using 04 for D, 15 for O, 21 for U and 07 for G. That's... 04152107. Let's just load up a few digits of pi here..."

Doug had inserted the disc into their supercomputer and pressed some buttons. The initial digits of pi flashed up on the screen:

"3.141592653589793238462643383279502884197169399"

Doug looked excited. "Let's have a read! So the first digits are 3 and 1, 31. Under our code that means... uhh. Hang on. Hm."

"I guess they haven't explained the full picture here," observed Adam. "There are too many two-digit numbers for the letters of the alphabet."

"No no, I'm sure it's fine" stammered Doug, trying to pick apart the card for a missing page. "Let's just-"

"It's ok - how about we just start again once we get to 27? So when we see 26 we get Z, then 27 will be A again, 28 is B and so on. We can keep wrapping round until we run out of numbers. A will be 01, 27, 53 and 79. Once we get to 99 it'll be U, so 00 can be V. I'll draw out a quick table...

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
53	54	55	56	57	58	59	60	61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78
79	80	81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	00

"Okay great," said Doug, nodding. "So we get 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62... what's that? E, U, G, Z, A, F, S, O, W, F, J..."

"Eugzafsowfj?" interjected Adam, eyebrows raised. "Sounds like the 'very fabric of mathematics' has had one too many spins."

"Well, there's going to be some junk, obviously," replied Doug, a little defensively. "After all, EVERY combination of numbers is in pi somewhere!"

"Conjecturally, right?"

"Yes yes, conjecturally. You're right, we'll get all manner of complaints if we don't say that."

"From who?" said Adam, confused, but Doug didn't seem to hear. He continued:

"But you see, it found the word 'SOW' - that's a good start. We just need to search deeper. So what we do now is input our question, and the algorithm will calculate the digits of pi, one by one, until it locates the question in our code. What comes after that will be the answer!"

Doug thought for a second, then said:

"You know what, let's use a completely different code from that one from now on, and don't say it out loud, just in case anyone decides to check what we do for themselves."

He glanced over his shoulder, then back again. Adam was about to say something, but thought better of it.

"We'll start with something simple," continued Doug, beginning to type, "WHEREISMYTOWEL... and it says you have to select an answer length... ok". The supercomputer whirred into action. After a minute, it came back with the words:

"INYOURTRAVELBAG"

"Wait, what?" said a shocked Adam. "How can-"

"I knew it!" exclaimed Doug, rushing to the corner of the room and producing a very sandy towel from an equally sandy suitcase. "I remember now, I was sleeping under it during my last desert stargazing visit. Hm, it's a bit dirty. But you see, it works! The power of pi! Don't you see how big this is? All the knowledge of the universe is at our fingertips - cures for all the diseases of the world, the secret to world peace... lottery numbers!"

"I suppose for that we'd need to encode for some numbers as well as letters," said Adam, still hesitant.

"Try something else!" cried Doug. He was bouncing.

"Ok, let's try... WHATISTHECUREFORTHECOMMONCOLD" said Adam, pressing 'enter'. The computer sprang into action again, noticeably more pained this time. It began to make thumping noises from within, but Doug didn't notice because he was shaking out his towel, muttering something about a mini-raft. Eventually, the answer came back:

"RAISINSBOILEDUNDERAFULLMOONKDQZ"

"Raisins boiled under a full moon, really?" said Doug. "Well, that's useful to know."

"What's that KDQZ at the end there?" asked Adam.

"Oh, just unused answer space, I guess. The computer doesn't understand when to stop reading - that's why you have to tell it. What are you asking it now?"

"I'm typing HOWMANYLEGSDOESASPIDERHAVE."

"Why are you asking it that? We know the answer is-"

"FORTYTWO."

"What?"

"That's the answer it gave - forty two. How about WHATISTHECAPITALOFSPAIN?"

"Wait a minute..."

"Oh - HJKSDMAFT, of course!"

"What's going on?"

Adam sighed and turned to his friend.

"Don't you see, Doug? The digits of pi have all the answers, yes-"

"Conjecturally," Doug reminded him.

"Yes - conjecturally, all the answers are there, but there's also a LOT of complete rubbish! If every string of numbers exists, infinitely often, within the digits of pi, then not only is every answer there, but so is every conceivable WRONG answer, as well as a load of pure gobbledegook. It's the the ultimate internet troll. Frankly it's amazing the code and questions we picked returned answers that made any sense whatsoever the first few times. Someone must have left an infinite improbability drive running somewhere nearby."

Doug typed another query into the computer.

"Yikes," he gasped as the response popped up. "Well, that's just obscene." He turned back to Adam. "So it's completely useless?" he asked, starting to look somewhat dejected.

"Perhaps not. I mean, it's an algorithm for calculating the digits of pi, at the very least. I guess if you wanted to generate a string of random numbers, you might argue that as far as anyone can predict them, pi's digits are random. Of course, they're really completely fixed, but if you don't know what's coming next it's much the same thing in practice."

Doug stood in thought. "I suppose it goes to show," he said, "that having the universe's information at your fingertips is no good if you have no way of making head or tail of it. It's one thing to claim that pi contains all the great works of art under some sophisticated encoding, but that doesn't help us to produce that art ourselves, nor does it detract from the achievements of those who do create it. But you know, now I can't decide whether it's fascinating that pi contains all that information, both true and false..."

"Conjecturally"

"Yes - conjecturally... or whether it's a complete banality! I mean, it's just an abstract notion, at the end of the day, isn't it? We could have constructed a number with the same properties just by taking some source of randomness and converting it into a string of digits. Or are there deterministic methods that don't require randomness? How many numbers even are 'normal' the way pi might be?"

"Who knows," said Adam, and added jokingly: "Let's ask pi."

As he entered the question, the computer shuddered visibly and smoke began to billow from the casing. With what sounded like a sigh of relief, it completed the calculation and spat out the response:

"SEEYOUNEXTWEEK"

Adam and Doug glanced at one another nervously. Adam went to the window and quietly shut the curtains.

Folic-ing with infinity

In the previous post we left Cleo searching for her lost ant, Tony, who is moving at some unknown, but constant, velocity, up or down an infinite pavement. Since we are imagining the pavement extends infinitely in both directions, imagine the pavement slabs are labelled using the positive and negative numbers ... -3, -2, -1, 0, 1, 2, 3 ... . Tony started at some integer position x, and is moving at some integer velocity v slabs per minute (both may be positive, negative or 0). How can Cleo, with the power (via maternal chauffeuring) to examine one point anywhere on the pavement every minute, ever hope to find him?

Two examples of schemes that may not work were given last time. Although Cleo might be lucky, there's no way to be sure she isn't heading in the wrong direction, or just too slowly to catch Tony up. But what if he weren't moving? In other words, what if he has velocity v = 0? Then the second method will eventually catch him, although the first still might not. In this case, Tony is fixed, unmoving, at a point x. Suppose Cleo checks slab 0 first, then 1, then -1, then 2, then -2, and so on. Here is that diagram from last time, with step-numbers labelled:

Whatever x may be, she will eventually reach it in a finite number of steps. She checks 0 on the initial try (call this time t = 0), then 1 at time t = 1, then a positive slab every 2 attempts. So if x is positive, she checks slab x at time t = 2x - 1. Similarly if x is negative, the time is t = -2x + 1. Although Cleo can't be sure at what time she'll find Tony, she knows that it is finite.

What all of the above comes down to is the notion of 'counting' an infinitely-large set. Colloquially, 'infinity' is often used to refer to an unimaginably large quantity, such as the size of the universe, and has a connotation of 'going on forever'. This is similar in spirit to the mathematical meaning, but here infinity has a very precise definition - in fact, several very precise definitions, since there is more than one kind of infinity!

First, think of the set of whole numbers {1, 2, 3, ..., n} with no numbers missed out. Call this set [n]. Unsurprisingly, the size of [n] is n. This is a set with finite size. But this is only a smaller part of the full collection of positive whole numbers {1, 2, 3, ...} going on forever. This collection is referred to as the set of 'natural numbers', denoted N. How big is this set? Since [n] is contained in N, we know N has at least n elements, since that is the size of [n]. But there is no limit to how large we could take n. If we tried to claim the size of N to be some number m, we could immediately disprove that claim by taking n = m + 1. This is what it means to say that N is infinite: for any number we choose, we can find a quantity of elements of N that exceeds that number.

You could say the same of other sets of numbers, such as the negative and positive whole numbers (including 0) - referred to as the integers Z - or just the even integers, 2Z. What is the size of the set of positive square numbers, {1, 4, 9, 16, ...}? It's infinite again, since however big you choose m, the set {1, 4, 9, ..., (m+1)²} contains only square numbers and has m + 1 elements. But what all these sets have in common is that they are 'countably' infinite. This means that they can be written down in a list without missing a single element of the set. For the natural numbers, this list could simply be 1, 2, 3, ... . For the integers, it could be Cleo's 'motionless Tony' algorithm 0, 1, -1, 2, -2, ... . We could explicitly label the step at which each number appears:

1. 0
2. 1
3. -1
4. 2
5. -2
...

This is precisely the meaning of countably infinite: there is what's known as a bijection between Z and the natural numbers: each element of N is coupled with precisely one of Z. In this sense, the two sets are 'the same size'. This seems counter-intuitive! It seems that Z should be 'twice as big' (at least) as N, because it contains every element of N as well as its negative counterpart. Another strange phenomenon is that the order in which you count the same set can determine whether or not you 'hit' all of it: compare the above method of counting Z with simply counting in the ascending order 1, 2, 3, ... . The second version misses all the negative numbers, no matter how far you go.

This is something first-year undergraduates at university have to get used to, which they often do kicking and screaming. The thing is, there's just no sensible meaning to the term 'twice as infinite', because infinity isn't a number, but the concept of a magnitude a number can't possibly exceed. It can be dangerous trying to apply an intuitive notion of what 'size' means in a situation where that idea breaks down, and our definition of infinity doesn't attempt to do that. The vital thing is that our results are consistent under this paradigm, however weird they occasionally seem, and mathematicians define infinite sizes as described above because it's the convenient way to think about maps from one set to another*. If they want to know whether it's possible for a function to take a value in N and spit out a value in Z, the answer is 'yes', because the sets are both countably infinite. And this is useful, because it's precisely the property of Z that Cleo uses to guarantee than she can scan through it without missing a value. Notice that even though Z is infinite, because it is countably infinite, there is no value that cannot eventually be reached, given enough time. Conversely, it's impossible to 'search' the entire set of decimal numbers in such a way, so this set (known as the 'real numbers', R) is called uncountably infinite.

So Cleo has used her understanding of infinite cardinalities to determine that if Tony is motionless, she can find him so long as she persists long enough (and they say the education system is being dumbed down!). Unfortunately, Tony probably is moving. It's no good being able to check every integer exactly once if Tony appears at that slab of pavement before or after Cleo checks it. Is there a way to get around this?

The answer, amazingly, is yes! Remember that Tony has two unknown parameters: his velocity, v, and his initial position x. If she knew what both of these were, Cleo would know exactly where along the pavement Tony is at time t: it's his initial position, plus his velocity times the number of minutes that have passed. So if we call his initial position x(0) = x, and denote by x(t) his position at time t, then

x(t) = x + t*v.

Knowing this, Cleo can 'try out' a pair (x,v) of parameters to see whether they are correct, by keeping track of the passage of time and checking slab x(t) for the current t. So long as she has a way of checking every possible combination of parameters, she will find Tony. One way to do this is to imagine a grid of numbers, with the x parameter along the horizontal axis and the v parameter along the vertical axis. Now starting with t = 0 at coordinate (0,0), Cleo checks the parameters x = 0, v = 0, then moves in a spiral pattern to (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1), (1,2), (0,2), (-1,2), and so on. What she is actually doing is 'counting' the infinite number of points as shown in this two-dimensional grid (numbers indicate the time this coordinate is visited).

The first time you see it, I think it's kind of intriguing that adding a whole new dimension doesn't prevent the new set of points from being counted just like the one-dimensional number line (of course, this would be considered a banality for seasoned mathematicians!). The diagram, however, makes it apparent that every single coordinate will eventually be enveloped by the spiral**. To be clear, the diagram doesn't explicitly indicate spatially where Cleo should search: she is navigating an imaginary parameter space which she then converts into a point on the pavement using the formula for x(t). The result of this method is that Cleo would check the following squares:

(0,0), t = 0: x(0) = 0 + 0*0 = 0
(0,1), t = 1: x(1) = 0 + 1*1 = 1
(-1,1), t = 2: x(2) = -1 + 2*1 = 1
(-1,0), t = 3: x(3) = -1 + 3*0 = -1
(-1,-1), t = 4: x(4) = -1 + 4*(-1) = -5
(0,-1), t = 5: x(5) = 0 + 5*(-1) = -5
(1,-1), t = 6: x(6) = 1 + 6*(-1) = -5
(1,0), t = 7: x(7) = 1 + 7*0 =1
(1,1), t = 8: x(8) = 1 + 8*1 = 9
(1,2), t = 9: x(9) = 1 + 9*2 = 19
(0,2), t = 10: x(10) = 0 + 10*2 = 20
(-1,2), t = 11: x(11) = -1 + 11*2 = 21
...

Notice that Cleo may check the same square many times, even staying put for several consecutive minutes. By following this strategy, she can be sure of finding Tony the moment she picks the correct pair of parameter values. So we're done!

I like this problem for a couple of reasons. Firstly, it is fairly simple to describe, but the answer gets to the heart of some fairly chewy thoughts about the nature of infinity and the unusual way in which it's traversed. Secondly, to solve the problem it's enough to describe the method of checking pairs of parameters and prove that this two-dimensional parameter space can be explored with a diagram like the one above, but this graphically simple answer hides a level of complexity that is revealed only if you work out the exact values of x(t) at each time point. The sequence 0, 1, 1, -1, -5, -5, -5, 1, 9, 19, 20, 21, ... doesn't, at first glance, appear all that predictable, in spite of the simple mechanism behind it. Part of what mathematicians come to love about their field is the hidden complexity behind ideas that can be expressed very simply. Because the answers can behave in ways that cannot be anticipated, the process is a lot like exploring a new and unknown land, created the moment a new concept is imagined (or perhaps it 'existed' all along - ask a mathematical philosopher!). Even the natural numbers, so simply defined, burst almost immediately into a cornucopia of properties, the unpredictable nature of the prime numbers being one example.

So, will Cleo actually find Tony? If she persists indefinitely, the answer is yes, but although the success time is finite, she doesn't know how large it is and would have to live indefinitely to be certain of success! The weird thing about a countable infinity is that every given element can be reached in finite time, but no matter how far you count, there will always be infinitely-many that remain untraversed. If you tried to express the progress you'd made as a percentage, the only sensible answer would be 0%, because to have any other value, such as 0.0001%, would be to suggest that you only had to carry on (for this example) 999,999 times as long as you already had done to reach the end. You won't! Infinity defies any attempt to visualise its magnitude.

Actually, Cleo's patience lasted even less time than her mother's, and after half an hour's trundling up and down the road she gave up and went inside to paint fractals on the walls. Tony had a near miss with a chef from the Insectivoracious restaurant, but escaped with the help of a vegetarian spider and went on to become one of the great forefathers of the insect-arachnid peace movement. If you see him giving a speech on a little podium, try not to step on him.

---

* Sometimes when asked 'why does maths work this way?', the boring answer is that it's a matter of definition, rather than some mysterious, universal truth. A definition might be chosen because it seems to extend our intuition in the most logical way without causing contradictions, or because it is the most useful choice when it comes to answering related questions. You might come up with a different notion of 'infinity' that didn't behave this way, but it would be best to call it something else, since the results you prove using it won't be the same. As I note later in the article, the mystery is what follows once you've laid down your definitions and start to see what you can do with the ideas that spring from them.

** It would also be possible, however, to choose a path that went on forever but didn't cover the entire grid. Imagine going up one from (0,0) to (0,1), then diagonally down to (1,0), then across to (2,0), then diagonally up through (1,1) and (0,2), up to (0,3), and so on, following all the diagonals with positive coordinates. This only covers a quarter of the whole grid. The path (0,0), (1,0), (2,0), always moving horizontally to the right, is a truly pathetic effort!