No title

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

Criticisms of Shafarevich

,Defending Shafarevich,

Criticism of the leading Moscow algebraic geometer I. R. Shafarevich for his essay "Russophobia" has continued. See The Mathematical Intelligencer, vol. 14, no. 1, pp. 61-62, and vol. 14, no. 2, pp. 3-4. It was noted there that hundreds of mathematicians, mostly American, had published an open letter to Shafarevich in the Notices of the American Mathematical Society. Professor Shafarevich's rejoinder has appeared in the Notices 39(1992), 683. On 16 July, the National Academy of Sciences USA wrote Shafarevich that its governing council condemned "Russophobia" for its anti-Semitism. The letter continued,

The Mathematical Intelligencer (vol. 14, no. 1) published extracts from an interview by M. Popovskii with B. Moishezon, who had been a student of Igor Shafarevich. The interview deals with Shafarevich's essay "Russophobia." There are serious objections to your treatment. (1) B. Mo~shezon says that in reading "Russophobia" he was shocked by the sentence

If "Russophobia" represents an accurate expression of your views, and if our information of the composition of the algebra section [of the Steklov Mathematical Institute] is a reflection of your influence on hiring and appointment practices, you may wish to consider whether it is appropriate for you to maintain your membership in the National Academy of Sciences. Professor Shafarevich replied 4 August denying that the essay is anti-Semitic, and disclaiming any role in hiring-practices excluding Jews. He concluded, By suggesting that I personally resign my membership from the Academy, you are in this way asking me to agree with your accusations, which I find absurd and scandalous. I never asked to be elected as a foreign member of the National Academy (though I was happy to be honored in this way). Therefore, I feel that the question of my continued membership in the National Academy is the Academy's own problem. The Intelligencer has received many communications on this issue. Our focus being mathematics, we cannot accommodate extended controversy on the details of "Russophobia."

Chandler Davis

The chosen people introduced the concept of the Messiah in order to gain sovereignty over the world. I do not find that sentence in the Russian edition. I ask Moishezon or Popovskii to state the page reference. (2) The other quotation Mo~shezon relies on is from a private conversation 30 years ago. In civil society such a report can not be used as proof. B. Mo~shezon has evidently learned his standards of reference not from I. R. Shafarevich but from other teachers. (3) The editor says Shafarevich's essay is "no doubt extremely nationalistic" without defining nationalism. If this is understood as a claim of exclusiveness of some nation i.e., chauvinism--then the editor's assertion is unsupported by anything in the essay. (4) M. PopovskiL while not claiming to know what has influenced Shafarevich, ventures that it may be the thirst for a powerful r0gime. But w h e n we lived under a powerful r0gime, Shafarevich fought against it, while neither Moishezon nor Popovski~ was much distinguished among its active opponents. (5) I hope that among I. R. Shafarevich's many students, who are much indebted to him, some will raise their voice now in defense of their teacher, if only to make up for their silence at the time when he was persecuted in our country. S. P. Demushkin Volgogradskii 114/1/55 Moscow 109443 Russia

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 9 1993 Springer-Verlag New York

3

Shafarevich Furor It's a good thing, I guess, that some mathematicians are putting a lot of energy into exposing and denouncing the anti-Semitic theories expounded by I. R. Shafarevich in his article "Russophobia." Joan Birman says (Intelligencer 14, no. 3, 3-4) that Shafarevich's role in contemporary Russian anti-Semitism is being discussed in The New Republic, so shouldn't mathematicians take the matter equally seriously? But her letter, the open letter in the Notices of the AMS (39(1992), 264-265), and the move by the National Academy of Sciences USA censuring Shafarevich, are much too narrowly focused. They treat Shafarevich and the movement he apparently represents as a singular phenomenon, but his theory is hardly unique. As critical articles about him (especially in Europe and Russia) have recognized, "Russophobia" states an often-heard theme, that a nation's historical uniqueness is being worn away by a hostile people. Other versions of this theory may be supported with less erudition and fewer academic titles, but they are being put into practice, in ethnic violence all over the territory of the former Soviet Union and elsewhere in Eastern Europe. For mathematicians to evoke possible future mass murders of Jews from a movement using "Russophobia" as "intellectual foundation," while making no mention of massacres of other groups already taking place on very similar "intellectual foundation," is at the very least a lapse of taste. Russian critics of Shafarevich, notably V. Karpov in the March 1990 issue of the literary magazine Oktyabr, have stressed the continuity of his anti-Semitism with his rejection, not only of the West, but of much of what is characteristic of the 20th century (and the 19th). Granting m a n y of Shafarevich's objections to Western materialism, one still might take him to task for his apparent nostalgia for absolute monarchies; or for his contemptuous dismissal of the contributions of Freud, Schoenberg, Picasso (?!), Kafka, and Brodsky; or for signing a call for the creation of a Russian Communist Party (in 1990). But these, presumably, are matters on which reasonable people may reasonably disagree, whereas the implications of "Russophobia" for Russian Jews d e m a n d immediate repudiation. The August move by the National Academy of Sciences inviting him to resign as a foreign associate raises new questions. As an outsider, I wouldn't think of meddling in NAS policy matters, but there does appear to be a question of inconsistency. Is Shafarevich being condemned for his ideas or his actions? The letter from the Council of the NAS to Shafarevich refers to both, although the NAS has not customarily censored political opinions of its members. The late William Shockley remained a member long after he had propounded his theories on race and intelligence. Deeds are another matter, and for this reason the claim 4

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

that Shafarevich was partly responsible for the refusal of the Algebra section at the Steklov Institute to hire Jews is especially important. But the claim seems to be based wholly on the fact that the author of "Russophobia" is head of the Algebra section. Russians who have no sympathy with his theories tell me they find the claim absurd. Can we reject their presumption without evidence? Even if Shafarevich were complicit as charged, he would not be the only prominent scientist to have behaved reprehensibly. The response to Shafarevich contrasts sharply with the treatment of another scientist who has found a second vocation providing "intellectual foundation" for a racist political platform. Unlike Shafarevich, whose political influence is apparently too slight even to get him a functional blackboard for his office, the eminent physicist Yuval Ne'eman has been a major player in Israeli politics for years--co-founder of the Tehiya party, a leader of the settlement movement, and Minister of Science for much of the last decade. His party's platform calls for the deportation of all refugee camp residents and the denial of full political rights to other Palestinians in the occupied territories. Recently, Ne'eman publicly returned his Israel Prize, to protest the award of the same prize to Palestinian author (and Israeli citizen) Emile Habibi. But no one objects to Ne'eman's sponsorship of international conferences in mathematical physics; no one is asking him to withdraw as foreign associate of the National Academy of Sciences. Israeli voters may have put an end to Ne'eman's political career this year: His party was completely shut out of the Knesset for the first time since 1981. If Shafarevich ever acquired the kind of political power Ne'eman had, and the theses of "Russophobia" were put before Russian voters, one may hope they would show similar good judgment. Meanwhile, mathematicians should not let an imagined future return engagement of Hitler blind us to the tragic consequences of real and present racism, whatever its target. Michael Harris Department of Mathematics Brandeis University Waltham, MA 02254 USA

Catalan N u m b e r s John McCarthy (letter, p. 5, The Mathematical Intelligencer vol. 14, 1992, no. 2) is certainly right that the equation xS 2 = S - 1 leads to a simple proof of the formula

(1)

for the kth Catalan number. Indeed, we derive the generalization xS p = S - 1

(2)

of (1) as equation (2.9) of our paper [HP], but point out that it requires the sophisticated Biirmann-Lagrange inversion theory to derive from (2) the formula = ;

for the kth generalized Catalan number, in the case p I> 3 (where ck = 2Ck). It was, of course, our principal purpose in [HP] to derive this formula for pCk, p / 3, by elementary arguments. We gave the alternative proof of the formula for Ck in [HP] in order to show the elegance of Andr6"s method and to be able to give his lovely solution of the Ballot Problem.

Reference [HP] Hilton, Peter and Jean Pedersen, Catalan Numbers, Their Generalization, and Their Uses, The Mathematical Intelligencer vol. 13 (1991), no. 2, 64-75. Peter Hilton Department of Mathematical Sciences SUNY Binghamton Binghamton, New York 13902-6000 Jean Pedersen Department of Mathematics Santa Clara University Santa Clara, California 95053

jectives like "arithmetical," and talk of "arithmetic groups" with a stress on the e; but we still say "dynamical system." "Mathematics" is singular, but we have no idea whether "dynamics" is singular or plural. We talk of "Gaussian curvature" but "Gauss map"; say that an integral is "Riemann" but a manifold "'Riemannian.'" Of course a manifold may also be "Nash." A lot of this is historical, of course---or should I say "historic"? and stems from the fairly recent adoption of the principle that there is no n o u n that cannot be verbed. Or adjectived. My main point is that your proposal to promote "strongly convergence" is precisely the wrong w a y round. It is the adverb that should be eliminated, if anything is to go. As sports commentators say, "the kid done real good." If we gonna be nongrammatic, we gotta be real nongrammatic. The sequence done strong convergent. Ian Stewart Mathematics Institute University of Warwick Coventry, CV4 7AL England (Please! I didn't promote the usage "strongly convergence" I noted its occasional occurrence. I agree, though, that the equally ungrammatical formation "'strong convergent" is slightly less jarring. Of course the question, "'Which is to be master?" in this context has a clear-cut answer: the Editor. Authors writing of strongly convergence during my term may find that their manuscripts are red-pencilled.)

Which Is to be Master II 1 Which is to be master? I agree completely about "eigenvalue" and the like--there's no profit in pedantry. But language is a system for communication, and if too much damage is inflicted on grammar then the result becomes unintelligible. Scientific literacy suffers because English is its lingua Franca, 2 but most scientists are not native English speakers. Scientific literacy suffers even when the writers are native English speakers because the training of scientists seldom involves teaching them h o w to write. The terminology of our subject is horribly inconsistent. Homology is a covarient functor but cohomology is contravariant. We have eliminated old-fashioned ad-

1 See vol. 14, no. 2, p. 51. 2 A b o r r o w e d Italian (not Latin) p h r a s e about the Franks (not French) w h i c h says a lot about English. Or, as a former US official said, "You can't trust the Russians because they have n o w o r d for dOtente. "

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993 5

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

There Are Too Many B.A.D. Mathematicians Melvin Henriksen I have always been slow to learn the ways of mathematicians and, for most of my life, reluctant to be critical of those with substantial reputations for doing research. In the mid-60's, my former colleague Holbrook MacNeille, w h o worked for the Atomic Energy Commission before becoming the first Executive Director of the American Mathematical Society, remarked often that whereas laboratory scientists were mutually supportive in evaluating research proposals, mathematicians were seldom loath to dump on each other. I attached little significance to what he said because at that time most worthwhile research in the United States was funded and there seemed to be enough money for all but the most greedy. Perhaps some nastiness existed, but not on a scale that was doing much harm. Federal support of research in mathematics done in universities is a post-Second-World-War phenomenon that was a spin-off of the contribution made by mathematicians and scientists to the allied victory. Research grants were made to individuals rather than institutions, to reduce fear of federal control of education. For, unlike today, in the immediate postwar years there was great concern about the unprecedented growth of the federal government. Americans' fear of big government was overcome by the cold war and the national mania to beat the Russians to the moon. The number of research grants to individuals grew rapidly. University administrations complained that the need to supply more laboratory and office space to visitors and/or replacements for regular faculty whose time was being released for research had indirect costs. Soon "overhead" charges were added to these grants. Initially small like the nose of a camel, with time they occupied more and more of the tent. Overhead charges from these grants became a significant part of university budgets, and staff were hired to help faculty hustle them up, and research that attracted support money was considered more worthwhile. Love of Mammon 6

overcame, with little or no debate, any residual fear of control of research or education by the federal government or other granting agencies. Money flowed freely, and nobody seemed to notice that converting research scientists into fund-raisers amounted to creating a Frankenstein monster. The mathematical community greeted the n e w prosperity with enthusiasm. Page charges were introduced for publication in many journals to transfer some of the cost of publication to federal agencies. Those without grants had to beg their institutions to pay page charges or accept the status of mathematical welfare recipients. Existing graduate programs expanded and n e w ones were created with the help of federally financed fel-

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 9 1993 Springer-Verlag New York

lowships. The number of doctorates awarded in the mathematical sciences in the United States and Canada increased from 300 in 1959-60 to over 1200 in 1967-68 and was expected to double by 1975. (It actually peaked at a little over 1500.) So the effects of any backbiting were made invisible by a federally financed pax mathematica. After a little over a decade of prosperity, the public's love affair with science and technology ended, perhaps because we had gotten to the moon first and, more likely, because the bill for the war in Vietnam came due.

A Lost Generation

of Mathematicians

By 1970, the illusory bottomless pit of need for mathematicians had been filled as far as the taxpayer was concerned, and graduate schools were full of able students about to earn a Ph.D. and compete for the few existing jobs with those being laid off by academic institutions and industry because of budget cuts. Funding could not keep up with the increase in the supply of eager and able mathematicians trained to do research. Universities rued the days w h e n they expanded in anticipation of continued federal funding, and dependence on "soft" money joined the list of sins not to be committed again by academic administrations. Tenure, once automatically granted to the capable and hard-working at all but the most elite institutions, became precious. Faced with a faculty more than half of which had tenure, often while in their thirties, with little hope of turnover, deans and presidents began to insist that only beginning Ph.D.s be hired, and reduced the number of positions that could lead to tenure. In the first half of the 1970s, a goodly number of capable mathematicians left the profession for different if not greener pastures. When the dust had settled by the middle of the decade, most of the new Ph.D.s had gotten jobs at undergraduate colleges they had never heard of before. Most of these y o u n g mathematicians, imbued with the ideals of their major professors and full of enthusiasm about the research area of their dissertation, wanted to continue to be active. Faced with heavy teaching loads, committee responsibilities, and little or no encouragement from their new senior colleagues (whose attitudes toward research had often been shaped by being denied tenure at a research-oriented department), most gave up in a year or two. The abrupt downturn in support kept their former major professors busy licking their wounds and wondering what to do about their o w n junior colleagues. As far as research opportunities were concerned, most of the Ph.D.s trained in the 1960s were cut adrift. According to E. T. Bell, projective geometry was developed by Poncelet while in prison, and Ramanujan did great work in isolation, so it might have been possible for

these young orphans to remain active in research. In fact, few of them did, and in spite of substantial expenditures on their training, most of them became a lost generation as far as research was concerned. Research grants in the United States were used to increase the salaries of individual faculty members by 2/9 (as if all research activity occurred only in the summer months) and to bring in substantial overhead to the coffers of the university, rather than as a means of nurturing the mathematically y o u n g or encouraging research outside of a small number of centers. Comp e t i t i o n for s u p p o r t i n t e n s i f i e d , a n d losing it amounted to a pay cut and a reduction in the budget of one's academic employer. At many "publish-or-perish" institutions, getting grants became a necessary condition for tenure or promotion. This raised the stakes in the game of competing for them, and those with funding were reluctant to share it with their brethren in the boondocks, where most of their recent Ph.D.s had taken jobs. A certain amount of money was put aside to support young mathematicians with major research accomplishments, but little was done to help the bulk of the new Ph.D.s to stay active in the face of poor working conditions and little stimulation. In sharp contrast, Canada developed a system whereby established senior mathematicians controlled the bulk of the research funds, but could not use them to supplement their own salaries. As a result, beginning Ph.D.s with research ambitions could count on two to three years of support, and the most able could get it for five years in the face of a job market even tighter than in the United States. In the U n i t e d States, i n s t e a d o f trying to nurture and s u s t a i n our m a t h e m a t i c a l c o m m u n i t y , w e s e e m to turn our b a c k s as a small b u t i n f l u e n t i a l group w r e a k s havoc. I call t h e m B.A.D.: Bigoted And Destructive.

They have always been with us; what has increased in recent years is their ability to be destructive. They are often very able at research and it is easy to believe that their proven expertise in one area qualifies them to pass judgment on every part of mathematics; just as we might expect someone w h o goes over Niagara Falls in a barrel and lives, to be able to bring peace to the Middle East. As members of the elite, they have no doubt that they know what is important, and all else is inconsequential or trivial. They usually write only for fellow experts and regard writing for a general mathematical audience as a waste of time. They often write referee's reports or reviews of research proposals that are nasty or condescending. Clear exposition, if it adds a few pages to a research paper, elicits often the contemptuous suggestion that the paper be sent to the American Mathematical Monthly. They often say that too many papers are published, and would not be caught dead giving a 10-minute paper at a meeting of the A.M.S. While proclaiming their devotion to high standards, they feather their o w n nests by reducing the THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

7

number of serious competitors for grants or space for publication in high-prestige journals. For in quite a few mathematics departments, tenure and promotion depend on publishing in the "right" journals. Certainly, there are large differences in quality of mathematical research, and all of us agree that some problems are substantially more important and/or difficult than others. This does not justify condemning whole fields of mathematics out of ignorance. Defending a negative view on a subject about which one knows hardly anything is not easily done in public. Like their racial or religious counterparts, mathematical bigots deny that the workers in the fields they regard as inferior are worthy of any kind of recognition or of having their work read. Like Galileo's inquisitor, they see no need to look in the telescope. At the beginning of my career, when you submitted a paper to a journal, it was read carefully by a referee and you got a set of critical and detailed comments about it as well as a decision on whether it would be published. I did not always agree with referees or editors, but my colleagues and I almost always got the impression that our papers had been read with care, if not sympathy. For the last decade or more, papers seem to be read at best in a cursory way, especially when the report is negative. The author's results are said to be "well-known" without even a hint of a reference, or the paper is called padded or poorly organized without any constructive criticism. Writing to the editor to ask for more detail or correct erroneous comments is usually an exercise in futility. The attitude that part of the job of an editor and referee is to help authors to turn their papers into something worthy of publication while maintaining high standards seemed fairly common in my youth; it has gone the way of the dodo bird. I was shielded from mathematical bigotry until I got to Princeton as a temporary member of the Institute for Advanced Study in 1956. My office-mate and collaborator was a Princeton Ph.D. One of his former professors asked out of curiosity who I was. When he learned that my major professor at Wisconsin was R. H. Bruck (an outstanding expert in the theory of loops and nonassociative algebras, as well as the projective geometries that motivated them), he asked contemptuously, "'What does he work o n - - m o o p s ? " Soon I learned that it was common practice at many institutions for the faculty to put down individuals and whole fields of mathematics in front of graduate students. Actually, my thesis had been written on the ring of entire functions and rings of continuous real-valued functions, which led me to work in general topology. I soon discovered that the latter is so low on the prestige totem pole that it seems unworthy of a name in elite circles; no modifying adjective to the word "topology" is used by algebraic topologists in describing their work. 8

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993

At first, these attitudes hurt, and like a victim of racial discrimination, I began to feel inferior; indeed, nobody at the elite institutions worked in my areas of interest. After a while, I learned to live with m y original sin, and, in addition to doing research in algebra and general topology, I have published papers in number theory and numerical analysis, and directed projects in applied mathematics. Rationalizing ignorance of some kinds of mathematics on the grounds that they are "inferior" seems ludicrous. In my old age, I have come to wonder if perhaps some of the clothing I fail to see may exist only in the minds of those who are so free to condemn others. Mathematicians intolerant of areas remote from their own work can be very destructive. When mathematics began to be applied extensively in industry and industrial mathematicians tried to publish articles on new applications of mathematics, they often found their work judged only on the quality of the new mathematics they had produced; neither clever mathematical modeling nor the applications themselves weighed in for much. Surely, this kind of mathematical bigotry contributed to the founding of S.I.A.M. and the paucity of papers on applied research presented at meetings of the A.M.S. or published in its journals.

Pariah Fields of Mathematics The b~tes noires of the B.A.D. mathematicians vary with time. For many years, the parts of linear algebra having to do with extensive computations with matrices were reviled, whereas those that avoided computation brought forth kudos. The elegance of the latter makes f u n c t i o n a l analysis a n d the s t r u c t u r e of finitedimensional algebras easier to understand, but hard computations are needed for numerical analysis as well for parts of the theory of differential equations. As electronic computers became increasingly accessible, the importance of numerical analysis could no longer be denied, and the mathematical bigots had to find other fields to pillory. They have little difficulty concluding that if they see no application of an area to what interests them, it should be pushed out of the "important" general journals. This is not as easily done with journals published by the A.M.S., but w h e n it is, the mechanism used is to take control of the editorial board and/or the position of managing editor while making sure that no member is a specialist in an "inferior" field. Whereas the journal is still advertised as one that publishes articles in all areas of mathematics, anyone who submits a paper in certain areas is told that no member of the editorial board has the expertise to evaluate it, or that the paper is "unduly technical" and should be submitted to a specialized journal. Since these boards are almost always self-perpetuating, once a field is deemed unfit for the journal, it stays that way. I have heard many stories about this method for

(allegedly) increasing the prestige of a general journal by stopping the publication of papers in "inferior" fields, and witnessed it at first hand twice. In the early 1970s, the new managing editor of the Duke Journal, unaware that I published papers in anything but algebra, bragged to me that he was quietly ceasing to publish papers in general topology. When I asked him if he sent such papers to a referee, he replied that if he did, the referee would be a general topologist and might recommend publication. Also, when James Dugundji died, so did general topology as far as the editors of the Pacific Journal are concerned. Two of my co-authors and I got a "your paper is unduly technical" letter in 1984, and after realizing the futility of asking that it be sent to a referee, sent it instead to the Transactions of the A.M.S., where it met the standards for publication. Many others had similar experiences. Attempts to get these editors to admit openly that the journal would not publish papers in general topology evoked evasive replies delivered with a technique that officials in Texas before the Voting Rights Act would have envied w h e n they were asked why only blacks failed literacy tests used as a qualification for voting. Academics usually have great difficulty admitting, even to themselves, that they act in their own self-interest, so the mathematical bigots have little trouble in rationalizing their selfish or dishonest acts as the maintenance of high standards. (In the late 1960s, Robert Solovay pioneered the use of the techniques developed by Paul Cohen to establish the independence of the continuum hypothesis to show that many of the unsolved problems in general topology were undecidable. General topology has never been the same since, and strong connections with model theory and set theory have been firmly established. The undecidability of the existence of an incomplete norm on the ring of continuous functions on an infinite compact space established by Dales, Esterle, and Woodin served to cement more firmly the connections between general topology and functional analysis as well as ordered algebraic systems. So, seemingly, the efforts to push general topology out of journals occurs just when this field has increased vitality and connections with other parts of mathematics.) I have no objection to editors instructing referees of papers to apply high standards; as an associate editor of the American Mathematical Monthly, I did so often, as well as acting as a referee myself. I contend that rejecting papers unread by experts while giving reasons that are evasive euphemisms is bigotry pure and simple. It is clear also that the members of the editorial boards of journals that engage in such practices are in a position of conflict of interest as long as research grants, promotions, and salary increases in so many academic institutions depend on being able to publish in "highprestige" journals. One of the destructive effects of excluding whole

fields from journals has been a large growth in the number of specialized journals. Authors who publish in such journals tend to write only for specialists in their area, and, as a result, mathematics tends to become a Tower of Babel. As we become more specialized, we tend to be reluctant to teach even advanced undergraduate courses outside of our specialty, and the intellectual incest passes to the next generation. Worse yet, publication of mathematical articles becomes difficult for all but a small elite. The prestige of a field changes with time, sometimes for good reason, but often as a result of power struggles which have an impact on granting agencies and the composition of editorial boards. This puts those not on the faculty of elite institutions in the position of playing against loaded dice. A small number of nasty referee's reports or evasive letters from editors are often enough to push "outsiders" out of research. Faculty who do no research tend not to keep up with change, and in the steady state, we can expect that most undergraduate institutions will be unable to send students to the better graduate schools. Students rarely choose a college with a view to preparing to do graduate work in mathematics, so this reduces our ability to attract talented young people into our profession. The impact of this waste is being delayed by the large influx of talented foreigners into the U.S. job market, but in the not-toodistant future, the faculty that entered the profession in the Sputnik era will retire in large numbers. At this point, my crystal ball gets very cloudy. Even if m y fears are exaggerated, the problems we face as mathematicians are formidable, and giving free reign to the B.A.D. mathematicians among us can only make things worse. It amounts to letting our young be eaten at a time w h e n the birth rate is dropping. While the size of this destructive group is small and they do not gather together to conspire, we all bear a share of the guilt w h e n we avert our eyes and let them operate with impunity out of fear that we may be regarded as defenders of mediocrity. Freeing ourselves of this kind of self-destructiveness will not be easy or pleasant. We must begin by demanding accountability from those editors and reviewers of proposals who condemn whole areas of mathematics while presenting no evidence in support of their actions. We can no longer close our eyes to the blatant conflict of interest that this presents and permit mathematicians who freeze out their competition to control key journals. We should no longer accept the selfserving claims that only the journals in which this selfappointed group of censors publish have really high standards. These problems will not go away unless we speak out and condemn the hypocrisy of B.A.D. mathematicians.

Department of Mathematics Harvey Mudd College Claremont, CA 91711 USA THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 9

Logic, Sets, and Mathematics Paul C. Gilmore

So the logicians entered the picture in their usual style, as spoilers. [15]

It was in the summer of 1967 on the terrace of a cafe on the campus of the University of California in Los Angeles that I saw my first satellite photograph of earth. The photograph appeared on the front page of the Los Angeles Times and showed the southeastern end of the Mediterranean Sea with the Gulf of Suez and part of the Red Sea clearly visible. With me on the terrace were colleagues from a conference on axiomatic set theory. I drew their attention to the remarkable physical confirmation of theory that the photograph provided: For m a n y hundreds of years, people have been crawling about the surface of Earth making measurements with surveying instruments and then making maps based on calculations from the measurements; now when we finally can get off Earth to take pictures of its surface and see its real shape, we find, lo and behold, that the pictures look just like our maps! Most of my colleagues dismissed my whimsy with a laugh, but one turned to me and said, "Gilmore, w h e n we can look at set theory in the same way as we can now see the surface of Earth, it will turn out to be ZermeloFraenkel!" Zermelo-Fraenkel [17] is one axiomatization of set theory developed early in this century in response to the discovery of contradictions in the naive set theory of Cantor and in the formal set theory and logic of Frege. My colleague's belief in the true nature of this set theory is certainly not universally held. John Gray in his introduction to [10] wrote, 10

The paradoxes of naive set theory showed that the Cantorian version was inadequate, but the various axiomatizations that soon were devised, while serving their purpose, have never been of particular interest to mathematicians. They now function mainly as t a l i s m a n s to ward off evil. The ad hoc character of the axioms of ZermeloFraenkel set theory and the equivalent class-set theory of G6del-Bernays [7] naturally leads to skepticism about their fundamental role in mathematics. But does it matter? If, as the formalists believe, mathematical

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 9 1993 Springer-Verlag New York

truths are simply logical consequences of assumed axioms, then the question "What is a correct logical argument?" becomes fundamental, as it does also if, as the logicists believe, mathematical truths are simply logical truths. By what criteria of correctness is an argument to be judged? Certainly, a minimum requirement is that an argument not permit true assumptions to have a false conclusion. Although objections will be heard from mathematicians of intuitionistic or constructivist persuasion that that minimum requirement is not sufficient, a discussion of these objections will be postponed. Of greater immediate importance is an understanding of what is meant by 'true' and 'false'. For example, no correct logical argument can conclude from the sentence 'All dogs are mammals' that 'There is a mammal that is not a dog' even though both sentences are true when 'mammal' and 'dog' are given their usual meaning. For if 'mammal" and 'dog' are given the same meaning, the assumption is true and the conclusion is false. A correct logical argument cannot depend upon facts that are not explicitly stated assumptions of the argument.

Elementary Logic and NaDSet Mathematicians, at least in principle, explicitly state their assumptions and try to use correct logical arguments to deduce theorems from them. The goal of mathematical logic has been to define what constitutes a correct logical argument in precise enough terms that a proposed argument can be mechanically checked for correctness. The goal is fundamental for mathematics, for no matter what one's view of the nature of mathematics, verification of argument is to mathematics what reproducibility of experiment is to the physical sciences. Before an argument can be mechanically checked for correctness, it must first be expressed in a symbolic language with a precise grammar. The language of NaDSet, a natural deduction-based set theory described in [5], will be used here. Consider, for example, the above discussed sentences. In symbolic form, they can be written respectively as the formulas Vx(x:D D x:M) and 3x(x:M A ~x:D). Here x is a variable, V is the universal quantifier, and D is the logical connective of material implication. In the second formula, 3 is the existential quantifier, A is the logical connective of conjunction, and ~ is negation. The formulas x:M and x:D express that whatever x denotes is a member of the sets M and D, respectively. To demonstrate that the conclusion ~x(x:M A -x:D) does not properly follow from the assumption Vx(x:D D x:M), it is sufficient, using the minimum require-

ment on correct logical arguments, to provide a counterexample; that is, an interpretation in which the assumption is true and the conclusion is false. Let a denote an object which may meaningfully have the properties D and M; that is, a:D and a:M are to be understood to be sentences that are either true or false, but not both. Consider the following tree of signed formulas, that is, formulas that have been prefixed by + or

-- :

+ Vx(x:D D x:M) - 3x(x:M A ~x:D) + (a:D D a:M) -a:D - (a:M A - a:M

+a:M ~a:D) - -a:D

The signed formula + Vx(x:D D x:M) at the root of the tree expresses that the assumption of the argument is to be taken to be true, whereas the signed formula - 3x(x:M A -x:D) immediately below it expresses that the conclusion of the argument is to be taken as false. Next appears + (a:D D a:M); it is obtained from the first by dropping the quantifier Vx and substituting a for x. This is justified by the fact that if the formula (x:D D x:M) is true for every value of x, then it must be true when x is a. The tree now branches, because (a:D D a:M) is true if and only if a:D is false or a:M is true w h e n D is interpreted as material implication. This is expressed in the tree by the signed formulas at the ends of the first horizontal line. Beneath - a:D at the left end of the line appears -(a:M A -a:D) which is obtained from -3x(x:M A -x:D) by dropping the quantifier 3x and substituting a for x. This is justified by the fact that if 3x(x:M A -x:D) is false, so also must (a:M A ~a:D) be false, no matter what a denotes. The tree branches again at the second horizontal line because if (a:M A -a:D) is false, a:M is false or -a:D is false. N o w examine the leftmost branch of the tree starting at the root and ending at the leaf -a:M. There are two signed atomic formulas in that branch, namely, - a : D and -a:M. The formulas are called "atomic" because they cannot be reduced to simpler formulas, unlike for example -a:D, which can be reduced to a:D, or (a:D D a:M), which can be reduced to a:D and a:M. The constant a is the only name of an object used in the signed formulas of the branch, so we may assume that it denotes the only existing object. N o w traverse the leftmost branch from its leaf to its root: If a:M is false, so is (a:M A -a:D), and, therefore, also 3x(x:M A -x:D) because a is the only object. If a:D is false, (a:D D a:M) is true. Again, because a is the only object, Vx(x:D D x:M) must also be true. The tree provides a counterexample to the argument that ~x(x:M A ~x:D) is a consequence of Vx(x:D D x:M). The time it has taken to construct this simple counTHIu M A T H e M A T I C A l . I N T F I . I . I G F N / C I ~ R V C I [ 15. NCI. 1.

I~:]

11

terexample may confirm in the minds of some that logicians spend too much time on trivial matters! But bear with me and remember the goal: to define what constitutes a correct logical a r g u m e n t in precise enough terms that a proposed argument can be mechanically checked for correctness. Mechanically checked means, of course, checked by a computer, and we all know how superbly computers take care of trivial matters, as long as we are careful in describing what we want them to do. The given tree of signed formulas is an example of a semantic tree that provides a counterexample to a proposed argument. The construction of the tree followed from the meaning or semantics given to the logical connectives - , D, A, and V, and the quantifiers V and 3. Semantic trees, by providing a systematic way of searching for a counterexample, can also demonstrate that no counterexample can be found. Consider a sim-

+ Vx(x:P D x:Q) + Vx(x:Q D x:R) -Vx(x:P D x:R)

-(p:P D p:R)

-V -D -D +V

+p:P -p:R + (p:P D p:Q) - p:P

+ p:Q + (p:Q D p:R)

+D +V

- p:Q

+D

+ p:R

pie mathematical example. Set inclusion is defined: P C Q for Vx(x:P D x:Q), where P and Q are terms intended, like D and M, as names of sets. Set inclusion is transitive, that is, if P C Q and Q c R are true, so is P C R; or in symbols: P C Q, Q c R ~ P C R. What follows is a semantic tree that formalizes an argument justifying this conclusion. The two assumptions P C Q and Q c R appear with + signs at the root of the tree, whereas the conclusion P C R appears with a - sign. The symbols - V , - D , etc., appearing to the right of the tree reference the rules described below used to construct the tree. In the quantifier rules, [t/v] and [p/v] are substitution operators. For example, (p:P D p:R) is [p/x](x:P D x:R). Using these rules, semantic trees are constructed as follows: 9 If the signed formula appearing above a dotted line in a rule appears in a branch of a semantic tree, then the branch may be extended by adding to the bottom of the branch the signed formula that appears below the line. 9 If the signed formula appearing above a solid line in a rule appears in a branch of a semantic tree, then the branch may be extended and split into two branches by adding the solid line to the bottom of the branch together with the two signed formulas that appear below the line. 9 A branch of a tree in which an atomic formula appears with both a + and a - sign is marked with a double dotted line === and is not extended further. It is said to be closed. The rules are called semantic rules [1] because they express the semantics or meaning of the logical connectives and quantifiers used in them as described by Tarski in [20]. It should be carefully noted, however, that unlike [1] and its variant [19], the method of semantic trees described here requires that a branch be closed only if there is an atomic formula that appears in

Semantic Rules +-

+~F

-F +D

+(F ~ G)

+A

- F +G +(F/~ G)

+V

+(F V G)

+F

-D + (F/~ G) +G

-A -V

+F +G +V

+3

12

+VvF +[Fv]F +3vF +[p/v]F

-V [t is any term] -3 [p is a new parameter]

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. I, 1993

--F +F - ( F D G)

+F -(F/~ G) -F -G - ( F V G) -F -VvF -[p/v]F -3vF

-[Fv]F

-(F D G) -G

-(F V G) -G [p is a new parameter] [t is any term]

the branch with both a + and a - sign. For the logic described so far, this makes no difference, but a profound difference results when semantic trees are used to verify arguments involving sets as they are in the logic and set theory NaDSet being described here. The distinction between a constant such as a and a parameter such as p is critical for the meaning of the quantifier rules; the former is used to denote a specified object from the domain D of the postulated counterexample, whereas the latter is used to denote an unspecified object of D that must exist if the postulated counterexample exists. For example, if VvF is false, there is necessarily some object in D which when assigned to the variable v falsifies F; if p names the object, then [p/vIF is false. Because the object may not be among those currently named in the argument, a new name p must be chosen. Similarly if 3vF is true. In the first semantic tree, M and D are understood as names of subsets of D. For example, in the counterexample that was constructed from the tree, D has a single element denoted by a, whereas both M and D denote the empty subset of D. For the second semantic tree, the parameter p denotes a member of the domain D of the postulated counterexample, whereas P, Q, and R denote subsets of D. A signed atomic formula such as + p:P is understood to assert that p is a member of P, whereas -p:P asserts that it is not. Thus, no counterexample can be discovered by extending a branch on which an atomic formula appears with both a + and a - sign; the branch is closed to further extension. If each branch of a semantic tree is closed, the tree is said to be closed. A closed semantic tree begun with signed formulas + F1. . . . . + Fk and - G provides a correct logical argument that G is a consequence of F] . . . . . Fk, because it demonstrates that no counterexample can exist. Symbolically, this is expressed by F1. . . . . Fk ~ G, or simply by ~ G if there are no assumptions. Some formulas may be correctly concluded from no assumptions, for example, the formula (P C Q / k Q c R D P C R) or even the formula VuVvVw(u C v/X v C_ w D u C w). For the latter, just treat each of P, Q, and R as a possible parameter p in an application of the - V rule. They are called set parameters because they are introduced as names of unspecified subsets of D. The lowercase parameters are called object parameters.

Sets and Abstraction Terms There are many significant mathematical arguments that cannot be expressed, much less verified, by the method of semantic trees developed so far. They all involve the apparent treatment of sets as objects that are members of the domain D of the postulated counterexample. Actually, however, they only involve the

treatment of names of sets as members of D. For a verifiable argument, involving specific sets necessarily introduces names for these sets; these names, and not the sets themselves, are then used in the argument. Abstraction is the process by which a set is formed from a property of objects. For example, given that M and D denote particular subsets of a domain D, the formula (p:M/k ~p:D) is true or false depending on the object denoted by p. The set of members of D for which the formula is true is denoted by the abstraction term {xl(x:M /~ -x:D)}. Rules ---{ } for such terms are the obvious ones: If +-p:{xl(x:M/~ -x:D)} is a signed formula on a branch of a semantic tree, +-(p:M/~ ~p:D) respectively can be added as a new signed formula to the branch. For example, the following closed semantic tree, in which P is a new set parameter, justifies asserting ~ {wla:w}:{ylVx(x:y V ~x:y)}:

-

-

{wla:w}:O/IVx(x:yV -x:y)} Vx(x:{wla:w}V -x:{wla:w})

- (P:{wla:w} V -P:{wla:w}) p:{wla:w} - ~p:{wla:w} + P:{wla:w} -a:P +a:P -

Note that the single branch of the tree did not close when P{wla:w} appeared on it with both a + and a sign because the formula is not atomic; however, a:P is atomic. Although the rules +{ } look dangerously like the naive comprehension axioms that got set theory into trouble in the past, they are subtly different; most obvious is the fact that they are rules not axioms. This has the effect of disarming such a paradox as Russell's. Consider the arguments he used in introducing his paradox [16]. They involved three sets named here as the following three abstraction terms: EMP for {xl3y(x:y/X -x:y)}, UNV for {xlVy(x:y D x:y)}, RUS for {xI-x:x}. The first is the empty set; no member of D is in EMP. The second is the universal set; every member of D is in UNV. The third is Russell's set; the members of RUS are those sets that are not members of themselves. Russell argued that EMP is a member of RUS because no set is a member of EMP, and that UNV is not because every set is a member of UNV. He then argued that RUS must be and must not be a member of itself. The following closed semantic tree formalizes the first of his three arguments: THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

13

- EMP:RUS

{xl3y(x:y A -~{xl3y(x:y/% --x:y)}:{xl3y(x:y /% ~x:y)} + {xl3y(x:y/% ~x:y)}:{xl3y(x:y/% -x:y)} + 3y({xl3y(x:y/% --x:y)}:y/% ~{xl3y(x:y/% -x:y)}:y) + ({xl3y(x:y/% ~x:y)}:P/% -{xl3y(x:y/% ~x:y)}:P) + {xl3y(x:y/% -x:y)}:P + ~{xl3y(x:y/% -x:y)}:P - {xl3y(x:y/% ~x:y)}:P -

This tree closes because the atomic formula {xl3y(x:y/% -x:y)}:P is required to be b o t h true and false in any counterexample in w h i c h EMP:RUS is false. A closed tree for ~ U N V : R U S can be similarly c o n s t r u c t e d . Thus, the first t w o of Russell's a r g u m e n t s are correct. Consider n o w the third: - (RUS:RUS/% - R U S : R U S ) - RUS:RUS - {xl-x:x} :{xl

x: x}

+ {xl-x:x}:{xl-x:x} + RUS:RUS

- -RUS:RUS + RUS:RUS

+{xl-x:x}:{xl-x:x} + -{xl-x:x}:{xl-x:x} - { x l - x:x} :{xl-x:x} - RUS:RUS

The s e m a n t i c tree d o e s n o t close! A l t h o u g h b o t h - RUS:RUS a n d + RUS:RUS a p p e a r o n each branch of the tree, the tree does not close because RUS:RUS is not an atomic formula. Thus, Russell's a r g u m e n t concluding RUS:RUS a n d - R U S : R U S w i t h o u t assumptions is not correct. The error in Russell's a r g u m e n t is his a s s u m p t i o n that a formula is necessarily true or false. With Tarski's semantics available to our hindsight, we can see that that a s s u m p t i o n c a n n o t be justified. W h a t have b e e n called truth gaps [13] are inevitable w h e n abstraction terms are a d m i t t e d as objects. The formula RUS:RUS can be neither true n o r false. The a r g u m e n t s involving the sets EMP, UNV, and RUS m a y seem r a t h e r r e m o t e from real mathematics, but they are similar to f u n d a m e n t a l algebraic and category theory a r g u m e n t s , as will be d e m o n s t r a t e d later. But first a closer look is n e e d e d at the m e a n i n g of atomic formulas w h e n abstraction terms are admitted as objects.

On Use, Mention, and Atomic Formulas

A set constant such as M or D is u s e d as a n a m e of a set a n d may, t h e r e f o r e , be an object in an a r g u m e n t . Therefore, a formula M:M is meaningful: It is true if M is a m e m b e r of the set M, and is false otherwise. Note carefully, h o w e v e r , that the first occurrence of M in the 14

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

formula M:M is being mentioned because it is a n a m e for the letter M, whereas the s e c o n d is being used as a n a m e of a set. This distinction b e t w e e n use a n d m e n tion is necessary for an u n d e r s t a n d i n g of some sentences of natural languages. For example, in the sentence 'In English, or and a n d are conjunctions' the first occurrence of 'and' is being u s e d as a conjunction, w h e r e a s the second is being m e n t i o n e d because it is a n a m e for itself. A n object parameter, such as p, d e n o t e s a m e m b e r of the d o m a i n D of an a r g u m e n t , w h e r e a s a set p a r a m e t e r such as P d e n o t e s a subset of D. This distinction m u s t be carefully maintained if confusions of use a n d m e n tion specifically w a r n e d against b y C h u r c h and Tarski are to be avoided [2,19]. The definition of atomic formula reflects this distinction: A formula t:T is atomic if t is a t e r m in which no variable occurs free a n d in w h i c h n o set parameter occurs, and T is a set constant or set parameter. An object p a r a m e t e r m a y occur in t because it denotes a m e m b e r of D; replacing it in t with a m e m b e r of D results in a m e m b e r of D. A set p a r a m eter m a y not occur in t because it d e n o t e s a subset of D. H o w e v e r , p r o f o u n d c o n s e q u e n c e s follow f r o m this distinction, as will be seen later w h e n we examine Cantor's diagonal argument.

Generalized Abstraction Terms In preparation for a s t u d y of a r g u m e n t s in real mathematical settings, it is n e c e s s a r y to consider a n exp a n d e d form of abstraction terms. Relations are sets of o r d e r e d tuples, not just single objects. Abstraction t e r m s t h a t d e f i n e sets of s u c h t u p l e s are n e e d e d t h r o u g h o u t mathematics. T h e y can be easily a d d e d to the logic. Let (r,s) stand for the o r d e r e d pair of terms r and s. T h e n the abstraction t e r m {(x,y)lVu(u:x D u:y)} is the inclusion relation b e t w e e n sets. In the construction of semantic trees, the signed formulas ---Vu(u:r D u:s)} m a y be a d d e d to a branch of a semantic tree o n w h i c h respectively +--(r,s):{(x,y)lVu(u:x D u:y)} appears. Thus, the following generalized abstraction rules e x t e n d the former. +{ }

+ [r/vlt:{tlF} + [_r/v]F

- { }

- [r/v]t:{tlF} - [r/v]F

For the example at h a n d , (x,y) is the term t a n d the substitution operator [r/v] is the simultaneous substitution operator [r,s/x,y] so that [r/v]t is (r,s). The o n l y restriction o n the term t u s e d in the formation of a generalized abstraction t e r m {t[F} is that no p a r a m e t e r , and at least one free variable, occurs in t; a single variable is an example of such a term. The variables occurring free in t, like the variables v u s e d in the quantifiers

Vv and 3v, bind free occurrences of themselves within {t[F}. Thus, for example, only the variable w has a free occurrence in the term {Iu:M ~/w:M}. These two rules complete the description of the logic NaDSet.

W h a t A b o u t the Goal?

have been developed that act as assistants to their human masters; they can verify arguments proposed by their masters and even fill in modest gaps in arguments; for example, they can be used to assist in verifying VLSI designs [8,9]. Other applications of logic in computer science are described or referenced in [21]. Are there correct logical arguments that cannot be represented by closed semantic trees as they have been described? I hope so, for in [6] I give a proof of the consistency of NaDSet and ! like to think that the proof is correct. But I know from a theorem of G6del in his 1931 paper reprinted in [11] that the proof cannot be correct if it is formalized within NaDSet! G6del's proof of his theorem uses a subtle application of Cantor's diagonal argument inspired by the liar paradox. A full examination of the application of GOdel's theorem to NaDSet must still be undertaken. NaDSet is one of the latest in a long line of logics and set theories created to formalize mathematical arguments. A full discussion of its antecedents and living relatives has been given elsewhere [5]. Its dependence upon a careful distinction between use and mention for an avoidance of the paradoxes is one of its distinguishing features. Earlier, Sellars suggested the same source of the paradoxes [18].

The minimum requirement on a correct logical argument has been used as the basis for defining semantic trees. The semantic rules used in the construction of the trees express the meanings for the logical connectives and quantifiers, and for abstraction. Mathematicians of intuitionistic or corfstructivist persuasion can object that the meanings are not theirs and that, therefore, their correct logical arguments are not necessarily expressed by closed semantic trees. But NaDSet can be easily modified to accommodate their wishes; an intuitionistic version of the logic can be provided, for example, in its sequent calculus formulation [5]. So the fact that intuitionistic arguments can differ from those expressed by closed semantic trees is not of importance in considering whether the description of NaDSet has achieved the goal set for it. The goal has been achieved for arguments expressed as d o s e d semantic trees. Given any tree of signed for- A r i t h m e t i c a n d R e c u r s i v e D e f i n i t i o n s mulas, it is possible to determine in a purely mechanical fashion whether or not it is a closed semantic tree; One of the most striking differences between logicism the set of closed semantic trees is decidable. For given and formalism can be seen in the development of arithany pair of signed formulas and any single-conclusion metic. A formalist treatment of the subject is develsemantic rule, it is decidable whether the first signed oped from axioms, say the Peano axioms [12]. The deformula is the premiss of an application of the rule velopment within a logic such as NaDSet proceeds enwith the second signed formula as conclusion. Simi- tirely from definitions of abstraction terms; Peano's larly, given any triple of formulas and any double- axioms can be derived from the definitions. An identity relation in NaDSet can be defined: conclusion semantic rule, it is decidable whether the first signed formula is the premiss of an application of the rule with the second and third formulas as conclu=for {]Vz(u:z D v:z)}. sion. Thus of each signed formula of a given tree it can be determined whether it is a conclusion of an appli- Although this definition is not symmetric with respect cation of a semantic rule with premiss occurring above to u and v, it is not difficult to show that the relation is it in the tree. If it is not, then it must be among the idempotent, symmetric, and transitive. It is an intensigned formulas at the root of the tree originating from sional identity: Two terms r and s are identical if they the assumptions and conclusion of the argument to be are members of exactly the same sets. The familiar infix verified. notation r = s will be used instead of (r,s): =. Briefly, the rules for constructing semantic trees An alternative definition of the empty set EMP can have been described precisely enough that a computer be given in terms of = and the first non-negative incan determine whether or not a given finite tree is a teger 0 is taken as an abbreviation for it: closed semantic tree. That is not to say, of course, that a computer can determine whether a given formula G 0 for { u l - u = u}. is a correct logical conclusion of given formulas F~, .... Fk, k/> 0. True creativity is needed for that task. The fact that correct logical arguments can be veri- The successor t' of a term t is taken to be the set with fied by computer has turned mathematical logic, for- only t as member: merly a branch of pure mathematics, into a very active branch of applied mathematics. Computer systems t' f o r {x)x = t}. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

15

(a)

(b)

-Vy((O:y/~ Vx(x:y D x':y)) D Vx(x:N D x:y)) - ( ( O : P / X Vx(x:P D x':P)) D Vx(x:N D x:P)) + ( O : P / ~ Vx(x:P D x':P)) -Vx(x:N D x:P)

[P new for (a)]

+ O:P

(c) (d)

+ Vx(x:P D x':P) -(P:N D p:P) + p:N - p:P +Vy((O:y/~ Vx(x:y D x':y)) D p:y) +((O:P/~ Vx(x:P D x':P)) D p:P)

[p new for (b)]

[(d) def. of N]

+p:P

- ( O : P / ~ Vx(x:P D x':P)

- O:P

- Vx(x:P D x' :P) -(q:P D q' :P) + q:P -q':P +(q:P D q':P) -q:P

Finally, the set N of non-negative integers can then be defined: N for {ulVy((O:y/N Vx(x:y D x':y)) D u:y)}. Using only these definitions the following three formulas can be concluded without assumptions:

0:N, Vx(x:N D x':N), and Vy((0:y/~ Vx(x:y D x':y)) D Vx(x:N D x:y)). The last of these is mathematical induction: If 0 is a member of a set y and the set is closed under successor, then N is a subset of y. At top, the closed semantic tree justifies this conclusion without assumptions: The definition of N is a typical example of a recursive definition of a set: It is the smallest set that has 0 as a member and is closed under successor. Similar deftnitions can be given for the addition and multiplication operations, and all of arithmetic can be developed from these definitions. Also such recursive definitions can be used in a similar manner to define the meaning of a computer program [21].

Algebra and Category Theory The requirement that all assumptions in an argument be made explicit can sometimes lead to a long list because in every complex subject, mathematical or not, a "jargon" must be developed to permit initiates to communicate quickly and accurately. Consider a very sim16 THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993

(q new]

[from (c)]

+q':P

ple algebraic example. An algebraist can define a B-algebra in just a few words: A B-algebra is a set which is closed under a single-valued, binary, commutative, and associative operation. What is being assumed of B-algebras? First, that the operation is single-valued means that an identity relation must be defined on the set. If the set is denoted by B and the identity relation by -~, then the following axioms are assumed:

1. Identity Axioms [Vu:B](u,u):~ , [Vu,v:B]((u,v):~- D (v,u):~), [u /~ (v,w):-~ D (u,w):~). Here the postfix notation of NaDSet is being used to emphasize that ~ denotes a set that is a binary relation. The bounded quantifiers appearing in these axioms have their expected meaning; for example, [Vu:B]F abbreviates Vu(u:B D F). It is important to recognize that the identity relation =, that had to be defined before the development of arithmetic could proceed, cannot replace ---- in these axioms and the others to come; this will be made evident when all the axioms have been assembled. That B is closed under a single-valued binary operation ~ is expressed by the following axioms:

2. Binary Operation Axioms [Vu,v:B][3w:B](u,v,w}:(~, [Vu,v,wl,w2:B]((u,v,wl):@ A (u,v,w2):~ D (wl,w2):----),

[Vul,u2,v,w:B]((ul,v,w):~ /~ (ul,u2):~ D (u2,v,w):~), [Vu,vl,v2,w:B]({u,vl,w}:~/~ {vl,v2}: -~ D (u,v2,w):(~), [Vu,v,wl,W2:B]((u,v,wl):(~ /N ( w l , w 2 ) : ~ D

(u,v, w2):~).

Here (u,v,w) is notation for the ordered triple, so that (u,v,w):e expresses that w is the result of applying ~ to u and v. The existential quantifier appearing in the first axiom is again an abbreviation: [3w:B]F abbreviates 3w(w:B A F). The last four axioms are needed to express properly that G is a binary operation on B. So eight axioms are needed in total to express that ~ is a single-valued binary operation on B; there is no doubt that the jargon of the algebraist is useful here! But now only two axioms are needed to express that ~ is commutative and associative:

3. Commutative and Associative Axioms [Vu,v,w:Bl((u,v,w):r ~ (v,u,w):r [u wl,w2,zl,z2:B]((u,v,wl):~ A (wl,w,zl):G A (u,w2,zg:@ A (v,w,w2):O D (zl,z2):-~). Certainly, the last axiom would be easier to understand if it was expressed in the usual infix functional notation: ((u 9 v) ~ w) ---- (u 9 (v 9 w)), but that notation depends on assumptions made explicit in the axioms. As an object, a B-algebra is a triple (B,----,fg) of abstraction terms B, 2, and ~ satisfying axioms (1), (2), and (3). The set Balg of all B-algebras is, therefore, named by the abstraction term {(B,~-,O)laxioms}; here axioms stands for the conjunction of (1), (2), and (3), and B, ----, and ~ are variables. A theorem of B-algebra is a formula F for which ~ V B V = V 9 (axioms D F) can be justified by a closed semantic tree. Consider now the relation ISO of isomorphism between B-algebras and the Cartesian product PR between B-algebras. ISO and PR can be defined as abstraction terms and shown to satisfy the axioms (1), (2), and (3) when B is Balg, ~ is ISO, and 9 is PR. Only some care is needed in interpreting the bounded quanriflers of the axioms when the variable B is replaced with the abstraction term {(B,-~,e)laxioms}. That is, a closed semantic tree can be constructed to prove the theorem: (Balg, ISO, PR):Balg [5]. A study of the cited theorem within NaDSet was suggested by an observation of Feferman [4]: He gave it as an example of commonly occurring arguments of algebra that cannot be formalized within the traditional set theories. There are no obstacles in NaDSet to a statement and proof of the theorem, nor for a corresponding result for category theory [21]. Although the closed tree needed to prove the theorem is very much larger than the tree that was presented earlier to justify Russell's first argument, it is nevertheless constructed in exactly the same fashion using the same semantic rules. Lawvere has proposed category theory as a foundation for mathematics [14]. But he ignored the fact that categorical arguments must be supported by a logic; for example, the formalization in [21] of category theory within NaDSet requires making explicit 20 assumptions in the form of axioms. Category theory, no more than a traditional set theory, provides a substitute for

a logic. This does not detract in any way from the value of the applications of category theory.

Sequences and Cantor's Diagonal Argument As noted earlier, the distinction maintained between object and set parameters has profound consequences; one of these is the failure of the diagonal argument used by Cantor to prove that there are more real numbers than there are natural. A real number in the closed interval [0,1] can be represented as a sequence b1, b2. . . . . bj. . . . . where each bj is 0 or 1. An enumeration F of sequences of 0's and l's is defined by a double enumeration ibj of 0's and l's, where i,j = 1,2 . . . . F[i] is the sequence ibj, w h e r e j = 1,2 . . . . . Define D[F] to be the sequence dj, where dj = 0 if Jbj = 1, and dj = 1 if Jbj = 0. Cantor's diagonal argument uses the "diagonal" sequence D[F] to prove:

CANTOR'S LEMMA: For each enumeration F of sequences of O's and l's, there is a sequence not enumerated by F. To prove the lemma, D[F] is first shown to be a sequence, and then shown to be not enumerated by F; the latter follows because for each j, cj ~ Jbj. Can this argument be justified by a d o s e d semantic tree? Using the definitions of the last section, 1 can be defined to be 0', N1 to be {u'lu:N}, and Bit to be {ulu = 0 V u = 1}. The set Sq of sequences of O's and l's can then be defined: Sq for {zl[Vn:N1][3u:Bit]((n,u):z A [u D v = u))}. Extensional identity = sq between sequences is defined: = sq for {(x,y)l[Vu:Nll[Vv:Bit]((u,v):x ~ (u,v):y)}, where -= expresses material equivalence, or "if and only if". A term Mp that is a single-valued map of N1 into Sq satisfies M[Mp], which is defined:

M[Mp] for [Vn:N1][3x:Sq]((n,x):Mp A [Vy:Sql((n,y):Mp D y = s q

X)).

Thus, the set Map of single-valued maps of N1 into Sq is defined: Map for {zIM[z]}. Cantor's diagonal argument, if correct, should therefore justify:

~[Vz:Map][3x:Sq][Vn:N1] ~ (n,x):z. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

(1) 17

The sequence D[Mp] used in Cantor's diagonal argument is defined: D[Mp] for {(n,b)l[Vx:Sq]((n,x):M p D [Vv:Bit]((n,v):x D --v = b))}. It is this term that should instantiate the existential quantifier [3x:Sq] in (1) when Mp is a member of Map. In the following semantic tree, constructed in an attempt to justify (1), D[P] is substituted for x in the fourth signed formula:

- [Vz:Map][3x:Sq][Vn:N1] ~ (n,x):z -(M[P] D [3x:Sq][Vn:N1] ~ (n,x):P)

[P new]

+M[P]

- [3x:Sq][Vn:N1] ~ (n,x):P -(D[PI:Sq/N [Vn:N1] ~ (n,D[P]):P) - D[PI:Sq :

- [Vn:N1] - (n,D[P]):P - (p:N1 D ~(p,D[P]):P)

[p new]

+ p:N1 - -(p,D[P]):P + (p,D[PI):P

(2)

cannot be justified because (p,D[P]):P is not a correct logical consequence of (p,D[P]):P. But it is not difficult to see (2) must be justified if the right branch of the tree is to close. Similarly, by extending the first branch of the tree, it can be seen that for it to close

(p,Q):P ~ (p,Q):P

(3)

must be justified, where Q is another set parameter, but again this cannot be done because (p,Q):P is not atomic. Therefore, the semantic tree needed to justify (1) cannot be closed; the diagonal argument used to justify (1) is not a correct logical argument! The failure of Cantor's diagonal argument in this example should not be a surprise, for it, like Russell's third argument, can lead to a contradiction. Cantor was aware of this and introduced the vague concept of consistent and inconsistent multiplicities to distinguish between sets that can consistently exist and those that cannot [3]. The distinction found a precise formulation 18

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

Mp:Map ~ [3x:Sq][Vn:N1] ~ (n,x):Mp when Mp is an abstraction term for which (2) and (3) can be justified with P replaced by Mp. For example, let a single-valued map FB of N1 into Sq be defined:

Note that the formula (p,D[P]):P, appearing in the right branch with a + and a - sign, is not an atomic formula even though it cannot be further reduced, for P must be a set parameter because it occurs to the right of :, but it also occurs in the term (p,D[P]) appearing on the left. Therefore, a branch on which both +(p,D[P]):P and -(p,D[P]):P appears is not closed; that is,

(p,D[P]):P ~ (p,D[P]):P

in the type theory of Whitehead and Russell and in another form in the traditional set theories. These theories concentrated on the question "what sets can consistently exist" rather than on the more fundamental question "what is a correct logical argument", which is the primary concern of NaDSet. The discussion of the Russell paradox in the section entitled "Sets and Abstraction Terms" illustrates the fundamental difference between these two points of view; the Russell set does not exist as an object in the traditional set theories, but in NaDSet, correct arguments involving the set can be formalized. Although the form of Cantor's diagonal argument needed to prove Cantor's lemma is not correct, many less general forms of Cantor's diagonal argument are. All of the "obvious" applications, for example, depend upon the following result: A closed semantic tree can be found to justify

FB for {(i,x)]i:N1/~ x = sq B[i]}, where the ith sequence B[i] is defined:

B[i] for {(m,b)lm:N1 /X(m ~ i D b = 1)/X (m > i D b = 0)}. The first sequence enumerated by FB is 1000 . . . . the second 1100 . . . . the third 1110 . . . . and so on. The sequence D[FB] consists of all O's. The reader is urged to verify (2) and (3) when P is replaced by FB. But of greater importance than such obvious applications is the fact that all the computational applications of Cantor's argument can be justified; for example, the argument used to prove that the sequences computed by Turing machines cannot be enumerated by a Turing machine can be justified. Even the applications of the argument in the traditional set theories can be justified! The formalization of G6del-Bernays set theory in NaDSet is accomplished in the same manner as the formalization of the B-algebras described earlier. The set GBST of structures that are G6del-Bernays set theories is named by the abstraction term {{Cls, M , E ) laxioms}, where Cls (class), M (set), and E (membership) are variables appearing in the conjunction axioms of all the axioms of the theory [5]. A theorem of the theory is a formula F for which

~VClsVMVE(axioms D F)

References can be justified by a closed semantic tree. One of the theorems that can be justified is Cantor's 1. E. W. Beth, Semantic entailment and formal derivability, lemma! Although the lemma cannot be derived in Mededelingen van de Koninklijke Nederlandse Akademie der Wetenschappen, Afdeling Letterkunde, Nieuwe Reeks, 18, no. NaDSet, it can be derived in G6del-Bernays set theory 13 (1955), 309-342. when the theory is formalized within NaDSet. Skolem 2. Alonzo Church, Introduction to Mathematical Logic, Princeforetold this remarkable situation in his 1922 paper reton, NJ: Princeton University Press (1956), Footnote 136, printed in [11] where he described and explained what p. 62. 3. Joseph Dauben, Georg Cantor, His Mathematics and Philoshas come to be called Skolem's paradox. He had ophy of the Infinite, Cambridge, MA: Harvard University shown that any theory, if it is consistent, must have a Press. denumerable domain. Thus, despite their purpose in 4. Solomon Feferman, Towards useful type-free theories, I, providing a formalization of transfinite number theory, ]. Symbol. Logic (March, 1984), 75--111. the traditional set theories must have denumerable 5. Paul C. Gilmore, How many real numbers are there?, models if they are consistent. The explanation for this University of British Columbia Computer Science Department Technical Report 89-7, revised August, 1991. paradoxical result, Skolem remarked, lies in the nature 6. Paul C. Gilmore, The consistency and completeness of of definitions within formal theories. We have a conan extended NaDSet, University of British Columbia crete illustration of his remarks: The failure of Cantor's Computer Science Department Technical Report 91-17, lemma within NaDSet is a consequence of the definiAugust, 1991. tions of Sq and of MIMp], which are the correct defi7. Kurt G6del, The Consistency of the Continuum Hypothesis, Annals of Mathematics Studies Number 3, Princeton, NJ: nitions for this logic. The proof of the lemma within Princeton University Press (1940). G6del-Bernays set theory, on the other hand, depends 8. Mike Gordon, Why higher-order logic is a good formalon different definitions and, of course, on the assumpism for specifying and verifying hardware, in Formal Astions expressed in the axioms of the theory. If one is pects of VLSI Design (G. Milne and P. A. Subrahmanyam, willing to accept the axioms of the set theory as "true" eds.), Amsterdam: North-Holland (1986). 9. Mike Gordon, A proof generating system for higherin some sense, then Cantor's lemma as interpreted in order logic, in VLSI specification, Verification and Synthesis the set theory is true in the same sense. But it is not (G. Birtwistle and P. Subrahmanyam, eds.), San Diego, true in the same sense that mathematical induction is CA: Academic Publishers (1988). true, that is, purely as a consequence of the definition 10. J. W. Gray (ed.), Mathematical Applications of Category Theof N and the meanings given to the logical connectives ory, Contemporary Mathematics, vol. 30, Providence, RI: American Mathematical Society (1984). --, A, N/, and D, the quantifiers V and 3, and to abstraction { }. Although in no sense have we obtained a 11. Jean van Heijenoort (ed.), From Frege to G6del, A Source Book in Mathematical Logic, 1879-1931, Cambridge, MA: satellite picture of set theory, what we have seen does Harvard University Press (1967). not support the belief of my colleague on the terrace in 12. Stephen Cole Kleene, Introduction to Metamathematics, the absolute character of the Zermelo-Fraenkel or Amsterdam: North-Holland (1952). 13. Saul Kripke, Outline of a theory of truth, J. Philosophy, 6 G6del-Bernays set theories. (1975), 690-716. Will we ever have a satellite picture of mathematics 14. William F. Lawvere, The Category of Categories as a Founin general and set theory in particular to tell us their dation for Mathematics, Proceedings of a Conference on Cattrue nature? No, because the living part of mathemategorical Algebras, Berlin: Springer-Verlag (1966), pp. 1-21. ics resides within the minds of mathematicians. The 15. Yiannis Moshovakis, Descriptive Set Theory, Amsterdam: North-Holland (1980). only "visible" part of mathematics are the theorems 16. Bertrand Russell, The Principles of Mathematics, Camand their proofs that mathematicians exchange with bridge: Cambridge University Press (1903), Vol 1. one another. The proofs, we have stressed, must be 17. Joseph R. Schoenfield, Mathematical Logic, Reading, MA: verifiable and, therefore, presentable within a logic Addison-Wesley (1967). such as NaDSet. The character of the remainder of 18. Wilfred Sellars, Abstract entities, Rev. Metaphys., 16, 625671; Classes as abstract entities and the Russell paradox, mathematics is beyond specification. Individuals are Rev. Metaphys., 17, 67-90. free to enjoy their own unbridled intuition, but if their 19. R. Smullyan, First Order Logic, Berlin: Springer-Veflag insights are to enter the body of mathematics, they (1968). must become subject to the discipline of logic. For ini- 20. Alfred Tarski, Der Wahrheitsbegriff in den formalisierten tiates of an area of specialization, that discipline may Sprachen, Studia Philosophica, 1 (1936), 261-405. English translation appears in Logic, Semantics, Metamathematics, be loose, although it becomes stricter when initiates of Papers from 1923 to 1938, Oxford: Oxford University Press different areas of specialization communicate. I was (1956), 152-278. reminded most vividly of this while teaching an eve- 21. George K. Tsiknis, Applications of a natural deduction ning course in mathematical logic to computer science based set theory, University of British Columbia Departstudents at Columbia University in the early 1970s. ment of Computer Science PhD thesis, 1991. During a break in a 3-hour class, a student asked me Department of Computer Science about the meaning of a definition I had just given. His University of British Columbia response to my explanation was, "That's the trouble Vancouver, B.C. V6T 1W5 Canada with you mathematicians, you are so imprecise!" THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. I, 1993

19

At the Dawn of the Theory of Codes Alexander Barg

Is there anything of which one can say "Look, this is new'? No, it has already existed, long before our time.

The theory of error-correcting codes was born in 1945 when C. Shannon wrote his landmark paper [1] on the mathematical t h e o r y of communication. This, of course, does not mean that there was no notion of the coding of messages before. Although this notion did not take the shape of a mathematical science, it kept producing, from time to time, instructive examples that may be still interesting to the mathematical community because they either present a surprising provisional insight or are of exceptional beauty. Below I intend to discuss some of these episodes. My aim here is not to contest the generally acknowledged priorities, nor do I claim that the discovery of these curiosities is my achievement. Rather I want to bring together a series of mathematical stories that form a part of the early history (or the prehistory) of coding theory. The purposes of the transformation of messages before transmission may be various: to compress the text in order not to send redundant information, or to conceal the sense of the text from an unauthorized user, or to add a few check symbols to correct possible channel errors after the transmission. The theory of errorcorrecting codes deals with the last problem. Let F be a finite set (an alphabet) of size IF[ = q. A (q-ary block) code A of length n is a subset of F". For q a prime power and F = 0:q a finite field, a linear code is a linear subspace of the vector space F n. Codes are designed for the transmission of messages over noisy channels. A channel is defined as a stochastic mapping T : F---* F with the matrix of transition probabilities (p(vlu)), u, v ~ F, where p(v]u) = Pr{v is receivediu is transmitted} (we do not use the most general definition here). Note that we assume that the information transmission 20

channel is memoryless, i.e., the noise affects the letters of a transmitted word statistically independently. Suppose a codeword (a message) a E A is to be transmitted over T letter by letter. Denote by x E F" the received word. To reconstruct a transmitted word from a received one, let us introduce the mapping D : F" -* A called the decoder. The goal of the decoder is to minimize the probability of decoding error, i.e., of an event D(x) # a. It can be shown that if the messages are equiprobable, the error probability is minimized (over all possible decoding rules) by the so-called maximumlikelihood decoder DML defined by the equality Pr{X[DML(X)} = m a x Pr{xIa}

for all x ~ F n.

(1)

a(~A

Suppose F" is endowed with a metric d that is matched to the channel in the sense that Pr{xiy} I> Pr{ziy} im-

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1 9 1993 Springer-Veflag New York

plies d(x,y) ~ d(z,y). Then a decoding rule equivalent to Equation (1) is the so-called minimum-distance decoder Dmd defined by the equality d(x, Dmd(X)) = min d(x,a)

for all x E F n.

(2)

a~A

Consider for example the channel with p(vlv ) = 1 and p(vlu) = e/(q - 1) for v ~ u; all errors being equiprobable, this is called the q-ary symmetric channel (QSC). It is easy to check that for q( < q - 1 the Hamming metric d(a,b) = #{j : aj ~ bj} is matched to this channel. For this reason, the QSC is the most popular channel model among coding theorists. For further details, we refer to the two classical treatises in modern information theory: [2], chap. 5, and [3], chap. 1. As a rule, the algorithmic implementation of DML as well as of Dmd requires the inspection of a large subset of code words and is, therefore, computationally intractable. For example, the general problem of minimum-distance decoding is known to be NP-hard. Because of this, one often studies the implementation of a less powerful d e c o d i n g mapping, namely, the bounded-distance decoding. By

THEOREM 1. M ~ q,-a+l.

(3)

Proof. Write all M code words in the rows of an M x n matrix. Delete any d - 1 columns. The rows of length n - d + 1 of the remaining submatrix are still distinct; on the other hand, there are at most qn-a+l different words of this length. This theorem was proved in [4] and is known as the Singleton bound. Singleton proved his theorem only for codes with integer k (for example, for linear codes). Surprisingly, we find the general bound (3) already in [5] that dates back to 1932. Though the authors do not provide a proof, the hints that are given lead us to think that they had in mind exactly the cited argument. In [5], the problem of constructing a maximal code was studied for a particular reason that we consider in the next section.

Commercial Codes

Historically, the first codes were intended to encipher plaintext of a dispatch in order to hide its sense from a third party. The story of these codes is presented in a more than thousand page volume [6]. However, Chapd(A) = rain d(a',a"), ter 22 of it (entitled "Sideshows") is devoted to nona',a"EA a' ~a" secret code systems primarily of commercial use. These codes became common already by 1825, after we denote the minimum distance within a code A Claude Chappe in 1794 constructed a semaphore sys(hereafter, code distance). Let 8 = 2t + I and let S(a,t) = {x E FnId(a,x) ~ t}. The bounded-distance decoding D a is a tem linking the main cities of France with hilltop towpartial mapping Da : U,eA S(a,t) --* A defined only on ers, signals being repeated from tower to tower. An vectors that are suitably close to the code. For this immense impetus to the promotion of commercial mapping to be well-defined, we need that the spheres codes was given in 1866 by the laying of the Atlantic S(a,t) be disjoint, or in other words that 8 ~ d(A). Usu- cable. The problem of inevitable transmission errors ally, one says that the decoding Da corrects up to t was understood by the code compilers even before 1877, when the United States Supreme Court considerrors. ered the case of the Philadelphia wool dealer Frank J. Denote the triple of code parameters by [n,M,d] = Primrose w h o sued a telegraph company for $20,000 [length, size, Hamming distance]. If F is a finite field he lost due to such an error. The codes for business and a code A is linear, then k = logq M is its dimension. transmission were constructed so as to rule out two In this case, one may think of a code as a linear bijecwords that differ by less than two letters. As we would rive mapping fA : Fk ~ A C F" from the set of k-letter say, these codes had the minimum distance 2. This is messages onto the set of n-letter code words. For this obviously insufficient to correct even a single error, reason, k is sometimes called the number of information though if a received word does not belong to the code, symbols, whereas the remaining n - k symbols are rethe receiver concludes that the transmission went abdundant and provide the error correction. Usually they normally. A code with distance 2 detects all single erare called check symbols. In the linear case, the norm llxll rors (and probably some double, triple . . . . ones). that corresponds to the Hamming distance is called the Originally, commercial codes consisted of codeHamming weight and denoted by wt(-). So wt(x) = words of different length, and the restriction meant #{j: xj 0}. that every subset of code words of equal length had the The main problems of coding theory are related to minimum distance 2. However, in the first quarter of the construction of codes with large size and distance. our century practically all m o d e m cable and telegraph Evidently, these two objectives come into conflict. A codes were based on the five-letter codeword because natural question is: H o w large can the distance of a five-letter groupings met all the various telegraph comcode of length n with M words be? or, h o w many panies' criteria of what would be counted as a word. words can there be in a code of length n and with distance d? The answer is given by the following state- Later, in 1923, A. C. Meisenbach published the Acme Commodity and Phrase Code that together with single ment. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

21

" H a m m i n g " errors was capable of detecting single transpositions, i.e., errors of the form abcda ---->acbda. This means that

x). For a, b E Z/(s), a # O, let us define a permutation of the elements of D s by ~-(e,x) = (e,e(a - x) + b).

a word x obtained from a codeword a after a substitution of one letter for another or after a transposition of two adjacent letters does not belong to a code.

(,)

The idea of a d d i n g transpositions to H a m m i n g errors was quite appropriate because together these two types of errors account for more than 0.9 of all operator errors. T h o u g h the function d*(a,b) = min{d(a,b), I(a,b)}, where I(a,b) is the m i n i m u m n u m b e r of transpositions of adjacent symbols that turns a into b, is not a metric, it is possible to consider the following problem [7]: What is the m a x i m u m size of a code that satisfies the imposed restrictions? The Acme code A over F = {a, b, c. . . . } with q = 26, of length 5, a n d with IA[ = 100,411 was in this sense a poor suggestion. Later, this problem was examined in [5]. Starting from Theorem 1, the authors constructed a m a x i m u m code of 264 = 456,976 words with H a m m i n g distance 2. After a careful h a n d analysis of the constructed code, they ruled out 16,925 further words to arrive at a code of 440,051 five-tuples that could detect one-place errors and single transpositions. At present, general m e t h o d s of constructing codes that detect single substitutions and single transpositions are k n o w n [8, 9]. For arbitrary q I> 3 a n d 2 ~< n ~< q, these m e t h o d s yield codes of length n with n - 1 information symbols and a single check symbol. In view of (3), we m a y observe that the transposition detection requirement entails no additional redundancy. Let W = {(xI . . . . . xn-1)} be the dictionary of all qn-1 information words. To each word we m u s t a d d a check symbol xn so that (*) holds [to construct a (*)-code]. The first two observations are obvious. OBSERVATION 1. Let q = pS, where s >I 1 for prime p > 2 and s >i 2 for p = 2. Let a~. . . . . an- 1 be distinct nonzero elements of ~:q. Then choosing x n = X7=~ aix i yields a (*)code. OBSERVATION 2. If there exist methods of constructing (*)-codes for ql and for q2, then there also exists such a method for q = qlq2. Proof. Represent every symbol x i, 1 ~ i <~ n - 1, uniquely as a pair (x!l),x!2)), where x!1) is a digit base ql a n d x!2) is a digit base q2. Compute separately x~) from (x~) . . . . . x,q)- 1), J = 1, 2, where x,q) is a digit base qj, a n d then restore the symbol x n base q. Thus, the only case left is q --- 2s, s odd. A nice way to treat this problem was suggested in [9]. Consider the dihedral group D s of order q w h o s e elements are given by pairs (e,x) with e E { - 1,1} a n d x E {0, 1. . . . . s - 1}. The group law is given by (e,x) 9 (f,y) = (ef,ey + 22

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

Finally, form

Xn

=

[q.n-l(xl)

, Tn-2(X2)

, . . . ,

T(Xn_ I)]- I,

where Tm = q"O q.m--1 a n d the inverse is taken in D s. P r o v i n g t h a t the code t h u s d e f i n e d satisfies (*) a m o u n t s to straightforward calculations [9]. Note that for q = 2, the problem of finding the maxi m u m size of a (*)-code remains unsolved.

Decoding of BCH Codes and a System of Nonlinear Equations In this section, we describe various approaches to the solution of a nonlinear system that attracted the attention of mathematicians d u r i n g the last 200 years starting in the 1790s. The first to consider it was de Prony [10], w h o was led to it by an interpolation problem (this was observed in [11]; see also [12]). After that, it has been considered (seemingly, for its o w n sake) by Srinivasa Ramanujan [13]; finally, it arose in a problem of decoding a class of algebraic codes (see [14-16], a n d also [17]). Here we derive the system in question in the frame of coding theory. Gaspard-Clair-Fran~ois-Marie baron Riche de Prony (1755-1839) was a well-known French engineer in public service. In different periods of his 40-year activity he was e n g a g e d in various projects, from relating the Greenwich meridian to that of Paris to measuring the m a x i m u m power of the steam engine, and from measuring the speed of sound to compiling trigonometric tables up to 19 decimals. Therefore, it is less surprising that he once came u p o n the problem we are going to consider, than that he f o u n d a solution that later became the frame of reference for the decoding of a class of algebraic codes. Let q be a prime power a n d suppose F = Bzqis a finite field of q elements. Let n = qm _ 1, Q = qm; denote by oL a primitive element of BzQ. Fix a basis of ~:Q over 0:q. For a positive integer 8 1> 2, consider the matrix

H=

(X2

Ot4

i

:

ORS-1 (X2(8-1)

...

"t

(X2 ( n - l )

:

...

'

(x(n-1)(8-1)

and substitute for every qm-ary entry of H the corresponding q-ary column vector of length m. Denote the resulting matrix by H*. Consider the subset B of vectors a ~ F" that satisfy the following linear system: H*a T=

0.

(4)

As the rows of H* are not necessarily linearly independent, the dimension k = dim(B)/> n - m(8 - 1). It is also possible to describe B as the set of vectors a E ~:q that satisfy the following ~ relations in ~:Q: H a T = 0.

(4')

Equation (4') is more convenient than Equation (4) because it enables us to use the properties of H. For example, any 8 - 1 distinct columns of H form a Vand e r m o n d e determinant. This implies that w, the mini m u m H a m m i n g w e i g h t of a n o n z e r o solution of Equation (4'), is greater than or equal to 8. The [n,qk,d I> 8] code B is called a (narrow-sense primitive) BCH code (after the n a m e s of its discoverers; see [18, 19]). The BCH codes are extremely popular because of their remarkable algebraic properties ([20], Chaps. 7-11, [17], Chaps. 5-11) that allow implementing the decoding Da by a simple polynomial algorithm. The d o m a i n of Da is the set of all vectors of F" that are at distance ~ t = [(8 - 1)/2] from B. For any x E F" and a E B, the condition d(x,a) ~ t implies Da(x) = a, that is, Da corrects u p to t errors. Suppose a vector received from the channel is equal to x = a + e, where wt(e) = v ~ t. Denote by S = ($1..... S2t ) the 2t-dimensional vector over ~:Q: S = H x T = H e T.

(5)

Usually S is called a syndrome. Clearly, for S = 0, we m u s t set D8 (x) = x. Otherwise, consider system (5) in greater detail. Denote by X 1 = c~il. . . . . X v = a 'v the n u m b e r s of nonzero coordinates in e, called the error locations. Suppose the values of these nonzero coordinates (errors) are Y1. . . . . Y~ E 0:9. Then system (5) turns into Y1X1 + "'" + Y~Xv = $1, Y1 x 2 + ... + yvx2v = $2, I

(6)

YIX2' + "'" + yvx2v t = S2t.

We are to solve system (6) in I:Q with respect to the u n k n o w n s X i, Yi a n d to find the correct value of v ~ t. As mentioned above, system (6) has been independently considered in [10], [13] and [14, 15]. De Prony obtained it in the course of studying a problem of "'curve fitting" over reals (that is, of interpolation) with respect to 2t equidistant points in the class of exponential functions of the form f(x) = E~= 1 Yi Xx. Finding the u n k n o w n coefficients Yi, Xi again leads to system (6) with v = t. Surprisingly, both de Prony a n d Peterson, Gorenstein, a n d Zierler suggested one a n d the same m e t h o d of solving system (6) that is appropriate for an arbitrary field (save one step m e n t i o n e d below). The m e t h o d also yields the correct value of v.

Denote by 1;

or(x) = H

(1

(7)

xXi)

-

i=1

the polynomial with roots equal to the reciprocals of the error locations X i. We are going to find the coefficients ora. . . . . or~ of this polynomial. Multiply Equation (7) by YlX~ +v and set x = Xz-l: Y I X I +v + orlYlXi +v-1 + ... + ( y v Y l X i = O.

(8)

S u m m i n g the Equations (8) over l = 1. . . . . v and taking into consideration system (6), we arrive at the recurrence relation orlSj+v--1

"F " ' " +

orvSj =

(9)

-- Sj+v.

W h e n j runs from 1 to v, Equation (9) generates a system of linear equations in ori:

Sv+l] 52 v

53 :

...

Sv+l

...

Sv+l : S2v-1

v-1 i

.

L orl j

,lO,

Ls2 j

It is not difficult to prove (see [17], Theorem 7.2.2) that the determinant of this system is zero if v is greater than the actual n u m b e r of errors and nonzero if v is equal to this number. Therefore, computing determinants of (10) for v = t, t - 1 . . . . . we can find the n u m b e r of errors. Clearly, de Prony's solution did not need this step because in his problem v --- t. Solving linear system (10), we find the coefficients of the polynomial or(x). The problem is n o w to find its roots. At this point, de Prony applied numerical m e t h o d s for solving equations of high degree that had just been devised by Lagrange (see [12]). In coding theory, it is possible to inspect all elements of the (finite) field of constants ~Q to find the error locations X i, 1 <~ i ~ v (the so-called " C h i e n search"). After this has been done, finding values of Yi from the by-now linear system (6) presents no further difficulties in principle, but it requires some additional computational effort. This drawback of the proposed solution led G. D. F o m e y [21] to a simplification based on a relation between or(x) and S(x) = E2it i Si xi. Define the polynomial of error values

oo(x) = E Y,x,x I I i1 - xjx) i=1

j#i

Then the following equality holds: oo(x) = S(x)or(x)

m o d x2t.

(11)

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 2 3

Indeed, 2t

S(x)(r(x) = s j=l

= i=1

r , x , x I I (1 lr

v

s i=l

v

YiXixJ 1-I ( 1 - X,x) I=1

x , x / ( 1 - xix) N (x,xlJ

.

j=l

The term in brackets equals I modulo x2t and Equation (11) follows. Since deg 00(x) ~< t, to find 00(x) from Equation (11), we need only the first t coefficients of S(x). Once we have found 00(x), the error values Yi are readily found from the relation

~o(x; ~)

Xi~o(X;1)

Yi = I-~>i(1_ XjX71) = -r

9

Thus, one can observe that Forney's algorithm for the computation of error values is, in essence, Lagrange interpolation. Finally, note that because this algorithm relies on the code construction (4), it guarantees the realization of the designated distance 8, not the true distance d. Relation (11) plays the principal role in the decoding of BCH codes. For this reason, it is referred as the "key equation" in coding theory [16] (whereas in numerical mathematics, it is known as the Pad6 equation). The aim of our exposition was to remark that this relation was also central in the method of solving the system (6) proposed in 1912 by Ramanujan. His idea of finding Yi and X i was much the same as the one here and involved the relations between power sums g X~ and symmetric functions r 1. . . . . Xv) known as Newton identities. Here we applied these identities in the generalized form (9). It is interesting to note that G. H. Hardy, in the foreword to the edition of Ramanujan's collected works, ranked this small paper among Ramanujan's major achievements.

Concluding Remarks. 1. It follows from (9) that one may view the problem of finding the coefficients of r as the problem of synthesis of the shortest linear feedback shift register with feedback coefficients - r . . . . - r that generates a given syndrome sequence. An algorithm that solves the problem in this form has been proposed in [16]. The "modern" description of this algorithm is due to J. Massey. We refer to [17] for a detailed formulation and discussion of the Berlekamp-Massey algorithm (BMA) which is computationally simpler than the procedure described above. Recently, the BMA was generalized to 2- and N-dimensional syndrome arrays [22] and applied to the decoding of algebraic-geometric codes. 24

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

2. The problem of solving the system (10) of the so-called Yule-Walker equations (which is to say, inverting Toeplitz and Hankel matrices, or solving discrete-time Wiener-Hopf equations) has been extensively studied, not only in coding theory but also in digital signal processing and in numerical methods. Since the 1947 paper [23], numerous algorithms have been suggested to solve this problem (see, e.g., W. Trench's article [24], whose algorithm is close to the BMA), many of them founded on Euclid's algorithm. The fastest version of the BMA, which applies the fast Fourier transform in finite fields, has the time complexity O(n log2n). We refer to [25] for an overview and comparison of these methods.

Perfect Coverings of Hamming Space and a Football-Pool Problem Let q = pm be a prime power. Here we consider a problem of constructing a covering of the vector space 0:q with Hamming metric. A subset A C Q:qis called an R-covering if for every x E 6:q there exists a E A such that d(a,x) ~< R.

(12)

The parameter R is called the covering radius of A. If A is a covering, then, of course, for some x there may be more than one vector from A with property (12). However, if A is at the same time a code with minimum distance d and t = [(d - 1)/2] (t <~ R), then all the vectors x with d(x,A) ~< t are covered only once. Finally, if t = R, the code A forms a perfect covering and rl for every x E GZq, there exists exactly one a E A such that inequality (12) holds. In this case, A is called a perfect code. Observe that perfect codes necessarily have odd distances. One can easily compute the size of a perfect [n,M,d = 2t + 1] code A: t

i=0

Because no code can be of size greater than the righthand side of Equation (13), this equality presents an upper b o u n d to the cardinality IAI of a code of length n having distance d. Let us give some examples of perfect codes: 1. q-ary linear In = (qm _ 1)/(q -- 1),q "-m,3] Hamming code ~m; 2. binary linear [23,212,7] Golay code ~323; 3. ternary linear [11,36,5] Golay code ~3n. Surprisingly, any nontrivial perfect code over a finite field either has the parameters coinciding with those of ~fm or is equivalent to one of the Golay codes. This theorem (proved independently by two different teams of researchers in 1973) can be found in [20], Sec. 6.10.

Both Golay codes are plainly linear. For example, the code ~311 is s p a n n e d by the rows of the matrix [I61P], where

P=

ii11111 0

1

-

1

0

1

-

1

0 1

1 0 1

(as usual, we write - instead of - 1 ) . The ternary linear code ~312generated by the matrix G = [I61S], where

[~ 1 1

S =

P

:

i

is not perfect but helps a lot in studying the properties of ~3n by establishing a number of deep connections, some of which are m e n t i o n e d at the e n d of this section. In fact, c4~12can be obtained from ~311 after extending each code w o r d a by adding the overall parity check. Define the inner product (a,b) = ~ aibi m o d 3 of two vectors a,b E Yq. A code A C U:~is called weakly self-dual (or self-orthogonal) if A C A ~- and self-dual if A = A ~. Clearly, a weakly self-dual linear code with dim A = n/2 is self-dual. Because SS T = - 16 (rood 3), every two rows of G are orthogonal. We conclude that ~312is selfdual (and so is ~324, the extended binary Golay code). Therefore, the H a m m i n g weight of every a E ~12 is divisible by 3. The weight distribution of ~312 is the following: M 0 = 1,

M 6 = 264,

M 9 = 440,

M12 = 24,

unique. COROLLARY. The Golay code ~3n is unique.

-

1

T H E O R E M 3 ([20], Sec. 20.8). A ternary [12,36,6] code is

(14)

where M i is the n u m b e r of vectors of weight i. It can be s h o w n that the largest m i n i m u m weight d a self-dual [n,3"/2,dl code A over F3 can have equals 3[n/12] + 3. So the code ~312is extremal in this sense. It appears that the weight distribution of a n y extremal self-dual code m u s t coincide with the one described in (14). Moreover, one can see that the 132 distinct supporting sets of the words of weight 6 in A form the Steiner system S(5,6,12). From this, it is not very difficult to prove the following result. THEOREM 2 (Theorem 98 in [27]). A ternary self-dual [12,36,6] code is unique. This means that a n y ternary self-dual [12,729,6] code can be obtained from ~312 after a suitable permutation of coordinates. The following theorem is also valid (though considerably more difficult to prove):

The problem of constructing a good (not necessarily perfect) covering of the H a m m i n g space ~3 is also called the football-pool problem. To explain this second name, consider a lottery that invites its participants to forecast the correct results of a series of n (football or other) matches b e t w e e n k n o w n teams. The objective is to form a ternary n-vector x with coordinates equal to Win, Draw, a n d Lose that is close in H a m m i n g metric to the correct vector a that becomes k n o w n later. A guess x is good (and is paid for) if d(x,a) ~< t, where t is a threshold i m p o s e d by the lottery rules. A player is charged for each forecast. Suppose a person has definitely decided to win or at least not to lose, that is, to complete a reasonable set A of guesses at least one of which is good. Clearly, the best choice for A would be a perfect covering of 0:~. This does not m e a n that he or she will necessarily get back more than the invested sum. (Seemingly, a better strategy would be to choose a r a n d o m subset of A; we shall not go into details.) Suppose a football pool consists of 12 matches a n d t = 2. Usually, even a lottery novice is sure about the result of one game of the pool. The code ~3n provides a very good play system for the remaining 11 matches. This connection might seem strained were it not for events in 1947 in Finland, w h e r e Juhani Virtakallio published the code ~311 in issues 27, 28, and 33 of the Finnish football pool magazine Veikkaaja. In the accomp a n y i n g text he diffidently reports: The following system with 729 columns [=codewords] was born in my brain during a period of depression in football-pool prizes. Because the prizes were too small at that time to compensate the investments that would have been required if the system had been used week after week, the system remained unpublished and was forgotten among other systems. When during the last winter the football-pool prizes reached a peak, there was talk with the editors about publishing the system but they could not fit the 729 columns into the magazine. Only now, when I discovered a method to obtain the required saving of space, does this system get a chance to enrich the possibilities of players, and perhaps the players themselves. If the match chosen to be the sure match has been forecast correctly, the system guarantees at least 10 correct results. In the model we only present how to forecast the 11 other matches, the sure match has not been written down. (cited from [26]) Whereas the discovery of the code ~3n a year a n d a half before it was constructed by M. Golay [28] is remarkable in itself; it becomes even more surprising in view of the corollary, as well as the fact that it is one of the few existing perfect codes over finite fields. The Golay codes have a n u m b e r of other interesting and deep properties. For example, consider the group THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 2 5

(Aut ~12) + = (Aut c~12)/{~1}, where Aut q~12 is the a u t o m o r p h i s m g r o u p of the Golay code ~12" It is k n o w n that A u t (~12 ~-- J~12,

a Mathieu group, a 5-transitive sporadic group of order 95,040. The a u t o m o r p h i s m group of ~311 is isomorphic to a subgroup of d~12 that fixes a certain coordinate, d~12 is a subgroup of another Mathieu group, ~24, that itself is the a u t o m o r p h i s m group of the Golay code ~324. This code is obtained from the code ~323after adding an overall parity check. The code (~24 is closely related to the Leech lattice A24 C ~24 that is k n o w n as a very good (indeed, the best possible) packing of unit spheres in 24-dimensional Euclidean space. A parti-colored mosaic of the properties of Golay codes, the Leech and k i n d r e d lattices, a n d related m a t h e m a t i c a l results forms the main contents of the voluminous book [30]. The football-pool problem gave birth to a n u m b e r of articles [30-33] devoted to the construction of good covering codes. Suppose we know for certain that in b of n matches of the pool, one of the teams is likely not to lose. Then, in these b coordinates, only two possibilities, W and D, are left. This leads to the problem of constructing covering codes in the " m i x e d " space M(b,n) = ~:b 2 X ~:~-b. The three most recent articles in the cited list are devoted to the construction of mixed covering codes in the space F 1 x F2 x 999x Fn, where [Fi[ = qi ~> 2. In particular, [31] contains a large table of the best-known covering codes in M(b,n) for I ~< n ~< 13 and 0 ~< b ~< 13. Needless to say, m a n y codes cited in it originate from Veikkaaja, Veikkaus-Lotto, a n d 11 other magazines a n d brochures devoted to football-pool systems. References

1. C. E. Shannon, A mathematical theory of communication I, II, Bell Syst. Tech. J. 27 (1948), 379-423, 623-656; reprinted in C. E. Shannon and W. Weaver, A Mathematical Theory of Communication, Urbana: University of Illinois Press (1949). 2. R. G. GaUager, Information Theory and Reliable Communication, New York: Wiley (1968). 3. I. Csisz~ir and J. K6rner, Information Theory. Coding Theorems for Discrete Memoryless Systems, New York: Academic Press (1981). 4. R. C. Singleton, Maximum distance q-nary codes, IEEE Trans. Inform. Theory IT-10(2) (1964), 116-118. 5. W. F. Friedman and C. J. Mendelsohn, Notes on codewords, Amer. Math. Monthly 39 (1932), 394-409. 6. D. Kahn, The Codebreakers: The Story of Secret Writing, New York: Macmillian (1968). 7. G. Simmons, How good is the Acme code? Fourth Joint Swedish-Soviet International Workshop on Information Theory, August-September 1989, Gotland, Sweden, Open Problems, pp. 24-30. 8. J. Verhoeff, Error Correcting Decimal Codes, Mathematical Center Tracts No. 29, Amsterdam: Math. Centrum (1969). 26 THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993

9. H. P. Gumm, A new class of check-digit methods for arbitrary number systems, IEEE Trans. Inform. Theory IT31(1) (1985), 102-105. 10. M. R. de Prony, Essai exp6rimentalle et analytique, J. I~cole Polytech. (Paris) 1 (1795), 24-76. 11. J. K. Wolf, Decoding of Bose-Chaudhuri-Hochquenghem codes and Prony's method for curve fitting, IEEE Trans. Inform. Theory IT-13(4) (1967), 608. 12. R. Hill, Error-correcting codes I, II, Math. Spectrum 22(3) (1989-1990), 94-102; 23(1) (1990-1991), 14-22. 13. S. Ramanujan, Note on a set of simultaneous equations, J. Indian Math. Soc. 4 (1912), 94-96. 14. W. W. Peterson, Encoding and error correction procedures for the Bose-Chaudhuri codes, IRE Trans. Inform. Theory IT-6 (1960), 459-470. 15. D. C. Gorenstein and N. Zierler, A class of errorcorrecting codes in pm symbols, SIAM J. 9 (1961), 207214. 16. E. R. Berlekamp, Algebraic Coding Theory, New York: McGraw-Hill (1968). 17. R. Blahut, Theory and Practice of Error Control Codes, Reading, MA: Addison-Wesley (1984). 18. R. C. Bose and D. K. Ray-Chaudhuri, On a class of error-correcting binary group codes, Inform. Control 3 (1960), 68-79. 19. A. Hochquenghem, Codes correcteurs d'erreurs, Chiffres 2 (1959), 147-156. 20. F. J. MacWiUiams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland (1977). 21. G. D. Forney, On decoding BCH codes, IEEE Trans. Inform. Theory IT-11(4) (1965), 549-557. 22. S. Sakata, Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Massey algorithm, IEEE Trans. Inform. Theory IT-37(4) (1991), 1200-1203. 23. N. Levinson, The Wiener RMS error criterion in filter design and prediction, J. Math. Phys. 25 (1947), 261-278. 24. W. F. Trench, An algorithm for the inversion of finite Toeplitz matrices, SIAM J. 12 (1964), 512-522. 25. Y. Sugiyama, An algorithm for solving discrete-time Wiener-Hopf equations based upon Euclid's algorithm, IEEE Trans. Inform. Theory IT-32(3) (1986), 391 !09. 26. I. Honkala, On the early history of the ternary Golay code, an appendix to [31], unpublished manuscript. 27. V. Pless, Introduction to the Theory of Error-Correcting Codes, 2nd ed., New York: Wiley (1989). 28. M. Golay, Notes on digital coding, Proc. IEEE 37 (1949), 637. 29. J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, New York: Springer-Verlag (1988). 30. H. J. L. Kamps and J. H. van Lint, The football pool problem for 5 matches, J. Comb. Theory, Ser. A 3 (1967), 315-335. 31. H. H/im/il/iinen and S. Rankinen, Upper bounds for football pool problems and mixed covering codes, J. Comb. Theory, Ser. A 56 (1991), 84-95. 32. J. H. van Lint, Jr. and G. J. M. van Wee, Generalized bounds on binary/ternary mixed packing and covering codes, J. Comb. Theory, Ser. A 57 (1991), 130-143. 33. G. J. M. van Wee, Bounds on packings and coverings by spheres in q-ary and mixed Hamming spaces, J. Comb. Theory, Ser. A 57 (1991), 117-129.

Institute for Problems of Information Transmission Ermolovoy 19 Moscow, GSP-4 101447 Russia

Karen V. H. Parshall*

A Parisian Caf and Ten Proto-Bourbaki Meetings (193! 1935) Liliane Beaulieu

The Caf~ Capoulade came from Auvergne. Like m a n y of his fellow countrymen, he migrated to Paris where he became a caf6 owner. From the nineteenth century, bougnats ~ abounded in Paris, where modest neighborhood cafes often doubled as coal stores. In the interwar period, the caf6 business flourished, despite the fickleness of the French economy. Some Auvergnats opened or bought grandes brasseries, in Montparnasse or SaintGermain-des-Pr6s, places such as La Coupole, Le D6me, La Brasserie Lipp, Le Caf6 de Flore, and Les Deux Magots. These became world-famous institutions when politicians, artists, actors, writers, and scientists from all over France, Europe, and the United States poured into Paris. They tasted la boh~me or partook of the intense intellectual life which the city seemed to spawn. With Georges Braque, Pablo Picasso, Andr4 Breton, and Paul i~luard, among m a n y others, setting the trends in arts and letters, Parisian caf6s served as the breeding grounds of their followers. Less visible, but not less crowded, were the caf6s, tabacs, and brasseries of the Latin Quarter, establishments like Balzar, Capoulade, Lacipi~re, and Mahieu. 2 Capoulade's car6 was located at 63 boulevard SaintMichel, at the comer of Soufflot, near the Panth6on and the Luxembourg Gardens. It was the regular haunt of litterati who preferred to meet in its basement room rather than frequent the glamorous establish-

ments of Montpamasse or Saint-Germain. 3 Its clientele also included students, professors, publishers, and people who worked in the Latin Quarter where the Sorbonne, the l~cole Normale Sup~rieure, the I~cole Polytechnique, the l~cole des Mines, many scientific laboratories, and several renowned lyc~es were concentrated. At Capoulade, a group of mathematicians met informally but regularly during the academic year 3 See H e r b e r t R. L o t t m a n n , La Rive gauche, Points, Paris: Seuil (1981).

1 T h e people from A u v e r g n e , as well as their s h o p s , w e r e c o m m o n l y called bougnats. 2 W h e n t h e y were n o t called "caf~ de . . . . " Parisian e s t a b l i s h m e n t s were often referred to b y their o w n e r ' s p a t r o n y m . * C o l u m n Editor's a d d r e s s : D e p a r t m e n t s of M a t h e m a t i c s a n d History, University of Virginia, Charlottesville, VA 22903 USA. THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1 9 1993 Springer-VerlagNew York

27

1934-35. The loose circle gradually f o r m e d a real working t e a m a n d later b e c a m e f a m o u s for its m a n y v o l u m e d , perpetually revised treatise entitled ~ldments de MatMmatique, 4 w h i c h has b e e n published u n d e r the p s e u d o n y m "Nicolas Bourbaki" from 1939 to the present.

T h e First M e e t i n g a n d Its C o n t e x t December 10, 1934. At the sacred h o u r of noon, Capoulade is filling up. H e n r i Caftan, Claude Chevalley, Jean Delsarte, Jean D i e u d o n n G Ren6 de Possel, and Andr6 Weil meet---over a lunch of cabbage soup and grilled meats s e r v e d with endives brais&s or pommes 4 The singular was favored over the usual plural. Bourbaki chose this title around 1938. The pseudonym was chosen in the summer of 1935.

souffldes---to exchange views o n a n e w project, s Weil

o p e n s the discussion with a general but firm s t a t e m e n t which m a p s out the perspective. The goal of the venture will be "to define for 25 years the syllabus for the certificate in differential a n d integral calculus b y writing, collectively, a treatise o n analysis. Of course, this treatise will be as m o d e r n as possible. ,,6 All are ard e n t l y in favor. The principle of collective writing makes g o o d sense. Because analysis touches o n such different specialties, the w o r k of m a n y people will allow better and more t h o r o u g h coverage. Delsarte is particularly insistent on this issue, but he also realizes that b y sharing the writing the g r o u p will leave n o 5 The reports on the meetings, which were used as a primary source for this account, are analyzed and described extensively by Liliane Beaulieu [Bourbaki. Une histoire du groupe de matMmaticiensfranfais et de ses travaux, 1934-1944, 2 vols. (Ph.D. dissertation, Universit6 de Montr6al, 1989)]. 6 Translation by the author.

"CafG grill-room, A. Capoulade," 63 boulevard Saint-Michel, comer of Souffiot, Paris (1934). Until recently, this caf~ was a meeting point for the artists, students, professors, publishers, and employees who haunted the neighborhood where the Sorbonne, ~cole Normale Sup4rieure, Ecole Polytechnique, I~cole des Mines, scientific laboratories, and lyc~es were concentrated. Inside the cafG two rooms accommodated patrons for meals and drinks. The basement room was often used for meetings. In the unrestrained atmosphere of the Latin Quarter and free from the constraints of the university, it served the needs of the proto-Bourbakis. Copyright Agence Roger-Viollet, photo Boyer. 28

THE MATHEMATICAL 1NTELLIGENCER VOL. 15, NO. 1, 1993

At the same address now stands a fast-food restaurant in the "Quick" chain. The population of the Latin Quarter, especially lyc~e students, still constitutes part of the clientele, but the style of the restaurant does not lend itself to lengthy and intense meetings. Good old "c6te" wine is no longer served, and the basement room now houses arrays of huge freezers. Like a reminder of the interwar years, the poster on the right in the foreground advertises an exhibition of works by Andr4 Breton and his cafes-habitues, surrealist companions. Photo by Liliane Beaulieu, June 1991.

traces of individual authorship and may thereby safeguard against future claims to intellectual property. 7 In the ensuing discussion, all but one participant agree that the treatise should be geared to teaching rather than reference. Someone m e n t i o n s that it should cover about 1000 pages. Delsarte urges that the treatise should appear quickly, within 6 months, so as to assure surprise. Consequently, they agree to set a definitive table of contents by the summer of 1935, when a general meeting will convene to parcel out the various writing tasks. At the time of the first meeting, "differential and integral calculus" and "analysis" were nearly synonymous in French mathematics instruction. The courses offered to students w h o registered for the licence in mathematics changed very little in the twenties and the thirties. In Paris, they chose from: differential and 7 These thoughts of Delsarte were not recorded in the report on the first meeting. Most likely they were expressed at some other time. They were recounted by his colleagues, Cartan and Weft. See Henri Cartan, Sur Jean Delsarte, in "Hommage a Jean Delsarte," Nichifutsu Bunka 25 (1970), 27-30.

integral calculus, advanced geometry, rational mechanics (or analytic mechanics and celestial mechanics), application of analysis to geometry, group theory and calculus of variations (or function theory and the theory of transformations), probability and mathematical physics, and general physics, s Another course, math~matiques g~n~rales, was a prerequisite for physics and mathematics students alike. Each course and its examinations constituted a "certificate" and three such certificates were required for the licence degree. 9 A provincial facult~ des sciences offered fewer choices. Everywhere, though, "calculus" was the core of the mathematics curriculum, and so it was a traditional practice for professors to write a textbook on analysis. The French Cours d'analyse belonged to a particular textbook genre. Some of these, like l~douard Goursat's Cours d'analyse mathdmatique and Jacques Hadamard's Cours d' analyse professd ~ l'~cole Polytechnique, stemmed S Course announcements, Facult6 des sciences de Paris, 1920-1939, Archives nationales, Box 61AJ161. 9 The licence was then roughly equivalent to the upper levels of undergraduate instruction in the better American universities. THE MATHEMATICALINTELLIGENCERVOL.15, NO. 1, 1993 29

Many physicists who use methods of integration and operations on series obtain exact numerical results but are convinced meanwhile that they are committing some mathematical heresies. This stems from the fact that, in most analysis treatises, fundamental theorems, such as methods of calculation, existence theorems, etc., are introduced with a rather impressive wealth of precautions. These theorems contain an overabundance of hypotheses. In many cases, it will be necessary for us to reconsider such theorems. 12

essentially from and were written for the classroom. 1~ Others, like Camille Jordan's Cours d'analyse de l'~.cole Polytechnique (despite its title) and I~mile Picard's Trait~ d'analyse, were more elaborate, true general analysis treatises. 1: These books integrated relatively recent results together with some of their authors' o w n mathematical work. The Parisian professorial lectures dominated French mathematics instruction, and some consensus had developed among university teachers throughout the country as to which textbooks to adopt. Thus, not atypically, Goursat's book had a long shelf life, guiding French mathematicians in the "calculus" even in the 1950s. Although a system as centralized as the French Universitd network ostensibly fostered neither change nor originality it did, however, support them in actual practice. Instructors, and especially professors, were free to teach their subject as they wanted. So, in contrast to the ossified, albeit remarkable teachings of immortal masters, the instructors and professors in the different facult~s des sciences often taught from their own notes. Provincial university teachers may have enjoyed even greater freedom in this regard than their more established Parisian counterparts. The protoBourbakis intended to make full use of that freedom. Judging by the contents of Goursat's book, a French course on differential and integral calculus typically drew from among the following topics: differentiation, integration (definite and indefinite integrals, multiple integrals), series approximations of functions, geometry (envelopes, curves, surfaces), functions of a complex variable, analytic functions (Cauchy's theory, holomorphic functions, analytic continuation, functions of several variables), solution of differential equations (existence theorems, linear and nonlinear differential equations), partial differential equations (first-order, Monge-Amp~re, linear, elliptic, harmonic), integral equations (solution by approximations, Fredholm's theorems, applications), and introduction to the calculus of variations. The group assembled at Capoulade did not object to these topics in and of themselves. Its main qualm about Goursat's book and other current Cours d'analyse was that they misled their readers, especially physicists, on the nature of mathematical rigor.

As the Committee sees it, special conditions do not necessarily yield more rigorous results. In the Cours d'analyse, theorems tended to appear several times in the text, each time with an added set of hypotheses. Thus, Cauchy's theorem was followed by Goursat's version of it, and Stokes's theorem received similar treatment. The group at Capoulade wants to avoid this sort of repetition and to present material in a more general and modern setting. 13 Indeed, they want their treatise to be "as modern as possible"--with emphasis on the word " m o d e r n " - - i n contrast to a type of knowledge which they deem outmoded. But what does "as modern as possible" really mean? Where should they start? What topics should they include? These questions occupy them from soup to coffee. Weil states that no topic should be eliminated a priori, whereas Cartan wonders whether it is appropriate to include algebra in an analysis treatise. As far as level is concerned, Cartan suggests that the equivalent of math~matiques g~n~rales be assumed. His colleagues protest: "We should start from scratch!'" Soon after, they argue about which topic should come first: functions of real or complex variables? Whereas a majority favors Beating the real before the complex case, all promptly agree with Weft and Chevalley that it would be best to introduce algebraic aspects of the theory of complex functions first. Delsarte points out that, more generally, the treatise should start with an abstract and axiomatic exposition of some general but essential notions such as field, operation, set, and group, as in van der Waerden's book. :4 The group agrees and informally calls this introductory section the "'abstract package [paquet abstrait].'" They further concur that it should be kept to a minimum, however, because notions can always be introduced later, as the needs of exposition demand. Next, they argue

10 l~douard Goursat, Cours d'analyse math~matique, 3 vols., Paris: Gauthier-Villars (1902-1917) (a fifth edition of the third volume appeared in 1956); A first course in mathematical analysis (Earle Raymond Hedrick, trans.), 3 vols., Boston-New York: Ginn & Co. (1904-1917) (a Dover edition of this translation appeared between 1959 and 1964); and Jacques Hadamard, Cours d' analyse profess~~ l'l~cole Polytechnique, Pards: Hermann (1927). See also Hadamard's preface where he points out which extra material he deemed useful to add. 12 Camille Jordan, Cours d'analyse de l'l~cole Polytechnique, 3 vols., Paris: Gauthier-Vftlars (1882-1887) (a third edition of volume three appeared in 1915); and l~mile Picard, Trait~ d'analyse, 3 vols., Paris: Gauthier-Villars (1891-1896) (a third edition of the third volume appeared in 1928).

12 Translation by the author. These were reportedly Weil's own words. 13 Related in Andr4 Weft, Oeuvres scientifiques--Collected Papers, Vol. 1, New York: Springer-Verlag (1980), 563; and Souvenirs d'apprentissage, Vita mathematica, Basel-Boston-Berlin: Birkh/iuser (1991), 103104. The latter work appeared in English translation as The Apprenticeship of a Mathematician, Boston: Birkh/iuser (1992). A discussion of Bourbaki's treatment of Stokes's theorem appears in Liliane Beaulieu, Proofs in expository writing: Some examples from Bourbaki's early work, Interchange 21 (1990), 35--45, on pp. 36-38. 14 Bartel L. van der Waerden, Moderne Algebra, 2 vols., Berlin: Springer-Verlag (1930-1931).

30 THEMATHEMATICALINTELLIGENCERVOL.15, NO. 1, 1993

over the starting point: sets or operations and fields? They close the meeting unresolved. Weil convenes another meeting for mid-January, same time, same place. Each participant is told to bring along a list of topics which he thinks should appear in the treatise. As it set out to write its modern analogue of the Cours d'analyse, the Committee already knew where it wanted to publish its work with Hermann in its collection entitled "Actualit~s scientifiques et industrielles.'" Gauthier-Villars, the official academic publisher of mathematics at the time, was out of the question for them. Some of the most conservative French mathematicians dominated its editorial board, just as they controlled every other institutional body in the field. In contrast, Hermann stood somewhat on the fringe. It was a small, independent firm directed by an enterprising and eccentric Latin Quarter character, Enrique Freymann, who was always willing to venture into new projects regardless of how financially unsound they might appear. Respectable mathematical texts, such as l~lie Carfan's Lefons sur les invariants int~graux and Hadamard's Cours d'analyse had already been published by Hermann. 15 Furthermore, several members of the Committee had recently had first-hand experience with the publisher and its "'Actualit~s." Soon after the early demise of their friend and colleague, Jacques Herbrand, Chevalley and Weil decided to publish a memorial volume of papers. They brought their project to Freymann, and the articles soon appeared as a series in the "Actualit~s. ''16 As a collection, the "Actualit~s" had originated in 1929 and published monographs in the form of rather homely, paper-bound booklets. It encompassed a variety of series on science, some of which pertained to mathematics. Each series was headed by a director, who had full reign over content, quality, and quantity of publication. For instance, ~lie Cartan led a series on geometry, Maurice Fr~chet headed one on general analysis, and Hadamard edited another on mathematical analysis and its applications. A given series had limitations neither on duration nor on number of publications. This flexibility welcomed innovations and encouraged autonomy. Freymann and his "Actualit~s" thus provided the Capoulade group with the full editorial freedom it sought. 17 is I~lie Cartan, Ler sur les invariants int~graux, Paris: Hermann (1922). For the reference to Hadamard's text, see footnote 10. 16 Claude Chevalley and Andr~ Weil (eds.), Exposes math~matiques publi~s ~ la mbnoire de J. Herbrand, Paris: Hermann (1934-1935). This w a s an international project involving French as well as foreign contributors. Among the French contributors, Henri Cartan, Delsarte, D i e u d o n n ~ , Dubreil, a n d Weil w e r e also a m o n g the protoBourbakis. The papers presented in this series are listed in Beaulieu, Bourbaki. Une Histoire, Vol. 2, pp. 66-67. 17 See Beaulieu, Bourbaki. Une Histoire, Vol. 1, pp. 138-140 and 147148. On Enrique Freymann and his publishing house, consult Weil, Souvenirs d'apprentissage, pp. 107-109 (footnote 13).

The "Committee on Analysis" and Its Participants The informal circle first called itself the "Committee on Analysis" or "Committee for the Analysis Treatise." Delsarte apparently decided simply to write the title "Trait~ d'analyse" at the top of the reports on the meetings, although Ren~ de Possel once insisted that it should be changed to "Treatise on Mathematics." No one else supported this motion, and the title-page of the minutes remained the same for some time. The notion of membership in the group was not clearly defined either. At the second meeting, the Committee decided to limit its numbers to the following nine participants: Carton, Chevalley, Delsarte, Dieudonn~, Paul Dubreil, Jean Leray, Szolem Mandelbrojt, TM de Possel, and Weil. Dubreil attended only a couple of meetings, and in May, Jean Coulomb, a physicist with a strong mathematical background, replaced him. Leray officially stayed on until the summer. Although he did not attend very regularly, he wrote out some of the more elaborate plans which occupied the Committee for several meetings. Later, when too few members showed up to discuss differential equations, a quorum became essential. It was only in the s u m m e r of 1935 that the Committee adopted the pseudonym "Bourbaki." The participants who were present at that general meeting declared themselves "official members" and in so doing finally defined membership. 19 From time to time, the members informally invited others to join the discussions as guests or advisors. Thus, Emil Artin attended a meeting of the Committee as a guest while visiting Paris from Hamburg in February 1935. His presence did not seem to influence the meeting, however: a five-line-long outline for "set theory" went undiscussed, and measure and integration was the topic of conversation. To provide the extra manpower needed to tackle differential equations, the Committee invited the physicist, Yves Rocard, 2~ as an advisor to inform them on what would be especially useful to physicists. Although Rocard's suggestions were labeled "the physicists' desiderata," they seemed mostly related to vibration and stability problems, and they did not convey a general picture of what physicists at the time might have needed as mathematical 18 Szolem Mandelbrojt is an uncle of the mathematidan Benoit Mandelbrot of fractals fame. 19 Charles Ehresmann was asked to join the group in place of Leray. As a point of nomenclature, I use the term "proto-Bourbaki" to designate a participant in the early Committee. A "Bourbaki" is a member of the group Bourbaki and is the offidal designation coined by the group itself. A "Bourbakist" is a follower of Bourbaki. 2o Rocard was in the same class as Delsarte and Weil at the I~cole Normale Sup~rieure and is known for his work on the A-bomb a n d in the theory of vibrations. He is the father of Michel Rocard, a French socialist politidan and recent Prime Minister of France. THE MATHEMATICALINTELLIGENCERVOL.15, NO. 1, 1993 31

tools. Although Rocard's suggestions were tabled until some future meeting, some of them ultimately found a place in one of the projects on differential equations. I~lie Cartan was also called in--at the tenth meeting-to help out the Committee on integral equations, and although no formal decision was reached at that time, like Rocard's, some of his advice was also later heeded. Born between 1899 and 1909, the regular participants were graduates of the l~cole Normale Sup6rieure, with the exception of Mandelbrojt who received most of education in Poland and came to Paris for his doctorate. They shared a common background, but did not know or use the same mathematical tools, and they did not even work in the same specialties. Many of them had traveled abroad after their doctorate or while doing their doctoral research, as fellows of some granting agency, the most generous of which was the Rockefeller Foundation. Although their hosts were not always real mentors to them, those fellows w h o spent research time in Denmark, Germany, Hungary, Italy, Sweden, Switzerland, and the United States became acquainted with areas of research, methods, and resources which w e r e not c o m m o n in their native France. Partly as a result of their contacts with foreign mathematicians in France or in other countries, some participants were more familiar with set-theoretical, axiomatic, algebraic, or topological methods. Others remained closer in their work to function-theoretical questions and analytic methods on which the reputation of French mathematics had been built. Their Committee discussions reflected this heterogeneity. 21 As mathematical researchers, the proto-Bourbakis had each already published several papers. 22 Furthermore, they were the recipients of fellowships, prizes, and other distinctions. In fact, most of these men received several of the prizes of the Acad6mie des Sciences de Paris early in their careers. 23 As professors, they had also followed the then current pattern of taking a position in a French provincial facultd des sciences before seeking a call to Paris. In 1934-1935, Henri Cartan and Andr6 Weil taught in Strasbourg, Delsarte and Dubreil were in Nancy, Dieudonn6 had a position in Rennes, and Mandelbrojt, de Possel and Coulomb in Clermont-Ferrand. Chevalley and Leray were grantees of the Caisse nationale that year. 24 From their provincial vantage points, they had the freedom to experiment with new ideas and fresh approaches which might have been less accepted in Paris. Nevertheless, these

21 O n trips and traveling fellowships, see Beaulieu, Bourbaki. Une Histoire, Vol. 1, pp. 69-105. 22 O n average, the proto-Bourbaki had published 23 papers, with a m i n i m u m of 4 a n d a m a x i m u m of 75, according to a r o u g h count. 23 O n prizes and o t h e r distinctions, see Beaulieu, Bourbaki. Line Histoire, Vol. 1, pp. 87-114. 24 O n teaching posts a n d provincial French facultds des sciences, see Bourbaki. Une Histoire, Vol. 1, pp. 114-122.

32 THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993

men formed an elite in a highly hierarchical system; they were the designated aspirants to the leadership of French mathematics. Paris, of course, was the best place for them to meet. They frequently went to the capital city to keep in touch with its scientific life, to visit fellow mathematicians, and to frequent bookstores and libraries. Most of them also commuted twice a month, on Mondays, to take part in a S~minaire de rnath~matiques, which met at the recently built Institut Henri-Poincar6. They usually held their Committee meetings in the hours before the seminar. Gaston Julia, professor at the Paris facult~ des sciences, officially convened this seminar which was primarily organized and animated by a handful of devotees. At the beginning of each year, the organizers w o u l d choose the theory which was going to be the topic of the year, and draft a list of possible talks and speakers (usually recruited from their o w n ranks). The "Julia seminar," as it was called, studied the following topics between 1933 and 1939: group theory and algebras, Hilbert spaces, topology, the works of l~lie Cartan, algebraic functions, and calculus of variations. Its objective was neither to serve as a teaching seminar nor to inform the audience on current literature. Rather, it offered, to its speakers as well as to its audience, an opportunity to work through large parts of recently developed theories and methods. It forced the speakers to synthesize information which was otherwise scattered in the literature. Since the seminar had virtually no official institutional ties, it provided a free forum for criticism. There, the members of the Committee e v e n t u a l l y assimilated, together, the approaches which they later tried to integrate into their collective expository writing. 2s The Committee had neither money nor a set administrative structure. Delsarte acted as "secretary" or "manager." He wrote up minutes and sent around reminders, but he had no particular powers. A de facto hierarchy developed quickly, however, based on a mixed measure of mathematical excellence and expertise, intellectual sophistication, strength of voice, and determination. Indeed, the meetings of the Committee, like the later gatherings of Bourbaki, reportedly took place amid great noise and confusion. This should come as no surprise, given that a Latin Quarter caf4 served as their laboratory. Still, the ambience of the Latin Quarter of the mid-30s--with its strikes, demonstrations, and political street fights--did not totally dominate the group's meetings. As a mathematical team, it largely managed to remain staunchly apoliti-

25 The texts of the talks were m i m e o g r a p h e d . A near complete set is deposited at the library of the Institut Henri-Poincar6 in Paris. For the list, see Bourbaki. Une Histoire, Vol. 2, pp. 63-65. O n the Julia Seminar, see Bourbaki. Une Histoire, Vol. 1, pp. 133-137.

of the topics to be included in the treatise. 27 Of the 10 meetings, 5 were devoted mostly to differential equations, integral equations, and partial differential equations. These topics constituted the bulk of the material of the old Cours d'analyse. Integration theory, analytic functions, and a little algebra were also discussed during that semester. The Committee parceled out the various topics to separate subcommissions and m a n d a t e d each to sketch out its topic. Most subcommissions consisted of Mathematical Shoptalk: three people, no more than two of w h o m were supDiscussions and Sketches posed to be specialists in the field. Subcommissions were created for the following topics: algebra, analytic At first, the Committee's aim seemed quite clear: to functions, integration theory, differential equations, change the teaching of mathematics at the university integral equations, existence theorems (for differential level by writing a treatise on analysis. Soon, however, equations), partial differential equations, differentials another purpose emerged: and differential forms, topology, calculus of variations, We must write a treatise which will be useful to all: to special functions, geometry, Fourier series and Fourier researchers (bonafide or not), "tinders," aspirants to posts integrals, and representation of functions. There was in public education, physicists, and all technicians. As a criterion, we can say that we should (without thought of no special subcommission for set theory (which was monetary gain) be able to recommend this treatise, or at considered part of algebra), and the subcommission for least its most important sections, to any self-taught stu- topology was formed only belatedly. 28 Altogether the dent, presumably of average intelligence . . . . Mostly, we subcommissions had to concentrate on a lot of "hard must provide users with a collection of tools, which classical analysis."29 But, of course, they had to rework should be as powerful and universal as possible. Usefulness and convenience should be our guiding principles. 26 these traditional topics into a m o d e m idiom. The queries inspired by analytic functions especially How could the Committee reconcile these seemingly revealed the Committee's puzzlement over the task of disparate goals? In particular, how could a textbook on merging the traditional and the modern. A classical analysis be used equally by mathematics students, pro- topic of the Cours d'analyse, function theory had been fessional scientists, and the man in the street (however strongly affected by the ideas of Ren~ Baire, i~mile studious he might be)? The proto-Bourbaki meetings Borel, and Henri Lebesgue, especially in the area of found their participants groping to reconcile these dif- functions of real variables. The works of Lars Ahlfors, ferent objectives. Ludwig Bieberbach, Constantin Carath~odory, Nicolas A partial solution to their dilemma lay in their deci- Lusin, and Rolf Nevanlinna further changed the field. sion, at the first meeting, to "start from scratch." They The Committee had its own specialists at hand: Henri would open with a preliminary set of abstract and el- Cartan, Dieudonn~, Mandelbrojt; to some extent, ementary notions which would appear in the first sec- Leray and de Possel worked with analytic functions as tions of the treatise. They quickly decided, however, to well. When Mandelbrojt voiced the opinion that the restrict this "abstract package" to a minimum and, treatise should not overemphasize entire functions, his during the whole semester, very little was done to pro- colleagues asked whether it should not include such duce even that. In fact, the minimal "abstract package" important matters as Picard's theorem, conformal repapparently ceased to be an immediate preoccupation. resentation, elliptic functions, Abelian functions, infiInstead, two levels of questions came to the fore: glo- nite products, etc. A variety of suggestions followed bally, which topics should go into the treatise; and and, in the resulting confusion, no decision was made. locally, for each topic considered, w h a t material Analytic functions reappeared on the agenda at anshould be covered and from what point of view? other meeting w h e n the participants put together their The Committee concentrated on inventories and outlines for its eventual analysis treatise, in no particular order of presentation. Notions went undefined; 27 This aspect of the work of the first semester is mentioned in Weft, Souvenirs d'apprentissage, pp. 109-110. theorems went unstated and, of course, unproved. 28 The list of topics comes from the report on the eighth meeting. Each meeting, thus, resembled a brainstorming ses- Because Alexandroff and Hopf's book on topology only appeared in sion, with many suggestions---but few final results 1935, the Committee did not even have this reference available for bursting forth. While the Committee did not concern consideration of topological topics. See Paul S. Alexandroff and itself so much with an overall plan, it did discuss some Heinz Hopf, Topologie, Vol. 1, Berlin: Springer-Verlag (1935). cal, even though some of the Committee participants may have had leftist leanings. With the exception of some discussion of and intervention in local academic politics, the proto-Bourbakis shied away from the political arena. In their case, then, the caf6 served as a public place for mathematical practice, while it stopped short of providing a metaphor for fuller public and political involvement.

26 Translation by the author. There is a pun here on the words "chercheurs" = "researchers" or "seekers" and "trouveurs" = "finders."

29 Benoit Mandelbrot criticized Bourbaki---among other things---for having neglected what he termed "hard classical analysis" in its l~l#rnents. See Benoit Mandelbrot, Chaos, Bourbaki, and Poincar~, Mathematical Intelligencer, Vol. 11 (1989), no. 3, 10-12. THE MATHEMATICALINTELLIGENCERVOL.15, NO. 1, 1993 33

written outlines on the subject. From these, the Committee drafted a proposal which attempted to place the material in an algebraic and topological setting. It started with the geometric representation of complex numbers and stressed that these form a field. It next proposed to move to the topology of open and closed surfaces. This sketch also featured some of the more "usual" material on analytic functions: Jordan's theorem, series, convergence, differentiation, integration, Cauchy's theorem and Cauchy's integral, Taylor's and Laurent's theorems for singular points of uniform functions, conformal representation, entire functions, Weierstrass's theorem, Mittag-Leffier's theorem, analytic continuation, etc. It was suggested that the general notion of analytic function be highlighted and that two sections be devoted to algebraic and automorphic functions, elliptic functions, and the theta function (the latter, most likely, with number theory in mind). The meeting also considered whether it should introduce analytic functions of many complex variables. It delegated the decision making on these matters to its subcommission. The Committee's initial work on integration theory looked more promising. At least, one point was certain at the outset: Integration would be done from Lebesgue's point of view, which had already undergone different levels of generalization and extension since 1901. 30 Although some French Cours d'analyse did mention the Lebesgue integral (usually in passing), they did not give an exposition of Lebesgue's theory. The older texts used Cauchy's approach, and the more recent ones introduced the Riemann integral. All concentrated on developing the techniques of integration and their applications. By choosing Lebesgue integration, the proto-Bourbakis were more in line with texts such as those by Constantin Carath6odory, Charles de La Vall6e Poussin, and Stanislaw Saks. 31 The Committee resolved that measure and integration should not be separated in the presentation. It drafted a list of potential topics which started with the notion of measure and proceeded to the integral viewed as a linear functional, stressing the equivalence of the two concepts. Next followed particular types of measures and integrals on topological spaces, Radon measures, and Haar measures on topological groups. Although order of presentation was not stressed, it appeared that the latter were meant not to be the pillars of the theory, but were introduced rather as special 3o For an historical account of Lebesgue's ideas, see Thomas Hawkins, Lebesgue"s Theory of Integration: Its Origins and Development, New York: Chelsea (1975). 31 See Constantin Carath6odory, Vorlesungen fiber reelle Funktionen, Leipzig-Berlin: Teubner (1918); Charles de La Vall~e Poussin, Intdgrales de Lebesgue. Fonctions d' ensemble. Classes de Baire, 1st ed., Paris: Gauthier-Villars (1916); 2nd ed., 1936; and Stanislaw Saks, Thdorie de l'int~grale, Monografie matematyczne, 1st ed., Vol. 2, Warsaw: Zsubwencji funduszu kultury narodowe (1933); 2nd ed., 1937. 34 THE MATHEMATICAL1NTELLIGENCERVOL. 15, NO. 1, 1993

kinds of measures. At any rate, the Committee had already decided to restrict its exposition on integration theory in the treatise. This sketch of contents resulted from discussions between Chevalley and de Possel, who advocated a thorough exposition on measure, and Delsarte, DieudonnG and Dubreil, who thought that a less elaborate presentation of measure and integration might be more appropriate for the treatise. Most probably, Weil and de Possel opposed each other also: Whereas de Possel wanted to do measure and integration on arbitrary sets only, Weil wanted to involve vector spaces and topological groups. The subcommission on integration had to reconsider these different opinions. 32 Delsarte and Leray were the main protagonists in the area of differential equations. Delsarte first suggested subdividing the study of differential equations into three sections: existence theorems, eigenvalue problems (crucial in physics), and the study of local and global properties of solutions. The Committee agreed with his choices, at least in principle. Then it examined a draft by Leray on existence theorems. Contrary to most other plans, this draft was not merely a list of items. It was more like a brief introduction to an abstract theory for systems of n equations in n unknowns. Leray introduced concepts from topology and functional analysis which he had been using in his own work, especially the notions of the differential of a function of n variables (as a linear functional) and of the topological degree of a continuous transformation. His approach set the study of differential equations squarely in line with works by Riesz, Banach, and Hahn on normed spaces. Leray's draft included the statements of fundamental theorems of global existence and of local existence (with uniqueness) of a solution. The Committee thought that, although it was all very interesting, Leray's project involved topological notions which were too specialized for the treatise. Perhaps for this reason, no final decision on differential equations was reached at this point in their deliberations. At the end of its eighth meeting, the Committee itself drafted a provisional and rather jumbled outline for differential equations. This plan comprised general existence theorems, global existence for real differential equations over any domain where the conditions for local existence hold, a classical theory of general linear equations, systems of n first-order linear equations in n unknowns, and second-order linear equations with constant coefficients. Among the applications to physics, some of Rocard's old suggestions re32 These differences in opinion are discussed in Beaulieu, Bourbaki. Une Histoire, Vol. 1, pp. 178-188. Chevalley and de Possel put forth their ideas in " U n th~or~me sur les fonctions d'ensemble compl~tement additives," Comp. rend. Acad. Sci. Paris 197 (1933), 885-887. See also Ren~ de Possel, "Notion g~n~rale de mesure et d'int~grale," Sgminaire de math~matiques IIA (1934), mimeographed.

surfaced, but the conceptual setting of Leray's project study to systems of linear partial differential equations had disappeared. The Committee had adopted the with one unknown function. He also stressed that both functional approach earlier in its work, yet it did not the "classical" point of view and the Pfaffian equations seem to envisage all the implications of this choice. should be introduced. These points were well taken, With the intention of covering a lot of ground, it del- but the group still did not commit itself on partial difegated work on differential equations to two subcom- ferential equations. The Committee did not intend to treat set theory, missions, one responsible for existence theorems and algebra, topology, or even integration for their own the other for the rest. The Committee's work on integral equations pro- sakes. As it stood, then, the treatise would include ceeded differently. An initial discussion, involving only enough algebra to deal with systems of equations, Cartan, Delsarte, DieudonnG and Weil, emphasized some integration theory to support analytic functions, three approaches to the subject: bounded operators on but mostly differential equations, integral equations, Hilbert spaces, Fredholm's point of view, and the more and partial differential equations. The Cours d'analyse recent line developed by Riesz and Leray (using exerted the main pull on the topical choices of the normed vector spaces). In the absence of Leray, the proto-Bourbakis. Wanting to cast this material in a Committee temporarily opted for bounded operators modern setting, the Committee sought a workable on Hilbert spaces, which they thought was a complete g r o u n d b e t w e e n approaches which otherwise apand beautiful theory. It hesitated over the third ap- peared either too general or too specialized. The Caproach because it was less familiar to most of those poulade group made only minimal progress toward present and postponed its decisions until Leray could this goal, however, and its aim to provide mathematibe reached. Paradoxically, the Committee was willing cians and physicists with the tools of their trade still to favor bounded operators, even though quantum seemed far from reach. Also, the initially expressed mechanics required unbounded operators. Thus, de- concern for the man in the street and the average selfspite expressed intentions to serve physicists, the taught student lost its edge in the course of on-going Committee was not always guided by a close eye on debates. what was being done in that field. Other considerEpilogue ations sometimes prevailed. 33 Two meetings later, Leray came to the rescue. He In choosing a caf6 as the setting for its meetings, the found Fredholm's approach rather useless for the proto-Bourbakis were not particularly original. Indeed, group's purposes, although Delsarte disagreed. The it was usual among politicians, artists, or scientists to two also discussed how much should be done on meet in Parisian cafes. It was also common for mathb o u n d e d operators. Leray actually suggested two ematicians, as well as writers, to enjoy working at a ideas for integral equations. The first one introduced favorite bistro table. Capoulade's caf6 was a familiar nonsymmetric integral equations as a special case of rendezvous which provided freedom from strict uniequations of the form x + ~(x) = 0, where x is an versity institutions while being conveniently close to element of a Banach space and ~ is a completely con- all the amenities of the neighborhood. This mixture of tinuous operator. The second one viewed symmetric Latin Quarter parochiality and a taste for autonomy integral equations as special cases of Hermitian oper- typifies the proto-Bourbaki attitude. The narrative of ators in a Hilbert space. The Committee adopted Le- bi-weekly gatherings, however, shows disunity in the ray's approach without further ado, and so the third party, hesitation in ideology, and uncertainty in purpoint of view ultimately won the day. pose. Indeed, this was a time of ill-defined goals and For partial differential equations, Delsarte drafted a unfinished business. The Committee only investigated brief outline which emphasized two aspects: local possibilities, and, despite hearty arguments, it hesiproblems (where the notion of characteristic would be tated to strive either to make things work or to estabfundamental) and limit problems (related to integral lish truths. It willfully postponed decisions to the genequations). After some discussion, the Committee de- eral meeting of the summer of 1935, w h e n a definitive cided that the study of a single first-order partial dif- overall plan of the treatise was expected to emerge. ferential equation with n unknowns represented the T h a t m e e t i n g , w h i c h t o o k place in B e s s e - e n bare minimum of what needed to be covered. But what Chandesse, started another phase in the history of else should be included? ~lie Cartan, who attended Bourbaki. Through negotiations and selections, opporthat meeting, suggested instead that they restrict their tunities were foreclosed, but new options were foreseen. D@artement de Mathdmatiques et d'Informatique 33 On bounded linear operators in Hilbert space, see Jean Delsarte, Universit~ du Qudbec~ Montrdal "L'axiornafique des op4rateurs lin4aires dans l'espace de Hilbert: op6rateurs born6s," S~,minaire de math~matiques IIC (1934), mimeo- C. P. 8888, Succursale "A" graphed; and Jean Leray and J. Schauder, "Topologie et 6quafions Montreal, Qudbec H3C 3P8 Canada fonctionnelles," Comp. Rend. Acad. Sci. Paris 197 (1933), l15ff. THEMATHEMATICALINTELLIGENCERVOL.15, NO. 1, 1993 35

Celtic Knotwork: Mathematical Art Peter R. Cromwell

The interlaced ornament produced by Celtic scribes and stone masons has fascinated people for many centuries. The designs, ranging from small individual knots to elaborate panels composed of many motifs, provide the geometrically minded mathematician with a rich source of examples. Many aspects of the interlaced patterns can be studied mathematically, and some of these are explored in this article. We begin with the geometry of the knots.

Constructing Interlaced Patterns Underlying many of the Celtic knot patterns is a lattice. It is this lattice which imparts the distinctive proportions to Celtic knotwork. It is usually composed of squares, but is occasionally built from 3 x 4 rectangles. For reference purposes, it is convenient to regard this lattice as the union of two dual lattices whose mesh size is double that of the original lattice (Fig. lb). These

Figure 1. How to construct alternating plaitwork. 36

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 • 1993 Springer-Veflag New York

Figure 3. The rule for eliminating crossovers.

Figure 2. A non-alternating Celtic pattern.

will be called the auxiliary grids. When laying out a design only the vertices of these two grids are drawn in (Fig. lc). The knotwork created on these grids is all related to plaitwork the basic weaving pattern used in basketwork and other crafts. This is shown in Figure ld. Note how the crossovers in the pattern lie at the intersection points of the two auxiliary grids, and that the interlacing has an alternating quality: Each string goes alternately over, then under other strings. This is a characteristic feature in Celtic patterns, too, although one or two anomalies are known (Fig. 2). Interlaced patterns formed from portions of plaitwork can be found in Egyptian, Greek, and Roman ornament and in the art of many other cultures. Yet for the Celt, these alternating plaits were merely the raw material on which the artist sets to work. To obtain the more elaborate interlaced designs, the regularity of this primal pattern must be interrupted. This is achieved by breaking two strings at a crossover and rejoining the ends as illustrated in Figure 3. (Operations such as this are currently used in combinatorial knot theory.) Note that eliminating crossings in this fashion preserves the alternating property of the interlacing. When sufficiently many crossings are removed, the underlying plait ceases to be the dominant feature in the design and a pattern composed of knot motifs appears. In this way, a bewildering assortment of interlaced designs can be created. So far the only aids to laying out a design are the vertices of the auxiliary grids. Additional construction lines are drawn between these vertices to indicate which crossings are to be removed from the plait and how the ends are to be rejoined. These lines are called break-markers. Each break-marker is an edge of one of the auxiliary grids. At each crossing point of the plait, there are two such edges, and the edge chosen indicates which one of the two possible reconnections is to be used. A glance at the example in Figure 4 will make the convention clear. To complete the design, the path of the strings is outlined and the background is filled in. This obscures all the construction lines. The pattern is then interlaced to produce the characteristic alternating weave. The construction of some elemental knot motifs is illustrated in Figure 5.

Figure 4. Break-markers aid the construction by indicating how the crossings are to be broken.

Figure 5. Examples of interlaced motifs together with their construction. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. I, 1993

37

Lindisfarne Gospel (a)

I

!

(b) Figure 6. Irregularly shaped panels can be decorated using the same techniques.

Eliminating the crossings according to the simple rule indicated in Figure 3 does not always produce aesthetically pleasing results. Sometimes a better result is achieved if the path of the strings is allowed to deviate from the path of the plait. At places where two break-markers meet to form a corner, the path of the strings can also be made angular. This has been done in the accompanying figures. In other situations, fairly sharp bends can be replaced with more gentle curves to produce a more graceful, freely flowing design. Figures 7 and 8d exhibits arcs of several different curvatures. These modifications help to disguise further the underlying plait structure on which the design is based. Another variation produces a very delicate form of interlacing: What are normally taken to be the two edges of an interlaced ribbon are themselves used as the strings to be interlaced. An example of such 'double interlacing' is shown in Figure 8j. Once the technique for constructing Celtic ornament has been understood, the art itself loses some of its mystery. It becomes possible to copy the ancient designs fairly accurately and easily and to create designs of your own. (Do not be surprised, though, if you discover your creations elsewhere.) Any rectilinear area can be filled with knotwork by regarding its boundary as being composed of break-markers on a suitable lattice (see Fig. 6a). Patterns can also be mapped into curvilinear regions by dividing them into quadrilaterals (Fig. 6b). Simple though this construction procedure may appear, the idea that the Celtic interlaced patterns were related to plaitwork took many years to mature. The methods used by the Celts themselves are no longer known, and the above technique was developed by J. Romilly Allen while he was surveying the patterns in the British Isles at the turn of the century. He records [1] p. xvii: The theory of the evolution of Celtic knotwork out of plaitwork . . . is entirely original, and, simple as it appears when explained, took me quite twenty years to think out whilst classifying the patterns. When we remember the large number of modifications the underlying plait can undergo and the ease with which it is disguised, perhaps this is not so surprising.

Interpreting Celtic Designs

Figure 7. This pattern is not based on the standard grid.

38

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

As Friezes

Much Celtic knotwork is in strip form, either as part of a border or simply as a narrow rectangular panel. In many of these strip patterns, the crossings are eliminated systematically and the pattern of break-markers repeats at regular intervals. This produces a pattern which can be described as "locally periodic": A single motif is repeated side by side. In other forms of orna-

ment, such periodicity gives rise to translational symmetry when the pattern is regarded as a randomly chosen segment of an infinite strip. However, in knotwork, the transition from a small s e g m e n t to an idealised frieze is not so immediate. Whereas in other forms of decoration, a pattern is simply truncated when it reaches the edge of the available space, knotwork is rarely terminated so abruptly. The pattern is adapted so that the otherwise free ends join up to form continuous strands. In this article, the knotwork patterns are regarded as friezes in the conventional mathematical sense: as parts of patterns which extend indefinitely in both directions. In the underlying lattice, the pattern is bounded by two parallel lines of break-markers and the other breaks are arranged so that the pattern as a whole has translational symmetry. Some examples are shown in Figure 8. The first two patterns are not constructed on a standard lattice. The pattern in Figure 8a is believed to be Scandinavian. Triangular motifs such as that used in Figure 8b are normally arranged in sets of four to form square patterns. An example based on the same motif is shown in Figure 7. I have excluded patterns that can be split up into other patterns. For example, if the knot design in Figure 2 is converted into a frieze, the resulting pattern comprises two parallel patterns which are not interlinked. An interlaced pattern is said to be connected if the unlaced path (or equivalently, the projection of the link onto the picture-plane) is connected. The frieze constructed from Figure 2 is not connected. For the moment, I shall assume that the friezes are connected and that the notion of connectedness captures to some extent our intuitive understanding of when a pattern can be split up. We shall, however, return to this question of separability later.

The Symmetry of Interlaced Friezes The symmetrical nature of frieze patterns is analysed mathematically in terms of symmetry operations: isometries which carry a pattern onto itself. It is wellknown that there are four isometries of the plane: rotation, translation, reflection, and glide-reflection. For planar frieze patterns, the only possible symmetries are 2-fold rotation, reflection in the centre-line, reflection in a line perpendicular to the centre-line, and glide-reflection along the centre-line. These symmetries can be combined in different ways but the number of combinations is limited to seven by the rigidity of the geometry. Examples of patterns exhibiting these seven different symmetry types are shown in Figure 9. When the knotwork friezes are compared with these planar patterns, it becomes apparent that we do not interpret the two kinds of pattern in the same way. The interlaced patterns are not confined to lie in the plane.

At the crossovers, the strings appear to extend behind and in front of the picture-plane. We perceive a threedimensional object composed of continuous strings lying in a neighbourhood of the plane, not a collection of arcs lying in the plane. We expect to see the obverse pattern on the back. I n t e r p r e t i n g the i n t e r l a c e d f r i e z e s as t h r e e dimensional patterns means that there are additional isometries which can act as symmetries. Two of these are compound motions like the glide-reflection: a screw is a rotation followed by a translation along its axis; a rotatory-reflection is a rotation followed by a reflection in a plane perpendicular to its axis. Both of these isometries can act as symmetries of an interlaced pattern. The complete set of possible symmetries of 2-sided friezes is described by reference to a set of standard axes: the a-axis runs along the band, the b-axis lies in the plane of the band perpendicular to a, and the c-axis is normal to the band. The possible symmetries are a 2-fold rotation about any of the three axes, reflections in the planes orthogonal to each of the three axes, glide-reflections in the planes orthogonal to a and b, a screw motion along a, and a 2-fold rotatory-reflection about c. This last symmetry is the same as reflection in a point or inversion (because it is a 2-fold symmetry). There are many different ways in which these symmetries can be combined. As these 2-sided friezes are less familiar than the seven 1-sided ones, patterns illustrating the 31 symmetry types [5] are shown in Figure 10. The motif in each of the patterns is a scalene triangle which, in most cases, is coloured black on one side and white on the other. When reflection in the plane of the strip is a symmetry, then both sides of the triangle must be the same colour: in this case the triangles are coloured gray. Next to each pattern is a label of the form P[313U] which encodes the symmetries present in the pattern. After the symbol P (which denotes that the pattern is periodic in one direction) the symbols 2, 2', 2, m, and a are used to indicate that an axis of 2-fold rotation, 2-fold screw, 2-fold rotatoryreflection, or the normal vector of a mirror plane or glide plane coincides with one of the reference axes. The first, second, and third symbols after the P correspond to the a-axis, b-axis, and c-axis respectively. If an axis and a plane of symmetry coincide with the same reference axis, both symbols are given; if no symmetry element corresponds, then the symbol I is used as a place marker. Trying to identify which symmetries are present in a particular knot pattern is not trivial. The reader is encouraged to experiment on the patterns in Figure 8. A useful observation is that the crossings in the Celtic friezes all have the same alignment and that they come in two kinds. Furthermore, each kind is stabilised by all the 2-fold rotations (see Fig. 11). Thus, direct symmetries carry a crossing to one of the same kind; indirect symmetries interchange the two kinds. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

39

Sutton Hoo Buckle

Plal

(a)

Rossie Priory Stone

Plal

Book of Kells

P2'1 1

Book of Durrow

P121

Lindisfarne Gospel

P121

(b)

(c)

(d)

(e)

Figure 8. E x a m p l e s of Celtic frieze p a t t e r n s ( t h r o u g h p. 42). 40 THEMATHEMATICALINTELLIGENCERVOL.15, NO. 1, 1993

Lindisfarne Gosoel

P222

Maiden Stone. Aberdeenshire

P222

(f)

(g)

St. Vioean's Stone, Tayside

P211

(h)

I inHi.~f~rn~

Gosoel

P2'22

(i)

Figure 8 is continued

o n p . 42.

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993 41

Figure 8. Continued. 42

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

The Celtic Frieze G r o u p s After analysing a few examples, one is led to ask how many of the 2-sided groups can arise from Celtic knot patterns. Can they all occur, and if not, then which ones? The slightly different question of which ones actually occur in practice can also be considered. The seven "gray groups"--those which have the picture-plane as a symmetry element---cannot occur for knot patterns because the crossing points do not obey this symmetry. Therefore, we can eliminate all the groups whose labels have an m as part of the last symbol. The observation that virtually all interlaced ornament are alternating allows further groups to be eliminated. Suppose that a knot motif has mirror symmetry. An example is shown in Figure 12a. To convert this knot into an alternating one, it is necessary to add an extra string which lies in the mirror plane as shown in Figure 12b. Those groups which contain reflections in planes orthogonal to the a-axis cannot arise from alternating knotwork patterns because the strings that lie in the mirror planes would run directly from the top edge of the band to the bottom--they could never join up with anything else. Thus, those groups whose labels have an m in the first position cannot be found in Celtic patterns. The groups whose labels have an m as part of the second symbol can arise from alternating patterns: such patterns must have a string that runs straight d o w n the centre-line of the band. There are two of these groups: Plml and p121. They are marked with a dagger (t) in Figure 10. Patterns of this form are not consistent with the standard Celtic grid, however, and so these symmetry groups cannot arise in Celtic patterns either. There is one more class of group labels that can be eliminated: those which contain an a as part of the third symbol (indicating that the picture-plane is also a glide-plane). The reason for this is that to create an alternating design, straight strands must run across the band as in the Pm[3D case, and these strings can never join up with anything. There remain ten possibilities. These are marked with an asterisk (*) in Figure 10. Examples of Celtic patterns exhibiting each of these symmetry groups are shown in Figure 8. Where I have been able to find ancient designs I have used them; a few are my own creations. The Relative A b u n d a n c e of Symmetry T y p e s In my search for examples of Celtic designs, I discovered that the abundance of the different symmetry types varied greatly. Some groups (Pl12, P222, P2'22) were very common; others were rare. In fact, the only patterns I could find which have group Plal are not constructed on the standard lattice described above.

RRRRRRR PbPbPb , AAAAAAAA, }BBBBBBBB /AVAVA { q qHHH H Figure 9. The seven 1-sided frieze patterns.

For the two groups Pl12 and p121, I found no examples at all. Are there any features of these patterns that make them difficult to obtain? Before resolving this puzzle we shall consider another question: Is there any correlation between the (2-sided) symmetry group of an interlaced design and the (1-sided) symmetry group of its underlying pattern of break-markers? The answer to this is yes. To see why, note that the unlaced path of the strings and the distribution of break-markers have the same symmetry type. The correspondences are listed in Table 1. Observe h o w each of the three rare groups is paired with another group which appears to be the preferred option. In fact, this preference is not a matter of a choice having been made by the designer, consciously or otherwise. It is a consequence of the fact that the ancient patterns terminate and are not true friezes. Study the two sections of plaited friezes in Figure 13. Do you notice any differences? Structurally, they are the same; symmetrically, they are not. This is seen most easily along the edges. In Figure 13b, the outermost crossovers are opposite each other; in Figure 13a they are staggered with those on one edge lying between those on the other. The symmetry types of these two plaits are, therefore, different. The symmetry type of a plaited frieze depends on its width. Those plaits that have an even number of lattice cells between the two edges have symmetry type P222; those plaits that span an odd number of cells have type p121. This observation allows us to resolve the mystery of the missing groups. It also provides an alternative method for enumerating the Celtic groups; because eliminating crossovers can only destroy symmetry, the Celtic groups must be subgroups of P222 or p121. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

43

Figure 10. The thirty-one 2-sided frieze patterns.

Table 1 can n o w be refined to show how the symmetry type depends on the width of the frieze as well as the underlying markers. The result is shown in Table 2. We now have at most one group per box of the table: The symmetry type of the interlacing is completely determined by the geometry of the underlying break-markers. Furthermore, all the rare groups are associated with friezes of odd width. The only frieze I found that has odd width is shown in Figure 8d. Its symmetry type is P121--a group which is independent of the width of the frieze. 44

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

It is not difficult to discover w h y odd-width friezes are uncommon. It is not, as has been suggested [1, p. 260], that the patterns look lopsided. Rather it has to do with the fact that the original Celtic patterns are finite designs with no loose ends. At the end of a row of motifs, the strings are paired up and joined--a process which requires an even number of strings. The number of strings is related to the width of the frieze: The parity of the width equals the parity of the number of strings. The Celts could only use odd-width friezes in situations where continuity could be ensured, such

1-sided

R

2-sided

Plll

~P Plal

P2'l 1

A

B

H

VA

P121

P211

Pll~ Pl12

p121 P2'22

P222

Table 1.

A

1-sided

VA

B

2-sided (odd)

Plll

Plal

P121

2-sided (even)

Plll

P2'l 1

P121

P211

Pll~

Pla21

Pl12

P2'22

P222

Table 2.

Figure 11. Each of these 2-fold rotations preserves the crossing.

(a)

(b)

Figure 12. A pattern with bilateral symmetry can be made alternating by adding an extra strand.

(a)

(b)

,%f%f%f~f~

Figure 13. Alternating braids with five and six strings. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 4 5

4x4

5x5

3x5

4x6

Figure 14. Can the number of components in a rectangular motif be determined from the dimensions of the rectangle?

as in complete borders. In some places, loose ends occurred naturally. These are often in zoornorphs: strange creatures whose elongated tails, limbs, necks, or tongues are intertwined in fanciful patterns. However, these patterns are never large enough to have repeated motifs and so will not provide examples of friezes.

C o n t i n u i t y , Transitivity, a n d Separability

One problem faced by the designer of interlaced patterns is that of determining the number of components in the completed design. In early forms of Celtic ornament, it is clear that continuity of the path was sought. It was important as a symbol of eternity. Even extremely intricate patterns have just one string arranged in an endless loop. In some examples, the regularity of a pattern has been deliberately abandoned and the pattern modified to ensure that a unique path was obtained. In later times, this rule was followed less strictly, but small rings in a pattern were still avoided. This raises the question of whether there is a simple way to determine the number of strings in a design from the underlying pattern of break-markers. When the interlacing is a rectangular portion of plaitwork (Fig. 14), then the answer can be expressed in terms of the bounding rectangle. If the lattice underlying the plait contains n x rn cells, then the pattern will have a single component if h.c.f. (m, n) ~ 2. If the pattern is square (n = m), then the number of components is [1/2n]. In fact, if we count closed loops rather than components, t h e n the number I/2n can be regarded as correct. When break-markers are added and the plaitwork is broken up, these rules are no longer valid. What rules replace them? How about interlaced friezes: How many strings do they have? The pattern in Figure 8f is a chain composed of infinitely m a n y closed loops. All the other friezes in Figure 8 have a finite number of infinitely long strings. Most of the patterns from Celtic sources have an even number of strings; only the nonstandard patterns a and b, and m y designs l, m, and n of Figure 8 have a single strand; Figure 8d has three. 46

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

For patterns with more than one component, we can investigate whether the symmetry group acts transitively on the strings: Can each string be carried onto any other string by some symmetry of the pattern? In the context of layered patterns and fabrics, a pattern which is string-transitive is said to be isonemal. Adopting this terminology, we can say that of the patterns in Figure 8, c and e are not isonemal, and all the others except i and j are isonemal by translation. In cases i and j, rotations are required to achieve complete transitivity. There is a simple test to check whether an interlaced frieze pattern is isonemal. Construct the quotient link by joining the two ends of a fundamental region of the frieze together. If this quotient link has a single component, then the frieze is isonemal by translation. Another problem arising in the mathematical study of fabrics is that of determining whether a layered pattern falls apart: Can the strings be separated into two or more sets which are not interlinked? We assumed above that friezes are connected. One consequence of this is that Celtic interlaced friezes never fall apart. If an interlaced frieze is alternating, connected, and separable, then so is the quotient link constructed from it. However, alternating diagrams of links represent split links if and only if they are not connected [4].

A Finer Classification

Classifying the multitude of Celtic interlaced patterns into only ten classes is, in some respects, not very satisfactory especially w h e n we realise that the resulting three-dimensional symmetry type is completely determined by the underlying two-dimensional pattern of break-markers. It would be nice to have some kind of classification by pattern type [3] rather than merely by symmetry type. Intuitively, a pattern is a collection of motifs arranged in a systematic fashion. This regularity is modelled mathematically by requiring that the symmetry group of the pattern acts transitively on the motifs. Classification by pattern type depends on three factors: the symmetry group G of the pattern; the stabiliser

stabG(M) of a motif M; and the set of motif transitive subgroups of G. Two patterns are said to have the same pattern type if all these features coincide. When we try to apply this kind of analysis to Celtic friezes, however, we immediately run into difficulties: The patterns are not discrete, so there is no obvious or natural way to split them up into motifs. The continuity of the strings makes it impossible to choose a motif in an unambiguous way, and the choice made will affect the resulting pattern type. Ironically, the arrangement of break-markers associated with an interlaced frieze pattern is discrete but not necessarily transitive.

Coda In this study of Celtic knotwork I have concentrated on one particular theme: symmetry. That an analysis in terms of symmetries is possible is due partly to the lattice structure underlying the construction of the designs. This inbuilt regularity and the imposition of periodicity by the artist means that many of the patterns have nontrivial symmetry. The reader may feel that this same rigidity would lead to a dull and sterile art form. A nonmathematician confronted with the mathematical classification of patterns according to their symmetry type wrote [2, p. 70], There is no danger that the resources of the pattern maker will be exhausted by the constraints of geometry. The remark seems appropriate in this context, too. A glance at any of the illuminated manuscripts produced by Celtic scribes will easily convince you that a geometric framework in no way hinders the artist. There is still room for imagination and creativity to express themselves.

I. Bain, Celtic Knotwork, London: Constable (1986). A. Meehan, Celtic Design: knotwork, London: Thames and Hudson (1991). Related Topics H. Arneberg, Norwegian Peasant Art: men's handicrafts, Oslo: Fabritius & Son (1951). K. M. Chapman, The Pottery of San Ildefonso Pueblo, School of American Research, monograph 28, Albuquerque: University of New Mexico Press (1970). D. W. Crowe and D. K. Washburn, Groups and geometry in the ceramic art of San Ildefonso, Algebras, Groups and Geometries (2) 3 (1985), 263-277. B. Grfinbaum, Periodic ornamentation of the fabric plane: lessons from Peruvian fabrics. Symmetry I (1990), 48-68. B. Gr~nbaum and G. C. Shephard, The geometry of fabrics, Geometrical Combinatorics (F. C. Holroyd and R.J. Wilson, eds), Pitman (1984), 77-97. B. Grfinbaum and G. C. Shephard, Interlace patterns in Islamic and Moorish art, Leonardo (in press). B. Grfinbaum, Z. Grfinbaum, and G. C. Shephard, Symmetry in Moorish and other ornaments, Comp. & Maths. with Appls., vol 12B, Nos. 3/4 (1986), 641-653. A. Hamilton, The art workmanship of the Maori race in New Zealand, Wellington: New Zealand Institute (1896). I. Hargittai and G. Lengyel, The seven one-dimensional space-group symmetries in Hungarian folk needlework, J. Chem. Educ. 61 (1984), 1033. G. H. Knight, The geometry of Maori art. Part I: rafter patterns, New Zealand Math. Mag. (3) 21 (1984), 36--40. G. H. Knight, The geometry of Maori art. Part 2: weaving patterns, New Zealand Math. Mag. (3) 21 (1984), 80--86. D. K. Washburn and D. W. Crowe, Symmetries of Culture: Theory and Practice of Plane Pattern Analysis, Seattle: University of Washington Press (1988).

Department of Pure Mathematics The University of Liverpool PO Box 147 Liverpool, L69 3BX England

References 1. J. Romilly Allen, Celtic Art in Pagan and Christian Times, London: Methuen (1904). 2. E. H. Gombrich, The Sense of Order: a study in the psychology of decorative art, Ithaca, NY: Cornell University Press (1979). 3. B. Gr~nbaum and G. C. Shephard, Tilings and Patterns, New York: Freeman (1987). 4. W. W. Menasco, Closed incompressible surfaces in alternating knot and link complements. Topology 23 (1984), 37-44. 5. A. V. Shubnikov and V. A. Koptsik, Symmetry in Science and Art (translated from the Russian by G. D. Archard), New York: Plenum (1974).

Further Reading Celtic Knotwork G. Bain, Celtic Art: the methods of construction, London: Constable (1977). THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

47

David Gale* For the general philosophy of this section see Vol. 13, No. 1 (1991). Contributors to this column who wish an acknowledgement of their contributions should enclose a self-addressed postcard.

We devote the column this time to some recent results on a pair of fairly well-known problems of recreational mathematics that have been around for quite a while. The first is the problem of tiling surfaces by unequal squares, the second that of devising fair procedures for dividing a cake. The results on tiling are rather definitive, whereas the work on cake-cutting is still in a rather formative stage.

Tiling of Surfaces by Unequal Squares The question is, or rather was, which rectangles can be tiled by squares no two of which have the same size.

Figure 1 is an example of a 32 x 33 rectangle which is tiled by 9 such squares. This example, apparently discovered by Moron in 1925, appears in Ball's Mathematical Recreations and Steinhaus's Mathematical Snapshots. In 1940, Tutte, Brooks, Smith, and Stone (Duke Math J. 7 (1940), 312-340) were able to show that this is the "smallest" such example, meaning that no rectangle can be tiled in this way by fewer than 9 squares. They also showed, however, that there is exactly one other rectangle, 61 x 69, shown in Figure 2, which can also be tiled by 9 squares. The authors were actually seeking and eventually found a square which could be tiled in this way. For an entertaining exposition, see the chapter by Tutte, "Squaring the Square," in Martin

Figure 1 * C o l u m n e d i t o r ' s a d d r e s s : Department of Mathematics, University of California, Berkeley, CA 94720 USA. 48

Figure 2

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 9 1993 Springer-Veflag New York

Figure 3

Gardner's second Scientific American Book of Puzzles and Diversions, Simon and Schuster, 1961. Now, such a "squaring" of a rectangle can be converted in a trivial w a y to a squaring of the cylinder, torus, M6bius strip, or Klein bottle by the usual identification of opposite sides, but there are also nontrivial squarings of these other surfaces, even simple squarings, meaning squarings in which there is no subset of tiles whose union is a rectangle. Until recently, however, it was not known whether there might be squarings of these surfaces requiring fewer than 9 squares. Then, in 1991, Bracewell found a squaring of the M6bius strip using only 8 squares. Very recently the question has been completely settled by S. J. Chapman. Perhaps the simplest but most surprising result is that a 1 x 5 M6bius strip can be tiled by 2 squares, as becomes obvious from Figure 3. To accommodate this example, one must extend the notion of a tiling to allow the mapping of the squares into the surface to self-intersect on their boundaries. Chapman shows that there are no 3- or 4-squarings of the strip but there is a unique 5-squaring (Fig. 4). For cylinders, the situation is interesting. Again it turns out that 9 squares are necessary. There are exactly two nontrivial 9-squarings of the cylinder, and these use exactly the squares of Figures I and 2 but in a different arrangement. The tiling corresponding to Figure 1 is shown in Figure 5. Note, for example, that the squares of size 10 and 15 are disjoint in the rectangle but they are contiguous on the cylinder. The cases considered so far involve surfaces with boundary, which forces one to orient the squares with one side parallel to the boundary. This is no longer the case with the torus and Klein bottle. If one allows arbitrary orientation, then, in fact, any two squares can tile some torus. Namely, let the squares have sides a and b and consider the torus obtained from identifying opposite sides of a square of side c, where c2 = a 2 + b2. Figure 6 shows h o w to do it and at the same time provides a new (?) proof of the Pythagorean Theorem. A more symmetrical representation is given in Figure 7. If one allows only tiles which are parallel to the sides of the square, then it turns out there are no nontrivial 9-squarings of the torus. Any squaring of the M6bius strip gives a squaring of the Klein bottle. For 6 or fewer tiles these are the only ones, but in the case of 7 or 8 tiles this is not known. Also it is not known whether there are tilings of the Klein bottle in which the tiles need not be parallel to the sides of the big square.

Figure 4

Figure 5

Figure 6 THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

49

Figure 7 Chapman's techniques for these problems are quite different from and simpler than those of Tutte, et al. and depend on a clever encoding of filings by matrices of O's, l's, and - l ' s .

D i v i d i n g a Cake A cake is to be divided between n of us. We have different tastes. Some of us like the frosting, others are partial to the chocolate filling, etc. Is there a way of giving each of us a piece of the cake such that every one feels he or she has gotten as desirable a piece as anyone else (such an allocation of pieces is said to be envy-free)? Well, it depends. First, the cake must not be too lumpy. If all of us have our hearts set on getting the cherry in the middle, then it is hopeless unless the cherry can be split up somehow among us. This key property, that any piece can be split up into smaller pieces, corresponds to the idea that our tastes are represented by so-called "atomless" measures, countably additive, etc., etc. In this model, if by a piece one means any measurable subset, then there is a very strong existence result. Not only is there an envy-free allocation, but there is one in which we all believe that everyone, ourselves included, got exactly one nth of the cake. Otherwise stated, there is a w a y of cutting the cake into n pieces so that we are all indifferent as to which piece we get. They all look equally delicious. This fact proved by Dubins and Spanier (1961) is a consequence of a celebrated and moderately highpowered theorem of Lyapunov which says that the range of a vector measure is convex. N o w as a practical matter, arbitrary measurable pieces of cake may not be so easy to come by. A more 50

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

down-to-earth model, therefore, has been treated by Stromquist (1980), where the cake may be taken to be an interval and the pieces are required to be subintervals. Perhaps a loaf of bread is a more apt illustration for this case. Using a fixed-point theorem, it is shown that envy-free allocations will always exist. Fixed-point theorems, however, are notoriously nonconstructive, and Stromquist's result gives no indication of h o w one might arrive at the desired culinary dissection. A rather different approach to the problem asks not just for the existence of envy-free allocations but for a procedure, or a protocol as we shall call it, which leads to such an allocation. The prototypical example is the procedure for the trivial two-person case where one of us divides the cake into two parts and the other chooses the part he prefers. This method has the obviously desirable property that if either of us ends up feeling he has been gypped, he has only himself to blame. It has long been an open problem to try to devise protocols with this property for the n-person case. The best result along these lines is an elegant three-person protocol due to John Selfridge which will n o w be described. We denote the players by #1, #2, #3.

Three-Person Protocol Step I: #1 "trisects" the cake into 3 parts equally acceptable to him.

If # 2 and # 3 prefer different pieces, we are through. Otherwise, say they both prefer A and # 2 prefers A to B which she likes at least as much as C. Thus,

Step II: # 2 trims a "sliver" (S) from A leaving A' so that A' and B are equally acceptable to her.

Step III: # 3 chooses his preferred piece among A', B, and C. Case 1. # 3 chooses A'. Then # 2 chooses B and #1 gets C (no envy so far). It remains to divide up the sliver which is like the original problem, except that n o w #1 will not be envious even if # 3 gets the whole sliver. Step IV: #2 trisects S. Step V: # 3 chooses, then #1 chooses, then #2.

Case//. #3 does not choose A'. Then #2 gets A' and the procedure is as before, except this time #3 trisects and #2 chooses first. This procedure has a number of nice properties. First, it is economical, requiring at most 5 cuts. Further, like the I-cut-you-choose protocol, it makes minimal assumptions on what the players are able to do; namely, (1) given any piece and an integer k, it is assumed that a player can divide the piece into k subpieces equally acceptable to him, and (2) if a player prefers one piece to another, she can trim off part of the first piece in such a way that what is left and the second piece are equally acceptable to her. Finally, preferences are required to be only weakly additive, meaning that if A, B, and X, Y are disjoint pieces and a player prefers A to X and B to Y, then he also prefers AUBtoXUY. Up to now, no protocol satisfying the desired conditions is known, even for the case of four players. However, recent work by Steven Brams and Alan Taylor seems to indicate that some progress is being made. The authors present what they call a finite algorithm for arriving at an envy-free allocation. Their procedure, however, is quite complicated and seems to require that players be able to measure numerically the value of any piece of cake. Further, even for the four-player case, there is no a priori upper bound on the number of cuts which may be required. Thus, for example, if the value of piece A to some player is greater than that of piece B by one part in a million, then it may require a million cuts to arrive at the desired allocation using the proposed algorithm. One might hope that procedures of simplicity comparable to that of the Selfridge protocol could be devised for the general case. As this is being written, however, the new work is still at the early (preprint) stages, and perhaps substantial simplifications will be found in the course of time.

pieces they strictly prefer. Obviously, it would be desirable for the final allocation to be undominated as well as envy-free. A general question, then, is whether in a given model it is always possible to satisfy both of these conditions. In this connection, recall that in the Stromquist formulation all pieces were required to be subintervals of an interval (unlike the earlier example in which m y allocation was the union of two disjoint intervals). For these Stromquist allocations, we have, in fact, THEOREM. An envy-free Stromquist allocation is automatically undominated.

Proof. Let P be an envy-free partition of the interval into n subintervals and let Q be any other such n-partition. Now, if P and Q are distinct n-partitions of an interval, then there must be some interval I of P which strictly contains some interval J of Q (think about it for a minute). But then whoever gets J in the allocation Q will not be strictly better off than she was under P, for she likes I at least as well as J and she likes the piece she got under P at least as well as I since P was envyfree. Q.E.D. Which brings us to the problem of the pie. Suppose a pie is to be divided among three people and the pieces are required to be traditional pie portions, namely, sectors.

D i v i d i n g a Pie: an U n s o l v e d Problem An allocation may be envy-free but have other undesirable properties. As an example, suppose you and I are to divide a loaf of bread which again we will take to be an interval, and suppose the loaf is symmetric about its midpoint in both of our measures. Then if we divide it in two at the midpoint, we have a Spanier-Dubins allocation in which we both agree that each of us got exactly half the cake. Suppose, however, that I like crust, so that I particularly want to get the two ends of the loaf, whereas you prefer not to have these parts. Then each of us would be strictly better off if we trisected the loaf in some way and you took the middle part while I took the two end intervals. In general, we will say an allocation is dominated if there is another allocation which gives all players

Does there necessarily always exist an allocation which is both envy-free and undominated? A d d e n d u m on the Variational M e t h o d There is, of course, an inexhaustible supply of problems that can be solved by variational methods, the subject of the last issue's column, but I missed a lovely two-examples-in-one case which was suggested to me by Clifford Gardner. It has the special virtue that it provides a simple but elegant application of calculus THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 5 1

and would fit in at around the third week of a traditional freshman course. (The NSF has been spending millions in recent years on trying to improve the teaching of calculus, so I am pleased to be able here to contribute my o w n two cents' worth.) Consider the discrete heat-flow problem. Given a graph like the one shown below, where some of the nodes are held at fixed temperatures (3, 5 and - 2 ) ; the laws of heat flow require that the (steady-state) temperature of every remaining node shall satisfy the mean value property, namely, that its temperature shall be the average of the temperatures of the nodes to which it is connected.

Question H o w do we know that such a set of temperatures will always exist, and if so are they unique? (Of course, this is a problem of solving a system of linear equations, but our students will not get to this until their sophomore year.)

Answer Existence: Let t i be the temperature at node i, and consider the function f(t 1. . . . . tn) = E (t i tj)2, summed over all pairs of neighboring nodes (this is the thermal energy of the system); choose values of the t's which minimize this function. To see that these values satisfy the desired condition, note that if the temperatures at all nodes except tk are held fixed at the minimizing values, then tk must minimize f as a function of one variable, and setting the derivative with respect to t k equal to zero gives the result. Ah, you say, but how do we know that the minim u m exists? My answer is that mathematics got along for two thousand years without worrying about such questions and there is no reason to inflict them on freshmen. For those who want to be mathematics majors, there will be time enough when they get to be juniors to force them, kicking and screaming in some cases, to worry about these matters. 52

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

Uniqueness (by the maximum principle!): Suppose there were two sets of temperatures satisfying the mean value property. Then so would their difference, and the difference temperatures at the fixed nodes would be zero. N o w consider a node where this difference temperature is a maximum. Then by the mean value property, all its neighbors must also be at this temperature, and likewise all its neighbors' neighbors, so eventually we will reach one of the fixed-temperature nodes (we assume the graph is connected); so the maximum is zero. Likewise the minimum. Q.E.D.

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 card 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 Mathematical Tourist Editor, Ian Stewart.

A French Officer in Prussian Magdeburg Riidiger Thiele Whatever our search after bygone times, the temporal gap will remain unbridgeable. Spatially it is another matter: We can revisit the scenes of historical events. Both inside and beyond the boundaries of his native country, Lazare Carnot is, today, recognized as one of the "h~ros de I'histoire de France." But has this man of affairs any claim to scientific fame, other than as the father of the famed physicist Sadi Carnot? In his own day there was not the slightest doubt about it. Early on Sunday, 15 September 1822, the philosopher Hegel, w h o was passing through Magdeburg, wrote the following words to his wife: "Further, yesterday afternoon [ saw all there is to be seen h e r e , the famous cathedral 1 (not particularly impressed). 9. . Of all I have seen, nothing exceeds in significance

General Carnot, a charming old gentleman, and a Frenchman, the celebrated Carnot: he took it kindly that I visited him." But it was not merely Carnot the man of affairs to whom Hegel paid his respects: He was also fully aware of Carnot the mathematician, as a quotation from his work Wissenschafl der Logik will show: "The elucidations of Carnot on the methods of infinite quantities are the very quintessence, and that

1 Several times Leonhard Euler (1707-1783) took Magdeburg and its Cathedral as subject matter w h e n he composed instructional letters for the daughter of the Margrave of Brandenburg-Schwedt, subsequently published as Lettres ~ u n e princesse d ' A l l e m a g n e . . . (17681772). During the Seven Years' War, the Court of Prussia took up quarters in the fortified city of Magdeburg. In a letter dated 27 August 1760, Euler posed the question as to whether a straight line, drawn from the rooms of the Princess in Berlin to her present quarters in Magdeburg, would be horizontal or inclined. Euler's argument was this: Berlin is situated on the Spree, which flows into the Havel, and the Havel flows into the Elbe. But Magdeburg lies on the Elbe, and therefore Berlin, on the Spree, must be situated higher than Magdeburg, and, at best, the top of the Cathedral towers would be on a horizontal line with the rooms in Berlin. Unfortunately, Euler forgot to take into consideration the considerable distance of Magdeburg above (not below) the point where the Have1 joins with the Etbe, and this although he himself published a Geographischer A t l a s containing a map which would make this abundantly dear. * Column Editor's address: Mathematics Institute, University of Warwick, Coventry, CV4 7AL England.

F i g u r e 1. Lazare N i c o l a s Marguerite C a r n o t (1753--1823).

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1 9 1993Springer-VerlagNew York 53

s.,.

tk,'m.%, ti.)m

~" ,7| ;.,dp~;,.~' "~?~,~'~,-*'~ L~~'~--*~- r

',,,t:, ,t L-ak.,. Lat,.,,-

~+.

."~'

Figure 2. Title-page of the competition essay Dissertation s u r la th~orie de l'infini math~matique of 1785, Carnot's entry for a prize offered by the Berlin Academy.

most clearly expounded, of what has been accomplished in the aforementioned [i.e., the derivation of the differential]" (Book 1, Section 2). Lazare Carnot lived an eventful life in eventful times. His career began as an officer of engineers, specializing in fortifications; he achieved fame in the defense of his country, yet twice had to flee the country for his staunch republican stance, being proscribed in 1815 by the Restoration (see Chronological Table). It thus came about that toward the close of his life the one-time French officer found refuge in the land of his former adversaries, the Prussians. Carnot arrived in Magdeburg on 3 November 1816. The Magdeburg of those days was the most important fortified city within Prussia, and, like Potsdam, a gathering point for Huguenots who had emigrated to Prussia. According to Carnot's second son, Hippolyte, it was the marks left by French life in Magdeburg, under Napoleon from 1806 to 1813 the chief town of a d~partement, that was the determining factor in Carnot's choice of his place of exile: first residing in the "King of Prussia" Inn, in Leiterstrasse (proceeding toward the Cathedral, only 5 minutes away from the present railw a y station; Leiterstrasse suffered severe war damage and was completely rebuilt some years back), from 1817, lodging at the house of a carrier, then at No. 15 Grosse Schulstrasse, one-time posting inn. This is now the part of Julius Bremer Strasse between Breiter Weg and Otto von Guericke Strasse; this section begins not far from the side of Alter Markt away from the river and proceeds roughly toward the railway station, approximately 5 to 10 minutes away. The quarter was almost completely destroyed in the war, with the result that Carnot's house is no longer extant. Across partly unbuilt land, one can see what was Otto von 54 THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

~o..~a,.;~'J~..~.~:o~

~'""~V"~ ; ' " ~ "

t)

'

i

~ - 4

~

o ,,. ~ ~r96. ~<".~','S'~fi.

"~-

~";>

"~"~'*~ / ~ o l .

'~"

9. ~'g~.~. .... ~ . . . . . . . . .

,

-

-

i

_

, ,F

'

~

'

"-~

,

9

~: ~-t ~':'

* "

O

ol

- -

Figure 3. Extracts from a letter written by Carnot to his German biographer W. Korte, dated 16 June 1819. (Courtesy of Universit~its- und L a n d e s b i b l i o t h e k Sachsen-Anhalt, Halle).

Guericke's house in Grosse MLinzstrasse, now housing the Savings Bank. Ffirstenwall, above the casemate immediately alongside the Cathedral (now unnamed, it runs directly beside the street Auf Dem FfirstenwaU from the Cathedral to the present seat of government) was in Carnot's day the only public walk in the fortified city of Magdeburg, and thus became the scene of Carnot's afternoon walk. To this day, from this point there is a charming view of the Elbe. Carnot lived a frugal and secluded life in Magdeburg, but this should not be taken to mean that he was idle during this time. Carnot, a Roman Catholic, died on 2 August 1823 and, by order of the King of Prussia, was interred in the Protestant churchyard of St. John in underground vaults. The ruins of St. John's Church can be seen a short distance away from Alter Markt in the direction of the river. It is possible to go up the tower. In 1832, his remains were reinterred in the Nordfriedhof cemetery (not far from the Technical University, and today a park, Nordpark, in which there is a memorial to Carnot, see photograph), and finally, on the anniversary of his death in 1889, on the order of the French National Assembly, his mortal remains were buried with military honors in the Pantheon in Paris.

Magdeburgische

Figure 5. Artist's impression of Carnot's former grave in the cemetery Nordfriedhof (now Nordpark), from the Magdeburgische Zeitung, 29 June 1889.

In 1821, Carnot was visited in exile for a few months by his son Sadi. Sadi had quit military service in 1819 and had begun the study of science and technical processes in fruitful dialogue with Nicolas Cl6mentDesormes. Carnot p6re, a trained engineer and always interested in engineering, had more recently turned to

the steam engine (the first steam engine in Magdeburg, 1818). Sadi Carnot had e n c o u n t e r e d British steam engines after the Napoleonic Wars and noted how far French engineers lagged behind in this sphere. We have no evidence of it, but it is easy to imagine father and son, in those Magdeburg days, deep in dis-

Figure 4. Report of Carnot's death from the Zeitung of 7 August 1823.

Figure 6. Ceremonial return of Carnot's mortal remains to Paris, 4 August 1889. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 5 5

Figure 7. View of Magdeburg across the Elbe, showing the Cathedral and Fiirstenwall (Photo: K. Haase).

cussion as to how to design good steam engines, and in this w a y acquiring an insight into the technology of thermodynamics (Carnot cycle). Be that as it may, Sadi Carnot's celebrated Rf'flexions sur la puissance motrice du f e u . . , appeared in 1824, a work which, for the sake of a general overview, disregards mechanical detail, quite in the style of the father. Lazare Carnot was a man of the transition period, and thus not to be neatly labeled. He was a decided opponent of the Ancien R~gime, a sincere republican, and by virtue of his public activities an extremely influential figure in the politics of science; he was not, however, typical of the revolution in the natural sciences, for he still had one foot in the old w a y of thought. Yet he represented the mathematico-physical awareness of his time; some of Cauchy's definitions remind one of the wording in Carnot. As an engineer Carnot was a pragmatist; the philosophical skepticism of a d'Alembert or a Lagrange was foreign to him. His Rdflexions sur la mdtaphysique du calcul infinitesimal (1797) was introduced with the words: "As however everything indicates that there will be a new turn in the culture of mathematics, he [Carnot] deems it apposite to publish this m o n o g r a p h . . . " (Avertissement). The traditional in Carnot's w a y of mathematical thinking is revealed in his adherence to the intuitive concept of quantity. Quantities are what vary continuously (understood in a dynamic sense). He does not treat functions, already introduced into analysis as a pivotal concept by Euler, but equations. As an engineer Carnot accepted mathematical expressions only insofar as the quantities contained in them were real and the operations involved held meaning: "Every quantity is a real object such that the mind can grasp it or at least its representation in calculation" (G~omdtrie de position, 1803, p. 7). From this proceed differences from our present-day view: to Carnot, negative quantities are impossible, and zero, just like infinity, is a limit. Negative quantities are "'chimeras" or "hieroglyphics of analysis." (Champollion deciphered Egyptian hieroglyphics in 1822; Carnot's image was thus much more forceful than it would be nowadays.) In contrast to this, infinitely small quantities are real objects, being representable, as differences between limits and values approaching them, etc. As differences of real quantities, they are themselves real. At the same

Figure 8. Memorial to Carnot in Nordpark (formerly the cemetery Nordfriedhof) by H. Apel, 1989. The plinth symbolizes French history as experienced by Camot. The periods are distinguished by the appropriate symbol of sovereignty: the Bourbon fleur-de-lis; the Revolutionary cockade; the Napoleonic "N"; and the symbol of the French Republic. The Revolutionary Period from 1789, the Napoleonic Period, and the Bourbon Restoration are additionally symbolized in the "slices" obtruding from the main shaft of the plinth (Photos: K. Haase). 56

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

time, infinitesimal quantities do not provide a clear mental picture, they are intellectual constructions, des ~tres de raison, but not thereby devoid of sense. In his Essai sur les machines en gdndral . . . . 1783, Carnot had dealt with an area of engineering in which virtual and real displacement are fundamental. It is on such finite variations in quantity in mechanics and geometry that Carnot's conviction rests, which he carries over into infinitesimal analysis. Hence, one can regard his founding of analysis as being based on engineering. The fusion of concepts of mechanics and geometry led Carnot into pure kinematics. Gdomdtrie de position seeks to prove that operations carried out on real quantities cannot produce ratiocinations which are devoid of content. For this proof, Carnot introduced the concept of the correlation of geometric systems. For example, the displacement of a geometric system by insensible degrees will still preserve the correlation, as in the transition from a secant to the limiting tangent.

For Carnot, it was as difficult to explain a limit as it was to explain the concept of an infinitely small quantity. To render calculation easier, infinitesimal calculus employs the infinitely small quantity; classical analysis employs the limit. Carnot pointed out that the various foundations of analysis are based solely on various applications of the principle he employed of undetermined coefficients. It is wrong to suggest that Carnot was a protagonist of the theory of the compensation of errors. A comparison of Carnot's theory with nonstandard analysis makes this apparent. It shows Carnot's supposed "compensation of errors" to be nothing other than the entry into and exit from the domain *R of the hyperreal numbers in nonstandard analysis.

Johannes Gutenberg-Universit~t Mainz Fachbereich 17-Mathematik Postfach 3980, Saarstrasse 21 D-6500 Mainz, Germany

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993 5 7

Imperial Cuboctahedron Istvlin Hargittai

On a recent (April, 1992) Visiting Professorship in Japan, sponsored by the Japan Society for the Promotion of Science (JSPS), I was fortunate to have the opportunity to visit the Katsura Imperial Villa and the Shugakuin Imperial Villa in Kyoto. Only small groups of visitors are admitted to these villas at appointed times with special permits arranged in advance from the Imperial Household Authority. Katsura, the country villa of the Katsuranomiya line of princes from the beginning of the 16th century, is comprised of the Old Shoin, the Middle Shoin, the Music Room, and the New Palace. It covers an area of 17 acres. The garden surrounding the villa itself contains four tea houses named Shokin-tei (Harp and pine pavilion), Shoka-tei (Pavilion for appreciating flowers), Shoi-ken (Hut of smiling thoughts), and Geppa-ro (Moon waves pavilion). The stroll-type garden was the first of its kind constructed in Japan. The Shugakuin Imperial Villa was constructed 30 years after the Katsura Imperial Villa. It was completed in 1659.

Garden lantern with triangular top, Katsura Imperial Villa. 58

The Shugakuin Imperial Villa is divided into three sections, each containing a tea house--the Upper, Middle, and Lower Villas. There is a mountain at the back of the Upper Villa tea house. The villa covers an area of over 545,000 square meters. The Upper Villa shows the Shugakuin Imperial Villa at its best. At the top of the southeast hill is the Rinuntei tea house commanding a sweeping view of Yokuryu Pond. These Japanese gardens and tea houses are of exquisite beauty. To me the garden lanterns, or toros in Japanese, were especially attractive in these gardens. Such lanterns can also often be found in parks, around shrines and temples and elsewhere. Toros were expensive gifts to the owners of the Imperial Villas from feudal lords who were expected to offer them as token of their loyalty. They were also supposed to deplete the feudal lords' purses, preventing them from becoming too rich. The toros are made of stone, and the geometrical shapes of their tops come in m a n y varieties: triangular,

Garden lantern with square top, Shugakuin Imperial Villa.

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 9 1993 Springer-Veflag New York

Garden lantern with hexagonal top, Shugakuin Imperial Villa.

Garden lantern with hexagonal top, Katsura Imperial Villa.

Garden lantern with round top, Shugakuin Imperial Villa.

square, hexagonal, r o u n d - - a n d often with an additional top decoration, usually of spherical shape. The toros in the Katsura and Shugakuin Villas blend especially nicely with their surroundings. Their positions, natural colors---due partly to the moss on their surface--and their height of about one meter, make them look as if they had grown on the spot. Some examples are shown here. The decoration on the top of one particular toro, in the Shugakuin Villa, is a cuboctahedron, shown also enlarged. According to my expert friends [1] this cuboctahedron toro decoration has not previously been described or noticed. Another cuboctahedron, with the imperial emblem, has been described [2]. It was found on the top of the Rinuntei tea house of the Upper Villa of the Shugakuin Imperial Villa. It is also shown here in a photograph. The meaning of the cuboctahedron in these places is an intriguing question. Its occurrence as a lantern-top decoration might be accidental; but its conspicuous appearance on the top of the Rinuntei tea house, with the imperial emblem, gives it added significance. I hope that one day there will be an answer to this question. All photographs in this paper were taken by the author.

Garden lantern with square top and cuboctahedron top-decoration, Shugakuin Imperial Villa.

Enlarged view of the cuboctahedron top-decoration.

References

1. Private communication from Professor Koji Miyazaki, Kyoto University, April, 1992. 2. K. Miyazaki, Plato and the Five-layered Tower: A Short History of Japanese Culture from the Point of View of Geometry (in Japanese). Jin-mon shoin, Kyoto, 1987. Budapest Technical University Szt. Gell~rt 4 H-1521 Budapest, XI Hungary

Cuboctahedron top decoration of the Rinuntei tea house, Shugakuin Imperial Villa. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 5 9

An American Woman in G6ttingen Betsey S. Whitman

One of the boarding houses May lived in at 19 Burgerstrasse, GOttingen.

The home of the Morgensterne family at 32 Rosdorfer Weg, GOttingen. 60

Mary Frances Winston (later Newson) was the first American woman to earn a Ph.D. in mathematics from a European university. She and Grace Chisholm (from England) arrived independently in G6ttingen, Germany to study with Felix Klein in October 1893. Mary Frances was 24 years old. She had earned an undergraduate degree in mathematics from the University of Wisconsin, had taught for two years, and had studied graduate mathematics for a year at Bryn Mawr with Charlotte Scott, the English head of the mathematics department there, and for a year at the University of Chicago w h e n it first opened in 18921893. Two of her professors at Chicago were from Germany, and they encouraged her when she became interested in applying for a European fellowship to study abroad. The three years she spent in Germany were probably the happiest years of her life, according to her two daughters, Caroline Beshers and Josephine Newson, of Sarasota, Florida. Mary Frances, who was known as May, wrote home about the boarding houses where she stayed, the h o m e of the M o r g e n s t e r n e family w h e r e Grace Chisholm stayed and where she, May, had a standing invitation for Saturday supper, the Auditorium which was the university building where all her classes and seminars were held, and Professor Klein's home where she and the other students of his seminar were invited for dinner once each semester. These places look much the same today as she described them a century ago. Travel to the nearby Harz mountains for long hikes was done on the train, and she and her friends frequently left G6ttingen before dawn. The station at Bad Sachsa at the foot of the Harz mountains looks today as it must have in January 1894 w h e n May and the Morgensternes arrived for a day's hike up the "Ravenskopf." May wrote home,

THE MATHEMATICAL INTELLIGENCER VOL, 15, NO. 1 9 1993 Springer-Verlag New York

The fir trees on the path near the top of the "Ravensberg" (known as the "Ravenskopf'" in 1894) in January, 1992.

The station at Bad Sachsa.

The Auditorium. May wrote, "The lower story of the wing to the left is occupied by the mathematical department."

Klein's home. There is a small marble plaque under the left upstairs window indicating Felix Klein lived here 18861925.

We took the train from G6ttingen and arrived at Bad Sachsa station at the foot of the mountains at quarter of ten . . . . The thermometer stood at about 10~ when we left G6ttingen and I suppose it was somewhat warmer when we got to the station. I felt pretty cold at first. The wind was cold and I had some misgivings as to the comfort of walking in winter time. But by the time we got to the top of the second hill we were warmed up again and did not suffer from the cold at all . . . . The fir trees on both sides were covered heavily with snow, but as yet the road was pretty good . . . . The sun shone very brightly, there was no wind, and altogether we could not have hoped for a better day . . . . We stopped a minute or two and each ate one of the sandwiches which Frau Morgensterne had put up for us. We could not stop long, however, as our feet would get cold. In J a n u a r y 1992, all the signs to the m o u n t a i n p o i n t e d to the " R a v e n s b e r g , " w h e r e , a l t h o u g h the n a m e has c h a n g e d , the sights are the same. Felix Klein established a reading r o o m w i t h journals, m o n o g r a p h s , a n d lecture notes of all lectures, in addition to a r o o m for a collection of m a t h e m a t i c a l m o d e l s for d e m o n s t r a t i n g geometrical p r o b l e m s . T o d a y , the m o d e l s occupy m a n y cases in the second-floor exhibit hall of the M a t h e m a t i c s Institute on Bunsenstrasse. W h e n M a y first s a w t h e m in 1893 d u r i n g her first w e e k in Europe, t h e y w e r e in the " m o d e l s r o o m " of the A u d i t o r i u m . She wrote, " W e m e t Dr. Ritter, Professor Klein's assistant a n d he s h o w e d u s the m o d e l s a n d

One of the many cases full of models now in the mathematical building on Bunsenstrasse.

s o m e of the calculating m a c h i n e s . H e explained t h e m a little a n d I w a s delighted to find that, t h o ' h e s p o k e in G e r m a n , I u n d e r s t o o d e v e r y w o r d h e said . . . . I do n o t think I a m going to h a v e a n y serious trouble with the language." A favorite s p o t for s u m m e r w e e k e n d s w a s the Th~iringen Forest w h i c h is p a r t of the f o r m e r East Germ a n y . The Wartburg, n e a r Eisenach in the Th~iringen, THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 6 1

a n d in private automobiles, coming to see the same sights May described a c e n t u r y ago. After M a y finished her degree, Magna C u m Laude, she taught high school for a year and then was app o i n t e d chair of the d e p a r t m e n t of mathematics at Kansas State Agricultural College in Manhattan, Kansas. She resigned that position to m a r r y H e n r y Byron N e w s o n , the acting head of the mathematics departm e n t at Kansas University in Lawrence, in 1900. T h e y h a d three children. After H e n r y died u n e x p e c t e d l y of a heart attack in 1910, May f o u n d a position at Washb u r n College in Topeka and later at Eureka College in Illinois. She taught until she was in her seventies a n d died at age 90 in 1959. References

1. Letters of Mary Frances Winston; copies given to the author by Caroline Newson Beshers; originals in Sophia Smith Archives, Smith College, Northampton, Massachusetts. 2. Personal interviews with Caroline Beshers and Josephine Newson December 1981, January 1987, and May 1992, Sarasota, Florida.

The Wartburg near Eisenach.

is a castle built a b o u t 1080 b y L u d w i g the Jumper. In 1521-1522 Martin Luther, while he lived h e r e in hiding from his enemies, c o m p l e t e d the translation of the N e w T e s t a m e n t into German. May w r o t e o n July 8, 1895, It was hot and uncomfortable last week so I yielded to the temptation to throw my work to the winds and join a party for a couple of days in Th/iringen . . . . (We) left GOttingen at 4 o'clock Saturday morning for Eisenach . . . . and got to Eisenach at nine. We hunted up a restaurant first and got something to eat and then went up to the Wartburg. I think I wrote of my trip to the Wartburg from Georgenthal last fall. It was just the same Wartburg, the same Luther's room with the table on which he is said to have translated the Bible, the same spot where the lathing is exposed by the people who have torn off the plaster and carried the ink-spot away, the same old oak bed-stead and the portraits of two very uninteresting old people who were introduced as Luther's parents and above all (that which interested me about as much as anything) the same man with the child-like face and long black beard who waited conscientiously until the whole party was in the room, placed himself with his back to the wall or some other firm support, cast his eyes to some spot in the floor and recited in a clear voice with a regular sing-song--his little piece. 9. . In several places I could have supplied the rest of the sentence if he had happened to forget it. He was undoubtedly 'the right man in the right place' however, and the rest could not see anything funny about him at all! In January 1992, o n a Saturday afternoon, the Wartb u r g was c r o w d e d with tourists, arriving in tour buses 62

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

Department of Mathematics Framingham State College Framingham, MA 01701-9101 USA

Print of General Bourbaki

The above old print, depicting "'Le G~n~ral Bourbaki, Comm a n d a n t de la le Division d'infanterie du 3e corps de l'Arm~e d'Italie" was spotted on the w a l l of a relative. (Thanks to Stefano L. Paveri-Fontana.)

Visualizing Toral Automorphisms Matthew Grayson, Bruce Kitchens, and George Zettler

The two-dimensional toms can be thought of as the unit square in ~2 with opposite edges identified, (0, y)

(1, y ) a n d (x, 0) - (x, 1). It is a group, with addition modulo I as the operation. A group automorphism can be defined by a 2 x 2 integer matrix with determinant +--1. Such a matrix maps the unit square in ~2 to a parallelogram with area one. When projected back to the unit square, by reduction modulo 1, the identifications for the toms are preserved. The following example is with the matrix

automorphism. The surprise is the speed at which the pieces of the partition are mixed. To understand the figures, observe that in the first figure the yellow region wraps around the toms once in the x direction and no times in the y direction, abbreviated (1, 0). In the second figure the yellow region wraps (2, 1) times. Then there are (5, 3), (13, 8), (34, 21), and finally (89, 55) wraps. These are succes-

The converse is also true: Any continuous automorphism of the torus is defined by such a matrix. The group GL(2, Z) can be identified with the group of continuous automorphisms of the toms. The figures were obtained by partitioning the toms using two colors and then applying the automorphism defined by the matrix in the example. The first figure is of the toms with the original partition. The second figure shows the image of the partition after the automorphism has been applied to it. The third figure shows the partition after two iterations of the automorphism, and so on until the sixth figure, which shows the image of the partition after five iterations of the THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 9 1993 Springer-Verlag New York 6 3

sive pairs of the Fibonacci numbers. The largest eigenvalue of the matrix is the square of the Golden Mean, (1 + V5)/2. Toral automorphisms provide examples of many types of dynamic behavior. The n-dimensional toms, T", is R n modulo Z n. The topology is the quotient topology. The differentiable structure and metric are inherited from ~". It is a compact topological group, and GL(n, Z) is identified with the group of continuous automorphisms. Lebesgue measure on R" projects to 64

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. I, 1993

Haar measure on the toms, and it is preserved by each automorphism. A measure-preserving transformation is ergodicif the only invariant sets have measure zero or one. A toral automorphism is ergodic if and only if it has no eigenvalues that are roots of unity [1]. In fact, every ergodic toral automorphism is measure-theoretically conjugate to a Bernoulli shift [2]. A measure-preserving transformation is mixing if for every pair of measurable sets, U and V, p,(U f3 T~(V))

---* ~(U)~(V) as n ---* ~. The property of mixing is stronger than ergodicity but weaker than being isomorphic to a Bernoulli shift. A two-dimensional ergodic toral automorphism can be seen, geometrically, to be mixing. If T E GL(2, Z) and is ergodic, then it has two real eigenvalues, ~ with I)~l > 1 and K = -+1/~. They are irrational algebraic integers. In ~2, T has corresponding eigenvectors, u for ;~ and v for K, both with irrational slope. The lines they determine in R 2 project to geodesics on ~-2 that are uniformly distributed [3]. Choose a small parallelogram, ~, on -r with sides of l e n g t h , parallel to the projection of u and v.

/J

/J

The image of ~ under T is another parallelogram of the same area but with sides of length I),le and IKI~, again parallel to u and v. For large n, the image of under T" will be a long thin parallelogram wrapped around the torus, approximating a section of the geodesic determined by u. The sides will have length I~1"~ and Inl"e. As n gets large, the image will be more and more uniformly distributed on the torus. This shows w h y the automorphism is mixing and explains the uniform stretching and shrinking that can be observed in the figures. A homeomorphism, T, of a metric space is expansive if there exists an ~ > 0 so that for any two points x y, there is an n E Z with d(T"x, T~y) I> e. A toral automorphism is expansive if and only if it has no eigenvalues of modulus 1 [4]. There are automorphisms of the torus that are ergodic but not expansive. The first ones occur in dimension 4. A diffeomorphism of a manifold is hyperbolic if for every point, x, there is a neighborhood that can be written as the product of an expanding and a contracting set. The contracting set is the set of points that are asymptotic to x in positive time, i.e., ~ : d(T~x, T"y) --~ 0 as n ~ oo}. The expanding set is the set of points that are asymptotic to x in negative time, i.e., {y : d(T~x, T~y) ~ 0 as n ~ -o0}. On the two-dimensional torus, these sets are translations of the contracting and expanding eigenlines. The expansive toral automorphisms are exactly the hyperbolic ones. Hyperbolic toral automorphisms exhibit many important types of dynamical behavior. They are where a number of properties of hyperbolic systems were first observed. The periodic points of a hyperbolic toral automorphism are dense; they are exactly the points with rational coordinates. Hyperbolic toral automorphisms are structurally stable [5]. Markov partitions for invert-

ible m a p s w e r e first c o n s t r u c t e d on the t w o dimensional torus [6, 7]. Topological Markov chains and topological entropy were also first used to classify smooth systems on the two-dimensional torus [7]. Hyperbolic toral automorphisms also exhibit topological rigidity, that is, any topological conjugacy must be essentially an algebraic one [8]. Automorphisms of the torus provide simple, concrete examples of many types of complex dynamic behavior. They are discussed in most elementary books on dynamics. They even provide beautiful pictures. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 6 5

Intelligent Choices for Mathematics Applied Chaos Theory A Paradigm for Complexity Ali Bulent ~ambel

CONTENTS: Living with Complexity. Meta-Quantification of Complexity. The Anatomy of Systems and Structures. Attractors. Rapid Growth. The Logistic Curve. The Discrete Logistic Equation. The Different Personalities of Entropy. Dimensions and Scaling. Gallery of Monsters. The Diagnostics and Control of Chaos. Discussion Topics. Each chapter has notes and references. November 1992, 264 pp., $49.95 (tentative)/ISBN: 0-12-155940-8

Evolutionary Art and Computers Stephen Todd and William Latham This book covers

Art, sculpture, modern art, and systems art 9 Mathematics, geometry, fractals, and chaos 9 virtualreality, and artificial life 9 Computer graphics, 3D modeling, computer rendering, and computer languages for art

9

September 1992, c. 288 pp., $59.95 ISBN: 0-12-437185-X

Order from your local bookseller or directly from

O

Fractals Everywhere SECOND EDITION

A C A D E M I C PRESS

Michael Barnsley

This vOlume is the revised Second Edition of the highly successful Fractals Everywhere, published by Academic Press in 1988. The Second Edition in-

HBJ Order Fulfillment Dept. #17915 6277 Sea Harbor Drive, Orlando, FL 32887 CALL TOLL FREE

cludes additional problems and tools emphasizing fractal applications, as well as an all new answer key to the text exercises, all of which make it the most complete and up-to-date fractal textbook available.

1-800-321-5068 FAX 1 - 8 0 0 - 3 3 6 - 7 3 7 7 Prices subject to change without notice. 9 1992 by Academic Press, Inc. All Rights Reserved.

January 1993, c. 550 pp., $49.95 (tentative)/ISBN: 0-12-079061-0

SL/CEP/WR - - 06122

References 1. P. Halmos, Lectures on Ergodic Theory, Chelsea Publishing Co., New York, 1956. 2. Y. Katznelson, Ergodic automorphisms of 1-" are Bernoulli, Israel J. Math. 10 (1971), 186-195. 3. H. Weyl, Ober die Gleichverteiling yon Zahlen mod. Eins, Math. Ann. 77 (1916), 313-352. 4. W. Reddy, The existence of expansive homeomorphisms on manifolds, Duke Math. Jour. 32 (1965), 627-632. 5. D. V. Anosov, Roughness of geodesic flows on compact Riemannian manifolds of negative curvature, Sov. Math. Dokl. 3 (1962), 1068-1070. 6. K. Berg, On the conjugacy problem for K-systems, Ph.D. Thesis, University of Minnesota, Minneapolis, 1967. 7. R. Adler and B. Weiss, Similarity of automorphisms of the toms, Mem. AMS 98 (1970). 8. R. Adler and R. Palais, Homeomorphic conjugacy of automorphisms on the toms, Proc. A M S 16 (1965), 12211225. Mathematical Sciences Department IBM T. J. Watson Research Center Yorktown Heights, N Y 10598 USA Mathematical Sciences Department IBM T. J. Watson Research Center Yorktown Heights, N Y 10598 USA Mathematics Department Columbia University New York, N Y 10027 USA 66

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1, 1993

Jet Wimp*

When Time Breaks Down: The Three-Dimensional Dynamics of Electrochemical Waves and Cardiac Arrhythmias by Arthur T. Winfree Princeton, NJ: Princeton University Press, 1987. 384 pp., Hardcover, US $65.00, softcover, US $19.95 (ISBN 0-691-02402-2)

The Geometry of Biological Time by Arthur T. Winfree N e w York: Springer-Verlag, 1990. 530 pp., softcover, US $32.00 (ISBN 0-387-52528-9)

Reviewed by Leon Glass But living materials are diverse in ways that often defy the mathematics evolved for doing physics and thus in those terms seem imprecise and unanalyzable. Biologists have recently recovered from this illusion in many ways. The way of particular pertinence here is the recognition that there are modes of mathematics--of "'reasoning with symbols"---other than the ones that make living organisms look imprecise. The topological mode offers special promise. It is this mode--indeed one tiny theorem in one part of this mode--that is celebrated here. Take note that this book remains tightly focused on experimental biology and chemistry. There will be no explicit mathematics. There is almost none behind the scenes either; the kinds of topology involved really boil down to little more than geometric intuition applied with patient tenacity. --A. T. Winfree 1987

In the late 1960s Art Winfree, a graduate student in biology at Princeton University, was studying the effects of light on the circadian rhythm in fruit flies, a biological rhythm of about 24 hours. To understand the experimental results, he found it necessary to develop a novel mathematical construct, that of a phase singularity. He realized that phase singularities not only were important in his experiments with fruit flies but also might arise in many other settings. Now, a generation later, hundreds of theoretical and experi-

* Column Editor's address: D e p a r t m e n t U n i v e r s i t y , P h i l a d e l p h i a , P A 19104 USA.

of M a t h e m a t i c s ,

Drexel

mental papers have proved phase singularities to be a perdurable research topic. The Geometry of Biological Time (GBT) and When Time Breaks Down (WTBD) are books of stunning beauty and originality. In these books, Winfree describes h o w phase singularities can be observed either directly or indirectly by a variety of cunning experiments. The modest disclaimer that there is little mathematics here must not be taken literally. These books are gold mines of mathematical ideas. It is true that hard-nosed mathematicians who are comfortable only with lemmatheorem-proof expositions will not be h a p p y with Winfree's chatty style. At the other extreme, biologists with little mathematical inclination will be befuddled by the subtle geometrical notions. Nevertheless, anyone with a curiosity about phenomenology in the natural sciences--and how it can be described with mathematics--will enjoy them greatly. The w a y that I find easiest to explain what phase singularities are is to start with nonlinear oscillations. The phase of an oscillator is a measure of the time since the last occurrence of some marker event of the oscillation. The marker event might be, for example, waking up, the contraction of the heart, or an excitation in a neuron. One usually normalizes the phase to the intrinsic cycle length of the oscillator and often uses a point of a circle to represent it. Differential equations serve as the most common theoretical models of biological oscillators. If one requires n variables to describe the oscillator, the state space then is n-dimensional, and the values of the variables as the oscillation evolves lie on a closed curve. Using the definition of phase above, we consider the phase to vary from 0 to 1 along the closed curve. We associate the values of 0 and 1 with the phase of the marker event. One also can define phase for values of variables that do not lie on the cycle. Assume that the cycle is locally stable and all points in its neighborhood asymptotically approach it. We say that two initial conditions lie on the same isochron if the time evolution with an initial condition starting at either of the points is identical for long times. The isochrons end at a single point or set of points and this is the phase singularity,

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1 9 1993 Springer-Verlag New York 67

!

!

Figure 1. Isochrons ending at a phase singularity. (Adapted from The Geometry of Biological Time (GBT).)

see Figure 1. More generally, the term phase singularity refers to a locus of points where the phase is undefined [1]. How can this picture be translated into predictions about the results of experimental manipulations? The simplest concept to explore experimentally is the phase resetting of biological oscillations. One can perturb any biological r h y t h m provided one has an appropriate stimulus. As examples: for the daily cycle of waking and sleeping, an appropriate stimulus is an exposure to bright light, whereas an electrical shock delivered to the heart alters cardiac rhythm. Following any perturbation, it is possible to measure the timing of subsequent biological events and to compare this with what it would have been in the absence of the stimulus. Research workers have used this protocol countless times to analyze activity in diverse organisms. Winfree shows that to interpret the results it is more relevant to have a grasp of the topology of oscillators sketched out above rather than the biochemistry or neurophysiology of whatever biological oscillator is involved. To see the importance of topological considerations, consider stimulation of a neural oscillator by an electric shock. The experimenter can vary the phase and also the amplitude of the stimulus. For every combination of stimulus, amplitude, and phase, the oscillator will find itself sitting on some isochron. Figure 2 shows the plot of the isochrons as a function of phase and amplitude of the stimulus for a mathematical model of a neural oscillator. Each shade corresponds to a unique phase. The phase singularities end up as black holes. For certain combinations of stimulus, amplitude, and phase, the oscillation will be annihilated, corresponding to the values in the black hole. Phase resetting 68

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

Figure 2. Isochrons for a model of a neural oscillator. (Adapted from WTBD).

using a low-amplitude stimulus is topologically different from phase resetting using a high-amplitude stimulus. In the first case, isochrons go all around the rainbow; in the latter case, they do not. About one-third of each book under review fleshes out this picture and discusses the experiments researchers have devised to test the theory's predictions. Winfree shows how phase singularities can be captured in physical space. The seminal idea here is to imagine a plane filled with oscillators, all of which are in synchrony. Along one axis of the plane are stimuli with graded amplitude; along the orthogonal axis, the stimuli occur at different phases of the cycle. The net result is that different oscillators will be knocked onto different isochrons. The isochrons tell us how the timing of the oscillators evolves. If the oscillator array traps the phase singularity, spiral waves arise. Winfree argues that the trapping of the phase singularity also should be possible in excitable systems. These systems do not spontaneously oscillate, but can support a large excursion from steady state position before returning to steady state. Winfree documents the case with computer simulations as well as with physiological and chemical experiments that show that excitable systems exhibit spiral waves. A recent triu m p h of the theoretical predictions occurred w h e n Davidenko and his co-workers [2], with the aid of volt-

Figure 3. Spiral waves in cardiac tissues. Reproduced from [2] with permission.

age-sensitive fluorescent dyes, observed spiral waves of electrical activity of a small slice of cardiac tissue using stimulation protocols suggested by Winfree's work, Figure 3. Winfree argues that potentially fatal arrhythmias in the intact heart may be associated with spiral waves of activity. However, in the threedimensional heart, it is also possible to have a whole panoply of other exotic geometries that now exist in the memories and graphics of high-speed computers but have not yet been documented in the biological domain; see Figure 4. Winfree has not written his books in a linear fashion. Much of the text is displayed in boxes, and that material develops peripheral points---historical information, anecdotes, or research suggestions. The boxes often point forward or backward to related topics. This gives the books a lively but somewhat disjointed spirit. The subject matter sketched out above forms the backbone of both books, but there are differences. Winfree uses equations sparingly in GBT and not at all in WTBD. GBT has a "bestiary" of examples, which are described in 13 (out of a total 23) chapters. Each of these chapters describes a specific experimental problem. These problems range from the flowering of morning glories to the dynamics of the female ovulatory cycle (deflowering on glorious mornings?), including along the way patterns in slime molds, insect cuticles, and fungi. Winfree has omitted most of the exotic examples from WTBD. Instead, he focuses on the best-developed examples from neurophysiology, cardiology, and chemistry, organizing the material along theoretical lines. The lack of equations in WTBD may simplify the reading for some, but I like to see equations occasionally to help fix ideas. Winfree emphasizes the nonretraction theorem in WTBD, but only refers to it once in GBT. (A version of the theorem occurs in GBT on p. 28 but is not identified as the nonretraction theorem.) This theorem (the "tiny theorem" in the quote heading this review) states that a compact manifold with a boundary cannot be mapped to its boundary by a continuous map that leaves the

boundary pointwise fixed. A beautiful exposition of this theorem and its application to the matters at hand was given by Steve Strogatz in Mathematical Intelligencer in 1985 [3]. Despite citing this theorem, Winfree tries hard to avoid jargon and high falutin' terms and deftnitions. However, more precise definitions and statement of results would help readers who are not in resonance with Winfree's idiosyncratic style. The Springer Study Edition of GBT under review here is essentially a reprinted version of the 1980 edition, which had been out of print for several years. There have been some minor changes in the text, e.g., on p. 153, "separatrix" becomes "separator." Though this book is now over 10 years old, I find it remarkable that the basic ideas were already in place by 1980. Thus, though WTBD contains some new material concerning the playing out of the ideas in chemistry and

Figure 4. A possible geometry for cardiac activity. From C. Henze, A. T. Winfree, Int. J. Bif. Chaos 1, 891-922, 1991. THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

69

cardiology and the structure of w a v e s in threedimensional excitable media, most of the material will be familiar to those w h o have already read GBT. This is not to say that the material is out of date. It is still fresh. Readers of Physical Review Letters will be familiar with the prevailing interest in the geometry and motion of spiral waves in excitable media [4,5], and the study of spiral waves in cardiology is intense; see Figure 3. Still, many of the problems, particularly those in the bestiary, lie dormant. I expect that researchers interested in biological oscillators will be digging in these books for ideas buried in their pages well into the next century. GBT is indispensable to all researchers with an interest in biological rhythms or the applications of nonlinear dynamics to the natural sciences. Already, research workers often cite it as a "classic." I am sure its stature will continue to grow. WTBD covers narrower territory than GBT. Becal4se it contains no equations, it is more accessible to people with weaker mathematical backgrounds. For biologists and those with a recreational interest in mathematics, it provides a good introduction to Winfree's approach. I close on a personal note. I have known Art Winfree since the fall of 1969 when we both had offices in a building on 57th Street in Chicago that housed the Meat Research Institute and the now defunct Department of Theoretical Biology. We have kept in contact since then. I consider it a privilege to have witnessed the discoveries recounted in these books. It is clear to me that the topological viewpoint that Winfree espouses is just taking hold. Yet there are still great mysteries in understanding the development and dynamics of organisms. The solution of these problems will require novel blends of mathematics, biology, and physics. Winfree's pioneering work has shown us that it can be done.

Apology In the review of J. Stillwell's Mathematics and Its History by J. Fauvel and A. Shenitzer (The Intelligencer 14, no. 3 (1992)), it was the reviewers' intent in the third paragraph of p. 69 to contrast the accounts of pre-1800 mathematics readily findable in popular books with the exceptional book of Stillwell, which also reports more recent mathematics. Unfortunately, the sense of this paragraph was altered in the printed version.

Ramsey Theory by Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer N e w York: Wiley-Interscience, Series in Discrete Mathematics and Optimization, Second Edition, 1990, xi + 196 pp., hardcover, US $49.95 (ISBN 0-471-50046-1). Reviewed by Richard K. Guy Combinatorics is at last seen as a respectable mathematical discipline, in no small part because of the emergence of Ramsey theory as one of its several main streams of thought. It is now a mathematical chestnut to ask to show that if six people are at a party, then three of them are already mutual acquaintances or three of them are strangers to each other. This is the simplest application of Ramsey's theorem, unless you count Kleitman's observation that among three ordinary people, two must have the same gender. Very roughly, Ramsey's theorem states that if a structure is big enough, it must contain a copy of a prescribed substructure. As Motzkin has put it: complete disorder is impossible. It was van der Waerden, in 1927, who proved the first theorem of Ramsey Theory: if the positive integers Notes and References are partitioned into two classes, then at least one of the 1. For a mathematical treatment of phase singularities, see classes must contain arbitrarily long arithmetic proJ. Guckenheimer, Isochrons and phaseless sets, J. Math. gressions. In 1935, Erd~s and Szekeres rediscovered Biology 1 (1975), 259-273. Ramsey's 1930 theorem. Behrend, Dilworth, and espe2. J. M. Davidenko, A. V. Pertsov, R. Salomonsz, W. Bax- cially Rado and Turin along with Erd6s, wrote importer, and J. Jalife, Stationary and drifting spiral waves of excitation in isolated cardiac muscle, Nature 355 (1992), tant papers in the forties and fifties which, with hindsight, are seen to be central to Ramsey theory. A fairly 349-351. 3. S. Strogatz, Yeast oscillations, Belousov-Zhabotinsky early paper was Greenwood and Gleason (1955). But it waves, and the non-retraction theorem, Mathematical In- was the sixties and seventies which saw the amalgamtelligencer 7 (1985), 9-17. ation into a coherent theory. Of the 132 references in 4. A. Karma, Scaling regime of wave propagation in singlethe book, 85 are from this period. diffusive media, Phys. Rev. Lett. 68 (1992), 397-400. The importance of the subject has demanded a sec5. D. A. Kessler, H. Levine, and W. N. Reynolds, Spiral core in singly diffusive excitable media, Phy. Rev. Lett. 68 ond edition. What has transpired in the eighties? Most (1992), 401-404. momentous, perhaps, is Shelah's discovery of much improved recursive bounds for the Hales-Jewett and Department of Physiology van der Waerden theorems. Indeed, the insertion of a McGill University new w and the related amplification of the old secMontreal, Quebec, H3G 1Y6 tion, EEEEENORMOUS UPPER BOUNDS, on "ackerCanada 70

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

manic" functions, are the only significant changes from the 1980 edition. Although there is half a page of "Notation" on p. xi, there is a desperate need for a more whole-hearted glossary. Notation is the aspect of the subject that puts most people off. Suppose that I start to read about the application of Topological Dynamics to Ramsey Theory, and find that it will prove van der Waerden's theorem and Hindman's theorem. The former I know, but I need to be reminded of the latter, which I find on p. 88: "If N is finitely colored, there exists S C NS infinite, such that ~(S) is monochromatic." What are N, NS and ~(S)? N is perhaps the natural numbers, and I confirm this on p. xi, although it seems that zero is not a natural number. However, in Chapter 1, on "Sets," where I might expect to find it, the only place where N occurs is on pp. 25-26, where it denotes a particular number. N next occurs on pp. 34, 39, 40; in each case for a specific integer. Then on p. 41 it has three different uses: as a particular number, then as the set of natural numbers, then as a fixed number of dimensions. We have now reached Gallai's theorem: "Let the vertices of R m be finitely colored. For all finite V C R m there exists a monochromatic W homothetic to V." We can't learn from p. xi (nor from anywhere else?) what R or R m are. Presumably the reals and m-dimensional Euclidean space. Is it usual to refer to its points as vertices? It is more suggestive of a polyhedron. To go back, @(S) is defined on p. 81, but not on p. xi. The mystery of NS was not revealed until I borrowed a colleague's copy of the first edition it should read N, S---a sentence of very different syntax. There are dozens of other misprints (almost none of which occur in the first edition), even among the more well-known names; H i n d m a n , Leeb, Ramsey, and Szekeres appear on pp. 88, 10, and 25 as Hinderman, Leep, Ramsey and Szekers; Tur~in sometimes has his accent, sometimes not; Erd(~s never gets his correct one. There are some atrocious line-breaks in the middles of formulas. My limited experience with TEX shows that line-breaks in the text can be handled very well. Why are many commercial word-processing systems so bad at it? Here we find homoge-neous, independent, appro-priate, elemen-tary, mathemati-cians, terminology. Would the program handle gene, depend, proper, element, mathematics, or term, in the same way? "Proven" is the part principle of preave, an archaic verb meaning "test" and not the modern meaning of mathematical proof. "Denote" is a transitive verb. All these things combine to obliterate the considerable efforts that the authors have made to expound the m a n y combinatorial proofs that most readers find so difficult. But the importance and elegance of the subject shine through, in spite of the blemishes of production.

References F. A. Behrend, "On sets of integers which contain no three in arithemetic progression," Proc. Nat. Acad. Sci., 23 (1946), 331-332. R. P. Dilworth, "A decomposition theorem for partially ordered sets," Ann. Math., 51 (1950), 161-166. P. Erd6s & G. Szekeres, "A combinatorial problem in geometry," Compositio Math., 2 (1935), 464--470. R. E. Greenwood & A. M. Gleason, "Combinatorial relations and chromatic graphs," Canad. J. Math., 7 (1955), 1-7. A. W. Hales & R. I. Jewett, "Regularity and positional games," Trans. Amer. Math. Soc., 106 (1963), 222-229. N. Hindman, "Finite sums from sequences within cells of a partition of N," J. Combin. Theory Ser. A, 17 (1974), 1-11. R. Rado, "Verallgemeinerung eines Satzes von van der Waerden mit Anwendung auf ein Problem der Zahlentheorie," Sonderausg. Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Kl., 17 (1933), 1-10. F. P. Ramsey, "On a problem of formal logic," Proc. London Math. Soc., 30 (1930), 264-286. S. Shelah, "Primitive recursive bounds for van der Waerden numbers," J. Amer. Math. Soc., 1 (1988)~ 683-697. B. L. van der Waerden, "Beweis einer Baudetschen Vermutung," Nieuw Arch. Wisk., 15 (1927), 212-216. Department of Mathematics and Statistics The University of Calgary Calgary, Alberta T2N 1N4 Canada

U n s o l v e d Problems in G e o m e t r y by H. T. Croft, K. J. Falconer, and R. K. Guy New York: Springer-Verlag, 1991, 240 pp. US$39.95 Reviewed by Dennis DeTurck One brisk winter day, the editor of this column called me to ask if I would be willing to review a "little problem book on geometry" that looked interesting to him. Having agreed to do it, and being a close neighbor (the Mathematics Departments of Penn and Drexel are less than two city blocks apart), I walked over to pick up a copy of the book. That night, I settled down to begin looking at the book, and read as far as problem A1 (on page 9)--the equichordal point problem. For the record, an equichordal point of a plane convex curve is one having the property that every chord through it has the same length. The problem (which dates back to 1917 and the likes of Fujiwara, Blaschke, Rothe, and Weitzenb6ck) is to decide whether there is a closed convex plane curve having two distinct equichordal points. Despite warnings in the book about the difficulty of the problem, it was three weeks and many hours of fruitless work later that I read problem A2 and beyond. Well, maybe not completely fruitless one oddball idea I explored a bit was to have my computer start with a pair of points, say (1,0) and ( - 1,0), which were to be the equichordal points, a length L > 6 (the common length of all the chords), and an initial point (x0,Y0), and to generate a sequence of points (xi,Yi) (all THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 7 1

on the putative curve) by drawing "chords" of length L f r o m (xi.l,yi.1) a l t e r n a t e l y t h r o u g h t h e t w o equichordal points. Each time, the s e q u e n c e of "chords" converged to a horizontal one. It is an amusing exercise to prove that this always happens. Anyhow, to get back to the book at hand, the authors have compiled a remarkable collection of geometry problems, none of which requires a great deal of mathematical sophistication to understand, yet which remain (in many cases after decades or even centuries) unsolved. There are 148 problem sections in all, where a problem section may consist of a single paragraph with the barest statement of a problem together with a reference or two, or else could be several pages long, containing information on published partial solutions, statements of related problems, and interesting anecdotes. The sections are patterned after (and in some instances the problems themselves come from) Victor Klee's "Research Problems" sections of the American Mathematical Monthly, which began running in the late 1960s. The problems are grouped into seven chapters, although many of the problems transcend the authors' classification scheme. Each chapter begins with a concise review of the terminology used therein. The problems in the first chapter (Convexity) have the property that the word "convex" appears in each problem. Here one will find problems ranging from the familiar (reconstruction of convex bodies from shadows and sections, variations on Queen Dido's isoperimetric problem, etc.) to more specialized, less-known problems. An example of the latter is problem A14: What closed convex 3-dimensional surfaces have the property that a regular tetrahedron can rotate to any orientation within them, keeping all four vertices always on the surface? Another intriguing problem in this chapter concerns the existence of convex sets with "universal sections.'" The second chapter contains problems about polytopes--there are real surprises among the first few open questions posed here. One's reaction is inevitably "You mean the answer to that question is unknown?!" This chapter contains the only problem about which I am aware of recent progress: problem B18. One of B18's subproblems asks, "Is every convex polyhedron equivalent to one with all its edges touching a sphere?" Here, equivalence means combinatorial equivalence (i.e., having the same relative arrangement of vertices, edges, and faces, as for instance a cube and a parallelepiped), and the answer to the question is yes. Koebe is responsible for the proof for a certain class of convex polyhedra, with proof for the general case being contained in Chapter 13 of Thurston's Princeton Notes on The Geometry of 3-manifolds. Very recently, Oded Schramm ("How to cage an egg," Inventiones Math. 107 (1992), 543-560) generalized the result: It is still true w h e n the sphere is replaced by an arbitrary smooth convex body. 72

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

The other chapters concern tiling and dissection (decompositions of rectangles, polyominoes, rep-tiles), packing and covering (packing pennies, filling containers), combinatorial geometry (problems about lattice points and variations on Minkowski's problem), problems about finite sets of points (number of distinct distances, triangles, etc., determined by such sets; lots of Erd6s problems here), and "general geometric problems." The book is a wonderful source of diversion. Rather than being a book to be read from beginning to end, the book invites the reader to open it almost at random and consider whatever problems are encountered. There is real peril involved, however. Many of the problems are irresistible, and all of them are difficult. The one serious criticism I have of the book concerns not what is between the covers, but what is on the back cover, and what is contained in the promotional material circulated by the publisher. To quote from the back-cover blurb: "The book is an invaluable reference for the research mathematician and also for t h o s e . . . who wish to keep abreast of progress on geometrical problems. For the mathematically minded layman or student, the book provides an insight into current mathematical research." Statements such as these do not accurately represent the nature or the value of the book. Although some of the problems in the later chapters (mostly the combinatorial problems) are au courant in research circles, by and large the problems in the book are not at the focus of late twentieth-century geometry. There are few differential geometry problems in the book, nor are there geometric analysis problems. The author index is not a Who's Who of geometry in the nineties. Rather, the authors have succeeded in producing a charming and valuable collection of accessible unsolved problems, the solution of any of which would attract the attention of some segment of the mathematical community. One can only hope that some day the solutions manual will appear!

Department of Mathematics University of Pennsylvania Philadelphia, PA 19104-6395 USA

Old and N e w Unsolved Problems in Plane Geometry and Number Theory by Victor Klee and Stan Wagon Washington, DC: Mathematical Association of America, 1991. 352 pp. paperback, US$22.00. (ISBN 0-88-385-3159)

Reviewed by Kenneth Falconer Most mathematicians have a favourite problem that they would very much like to solve; a few achieve this aim, but many more enjoy investigating aspects of the

problem, perhaps producing partial solutions or answering simpler related questions, or just convincing themselves that the problem is indeed difficult. Some devote considerable time to an unsolved problem in the hope that a flash of inspiration will lead to their immortalisation in mathematical history. Problems studied by professional mathematicians may be highly technical, but there are many simply stated questions that have occupied innumerable hours of amateurs and professionals alike, Fermat's Last Theorem being, perhaps, the best known example. Appealing problems, problems that anyone can understand but that are hard to solve, are probably most prevalent in the fields of number theory and two- or three-dimensional geometry. We all encounter primes, rationals, convex sets, and plane closed curves at an early age; surely any questions on such familiar topics ought to be tractable! Not surprisingly, m a n y of the unsolved problems in collections and in mathematical journals tend to be on number theory or geometry. This book covers both areas; in a sense it contains two books in one--the halves on geometry and number theory having little in common except for the intuitive nature of the problems. The selection of problems is inevitably somewhat subjective. The authors have dearly decided to include the "big" unsolved problems. Does there exist a plane convex set such that every chord through one of two given points has unit length (the equichordal point problem)? Does there exist a polygon that only tiles the plane aperiodically? (There is a pair of polygons, the famous "Penrose tiles," that tile the plane aperiodically but not periodically.) We also encounter Fermat's Last Theorem and the Riemann Hypothesis. But some problems included are less central, for example, does every simple closed curve contain the vertices of a

Does every simple closed curve in the plane contain all four vertices of some square?

square? Does there exist a box with the lengths of sides, face-diagonals, and main diagonals all integers? The inclusion of these problems reflects the authors" interests. Many readers will have their own favourites that could equally well have formed the basis of sections. The reviewer's own selection might have included: Can a rectangle be dissected into three congruent Jordan regions in a nontrivial way? In the disc of radius 1, what is the subset of largest area for which a distance of 1 between any two of its points is not attained (surely it must be an open disc of diameter 1)? If a convex set C is covered by a collection of parallelsided strips or "planks" of widths wi (1 ~ i ~ m), is it the case that X(wi/Wi) t> 1, where Wi is the width of C in the direction perpendicular to the ith strip? (This is the affine-width version of Bang's plank problem.) Any book of this nature is out of date before publication. The section on "squaring the circle" (can a circle be decomposed into finitely m a n y pieces that can be rearranged to form a square?) has already capitulated to Laczkovitch's brilliant and unexpected proof that it can indeed be done. Still, such advances raise many further problems; for example, in this instance, how few pieces are required? (Somewhere between 3 and 10,000,000 seems all that is known.) How essential is the axiom of choice in any solution? The book is well-written and readable. As well as the main problem stated at the beginning of each section, there is a description of the state-of-the-art related theorems (sometimes accompanied by proofs where these are instructive and fairly elementary) and subsidiary problems. Each part of each section concludes with a nice selection of exercises; working through these (with the odd glance at the Hints and Solutions, if required) will probably not help anyone solve the main problems, but it will increase familiarity with the area and highlight some elegant ideas and slick methods. The authors have appended a useful bibliography to each chapter. Considering the literature that has accumulated on some of the more notorious problems, these bibliographies are by no means complete, but they provide an adequate start for those wishing to study a problem in greater depth. I find the layout of this book highly irritating. Chapter 1 on "Two-dimensional Geometry" has two parts. The first part discusses each of 12 problems at a basic level in half a dozen pages or so. The second part reconsiders each problem, in turn, in greater depth and with historical details and references. Consequently, between Problems 6.2 and 6.3 on the number of connecting lines through points in a finite plane set, one encounters Problem 7.2 on tiling the plane by pentagons, as well as Problem 1.5 on the number of billiard paths on a convex table. The authors have split Chapters 2 and 3 on "Number Theory" and "Interesting Real Numbers" in the same way. Thus, when flicking back and forth between the two Sections 18 on THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993 7 3

1

643~~-2~

84 320~z~53

5~

"17~("~35

34,

12 24.//

140

11

92

120/

6

14/

58.,/"/~"~112,/, 56-~

9

38/10 , 37 76./ 74,,2'72/3618

ioo5O25

;" /

33 The 3n + 1 Problem: Is every positive integer eventually taken to 1 under iteration of the function f(n) = n/2 (if n is even) and fin) = 3n + 1 (if n is odd)?

prime factorization algorithms, one is seduced by an eye-catching problem on approximation of tetrahedra by rational tetrahedra, or by the graph of the Riemann Zeta function, and forgets the original problem. In my frustration, I nearly cut up the book and reassembled the pages to unify the sections! This is an attempt to put two books into one: the first, consisting of the Parts 1, suitable for mathematics undergraduates, the second, consisting of Parts 1 and 2 together, for more advanced s t u d e n t s and researchers. However, it would have been better to keep the material on each problem (including references) together. This book will inevitably be compared with the two Springer-Verlag Unsolved Problems in Intuitive Mathematics rifles, Unsolved Problems in Number Theory by Richard Guy and Unsolved Problems in Geometry by Hallard Croft, Richard Guy, and the reviewer, particularly with the latter book, which appeared at about the same

74

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1, 1993

time as the book under review. Though I feel it is inappropriate to praise or scorn m y own book (looking back at some past reviews and refutations, I feel this may differ from Mathematical Intelligencer editorial policy!), some remarks seem in order. Both works have u n d o u b t e d l y benefited from correspondence and manuscripts that have circulated privately for up to 30 years. Many well-known mathematicians have, at least indirectly, influenced both books (this is clear even from comparing the acknowledgements), and there are many common problems. The Springer books contain far more problem sections, but with less discussion and proof in each section. I feel the books complement each other: If you enjoy reading one, then you probably will enjoy meeting new, but not entirely unfamiliar, material in the other. I have to admit (grudgingly, because the matter was outside m y control) that, at $22, this book is more reasonably priced than t h e Springer ones. From m y experience, I know that the book will result in a considerable mailbag for the authors. Some letters will be irritating: "Why haven't you cited my vaguely related paper in the Outer Hebridean Mathematical Society Proceedings?" Others will give purported solutions to the problems. Some will contain genuine misconceptions; others will be just cranky. Some, from both amateurs and professionals, may contain a proof or an idea that will be a genuine contribution to one of the topics. I agree with the publisher's claim that the book will appeal to a wide range of readers, from spare-time amateur mathematicians, to teachers at all levels, students, and university researchers. I personally found many facts and problems to fascinate both on familiar and unfamiliar topics. The sections on prime factorisation, Fermat's Last Theorem, etc., are useful for nonspecialists to update their mathematical general knowledge. Even the sections on areas that I am most conversant with, and to w h i c h I have m a d e minor contributions, contained unfamiliar material. Several people have commented to me that they had "been unable to put the Springer Unsolved Problems in Geometry d o w n . " (I refrain from the Wodehousian crack that this was because they had not picked it up in the first place!) The same is true of Klee and Wagon's book. It is compulsive reading and will fill your mind with problems that will come back to haunt you again and again during idle moments.

School of Mathematics University of Bristol Bristol, BS8 1TW England

ERRATUM Due to a printing error, the Cyrillic-language text in the references to Yuri Matijasevich, " M y collaboration with Julia Robinson," The Mathematical Intelligencer 14, No. 4 (1992), 38-45 was dropped from the printed version. The correct references are reprinted below in full.

spired by mathematical logic, Proceedings of Fifth International Congresson Logic, Methodologyand Philosophyof Science, London, Ontario, 1975, Dordrecht: Reidel (1977), 121-127.

References

1. Martin Davis, Yuri Matijasevich, and Julia Robinson, Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution, Proc. Syrup. Pure Math. 28 (1976), 323-378. 2. Martin Davis, Hilary Putnam, and Julia Robinson, The decision problem for exponential Diophantine equations, Ann. Math. (2) 74 (1961), 425-436. 3. G. V. Davydov, Yu. V. Matijasevich, G. E. Mints, V. P. Orevkov, A. O. Slisenko, A. V. Sochilina and N. A. Shanin, "Sergei Yur'evich Maslov'" (obituary), Russian Math. Surveys 39(2) (1984), 133-135 [ t r a n s l a t e d from Ycnexu ~am. uayx 39(236) (1984), 129-130]. 4. David Hilbert, Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker Kongress zu Paris 1900, Nachr. K. Ges. Wiss., Grttingen, Math.-Phys. Kl. (1900), 253-297. 5. James P. Jones, Universal diophantine equation, J. Symbolic Logic 47 (1982), 549-571. 6. IO. B. Marnacee~,t, ~loqba,roaocrb nepen,c~,m, lx MHO>Kecra, ;Slornadbi AH CCCP 191(2) (1970), 27%282 [translated in Soviet Math. Doklady 11(20) (1970), 354-357; correction 11(6) (1970), vi]. 7. Yuri Matijasevich, On recursive unsolvability of Hilbert's tenth problem, Proceedings of Fourth International Congress on Logic, Methodology and Philosophy of Science, Bucharest, 1971, Amsterdam: North-Holland (1973), 89-110. 8. Yuri Matijasevich, Some purely mathematical results in-

9. IOpnfl MaTI, LSlCeBHq, } ~ y a r t a PO6HtlCOH, j~Ba ynnBepcadlbHb~X TpexKaaHTOpHb~X npeacTaaaeHna nepenncanMb~x MHOX~ec'ra, Teopua a.azopuctb~oa u xcam. ,~ozutca, Mocgaa: BL[ AH CCCP (1974), AH CCCP (1974), 112-123. 10. Yuri Matijasevich and Julia Robinson, Reduction of an arbitrary Diophantine equation to one in 13 unknowns, Acta Arith. 27 (1975), 521-553. 11. Constance Reid, The autobiography of Julia Robinson, College Math. J. 17 (1986), 3-21. 12. John A. Robinson, A machine-oriented logic based on the resolution principle, J. Assoc. Comput. Mach. 12 (1965), 23-41 [translated in Ka6epneTHqecgHfi c6OpHHK (aoaaa cepaa) 7 (1970), 194-218]. 13. Julia Robinson, An iterative method of solving a game, Ann. Math. (2) 54 (1951), 296-301. 14. Julia Robinson, Existential definability in arithmetic, Trans. Amer. Math. Soc. 72 (1952), 437-449. 15. Julia Robinson, Unsolvable Diophantine problems, Proc. Amer. Math. Soc. 22 (1969), 534-538. 16. Julia Robinson, Axioms for number theoretic functions, Selected Questions of Algebra and Logic (Collection Dedicated to the Memory of A. I. Mal'cev), Novosibirsk: Nauka (1973), 253-263; MR 48#8224. 17. D. Singmaster, Notes on binomial coefficients, J. London Math. Soc. 8 (1974), 545-548; P)KMaT (1975), 3A143. 18. N. N. Vorob'ev, Fibonacci Numbers, 2nd ed., Moscow: Nauka, 1964; 3rd ed., 1969.

THE MATHEMATICALINTELLIGENCERVOL. 15, NO. 1 9 1993 Springer-VerlagNew York 75

Robin Wilson*

Greek Mathematics III

Archimedes

The achievements of Archimedes (c. 287-212 B.C.) were many and varied. In geometry he calculated the volumes and surface areas of various solids, such as the sphere and cylinder, and he listed the thirteen semi-regular polyhedra in which all faces are regular but are not all the same. He also investigated the socalled Archimedean spiral w h o s e polar equation is r = k0. In applied mathematics he made outstanding contributions, both to mechanics and to statics. In mechanics he studied levers and devised ingenious mechanical contrivances for the defence of Syracuse. In statics he noted that when an object is immersed in a liquid its weight is reduced by an amount equal to the weight of liquid displaced now called Archimedes's principle and used this to test the purity of a gold crown. On discovering this fact, he supposedly jumped out of his bath and ran naked down the street shouting "Eureka! Eureka!"; regrettably this particular episode has not yet been featured on a stamp.

* Column editor's 76

address:

Faculty of Mathematics, The Open University, Milton Keynes, MK7 6AA England.

THE MATHEMATICAL INTELLIGENCER VOL. 15, NO. 1 9 1993 Sprlnger-Veflag New York