Tracking the Automatic ANT

Frontmatter

chapter 1. Simple Sequences with Puzzling Properties

Abstract

Many mathematicians feel that the main impact of computers on mathematics has been not in solving problems, as one might expect, but rather in posing them. The prime illustration is probably the recent activity in discrete dynamical systems stimulated by the celebrated computer experiments of Mitchell Feigenbaum. Perhaps “explorations” is a better description of this work, for the appropriate analogy is not with physics or biology but with astronomy. The computer is the mathematician’s telescope, which when used intelligently makes it possible to find out what is “out there” in the mathematical universe. (This whole development should be a source of satisfaction to the Platonists, who have been saying all along that, like stars and galaxies, mathematical phenomena are discovered, not invented.)

David Gale

chapter 2. Probability Paradoxes

Abstract

What is a paradox? Perhaps the best-known examples in mathematics are Russell’s paradox and the Banach-Tarski paradox, but these two results are very different. The Banach-Tarski theorem is considered paradoxical because it shows that sets can behave in a way very different from our intuitive notions about them. Russell’s paradox, on the other hand, shows that starting from what seem to be plausible axioms, one can arrive at a contradiction. The proper term for this is not paradox but antinomy, which, according to Webster, is “a contradiction between two apparently equally valid principles or between inferences correctly drawn from such principles,” whereas a paradox is “a statement that is seemingly contradictory or opposed to common sense and yet is perhaps true.”

David Gale

chapter 3. Historic Conjectures: More Sequence Mysteries

Abstract

Among notable recent achievements in mathematics are the resolutions of some celebrated long-standing conjectures: the proof by Deligne of the Weil conjectures; by de Branges of the Bieberbach conjecture; and by Faltings of the Mordell conjecture. On the other hand, the Fermat problem,* the Riemann hypothesis, and the socalled Poincaré conjecture remain unresolved, though for brief periods it was claimed that they too had been settled. In any case, it seems timely to present some scattered facts about the origins of some of these problems. For most of what follows in this section, aside from the next paragraph, I am indebted to Professor M. R. Choudhury of the University of Dhaka, Bangladesh.

David Gale

chapter 4. Privacy-Preserving Protocols

Abstract

One of the exciting mathematical developments of the past decade was the discovery of so-called uncrackable public key codes. These are codes with the characteristic that everyone knows the method of encryption, but the amount of calculation required for an outsider to break the code is considered beyond present computational capabilities. In the best-known example, breaking the code was equivalent to finding the factors of, say, a 100-digit number, which was believed to be computationally infeasible.

David Gale

chapter 5. Surprising Shuffles

Abstract

Imagine (if you can) a countably infinite deck of cards. Each card is marked with a different natural number, and initially the cards are arranged in their natural order with card 1 on the top and placed face down on a (finite) table.

David Gale

chapter 6. Hundreds of New Theorems in a Two-Thousand-Year-Old Subject: Where Will It End?

Abstract

Once again our subject is the interaction of mathematics and computers.

David Gale

chapter 7. Pop Math and Protocols

Abstract

A mathematician in Moscow and another in New York are talking long distance about a joint paper they have written which they have been invited to present at a meeting in Paris. Because both of them would like to go but only one can, they decide that the only fair thing is to leave it to chance. “All right” says the Russian, “I just tossed a coin. Is it heads or tails?” “Wait a minute,” says the American, “that’s not fair.” “What’s the matter?” says the Russian. “Don’t you trust me? All right then, I give you the number 32357650571 0846612139746964423009788488853006293190845009410037062 5655448971039595527235426169795539, and if you tell me correctly whether its largest prime factor is congruent to 1 or to —1 modulo 4, you can give the paper.” After the American makes his guess the Russian reveals the prime factorization, which in this case happens to be 56123699566021020558766279166381074847903158831 451 × 57654165390541998 801236990031588314500658098016489, and the American can verify the multiplication and the primality of the factors.

David Gale

chapter 8. Six Variations on the Variational Method

Abstract

As a graduate student in physics at the University of Michigan many years ago I had the good fortune to take a course in function theory from Norman Steenrod that pretty much changed the course of my life. My experience in that course plus several private conversations convinced me to switch out of physics and into mathematics. I recall one of our sessions particularly, where, in trying to describe what mathematical research was like, Steenrod said that really there were only about a dozen or so ideas in the whole subject, which people just use over and over again, and once you have mastered these you are, so to speak, in business. I wish now I’d had the presence of mind to ask him for his list of the top twelve. In any case, I expect that on anyone’s list, one of the ideas would be the so-called variational method.

David Gale

chapter 9. Tiling a Torus: Cutting a Cake

Abstract

We devote this chapter to some recent results on a pair of fairly well-known problems of recreational mathematics that have been around for quite a while. The first is the problem of tiling surfaces by unequal squares, the second that of devising fair procedures for dividing a cake. The results on tiling are rather definitive, whereas the work on cake-cutting is still in a rather formative stage.

David Gale

chapter 10. The Automatic Ant: Compassless Constructions

Abstract

Most readers of this book are no doubt familiar with John Conway’s famous Game of Life. Life is an example of what have come to be called cellular automata. I will discuss here another such automaton, called the ant, and though it is very easy to describe, its behavior is interesting and somewhat mysterious.

David Gale

chapter 11. Games: Real, Complex, Imaginary

Abstract

The subject of game theory is by now a fairly substantial branch of mathematics, treated in dozens of books, hundreds of research papers, and at least two full-time journals. Game theory comes in many quite different flavors, including economic, political, military, and, of course, recreational; but all of these branches have one thing in common. In all but very rare cases, the games analyzed are not traditional existing games but rather new games, invented not to be played but to be analyzed. There are a few exceptions like the game of Dots and Boxes, which predates game theory. Also very recently Elwyn Berlekamp has been applying some of the most sophisticated ideas of combinatorial game theory to certain positions in the game of go. However, this work has little to do with actually playing go, in the same way that chess problems have little to do with playing chess.

David Gale

chapter 12. Coin Weighing: Square Squaring

Abstract

One type of problem that we all “teethed on” in our mathematical youth was the so-called weighing problem. We learned therein the valuable lesson of “branching” procedures: if this and this happens, then we do that and that, but if it does not happen, then instead we do such and such.

David Gale

chapter 13. The Return of the Ant and the Jeep

Abstract

The industrious ant (see Chapter 10) has some sisters and cousins that are even more interesting. These generalized ants move from cell to cell in an infinite square grid. At any given moment, each cell in the grid is in some particular state. These states will be numbered 0 through (n — 1), where n is the number of allowed states. When an ant passes through a cell that is in state k, the state of the cell changes for k to (k + 1) modulo n, and the ant then leaves the cell, making either a left or a right turn relative to the direction it was traversing when it arrived at the cell. The ant is not free to choose which way it will go (right versus left). It must proceed in accordance with a rule-string of length n that is fixed for all time. The rule-string consists of n bits, numbered 0 through n — 1. When the ant is leaving a cell whose state used to be k (and is now (k + 1) modulo n), it turns right if r_k is 1 and left if r_k is 0, where r_k is the kth bit of the rule-string. This generalization of the ant seems to have been first considered by Greg Turk [1] and, independently, by Bunimovich and Troubetzkoy [2], who were building upon earlier work of E.G.D. Cohen [3].

David Gale

chapter 14. Go

Abstract

Chapter 11 of this book is devoted to certain games, and we remarked that although game theory has become an extensive branch of both pure and applied mathematics, the set of games studied in the mathematical literature, is with very few exceptions, disjoint from the set of games people actually play. A notable exception is the analysis by Paterson and Zwick of the children’s game of Concentration, where the authors actually found the rules for optimal play; that is, they solved the game.

David Gale

chapter 15. More Paradoxes. Knowledge Games

Abstract

To reintroduce the subject of paradoxes (see Chapter 2) I present the following example.

David Gale

chapter 16. Triangles and Computers

Abstract

Chapter 6 took up the subject of computer-aided discoveries in geometry and, in particular, some work of Clark Kimberling on “centers” of triangles, points like the centroid, circumcenter, orthocenter, and so on. Kimberling defined 91 such points and found by numerical explorations that there were (or I should say, appeared to be) an enormous number of collinearities among these points. These empirical results could then be proved, again using computers, but this time using symbolic rather than numerical computation: By expressing the given centers by “trilinear coordinates” as functions of the side lengths, a, b, and c, it became a matter of showing that the appropriate determinant in these symbols vanishes, a task ideally suited to programs like Mathematica or Maple.

David Gale

chapter 17. Packing Tripods

Abstract

This chapter is devoted to an unsolved problem so simple to state that it can be told to the proverbial person in the street. Since it appears to be unrelated to known theorems, everyone, specialist or amateur, has an equal crack at it. The puzzle enthusiast, computer programmer, or mathematician may find it a tempting challenge. Moreover, because it hasn’t been worked on by many people, there is a good chance for a fresh approach.

Sherman K. Stein

chapter 18. Further Travels with My Ant

Abstract

A recurring theme of this book has been computer-generated mysteries. Examples are sequences defined by simple rational recursions whose terms turn out to be integers with interesting but unexplained divisibility properties or geometric configurations that exist although there are no proofs of existence. In most of the examples, the reported mysteries have remained unsolved and in some cases may in fact be, in a suitable sense, unsolvable. It is therefore gratifying to be able to present an elegant solution of a previously described mystery. An especially pleasing feature of this solution is that the breakthrough became possible by drawing the right picture. Once the picture is drawn, it becomes clear what must be proved, after which further study of the picture gives the clue for constructing the proof. It turns out that at one point one needs to use the Jordan curve theorem for a special class of closed curves.

David Gale, Jim Propp, Scott Sutherland, Serge Troubetzkoy

chapter 19. The Shoelace Problem

Abstract

Has this ever happened to you? You ve just finished patiently trying to explain some beautiful result of pure mathematics to a group of nonmathematicians, hoping that you ve conveyed something of the flavor of this pearl of truth and beauty, and then after a pause someone says, “Yes, but what has any of this got to do with everyday life?” After much thought I’ve decided that the correct response is to say “Nothing. That’s what’s so nice about it. After all, everyday life is often a drag, so we do mathematics for the same reason we listen to music or ski down a mountain: to get away from and above and beyond everyday life.”

David Gale

chapter 20. Triangles and Proofs

Abstract

This is our third chapter concerned with the subject of triangles, but with a difference. The earlier chapters were concerned with the impact of computers on triangle geometry, whereas here we will go back to basics, taking a new look at some very classical topics.

David Gale

chapter 21. Polyominoes

Abstract

In 1900, when the great German mathematician David Hilbert, in an address to the International Congress of Mathematicians assembled in Paris, laid out his agenda for twentieth-century mathematics, his “most wanted list” of twenty-three unsolved problems included, as number 18, a question concerning the ways in which n-dimensional Euclidean space (including n = 2 and n = 3) can be “tiled” or “packed” with congruent copies of a single geometric figure. Specifically, he asked:

#1.

“Is there in n-dimensional Euclidean space … only a finite number of different kinds of groups of motions with a [compact] fundamental region?“

 

#2.

“Whether polyhedra also exist that do not appear as fundamental regions of groups of motions, by means of which nevertheless by a suitable juxtaposition of congruent copies a complete filling up of all [Euclidean] space is possible?”

 

David Gale

chapter 22. A Pattern Problem, A Probability Paradox, and A Pretty Proof

Abstract

If S is a finite set of nonnegative integers, we define mexS as the smallest nonnegative integer that is not a member of S. (mex is an abbreviation for minimum-excluded (Berlekamp, Conway, and Guy, Winning Ways).)

David Gale

chapter 23. The Sun, the Moon, and Mathematics

Abstract

I hesitate to pick a fight with Walt Whitman, who’s dead and can’t defend himself, but I have to wonder why he was so turned off by a few proofs and figures. The learn’d astronomer, after all, was just doing his job, trying to find out how things work. I have a feeling, though, that this poem is comforting to many people, who become dismayed, perhaps even becoming “tired and sick,” when confronted by science. To hear Walt tell it, the universe somehow became less “mystical” when Copernicus made his discoveries about the solar system. Well, I’m sorry, Mr. Whitman, but I don’t believe knowing the laws of celestial mechanics need affect a person’s ability to react on an emotional level to the beauty of the night sky. Indeed, if anything, it’s the other way round. That other great poet had it right, it seems to me: Truth is beauty (and beauty truth)—and a good thing it is for all of us, poets and astronomers alike.

David Gale

chapter 24. In Praise of Numberlessness

Abstract

One of the more frustrating things about being a mathematician is that almost no one other than professional scientists has the faintest idea what the subject is about or what it is we do. Ask a person chosen at random what the central concept of mathematics is and the answer will probably be numbers. Now, I don’t know myself what mathematics is about (more on this later), but I’m quite sure that the central concept is not numbers. Still, there is a central concept. It is proof. The examples to follow are intended to illustrate how sometimes the reflex action of trying to use numbers makes proofs more difficult.

David Gale

Backmatter