Ian Stewart
Page 5
All this has mainly historical interest, since it is now known that without assuming the Riemann hypothesis, π(x) is larger than Li(x) for some x < 1.397 × 10316. Which is still pretty big.
In our book The Science of Discworld III: Darwin’s Watch, Terry Pratchett, Jack Cohen and I suggested a simple way to name really big numbers, inspired by the way googol becomes googolplex: If ‘umpty’ is any number,8 then ‘umptyplex’ will mean 10umpty, which is 1 followed by umpty zeros. So 2plex is a hundred, 6plex is a million, 9plex is a billion. A googol is 100plex or 2plexplex, and a googolplex is 100plexplex or 2plexplexplex. Skewes’ number is 34plexplexplex.
We decided to introduce this type of name to talk about some of the big numbers appearing in modern physics without putting everyone off. For instance, there are about 118plex protons in the known universe. The physicist Max Tegmark has argued that the universe repeats itself over and over again (including all possible variations) if you go far enough, and estimates that there should be a perfect copy of you no more than 118plexplex metres away. And string theory, the best known attempt to unify relativity and quantum theory, is bedevilled by the existence of 500plex variants on the theory, making it hard to decide which one, if any, is correct.
As far as big numbers go, this is small beer. In my 1969 PhD thesis, in an esoteric and very abstract branch of algebra, I proved that every Lie algebra with a certain property that depends on an integer n has another, rather more desirable, property9 in which n is replaced by 5plexplexplex . . . plex with n plexes. I strongly suspected that this could be replaced by 2n, if not n + 1, but as far as I know no one has proved or disproved that, and I’ve changed my research subject anyway. This tale makes an important point: the usual reason for finding gigantic numbers in mathematics is that some sort of recursive process has been used in a proof, and this probably leads to a wild overestimate.
In orthodox mathematics, the role played by our ‘plex’ is usually taken over by the exponential function exp x = ex, and 2plexplexplex will look more like exp exp exp 2. However, 10 is replaced by e here, so this statement is a complete lie. However, it’s not hard to complicate it so that it’s true, bearing in mind that e = 100.43 or thereabouts. Theorems about repeated exponentials are often rephrased in terms of repeated logarithms, like log log log x (see page 189 for logarithms). For example, it is known that every positive integer, with finitely many exceptions, is a sum of at most
n log n + n log log n
perfect nth powers - well, ignoring a possible error that is smaller than n. More spectacularly, Carl Pomerance has proved that the number of pairs of amicable numbers (page 110) up to size x is at most
for some constant c.
Several systems for representing big numbers have been worked out, with names like Steinhaus-Moser, Knuth’s up-arrow and Conway’s chained arrow. The topic is much bigger than you might expect, which is only appropriate, and you can find much more about it at
en.wikipedia.org/wiki/Skewes’_number
en.wikipedia.org/wiki/Large_numbers
The Drowning Mathematician
Which (perhaps unfortunately) reminds me:
Q: What sound does a drowning mathematician make?
A: ‘log log log log log log log ...’
Mathematical Pirates
Piracy is probably not the first thing that comes to mind in connection with mathematics. Of course, the peak period for piracy, or its state-sanctioned version, privateering, was also the golden age of the mathematics of navigation. Navigators drew geometric diagrams on charts using compasses and protractors; and they ‘shot the Sun’ with sextants and used mathematical tables to calculate the ship’s latitude. But that’s not the connection I’m after here, which is a curious set of historical links between mathematicians and pirates, centred on one of the all-time greats: Leonhard Euler, a Swiss-born mathematician who worked in Germany and Russia. He lived between 1707 and 1783 and produced more new mathematics than anybody who has ever lived. The connections were discovered by Ed Sandifer, and posted on his wonderful ‘How Euler Did It’ website: www.maa.org/news/howeulerdidit.html
Euler made major advances in mechanics, including extensive applications of the principle of least action, credited to Pierre-Louis Moreau de Maupertuis, an influential French mathematician, writer and philosopher. Maupertuis associated a quantity called ‘action’ with the motion of any mechanical system, and observed that the actual motion of the system minimises the action, compared with all alternative motions. When a stone bounces down a hill, for instance, the total action is less than it would have been if the stone had started by bouncing uphill for a time, or if it had wandered off sideways, or whatever. Maupertuis was President of the Berlin Academy of Sciences during the period when Euler was in Berlin, and knew Euler well. His father, René Moreau, made the family fortune in the 1690s by attacking British ships, on a privateering licence from the King of France, and married into the aristocracy.
Maupertuis wearing Lapp gear on his 1736 expedition to Lapland, which proved that the Earth is slightly flattened at the poles.
Euler wrote widely about ships,10 and in particular analysed their stability, a beautiful application of hydrostatics. His work was not merely theoretical: it had a significant influence on Russian naval shipbuilding. In 1773, he published the Théorie Complette de la Construction et de la Manoeuvre des Vaissaux Mise à la Portée de Ceux qui s’Appliquent à la Navigation. In 1776, Henry Watson translated the book into English as A Complete Theory of the Construction and Properties of Vessels, with Practical Conclusions for the Management of Ships, Made Easy to Navigators. Watson was a prominent and regular contributor to the Ladies’ Diary, which contained many mathematical games and problems and was widely read by men as well as women. He borrowed enough money to build three ships, based on some of Euler’s work on ship design, and applied to the King of England for a privateer’s licence, to operate near the Philippines. When the King declined, Watson used the ships to carry goods instead. Shortly after, he lost £100,000 (the equivalent of about £15-20 million in today’s money) on a project to modernise the Calcutta docks for the East India Company. The Company let the project go bankrupt and then bought it for peanuts. On his way back to England to sue the Company, Watson caught a fever and died.
Sir Kenelm Digby was a courtier and diplomat in the reign of King Charles I of England. His link to Euler runs through Fermat, who sent Digby a geometrical problem in 1658. The letter was lost but Digby sent a copy to John Wallis, which has survived. Euler, who made a systematic effort to read everything Fermat wrote, heard of the problem and solved it. Digby had a colourful background. His father, Sir Everard Digby, was executed in 1606 for involvement in the Gunpowder Plot. He dabbled in alchemy, and was a founder of the Royal Society. In 1627-28 he led a privateering expedition to the Mediterranean. Here he seized Spanish, Flemish and Dutch ships, and attacked some French and Venetian ships anchored near the friendly Turkish port of Iskanderun. He returned to England with two ships filled with plunder. However, he also made life difficult for English merchant shipping, by inviting reprisals.
Fermat’s poser: Draw a rectangle for which AB is √2 times AC, put a semicircle on top, and choose any point P on the semicircle. Construct X and Y as shown. Prove that AY2 + BX2 = AB2.
Sandifer also mentions a very tenuous link, through Catherine the Great, who earlier had employed Euler as Court Mathematician, to John Paul Jones, ‘Father of the American Navy’. Jones was charged with piracy by the Dutch because he allegedly attacked shipping under ‘an unknown flag’, but the charge was dropped when the American flag was registered with the appropriate authorities.
The Hairy Ball Theorem
An important theorem in topology says that you can’t comb a hairy ball smoothly.11 A proof was given in 1912 by Luitzen Brouwer.
A failed attempt to comb a hairy ball smoothly. At the north and south poles, the hairs would stick up, which is not allowed.
Among the consequences of this
theorem is the fact that, at any instant, the horizontal wind speed at some point on the Earth must be zero. Bearing in mind that typical winds are non-zero, such a point will almost always be isolated, and it will often be surrounded by a cyclone. So, at any time, there should be at least one cyclone somewhere in the Earth’s atmosphere, for purely topological reasons.
The theorem also helps to explain why experimental fusion reactors use toroidal magnetic bottles (‘tokamaks’) to contain the superheated plasma. You can comb a hairy torus (or doughnut12) smoothly. There’s more to the physics than that, of course.
How to comb a hairy doughnut smoothly.
Years ago, one of my mathematical colleagues explained this theorem to a friend of his, and unwisely pointed out that it applied to the family dog. The dog was called ‘hairy ball’ from that moment on.
The picture shows a combed sphere with two ‘tufts’ - two places where the hairs don’t lay flat. The theorem says there can’t be no such places, but can there be only one?
Answer on page 287
Cups and Downs
This puzzle starts with a simple trick involving three cups, which is fun in its own right but also suggests some further questions with surprising answers.
There is a time-honoured way to make money in a pub, requiring three cups and one mug. (The mug is human, and should be moderately intoxicated for increased gullibility.) The con-artist places three cups (or glasses) upright on the bar:
He inverts the centre cup
and explains that he will now turn all three of them to the upside-down position in exactly three moves, where each move inverts exactly two cups. They need not be adjacent: any two will do. (Of course, this can be done in one move - invert the two end cups - but the requirement to use three moves is part of the misdirection.)
The three moves are:
Now the con-artist begins to work on the mug. He casually turns the middle cup upright to get
and invites the mug to repeat the trick, with a small bet on the side to make things more interesting.
Strangely, the cups refuse to behave themselves, no matter what moves the mug attempts. What the mug fails to notice is that the initial position has been changed, surreptitiously. And even if he does notice the change, he may not be aware of the devastating consequences. The parity (odd/even) of the set of upright mugs has now changed from even to odd. But every move preserves this parity. The number of upright cups changes by -2, 2 or 0 at each move, so even numbers stay even and odd numbers stay odd. The first starting position has even parity, and so does the required final position. But the second initial position has odd parity. This makes the required final position inaccessible - not just in three moves, but in any number whatsoever.
This disgraceful con-trick (please do not try this at home, or in a bar, or anywhere else - or if you do, keep me out of it) shows that there can be obstacles to cup-inversion, but it also misdirects the mug into looking for a three-move solution when the original problem can actually be solved in one move.
The problem can be generalised, with a slight difference from the pub scenario. The resulting puzzle involves the same principles, but it’s tidier. I’ll ask you two instances of it.
Cups Puzzle 1
Suppose you start with 11 cups, all upside down. The rule is that you must make a series of moves, each of which inverts precisely 4 cups. They do not have to be adjacent. Your objective is to get all 11 cups upright at the same time. Can you do this, and if so, what is the smallest number of moves that does the job?
Cups Puzzle 2
The same question starting with 12 cups, all upside down. Now the rule is that each move must invert precisely 5 cups. Again they do not have to be adjacent. Your have to get all 12 cups upright at the same time. Can you do this, and if so, what is the smallest number of moves required?
Answers on page 287
Secret Codes
Coded messages are as old as writing, but most of the early codes were very easy to break. For instance, the message
QJHT EP OPU IBWF XJOHT
can be decoded as
PIGS DO NOT HAVE WINGS
just by changing each letter into the previous one in the alphabet. If the code shifts the entire alphabet along a number of steps, there are only 25 possibilities to try. Julius Caesar is thought to have used this kind of code, with a shift of 3, in his military campaigns. It has the advantage that encrypting messages (putting them into code) and decrypting them (working out the original ‘plaintext’ from the coded message) are easy. Its main disadvantage is that you don’t have to be very bright to break the code.
You don’t have to keep the alphabet in (cyclic) order, of course; you could shuffle it into some random-looking order, giving a substitution code. Both sender and recipient must know the shuffled order, so they probably have it written down somewhere, which is potentially insecure. Or else they remember a ‘key’ such as DANGER! FLYING PIGS, which reminds them to use the order
DANGERFLYIPSBCHJKMOQTUVWXZ
which starts with the letters of the key, ignoring duplicates, and finishes with all the others in alphabetical order. Or maybe reverse alphabetical order, if lots of letters happen to remain unchanged.
Substitution codes are easy to break if the person trying to break them has access to a reasonable quantity of coded messages, because in any language some letters occur more often than others. By calculating the frequency with which each letter occurs - the fraction of times it appears, relative to the total number of letters - you can make an educated guess at the plaintext, and then correct it by looking for words that almost make sense but don’t quite.
Typical frequencies of letters in written English.
For instance, in most English writing, the commonest letter is E, followed by T, A, O, I, N, and so on. Of course, texts from different sources may have different frequencies, but all we need is a rough guide. Suppose we already know that in the coded messages, the corresponding ‘top six’ letters are Z, B, M, X, Q, L. Our first attack on the code message
UXCY RQ LQB KMFZ AXLCY
is to replace each of the letters ZBMXQL by the corresponding ones in ETAOIN. The result (replacing unknown letters by *s) is
*O** *I NIT *A*E *ON**
which doesn’t look promising until we realise that NIT is unlikely to appear, whereas NOT is quite plausible. So perhaps X and Q are the wrong way round, and ETAION corresponds to ZBMQXL. Now we decode the message as
*I** *O NOT *A*E *IN**
The second word can’t be TO or NO, because T and N have already been used, but it could well be DO. Now we know that letter R encodes D, and so on. If we guess that the twice-used pair CY should be GS, we’re looking at
*IGS DO NOT *A*E *INGS
and the code breaks wide open.
What worked (probably badly) for Julius Caesar was not suitable for secure communications in more recent times. Once semaphore, the telegraph and radio were invented, and messages did not have to be carried by a human courier or a pigeon, secure codes became crucial to military and commercial operations. The subjects of cryptography (putting messages into code) and cryptanalysis (decoding them without initially knowing the code) became much more important. Today, almost all countries have big operations in both.
Clearly, the two are linked: in order to break a code you need a lot of sample messages, and some understanding of what sort of code might be involved. Letter frequencies, for instance, do not help much if it is not a substitution code - and it won’t be. Each procedure for encrypting messages generates specialised methods for trying to break it.
For very high security, the traditional encryption method is the one-time pad. Here, the originator and recipient of the code message both possess a ‘notepad’ listing ‘keys’, which are sequences of random numbers. One such sequence is used for any given message, and after use it is destroyed. The numbers on that page are combined with the letters in the plaintext message according to a simple mathematical rule. For instance, succ
essive numbers in the sequence may indicate how far along the alphabet the corresponding letter is to be displaced. So, for example, if the pad reads
and the plaintext is
PIGS FLY
then the encrypted message would be
UPUO GSO
(P moves along 5 places, I moves 7 places, and so on). I’m ignoring how to treat spaces, and in practice these should be thought of as additional ‘letters’.
The one-time pad was invented in 1917, and it has been proved that any perfectly secure code must use keys that are in some sense equivalent to one-time pad keys. Although one-time pads are secure against any cryptanalysis system, they are not fully secure, because the notepad might be discovered. Originally, the notepad was a physical object - a pad of paper. To reduce the risk of discovery, it was often printed in very small type, and read using a magnifying-glass. For ease of disposal, the pages were made of inflammable material. Today, the ‘notepad’ might be a computer file.
When 2 + 2 = 0
As a warm-up to more modern methods of data encryption, we need to understand a curious type of arithmetic that goes back to Carl Friedrich Gauss. It is called modular arithmetic, and it is widely used in number theory.
Pick some number, say 4, and call it the modulus. Work only with the whole numbers 0, 1, 2, 3 that lie between 0 (included) and the modulus (excluded). To add two such numbers, add them in the usual way, but if the sum is greater than or equal to 4 (the modulus), subtract a multiple of 4 to reduce the sum to the range 0-3. Do the same for multiplication. So, for example,