No title

The Mathematical Intelligencer encourages comments about the material in this issue. Letters to the editor should be sent to the editor-in-chief, Sheldon Axler,

The Mandelbrot Set It is with some trepidation that I enter into a controversy (Opinion column, Mathematical Intelligencer, vol. 11, no. 4) which is clearly completely overheated and more than a little pointless. I only hope that I can add a little bit of flesh air and cold water to the subject. Regarding the issue of who invented what is now k n o w n as the Mandelbrot set, I think it is worth keeping in mind that Fatou had a pretty complete picture of the whole state of affairs by about 1920. There is absolutely no doubt in my mind that if Fatou had had access to modern computing facilities, he could have and would have drawn pretty much the same pictures that Matelski, Mandelbrot, and I did about sixty years later. The same is certainly true of a large n u m b e r of workers in the field in the intervening years. Frankly, I w o u l d be hard put to claim too much credit for what amounts to having lived during the computer revolution. But even without the aid of the computer, Fatou was led to a rather penetrating insight into the dynamical behavior of rational functions--some of which he could prove, some of which he only c o n j e c t u r e d - which stands up very well in comparison with all that has come since. I would recommend that anyone interested in the subject read Fatou's paper (P. Fatou, M6moire sur les 6quations fonctionnelles, Bull. Soc. Math. France, I: vol. 47 (1919), pp. 161-271; Ih vol. 47 (1920), pp. 33-94, III: vol. 47 (1920), pp. 208-314). It is a masterpiece of what might be called "descriptive mathematics." I feel I must comment on Mandelbrot's remark that Matelski and I were "close to something that was to prove special, but they gave no thought to the picture." I don't know h o w he can be so sure of what we gave thought to and what we d i d n ' t - - w e are not particularly fond of the idea of publishing our philosophical musings or our half-baked s c h e m e s - - b u t the bottom line is really in the first part of his phrase. If, after all this public bellowing, Mandelbrot can really believe

that this set is something special, then he is really and truly not listening to himself. Just as the coast of England is not really very different from all the other coastlines of the world, the Mandelbrot set is just one (and certainly neither the first nor the last) of a whole universe of mathematical curiosities, which reflect various types of beauty and subtlety in nature and in the world of the mind. For me to have spent too much time on this one curio w o u l d have meant spending less time elsewhere, and to my taste would have reflected a rather infantile and somewhat dull mathematical sensibility. I may have been mistaken on this point, but I would certainly invite Mandelbrot to peruse some of m y other papers to decide if I made the right choice. My only request is that he not announce his verdict in print.

Robert Brooks Department of Mathematics UCLA Los Angeles, CA 90024-1555 USA .FractalsThis letter is a response to the Opinion Column in the last issue of the Mathematical Intelligencer, which contained Steven Krantz's book review and Benoit Mandelbrot's rejoinder. As your readers might recall, the books in question were a collection edited by H.-O. Peitgen and D. Saupe, and also The Beauty of Fractals: Images of Complex Dynamical Systems by Peitgen and P. Richter. I know the latter book very well indeed since it is r e c o m m e n d e d reading in m y undergraduate course on computer studies of chaos. Somehow, in all the discussion, the qualities of this book did not get very much attention. The Beauty of Fractals is simply a lovely book, and it is in itself a very solid contribution to intellectual discourse. It is aimed at the intelligent and well-educated general reader w h o has a good mathematical background. It does contain some real mathematics. A1-

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1 9 1990 Springer-Verlag New York

3

though the book does not give proofs, Peitgen and Richter do give careful statements of elegant theorems by Adrien Douady, John Hubbard, and Dennis Sullivan, among others. And, in addition, they give some very beautiful pictures of the mathematical objects under discussion, which mostly are sets bearing the names of Julia and Mandelbrot. Furthermore, The Beauty of Fractals tells how the pictures are related to the theorems and in what ways an examination of one will tell you more about the other. This book suggests and illustrates the proposition that a combined process of looking, thinking, and proving is one possible road to truth (and to beauty). I think that The Beauty of Fractals is likely to be a classic.

Leo P. Kadanoff The ResearchInstitutes The University of Chicago 5640 S. Ellis Avenue Chicago, IL 60637 USA Proof as Explanation. James Gleick in his rejoinder (Mathematical Intelligencer, vol. 11, no. 3) to the article of Morris Hirsch has, it seems to me, missed an important point. He writes "there are times w h e n mathematical proof (essential t h o u g h it is!) c o m e s , historically, as an afterthought . . . . Lanford's proof of Feigenbaum was ingenious and admirable, but it did little, really, to validate Feigenbaum's b r e a k t h o u g h - - e x p e r i m e n t s accomplished that." The point is that Lanford and other mathematicians were not trying to validate Feigenbaum's results any more than, say, N e w t o n was trying to validate the discoveries of Kepler on the planetary orbits. In both cases the validity of the results was never in question. What was missing was the explanation. Why were the orbits ellipses? Why did they satisfy these particular algebraic relations? In his celebrated "afterthought" Newton provided the explanation while, incidentally, adhering meticulously to the "theorem-proof methodology" which, according to Gleick and Keith Devlin, "most scientists find peculiar." I believe many mathematicians share Gleick's excitement over the fascinating experimental discoveries of Feigenbaum as well as the beautiful self-symmetries of the Julia sets, the omnipresence of the Mandelbrot set, and so on. Indeed, these things have been a wonderful shot in the arm for mathematics, providing a whole new range of mathematical phenomena, phenomena which, to a mathematician, fairly cry out for explanation. T h a n k s to the work of Lanford and others one can now account for a great m a n y of these experimental results, though I'm told there still remain some challenging mysteries. But, to return to m y point, there's a world of difference b e t w e e n validating and explaining. Physics wouldn't be much of a science if physicists simply 4

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

measured and recorded the light spectra of the various elements and let it go at that. The main goal of all science is first to observe and then to explain phenomena. In mathematics the explanation is the proof. It's as simple as that, and I doubt that any scientist who understands this can find our methodology peculiar. I can well imagine that some scientists might find it peculiar that a person is willing to devote a lifetime to, say, trying to find out if the 3-sphere is the only simply connected 3-manifold, but given that that's what one wants to do there is nothing peculiar about using the theorem-proof methodology, because in fact it's the only methodology there is.

David Gale Department of Mathematics University of California Berkeley, CA 94720 USA -Hausdorff I am pleased to see that recently the "Years Ago" column in the Mathematical Intelligencer (vol. 11, no. 1, 1989) was devoted to Felix Hausdorff and his epochmaking work. I would like to add a few comments designed to accentuate certain aspects of Hausdorff's personality and of his Grundziige der Mengenlehre. On page 62 of the Grundziige one finds unmistakable evidence of the author's musical bent of mind. Indeed, Hausdorff's love and talent for music were evident quite early; it was on his father's insistence that he abandoned his plan to study music. Hausdorff nevertheless retained his interest in music, literature, philosophy, and fine arts; and during his early professional career, he devoted at least as much time to these pursuits as he did to mathematics. Under the pseudonym Paul Mongr6, he published as many as four literary works of no mean accomplishment (these are discussed at some length in [Krull]). But it is his mathematical development that deserves to be studied more closely. The astonishing fact remains that prior to the appearance of the Grundz~ige, Hausdorff had not published anything at all on what must be regarded as the most original and influential part of the w o r k - - t h e theory of topological and metric spaces (chapters 7, 8, 9). As Katetov says [article on Hausdorff, Dictionary of Scientific Biography, vol. 6 (1981), p. 176], "The Grundziige is a very rare case in mathematical literature; the foundations of a new discipline are laid without the support of any previously published comprehensive work." Interestingly enough, the preface of the Grundziige reveals Hausdorff's own views on his labors. Expressing the hope that while the book might profitably be read by a student of the middle semesters (i.e., an advanced undergraduate), he declares that it would have failed its purpose if it did not offer the profes-

sional colleagues something new, at least in methodological and formal aspects. Saying that one should logically and systematically organize scattered facts, remove unnecessarily special or complicating assumptions from previous results, that one should strive for attaining simplicity and generality--surely the minimum that can be demanded of an author dealing with material already treated by o t h e r s - - H a u s d o r f f expresses his belief of having reasonably fulfilled this demand and of having opened some new lines of inquiry. He points out, especially, that by axiomatizing point-set theory, many theorems on point-sets on the real line have been so transformed, generalized, decomposed, and tied up in another context that a mere reference to the existing literature would give no correct picture. Thus, despite these rather modest and unassuming words, there is no question that Hausdorff was aware of what he had accomplished with this book. So, while he was no doubt pleased with the impact created by the Grundz~ige on the subsequent development, he was hardly surprised. The definition of a topological space by means of a set of axioms on neighborhoods (p. 213) is, beyond question, Hausdorff's greatest contribution. The concept of a n e i g h b o r h o o d as such was, of course, nothing new; Hausdorff's great credit was to make it the point of departure for an axiomatic development --abstract in form, but as Bourbaki has observed [General Topology, Part I, Addison-Wesley, 1966, p. 166 (Historical Note to Chapter I)], adapted in advance to a p p l i c a t i o n s - - a n d to have found the right set of axioms. That, in analogy with metric spaces, he incorporated the separation axiom since named after him, detracts nothing from this credit. The Grundz~ige was the source to which the spectacular rise of point-set topology in the 1920s and 1930s is due. Many of the basic notions and concepts of the subject that are to be found h e r e - - e v e n the name metric space (the concept itself is due to Fr6chet)--have come down to us unaltered; one has to e n v y Hausdorff for his singular acumen and extraordinary foresight. On the personal side, it is interesting to note that within a year of Hausdorff's appointment as Extraordinarius (ausserordentlicher Professor) at Leipzig, he received a similar call to GOttingen, but it was turned down. Considering the reputation of GOttingen in those days, this appears mystifying. According to Wolgang Krull, the eminent algebraist w h o was Hausdorff's colleague at Bonn from 1928, the refusal definitely harmed his academic career ([Krull], p. 54). As early as 1932, Hausdorff could sense the oncoming calamity of Nazism; but he made no serious attempt to emigrate while this was still possible. A memorial plaque to Hausdorff was unveiled at the entrance of the Mathematical Institute of the University of Bonn (Wegelerstrasse 10) on 25 January 1980. It bears the inscription:

AN DIESER UNIVERSITAT WIRKTE, 1921-1935 DER MATHEMATIKER FELIX HAUSDORFF 8.11.1868- 26.1.1942 ER WURDE VON DEN NATIONALSOZIALISTEN IN DEN TOD GETRIEBEN, WEIL ER JUDE WAR. MIT IHM E H I ~ N WIR ALLE OPFER DER TYRANNEI. NIE WIEDER GEWALTHERRSCHAFT UND KRIEG! (At this University worked, 1921-1935, the mathematician Felix Hausdorff: 8.11.1868-26.1.1942. He was driven to death by the national-socialists, because he was a Jew. With him we honor all victims of the tyranny. Never again dictatorship and war!)

Bibliography W. Krull, Felix Hausdorff 1868-1942, Bonner Gelehrte (Beitr~igezur Geschichte der Wissenschaflen in Bonn, Mathematik und Naturwissenschaften), Bonn: Universit/it Bonn (1970), 54-69. H. Mehrtens, Felix Hausdorff--Ein Mathematiker seiner Zeit (40 pp.), Bonn: Mathematisches Institut der Universit/it Bonn (1980).

M. R. Chowdhury Department of Mathematics University of Dhaka Dhaka-lO00, Bangladesh

DirichletVol. 10, no. 2, 1988, of the Mathematical Intelligencer contains a fascinating article by David Rowe on Dirichlet's early mathematical achievements. Unique evidence on his working procedure is provided in a letter written by Dirichlet in October 1827 to his mother. The letter is published in the article together with an English translation according to the transcription produced by Dirichlet's great-grandson Leonard Nelson and p r e s e r v e d a m o n g Felix Klein's p o s t h u m o u s papers. Rowe left the question open if the original of Dirichlet's letter is still extant. The question can be answered in the affirmative: The original has been preserved in the voluminous series of Dirichlet's letters to his mother, which constitutes one of the parts of Dirichlet's NachlaJJ now located in the Murhard Library/University Library in Kassel (Federal Republic of Germany). For information on the "trifurcation" of Dirichlet's NachlaJJ, see my article in Historia Mathematica 13 (1986), "The Three Parts of the Dirichlet Nachlass.'" A comparison of Nelson's transcript with the original reveals that the copy is not entirely correct--although Nelson succeeded in deciphering highly difficult passages. The major differences are the following: 9 the date of the letter is not "29. October 1827" but instead "19. October 1827"; 9 Dirichlet does not speak of an "'unknown" but of an " u n p u b l i s h e d " dissertation of Gauss: "In diesem THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

5

Aufsatze (gelehrte Anzn. 11 April 1825) wird eine yon unserem Gauss der dortigen Societat (iberreichte, bisher ungedruckte Abhandlung iiber die biquadratischen Reste angekiindigt u n d . . . " ; 9 in the middle of the last paragraph, no additional word "Satzes" has to be inserted since the supposed adjective "searched" is in fact a noun: "Eines Abends ( . . . ) hatte ich einige Ideen, welche mich in den Besitz des so lange und so eifrig Gesuchten setzen zu miissen schienen"; 9 the last quoted sentence reads entirely different (the English translation given by Rowe corresponds already to the correct text): "Ich werde gewit] nicht ermangeln, das was er (iber die Schwierigkeiten, womit die Beweise dieser S/itze verbunden sind, sagt, in meiner Abhandlung auf geschickte Weise anzufiihren." It should be mentioned that the original bears a remark by Dirichlet on the margin of the first page that documents in a characteristic manner his energetic and strategic search for a mathematical career in Prussia's capital. Wenn meine Abhandlung in Berlin die Aufnahme finder, welche sie verdient, so werde ich wahrscheinlich nicht lange mehr hier bleiben sondern bald nach Berlin versetzt werden, w o e s so sehr an ordentlichen Mathematikern fehlt, daf~ Leute wie Crelle zu Mitgliedern der Akademie ernannt werden. (If my dissertation finds in Berlin the appreciation it merits, then it is probable that I shall not stay here much longer but will be transferred to Berlin. Qualified mathematicians are so scarce there that people like Crelle have been appointed members of the Academy.) Dirichlet's last remark shows him in opposition to his protector Alexander yon Humboldt: It had been Humboldt's intention to have A. L. Crelle act within the Academy as his organizational ally. The photo reproduced in Rowe's article as well as on the cover of issue 10/2 of the Mathematical Intelligencer warrants some critical commentary. This photo, from the Portr~tsammlung of the University Library G6ttingen is claimed to show "P. G. Lejeune Dirichlet as a young man" (p. 14). Reading this attribution, two objections came immediately to my mind: 9 the young man is shown without spectacles. Dirichlet's myopia dated from his very youth and was so excessive that it saved him from serving in the army; 9 the age of the young man seems to be thirty at most: if it was Dirichlet, the photo should have been produced in 1835 or even earlier. The quality of the photo seems to contradict the level of development of photography in those years. Therefore I asked Professor Kurt-Reinhard Biermann (Berlin) who first published this picture in his important biographical study of 1959 (J. P. G. Lejeune 6

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Dirichlet. Dokumente fiir sein Leben und Wirken, Berlin: Akademie-Verlag), providing it with the same legend. In his answer, Professor Biermann avowed not to have imagined at that time how erroneous the attributions in portrait collections can be. From some technical details, he explained, it is evident that the picture is a real photograph and not the earlier technique of daguerrotype. Hence, it is clear that the young man in that picture is not Dirichlet! (It might be one of his sons.) Gert Schubring Institut fiir Didaktik der Mathematik Universitdt Bielefeld 4800 Bielefeld, Federal Republic of Germany Hamilton's N o t e b o o k I would like to make a small correction to our paper R. Dimitri4, B. Goldsmith: "Sir William Rowan Hamilton," Mathematical Intelligencer, vol. 11, no. 2 (1989), pp. 29-30. The notebook where Hamilton wrote his quaternion formulae is not in the Royal Irish Academy as we stated but at Trinity College, Dublin, in Trinity Manuscript Collection, reference number TCDMS 1492. Radoslav Dimitrid Department of Mathematics University of Exeter Exeter EX4 4QE Great Britain

The Opinion column offers mathematicians the opportunity to write about any issue of interest to the international mathematical community. Disagreements and controversy are welcome. An Opinion should be submitted to the editor-in-chief, Sheldon Axler.

H o w Reliable Is a Computer-Based Proof? C. W. H. Lam "Is a Math Proof a Proof If No One Can Check It?" asked the headline of a recent New York Times article [2]. The article reported the results of our just finished computer search for a finite projective plane of order 10. The computation was enormous and over 1014 cases were investigated, obviously too much for any h u m a n being to check. I discussed this question briefly with the reporter, M. W. Browne, when he was preparing that article. I did not tell him that the CRAY-1A, the supercomputer that did most of our work, was reported to have undetected errors at the rate of approximately one per thousand hours. Since we used several thousand hours of CRAY-1A computer time, we should expect a few errors. Imagine an expanded headline, "Is a Math Proof a Proof If No One Can Check It and It Contains Several Errors?" I try to avoid using the word "proof" and prefer to use the phrase "computed result" instead. However many mathematicians are willing to accept the result as a proof! For everyone's peace of mind, in the paper reporting the result [6], I included a section that speculated on the correctness of the computer search. It concluded that the probability of a few random hardware errors causing the search to miss a plane is extremely small. Notice that the assertion of correctness is not absolute, but only nearly certain, which is a special characteristic of a computer-based result. On second thought, perhaps I should not avoid the issue and should actually use the word "proof." This is not the first time that a computer has played an important role in "proving" a theorem. A notable earlier example is the four-color theorem [1]. As more and more mathematicians are realizing the power of a computer, maybe we should also consider its limitations. Above all, the computer is a new tool to be used with care. The use of a computer also has serious implications for what constitutes an acceptable proof. In this article, I shall outline some of my thoughts on this subject. 8

You might think that it is not your problem and that it affects only researchers like me who work in enumerative searches. "Occupational hazard," you might say. But, consider symbolic manipulation programs such as MACSYMA, REDUCE, or MAPLE. They are great time-savers and enable us to solve problems otherwise too large to do by hand. Suppose one of the steps in a proof is based on using one of these programs. Then we have to also consider whether the computer is giving the correct result. In [3], there is an example where one such program missed one of the two possible solutions to a system of equations. A colleague here at Concordia once asked MACSYMA to factorize a polynomial and was told that it was irreducible. Not believing the result, he did it again. This time MACSYMA returned the correct factors. Did MACSYMA make a mistake or did he input the wrong

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1 9 1990 Springer-Verlag New York

polynomial initially? The answer is not important to us. The important lesson is that a computed result may be wrong for whatever reasons. Hence, even if the computer played only a minor role in a proof, the result may not be absolute. In Section 2, we shall look into some of the common computing errors. We have to understand the enemy to prescribe counter-measures. In Section 3, I shall describe some of the methods I used to increase the confidence of a computed result. Section 4 outlines my thoughts on h o w computer-based proofs should be evaluated. Section 5 addresses the role of an independent verification of a computer-based proof. Section 6 contains a few brief concluding remarks.

Characteristics of Computing Errors Computing errors can be broadly classified into two categories: h u m a n errors and h a r d w a r e errors. Human errors are the most common. H u m a n errors can further be subdivided into user errors that are under the user's control or system errors that are outside the user's control. One type of user error is the input. If we give the computer wrong data, then we cannot expect correct

The CRAY-1A, the supercomputer that did most of our work, was reported to have undetected errors at the rate of approximately one per thousand hours. Since we used several thousand hours of CRAY-1A computer time, we should expect a few errors. answers back. There is a saying, "Garbage in, garbage out." It is always worthwhile double checking the input data. Another type of user error is the programming error, if the user is actually doing the programming. Programming is a process of giving the computer a sequence of instructions to follow. The computer will follows these instructions, with no regard as to whether they make sense. If we give a computer the wrong or incomplete instructions, the results may be correct some of the time and wrong some other time. As most programmers are painfully aware, computer programs have to be tested. Testing involves running the p r o g r a m w i t h s o m e test data a n d checking whether the expected results are obtained. A programming error is commonly called a bug. The process of catching and then correcting bugs is called debugging. Debugging has its limitations. The common wisdom is, "Testing can only show the presence of errors and cannot prove their absence." An important characteristic of programming errors

is that most of them are reproducible, meaning that given the same input, the same erroneous output will result. The possible exception is the programming of parallel computers, where timing-dependent errors are usually irreproducible. For reproducible errors, it

Although system programs should have undergone thorough debugging before reaching the hands of users, they are seldom error-free. is useless to rerun a program, because whether it is correct or not, the answer produced will be the same. We group all the other programming errors not made directly by the user as system errors. Whatever c o m p u t e r we use, we u s u a l l y need an operating system such as MSDOS or UNIX, which is a package of programs written by others to make it easier to use the computer. There are also compilers, which are translating programs that convert user programs written in high-level languages (such as Pascal) into the equivalent machine-level instructions. Some compilers are called optimising compilers because they can generate more efficient machine-level instructions. Although system programs should have u n d e r g o n e thorough debugging before reaching the hands of users, they are seldom error-free. I have encountered problems with several optimising compilers. One example is the early versions of the Pascal compiler on the VAX running under the VMS operating system. When used with the optimize option, it gave a wrong translation of some of the operations related to packed sets. Packed sets are used in many of our programs on projective planes to save both m e m o r y space and computer time. So we had to systematically avoid using the optimize option, even though the programs would run slower. We had enough worries about the correctness of our own programs without having to worry about the correctness of the compiler. Can programming errors be totally eliminated? Programmers have long resigned themselves to accepting a small number of undetected bugs in long and complicated programs. In fact, there is a saying, "The only programs with no bugs are the trivial ones." Whether the correctness of a program is provable is still very much a research topic. Hardware errors, on the other hand, are not under the control of humans. They occur randomly and u s u a l l y lead to catastrophic results, for example halting the computer or destroying the data on the disk. They seldom go unnoticed and rarely pose a problem regarding the correctness of a computed resuit, because either there is no result or the result is obviously wrong. However, the unnoticed errors that change the results in some subtle and non-obvious ways are the most dangerous. For example, a common THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990 9

error is the r a n d o m changing of bits in a computer memory. Most large computers use error-correcting memory to minimize this problem. Yet, there are error patterns that look correct to the error-correction circuits. Fortunately, such errors are very rare and the probability of being affected by them is small, though not always negligible, as indicated by the error rate of the CRAY-1A. Let us summarize the characteristics of the two types of computer errors. Human errors are the most common; they are usually reproducible, and they are almost unavoidable. Hardware errors are random and rarely unnoticed. The unnoticed ones do occur, but they are extremely rare. Looking at this summary, it is not surprising that we should be more concerned with h u m a n errors t h a n hardware errors. Fortunately, human errors are more under our control.

M e t h o d s to Increase Confidence in a C o m p u t e d Result Eliminating all human errors should be the ultimate goal, but it may be too ambitious. A more realistic goal is to aim for a nearly certain status in a computed result. We shall discuss four methods that can be used to increase the confidence of computer-based results.

Prove the Results by Hand. Suppose we used a symbolic manipulation program. Should we just accept the results unquestioningly? I suspect most of us will. However, we should at least try to prove it by hand. If we can prove a result by hand, then all the doubts about computing errors are eliminated. As Ronald L. Graham observed in [7], "Knowing what to prove is more than half the battle." If our problem is to factorize a composite number, then it is not difficult to multiply the factors by h a n d and check the result. Clearly, this is the best solution. The same approach could be used on most computer-based results. However, this is not always as easy or straightforward as in the factorization example. I would dearly like to see a computer-free proof of the non-existence of a finite projective plane of order 10. Even a proof of a major subcase would be illuminating. What if we fail to prove the result by hand? Certainly, we should not just sit on it and hope that someday we can find a computer-free proof. We may want to ask the computer to print out the intermediate steps. Maybe these can provide some hints for a proof. In this respect, I find most symbolic manipulation programs inadequate, because it is difficult or impossible to print out the intermediate steps. We might also try to run the program a second time. Unless we suspect that a rare, undetected hardware error has occurred, it is useless to merely rerun a program. Because programming errors are reproducible, we would get the same answer, whether it is fight or wrong. Instead, we should try for other means of double checking the result. Double Checking the Result. Consider again the example of solving mathematical problems using symbolic manipulation programs. There are several such programs with similar capabilities. It is worthwhile solving the same problem using different programs. If they agree, then the probability of the answer being wrong is very small. It is still not possible to claim that the answer is absolutely correct. We can definitely imagine a scenario where the answer is wrong and yet both programs agree. Maybe we gave them the same wrong input or maybe they use the same erroneous method! Even w h e n we develop our own programs, we can still do some double checking. We can develop two

10

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

different programs, preferably using different methods and written by different individuals, and compare the results. You may think that the idea is unworkable, because developing one working program is already difficult enough, let alone two. However, the difficulty of developing a working program really arises in requiring the one program to be both efficient and general purpose, two often conflicting goals leading to complicated programs. It may be much easier to develop a second simpler program, where issues of efficiency or generality are not the main objective. For a long-running program, it is often necessary to develop two programs: one simple but slow, for exploration purposes, and another complicated but fast, for the actual run. In our search for the plane of order 10, we actually used many programs. The search is divided into cases, and we have fast programs tailor-made for each case. We also have another program that is slower by about four orders of magnitude, but which can work on any case. The results of these two programs are compared. Because it would have taken too long to run each case completely using the slower program, the comparison of results is restricted to a few selected small subcases. So, this is not a complete double checking of results, but the agreement of the results of selective subcases is still comforting. Even with only one program, it is possible to increase the confidence in its correctness by using internal consistency checking.

Consistency Checking. I shall start this section by describing one of my many programming errors. In 1975, as part of a study of the 1-width of a (0,1)-matrix [4], I had to generate all 6 x 6 (0,1)-matrices. A (0,1)matrix is a matrix all entries of which are either 0 or 1. The 1-width of a (0,1)-matrix is the minimum number of columns such that there is at least one 1 in each row. Since the matrix has 36 entries and each entry is either a 0 or a 1, there are 236 ~ 7 x 10TM such matrices. There are too many matrices to be considered directly, so I exploited the fact that the 1-width of a (0,1)-matrix is not changed by permuting rows or columns. These permutations divide the matrices into equivalence classes and I generated only one matrix from each equivalence class. The number of matrices to be considered is reduced by roughly a factor of 6! x 6!, to approximately 105. After running the program, I checked whether the answers made sense. By using P61ya's theory of counting or Burnside's Lemma, it is possible to calculate the size of each equivalence class. Adding up all these sizes, I obtained a number slightly smaller than 236. I spent the next weekend agonizing over what could be wrong without knowing where to start. I forget what the actual error was, except that it was very minor. I remember this story because it was the beginning of my conviction that an enumerative

search program should contain some internal consistency checking. What is consistency checking? It is the verification that a computed result does not contain contradictions. Many computational results contain internal relationships. For example, the sum of the degrees of the factors of a polynomial must equal the degree of the original polynomial, or the number of 6 x 6 (0,1)matrices is 236. To implement consistency checking, start by identifying some easily verifiable relationships among the expected results. Preferably, the relations should involve the whole computation rather than

A paper containing a computer-based proof creates a new challenge for our refereeing system. only a small part of it. Then, these relations should be tested and a failure would demonstrate the existence of errors. Where should we look for these relations? There is no simple answer and it depends on the nature of the problem being solved. In combinatorial computing, the counting method described above for the 1-width problem is typical. The permutation of rows and columns are generalized to the property-preserving operations. The idea of having to investigate only one representative from each equivalence class is the basis of isomorph rejection. This method can speed up a combinatorial program enormously, but it is also the source of many programming errors. Fortunately, the idea of counting objects in two different ways provides powerful consistency checking [5] and is responsible for catching many of my errors. I feel more comfortable with my computed results if they pass this check.

Use Well-tested Programs. The suggestion of using only well-tested programs seems a tautology. Yet, one can deduce different conclusions from this principle. For example, avoid writing unnecessary programs. In fact, very few mathematicians need to write complicated programs. There exist many excellent packages that are easy to use and can do most of the calculations we want to do. Since these packages are also used by many others, they have undergone extensive testing and hence are more reliable. A related conclusion is that we should use popular software packages, the more popular the better, because a popular package is more heavily used and less likely to have bugs. Mathematicians tend to be concerned about the cost of software packages. If there is a well-tested and free software package, by all m e a n s we should use it. However, there is cost involved in designing and deTHE M A T H E M A T I C A L INTELLIGENCER VOL. 12, NO. 1, 1990

11

veloping a good package and someone has to pay for it. So do not let the cost of a package be the overriding factor. Investigate carefully its capability and its reliability. Consider part of the cost as an insurance premium for the correctness of the result. Perhaps the extra cost is worth the peace of mind. As mathematicians, we are using the computer as a tool, and we need a dependable and reliable tool. It is advisable to be conservative and follow the wellbeaten tracks rather than breaking n e w frontiers in computing technology. Leave the latter task to computer scientists or mathematicians with a strong background in computer science.

How Should Computer-Based Proofs be Evaluated? A paper containing a computer-based proof creates a new challenge for our refereeing system. Normally, a referee is expected to check the correctness of the proofs. H o w can a referee check a proof that "no one can check?" Is he or she expected to write a program to check the results? What if the program requires a lot of computer time, as the search for a finite projective plane of order 10 does. This is too much to expect from our referees. I believe it is best to treat computer-based proofs as scientists in other disciplines treat experimental results. In addition to the results, the author of the paper should include a description of the methodology, an analysis of the results, and a discussion of how the results fit into the known theory. The referee can check whether the methodology is correct and whether the author has taken care to ensure the correctness of the computed result. Ultimately, the referee has to make a judgement on whether the results are interesting and believable. The consequence of using the "believability" criterion is that, sometimes, wrong results are published. Scientists in other disciplines have a standard technique for handling this problem. They emphasize the importance of i n d e p e n d e n t verification of experimental results.

Independent Verification It is important to encourage the independent verification by a second party of computer-based proofs. The necessity of an independent verification may require a rethinking of what is publishable. Normally, in mathematics, w e s e l d o m p u b l i s h a s e c o n d p r o o f of a theorem, unless it contains new ideas. An independent verification may not contain any n e w ideas and hence not publishable by this standard. In this "publish or perish" world, few people are interested in redoing someone else's work. The consequence of this 12

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

In this "'publish or perish" world, f e w people are interested in redoing someone else's work. The consequence of this attitude is that some wrong computer-based proofs m a y s t a y unchallenged for a long time.

attitude is that some w r o n g computer-based proofs may stay unchallenged for a long time. For the health of the discipline, I hope there will be a change of attitude. Personally, I believe that a journal that publishes a computer-based proof has a moral obligation to publish, albeit in a shorter form, an independent verification of the result. In a sense, the verification completes the proof.

Conclusion The advent of computers has provided mathematicians with a very powerful tool. It enables us to tackle complex problems. The slight uncertainty inherent in a c o m p u t e r - b a s e d proof should not deter us from using it. As Richard Feynman, a Nobel Laureate in Physics, said in his 1955 address to the National Academy of Sciences, "Scientific knowledge is a body of statements of varying degrees of certainty--some most unsure, some nearly sure, but none absolutely certain." As physicists learned to live with uncertainty, so we should learn to live with an "uncertain" proof. Maybe we can borrow a further leaf from the experimental physicist's b o o k - - t h e y have their particle accelerators, so why shouldn't we dream of mathematical supercomputers?

References 1. K. Appel and W. Haken, Every planar map is fourcolorable, Bull. Amer. Math. Soc. 82 (1976), 711-712. 2. M. W. Browne, Is a math proof a proof if no one can check it?, The New York Times (20 December 1988). 3. K. R. Foster and H. H. Bau, Symbolic manipulation programs for the personal computer, Science243 (3 February 1989), 679-684. 4. C. W. H. Lam, The distribution of 1-width of (0,1)-matrices, DiscreteMathematics20 (1977), 109-122. 5. C. W. H. Lam and L. H. Thiel, Backtrack search with isomorph rejection and consistency check, J. of Symbolic Computation 7 (1989), 473-485. 6. C. W. H. Lam, L. H. Thiel, and S. Swiercz, The nonexistence of finite projective planes of order 10, Can. Journal of Math. (to appear). 7. P. Wallich, Beyond understanding? Computers are changing the spirit of mathematics, ScientificAmerican (March 1989), 24.

Computer Science Department Concordia University Montrdal, QuebecH3G 1M8 Canada

THE MATHEMAT|CAL INTELLIGENCER VOL. 12, NO. 1 @ ~990 Springer-Veflag New York

13

Mathematics and Poetry: How Wide the Gap? W. M. Priestley

A little learning is a dangerous thing; Drink deep, or taste not the Pierian spring: There shallow draughts intoxicate the brain, And drinking largely sobers us again. --Alexander Pope Until I was in m y late twenties and agonizing over the writing of a thesis in mathematics, I was never seriously engaged by a poem. Poetry had usually been thrust upon me in English classes in the same spirit that mathematics was thrust upon English majors. It was a passive experience. You could be active in mathematics. You could get inside a good problem and enjoy the discovery of unexpected connections with familiar things. Sometimes, as a result, you had the pleasure of seeing everything anew. You just needed to muster the self-discipline to keep the subject constantly before you. Then, as Newton said, "wait till the first dawnings open little by little into the full light." No one ever suggested to me that with the same approach, you might sometimes encounter the same pleasure inside a good poem. Then came a trying time when the prospect of my failing to complete a thesis in mathematics seemed imminent. ! was not prepared to face that prospect and, to m y surprise, I found myself recalling a poet's lament: "Thou art indeed just, Lord, if I contend with thee, b u t . . , send m y roots rain!" When I had first read these lines in college I thought them to express the kind of desperate state attainable only by an Old Testament prophet or an overly emotional poet. In fact, I thought of the whole poem as extravagantly exaggerated, a virtuosic piece written by Gerard Manley Hopkins just to show how free and 14

flamboyant he could be within the presumably confining r h y m e s c h e m e - - a b b a abba cdc c d c - - o f a sonnet. But m y problems with writing mathematics and Hopkins's problems with writing poetry had led us to essentially identical plights: You know what you want to write about, and you keep the subject before you. Yet inspiration descends grudgingly and fleetingly. You strain for months, but your best efforts produce only disappointments. To make things worse, others seem to get lively ideas without apparent effort. It isn't fair:

THE MATHEMATICAL INTELLIGENCER VOL, 12, NO. 1 9 1990 Springer-Verlag New York

Thou art indeed just, Lord, if I contend With thee; but sir, so what I plead is just. Why do sinners" ways prosper? and why must Disappointment all I endeavour end? Wert thou my enemy, 0 thou my friend, How wouldst thou worse, I wonder, than thou dost Defeat, thwart me? Oh, the sots and thralls of lust Do in spare hours more thrive than I that spend, Sir, life upon thy cause. See, banks and brakes Now, leaved how thick! laced they are again With fretty chervil, look, and fresh wind shakes Them; birds build--but not I build; no, but strain, Time's eunuch, and not breed one work that wakes. Mine, 0 thou lord of life, send my roots rain. Hopkins's poem now seemed to represent my own agony. However, the real revelation came in seeing that the poem's very existence gives assurance that such agony can be sublimated into flamboyant flight - - e v e n when that flight is held to the rigid demands of sonnet form. I had been absorbed by the daring flights of mathematics in the face of rigid formal demands, and I w a n t e d to make my own daredevil flight. How could I not become absorbed in this poem, which did, in essence, what I wished to do? Others have known emotional perils of mathematics [17], and other students of mathematics have been inspired by this poem [5, p. 31]. My encounter led me to try to learn a little about the world of serious poetry and to keep an eye out for similarities to the world of serious mathematics. (It pleased me no end to find out, incidentally, that Hopkins had made a brilliant record in mathematics at Balliol College, Oxford.) One similarity between mathematics and poetry paradoxically has the effect of preventing other shared characteristics from becoming more widely known. Each of the two callings seems--particularly from the other's point of v i e w - - t o aspire to create a world that "'the Philistine cannot enter without ceasing to be a Philistine." An apprenticeship does seem necessary to gain full entrance to either world. The longer I serve as an apprentice, the more I find that the gap between mathematics and poetry is not nearly so wide as it formerly seemed to be.

A Little Learning To probe the gap between mathematics and poetry, we might best begin by taking note of a kindred relationship that is less problematical and more familiar: the bond between mathematics and the basic elements of language. This bond was institutionalized in medieval times with the establishment of the "seven liberal

arts" as an educational unit. The trivium--grammar, rhetoric, and logic--could not have been wed to the quadrivium--arithmetic, geometry, astronomy, and m u s i c - - w i t h o u t general acknowledgment of a natural affinity between these two groups of disciplines. This affinity has persisted through modern times, w h e n a number of mathematicians have displayed more than a casual interest in the trivium. Gauss in his y o u t h was equally torn b e t w e e n mathematics a n d classical philology, and more recently we have seen mathematical treatments that have revolutionized aspects of logic and linguistics. As academic disciplines, mathematics and language are today intertwined at language's lower levels. The question to be addressed here may be put as follows: How wide is the gap between mathematics and language at language's highest level? Salomon Bochner, a distinguished mathematician and an avid student of linguistics, remarked that the Greek word for mathematics originally had the very general meaning of "something that has been learned or understood." The contraction of meaning around the time of P l a t o - - w h i c h r e s u l t e d in the w o r d ' s present denotation--Bochner [3, p. 25] thought to be noteworthy: This contraction is remarkable not only because it was so extensive, but because there was only one other contraction, in Greek, which was equally extensive, the contraction of the word "Poetics." By origin, poetikd means " s o m e t h i n g that has been done, manufactured, achieved." It thus appears to have been possible in 400 B.C. to use the words "poetry" and "mathematics" to refer on occasion to the same thing. Nothing, of course, could be further from the case today, when many students and professors do not even view mathematics as belonging to the liberal arts. The shortsightedness of this current view induced me to put the following words in the middle of a calculus book: It is hard to overestimate the value of appropriate symbolism. Of all creatures, only human beings have much ability to name things and to coin phrases. Poets do this best of all.

9 . . as imagination bodies forth The forms of things unknown, the poet's pen Turns them to shapes and gives to airy nothing A local habitation and a name9 A Midsummer-Night's Dream, Act V It can be contended that Leibniz's way of writing the calculus approaches the poetic. One can be borne up and carried along purely by his symbolism, while his symbols themselves may appear to take on a life all their own. Mathematics and poetry are different, but they are not so far apart as one might think [13, p. 110]. Though mindful that a little learning is a dangerous thing, I wish to expand upon the thesis expressed in THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

15

the last sentence above. Let us take note of some ways in which mathematics and imaginative writing have touched each other.

Shallow Draughts Consider the following familiar lines:

Nature and Nature's Laws lay hid in night: God said, 'Let Newton be!"and all was light. Pope's "Epitaph Intended for Sir Isaac N e w t o n "

was intended to be taken as playfully composed sarcasm. When read that way in a poetry class it can elicit delighted chuckles from students. Read it aloud yourself, and you may feel an undercurrent of cynicism. Alexander Pope was not endorsing the Age of Reason. On the contrary, he could see nothing humanistic in Newton's legacy, and was reacting, perhaps partially out of envy, against it: Pope was, of course, one who ascribed to his own admonition.., that the proper study of mankind is man, [unlike] Sir Isaac Newton . . . . [who was] a student of the physical world, not [of] man. [This epitaph is] half-satiric, half-admiring . . . . The paraphrase of the line from Genesis is obvious--and cynical [12, p. 302]. Pope is easily misread by historians of mathematics. Eves [6, p. 307] and Kline [11, p. 281] q u o t e this epitaph for the purpose of epitomizing what they suppose, falsely, to be the unbounded admiration of an entire age for N e w t o n ' s accomplishments. Pope's words might better be taken in exactly the opposite way: to h e r a l d the e v e n t u a l b r e a k b e t w e e n the sciences and the humanities that led to the notorious "two cultures" of C. P. Snow.

P o e t r y and m a t h e m a t i c s do n o t belong to distinct cultures.

and mathematical ideas do not." This point is well taken, so long as we note that longevity does not imply superiority. If it did, Homo sapiens would not fare well in comparison with other species. A more contentious issue is raised with Hardy's analysis of "good lines" of poetry that are devoid of significant meaning [8, p. 84]. Hardy evidently thinks that the conventional w i s d o m of the 1930s w o u l d judge good lines to be good poetry even w h e n the lines are incoherent. It is curious that he should think so, for Hardy is at pains to contrast examples of beautiful mathematics (the Greek proofs of the irrationality of the square root of two, and of the infinity of primes) with examples of ugly mathematics (there are just four numbers which are the sums of the cubes of their digits). His point is that, in mathematics, truth is not a sufficient criterion for beauty. Seriousness and depth must be considered as well.

One hears of college courses labeled Mathematics for Poets. There is an equal need for courses in Poetry for Mathematicians. Hardy has only a vague notion [8, pp. 90-91] that a poet might have similar feelings about poetry. Yet poets do, of course, feel the importance of seriousness and coherence in judging a poem [4, pp. 340-343]. Perhaps the canonical textbook example of the good lines/bad poem syndrome is given by Joyce Kilmer's "Poems are made by fools like me, But only God can m a k e a t r e e . " Cleanth Brooks a n d Robert P e n n Warren [4, pp. 289-290] give a debunking of Kilmer's poem Trees. "Is there any basis," they ask, "for saying that God makes trees and fools make poems?" One hears of college courses labeled Mathematics for Poets. There is an equal need for courses in Poetry for

Mathematicians.

Poetical Power Poetry and mathematics do not belong to distinct cultures, however, despite the small number of people who would profess to truly appreciate them both. We shall see that Pope and Newton had something in common after all, that mathematics has within it humanistic elements of the same nature as poetry. First, however, we need to eliminate misconceptions about poetry that are likely to burden mathematicians. Even a mathematician like G. H. Hardy, whose graceful writing style could have come only from a deep love of letters, has made remarks about poetry that do not quite ring true. In his book A mathematician's apology he says [8, p. 81]: "Greek mathematics is 'permanent', more permanent even than Greek literature. Archimedes will be r e m e m b e r e d when Aeschylus is forgotten, because languages die 16

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Some mathematicians are not bad as poets. Here is the last of four stanzas written by Errett Bishop [2, p. 14] to w a r n mathematicians against the seduction of formal systems, and to implore them to turn instead to the bright sun of constructivism:

If Aphrodite spends the night, Let Pallas spend the day. When the sun dispels the stars, Put your dreams away. These are, in my opinion, good lines--both to the ear and to the mind. The last two rephrase the content of the first two. If you read the stanza aloud, however, you will notice the effect of a subtle change in meter.

The stanza exhibits the familiar iambic pattern of unaccented syllable followed by accented syllable, but in each of the last two lines the initial unaccented syllable is truncated. This change, coupled with the fact that these lines each begin with three monosyllables, forces us at mid-stanza to read more deliberately, to adopt a graver tone. This marked shift in tone, from fanciful to serious, has the effect of rendering to us the depth of Bishop's profound concern. Mathematics, of course, cannot render a feeling or an experience like poetry. To find similarities between poetry and mathematics, we must look elsewhere. Toward this end, consider Bishop's choice of the word dispels, which he may well have picked just because it "felt right." However, he may have considered and rejected other w o r d s or phrases: drives out, repels,

wards off, rebukes, rebuffs, etc. None of these other possibilities carries the overtones produced by the word Bishop picked. Literally, the word means "drives away," but in context dispels suggests "breaking the spell" of the magic of Aphrodite's stars. While there may be no logical or etymological connection between dispel and spell, their association by the ear can produce an association in the mind. If this happens, the word does double duty upon the reader. It is denoting and connoting at the same time in such a w a y that both actions carry forward the argument. To attain this poetic effect the association need not necessarily be produced by aural means; etymological or conceptual means work just as well. Regardless of h o w it is done, this imaginative way of mobilizing a w o r d - - o f making it speak in harmony on several levels at once--is a main weapon of poetry. Can mathematics do anything like this? It can. In fact, this is a key to the power of mathematics. Mathematicians engage in a kind of collective poetical undertaking by virtue of what has evolved as their common language. To take an example, consider the concept of a function. You may, if you choose, define it in a most unpoetic way as a set of ordered pairs with no first component repeated. Whatever you take the word to denote, the fact is that the concept carries with it a large baggage [3, p. 217], much as a single word can carry far-flung connotations. Mathematicians make a function do triple duty. As every student learns early on, a function can be thought of statically, kinematically, or geometrically; that is, as a pair of columns of elements, as a rule of correspondence between moving points, or as a curve. Through this word you may move at will, conceptually, in three vastly different realms at once, or shift back and forth until you get the best view. Philosophers of mathematics seem to pay little attention to this point, perhaps because the practice of couching much of mathematics within the language of functions is essentially poetic.

Of course, most of us like to speak in terms of functions just because it feels right. There are no critics of m a t h e m a t i c s a r o u n d to wax e l o q u e n t about w h y things sometimes work out so happily when functions are mobilized. Or when the deep analogies of isomorphisms are brought to bear. Or when algebra, analysis, and geometry train three points of view upon the same target at the same time.

A Final Epigraph That well-crafted mathematics has an aesthetic appeal is argued in different w a y s b y Halmos [7] and b y Hardy [8]. Bertrand Russell put this claim in the following way: Mathematics, rightly viewed, possesses not only truth, but supreme beauty--a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stem perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than man, which is the touchstone of the highest excellence, is to be found in mathematics as surely as in poetry. In later life, when Russell no longer thought well of the essay that begins with these oft-quoted words, he still maintained [15, p. 212] that "the aesthetic pleasure to be derived from an elegant piece of mathematical reasoning remains." An elegant argument in mathematics may not give the same kind of aesthetic pleasure as an elegant argument in a poem, but the immediate response of a serious reader is often the same in either case. "Silence is the appropriate response to revelation," as an old professor of mine once wrote [9], putting it much better than I ever could. Of course, if revelation is taken to mean something that shakes us to our foundations and makes us adopt, or at least appreciate, a radically new point of view, then it is rarely encountered except in the greatest of works. G6del's theorem may leap to our minds as the purest example of revelation in mathematics. (My old professor, incidentally, was writing about King Lear.) However, revelatory works need not be vast and sublime. We are jarred by Pope when we hear that drinking a little will make you drunk, but drinking a lot will sober you up; by Shakespeare when we hear that airy nothing can be given a body and shape and name; and by Bishop w h e n we hear that we must choose the goddess of wisdom over the goddess of love in mathematics! We are jarred by Pythagoras when we hear about the square root of two, and by Euclid w h e n we hear of the long march of primes. A common function of poets and mathematicians is to jar us into place, to refocus our vision so as to order the chaos around us and to connect what is familiar with what is beyond. This function is objectified in THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

17

Wallace Stevens's Anecdote of the Jar, where a jar upon a hill tames the wilderness in which it is placed:

The wilderness rose up to it, And sprawled around, no longer wild. The jar was round upon the ground And tall and of a port in air. It took dominion everywhere... Here, a bare and gray container is made to symbolize the effect of the adoption of a n e w point of view. Or, more briefly, Stevens has simply (!) made a jar symbolize a jar, giving to an abstract idea a local habitation that might have surprised even Shakespeare. Just as a piece of mathematics can model different situations, this poem is subject to different interpretations. The jar could be a poem, which may have been what Stevens had in mind, but it could be any artifact of the imagination made for the purpose of instituting order, control, understanding, or unity. Artifacts giving form to abstractions are as essential to mathematics as to poetry. Should prizes be offered for bodying forth the forms of things unknown, t h e n - - t o mention just one nomination from mathematics--the notion of a limit would have to be considered. What was a limit, before it was given a name? Before Cauchy gave a precise significance to the notion, the answer might have been an oracular utterance alluding to the Greek method of exhaustion, like "that which remains when everything to which it is not equal is eliminated." If anything was ever airy nothing before being given a name, this is it! What did Cauchy's jar do? The wilderness explored by Newton, Leibniz, and Euler rose up to it. The infinitesimal calculus sprawled around, no longer wild. It was perfectly grounded, this jar, yet tall enough to serve as port for the high-flown fancies of modern-day analysts. It took dominion everywhere. Stevens's poem once seemed to me the ideal epigraph to set forth the theme of a calculus text, and I used it that way in [13]. Now I see that my jar was too small. The poem could well be taken as an epigraph for all of mathematics.*

The Necessary Gap

to be a fine poet. Mathematics relies upon the eye, but not so much. Greek mathematicians, like Greek artists, may have relied primarily upon the sense of touch [10]. Ugly mathematics--such as a correct, but inelegant brute-force method hidden away in some computer p r o g r a m - - c a n be of great value. Ugly poetry is of no value except to illustrate bad form to be avoided. Society will let you copyright a poem, but not a theorem. Thus there is a legal distinction between poetical truth and mathematical truth. Society produces critics of poetry who are not poets, while mathematicians must serve as their own reviewers. In fact, the differences between mathematics and literature in society are an obvious subject for satire. What would the land be like if the roles of mathematics and literature

Society will let you copyright a poem, but not a theorem. were reversed in America? "'Acirema'" is the land to which Kenneth May and Poul Anderson [1] take us, where "mentioning the latest theorem is a standard ploy of social one-upmanship, whether or not one has actually studied it." It is argued in [14] and elsewhere that the spirit animating the study of mathematics is humanistic. H o w closely that spirit resembles the spirit of poetry is an inviting subject for a book. The only happy outcome of an expansion of this theme to booklength size, however, might be to prompt the reprinting of lines from Schwarzenberger's famous review [16]:

By and large any human activity Displays mathematical structures, But an author with some sensitivity Won't let them expand to six chapters. The material was once a nice lecture But expansion's a dangerous trap; My opinion as humble reviewer Is: the book fills a much needed gap.* Mathematics and poetry are different. Let that be conceded.

We have discussed some less obvious similarities between poetry and mathematics. Let us end on a lighter note about the less obvious differences. Poetry relies strongly upon the ear. A person deaf since birth could be a fine mathematician, but would have little chance

Despite the differences between mathematics and poetry, there are common threads enough to show that essential elements of mathematics are humanistic. In

* Editor's note: For a different analysis of t h e s a m e p o e m , see the review b y J o n a t h a n H o l d e n in this issue of t h e Mathematical Intelligencer.

* Professor S c h w a r z e n b e r g e r h a s v o l u n t e e r e d t h e information that the p h r a s e "'this book fills a m u c h - n e e d e d g a p " w a s b o r r o w e d f r o m a b o o k review written by Paul H a l m o s .

18 THE MATHEMATICALINTELLIGENCERVOL. 12, NO. 1, 1990

Conclusion

fact, the only w a y to avoid seeing a n y t h i n g poetic in mathematics is to read its language in a p u r e l y formalistic fashion, p a y i n g attention to d e n o t a t i o n and the laws of logic, and to nothing else.

Acknowledgment: I wish to thank Henry F. Arnold, Jr., Professor of English at the University of the South, for help in making coherent a first draft of this paper.

References 1. Poul Anderson and Kenneth O. May, An interesting isomorphism, American Mathematical Monthly 70 (1963), 319-322. 2. Errett Bishop, Schizophrenia in contemporary mathematics, Contemporary Mathematics 39 (1985), 1-32. 3. Salomon Bochner, The role of mathematics in the rise of science, Princeton: Princeton University Press (1966). 4. Cleanth Brooks and Robert Penn Warren, Understanding poetry, New York: Holt, Rinehart and Winston (1960). 5. Freeman J. Dyson, Disturbing the universe, New York: Basic Books, Inc. (1979). 6. Howard Eves, An introduction to the history of mathematics, New York: Saunders College Publishing (1983). 7. P. R. Halmos, Mathematics as a creative art, The American Scientist 56 (1968), 375-389. 8. G. H. Hardy, A mathematician's apology, Cambridge: Cambridge University Press (1967). 9. Charles T. Harrison, The Everest of poems, The Sewanee Review 75 (1967), 662-671. 10. William M. Ivins, Jr., Art and geometry, New York: Dover (1946).

11. Morris Kline, Mathematics in western culture, New York: Oxford University Press (1953). 12. Frank N. Magill, Magill's quotations in context, New York: Harper and Row (1965). 13. W. M. Priestley, Calculus: an historical approach, New York: Springer-Verlag (1979). 14. , Review of The Mathematical Experience, by Philip J. Davis and Reuben Hersh, American Mathematical Monthly 89 (1982), 515-518. 15. Bertrand Russell, My philosophical development, New York: Simon & Schuster (1961). 16. R. L. E. Schwarzenberger, Review of Mathematics and Humor, by J. A. Paulos, Bulletin of the London Mathematical Society 42 (1981), 248. 17. Donald R. Weidman, Emotional perils of mathematics, Science 149 (1965), 1048.

Department of Mathematics and Computer Science The University of the South Sewanee, TN 37375 USA

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

19

A Curious New Result in Switching Theory Lee C. F. Sallows

G6del turned out to be an unadulterated Platonist, and apparently believed that an eternal "'not" was laid up in heaven, where virtuous logicians might hope to meet it hereafter. --Bertrand Russell [1].

The following account relates how a puzzle brought to light a remarkably simple, highly intriguing, probably useless, but undeniably basic new result in switching theory. Spice is added to the story through the role played by construction of a wildly improbable electronic device in helping to establish the new finding. "Switching theory" has a slightly old-fashioned ring to it; what exactly does it signify? A brief remark on this and a couple of related matters will set our subject in perspective and prepare the way for issues arising later. Computer science emerges into view as a separate discipline from a fluster of related topics, chief among them symbolic logic, Boolean algebra, switching and automata theory. Logic, originating with Aristotle, concerns the study of deductive inference, of the conditions of truth-preservation in deriving one statement from another. More than two millenia following Aristotle, George Boole was to design his algebra to model logic, a step largely intended to replace reasoning with calculation, with the rule-governed manipulation of symbols. Boolean algebra, we remind ourselves, comprises a so-called formal system: a well-defined set of signs and conventions by means of which, starting with certain symbol strings, certain others may be legally substituted, the latter being deemed equivalent to the former. No specific meaning is attached to these transformations, except in the loose identification of signs with the things they usually signify when applying such formalisms to external systems (such as

logic). Whether the algebra applied really is an accurate model of the system in question is of course a problem not resolvable within the algebra itself. A notable success in the practical application of Boolean algebra occurred with the appearance of C. E. S h a n n o n ' s paper "Symbolic Analysis of Relay and Switching Circuits" in 1938 [2]. Ever since, the analogy of "0" and "'1" with open and closed switch contacts, and of series/parallel switch connections with AND/ OR B o o l e a n o p e r a t o r s , has b e e n a s t e r e o t y p i cal textbook example. Then, as today, a relay was an electromagnetically operated switch, a device opening

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1 9 1990 Springer-Verlag New York

21

up new realms of complexity in the possibilities it offered of switches controlling still other switches in endlessly convoluted networks. The problems thrown up in this new domain soon became the concern of "switching theory.'" Ten years following Shannon, switching theory advanced to a new level of maturity with G. A. Montgomerie's paper "Sketch for an Algebra of Relay and Contactor Circuits" [3]. By now a vital distinction had been recognized in the division of networks into combinational and sequential types. Combinational circuits were those in which the open or dosed states of every switch depended purely upon current input values (0, 1) to the network. A Boolean formula, simple or complicated, would always describe this relation satisfactorily. Sequential circuits, on the other hand, were those whose response to input patterns also depended in part on their past history: on the foregoing sequence of values presented. The behaviour of the circuit might thus change significantly after receipt of some critical input, the latter event thereby being in some sense "remembered.'" In fact memory--introduced via feedback effects--was the key property of such networks. Flow tables and state transition diagrams now displaced static formulas in the need to capture this temporal context-dependent behaviour. Thus was launched the study of what came to be called sequential or finite state machines, a field later to be known as automata theory. The progress of developments in automata theory is b e y o n d our p u r p o s e here: advances w e r e rapid, leading to theoretical results of great m o m e n t in connection with Turing machines and mathematical linguistics, the subject soon shading seamlessly into

The possibility of simulating three inverters by means of t w o had never so much as crossed my mind before; the bare contingency hinted indefinably at something wonderful. theoretical computer science proper. Back in the mainstream of switching theory however, by the 1960s advances in technology had shifted emphasis away from relays and onto "electronic digital logic" realized in micro-packaged integrated circuits or "'chips." Mechanically-actuated contacts gave way before "ANDgates" and "OR-gates" etc., the binary states (0, 1) whose input and output lines were represented by two discrete voltage levels. Soon Boolean algebra was a standard item on the training syllabus of electronics engineers; formerly recondite chapters of the now slightly outmoded-sounding "switching theory" became the stock-in-trade of every technician. Hence, overtaken by studies into the more chal22

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

lenging finite state machines, as a subject of research, switching theory dropped into the background, furnishing instead a well-knit body of established results that found daily application in electronic logic design. This is not to say that all the theoretical questions raised had been successfully answered. Many problems, especially in the area of minimization, remained unsolved; later these would provide a point of departure for the currently vigorous theory of circuit complexity (see [4]), a field closely related to, yet historically distinct from the old switching theory. In any case, mass-production techniques had extinguished any practical need for minimal solutions. Gone forever was the pioneering impetus of the early days. Who then would have expected to stumble across an undiscovered nugget still reposing amid the slagheaps of this abandoned mine?

A Knotty Problem Recently browsing through A Computer ScienceReader (Selections from Abacus, Springer-Verlag, 1988), m y eye was caught by an article on Automated Reasoning by Larry Wos [5]. Wos illustrated the working of his r e a s o n i n g p r o g r a m by m e a n s of a few example problems, one of which immediately captured my attention. It was this:

z

.~

x /

.~

zI

The black box above receives binary inputs (0, 1) at x, y, and z. Each output line yields the complement of the corresponding input; that is, if x is 0, x' is 1, and so on. Each of the eight possible 3-bit input words thus gives rise to its complementary word at the outputs. Normally such a transfer function would be achieved by using three inverters or NOT-gates connected between each input and output.

Problem: Design a network using any number of AND and OR gates, but not more than two (2) NOT's to achieve exactly the same input-output function. (The AND's and OR's may have as m a n y inputs as required.) Now relays, gates, switchery, and logic hold powerful fascination for some. The possibility of simulating three inverters by means of two had never so much as crossed m y mind before; the bare contingency hinted indefinably at something wonderful. It seemed to call for ingenious circuitry. The puzzle had me hooked in no time.

Figure 1. Moore's circuit. It turned out to be a far tougher conundrum than first imagined. So much so, in its elusiveness it became hypnotic. In fact, on and off I took almost a fortnight to solve it, succeeding even then only through reasoning aided by trial and error. But the solution was worth waiting for: an intricate network of true Platonic elegance and inevitability. It is a logical constellation that was always there, sooner or later someone was bound to find it; a sheer poem for the switching theorist. As the sequel shows, the name of the man who did find it first turned out to be Edward F. Moore, a distinguished pioneer in the field of automata theory. From now on I shall refer to the basic arrangement as Moore's circuit. Incidentally, Wos's a u t o m a t e d r e a s o n i n g p r o g r a m was successful in solving the problem; his method being too complex to outline here, a detailed account can be found in [6]. One version of Moore's circuit is shown in Figure 1. The network admits of a number of (essentially minor) variations, some more economical in gates than others; our example is picked for its functional clarity. Interested readers might like to seek a more parsimonious circuit u s i n g one gate fewer t h a n Figure 1 (multi-input gates then being counted as if built up from 2-input equivalents; Figure 1 thus containing 11 AND's and 14 OR's). In view of its importance to what follows, a few comments on Moore's circuit will be worthwhile. Central to every variant of Moore's solution is circuitry leading to a b i n a r y r e p r e s e n t a t i o n of the number of zeros present in the input word (xyz) by the four possible states of the two inverter outputs: 00 = none, 01 = one, 10 = two, 11 = three zeros. Simple as this may seem, there is but a single way to achieve

it. In effect, each inverter's output state (0 or 1) must represent a classification of xyz according to whether the n u m b e r of ones it contains falls in the top or bottom row (first inverter, A), and in the left or right column (second inverter, B) of the table: B 1

0

In this way the intersection of A's row and B's column choice pinpoints the number of ones (and thus, zeros) in the input word. In our circuit, use of AND gates to combine this information with the specific input pattern enables a complete decoding of the input word. See how each of the seven lines feeding the three OR gates at the right is uniquely activated by a different input word (indicated). The circuitry to the left is thus a "3-bit to parallel d e c o d e r . " Note that a l t h o u g h available, the eighth line (23 = 8) is unused since, when active (i.e., when x = y = z = 1), all outputs are to remain 0. Similarly, the three interconnected output OR's comprise a "parallel to 3-bit re-coder," the coding in this case ensuring that xyz inputs that are 0 result in corresponding outputs that are 1, and vice versa: an active " x ~ " line turns on outputs y and z, for instance. A point to observe is that alternative OR combinations could replace (or supplement) this one to produce any desired input-output functions: An output word may have as many bits as we please, and distinct recoders working in parallel could realise unlimited simultaTHE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

23

neous output words, if required. Already one senses a surprising latent potency here, although, as we shall see, most of the magic in Moore's circuit lies exactly in the mischievous recoding he did choose. Speaking of coding and recoding serves to recall that a circuit diagram is a kind of coded representation and thus itself capable of translation into different symbol systems. A change of m e d i u m often brings new aspects into view. An obvious alternative in this connection is Boolean algebra. Re-expressing Moore's circuit in these terms is a mere mechanical exercise. Designating the output of inverter A as A, for instance, we can work backwards through the circuitry towards the inputs, transcribing directly as we go:

A = Not[x & y) Or (x & z) Or (y & z)l. Comparing formula with circuit we find the inverter is replaced by Not, the 3-termed, square-backeted Or expression deputizes for the OR-gate wired to its input, and the three parenthesized terms stand in for the AND-gates communicating between the input pairs xy, xz, and yz and the OR inputs. Note how the nesting of expressions r e p r o d u c e s the pattern of outputs feeding into inputs in the circuit. We are looking at a fragment of Moore's circuit written in a different language. Analogously, and taking advantage of the above, a compact expression representing the output B of inverter B can also be written: B = Not[(x & A) Or (y & A) Or (z & A) Or (x & y & z)]. Note how the presence of A as an argument in the function describing B is more than a convenient abbreviation, it reflects A's antecedence in the signal processing path: the value of A must already be available in determining that of B, a point that will prove of importance later. However, the real convenience of these partial descriptions becomes clear in the crisp encap-

sulation of the complete Moore circuit they now facilitate: x' = [ ( y & A ) Or (z & A) Or (B & y & z) Or (A & B)] y' = [(x&A) Or (z & A) Or (B & x & z) Or (A & B)] z' = [(x&A) Or (y & A) Or (B & x & y) Or (A & B)]. See how the equations expose a (predictable) threefold functional symmetry hinted at, but less successfully conveyed, by their equivalent circuit diagram, an obfuscation resulting from the latter's confinement to two dimensions. (An amusing exercise is to design a 3-D version of the circuit recapturing the trilateral balance.) Still later we shall have occasion to recall these formulas. So much then for a preliminary look at Moore's circuit.

Networks and Notworks This was all fine as far as it went: an intriguing puzzle with a beautiful solution, if lacking in practical application. During an early stage in reaching that solution, however, a rather astounding thought hit me. As an electronics engineer the idea occurred to mind quite easily and, although perhaps ingenious in small degree, is certainly no creative tour de force. Nevertheless, the implications struck me as luminous and compelling. The idea was simply this: If it is possible to simulate three independent NOTfunctions using only two primary NOT's (or real inverters) then couldn't we use two of those three in order to simulate a second set of three NOT-functions? At this stage, having used only two of the first set of three, there would still be one left over. That means that a total of FOUR i n d e p e n d e n t NOT-functions would have been simulated while still using only two real inverters. Figure 2 makes the proposal explicit. C o n s i d e r the circuit s h o w n . N e t w o r k 2 is the

Figure 2. Four NOT-functions from two inverters. 24

THE MATHEMATICAL INTELLIGENCEI~ VOL. 12, NO. 1, 1990

Figure 3. Recursive nesting to produce N negations from two inverters. straightforward Moore circuit; as such its behaviour is functionally equivalent to an outwardly similar box containing three separate NOT's or inverters connected between each of its three inputs and outputs. Network 1 is identical to Network 2 except that its two inverters have been removed. The internal inputoutput connections normally made to the missing inverters have been brought out and connected instead to two channels of Network 2. Network 2 thus furnishes the two NOT functions required for normal

working of Network 1 (channels a, b, c) while still leaving a fourth independent complement function over (channel d). That is all. The ramifications of this stratagem ripple swiftly outward. For clearly the four newly created NOTfunctions can again be nested in an endlessly expandable recursive hierarchy to produce an unlimited number of independent negation functions; see Figure 3. In other words (and striving for the infinite in the name of logic): THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990 2 5

THEOREM I. In any universe, exactly two fundamental negators suffice for concomitant synthesis of all others. But this soon leads us to a couple of other interesting consequences: THEOREM II. A device whose input-output relations are described by some system of Boolean functions is always constructible using a network comprising some number of AND- and OR-gates but no more than two inverters. Or, still more ambitiously (and relying on other well-known results in the field): THEOREM III. Every possible finite state machine (automaton) is realizable using no more than two primary complement functions. Am I alone in continuing to feel a sense of wonder in this simple discovery? As I say, the idea for the above configuration occurred to me at the time of reading Wos's article, even before solving his problem. Taking it to be a merely personal rediscovery of a presumably well-established result in logic, thought of any further development never arose. Being satisfied that the idea was sound, as an engineer I felt only sheer surprise that, in principle, all the millions of inverters in use throughout the world could be " s e e d e d " from a single pair. Having a romantic turn of mind, it conjured an imaginative vision of a sort of Yin-Yang dyad of inverters occupying a dusty, temperature-controlled glass case at the National Bureau of Standards. Wires leading away from the four old-fashioned knurled brass input and output terminals lead off for distribution to other boxes scattered about the nation. (I should say five terminals: a " g r o u n d " or zero voltage reference line would also be required.) Well-established result or no, the self-duplicating inverter circuit was a revelation to me and continued to exercise fascination. Having nothing better to do, for fun I typed out a devilish new version of Wos's problem, sending it around to tease friends and colleagues at computer science and mathematics departments at the University of Nijmegen. In the new version, otherwise identical to the old, four complement functions are to be realized instead of three. As before, of course, only two inverters are allowed. (As a matter of fact, by Theorem II above, the input-output functions demanded by any severer version of the problem could be made as complicated as one wished. Asking for four NOT-functions is the obvious choice, this representing the least jump in difficulty at the new level of complexity.) In a few cases the response to this teasing was sharper than anticipated. I suppose the problem is so clear-cut and inescapable it poses a provocative chap 26

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

lenge to one's self-esteem as an engineer, mathematician, logician, or whatever. Prevarication in the face of this kind of simplicity is difficult; admitting one cannot solve such an apparently elementary problem, even more so. The trouble is, unless you happen to be aware of Moore's circuit (as most people are not), the two separate insights needed for reaching the solution put it well beyond all reasonable ingenuity. It would be a creative act to re-invent Moore's circuit from scratch; penetrating to the fact that such a circuit is necessary as a component in the 4-complement configuration asks too much of human imagination. In light of this, some of the scepticism poured on my assurances that the solution was complex but straightforward, involving absolutely no hanky-panky, becomes explicable. At this stage Hans Cornet, a mathematical friend at The Hague, ran across what proved to be the original source of the 3 - c o m p l e m e n t problem. In Marvin Minsky's book Computation: Finite and Infinite Machines (Prentice-Hall Inc., 1967, page 65) was a confirmation of m y assumption that Wos had merely borrowed r a t h e r t h a n i n v e n t e d the p r o b l e m . Looking u p Minsky's book in Nijmegen I learned the problem had first been "'suggested by E. F. Moore." Admittedly the solution circuit (shown only in skeletal form) is not overtly attributed to Moore but surely no one could pose such a riddle without first having unravelled it? A comment by Minsky following the problem statement drew from me an appreciative smile: "The solution n e t . . , is quite hard to find, but it is an extremely instructive problem to work on, so keep trying! Do not look at the solution unless desperate." It was a final remark of his, however, that brought me up with a jolt. With deepening puzzlement I ran my eye again and again over his two terminal sentences: To what extent can this result be applied to itself--that is, how many NOTs are needed to obtain K simultaneous complements? This leads to a whole theory in itself; see Gilbert [19541 and Markov [1958]. Clearly the sufficiency of two NOT's in obtaining K (an arbitrary number of) complements was unknown to Minsky. Yet to speak of "'applying the result to itself" was a pretty reasonable description of exactly the trick used in my 4-complement circuit. H o w could it be that he h a d envisioned the self-same possibility without ending up at the same configuration? Why on earth should a "whole theory" be required? My thoughts sped back to those sceptical friends who could "almost prove your 4-complement problem is insoluble." Previously I could afford to be smug, now it was me against Minsky, Gilbert, and M a r k o v - the latter a name of intimidating authority in the world of mathematics. Was it likely his theory would turn out to be wrong? Hadn't I after all overlooked some inherent logical flaw that rendered reflexive re-application of the circuit to itself in fact unworkable? I lost

no time in hunting up the papers from Gilbert and Markov. Alas, the journals were not available in Nijmegen; there was nothing for it but to order copies. That would take a week or so. In the meantime I returned to the 4-complement circuit, re-examining it from every angle. Later that evening I banged a defiant fist on the table. It was no good: Markov or no Markov, theory or no theory, there was nothing wrong with that circuit: it had to w o r k ! - - A n d w h y not demonstrate my reasoning agreed with reality by building it? The very next day saw me launched on construction.

The 4-Complement Simulator Physical realisation of the circuit followed conventional electronic practice. Taking standard ttl integrated circuits lying at hand (six SN74LS08's and eight SN74LS32's: 14 pin packages containing four 2-input AND's and OR's, respectively) and a prototype-development printed circuit card fitted out with 14-pin chip holders, using a wire-wrap pistol to make interconnections, assembly was completed within a matter of hours. An obvious approach in implementing the device was dictated by the very principle of operation: first build and test two quite independent Moore circuits, afterwards remove the inverters from one (a single SN74LS04 chip) and replace with connections to two inputs and outputs on the other. This is exactly what I did. In the cover photo, the twin Moore circuits are formed by the two groups of eight chips furthest from the multipin connector. In one circuit, four wires leading from the underside of the card to a small plug that replaces the discarded inverter chip are plain to see. Finally, to facilitate testing, a push-button controlled 4-bit binary counter and a sprinkling of light-emitting diodes (LEDs) were added. Successive presses on the button (see adjacent to the main connector) run the counter through 0000, 0001, 0010 . . . . . 1111, the seq u e n c e of sixteen possible 4-bit w o r d s . C o u n t e r outputs are wired to the four NOT-simulator inputs, the presently activated word being indicated by a line of four adjacent LEDs situated close by (on = 0, off = 1). Six remaining LEDs dotted about the board report on the high/low status of the 2 x 3 Moore circuit outputs. For ease of comparability one of these is duplicated so as to form a single line of four evenly spaced LEDs monitoring the four main outputs. These additions account for two of the three extra chips at one end of the board: an SN74LS93 binary counter and an SN74LS00 (four 2-input NAND's) used as a so-called set-reset flip-flop to eliminate pushbutton contact bounce problems. The need for still a further chip made itself felt when, having completed and tested the two separate Moore circuits, the final

4-complement simulator produced by combining them failed to work as anticipated! At first this was unnerving. Using an oscilloscope, however, the source of the trouble was soon tracked down: under certain input transitions Moore's circuit exhibits race-conditions. Race conditions arise w h e n delays introduced by hardware inertia result in unint e n d e d overlaps b e t w e e n logical state durations, leading to transitory "spikes" or pulses of very short duration (the antecedence of inverter A in the signal processing path now shows its significance; see Figure 4). Such spikes can be innocuous enough in many applications, but not so in the 4-complement simulator. Here, a spike emerging from output x' of the nested circuit becomes gated through the outer circuit to the input of its second inverter (B, see Figures 1 and 2 ) - itself, however, now simulated by channel y of the nested circuit. Our spike, in other words, traverses a sneaky feedback loop and now finds itself re-entering an input of the inner Moore circuit! A vicious circle has been established: regenerative oscillation sets in.

Figure 4. Race condition: Input word xyz changes from 101 to 100. Delayed reaction of second inverter (B) to first (A) causes brief pulse at the output of the AND to which they are connected. THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

27

Notice that the culprit here is not the feedback loop - - a n intrinsic feature of the nested scheme (to which we shall r e t u r n ) - - b u t the pulse generated by the race condition. Happily, a cure is easily effected through interposing a delay in the appropriate line (connecting the output of inverter A to the AND-gate input so as to ensure the latter cannot receive a 1 from the former until after the output of inverter B has changed to 0). This accounts for the last remaining chip in the photo (another SN74LS08: four AND's connected together head to tail, each contributing its own share to the aggregate delay thus created). With this modification completed, turning on the power once again, I finally had the satisfaction of verifying a perfectly functioning 4-complement simulator. It was a happy moment of vindication and triumph. The 4-complement circuit thus stood acquitted-though in hindsight it is amusing to recall exultation on completion of one of the most futile or, at least, r e d u n d a n t items of electronic apparatus ever constructed! The Great Unanswered Question n o w remaining, however, was how could this success ever be reconciled with the apparently contradictory theory of Gilbert and Markov? The working device was an unshakeable fact, yet a theorem in logic cannot be validated via any empirical demonstration, however suggestive. Could some sort of a disillusionment still lurk in the publications awaited?

A Gordian Not Unravelled Following eventual receipt of the anxiously awaited material, a rapid glance at Markov's and Gilbert's conclusions confirmed Minsky's original remark: blatant contradiction of the two-inverters-always-suffice idea. Steeling myself to the mathematics, I settled down to read. Gilbert's is the earlier, exploratory paper, his partial result later subsumed by Markov's more embracing work, " O n the Inversion Complexity of a S y s t e m of F u n c t i o n s " (translated b y Morris D. Friedman). We confine ourselves to the latter. Markov begins his monograph with a series of careful definitions. A small alphabet of the signs familiar from Boolean algebra is introduced, constants and variables included: {0, 1, xl . . . . . xn, &, Or, Not, (, )}. Certain words or strings of these are specified as formulas and sub-formulas, negative sub-formulas being characterized as those prefixed by " N o t . " The socalled inversion complexity of a system of sub-formulas is now identified with the number of distinct negative sub-formulas occurring in it. My pr6cis lacks his precision but the outline of what is going on here is already dear: substituting concatenations of discrete symbols for the tangled Celtic knotwork language of the switching engineer, Boolean formulas replace circuit diagrams: " N o t " s are to be counted instead of inverters. 28

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

So far so good. Moore's problem itself might well have been so reformulated as to ask for a system of Boolean functions equivalent to x' = Not(x), y' = Not(y), z' = Not(z), but in which "Not" (preceding a distinct sub-formula) would occur no more than twice. O u r previously derived set of three formulas describing Moore's circuit is just such a solution. As before, we are merely talking about the same thing in a different language. Markov's list of definitions ends abruptly with a bold statement of his result, followed by a one-page l e m m a r u n n i n g into s u b - s u b s c r i p t e d , s u b - s u p e r scripted variables that "plays an essential role in the proof." The full proof is spared u s - - t h e author doubtless feeling a recapitulation of the obvious would be too t e d i o u s - - a n d so ends his paper. It is just as well: that lemma might have been written in Celtic for all I could make of it (printing errors abound, too). Not that I felt especially over-confident in challenging his mathematics. This was a g o o d instance of w h a t Richard Guy calls proof by intimidation. But what was that result? Following Markov we must be quite precise here. Consider a system of m Boolean functions of n arguments. It can be defined by different systems of m formulas in n variables. Take n o w a worst case instance of such a system of functions in which the number of distinct negative sub-formulas necessary to their definition is at its greatest. Then, says Markov, the least number of negative sub-formulas that will have to appear in the formulas defining the functions will be [log2n [ + 1 = the number of digits in the binary representation of n. (The vertical strokes indicate the truncated value of log2n. ) Thus Ilog2nl + 1, otherwise known as I or the inversion complexity of the system of functions, is indeed the Markovian equivalent to the minimum number of separate inverters that would be required in any network implementation of its formulas. Note that m, the number of functions (or formulas) does not actually enter into it. (Think of all the recoders that can be connected to Moore's 3-bit to parallel decoder, each yielding a n e w output function, none d e m a n d i n g extra negations). We can examine this further by taking Moore's problem as a example. Translating into Boolean terms, our question concerns a system of three functions (x' = Not(x), y' = Not(y), z' = Not(z)), of three arguments (x, y, z). Applying Markov's result we find n = 3, log23 = 1.5849 . . . . h e n c e ! = 1 + 1 = 2. That agrees with our conclusion: two inverters are sufficient. But what about the 4-complement problem? N o w n = 4, log24 = 2, I = 2 + 1 = 3. Three inverters are required. That disagrees with our conclusion. In effect, Theorem I above would assert that I = 2, irrespective of m and n. Here we have a contradiction. The collision here is so acute that something will

have to give way. And so it proves. Forcing the issue to a head, an o b v i o u s step n o w is to p r o d u c e a counter-example to Markov's result by writing out the 4-complement circuit as a system of Boolean formulas, thus demonstrating that only two distinct negative sub-formulas need appear. And indeed, with this comes a breakthrough and the resolution to this whole curious dilemma. The scales, so to speak, are about to fall from our I's. For with an attempt to write out a set of formulas depicting the 4-complement circuit comes the discovery that no Boolean representation of it exists. The barrier to deriving a Boolean representation is revealing. Looking back at the 4-complement block diagram (Figure 2), recall that Network 2, the nested box, is a pure Moore circuit for which we already have a system of formulas. To represent the complete 4complement box, however, we first need to respecify x, y, and z - - t h e inputs to the nested b o x - - i n terms of the n e w set of arguments: a, b, c, and d, the new main inputs. The obstacle to achieving this appears in finding that no expression for y can be derived without y occurring as one of its own arguments! H o w does this come about? It is our old friend the sneaky feedback loop, reminding us that this is no longer a simple combinational circuit like Moore's. Through the nesting of one box in another a primitive form of memory has been introduced whereby it has become a sequential switching circuit w h o s e subsequent internal state depends both upon present inputs and current state: the present value of y plays a part in determining y's n e w value. In short, the 4-complement circuit is really a finite state machine, a device w h o s e context-sensitive action lies b e y o n d the descriptive scope of Boolean formulas. The facile notion that everything can always be "talked about in a different language" is thus not without its pitfalls. Still sneakier (and this really is rather subtle), the 4-complement circuit is a finite state machine mimicking the behaviour of a non-sequential machine, the latter comprising a humble combinational circuit of just four inverters: a' = Not(a), b' = Not(b), c' = Not(c), d' = Not(d). Here we have the peculiar case of a higher or meta-Boolean form of life disguised as a lower, Boolean form. The camouflage is truly effective too, since no experiment conducted on the terminals of the 4-complement (black) box could determine whether it contained Boolean or non-Boolean-representable entrails. (Although c u r i o u s l y - - a n d here is another tricky t w i s t - - t h e non-Boolean circuit is actually composed entirely of Boolean components--AND's, OR's and N O T ' s - - a n indication both of the import of their interconnection pattern and of the source of weakness in the algebra that cannot describe it.) A fine distinction is involved in all this that it is worth being clear about. The familiar (two-element) Boolean function describes a relation or mapping be-

tween one two-valued variable (the value of the function) and others (its arguments). As such it may be expressed or specified in different ways; in a tabulation of corresponding values, for instance. Often we represent it as a Boolean formula, that is to say, as a legal expression in the formalism called Boolean algebra. In that case the dependence of the formula's value on that of its variables will strictly mirror that of the function on its arguments. Moreover, any Boolean function can always be described by a Boolean formula. But that is not to say that it has to be so represented or that a specification or implementation of the function must d e p e n d on some analogous structure or mechanism. The 4-complement finite state machine is an example of an alternative implementation, its effect representable by a' = Not(a), etc., but its internal operation (as embodied in its circuit diagram) having no counterpart in Boolean algebra. The importance of all this is that generalizations about devices that perform Boolean functions are not to be reliably based solely on inferences about Boolean algebra representations of those functions. So it is that the s u p p o s e d discrepancy b e t w e e n Markov's condusion and Theorem I turns out to be illusory. The meticulous definitions at the beginning of his paper are not to be overlooked. As a careful reexamination of the account above will show, the result he proves is explicitly restricted to Boolean functions realized in Boolean formulas. Our concern, on the other hand (if only lately appreciated), has been with Boolean functions realized otherwise. Minsky's implication notwithstanding, Markov's work is simply inapplicable to the case in hand. Like the 4-complement box, the K-complement box need employ no more than two inverters. But at least Ilog2KI + I distinct negative subformulas will be required in any Boolean formulas describing the input-output functions of the latter. No contradiction is implied. E. N. Gilbert's paper, incidentally, which also addresses the minimum inverter requirement question is equivalently restricted, his analysis being confined to loop-free networks. Even so, doesn't a.suspicion linger that the K-complement simulator is in some w a y yielding something for nothing? After all, inverting binary signals is a concrete if trivial operation, analogous to flipping over coins so as to make heads from tails or tails from heads. In the end, just h o w is it that K such reversals can be effected given only two reversing-machines? The answer is simple. It is done by using those machines more than once. Through reiterated application we can achieve serially the same result as K single-action machines working in parallel. But at a price, to be sure. Here is how John E. Savage puts it in The Complexity of Computing [4]: "Sequential machines compute logic functions, just as do logic circuits. However, since sequential machines use their memories to reuse THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

29

their logic circuitry, they can realize functions with less circuitry than a no-memory machine but at the expense of time" [my italics]. As we saw earlier, hardw a r e - i m p l e m e n t e d logic introduces lag. As K increases, so will the number of passes through feedback paths in the nested circuitry, and the longer final outputs will take in responding to changing input patterns. In practice this would be a serious factor to consider.

I t is amusing to recall exultation on completion of o n e of the most futile or, at least, red u n d a n t items of electronic apparatus ever constructed! Lastly, note h o w Savage casts incidental light on the reason w h y a single i n v e r t e r - - h o w e v e r combined with AND's and O R ' s - - i s inadequate for simulating further negators. Negation of externally presented bits on one channel will always require one inverter. But at least a second will be d e m a n d e d in creating the memory needed in re-utilizing that first. In fact, as we have seen, two inverters are both necessary and sufficient. Simple but hard-won insights are compressed into the foregoing paragraphs. Having gained clearer understanding, a letter to the author whose casual remarks unwittingly triggered this improbable detective story seemed not inapposite. I was gratified thus w h e n , in a s u b s e q u e n t c o m m u n i c a t i o n , Marvin Minsky warmly concurred in the above analysis, graciously conceding a too hasty perusal of Gilbert's and Markov's articles. Likewise, his "To what extent can this result be applied to itself?" turned out to be a mere chance form of words, no reference to recursion i n t e n d e d , b u t r e s o n a n t to me u n d e r the circumstances. Thus were the K-nots disentangled from a Markov chain of deduction, and the sufficiency of two negators in producing moore inverters ad libitum confirmed.

Conclusion The inception of this narrative was a puzzle appearing in Abacus. As a matter of fact, the question there posed came in two, supposedly equivalent versions: Moore's original problem in circuit design and a seemingly analogous problem in computer programming. In the latter form we are asked to "write an [assembly language] program that will store in locations U, V, W the l's complement of locations x, y, and z. You can use as many COPY, OR and AND instructions as you like, but you cannot use more than two COMP (l's complement) instructions." This second version is absent from Wos et al's Automated Reasoning [6], ap30

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Figure 5. The 4-complement circuit in Pascal.

pearing only subsequently in his synoptic Abacus article. The trouble is, although purportedly isomorphic with the network puzzle, the conditions now imposed are actually more restrictive than Moore's, a whole class of solutions becoming inadvertently excluded. What is it that makes the program version different? In effect it is a silent prohibition against certain kinds of perfectly valid circuit configurations: a ruling out of the use of feedback loops implicit in the preclusion of a JUMP instruction. Self-modifying functions would be excluded from representation in software. That is, for every program solution there would be an equivalent circuit, but not vice versa. Just as sequential networks defy description in the notation of Boolean algebra, so loops in any circuit solution will defeat implementation in such a program. The slip is an easy one to make, and especially so w h e n Moore's o w n published circuit uses no feedback. Perhaps it was familiarity with this that unconciously acted to restrict Wos's contemplation to combinational type solutions only. Let us make no mistake however: discarding one channel from the 4-complement simulator would leave a three-channel device answering all the demands of Moore's problem. Here we have a finite state machine solution (one of an infinity) that cannot be represented in the above reduced instruction code. I suspect that in the urge to translate Moore's problem into terms suited to his automated reasoning program, Larry Wos temporarily underestimates and thus misrepresents the complexity and potential of networks using AND's, OR's and NOT's. [In p a s s i n g - - a n d without any reference to the aforementioned a u t h o r - - t h e tendency to see circuit diagrams as engineers' easy-to-read-picture-book-explications of "real mathematics" envisioned in putative formulas is not uncommon among mathematicians. Engineers, I may add, humble as their mental endowment may be, will be more impressed when condescension can be matched with insight into the advantages of a two-dimensional language.] Whether or not the automated reasoning technique could be successfully applied to the 4-complement problem is a further interesting question. Following the lead suggested here, the 4-complement circuit is elegantly modelled in a simple computer program using iteration to imitate the feedback loop. A series of assignment statements based on the earlier derived formulas describing Moore's circuit make up the body of the program. Figure 5 shows a version written in Turbo Pascal. Read in conjunction with Moore's circuit and Figure 2, the program is selfexplanatory: more eloquent in fact than any verbal commentary on circuit operation. Interested readers

THE MATHEMATICAL INTELL1GENCER VOL. 12, NO. 1, 1990

31

may like to try the effect of including a Write statement in the Repeat loop so as to expose the behaviour of y under different input sequences. A final observation on Markov's result must bring this account to a close. Figure 3 depicted the endlessly expandable system of recursively nested Moore circuits for producing an arbitrary number of NOT's. Winning three NOT's from two, every level of nesting yields a spare inverting channel. In practice, however, the mass-production of NOT-functions can be enormously accelerated. How? Notice that Markov's I is still only 3 for n as high as 7. But this is another way of saying that a simple combinational circuit exists that can simulate seven inverters directly from three. Similarly, from these seven a further 127 can be produced at only the third level of nesting: 2 --~ 3 --* 7 --~ 127 -~ . . . . Readers may like to test their grasp of the foregoing by writing a program that implements seven inversions while using only two Not operators. In conclusion, and before any false hopes are raised though, I ought to say that the above suggestion is intended merely as an exercise. Patents, it must be explained, have already been granted and the Sal-Mar International Inverter Hire Company, Inc., is due for launching at an early date. Prompt negations of the highest quality will be available to customers via standard phone lines. Charges are expected to be modest. In the meantime--call me an adulterated Platonist if you w i l l - - I presume that up in heaven two eternal NOT's await the arrival of virtuous logicians (and the occasional virtuous engineer). I look forward to rubbing that in with G6del and Russell hereafter.

As an engineer I felt only sheer surprise that, in principle, all the millions of inverters in use throughout the world could be "'seeded" from a single pair.

[Grateful thanks are due to Jim Propp, formerly of the Department of Mathematics, University of Maryland, whose searching criticisms brought to light various errors and made for substantial improvements to an earlier draft of this paper.]

References 1. B. Russell, The Autobiography of Bertrand Russell, Unwin (1978), p. 466. 2. C. E. Shannon, A symbolic analysis of relay and switching circuits, Trans. AIEE 57 (1938), 713-723. 3. G. A. Montgomerie, Sketch for an algebra of relay and contractor circuits, Jour. IEE 95, Part III (1948), 303-312. 4. J. E. Savage, The Complexity of Computing, Wiley (1976). 5. L. Wos, A Computer Science Reader, Ed. E. A. Weiss, Springer-Verlag, (1988), pp. 110-137. Orig. pub. Abacus, vol. 2, no. 3 (Spring 1985), pp. 6-21. 6. L. Wos, R. Overbeek, E. Lusk & J. Boyle, Automated Reasoning, Introduction and Applications, Prentice-Hall (1984). 7. M. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall (1967), p. 65. 8. E. N. Gilbert, Lattice theoretic properties of frontal switching functions, Jour. Math. & Physics 33 (April 1954), 57-67. 9. A. A. Markov, "On the inversion complexity of a system of functions" (translated by M. D. Friedman), JACM 5 (1958), 331-334. Orig. pub. Doklady Akad. Nauk SSSR 116 (1957), 917-919. Buurmansweg 30 6525 RW Nijmegen The Netherlands 32

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Karen V. H. Parshall*

With this issue, the Years Ago department changes its editor but not its basic editorial policy. It will continue to chronicle major anniversaries (25th, 50th, 75th, lOOth, etc.) of important and interesting mathematical events. In a departure from the past, however, the editor will solicit a number of contributions each year for publication in the column. Readers are welcomed and encouraged to send proposals, suggestions, comments, and criticisms to me.

It is with great sadness that I report the death of my predecessor in this job, Allen Shields. I had hoped to take this opportunity to thank him for his efforts in bringing the history of mathematics before a wider audience on the pages of the Mathematical Intelligencer. I shall try to uphold the example he set. Karen V. H. Parshall

A Voyage with Three Balloons R.-P. Holzapfel Consider three examples of plane curves y = p2(x), y2 = p3(x), y3 = p4(x), where pk(x) denotes a polynomial of degree k. These simple curves are closely connected with the creation of mathematical theories. I want to use them as balloons for trips over old and new mathematical landscapes.

in the second half of the last century. The first equation describes a parabola. Much stimulation for the s t u d y of q u a d r a t i c s came f r o m physics: optics, acoustics, gravitation, etc. We switch from real geometry to complex analytic function theory by considering the integral

f

dz - I dz p~z) (z - a)(z - b)

The First Voyage The first of our curves will not bring us to recent developments. It should be used for training in navigation. Starting from antique shores we will reach Berlin

along a path in the complex z-plane. The integral can be calculated from the antiderivative ln[(z - a)/(z - b)]/ (a - b) of 1/p2(z) (a ~ b). So the problem is reduced to the study of the elementary function w(z) = In(z).

* Column Editor's address: D e p a r t m e n t s of Mathematics and History, University of Virginia, Charlottesville, VA 22903 USA.

THE MATHEMATICALINTELLIGENCERVOL. 12, NO. 1 9 1990Springer-VerlagNew York 33

Looking around, we have reached the 18th century, w h e n elementary complex analytic function theory was b o r n a n d m a t h e m a t i c s b e c a m e an organized science with its o w n inner laws of development. The new era was opened by Isaac Newton and Gottfried Leibniz; L e o n h a r d Euler initiated f u r t h e r major changes in viewpoint. Understanding In(z) as a complex analytic function presented some difficulties. J. Bernoulli believed that I n ( - r) = In(r) for real numbers r # 0, whereas Leibniz thought that I n ( - r ) was an imaginary number for r > 0. In a correspondence of 1712/1713, each of these mathematicians found good arguments against the opinion of the other. The situation was clarified by Euler: In(z) is a multivalued function. We will symbolize multivalued functions by means of several arrows. For example, we write In: C* --~ C, C* = C \ {0}, C the complex numbers. The periodic inverse function z = exp(w) = ew clarifies the situation completely. It is described in the following inversion diagram: In / C*

Z~ex p

(1)

.C

The symbol 27 means that exp is also understood as the quotient map C --* C/Z = C* C C with the Z-action w --*w + m.2~ri, m E Z, o n C . Our route leads us n o w to special values of the elementary function exp. The values at the torsion points of the additive group C/77 are the roots of unity ~ = e 2~rim/n, m,n E Z, n ~ O. The theory of cyclotomic fields Q(~) is a cradle of algebraic number theory. We remember that Karl Friedrich Gauss reduced constructions of regular n-gons to calculations in these fields called "Kreisteilungsk6rper." His successful synthesis of geometry, algebra, and number theory, especially the construction of the 17-gon, led him to study mathematics rather than languages. The important role of cyclotomic fields in the theory of algebraic numbers is expressed in the completeness theorem of KroneckerWeber: Each absolutely abelian number field (finite abelian Galois extension of Q) is a subfield of a cyclotomic field. N o w our first trip is finished. We will come back to Leopold Kronecker later. The

Second

To me, there is little interest in that aspect of integral calculus where we use substitutions, transformations, etc.-merely clever mechanical tricks--in order to reduce integrals to algebraic, logarithmic, or trigonometric forms, as compared with the deeper study of those transcendental functions that cannot be so reduced. We are as familiar with circular and logarithmic functions as with one times one, but the magnificent goldmine that contains the secrets of higher functions is still almost completely terra incognita. I have, formerly, done much work in this area and intend to devote a substantial treatise to it, of which I have given a glimpse in my Disquiss. Arithmeficae p. 593, Art. 335. One cannot help but be astounded at the great richness of the new and extremely interesting relations that these functions exhibit (the functions associated with rectification of the ellipse and hyperbola being included among them). G a u s s on his o w n could not carry out the programme mentioned in the letter. A central theme in the creation of the fundamentals of analytic function theory during the last century was the theory of hypergeometric functions. Gauss was the first to consider hypergeometric series as functions of a complex variable. In this connection he introduced and investigated the circle of convergence (1813). Instead of a general definition of hypergeometric functions, we present a simple example coming from a variation of elliptic curves:

Voyage

The second balloon will carry us to new heights. If p3(x) has three different zeros, then the curve E defined by y2 = p3(x) is an elliptic curve. Elliptic curves arise from the rotation of a solid body around a fixed point. Karl Jacobi proved in Crelle's Journal 39 (1850) that for important special cases already investigated by Euler, Louis Poinsot, Ren6 Francois Lagrange, and Sim6on Poisson, the rotation can be described by 34

means of elliptic integrals t(s) = f~o dz/PV'~)k(z), k = 3,4. Knowledge of the function s(t), t the time coordinate, is the key to an explicit description of the motion. Periodicity of the rotation forces t(s) to be a multivalued function and s(t) to be periodic. Indeed, Niels Abel was the first to discover the double periodicity of the inverse meromorphic function s, called an elliptic function. Independently Jacobi came to the same result. Later he presented elliptic functions as quotients of theta-functions. Special cases of these quasiperiodic holomorphic functions had already appeared in the work of J. Bernoulli, Euler, and Jean Baptiste Fourier. Fourier used them to solve the heat equation (1826). Karl Weierstra~ later erected his pyramid of the theory of abelian functions of one, two, and several variables. However, with our second balloon we will not fly to higher dimensions. We are more interested in non-euclidean arithmetic and function theory. Coming from the arithmetic and geometric side, Gauss was led to a new point of view. In an 1808 letter to Heinrich Schumacher he wrote:

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

k2 - k y = F(t) = 1 + ~~ ( . 1 . 3 . 5 - . .2. ( 2 It!

1)) "t k

(2)

satisfies the special hypergeometric differential equation 1 - 2t y"+ - - y ' t(1 - t)

1 4t(1 -

y = 0. t)

(3)

value of x, and conversely many values of x correspond to a given value of y, then one can ask whether one cannot express both y and x as single valued functions of a third variable t. A case in point is the example of elliptic functions, in which we can express, not merely the algebraic functions on a Riemann surface, but also the integrals of the first and second kinds, as single-valued functions of a third ('uniformizing') variable, namely the integral of the first kind. We can say, therefore: It is a general problem of analysis, in the discussion of analytic relationships, always to find a 'uniformizing parameter'. We look for a description of the inverse map of 4. It turns out that the triangles are fundamental domains of a lattice subgroup F of the group of biholomorphic automorphisms of the disc D. By means of a projective coordinate change we can assume that D C pl is the upper half-plane H = {z E C: Imz > 0} C pl with the automorphism group SL2(~). Then F is the congruence subgroup of SL2(77) defined by the exact sequence 1 --* F ~ SL2(7/) ~ SL2(Z/27/) ---) 1. The inversion diagram for ~ = yl/Y2 is"

Figure 1. Tesselation of the disc.

Up to a constant factor the hypergeometric function F can also be presented as a special hypergeometric integral dz

(4)

X/z(z - 1)(tz - 1)' where b,c ~ {0,1,~} and t ~ {0,1,~}. Think of F as a multivalued function of t on C\{0,1} = P1\{0,1,oo} (here pl denotes the Riemann sphere C U {~}). Following an idea of Georg Friedrich Riemann, Herm a n n Amandus Schwarz gave a nice description of the multivalence in 1873. He considered two independent solutions Yl,Y2 of (3) and their quotient ~ = yl/y2, which maps C \ ~ + (~+ = {r ~ ~: r I> 0}) onto an open triangle in a disc. By analytic continuation across the real half-line R +, the values of ~ fill the disc. The disc is tesselated by infinitely m a n y triangles as shown in Figure 1. The triangles are congruent from a non-euclidean point of view, making evident an important connection between analysis and non-euclidean geometry. We continue with a quotation from Felix Klein's lect u r e s on h y p e r g e o m e t r i c f u n c t i o n s ( G 6 t t i n g e n 1893/94): Now we want to apply our triangle figures in another direction, by asking: When is the (generally multi-valued) function ~(x) uniquely invertible, that is, when is x a single-valued function of ~? This is a special case of a quite general problem in function theory, arising from the desire to avoid operations with multivalued functions as far as possible. In general, if one has a functional dependence y(x) in which many, perhaps infinitely many, values of y correspond to a given

~////i~

ENN= El/E2

(5)

P~\{O,I,o~}--~ P~\{3 points} C P~ where e is a F-automorphic function. By analogy with elliptic and theta-functions, ~ can be realized as a quotient of two holomorphic quasi-periodic functions, more precisely, as a quotient of two F-automorphic forms of weight 1. Up to a cusp condition, F-automorphic forms of weight m are defined as holomorphic functions f on H satisfying the functional equations f(~(z)) " j~m(z) = f(z), ~/ e r, Jr = d~//dz.

(6)

From the algebraic point of view the forms E1,E2 appear as generators of the ring of F-automorphic forms of arbitrary weight. H. A. Schwarz's article is not restricted to our example involving modular forms. He also determined all h y p e r g e o m e t r i c f u n c t i o n s p r o d u c i n g triangle groups. Later the theory was greatly extended by F. Klein and Henri Poincar& Poincar4 started from a class of second order differential equations containing (3) as a special case, called Fuchsian equations. Looking not only to G6ttingen but also to Berlin, he brought into being a non-euclidean analogue of Weierstrass's elliptic function theory. We now turn to Berlin to understand Kronecker's "liebsten Jugendtraum." In some mysterious fashion, Kronecker saw the possibility of proving an analogue of the completeness theorem for absolutely abelian n u m b e r fields: The abelian extensions of imaginary quadratic n u m b e r fields are contained in n u m b e r fields generated by special values of elliptic functions THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990 3 5

and of the modular function j (Hauptmodul in Dedekind's terminology). This idea is the cradle of class field theory, the heart of algebraic n u m b e r theory. The precise theorem was proved by Tagaki in 1920. The special values on the elliptic curves are torsion points. The special values for the modular function are "singular m o d u l e s " ("singu1/ire M o d u l n " ) . We w a n t to u n d e r s t a n d t h e m as a non-euclidean version of torsion points.

the soul of our science. A last side-glance indicates the intimate interaction of arithmetic and analysis: The Eisenstein series oo

cr3(n)e2~rin"

E 2 = 1 + 240 ~ n=l oo

E3 = 1 - 504 ~ , r

2~in"

r

= ~

n=1

a k (7)

din

are the normalized Fourier series of g2('r) or g3(~-), respectively.

In some mysterious fashion, Kronecker saw the possibility of proving an analogue of the completeness theorem for absolutely abelian The Third Voyage number fields. First we look at the moduli space of elliptic curves, which parametrizes all isomorphism classes of elliptic curves. In (4) the variable t appears as a parameter for elliptic curves. With a glance at the diagram (5), we define the analytic family {E~},dn of elliptic curves in Weierstrass's normal form: E,:

y3 = 4(x - ex(~))(x - e2(T))(x - E3(~)) = 4x3 - g2(T)x - g3(T).

We choose ~1,e2,E3, with e 3 ~- - - ~1 - - ~ 2 , i n a symmetric m a n n e r with r e s p e c t to the s y m m e t r i c g r o u p S3 SL2(77)/['. The moduli curve is H/SL2(7/) = ( H / [ ' ) / S 3 pl\{oo}. The values of the modular function j(~) = 1728 ~(T)/(g23(~) - 27g2(-r)) are in one-to-one corres p o n d e n c e with all i s o m o r p h i s m classes of elliptic Curves.

In order to explain "singular moduli" w e look back to the exponential map. The pre-images ~ on C of torsion points of C/2~ri77 are characterized b y the two equivalent conditions:

The third balloon will bring us to higher dimensions. We start at the end of the last century in Paris, w h e r e w e find an immediate and important continuation of Weierstrass's w o r k in the hands and heads of H. Poincar6, Charles Emile Picard, and Paul-Emile Appell. We discover the first fine analysis of the family of curves {y3 = p4(x)} in a paper by Picard in Acta Mathematica (1883). This family appears in the hyperfuchsian integrals I(tl,t2) =

3Vz(z -

1)(z

-

6)(z - h ) "

w h e r e b,c E {0, 1, oo}, (tl, t2) E T** C C 2, T** = {(tl, t2) C2:tl, t 2 ~ {0, 1), t~ ~a t2}. The integrals satisfy the Euler partial differential equation 32F

a +

c~tlc~t2

-

a

-

t 2 --

OF

+ t2

-tl

--

0, a

=

1/3.

t2 3t2

This equation can be completed to a system of three partial differential equations w h o s e solutions are the multivalued functions I(t 1, t2) and their linear combinations (see Euler-Picard system below). The solution space has three dimensions at each point P0 = ( t~ to) (i) q(r -----0 m o d 2~ri, T**. Three of the above integrals 11, I2, I3 form a basis of (ii) (q + 1)or -= cr mod 2~ri, q e Q* ~ GLI(Q ). this space in a neighbourhood of P0. Starting at P0 w e can develop (/1,/2,/3) along paths cr in T** by analytic The torsion condition (i) is translated to the fixed point continuation. Passing through a cycle a each Ij, j = 1, condition (ii). Fixed point conditions make sense also 2, 3, changes to a linear combination of 11,/2,/3. In this for spaces w i t h o u t additive structure. The fixed points w a y one obtains a m o n o d r o m y representation of the q" of elements of GL~(Q) = {g E GL2(Q): det g > 0} fundamental group ~1 (T**, P0) in C 3. acting non-trivially on H are the "singular moduli." It Using five generators Picard found a unitary monoturns out that k, = Q(r is an imaginary quadratic d r o m y r e p r e s e n t a t i o n ~rl(T** ) --~ U((2, 1), C). The n u m b e r field, k = k, a p p e a r s a g a i n as the field group U((2, 1), C) consists of all elements of GL3(C ) Q (~) End(E,) of "complex multiplication" of E,. These respecting the hermitean metric lul2 + Ivl2 - Iwl2 on curves go with the child called class field theory. The C 3. In Picard's notation the five generators are called algebraic n u m b e r j(~) generates the maximal unrami- fundamental substitutions. Some years later Poincar6 defled abelian field extension of k, which is the absolute fined general f u n d a m e n t a l g r o u p s in his w o r k on class field of k. Analysis situs, which was the foundation-stone of algeThe theory of elliptic curves is a huge field of clas- braic topology. sical and present-day research, but w e will stop our N o w U((2, 1), C) acts on the complex unit ball B = second trip here. We w a n t to stay on the intersection {(u, v):lu[2 + Ivl2 < 1} in C 2. Picard was aware of the line of several branches of mathematics because this is central role of his model for further investigations. 36

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Figure 2. The ball B is projected onto the punctured complex branched along the six lines with ramification index 3. The projective plane T* = P2\{P1, P2, Pa, P4}- The four omitted S4-quotient of the complement T** of the six lines in p2 is the points are images of four cusps k1, k2, k3, k4 (and their F- moduli space of smooth Picard curves. The values of the orbits). Six discs in B (and their F-orbits) are projected on multivalued integral map (I1:12:13)fill the complement of the the six lines through the points P1, P2, P3, P4. The mapping is F-orbits of the six discs in B. Looking for unitary modular functions he remarked: "'Our functions of u, v p l a y . . , the same role as the modular function in the theory of elliptic functions." In the monograph "Th60rie de courbes et de surfaces alg6briques" Picard later referred back to his old work: "We have sought, Mr. Alezais and I, to prepare the ground for such i n v e s t i g a t i o n s . . , by doing some preliminary arithmetic studies." The situation can be clarified by modern methods. The main points are concentrated in the following inversion diagram: (I1 : I 2:I3) _,, B.

(el: ~2: e3: %)

(8) T** ~ T *

L \ P 2 \ { 4 points}.

11, 12, 13 are three linearly independent solutions of our Euler-Picard system. F is the congruence subgroup defined by the exact sequence 1 -+ r -+ U((2,1),9 ~ U((2,1),O/(1 - o~)O) --+ 1,

where 00 = e2"u3 and 9 = Z + 77o~is the ring of Eisenstein integers, e 1, e2, e2, e 4 satisfy el + (~2 + E3 q- ~4 = 0 and are fundamental F-automorphic forms (of Nebentypus). The normal forms 4

C(u,v):v 3

=

1-I (x

-

=

i=1

x 4 + G2(u,v)x 2 + G3(u,v)x + G4(u,v),(u,v ) E •,

define an analytic version of Picard's curve family. The moduli space for Picard curves is B/U((2, 1), O) = (B/F)/S 4 = (P2/$4)\{1 point} (compare with Figure 2.) Singular moduli are defined as isolated fixed points on B of elements of the group U((2, 1), Q(o~)) respecting the hermitean (2, 1)-metric on C 3 up to a constant factor. N o w it again happens, as in Kronecker's case, that the generating U((2, 1), 9 functions take values in algebraic number fields at the singular moduli. The first proof working for a class of these points was presented by H. Shiga [6] in 1986. He lifted Helmut Hasse's analytic proof for Kronecker's THE MATHEMATICALINTELLIGENCERVOL. 12, NO. 1, 1990

37

case to the second dimension. The modular forms ~i are p r e s e n t e d explicitly as theta-constants. Their Fourier series look like those of E2, E3 in (7) but with explicit theta-functions as coefficients instead of crk(n). The intimate interaction of arithmetic, complex analysis, and n o n - e u c l i d e a n g e o m e t r y is obvious. It sounds surprising, but all the results can be obtained by means of algebraic geometry. Moreover, algebraic geometry plays a double role. On the one hand it The power

of algebraic geometry lies in the combination of technique with a new kind of intuition.

compensates for the loss of immediate intuition in classical non-euclidean geometry (see for example Figure 1). On the other hand the fine techniques of algebraic geometry remove all obstructions to a proof. The power of algebraic geometry lies in the combination of technique with a new kind of intuition. David Hilbert proclaimed a very general continuation of K r o n e c k e r ' s " J u g e n d t r a u m . " In the 12th problem of his Paris lecture (1900) Hilbert designated this extension as "one of the deepest and most farreaching problems of number theory and function theory." A more concrete continuation can be found in Erich Hecke's work on Hilbert modular functions. From his thesis we quote: "The most general thetafunctions of this kind lead directly to the functions of Hilbert and Picard." Now, for Picard curves the "Jugendtraum" climbs up towers of surfaces constructed recently by Hirzebruch, which we could identify as towers of Picard modular surfaces ([2], [4]). Keeping in mind the non-euclidean nature of the moduli space of Picard curves coming from the ball B, we turn back for a moment to the classical origins of Euler's equations O2F a OF a OF -+ --.-+ . . . . OrOs s - r Or r - s as

0, F = F(r,s).

(9)

There are only a few hints at Euler's work on these equations in connection with acoustics. One can be found in the "Festschrift zur Feier des 200. Geburtstages Leonhard Eulers'" (Teubner, 1907). In his treatise "Ueber die Fortpflanzung ebener Luftwellen von endlicher S c h w i n g u n g s w e i t e " (Abh. d. Kgl. Ges. d. Wiss. G6ttingen, 8, 1860) Riemann proved, without any reference to Euler's work, that the equations (9) govern the propagation of gas waves. We quote from the introduction to his paper: "Although the mathematical treatment up to this point has proved to be sufficient to explain the experimental phenomena observed so far, it m a y well be j u s t i f i e d - - w h e n one looks at the great advances made recently by Helmholtz in the e x p e r i m e n t a l t r e a t m e n t of acoustic 38 THE MATHEMATICALINTELL1GENCERVOL. 12, NO. 1, 1990

problems--to hope that the results of this more precise study may, in the not too distant future, provide some starting points for this n e w experimental research. This hope, apart from the intrinsic theoretical interest of treating non-linear partial differential equations, may justify the present communication." Riemann constructed two auxiliary functions r, s, starting from the density and velocity of the gas or its particles, respectively. Then there follows a remarkable inversion step. He switched the roles of the pairs (r, s) and (6, ~') where 6, ~"are the variables of place and time. That means that 6, ,r are locally understood as functions of r, s. The solution F = F(r, s) of an Euler equation provides multivalued functions 6, 7, solving the problem up to inversion. Mathematically, the situation is similar to the rotation of a solid body when time is expressed by an elliptic integral. Picard's curve family involves special Euler partial differential equations together with solutions. The study of papers by Picard, Appell, and related authors (modem treatments are [3] and [8]) induces the feeling of a certain duality between the Euler equations and n-th root integrals J'~t dx/"V'x(x - 1)(x - tl) . . . (x - tr) taken along cycles on the cycloelliptic curves (Serge Lang called them "superelliptic") Ct: y" = Pr+2(X) = Pr+2(x;t), t = (t 1..... tr) ~ Y'** C

Pr(C).

The connecting objects are algebraic curve families "--> V**, ~ = ~ ( r , y/) = {Ct} t C Z * * . This duality can be made precise in the most obvious manner for n ~> 2, r /> 1, g.c.d.(n, r + 2) = l, 0 < l < n, completing systems of Euler equations to Euler-Picard systems: --+ OtiOtj

-

F=O,

n(tj

ti)

i O2F

I 1 <- i,j <<-r,i # j, Ot2 + n(tk _ 1)tk

gP(r,n,l) -

(r + 2)(tk - 1 ) -

k = 1. . . . .

tk - 1

. F = 0,

r.

For fixed triples (l, n, r) as above the following duality theorem holds: 1.) All solutions of EP(r, n, l) are C-linear combinations of r + I linearly independent solutions of integral type F(t) = I,t dx/y I along local families of cycles {o~t}on {Ct}. 2.) Each (analytic) partial differential operator which annihilates the cycloelliptic integrals .f,,t dx/yZ lies in the sheaf E of ideals generated by the r 2 Euler-Picard operators appearing on the left-hand side of EP(r, n, I). The Euler-Picard operators are the only

differential operators of the form (O2/Ot,Otj + first order operator) belonging to the vanishing ideal E. For the proof of this duality we use modern techniques of algebraic geometry again, mainly GaussManin connections. A little game with symbols yields some insight into these structures. Consider the combination of three signs Dfoo, where o~ is a differential form depending on parameters and D a differential operator for these variables. Leibniz's venerable integral symbol stands like a wall between D and o~. After explaining carefully the meaning of differentiation of differential forms, we can write fDto. Now we omit the integral symbol f. In this way classical integral calculations are successfully delegated to structure problems for modules (or module sheaves) over rings (or ring sheaves) of differential operators. Finally, nice structure results can be converted into the concrete conclusions 1) and 2). The first accurate construction of Gauss-Martin connections can be found in a paper by Yuri Manin (1958). With these techniques Manin prepared his proof of Mordell's conjecture in the function field case (1963). In recent times the non-euclidean nature of moduli spaces of curves has attracted much interest from different directions, e.g., string theory and the theory of diophantine equations.* So it should also be of interest that cycloelliptic curve families are connected with higher-dimensional complex unit balls. Terada found unitary m o n o d r o m y representations of the corres p o n d i n g integral maps in [7]. Perhaps Riemann sensed the non-euclidean nature of the Euler equations w h e n he constructed solutions by means of hypergeometric functions (1860). One year earlier Riemann had lectured in G6ttingen on hypergeometric functions. The library of the H u m b o l d t - U n i v e r s i t y and the Academy archives (both in Berlin) possess the only (readable) manuscript of these lectures. It had been written at the inducement of H. S. Schwarz. Ludwig Bieberbach presented the manuscript to the University. In order to u n d e r s t a n d further developments we look back to diagram (8). For a moment we break it into two parts, the mulfivalued map on the left-hand side and the quotient map on the right-hand side. This happens automatically if one looks for inversions of cycloelliptic integral maps in general. Namely, for r I> 2 there are only finitely many cases where the m o n o d r o m y group is big enough to produce an inverse quotient map. These cases have been determined precisely by Pierre Deligne, George Mostow [3] and, independently, by T. Terada. An advance to n e w "terra incognita" allows us to compose multivalued maps and quotient maps again. The key is the solution of a higher-dimensional ver* Both theoriesmeet on a high levelin the article[1] by Beilinsonand Martin.

sion of the Riemann-Hflbert problem: To find differential equations of Fuchsian type with given monodromy group and singularities (Hilbert's 21st problem). A quotient map of a ball can be considered as a datum for the corresponding problem because it gives a lattice group and local branch data. Yoshida proved the existence of a system of differential equations of Fuchsian type with the given data (see [8]). In dimension two the data for Riemann-Hilbert's problem for the ball are already rather hidden. It is a difficult problem to find quotient surfaces of a ball. Here again algebraic geometry is hardly challenged. A leading example is the complex projective plane together with six lines as described in Figure 2. T. H6fer found all (27) ball coverings branched along these lines and along exceptional lines arising from blowing up some of their intersection points ([2]). The most eyecatching general result has been achieved recently by the Japanese mathematicians R. Kobayashi, I. Naruki, and F. Sakai [5]. They characterized ball quotient surfaces precisely by means of numerical data of surfaces, singularities, and branch divisors. In the m e a n t i m e - starting from Picard modular surfaces--we developed a t h e o r y of a r i t h m e t i c - n o n - e u c l i d e a n surface invariants with the general uniformization theory of algebraic surfaces in the background. Now we have finished our balloon trips over mathematical landscapes. We reached certain heights from where we could look back to the earth at any time; thus presenting some useful navigational experience from the mathematical heritage of Berlin.

Bibliography 1. A. A. Beilinson and Yu. I. Manin, The Mumford form and the Polyakov measure in string theory, Comm. Math. Phys. 107 (1986), 359-376. 2. G. Barthel, F. Hirzebruch, and T. H6fer, Geradenkonfigurationen und algebraische Fliichen, Aspekte der Mathematik, Vieweg-Verlag, Braunschweig/Wiesbaden, to appear. 3. P. Deligne, and G. D. Mostow, Monodromy of hypergeometric functions and non-lattice integral monodromy, I.H.E.S. Publ. Math. Paris 63 (1986), 5-106. 4. R.-P. Holzapfel, Chem numbers of algebraic surfacesHirzebruch's examples are Picard modular surfaces, Math. Nachr. 126 (1986), 225-273. 5. R. Kobayashi, I. Naruki, and F. Sakai, Theory of minimal models for open surfaces and the numerical characterization of ball quotients, preprint. 6. H. Shiga, On the construction of algebraic numbers as special values of the Picard modular function, Chiba University, preprint. 7. T. Terada, Fonctions hyperg6om6triques F1 et fonctions automorphes I, II, J. Math. Soc. Japan 35 (1983), 451-475 and 37 (1985), 173-185. 8. M. Yoshida, Fuchsian differential equations, Asperkte der Mathematik Ell, Vieweg-Verlag, Braunschweig/Wiesbaden (1987). Karl-Weierstrafl-Institut far Mathematik DDR-1086 Berlin German Democratic Republic THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

39

Memorial Address for J. Frank Adams J. Peter May

Editor's note: J. Frank Adams, the Lowndean Professor of Astronomy and Geometry at Cambridge University, was killed in a car crash on 7 January 1989. He was one of the great figures in the history of algebraic topology, and one of the most fascinating personalities in twentieth-century mathematics. The next two articles present a portrait of Frank Adams. What follows is the text of the Memorial Address for Professor Adams delivered by J. Peter May in Trinity College Chapel, Cambridge, on 29 April 1989. The Memorial Address is followed by an article, also written by J. Peter May, discussing the life and mathematics of Frank Adams.

Frank Adams was a superb mathematician, a devoted family man, and a kind and gentle friend. He was a man of contradictions: a shy man who could and did dominate many around him; an immensely erudite man who delighted in the lowest puns and doggerel; a man of strong opinions whose view of the world's antics was tinged with a bemused and wry tolerance. His approach to mathematics was marked by inexhaustible intensity and energy, excruciating competitiveness, insatiable curiosity, meticulous craftsmanship, vivid imagination, lively wit, deep seriousness, and marvelous eloquence of expression. But what was perhaps most remarkable about him was the way in which these qualities were wholly untempered in his approach to even the most mundane aspects of life. He was all of a piece. It is impossible to convey any real sense of Adams's mathematical achievement to a lay audience. He was unquestionably the world's leading algebraic topologist. He dominated that field, originating many of its most fruitful directions. In particular, he took the embryonic area of stable homotopy theory and singlehandedly developed it into one of the major branches of the subject. He considered himself to be, in his own 40

words, a "true English problem-solver," and his solutions of the "Hopf-invariant-one problem" and the "vector-fields problem" were great events in the history of topology. He was never concerned with either theory or calculation for its o w n sake. He regarded those as simply means to an end. Nevertheless, he left a large body of new theory of lasting importance, including such contributions as the construction of the Adams spectral sequence and the introduction of the Adams operations, while his work was marked by extraordinarily intricate and insightful algebraic calculation. He had a compulsion to learn everything there was to know about algebraic topology, and he was never happy with any new development until he understood it in complete detail. Beyond his original contributions, he left quite a few extremely valuable expository works based on the contributions of others.

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1 9 1990 Springer-Verlag New York

For some t w e n t y - f i v e years, Frank A d a m s was m y m e n t o r , m y closest m a t h e m a t i c a l colleague, a n d m y dearest personal friend. We e n g a g e d in a v o l u m i n o u s c o r r e s p o n d e n c e , i n t e r r u p t e d only b y o u r visits back a n d forth 9 F r a n k w a s also a g o o d friend to m y family, a n d his n o n - m a t h e m a t i c a l letters w e r e u s u a l l y add r e s s e d to m y wife. P e r h a p s I can best give a picture of the m a n b y q u o t i n g f r o m his letters, letting h i m s p e a k for himself. A recurring t h e m e in his letters w a s the nature of m a t h e m a t i c a l exposition. H e rewrote his o w n p a p e r s m a n y times over. I once a s k e d for a c o p y of s o m e w o r k in progress, a n d his delightful r e s p o n s e w e n t as follows: It is perfectly true that when I last wrote to you I had drafts of sections one and three which I was willing to let people see. Today I still have the same pieces of paper, but like Mr. Brown, I discern the Capability of Improvement. The chief rogue (a definition, needless to say) has been marched off to the condemned cell, where he lodges till I determine whether his rival is likely to serve the crown more usefully; he took with him a handful of perfectly valid theorems (humming sadly "we shall not all die, but we shall all be changed"). H e expected others to a d h e r e to the s a m e high stand a r d s he set himself, a n d he h a d little tolerance for s h o d d y w o r k m a n s h i p . H e stirred u p h o r n e t s ' nests of c o n t r o v e r s y b y his public r e m o n s t r a t i o n s o n the subject, b u t his c o m m e n t s in private c o r r e s p o n d e n c e w e r e m o r e eloquent. S h o r n of irrelevant context, one of his perorations on the subject w e n t as follows. The matter in h a n d was a cryptic p a p e r I was refereeing. 9 . . So perhaps it's best if I stick to stating a few abstract principles, and reserve the question of whether or not they have any reference to the matter in hand. (A) Mathematicians who wish for the gratitude of the mathematical public must write so that the mathematical public does not have too much difficulty in making out what they mean. And here the word "public" includes struggling graduate students, let alone people like you who have spent years thinking about the subject. I well remember one time when Henry Whitehead knew that he had Peter Hilton as a referee9 His reaction was: Peter has missed the point, but Peter is an intelligent man; therefore, I must put the point more clearly9 (B) Mathematics in general is dependent on technical details9 It may happen, though, that one likes the end without liking the means; in other words, one would wish to rely on certain technical details but finds them distasteful9 I observe maybe four approaches. (i) The first follows M a c b e t h . . . "I am so fetlock deep in gore,/Return were just as tedious as go o ' e r . . . " and plunges ahead with the first set of details that come to mind. (ii) The second pauses to consider the technical details and examine how they can be handled so as to minimise the nuisance9 This is par for the course9 (iii) The third pauses to consider whether a change of approach or strategy may lead to reliance on a different set of technical details which may be less distasteful9 Alas, Newton's Fourth Law [the law of maximum unhappiness] . . . .

J. Frank

Adams

(iv) The fourth plan is explain the ends and leave the details out; that is, the author omits to explain what is involved. As a general principle, I reject plan (iv) entirely. I did promise to reserve judgment on the applicability of these principles9 The suspicion I would wish to test, though, is that the author's defence of his theorems accuses his writing of (iv). In his v e r y next letter, he told m e a b o u t a p a p e r he h a d just refereed. Still, let me tell you of a paper that I got to referee the other day. My thoughts went much as follows. "This has a pleasantly familiar drift; I did this in 1955/56 and never published it. Well, one can't punish the author for the fact that I never published it; if it were one-third the length it might be quite acceptable . . . . Hold on! Not only did I solve this problem in 1955/56 and never publish it, but I got a different answer . . . . " F r a n k t o o k the refereeing of p a p e r s v e r y seriously, a n d his inability not to r e d o a n d i m p r o v e the m a t h e matics that he e n c o u n t e r e d occasionally led h i m out into the o p e n as a c o a u t h o r of the revised versions. H e w a s a fine collaborator. While he preferred to hold p e n in h a n d himself, he w a s s c r u p u l o u s l y careful to take the w i s h e s of his coauthors into account. H e w a s also v e r y s y m p a t h e t i c to the n e e d s of his students, a n d he THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

41

could see objectively h o w they might well find him difficult to w o r k with. I vividly r e m e m b e r one occasion w h e n he asked m e to talk to one of his students, telling me that " e v e r y time he c o m e s to see m e he shakes.'" In a similar vein, Frank was ruefully aware that he was not particularly effective in matters of politics, academic or otherwise. H e engaged in acts of political protest w h e n his feelings were strongly engaged. A recent occasion was the 1986 U.S. attack o n Libya: Over Libya, President Reagan and Mrs. Thatcher succeeded in making Airstrip One, your unsinkable aircraftcarrier, look like a stooge to a bully. The Sunday before it happened, Grace and I were engaged in handing in petitions against it at our local U.S. base, and I was trying to explain to a heavily-armed U.S. guard that I was a friend of the U.S.A. from way back, and I just wanted to see her acting in her own best interests. Still, such activity w e n t a little against his grain. As he wrote in 1987, "It is one of the defects in m y character that I am not as politically active as Grace thinks I o u g h t to b e . " H e w a s far f r o m d o c t r i n a i r e , b u t s o m e h o w he was quite capable of e m p a t h i z i n g with the views of others, while at the same time deprecating their inability to see the obvious correctness of his o w n more logical position. He h a d a global out~ look, and he was v e r y keen on b r o a d e n i n g contacts a m o n g mathematicians in different countries. The following quote concerns the Intemational Congress of Mathematicians held in Warsaw in 1983: The International Congress was not a bad do. It was less good than it might have been because of the absence of a number of Westem mathematicians, including a number of invited speakers who had accepted the invitation to speak and done nothing to inform the organisers that they weren't coming. The Poles did not like this very much; "what is the use of doing something as a protest if you don't tell people you are protesting?" A number of speakers dedicated their talks to Polish mathematicians (of course, ones who had been or were in jail); this went down much better . . . . Later in the same letter, Frank described his indulgence in one of his favorite vices, a c o m p u l s i o n to climb to the top of the highest thing in sight, be it building or m o u n t a i n . I also explored the Palace of Science and Industry, where the Congress was held . . . . The ordinary observationplatform is on floor 31 and the ordinary lifts go up to floor 33. After that there is a lift, which I presume is intended for service staff only, going from floor 33 to floor 45. As I was travelling exclusively by staircase, I was able to master the geography pretty well, and I didn't mind when the lift stopped and there was only a staircase. I found some much better and more congenial observation points higher in the tower, where the pigeons were surprised to see me. The top of the construct is a vertical tubular steel spike9 As I had already disregarded all the notices in Polish which, I strongly suspect, forbade all unauthorised persons to go further, I went up it as far as there was a ladder9 42

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Frank loved rock-climbing. H e f o u n d the d a n g e r exhilarating, and he was v e r y p r o u d of his physical proficiency. The last trips he w r o t e about were in 1987; one included a "splendid climb" of Jones' Direct with his son Adrian. Frank's family and mine figured prominently t h r o u g h o u t our correspondence. In 1986, at its 600th anniversary celebration, the University of Heidelberg conferred an h o n o r a r y doctorate on him. He w r o t e of Grace o n that occasion: She did enjoy being a tourist in Heidelberg: going around the castle, down the high street of the old town, walking on the Philosophenwegthrough the woods on the other side of the river, and having snacks in nice caf6s or at tables outside in the square9 And for the ceremony, they got her to walk beside me in the procession and gave her a bouquet9 9

.

.

Frank spoke in Latin at the c e r e m o n y since, as he wrote, h e was unwilling to reinforce received ideas a b o u t Anglo-Saxon insularity b y speaking English, a n d h e felt that his G e r m a n w o u l d embarrass all concerned. Characteristically, h e obtained coaching bef o r e h a n d o n the p r o p e r G e r m a n p r o n u n c i a t i o n of Latin. In fact, h e was m e t i c u l o u s l y t h o r o u g h in his p r e p a r a t i o n of all talks he gave. H e usually w r o t e t h e m out fully in advance, including the jokes. O u r children figured especially prominently in o u r correspondence. My sons v i e w e d Frank as a friend, a n d h e t a u g h t t h e m and m e his favorite game, GO. T h e y once played a game, transcribed the moves, a n d sent the list of moves to Frank 9 He s o m e h o w f o u n d the time to write out 28 single-spaced pages of detailed c o m m e n t a r y and instruction to send back to them. H e and I confided in each o t h e r about the difficulty of dealing with adolescent children. He once described some tit for tat with his d a u g h t e r Alice, at age sixteen, e n d i n g b y writing " H o n o r appears to be satisfied for the time being." It was v e r y clear that he respected a n d a d m i r e d h e r spirit. In 1983, h e w r o t e of his pleasure at attending her g r a d u a t i o n from the University of Edinburgh, w h e r e she was given her M.A. H e also t o o k p l e a s u r e in A d r i a n ' s r a p i d a d v a n c e m e n t t h r o u g h the ranks of his civil engineering firm, a n d he r e p o r t e d with considerable satisfaction w h e n Adrian was g r a n t e d M e m b e r s h i p in the Institute of Civil Engineers, his final professional qualification, in 1987. Frank h a d great love and e m p a t h y for y o u n g e r children. H e gave the following description of a d a y ' s outing with his y o u n g e r d a u g h t e r s in the spring of 1976. Last time I took Lucy and Katy out to Cambridge Lucy insisted that we begin by going to the indoor swimmingpool by Parker's Piece, which turns out to be quite good. Lunch in Vigani's room, of course; they were so full when it came to the trifle that we had to take half a bowl home so as not to waste it, and return the bowl later9 Then to the FitzwiUiam Museum (Katy is dead keen on the Egyptian rooms), punting on the Backs, and on to the top of the

Wren Library to admire the view9 I've learnt a lot of odd comers of the College where a Fellow can take nine or ten year olds to please them. Then Lucy & Katy had tea & toast in the Parlour (which one may do if no Fellow there objects, and they seldom do). Frank loved Trinity College not just as a great a n d v e n e r a b l e a c a d e m i c institution b u t also as a s e c o n d h o m e a n d a v e r y special place to entertain those he f o u n d particularly deserving, including the administrative assistant of DPMMS, his surgeon, his m o s t fav o r e d m a t h e m a t i c a l visitors, and m o s t especially his children. Lucy is coming as my guest to the Twelfth Night Dinner in Trinity9 To quote from the rules "it is understood that a Fellow may bring a young member of his family," and whatever went for sons before the Statutes were amended now goes for daughters too. Lucy came in January 1978 and Katy in January 1979, so the pattern seems to be clear for a few years. A n y w a y , Twelfth Night is Lucy's birthday. His letters refer to m a n y of the feasts a n d other traditional occasions at Trinity. While he e n j o y e d t h e m thoroughly, he also s a w their h u m o r o u s side, their air of quaint a n a c h r o n i s m . This came out best in a r e m a r k a b o u t a C o m m e m o r a t i o n service held on J u n e 8, 1985, at the College next door. Today the fellows of St. John's have a Commemoration Service. The sort of Commemoration Service that you have once a year can of course be safely skipped by those who dislike rituals, but this is different. Four hundred and fifty years ago, to the day, their co-founder was beheaded. In fact, F r a n k h a d a d e e p a n d y e t s o m e h o w detached love of e v e r y t h i n g English. H e l o v e d the countryside, a n d he w r o t e with pleasure of his vacations w i t h G r a c e in the L a k e District, Norfolk, C o r n w a l l , Wales, a n d Yorkshire. H e v e r y m u c h e n j o y e d hiking a n d s w i m m i n g w i t h her. H e especially l o v e d their h o m e in H e m i n g f o r d Grey. H e d e s i g n e d a n d built a lovely semicircular perennial garden behind the house. To one side of it he m a d e a r o u n d p o o l for papyrus, a b o u t w h i c h h e once wrote: The other day Grace observed that there was something new in the pond which I made in our garden; a toad. Katy was overjoyed that it had chosen to honour our pond with its presence, pronounced it a splendid specimen, and took her dinner outside to eat by the pond while she continued to admire it. First things first, you understand; you get a dinner every day, but toads with copper-coloured eyes . . . . Frank w a s a m a r v e l o u s craftsman. H e delighted in intricate c a r p e n t r y a n d in enameling. H e r e are before a n d after quotes a b o u t a 1975 project. In my spare time I am supposed to be making Grace a jewelry box, for her birthday . . . . It's to be in Japanese oak, replete with concealed dowelled joints, brass hinges and locks, trays in cedar, etc. Currently I am doing the carcase in duplicate so that if I make some frightful mistake with one I can carry on with the other.

The jewelry box for Grace turned out OK, except that when it was brought into the centrally heated house the lid decided that if nasty people were going to evaporate off its water content it would prefer to be ever so slightly concave; this entailed taking it outside again, removing the lid and planing the bit which was supposed to fit the rest of the box till it did fit the rest of the box again. The second jewelry box also turned out OK and caused great surprise when it was brought out as a Christmas present; it matches the first very handsomely. I will give one last excerpt, f r o m a long a n d chatty letter of S e p t e m b e r 1983. It d e s c r i b e s daily life at 7 W e s t m e a r e after the vacation in Cornwall a n d before Lucy a n d Katy w e n t off to school. As for Grace, she told our daughters what to do and proceeded to get the house the way she likes it. I think she evicted a lot of spiders. Grace believes in the conspiracy theory of spiders: she thinks that at this time of year they all go round telling each other, let's creep into 7 Westmeare, their central heating is the best. She is determined that instead a very few spiders should tell their friends how lucky they were to escape from that terrible ogre at 7 Westmeare who destroys all webs and most spiders . . . . In the evenings I did a bit more enamelling. Apprentice enamellers should write out five times: Do Not Be Too Ambitious9 My project was for small stud earrings, based on the creatures which we call ladybirds and you (more logically) call ladybugs . . . . At first my intentions were 9

.

.

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

43

good. Since two-spot ladybugs exist in nature, my customers would have to be content with two spots per bug. Also the creatures would be a bit larger than life-size; lifesize ladybugs are (a) insufficiently spectacular and (b) fiddlesome . . . . I went out and found some ladybugs in our garden. I couldn't find any two-spot ones. The front end of a ladybug is more complicated than you might think; I had to plan on stylising it in the hope that my customers hadn't looked at a live ladybug carefully. . . . The metal work came down to a small oval base and two cloison wires making space for two red wing-covers and one black "head." The theory is that you set the cloison wires in a layer of glass which has a higher melting-point than the red and black glasses you will use later. As usual, theory is oversimplified. To begin with, glasses don't have a meltingpoint; their viscosity changes gradually over a range of temperature . . . . The smaller cloison wire turned out to be particularly temperamental. Until you get enough glass on both sides, the sensitivity of such a cloison wire to gravity waves must exceed that of the conventional experimental dispositions; the only reason it is no use in that role is that it falls around for other reasons too, beginning with Brownian motion. It also responds to psychic influences and emotional vibrations; and it is deeply sensitive to the groans of spiders, lamenting the ruin of their handiwork. It is quite unmoved by the groans of human beings similarly afflicted. The passage d o e s n ' t e n d there. Frank w e n t on to describe the difficulty of making five spots per ladybug without smearing the spots. It is entirely in character that the lack of t w o - s p o t t e d l a d y b u g s in his garden had left him dissatisfied with his original good intentions. N o r was he satisfied with the final result: On considering the results, I thought, perhaps I should have left my lady-bugs unspotted. But that would not do; 44

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

a no-spot ladybug is no ladybug at all. Perhaps if I had made the spots with brown glass instead of black, then the result might have looked less like coleoptera that have been cohabiting in a coal-hole. Oh, well . . . . imperfections which distress the artificer may seem much less important to the customers. In other words, your daughters will say that your ladybugs are sweet (or in American, cute). Frank's a p p r o a c h to the p r o b l e m of m a k i n g cloisonn6 earrings displays m a n y of the same features as his a p p r o a c h to problems in mathematics. The intensity, curiosity, craftsmanship, attention to detail, selfcritical perfectionism, imagination, and wit are all there. Frank A d a m s was the m o s t remarkable and admirable p e r s o n I ever knew. I feel privileged to h a v e b e e n his friend and am diminished b y his death. We h a d m a n y m a r v e l o u s t i m e s t o g e t h e r . We c l i m b e d t h r o u g h a hailstorm to the top of a mountain in Scotland; w e climbed on h a n d s a n d knees over s n o w and ice to the top of a m o u n t a i n in Colorado; we p u s h e d a stalled r e n t e d car along a flooded dirt road in a torrential d o w n p o u r in Mexico; w e climbed a little Japanese m o u n t a i n at d u s k and t h e n scrambled d o w n in the dark of night. I shall always treasure these memories and many, many more. We also proved some t h e o r e m s t o g e t h e r , a n d g e t t i n g to a t h e o r e m w i t h Frank was very m u c h the same kind of exhilarating experience as getting to the top of a mountain. There will n e v e r be another like him.

Department of Mathematics University of Chicago Chicago, IL 60637 USA

Reminiscences on the Life and Mathematics of J. Frank A d a m s J. Peter May

Frank Adams was both my closest personal friend and my closest mathematical friend. I will say a little about his mathematical work here, but a fuller appreciation is being prepared for publication elsewhere. I will try to convey something of his style and of his feelings about mathematics, again letting him speak in his own words. Adams was knowledgeable about many other fields, but topology was his love. While all of his work was at a very high level, two groups of early papers stand out particularly: On the structure and applications of the Steenrod algebra (June 1957) On the non-existence of elements of Hopf invariant one (April 1958) Vector fields on spheres (October 1961) On the groups J(X)--I (May, 1963) II (September 1963) III (November 1963) IV (July 1965) The dates given are the dates of submission; actually, according to J(X)--IV, much of the material in the J(X) papers dates from the years 1960-1961. The first two papers above were concerned with the Hopf-invariant-one problem. One way of motivating the problem is to ask the possible dimensions n of a real division algebra D. Given D, we obtain a map f from the unit spher e S 2n- 1 C D x D to the one-point compactification S n of D by sending (x,y) to x - ly if x 0 and to the point at infinity if x = 0. If we form the two-cell complex X = S n Ufe 2", we find that its cohomology is Z in dimensions n and 2n and that the cup square of the generator in dimension n is a generator in dimension 2n. We say that f has Hopf invariant one. The homotopical problem asks what dimensions n support a map of spheres f: S 2n-1 ~ S n of Hopf invariant one. In view of the real, complex, quaternion, and Cayley numbers, n = 1, 2, 4, and 8 are possible. Adams proved that these are the only possibilities. The first paper I mentioned can be v i e w e d as a failed attempt to prove this result. All it obtained on the problem was that, if n > 4, one couldn't have

Hopf-invariant-one maps for both n and 2n. However, since the paper introduced what is n o w called the Adams spectral sequence, it can't be written off as a total loss. In fact, the Adams spectral sequence is the most important theoretical tool in stable h o m o t o p y theory, and its introduction marked the real starting point of this fundamental branch of algebraic topology. The Adams spectral sequence converges from E2 = ExtA(H*(X; Zp), Zp) to the p-primary component of the stable homotopy groups of the space X, where A denotes the Steenrod algebra of stable operations in mod p cohomology. The connection with the Hopf-invariant-one problem is that the mod 2 cup square is a Steenrod operation, and this allows a translation of the problem into a stable one. Certain differentials in the Adams spectral sequence give decompositions of Steenrod operations into composites of secondary operations. In a two-cell complex X, there are no intermediate dimensions in the rood 2 cohomology, hence such a decomposition of the relevant Steenrod operation implies that the cup square of the integral generator in dimension n is zero mod 2. In the second paper above, the Hopf-invariant-one problem was solved by means of an explicit decomposition of all of the relevant mod 2 Steenrod operations in terms of secondary operations. My o w n 1964 doctoral thesis was motivated by the Adams spectral sequence, specifically by the following passage from Adams's 1960 Berkeley lecture notes: The groups E2 are recursively computable up to any given dimension; what is left to one's intelligence is finding the differentials in the spectral sequence, and the group extensions at the end of it. This account would be perfectly satisfying to a mathematical logician: an algorithm is given for computing E2; none is given for computing dr. The practical mathematician, however, is forced to admit that the intelligence of mathematicians is an asset at least as reliable as their willingness to do large amounts of tedious mechanical work. The history of the subject shows, in fact, that whenever a chance has arisen to show that a differential dr is non-zero, the experts have fallen on it with shouts of joy--"Here is an interesting phenomenon! Here is a chance to do some

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1 9 1990 Springer-Verlag New York

45

nice, clean research!"--and they have solved the problem in short order. On the other hand, the calculation of Ext groups is necessary not only for this spectral sequence, but also for the study of cohomology operations of the nth kind: each such group can be calculated by a large amount of tedious mechanical work: but the process finds few people willing to take it on. That was what I took on in my thesis. But my calculations in fact forced some calculations of differentials, and those calculations did not all agree with the ones tabulated by Adams in his cited lecture notes. I wrote him on February 23, 1964, pointing out his mistakes. I hasten to add that mistakes of any sort were most unusual in Frank's work. That marked the beginning of our friendship and the start of a correspondence which averaged one or two letters a month in each direction over the last twenty-five years, interrupted only by his frequent visits to Chicago and my visits to Cambridge. 46

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Frank was the most competitive man I have ever met. Let me give one example. In the spring of 1971 my younger son was 21/2years old, the age of language acquisition and thus of most accurate memory. One day Frank and he were playing the card game Concentration on our living room floor. My wife said something to Frank, and he snapped back "Be quiet, I'm concentrating!" In fact, by then he had mellowed. He was far more intense in earlier years. In his Spring 1960 Berkeley notes, he described some work in progress on the vector-fields-on-spheres problem, which asks for the m a x i m u m number of linearly i n d e p e n d e n t vector fields on S" for each n. Hirosi Toda, in Japan, was also working on the problem and had some partial results. With this spur, Adams had polished off the problem completely by October 1960. Moreover, his methods were totally different from those he had been working on in the spring. Then, he was thinking in terms of

ordinary cohomology, higher order cohomology operations, and differentials in the Adams spectral sequence. As he wrote in the published account, "The author's work on this topic may be left in decent obscurity, like the bottom nine-tenths of an iceberg." In fact, his solution of the problem was obtained by the introduction and exploitation of what are now called the Adams operations in topological K-theory K(X). Recall that K(X) is the Grothendieck ring determined by the semi-ring of isomorphism classes of vector bundles over X. The vector-fields problem is closely related to the study of the groups J(X). These are quotients of the groups K(X) obtained by classifying vector bundles in terms of fiber homotopy equivalence rather than bundle equivalence. The first of the J(X) papers contained a remarkable c o n j e c t u r e - - n o w called the Adams conjecture--and proved it in special cases. It gave an upper bound for J(X) in terms of the Adams operations. That is, it asserted that certain elements of

K(X) specified in terms of Adams operations were always in the kernel of the natural homomorphism K(X) ~ J(X). The remaining J(X) papers made clear that the Adams conjecture was of fundamental importance in algebraic topology. The Adams conjecture was later proven by Sullivan and Quillen, and their proofs led to a cornucopia of new mathematics. Sullivan's proof led him to the now ubiquitously used theory of localization and completion of topological spaces. QuiUen's proof led him inexorably to the now standard definition of the higher algebraic K-groups of rings. Rather than say more about Adams's mathematics, I will let him give an example of his style of exposition. In going over his papers in England, I found his lecture notes on the definitive proof, using the Adams operations in K-theory, of the non-existence of elements of Hopf invariant one. This proof is due to Adams and Atiyah. The lecture notes assume a little THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

47

knowledge of the relationship b e t w e e n ordinary cohomology and K-theory, as given b y the Atiyah-Hirzebruch spectral sequence, but the lecture was clearly i n t e n d e d to be accessible to graduate students. It m a y be objected that the algebra at the end of the proof was left to the reader 9 That reflects Adams's considered position o n the relation b e t w e e n topology and algebra in his work. As he once wrote me:

ceding Memorial Address. His letters were always a delight, although his h a n d w r i t i n g required careful deciphering. Imagine the pleasure of receiving the following piece of doggerel in the mail. It concerns ano t h e r aspect of Frank's role in policing the topological literature.

I am usually interested in writing papers in which one reduces topological problems to algebra9 From that point of view, one tends to accept algebra as a subject under our control; one writes algebra only as required9 In fact, A d a m s always aimed at geodesic solutions to problems, d e v e l o p i n g only such t h e o r y and doing only such calculations as were essential to the main line of argument. I myself am more Bourbakian, and his attitude is amusingly c o n v e y e d by the following q u o t e from a letter he w r o t e me in 1984, w h e n we were collaborating o n a paper: It is not like you, Peter, to miss the correct level of generality. Riddle: does JFA ever miss the correct level of generality? Answer: if his wife and daughters stayed away he would miss them, but as for the correct level of generality, he hardly seems to feel the lack of it. Frank had v e r y forceful opinions on the writing of mathematics, a n d he took it u p o n himself to try to keep the literature honest 9 This came out particularly in Section 6 of a crusty p a p e r in the proceedings of the 1982 Aarhus conference on algebraic topology. It included the following quotes. I must admit that the attitude expressed is one that I share. In fact, some of the examples of s l o p p y mathematics that led to the diatribe were supplied b y me in correspondence, in an area that I k n e w well and that Frank was learning. If you catch anyone writing a sentence like that, make a note that you do not trust his critical faculties9 Linguistically, notation with very strong associations, which are totally different from its declared logical meaning, is misleading notation. I suggest we should use misleading notation only when we wish to mislead, for example, on April 1st. Since mathematicians do not normally intend to deceive, misleading notation is especially dangerous to authors capable of self-deception. 9. . I am moved to preach a sermon on this subject9 So, if such of my friends as have favorite pieces of minor sloppiness will please put them down and walk quietly away from them, I will begin. I earnestly desire that people should not copy out of previous papers without pausing to ask whether the passages to be copied make sense. And when we write a sentence which implies that one checks A and B, then we shall take scrap paper and check A and B--from the deftnltions. And for those of us who have the care of graduate students, I recommend that we give them critical faculties first and their PhD's afterwards. Here ends my sermon9 He wrote e v e n m o r e effectively about such matters in private c o r r e s p o n d e n c e as can be seen in the pre48

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Department of Mathematics University of Chicago Chicago, IL 60637 USA

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 cafd where the famous conjecture was made, the desk where the

famous initials are scratched, birthplaces, houses, memorials. Does your hometown have a mathematical tourist attraction? Have you encountered a mathematical sight on your travels? If so, we invite you to submit to this column a picture, a description of its mathematical significance, and either a map or directions so that others may follow in your tracks. Please send all submissions to the European Editor, Ian Stewart.

Euler's Tomb Frank den Hollander Leonhard Euler (1707-1783) spent the first twenty years of his life in his native country, Switzerland. In 1727 he was called to St. Petersburg, at the instigation of Daniel and Nicolaus Bernoulli, to become a member of the Academy that had been founded two years earlier by Catherine I, the wife of Peter the Great. Because the social and political situation in Russia rapidly declined, Euler decided to move to Berlin in 1740, accepting the invitation of Frederick the Great to join the Berlin Academy. Even while in Berlin he received part of his salary from Russia. Euler never got along well with Frederick, and in 1766 he once again packed his bags and moved back to St. Petersburg. This time the invitation came from Catherine the Great, the patron of intellectual and artistic life in Russia during the second half of the eighteenth century. In the last years of his life Euler enjoyed a position of high esteem in Russian society. He was an international celebrity and Catherine the Great took a close personal interest in his well-being. Euler is buried in the cemetery of the Alexander Nevsky Monastery, which is located in the eastern part of central Leningrad, on the border of the Neva river. There is a metro stop close by. When you enter the monastery from Alexander Nevsky Square, you will find two small cemeteries to the left and right. Euler's tomb is on the far side of the left cemetery. On it is written: LEONHARDO EULERO ACADEMIA PETROPOLITANA MDCCXXVII NAT. BASILEAE IV/XV APRIL MDCCVII MORT PETROPOLI VII/XVIII SEPTEMBER MDCCLXXXIII * Column Editor's address: Mathematics Institute, University of Warwick, Coventry CV4 7AL England. ['HE MATHEMATICAL INTELLIGENCER VOL, 12, NO. 1 9 1990 Springer-Verlag New York

The first dates refer to the Russian calendar, which at that time was eleven days behind the Gregorian calendar in use elsewhere. The monastery is presently being restored in bright red and white colours. While you are there, do not miss going to the other cemetery as well, w h e r e y o u will find y o u r s e l f s t a n d i n g amongst the tombs of some of Russia's greatest musical talents: Balakirev, Borodin, Glasunov, Mussorgsky, Rimsky-Korsakov, Rubinstein, and Tchaikovsky. Department of Mathematics Delft University of Technology Delft, The Netherlands

Euler's Tomb

Below: Entrance to the Alexander Nevsky Monastery

Reminiscences of a Topologist* Ioan James

In my undergraduate days (1947-1951) the Oxford mathematics syllabus had not changed greatly from that of the thirties. G. H. Hardy, of course, had done much to break d o w n the insularity of British mathematics, and as a result Hardy's former research students, of w h o m E. C. Titchmarsh was the foremost member, were influential. I was fortunate in that my tutor, Haslam-Jones, was one of these. He took pride in being able to teach the whole of the undergraduate course expertly and I owe him a great deal. At the beginning of the third and last year of the course I fell seriously ill and had to take a year off. I had been on the point of approaching Titchmarsh to see if he would accept me as a graduate student. However, while convalescing from my illness I had the opportunity to read mathematics much more widely than the Oxford course provided for. Gradually I came to feel that rather than study eigenfunctions under Titchmarsh I might do better to study topology under J. H. C. (Henry) Whitehead. Whitehead had a rather unusual career. At Eton he had not distinguished himself academically and the College was quite surprised when he w o n a Balliol ex-

hibition, in mathematics. Although he did well at Oxford he decided, when he graduated, not to stay on but to begin a career in the City of London as a stockbroker's clerk. After a few years, however, he changed his mind, returned to Balliol briefly, and before long was on his way to Princeton, as one of the first Commonwealth (now Harkness) fellows, to study under Oswald Veblen. The Cambridge Tract Foundations of Differential Geometry resulted from this. In those days the leading topologist in Princeton was James Alexander; Whitehead became a member of this circle,

* Text of an address given on 27 June 1988 at the fifth Oxford Topology Symposium held at the Palazzone, CoRona, Italy. The two portraits of H e n r y W h i t e h e a d were taken by Professor A. Kosinski and are reproduced with his kind permission. 50 THE MATHEMATICALINTELLIGENCERVOL. 12, NO. I 9 1990Springer-VerlagNew York

Hardy leading out his cricket team. From left to right: G. H. Hardy, H. O. Newboult (?), W. L. Ferrar, U. S. Haslam-Jones (?), E. C. Titchmarsh, ?, E. H. Linfoot, L. S. Bosanquet.

which included people like Samuel Eilenberg and Solomon Lefschetz. While he left for America a geometer he returned a topologist, and set out to revitalise Oxford mathematics by promoting the study of topology. Before World War II Whitehead had just one research student, Graham Higman. Whitehead's career was interrupted by the war during which he served, along with various other well-known mathematicians --notably Alan T u r i n g - - a t the celebrated defence research centre at Bletchley. He was always proud of his work there although secrecy regulations prevented him saying m u c h a b o u t it. One of his juniors at Bletchley was a young man named Peter Hilton, who became a founding member of the group of research students Whitehead gathered around him after the war. I was fortunate to join this lively and distinguished group, which included people like Michael Barratt, Wilfred Cockroft, and Victor Gugenheim, as well as Hilton. Of these I was probably closest to Michael Barratt. Being reluctant to trouble the great man himself about my struggles to understand what was going on, I troubled Michael instead and will always be grateful to him for the help he gave me. It may be difficult for the present generation to appreciate how homotopy theory stood at that stage. Of course, research had been rather interrupted by the war, and there were many questions outstanding. For

example, it was not known that the homotopy groups of spheres were finitely generated. At the last International Congress of Mathematicians before the war Lev Pontrjagin had announced that ~s(S3) = 0. The argument he had in mind was essentially what we now know as the Pontrjagin-Thom construction. This involves framed manifolds, of course, in this case 2manifolds. Unfortunately, Pontrjagin had somehow overlooked the torus and so, as George Whitehead showed, his announcement was wrong and ~5(S3) is non-trivial, in fact Z2. The next real difficulty was ~6 ($3)9 This group was known to be of order 12, either Z 3 + Z4 or Z3 + Z 2 + Z 2. Most of the Whitehead students had a go at trying to settle this question. In the end it was Barratt and George Paechter who got the right idea, essentially a special case of what we now refer to as Toda brackets. I well remember Barratt's lengthy arguments on the subject with a sceptical Henry Whitehead. In those days there were few books relevant to graduate studies in homotopy theory. There was Alexandroff and Hopf, also Seifert and Threlfall. There was Lefschetz's Introduction and his Colloquium volume. That was about all. The first new textbook to appear after the war was Steenrod's Topology of Fibre Bundles. That book was an enormous help to me and I practically knew it by heart. Naturally a "first organization" of a new branch of mathematics stimulates a lot of furTHE MATHEMATICAL INTELLIGENCER VOL. I2, NO. 1, 1990 5 1

ther research and tends to make itself obsolete after a time, but Steenrod's book remains r e c o m m e n d e d reading to this day. My first independent piece of research arose from that book. Steenrod gives a classification of spherebundles over spheres, as fibre bundles, and I tried to classify them by homotopy type instead. Classification by fibre homotopy type is quite easy, of course, but the classification by ordinary homotopy type was just the sort of project I needed in order to get started. The outcome was two joint papers by Whitehead and myself. The first, on the case where there exists a crosssection, was largely written by me, while H e n r y Whitehead largely wrote the second. In fact there was a difficulty for (n-1)-sphere bundles over S n (n = 4 or 8), which we were unable to resolve. Later I was able to settle n = 4, with some hints from Barratt, who has also settled the case n = 8 in work which, alas, remains unpublished. Topology at Oxford has always benefited greatly from academic visitors. Some of these come to lecture at the seminar Whitehead established in 1946 and which always met, in term time, on Mondays at 5 (except in the cricket season when it met after dinner). This seminar is still running and I often regret that we didn't maintain a "visitors book" in which to record the many notable lectures given in the seminar and the people w h o gave them. One I particularly remember is Norman Steenrod's lecture on the cohomology operations now called the Steenrod squares; this led to the well-known note by Steenrod and Whitehead about vector fields on spheres.

52

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

In most years there have generally also been one or two topologists visiting Oxford, and they are often asked if they would like to give a course. I particularly remember Everett Pitcher's course on Morse theory. In this course Pitcher talked about Morse's theorem concerning the space of loops on S n+l. Essentially he showed that this could be approximated, from the homotopy theoretic point of view, by spaces of geodesic segments; thus fl(S n+x) has the homotopy type of a CW-complex S~ of the form S n U e 2n U e3n U . . . . Pitcher himself had shown that the 2n-cell in this complex was attached by the Whitehead square of the generator of ~rn(S n) and had obtained some information about the attachment of the 3n-cell. I tried to improve on this and somehow got the idea that the complex was what I came to call the reduced product s p a c e - essentially the free monoid on S n. I found out later that the same idea had occurred independently to the young Japanese topologist Hiroshi Toda--although it was not suggested to him by Morse theory as far as I know. About that time George Whitehead published his famous A n n a l s paper concerning the exactness of the sequence 9. . ~

"lTr S n ~

Tfr+l Sn+l

~

"lTr+l $ 2 n + 1 ~

"lrr_l Sn ~

. . .

in homotopy groups of spheres. Whitehead showed that exactness holds as far as r = 2n, approximately, and I began to wonder if this could be extended further. Because the reduced product is such a simple gadget I began to play around with it and eventually found a family of maps S~ ~ S~ that seemed to have

interesting properties. However, to exploit their full potential I needed some n e w machinery and fortunately this arrived in the form of Jean-Pierre Serre's thesis Homologie singuli~re des espaces fibrds. The machinery Serre made such effective use of was, of course, the spectral sequence. This was originally developed by Leray, for use in sheaf theory. However, Serre realized that a singular version of the spectral sequence would find many applications in homotopy theory. He forged this new weapon and results came cascading out. For example, he showed the homotopy groups of spheres to be finitely generated. In those years I always went skiing after Christmas, usually to Klosters, where I stayed at a picturesque inn called the Chesa Grischuna. After a hard day on the slopes I found it quite refreshing and certainly stimulating to study Serre's beautiful work. And with it I was able to establish that the sequence of George Whitehead had exactness properties far beyond what I had ever conjectured. In fact, the sequence is exact without limit for odd values of n and the same is true for even n if odd torsion is disregarded. Although Serre immediately leapt to fame amongst us homotopy theorists, he was not at all well known in the outside world. About this time Whitehead persuaded the Maison Franchise, the French cultural outpost in Oxford, to invite Serre over for a few days. The Director's doubts about inviting a n y o n e so y o u n g were dispelled when, just before his visit, Serre was elected to membership of the Coll~ge de France, a most unusual honour for anyone of his age. The lecture Serre gave at the Monday seminar was full of ideas. He started by talking about %-theory--the subject of his second Annals p a p e r - - b u t he also told us about other ideas he had, for example the expression for ~~(S p + I ~/ Sq+l) as a product of loop-spaces ~SP +1 x f~Sq+1 x f~Sv+q+l x . . . . This was taken up by Hilton who developed it in his well-known paper in the Proceedings of the Cambridge Philosophical Society. Chatting after dinner, I remember, Serre made a conAcademic "family tree" of Henry Whitehead, showing research students he supervised, grandstudents, and so on (in some cases more than one supervisor was involved, but for simplicity only one is shown).

jecture about symmetric products which rather stuck in my mind. It had long been known that the rth symmetric product of S1 had the same homotopy type as SI, and that the rth symmetric product of S2 was homeomorphic to the r-dimensional complex projective space. Serre observed that in the limit, as r ~ % this indicated that the infinite symmetric product of Sn was the Eilenberg-Mac Lane space K(z,n) for n = 1,2 and conjectured that this might be true generally. After I got m y doctorate I applied, with H e n r y Whitehead's encouragement, for one of the Commonwealth Fellowships that he had himself held when visiting the States in Prohibition days. I was fortunate enough to be selected and in 1954 found myself on the Queen Mary bound for N e w York along with a dozen or so other new Commonwealth Fellows. The Fellowship could be held anywhere in the States. I chose Princeton so as to be able to work with Steenrod along with Emery Thomas, w h o m I had gotten to k n o w when he was a Rhodes Scholar at Oxford and w h o was just completing his Ph.D. at Princeton u n d e r Steenrod. Princeton was still the leading place in the States for topology, and probably in the whole world. Although Alexander had retired prematurely, Lefschetz, Ralph Fox, Deane Montgomery, and other luminaries were in their prime, as well as Steenrod. I received a lot of encouragement and continued to develop some of the ideas in my thesis. I am particularly proud of one result I obtained at that time. Hilton had obtained, arising out of his work on the loop-space on a product of spheres, some powerful results about the composition law for homotopy groups. I tried to prove similar results by my o w n methods and found that there appeared to be a discrepancy between Hilton's results and my own. At first I put it down to a difference in sign conventions - - t h e s e had gotten into rather a mess. However, after laboriously working through these it transpired that the apparent discrepancy was genuine and this led to the conclusion that ~rr(Sn), for n odd and all r, contains no elements of order 2". This is best possible since ~r6(S3) contains an element of order 4, as mentioned before. The following year Toda, who had also been working on the homotopy groups of spheres, proved a similar result for odd primes. Recently there has

THE MATHEMATICALINTELLIGENCERVOL. 12, NO. 1, 1990 53

Henry Whitehead at his desk in the old Mathematical Insti-

Norman Steenrod.

tute at Oxford. been a revival of interest in these results and substantial improvements have been obtained. When I got to Princeton I was surprised to learn that Steenrod was going to spend the second half of the year at Berkeley. Accordingly, early in February, Steenrod, Emery Thomas, and I got into Steenrod's Buick and drove off with him to California via Florida, Louisiana, and Texas. In those days the mathematics department at Berkeley was quite small, although very distinguished. You went to Dwinelle Hall, the home of the Arts Departments, and in one corner of the fourth floor, I believe, you would find people like Kelley, Lehmer, and Tarski. Emery and I settled in happily. While I was at Berkeley my thoughts returned to Serre's conjecture about infinite symmetric products. If this was correct, then might it not be true, more generally, that the homotopy groups of the infinite symmetric product of a space were just the homology groups of the original space? This suggested trying to prove that the homotopy groups of the infinite symmetric p r o d u c t satisfied the E i l e n b e r g - S t e e n r o d axioms for homology. And for this one needed to show that the infinite symmetric product transforms cofibrations into fibrations. Although this is true, in a sense, the definition of fibration needs to be modified somewhat. I spent a lot of time that year trying to convince Steenrod that the modification I thought worked actually did so. When I returned to Princeton at the end of that summer I felt sufficiently sure of the truth of the result to announce it at Montgomery's seminar in the Institute. However, at the end of my lecture John Moore told me that Albrecht Dold and Ren6 Thorn had just published an announcement of the same result in the Comptes Rendus. I must say that I felt v e r y d i s a p p o i n t e d . The infinite s y m m e t r i c product, essentially the free abelian monoid, seemed the perfect follow-on for the infinite reduced product, 54

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

essentially the free non-abelian monoid. Perhaps I should have taken a chance and announced the result before I had worked out all the details, but I have never liked to do that sort of thing. Back at Princeton I began, with Montgomery's encouragment, to investigate H-spaces. Here the great conjecture, the proof of which eluded me, was to show that of the spheres only S1, S3, and S7 can be H-spaces. However, amongst other results I was able to show that S" is only a homotopy-commutative Hspace for n = 1, and a homotopy-associative H-space for n = 1 and n = 3. Later Frank Adams established the great conjecture, as we all know. During my two years in the States I made many friends among contemporary and more senior mathematicians. This was particularly true in my second year, at the Institute for Advanced Study, where Marston Morse and Oswald Veblen, alas no longer with us, were very kind, also Deane Montgomery, Hassler Whitney, and many others. Unfortunately, Einstein and von Neumann had passed away by that time, but the legendary Alexander was still in Princeton, living rather in seclusion, and one day Emery Thomas and I went to call on him and hear stories about Princeton in pre-war days. Lefschetz figured prominently in these stories, of course. When I first knew him he was spending part of each year in Mexico, helping to build up the mathematics department at the University of Mexico. As part of this programme, in 1956 he was organising a major topology conference in Mexico City; I was delighted to be invited to attend and give a short talk. I travelled down to Mexico with Ralph, Cynthia, and Robin Fox, spending about a week on the drive which proceeded rather slowly becasue of Ralph's butterfly collecting and Cynthia's bird watching. Mexico was delightful--I spent the whole summer there, partly in Mexico City and partly in Acapulco--and I have re-

Emery Thomas, Michael Barratt, Henry Whitehead, the author, and Peter Hilton at the International Topology Symposium in Mexico City, 1956.

Henry Whitehead at Manor Farm, Noke.

tained the warmest of feelings towards that country and its people. The conference itself was a great occasion. Everybody was there and much good work was done. Alas it was marred, towards the end, by the news of the accidental death of Witold Hurewicz, who fell from the top of a Mayan pyramid when on a visit to Yucatan. On my return to England I was elected to a Junior Research Fellowship at Caius College, Cambridge. This was before the great Cambridge diaspora. Adams was away in the States but Michael Atiyah and Christopher Zeeman were there working as college tutors while David Epstein and Terry Wall had gotten to the part III stage. All of us attended Hodge's seminar and I r e m e m b e r a lively discussion taking place over Milnor's proof of the existence of exotic differential structures on the 7-sphere, one of the sensations of the Mexico conference. I was just getting accustomed to Cambridge life when I heard that a new Readership in Mathematics had been established at Oxford and was invited to apply. When I was offered it I accepted with alacrity, particularly since it would enable me to rejoin Whitehead and work in partnership with him. By now I knew Henry and Barbara Whitehead very well, and they kindly invited me to lodge at Manor Farm, Noke, where they had m o v e d from Charlbury Road. This was a delightful place to live, and I greatly enjoyed life on the farm. There was never a dull moment where the Whiteheads were concerned. One of the great challenges of homotopy theory in those days was the vector-field problem, which is discussed in Steenrod's book on fibre bundles. When I first read about it as a research student I tried to see what could be done in the positive direction. My efforts led me to the 1920s work of Hurwitz and Radon; and I was delighted to find that this work could be adapted to give what I thought were new results about the problem. I took these along to Whitehead--it was

the first thing I had to show him as a research student - - a n d was dashed to hear that Beno Eckmann had been there before me. Returning to the problem some ten years later I started to become interested in Stiefel manifolds, which are central to questions about vector fields. The work I did at that time is collected in my book on the subject. Of course, it was Adams w h o eventually solved the vector-field problem itself, but I enjoyed finding out about the beautiful properties of Stiefel manifolds and made a number of conjectures, some of which have recently been established by Haynes Miller. Adams's solution to the vector-field problem used K-theory, particularly the family of operations he invented for the purpose. Many other applications have since been found for these operations. The immersion problem for real projective spaces has attracted the attention of almost every homotopy theorist at one time or another. My own contribution was to prove a noni m m e r s i o n result for d i m e n s i o n s one less than a power of two, which according to Gitler and Mahowald is best possible. It is a good illustration of the power of K-theory. Perhaps that is a good point at which to stop. Looking back, I have the impression that it was much easier to make an impact on homotopy theory up to 1970, say, than it is nowadays. However, the powerful methods n o w available enable results to be proved that seemed quite out of reach not so very long ago. The architecture of homotopy theory, at any rate, of stable homotopy theory, is beginning to become more apparent, and in this I am particularly proud that one of my most recent research students, Mike Hopkins, has played a leading role.

Mathematics Institute Oxford University Oxford, England OX1 3LB THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. I, 1990 5 5

Steven H. Weintraub* For the general philosophy of this section, see Volume 9, No. 1 (1987). A bullet (e) placed beside a problem indicates a submission without solution; a dagger (t) indicates that it is not new. Contributors to this column who wish an acknowledgment of their contribution should enclose a self-addressed postcard. Contest entries and problem solutions should be received by I May 1990. The winner of contest 90-1 below will be awarded a free subscription to the Math-

ematical Intelligencer.

tained from w by iterating: i) change a I to a 0, if all the terms preceding that 1 are also 1% and ii) delete the first (leftmost) 0. For instance, B(010) = {010, 10, 00, 1, 0, 0} Show that IA(w)l = IB(w)l.

Problems Mathematical genealogy: Contest 90-1 b y the Column Editor Give the thesis advisor ("Doktor-Vater") of each of the following mathematicians: 1. 2. 3. 4. 5. 6.

M. F. Atiyah S. Banach G. Cantor E. Hecke K. Hensel D. Hilbert

7. 8. 9. 10. 11. 12.

A. Hurwitz J. W. Milnor E. Noether C. L. Siegel N. E. Steenrod O. Zariski

Of course, the entry with the most correct names wins. (Ties will be broken by lot. Joint entries are welcome, but readers are on their honor not to consult reference materials.)

Equal Cardinality: Problem 90-2 by Richard M. Stanley (Massachusetts Institute of Technology, USA) Let w be a finite sequence of O's and l's. Let A(w) be the set of sequences that can be obtained from w by iterating the following two operations: i) change a 1 to a 0, and ii) delete the last element of a sequence if it is a 0. For instance, A(010) = {010, 000, 01, 00, 0, 0}. Similarly, let B(w) be the set of sequences that can be ob-

* Column editor's address: D e p a r t m e n t of M a t h e m a t i c s , Louisiana State University, Baton R o u g e LA 70803-4918 USA

56 THE MATHEMATICALINTELLIGENCERVOL. 12, NO. 1 9 1990Springer-VerlagNew York

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

57

Mathematics Is Beautiful* R6zsa P6ter Translated by Leon Harkleroad

Members of the Audience:

book Playing with Infinity1: in it there is much more about the beauty of mathematics than in my address. No doubt, some of you have been thinking right from the outset: how can one call the dull "two times two" beautiful? My aim is to show that mathematics is not dull a n d not " t w o times t w o , " but rather has much in common even with art.

I am here to pass on my belief that mathematics is beautiful. When I began my college education, I still had many doubts about whether I was good enough for mathematics. Then a colleague said the decisive words to me: it is not that I am worthy to occupy myself with mathematics, but rather that mathematics is worthy for one to occupy oneself with. Even now, despite the prizes and professorship I have received since then, I often doubt my own worthiness, but I Abstraction never had a doubt that I could do anything better and more beautiful than to work on mathematics. It is a great misconception that the mathematician But something prevented me from giving free rein mainly calculates. I have picked out mathematicallyto my thoughts on that here. Namely, I have recorded minded students with the following riddle: We have in a book all that I have to say about mathematics from two identical glasses; in one, we pour wine, in the the viewpoint of a non- or not-yet-mathematician, and other, water, to the same height (not quite full). Then the book was also translated into German. Because we take a spoonful of wine from the first glass, put it here in the German Democratic Republic this book is into the glass with the water, and then mix it. Next we a l r e a d y in its t h i r d printing, I m u s t a s s u m e that put a spoonful of this mixture into the wine of the first perhaps even some people in the audience have read glass. Thus, as the end result, some wine goes into the it. So, in my address I intend to eliminate anything water and some water into the wine. Which is more: that occurs in the book; it was not at all easy to find the pure wine that went into the water, or the pure some even loosely connected new thoughts on this water that went into the wine? subject. Besides, I couldn't change anything in my adWhat is essential here is not whether one figures out dress now if n o b o d y in the audience had read the the right answer (there is a little trap here, into which book; in particular, I don't know German well enough m a n y people fall: one thinks, a spoonful of wine goes to improvise. At any rate, I am propagandizing for my into the water, but a mixture, thus not a spoonful of

* This paper is a translation, with excerpting and editing by the Intelligencer, of an address that R6zsa P6ter delivered to high school teachers and students in 1963 in Rostock, German Democratic Republic. The original version was published in Mathematik in der Schule 2 (1964), 81-90.

1 R6zsa P~ter, Das Spiel mit dem Unendlichen, B. G. Teubner Verlagsgesellschaft, Leipzig 1955. [Translator's note: Z. P. Dienes's translation of the book into English, Playing with Infinity, is published by Dover Publications.]

58 THEMATHEMATICALINTELLIGENCERVOL.12, NO. 1 9 1990Springer-VerlagNew York

R6zsa P ter: Recursive Function Theory's Founding Mother Edie Morris* and Leon Harkleroad*S Take a person w h o was a major f o u n d e r of a thriving area of mathematical research. Say that this person wrote, in addition to papers that are still cited 50 years later, the first book in that field. And say that this same person also authored a classic book of mathematical exposition for the general public. N o w say that this person was a woman. You would expect, even if her name were not a household word in the mathematical community at large, that at least she would be frequently mentioned in the literature that details the significant achievements of female mathematicians. But such is not the case. R6zsa P~ter (1905-1977) is the person in question, a person w h o m Stephen Kleene once described as "the leading contributor to the special t h e o r y of recursive functions. ''1 We feel that P~ter's many contributions to mathematics deserve much greater recognition than they have received. P~ter had set out to work in chemistry, but during the course of her studies at Lorand E6tvOs University in Budapest she attended the lectures of Lip6t Fej~r. These talks sparked her mathematical interest, and she changed fields. By the time P~ter graduated in 1927, it was as a would-be seco n d a r y s c h o o l t e a c h e r of m a t h e m a t i c s a n d physics. However, there were quite a few more mathematicians than openpositions in Hungary at that time. P~ter, like many of her colleagues, could not obtain full-time employment and made her living by tutoring and the like. Eighteen years later, in 1945, P~ter finally secured a full-time position, joining the faculty of the Budapest Teachers Training College, w h e r e she remained until the college closed in 1955. She then assumed a full

professorship at Lorand E6tv6s University, a post she held until her retirement in 1975. Just as P~ter had switched from chemistry to mathematics, she also changed fields within mathe m a t i c s - - o r rather, after abandoning one field, she helped found another! Originally, P~ter's research area was number theory. However, some theorems she obtained turned out to be independent rediscoveries of results that had already been proved by Robert Carmichael and L. E. Dickson. This discouraged P~ter so much that she backed away from mathematics altogether, devoting herself to writing p o e t r y m t h r o u g h o u t her life, P ~ e r was also a talented poet and translator of poetry. ~At the beginning of the 1930s, she was brought back into the mathematical fold by L~szl6 Kalm~. Kalm~tr had been a classmate of hers at Lorfind E6tvOs University, a n d t h e y became lifelong friends and colleagues. He told P6ter about Kurt G6del's recent work related to incompleteness. Without knowing how G6del had proved various results in his landmark paper, she was able to devise her own, different proofs. This experience not only restored P~ter's self-confidence, but it also pointed her research in the direction she would follow from then on. P~ter realized that the primitive recursive functions 2 G6del used were important in their own right, not just as a tool for proving incompleteness. This insight led to h e r 1932 paper, 3 presented at the International Congress of Mathematicians in Zurich, in which P~ter became the first person to propose the study of recursive functions as a field in itself. She then proceeded to write m a n y of the first papers in that field. Between

* More people have helped and encouragedus in this research than we can acknowledgehere. We are deeply grateful to all

2 G6del's paper did not use this now standard t~a-dnology. In fact, it was POJer who introduced the phrase "primitive recursion" in 1934. 3 This paper appeared under her original name, R6zsa Politzer. Like many other Hungarians during that period, she changed her German-Jewish name to something more Hungarian. All of her subsequent work appeared under the name P(Rer.

those who shared their time and information with us. w This paper was written with support from the Charles A. Dana Foundation while at Cornell on sabbatical leave from Bellarmine. Many thanks to all three institutions. i Bulletin of the American Mathematical Society, 58 (1952), 270.

(continued on page 61)

THE MATHEMAtICAl. INTELLIGENCER VOL. 12. NO. 1 9 1990 Springer-Verlag New York 5 9

R6sza P6ter

pure water goes into the wine), but rather the main point is just whether one truly accepts the following explanation as convincing. Exactly as much wine goes into the water as water goes into the wine. For let us consider, say, the wine glass at the beginning and at the end, ignoring what happened in between. The liquid in it stands exactly as high at the end as at the beginning. The difference is just that it has lost some pure wine (which is now in the water glass) and gained some pure water. If its loss were greater or less than its gain, then the liquid would have to stand lower or higher than at the beginning. Thus its l o s s - - t h e wine that went into the w a t e r - - i s exactly as much as its gain: the water it received. Those w h o think less mathematically, let us say physicists, are still not convinced by this logical, clear explanation. They are satisfied only when one begins to calculate: If in a spoonful of the mixture are, for example, three-fourths parts water and one-fourth part wine, then from the spoonful of wine that went into the water, we put a quarter-spoon back again. Thus while three-quarters of a spoon of water were put into the wine, just three-quarters of a spoon of wine likewise remain in the water. For the mathematician, not calculation, but clear thinking is characteristic: the ability to disregard inessential things. Here is another problem, in which no numbers occur, and that requires just abstraction for its solut i o n - t h e ability to disregard things not essential to the question (and exactly this turns it into an exercise for mathematical thinkers): A train goes through a tunnel. Smoke enters through an open window into a 60

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

compartment, and the noses of the three travelers in the compartment become sooty. They look at each other and laugh. Each thinks that he alone took a lucky seat and so kept his nose clean. H o w does the cleverest of the three realize that his nose is sooty too? He can depend on only the three following assumptions: 1) there is nothing else to laugh at; 2) neither of the other two is about to stop laughing; 3) if somebody k n e w that he himself were also laughable, then he would not laugh. The solution is not very easy, but again what is crucial is not whether one finds the solution by oneself, but rather that the non-mathematical thinkers do not restrict themselves to the assumptions made. People have often exasperated me with solutions such as: "The cleverest one looks in a mirror." Or "The cleverest one thinks: the noses of the others became sooty - - w h y would I be an exception?" I can best relate the correct solution in the first person; forgive me for making myself the cleverest one. Call the two others, say, Kurt and Hans. I think as follows: Kurt has reason to laugh--after all, he sees the sooty nose of Hans. But he also sees that Hans is laughing. Why doesn't he get the idea from that, that his nose is also sooty? Indeed, otherwise Hans would not see anything at all laughable from his viewpoint--except in the case that my nose is sooty too. But that must be the case, because Hans laughs and Kurt doesn't stop laughing. To stick to assumptions once they are laid d o w n is precisely what is essential in the axiomatic development of mathematics. Furthermore, such a precise development became particularly important as contradictions arose in so-called "naive" mathematics. I will return to this later. Here I would just like to empha-

For the mathematician, not calculation, but clear thinking is characteristic: the ability to disregard inessential things. size that never are all the properties of the objects u n d e r consideration captured by axioms, but only some properties, and so it can happen that even totally different objects satisfy the same axioms. One then says that there exist different "models" of the axiom system being considered. I have also cited examples of this in my book, so I do not wish to go into it further here. Abstraction plays an essential role in all of mathematics. Indeed, our natural numbers arose by abstraction. Primitive peoples are known that use different numbers for counting thick objects and for counting flat ones, etc.; they have, say, seven such number sequences in all, so that in order to be able to count to

ten they would have to create seventy number words. For example, fiat shells were the currency of a tribe, and initially the people counted fiat objects with the following words (in their language): "oneshell, twoshell, etc." Then in time the meaning of shells completely disappeared so that today, "oneshell" means simply "one," "twoshell'" simply "two," etc. Everyone can observe how the concept of number is formed in a youngster. It takes a long time until the common property of "twoeyes," "twolegs," "twonuts," namely their number, becomes clear. The drab sign 2 is just a symbol of the many living two's. If we look at it, then there should arise before us a picture, such as

that of all the pairs in the world marching into Noah's Ark: two doves, two lambs, two lions, but also two legs, two words, etc. One could say to this: Yes, people have come by the abstract concept of number via living, richly colored things, but, after all, mathematics goes on to deal with this colorless concept of number. However, w h a t mathematics takes away with the one hand, it richly repays with the other hand: it colors the picture that had become colorless with unexpected new brushstrokes. Six apples, six rabbits, for example, are much more interesting than the six, abstracted from them, that people count with. But what a personal, interTHE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

61

esting brushstroke this six obtains if you find out that it is the first perfect number! Perhaps not everyone is familiar with this notion: A proper divisor of a number is a smaller number that divides into it without a remainder. A number is called perfect if it equals the sum of its proper divisors. For example, the numbers 1, 2, and 3 are all the proper divisors of 6, and in fact 1+2+3=6.

Discovery No other field can offer, to such an extent as mathematics, the joy of discovery, which is perhaps the greatest h u m a n joy. The schoolchildren that I have taught in the past were always attuned to this, and so I have also learned much from them. It never would have occurred to me, for instance, to talk about the Euclidean Algorithm in a class with twelve-year-old girls, but my students led me to do it. I would like to recount this lesson. What we were busy with was that I would name two numbers, and the students would figure out their greatest common divisor. For small numbers this went quickly. Gradually, I named larger and larger numbers so that the students would experience difficulty and would want to have a procedure. I thought that the procedure would be factorization into primes. T h e y h a d still easily f i g u r e d o u t the g r e a t e s t common divisor of 60 and 48: "'Twelve!" But a girl remarked: "Well, that's just the same as the difference of 60 and 48." "That's a coincidence," I said and wanted to go on. But they w o u l d not let me go on: "Please name us numbers where it isn't like that." "Fine. Sixty and 36 also have 12 as their greatest common divisor, and their difference is 24." Another interruption: "'Here the difference is twice as big as the greatest common divisor." "All right, if this will satisfy all of you, it is in fact no

It never would have occurred to me, for instance, to talk about the Euclidean Algorithm in a class with twelve-year-old girls, but my students led me to do it. coincidence: the difference of two numbers is always divisible by all their common divisors. And so is their sum." Certainly that needed to be stated in full, but having done so, I really did want to move on. However, I still could not do that. A girl asked: "'Couldn't they discover a procedure to find the greatest common divisor just from that?" They certainly could! But that is precisely the basic 62

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO~ 1, 1990

idea behind the Euclidean Algorithm! So I abandoned my plan and went the w a y that my students led me. For example, the reason w h y it is hard to figure out the greatest common divisor of 116 and 36 is that 116 is disagreeably large. But n o w we already know that the greatest common divisor also goes into their difference, thus also into 80, and of course 80 is smaller than 116. On the other hand, whatever goes into 80 and 36 evenly also goes into their sum 116. We could thus look for the greatest common divisor of 80 and 36 instead of 116 and 36. Whoever finds these numbers too big can again take the difference of these numbers, i.e., 44, in place of 80. The greatest common divisor of 44 and 36 is already much easier to figure out. But whoever wants to avoid even that work can take the difference of these numbers, i.e., 8, in place of 44; then the difference of 36 and 8, i.e., 28, in place of 36; the difference of 28 and 8, i.e., 20, in place of 28; the difference of 20 and 8, i.e., 12, in place of 20; finally, the difference of 12 and 8, i.e., 4, in place of 12, and the fact that 4 is the greatest common divisor of 4 and 8, certainly anyone can see that. So they had the desired procedure in hand: to decrease the numbers by subtraction so that figuring out their greatest common divisor becomes child's play. Naturally, all that subtraction quickly became tedious to the girls, and they observed that it is also unnecessary. Just now, for example, we subtracted 36 from 116 three times in a row until 8 was left, then subtracted this 8 from 36 four times until 4 was left. That was so because 36 goes into 116 three times with remainder 8, and 8 goes into 36 four times with remainder 4. Thus instead of the many subtractions, one can perform a single division and immediately replace the larger number with the remainder of this division. And with that, the procedure has been found. I would also like to remark that it is not just the rediscovery of already-known results in mathematics that is possible for intelligent schoolchildren. I know a schoolchild who was twelve years old when his first original mathematical result appeared in a mathematical j o u r n a l - - o n e not meant for schools. In another field, that would hardly be conceivable. People created the natural numbers for the purpose of counting, but now they are here and have their o w n rules that were not planned and can no longer be changed; the mathematician sets about discovering these. Even my students often discovered something that I had not thought about at all. I would like to give one further example of this. I told my favorite high school class that there are lightning calculators who solve complicated arithmetic problems amazingly quickly, but often a mathematician w h o calculates slowly can beat them by knowing certain mathematical relationships. I wanted to show, among other things, how one can rapidly calculate a sum like this:

1

1

1

1---~ + ~

+ ~

1

1

+ 4---~5 + 5---T-6

and every sum that is formed by adding further similar terms. I a s k e d m y s t u d e n t s to look at these numbers closely themselves. I expected that someone might notice that 1

1 n

n(n + 1)

1 n + 1

Consequently, our sum can be written as follows: _1 _ _ +1_ _ _ +1_ - - _1+ _ - -1- + - - 1- 1 2 2 3 3 4

1 4

1 5

1 5

1 6

Outside of the first and last terms, everything cancels out, so one can give the answer right away: 1

1 6

always be typed in. Indeed, one can observe that there are very many texts of 100 symbols, although only finitely many: the first symbol can turn out 95 different ways, for each of these the second symbol again 95 ways, so the first two symbols 95 times 95 ways, etc.; thus one sees that there are 95 l~176 texts of 100 symbols: a large, but finite number. Even definitions of natural numbers occur among these texts; for example, 3 is

5 6"

However, a girl came up with a totally different observation that, to be sure, has nothing to do with rapid addition, but that is interesting in its o w n right. She observed the denominators of the above example (independently of h o w they were actually being used), included further terms, thus 1.2,2.3,3.4,4.5,5"6, 6.7,7.8,8"9,9"10 ..... and noticed that by carrying out the multiplication, no matter how far one goes, one always produces, like clockwork, n u m b e r s with the following repetitive endings: 262002620... That really does always hold, and it is not hard to prove it in general; perhaps someone would like to think it over after the address. Contradictions and Axiomatics

I would also like to discuss one of the contradictions mentioned earlier that likewise has something of the playful about it: the so-called Richard's Paradox. Imagine a typewriter suitable for all English texts; let us assume, for example, that it can type 95 different symbols. The blank space will also be counted among the symbols. If a monkey, let us say, begins to type on it, then a mostly meaningless text of, say, 100 symbols will result; but meaningful texts could also accidentally appear. For instance, among the texts of 100 symbols occur all--true and false--wedding announcements, because these always consist of many fewer than 100 symbols, and trailing blank spaces up to 100 can also

The terms, about which the axioms say something, signify nothing concrete, but rather arbitrary things that possess the basic properties stated in the axioms. However, everyone who deals with them secretly thinks about concrete things. defined by the following text (and blank spaces thereafter): "The smallest odd prime number." However, not every natural number can be defined by some text of 100 symbols, because there are infinitely many natural numbers. Let us consider the smallest among the natural numbers not definable with 100 symbols. I define: "The smallest natural number that cannot be defined b y using one h u n d r e d s y m b o l s . " It can be checked that this definition consists of 80 symbols, thus of exactly 100 symbols if, in addition, 20 blank spaces are typed after this. Therefore, this number, that cannot be defined by 100 symbols, can be defined by 100 symbols. This is Richard's Paradox. Such a contradiction surely indicates that mathematics is not boringly cut-and-dried "two times two." The precise axiomatic development of mathematics aims, above all, to eliminate such contradictions. And the terms, about which the axioms say something, signify nothing concrete, but rather arbitrary things that p o s s e s s the basic properties stated in the axioms. H o w e v e r , everyone w h o deals with them secretly thinks about concrete things. I have already mentioned the different models that the same axioms can satisfy. N o w in mathematics the f o r m - - t h e formal r u l e s - often helps us obtain new content. For example, I wilt n o w a s s u m e that p e o p l e k n o w only of the real numbers. Well, people have also found a general formula, the so-called Cardano's Formula, to solve cubic equations. If one applies it to, say, the equation x3-6x-4=0, then one obtains:

The meaningless ~

appears here (twice, even), al-

THE MATHEMATICAL 1NTELLIGENCER VOL. 12, NO. 1, 1990

63

though the square root of a negative number cannot be extracted. One is inclined to say then that this equation has no solution. But after all, if one tries out small whole numbers, o n e soon finds that x = - 2 is a solution; please check it out. Couldn't this be gotten from Cardano's Formula? If one looks more closely at the result obtained from the formula, then one notices that the meaningless appears in it once with a plus sign and once with a minus sign. If the indicated operations are performed, then one can hope that the two meaningless values cancel out. But how does one perform operations with such meaningless things? One tries it with the help of the old formal rules. It works and, in fact, o n e obtains the expected solution - 2 for our equation, plus two other reasonable solutions besides. So the formal rules helped and even led to a new field in mathematics: indeed, it turns out that it is worthwhile to expand the notion of number with so-called imaginary numbers such as X/-Z4. The Infinite

Among the m a n y common traits of art and mathematics, I would like to mention just one more still, perhaps the most exciting: the encounter with the infinite. An example from literature, namely Joseph and His Brothers by Thomas Mann, reads:

brick, which weighs 1/2 kilogram plus its half, that is, a quarter brick. The weight of the quarter brick is V4kilogram and half of the quarter brick, that is, an eighth brick. So a brick weighs 1 1+-+2

1 4

kilograms plus an eighth brick. And so it continues: 1 1 +-

2

1 +-

4

1 +-

8

+ ...adinfinitum.

But on the other hand, it is clear that a balance, with a brick on the left scale and a kilogram plus a half brick on the right, is evenly balanced. The half brick on the right balances with a half of the whole brick on the left; so the kilogram weight on the right must balance with the other half. Therefore, a half brick weighs 1 kilogram, and thus a whole brick weighs 2 kilograms. So the anxiety due to the addition's extending ad infinitum is dispelled: the sum of the infinite series 1 +-

1 2

+-

1 4

+-

1 8

+ . . .adinfinitum

is, quite precisely, equal to 2. P u r e (?) M a t h e m a t i c s

And in mathematics? My book, from which I do not wish to quote anything here, was particularly devoted to encounters with the infinite. Here I would like to show, by an example not in the book, how in mathematics the anxiety caused by infinity can be dispelled. Someone says: "'The weight of a brick is 1 kilogram plus a half brick. How much does the brick weigh in kilograms?" One can begin as follows: First, it weighs 1 kilogram, and on top of that comes the weight of a half

It would be appropriate to end my speech with how this happens in music, with the resolution of dissonances. Many people, however, would consider it a shortcoming that not a word has been said here about the practical applicability of mathematics. Now in this regard mathematics needs no speech in its defense; certainly, it is well known that mathematics is indispensable nearly everywhere in h u m a n activity, and particularly in scientific activity. I would like to win over those who consider mathematics useful, but colorless and d r y - - a necessary evil. I myself work in a field that was created for purposes internal to mathematics. This is the theory of the so-called recursive f u n c t i o n s - - I would not have dreamed that this theory could also be applied practically. And today? My book on recursive functions was the second H u n g a r i a n m a t h e m a t i c a l book to be p u b l i s h e d in the Soviet Union, and precisely on the practical grounds that its subject matter has become indispensable to the theory of computers. And so it goes, sooner or later, for all branches of so-called pure mathematics. In my address I wished to show that one can fall in love with mathematics. Now I would add: one never has to worry that one is working on something useless, either.

2 Translator's note: This translation of Mann appears in Joseph and His Brothers, translated by H. T. Lowe-Porter and published by Alfred A. Knopf, Inc.

Leon Harkleroad Department of Mathematics Bellarmine College Louisville, KY 40205 USA

Very deep is the well of the past. Should we not call it bottomless? Bottomless indeed, if--and perhaps only if--the past we mean is the past merely of the life of m a n k i n d . . . For the deeper we sound, the further down into the lower world of the past we probe and press, the more do we find that the earliest foundations of humanity, its history and culture, reveal themselves unfathomable. No matter to what hazardous lengths we let out our line they still withdraw again, and further, into the depths. 'Again' and 'further' are the right words, for the unresearchable plays a kind of mocking game with our researching ardours; it offers apparent holds and goals, behind which, when we have gained them, new reaches of the past still open o u t . 2

64

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Some Topological Problems in Robotics Daniel R. Baker

This paper is intended to be an exposition for mathematicians on some problems in engineering, and, before introducing these problems, it seems worthwhile to first arm the reader with at least one concrete example of the objects under discussion. Figure l(a) shows a picture of a type of robot commonly used in m a n y robotics applications, for example, in the automobile industry. The robot consists of a three-link arm (with joints 01, 02, and 03), and a wrist attached to the end of the arm. The wrist also has three joints, 04, 05, and 06, which can be used to orient a tool mounted on the end of the arm. Because the space of orientations, SO(3), is three-dimensional, a minimum of three joints is needed to orient the tool in an arbitrary fashion. Such robots are typically used for jobs such as parts assembly, welding, or spray painting (see Figure l(b)). The robot can be programmed to do such work by specifying a time-dependent trajectory it should follow in the so-called operational space, which, in the case of parts assembly, might be the space R 3 x SO(3). The R 3 component of the trajectory specifies the p o s i t i o n of the tool mounted on the end of the robot, and the SO(3) component specifies the orientation of the tool. Although the task of a robot is specified by giving a trajectory in the operational space, this trajectory must be followed by giving commands to the joint motors to execute an associated trajectory in the joint space. For the robot pictured in Figure l(a), all joints are rotational, so that this joint space can be viewed as a sixdimensional toms, T6. There is clearly a function

As is the case for many conventional robots, this one is equipped with the minimum number of joints (six) needed to be able to move around freely in its six-dimensional operational space. This economy in engineering design seems natural at first, but it also has disadvantages. If the robot works in a crowded environment, it might be useful to have extra, redundant joints which enable the arm to move around to avoid obstacles while holding the endpoint of the arm fixed. These redundant joints also offer another potential advantage, which is not so obvious at first glance. They can be used to avoid singular joint configurations, i.e., joint positions at which the Jacobian df of the forward kinematics map does not have maximal rank. Singular configurations cause the mecha-

f : T6 ~ R 3 x SO(3), known as the forward kinematics map, which associates to each point 0 in the joint space the corresponding position and orientation of the robot when the robot joints are positioned at 0. 66

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1 9 1990 Springer-Verlag New York

nism to lock up, rendering it unable to move in certain directions. Examples of this problem are given in the next section, where it is shown that avoiding singular configurations restricts the potential work area of a nonredundant robot. On the other hand, if extra joints are available, most positions in the operational space will be reachable by a continuum of different joint configurations, and this choice in joint motions, for the same motion in the operational space, should make it possible to avoid singularities without restricting the work area. Such a strategy opens up a whole n e w class of technical problems, namely, one must n o w decide which of an infinite number of different joint trajectories one should use in order to follow a trajectory in the operational space. An exact formulation of the problem depends on the nature of the robotics task, and two broad classes of problems emerge, demanding fundamentally different solution methods. We shall refer to these two different types of tasks as global and local problems. To define them, denote the position in operational space, as a function of time t, by x(t), and denote the position of the joints by 0(t). A global problem is one in which the entire desired trajectory x(t) is known ahead of time, and the path 0(t) must be chosen so as to produce x(t). This will be the case, for example, if the robot is to perform the same task, over and over again, without changes. Local problems, on the other hand, assume no prior knowledge of the future of the trajectory which is to be followed. Such problems occur w h e n the robot is being guided by sensor input, and the path x(t) is continually changing in reaction to this input. As such, only local information, such as the germ of x(t), is available as one determines 0(t). Global problems can be solved off-line, using as much computer time and memory as is convenient. To solve a local problem, the path 0(t) must be determined on-line, as the motion is being performed, which means that the solution must be simple e n o u g h to be p e r f o r m e d quickly and with more modest computing resources. When solving global problems, one can take into consideration many of the practical limitations of the problem, such as hardware limits on joint speeds or torques (see, e.g., [8] and [4]), treating them as constraints in a variational problem, where one tries to minimize over the entire path some average quantity such as the square of the joint velocity,

Figure l(a). A six-jointed robot (the PUMA 560), used for positioning and orienting tasks. The first three joints position the arm, and the last three joints orient the wrist at the end of the arm.

Figure l(b). Robots spray-painting a car body.

T

f0

11()(t) II2 dt,

(1.1)

subject to the additional constraint that one must follow the path x(t) while doing so. It should be pointed out that such a strategy does not a priori guarantee the avoidance of singularities, but, as we shall see, joint speeds tend to rise when approaching a sin-

Figure 2. An n-joint planar mechanism, shown for n = 5. The mechanism consists of straight links attached in a serial fashion via rotational joints to a fixed base. A tool mounted at the end-effector can be positioned in the plane by rotating the joints of the mechanism. THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

67

Figure 3(a). A two-joint pointing mechanism can be used to point tools such as spray-painters, welding guns, or screwdrivers in variable directions. Although the mechanism is normally mounted on a mechanical arm, so that the tool can be positioned as well as pointed, it is shown here mounted on a fixed base. The sphere of pointing directions is also shown, positioned with its center at the tail of the mechanical arrow. Note that the rotational axes of the two joints also pass through the center of the sphere. As pictured, the mechanism is pointing towards the back of the sphere. The joint coordinates for this mechanism turn out to coincide with the usual spherical coordinates.

two-joint mechanism, the axes of all joints pass through the center of the sphere of pointing directions. As a result, rotating these joints will not alter the position of the tail of the arrow, which is also positioned at the center of the sphere, but will only alter the direction of the arrow.

Figure 3(b). By attaching the mechanism of Figure 3(a) to a third joint, the mechanism becomes a three-joint, redundant, pointing mechanism. Note that, as is the case for the

Figure 3(c). The pointing mechanism is in a singular configuration, if all three rotational axes and the arrow lie in a common plane, as shown above. The configuration is singular, because no infinitesimal rotations of the joints will be capable of rotating the arrow about an axis perpendicular to this common plane. In fact, for the configuration shown, rotating the second joint produces no change in the pointing direction at all, even though, as soon as the second axis is rotated, the mechanism is no longer in a singular configuration.

gular configuration, a n d the optimal trajectory 0(t) usually stays a w a y from singularities. The variational a p p r o a c h to global problems points o u t t h a t the d i f f e r e n c e b e t w e e n local a n d global problems is m o r e t h a n just the c o m p u t i n g resources which can be b r o u g h t to bear on them. Optimizing the integral (1.1) can only be done if the entire path x(t) is already k n o w n , a n d the choice of 0(t0), at some time to, is influenced not just b y x(t) in some n e i g h b o r h o o d of t 0, but also by w h e r e x(t) will be at m u c h later times than t o. Thus local a n d global problems are different

from a mathematical, as well as a computational, p o i n t of view. The rest of this p a p e r will focus on solutions to the local p r o b l e m s . Most of the results to be p r e s e n t e d h a v e a p p e a r e d e l s e w h e r e , b u t in expositions a i m e d primarily at engineers. It turns out that there are some f u n d a m e n t a l limitations o n w h a t can be accomplished in solving the local p r o b l e m s , a n d these limitations arise f r o m topological c o n s i d e r a t i o n s of the j o i n t space, the operational space, a n d the forward kinematics map. Because these facts are p r o v e n using alge-

68

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

braic topological techniques, an exposition of the material aimed at mathematicians, where no previous knowledge of robotics is assumed, might be of general interest. If I can interest some mathematicians more generally in the field of robotics, that will be an added benefit. It is appropriate at this point to acknowledge my indebtedness to Charles Wampler, the engineer who introduced me to r e d u n d a n t manipulators, as these mechanisms are often called, and who is responsible, either jointly with me in [2] and [3], or in the papers [9] and [10], for much of what will be presented here.

The Main Results The notion of operational space, used in the last section, needs to be generalized somewhat, and we return to the robot in Figure l(a) to illustrate this. It has already been noted that the appropriate operational space for such a robot, when used for tasks such as parts assembly, is the space R3 x SO(3). In contrast to this, the jobs of welding or spray painting do not require the full space of orientations, because the angle of rotation a r o u n d the pointing direction of the welding gun or spray painter is immaterial. All that matters is the direction in which the tool is pointing, so that, for such jobs, the operational space would be R 3 x S2, where S2 is the two-sphere of pointing directions. This space is five-dimensional, so that the sixjointed robot becomes redundant when used for such jobs. Other examples of operational spaces of interest are R 2 or R 3, if motion without orientation in the plane or in three-space is being considered, and S2 or SO(3), if we wish to c o n s i d e r the motion of orienting or pointing wrists, not attached to positional arms. It is, of course, possible to use several robots working together to perform tasks, so that cross-products of these spaces are also potentially useful. In w h a t follows, we will denote operational spaces with the letter X. We will also enlarge the class of robots under consideration to contain somewhat more general joint spaces. These will include joints that are either rotational and parameterized by angles on the circle, S1, or translational (also called prismatic) joints, parameterized by points on some d o s e d interval [a, b] of the real line. It may also occur that rotational joints have angle limits, so that they too may be parameterized by intervals. The joint space, to be denoted by ]n, will be the cross-product of the parameter spaces for each of the robot's n motorized joints, and will always have the homotopy type of a toms. Note that we are excluding ball joints, the positions of which are parameterized by S2, from this description. This is because it is difficult to power a ball joint with a motor, although

they can still be used as passive joints in a mechanism. In such cases they will constrain the motion of the motorized joints, restricting the joint motions to some subset of the space J". Care must be used in generalizing the results presented here to this more general context. We will assume that each point in J~ determines a physically allowable joint configuration for the robot, which, in turn, positions the robot at some point in the operational space X. This means, in particular, that the mechanism is not constrained to move in a subspace of J", as described above, and one can thus define the forward kinematics map on the entire joint space,

f:J~---~ X, as described in the last section. Given a trajectory x(t) C X, we must find a path 0(t) C jn with f(0(t)) = x(t), in order to get the robot to track the path x(t). We turn now to some examples of these constructions, which will be useful in what follows:

The n-Joint Planar Mechanism: This mechanism is pictured in Figure 2, and it is not hard to build a cardboard model of it. Each of the joints is rotational, and can be made using a thumb tack to hold the cardboard links together. We denote points in the joint space Jn = Tn by 0 = (01. . . . . 0n), where 0i is the angle the i-th link makes to the horizontal axis. The mechanism positions its endpoint somewhere in the plane, so that X = R 2. Obviously, redundancy occurs when n > 2. The forward kinematics map is given by n

f(0) =

lj 0j, j=l

where ll is the length of the j-th link.

Pointing Mechanisms: Figure 3(a) shows a picture of a two-joint pointing mechanism. By choosing different positions for the two joints in the mechanism, the mechanical arrow can be made to point in any desired direction. The operational space is S2, the mechanism is nonredundant, and the angles 01 and 02 turn out to be the usual spherical coordinates on the sphere. One thus has the forward kinematics map given by f(01, 02) = (COS 02 COS 01, COS 02 s i n

01,

s i n 02).

Figure 3(b) shows a three-joint, redundant pointing mechanism. We leave it as an exercise to the reader to write d o w n the forward kinematics map. Recall from the last section that a point 0 E jn is called a singular configuration if the Jacobian df of the forward kinematics map at 0 does not have maximal rank. Each of the above examples has singular configurations, which we now examine. For the n-joint planar mechanism the singular conTHE MATHEMATICALINTELLIGENCERVOL. 12, NO. 1, 1990 69

0 2 -~ ~ '11"/2. Note that varying 01 when in either of these configurations produces no change in the pointing direction. Because the entire mechanism lies in a plane, infinitesimal rotations of the pointer around an axis perpendicular to the plane of the mechanism are impossible to attain. A singular configuration for the redundant pointing mechanism is shown in Figure 3(c). Singularities are particularly unpleasant for the robotics engineer, because joint speeds tend to blow up near them when tracking paths of bounded speed in the operational space. This is because, as the Jacobian df starts to become singular, the ratios of velocities along the path

/

when

Figure 4. A singular configuration for a three-joint planar mechanism. No infinitesimal rotation of the joints can produce a motion of the end-effector in the direction of the arrow.

5

, ?

6"i

~

3

~

5

x(t) 4

3

2

1

i i i

i

7 Figure 5. A two-joint planar mechanism has a singularity

when pointing at its base, if both link lengths are equal. Different configurations are shown for such a mechanism, as it tracks a path which goes near, but not through, the singularity. For a set of equally spaced points along the path, the corresponding positions of the elbow are also shown. As the mechanism goes by the singularity, it is forced to switch from an elbow-up position to an elbow-down position, and the closer the path comes to the singularity, the quicker this switch must take place. The resulting increase in joint speeds, when tracking the path at constant speed, can be seen from the increasing distance between tick-marks along the elbow trajectory. figurations occur w h e n the mechanism is jackknifed, i.e., when 0 i = 0 j o r 0 i = 0 j q- q'c, for all i andj. Such a configuration is shown in Figure 4. Note that no infinitesimal joint motions can create motion in the radial direction in the operational space w h e n the mechanism is in such a configuration. Both the redundant and the nonredundant pointing mechanisms are in singular configurations w h e n the entire mechanism lies in a plane. For the nonredundant mechanism, this will occur when pointing in the directions of either the north or the south poles, i.e., 70

THE MATHEMATICAL 1NTELLIGENCER VOL. 12, NO. 1, 1990

li 6 II II i ll' with df(O) = i, may tend to infinity. An example of this is s h o w n in Figure 5, which shows a 2-1ink, nonredundant planar manipulator, with both links of equal length. A singularity occurs when the end of the manipulator is at the origin, the base of the manipulator, and Figure 5 shows several configurations as the mechanism tracks a straight line path going near, but not passing through the origin. Tick marks have been made at regular intervals along this path, and corresponding tick marks also show where the elbow of the manipulator is positioned w h e n the end of the manipulator is at each mark on the straight line. The large spacing between elbow tick marks shows that the joint speeds must increase as the manipulator goes by the origin. This is because the mechanism is forced to switch quickly from an "elbow-up" position, on the right-hand side, to an "elbow-down" position on the left-hand side. The closer the path comes to the origin, the faster the transition from elbow-up to elbow-down takes place, and this forces the joint speeds to become infinite. Strangely, the problem does not arise w h e n tracking a straight line that goes directly through the singularity. In this case, the manipulator can track on both sides of the singularity in an elbow-up position, so that high joint speeds are not necessary. High joint speeds also become necessary w h e n the nonredundant pointing mechanism tracks paths near its singularities, the north and south poles. Suppose, for example, we track a path given by the intersection of a plane, parallel to the north-south axis but not containing it, with the two-sphere. Figure 6 shows a bird'seye view of what such a path would look like, looking down on the sphere from above the north pole. The figure shows that, as the mechanism goes by the north pole, the first angle 01 is forced to make a quick jump of close to "rr radians, and the closer the path comes to the north pole, the faster this jump must take place. As in the case of the two-joint planar mechanism, the problem does not arise at all if the path being tracked goes directly through the singularity. In such situa-

tions, the pointing mechanism can hold 01 constant and track by varying 02 at bounded speeds. These facts force the engineer using such mechanisms to avoid not only the singularities themselves, but also neighborhoods around these singularities, in order to bound the ratios of joint speeds to operational space speeds when tracking paths. The size of the hole to be cut out of the operational space depends on how tightly one wants to b o u n d these speed ratios, but some hole must be cut out, in any event. For the twojoint planar mechanism, this means that we cannot go too close to the origin, and, for the pointing mechanism, we must stay away from the north and south poles. Such limitations become even more annoying, for example, if one imagines the n o n r e d u n d a n t pointing mechanism mounted on a positional arm. As the arm moves, the north and south poles will rotate along with the last link of the arm, and the holes that must be cut out of the pointing sphere rotate as well. The point now is that redundant joints can be used to avoid singularities, and the accompanying high joint speeds. Figure 7 s h o w s a three-joint planar mechanism tracking the same path tracked by the two-joint mechanism in Figure 5. Because of the redundancy, the mechanism is capable of tracking the entire path in an elbow-up position, and as the path gets closer to the origin, the joint speeds remain bounded. The three-joint pointing mechanism offers similar advantages. Although the mechanism still has singularities, all pointing directions can be reached by nonsingular configurations. To see this, consider the singular configuration shown in Figure 3(c). To point in the same direction nonsingularly, it suffices to rotate the second joint so that the rotational axis of the third joint comes out of the plane of the singular configuration, while the pointing vector remains fixed. The resulting con.figuration will then be nonsingular, since df(03) and df(02) are linearly independent. The situation now becomes very reminiscent of path lifting problems in covering spaces or fibre bundles. One has the forward kinematics map

this problem under two different sets of assumptions. Either one knows the entire path at the outset, resulting in a global optimization problem, or, in the case where the path is being guided by sensor informarion, one must choose the lifting using only local information about the path in operational space. We concentrate now on this local question, and first discuss briefly some of the methods that have been proposed to design algorithms. The most natural way to construct a local path lifting algorithm is to use a differential equation of the form Y

i

i i i

.....

- .....

X

i

.. Figure 6. The two-joint pointing mechanism has singularities when pointing in the direction of the north or south poles. The figure shows a view of the pointing sphere, looking down the axis through the poles, i.e., the z-axis. A path on the sphere is shown which goes near, but not through, the north pole, and the first joint angle is shown at two different positions along this path. As the mechanism goes by the north pole, 01 is forced to jump suddenly by an amount close to ~r radians, and the closer the path comes to the north pole, the quicker this jump must take place.

f: ln---~ X, and, given a path x(t) C X, one must determine a path lifting O(t) in jn with f(O(t)) = x(t). There are, however, some new wrinkles to this old problem. First of all, the forward kinematics map is not really a fibre bundle map; it has singularities, and they must be avoided by the path liftings. Furthermore, an algorithm for performing this path lifting must be given in such a fashion that a computer can perform it. All of this said and done, one would also like to optimize the algorithm so that it not only avoids singularities, but optimizes the ratios of joint speeds to operational space speeds in some sense. As mentioned in the introduction, one can approach

x(t)

Figure 7. A three-joint planar mechanism tracking the same

path shown in Figure 5. Because of the redundancy, the mechanism can remain in an elbow-up position for the entire path, and the ratios of joint speeds to operational space speeds remain bounded, as the path approaches the base of the mechanism. THE

MATHEMATICAL

INTELLIGENCER

VOL.

12, NO.

1, 1990

71

= G(0,

i),

where

of the operational space. It follows that n - m is the degree of our redundancy, so let

df(G(O, i)) = i.

h: J"-+ M

If one can construct such a function G, the computer can integrate the differential equation, producing a path lifting. There is, of course, no reason not to consider higher order differential equations as well, as has been done in [8] to minimize joint torques, but we will restrict our attention here to first order equations. One method which has been proposed for defining G (see [7]) is to take G(0, 50 to minimize ]] 0 ]]2in the set

be a smooth constraint function from the joint space to some n - m dimensional manifold M. One considers now the function

{0 I df(O) -- i}.

f x h(0(t)) = (x(t), constant).

This is certainly a natural choice, but it has been found to have a number of disadvantages. First, and perhaps surprisingly, situations will arise w h e n this method steers you straight into a singularity. Although this is unlikely, it is still possible, and this means that following sensor information can steer you unwittingly into a lock-up position. The method suffers from another disadvantage, which is also common to other proposals for solving local problems. Given a closed path x(t) in the operational space, it will usually be tracked by an open path in the joint space. This property is undesirable from an engineering standpoint, because it leads to unpredictability. Suppose, for example, that the robot will follow the same trajectory over and over again (or even approximately the same trajectory, if it is being modified by sensor information). As the path in operational space is repeated, the path in joint space may start to wander, bringing the mechanism into unforeseen positions. This makes any evaluation of the path in terms of an optimization criterion difficult, and, if obstacle avoidance is an issue, it can pose more severe dangers. It also makes it very difficult to know ahead of time when the manipulator will run into a singularity, and, if some of the joints have angle limits, which is usually the case, it is hard to predict w h e n they will be exceeded. Because this issue will arise repeatedly in our discussions, we forrealize it:

The constant will be determined by the initial operating position of the manipulator when tracking starts. Again, this method offers no guarantee of avoiding singularities, and the skill in using it lies in proposing appropriate functions h, which either avoid singularities or put them in places where they are not so annoying. The constraint function h can also have the effect of introducing artifidal singularities where before there were none. This is because, in order to solve (2.1), one must invert f x h, and this requires that the extended Jacobian

Definition: Call a tracking algorithm cyclic if every closed path in the operational space is tracked by a closed path in the joint space.

Although it need not always be the case, the above d e s c r i b e d a l g o r i t h m u s u a l l y leads to non-cyclic tracking. There is another general strategy for solving local problems that e n c o m p a s s e s a n u m b e r of solution methods proposed in the literature. In [1] it has been dubbed the extended Jacobian method, and uses constraint functions to resolve the indeterminacy arising because of redundancy. Specifically, suppose n is the dimension of our joint space, and m is the dimension 72

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

fxh:J"--+XxM, which is defined between manifolds of equal dimension. It is possible to track paths x(t) in X by requiring that (2.1)

be nonsingular. This matrix can become singular, even at points where df has maximal rank. To solve (2.1), it is turned into a differential equation of the form dr(0) =

dh(O) = O. Unfortunately, the extended Jacobian method also can produce non-cyclic tracking. The last solution method for local problems to be discussed is conceptually the simplest of all. An inverse kinematic function (or just an inverse function) defined on some subset X0 C X is a

Definition:

differentiable function g : X 0 ~ J" with f o g = id. Given an inverse function, path tracking seems very easy. The path x(t) in X0 is tracked by 0(t) = g(x(t)) in jn. The simplicity of this is, h o w e v e r , deceptive. Whereas there is a wealth of software tools for solving differential equations on a computer, the construction of an inverse function, in particular, one that can easily be stored and evaluated by computer, is much more difficult. Examples of inverse functions for redundant pointing mechanisms have been given in [9], but general methods for obtaining them for more complicated manipulators are not yet available. Note that we have allowed X0, the domain of definition of g, to be a proper subset of X, even though one can then

only track paths lying entirely in X0. The following theorem explains why. THEOREM 2.1: Suppose X = S 2 or X = S0(3). Then no inverse function can be defined on all of X.

Theorem 2.1 is not difficult to prove, using cup products and cohomology arguments. Its significance for robotics was first noted in [6], and it implies that inverse functions can never be entirely successful in circumventing the problems of singularities w h e n pointing or orienting. This is true no matter h o w much redundancy we are prepared to allow ourselves. Thus it is t e m p t i n g to forge ahead, looking for other methods that might provide complete solutions. The search for other more satisfactory tracking algorithms opens up yet another question. H o w can you tell if a tracking algorithm is equivalent to one induced by an inverse function, even if this fact is not obvious in its implementation? For example, an inverse function can easily be reformulated in terms of differential equations, so that it is no longer apparent that Theorem 2.1 still applies. The answer to this question turns out to be of particular interest, because it makes clear what price must be paid if we are to look for solutions not given by inverse functions. THEOREM 2.2: A tracking algorithm is equivalent to one determined by inverse functions if and only if the tracking algorithm is cyclic.

In order to rigorously prove Theorem 2.2, one must first carefully define exactly w h a t is m e a n t by a tracking algorithm. This has been done in [2], in the form of a set of axioms. Most important of these axioms is the stipulation that the germ of the tracking path 0(t) be determined only by the germ of the path x(t) in operational space, which is necessary if the tracking algorithm is to be a solution to a local problem. Given a cyclic tracking algorithm, it is not difficult to define the associated inverse function. We start out by choosing basepoints x 0 in X and 00 in Jn, with f(00) = x0. To define the inverse function at some point x I, choose a path x(t), starting at xo and ending at xl. Let 0(t) be the path in joint space, determined by the tracking algorithm, which tracks x(t) starting at 00 and ending at some point 01. We define g(xl) = 01. Because the tracking algorithm is cyclic, the point 01 must be independent of the path chosen from x0 to x 1, so that this definition makes sense. The proof that the resulting function is continuous is somewhat more technical, and the reader is referred to [2] for the details. The disadvantages of non-cyclic tracking, along with Theorem 2.2, supply a powerful motivation for using inverse kinematic functions, in spite of the limitations imposed by Theorem 2.1. In fact, even though

Figure 8. Positioning the hole in the domain of an inverse function for a pointing mechanism, so that the connecting arm, on which the mechanism is mounted, goes through the hole.

the problem of singularities and the holes they make in operational spaces cannot be entirely eliminated using redundant manipulators for pointing or orienting, inverse functions can obtain significant improvements over the limitations for nonredundant manipulators. The inverse functions in [9] for three-jointed pointing mechanisms leave only one hole on the sphere uncovered, as opposed to two holes for the nonredundant case. Because the pointing mechanism is usually mounted on an arm, and pointing in the direction of the connecting arm link is impossible for mechanical reasons, it makes sense to try to position the hole in the inverse function as is shown in Figure 8. Unfortunately, for the configuration of the wrist links in the manipulator in Figure 8, this is impossible, and in [9] suggestions for changing the mechanical design to be able to position the hole over the arm link are made. The above discussion still does not resolve the question of whether or not it is possible to track on all of S2 or SO(3) if one is willing to use non-cyclic algorithms. The next theorem, p r o v e n in [2], states an e v e n stronger obstruction to doing this. THEOREM 2.3: Suppose X = S 2 or X = S0(3) and a tracking algorithm has been defined on all of X. Then there are closed paths in X of arbitrarily short length that are tracked by open paths in jn.

The above statement is not vacuous. In an appendix of [2], such a tracking algorithm for a three-joint THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990 7 3

Corollary: The extended Jacobian method cannot be used to track on all of S 2 or S0(3), no matter what constraint function is used or how much redundancy is available.

~

x(t) l i / / /

Figure 9. A three-joint planar mechanism tracking the boundary of a disk, centered at the base, on which an inverse function is defined. A configuration is shown, as described in Theorem 2.4, in which the i-th link is pointing in the opposite direction of the vector from the base to the endeffector.

So far, most of our attention has been focused on problems of pointing and orienting. We now discuss some a n a l o g o u s results for positional manipulators.We will focus on the n-joint planar mechanism and determine the radius of the largest disk, centered at the base of the manipulator, on which an inverse function can be defined. The methods involved in this problem must be somewhat different from the cohomology arguments used to prove Theorem 2.1. Because the disk has no nonzero cohomology in positive dimensions, and all disks are the same from a topological standpoint, we will have to use a finer argument.

Theorem 2.4: Suppose an inverse function g: D(r) --~ T ~ exists for the n-joint planar mechanism on the disk D(r) of radius r, and let g ( x ) = (01(x) . . . .

,0.(x)).

Let x(t) be the path around the boundary of D(r), x(t) = re z~it.

Then, for every 1 ~ i ~ n, there is some value of t with -x(t) 0i(x(t)) = [I x(t)I-----~"

Figure 10. The maximum radius r that can be reached when the longest link of a planar mechanism is pointing in the opposite direction of the vector from the base to the end-effector. No inverse function can be defined on a disk of radius greater than r centered at the base of the mechanism. pointing mechanism is given. In addition to having the property predicted in Theorem 2.3, it has the additional disadvantage that unlimited path tracking can be done only if none of the joints has angle limits, and this makes it impractical to implement from an engineering point of view. Theorem 2.3 can be reformulated in a way that is instructive, using the following definition.

Definition:

A tracking algorithm is locally cyclic if there is an open covering {Ui} of X such that the tracking algorithm is cyclic when restricted to any Ui. T h e o r e m 2.3 n o w states that no locally cyclic tracking algorithm exists on all of S 2 o r SO(3). Because the extended Jacobian method is locally cyclic, one has the following: 74

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Figure 9 shows a picture of what such a configuration looks like. The theorem states that, on some point on the disk boundary, the i-th link of the manipulator must be pointing in the opposite direction of the line segment from the manipulator base to its endpoint. To see this, note that the i-th link of the manipulator must have winding number zero, as the manipulator traverses the outside boundary of the disk. This is because the function 0i(x) is defined on the interior of the disk, as well as on the boundary, so the path of the i-th link on the boundary can be deformed to a constant path at the center of the disk. On the other hand, the path x(t) has winding n u m b e r 1 about the origin. Using these observations, the theorem is not difficult to prove. One then has (see [10]): Corollary: Suppose 11. . . . . In are the link lengths of the n-joint planar manipulator, let L = E~'=1 li, and let lM be the longest link length. If r > L - 2l M, then no inverse function exists on D(r). The radius referred to in the corollary is the maxirnum distance the manipulator can reach, while its longest link is pointing in the direction opposite to the

other (aligned) links, as shown in Figure 10. It is worth remarking that analogous statements can be made for three-dimensional positional arms, but the arguments must be done using the degree of mappings of the two-sphere, instead of winding numbers around the circle. It turns out that if r < L - 21M, then an inverse function can actually be constructed on D(r). Several different such constructions have been given, but none of them simple enough to warrant publication. These ideas also generalize to a "rope" manipulator, which can be thought of as the limit, as n tends to infinity and the link lengths go to zero, of the n-joint planar mechanism. It looks like a snake, or an elep h a n t ' s trunk, and the joint-space J| is the set of smooth paths 0 : [0, L] --> R 2, parameterized by arclength, with

tion, so that it can be used to guide robots, and it seems reasonable to suspect that large scale applications of this sort will be some time in coming. Still, there is an enormous amount of interest in these questions in the research engineering community, and I believe that sensor-guided robot control will, at some point in the future, become commonplace in industrial applications. The analysis given in the last section was predicated on the assumption that the robot mechanism under consideration admits a forward kinematics map, and not all possible mechanisms satisfy this condition.

10(s)[ ~< K and 0(0) = 0. The curvature b o u n d is necessary in order to prevent the mechanism from breaking if it is folded too sharply onto itself. A lot of engineers have enjoyed playing with this idea, and proposals for building such manipulators (or approximations to them) continue to crop up at regular intervals. It is my understanding that one of the earlier attempts, called the " O r m , " was built around 1968 at Stanford University, but work on it was eventually abandoned because of the problems involved in controlling it. (The Orm was, in fact, three-dimensional.)

r

Jv I

Figure 11. The maximum radius r that can be reached by a planar rope mechanism while a tangent vector at a point on the rope is pointing in the direction opposite to the position vector. No inverse function can be defined on a disk of radius greater than r centered at the base of the mechanism. (Compare with Figure 10).

THEOREM 2.5: (see [10]) If a planar rope manipulator has total length L, a kinematic inverse function for it cannot be defined on the disk of radius r if r > L - 2"tr/K. Figure 11 shows the curlicue configuration that the manipulator will have to make at some point on the boundary of any disk on which an inverse function is defined. Note that the tangent vector at the apex of the loop points in the opposite direction of the vector from the base to the endpoint of the manipulator, in analogy to Theorem 2.4.

What Is the Significance of All This? It is natural to ask what impact these results will have on the robotics industry, and, without trying to give a definitive answer to this question, I would like to offer up a context in which it can be considered, and then indulge in some conjectures about what the future may hold. A l t h o u g h our list of solution m e t h o d s to local problems is by no means complete, it does leave the (correct) impression that this area has not yet reached the stage of a marketable technology. In fact, there are still many very difficult and unsolved problems involving the real-time processing of sensor informa-

Figure 12. A Stewart Platform, an example of a closed link mechanism. The platform is attached to a fixed base via six telescopic legs, which can be viewed as translational joints. By varying the lengths of the six legs, both the position and the orientation of the coordinate frame attached to the platform can be changed. Since, for any position and orientation of the platform, the leg-lengths are uniquely determined, an inverse kinematics map is well defined. It is not, however, one-to-one, because every position and orientation of the platform can be reflected through the plane of the base without changing leg-lengths. THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990 7 5

This condition will, however, be satisfied by all seriallink m e c h a n i s m s , i.e., ones w h o s e m e c h a n i c a l linkages contain no closed chains, and the large majority of robots being b u t t at this time are either seriallink mechanisms or can be modeled as such for the purposes of path-tracking problems. The design of robot mechanisms that are not serial-link is an area of active research, but it entails a number of problems b e y o n d the scope of this article, which must be resolved before such designs become commercially viable. Figure 12 shows an example of one such mechanism. It consists of a base and a movable platform, connected by six translational joints, or legs. As the lengths of these legs vary, the platform changes both its position and its orientation in R 3. The problem of motion control for such a mechanism takes on a very different character from the problems examined in the previous section. For example, as reported in [5], this nonredundant mechanism comes with an inverse kinematics map g : R 3 x S0(3) -* j6

verse functions pose hard implementation questions, and most engineers will probably shy away from them unless concrete help is available in dealing with these issues. It should, however, be noted that constructing inverse functions is basically an off-line job, so that we can afford to be generous in the computer resources we use. Only the later evaluation of the inverse function, as paths are being tracked, must be done on-line. I believe that the future of inverse functions in rob o t i c s d e p e n d s largely on t h e d e v e l o p m e n t of methods for constructing them. If such methods are not forthcoming, or if they turn out to be too painful in their implementation, it seems reasonable to assume that the engineering community will focus its attention on the d e v e l o p m e n t of non-cyclic tracking methods, ways to live with the non-cyclic behavior, or on just accepting singularities where they arise and learning h o w to work around them.

instead of a forward kinematics map. The function g also has singularities, but in singular configurations infinitesimal motions in the operational space are now possible, while the leg-lengths are held fixed. Note also that many paths in the operational space will result in leg collisions, so that one does not really have access to the entire operational space, even if the singularities are ignored. The reader is referred to [5] for further details. For the class of robot mechanisms admitting forward kinematics maps, the results that we have discussed seem to be mostly of a clarifying sort; they make some very precise statements about what cannot be accomplished, and what trade-offs must be dealt with. Specifically, it has been s h o w n that cyclic tracking algorithms are equivalent to ones determined by inverse functions, and we have seen a number of situtions in which inverse functions cannot be defined on the whole operational space. These statements serve only as a background for the real engineering work, which still remains. It would be useful to have a repertoire of methods for determining whether or not inverse functions can be defined on various subsets of the operational spaces of different robots, but, even more important, the engineer needs a collection of methods by which inverse functions can actually be constructed in specific situations. These inverse functions must ultimately be given in a form that makes them easy for a computer to evaluate in real time. Furthermore, the problem of optimizing the inverse function to obtain some sort of minimization of the ratios of joint speeds to speeds in operational space must be dealt with, and this problem is clearly no longer topological in nature. In contrast with many of the non-cyclic tracking methods which have been proposed, in-

1. John Baillieul, Kinematic programming alternatives for redundant manipulators, Proc. of IEEE International Conference on Robotics and Automation, March 25-28, St. Louis, MO (1985), 722-728. 2. Daniel R. Baker and Charles W. Wampler, On the inverse kinematics of redundant manipulators, International Journal of Robotics Research 7 (2) (1988), 3-21. 3. Daniel R. Baker and Charles W. Wampler, Some facts concerning the inverse kinematics of redundant manipulators, Proc. of IEEE International Conference on Robotics and Automation, March 31-April 3, Raleigh, NC (1987), Vol. 2, 604-609. 4. J. E. Bobrow, S. Dubowsky, and J. S. Gibson, On the optimal control of robotic manipulators with actuator constraints, Proc. of Automatic Control Conference, June 22-24, San Francisco, CA (1983), Vol. 3, 782-787. 5. E. F. Fichter, A Stewart platform-based manipulator: general theory and practical construction, International Journal of Robotics 5 (2) (1986), 157-182. 6. Daniel H. Gottlieb, Topology and robots, Proc. of IEEE International Conference on Robotics and Automation, April 7-10, San Francisco, CA (1986), Vol. 3, 1689-1691. 7. C. A. Klein and C.-H. Huang, Review of pseudoinverse control for use with kinematically redundant manipulators, IEEE Trans. on Sys., Man, and Cybernetics, Vol. SMC-13, No. 3 (1983), 245-250. 8. Ki C. Suh and John M. Hollerbach, Local versus global torque optimization of redundant manipulators, Proc. of IEEE International Conference on Robotics and Automation, March 31-April 3, Raleigh, NC (1987), Vol. 2, 619-624. 9. Charles W. Wampler, Inverse kinematic functions for redundant manipulators, Proc. of IEEE International Conference on Robotics and Automation, March 31-April 3, Raleigh, NC (1987), Vol. 2, 610-617. 10. Charles W. Wampler, Winding number analysis of invertible workspaces for redundant manipulators, Proc. of 26th IEEE Conference on Decision and Control, Dec. 9-11, Los Angeles, CA (1987), Vol. 1, 564-569.

76

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

References

Mathematics Department General Motors Research Laboratories Warren, MI 48090 USA

Chandler Davis*

The Poetry of Wallace Stevens (Excerpted from Holden's article "Poetry and Mathematics," The Georgia Review 34 (1985), 770-783.)

Comments by Jonathan Holden 9. . And how seriously can analogies between poems and "certain pages of algebra" be drawn? Are such analogies fun but trivial? To get at answers to these questions, let us consider some of the poetry of Wallace Stevens. Stevens was by far the most mathematically sophisticated of recent American poets. His poems regularly allude to mathematical ideas, affectionately imitate mathematical demonstrations, and apply language "'mathematically" to the world. The most obviously mathematical poem of Stevens is Anecdote of the Jar:

Here, the jar is the origin of a Cartesian coordinate system imposed upon the "wilderness" of a physical world u n m a p p e d in human terms. 2 Stevens is even careful to propose a vertical z-coordinate: the jar was "tall and of a port in air." And he is careful to remind us that the terms being imposed upon this "wilderness" are, like lines and points, wholly imaginary, wholly ideal, that this "jar" was "the only thing" in Tennessee which "did not give of bird or bush." Anecdote of the Jar doesn't actually set out to measure anything in particular. It is about the conditions for measurement of "wilderness." Measurement is done, Stevens tells us, by imposing u p o n the world constructions of the imagination, ideal structures, terms which can only be sustained through something akin to Coleridge's "willing suspension of disbelief that is poetic faith."

I placed a jar in Tennessee, And round it was, upon a hill. It made the slovenly wilderness Surround that hill.

Department of English Kansas State University Manhattan, KS 66506 USA

The wilderness rose up to it, And sprawled around, no longer wild. The jar was round upon the ground And tall and of a port in air.

Advanced Calculus of Murder by Erik Rosenthal New York: St. Martin's Press, 1988, 263 pp.

Reviewed by Mary W. Gray It took dominion everywhere. The jar was gray and bare. It did not give of bird or bush, Like nothing else in Tennessee. 1

If I w a n t conversation on a plane, I a n s w e r m y neighbor's inquiry of "What do you do?" with "I'm a lawyer.'" On the other hand, if I want peace and quiet

* Column editor's address: Mathematics Department, University of Toronto, Toronto, Ontario M5S 1A1 Canada Copyright 1923 and renewed 1951 by Wallace Stevens. Reprinted from Collected Poems of Wallace Stevens, by permission of Alfred A. Knopf, Inc.

2 IS it an accident or characteristic of Stevens' wit and attention to minutiae that the round mouth of the jar just happens to resemble the zero at the origin of a Cartesian coordinate system and the letter O of the word origin?

THEMATHEMATICALINTELLIGENCERVOL.12, NO. 1 9 1990Springer-VerlagNew York 77

Derek Jacobi as Alan Turing in

Breaking the Code

I reply, "I'm a mathematician." The union of those bored or intimidated by this response is virtually the universe. Some of us might seek a more interesting image for the mathematics professions, but we have had little in literature to which we may turn. A couple of seasons ago Breaking the Code, based on the life of Alan Turing, enjoyed London and New York stage successes surprising to many. This season Tom Stoppard followed up his m a t h e m a t i c i a n in Jumpers with a physicist in Hapgood who talks about the Koenigsberger bridge problem. Occasionally we have seen a mathematician as m u r d e r e r - - m o s t notably recently in Scott Turow's Presumed Innocent [1], although my favorite remains Michael Innes's Weight of the Evidence [2]. Usually, however, an academic setring for a thriller means that all the interesting people are in literature; similarly, film rarely brings us a mathematician, Jill Clayburgh providing an intriguing exception in It's My Turn. Now Erik Rosenthal brings us, in Advanced Calculus of Murder, a second installment of his mathematician-private investigator Dan 78

THE MATHEMATICAL INTELLIGENCER VOL. 12, NO. 1, 1990

Brodsky [3]. This time author, victim, murderer, and sleuth are all mathematicians. Lest you think this unfairly reveals the solution, let me say that the murder takes place at a math conference at Oxford with several hundred mathematicians as the only suspects. Rosenthal is good at recreating the atmosphere of such meetings and more generally that of the inbred world of mathematics research. Those who were at Berkeley in the 60s will recognize some of his fictional characters, and perhaps recall nostalgically Steve Smale's "flight to Moscow" to pick up a Fields medal and the resulting fallout from the story that his work was done on the beaches of Rio under an NSF grant [4]. At least the jet-set image is in some ways an improvement over the "nerd" image. A recent occupational survey, rating jobs on the basis of such things as working conditions, stress, pay, and security, put actuary, computer programer, computer analyst, statistician, and mathematician (in that order) at the top of the list; college professor fell in the ll4th place and migrant worker was the least desirable. I wonder how we would rate on glamour and excitement. A minor quibble with the author's setting the stage: trains from Oxford come into Paddington station, not Victoria. Keeping London mainline stations straight seems to be a problem that American mystery writers often have. Martha Grimes, otherwise a superb creator of English atmosphere, has had this difficulty. On the other hand, perhaps this is a device to see whether the readers are paying attention. As a mystery Advanced Calculus of Murder is not very successful--Rosenthal telegraphs the killer's identity rather early on. As an anthropological study of mathe-

matics, it is more successful. It is said that academics battle so viciously because so little is at stake; Rosenthal captures the sense of how trivialities can come to dominate the lives of mathematicians. Moreover, he reminds us all of the cyclic nature of mathematical employment. Again today there is a shortage of mathematicians, but Brodsky is a remnant of less happy days. His gypsy academic character is still found in great numbers in fields less in demand. Unable to get a "real job," he teaches part-time at Berkeley for a pittance, but unlike many of the exploited underclass of part-timers he keeps up his research and has found a

R o s e n t h a l c a p t u r e s the sense o f h o w t r i v i a l ities can come to d o m i n a t e the lives o f m a t h ematicians.

declarations by young girls and boys that they want to grow up to be mathematicians or to delight by mathematicians" seatmates at the prospect of vicarious glamour for the duration of the flight. John yon Neumann acquired a measure of public recognition, in which he is said to have taken naive delight, but he cannot be said to have generated an aura of excitement about mathematics as a profession. Sonia Kovaleskaia was, in the view of some of her contemporaries, a romantic figure--but in roles other than as a mathematician. We need a folk hero. Law school applications are said to be way up this year due to viewer interest in L.A. Law. Would that someone could make a similar splash with M.I.T. Math! The closest that mass culture has come recently is Stand and Deliver.

References creative means of supplementing his income. His work as a private investigator is generally not exciting, process serving and such being the mainstay. The subplot in Advanced Calculus of Murder of reuniting a young woman with the mother who gave her up for adoption takes Brodsky not very convincingly to the porno underworld and to Wales. He should stick to math conferences. Is there a way to make mathematicians more exciting, short of taking up murder? Allen Paulos's Innumeracy [5] has made the New York Times best-seller list, but unfortunately Paulos's work is unlikely to lead to

1. Scott Turow, PresumedInnocent, New York: Farrar Straus Giroux (1987). 2. J. I. M. Stewart (Michael Innes), Weight of the Evidence, London: Gollancz (1943). 3. Brodsky first appeared in Rosenthal's Calculusof Murder, New York: St. Martin's Press (1986). 4. The story was retold by Smale in "On the steps of Moscow University," Mathematical Intelligencer, vol. 6, no. 2 (1984), 21-27. 5. John Allen Paulos, Innumeracy, New York: Hill & Wang (1989).

Department of Mathematics and Statistics The American University Washington, DC 20016 USA

STATEMENT OF OWNERSHIP, MANAGEMENT, AND CIRCULATION (Required by 39 U.S.C. 3685). (1) Title of publication: The Mathematical InteUigencer. A. Publication No.: 03436993. (2) Date of filing: 10/1/89. (3) Frequency of issue: Quarterly. A. No. of issues published annually, 4. B. Annual subscription price, $30.50 (4) Location of known office of publication: 175 Fifth Avenue, New York, NY 10010. (5) Location of the headquarters of general business offices of the publishers: 175 Fifth Avenue, New York, NY 10010. (6) Names and addresses of publisher, editor, and managing editor:. Publisher. Springer-Verlag New York Inc., 175 Fifth Avenue, New York, NY 10010. Editor:. Sheldon Axler, Department of Mathematics, Michigan State University, East Lansing, MI 48824. Managing Editor: Springer-Verlag New York Inc., 175 Fifth Avenue, New York, NY 10010. (7) Owner: Springer Export GmbH, Tiergartenstrasse 17, D-6900 Heidelberg, West Germany;, and Springer-Verlag Berlin, Heidelberger Platz 3, D-1000 Berlin 33, West Germany. (8) Known bondholders, mortgagees, and other security holders owning or holding 1 percent or more of total of bonds, mortgages or other securities: none. (9) The p u ~ , function, and nonprofit status of this organization and the exempt status for Federal income tax purposes: has not changed during preceding 12 months. (10) Extent and nature of circulation. A. Total no. copies printed (net press run): Average no. copies each issue during the preceding 12 months, 6175; no. copies single issue nearest filing date, 6400. B. Paid circulation: 1. Sales through dealers and carders, street vendors, and counter sales: Average no. copies each issue during preceding 12 months, 597; no. copies single issue nearest to filing date, 654. 2. Mail subscriptions: average no. copies each issue during preceding 12 months, 4901; no. copies single issue nearest to filing date, 4980. C. Total paid circulation: average no. copies each issue during preceding 12 months, 5498; no. copies single issue nearest to filing date, 5634. D. Free distribution by mail, carder, or other means. Samples, complimentary, and other free copies: average no. copies each issue during preceding 12 months, 277; no. copies single issue nearest to filing date, 277. E. Total distribution: average no. copies each issue during the preceding 12 months, 5775; no. copies single issue nearest to filing date, 5911. F. Copies not distributed: 1. Office use, left-over, unaccounted, spoiled after printing: average no. copies each issue during the preceding 12 months, 284; no. copies single issue nearest to filing date, 358. 2. Return from news agents: average number of copies single issue during preceding 12 months, 116; no. of copies single issue nearest to filing date, 131. G. Total: average no. copies each issue during preceding 12 months, 6175; no. copies single issue nearest to filing date, 6400. I certify that the statements made by me above are correct and complete.

Ute Bujard Vice-President, Production

THEMATHEMATICALINTELLIGENCERVOL.12, NO. 1, 1990 79

* C o l u m n editor's a d d r e s s : Faculty of M a t h e m a t i c s , T h e O p e n University, Milton K e y n e s MK7 6AA E n g l a n d 80 THE MATHEMATICALINTELLIGENCERVOL. 12, NO. 1 9 1990Springer-VerlagNew York