No title

Farewell With this issue of the Mathematical Intelligencer I conclude my fiveyear term as Editor-in-Chief. Although it has monopolized a nontrivial portion of my time, no other mathematical publication could be as much fun to edit as the Mathematical Intelligencer. Where else could one entertain mathematicians by publishing expository articles about hot new developments along with the jokes, cartoons, poems, pictures, history, and controversy that have filled these pages? Thanks are owed to a large crowd for contributions to the Mathematical Intelligencer. Primary thanks go to the authors, the folks who wrote the wonderful material you've enjoyed in this publication. I read every paper submitted to the Mathematical Intelligencer during the last five years. Many articles were written because ! twisted someone's arm; others arrived unsolicited. Only a small minority of the submitted papers could be published--! tried to choose those that would most interest our readers. My most unpleasant duty as Editor-in-Chief was having to send rejection letters to many people w h o wanted to contribute to the journal. The Assistant Editor, European Editor, Mathematical Entertainments Editors, Reviews Editor, Stamp Corner Editor, and Years Ago Editors have all done a marvelous job. My thanks also go to the Correspondents, w h o were a good source of suggestions and advice. Springer-Verlag, publisher of the Mathematical Intelligencer, has provided extraordinary support. My agreement with Springer was that I and the column editors that I appointed would have complete control of the contents of the Mathematical Intelligencer, except for advertisements. Springer scrupulously adhered to this agreement, never pressuring me to stifle a controversy or suppress a review that might adversely affect Springer's interests as a commercial publisher of mathematics. Springer also graciously approved budget-busting practices such as color photographs inside the Mathematical Intelligencer (twice in my five years) and the inclusion of a phonographic record in one issue. The editorial and production staff at Springer deserve applause for the beautiful appearance of the Mathematical

Intelligencer. Starting with the next issue, a new Editor-in-Chief and a revised list of column editors and Correspondents will shape the Mathematical Intelligencer. I wish them success in their efforts to communicate important mathematics, and the mathematical culture that generates it, in an exciting fashion.

Sheldon Axler

THE MATHEMATICAL 1NTELLIGENCER VOL. 13, NO. 4 9 1991 Springer-Verlag New York

3

The Mathematical Intelligencer encourages comments about the material in this issue. Letters to the editor should be sent to the reviews editor, Chandler Davis.

Letters of Recommendation

In talking with colleagues, it seems that few have hit on the simple solution I use. To lay some claim for credit, I offer it here, amazed that no one else seems to have thought of it:

As an older member of the profession, I am asked to write many letters of recommendation. I suppose I write such letters for 20 or more people each year. Usually the subject is good or even excellent and I want to help. However, what should be a pleasant task often becomes a painful problem for several reasons:

I think it is necessary to add a few remarks:

1. It takes lots of time to study the requester's work. 2. I do not know how much he thinks of himself (please read " s h e " for "he" etc. here and below when necessary). This is essential input. Without it, I may think I am doing him a favor, but he expected more praise and I may actually be hurting him. 3. He may suspect I have damned him with faint praise and he and I will go on each knowing that there is a critically important and hidden question between us. He may find out someday by using the Freedom of Information Act that I changed the course of his life and I didn't even understand his best work. Somehow this almost makes me into a kind of KGB informant, especially if there is any doubt in my own mind about how strong a letter to write, which there usually is. 4. The above practice of damning with faint praise distorts language as the praise-metric keeps getting stronger. I really don't like faint praise. It's ambiguous and thus anti-mathematical. 5. Even more disgusting are clever phrases like, "his work fills a much needed gap," "he is in the upper 90% of his class," "he has struck out in many directions," or " y o u will indeed be fortunate if you can get him to work for you," all designed to be ambiguous. As a joke such phrases are fine, but I hope no one ever actually uses them (for an amusing selection of such phrases see LIAR: Lexicon of Intentionally Ambiguous Recommendations, by Robert Thornton, 1988, Meadowbrook).

a. I ask him to write exactly the letter he hopes I will write. If what he writes is close to what I can say in good conscience, I edit it a little to conform to my style, send it off and never show it to him. If I cannot be as full of praise as he wants, I look at his own supporting reasons that cite specific points in his own papers, and maybe change my mind. A serious problem arises if it's really a mismatch. I tone it down to something I can live with, and send it to him so that he can try to convince me that he is stronger than I think he is. If he succeeds, fine. If not, then I tell him that I don't see it his way. In this case, I have made an enemy for life, and this is the bad news in my idea. Nothing comes for free, but consider what I have gained: i. I have told him valuable information, for which he will, I naively hope, one day t h a n k me, namely, that the world has a different view and maybe he should change the world or his field. ii. I have avoided the problem that he might someday think I stabbed him in the back. But suppose there is this mismatch, what happens next? He has the option to ask me not to send it. This has never arisen, but if it did, I then plan to say that I will send it anyway if I am asked independently by the department or agency, etc., directly. Of course this would be awkward, but at least it would be clear.

4

I ask the requester to write his own letter.

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4 9 1991 Springer Verlag New York

TOPICS IN NONCOMMUTATIVE GEOMETRY Yuri L Manin Yuri Manin addresses a variety of instances in which the application of commutative algebra cannot be used

D-MODULESAND SPHERICAL REPRESENTATIONS Fr6d6ric Bien The theory of D-modules deals with the algebraic

to describe geometric objects, emphasizing the recent upsurge of activity in studying noncommutative rings as if they were function rings on "noncommutative spaces." This book is intended for mathematicians and physicists with some background in Lie groups and complex geometry.

aspects of differential equations. The book provides a general introduction to the theory of D-modules on flag varieties, and it describes spherical D-modules in terms of a cohomological formula. Using microlocalization of representations, the author derives a criterion for irreducibility. The relation between multiplicities and singularities is also discussed at length.

M. B. Porter Lectures, Rice University, Department of Mathematics

Mathematical Notes, 39

Cloth: $35.00 ISBN 0-691-08588-9

Paper: $22.50 ISBN 0-691-02517-7 In Japan order from United Publishers Services

Prln=ton UnirxrsityPress

PrincetonUni rslty Press

41 WILLIAM ST. 9 PRINCETON, NJ 08540 * (609) 258-4900 ORDERS: 800-PRS-ISBN (777-4726) OR FROM YOUR LOCAL BOOKSTORE

41 WILLIAM ST. 9 PRINCETON, NJ 08540 9 (609) 258-4900 ORDERS: 800-PRS-ISBN (777-4726) OR FROM YOUR LOCAL BOOKSTORE

Incidentally, often I am asked by the department directly without being asked by the individual. I then call the individual and inform him of the department's request and then I ask him to write the letter. This reduces the problem to the one previously "solved." If some departments will no longer ask me for letters now that they know my procedures, GREAT! I have always wondered why universities ask outside people, who may have many conflicts of interest they are not even aware of, to judge their own people, w h o m they know, or should know, much better. b. He must not be allowed to be modest. This is often a problem; most people are much too modest. To encourage bragadoccio, I like to point out that Einstein, annoyed at a display of false modesty, once said to a colleague, "You aren't good enough to be so modest!" I also say that ! will only turn the praise down, never up, so he must err on the positive side. It happened once that he refused to write his own letter. He said, "It is impossible for me." I argued

that it is not in my interest to have such a letter written, that it is he who should do the work, but to no avail. He refused. I like this fellow very much and finally I did it myself. I would only do this for that rare truly and consistently modest person. c. He must not be punished for immodesty. In case, and it has happened to me at least once, he writes a letter grossly exaggerating his qualities, I do not get mad at him for his immodesty, because he was provoked into this behavior. Instead, I turn up my praise a little, more than I would have in order to try to find a compromise. Thus, a negotiation takes place. I try to shoot down his arguments. I think both of us learn something from this exercise. d. I wouldn't say it's fun to write recommendations with this recipe, but it's the only way for a lazy fellow like me. Lawrence Shepp AT&T Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974 USA THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991 5

The Opinion column offers mathematicians the opportunity to write about any issue of interest to the international mathematical community. Disagreement and controversy are welcome. An Opinion should be submitted to the reviews editor, Chandler Davis.

The Association for Women in MathematicsmA Personal V i e w Mary W. Gray

Why should there be an organization for women in mathematics? In declining the invitation of the Association for Women in Mathematics (AWM) to deliver its annual Emmy Noether lecture, a promising young mathematician posed this question. Twenty years ago at a meeting of the AMS-MAA in Atlantic City a small group of w o m e n and men put it differently: w h y shouldn't there be? Anniversaries provide opportunities for retrospectives. A member of AWM (in fact, my husband) asserts that numbers like 10, 20, and 25 are uninteresting; however, now seems a good time to reflect on how far AWM has come from being operated from a file drawer in my study to an established office, with paid staff, travel grants and prizes for women mathematicians, and general recognition for its considerable achievements. Frustrated by the difficulties in getting jobs, the lack of women speakers at American Mathematical Society (AMS) meetings and at conferences, the dearth of women as officers or on committees of the AMS, w o m e n (and a few men) all over the country responded to the initial invitation to join AWM. From the beginning the agenda of AWM has been two-fold: to encourage more women and girls to study mathematics and to help women mathematicians professionally. When Alice Schafer took over as its second president, setting up the continuing AWM office at Wellesley, AWM began to be a secure, established presence on the mathematics scene. The AWM prize for an outstanding w o m a n undergraduate was established in Alice's honor. Alice has continued to be active in AWM through two retirements (one from Wellesley, one 6

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4 9 199I

Springer VerlagNew

from Simmons) and her new career as department chair at Marymount University; I've also stuck around, for the last ten years as General Counsel for AWM. In Jill Mesirov of Thinking Machines, Inc., AWM recently had its first president from outside academe. Because the AMS seemed to have a grip on mathematical life in the United States, at first a lot of attention was focused on the Society. Although it was not their intention, those who were officers of the AMS at the time provided inspiration. I had decided to go to a Council meeting to see what went on. The president

York

Left to right: Rhonda Hughes, former AWM president; Shirley M. Frye, recipient of the first Louise Hay Award for Contributions to Mathematics Education; Mary Gray; Jill Mesirov, AWM pastpresident.

met me at the door to tell me that the meetings were not open to the membership. Having done a little research, I replied that the By-laws of the AMS did not specify closed meetings. "Oh," he replied, "it's a gentlemen's agreement." As I'm no gentleman, I stayed put. Ever since, the meetings have been open. Little did those of us pushing for openness realize how deadly dull AMS Council meetings could be. We did liven them up occasionally: we brought about n o m i n a t i o n b y p e t i t i o n for the C o u n c i l , vicepresidencies, and the nominating committee. In the early days many of the AWM activists came out of the civil rights and anti-war movements, including the mathematics version, Mathematics Action Group (MAG). We all got tired of licking envelopes while men took leadership roles. Nevertheless, those w h o m AWM helped elect to the AMS Council generally allied themselves with those working on broader social issues. An early small triumph was getting the reciprocity agreement with the South African Mathematical Society cancelled. The reception of AWM activists by the AMS Council was at first not always cordial, but I think we generally gave as good as we got. As a newly elected vicepresident I remember introducing myself across the table to a fellow Council member who said: " O h yes, I voted for your opponent." What to say but "That was an error in judgment on your part." At another Council meeting during my term as vice-president, the President of the Society appeared wearing a tie popular at the time. The pattern was neatly embroidered pigs with "MCP" (male chauvinist pig) under each. As he leaned across the table so that the tie dangled in my

Three former AWM presidents are left to right: Bhama Srinivasan, Rhonda Hughes, Linda Rothschild.

face, I asked "Would you wear a tie that said 'I am a white supremacist'?" To his negative reply I responded: "So w h y the 'MCP'?" An incontrovertible answer came back: "Women are different; we live with them." Eventually we succeeded pretty well with the AMS itself. We got more w o m e n speakers, more w o m e n committee members (on committees other than the one on w o m e n that had been created early on in a futile attempt to keep us quiet), w o m e n elected to the Council, vice-presidency and even (once) the presidency. Many of these w o m e n were distinguished mathematicians who had been around for years, but somehow had just been overlooked by the establishment. Thanks to the wonderfully supportive meetings staff, AWM got space to set up recruiting tables and slots on the programs of the joint mathematics meetings. We pioneered panels on employment issues such as careers in government, business, and industry and on the history of mathematics, and presented specialized discussions on managing two-career families and on mentoring. Long before the other mathematical organizations established a presence in Washington, AWM was lobbying and even participating in amicus briefs. Mathematicians crowd the annual Emmy Noether lectures, directed at a general mathematical audience with the speakers being selected because they are good expositors as well as good mathematicians. AWM parties are always well populated, frequently by those who were its most vociferous opponents early on. We always welcome warmly even belated converts. Some are incorrigible, however. At a panel at a 1990 AMS meeting, a well-known emeritus member of a distinTHE MATHEMATICAL 1NTELLIGENCER VOL. 13, NO. 4, 1991

7

guished mathematics department offered as a reason for not hiring w o m e n the fact that his department had once (about 50 years ago) had a w om a n faculty member but that her research was not very good and besides she had trouble placing her students in good jobs! It used to be that there was rarely more than one woman at a specialized conference, but things have changed a lot. In fact, a conference on forensic statistics last year marked the first time in years that I found myself the only speaker on the program. AWM has had its own conferences--on Emmy Noether at Bryn Mawr and Sonya Kovaleskaia days in Boston--and this year sponsored a panel at the annual American Association for the Advancement of Science meeting, focusing on areas of mathematics that have public policy implications. There have been offshoots of AWM---the Association for Women in Mathematics Education and the European Women in Mathematics--working for essentially the same goals. Certainly there are countries where women in mathematics have had even a harder time than in the United States. Although there are relatively few faculty who hold the rank of professor in Britain, it is still shocking that, to my knowledge, there has never been a w o m a n professor of mathematics there; the situation in Germany is not much better, but in France, Italy, and some d e v e l o p i n g countries w o m en professors have not been so rare. AWM has become a regular presence at International Congresses of Mathematicians (ICM), but it took until 1990 to get any reasonable representation of women mathematicians as invited speakers. An AWM highlight was a memorable panel of w o m e n mathematicians at the 1978 Helsinki meeting. I w o n d e r what has happened to the Soviet woman who explained how good things were for women, neglecting to mention that queuing for food, cooking, cleaning, and many other chores still seem to be reserved for women, no matter how good their mathematics might be. Lest we in the United States seem complacent, let me recall another vivid m o m e n t at an AWM panel w h e n an indignant young French mathematician spending a year at Princeton asked how w om en in America could be expected to prove theorems w hen there weren't any decent provisions for childcare. To balance that and to show that p e r h a p s mentoring is b r o a d e r than we think, I remember fondly one of my Ph.D. students from a Middle Eastern country telling me how he pulled the shades so that the neighbors would not see him the first time back home that he did the dishes. Not that all the battles are won. The country's leading m a t h e m a t i c s d e p a r t m e n t s h a v e few t e n u r e d w o m e n on the faculty and AMS meetings and the ICMs still have too few w om en in prominent roles. The National Academy of Sciences seems unable to move beyond one w o m a n mathematician at a time. The head 8

THE MATHEMATICAL INTELLIGENCER VOL. I3, NO. 4, 1991

of the mathematical sciences section of the National Science Foundation (NSF) is a woman; it would be nice if the head of the whole NSF or the President's science advisor were a woman mathematician. Sometimes one is able to nudge a little; a few years ago I was on an accreditation review panel for Harvard. When asked w h o m I wanted added to the list of interviewees, I proposed to speak with the person in charge of affirmative action; it turned out that this official was lodged up in the attics and was as amazed as those setting up the interviews that anyone would want to see her. In addition to making recommendations in that area, our accreditation report strongly urged the addition of a mathematics requirement for all Harvard and Radcliffe undergraduates; I got calls about that from the Harvard Crimson for months afterward. The downside of that a d v e n t u r e was s p e a k i n g w i t h an u n d e r g r a d u a t e w om an mathematics major w ho related the sense of isolation and lack of encouragement that were turning her away from the field. There are those who claim that affirmative action has led to widespread hiring of underqualified w o m e n and minorities at the expense of better qualified white males. I do not doubt for a m o m e n t that some departments have taken misguided actions in the name of affirmative action; many more have told disappointed white male candidates that they were not hired because of affirmative action requirements w hen in fact they were simply not the best qualified. Because some have tried to use AWM to pretend to engage in affirmative action, we have always refused to provide our mailing list to non-members. But many an AWM member listed in the AMS membership directory has routinely received letters inviting her to apply for anything from a temporary lecturer position at Podunk U to an endow ed chair at a prestigious university; perhaps the departments who send out such letters are fooling their institutions' affirmative action officers, but they are not engaging in any real affirmative action. Then there are the p h o n e calls like the one I received a number of years ago w h e n I was chairing what at that time was a math, stat, and computer science department. It seems that the caller, from a state university in Texas, was hunting for a w om a n for a faculty position in artificial intelligence; he also mentioned that he was hunting for African-American or Hispanic faculty and would really like a "two-fer" because "those kind of people don't fit in very well with the folks in our department so it would be better if we could get by with just one." I managed to restrain m y thoughts about his department's need for intelligence of some kind. An "old girls network" has arisen because w o m e n mathematicians know one another through AWM, and sometimes this network gets linked into the "old boys network" when jobs open up, or more often w h e n committee positions that take a lot of work and get

little recognition are open. Mathematicians mentoring promising women undergraduates also use their contacts to seek out departments with graduate faculty known to be hospitable to women students. The long period of uncertainty encountered in graduate programs, followed by the anxiety of pre-tenure years, makes pursuing a Ph.D. a less attractive option than law school or an M.B.A. program for many talented women and men. That this time span coincides with prime childbearing years for women is a complicating factor that has spurred discussion within AWM and elsewhere of whether reform in the regime might not be in order. Although the percentage of Ph.D.s in mathematics going to women has risen from the six percent that prevailed from the 1930s through the mid 1960s to around twenty percent, there was a slight decline last year. Moreover, the increase in percentage represents an essentially constant number of women and a concomitant fall in the number of men. What is worse, African-American and Hispanic-American w o m e n (and men) are very scarce among mathematicians. AWM has had a panel on African-American women mathematicians and often works in cooperation with t h e National Association of Mathematicians on problems of attracting and retaining minorities in the field. The issue of mentoring is a long-standing problem. At the time AWM began, there were a few senior women mathematicians around. (Not including me--I was an untenured associate professor only six years beyond my degree. I have not been around forever even though one of my calculus students last fall asked me whether I had been a suffragette--oh well, at least he had heard of suffragettes.) For the most part these women had not seen the mentoring of other women as part of their roles. In fact, just as for many years a substantial portion of African-American Ph.D.s in mathematics had been mentored by Lee Lorch (an early AWM member), a fair number of women mathematicians could be traced to Lipman Bers and the late I. N. Herstein. Many w o m e n mathematicians have consciously tried to avoid identification with AWM and issues of equity in general, whether because of lack of confidence in their own accomplishments, an indifference to helping other women, or just a focus on other priorities. AWM itself has emphasized the importance of helping the next generation by establishing an award for contributions to the education of mathematicians; it is named in memory of Louise Hay, who would have become president of AWM if not for her untimely death and who was the mentor of Rhonda Hughes, a former AWM president. That many have a certain ambivalence about AWM is understandable. Most of us want to be known as mathematicians, not as women mathematicians or still less as " w o m e n libbers," whatever that is supposed to mean. Young or even established mathematicians may

/

[{"

"

-lre_:mFor,~r

"'Yes, we do have something in condensed matter theory and astro-par~cle physics. Can you type?"

9 1989 by Sidney Harris--American Scientist Magazine

fear that association with the goals of AWM will hurt them professionally, make them appear less than serious about their research. Moreover, there is a strong inclination to discount the scientific accomplishments of activists of any stripe, except for the achievements of a handful at the very pinnacle; even they frequently took up their causes only w h e n their place at the top was secure. The indoctrination we all get early on that there is nothing as important as "good mathematics" (meaning recognized mathematics) sticks tenaciously with most of us. Let me illustrate. Before I gave up algebra years ago to take up statistics (and eventually law) because it appealed to me as more socially useful, I wrote a book on ring theory called A Radical Approach to Algebra. (It sold better than most m o n o g r a p h s because some thought it was a Marxist interpretation.) A few years ago I was shuttling from a conference at the New York University law school to Boston for a planning meeting for another conference. I had forgotten to remove my name tag, and the young m a n - - w h o looked about sixteen--sitting next to me asked, "Are you the Mary Gray?" How to answer? Shortly before I had spoken on economic equity issues on television several times, including on the MacNeil-Lehrer show, but I doubted that I had achieved a status triggering such a reaction. While I searched for something to say, he continued, "The one who wrote the ring theory book?" It turned out that he was a graduate math student at Harvard. Although I had not thought about the book for ages, after his comment I didn't need the plane to fly the rest of the way. The issue of mathematical reputation has been a sensitive one within AWM itself. Strong research credentials have generally been thought necessary for candidates for the presidency, but many question whether that is the best criterion for leadership and assert that AWM has unthinkingly adopted the standards of the THE MATHEMATICAL INTELL1GENCER VOL. 13, NO, 4, 1991 9

%~n excellent defense, Let's give her the doctorate." Drawing by Handelsman; 9 1987 The New Yorker Magazine, Inc.

establishment. No doubt this is a controversy that will continue; in fact, the establishment itself might benefit from questioning whether the selection standards it has used have always led to the most effective leadership for mathematics as a discipline and as a profession. This year Amnesty International is organizing a campaign specifically focused on h u m a n rights abuses against women. AWM is way ahead on this issue also, for many years having concerned itself with the human rights of w o m e n mathematicians. AWM members tried to get some of these cases addressed by the AMS; I recall that at one Council meeting the disappearance of an Argentinean w o m a n , a graduate student in mathematics, was brought up. Certain Council members wanted to know what theorems she had proved that would entitle her to attention by the mathematical community; to be fair, in those years the same objections were sometimes raised when it was suggested that the AMS take action on behalf of men mathematicians. Many Soviet w o m e n mathematicians who were denied employment and/or the right to emigrate have been the subject of AWM concern, as has a Nicaraguan woman who we feared would not be allowed to attend the ICM at Berkeley and Chinese women imprisoned for pro-democracy activities in 1989. Presently a woman who formerly chaired the mathematics department at Bir Zeit University is being kept from practicing her profession by the more-than-three-year 10

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

closure of Palestinian universities. (She was also the subject of previously expressed concern by the mathematics community when she personally was barred from her position.) I do not know whether any of the Saudi academics who were fired for driving cars are m a t h e m a t i c i a n s , but C e a u s e s c u ' s m a t h e m a t i c i a n daughter sought help from Alice Schafer, who chairs the AMS Committee on the H u m a n Rights of Mathematicians. Controversy over how best to deal with h u m a n rights violators broke out last year in AWM. AWM had decided to sponsor a tour to China to meet with women mathematicians there; as the tour was scheduled for close to the time of the events of Tiananmen Square, it was postponed. When the tour was rescheduled for the summer of 1990, many AWM members, particularly those with students who had been involved in the emerging democracy movement, felt that AWM should withdraw its sponsorship. Echoing the discussions that occurred for many years in the AMS Council, others argued just as strongly that keeping lines of communication open was important and that in any event the women mathematicians to be visited were not responsible for the repressive violence of the Chinese government. Still others believed that the most useful approach was to go to China and seek to raise h u m a n rights issues with appropriate officials. Ultimately AWM withdrew its official sponsorship, but most of those scheduled to go went as an independent group. Although AWM has had an external mission in its efforts to attract more women and girls to mathematics, it has not had the goal of transforming the curriculum that has preoccupied many women's caucuses or independent groups. There has been an interest in spotlighting the accomplishments of m a n y littlek n o w n w o m e n mathematicians, but people h a v e - perhaps u n f o r t u n a t e l y - - n e v e r been central to the study of mathematics. AWM members are alternately told that theorems have no gender and asked what feminist mathematics is. The question belongs in part to the discourse about whether, for its own good, science needs to undergo a feminist transformation. Major work on this aspect of mathematics has been done by a group of French feminist mathematicians, but the philosophical discussion has not become prominent within AWM itself. A more manageable question than whether the nature of mathematics is masculine, and if so whether it can or should be altered, is whether women are attracted to particular fields within mathematics. If the left brain-right brain gender-difference theorists are correct in their claim that w o m e n are generally less capable in the visual-spatial arena, one would expect women generally to avoid certain aspects of topology and geometry. In a survey done ten years or so ago, it was discovered that women were overrepresented in

I

algebra and underrepresented in applied mathematics. However, more recently the distribution of women across fields appears to be more uniform. The earlier concentration in algebra could, of course, have causes other than those centered in hemispheric-dominance theory--the presence of particularly helpful advisors or the inspiration of Emmy Noether, who, until AWM h e l p e d publicize the a c c o m p l i s h m e n t s of other women, was probably the only woman mathematician whose name most mathematicians would recognize. In fact, early in the history of AWM, when the acronym stood for the Association of Women in Mathematics, it was suggested that the name be changed to the Emmy Noether Society. The mathematics curriculum has not entirely escaped AWM's attention. A number of years ago a popular textbook for finite mathematics used the relationship between bust size and IQ as an example of negative correlation. A polite letter from an AWM member to the author was not well received. As it turns out there were AWM members in charge of large enrollment finite mathematics courses at many institutions. As adoptions of the offending text fell off, the publisher's field representatives sought an explanation. The next edition appeared without the objectionable example. At one time the diagnosis of "math anxiety" was being used by many as an excuse to shield women from the study of mathematics. Many AWM members designed special courses based on the theory that the best way to dispel anxiety about mathematics was to learn to do mathematics. Although the merits of gender-segregated mathematics classes--indeed of gender-segregated education--will continue to be debated, AWM members have generally been willing to try almost anything to proselytize for mathematics. The strength of AWM has, ! believe, been its broad focus. We have had a speakers bureau for many years, and our members have been active in outreach to community groups as well as to junior high schools, high schools, and colleges. Members spend many hours consulting with w o m e n ranging from the high school student wanting to do a paper on a woman mathematician, to the woman wanting to return to college and worrying about future job prospects, to the woman facing a struggle for tenure. AWM is one of the strongest of the disciplinary organizations for women, probably partly because of our minority status in the field. There are few enough of us that we tend to know one another, and we feel the need to join together. The office, the staff, the NSF and foundation grants are stabilizing features, but it is our spirit that keeps AWM vital.

Mathematics Department American University Washington, DC 20016 USA

II

Ein Jahrhundert Mathematik 1890-1990 Festschrift zum Jubil ium der DMV Edited by Gerd Fischer, Friedrich Hirzebruch, Winfried Scharlau und Willi T6rnig 1990. xii, 830 pp. Hardcover DM 198.-; US$142.00 ISBN 3-528-06326-2

The year 1990 marks the 100th anniversary of the DeutscheMathematiker-Vereinigung, the German Mathematical Society. The book contains nineteen contributions covering the development ofthe main fields of past hundred years mathematics in Germany. Special attention should be given to the first contribution: a critical description of the history of mathematics and mathematicians during the Third Reich period. Contents: Norbert Schappacher unter Mitwirkung von Martin Knesec Fachverband - Institut - Staat / Martin Aigner" Diskrete Mathematik / Friedrich L. Bauer: Kurzer AbriB der Geschichte der Informatik 1890-1990 /Josef Bemelmans, Stefan Hildebrandt, Wolf von Wahl: Partielle Differentialgleichungen und Variationsrechnung / Walter Benz" Grundlagen der Geometrie / Lothar Collatz: Numerik / Peter Dombrowski: Differentialgeometrie / Dieter Galen 0ber die Entwicklung der Funktionentheorie in Deutschland von 1890 bis 1990 / Peter Manfred Gruben Zur Geschichte der Konvexgeometrie und der Geometrie der Zahlen / Ulrich Krengeh Wahrscheinlichkeitstheorie / Rolf Leis: Zur Entwicklung der angewandten Analysis und mathematischen Physik in den letzten hundert Jahten / Gerhard O. Michler" Vom Hilbertschen Basissatz bis zur Klassifikation der endlichen einfachen Gruppen / JElrgen Neukirch: Algebraische Zahlentheorie / Samuel J. Patterson: Erich Hecke und die Rolle der L-Reihen in der Zahlentheorie / Albrecht Pfistec Quadratische Formen / Hans-Wemer Henn und Dieter Puppe: Algebraische Topologie / Kurt SchE#te und Helmut Schwichtenberg: Mathematische Logik / Wolfgang Schwarz: Geschichte der analytischen Zahlentheorie seit 1890 / Hermann Witting: Mathematische Statistik

Verlag Vieweg 9R O. Box 58 29. D-6200 Wiesbaden. Germany

In the USA and Canada represented by: Ballen Booksellers International, Inc.. Dept.Vieweg 125 Ricefield Lane. Hauppauge NY 11788.Telex 9103 800 079 Fax (516) 864-5850. Phone (516) 543-5600 Call toll free: 1-800-645-5237

meweg THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

11

Karen V. H. Parshall*

Edmund Landau's G0ttingen: From the Life and Death of a Great Mathematical Center Norbert Schappacher

Talk at the Dedication of The Edmund Landau Center for Research in Mathematical Analysis** in Jerusalem, 28 February 1989 Dear Mr. President, Ladies and Gentlemen. Edmund Landau lived from 1877 to 1938, 61 years almost to the day. He was born and died in Berlin. His father, Leopold, was a gynecologist; his mother (Joh a n n a , n6e Jacoby) came from a very well-to-do banker's family. The Landaus lived in the Jacobys' house, situated in the most elegant quarter of Berlin. The street address was Pariser Platz 6a, close to the Brandenburg gate. The famous painter Max Liebermann was soon to have his studio in a house near by. Like many assimilated Jews in Berlin at the time, the father was a German patriot. But he also actively promoted Jewish traditions. Thus he was involved in the founding, in 1872, of the Hochschule fiir die Wissenschaft des Judentums--an academy of Judaism in Berlin. Both the German and the Jewish cause would be close to the heart of Leopold's son Edmund as well. In particular, E d m u n d Landau became an active supporter of the Hebrew University in Jerusalem. He gave a mathematical lecture--his first in H e b r e w - - a t the opening of the Hebrew University, on 1 April 1925. And during the winter term 1927/28 he took a sabbatical from GOttingen University in order to start mathematical t e a c h i n g here, with two courses, one on number theory and the other on principles of analysis.

As I learned from correspondence in the archives of the H e b r e w University, L a n d a u even c o n s i d e r e d s t a y i n g p e r m a n e n t l y at Jerusalem. Incidentally, Landau was the only GOttingen mathematician who, in our century, was a member of the synagogue community in GOttingen. Let us not jump ahead, but go back to the early years of Edmund Landau. He was intellectually precocious. He graduated from the French lyc~e in Berlin at the age of 16, some two years earlier than usual, and immediately entered Berlin University as a student. His clear preference for mathematics showed fairly soon. Also it must have been very early on that he

* 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 E d m u n d Landau Center at the D e p a r t m e n t of Mathematics of the Hebrew University at Jerusalem is s u p p o r t e d by the Federal Republic of Germany.

12 THE MATHEMATICALINTELLIGENCERVOL. 13, NO. 4 9 1991 Springer-VerlagNew York

developed the sense of duty and precision that characterized his later career. When David Hilbert learned of Landau's death, he succinctly characterized Landau as the "'Pflichttreueste von uns a l l e n " - - t h e one with the greatest sense of duty among all his colleagues. We shall have occasion to see what Hilbert meant. L a n d a u ' s f o n d n e s s for intellectual g a m e s and puzzles, illustrated by n u m e r o u s later anecdotes, shows already in his first two publications preceding his Berlin dissertation; both deal with mathematical problems related to chess. In July 1899, at the age of 22, Landau received his doctorate on the basis of his first number-theoretic work. It is also the first of a large number of publications in which Landau managed to shorten substantially the proof of a result previously established by some other mathematician. Both his doctorate and the next academic degree only two years later, the Habilitation, by which the candidate obtained the right to teach mathematics courses at Berlin University, were given to Landau without hesitation, but also without any indication by the professors i n v o l v e d - - a n d in particular Georg F r o b e n i u s - - t h a t Landau was outstanding. In fact, Frobenius's evaluation of Landau's work on the occasion of the Habilitation in 1901 concludes with the admonition that Landau should cease to concentrate on this "extremely narrow subject" of analytic number theory! A similar remark, again due to Frobenius, is to be found in a 1917 relative evaluation of Landau and Issai Schur. There the point is m a d e that the majority of L a n d a u ' s publications would lose all their value the day that "a certain hypothesis of Riemann" was proved. This hypothesis, h o w e v e r - - a s m o s t of y o u k n o w - - h a s n o t b e e n proved to date. Right from his dissertation, there was a continuous and ever-growing flow of publications by Landau. As of January 1900, he communicated his new findings to David Hilbert, the greatest German mathematician of the time. In 1904, the n u m b e r of his publications started to exceed his age (27). Soon afterwards, no other German mathematician in the same age bracket could have competed with Landau's impressive list of publicationsdr In addition to his relentless publishing, Landau quickly proved to be an extremely successful teacher at Berlin University. He agreed to teach beginners' courses from time to time, even though such was not his duty as a Privatdozent. And he was among the first mathematicians in Germany to teach courses outside

t The complete papers of Edmund Landau have recently been published: Edmund Landau, Collected Works, Thales Verlag, Essen. This collection of Landau's papers also contains the photographs that are published with this article. Permission from Thales Verlag to publish these pictures here is gratefully acknowledged.

Edmund Landau.

his specialty, the analytic theory of numbers, on foundational topics, such as irrational numbers and set theory. This, as well as the pains-taking perfectionism with which he prepared his lectures and the enthusiasm with which he delivered them, accounted for the highly impressive s t u d e n t a t t e n d a n c e of his classes. There can be no doubt that Landau remained an inspiring lecturer thoughout his life. However, later on, especially in the 1920s, there was also criticism of too much formal rigidity in his style of presentation. And it should also be said that he tended not to have cordial relationships with his students, being rather an aloof person. THE MATHEMATICALINTELLIGENCERVOL. 13, NO. 4, 1991 13

Twice the Berlin F a c u l t y - - w h o by now had realized what an asset this young man was for t h e m - - t r i e d to secure a formal position for Landau beyond the mere right to teach courses. The first time, in 1904, this resulted only in the title of Professorfor Landau without a n y c o n t r a c t or r e m u n e r a t i o n . The s e c o n d time around, in 1908, the Ministry flatly denied the attempt of the Befliners to keep Landau and agreed instead to make him Ordinarius--full professor--at G6ttingen, as successor to Hermann Minkowski, who had suddenly died from a ruptured appendix at the age of 44. This move in favor of G6ttingen must be seen as part of a program initiated some twenty years earlier by the Prussian administrator Friedrich Althoff and put into action in close collaboration with Felix Klein at G6ttingen. The idea was to make G 6 t t i n g e n the stronghold of mathematics and sciences in Prussia, whereas the humanities were to be emphasized more in Berlin. Thus, Hilbert and Minkowski had been drawn to G6ttingen, the latter to a chair newly created for the occasion.

On the big continuous rolling blackboards in the lecture halls of the new GiJttingen Mathematics Institute built in 1929, Landau apparently tried to arrange longer proofs in such a w a y that the final conclusion of the proof would end up after a full turn of the board, right above the statement of the theorem. There are a number of apocryphal stories about how Landau was chosen by the G6ttingen faculty as successor to Minkowski. Most of them must be inaccurate, because they do not even give the correct names that were proposed, namely in alphabetical order: Blumenthal, Hurwitz, Landau. Note in passing that all three candidates were Jewish. Such an all-Jewish list of candidates would not have been acceptable at many other German universities at that time. Who chose L a n d a u - - w h e t h e r this was decided at G6ttingen or in the M i n i s t r y - - I do not know. When accepting the offer, Landau thanked both Klein and Hilbert in separate letters for what they had done for him. But the letters show that he, too, was not sure of who had done what. The Landaus settled at G6ttingen and soon had constructed for themselves a beautiful, luxurious mansion in English Cottage style at what was then the eastern edge of the town of G6ttingen, close to the woods. Edmund Landau had married Marianne Ehrlich at Frankfurt-am-Main back in 1905. Her father, Paul Ehrlich, h a d been a colleague and friend of Landau's father. Ehrlich won a Nobel prize in 1908 for his work in immunology. (Considering that a Paul14

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

Ehrlich-Institute for Immunology has recently been created here at the Hebrew University, today's occasion does not lack a certain family aspect.) The young couple could look forward to a financially easy life. There were going to be two daughters and one son, not counting a first son who died at the age of 5. Landau stayed in G6ttingen until November 1933, when he was forced out by the Nazis because he was Jewish. In a way, these almost twenty-five years that Landau spent in G6ttingen, 1909-1933, form a unity because of the uninterrupted continuity of Landau's work. In the first place, he p r o d u c e d a steady flow of papers and textbooks, some of them famous. Secondly, his courses were, of course, taught every term. And here Landau kept the promises of the y o u n g Berlin Privatdozent. His lectures were getting increasingly perfectionistic. For instance, on the big continuous rolling blackboards in the lecture halls of the new G6ttingen Mathematics Institute built in 1929, Landau apparently tried to arrange longer proofs in such a way that the final conclusion of the proof would end up after a full turn of the board, right above the statement of the theorem. One of his assistants had to sit in his lectures, especially beginners' lectures, to make him immediately correct mistakes that might occur in spite of the conscientious preparation. And thirdly, Landau accepted a great number of research students: twenty-seven received their doctorates in G6ttingen under his guidance. Landau recognized Carl Ludwig Siegel's outstanding qualities and led him to a reasonable presentation of his thesis. Even though Landau's activities appear as one unity all through his stay at G6ttingen, G6ttingen did of course change and develop while Landau was there. When Landau came to G6ttingen, this was still the G6ttingen of Klein and Hilbert. Then, whereas Hilbert stayed on through 1930, Klein, thirteen years older than Hilbert, formally retired in 1913, and was less and less present as the organizer he had once been. He died in 1925. As successor to Klein, Hilbert and Landau attracted the function theorist Carath6odory. " C a r a " - - a s he was commonly called--came to G6ttingen in 1913, but did not stay even three years. Then came the brilliant analytic number theorist Hecke. But right after the War, in 1919, Hecke accepted an offer from the newly founded Hamburg University. The definite successor to Felix Klein was then found in Richard Courant, whose extraordinary talents as an organizer actually made him the right candidate to carry on this part of Klein's legacy. Courant was not altogether to Landau's liking, both for his mathematical specialty (mathematical physics) as well as for the somewhat relaxed style of exposition in his courses. Instead of Courant, L a n d a u had proposed for the chair the algebraist Schur, a former colleague from

Berlin. But Klein and Hilbert preferred Courant. Apart from Hilbert, Landau, and Courant, the mathematical chairs at G6ttingen were occupied by: 9 the a p p l i e d m a t h e m a t i c i a n Carl D a v i d Tolm6 Runge. He retired in 1924, and was then succeeded by the Austrian pure mathematician Gustav Herglotz; 9 the statistician Felix Bernstein, who more and more leaned towards applied research in medicostatistics, and at least for that reason was not close to Landau. Last, but certainly not least, Emmy Noether has to

be mentioned: the greatest woman mathematician to date and one of the founders of modern abstract algebra. Solely because of her sex, she did not have any position at the university with civil-servant status. Even to grant her the Habilitation had been possible only after long and serious fights by mathematicians against the majority of the Philosophische Fakultfit during World War I. During the 1920s, a very good collaboration developed between Noether's group of advanced students and Landau's research students. Since Noether did not formally have the right to pass a student on to the doctorate, it was usually Hilbert or Landau who stepped in as official thesis adviser.

From left to right: Henri PoincarG GOsta Mittag-Leffler, Edmund Landau, and Carl Runge. (From the Collected Works of Edmund Landau, vol. 2, Thales Verlag, Essen. In the forthcoming vol. 10, additional biographical material and many photographs are published.) THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

15

Having m e n t i o n e d the applied m a t h e m a t i c i a n s Runge and Bernstein, let me say one word on the broadness of the mathematical-scientific center at G6ttingen, a side of it in which Landau did not take interest. Klein, Hilbert, Minkowski, Noether, Courant, then after 1930 Hilbert's successor Hermann W e y l - all of these mathematicians were, at least for some time in their careers, interested in the development of physics. And G6ttingen physics--with the two Nobel laureates Max Born and James Franck, as well as young men like Heisenberg--left nothing to be desired. Furthermore, there was not only the contact with theoretical physics but, as the most remarkable if belated result of Felix Klein's efforts to associate even engineering applications with the university, Ludwig Prandtl's Experimental Institute of Aerodynamics became operational in 1917. There was close contact between Prandtl and the Mathematical Institute at least as long as Courant was director of the latter, i.e., until spring 1933.

The glory of G6ttingen could also cause grief to those who did not work there. What made G6ttingen probably the most eminent center of mathematics in the w o r l d - - u n t i l 1933--was the unrivaled inspiring atmosphere among the numerous young mathematicians who flocked to G6ttingen from everywhere. This is a hard thing to pin down exactly in a general o v e r v i e w - - a n d it is an easy thing to destroy by altering the overall conditions of work,

After Landau had turned down an offer of a chair in Heidelberg in 1913, the G6ttingen mathematicians celebrated this success by a party at which Hilbert gave a speech which ended with the words: Since the mathematical sciences are so vast and varied, it is necessary to localize their cultivation, for all human activity is tied to places and persons. G6ttingen is a place which--favoured by tradition, by the cooperation of our Prussian government, and by a series of other favorable circumstances--has become a preferred center of mathematical science. By your decision, you [Landau] have shown that you, too, favor this place. We are most grateful for this. And the best way to show our gratitude is by a continuing, enthusiastic collaboration in our mathematical science. Thus in future histories of G6ttingen it should read: Gauss, Riemann, and Klein--those were individual summits rising into the clouds. But then, around the time that Landau came to G6ttingen, there started a period of general mathematical high culture; from G6ttingen mathematics launched a new conquest into the universe of science . . . . Let me add that the glory of G6ttingen could also cause grief to those who did not work there. Apparently it happened more than once that new results by others were talked about in G6ttingen seminars, and 16

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

then people from G6ttingen quickly developed them further, forgetting about the creator. This process was euphemistically termed the "nostrification" of an idea. The palpable realization of the glamour of G6ttingen mathematics was the construction, finished in 1929, of a grand new building for the Mathematical Institute financed by the Rockefeller Foundation. Two mathematical institutes were t h u s built in Europe with American money in the 1920s; a few years before G6ttingen, the Institut Henri Poincar6 in Paris. Let us now change our perspective of Landau's G6ttingen and turn to the major political e v e n t s - - t h e war and the two turnovers of the whole political system of G e r m a n y - - a n d their peculiar effects on G6ttingen mathematics. Let us start at the end: Between April a n d November of 1933, the Mathematical Institute at G6ttingen was virtually d e s t r o y e d because the Nazis quickly put on leave or dismissed a good part of the staff. The G6ttingen case is unique among German universities for the rapidity and thoroughness of destruction of a big institute. This is all the more remarkable as not one of the G6ttingen professors of mathematics was affected by the non-Aryan clause of the new civil service law of 7 April 1933. More precisely, this non-Aryan clause (w specified that Jewish civil servants had to be dismissed, unless t h e y had been civil servants before World War I or had done frontline fighting during the war. Let us recall that many German Jews occupying eminent positions in society not only shared patriotic feelings for Germany but thought that World War I was the historic occasion to prove, even beyond duty, their allegiance with the German cause. This idea of having to do maybe more than non-Jewish Germans was undoubtedly fostered by the presentiment that otherwise they would be accused of indifference to the national cause. And sure enough, right after the capitulation, which so surprised the fighting troops and toppled the m o n a r c h y in Germany, right-wingers tried to restore as much as possible of the old order and often accused Jewish citizens of having contributed to the disaster by evading their part of the duty during the war (Dr~ickebergerei). In the small world of the G6ttingen mathematicians, Richard Courant is an example of a German Jew who participated beyond the necessary m i n i m u m in the military. Courant was seriously w o u n d e d in September 1915 at the Western Front and afterwards tried to develop a long-wave broadcasting device to help communication between the trench lines (Erdtelegraph). Thus Courant was exempted from w of the law. As for Landau, he was not affected because he had been appointed professor, and thus civil servant, in 1909. During World War I, he reached his forties and was repeatedly found not apt for military service. It is

From left to right: G. T. Whyburn, Marianne Landau, Edmund Landau, Earl Hedrick, Susanne Landau, and Karl Menger at Metro-Goldwyn-Mayer Studios in Hollywood, June 1931.

indicative of the wild right-wing political agitation of the first few months after the war that Landau (along with three other faculty members) was accused of military service evasion in an anonymous letter, published on 24 December 1918, to the editors of the right-wing paper G6ttinger Tageblatt. In h i s - - a n d only his--case, however, the paper printed a formal apology the following day. Now, to get back to the law of 1933, Felix Bernstein, just like Landau, had been a civil servant already before the war; Herglotz and Weyl were not Jewish, and Emmy Noether was not affected because, at first, the law covered only people in civil servant status. But now suddenly, for the only time in her life, she was treated by a German government according to her real merit, not according to her formal position: In a telegram dated 25 April 1933, the ministry put on temporary leave the mathematicians Bernstein, Courant, and Emmy Noether "until final decision of their cases according to the civil service law." This highly unusual and precipitate action calls for explanation. First of all, there were other clauses in the law besides the non-Aryan clause that enabled the government to remove civil servants whose political opinions were thought to make it impossible for them to serve the n e w regime faithfully. Thus Courant, having

learned of the telegram, assumed that it implicitly accused him of such political unreliability; Courant tried to defend himself against this, because he still wanted to save whatever he could of all that he had built up in G6ttingen. This political theme squared very well with a veritable street campaign in G 6 t t i n g e n - - a p p a r e n t l y orchestrated by national-socialist activist students and/or by faculty members from other disciplines--which explicitly focused on the Mathematical Institute, calling it a "fortress of Marxism," a "center of liberalism," and the like. The telegram therefore can be explained as a quick action by the ministry to prevent the street forces from doing things on their own. Already on 28 March 1933, G6ttingen had in fact witnessed a boycott of Jewish shops, with violent harassment of some of their owners, which was a spontaneous action of the local SA (and also SS), anticipating the centrally planned boycott actions. The attempt by the ministry to keep the situation under control can also be seen from the "recommendations" sent out shortly after the telegram to all academic teachers who were considered to be not liked by the national-socialist student majority. Thus at the Mathematical Institute, Landau was asked not to teach his calculus class himself. Consequently, all through the summer term of 1933, Landau prepared the lectures with his assistant Werner W e b e r - - a t that time already a fervent N a z i - - a n d then actually sat in his office during each class, just in case a message from the ministry would reach him that further caution was not needed, and he could take over the class himself again. He heard nothing from Berlin. The political agitation of the G6ttingen students in general is not too unusual considering the general almost religious fervor that gripped so many Germans in 1933. But why, you will ask, did they focus on the Mathematical Institute, out of all possible targets? In the light of documents that I only got to know fairly recently, it becomes clear that the political agitation in the spring of 1933 was the direct continuation of political fights going back at least to 1918. After World War I, in the wake of the capitulation and the half-hearted German revolution, Bernstein and Courant took an active part in the campaign for the elections to a new National Assembly (19 January 1919). Bernstein was vice-president of the n e w l y f o u n d e d left-liberal p a r t y " D D P " at G 6 t t i n g e n ; Courant was commonly referred to as a "well-known socialist" in the newspaper reports on his numerous public speeches. The elder daughter of the applied mathematician Runge also was in the papers almost every day in December 1918/January 1919; and David Hilbert, though he did not give speeches, was conspicuously present at various liberal or leftist election rallies. Emmy Noether did not make public appearances at the time, but the nationalistic circles in 1933 THE MATHEMATICAL 1NTELLIGENCER VOL. 13, NO. 4, 1991

17

clearly considered her socialist, if not communist. She had been a member of the USPD, then the S P D - - t h e social democratic p a r t y - - i n the early 1920s. But for the Nazi students the mere fact that she had given lectures in Moscow in 1928/29 was sufficient to condemn her. The intertwining of anti-Semitic and political agitation against G6ttingen mathematicians can also be traced through the Weimar republic. Thus Bernstein devised a quite successful state loan to stabilize the faltering finances of the young republic in 1919/20 and subsequently was badly hassled in G6ttingen for his

Between April and November of 1933, the Mathematical Institute at G6ttingen was virtually destroyed because the Nazis quickly put on leave or dismissed a good part of the staff. The G6ttingen case is unique among German universities for the rapidity and thoroughness of destruction of a big institute. allegedly irresponsible behaviour in that context: some faculty claimed he had tried to enrich himself in an inadmissible way. But it is obvious from looking at the attackers that this was also simply a fight against the liberal democrats and against the whole republican system, which the right refused to accept. On an almost hilarious note, Courant was implicated, in 1926/27, in a political affair because he had failed a female student in an oral exam. The attempts of the student to sue Courant because he had written in the notes of the exam that she appeared "psychopathic" had no success at all before court. In fact, a doctor's report confirmed Courant's impression. But she managed to enlist the help of the right wing Deutsch Nationale Volkspartei, which took the affair all the way to parliament. I hope these few indications, unpleasant as they are, suffice to show the picture of the political turmoil at G6ttingen that prompted the quick action of the ministry against mathematicians. By the beginning of the winter term 1933/34, in November 1933, Courant was still on leave; Noether had been dismissed according to w (the law had quickly been extended to non-civil-servant employees); Hermann Weyl had preferred to leave for Princeton (the fact that his wife was Jewish would have cost him his job in 1937, if he had stayed on); and Bernstein, who had not been in G6ttingen at all since the end of 1932, was about to be formally dismissed. Thus, only Herglotz and Landau remained, and on 2 November 1933, Landau made an attempt to resume his calculus class himself. The students had apparently been alerted by Werner Weber, w h o had not been asked by Landau to take over the teaching, and 18

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

they staged a boycott with SA guards at the entrances to the lecture hall deterring by their mere presence the students from entering. Only one student had found his w a y in. So Landau had to give up, retired to his office, and there, a few minutes later, was visited by the student leader of the boycott, Oswald Teichm~iller, who proceeded to explain the reasons for the boycott. Landau asked Teichm~iller to write up these reasons and send them to him within two days so that he would have something written in hand. Teichmi~ller complied with this request, and then Landau drew up a letter to the ministry asking for his early retirement. He enclosed a copy of the text of Teichm/iller's letter; b u t - - a s a last and supreme act of his incredible sense of duty and c o r r e c t n e s s - - h e did not communicate Teichm~iller's name to the ministry, evidently in order not to create problems for this young and extremely talented student. I am not personally familiar with Teichm~iller's letter, m a y b e it is no longer extant. That it was actually Teichm~iller who led the boycott is proved, for example, by a letter written by Teichm~iller's mother after the war in which she also mentions this shameful letter. The contents of it must have been pure antiS e m i t i s m , s o m e t h i n g to the effect that G e r m a n ("Aryan") students no longer wanted to be instructed by Jewish teachers. The well-known Berlin professor of mathematics Ludwig Bieberbach, himself hardly ten y e a r s y o u n g e r than L a n d a u , shortly a f t e r w a r d s praised the G6ttingen students for what he called their "manly" action against Landau, and he proceeded to explain an incompatibility of Landau's Jewish w a y of presenting calculus with the German way of thinking. Landau was granted his retirement at the beginning of 1934. The Landaus gave up their house in G6ttingen that same year and moved to Berlin. After a few years highlighted by mathematical trips to Holland and England, Landau died in Berlin on 19 February 1938. He died of natural causes although it is of course impossible to tell h o w much the distress of the last years m a y have precipitated his death. He is buried in the Jewish cemetery of Berlin-Weissensee. As for Teichm~iller, he grew to be probably the greatest mathematical talent of the 1930s--certainly the most original mathematician who ever believed in National Socialism. He perished at the Eastern Front in September 1943, shortly after having volunteered to go there in order to help stop the retreat of the German troops after Stalingrad. [Some of the information concerning Landau has been taken from W. Kluge: Edmund Landau--Sein Werk und sein EinfluJ3 auf die Entwicklung der Mathematik; Staatsexamensarbeit, Duisburg, 1983.] Max-Planck-Institut fi~r Mathematik Gottfried-Claren-StraJ3e 26 D-5300 Bonn 3 Federal Republic of Germany

When the Owl Is Hooting, or, A Mathematical Ghost Story Osmo Pekonen

It was 11 February 1990, a dark stormy winter night at the renowned Mittag-Leffler Institute in Djursholm, S w e d e n . C o b w e b s h u n g over the t i m e - h o n o u r e d volumes of Acta Mathematica, published here since 1882. The famous bat fluttered a r o u n d in the corridors, the celebrated owl hooted outside in the park. Dusty gypsum busts of mathematicians long since dead and statues of owls, G6sta Mittag-Leffler's favourite birds, sulked gloomily in the library. And cold it was, as cold as in the winter of 1650 when Descartes died of pneumonia at the court of Queen Kristina of Sweden. I had stayed late at my desk absorbed by the ghosts and antighosts of Berezinian integrals, skeletons of CW complexes, and other dreary readings that one can find on certain shelves in the venerable institute. The volumes on alchemy betray a passion that G6sta shared with August Strindberg. Suddenly the lights went out. Some absent-minded

nitwit had once again turned off the central switch downstairs. I groped my way in absolute darkness to the staircase. Of course, I came tumbling d o w n it and ultimately hit my head against the mantelpiece of the reading room, an imposing stone structure decorated with owls and the following engraved words: "Talet dr tfinkandets b6rjan och slut.~ Med tanken f6ddes talet./ Ut6fver talet ndr tanken icke." ("Number is the beginning and the end of T h o u g h t . / N u m b e r was born with Thought./Beyond Number, Thought will not reach.") It occurred to me to read these deep lines of G6sta aloud in the original Swedish. Maybe I was actually reading it backwards, for my aching head was buzzing like a beehive. I can't remember clearly now. But then again nobody had warned me in the arrival instructions that this maxim must under no circumstances be recited b a c k w a r d s at m i d n i g h t w h e n the owl is hooting.

THE MATHEMATICAL INTELL1GENCER VOL. 13, NO. 4 9 1991 Springer-Ver|ag New York

19

At once I realized that I was no longer alone at the institute. A long-bearded translucent figure in the full academic regalia of Rector Magnificus of the University of Mfinster stood before my bewildered eyes. I was in the presence of Herr Doktor Professor Wilhelm Killing, president of the Society of Saint Vincent de Paul, member of the Third Order of St. Francis, and the classifier of simple Lie algebras of all orders [1]. In his left hand, the specter held what looked to be a crosier, but somewhat different from that of Bishop Stanislaus Hosius, who had founded Killing's college L y z e u m H o s i a n u m in Braunsberg, East Prussia in 1565. The crosier seemed to consist of a vertical part made of six equal stubs; however, at the fourth joint from the bottom there was a single sideways pointing stub, so that something resembling a quasicross was formed. Under his right arm, he carried a thick black book, which I recognized as one of the lost books of the Kabbala. "Eh . . . . guten Abend, Herr Doktor Professor!" "Zweihundert achtundvierzig, lieber Herr." "Wie bitte??" "'Zweihundert achtundvierzig habe ich schon damals gesagt!'" He thumped the floor with his fake crosier, seemingly in great irritation. I tried to calm him down. "Ja, ja, natiirlich, Herr Doktor Professor . . . . " Just then the bell of the Djursholm chapel tolled midnight. Instantly, the strange apparition vanished, perhaps hurrying back to heaven to say Compline with Elie Cartan. Yes, 248, that is the number that is the beginning and the end of all thinking! The heavenly visitor had told me straight from the Book the dimension of the exceptional Lie algebra E8. And the fancy crosier was but its Coxeter-Dynkin diagram. Working out the corresponding Cartan matrix (actually due to Killing), I recalled how eerily E8 haunts the differential topology of 4-manifolds. The topological 4-manifolds with intersection forms E8 or E8 G E8 cannot carry differentiable structures at all (theorems of Rochlin and Donaldson, respectively, [2]), and not even a quasiconformal structure (Donaldson and Sullivan [3]). Michael Freedman has actually seen such occult manifolds. I started to feel ill at ease, all alone in a spooky house with a bat and E8. In my nightmares, I often find myself trying to read those notorious papers where the (meta)physicists building Stanislas Lem's Universal Theory of Everything conjure up the number 496 as the gauge group dimension of unified superstring theory [4,5]. Uncannily, this is precisely the dimension of E8 x E8 and of little else. Even more uncannily, 496 is a perfect number; in other words, it equals the sum of its own divisors. But 6 = 1 x 2 x 3 = 1 + 2 + 3 is also a perfect number, and therefore, according to St. Augustine, the world was created in 6 days. No wonder then that Stephen Hawking keeps 20

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

quoting from St. Augustine [6]. The hypothesis of 496 virtual exchange particles, most of them yet to be discovered, means that in the very early universe there m u s t have been more than four fundamental forces. I w o n d e r e d h o w m a n y of those U n k n o w n Forces were at work in the institute on this stormy night. The n u m b e r 248 starts a cabalistic arithmetic progression 248, 496, 744, 9 9 2 . . . A n e w mental shock n o w jolted me. 744. I have seen that fellow before! My past life as a complex analyst ran t h r o u g h m y mind like in a movie. Yes, 744. That is the zero m o d e Fourier coefficient of the Klein modular function j = 1728/'. N o b o d y knows why. I will go m a d before d a w n w i t h the u b i q u i t o u s revenant E8, I said to myself. In my panic I grabbed the t e l e p h o n e i n t e n d i n g to dial a n y n u m b e r a n d scream for help. I h a p p e n e d to pick the next Fourier coefficient of j, 196884. However, as m y h a n d s were trembling, I accidentally dialed 196883. A friendly giant's voice answered. "This is the Monster. Unfortunately no irreducible representations can be delivered after m i d n i g h t . There is n o t e n o u g h m o o n s h i n e [7]." " C a n you at least give me a theorem with 992?" "Yes, of course. See the classical paper of Kervaire and Milnor [8]. That is the number of distinct smooth structures on the eleven-sphere. W h y don't you dial 175560 for further information?" In the m o r n i n g m y colleagues f o u n d me at the blackboard busily inverting by h a n d a matrix of order 1240. "There is nothing we can do to stop him," the S w e d i s h p s y c h i a t r i s t s said. " H e believes t h e r e ' s a theorem in it." During the night the Wicked Dwarf (so n a m e d by Jacques Tits) h a d carved one more owl next to the mantelpiece inscription.

References

1. A. J. Coleman, The greatest mathematical paper of all time, The Mathematical Intelligencer 11 (3) (1989), 29-38. 2. R. J. Stern, Instantons and the topology of 4-manifolds, The Mathematical Intelligencer 5 (3) (1983), 39-44. 3. S. K. Donaldson, D. P. Sullivan, Quasiconformal 4manifolds, Acta Mathematica 163 (1989), 181-252. 4. M. B. Green, J. Schwarz, Anomaly cancellation in supersymmetric D= 10 gauge theory and superstring theory, Physics Letters B 149 (1984), 117-122. 5. E. Witten, Global gravitational anomalies, Communications in Mathematical Physics 100 (1985), 197-229. 6. S. W. Hawking, " Q u a n t u m cosmology," in Three Hundred Years of Gravitation, S. W. Hawking and W. Israel (eds.), Cambridge University Press (1987), 631-651. 7. J. G. Thompson, Some numerology between the Fischer-Griess monster and the elliptic modular function, Bulletin of the London Mathematical Society 11 (1979), 352-353. 8. M. Kervaire, J. W. Milnor, Groups of homotopy spheres I, Annals of Mathematics 77 (1963), 504-537.

This photograph of G6sta Mittag-Leffler (1846--1927) appeared in v o l u m e 50 of Acta Mathematica in 1927. In the centenary v o l u m e 148 of the journal in 1982, the picture was described as follows by Andr6 Weil, w h o had been at the institute in 1927: "He l o o k e d like a bird--a bird of prey of course, such as one could see in the Skansen in Stockholm; frail but still tough, wiry, s h o w i n g little sign (to m y inexperienced eye at least) of his i m p e n d i n g death . . . . " THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

21

Working with Alan Turing* Peter Hilton

We are here to honor the outstanding playwright Hugh Whitemore, and to express to him our appreciation of the service he has done to the cause of disseminating an awareness of the importance of mathematics through his celebrated play Breaking the Code. There can be no doubt that the award he is about to receive is richly deserved, as you will have the opportunity to judge for yourselves when Mr. Whitemore reads excerpts from his play to you. The play was inspired by the life and work of the great British logician and mathematician Alan Turing ( 1 9 1 2 - 1 9 5 4 ) - - a life u n u s u a l l y rich in d r a m a and tragedy. I had the good fortune to work closely with Turing and to know him well for the last 12 years of his short life, and thus I am happy to be given this opportunity, within the context of celebrating Mr. Whitemore's award, to reminisce on my association with Turing and to pay tribute to his memory. However, I will be rather selective in my recollections and reflections for a number of reasons. First, there exists a very comprehensive biography of Alan Turing by the logician A n d r e w H o d g e s [3] and it would be gratuitous for me to supply details already carefully assembled and lucidly described in that excellent book. In fact, Whitemore describes his play as based on Hodges's book, though I would claim that it is more accurately described as being inspired by it, since Whitemore's is a brilliant work of imaginative fiction; the book and the play fulfill extremely different functions. Second, I have already written briefly of my association with Turing in Part I of the centenary volume of the American Mathematical Society [2], and, while it w o u l d be futile to seek to avoid any overlap with that article, I feel that only very major aspects of Turing's character, genius and achievement should be repeated here if treated in [2]. After all, my p u r p o s e in [2] w a s rather different; it w a s much broader, and Turing featured in those reminiscences because he was an important mathematician w h o flourished earlier in this century and w h o m I was fortunate enough to know.

Third, I am unfortunately obliged to be reticent about the details of the work we did at Bletchley Park in breaking the high-grade German ciphers. For reasons best k n o w n - - i n d e e d , almost certainly, exclusively k n o w n - - t o themselves, the bureaucrats in Washington and Whitehall steadfastly refuse to declassify such details. It is, to me, inconceivable that such information could be valuable to a potential enemy today, when the methods of encryption and decoding must be utterly different from those of 50 years ago. Does the State Department envisage Colonel Gaddafi gloating over a description of our methods of long ago and concluding that, armed with this knowledge, it is n o w safe to attack the United States? However that may be, I would not wish to risk deportation from the United States and arrest on returning to the United Kingdom, and I must therefore forbear to share with you a fascinating story (as much as I dare tell is to be found in [2]). I joined the distinguished team of mathematicians and first-class chess players working on the Enigma

* Text of a talk delivered on the occasion of the presentation of an award to Mr. Hugh Whitemore, at the winter meeting of the AMSMAA in Louisville(Kentucky)in January, 1990, for communicating, through his play Breakingthe Code,the importance of mathematics to contemporary society. 22

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4 9 1991 Springer-Verlag New York

code on 12 January 1942--and Alan Turing was the called i t - - f o r transmitting their highest-grade ciphers acknowledged leading light of that team. However, I in 1943, so that a wholly new system had to be anamust emphasize that we were a t e a m - - t h i s was no lyzed before we could again start providing regular one-man show! Indeed, Turing's contribution was decryptions to military intelligence. Thus Turing's role somewhat different from that of the rest of the team, remained decisive--but he was not alone in playing being more concerned with improving our methods, that role. However, he was perhaps alone in underespecially the machines we used to help us, and less standing that the machine he was designing to help us concerned with our daily output of deciphered mes- to read messages encoded by the Geheimschreiber was sages. This brings me to an important point inevitably destined, under his guidance, to be the forerunner of g l o s s e d over in W h i t e m o r e ' s play. The p h r a s e the electronic computer. "breaking the code," in popular parlance, refers to the Let me now narrow the focus and describe the sort analysis of the system whereby the message (= signal of man Alan Turing was. First, however, let me estab= i n f o r m a t i o n ) is e n c o d e d . This is the natural lish my credentials for offering such a description. I m e a n i n g - - a s , for example, in the reference to the was fortunate to establish an easy, informal relationwork of Crick and Watson in "breaking the genetic ship with Turing virtually from the day of my arrival code" by analyzing DNA. However, cryptanalysts, at Bletchley Park (this probably had something to do especially under wartime conditions, have another with my helping him to solve a chess problem which t a s k - - t h a t of " r e a d i n g " the e n c o d e d messages so was intriguing him on my first day on the job); and to promptly, so rapidly that the intelligence content of maintain that relationship thereafter. I left Bletchley those messages could be exploited to advantage. Of Park in the summer of 1945, shortly after the end of course, this second aspect of code-breaking would be the European war; after a year at the Post Office Engiimpossible without the first (this is not quite t r u e - - i t neering Research Station I was demobilized and went is sometimes possible to decode messages without back to Oxford University to work on my doctorate fully understanding the method of encipherment); but u n d e r the s u p e r v i s i o n of m y g o o d friend from it is clear that the first would have had no impact on Bletchley days, the great topologist Henry Whitehead. winning the war without the second. To Turing, very In 1948 I took up my first academic appointment, at largely, we owe success in the first, primary aspect of Manchester University, where the head of department code-breaking, together with an entire approach to the was Max Newman, another great topologist and one problem of cryptanalysis which was revolutionary and who had played a decisive role as head of the key secdecisive; but it is to the t e a m - - a n d scarcely at all to tion at Bletchley Park responsible for breaking the T u r i n g - - t h a t we o w e our success in providing our Geheimschreiber code. Max had done me the honor of war machine with information about enemy disposi- appointing me as Assistant Lecturer; he had also tions, plans, tactics, and strategy on a scale and with a b r o u g h t off the t r e m e n d o u s coup of luring Alan regularity never before achieved. It is due to the ef- Turing away from the National Physical Laboratory to forts of Turing and the entire team that Churchill was become Reader in Mathematics--with special responable to describe our work as " m y secret w e a p o n . " sibility for designing a computer to be built by FerTuring could never have said, as Derek Jacobi, the ranti. Thus my relationship with Turing was restored actor who so dramatically played the role of Turing in and I can recall vividly the hours he spent explaining the play, said, "I broke the German code." Neither his to me h o w the computer functioned and how to use it. modesty nor his honesty would have permitted such I left Manchester for Cambridge in 1952, but I regrandiosity. But, in the play, there are but three crypt- mained in touch with Alan Turing until his death. a n a l y s t s - - a n ancient has-been, a y o u n g w o m a n Alan Turing was obviously a genius, but he was an emotionally involved with Turing, and Turing him- approachable, friendly genius. He was always willing self. In fact, our team contained no has-beens, no pas- to take time and trouble to explain his ideas; but he sengers at all, and only one w o m a n - - w h o scarcely was no narrow specialist, so that his versatile thought fitted the description of "Pat Green" in the play; but it ranged over a vast area of the exact sciences; indeed, did contain some wonderful people, mathematicians at the time of his death his dominant interest was in and others, whose contributions were enormous. morphogenesis. He had a very lively imagination and It is also necessary to point out that the two aspects a strong sense of h u m o r - - h e was a fundamentally seof code-breaking referred to above continued to be, rious person but never unduly austere. both of them, of vital importance throughout the war. If I were to attempt to characterize the nature of his For the Germans very frequently changed their enci- genius, I would say it lay in his capacity for thought of phering procedures. Such changes might be relatively great originality, so often going back to first principles m i n o r - - f o r example, changing the wheel patterns for his inspiration. This is not the place for a careful first monthly, then weekly, then d a i l y - - b u t they evaluation of his work, but even the most superficial might be fundamental. Thus the Germans introduced examination of his oeuvre shows how often he took up a totally n e w m a c h i n e - - t h e Geheimschreiber, as we a new topic--his publications range very widely inTHE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

23

Gargoyles for Computer Science Two twentieth-century mathematician have been immortalized as gargoyle on the campus of the Univer ity of Oregon. In keeping with th state of Oreg n' "One Percent for Art Initiative," planners of a n w science complex at th University spon or d a national competition for architecturally integrated art. Winning arti ts included Wayne Chabre, of Milton-Freewater, Oregon, whos sp cialities include copper gargoyles. Chabre's propo al allowed building u er to choose the ubjects of the gargoyles. For Deschutes Hall, the new home of the Department of Computer and Information Science, the faculty requested images of two of the principal contributors to the foundation of the discipline, John von eumann and Alan Turing. Chabre spent some months re arching the subjects, reading biographies and materials accessible to a layman and, with the h lp of faculty, gathering photographs from public and private Mr sources. Gargoyles representing Alan Turing and John von eumann adorn the southern facade of Deschutes Hall, new home of the University of Oregon Department of Computer and Information Science. Gargoyle artist is Wayne Chabre of Milton-Freewater, Oregon.

Readers of the Mathematical Intelligencer may b intere ted in some of th artist's remarks on the subjects: Von N umann gave me trouble as far as portraits are concerned. I was looking at pictures of him a an older man. His face i not distinguished but radiates a mischievou n . r wanted that but don't think I quite got it. I probably spent an extra we k hammering his h ad this way and that. But, if you thought too much about what's involved in a portrait, you wouldn't even attempt it.

r saw

Turing as kind of opposite of Von umann. ot social, not wealthy, not a influential in his lifetime; in fact, he had a hard time making him If under tood. But, though I am certainly not a comput r scienti t, Turing s m d to hav had much more of a vision to communicate. A a result, I identified clo ely with Turing. He went ea ily.

The gargoyles are made of hammered copper sh et and are each about three feet high. The University of Oregon is located in Eugene, Oregon. Eugene Luks Department of Computer and Illformation Science Ulliversity of Oregoll Eugene, OR 97403 USA

administering cyanide cyanide to to himself. himself. However, However, most deed; but but to certain certain topics, topics, in in which which he he made made fundafunda- administering most of of deed; mental advances, advances, he he only only made made one one or or two two published published those those who who knew knew him him well well believe that that he he committed committed mental contributions. Good suicide in Good examples examples of this this modus modus operandi operandi suicide in a moment moment of of despair despair whose whose precise precise timing timing contributions. are his his papers papers on on abelian abelian groups groups and and his his proof proof of the the he he had had not not anticipated anticipated but but of of whose whose eventual eventual arrival arrival are nondecidability of of the the word word problem problem for semigroups semigroups he he felt very very certain. certain. Typically, the the moment moment found found him him nondecidability with cancellation. cancellation. prepared. well prepared. with H u g h Whitemore, This very characteristic characteristic way way of thinking thinking may may also be Hugh Whitemore, perfectly perfectly legitimately, legitimately, makes makes This exemplified by by relating relating certain certain more more lighthearted lighthearted epiepi- Turing's Turing's homosexuality homosexuality a central central theme theme of his his play. play. exemplified Again perfectly perfectly legitimately, legitimately, Whitemore Whitemore is concerned concerned sodes in in Turing's Turing's life. The The story of his his bicycle has has al- Again sodes ready been been told told by by Max Max Newman Newman [4] in in his his obituary obituary of with with the the dramatic dramatic impact impact and and thematic thematic consistency consistency of ready Turing in in the the Obituaries Obituaries of Fellows of the the Royal So- the the story story he he tells with with such such tremendous tremendous effect, so that that Turing Let me me instead instead describe describe his his approach approach to the the it must must remain remain the the responsibility responsibility of others others to tell the the ciety. Let game of tennis. tennis. Turing Turing was was a superb superb athlete athlete (he was, was, true true story story of the the real-life Alan Alan Turing. Turing. I feel compelled compelled game in fact, a marathon marathon runner runner of great great distinction) distinction) and and to put put on on record record the the fact that that I am am unaware unaware of any any in conceived, at at one one time time during during his his stay stay at at Bletchley Bletchley episode episode of overt overt homosexual homosexual activity on on Turing's Turing's part part conceived, Park, a great great love of playing playing at the net net in a doubles during during his his period period at Bletchley Park. Park. Moreover, I must must Park, match. However, although although he was was very quick quick to interinter- strenuously strenuously insist insist that that homosexuality homosexuality was was not not an an issue issue match. cept an an attempted attempted passing passing shot, shot, he he was was distressed distressed at at that that time. As our our colleague and and friend Jack Good Good cept the frequency with with which which he he put put the ball into into the the net. net. has has pointed pointed out out [1], we we did did not not know know that that Turing Turing was was the he began began to think think carefully about about the the reason reason a homosexual; homosexual; indeed, indeed, Good Good has has remarked remarked very perperTypically, he these errors errors and tinently, "Fortunately, "Fortunately, the and decided decided that that it was was necessary necessary to tinently, the authorities authorities did did not not know know for these increase the time-interval time-interval between between the the arrival arrival of the the Turing Turing was was a homosexual. homosexual. Otherwise Otherwise we we might might have have increase on his his racquet racquet and and its dispatch. dispatch. The The remedy remedy con- lost the the war." war." Yes, the authorities, authorities, in a remarkable remarkable exball on sisted, then, then, in in loosening loosening the the strings strings of his his racquet racquet ercise in circular circular thinking, thinking, sought sought to weed weed out out homohomosisted, sexuals because because they were which-being Turing-he proceeded to do do himself. sexuals were a security risk; but but we who who w hich--being T u r i n g - - h e proceeded were merely merely concerned concerned to win bearing a were win the the war war had had other other He arrived arrived next next time on court court with with a racquet racquet bearing had we known known that that Turing Turing was a hodistinct priorities. Even had distinct resemblance resemblance to a fishing net and and was utterly priorities. mosexual (I certainly knew knew of others others at Bletchley Park Park devastating devastating at the net, net, as you may well imagine! How- mosexual that they were homosexuals) homosexuals) we wouldn't wouldn't have cared. ever, he did allow himself persuaded that himself to be persuaded that he was that admit to resenting resenting a tendency tendency to foist onto our our comviolating I admit violating the spirit spirit of the game, if not the letter. munity that unhealthy with There is a wonderful story of how Alan Turing munity of that time the unhealthy obsessions with There w o n d e r f u l story h o w Alan Turing people's preferences which disfigure today's joined the Home Guard, a civilian defense force, when people's sexual preferences which disfigure today's joined Home Guard, when that the prejudices the the danger danger of a German German invasion invasion loomed loomed large, large, in society. I also find myself fearful that which death one thinkers of which led to the death of one of the finest thinkers order to become adept at firing a rifle-typically, he order adept rifle--typically, century be surfacing again this century may surfacing again in the wake of the quickly became expert. Those who would like the deexpert. who would universal anxiety created by the spread tails of this story are referred to page 231 of [3]-1 told universal anxiety created the spread of AIDS, referred page [3]--I leading perhaps perhaps to other pointless and and avoidable tragthe story to Andrew Andrew Hodges who gleefully inserted inserted it leading edies. Can we never learn? Can in his book. Suffice it here to say that, that, once again, again, present to you Mr. Hugh Hugh It is now my pleasure to present Turing Turing attacked a problem from first principles, principles, and and Whitemore. Whitemore. found a highly original original solution. Let me close this brief memoir memoir by a reference to the tragedy of Alan Turing's Turing's life and and the cause of his early death. Alan Turing Turing was a homosexual-not h o m o s e x u a l - - n o t a flam- References References boyant one, not attached attached to casual acquaintanceship acquaintanceship 1. 1.I. J. Good, Early work in computers at Bletchley, NPL 1. -but - - b u t he was committed committed to the personal personal value, to him, (1976) No.1 No. 1 (reproduced in Annals of the History Report 82 (1976) of intimate intimate relationships relationships with male companions. companions. The of Computing). appalling appalling laws of England England of the time, inhuman inhuman in Reminiscences of Bletchley Park, 2. Peter Hilton, Reminiscences both theory and practice, led to his arrest in 1952 on a 1942-1945, A Century of Mathematics in America, Part I, charge of entering entering into a homosexual relationship; relationship; he Mathematical Society Society (1988), (1988), 291-301. American Mathematical 3. Andrew Hodges, Alan Turing: The The Enigma, New York: York: 3. was bound over by the magistrate, magistrate, avoiding a prison (1983). Simon and Schuster (1983). sentence by agreeing agreeing to hormone hormone therapy. He lost his 4. M. H. A. Newman, Alan Mathison Turing, Biographical Biographical 4. security clearance, he was no longer allowed, as a Memoirs of Fellows Fellows of the the Royal Society 11 (1955), (1955), 253-263. convicted felon, to visit the United States, and he became a very lonely man. The circumstances circumstances of his death d e a t h remain remain somewhat s o m e w h a t ambiguous-his a m b i g u o u s - - h i s mother m o t h e r Department of Mathematical Sciences Sciences always believed that his death was due to a miscalcu- State University University of New York 13902 USA USA lation in an experiment he was conducting involving Binghamton, NY 13902 THE MATHEMATICAL MATHEMATICAL INTELLIGENCER INTELLIGENCER VOL.. VOL., 13, 13, NO.4, NO. 4, 1991 1991 THE

25 25

Writing about Alan Turing* Hugh Whitemore

I must make it clear at the very beginning, ladies and gentlemen, that I k n o w absolutely n o t h i n g about mathematics. On the rare occasions when I have attempted to help my 13-year-old son with his math homework, I have failed miserably to understand even the simplest question, let alone to suggest any answer. So as you can imagine, the idea of writing a play about a mathematician is not something that has ever been uppermost in my mind. But in November 1983, while reading The New York Review of Books, I came upon an essay about a newly published b i o g r a p h y - - b y Andrew H o d g e s - - o f a man called Alan Turing. I was astonished to find that this m a n - - o n e of the very few human beings who can be described appropriately and correctly as a g e n i u s - this man had led a life that a writer of fiction would not dare to invent. And I am ashamed to admit that I had never even heard of him. Born in 1912--a product of the English middle-class - - A l a n Turing was educated at Sherborne School and Cambridge. At an early age he showed an astonishing grasp and understanding of mathematics and when he was only 22 he was elected a Fellow of Kings. He became interested in the idea of "Thinking Machines" and wrote a highly influential paper On Computable Numbers. During the Second World War he was sent to the secret decoding establishment at Bletchley Park, where he played a key role in breaking the supposedly uncrackable Enigma C o d e - - o n e of the most crucial factors in defeating Hitler. It must have seemed then

that Turing's future was a s s u r e d - - w i t h a middle-age laden with academic honours and public recognition of his work. But Turing was a homosexual--which, in those days, was a crime in Britain. In 1952 he picked up a young man on the street, took him home and took him to bed. Subsequently, Turing's house was broken into and burgled. Turing suspected that the young man was involved and when he reported the burglary to the police, Turing rashly revealed his own homosexuality. Thus he found himself a criminal, was arrested and sent for trial. He was found guilty of

* Editor's note: This article is the text of a talk g i v e n by H u g h Whitem o r e in J a n u a r y 1990 in Louisville, K e n t u c k y , w h e r e h e w a s pres e n t e d with t h e s e c o n d a n n u a l C o m m u n i c a t i o n s A w a r d by the Joint Policy Board for M a t h e m a t i c s for his play (Breaking the Code) a b o u t Alan Turing. 26 THE MATHEMATICALINTELLIGENCERVOL. 13, NO. 4 9 1991 Springer-VerlagNew York

what is termed "gross indecency" and had to endure the humiliation of sex drug therapy. But Turing was a resilient man; he seemed to weather this terrible storm and to find a new happiness in his work and amongst his circle of loyal friends. And t h e n - - q u i t e unexpecte d l y - h e took his o w n life. This was clearly marvellous material for a play. I knew that the actor Derek Jacobi wanted to appear in a contemporary role, following his enormous success as Cyrano de Bergerac, and my producer put us in touch. Jacobi thought it was a splendid idea and I decided to acquire the dramatic rights in the biography of Turing by Andrew Hodges. But this was not quite as easy as I'd anticipated. Mr. Hodges was not terribly keen on the idea of a play being made from his book; he would have much preferred a movie. However, luck was on my side: I had a play called Pack of Lies running very successfully in London. I took Mr. Hodges to see the play and was delighted to observe that he was suitably impressed by the sight of a packed theatre responding e n t h u s i a s t i c a l l y to the play. An a g r e e m e n t was reached between us and I embarked on trying to turn his book into my play. This proved to be extremely difficult. A year went by as I struggled to find a suitable dramatic form. During this time it became very clear that in order to represent Turing's life on the stage, the a u d i e n c e m u s t be given s o m e understanding of his work and this meant that I would have to try to understand it myself. A daunting prospect for a mathematical dunce. But I persevered. A n d r e w Hodges spent many hours patiently explaining some of the most important aspects of Turing's work; slowly the play began to take shape. Let me now read you one of the scenes in which I tried to express Turing's mathematical ideas in dialogue form. Turing has just arrived at Bletchley Park and Dillwyn Knox, one of the senior cryptographers, asks him about his work. I knew quite a bit about mathematics when I was young, [says Knox] but this is well--baffling. [And he refers to a file containing notes on Turing's work.] For example, this thing here--On Computable Numbers with an Application to the Entscheidungsproblem. Perhaps you could tell me about it. Tell you what? Well, a n y t h i n g - - a few words of explanation in general terms. ITuring is privately amused.J A few words of explanation? Yes. In general terms? If possible. THE MATHEMATICAL 1NTELLIGENCER VOL. 13, NO. 4, 1991 ~ 7

what is termed "gross indecency" and had to endure the humiliation of sex drug therapy. But Turing was a resilient man; he seemed to weather this terrible storm and to find a new happiness in his work and amongst his circle of loyal friends. And t h e n - - q u i t e unexpecte d l y - h e took his o w n life. This was clearly marvellous material for a play. I knew that the actor Derek Jacobi wanted to appear in a contemporary role, following his enormous success as Cyrano de Bergerac, and my producer put us in touch. Jacobi thought it was a splendid idea and I decided to acquire the dramatic rights in the biography of Turing by Andrew Hodges. But this was not quite as easy as I'd anticipated. Mr. Hodges was not terribly keen on the idea of a play being made from his book; he would have much preferred a movie. However, luck was on my side: I had a play called Pack of Lies running very successfully in London. I took Mr. Hodges to see the play and was delighted to observe that he was suitably impressed by the sight of a packed theatre responding e n t h u s i a s t i c a l l y to the play. An a g r e e m e n t was reached between us and I embarked on trying to turn his book into my play. This proved to be extremely difficult. A year went by as I struggled to find a suitable dramatic form. During this time it became very clear that in order to represent Turing's life on the stage, the a u d i e n c e m u s t be given s o m e understanding of his work and this meant that I would have to try to understand it myself. A daunting prospect for a mathematical dunce. But I persevered. A n d r e w Hodges spent many hours patiently explaining some of the most important aspects of Turing's work; slowly the play began to take shape. Let me now read you one of the scenes in which I tried to express Turing's mathematical ideas in dialogue form. Turing has just arrived at Bletchley Park and Dillwyn Knox, one of the senior cryptographers, asks him about his work. I knew quite a bit about mathematics when I was young, [says Knox] but this is well--baffling. [And he refers to a file containing notes on Turing's work.] For example, this thing here--On Computable Numbers with an Application to the Entscheidungsproblem. Perhaps you could tell me about it. Tell you what? Well, a n y t h i n g - - a few words of explanation in general terms. ITuring is privately amused.J A few words of explanation? Yes. In general terms? If possible. THE MATHEMATICAL 1NTELLIGENCER VOL. 13, NO. 4, 1991 ~ 7

It's about right and wrong [says Turing]. In general terms. It's a technical paper in mathematical logic, but it's also about the difficulty of telling right from wrong. People t h i n k - - m o s t people t h i n k - - t h a t in mathematics we always know what is right and what is wrong. Not so. Not any more. It's a problem that's occupied mathematicians for forty or fifty years. How can you tell right from wrong? Bertrand Russell wrote an immense book about it: Principia Mathematica. His idea was to break down all mathematical concepts and arguments into little bits and then show that they could be derived from pure logic; but it didn't quite work out that way. After many years of intensive work, all he was able to do was to show that it's terribly difficult to do anything of the kind. But it was an important book. Important and influential. It influenced both David Hilbert and Kurt G6del. It's rather like what physicists call splitting the atom. As analysing the physical atom has led to the discovery of a new kind of physics, so the attempt to analyse these mathematical atoms has led to a new kind of mathematics. Hilbert took the whole thing a stage further. He looked at the problem from a completely different angle and he said, if we are going to have any fundamental system for mathematics-like the one Russell was trying to work o u t - - i t must satisfy three basic requirements: consistency, completeness and decidability. Consistency means that you won't ever get a contradiction in your own system; in other words, you'll never be able to follow the rules of your system and end up by showing that two and two make five. Completeness means that if any statement is true, there must be some way of proving it by using the rules of your system. And decidability means that there must exist some method, some definite procedure or test, which can be applied to any given mathematical assertion and which will decide whether or not that assertion is provable. Hilbert thought this was a very reasonable set of requirements to impose; but within a few years Kurt G6del showed that no system for mathematics could be both consistent and complete. He did this by constructing a mathematical assertion that s a i d - - i n effect: 'This assertion cannot be proved.' A classic paradox. 'This assertion cannot be proved.' Well either it can or it can't. If it can be proved we have a contradiction, and the system is inconsistent. If it cannot be proved then the assertion is t r u e - - b u t it can't be proved; which means that the system is incomplete. Thus mathematics is either inconsistent or it's incomplete. It's a beautiful theorem, quite beautiful. I think G6del's theorem is the most beautiful thing I know. But the question of decidability was still unresolved. 28

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

As I said, Hilbert thought there should be a single clearly defined method for deciding whether or not mathematical assertions were provable. The decision problem he called it. The Entscheidungsproblem. In my paper On Computable Numbers I wanted to show that there can be no one method that will work for all questions. Solving mathematical problems requires an infinite supply of new ideas. It was, of course, a monumental task to prove such a thing. One needed to examine the provability of all mathematical assertions past, present and future. How on earth could this be done? Eventually one word gave me the clue. People had been talking about the possibility of a mechanical method, a method that could be applied m e c h a n i c a l l y to s o l v i n g m a t h e m a t i c a l problems without requiring any human intervention or ingenuity. Machine!--that was the crucial word. I conceived the idea of a machine, a Turing machine, that would be able to scan mathematical s y m b o l s - - t o read them if you l i k e - - t o read a mathematical assertion and to arrive at the verdict as to whether or not that assertion were provable. With this concept I was able to prove that Hilbert was wrong. My idea worked.

When Derek Jacobi read the finished text he was initially enthusiastic and plans for the production went forward smoothly. But then, barely a month before rehearsals were due to begin, Jacobi telephoned me and asked me to dinner. As we sat in a French restaurant in Soho, he expressed grave misgivings about the play. He couldn't believe that an audience would be interested in the mathematical material and feared that the long speeches about Turing's work would be dramatic millstones around his neck. In my heart, I had similar fears. No matter how experienced one may be, fortunes in the theatre can never be predicted; conseq u e n t l y - a n d w i s e l y - - o n e always fears the worst. But as we sat there, anxiously worrying about what we should do, I remembered the passion with which a mathematician had once spoken to me about his work. I looked across the table and remembered the passion with w h i c h Derek Jacobi h a d delivered the fiery speeches of Cyrano de Bergerac. Quite suddenly I realised that these passions were one. There is no division between artist and scientist, poet and mathematician. I told Jacobi what I was thinking and it seemed to unlock something in his imagination. Although still anxious about the eventual fate of our play, we would proceed. Using some ideas I h a d g l e a n e d from A n d r e w Hodges and some of Turing's own writings, I wrote a speech in the second act of the play in which I tried to show how Turing's passion for mathematics and science grew and developed in his childhood years.

was to read that! What an audacious, challenging - - r a t h e r n a u g h t y - - i d e a that was. He made life seem like a thrilling experiment. And I longed to take part in that experiment.

Derek Jacobi as Alan Turing in Breaking the Code

When I was a child, numbers were my friends. You know how it is; you know how children have their own secret, make-believe friends; friends who can always be trusted: dolls or teddybears or some old piece of blanket they've kept and treasured since they were babies. My friends were numbers. They were so wonderfully reliable; they never broke their own rules. And then, when I was about nine or ten, somebody gave me a book for Christmas: Natural Wonders Every Child Should Know. I thought it was the most exciting book I'd ever read. It was, I suppose, looking back, a sort of gentle introduction to the facts of life; there was a lot about chickens and eggs, I remember. But what the writer of that book managed to convey was the idea that life--all life--is really a huge, all-embracing enterprise of science. There was no nonsense about God, or divine creation. It was all science: chemicals, plants, animals, h u m a n s . "The body is a machine," he said. How exciting it

After our momentous supper in Soho, Derek and I went away on holiday; I to the South of France with my family; Derek to the sandy beaches of the Caribbean, w h e r e he learnt the i m m e n s e role of Alan T u r i n g - - a n d thus dazzled us all by being virtually word perfect at the first rehearsal. We rehearsed for a m o n t h at the Old Vic Theatre. In m a n y ways, rehearsals are the most absorbing part of creating a play. Everybody, actors, director, playwright, technicians, all share in the excitement of discovering and creating something new. It is a period of intense collaboration. Like most productions our play received its first performance in a provincial theatre, safely hidden from the scrutiny of the London critics. As the first night approached, all the fears that Derek Jacobi and I had shared in that Soho restaurant returned like horrid ghosts to haunt us. Eventually the hour of reckoning arrived. The audience settled themselves into their seats. The play began. To our amazement, they listened. The long speeches, during which we feared that people would be restless and bored, were received in an almost rapt silence. What's more, I received a lot of letters saying that it would have been good to have more scientific material in the text. This I d u t i f u l l y inserted before we o p e n e d the play in London. The text was further revised during the London run and before the Broadway production. Let me finish by r e a d i n g a long speech w h i c h opened the second a c t - - a n d which Derek Jacobi delivered as the most extraordinary tour de force. Alas, I cannot begin to match his astonishing performance. Let me set the scene. In 1953 Alan Turing was invited to revisit his old school and to address the Science Society. He talked to them about his thinking machine. In a letter to a friend he said "Went down to Sherborne to lecture some boys on computers. Really quite a treat, in many ways." And so imagine, if you will, a room in an English public school. O u t s i d e - - t h e Dorset countryside. Alan Turing is talking to a group of senior boys and three or four members of the staff. Wearing a shabby sports jacket, stained grey trousers and scuffed shoes, Turing leans against a desk and starts to speak. I want you to imagine a bowl of porridge. A bowl of cold porridge. When I was a boy here at Sherb o r n e - s o m e 25 years a g o - - w e always had porridge for b r e a k f a s t - - e v e r y d a y , w i n t e r a n d s u m m e r - - o r so it seems. And for some unacc o u n t a b l e r e a s o n , by the time the p o r r i d g e reached me it was always cold. My friends were more fortunate; they enjoyed their porridge and THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

29

ate it heartily. But I sat there every morning staring miserably into my bowl of cold porridge: all grey and soft and wrinkled on top. You must be w o n d e r i n g w h y I'm telling y o u this. Your Headmaster has asked me here to talk about my work with computers and here I am describing bowls of cold porridge. Well there's a very good reason for it and I'll come to that in a moment. I daresay the word computer is unfamiliar to many of you. It is to lots of people. But if I were to say Electronic B r a i n - - a h ! - - t h a t ' s much more interesting. And if I were to ask, can a machine think? - - I ' m sure y o u ' d all be intrigued to know the answer. But before we can consider that question properly I must tell you something about computers and h o w they work. First of all, let me compare a c o m p u t e r with the h u m a n b r a i n - which brings us back to our bowl of porridge, because that's w h a t the h u m a n brain looks like: same colour, same texture. A computer is very different. It's b i g - - t h e size of several large wardrobes all joined together; it's hard and metallic on the outside, terribly complicated inside, with lots of valves and condensers and so o n - - n o t a bit like cold porridge, but that doesn't matter. It's the logical pattern of the brain that counts, not the grey stuff it's made of. The same with a computer. What matters is its logic. And the logic of a computer is really very simple. All it does is to read a list of i n s t r u c t i o n s - - w e call this a p r o g r a m - which it then carries out methodically. And the only thing you have to do is to write down exactly what you want done in a language the computer understands. I know this may sound like a fanciful theory, but I assure you that it's not. The computer we've built at Manchester University has been working for over four years, since 1949, and in that time it has successfully tackled a wide variety of tasks. People assume that computers are just glorified calculating machines. Not so. It's true that computers are often used to do calculating because they do calculate very quickly-but computer programs don't have to have anything to do with numbers. A colleague of mine has got our computer to hum t u n e s - - i t once sang 'Jingle Bells'. We've even got it to write love letters! S o - - d o i n g calculations, h u m m i n g tunes, writing love letters. All very different tasks, but all performed by one machine. And that's an extremely important fact about computers. A computer is a universal machine and I have proved how it can perform any task that can be described in symbols. I would go further. It is my view that a computer can perform any task that the human brain can carry out. Any task. Now you might think from what I've said that a computer can only do what it's been told to do. Well, it's true 30

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

that we may start off like t h a t - - b u t it's only the start. A computer can be made to learn. Suppose, for example, that it was set to play chess. It could find out for itself, in the light of its own experience, which were winning and which were losing strategies, and then drop the losing ones. After a while we wouldn't know which instructions it was actually using; so it would hardly be fair to say that we had instructed it what to do. That would be like crediting the master with any originality s h o w n by the pupil. The question thus arises as to whether or not we would credit such a machine with intelligence. I would say that we must. What I would very much like to do is to educate a computer, partly by direct training, partly by letting it find out things for itself. We don't know how to do this yet, but I believe that it will be achieved in the very near f u t u r e - - a n d I feel sure that by the year 2000, it will be considered perfectly correct to speak of an intelligent machine or to say that a computer is thinking. Of course not everyone agrees with this view, far from it. There are those who say that thinking is a function of man's immortal soul and since a machine has no soul it cannot think. Surely this is b l a s p h e m o u s - - w h o are we to deny the possibility that God may wish to grant a soul to a machine? Then there is what I call the 'Heads in the Sand' objection. "The consequences of machines thinking is too dreadful to contemplate," people say, "such a thing could never h a p p e n . " This point of view is usually expressed by intellectuals. They have the most to 10se. Another objection-and this is one I hear very frequently--is that a machine cannot be said to think until it can write a sonnet or compose a concerto, feel grief when its valves fuse, be warmed by flattery, be angry or depressed when it can't get what it wants. Well of course one might reply that there are precious few h u m a n beings who can write a sonnet or compose a concerto--and I can see no reason at all w h y a thinking machine should not be kind, resourceful, beautiful, friendly, have a sense of humour, tell right from wrong, make mistakes, fall in love, or enjoy strawberries and cream. At the m o m e n t such considerations should not concern us; but it might be rather n i c e - - d o n ' t you think?---if, one day, we could find out just what a machine can feel. Finally, ladies and gentleman, I would like to thank you for asking me to be with you this evening. It is a great honour for me. I am deeply grateful. Thank you.

22 Ladbroke Grove London Wll 3BQ England

Hypersets Jon Barwise and Larry Moss

Introduction:

What

Are

Hypersets?

There were a h a n d f u l of experiences that led me 1 to c h o o s e m a t h e m a t i c s as a career. O n e w a s a h i g h school teacher s h o w i n g me the c o n t i n u e d fraction x = 1 +

1 1 1 + - 1+...

(1) D e f i n i t i o n 1. A set b is a h y p e r s e t if there exists an infinite d e s c e n d i n g sequence

a n d t h e n going o n to convince me that x is, of all

l+V~ things, the g o l d e n ratio ~b - - - - - 7 - .

O n the one

h a n d was the ellipsis " . . . " d e s c e n d i n g like Lucifer's b a n d ever d e e p e r into the nefarious d e n o m i n a t o r . O n the other was the light and clarity of the solution of equation (1), obtained by observing that the fraction satisfies the identity x = l + -

1

x

,

A n d eventually, it led m e to appreciate the construction of the reals as C a u c h y sequences of rationals. But that was far d o w n the road. I h a d a similar e x p e r i e n c e a few y e a r s ago, in r e a d i n g a m a n u s c r i p t 2 b y Peter Aczel o n non-wellf o u n d e d 3 sets.

9. . Ean+ lea

hE.

. . Ea 1E

b.

O t h e r w i s e b is w e l l - f o u n d e d . A simple example of a h y p e r s e t is: x = {1,{1,{1,{1 . . . .

}}}}

(3)

This set is a m e m b e r of itself, for the same reason that the c o n t i n u e d fraction in (1) satisfies (2). Therefore x is

(2)

1 + X/-5 2 I was hooked; I s p e n t several periods on hall monitor d u t y making u p c o n t i n u e d fractions a n d "solving" t h e m . E v e n t u a l l y I s t u m b l e d on s o m e problematic ones, w h i c h s h o u l d h a v e led me to the c o n c e p t of limit, I suppose. But they at least led me to appreciate the notion w h e n I learned of it a couple years later. which quickly leads to x -

1 For obvious expository r e a s o n s , t h e introductory section is written in the first p e r s o n , in t h e voice of J.B., the older a u t h o r a n d the one c o n s e q u e n t l y m o r e inclined to reminisce. O t h e r w i s e , b o t h a u t h o r s a r e equally to b l a m e for w h a t is contained here. 2 This m a n u s c r i p t e v e n t u a l l y d e v e l o p e d into Aczel [2], the definitive reference o n n o n - w e l l - f o u n d e d sets. 3 O u r hypersets a n d A c z e l ' s non-well-founded sets are t h e s a m e thing. T h e former h a s t h e a d v a n t a g e of n o t h a v i n g n e g a t i v e c o n n o t a t i o n s , a n d it r e m i n d s u s of t h e h y p e r r e a l s of n o n - s t a n d a r d analysis. A s we shall see, there is a n analogy. THE MATHEMATICAL1NTELLIGENCERVOL. 13, NO. 4 9 1991 Springer-VerlagNew York

31

a hyperset. Confronted by such an expression years earlier, I experienced the same sense of vertigo experienced on my first encounter with continued fractions, but without the corresponding uplifting feeling given by the solution of the continued fraction. Sure, you can play the same game, by noting that x = {1,x}

(4)

But then what? In what domain of sets could one solve such an equation? But I was told that such sets do not exist. They are ruled out by an accepted axiom of set theory, the Axiom of Foundation, (FA): Every set is well-founded.

(FA)

So it would seem to be hopeless to try to solve (4).

The Axiom of Foundation FA states that there are no infinite descending sequences of sets under E. There is an equivalent form of FA that is much more attractive. One of the building blocks of ZFC set theory is the family of sets V~, where e~ is an ordinal number. V0 is the empty set, Q. V~+ 1 is the set of all subsets of Vs. Finally, at limit ordinals we take unions. It turns out that FA is equivalent to the assertion that every set belongs to some V~,. Assuming FA, every set has a place in this well-ordered hierarchy. Roughly speaking, the higher the place, the more complicated the set. By adopting FA, we come to feel that the set-theoretic universe is a richly structured, hierarchical realm. Set-theorists tend to have one of two attitudes towards FA. On the one hand there are those who believe that it is fundamental to our understanding of sets, and so is one of the most basic axioms. The other attitude is that the Axiom of Foundation, unlike the other axioms of Zermelo-Fraenkel set theory (ZFC), does not capture a commonly accepted mathematical principle, one used by the working mathematician when applying set theory. On this view it is a harmless piece of logician's hygiene. (See Box " S o m e Quotes on The Foundation Axiom" for some examples of these diverging attitudes.) How do we know it is harmless? Well, start with set theory without FA, known as ZFC-, and consider the collection WF of all well-founded sets. Using the observation that any set of well-founded sets is itself well-founded, it is easy to show (using ZFC-) that all the axioms of ZFC- hold when relativized to WF, and so does FA. Thus, introducing FA cannot introduce any inconsistencies into set theory. And, moreover, we can model familiar mathematical structures (natural numbers, rationals, reals, and so on) within WF. So why not assume FA? And so, until recently, FA has pretty much had its way. While we may have disagreed about the reason, 32

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

most set-theorists have been quite content to assume that it is true. And for many of us, there was an almost religious devotion to FA. (See Barwise [3], for example.) But recently Foundation has been shaken, not by contradictions but by the claim that it disallows sets that we might, after all, want to have around. More importantly, an elegant alternative conception of set has been developed. It suggests a universe that encompasses all the old well-founded sets, but also allows a space in which equations like (4) can be solved. And it is leading to some lovely mathematics. Equally important, this new conception of set has elegant applications outside of mathematics, in computer science, AI, philosophy, and linguistics. Hypersets allow us to model various kinds of real-world phenomena in set theory in a simple and elegant manner, using the machinery long familiar from the theory of sets. As a matter of fact, Aczel's work on non-wellfounded sets grew out of a problem in computer science, on the theory of so-called " c o m m u n i c a t i n g systems." In attempting to understand and simplify work in this area, he was led to develop his universe of sets, and to formulate AFA, the so-called Antifoundation Axiom. Ten years ago we, along with many set-theorists, would have claimed that the Axiom of Foundation was unassailable. But after learning about and using AFA, our feelings about FA and set theory in general have changed. We now recognize that axioms often embody metaphors, and that their adoption colors mathematics. The intuitions that FA is getting at are important, but they are limiting as well. So FA is not just an innocent assumption adopted out of expedience or the wish to be parsimonious. And to adopt FA merely because the iterative conception is attractive is to make a necessity of virtue. Aczel's work has taught us that FA is not a necessary part of a clear picture of the universe of sets. He showed that there is a domain of abstract objects in which equations like (4) have solutions, and that this domain is an elegant alternative to the ordinary universe of sets. Mathematically, the domain is an extension of the well-founded universe, in very much the way that the real numbers are an extension of the rationals. On the other hand, there is a big difference between the two conceptions of set upon which the axioms rest. The point of this article is to describe this domain, and some of its applications. We are also interested in the hypersets as a case study in the philosophy of mathematics. It gives us a chance to observe and take part in the evolution of a broadening of a mathematical concept, analogous to what took place with the discovery of the irrationals and complex numbers. Our aim will be satisfied if you come to see this domain as an interesting, mathematically and philosophically respectable alternative to the classical domain of set theory.

We feel that h y p e r s e t s will b e c o m e i m p o r t a n t as people use t h e m in modeling. The fact that they emb o d y an intuition about sets is a big plus for them. That this intuition differs from w h a t we have for the well-founded sets is unfortunate, but unavoidable. As always with mathematics, the i m p o r t a n t thing is to be aware of w h a t the axioms are saying, and what is behind them.

The Foundation A x i o m and Ordered Pairs The importance of set t h e o r y in mathematics does not lie in the intrinsic interest in u n s t r u c t u r e d sets of objects, so m u c h as in the mathematician's ability to use such sets to r e p r e s e n t mathematical structures of enorm o u s variety: n u m b e r s , functions, relations, and the like, as well as non-mathematical structure. W h e n you trace all this back to its roots, it relies crucially on the

ability to represent sets of o r d e r e d pairs, and so ord e r e d pairs themselves. If it were not possible to represent o r d e r e d pairs in set theory, set theory w o u l d be of virtually no mathematical interest at all. The standard way of modeling the ordered pair Ix,y) in set t h e o r y is by m e a n s of the set {{x},{x,y}}. All that matters for most p u r p o s e s is that this modeling satisfy the defining condition on o r d e r e d pairs: if Ix,y) = (u,v) t h e n x = u and y = v. For our purposes, it is important that this holds n o m a t t e r w h a t objects x a n d y h a p p e n to be, even if x a n d y are hypersets, say if x = {x,y}. A m o m e n t ' s t h o u g h t shows that the usual proof of this c o n d i t i o n d o e s n o t m a k e a n y a s s u m p t i o n s a b o u t the n a t u r e of x or y. O n c e we h a v e o r d e r e d pairs, w e can r e p r e s e n t o r d e r e d triples as o r d e r e d pairs (~x,y,z) = (x,(y,z)~), binary relations as sets of ord e r e d pairs, functions as certain kinds of relations, and so forth, as usual. THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

33

To see the connection b e t w e e n o r d e r e d pairs and FA, it is useful to give an equivalent characterization of the hypersets.

Definition 2. A set x is a constituent of a set z, written x E* z, if x is a m e m b e r of z, or a m e m b e r of a m e m b e r of z, or a m e m b e r of a m e m b e r of a m e m b e r of z . . . . (That is, the relation E* is the transitive closure of the m e m b e r s h i p relation E.) The observation is just that a set b is a h y p e r s e t iff there is a sequence Can : n = 1,2 . . . . ) in the constituent-of relation E*: 9 . . ~*

an+

1

E*

a n E*

. . . E*

a 1 E*

b

(One direction ( ~ ) is immediate, the other direction obvious: y o u just fill out a d e s c e n d i n g sequence in the E* relation to get a d e s c e n d i n g sequence in the membership relation.) It is important to note that the sets a, are not required to be distinct. Thus, for example, any cycle in the constituent relation in a n y constituent of a set b will cause b to be non-well-founded. Using FA, w e can p r o v e some s u r p r i s i n g general facts about various sorts of mathematical objects. Here are two that will be of use to us.

Proposition 1. Assume the Axiom of Foundation. 1. For any x,y, x ~ Cx,y) and y ~ Cx,y) 2. For any relations R, S, if there is an object a such that a bears R to S (in symbols, aRS), then there can be no object b such that b bears S to R. Proof. These all rely on the simple observation that, with the above representation of o r d e r e d pairs, both x and y are constituents of Cx,y). Every representation of o r d e r e d pairs we k n o w of has this p r o p e r t y , and this is all that is n e e d e d to p r o v e these results. Let us prove (2) for the record. Assume by w a y of contradiction that aRS and bSR, i.e., that Ca,S) E R a n d that Cb,R) E S. T h e n w e h a v e a cycle in the c o n s t i t u e n t relation E*: S E* Ca,S) E R E* Cb,R) E S which shows founded. 9

t h a t t h e s e s e t s a r e all n o n - w e l l -

This result suggests that FA will cause p r o b l e m s w h e n w e s e e k to u s e w e l l - f o u n d e d sets to m o d e l various kinds of circular phenomena, and we turn n o w to a few examples.

ModeIing Circular Phenomena in Set Theory Over the past h u n d r e d years, a wealth of techniques for modeling various sorts of p h e n o m e n a has been developed within set theory. These build on the representation of o r d e r e d pairs, relations, a n d functions. 34

THE MATHEMATICAL IN~ELL1GENCER VOL. 13, NO. 4, I991

H o w e v e r , w h e n we try to apply these techniques to p h e n o m e n a that i n v o l v e circularity, the A x i o m of F o u n d a t i o n frequently gets in the way. In this section we examine a few of these. We only go into the simplest two in any detail, since the aim is to give the reader a feel for the sorts of cases w h e r e h y p e r s e t s are important.

Streams The notion of a stream comes u p in comp u t e r science. Intuitively, a stream is an o r d e r e d pair s = Ca,s'), the first e l e m e n t of w h i c h is s o m e finite value, the second element of which is a n o t h e r stream 9 T h u s the basic o p e r a t i o n s on streams are taking its first element, which gives a finite value, and taking its second element, which p r o d u c e s another stream. While streams are infinite, it is easy to write comp u t e r programs that generate them. For example, if w e define: fin) = (n,fln + 1)) a n d r u n this as a program, it will generate the stream C0,C1,C2. . . . ))), at least in the ideal limit that interests us as theorists. Let A be a set of " a t o m s , " character strings, num e r a l s , w h a t h a v e y o u , a n d s u p p o s e w e w a n t to m o d e l the collection of streams, each having as first e l e m e n t an atom in A. The natural definition that suggests itself is as follows. Let the set St(A) of streams be the largest set satisfying the following condition: if s E St(A) t h e n s = Ca,s') for some a E A a n d some s' E

St(A). Intuitively, every infinite sequence of atoms s h o u l d give rise to a stream (and vice versa). H o w e v e r , we have the following observation:

Proposition 2. Assume the Axiom of Foundation. Then St(A) = (~. The proof, like the proof of Proposition 1, relies on the observation that y is a constituent of Cx,y). Thus a n y stream w o u l d give rise to an infinite descending chain in the relation E*. This is a pretty drastic mismatch b e t w e e n the intuitive n o t i o n a n d o u r m a t h e m a t i c a l m o d e l . C o n s e quently, if we are going to m o d e l streams in zFc, set t h e o r y with the Axiom of Foundation, we cannot do it in the intuitively natural way. We w o u l d have to resort to some artifice, like treating them as functions from the natural n u m b e r s into A. This would force us to m o d e l the operation of taking the second coordinate of a s t r e a m by m e a n s of a shift o p e r a t i o n on s u c h functions.

Non-hierarchical Databases Intuitively, a database is some sort of syntactic structure that represents purp o r t e d facts a b o u t the w o r l d . A relational d a t a b a s e r e p r e s e n t s facts of the form that certain objects stand

in certain relations. For our purposes, w e can skip the syntactic structure, a n d worry about the facts themselves. Here is an example of a database that represents facts about the Barwise family:

FatherOf Father

Child

Mother

Child

Brad Dan Dan

Casey David Alisa

Nancy Judith Judith

Brad David Alisa

BrotherOf

David

Proposition 3. Assume the Axiom of Foundation. Then there are no correct database models.

MotherOf

Brother

H o w e v e r , our set-theoretic models do not s u p p o r t this intuition. Indeed, w e have the following:

Sibling

Alisa

For ease of exposition, let us restrict attention to databases like this one w h e r e all the relations involved are binary, and let us s u p p o s e that binary relations are represented as usual in set theory, as sets of ordered pairs. Thus, w e d e f i n e a database m o d e l to be any function ~J~ with d o m a i n some set Rel of binary relation symbols such that for each such relation symbol R, R ~ is a finite binary relation. The basic problem that we w a n t to examine is that it is easy to write d o w n databases that seem correct but which, on this definition, have n o database model at all. Lets look at a v e r y simple example, t a k e n from Barwise [7]. A s s u m e that our set Rel does not contain the relation symbol SizeOf, a n d let Rel' = Rel U {SizeOf}. We say that a database model ~J)~ for Rel' is correct if the relation SizeOf ~ consists of all pairs (R,n) w h e r e R is a relation of ~ and n is the cardinality of R. N o w , intuitively, every database for ReI can be extended in a unique way to a correct database for Rel'. For example, h e r e is the e x t e n s i o n of the d a t a b a s e r e p r e s e n t e d above, which s h o w s h o w the general p r o o f should go.

Proof. S u p p o s e that ~ is correct, let SizeOf be the size relation in ~d~, a n d let n be its size. T h e n we h a v e n SizeOf SizeOf. But then w e can apply part 2 of Proposition 1 (with R = S = SizeOf) a n d get a contradiction. In the case of streams, we saw that w e could, at some cost in naturalness, get a r o u n d the problem b y modeling t h e m by functions on the natural n u m b e r s , rather than as pairs. H e r e too w e could get a r o u n d the problem. For example, w e could alter the definition of correctness to specify that the interpretation SizeOf of S i z e O f be a function of the symbols in Rel, not of their interpretations. This m a y not be that objectionable, in this case. We include this example mainly because it is easy to state and gives a feel for the sorts of problems that can arise. At the e n d of this p a p e r we mention s o m e m o r e substantial e x a m p l e s of desirable circularity. It w o u l d take a fuller discussion to do justice to a n y of these.

Rethinking These Negative Results Let's rephrase the results of this section in a w a y that does not dep e n d on FA. Let us call a stream s E St(A) well-founded if it is in the class WF of well-founded sets. Similarly, let us call a database m o d e l ~JJ~hierarchical if it belongs to WF. Propositions 2 and 3 can be restated as follows:

Proposition 4 (Working in zFc-.) 1. There are no well-founded streams. 2. No hierarchical database is correct.

Father

Child

Mother

Child

Put this way, these results are neither surprising n o r upsetting. T h e y simply s h o w that we have been att e m p t i n g to m o d e l n o n - w e l l - f o u n d e d p h e n o m e n a with w e l l - f o u n d e d structures. It suggests that if we had a workable replacement for FA, we might be able to p r o v e the sorts of existence results we want. A n d this turns out to be the case.

Brad Dan Dan

Casey David Alisa

Nancy Judith Judith

Brad David Alisa

The Antifoundation Axiom

FatherOf

MotherOf

BrotherOf

SizeOf

Brother

Sibling

Relation

Number

David

Alisa

FatherOf MotherOf BrotherOf SizeOf

3 3 1 4

It is, of course, not m u c h use giving u p the Axiom of F o u n d a t i o n w i t h o u t s o m e t h i n g with which to replace it. It is not e n o u g h to simply d r o p FA a n d d e d u c e that there might be hypersets. If y o u are going to p r o v e that the right sorts of h y p e r s e t s do exist, y o u n e e d to a s s u m e some general principle which, together with the o t h e r axioms, implies this. A n d we n e e d to do this in a w a y that is compatible with all the other principles of set theory. THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991 3 5

There is another problem as well. The usual Axiom of Extensionality tells us that sets with the same members are identical. But what about sets a = {a} and b = {b}? Is a necessarily identical with b? The usual formulation of the Axiom of Extensionality (sets with the same members are themselves the same) does not help us answer this question. Without a clear identity criterion for hypersets, they are not of much use. It is not even clear that they deserve the name "set." So a theory of hypersets must be based on new axioms. How are new axioms of set theory born? For us, axioms are conceived in an attempt to capture the essence of some important phenomenon. We want to abstract from a repeated pattern in the physical world or the world of mathematical ideas and say something true and fundamental. It is not e n o u g h that a new axiom not lead to a contradiction (as sometimes happens in set theory). Even if it were "obviously" inoculated against the plague of paradox, a new axiom will not survive unless it is based on a solid intuitive understanding of something. Otherwise it would die stillborn for lack of interest. And indeed, the literature is strewn with stillborn theories without an intuitive conception on which to rest. There have been a number of set-theorists exploring in the wilderness of set theory w i t h o u t FA, pretty much ignored by their peers. These visionaries include M. Boffa, M. Forti, L. Gordeev, and F. Honsell. However, it has only been recently, with the work of Peter Aczel, that the theory has really jelled into a coherent body of work that gives a clear picture of a universe of hypersets. Perhaps the reason that the earlier work wasn't received well was that it wasn't clear that the many axioms proposed were connected to the modeling of circular phenomena or how they related to the deep and important enterprise of finding new conceptions of set. There are at least two quite distinct metaphors that can inspire a theory of sets. One is that a set is like a box of things, and that forming a set is like putting things in a box. Quite a distinct metaphor is that set formation is the result of forgetting components in favor of structure. Take any sort of structured object, an object with " ' c o m p o n e n t s , " and forget the particular components and the particular "glue" that holds them together. What you are left with is abstract set-theoretic structure. The difference between these metaphors is apparent w h e n we ask: Where do the objects come from in the first place, and what objects are there? The box metaphor is the motivating intuition that gives rise to the Axiom of Foundation, by means of the cumulative hierarchy. Starting with some set of atoms, you can form sets of these. This gives you a new collection of things to use in forming sets. And so on. Any set formed in this way will be well-founded, since any set of well-founded sets is itself well-founded. 36

THE MATHEMATICAL INTELLIGENCER VOL 13, NO. 4, 1991

The structure-forgetting metaphor, by contrast, is reflected in the " f o r g e t f u l f u n c t o r s " of category theory. It is also the intuition behind a conception of set that admits of hypersets. First, it is worth noting that every set b, well-founded or not, can be represented as a structured object, namely as a directed graph. For nodes, take b and all its constituents. For edges, draw an edge x ~ y from node x to node y whenever y E x. This graph is what is known as an accessible pointed graph, or apg. The "point" is the distinguished node b. It is accessible because every n o d e in the graph can be reached by some path starting from the point. Figure 1 shows four sets and the apg's they determine. In each case, the distinguished node of the apg is the uppermost node. For the moment, consider only Figure l(a) and (b). In Figure l(a), we see the apg determined by {0,{0}}. This set is the standard representation of the natural number 2 as a v o n Neumann ordinal. Figure l(b) shows the apg for 3.

(a)

{r162

(c)

s = {~}

Figure 1. Four pictures of sets.

(b)

(d)

{~,{r162162

~

again

The forgetful f u n c t o r m e t a p h o r s u g g e s t s that w e s h o u l d think of sets as arising f r o m such directed g r a p h s b y the p r o c e s s of abstraction, forgetting the nature of the n o d e s themselves. That is, to each directed graph we s h o u l d be able to " f o r g e t " the exact nature of the n o d e s a n d so assign to each n o d e n a set d(n) so that

d(n) = {d(m)ln ~ m}

(5)

H e r e , a n d a b o v e , " n ~ m " is r e a d " n is a p a r e n t of m."

Aczel puts it s o m e w h a t differently, in terms of a picturing m e t a p h o r . Sets, on this m e t a p h o r , are just the sorts of structures that are pictured by accessible p o i n t e d graphs, w h e r e the d e n o t a t i o n function bet w e e n a n o d e a n d the set it represents m u s t satisfy (5). This leads us to the following formulation of AFA, the Antifoundation Axiom. D e f i n i t i o n 3. (Working in ZFC-.) 1. A directed graph (G,---~) consists of a set G of objects called nodes, and a set ~ of pairs of nodes, these pairs being called edges. 2. An accessible pointed graph (G,---~,p) consists of a directed g r a p h together with a distinguished n o d e p w i t h t h e p r o p e r t y t h a t e v e r y n o d e can be reached b y some finite path from p. 3. A decoration for a directed graph G consists of a s e t - v a l u e d f u n c t i o n d w i t h d o m a i n the set of nodes, satisfying equation (5). 4. An apg G = (G,---~,p) pictures the set b if there is a decoration d of the graph so that d(p) = b; that is, so that b is the set that decorates the top node. We have already seen h o w to picture a n y set whatsoever with an apg. The question is about the converse. Which apg's picture sets? It is a t h e o r e m of ZFC- that every w e l l - f o u n d e d apg (an apg with n o infinite descending chains) pictures a u n i q u e set. If o n e a s s u m e s FA, then one can p r o v e that only w e l l - f o u n d e d apg's can picture sets, since any infinite d e s c e n d i n g chain in an apg gives rise to an infinite d e s c e n d i n g chain in the m e m b e r s h i p relation. Hence, a s s u m i n g FA, the apg's that picture sets are the well-founded apg's. Aczel's proposal is that we think of sets as just those objects that can be pictured by any apg whatsoever. This gives rise to the A n t i f o u n d a t i o n Axiom, AFA. Every apg pictures a u n i q u e set.

(AFA)

T h e r e are s e v e r a l e q u i v a l e n t w a y s to state this axiom. We have c h o s e n the one that is closest to the intuition that motivates it. A n o t h e r w a y to state it is that e v e r y d i r e c t e d g r a p h has a u n i q u e decoration. Still a n o t h e r equivalent version is k n o w n as the Solution L e m m a , stated below. It is this v e r s i o n that is m o s t u s e f u l for a c t u a l l y p r o v i n g r e s u l t s a b o u t hypersets.

T h e simplest h y p e r s e t is called fL It satisfies the equation f~ = {f~}, and it is pictured in Figure 1(c). It s h o u l d be n o t e d that a n y apg in which e v e r y n o d e has a child is a picture of ft. There are two sides to AFA, existence and uniqueness. Existence gives us m a n y hypersets. Uniqueness settles the problems a b o u t identity of sets. Consider, for example, sets a = {a} and b = {b}. Both of these sets are pictured by the simplest cyclic graph, depicted in Figure 1(c). But according to AFA, there is only one such set, so a = b = fk More generally, AFA tells us that a set is completely d e t e r m i n e d by a n y graph that pictures it. This has the effect of making sure that sets are equal w h e n e v e r t h e y possibly could be. This is ext r e m e l y useful in m a t h e m a t i c a l m o d e l i n g with AFA since it forces one to be explicit about w h a t it is that makes distinct objects distinct.

The Consistency of AFA

We saw earlier (see Box " A r e n ' t Contradictions Lurking in Hypersets?") that h y p e r s e t s do not give rise to a n y obvious paradoxes. But h o w do we k n o w for sure that the notion of set u n d e r w r i t i n g AFA is c o h e r e n t , so that n o contradictions can arise? The reply to this challenge is to s h o w h o w to c o n s t r u c t a d o m a i n w h e r e all the axioms of ZFC- together with AFA are true. This w o u l d s h o w that ZFC- plus AFA is consistent. Of course we k n o w by the f a m o u s G6del Incompleteness T h e o r e m s that we c a n n o t prove such a result outright. N o m a t h e m a t i c a l t h e o r y w o r t h its salt is s t r o n g e n o u g h to p r o v e its o w n consistency. H o w ever, w h a t we can do is to p r o v e a relative consistency result, by s h o w i n g that if ZFC- is consistent, so is the result of a d d i n g AFA. The proof shows more. It shows h o w to take any d o m a i n W of sets satisfying ZFC- a n d e x t e n d it in a canonical w a y to get a d o m a i n V satisfying all of z F c - + AFA.4 We will not give the p r o o f in detail, b u t w e will sketch it. The basic idea is similar to the modeling of the real n u m b e r s as equivalence classes of C a u c h y seq u e n c e s of rational n u m b e r s . But h e r e , i n s t e a d of using sequences, we use apg's, with their o w n equival e n c e r e l a t i o n . A bisimulation b e t w e e n t w o a p g ' s (G1,---~l,Pl) a n d (G2,---~2,P2~ consists of a relation R C G 1 x G 2 satisfying the following conditions:

1. plRp2 2. if xRy then 9 for e v e r y x 0 ~--1 x there is a Yo ~--2 Y such that

xoRyo 9 for e v e r y Yo <--2 Y there is a x 0 *--1 x such that

xoRyo We say that two apg's are bisimilar, and write G 1 - G 2,

4 This o b s e r v a t i o n s h o w s w h y it is that AFA does n o t yield a n y n e w t h e o r e m s that s p e a k only a b o u t w e l l - f o u n d e d sets. THE MATHEMATICALINTELLIGENCERVOL. 13, NO. 4, 1991

37

if there is a bisimulation relation b e t w e e n them. As an example, the g r a p h s in Figure 1(c) a n d l(d) are bisimilar: the bisimulation relates the u n i q u e point in (c) to e v e r y point in (d). The following observations are each p r e t t y easy to check, using just ZFC-: 1. The relation G 1 - G2 is an equivalence relation on apg's. 2. If G 1 - G2, t h e n G 1 and G2 picture the same sets, if any. The basic idea of the construction of V from W is to take equivalence classes [G] of apg's G E W, u n d e r the relation - , and use t h e m to model sets. The membership relation is d e f i n e d on them in the natural way: 38

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

[H] E [G] iff there is a n o d e n that is a child of the top n o d e in G so that H - G n, w h e r e G n is the apg gotten from G b y snipping it off just above n. The effect of this construction is just to identify any two apg's that should be identified in that they will be picturing the s a m e sets. O f c o u r s e o n e m u s t c h e c k that all the axioms hold in the resulting structure. To e m b e d W isomorphically into V we go from any set b to the canonical picture G b of it, described earlier, and on to [Gb]. This construction does m o r e than s h o w consistency of AFA. It also shows that, in a certain sense, the AFA sets are " f i n a l " in the c a t e g o r y of u n i v e r s e s of set t h e o r y . But w e will not go into the c o n s t r u c t i o n in

greater detail here, instead referring the r e a d e r to Aczel [2] for details a n d historical r e m a r k s on the proof.

The Solution L e m m a We m e n t i o n e d above that there are a n u m b e r of different ways to state AFA. O n e of the most useful ones in the applications is the Solution Lemma, a version of w h i c h w e state here. It lets us solve systems of equations such as x = {x,y}

y = {2,3,y,z} z = {x,y,f~} The intuitive c o n t e n t of the Solution L e m m a is that a n y such system of equations is solvable in the universe of hypersets. In stating the result, w e use "9X" for the p o w e r set of X. L e m m a 5 (The S o l u t i o n Lemma) Assume AFA, and let X be any set, let b be a function from X to VX, and let c be a function with domain X. Then there is a unique function d with domain X such that for all x E X,

w h e r e the bars I I d e n o t e the cardinality of the set inside. To e x t e n d ~ to a c o r r e c t m o d e l , w e set SizeOf ~ to be the solution to this equation. We s h o u l d point out that AFA is not magic: not e v e r y " e q u a t i o n " involving sets has a solution. You m u s t be able to cast the equation in the form given by the Solution Lemma. For example, it is a t h e o r e m of Cantor, p r o v e d u s i n g only ZFC-, that t h e r e is n o set w h i c h contains its o w n powerset. It follows that we cannot solve the equation x = I0x, no matter w h a t axioms we add to ZFC-. This observation is a parallel to the fact that some c o n t i n u e d fractions d o not converge to real numbers. Likewise, and somewhat disappointingly, we c a n n o t use AFA to build nontrivial sets or topological spaces equal to their o w n function spaces. True, 12 is a solution to X = X x. H o w e v e r , this is the only solution AFA gives us. Indeed, we have the following stronger observation, due to Aczel.

Proposition 6. Assume AFA. If X C X X, then either X = Q o r X = 12.

d(x) = {d(y) : y E b(x)} U c(x). In fact, this Solution L e m m a is equivalent to AFA; if we assume only ZFC- and the Solution Lemma, we can d e d u c e AFA. (This is a good exercise.) As a s i m p l e e x a m p l e , h e r e is h o w the Solution L e m m a allows us to solve the system above. Let X be any three-element set {x,y,z}. Let b(x) = {x,y}, b(y) = {y,z}, a n d let b(z) = {x,y}. Let c(x) = 0 , c(y) = {2,3}, a n d c(z) = {12} = 12. T h e n the Solution L e m m a gives us sets d(x), d(y) and d(z) that solve the system. It also implies t h a t the s o l u t i o n s of s y s t e m s like this are always unique. Let us look again at the set St(A) of streams on a set A. U n d e r FA, w e saw that this set was e m p t y . Using the S o l u t i o n L e m m a , w e can s h o w t h a t e v e r y seq u e n c e a I, a 2, a 3. . . . of atoms gives rise to a stream (al,(a2,(a3...))). Namely, consider the following system of equations: x 0 = (al,xl) X 1 = (a2,x2)

x2 = (a3,x3)

(We leave it to the reader to convert this intuitive description into the form d e m a n d e d by o u r version of the Solution Lemma.) If we take the solution to this set of equations, t h e n obviously the value assigned to the u n k n o w n x 0 is the desired stream. Next, recall our example concerning databases. We a s s u m e a finite set Rel of binary relations together with an assignment R ~ R ~ of finite binary relations to the m e m b e r s of Rel. Let S i z e O f be a n e w relation symbol. Consider the equation x = {(R~a, I R ~ I ) : R E Rel} U {(x, IRel I + 1)},

P r o o f . Let X C X x. A s s u m e X # •. system

C o n s i d e r the

x = {(y,y(x)) : y E X}, w h e r e w e have an equation for each x E X. The Solution L e m m a implies that this system has a u n i q u e solution. But the constant function fl is a solution, so the o n l y solution. Thus, e v e r y y E X is 12 so X = {fl} =12. m

Hypersets as Limits of Well-founded Sets We began this p a p e r with an analogy, b e t w e e n cont i n u e d f r a c t i o n s a n d n o n - w e l l - f o u n d e d sets. This analogy suggests that we s h o u l d be able to look at a set like x = {1,{1,{1,{1 . . . .

}}}}

(6)

as some sort of limit of the well-founded sets: {1}, {1,{1}}, {1,{1,{1}}}, {1,{1,{1,{1}}}}. . . .

(7)

The i n t u i t i o n is that the sets f u r t h e r out in this seq u e n c e are h a r d e r and h a r d e r to distinguish from the given set x. A n u m b e r of people have p u r s u e d this line of investigation. Every set x is pictured by some apg G. By considering a closely related apg, w e m a y assume that G has no cycles (though it might have infinite paths). Thus G is a tree. The basic idea is that this tree should be the "limit" of its finite (hence well-founded) subtrees. The set x we started with should be the limit of the f a m i l y of sets p i c t u r e d b y t h e s e w e l l - f o u n d e d trees. So in order to consider h y p e r s e t s as limits from W F requires the right notion of convergence of trees. THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

39

Under the most natural notion of "limit" one can obtain all of the hypersets in this way. However, limits in this sense are not unique, and taking the limits of all of the trees in the well-founded universe gives a collection of objects that is larger than the universe of hypersets. An offshoot of this work has been the introduction of several different types of partial sets, objects which are set-like but somehow incompletely specified. Several different notions of partial set have emerged, and these are related to different intuitions about the nature of possible memberships. As with work on AFA, this work has led to interesting mathematics.

Epilogue: Where Does the Stuff of Mathematics Come From? For thousands of years philosophers have been wondering about the source and home of mathematical objects. It is easy to make the question seem puzzling indeed. As should be clear from the above, we are mathematical realists: we take mathematics to be about real stuff. Numbers and other patterns are real. So are sets. The challenge is to talk sense about the stuff of mathematics while steering a course between the Scylla of Naive Platonism and the Charybdis of formalism. For the Naive Platonist is committed to a world of mathematical objects i n d e p e n d e n t of humankind, disconnected from the world of experience. As a result, the applicability of mathematics to the world of matter and man becomes rather puzzling, a matter of "participating in ideal forms." The formalist, on the other hand, seems committed to a world without mathematical objects at all, only meaningless symbols. Here the applicability of mathematics is even more of a mystery. To us, one of the exciting aspects of recent development in hypersets and their theory is that it serves as a case study in this age-old debate. It seems that neither Platonism nor formalism gives an adequate insight to the history as it is actually unfolding. Indeed, we think this unfolding shows how we can be realists without being Platonists. Where did h y p e r s e t s come from? A mixture of places. In some ways, they arise out of the desire to use a certain set of tools in modeling significant realworld phenomena in the areas of computer science, cognitive science, and philosophy. It is of course fundamental to science that mathematical models of realworld phenomena can enrich our understanding of the phenomena. But more important for mathematics is the flip side. The need to create such models sometimes enriches mathematics by bringing to light new abstract patterns that need to find a home in the universe of mathematical objects. And this is certainly a major part of what is going on here. 40 THE MATHEMATICALINTELLIGENCERVOL. 13, NO. 4, 1991

A different and more subtle source of mathematical ideas is the whole array of assumptions, metaphor, taste, a n d a n a l o g y that m a t h e m a t i c i a n s (we are people, after all, in spite of what the public thinks) bring to the experience of mathematics. It is easy to neglect this aspect or to pretend that it isn't there, but when we do this we lose much of the motivation for and h u m a n essence of mathematics. In our case study, this neglect can obscure the nature of conventional set theory. But w h e n push comes to shove, we must admit that the cumulative notion of a set is deeply rooted in a metaphor, one that can guide us but is simply not rich enough to settle all questions of set theory. And it is not the only metaphor around. Hypersets are based on an alternative metaphor, one that gives rise to an alternative conception of set. The question of taste comes up here, too. Some settheorists find the cumulative picture ultimately more satisfying. Others find the elegance and versatility of the Solution Lemma irresistible. (And of course category-theorists find set theory more or less beside the point.) Choosing between them is both a matter of taste and a matter of expedience. Finally, there is the matter of analogy. Analogy plays a large role in the development of mathematics. We know how things go in one domain and try to make things go analogously in another. In the case of h y p e r s e t s , a m o t i v a t i n g a n a l o g y is the different number systems: rationals, reals, and complexes. Each is an extension of the ones that come before. Certain nice properties are lost in the extension. The complex numbers have no nice ordering, for example. On the other hand, each extension allows us a space in which to solve equations that were not solvable before, and so to solve certain real-world problems that were not solvable before. Similarly, the hyperreals of infinitesimal analysis constitute an extension of the reals where certain systems of equations and inequalities that don't have "real" solutions do have solutions: What the extensions of the number systems and set theories have in common is that in making the extension, we lose none of the original objects, but we gain solutions to interesting s y s t e m s of equations. In making the extension in the set-theoretic case, we lose the nice hierarchical picture, 6 but instead we have the view that sets are exactly the objects pictured by apg's. In this way, we gain sets that allow us to solve new equations, and so model new phenomena. And just as the reals can be modeled as equivalence classes of Cauchy sequences of rationals, so too the hypersets 5 See t h e p r e s e n t a t i o n in Keisler [14], for example. 6 Actually, t h e r e is a w a y to h a v e a s p e c t s of both views. By the A x i o m of Choice, every a p g is i s o m o r p h i c to an a p g w h o s e n o d e s are w e l l - f o u n d e d (indeed ordinals). So o n e can h a v e the view that the a p g ' s are built in stages, a n d only after all of t h e m h a v e b e e n created, t h e sets a p p e a r as decorations.

can be modeled as equivalence classes of apg's. In both cases, these constructions convince us that there is nothing really ontologically suspicious going on. The analogy even extends into the sociological dimension. There were times w h e n V'2 and i were viewed with great suspicion, even rancor. Nowadays we don't think twice about them, except in teaching wary undergraduates. More recently, the discovery of the infinitesimals led to some name-calling by otherwise sensible people. Similarly, sets like f~ and the stream (0,~1,~2. . . . ~ were until recently viewed as non-entities. Nowadays we are coming to understand them for what they are, perfectly good sets under a richer conception of set. The two of us feel that as more and more applications of hypersets are found, they are going to find their way into everyday mathematics. In twenty years, introductory books on set theory will have to have a chapter on them. They are no more irrational than the irrational numbers and no more imaginary than the complex numbers. They are darned useful. And better still, the universe of hypersets is a charming one in which to pursue some lovely mathematics.

Some Remarks on the Literature The theory of non-well-founded sets is studied in detail in Aczel's book [2]. This book also contains a detailed bibliography and a discussion of their history. A more elementary introduction can be found in Chapter 3 of [8]. Some more recent theory of hypersets can be found in Chapter 12 of [5], and theories of approximations to hypersets can be found in [1] and [17]. For a general discussion of the two metaphors for sets, and the need for non-well-founded sets for modeling circular phenomena, see Chapter 8 of [5]. At the present time, we are only just beginning to see applications of hypersets. We expect to see m a n y more in the years to come. Here are some references: 9 To the theory of concurrency: Chapter 7 of [2]. This is a mathematical model of processes that communicate with each other in the course of a computation, inspired by large parallel computers composed of many small parts. The notion of a bisimulation can be found in this area, first in the work of Park, though it had antecedents in the set-theoretic and model-theoretic literature. 9 To database theory: [6] 9 To the semantical paradoxes: [8]. The semantic paradoxes include the Liar Paradox ("This sentence is false."), and also Richard's Paradox ("the first non-definable number"). Like the set-theoretic paradoxes, the semantic paradoxes seem to involve circularity. The standard m o d e r n treatment is to impose some sort of hierarchy on the world, and thereby claim that the circularity is only apparent. In contrast, [8] advances the view

that the circularity is genuine, and that it can be understood coherently once we have mathematical tools like AFA for modeling it. 9 To the theory of common knowledge: Chapter 9 of [5]. Suppose two people are making bids at a public auction. Their behavior is different than it would be if they made their bids privately, because each is aware that the other is aware of the entire situation. The analysis of common knowledge has been controversial and problematic in the philosophy of language. It also comes up in theoretical economics. 9 To theoretical and computational linguistics: Barwise [5] and Rounds [18].

References 1. Samson Abramsky, Topological aspects of non-wellfounded sets, to appear. 2. Peter Aczel, Non-well-founded Sets, CSLI Lecture Notes, Chicago: University of Chicago Press (1988). 3. Jon Barwise, Admissible Sets and Structures, New York: Springer-Verlag (1975). 4. Jon Barwise (ed.), Handbook of Mathematical Logic, Amsterdam: North-Holland (1977). 5. Jon Barwise, The Situation in Logic, CSLI Lecture Notes, Chicago: University of Chicago Press (1989). 6. Jon Barwise, review of [12], Journal of Symbolic Logic 54 (June, 1989). 7. Jon Barwise, Consistency and logical consequence, Truth or Consequences, Dunn and Gupta, eds., Dordrecht: Kluwer Academic Publishers (1990). 8. Jon Barwise and John Etchemendy, The Liar: An Essay on Truth and Circularity, New York: Oxford University Press (1987). 9. Paul Bernays, Axiomatic Set Theory, Amsterdam: NorthHolland (1958). 10. Paul Cohen, Set Theory and The Continuum Hypothesis, New York: W. A. Benjamin (1966). 11. Abraham A. Fraenke|, Yehoshua Bar-Hillel, and Azriel Levy, Foundations of Set Theory, Amsterdam: North-Holland (1973). 12. Barry Jacobs, Applied Database Logic I, Englewood Cliffs, NJ: Prentice-Hall (1985). 13. Mark Johnson, Attribute-Value Logic and the Theory of Grammar, CSLI Lecture Notes, Chicago: University of Chicago Press (1988). 14. H. Jerome Keisler, Elementary Calculus, Boston: Prindle, Weber and Schmidt (1976). 15. Kenneth Kunen, Set Theory: An Introduction to Independence Proofs, Amsterdam: North-Holland (1980). 16. James D. McCawley, Everything Linguists Want to Know about Logic but are Afraid to Ask, Chicago: University of Chicago Press (1981). 17. Michael W. Mislove, Lawrence S. Moss and Frank J. Oles, Non-welMounded sets modeled as ideal fixed points, to appear in Information and Control 18. William C. Rounds, Complex objects and morphisms I. A set-theoretic semantics, Situation Theory and its Applications II, to appear. 19. Joseph Shoenfield, Axioms of set theory, in [4], 322-344. Department of Mathematics Indiana University Bloomington, IN 47405 USA THE MATHEMATICAL INTELLIGENCER VOL, 13, NO. 4, 1991

41

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.

The Bourbaki Panorama, Lucerne Ian Stewart "His name is Greek, his nationality French, and his history is curious." So wrote Paul Halmos of Nicolas Bourbaki, a name that needs no introduction to mathematicians. There is speculation that the pseudonymous collective author was christened after General Charles Denis Sauter Bourbaki, who played an important role in the Franco-Prussian war. True Bourbakistes should therefore make the pilgrimage to Lucerne, Switzerland, where they will find the magnificent Bourbaki Panorama. The huge panorama covers 1100 square metres. The scene is the valley of Travers in the Winter of 1870/71. The Bourbaki Army (French Eastern Army) is crossing the frontier into Switzerland, seeking asylum. It was sent to relieve the siege of Belfort, but was defeated after a three-day battle by the German generals Manteuffel and Werder. Bourbaki, disgraced, planned suicide, and was replaced by general Clinchant, who led the army back to the Swiss border by way of Besan~on and Pontarlier. At the left of the panorama the Bernese battalion is arriving to reinforce the Swiss contingent. The people of the valley of Travers are seen bringing help to the soldiers, against a backdrop of railway wagons. A s e e m i n g l y e n d l e s s c o l u m n of F r e n c h w o u n d e d struggles through the snow, and to their right the

* C o l u m n Editor's address: Mathematics Institute, University of Warwick, Coventry CV4 7AL England.

42

Bourbaki Army lays d o w n its w e a p o n s in a heap. Cows and a few Swiss soldiers watch mutely from behind low stone walls. It took seven artists two years to complete the panorama, their leader being Edouard Castres, who spent the winter of 1876/77 in Les Verri6res making studies of the scene. Castres himself crossed the Swiss frontier as a medical corpsman in the Bourbaki Army. The panorama was displayed in Geneva for ten years, but in 1889 it moved to Lucerne. The Panorama is open between 9.00 and 17.00 in March, April, and October; and between 9.00 and 18.00 M a y - S e p t e m b e r . To find it, start from the railway station and follow the Seebriicke north to Schwanenplatz; turn right along Schweizerhofquai and then left into LOwenstrasse. Turn right at the far end. (See map.) For further information see Swissair Gazette for September 1986, which is devoted to Swiss panoramas. Help Needed! For some time water has been leaking

through the roof onto the 102-year-old monument. The Verein zur Erhaltung des Bourbaki-Panoramas Luzern (Society to Preserve the Bourbaki-Panorama of Lucerne) is planning extensive restoration. Donations and other assistance will be greatly appreciated. Write to the address in caption, p. 43. Mathematics Institute University of Warwick Coventry CV4 7AL United Kingdom

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4 9 1991 Springer-Verlag New York

Edouard Castres and his colleagues in front of their masterpiece. On the left: four models; behind them Henri Silvestre; sitting Ferdinand Hodler; behind him two Belgian specialists in panorama painting; behind them Louis Dunki; in foreground with palette Roy Parisien; behind him Gustave Beaumont; in the background William-Henri H4bert, Aim6 Nicolas Morort, and Fr4d6ric Dufaux. Edouard Castres is inset in the lower right corner. The photographs are courtesy of the Verein zur Erhaltung des Bourbaki-Panoramas Luzern, % Kantonale Denkmalpflege, Murbacherstrasse 23, 6002 Luzern, Switzerland.

How to find the Bourbaki Panorama.

Detail: the French lay down their arms. THE M A T H E M A T I C A L INTELLIGENCER VOL. 13, N O . 4, 199I

43

Computer Programs and Mathematical Proofs Robert Gray

In his Mathematical Intelligencer article [2] about computer science and mathematics, E. W. Dijkstra states that "the techniques of program design h a v e . . , successfully been applied to proof design." This article provides examples of Dijkstra's statement.

The Heine-Borel Theorem If a closed interval is covered by a collection of open sets, then the Heine-Borel theorem guarantees that the interval can be covered by a finite subcollection of these sets. The standard proofs do not construct this finite subcover; they infer its existence from a contradiction. But a finite subcover can be easily built using the programming strategy named divide-and-conquer [1, p. 306-311]. This strategy builds the subcover by dividing the interval into half, building a finite subcover for each half, and then taking the union of these subcovers. Of course, we may need to repeat these operations on the half intervals, on their half intervals, and so on. These operations are succinctly summarized in the recursive procedure:

procedure subcover ([x, y], Subcover); begin if [x, y] C Open where Open C C then Subcover := {Open}

else begin subcover ([x, (x + y)/2], Subcoverl); subcover ([(x + y)/2, y], Subcover2); Subcover := Subcoverl U Subcover2;

end end; H o w do we know that this procedure terminates? And that it produces a finite subcover? Answering these questions requires a mathematical proof about its behavior. This proof uses the procedure's call tree, which is formed by the procedure calls that occur

procedure subcover ([x, y], Subcover); begin subcover ([x, (x + y)/2], Subcoverl); subcover ([(x + y)/2, y], Subcover2); Subcover := Subcoverl U Subcover2;

end; Unfortunately, this procedure never terminates--it just keeps dividing intervals in half. We need a termination condition that tells the procedure when to stop dividing intervals. Let C be an open cover of [a, b], and consider the question: "When is it obvious that an interval [x, y] is covered by a finite subset of C ?". The a n s w e r - - w h e n the interval is covered by a single set of C--provides the termination condition for our improved procedure: THE MATHEMATICAL [NTELLIGENCER VOL. 13, NO. 4 9 1991 Springer-Verlag New York

45

s u b c o v e r ([1, 2], { I 1, 11.5, I1.85 } )

subcover ([1, 1.5], { I 1 } )

subcover ( [1.5, 2], { 11.5, 11.85 } )

subcover ([1.5, 1.75], { I1.5 } )

subcover ([1.75, 2], { 11.85 } )

Figure 1. A call tree of procedure subcover with interval [1,2] and cover {Ix : Ix = (x -

1/x3, x + 1/x3), x @ I1,21}. when it runs. Figure I shows a call tree that is generated when procedure subcover works with the interval [1, 2] and the cover {Ix : I x = (x - 1/x 3, x + 1/x3), x E [1, 2]}. To prove that procedure subcover terminates, we show that its call tree is finite. The proof is by contradiction. Assume that the call tree is infinite. K6nig's lemma states that every infinite, finitely branching tree has an infinite path. Hence, our call tree has an infinite path. This path consists of subcover calls that do not satisfy the termination condition. The endpoints of the input arguments of these calls form a pair of nested sequences, x n and y,, such that ~ (yn - x,) = 0. Let x = lim xn = lim y,. Since [a, b] is a closed interval, x is in [a, b]. So x belongs to an open set A of the cover C. For some N, [xN, YN] _C A. Thus, the interval [xN, YN] satisfies the procedure's termination condition and we have our contradiction. To show that the procedure outputs a finite subcover of [a, b] requires a simple induction starting at the leaf nodes of the call tree. Our proof of the Heine-Borel theorem shows an interplay between computer science and mathematics. C o m p u t e r science suggested the procedure, while mathematical arguments showed that the procedure behaved in the desired way. (We could eliminate the computer science part by rephrasing the proof, but then we would eliminate the proof's inspiration.) Procedure subcover is as constructive as its input and termination condition. However, its termination proof is non-constructive. This proof was by contradiction and it used two properties of infinite sets: K6nig's lemma and the existence of a limit point for a pair of converging nested sequences. There are other examples of termination proofs that require properties of infinite sets. A d r a m a t i c e x a m p l e c o m e s f r o m Friedman's analysis of Kruskal's theorem [6]. Consider any program that produces a sequence of finite trees and terminates when it finds a pair of trees such that one can be e m b e d d e d in the other. Kruskal's theorem implies that all programs of this type will terminate. Friedman's analysis shows that this termination proof requires strong assumptions about infinite s e t s - - t h e proof cannot be done in ordinary number 46

THE MATHEMATICALINTELL1GENCERVOL. 13, NO. 4, 1991

theory. In fact, it cannot be done in predicative mathematics. N o t e that the t e r m i n a t i o n p r o o f of p r o c e d u r e subcover is essentially the same as Borel's second proof of his theorem.* This similarity raises some interesting questions. Are there other indirect existence proofs that can be converted to termination proofs of computer programs? Can all indirect existence proofs be converted to termination proofs? To have any hope of answering this last question affirmatively will require a broadening of the concept of computer program. Integration

The divide-and-conquer strategy we used to construct a finite subcover was named by computer scientists, but mathematicians have been using it for centuries. For example, the area under a curve is approximated by dividing the interval under the curve into smaller and smaller subintervals until the curve is nearly constant over these subintervals. The area between the curve and one of these subintervals is very close to the area of a rectangle. The area under the entire curve is approximately equal to the sum of the areas of these rectangles. This old method of approximating an area leads to procedure integral in Figure 2. This procedure outputs Lower and Upper, which bound the integral f~f(t)dt. The recursive part of our procedure (lines 10-13 in Figure 2) computes these bounds by dividing the interval into half, computing bounds for each half, and then adding the bounds from each half together. The termination condition (line 3 in Figure 2) tells our procedure w h e n to stop dividing intervals. This condition checks to see if the values of f on the interval Ix, y] are within e of f ( x ) . If t h e y are, then the integral is bounded by (f(x) - ~)(y - x ) a n d (f(x) + ~)(y - x). Using procedure integral, we n o w prove that a function that is continuous on a closed interval is Riemann integrable on the interval. Our proof requires little * See [4, p. 20-25] for a discussion of the early proofs of the HeineBore! theorem.

procedure integral (Ix, y], e, Lower, Upper); begin if I f ( x ) - f ( t ) l < e for all t ~ [x, y] then begin Lower := ( f ( x ) - E ) * ( y - x ) ; Upper := (f(x) + e)* ( y - x ) ; end else begin integral ( [x, (x + y) / 2], ~, Lowerl, Upperl ); integral ( [(x + y) / 2, y], e, Lower2, Upper2 ); Lower := Lowerl + Lower2; Upper := Upperl + Upper2; end end; Figure 2. A procedure for calculating integrals of continuous functions.

procedure integral([x, y], e, Ik, Lower, Upper); begin if I f ( x ) - f ( t ) l < e for all t ~ Ix, y] then begin Lower := ( f ( x ) - e ) * ( y - x ) ; Upper := (f(x) + e)* ( y - x ) ; end else if [x, y] ~ I k for some k then begin Lower : = - M * ( y - x ) ; Upper := M* (y - x); end else begin integral ( [x, (x + y) / 2], e, I~, Lowerl, Upperl ); integral([(x+y)/2, y], e, I k, Lower2, Upper2); Lower := Lower1 + Lower2; Upper := Upperl + Upper2; end end; Figure 3. A procedure for calculating integrals of bounded, almost everywhere continuous functions.

b e y o n d the definitions of c o n t i n u o u s function and Riemann integral. Once again, we begin with a termination proof. Let f be continuous on [a, b]. Run procedure integral with input [a, b] and e. If the procedure does not terminate with these input arguments, then its call tree is infinite. Use K 6 n i g ' s l e m m a to extract an infinite sequence [xn, Yn] of nested intervals from the call tree. The endpoints of these intervals have a limit x. Since f is continuous at x, there is a ~ such that Ix - t I < implies If(x) - f(t)l < e/2. But some interval [xN, YN] in

the nested sequence sits inside the open set {t: Ix - t I < 8}. For all t in this interval, If(xN) -- f(t)l < e. Thus, the interval [xN, YN] satisfies the procedure's termination condition and we have our contradiction. An induction through the call tree shows that the o u t p u t arguments, Lower and Upper, are the integrals of step functions b o u n d i n g f such that Upper - Lower = 2e(b - a). For those w h o prefer to do integration with Riem a n n s u m s rather t h a n step f u n c t i o n s , p r o c e d u r e integral can be modified so that its o u t p u t b o u n d s these sums. Run the procedure with input e, and let be the m i n i m u m size of the intervals in the leaf nodes of the call tree. Consider a n y partition P of [a, b] w h o s e m e s h size is less than 8. The o u t p u t arguments, Lower and Upper, might not b o u n d all Riemann sums over P. However, if we modify the procedure by replacing with 2e in the first pair of assignment statements (lines 5 - 6 in Figure 2), t h e n the o u t p u t a r g u m e n t s will b o u n d these sums. Our proof of integrability is more direct than most, and it provides a m e t h o d of calculating b o u n d s for the integral. Also, analysis of our procedure's behavior leads to proofs of several w e l l - k n o w n properties of continuous functions. Procedure integral recursively halves its first argument, its interval argument, until reaching intervals that satisfy the termination condition. These intervals are at the leaf nodes of the call tree and their union is [a, b]. Thus, we have divided [a, b] into subintervals that satisfy the termination condition. This result can be translated into a theorem about partitions. Recall that a partition of [a, b] is a finite set {x0, x 1. . . . . xn-1, xn} w h o s e members satisfy: a = x0 < x 1 < . . . < x , _ 1 < x, = b. This partition divides [a, b] into subintervals Ix i, xi+l]. We can n o w rephrase our result: Theorem. Let f be continuous on [a, b]. For every e > 0, there is a partition P, = {x0, x 1. . . . . x,_ 1, x,} dividing [a, b] into subintervals [xi, Xi+l] such that if t ~ [x i, xi+l], then If(xi) - f(t)l < ~.

Each P, is a finite set such that the values of f on P, approximate the values of f on [a, b] to within ~. The P, partitions can be used to construct simple proofs that f is b o u n d e d , uniformly continuous, and attains a maxi m u m a n d a m i n i m u m on [a, b]. (See [3] for details.) Another advantage of our integrability proof is that a small modification in our procedure leads to the proof of a stronger theorem. By adding another input a r g u m e n t a n d another termination condition to procedure integral, we obtain a procedure that can be used to prove Lebesgue's well-known theorem: A function that is b o u n d e d and almost everywhere continuous on a closed interval is Riemann integrable on the interval. The n e w procedure is given in Figure 3. Once again, we m u s t prove termination. Let f be continuous alTHE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

47

most everywhere on [a, b], let Ifl ~ M on [a, b], and let I k be a sequence of open intervals covering f's discontinuities such that ~ = 1 length (Ik) < ~'. Run the new procedure with input arguments [a, b], e, and I k. If the procedure does not terminate with these input arguments, then its call tree is infinite. Use K6nig's lemma to extract a sequence [xn, y,] of nested intervals whose endpoints have limit x. If f is continuous at x, then the argument in our last termination proof provides a contradiction. If f is not continuous at x, then x E I k for some k. For some N, [x N, YN] C I k. Thus, the interval [XN, YN] satisfies the procedure's second termination condition and we have a contradiction. An induction through the call tree shows that the output arguments, Lower and Upper, are the integrals of step functions bounding f such that oo

Upper - Lower ~ 2~(b - a) + 2M ~ length(Ik) k=l

< 2e(b - a) + 2Me'. Note that all of our termination proofs use K6nig's lemma. The work of Friedman and Simpson on reverse mathematics [5] shows that a weak version of this lemma is needed to prove the theorems in this article. Reverse mathematics begins with an axiom system, called RCA0, that captures the computable reasoning used in analysis. Next KOnig's lemma is restricted to binary trees consisting of finite sequences of O's and l's. The resulting lemma is known as the weak K6nig lemma. It is straightforward to rewrite the proofs in this article using the axiom system RCA 0 and this lemma. But reverse mathematics shows that the flow of reasoning from lemma to theorem can be reversed. Namely, within the axiom system RCA0, each of the t h e o r e m s in this article implies the weak K6nig lemma. This means that these theorems are of the same logical strength as the weak K6nig lemma, and hence this lemma or some equivalent is required for their proofs. (Technical note: Because the axiom system RCA0 only handles countable reasoning, reverse mathematics restricts the Heine-Borel theorem to sequences of open intervals.)

Conclusion This article was written to illustrate an interplay between computer science and mathematics in the hope of lessening the "cultural gap" described by Dijkstra [2]. More illustrations can be found in [3]. Many mathematicians may prefer the old proofs over the ones presented here. But what about the next generation of mathematicians, who are growing up with personal computers? A simple exercise should provide insight into their preferences. N a m e l y , 48

THE MATHEMATICAL INTELLIGENCER VOL, 13, NO, 4, 1991

present the following three proofs of the Heine-Borel theorem to a class of mathematics students: One of the standard proofs (either the bisection proof or the least upper bound proof), the proof in this article that uses procedure subcover, and a rephrasing of this proof that avoids procedures (using a bisection that terminates when the subinterval fits within a member of the open cover). Ask the students to rank the proofs in order of their preferences and have them supply reasons for their rankings. This exercise should provide insight into how students view indirect existence proofs and what they think about using a computer procedure to aid in proving a theorem.

References 1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, Massachusetts, 1983. 2. E. W. Dijkstra, On a cultural gap, The Mathematical Intelligencer 8 (1986), 48-52. 3. R. Gray, A programmer's view of elementary analysis, unpublished. 4. M. F. Hallett, Towards a theory of mathematical research programmes, British Journal for the Philosophy of Science 30 (1979), 1-25 and 135-159. 5. S. G. Simpson, Reverse mathematics, Proceedings of Symposia in Pure Mathematics, vol. 42, Amer. Math. Soc., (1985), 461-471. 6. C. Smoryriski, The varieties of arboreal experience, The Mathematical Intelligencer 4 (1982), 182-189. Prime Computer, Inc. 500 Old Connecticut Path Framingham, MA 01701 USA

David Gale For the general philosophy of this section see vol. 13, no. 1 (1991). Contributors to this column who wish an acknowledgment of their contribution should enclose a self-addressed postcard.

Somos Sequence Update Some readers m a y recall that in the winter issue I reported on some sequences defined by a simple recursion that for unexplained reasons always seemed to yield integer terms. The sequences were originally introduced by Michael Somos and can be described as follows: Given an integer k/> 4 a Somos (k) sequence is characterized by the recursion anan-k

=

Xlan q-

wherer=

1an

k+l

(1)

q- X 2 a n - 2 a n - k + 2

. . . q- X r a n -

r an-k+r

bn =

W h e n I simply refer to Somos (k), I will m e a n a k-sequence in which all the x i a n d initial ag are unity. It was first observed numerically and later proved that Somos 4, 5, 6, 7 always have integer terms whereas Somos 8, 9 and presumably all the rest do not. But there still remains a doubly-infinite family of Somos sequences that appear to have integer terms, although this has not been proved (see winter column for details). Motivated by the Somos p h e n o m e n a , Dana Scott discovered that sequences with initial values unity and the following recursions have integer terms: k =

2

an-1

+

2

an_ 2 +

999

+

a 2n - k + 1

. . .

(2) (3)

anan-k = a n - l a n - 2 + a n - 3an-4 -f-

q- a n _ k + 2 a n _ k + l

for k odd. The integer property also holds for anan=k

=

an-lan-2 q-

+

an-k

(4)

q- a n - 2 a n - 3

. . . q- a n _ k + 2 a n _ k +

1

Proofs of integrality of (2), (3) and (4) have n o w been f o u n d by Raphael Robinson with an assist at one point

*Column editor's address: D e p a r t m e n t o f M a t h e m a t i c s , U n i v e r s i t y California, Berkeley, C A 9 4 7 2 0 U S A .

(5)

2 . . . an-k+1

and the claim is that the bn are constants, that is, bn+ 1 = b,. To see this note that an(an + an-k) = (an+l + a n - k + l ) a n

a k - 1.

anan-

an an_lan-

[~]andthexiaregivenintegers.

Since in (1), a n is defined in terms of the preceding k terms, one must choose initial values for a 0, a 1. . . . .

of

from Dean Hickerson. The proofs are quite elementary, so we will present the one for (2), the a r g u m e n t for (3) and (4) being similar. They involve finding rational functions that are invariant u n d e r the recursions. For (2) we define a new sequence (bn) for n / > k by

k+l

(6)

2 because from (2) both sides of (6) are equal to a2n + a,_ 1 + + a 2n - k + 1 . Dividing both sides by a n a n 1 . . . an_k+ 1 gives bn = b,+ 1. But from the initial conditions bk = k hence bn = k, so from (5) we have 9

9

9

a , = k ( a n _ l a n _ 2 . . . an_k+ 0 - a , _ k

(7)

which gives a n e w recursion for the a n where the righth a n d side is a polynomial (rather t h a n a rational function) of the a i, so integrality follows, as does the fact that the sequence reduced m o d m is periodic for any m. But while some problems have n o w been solved, further numerical explorations by Robinson brought to light a host of n e w structural properties of Somos sequences, some of them number-theoretic, others analytic. Since these results will appear elsewhere, I will just mention a few of them. First, as m e n t i o n e d at the end of the earlier column, all Somos sequences that give integers appear to be periodic w h e n reduced rood m for any m. Robinson proved this for Somos 4 and 5 but not for 6 and 7. For 4 and 5 the period as a function of m seems unpredictable, but the following striking relation was observed: For all m except 2 the period rood m k is equal to m k - 1 times the period m o d m. For 2 a s o m e w h a t more complicated pattern holds. (At this point I will stop qualifying e v e r y s t a t e m e n t w i t h "seems to," which is to be understood.) Robinson also investigated which primes divide the various terms of the sequences and found that for Somos 4 and 5 (but not for 6 a n d 7), the terms divisible by a given prime were equally spaced. Thus in Somos (4) every fifth

THE MATHEMATICAL INTELLIGENCER VOL. 13, N O 4 9 1991 Springer-Verlag New York

49

term is even, every seventeenth term is divisible by 11 and none is divisible by 5, while in Somos (5) every tenth term is divisible by 5 but none is divisible by 7. In a different direction, Robinson investigated analytic properties of the sequences for arbitrary k and initial values and found in all cases tested that there were (unique) constants C and D such that an = C ~n-D)2 ~(n)

(8)

where 6(n) has an oscillation with a well-defined period. The constants C and D depend on the initial values as well as on k but in an apparently unpredictable manner. Learning of Robinson's data, Clifford Gardner succeeded in finding explicit formulas for Somos 4 and 5 in terms of Jacobi elliptic functions, so in some sense the problem is starting to come full circle, since Somos originally discovered his sequences while studying properties of elliptic functions and was aware of some of the phenomena described here. To a non-expert the analytic and number-theoretic properties of the Somos sequences seem unrelated, but perhaps algebraic-number theorists who are accustomed to such things will be able to make a connection. In any case, it is intriguing to see more and more properties of these sequences being revealed by numerical exploration.

Unconditionally Secure Protocols One of the exciting mathematical developments of the past decade was the discovery of so-called uncrackable public key codes. These are codes with the characteristic that everyone knows the method of encryption, but the amount of calculation required for an outsider to break the code is thought to be beyond present computational capabilities. In the best-known example, breaking the code was equivalent to being able to find the factors of, say, a 100-digit number, which was believed to be computationally infeasible. A more recent but less well known development with somewhat the same flavor involves methods of conveying certain information that depends on other information that must remain secret. In these cases, however, it is literally impossible for anyone but a mind-reader to learn the secrets. Here is a simple example. Some people P1. . . . . Pn, say, the members of a mathematics department, are interested in learning their average salary but they are not willing to reveal their own salaries to anyone else. How can this be done? I put the problem to some of my colleagues and they were not able to come up with an answer. I also mentioned it at a social gathering and rather quickly a young woman who h a d n ' t had a mathematics course since high school (and claimed she'd failed 9th grade algebra) proposed the following simple solution: P1 chooses an arbitrary number x and tells it to P2 who adds his salary and tells the total to P3 who adds her 50

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

Some people P1, 9 9 P , , say, the members of a mathematics department, are interested in learning their average salary but they are not willing to reveal their o w n salaries to anyone else. H o w can this be done? salary and tells it to P4, and so on, until Pn adds his salary and tells it to P1 who adds her salary, subtracts x, divides by n and announces the result. Clearly no one has learned anything about anyone else's salary except what can be inferred from knowing the average. Now while it is true that in the above scheme no person acting alone can discover anything about the other people's salaries, the situation changes if people are allowed to collude. For example, if P1 reveals x to P3 then P3 will know P2's salary. Thus the scheme, or protocol as it is called, is said to be 1-private but not 2-private. One may then ask if there are any 2-private protocols for this problem. The answer is that, in fact, there is an n-private protocol which is also easy to describe. A protocol is called n-private if no subset of the people by colluding can learn anything about the complementary set except what can be inferred from their knowledge of the average. Here is how it works. Let s i be the salary of Pi. Each Pi chooses n numbers sij subject only to the condition that they sum to si, and deals sij to Pj. Now each Pi announces the sum tj of the numbers in his hand. The sum of the tj is of course the sum of the si, as desired. The situation is represented by the matrix S = (sij) where the/th r o w sum is Si and t h e jth column sum is tj.

S1

t1

t2

tk

t.

$11

$12

Slk

Sln

Skl

Sk2

$2

Sk

Skk

Skn

Sk S.

Snl

Sn2

SHtz

To see that the protocol is n-private, suppose, say, the first k players collude. Then they will know all entries of S except those in the lower (n - k) x (n - k) submatrix Sk and they will know as well tk+ 1. . . . . t n, SO they will know the column sums of S k. But if one knows only the column sums cj of a matrix then the row sums r i can be any numbers subject only to the

condition Y~r i = Y~Cj, SO the colluding players will know only the sum of the other players' salaries, which they would know anyway from knowing the sum of all the salaries. The sum protocol can be used to learn other things, for example, the distribution of salaries, that is, the number of people at each salary level, without revealing who they are. To find out how many people have salary x, do the sum protocol where Pi's secret number is 1 or 0 according as his salary is or is not equal to x, and repeat the protocol for all values of x. A more efficient method is for Pi to choose the secret number (n + 1)si. When the sum is computed it is expressed in base (n + 1) and the coefficient of (n + 1)x will be the number of people whose salary is x. The same trick can be used for a secret ballot. Suppose the candidates for some office are labeled 1 through m. A person who wants to vote for candidate k should use the secret number (n + 1)k. The sum protocol then gives the vote count. What about other functions? For example, the maximum rather than the sum of the salaries? If an upper bound ~ of the salaries is known the following procedure suggests itself. Use the sum protocol to find out how many people have salary ~. If the answer is zero try again with ~ - I and so on until the sum is positive. The trouble is that one learns too much. One learns not only the maximum salary but also the number of people who earn the maximum. Is it possible to learn the maximum and nothing more? In the same spirit, is it possible to learn only the winning candidate(s) in an election but nothing about the distribution of votes? And a simple arithmatical question: the sum of n numbers can be computed n-privately--What about the product? The answer to all of these questions is the same and is quite surprising. There exist t-private protocols for all of them if and only if t is less than n/2. Such protocols might be called minority-private. The existence of minority-private protocols was proved by Ben-Or, Goldwasser, and Wigderson [2] and independently by Chaum, Cr6peau, and Damgard [3]. Given secret numbers s1. . . . . sn that may take on some finite set of values, it is shown that any function of the s i can be computed minority-privately. It suffices to consider functions on a sufficiently large finite field. A minorityprivate protocol is given for multiplication, which is somewhat more complicated than that for addition. (Everything we have described up to now could probably be understood by a competent 7th grader. The multiplication protocol is about at the level of an undergraduate abstract algebra course.) Once one has addition and multiplication, one has polynomials and hence all functions on a finite field. It seems to be the case that by suitable encoding most problems of the sort one is interested in can be transformed into a problem of calculating a function from integers to integers,

although this is not immediately obvious, for example, in the secret-ballot problem where one wants to know only which candidate won the election. Perhaps even more striking than the sufficiency is the necessity of the condition t < n/2. This means there is no protocol, for example, for computing the product of n secret numbers that can maintain secrecy if half or more of the participants decide to collude. In fact, essentially the only functions that can be computed majority-privately are functions that can be obtained using only the sum protocol. This was first shown by Chor and Kushilevitz [4] for Boolean functions and then by Beaver [1] for general integer-valued functions. Notice that we have nowhere up to now said what a protocol actually is, but have simply exhibited examples. This is fine as long as one is proving existence theorems. By way of analogy, to show that there is a "formula" for the roots of third and fourth degree polynomials one simply displays them and checks that they work. On the other hand, in order to show non-existence of such expressions for higher degree polynomials, a strict formalization of the problem is necessary. In the same way, to prove non-existence of majority-private protocols, one must have precise definitions of protocols and privacy and then develop the necessary theory to deal with these concepts; and the arguments are considerably more involved than those for existence. As a special case of Beaver's result we see that when there are only two people, essentially nothing can be learned privately, as, for example, whether they have the same secret number. On the other hand, from the existence theorem we know that if a third party P3 enters the picture and is able to give and receive messages, then P1 and P2 can learn whether or not they have the same number 1-privately, and P3 will not even know whether the answer is yes or no. There is a good deal more to the theory than has been mentioned. For example if one does not require unconditional security but only "uncrackability" in the sense described in the first paragraph, then it has been shown that any function can be computed n-privately, including the situation where there are only two people. In the so-called "millionaires problem" of Yao [5], for example, P1 and P2 can learn which of them has the larger salary and nothing else. To conclude let me return to the 7th grade level and describe a 1-private protocol that computes the maximum salary. For this we bring in an outsider P0 who chooses some secret number x0. The rules are then the following: if Pi's salary is ~ (the upper bound), she chooses some arbitrary positive number x i. If not her secret number is 0. Now do the sum protocol. If the sum is not xo, then P0 announces that ~ is the maximum. If the sum is x0, play again, replacing ~ by ~ - 1, and so on until the maximum is found. Notice that it is necessary to bring in Po because if the others played the game without him and at some stage the sum THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

51

turned out to be x i, then Pi would know that she was the only one getting the maximum. Similarly, the protocol with P0 is only 1-private, because if P0 gets together with a person earning the maximum salary, then the two of them will know whether or not anyone else is also earning this maximum. I want to express my thanks to Donald Beaver of AT&T for much of the material I have presented and to Michael Hirsch of UC Berkeley for bringing this interesting subject to my attention. It seems there are more kinds of mathematics in heaven and on earth than are dreamed of in all your volumes of Bourbaki.

References 1. D. Beaver, Perfect privacy for two-party protocols, Harvard Tec. Report TR-11-89, Aiken Computer Laboratory. 2. M. Ben-Or, S. Goldwasser, and A. Wigderson, Completeness theorems for non-cryptographic fault tolerant distributed computations, Proceedings 20th STOC (1988), 1-10. 3. D. Chaum, C. Cr6peau, and I. Darngard, Multiparty unconditionally secure protocols, Proceedings 20th STOC (1988), 11-19. 4. B. Chor and E. Kushilevitz, A zero-one law for Boolean privacy, Proceedings 21st STOC (1989), 62-72. 5. A. C. Yao, Protocols for secure computation, Proceedings FOCS (1982), 160-164.

A True Story Once upon a time there was a little girl named Clara who was barely three years old and had just learned how to count. She could tell how many chairs there were in the living room and the number of steps down from the front porch. One day her father decided to test her. "Look" he said, "I've brought you these four lollipops," but he h a n d e d her only three. Clara took the lollipops and dutifully counted, "One, two, four." Then she looked up a bit puzzled and asked, "Where's the third one?"

Problems Rational primes: Quickie 91-5 by W. Sierpifiski (submitted by S. H. Weintraub). Call a rational number a prime rational if it is the quotient of (integer) primes. Show that the set of prime rationals is dense in the positive reals.

52

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

Mathematical Notions in Preliterate Societies Walter S. Sizer

In many textbook treatments of the history of mathematics mention is made of counting and tallies in prehistoric times with pictures of notches in bones to provide evidence, but then the jump is made to written records, particularly those of Egypt and Mesopotamia (see, for example, [15], [9]). A few reference books have attempted to look at the development of mathematics and mathematical notions in cultures that had not d e v e l o p e d writing, notably Africa Counts by Claudia Zaslavsky [52] and Native American Mathematics by Michael P. Closs [10]. (Some of the cultures treated in these books were literate, of course, but the majority were not.) B. L. van der Waerden, in Geometry and Algebra in Ancient Civilizations [49], takes the intriguing and highly speculative approach of looking for similarities in the earliest mathematical writings in distant parts of the world and hypothesizing that these similarities stem from a prehistoric mathematical background common to all these civilizations. (The idea evidently goes back to Cantor--see [42].) This approach allows van der Waerden to ascribe a prehistoric setting to the Pythagorean Theorem, for example. The conclusion may seem a bit extreme, but the question is raised: What level of mathemtical development was obtained before societies developed written languages? Similarly, how much of early recorded mathematics is a recording of what was known long previously? Two methodologies for trying to answer these questions suggest themselves, both of which contain difficulties. One approach would be archeological: By examining remains and ruins of prehistoric cultures, the researcher tries to deduce what mathematical concepts they had developed. The second approach, perhaps easier, is anthropological: By studying accounts of present-day or recent societies that have not devel-

oped writing, the researcher tries to determine the extent of their mathematical conceptualization. My approach to the question of the level of mathematics in preliterate societies has been essentially anthropological, concentrating on island cultures from Borneo east through Polynesia. At this stage my interest is still in the question, "How much mathematical development took place before people learned to write?" This report is not intended as a description of the mathematical development of any one group of people but rather a survey of some of the mathematical notions attained in preliterate societies.

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4 9 1991 Springer-Verlag New York

53

Others presently are studying specific areas of mathematics across preliterate societies or mathematical d e v e l o p m e n t s in specific preliterate societies, while my emphasis is on getting a broad perspective. For the use of traditional (mostly preliterate) African geometric patterns in modern mathematical education one should consider the works of Paulus Gerdes [17], [18]. For current work on the history of African mathematics in general the Newsletter of the African Mathemat-

ical Union Commission on the History of Mathematics in Africa is helpful. For further work in geometric designs across cultures and in kinship and other logical relations, the reader is referred to the works of Marcia Ascher [1], [2].

Counting, N u m b e r s , and Computations Several p r e l i t e r a t e societies d e v e l o p e d n u m b e r systems extending to the hundreds of thousands or beyond. Some such societies include the natives of the Society Islands, Samoa, and Tonga in the Pacific ([48], p. 375); the Yoruba, Maasai, and Igbo in Africa ([52], pp. 33, 251, 43); a n d the Dakota, Cherokee, and Ojibway in North America ([10], p. 13). In some instances the large numbers were used in counting objects (for example, with the Yoruba, shells used as money); in some cases it seems that practical counting did not go up to the largest numbers. In some societies counting-games were common; Henry describes as a game a contest in Tahiti to see which of two or three players could count to a given sum the fastest ([24], p. 323). For some groups counting was a specialized activity. Not everyone could count, and special experts were consulted for tasks such as counting the yam harvest (see [50], pp. 226-227). This fact perhaps accounts in part for some of the divergence in reports of how high certain groups were able to count: Consulting ordinary people would give one impression; consulting with an expert in counting would give another answer. The anthropological approach must be used with caution, as illustrated by an example from the Tonga Islands. Natives there gave an early western observer number words up to the quadrillions, only to have it discovered later that the list was accurate only up to the hundreds of thousands, after which they had filled in with other words and nonsense syllables ([11], p. 85; [35], vol. II, appendix, p. xxxi). In the literature surveyed there is essentially no mention of the notion of fractions. The one exception to this is a report of the use of a word for half in Kedang in east Indonesia [4], but even there no further concept of fractions appears in the vocabulary. Simple addition and subtraction are mentioned in relation to several groups, including natives of Duke of York Island in Melanesia ([8], p. 294), the Bontoc Igorot of the Philippines ([27], p. 217), and the natives 54

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

of Kedang [4]. Usually addition and subtraction were done concretely, using stones or twigs to count and either physically combining two totals or removing one from the other. In Kedang, however, with small quantities natives were adept at mental computation. In the account of the residents of the Duke of York Island multiplication and division are also cited as being carried out in the concrete manner. Also, mention is made that the Kedang natives recognized the difference between odd and even numbers. Numbers were recorded in various ways: By using knots in a cord, by using piles of stones or bundles of twigs, by using notches (see for example, [6], p. 457; [12], p. 353). Abilities with numbers are generally well summed up by the following statement of Wolfers about residents of Papua and New Guinea: Generally, then, most Papuans and New Guineans have always been able to count or tally as high and as exactly as they needed, to survive (through being able to calculate how much food to store), to celebrate, to pay or collect their debts, or just to check on what they owned. There was not so much a limit on counting as a limit to the goods and quantities that needed to be counted, or that particular groups of people wanted to measure ([51], p. 82).

Geometric Notions: Euclidean Geometry Preliterate cultures show some awareness of m a n y basic geometric notions, in art, in agriculture, in tools and weapons, in houses, and in other ways. Determining the precise notion of the concept is, however, a difficult task. If a house is roughly circular, or approximately rectangular, do we ascribe to the builders a precise knowledge of circles and rectangles, or only a general n o t i o n ? To a m a t h e m a t i c i a n , r e c t a n g u l a r means (1) the opposite sides are parallel and equal in

Top: Tally using notches in bone; bottom: Tallies using knots in string, piles of stones, bundles of twigs.

length, and (2) the angles are right angles. However, a mathematician, in illustrating a lecture, sketches such a figure only roughly, without even necessarily using a straightedge to ensure straight sides. If the house has the shape of the mathematician's sketch, do we assume the builder and the mathematician have the same notion of a rectangle? In our society with prefabricated building materials and critical expectations, precision in constructing a building with accurate right angles may be more important than in other societies. If we note no attempt by the builder to square the angle (beyond visual approximation), can we conclude that the society could not accurately construct a right angle if it were important? The basic notions of geometry, the straightedge and compass, or the straight line segment and circle, seem widespread in preliterate cultures. The use of cords or vines to measure and transfer distances is widespread, and in at least two cases a stretched cord was used to draw a circular outline for a house ([52], p. 158; [42], p. 555). Straight line segments in construction are frequently obtained by stretching a cord tight to mark the line for a wall (for example, see [28], p. 97). In some s,ocieties, laying out a straight line was a technical skill Of a fairly high level, as the following quotation indicates:

Warriors in N e w Guinea (from Gardens of War: Life and Death in the New Guinea Stone Age, by Robert Gardner and Karl Heider). Note the straight spears. Photograph reproduced with permission of the Film Study Center, Harvard University.

Putting the posts in the ground in a straight line is a skilled job and not every man can do it. There were ten men in a village of two hundred and thirty people who were skilled in this. If a man is not able to do it he gets one of these skilled men to mark off the ground in a straight line with a vine . . . . ([39], p. 186). Line of sight t e c h n i q u e s are u s e d to get straight weapons; accounts are given of the treatments used in crafting spears to r e s h a p e the w o o d so that it is straight ([23], pp. 280-281; [36], pp. 175-176). In photographs, for example, of warriors with ten or fifteen foot spears, one is sometimes struck by the precision crafting used to make the spears straight. Straight line segments appear in numerous other contexts as well, constructed with greater or lesser precision. Circle designs, not necessarily drawn with precision, appear in house shapes, carvings, patterns on cloth and painted on wood, and in other places. In one instance an observer tells of the construction of a "circular" hut, the shape of which was obtained by laying out on the ground a rough pattern of heavy vines and carefully rounding it out ([23], p. 261). The geometric result that in general two lines in a plane determine a unique point was used in egg gathering by natives of the Torres Straits ([21], p. 161). A female sea turtle comes well up on a beach to lay its eggs, smooths the sand around the site, then returns to the water by a different route. By sighting along the track where the turtle came out of the water, and sighting back along the track where the turtle re-entered the water, the natives were able to locate the site

Finding the location of turtle eggs.

of the eggs as the point of intersection. The notion of a rectangle seems widespread, implying notions of parallelism and the right angle. Many cultures build houses on a rectangular plan, and in flat areas garden plots are frequently divided by a rectangular gridwork ([34], pp. 88-89). The notion of parallel straight-line segments seems to take the form of lines everywhere equidistant from each other. In describing construction procedures observers occasionally mention the measuring off of equal distance with stretched cords to align wall supports for a building (ibid., p. 248). Parallelism, in the sense of equidistance, is also observable in patterns involving zigzags, circles, and wavy lines, as evidenced in the carvings, paintings, and cloth designs of many cultures. Right angles also appear frequently. Most often THE MATHEMATICAL INTELLIGENCER VOL, 13, NO. 4, 1991

55

r>
\ Above: Laying house beams in the Caroline Islands. Center, top rows: tattoo motifs from the Cook Islands; b o t t o m row: painted designs from paddle decorations, Cook Islands. From [44], reprinted with p e r m i s s i o n of the Bishop Museum Press.

t h e s e are p r o b a b l y just visual a p p r o x i m a t i o n s , achieved by trying to get equal angles on either side of a joint or trying to fit a mental image of a right angle. The precision of some Mesoamerican right angles in urban layout, however, according to Vinette (in [10]), suggests some intentional construction was used to get the angles. (Actually, Mesoamerican cultures had progressed to a hieroglyphic writing stage, and so had advanced beyond the preliterate stage; however, the knowledge of how to construct right angles may still have been achieved in the preliterate stage.) A geometric technique for constructing accurate right angles seems to have been used in some Maori and Caroline Islands house-building. In the latter case, the builders would set in place parallel side beams for a house, which were intended to extend beyond the ends. Before lashing the end beams in place they would measure the diagonals and adjust the position of the end beam so that the diagonals (and presumably also the side lengths) were equal. The construction was intended to insure square corners ([5], pp. 227, 234; [46], p. 55). Gerdes [17] indicates that a similar procedure is traditionally used by some native groups in Mozambique to construct right angles, and he gives an alternate traditional method used by other groups. In other cultures where precise vertical and horizontal pieces were needed for astronomical readings, plumb lines and rolling rounded objects were used respectively, and right angles obtained ([26], vol. I, pp. 106-109). Other geometric shapes appear commonly also. The diamond shape or parallelogram is common as a decorative motif, as are triangles (for example, see [43], pp. 197-200). The shape consisting of two parallel straight sides and semicircular ends was a commonly used shape for Polynesian residences ([8], p. 25; [47], p. 24; [16], p. 76). Approximations of a regular pentagram appear as tattoo patterns in the Cook Islands ([44], pp. 56

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

\ "n

Determining the inclination of the midday sun.

130-132). Other familiar (to us) and unfamiliar geometric shapes also appear repeatedly as c o m m o n motifs in certain cultures. A curious example, which suggests an u n d e r standing of similar right triangles, occurs among some tribes on Borneo. The context involves attempting to predict the start of the dry season (which usually comes in April). One technique involves measuring the length of the midday (shortest) shadow. A vertical stake of p r e d e t e r m i n e d length is used and care is taken to assure its vertical setting by using a plumb line. A horizontal piece is laid out from the base of the stake. Notches mark various lengths on the horizontal, and w h e n the m i d d a y s h a d o w comes to a given notch, the season is announced for clearing land and planting--activities which are most successful if undertaken at the start of the dry season. The person taking the readings of shadow length prepares the equipment. The vertical stake is to stand above the ground by an amount equal to this person's span from outstretched hand to outstretched hand, plus the span from thumb to first finger. The horizontal piece is the length from armpit to outstretched hand, with the critical notch at the middle of the upper arm ([26], pp. 106-108; [40], appendix, p. 209). Assuming people from the same tribe have similarly built, but possibly differently sized, bodies, the approach described uses similar triangles to determine the appropriate inclination of the midday sun. Geometric Notions: Curves, Symmetry, and Coordinates

Other examples of curved shapes show up but with a much smaller frequency than the circle. Curiously, the spiral is a favorite motif of the Maoris of New Zealand. Many Maori carvings show spirals that approximate

the uniform expansion of the polar graph of r = k0 (the spiral of Archimedes) ([32], pp. 54-55; [45], p. 314). In other cultures ovals occur in various contexts (dishes, masks, patterns: see [33], p. 22; or Gerbrands, in [38], pp. 120, 124). Figures formed by the intersections of two circles also appear in patterns ([43], p. 200; [44], p. 406). Two further examples of shapes or curves are worthy of note. One is the string design or "cat's cradle," an amusement that enjoyed seemingly worldwide appeal. Done by one or more individuals with one or more loops of "string," these designs may involve many steps and may get very involved. Typically the loop is caught at corners over one person's fingers and thumb, but toes and the mouth may also be used, and more than one person may help hold the loops of one design. Some string figures are derived from designs used in lashing ([22], pp. 3-4), and in some cultures many different techniques were used in lashing, d e p e n d i n g on the objects being lashed. Dickey ([13], p. 8) reports that at least 346 string designs have been identified in native American groups, 85 in African g r o u p s , 15 in E u r o p e a n and Asian groups, and 405 in South Pacific groups (see also [37]). Another example of curves or designs comes from looking at curves d r a w n in sand or appearing on clothes or as decorations elsewhere. Many examples of these intricate patterns are given in Ascher ([1], [2]), some of which come from the Pacific islands. Of special interest here, evidently, were curved line designs that could be traced continuously in one movement without retracing any part (see also [52], p. 105; [20], p. 130). The arts and crafts of preliterate societies display various kinds of s y m m e t r y and probably indicate s o m e c o n s i d e r a b l e u n d e r s t a n d i n g of s y m m e t r y . Translational, rotational, and axial symmetry are all present and can be found in all possible combinations in planar designs, and symmetry of various sorts in solid crafted objects is also apparent. D. W. Crowe (in [52], chapter 14) identifies the seven possible symmetries for a one-dimensional design and indicates that all seven can be found on the clothwork of the Bakuha tribe (of the Congo or Zaire basin) and on bronzework from Benin. Likewise, in looking at Maori (New Zealand) rafter patterns, Gordon Knight reports that patterns exist showing all seven kinds of linear symmetry [29]. Plane symmetry patterns have also been studied (Crowe, in [52], and [30]), and many of them can be seen in the arts and crafts of preliterate societies. One also sees the development of a primitive notion of coordinates in some preliterate societies. Boyer, in tracing the history of analytic geometry, writes ([7], p. 28): The use of coordinates in a broad sense is without doubt prehistoric. Coordinates are simply magnitudes associated with objects in order to locate them with respect to

Cat's cradle design.

Navigational aid, Marshall Islands.

other objects taken as a frame of reference. Instructions given, or diagrams drawn, to indicate relative positions are in this sense applications of the coordinate principle. Primitive Chaldean star charts are specific and systematized instances of the use of coordinates. Boyer further cites similar practices by early Egyptian and later Greek practitioners. In their navigations Polynesians made use of two such sorts of diagrams. Grids of thin sticks were lashed together with shells attached showing the relative positions of islands, thus giving maps of an area to aid navigators. Some examples of this sort come from the Marshall Islands (see [32], p. 67; [20], pp. 197-198). Also, master navigators learned elaborate sky charts laid out on ceilings with a background grid to help in learning relative locations. Navigators learned relative positions of over 175 stars in this way in the Gilbert Islands ([19], pp. 215 ft.). One could also argue that successful navigation in island groups required a good sense of "direction and magnitude" of voyages necessary to go from one place to another, a sort of intuitive notion of vectors. In [25] it is suggested that certain markers used to determine the sailing direction to nearby islands were adjusted not to point to the destination but to point in the direction to head so that the ocean current drift, together with normal sail power, would bring the boat to the desired destination.

Logical T h i n k i n g and Strategy Signs of logical thought patterns frequently show up in the development of games of strategy, ranging in difficulty from tic-tac-toe to chess. Preliterate societies have many such games, too, although perhaps not in the profusion that we enjoy. To illustrate such games, four examples follow. THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

57

/mDB /B m

Torere board design.

9

9

9

O

9

9

9

9

9

9

9

9

9

9

9

9

9 . . . .

9

9 0

9 9

.

9

I

I

9

s

9

9

9

9

9

I

9

9

9

9

9

9

9

9

I

9

9

9

9

9

9

9

9

9

9

9

9

9

9

9 Q

9 9

9 9

9 9

9 9

m

n

9

9

n

9

9

9

9

9

9

9

9

9

O

9

9

9

9

9

:

:

: ' : - ' .

9 9

9 9

9 9

"

9 9

0 9

--

9 9

9 9

9 9

n

Konane board design.

Main machan board design.

(1) Torere or mu torere (Maori, New Zealand): An eight-pointed star-shaped board (or drawing) is used for this game. It was referred to as an octopus. There were nine positions on the b o a r d - - o n e in the center and one at the tip of each arm or point. Each player had four markers, which at the start of the game were on four adjacent points (the center position was thus vacant). Possible moves were: (a) Move a piece from a point to the vacant center, provided one of the points adjacent to the piece moved is occupied by an opponent's piece; (b) move a piece from a point to a vacant adjacent point; (c) move a piece from the center to a vacant point. The objective is to trap your o p p o n e n t so he/she cannot move (see [31], pp. 129-130; [45], p. 244; [5], p.

137). (2) Main machan (Iban, Borneo): The board for this game consists of 37 positions in the shape of a square with a triangle attached by one vertex to each of two opposite sides. One player has two pieces, the other 28. The one with two pieces can remove the opponent's pieces from the board by jumping them; the player with the 28 pieces tries to hem in the opponent and trap the two pieces (see [31], pp. 127-128, for a complete description of how to set up the board and play the game). (3) Konane (Hawaii): The game of k o n a n e was played on a board with a rectangular grid of indentations in which to place the players' pieces. Boards were not all the same size; examples are recorded of boards with 12 rows of 15 indentations each, with 14 rows of 17 indentations each, and in one unusual example with 10 rows of alternately 6 or 7 indentations 58

THE

MATHEMATICAL

INTELLIGENCER

VOL.

13, N O ~ 4 , 1 9 9 1

Mancala game board design.

each (see [43], pp. 369-370 for descriptions of different board configurations). A marker is put in each indentation, with black and white markers alternating. The first player removes a marker from one of the center spots or a corner; the other player removes an adjacent marker. The color removed by each player d e t e r m i n e s w h i c h color t h a t p l a y e r plays w i t h throughout the game. On subsequent moves a player with his or her markers may jump an adjacent marker of the opponent, and remove the jumped piece. If a player cannot jump an opponent's marker the player loses ([14], pp. 84-85). (4) Mancala Games (Africa, parts of Asia, the West Indies a n d South America, the Philippines): Also called wari in Africa, these games are often played with beans as counters on boards of varying shapes. Perhaps the most common board consists of two parallel rows of six dishes each, with a larger dish at each end. At the beginning four beans are put in each of the twelve dishes making up the two rows. The end dishes are u s e d for c a p t u r e d beans. Each of two players is assigned a row. A move consists of picking up all the beans in a dish in the player's own row, and depositing one in each successive dish (except the end dishes) going counterclockwise. If the last bean is placed in a dish of the opponent, and if that dish had one or two beans in it before the last bean was added, the beans in that dish are captured, as well as all beans in successive opponent's dishes with two or three beans going clockwise until the string of two's or three's is broken. Players alternate turns, and the winner is the one who captures the most beans. (There are numerous further variations which may change the way the game is p l a y e d - - s e e [41] or [53], chapter 11).

Other examples of complex logical relationships can be seen in the kinship groupings that exist in various societies (see [3], for example). In m a n y societies people are assigned a kinship group at birth, usually based on sex a n d the kinship g r o u p of one of their parents. W h e n they grow to marriageable age, choice of a suitable marriage partner is restricted by kinship group: Men of a certain group can marry only w o m e n from a certain other group or groups, or conversely, w o m e n of a certain group are restricted to m e n of a certain other group or groups. The number of groups in a society varies of course with the society, as do rules for assigning an individual to a group a n d rules about marriages. These marriage restrictions serve to prevent marriages between close blood relatives.

8. 9. 10. 11. 12. 13. 14. 15.

Conclusions M a n y preliterate societies show considerable mathematical development. It is not unusual to encounter numeral systems going up to the h u n d r e d s of thousands or higher a n d to e n c o u n t e r some arithmetic ability. M a n y geometric notions are present, including simple forms like circles, lines, rectangles and parallelograms, a n d triangles, Other shapes a n d curves occur with less frequency. Some simpler geometric constructions are carried out, and perhaps some properties of similar right triangles are known. Logical reasoning shows up in kinship relationships a n d in some games of strategy. People seem to develop basic mathematical notions largely in response to w h a t they consider important aspects of life. Large n u m b e r s come up w h e n people n e e d to count higher, w h e t h e r counting shells used as m o n e y or yams harvested and stored or animals. More precise geometric c o n s t r u c t i o n s also e n t e r in o n l y w h e r e the society v a l u e s precision. Part of determining exactly w h a t a society has accomplished mathematically involves finding those aspects of life where the development of mathematical notions was important to the people. References 1. Marcia Ascher, Graphs in cultures: a study in ethnomathematics, Historia Mathematica 15 (1988), 201-227. 2. , Graphs in culture (II): a study in ethnomathematics, Archive for History of Exact Sciences 39 (1988), 75-95. 3. and Robert Ascher, Ethnomathematics, History of Science 24 (1986), 125-144. 4. R. H. Barnes, Number and number use in Kedang, Indonesia, Man 17 (1982), 1-22. 5. Elsdon Best, The Maori as He Was, Wellington: Dominion Museum (1924). 6. Bernice Blackwood, Both Sides of Buka Passage, Oxford: The Clarendon Press (1979) (reprint of the 1935 edition). 7. Carl B. Boyer, History of Analytic Geometry, Princeton

16. 17. 18. 19. 20. 21. 22.

23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33.

Junction, N.J.: The Scholar's Bookshelf (1988) (reprint of 1956 publication). George Brown, Melanesians and Polynesians, New York: Benjamin Blom, Inc. (1972) (first published, 1910). Sir Peter Henry Buck, see Te Rangi Hiroa. David M. Burton, The History of Mathematics, Boston, Allyn & Bacon, Inc. (1985). Michael P. Closs, (ed.), Native American Mathematics, Austin: University of Texas Press (1988). Levi Leonard Conant, The Number Concept, New York: Macmillan & Co. (1931) (first copyrighted, 1896). R. H. Codrington, The Melanesians: Studies in Their Anthropology and Folk-lore, Oxford: The Clarendon Press (1891). Lyle A. Dickey, String Figures from Hawaii, Bernice P. Bishop Museum Bulletin 54, New York: Kraus Reprint (1971) (reprint of 1928 edition). Kenneth P. Emory, The Island of Lanai, Honolulu: Bernice P. Bishop Museum Bulletin (1969) (first published 1924). Howard Eves, An Introduction to the History of Mathematics, fifth edition, New York: Saunders College Publishing (1983). Edwin N. Ferdon, Early Tahiti as the Explorers Saw It: 1767-1797, Tucson: University of Arizona Press (1981). Paulus Gerdes, On culture, geometrical thinking and mathematics education, Educational Studies in Mathe matics 19 (2) (1988), 137-162. , On possible uses of traditional Angolan sand drawings in the mathematics classroom, Educational Studies in Mathematics 19 (1) (1988), 3-22. Rosemary Grimble, Migrations, Myth and magic from the Gilbert Islands: Early Writings of Sir Arthur Grimble, Boston: Routledge & Kegan Paul (1972). Enrico Guidoni, Primitive Architecture (Robert Erick Wolf, trans.), New York: Harry N. Abrams, Inc., Publishers (1978). A. C. Haddon, Reports of the Cambridge Anthropological Expedition to Tortes Straits, vol. IV, Arts and Crafts, Cambridge (1912) (reprinted 1971). Willowdean Chatterson Handy, String Figures from the Marquesas and Society Islands, Bernice P. Bishop Museum Bulletin 18, New York: Kraus Reprint (1971) (reprint of 1925 edition). Karl G. Heider, The Dugum Dani, Chicago: Adline Pub lishing Co. (1970). Teuria Henry, Ancient Tahiti, New York: Kraus Reprint (1971) (first published 1928). Bret Hilder, Polynesian navigational stones, Journal of the Institute of Navigation 12 (1959), 90-97. Charles Hose and William McDougall, The Pagan Tribes of Borneo, New York: Barnes & Noble, Inc. (1966) (first edition, 1912). Albert Ernest Jenks, The Bontoc Igorot, Manila: Bureau of Public Printing (1905). Samuel Manaia Kalani Kamakau, The Works of the People of Old, Honolulu: Bishop Museum Press (1976). Gordon Knight, The geometry of Maori art--rafter patterns. The New Zealand Mathematics Magazine 21 (3) (1984), 36-40. , The geometry of Maori art--weaving patterns, The New Zealand Mathematics Magazine 21 (3) (1984), 80-86. David Levinson and David Sherwood, The Tribal Living Book, Boulder: Johnson Books (1984). Ralph Linton and Paul S. Wingert, Arts of the South Seas, New York: Museum of Modern Art (1946). Sava Maksic and Paul Meskil, Primitive Art of New Guinea: Sepik River Basin, Worcester, Mass.: David PubliTHE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

59

Now in its Third Revised Printing - -

To Infinity and Beyond A Cultural History of the Infinite

by Eli Maor From the reviews: "Fascinating and enjoyable... Maor has written a book that places the ideas of infinity in a cultural context and shows how they have been espoused and molded by mathematics." - - Science "The work of a gifted writer.., this book is must reading for anyone who wants to find out what mathematicians do, how they think, and what turns them on." - - SIAM News "A splendid and lavishly designed and illustrated book for the general reader about all aspects of infinity. It is destined to become a classic." - - Mathematics Magazine "Maor explores the idea of infinity in mathematics and in art and argues that this is the point of contact between the two, best exemplified by the work of the Dutch artist M.C. Escher, six of whose works are shown here in beautiful color plates." - - Los Angeles Times

Order Your Copy Today! To Infinity and Beyond: A Cultural History o f the Infinite by Eli Maor

Third Revised Printing, 1991 1987/304 pp., 162 illus., 6 color plates Hardcover/ISBN 0-8176-3325-1/$49.50 9 Call: Toll-Free 1-800-777-4643. In NJ please call (201) 348-4033. Your reference number is Y495. 9 Write: Send payment plus $2.50 for postage and handling to: Birkh~iuser, Attn. S. Gebauer - Dept. Y495, 175 Fifth Avenue, New York, NY 10010. 9 Visit: Your Local Technical Bookstore. Visa, MasterCard, American Express and Discover Charge Cards, as well as personal checks and money orders, are acceptable forms of payment. All orders will be processed upon receipt. If an order cannot be fulfilled within 90 days, payment will be refunded. Payable in U.S. currency or its equivalent.

Birkhiiuser Boston

Basel Berlin

cations, Inc. (1973). 34. Bronislaw Malinowski, Coral Gardens and Their Magic, vol. I: Soil Tilling and Agricultural Rites in the Trobriand Islands, Bloomington: Indiana University Press (1965) (first published 1935). 35. William Mariner, An Account of the Natives of the Tonga Islands, New York: AMS Press (1979) (first printed 1816). 36. Peter Matthiessen, Under the Mountain Wall, New York: Viking (1962). 37. Honor Maude, Solomon Islands String Figures, Canberra: The Homa Press (1978). 38. Sidney Mead (ed.), Exploring the Visual Art of Oceania, Honolulu: University Press of Hawaii (1979). 39. Hortense Powdermaker, Life in Lesu, London: Williams & Norgate Ltd. (1933). 40. Henry Ling Roth, The Natives of Sarawak and British North Borneo, London: Truslove & Hanson (1896). 41. Laurence Russ, Mancala Games, Algonac, Mich.: Reference Publications, Inc. (1984). 42. A. Seidenberg, The ritual origin of geometry, Archive for History of Exact Sciences 1 (1963), 488-527. 43. Te Rangi Hiroa, Arts and Crafts of Hawaii, Honolulu: Bishop Museum Press (1957). 44. - - , Arts and Crafts of the Cook Islands, Bernice P. Bishop Bulletin 179, New York: Kraus Reprint (1971) (first published 1944). 45. , The Coming of the Maori, Wellington: Whitcombe & Tombs, Ltd. (1962) (first published 1949). 46. - - , Material Culture of Kapingamarangi, Bernice P. Bishop Museum Bulletin 200, New York: Kraus Reprint (1971) (first published 1950). 47. , Samoan Material Culture, Bernice P. Bishop Museum Bulletin 75, New York: Kraus Reprint (1971) (first published 1930). 48. George Turner, Samoa, A Hundred Years Ago and Long Before, New York: AMS Press (1979) (first published 1884). 49. B. L. van der Waerden, Geometry and Algebra in Ancient Civilizations, New York: Springer-Verlag (1983). 50. F. E. Williams, Papuans of the Trans-fly, Oxford: The Clarendon Press (1969) (first published 1936). 51. Edward P. Wolfers, The original counting systems of Papua and New Guinea, The Arithmetic Teacher 18 (1971), 77- 83. 52. Claudia Zaslavsky, Africa Counts, Number and Patterns in African Culture, Boston: Prindle, Weber & Schmidt (1973). Department of Mathematics Moorhead State University Moorhead, MN 56560 USA

P u t O u r List O n Y o u r List Such as buy 9 c a r . . , estimatesocial security.., start the d i e t . . , check Out investments... Our list is the Consumer Information Ca~log. It's free and lists more than 200 free and low-cost government booklets on employment, health, safety, nutrition, housing, Federal benefits, and lots of ways you can save money. SOto shorten your list, send for the free Consumer I n f o ~ a t i o n Ceta/og. It's the thing to do. Just send us your name and s~lreas. Write: C o q M ~ l l e r I n f o r n s l l U o n C e m m r , Departlln0mM

~.~,

~'~/~ U., Puoblo, Colorlido 111(1@9

A pJl~Cm ~ e ~ th~ pu~4w~n 1~4 the Conmmlorklfomwtk~Ceoter~ the U.S. eener~ Sen4cleA d m l n ~

60

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

Computing with Barycentric Polynomials Rida T. Farouki

1. Introduction I~olynomials are dear to mathematicians of all persuasions, whether they be purists seeking only intellectual gratification, or pragmatists in pursuit of expedient solutions to scientific and engineering problems. As far as polynomial computations are concerned, the aspirations of the purist have been admirably served by the a d v e n t of computer algebra systems [1], which promise exact calculations over the field of rational n u m b e r s - - o r algebraic extensions t h e r e o f - - a n d hence infallible answers to suitably phrased problems. For the pragmatist, however, the combination of computational expense and limited capability incurred by exact methods often proves intolerable in the context of "real-world" problems. The pragmatist is thus enticed into a Faustian bargain with the computer, conceding to it the perverse freedom to introduce random (small) fractional errors at each arithmetic step, in return for simplicity of programming and efficiency of execution. This devilish compact is known as floating-point arithmetic. For most mathematicians, of course, the word polynomial immediately connotes the familiar " p o w e r " form: antn + . . . + alt + a 0,

which polynomial representations, if any, exhibit an enhanced degree of numerical stability in the context of floating-point computations. While this question has already attracted some attention, early studies [10,11,18] have often focused on specific examples, offering no convincing grounds for believing that any polynomial basis could be systematically more stable than another. In many applications, however, one is primarily concerned with real polyno mials defined over finite real domains of the indepen dent variable(s). The "barycentric" form is an elegant means of representing such polynomials. In this informal survey we will sketch some of the remarkable stability properties of the barycentric form, and at-

(1)

suggested by the etymology of that word. Although, by force of habit, the education and literature of mathematicians has been imbued with this form, it is nevertheless well known that alternative polynomial representations offer a preferable medium for discussion in specific contexts (e.g., the Chebyshev forms in approximation theory). Thus, it seems natural to ask THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4 9 1991 Springer-Verlag New York

61

t e m p t to convince the reader that, u n d e r certain simple conditions, it is always preferable to the familiar power form (1).

2. Condition N u m b e r s Numerical analysts characterize the intrinsic stability of mathematical problems in terms of condition numbers [19]. Conceptually, we may think of a problem @ as receiving certain numerical values as " i n p u t , " and generating other values as the solution or "output." We assume that the output is an analytic function of the input, even though we cannot, in general, express that function in a simple closed form. When the input suffers random perturbations characterized by a given (infinitesimal) relative magnitude e, corresponding perturbations in the output are induced. We say that @ is "well-conditioned" or "illconditioned" according to whether the worst of these output perturbations is commensurate with, or much larger than, the input perturbation. The condition number C is simply a quantitative expression of this notion. Note that we make no reference to any particular algorithm whereby the solution is actually effected; the condition number is an intrinsic characteristic of the problem @ itself. Now it is only fair to admit that condition numbers can be criticized on several grounds: their overtly pessimistic bias, their sweeping reduction of subtle inputo u t p u t relationships to a single number, and the seemingly tenuous connection of this input-output stability to the cumulative effects of random round-off errors. Nevertheless, at least partial responses and/or remedies to such criticisms may be given, and the " c o n d i t i o n " p a r a d i g m has indeed proven fruitful, both in practice and in the development of a substantive theory. It will suffice h e r e to c o n s i d e r the c o n d i t i o n numbers of polynomial roots and of linear maps (matrices). Consider the problem of locating a simple real root r of the polynomial

P(t) = ~ CkCbk(t),

(2)

k=0

given its coefficients {Ck}in the basis {(bk(t)} as input. If the {Ck} suffer r a n d o m errors of m a x i m u m relative magnitude e, the perturbed value/5(0 will lie in the range n

P(t) - e ~,

ICke~k(t)l<~ P(t)

Ick%(t)l

~ P(t) + e

k=O

(3)

k=O

for each t. We call this range of values the e-perturbation region of the polynomial P(t), for the basis {~bk(t)}. By the implicit function theorem, we may deduce that the magnitude of the resulting perturbation 8"r of the root "r is bounded, as e ~ 0, by

IS'r[ ~ C~(~')e, where

C~('0 -

k=0

ICk k( )l.

(4)

We see that the condition number C~(-r) of the root "r of

P(t) depends on two factors: the magnitude of the derivative P'(a-)--an intrinsic property of P over which we have no control--and the basis {~bk(t)}, which we are free to choose at will. (Note that we define C~,('r) in terms of relative perturbations of the coefficients, but absolute perturbations of roots: if we are interested only in roots on a finite interval, [0,1] say, then 15-r[ is a more reasonable error measure than iSa'/'rl since, for fixed lsa'l, the latter grows without bound as 9~ 0.) Consider next the stability of a matrix transformation. We define the norm I]xflpof a vector x of n + I real elements, and the c o r r e s p o n d i n g - - o r subordinate-matrix norm IIMllpof an (n + 1) x (n + 1)real matrix M, as follows: llXllp =

Ixkip~I/p and

[IMIIp=

sup

x~o

IIMxllp (5) Ilxllp

By convention, we take ][xlL = maxk [Xk[. Although the matrix norm [IMIIpis in general quite difficult to compute, the cases ]IMiil and [[MIL correspond simply to the greatest of the sums of absolute values of matrix elements across columns and rows, respectively (also, [[MII2 is the square-root of the largest eigenvalue of the symmetric matrix MrM) [22].) Suppose the matrix M maps the vector x into the vectory y, and we introduce a random perturbation Bx into the former. Since y = Mx, the corresponding perturbation in y is given by 8y = MSx, and if we define the fractional error measures

IJ~xllp ex = Ilxllp and 62

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

ey-

ll~ylip Ilyllp'

(6)

it follows from the definition of the subordinate matrix norm that Ey ~ Cp(M)ex, where Cp(M) = IIMIrpNM-illp.

1.0

(7) 0.8

The quantity Cp(M) is the condition number of the matrix M, in the p norm. In certain degenerate cases (multiple roots, singular matrices, etc.) the assumption of a linear relationship b e t w e e n the output and input perturbations breaks down, and the condition number is formally infinite. An interesting perspective on the relationship bet w e e n such " i l l - p o s e d " p r o b l e m s a n d condition numbers in general may be found in [3]. 3. H i s t o r i c a l B a c k g r o u n d

Barycentric polynomials played an important role in a constructive proof of the theorem of Weierstrass given by S. N. Bernstein in 1912 [15]. If f is a continuous function on a finite interval I, and 8 (>0) a prescribed tolerance, this theorem states that there exists a polynomial F such that IF(t) - flt)l < 8 for all t ~ I. In particular, if we take I = [0,1] for simplicity, the n-th order BernStein approximation to f(t) is given by F,(t) = ~ f(k/n)(k)tk(1

- t)"-k,

0.6

8~(t) 0.4

0.2

0.0 0.0

0.2

0.4

0.6

0.8

1.0

t Figure 1. The barycentric basis functions {[~,(t)} of degree n = 7 on the interval t ~ [0,1], as defined by equation (9).

I

'

J

J

I

'

I

,

I

~

I

J

I

'

I

I

(8)

k=0

F.(t)

and there exists an integer n~ such that tF,(t) - f(t)l < for all t ( [0,1] whenever n i> n a. We say that F,(t) converges uniformly to f(t) on [0,1] as n ~ 2. Henceforth we shall call the n + 1 polynomials ~(t) = (k) t k ( 1 -

On-k"

k = 0,1 . . . . .

n

(9)

occurring in (8) the Bernstein basis functions of degree n on [0,1]. The quantities u = t and v -- 1 - t may be r e g a r d e d as barycentric coordinates of a point t with respect to [0,1], and the basis functions (9) are just the terms arising in the binomial expansion of 1 = (u + v)". (The reader may recognize ~(t) as the probability of k successes in n trials of a random event, considered as a function of the probability t of success in each individual trial.) For an arbitrary interval [a,b] we simply set u - (t a)/(b - a) and v = (b - t)/(b - a). Essentially, the Bernstein polynomial F,(t) samples fit) at n + 1 equidistant points and "blends" these values together with the functions ~3~(t) shown in Figure 1. Although Bernstein's proof is indisputably elegant, the polynomials F,(t) have been relegated to the theory (rather than practice) of functional approximation [2], because their convergence to a given fit) can be excruciatingly slow (see Figure 2). Suppose, however, that we replace the quantities f(k/n) in (8) by coefficients bk that are considered to be freely chosen, rather than

,

0.0

0.2

0.4

0.6

0.8

1.0

t Figure 2. Bernstein polynomial approximations F,(t) of degree n = 5, 10, 25, 50, and 100 to the function fit) = sin(2~rt), as defined by equation (8). The bold curve is the graph of f(t), and the lighter curves are the approximations.

equidistant samples of some continuous function f(t). Since the functions (9) are linearly independent, any polynomial of degree n (or less) may clearly be written in the form P(t) = "Zbkf3~(t). In the 1960s, the barycentric form was introduced and popularized in the field of computer-aided geometric design (CAGD)--which deals with the computer representation and manipulation of shape information for engineering p u r p o s e s - - b y two Frenchmen working independently in the automobile industry, P. de Casteljau at Citro6n and P. B6zier at Renault (the identification of their ideas with barycentric forms came later, however [9,12]). THE MATHEMATICAL INTELLIGENCER VOL. 13, NO, 4, 1991

63

@ Tjk = ~ i f j ~ > k

and

Tjk = 0 i f j < k .

(11)

W

The r e a d e r m a y verify t h a t the e l e m e n t s {Tjk} are simply the coefficients in the representation of the monomial tk in the Bernstein basis of degree n on [0,1]. Thus, the matrix T maps the power coefficients {ak} of a polynomial P(t) about t = 0 into the barycentric coefficients {bj} on [0,1]:

tk = ~ Tjk~7(t), bi = ~ Tjkak. j=0

(12)

k=O

Observe that the matrix elements (11) are all nonnegative. This is the key to a powerful result. Consider

Figure 3. A parametric Bdzier curve of degree 7 and its control polygon. The vertices of this polygon are the "control points" of the curve, i.e., the vector-valued coefficients {bk} in its barycentric representation (10).

If we take vector-valued coefficients b k for a barycentric polynomial

the e-perturbation regions (3) for the power and barycentric forms of a polynomial P(t). We wish to compare the m a g n i t u d e s of the sums Z lakltk and Z Ibjl~y(t) over the interval t E [0,1]. (We take the liberty of dropping the absolute value signs a r o u n d the {tk} a n d {~7(t)} since they are all non-negative on this interval.) Taking note of (12), we have, for an arbitrary polynomial P(t):

Ibjl"7(t) j= 0

=

Tjkak

7(t)

j=0

~ lakl ~ Tjk~(t) k=O P(t) = ~

bk~(t),

(10)

k=0

j=0

= ~ lakltk,

(13)

k=O

we have w h a t is k n o w n as a B~zier curve of degree n (Figure 3). The coefficients b k are the control points of the curve, and define the vertices of its control polygon. This polygon m a y be regarded as a caricature of the curve, offering the design engineer a convenient and intuitive m e a n s of " s h a p i n g " the curve to suit aesthetic or functional requirements. Today the B6zier curve is essentially a de facto ind u s t r y standard; m a n y of us have (perhaps unwittingly) had occasion to make use of artifacts that relied u p o n such forms in their design. Besides the mimicry of the polygon and curve shapes, this form boasts an elegant and practical subdivision algorithm (see Section 5 below), a n d c o n f i n e m e n t of the curve w i t h i n the convex hull of the polygon, among its attractive features. A more detailed discussion m a y be f o u n d in [4]. 4. B a r y c e n t r i c V e r s u s P o w e r F o r m s

A l t h o u g h b a r y c e n t r i c forms w e r e i n t r o d u c e d into CAGD for their attractive geometric properties, they simultaneously offered an extremely important advantage that was not, until recently, fully appreciated [7]. Consider the lower-triangular matrix T defined by 64

THE MATHEMATICAL 1NTELLIGENCER VOL. 13, NO. 4, 1991

where we invoke the triangle inequality Iz0 + . . . + znl Izd + . . . + Iznl, and the fact that ITjkl = Tjk. Thus, we conclude that for any polynomial, the width of the perturbation region over [0,1] in the barycentric form is less

than or equal to that in the power form. From the definition (4) of root condition numbers, it is clear that a similar inequality holds with regard to the stability of (simple) roots on [0,1[ in the barycentric and p o w e r forms. In fact, the root condition numbers for the barycentric form are strictly less than for the power form (except at t = 0), because the presence of a root on [0,1] implies that the coefficients a 0. . . . . an are not all of like sign. We m a y generalize this result [7] to claim that the condition n u m b e r s of the simple real roots of a n y p o l y n o m i a l P(t) on a given interval [a,b] are always smaller in the barycentric basis on [a,b] t h a n in a power basis about any center c ~ (a,b). W h e n c ~ (a,b), however, the barycentric form relinquishes its systematic s u p e r i o r i t y - - s o m e roots will have smaller condition n u m b e r s in the power form (those near c), others in the barycentric form. Perhaps the most (in)famous example of pathologically unstable polynomial roots was identified by J. H.

In order to e m p l o y the superior s t a b i l i t y of barycentric f o r m s to full advantage, w e m u s t l e a r n to "'think barycentric,'" c a s t i n g aside o u r deeply-ingrained predilection f o r p o w e r r e p r e s e n t a t i o n s , a n d f o r m u l a t i n g our algor i t h m s e x c l u s i v e l y in b a r y c e n t r i c terms instead. The d i f f i c u l t y here is p s y c h o l o g i c a l rather than m a t h e m a t i c a l , since the barycentric f o r m s of c o m m o n p o l y n o m i a l procedures (arithmetic operations, substitution, interpolation, greatest c o m m o n divisors, elimination o f variables, etc.) are n o t significantly more difficult t h a n - - a n d in m o s t cases r e m a r k a b l y similar t o - - t h e traditional p o w e r forms. Wilkinson [20] in 1959. In the course of testing some r e c e n t l y - i m p l e m e n t e d s o f t w a r e for f l o a t i n g - p o i n t arithmetic, he a t t e m p t e d to iterate for the roots of a polynomial of degree 20 with equidistant real roots

P(t) = ~I (t - k/n), n = 20.

(14)

resentation adopted by W i l k i n s o n - - m a y lead to root displacements of order unity/In fact, most of the roots w a n d e r off the real axis as complex conjugate pairs at m u c h smaller values of e. In the barycentric form, h o w e v e r , the largest c o n d i t i o n n u m b e r s are s o m e seven orders of magnitude smaller than in the p o w e r form. Quite often, the logarithm of a root condition n u m b e r will be an accurate indication of the n u m b e r of significant digits lost in iterating for that root by any simple numerical scheme. Thus, in standard double-precision arithmetic, we should expect at most one or two accurate decimal digits in c o m p u t i n g the roots of (14) in power form, but perhaps eight or nine in the barycentric form. Figure 4 illustrates a further dramatic imp r o v e m e n t u p o n subdividing the barycentric form at t = 1/2 (a process that we describe below). Actually, it is not difficult to identify the "gremlin" at work in Wilkinson's polynomial. Let us compute the value of P(t) at t = 21/40(we choose a point between two r o o t s - - n e a r an extremum of P(t)--since the value at the roots is, of course, zero). The contributions of the 21 terms aktk, accurate to the n u m b e r of decimal digits shown, are as follows: a0

=

alt a2t2 a3t3 a4t4 a5t5 a6t6 a7t7 a8t8 a9t9

= = = = = = = = =

109

aiotl~ all tll a12t12 a13t13 a14t14 a15t15 a16t16 a17t17 a18t18 a19t19

= = = = = = = = = =

107

a20t20 =

+0.000000023201961595 -0.000000876483482227 +0.000014513630989446 -0.000142094724489860 +0.000931740809130569 -0.004381740078100366 +0.015421137443693244 -0.041778345191908158 +0.088811127150105239 -0.150051459849195639 +0.203117060946715796 -0.221153902712311843 +0.193706822311568532 -0.135971108107894016 +0.075852737479877575 -0.033154980855819210 +0.011101552789116296 -0.002747271750190952 +0.000473141245866219 -0.000050607637503518 +0.000002530381875176

P(t) =

0.000000000000003899

k=l

He was subsequently to call this attempt " t h e most traumatic experience in m y career as a numerical analyst" [21]. Most contemporary numerical analysis texts indulge in some mention of (14) as a dire warning of the potentially severe limitations of floating point (see [1] also). F i g u r e 4 i l l u s t r a t e s the r o o t c o n d i t i o n n u m b e r s for ( 1 4 ) - - a n d the source of the computational difficulties in dealing with it. We see that a relative perturbation of only e = 10-13 in the coefficients of the power form of (14)--the rep-

1017 1015

L

L

9 power 9 borycentric

I

I

9 barycentric with subdivision

1013 1011

@

10s

(15)

103

101

10-1 10-3 0.0

,

L

0.2

L

0.4

0.6

0.8

1.0

T

Figure 4. Condition numbers in the power and barycentric bases for the twenty equidistant roots of the Wilkinson polynomial defined by equation (14). The effect of subdividing the barycentric form at t = V~is also shown (see w

A massive cancellation evidently occurs in s u m m i n g the terms aktk, the value of P(t) being just a minuscule residual by comparison w i t h the m a g n i t u d e of (the largest of) those terms. Accordingly, w h a t might appear to be an insignificant perturbation in one or more of the coefficients {ak} m a y nevertheless exert a dramatic influence on the value of P ( t ) - - a n d hence its roots, since these are simply the locations at which that value vanishes. T H E M A T H E M A T I C A L INTELLIGENCER VOL. 13, N O . 4, 1991

65

I

'

I

'

[

barycentdc

'

I

/p I

'

'

I

ower

~ = 0.00002

P(O

'

]

r = 0.002

P(t)

\ ,

0.0

J 0.2

,

I

,

0.4

I 0.6

[

,

0.8

I

J 1.0

0.0

~

0.2

I

,

0.4

I

,

0.6

I 0.8

I

I 1.0

t

t

Figure 5. ~-perturbation regions for the power and barycentric forms of a degree 6 polynomial of the form (14), for (a) 9 = 0.00002, and (b) c = 0.002. The bold curve is the nominal graph of the polynomial, while the lighter curves

represent the b o u n d s on its perturbed value w h e n the power and barycentric coefficients suffer random errors of maximum relative magnitude ~.

A similar tabulation for the barycentric form of P(t) on [0,1] reveals that its terms bk~(t ) are about 6 orders of magnitude smaller, and the value of P(t) is correspondingly less sensitive to perturbations in the barycentric coefficients {bk}. The difference in condition number magnitudes evident in Figure 4 is in surprisingly good agreement with this simplistic analysis. Of course, we have chosen a pathological example here for purposes of emphasis; in most cases the improvement offered by the barycentric form will be more modest (see [7] for another example). Nevertheless, it is worth emphasizing again that this improvement is s y s t e m a t i c - - t o s o m e extent, the barycentric form always provides greater stability. In Figure 5 we illustrate the e-perturbation regions for a milder form of (14), with n = 6. W h e n ~ = 0.00002 the perturbed power form already exhibits a significant deviation, while the perturbed barycentric form is indistinguishable--to the scale of the g r a p h - from the nominal value. If we increase the error to the point where the perturbed barycentric form becomes visible (e = 0.002), the power form goes "wild" for t > 0.2. Further interesting perspectives on Wilkinson's polynomial may be found in [16,17].

G = (b- s)/(b-a),andb~ ~ bk f o r k = compute a triangular array of terms:

5. S u b d i v i s i o n

Suppose we are given the Bernstein coefficients {bk} of a polynomial P(t) of degree n on [a,b]. Choosing a "split" point s ((a,b) and setting u s = (s - a)/(b - a), 66

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

b 01 bt0} bill 1)

0. . . . .

n, we

b( O (16)

as follows. Each entry in this array is the linear interpolant b~r) = usb~r-~) + Gb~r-l)

(17)

of the t w o values i m m e d i a t e l y above it, for k = r. . . . . n and r = 1. . . . . n. This procedure is known as the de Casteljau algorithm. The final entry b(~") is the polynomial value P(s) at the split point s, while the entries b8~ bt1). . . . .

b(.") and

b(."),b(,"-1) . . . . .

b~)

(18)

on the left- and right-hand sides of the array are the barycentric coefficients of P(t) on the intervals [a,s] and [s,b] respectively--hence the term subdivision. Equation (17) is also known as a "corner-cutting" algorithm because of the simple geometric construction it describes for the control p o l y g o n of a B6zier curve (Figure 6). Barycentric forms exhibit an interesting property

with regard to subdivision. Suppose we have a choice between the barycentric forms of a polynomial P(t) on two intervals [a,b] and [~,b], with similar accuracy in their coefficients. By arguments similar to those of section 4, it m a y be s h o w n [7] that if [~,b] C [a,b], the roots of P(t) on the subinterval always have smaller condition numbers in the basis on [~,b] than in that on [a,b]. Subdivision is a powerful practical tool for comp u t i n g approximations and intersections of curves, isolating roots of polynomials (cf. below), etc., but h o w susceptible is it to round-off error accumulation w h e n invoked repeatedly? We m a y gain some idea of the f u n d a m e n t a l limitations on subdivision in finite-precision arithmetic as follows: The subdivision process m a y be characterized by a square matrix S that maps the Bernstein coefficients of any polynomial P(t)_on a given interval [a,b] into those on a subinterval [~,b] thereof. The elements of S have a rather complicated form [6]: min(j,k)

Sjk =

~

where f = (b - a)/(-b - -d) is the " z o o m " factor, and u m = (-m - a)/(b - a), Vm = (b - -~)/(b - a) are barycentric c o o r d i n a t e s of the subinterval m i d p o i n t ~ = 1/2(~ + b) with respect to [a,b]. The quantity max(u,,,Vm) describes the dependence of C~(S) on the location of the subinterval (note that I < 2 max(um,Vm) < 2 w h e n [~,b] C [a,b], the condition n u m b e r increasing by a factor of 2 n as we move [~,b] away from the center of [a,b] toward either end), while f describes the d e p e n d e n c e on the size of the subinterval. Such observations are useful w h e n isolating the real roots of polynomials by subdivision: In order to isolate the real roots of P(t) on [a,b], we appeal to the variation-diminishing property of the barycentric form. If V(b0, . . . , b,) denotes the n u m b e r of sign changes in the Bernstein coefficients of P(t) on [a,b], and N the n u m b e r of real roots of P(t) (counted with multiplicity) on (a,b), this property indicates that N = V(b o . . . . .

~-i(a)~/(b).

(20)

C~(S) = [2f max(um,Vm)] ~,

b,) - 2k

(21)

(19)

i = m a x ( 0 , j + k - n)

N o w (19) is actually valid for arbitrary [a,b] and [a,b], but in the case that [a,b] C [a,b], the matrix elements (19) are non-negative a n d sum to unity across rows, so S is a stochastic m a t r i x . In that case, the c o n d i t i o n n u m b e r of S (in the I]" I]~ norm) admits a particularly simple expression in terms of geometric parameters describing the subdivision map [6]:

for some integer k ~> 0. This is really just a manifestation of Descartes' Law of Signs, as can be seen from the expression P(u) = (1 + U)-n~Zbk(~)uk resulting from the substitution u = t/(1 - t ) - - w h i c h maps t E (0,1) into u E ( 0 , ~ ) - - i n P(t) = ~,bk(~)tk(1 -- t) n-k. To isolate the (simple) real roots of P(t) on [a,b], we keep splitting that interval in a binary fashion until exactly zero or one sign changes are observed for each subinterval, indicating a corresponding n u m b e r of real roots [14]. If we w i s h to f u r t h e r a p p r o x i m a t e t h o s e roots, t h e b a r y c e n t r i c f o r m offers an " i n s u r a n c e p o l i c y " in the use of an e f f i c i e n t - - b u t o t h e r w i s e s o m e w h a t d a n g e r o u s - - n u m e r i c a l m e t h o d , the familiar N e w t o n - R a p h s o n iteration:

t k = tk_ t

Figure 6. Subdivision of a cubic B~zier curve defined on the parameter interval t ( [0,1] by "corner cutting." This corresponds to computing the triangular array of coefficients (16) by means of the de Casteljau algorithm (17). The case shown is for subdivision at t = 1/2, yielding control polygons for the curve subsegments t ~ [0,1,6] and t ( [1A,1] individually.

P(tk-1) p,(tk_t),

k -- 1, 2 . . . . .

(22)

If the starting approximation t o is "sufficiently close" to the desired root % then (22) will furnish a sequence of i m p r o v e m e n t s t 1, t2. . . . converging rapidly to -r. In practice, of course, the d i f f i c u l t y lies in g i v i n g a simple, algorithmic characterization of this proximity criterion. Although sufficient conditions for convergence m a y be described in terms of the behavior of the first and second derivatives of P(t) over an isolating interval for "r [13], they are not easily verified in the traditional power form. For the barycentric f o r m P(t) = Y-,bk~(t ) on an isolating interval [a,b] of the root "r, however, sufficient conditions for the convergence of (22) from any t o [a,b] m a y be expressed in a particularly simple form. Noting that the derivatives of P(t) are THE MATHEMATICAL INTELLIGENCER VOL. 13, NO- 4, 1991

67

n

P'(t) - - -

n-1

~

Abk [3~-1(t)

and

b -- a k= o

n(n - 1).-2 P"(t) - -~ -- a-~ k=0 ~ A2bk ~ - 2 ( t )

(23)

in barycentric form, where Ab k = bk + 1 - bk a n d A2b k = bk + 2 - 2bk +1 + bk, we have the following sufficient conditions for g u a r a n t e e d convergence of (22) to a simple root "r: bob" < 0, (24a) Abo, Ab._l # 0

and

V(Abo

.

V(A2bo .....

[bo[ <<-nlAbo[

.

.

.

.

A2bn_2)

and

Abn_l) = O, (24b) =

0,

[b,[ <<-n[Ab,_l[.

(24c) (24d)

The first condition is equivalent to P(a)P(b) < 0, indicating the p r e s e n c e of a root on (a,b), while the second implies that P'(t) # 0 for all t E [a,b], so there is only one root. The third condition guarantees that P'(t) /> 0 or P'(t) ~< 0 on [a,b], and the fourth requires the tangents to P(t) at a a n d b to intersect the t-axis within the interval [a,b] (see [13] for further details).

6. Computing with Barycentric Forms As in other walks of life, in numerical analysis there is " n o free lunch," a n d the reader w h o naively expects to benefit from the e n h a n c e d stability of barycentric representations by explicitly converting from power forms will be (deservedly) disappointed. To see w h y , consider the condition n u m b e r of the transformation matrix T given by (11). Since T is symmetric about its seco n d a r y diagonal (T,_k,,_ j = Tjk), we have the same result in the [[ 9 ]]1 a n d [] 9 [[~ norms, namely [5]

stead. The difficulty here is psychological rather than mathematical, since the barycentric forms of c o m m o n polynomial procedures (arithmetic operations, substitution, interpolation, greatest c o m m o n divisors, elimination of variables, etc.) are not significantly more difficult t h a n - - a n d in most cases remarkably similar to - - t h e traditional power forms [8]. We will briefly mention just one important difference, concerning the degree of the barycentric form P(t) = ~ b k ~ ( t ). It is important to bear in mind that the degree n of the basis in which we express P(t) is only an upper bound on the degree of P(t). Thus b0(1 - 03 + b13t(1 - t) 2 + b23t2(1 - t) + b3t3

with (bo,bl,b2,b3) = (0,1/3,2/3,1), for example, is just a rather complicated way of writing t so that it "looks like" a cubic. In fact, the true degree of P(t) will be less than n w h e n e v e r b, - (~)b._ 1 + . . . + (-1)"b 0 = 0. This m a y seem like a great nuisance, but in fact there are circumstances where one wants to represent barycentric forms in such a " d e g r e e - e l e v a t e d " m a n n e r . Suppose we are trying to a d d together two barycentric polynomials Q(t) = ~ C k ~ ( t ) a n d R(t) = ~ d k ~ ( t ) of true degree m a n d n, respectively. Obviously, the barycentric coefficients bk of the s u m Q(t) + R(t) are equal to ck + d k only w h e n m = n. However, if m > n (say), we can perform an (m - n)-fold degree elevation on R(t) and t h e n simply s u m corresponding coefficients. This gives

bk=Ck+

~

for k = 0 . . . . . m. (27)

Finally, although we have no space for a detailed discussion, we should mention that m a n y of the ideas presented here generalize readily to multivariate polynomials. Recall that a univariate polynomial on an interval I can be written in the h o m o g e n e o u s form n! P(u,v)

=

~

i+j=, By use of the Stirling Formula m .v~ ~ e _ inm m , w e find [5] that the simpler form C(T) ~ 3 "+1 V~(n + 1)/4~r gives an excellent a p p r o x i m a t i o n to (25), indicating that the condition n u m b e r of the basis transformation grows roughly by a factor of 3 for each unit increment in the degree. In the case of Wilkinson's polynomial (n = 20), for example, we have C(T) ~ 101~ so the potential loss of accuracy in transforming from power to barycentric forms could easily negate the e n h a n c e d root stability of the latter. In order to e m p l o y the superior stability of barycentric forms to full advantage, we must learn to "think barycentric," casting aside our deeply-ingrained predilection for p o w e r representations, a n d formulating our algorithms exclusively in barycentric terms in68

THE MATHEMATICAL INTELL1GENCER VOL. 13, NO. 4, 1991

(26)

bo--uivJ.

(28)

i!j!

The barycentric coordinates are redundant (u + v = 1), and for s y m m e t r y we also e m p l o y r e d u n d a n t indices on the coefficients. N o w we m a y regard I as a one-dimensional simplex, and u, v as the fractional lengths of that simplex subtended by a point interior to it. For a bivariate polynomial, we take a reference simplex (triangle) T in the plane, a n d define barycentric coordinates (u,v,w) of a point p as the ratios of the areas s u b t e n d e d at p by the three sides of T to the total area of T itself. The degree-n basis f u n c t i o n s are simply the terms in the trinomial expansion of 1 = (u + v + w) n. Thus we write n! P(u,v,w) = ~ bijk i!j!k!uivJu/'. (29) i+j+k=n

For an m-variate polynomial, we take an m-dimensional simplex and define m + 1 barycentric coordinates in an exactly analogous manner, i.e., as the fractional volumes of the simplex subtended by its faces at an interior point. These higher-dimensional forms have much in common with the univariate case, in terms o f b o t h a l g o r i t h m s a n d s t a b i l i t y p r o p e r t i e s .

References 1. J. H. D a v e n p o r t , Y. Siret, a n d E. T o u r n i e r , Computer Algebra, L o n d o n : A c a d e m i c P r e s s (1988). 2. P. J. Davis, Interpolation and Approximation, N e w York: Dover (1975). 3. J. W. D e r n m e l , O n c o n d i t i o n n u m b e r s a n d t h e d i s t a n c e to the nearest i l l - p o s e d p r o b l e m , Numer. Math. 51 (1988), 251-289. 4. G. Farin, Curves and Surfaces for Computer-aided Geometric Design, N e w York: A c a d e m i c P r e s s (1988). 5. R. T. F a r o u k i , O n t h e stability of t r a n s f o r m a t i o n s bet w e e n p o w e r a n d B e r n s t e i n p o l y n o m i a l f o r m s , Comput. Aided Geom. Design 8 (1991), 2 9 - 3 6 . 6. R. T. F a r o u k i a n d C. A. Neff, O n t h e n u m e r i c a l c o n d i t i o n of B e r n s t e i n - B 6 z i e r s u b d i v i s i o n p r o c e s s e s , Math. Comp. 55 (1990), 6 3 7 - 6 4 7 . 7. R. T. F a r o u k i a n d V. T. Rajan, O n t h e n u m e r i c a l c o n d i t i o n of p o l y n o m i a l s i n B e r n s t e i n f o r m , Comput. Aided Geom. Design 4 (1987), 1 9 1 - 2 1 6 . 8. , A l g o r i t h m s for p o l y n o m i a l s in B e r n s t e i n f o r m , Comput. Aided Geom. Design 5 (1988), 1 - 2 6 . 9. A. R. Forrest, I n t e r a c t i v e i n t e r p o l a t i o n a n d a p p r o x i m a t i o n b y B6zier p o l y n o m i a l s , Computer J. 15 (1972), 7 1 - 7 9 . 10. W. G a u t s c h i , O n t h e c o n d i t i o n of a l g e b r a i c e q u a t i o n s , Numer. Math. 21 (1973), 4 0 5 - 4 2 4 . 11. , Q u e s t i o n s of n u m e r i c a l c o n d i t i o n r e l a t e d to p o l y n o m i a l s , Studies in Numerical Analysis (G. H. G o l u b , ed.), M A A S t u d i e s i n M a t h e m a t i c s 24 (1984), 1 4 0 - 1 7 7 . 12. W.J. G o r d o n a n d R. F. Riesenfeld, B e r n s t e i n - B 6 z i e r methods for the c o m p u t e r - a i d e d d e s i g n of free-form c u r v e s a n d s u r f a c e s , J. Assoc. Comput. Mach. 21 (1974), 293-310. 13. P. H e n r i c i , Elements of Numerical Analysis, N e w York: W i l e y (1964), 7 7 - 8 3 . 14. J. M. L a n e a n d R. F. R i e s e n f e l d , B o u n d s o n a p o l y n o mial, BIT 21 (1981), 1 1 2 - 1 1 7 . 15. G. G. L o r e n t z , Bernstein Polynomials, N e w York: Chelsea (1986). 16. R. G. M o s i e r , R o o t neighborhoods of a p o l y n o m i a l , Math. Comp. 47 (1986), 2 6 5 - 2 7 3 . 17. T. P o s t o n a n d I. S t e w a r t , Catastrophe Theory and Its Applications, L o n d o n : P i t m a n (1978), 4 4 2 - 4 4 4 . 18. J. R. Rice, O n t h e c o n d i t i o n i n g of p o l y n o m i a l a n d rat i o n a l f o r m s , Numer. Math. 7 (1965), 4 2 6 - 4 3 5 . 19. - - , A t h e o r y of c o n d i t i o n , SIAM J. Numer. Anal. 3 (1966), 2 8 7 - 3 1 0 . 20. J. H. W i l k i n s o n , T h e e v a l u a t i o n of the zeros of ill-condit i o n e d p o l y n o m i a l s , Numer. Math. 1 (1959), 1 5 0 - 1 8 0 . 21. , T h e p e r f i d i o u s p o l y n o m i a l , Studies in Numerical Analysis (G. H. G o l u b , e d . ) , M A A S t u d i e s i n M a t h e m a t i c s 24 (1984), 1 - 2 8 . 22. , The Algebraic Eigenvalue Problem, O x f o r d : Clare n d o n P r e s s (1988).

IBM Thomas J. Watson Research Center P.O. Box 218 Yorktown Heights, NY 10598 USA

Computational Number Theory P r o c e e d i n g s o f the C o l l o q u i u m on C o m p u t a t i o n a l N u m b e r T h e o r y held at K o s s u t h L a j o s University, D e b r e c e n ( H u n g a r y ) , S e p t e m b e r 4 - 9, 1989

Edited by Attila Peth6, Michael Pohst, Hugh C. Williams and Horst Giinter Zimmer 1991. XIII, 342 pages. 17 x 24 cm.

USA, Canada, Mexico. Cloth US$ 74.95 ISBN 0-89925-674-0 All other countries. Cloth DM 128,- ISBN 3-11-012394-0 The volume contains 28 original research and survey articles and is devoted to the interaction of modern scientific computation and classical number theory. The contributions, ranging from effective finiteness results to efficient algorithms in elementary, analytic and algebraic number theory, provide a broad view of the methods and results encountered in the new and rapidly developing area of computational number theory. Topics covered include finite fields, quadratic forms, number fields, modular forms, elliptic curves and diophantine equations. In addition, two new number theoretical software packages, KANT and SIMATH, are described in detail with emphasis on algorithms in algebraic number theory. Key words: Number theory, elliptic curves, diophantine equations; algorithms, scientific computing, development of software; computer algebra, cryptography, complexity.

Contents: S.A. Stepanov and I.E. Shparlinskiy: On the construction of primitive elements and primitive normal bases in a finite field - A. Grytczuk and B. Tropak: A numerical method for the determination of the cyclotomic polynomial coefficients - B. Kov~ics: Number systems - Yu. V. Melnichuk: Fast converging series representations of real numbers and their implementations in digital processing - A. Pethti: On a polynomial transformation and its application to the construction of a public key cryptosystem - M. Tasche, G. Steidl, and R. Creutzburg: Number-theoretic transforms and a theorem of Sylvester-Kronecker-Zsigmondy - J. Buchmann and S. Diillmann: A probabilistic class group and regulator algorithm and its implementation- E Halter-Koch: Prime-producing quadratic polynomials and class numbers of quadratic orders - R.A. Mollin: Applications of a new class number two criterion for real quadratic fields - R.A. Mollin and H.C. Williams: On a solution of a class number two problem for a family of real quadratic fields - V. Ennola: Cubic number fields with exceptional units - D. Ford: Enumeration of totally complex quartic fields of small discriminant - K. Nakamula: Class number computation by cyclotomic or elliptic units - B. Arenz: Computing fundamental units from independent units - M. Pohst: A note on index divisors - U. Schr6ter: Computation of independent units in number fields by a combination of the methods of Buchmann/Peth6 and Pohst/Zassenhaus - B.J. Birch: Hecke actions on classes of ternary quadratic forms - H. Cohn: Computation of singular moduli by multi-valued modular equations - P. Serf: Congruent numbers and elliptic curves - U. Schneiders and H.G. Zimmer: The rank of elliptic curves upon quadratic extension - I. GMh On the resolution of some diophantine equations - N. Schulte: Index form equations in cubic number fields - N. Tzanakis and B.M.M. de Weger: On the practical solution of the Thue-Mahler equation - J.H. Evertse and K. Gy6ry: Some results on Thue equations and Thue-Mahler equations - I. Nemes: On the solution of the diophantine equation G,; = P(x) with sieve algorithm - R.J. Stroeker: On Thue equations associated with certain quartic number fields - J. Graf yon Schmettow: KANT - a tool for computations in algebraic number fields - C. Hollinger and P. Serf: SIMATH - a computer algebra system. Walter de Gruyter & Co., Genthiner Str. 13, D-1000 Berlin 30, FRG, Phone (30) 260 05-0, Telex 1 84 027, Fax (30) 260 05-25 I Walter de Gruyter, Inc., 200 Saw Mill River Road, Hawthorne. N.Y. 10532, USA, Phone (914) 747-0110, Telex 64 66 77, Fax (914) 747-1326

Chandler Davis*

Ein Jahrhundert Mathematik, 1890-1990: Festschrift z u m J u b i l / i u m d e r D M V Edited by Gerd Fischer, Friedrich Hirzebruch, Winfried Scharlau, and Willi T6rnig Dokumente zur Geschichte der Mathematik, Band 6 Deutsche Mathematiker-Vereinigung Braunschweig/Wiesbaden" Friedr. Vieweg & Sohn, 1990 xii + 830 pp.

Reviewed by David E. Rowe " . . . mathematics (pure mathematics), despite its many subdivisions and their enormous rate of growth 9. . is an amazingly unified intellectual structure . . . . IT]he interplay b e t w e e n widely separated parts of mathematics always s h o w s up. The concepts and methods of each one illuminate all others, and the unity of the structure as a whole is there to be marvelled at."--Paul H a l m o s t The Deutsche Mathematiker-Vereinigung celebrated its centennial last fall at a meeting in Bremen 9 In the (loosely translated) words of the editors, this anniversary marked an occasion "to look back on the past century and reflect upon how mathematics has developed during this period, what the Vereinigung has since accomplished, and what was neglected . . . . The scientific public at home and abroad should learn how mathematicians view and evaluate the development of their field9 The idea here, certainly a sound one, was not to aim at an exhaustive history of mathematics covering the past hundred years but rather to present a series of concise overviews highlighting those fields in which German mathematicians had made substantial contributions.

* Column editor's address: Mathematics Department, University of Toronto, Toronto, Ontario M5S 1A1 Canada. t "Applied Mathematics is Bad Mathematics," in Lynn Arthur Steen, ed., Mathematics Tomorrow (New York/Heidelberg/Berlin: Springer-Verlag), p. 15.

Festschriften constitute one of the more problematic genres for those with a serious interest in history of mathematics. On the one hand, they often contain valuable firsthand accounts or documentary information that may be difficult, even impossible, to obtain elsewhere, whereas on the other, their celebratory nature makes them an unlikely vehicle for serious retrospective analysis of a mathematician's work and career. What one is more likely to find in a typical contribution to a Festschrift is an article that begins with a bowing nod in the direction of the celebrant and then proceeds to the matters that really interest the writer, more often than not, her or his o w n work. Let me say at the outset that this volume should not be viewed as a Festschrift of this sort, and while it has some serious faults, nearly all of its 19 essays set a high standard for mathematical exposition. The editors succeeded in finding expert authorities for several relevant (and some not so relevant) fields, two of the more glaring omissions being developments in abstract algebra prior to 1930 (although some of the principal achievements of Hilbert, Artin, and Noether are discussed in an article by Gerhard O. Michler), and the theory of Lie groups and algebras, including the contributions of Lie, Cartan, Schur, Weyl, and yon Neumann. Most of the essays present lots of technical information, but the more successful ones do so without getting overly mired in details. Number theorists should be gratified to find four very substantial contributions in this volume. Those by J~irgen Neukirch ("Algebraische Zahlentheorie") and Wolfgang Schwarz ("Geschichte der analytischen Zahlentheorie seit 1890") have the character of sweeping surveys that cover a vast terrain. Neukirch starts with quadratic reciprocity and the Legendre symbol, and then proceeds to consider h o w the search for higher reciprocity laws led Kummer and Hilbert to formulate ever more general symbols to capture the properties of appropriate algebraic number fields. Following Hilbert's reciprocity law, Neukirch takes u p the staggering achievements of Artin, Chevalley, and others w h o created class field theory (he might have said more here about Weber's contribution), then the L-se-

70 THE MATHEMATICALINTELLIGENCERVOL.13, NO. 4 9 1991SpringerVeflagNew York

ries of Artin and Hecke, the Langlands conjecture, and Etale topology. Through the sheer clarity of his prose and a knack for compressing all but the most vital information, Neukirch successfully illuminates some of the principal achievements in one of the richest and most abstract fields of modern mathematics. By contrast, Schwarz's article on analytic number theory, while highly informative, left me somewhat lost in its swirl of facts. S. J. Patterson's essay on "Erich Hecke und die Rolle der L-Reihen in der Zahlentheorie" is one of the few in the volume to delve deeply into 19th-century achievements. Particularly rewarding is the section on the complex multiplication of elliptic functions, which through Weber's presentation in his Lehrbuch der Algebra served as the classical background for class field theory. The author's deep knowledge of and appreciation for the work of Gauss, Kummer, Artin, Hecke, et al. is apparent on every page. Finally, Albrecht Pfister gives a concise survey of the theory of quadratic forms in f o u r s t a g e s h i g h l i g h t e d b y the w o r k of: 1) Minkowski and Hilbert; 2) Hasse, Siegel, and Witt; 3) Eichler and M. Kneser; and 4) Scharlau, Knebusch, and others. The author relates some interesting anecdotal information about Ernst Witt that reveals a good deal about the latter's style; he also clearly indicates how Witt's work emancipated the theory of quadratic forms from number theory and brought it under the umbrella of modern algebra. A second Schwerpunkt, just as fitting as number theory for this Festschrift, consists of four essays that deal with pure and applied analysis. Lothar Collatz's article on numerical analysis stands in a class by itself, as the author draws heavily on his personal experiences as a student just prior to World War II. Beginning with an overview of the tensions that characterized the relationship between pure and applied mathematics at the turn of the century, he goes on to contrast the two major centers where he studied: Courant's G6ttingen and the Institute for Applied Mathematics in Berlin under the direction of Richard von Mises. Von Mises fled from Germany just as Collatz was preparing to write his dissertation under him. With his departure, applied mathematics in Germany went into a steep decline, although Alwin Walther's center in Darmstadt remained active, and Erich Kamke continued to do important work despite being forced to give up his position in Tfibingen in 1937. The latter half of Collatz's interesting article is devoted to a discussion of the reemergence of applied mathematics in Germany following the war. Here he traces the reciprocal influence of several new impulses that came from abroad, including computer technology, functional analysis, and operations research. Dieter Gaier's presentation of developments in complex variable theory starts out promising enough, but about halfway through I just could not keep up with

the relentless outpouring of information. Perhaps this one will be better appreciated by the Fachexperten. By contrast, the lengthy article on partial differential equations and calculus of variations by Josef Bemelmans and Stefan Hildebrandt (with a supplement by Wolf von Wahl) sparkles with insight and clarity. Like nearly all of the contributions to this Festschrift, it contains a rich array of information, including a great deal about the contributions of Leon Lichtenstein and his followers. The difference, however, is that here the authors delineate a clear story line, motivated by a beautifully written introductory section. In it they also express their disappointment that they were unable to cover several other vital parts of this subject, but in so doing they spell out exactly what these were and, in some cases, where one might turn to learn about them. This article is a true gem, displaying expository writing in mathematics at its best. As a companion piece, one can read about Dirichlet's principle, integral equations, and the tradition of Hilbert-Courant in Rolf Leis's portrait of developments in applied analysis and mathematical physics. The interplay b e t w e e n these two fields intensified after around 1905 when Hilbert and his students began developing n e w variational methods designed to deal with boundary-value problems in the theory of partial differential equations. Hilbert's long shadow extended over early developments in the foundations of geometry as well, a theme addressed by Walter Benz, who presents a very nice discussion of Hilbert's Grundlagen der Geometrie and its significance for subsequent research on geometric structures. To pursue this line further, however, one needs to jump from geometry to the article on mathematical logic by Kurt Schiitte and Helmut Schwichtenberg. After quickly sketching the shape of the "foundations crisis" that reared its head at the very end of the First World War--and here the authors happily emphasize that Hilbert never saw himself as a formalist in this debate---they turn to discuss his proof theory and its elaboration in the hands of Ackermann, Bernays, Gentzen, and G6del. One can find much else of interest by flipping back and forth through these pages. For example, the articles by Ulrich Krengel (on probability theory) and Hermann Witting (mathematical statistics) illuminate the marginal status of these fields in Germany both before and after the last war. Michler's paper gives an excellent account of Richard Brauer's work, most of it done in the United States, on the w a y to the classification of finite groups. Hans-Werner Henn and Dieter Puppe present some of the key threads that emerged in algebraic topology from Poincar6 duality to the K-theory of Atiyah and Hirzebruch. But if the individual reader is forced to pick and choose from those topics in the volume that happen to appeal to his or her interests and tastes, everyone w h o has the slightest interest in h o w German mathematics THE MATHEMATICAL 1NTELLIGENCER VOL. 13, NO. 4, 1991 7 1

Meeting of the Society of German Natural Scientists and Physicians, Mathematics and Astronomy Section, September 1890.

fared in the wake of the country's harrowing political events should be strongly advised to read and ponder the opening essay, written by Norbert Schappacher with the assistance of Martin Kneser, "FachverbandInstitut-Staat". This penetrating study deals with the external circumstances that shaped German mathematics from 1890 to the early post-war years, concentrating particularly on the tumultuous repercussions of the Nazi period. In it the authors raise several important themes in sketching developments within the German mathematical community during the Wilhelmian period: the polarization between G6ttingen and Berlin echoed in the traditions of Riemann vs. Weierstrass, the politicization of German mathematics through the activities of Felix Klein and the Prussian ministerial official Friedrich Althoff, the initial entry of big business in the form of the G6ttingen Association for the Promotion of Applied Physics and Mathematics, and 72

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

the tension between nationalist-oriented mathematicians and those with an internationalist outlook. The documentation on the destruction of German mathematics during the Nazi era is meticulously researched and often startling. Between 1932 and 1939 the total number of students at German universities declined from just under 100,000 to around 40,000. This decline, however, tells only part of the story, as it was far from uniform, with some fields affected far more than others. For example, the drop in enrollments in medicine and chemistry, while significant, was not nearly so precipitous as that in physics, which by 1939 had fallen to roughly a quarter of its former level. Still, no field felt the crunch so dramatically as mathematics. In the summer of 1932 there were 4,245 mathematics students attending universities in Germany. Seven years later the number was down to 306, just 7.2% of the pre-Nazi figure.

Within the mathematical community itself, Schappacher and Kneser trace the damaging effects on representative institutes and individuals in considerable detail by following the three waves of dismissals that swept through Germany following the enactment of laws to "purify" the civil service (which included university professors). The first of these took effect in April 1933, sounding a virtual death knell for G6ttingen mathematics: less than three weeks later Richard Courant, Felix Bernstein, and Emmy Noether were informed by telegram that their services were no longer

In the summer of 1932 there were 4,245 mathematics students attending universities in Germany. Seven years later the number was down to 306, j u s t 7.2% of the pre-Nazi figure. required. Regarding this sudden and wholly unanticipated action, the authors, noting that G6ttingen had long been a fortress for right-wing agitation, draw the plausible conclusion that the Ministry did not want to risk losing control over the situation and undertook this preemptive strike primarily to nullify a potential firestorm set by grassroots leaders. Rather than wait for the next blow to fall, Hermann Weyl accepted a position on the faculty of the newly founded Institute for Advanced Study. Proud and defiant, Edmund Landau decided to test the new waters. When the semester opened he found SA-guards posted at the doorway to his lecture hall and one student inside. As a consequence, he "voluntarily" went into retirement. The boycott of Landau's class had been led by none other than Oswald Teichm~iller, the one truly brilliant mathematician among the Nazi rabble. The first wave of dismissals hit hardest in G6ttingen, b u t the authors also follow its c o n s e q u e n c e s in Aachen, Breslau, Freiberg, Leipzig, Munich, and K6nigsberg. The situation in Berlin was strongly colored by the presence of Ludwig Bieberbach, the notorious proponent of "Deutsche Mathematik." Bieberbach had been late to jump onto the Nazi bandwagon, but only months after the destruction of the Mathematics Institute in G6ttingen, he made a bold move to politicize German mathematics. In a published lecture that purported to clarify differences in mathematical styles by appealing to racial and national stereotypes, he seized on Landau as a prime illustration of the "Jewish t y p e " and praised the G6ttingen students who boycotted his classes for their "manly action" [mannhaftes Auftreten]. And w h e n Harald Bohr criticized him in a Danish newspaper article, Bieberbach, as Schriftenleiter for the Jahresbericht of the DMV, published an " O p e n Letter to Harald Bohr" calling him a "pest on all international cooperation." Since Bieberbach had published the letter against the expressed

wishes of the only two co-editors who knew about it beforehand (Helmut Hasse and Konrad Knopp), this set the stage for a dramatic confrontation that culminated in September 1934 at the annual DMV meeting held in Bad Pyrmont. There, flanked by a throng of right-wing students w h o m he had invited, Bieberbach vied to implement the "F~ihrerprinzip" so dear to Nazi idealogues, by entering a motion in which he nominated Erhard Tornier, a second-rate mathematician with a first-rate Nazi pedigree, for the post of F~ihrer of the DMV. When this coup attempt failed, he later tried to intimidate his rivals in the DMV by exploiting his connections with Theodor Vahlen, a former mathematics professor in Greifswald and virulent Nazi who rose to an influential position in the Reichsministerium. But having survived the s h o w d o w n in Bad Pyrmont, Oskar Perron and Konrad Knopp were now prepared to call his bluff, and in early 1935 Bieberbach was forced to step down from the executive committee of the DMV. Schappacher and Kneser not only present a wealth of detailed information about these and other dramatic events but they also help to illuminate the roots of such conflicts. For example, they note Bieberbach's role in the earlier battle that ensued w h e n Hilbert sought to oust Brouwer from the editorial board of Mathematische Annalen, an episode recently chronicled by Dirk van Dalen in the Mathematical Intelligencer (vol. 12, no. 4). The authors conclude quite correctly that this battle and the whole intuitionist-formalist debate that echoed throughout the Weimar period carried broader political implications, and these set the stage for much of what followed during the early Nazi years. In assessing this volume as a whole, though it contains much to be admired from a technical standpoint, I found it left me rather disappointed. For one thing, the authors rarely allude to the larger sweep of events that shaped mathematics in Germany, and too often their accounts simply trace a chronology of semirelated ideas culminating in present-day developments. The inevitable result is a faulty historical perspective, or none at all. Indeed, the collective impression created by these essays is that the proliferation and absorption of mathematical ideas just happen, as if they emerged as byproducts of a harmonious, perfectly regulated mechanism. I do not wish to press this point too hard, as the authors often explicitly indicated that their objective was not to write an historical survey but rather to give a subjective sketch of important developments in their respective fields. But it seems to me that something vital is missing here. Should not a volume like this one say something about the state of mathematics in Germany 100 years ago, indicating which fields were important then and now? Can one meaningfully talk about changing directions of mathematical research over the last hundred years without mentioning the often conflicting visions of mathematics that have prevailed from time to time? What kind of THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991 7 3

mathematics was fashionable and when, maybe even why? Even the most provisional answers to questions like these are b o u n d to be interesting and provocative as well. Unfortunately, these broader considerations largely go ignored. The quality and scope of the articles is also quite uneven, a fault that may, in part, be blamed on the editors, who apparently gave the authors little guidance about what they should write or should not write--"[wir] haben nicht versucht, die Autoren der fachlichen Beitr~ige zu einem einheitlichen Konzept zu fiberreden"--with predictable results. This may explain why some of the essays tend to drift away from or never really focus on the central theme: German contributions to the mathematics of the last hundred years. A particularly bewildering feature of this volume is the (in effect) random arrangement of the articles (except for the first, they appear in alphabetical order by author). This only accentuates the all too flagmentary impression the book leaves, which is most unfortunate considering that many of the individual articles stand up very well on their own, having been written with consummate attention to detail. They simply do not mesh well together, and I doubt that many people would find pleasure in reading this volume from cover to cover. After reading these essays--I can't remember in what order--I myself came away asking one fundamental question: do mathematicians today really believe, like Paul Halmos, that their subject represents something more than the sum of its parts? Around the turn of the century, Klein and Hilbert struggled mightily to preserve and protect their respective visions of mathematics as a unified whole. Klein, being deeply rooted in 19th-century geometry and physics, was tempted to pose the issue in the broadest possible terms, and to solve it he tried, among other things,

Around the turn of the century, Klein and H i l b e r t s t r u g g l e d m i g h t i l y to p r e s e r v e and p r o t e c t their respective v i s i o n s o f m a t h e m a t ics as a unified w h o l e . mobilizing a giant army of experts w h o compiled Die Encyklopddie der mathematischen Wissenschaften. Hilbert saw the problem in somewhat more limited (some might say realistic) terms, and thus could offer a much cleaner solution exemplified by his lecture at the Paris Congress of 1900: a set of " p r o b l e m s " - - s o m e old, some new--designed to direct and orchestrate mathematical research. Where does the enterprise stand today? Clearly it has become more difficult than ever to find a consensus, but the hope once held by Klein, Hilbert, and Weyl springs eternal. In the meantime, those w h o continue to profess the ancient faith in 74

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

mathematics (or at least "pure mathematics") as a unified endeavor should take little solace from a volume like this one.

Mathematics Department Pace University Pleasantville, NY 10570 USA

The reviews section of the Mathematical Intelligencer apologizes to Stephen Hawking for its glaring lapse in vol. 13 no. 3, giving wrong versions both of his name and of the title of his book A Brief History of Time.

A Century of Mathematics in America. 3 vols. Edited by Peter Duren, assisted by R. A. Askey, H. M. Edwards & U. C. Merzbach. Providence, R.I.: Amer. Math. Soc., 1988-1989. US $212.

Reviewed by W. H. J. Fuchs and Lee Lorch The N e w York Mathematical Society was founded in 1888 and changed its name to the American Mathematical Society in 1894. The volumes before us are part of the Society's celebration of its centenary. The Society Committee in charge (Peter Duren, Chair, Richard Askey, Bruno Harris, Uta Merzbach) began by inviting a number of prominent mathematicians to contribute "an autobiographically oriented historical article," to what was to be a single volume. The response was enthusiastic, the interest in the mathematical community enormous. To a willing committee came many suggestions. The project grew to two and then to three large volumes. They total more than 1700 pages and comprise 106 different articles, of which 34 are reprints, on a great variety of topics. These constitute valuable source material for historians of mathematics and of education, and provide intriguing and instructive reading for contemporary and future mathematicians everywhere. Space permits comments on only a few of the articles.

Partial Classification of the Articles The wide range and variety of the articles makes a complete description of their contents impossible. A very rough classification might be: 1. Straightforward historical memoirs with little if any "autobiographical component." 2. The growth of US mathematics and of some famous departments.

3. Outstanding mathematicians. 4. Autobiographical writings, some anecdotal, some administrative, some like Hassler Whitney's delightful account of "Topology Moving Toward America" (vol. 1), incorporating serious discussions of mathematical topics, some conveying a sense of the political, economic, racist, sexist, or other adventitious pressures that made life so difficult for many. Peter Hilton's "Reminiscenses of Bletchley Park'" (vol. 1), a lively account of the milieu w h e r e the sensational codebreaking took place, includes a frank report on the shameful persecution later inflicted upon Alan Turing, the central figure. 5. Articles about specific mathematical developments, some reducing the autobiographical component to the point of self-effacement. The Collection as a Whole

What makes the collection so attractive is the great variety of styles and the charm of much of the writing. Many of the most enjoyable articles do not fit into a single category, but mix the ingredients of history, personal account, and mathematical discussion, like R . W. Hamming's "The Use of Mathematics" (vol. 1) and Whitney's article mentioned above. In addition to the wealth of information they contain, these articles provide an excellently presented exposition of many branches of mathematics, including applied mathematics. Much of it illustrates the growing cross-fertilization between different parts of mathematics, as well as their increasing value for old and new partner sciences. This is a welcome antidote to the

Richard Askey

fear that our subject was in danger of fragmentation and isolation. One example of reassurance is found in David Blackwell's observation (vol. 3, p. 607) that much really interesting mathematical research at universities is being done outside mathematics departments. In their entirety, these articles cover the rise of US mathematics during the century and some of the causes: the modest, but not negligible, beginnings; the great scholars whose research, vision, and determination created the centers offering inspiration and opportunity admired worldwide; the influx of refugees (some already world-renowned, others destined to become so); Sputnik with the attendant massive expansion in US funding of research. The effect of the brain drain (that is, of the post-war immigration of distinguished scholars who were not refugees) is not discussed, either as to its benefit to the US or its detriment to some other countries. Of course, all of this was made possible by the great resources of the US, especially after World War II, from which it alone among the great industrial powers emerged unscathed, even strengthened, and the public policy that resulted. That war (as several of the articles illustrate), and also the reaction to Sputnik, brought about the acceptance of mathematical research as a profession, not simply the hobby of professors in a few eminent universities. The Committee and Editors have earned our gratitude. This monumental, fascinating, occasionally anguishing, sometimes amusing work conveys a good impression of the wonderful success story of mathematics in the US.

Peter Hilton THE MATHEMATICAL INTELL1GENCER VOL. 13, NO. 4 9 1991

Springer-Verlag New York

75

Some Definitions The books use "America" as a synonym for the US. Other parts of the continent are not featured--not even Canada, which has participated in the American Mathematical Society from its early days. One of the Society's most influential and longest serving secretaries, R. G. D. Richardson, was from Canada, as were a number of outstanding American mathematicians, professors at the Institute for Advanced Study, Brown, Cornell, Harvard, Princeton, Chicago, Berkeley, Yale, NYU, Michigan, Tufts, and elsewhere. Canada also provided refuge for a number of US mathematicians driven from the US by McCarthyism. Its star too has risen in the mathematical firmament. "Mathematics" is used primarily for the researchoriented pursuit of mathematical knowledge, the principal motivation of the Society, as is made clear by the (reprinted) articles in vol. 1 by Thomas Scott Fiske, a founder and early president of the Society. They also record E. H. Moore's influence in prompting the establishment in 1903 of associations of teachers in the schools. 1888 and All That The Society was founded in a period of great ferment. There did not exist anywhere in the US an articulated system of public education leading through university. In 1881 (probably also still in 1888), N e w York City had no public high schools. The State legislature made provision for them only in 1896. This impeded the burgeoning industrialization of the US and the social program of a nascent labor movement. Businessmen demanded decisive revamping of all educational levels. The unions demanded free ele-

David Blackwell 76

THE MATHEMATICAL INTELLIGENCER VOL, 13, NO. 4, 1991

mentary education, compulsory attendance, and child labor laws. By 1888 the US had enough schools that there were by then more teachers than clergymen or lawyers. Business tycoons and university presidents wanted all this coordinated and controlled. Various professional organizations, including our Society, came into being. Mathematics was a respected part of the classical curriculum and was valued also by the educational reformers. The time was ripe for a voice for the mathematical community. It was also a high-water mark of massive immigration. All these aspects are summarized by way of background in a book by Professor S. Gorelick, [NY] City College and the Jewish Poor, 1880-1924 (Rutgers University Press, 1981). But, as she reports the changes which opened that period (p. 138), The liberalization of academia let flow academic theories of the racial and cultural inferiority of Blacks, Native Americans, Jews, Italians and Poles. These theories permeated college curricula. These doctrines did not originate in the US. They came from a Europe anxious to justify colonialism. Imported, they served well a policy of dispossessing Native Americans, depriving African-Americans of citizenship rights and legal protections, and dominating the flood of immigrants. The sociologist E. A. Ross characterized the Russian Jewish immigrants as repulsive in appearance and "of obviously low mentality," evidenced by small crania. Frederick Jackson Turner, historian of the US frontier and 1909-1910 President of the American Historical Association, declared that the immigration of Italians, Poles, Russian Jews, and Slovaks was a "loss to the social organism of the United States." Racist denunciations of Native Americans and African-Americans bedevil US society even now. Respected academic journals publish such; some foundations provide grants to professors preaching them. They are used to gut social programs and to excuse the practice of blaming the victims for their own plight. Given the atmosphere at the beginning of the century under consideration, it is small wonder that some influential mathematicians acted in that spirit and that both distinguished and not-so-distinguished institutions excluded African-American students and staff and discriminated quite openly against other groups. This too is part of our record. We need to ponder our current (and future) activities with this in mind. The article by James A. Donaldson and the interview with David Blackwell, both in vol. 3, furnish helpful insights. Regrettably, there are no contributions that address the problems of Native Americans or Hispanic Americans. Similar theories were in vogue in respect to the intellectual powers and emotional stamina of women. These too are still voiced, and serve similar purposes.

Lipman Bets

J.L. Kelley

J.C. Scanlon

All photos in this review are from I Have a Photographic Memory by Paul Halmos, 9 1987, American Mathematical Society.

Some S h a d o w s The way the articles were solicited makes inevitable large variation in the stress put on different aspects. The subject of refugees from Nazi Germany receives careful professional treatment in N. Reingold's article, reprinted in vol. 1 from Annals of Science. Lipman Bers presents a more personal account in a gripping contribution that, w h e n delivered as a Society lecture, evoked a standing ovation. Ivan Niven provides ("The Threadbare Thirties," vol. 1) a vivid picture of how those dismal years affected mathematicians. So too does J. L. Kelley (vol. 3) in a lightly written piece with very serious content. In it he includes the struggle against the notorious California loyalty oath, in which he played an important role, and recounts some of the academic freedom issues forced on academics after World War II. Similar references occur in other articles. In one of the six frank and forceful articles he contributed, some on purely mathematical topics, others on h o w mathematics was managed, Saunders Mac Lane discloses (vol. 2, p. 149) h o w a soon-to-be leading mathematician was denied an appointment, despite departmental recommendation, because of the former political activities of the candidate's father. Chandler Davis, himself a refugee in Canada, contributes a stirring account ("The Purge," vol. 1) of how the US witch-hunt operated and what it did to a number of mathematicians and the institutions they served.

Discrimination on grounds of race or gender, mentioned above, also casts its long shadow.

W. L. Duren's Survey One remarkable article essays an overall view of mathematics in the US educational framework during the entire period. This is by W. L. Duren ("Mathematics in American Society 1888-1988. A Historical Commentary," vol. 2, pp. 399 447). An extensive review is in MR 90k:01015. Duren takes a broader view than the other contributors by his emphasis on both school and college mathematics. He is not merely descriptive; there are frequent calls to action. These may well influence the future policies of the mathematical community; they require thoughtful attention. Many of his concerns are those of all of us. Many of his suggestions will command support. His call for an effective mathematics lobby is already the view of major mathematical organizations. They support him also in insisting that post-secondary mathematicians exert serious influence on lower school curricula. We would go further: Of at least equal importance would be ending the underfunding, the overcrowding, and the overburdening of teachers, in the lower schools. Innercity schools and impoverished school districts need special support. All this requires our activity too. Decisive improvement is a sine qua non for an adequate infrastructure for our science, as well as for the general educational needs of today's world. THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

77

W. L. Duren

He advocates (p. 436), as do we, a better appreciation of the contributions and potential of women, and notes the importance of the organized struggle women have had to wage. In this context he reminds us, appropriately, of the role of Mary Gray, founding president of the Association for Women in Mathematics. Minorities deserve and need similar approbation. So do all dispossessed. We get nervous at the point (p. 413) where he says: Around 1954 three little-noted events signaled the end of the era of excellence. . . . Finally there was the 1954 Supreme Court decision.., that outlawed segregation in the schools and guaranteed the right of public education without restriction by race. This decision helped to justify a gradual shift from competitive excellence to concern for the underprivileged and underperformers in society. Mathematicians certainly shared this concern but it created special difficulties for mathematics. How he can characterize that world-famous decision as "little-noted" mystifies us. But more importantly, there is a fundamental defect in his interpretation of the situation. To guarantee equal opportunity to the "underprivileged and underperformers" would not cause a "shift from competitive excellence." It would open competition for the first time to the poor and 78

THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4, 1991

underprivileged. To make this possible by special measures, as need be, is a requirement that history has imposed on US society. The same issue surfaces in his dismissal (p. 426) of open-admissions policies as devices "to maximize enrollments and therefore the subsidy paid by the state" which divert "educational funds to unproductive efforts." Whatever may be thought of the effectiveness of open-admissions policies, we think it unfair to ascribe their existence to base motives. We are apprehensive about his support for the curricular proposals of Reagan's Secretary of Education, Wm. J. Bennett (pp. 427, 428, 530). These Duren characterizes as a "return to a secondary curriculum in which about two-thirds is a required common core of proven value, including three units of mathematics." He calls us "to go back into the national political arena urging the establishment of a general studies curricul u m , s u c h as the one t h a t S e c r e t a r y B e n n e t t proposed." We could support the three units of mathematics, but we dare say that not even these would be the same as in schooldays of yore. What of the rest of the "common core"? Is it to be restricted to the classics, literature, and history of the white, male West? How would minorities and women respond to an educational process so defined? What would its overall effect be? When leading universities decided to alter their "common core" by including African-American, Third World, and female contributions, Bennett took to the hustings to condemn these inclusions and to demand that these courses revert entirely to their traditional offerings. If we really wish to attract minorities and women to our community, to the benefit of both democracy and scholarship, we can expect to do so only via an educational system in which they have a real part, and where their feelings of self-worth are reinforced, not destroyed, where the majority students will acquire appreciation for the achievements of all. This is not Bennett's program, but it should be ours. The reservations we have expressed on some aspects of Duren's extensive analysis do not, of course, diminish our support for what we take as his main point, namely that the mathematical community needs a strong lobby on behalf of our science, and that it needs to address its problems broadly. Where Next?

History has much to teach us. The volumes before us testify to this. Shall we be willing and able to act upon its lessons? It may take some courage and certainly some creativity. Department of Mathematics Cornell University Ithaca, NY 14853 USA

Department of Mathematics York University North York, Ontario M3J 1P3 Canada

Robin Wilson*

Computing on Stamps Many stamps feature computers and related topics. Some are concerned with the uses of computers in society, while others relate to the history of computing and calculation. The first mechanical calculating machines appeared in the seventeenth century, following the invention of logarithms by John Napier and the development of such instruments as the slide rule, pictured on a 1957 Romanian stamp. An early machine was described by Wilhelm Schickard in 1623, and is featured on a 1973 stamp from the Federal Republic of Germany. Other calculating machines, some of which have survived to the present day, were constructed by Pascal and Leibniz, who have appeared on stamps of Monaco and the Federal Republic of Germany, respectively. The central figure of nineteenth century computing was Charles Babbage, whose 200th anniversary occurs in December 1991, and who was commemorated by a British stamp last March. He may be said to have pioneered the modern computer age with his analytical engine, even though the technology of the time was insufficiently advanced for a working version to be developed.

* C o l u m n editor's address:

Facultyof Mathematics, The Open University,Milton KeynesMK7 6AA England THE MATHEMATICAL INTELLIGENCER VOL. 13, NO. 4 9 1991 Springer-Verlag New York 7 9