The Mathematical Intelligencer encourages comments about the material in this issue. Letters to the editor should be sent to the editor-in-chief, Chandler Davis.
More About D o o m John Leslie's article "The Doomsday Argument" in the Spring 1992 Mathematical Intelligencer is somewhat informal about the numbers with which it deals, but this seems to represent it fairly: We contemplate the prospect D ("Doomsday") that humanity will go extinct before 2150 and will never have had more than 101~ or 1011 members; otherwise, A, it will spread through the galaxy and come to have had about 1015 (perhaps 1016) members. I grant, he says, that D may seem unlikely. Very well, let us assign it a low a priori probability, very low, say 1%. This leaves 99% probability for A. But now (ahem!) I, Leslie, observe that I live before 2150. H o w did this observation get made? Either A holds, and then the observation has conditional probability 10-15 (or 16); or D, which gives us conditional probability 10 -1~ By elementary Bayesianity, D now has 99.9% probability. May I suggest a refinement? Grant me the further observation--which only Leslie can make--that John Leslie is a real human being. Let us consider the possible cases A, D, and also S: there is only one real human being (J.L.), with 101~ 1 of us little green men disguised as humans. S may seem even more unlikely than D, so let us give it a really low a priori probability like 10-7 (i.e., 10-5%). But now Leslie's dates have, on S, a conditional probability of 1. So Bayes assures us that S is 99.999% probable, and we can all applaud Professor Leslie's discovery. Greenly.
John Leslie's article "The Doomsday Argument" in the Mathematical Intelligencer [3], expresses concern about the future of the human race, which certainly all responsible people will share. The evident danger of a man-made Big Crunch demands a broad discussion to give rise to political action. In this discussion, scientific arguments have a special weight, and consequently scientists have a special obligation to be critical and honest in their arguments. False results published with the pretension of scientific truth may cause severe harm--besides discrediting scientific methods in the public judgement. Mr. Leslie asks for the opinion of the readers of the Mathematical Intelligencer. Here is my answer: First of all, I am really glad that the Doomsday Argument is nothing but apocalyptical nonsense. Second, I feel angry that scientific journals of high reputation (not only the Mathematical Intelligencer) give room to publish such a spectacular result based on obvious misuse of mathematical methods. Third, I appreciate the article because of its educational value. It demonstrates that applying mathematics to real-world problems is a delicate art which needs competence and sane intuition. Why is the argument worthless? Leslie considers one event and two hypotheses, which I will call H, S, and L, with the following meanings: H: A (somehow selected) human being is living in the 1990s. S: The human race will end within a short time. L: The human race will continue for a long time. He applies Bayes's rule
John Isbell Department of Mathematics State University of New York Buffalo, NY 14214-3093 USA
P(SIH) =
P(HlS)P(S) P(HIS)P(S) + P(HIL)P(L ) '
making the essential assumption P(H[S) > P(H[L). THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3 Q1993 Springer-VeflagNew York 3
This would be correct if the human being in consideration had been randomly selected from an omnipotent spirit's urn containing the names of all people who ever lived and ever will live. But that is not the situation. The process of selecting a person is limited to living people. (Leslie refers to himself.) At the best, it could be extended to all people who ever lived. In any case, we get P(H]S) = P(H]L) and Bayes's rule gives P(S]H) = P(S). It is also intuitively clear that Bayes's rule cannot give any evidence for S or for L: John Leslie's or the reader's or my own existence in no w a y depends on the truth of S or L. So it cannot give any information on S or L. Moreover, even if L is true, there is no possibility of selecting a person living in the distant future and thereby getting evidence for the truth of hypothesis L. So Leslie's way of applying Bayes's rule will always indicate "Doom Soon", no matter which of the two hypotheses is actually true. By the way, w h y shouldn't we apply Leslie's argument to billions of people living in our age? The result would be terrifying! A reasonable description of the two cases considered by Leslie a near end of mankind or a long future for the human race---would be given by two (hypothetical) lists with the names of all people who ever lived and ever will live in chronological order. There would be a smaller list where our names would be found near the end, and a long list containing our names at its beginning. But both lists would be identical until the 1990s. Let us consider an analogy to the numerical example used by Leslie: Assume that my name is on a long list with 1,000,000 names and that there is a second list containing only the first 10 names of the long list. N o w somebody randomly chooses one of the lists and starts reading. If my name were found among the first 10 names I really would be surprised. Nevertheless, there would be no indication that the small list had been chosen. There is a moral in the story: Never believe in formal arguments if they are incompatible with your daily experiences or with your critical intuition! (If you feel that the mere fact of your existence cannot indicate a near end of mankind, you are right, no matter what kind of calculation some "experts" make.) Mr. Leslie already knows all the objections against the Doomsday Argument. So I don't believe that he will be converted by mine. Nevertheless, I tried to make my point of view very clear for two reasons: 1. The Doomsday Argument has been widely disseminated by publications in several scientific magazines and public talks. As the subject itself is serious and as the Doomsday Discussion finally found a podium in a first-class mathematics journal, it seems to be time for the mathematical community to react and, if possible, to stop the discussion. 2. The incompetent use of mathematical methods by the Doomsday Protagonists is not an isolated phenomenon. There are many spectacular examples of 4
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
the misuse of mathematics in different fields (politics, medicine, jurisprudence . . . . ) [2, 5, 6]. It is striking that the misuse of mathematics mainly occurs in the context of probabilistic and statistical problems. The recent discussion concerning the TV show "Let's Make a Deal" evoked by Marilyn vos Savant is another example of this fact [1, 7]. As more and more people apply mathematics in their professional lives, mathematical modeling should become part of mathematics education--as demanded in the NCTM Curriculum and Evaluation Standards for School Mathematics [4]. To teach modeling, welldesigned examples should be worked out and thoroughly discussed in the classroom. Sensitivity to the delicate relationship between formal mathematics and real-world problems can best be developed by realistic examples demonstrating the misuse of mathematics and its possible consequences. The Doomsday Argument could be such an example. So, in spite of all my objections, I would like to thank the editors of the Mathematical Intelligencer for the publication of an educational gem.
References 1. Gillman, Leonard, "The Car and the Goats," AmericanMathematical Monthly 99 (1992), 3-7. 2. Gray, Mary W., "Statistics and the Law," Mathematics Magazine 56 (1983), 67-81. 3. Leslie, John, "The Doomsday Argument," The Mathematical Intelligencer 14 2 (1992), 48-51. 4. Curriculum and Evaluation Standards for School Mathematics, National Council of Teachers of Mathematics, Reston, VA (1989). 5. Schrage, Georg, "Schwierigkeiten mit stochastischer Modellbildung," Journalfiir Mathematikdidaktik I (1981), 86-101. 6. Schrage, Georg, "Stochastische Trugschlfisse," Mathematica Didactica 3 (1984), 3-19. 7. vos Savant, Marilyn, "Ask Marilyn," Parade, (a) September 9, 1990; (b) December 2, 1990; (c) February 17, 1991.
George Schrage University of Dortmund Department of Mathematics 4600 Dortmund, Germany
In the Spring 1992 issue of the Mathematical Intelligencer, John Leslie expounded his Doomsday Argument, summarizing his earlier articles on the subject. The last of these earlier papers to which Dr. Leslie referred [2] was directly preceded by an article in which the Argument was critically analysed [1]. I would like to draw attention to the main points of this analysis, which in my opinion puts the Doomsday Argument in a proper perspective. The Doomsday Argument is an application of Bayesian reasoning. It is essential to note that (1) Bayes's rule gives
the relation between a priori and a posteriori probabilities (conditionalization on the evidence), but otherwise says nothing about what the values of the probabilities should be; (2) if one assigns probabilities in a consistent way, it makes no difference whether one takes into account all available information at once, or whether one first takes into account only part of the information, assigns probabilities to various hypotheses on that basis, and subsequently conditionalizes on the remainder of the information (via Bayes's rule). The a posteriori probability of the second procedure should equal the a priori probability if one takes all information into account at once (both are equal to the probability of H and E, with H the hypothesis considered and E the evidence). Further, if the Argument is to have any force at all, the two hypotheses considered (imminent doom and long survival of mankind, respectively) must not contain the information that I live now, in 1993. For if they do, there will be no change in probability if Bayes's rule is applied with this evidence (the probability of the evidence, namely, that I live in 1993, will be I on both hypotheses). Leslie's argument must presuppose that my position in time is completely uncertain in both hypotheses considered. J As said above, it should make no difference whether I judge the chances of survival of the human race at once on the basis of all available information, including the fact that I live now, in 1993 (which implies that any possible disaster ending the existence of mankind will not be before 1993), or whether I first forget about my position in time and conditionalize on that piece of information afterwards. Suppose that we, in our actual knowledge situation, estimate the chances for the survival of the human race as being roughly equal to the chances of imminent disaster. The foregoing implies that if we don't take our position in history into account, our a priori probability for the disaster hypothesis should be very much smaller than the probability we assign to the hypothesis that the human race will survive for a very long time (so that this difference in probabilities will subsequently disappear if we conditionalize on the evidence that we live in the 1990s). Is such a large difference in prior probabilities not irrational? Well, reflect on the strangeness of the situation to which these probabilities pertain: You know about the evolution of mankind until halfway through 1993, but you yourself could be alive anywhere in human history (you could turn out to be a caveman, for example). It is not so easy to assess the a priori probability that hypotheses would have for us in that strange knowledge situation! The safest thing to do is to follow the calculation sketched in the previous paragraph. But Bayes's rule can actually help us to get one step further. We can see the reasonableness of the difference in prior probabilities not only from the 'posterior side,' but also by considering an imaginable situation in which these probabilities arise as the result of earlier condition-
alization. Suppose that you don't know you are human (you have no idea about what kind of observer you are) and that you are unaware of your position in time. From this detached viewpoint, you consider two hypotheses: H1 (disaster for mankind a couple of million years after its beginning) a n d / / 2 (much longer survival of the human race). Assume you assign roughly equal initial probabilities to/-/1 and/-/2- There will be vastly more humans in the history of the universe according to H2 than according to/-/1. N o w you learn that you yourself are human. You apply Bayes's rule and conclude that//2 has become much more probable than t/1 because it is much more probable that you, a randomly chosen observer, are human on//2 than on//1. The two new probabilities of the hypotheses will be in proportion to the respective population numbers (you have taken the total number of observers in the universe to be the same very large number under both hypotheses--you don't have any information about the ratio humans/nonhumans). You are now in the initial situation discussed before: you know that you are human but are still unaware of your position in history. Subsequent conditionalization on the evidence that you live in the nineties will undo the result of the previous conditionalization and will make the probabilities for the two hypotheses roughly equal again (see [1] for a more extensive discussion). Of course, the foregoing observations do not prove anything absolute about the values of the probabilities of //1 and//2. It is a fundamental point that our probability judgements ultimately have to be based on something other than the application of Bayes's rule. It seems clear, however, that the mere fact that we are living in the 1990s does not constitute significant information about the future prospects of mankind.
References 1. D. Dieks, "Doomsday--or: The Dangers of Statistics," The Philosophical Quarterly 42 (1992), 78. 2. L. Leslie, "Doomsday Revisited," The Philosophical Quarterly 42 (1992), 85. Dennis Dieks Department of History and Foundations of Mathematics and Science University of Utrecht P.O. Box 80,000 Utrecht, The Netherlands
John Leslie Replies Brandon Carter's "doomsday argument" could work really well only if the world were deterministic, or at least such that any indeterminism was unlikely to affect how long the human race would last. You could then supposedly treat the humans spread out in time as if they were THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3,1993 5
balls in a gigantic urn. Only one ball is marked with your name. It turns out to be among the first hundred billion drawn from the urn. Simplifying, suppose that either one hundred billion are all there are in the urn (the human race reaches Doom in A.D. 2150, say, when one hundred billion humans have lived their lives) or else the number is a hundred thousand times larger (the race survives much longer and spreads through the galaxy). Bayes's Rule is that P(h, e ) - the probability of hypothesis h in view of evidence e - - equals
P(h)p(e, h) P(h)P(e, h) + P(not h)P(e, not h)' where P(h) was one's initial guess for the probability of h. It tells one how to revise one's prior confidence in hypotheses, in the light of items of evidence. If you started off fairly confident that the human race was fated to colonize the galaxy and that every human before 2150 was in the first 0.001% of all humans to be born, then reflecting that you are before 2150 could, if Bayes's Rule applies here, very greatly reduce your confidence. Does the Rule apply, though? Or is Carter's reasoning as weak as Isbell, Schrage, and Dieks suggest? Isbell's letter is so mathematically unsound as to be disappointing even as a parody. His first paragraph suggests 10l~ humans if Doom Soon, that is, by A.D. 2150, and 1015 if Doom Delayed. He then calculates the conditional probability of John Leslie's being before 2150, on the hypothesis of Doom Delayed, as 10 -15 . In fact, though, it is 10 -15 multiplied by 101~ or 10 -5 (since 10l~ of the 1015 humans are before 2150). He next gives the conditional probability on the hypothesis of Doom Soon as 10-1~ In fact it is 1, obviously: Granted the fact of Doom before 2150, it is certain that Leslie is before 2150. The next paragraph is equally faulty. It rotates around the idea that if all except Leslie were little green men in disguise, then it would be certain that Leslie, being a real human, was before 2150, for all real humans would be Leslie: The conditional probability, on the little green men hypothesis, of Leslie's being before 2150 must thus be 1, Isbell suggests. Now, it is doubtful whether he is correct, for doesn't his argument demand the further premise that Leslie, or all humans, must live before 2150? But even if he were correct, Bayesian calculation would not then yield the 99.999% which he gives for the probability that Leslie is the only real human. It would not yield it even on his fantastic supposition that there had been a fully one-in-ten-million chance, a prior probability of 10-7, that Leslie was the only real human. For if his figure of 10l~ persons (10 l ~ 1 of whom might be little green men in disguise) is the appropriate one, then what appears to be the human race will end by 2150 since (see his first paragraph) 10l~ is his Doom Soon figure. The conditional probability of Leslie's living before 2150 must then also be I whether or not the others are little green men. Bayesian calculation thus gives, as one might expect, a posterior probability of 10 -7, exactly the same 6 mE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3,1993
as the prior probability. That looks quite a bit different from 99.999%. But what if the appropriate figure for the number of persons is instead 1015? Matters are only a little improved. For now the probability that Leslie finds himself before 2150 is the 10 -5 that I mentioned earlier. Well, 10 -7 • 1 (10 -7 x 1) + [(1 - 10 -7) • 10 -5] is still equal only to about 10 -2, which is once again a long way from 99.999%. Substituting 10 -5 for I has not helped much. How about Schrage? So far as I can tell, Schrage's story of the two lists of names, one long and one short, makes just a single valid point: viz., that you can be equally sure that you are indeed in the 1990s, no matter what your theory is about how long the human race will last. However, Carter never doubted this. What Carter considers is how likely one would have been to find oneself in the 1990s, if only a very small proportion of all humans who would ever live would have been born by then. And Carter is not eager to accept the other, invalid point which the story of the two lists appears to have suggested to Schrage's mind. Carter does not think that one really would have reason to be surprised at finding oneself on a list of humans born by 2150, if all humans who would ever live had been born by then. Carter would not gasp at how lucky he was to be one of the only hundred billion humans ever. Schrage's only remaining mathematical point would seem to be that any people born later than the 1990s cannot yet say where they are in time. But Carter never doubted this either. Why think it a difficulty for him? Imagine two batches of frozen human embryos: the first of just five, the second of five billion. The plan was that one batch was to be unfrozen in A.D. 3050 for development into adults, and the other in A.D. 5050. You do not know which batch was to be unfrozen first L but you know you started off as one of the embryos and were unfrozen in 3050. Do you say to yourself that if you had been in the batch of only five, then the humans who would come from the batch of five billion could not yet say where they were in time and that therefore you could have no probabilistic grounds for thinking that more than five were unfrozen in 3050? Surely not. Dieks's letter is more interesting: He has done some hard thinking. He reasons that the doomsday argument overlooks the fact that a longer-lasting human race would have contained more observers when it ended. The consequent increased likelihood of finding yourself to be a h u m a n observer could then counterbalance the lesser likelihood of finding yourself before 2150. When Dieks developed this line of thought in The Philosophical Quarterly, in reaction to an earlier paper of mine there, I understood him as saying that the counterbalancing was automatic and exact. However, he now stresses that what does the counterbalancing is just area-
sonable preference for supposing that the human race is large, granted that one finds oneself to be a human observer, not (say) an Andromedan. But I see no real difficulty for Carter's argument here. Suppose we concede (very controversially) that the universe's spatiotemporal entirety includes many trillion trillion trillion Andromedans. We must then make the further concession that adding a few trillion post-2150 humans would only marginally reduce an observer's chance of finding himself or herself to be a pre-2150 human. ]"Working with" the hugely many Andromedans, the trillions of post2150 humans would make it only marginally "harder" for a randomly chosen observer to be a pre-2150 human. It would be the Andromedans who were doing almost all the work.] But this concession is of only slight interest, for one's reference class ought to be humans and not observers. Why? Well, Carter is not asking the question to which "Am I a human observer and not just an observer?" could be relevant, the question of whether the human race is large or small compared with the race of Andromedans or with all nonhuman races together. Rather, he asks whether the humans before 2150 are many or few compared with the humans afterwards. Hence he can forget about brainy dinosaurs, whales, Martians, intelligent black clouds, and so on. If an urn contains just one ball marked with your name, and you find it is in the first ten blue balls to be drawn, then this can be a strong hint that the urn does not contain a thousand blue balls. You can rightly disregard any red balls, green balls, black balls, yellow balls, et cetera. Several readers asked for copies of my "Time and the Anthropic Principle," presented in Leningrad in 1990. A much expanded version of this is in the July 1992 issue of Mind, a British philosophical journal. A large number of objections to Carter's argument are considered there, but so far I have found none that destroys it.
John Leslie Department of Philosophy University of Guelph Guelph, Ontario NI G 2 W1, Canada
Ulam and Beethoven I read with interest the review of S. Ulam's work by Reuben Hersh [Mathematical Intelligencer 14, no. 4, 7172]. In it, Hersh repeats a theory proposed by Gian-Carlo Rota that Ulam suffered from brain damage. Hersh goes on to compare Ulam's work with that of Monet and Beethoven, and reveres Ulam with "equal admiration." Ulam is called the father of the H-bomb; he boasted of that accomplishment. How can the creation of weapons of mass destruction be paralleled with Monet's paintings and Beethoven's symphonies? Non-mathematicians are
often baffled when we talk abut the elegance of a proof or the beauty of a concept. However, the invention of a deadly weapon for humankind cannot be put at the level of masterful human artistic creations. This is a long review article spanning the whole career of Stanislav Ulam. Hersh provides the reader with his personal anecdotes of the times he spent with Ulam. But the article ends up being incomplete and misleading, for its omits discussion of the effects of Ulam's invention. It is naive to assume that by not confronting the consequences of our w o r k we make them go away.
Daniel B. Szyld Department of Mathematics Temple University Philadelphia, PA 19122-2585 USA e-maih
[email protected]
Reuben Hersh Responds I agree with Daniel P. Szyld's concluding sentence. I question the others. It would be fatuous to compare Stan Ulam's mathematics with Beethoven's music. Stan had encephalitis. Rota speculated that Stan's inability to sustain concentrated mental effort might have been due to brain damage. As an analogue I cited Beethoven's Ninth Symphony. It was composed after Beethoven became deaf. That fact makes it more impressive, not less. In the same way, Stan's continuing his mathematical activity for years after suffering encephalitis and possible brain damage makes his accomplishments more impressive, not less. This is not equating Stan's mathematics with Beethoven's music, nor Stan's encephalitis with Beethoven's deafness. 1 isn't equal to 3, nor 2 to 6, but still I is to 2 as 3 is to 6. I told Stan I'd read that he was father of the H-bomb, and dismissed it as journalistic nonsense. He answered proudly, "But it's true!" No reasonable human wants to be known as father of the H-bomb. I was shocked that Stan proudly accepted that title. Probably Szyld would like my implications to be more explicit. Daniel Szyld finds my review "incomplete and misleading" because it "omits discussion of the effects" of the H-bomb. As to its potential effect, it needs no repetition in 1993 that it can end all human life. As to its actual effect (no human has yet been injured by explosion of an H-bomb), this needs a serious politico-economic analysis. I'm unqualified to do this. Perhaps Daniel Szyld will provide it.
Department of Mathematics University of New Mexico Albuquerque, NM 87131-0001 USA THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
7
Taking Formalism Seriously* Edward Nelson
Almost all mathematicians believe that the natural numbers exist. How would the world be different if they did not exist? Share with me a fantasy: We open our morning newspaper to find a report with a banner headline: "Numbers Vanish!--Early last night the natural numbers, so called because they have always been found in nature, suddenly disappeared. Mathematicians have expressed stunned despair. Without numbers, they say, they can no longer prove theorems. Numbers are the foundation of science and technology, and without them humanity will soon revert to barbar- (continued on an inside page)." This is nonsense. The newspaper could still put marks 2, 3, etc., on the inside pages for ease of reference. Machines could still function as before. And we mathematicians could continue to put marks on paper, just as before, and hopefully submit them to editors of mathematical journals. We do not need the natural numbers. Some would maintain that the natural numbers exist of necessity and could not disappear. This is a religious belief that I do not share. Formalism is that view of the foundations of mathematics which maintains that the natural numbers and other mathematical entities do not exist, that mathematics is the manipulation of marks according to specified rules. Formalism is associated with the name of David Hilbert, but Hilbert did not take formalism seriously. For him, it was a tactical device in his skirmishes with the intuitionists, designed to enable mathematicians to continue to dwell in Cantor's paradise. I shall outline what I believe are the consequences of taking formalism seriously.
Writing Correct Proofs There is a gap between the professions of formalists and mathematical practice. Few mathematical works contain full proofs that obey in detail explicitly formulated rules. Such completeness has been too tedious for author and reader alike. But since the dawn of mathematics in Greece, it has been a worthy ideal. Mathematics is a highly social endeavor, and although we may dis-
* This article is a d a p t e d from a talk given by the author at the Congress on Logic, Methodology, and the Philosophy of Science, Uppsala, 1991. 8
THE MATHEMATICALINTELLIGENCERVOL 15, NO. 3 (~)1993Springer-VerlagNew York
pute with each other questions of priority or questions of value, through the centuries we have striven--with a remarkable measure of success--for c o m m o n standards of what constitutes a correct argument. More than the practitioners of any other discipline, mathematicians judge work by c o m m o n l y held criteria. But it is a frequent occurrence for incorrect results to be published, and it is even more frequent for results to be published with a serious gap in the argument. And w h e n a truly important result is claimed, several mathematicians m a y spend weeks checking the proof. With the advent of digital computers, this will soon begin to change, and it will change radically during the lifetime of m a n y of those reading this. There will be data banks of theorems, arranged hierarchically to facilitate search by mathematicians attempting to prove n e w theorems. Interactive programs will be developed to help us construct fully formalized proofs, and w h e n these are submitted, they will be verified and entered into the data bank with the name of the inventor and date of construction. For m y own purposes, I have constructed a proofchecking program called qed, written in Larry Wall's perl language. It is available as pub/qed.tar.Z by a n o n y m o u s ftp from math.princeton.edu. Qed runs over a suitably prepared .tex file and checks close to 400 proofs, performing over 17000 steps, in 9 minutes on a sparc. The proofs in question were constructed by using qed interactively. It is a primitive program, but it has some features that I believe more sophisticated programs will share. I am speaking about programs for mathematical reasoning as distinguished from mathematical computation. Such a program should have two levels: a very rapid verification program for fully formalized proofs and a hierarchically structured interactive search program. The verification should exploit duality. Each logical operator should be encoded by a single byte, and there should be a byte for affirmation (the dual of negation) so that the negation of any formula can be achieved simply by translating each logical operator byte into its dual. Every step of every proof should be an argument by contradiction. Suppose that A1,..., An is a list of formulas that have been proved, or are assumed as hypotheses in a deduction, and we want to deduce A. Then we adjoin -~A to the list, and for each formula on the list, we look to see whether it or its negation is a subformula of some other formula on the list; if so, we make the appropriate reduction by the laws of the propositional calculus with equality. This can be done very rapidly. If we find a contradiction, then A has been deduced. But if we do not find a contradiction, our work m a y not have been wasted: Each formula on the reduced list is a consequence of assuming -~A as a hypothesis, and the argument can be continued. There are m a n y levels of search involving an exponentially large world of possibilities. By necessity, such searches are time-consuming. The most primitive level
of search is for the appropriate terms to substitute for the free variables in a theorem. This is usually routine, as in applying the commutative law x 9y = y 9x to conclude that a + b. c = a + c. b, but sometimes it involves insight, as in applying the Liouville theorem " f is a b o u n d e d entire function implies f is a constant" to the function 1/p where p is a polynomial without roots. As the years pass, more and more sophisticated searches will be prog r a m m e d into computers. But good mathematics is the fruit of deep personal and cultural experience. Digital computers and people have different search skills, and a fruitful program will involve them in an interactive partnership.
Questioning Church's Thesis 0 is a numeral; if n is a numeral, then Sn is a numeral. Thus the numerals are 0, SO, SS0, SSS0, and so forth. Numerals are used to count things. An effectively computable function is a program that for any numerals as arguments terminates in a finite number of steps and yields a numeral as value. This is a somewhat vague concept, but the concept of a recursive function is precisely formalizable; Church's thesis is that the two concepts are equivalent. For example, x + O = x, x+Sy = S(x+y) x - 0 = O, x . S y -- (x. y) + x, x ~ = SO, x s~ = x ~ -x,
(1) (2) (3) (4) (5) (6)
x ~ 0 = SO,
(7)
x "~ Sy = x ~ y
(8)
give constructions of addition, multiplication, exponentiation, and superexponentiation as recursive functions. No attempt to construct an effectively computable function that is not recursive has been successful; Church's thesis has withstood challenges from above. But we can challenge it from below: how do we k n o w that every recursive function is effectively computable? Computer scientists agree that the dividing line between functions computable in practice and those not computable in practice lies roughly between multiplication and exponentiation. But I want to discuss computability in principle, as nearly as I can recall the meaning that I used to think I understood by the phrase "in principle". Thefinitary dogma asserts that every recursive function is effectively computable; that is, it asserts that for any variable-free term made up from 0 and function symbols representing recursive functions, such as
ss0 ~- (ss0 # sssss0), THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
9
if we apply the rules of construction sufficiently often, we end up with a numeral. Finitists have verified this for simple cases. In other cases, they may give up, but they know that if only they persisted long enough the computation would terminate. If asked how long that is, their answer would be: roughly the number of the numeral I am computing. Spoiled children throw temper tantrums; they have verified in simple cases that this gets them what they want. In other cases, they may give up, but they know that if only they persisted long enough they would get what they want. If asked how long that is, their answer would be: until I get what I want. In saying this, I am casting no aspersions on those who hold opinions different from mine; I am simply expressing my opinion that finitism is a self-validating belief system for which there is no evidence and which may very well be incorrect. Let us examine the finitary dogma more closely. In general, the logical terminology and notation used here are those of Shoenfield [5]. Let T be a strong theory, one that formalizes contemporary mathematics. Assume that T is consistent. Let T be the theory obtained by adjoining to T a new unary predicate symbol r and the axioms
r r
(9) (10)
r
These axioms express the idea of counting, parallel to the metamathematical definition of a numeral, and the intended meaning of r is "x is equal to a numeral". Let F be a recursive function, say of two variables, formalized in T. Can we prove in t a theorem expressing the idea that if x and y are numerals, then F(x, y) is equal to a numeral? Even for addition, we cannot prove in ~ that
+y).
(11)
To see this, take a nonstandard model of T (i.e., one in which the natural numbers contain a nonstandard u) and interpret r as signifying that x is less than u plus some standard natural number. Then we have (9), (10), and r but not r + u), so (11) is not provable in T. Let us try another approach. Can we find an inductive formula A of ~ (i.e., a formula such that A(0) and A(x) --* A(Sx), and consequently A(n) for every numeral n, are theorems of T) such that
A(x) & A(y)
r
y))
(12)
is a theorem of T? If so, then we can say that we have proved that if x and y are numerals, then F(x, y) is equal to a numeral. For addition we can let A be the formula r given by
10
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3,1993
and for multiplication we can let A be the formula given by
vy[r
r
•3(X)
x)];
see Chapter 5 of [1]. But the proofs of (12) for addition and multiplication use the associativity of these operations, and exponentiation is not associative. In fact, the following metatheorem is proved in Chapter 18 of [1] (though not formulated in quite this way): If F is the exponential function, F(x, y) = xY, there does not exist an inductive formula A of t such that (12) is a theorem
oft. In other words, the only w a y to prove that the exponential of one numeral by another is always equal to a numeral is to beg the question by postulating for the formalization of the concept "x is equal to a numeral" some property going beyond the original concept of counting. It is interesting that the dividing line for demonstrable computability in principle is the same as that for computability in practice. This result should give finitists pause. Finitism is the last refuge of the Platonist.
S e e k i n g a Contradiction Robinson's theory Q (see [4]) is the theory whose nonlogical axioms are Sx r 0, Sx=Sy ~ x=y,
(13) (14)
x r 0 ~ ~y[Sy = x].
(15)
(1)-(4), and This may be reformulated as an open theory Q0 by introducing a function symbol P (for predecessor) and replacing (15) by x # 0 --* SPx = x.
(16)
Robinson's theory is the simplest theory in which one can do nontrivial mathematics. It is essentially Peano Arithmetic without induction. Several consistency proofs for Q are known. The most familiar is the infinitary argument that the natural numbers are a model for Q. But in a world from which numbers have vanished, this carries no conviction. There is also a finitary consistency proof. The first point is that Q0 is quasitautologically consistent, meaning that it is impossible to derive a contradiction in the theory without using quantifiers. More precisely, let Q~ be the formal system with the same language and nonlogical axioms as Q0 but with no quantifiers and with instance and quasitautological consequence as rules of inference; then Q~ is consistent. There is certainly a finitary demonstration of this assertion. I believe that it is
in fact true and that a demonstration can be given that will convince the most skeptical of formalists. The second point is that the consistency of Q follows from this assertion by the Hilbert-Ackermann theorem, a finitary algorithm for eliminating quantifiers from proofs; see [5]. But the Hilbert-Ackermann theorem relies on the finitary dogma; specifically, that superexponentiation is effectively computable. For one who has put aside credence in the finitary dogma, this proof also carries no conviction. Taking formalism seriously entails regarding the consistency of Q as an open problem. It would be solved if one could derive a contradiction in a theory interpretable in Q. This is what I am working on now.
Seeking a Demonstrably Consistent Mathematics Who would have believed 10 years ago that it is possible to do modern mathematics in a theory for which there is a finitary consistency proof? Yet that is what [1] and [2] together accomplish; see the description of Q* in the last chapter of [1]. In [2], modern ideas of stochastic processes find direct expression, liberated from the h e a v y weight of Cantorian set theory. This is made possible by using a small portion of Abraham Robinson's nonstandard analysis [3]. It is an open problem to develop a formal system that is demonstrably--without appeal to the finitary d o g m a - consistent, and yet is powerful enough for modern mathematics. The phrase "foundations of mathematics" is a static architectural image. I prefer to think of mathematics as a growing tree. Rather than construct foundations, the formalist can study and nourish the roots of this tree. By taking a fresh look at the way good mathematics is actually done, we may find to our surprise that it is demonstrably consistent.
Ad Infinitum... The Ghost in Turing's Machine TAKING GOD OUT OF MATHEMATICS AND PUTTINGTHE BODY BACKIN AN ESSAYIN CORPOREALSEMIOTICS
Brian Rotman "A bold, imaginatively worked out and extremely lucid reconceptualization of the fundamental nature of mathematics. Extending and supporting contemporary conceptions of the social and rhetorical operation of all forms of knowledge, Ad Infinitum is a significant contribution to 'postmodem' epistemology and the philosophy of science." --Barbara Hermstein Smith, Duke University This ambitious work puts forward a new account of mathematics-as-language--a radical altemative to the classical interpretation of whole numbers called non-Euclidean arithmetic--that challenges the coherence of the accepted idea of infinity and suggests a n e w conception of counting. Cloth, $39.50; paper, $12.95
Signifying Nothing References 1. Nelson, Edward, Predicative Arithmetic, Mathematical Notes No. 32, Princeton University Press, Princeton, NJ (1986). 2. Nelson, Edward, Radically Elementary Probability Theory, Annals of Mathematics Studies 117, Princeton University Press, Princeton, NJ (1987). 3. Robinson, Abraham, Non-standard Analysis, rev. ed., American Elsevier, N e w York (1974). 4. Robinson, R. M., "An essentially undecidable axiom system," Proc. Int. Cong. Math., Cambridge, MA, 1950, Vol. I, pp. 729-730. 5. Shoenfield, Joseph R., Mathematical Logic, Addison-Wesley, N e w York (1967).
THE SEMIOTICSOF ZERO
Brian Rotman This book portrays the introduction of the mathematical sign zero as a major signifying event, both within the writing of numbers and as an emblem of parallel events in other sign systems. "This unusal book is a delightful analysis of the nature of zero as a sign intimately connected to the idea of nothing." -.-Choice "A tapestry of delicate elaborations on a single beautiful idea." --Radical Philosophy Paper, $12.95
Stanford University Press Department of Mathematics Princeton University Princeton, NJ 08544 USA E-maih
[email protected], edu
STANFORD, CA 94305-2235
THEMATHEMATICALINTELLIGENCERVOL.15,NO.3,1993 11
A N e w Look at Euclid's Second Proposition Godfried Toussaint
There has been considerable interest during the past 2300 years in comparing different models of geometric computation in terms of their computing power. One of the most well-known results is Mohr's proof in 1672 that all constructions that can be executed with straightedge and compass can be carried out with compass alone. The earliest such proof of the equivalence of models of computation is due to Euclid in his second proposition of Book I of the Elements, in which he establishes that the collapsing compass is equivalent in power to the m o d e m compass. Therefore, in the theory of equivalence of models of computation Euclid's second proposition enjoys a singular place. However, the second proposition has received a great deal of criticism over the centuries. Here it is argued that it is Euclid's early Greek commentators and more recent expositors and translators that are at fault, and that Euclid's original algorithm is beyond reproach.
operations that can be performed in one unit of time include the arithmetic operations consisting of addition, subtraction, multiplication, and division, comparisons between real numbers, reading from and writing into a storage location, as well as perhaps some more
Introduction In the modern comparative study of geometric algorithms it is imperative first to define the models of computation, that is, the characteristics of the machine that will execute the algorithms [30]. A model of computation specifies the number of processors used, whether they are used sequentially or in parallel, the primitive operations allowed, and the cost associated with each of these operations. For example, one of the preferred conceptually abstract models or ideal machines in which many geometric algorithms are compared is the Real RAM (Random Access Machine) [1], in which each unit of storage space is capable of holding a real number of unlimited precision, and in which the primitive 12
~
MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3 9 1993 Springer-Verlag New York
powerful operations, such as computing kth roots, trigonometric functions, and other analytic functions. More controversial assumptions sometimes include the ceiling and floor functions. In classical constructive geometry, mathematicians have also been concerned with defining the models of computation, that is, the characteristics of the "machine" that will execute the algorithms. Typical machines that have been used in the past starting with Euclid include (1) the straightedge, (2) the ruler, (3) the collapsing compass, (4) the compass, (5) the fixed-aperture compass, (6) the compass with aperture bounded from above, and (7) the compass with aperture bounded from below, just to name a few [11, 17, 21, 34]. The collapsing compass deserves elaboration here. With the regular compass, one can open it, lock it at a chosen aperture, and lift it off the work space to some other location to draw a circle with the chosen radius. This operation cannot be done with a collapsing compass. The collapsing compass is, like the other machines, an idealized machine which allows the compass to be opened to a chosen radius and a circle drawn, but no distance can be transferred. It is as if when the compass is lifted off the work space, it collapses and, thus, erases any Jtrace of the previous aperture made. Of course, more complicated machines can be obtained by combining sets of simple machines. For example, in Euclid's Elements he uses the straightedge and collapsing compass (the combination of machines 1 and 3) as his model of computation. Attempts have also been made to specify the primitive operations allowed with each type of machine [23] and to design constructions that require fewer operations than did Euclid's original constructions. Another active area of research has been to analyze and compare different machine models in terms of their computational power [2, 4, 11, 17]. For example, in 1672 Jorg Mohr [25] and in 1797 the Italian geometer Lorenzo Mascheroni [24] independently proved that any construction that can be carried out with a straightedge and a compass can be carried out with a compass alone; and Jacob Steiner proved in 1833 that the straightedge is equivalent in power to the compass if the former is afforded the use of the compass once [32]. To remind the reader that the straightedge and compass are not yet obsolete computers, we should point out that the Mohr-Mascheroni result was strengthened as recently as in 1987 by Arnon Avron [2] at the University of Tel Aviv. The earliest proof of the equivalence of models of computation is due to Euclid in his second proposition of Book I of the Elements, in which he establishes that the collapsing compass is equivalent in power to the compass. Therefore, in the theory of equivalence of the power of models of computation, Euclid's second proposition enjoys a singular place. However, like much of Euclid's work and, particularly, his constructions involving m a n y cases, his second proposition has
received a great deal of criticism over the centuries. In this article, it is argued that it is Euclid's commentators and translators that are at fault, and that Euclid's original algorithm and proof are beyond reproach.
Euclid's First Two Propositions According to Pedoe Pedoe [27] contains a lively discussion of Euclid's elements of geometry applied to painting, sculpture, and architecture throughout recent history. To illustrate Euclid's method, he presents the first two propositions of Book I of his Elements. Earlier in the book Pedoe actually has a completely different algorithm and proof of Proposition 2, to which we shall return at the end of this article. However, at this later point in the book he states that "it is of interest to read how it appears in Euclid." Whereupon the following algorithms and proofs of correctness are presented. PROPOSITION 1. On a given finite straight line to con-
struct an equilateral triangle. Algorithm 1: Input: Let AB be the given finite straight line. (Thus, it is required to construct an equilateral triangle on the straight line AB.) See Figure 1.
D
E
Figure 1. Euclid's figure for the proof of Proposition 1.
Begin Step 1: With centre A and distance AB let the circle BCD be described. Step 2: With centre B and distance BA let the circle ACE be described. Step 3: From the point C, in which the circles cut one another, to the points A, B let the straight lines CA, CB be joined. End THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3, 1993 1 3
Proof of Correctness: Now, since the point A is the centre of the circle CDB, AC is equal to AB. Again, since the point B is the centre of the circle CAE, BC is equal to BA. And things which are equal to the same thing are also equal to one another; therefore, CA is also equal to CB. Therefore, the three straight lines CA, AB, BC are equal to one another. Therefore, the triangle ABC is equilateral; and it has been constructed on the given finite straight line AB. Being what it was required to do. End of Proof
K
D
Of course, neither Euclid nor Pedoe uses the words algorithm, input, begin, and end. Neither do they use the phrases proof of correctness nor end of proof, nor do they label separate chunks of the algorithm with the word Step such-and-such. However, early Latin manuscripts do preface the construction by the words exempli causa and the proof by probatio eius. We include these wellknown terms found in modern computer science for clarity of layout, and to recall that these divisions did appear in essence in at least the earliest Arab and Latin translations of Euclid's Elements. The important thing is that Euclid always gave the algorithm first and the arguments to substantiate the correctness of the algorithm immediately afterward. Even today, too many writers publish geometric algorithms without including a proof of correctness, in spite of the many geometric algorithms that have been found to be incorrect [37]. These authors could certainly take a lesson here from Euclid. Sometimes, as we shall see below, the algorithms in the Elements include unnecessary steps for obtaining the solution, but these steps have the benefit of simplifying the ensuing proof of correctness. Euclid also made use of another common practice in m o d e m computer science: subroutines. In the algorithm of his second proposition described next, he uses Algorithm I above. Below we give Pedoe's description of Euclid's construction.
Exit with AL as the solution. End Proof of Correctness: Then, since the point B is the centre of the circle CGH, BC is equal to BG. Again, since the point D is the centre of the circle GKL, DL is equal to DG, and in these DA is equal to DB. Therefore, the remainder AL is equal to the remainder BG. But BC was also proved equal to BG. Therefore, each of the straight lines AL, BC is equal to BG; and things which are equal to the same thing are also equal to one another. Therefore, AL is also equal to BC. Therefore, at the given point A the straight line AL is placed equal to the given straight line BC. Being what it was required to do. End of Proof
PROPOSITION 2. To place at a given point (as an extremity) a straight line equal to a given straight line. Algorithm P [Pedoe's version]: Input: Let A be the given point, and BC the given straight line. (Thus, it is required to place at the point A (as an extremity) a straight line equal to the given straight line BC.) See Figure 2. Begin Step 1: From the point A to the point B let the straight line AB be joined. Step 2: On AB (using Algorithm 1) let the equilateral triangle DAB be constructed. Step 3: With centre B and distance BC let the circle CGH be described. Step 4: With centre D and distance DG let the circle GKL be described.
We remark here that Pedoe's figure, shown in Figure 2, is considerably different from those in other sources on Euclid such as Heiberg [16], Heath [15], and Dijksterhuis [13] for example. Much more serious, however, is the fact that Algorithm P given by Pedoe is incorrect! It is clear that for a solution to be obtained by Algorithm P, it is crucial that the circle centred at B with radius BC intersect DB at G. Otherwise, G is undefined and the rest of the algorithm makes no sense. Now consider what happens w h e n the length of BC is greater than the distance from A to B. Clearly, the circle centred at B with radius BC will completely enclose triangle ABD and its interior and the construction fails! In m o d e m parlance, for such an input the algorithm crashes.
14
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
L B
C
A
H Figure 2. Pedoe's figure for proving Euclid's Proposition 2.
Euclid's Construction According to 19th-, 18th-, and 17th-Century Scholars During the 19th century, along with more than 700 editions of The Elements, there was a flurry of textbooks on Euclid's Elements for use in the schools and colleges. A sample of several of these books [14, 22, 33, 36] yields a common (apart from notation) algorithm and illustrative figure for Euclid's second proposition. However, both the algorithm and figure are quite different from Pedoe's. Consider then the algorithm according to one of these sources [14]. PROPOSITION 2. From a given point to draw a straight line equal to a given straight line. Algorithm 19C [Popular 19th-century version]: Input: Let A be the given point and BC the given straight line. (It is required to draw from the point A a straight line equal to BC.) See Figure 3.
Begin
This algorithm is certainly an improvement over Pedoe's algorithm as it appears to work correctly for some input configurations whether BC is greater than or less than BA. Nevertheless the algorithm suffers from ambiguous statements. Step 4 asks us to produce (extend in length) DB to meet the circle CGH at G, but it does not tell us in which direction (emerging from D or from B) to produce DB, and certainly in either direction we are bound to meet the corresponding circle constructed in Step 3. Figure 3 shows one possible case, but had we produced DB in the direction from B to D instead of the direction shown we would have obtained a completely different intersection point G. A similar problem exists with Step 6. The ambiguities observed in the algorithms described in [14] and [33], which are exemplified here as Algorithm 19C, are absent in the exposition by Taylor [35], if not in the body of the algorithm at least in the subsequent discussion, where it is indicated that we are free to choose one or the other alternative as in Step 1. It is therefore instructive to examine his algorithm and accompanying discussion in more detail.
Step 1: Join AB. Step 2: On AB, describe an equilateral triangle DAB. Step 3: From centre B, with radius BC, describe the circle CGH. "Step 4: Produce DB to meet the circle CGH at G. Step 5: From centre D, with radius DG, describe the circle GKF. Step 6: Produce DA to meet the circle GKF at F. Then AF shall be equal to BC.
PROPOSITION 2. From a given point to draw a straight line equal to a given straight line. Algorithm T [Taylor's version]: Input: Let A be the given point and BC the given straight line. (It is required to draw from the point A a straight line equal to BC.) Refer to Figure 4.
End
Begin Step 1: Draw AB, the straight line from A to one of the extremities of BC. Step 2: On it, construct an equilateral triangle DAB. Step 3: With B as centre and BC as radius, describe the circle CEF, meeting DB (produced if necessary) at E.
Figure 3. Popular 19th-century figure for the proof of Euclid's Proposition 2.
K Figure 4. IllustratingTaylor's version of Euclid's Proposition 2. H
H C
D F
A
C
B F
G
G THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993 l ~
Step 4: With D as centre and DE as radius, describe the circle EGH, meeting DA (produced if necessary) at G. Then AG is the straight line as required. End Note that Taylor is careful to add in Steps 3 and 4 the explicit if statements that DB and DA are to be produced if necessary. Therefore we presume that if the construction circle CEF intersects the sides of equilateral triangle ABD, then the extension of DA need not be carried out. Unlike the previous 19th-century geometry books, Taylor follows the proof of Proposition 2 with the following interesting discussion. It is assumed in this proposition that the straight line DB intersects the circle CEF. It is easily seen that it must intersect in two places. It will be noticed that in the construction of this proposition there are several steps at which a choice of two alternatives is afforded: (1) we can draw either AB or AC as the straight line on which to construct an equilateral triangle: (2) we can construct an equilateral triangle on either side of AB: (3) if DB cut the circle in E and I, we can choose either DE or DI as the radius of the circle which we describe with D as centre. There are therefore three steps in the construction, at each of which there is a choice of two alternatives: the total number of solutions of the problem is therefore 2 x 2 x 2 or eight. We see that Taylor's w a y of dealing with the ambiguities discussed above is to explicitly acknowledge that there are eight different cases to Euclid's proposition that depend on h o w the construction is carried out, that we are free to choose any one of these eight paths through the implied decision tree, and that the sides DB and DA need not be produced if not necessary. In light of this classification, let us follow down one path of these choices on the input configuration illustrated in Figure 4, where it is assumed that the length of CB is greater than the length of CA. In our first choice we, therefore, select AB as the segment on which to construct our equilateral triangle. Our second decision will be to construct the triangle on the side shown in Figure 4. N o w because the circle CEF does not intersect the triangle, we extend DB, which cuts the circle at the two points E and I. According to Taylor, we may n o w choose either DE or DI as the radius of the circle which we describe with D as centre. Let us choose DI. Now, this circle with D as centre intersects DA at G', playing the role of G in his algorithm, and, therefore, according to Step 4, DA need not be produced to G. According to the algorithm, therefore, the solution is given by AG' which is clearly incorrect, because AG' is smaller than AB, whereas BC is greater than AB, by assumption. Therefore, although the ambiguities of Algorithm 19C have been removed by Taylor, Algorithm T does not always yield the correct solution on a given line-point configuration, depending on which construction strategy is applied. 16
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
Furthermore, Algorithm T suffers from an additional minor bug not even present in Algorithm 19C. Note that Step 1 in Algorithm 19C does not offer choice. Algorithm T asks that A be connected to one of the extremities of BC, one that we are free to choose. However, if we choose to connect A to C (rather than B as in Taylor's figure), then it is impossible to execute Step 2, and the algorithm crashes. Another author, Lardner [22], also follows his presentation of an ambiguous algorithm identical to Algorithm T with a discussion of h o w the student should be careful about different cases arising from the varieties of different input configurations. In his o w n words, The different positions which the given right line and the given point may have with respect to each other, are apt to occasion such changes in the diagram as to lead the student into error in the execution of the construction for the solution of this problem. Hence it is necessary that in solving this problem the student should be guided by certain general directions, which are independent of any particular arrangement which the several lines concerned in the solution may assume. If the student is governed by the following general directions, no change which the diagram can undergo will mislead him. Lardner then proceeds to present six general rules concerning what can and cannot be done to ensure that Algorithm T works correctly on all inputs. This discussion includes a case analysis of construction strategies. Unlike Taylor [35], it does not allow DA and DB to be extended in either direction, but insists that they be extended through the base of the constructed triangle, thus concluding that the solution to Euclid's second proposition has four cases rather than Taylor's eight. Another general rule that Lardner insists should be followed is that the centre of the circle constructed in Step 3 should lie at the extremity of BC connected to A in Step 1, thus avoiding one of Taylor's problems. Another variation occurs in a much earlier Scottish book on Euclidean geometry published in 1831 by John Playfair [29], which has a variant of Algorithm 19C. In this book, we are asked to extend DA and DB to E and F, respectively, and thus the ambiguity of Algorithm 19C is also present here. However, unlike Algorithm 19C or Algorithm T, the algorithm in [29] first performs the extensions and subsequently constructs the circles. We close this section with a note on textbooks of the 18th and 17th centuries. In these two centuries combined the number of editions of Euclid's Elements published was less than half of the number for the 19th century, about 325 and 280 in the 18th and 17th centuries, respectively. It is also much more difficult to find copies of these earlier editions. I have held in m y hands only two editions from the 18th century [5, 38] and one from the 17th century [10], having found all
three in the special collection of the library at Queens University in Kingston, Ontario. The 1705 manuscript by Isaac Barrow (from Trinity College, Cambridge) has the additional distinction (according to the claim on its front page) of being the first English copy translated from Latin. What is worth noting about the algorithms in these texts is that (1) they are identical to each other; (2) like Algorithm 19C, they are ambiguous; but (3) unlike all other algorithms I have encountered, they begin not by connecting point A to one of the end points of segment BC but by constructing a circle of radius BC centred at one of the end points of BC. Then, in the second step, point A is joined to the end point selected as the centre in the previous step. Note that this ordering circumvents the problem that Algorithm T has with Steps I and 2, and furthermore allows us to ignore Lardner's caveat intended to resolve it.
In spite of the criticism often directed at Euclid, one may find it difficult to believe that he could have been guilty of such oversight as in the versions of his algorithm exhibited so far. However, established authorities on Euclid, such as Heiberg [16], Heath [15], and Dijksterhuis [13], have a significantly different algorithm. The figure in these three works is given in Figure 5, and the algorithm is given below. We omit the proof of correctness as it is exactly the same as that given by Pedoe.
K
H Euclid's Construction According to Gerard of Cremona and Peyrard
D
One is naturally led to the question: Which of all these algorithms is the one Euclid originally proposed? It "would be easy to answer this question by looking up Euclid's original manuscript. Unfortunately, history has made this impossible. In the year 332 B.c. AlexE ander the Great, at the age of 24, conquered Egypt and founded the city of Alexandria. When, after conquering much of the rest of the world, he died at the age of 33, his generals divided up the empire. In this way G Egypt fell into the h a n d s of Ptolemy I in 306 B.c. Ptolemy II created the University of Alexandria, which F became, by virtue of its excellent scholars (including Figure 5. Euclid's figure for the proof of Proposition 2 Euclid) and its impressive library (three-quarters of a according to Heath. million books including Euclid's original version of The Elements), the intellectual and scientific centre of the world. In 48 B.c. Julius Caesar occupied Alexandria PROPOSITION 2. To place at a given point (as an extremand intended to carry a large portion of the library with ity) a straight line equal to a given straight line. him back to Rome. The academic community held a Algorithm Euclid [Heath's version]: demonstration which was quickly quelled by Caesar's Input: Let A be the given point, and BC the given army. In the fighting many of the books were burned. straight line. (Thus, it is required to place at the point More books were burned during later Egyptian revolts A (as an extremity) a straight line equal to the given in 272 A.D. and 295 A.D. In the 4th and 5th centuries, straight line BC.) See Figure 5. zealous Christian bishops began to persecute the pa- Begin gan writers (mathematicians) and their books. Bishop Step 1: From the point A to the point B let the straight Theophilus in 391 A.D. led a Christian mob and de- line AB be joined. stroyed the Temple of Serapis which housed many of Step 2: On AB (using Algorithm 1) let the equilateral the remaining books. The last mathematician alive in triangle DAB be constructed. Alexandria, a w o m a n by the name of Hypatia, was Step 3: Let the straight lines AE, BF be produced in a hacked to pieces by Bishop Cyril. Finally, the Arabs straight line with DA, DB. invaded Egypt in 646 A.D., and General Amr ibn-al-As Step 4: With centre B and distance BC let the circle CGH burned the remaining books, allegedly because [6] "if be described. the books agreed with the Koran they were superflu- Step 5: With centre D and distance DG let the circle GKL ous; if they disagreed they were pernicious." In short, be described. in all likelihood Euclid's original algorithm went up in Exit with AL as the solution. End smoke. THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3, 1993 ~ 7
Note that in Figure 5 the length of BC is indeed larger than the distance between A and B and Pedoe's version of Euclid's algorithm would not work in this case. However, for unknown reasons (I will offer a conjecture later), Pedoe leaves out Step 3 in the above algorithm. This crucial step in Euclid's algorithm constructs the extensions of DA and DB in directions E and F, respectively, thus ensuring that, whether or not the length of BC is larger than the distance between A and B, the algorithm continues to "execute," and the figure remains the same in the sense that point G exists and lies on BF. Note the difference between the manner in which DA and DB are to be produced in Algorithm Euclid as compared to Algorithm 19C and Algorithm T. In the latter two algorithms, the ambiguous instructions state that the sides of the equilateral triangle DA and DB are to be produced. In Algorithm Euclid, on the other hand, the statement in Step 3 concerning the extension of DA and DB states, "Let the straight lines AE, BF be produced in a straight line with DA, DB.'" In other words, the extensions are to be collinear with (in a straight line with or in the direction of) DA and DB. No room is left here for choosing the direction of the extensions of DA and DB as in Algorithm 19C. At this point, one may wonder about the authenticity and correctness of the accounts of Heiberg [16], Heath [15], and Dijksterhuis [13]. The Greek text by Heiberg is considered to be the definitive edition. It consists of portions taken from different Greek manuscripts spanning the 9th to 12th centuries and considered by philologists to be the most authentic. There also exist several interesting Latin manuscripts which are translations of Arabic manuscripts. We may peruse the first printed edition of the Latin translation of the Arabic (Ishaq-Thabit) version of Euclid's Elements, believed to have been made by the monk Gerard of Cremona in Toledo during the 12th century [8] following its discovery in Baghdad. We find that apart from the letters E and F in Heath being replaced in [8] by L and G, respectively, the algorithms and proofs of correctness found in [13, 15, 16] are identical to those in the 12th-century manuscript. This 12th-century algorithm is a Latin translation of an Arabic translation of a Theonian Greek manuscript. In fact, all Arabic translations are believed to descend from the recension by Theon of Alexandria. Anyone who has played the translation game may wonder how this version compares with early Greek manuscripts with respect to the crucial Step 3. In another 12th-century Sicilian Latin translation (of unknown authorship) of Euclid's Elements made directly from the Greek [9], Step 3 is stated as follows: Educantur in directo rectis DA et DB recte AE et BF. This translates to "Lead forth the straight lines AE and BF in a straight line with (in the direction of) the straight lines DA and DB" and is, thus, in agreement with the Gerard 18
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
of Cremona version and Heiberg's definitive edition. A final piece of evidence that Algorithm Euclid described above is indeed Euclid's is the so-called manuscript P, the Vatican manuscript No. 190. Until 1804, all manuscripts of Euclid's Elements were believed to be descended from Theon's 4th-century recension [7]. When Napoleon conquered Italy, he stole from the Vatican a Greek manuscript (No. 190) of Euclid's Elements which he kept in the King's Library in Paris. F. Peyrard, a professor at the Lyc6e Bonaparte, wanted to write a definitive French version of the Elements using the best Greek manuscripts at his disposal, and towards that end obtained access to the King's Library. There he found manuscript No. 190, and to his astoni s h m e n t discovered he h a d in his h a n d s a preTheonian 10th-century manuscript. In the meantime the Allied Forces defeated Napoleon and forced France to return all stolen works of art. At the request of the French government, the Pope made Peyrard a happy man by granting an extension of the return date of the manuscript, thus giving him enough time to finish his translation [28]. In Peyrard's manuscript, which he emphasizes is a literal translation, the crucial Step 3 is written as "Menons les droites AE, BZ dans la direction de DA, DB," and is, thus, in agreement with Algorithm Euclid described above.
Cases in Constructions and Proofs The above discussion brings up naturally the general question of the analysis of cases in Euclid's constructions, modern computational geometry, and geometric proofs in general. When we talk about cases today we generally mean equivalence classes of input configurations, rather than instances of the construction sequence resulting from a set of choices made as a result of the ambiguities of the algorithm's description, as are the case classifications in Taylor [35] and Lardner [22]. An algorithm must be specified unambiguously and should execute correctly for all inputs it was designed to handle. Much criticism has been heaped on Euclid over the past two thousand years for his alleged sloppiness in constructions and proofs concerning cases. For one thing, he has been accused of giving proofs of correctness that depend severely on the figure accompanying the proof. Thus, Bertrand Russell [31]: A valid proof retains its demonstrative force when no figure is drawn, but very many of Euclid's earlier proofs fail before this test... The value of his work as a masterpiece of logic has been very grossly exaggerated. Again, in the words of William Dunham [12]: Admittedly, when he allowed himself to be led by the diagram and not the logic behind it, Euclid committed what we might call a sin of omission. Yet nowhere in all 465 propositions did he fall into a sin of commission. None of his 465 theorems is false.
Finally, in the words of Felix Klein [20]: Euclid... always had to consider different cases with the aid of figures. Since he placed so little importance upon correct geometric drawing, there is real danger that a pupil of Euclid may, because of a falsely drawn figure, come to a false conclusion. A proposition that has a plethora of cases and that has been the subject of much criticism of Euclid is in fact Proposition 2, the topic of this article. It will be argued here using this proposition as a "case" study that much of the criticism of Euclid's case analysis stems from a lack of understanding of his original work due in part to the writings of the early Greek commentators of the Elements such as Heron and Theon of Alexandria and others reviewed by Proclus [26] in the 5th century, and exacerbated by a 12th-century Latin translation of an Arabic manuscript by Adelard of Bath [7] and many English scholars of the 19th century. Furthermore, if we judge the original algorithm and proof of correctness of Euclid's Proposition 2 using today's highest standards in the field of computational geometry Euclid deserves praise for his brilliance. Return then to Euclid's second proposition: To place at a given point (as an extremity) a straight line equal to a given straight line. Clearly, an algorithm for carrying out this task has to execute, that is, be well defined for all inputs, that is, for all possible line segments BC and all points A no matter h o w they are positioned with respect to each other in the plane. Furthermore, unless the algorithm is designed to work only for inputs in general position, it should also be able to handle singularities such as w h e n point A lies on the segment BC or A is equidistant from B and C. Similarly, a proof of correctness must establish that in all situations the algorithm will yield the correct solution. Euclid had the habit, as is well illustrated by Figure 5, of including only one figure to illustrate the construction and proof. A reader may thus wonder, on stepping through the algorithm on the given figure, whether the same steps would work on a completely different figure. The same reader may even be skeptical as to whether the arguments in the proof of correctness would carry over with the same letters used as labels of crucial points derived during the construction. This, in fact, appears to have been the reaction of early Greek commentators of the Elements, w h o criticized Euclid for leaving out cases that they discovered missing and then supplied proofs of their own. An in-depth commentary of Euclid's elements and subsequent criticisms made against it was written in the 5th century by Proclus [26]. Proclus himself does not usually criticize Euclid, and on several occasions actually comes to his defense. In the words of Glenn Morrow [26], When in the proof of a theorem Euclid uses only one of two or more possible cases, as is his custom, Proclus will often prove one or more of the omitted cases; sometimes
he simply calls attention to them and recommends that his readers, "for the sake of practice," prove them for themselves. Sometimes he gives an alternative proof of a theorem devised by one of his predecessors for the obvious purposes of showing the superior elegance or appropriateness of Euclid's demonstration. Indeed one can conjure up many special cases of an initial configuration of point A and line segment BC. For example: Case 1: A may lie on the line collinear with BC, or Case 2: A may lie on one side of the line collinear with BC. In Case 1, A may lie on the line segment BC (Case 1.1) or off the line segment BC (Case 1.2). If A lies on BC, then in Case 1.1.1 it may lie on an end point of BC or in Case 1.1.2 on the interior of BC, and in the latter case we have two more cases depending on whether A is closer to B or closer to C. In Case 1.2, where A lies off segment BC, A could be closer to B (Case 1.2.1) or to C (Case 1.2.2). Furthermore, Case 1.2.1 divides into two more cases d e p e n d i n g on whether the distance between A and B is greater than or less than the distance between B and C. Case 2 in which A lies off the line coUinear with BC can also be divided into cases using a variety of criteria. For example, we might consider two cases d e p e n d i n g on whether the line segment BC lies in the interior (Case 2.1) or the exterior (Case 2.2) angle that triangle ABD makes at D. Finally, each of these two cases determines two more cases depending on whether the distance between A and B is greater than or less than the distance between B and C. Some of the above cases (but certainly not all!) were discussed by the Greek commentators and are included in the work of Proclus. Usually a proof that Euclid's algorithm worked correctly was then provided for the particular case at hand. Sometimes the actual algorithm given by Eudid was changed to handle the special case. For example, for a particular input configuration in Case 2.1 with the distance between A and B less than the distance between B and C, Proclus objects to Euclid's algorithm because line segment BC "gets in the way" of the construction of triangle ABD above segment AB (see Fig. 6). In the words of Proclus, "'for there is not room." Heath notes that Heron of Alexandria circa 100 A.D., in his commentary on the Elements, also sometimes used constructions different from Euclid's to circumvent objections of this type. The algorithm of Proclus for this particular case follows (see Fig. 6).
Begin Step 1: Let a circle be drawn with centre at B and distance BC. Step 2: Let the lines AD and BD be produced to F and G. Step 3: With centre at D and distance DG let the circle GE be described. [Exit with AE as the solution.]
End THE MATHEMATICAL INTELLIGENCER VOL, 15, NO. 3, 1993
19
Euclid's A l g o r i t h m R e c o n s i d e r e d
It is clear from the above discussion that Euclid's followers were concerned that perhaps Euclid's algorithm and proof of correctness did not hold for all possible configurations of the input to the problem. I will argue that the commentators themselves succumbed to the fallacy of "going by the figure" even more than Euclid himself, and that they missed the essence, semantics, or deep structure behind Euclid's proof. First, we should remember that w h e n cases did in fact exist, Euclid used figures to illustrate a construction and proof rather than make a case statement. In the words of Heath,
C
E
Figure 6. Proclus's figure for the proof of a subcase of Case 2.1 of Proposition 2.
Note h o w Proclus has c h a n g e d the clear lineextension statements of Euclid's algorithm to the ambiguous statements (let the lines AD and BD be produced to F and G) found in the 19th-century accounts, and that the correctness of the construction is made to depend on the figure! Another fascinating manuscript is an Arabic book titled On the Resolution of Doubts in Euclid's Elements and Interpretation of Its Special Meanings written in 1041 A.D. by Ibn al-Haytham. A copy of this book made in 1084 A.D. was found in the University of Istanbul Library [18]. As the title suggests, this is not a translation of the Elements but a discussion about well-known criticisms of Euclid's work. In discussing Euclid's second proposition al-Haytham treats four basic cases in terms of input: (1) point A is either B or C, (2) A lies on the line segment BC, (3) A lies on the line passing through BC, and (4) A lies outside the line passing through BC. In addition to these, he has a very strange case that does not appear to have been mentioned anywhere else, and this is the case w h e n the line segment BC and the point A are separated by a valley or a river so that the line joining the points A and B cannot be drawn! His solution to this last case is most puzzling, for he writes that the way to handle this case is to measure the line segment and redraw it in the neighborhood of the point, after which Euclid's procedure is then applied! It would appear that Ibn al-Haytham was not lacking a sense of humor in his mathematical writings. 20
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
To distinguish a number of cases in this way was foreign to the really classical manner. Thus, as we shall see, Euclid's method is to give one case only, for choice the most difficult, leaving the reader to supply the rest for himself. Where there was a real distinction between cases, sufficient to necessitate a substantial difference in the proof, the practice was to give separate enunciations and proofs altogether. This is, indeed, the social convention followed even today in computational geometry, where the phrase "the remaining cases can be proved in a similar w a y " is seen in almost every published paper in the most scholarly of journals. I conjecture, though, that Euclid saw no cases in Proposition 2 because fundamentally there are not any. Furthermore, if the reader will follow through Euclid's original algorithm in all the possible "fabricated" cases enumerated in the previous section, he or she will find that the algorithm is well defined in the modern sense and will execute correctly and terminate with the correct solution. Furthermore, the proof of correctness also follows through. This cannot be said of any of the subsequent algorithms and proofs offered by Heron, Proclus, and the other Greek commentators of Euclid, nor the 19th-century English scholars. It should be mentioned here that one logical (out-ofcontext) situation consists of Case 1.1.1 in which the point A lies at one end point of segment BC. Clearly, in this pathological situation an equilateral triangle cannot be constructed on AB and the algorithm would be undefined and fail to execute. However, the purpose of the problem is to transfer a distance. If A coincides with either B or C, then the answer, namely, segment BC, is already known at the start. Therefore, the algorithm is clearly intended to work for all points A on the plane except B and C. The reader may experience an interesting effect upon actually carrying out Euclid's construction and proof for all the cases enumerated above, and that is the Eureka experience in which the essence, semantics, or deep structure behind Euclid's construction is m a d e manifest. Once this happens, it is transparently clear that Euclid's algorithm and proof of correctness are
valid for all cases one could possibly imagine. Fundamentally there are indeed no cases. It is difficult to grasp the essence of the algorithmproof by fixing an input configuration and then analyzing variations in constructions as in the work of the Greek commentators. However, the following "trick" makes the essence "jump out of the page at you." We fix the construction instead and for this fixed construction we "look" at all possible input configurations. The crucial part of Euclid's construction (missing in Pedoe's algorithm [27] and missed by most of Euclid's followers) is the cone determined by the rays DE and DF and making an angle of 60 ~ at D. This cone is implicitly constructed by the resulting concatenation of the equilateral triangle DAB and the extensions constructed in Step 3 from A to F and B to E. This cone is as large as desired and always subtends 60~ Consider such a cone as fixed in space and refer to Figure 7. N o w point A must always lie on one ray DF. Also, line segment BC must always have its end point B on the other ray DE. With the compass anchored on B, Euclid's construction first marks off a point G on BE such that BG equals BC. Then with the compass anchored on D, it marks off a point L on AF such that DL equals DG. It is clear that "for all possible configurations of points A and line segments BC the construction is valid. Variation in the distance between A and B does not change the essence of the proof. Furthermore, all possible relative positions of segment BC with respect to point A retain their property of cutting BE at G. It does not matter whether BC is greater than, less than, or equal to AB. Neither does it matter if C lies on AB or DB, or for that matter if it coincides with point A or D! Therefore, the algorithm is well defined and executes in all possible cases.
D
C
C
C
F Figure 7. Illustrating the proof of Euclid's Proposition 2 for all eases.
Because in all cases DB equals DA, it follows that the algorithm yields the correct solution in all cases as well. This then is the logic behind Euclid's proof; and, we might add that, Bertrand Russell [31] and Dunham [12] notwithstanding, it holds without the need of a figure. We see at once Euclid's brilliance in the extension of DA and DB in the directions of A and B to create the cone with apex at D rather than in the direction of D as done by Proclus, for example. It is also easy to see with the aid of this cone that indeed there are no proper cases here at all. The cases fabricated and considered by Euclid's commentators are artifacts of a lack of understanding of the underlying logic which, it is conjectured, Euclid had in mind. In light of the culturally established belief held by so many that Euclid's proofs only hold for certain cases, together with the fact that almost all modern versions of the construction are either ambiguous or downright incorrect, it is easy to understand w h y Pedoe [27] picks only one such case and claims to give Euclid's original proof although it is missing the crucial construction of the cone mentioned above. We close this section with a conjecture as to h o w it came about that so many of the English textbooks contain an incorrect algorithm for Euclid's second proposition. I believe the answer may lie in the famous Latin translation (of an Arabic manuscript by A1-Hajjaj) due to Adelard of Bath [7]. A m o n g the most w e l l - k n o w n medieval English translators of Euclid's Elements was Adelard of Bath in the 12th century. Actually, Adelard of Bath's name is associated with three distinct versions of the Elements; according to Busard [7], it was version II "that became the most popular of the various translations of the Elements produced in the 12th Century and apparently the one most commonly studied in the schools." Furthermore, this version is apparently the least authentic. In the words of Busard, "not only are the enunciations differently expressed but the proofs are very often replaced by instructions for proofs or outlines of proofs." Adelard of Bath writes Step 3 as follows: Protrahanturque linee DA et DB directe usque ad L et G.
His actual letters are different and are here substituted to match those of Figure 5 for ease of discussion. As a minor aside, there is an error (probably typographic?) in this manuscript, that is, L and G are actually reversed. More seriously, E and F are nonexistent, as are the references to producing the lines AF and BE, and the literal translation reads "'Draw forward (extend) lines DA and DB until L and G." The sentence that pervades the English textbooks reads, "Produce lines DA and DB until L and G.'" Thus, one possibility is that Adelard of Bath is responsible for introducing the error. To be sure, it is k n o w n that in the 4thTHE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
21
century Theon of Alexandria's recension of the Elements involved altering the language in some places and sometimes supplying alternative proofs; and according to Busard [7] all the manuscripts of the Elements known until the 19th century were derived from Theon's text. Is Theon the culprit here? Adelard of Bath translated his manuscript from the A1-Hajjaj manuscript in Arabic; one may wonder if AI-Hajjaj is to blame. However, it is generally considered that the Arabic manuscripts are quite trustworthy, and other Latin translations of Arabic manuscripts, such as that of Gerard of Cremona, have a correct algorithm. The finger seems to point in the direction of Adelard of
Bath.
E Figure8. Illustratingthe constructionwith compasses only.
2 0 t h - C e n t u r y Algorithms
These two circles intersect at C and X where X is the desired reflection point of C across the imaginary line through DE, and XA is the desired length.
For the sake of comparison, contrast, and completeness, we offer in this section an alternative modern End construction that is fundamentally different from all In the spirit of Proclus we invite the reader to supply those considered by Euclid, Heron, Proclus, and the the proof of correctness. other Greek and subsequent commentators, as well as the plethora of 19th- and early 20th-century textbook writers. It is based on the notion of mirror symmetry. Conclusions Recall that in 1672 Jorg Mohr and in 1797 the Italian geometer Lorenzo Mascheroni independently proved We mention in closing that even the 20th-century Althat any construction that can be carried out with a gorithm CO pales by comparison with Algorithm Eustraightedge and a compass can be carried out with a clid from the point of view of robustness with respect compass alone. The reader may wonder how on earth to singularities. Consider, for example, the case where we can draw a line segment of length BC with one point C happens to lie at a location equidistant from A extremity at A without using a straightedge. Strictly and B. Algorithm Euclid executes in this case as easily speaking, we cannot, and therefore in constructions of as in any other because everything is well-defined. a line or line segment with compasses alone, we re- Without special flag-waving code, however, Algoquire only that two points on the line or the two end rithm CO could crash attempting to draw a circle with points of the line segment be specified. Thus, we are radius zero and then intersecting two circles, one of actually simulating a line or line segment by two points. which has radius zero. In this sense it is more appropriate to state the MohrOne apparent difference between modern and clasMascheroni theorem as: any construction that can be car- sical computational geometry concerns the issue of ried out with a straightedge and a compass can be simulated lower bounds on the complexity of geometric probwith a compass alone. The above constructions use both lems. Although Lemoine [23] and others were cona straightedge and a compass. It is fitting to end this cerned with defining primitive operations and countdiscussion with a construction that uses a compass ing the number of such operations involved in a cononly. We present the one described in [17] which is struction, they do not appear ever to have considered also the first construction presented in Pedoe [27]. the question of determining the minimum number of operations required to solve a given problem under a Algorithm CO ]Compass Only version]: specified model of computation. For example, if we Input: Let A be the given point and BC the given define (1) drawing a line and (2) drawing a circle as the straight line. [Thus, it is required to place at the point primitive operations allowed under the straightedge A (as an extremity) a straight line equal to the given and compass model of computation, Algorithm Euclid straight line BC.] See Figure 8. takes nine steps, whereas Algorithm CO takes only Begin four steps. Its nonrobustness not withstanding, is AlStep 1: Draw a circle with centre A and radius AB. gorithm CO optimal? In other words, is four a lower Step 2: Draw a circle with centre B and radius BA. (The bound on this problem? Is Algorithm Euclid the optitwo circles intersect at D and E.) mal robust algorithm? It is not difficult to argue that at Step 3: Draw a circle with centre D and radius DC. least three steps are required. I conjecture that, in fact, Step 4: Draw a circle with centre E and radius EC. four are always necessary. 22
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO, 3, 1993
This research suggests that perhaps the chaotic situation described here with respect to Euclid's second proposition exists also for his other propositions involving cases, a n d i n d e e d for all of Greek mathematics. It m a y suggest a n e w w a y of examining old constructive mathematics a n d a n e w approach for historians of mathematics a n d philologists. There are possible implications for education. It has been argued that Euclidean construction problems provide an excellent m e t h o d of teaching high school students constructive proofs of existence theorems [3]. The work presented here suggests that Euclidean constructive geometry can be used as a m e d i u m for teaching m o d e m concepts concerning the design a n d analysis of algorithms to high school students. For easy problems, the students can prove that Euclid's constructions are valid for all possible inputs. For more difficult problems, t h e y can search for constructions that require fewer steps. Finally, for really challenging problems, they can search for constructions that require the fewest n u m b e r of steps.
"Acknowledgments The author is grateful to Hossam E1Gindy for translating Ibn al-Haytham's 11th-century Arabic manuscript [18]; to Mariza Komioti for translating Heiberg's definitive Greek edition [16]; to Kelly Lyons for bringing to his attention a copy of Peyrard's book at Q u e e n s University [28]; to Diane Souvaine, Sue Whitesides, and Chee Yap for discussions on this topic; a n d to A m o n Avron for providing some useful references.
References
11. R. Courant and H. Robbins, What is Mathematics? Oxford: Oxford University Press, 1981. 12. W. Dunham, Journey Through Genius: The Great Theorems of Mathematics, New York: Wiley, 1990. 13. E. J. Dijksterhuis, The First Book of Euclid's Elementa, Leiden: E. J. Brill, 1955. 14. H. S. Hall and F. H. Stevens, A Text-Book of Euclid's Elements, London: Macmillan and Co., 1887. 15. Sir T. L. Heath, The Thirteen Books of Euclid's Elements, Cambridge: Cambridge University Press, 1928. 16. I. L. Heiberg, Euclidis Elementa, Lipsiae: B. G. Teubneri, 1883. 17. R. Honsberger, Ingenuity in Mathematics, New York: Random House, 1970. 18. Ibn al-Haytham, On the Resolution of Doubts in Euclid's Elements and Interpretation of Its Special Meanings, University of Istanbul, 1041 A.D., facsimile edition published by the Institute for the History of Arabic-Islamic Science at the Johann Wolfgang Goethe University, Frankfurt am Main, 1985. 19. G. J. Kayas, Euclide: Les Elements, Paris: Editions du Centre National de la Recherche Scientifique, 1978. 20. F. Klein, Elementary Mathematics from an Advanced Standpoint: Geometry, New York: Dover, 1939. 21. A. Kostovskii, Geometrical Constructions with Compasses Only, Moscow: Mir Publishers, 1986. 22. D. Lardner, The First Six Books of the Elements of Euclid, London: H. G. Bohn, 1861. 23. E. Lemoine, G~om~trographie, Paris: C. Naud, 1902. 24. L. Mascheroni, The Geometry of Compasses, Pavia: University of Pavia, 1797. 25. G. Mohr, The Danish Euclid, Amsterdam, 1672. 26. G. R. Morrow, Proclus: A Commentary on the First Book of Euclid's Elements, Princeton, NJ: Princeton University Press, 1970. 27. D. Pedoe, Geometry and the Liberal Arts, New York: Penguin Books, 1976. 28. F. Peyrard, Les Oeuvres D'Euclide, Traduites Litt~ralement, Paris: C. F. Patris, 1819. 29. J. Playfair, Elements of Geometry; Containing the First Six Books of Euclid, Edinburgh: Bell & Bradfute, 1831. 30. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, New York: Springer-Verlag, 1985. 31. B. Russell, The Autobiography of Bertrand Russell, Boston: Little, Brown & Co., 1951. 32. M. E. Stark and R. C. Archibald, Jacob Steiner's geometrical constructions with a ruler given a fixed circle with its center (translated from the German 1833 edition), Scripta Mathematica, 14 (1948), 189-264. 33. J. H. Smith, Elements of Geometry, London: Rivingtons, 1879. 34. A. S. Smogorzhevskii, The Ruler in Geometrical Constructions, New York: Blaisdell, 1961. 35. H. M. Taylor, Euclid's Elements of Geometry, Cambridge: Cambridge University Press, 1895. 36. I. Todhunter, The Elements of Euclid, Toronto: Copp, Clark & Co., 1876. 37. G. T. Toussaint, Computational geometric thinking as kinesthetic thinking, presented at Conference on Thinking, Harvard University, August 1984. 38. R. Williams, Elements of Euclid Explained and Demonstration in a New and Most Easy Method, London: Globemaker, 1703.
1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Reading, MA: Addison-Wesley, 1974. 2. A. Avron, Theorems on strong constructibility with a compass alone, J. Geometry 30 (1987), 28-35. 3. A. Avron, Construction problems--why and how? Int. ]. Educ. Sci. Technol. 20 (No. 2) (1989), 273-287. 4. A. Avron, On strict constructibility with a compass alone, ]. Geometry, 38 (1990), 12-15. 5. I. Barrow, Euclide's Elements, London: E. Redmayne, 1705. 6. P. Beckman, A History of Pi, New York: The Golem Press, 1971. 7. H. L. L. Busard, The First Latin Translation of Euclid's Elements Commonly Ascribed to Adelard of Bath, Pontifical Institute of Medieval Studies, 1983. 8. H. L. L. Busard, The Latin Translation of the Arabic Version of Euclid's Elements Commonly Ascribed to Gerard de Cremona, Leiden: E. J. Brill, 1984. 9. H. L. L. Busard, The Medieval Latin Translation of Euclid's Elements Made Directly From the Greek, Stuttgart: Franz School of Computer Science McGill University Steiner Verlag Wiesbaden GMBH, 1987. 10. C. Clavio, Euclidis Elementorum, Francofurti: Jonae Rosae, Montreal, Quebec H3A 2A7 Canada 1654.
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993 2 3
ARNE BEURLING COLLECTED W O R K S Edited by LENNART CARLESON, Royal Institute of Technology, Stockholm, Sweden, PAUL MALLIAVIN, Universit6 de Paris VI, JOHN NEUBERGER, University of North Texas, and JOHN WERMER, Brown University FROM THE REVIEWS...
rne Be.urling was a highly creative m a t h e mauclan whose legacy will influence future mathematicians for many years to come, maybe even for generations. He published very selectively and only when all details were resolved; a sizeable part o f his work never appeared in print before being published in these collected works. In total, about 170 pages contain new material. Among m a n y topics covered should be mentioned:
! ! g e u r l i n g ' s publications appeared in a wide aLwvariety of places, so that these two volumes will be indispensable for any library that wants to have adequate coverage of Beurling's work. It is gratifying that the two volumes are relatively inexpensive. T h e seminar lectures and some other material have been translated from Swedish, and have not been published before." -Mathematical Reviews
a) a comprehensive treatment ofextremal length b) a survey of different concepts of quasi-analyticity
Volume One: Complex Analysis 1990 512pp. Hardcover $49.00 ISBN0-8176-3415-0
c) Balayage and interpolation in harmonic analysis
Volume Two: Harmonic Analysis 1990 384pp. Hardcover $49.00 ISBN0-8176-3416-9
Also included are about twenty seminars from Beurling's time in Uppsala, Sweden, 1937-1952, containing interesting material for future research.
Two Volume Set: 1989 896pp. $89.00 ISBN0-8176-3412 from the ContemporaryMathematiciansseries
-Paul Malliavin
Three Easy Ways to Order! Call: Toll-Free 1-800-777-4643. In NJ please call (201) 348-4033. Your reference n u m b e r is Y655. Write: Birkh/iuser, 44 Hartz Way, Secaucus, NJ 07096-2491
Visit: Your Local Technical Bookstore, or urge y o u r librarian to order for y o u r d e p a r t m e n t .
Payment can be made by check, money order or credit card. Please enclose $2.50 for shipping & handling for the first book ($1.00 for each additional book) and add appropriate sales tax if you reside in NY, NJ, MA, VT, PA or CA. Canadian residents please add 7% GST. Prices are valid in North America only, are payable in U.S. currency or its equivalent, and are subject to change without notice. For pricing and ordering information outside North America, contact Birkhauser Verlag AG, P.O. Box 133, Klosterberg 23, CH-4010 Basel, Switzerland. Fax: 41 61 / 271 76 66.
Birkhiiuser
Boston Basel Berlin
The Story of a Friendship: Recollections of Arne Beurling* Lars Ahlfors
Arne Beurling was the best friend I have ever had. We were approximately the same age, and we shared a common mathematical background, the Scandinavian tradition in analysis. The mathematicians most influential in shaping our futures were Torsten Carleman in Sweden and Rolf Nevanlinna in Finland. Our personalities were as different as could be. I was the traditional stodgy, mostly silent Finn, chronologically two years younger, but in reality so immature that I was like a child compared to Arne. In contrast, Arne was a self-assured upper-class Swede with strong convictions and a temper that could flare up and become almost dangerously choleric. H o w was it possible that we could hit it off so well from the moment we met? The answer is that we were both so deeply involved in mathematics that everything else seemed irrelevant. We respected each other, and we recognized a remarkable similarity between our likes and dislikes in mathematics. Typically, after obtaining my first academic degree, I was very happy that my father made it possible for me to go with m y teacher Rolf Nevanlinna to Z~irich, where he was substituting for Hermann Weyl at ETH. This was my first contact with live mathematics, and it opened my eyes to serious thinking as opposed to passive reading.
Meanwhile, Arne's father took his son to Panama to hunt alligators, a rather different approach to parental upbringing. Arne loved it, while I, in his place, w o u l d have tried to get as far away as possible from all guns and alligators. Nevertheless, he must also have had time for very serious mathematics, for w h e n he returned to Sweden,
* This reminiscence is based on his remarks at the memorial for Arne Beurling at the Institute for Advanced Study in 1986. THE M A T H E M A T I C A L INTELL[GENCER VOL. 15, NO. 3 9 1993 Springer-VerlagN e w York 2 5
he looked up Professor Carleman and told him that he had proved the Denjoy conjecture, a problem that had recently been brought back to the limelight by Carleman himself. On learning that a proof had just been published by an obscure young Finn, many mathematicians would have been seriously upset, but not Arne. He realized that the Denjoy conjecture was not very interesting in itself, and by that time he had probably already proved many results which he knew to be more important. It is not unusual that the same or closely related mathematical ideas turn up simultaneously, even in different locations. Arne did not know of me, nor I of Arne, and neither of us had heard of H. Gr6tzsch, a German mathematician who could easily have proved the Denjoy conjecture and later became well known in connection with quasiconformal mappings. The notion of harmonic measure had only recently been introduced by Carleman and further developed by Rolf Nevanlinna, but it had been used only in connection with the classical maximum principle. I believe that Arne and I both realized that there was a gap that needed to be filled in order to treat conformal mappings adequately. My approach was rather pedestrian---enough said but already at this early stage Arne applied a very sophisticated point of view, which later became a cornerstone of his dissertation. Briefly, he replaced a single problem by a class of conformally equivalent problems. This was something entirely new, and typical of his particular genius. Beurling was in no hurry to get into print. It was 1933 before his thesis appeared, and because of the Swedish custom at the time to have all dissertations privately published, it was never easily available. Nevertheless, Beurling's fame spread quickly, and the thesis became one of the most influential mathematical publications of its time. I am not quite sure when I first met Arne, but it was probably at the Scandinavian Congress in Stockholm, 1934. I have a foggy memory of a banquet in Stockholm's City Hall, and of Arne being very concerned that I should find my w a y to my crummy hotel. This soon became a pattern. Arne always thought that I was younger and smaller and could not quite take care of myself, but he was never patronizing, and I came to accept it as the natural thing because of his physical strength and superior coordination. In the beginning we did not meet frequently. There was no air travel, and there were no government agencies one could ask for support. Occasionally, Carleman would invite me for a short stay in Stockholm with access to the Mittag-Leffler Institute, and I could take a side trip to Uppsala, where Arne was teaching. That was enough to keep our friendship alive and growing. Shortly thereafter, things began to look up for me. I got married and was offered a three-year appointment at Harvard University. This was a lucky break, because 26
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
I could broaden my background in mathematics. Unfortunately, it also meant that my contacts with Arne became fewer; but at least we were both busy, and our work had much in common. When my stint at Harvard was over, I returned to Finland. Our oldest daughter was born, and we had one h a p p y year in Helsingfors before the war caught up with us. When the hostilities were imminent, w o m e n and children were ordered to leave Helsingfors. We had no place in Finland to go to, but my wife had a sister in Sweden and it was natural to go there. Travel in wartime is never easy, and for my wife with two very small children it was a nightmare. The so-called winter war lasted 100 days. It was followed by an armistice, and my family could return. The rest is history. Finland re-entered the war on the wrong side, Helsinki was bombed regularly, and my wife went back to Sweden, this time with three children. In the bleakest moment, w h e n it was almost certain that Germany would lose the war and w h e n I had almost given up hope of being reunited with m y family, Switzerland came unexpectedly to my rescue. Out of the blue I received a telegram from the University of Z(irich offering me an Associate Professorship. Naturally, I grabbed at the straw, and to my surprise I was even granted permission to leave the country, but of course without currency of any kind. (I resorted to smuggling my Fields Medal out of Finland and pawning it in Sweden.) All this had nothing to do with Arne Beurling, but the rest of my story is intimately connected with him. To get to Sweden was easy, but once there I was surrounded by enemy countries: by that time Finland was already negotiating a separate peace with the Soviet Union, and the Germans wanted nothing to do with me. Fortunately, the British, although enemies on paper, did not lock the door, but warned me that I was in for a long wait. This is where Arne comes in. Somehow he found out that I was in Sweden, and he at once invited me to Uppsala. There he helped me rent a small room, and he gave me an office in the Mathematics Department. His hospitality knew no bounds. I was a frequent luncheon and dinner guest in his house, and he even arranged for a small income from guest lectures and for acting as official opponent at doctors" dissertations. This was necessary, for the Swiss would not send any money until they were sure I could get there. In Uppsala, Arne and I worked together on the sharp form of Arne's definition of extremal length, which ultimately replaced all earlier versions. The students in Arne's seminar were also interested and helped out with examples and the like. The seminars usually met in the evening, and sometimes a smaller group went for a light supper in a small restaurant. In his good mood Arne was not above playing some innocent pranks. I remember one that amused me a
lot. We came from the restaurant on a mild winter night with plenty of snow. The streets were deserted, but the lights were on. At a crossing there was a very strong light, and Arne could not resist throwing a snowball at it. The chances of hitting it seemed infinitesimal, but the light went out. Arne turned to us and said, "Now we run!", and I can guarantee that everybody ran. In spite of the uncertainty, this was a relatively happy time, but it did not last. Suddenly, tragedy struck me and my family. They had come from Finland to Sweden for safety, but a faulty wire, which should not have been there, gave my year-old son an electric shock which killed him instantly. In the confusion, even the cause of death was not immediately recognized. My wife was able to reach Arne's mother in Uppsala, and it was up to Arne to break the news to me. Never in my life have I witnessed anybody handle such a difficult assignment with greater tact and compassion. It seemed to me that Arne's extraordinary sensitivity had raised our friendship to a level that I had not experienced before, and from that moment on I have come to regard Arne as the personification of what true friendship can be. In addition, Arne was also v e r y practical, and arranged for me to take the night train to Gothenburg where I was united with my wife and daughters. In order to continue on our way to the continent, we still had to wait for the Battle of the Bulge to be over, and then for a moonless night. As soon as the conditions were right, we were flown via the "stratosphere" to Prestwick Airport in Scotland, and from there, with great help from the Swiss embassies in London and Paris, we slowly found our way to Switzerland. The arrival in Z~irich was an anticlimax. We landed in a never-never land that seemed to have had no contact with the war. My first impression was that the University, and perhaps the whole country, had been asleep for a h u n d r e d years. I later revised my opinion, and I am forever grateful for the opportunity I was given to start a new life. I grew very fond of Z~irich, which is still one of my favorite cities, but I was always plagued by the feeling that I had come to the wrong place at the wrong time. I was therefore more than pleased when in less than two years I was asked to return to Harvard. I could leave Z~irich with a good conscience because m y position at the university was upgraded and filled by Rolf Nevanlinna. At Harvard I could teach what I wanted, and I had m a n y excellent students. But the main thing for me is that I was in a position to invite Beurling to Harvard. To my great joy he liked it, and we worked together for two years or more. Our most important paper from this creative period is the one in Acta Mathematica on Conformal Invariants and Function-Theoretic Nullsets, which among other things contains the definitive presentation of the method of extremal length.
My memories from this time are all very precious. My wife and I were living in an apartment near Harvard Square, which we rented from Harvard. There we spent many happy evenings with Arne. Sometimes the evening became morning, and we would sit in our kitchen watching the sun rise over the roofs of Cambridge. At times we would walk across the Harvard Yard toward Arne's lodgings. If he spotted two members of the Harvard police at a distance, he would automatically straighten his back and his walk became very correct. When the police passed us they greeted us very politely with "Good morning gentlemen, have a nice evening." Arne could hardly believe it and said it could not happen in Uppsala. It was inevitable that the Institute for Advanced Study would cast its eyes on Arne, and I cannot blame him for accepting the call. The sad thing was that we started to drift apart. It was natural enough that our mathematical interests would take off in different directions. For a long time we remained best friends, but our meetings were fewer and tended to become more social than mathematical. With the loss of proximity, too many frictions arose that could not be put right at once. Misunderstandings were piled on misunderstandings, and in the end nobody could do anything about it. For far too many years we had no contact whatsoever. Much too late, but better late than never, the arrangers of the Bieberbach celebration in Purdue had the bright idea of inviting both of us as speakers. We both accepted, and each knew that the other had accepted. Arne's health was known to be brittle, and we were not sure that he would be able to make it. But he came, and the old magic worked. He put his hand on my shoulder, and with no words spoken I knew that bygones were bygones. We stayed together at the meeting as much as his health permitted, and we parted as friends. We missed each other when everybody left, but our mutual farewell notes crossed in the mail. This sealed the bargain better than anything else.
In October 1986 I received a telephone call from Karin Beurling who told me that Arne was very ill and wanted to see me. I am forever grateful to Karin for making this possible. When I saw Arne in Princeton he was very sick and obviously in pain, but his mind was clear and he was quite aware of the reason for our meeting. Less than two weeks later I heard again from Karin that Arne was dead and buried. And that was the end of a beautiful friendship.
160 Commonwealth Avenue Boston, MA 02116 USA THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
27
Memories of Arne Beurling,, February 3, 1905-November 20, 1986 Bo Kjellberg
Studies in Uppsala In 1924, when Beurling finished school, there were only two universities in Sweden, in Lund and in Uppsala. He and his close friend, Sven T/icklind, left their home city G6teborg and went to Uppsala to study mathematics. At this time there were only two professors of mathematics in Uppsala: Erik Holmgren, whose field was differential equations, and Anders Wiman, working in function theory, algebra, and geometry. Both were highly respected mathematicians. ! do not have much to tell about Beurling's student years. A main event was the publication in 1933 of his dissertation, "l~tudes sur un probl~me de majoration." It contained sharp results in function theory, introduced "extremal length," etc. It became a rare publication from the start: Besides the compulsory number of copies for the university library, he ordered only 75 extra copies from the printer. Thereafter, he became "docent" at the university, a research position without tenure involving a certain amount of teaching. His friend T/icklind obtained the same type of position after a dissertation about the heat equation.
The lectures were supplemented with a series of problem sessions where the students, one after another, were asked to step forward and present solutions of problems given earlier. We soon discovered that our teacher had a temper. Clumsy solutions seemed to be a personal offense to him. The atmosphere in the room could be explosive. Let me say at once that this has changed over the years. The day came w h e n he asked, "Tell me honestly, do you think I have calmed down in m y relation to the students?" And, telling the truth, I could answer, "Yes, now you have the patience of an angel!" The academic year 1936-37 was his last as a docent.
My First Encounter with Beurling I came to Uppsala in September 1936 and chose to follow the courses in calculus given by Beurling, in differential equations by Holmgren, and in geometry by T/icklind. Already the first lecture by Beurling made an overwhelming impression on me. It was clear and elegant and provoked interest in the subject. My strong feeling of sympathy for the speaker lasted all m y life. 28
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3 9 1993 Springer-Verlag New York
Professor in Uppsala In 1937, he was appointed the successor of Holmgren. Years after, he told me that he had many times missed active encouragement from his teachers. Therefore, on the day of his appointment to professor, he made a firm decision to act differently toward his own future students. In the usual manner, he was solemnly installed as professor in the magnificent festival hall of the university. His inauguration lecture was about the role of logic and intuition in mathematical research. He strongly stressed the decisive role of intuition.
Research and Teaching N o w followed more than 10 years of intense work in Uppsala. He gave a series of lectures about, for instance, analytic functions, entire functions, potential theory, differential equations, Fourier integrals, hydrodynamics, and harmonic analysis. The lectures were excellent, loaded with new results, and, as far as I can remember, never repeated. Most of his time was devoted to hard research activities, often in different directions during the same week. Each year he announced a series of evening seminars on "selected problems." The content of each seminar was generally a surprise to the audience. Often he presented new results from the same day or week. Because of other work, I could never study full-time, but I could attend his seminars most of the years. I tried to make detailed notes. Beurling did not devote much time to preparing his results for immediate printing. So his publications were generally delayed for years. Sometimes he had to ask for my notes to remember what he had done. Quite a number of students became inspired by his seminars and started research in different fields, leading to articles and dissertations. And what of his promise of active support? I can only speak for myself. From his lectures I had learned that little n e w was known about the minimum modulus of entire functions since the fundamental work of Wiman. I decided to write my thesis about that. But m y progress was too slow for Beurling. "From n o w on you should come to me every second month and report some significant results!" And I agreed. It worked for some time. But once I had almost nothing n e w to tell and I had to admit that I had used the time available to construct a sauna. "A sauna, do you understand that you have broken your promise to me?" Yes, I understood. After further efforts, the thesis was finished at last. I wish I could describe h o w Beurling managed to create important n e w results. One impressive factor was his ability to use appropriate theorems from other investigations just at the right moment.
Beurling at work. Photo by Anders Wik, FRA. Personality In general, Beurling was one of the most charming persons you could meet. He had a very strong feeling for justice and fair play. As mentioned earlier, he was very anxious to talk to the students in a kind and friendly way. With colleagues, he could get agitated w h e n he defended his point of view. I remember once I passed his office and heard some explosion within. Out stumbled a visitor, one of the most brilliant mathematicians of our time. "I never thought Beurling could behave like that!" The next day, they could be seen sitting together in cordial discussion. Of course, he scared some people. One day I had a phone call from the administrative chief of the university. "Beurling has applied for more financial support for his group of candidates for the doctorate. But the board has turned it down. My problem now is that the president refuses to sign the protocol because he is afraid of Beurling's reaction. I want to close the case. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
29
Can you help me?" And I answered without hesitation: "Yes, tell the president to sign, no protest will come from Beurling!'" As I had expected, when I told Beurling about the call, as a reasonable man he let the matter rest. However, the meagre financial circumstances may have influenced his later decision to move to the United States.
W o r k for the S w e d i s h D e f e n s e When the Germans invaded Denmark and Norway in 1940 Sweden was in a dangerous position. A large number of radio messages, diplomatic and military, mostly written in cipher, were recorded. The messages became easier to intercept when the Germans hired cables through Sweden to Oslo, Stockholm, and Helsinki. A message could look like this: PSWBETCAQRLTOMDKQYYS . . . . .
The original German G-Schreiber. Photo courtesy of FRA.
30
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
Each letter was built up of 5 elements, each + or - , for instance + - + + - . It turned out later that the German cipher machine was excellent. It was called "G-Schreiber," where G stands for "geheim." Ten wheels gave the possibility of trillions of different settings, so the machine was considered safe by the Germans throughout the war, especially because of successive improvements they introduced. The Swedish agency FRA, charged with decrypting messages from all countries of concern, had the good judgment to ask Beurling for help. He solved the problem in 14 days during the summer of 1940, using all messages from the day May 25, 1940. He found out how the deciphering machine should be constructed and h o w a special setting could be found by a certain amount of hard work and imagination. More than 30 machines were built and began to be used daily.
Each morning from 6 A.M. a mathematician was responsible for finding the principal setting of the day. In general, it was done within a couple of hours. But I remember one morning w h e n I was on duty that I had to struggle until 11 A.M., with dozens of typists waiting for work looking at me hour after hour! It is possible that Beufling's achievement contributed to Sweden's keeping out of the war. All German troop m o v e m e n t s were k n o w n in advance so the Swedish command could take adequate countermeasures. In all, 296,900 secret German messages were decrypted during the war. One day in October 1943 as many as 678 such messages were delivered to the government and to the military command. Some of the facts above are given by Carl-G6sta Borelius, another genius from FRA. 1
The S w e d i s h Mathematical Society During the forties, Beufling began to talk about the necessity of starting a Swedish mathematical society. In 1950, an invitation was sent out for a first meeting in the old castle Skokloster, between Uppsala and Stockholm. I remember an amusing talk with the innkeeper when we went to discuss the dinner. Beurling wanted a lavish meal beginning with some 10 sorts of herring, typically Swedish! A high price was demanded. He remonstrated: Last year he had attended a conference in another castle with the same dinner for half the price. ANSWER: "That innkeeper has gone bankrupt since then, that is not m y intention!" So the dinner had to be simpler. Beurling was elected first chairman and the society is still flourishing.
A Beurling clock. From the archive of the Nordic Museum, Stockholm.
Among his ancestors he especially mentioned his grandfather's grandfather, the royal clockmaker Pehr
Beurling. He lived 200 years ago during the reigns of King Gustav III and King Gustav IV Adolf. Like the mathematical theorems of Arne Beurling, the golden clocks of Pehr Beurling are characterized by elegance and precision. These clocks are still in use in official buildings and homes. Arne Beufling's parents were the estate owner Konrad Beurling and his wife Eva Raab. His son PehrHenrik began to study mathematics under the guidance of Carleson, but passed away early with a kidney disease. His daughter Christina accompanied her father to the United States and is n o w professor in California. Beurling's wife, Karin, continues to live in Princeton near the Institute.
i R e a d e r s m a y c o m p a r e this a s t o n i s h i n g a c c o u n t w i t h that by David Kahn in The Code Breakers (Signet, N e w York 1973).--Editor
G6kdrtsviigen 115 183 44 Tiiby Sweden
Leaving for Princeton I guess that the opportunities in Sweden were too limited for him. Anyhow, in 1948-49 he took a leave of absence to become visiting professor at Harvard, and in the early fifties at Princeton, where he remained as a permanent member of the Institute in 1954. A worthy successor in Uppsala was Lennart Carleson.
Family
THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3, 1993 31
Recollections of Arne Beurling John Wermer
At the end of my first year of graduate school, in 1948, I heard that a Swedish professor named Arne Beurling was coming to visit Harvard in the fall and to teach a course in analysis. During the summer, I did some independent work, away from Harvard. In particular, I studied the behavior of the distance from a fixed point in a Banach space to a point on a straight line. During four or five weeks, I made progress on some examples, but was not able to prove a general result. When the fall semester started, I attended Beurling's course. I had not spoken with him. In the first few minutes of his first class he gave the (simple) solution of the problem I had been trying to solve. It was a good beginning for an acquaintance. Beurling's course was like nothing I had seen. He lectured on a great variety of problems in analysis, mostly pure but some applied, and virtually all of it on his own work on these problems. The audience, besides some innocents like myself, contained Lars Ahlfors, Raphael Salem, Izzy Hirschman, and James Jenkins. The lectures were enchanting, and, except for some small points (what sounded like "preaction" was "projection"), I had no trouble with his English. Harvard graduate students in analysis in those days were pretty well divided into solidly classical analysts working with Ahlfors or Widder or Walsh, and fiercely abstract analysts studying with Loomis and Mackey. The latter group, which included me, struggled mightily with the course, and must have seemed amazingly naive to Beurling. "You Harvard boys are afraid of integral signs!" he exclaimed on one occasion. Beurling enjoyed teaching his course. Among other graduate students in the class, I remember Henry Pollak, Henry Helson, Philip Davis, and Chandler Davis. For the following academic year, Beurling returned to Uppsala, and I followed him there. I was one of his eight research students at Uppsala that year. The other profes32
sor of mathematics, Trygve Nagell, in algebraic number theory, had one doctoral student. The "undergraduate" teaching was mostly done by the docents, Broman, Kjellberg, and Borg, and the assistants. The docents had been Beurling's earlier Ph.D. students. Beurling gave the oral exam to the undergraduates who had passed the written exam. As I remember it, 8 of the 60 students who took the written exam survived it and went on to take the oral. This was rather unlike the American model. On Tuesday evenings, after supper, Beurling gave a seminar on his most recent research. The entire analysis group attended the seminar. I imagine that the enormous work load on Beurling played a big role in his decision to leave Uppsala for the Institute in Princeton in the mid-1950s.
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3 (~)1993 Springer-Verlag New York
In 1976-77, Lennart Carleson organized a "Beurling Year" at the Mittag-Leffier Institute in Djursholm in
Sweden, and Beurling gave a series of lectures, which traced the development of some of his main mathematical ideas starting from the 1930s. Carleson and I wrote up the notes on these lectures, and these appear in his Collected Works. These lectures were fascinating. They begin with his original idea of obtaining conformal invariants by means of extremal distance. This geometric theory leads to powerful inequalities for harmonic measure, and these estimates, in turn, yield some striking consequences in function theory. The proofs are short and deep at the same time. He next uses harmonic measure estimates to build a theory of quasianalytic classes, and then uses this theory to derive results in approximation theory. The ideas of quasianalyticity form a connecting thread for many parts of Beurling's later work, in particular in the study of the spectrum of a function in harmonic analysis. Over and over again, his work showed how, by thinking deeply about a problem in classical analysis, it is possible to throw light on huge areas of mathematics. The gap between "abstract" and "concrete" vanishes. A famous instance of this is Beurling's 1949 paper "On two "problems concerning linear transformations in Hilbert space." This paper, together with yon Neumann's inequality for contractions on Hilbert space from 1951, is basic to modern operator theory. Another instance is his 1938 paper "Sur les int6grales de Fourier absolument convergentes et leur application a une transformation fonctionnelle." In this paper, his study of Tauberian theorems led him to fundamental discoveries about Banach algebras. Beurling had an intensely personal relationship with the mathematics he worked on and a complete mastery of much of classical analysis. He could contribute incisive ideas to many problems which people brought to him. As a result, he made a profound impression on all mathematicians who came in close contact with him. Outside of the mathematical sphere he was manysided. He was very much an outdoorsman, keenly interested in sailing and fishing. My wife Kerstin and I often visited him and his wife Karin in Princeton. Our visits there began with mathematics and ended with a feast served up by Karin. In all his years in Princeton, he remained a man of two countries, Sweden and America. The Institute did not provide random samples of the U.S. electorate, and he said before the 1980 election that he could not believe that the American people would elect Ronald Reagan as president. We made a $10 bet, and he paid up, but I never cashed the check.
Department of Mathematics Brown University Providence, R102912 USA THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
33
Beurling's Analyticity Theorem J. w. Neuberger
In 1967, I sent some reprints to the Institute for Advanced Study as part of an application for a visiting membership. In one of these papers [5], Arne Beurling saw a result of mine which suggested to him a conjecture which he subsequently proved. The result is still scarcely known. It is a real variable result whose proof uses some complex analysis and harmonic analysis. It has implications for the study of one-parameter semigroups of operators, Markov processes, structure of Banach spaces, and certain aspects of chaos theory. It is the intent of this article to describe the result, give the setting under which it was found, and indicate some of its implications. I also hope to contribute to a fuller picture of Beufling. First, I describe what Beurling saw which led to the discovery of his theorem. We need some notation for higher-order finite differences:
There is the following easy consequence: THEOREM 2. Suppose G is a collection of continuous realvalued functions on [0,1] so that if f E G, there is M,~ > 0 so that ]Af(n;u,8)] <~ M(2 - e)" provided [u,u + ~n] C [0,1]. Then G is quasi-analytic in the sense that no two distinct members of G agree on an open subset of [0,1].
k=0
where f is a real- or complex-valued function, n is a positive integer, and u,8 E R, so that [u,u + 8n] is a subset of D(t), the domain of f. Note that ]~f(n;u,5) l <~ 2nM if M is a bound for f on [u,u + 8n]. In 1963, there appeared in [5] the following: THEOREM 1. Suppose f is a continuous function on [0,1] so that (1) f(t) = O, 0 ~ t ~ 1/2, and (2) if ~ > O, there is t E [~/2,V2
q-
(~] SO that fit) ~ O.
Then if V2 < a < 1, lim~__,o+ supa~s,~l [Af(n;O,~)[v" = 2. 34
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3 9 1993 Springer-VerlagNew York
Theorem 2 is in the first paragraph of [5]. I strongly suspect that Beurling never read any further in the paper. In early 1968, I arrived at IAS to start a threemonth stay there. On m y arrival there, I found a note from Beurling inviting me to stop by his office. He commenced to describe his thoughts upon seeing the above Theorem 2: "I said to myself, 'Why, these functions are analytic I can't prove it but I know it is true.' " He went on to indicate that he had worked fairly hard to prove that his first impression was correct. To be precise, he showed the following: THEOREM 3 (Beurling). Suppose that f is a continuous function on [-4,4]. Suppose that 3/2 ~< 0 < 2 and set o~ = (2 - 9)/4. Suppose
unpublished work. Some of it is from lecture notes, much of which was translated from Swedish by Lennart Carleson. We now describe two areas connected with Beurling's theorem. The first indicates connections with quasi-analytic collections and the study of certain aspects of chaotic behavior. The second concerns relationships with the study of semigroups of linear transformations. C o n n e c t i o n s w i t h the S t u d y of Quasi-analyticity
Quasi-analytic collections have been studied by Denjoy, Carleman, S. Bernstein, S. Mandelbrojt, as well as Beurling and others. In Beurling's collected works ]dif(n;u,8)] <~ p" there is a section devoted to his previously unpublished work on quasi-analyticity. The ninth and last whenever [u,u + 8n] C [-4,4]. There is an absolute conpart of this section contains a statement and proof of stant k so that f is analytic in the rhombus with vertices his analyticity theorem. Even though his motivation (--4,0), (0,-+4kcx2). for the conjecture came from an article [5] on quasianalyticity, it does not seem that he himself made any He gave me a handwritten proof at this time. He further connection b e t w e e n his result and quasigives analyticity. Nevertheless, his result has other conneck = 1/(4we) tions with the subject. Beurling discussed quasi-analyticity very little with which he asserts is NOT the best constant. Not having me. I got the impression that he felt that the subject the best constant in an otherwise nice result would was, in a sense, closed out by his own work. When I always annoy Beurling--that alone would be sufficient first arrived at IAS, he gave me a copy of his (unpubgrounds to delay publication indefinitely. lished, of course) Stanford Lecture Notes (these are Lars H6rmander, who also was at IAS at the time, essentially included, but not by name, as previously showed me an elegant argument in the periodic case. unpublished work in [2]). He said, "Come back w h e n Roughly speaking, H6rmander's argument uses Fou- you understand these." Three weeks later I returned, rier series, but the more difficult general case of Beurl- having absorbed perhaps one percent of the material hag requires Fourier integrals. he gave me. The part of m y own work on quasiBeurling surprised me by asking me to publish his analyticity which is related to Beurling's analyticity result (giving him credit, of course). It is m y guess that theorem may eventually be shown to follow from his he would have published it himself had he had the work on quasi-analyficity. I hope anyone who does best constant k. I certainly felt ambivalent about the figure out how to do it, will let me know. prospect of merely typing his two-page handwritten To be more specific on these connections, we can use paper, adding one sentence of my own like "A. Beurl- some more notation: ing did the following" and then submitting this to Suppose that S is a closed and bounded interval and some journal under m y own name. (Some years later, f is a continuous function whose domain includes S. Ed Hewitt, upon hearing this story, said simply, "You For 0 < ~ < ISI, define should have done it.") Much later I realized that I might have submitted such a paper to Beufling, who 4,ff, ,S) = sup IAt(n;u,a)l TM. was an editor of the Journal of Functional Analysis. It [u,u+SnlCS then might have appeared as "Communicated by Arne Beurling." Beurling clearly liked the result. The "2" in Since, for [u,u + 8n] C S, "2 - 9" in the theorem is certainly best possible; if only the best "k'" could somehow . . . . laf(n;u,8)l ~ 2 n sup~(x)l, A proof finally appeared in Beurling's collected xES works in 1989 ([2], v. 1, pp. 429-431). In fact, the existence of this unpublished result led me to mention (in it follows that about 1980) to G.-C. Rota that Beurling's collected works should be published. These collected works are lim sup ~((,8,S) ~< 2. 8--*O+ distinguished in containing a large body of previously THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3, 1993 3 ~
In this notation, one may restate (omitting mention of some specific constants) Beurling's result:
THEOREM. If lim supa--~o+ 6(f,8,S) < 2, then f is realanalytic on the interior of S. We call f chaotic at x E int(D(f)) provided that for each subinterval S of D(f) having x in its interior lim 6~,8,S) = 2. ~--*0+
The function f being chaotic at x is indicative of roughly f being hopelessly oscillatory (looking at higher-order differences) in any neighborhood of x on arbitrarily fine microscopic scales. [The interested reader might figure out higher-order differences for the f defined as follows: f(t) = O, 0 ~ t ~ 1/2, f(t) = t - 1/2, 1/2 ~ t ~ 1. In [8], there is a BASIC code which does this for you, whatever the definition of f may be on [1/2,1].] Now, if f is not chaotic at x E int(D~), there is an interval S having x in its interior so that lim inf 6(~,8,S) < 2. 8--*0+
A first question to ask about this definition is whether being nonchaotic at x ~ int(Dq)) implies by Beurling's theorem that f is analytic at x. The answer is in the negative. The Hardy-Weierstrass continuous nowhere differentiable function f,
Fourier series (or Fourier integral) can be written as the sum of two nowhere chaotic functions [just split the series into two series in such a way that both of the created series have appropriate gaps (see [9])]. A recent [10] construction of this writer gives a method of continuation for nonchaotic functions. The construction is vaguely reminiscent of analytic continuation. Here is a connection with the study of quasi-analytic collections. For each sequence cr = 81, 8 2 . . . . decreasing to zero and each interval S, define G(cr, S) as the set of all continuous real-valued functions f on S for which there are M,e > 0 so that
IAi(n;u, Sk)l ~
M(2 - e)l/,
provided n,k ~ 77+ and [u,u + 8kn ] C S. It is an easy consequence of Theorem 1 that G(r is a quasianalytic collection. Moreover, if f is nonchaotic at x E int(D~), then ]~s E G(cr, S) for some interval containing x in its interior. Without Beurling's theorem, I might well have labored on determining wonderful properties of members of G in Theorem 2 without, of course, realizing that I was working with analytic functions. Imagine someone spending years studying linear transformations on locally compact Banach spaces without realizing that such a study is just finite-dimensional linear algebra!
Connections with Semigroups of Linear Operators
oo
f(t) = ~
3 -k COs(3kt), t E R ,
k=O
is nowhere chaotic. Generally, functions whose Fourier spectrum has sufficiently large gaps are nowhere chaotic [6], [7], [9]. This can be seen directly by getting an expression for higher-order differences of Fourier series or Fourier integrals: If f(t) = R e ~
ck eat
t ~ R,
kET_
By "semigroup," we mean here a function T from [0,~) to L(X,X), where X is a Banach space. We assume that T(0) = I and T(s)T(t) = T(t + s), t,s >I O. Moreover, we assume that if x E X and z(t) = T(t)x, t >I 0, then z is continuous; that is, that T is strongly continuous. The generator A of T has domain D(A) = {x E X : lima__,0+ (1/8) (T(8) - /)x exists},
and for x E D(A), A x is the above limit. It is known that A E L(X,X) if and only if T is continuous in the operator norm, that is,
then lim
Al(n,u,8 ) = Re ~
Ck eiku(eika - 1)",
n E 77+, u,8 E ~.
IT(8) -
II = 0.
~-~0+
kET_
If, for some 81, 8 2 . . . . decreasing to zero, ck = 0 for those k so that kS, is close to an odd multiple of ~r for some integer n, then the resulting function f will be nowhere chaotic (see [9] for a precise statement). Furthermore, nonchaotic functions are very common. For example, any function with an absolutely convergent 36
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
The generator A is always closed and densely defined, but is continuous if and only if it is everywhere defined. For x E X, g E X*, the function f on [0,~) defined by fit) = g(T(t)x),
t >t O,
will be referred to as a functional of a trajectory of T. The main connecting point between semigroups and the earlier part of this article is the observation that for f a functional of a trajectory, as above,
David Kendall ([4], or see [7]) used Theorem 1 in his study of Markov semigroups for denumerable processes: Suppose that each of pq is a continuous function on [0,~), and (i) Pij(U + v) = Y'ff=oPik(U)Pkj(V), U,V >~ O,
Af(n;u,8) = g((T(8) -
l)"T(u)x),
u,~ >~ O,x ~ X, g E X*, n E Z +. The one time w h e n I was really tempted to comply with Beurling's request (to publish Beurling's theorem) occurred when I found the following result. Its proof relies entirely on Beurling's theorem.
THEOREM
4. Sup p o s e T is a strongly continuous semi-
group on Xand lim sup~_,o+lT(~ ) - I I < 2. Then AT(t) E L(X,X) for all t > O. It was observed, in the course of the argument for this theorem, that every functional of a trajectory of T is real-analytic. This result was informally announced. It evidently stirred up some interest. For one thing, Beurling heard about this use of his theorem (every time I saw him after that our discussion would start with a lecture on h o w I should be careful with his unpublished work). Beurling himself rather quickly wrote a paper ([1], [2], pp. 317-331 with corrections) which gave necessary and sufficient conditions for a semigroup [strongly continuous on (0,o0), not necessarily even defined at 0 nor approaching I in any meaningful sense at 0] to be holomorphic. The reader should see [1] or [2] for a complete statement and proof of Beurling's holomorphic semigroup result. [A holomorphic semigroup is one which can be extended into a wedge in the right half of the complex plane so that T is actually analytic in that wedge; such semigroups necessarily have the property that AT(t) E L(X,X), t > 0.] The article [1] does not contain a statement of Beurling's analyticity theorem. One conceivably might discern the theorem from [1], but that seems unlikely. In [7], I stated the analyticity theorem and referred to [1]. It would be another 16 years before a proof would finally be available. Kato [3] also published in 1970 a characterization of holomorphic semigroups centering about IT(g) - II, > 0; his argument is independent of Beurling's theorem. In [11], Beufling's theorem on holomorphic semigroups in [1] was used to prove a Banach space structure theorem. Pisier later told me that he did not know about the analyticity theorem when he wrote [11]. The analyticity theorem can be applied directly to prove the major part of [1]. I raised the question with Pisier about applying the analyticity theorem directly to his work, that is, without bringing in semigroups at all.
(ii) E~= lpij(t) = 1,
t >- O,
(iii) limit0+ Pij(t) = 8q. Define the semigroup T by oc
(T(t)x)j = Z
t>~O, x E l l , j = 0 , 1
xiPij(t),
.....
i=0
Kendall shows that IT(t) -
II
= 2(1 - g(t)), where
g(t) = inf pii(t),
t >! O.
i>~O
We see n o w that the probabilistically significant condition lira inf g(t) > 0 t-*0+
holds if and only if lim sup
IT(t)
- I[ < 2.
t-*0+
In light of Beurling's theorem, all Pij, i,j = 0, 1, 2 . . . . are real-analytic on [0,~) (although this was not known at the time of Kendall's paper). In an attempt to complete a picture, we ask about implications of the condition lim inf IT(t) - II < 2. t-*0+
In Kendall's case this would hold if and only if lim sup g(t) > O. t---*0+
It is an easy consequence of Theorem 1 that THEOREM 5. Suppose T is a strongly continuous semigroup on the Banach space X and lim inf IT(t) - I I < 2. t-*0+
Then every functional of a trajectory of T is everywhere nonchaotic. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993 3 7
Note that if the inequality in the hypothesis fails, then lim IT(t) - II = 2 t---~0+
if IT(t)[ ~< 1, t /> 0, as in the case of Kendall's semigroup. Put another way, all the functionals of trajectories of T belong to the quasi-analytic collection G(cr,[0,oo)), is a sequence decreasing to 0 in where rr = 81, 8 2 . . . . such a w a y that lim [T(Sn) - I[ < 2. y/----)~
In this case, we might use the continuation theorem in [10] to reconstruct an entire functional of a trajectory of T from any given part of it on an interval. In closing, I pass on Beurling's last advice to me: "Leave the really difficult things to others, concentrate on those things about which you have some insight." Incredibly, he actually t h o u g h t he was doing that himself! References
1. A. Beufling, On analytic extension of semigroups of operators, J. Funct. Anal. 6 (1970), 387-400. 2. CollectedWorks of Arne Beurling (L. Carleson, P. Malliavin, J. Neuberger, J. Wermer, eds.), Boston: Birkh/iuser (1989), Vols. 1 and 2. 3. T. Kato, A characterization of holomorphic semigroups, Proc. Amer. Math. Soc. 25 (1970), 91-94. 4. D. G. Kendall, Some recent developments in the theory of denumerable Markov processes, Transactions of Fourth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes: Academia Prague (1967), 1127. 5. J. W. Neuberger, A quasi-analyticity condition in terms of finite differences, Proc. London Math. Soc. (3) 14 (1964), 245-259. 6. J. W. Neuberger, Quasi-analytic collections containing Fourier series which are not infinitely differentiable, J. London Math. Soc. 43 (1968), 612-616. 7. J. W. N e u b e r g e r , Quasi-analyticity and semigroups, Bull. Amer. Math. Soc. 78 (1972), 909-922. 8. J. W. Neuberger, Chaos and higher-order differences," Proc. Amer. Math. Soc. 101 (1987), 45-50. 9. J. W. Neuberger, Quasi-analytic collections of square integrable functions, Bull. London Math. Soc. 20 (1988), 321326. 10. J. W. Neuberger, Predictability in absence of chaos, Jour. Math. Anal. and Appl. (to appear). 11. G. Pisier, Holomorphic semigroups and the geometry of Banach Spaces, Ann. Math (2) 115 (1982), 375-392.
Department of Mathematics University of North Texas Denton, TX 76203 USA 38
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
Call for Information Birkh/iuser Boston wishes to a n n o u n c e that Professor R. Daniel Mauldin of the University of North Texas has agreed to prepare a revised version of The Scottish Book: Mathematics from the Scottish Cafd. Originally published in 1981 from a manuscript translated a n d maintained by Stan Ulam and circulated privately, the book contains the approximately 190 problems originally recorded in the famous Scottish Caf6 notebook kept by Banach, Mazur, Ulam, and others--s u p p l e m e n t e d by c o m m e n t a r y on progress to that time on the solutions of the various problems. Professor Mauldin w o u l d be most grateful to a n y o n e w h o would contribute c o m m e n t a r y on progress since 1981 or point out references to such developments. Letters with contributed information should be sent to Edwin F. Beschler Birkhfiuser Boston 675 Massachusetts Avenue Cambridge, M A 02139 USA e-maih
[email protected], corn
Jeremy J. Gray*
A Brief Collaboration: Hans Heilbronn and E.H. Linfoot, 1933-1935 Joyce Linfoot The collected papers of Hans Arnold Heilbronn have recently been published by the Canadian Mathematical Society [1]. Besides the papers themselves and commentaries on them, the book contains the Royal Society's obituary notice, and many articles from personal friends and colleagues. Most periods of his life are well covered in these accounts, but the interval from November 1933 when Heilbronn first came to England to June 1935 when he left Bristol for Cambridge, has received little attention. Yet it was during this time that Heilbronn published a much acclaimed paper, and two months later, with E.H. Linfoot, a sequel in which a further advance was made. This is an account of that period. Heilbronn, who had been working in G6ttingen as Edmund Landau's assistant, was in 1933 dismissed from his post, like many other German university teachers, as a consequence of the anti-Semitic laws passed in that year by the National Socialist Government. Recognising, as he himself said, that he had "no further possibility of scientific work in Germany," Heilbronn made for England, with little money (enough, he estimated, to keep himself for six months), but with excellent recommendations from Landau, and from Harold Davenport of Cambridge, who had spent the summer talent-spotting (as it might now be called) in Germany. He rated Heilbronn as "one of the most promising of the younger men." On arrival, Heilbronn went first to Cambridge, where he took lodgings, and Davenport wrote on his behalf
to the Academic Assistance Council (AAC) 1, which was trying to coordinate the placement of academic refugees. 1 The archives of the Academic Assistance Council (as it then was) are n o w in the Bodleian Library, Oxford. I have read all the documents in these archives referring to Heilbronn, and the attempts to find a grant for his support.
* C o l u m n Editor's address: Faculty of Mathematics, The Open University, Milton Keynes, MK7 6AA, England. THE MATHEMATICALINTELL1GENCERVOL.15, NO. 3 (~1993 Springer-Verlag New York 39
The Council had already compiled a list of university teachers requiring assistance, but Heilbronn was sent a form to fill in. He declared that he was of Jewish descent and religion, could read English fluently, and was willing to go to any country where he could have access to a good library. His name was added to the list, but he was w a r n e d that there was little chance of a grant. Heilbronn then went to see Mordell in Manchester. MordeU was anxious to have him as a collaborator, and prevailed on the Vice-Chancellor to write to the AAC
with an offer of accommodation, but he also asked for a grant. The same answer was returned: Their funds were exhausted; no grants were available. Professor G.H. Hardy wrote from Cambridge; he had no more success. But Professor H.R. Hass4, Head of the Department of Mathematics at the University of Bristol, wrote, "I am considering the possibility of inviting a young German Jewish mathematician to take a temporary position in Bristol." He mentioned Heilbronn, and added that he was trying to raise a salary of s p.a., and had asked the local Jewish community for their help. This proved to be the key. The AAC replied that their grants to single men had been s but that if such a sum could be raised locally, they might be able to consider a small grant to help with accommodation. Fortunately Professor Hasse proved to be an excellent fund-raiser. The Jewish community promised s p.a. for 3 years, and promises totalling s p.a. came from other sources, including University colleagues. Hasse reported this to the AAC, adding that he had hopes of more, and that accommodation would be provided at Wills Hall. Heilbronn was invited to come. This was an act of pure benevolence on the part of most of the subscribers, few of whom knew much about the man they were rescuing, still fewer anything about his work. The one man who did know, and had read his papers, was E.H. Linfoot, who had recently become the assistant lecturer in the department of mathematics. Linfoot strongly supported the invitation. Probably he suggested it in the first place. Linfoot had lived in G6ttingen, and had attended Landau's lectures. He knew (all G6ttingen knew!) what stringent demands Landau used to make on his assistants, and how high his standards were. To have held such an appointment was a very solid recommendation. Further, Linfoot's recent knowledge of Germany made him realise that "time was of the essence." How close Heilbronn and Linfoot were to each other in age, outlook, and mathematical experience can be seen from the following summaries:
Linfoot: Born in June 1905, educated at King Edward VII
Dr. E.H. Linfoot, 1955 40
T ~ MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
School, Sheffield, he won a Balliol scholarship in 1922, and went up two years later. His first paper was published in 1926. In 1928 he took an Oxford D.Phil., and then spent two semesters in G6ttingen, where he attended lectures by Landau, Harald Bohr, and Artin. By 1929 he had published six papers (three in the Journal of the London Mathematical Society). He then spent 2 years in Princeton on a Jane Eliza Procter Fellowship. While there he completed a book on Almost Periodic Functions, which however remained unpublished. He spent the academic year 1931/2 teaching in Balliol. By 1933 he had produced with C.J.A. Evelyn a series of six papers in the additive theory of numbers, and two papers with L.S. Bosanquet (in Quart. J. Math.) concerned with the summability of Fourier series.
Heilbronn: Born in November 1908, educated at a Realgymnasium in Berlin. He entered Berlin University in 1926. He later transferred to Freiburg, and finally to G6ttingen. In 1930 he became Professor Landau's assistant. He obtained his D.Phil. early in 1933 with a thesis on G. Hoheisel's prime number theorem. By the time he left Germany at the end of 1933, he had published six papers, three with Landau. Linfoot spoke excellent German, and Heilbronn quite good English, which rapidly improved. Habitually, they spoke English to one another, recognising that for Heilbronn it was vital to attain normal fluency in the language as soon as possible. It was arranged that Heilbronn should come to Bristol at the beginning of the spring term, on 16th January 1934. Hass6 (it was like him) went to the station to meet him, and took him to Wills Hall. Linfoot was also living there, and this made it very easy for them to work together. It was quite soon after this that I myself first met Heilbronn. I had come down from Cambridge in 1932 and was teaching in a Bristol school. Linfoot and I became officially engaged that summer; we were married a year later. Naturally I often went to Wills Hall. Sometimes . Heilbronn and Linfoot would be talking mathematics, and I was happy to listen for a time, even when I could not understand. I could tell how well things were going. Heilbronn's paper [2], his first in English, was received in March 1934 and published in VoI. 5 of the Quarterly Journal of Mathematics. Two months later the joint paper [3] was sent in and appeared in the same volume. The first paper caused some excitement in the mathematical world. Landau wrote enthusiastically to the AAC that Heilbronn was a scholar of the first rank, and that his work had already brought results with which his name would remain associated in the history of the subject, while Hardy wrote, "He has finished an exceptional piece of work which will make a considerable sensation when it appears." Heilbronn had in fact proved a conjecture made by Gauss more than a hundred years earlier which had remained unproved ever since, in spite of vigorous attacks by many well-known mathematicians using a variety of methods. The original conjecture, on Gaussian quadratic forms, had been shown equivalent to one on the class number of imaginary quadratic fields. Hecke in 1918 had turned it into an analytic question, showing that it would follow from conjectured results on the zeros of the Riemann zeta-function and Dirichlet L-function. Deuring had gone part way to proving it in the opposite case, and Heilbronn succeeded in bridging the gap between the previous two results. The joint paper which followed (the eighth for Heilbronn and the sixteenth for Linfoot) developed the ideas further. It had in fact been necessary to get the paper [2] published as quickly as possible. Heilbronn's position in Bristol was very temporary, and until he had assured
Hans Heilbronn,
c. 1 9 3 4
THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3,1993 4 1
support there was no prospect of getting his family out of German~ where the position for Jews was becoming intolerable. After Hardy had read the paper (he was sent a copy prior to publication), he found a Fellowship Fund that enabled him to guarantee Heilbronn support for 5 years. Heilbronn at once got permission through the AAC to bring to England his mother, father, and young sister, and in July 1934 he went to Germany to fetch them. To celebrate their mathematical success, Heilbronn and Linfoot planned a colloquium to take place at Wills Hall in June 1935. Professor Hass~, w h o was delighted that things had turned out so well, arranged that the halfdozen or so invited participants should be guests of the Department. There is a file of correspondence about the arrangements, with letters from most of those who took part. The youngest person there was Paul Erd6s, who was then working as a visiting student at the University of Manchester. (Two years ago, I was able to speak to him after his lecture to ICME 6 at Budapest, and he remembers it well.) The program (see below) was afterwards sent to the Mathematical Gazette. In the middle of this file is a letter to Linfoot from Heilbronn, who was spending Easter in Manchester. After news of Mordell and Erd6s, he adds, "Apart from this I have to tell you that I was offered yesterday, to my greatest surprise, a fellowship at Trinity College, Cambridge. I can hardly believe in so much luck." This news, when it broke, added very much to the success of the colloquium. It became, in fact, a celebratory occasion, and a report of the proceedings was written. In January 1936, Heilbronn wrote from Cambridge, "I have distributed the Colloquium reports, and they have been accepted with delight everywhere." His personal copy is now preserved by John Friedlander at the University of Toronto. Heilbronn took up his fellowship in the summer of 1935, and after that, he and Linfoot could only meet occasionally. Heilbronn and Davenport began working together (this was, after all, implied by the award), and by October Heilbronn found his time well filled. (In 1935 and 1936, Heilbronn and Davenport published six joint papers, and besides this Heilbronn published two papers in German, one alone, and one with Landau and Scherk.) But in 1936 Linfoot had a Ph.D. student who was submitting a thesis, and he invited Heilbronn to be the external examiner. On 18th November, Heilbronn wrote, "I feel it would facilitate our task considerably if we could communicate with each other personally. Unfortunately I am rather busy this term, but if you were to come here in about 10 or 12 days' time, I should be delighted to put you up. We have a feast on Thursday, 30th November and the dinner is worth being considered. So I recommend that date for your special attention." In about a month's time, Linfoot would go to Cambridge again. Heilbronn wrote in January, "Would you care to speak in Hardy's conversation class on Tuesday at 5:00 p.m.? Please let me know your answer and the title of your lecture as soon as possible as the invita42 THEMATHEMATICAL INTELLIGENCERVOL.15,NO.3,1993
G.H. Hardy, 1930
tions usually go out on Thursday." A few days later, Heilbronn wrote, "Thanks for your prompt reply. I am very glad you are going to speak on the princ, id. Thm. But I should point out to you that very few people in Cambridge know much about algebraic numbers and that it may be wise to make the lecture as elementary as possible." But by this time Linfoot had begun to think seriously of changing the field of his research. The news coming out of Germany had become more and more disquieting, and he now felt that war was inevitable. He knew that he was unfit for military service, and turned to research in instrumental optics as the most useful thing he could do. The subject had always appealed to him, and now he would be able to combine the practical skills which he learnt from Cyril Burch in the Wills Physics Laboratory with his theoretical knowledge of Fourier Series and Fourier Transforms. This meant that he could both design and make new types of optical systems. He might be able to do something to reduce the formidable lead that the German firm of Zeiss held in optical technology. In 1939, at the end of May, Heilbronn invited us for a weekend, Linfoot to stay at Trinity and myself with his family, who had meanwhile settled in Cambridge. It was hot and sunny weather, and on the Saturday afternoon he took us out on the river: his sister, Linfoot, and myself. Somehow he had found time to learn to manage a punt on the Cam. I believe I was given the paddle, but it was quite unnecessary. Before turning back, he moored by the bank, and we talked for a while. Linfoot and I were still in a fairly early stage of our marriage; I had had to give up my school work, as was customary in those days for a woman when she married, and I was rather dismayed to find how much more difficult it was, for me, to look after a house and a husband than to teach mathematics. Suddenly I heard myself saying, "It sometimes seems incredible to me that some people can earn their living just by talking." Hans looked hard at me, and asked, "Does that include me?" I had to admit that, although that was not what I had been thinking of, I supposed it did. No more was said then, but some time later he unexpectedly remarked, "The human animal is incurably lazy." Was that meant to refer to me or to himself? Or was it just a general observation? I never knew. He turned the boat, and we started back. Time was beginning to run short. Suddenly Heilbronn became angry with his sister for some boating misdemeanour, and shouted at her in schoolboy slang, "Kalb!'. Then, repenting, he added in a low voice, "She does not know how lucky she is." His meaning was quite clear. She had not many personal resources, and if he had not managed to get her out of Germany, she would hardly have survived. Suddenly he seemed to me much older than he had been when he first came to Bristol, although it was little more than 5 years ago. He had such a gift then, in spite of his difficulties and anxieties, for enjoying life. I
remember one day when the three of us went over to Avonmouth, in a little car I had then, to see a sailing ship, a three-master, which had just come into port. I still have two snapshots of the occasion, one of the rigging of the ship, and one of Hans. He looked young, strong, resourceful, and that is how I remember him. In 1939, Heilbronn applied for naturalization. He wrote to Linfoot asking if Linfoot would be willing to be one of the four signatories required. Linfoot was horrified, realizing how short the time might be, and wrote back by the next post, "Send the papers at once." When they came he signed and sent them back immediately. But by the time Heilbronn managed to get them to the authorities, it was too late, and he missed naturalization by a few days. The result of this was internment in the Isle of Man, and the loss of about 6 years of his mathematical life. One has the impression that everyone in Trinity had a feeling of security, not least Hardy himself. Heilbronn was, for instance, in charge of fire precautions for the College. Who could have expected that the police would come and arrest him without warning? During those early years in England he had a wonderful and characteristic sense of humour, and I conclude with two stories to illustrate it. (It vanished later.) The first Heilbronn told against himself. "One day I was drinking with a friend in a pub in Cambridge, and my friend accused me of being drunk. 'I'm not drunk,' I said. 'Could I prove the law of Quadratic Reciprocity if I were drunk?' So I began the proof and went through it all without a mistake, and my friend then agreed that I could not be drunk. But," continued Heilbronn, "I think I could have given that proof even if I had been drunk." Another. One day, Linfoot, Heilbronn, and myself had just finished supper at the Clifton Down Hotel, and were going out through the revolving door. This was very large and handsome, and so beautifully made that it moved at a touch. On the other side Heilbronn turned and stood looking back at it thoughtfully. Then he said softly, "I wonder . . . . . . I almost believe . . . . . ". Suddenly he bent down a little and blew at the centre of the outward edge of one of the flanges. The door began to turn!
References 1. The Life and Works of Hans Arnold Heilbronn, John Wiley & Sons, Toronto, 1988. 2. H.A. Heilbronn. On the class-number in imaginary quadratic fields. Quarterly Journal of Mathematics 5 (1934), 150-160. 3. H.A. Heilbronn and E.H. Linfoot. On the imaginary quadratic corpora of class-number one. Quarterly Journal of Mathematics 5 (1934), 293-301.
43A The Broadway Didcot, Oxford 0 X l l 8AQ United Kingdom THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3,1993
43
The Riemann-file Nr. 135 of the Philosophische Fakultitt of the Georgia Augusta at GOttingen Reinhold Remmert
On November 14, 1851, Georg Friedrich Bernhard Riemann (b. September 17, 1826, d. July 20, 1866) submitted a thesis "'Grundlagen ffir eine aUgemeine Theorie der Functionen einer ver/inderlichen complexen Gr61]e" (Foundations of a general theory of functions of one complex variable) to the philosophy faculty of the University of G6ttingen to earn the degree of doctor philosophiae. In Bernhard Riemann's Lebenslauf, R. Dedekind states that Riemann had probably conceived the decisive ideas in the autumn holidays of 1847; see [1], p. 576. The creative visions of Riemann in his inaugural dissertation were not at all understood by his contemporaries (except possibly by Gauss). In 1953, L. V. Ahlfors wrote, "Riemann's writings are full of cryptic messages to the future . . . . The spirit of Riemann will move future generations as it has moved us" ([2], pp. 493, 501). It was only after Riemann's untimely death that H. A. Schwarz and L. Fuchs, on the advice of K. Weierstrass, began to study and grasp the richness of the revolutionary new ideas. Later, F. Klein became Riemann's eloquent public relations agent [3]; his conception of a Riemann surface is based on the cut-andpaste method (Schere- und Kleistermethode). It was not until 1913 that H. Weyl, in his classic Die Idee der Riemannschen FMche, gave rigorous definitions and proofs. This book opened eyes to the hidden treasures of Riemann's profound invention; we read the enthu-
I T h e full n a m e of t h e f a m o u s u n i v e r s i t y a t G 6 t t i n g e n is t h e w e s e e h e r e t h e L a t i n f o r m of it. (ed.)
siastic sentence "In dem Symbol des zweidimensionalen Nicht-Euklidischen Kristalls wird das Urbild der Riemannschen Fl/ichen selbst (soweit dies m6glich ist) rein und befreit von allen Verdunklungen und Zuf/illigkeiten, erschaubar" ([4], p. VI). ["In the symbol of the two-dimensional non-Euclidean crystal, one can see (insofar as this is possible) the very nature of Riemann surfaces themselves, pure and freed of all obscurities and incidentals."] Ever since, mathematicians and historians all over the world have been praising Riemann's thesis as one of the deepest writings in mathematics during the nineteenth century. It is all the more difficult to understand that, in the accessible lit-
Georg
August Universitiit a n d 44
THE MATHEMATICAL INTELLIGENCERVOL. 15, NO. 3 9 1993 Spr[nger-Veflag New York
erature on Riemann, mathematicians have never called attention to the evaluation of the thesis in 1851 by G6ttingen's Georgia Augusta. E. Schering alone cites this evaluation in his obituary Zum Gedfichtnis an B. Riemann; see [5] in [6], p. 836. Schering gave his address on December 1, 1866 in a public session of the Royal Society of Science at G6ttingen. It was only in 1909 that his talk was published in Schering's collected works. Luckily, this obituary is n o w available in the recently published third edition of Riemann's collected papers, carefully edited and commented on by R. Narasimhan.
The aim of the present note is to reprint--with the kind permission of the archive of the University of G6ttingen--relevant parts of the Riemann-file Nr. 135 from 1851. Historians, of course, are well aware of the existence of this file; see, e.g., [7], p. 223, footnote 5. With his request for admission to a doctorate on November 14, 1851, Riemann submits his vita; both documents are composed in Latin (as the university laws of those days demanded). On the following day, the Dean informs the faculty (full professors only), in preSi~tterlin handwriting:
Amplissimo Ordini habe ich hier die Abhandlung eines neuen Candidaten unsrer Doctorw(irde, Herrn B. Riemann aus Breselenz, vorzulegen; und bitte Herrn Geh. Hofr. Gaul~ um ein Gutachten fiber dieselbe und, falls sie als gen~igend sich beweist, um eine gef/illige Andeutung des Tages und der Stunde in welcher die m~indliche Priifung etwa gehalten werden k6nnte. Der Candidat w~inscht in Mathematik und Physik geprfift zu werden. Das Latein in dem Gesuche und der Vita ist ungelenk und kaum ertrhglich: indessen wird in den nicht philologischen Wissenschaften besseres gegenw/irtig wohl kaum auch nur noch von solchen erwartet welche wie dieser Candidat bei der Universit/itsLaufbahn zu bleiben willens sind. 15 ten Nov. 51. Hochachtungsvoll Ewald
Herewith I have to put before my distinguished colleagues the treatise of a new candidate for our doctorate, Mr. B. Riemann from Breselenz; and entreat Mr. Privy Councillor Gauss for an opinion on the latter and, if it proves to be satisfactory, for an appropriate indication of the day and the hour when the oral examination could be held. The candidate wants to be examined in mathematics and physics. The Latin in the request and the vita is clumsy and scarcely endurable: however, outside the philological sciences, one can hardly expect at present anything better, even from those w h o like this candidate are prepared to enter on a career at the university. 15 Nov., 51. Respectfully Ewald THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
45
Gauss complies with the Dean's request shortly thereafter (undated, but certainly still in November 1851); he writes in pre-Sfitterlin calligraphy the following "referee's report":
46
THE MATHEMATICAL INTELLIGENCER VOL. 15. NO. 3. 1993
Die yon Herrn Riemann eingereichte Schrift legt ein biindiges Zeugni~ ab von den gr~ndlichen und fief eindringenden Studien des Verf. in demjenigen Gebiete, welchem der darin behandelte Gegenstand an-
geh6rt; von einem strebsamen /icht mathematischen Forschungsgeiste, und von einer riihmlichen productiven Selbstth/itigkeit. Der Vortrag ist umsichtig und concis, theilweise selbst elegant: der gr6i~te Theil der Leser m6chte i n d e f wohl in einigen Theilen noch eine grOflere Durchsichtigkeit der Anordnung w~inschen. Das Ganze ist eine gediegene werthvolle Arbeit, das Maaf der Anforderungen, welche man gew6hnlich an Probeschriften zur Erlangung der Doctorw~irde stellt, nicht blof er~llend, sondern welt iiberragend. Das Examen in der Mathematik werde ich ~ibernehmen. Unter den Wochentagen ist mir Sonnabend oder Freitag allenfalls auch Mitwoch am passendsten und, wenn eine Nachmittagsstunde gew/ihlt werden soil, u m 5 oder 51/2 Uhr. Ich wiirde aber auch nichts gegen die Vormittagsstunde 11U zu erinnern haben. Ich setze (ibrigens voraus, daft das Examen nicht vor der n/ichsten Woche Statt finden wird. Gauf beistimmend: Mitscherlich, Hausmann, Ritter, Hoeck, Hermann, Waitz, Weber The paper submitted by Mr. Riemann bears conclusive evidence of the profound and penetrating studies of the author in the area to which the topic dealt with belongs, of a diligent, genuinely mathematical spirit of research, and of a laudable and productive independence. The presentation is circumspect and concise, in part even elegant: yet the majority of readers might well wish in some parts a still greater transparency of arrangement. The whole is a worthy and valuable work, not only meeting the requisite standards which are commonly expected from doctoral dissertations, but surpassing them by far. I shall take on the examination in mathematics. Among weekdays Saturday or Friday or, if need be, also Wednesday is most convenient to me and, if a time in the afternoon is chosen, at 5 or 5:30 P.M. But I also would have nothing to say against the forenoon hour 11 A.M. I am, incidentally, assuming that the examination will not be held before next week. Gauss approved: Mitscherlich [rhetoric], Hausmann [mineralogy and technology], Ritter [philosophy], Hoeck [classical philology], Hermann [classical philology and archeology], Waitz [history], Weber [physics] The oral examinations were held on December 3; the public disputation a n d the graduation to doctor philosophiae took place on December 16, 1851. It seems appropriate to add some comments. The Dean of the Faculty was the well-remembered Protestant theologian Georg Heinrich August Ewald (18031875). He was, as was the physicist Wilhelm Eduard Weber (1804-1891), 1 one of the famous "G6ttinger Seven" who in 1837 protested against th e revocation of the liberal constitution of the kingdom of Hannover by
King Ernst August and lost their positions. Ewald was an expert in Hebrew grammar; hence, one may forgive him his complaints about Riemann's poor handling of Latin. It was customary in Germany in those days to write terse evaluations without descending into details. Nevertheless, it is to be regretted that Gauss says nothing about the mathematics as such in Riemann's dissertation which in part had been familiar to him for many years. Indeed, Riemann, w h e n paying his formal visit to Gauss for the rigorosum, was informed "that for a long time he [Gauss] has been preparing a paper dealing with the same topic but certainly not restricted to it;" see [1], p. 545. [The paper referred to here is Gauss's article (Bestimmung der) Convergenz der Reihen, in welche die periodischen Functionen einer vefanderlichen Gr6sse entwickelt werden, Gauss's Werke X, 1, 400-419; cf. also Werke X, 2, p. 209.] The reader is unable to learn from Gauss's report even what topic is dealt with in the dissertation (geometry or number theory o r . . . ). Gauss is famous for his sparing praise; thus, his short report must be rated as a strong appraisal. Note that Gauss does not suggest a grade and that one-third of his letter deals with finding a good time for the oral examination. Let me conclude with an episode shedding significant light on the situation of cand. math. B. Riemann. On November 24, 1851, he addresses, for personal reasons, a most humble petition for dispensation from the disputation to the distinguished faculty (German headhag: An die hochpreisliche philosophische Facult/it gehorsamstes Gesuch des cand. math. B. Riemann u m Dispensation yon der zur Erlangung der Doctorw~irde erforderlichen Disputation). W. Weber was in favor of granting the dispensation, employing a most remarkable argument: "In dem vorliegenden Falle finde ich gegen die Disputation schon darum ein Bedenken, well w e n n der Candidat nicht selbst unter seinen Freunden einen Opponenten findet, die Facult~it gar nicht im Stande sein wiirde, einen Opponenten zu stellen. Diese Verlegenheit di~rfte sehr leicht eintreten." (In the present case I already have against the disputation the foIlowing reservation: If the candidate does not himself find an opponent among his friends, the faculty will not be in a position to provide an opponent. This predicament might very easily occur.) However, Gauss was reluctant. He writes: "Ohne Disputation ist ein Doctor kein rite promotus" (Without disputation a doctor is not a real doctor). Furthermore, he points out, "The candidate intends, in future, to qualify as a Privat-docent; the law provides that at that 1 W e b e r w o r k e d o n e l e c t r o m a g n e t i s m , a n d set u p in 1833, w i t h G a u s s , t h e first telegraph. W e b e r ' s s i g n a t u r e is t h e left-most o n e o n G a u s s ' s report. THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3, 1993 4 7
time he has to catch up on the missing disputation . . . . Therefore, in this case, I have, sine praeiudido, no objections to impose the disputation on him now." Thus, Riemann had to face a disputation in Latin on December 16, 1851. It is most unfortunate that the Archives at G6ttingen neither reveal the theses he was defending nor the opponent(s) that were chosen.
Acknowledgments The author thanks Dr. Hunger of the Universit/itsArchiv of the University of G6ttingen for providing him with the relevant documents.
References 1. R. Dedekind, Bernhard Riemann's Lebenslauf, in [6], pp. 571-590. 2. L. V. Ahlfors, Development of the theory of conformal mapping and Riemann surfaces through a century, Contributions to the theory of Riemann surfaces, Ann. Math. Studies 30 (1953), 3-13; also in Collected Papers 1 (1982), 493-501. 3. F. Klein, Riemann und seine Bedeutung fiir die Entwicklung der modernen Mathematik, Lecture given 1894 at Vienna; Ges. Math. Abh. 3 (1923), 482-497. 4. H. Weyl, Die Idee der Riemannschen Flfiche, Leipzig: Teubher (1913); anastatic reprint 1923 by Teubner (Leipzig); reproduced 1947 by Chelsea (New York); 3rd ed. 1955 by Teubner (Stuttgart); 4th ed. 1964. 5. E. Schering, Zum Ged/ichtnis an B. Riemann, Ges. Math. Werke 2, Berlin: Mayer und Miiller (1909), in [6], pp. 827844. 6. B. Riemann, Gesammelte Mathematische Werke und Wissenschaftlicher Nachlass, edited with the support of R. Dedekind and H. Weber, Leipzig: Teubner (1876); 2nd ed. by H. Weber, 1892; reprint of 2nd ed. by New York: Dover Publ. Inc. (1953); 3rd ed. by R. Narasimhan, Berlin: Springer-Verlag and Leipzig: Teubner (1990). 7. E. Neuenschwander, O-ber die Wechselwirkungen zwischen der franz6sischen Schule, Riemann und Weierstrag. Eine Ubersicht mit zwei QueUenstudien, Arch. Hist. Ex. Sci. 24 (1981), 221-225.
Mathematisches Institut Einsteinstrasse 62 D-4400 Mfinster Federal Republic of Germany
Cartoon by John de PiUis
"'Let's see--dishevelled, sweater, dazed expression--you're a mathematician, right?"
48
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
Ian Stewart* The catapult that Archimedes built, the gambling-houses that Descartes frequented in his dissolute youth, the field where Galois fought his duel, the bridge where Hamilton carved quaternions-not all of these monuments to mathematical history survive today, but the mathematician on vacation can still find many reminders of o u r subject's glorious and inglorious past: statues, plaques, graves, the cafd where the famous conjecture was made, the desk where the
Riemann Surface
famous initials are scratched, birthplaces, houses, memorials. Does your hometown have a mathematical tourist attraction? Have you encountered a mathematical sight on your travels? If so, we invite you to submit to this column a picture, a description of its mathematical significance, and either a map or directions so that others may follow in your tracks. Please send all submissions to the Mathematical Tourist Editor, Ian Stewart.
Crocheted in Four Colors
Elisabeth Miihlhausen Filled with deep reverence, Lily R(idenberg, Herman Minkowski's daughter, tells us in her reminiscences of the awe and wonder she experienced w h e n her father took her to the Mathematical Institute and showed her the exhibits "which could draw interesting curves in many different colours'" [1]. * Column Editor's address: Mathematics Institute, University of
Wa~ "ick,C-Jventry, CV4 7AL England.
The fascinating devices and other mathematical models which little Lily saw survived two World Wars and are to be f o u n d in the room above the "HilbertRaum" (in German it means both "Hilbert space" and "Hilbert room") and the corridors of the Mathematical Institute of the University of G6ttingen at Bunsenstrat~e 3-5. The exterior of the building may appear rather grey and dull, perhaps because it is uncompromisingly
Figure 1. Neugebauer's glass cases. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3 9 1993 Springer-Verlag New York 4 9
Figure 2. K/istner's polyhedra from 1780.
symmetric. But the visitor will be surprised by the sight of the mathematical treasures inside: In some 60 glass cases, there are about 700 exhibits, most of which date from the period 1880-1930. Walking through the Institute is like reading "Who's Who in Mathematics"; the walls are covered with photographs of the m a n y famous mathematicians who worked in G6ttingen. The photographic display and accompanying texts were prepared in 1987 on the occasion of the 250th anniversary of the founding of the University of G6ttingen. In 1929, w h e n the building of the Mathematical Institute was opened, the use of models for teaching was already somewhat out of fashion. They disappeared from the lecture rooms, but fortunately were not consigned to the attic or cellar. Instead, they formed the 50
THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3, 1993
basis of an unusual mathematical m u s e u m . Even though they are not being used any longer for teaching, at least they can still be admired in an adequate environment. This was clearly the goal of the mathematician and historian Otto Neugebauer (1899-1990) who tended the collection knowledgeably and affectionately. The glass cases which he designed are both functional and aesthetically pleasing. They are dust-proof and topped by frosted glass which lets the light fall naturally on the exhibits underneath (Fig. 1). The plain wooden bases on which they are mounted also serve as cupboards. The arrangement of the cases makes it possible for the visitor, or the student waiting during a break in lectures, to stroll between them. There are always new details to be discovered. Some of the models have been documented with beautiful, technically perfect pictures and detailed commentaries in the two-volume work Mathematical Models edited by Gerd Fischer [2], who made the photographs. In these volumes, the plaster models have pride of place as they are the most photogenic. More than 100 m o d e l s - - m a n y from G6ttingen--are described here, but this is only a small sample of the G6ttingen collection. If y o u w a n t to have the s a m e e x p e r i e n c e as Minkowski's daughter, first take a look at David Hilbert's bust, and then follow the direction of his nose, which leads you into a small corridor. In the first two glass cases stand devices that can be moved only with special permission. Nevertheless, you can still go deeply into the rotation of the intermeshing cogwheels and imagine the development of the epicycloids and epitrochoids on the transparent glass plates. These models came from the workshop of Martin Schilling, who was a major producer of mathematical models of all kinds. Above them is a small machine demonstrating three-dimensional epicyclic motion, proposed by Eudoxus as a description of planetary orbits. One might wonder whether Lily was allowed to play with this fragile cosmos. Two cases further on there are massive models illustrating points of the theory of the gyroscope. These models, made of heavy wood and polished brass, form a contrast to a gyroscope in a delicate Cardan suspension placed between them. Before going to the upper floor it is worthwhile to make your way along the dark corridor to the portrait and biographical sketch of Abraham Gotthelf K~stner (1719-1800). From 1756 on, he was professor of mathematics in G6ttingen, and for his teaching he used models of geometrical bodies which are the oldest in the collection (Fig. 2). These polyhedra of thin cardboard are now somewhat yellowed and stained, their writings a little pale; but on the whole they are wellpreserved and attractively arranged in a wall case in front of the Auditorium Maximum.
Figure 3. Crystallographic groups.
Next to this case there is a case illustrating, in plaster of Paris, various crystallographic g r o u p s - - t h r e e "dimensional jigsaw puzzles (Fig. 3). They embody results of the research carried out by Arthur Schoenflies (1853-1928), who, in 1892, was the first incumbent of the professorship for applied mathematics that was created at Felix Klein's instigation. He concerned himself, among other things, with spatial geometric configurations, and established the relationship between translation groups and crystallography. For the explanation of crystal structures, he developed mathematical models that could be confirmed by physical methods. To clarify the connection between mathematical structures and those of nature, there are models of the crystal structures of zincblende and diamond. Both have the form of a hexakis tetrahedron and belong to
Figure 4. Crocheted Riemann surface.
the crystal class that Schoenflies denoted by T a. A further three-dimensional impression of molecules is given by looking through a stereoscope at cards designed by Max yon Laue and Richard yon Mises and printed by Julius Springer Verlag. Turning around to the glass cases in the middle of the room, you will see further samples of applied mathematics. Next to plaster space curves that are produced by plucked violin strings or struck piano strings, there are huge and bulky calculators. An "arithmometer" in a solid wooden box advertises its own abilities with the logo TIM (Time Is Money). It masters the four fundamental rules of arithmetic and must assert itself against an even larger machine called "Million~ir." The other calculators make you smile not only because of their design, but also because of their impressive names, such as "Triumphator," "'MercedesEuclid," or "Archimedes-Patent." Another glass case contains the favorite toys of Richard Courant (1888-1972), boundary curves for minimal surfaces made of wire. There is a documentary film [3] in which he dips some of these wire frames into soap solution and presents, in fascination, beautiful shimmering soap films between the wires. Due to surface tension, the area spanned is as small as possible; in other words, it is a minimal surface. This same charming impression of childlike pleasure is also produced by the eight wire models in the small cardboard boxes with curves drawn on the three inner sides. They accurately present singularities of space curves, but still convey the idea of cute mathematical doll houses. Nearby are various constructions of Riemann surfaces made of different materials. The most outstanding is certainly the unique crocheted object with the embroidered number of the collection (Fig. 4). THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
51
~2
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
Finally I want to draw your attention to several variable models which are more than 100 years old and which present different one-sheeted hyperboloids as ruled surfaces (Fig. 5). An old photo of such a model surrounded by female students of mathematics at Wellesley College can be found in a volume of The Mathematical Intelligencer from 1987 [4]. By asking Professor Samuel J. Patterson, who is now responsible for the collection, you might have the chance of being shown the possible variations of these carefully restored objects, made of perforated iron strips and m u l t i c o l o u r e d threads, w h i c h remain stretched in each position because of lead bullets fixed at their ends. You should also ask him for another mathematical curiosity: a mysterious old leather suitcase inside the "poison cabinet" in the supervisor's lodge in front of the reading room. A gigantic book of oblong format is hidden there. As the space on the table in the small room is hardly big enough to open it, you should simply read it on the floor. The senior primary school teacher Johann Gustav Hermes from K6nigsberg put down in his neatest handwriting endless tables, tiny drawings, and some text. This is the result of 10 years' ~meticulous concentrated work on the construction of the 65537-gon [or (2 l~ + 1)-gon] together with the corresponding algebraic results. If you want to relax after this experience, have a look at some more plaster models, reflecting a sense of calm, such as the cyclides of Dupin in the glass case next to the conference hall (Fig. 6). Before walking out, you should take a close look at the door handle; it is a mathematical composition of a circular cylinder and a square-sectioned rod created by the architect and industrial designer Martin Gropius (1883-1969), founder of the Bauhaus school. You can find a lot of Bauhaus details in the whole Mathematical Institute, but to look at the building from this point of view would be another day's work. Acknowledgment
The photographs are taken by Elisabeth M~ihlhausen with the permission of Professor Samuel J. Patterson from the Mathematical Institute of the University of GOttingen. References
1. L. R~idenberg, Erinnerungen an H. Minkowski, Hermann Minkowski, Briefe an David Hilbert (L. Riidenberg and H. Zassenhaus, eds.), Berlin-Heidelberg-New York: Springer-Verlag (1973), p. 16. 2. G. Fischer (ed.), Mathematische Modelle/Mathematical Models: Braunschweig (1986), Vols. 1 and 2. [Reviewed by Jeremy Gray in Mathematical Intelligencer vol. 10 (1988), no. 3, 64-69.]
Figure 6. Surfaces of order four and cyclides of Dupin.
3. A. N. Feldzamen and P. E. Miles, G6ttingen and New York--Reflections on a Life in Mathematics: Richard Courant, Washington, D.C.: Mathematical Association of America (1965). 4. J. Green and J. La Duke, Women in the American mathematical community: The pre-1940 Ph.D.'s, Mathematical Intelligencer, vol. 9 (1987), no. 1, 11-23. The photo is on page 17. Vorbergstrasse 13 WIO00 Berlin 62 Germany THE M A T H E M A T I C A L INTELLIGENCER VOL. 15, NO. 3, 1993 ~ 3
The Cuboctahedron in the Past of Japan Koji Miyazaki The cuboctahedron seems to have had a special meaning for religious people in Japan. It may be a matter of common knowledge that in the past the most revered solid symbol was not the cuboctahedron but the "Hoju" gem, a chestnut-shaped solid. We can find easily many Hojus in the sanctuary of a shrine or temple. It sometimes symbolizes a god; it also forms a decoration at the top of sacred buildings or monuments such as a pagoda, or the main hall of a temple or shrine; it is also used as a garden lantern ("Toro" in Japanese). In particular, a big Hoju is usually put on the top of the "Gorinto" pagoda, a five-storied small pagoda which is the most typical monument for Buddhists in Japan (Fig. 1). This pagoda is made of five blocks which symbolize the earth (a cube), water (a sphere), fire (a square pyramid or sometimes a tetrahedron), air (a hemisphere), and the universe (a Hoju), from bottom to top. There is an opinion that such construction might be derived from Plato's "Timaeus" [1]. If so, the Hoju may mean the regular dodecahedral universe of Plato. Figure 1. A Gorinto pagoda.
Figure 2. A cuboctabedra! offering, Toshogu Shrine, Nikko. 54
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3 (~)1993 Springer-Verlag New York
In spite of this, as Hargittai [2] has reported, there are some cuboctahedral top decorations of imperial monuments in Shugakuin Imperial Villa, Kyoto. Figure 2 shows another cuboctahedral sacred offering at the Toshogu Shrine, Nikko, Tochigi. This shrine was completed in the middle of the 17th century, almost the same time as Shugakuin Villa, and is famous for its gorgeous ornaments, which oppose the architectural policy of plain Katsura and Shugakuin. Why was the cuboctahedron sometimes used instead of the Hoju, i.e., the regular dodecahedron? My opinions are as follows: It is usually said that the Japanese of the past much preferred the silver ratio 1 : V'2 belonging to the cuboctahedron to the golden ratio 1 : 1.618 belonging to the regular dodecahedron: see [3]. Furthermore, cuboctahedral decorations can be easily made and practically used. There are many small cuboctahedral decorations in traditional Japanese furniture, buildings, and toys, even though these are not sacred. Japanese traditional mathematicians, Wasan mathematicians who are known from the beginning of the 17th century, also liked the cuboctahedron. They called it the "Kiriko," which means a truncated bamboo basket. The shape of the Kiriko appeared as a lantern in pictures as early as the 13th century. It is rumoured that the archetype of the sacred lantern is not a sphere or ellipsoid, as is usual today, but a cuboctahedron. Kiriko lanterns appear even now in some Bon ceremonies held in mid-August every year to commemorate the dead. Figure 3 shows one held in Shimabara, Nagasaki. In this ceremony, about 20,000 Kiriko lanterns are floated down to the sea. Figure 4 shows a Kiriko lantern hung in the main hall of Kongobuji Temple in Mt. Koya, Wakayama. There are many other colorful and beautiful examples. According to custom, this lantern must be kept secret from people except on the days of the Bon ceremony. Curiously enough, in the nearest country to Japan, Korea, from which the ancient Japanese learned many things, the shape of the important lantern is not the cuboctahedron, but the rhombicuboctahedron. References
1. K. Miyazaki, An Adventure in Multidimensional Space, John Wiley & Sons, New York, 1986, p. 38. 2. I. Hargittai, "Imperial Cuboctahedron," The Mathematical Intelligencer, 1993, 15, 1, pp. 58-59. 3. K. Miyazaki, "A Mystic History of Fivefold Symmetry in Japan," in Five-fold Symmetry, I. Hargittai, ed., World Scientific, Singapore, 1992, pp. 361-393.
Kyoto University Yoshida Sakyo-ku Kyoto, 606 Japan
Figure 3. Kiriko lanterns in a Bon ceremony, Shimabara, Nagasaki. Figure 4. A Kiriko lantern in a Bon ceremony, Kongobuji Temple, Mt. Kova.
David Gale* For the general philosophy of this section see Vol. 13, No. 1 (1991). Contributors to this column who wish an acknowledgment of their contributions should enclose a self-addressed postcard.
Games People Play The subject of game theory is by now a fairly substantial branch of mathematics, treated in dozens of books, hundreds of research papers, and at least two full-time journals. Game theory comes in many quite different flavors, including economic, political, military, and, of course, recreational, but all of these branches have one thing in common. In all but very rare cases, the games analyzed are not traditional existing games but rather new games, invented not to be played but to be analyzed. There are a few exceptions like the game of Dots and Boxes which predates game theory. Also, very recently Elwyn Berlekamp has been applying some of the most sophisticated ideas of combinatorial game theory to certain positions in the game of Go. However, this work has little to do with actually playing Go, in the same w a y that chess problems have little to do with playing chess. All of this is by way of leading up to the fact that, in contrast to the remarks above, Michael Paterson and Uri Zwick have recently succeeded in giving an almost complete analysis of the familiar game of Concentration, which many readers have no doubt played as children or, perhaps later, with children. A deck consisting of n pairs of matched cards is shuffled and the cards are spread out face down on a table. A player turns over a card and then a second card. If the two cards match, the player keeps the pair and gets another turn. If not, the chosen cards are again turned face down and the turn passes to the opponent. The winner is the player who accumulates the largest number of pairs. Because both players see all cards that have been turned over, success at the game depends on skill in remembering the location of the cards which were previously turned. Thus, people * Column editor's address: Department of Mathematics, University of California, Berkeley, C A 94720 USA. 56
with so-called photographic memories should do well. But what if both players have perfect memories? Would it then be just a matter of the luck of the draw? The authors' first striking observation is that, in fact, strategic behavior is possible and sometimes it is advantageous to make a deliberately "stupid move." We illustrate. Consider a deck containing four pairs, say, aces, kings, queens, and jacks. On his first move, your opponent turns over an ace and a king. You then turn over the other ace, collect the pair, and play again. This time you turn over a queen on your first draw, so the state of the game is represented below.
The dotted card indicates that the king is face down but its position is known to both of you, the queen is face up, and the position of the remaining cards is not known. N o w you must turn over a second card so, naturally, you should turn over one of the unknown face-down cards. Wrong! The proper move is to turn over the king, even though you know this will gain you nothing and will pass the turn to your opponent. Why is this? All right, if you turn up another card, then with probability 1/2 it will be a jack, in which case your opponent will get all three pairs, so your expected loss is 3/2. On the other hand, if you do not draw the jack you are equally likely to draw the king or the queen and from symmetry one sees that your expected loss in the first case is the same as your expected gain in the second, so your overall expected loss is 3/2. On the other hand, suppose you turn over the card you know to be the king. N o w with probability 1/2 your opponent draws the jack and will
THE MATHEMATrCAL1NTELLIGENCERVOL. 15, NO. 3 (~)1993Springer-VerlagNew York
win or lose the three pairs depending on whether or not h e then draws the other jack, so his expectation is --1/2. If he draws the king or queen, he takes the pair and is then twice as likely to win as to lose the other two pairs, giving him an expectation of 5/6, so his total expected gain, which is your expected loss, is 1/3. To summarize, if you are playing for a dollar a pair, then the "stupid move" costs you only 33 cents as opposed to the dollar and a half you would expect to lose if you played in the usual way (from now on in all of the analyses, it is assumed that you are interested in maximizing your expected winnings, this being the difference between the number of your pairs and your opponent's pairs). Of course, the common sense behind the above calculations is fairly clear. In deciding whether or not to turn over a second card, you are weighing the chance of getting a match, on the one hand, against the information you give your opponent in case you fail, on the other. As the simplest example of this, consider a deck consisting of only two pairs. Then it is clearly a disadvantage to play first because you only have one chance in three of getting a match, and if you do not, you lose both pairs. Is it then a disadvantage to go first for a deck of any size? The answer is yes for decks of 3, 4, and 5 pairs, but for 6 and 7 pairs the first player has the edge. From then on, the advantage is for the first or second player according to whether the number of pairs in the deck is odd or even, a fact which seems far from obvious. Returning to the question of strategic play, the best strategy will depend on the assumption one makes about one's opponent. In the example above, we considered a "naive" opponent, meaning one who always turns over a second card when she does not get a match. We will refer to this as a 2-move. In this case, it turns out that one should almost always play the stupid move, which we will refer to from now on as a 1-move. However in some situations one should play a "superstupid move." Thus, in the four-pair game, if your opponent starts by turning over the ace and king, the best thing you can do is turn them up a second time. This of course amounts to passing, and, as was seen in the previous paragraph, this may well be the best thing to do. We will refer to this as a O-move. Further, because we are assuming perfect memory, we may as well assume that cards which have been turned over remain face up. The general optimal strategy against a naive player turns out to be the following: Aside from sporadic exceptions for decks of fewer than 30 pairs, one should always play a 1-move when the number of pairs has the same parity as the number of face-up cards. When these parities are different, one still plays a 1-move until the proportion of face-up cards is very large. At some critical point, one then in some cases plays an isolated 2-move followed by 0-moves. The picture is given by the table below, where it is assumed that 0- and 1-moves are permitted even at the start of the game when no cards have been turned over.
.-
l:J
~- 2 022~ m- 3 10 S 6 0210ii100~ 102110 7 210 0 02110110~ g 210110110~ 10 0210110110 11 20210111110 12 210111111110 1~ 0210111111110 14 10211111111110 15 211011111111110 16 021 n" 17 210111111111111101~. n" 18 02101111111111111~0~ n" 19 10111111111111111
n" m" nnnn" nmn"
20 21 22 23 24 25 26 29
21011111111111111110~ 021111111111111111110~ 1011111111111111111210~
21111111111111111111210~ 0211111111Ii11111111121~0 ~ 21111111111111111111112 21111111111111111111111210~ 10111111111111111111111121~
28 21111111111111111111111112 n" 29 02111111111111111111111111210~ n- 30 211111111111111111111111111210~ ~- 31 2111111111111111111111111111210~ n- 32 21111111111111111111111111111210~
m- 33 21111111111111111111111111111121~ n" 34 2111111111111111111111111111111210~ n- 35 21111111111111111111111111111111210~ n= 36 211111111111111111111111111111111210~ n- 39 2111111111111111111111111111111111210~L n- 38 21111111111111111111111111111111111010~
n- 39 211111111111111111111111111111111111010~ n- 40 2111111111111111111111111111111111111010|
The kth entry in r o w n tells w h i c h m o v e to p l a y in a g a m e w i t h n pairs a n d k - I face-up cards.
The work of Paterson and Zwick is concerned not with the naive opponent but rather with two equally sophisticated players. In this case the optimal strategy is even easier to describe. With the exception of the six-pair deck, the rule is that if the number of pairs and face-up cards has the same parity, one plays a 1-move. For the other case, one plays a 2- or 0-move according to whether the number of face-up cards is more or less than two-thirds of the number of pairs. Of course, a 0-move by either player means that the game will terminate because otherwise, both players would continue playing 0-moves forever. The story of the Paterson-Zwick result is intriguing. First, it was a happy circumstance that the pattern of the optimal strategy turned out to be so easy to describe, Of course, this pattern could not have been discovered without the aid of high-speed computation (surely no one could possibly have conjectured such a pattern a priori). On the other hand, given the availability of such computation, it was a relatively routine matter to obtain as much data as one needed. Thus, the optimal move for a given configuration of face-up and face-down cards depends on the optimal move for configurations with fewer face-down cards, and it is not hard to formulate the appropriate recursions in this way. What is rather remarkable, however, is that the authors were able to prove with complete rigor that the strategy described above is indeed optimal. Further, the proof is extremely involved, running some 14 pages broken up into 7 sections. Perhaps most noteworthy of all is the fact that the proof makes heavy use of computer-aided symbolic compuTHE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3,1993
57
tation. In the authors' words, "It is doubtful whether this analysis could have been carried out without resort to experimentation and a substantial use of automated symbolic computations." The observations above should not be taken to mean that the whole project was handled by computers and that all the investigators had to do was feed in the data. On the contrary, the main challenge in attacking this problem was to bring it into a form which made the decisive symbolic computations possible. Some of the section headings, "Operator Notation," "Bootstrapping," "Boundary Layer Influence," give an indication of some of the concepts involved in this effort. Here then is one more example to suggest that mathematicians may want to rethink their notions of what it means to "do mathematics" in the age of high-speed computation. Meanwhile, despite these new discoveries, children and parents will no doubt continue to play Concentration because, for better or worse, there seems to be no indication that humans are about to develop perfect memory.
Games People Do Not Play This is a memo r y game of a different sort. I have an infinite deck of cards and on my first move I hand you a finite subset of them. You are then allowed to discard one card, after which I hand you another finite subset of the remaining cards and you again make a single discard. The game continues in this way for a countable number of moves, and if at the end your hand is empty, you win, and otherwise I do. Simple. Now, as described above, the game is not very interesting because, in fact, you have an easy winning strategy. You simply keep track of the cards as I hand them to you and proceed to discard, first the cards I gave you on my first move (in any order), then those I gave you on my second move, and so on. Thus, by the end of the game you will have gotten rid of them all. Notice, however, that to execute this strategy you must have a very long memory. For example, if I give you a million cards on each move, you will continue to fall further and further behind, and by the time you have gotten rid of the first hand I gave you, you will be holding 1012 cards. In other words, to play the simple strategy you will need to have an unbounded memory. Let us, therefore, go to the other extreme and suppose that you have no memory at all but only know on each turn the names or numbers of the cards you are currently holding (note that this sort of information is good enough for finite games, like chess, checkers, or tic-tac-toe, where to decide on your next move the only thing that matters is the current position of the board and not how the position was reached). If the deck is countable, you are still in good shape. Namely, before the game starts, you enumerate the deck in some fashion and then on each turn you simply discard the card in your hand with the smallest number. What happens, however, if the deck is uncountable? 58 THEMATHEMATICALINTELLIGENCERVOL.15,NO.3,1993
THEOREM 1. For an uncountable deck in the zero-memory game, there is no winning strategy for the second player.
Proof: A strategy in the memoryless game is simply a function which to each finite set of cards (your hand) assigns a card (your discard). In particular, therefore, it assigns to each pair of cards the one which is to be discarded. Let us then define for each card x the set Dx consisting of all cards p # x such that if you hold {x, y} you will discard y. Now, to show that you have no winning strategy, it will suffice to prove that there is some x' such that Dx, is infinite, because then it will contain some infinite sequence yl~ y2~...~ so I will give you {x',yl} on m y first move and {yn} on my nth, and you will never get rid of x'. To complete the proof, we construct such an x'. Namely, choose a countable set C of x's and suppose all Dx are finite for x in C (if not we are through). Then clearly the union U of C with all the D~ for x in C is countable. But then any x' in the complement of U (nonempty because the deck is uncountable) has the property that C is contained in Dx,, and this is the desired construction. | So you have no winning strategy in the zero-memory game. However, it turns out that to win you do not need unbounded memory. All you need to remember is your last discard (which is perhaps left face up on the top of the discard pile) and once again you have a win if (and only if!) the axiom of choice is permitted. THEOREM 2. Using the axiom of choice, there is a win for
the second player provided she knows the cards in her hand and also her last discard. Proof: The winning strategy is simple. Well-order the deck. Then on your first move, discard your highest card. Thereafter, (A), discard the highest card which is lower than your last discard if there is one. Else, (B), discard your highest card. To see that this works, note that as long as you are in case (A) the last discard will be strictly decreasing as a function of time, and hence by the wellordering property the sequence must be finite, so case (B) must eventually occur. N o w look at some card x in your hand. If it is less than the current discard, then, by the observation above, you will surely discard it at some future time. If it is greater than the current discard, then when case (B) occurs, you will either discard x or some card greater than x, and then the previous argument again applies. | A third result, which also uses well-ordering, shows that the second player also has a winning strategy if she is allowed at each move to see the cards in her hand and also the set of all the cards that have been discarded. Theorem I is a special case of a general result of Martin Furer and Ernst Specker, whereas Theorem 2 and the third result mentioned are due to Richard Laver and Krzysztof Ciesielski. As far as I know, none of this work has been published.
Games People Could Play The game, christened C h o m p by Martin Gardner, is a variation on Nim. It has been around for quite a while, but some recent results lead to a n u m b e r of intriguing questions. The game is easily described. One begins by laying out a rectangular array of "cookies." Players move alternatively by choosing a cookie and then removing all cookies above and to the right of it. Figure 1 shows an initial 3 x 5 C h o m p position and the position after a possible first move in row 3, column 4.
00000 00000 00000
000 00000 @0000 Figure I
The loser is the player w h o is forced to pick up the poison cookie in the lower left-hand corner. The essential feature of the game is that with optimal play it should always be won by the first player. The argument is illustrated by Figure 2.
0 0 0 0 0
oO 0OloOO O0
00000
@0000
0 0 0 0
and hence he will eventually win. The other example is the n x n case where the first player plays as shown and thereafter plays the same move as his opponent but reflected in the diagonal (Fig. 4).
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00000
0 0 0 0
Figure 4 As an illustration of our ignorance, it seems experimentally that in 3 x n C h o m p the winning first move is unique. The winning move for 3 x 5 is shown on the right in Figure 1, but these winning first moves show no apparent pattern. It was originally conjectured that the winning first move was always unique, but the 6 x 13 game turned out to be a counterexample in which there are two winning first moves. C h o m p can also be played with an infinite number of cookies. The simplest example is the 2 x o; case (Fig. 5);
00000
.-
@0000
..
Figure 2
Figure 5
If removing the upper right-hand cookie (left above) gives player 1 a winning position, then the assertion is proved. If not, then it gives a losing position, and player 2 has a response which gives her a winning position (right above); but any such move by player 2 is a move player 1 could have m a d e on the first move himself. It is to be noted that this argument is completely nonconstructive, asserting only that a winning strategy for the first player exists but giving no indication of how to find it. Indeed, except for two special cases, almost nothing is known about the structure of these winning strategies. The exceptions are the 2 x n (and n x 2) games where one easily sees that the first player can always give his opponent a position in which the bottom row has one more element than the top row (Fig. 3):
for note that even though there are an infinite number of cookies, the game can only last a finite number of moves. In fact, this is the first example of a game which is a win
0000 @0000 Figure 3
f;o;" 000 000. Figure 6 for the second player, for it is easy to see that no matter what the first player does, the second player can move to give a position like that of Figure 3. It then follows that the 0; x a; game, shown in Figure 6, is a first-player win, for by choosing the element in row 3, column 1, he can give the opponent the 2 x ~ game. THE MATHEMATICAL INTELLIGENCER VOL 15, NO. 3, 1993
59
In an obvious way, the w x a; game can be represented b y the set of all lattice points in the positive q u a d r a n t of the plane, and this can be generalized to three or more dimensions. The g a m e on the positive octant in 3-space remains unsolved; is it a first- or second-player win? A $200 prize has been offered for the solution of this problem (for further information on this contact the c o l u m n editor). The new results alluded to earlier reduce this question to a problem in the arithmetic of transfinite ordinals as will n o w be explained. First, we note that C h o m p can be played with arbitrary ordinals; thus, given any ordinals ~ and fl, we m a y consider ~ x fl Chomp. Because of the well-ordered property of ordinals, it follows that any play of these games must terminate in a finite n u m b e r of moves. In the same way, one could also consider games played on the p r o d u c t of three or more ordinals. Next, a game position which is losing for the player w h o is about to m o v e has been called a P-position by Berlekamp, Conway, and G u y (Win ning Ways, Academic Press, 1982), where the P indicates that the game is a win for the previous mover. Figures 3, 4, and 5 are P-positions for Chomp. The following fact, communicated to me by Scott Huddleston, is a special case of w h a t he suggests might be called the Fundamental T h e o r e m of Chomp. We state it as follows: T H E O R E M . For any integer n there exists a unique ordinal c~ such that the n x c~ rectangle is a P-position.
Proof." We first note that the uniqueness of the critical ordinal is immediate, for if c~ gives a P-position with c~ < fl, then n x fl is not a P-position because the first player can m o v e to change the position to n x c~. We have already seen that if n = 2, then c~ = a;. H u d dleston has said that he is convinced that the rectangles 3 x w~ and 4 x Od2 are P-positions, but I have not seen proofs of these intriguing assertions, nor has he supplied a proof of the Fundamental Theorem; but George Bergman has, and the following is a mild modification of his argument. We will show, in fact, that the critical ordinal c~ must be a countable ordinal, so from n o w on all ordinals considered are assumed countable. Instead of cookies, it is better to think of a C h o m p position as a nonincreasing sequence of ordinals (~1, 999 c~n). For any integer 0 < m < n and ordinal ~, define f(c~, m) to be the u n i q u e ordinal fl, if it exists, such that (fl, fl . . . . . fl, ~, ~ . . . . . c~) is a P-position, w h e r e fl occurs m times (this is a position after a first m o v e in an n x fl game in which fl has been replaced b y c~in the top n - m rows). Let g(c~) = s u p f ( G m) for all ~ < c~ and 0 < m < n. Because the set of these (G m) is countable, g(c~) is a countable ordinal. N o w define the sequence of ordinals (c~i), where c~1 = 1 and ~i+1 = g(c~i), and let q, be the smallest ordinal greater than all c~. If n x -y is a P-position, the theorem is proved. If not, there is a winning first move, which gives a P-position ( % . . . , % ~, G . . . , ~) with ~ < % 60
T . E MATHEMATICALINTELLIGENCERVOL. 15, NO. 3,1993
where "~ occurs m times. Let us see whether m > 0 is possible. Then "~ w o u l d be f ( G m), and this w o u l d contradict the definition of % Therefore, the winning m o v e must give a position (G G - . - , ~), so the n x ~ game is a P-position. | Note that, like C h o m p proofs in general, this one is completely nonconstructive, giving no clue as to h o w to find the critical ordinal. A slightly more complicated a r g u m e n t shows that for any pair of ordinals c~and fl there exists a unique ordinal "~ such that the c~ x fl x -y game is a second-player win (thus, a P-position). H u d d l e s t o n has asserted that 2 x 2 x Od3 is a P-position. The $200 problem would be solved if one k n e w for which ordinal c~ the a; x o; x ~ game is a P-position. A possibly simpler question is to decide whether the 3 x 3 x ~; game is a first-player win. A n y takers?
Problems A Canonical Basis Algorithm (93-1) This p r o b l e m is adapted from a result of B. C. Eaves contained in a technical report of the Operations Research D e p a r t m e n t at Stanford. The following assertions have not a two-line but a t w o - w o r d proof, in the sense that given the two words, the a r g u m e n t becomes readily apparent (prerequisite, a s o p h o m o r e course in linear algebra). What are the two words? Let V be a finite set of vectors in real or complex nspace. Let B be a basic subset of V, and let X be the set of all coefficients obtained by expressing each m e m b e r of V as a linear combination of vectors of B. Consider the following algorithm.
(a) (1) If all m e m b e r s of X have n o r m at most 1, then stop. If not, there is some v in V and b and B such that the coefficient of b in the expression for v has n o r m greater than 1. Then, (2) replace b b y v in the basis and go to (1). Prove that the algorithm terminates. (b) Consider the same setup over the rationals and express all elements of X in lowest terms. If all numerators are odd, stop. If not, then for some v and b, the coefficient of b in the expression for v has an even numerator, so replace b by v. Prove that the algorithm terminates. (The c o l u m n invites someone to contribute a problem with a o n e - w o r d proof. After that we can perhaps start counting letters.)
An Old Story in a Contemporary Setting A traditional women's college is considering admitting men. The chairman of the Board of Trustees thinks it would be a good idea, but the college president disagrees. "If you admit men," she says, "more than half of the women students will leave before the end of the year." As a compromise, they agree to admit only 1% of men on an experimental basis. The end of the year rolls around, and at the Trustees' meeting the chairman announces triumphantly that the experiment has been a success. True, he admits, there were some defections by women, but the drop in percentage of women students was only 1%, from 99% at the start of the year to 98% at the end. "What did I tell you!" says the college president. THEMATHEMATICALINTELLIGENCERVOL.15,NO.3,1993 61
The Shape of the Ideal Column Reconsidered Philip G. Kirmser and Kuo-Kuang Hu
Comments on Previous Papers This is an interesting, famous problem about which many papers have been written. It is also an unusual one in the sense that a surprising number of good papers written by well-known, competent authors contain misstatements a n d / o r mistakes of various kinds. These errors are caused by attempts at too sophisticated generality; misinterpretation of words, such as "eigenvalue" and "buckling load", which are related but which do not have identical meanings in the way they are used by various authors; plain errors of statement; and artificial requirements for bounds on cross-sections or unnecessary treatment of arbitrary multiplicity of eigenvalues. Consider "too sophisticated generality." Several authors, among them Tadjbakhsh and Keller [1], Masur [2], and Seieranyan [3], describe column equations by fourth-order ordinary linear differential equations. Although convenient sometimes, it is never necessary to use fourth-order equations because all of the column equations they consider can be written as second-order ordinary differential equations. The use of higher-order equations can introduce extraneous eigenvalues which must be accounted for in careful analysis. Masur [2], striving for generality, includes a discussion of conditions for optimality for arbitrary multiplicity of eigenwtlues. Now, the multiplicity of eigenvalues cannot exceed the order of the differential equation which generates them. Unless single columns have additional constraints (see |4]), or eigenvalues for higher modes of buckling are considered, this discussion is a useless exercise. "Too sophisticated generality" also includes the use of "subspace of H 2, the space of L 2 functions on the interval (0, 1) with first and second distributional deriva62
tives in L 2" by Cox and Overton [5]. Physically, structural columns always bend in smooth curves of class C 2 except at isolated singular points where connectivity still requires C o curves. This implies that the use of old-fashioned Riemann integrability and conventional solution of differential equations should always suffice for finding the shape of the strongest column. The use of the same words, but which have differ-
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3 (~)1993 Springer-Verlag New York
ent definitions as used by various authors, has also contributed to misunderstandings and erroneous statements. The definition of "eigenvalue" used by Tadjbakhsh and Keller [1] is different from that used by Cox and Overton [5], who, on using an eigenvalue of Tadjbakhsh and Keller for the clamped-free column as being equal to the buckling load, scale it incorrectly and reach the erroneous conclusion that the strongest fixed-pinned column of Tadjbakhsh and Keller is actually weaker than the fixed-pinned column of constant cross-section. It is obvious from engineering intuition that this last statement must be wrong. Consider the question of the buckling load for the strongest fixed-pinned column of given volume and length. As shown in many places, including Timoshenko and Young [6], the buckling load for a uniform, fixedpinned column is P = 7r2EI/(0.69911) 2. The buckled shape of this column has an inflection point at x = 0.3008/measured from the fixed end. Because at an inflection point the bending moment is zero, the inflection point could be replaced by a pinned joint. This now internally jointed uniform column could be strengthened, while keeping the length and volume constant, by removing material from the column where it bends less When buckled, and adding it to places where it bends more. Such a redistribution of materials, which is referred to by Cox [7] as his "meta-theorem," "reaffirms the engineering principle that in order to keep something from bending, find out where it bends and add material there" [8]. The column could be strengthened more by repeating this redistribution of material as long as the eigenvalue for the corresponding buckling load is simple. If the eigenvalue becomes repeated, the criteria for redistributing the material to strengthen the column become more complicated because the bending, which is an arbitrary linear combination of two eigenfunctions, is not determined uniquely. A column cannot be infinitely strong, so an optimal shape must exist, and it is clear from this qualitative argument that the optimal form for the fixed-pinned column must be stronger than one of constant cross-section having the same volume and length. Several misstatements or omissions which cause misunderstanding occur in various papers, also. Tadjbakhsh and Keller [1], in their solution for the strongest fixedpinned column, assume that the eigenvalues are simple, and that the buckled deflection curves are C 2. These conditions yield a subset of the general C o solutions found by piecing together the optimal fixed-pinned-linked and Keller's [9] optimal pinned-pinned columns. Such a combination is really a structure of two separate columns, which together have a double eigenvalue for the optimal shape, for then the eigenvalue of the fixed-pinnedlinked part of it must equal that for the Keller [9] optimal pinned-pinned part. Tadjbakhsh and Keller's [1] C 2 solutions are subsets of the general C o optimal so-
lutions. Although their C 2 solutions, including those for higher eigenvalues, are correct, they state, referring to the fixed-pinned-linked part of their optimal column, "the remainder of the column has the shape of the strongest fixed-free column of its length and volume." This unfortunate error was propagated in Cox and Overton [5], who reached a wrong conclusion partly because of it. On occasion, an elementary oversight leads to misstatements. Cox [7], following his equation (16), which reads ~4[]~11 ]2 = cAB, states that "Equation (16) then implies that A cannot remain bounded in a neighborhood of x0." Here x0 is identified as "an inflection point," with an implication that/~"(x0) = 0. However, a point in a column at which the cross-section goes to zero is not necessarily an inflection point. It must act as a hinge to hold the pieces of the column together. Because a hinge cannot support a bending moment, the condition which should be used at x0 is A 2 ' (/~I,) = 0. Equation (16) can be satisfied if A]//"[ 2 = c. At x0, ~2/~,, = 0, so A and ~ must be functions of x such that limx-~x0 A 9 (/~,,)2 = c and limx~x 0 A2/~" = 0. It is easy to see that A can go to zero a n d / / " to infinity as x goes to x0 so that both limits are satisfied without imposing bounds on A. Keller's [9] optimal solution for the pinned-pinned column exhibits this. In fact, the condition A. (]~,,)2 _~ r together with the differential equation for the pinned-pinned column of Keller [9], imply his condition for optimality, y2 = r We surmise that Cox and Overton's [5] and Cox's [7] unnecessary introduction and use of bounds for crosssectional areas was caused over a misunderstanding of the implications of Cox's [7] equation (16). Seieranyan [3], in an otherwise excellent paper which presents the first semi-analytic solution for the optimal fixed-fixed column, makes the misstatement: "It is shown in this work that of the boundary conditions of the type hinge-hinge, clamp-hinge, clamp-free end, and clamp-clamp, only the last case allows multiplicity of the critical force, and this multiplicity does not exceed 2." As shown numerically in Kirmser and Hu [10], the multiplicity of the optimal "clamp-hinge" column is, in fact, two, and its eigenvalue is that of Tadjbakhsh and Keller [1]. This is verified by a new analytic solution which is presented below. We have made mistakes and misstatements in our published work, too. In Kirmser and Hu [11], we criticized Olhoff and Rasmussen's [12] and Masur's [2] work too harshly, with the words: "In their solutions, a stationary value for the functional ,~* = (1 - "Y),~l + ")"~2 is found instead of the maximum value for the functional A = max min()q, ,~2) which is the correct one. Since the topology of,~* differs from that of A, they have obtained a correct solution for a problem which only approximates that which was originally stated." The functional )~* is correct, but is weaker than A, for setting 6,~* = 0, as Olhoff and Rasmussen [12] and Masur [2] do, is a staTHE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
63
tionarity requirement which holds equally well for minimizing or maximizing A*, whereas A = max min(A1, A2) is always correct. We also stated, "The method outlined above ... yielded the buckling load 52.43432, the greatest lower bound now known for the optimal fixed-fixed column." This misstatement was caused by small errors in our computer program which was used to calculate it-another example of why mathematical proofs which depend on numerical computation must be examined carefully, or at least verified theoretically. In some ways, however, this was a fortunate error because it kept us working on an interesting and controversial problem. There are mistakes, misstatements, and unnecessary requirements in Olhoff and Rasmussen's [12] imaginative and important work. On p. 610, it is stated that: "Being based on the functional A*,..., the bimodal formulation.., possesses a property that is particularly valuable in the present context; it has the ability of handling automatically a problem where the optimal buckling load is, de facto, a simple eigenvalue. Clearly, such behavior manifests itself by the functions yl and Y2 becoming identical, thereby leaving the Lagrangian multiplier undetermined . . . . " For single eigenvalues, the -y which determines A* must be zero, not undetermined, and the eigenfunctions yl and y2 can never be identical whether the eigenvalues are single or double. Olhoff and Rasmussen's [12] work is based on their engineering insight that the eigenvalue for the optimal form of the fixed-fixed column is double, and they used bounds on the cross-sectional area to facilitate their computations, which are based on making changes in crosssectional areas which force the lowest eigenvalues together. Their numerical method is really an application of regula falsi, not calculus of variations. Masur [2], in a semianalytic method similar to that used by Seieranyan [3], also assumes that the eigenvalues associated with the optimal form of the fixed-fixed column are double. He states: "Even if the optimal design is in the interior of the admissible design space, multiple eigenvalue solutions are not stationary, but singular." "Necessary and sufficient conditions for local and global optimality are explored and explicit optimality criteria are established for a double mode solution. In that case the space of all admissible design changes is split into a two-dimensional subspace in which the dual eigenvalues separate and a complementary subspace in which they remain coincident. It is within this latter subspace that sequential approximations must take place." As the analysis below indicates, the assumption of double eigenvalues is never necessary, nor is the use of sequential operations in the subspace in which the eigenvalues are double. Furthermore, the multiple calculus of variations procedures used provide smooth variations of the eigenvalues, with the attainment of the optimal form of the column demonstrated by simple tests on the eigenvalues and variations thereof.
64
THE MATHEMATICALINTELLIGENCERVOL. 15,NO. 3, 1993
A Multiple Calculus of Variations M e t h o d for F i n d i n g the Optimal Shapes of C o l u m n s The method, which is a general one, is outlined here for finding the strongest fixed-fixed column of unit length and volume. The differential equation and boundary conditions for this problem are given by 4~rA , (A2(x)y"(x)) '' + --~--y (x) = 0
(1)
y(0) = y'(0) = y(1) = y'(1) = 0,
(2)
and where A(x) is the cross-sectional area of a column of circular cross section, E is the modulus of elasticity, y(x) is the deflection curve, A is its buckling load, and the primes denote derivatives. The strongest column is that for which the smallest A is a maximum. Rayleigh's quotient for this problem is (y'(x)) 2 dx
Ai(A) = ~
)1/0,
A2(x)(y~'(x)) 2 dx,
(3) with variations 6A yielding, for y normalized by
f0 (y,)2
= 1,
6Ai(A) = ~
A(y")2(6A) dx
+
A2y"(~y '') dz - --~
y'(6y') dx + . . .
, (4)
w h e r e . . , indicates terms which are of higher order in the variations. The first-order terms which are underlined add to zero for arbitrary admissible variations 6y, as can be seen by multiplying Eq. (1) by ~y and integrating by parts. With the notation fi = A . (y~t)2 and ]i = f01 A(Y~')2 dx, a particularly useful form for 6A is OO
6A = ~--~(fi - ?~)ki,
(5)
i=1
for such variations preserve the volume constraint f~ ~ A d x = O. Using this notation, variations in all eigenvalues can be expressed as
~A2 9
E --
>{kl} k2
1
i,(i,-7,)dx
;o
,
(6)
In summary, the general criterion for optimality is that for the lowest two eigenvalues, ;~1 _< ,~2, an a _> 0 exist such that (fl - f l ) + a(f2 - f2) = 0. (11)
which can be written as
(/0
(fi
{6Ai}
(co x 1) =
-
"fi)(Yd
-
']j) dx
)
(kj} (oo x 1)
This criterion can be met in a n u m b e r of ways:
(mij) (oo x oo)
{kj} x 1)
(7)
by redefining the constants k and elements m q as shown by comparison 9 In this equation, the rows are ordered according to the size of ,~i. Equation (7) can be used to drive all of the eigenvalues in arbitrary directions to the extent possible by assuming small {6~}, solving for the constants {k}, a n d using these to define variations which will make the changes desired while keeping step sizes small to preserve local linearity. In the fixed-fixed column problems, it is k n o w n that the multiplicity of eigenvalues is less than or equal to 2 [3, 8]. Thus, it is sufficient to use only the first two rows of Eq. (7),
6~2
= (2 x oc) (c~ x 1)'
(8)
to drive the lowest eigenvalue to its greatest possible value. If (mij) is of rank 2, this equation can be written as {6~} (2xl)
_ (mij) (N) {kj} - (2x2) (2xoo) (ooxl) (mid) {K} (2x2) (2xl)'
(9)
where Nk = K. This shows that if the optimal shape has not been reached, there are m a n y variations 8A given by k or K which can be used to drive ~1 and )~2 higher. If the rank of (mid) is less than 2, its rows are proportional. If the constant of proportionality is positive, an o p t i m u m has not been reached because K can be chosen to drive the eigenvalues higher. If the constant is negative and ,kl = A2, a local m a x i m u m has been reached because any nonzero K drives one eigenvalue u p and the other down, or keeps one constant while the other is driven up or down. At an optimum, with a as defined below, Eq. (8) becomes ((~.~1) 2 q- ((~,,~2) 2 =
9
[:
(1
1. a = 0 a n d , ~ l < ,k2. This implies that fl = ] l , a constant, and that the eigenvalues are distinct. This is theTadjbakhsh and Keller [1] and Keller [9] case. 2. fl = f l and f2 = f2- This is impossible because it requires that the two eigenfunctions Yl and Y2 be the same. 3. )~1 = )u and a > 0, with fl and f2 zero and constant, or constant and zero, piecewise. This is the optimal Tadjbakhsh and Keller case, as mentioned in [10]. 4. ,kl = /~2 and a > 0, with (fl - ]1) q- a(f2 -- 7 2 ) = 0. This is the Masur [2], Seieranyan [3], and Olhoff and Rasmussen [12] case. From Eq. (11), it follows that ~'~1 "F O ~ 2
:
((fl - - f l ) + a ( f 2 - 7 2 ) ) 6 A d x
= 0, (12)
which is the criterion for optimality used in bimodal optimization [2, 3, 12]. But here it has been derived from the usual Rayleigh's quotient, without a priori assumption of bimodality, as a natural consequence of an optimization using multidimensional calculus of variations, and without requirements for b o u n d s on the cross-sectional area. Bimodal optimization, which depends on good engineering judgment, is never needed analytically.
A n Exact Solution for the Optimal Fixed-Pinned-Linked C o l u m n Consider the column shown in Figure 1. The length ll is a flexible fixed-pinned cantilever column which has a finite buckling load. The link 12is pinned to the cantilever column at its left end and to another pinned joint at its right end. Note that the cantilever column 11 is not fixedfree unless/2 is infinite.
+ ol 2) 2
(:1 - 71)
(fj -- "]j)k d
dx
=0. (10)
Because the set {fj - fd : J > 1} is linearly independent [4], this implies that the optimal shape is unique.
Figure 1. A fixed-pinned-linked column. THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3, 1993
65
c o s 2 8(0)
tI)(8(0))- sin68(0)
Lambda 10000
I
kl
I
~
I
I
I
I
.(38
sin 48(0) ) 32
sin 28(0) m + _ _ 38(0)8
(20)
1000
and
/X
100
vl = volume of the cantilever = 9L2V ~ 5 ,
1 = l
I
0
I
0.1
0.2
I
I
I
0.3
0.4
0.5
Figure 2. Lambda as a function of
0.6
0.?
0.8
tl/L
ll/L.
Assuming small deflections and the Euler beam theory, the governing differential equation can be written, using L = I1 + 12,
A2y ' ' + A
y-~2(L-x)
) =0,
y(0) = y'(0) = A2y"(ll) = 0and (Aay")'(ll) = A6
12"
(14)
= y - (6/12)(L - x), it be-
A2~b'' + A~b = O,
(15)
with the boundary conditions r
=
s
-12
r
-- - F2' ~ 0, and (A2r
'
A2r
r X6
-- [2"
+/~(~-1/3 ----O.
and
(
3(0(0)) = 3 ~ r - 0 ( 0 ) + cosO(O)
= A 312sin30(~),
r
tl
ThE MATHEMATICALINTELLIGENCERVOL.15,NO. 3,1993
This structure is composed of the optimal cantilever fixed-pinned-linked column joined to the optimal pinned-pinned column of Keller [9]. Keller's eigenvalue is 47r2 (V22~ (22) = -$ \ )' where v2 and 12are the volume and length of the pinnedpinned column. For the optimal fixed-pinned-linked column of length L and volume v,
(v21~ 4~r2 (v2~ = AK, \ L 2] = ~ ~l 2]
(23)
where vl + v2 = V and ll +/2 = L. From these conditions, vl _ 61rr v 6~rr + 122
and
v2 _ v
12
(24)
67r4~ + 12"
It follows that
(17) LaI~HK = - - ~
(25)
6~22
9 can be written 1 ( ( l l / L ) -- COS2 0(0) ~ O -- - ~ cot O(0) ~ s ] ~ 0-0--~ 7'
(18)
1sin 20(0) )
9
66
The Optimal Solution for the Complete Fixed-Pinned-Linked Column
(16)
The eigenvalue AHK of this equation, expressed in terms of a parameter 0(~) is, with A(~) = A0 sin 2 0(~)
where 0(0) is found from fl(0(0)) = ll/L and r -O(fl-l(ll/n)). A graph of AHK for Vl = L = 1 is shown as a function of ll/L in Figure 2.
1 L2AHK=2-~
= O,
As in Tadjbakhsh and Keller [1], the assumption that the eigenvalues are simple and the use of volume-preserving variations leads to the condition r = A3(x) for optimality. This substitution changes the differential equation to r
(21)
\ L4 ) '
(13)
with boundary conditions
With the substitution r comes
(v2~
(26)
and AHK for the optimal fixed-pinned-linked column as (19)
AHK
8(0)
~2 (v2 ~
16 tan2 fl(0) ( sin 2 \(/1/L-)C~os 0(0)]
= 27
\L4] "
(27)
Tadjbakhsh and Keller's Solution for the Optimal Fixed-Pinned Column Is Correct On p. 162 of Tadjbakhsh and Keller [1], the two equations following their Eq. (40) are 12 .... L
3 7r cos 0(0) sin -3 0(0) 2
(28)
(note that in [1], 7r is missing from this equation) and v2
-
cos 0(0) sin -5 0(0),
(29)
V
and corrosion as well. Yet, engineers should k n o w the theory and its implications for ideal structures and use them to their advantage in the art and science of designing structures. Mathematics, especially interesting analysis, is of great practical value to engineers in the real world. As can be seen in the case of this famous column problem, engineering sense and intuition can be of value to mathematicians, too. Remember that several of the world's greatest mathematicians have been engineers and scientists who have been led to invent new mathematics for reasons of practical application.
from which Vl sin 2 0(0) v = ( l l / L ) - cos 2 0(0)"
(30)
Substitution into Tadjbakhsh and Keller's [1] eigenvalue yields /~TK
16 ~- ~
tan 2 0(0)
(v 2 ) ~5
16 (sin20(0))2 -- 27tan20(0) (ll/L-y--cos20(0)
(V2~
\L2]
"
(31) Now, the eigenvalues ATK and ;~HK are related by /~TK = L2/~HK, SO Tadjbakhsh and Keller's solution agrees exactly with ours. H o w can this be? Tadjbakhsh and Keller have assumed simple eigenvalues and restricted their solution to C 2 functions and have tacitly assumed that the singularity of the differential equation at the place where the cross section goes to zero can be removed by a suitable definition. Our solution has the column composed of two parts. The eigenvalues are simple in each part, and the solutions are C 2 separately. They are joined at the hinge of the column to form C O solutions for a system of two equations which has a double eigenvalue. Tadjbakhsh and Keller's [1] solution is correct only because their C 2 restriction yields a subset of our C O solutions. Their statement that the cantilever part of the column has the shape of the optimal fixed-free column, however, is wrong.
Concluding Remarks After all of this discussion of an interesting problem, one could ask h o w important this theoretical analysis is for practical engineering construction. The surprising answer is, not very. Several requirements which complicate the analysis and design have not been considered. Practical columns must be designed so that failure in compression is avoided. Compressive stresses have been ignored completely here. The end conditions for real structural columns are never completely fixed or pinned as assumed here. Fire protection m u s t be provided, and resistance to deterioration caused by rot
References 1. I. Tadjbakhsh and J. Keller, "Strongest columns and isoperimetric inequalities for eigenvalues," J. Appl. Mech. 29 (1962), 159-164. 2. E. Masur, "Optimal structural design under multiple eigenvalue constraints," Int. J. Solids Struct. 20 (1984), 211231. 3. A. P. Seieranyan, "A solution of a problem of Lagrange," Dokl. Akad. Nauk SSSR 271 (1983), 337-340 [English translation: Soy. Phys. Dokl. 28(7) (1983), 550-551.] 4. Ph.G. Kirmser and K.K. Hu, "On the multiplicity of eigenvalues in column optimization problems," Developments in Theoretical and Applied Mechanics Volume XV, Georgia Institute of Technology, March 22-23, 1990, pp. 275-278. 5. S.J. Cox and M.L. Overton, "On the optimal design of columns against buckling," SIAM J. Math. Anal. 23(2) March (1992), 287-325. 6. S. Timoshenko and D.H. Young, Elements of Strength of Materials, 5th ed., D. Van Nostrand, New York, 1968, p. 273. 7. S.J. Cox, "The shape of the ideal column," Mathematical Intelligencer 14(1) (1992), 16-24. 8. K.K. Hu and P.G. Kirmser, "Remarks on the optimal shape of the fixed-fixed column," Optimization of Distributed Parameter Structures: volume 1, edited by E.J. Haug and J. Cea, Sijthoff and Noordhoff, Alphen aan den Rijn, The Netherlands, 1981, p. 524. 9. J. Keller, "The shape of the strongest column," Arch. Rat. Mech. Anal. 5 (1960), 275-285. 10. Ph.G. Kirmser and K.K. Hu, "On an error in Seieranyan's paper on a solution of a problem of Lagrange," Developments in Mechanics 15, Proceedings of the 21st Midwestern Mechanics Conference, Michigan Technical University, Houghton, Michigan, August 13-15, 1989. 11. Ph.G. Kirmser and K.K. Hu, "A critique of bimodal optimization in the fixed-fixed column problem," Developments in Mechanics 13, Proceedings of the 19th Midwestern Mechanics Conference, Ohio State University, Columbus, Ohio, September 9-11, 1985. 12. N. Olhoff and S. Rasmussen, "On single and bimodal optimum buckling loads of clamped columns," Int. J. Solids Struct. 13 (1977), 605-614. EECE Department Kansas State University Manhattan, KS 66506 USA CE Department Kansas State University Manhattan, KS 66506 USA THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3,1993 67
z
a~
b~
Z
t~
QO
Jet Wimp*
Partial Differential Equations I: Foundations of the Classical Theory, Encyclopedia of Mathematical Sciences, Vol. 30 by Yu. V. Egorov and M.A. Shukin Heidelberg: Springer-Verlag, 1992. 259 pp. US$79.00 ISBN 3-540-52002-3.
Linear and Boundary Integral Equations, Encyclopedia of Mathematical Sciences, Vol. 27
by V.G. Maz'ya and S. PriJssdorf Heidelberg: Springer-Verlag, 1991. 233 pp. US$59.00 ISBN 3-540-51997-1.
Reviewed by David Colton Differential and integral equations have been linked since Newton's discovery of the fundamental theorem of calculus. With Ivar Fredholm's 1903 masterpiece, Sur une classe d'6quations fonctionnelles [3], the marriage seemed secure. However, the consummation was not complete: The two fields developed along separate lines rather than together. Nevertheless, integral equations methods still play an important role in partial differential equations, so it seemed natural to me to review both of these books together. What happened to integral equations after Fredholm's 1903 paper? From 1903 to the 1950s, the story is simple. Under the influence of D. Hilbert, E Riesz, E. Schmidt, and J. Schauder, the theory of Fredholm integral equations of the form (I + T ) f = 9, where T is a compact
*Column Editor's address: Department of Mathematics, Drexel University, Philadelphia, PA 19104 USA.
operator on a Banach space, rapidly became a beautiful, self-contained branch of analysis with important applications in mathematical physics. The extension of the theory to one-dimensional singular integral equations by F. Noether and T. Carleman and the introduction of Wiener-Hopf integral equations by N. Wiener and E. Hopf added other jewels to the crown. Indeed, by the time I entered college in 1960 there were already many "classic" textbooks on integral equations [10, 11, 12, 17]. A one-semester course on integral equations was standard in most graduate programs in the United States. By the mid-1960s, however, many of those not working in the field considered the subject to be beautiful, but dead. These were the actual words m y thesis advisor said to me in 1966 when I told him I was interested in learning about integral equations! Before continuing the story of integral equations, let us look at the history of partial differential equations. Here again, the story, in its broad strokes, is simple, although strikingly different from that of integral equations. Until the 1960s, the theory of partial differential equations was a hodgepodge, at least as far as graduate education in the United States was concerned. Most often, students learned about the simplest partial differential equations such as the wave, heat, and potential equations in a course on methods of mathematical physics. A general theory was still in development. Indeed, for this reason many graduate programs did not even have a course on partial differential equations when I entered college in 1960. In contrast to the many integral equations texts, there was only one text suitable for a graduate course on partial differential equations [12]. By the middle of the 1960s, it appeared that the marriage of integral and differential equations formed by Fredholm in 1903 was in danger of being completely dissolved. The 1960s not only ushered in an intense period of social and political conflict in America, but also effected fundamental changes in many academic disciplines.
THE MATHEMATICALINTELLIGENCERVOL.15, NO. 3 (~)1993Springer-VerlagNew York 6 9
Mathematics was no exception. The books of Garabedian [5] and Hellwig [6] announced the arrival of partial differential equations as a mature, coherent discipline. Soon, year-long graduate courses on partial differential equations became common. Because of the influence of earlier textbooks by Riesz and Sz.-Nagy [13] and Kolmogorov and Fomin [8], the theory of integral equations became more a part of functional analysis than a discipline in its own right. But functional analysis also began to play a dominant role in the theory of partial differential equations. Upstaged by the development of distribution theory and variational methods for solving elliptic boundary value problems, the methods of integral equations seldom appeared in textbooks on partial differential equations [4, 7, 16]. By the 1970s, they appeared to most graduate students of that time to be more of a historical artifact than a practical tool. Fortunately, the above pessimistic view of the interconnection between integral equations and partial differential equations has changed in the last 20 years. Partial differential equations is still the dominant partner (as evidenced by the proposed eight volumes on partial differential equations in the Encyclopedia of Mathematical Sciences, in contrast to a single volume on integral equations). However, with the emergence of the theory of multidimensional singular integral operators and pseudodifferential operators as a major tool in the study of partial differential equations, integral equation methods are no longer an historical curiosity (cf. [15]). In a more classical direction, integral equation methods in scattering theory are of fundamental importance in many applications and are currently the subject of active investigation [2]. The use of the theory of integral equations of the first kind to investigate inverse problems in partial differential equations is one of the more fashionable topics in applied mathematics (cf. [1, 9]). Further, these new efforts to revive the marriage of integral and partial differential equations are being incorporated into the graduate program at leading American universities. Fredholm must surely be smiling in heaven at these latest developments! (On the other hand, after seeing Fredholm determinants, some of my students are convinced that Fredholm is residing in hell.) The two volumes under review are part of a massive translation project of the Soviet Encyclopedia of Mathematical Sciences being directed by Springer-Verlag. The volumes in this series that I have seen to date are all of high quality and attractively presented. As it has so often done in the past, Springer-Verlag has performed a real service to the mathematical community in undertaking this project. The main idea of volumes in the Encyclopedia is to survey specific areas of mathematics, stating the main results but only giving proofs in simple special cases. The final product should provide a relatively painless way for mathematicians to find out what is happening in areas outside their specialty. 70
THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3,1993
The book Partial Differential Equations h Foundations of the Classical Theory is the first of a proposed eight volumes on partial differential equations. The chapter titles of this first volume tell the reader what to expect: Basic Definitions and Examples, the Cauchy-Kovalevskaya Theorem and its Generalizations, Classification of Linear Differential Equations, Distributions and Equations with Constant Coefficients, Elliptic Boundary Value Problems, Sobolev Spaces and Generalized Solution of Boundary Value Problems, Hyperbolic Equations, Parabolic Equations, General Evolution Equations, Exterior Boundary Value Problems and Scattering Theory, Spectral Theory of One Dimensional Differential Operators, and Special Functions. Included in the above, for example, are Holmgren's theorem, Fourier transforms of tempered distributions, capacity, embedding and trace theorems, lacunae, application of the theory of semigroups, and the scattering matrix. Particularly welcome is the chapter on scattering theory (written by Professor Vainberg), which is usually left out in such surveys. On the other hand, I find the chapter on one-dimensional spectral theory inappropriate. I would prefer to see, instead, a section on inverse problems, for example, some of the recent lovely results on the impedance tomography problem. However, this is a minor complaint, and, all in all, I think the volume is a great success and an excellent preparation for future volumes in the series. As might be expected, the book Linear and Boundary Integral Equations is considerably more condensed than the one on partial differential equations because the authors have to get everything into one volume. A further difference is that the book on integral equations is really two books combined into one, the first part (by S. Pr6ssdorf) on linear integral equations and the second part (by V.G. Maz'ya) on boundary integral equations, that is, applications of integral equations to partial differential equations. The chapter titles again give an idea of what is here: Some Facts from Abstract Operator Theory, Fredholm Integral Equations, One Dimensional Singular Equations, Multidimensional Singular Equations, Theory of Harmonic Potentials, Integral Equations for the Equations of Lam6 and Stokes, Some More Applications of the Boundary Integral Equation Method, The Integral Equations of Potential Theory in the Spaces C and Lp, and Boundary Integral Equations on Piecewise Smooth Surfaces. A huge amount of material is crammed into the above chapters. For example, there are subsections on Hille-Tamarkin operators, Triebel classes, Wiener-Hopf integral equations, Calder6n-Zygmund operators, pseudodifferential operators, integral equations for the biharmonic equation, time-dependent boundary integral equations in visco-elasticity, the Fredholm radius for potentials on piecewise smooth surfaces, and much more. Of the two books under review, the one on partial differential equations is the more successful. The pace is more leisurely, more theorems are proved (or an outline of the proof given), and the selection of topics is
more even. For example, the presentation on boundary integral equations by Maz'ya has one paragraph on the Helmholtz and Maxwell equations and an entire chapter (out of five altogether) on the equations of Lam6 and Stokes. On the other hand, the chapter on linear integral equations by Pr6ssdorf is so condensed that it is more a scholarly reference for insiders than an introduction for outsiders. That is probably what Professor Pr6ssdorf had in mind, but, in my view, the introductory style of Egorov and Shukin is more attractive. Nevertheless, both volumes are a welcome addition to the literature and I am looking forward to the appearance of more volumes of the Encyclopedia in the near future. I also hope that the Mathematical Intelligencer will continue reviewing selected volumes as they appear so I can tell which ones to purchase in order to become more mathematically literate!
References 1. J. Baumeister, Stable Solution of Inverse Problems, Friedr. Vieweg & Sohn, Braunschweig, 1986. 2. D. Colton and R. Kress, Integral Equation Methods in Scattering Theory, Wiley,New York, 1983. 3. I. Fredholm, Sur une classe d'6quations fonctionnelles, Acta Math. 27 (1903) 365-390. 4. A. Friedman, Partial Differential Equations, Holt, Rinehart and Winston, New York, 1969. 5. P. Garabedian, Partial Differential Equations, Wiley, New York, 1964. 6. G. Hellwig, Partial Differential Equations, Blaisdell, New York, 1964. 7. F. John, Partial Differential Equations, Springer-Verlag, New York, 1982. 8. A.M. Kolmogorov and S.V. Fomin, Elements of the Theory of Functions and Functional Analysis, Graylock, Rochester, NY, 1957. 9. R. Kress, Linear Integral Equations, Springer-Verlag, New York, 1989. 10. S.G. Mikhlin, Integral Equations, Pergamon, New York, 1957. 11. N.I. Muskhelishvili, Singular lntegral Equations, Noordhoff, Groningen, 1953. 12. I.G. Petrovsky, Lectures on Partial Differential Equations, Interscience, New York, 1954. 13. E Riesz and B. Sz.-Nagy, Functional Analysis, Ungar, New York 1955. I4. E Smithies, Integral Equations, Cambridge University Press, Cambridge, 1958. 15. M. Taylor, Pseudodifferential Operators, Princeton University Press, Princeton, NJ, 1981. 16. E Treves, Basic Linear Partial Differential Equations, Academic Press, Orlando, FL, 1975. 17. F. Tricomi,Integral Equations, Interscience, New York, 1957.
Department of Mathematical Sciences University of Delaware Newark, DE 19716 USA
History of Continued Fractions and Pad4 Approximants by Claude Brezinski New York: Springer-Verlag, 1990. viii + 560 pp. US $79.00, ISBN 0-387-15285-5.
Reviewed by William B. Jones Continued fractions and Pad6 approximants have played major roles in the development of mathematics. In number theory, continued fractions were used to establish the irrationality of ~r(and other real numbers) and the transcendence of numbers such as e and 7r. Modern spectral analysis of operators and moment theory originated in the research on continued fractions by Stieltjes (1894) and Hamburger (1920-1921). Closely related to this are the general theories of orthogonal polynomials and Gaussian quadrature. Continued fractions and Pad6 approximants provide powerful methods for the representation of analytic functions, for the acceleration of their convergence, and for summing divergent asymptotic series. Continued fractions had their greatest impact during the 19th century. Brezinski asserts that then "The subject was known to every mathematician and even every scholar in many countries. An army of Mathematicians, among them most of the famous ones, contributed to the development of continued fractions and in their application to various problems of mathematics and physics." A rebirth of interest and research activity in the subject took place around the middle of the 20th century. This rebirth was due in part to the advent of high-speed electronic computers and the algorithmic character of continued fractions and Pad6 approximants. It was due also to an expanded set of applications in theoretical physics and chemistry, number theory, computer science, automata, electronics, signal processing, and other areas of engineering and applied sciences. History of Continued Fractions and Padd Approximants by Brezinski describes the development of continued fractions from the Elements of Euclid (c. 306 B.C. to c. 283 B.C.) until modern times ending in 1939 A.D. The book is divided into six periods (chapters) in chronological order. The Early Ages (Chapter 1) extends from Euclid until the 12th century A.D. and includes work by Greek Chinese, Indian, Arabic, and European mathematicians. Continued fractions in this period did not appear explicitly. Rather they were rational numbers embedded in the Euclidean algorithm for finding the greatest common divisor (g.c.d.) of two positive integers a and b. We recall briefly the Euclidean algorithm: Let a and b denote positive integers with a > b. We set r0 = a, rl = b; then for k = 0, 1 , 2 , . . . , we find positive integers rk+ 2 and qk such that
rk = rk+lqk + rk+2
and
0 ~ rk+2 ~ rk+l.
THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3,1993 7 1
If n is the first index k such that Vn+2 = and
rn = rn+lqn
rn+l
0,
then
Brouncker obtained the infinite continued fraction representation
is the g.c.d, of a and b.
4 re
-
From this computation, one obtains as a by-product the regular continued fraction expansion a b
-
ql +
4 re
1
q2+ + - -1
Much work was done in this period to obtain rational approximations of irrational numbers such as rr and v ~ , where A is a positive integer. Other work involved the solution of Diophantine equations. Modern notations for finite continued fractions such as the one above include
q0+ and
i~(1) k=l
,
1 1 q0+ . . . . . .
1l
1l
ql + q2 +
1
+ qn
11 Iq--;
oo [~__s ~,,, ,} \ bo + ~=,K a k
=
al a2 a3 bo + b l + b2 + b3 + "'" '
where the elements ak and bk can be complex numbers or functions of complex variables or even more general mathematical objects. The First Steps (Chapter 2) begins with Leonardo of Pisa, also called Fibonacci (1170-1250), who made the first attempt at a general definition of continued fractions. Brezinski attributes the "birth of continued fractions" to P.A. Cataldi (1548-1626), professor of mathematics and astronomy at Firenze, Perugia, and Bologna. Cataldi developed a symbolism for continued fractions, and, at least for some special cases, he studied the second-order linear difference equations and determinant formulas satisfied by the nth numerators An and denominators Bn. The Beginnings of the Theory (Chapter 3) centers around the work of the 17th-century mathematicians W. Brouncker (1620, Castle Lyons, Ireland-1684, Westminster), C. Huygens (1629-1695, The Hague), and J. Wallis (1616, Ashford-1703, Oxford). Wallis introduced the term "continue fractum," derived the second-order linear difference equations for numerators and denominators of general continued fractions and considered the convergence question for infinite continued fractions. 72
THEMATHEMATICAL INTELLIGENCERVOL.15,NO.3,1993
9
25
49
2 + 2 +
..-
3.3.5.5.7.7.-2.4.4.6.6.8...
Huygens applied continued fractions to number the teeth for gears in an automatic planetarium that he constructed. Golden Age (Chapter 4) is the designation of 18thcentury work on continued fractions. Brezinski asserts, "It was marked by three outstanding mathematicians, L. Euler (1707-1783), J.H. Lambert (1728-1777), and J.L. Lagrange (1736-1813), all belonging to the Berlin Academy of Sciences. The 18th century was also that of the birth of Pad6 approximants, which are connected with continued fractions and played (and are still playing) an important role in applications." Euler proved that every rational (irrational) real number has a finite (infinite) regular continued fraction representation and that every periodic continued fraction is a zero of a quadratic equation. He obtained the expansion e =2+
These notations are now extended to infinite continued fractions
1
2+2+
for Wallis' infinite product
1 =q0+
=1+
1 1 1 1 1 1 1 1+2+1+1+4+1+1+6+
1
...
and other similar ones. He applied continued fractions to solve Riccati differential equations. "His 1748 publication, 'Introductio in analysin infinitorum,' was the first extensive systematic exposition of the theory of continued fractions." All three of the above mathematicians obtained the continued fraction expansion tan x -
1
1
1
1
x -1 + 3x -1 + 5x -1 + 7x -1 + " " .
"Then Lambert showed that tan x is irrational if x is a non-zero rational number. Since tan rr/4 = 1, it follows that re/4 and then re are irrational." Lambert's conjecture that e and re are transcendental was proved by continued fractions in the next century by Hermite and Lindemann. Among other things, Lagrange applied continued fractions to the study of Diophantine equations. The invention of Pad6 approximants emerged gradually from continued fractions, but they were also defined without this connection in the works of D. Bernoulli (Gronigen 1700-Basel 1782). The explosion of work on continued fractions in the 19th century (Maturity, Chapter 5) and early 20th century (Modern Times, Chapter 6) has been cited at the start of this review. We add that many results of this period no longer exist in living memories. As they are rediscovered, they may well lead to interesting and important applications. Brezinski's History can play a large role.
The book contains numerous quotes from and references to original sources including an appendix of documents. Other useful data can be found in an extensive scientific bibliography with 2302 references, a list of 78 works, a historical bibliography with 478 references, a name index giving page references and birth--death data, and a subject index. In his introduction, Brezinski acknowledges, "I soon realized that I am not a historian, that I knew nothing about the methods of history, and that it is in fact quite difficult to approximate a historian. Thus this book is more a collection of facts and references about continued fractions than their history in the modern sense of the word, that is a profound analysis of the ancient mathematical works on the subject." Yet Brezinski has rendered an enormous contribution to future historical investigation. He has provided also a valuable resource for future researchers in continued fractions a n d / o r Pad6 approximants. Moreover, his user-friendly writing style makes reading pleasant as well as profitable.
Department of Mathematics University of Colorado Boulder, CO 80309-0426 USA
Abstract Algebra and Famous Impossibilities by A. Jones, S.A. Morris, and K.R. Pearson N e w York: Springer-Verlag, 1991. x + 187 pp. US $29.95, ISBN 0-387-97661-2
Reviewed by Israel Kleiner The famous impossibilities in the title refer to the impossibility of squaring the circle, doubling the cube, and trisecting an angle, using a straightedge and compass alone. The authors introduce enough field theory to prove the three impossibilities. The standard topics-polynomials, algebraic numbers, field extensions--are introduced gently, making the book accessible to a wide student audience. The students are assumed to have had a course in linear algebra. The classical Greek mathematical works--those of Euclid, Archimedes, and Apollonius--contain theorems and problems. Both theorems and problems, construction problems in particular, were an integral part of the Greek mathematical tradition. The three so-called classical problems, which probably date back to the 5th century B.C., are typically Greek, for they ask for exact solutions. A thousand years earlier, the Egyptians had squared the circle "for all practical purposes" by squaring 8/9th of its diameter. Why were the Greeks interested in construction problems? Some m o d e m writers, with 2000 years of hindsight, have ascribed to Greek mathematics a construc-
tivist philosophy. They have interpreted constructions as demonstrations of the existence of entities mentioned in theorems. For example, Euclid shows how to construct lines perpendicular to given lines before he deals with propositions about right angles. However, there is sufficient evidence to indicate that the investigation of construction problems was a prominent activity of Greek mathematics independent of any constructivist tendencies. Being astute mathematicians, the Greeks undoubtedly would have been sympathetic to Hilbert's assertion at the 1900 International Congress of Mathematicians that "as long as a branch of science offers an abundance of problems, so long is it alive." In fact, Greek attempts to solve the three classical problems served (it is thought) as motivation for the introduction of new geometric techniques and several algebraic and transcendental curves, among them the conic sections (!), the spiral, the conchoid, and the quadratrix. Most pronouncements on Greek mathematics must be treated with caution. There are no primary sources for early (pre-Euclidean) Greek mathematics; we must piece it together from fragments transmitted by later (often much later) commentators. We cannot, for example, authenticate the existence of Pythagoras (presumably in the 6th century B.C.). And even Euclid's Elements is a copy of a copy of a copy of . . . . The book was written ca. 300 B.C., but the earliest available manuscripts date from the tenth century A.D. Why focus on the three classical problems, and whence the insistence on their solution by straightedge and compass? We have no definitive answers. These are questions of current historical research that involve detective work of considerable complexity (see [5], [6]). For example, the story that the Delian oracle motivated the problem of the duplication of the cube, appealing as it is, has now been discounted. The most prominent Greek mathematical texts, those of Euclid, Archimedes, and Apollonius, are no different from most of today's books: They offer the end product of mathematical activity, hence provide little motivation. What can be said with reasonable confidence is that the three classical problems were part of a large body of "natural" problems in the context of Greek mathematics, and that attempts to solve them broadened considerably the methods and scope of Greek geometry. Two examples of such problems--dealt with by Apollonius and Archimedes, respectively--are the construction of a normal to a conic through a point outside the conic, and the cutting of a sphere by a plane so that the two resulting segments are in a given ratio. There are no explicit statements in Greek sources about the need to perform constructions using only straightedge and compass, and hardly any comments indicating preference for the use of these tools over other methods. It is likely that the main, and initially the only, objective of Greek mathematicians was to solve the problems by any means possible. Many of the most prominent Greek mathematicians, among them Hippocrates, EuTHE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
73
doxus, Eratosthenes, Archimedes, Apollonius, Heron, and Pappus, gave solutions of one or more of the three classical problems using various techniques. Eutocius, a 6th-century mathematician, lists 12 known methods for doubling the cube. (Recall that Gauss gave six proofs of the quadratic-reciprocity law and that over a hundred are now available.) It was only after the accumulation of diverse solutions that one began to classify them. Pappus (ca. 300 A.D.) states that the Greek mathematicians divided geometrical problems into three kinds: plane problems, which can be constructed by straight lines and circles; solid problems, solvable by the intersection of conics; and linear (or "line-like") problems, which require for their construction more complicated types of curves. Pappus adds that if a problem can be constructed by straight lines and circles, it is a mistake to use other means. The insistence on straightedge and compass, then, was programmatic, an attempt to get as much as one could with as little machinery as possible (cf. "elementary" proofs of the Prime Number Theorem). What is important is that, whether or not the Greeks had a preference for the straightedge and compass, mathematicians of the 17th and later centuries thought that they did. Attempts to solve the three classical problems continued in the 17th and 18th centuries. For example, Pascal, Newton, and Maclaurin devised various methods for trisecting an angle. The distinctive feature in some of these efforts was the use of the new algebra (analytic geometry) of Descartes and Fermat. This algebra, however, served only to reformulate the three classical problems, not to solve them (with straightedge and compass, that is). A solution called for a more powerful algebra, the "abstract algebra" which began to emerge in the early 19th century. The impossibility of doubling the cube and trisecting an angle with straightedge and compass was first proved by Pierre Laurent Wantzel (1814-1848) in 1837. The problem of squaring the circle was disposed of when Lindemann proved the transcendence of 7r in 1882. (Two thousand years earlier the Greeks seem to have sensed that the problem of quadrature of a circle differs from the other two problems. For they classified the latter two as "solid" problems and the squaring of the circle (usually) as "linear," hence more complex.) What algebraic tools were available to Wantzel? There were the works of Ruffini and Abel on the unsolvability by radicals of the general polynomial equation of degree greater than four, and the work of Gauss on the solvability by radicals of the cyclotomic equation and on the construction of regular polygons with straightedge and compass. (Although Galois completed his work on Galois theory in 1832, it was not published till 1846.) In none of these treatises does the field concept appear explicitly. Wantzel, too, does not introduce the language of fields, but the essentials of the ideas we use today to resolve these construction problems are there: the reduction of 74
THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3, 1993
the problem to that of the solution of equations, the notion of an irreducible polynomial equation, the concept of a rational function of a given number of elements, and conditions for constructibility given in terms of the iteration of the solution of quadratic equations. (The first abstract definition of a field was given as late as 1893, by Weber.) Wantzel, who got degrees in mathematics and engineering from the Paris Polytechnic where he spent his academic career as a mathematics instructor, gets little mention in histories of mathematics. But Liouville thought sufficiently highly of the 22-year-old to publish the paper on the famous impossibilities in his prestigious Journal de Mathdmatiques [9]. Wantzel's paper also contains a proof that Gauss's sufficient condition for the constructibility of regular polygons is also necessary. (Gauss stated the necessity but never proved it.) In 1843 Wantzel proved the "irreducible cubic" theorem, namely, that the solution by radicals of a cubic irreducible over the rationals, all of whose roots are real, must be expressed in terms of complex radicals. (An encounter with this paradox "forced" Bombelli three centuries earlier to introduce complex numbers.) In 1845 Wantzel gave a proof of the unsolvability of the general quintic, claiming that the proofs of Ruffini and Abel were unsatisfactory. All told, Wantzel published about 20 mathematical papers. He was undoubtedly a highly creative mathematician. So ended a 2000-year saga. But not for everyone. Circle-squarers and angle-trisectors abound to this day. (See, for example, [2] and [3].) The book under review uses the machinery of field theory to prove the nonconstructibility with straightedge and compass of the three classical problems, but it does so without overwhelming the student. On the other hand, the idea is not to establish the famous impossibilities via the most elementary route (for that see [1] or [4]), but to use the geometry to motivate the introduction of some abstract algebra. The Introduction gives a brief overview suggesting that the solutions of the construction problems hinge on the dimensions of certain vector spaces. But they hinge at least as much on fields. This could be quickly pointed out: If a and b are constructible (real) numbers, so are their sum, difference, product, and quotient (if the denominator is not zero), hence the constructible numbers form a field (a subfield of the reals). Moreover, if F is a field of constructible numbers, and a c F, a > 0, then v'a is constructible, hence so is the field F(x/-a ). All this is easy to show. Thus to study constructible numbers it is important to study fields and (quadratic) field extensions. Perhaps the authors would consider adding some such comments to the Introduction of a subsequent edition of their text. (These results do appear in the b o o k but only on p. 93.) The book is written in a leisurely style for the average student. In fact, it could be used for independent study. The proofs are very carefully presented. Many
contain informal remarks which give indications of how one ought to begin or to proceed. (Example: "We want to find a polynomial, with c~ as a zero, which has coefficients in Q. This suggests . . . . ") But these remarks are set apart from the "formal proofs" by special brackets, and this separation, in my opinion, is inadvisable. After all, where do we draw the line between informal and formal proof? And what, in any case, is a formal proof in the context of an introductory text? A very welcome feature of the book is the Additional Reading for each chapter. These references are wellchosen and are preceded by comments about what they contain and how they may broaden or deepen the material of the text. The following are further noteworthy aspects. a. There are ample exercises at the end of each section, at a level suitable for the intended audience of the book. b. Self-contained proofs of the transcendence of r and 7r are presented. c. No use is made of quotient rings. An elementary proof using vector-space ideas shows that if F is a field and c~ an algebraic number, then F(~), the ring of polynomials in c~ with coefficients in F, is a field. (All fields are Subfields of the complex numbers.) d. Numerous theorems are given specific names which suggest their content. (Example: "Small Degree Irreducibility Theorem" stands for the result that a polynomial of degree 2 or 3 is reducible over a field if and only if it has a zero in the field.) e. A brief concluding chapter entitled "Other Impossibilities and Abstract Algebra" sketches results on regular polygons, quintic equations, and integration of functions in closed form. To this one might add a recent (20thcentury) result, with roots in Greek antiquity, characterizing all constructible lunes (see [7]). Here is another suggestion for a future edition: Include a chapter characterizing the constructible regular polygons. A regular n-gon is constructible with straightedge and compass if and only if n = 2kplP2...pl, where p~ are distinct primes of the form 22~i q- 1. The tools for the proof of the necessity of this result have already been developed in the text. The sufficiency can be proved using some elementary group theory (see [8]). The extra investment of time and effort by the students would be well worth it. They would be introduced to such fundamental algebraic ideas as cyclotomic fields, groups, and the interplay between groups and fields. They would be richly rewarded. Every course should have an ideology, a philosophy. Here is mine, in several parts, for a course based on material in this book (but not only for such a course). 1. Problems are the sources for much of the theory developed over the centuries. Moreover, "concrete" problems often give rise to "abstract" theory. Moral: asking ques-
tions is a fundamental mathematical activity. A second moral: there is nothing so practical as a good theory. 2. Compartmentalizing mathematics, into areas such as geometry, algebra, trigonometry, calculus, is, in general, not helpful. In the case under discussion, geometric problems could only be solved algebraically. Other remarkable instances of the indivisibility of mathematics are in the use of analysis (the continuous) to solve problems in number theory (the discrete). Moral: bring to bear on the solution of a problem any idea or technique you find useful. 3.2000 years (or 20 years, or 20 hours) may pass between the posing of a problem and its solution. Persevere. 4. Impossibility results are an important feature of the mathematical scene. Hilbert spoke about them in his 1900 address on "Mathematical Problems," expressing his conviction (shared, he claimed, by all mathematicians) that "every definite mathematical problem must necessarily be susceptible of an exact settlement, either in the form of an actual answer to the question asked, or by the proof of the impossibility of its solution .... "The first result of the latter type goes back to the Pythagoreans, who proved the impossibility of measuring the diagonal of a unit square by a ratio of whole numbers. Showing that a problem is impossible is, of course, not the same as being unable to solve the problem. This is not an easy idea to get across to students. 5. Simplicity in mathematics is elusive. Simple questions may have very complex answers. Number theory is, of course, the source par excellence of such examples. The book under review may serve as a text for putting into practice this or similar ideologies.
References 1. R. Courant and H. Robbins, What is Mathematics?, Oxford University Press, 1941. 2. A. De Morgan, A Budget of Paradoxes, Dover, 1954 (original, 1872). 3. U. Dudley, A Budget of Trisections, Springer-Verlag, 1987. 4. N.D. Kazarinoff, Ruler and the Round, Prindle, Weber & Schmidt, 1970. 5. W.R. Knorr, The Ancient Tradition of Geometric Problems, Birkh/iuser, 1986. 6. W.R.Knorr, Textual Studies in Ancient and Medieval Geometry, Birkh/iuser, 1989. 7. M.M. Postnikov, Fundamentals of Galois Theory, 2nd ed. (in Russian), Moscow, 1963. 8. F. Richman, Number Theory: An Introduction to Algebra, Brooks/Cole, I971. 9. EL. Wantzel, Recherches sur les moyens de reconnaRre si un Probl6me de G6om6trie peut se r6soudre avec la r6gle et le cornpas, ]ournal de Mathdmatiques 2 (1837), 366-372. Department of Mathematics and Statistics York University North York, Ontario M3J 1P3 Canada THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 3,1993
75
Robin Wilson* Metrication Through the centuries, various counting systems have been used for weights and measures. The Babylonians (c. 1800 B.C.) used a number system based on 60 (still used today for measuring time and angles), while native American tribes have used number systems based on 5, 10 and 20. Leibniz discovered a binary system (later used extensively for computers), while until recently the British used a monetary system based on 12 and 20. Even now, some countries (including Britain and the U.S.A.) continue to use archaic systems of weights and measures. Shortly after the French Revolution, a commission was set up to investigate the value of a metric system for France; the chairman of this commission was the mathematician Joseph-Louis Lagrange (1736-1813). Since then, many countries have adopted the metric system, and a substantial number of metrication stamps have been issued. Here we present a selection of these, including the controversial cartoon stamps of Australia, issued in 1973.
*Column editor's address:Facultyof Mathematics,The Open University,MiltonKeynes,MK76AA England. 76
THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 3 (~)1993Springer-VeflagNew York
