Mathematical American (Scientific American Special Online Issue No. 10)

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

M AT H E M AT I C A L A M E RI C A N

ScientificAmerican.com

exclusive online issue no. 10

“Mathematics, rightly viewed, possesses not only truth, but supreme beauty." So wrote British philosopher and logician Bertrand Russell nearly 100 years ago. He was not alone in this sentiment. French mathematician Henri Poincaré declared that "the mathematician does not study pure mathematics because it is useful; he studies it because he delights in it and he delights in it because it is beautiful." Likewise, Einstein described pure mathematics as "the poetry of logical ideas." Indeed, many a scholar has remarked on the elegance of the science. It is in this spirit that we have put together a collection of Scientific American articles about math. In this exclusive online issue, Martin Gardner, longtime editor of the magazine’s Mathematical Games column, reflects on 25 years of fun puzzles and serious discoveries; other scholars explore the concept of infinity, the fate of mathematical proofs in the age of computers, and the thriving of native mathematics during Japan’s period of national seclusion. The anthology also includes articles that trace the long, hard roads to resolving Fermat’s Last Theorem and Zeno’s paradoxes, two problems that for centuries captivated--and tormented--some of the discipline’s most beautiful minds. —The Editors

TABLE OF CONTENTS 2

A Quarter-Century of Recreational Mathematics BY MARTIN GARDNER; SCIENTIFIC AMERICAN, AUGUST 1998 The author of Scientific American's column "Mathematical Games" from 1956 to 1981 recounts 25 years of amusing puzzles and serious discoveries

10

The Death of Proof BY JOHN HORGAN; SCIENTIFIC AMERICAN, OCTOBER 1993 Computers are transforming the way mathematicians discover, prove and communicate ideas, but is there a place for absolute certainty in this brave new world?

16

Resolving Zeno's Paradoxes BY WILLIAM I. MCLAUGHLIN; SCIENTIFIC AMERICAN, NOVEMBER 1994 For millennia, mathematicians and philosophers have tried to refute Zeno's paradoxes, a set of riddles suggesting that motion is inherently impossible. At last, a solution has been found

21

A Brief History of Infinity BY A. W. MOORE; SCIENTIFIC AMERICAN, APRIL 1995 The infinite has always been a slippery concept. Even the commonly accepted mathematical view, developed by Georg Cantor, may not have truly placed infinity on a rigorous foundation

25

Fermat's Last Stand BY SIMON SINGH AND KENNETH A. RIBET; SCIENTIFIC AMERICAN, NOVEMBER 1997 His most notorious theorem baffled the greatest minds for more than three centuries. But after 10 years of work, one mathematician cracked it

29

Japanese Temple Geometry BY TONY ROTHMAN; SCIENTIFIC AMERICAN, MAY 1998 During Japan's period of national seclusion (1639-1854), native mathematics thrived, as evidenced in "sangaku"— wooden tablets engraved with geometry problems hung under the roofs of shrines and temples

1 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DECEMBER 2003

Originally published in August 1998

A Quarter-Century of Recreational Mathematics The author of Scientific American’s column “Mathematical Games” from 1956 to 1981 recounts 25 years of amusing puzzles and serious discoveries by Martin Gardner

“Amusement is one of the fields of applied math.” —William F. White, A Scrapbook of Elementary Mathematics

M

y “Mathematical Games” column began in the December 1956 issue of Scientific American with an article on hexaflexagons. These curious structures, created by folding an ordinary strip of paper into a hexagon and then gluing the ends together, could be turned inside out repeatedly, revealing one or more hidden faces. The structures were invented in 1939 by a group of Princeton University graduate students. Hexaflexagons are fun to play with, but more important, they show the link between recreational puzzles and “serious” mathematics: one of their inventors was Richard Feynman, who went on to become one of the most famous theoretical physicists of the century. At the time I started my column, only a few books on recreational mathemat-

ics were in print. The classic of the genre—Mathematical Recreations and Essays, written by the eminent English mathematician W. W. Rouse Ball in 1892—was available in a version updated by another legendary figure, the Canadian geometer H.S.M. Coxeter. Dover Publications had put out a translation from the French of La Mathématique des Jeux (Mathematical Recreations), by Belgian number theorist Maurice Kraitchik. But aside from a few other puzzle collections, that was about it. Since then, there has been a remarkable explosion of books on the subject, many written by distinguished mathematicians. The authors include Ian Stewart, who now writes Scientific American’s “Mathematical Recreations” column; John H. Conway of Princeton University; Richard K. Guy of the University of Calgary; and Elwyn R. Berlekamp of the University of California at Berkeley. Articles on recreational mathematics also appear with increasing frequency in mathematical periodicals. The quarterly Journal of Recreational Mathematics began publication in 1968. The line between entertaining math

2 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

and serious math is a blurry one. Many professional mathematicians regard their work as a form of play, in the same way professional golfers or basketball stars might. In general, math is considered recreational if it has a playful aspect that can be understood and appreciated by nonmathematicians. Recreational math includes elementary problems with elegant, and at times surprising, solutions. It also encompasses mind-bending paradoxes, ingenious games, bewildering magic tricks and topological curiosities such as Möbius bands and Klein bottles. In fact, almost every branch of mathematics simpler than calculus has areas that can be considered recreational. (Some amusing examples are shown on the following page.) Ticktacktoe in the Classroom

T

he monthly magazine published by the National Council of Teachers of Mathematics, Mathematics Teacher, often carries articles on recreational topics. Most teachers, however, continue to ignore such material. For 40 years I have done my best to convince educaDECEMBER 2003

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Four Puzzles from Martin Gardner 1

ILLUSTRATIONS BY IAN WORPOLE

(The answers are on page 75.)

2

1 3

1 3

?

?

1 3

M

r. Jones, a cardsharp, puts three cards face down on a table. One of the cards is an ace; the other two are face cards. You place a finger on one of the cards, betting that this card is the ace. The probability that you’ve picked the ace is clearly 1/3. Jones now secretly peeks at each card. Because there is only one ace among the three cards, at least one of the cards you didn’t choose must be a face card. Jones turns over this card and shows it to you. What is the probability that your finger is now on the ace?

3

T

he matrix of numbers above is a curious type of magic square. Circle any number in the matrix, then cross out all the numbers in the same column and row. Next, circle any number that has not been crossed out and again cross out the row and column containing that number. Continue in this way until you have circled six numbers. Clearly, each number has been randomly selected. But no matter which numbers you pick, they always add up to the same sum. What is this sum? And, more important, why does this trick always work?

4 1

2

7

3

8

11

17

24

25

33

48

36

42

16

21

28

35

49

15

20

27

41

6

CUT THE DECK 14

19

26

5

10

13

34

40

47

9

12

18

4

29

37

43

22

30

38

23

31

32

RIFFLESHUFFLE

39

44

45

46

50

P

rinted above are the first three verses of Genesis in the King James Bible. Select any of the 10 words in the first verse: “In the beginning God created the heaven and the earth.” Count the number of letters in the chosen word and call this number x. Then go to the word that is x words ahead. (For example, if you picked “in,” go to “beginning.”) Now count the number of letters in this word—call it n—then jump ahead another n words. Continue in this manner until your chain of words enters the third verse of Genesis. On what word does your count end? Is the answer happenstance or part of a divine plan?

A

magician arranges a deck of cards so that the black and red cards alternate. She cuts the deck about in half, making sure that the bottom cards of each half are not the same color. Then she allows you to riffle-shuffle the two halves together, as thoroughly or carelessly as you please. When you’re done, she picks the first two cards from the top of the deck. They are a black card and a red card (not necessarily in that order). The next two are also a black card and a red card. In fact, every succeeding pair of cards will include one of each color. How does she do it? Why doesn’t shuffling the deck produce a random sequence?

3 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

a

b

e 2 1

c

IAN WORPOLE

√3

d LOW-ORDER REP-TILES fit together to make larger replicas of themselves. The isosceles right triangle (a) is a rep-2 figure: two such triangles form a larger triangle with the same shape. A rep-3 triangle (b) has angles of 30, 60 and 90 degrees. Other reptiles include a rep-4 quadrilateral (c) and a rep-4 hexagon (d). The sphinx (e) is the only known rep-4 pentagon.

tors that recreational math should be incorporated into the standard curriculum. It should be regularly introduced as a way to interest young students in the wonders of mathematics. So far, though, movement in this direction has been glacial. I have often told a story from my own high school years that illustrates the dilemma. One day during math study period, after I’d finished my regular assignment, I took out a fresh sheet of paper and tried to solve a problem that had intrigued me: whether the first player in a game of ticktacktoe can always win, given the right strategy. When my teacher saw me scribbling, she snatched the sheet away from me and said, “Mr. Gardner, when you’re in my class I expect you to work on mathematics and nothing else.” The ticktacktoe problem would make a wonderful classroom exercise. It is a superb way to introduce students to combinatorial mathematics, game theory, symmetry and probability. Moreover, the game is part of every student’s experience: Who has not, as a child, played ticktacktoe? Yet I know few mathematics teachers who have included such games in their lessons. According to the 1997 yearbook of the mathematics teachers’ council, the latest trend in math education is called “the new new math” to distinguish it from “the new math,” which flopped so disastrously several decades ago. The newest teaching system involves dividing classes into small groups of students and instructing the groups to solve problems through cooperative reasoning. “Interactive learning,” as it is called, is substituted for lecturing. Although there

are some positive aspects of the new new math, I was struck by the fact that the yearbook had nothing to say about the value of recreational mathematics, which lends itself so well to cooperative problem solving. Let me propose to teachers the following experiment. Ask each group of students to think of any three-digit number—let’s call it ABC. Then ask the students to enter the sequence of digits twice into their calculators, forming the number ABCABC. For example, if the students thought of the number 237, they’d punch in the number 237,237. Tell the students that you have the psychic power to predict that if they divide ABCABC by 13 there will be no remainder. This will prove to be true. Now ask them to divide the result by 11. Again, there will be no remainder. Finally, ask them to divide by 7. Lo and behold, the original number ABC is now in the calculator’s readout. The secret to the trick is simple: ABCABC = ABC ≤ 1,001 = ABC ≤ 7 ≤ 11 ≤ 13. (Like every other integer, 1,001 can be factored into a unique set of prime numbers.) I know of no better introduction to number theory and the properties of primes than asking students to explain why this trick always works. Polyominoes and Penrose Tiles

O

ne of the great joys of writing the Scientific American column over 25 years was getting to know so many authentic mathematicians. I myself am little more than a journalist who loves mathematics and can write about it glibly. I took no math courses in college. My columns grew increasingly sophisticat-

4 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

ed as I learned more, but the key to the column’s popularity was the fascinating material I was able to coax from some of the world’s best mathematicians. Solomon W. Golomb of the University of Southern California was one of the first to supply grist for the column. In the May 1957 issue I introduced his studies of polyominoes, shapes formed by joining identical squares along their edges. The domino—created from two such squares—can take only one shape, but the tromino, tetromino and pentomino can assume a variety of forms: Ls, Ts, squares and so forth. One of Golomb’s early problems was to determine whether a specified set of polyominoes, snugly fitted together, could cover a checkerboard without missing any squares. The study of polyominoes soon evolved into a flourishing branch of recreational mathematics. Arthur C. Clarke, the science-fiction author, confessed that he had become a “pentomino addict” after he started playing with the deceptively simple figures. Golomb also drew my attention to a class of figures he called “reptiles”— identical polygons that fit together to form larger replicas of themselves. One of them is the sphinx, an irregular pentagon whose shape is somewhat similar to that of the ancient Egyptian monument. When four identical sphinxes are joined in the right manner, they form a larger sphinx with the same shape as its components. The pattern of rep-tiles can expand infinitely: they tile the plane by making larger and larger replicas. The late Piet Hein, Denmark’s illustrious inventor and poet, became a good friend through his contributions to “Mathematical Games.” In the July DECEMBER 2003

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DOG

3 1 2

4

PYRAMID

STAIRS

6

CHAIR

7

IAN WORPOLE

5

SOMA PIECES are irregular shapes formed by joining unit cubes at their faces (above). The seven pieces can be arranged in 240 ways to build the 3-by-3-by-3 Soma cube. The pieces can also be assembled to form all but one of the structures pictured at the right. Can you determine which structure is impossible to build? The answer is on page 75.

1957 issue, I wrote about a topological game he invented called Hex, which is played on a diamond-shaped board made of hexagons. Players place their markers on the hexagons and try to be the first to complete an unbroken chain from one side of the board to the other. The game has often been called John because it can be played on the hexagonal tiles of a bathroom floor. Hein also invented the Soma cube, which was the subject of several columns (September 1958, July 1969 and September 1972). The Soma cube consists of seven different polycubes, the threedimensional analogues of polyominoes. They are created by joining identical cubes at their faces. The polycubes can be fitted together to form the Soma cube—in 240 ways, no less—as well as a whole panoply of Soma shapes: the pyramid, the bathtub, the dog and so on. In 1970 the mathematician John Conway—one of the world’s undisputed geniuses—came to see me and asked if I had a board for the ancient Oriental game of go. I did. Conway then demonstrated his now famous simulation game called Life. He placed several counters on the board’s grid, then removed or added new counters according to three simple rules: each counter with two or three neighboring counters is allowed to remain; each counter with one or no neighbors, or four or more neighbors, is removed; and a new counter is added to each empty space adjacent to exactly three counters. By applying these rules repeatedly, an aston-

ishing variety of forms can be created, including some that move across the board like insects. I described Life in the October 1970 column, and it became an instant hit among computer buffs. For many weeks afterward, business firms and research laboratories were almost shut down while Life enthusiasts experimented with Life forms on their computer screens. Conway later collaborated with fellow mathematicians Richard Guy and Elwyn Berlekamp on what I consider the greatest contribution to recreational mathematics in this century, a two-volume work called Winning Ways (1982). One of its hundreds of gems is a twoperson game called Phutball, which can also be played on a go board. The Phutball is positioned at the center of the board, and the players take turns placing counters on the intersections of the grid lines. Players can move the Phutball by jumping it over the counters, which are removed from the board after they have been leapfrogged. The object of the game is to get the Phutball past the opposing side’s goal line by building a chain of counters across the board. What makes the game distinctive is that, unlike checkers, chess, go or Hex, Phutball does not assign different game pieces to each side: the players use the same counters to build their chains. Consequently, any move made by one Phutball player can also be made by his or her opponent. Other mathematicians who contributed ideas for the column include Frank

5 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

STEAMER

CASTLE

SKYSCRAPER BATHTUB

TUNNEL

SOFA

WELL

WALL

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Harary, now at New Mexico State University, who generalized the game of ticktacktoe. In Harary’s version of the game, presented in the April 1979 issue, the goal was not to form a straight line of Xs or Os; instead players tried to be the first to arrange their Xs or Os in a specified polyomino, such as an L or a square. Ronald L. Rivest of the Massachusetts Institute of Technology allowed me to be the first to reveal—in the August 1977 column—the “publickey” cipher system that he co-invented. It was the first of a series of ciphers that revolutionized the field of cryptology. I also had the pleasure of presenting the mathematical art of Maurits C. Escher, which appeared on the cover of the a

BLOCK

April 1961 issue of Scientific American, as well as the nonperiodic tiling discovered by Roger Penrose, the British mathematical physicist famous for his work on relativity and black holes. Penrose tiles are a marvelous example of how a discovery made solely for the fun of it can turn out to have an unexpected practical use. Penrose devised two kinds of shapes, “kites” and “darts,” that cover the plane only in a nonperiodic way: no fundamental part of the pattern repeats itself. I explained the significance of the discovery in the January 1977 issue, which featured a pattern of Penrose tiles on its cover. A few years later a 3-D form of Penrose tiling became the basis for constructing

IN THE GAME OF LIFE, forms evolve by following rules set by mathematician John H. Conway. If four “organisms” are initially arranged in a square block of cells (a), the Life form does not change. Three other initial patterns (b, c and d) evolve into the stable “beehive” form. The fifth pattern (e) evolves into the oscillating “traffic lights” figure, which alternates between vertical and horizontal rows.

b

BEEHIVE

c

BEEHIVE

d

BEEHIVE

a previously unknown type of molecular structure called a quasicrystal. Since then, physicists have written hundreds of research papers on quasicrystals and their unique thermal and vibrational properties. Although Penrose’s idea started as a strictly recreational pursuit, it paved the way for an entirely new branch of solid-state physics. Leonardo’s Flush Toilet

T

he two columns that generated the greatest number of letters were my April Fools’ Day column and the one on Newcomb’s paradox. The hoax column, which appeared in the April 1975 issue, purported to cover great breakthroughs in science and math. The startling discoveries included a refutation of relativity theory and the disclosure that Leonardo da Vinci had invented the flush toilet. The column also announced that the opening chess move of pawn to king’s rook 4 was a certain game winner and that e raised to the power of π ≤ √163 was exactly equal to the integer 262,537,412,640,768,744. To my amazement, thousands of readers failed to recognize the column as a joke. Accompanying the text was a complicated map that I said required five colors to ensure that no two neighboring regions were colored the same. Hundreds of readers sent me copies of the map colored with only four colors, thus upholding the four-color theorem. Many readers said the task had taken days. Newcomb’s paradox is named after physicist William A. Newcomb, who originated the idea, but it was first described in a technical paper by Harvard University philosopher Robert Nozick. The paradox involves two closed boxes, A and B. Box A contains $1,000. Box B contains either nothing or $1 million. You have two choices: take only Box B or take both boxes. Taking both obviously seems to be the better choice, but there is a catch: a superbeing—God, if you like—has the power of knowing in advance how you will choose. If he predicts that out of greed

IAN WORPOLE

e

6 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

φ

72°

36° 36°

36° 1 1

φ

1 φ

36°

36° 36°

72° φ φ =

1 + √5 2

PENROSE TILES can be constructed by dividing a rhombus into a “kite” and a “dart” such that the ratio of their diagonals is phi (φ), the golden ratio (above). Arranging five of the darts around a vertex creates a star. Placing 10 kites around the star and extending the tiling symmetrically generate the infinite star pattern (right). Other tilings around a vertex include the deuce, jack and queen, which can also generate infinite patterns of kites and darts (below right).

DEUCE

JACK

B contains $1 million, you’ll get the million plus another thousand. So how can you lose by choosing both boxes? Each argument seems unassailable. Yet both cannot be the best strategy. Nozick concluded that the paradox, which belongs to a branch of mathematics called decision theory, remains unresolved. My personal opinion is that the paradox proves, by leading to a logical

TRAFFIC LIGHTS

7 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

QUEEN IAN WORPOLE

you will take both boxes, he leaves B empty, and you will get only the $1,000 in A. But if he predicts you will take only Box B, he puts $1 million in it. You have watched this game played many times with others, and in every case when the player chose both boxes, he or she found that B was empty. And every time a player chose only Box B, he or she became a millionaire. How should you choose? The pragmatic argument is that because of the previous games you have witnessed, you can assume that the superbeing does indeed have the power to make accurate predictions. You should therefore take only Box B to guarantee that you will get the $1 million. But wait! The superbeing makes his prediction before you play the game and has no power to alter it. At the moment you make your choice, Box B is either empty, or it contains $1 million. If it is empty, you’ll get nothing if you choose only Box B. But if you choose both boxes, at least you’ll get the $1,000 in A. And if

contradiction, the impossibility of a superbeing’s ability to predict decisions. I wrote about the paradox in the July 1973 column and received so many letters afterward that I packed them into a carton and personally delivered them to Nozick. He analyzed the letters in a guest column in the March 1974 issue. Magic squares have long been a popular part of recreational math. What makes these squares magical is the arrangement of numbers inside them: the numbers in every column, row and diagonal add up to the same sum. The numbers in the magic square are usually required to be distinct and run in consecutive order, starting with one. There exists only one order-3 magic DECEMBER 2003

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

any practical use. Why then are mathematicians trying to find it? Because it might be there.

The Vanishing Area Paradox

C

onsider the figures shown below. Each pattern is made with the same 16 pieces: four large right triangles, four small right triangles, four eight-sided pieces and four small squares. In the pattern on the left, the pieces fit together snugly, but the pattern on the right has a square hole in its center! Where did this extra bit of area come from? And why does it vanish in the pattern on the left?

square, which arranges the digits one through nine in a three-by-three grid. (Variations made by rotating or reflecting the square are considered trivial.) In contrast, there are 880 order-4 magic squares, and the number of arrangements increases rapidly for higher orders. Surprisingly, this is not the case with magic hexagons. In 1963 I received in the mail an order-3 magic hexagon devised by Clifford W. Adams, a retired clerk for the Reading Railroad. I sent the magic hexagon to Charles W. Trigg, a mathematician at Los Angeles City College, who proved that this elegant pattern was the only possible order-3 magic hexagon—and that no magic hexagons of any other size are possible!

E

IAN WORPOLE

The secret to this paradox—which I devised for the “Mathematical Games” column in the May 1961 issue of Scientific American—will be revealed in the Letters to the Editors section of next month’s issue. Impatient readers can find the answer at www.sciam.com on the World Wide Web. —M.G.

The Amazing Dr. Matrix

What if the numbers in a magic square are not required to run in consecutive order? If the only requirement is that the numbers be distinct, a wide variety of order-3 magic squares can be constructed. For example, there is an infinite number of such squares that contain distinct prime numbers. Can an order-3 magic square be made with nine distinct square numbers? Two years ago in an article in Quantum, I offered $100 for such a pattern. So far no one has come forward with a “square of squares”— but no one has proved its impossibility either. If it exists, its numbers would be huge, perhaps beyond the reach of today’s fastest supercomputers. Such a magic square would probably not have

very year or so during my tenure at Scientific American, I would devote a column to an imaginary interview with a numerologist I called Dr. Irving Joshua Matrix (note the “666” provided by the number of letters in his first, middle and last names). The good doctor would expound on the unusual properties of numbers and on bizarre forms of wordplay. Many readers thought Dr. Matrix and his beautiful, half-Japanese daughter, Iva Toshiyori, were real. I recall a letter from a puzzled Japanese reader who told me that Toshiyori was a most peculiar surname in Japan. I had taken it from a map of Tokyo. My informant said that in Japanese the word means “street of old men.” I regret that I never asked Dr. Matrix for his opinion on the preposterous 1997 best-seller The Bible Code, which claims to find predictions of the future in the arrangement of Hebrew letters in the Old Testament. The book employs a cipher system that would have made Dr. Matrix proud. By selectively applying this system to certain blocks of text, inquisitive readers can find hidden predictions not only in the Old Testament but also in the New Testament, the Koran, the Wall Street Journal— and even in the pages of The Bible Code itself. The last time I heard from Dr. Matrix, he was in Hong Kong, investigating the accidental appearance of π in well-known works of fiction. He cited, for example, the following sentence fragment in chapter nine of book two of H. G. Wells’s The War of the Worlds: “For a time I stood regarding...” The letters in the words give π to six digits! SA

The Author

Further Reading

MARTIN GARDNER wrote the “Mathematical Games” column for Scientific American from 1956 to 1981 and continued to contribute columns on an occasional basis for several years afterward. These columns are collected in 15 books, ending with The Last Recreations (Springer-Verlag, 1997). He is also the author of The Annotated Alice, The Whys of a Philosophical Scrivener, The Ambidextrous Universe, Relativity Simply Explained and The Flight of Peter Fromm, the last a novel. His more than 70 other books are about science, mathematics, philosophy, literature and his principal hobby, conjuring.

Recreations in the Theory of Numbers. Albert H. Beiler. Dover Publications, 1964. Mathematics: Problem Solving through Recreational Mathematics. Bonnie Averbach and Orin Chein. W. H. Freeman and Company, 1986. Mathematical Recreations and Essays. 13th edition. W. W. Rouse Ball and H.S.M. Coxeter. Dover Publications, 1987. Penguin Edition of Curious and Interesting Geometry. David Wells. Penguin, 1991. Mazes of the Mind. Clifford Pickover. St. Martin’s Press, 1992.

8 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Answers to the Four Gardner Puzzles 1. Most people guess that the probability has risen from 1/3 to 1/ . After all, only two cards are face down, and one must be 2 the ace. Actually, the probability remains 1/3 . The probability that you didn’t pick the ace remains 2/3 , but Jones has eliminated some of the uncertainty by showing that one of the two unpicked cards is not the ace. So there is a 2/3 probability that the other unpicked card is the ace. If Jones gives you the option to change your bet to that card, you should take it (unless he’s slipping cards up his sleeve, of course).

2 3

1 3

I introduced this problem in my October 1959 column in a slightly different form—instead of three cards, the problem involved three prisoners, one of whom had been pardoned by the governor. In 1990 Marilyn vos Savant, the author of a popular column in Parade magazine, presented still another version of the same problem, involving three doors and a car behind one of them. She gave the correct answer but received thousands of angry letters—many from mathematicians—accusing her of ignorance of probability theory! The fracas generated a front-page story in the New York Times. 2. The sum is 111. The trick always works because the matrix of numbers is nothing more than an old-fashioned addition table (below). The table is generated by two sets of numbers: (3, 1, 5, 2, 4, 0) and (25, 31, 13, 1, 7, 19). Each number in the matrix is the sum of a pair of numbers in the two sets. When you choose the six circled 3 1 5 2 4 0 numbers, you are selecting six pairs that 25 together include all 12 of the generating 31 numbers. So the sum of the circled num13 bers is always equal to the sum of the 12 1 generating numbers. These special magic 7 squares were the sub19 ject of my January 1957 column.

I discussed Kruskal’s principle in my February 1978 column. Mathematician John Allen Paulos applies the principle to word chains in his upcoming book Once upon a Number. 4. For simplicity’s sake, imagine a deck of only 10 cards, with the black and red cards alternating like so: BRBRBRBRBR. Cutting this deck in half will produce two five-card decks: BRBRB and RBRBR. At the start of the shuffle, the bottom card of one deck is black, and the bottom card of the other deck is red. If the red card hits the table first, the bottom cards of both decks will then be black, so the next card to fall will create a blackred pair on the table. And if the black card drops first, the bottom cards of both decks will be red, so the next card to fall will create a red-black pair. After the first two cards drop—no matter which deck they came from—the situation will be the same as it was in the beginning: the bottom cards of the decks will be different colors. The process then repeats, guaranteeing a black and red card in each successive pair, even if some of the cards stick together (below). THOROUGH SHUFFLE

OR

This phenomenon is known as the Gilbreath principle after its discoverer, Norman Gilbreath, a California magician. I first explained it in my column in August 1960 and discussed it again in July 1972. Magicians have invented more than 100 card tricks based on this principle and its generalizations. —M.G.

10 13 15

IAN WORPOLE

12 4

14

16 2

8

5 6

9 3. Each chain of words ends on “God.” This answer may seem providential, but it is actually the result of the Kruskal Count, a mathematical principle first noted by mathematician Martin Kruskal in the 1970s. When the total number of words in a text is significantly greater than the number of letters in the longest word, it is likely that any two arbitrarily started word chains will intersect at a keyword. After that point, of course, the chains become identical. As the text lengthens, the likelihood of intersection increases.

STICKY SHUFFLE

19 7

1 11

3 17

18

MAGIC HEXAGON has a unique property: every straight row of cells adds up to 38.

SKYSCRAPER cannot be built from Soma pieces. (The puzzle is on page 71.)

9 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Originally published in October 1993

THE DEATH OF PROOF by John Horgan, senior writer

Computers are transforming the way mathematicians discover, prove and communicate ideas, but is there a place for absolute certainty in this brave new world?

Legend has it that when Pythagoras and his followers discovered the theorem that bears his name in the sixth century B.C., they slaughtered an ox and feasted in celebration. And well they might. The relation they found between the sides of a right triangle held true not sometimes or most of the time but always—regardless of whether the triangle was a piece of silk or a plot of land or marks on papyrus. It seemed like magic, a gift from the gods. No wonder so many thinkers, from Plato to Kant, came to believe that mathematics offers the purest truths humans are permitted to know. That faith seemed reaffirmed this past June when Andrew J. Wiles of Princeton University revealed during a meeting at the University of Cambridge that he had solved Fermat’s last theorem. This problem, one of the most famous in mathematics, was posed more than 350 years ago, and its roots extend back to Pythagoras himself. Since no oxen were available, Wiles’s listeners showed their appreciation by clapping their hands. But was the proof of Fermat’s last theorem the last gasp of a dying culture? Mathematics, that most tradition-bound of intellectual enterprises, is undergoing profound changes. For millennia, mathematicians have measured progress in terms of what they can demonstrate through proofs—that is, a series of logical steps leading from a set of axioms to an irrefutable conclusion. Now the doubts riddling modern human thought have finally infected mathematics. Mathematicians may at last be forced to accept what many scientists and philosophers already have admitted: their assertions are, at best, only provisionally true, true until proved false. 10 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

This uncertainty stems, in part, from the growing complexity of mathematics. Proofs are often so long and complicated that they are difficult to evaluate. Wiles’s demonstration runs to 200 pages—and experts estimate it could be five times longer if he spelled out all its elements. One observer asserted that only one tenth of 1 percent of the mathematics community was qualified to evaluate the proof. Wiles’s claim was accepted largely on the basis of his reputation and the reputations of those whose work he built on. Mathematicians who had not yet examined the argument in detail nonetheless commented that it “looks beautiful” and “has the ring of truth.” Another catalyst of change is the computer, which is compelling mathematicians to reconsider the very nature of proof and, hence, of truth. In recent years, some proofs have required enormous calculations by computers. No mere human can verify these so-called computer proofs, just other computers. Recently investigators have proposed a computational proof that offers only the probability—not the certainty—of truth, a statement that some mathematicians consider an oxymoron. Still others are generating “video proofs” in the hopes that they will be more persuasive than page on page of formal terminology. At the same time, some mathematicians are challenging the notion that formal proofs should be the supreme standard of truth. Although no one advocates doing away with proofs altogether, some practitioners think the validity of certain propositions may be better established by comparing them with experiments run on computers or with realworld phenomena. “Within the next 50 years I think the importance of proof in mathematics will diminish,” says Keith Devlin of Colby College, who writes a column on computers for Notices of the American Mathematical Society. “You will see many

more people doing mathematics without necessarily doing proofs.” Powerful institutional forces are promulgating these heresies. For several years, the National Science Foundation has been urging mathematicians to become more involved in computer science and other fields with potential applications. Some leading lights, notably Phillip A. Griffiths, director of the Institute for Advanced Study in Princeton, N.J., and Michael Atiyah, who won a Fields Medal (often called the Nobel Prize of mathematics) in 1966 and now heads Cambridge’s Isaac Newton Institute for Mathematical Sciences, have likewise encouraged mathematicians to venture forth from their ivory towers and mingle with the real world. At a time when funds and jobs are scarce, young mathematicians cannot afford to ignore these exhortations. There are pockets of resistance, of course. Some workers are complaining bitterly about the computerization of their field and the growing emphasis on (oh, dirty word) “applications.” One of the most vocal champions of tradition is Steven G. Krantz of Washington University. In speeches and articles, Krantz has urged students to choose mathematics over computer science, which he warns could be a passing fad. Last year, he recalls, a National Science Foundation representative came to his university and announced that the agency could no longer afford to support mathematics that was not “goal-oriented.” “We could stand up and say this is wrong,” Krantz grumbles, “but mathematicians are spineless slobs, and they don’t have a tradition of doing that.” David Mumford of Harvard University, who won a Fields Medal in 1974 for research in pure mathematics and is now studying artificial vision, wrote recently that “despite all the hype, the press, the pressure from funding agencies, et cetera, the pure

mathematical community by and large still regards computers as invaders, despoilers of the sacred ground.” Last year Mumford proposed a course in which instructors would show students how to program a computer to find solutions in advanced calculus. “I was vetoed,” he recalled, “and not on the grounds—which I expected—that the students would complain, but because half of my fellow teachers couldn’t program!” That situation is changing fast, if the University of Minnesota’s Geometry Center is any indication. Founded two years ago, the Geometry Center occupies the fifth floor of a gleaming, steel and glass polyhedron in Minneapolis. It receives $2 million a year from the National Science Foundation, the Department of Energy and the university. The center’s permanent faculty members, most of whom hold positions elsewhere, include some of the most prominent mathematicians in the world. On a recent day there, several young staff members are editing a video demonstrating how a sphere can be mashed, twisted, yanked and finally turned inside out. In a conference room, three computer scientists from major universities are telling a score of high school teachers how to create computer graphics programs to teach mathematics. Other researchers sit at charcoal-colored NeXT terminals, pondering luridly hued pictures of four-dimensional “hypercubes,” whirlpooling fractals and lattices that plunge toward infinity. No paper or pencils are in sight. At one terminal is David Ben-Zvi, a Harpo Marx–haired junior at Princeton who is spending six months here exploring nonlinear dynamics. He dismisses the fears of some mathematicians that computers will lure them away from the methods that have served them so well for so long. “They’re just afraid of change,” he says mildly. The Geometry Center is a hotbed of what

A Splendid Anachronism? Those who consider experimental mathematics and computer proofs to be abominations rather than innovations have a special reason to delight in the conquest of Fermat’s last theorem by Andrew J. Wiles of Princeton University. Wiles’s achievement was a triumph of tradition, running against every current in modern mathematics. Wiles is a staunch believer in mathematics for its own sake. “I certainly wouldn’t want to see mathematics just being a servant to applications, because it’s not even in the interests of the applications themselves,” he says. The problem he solved, first posed more than 350 years ago by the French polymath Pierre de Fermat, is a glorious example of a purely mathematical puzzle. Fermat claimed to have found a proof of the following proposition: for the equation X N + Y N = Z N, there are no integral solutions for any value of N greater than 2. The efforts of mathematicians to find the proof (which Fermat never did disclose) helped to lay the foundation of modern number theory, the study of whole numbers, which has recently become useful in cryptography. Yet Fermat’s last theorem itself “is very unlikely to have any applications,” Wiles says. Although funding agencies have been encouraging mathematicians to collaborate, both with each other and with scientists, Wiles worked in virtual soli-

tude for seven years. He shared his ideas with only a few colleagues toward the end of his quest. Wiles’s proof has essentially the same classical, deductive form that Euclid’s geometric theorems did. It does not involve any computation, and it claims to be absolutely—not probably—true. Nor did Wiles employ computers to represent ideas graphically, to perform calculations or even to composehis paper; a secretarytyped his hand-written notes. He concedes that testing conjectures with computers may be helpful. In the 1970s computer tests suggested that a far-fetched proposal called the Taniyama conjecture might be true. The tests spurred work that laid the foundation for Wiles’s own proof. Nevertheless, Wiles doubts he will take the trouble to learn how to perform computer investigations. “It’s a separate skill,” he explains, “and if you’re investing that much time on a separate skill, it’s quite likely it’s taking you away from your real work on the problem.” He rejects the possibility that there may be a finite number of truths accessible to traditional forms of inquiry. “I disagree vehemently with the idea that good theorems are running out,” he says. “I think we’ve barely scratched the surface.”

11 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

is known as experimental mathematics, in which investigators test their ideas by representing them graphically and doing calculations on computers. Last year some of the center’s faculty helped to found a journal, Experimental Mathematics, that showcases such work. “Experimental methods are not a new thing in mathematics,” observes the journal’s editor, David B. A. Epstein of the University of Warwick in England, noting that Carl Friedrich Gauss and other giants often performed experimental calculations before constructing formal proofs. “What’s new is that it’s respectable.” Epstein acknowledges that not all his co-workers are so accepting. “One of my colleagues said, ‘Your journal should be called the Journal of Unproved Theorems.’ ” Bubbles and Tortellini A mathematician who epitomizes the new style of mathematics is Jean E. Taylor of Rutgers University. “The idea that you don’t use computers is going to be increasingly foreign to the next generation,” she says. For two decades, Taylor has investigated minimal surfaces, which represent the smallest possible area or volume bounded by a curve or surface. Perhaps the most elegant and simple minimal surfaces found in nature are soap bubbles and films. Taylor has always had an experimental bent. Early in her career she tested her handwritten models of minimal surfaces by dunking loops of wire into a sink of soapy water. Now she is more likely to model bubbles with a sophisticated computer graphics program. She has also graduated from soap bubbles to crystals, which conform to somewhat more complicated rules about minimal surfaces. Together with Frederick J. Almgren of Princeton and Robert F. Almgren of the University of Chicago (her husband and stepson, respectively) and Andrew R. Roosen of the National Institute of Standards and Technology, Taylor is trying to mimic the growth of snowflakes and other crystals on a computer. Increasingly, she is collaborating with materials scientists and physicists, swapping mathematical ideas and programming techniques in exchange for clues about how real crystals grow. Another mathematician who has prowled cyberspace in search of novel minimal surfaces is David A. Hoffman of the University of Massachusetts at Amherst. Among his favorite quarry are catenoids and helicoids, which resemble the pasta known as tortellini and were first discovered in the 18th century. “We gain a tremendous amount of intuition by looking at images of these surfaces on computers,” he says. In 1992 Hoffman, Fusheng Wei of Amherst and Hermann Karcher of the University of Bonn speculated on the existence of a new class of helicoids, ones with handles.

They succeeded in representing these helicoids—the first discovered since the 18th century—on a computer and went on to produce a formal proof of their existence. “Had we not been able to see a picture that roughly corresponded to what we believed, we would never have been able to do it,” Hoffman says. The area of experimental mathematics that has received the lion’s share of attention over the past decade is known as nonlinear dynamics or, more popularly, chaos. In general, nonlinear systems are governed by a set of simple rules that, through feedback and related effects, give rise to complicated phenomena. Nonlinear systems were investigated in the precomputer era, but computers allow mathematicians to explore these systems and watch them evolve in ways that Henri Poincaré and other pioneers of this branch of mathematics could not. Cellular automata, which divide a computer screen into a set of cells (equivalent to pixels), provide a particularly dramatic illustration of the principles of nonlinearity. In general, the color, or “state,” of each cell is determined by the state of its neighbors. A change in the state of a single cell triggers a cascade of changes throughout the system. One of the most celebrated of cellular automata was invented by John H. Conway of Princeton in the early 1970s. Conway has proved that his automaton, which he calls “Life,” is “undecidable”: one cannot determine wheth-er its patterns are endlessly variegated or eventually repeat themselves. Scientists have seized on cellular automata as tools for studying the origin and evolution of life. The computer scientist and physicist Edward Fredkin of Boston University has even argued that the entire universe is a cellular automaton. More famous still is the Mandelbrot set, whose image has become an icon for the entire field of chaos since it was popularized in the early 1980s by Benoit B. Mandelbrot of the IBM Thomas J. Watson Research Center. The set stems from a simple equation containing a complex term (based on the square root of a negative number). The equation spits out solutions, which are then iterated, or fed back, into the equation. The mathematics underlying the set had been invented more than 70 years ago by two Frenchmen, Gaston Julia and Pierre Fatou, but computers laid bare their baroque beauty for all to see. When plotted on a computer, the Mandelbrot set coalesces into an image that has been likened to a tumorous heart, a badly burned chicken and a warty snowman. The image is a fractal: its fuzzy borders are infinitely long, and it displays patterns that recur at different scales. Researchers are now studying sets that are similar to the Mandelbrot set but inhabit four dimensions. “The kinds of complica-

12 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

tions you get here are the kinds you get in many different sciences,” says John Milnor of the State University of New York at Stony Brook. Milnor is trying to fathom the properties of the four-dimensional set by examining two-dimensional slices of it generated by a computer. His preliminary findings led off the inaugural issue of Experimental Mathematics last year. Milnor, a 1962 Fields Medalist, says he occasionally performed computer experiments in the days of punch cards, but “it was a miserable process. It has become much easier.” The popularity of graphics-oriented mathematics has provoked a backlash. Krantz of Washington University charged four years ago in the Mathematical Intelligencer that “in some circles, it is easier to obtain funding to buy hardware to generate pictures of fractals than to obtain funding to study algebraic geometry.” A broader warning about “speculative” mathematics was voiced this past July in the Bulletin of the American Mathematical Society by Arthur Jaffe of Harvard and Frank S. Quinn of the Virginia Polytechnic Institute. They suggested that computer experiments and correspondence with natural phenomena are no substitute for proofs in establishing truth. “Groups and individuals within the mathematics community have from time to time tried being less compulsive about details of arguments,” Jaffe and Quinn wrote. “The results have been mixed, and they have occasionally been disastrous.” Most mathematicians exploiting computer graphics and other experimental techniques agree that seeing should not be believing and that proofs are still needed to verify the conjectures they arrive at through computation. “I think mathematicians were contemplating their navels for too long, but that doesn’t mean I think proofs are irrelevant,” Taylor says. Hoffman offers an even stronger defense of traditional proofs. “Proofs are the only laboratory instrument mathematicians have,” he remarks, “and they are in danger of being thrown out.” Although computer graphics are “unbelievably wonderful,” he adds, “in the 1960s drugs were unbelievably wonderful, and some people didn’t survive.” Indeed, veteran computer enthusiasts know better than most that computational experiments—whether involving graphics or numerical calculations—can be deceiving. One cautionary tale involves the Riemann hypothesis, a famous prediction about the patterns displayed by prime numbers as they march toward infinity. First posed more than 100 years ago by Bernhard Riemann, the hypothesis is considered to be one of the most important unsolved problems in mathematics. A contemporary of Riemann’s, Franz Mertens, proposed a related conjecture involving positive whole numbers; if true, the conjecture would have provided strong evi-

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

dence that the Riemann hypothesis was also true. By the early 1980s computers had shown that Mertens’s proposal did indeed hold for at least the first 10 billion integers. In 1984, however, more extensive com-putations revealed that eventually—at numbers 70 as high as 10 (10 )—the pattern predicted by Mertens vanishes. One potential drawback of computers is that all their calculations are based on the manipulation of discrete, whole numbers— in fact, ones and zeros. Computers can only approximate real numbers, such as pi or the square root of two. Someone knowledgeable about the rounding-off functions of a simple pocket calculator can easily induce it to generate incorrect answers to calculations. More sophisticated programs can make more complicated and elusive errors. In 1991 David R. Stoutemyer, a software specialist at the University of Hawaii, presented 18 experiments in algebra that gave wrong answers when performed with standard mathematics software. Stephen Smale of the University of California at Berkeley, a 1966 Fields Medalist, has sought to place mathematical computation on a more secure foundation—or at least to point out the size and location of the cracks running through the foundation. Together with Lenore Blum of the Mathematical Sciences Research Institute at Berkeley and Michael Shub of IBM, he has created a theoretical model of a computer that can

HELICOID WITH A HOLE was discovered last year by David A. Hoffman of the University of Massachusetts at Amherst and his colleagues, with the help of computer graphics.

process real numbers rather than just integers. Blum and Smale recently concluded that the Mandelbrot set is, in a technical sense, uncomputable. That is, one cannot determine with certainty whether any given point on the complex plane resides within or outside the set’s hirsute border. These results suggest that “you have to be careful” in extrapolating from the results of computer experiments, Smale says. These concerns are dismissed by Stephen Wolfram, a mathematical physicist at the University of Illinois. Wolfram is the creator of Mathematica, which has become the leading mathematics software since first being marketed five years ago. He acknowledges that “there are indeed pitfalls in experimental mathematics. As in all other kinds of experiments, you can do them wrong.” But he emphasizes that computational experiments, intelligently performed and analyzed, can yield more results than the old-fashioned conjecture-proof method. “In every other field of science there are a lot more experimentalists than theorists,” Wolfram says. “I suspect that will increasingly be the case with mathematics.” “The obsession with proof,” Wolfram declares, has kept mathematicians from discovering the vast new realms of phenomena accessible to computers. Even the most intrepid mathematical experimentalists are for the most part “not going far enough,” he says. “They’re taking existing questions in mathematics and investigating those. They are adding a few little curlicues to the top of a gigantic structure.” Mathematicians may take this view with a grain of salt. Although he shares Wolfram’s fascination with cellular automata, Conway contends that Wolfram’s career—as well as his contempt for proofs—shows he is not a real mathematician. “Pure mathematicians usually don’t found companies and deal with the world in an aggressive way,” Life’s creator says. “We sit in our ivory towers and think about things.” Purists may have a harder time ignoring William P. Thurston, who is also an enthusiastic booster of experimental mathematics and of computers in mathematics. Thurston, who heads the Mathematical Sciences Research Institute at Berkeley and is a co-director of the Geometry Center (with Albert Marden of the University of Minnesota), has impeccable credentials. In the mid-1970s he pointed out a deep potential connection between two separate branches of mathematics—topology and geometry. Thurston won a Fields Medal for this work in 1982. Thurston emphasizes that he believes mathematical truths are discovered and not invented. But on the subject of proofs, he sounds less like a disciple of Plato than of Thomas S. Kuhn, the philosopher who argued in his 1962 book, The Structure of Sci-

13 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

entific Revolutions, that scientific theories are accepted for social reasons rather than because they are in any objective sense “true.” “That mathematics reduces in principle to formal proofs is a shaky idea” peculiar to this century, Thurston asserts. “In practice, mathematicians prove theorems in a social context,” he says. “It is a socially conditioned body of knowledge and techniques.” The logician Kurt Gödel demonstrated more than 60 years ago through his incompleteness theorem that “it is impossible to codify mathematics,” Thurston notes. Any set of axioms yields statements that are selfevidently true but cannot be demonstrated with those axioms. Bertrand Russell pointed out even earlier that set theory, which is the basis of much of mathematics, is rife with logical contradictions related to the problem of self-reference. (The self-contradicting statement “This sentence is false” illustrates the problem.) “Set theory is based on polite lies, things we agree on even though we know they’re not true,” Thurston says. “In some ways, the foundation of mathematics has an air of unreality.” Thurston thinks highly formal proofs are more likely to be flawed than those appealing to a more intuitive level of understanding. He is particularly enamored of the ability of computer graphics to communicate abstract mathematical concepts to others both within and outside the professional community. Two years ago, at his urging, the Geometry Center produced a computer-generated “video proof,” called Not Knot, that dramatizes a ground-breaking conjecture he proved a decade ago [see illustration on pages ?? and ??]. Thurston mentions proudly that the rock band the Grateful Dead has shown the Not Knot video at its concerts. Whether Deadheads grok the substance of the video—which concerns how mathematical objects called three-manifolds behave in a non-Euclidean “hyperbolic” space—is another matter. Thurston concedes that the video is difficult for nonmathematicians, and even some professionals, to fathom, but he is undaunted. The Geometry Center is now producing a video of yet another of his theorems, which demonstrates how a sphere can be turned inside out. Last fall, moreover, Thurston organized a workshop at which participants discussed how virtual reality and other advanced technologies could be adapted for mathematical visualization. Paradoxically, computers have catalyzed a countertrend in which truth is obtained at the expense of comprehensibility. In 1976 Kenneth Appel and Wolfgang Haken of the University of Illinois claimed they had proved the four-color conjecture, which stated that four hues are sufficient to construct even an infinitely broad map so that no identically colored countries share a border. In some respects, the proof of Appel and Haken was

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

conventional—that is, it consisted of a series of logical, traceable steps proceeding to a conclusion. The conclusion was that the conjecture could be reduced to a prediction about the behavior of some 2,000 different maps. Since checking this prediction by hand would be prohibitively time-consuming, Appel and Haken programmed a computer to do the job for them. Some 1,000 hours of computing time later, the machine concluded that the 2,000 maps behave as expected: the four-color conjecture was true. The Party Problem Other computer-assisted proofs have followed. Just this year, a proof of the so-called party problem was announced by Stanislaw P. Radziszowski of the Rochester Institute of Technology and Brendan D. McKay of the Australian National University in Canberra. The problem, which derives from work in set theory by the British mathematician Frank P. Ramsey in the 1920s, can be phrased as a question about relationships between people at a party. What is the minimum number of guests that must be invited to guarantee that at least X people are all mutual acquaintances or at least Y are mutual strangers? This number is known as a Ramsey number. Previous proofs had established that 18 guests are required to ensure that there are either four mutual acquaintances or four strangers. In their proof, Radziszowski and McKay showed that the Ramsey number for four friends or five strangers is 25. Socialites might think twice about trying to calculate the Ramsey number for greater X’s and Y’s. Radziszowski and McKay estimate that their proof consumed the equivalent of 11 years of computation by a standard desktop ma-

chine. That may be a record, Radziszowski says, for a problem in pure mathematics. The value of this work has been debated in an unlikely forum—the newspaper column of advice-dispenser Ann Landers. In June a correspondent complained to Landers that resources spent on the party problem should have been used to help “starving children in war-torn countries around the world.” Some mathematicians raise another objection to computer-assisted proofs. “I don’t believe in a proof done by a computer, says Pierre Deligne of the Institute for Advanced Study, an algebraic geometer and 1978 Fields Medalist. “In a way, I am very egocentric. I believe in a proof if I understand it, if it’s clear.” While recognizing that humans can make mistakes, he adds: “A computer will also make mistakes, but they are much more difficult to find.” Others take a more functional point of view, arguing that establishing truth is more important than giving mathematicians an aesthetic glow, particularly if a result is ever to find an application. Defenders of this approach, who tend to be computer scientists, point out that conventional proofs are far from immune to error. At the turn of the century, most theorems were short enough to read in one sitting and were produced by a single author. Now proofs often extend to hundreds of pages or more and are so complicated that years may pass before they are confirmed by others. The current record holder of all conventional proofs was completed in the early 1980s and is called the classification of finite, simple groups. (A group is a set of elements, such as integers, together with an operation, such as ad-dition, that combines two elements to get a third one.) The demonstration consists of some 500 articles totaling nearly

15,000 pages and written by more than 100 workers. It has been said that the only person who grasped the entire proof was its general contractor, Daniel Gorenstein of Rutgers. Gorenstein died last year. Much shorter proofs can also raise doubts. Three years ago Wu-Yi Hsiang of Berkeley announced he had proved an old conjecture that one can pack the most spheres in a given volume by stacking them like cannonballs. Today some skeptics are convinced the 100-page proof is flawed; others are equally certain it is basically correct. Indeed, the key to greater reliability, according to some computer scientists, is not less computerization but more. Robert S. Boyer of the University of Texas at Austin has led an effort to squeeze the entire sprawling corpus of modern mathematics into a single data base whose consistency can be verified through automated “proof checkers.” The manifesto of the so-called QED Project states that such a data base will enable users to “scan the entirety of mathematical knowledge for relevant results and, using tools of the QED system, build upon such results with reliability and confidence but without the need for minute comprehension of the details or even the ultimate foundations.” The QED system, the manifesto proclaims rather grandly, can even “provide some antidote to the degenerative effects of cultural relativism and nihilism” and, presumably, protect mathematics from the alltoo-human willingness to succumb to fashion. The debate over computer proofs has intensified recently with the advent of a technique that offers not certainty but only a statistical probability of truth. Such proofs exploit methods similar to those underlying

Silicon Mathematicians The continuing penetration of computers into mathematics has revived an old debate: Can mathematics be entirely automated? Will the great mathematicians of the next century be made of silicon? In fact, computer scientists have been working for decades on programs that generate mathematical conjectures and proofs. In the late 1950s the artificial-intelligence guru Marvin Minsky showed how a computer could “rediscover” some of Euclid’s basic theorems in geometry. In the 1970’s Douglas Lenat, a former student of Minsky’s, presented a program that devised even more advanced geometry theorems. Skeptics contended that the results were, in effect, embedded in the original program. A decade ago the computer scientist and entrepreneur Edward Fredkin sought to revive the sagging interest in machine mathematics by creating what came to be known as the Leibniz Prize. The prize, administered by Carnegie Mellon University, offers $100,000 for the first computer program to devise a theorem that has a “profound effect” on mathematics. Some practitioners of what is known as automated reasoning think they may be ready to claim the prize. One is Larry Wos of Argonne National Laboratory, editor of the Journal of Automated Reasoning. He claims to have developed a program that has solved problems in mathematics and logic “that

have stumped people for years.” Another is Siemeon Fajtlowicz of the University of Houston, inventor of a program, called Graffiti, that has proposed “thousands” of conjectures in graph theory. None of these achievements comes close to satisfying the “profound effect” criterion, according to David Mumford of Harvard University, a judge for the prize. “Not now, not 100 years from now,” Mumford replies when asked to predict when the prize might be claimed. Some observers think computers will eventually surpass our mathematical abilities. After all, notes Ronald L. Graham of AT&T Bell Laboratories, “we’re not very well adapted for thinking about the space-time continuum or the Riemann hypothesis. We’re designed for picking berries or avoiding being eaten.” Others side with the mathematical physicist Roger Penrose of the University of Oxford, who in his 1989 book, The Emperor’s New Mind, asserted that computers can never replace mathematicians. Penrose’s argument drew on quantum theory and Gödel’s incompleteness theorem, but he may have been most convincing when discussing his personal experience. At its best, he suggested, mathematics is an art, a creative act, that cannot be reduced to logic any more than King Lear or Beethoven’s Fifth can.

14 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

error-correction codes, which ensure that transmitted messages are not lost to noise and other ef-fects by making them highly redundant. The proof must first be spelled out precisely in a rigorous form of mathematical logic. The logic then undergoes a further transformation called arithmetization, in which “and,” “or” and other functions are translated into arithmetic operations, such as addition and multiplication. Like a message transformed by an errorcorrection code, the “answer” of a probabilistic demonstration is distributed throughout its length—as are any errors. One checks the proof by querying it at different points and determining whether the answers are consistent; as the number of checks increases, so does the certainty that the argument is correct. Laszlo Babai of the University of Chicago, who developed the proofs two years ago (along with Lance Fortnow, Carsten Lund and Mario Szegedy of Chicago and Leonid A. Levin of Boston University), calls them “transparent.” Manuel Blum of Berkeley, whose work helped to pave the way for Babai’s group, suggests the term “holographic.” The Uncertain Future Whatever they are named, such proofs have practical drawbacks. Szegedy acknowledges that transforming a conventional demonstration into the probabilistic form is difficult, and the result can be a “much bigger and uglier animal.” A 1,000-line proof, for example, could easily balloon to 1,000 3 (1,000,000,000) lines. Yet Szegedy contends that if he and his colleagues can simplify the transformation process, probabilistic proofs might become a useful method for verifying mathematical propositions and large computations—such as those leading to the fourcolor theorem. “The philosophical cost of this efficient method is that we lose the absolute certainty of a Euclidean proof,” Babai not-ed in a recent essay. “But if you do have doubts, will you bet with me?” Such a bet would be ill advised, Levin believes, since a relatively few checks can make the chance of error vanishingly small: one divided by the number of particles in the universe. Even the most straightforward conventional proofs, Levin points out, are susceptible to doubts of this scale. “At the moment you find an error, your brain may disappear because of the Heisenberg uncertainty principle and be replaced by a new brain that thinks the proof is correct,” he says. Ronald L. Graham of AT&T Bell Laboratories suggests that the trend away from short, clear, conventional proofs that are beyond reasonable doubt may be inevitable. “The things you can prove may be just tiny islands, exceptions, compared to the vast sea of results that cannot be proved by human

PARTY PROBLEM was solved after a vast computation by Stanislaw P. Radziszowski and Brendan D. McKay. They calculated that at least 25 people are required to ensure either that four people are all mutual acquaintances or that five are mutual strangers. This diagram, in which red lines connect friends and yellow lines link strangers, shows that a party of 24 violates the dictum.

thought alone,” he explains. Mathematicians seeking to navigate uncharted waters may become increasingly dependent on experiments, probabilistic proofs and other guides. “You may not be able to provide proofs in a classical sense,” Graham says. Of course, mathematics may yield fewer aesthetic satisfactions as inves-tigators become more dependent on computers. “It would be very discouraging,” Graham remarks, “if somewhere down the line you could ask a computer if the Riemann hypothesis is correct and it said, ‘Yes, it is true, but you won’t be able to understand the proof.’ ” Traditionalists no doubt shudder at the thought. For now, at least, they can rally behind heros like Wiles, the conqueror of Fermat’s last theorem, who eschews computers, applications and other abominations. But there may be fewer Wileses in the future if reports from the front of precollege education are any guide. The Mathematical Sciences Research Institute at Berkeley, which is overseen by Thurston, has been holding an ongoing series of seminars with high school teachers to find new ways to entice students

15 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

into mathematics. This past January Lenore Blum, the institute’s deputy director, organized a seminar devoted to the question “Are Proofs in High School Geometry Obsolete?” The mathematicians insisted that proofs are crucial to ensure that a result is true. The high school teachers demurred, pointing out that students no longer considered traditional, axiomatic proofs to be as convincing as, say, visual arguments. “The high school teachers overwhelmingly declared that most students now (Nintendo/joystick/MTV generation) do not relate to or see the importance of ‘proofs,’ ” the minutes of the meeting stated. Note the quotation marks around SA the word “proofs.”

FURTHER READING ISLANDS OF TRUTH: A MATHEMATICAL MYSTERY CRUISE. Ivars Peterson. W. H. Freeman and Company, 1990. THE PROBLEMS OF MATHEMATICS. Ian Stewart. Oxford University Press, 1992. PI IN THE SKY: COUNTING, THINKING, AND BEING. John D. Barrow. Oxford University Press, 1992.

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Originally published in November 1994

Resolving Zeno’s Paradoxes For millennia, mathematicians and philosophers have tried to refute Zeno’s paradoxes, a set of riddles suggesting that motion is inherently impossible. At last, a solution has been found by William I. McLaughlin

O

nce upon a time Achilles met a tortoise in the road. The tortoise, whose mind was quicker than his feet, challenged the swift hero to a race. Amused, Achilles accepted. The tortoise asked if he might have a head start, as he was truly much slower than the demigod. Achilles agreed happily, and so the tortoise started off. After taking quite a bit of time to fasten one of his sandal’s ankle straps, Achilles bolted from the starting line. In no time at all, he ran half the distance that separated him from the tortoise. Within another blink, he had covered three quarters of the stretch. In another instant, he made up seven eighths and in another, fifteen sixteenths. But no

WILLIAM I. MCLAUGHLIN is a technical manager for advanced space astrophysics at the Jet Propulsion Laboratory in Pasadena, Calif., where he has worked since 1971. He has participated in many projects for the U.S. space program, including the Apollo lunarlanding program, the Viking mission to Mars, the Infrared Astronomical Satellite (IRAS ) and the Voyager project, about which he wrote an article for Scientific American in November 1986. He received a B.S. in electrical engineering in 1963 and a Ph.D. in mathematics in 1968, both from the University of California, Berkeley. McLaughlin conducts, in addition, research in epistemology.

matter how fast he ran, a fraction of the distance remained. In fact, it appeared that the hero could never overtake the plodding tortoise. Had Achilles spent less time in the gym and more time studying philosophy, he would have known that he was acting out the classic example used to illustrate one of Zeno’s paradoxes, which argue against the possibility of all motion. Zeno designed the paradox of Achilles and the tortoise, and its companion conundra (more about them later), to support the philosophical theories of his teacher, Parmenides. Both men were citizens of the Greek colony of Elea in southern Italy. In approximately 445 B.C., Parmenides and Zeno met with Socrates in Athens to exchange ideas on basic philosophical issues. The event, one of the greatest recorded intellectual encounters (if it really took place), is commemorated in Plato’s dialogue Parmenides. Parmenides, a distinguished thinker nearly 65 years old, presented to the young Socrates a startling thesis: “reality” is an unchanging single entity, seamless in its unity. The physical world, he argued, is monolithic. In particular, motion is not possible. Although the rejection of plurality and change appears idiosyncratic, it has, in general outline, proved attractive to numerous scholars. For example, the “absolute idealism” of the Oxford philosopher F. H. Bradley (1846–1924) has points in common with the Parmenidean outlook.

16 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

This portrayal of the world is contrary to our everyday experience and relegates our most fundamental perceptions to the realm of illusion. Parmenides relied on Zeno’s powerful arguments, which were later recorded in the writings of Aristotle, to support his case. For two and a half millennia, Zeno’s paradoxes have provoked debates and stimulated analyses. At last, using a formulation of calculus that was developed in just the past decade or so, it is possible to resolve Zeno’s paradoxes. The resolution depends on the concept of infinitesimals, known since ancient times but until recently viewed by many thinkers with skepticism.

T

he tale of Achilles and the tortoise depicts one of Zeno’s paradoxes, usually denoted “The Dichotomy”: any distance, such as that between the two contenders, over which an object must traverse can be halved ( 1 ⁄ 2, 1 ⁄ 4, 1 ⁄ 8 and so on) into an infinite number of spatial segments, each representing some distance yet to be traveled. As a result, Zeno asserts that no motion can be completed because some distance, no matter how small, always remains. It is important to note that he does not say that infinitely many stretches cannot add up to a finite distance (glancing at the geometry of an infinitely partitioned line shows immediately, without any sophisticated calculations, that an infinite number of pieces sum to a finite interval). Rather the

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

force of Zeno’s objection to the idea of motion comes from the obligation to explain how an infinite number of acts—crossing one interval—can be serially completed. Zeno made a second attack on the conceptual underpinnings of motion by viewing this first argument from a slightly different perspective. His second paradox is as follows: Before an object, say, an arrow, gets to the halfway mark of its supposed journey

would be so very near zero as to be numerically impotent; such quantities would elude all measurement, no matter how precise, like sand through a sieve. Giovanni Benedetti (1530–1590), a predecessor of Galileo, postulated that when an object appeared to be frozen in midair to Zeno, he was in fact seeing only part of the action, as though one were watching a slide show instead of a movie. Between the static

quantities, nor quantities infinitely small, nor yet nothing. May we not call them ghosts of departed quantities?” He observed further: “Whatever mathematicians may think of fluxions [rates of change], or the differential calculus, and the like, a little reflexion will shew them that, in working by those methods, they do not conceive or imagine lines or surfaces less than what are perceivable to sense.”

Mathematicians found infinitesimals hard to skirt in the course of their discoveries, no matter how distasteful they found them in theory. (an achievement granted in the preceding case), it must first travel a quarter of the distance. As in Zeno’s first objection, this reasoning can be continued indefinitely to yield an infinite regress, thus leading to his insistence that motion could never be initiated. Zeno’s third paradox takes a different tack altogether. It asserts that the very concept of motion is empty of content. Zeno invites us to consider the arrow at any one instant of its flight. At this point in time, the arrow occupies a region of space equal to its length, and no motion whatsoever is evident. Because this observation is true at every instant, the arrow is never in motion. This objection, in a historical sense, proved the most troublesome for would-be explainers of Zeno’s paradoxes. Many philosophers and mathematicians have made various attempts to answer Zeno’s objections. The most direct approach has simply been to deny that a problem exists. For example, Johann Gottlieb Waldin, a German professor of philosophy, wrote in 1782 that the Eleatic, in arguing against motion, assumed that motion exists. Evidently the good professor was not acquainted with the form of argument known as reductio ad absurdum: assume a state of affairs and then show that it leads to an illogical conclusion. Nevertheless, other scholars made progress by wrestling with how an infinite number of actions might occur in the physical world. Their explanations have continually been intertwined with the idea of an infinitesimal, an interval of space or time that embodies the quintessence of smallness. An infinitesimal quantity, some surmised,

images Zeno saw were infinitesimally small instants of time in which the object moved by equally small distances. Others sidestepped the issue by arguing that intervals in the physical world cannot simply be subdivided an infinite number of times. Friedrich Adolf Trendelenburg (1802–1872) of the University of Berlin built an entire philosophical system that explained human perceptions in terms of motion. In doing so, he freed himself from explaining motion itself. Similarly, in this century, the English philosopher and mathematician Alfred North Whitehead (1861–1947) constructed a system of metaphysics based on change, in which motion was a special case. Whitehead responded to Zeno’s objections by insisting that events in the physical world had to have some extent; namely, they could not be pointlike. Likewise, the Scottish philosopher David Hume (1711–1776) wrote, “All the ideas of quantity upon which mathematicians reason, are nothing but particular, and such as are suggested by the senses and imagination and consequently, cannot be infinitely divisible.” Either way, the subject of infinitesimals (and whether they exist or not) generated a long and acrimonious literature of its own. Until recently, most mathematicians thought them to be a chimera. The Irish bishop George Berkeley (1685–1753) is noted principally for his idealistic theory, which denied the reality of matter, but he, too, wrestled with infinitesimals. He believed them ill conceived by the mathematicians of the time, including Newton. “They are neither finite

17 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

Indeed, mathematicians found infinitesimals hard to skirt in the course of their discoveries, no matter how distasteful they found them in theory. Some historians believe the great Archimedes (circa 287–212 B.C.) achieved some of his mathematical results using infinitesimals but employed more conventional modes for public presentations. Infinitesimals left their mark during the 17th and 18th centuries as well in the development of differential and integral calculus. Elementary textbooks have long appealed to “practical infinitesimals” to convey certain ideas in calculus to students. When analysts thought about rigorously justifying the existence of these small quantities, innumerable difficulties arose. Eventually, mathematicians of the 19th century invented a technical substitute for infinitesimals: the so-called theory of limits. So complete was its triumph that some mathematicians spoke of the “banishment” of infinitesimals from their discipline. By the 1960s, though, the ghostly tread of infinitesimals in the corridors of mathematics became quite real once more, thanks to the work of the logician Abraham Robinson of Yale University [see “Nonstandard Analysis,” by Martin Davis and Reuben Hersh; SCIENTIFIC AMERICAN, June 1972]. Since then, several methods in addition to Robinson’s approach have been devised that make use of infinitesimals.

W

hen my colleague Sylvia Miller and I started our work on Zeno’s paradoxes, we had the advantage that infinitesimals had be-

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

difference between two concrete numbers must be concrete (and hence, standard). If this difference were infinitesimal, the definition of an infinitesimal as less than all standard numbers would be violated. The consequence of this fact is that both end points of an infinitesimal interval cannot be labeled using concrete numbers. Therefore, an infinitesimal interval can never be captured through measurement; infinitesimals remain forever beyond the range of observation.

PATRICIA J. WYNNE

S RACE between Achilles and the tortoise illustrates one of Zeno’s paradoxes. Achilles gives the tortoise a head start. He must then make up half the distance between them, then three fourths, then seven eighths and so on, ad infinitum. In this way, it would seem he could never come abreast of the sluggish animal.

come mathematically respectable. We were intuitively drawn to these objects because they seem to provide a microscopic view of the details of motion. Edward Nelson of Princeton University created the tool we found most valuable in our attack, a brand of nonstandard analysis known by the rather arid name of internal set theory (IST). Nelson’s method produces startling interpretations of seemingly familiar mathematical structures. The results are similar, in their strangeness, to the structures of quantum theory and general relativity in physics. Because these two theories have taken the better part of a century to gain widespread acceptance, we can only admire the power of Nelson’s imagination. Nelson adopted a novel means of defining infinitesimals. Mathematicians typically expand existing number systems by tacking on objects that have desirable properties, much in the same way that fractions were sprinkled between the integers. Indeed, the number system employed in modern mathematics, like a coral reef, grew by accretion onto a supporting base: “God made the integers, all the rest is the work of man,” declared Leopold Kronecker (1823–1891). Instead the way of IST is to “stare” very hard at the existing number system and note that it already contains numbers that, quite reasonably, can be considered infinitesimals. Technically, Nelson finds nonstandard

numbers on the real line by adding three rules, or axioms, to the set of 10 or so statements supporting most mathematical systems. (Zermelo-Fraenkel set theory is one such foundation.) These additions introduce a new term, standard, and help us to determine which of our old friends in the number system are standard and which are nonstandard. Not surprisingly, the infinitesimals fall in the nonstandard category, along with some other numbers I will discuss later. Nelson defines an infinitesimal as a number that lies between zero and every positive standard number. At first, this might not seem to convey any particular notion of smallness, but the standard numbers include every concrete number (and a few others) you could write on a piece of paper or generate in a computer: 10, pi, 1 ⁄ 1000 and so on. Hence, an infinitesimal is greater than zero but less than any number, however small, you could ever conceive of writing. It is not immediately apparent that such infinitesimals do indeed exist, but the conceptual validity of IST has been demonstrated to a degree commensurate with our justified belief in other mathematical systems. Still, infinitesimals are truly elusive entities. Their elusiveness rests on the mathematical fact that two concrete numbers—those having numerical content—cannot differ by an infinitesimal amount. The proof, by reductio ad absurdum, is easy: the arithmetic

18 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

o how can these phantom numbers be used to refute Zeno’s paradoxes? From the above discussion it is clear that the points of space or time marked with concrete numbers are but isolated points. A trajectory and its associated time interval are in fact densely packed with infinitesimal regions. As a result, we can grant Zeno’s third objection: the arrow’s tip is caught “stroboscopically” at rest at concretely labeled points of time, but along the vast majority of the stretch, some kind of motion is taking place. This motion is immune from Zenonian criticism because it is postulated to occur inside infinitesimal segments. Their ineffability provides a kind of screen or filter. Might the process of motion inside one of these intervals be a uniform advance across the interval or an instantaneous jump from one end to the other? Or could motion comprise a series of intermediate steps or else a process outside of time and space altogether? The possibilities are infinite, and none can be verified or ruled out since an infinitesimal interval can never be monitored. Credit for this rebuttal is due to Benedetti, Trendelenburg and Whitehead for their earlier insights, which can now be formalized by means of IST. We can answer Zeno’s first two objections more easily than we did the third, but we need to use another mathematical fact from IST. Every infinite set of numbers contains a nonstandard number. Before drawing out the Zenonian implications of this statement, it is necessary to talk about the two other types of nonstandard numbers that are readily manufactured from infinitesimal numbers. First, take all the infinitesimals, which by definition are wedged between zero and all the positive, standard numbers, and put a minus sign in front of each one. Now there is a symmetrical clustering of these small objects about zero. To create “mixed” nonstandard numbers, take any standard number, say, one half, and add to it each of the nonstandard infinitesimals in the grouping around zero. This act of addition translates the original cluster of infinitesimals to positions on either side of one half. Similarly, every standard number can be viewed as having its own collection of nearby, nonstandard numbers, each one only an infinitesimal distance from the standard number. The third type of nonstandard number is

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

simply the inverse of an infinitesimal. Because an infinitesimal is very small, its inverse will be very large (in the standard realm, the inverse of one millionth is one million). This type of nonstandard number is called an unlimited number. The unlimited numbers, though large, are finite and hence smaller than the truly infinite numbers created in mathematics. These unlimited numbers live in a kind of twilight zone between the familiar standard numbers, which are finite, and the infinite ones. If, as demonstrated in IST, every infinite set contains a nonstandard number, then the infinite series of checkpoints Zeno used to gauge motion in his first argument must contain a mixed, nonstandard number. In fact, as Zeno’s infinite series of numbers creeps closer to one, a member of that series will eventually be within an infinitesimal distance from one. At that point, all succeeding members of the series will be nonstandard members of the cluster about one, and neither Zeno nor anyone else will be able to chart the progress of a moving object in this inaccessible region.

T

here is an element of irony in using infinity, Zeno’s putative weapon, to deflate his claims. To refute Zeno’s first paradox, we need only state the epistemological principle that we are not responsible for explaining situations we cannot observe. Zeno’s infinite series of checkpoints contains nonstandard numbers, which have no numerical meaning, and so we reject his argument based on these entities. Because no one could ever, even in principle, observe the full domain of checkpoints that his objection addresses, the objectionable behavior he postulates for the moving

object is moot. Many descriptions of motion in the microrealm other than that containing the full series of checkpoints could apply, and just because his particular scenario causes conceptual problems, there is no reason to anathematize the idea of motion. His second argument, attempting to show that an object can never even start to move, suffers from the same malady as the first, and we reject it on like grounds.

W

e have resolved Zeno’s three paradoxes using some technical results from IST and the principle that nonstandard numbers are not suitable for describing matters of fact, observed or purported. Still, more can be said regarding the matter than just the assurance that Zeno’s objections do not preclude motion. Indeed, we can construct a theory of motion using a very powerful result from IST. The theory yields the same results as do the tools of the calculus, and yet it is easier to visualize and does not fall prey to Zeno’s objections. A theorem proved in IST states that there exists a finite set, call it F, that contains all the standard numbers! The corollary that there are only a finite number of standard numbers would seem to be true, but surprisingly, it is not. In developing IST, Nelson needed to finesse the conventional way mathematicians form objects. A statement in IST is called internal if it does not contain the label “standard.” Otherwise, the statement is called external. Mathematicians frequently create subsets from larger sets by predicating a quality that characterizes each of the objects in the subset—the balls that are red or the integers that are even. In IST, however, it is forbidden to use external pred-

icates, such as standard, to define subsets; the stricture is introduced to avoid contradictions. For example, imagine the set of all standard numbers in F. This set would be finite because it is a subset of a finite set. It would therefore have a least member, say, r. But then r – 1 would be a standard number less than r, when r was supposed to be the smallest standard number. Thus, we cannot say the standard numbers are finite or infinite in extent, because we cannot form the set of them and count them. Nevertheless, the finite set F, though constrained as to how it can be visualized, is useful for constructing our theory of motion. This theory can be expressed quite simply as stepping through F, where each member of F represents a distinct moment. For convenience, consider only those members of F that fall between 0 and 1. Let time 0 be the instant when we start tracking a moving object. The second instant when we might try to observe the object is at time f1, where f1 is the smallest member of F that is greater than 0. Ascending through F in this fashion, we eventually reach time fn , where fn is the largest member of F less than 1. In one more step, we reach 1 itself, the destination in this example. In order to walk through a noninfinitesimal distance, such as the span from 0 to 1 using infinitesimal steps, the subscript n of fn must be an unlimited integer. The process of motion then is divided into n + 1 acts, and because n + 1 is also finite, this number of acts can be completed sequentially. Of the possible observing times identified earlier, the object’s progress could be reported solely at those instants corresponding to certain standard numbers in F. (By the way, f1 and fn would be nonstandard, as they are

Topology of the Real Line

—3

T

—2

—1

0

1

he real numbers consist of the integers (positive and negative whole numbers), rational numbers (those that can be expressed as a fraction) and irrational numbers (those that cannot be expressed as a fraction). The real numbers can be represented as points on a straight line known as the real line (above). The mathematician Edward Nelson of Princeton University labeled three types of numbers as nonstandard within this standard number system. Infinitesimal nonstandard numbers are smaller than any positive standard number yet are greater than zero.

2

5

N

N+1

Mixed nonstandard numbers, shown grouped around the integer 5, result from adding and subtracting infinitesimal amounts to standard numbers. In fact, every standard number is surrounded by such mixed, nonstandard neighbors. Unlimited nonstandard numbers, represented as N and N + 1, are the inverses of infinitesimal nonstandard numbers. Each unlimited number is greater than every standard number and yet less than the infinite real numbers. The nonstandard real numbers prove useful in resolving Zeno’s paradoxes.

19 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

JOHNNY JOHNSON

—(N + 1) — N

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Calculus by Means of Infinitesimals

T

FEET

32dt + 16dt 2, divided by dt, is the deo see the relation between in0 sired average velocity, 32 + 16dt. finitesimals and differential calBecause 16dt is but an infinitesimal culus, consider the simple case of a 50 amount, undetectable for all intents and falling stone. The distance the stone has purposes, it can be considered equal to traveled in feet can be calculated from 100 0. Thus, after one second of travel, the the formula s = 16t 2, where t equals formula yields the stone’s instantathe time elapsed in seconds. For exam150 neous velocity as 32 feet per second. ple, if a stone has fallen for two seconds, This manipulation, of course, resemit will have traveled 64 feet. 200 bles those used in traditional, differenSuppose, however, one wishes to caltial calculus. There the small residue culate the instantaneous velocity of the 250 16dt cannot be dropped at the end of stone. The average speed of a moving the calculation; it is a noninfinitesimal object equals the total distance it trav300 0 1 2 3 4 quantity. Instead, in this calculus, it els divided by the total amount of time it SECONDS must be argued away using the theory takes. By using this formula over an inof limits. In essence, the limit process finitesimal change in the total distance and time, one can calculate a fair approximation of an object’s instantaneous renders the interval of length dt sufficiently small so that the average velocity is arbitrarily close to 32. As before, the instantaneous velocity of the stone afvelocity. Let dt represent an infinitesimal change in time and ds an infinitesimal ter one second of travel equals 32 feet per second. Similarly, judicious use of change in distance. The computation for the velocity of the stone after one infinitesimal regions facilitates the computation of the area of complicated resecond of travel, then, will be as follows: The time frame under consideration gions, a basic problem of integral calculus. Some think the newer calculus is ranges from t = 1 to t = 1 + dt. The position of the stone during that time pedagogically superior to calculus without infinitesimals. Nevertheless, both changes from s = 16(1) 2 to s = 16(1 + dt )2. The total change in distance, methods are equally rigorous and yield identical results.

infinitesimally close to 0 and 1, respectively.) For example, although we can express a standard number to any finite (but not unlimited) number of decimal places and use this approximation as a measurement label, we cannot access the unlimited tail of the expansion to alter a digit and thus define a nonstandard, infinitesimally close neighbor. Only concrete standard numbers are effective as measurement labels; the utility of their nonstandard neighbors for measurement is illusory.

M

uch is superfluous in this theory of motion, and much is left unsaid. It suffices, however, in the sense that it can easily be translated into the symbolic notation of the integral or differential calculus, commonly used to describe the details of motion [see box on preceding page]. More important in the present context, the finiteness of the set F enables us to jump over the pitfalls in Zeno’s first two paradoxes. His third objection is dodged as before: motion in real time is an unknown process that takes place in infinitesimal intervals between the standard points of F; the

nonstandard points of F are irrelevant given that they cannot be observed. For many centuries, Zeno’s logic stood mostly intact, proving the refractory nature of his arguments. A resolution was made possible through two basic features of IST: first, the ability to partition an interval of time or space into a finite number of ineffable infinitesimals and, second, the fact that standardly labeled points—the only ones that can be used for measurement—are isolated objects on the real line. Is our work merely the solution to an ancient puzzle? Possibly, but there are several directions in which it might prove extensible. Aside from its mathematical value, IST is ripe with epistemological import, as this analysis has shown. It might well be modified to constitute a general epistemic logic. Also, infinitesimal intervals, or their generalization, would promise a technical resource to house Whitehead’s so-called actual entities, the generative atoms of his philosophical system. Finally, the current theory of motion and the predictions of quantum physics are not dissimilar in that they both restrict the obser-

vation of certain events to discrete values. Of course, this theory of motion is not a version of quantum mechanics (nor relativity theory, for that matter). Because the theory resulted from a thought experiment on Zeno’s terms, it holds no direct connection to present physical theory. Moreover, the specific rules inherited from IST are probably not those best suited to describe reality. Modern physics might adapt the IST approach by modifying its rule system and introducing “physical constants,” perhaps by assigning parameters to the set F. But maybe not. Still, the simplicity and elegance of such thought experiments have catalyzed research throughout the ages. Notable examples include Heinrich W. M. Olbers, questioning why the sky is dark at night despite stars in every direction, or James Clerk Maxwell, summoning a meddling, microscopic demon to batter the second law of thermodynamics. Likewise, Zeno’s arguments have stimulated examinations of our ideas about motion, time and space. The path to their resolution has been SA eventful.

FURTHER READING A HISTORY OF GREEK PHILOSOPHY, Vol. 2: THE PRESOCRATIC TRADITION FROM PARMENIDES TO DEMOCRITUS. W. K. Guthrie. Cambridge University Press, 1965. ZENO OF ELEA. Gregory Vlastos in The Encyclopedia of Philosophy. Edited by Paul Edwards. Macmillan Publishing Company, 1967. NONSTANDARD ANALYSIS. Martin Davis and Reuben Hersh in Scientific American, Vol. 226, No. 6, pages 78–86; June 1972. INTERNAL SET THEORY: A NEW APPROACH TO NONSTANDARD ANALYSIS. Edward Nelson in Bulletin of the American Mathematical Society, Vol. 83, No. 6, pages 1165–1198; November 1977. AN EPISTEMOLOGICAL USE OF NONSTAN-DARD ANALYSIS TO ANSWER ZENO’S OB-JECTIONS AGAINST MOTION. William I. McLaughlin and Sylvia L. Miller in Synthese, Vol. 92, No. 3, pages 371–384; September 1992.

20 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Originally published in April 1995

A Brief History of Infinity The infinite has always been a slippery concept. Even the commonly accepted mathematical view, developed by Georg Cantor, may not have truly placed infinity on a rigorous foundation by A. W. Moore

F

or more than two millennia, mathematicians, like most people, were unsure what to make of the infinite. Several paradoxes devised by Greek and medieval thinkers had convinced them that the infinite could not be pondered with impunity. Then, in the 1870s, the German mathematician Georg Cantor unveiled transfinite mathematics, a branch of mathematics that seemingly resolved all the puzzles the infinite had posed. In his work Cantor showed that infinite numbers existed, that they came in different sizes and that they could be used to measure the extent of infinite sets. But did he really dispel all doubt about mathematical dealings with infinity? Most people now believe he did, but I shall suggest that in fact he may have reinforced that doubt. The hostility of mathematicians toward infinity began in the fifth century B.C., when Zeno of Elea, a student of Parmenides, formulated the well-known paradox of Achilles and the tortoise [see “Resolving Zeno’s Paradoxes,” by William I. McLaughlin; SCIENTIFIC AMERICAN, November 1994]. In this conundrum the swift demigod challenges the slow tortoise to a race and grants her a head start. Before he can overtake her, he must reach the point at which she began, by which time she will have advanced a little. Achilles must now make up the new distance separating them, but by the time he does so, she will have advanced again. And

A. W. MOORE is a tutorial fellow in philosophy at St. Hugh’s College of the University of Oxford. He studied for his Ph.D. in the philosophy of language at Balliol College at Oxford. His main academic interests are in logic, metaphysics and the philosophies of Immanuel Kant and Ludwig Wittgenstein, all of which have informed his work on the infinite. He is at work on a book about the metaphysics of objectivity and subjectivity.

so on, ad infinitum. It seems that Achilles can never overtake the tortoise. In like manner Zeno argued that it is impossible to complete a racecourse. To do so, it is necessary to reach the halfway point, then the three-quarters point, then the seven-eighths point, and so on. Zeno concluded not only that motion is impossible but that we do best not to think in terms of the infinite. The mathematician Eudoxus, similarly wary of the infinite, developed the so-called method of exhaustion to circumvent it in certain geometric contexts. Archimedes exploited that method some 100 years later to find the exact area of a circle. How did he proceed? In the box on page 23, I present not his actual derivation but a corruption of it. Part of Archimedes’ own procedure was to consider the formula for the area of a polygon with n equal sides—call it Pn—inscribed inside a circle C. According to the distortion of his argument, this formula can be applied to the circle itself, which is just a polygon with infinitely many, infinitely small sides. The perversion of Archimedes’ argument has some intuitive appeal, but it would not have satisfied Archimedes. We cannot uncritically make use of the infinite as though it were just some unusually big integer. Part of what is going on here is that the larger n is, the more nearly Pn matches C. But it is also true that the larger n is, the more nearly Pn approximates a circle with a bulge—call it C*. The key point intuitively is that C, unlike its deformed counterpart C*, is the limit of the polygons—or what they are tending toward. Still, it is very hard to see any way of capturing this intuition without, once again, thinking of C as an “infinigon.” Archimedes provided a way. He pinpointed the crucial difference between C and C* by proving the following point: no matter how small an area you consider, call it ε (the Greek letter epsilon), there exists an integer n that is large enough for the area of Pn to be within ε of

21 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

the area of C. The same is not true of C*. This fact, combined with a similar result for circumscribed polygons and supplemented with a refined version of the logic contained in that argument, finally enabled Archimedes to show, without ever invoking the infinite, that the area of a circle equals π r 2. The Actual and Potential Infinite

A

lthough Archimedes successfully ducked the infinite in this particular exercise, the Pythagoreans (a religious society founded by Pythagoras) happened on a case in which the infinite was truly inescapable. This find shattered their belief in two fundamental cosmological principles: Peras (the limit), which subsumed all that was good, and Apeiron (the unlimited or infinite), which encompassed all that was bad. They had insisted that the whole of creation could be understood in terms of, and indeed was ultimately constituted by, the positive integers, each of which is finite. This reduction was made possible, they maintained, by the fact that Peras was ever subjugating Apeiron. Pythagoras had discovered, however, that the square of the hypotenuse (the longest side) of a right-angled triangle is equal to the sum of the squares of the other two sides. Given this theorem, the ratio of a square’s diagonal to each side is √ 2 to 1, since 12 + 12 = ( √2) 2. Were Peras impervious, this ratio should be expressible in the form p to q, where p and q are both positive integers. Yet this is impossible. Imagine two positive integers, p and q, such that the ratio of p to q, or p divided by q, is equivalent to √ 2. We can assume that p and q have no common factor greater than 1 (we could, if necessary, divide by that factor). Now, p 2 is twice q 2. So p 2 is even, which means that p itself is even. Hence, q must be odd, otherwise 2 would be a common factor. But consider: if p

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

is even, there must be a positive integer r that is exactly half of p. Therefore, (2r) 2 equals 2q 2, or 2r 2 equals q 2, which means that q 2 is even, and so q itself is also even, contrary to what was proved above. For the Pythagoreans, this result was nothing short of catastrophic. (According to legend, one of them was shipwrecked at sea for revealing the discovery to their enemies.) They had come on an “irrational” number. In doing so, they had seen the limitations of the positive integers, and they had been forced to acknowledge the presence of the infinite in their very midst. Indeed, a modern mathematician would say that √2

thing deeper and more abstract. Existing “in time” or existing “all at once” assumed much broader meanings. To take exception to the actual infinite was to object to the very idea that some entity could have a property that surpassed all finite measure. It was also to deny that the infinite was itself a legitimate object of study. Some 2,000 years later the infinite, both actual and potential, exercised mathematicians once more as they developed the calculus. Early work on the calculus, ushered in by Isaac Newton and Gottfried Wilhelm Leibniz in the late 17th century, fell far short of Greek standards of rigor. Indeed, mathe-

also include odd numbers. The medievals proffered many similar examples, some of which were geometric. In the 13th century the Scottish mathematician John Duns Scotus puzzled over the case of two concentric circles: all the points on the shorter circumference of the smaller circle can be paired off with all the points on the longer circumference of the bigger circle. The same result applies to two spheres. Some 350 years later Galileo discussed a variation of the pairing example of the even integers, based instead on squared integers. Particularly striking is the fact that as increasingly larger segments of the sequence of

Asking whether Cantor’s continuum hypothesis is true may be like asking whether Hamlet was left-handed. It may be that not enough is known to form an answer. is a kind of “infinite object.” Not only is its decimal expansion infinite, but this expansion never adopts a recurring finite pattern. In the fourth century B.C. Aristotle recognized a more general problem. On the one hand, we are under pressure to acknowledge the infinite. Quite apart from what we may have to say about √ 2, time appears to continue indefinitely, numbers seem to go on endlessly, and space, time and matter seem to be forever divisible. On the other hand, we are under pressure from various sources, including Zeno’s paradoxes, to repudiate the infinite. Aristotle’s solution to this dilemma was masterful. He distinguished between two different kinds of infinity. The actual infinite is that whose infinitude exists at some point in time. In contrast, the potential infinite is that whose infinitude is spread over time. All the objections to the infinite, Aristotle insisted, are objections to the actual infinite. The potential infinite, on the other hand, is a fundamental feature of reality. It deserves recognition in any process that can never end, including counting, the division of matter and the passage of time itself. This distinction between the two types of infinity provided a solution to Zeno’s paradoxes. Traversing a region of space does not involve moving across an actual infinity of subregions, which would be impossible. But it does mean crossing a potential infinity of subregions, in the sense that there can be no end to the process of dividing the space. This conclusion, fortunately, is harmless. Aristotle’s parting of the actual and the potential infinite long stood as orthodoxy. Nevertheless, scholars usually interpreted his reference to time as a metaphor for some-

maticians had made extensive, uncritical use of infinitesimals, items taken to be too small for measure. Sometimes these quantities were considered equal to zero. For example, when they were added to another number, the value of the original number remained the same. At other times, they were taken to be different from zero and used in division. Guillaume François Antoine de l’Hôpital wrote: “A curve may be regarded as the totality of an infinity of straight segments, each infinitely small: or ... as a polygon with an infinite number of sides.” Only in the 19th century did French mathematician AugustinLouis Cauchy and German mathematician Karl Weierstrass resuscitate the method of exhaustion and give the calculus a secure foundation. The Infinite and Equinumerosity

A

s a result of Cauchy’s and Weierstrass’s work, most mathematicians felt less threatened by Zeno’s paradoxes. Of more concern by then was a family of paradoxes born in the Middle Ages dealing with equinumerosity. These puzzles derive from the principle that if it is possible to pair off all the members of one set with all those of another, the two sets must have equally many members. For example, in a nonpolygamous society there must be just as many husbands as wives. This principle looks incontestable. Applied to infinite sets, however, it seems to flout a basic notion first articulated by Euclid: the whole is always greater than any of its parts. For instance, it is possible to pair off all the positive integers with those that are even: 1 with 2, 2 with 4, 3 with 6 and so on—despite the fact that positive integers

22 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

positive integers are considered, the proportion of these integers that are squares tends toward zero. Nevertheless, the pairing still proceeds indefinitely. It is certainly tempting, in view of these difficulties, to eschew infinite sets entirely. More generally, it is tempting to deny, as did Aristotle, that infinitely many things can be gathered together all at once. Eventually, though, Cantor challenged the Aristotelian view. In work of great brilliance he took the paradoxes in his stride and formulated a coherent, systematic and precise theory of the actual infinite, ready for any skeptical gaze. Cantor accepted the “pairing off” principle and its converse, namely, that no two sets are equinumerous unless their members can be paired off. Accordingly, he accepted that there are just as many even positive integers as there are positive integers altogether (and likewise in the other paradoxical cases). Let us for the sake of argument, and contemporary mathematical convention for that matter, follow suit. If this principle means that the whole is no greater than its parts, so be it. We can in fact use this idea to define the infinite, at least in its application to sets: a set is infinite if it is no bigger than one of its parts. More precisely, a set is infinite if it has as many members as does one of its proper subsets. What remains an open question, once things have been clarified in this way, is whether all infinite sets are equinumerous. Much of the impact of Cantor’s work came in his demonstration that they are not. There are different infinite sizes. This proposition results from what is known as Cantor’s theorem: no set, and in particular no infinite set, has as many members as it has subsets. In

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Archimedes and the Area of a Circle ow did Archimedes use the method of exhaustion to find the area of a circle? Here is the corruption of his argument. Imagine a circle C that has a radius r. For each integer n greater than 2, we can construct a regular polygon with n sides and inscribe it inside C. This n-sided polygon—call it Pn — can be divided into n congruent triangles. Label the base of each trianP4 P6 gle b n and its height h n. Then the area of each triangle is 1/2 b nh n. Thus, the area of Pn as a whole is n(1/2 b nh n ), or 1/2 nb nh n. But C itself is a polygon with infinitely many, infinitely small sides. In other words, C results when we extend the

other words, no set is as big as the set of its subsets. Why not? Because if a set were, it would be possible to pair off all its members with all its subsets. Some members would then be paired off with subsets that contained them, others not. So what of the set of those members that were not included in the set with which they had been paired? No member could be paired off with this subset without contradiction. The argument can be recast in a diagram [see illustration above]. For convenience, I will focus on the set of positive integers. I can represent any subset of the set of positive integers by an infinite sequence of yeses and noes, registering whether successive positive integers do or do not belong to the set. For example, the set of even integers can be represented by the sequence <no, yes, no, yes, no... >, corresponding to 1, 2, 3, 4, 5, and so forth. We can do the same for the set of odd integers , the set of prime numbers <no, yes, yes, no, yes... > and the set of squares . Generally, then, any assignment of different subsets to individual positive integers (such as the purely arbitrary example illustrated) can be represented as an infinite square of yeses and noes. To show that at least one subset is

original definition of Pn and allow n to be infinite. In this case, nb n is the circumference of C, which equals 2π r (which follows from the definition of π ), and h n is the radius r. So the area of C is 1/2(2π rr ), or simply π r 2.

P8

nowhere on this list of subsets, we make a new subset by moving down the “square’s diagonal,” replacing each yes with a no, and vice versa. In the case illustrated, we write < yes, yes, no, no... >. What results represents the subset in question. For by construction it differs from the first subset listed with respect to whether 1 belongs to it, from the second with respect to whether 2 belongs to it, from the third with respect to whether 3 belongs to it, and so on. There is a pleasant historical quirk here: just as studying a diagonal had led the Pythagoreans to acknowledge an infinitude beyond the grasp of the positive integers, the same was true in a different way in Cantor’s case. Cantor later devised infinite cardinals— numbers that can be used to measure the size of infinite sets. He invented a kind of arithmetic for them as well. Having defined his terms, he explored what happens when one infinite cardinal is added to another, when it is multiplied by another, when it is raised to a power, and so forth. His work showed mathematical craftsmanship of the highest caliber. But even in his own terms, difficulties remained. The continuum problem is perhaps the best known of these troubles. The set of positive integers, we have seen, is smaller than the set of sets of positive inte-

1

2

3

4 ... n ...

1

4

9

16 . . . n 2 . . .

SETS ARE THE SAME SIZE if all their members can be paired with one another. But this principle seems to be violated in infinite sets. All the squared integers can be matched with every single positive integer (above), even though the set of squares seems smaller. Similarly, all the points on the smaller sphere can be paired o› with those on the larger one (left).

JARED SCHNEIDMAN DESIGN

P12 JARED SCHNEIDMAN DESIGN

H

23 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

gers. But how much smaller? Specifically, are there any sets of intermediate size? Cantor’s Continuum Hypothesis

C

antor’s own hypothesis, his famous “continuum hypothesis,” was that there are not. But he never successfully proved this idea, nor did he disprove it. Subsequent work has shown that the situation is far graver than he had imagined. Using all the accepted methods of modern mathematics, the issue cannot be settled. This problem raises philosophical questions about the determinacy of Cantor’s conception. Asking whether the continuum hypothesis is true may be like asking whether Hamlet was lefthanded. It may be that not enough is known to form an answer. If so, then we should rethink how well Cantor’s work tames the actual infinite. Of even more significance are questions surrounding the set of all sets. Given Cantor’s theorem, this collection must be smaller than the set of sets of sets. But wait! Sets of sets are themselves sets, so it follows that the set of sets must be smaller than one of its own proper subsets. That, however, is impossible. The whole can be the same size as the part, but it cannot be smaller. How did Cantor escape this trap? With wonderful pertinacity, he denied that there is any such thing as the set of sets. His reason lay in the following picture of what sets are like. There are things that are not sets, then there are sets of all these things, then there are sets of all those things, and so on, without end. Each set belongs to some further set, but there never comes a set to which every set belongs. Cantor’s reasoning might seem somewhat ad hoc. But an argument of the sort is required, as revealed by Bertrand Russell’s memorable paradox, discovered in 1901. This paradox concerns the set of all sets that do not belong to themselves. Call this set R. The set of mice, for example, is a member of R; it does not belong to itself because it is a set, not a mouse. Russell’s paradox turns

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

POSITIVE INTEGERS 1

2

3

4

5

EVEN INTEGERS

NO

YES

NO

YES

NO

ODD INTEGERS

YES

NO

YES

NO

YES

PRIMES

NO

YES

YES

NO

YES

SQUARES

YES

NO

NO

YES

NO

MULTIPLES OF 4

NO

NO

NO

YES

NO

YES

YES

NO

NO

YES

DIAGONALIZED SET

. . .

. . .

. . .

CANTOR’S THEOREM—that no set has as many members as it has subsets—is proved by diagonalization, which creates an extra subset. Each subset of the set of positive integers is represented as a series of yeses and noes. A yes indicates that the integer belongs to the subset; a no that it does not. Replacing each yes with a no, and vice versa, down the diagonal (shaded area) creates another subset.

be suggesting, with what most people would say. Well, certainly most people would say the set of positive integers is “really” infinite. But, then again, most people are unaware of Cantor’s results. They would also deny that one infinite set can be bigger than another. My point is not about what most people would say but rather about how they understand their terms—and how that understanding is best able, for any given purpose, to absorb the shock of Cantor’s results. Nothing here is forced on us. We could say some infinite sets are bigger than others. We could say the set of positive integers is only finite. We could hold back from saying either and deny that the set of positive integers exists. If the task at hand is to articulate certain standard mathematical results, I would not advocate using anything other than standard

mathematical terminology. But I would urge mathematicians and other scientists to use more caution than usual when assessing how Cantor’s results bear on traditional conceptions of infinity. The truly infinite, it SA seems, remains well beyond our grasp. FURTHER READING INFINITY AND THE MIND: THE SCIENCE AND PHILOSOPHY OF THE INFINITE. Rudy Rucker. Harvester, 1982. TO INFINITY AND BEYOND: A CULTURAL HISTORY OF THE INFINITE. Eli Maor. Birkhauser, 1986. THE INFINITE. A. W. Moore. Routledge, 1990. INFINITY. Edited by A. W. Moore. Dartmouth, 1993. UNDERSTANDING THE INFINITE. Shaughan Lavine. Harvard University Press, 1994.

Diagonalization and Gödel’s Theorem

T

he diagonalization used in establishing Cantor’s theorem also lies at the heart of Austrian mathematician Kurt Gödel’s celebrated 1931 theorem. Seeing how offers a particularly perspicuous view of Gödel’s result. Gödel’s theorem deals with formal systems of arithmetic. By arithmetic I mean the theory of positive integers and the basic operations that apply to them, such as addition and multiplication. The theorem states that no single system of laws (axioms and rules) can be strong enough to prove all true statements of arithmetic without at the same time being so strong that it “proves” false ones, too. Equivalently, there is no single algorithm for distinguishing true arithmetical statements from false ones. Two definitions and two lemmas, or propositions, are needed to prove Gödel’s theorem. Proof of the lemmas is not possible within these confines, although each is fairly plausible. Definition 1: A set of positive integers is arithmetically defin-

able if it can be defined using standard arithmetical terminology. Examples are the set of squares, the set of primes and the set of positive integers less than, say, 821. Definition 2: A set of positive integers is decidable if there is an algorithm for determining whether any given positive integer belongs to the set. The same three sets above serve as examples. Lemma 1: There is an algorithmic way of pairing off positive integers with arithmetically definable sets. Lemma 2: Every decidable set is arithmetically definable. Given lemma 1, diagonalization yields a set of positive integers that is not arithmetically definable. Call this set D. Now suppose, contrary to Gödel’s theorem, there is an algorithm for distinguishing between true arithmetical statements and false ones. Then D, by virtue of its construction, is decidable. But given lemma 2, this proposition contradicts the fact that D is not arithmetically definable. So Gödel’s theorem must hold after all. Q.E.D.

24 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

DECEMBER 2003 COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

JARED SCHNEIDMAN DESIGN

SUBSETS

. . .

on whether R can belong to itself. If it does, by definition it does not belong to R. If it does not, it satisfies the condition for membership to R and so does belong to it. In any view of sets, there is something dubious about R. In Cantor’s view, according to which no set belongs to itself, R, if it existed, would be the set of all sets. This argument makes Cantor’s picture, and the rejection of R that goes with it, appear more reasonable. But is the picture not strikingly Aristotelian? Notice the temporal metaphor. Sets are depicted as coming into being “after” their members—in such a way that there are always more to come. Their collective infinitude, as opposed to the infinitude of any one of them, is potential, not actual. Moreover, is it not this collective infinitude that has best claim to the title? People do ordinarily define the infinite as that which is endless, unlimited, unsurveyable and immeasurable. Few would admit that the technical definition of an infinite set expresses their intuitive understanding of the concept. But given Cantor’s picture, endlessness, unlimitedness, unsurveyability and immeasurability more properly apply to the entire hierarchy than to any of the particular sets within it. In some ways, then, Cantor showed that the set of positive integers, for example, is “really” finite and that what is “really” infinite is something way beyond that. (He himself was not averse to talking in these terms.) Ironically, his work seems to have lent considerable substance to the Aristotelian orthodoxy that “real” infinitude can never be actual. Some scholars have objected to my suggestion that, in Cantor’s conception, the set of positive integers is “really” finite. They complain that this assertion is at variance not only with standard mathematical terminology but also, contrary to what I seem to

Originally published in November 1997

Fermat’s Last Stand His most notorious theorem baffled the greatest minds for more than three centuries. But after 10 years of work, one mathematician cracked it by Simon Singh and Kenneth A. Ribet

T

his past June, 500 mathematicians gathered in the Great Hall of Göttingen University in Germany to watch Andrew J. Wiles of Princeton University collect the prestigious Wolfskehl Prize. The reward— established in 1908 for whoever proved Pierre de Fermat’s famed last theorem— was originally worth $2 million (in today’s dollars). By the summer of 1997, hyperinflation and the devaluation of the mark had reduced it to a mere $50,000. But no one cared. For Wiles, proving Fermat’s 17th-century conundrum had realized a childhood dream and ended a decade of intense effort. For the assembled guests, Wiles’s proof promised to revolutionize the future of mathematics. Indeed, to complete his 100-page calculation, Wiles needed to draw on and further develop many modern ideas in mathematics. In particular, he had to tackle the Shimura-Taniyama conjecture, an important 20th-century insight into both algebraic geometry and complex analysis. In doing so, Wiles forged a link between these major branches of mathematics. Henceforth, insights from either field are certain to inspire new results in the other. Moreover, now that this bridge has been built, other connections between distant mathematical realms may emerge. The Prince of Amateurs

P

ierre de Fermat was born on August 20, 1601, in Beaumont-de-Lomagne,

25 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

a small town in southwest France. He pursued a career in local government and the judiciary. To ensure impartiality, judges were discouraged from socializing, and so each evening Fermat would retreat to his study and concentrate on his hobby, mathematics. Although an amateur, Fermat was highly accomplished and was largely responsible for probability theory and the foundations of calculus. Isaac Newton, the father of modern calculus, stated that he had based his work on “Monsieur Fermat’s method of drawing tangents.” Above all, Fermat was a master of number theory—the study of whole numbers and their relationships. He would often write to other mathematicians about his work on a particular problem and ask if they had the ingenuity to match his solution. These challenges, and the fact that he would never reveal his own calculations, caused others a great deal of frustration. René Descartes, perhaps most noted for inventing coordinate geometry, called Fermat a braggart, and the English mathematician John Wallis once referred to him as “that damned Frenchman.” Fermat penned his most famous challenge, his so-called last theorem, while studying the ancient Greek mathematical text Arithmetica, by Diophantus of Alexandria. The book discussed positive whole-number solutions to the equation a2 + b2 = c2, Pythagoras’s formula describing the relation between the sides of a right triangle. This equation has COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

infinitely many sets of integer solutions, such as a = 3, b = 4, c = 5, which are known as Pythagorean triples. Fermat took the formula one step further and concluded that there are no nontrivial solutions for a whole family of similar equations, a n + b n = c n, where n represents any whole number greater than 2. It seems remarkable that although there are infinitely many Pythagorean triples, there are no Fermat triples. Even so, Fermat believed he could support his claim with a rigorous proof. In the margin of Arithmetica, the mischievous genius jotted a comment that taunted generations of mathematicians: “I have a truly marvelous demonstration of this proposition, which this margin is too narrow to contain.” Fermat made many such infuriating notes, and after his death his son published an edition of Arithmetica that included these teases. All the theorems were proved, one by one, until only Fermat’s last remained. Numerous mathematicians battled the last theorem and failed. In 1742 Leonhard Euler, the greatest number theorist of the 18th century, became so frustrated by his inability to prove the last theorem that he asked a friend to search Fermat’s house in case some vital scrap of paper was left behind. In the 19th century Sophie Germain—who, because of prejudice against women mathematicians, pursued her studies under the name of Monsieur Leblanc—made the first significant breakthrough. Germain proved a general theorem that DECEMBER 2003

went a long way toward solving Fermat’s equation for values of n that are prime numbers greater than 2 and for which 2n + 1 is also prime. (Recall that a prime number is divisible only by 1 and itself.) But a complete proof for these exponents, or any others, remained out of her reach. At the start of the 20th century Paul Wolfskehl, a German industrialist, bequeathed 100,000 marks to whoever could meet Fermat’s challenge. According to some historians, Wolfskehl was at one time almost at the point of suicide, but he became so obsessed with trying to prove the last theorem that his death wish disappeared. In light of what had happened, Wolfskehl rewrote his will. The prize was his way of repaying a debt to the puzzle that saved his life. Ironically, just as the Wolfskehl Prize was encouraging enthusiastic amateurs to attempt a proof, professional mathematicians were losing hope. When the great German logician David Hilbert was asked why he never attempted a proof of Fermat’s last theorem, he replied, “Before beginning I should have to put in three years of intensive study, and I haven’t that much time to squander on a probable failure.” The problem still held a special place in the hearts of number theorists, but they regarded Fermat’s last theorem in the same way that chemists regarded alchemy. It was a foolish romantic dream from a past age. The Childhood Dream

C

hildren, of course, love romantic dreams. And in 1963, at age 10, Wiles became enamored with Fermat’s last theorem. He read about it in his local library in Cambridge, England, and promised himself that he would find a proof. His schoolteachers discouraged him from wasting time on the impossible. His college lecturers also tried to dissuade him. Eventually his graduate supervisor at the University of Cambridge steered him toward more mainstream mathematics, namely into the fruitful research area surrounding objects called elliptic curves. The ancient Greeks originally studied elliptic curves, and they appear in Arithmetica. Little did Wiles know that this training would lead him back to Fermat’s last theorem. Elliptic curves are not ellipses. Instead they are named as such because they are described by cubic equations, like those used for calculating the perimeter of an 26 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

ellipse. In general, cubic equations for elliptical curves take the form y2 = x 3 + ax 2 + bx + c, where a, b and c are whole numbers that satisfy some simple conditions. Such equations are said to be of degree 3, because the highest exponent they contain is a cube. Number theorists regularly try to ascertain the number of so-called rational solutions, those that are whole numbers or fractions, for various equations. Linear or quadratic equations, of degree 1 and 2, respectively, have either no rational solutions or infinitely many, and it is simple to decide which is the case. For complicated equations, typically of degree 4 or higher, the number of solutions is always finite—a fact called Mordell’s conjecture, which the German mathematician Gerd Faltings proved in 1983. But elliptic curves present a unique challenge. They may have a finite or infinite number of solutions, and there is no easy way of telling. To simplify problems concerning elliptic curves, mathematicians often reexamine them using modular arithmetic. They divide x and y in the cubic equation by a prime number p and keep only the remainder. This modified version of the equation is its “mod p” equivalent. Next, they repeat these divisions with another prime number, then another, and as they go, they note the number of solutions for each prime modulus. Eventually these calculations generate a series of simpler problems that are analogous to the original. The great advantage of modular arithmetic is that the maximum values of x and y are effectively limited to p, and so the problem is reduced to something finite. To grasp some understanding of the original infinite problem, mathematicians observe how the number of solutions changes as p varies. And using that information, they generate a so-called L-series for the elliptic curve. In essence, an L-series is an infinite series in powers, where the value of the coefficient for each pth power is determined by the number of solutions in modulo p. In fact, other mathematical objects, called modular forms, also have L-series. Modular forms should not be confused with modular arithmetic. They are a certain kind of function that deals with complex numbers of the form (x + iy), where x and y are real numbers, and i is the imaginary number (equal to the square root of –1). What makes modular forms special is COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

that one can transform a complex number in many ways, and yet the function yields virtually the same result. In this respect, modular forms are quite remarkable. Trigonometric functions are similar inasmuch as an angle, q, can be transformed by adding π, and yet the answer is constant: sin q = sin (q + π). This property is termed symmetry, and trigonometric functions display it to a limited extent. In contrast, modular forms exhibit an immense level of symmetry. So much so that when the French polymath Henri Poincaré discovered the first modular forms in the late 19th century, he struggled to come to terms with their symmetry. He described to his colleagues how every day for two weeks he would wake up and search for an error in his calculations. On the 15th day he finally gave up, accepting that modular forms are symmetrical in the extreme. A decade or so before Wiles learned about Fermat, two young Japanese mathematicians, Goro Shimura and Yutaka Taniyama, developed an idea involving modular forms that would ultimately serve as a cornerstone in Wiles’s proof. They believed that modular forms and elliptic curves were fundamentally related—even though elliptic curves apparently belonged to a totally different area of mathematics. In particular, because modular forms have an L-series— although derived by a different prescription than that for elliptic curves—the two men proposed that every elliptic curve could be paired with a modular form, such that the two L-series would match. Shimura and Taniyama knew that if they were right, the consequences would be extraordinary. First, mathematicians generally know more about the L-series of a modular form than that of an elliptic curve. Hence, it would be unnecessary to compile the L-series for an elliptic curve, because it would be identical to that of the corresponding modular form. More generally, building such a bridge between two hitherto unrelated branches of mathematics could benefit both: potentially each discipline could become enriched by knowledge already gathered in the other. The Shimura-Taniyama conjecture, as it was formulated by Shimura in the early 1960s, states that every elliptic curve can be paired with a modular form; in other words, all elliptic curves are modular. Even though no one could find a way to prove it, as the decades DECEMBER 2003

passed the hypothesis became increasingly influential. By the 1970s, for instance, mathematicians would often assume that the Shimura-Taniyama conjecture was true and then derive some new result from it. In due course, many major findings came to rely on the conjecture, although few scholars expected it would be proved in this century. Trag-

power. So a proof that the discriminant of an elliptic curve can never be an nth power would contain, implicitly, a proof of Fermat’s last theorem. Frey saw no way to construct that proof. He did, however, suspect that an elliptic curve whose discriminant was a perfect nth power—if it existed—could not be modular. In other words, such an elliptic

This special form of addition can be applied to any pair of points within the infinite set of all points on an elliptic curve, but this operation is particularly interesting because there are finite sets of points having the crucial property that the sum of any two points in the set is again in the set. These finite sets of points form a group: a set of points that

For seven years, Wiles worked in complete secrecy. Not only did he want to avoid the pressure of public attention, but he hoped to keep others from copying his ideas. ically, one of the men who inspired it did not live to see its ultimate importance. On November 17, 1958, Yutaka Taniyama committed suicide. The Missing Link

I

n the fall of 1984, at a symposium in Oberwolfach, Germany, Gerhard Frey of the University of Saarland gave a lecture that hinted at a new strategy for attacking Fermat’s last theorem. The theorem asserts that Fermat’s equation has no positive whole-number solutions. To test a statement of this type, mathematicians frequently assume that it is false and then explore the consequences. To say that Fermat’s last theorem is false is to say that there are two perfect nth powers whose sum is a third nth power. Frey’s idea proceeded as follows: Suppose that A and B are perfect nth powers of two numbers such that A + B is again an nth power—that is, they are a solution to Fermat’s equation. A and B can then be used as coefficients in a special elliptic curve: y2 = x(x – A)(x + B). A quantity that is routinely calculated whenever one studies elliptic curves is the “discriminant” of the elliptic curve, A2B2(A + B)2. Because A and B are solutions to the Fermat equation, the discriminant is a perfect nth power. The crucial point in Frey’s tactic is that if Fermat’s last theorem is false, then whole-number solutions such as A and B can be used to construct an elliptic curve whose discriminant is a perfect nth 27 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

curve would defy the Shimura-Taniyama conjecture. Running the argument backwards, Frey pointed out that if someone proved that the ShimuraTaniyama conjecture is true and that the elliptic equation y2 = x(x – A)(x + B) is not modular, then they would have shown that the elliptic equation cannot exist. In that case, the solution to Fermat’s equation cannot exist, and Fermat’s last theorem is proved true. Many mathematicians explored this link between Fermat and Shimura-Taniyama. Their first goal was to show that the Frey elliptic curve, y2 = x(x – A)(x + B), was in fact not modular. Jean-Pierre Serre of the College of France and Barry Mazur of Harvard University made important contributions in this direction. And in June 1986 one of us (Ribet) at last constructed a complete proof of the assertion. It is not possible to describe the full argument in this article, but we will give a few hints. To begin, Ribet’s proof depends on a geometric method for “adding” two points on an elliptic curve. Visually, the idea is that if you project a line through a pair of distinct solutions, P1 and P2, the line cuts the curve at a third point, which we might provisionally call the sum of P1 and P2. A slightly more complicated but more valuable version of this addition is as follows: first add two points and derive a new point, P3, as already described, and then reflect this point through the x axis to get the final sum, Q. COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

obeys a handful of simple axioms. It turns out that if the elliptic curve is modular, so are the points in each finite group of the elliptic curve. What Ribet proved is that a specific finite group of Frey’s curve cannot be modular, ruling out the modularity of the whole curve. For three and half centuries, the last theorem had been an isolated problem, a curious and impossible riddle on the edge of mathematics. In 1986 Ribet, building on Frey’s work, had brought it center stage. It was possible to prove Fermat’s last theorem by proving the Shimura-Taniyama conjecture. Wiles, who was by now a professor at Princeton, wasted no time. For seven years, he worked in complete secrecy. Not only did he want to avoid the pressure of public attention, but he hoped to keep others from copying his ideas. During this period, only his wife learned of his obsession—on their honeymoon. Seven Years of Secrecy

W

iles had to pull together many of the major findings of 20th-century number theory. When those ideas were inadequate, he was forced to create other tools and techniques. He describes his experience of doing mathematics as a journey through a dark, unexplored mansion: “You enter the first room of the mansion, and it’s completely dark. You stumble around bumping into the furniture, but gradually you learn where each piece of furniture is. DECEMBER 2003

Finally, after six months or so, you find the light switch. You turn it on, and suddenly it’s all illuminated. You can see exactly where you were. Then you move into the next room and spend another six months in the dark. So each of these breakthroughs, while sometimes they’re momentary, sometimes over a period of a day or two, they are the culmination of, and couldn’t exist without, the many months of stumbling around in the dark that precede them.” As it turned out, Wiles did not have to prove the full Shimura-Taniyama conjecture. Instead he had to show only that a particular subset of elliptic curves— one that would include the hypothetical elliptic curve Frey proposed, should it exist—is modular. It wasn’t really much of a simplification. This subset is still infinite in size and includes the majority of interesting cases. Wiles’s strategy used the same techniques employed by Ribet, plus many more. And as with Ribet’s argument, it is possible to give only a hint of the main points involved. The difficulty was to show that every elliptic curve in Wiles’s subset is modular. To do so, Wiles exploited the group property of points on the elliptic curves and applied a theorem of Robert P. Langlands of the Institute for Advanced Study in Princeton, N.J., and Jerrold Tunnell of Rutgers University. The theorem shows, for each elliptic curve in Wiles’s set, that a specific group of points inside the elliptic curve is modular. This requirement is necessary but not sufficient to demonstrate that the elliptic curve as a whole is modular. The group in question has only nine elements, so one might imagine that its modularity represents an extremely small first step toward complete modularity. To close this gap, Wiles wanted to examine increasingly larger groups, stepping from groups of size 9 to 9 2, or

81, then to 93, or 729, and so on. If he could reach an infinitely large group and prove that it, too, is modular, that would be equivalent to proving that the entire curve is modular. Wiles accomplished this task via a process loosely based on induction. He had to show that if one group was modular, then so must be the next larger group. This approach is similar to toppling dominoes: to knock down an infinite number of dominoes, one merely has to ensure that knocking down any one domino will always topple the next. Eventually Wiles felt confident that his proof was complete, and on June 23, 1993, he announced his result at a conference at the Isaac Newton Mathematical Sciences Institute in Cambridge. His secret research program had been a success, and the mathematical community and the world’s press were surprised and delighted by his proof. The front page of the New York Times exclaimed, “At Last, Shout of ‘Eureka!’ in Age-Old Math Mystery.” As the media circus intensified, the official peer-review process began. Almost immediately, Nicholas M. Katz of Princeton uncovered a fundamental and devastating flaw in one stage of Wiles’s argument. In his induction process, Wiles had borrowed a method from Victor A. Kolyvagin of Johns Hopkins University and Matthias Flach of the California Institute of Technology to show that the group is modular. But it now seemed that this method could not be relied on in this particular instance. Wiles’s childhood dream had turned into a nightmare. Finding the Fix

F

or the next 14 months, Wiles hid himself away, discussing the error only with his former student Richard

Taylor. Together they wrestled with the problem, trying to patch up the method Wiles had already used and applying other tools that he had previously rejected. They were at the point of admitting defeat and releasing the flawed proof so that others could try to correct it, when, on September 19, 1994, they found the vital fix. Many years earlier Wiles had considered using an alternative approach based on so-called Iwasawa theory, but it floundered, and he abandoned it. Now he realized that what was causing the Kolyvagin-Flach method to fail was exactly what would make the Iwasawa theory approach succeed. Wiles recalls his reaction to the discovery: “It was so indescribably beautiful; it was so simple and so elegant. The first night I went back home and slept on it. I checked through it again the next morning, and I went down and told my wife, ‘I’ve got it. I think I’ve found it.’ And it was so unexpected that she thought I was talking about a children’s toy or something, and she said, ‘Got what?’ I said, ‘I’ve fixed my proof. I’ve got it.’” For Wiles, the award of the Wolfskehl Prize marks the end of an obsession that lasted more than 30 years: “Having solved this problem, there’s certainly a sense of freedom. I was so obsessed by this problem that for eight years I was thinking about it all of the time—when I woke up in the morning to when I went to sleep at night. That particular odyssey is now over. My mind is at rest.” For other mathematicians, though, major questions remain. In particular, all agree that Wiles’s proof is far too complicated and modern to be the one that Fermat had in mind when he wrote his marginal note. Either Fermat was mistaken, and his proof, if it existed, was flawed, or a simple and cunning proof awaits discovery. SA

The Authors

Further Reading

SIMON SINGH and KENNETH A. RIBET share a keen interest in Fermat’s last theorem. Singh is a particle physicist turned television science journalist, who wrote Fermat’s Enigma and co-produced a documentary on the subject. Ribet is a professor of mathematics at the University of California, Berkeley, where his work focuses on number theory and arithmetic algebraic geometry. For his proof that the Shimura-Taniyama conjecture implies Fermat’s last theorem, Ribet and his colleague Abbas Bahri won the first Prix Fermat.

Yutaka Taniyama and His Time: Very Personal Recollections from Shimura. Goro Shimura in Bulletin of the London Mathematical Society, Vol. 21, pages 186–196; 1989. From the Taniyama-Shimura Conjecture to Fermat’s Last Theorem. Kenneth A. Ribet in Annales de la Faculté des Sciences de L’Université de Toulouse, Vol. 11, No. 1, pages 115–139; 1990. Modular Elliptic Curves and Fermat’s Last Theorem. Andrew Wiles in Annals of Mathematics, Vol. 141, No. 3, pages 443–551; May 1995. Ring Theoretic Properties of Certain Hecke Algebras. Richard Taylor and Andrew Wiles in Annals of Mathematics, Vol. 141, No. 3, pages 553–572; May 1995. Notes on Fermat’s Last Theorem. A. J. van der Poorten. Wiley Interscience, 1996. Fermat’s Enigma. Simon Singh. Walker and Company, 1997.

28 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DECEMBER 2003

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Originally published in May 1998

Japanese Temple Geometry

During Japan’s period of national seclusion (1639–1854), native mathematics thrived, as evidenced in sangaku—wooden tablets engraved with geometry problems hung under the roofs of shrines and temples by Tony Rothman, with the cooperation of Hidetoshi Fukagawa

BRYAN CHRISTIE, AFTER TOSHIHISA IWASAKI

O

f the world’s countless customs and traditions, perhaps none is as elegant, nor as beautiful, as the tradition of sangaku, Japanese temple geometry. From 1639 to 1854, Japan lived in strict, self-imposed isolation from the West. Access to all forms of occidental culture was suppressed, and the influx of Western scientific ideas was effectively curtailed. During this period of seclusion, a kind of native mathematics flourished. Devotees of math, evidently samurai, merchants and farmers, would solve a wide variety of geometry problems, inscribe their efforts in delicately colored wooden tablets and hang the works under the roofs of religious buildings. These sangaku, a word that literally means mathematical tablet, may have been acts of homage—a thanks to a guiding spirit— or they may have been brazen challenges to other worshipers: Solve this one if you can! For the most part, sangaku deal with ordinary Euclidean geometry. But the problems are strikingly different from those found in a typical high school geometry course. Circles and ellipses play a far more prominent role than in Western problems: circles within ellipses, ellipses within circles. Some of the exercises are quite simple and could be solved by first-year students. Others are nearly

impossible, and modern geometers invariably tackle them with advanced methods, including calculus and affine transformations. Although most of the problems would be classified today as recreational or educational mathematics, a few predate known Western results, such as the Malfatti theorem, the Casey theorem and the Soddy hexlet theorem. One problem reproduces the Descartes circle theorem. Many of the tablets are exceptionally beautiful and can be regarded as works of art. Pleasing the Kami

I

t is natural to wonder who created the sangaku and when, but it is easier to ask such questions than to answer them. The custom of hanging tablets at shrines was established in Japan centuries before sangaku came into existence. Shintoism, Japan’s native religion, is populated by “eight hundred myriads of gods,” the kami. Because the kami, it was said, love horses, those worshipers who could not present a living horse as an offering to the shrine might instead give a likeness drawn on wood. As a result, many tablets dating from the 15th century and earlier depict horses. Of the sangaku themselves, the oldest surviving tablet has been found in Tochigi Prefecture and dates from 1683.

SANGAKU PROBLEMS typically involve multitudes of circles within circles or of spheres within other figures. This problem is from a sangaku, or mathematical wooden tablet, dated 1788 in Tokyo Prefecture. It asks for the radius of the nth largest blue circle in terms of r, the radius of the green circle. Note that the red circles are identical, each with radius r/2. (Hint: The radius of the fifth blue circle is r/95.) The original solution to this problem deploys the Japanese equivalent of the Descartes circle theorem. (The answer can be found on page 35.) 30 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

Another tablet, from Kyoto, is dated 1686, and a third is from 1691. The 19th-century travel diary of the mathematician Kazu Yamaguchi refers to an even earlier tablet—now lost—dated 1668. So historians guess that the custom first arose in the second half of the 17th century. In 1789 the first collection containing typical sangaku problems was published. Other collections followed throughout the 18th and 19th centuries. These books were either handwritten or printed with wooden blocks and are remarkably beautiful. Today more than 880 tablets survive, with references to hundreds of others in the various collections. From a survey of the extant sangaku, the tablets seem to have been distributed fairly uniformly throughout Japan, in both rural and urban districts, with about twice as many found in Shinto shrines as in Buddhist temples. Most of the surviving sangaku contain more than one theorem and are frequently brightly colored. The proof of the theorem is usually not given, only the result. Other information typically includes the name of the presenter and the date. Not all the problems deal solely with geometry. Some ask for the volumes of various solids and thus require calculus. (This point raises the interesting question of what techniques the practitioners brought into play; some speculations will be offered in the following discussion.) Other tablets contain Diophantine problems—that is, algebraic equations requiring solutions in integers. In modern times the sangaku have been largely forgotten but for a few DECEMBER 2003

Typical Sangaku Problems*

Here is a simple problem that has survived on an 1824 tablet in Gumma Prefecture. The orange and blue circles touch each other at one point and are tangent to the same line. The small red circle touches both of the larger circles and is also tangent to the same line. How are the radii of the three circles related?

P

This striking problem was written in 1912 on a tablet extant in Miyagi Prefecture; the date of the problem itself is unknown. At a point P on an ellipse, draw the normal PQ such that it intersects the other side. Find the least value of PQ. At first glance, the problem appears to be trivial: the minimum PQ is the minor axis of the ellipse. Indeed, this is the solution if b < a ≤ √2b, where a and b are the major and minor axes, respectively; however, the tablet does not give this solution but another, if 2b2 < a2. Q

BRYAN CHRISTIE

This beautiful problem, which requires no more than high school geometry to solve, is written on a tablet dated 1913 in Miyagi Prefecture. Three orange squares are drawn as shown in the large, green right triangle. How are the radii of the three blue circles related?

31 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DECEMBER 2003

In this problem, from an 1803 sangaku found in Gumma Prefecture, the base of an isosceles triangle sits on a diameter of the large green circle. This diameter also bisects the red circle, which is inscribed so that it just touches the inside of the green circle and one vertex of the triangle, as shown. The blue circle is inscribed so that it touches the outsides of both the red circle and the triangle, as well as the inside of the green circle. A line segment connects the center of the blue circle and the intersection point between the red circle and the triangle. Show that this line segment is perpendicular to the drawn diameter of the green circle.

devotees of traditional Japanese mathematics. Among them is Hidetoshi Fukagawa, a high school teacher in Aichi Prefecture, roughly halfway between Tokyo and Osaka. About 30 years ago Fukagawa decided to study the history of Japanese mathematics in hopes of finding better ways to teach his courses. A mention of the math tablets in an old library book greatly astonished him, for he had never heard of such a thing. Since then, Fukagawa, who holds a Ph.D. in mathematics, has traveled widely in Japan to study the tablets and has amassed a collection of books dealing not only with sangaku but with the general field of traditional Japanese mathematics. To carry out his research, Fukagawa had to teach himself Kambun, an archaic form of Japanese that is closely related to Chinese. Kambun is the Japanese equivalent of Latin; during the Edo period (1603–1867), scientific works were written in this language, and only a few people in modern Japan are able to read it fluently. As new tablets have been discovered, Fukagawa has been called in to decipher them. In 1989 Fukagawa, along with Daniel Pedoe, published the first collection of sangaku in English. Most of the geometry problems accompanying this article were drawn from that collection. Wasan versus Yosan

A This problem comes from an 1874 tablet in Gumma Prefecture. A large blue circle lies within a square. Four smaller orange circles, each with a different radius, touch the blue circle as well as the adjacent sides of the square. What is the relation between the radii of the four small circles and the length of the side of the square? (Hint: The problem can be solved by applying the Casey theorem, which describes the relation between four circles that are tangent to a fifth circle or to a straight line.)

*Answers are on page 35. 32 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

lthough the origin of the sangaku cannot be pinpointed, it can be localized. There is a word in Japanese, wasan, that is used to refer to native Japanese mathematics. Wasan is meant to stand in opposition to yosan, or Western mathematics. To understand how wasan came into existence—and with it the unusual sangaku problems— one must first appreciate the peculiar history of Japanese mathematics. Of the earliest times, very little is definitely known about mathematics in Japan, except that a system of exponential notation, similar to that employed by Archimedes in the Sand Reckoner, had been developed. More concrete information dates only from the mid-sixth century A.D., when Buddhism—and, with it, Chinese mathematics—made its way to Japan. Judging from the works that were taught at official schools at the start of the eighth century, historians infer that Japan had imported the great Chinese classics on arithmetic, algebra and geometry. According to tradition, the earliest of

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

these is the Chou-pei Suan-ching, which contains an example of the Pythagorean theorem and the diagram commonly used to prove it. This part of the tome is at least as old as the sixth century B.C. A more advanced state of knowledge is represented in the Chiu-chang Suanshu, considered the most influential of Chinese books on mathematics. The Chiu-chang describes methods for finding the areas of triangles, quadrilaterals, circles and other figures. It also contains simple word problems of the type that torment many high school students today: “If five oxen and two sheep cost eight taels of gold, and two oxen and eight sheep cost eight taels, what is the price of each animal?” The dates of the Chiu-chang are also uncertain, but most of it was probably composed by the third century B.C. If this information is correct, the Chiu-chang contains perhaps the first known mention of negative numbers and an early statement of the quadratic equation. (According to some historians, the ancient Egyptians had begun studying quadratic equations centuries before, prior to 2000 B.C.) Despite the influx of Chinese learning, mathematics did not then take root in Japan. Instead the country entered a dark age, roughly contemporaneous with that of Western Europe. In the West, church and monastery became the centers of learning; in Japan, Buddhist temples served the same function, although mathematics does not seem to have played much of a role. By some accounts, during the Ashikaga shogunate (1338–1573) there could hardly be found in all Japan a person versed in the art of division. It is not until the opening of the 17th century that definite historical records exist of any Japanese mathematicians. The first of these is Kambei Mori, who prospered around the year 1600. Although only one of Mori’s works—a booklet—survives, he is known to have been instrumental in developing arithmetical calculations on the soroban, or Japanese abacus, and in popularizing it throughout the country. The oldest substantial Japanese work on mathematics actually extant belongs to Mori’s pupil Koyu Yoshida (1598– 1672). The book, entitled Jinko-ki (literally, “small and large numbers”), was published in 1627 and also concerns operations on the soroban. Jinko-ki was so influential that the name of the work often was synonymous with arithmetic. Because of the book’s influence, compuDECEMBER 2003

From a sangaku dated 1825, this problem was probably solved by using the enri, or the Japanese circle principle. A cylinder intersects a sphere so that the outside of the cylinder is tangent to the inside of the sphere. What is the surface area of the part of the cylinder contained inside the sphere? (The inset shows a three-dimensional view of the problem.)

This problem is from an 1822 tablet in Kanagawa Prefecture. It predates by more than a century a theorem of Frederick Soddy, the famous British chemist who, along with Ernest Rutherford, discovered transmutation of the elements. Two red spheres touch each other and also touch the inside of the large green sphere. A loop of smaller, different-size blue spheres circle the “neck” between the red spheres. Each blue sphere in the “necklace” touches its nearest neighbors, and they all touch both the red spheres and the green sphere. How many blue spheres must there be? Also, how are the radii of the blue spheres related? (The inset shows a three-dimensional view of the problem.)

BRYAN CHRISTIE

Hidetoshi Fukagawa was so fascinated with this problem, which dates from 1798, that he built a wooden model of it. Let a large sphere be surrounded by 30 small, identical spheres, each of which touches its four small-sphere neighbors as well as the large sphere. How is the radius of the large sphere related to that of the small spheres? (The inset shows a three-dimensional view of the problem.)

*Answers are on page 35. 33 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DECEMBER 2003

tation—as opposed to logic—became the most important concept in traditional Japanese mathematics. To the extent that it makes sense to credit anyone with the founding of wasan, that honor probably goes to Mori and Yoshida. A Brilliant Flowering

W

asan, though, was created not so much by a few individuals but by something much larger. In 1639 the ruling Tokugawa shogunate (during the Edo period), to strengthen its power and diminish challenges to its reign, decreed the official closing of Japan. During this time of sakoku, or national seclusion, the government banned foreign books and travel, persecuted Christians and forbade Portuguese and Spanish ships from coming ashore. Many of these strictures would remain for more than two centuries, until Commodore Matthew C. Perry, backed by a fleet of U.S. warships, forced the end of sakoku in 1854. Yet the isolationist policy was not entirely negative. Indeed, during the late 17th century, Japanese art and culture flowered so brilliantly that those years go by the name of Genroku, for “renaissance.” In that era, haiku developed into a fine art form; No and Kabuki theater reached the pinnacle of their development; ukiyo-e, or “floating world” pictures, originated; and tea ceremonies and flower arranging reached new heights. Neither was mathematics left behind, for Genroku was also the age of Kowa Seki. By popular accounts, Seki (1642– 1708) was Japan’s Isaac Newton or Gottfried Wilhelm Leibniz, although this reputation is difficult to substantiate. If the numbers of manuscripts attributed to him are correct, then most of his work has been lost. Still, there is no question that Seki left many disciples who were influential in the further development of Japanese mathematics. The first—and incontestable—achievement of Seki was his theory of determinants, which is more powerful than that of Leibniz and which antedates the German mathematician’s work by at least a decade. Another accomplishment, more relevant to temple geometry but of debatable origin, is the development of methods for solving high-degree equations. (Much traditional Japanese mathematics from that era involves equations to hundreds of degrees; one such equation is of the 1,458th degree.) Yet 34 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

a third accomplishment sometimes attributed to Seki, and one that might also bear on sangaku, is the development of the enri, or circle principle. The enri was quite similar to the method of exhaustion developed by Eudoxus and Archimedes in ancient Greece for computing the area of circles. The main difference was that Eudoxus and Archimedes used n-sided polygons to approximate the circle, whereas the enri divided the circle into n rectangles. Thus, the limiting procedure was somewhat different. Nevertheless, the enri represented a crude form of integral calculus that was later extended to other figures, including spheres and ellipses. A type of differential calculus was also developed around the same period. It is conceivable that the enri and similar techniques were brought to bear on sangaku. Today’s mathematicians would use modern calculus to solve these problems. Spheres within Ellipsoids

D

uring Seki’s lifetime, the first books employing the enri were published, and the first sangaku evidently made their appearance. The dates are almost certainly not coincidental; the followers of Yoshida and Seki must have influenced the development of wasan, and, in turn, wasan may have influenced them. Fukagawa believes that Seki encountered sangaku on his way to the shogunate castle, where he was officially employed as court mathematician, and that the tablets pushed him to further researches. A legend? Perhaps. But by the next century, books were being published that contained typical native Japanese problems: circles within triangles, spheres within pyramids, ellipsoids surrounding spheres. The problems found in these books do not differ in any important way from those found on the tablets, and it is difficult to avoid the conclusion that the peculiar flavor of all wasan problems—including the sangaku—is a direct result of the policy of national seclusion. But the question immediately arises: Was Japan’s isolation complete? It is certain that apart from the Dutch who were allowed to remain in Nagasaki Harbor on Kyushu, the southernmost island, all Western traders were banned. Equally clear is that the Japanese themselves were severely restricted. The mere act of traveling abroad was considered high treason, punishable by death. It appears safe to assume that if the isola-

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

tion was not complete, then it was most nearly so, and any foreign influence on Japanese mathematics would have been minimal. The situation began to change in the 19th century, when the wasan gradually became supplanted by yosan, a process that produced hybrid manuscripts written in Kambun with Western mathematical notations. And, after the opening of Japan by Commodore Perry and the subsequent collapse of the Tokugawa shogunate in 1867, the new government abandoned the study of native mathematics in favor of yosan. Some practitioners, however, continued to hang tablets well into the 20th century. A few sangaku even date from the current decade. But almost all the problems from this century are plagiarisms. The final and most intriguing question is, Who produced the sangaku? Were the theorems so beautifully drawn on wooden tablets the works of professional mathematicians or amateurs? The evidence is meager. Only a handful of sangaku are mentioned in the standard A History of Japanese Mathematics, by David E. Smith and Yoshio Mikami. They cite the 1789 collection Shimpeki Sampo, or Mathematical Problems Suspended before the Temple, which was published by Kagen Fujita, a professional mathematician. Smith and Mikami mention a tablet on which the following was appended after the solution: “Feudal district of Kakegawa in Enshu Province, third month of 1795, Sonobei Keichi Miyajima, pupil of Sadasuke Fujita of the School of Seki.” Mikami, in his Development of Mathematics in China and Japan, mentions the “Gion Temple Problem,” which was suspended at the Gion Temple in Kyoto by Enkyu Tsuda, pupil of Enri Nishimura. Furthermore, the tablets were written in the specialized language of Kambun, signifying the mark of an educated class of practitioners. From such scraps of information, it is tempting to conclude that the tablets were the work primarily of professional mathematicians and their students. Yet there are reasons to believe otherwise. Many of the problems are elementary and can be solved in a few lines; they are not the kind of work a professional mathematician would publish. Fukagawa has found a tablet from Mie Prefecture inscribed with the name of a merchant. Others have names of women and children—12 to 14 years of age. Most, according to Fukagawa, were DECEMBER 2003

created by the members of the highly educated samurai class. A few were probably done by farmers; Fukagawa recalls how about 10 years ago he visited the former cottage of mathematician Sen Sakuma (1819–1896), who taught wasan to the farmers in nearby villages in Fukushima Prefecture. Sakuma had about 2,000 students. Such instruction recalls the Edo period itself, when there were no colleges or universities in Japan. During that time, teaching was carried out at private schools or temples, where ordinary people would go to study reading, writing and the abacus. Because laypeople are more often drawn to problems of geometry than of algebra, it would not be surprising if the tablets were painted

with such artistic care specifically to attract nonmathematicians. The best answer, then, to the question of who created temple geometry seems to be: everybody. On learning of the sangaku, Fukagawa came to understand that, in those days, many of the Japanese loved and enjoyed math, as well as poetry and other art forms. It is pleasant to realize that some sangaku were the works of ordinary mathematics devotees, carried away by the beauty of geometry. Perhaps a village teacher, after spending the day with students, or a samurai warrior, after sharpening his sword, would retire to his study, light an oil lamp and lose the world to an intricate problem involving spheres and ellipsoids. Perhaps he would

spend days working on it in peaceful contemplation. After finally arriving at a solution, he might allow himself a short rest to savor the result of his hard labor. Convinced the proof was a worthy offering to his guiding spirits, he would have the theorem inscribed in wood, hang it in his local temple and begin to consider the next challenge. Visitors would notice the colorful tablet and admire its beauty. Many people would leave wondering how the author arrived at such a miraculous solution. Some might decide to give the problem a try or to study geometry so that the attempt could be made. A few might leave asking, “What if the problem were changed just so....” Something for us all to consider. SA

Answers to Sangaku Problems

U

nfortunately, because of space limitations the complete solutions to the problems could not be given here.

1)2

Answer: r/[(2n – + 14]. The original solution to this problem applies the Japanese version of the Descartes circle theorem several times. The answer given here was obtained by using the inversion method, which was unknown to the Japanese mathematicians of that era. Answer: 1/√r3 = 1/√r1 + 1/√r2 , where r1, r2 and r3 are the radii of the orange, blue and red circles, respectively. The problem can be solved by applying the Pythagorean theorem. Answer: PQ =

BRYAN CHRISTIE

Answer: If a is the length of the square’s side, and r1, r2, r3 and r4 are the radii of the upper right, upper left, lower left and lower right orange circles, respectively, then

√27 a2b2 3 (a2 + b2 ) /2

The problem can be solved by using analytic geometry to derive an equation for PQ and then taking the first derivative of the equation and setting it to zero to obtain the minimum value for PQ. It is not known whether the original authors resorted to calculus to solve this problem.

r22

Answer: = r1r3, where r1, r2 and r3 are the radii of the large, medium and small blue circles, respectively. (In other words, r2 is the geometric mean of r1 and r3.) The problem can be solved by first realizing that all the interior green triangles formed by the orange squares are similar. The original solution then looks at how the three squares are related. Answer: In the original solution to this problem, the author draws a line segment that goes through the center of the blue circle and is perpendicular to the drawn diameter of the green circle. The author assumes that this line segment is different from the line segment described in the statement of the problem on page 87. Thus, the two line segments should intersect the drawn diameter at different locations. The author then shows that the distance between those locations must necessarily be equal to zero—that is, that the two line segments are identical, thereby proving the perpendicularity.

a=

2(r1r3 – r2 r4) + √2(r1 – r2 )(r1 – r4)(r3 – r2 )(r3 – r4) r1 – r2 + r3 – r4 Answer: 16t √t(r – t), where r and t are the radii of the sphere and cylinder, respectively.

Answer: Six spheres. The Soddy hexlet theorem states that there must be six and only six blue spheres (thus the word “hexlet”). Interestingly, the theorem is true regardless of the position of the first blue sphere around the neck. Another intriguing result is that the radii of the different blue spheres in the “necklace” (t1 through t6 ) are related by 1/t1 + 1/t4 = 1/t2 + 1/t5 = 1/t3 + 1/t6. Answer: R = √5r, where R and r are the radii of the large and small spheres, respectively. The problem can be solved by realizing that the center of each small sphere lies on the midpoint of the edge of a regular dodecahedron, a 12-sided solid with pentagonal faces.

The Author

Further Reading

TONY ROTHMAN received his Ph.D. in 1981 from the Center for Relativity at the University of Texas at Austin. He did postdoctoral work at Oxford, Moscow and Cape Town, and he has taught at Harvard University. Rothman has published six books, most recently Instant Physics. His next book is Doubt and Certainty, with E.C.G. Sudarshan, to be published this fall by Helix Books/Addison-Wesley. He has also recently written a novel about nuclear fusion. Scientific American wishes to acknowledge the help of Hidetoshi Fukagawa in preparing this manuscript. Fukagawa received a Ph.D. in mathematics from the Bulgarian Academy of Science. He is a high school teacher in Aichi Prefecture, Japan.

A History of Japanese Mathematics. David E. Smith and Yoshio Mikami. Open Court Publishing Company, Chicago, 1914. (Also available on microfilm.) The Development of Mathematics in China and Japan. Second edition (reprint). Yoshio Mikami. Chelsea Publishing Company, New York, 1974. Japanese Temple Geometry Problems. H. Fukagawa and D. Pedoe. Charles Babbage Research Foundation, Winnipeg, Canada, 1989. Traditional Japanese Mathematics Problems from the 18th and 19th Centuries. H. Fukagawa and D. Sokolowsky. Science Culture Technology Publishing, Singapore (in press).

35 SCIENTIFIC AMERICAN EXCLUSIVE ONLINE ISSUE

COPYRIGHT 2003 SCIENTIFIC AMERICAN, INC.

DECEMBER 2003