Ian Stewart Page 12

  Answers on page 311

  The Catalan Conjecture

  Anyone who plays around with numbers soon notices that the consecutive integers 8 and 9 are both perfect powers (higher than the first power, of course). In fact, 8 is 2-cubed and 9 is 3-squared.

  Are there any other positive whole numbers with this property—consecutive or not? (Powers higher than the cube are permitted, and strictly speaking 0 is not positive: it is non-negative. So this rules out 1m - 0n = 1.) In 1844, the Belgian mathematician Eugène Catalan conjectured that the answer is no - that is, the Catalan equation

  xa - yb = 1

  has only the above solutions in positive integers x and y when a and b are integers ≥ 2. In a mathematical publication known as Crelle’s Journal,29 he wrote: ‘Deux nombres entiers consécutifs, autres que 8 et 9, ne peuvent être des puissances exactes; autrement dit: l’équation xm - yn = 1, dans laquelle les inconnues sont entières et positives, n’admet qu’une seule solution.’

  The problem has a long history. The composer Philippe de Vitry (1291-1361) stated that the only powers of 2 and 3 that differ by 1 are (1,2), (2,3), (3,4) and (8,9). Levi ben Gerson (1288-1344) provided a proof that de Vitry was right: 3m ± 1 always has an odd prime factor if m > 2, so it cannot be a power of 2. By 1738, Euler had completely solved the equation x2 - y3 = 1 in whole numbers, proving that the only positive solution is x = 3, y = 2. But Catalan’s conjecture allows higher powers than the cube, so these earlier results were not sufficient to prove it.

  In 1976, Robert Tidjeman proved that Catalan’s equation has only finitely many solutions; indeed, any solution must have x, y < exp exp exp exp 730, where exp x = ex. However, this upper limit on the size is almost inconceivably gigantic - and in particular far too large for a computer search to eliminate all other potential solutions. In 1999, M. Mignotte proved that in any hypothetical solution, a < 7.15×1011 and b < 7.78×1016, but the gap is still too big for a computer to fill. A solution seemed hopeless. But, in 2002, the mathematical world was stunned when the Romanian-born German mathematician Preda Mihailescu proved that Catalan was right, with a clever proof based on cyclotomic numbers - complex nth roots of 1. So the conjecture has now been renamed Mihailescu’s theorem.

  There is a generalisation of the problem, to so-called Gaussian integers, which are complex numbers p + qi, where p and q are ordinary integers and i = . Here, there exist two non-trivial powers that differ not by 1, but by i:

  (78 + 78i)2 - (-23i)3 = i

  As far as I know, the corresponding conjecture - that this or minor variations are the only new cases where two Gaussian integer powers differ by 1, -1, i, or -i - remains open.

  An extensive history of the problem can be found at: www.math.leidenuniv.nl/~jdaems/scriptie/Catalan.pdf

  The Origin of the Square Root Symbol

  The square root symbol

  √

  has a wonderfully arcane look, like something out of an ancient manuscript on alchemy. It’s the sort of symbol wizards would write, and formulas that contain it always look impressive and mysterious. But where did it come from?

  Before 1400, European writers on mathematics generally used the word ‘radix’ for ‘root’ when referring to square roots. By the late medieval period, they abbreviated the word to its initial letter, a capital R with a short stroke through it:

  The Renaissance Italian algebraists Girolamo Cardano, Luca Pacioli, Rafael Bombelli and Tartaglia (Niccolò Fontana) all used this symbol.

  The symbol √ is in fact a distorted letter r. How mundane! It first appeared in print in the first German algebra text, Christoff Rudolff’s Coss of 1525, but it took several centuries to become standard.

  The site

  www.roma.unisa.edu.au/07305/symbols.htm

  discusses the history of many other mathematical symbols.

  Please Bear with Me

  Q: What’s a polar bear?

  A: A Cartesian bear after a change of coordinates.

  The Ham Sandwich Theorem

  I’m not making this up: that’s what it is called. It says that if you make a ham sandwich from two slices of bread and a slice of ham, then it is possible to cut the sandwich along some plane so that each of these three components is divided exactly in half, by volume.

  Start with this . . .

  . . . to get this - easy!

  This is fairly obvious if the bread and the ham form nice square slabs, neatly arranged. It is less obvious if you appreciate that mathematicians are referring to generalised bread and ham, which may take any shape whatsoever. (One immediate consequence is the cheese sandwich theorem, which might otherwise need a separate proof. Generality and power go hand in hand.)

  A mathematician’s ham sandwich.

  There are some technical conditions: in particular, the three pieces must not be so terribly complicated that they don’t have well-defined volumes (see Cabinet, page 163). In compensation, there is no requirement for a ‘piece’ to be connected - all in one lump, so to speak - but if it’s not you only have to divide the overall lump in half, not each separate part of it. Otherwise you’re trying to prove the ham and cheese sandwich theorem, which is false - see below.

  The ham sandwich theorem is actually quite tricky to prove, and it is mostly an exercise in topology. To give you a flavour of the proof, I’ll show you how to deal with the simpler case of two shapes in two dimensions - the Flatland cheese-on-toast theorem.

  Here’s the problem:

  Find a line that splits both cheese (white) and toast (grey) in half, by area.

  Here’s how to prove it can be solved. Pick a direction and find a line pointing that way, which splits the cheese in half. It is not hard to prove that precisely one such line exists.

  Start with a line in some direction (shown by the arrow) that splits the cheese in half.

  Of course, unless you’ve got lucky, this line won’t split the toast in half too, but there will be two parts A and B on opposite sides of the line, with A on the left and B on the right if you look along the arrow. (Here B includes both chunks of the toast on that side. In general, either A or B might be empty - that doesn’t change the proof.) Suppose that, as shown, A has a bigger area than B.

  Now gradually rotate the direction you’re thinking of, and do the same thing for each new direction.

  Gradually rotate the line, always splitting the cheese in half.

  Eventually you will have rotated the direction by 180°. Since only one line splits the cheese in half, this line must coincide with the original one, except that the arrow now points the other way:

  After a 180° rotation, the line has exactly reversed direction, and regions A and B have swapped places.

  Because the arrow points the other way, parts A and B of the toast have changed places. At the start, A was bigger than B, so now B must be bigger than A. (The pieces are the same as they were at the start, only the labels A and B have swapped.) However, the areas of A and B vary continuously as the angle of the line rotates. (This is where the topology comes in.) Since initially area(A) > area(B) and finally area(A) < area(B), there must be some angle in between for which area(A) = area(B). (Why? The difference area(A) - area(B) also varies continuously, starts positive, and ends negative. Somewhere in between it must be zero.) This proves the Flatland cheese-on-toast theorem.

  This type of proof doesn’t work in three dimensions, but the theorem is still true. It seems to have first been proved by Stefan Banach, Hugo Steinhaus, and others in 1938. A version about simultaneously bisecting n pieces in n dimensions was proved by Arthur Stone and John Tukey in 1942.

  Here are two easier puzzles for you, which explain some of the limitations:

  • Show that it is not always possible to bisect three regions of the plane with a single straight line.

  • Show that the ham and cheese sandwich theorem is false: it is not always possible to bisect four regions of space with a single plane.

  Answers on page 311

  More on this theor
em, and an outline of the proof, can be found at:

  en.wikipedia.org/wiki/Ham_sandwich_theorem

  Cricket on Grumpius

  On planet Earth, and in those countries that play the game,30 cricket fans always get very upset when a batsman scores 49 and then gets out, because he has just missed a half-century. But this is a horribly decimalist way of viewing the situation.

  The inhabitants of the distant alien world of Grumpius are a case in point. Oddly enough, when humans first made contact with their civilisation, it turned out that they were passionate about cricket. Astrobiologists speculate that the Grumpians must have picked up our satellite TV programmes during an exploratory trip through the Solar System.

  Out for 49 — congratulations!

  Anyway, whenever a Grumpian batsthing scores what we would write as 49, the crowd goes wild, and the batsthing raises its bat and bobs its tentacles in the Grumpian equivalent of a punched fist. Why?

  Answer on page 312

  The Man Who Loved Only Numbers

  The brilliant Hungarian mathematician Paul Erdős was distinctly eccentric. He never held a formal academic position, and he never owned a house. Instead, he travelled the world, living for short periods with his colleagues and friends. He published more collaborative papers than anyone else, before or since.

  He knew the phone numbers of many mathematicians by heart, and would phone them anywhere in the world, ignoring local time. But he could never remember anyone’s first name—except for Tom Trotter, whom he always addressed as Bill.

  One day, Erdős met a mathematician. ‘Where are you from?’, he enquired.

  ‘Vancouver.’

  ‘Really? Then you must know my friend Elliot Mendelson.’

  There was a pause. ‘I am your friend Elliot Mendelson.’

  Paul Erdős.

  The Missing Piece

  ‘Ooooh! Jigsaws!’ yelled Innumeratus. ‘I love jigsaws!’

  ‘This one is special,’ said Mathophila. ‘There are 17 pieces, forming a square. I’ve laid them out on a square grid, and every corner of every piece lies exactly on the grid.’

  Rearrange the pieces to form the same square . . . with one piece left over.

  ‘Now,’ she continued, ‘I’m going to take away one of the small squares, and your job is to fit the other 16 pieces back together again to make the same big square that we started with.’

  Innumeratus saw no contradiction in that, and half an hour later he proudly showed his answer to Mathophila.

  What was his answer, and how can he form the same square when one piece is missing? [Hint: it can’t really be exactly the same. And maybe that initial ‘square’ isn’t actually square . . . ]

  Answer on page 312

  The Other Coconut

  A mathematician and an engineer are marooned on a desert island, which has two palm trees: one very tall, the other much shorter. Each has one coconut, at the very top.

  The engineer decides to have a try for the more difficult coconut, on top of the tall tree, while they still have the energy to reach it. He clambers up, scraping his legs raw, and eventually returns with the coconut. They smash it open with a rock and eat and drink the contents.

  Three days later, both of them now weak with hunger and thirst, the mathematician volunteers to get the other coconut. He climbs the shorter tree, detaches the coconut, and brings it down. The engineer then watches bemusedly while the mathematician starts climbing the taller tree, groaning and sweating profusely, finally gets to the top, deposits the coconut there, and makes his way back down with even more difficulty. He is completely exhausted.

  The engineer stares at him, then up at the distant coconut, and then back to the mathematician. ‘Whatever possessed you to do that?’

  The mathematician glares back. ‘Isn’t it obvious? I’ve reduced it to a problem that we already know how to solve!’

  What Does Zeno?

  Zeno of Elea was an ancient Greek philosopher who lived around 450 BC, and he is best known for Zeno’s Paradoxes - four thought experiments, each of which aims to prove that motion is impossible. Some of them may not have originated with Zeno, and others may not even have been stated by Zeno - the evidence is debatable - but I’ll list the traditional four, starting with the best known:

  Achilles and the Tortoise

  These two characters agree to have a race, but Achilles can run faster than the tortoise, so he gives the creature a head start. The tortoise argues that Achilles can never catch him, because by the time Achilles has reached the position where the tortoise was, it has moved ahead. And by the time Achilles has reached that position, the tortoise has moved ahead again ... So Achilles has to pass through infinitely many locations before he can catch up, which is impossible.

  Achilles in hot pursuit.

  The Dichotomy

  In order to reach some distant location, you must first reach the halfway mark, and before you do that, you must reach the quarterway mark, and before that ... So you can’t even get started.

  The Arrow

  At any instant of time, a moving arrow is stationary. But if it is always stationary, it can’t move.31

  The Stadium

  This one is more obscure. Aristotle refers to it in his Physics, and says roughly this: ‘Two rows of bodies, each composed of an equal number of bodies of equal size, pass each other on a racecourse, proceeding with equal velocity in opposite directions. One row originally occupies the space between the goal and the middle point of the course; the other that between the middle point and the starting post. The conclusion is that half a given time is equal to double that time.’

  What Zeno had in mind here is not at all clear.

  Set-up for the stadium paradox.

  As a practical matter, we know that motion is possible. While the tortoise is expounding his argument, Achilles shoots past him, oblivious to the impossibility of doing infinitely many things in a finite time. The deeper issue is: what is motion, and how does it happen? This question is about the physical world, whereas Zeno’s paradoxes are about mathematical models of the real world. If his logic were correct, it would dispose of several possible models. Is it correct, though?

  Most mathematicians and school mathematics teachers resolve (that is, explain away) the first two paradoxes by doing a few calculations. For instance, suppose that the tortoise moves at 1 metre per second, while Achilles moves at 10 metres per second. Start with the tortoise 100 metres in front. Tabulate the events that Zeno considered:

  Time Achilles Tortoise

  0 0 100

  10 100 110

  11 110 111

  11.1 111 111.1

  11.11 111.1 111.11

  The list is infinitely long - but why worry about that? Where is Achilles after, say, 12 seconds? He has reached the 120-metre mark. The tortoise is behind, at 112 metres. Indeed, Achilles gets level with the tortoise after exactly 11 seconds, because at that instant, both of them have reached the 111 -metre position.

  As a follow-up, we might add that the infinite sequence

  10, 11, 11.1, 11.11, 11.111, . . .

  converges to 11, meaning that it approaches indefinitely close to that value, and that value alone, if you go far enough along the sequence.

  The dichotomy paradox can be approached in a similar way. Suppose that the arrow has to travel 1 metre and moves at 1 metre per second. Zeno tells us where the arrow is after second, second, second, and so on. At none of these times has it reached its target. But that doesn’t imply that there is no time at which it reaches the target - just that it’s not one of those considered by Zeno. It doesn’t get there after seconds, either, for instance. And it clearly does get there after 1 second.

  And here, too, we can point out that the infinite sequence

  converges to zero, and the corresponding sequence of times

  converges to 1, the instant at which the arrow hits the target.

  Many philosophers are less satisfied with these resolutions than mathematicians, physicist
s and engineers are. They argue that these ‘limit’ calculations do not explain why infinitely many different things can happen in turn. Mathematicians tend to reply that they show how infinitely many different things can happen in turn, so the assumption that they can’t is what’s making everything seem paradoxical. When the arrow travels from the 0-metre mark to the 1-metre mark, it does so in the finite time of 1 second. But although the length of the interval from 0 to 1 is finite, the number of points in it (in the usual ‘real number’ model) is infinite. In such a model, all motion involves passing through infinitely many points32 in a finite time.

  I don’t claim that my discussion knocks the argument on the head, or covers all relevant points of view. It’s just a quick and broad summary of a few of the main issues.