The Mathematical InteUigencer encourages comments about the material in this issue. Letters to the editor should be sent to the editor-in-chief, Chandler Davis.
A Modest Proposal Regarding Anatole Beck's article "The Decimal Dysfunction" in the Mathematical In telligencer, vol. 17 (1995), no. 1: As a computer scientist, I applaud his proposal to switch from the awkward, old-fashioned decimal system to the useful, modern octal system, but I fear that, human nature being what it is, people will not flock to base eight without some external pressure. So, like Swift, I have a modest proposal ... Since our addiction to the decimal system is based, as Beck says, on "the biological accident of pentadactylism~" we can easily promote the octal system (and especially hand calculations in it) by promoting tetradactylism - - simply insist on a minor surgical procedure at birth (or possibly in utero) to remove every infant's little fingers and little toes. Furthermore, then, use of the hexadecimal system can be encouraged by outlawing shoes and socks. Any attendant inconveniences would be a small price to pay for the conveniences of a "binaricized system." Of course, some minor adjustments will be needed in keyboard layout, but that will be universally welcomed since the QWERTY arrangement is notoriously unergonomic. Mankind must learn to adapt to the modern a g e - we must not let Luddites dictate scientific policy. Vive la Rdvolution t. Off with their digits!
- - A S e r i e s f r o m the K a r a n a p a d d h a t i - From the asymptotic expansion of Borwein, Borwein and Dilcher [1] N
~r
~T~(-1)k+l (1 = 2 ~-~i +
1 5 N3 + N 5
61 N7 •
)
k=l
(where 4[ N) it follows that the sequence {aN} aN-
1 1
1 1 1 3+~-~•
1 1 N_l+2~
converges to '~ much better than the Leibniz series. Modifying the a n into
1)§ (1 _
_ 1 + 1)+(12
~1 + 1 / . . .
(1 • 3 1 4 + 2.3-----~
2
1 -4
1)
N~+2-N
1 1 4 . 5 . 6 + 6.7.-----~"'"
Binarily yours,
•
1 ( N - 2). ( N - 1). N '
one obtains the series (e.g., [2]) Edward M. Reingold Department of Computer Science University of Illinois Urbana, IL 61801-2987, USA
~r
3 ~ = 4 +
k=l
(-1) k+l 2k- (2k-~ l"y: (2k + 2)"
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3 (~)1995 Springer-Verlag New York
3
This series, however, dates back to the Karanapaddhati, a script written at the beginning of the 15 th century by the South Indian scholar Nilakan.tha [3], [4], [5]. It is unk n o w n how Nilakantha derived it.
References 1. J.M. Borwein, P. B. Borwein, and K. Dilcher, Pi, Euler Numbers, and Asymptotic Expansions, Amer. Math. Monthly 96 (1989), 681--687. 2. K. Knopp, Theorie und Anwendungen der unendlichen Reihen. 4. Aufl., p. 109, Exerc. 109 c). Springer, Berlin/Heidelberg 1947. 3. J.E. Hofmann, Geschichte der Mathematik, 2. Aufl., de Gruyter, Berlin 1963. 4. J.E. Hofmann, Math.-Phys. Sem.-Ber. 3 (1953). 5. A.P. Juschkewitsch, Geschichte der Mathematik im Mittelalter, Teubner, Leipzig, 1964. F. L. Bauer Department of Computer Science TU Munich D-80333 Munich, Germany
S i n e - Gordon Equation Let me make some comments on the paper b y Robert McLachlan, "A gallery of constant-negative-curvature surfaces," Mathematical Intelligencer, vol. 16 (1994), no. 4, 31-37. The author writes that the s i n e - G o r d o n equation "apparently appeared for the first time in the w o r k of Hazzidakis" in 1880 [1]. This differential equation had been derived before by other mathematicians. The earliest source I k n o w is E. Bour in 1862 [2]. Papers of O. Bonnet [3] and A. Enneper [4] on the subject followed closely. The s i n e G o r d o n equation e m e r g e d in the differential-geometric context as the condition that a surface, w h e n described in asymptotic coordinates or lines of curvature, has constant negative Gaussian curvature. The fact is to be considered as k n o w n in differential geometry after [3] and [4]. What is k n o w n t o d a y u n d e r the name "B/icklund transformation" d e v e l o p e d in just this context. Searching for a way to find all pseudospherical surfaces, L. Bianchi in 1879 [5] formulated a surface transformation following a geometrically inspired Ansatz of A. Ribeaucour of 1870. S. Lie reformulated it, and A. V. B~cklund gave the transformation its final form in 1883 by extending it to a one-parameter family [6]. So new solutions of the s i n e G o r d o n equation can be p r o d u c e d from k n o w n solutions; one m a y even start with the trivial zero-solution. M a n y decades later the s i n e - G o r d o n equation reappeared in physics. The well-known physicist J. I. Frenkel and his co-worker T. A. Kontorova in Leningrad (USSR) in 1938 described m o v i n g dislocations in a crystal by a chain m o d e l - - t h a t is, with continuous time and discretized space variable - - which corresponds to the sine G o r d o n equation [7]. (It seems to be an interesting open problem whether the F r e n k e l - Kontorova chain has gen4
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
uine solitonic character.) Some approximations led them to a solution which corresponds to the well-known s i n e G o r d o n one-soliton solution. In the early 1950s A. Seeger, et al. in Stuttgart (Germany) p r o p o s e d the s i n e - G o r d o n equation as a model in solid state physics [8]. They were aware of the F r e n k e l Kontorova papers as well as of the differential-geometric interpretation of the 19th century. In particular, they used the B/icklund transformation to p r o d u c e exact (solitonic) solutions. The story of rediscoveries carried on; let us mention E C. Frank a n d J. H. v.d. Merwe [9] (in the same year as [8] but less detailed) and later T. H. R. Skyrme's model of baryons [10]. The s i n e - G o r d o n equation acquired its status of a distinguished solitonic differential equation only after the classical p a p e r ofM. J. Ablowitz, D. J. Kaup, A. C. Newell, and H. Segur [11], where it was solved by the inverse scattering method. In fact, it was e m b e d d e d in a considerably w i d e r set, the AKNS class of equations, which can be solved this way. Let me finally note that the n a m e of the differential equation u n d e r consideration originated from a kind of joke: some formal resemblance to the K l e i n - G o r d o n equation led to a choice of w o r d s which r h y m e with " K l e i n - G o r d o n . " S. Coleman quotes in [12], p. 402, from a letter of David Finkelstein to him: I am sorry that I ever called it the sine-Gordon equation. It was a private joke between me and Julio Rubinstein and ! never used it in print. By the time he used it as title of a paper he had earned his Ph.D. and was beyond the reach of justice. The first public appearance of the questioned name is in [131. Discussions with R. Schimming (Greifswald, Germany) on the subject of this letter are gratefully acknowledged.
References 1. J. N. Hazzidakis, Ober einige Eigenschaften der Fl~ichen mit constantem Kriimmungsmaass. J. reine angew. Math. (Crelle's J.) 88 (1880), 68-73. 2. E. Bour, Th6orie de la d6formation des surfaces. J. F:cole Polytechn. 39 (1862), 1 - 148. 3. O. Bonnet, M6moire sur la th6orie des surfaces applicables sur une surface donn6e. J. Ecole Polytechn. 42 (1867), 1 - 151. 4. A. Enneper, Analytisch-geometrische Untersuchungen V. Nachr. k6nigl. Ges. Wiss., Georg August Universita't Gf~'ttingen (1868), 258-277. 5. L. Bianchi, Ricerche sulle superficie a curvatura constante e sulle elicoidi. Ann. Scuola Norm. Sup. Pisa 2(1) (1879),
1-57. 6. A. V. B/icklund, Om ytor med konstant negativ kr6kning. Lund Universitets Arsskrifi 19 (1883), 1-48. 7. J.I. Frenkel and T.A. Kontorova, On the theory of plastic deformation and twinning I, II, III (In Russian). continued on p. 66
References 1. Bertrand Russell, "Recent Work on the Principles of Mathematics," International Monthly 4 (1901), 84. 2. A.E. Housman, "The Name and Nature of Poetry," in Collected Poems and Selected Prose, London: Allen Lane, The Penguin Press (1988), p. 364. 3. Clive Bell, Art, London: Chatto & Windus (1949), p. 25. 4. Isaiah Berlin, The Crooked Timber of Humanity, New York: Random House (Vintage Books) (1990), pp. 5-6. 5. David Knowles, The Evolution of Medieval Thought, New York: Random House (Vintage Books) (1962), p. 55. 6. Plato, Timaeus, 29 ft. 7. Romans 1:20. 8. Spinoza, Ethics, Part II, prop. vii.
9. Boethius, De Institutione Arithmetica (translated by Michael Masi as Boethian Number Theory), Amsterdam: Editions Rodopi B.V., 1983, I, 1. 10. John Dewey, The Quest for Certainty. New York: Minton, Balch, 1929, p. 23. 11. Plato, Thaeatetus, 191c ff, 193b-196a, 200c; Aristotle, De anima 424a. 12. Shakespeare, Measure for Measure, II, ii, 117-122. 13. The most learned and fascinating expositor and defender of the traditional philosophy of art was Ananda K. Coomaraswamy; see, for example, TraditionalArt and Symbolism, Princeton NJ: Princeton University Press (1986). 14. Dante, Inferno, xxxii, 10-12. 15. Richard Paul, "Jean-Philippe Rameau (1683-1764), the Musician as Philosophe," Proc. Am. Phil. Soc. 114 (1970), 140-154. 16. Johann Winckelmann, "History of Ancient Art," in Winckelmann: Writings on Art, David Irwin (ed), London: Phaidon (1972), pp. 117ff.
17. Honor6 de Balzac, Le p~re Goriot, trans. M. A. Crawford, London: Penguin (1951), p. 134. 18. Isaiah Berlin, (ref. 4) passim. 19. M. L. Abrams, The Mirror and the Lamp, New York: Oxford University Press (1953). 20. S. T. Coleridge, Table Talk and Omniana of Samuel Taylor Coleridge, quoted in Ref. 19, p. 58. 21. Howard E. Hugo (ed.), The Portable Romantic Reader, New York: Viking Press (1957), p. 61. 22. Gabriel Josipovici, The Worldand the Book:A Study ofModern Fiction, London: Macmillan (1971), pp. xiii-xiv. 23. M. Kline, Mathematics in Western Culture, New York: Oxford University Press (1953), p. 9. 24. Ivor Grattan-Guinness, Br. J. History Sci. 7 (1974), 186. 25. J~nos Bolyai, letter of 3 November 1823, in Roberto Bonola, Non-Euclidean Geometry. New York: Dover (1955), "Translator's Introduction" to The Science of Absolute Space, p. xxviii. 26. William Wordsworth, The Prelude, III, 142. 27. On both G6del and Thom, cf. Philip J. Davis and Reuben Hersch, The Mathematical Experience, New York: Penguin Books (1983), pp. 318-319. 28. Constance Reid, Hilbert-Courant, New York: SpringerVerlag (1986), p. 194. 29. G. Frege, The Foundations of Arithmetic, 2nd rev. ed., trans. J.L. Austin, Evanston IL: Northwestern University Press (1980), p. 108.
539 Highland Avenue Ottawa, Ontario K2A 2J8 Canada
continued from p. 4
8.
9. 10. 11. 12. 13.
JETP 8 (1938), 89-95 (I), 1340-1349 (II), 1349-1359 (III). Shortened translation of I und Ih On the theory of plastic deformation and twinning. J. Phys. (Moscow) 1 (1939), 137-149; translation of h On the theory of plastic deformation and twinning. Physikalis. Zeitschr. Sowjetunion 13 (1938), 1 - 10. A. Seeger, H. Donth, and A. Kochend6rfer, Theorie der Versetzungen in eindimensionalen Atomreihen III: Versetzungen, Eigenbewegungen und ihre Wechselwirkungen. Z. Physik 134 (1953), 173-193. E C. Frank and J. H. v.d. Merwe, One dimensional dislocations IV. Proc. Roy. Soc. London A 201 (1950), 261-268. J. K. Perring and T. H. R. Skyrme, A mode unified field equation. Nucl. Phys. 31 (1962), 550. M. J. Ablowitz, D. J. Kaup, A. C. Newell, and H. Segur, Method for solving the sine-Gordon equation. Phys. Rev. Lett. 30 (1973), 1262-1264. S. Coleman, Classical lumps and quantum descents. Zichichi: New Phenomena in Subnuclear Physics. Plenum Press, New York (1977), pp. 297-407. J. Rubinstein, Sine-Gordon equation. J. Math. Phys. 11 (1970), 258 - 266.
Markus Heyerhoff Marienstrasse 18 58455 Witten Germany 66
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
Number Magic Unexplained. On p a g e 48 of The Intelligencer's Winter 1995 issue, the author m a d e an error s o m e w h a t d a m a g i n g to his credibility in the rest of the article. H e said that "the value of 288 is a particularly felicitous one [for erecting spurious stoichiometric uniformities], for 288 has the largest n u m ber of integer divisors of a n y n u m b e r from 0 to 576." But in fact 360 has six m o r e divisors t h a n 288 and three m o r e than 576. Such a mistake s e e m s especially regrettable in an article so d e p e n d e n t u p o n s h a r p criticism. A fun piece withal.
Charles Mus~s Mathematics & Morphology Research Centre 45911 Silver Avenue Sardis, British Columbia V2R 1Y8 Canada Editor's note: The error was made by the sharp critic H. Bull in 1941 and went undetected by The Intelligencer's author
and myself. It does not diminish by much our admiration for Dr. Bull's debunking.
ADVERTISEMENT TRANSFINITE
SET
THEORY
IS TRIVIALLY
INCONSISTENT
COPYRIGHT ~ 1995 MICHAEL HUGH KNOWLES. ALL RIGHTS RESERVED. TRANSFINITE SET THEORY IS INCONSISTENT: cardinality(co+l)=card(l+co)=Ro+l=l+No>No, which also falsifies The Continuum Hypothesis, or there exist transfinite sets which are not selfequivalent; either way ~n accepted result or axiom of (transfinite) set theory is contradicted.
PROOF: It suffices to consider co+l. Heretofore mathematicians have "reordered" co+l to l+co and shown that l+co was equivalent (~o) to co ~ No. I.e. mathematicians matched the element co+l with 1, matched the unmatched 1 with 2, "and so on" to "infinity" generating a bijection which ostensibly demonstrates the set equivalence co+l~l+coooco~ob~',0. (Notationally, the bijection is: co+l.--1, and i.-.i+l for i ~ , or some such.) This "and so on" is the problem. The nubbin of the inconsistency and this proof is that heretofore unquestioned concept that every set is self-equivalent. Let us look at the standard reordering again using new terms/concepts (but using the same old fundamental "serial processes" used to generate co ~b~0 and co+l and the "simultaneous" bijection between them; see comment belowT). Let us refer to the one-to-one correspondence of an element with another element (in some important cases itself') as a "link" (purely terminological, for emphasis). Now take co+1 ~ co +1: there is a bijection of the set co+l to itself, one which has every element "linked" to itself. Let us note-th~it to start to reorder the set co+l so as to make it equivalent to coooN0 we must break this link between the element co+l ('"'7) and itself. We have remaining the set co which (the nubbin) is self-equivalet~t, co oo co. Remember, this means every element of co ~oco is//nked to itself (for now). We also now refer to the now unlinked element co+l as being in "LIMBO" (conceptualT) To reorder, we next break the link between 1 and itself, which places the 1 in LIMBO, and we "forge" the link between 1 and co+l taking co+l out of LIMBO. Instead of co+l in LIMBO we have 1. The rest is obvious: as we reorder we have a succession of numbers in LIMBO, but always at least one such number (unless we forge a one-to-two link, or some such). 1) I F we find an unlinked number somewhere in co to link the number in LIMBO to, it means that co was/is n o t self-equivalent, a standard contradiction. 2) I F we do not find such an unlinked number in co, then we can not link the number in LIMBO to any number in co, and co+l is the next obvious candidate. We must therefore acknowledge (there are quibbles and details, but the conclusion is obvious) that: cardinality(co+l)=card(l+co)=No+l=l+No>No, also a standard contradiction. Either way transfinite set theory is standardly inconsistent, and trivially so, fatally flawed with an "accounting" error. (The standard "simulaneous bijection" in fact invisibly creates and/or ignores an additional element which must either be included in co or in co+l. Either way...; see comment below!) Assuming that we forgo non-self-equivalent sets, the Continuum Hypothesis is falsified since N0+l is a cardinality >No and <2 ~~.
QED.
Comment: a minor variant of this proof was rejected by one reviewer whose only reason was: "There is a fundamental misconception in your work, namely that the equivalence between co and co+l is demonstrated in a serial process. In fact the bijection is defined simultaneously." ???!!! THAT'S W H Y THIS KIND O F THING C A N TAKE A "KUHN'S A G E " TO B E A C C E P T E D / THE FOUNDATIONS OF SET THEORY/MATHEMATICS ARE FATALLY FLAWED WITH AN "ACCOUNTING"/BOOKKEEPING ERROR, AND THE MORE MATHEMATICIANS WHO MADE AWARE OF THIS, THE SOONER IT WILL BE ACCEPTED. I AM LOOKING FOR A MAJOR PUBLISHER WHO DOESN'T NEED TO WAIT. M. H. KNOWLES, 562 KENDALL AVE. #14, PALO ALTO, CA 94306-2721 THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995 5
The Opinion column offers mathematicians the opportunity to write about any issue of interest to the international mathematical community. Disagreement and controversy are welcome. The views and opinions expressed here, however, are exclusively those of the author and neither the publisher nor the editor-in-chief endorses or accepts responsibility for them. An Opinion should be submitted to the editorin-chief, Chandler Davis.
Will Mathematics Survive. Report on the Zurich Congress V. I. A r n o l d Every four years mathematicians from around the world gather together at their International Congress of Mathematicians to find out who are the new champions (as in the Olympic Games or the "Hamburg accounting" described by Shklovskii). In August 1994 the Congress took place in Zurich. (This is the third time it has been held there; the very first Congress was in Zurich, in 1897.) The Congresses are not numbered, because not everyone agrees on which past Congresses should be included. In the years prior to the Congress, a specially selected International Program Committee (whose membership is secret until the opening of the Congress) chooses invited speakers. This year's invited talks were 16 plenary talks of one hour and 156 sectional talks of 45 minutes. There are 19 sections (mathematical logic, algebra, number theory,.., to history of mathematics and mathematical pedagogy), and the talks were given in seven halls simultaneously. Every day one could attend six talks. An invitation to speak at the Congress is considered a great honor; it can be (unfortunately?) very important for the career of a mathematician in a very strained world job market. This year among the 16 plenary speakers 3 were from the Russian school of mathematics (in Kyoto, 1990, there had been 4 out of 15). Among the 156 sectional speakers I counted 14 from the Russian school (in Kyoto, 19 out of 139). In these counts I did not consider the present place of employment. Why our standing has dropped from
14% to 9% in four years--say, by a third--remains to be explained. At the Congress the names of those to be honored with Fields Medals were announced: J. Bourgain (France and and USA), E. Zelmanov (Russia and USA), J.-C. Yoccoz (France), P.-L. Lions (France). These medals, awarded to mathematicians aged at most 40, are often compared to the Nobel Prizes (there is no Nobel Prize for mathemat-
1 This is a translation of an article in the general-circulation m a g a z i n e
Eureka, s o m e w h a t a m p l i f i e d b y the author. 6 THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3 (~1995Springer-VerlagNew York
ics). The comparison is undeserved: unlike the Nobel Registered Participants in the Zurich Congress: Prizes, the Fields Medals pass by many of the truly out2370 (Down from 4102 at Kyoto) standing people, and in particular Russians. To give three medals at once to representatives of the French mathematical school, and all three'of them noted for the art of manipulation of inequalities, is hardly a help to the international prestige of French mathematics 2 particularly coming at a time when the president of the International Mathematical Union (the organization naming the Fields Committee) was a well-known French analyst. It is hard to affirm a causal relation between these circumstances; that would imply a quite unlikely degree of corruption. But it is one more reminder how invalid is the comparison of Fields Medals to Nobel Prizes. The Nobel Committee asks the opinion of a much wider group The Assembly did adopt a re~olution to make public of specialists than the Fields Committee does, and as a when appointed the identity of the Chair of the Program rule it does not leave itself open to suspicions (even un- Committee (so that this person could come under presfounded) of the sort pointed out above. (I am afraid I sure). Delegates from developing countries hoped that heard such suspicions expressed by all too many partici- the entire deliberations of the Program Committee and pants at the Congress, from many countries and special- the sectional committees would be made public. Counties.) tries without an established mathematical tradition tend This year, many at the Congress reacted to the names to be represented in the Assembly by politicians rather of the medalists with, "Who is he?" Well, according to than mathematicians. The resolution by the Assembly Plutarch, for a young person a medal is not a reward but carries a very real danger which could have grave cona deposit toward future achievement. Let us hope that sequences for the world mathematical community. this year's laureates go on to achievements justifying the investment. I counted 10 women among the invited speak- The difference between the tenth best, who will ers. This included - - a special h o n o r - - p l e n a r y talks be invited, and the eleventh, who will not, is in the opening session (M. Ratner, "Interaction be- very small. tween ergodic theory, Lie groups, and number theory") and the closing session (I. Daubechies, "Wavelets and other methods of localization in phase Each sectional subcommittee ("panel") is supposed to space"). Outside of the regular program was a spe- name ten or so as best among the twenty or so most accial "Emmy Noether Lecture" by a woman mathe- tive people in its area (who did not give invited talks at matician. This was delivered by Academician O.A. previous congresses). The difference between the tenth Ladyzhenskaya (St. Petersburg). best, who will be invited, and the eleventh, who will At the General Assembly of the International Math- not, is very small. An attempt to make discussion of ematical Union (a sort of mathematicians' UN) held in this difference public will only add to the weight of Lucerne just before the Congress, the American delega- extra-scientific considerations (representation of differtion proposed to "increase the representation of women ent countries, sexes, nationalities, etc.). The relatively few and to achieve a better balance of ethnic groups" among women speakers at the Zurich Congress won this honor invited speakers. This proposal was rejected by the As- in fair competition with men, without allowances being sembly as a hidden insult to both women and ethnic made. 4 groups. One Assembly delegate remarked, "It is strange The Assembly gave special attention to the public imthat, contrary to their usual practice, Americans didn't age of mathematics. mention sexual minorities. "3 At the beginning of this century a self-destructive democratic principle was advanced in mathematics (es2 Here I take a view contrary to that of P. Cartier. pecially by Hilbert), according to which all axiom sys3 The remark was found offensive by many. Let m e try to explain why. tems have equal right to be analyzed, and the value of It was heard as a witty reductio ad absurdum: the speaker meant to a mathematical achievement is determined, not by its thwart efforts for participation of w o m e n and minorities by putting significance and usefulness as in other sciences, but by t h e m in analog~ with efforts for participation of homosexuals. The wit relies, then, on the listener finding absurd the notion of defending homosexuals' participation. The insult to homosexuals was incidental to the speaker's intent to laugh d o w n the American proposal, but it hurt. - - Editor's Note.
4 Certainly. But this fair competition occurred only after vocal d e m a n d s that Congresses stop underrepresenting w o m e n . See Lenore Blum, Mathematical Intelligencer vol. 9, no. 2 (1987), 2 8 - 3 2 . - - E d i t o r ' s Note. THE MATHEMATICALINTELLIGENCERVOL.17, NO. 3, 1995 7
its difficulty alone, as in mountaineering. This principle quickly led mathematicians to break from physics and to separate from all other sciences. In the eyes of all normal people, they were transformed into a sinister priestly caste of a dying religion, like Druids, parasitic on science and technology, recruiting acolytes in the mathematical schools by Zombie-like mental subjection.
... the angel of topology and the devil of abstract algebra fight for the soul... Bizarre questions like Fermat's problem or problems on sums of prime numbers were elevated to supposedly central problems of mathematics. ("Why add prime numbers?" marvelled the great physicist Lev Landau. "Prime numbers are made to be multiplied, not added!") Unfortunately, mathematicians themselves contributed a lot to entrenching this image of their science, especially to entrenching the myth of its inaccessibility to the uninitiated. Hermann Weyl, one of the greatest mathematicians of our times (who worked, by the way, in Zurich), said, "In these days the angel of topology and the devil of abstract algebra fight for the soul of each individual mathematical domain. "5 In the first half of the century, the devil was winning. A special "axiomatic-bourbakist" method of exposition of mathematics was invented, to make it perfectly pure. For example, suppose we are saying that the value of a product is unaffected by the order of the factors. If we want, we can define multiplication using "rules for addition of columns." That the answer is independent of the order of multiplication can be deduced purely formally from one of these rules without knowing anything of the content of the operation of multiplication. This formal proof is urged on students by the criminal bourbakizers and algebraizers of mathematics. If we didn't know the content of the idea of addit i o n - i f we had not first counted apples or pebbles or (with Mayakovskii) cigarette butts or locomotives-clearly we could not understand the formal proof. It is convincing only to those who have undergone a distinctive algebraic perversion of the mind, and is useless for teaching and for all applications. The grave consequences of this perversion for mathematical education in Russia and elsewhere are well known. Whole generations of mathematicians came along knowing no other style of mathematics-- and of course, no other sciences. Avenging their humiliating experience in school, leaders of most countries, like the proverbial pig under the oak, planned and implemented the extermination of mathematics. According to American data, this process will take 10 to 15 years. 5 " I n v a r i a n t s , " Duke Math. J. 5 (1939), see p. 500. 8
THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3,1995
Their logic is simple. England got nothing for Newton inventing the calculus; or Germany for Leibniz devising the notation the whole world uses; or France for Poincar6 creating modern mathematics (topology and dynamical systems), which is indispensable in, say, radio. The American leaders, in accordance with the opinion of their voters and taxpayers, are not about to fund fundamental research (such as mathematics) unless it is proved that countries where fundamental research gets funding (Russia, France) are better off than those where it gets almost none. Selfish calculations by the separate states lead them to scrap fundamental research needed by humanity as a whole (especially mathematics) as soon as military confrontation ends: no star wars, no supercollider, no mathematics. The return of contemporary mathematics to the mainstream of natural science, seen everywhere over the last
There is no scientific distinction between pure and applied mathematics, just a social one. few decades, has not yet been reflected in the conception of mathematics and mathematicians held by the "person in the street." This is true for both "pure" and "applied" mathematics. For that matter, there isn't a scientific distinction between pure and applied mathematics so much as a social one. The "pure" mathematician is paid to do mathematics, the "applied" mathematician to solve a particular problem. If a number-theorist were paid to solve the Fermat problem, then number theory would be an applied field--like the theory of Galois fields and curves over finite fields, where research is funded by the CIA, KGB, and similar agencies for purposes of cryptography. Columbus as he set sail was in the position of the applied mathematician: he was being paid to solve a specific problem, finding a passage to India. The discovery of the N e w World, however, was more analogous to pure mathematics. Coastwise navigation brought the Spanish economy much more short-term benefit than the unprofitable voyages of Columbus. Contemporary applications of mathematics, including "computer science" and applications of computers, draw on reserves of wealth accumulated by "pure" mathematics of previous generations. In contrast to geography, discoveries on the order of Columbus's are still possible-and happen yearly. Explaining these discoveries to the uninitiated is, to be sure, not easy. Behold the Princeton mathematician John Conway come to address this problem before an audience of three thousand in the Kongressenhaus of Zurich. He appears on the brightly lit dais in shorts, sandals, and windbreaker. "Nobody knows," he says, "how to fill our
ordinary three-dimensional space as densely as possible with identical spheres. It is supposed that the best w a y is to pack the balls in rows and layers, in the way I'll show you now." The lecturer pulls out of his windbreaker pocket something all crumpled like a handkerchief. This turns out to be a piece of some kind of plastic that quickly uncrumples and becomes a blue ball the size of a baby's head. "Let us put next to it a few more balls," says Conw a y and takes about ten more out of the same pocket. He lays them adjacent on the table so they form a lattice of equilateral triangles. "Now," says the lecturer, "let us put another layer on top" - - and fishes in another pocket of the windbreaker for red balls. When the third layer (of green balls, from a third pocket of the windbreaker) has been put in place, everyone clearly understands the layered packing of all of space. "Now I don't need this ball any more," says Conway, and takes a ball from the top of his pyramid and hurls it into the hall somewhere between the twentieth and the fortieth row. "I don't need these either," and he goes on throwing colored balls to all corners of the hall. When all the balls have been thrown (and caught with a happy shout by somebody in the audience), Conway remarks, "Now I don't need the windbreaker either," and takes it off and throws it on the floor. The shorts stay on throughout the lecture.
Speakers are trying to show w h a t great scientists they are more than to impart something to the audience. Eccentric as it was, Conway's was one of the most understandable talks in the Congress. The trouble is the progressive conversion of congresses into Reputation Fairs: speakers are trying to show what great scientists they are more than to impart something to the audience, and they think their purpose is served by incomprehensible lectures. (This is especially so in the section talks.) In my opinion, the best talks at the Congress were the one by Clifford Taubes (Harvard, USA) surveying the geometry of 4-dimensional manifolds (in connection with physics of gauge fields) and the one by J/irg Fr6hlich of Zurich about his recent theory of the Quantum Hall Effect. The topology of three or four dimensions has proved to be more complicated than either the topology of curves and surfaces or that of five or more dimensions. For example, only in 4 dimensioris are there "fake Euclidean spaces," topologically equivalent to ordinary space but not admitting a global smooth coordinate system. All these fake 4-spaces have, by the way, a nice description in terms of dynamical systems: they are the orbit spaces of certain smooth vector-fields (with no zeros) in the usual Euclidean 5-space. Yet, as far as I know, no
one has ever written such a vector-field explicitly. May its components be elementary functions? polynomials? Three interesting talks were devoted to the theory of mirror symmetry, a striking connection, recently discovered by physicists, between apparently unrelated mathematical theories, belonging to algebraic geometry, singularity theory, topology, and combinatorics of convex polyhedra. Many assertions of this theory remain so far only conjectures (corroborated by vast experimental data and by the equality of integers with a great many digits occurring in the different theories). Yet in the talks of M. Kontsevich ("Homological algebra of mirror symmetry"), of A. B. Givental' ("Homological geometry and mirror symmetry"), and of D. R. Morrison ("Mirror symmetry and moduli spaces of conformal field theories"), one could get a relatively harmonious view of a theory to come. In the talk by F611mer (Bonn) on financial mathematics, it was pleasant to hear about "Russian options," introduced by Shiryaev and She.pp. I had hitherto heard only of European and AmetXcan options. I was greatly impressed by the short description of the work of Nevanlinna Prize winner A. Wigderson, given at the opening session by Yu. Matijasevich (St. Petersburg). This is about new ideas in complexity of solution of mathematical problems and applications of probabilistic ideas to proof theory. Finally, we have the possibility in rigorous mathematics of finding proofs that are correct, not with certainty, but with an extremely small probability of error (say, 10-5~176 Everyone knows that some problems have solutions that are easy to verify but hard to find. An example is the decomposition of an integer into prime factors. If a factor is known, then one can verify the divisibility quite fast (even if the dividend has two hundred digits and the divisor one hundred). Yet finding a factor is very difficult: one has to just go through the possibilities, and the time required is enormous (growing exponentially with the number of digits of the given number). Problems of exponential complexity are out of reach of computers in practice, and will remain so however the technology may be perfected. This makes factorizations usable in schemes for transmitting secret information over public communication channels. However, it remains an unproved conjecture that these classes really are more than polynomially complex (though a list has been assembled of thousands of problems, each of which is known to be "hard" if any is). The new advance is the elaboration of a broad theory based on the still-unproved hypothesis of the existence of hard problems. Especially interesting is the study of randomized algorithms-- algorithms including random t e s t s - and of possible means of derandomizing t h e m - - t h a t is, replacing their stochastic elements by pseudorandom number generators. It is shown in particular that an arbitrarily complex proof can be made verifiable arbitrarily fast. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995 9
All this activity based on an unproved conjecture (with sometimes paradoxical consequences) reminds me of the work of Lobachevskii, who constructed a beautiful theory of his geometry, undeterred by having an unproved hypothesis at the foundation. Now we know that there are two geometries, one where Lobachevskii's hypothesis is satisfied and one where it is not. They simply describe the geometry of different surfaces.
American universities boast about w h a t famous Russian mathematicians they have rejected.
questions at the end. And when some old-fashioned professors, like J. Moser (Director of the Mathematical Institute of ETH Zurich, the principal mathematical center in Switzerland), did urge people to ask questions, very few listeners overcame fear of exposing their ignorance sufficiently to do so. The talks differed from sermons, however, in not being free. For those not registered as participants, the fee to attend a talk was considerable, as for a concert or a play. I take pleasure in reporting that representatives of the Russian school generally were on the more comprehensible side. It is part of our tradition that a survey talk should emphasize new ideas and illuminating examples and not technical details. I find rather worrisome the distinct shift in interests of our younger researchers (especially those working in the West) from directions long pursued by us to those fashionable in the USA. Such a shift of interests (doubtless related to the difficult conditions of job-hunting in American universities, some of which boast about what famous Russian mathematicians they have rejected) is inevitably negative. World leaders in one field leave it to race in a pack of jostling competitors following some other leader. Could this explain the distinct decrease in the proportion of our mathematicians among speakers at Congresses? It is a pleasure to note also the large number of young Congress participants, including graduate students, from Russia and other countries of the former Soviet Union. Their attendance was made possible by generous support from the Swiss Organizing Committee of the Congress and the Soros Foundation. Swiss mathematicians did everything possible to make our stay pleasant: participants were offered trips all over Switzerland (Lucerne, Interlaken, Bern, etc.), trips to the mountains (to Rigi Kulm overlooking the Vierwaldst/itter See), to the Rhine waterfall (comparable to Niagara), concerts of classical and folk music. I was impressed by the small and little-known B~irlet art gallery in Zurich--Rembrandt and Franz Hals, E1 Greco and Goya, Canaletto and Tiepolo, Greuze and Ingres, Corot and Courbet, C6zanne, van Gogh, Matisse, Pissarro, Picasso.
It seems doubtful that there can be a mathematics that contains exponentially hard problems (impossible to solve without combinatorial search) and another that does not. In any case, various aspects of deterministic, randomized, and derandomized algorithms provided many interesting lectures at Zurich (the section on computer science). Most talks at the Congress, however, were like sermons. The lecturers plainly didn't expect that listeners would understand anything. Sometimes they went so far as to state obviously false theorems to the respectfully silent auditorium. The sermon mood was so pervasive that most of the introducers didn't even ask for 10
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
After the tiring Congress, I spent a day at the home of my old friend A. Haefliger near Geneva. We climbed from 1500m to 3000m in the mountains near the Rhone valley, about halfway between the Jungfrau and the Matterhorn, and I got to swim in a glacial lake. On the return I picked mushrooms, sorrel, blueberries, and wild strawberries, and made my hosts a dinner from these gifts of nature (overcoming their doubts as to their edibility). The next day I returned to Moscow. Steklov Mathematical Institute ul. Vavilova 42 117966 Moscow GSP-1 Russia
A Nobel Prize for John Nash John Milnor
John E Nash created an impressive array of exciting mathematics during the 10 years of his mathematical activity. To some, the brief p a p e r written at age 21, for which he has w o n a Nobel prize I in economics, m a y seem like the least of his achievements. Nevertheless, I applaud the w i s d o m of the selection committee in m a k i n g this award. It is notoriously difficult to apply precise mathematical methods in the social sciences, yet the ideas in Nash's thesis are simple and rigorous, and provide a firm background, not only for economic theory but also for research in evolutionary biology, and more generally for the study of any situation in which h u m a n or nonhum a n beings face competition or conflict. According to P. Ordeshook [O], p. 118,
Game Theory In the f r a m e w o r k set d o w n by v o n N e u m a n n and Morgenstern [NM], an n-person game can be described as follows. There are n agents or players, n u m b e r e d from 1 to n. For each i between I and n, the ith player has a set Si of possible strategies, and chooses some element si E S~, where these choices are to be m a d e simultaneously. The outcome of the game is then a function of the n choices Sl . . . . . sn. The ith player also has a preference ordering for the set of possible outcomes. This is conveniently described b y a real-valued function Pi: $1 x . . . x S , , --0 R ,
The concept of a Nash equilibrium n-tuple is perhaps the most important idea in noncooperative game theory9 9 we are analyzing candidates' election strategies, the causes of war, agenda manipulation in legislatures, or the actions of interest groups, predictions about events reduce to a search for and description of equilibria. Put simply, equilibrium strategies are the things that we predict about people9 The first section of this article will describe this prize work. After a short digression, the third section will outline some of the w o r k for which Nash is famous a m o n g mathematicians, and the last will briefly describe events since 1958. 1 C o m p a r e [P]. This is the third Nobel prize to be a w a r d e d to a Princeton mathematics graduate. The first two were physics prizes, both to John Bardeen. THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3 @1995Springer-VerlagNew York 11
simple and objective, such as money, but rather are supposed to incorporate every relevant motivation which the players may have, whether selfish, altruistic, or whatever. Although von Neumann and Morgenstern developed a beautiful theory of two-person games which are zerosum, in the sense that pl q- p2 = 0, their theory for the more general case was complicated and unconvincing. Nash's theory, on the other hand, is direct and elegant:
Definition. An n-tuple of strategies ( s l , . . . , s,~) constitutes an equilibrium point for the game if no player can increase his payoffpi(sl,..., sn) by changing only si while the other sj remain fixed. It is not claimed that an equilibrium point is a particularly desirable outcome for a game. Indeed, it may well be disastrous for all parties. (As an example, it is not difficult to describe a game of "atomic warfare" with only one equilibrium point, which requires each player to annihilate the others.) Rather, we must think of an equilibrium point as a description of what is likely to happen in a completely noncooperative situation, in which the players pursue their individual goals without any cooperation, either because they cannot communicate or because they have no mechanism or no will for cooperation. This contrasts with the von Neumann-Morgenstern work, which considered only cooperative games. I am indebted to Hector Sussmann for two examples which show that equilibrium points are relevant even in everyday life:
Example 1. At a boring party, all of the guests want to go home early, but no one is willing to leave before midnight unless someone else leaves first. There is just one equilibrium point: everyone stays until midnight. (Compare [Sch].) called his payoff function. Each player's objective is to make his own choice s~ in such a way as to maximize his payoff pi(sl .... ,8n), with the understanding that for each J # i, the j t h player is simultaneously choosing sj, trying to maximize the value of his own payoff pj. In interpreting this mathematical model, the various "players" can be individual persons. However, there are many other possibilities: The players can be nations, corporations, armies, teams, human-programmed computers, or animals. For the study of evolution, one considers competition between species or between genes. (Compare [MSP], [MS], and [D].) In the case of a game which extends over time, the "strategies" chosen by the players should be thought of, not as individual choices, but rather as comprehensive prescriptions of what to do in every conceivable situation which may arise during the course of the game. For example, a strategy for the game of chess might consist of a computer program which selects a move for every possible chess position. The "payoff" functions are usually not measured in something 12
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3,1995
Example 2. A group of 20 is going to dinner, and each one has the choice of an adequate meal for 10 dollars or an excellent meal for 20 dollars. If paying individually, each one would choose the cheaper meal. However, they have decided to split the bill. Since the marginal cost of the more expensive meal for each person is only 50 cents, everyone chooses it. Before stating Nash's basic existence theorem, we must introduce probabilities, via the von N e u m a n n Morgenstern theory of mixed strategies. To see why this is necessary, consider the following.
Example 3. A simple combination lock has 1000 possible combinations; the owner is free to choose any one of them. A would-be thief will have just one chance to guess the combination. Thus, we could take $1 and $2 to be finite sets, with 1000 elements each. However, with this mathematical model, no equilibrium point would exist.
What we must rather do, in order to obtain a reasonable theory, is to allow randomization in making choices. In fact, we take $1 and $2 to be 999-dimensional simplexes, with 1000 vertices each. A point of the simplex $1 or of $2 is to be construed as a_probability distribution over the 1000 possible combinations. N o w there is a unique equilibrium point (81, s2), where each si is the probability distribution which assigns each choice of combination the probability 1 /1000. The thief then has just I chance in 1000 of making the correct guess. (This is an example of a two-person zero-sum game, so a Nash equilibrium point in this case is the same thing as a pair of optimal strategies in the sense of von N e u m a n n and Morgenstern.) Following von N e u m a n n and Morgenstern, such a weighted average of finitely m a n y pure strategies, where the weighting coefficients are interpreted as probabilities, is called a mixed strategy. The set of all mixed strategies for a given player forms a finite-dimensional simplex. EXISTENCE THEOREM. If the space of strategies Si for each player is a finite-dimensional simplex, and if each payoff function Pi(Sl, . . . , sn) is continuous as a function of n variables, and is linear as a function of si when the other variables are kept fixed, then at least one equilibrium point exists. To prove this statement, we embed each Si in a Euclidean space R a' of the same dimension, and consider the Cartesian product K = Sl x ... x Sn C R d1 x . . . x R
an.
We can then construct a continuous vector field .... ,vn) 9
d'x'''xR
(,)
as follows: The component vi in the R a' direction is to be the gradient vector cgpi/Osi for the function p~ when considered as a linear function of si, with sj kept fixed for every j # i. We will need the following:
Applying this lemma to the vector field (,), we obtain an n-tuple ~ = (~1 . . . . , ~n), which is the required equilibrium point. [] Commentary. As with a n y theory which constructs a mathematical model for some real-life problem, we must ask h o w realistic the model is. Does it help us to understand the real world? Does it make predictions which can be tested? In the case of Nash's equilibrium-point theory, we might first ask whether this is intended as a descriptive theory which tells us h o w people actually act in a competitive situation, or a normative theory which tells us h o w rational people ought to act in order to achieve the best possible outcome. The answer is probably both, and neither. In fact, the two aspects can never really be separated, since a descriptive theory of h o w the other players are making their choices m a y be crucial for making one's o w n choice. First let us ask about the realism of the underlying model. The hypothesis'/s that all of the pla);ers are rational, that they understand the precise rules of the game, and that they have complete information "about the objectives of all of the other players. Clearly, this is seldom completely true. One point which should particularly be noticed is the linearity hypothesis in Nash's theorem. This is a direct application of the von N e u m a n n - Morgenstern theory of numerical utility: the claim that it is possible to measure the relative desirability of different possible outcomes by a real-valued function which is linear with respect to probabilities. In other words, if the strategy s yields a 50% chance of an outcome with utility a and a 50% chance of an outcome with utility b, whereas the strategy s ~ yields a 100% chance of an outcome with utility (a + b)/2, then the player should be indifferent between s and sq This concept has been studied by m a n y authors.
LEMMA. If K C R a is a compact, convex set, and v: K --* R d is any continuous function, then there exists at least one point ~ E K where the vector field v either vanishes, or points out of K in the sense that every point of K lies in the half-space (s C Rd: s-v(~) _< ~- v(~)}. Proof Outline. (See Figure 1.) Let p : R a ~ K be the canonical retraction, which carries every point of R a to the closest point of K. Then the composition s ~-* p(s + v(s)) maps K into itself and hence, by the Brouwer Fixed Point Theorem, has a fixed point =
+
It is easy to check that v(~) either vanishes or points out of K.
Figure 1. Examples of vectors pointing "out" at a boundary point of a compact convex set. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
13
(See for example [HM].) M y own belief is that this is quite reasonable as a normative theory, but that it m a y not be realistic as a descriptive theory. Under what conditions does equilibrium-point theo r y really apply? A g a m e may have m a n y equilibrium points, some better than others for one player or even for all of the players. If the game is played only once, with no communication at all between the players, h o w will they know which of these equilibrium points is relevant? If the players do communicate, at what point does it cease being a "noncooperative" game? Another c o m m o n scenario would be a game which is played over a n d over again, perhaps gradually settling toward some equilibrium. In this case, there is the a d d e d complication that the players' utility functions m a y not remain the same for each play. Evidently, Nash's t h e o r y was not a finished answer to the problem of u n d e r s t a n d i n g competitive situations. Rather, it was a starting point, which has led to m u c h further study d u r i n g the intervening years. In fact it should be emphasized that no simple mathematical theory can provide a complete answer, since the p s y c h o l o g y of the players and the m e c h a n i s m of their interaction m a y be crucial to a more precise understanding. Games
Nash entered Princeton as a graduate student in 1948, the same year that I entered as a freshman. I quickly got to k n o w him, since we both spent a great deal of time in the c o m m o n room. H e was always full of mathematical
ideas, not only on game theory, but in geometry 2 and topology as well. However, m y most vivid m e m o r y of this time is of the m a n y games which were played in the c o m m o n room. I was introduced to Go and Kriegspiel, and also to an ingenious topological game which we called Nash, in honor of the inventor. In fact it was later discovered that the same game had been invented a few years earlier b y Piet Hein in Denmark. Hein called it Hex, and it is n o w c o m m o n l y k n o w n by that name. An n x n Nash or Hex board consists of a rhombus which is tiled by n 2 hexagons, as illustrated in Figure 2. (The reco m m e n d e d size for an enjoyable g a m e is 14 x 14. H o w ever, a m u c h smaller board is s h o w n here for illustrative purposes.) Two opposite edges are colored black, and the remaining two are colored white. The players alternately place pieces on the hexagons, and once played, a piece is n e v e r moved. The black player tries to construct a connected chain of black pieces joining the two black boundaries, while the white player tries to form a connected chain of white pieces joining the white boundaries. The g a m e continues until one player or the other succeeds.
2 Here is one question asked by Nash. Let ~B be a singular algebraic variety of dimension k, embedded in some smooth variety Mo, and let/~,I1 = Gk(MO) be the Grassmann variety of tangent k-planes to Mo. Then Volifts naturally to a k-dimensional variety ~r C M1. Continuing inductively, we obtain a sequence of k-dimensional varieties t~ ~ V1 ~-- V2 . . . . . Do we eventually reach a variety ~ which is nonsingular? Even today, this has been proved only in special cases. (Compare [G-S], [H], and [Sp].)
Figure 2. A typical situation in the game of Hex. Problem: Black to move and win. Alternate Problem: White to move and win. (Solution on page 56.) 14
T"E MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
Figure 3. On an asymmetric board, as shown, white can win even if black moves first. The winning strategy can be explicitly described by "doubles": Whatever move black makes, white responds by playing in the hexagon which is marked with the corresponding symbol, where the correspondence (for example, a ~ A) is a glide reflection which flips the left half of the board onto the fight half.
THEOREM. On an n x n Hex board, the first player can always win. Nash's proof is marvelously nonconstructive and can be outlined as follows. First Step. A purely topological argument shows that, in any play of the game, one player or the other must win: If the board is covered by black and white pieces, then there exists either a black chain from black to black or a white chain from white to white, but never both. Second Step. Since this game is finite, with only two possible outcomes, and since the players move alternately with complete information, a theorem of Zermelo, rediscovered by yon Neumann and Morgenstern, asserts that one of the two players must have a winning strategy. Third Step, by symmetry. If the second player had a winning strategy, the first player could just make an initial move at random, and then follow the strategy for the second player. Since his initial play can never hurt him, he must win. Thus, the hypothesis that the second player has a winning strategy leads to a contradiction. (This is a well-known arguhlent which applies to some other symmetric games, such as Five-in-a-Row.) []
Note that this proof depends strongly on the symmetry of the board. On an n x (n + 1) board, the player with the shorter distance to' connect can always win, even if the other player has the first move. (Compare Fig. 3.)
Geometry and Analysis
After receiving his doctorate, Nash moved to M.I.T., where he produced a remarkable series of papers. The first was a basic contribution to the theory of real algebraic varieties. THEOREM. Given any smooth compact k-dimensional manifold M, there exists a real algebraic variety V c R 2k+1 and a connected component Vo of V so that Vo is a smooth manifold diffeomorphic to M. He complemented this theorem by giving an abstract characterization of such manifolds V0by means of a suitable algebra of real-valued functions. As one example of the power of this result, let me describe an important application. A basic problem in dynamics is to understand how the number of periodic points of period p for a smooth map can increase as a function of p. THEOREM OF ARTIN AND MAZUR. Any smooth map from a compact manifold to itself can be approximated by a smooth map such that the number of periodic points of period p grows at most exponentially with p. The only known proof of this result makes essential use of Nash's work, in order to translate the dynamic THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995 1 5
problem into an algebraic one of counting solutions to polynomial equations. Two years later, he attacked one of the fundamental unsolved problems in Riemannian geometry, namely, the Isometric Embedding Problem for Riemannian manifolds. In other words, he considered the system of differential equations Ox Ox OUi OUj "~ gij(Ul,''',Uk), where the u~ are local coordinates for some given k-dimensional Riemannian manifold, where g i j ( u l , . . . , uk) is the prescribed Riemannian metric, and where X(Um,..., Uk) is the unknown isometric embedding into Euclidean n-space. This is a system of k(k + 1)/2 nonlinear differential equations in n unknown functions, to be solved globally, over the entire manifold. He first tackled the C 1-case. Every student of differential geometry knows that a compact surface without boundary in Euclidean 3-space must have points of positive curvature. (Proof: Enclose the surface in a spherical balloon, and then move the balloon until it first touches the surface. Then both principal curvatures at the point of contact must be nonzero, with the same sign. Hence, the Gaussian curvature at this point is strictly positive.) As an example, it follows that a flat torus S 1 x S 2 C R 2 x R2 has no smooth isometric embedding into 3-space. Nash ignored such difficulties. Incorporating a later improvement by Kuiper [K], we can state his result as follows. THEOREM. If a compact Riemannian manifold (M, g) can be smoothly embedded in the Euclidean space R n, then it can be C 1-isometrically embedded in R n.
Here is a very rough outline of the proof. Start with any smooth embedding and shrink it uniformly until all distances in the induced metric are shorter than distances in the given metric g. Next introduce small sinusoidal ripples in the embedded manifold so as to increase the Euclidean lengths of curves in one coordinate patch after another. Now repeat this process, keeping careful control of first derivatives at every stage, so that the Riemannian metric induced from the embedding will increase monotonically toward the required metric g. The catch in this construction is that there is no way of keeping control of second derivatives. Thus, the embedding which is constructed will never be C2-smooth. Since the concept of curvature involves second derivatives in an essential way, any argument involving principal curvatures simply will not apply to the resulting embedding. Next he attacked the much more serious C rembedding problem, for r > 1. 16
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
THEOREM. If n > k(k + 1)(3k + 11)/2, then every k-dimensional Riemannian manifold of class C ~ can be C ~isometrically embedded into R n, for 3 < r < oo. To prove this result, he introduced an entirely new method into nonlinear analysis. As later generalized by Moser, this method can be roughly described as follows. We are trying to solve some system of equations in an infinite-dimensional space of functions f. Given an approximate solution f0, we can apply some linear approximation procedure analogous to Newton's method, to produce a better approximation g0. The difficulty is that this linear procedure typically involves differentiation, so that g0 is less differentiable than f0. The trick is then to apply a smoothing operator, approximating 90 by a function fl which has better smoothness properties. We can then continue inductively, constructing a sequence of approximations fo, f l , f 2 , . . 9 with extremely careful estimates at every stage. With appropriate hypotheses, these will converge to the required solution. (For further development of these ideas, see [Gr] and [Gii].) At this time he began a deep study of parabolic and elliptic differential equations, proving basic local existence, uniqueness, and continuity theorems (and also speculating about relations with statistical mechanics, singularities, and turbulence). This work has been somewhat neglected. In fact, a 1957 paper by De Giorgi [DG] has tended to dominate the field. The methods were quite different, but both authors were strikingly original, and made real breakthroughs. De Giorgi considered only the elliptic case, whereas Nash rather assigned a primary role to parabolic equations. His methods, based on a moment inequality for the fundamental solution, are quite powerful. (Compare [FS].) Here are some quotations (abridged and mildly edited) from his paper on "continuity of solutions"(Nash [12]), which help to describe his vision and goals in 1958. The open problems in the area of non-linear partial differential equations are very relevant to applied mathematics and science as a whole, perhaps more so than the open problems in any other area of mathematics, and this field seems poised for rapid development. Little is known about the existence, uniqueness and smoothness of solutions of the general equations of flow for a viscous, compressible, and heat conducting fluid. Also, the relationship between this continuum description of a fluid and the more physically valid statistical mechanical description is not well understood. Probably one should first try to prove existence, smoothness, and unique continuation (in time) of flows, conditional on the non-appearance of certain gross types of singularity, such as infinities of temperature or density. A result of this kind would clarify the turbulence problem. Successful treatment of non-linear partial differential equations generally depends on 'a priori' estimates, which are themselves theorems about linear equations . . . . The methods used here were inspired by physical intuition, of diffusion, Brownian movement, and flow of heat or electrical charges, but the ritual of mathematical exposition tends to hide this natural basis.
Epilogue In 1958, at the age of 30, Nash suffered a devastating attack of mental illness. (Compare [N].) There followed m a n y horrible years: periods of confinement to mental hospitals, usually involuntary and often accompanied b y shock treatments, interspersed with periods of partial recovery. During a brief respite in 1966, he published one further paper, showing that his isometric e m b e d d i n g theorem, and more generally the N a s h - M o s e r implicit function machinery, can be extended to the real-analytic case. There followed an extremely long fallow period. I lost touch with him d u r i n g this time; however, I was v e r y h a p p y to hear that in recent years his illness has abated, and that he has regained interest in major unsolved problems. This year, Nash not only attended the award ceremonies in Stockholm but also gave a seminar in Uppsala on his recent w o r k in mathematical physics. I conclude by congratulating John Nash, not just for his prize, but for his m a n y contributions to h u m a n knowledge, and offer him all best wishes for the future.
[M] J. Moser, A new technique for the construction of solutions of nonlinear differential equations, Proc. Nat. Acad. Sci. USA 47 (1961) 1824-1831. [MS] J. Maynard Smith, Did Darwin Get It Right?, Chapman and Hall, New York (1989). [MSP] J. Maynard Smith and G. R. Price. The logic of animal conflict,3 Nature 246 (1973), 15-18. IN] S. Nasar, The lost years of a Nobel laureate, New York Times Business Section, 13 November 1994, 1 and 8. [NM] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton, NJ: Princeton University Press (1944). [O] P. Ordeshook, Game Theory and Political Theory: An Introduction, Cambridge UK: Cambridge University Press, (1986). [P] R. Pool, Economics: Game theory's winning hands, Science 266 (Oct. 21, 1994), 371. [Sch] J. Schwartz, Lectures on the Mathematical Method in Analytical Economics, New York: Gordon and Breach (1961). [Sp] M. Spivakovsky, Sandwiched surface singularities and desingularization of surfaces by normalized Nash transformations, Ann. Math. 131 (1990), 411-491.
Published Papers of John F. Nash Acknowledgments I want to thank D. Gale, I. Kra, H. Kuhn, J. Moser, M. Spivakovsky, and H. Sussmann for their help.
References [AM] M. Artin and B. Mazur, On periodic points, Ann. Math. 81 (1965), 82-99. [D] R. Dawkins, The Selfish Gene, Oxford: Oxford Univeristy Press (1976). [DG] E. De Giorgi, Sulla differenziabilit~t e l'analiticit~ delle estremali degli integrali multipli regolari, Mem. Accad. Sci. Torino CI. Sci. Fis. Mat. Nat. (3) 3 (1957), 25-43. [FS] E. B. Fabes and D. W. Stroock, A new proof of Moser's parabolic Harnack inequality using the old ideas of Nash, Arch. Rat. Mech. Anal. 96 (1986), 327-338. [G-S] G. Gonzalez-Sprinberg, R6solution de Nash des points double rationnells, Ann. Inst. Fourier, Grenoble 32(2) (1982), 111-178. See also: D6singularisation des surfaces par des modifications de Nash normalis6es, Sdm. Bourbaki 1985/86, Astdrisque 145-146 (1987), 4 and 187-207. [Gr] M. Gromov, Partial Differential Relations, New York: Springer-Verlag (1986). [G/i] M. Giinther, Isometric embeddings of Riemannian manifolds, Proc. Int. Cong. Math.'Kyoto, II, Mathematical Society of Japan, Springer (1991), 1137-1143. [H] H. Hironaka, On Nash blowing-up, Arithmetic and Geometry II, Boston: Birh/iuser (1983), 103-111. [HM] I. N. Herstein and J. Milnor, An axiomatic approach to measurable utility, Econometrica 21 (1953), 291 -297. [K] N. Kuiper, On Ct-isometric imbeddings, I, II, Indag. Math. 17 (1955), 545-556, 683-689.
1. Equilibrium points in n-person games, Proc. Nat. Acad. Sci. USA 36 (1950), 48-49. 2. The bargaining problem, Econometrica 18 (1950) 155-162. (Written as an undergraduate at Carnegie Tech.) 3. Non-cooperative games, Ann. Math. 54 (1951) 286-295. 4. Real algebraic manifolds, Ann. Math. 56 (1952) 405-421. 5. Two-person cooperative games, Econometrica 21 (1953) 128-140. 6. Some experimental n-person games (with C. Kalisch, J. Milnor and E. Nering), Decision Processes (R. M. Thrall, C. H. Coombs, and R. L. Davis, eds.), New York: Wiley (1954). 7. CCisometric imbeddings, Ann. Math. 60 (1954), 383-396. [See also Bull. Amer. Math. Soc. 60 (1954), 157.] 8. Results on continuation and uniqueness of fluid flow, Bull. Am. Math. Soc. 60 (1954), 165-166. 9. A path space and the Stiefel-Whitney classes, Proc. Nat. Acad. Sci. USA 41 (1955), 320-321. 10. The imbedding problem for Riemannian manifolds, Ann. Math. 63 (1956), 20-63. [See also Bull. Am. Math. Soc. 60 (1954), 480.] 11. Parabolic equations, Proc. Nat. Acad. Sci. USA 43 (1957), 754- 758. 12. Continuity of solutions of parabolic and elliptic equations. Am. J. Math. 80 (1958), 931-954. 13. Le probl6me de Cauchy pour les 6quations diff6rentielles d'un fluide g6n6ral, Bull. Soc. Math. France 90 (1962), 487497. 14. Analyticity of the solutions of implicit function problems with analytic data, Ann. Math. 84 (1966), 345-355. Institute for Mathematical Sciences State University of New York at Stony Brook Stony Brook, N Y 11794-3660, USA
3 Note that an evolutionarily stable strategy in the sense of Maynard Smith and Price is nearly the same thing as a Nash equilibrium point. THE MATHEMATICALINTELLIGENCERVOL.17, NO. 3,1995 17
A Candidate for the "Next Fermat Problem" Gary L. Mullen
Keith Devlin's editorial [12] discussed various candidates for the Next Fermat Problem. a He raised some very interesting problems including the Goldbach, twin prime, and Mersenne prime conjectures, the "hailstone" N / 2 and 3N + 1 problem, and the rectangular brick problem (his favorite). My o w n proposal for the Next Fermat Problem goes back to Euler. In 1782 Leonhard Euler conjectured [14] that if n = 2(2k + 1), that is, if r~ is an odd multiple of 2, then there does not exist a pair of mutually orthogonal latin squares (MOLS) of order n. In 1899-1900 this was s h o w n to be true by Tarry for n = 6 [10, pp. 140, 537], but in 1959-1960 Euler's conjecture was s h o w n to be false for all larger odd multiples of 2 [4, 5]. From [10], p. 138, or Euler's Collected Works [15], it is known that Euler presented latin-square results to the Academy of Sciences of St. Petersburg on March 8, 1779. In particular, he correctly enumerated the reduced latin squares (first row and column in natural order) of order n G 5 and discussed squares of order 6. Considering Euler's great imagination and tremendous calculational ability, it is not inconceivable that, while he was making w h a t has become k n o w n as the Euler conjecture above, perhaps he was already thinking along the lines of the
Latin Squares Recall that by a latin square of order n is meant an u x u square in which each row and each column consists of n distinct elements, often taken to be {0, 1 . . . . , n - 1}. Thus, examples of orders 2 and 3 are
NEXT PROBLEM. There exist n - 1 M O L S of order n if and only if n is a prime power.
1 In the December 1994 issue of Focus, Devlin reports on the current status of Fermat's Last T h e o r e m in a note entitled " G r o w i n g o p t i m i s m that Fermat's Last T h e o r e m has been solved at last." 18
THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3 (~)1995Springer-VerlagNew York
0 0
1
1
0
1
2
1 2
0
2
1
0
Two squares of the same order, say n, are orthogonal if w h e n superimposed, each of the n 2 possible ordered pairs occurs exactly once. In addition, a set L1,. 99 Ls of s _> 2 latin squares of the same order is orthogonal if a n y two distinct squares,are orthogonal, that is, if L~ is orthogonal to L ; w h e n e v e r i ~ j. Thus, for order 3, the squares 0
1
2
0
1
2
1
2
0
2
0
1
2
0
1
1
2
0
are orthogonal, for u p o n superimposing the two squares w e have 00
11
22
12
20
01
21
02
10
Let me n o w provide some speculation on Euler's thinking. H e certainly was able to construct a pair of MOLS of order 3. He probably also did or felt at least that he could build three MOLS of order 4 and perhaps four MOLS of order 5. After all, there are only 4!3!4 latin squares of order 4, and as indicated earlier, Euler correctly e n u m e r a t e d the reduced latin squares of order 5, of which there are 56. For n = 6, he of course could not find even a pair of MOLS. For 7 < n < 9 Euler probably was able to construct some MOLS of order n. For the case of n = 10, he also could not find a pair of MOLS, and so because of the cases of n = 6 and n = 10, he was led to "Euler's Conjecture." I a m saying that from his vantage it would have been natural to conjecture also what I am calling the "Next Problem." As Devlin suggests in [12], if a problem is to become the Next Fermat Problem, it "would have to be simple to state, easy for the layperson to understand, likely to defy attempts at a solution for m a n y years, and require some h e a v y mathematical machinery w h e n that solution does finally come." Does the above problem meet these conditions? It is certainly easy to state and understand: after all, latin and magic squares have been used for a m u s e m e n t for generations. Whereas Fermat's Last Theorem remained open for more than 350 years, the Next Problem had its beginnings in the work of Euler more than 210 years ago. Finally, this problem has resisted all attempts at solution, including those using techniques from n u m b e r theory, g r o u p theory, combinatorics, algebraic coding theory, and, more recently, computational approaches. The following a r g u m e n t can also be m a d e concerning applications. In the case of Fermat's Conjecture, there are few if any applications of the solution to the problem. The important point here is that n u m e r o u s areas of mathematics were d e v e l o p e d in attempts to resolve the conjecture.
In the case of the Next Problem, there are indeed applications of the solution, regardless of whether the conjecture is f o u n d to be true or false. Since Bose [3] s h o w e d the equivalence between the existence of a complete set of n - 1 MOLS of order n and the existence of a projective (and hence affine) plane of order n, we quickly see that if the Next Problem is f o u n d to be true, then we will k n o w that all such planes have prime p o w e r orders. Also as a consequence, there will not exist various other kinds of designs such as affine resolvable designs with certain parameters. More importantly, there will be various algebraic methods and constructions available for use in proving results about any such plane or design. Such algebraic methods include the use of finite fields and other finite algebraic systems such as quasi-fields which are k n o w n to exist only in p r i m e - p o w e r cases. On the other hand, if a counterexample is found to the Next Problem, then one could use it to build totally new combinatorial objects such as complete sets of hypercubes, affine designs, and .orthogonal frequency squares. These objects in non-prime-power cases w o u l d be totally different from existing ones and w o u l d thus provide an entirely new area of future research. It m a y be helpful to point out that sets of MOLS are well k n o w n to be equivalent to the construction of various other combinatorial objects. These objects include orthogonal arrays of strength 2 and index 1, transversal designs of index 1, and nets; see for example [1], [10], and [27]. I n o w give a brief historical s u r v e y of the Next Problem, with a n u m b e r of related conjectures and open problems. To help simplify the statements of some of these results, let N ( n ) denote the m a x i m u m n u m b e r of MOLS of order n, so that (as the reader should check) N ( n ) <_ n - 1 for all n _> 2. Thus Euler's original c o n j e c t u r e w a s that if n was an o d d multiple of 2, then N ( n ) = 1; our Next Problem is the conjecture that N ( n ) = n - 1 if and only if n is a prime power. In 1899-1900, Tarry s h o w e d that N(6) = 1. This was no small accomplishment, for, as Tarry also showed, the n u m b e r of distinct latin squares of order 6 is equal to 6!5!9408; see [10], p. 140; and [1]-[5] on p. 537 of [10]. For short proofs that N(6) = 1, see [13] and [26]. Tarry's result gave some plausibility to Euler's conjecture, and in 1922 MacNeish [20] p r o v e d that N ( n ) ~ ql - - 1 , where ql is the smallest prime p o w e r in the factorization of n. I n o w state w h a t has become k n o w n as the M A C N E I S H CONJECTURE. Suppose that n
= ql x 9 .. x qr is the canonical factorization of n into prime powers w i t h ql < "'" < qr. Then N ( n ) = ql - 1.
MacNeish's conjecture was s h o w n to be false in 1959 w h e n Parker [23] found that N(21) _> 4. Euler's conjecture was, later in 1959, also s h o w n to be false w h e n Bose and Shrikhande [4] s h o w e d that N(22) _> 2. Parker [24] then s h o w e d in 1960 that N(10) >_ 2. Then in 1960, Bose, THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3,1995
19
et al. [5] joined forces in a major step forward b y showing that N(n) _> 2 for all n ~ 2 or 6 - - d e s p i t e the weight of Euler's conjecture and Tarry's result. What about the MacNeish conjecture? Will it suffer the same fate as that of the Euler conjecture and turn out to be false for all the open values? This is still u n k n o w n [18]. CONJECTURE. The MacNeish conjecture is false for all n except 6 and prime powers. As evidence for this, for n _< 200, the MacNeish conjecture holds for n a p r i m e power and for n = 6; is open for 12 values of n (35, 45, 63, 77, 99, 117, 119, 143, 153, 171, 175, 187), and is false otherwise; see [7]. Progress has been very slow, often only a single case of the conjecture is disproved. A major result w o u l d be
PROBLEM 1. Find a general method that would disprove the MacNeish conjecture for an infinite number of n, as did the method of Bose, et al. [5] for the Euler conjecture. Even better, solve PROBLEM 2. Generalize the method of Bose, et al. to show that the MacNeish conjecture is false for all n except 6 and prime powers. What is k n o w n t o d a y toward the proof of the Next Problem? Bose [3] is usually given credit for the construction in 1938 of a complete set of MOLS of order q a prime power. Actually, Bose was preceded in 1896 by Moore [21], w h o in different notation but with the same method, used the linear equations ax + y with a ~ 0 E Fq, the finite field of order q, to construct a (complete) set of q - 1 MOLS of order q. Kirkman had established the existence of projective planes of prime p o w e r order a r o u n d 1850 (see [2]); and Bose [3] showed the equivalence of a set of n - 1 MOLS of order n and a projective plane of order n. In [8] Bruck and Ryser s h o w e d that for infinitely m a n y n there do not exist n - 1 MOLS of order n. In particular, they proved that if n = 1,2 (mod 4) and if the squarefree part of n contains at least one prime factor of the f o r m 4k + 3, then N ( n ) < n - 1. Thus N ( n ) < n - 1 for n = 6, 14, 21, 22, 30, . . . . This result was p r o v e d through the use of n u m e r o u s number-theoretic techniques, including Lagrange's theorem to the effect that e v e r y positive integer can be represented as the sum of at most four integral squares. See [10], p. 170 for a discussion. See also [9] for a closely related result. The B r u c k - R y s e r - C h o w l a theorem actually proves more than N ( n ) < n - 1. Building on the w o r k of n u m e r o u s researchers w h o studied the binary error-correcting code generated b y the rows of the incidence matrix of an assumed-to-exist projective plane of order 10, Lam, et al. [17] recently s h o w e d through the use of some 2000 hours of C r a y - l A CPU 20
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
time that N(10) < 9. Thus the Next Problem is true at n = 10. In addition, from Shrikhande [25] or [10], p. 330, we k n o w that 2 _< N(10) _< 6. What is N(10)? Although computers m a y be helpful for specific cases as they were in the n = 10 case, they are not likely to be useful for the general solution of the Next Problem. If the Next Problem is indeed s h o w n to be true, then we m a y turn to the even more difficult PROBLEM 3. Find a formula for N ( n ) for each n. The only known cases are N(6) = 1 and N(q) = q - 1 for q a prime power. I n o w point out some important w o r k related to the asymptotic n u m b e r of MOLS. The following is sometimes referred to as Wilson's Problem: Is there an absolute constant c so that N ( n ) >_ n / c for all or for all but finitely m a n y values of n? See for example the w o r k of van Lint and Wilson [19], w h o indicate that "at the present time this appears to be incredibly hard to prove." In [28] Wilson showed using transversal designs that for sufficiently large n, N ( n ) >_ n 1 / 1 7 - - 2. As indicated in [6], p. 167, this result has been i m p r o v e d by various authors so that n o w for sufficiently large n, it is k n o w n that N ( n ) >_ n 10/143 - - 2.
Hypercubes In this section I consider several generalizations of the above ideas to hypercubes of dimension d _> 2. Natural higher-dimensional Euler and MacNeish conjectures remain false, but for d > 2, one extension of the Next Problem is indeed true. For d _> 2, a d-dimensional h y p e r c u b e of order n is an n x --. x n array with n d points based on n distinct symbols, with the property that w h e n e v e r any one of the coordinates is fixed, each of the n symbols appears n d-2 times in that subarray. Two hypercubes are orthogonal if, w h e n superimposed, each of the n 2 ordered pairs appears n d-2 times, and a set of s _> 2 hypercubes is orthogonal if e v e r y pair of distinct hypercubes is orthogonal. M a n y h y p e r c u b e results and problems could be stated in terms of other combinatorial objects such as orthogonal arrays and transversal designs, but as in the case d = 2 of latin squares, I will not go into these details. In addition to their use in statistical and combinatorial design theory, hypercubes are useful in the construction of point sets with strong uniformity properties for simulation and numerical integration problems; see for example [22]. It is k n o w n [10, p. 189] that the m a x i m u m n u m b e r Na (n) of m u t u a l l y orthogonal hypercubes of order n and dimension d is b o u n d e d by n d -- 1 Nd(n) < - d. (1) - n-1 When d = 2, these ideas reduce to the usual notions for MOLS.
By w a y of illustration, here is a c o m p l e t e set of 10 m u t u a l l y orthogonal h y p e r c u b e s of order 3 a n d dimension 3. 123 231 312
123 312 231
123 123 123
123 123 123
111 222 333
111 222 333
123 231 312
123 312 231
123 312 231
123 231 312
123 231 312
123 312 231
231 231 231
312 312 312
222 333 111
333 111 222
231 312 123
312 231 123
231 123 312
312 123 231
As a generalization of Problem 3, I raise P R O B L E M 5 . Ford >_2 find a formula for Nd(n ) for each n. P R O B L E M 6. Is it true for each n and d >_ 2 that
Nd(n) = (N(n) + 1) d - 1 _ d? g(n)
(4)
Clearly, Eq. (4) holds for n a p r i m e power. Is it true in general? If true, Eq. (4) w o u l d indicate that the m a x i m u m n u m b e r of h y p e r c u b e s of d i m e n s i o n d _> 2 and o r d e r n 123 123 312 231 333 222 312 231 312 231 is obtained b y substituting N(n), the m a x i m u m n u m b e r 231 312 312 231 111 333 123 123 231 312 of MOLS of order n, into Eq. (3). 312 231 312 231 222 111 231 312 123 123 In [16] H 6 h l e r studied a very interesting modified version of orthogonality for h y p e r c u b e s of d i m e n s i o n d _> 2. Using a M a c N e i s h - t y p e p r o d u c t construction [10, His definition reduces to the usual notion for d i m e n s i o n p. 390] it is easy to see that if ql " " q r is the canonical d = 2, but for d > 2, his definition places strong exfactorization of n into p r i m e p o w e r s with ql < 9 9 < qr, tra conditions on h o w the ordered pairs are distributed then w h e n two orthogonal h y p e r c u b e s are s u p e r i m p o s e d . In qd _ 1 d <_ Nd(n). (2) addition to requiring e~ch ordered pair to a p p e a r exactly ql -- 1 n d-2 times, he required the occurrences of each ordered Thus a natural d-dimensional version of the Euler con- pair to be "in latin position" (Ger. lateini6ch verteilt). In jecture w o u l d be that if n = 2(2k + 1), there do not exist particular, he defined n t points of a h y p e r c u b e to be in m o r e than 2 d - 1 - d orthogonal h y p e r c u b e s of d i m e n - latin position if every s u b a r r a y of the h y p e r c u b e consion d and order n. tains either n o n e of the points or n 8 of the points for The algorithm in [18] enables one to construct large s o m e s < d, w h e r e d is the d i m e n s i o n of the hypercube. sets of m u t u a l l y o r t h o g o n a l h y p e r c u b e s of o r d e r n and Equivalent to H 6 h l e r ' s second condition is the inductive d i m e n s i o n d > 2 f r o m sets of MOLS of order n. In par- r e q u i r e m e n t that every pair of c o r r e s p o n d i n g s u b a r r a y s ticular, it is s h o w n that, given i,~ MOLS of o r d e r n, one be either isomorphic or orthogonal. See [16] for details. can construct The net effect is that for d _> 2 the m a x i m u m n u m b e r (in + 1 ) d - 1 d (3) Hd (n) of "H6hler-orthogonal" h y p e r c u b e s of d i m e n s i o n in d a n d order n is b o u n d e d a b o v e b y Hal(n) <_ (n -- 1) d-l. orthogonal h y p e r c u b e s of order n and d i m e n s i o n d _> More importantly, with this stronger version of orthog2. If i~ = n - 1, then the a b o v e n u m b e r of orthogonal onality, he w a s able to p r o v e a d > 2 analog of the Next h y p e r c u b e s is maximal, that is, it is (nd - 1 ) / ( n - 1) - d. Problem, namely, It is also s h o w n in [18] that for d > 2 and n _> 2, the d-dimensional Euler conjecture is false unless n = 2 or 6. T H E O R E M 1. For d > 2 there exist (n - 1) a-1 HShlerIt is true at n = 2 for a n y d _> 2; but the n = 6, d > 2 case orthogonal hypercubes of order n and dimension d if and only remains o p e n [18]: if n is a prime power.
PROBLEM 4. 2 Prove or disprove that for
n = 6 and d
>
2, Nd(6) = 2 a -- 1 -- d. Analogously, a d-dimensional MacNeish conjecture w o u l d be that Nd(n) = [(qd _ 1)/(qi -- 1)] -- d. In [18] it is s h o w n that if the M a c N e i s h conjecture is false for latin squares of order n, then the d-dimensional MacN e i s h conjecture is also false for all d > 2. This leaves [18] the C O N J E C T U R E . For d >_ 2 and n r 6 or a prime power, the d-dimensional MacNeish conjecture is false. 2 c. F. Laywine and the author have recently constructed six mutually orthogonal hypercubes of order 6 and dimension 3. See also Problem 6. As a consequence, Nd(6) > 2d -- 1 -- d for d > 2.
Acknowledgments The a u t h o r w o u l d like to t h a n k C . E L a y w i n e and C. J. C o l b o u r n for a n u m b e r of v e r y helpful comments. Thanks are also d u e the referees for p r o v i d i n g n u m e r o u s ideas which i m p r o v e d the original version of the paper. The author w o u l d also like to t h a n k the NSA for partial s u p p o r t u n d e r grant a g r e e m e n t M D A 904-92-H-3044.
References 1. T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Cambridge: Cambridge University Press (1986). 2. N. L. Biggs, T. P. Kirkman, mathematician, Bull. London Math. Soc. 13 (1981), 97-120. 3. R. C. Bose, On the application of the properties of Galois fields to the construction of hyper-Graeco-Latin squares, Sankhyd 3 (1938), 323- 338. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
21
4. R. C. Bose and S. S. Shrikhande, On the falsity of Euler's conjecture about the non-existence of two orthogonal latin squares of order 4t + 2, Proc. Nat. Acad. Sci. U.S.A. 45 (1959), 734-737. 5. R.C. Bose, S. S. Shrikhande, and E. T. Parker, Further results on the construction of mutually orthogonal latin squares and the falsity of Euler's conjecture, Can. J. Math. 12 (1960), 189 - 203. 6. A. E. Brouwer, Recursive constructions of mutually orthogonal latin squares, pp. 149-168 of [11]. 7. A. E. Brouwer, C. J. Colbourn, and J. H. Dinitz, Mutually orthogonal latin squares, in CRC Handbook of Combinatorial Designs (C. J. Colbourn and J. H. Dinitz, eds.), Boca Raton, FL, CRC Press (1995). 8. R. H. Bruck and H. J. Ryser, The non-existence of certain finite projective planes, Can. J. Math. 1 (1949), 88-93. 9. S. Chowla and H. J. Ryser, Combinatorial problems, Can. ]. Math. 2 (1950), 93-99. 10. J. D6nes and A. D. Keedwell, Latin Squares and Their Applications, New York: Academic Press (1974). 11. J. D6nes and A. D. Keedwell, Latin Squares, Annals of Discrete Math., Vol. 46, North-Holland, Amsterdam, 1991. 12. K. Devlin, Marginal interest, Focus 14 (1994), 16. 13. S.T. Dougherty, A coding theoretic solution to the 36 officer problem, Designs, Codes Cryptogr. 4 (1994), 123-128. 14. L. Euler, Recherches sur une nouvelle esp6ce de quarr6s magiques, Verh. Zeeuwsch Genootsch. Wetensch. Vlissengen 9 (1782), 85-239. 15. L. Euler, Opera Omnia (Collected Works), Leipzig: Teubner (1911). 16. P. H6hler, Eine Verallgemeinerung von orthogonalen lateinischen Quadraten auf h6here Dimensionen, Diss. Dokt. Math. Eidgen6ss Techn. Hochschule Z/irich, 1970. 17. C. W. H. Lam, L. Thiel, and S. Swiercz, The non-existence 22
THE MATf-IEMATICAL [NTELLIGENCER VOL. 17, NO. 3, 1995
18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28.
of finite projective planes of order 10, Can. J. Math. 41 (1989), 1117-1123. C. E Laywine, G. L. Mullen, and G. Whittle, D-dimensional hypercubes and the Euler and MacNeish conjectures, Monatsh. Math. 119 (1995), 223-238. J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge: Cambridge University Press (1992). H. F. MacNeish, Euler squares, Ann. Math. 23 (1922), 221 227. E. H. Moore, Tactical memoranda I - I I I , Am. J. Math. 18 (1896), 264- 303. G. L. Mullen and G. Whittle, Point sets with uniformity properties and orthogonal hypercubes, Monatsh. Math. 113 (1992), 265- 273. E.T. Parker, Construction of some sets of mutually orthogonal latin squares, Proc. Am. Math. Soc. 10 (1959), 946-949. E.T. Parker, Orthogonal latin squares, Proc. Nat. Acad. Sci. U.S.A. 21 (1960), 859-862. S. S. Shrikhande, A note on mutually orthogonal latin squares, Sankhyd, Series A 23 (1961), 115-116. D. R. Stinson, A short proof of the nonexistence of a pair of orthogonal latin squares of order six, J. Combinat. Theory Series A 36 (1984), 373-376. A. P. Street and D. J. Street, Combinatorics of Experimental Design, Oxford: Clarendon Press (1987). R.M. Wilson, Concerning the number of mutually orthogonal latin squares, Discrete Math. 9 (1974), 181 - 198.
Department of Mathematics The Pennsylvania State University University Park, PA 16802, USA e-mail:
[email protected]
Jeremy J. Gray*
Kepler's Work on Polyhedra Peter R. C r o m w e l l Introduction Although Johannes Kepler is remembered chiefly for his astronomical works, he was a prolific author and wrote on a diversity of topics. These included the first advances in the mathematical study of polyhedra since classical times. Kepler's interest in polyhedra spanned his whole career. They appear in his first published treatise, Mysterium Cosmographicum [1], as the essential ingredient in his exposition of the Creator's design of the cosmos, and also in one of his last major works, Harmonice Mundi [2], where he analyses various types of polyhedra: the Platonic and Archimedean solids, some rhombic polyhedra, and some self-intersecting polyhedra. The latter include the two star polyhedra which are perhaps Kepler's best known polyhedral innovation. They have been discussed by several writers [3, 4]; his other contributions seem to have been neglected. Coxeter [5] gives an overview of Kepler's work on geometry, but a detailed study has not been made.
tive constructions. To make the construction more difficult, thus demonstrating a greater proficiency with the new techniques, artists drew vacuous or skeletal polyhedral forms. The polyhedra in the plate illustrating Kepler's planetary model are drawn in this way (Fig. 1). Polyhedral figures were popular motifs among Italian marquetry workers who often incorporated them into
Background Over the 200 years preceding Kepler, interest in solid geometry had been revived in Europe. This was influenced by various factors: the rediscovery of classical works, especially Plato and his discussion of the regular bodies; increased trade and the need to estimate the volumes of containers quickly and accurately; and the introduction of perspective into painting. Being composed of straight lines and fiat planes, geometrical figures were a favourite exercise for perspec* C o l u m n Editor's address: Faculty of Mathematics, The O p e n University, Milton Keynes, MK7 6AA, England. THE MATHEMATICALINTELLIGENCERVOL.17, NO. 3 Q1995 Springer-VerlagNew York 23
Figure 1. Illustration from Kepler's Mysterium Cosmograph-
Figure 2. Illustration from Pacioli's Divina Proportione.
icum. their designs. Patterns which produce a strong threedimensional impression were also inset in coloured marble in the floors and staircases of palaces and cathedrals. Treatises on the mathematics of polyhedra were also written during this period. They were mainly concerned with the regular solids described by Plato and constructed in the thirteenth book of Euclid's Elements. Piero della Francesca's treatise Libellus de quinque corporibus regularibus [6] was translated into Italian by Luca Pacioli and incorporated as the third of the three parts of his book De Divina Proportione [7]. In the first part of the book, Pacioli shows how new polyhedra can be derived from the Platonic solids by the processes of augmentation (adding right pyramids to the faces) and truncation (slicing off corners or edges). The text is illustrated by Leonardo's drawings of the resulting figures, both solid and skeletal forms. An example is shown in Figure 2. Albrecht Diirer's book on craftsmen's geometry, Unterweysung der Messung [8], also contained sections dealing with solid bodies and polyhedra. The renowned Nuremberg goldsmith Wentzeln Jamnitzer was an avid collector of Diirer's work. He made a set of perspective drawings of polyhedral forms derived from the regular solids by the processes of augmentation, truncation, and other mutilations such as cutting notches out of the edges, or making incisions into the faces. The resulting solids all retain the same symmetry as the original--in only one case is the reflection symmetry destroyed to produce a cheiral polyhedron. These drawings were turned into etchings by Jost Amman and published in Perspectiva Corporum Regularium [9]. The final section of the book includes bodies derived from cones and spheres and a series of "polyhedral monuments" - - sculptures formed from polyhedra (see Fig. 3). 24
T~E MATHEMATICAL [NTELLIGENCER VOL. 17, NO. 3, 1995
Figure 3. Illusffation from Jamnitzer's Perspectiva Corporum Regularium. Courtesy of University College London. (Ref: Graves 148.L13.)
They could never be constructed, however, for they usually contain parts which are only connected through vertices, are balanced precariously on a single vertex, or are not supported at all. Note that Kepler's plate in Figure 1 also has this property: ARhough it appears to represent an actual model, the pieces do not support each other. Translations of the Greek classics also appeared during this period, along with commentaries. It seems that while Kepler was teaching at Graz, he had access to some of these: Commandino's Latin translation of Pappus (which appeared in 1588) and Candalla's Euclid (1566) which contains a sixteenth book, De mixtis et compositis regularibus solidis, showing how the regular polyhedra can be inscribed in one another. Whatever sparked off Kepler's interest in polyhedra, he certainly studied them while at Graz. It is here that he wrote Mysterium Cosmographicum with its notorious planetary model constructed around the five cosmic figures, and the conception of the Harmonice Mundi can also be traced back to this period. Definitions and Methods
The bulk of Kepler's work on polyhedra is contained in the second of the five books of Harmonice Mundi, an English translation of which has been made by J.V. Field [3]. Except where referenced otherwise, the quotations are from her paper. The first two of the five books of Harmonice Mundi are concerned with polygons and the different ways in which they form "congruences." In book one, Kepler defines a polygon to be regular if it is equilateral and has equal angles. He then defines a semiregular polygon to be one which is equilateral, and he restricts attention to those having four sides. Thus, Kepler's semiregular polygons are, in fact, rhombi. In the second book, he investigates the ways in which regular and semiregular polygons can be fitted together around a point. This leads to the construction of tessellations of the plane and of polyhedra. Kepler uses the word congruence, meaning "fitting together," to describe both situations-- a tessellation being a congruence in the plane, and a polyhedron being a congruence in space. (I shall use the modern terminology.) Here, Kepler is concerned with harmony in its broad sense, for the word "harmony" is derived from the Greek for "fitting together." He remarks that space-filling is another form of congruence. (He considered this aspect in De Nive Sexangula [10].) He defines a polyhedron as follows:
regular polygons or rhombi fitted together edge-to-edge. Note that he distinguishes between the polyhedral surface and the solid it bounds. He calls nonclosed polyhedra semisolid. The two examples of such polyhedra which he describes are self-intersecting polyhedra composed of star polygons. They can be completed by the addition of regular polygons (as required), but Kepler seems not to be aware of this. Kepler's classification of the polyhedra he discusses is summarised in the following diagram: Perfect (similar vertices) F
Most perfect
Perfect to a lesser degree
(congruent faces)
(regular facesof several kinds)
Regular
Semiregular
(Platonic)
(rhombic)
(Archimedean)
Imperfect (prismatic)
Having defined a perfect congruence as one in which all the vertices are similarly surrounded, he subdivides this class into those that are most perfect and those that are perfect to a lesser degree. The former category'comprises the polyhedra whose faces are all the same shape. These are further subdivided into regular and semiregular according to whether their faces are regular or semiregular polygons. The use of the term "semiregular" here should not be confused with modern usage: Kepler's semiregular polyhedra are rhombic polyhedra, not the Archimedean polyhedra to which the term is usually applied today. In fact, the rhombic polyhedra are not a subclass of the perfect polyhedra at all because their vertices do not all have the same valence. Kepler knows this but remarks: There is no reason why we should not call this congruence most perfect, for its imperfection is in the faces and is not a consequence of its being solid but, rather, an accidental feature. The polyhedra that Kepler calls perfect to a lesser degree have regular faces of several kinds. We know them as the Archimedean polyhedra and the families of prisms and antiprisms. Kepler notes that among the prismatic figures, the triangular antiprism and the square-based prism belong to the most perfect polyhedra (the former being the regular octahedron, the latter the cube). All the other prismatic solids are classified as imperfect, be-
There is a congruence in space, and a solid figure, when the individual angles of several plane figures make up a solid angle, and regular or semiregular figures are fitted together so as to leave no gap between the sides of the figures, which join up on the opposite side of the solid figure, or, if a gap is left, it is such that it can be filled by a figure of one of the kinds already employed, or, at least, by a regular figure. To Kepler, then, a polyhedron was a figure composed of
Figure 4. Illustration from Kepler's Harmonice Mundi. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
25
(a) Figure 5. (a) Rhombic dodecahedron; (b) rhombic triacontahedron.
ing either more like plane figures, in the case of prisms, or more like parts of figures than whole ones. Kepler's diagram showing an exploded view of an icosahedron shows clearly what he had in mind (Fig. 4). The middle slice is a pentagonal antiprism. Kepler's reason for investigating polyhedra becomes clear a little later: He wants to establish a hierarchy of polygons according to their "sociability" - - a measure of their capacity to combine with other polygons to form tessellations and polyhedra. Polygons are labelled either "congruous" or "unsociable" according to whether or not they can form part of a congruence. In a later book of Harmonice Mundi, this ranking is used to explain astrological phenomena. The first family of polyhedra which Kepler enumerates are the regular polyhedra. He notes that this proposition is the last in Euclid's Elements, and his proof follows the Euclidean one: He tries fitting combinations of polygons around a point and eliminates all the arrangements whose angle sum is greater than 360 ~. The five remaining possibilities can be realised as the Platonic solids.1 Kepler uses this method of proof consistently throughout book two: he tries all combinations of polygons round a point and notes the angle sums that are possible. Following his discussion of the Platonic solids, he describes four polyhedra whose faces are star polygons. Two of these are the well-known star polyhedra which have pentagram faces; the others are semisolid polyhedra. These are not discussed further. Kepler then turns to his semiregular polyhedra which he calls "solid rhombi." He knew two such polyhedra 1 In fact, Euclid's statement is unclear: "No other figure, besides the said five figures can be constructed which is contained by equilateral and equiangular figures equal to one another"[ll]. As it stands, this statement is false, even when restricted to convex figures. The problem arises because we do not know what "polyhedron" meant in Euclid's times. Waterhouse [12] suggests that inscribability in a sphere was an integral part of the early definitions, as the regular polyhedra are only discussed in relation to their circumsphere. The earliest treatment of the regular solids was given by Plato in the Timaeus and he, too, mentions the circumsphere. If this is assumed, then enumerating the possible types of solid angle does prove the proposition, for it is not hard to show that the vertiges of a circumscribed polyhedron whose faces are congruent regular polygons must all be the same type. In his definition, Kepler notes both properties.
26 THEMATHEMATICALINTELLIGENCERVOL.17,NO. 3. 1995
(see Fig. 5). One is bounded by 12 rhombi whose diagonals ale in the ratio 1 : v~; the other is bounded by 30 rhombi whose diagonals are in the golden ratio. It seems that he had known of these two polyhedra, together with one of the star polyhedra, much earlier. In a letter to Michael M/istlin [13], he describes a polyhedron composed of 12 pentagram faces and remarks that it is one of several "Keplerian" polyhedra to be discussed in a new book (Harmonice Mundi). The other "Keplerian" polyhedra are probably these rhombic solids. The star polyhedron is also described in a letter to Herwart von Hohenburg [14]. Kepler attempts to prove that he has found all possible rhombic polyhedra. In the course of this, he discovers the rhombohedron (a cube stretched linearly along one diagonal) but discards it as imperfect. He is interested only in polyhedra which have a spherical symmetry group. There are, in fact, two other rhombic polyhedra: One found by Fedorov in 1885 is bounded by 20 rhombi; the other was discovered by Bilinski [15] when he carried out a rigorous enumeration. It has 12 faces and he called it the "rhombic dodecahedron of the second kind" to distinguish it from Kepler's solid. Both of these polyhedra can be derived from Kepler's rhombic triacontahedron by collapsing belts of rhombi running round the polyhedron. In his enumeration of the Archimedean solids, Kepler gives them each a name which, in most cases, is that still used today (see Figs. 12 and 13). His nomenclature is systematic and indicates how each polyhedron is related to the Platonic solids. The truncated figures need no explanation. The cuboctahedron and icosidodecahedron are also fairly clear. However, variants of the other names have been proposed. It has been argued that because the snub cube is related as much to the octahedron as to the cube (having faces contained in the face-planes of both), it is more logical to call it a snub cuboctahedron. Likewise, the snub dodecahedron could be called the snub icosidodecahedron. The figure commonly called the rhombicuboctahedron was given two names by Kepler, the other being "truncated cuboctahedral rhombus." As Kepler refers to his rhombic faced polyhedra as "solid rhombi," it seems that this alternative name stems from the fact that the solid has the same combinatorial structure as the solid obtained by truncating the rhombic dodecahedron - - a figure which, as we will see later, can be derived from the cube-octahedron compound. The truncation produces rectangular faces instead of squares, and the resulting figure needs to be distorted slightly to obtain a figure with regular faces. This polyhedron can also be obtained from the cuboctahedron by joining the midpoints of the edges (producing the same figure as before) and distorting it. The prefix "rhombi" in the name "rhombicuboctahedron" is said by some authors to signify that the figure contains faces in the face-planes of a rhombic polyhedron; others see it as a reminder that a deformation has
been applied to change rectangular faces into rhombi (squares). The truncated cuboctahedron has also given rise to problems because it is not a true truncation. Kepler himself recognised that it is not formed by truncating a cuboctahedron but that it is analogous to such a figure (i.e., it has the same combinatorial type). Again, rectangles formed by truncation need to be deformed into squares. This has led some to call it the "great rhombicuboctahedron," requiring the prefix "small" to be added to other figure. Wenninger [16] proposes the compromise "rhombitruncated cuboctahedron." Similar remarks apply to the rhombicosidodecahedron and the truncated icosidodecahedron. The Rhombic Polyhedra
The rhombic polyhedra are described by the following definition: The solid formed is semiregular when the plane figures are semiregular. Its solid angles are then not all the same, but differ in the number of lines they contain, though the angles are not more than two kinds and neither are they distributed on more than two spherical surfaces, which are concentric. The number of angles of each kind must be the same as the number of angles of one of the regular solid figures. Kepler knew two polyhedra that satisfy this definition: the rhombic dodecahedron (of the first kind) and the rhombic triacontahedron (Fig. 5). In an earlier work, he provides a hint as to h o w he discovered these two polyhedra. The De Nive Sexangula is nominally concerned with the question of w h y snowflakes have six corners although it makes frequent diversions and touches on m a n y other topics. In one of these asides, Kepler considers another example of hexagonal forms occurring in nature, namely, a honeycomb. He notes that a bee's cell is terminated at the base by three equal rhombi. He continues: These rhombi put it into my head to embark on a problem of geometry: whether any body, similar to the five regular solids and to the fourteen Archimedean solids could be constructed with nothing but rhombi. I found two, one with affinities to the cube and octahedron, the other to the dodecahedron and icosahedron--the cube can itself serve to present a third, owing to its affinity with two tetrahedra coupled together. The first is bounded by twelve rhombi, the second by thirty. [17, p. 11] The clue is in the reasons given for including the cube as a third possibility. Two equal tetrahedra can be placed so that the edges of one meet the edges of the other at right angles and so that the points of intersection bisect the edges. Such a pair of coupled tetrahedra is shown in Figure 6. Kepler named this body "stella octangula," but it was known to m a n y others including Pacioli and Jamnitzer. Pacioli called it "octaedron elevatum." The eight corners of this c o m p o u n d polyhedron coincide with the corners of a cube, the edges of the tetrahedra forming diagonals of the square faces.
Now, an octahedron and a cube of appropriate sizes can also be coupled together so that their edges bisect each other at right angles (see Fig. 7). The relationship between the rhombic dodecahedron and this compound is analogous to that between the cube and the two tetrahedra: The corners of the rhombic polyhedron coincide with those of the cube and the octahedron, and two intesecting edges of the c o m p o u n d are diagonals of a rhombic face. The regular dodecahedron and the icosahedron can be similarly coupled together to form a c o m p o u n d polyhedron (Fig. 8). This c o m p o u n d shows a similar affinity with the rhombic triacontahedron. Having described the two rhombic polyhedra again in Harmonice Mundi, Kepler proceeds to show that these are, in fact, the only polyhedra which satisfy his definition of semiregular. First, he observes that in any rhombus, opposite angles are equal, two being acute, the others being obtuse. Furthermore, the s u m of an acute angle and an obtuse angle is 180 ~. The obtuse angle must be greater than 90~ henc.,r there cannot be four or more ob-
Figure 6. Compound of two tetrahedra.
Figure 7. Compound of cube and octahedron.
Figure 8. Compound of dodecahedron and icosahedron. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3,1995
27
t
Z (b)
Figure 9. (a) Prolate rhombohedron; (b) oblate rhombohedron.
Figure 10. A rhombic tessellation.
tuse angles surrounding a point because the angle sum would be greater than 360 ~. So, if all the angles bounding a solid angle are obtuse, there must be exactly three rhombi forming the solid angle. The acute angles of three rhombi can be fitted together to form a solid angle, and two such sets can be joined to form a (prolate) rhombohedron (see Fig. 9). Its eight vertices lie on two concentric spheres; six on the inner sphere and two on the outer one. The final clause of Kepler's definition of a semiregular polyhedron excludes this case, for no regular polyhedron has two vertices. The requirement that the two kinds of vertex have different valencies also rules out this case. But, Kepler argues, this polyhedron should also be excluded because the six equatorial solid angles are "mixed," being composed of both acute and obtuse angles: Each of the six obtuse solid angles is formed by two obtuse plane angles and one acute one, an irregularity which is once more contrary to the definitions. Such "irregularities" are not, in fact, excluded; perhaps they are not in the spirit of perfection implicit in the definitions. In the remainder of the proof, he relies on this extra "implicit" condition: that each solid angle is bounded by a single type of plane angle so that acute angles meet 28
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
only acute angles, and obtuse angles meet only obtuse angles. If the obtuse angles in the rhombus are greater than 120~, then three obtuse angles cannot be brought together to form a solid angle. If the obtuse angles are exactly 120~ then the rhombi can be fitted together to form a tessellation (Fig. 10). So, to form a polyhedron, the obtuse angles in a rhombus must be less than 120 ~ and, consequently, .the acute angles must be greater than 60 ~. If all the plane angles surrounding a solid angle are acute, then there can be at most five of them, because if there were six or more, the angle sum would be greater than 360 ~. The case with three acute angles meeting has already been excluded; so the only possibilities remaining are for a solid angle to be bounded by four or five acute angles. These two possibilities are realised in the two rhombic polyhedra. There are two points to note arising from this discussion. First, the proof is not constructive-- it does not tell us what shape of rhombus we need to make the polyhedra. Nor does it guarantee their existence. However, Kepler already knows that two such polyhedra do exist and only wants to show that there are no others. Even so, the question of uniqueness still needs to be considered. The second point concerns the definition of semiregular polyhedra. It appears that, having found two rhombic polyhedra which are similar to the Platonic solids in that they are spherical and have equal faces, Kepler desired to show that (like the Platonic solids) their number is limited, and that he had found all the possibilities. He listed several properties shared by both polyhedra and hoped that these were sufficient to characterise them. In order to exclude the rhombohedron, he restricted the number of solid angles of each kind to be the same as occurs in one of the Platonic solids. (He applied a similar restriction when dealing with the Archimedean solids, intending to exclude the prisms and antiprisms but, in fact, excluding others as well.) In the course of the proof, he finds it more convenient to use another property that both of his rhombic polyhedra possess but which is not included in the definition. Here, as in much of Kepler's writing, we can watch thought processes in action. We also juggle definitions and proofs to achieve the strictest accuracy and widest applicability of our theorems. We, however, cover over our early attempts at definitions which do not provide the properties required in a proof. In Kepler's case, a proof-generated definition could be phrased as follows: A polyhedron is semiregular if all its faces are semiregular polygons (rhombi) and each solid angle is surrounded by a single kind of plane angle. The Archimedean
Solids
In his Mathematical Collection, Pappus attributes to Archimedes the discovery of 13 polyhedra: "Figures contained by equilateral and equiangular, but not similar, polygons." Unfortunately, Archimedes's own treatment
of them is lost; even so, the 13 polyhedra of Figures 12 and 13 are still k n o w n as Archimedean solids. As with Euclid (see footnote 1), Pappus's definition is incomplete unless we require that the p o l y h e d r a be inscribed in a sphere. 2 In this case, the condition that the vertices lie on a sphere is still insufficient, for there is a 14th solid which satisfiesthis condition (see Fig. 11). It is possible that Kepler k n e w this polyhedron, for in the passage from De Nive Sexangula quoted above he refers to 14 Archimedean solids. The true Archimedean solids have one of the spherical 3 g r o u p s as their s y m m e t r y group; the 14th solid, the prisms, and antiprisms all have dihedral symmetry. The creation of new figures for perspective designs had led to some of the Archimedean solids being rediscovered. Drawings of some of them are included in Pacioli's Divina Proportione (Figure 2) and Dfirer's Unterweysung der Messung; a few a p p e a r in Jamnitzer's Perspectiva Corporum Regularium [9]. Prior to Kepler, no one seems to have rediscovered the complete set. From his reference to "Archimedean solids" w e can d e d u c e that he was aware of Pappus's w o r k and that, therefore, he k n e w to search for 13 polyhedra. However, through his mathematical analysis, he found that prisms and antiprisms also satisfy the definition; the latter had not been described before. H e defines these figures as follows: A congruence is perfect, but of lower degree, when the plane figures are regular and all the angles lie on the same spherical surface and are similar to one another, but the faces are of various kinds, though the number of each kind must be the same as the number of faces of one of the most perfect figures, that is, not less than four which is the minimum number of planes to bound a solid figure. There is an imperfect congruence or figure when other conditions remain the same but the larger plane figure does not occur more than twice. The requirement that the n u m b e r of faces of each kind in one of these figures is the same as the n u m b e r of faces in a most perfect p o l y h e d r o n (i.e., 4, 6, 8, 12, or 20 for the Platonic solids, and 12 or 30 if Kepler's rhombic solids are included) is intended to exclude prisms and antiprisms. Kepler regards these as imperfect figures being "discus-shaped" rather than "globe-shaped" like a s p h e r e - - the most perfect of all solids. Rather than insist that the n u m b e r of each kind of face is at least three, which appears to be a somewhat arbitrary restriction, he links the n u m b e r s of faces to the perfect solids, which seems more legitimate. However, the condition is far stronger than is n e e d e d and excludes more than 2 A p a r t from the vertex-transitive p o l y h e d r a there are 92 convex polyh e d r a w h o s e faces are regular p o l y g o n s [18,19]. Most of t h e m are parts ol~the A r c h i m e d e a n figures, b u t 17 of t h e m cannot be p r o d u c e d in this way. 3 [ like to d i s t i n g u i s h b e t w e e n the spherical a n d the prismatic groups. By the former, I m e a n g r o u p s w h i c h contain m o r e t h a n one n-fold rotation for n > 2, as o p p o s e d to prismatic g r o u p s w h i c h contain at m o s t one s u c h rotation. O t h e r a u t h o r s like to regard the d i h e d r a l g r o u p s as spherical.
Figure 11. A fourteenth "Archimedean" solid?
Kepler intended. There are Archimedean solids that do not possess this p r o p e r t y - - t h e snub polyhedra have more than 30 triangular faces. Kepler's enumeration of these polyhedra proceeds by considering all possible ways that a solid angle could be formed from regular polygons. This task is straightforward but s o m e w h a t laborious. Two preliminary observations make the process easier: The plane can not be'filled by a congruence of the individual angles of plane figures of more than four kinds [in fact three kinds]. Three plane angles of figures of three different kinds, one having an o d d n u m b e r of sides, cannot come together in a perfect solid figure. The first of these lemmas is straightforward to prove. The four regular polygons having the smallest internal angles are the triangle (60~ the square (90~ the pentagon (108~ and the hexagon (120~ The total s u m of these four angles is greater than 360 ~, so these four regular polygons cannot all be present a r o u n d a vertex. With a different set of four or more different regular polygons, the total angle sum is even larger. Hence, four or more different kinds of polygons cannot surround a vertex. The second lemma is used to exclude certain combinations of polygons a r o u n d 3-valent vertices. It is convenient to make a distinction between the set of faces which b o u n d a solid angle and the specific order in which they occur. Thus, following Grfinbaum and Shephard [20], the species of a solid angle is an u n o r d e r e d list of the faces which are present, whereas the type of a solid angle specifies the order in which the faces occur around the vertex. For example, the species of a solid angle b o u n d e d by two 3-gons and two 4-gons comprises two types of solid angle according to whether opposite faces are the same or different. The two types can be written in a shorthand fashion as (3,3,4,4) and (3,4,3,4) where the lists contain the n u m b e r of sides of each face in order. Kepler appears not to have m a d e a distinction between species and types. He enumerates only vertex species, and in the case of the above example, he writes: Two trigon angles and two tetragon angles are less than four right angles. Thus eight trigons and six tetragons fit together to form a tessareskaedecahedron which I call a cuboctahedron. It is shown here with the number eight [see Fig. 13]. THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3, 1995 29
Figure 12. Illustration from Kepler's Harmonice Mundi. 1: Truncated cube; 2: truncated tetrahedron; 3: truncated dodecahedron; 4: truncated icosahedron; 5: truncated octahedron; 6: truncated cuboctahedron; 7: truncated icosidodecahedron.
H e does not mention that there are two possible arrangements of the polygons r o u n d the vertex. The illustration shows h o w they are to be arranged; the type (3,3,4,4) is not considered. 4 This case cannot be realised as a perfect polyhedron. To exclude it, an analogue of the lemma above is required which applies to 4-valent vertices. It is easy to formulate and is p r o v e d in a m a n n e r similar to the 3-valent case. These two results are collected together in the following lemma.
A polyhedron in which all the solid angles are surrounded in the same way cannot have solid angles of the following types: LEMMA.
4 In the case of tessellations of the plane, he does find different types of the s a m e species.
30 THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3, 1995
Figure 13. Illustration from Kepler's Harmonice Mundi. 8: cuboctahedron; 9: icosidodecahedron; 10: rhombicuboctahedron; 11: rhombicosidodecahedron; 12: snub cube; 13: snub dodecahedron.
(i)
(ii)
~
wherea is odd and b # c.
where a # c.
Proof. In the first case, the fact that all the solid angles have the same type implies that the b-gon faces must alternate with the c-gon faces r o u n d the b o u n d a r y of an a-gon face. But, as a is assumed to be odd, this leads to a contradiction. In case (ii), we consider the w a y that the faces must be arranged a r o u n d the 3-gon. At each angle, the face
opposite the 3-gon is always a b-gon. Because all the solid angles have the same type, the sides of the 3-gon must be attached to a-gons and c-gons, and these must alternate around the 3-gon. This again leads to an inconsistency. Kepler's final theoren~ in book 2 reads: There are thirteen solid congruences which are perfect to a lower degree. From these thirteen we obtain the Archimedean solids. The theorem is proved by exhausting all the possible combinations of faces which can surround a vertex. All the types of solid angle that are not excluded by the simple conditions in the previous lemmas are candidates for polyhedra which are perfect to a lower degree. After ignoring the "imperfect" prismatic figures, the 13 possibilities which remain are realised by the Archimedean solids. Kepler's illustrations of them are shown in Figures 12 and 13. The order of the polyhedra in the figures does not match the order in which they appear in the enumeration. Instead, all the truncated solids are grouped together. Furthermore, the truncations of the Platonic solids are in the same sequence as the Platonic figures in the cosmological model. Star Polyhedra
In book one of Harmonice Mundi, Kepler defines a regular polygon as a figure whose sides are all equal in length and whose angles are equal and pointing outwards. He goes on to distinguish two kinds of regular polygon: the fundamental or primary ones whose sides do not cross, and others of a more general type called stellated polygons. These stellated polygons can be derived from the primary ones by extending their sides until they intersect. He includes only those stellated polygons that can be traced in a single line. Kepler then generalised this procedure so that it could be applied to the regular polyhedra. When considering polygons, it is clear that the stellated figures are produced by extending the sides of the convex figures. But in three dimensions it is less clear how to p r o c e e d - - w h a t should be extended?, which parts of a polyhedron are its sides? Kepler gives two alternative generalisations of this idea. First, the sides of the faces of the polyhedron can be extended until they intersect. A polyhedron produced in this way is called an echinus, and Kepler aptly describes such polyhedra as spiky or prickly (echinus means "hedgehog" or "sea urchin"). His second method involves extending the faces themselves until they intersect, the resulting polyhedron being called an ostrea ("oyster"). The two stellated polyhedra that Kepler discovered appear to have been produced by applying the first method to the Platonic solids. In his account of the resulting polyhedra, he gives descriptions only and does not pass on any indication as to how they were discovered. Extending the edges of a tetrahedron does not produce a new polyhedron, as the lines do not intersect apart from
Figure 14. (a) Small stellated dodecahedron; (b) great stellated dodecahedron.
at the original vertices. The same is true of the cube and the octahedron. Applying the stellation-process to the dodecahedron does produce an example of a echinus; the icosahedron furnishes the other example. These two polyhedra are shown in Figure 14. In the last few years of life, Kepler started preparing a treatise on geometry. In his notes for this unfinished work there is a section entitled De auctis (on augmented figures) which deals with the stellation process. In this work, he calls the two star polyhedra echinus major icosagdricus and echinus minor icosa~dricus (larger and smaller icosahedral hedgehogs). Kepler also recognised that the larger hedgehog could be derived from the dodecahedron via the second process of face stellation. In fact, both of the polyhedra can be produced in this way, and it is the process of face stellation which is referred to in their current English names: the 12-vertex one being the "small stellated dodecahedron" and the 20-vertex one the "great stellated dodecahedron." These names were introduced by Cayley [21]. These two polyhedra can easily be regarded as convex regular polyhedra with a suitable pyramid erected on each face. From this point of view, one is led to compare the convex figure with the augmented one. Noticing this, Kepler comments that the stellated figures are so closely related the one to the dodecahedron and the other to the icosahedron that the latter two figures, particularly the dodecahedron, seem somehow truncated or maimed when compared to the figures with spikes. The process of augmenting convex polyhedra by adding pyramids of various heights had been used to generate many new polyhedra in the preceding 200 years. It is not surprising, therefore, to find that all of Kepler's stellated forms had already been depicted. Earlier sketches of the stella octangula have already been mentioned. A picture of the small stellated dodecaheTHE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
31
dron dating from the 1420s can be seen in St. Mark's Basilica in Venice. It is inlaid in marble and forms part of the floor decorations. It is located in one of the main doorways. The design has been attributed to Uccello. The great stellated dodecahedron was pictured by Jamnitzer as part of one of his polyhedral monuments (Fig. 3). The spiky component at the core of this monument is clearly an example of this polyhedron, but, as far as I am aware, this has not been noticed before. However, Kepler's interest in these figures was not merely aesthetic. He considered them in a mathematical context. These two stellations of the dodecahedron can be interpreted in yet another way. A close examination of the small stellation reveals that the triangular faces are arranged in groups of five so that all the faces in each group lie in a plane. Furthermore, each group surrounds a regular pentagon buried under a pyramid. Together, a pentagon and its five satellite triangles form a pentagram. Therefore, this polyhedron can be regarded as having pentagrams for faces, 12 in total, arranged with 5 meeting at each vertex. The great stellation can also be regarded as being built up from 12 pentagrams, meeting in threes at the vertices. Under this radically different interpretation the faces of the polyhedra are allowed to pass through each o t h e r - - like the sides of a star polygon. The star pentagon faces are joined side against side as in conventional polyhedra, yet they pass through each other, allowing some parts of each face to be seen and confining others to the interior of the polyhedron hidden from sight. Regarding the faces of these polyhedra as pentagrams forces us to accept the following surprising conclusion: They are regular polyhedra, for they have equal regular polygons for faces, the same number surrounding each solid angle. Including the star polygons among the regular polygons allows a more general type of regular polyhedron to be constructed. Kepler does not recognise that, in this generalised setting, his new regular polyhedra have the same status as the convex regular polyhedra. In the same way that he separated regular polygons into primary and stellated, he regards the convex polyhedra as fundamental and their stellations as secondary: "nothing but an augmented dodecahedron (but augmented most regularly)." Perhaps part of the reason why he was reluctant to raise his hedgehogs to the level of the Platonic polyhedra was that it would ruin his solution of the cosmic mystery. Even after his work on the elliptical nature of planetary orbits, Kepler continued to experiment with his planetary model. In book five of Harmonice Mundi, he investigates the possibility of replacing the dodecahedron and icosahedron by a single echinus major with its circumsphere bounding the orbit of Mars and its midsphere bounding the orbit of Venus, leaving Earth's orbit free and undetermined. 5 But in a later work, Epitome Ass S e e [22], e x t r a c t 1 0 . A 3 ( a ) , p p . 3 2 4 - 3 2 5 .
32
THE MATHEMATICALINTELLIGENCER VOL. 17, NO. 3, 1995
(a)
(b) Figure 15. One of Kepler's semisolid polyhedra (a) and its completion (b).
tronomiae Copernicanae, he discards this idea. If such an alteration is made, then the reason there are but six planets evaporates, and the whole harmonious nature of his system is destroyed. This unwillingness to abandon his cherished model may go some way to explaining why Kepler did not investigate the properties of his star-faced polyhedra more thoroughly. In the case of the two rhombus-faced polyhedra, he proceeded to analyse them and show that he had found all the possibilities. In contrast, he makes no attempt to establish whether any other polyhedra have properties similar to his star polyhedra. The two stellations are composed of pentagrams meeting in groups of three or five to form the solid angles. Is it possible to construct a polyhedron with four pentagrams surrounding each solid angle? Furthermore, the angle in the corner of a pentagram is 36 ~ so up to nine can be fitted round a vertex. It is conceivable that polyhedra with up to nine pentagrams per solid angle could be constructed. The other star polygons provide further possibilities. There are no other regular polyhedra bounded by star polygons. After Poinsot [23] had rediscovered Kepler's two star polyhedra, along with two other polyhedra which have convex faces but whose vertex figures are star polygons, Cauchy [24] proved that these four are the complete set of regular star polyhedra. Bertrand [25] provided a different proof. Semisolid Polyhedra Kepler did experiment with other star polygons. Besides the two pentagram-faced polyhedra, he found two semisolid polyhedra: One composed of star octagons, the other of star decagons. The sides of the first and fourth points of star octagons and star decagons lie in a line, which passes through two intermediate points, and the stars can be fitted together with such sides joined two by two. The star octagons make a kind of cube, and the star decagons a kind of dodecahedron, figures
which have not angles but ears, for when two of the plane angles are fitted together they must leave a gap, which can not be closed. The "eared cube" is illustrated in Fig. 15(a). In fact, these two figures can be completed by the addition of regular polygons. Eight triangles a d d e d to the six octagrams of the "eared cube" form a polyhed r o n which Wenninger [16] calls a "quasitruncated hexahedron" [Fig. 15(b)]. The second figure is completed b y the addition of 12 pentagons. Wenninger calls this a "quasitruncated small stellated dodecahedron." These are two of the uniform p o l y h e d r a - - a generalisation of the Archimedean p o l y h e d r a in which the faces must be regular polygons (or star polygons) not all the same kind, and the s y m m e t r y g r o u p must act transitively on the vertices. The p o l y h e d r o n m a y intersect itself as do the two examples above. Besides the Archimedean solids, there are 53 such polyhedra. The list given by Coxeter, et al. [26] was shown to be a complete enumeration by Skilling [27].
Concluding Remarks Kepler's influence on the subsequent d e v e l o p m e n t of mathematics is minimal. His work on star polyhedra was certainly u n k n o w n to Poinsot 200 years on. Later still, Catalan [28] was unaware that the Archimedean solids had been previously investigated. One reason that Kepler's results were overlooked is that m u c h of his work is not published in the form of a scientific exposition, but rather as a saga recording the trials of the process of discovery. Finally, it seems surprising that Kepler did not discover Euler's formula. He possessed all the requisite concepts. He distinguished between surfaces and solids. His polyhedra were "congruences" of polygons fitted together edge-to-edge to form a closed surface: The comp o u n d s of regular p o l y h e d r a and the star p o l y h e d r a can only be understood as intersecting surfaces. Furthermore, the process of edge-stellation shows that he had isolated the edge as a constituent of a polyhedral surface. He had a passion for searching out numerical relationships. But there is no evidence that he m a d e any connection. Topological ideas had to wait until the following century.
Acknowledgments I am grateful to the staff of the library at University College L o n d o n for allowing me access to their collection of rare books. The illustration in Figure 3 is included with their permission. I w o u l d also like to thank Branko G r 6 n b a u m and Jeremy Gray for their helpful comments.
References 1. J. Kepler, Mysterium Cosmographicum, Tubingen (1596). In M. Caspar, Johannes Kepler Gesammelte Werke, Munich: Beck (1938), Vol. 1.
2. J. Kepler, Harmonice Mundi, Linz (1619). In M. Caspar, Johannes Kepler Gesammelte Werke, Munich: Beck (1938), Vol. 6. English translation of book two in J. V. Field [3]. 3. J.V. Field, Kepler's star polyhedra, Vistas Astron. 23 (1979) 109-141. 4. J. P. Phillips, Kepler's Echinus, ISIS, 56 (1965), 196-200. 5. H. S. M. Coxeter, Kepler and mathematics, Vistas Astron. 18 (1975), 661-670. 6. M. D. Davis, Piero della Francesca's mathematical treatises, Ravenna, Italy: Longo Editore (1977). 7. L. Pacioli, Divina Proportione, Venice (1509). 8. A. Diirer, Unterweysung der Messung mit dem zirkel un richtscheyt in linien ebnen unnd gantzen corporen, N/irnberg (1525). 9. W. Jamnitzer, Perspectiva Corporum Regularium, N/irnberg (1568). 10. J. Kepler, De Nive Sexangula, Prague: (1611). English translation in C. Hardie [17]. 11. T. L. Heath, The Thirteen Books of Euclid's Elements, Cambridge: Cambridge University Press (1908). 12. W. C. Waterhouse, The discovery of the regular solids, Arch. History Exact Sci. 9 (1972), 212-221. 13. J. Kepler, letter to Micheal M/istlin, M. Caspar, Johannes Kepler Gesammelte Werke,Munich: Beck (1938), 14 letter 132, pp. 43- 59. 14. J. Kepler, letter to Hermart von Hohenburg, M. Caspar, Johannes Kepler Gesammelte Werke, Munich: Beck (1938), 14 letter 130, p.p. 31-44. 15. S. Bilinski, Uber die Rhombenisoeder, Glasnek Mat. Fiz. Astron. Drustvo Mat. Fiz. Hrvatske (series 2) 15 (1960), 251 -262. 16. M. J. Wenninger, Polyhedron Models, Cambridge: Cambridge University Press (1971). 17. C. Hardie, The Six-Cornered Snowflake, Oxford: Oxford University Press (1966). 18. N. W. Johnson, Convex polyhedra with regular faces, Can. J. Math. 18 (1966), 169-200. 19. V. A. Zalgaller, Convex Polyhedra with Regular Faces, New York: Consultants Bureau (1969). 20. B. Griinbaum and G. C. Shephard, Tilings and Patterns, San Francisco: Freeman (1987). 21. A. Cayley, On Poinsot's four new regular solids, Philos. Mag. 17 (1859), 123-128. Second note on Poinsot's four new polyhedra, Philos. Mag. 17 (1859), 209-210. 22. J. Fauvel and J. Gray, The History of Mathematics: A Reader, New York: MacMillan (1987). 23. L. Poinsot, M6moire sur les polygones et les polybdres, J. Ecole Polytech. 10 (1810), 16-48. 24. A.L. Cauchy, Recherches sur les poly6dres (first m6moire), J. Ecole Polytech. 9 (1813), 68-86. 25. J. Bertrand, Note sur la th6orie des poly6dres reguliers, Compt. Rend. Seances Acad. Sci. 46 (1858), 79-82. 26. H.S.M. Coxeter, M. S. Longuet-Higgins, and J. C. P. Miller, Uniform polyhedra, Philos. Trans. Roy. Soc. London (series A) 246 (1953), 401-450. 27. J. Skilling, The complete set of uniform polyhedra, Philos. Trans. Roy. Soc. London (series A) 278 (1975), 111 -135. 28. E.C. Catalan, M6moire sur la th6orie des poly6dres, J. Ecole Polytech. 24 (1865), 1 -71.
Department of Pure Mathematics The University P.O. Box 147 Liverpool L69 3BX, United Kingdom THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
33
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 our subject's glorious and inglorious past: statues, plaques, graves, the caff where the famous conjecture was made, the desk where the famous ini-
tials 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 inviteyou 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.
Fullerene Geometry under the Lion's Paw Istv in Hargittai "... the spherical is the form of all forms most perfect, having need of no articulation; and the spherical is the form of greatest volumetric capacity, best able to contain and circumscribe all else; and all the separated parts of the w o r l d - - I mean the sun, the moon, and the stars--are observed to have spherical form; and all things tend to limit themselves under this f o r m - - a s appears in drops of water and other liquids--whenever of themselves they tend to limit themselves. So no one may doubt that the spherical is the form of the world, the divine body." From Copernicus, De Revolutionibus Orbium Caelestium, 1543.
H e a v e n , in fact, is often depicted as a sphere in sculptures. The sphere m a y also be a representation of the Globe, a n d it is said to symbolize p o w e r as well. Two lions stand g u a r d in front of the Spanish C h a m b e r of Deputies (Congreso de los Diputados). One of t h e m has a sphere u n d e r the right p a w a n d the other u n d e r the left p a w (Figure 1). The surfaces of these spheres are smooth, without a n y decoration. It has b e e n c o m m o n practice in China to have lion sculptures in front of i m p o r t a n t (and not so important)
Figure 1. Two lions in front of the Chamber of Deputies (Congreso de los Diputados), Madrid, Spain
*Column Editor's address: Mathematics Institute, University of Warwick, Coventry, CV4 7AL England.
34 THEMATHEMATICAL INTELLIGENCER VOL. 17, NO. 3 (~)1995 Springer-Verlag New York
Figure 2. Two bronze lions in front of the Gate of Supreme Harmony (TAIHEMEN) in the Forbidden City, Beijing, China.
Figure 3. Two gold-plated lions in front of the Gate of Heavenly Purity (QIANQINGMEN) in the Forbidden City, Beijing, China. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995 3 5
When Kroto and co-workers observed [2] the great relative abundance of C60 molecules in their laser vaporisation cluster-beam experiment, a search followed for the structure of this extraordinarily stable species. Kroto [3] describes eloquently how his previous encounters with Buckminster Fuller's work, and in particular the Geodesic Dome as the U.S. Exhibition Hall at the Montreal Expo, assisted him and his colleagues to arrive at the highly symmetrical truncated icosahedral structure (Figure 5). A visit to the Forbidden City might have been similarly instructive and beneficial. All photographs in this Note were taken by the author in 1993. I am grateful to Miss Jing Wei, student of Peking Unicersity, for her kind assistance in gathering information about the lion sculptures in the Forbidden City.
buildings. These lions also appear in pairs. The female has a baby lion under the left paw and the male has a sphere under the right paw. The female lion is apparently teasing the baby lion while the sphere under the male's paw is said to represent a ball made of strips of silk, which was a favorite toy in ancient China. Figure 2 shows a pair of bronze lions in front of the Gate of Supreme Harmony (Taihemen) in the Forbidden City, Beijing. It was made during the reign of the Ming Dynasty (1368-1644). An elaborate regular hexagonal decoration of the surface of the sphere is under the male lion's paw. It is not possible, however, to cover the surface of the sphere by a regular hexagonal pattern. Indeed, considerable chunks of the sphere are hidden by the lion's paw and by the stand itself on which the lion and the sphere stand. Other lions with similar decorations of the sphere are found in many other places. An interesting pair of lions whose male partner has a sphere under the paw with a different decoration is shown in Figure 3, with sphere in a close-up in Figure 4. This pair is in front of the Gate of Heavenly Purity (Qianqingmen) in the Forbidden City and dates back to the reign of Qian Long (1736-1796) of the Qing Dynasty. The surface of this sphere is decorated by a hexagonal pattern which, however, is interspersed by pentagonal shapes. Such a pattern can indeed cover the complete surface of a sphere. Mathematicians have known, of course, that one can close an even-number of vertices with any number of hexagons (except one), provided 12 pentagons are included in the network (see, e.g., [1]). An important recent discovery in chemistry is related to such structures.
Budapest Technical University Szt. Gelldrt tdr 4 H-1521 Budapest Hungary
Figure 4. Close-up of the sphere under the male lion's paw of Figure 3. Several pentagonal shapes are seen interspersed in the hexagonal pattern decorating the surface of the sphere.
Figure 5. The structure [4] proposed for the super-stable C60 all-carbon molecule. Each vertex is occupied by a carbon atom. The single and double lines represent two different carbon-carbon linkages. This structure has been proved by a variety of physical and computational techniques (see, e.g., [5]).
36
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
References
1. Gasson, P. C. Geometry of Spatial Forms. Ellis Horwood, Chichester, 1983, pp. ix-x. 2. Kroto,H. W., Heath, J. R., O'Brien, S. C., Curl, R. E, Smalley, R. E. Nature 1985, 318, 162. 3. Kroto,H. W. Angew. Chem. Int. Ed. Engl. 1992, 31,111. 4. Kroto,H. W. In Symmetry 2: Unifying Human Understanding; Hargittai, I., Ed.; Pergamon Press: Oxford, 1989; pp. 417-423. 5. Hargittai, I. Per.Mineral. 1992, 61, 9.
Impressions from Riemann's Native Country Annette Laugwitz and Detlef Laugwitz
Bernhard Riemann (1826 - 1866) was one of the outstanding mathematicians of the 19th century. His work revolutionized complex analysis and g e o m e t r y - - Riemann surfaces and the still unsettled Riemann hypothesis, Riemannian geometry and the Riemann integral testify to his lasting influence. One of the main novelties of Riemann's approach was the way he replaced algorithmic calculations by conceptual reasoning wherever he could. A leitmotif of his was to find results with as little calculation as possible, fast otme Rechnung. In mathematics as well as in physics, Riemann had one underlying principle: He attempted to understand geometry, analytic functions, and physical phenomena from behavior in infinitely small regions. In physics he aimed at what we now call a unified field theory of matter, electricity, magnetism, and gravity. Hans Freudenthal [1] counts Riemann among the great philosophers. It is worthwhile to look into circumstances which may have contributed to the moulding of this exceptional figure. Riemann spent almost all of the first half of his life in the northeast part of the kingdom of Hanover. 1 At the age of 20 he went to the realm's University at G6ttingen, and from 1847 to 1849 he studied at Berlin. He received his degrees (doctorate, 1851; Habilita tion, 1854) under Gauss (1777-1855) at G6ttingen [2]. Riemann taught there as a Privatdocent and, from 1859, as a Professor ordinarius, though his health forced him to spend much of his last years in the more favorable climate of Italy. He died at Selasca, Lago Maggiore. Riemann was a singular figure among the scholars of his time. Of course, he shared with his North German contemporaries the influences of post-Kantian philosophy and of neohumanistic educational ideals. But we should bear in mind that he was almost 14 when he first entered school, a Lyceum in the city of Hanover. Until then his education had been in the hands of his father, a Lutheran village pastor. Young Riemann must have been influenced by the seclusion of his native country, which he seems to have loved. Even in later years he spent as much time as possible there, where much of his work came into being. One is reminded of Newton, whom
Riemann admired, and of the inspirations that may have come to young Isaac in the loneliness of Woolsthorpe. We invite our readers to join us in exploring the Wendland, Riemann's native country, located between the Elbe River and the city of L6neburg. As public transportation is still very poor throughout the region, we will there from Hamburg by car. Our destinations will be the villages of Breselenz, where Riemann was born in 1826, and Quickborn, where the'family lived from 1833 until the father died in 1855. Finally we shall visit L/ineburg, where Riemann went to the Gymnasium from 1842 to 1846. After a drive of about an hour and a half, following a road close to the river, we enter the Wendland near Hitzacker where the Dukes of Braunschweig-Lfineburg had
1 N o w the S t a t e o f L o w e r S a x o n y in n o r t h w e s t e r n G e r m a n y .
THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3 (~)1995Springer-Verlag New York
37
one of their castles before they m o v e d to Wolfenbiittel, taking their famous library with them. After the catastrophic flood of 1962, a strong dike was built, which permits us a fine first view of the "formerly Wendish Elbe Marshland," as Schering called the region [3, p. 829]. One heritage of the Wendish (i.e., Slavic) tribe that settled here a r o u n d 600 A.D. is the peculiar "roundling" shape of the sparsely distributed hamlets. Their cottages are arranged circularly, each facing the village green, with a church built outside the circle. N o hedges bar our vista of smooth hills and forests to the west, and of the wide landscape w h e r e both fauna and vegetation are m u c h better p r e s e r v e d than in other parts of Germany. 2 Our next stop is Breselenz. After some inquiries as to the Riemanns' former home, w e are directed to Dr. Alfred Kelletat, who was a colleague of the late Herbert Meschkowski of Berlin, well k n o w n to historians of mathematics. We learn that the house of Riemann's birth, on a street which n o w bears his name, has been pulled down. Fortunately Dr. Kelletat has photographs of it in his private archive (see Fig. 1), and most kindly consents to have them published here. On the occasion of Riemann's 150th anniversary Dr. Kelletat arranged for the village to dedicate a stone monu m e n t in the churchyard to the m e m o r y of its famous son (Fig. 2). The church itself u n d e r w e n t some changes around 1870.
Figure 1. Breselenz, house of Riemann's birth. (top) Front. (bottom) Back.
2 Even now the Wendland county (Kreis Liichow-Dannenberg)is by far the most sparsely populated region of Lower Saxony,with only 41 inhabitants per km2 according to the census of 1981. Two sides of the triangle-shaped county were parts of the Iron Curtain.
Figures 2. (left) Churchyard at Breselenz with Riemann memorial. (right)The memorial plaque. 38
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
Figure 3. Street at Quickborn.
We follow the way the Riemanns may have taken in 1833 when they moved to Quickborn, a village closer to the river, where most of the streets are still unpaved and bordered by mighty and very old oak trees (Fig. 3). Farmhouses and cottages are timber-framed, the frames filled in with red bricks, sometimes forming patterns. Strong horizontal beams bear carved inscriptions, many of a pious nature. Quickborn is an exception to the Wendish rule, with the church on a knoll in the middle of the village (Fig. 4). The red brick church goes back to the Middle Ages but was rebuilt during the Baroque era. The nearby vicarage (Fig. 5) is hidden among trees and shrubbery, and it may, though rebuilt in 1866, give us a fairly correct impression of the Riemann home. Quickborn is surrounded by LangendorferGeest, a dry and slightly hilly area, in contrast to the marshland prevailing in the region, and speckled with pieces of farmland and of mixed forests, where brooks meander toward the great riven The Elbe river (Fig. 6) has always been the main waterw a y connecting the North Sea and Hamburg to central Europe. During the 19th century, sailing vessels carried timber and farm products down to Hamburg, and trains of barges returned with coal and industrial articles. We turn westward, seeing watermills which were still working in Riemann's time, in addition to the only windmill of the region, w h i c h - - though jobless n o w - - is preserved at Quickborn. Many houses we pass on our way to L6neburg were built in the early 19th century, and Riemann must have seen them on his frequent marches of about 60 km between home and school. The city of L/ineburg, on the northern border of the famous Heide, has preserved much of its medieval charm, with its patrician gable-walls, churches, and spires representing North German Backsteingotikat its best, red bricks being predominant. North of St. Johannis we find the building, erected in 1829, of the Gymnasium Johanneum, presently housing a school for learning-disabled children
Figure 4. Church at Quickborn, with vicarage in the background.
Figure 5. The vicarage at Quickborn.
Figure 6. Elbe river near Quickborn. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3,1995
39
Figure 7. The former Gymnasium Johanneum at Liineburg.
Figure 8. Building in Liineburg where Riemann lived, 18441846.
(Fig. 7). Its facade has not greatly changed since Riemann w e n t to school here from 1842 to 1846. A few blocks further to the north we almost stumble over an unexpected memorial tablet at No. 18 in the small street Auf dem Kauf (Fig. 8) telling us that Bernhard Riem a n n lived here as a student. 3 We can learn more of Riemann's years at L~ineburg, and about his landlord Seffer, from the new edition of the Collected Works of Riemann [3, pp. 8 4 9 - 853]. When preparing an obituary address after Riemann's death in 1866, Ernst Schering of G6ttingen had collected information from C. Schmalfuss, w h o in the 1840s had been headmaster of the Johanneum, and also from G. H. Seffer, a teacher of H e b r e w and a tutor. Their letters, though composed rather hastily only a few days before Schering had to deliver his address, and possibly influenced by an attitude of de mortuis nil nisi bonum, p r o v i d e us with valuable information. In the case of Riemann, Schmalfuss claims to have been the teacher (who inevitably appears in any b i o g r a p h y of an eminent scholar) w h o recognized the exceptional gifts of the y o u n g man. Schmalfuss encouraged Riemann and o p e n e d his considerable mathematical library to him. As he remembers, "even at that time he [Riemann] was a mathematician beside whose powers a teacher felt poor." At times y o u n g Riemann must have driven his teachers to despair by his extremely meticulous attitude tow a r d writing essays, both in G e r m a n and in Latin. Diligence and conscientiousness apparently were more important to the student than promptness in delivering his homework. This property, which we m a y recognize and even admire in his later writing, appears to have become
a serious obstacle at school, even endangering his Abitur, the prerequisite to matriculation as a university student. Like m a n y teachers of the time, Seffer a u g m e n t e d his small salary by making his h o m e a boarding-house for students. To enforce the regulations of the school, die Schulgesetze, Seffer was commissioned by the Council of Masters to take care of Riemann's homework. He took him into his house (at a reduced rate, as he does not forget to mention), and m a n y a night was spent by the two of them in desperate attempts to complete essays. We m a y think of these tortures when looking at the front of a house which Riemann, then almost 20, must have considered a prison both to his b o d y and to his soul, longing for open country life and spiritual independence. Freedom eventually came at Easter, 1846. Once in G6ttingen, he did not register for theology, as had been his father's hope, but for mathematics.
3 Riemann lived with Seffer from Easter 1844 (and not from 1842,as the inscription says) until Easter 1846. This is confirmed by Seffer in his letter to Schering [3, p. 849]. According to Dr. Reinhardt of the Archives at Lfineburg,the tablet was erected in 1985. In the same year E. Neuenschwander had unearthed new material on Riemann's years at L/ineburg, and it is to be hoped that he will publish it in the near future. 40
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
References 1. H. Freudenthal, Riemann. In: Gillispie (ed.), Dictionary of Scientific Philosophy (1975). 2. See R. Remmert, The Riemann-file Nr. 135 of the Philosophische Fakultdt of the Georgia Augusta at G6ttingen, The Mathematical Intelligencer vol. 15 (1993), no. 3, 44-48. 3. B. Riernann, Collected Papers, R. Narasimhan (ed.) Springer/Teubner (1990). Biography by Dedekind, 573590.
Ahornweg 23 64367 Mf,ihltal Germany
Fachbereich Mathematik Technische Hochschule Darmstadt Schlossgartenstr. 7 6100 Darmstadt Germany
Discovery of a Lost Factoring Machine Jeffrey Shallit, Hugh C. Williams, and Fran(;ois Morain I
Dedicated to the memory of Robert Silber
So said W. Stanley Jevons in 1874, in his book The Principles of Science. Today, trial division on a digital computer can c o m p u t e the factorization
Introduction
Given any two numbers, we may by a simple and infallible process obtain their product, but it is quite another matter when a large number is given to determine its factors. Can the reader say what two numbers multiplied together will produce the number 8,616,460,799? I think it is unlikely that any one but myself will ever know; for they are two large prime numbers, and can only be rediscovered by trying in succession a long series of prime divisors until the right one be fallen upon. [13], p. 141
1On leave fromthe FrenchDepartment of Defense,D616gationG6nerale pour l'Armement.
Jeffrey Shallit
Hugh C. Williams
Fran~;ois Morain
8,616,460,799 = 89681.96079 practically instantaneously.. More advanced methods, including the quadratic-sieve, the elliptic-chrve method, and the number-field sieve, n o w make it possible to factor 100-digit numbers fairly routinely. Just recently, a team consisting of Derek Atkins, Michael Graft, Arjen Lenstra, Paul Leyland, and more than 600 volunteers factored a n u m b e r with 129 decimal digits. These m o d e r n successes, as great as they are, should not take the lustre off early efforts toward integer factorization and primality testing. For example, around 1776,
Jeffrey Shallit is associate professor of computer science at the University of Waterloo. He received his Ph.D. in mathematics from the University of California" at Berkeley in 1983. Prior to his present position, he taught at the University of Chicago and Dartmouth College and was a visith3,g pro~ fessor at the University of Wisconsin and the Universit6 de Bordeaux, FranceL His main research interests are algorithmic number theory and formal languages. In his spare time, he likes to go walking and hiking, especially in the southwestern United States. Hugh C. Williams is a professor of computer science and an associate dean of science at the University of Manitoba, where he has been since 1970. He graduated with a Ph.D. in computer science from the University of Waterloo in 1969. Since that time, his main area of research activity has been the application of computational techniques for solving problems in number theory. This has led him to further interests in special-purpose computing hardware, cryptography, and the history of mathematics. His hobbies include: walking, travel, photography, reading, and drinking. Francois Morain is a 1983 graduate of the ]~coIe Potytechnique in France. He received his doctorate in mathematics from INRIA and the Universit6 de Lyon I in I990. He is ~Ing6nieur Principal de l'Armement. His current position is with the Laboratoire d'Informatique at the ~cole Polytechnique, where he teaches analysis of algorithms and numbertheoretic algorithms. In his spare time, he enjoys watching movies, reading science fiction and history, and gastronomy.
THE MATHEMATICAL [NTELLIGENCER VOL. 17, NO. 3 (~)1995 Springer-Verlag New York
41
C. E H i n d e n b u r g and A. Felkel i n d e p e n d e n t l y invented devices to aid the construction of factor tables, but it is not clear h o w successful they were. Charles Babbage envisioned a machine to construct a table of p r i m e numbers from 0 to 10,000,000, but like his Analytical Engine, this machine was never built. This article tells the story of our search for and eventual discovery of a lost factoring machine, built 75 years ago by a French amateur, Eug6ne Olivier Carissan. This marvelous mechanical device represents the first k n o w n success in automating integer factorization. But before we begin the story, let us first turn to the principles on which this machine was based.
Sieving
i = 1, 2, 3,...~ k) which are usually relatively prime in pairs, . k sets of acceptable residues Ri = {rid I0 <_ rid < ra~ } (i = 1, 2, 3 , . . . , k ) . We are to determine all integers x such that A _< x < B and (x m o d mi) E R~ (i = 1, 2, 3 , . . . , k ) . We call this a sieve problem because the k sets of acceptable residues can be regarded as acting like a succession of kitchen flour sieves, each with a finer mesh than its predecessor. Notice that the well-known sieve of Eratosthenes is an instance of the GSP. In this case, if we denote the ith prime b y Pi and put B = p2 + 1, the problem of finding all primes between A _> 0 and B is that of solving the GSP for m~ = Pi and Ri = {1, 2, 3 , . . . ,Pi 1}, for i = 1 , 2 , 3 . . . . ,k. Consider again the problem of solving (1) and observe the tableau below: -
Here is a simple example. Suppose we wish to factor 611 b y representing it as a difference of two squares; that is, we want to find x and y such that 611
= x2 -
y2 = (x - y)(x
(1)
.-}- y ) .
(We can express any o d d n u m b e r in this way, although it is possible that the representation only gives the trivial factorization.) N o w any perfect square must be one of 0, 1, or 4 modulo 8, and 611 = 3 (mod 8); therefore, we can only have X 2 ~ 4 (mod 8) and y2 _ 1 (mod 8). It follows that x = 2 (mod 4). Similarly, since any perfect square can only be 0 or 1 (mod 3), we find that x = 0 (rood 3). If w e make use of the additional m o d u l i 5 and 7, we find that any perfect square can only be 0, 1, or 4 (mod 5) and 0, 1, 2, or 4 (rood 7). It follows from (1) that we can only have 611 + 0, 1, 4 x2= 611+0,1,2,4 X2 ~
(mod 5), (mod7);
thus, x - 0, 1, or 4 (mod 5) and x - 2, 3, 4, or 5 (mod 7). We are n o w left with the following problem: Find values of x such that 0 _< x < 611 and x x x = x_=
2 0 0, 1, o r 4 2, 3, 4, o r 5
(mod4), (mod3), (modS), (mod7).
For one of these values of x there must exist a y such that (1) holds. Indeed, the least solution to this system is x = 30, and for this value of x we get 611 = 302 - 172 = 13 947, which gives the complete factorization of 611. This problem is an instance of the Generalized Sieving Problem (GSP), in which we are given
1. bounds A, B with B > A, 2. k _> 1 moduli m l , m2, rn3,... ,rrtk (mi 42
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
>
1,
-
x
0 1 2 3 4 5 6 7 8 9 10 11 1 2 - - . 3 0
(xmod4)
x x x/ x x x v/ x x x x/ x x ... v /
(xmod3)
x/x
(xmod5)
x/v/X
(xmod7)
x x ~/v/ x/v/ x x x x/v / v/x/--.v
x v/X x v/x
x x/x
x x/ " " v /
x ~/ ~/ v/ x x ~ / x / v/ x . . . v / /
For each of the moduli 4, 3, 5, and 7 we have placed a check m a r k (x/) u n d e r each acceptable value of x and a cross (x) u n d e r the others. W h e n we arrive at a value of x above a column consisting only of check marks, that value of x is a solution to our sieving problem. The difficulty with this approach, of course, is that we might have to go a very long way in o u r search for x before w e find a solution, especially if k is large. We can solve this problem b y first noticing that each row of the tableau exhibits a cyclic pattern of check marks and crosses, information that can be compressed by the simple expedient of recording these patterns only once. A n y column of the original table can be generated b y shifting each of the rows to the left in order to advance the appropriate set of symbols to the first column, the leftmost symbol wrapping a r o u n d to the rightmost. In general, column t will appear in the first column after t of these shift operations have been performed. To u n d e r s t a n d how one might construct a machine to perform these sieving operations, imagine each m o d u l u s mi represented by a loop or ring which is divided into mi positions. Those positions that represent acceptable residues are tagged in some manner, and the machine examines one position from each ring at a fixed location called a window. The rings are advanced in unison, a solution being detected w h e n the w i n d o w is filled exclusively with tags. A trial counter records the n u m b e r of shifts p e r f o r m e d by the machine. Thus, the device can be set u p to start searching from some point N by setting the ith ring such that N (mod mi) is in the w i n d o w w h e n the
mechanism is turned on; after s shifts, the residue being Sphinx-Oedipe, also became involved in constructing a tested is N + s. A device of this type is called a number number sieve in 1912. His device, constructed by his sieve or frequently just a sieve. brother Eug6ne, is mentioned by G4rardin [9] and again It seems that the British mathematician Frederick in passing in [12], but it is only in [2] that we are given William Lawrence [14] im1896 was the first person to any information about it. We are simply informed that it advocate building an automatic sieving device to factor was made up of hanging flexible modular loops (rings) integers. He presented a number of details on how such a which were driven simultaneously by a grooved roller machine might be built, but he did not actually construct and scanned for solutions by eye. It seems that this device one. was not very effective. Lawrence's idea was forgotten until 1910, when Andr6 All three of these early attempts to construct a sieve G6rardin published a French translation of Lawrence's suffered from the same inadequacies: they existed only as article in his unusual monthly mathematical review, roughly constructed prototypes, were rather inefficient, Sphinx-Oedipe. This article seems to have inspired the required the human eye to scan for solutions, and proRussian engineer Maurice Kraitchik to construct a model duced no significant results--apparently none whatsoof a sieve device early in 1912. The machine, made of ever. wood according to G6rardin [9], was composed of 15 ring gears with differing numbers of teeth representing T h e C a r i s s a n M a c h i n e the primes from 2 to 47. These gears were mounted on a single common shaft S' but could turn freely about this In 1913-1914, E.-O. Carissan, who at that time was a lieushaft. A second group of 15 driving gears were mounted tenant in the French infantry, began his development of on a second shaft S and fixed on that shaft. The sum a second automatic nu'merical sieving device [2]. This of the radius of each driving gear and its corresponding work had to be suspended with the outbreak of World ring gear was fixed at 200 mm. The two shafts could be War I and was not completed until 1919. "The resulting arranged in parallel with the gears on shaft S engaging machine, called the machine ~ congruences, was a precithose on shaft S'. Further, the radii of the gears were also sion device constructed by the award-winning firm of determined in such a way that all the ring gears turned Chateau Fr6res (at that time located at 125, Boulevard de at the same rate when the shaft S was rotated. Grenelle, Paris). Its dimensions were 27 cm x 33 cm x A numbered hole was placed a fixed distance (60 mm) 12 cm. from the centre of the ring gear beneath each tooth on This machine made use of 14 congruence rings, which that gear. For a given sieve problem the holes corre- were in fact circular rings made of brass. The ring corsponding to unacceptable residues for each modulus responding to modulus m had 2-mm gear teeth cut in were plugged. A light source was placed in a fixed posi- its underside and ra equally spaced steel studs screwed tion near one end of the shaft S' and a screen at the other. into its topside. The values of the moduli were fixed at As shaft S rotated, the occurrence of a solution would be 19, 21 = 3.7, 23, 26 = 2.13, 29, 31, 34 = 2.17, 37, 41, 43, 47, indicated when a set of unplugged holes on the 15 gears 53, 55 = 5.11, and 59. Thus, the first 17 odd primes could lined up, causing a spot of light to appear on the screen. be used as sieve moduli, and in principle, the machine Although this mechanism might have worked reason- could handle problems modulo ably well at low speeds, it would very likely have been useless at higher speeds because of meshing problems H p = 19, 22760, 35015, 42126, 39070, caused by the different sizes of the gear teeth. 2_(1o(--59 p prime In 1912, G6rardin [9] also announced that he had built a sieve. Unfortunately, his article [10] is rather sketchy, but a second article [11] provides a few more details on its design. Apparently, this mechanism consisted of an unspecified number of paper strips, each representing a ring for some modulus. A strip corresponding to modulus m was marked off in a multiple of m spaces of fixed size. These spaces were coloured white or black according to whether the residue represented by the space was acceptable or not. A solution to a sieve problem, which required several of these scrips, would be indicated by a completely white column. The strips were set up to be almost of equal length, usually about 3 m, and were wound up between two identical rollers while an operator checked for a blank column. Figure 1. The "machine ~ congruences," showing the rollers Now enter the main characters of our story: Pierre and on which the congruence rings were mounted. (Photo courEug6ne Olivier Carissan. Pierre, another contributor to tesy of H. C. Williams.) THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
43
Figure 2. The "machine/I congruences," with 10 of the 14 congruence tings in place. (Photo courtesy of H. C. Williams.)
circle and parallel to their plane of rotation, engaged the teeth on their undersides. This pinion gear was driven by a hand-turned flywheel. A six-digit counter was also connected by gears to the pinion gear (see Fig. 2). To run a sieve problem, a nonconducting cap was placed on every stud that corresponds to an acceptable residue for each modulus m. If the sieve was to begin searching at N, the rings were mounted such that the studs representing the value of N (mod m) were placed on a fixed radius of the ring circle called the investigation line. An armature, containing 14 spring-loaded contact switches arranged along a straight line, was mounted above the rings directly along the investigation line (see Fig. 3). Because the capped studs representing the acceptable residues on a given ring would be somewhat longer than the others, they would press on the contact switch for that ring when passing under the armature. The 14 switches were connected in series so that if all the residues under the investigation line were acceptable, an electrical circuit would be completed, causing a telephonic sound to be made in a headset worn by the operator who was also turning the flywheel by means of a crank. When the operator heard this sound, he would carefully stop cranking, then slowly crank in the opposite direction until he heard the sound once again. He could then read off a number from the counter, which, when added to N, forms a solution to the sieve problem. This remarkable, beautifully engineered device was displayed at the Exposition Publique de Machines h Calculer in Paris, 5-13 June 1920, under the auspices of the Soci6t6 d'Encouragement pour l'Industrie Nationale [2]. It could canvass numbers at the rate of 35- 40 per second when the operator turned the flywheel at the appropriate rate of 2 rotations per second. The effectiveness of this instrument was illustrated by applying it to several (noncooked) problems. For example, the number 708,158,977 was proved prime (see also P. Carissan [5]) by showing that it could be represented as the sum of two squares in only one way, 708,158,977 = 19,2242 + 18,4012;
Figure 3. The "machine ~ congruences," s h o w i n g the armature with spring-loaded contact switches. The counter is at upper left, and the hand crank is at lower left. (Photo courtesy of H. C. Williams.)
a number of 22 decimal digits. The studs for each ring were numbered 1, 2, 3. . . . . ra, with the area of the ring containing the stud m painted in red. The rings were mounted concentrically, and could rotate within the same plane by being supported by three radial tracks of rollers in one plane, separated by 120 ~ angles. In order to reduce the effects of friction and chatter, these rollers were very narrow and engaged the rings in tracks on their outside edges (see Fig. 1). A pinion gear, placed under the plane of the rings, along a radius of their 44 THE MATHEMATICAL[NTELLIGENCERVOL. 17, NO. 3, 1995
this representation required 10 min of sieve time to compute. Carissan was also able to prove the primality of 231 - 1 by finding in 15 min of sieve time that it could be represented in only one way as 4x 2 q- 3y2 with gcd(x, y) = 1: x = 23081, y = 2349. Eugene was even able [3] to factor the 13-digit number 2?23, the 23rd value of x satisfying the Pellian equation X 2 - - 3y2 = 1; that i s , 2X23 = ( 2 q- V ~ ) 23 q- ( 2 -- V~) 23. He found in 18 rain that x23/2 could be represented as a sum of two squares in two different ways. From these representations it was easy to find the partial factorization .r23 = 7, 141,075,053,842 = 2 9841,249.4,244,329. (Actually, 841,249 = 277- 3037, but this was apparently not noticed by Carissan.)
Eugbne Carissan had plans for upgrading his machine; in fact, in an unpublished manuscript [3] he mentioned four different possible improvements that might be made to it. One of these ideas, also mentioned in [2] and attributed by d'Ocagne ([7L p. 136; [8]) to a certain M. Carpentier, was to attach a small electric motor to drive the machine instead of driving it by hand. Also, the motor could be wired to the solution-detecting armature in such a way that when a solution occurred, the motor would shut itself off. Carissan stated that this particular improvement was under study in 1920, but it seems that no further work was ever done.
T h e H u n t for the M a c h i n e We learned of the existence of the Carissan machine serendipitously when one of us (Shallit) came across the article [2] while on sabbatical at the University of Wisconsin in the fall of 1989. Soon we were engaged in an active search for its whereabouts in France. We looked for clues at the Conservatoire National des Arts et M6tiers (CNAM), the l~cole Normale Superieure, the Institut Henri PoincarG and the Biblioth6que Nationale (BN), without success. We also were unable to contact the company that built the machine, Maison Chateau Frbres- they had apparently gone out of business. When a year of intermittent searching failed, we resorted to what seemed at the time a preposterous idea: we would write a letter to each person named Carissan in France and ask for leads. But how to find all the Carissans? Luckily for us, France Telecom provides a computerized database of telephone numbers via the Minitel, a small terminal provided free of charge to Telecom subscribers. (In many respects, France leads the world in access to the so-called "information highway.") With the assistance of Jean-Paul Allouche of the CNRS, we searched each d6partement in France for the names and addresses of people with the Carissan surname. Our computer search produced 85 names and addresses. With much hope but few expectations, we sent off a letter in the summer of 1991 to all of the 85 listed Carissans, asking if they knew of the machine, or if they might possibly be related to the Carissans who invented it. Not long afterwards, we were surprised when one of us (Morain) received a phone call from Marie-Josbphe Salefran-Carissan, an inhabitant of Pau, and a daughter of Eug6ne Carissan. (Luck was with us, as Mme. SalefranCarissan had just recently hyphenated her name to restore the "Carissan".) We learned with great excitement that the machine still existed and was being stored near Bordeaux. Apparently it had remained in the possession of the family until about 1940, when Jean Dubois, an astronomer and friend of one of Eug6ne Carissan's daughters, arranged for the machine to be transferred to the Observatory in Floirac, near Bordeaux. There it stayed,
stored in a dusty drawer, until March 1992, when one of us (Morain) visited it as a guest of Michel Rousseau, another astronomer at the Observatory. The machine was still in good shape, and Morain was able to program up a small sample problem. The machine has since been donated to the CNAM in Paris, where it was installed in June of 1994.
Lives of the Carissans In September 1991, Morain received a phone call from another daughter of Eug6ne, France Silber, who lives in Grenoble. She gave us the full name of her father, Eug6ne Olivier Carissan, and told us that he served in the 71 eme ROgiment d'Infanterie during World War I. With this clue, we were able to obtain Eug6ne's military record from the Service Historique of the French army. Mme. Silber also provided the photograph of Eug6ne given in Figure 4. Later, having read in [2] that Pierre Carissan taught at one time at the Collbge de Lesneven, we examined the files of the Archives l'qationales in Paris and were fortunate to discover a dossier on his teaching career [1]. This eventually led one of us (Shallit) to the small town of Cond6-sur-Noireau in Normandy, where we obtained what may well be a photograph of Pierre Carissan (see Fig. 5). From these and other resources, we were able to piece together a reasonably complete biography of Pierre and Eug6ne Carissan: Pierre-Eug6ne-Georges Carissan and Eug6ne Olivier Carissan were two of five children born to Eug6ne Pierre Vincent Carissan (b. 6 July 1830; d. 12 October 1883) and Am61ie C16mence Eulalie de Dieudonn6. Their father
Figure 4. Eug6ne OIivier Carissan (1880-1925). Inventor of the "machine ~ congruences." (Photo courtesy of France Silber.) THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
45
Figure 5. Faculty and students at
the
Coll~ge
Dumont
d'Urville, Cond4-sur-Noireau, France, circa 1920. Pierre Carissan is probably the man indicated by the white circle. (Photo courtesy of Jean-Pierre Lafontaine.)
was a native of Nantes who taught history and geography in Nantes, Angoul~me, and Nancy. Their grandfather, Honor6 Eug6ne Carissan, was a justice of the peace in Nantes. Pierre was born on 15 April 1871 in AngoulOme. He received the licenci6-6s-sciences math6matiques degree (similar to a North American MS degree) from the Facult6 des Sciences de Rennes in July 1896. In the following years, Pierre held a succession of teaching jobs at a total of 16 different schools, including positions at Rennes, Angers, Paris, Versaille, Reims, Nancy, and Caen. Pierre had an unusual personality and was remembered as an "original fini" by his niece, France Silber. During Pierre's brief tenure at the Coll6ge de Lesneyen (from October 1911 to September 1912), he organized an integer-factoring contest for students aged 1315. This contest was held in July 1912. Using the methods of G6rardin, the students factored numbers of six or seven decimal digits in "a matter of minutes" [12]. Pierre was a frequent contributor to G6rardin's journal, SphinxOedipe;for example, see [6]. He also contributed to other mathematical journals; in [4] he described a mechanical device for drawing logarithmic spirals. In December 1914, Pierre was appointed to the position of professeur de math6matiques at the Coll6ge Dumontd'Urville, in Cond6-sur-Noireau, a small town near Caen in northern France. He died there on 7 April 1923. Pierre's younger brother, Eug6ne, was born 26 November 1880 in Nantes. He attended the t~cole Sp6ciale Militaire beginning in October 1900, and graduated with rank of sous lieutenant on I October 1902. On 1 October 1904 he was promoted to lieutenant. On 29 December 1904, he married Marie Emilie Brun at St.-Brieuc. They would have four children. Eug6ne was mobilized on 2 August 1914, five days after the beginning of World War I. On 28 August 1914, he was gravely wounded in the shoulder in the battle of St.Richaumont. He was evacuated and later promoted to capitaine. He returned to the front on 6 October 1914. He 46
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
was wounded again, this time in the head by a shell, on 15 July 1915, but refused to be evacuated and continued to command his troops. He became chef de bataillon on 22 August 1916. He was wounded for a third time at Mont Cornillet on 30 April 1917. Eug6ne received the Chevalier de la L6gion d'Honneur on 14 August 1915, and became Officier de la L6gion d'Honneur on 13 April 1921. A contemporary military account describes him: "officier d'une intelligence d'61ite, d'un courage hors ligne; toujours pr~t a se donner corps et ame." At the conclusion of World War I, Eugbne became a professor at the Ecole Militaire de St. Maixent. In October 1922, he was chosen to attend a course at the t~cole Sup6rieur d'l~lectricit6. He then continued his studies at an arms manufacturer in Chatellerault. His first wife, Marie Brun, died about this time. Eug6ne remarried in Paris on 24 October 1923 to Yvonne Louise L6onie Humbert. They had one child. Eug6ne died at the military hospital in Val de Grace on 25 April 1925. He is buried in the Mis6ricorde Cemetery, rue Pelleterie, in Nantes. Conclusions
Despite the importance of the work of Eug6ne Carissan and the remarkable machine he built, very few people were aware of his work. Perhaps this was because both Pierre and Eug6ne died within 5 years of the exhibition of the machine in Paris in 1920. Indeed, when D. H. Lehmer began to construct his first automatic sieve in 1926, he had never heard of Carissan's sieve, and he remained ignorant of it until 1989. Lehmer's 1926 sieve, which was in some ways much less sophisticated than Carissan's, made use of bicycle chains driven by an electric motor. It was his first attempt of many. Each time he built a new sieve, the most advanced technology was used: photoelectric cells in 1932, 16-mm movie film in 1936, and delay lines in 1965 for the DLS-127 (later DLS-157). For an account of all of this, see [18].
One could be led to think that sieves are old-fashioned and outclassed by m o d e r n computers. As a matter of fact, sieve methods remained the fastest k n o w n m e t h o d for factoring integers u p to 1970. Sieve devices are still m u c h faster than currenP software programs. For instance, Williams, et al. (see [16] and [18]) have constructed devices that can p e r f o r m u p to 2 x 1012 trials per second, c o m p a r e d to 2,000,000 on a workstation. M o d e r n sieve devices are no longer used for factoring purposes, because an approach based on more sophisticated mathematical ideas and massive distribution of programs on workstations is m u c h more powerful (see [15]). We should also point out that another specialp u r p o s e factoring machine, which was not a sieve, was constructed by Smith and Wagstaff [17] in 1983. However, for other special problems, sieve devices still seem to be the only way. For example, Stephens and Williams [18] used their device to find pseudosquares, n u m b e r s that behave like squares m o d u l o m a n y small primes. This study could eventually lead to a v e r y fast primality-proving algorithm, if some highly plausible (yet hard) conjecture in n u m b e r theory were true. Although sieve machines are not used to factor integers anymore, the basic principle of sieving remains at the heart of the m o d e r n factoring methods such as the quadratic sieve m e t h o d or the n u m b e r field sieve algorithm. Thus sieving, which was k n o w n to Euclid, is still a powerful m e t h o d used in e v e r y d a y life of numbertheorists.
Acknowledgments We are pleased to acknowledge the m a n y people w h o aided us in our search. In particular, we are most grateful to Marie-Jos6phe Salefran-Carissan, w h o first told us that the machine still existed; and to France Silber and the late Robert Silber for welcoming us into their home, answering our frequent questions, and providing valuable information about the machine and its inventor. We thank Michel Rousseau of the Observatoire de Floirac for having been host to o u r examination of the machine on three separate occasions. We also are very grateful to Jean-Pierre Lafontaine, w h o provided the p h o t o g r a p h in Figure 5. The first and second authors w o u l d like to thank Michel Mend6s France and Jean-Paul Allouche for their assistance in obtaining French documents. The first author would like to thank Marie-Annick H e p p of the Service Historique of the French Department of Defense for her assistance in providing the military records of Eug6ne Olivier Carissan. Finally, we all wish to thank Louis Andr6 of the CNAM, w h o was responsible for acquiring the Carissan machine for the p e r m a n e n t collection of the CNAM. Jeffrey Shallit and H u g h C. Williams were s u p p o r t e d in part by NSERC Canada.
References 1. Archives Nationales, Carton F/17/25723 (Instruction Public), containing items on Pierre-Eug6ne-Georges Carissan; Paris, France. 2. E. Carissan, Machine a r6soudre les congruences, Bull. Soc. Encouragement Ind. Nat. 132 (1920), 600--607. 3. E. Carissan, Principe m6canique et description de la machine du Ct. E. Carissan. Unpublished manuscript (1920). 4. P. Carissan, Description m4canique de la spirale logarithmique, Nouv. Ann. Math. 17 (1917), 273-277. 5. P. Carissan, R6ponse 511, Sphinx-Oedipe 15 (1920), 43--46. 6. P. Carissan, Le tonneau des Danaides, Sphinx-Oedipe 18 (1923), 73-75. 7. M. d'Ocagne, Vue d'ensemble sur les machines a calculer, Bull. Sci. Math. 46 (1922), 102-144. 8. M. d'Ocagne, Le Calcul Simplifid par les ProcdddsMdcaniques et Graphiques, Paris: Gauthier Villars (1928). [English translation in J. Howlett and M. R. Williams, eds., Le Calcul Simplifid: Graphical and Mechanical Methods for Simplifying Calculation, Cambridge, MA: MIT Press (1986).] 9. A G6rardin, Question et r6ponse 355, Sphinx-Oedipe 7 (1912), 47-48, 61-64; also see p. 31. 10. A. G6rardin, RapporF'sur diverses m6thodes de solutions employ6es en th4orie pour la decomposition des nombres en facteurs, Assoc. Franqaise Avan. Sci. Cornptes Rendus 41 (1912), 54-57, IV partie. 11. A. G6rardin, Sur une nouvelle machine alg6brique, Br. Assoc. Reports 82 (1912), 405-406. 12. A. G6rardin, Sur quelques nouvelles machines alg6briques, Proc. 5th International Congress of Mathematicians, Vol. II (E. W. Hobson and A. E. H. Love, eds.), Cambridge UK: Cambridge University Press (1913), 572-573. 13. W.S. Jevons, The Principlesof Science: A Treatiseon Logic and Scientific Method, Vol. I. London: Macmillan and Co. (1874). 14. E W. Lawrence, Factorisation of numbers. Quart. J. Pure Appl. Math. 28 (1896), 285-311. [French translation in Sphinx-Oedipe 5 (1910), 98-121.] 15. A.K. Lenstra and Mark S. Manasse, Factoring by electronic mail, Advances in Cryptology (J.-J. Quisquater, ed.), New York: Springer-Verlag (1990). 16. R. E Lukes, C. D. Patterson, and H. C. Williams, Numerical sieving devices: their history and some applications, Nieuw Archief voor Wiskunde (in press). 17. J. W. Smith and S. S. Wagstaff, Jr., An extended precision operand computer, Proc. 21st Southeast Region ACM Conference (1983), 209-216. 18. A. J. Stephens and H. C. Williams, An open architecture number sieve, Number theoryand cryptography (J. H. Loxton, ed.), Cambridge UK: Cambridge University Press (1990), 38-75. Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1 Canada e-maih
[email protected]
Department of Computer Science University of Manitoba Winnipeg, Manitoba R3T 2N2 Canada e-maih
[email protected] Ecole Polytechnique F-91128 Palaiseau France e-maih
[email protected] THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
47
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.
Further Travels with My Ant David Gale, Jim Propp, Scott Sutherland, and Serge Troubetzkoy
Introduction A recurring theme of this column over the past 4 years has been what w e have referred to as computergenerated mysteries. Examples are sequences defined b y simple rational recursions whose terms turn out to be integers with interesting but unexplained divisibility properties, or geometric configurations that are observed to exist although there are no proofs of existence. In most of the examples, the reported mysteries have remained unsolved and in some cases may in fact be, in a suitable sense, "unsolvable." It is therefore gratifying to be able to present in this m o n t h ' s column an elegant solution of a previously described mystery. An especially pleasing feature of this solution is that the "breakthrough" was m a d e possible by d r a w i n g the right picture. Once the picture is drawn, it becomes clear what must be proved, after which further s t u d y of the pictures gives the clue as to how to construct the proof. It turns out that at one point one needs to use the Jordan curve theorem for a special class of closed curves. In the paragraphs to follow, we shall present an informal but we hope convincing argument which will require little more of the reader than the careful observation of a collection of pictures.
The Story So Far and the Mystery We shall be concerned once again with a certain automaton that has been called an ant. An ant lives in a * C o l u m n editor's address: Department of M a t h e m a t i c s , U n i v e r s i t y of C a l i f o r n i a , Berkeley, C A 94720 USA.
plane that has been partitioned in the standard way into squares or, as we shall call them, cells (think of the corners of the cells as the lattice points of the plane). Each cell can be in one of several states, and the respective states of these cells change over the course of time as the cells are in turn visited by the ant. Before we explain precisely h o w the ant interacts with its surroundings, it will help to consider a specific example. In the simplest nontrivial version of the ant, originally studied by Chris Langton, there are just two states, which we will call L (for left) and R (for right). We think of the ant as starting on the b o u n d a r y between two cells, heading in one of the four cardinal compass directions (east or west on the vertical boundaries, and north or south on the horizontal ones). As the ant advances through the cell, it makes a 90 ~ turn, turning left in L-cells and right in R-cells, and m o v e s to the b o u n d a r y of the neighboring cell. As the ant leaves each cell, it changes the state of the cell, switching L-cells to R-cells, and vice versa. For an informal discussion of this ant see [1], where a n u m b e r of interesting ant behaviors are observed. For our present purposes we note only the following still unexplained phenomenon: If initially all cells were in the same state, then at various times the ant's "track" (the set of cells it has visited, together with their current states) is centrally symmetric, that is, the configuration of L- and R-cells has central symmetry. We reproduce here, in Figure 1, the corresponding pictures, where the R-cells are black and the L-cells white; all cells were initially in the L-state, and the ant started out heading west on the right b o u n d a r y of the central cell, and about to enter it. These central symmetries stop occurring eventually, and after about 10,000 time-units, the ant settles into a periodic "highway-building" behavior, heading off to infinity in a southwesterly direction. This p h e n o m e n o n of "transient s y m m e t r y " awaits a satisfying explanation. In our next episode [2], Jim P r o p p describes the behavior of the more general n-state ants. There are n o w n different states for cells to be in, numbered 1 through n, and it is the ant's internal " p r o g r a m m i n g " that tells it which states to treat as L's and which states to treat
48 THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3 Q 1995Sprmger-Verlag New York
Figure 1. The universe of ant 2 at times 184, 368, and 472.
as R's in choosing which w a y to turn. We represent this p r o g r a m m i n g by means of a rule-string, a string of n Us and R's whose kth letter represents the ant's course of action when it comes to a cell in state k; for instance, the seven-state string LLRRRLR represents an ant that turns left on visiting cells in states 1, 2, and 6 and turns right on visiting cells in states 3, 4, 5, and 7. When an ant comes to an L-cell (a cell in an L-state), it turns left; w h e n it comes to an R-cell, it turns right. When the ant leaves a cell that is in state i, the cell changes to state i + 1 (mod n). In this terminology the simple ant has the rule-string LR. From s y m m e t r y considerations it clearly suffices to consider only strings that start with an L. If in the rulestring we replace an L b y a 1 and an R by 0, we see that each ant corresponds to a positive integer expressed in base 2, so the simple ant is ant 2 and o u r sevenFigure 2. The universe of ant 12 at time 16,464. state ant with "genome" LLRRRLR is ant 98. P r o p p finds that different ants behave very differently d e p e n d i n g on their rule-strings. Some seem to be completely chaotic, whereas others eventually build highways. The only general statement that can be made is the following: FUNDAMENTAL
THEOREM
OF M Y R M E C O L O G Y
(Bunimovich-Troubetzkoy). An ant's track is always unbounded, provided its rule-string contains at least one L and one R. (For a proof see [1]. Note that the attribution given there is incorrect; the proof actually first appeared in [3].) In this exposition we concentrate on the p h e n o m e n o n described by Propp as follows. Ants 9 and 12 [LRRL and LLRR in our notation] are the truly surprising ones [among ants with rule-strings of length 4]. In each case the patterns get ever larger, but without ever getting too far away from bilateral symmetry! More specifically, one finds that the ant makes frequent visits to the cell it started from, and when it doOs, the total configuration quite Figure 3. The universe of ant 9 at time 38,836. often has bilateral symmetry. Figures 2 and 3, r e p r o d u c e d from [2], show the track of ant 12 after 16,464 steps and the track of ant 9 after 36,836 steps. The figures use black, white, and two shades of gray to indicate the four different states. Propp continues, "To find more ants of this sort we have to m o v e to rule
strings of length 6. Here we encounter another mystery: the rule strings that lead to bilaterally symmetric patterns are 33, 39, 48, 51, and 60. Note that all these numbers are divisible by three! Surely this cannot be an accident." Indeed it is not, as we will presently show. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
49
Figure 4. H-cells in L and R orientation.
Figure 5. V-cells in L and R orientation.
Figure 6. The initial configuration. Truchet Tiles
First a preliminary observation. Since an ant turns through a right angle after each move, it follows that its m o v e s are alternately horizontal and vertical. Therefore, the cells of the plane split u p checkerboard-fashion into two sets: H-cells, which the ant always enters horizontally, from the left or the right, and exits vertically, either at the top or the bottom; a n d V-cells, which the ant always enters vertically and exits horizontally. Now, a crucial p r o p e r t y of a cell is that it is able to change its state and thus change the course of action (left turn versus right turn) that the ant will take after its next visit to the cell. The key idea for representing this property, due to Bernd R/immler, was to actually install schematic "switches" in the cells, in which the orientation of the
Figure 7. The universe of ant 2 at times 184 (top left), 368 (left), and 472 (fight).
50 THEMATHEMATICAL INTELLIGENCER VOL.17,NO.3, 1995
switch indicates whether the cell is currently an L-state or an R-state. These switches are called Truchet tiles and are illustrated in Figure 4, which shows an H-tile first in its L orientation and then in its R orientation, and Figure 5, which shows the same thing for a V-tile. (An "H-tile" is the Truchet tile associated with an H-cell, and similarly for V-tiles.) Note that switching orientation corresponds to reflecting the tile about either its vertical or horizontal axis. Figure 6 shows the plane paved with Truchet tiles, all of which have the L orientation, giving a pattern of disjoint circles: the "initial configuration." As the ant moves, some of the tiles will switch in accordance with the given rule-string, but it is clear that the pattern will always be made up of a set of disjoint simple closed curves which we shall call Truchet contours. (Infinite contours cannot arise, since at each stage the ant has only switched finitely many of the tiles.) It will be helpful (at least for now) to imagine that the ant actually travels along the Truchet curves themselves, rather than along a lattice-path join-
ing the centers of the cells, and that the ant's initial position is the midpoint of one of the edges of the central Truchet tile. Figure 7 gives the "Truchet pictures" corresponding to the (transiently) centrally symmetric configurations of the simple ant given by Figure 1, whereas Figures 8 and 9 give Truchet pictures corresponding to Figures 2 and 3, and manifest the same bilateral symmetry. In all of these pictures the ant has returned to its original location, and of particular interest is the Truchet contour through this point, which we will call the principal contour. Initially, the principal contour is just a circle as are all other contours. In Figure 9 the principal contour has been highlighted. N o w if one knew that each time the ant left its starting location it would stay on the principal contour until it returned once more to its starting location, then it would follow that when the ant had completed its tour, all the symmetries of the initial state of the universe would be preserved; for whenever a cell was visited, its symmetric mate would also be visited.
Figure 8. The universe of ant 12 at time 16,464. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
51
Figure 9. The universe of ant 9 at time 38,836. The principal contour has been highlighted.
Unfortunately, an ant will not, in general, stay on the principal contour, because (as in Fig. 10) the contour may pass through some cells twice. This means that when the
ant returns to such a cell, the orientation of that cell may have switched (indeed this will always be the case for the simple ant studied by Langton), causing the ant to leave the principal contour. However, for the ants listed by Propp one can show that, in fact, The cells that are visited twice by a contour never switch on the first visit.
Figure 10. Switching: the universe of ant 2 at times 4 and 5. 52
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
(1)
This implies that the ant will engage in a process of repeatedly tracing out bilaterally symmetric principal contours, resulting in a bilaterally symmetric universe each time the ant returns to its starting point. Property (1) was first proved by R/immler for ant 12 and then generalized to the other ants by Troubetzkoy. The argument to follow is a reworking by Propp of those proofs.
T h e Even Run-Length Property and the A u g m e n t e d Picture Why do some ant tracks exhibit recurrent bilateral symmetry and others not? Here~are the rule-strings for the 4and 6-state ants of Propp's article that exhibit recurrent symmetry. Ant 9 12 33 39 48 51 57 60
Rule-string LRRL LLRR LRRRRL LRRLLL LLRRRR LLRRLL LLLRRL LLLLRR
It is not hard to see what these strings have in common. If we think of them as arranged in cyclic rather than linear order, then each of them consists of an even num-
ber of Us followed by an even number of R's. In general, we say a rule-string has the even run-length property if in the cyclic order it consists of alternate runs of Us and R's of even length, for example, LRRLLRRRRL. For simplicity in what follows we will consider only the case where the string starts with an even number of Us (ants 12, 48, 51, and 60), the argument for the other case being similar. Why does the even run-length property imply recurrence of bilateral symmetry? Here Riimmler has augmented the picture in a manner that can be paraphrased as follows. Let us say that a cell is cold if its state is odd, so that it will not change orientation the next time it is visited (because of the even run-length property), and hot if its state is even, so that it may or may not change orientation the next time it is visited. To complete the picture we make the convention that for hot cells we display not only the Truchet tile but also its diagonal. The diagonals graph is the graph whose edges consist of the diagonals of the hot tiles. Figures 11 and 12 show the diagonals graph of ants 12 and 48 associated with certain
Figure 11. The universe of ant 12 at its first four symmetric returns to home: 4, 8, 28, and 32. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3,1995
53
Figure 12. The diagonals graph of ant 48 at time 7016.
instants in time at which the ant has returned to its initial location (hereafter called "home"). Note that these graphs can be quite complicated, breaking u p into m a n y components as s h o w n in Figure 12. However, observe a key fact, which we call the even diagonals-degree property:
All vertices in the diagonals graph have even degree (thus, degree 0, 2, or 4).
(2)
L E M M A 1. Suppose that the ant is at its home position and that the state of the universe satisfies (2). Then the ant will
travel along the principal contour (and return home). Proof. As was remarked earlier, the only thing we have to w o r r y about is that the principal contour C might visit a cell twice and that this cell might change its orientation after the ant's first visit. If the twice-visited cell is cold, 54
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
then the Truchet tile will not change its orientation after the ant's first visit. What about twice-visited cells that are hot? We will show that such cells do not exist, as a consequence of (2). Let T be such a cell, and let d be the diagonal of T connecting vertices u and v. CLAIM. If d is deleted, then in the resulting graph the components of u and v are disjoint. If we can show this, then the desired contradiction follows, since from (2) the c o m p o n e n t of u (or v) w o u l d contain only one vertex of odd degree, contradicting the well-known fact (usually associated with Euler) that a connected g r a p h must always have an even n u m b e r of vertices of o d d degree. (This is sometimes referred to as the h a n d s h a k e theorem, in that it says that the n u m b e r of
p e o p l e w h o have shaken hands an o d d n u m b e r of times is even.) It remains to prove the claim. For this purpose consider the twice-visited tile T and its two arcs (quarter circles). Without loss of generality, w e assume that T is an H-tile. N o w color in red the arc in T below the diagonal and, in addition, all succeeding arcs of C u p to the point w h e r e C is about to reenter T. Color the remaining arcs blue. The d o t t e d arcs in Figures 13(a) and 14(a) represent the red arcs and the solid arcs represent the blue. N o w consider the same picture except that the diagonal of T has been deleted and T has switched to its other orientation, as s h o w n in Figures 13(b) a n d 14(b); as before, the arc in T below the diagonal should be colored red and the other arc blue. One sees at once that C has split into two contours: one all red, the other all blue (this m u c h is a purely combinatorial fact and has nothing to do with the topolo g y of the plane). N o w the Jordan curve theorem tells us that each of these nonintersecting contours has an inside and an outside, which can be arranged either as in Figure 13(b) (the non-nested case) or as in Figure 14(b) (the nested case). In either case it is clear that the c o m p o n e n t s of u and v are disjoint, since both the red contour and blue contour intervene. Combining this with the handshake theorem completes the proof.
Remark. Although these last observations can be m a d e rigorous without using the full force of the Jordan curve theorem, there must be some use of the topology of the plane, for the analogue of Lemma 1 is not true on the torus. Finally, we must prove (2). L E M M A 2. If (2) holds when the ant is at home, it will still hold after the ant has toured the principal contour and returned home.
Proof. Let L' be some vertex of the diagonals graph. The neighborhood, N(v), consists of the four cells having v as a vertex. We will show that if at some point the Truchet contour enters and then leaves N(v), the parity of the degree of v is not changed. Case I. The contour meets N(v) in only one cell. Then v does not lie on a diagonal of that cell. If the cell is cold, the situation remains the same, since cold cells d o not
Figure 13. The Non-Nested Case. (a) before; (b) after.
Figure 14. The Nested Case. (a) before; (b) after.
switch; if it is hot, then it becomes cold, hence has no solid diagonal; so, whether it switches or not, the degree of v is unchanged. Case II. The contour meets more than one cell of N(v). Then let E be the cell where it enters and E I the cell where it exits. If E is hot, then its diagonal is incident on v, so w h e n it becomes cold, this diagonal disappears (whether E switches or not); if it is cold, it becomes hot (without switching), so a new solid diagonal will be incident on v. The exact same argument applies to E', so the net effect of the two changes is to preserve the parity of the degree of v (see Fig. 15). As for intermediate cells (there m a y be one or two of them), their diagonals do not meet v, so the a r g u m e n t is the same as for Case I: these cells do not contribute to a n y change in the n u m b e r of solid diagonals incident on v. There is an additional case in which the cells E and E ' coincide; we leave the analysis of this case to the reader.
Figure 15. The parity of the number of solid diagonals incident to v does not change.
THEMATHEMATICAL INTELLIGENCERVOL.17,NO.3,1995 55
In general, the principal contour may reenter and reexit IV(v) several times; but if one looks at the portion of the curve between any entrance point and the corresponding exit point, the preceding analysis will apply. This completes the proof. Combining Lemmas 1 and 2, we can finally see what is happening: If the state of the universe satisfies the even diagonals-degree property with the ant at home, then the ant must travel along the principal contour, but when it completes this path and returns home, it restores the even diagonals-degree property, so that it must once again travel along the (new) principal contour, and so on, ad infinitum. In view of the argument at the end of the preceding section, the proof of the theorem (and the solution of the symmetry-mystery) is complete. We leave it to the reader to find the simple numbertheoretic argument that shows that a number like 57 whose binary expansion has the even run-length property is divisible by 3; this explains Propp's observation concerning the code numbers of the ants whose tracks exhibit recurrent bilateral symmetry.
Note: For a copy of Propp's program ant.c (an ant-universe simulator designed for UNIX machines), send e-mail to
[email protected].
References 1. D. Gale, "The industrious ant," Mathematical Intelligencer 15(2) (1993), 54-58. 2. D. Gale and J. Propp, "Further ant-ics," Mathematical Intelligencer 16(1) (1994), 37-42. 3. L. A. Bunimovich and S. Troubetzkoy, "Recurrence properties of Lorentz Lattice Gas Cellular Automata," J. Statist. Phys. 67 (1992), 289- 302.
Jim Propp Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139-4307 USA Scott Sutherland Serge Troubetzkoy Institute for Mathematical Sciences SUNY at Stony Brook Stony Brook, NY 11794-3660 USA
Raphael Robinson, 1911-1995 As some readers may have heard, Raphael Robinson, world-renowned mathematician, died on January 25th of this year. It seems appropriate to take note of this in this space, for Raphael more than any other outsider was a supplier of material for many of these columns ever since I became editor in 1991. In particular he made major contributions to my first column on "Somos sequences,"
56
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3,1995
and most recently he discovered proofs of the results on "Configurations with Rational Angles" in this winter's issue. Robinson in his career made major contributions to logic, set theory, number theory, analysis, geometry, and combinatorics. It was a piece of great good luck that The Intelligencer was able to benefit from the interest and insight of this remarkable mathematical mind.
ET and an Infinitary Church's Thesis Robert M. Baer
Martin Davis, in Computability & Unsolvability (1958), said of Church's thesis, "For how can we ever exclude the possibility of our being presented, some day (perhaps by some extraterrestrial visitors), with a (perhaps extremely complex) device or 'oracle' that 'computes' a noncomputable function?" The recent television revival of the Stephen Spielberg film ET presented a script sadly deficient with respect to Davis's question and to mathematics generally. To be fair, this film was made for American juveniles, for w h o m any mathematical references would have been mysterious. Still, one can imagine a scenario for an actual ET visit. In this scenario, the ET landing occurs at Princeton, NJ, and the colloquy takes place in English, between ET and a mathematician from the Institute for Advanced Study (who agreed reluctantly to be the designated Presidential Representative only after assurance that he would not first have to be approved by any Senate committee) ...
-
ET: You have some questions for me? PR: Yes, some mathematical questions. You've reviewed our mathematics library overnight. So can you offer a relative evaluation of your mathematics and ours? ET: My first impression was surprise that you have any mathematics at all. Mathematics is never mentioned in your television. PR: That's right.
PR: Your English is surprisingly good. And your voice is surprisingly human. ET: The voice comes from an implanted specially engineered larynx to mimic your species. The English comes from study of your television transmissions. PR: Uh-oh. ET: Is there a problem with using television English? PR: It's a vulgar dialect, that is, it doesn't accord with English grammar. It uses double negatives incorrectly, doesn't understand the significance of case, doesn't grasp the use of the subjunctive, and .... Anyway, it is rarely used for mathematical discourse. THE MATHEMATICAL INTELLIGENCER VOL 17, NO. 3 (~)1995 Springer-Verlag New York
57
ET: We held several theories about its conspicuous absence. One, that you regard mathematics as a liturgy-- a theological work considered too sacred for telecast. Another, that mathematics is bound by patent rights and trade secrecy and so is precluded from public presentation. And still a n o t h e r - - t h e cynics, you u n d e r s t a n d - was simply that you have no mathematics. PR: But you've seen our library. Seven hundred eightytwo research mathematics journals. ET: Yes, that is a surprise. You write down everything. We, by contrast, communicate just verbally all but the most complicated results. Those we write down. Of course, when I say we write them down, I should be exact and say that we dictate them to our computers. They write them down and then write them up. PR: Down and up. I can guess the distinction. But would you... ? ET: It's your terminology. Writing it down is just transcribing oral input to computer memory. Writing it up means the computers' checking for logical consistency, maximal coherence, novelty to existing theory, accuracy of references--what you would call "rounding up the usual suspects" - - rewriting the text accordingly and disseminating it in e-mail. PR: You let computers edit your work? We prefer to do that ourselves.
The principle difference between our approaches to mathematics appears to be that we a l w a y s start w i t h infinite objects and you start w i t h finite objects.
ET: [Puzzled] Why bother? In any case, there's an advantage to having all of the theory in the computers. They're constantly checking for analogous theorems in seemingly disparate a r e a s - - which might suggest a metatheorem or a connection which has been unnoticed. PR: Well, we do that ourselves as well. ET: [Carefully polite] Yes. Of course our mathematics is so much more voluminous than yours . . . . By the way, I noticed in your literature an explicit reference to my possible arrival and how it might influence your view of effective procedures. PR: Ah. Church's thesis. ET: I must tell you first how we view natural numbers and integers. What you call integers, we call little inte58
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
gers. What we call integers are bounded sequences of little integers indexed by the little integers. PR: Bounded bi-infinite sequences of integers? Hm. What do you call one-way infinite sequences of integers? ET: Half-integers. The principal difference between our approaches to mathematics appears to be that we always start with infinite objects and you start with finite objects. PR: Why don't we call your integers meta-integersso I can still call m y integers just integers. ER: All right. Then do you want to call bi-infinite sequences of natural numbers metanatural numbers? PR: Just metanumbers will do. ET: All right. You can see that the meta-integers form a ring which contains a subring isomorphic to the ring of integers? And the metanumbers form a semiring with a subsemiring isomorphic to the semiring of natural numbers? PR: Yes, yes, under componentwise operations. But coming back to Church's thesis ... ET: I was going to say that our version of an effectiveness principle is pretty much like your Church's thesis except that the recursive functions are applied to metanumbers rather than natural numbers. In your jargon such mappings might be called parallel-recursive operators. Or props. So if g is a recursive function and (hi) is a metanumber, then the corresponding prop g is defined by g((ni)) = (g(ni)). So your Church's thesis proposes that the class of effectivelycomputable functions be identified with the class of recursive functions, whereas our effectiveness principle proposes that the set of effective functions be identified with the set of props. You might want to refer to it as Church's Thesis Extended. Or you might want to challenge it. PR: Well, if your notion of "effective" is informal, as ours is, then your effectiveness principle is no more susceptible to proof than is Church's thesis. [Pauses; thinking] I suppose that your notion of p r o o f - - infinitized? - - is the same as ours. ET: Yes, there seems to be a logic-relativity principle: The consistency and completeness of logics are identical everywhere. In that sense, at least, we speak the same language. PR: [Nods] It's obvious that props map the semiring of metanumbers into itself... ET: In a finite number of steps. It's what you call parallel computation; we simply call it computation. PR: A finite number of steps? [Thinks] Yes, obvious. But we have no models of computation for infinite systems-ET: Sure you do. Cellular automata, random-access machines with infinite registers, Turing machines-PR: [Smiling] No, no. Turing machines are finite. Or rather they have finite configurations. The models may be infinite, but the configurations are finite. Well, the con-
figurations may be infinite, but the change in configurations at each step is finite. ET- Our models of computation are mathematical-- they have only infinitary configurations. And, in contrast to yours, our configurations are not restricted to a finite change at each computation-step.
placing the code for ni in the ith row. Rig it so that each row simulates a Turing calculation of f. And preclude interaction among rows. If the range of (ni) is contained in domain(f), then the CA halts in finitely many steps; otherwise the CA never halts and the result is undefined.
PR: But a TM has only one read-write head. ET: Our version has infinitely many read-write heads, just as the cellular automaton has infinitely many finitestate machines. One head for each number-code on the tape. PR: Infinitely many heads? But they could collide during computation. [Thinks] I see. The lengths of strips of tape required for a bounded number of evaluations are bounded. So you just allow a sufficiently liberal spacing of the initial values along the tape. ET: More precisely, between initial values. So, no adjacent heads ever get close to each other. PR: But defining infinitely many initial v a l u e s - - t h e components of the metanumber initial i n p u t - - i s n ' t effective. ET: In our view it's conceptually effective. PR: Conceptually effective? ET: The components are assigned by a recursive function, values of even-indexed arguments to the right, values of odd-indexed arguments to the left. PR: Let's see . . . . Instead of using metanumbers, why not have as input those bi-infinite sequences which have bounded computation-times? ET: No, that would never do. Take as the metanumber input the sequence (2 lil + 1/, in binary of course, and let each Turing head have the program which directs it to find, starting at the low-order bit, the first low-order 1-bit and erase it. Then the number of computation steps to compute the result is bounded - - indeed just one computation step is required - - but the same algorithm applied to the result never terminates since the distances traveled by the heads to find the low-order 1-bit are unbounded. PR: Okay, props map the space of metanumbers into itself, but not the space of sequences producing timebounded computations into itself. ET: Just the way that recursive functions map the space of natural numbers into itself. PR: [Smugly] But of course you've lost the partial recursive functions - - the parallel partial recursive functions - entirely. Shall we call them p-props? ET: If you like. No, we havenZt lost them. The Turing machine is not the appropriate model for the p-props. But, with respect to mechanical models, the planar cellular automata do nicely for that. Perhaps you can see how they would suffice. PR: Let's see . . . . Suppose f is some partial recursive function. Start the CA with a metanumber input (n~) by
Since all of your classical models of computability are linear-- one-dimensional--I thought that you would be interested in how they fare under infinitization.
ET: Exactly. Now consider the same CA starting with the code for 2i in its ith row for i > 0 and with the code for 2i + 1 in the ith ro~aTfor i < 0. Note that the CA is not computing just a function value, but rather the entire function. PR: [Frowning] But the starting sequence isn't bounded. It isn't a metanumber. ET: Correct. Nor am I suggesting that this function is computed in finite time, even though there are recursive functions g which this type of CA can compute in finite time. For example, let g be the identity function, g(n) = n, and let the CA's rows simulate a corresponding Turing machine which has its halting state as its initial state. So the CA computes this particular recursive function in finite time. But this type of CA couldn't compute many unbounded functions in finite time. For example, it couldn't compute the function f(n) = n 2 in finite time. (Not the function value, understand, but the function.) That is w h y we apply props to metanumbers. Because then every prop takes only a finite time for calculation. PR: I see w h y the Turing machine with infinitely many heads cannot handle partial props. In some cases adjacent heads would collide. Hm, if it were permissible for multiple heads to scan the same square, that might embody an interesting case of computability chaos . . . . Sorry, I didn't mean to wander. Anyway, since CA's can handle partial props and your infinitary Turing machines cannot, w h y bother with the latter? ET: Since all of your classical models of computability are linear-- one-dimensional-- I thought that you would be interested in how they fare under infinitization. PR: So it appears that these infinite models of computation-- should I say models of infinite computat i o n ? - may be equivalent for recursive functions but not for partial recursive functions. Interesting. Our writers place great importance on the equivalence of models in recursive function theory. So, if there is no equivalence for your p-props ... THE MATHEMATICAL INTELL[GENCER VOL. 17, NO. 3, 1995 5 9
ET: Your writers? PR: Kleene, Davis, Gandy, Kreisel, Webb. To name a few. It's even been considered as a principle of physics. By Rosen and Deutsch. ET: Can you quote them? PR: Well... in substance. Anyway, I was going to say that parallelism isn't a notion that's part of our mainstream mathematics. ET: I gathered t h a t - - from one of your writers. PR: Oh? Which one? ET: Lopez-Escobar. PR: [Slyly] Can you quote him? ET: "At the present time such problems of how to carry out infinitely many acts in a finite amount of time are of no interest whatsoever." PR: Mm. Well, in any case we just don't consider that starting with an infinite amount of input is consistent with the notion of effectiveness. ET: The input must be finite? PR: Absolutely. ET: The input could be finite but be larger than this particular universe. But you would still say it could be effectively presented? PR: Yes. It could be conceptuallyeffectively presented. ET: Strange. Why is it, I wonder, that you're dedicated to basing so much theory on the finite? PR: [Shrugs] Perhaps because the universe is finite. The physical universe. ET: [Imitates a shrug] Finite? Why do you think so? PR: We can see the boundary. ET: Your technology is not sufficiently refined to see the boundary. And it is much too primitive to see other universes. They are too far away. PR: [Stunned] Other universes! Wow. Do you see them?
"We've never f o u n d a w a y to get around the speed of light. A n d it's sooo slow."
ET: Very Distant Objects. The nearest universes. Tight concentrations of supergalaxies. Like the local bubble. PR: How do you do it? ET: We blanket two of our moons with mosaics of integrated silicon photodetectors. They give us large lightcollectors and a nice parallax base besides. Of course it's tedious waiting for the data transmission. We've never found a way around the speed of light. And it's sooo slow. PR: No, I meant how do you manage to get the funding? ET: [Puzzled] Well, what else would we spend funds on? PR: Did I hear you say siliconphotodetectors? Do you use silicon-based computers? ET: We did, long ago. I would say that was our stone age. PR: Really? Then what do y o u - - ? ET: We use holographic computers. You would call them quantum mechanical. PR: Quantum mechanical? I'm talking about real computers. ET: Yes. No heat generation. Enormous memory. Very fast. And almost everything computes in near-linear time. PR: Hm. Well, we know how to design quantum computers. It's just a matter of getting our technology up to speed. Anyway, let's get back to computability. ET: Do you have any further questions? PR: Yes. But first I'd just like to point out that we have models of computability which aren't infinitary at all. Markov normal algorithms. Post's Tag. ET: [Nodding] We have versions of those. PR: Infinitary? ET: Yes. PR: [Frowning] Could you... ? ET: Of course. As for normal algorithms, you may know that, for any recursive function g, there is a normal algorithm with rules of the form 0'~ 1n 0p ~ 0q 1r 0 3 that start with initial strings of the form Oh lJ0 where the string Oh encodes the arguments of g. All the h, m, n, p, q, r, s, and J are positive integers, and n and r range over a fixed finite set that accords to g. PR: Mm.
" . . . h o w do you manage to get the funding?"
ET: Not yet. But our cosmological theory tells us that they must exist. Our theory says that space is infinite and percolates universes. Actually we refer to this universe as the local bubble. We're currently building an enormous superconducting supercollector which we are sure will detect VDOs. PR: VDOs? 60
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
ET: So if (n~/ is a metanumber, then let (n(n~)/ be the corresponding sequence of codes. Let u be some integer larger than any of the n and r that appear in the rules, and take 1~ as a separator. The input string for the infinitary normal algorithm is just the concatenation of the encodings separated, pairwise, by the separator. PR: A bi-infinite string? ET: Yes. I suppose that you would call it a metastring. PR: I see. And the infinitary algorithm is just the algorithm applied in parallel . . . .
ET: Note that there is no ambiguity about which rules apply (and where) at each step, so the application of rules at infinitely many places simultaneously is well defined; also, if 9 is partial recursive, then as usual the infinitary normal algorithm halts just in case the bounded, hence finite, set of numbers in the initial sequence is contained in the domain of 9. PR: Mm.
ET: Isn't it curious that the infinitization of one of your finitary models properly handles the class of partial recursive functions, whereas the infinitization of your primary infinitary m o d e l - - the Turing machine-- can handle only the class of recursive functions. PR: [Thoughtful] Because... in the normal algorithm the ietters aren't anchored to tape positions.
ET: [Carefully polite again] I suppose it's a matter of interpretation. PR: [Nods] Tell me this: If your mathematics starts with infinite objects--
ET: Yes. PR: - - t h e n what about finite groups, finite rings, finite geometries, combinatorics?
ET: We lump all of that into what, in your terms, might be called structured arithmetic. We teach that to our firstgraders. PR: [Glumly] We teach it to our first-year graduate students.
ET: [Nods sympathetically] Anything else? PR: [Sighs] Yes. About the Riemann hypothesis ...
ET: Yes. When you get away from mechanical models, everything goes nicely. PR: Mm.
ET: Can I ask whether you accept a computability theory based on infinitely many computational steps performed in parallel? PR: As a purely mathematical notion? Yes. [Thinks for a moment.] What would happen if infinitely many computational steps in serial were permitted?
ET: We have a theory for that style of computability which we call accelerated. You might call it asynchronous or fractalized. In that theory the nth step of any computation takes place in time interval 2-n; so any computation is completed in at most two units of time. And that applies to the cellular automaton example which we discussed earlier, in which entire recursive functions are computed. But don't confuse that with props applied to metanumbers. PR: [Coolly] I can distinguish the two theories.
ET: Of course in your mathematics, infinitely many computational steps in serial took a dramatically sophisticated step forward with Newton and Leibniz telescoping infinite series and sequences into finite-time results by the notion of limit. Then Abel, Cauchy, Weierstrass-PR: Yes, yes. That's a curious point of view. We don't associate time with taking the limit of infinite sequences.
ET: Not even when your computers calculate them with symbolic mathematics programs? I have the impression that you have to pay for your computer time. PR: Well, yes and no. Why did you say that I might want to call such computations fr~ctalized?
ET: I noticed in your literature that your cellular automaticians get fractals in that way; they normalize serially generated patterns and approximate the l i m i t - - when it exists-- obtaining fractals. PR: Be that as it may, we don't consider taking limits to be the same as performing infinitely many acts in series.
Bibliography
Baer, R. M., Computability by normal algorithms, Proc. Am. Math. Soc. 20 (1969), 551-552. Davis, M., Computability & Unsolvability, New York: McGrawHill (1958). Davis, M., Why G6del didn't have Church's Thesis, Inform. Control 54 (1982), 3-24. Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. Roy. Soc. London Ser. A 400 (1985), 97-117. Fischler, W., Morgan, D., and Polchinski, J., Quantization of false-vacuum bubbles: a Hamiltonian treatment of gravitational tunneling, Phys. Rev. D 42 (1990), 4042-4055. Gandy, R., The confluence of ideas in 1936, in The Universal Turing Machine: A Half-Century Survey (R. Herken, ed.), Hamburg: Kammerer & Unverzagt (1988). Goodman, N. D., Intensions, Church's thesis, and the formalization of mathematics, Notre Dame J. FormalLogic28 (1987), 473- 489. Kleene, S.C., Reflectionson Church's thesis, Notre DameJ. Formal Logic 28 (1987), '90-498. Kreisel, G., Church's tl sis and the ideal of formal rigour, Notre Dame J. Forma, ~gic 28 (1987), 499-519. Kreisel G., Church's The s: a kind of reducibility axiom for constructive mather~ ~cs, in Intuitionism and Proof Theory: Proceedings of the ;ummer Conference at Buffalo, N.Y. (A. Kino, J. Myhill, R.~ Vesley,eds.), Amsterdam: NorthHolland (1970). Lopez-Escobar, E. G. K., Re larks on an infinitary language with constructive formt ~s, J. Symbol. Logic 32 (1967), 305318. Lopez-Escobar, E. G. K., Infi te rules in finite systems, in Nonclassical Logics, Model Th ~ry and Computability (A. I. Arruda, N. C. A. da Costa, aJ l R. Chuaqui, eds.), Amsterdam: North-Holland (1977). Rosen, R., Church's Thesis Ld its relation to the concept of realizability in biology and physics, Bull. Math. Biophys. 24 (1962), 375-393. Webb, J. C., Mechanism, Mentalism, and Metamathematics, Dordrecht: Reidel (1980). Parallel Logic Corporation 379 Countyview Drive Mill Valley, CA 94941, USA THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
61
What Is Modern about "Modern" Mathematics? Hardy Grant
In 1901 Bertrand Russell offered the opinion, subsequently much quoted, that in mathematics we never know what we are talking about nor whether what we are saying is true [1]. I imagine that most mathematicians will have a sense of what lies behind these words, and will agree that the view they express is certainly modern. I should like, however, to put this last point a bit more strongly and suggest that Russell's stance is calculated to make a Euclid or even a Newton spin around in his grave. Now, beside Russell's pronouncement I want to set two others. The first will be recognized by readers of Hardy's Apology, where it is quoted with approval. It is not, however, about mathematics but about poetry; it is A. E. Housman's famous assertion (1933) that "poetry is not the thing said but a way of saying it" [2]. Hardy did not add that this sentiment is calculated to make a Vergil or a Milton spin in his grave. And here is a third declaration, with the same power to upset distinguished shades, but this time bearing on the visual arts. In 1914 Clive Bell laid it down that "the representative element in a work of art may or may not be harmful; always it is irrelevant" [3]. I venture to suggest that these three roughly contemporaneous quotations hint at certain parallels between mathematics and other spheres on the one hand, and certain distinctions between ancient and modern perspectives on the other, which may be worth exploring.
sisted that for past generations an unvarying set of three assumptions underlay discourse in these realms, namely that, first, all genuine questions must have one true answer and one only, the rest being necessarily errors; secondly, there must be a dependable path towards the discovery of these truths; and, thirdly,
The Classical Tradition To get some further anchorage in a large and amorphous subject, I call no less a witness than Sir Isaiah Berlin, the great historian of political and moral philosophy. Repeatedly, almost obsessively, Sir Isaiah has in62
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3 (~ 1995 Springer-Verlag New York
the true answers, when found, must necessarily be compatible with one another and form a single whole [4].
entities were guiding presences in the divine mind at the origin of the universe. "God the creator of the massive structure of the world," wrote Boethius (6th century Again, the reference here is primarily to moral and A.D.), "considered [arithmetic] as the exemplar of his own political thought. But Isaiah Berlin prefaces this list of thought, and established all things in accord with it" [9]. perennial beliefs with the phrase "as in the sciences"; Thus mathematics seemed uniquely to promise knowland indeed it would seem that, both logically and psyedge of a transcendent reality. And of course an actual chologically, these convictions must be underwritten by example was ready to hand, for most of the life of the analogous postulates about the nature and reliability of tradition, of absolute and certain truth already attained human knowledge of the world around us. Translated by right method, namely Euclidean geometry. into such terms, that would mean that our ancestors beMore to the present point, this Platonist epistemollieved (at a minimum) that ogy was what John Dewey called a "spectator" theory of - - the world presents to us an objective reality, which knowledge [10]. The grasping of the eternal verities was likened to the everyday experience of looking and seein principle we can know; there is about the world a unique set of truths which i n g - with the "mind's eye," to be sure. This meant that the acquisition of knowledge was in an important sense are objectively valid and mutually consistent; - - b y the right choice of method these truths are a passive experience. Not, of course, that it lacked emotional commitment and i n t e n s i t y - - n o reader of Plato discoverable. would suppose that. But the facts are "out there," and Dissenters and skeptics notwithstanding, these beliefs thus are, so to say, beyond human control. The observer were indeed at the heart of the mainstream epistemol- hopes to apprehend them, but cannot and does not hope ogy in the West in antiquity and beyond. "It was the uni- to change them or shape them, still less to in any sense versal conviction among those who thought seriously," create them. This is true in particular of math6matics. The says the great medieval scholar David Knowles, "that Greeks took the view that "the mathematician cannot crethere was a single true rational account of man and the ate things at will, any more than the geographer can; he universe.., as valid in its degree as the revealed truths too can only discover what is there and give it a name." of Christianity" [5]. For convenience, and with all due I shall identify later the writer of these words. reservations, I shall label this theory of knowledge "clasThis passive character of knowledge acquisition sical" or (equivalently) "Platonist." shows clearly in the various metaphors by which our Whence came this trust that human beings can attain ancestors sought to explain the workings of our minds. certain knowledge of the real? Note first that it is after all Thus Plato and Aristotle already liken the mind to wax very much the common sense of the common man, and receiving the impression of a seal [11]. Of all such imso is entirely natural. But sophisticated thought added its ages, probably the most powerful and pervasive was of own elaborate rationalizations. I shall indicate in a mo- the mind as a mirror, reflecting (but not shaping!) exment the powerful role played in this respect by mathe- ternal reality. That was a very natural metaphor in a matics. Plato's influential Timaeus told how the physical context where, as I have said, the mental act of knowworld was actually modeled on divine archetypes, an ori- ing was so commonly analogized to the physical act of gin which seemed to guarantee its rationality [6]. Chris- seeing. Moreover, the mirror metaphor offered a convetianity offered convincing reinforcement. St. Paul wrote nient explanation of the manifest failings of our quest for to the Romans, "The invisible things of him from the understanding: one could say that human sin and error creation of the world are clearly seen, being understood bend or cloud the mirror and so distort its images (some by the things that are made" [7]. Indeed, is man himself lovely lines in Shakespeare's Measure for Measure say just not made in the image of God? And has he not been en- this) [12]. The methodological reformers of the Renaisdowed by his creator with a "natural light," by which he sance, like Francis Bacon and Descartes, can usefully be may see eternal truths? Many postulated a fundamen- pictured as attempting to get truer reflections of reality tal congruence or "fit" between our minds and "reality"; by straightening and polishing our mental mirrors. perhaps the best known statement is Spinoza's dictum The Platonist epistemology that I have been sketching that "the order and connection of [our] ideas is the same entailed a corresponding aesthetic, a traditional philosoas the order and connection of things" [8]. phy of artistic purpose, and here the contrast that I want No secular agency under~rote this optimistic vision to draw between ancient and m o d e m ways of thought of human knowledge more powerfully than did mathe- appears with particular vividness, being in fact close to matics. Several strands of thought contributed. Plato's a polar opposition [13]. The artist's aim, on the old view, theory of Ideas, the fountainhead of the classic epistemol- was the imitation ("mimesis") of the nature of things, ogy, drew deeply on the perceived status of numbers and of the eternal verities, as his culture by general consengeometrical shapes-7--independent of, yet accessible to, sus intuited them. The beauty of his work was in direct human minds. From the Timaeus to Kepler and Galileo, proportion to his success in this endeavour. Beauty was the conviction persisted that these same mathematical thus objective, and was in fact identical with truth. The -
-
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
63
artist worked consciously within a tradition whose timehonoured conventions he was at pains to obey. It was no part of his business to express his own personality. His moral imperative was rather that of the good reporter: to set out the truth of things without letting his own idiosyncracies or his biases intervene. There is a touching example of this in Dante, when the poet invokes the Muses to help him describe with utmost fidelity the horrors of Hell as his vision revealed them [14]. I have been trying to outline a complex of ideas which, to summarize, has three facets: the "classical" or Platonist epistemology, a corresponding monism in political thought, and an attendant philosophy of the arts. The tradition that these jointly represent had a very long careen Beginning with the Renaissance, to be sure, there were a number of challenges to those old beliefs, hints of changes to come. Let me mention just three of these: - - I n the Renaissance and afterward a growing cult of individual, self-conscious genius weakened the old vision of the artist as the humble, anonymous expositor of communally shared truths. - - A small minority of thinkers--posterity salutes especially Giambattista Vico ( 1 6 6 8 - 1 7 4 4 ) mounted a drastic challenge to the traditional epistemology. On their view we know with certainty only those things which we ourselves make (including mathematics!). The opening here for subjectivist and relativist theories of knowledge is obvious. --Similarly, from the 17th century's doctrine of the "secondary" qualities of objects, qualities like colours and tastes, held to be present in our minds rather than in the objects themselves, it can have been no great leap to the idea that when we form pictures of the world we are not passive recorders of the given but active contributors. Yet despite all such anticipations, the older tradition remained largely intact until well into the 18th century. Consider: in that century Voltaire, Leibniz, and others still believe that eternal, necessary laws govern even such slippery realms as morals and metaphysics. Rameau in France can still hope to reduce musical theory to a few clear and distinct principles and mathematically formulated rules [15]. Winckelmann in Germany preaches an ideal, absolute beauty in the visual arts [16]. Relativism, pluralism, subjectivism are still in the future. Nor is the primary reason for all this far to seek. The unprecedented triumphs of Newtonian science seemed to have solved the riddles of the physical world and to offer a methodology for unveiling eternal truths in other realms. The Romantic Revolution And so when, in the decades around 1800, the great change finally c o m e s - - when the mirror finally breaks - the impulse comes in large measure as a reaction against the mathematizing spirit. A full account would be the 64
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
full story of the genesis and course of Romanticism, obviously not to be undertaken here even had I the competence. I can only cite instead some of the trends that bear most directly on my present theme. Three seem especially germane: the reaction against the perceived dominance of scientific thinking, the rise of nationalism, and the rise of historical consciousness. Singly or together, these ensure that the Romantic spirit refuses to grant sole possession of absolute truth to any particular group of people, any particular point of view, any particular methodology. There is now an insistence in some quarters that each group, each nation, has so to say its unique window on the world, its particular experiences, visions, values, which may be simply incommensurable with those of others. There is a growing belief that the supposedly natural, universal "laws" of the commonwealth are in fact shaped by particular human beings and are rooted in place, time, and circumstance. ("There are no laws," says Vautrin to Rastignac in Le p~re Goriot (1833), "there are only circumstances" [17].) Thus Isaiah Berlin locates in just this period, the late 18th and early 19th centuries, the abandonment of those age-old axioms of political and social thought that I cited earlier. For him a key figure is Herder, with his celebration of the unique history and character of each people, and of the German people in particular [18]. Meanwhile in epistemology the Romantic age sees the radical replacement of one canonical metaphor of mind by another. The mirror as passive reflector of external impressions gives way t o - - the lamp, conceived as actively lighting up the outer world from within [19]. Coleridge, who of course is near the heart of the whole movement, speaks of "informing the senses from the mind, and not compounding a mind out of the senses" [20]. Thus there emerges an epistemology in which the known is shaped, even created, by the knower, and the very idea of objective, absolute truth becomes deeply problematic or is abandoned altogether. Knowledge and truth increasingly seem subjective, relative, fragmented, pluralistic. Correspondingly, the traditional philosophy of the arts is by now essentially stood on its head. Artists now specifically reject its underlying Platonism, specifically deny (here I quote a contemporary witness) that "beauty could ever own any fixed, absolute form" - - there speaks the quintessential Romantic musician, Franz Liszt [21]. The ancient imperative of mimesis is now widely mocked. The artist no longer draws the content of his work from a communal vision of the real, and no longer fashions its form according to communal tradition; content and form alike become intensely subjective. Often, the form of a work is seen as more significant than its c o n t e n t - - a heresy on the older view, but precisely the attitude expressed in those remarks by A.E. Housman and by Clive Bell that I quoted at the outset. Creative freedom is unlimited, but operates in the absence of socially agreed canons of meaning and of value. "Modern" art is born.
I have tried to stress how deep and pervasive and longlasting was the old Platonist tradition, here supplanted. Arguably, then, the breakdown of that whole complex of ideas, the giving up of its assumptions, the casting off of its conventions, the lo~s of its certainties, the embrace of other possibilities, was the pivotal watershed in the history of western sensibility, and its aftermath is the defining condition-- some would say "predicament" - of modernity. The novelist and critic Gabriel Josipovici writes [22]: What all the moderns have in common--perhaps the only thing they have in common-- is an insistence on the fact that what previous generations had taken for the world was only the world seen through the spectacles of habit .... The modems unanimously rejected the implication that the norms of the Renaissance corresponded with the necessary structure of reality....
Mathematics
Too?
Now it is well known that great changes come over mathematics too in just the years of the Romantic revolution. To me, several of these developments echo strikingly the upheavals that I have tried to describe in general culture. Thus 19th- and 20th-century mathematics lays increasing stress on form and structure as against content-hence Russell's famous quip. Absolutes and certainties crumble, until Morris Kline can lament that mathematics "contains no truths" [23]. Axioms are no longer statements of self-evident fact but mere assumptions, which may be more or less arbitrary. Axiom systems multiply, and internal consistency replaces truth as the criterion of their validity and value. Diverse mathematical structures coexist side by side, like euclidean and hyperbolic geometry, individually valid though mutually irreconc i l a b l e - w h i c h is exactly how Herder viewed the differing world-views of national groups. Euclidean geometry, for centuries the stock example of objective truth and incontestable knowledge, now seems merely "the world seen through the spectacles of habit," and not at all "the necessary structure of reality." More generally, the contacts of mathematical structures with "reality" become ever more mysterious, or in some eyes simply irrelevant. Meanwhile the creative freedom of the individual mathematician is much cherished, but sometimes seems to issue in waywardness and sterility. "Much of the current picture of pure mathematics," says Ivor GrattanGuinness, "is a dispiriting accumulation of scholastic exercises in difficult manipulations of complex structures without regard to their intellectual or empirical implications" [24]. Mutatis mutandis, the remark's tone echoes countless exasperated responses to modern experiments in literature, music, and art. Thus to the question raised by my title, "What is modern about 'modern' mathematics?", the answer from a cross-cultural perspective would be precisely this partici-
pation of mathematics in many of the trends and characteristics of modernity as a whole. One can go on to ask whether in this context there may have been actual influence between mathematics and the rest of the culture; here I offer only the briefest of remarks. First, remember that well before the rise of Romanticism, mathematics began dealing with concepts and entit i e s - irrational and complex numbers, infinities and infinitesimals, dimensions beyond the t h i r d - - t h a t would seem to be pure creations of the human mind, not to be discovered in a mirror of the physical world. Could this internal trend have "spilled over," operating suggestively on other minds? I can only say that I know of no direct evidence, no declaration of such indebtedness. Indeed, may it be significant that the mathematicians' full acceptance of these exotic entities generally awaited the early 19th c e n t u r y - - t h e very decades when Romanticism so weakened the old epistemology? Are there other hints of this opposite direction of influence, the impact on mathematics o f the wider milieu? I.am for the most part a convinced "internalist," especially at 19thcentury levels of mathematical sophistication, and I have no doubt that there were good mathematical reasons for all of those developments, cited above, that so closely parallel modernist trends elsewhere. But is that absolutely the whole story? Let me dramatize the issue with a single example. In 1823 the younger Bolyai, exulting in his discovery of hyperbolic geometry, rejoiced that "from nothing I have created another wholly new world" - - something which Euclid never would have said [25]. At very much the same time, Wordsworth, remembering his time at Cambridge, wrote [26] that I had a world about me; 'twas my own, I made it .... which Dante never would have said. Is the similarity a mere coincidence? Those two men never met; but they breathed the same air, and that air was full of revolutionary things. Yet ... all that said, I cannot resist giving the story one final twist. Platonism dies very h a r d - - and nowhere harder than among mathematicians. Kurt G6del's deep commitment to it is well known. Ren6 Thom declared fervently that "mathematical forms indeed have an existence that is independent of the mind considering them" [27]. David Hilbert spoke late in his life of a preestablished harmony between nature and our thoughts, a harmony realized by us in and through mathematics [28]. Earlier I quoted a writer who said that mathematical entities are "out there" to be observed and described as the geographer describes things, and I said that this attitude was that of the Greeks. In fact the writer of those words was Gottlob Frege, in 1884, and the position he there described was his own [29]. Perhaps mathematics is actually in this sense the least "modern" of modern endeavours. --
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3,1995
65
References 1. Bertrand Russell, "Recent Work on the Principles of Mathematics," International Monthly 4 (1901), 84. 2. A.E. Housman, "The Name and Nature of Poetry," in Collected Poems and Selected Prose, London: Allen Lane, The Penguin Press (1988), p. 364. 3. Clive Bell, Art, London: Chatto & Windus (1949), p. 25. 4. Isaiah Berlin, The Crooked Timber of Humanity, New York: Random House (Vintage Books) (1990), pp. 5-6. 5. David Knowles, The Evolution of Medieval Thought, New York: Random House (Vintage Books) (1962), p. 55. 6. Plato, Timaeus, 29 ft. 7. Romans 1:20. 8. Spinoza, Ethics, Part II, prop. vii.
9. Boethius, De Institutione Arithmetica (translated by Michael Masi as Boethian Number Theory), Amsterdam: Editions Rodopi B.V., 1983, I, 1. 10. John Dewey, The Quest for Certainty. New York: Minton, Balch, 1929, p. 23. 11. Plato, Thaeatetus, 191c ff, 193b-196a, 200c; Aristotle, De anima 424a. 12. Shakespeare, Measure for Measure, II, ii, 117-122. 13. The most learned and fascinating expositor and defender of the traditional philosophy of art was Ananda K. Coomaraswamy; see, for example, TraditionalArt and Symbolism, Princeton NJ: Princeton University Press (1986). 14. Dante, Inferno, xxxii, 10-12. 15. Richard Paul, "Jean-Philippe Rameau (1683-1764), the Musician as Philosophe," Proc. Am. Phil. Soc. 114 (1970), 140-154. 16. Johann Winckelmann, "History of Ancient Art," in Winckelmann: Writings on Art, David Irwin (ed), London: Phaidon (1972), pp. 117ff.
17. Honor6 de Balzac, Le p~re Goriot, trans. M. A. Crawford, London: Penguin (1951), p. 134. 18. Isaiah Berlin, (ref. 4) passim. 19. M. L. Abrams, The Mirror and the Lamp, New York: Oxford University Press (1953). 20. S. T. Coleridge, Table Talk and Omniana of Samuel Taylor Coleridge, quoted in Ref. 19, p. 58. 21. Howard E. Hugo (ed.), The Portable Romantic Reader, New York: Viking Press (1957), p. 61. 22. Gabriel Josipovici, The Worldand the Book:A Study ofModern Fiction, London: Macmillan (1971), pp. xiii-xiv. 23. M. Kline, Mathematics in Western Culture, New York: Oxford University Press (1953), p. 9. 24. Ivor Grattan-Guinness, Br. J. History Sci. 7 (1974), 186. 25. J~nos Bolyai, letter of 3 November 1823, in Roberto Bonola, Non-Euclidean Geometry. New York: Dover (1955), "Translator's Introduction" to The Science of Absolute Space, p. xxviii. 26. William Wordsworth, The Prelude, III, 142. 27. On both G6del and Thom, cf. Philip J. Davis and Reuben Hersch, The Mathematical Experience, New York: Penguin Books (1983), pp. 318-319. 28. Constance Reid, Hilbert-Courant, New York: SpringerVerlag (1986), p. 194. 29. G. Frege, The Foundations of Arithmetic, 2nd rev. ed., trans. J.L. Austin, Evanston IL: Northwestern University Press (1980), p. 108.
539 Highland Avenue Ottawa, Ontario K2A 2J8 Canada
continued from p. 4
8.
9. 10. 11. 12. 13.
JETP 8 (1938), 89-95 (I), 1340-1349 (II), 1349-1359 (III). Shortened translation of I und Ih On the theory of plastic deformation and twinning. J. Phys. (Moscow) 1 (1939), 137-149; translation of h On the theory of plastic deformation and twinning. Physikalis. Zeitschr. Sowjetunion 13 (1938), 1 - 10. A. Seeger, H. Donth, and A. Kochend6rfer, Theorie der Versetzungen in eindimensionalen Atomreihen III: Versetzungen, Eigenbewegungen und ihre Wechselwirkungen. Z. Physik 134 (1953), 173-193. E C. Frank and J. H. v.d. Merwe, One dimensional dislocations IV. Proc. Roy. Soc. London A 201 (1950), 261-268. J. K. Perring and T. H. R. Skyrme, A mode unified field equation. Nucl. Phys. 31 (1962), 550. M. J. Ablowitz, D. J. Kaup, A. C. Newell, and H. Segur, Method for solving the sine-Gordon equation. Phys. Rev. Lett. 30 (1973), 1262-1264. S. Coleman, Classical lumps and quantum descents. Zichichi: New Phenomena in Subnuclear Physics. Plenum Press, New York (1977), pp. 297-407. J. Rubinstein, Sine-Gordon equation. J. Math. Phys. 11 (1970), 258 - 266.
Markus Heyerhoff Marienstrasse 18 58455 Witten Germany 66
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
Number Magic Unexplained. On p a g e 48 of The Intelligencer's Winter 1995 issue, the author m a d e an error s o m e w h a t d a m a g i n g to his credibility in the rest of the article. H e said that "the value of 288 is a particularly felicitous one [for erecting spurious stoichiometric uniformities], for 288 has the largest n u m ber of integer divisors of a n y n u m b e r from 0 to 576." But in fact 360 has six m o r e divisors t h a n 288 and three m o r e than 576. Such a mistake s e e m s especially regrettable in an article so d e p e n d e n t u p o n s h a r p criticism. A fun piece withal.
Charles Mus~s Mathematics & Morphology Research Centre 45911 Silver Avenue Sardis, British Columbia V2R 1Y8 Canada Editor's note: The error was made by the sharp critic H. Bull in 1941 and went undetected by The Intelligencer's author
and myself. It does not diminish by much our admiration for Dr. Bull's debunking.
An Eigenvector Proof of Fatou's Lemma for Continuous Functions Stephen Simons
Introduction In a first course on analysis, we typically teach students that continuous functions on a compact interval are bounded and attain their bounds. We also teach them about the Riemann integral and that the Riemann integral "works" under uniform convergence. In a second ~ourse on analysis, we typically teach students about measure theory and prove the Bounded Convergence Theorem for the Lebesgue integral. We also prove that a Riemann integrable function is Lebesgue integrable; consequently, the Bounded Convergence Theorem is true for the Riemann integral. So the Bounded Convergence Theorem for Riemann integration can be stated entirely in first-course-in-analysis terms, but we typically give a second-course-in-analysis proof of it. In fact, the Bounded Convergence Theorem for the Riemann integral was known many years before the arrival on the scene of measure theory (it was established by Arzela in 1885), and, even after the arrival of measure theory, a number of authors considered the problem of finding a measure-free proof of it and various generalizations of it. The problem is discussed in great detail by Luxemburg [14]. That article contains an extensive bibliography, going back to Arzelh's original proof. Measure-free proofs of the Bounded Convergence Theorem for continuous functions were obtained by E Riesz [16] (using Dini's Theorem), Eberlein [2] (using innerproduct techniques), and Simons [18, 19] (using vector lattice techniques and using a precursor of the techniques discussed in this article, respectively). Other elementary proofs, some of which apply to Riemann integrable functions with Riemann in tegrable limit, are Cunningham [ 1], Kestelman [9], and Lewin [13].
This article is in two parts. In the first part, I shall give a new first-course-in-analysis proof of the bounded convergence theorem for continuous functions on [0, 1]. The proof depends on an "Additive Diagonal Lemma" which, in turn, depends on an explicit eigenvector of a certain matrix (1). In fact, the techniques really belong in functional analysis, and in the second part of the article, I show how the "Additive Diagonal Lemma" leads to the "Sup-limsup Theorem" for Banach spaces, which not only contains the results already mentioned but also contains an abstract result on weak convergence in a Banach space that generalizes and gives insight into Rainwater's Theorem.
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3 (~)1995 Springer-Verlag New York
67
all n > 1, x,~ e Cn, and m _> 1. Then ~ _ > m (x~/2") is a b o u n d e d real function on T. We write
The B o u n d e d C o n v e r g e n c e T h e o r e m for C o n t i n u o u s Functions on [0, 1] THEOREM A. Let {xn}n>l be a bounded sequence of continuous real functions on [0, 11 and x,~ ---* 0 pointwise on [0, 1] as n --+ oo. Then f~ x,~ ~ O.
.~---d-:=
77 : for all n > m, x= E C,~
n>rn
}
I
Theorem A can easily be deduced from Theorem B. THEOREM B. Let {a:,~}n_>l be a bounded sequence of continuous real functions on [0, 1] and, for all t c [0, 1], limsup,~oo Xn(t) G O. Then l i m s u p n ~ f0~ xn _< 0.
Notation. Unless otherwise stated, the indices k, m, and n stand for strictly positive integers. We write cor {y,~ : n _> m} for
ADDITIVE D I A G O N A L LEMMA. Let T ~ 0 and {C, },~>1 be a uniformly bounded family of nonempty sets of real flmctions on T such that for all m >_ 1,
Cn Vm ~ C ~_ra-1
E
(2)
"
~ ~ rrt
Let 6 > O. Then, for all m >_ 1, there exists wm ff C~ such that wm > 2 m - l w l - ( 2
m-l-1)S(wl)-6
onT,
EIGENVECTOR LEMMA. Let ra > 1, X be the trans(111 1 1 1) pose of the vector ' 4' 8 . . . . . 2 m-3, 2 m-2, 2 m-I
zvhere,for all bounded realfunctions x on T, S (x ) := SUpT X.
and M the (m - 1) x (m - 1) matrix
Proof. For all m >_ 1, choose Zm C C,~ inductively so that
'
1 1 1
1 2 1
1 2 1
~
~
1
1
1
1
1
1
""22
...~ ...~
s
~
+ 2--;~_ ,
1
1
~0
g
g
g
:
:
:
:
:
:
1 2 m-3 1 2m-2 1 2 TM-2
1 2 TM-3 1 2m-3
1 2m-4
0
0
0
0
9-.
0
0
0
0
0
...
0
0
0
~7
+
+~-~.
00 (The i n f i m u m in the above inequality is finite because {C,},_>1 are uniformly b o u n d e d and nonempty.) For all m > 1, let tv,~ := 2m-l[~n>_r n (Z,~/2'~)] E C m - We will prove that {win}m>1 has the required properties. Let m > 1. Left-multiplying both sides of (1) by the row ( z l , . . . , z,~-l) of functions,
Then
~g
M. x = x.
(1)
+2-K~-1 2m-k -
k<m
Proof. This follows by direct computation. (We interpret the above matrix as the scalar I if m = 2, and as
(1) 0
i f m = 3.)
Notation. Let T # 0. Suppose that {Cn}n>l is a uniformly bounded family of sets of real functions on T, for 68
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
E
277
rz~m =
1
(3)
lld I
Wrn 2m_ 1 9
(4)
Using the definition of S, the fact that wk E Ck, and inequality (3), zk
+ 2-;:s-~ -<s
~
+~-;~
_<s
~
+2-w-, + a ;
2~5
= S(w~) + ~;.
2~
It follows by substituting in Eq. (4) that
S(wl)+~
E
A Generalization to Radon Measures
2--g-G-_k>w,-2m_----T.
k<m
This simplifies to wm _> 2m-lwl - (2 m-1 - 1)S(Wl) Y~'~k<m(6/2a) and gives the desired result. N o w for the proof of Theorem B.
Proof. Suppose, on the contrary, that l i m s u p , ~ f x~ > 0. Then there exists a subsequence {y, }~>1 of {Xn}n>l and 6 > 0 such that f inf l y,~ > 26. ~_>ld
(5)
Apply the Additive Diagonal Lemma with T := [0, 1] and C,~ := c % { y , : n > m} and obtain w,~ E cor : n >__m } such that
Wm >_ 2m-lwl -- (2 m-1 -- 1)S(Wl) -- t5.
(6)
From the M-test, wi is a continuous function on [0, 1]; hence there exists t c [0, 1] such that wl(t) = S(wl). Evaluating inequality %) at t and using the fact that for all x E C[0, 1], S(x) > f x, we obtain that tv.~(t) > S wl - 6.
(7)
N o w Wm E CO~{g~ : n _> m} and wi C co~{y,~ : n >_ 1}. Because )~n_>0
and
~,~n=l n>_l
I could mimic this proof of Theorem B to obtain the following result, which would normally be proved by using the Riesz Representation Theorem (to show that # can be represented by a Borel measure) and the development of measure theory up to Fatou's Lemma. THEOREM C. Let T be a compact Hausdorff space, # be a Radon probability measure on T, {Xn}n~l be a uniformly bounded sequence of continuous real functions on T, and, for all t E T, l i m s u p n _ ~ x ~ ( t ) < O. Then l i m s u p n ~ f x~ dp _< 0. I will not say any more about Theorem C, as it is contained in the more abstract Banach space results that follow.
The "Sup-limsup Theorem" for Banach Spaces In fact, the techniques discussed above belong m u c h more to functional analygis than to measure theory. I n o w state and prove the "Sup-limsup Theorem" for Banach spaces, which contains Theorem C. [Take E := C(T), F for the set of evaluations at points of T, and G for the set of Radon probability measures on T.] I will then show how the Sup-limsup Theorem gives a result on weak convergence in a Banach space that generalizes Rainwater's Theorem. SUP-LIMSUP THEOREM. Let E be a real Banach space with dual E' ; F c G c E'; and assume that for each x E E there exists an f c F such that f ( x ) = maxg~o g(x). Let {x~ }n>_l be a bounded sequence in E. Then sup limsup f(x,~) = sup limsup g(xn). f EF
we obtain sup y~(t)>_Wm(t)
n>rn
and
S w l _ > i n f S y'~" n> l
•--+oo
Proof. From the Uniform Boundedness Theorem, G is a b o u n d e d subset of E', and so {x,,}n>l gives rise to a uniformly b o u n d e d sequence of real functions on G. Let g E G and 6 > 0. Then there exists a subsequence {yn },~_>1 of {x,~}~_>l and 6 > 0 such that n_>l
inf sup gn ( t ) > inf f y~ - 6 > (5, m>_l n>_rn n>_l J that is to say, limsup y~ ( t ) >__6. This gives the result by contradiction, as
9
TI~OG
The above proof uses the M-test, and the facts that every continuous function on [0, 1] attains its supremum, and f is linear and commutes with uniform convergence.
(8)
n~cm
Apply the Additive Diagonal L e m m a with T := G and Cm := co~{y~ : n >_ m} and obtain wm E co~{yn : n _> m} such that for all f E G,
f ( w m ) > 2m-If(w1) - (2 m-1 - 1)S(Wl) - 6.
n ---*o ~
T~"--+O0
gEG
inf g(gn) > limsup g(x,~) -- 6.
Combining with inequality (7),
limsup x~(t) > limsup y~(t).
n---+oo
(9)
In this case, for all x E E, S(x) = m a x f c F f ( x ) = max f e e f ( x ) . By hypothesis, there exists f ~ F such that f ( w l ) -- S(wl). From inequality (9),
f ( w m ) >_ S(Wl) - 6 ~ g(wl) - 6. It follows from the continuity of f and g, as T H E M A T H E M A T I C A L I N T E L L I G E N C E R VOL. 17, NO. 3, 1995
69
wmEcor
and
WlECOr
and
g(wl) _> inf g(y,~).
that sup f(y,~) >_ f(wm)
n>_m
n>l
Hence, inf sup f(pn) >_ inf g(y,~)- 5;
m>_l n>_m
n>_l
did lead to a simple proof of the Sup Theorem in the separable case [8], but I still do not k n o w a simple proof in the nonseparable case. Perhaps there are also connections between these methods a n d convex analysis: In the Sup-limsup Theorem, consider S as a convex function on E. Let x E E. Let f be chosen so that f ( x ) = S(x). Then, for all y E E,
S(x) + f ( y -
that is to say, limsup f ( y ~ ) n ----*r
>
inf g(y,~) - 6. n~l
From inequality (8),
x) = f ( x ) + f ( y -
x) = f ( y ) <_ S(y);
that is to say, f is in the subdifferential of S at x. Convex analysis m a y give additional insight into the processes involved.
References
limsup f(Yn) >_ limsup g(xn) - 26. 1. E Cunningham, Taking limits under the integral sign, Math. Mag. 40 (1967), 179-186. The desired result follows because l i m s u p n ~ f ( x n ) >_ 2. W.F. Eberlein, Notes on integration h The underlying conlimsupn~.~ f(yn) and g and 6 were arbitrary. vergence theorem, Commun. Pure Appl. Math. 10 (1957), Our next result generalizes Rainwater's Theorem. (See 357- 360. 3. M. Fabian and G. Godefroy, The dual of every Asplund [15]. In Rainwater's Theorem, F is the set of extreme space admits a projectional resolution of the identity, Studia points of the unit ball of the dual of E, which has the Mathematica 91 (1988), 141 - 151. required " m a x i m u m " p r o p e r t y from the Krein-Milman 4. B. Fuchssteiner and M. Neumann, Small boundaries, Arch. Theorem. Rainwater's proof required the C h o q u e t Math. 30 (1978), 613-621. Bishop-De Leeuw T h e o r e m to produce a R a d o n mea5. G. Godefroy, Boundaries of a convex set and interpolation sets, Math. Ann. 277 (1987), 173 - 184. sure, and then the a p p a r a t u s of measure t h e o r y exactly 6. G. Godefroy, Five lectures in geometry of Banach spaces, as in Theorem C.) The present proof shows that RainwaSeminar on Functional Analysir Vol. 1 (1987), Univ. de ter's Theorem does not really d e p e n d on the properties Murcia. of extreme points as m u c h as the property of " m a x i m u m 7. G. Godefroy and V. Zizler, Roughness properties of norms boundaries." on non Asplund spaces, Mich. Math. J. 38 (1991), 461-466. 8. R. C. James, Reflexivity and the sup of linear functionals, THEOREM ON WEAK CONVERGENCE. L e t E be a Israel J. Math. 13 (1972), 289-300. 9. H. Kestelman, Riemann integration of limit functions, real Banach space with dual E'. Suppose that F is a subset Amer. Math. Monthly, 77 (1970), 182-187. of the unit ball of E' and, for all x E E, there exists f E F 10. H. K6nig, Two theorems in superconvex analysis, General such that f ( x ) = Hxl]. Let {Vn}n_>l be a bounded sequence in Inequalities 4, Basel: Birkh/iuser (1984), 203-211. E, v E E, and, for all f E F, f(vn) -* f(v). Then vn -* v 11. H. K6nig, Theory and applications of superconvex spaces, weakly. Aspects of Positivity in Functional Analysis, R. Nagel, U. Schlotterbeck and M. P. H. Wolff, eds., Elsevier Science Proof. Let G be the unit ball of E'. The result follows from Publishers (North-Holland) (1986), 79-117. two applications of the Sup-limsup Theorem, first with 12. H. K6nig, On the Main Theorems of Superconvex Analyx~ := v,~ - v and then with Xn := v - vn. sis, Okonomie und Mathematik, Heidelberg: Springer-Verlag (1987), 29- 34. More history and connections. The analysis pre13. J. W. Lewin, A truly elementary approach to the bounded convergence theorem, Amer. Math. Monthly 93 (1986), 395sented here is suggested by [12], which is the culmi397. nation of a series of papers by K6nig [10-12], Kremp 14. W.A.J. Luxemburg, Arzela's dominated convergence thea n d Kiihn on "Superconvexity," an axiomatic theory of orem for the Riemann integral, Amer. Math. Monthly 78 countable convex combinations introduced b y Rod6 [17]. (1971), 970-979. 15. J. Rainwater, Weak convergence of bounded sequences, These techniques were applied to abstract b o u n d a r y theProc. Amer. Math. Soc. 14 (1963), 999. ory by Fuchssteiner and N e u m a n n [4] and, more recently, 16. E Riesz, Uber Integration unendlicher Folgen, Jahresb. to the geometry of Banach spaces by Fabian, Godefroy, Deutscher Math.-Verein. 26 (1917), 274-278. and Zizler [3, 5 - 7]. The proof here is m u c h simpler, and 17. G. Rod6, Superkonvexe Analysis, Arch. Math. 34 (1980), shows the s o m e w h a t unexpected connection with eigen452- 462. vectors. 18. S. Simons, A theorem on lattice-ordered groups, results of Pt~k, Namioka and Banach, and a front-ended proof of What I had been trying to do, actually, was to obLebesgue's Theorem, PacificJ. Math. 20 (1967), 149-153. tain a simple proof of something apparently unrelated, 19. S. Simons, A convergence theory with boundary, Pacific]. R. C. James's Sup Theorem: Let B be a nonempty bounded Math. 40 (1972), 703-708. closed convex subset of a Banach space E and assume every Department of Mathematics continuous linear functional on E attains its maximum on B. University of California Then B is weakly compact. The techniques discussed here Santa Barbara, CA 93106-3080, USA n~oo
70
r~~ oG,
T H E MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
Jet Wimp*
Solving the Quintic (Educational Poster) Wolfram Research, Inc., Champaign, IL, USA
13
p= -~b
R e v i e w e d by Eric Schechter
~s every high school student knows, the quadratic equation a x 2 + b x + c = 0 has solutions X ~-
- b + v ~ - 4ac 2a
These solutions were, essentially, known to the ancient Babylonians, although of course they did not use our notation. Millennia passed before substantial further progress was made on the solution of polynomial equations. In 1539 Cardano published the solutions to the general cubic and quartic polynomial equations. Most high school students - - and many mathematicians-- are not familiar with these formulas, but the formulas are interesting and do not require group theory or other advanced notions. We sketch them here, although not using Cardano's notation. To solve the cubic equation, first divide through by the leading coefficient to write the equation x3+bx2+cx +d = 0. A solution is given by Cardano's formula, 1 where * C o l u m n Editor's address: Department of Mathematics, Drexel University, Philadelphia, PA 19104 USA.
+
1
b c - ~d,
q= ~c-
b2.
The quartic equation x 4 + bx 3 + cx 2 + dx q- r = 0 is just more of [he s a m e - - much more, in fact; its formula is quite long. The solution (due to Cardno's student, Ferrari) can be described more elegantly with a method than with a formula. First "complete the square," to write the given quartic polynomial so that it is nearly the square of a quadratic polynomial; there will be a quadratic remainder term. If we insert an arbitrary constant z (which is to be selected later), then the given quartic equation can be rewritten X2 q- T
q- Z
=-
-- C + 2Z
x2+(bz-d)x+(z2-e).
We can solve this by taking square roots on both sides, if the right side happens to be a perfect square. A quadratic px 2 q- qx q- v is a perfect s q u a r e - - t h a t is, of the form p(z + s) 2 for some constant s - - i f and only if q2 = 4pr. In terms of the previous constants, that condition says
c+2z) 2 which is a cubic equation in z. Solve for z, and then for z. We note that the problem of representing solutions of the cubic or quartic in terms of roots is not necessarily solved in a practical sense, for the expressions for the roots may require finding cube roots of complex numbers even when the equation is known to have real roots.
THE MATHEMATICALINTELLIGENCERVOL.17, NO. 3 (~)1995Springer-VerlagNew York 71
For instance, x 3 + 6x 2 -I- 3x - 12 -- 0 has three real roots, but Cardano's formula yields p = 1, q = -3, and p 2 + q3 = -26. The fifth-degree equation is still more difficult. We know that it has five complex roots by the Fundamental Theorem of Algebra. At least some quintic equations have solutions which can be expressed in terms of radicals. For instance, one of the solutions of x ~+ 20x + 32 = 0 is
_!5 ~/2500 v~ + 250 V/50 - 10 v~ - 750 v/50 + 10 v~ +-~ ~/2500 v~ - 250 x/50 + 10 v~ - 750 v/50 - 10 v~ +1 ~/2S00 v~ + 250 v/S0 + 10 v/5 + 750 v/S0 - 10 v~ _!s ~/2500 v~ - 250 v/S0 - 10 v~ + 750 v/50 + 10 v~. Examples like the above could lead one to expect that the general fifth-degree polynomial equation, like the equations of lower degree, can be solved by a formula using roots and arithmetic operations. Mathematicians tried for many years to find such a formula. Finally, in 1826 Abel showed that such a formula is not possible, and by 1832 Galois had developed a theory which describes exactly when a polynomial equation is solvable by radicals. It depends on the solvability of certain groups, called Galois groups, associated with the equation. For instance, the polynomial 2x 5 - 2x + 1 has Galois group $5, which is not solvable, so the five roots of 2x s - 2x + 1 cannot be represented in terms of radicals. How can the roots of higher-order equations be represented? If we cannot solve such an equation in the spirit of Cardano, in what sense can we "solve" it? If nth roots are not enough, we need some other kinds of functions. In 1858 Hermite, Kronecker, and Brioschi showed how to solve quintics in terms of nth roots and elliptic modular functions; in 1877 Klein showed how to solve quintics in terms of nth roots and the hypergeometric function. The hypergeometric function, first extensively studied by Gauss, is a three-parameter generalization of the geometric function (1 - z)-% For tzi < I it has the convergent series representation o~
F(a,b;c;z) = E (a)k(b)a zk" k--o (c)kk! c # 0,-1~-2,...,
(a)k =
a(a+l)(a+2).-.(a+k-1), 1,
k#0 k=0.
A key step in these solutions was a transformation due to Tschirnhaus (1683). The transformation is too complicated to describe in complete detail here, but I can describe an easy part of it. Any polynomial equation 72 THE MATHEMATICALINTELLIGENCERVOL. 17, NO. 3,1995
X n q- a n - i x n - 1 q- a n - 2 x n - 2 q- " " 9 q- a l x + ao = 0
can be transformed by the affine substitution x=y
vfa
n-2
n - 1 ~
an-1
a2n-1
n
to yield a new polynomial equation of the form yn + y n - 2 q_ b n _ 3 g n - 3 q_ b n _ 4 y n - 4 q_ . . . q_ bly -4- bo = O,
where the bj's are known constants. Note that b n - 1 = 0 and bn-2 = 1. Tschirnhaus investigated much more complicated transformations; one of these reduces any quintic polynomial equation to an equation of the form t 5 - t - p = 0, where p can be expressed in terms of the original coefficients using radicals. The methods of Hermite, et al., although theoretically complete, are enormously complicated. They are not practical for everyday computations like the quadratic formula, or even for occasional computations like the formulas published by Cardano. They could not be used effectively until the arrival of electronic computers and, more particularly, Mathematica. We may think of Mathematica as a fancy programmable calculator; in addition to the usual "sin" and "log" buttons, it also has "elliptic" and "hypergeometric" buttons. With Mathematica, the solution of the quintic becomes feasible, but it is still very complicated. Of course, to find numerical solutions to particular equations, we don't really need elliptic or hypergeometric functions. All we really need is a simple iterative scheme such as Newton's method. However, the decimal numbers generated by such a method would have no evident pattern; they would seem to be arranged randomly. Our real reason for studying the ideas of Cardano, Galois, and others is for the theoretical understanding they give us concerning the orderly, nonrandom structure of the sets of solutions. So, too, the real reason for implementing Hermite's solution in Mathematica is not to crank out solutions of particular polynomial equations, but to understand better both Hermite's solution and Mathematica's capabilities. The work being reviewed is not a book, but a wall poster produced by Wolfram Research, the makers of Mathematica. The poster measures about 27 in. (68 cm) wide and 38 in. (97 cm) tall. It is titled "Solving the Quintic" in large letters across the top; across the bottom it says "with Mathematica" in letters which are nearly as large. Most of the poster is filled with five columns of text, but the poster also includes many small pictures, plus one large (8 in. by 13 in.) picture of the Riemann surface for the quintic t s - t - p. The rightmost column of text is a chronology, with one to three sentences for each year listed, from 2000 B.C., (Babylonian solution of the quadratic) to 1992 (solutions of solvable quintics, by Dummit, Kobayashi, and Nakagawa). It is enlivened by small black and white pictures of old texts, of computing devices, and of many
of the mathematicians listed in the chronology. There is room for disagreement here: Most historians credit Abel (1826) with founding the abstract theory of groups and with proving the unsolvability of the general quintic, but some historians give Ruffini (1799) part of the credit; the poster gives Abel and Ruffini approximately equal credit. (Ruffini's arguments, although muddled and incomplete, were mostly pointed in the right direction.) The poster's two left columns of text briefly introduce some of the theory of the quintic-- the Tschirnhaus transformation, solutions based on series, solutions based on differential equations, and so forth. A sidebar in the lower left corner of the poster introduces hypergeometric functions, theta functions, and elliptic modular functions. Sprinkled throughout these discussions are formulas from Mathematica which illustrate the ideas more conc r e t e l y - at least, if the reader is familiar with Mathematica. The version of Mathematica used in the poster is not the current release (version 2.2), but a new version which is in preparation by Wolfram Research. The third and fourth columns of text are taken up by Mathematica's solutions of the general polynomial equations of degree 2, 3, 4, and 5. For degrees less than 5, it's very easy--Mathematica knows how to solve those equations algebraically. For instance, in the forthcoming version, if you input Solve [ax 2 + bx + c = O, x],
grams and text of the poster plus additional information (including a bibliography of over 400 books and articles), in the form of several Mathematica notebooks. You can get these notebooks from mathsource.wri.com by anonymous ftp; look in the subdirectory "pub/NumberedItems". Issue a '%inary" command and then use either "mget 0207-199"" if you want the formatted versions, or "mget 0207-122"" if you want the plain text versions. You may want to skip the file 0207-122- 0066 or 0207-199-0066, which is an 8-megabyte graphics file; the other notebooks are of more modest size. The poster can be ordered by: United States or Asia
Europe
Voice phone 1-800-441-MATH +44-(0)1993-883400 Fax 2 1 7 - 3 9 8 - 0 7 4 7 +44-(0)1993-883800 E-mail
[email protected] [email protected] In the United States the price is $2 for the poster plus $5 for shipping and handling. The reviewer is grateful to Richard Arenstorf, Steven Tschantz, and the editor for several helpful discussions and suggestions. Department of Mathematics Vanderbilt University Nashville, TN 37240 USA e-mail:
[email protected]
the resulting output will be x ---*
2a
,
x ---*
2a
"
An analogous procedure works for degrees 3 and 4. The output for degree 4 is extremely long, so it is shown on the poster in very tiny p r i n t - - s o tiny, in fact, that it is impossible to read. Still, it's readable on your computer screen if you run Mathematica, and the poster serves to demonstrate the power of Mathematica. The poster then continues with an implementation in Mathematica of Hermite's solution of the quintic. One of the reviewer's colleagues modified that implementation, to make it run under version 2.2. We found it more cumbersome than practical, but it was an educational experience. The poster is pleasant to look at, and its many tidbits of information may entice a newcomer to study this subject further. However, the poster does not constitute a whole introduction to the subject. For instance, the poster includes a picture of an icosahedron and another picture of circles inside a pentagon; the captions of these pictures mention that quintics are "related to" icosahedrons but give no indication of what the relationship is. The poster is just a beginning. Wolfram Research has made available via Internet at no charge, the pro-
The Biographical Dictionary of Scientists, Second Edition Roy Porter, Consultant Editor New York: Oxford University Press, 1994. lvii + 891 pp. Hardcover. ISBN 0-19-521083-2
Reviewed by Donald M. Davis The Biographical Dictionary of Scientists is a nice reference for learning a little bit about the lives and mathematical contributions of the great mathematicians, but don't plan to use it to learn mathematics. It contains biographies of approximately 140 mathematicians and approximately the same number of biographies for the other sciences: Astronomy, Biology, Chemistry, Engineering and Technology, Geology, and Physics. These biographies average slightly less than one large dense page and are generally arranged in the following standard format. First, there is a short paragraph summarizing the person's achievements. Then there are one or more paragraphs about the person's birth, education, employment, and nonscientific aspects of the life. Next, there are one or more paragraphs about the person's scientific achievements. Finally, there may be a summary paragraph, putting the person's achievements into perspective. THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
73
There is also a six-page s u m m a r y history of mathematics, weaving all these people together, and a dictionary of scientific terms, w h e r e you can learn such things as Euclid's fifth postulate states that parallel lines meet only at infinity. manifold in two-dimensional space, a regular surface that locally looks like a fiat plane slightly distorted. M a n y other definitions contain little (or not so little) mistakes such as these, and similar problems in the biographies themselves convince me that the mathematical part either was not written by a mathematician or was mutilated by a copy editor. (I d o n ' t have the expertise to judge whether the summaries of the other sciences are equally flawed.) I did enjoy reading this book, and think it should be a part of a mathematics d e p a r t m e n t library. I enjoyed the personal histories more than the discussions of the mathematical contributions. I found it interesting to read about m a n y famous mathematicians w h o h a d been actively involved in politics, usually to the detriment of their mathematical work. Monge is perhaps foremost in this regard; he was a close friend and advisor of Napoleon. By the time the French Revolution broke out in 1789, Monge was one of the most celebrated of French scientists. He was an earnest supporter of the radicals and joined several revolutionary clubs and societies. In 1792, he was appointed Minister of the Navy, but as the revolution took its speedy course towards the Terror, he was discovered (despite his association with the left-wing Jacobins) to be a moderate and he resigned his post in April 1793. Thereafter he held no overt political position, although he was a member of the Committee on Arms in 1793-1794 and did important work in supervising the Paris armaments workshops and in helping to develop military balloons .... In 1796, Monge's friendship with Napoleon began. Having conquered Italy, the revolutionary French government decided to plunder the country of its artistic and scientific treasures and Monge was sent, as a member of the Commission des Sciences et des Arts en Italie, to assist in the selection of objects to be removed to France. He met Napoleon briefly, but was then recalled to France in 1797 to take up a new appointment as director of the Ecole Polytechnique. He then went back to Italy in 1798, this time as a member of a mission to inquire into the country's political organization. While he was there, he was invited by Napoleon to assist in the preparation for the Egyptian campaign; he then accompanied Napoleon on the expedition to Egypt and was appointed president of the Institut d'Egypte established at Cairo in 1798.... He had scarcely begun to resume his duties as director of the Ecole Polytechnique when the coup d'dtat of 18 Brumaire placed Napoleon in control of the French government. Two months later Napoleon appointed him a senator for life and he resigned the directorship of the Ecole Polytechnique. For the rest of Napoleon's ascendancy Monge assumed the role of the foremost scientific supporter of the imperial regime. He was rewarded by being made 0 Grand Officer of the Legion of Honour in 1804, President of the Senate in 1806, and the Count of Peluse in 1808. His creative scientific life was now a thing of the past, but in the leisure which freedom from onerous official appointments allowed, Monge 74
THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
brought together his life's work in a number of publications: Gdomdtrie Descriptive (1799), Feuilles d'Analyse Appliqudes ~ la Gdomdtrie (1801), its expanded version (1807), and several smaller works on infinitesimal and analytical geometry.... When Napoleon was finally overthrown in 1815, Monge was discredited. In 1816 he was expelled from the Institut (the renamed Academy of Sciences), and on 28 July 1818 he died in Paris. Monge was one of the most wide-ranging scientists and mathematicians of his age. In the years between 1785 and 1789, for example, he submitted to the Academy of Sciences papers or notes on an astonishing variety of subjects: the composition of nitrous acid, the generation of curved surfaces, finite difference equations and partial differential equations (1785); double refraction, the composition of iron and steel and the action of electric sparks on carbon dioxide (1786); capillary phenomena (1787); and the physiological aspects of optics (1789). He holds an honoured place in the history of chemistry, not simply for his independent synthesis of water, but also for working with Lavoisier in 1785 in the epoch-making experiments on the synthesis and analysis of water. The article points out that M o n g e introduced contact transformations, which were to be generalized by Sophus Lie a century later. Because of his interesting life, there is m o r e text about Monge than anyone else who is primarily a mathematician. N e w t o n has the most text of anyone, but he is listed as a physicist first and mathematician second. Cauchy and Volterra lost academic positions for political reasons, Leibniz and Wallis w e r e active in politics at a high level before they m a d e their main mathematical contributions, and Betti and Emile Borel obtained high political positions at the end of their careers. Religion also featured prominently in the lives of m a n y famous mathematicians. Everyone knows of the m a n y European Jews w h o came to America with the rise of Hitler. However, I didn't realize that G6del failed to get one position because it was erroneously thought that he was Jewish, or that Hausdorff c o m m i t t e d suicide, along with his wife and her sister, in order to avoid being sent to an internment camp. The story of the highs and lows in the life of Sylvester, some d u e to his being Jewish, are quite fascinating. DeMoivre is another w h o had a turbulent life affected b y religion, he being Protestant in Catholic France. Cayley was a l a w y e r for m a n y years because he refused to take u p religious orders at Cambridge. Here are a few other things that I was interested to learn. Perhaps I should already have k n o w n them. 1. Determinants were probably discovered by Leibniz in 1693, but didn't receive m u c h attention until C r a m e r ' s Rule in 1750. 2. Markov's original example of a Markov chain was the occurrence of consonants and vowels in Pushkin. 3. Peano's axioms for natural n u m b e r s were first discovered by Dedekind. 4. Napier invented the decimal point, and Lagrange was the father of the metric system.
Some of the summaries I thought particularly good were those of Beltrami (he brought non-Euclidean geometry into the mainstream of mathematical thought), Courant (his principal contributions were as administrator and writer), and Frege-(he was devastated by Russell's paradox). Now for the criticism. First, we have the major mathematical mistakes:
3. In Fermat's bio, the editors note, correctly, that the Fermat-Pascal correspondence resulted in the foundation of probability theory. But they err in saying that their conclusion was the formula for the probability of the intersection of independent events. They do a better job in Pascal's bio. 4. There is nothing about Gauss's work in geometry; indeed, precious little about any of Gauss's work. 5. Euler is described as a "prolific author," but nowhere is it mentioned that he was the most prolific mathematician in history. 6. The discussion of the four-color theorem in M6bius's bio seems terribly naive, as illustrated by the sentences "Neither M6bius nor anyone else has ever found a five-color solution. Recently, it has been proved by computer analysis that four colors always suffice." The second sentence is fine, and the first sentence isn't wrong, but it isn't said the way a mathematician would say it. 7. It says that Poincar6 is-the originator of the study of algebraic topology, but no more. Nothing is said about Poincar6 duality or the Poincar6 conjecture or his introduction of the fundamental group and what we now call homology groups. 8. Nothing is said in Riemann's bio about his work in number theory, and in particular about the Riemann hypothesis. 9. Although Russell's paradox is discussed in Frege's bio, it is not mentioned in Russell's bio.
1. The editors say that Diophantus's innovation was using a symbol to represent the unknown. Nowhere do they say that Diophantine equations are only concerned with rational solutions. 2. Frequently (for example, in Eilenberg's biography), they say that topology is the study of figures and shapes that retain their essential properties when twisted or stretched. Rather, it is the study of properties that remain invariant under certain types of deformation. 3. There is much confusion about Euclid's parallel postulate. There is the misstatement in the definition already mentioned. In the Bolyai biography, the editors state it correctly, but then botch it by saying, "... or, in layman's language, that parallel lines do not meet." There is also a confusing statement in Clifford's bio, where I think they mean "parallels not in the same plane" rather than their "not in the same place," but even then the statement doesn't make sense. 4. There are misstatements about angle sums in nonEuclidean geometry. In Riemann's bio, the editors Finally, I have quibbles about who is included. I realwrite that the sum of the angles of a quadrilateral on ize that this is just a matter of taste, but here are some a sphere is less than 360 degrees, whereas in Dehn's of my opinions. bio, there is confusion about his work regarding an1. I don't think the philosopher Max Black, the histogle sums and Archimedes's axiom. rian Florian Cajori, or the writer Charles Dodgson 5. Displayed equations are frequently wrong. In the should have been included. They were not imporequation of the catenary in Euler's bio, e x/a has betant scientists. come e~/a. Lindemann's proof of the transcendence 2. I think that Tchebycheff, Cardano, and the ancient of 7r is correct in outline, but the details are comIndian Bhaskara should have been included. pletely botched. First, ea' is written eai. Then the 3. The living mathematicians who are included are equation e i~ = -1 is written I i~ = -1. Finally, ~r Baker, Mandelbrot, Penrose, Thorn, Weil, and Zeeis written as p. man. Both Thom and Zeeman made important conNext, there are the minor mistakes, such as saying tributions to topology prior to their work on catasGalois was concerned with the question whether firsttrophe theory. Thorn's early work on classification degree equations were solvable by radicals, that Gauss of manifolds is discussed, and quite possibly justifies added the first 101 digits, that A. N. Whitehead went to his inclusion. For Zeeman, only his work on catastroHarvard in New York; Clifford is renamed Church sevphe theory is mentioned. I don't feel that this justifies eral times. In addition, there are the following errors of his inclusion. I would rather see Atiyah or perhaps omission or emphasis: Serre in place of Zeeman. 1. There is no mention of B~ouwer's work in topology. 2. Cauchy is given "credit for 16 fundamental concepts and theorems in mathematics and mathematical physics, more than for any other mathematician." (I wonder who decides what constitutes a "fundamental concept;" and I am surprised that Cauchy would come out ahead of Gauss or Euler.)
All this criticism notwithstanding, I still think this is a worthwhile book. However, I would hesitate to try to learn about another scientific discipline from it, given its track record in mathematics. Lehigh University Bethlehem, PA 18015, USA e-mail:
[email protected] THE MATHEMATICAL INTELLIGENCER VOL. 17, NO. 3, 1995
75
Robin Wilson* Mathematical Physics I Keith Hannabuss and Robin Wilson One of the founders of statistical physics was James C l e r k M a x w e l l (1831-1879). He worked on colour vision and took some of the earliest colour photographs, but it is for his electromagnetic theory that he is especially remembered. Using the most advanced vector analysis of his day, he synthesized Michael Faraday's laws of electromagnetism into a coherent mathematical theory that confirmed Faraday's intuition that light consists of electromagnetic waves. It was while seeking experimental confirmation of this that Heinrich Hertz (1857-1894) discovered radio waves. H e n d r i k A n t o o n L o r e n t z (1853-1928) showed how Maxwell's electromagnetic waves interact with matter consisting of atoms within which are distributions of electric charge. His prediction that strong magnetic fields would modify the spectral lines of atoms was confirmed by his pupil Pieter Zeeman, with whom he shared the 1902 Nobel prize for physics. Lorentz transformations were discovered by Lorentz in 1904, but their significance became apparent only when Albert Einstein (18791955) published his papers on special relativity in the following year.
Until that time it had been assumed that Maxwell's equations are directly valid only in a particular frame of reference (that of the luminiferous ether that carried the waves), and were thus quite unlike Newton"s laws of mechanics, which hold for all observers in uniform motion. Einstein reconciled this apparent discrepancy by starting from the postulate that the basic laws of physics (including Maxwell's equations) are the same for all observers in uniform motion relative to one another. This led him to his famous equation E = m c 2, relating energy E and mass m via the speed c at which electromagnetic waves propagate. Ten years later, in his general theory of relativity, Einstein extended his earlier work to encompass accelerated motion and gravity. The general theory made extensive use of the newly developed ideas of higherdimensional differential geometry, and in turn served to stimulate many further developments of that subject.
One of Maxwell's Equations
Einstein's Energy Law Hertz and Maxwell
H.A. Lorentz
* Column editor's address: Facultyof Mathematics, The Open University,Milton Keynes,MK76AA,England.
76 THEMATHEMATICAL INTELLIGENCER VOL. 17, NO. 3 (~1995 Springer-Verlag New York
Albert Einstein
