No title

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

On Shafarevich's Essay "'Russophobia" In the Spring of 1989 the Mathematical Intelligencer (vol. 11, no. 2, 16-28) published a 12-page interview by Smilka Zdravkovska with the eminent Russian mathematician I. R. Shafarevich. Its focus was on Professor Shafarevich's long and productive career as a mathematician. Only at the very end there was a casual dis,cussion of his book "Russophobia," which at the time had been widely circulated in Samizdat in the Soviet Union. Shafarevich's book deals not with mathematics, but with "social issues." Its principal thesis is that Jews (the "little people") have succeeded in penetrating and dominating Russian culture and life as part of a worldwide conspiracy, the origins of which reach back into history. The Mathematical Intelligencer interviewer brought up the matter when she said to Shafarevich, "'Some consider ['Russophobia'] unfair, and even accuse you of anti-Semitism." He replied, in part, "Russians and Jews will have to live together for a long time and must learn to listen and discuss each other's opinions, even if they seem offensive." The tone throughout the interview was one of respect and civility. Quite a different picture emerged in the February 5, 1990 issue of The New Republic. In a series of articles about rising anti-Semitism in the Soviet Union, the views of our colleague Shafarevich were featured prominently. This surprised me no end: H o w could it be that mathematicians said nothing, while "'outsiders" wrote about a campaign reminiscent of the days of the Nazis? Professor I. R. Shafarevich is "'one of us," and truth is so clear in our work and fundamental to our work. When the opportunity arose to obtain a copy of an English-language version of "Russophobia," translated by fellow mathematician Larry Shepp, I learned what was in Shafarevich's book firsthand. (Note: If you wish to see it too, I will lend you a copy.) Well, there was no way I could have been prepared for the allconsuming sickness and distortion and viciousness of Shafarevich's attack on Jews. However, that is not all.

Our colleague Shafarevich has continued his campaign of hate. He is, at this time, a well-known figure on Russian television, where he continues to spread his ugly message. As a Corresponding Member of the Academy of Sciences of the USSR and a Foreign Associate of the National Academy of Sciences USA, his words carry weight. Almost three years have passed since the Zdravkovska interview was published. During that time, efforts have been made to raise the collective voice of the American mathematical community in protest. Some, though, have held that mathematicians should confine their activities to matters relating directly to mathematics. At this writing, we know of only two published responses, both in the Mathematical Intelligencer: 1. Shepp (who had translated the essay into English) and Eugene Veklerov wrote a detailed review and critique of "Russophobia" and submitted it to the Mathematical Intelligencer, but the editors were unwilling to publish it. Instead, after a lengthy negotiation, they published a brief letter to the editor from Shepp and Veklerov (vol. 12, no. 1, 4). 2. In its Winter 1992 issue the Mathematical Intelligencer brought the matter up anew, with a short piece in its "Opinions" column (vol. 14, no. 1, 61-62) made up of excerpts from an interview with Professor Boris Moishezon, a former student of Shafarevich. The interview focussed nostalgically on the past: on the sadness of a student who could not believe that his beloved teacher had changed so much. There was not so much a denial of the ugly present as a tone of w o n d e r and disbelief, the net result of which was to mute the seriousness of the matter. After all, it said by implication, a man who loved his (mathematical) children so much could not be so bad. The Mathematical Intelligencer is the unique journal in our field which attempts to describe the culture and flavor of mathematics as well as its content. Much has been said about the role of individual responsibility in the events which led to mass murder during World War II. There is nothing to say that it cannot happen

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2 9 1992 Springer-Ver|ag New York 3

again. It is long past time for the Mathematical Intelligencer to speak out. Anything else is a matter for shame.

Joan S. Birman Columbia University New York, NY 10027 USA (The Editor calls attention also to an open letter to Professor Shafarevich, signed by hundreds of mathematicians mostly from the USA, published in the Notices of the American Mathematical Society 39 (1992), no. 3.)

,Sheldon Axler Replies As Editor-in-Chief of the Mathematical Intelligencer from 1987 to 1991, I made the decisions to publish the Zdravkovska interview with Shafarevich, to reject the Shepp-Veklerov paper, and to publish the SheppVeklerov letter. Professor Birman's letter contains some serious distortions. She states that Shafarevich's book Russophobia was widely k n o w n in the Soviet Union when Zdravkovska interviewed Shafarevich. Actually, at the time of the interview (June 1988) Russophobia was just beginning to circulate in the Soviet Union. Zdravkovska obtained one of the first copies of Russophobia available to mathematicians. She realized its importance after she had returned to the U.S. and had prepared the first draft of the interview. On her next trip to Moscow in December 1988, Zdravkovska requested that Shafarevich answer an additional question, the one about Russophobia. Shafarevich's reply was incorporated at galley stage. Its publication in the Mathematical Intelligencer provided the first announcement to the mathematical community of the existence of Russophobia. Before making a decision about the long SheppVeklerov paper that was later submitted to the Mathematical Intelligencer, I read every word of Russophobia. I found the book utterly unconvincing and offensively anti-Semitic. Russophobia does not contain one sentence, or even a single phrase, that smacks of mathematics or mathematical-type logic or reasoning or proof. A reader of Russophobia who did not know otherwise would have no reason to guess that Shafarevich has any mathematical knowledge. Thus, Shepp was simply incorrect when he wrote that Russophobia "abuses mathematical logic." Russophobia does abuse logic, in the commonsense meaning that Shafarevich draws ridiculous conclusions from selected evidence. But there is no mathematical or pseudo-mathematical framework within Russophobia, just the usual style of a book written by a historian (of course, in this case the book is junk). The Shepp-Veklerov article, which I decided was not appropriate for the Mathematical Intelligencer, also has no contact with anything mathematical. Here is an analogy: The Mathematical Intelligencer has published articles about what h a p p e n e d to Steve 4

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

Smale during the Vietnamese war. This material focused on what happened to Smale as a mathematician (for example, his problems with the National Science Foundation) as a result of his political activities protesting U.S. action in Vietnam. If Smale or someone else had written an article just analyzing Smale's (nonmathematical) arguments about Vietnam, in other words an article about the history of U.S. intervention there, I would think that such an article would be inappropriate for the Mathematical Intelligencer (even if I as Editor-in-Chief agreed with its contents). Similarly, the Shepp-Veklerov paper is a long analysis of Shafarevich's historical (and completely nonmathematical) ideas. Birman writes that the Shepp-Veklerov letter-to-theeditor was published in the Mathematical Intelligencer after "a lengthy negotiation," implying I was reluctantly prodded into publishing the letter. In fact what happened is that in my letter to Shepp-Veklerov rejecting their paper, I suggested that they write such a letter for publication in the Mathematical Intelligencer. They wrote the letter, and after receiving it I immediately sent Shepp an acceptance letter, requesting no revisions. Because the Shepp-Veklerov letter accused Shafarevich of anti-Semitism and criticized Zdravkovska for being too gentle with Shafarevich, I sent Shafarevich and Zdravkovska copies of the letter and offered them the opportunity to respond. Shafarevich never answered me. Zdravkovska did write a response, explaining the chronology of the Russophobia question in the interview, much as I have done above. I thought the Shepp-Veklerov letter would be stronger if it concentrated just on Shafarevich's anti-Semitic ideas. Thus after receiving Zdravkovska's response I sent it to Shepp-Veklerov, and told them they had a choice: (1) I would publish their original letter and Zdravkovska's response, or (2) they could delete their criticism of Zdravkovska, in which case I would publish their revised letter but not Zdravkovska's answer. Shepp-Veklerov quickly chose option (2), and then their revised letter appeared in the Mathematical Intelligencer. Hardly "a lengthy negotiation."

Sheldon Axler Department of Mathematics Michigan State University East Lansing, MI 48824 USA

Explaining the Number 1240 It was a pleasure to read Osmo Pekonen's ghost story (Mathematical Intelligencer, vol. 13 (1991), no. 4). It ends with an open question: What is the mathematical meaning of 1240. My solution is quite trivial, but (perhaps) surprising. As you can see from my address, 1240 is the P.O. Box number of the German National Research Institute for Mathematics and Computer Science---which is Io-

cated at a castle in St. Augustin, who is quoted twice in the article. In the field of cabbalistics there are no accidents. Unfortunately we have to change our P.O. Box number. Does this mean that postal clerks are unsympathetic to cabbalists, or are they trying to prevent that ghost from haunting our castle?

Bernhard Klaassen Gesellschaft fiir Mathematik und Datenverarbeitung P.O. Box 1240 W-5205 St. Augustin 1 Federal Republic of Germany

Here is a simpler derivation of the formula for the Catalan numbers than the one given by Peter Hilton and Jean Pedersen in the spring 1991 Mathematical Intelligencer. The binary trees with leaves from a set A of atoms are the same as the set S of Lisp S-expressions with atoms from A. S is the least set satisfying (1)

Where + is interpreted as disjoint union, and x as Cartesian product. The formula expresses the definition of an S-expression as either an atom or an ordered pair of S-expressions. In good 18th-century style, we ruthlessly regard (1) as a quadratic equation for the set S, solve it by the quadratic formula, choose the minus sign in the solution, expand the radical by the binomial theorem, and simplify the coefficients. This gives

k=0 1

12k\

and ~--~-~ k) is precisely the kth Catalan number. That's all.- For the picky who grumble about taking such liberties with sets, here's another derivation. (1) can be expanded by repeatedly substituting the right-hand side of (1) for each occurrence of S on the right side. To this we can then apply the distributive law, associative laws, and laws for collecting terms that are familiar in numerical mathematics but which also apply to sets. This gives a formula S - A + A2 § 2 x A 3 + 5 x A4 + 14 x A 5 + etc.

S=A+S

p.

John McCarthy Department of Computer Science Stanford University Stanford, CA 94305-2140 USA

Recognizing Finiteness

Catalan Numbers

S = A + S x S,

A similar formula applies to the p-ary trees counted by the generalized Catalan numbers, but there isn't such an easy way of evaluating the coefficients obtained by solving the set equation

(2)

However, the coefficients in (2) are the same as those that would be obtained by similarly expanding the quadratic equation x = a + x2. Since, in the latter case, there is no doubt of the applicability of the quadratic formula and the binomial theorem, the original way the coefficients were determined is justified.

In the Summer 1991 Mathematical Intelligencer, Peter Nyikos wrote a letter criticizing James Henle's article, "The H a p p y Formalist," which had appeared in the Winter 1991 issue. Nyikos's criticism is mistaken, but it is based on a misunderstanding widespread among mathematicians. Nyikos claimed that it is impossible to formalize in a satisfactory way the distinction "finite" and "infinite" in a formal system. That is, if we define "finite" within a formal system, there will be non-standard models of arithmetic in which there are infinite integers. But this argument depends, not on the notion of formal system, but on the very particular kind of formal system embodied in first-order logic. Henle's definition of formal system (p. 13) does not apply only to first-order logic, but to many kinds of logic, and in particular to second-order logic. If formal systems are restricted to first-order logic, then Nyikos is quite correct. For in the models of firstorder logic, the quantifiers are taken to vary only over individuals, not over sets. First-order logic satisfies a "Compactness Theorem," which is exactly w h y it gives non-standard models of arithmetic and w h y it cannot satisfactorily distinguish between "finite" and "infinite." (The Compactness Theorem states that a set A of sentences has a model if every finite subset of A has a model.) By contrast, second-order logic, which has quantifiers varying over sets (but not over sets of sets) as well as quantifiers varying over individuals, has no such Compactness Theorem. Second-order logic has no non-standard models of arithmetic, and can distinguish quite satisfactorily between "finite" and " i n f i n i t e . " Likewise, in s e c o n d - o r d e r logic Nyikos's example of the Twin Primes Conjecture also fails. So if Henle meant to restrict formal systems to firstorder logic, then Nyikos's criticisms are correct. But if Henle meant what he said in defining the notion of formal system, then his definition includes secondorder logic and Nyikos's criticism is mistaken.

Gregory H. Moore Department of Mathematics McMaster University Hamilton, Ontario L8S 4K1 Canada THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992 5

Mathematical Ideas, Ideals, and Ideology Harold M. Edwards

One of the high points of 19th-century mathematics was Ernst Eduard Kummer's introduction, in 1846, of his "ideal prime factors" of cyclotomic integers. His development of the theory of these "factors" enabled him soon thereafter to prove Fermat's last theorem for many prime exponents and in later years to prove his general reciprocity law. At least as interesting to the historian of mathematics as Kummer's idea itself, however, is the way he chose to present it and the ways his successors modified and reformulated it.

Kummer's paper of 1846 [12] is well worth reading. He was in possession of an important new idea, but a radically innovative one, and his task in the paper was to present it in a way the mathematical public would find acceptable and convincing. The resulting paper gives not only a lucid presentation of a great mathematical idea, but also an indication of the mathematical culture of 1846 as Kummer perceived it. Briefly put, Kummer described an ideal prime factor by describing an explicit computation for determining the multiplicity with which a given cyclotomic integer is divisible by the ideal prime factor: When fox) has the property that the product f(c0 9~(~r) is divisible by q, it will be expressed in this way; f(~) contains the ideal prime factor of q corresponding to u = -q~. Moreover, when f(a) has the property that f(c~)(~(~,))~ is divisible by q", b u t f(O0(~Is(Xlr)) "+1 is not divisible by q,+l, it will be said that f(~x) contains the ideal prime factor of q corresponding to u = "qr exactly ~ times. Here q is a prime integer, and what is being described is the method for determining the multiplicity with which a given cyclotomic integer f(o0 is divisible by a certain ideal prime factor of q. The construction of the crucial cyclotomic integer ~('qr) is of course described prior to the definition. 1 Thus, what is defined is not the ideal prime factor itself but the multiplicity with which it divides any given cyclotomic integer. Today, few mathematicians would find this definition acceptable. Most w o u l d want the ideal prime factor itself to be defined, and to be defined in terms of set theory. (The definition a m o d e m mathematician would most likely find sarisfactory is in terms of a valuation, a mapping of the nonzero elements of the cyclotomic field to Z sarisI For a m o r e d e t a i l e d a c c o u n t of K u m m e r ' s "Kummer's Original Definition."

6 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2 9 1992 Springer-Verlag New York

definition, see box

fying certain well-known axioms.) The wish for such a after. Two decades and more elapsed before finally, in definition is evidence of the enormous influence of 1881, he published his treatise Grundziige einer arithDedekind's ideal theory and his method of formu- metischen Theorie der algebraischen Gr6ssen, one part of lating mathematical ideas in general. In 1846, Dede- which, his theory of divisors, generalized Kummer's kind was still a boy; there is no evidence that Kummer theory not only to general algebraic number fields but or his contemporaries were dissatisfied with his defini- to algebraic function fields (the number field case tion for reasons of this kind. being the one in which the algebraic functions are The real reason to be dissatisfied with Kummer's functions with no variables). approach was not immediately evident, although During the 22 years between Kummer's cryptic anthere was a subtle hint of it in his first paper on the nouncement of Kronecker's theory and the publication subject when he stated that an analog,_o_us theory for of the Grundzitge, Dedekind gave up waiting for Kro"complex numbers of the form x + y V D " existed that necker and published his own generalization to the could be regarded as an alternative formulation of case of general algebraic number fields--his theory of Gauss's famous theory of binary quadratic forms. Al- "ideals." The influence of Dedekind's theory went far though the theory he hints at does exist and has the beyond the realm of algebraic number theory to the properties he claims for it vis-a-vis Gauss's theory, very foundations of mathematics and the way in Kummer never developed the theory of "ideal prime which mathematical theories were later to be formufactors" for algebraic integers of the form x + yX/-D, lated. and there are substantial obstacles to developing such A sea change in mathematical thinking took place in a theory in the way Kummer developed the theory in the second half of the nineteenth century. The conthe cyclotomic case, because Kummer's approach requires trasts between Kummer's original theory and Dedethat the ideal prime factors be explicitly given a priori; he kind's theory of ideals illustrate the change very was able to do this in the cyclotomic case for prime k, clearly, but the change encompassed much more than but in the case of general algebraic number fields it is algebraic number theory. In fact, its causes proceeded from analysis and the theory of functions, and these impossible. For his work on Fermat's last theorem, which was Kummer's first successful application of his were the areas most affected. That it reached as far as theory, the theory for cyclotomic fields with prime )~ algebraic n u m b e r theory, where, as Kronecker's was all he needed. His real objective, however, was theory shows, it was wholly unnecessary, is a meahigher reciprocity laws. Here he d i s c o v e r e d the sure of the forces that produced it. theorem he wanted to prove as early as 1847 (he comWhat brought about the change was the discovery municated it to Dirichlet in January of 1848) but was of the u n d r e a m e d - o f generality with which some unable to prove it for over a decade. His efforts to t h e o r e m s of analysis are valid. The a s s u m p t i o n s prove it led him to generalize his theory to other cases. needed to prove that the Fourier series of a function First, in a lengthy paper [13] published in 1856, he converges to the function were found to be so weak 2 generalized it to the cyclotomic case when ~, is com- that mathematicians were led to the outer reaches of posite. Finally, in the culminating paper of 1859 [14] what was conceivable as a "function," and encourcontaining the proof of his general reciprocity law, he aged to discard any notion that a function needed to generalized it (in a limited way, since he did not deal be given by a formula or a precisely formulated prowith prime divisors of the discriminant) to the fields cess. Similarly, the discovery that so mild an assumpHilbert later named "Kummer fields," namely, exten- tion as the Cauchy-Riemann equations implied that a sions of the cyclotomic field with prime k obtained by function of a complex variable was expandable as a adjoining a Mh root. Each time he generalized his power series prompted efforts to formulate the fountheory, he was obliged to find the analog of q~('qr), dations in a way that took advantage of the great genwhich is to say, he was obliged to determine in a erality that now seemed admissible. Riemann was the rather explicit way the factorization of all primes. most prominent figure in this movement, and much of By this time it was clear that the theory needed to be the change was inspired by his work, but it certainly formulated in a way that would make it possible to did not begin with him, and the actual exploration of describe the ideal primes without determining a priori the foundations inspired by his work was carried out the factorizations of all primes. Kummer stated in his by others. 1859 paper on the reciprocity laws (p. 57) that KroDedekind (1831-1916) was a few years y o u n g e r necker would very soon (nfichstens) publish a work "in w h i c h the t h e o r y of the most general c o m p l e x numbers" [meaning, surely, the most general alge- 2 For e x a m p l e , as Dirichlet rigorously proved, the Fourier series braic number field] "is completely developed with c o n v e r g e s p o i n t w i s e to the function for a n y periodic function with p e r i o d 2~r t h a t is p i e c e w i s e m o n o t o n e a n d h a s at m o s t a finite marvelous simplicity in its connection with the theory n u m b e r of discontinuities, at each of w h i c h the function h a s a leftof decomposable forms of all degrees." Unfortunately, h a n d limit a n d a r i g h t - h a n d limit a n d a v a l u e that is the average of Kronecker did not publish his theory very soon there- t h e s e two limits. THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992 7

than Riemann (1826-1866) and was strongly influenced by him, first as a student and later as a Privatdozent in G6ttingen. The other great influence on Dedekind was Dirichlet, who arrived in G6ttingen in 1856. Dirichlet's lectures on number theory initiated Dedekind's career in number theory and his interest in Kummer's ideal prime factors. The first edition of Dirichlet-Dedekind--the classic Vorlesungen fiber Zahlentheorie von P. G. Lejeune Dirichlet, herausgegeben und mit Zusdtzen versehen von R. Dedekind, published in 1863--contained nothing about Kummer's ideal prime factors, but the second, published in 1871, contained in its tenth supplement a complete development of Dedekind's theory of "ideals." Although this development differed substantially from Dedekind's later versions of the theory, the foundational ideas were the same. In an effort to do for number theory what Riemann had done for function theory--which Dedekind saw as the elimination of formulas and calculations in favor of intrinsic properties--Dedekind introduced the notion of an "ideal," which was, in modern words, a subset of a ring closed under addition and under multiplication by ring elements. The success of ideal theory was certainly not immediate, but in the following fifty years it was total. Through the work of Weber, Hilbert, Hecke, Noether, Artin, and others, the concept of an "ideal" became an unchallenged foundational concept not only of algebraic number theory but of algebra generally. From the point of view of number theory in 1870, the success of Dedekind's idea would have seemed unlikely if not incredible. Dedekind's fundamental premise was that the notion of "the set of all even numbers" was a concrete o n e - - e v e n though the taboo against completed infinites in mathematics still had many a d h e r e n t s - - w h i l e the notion of " e v e n " was formal or abstract. How did Dedekind and his followers succeed in convincing the mathematical world over the next half century that "the set of all things divisible by something" was more concrete than the notion of divisibility? For Dedekind himself, the conviction came from outside n u m b e r theory. D e d e k i n d ' s invention of ideals followed his invention of the Dedekind cut description of real numbers. The elusive concept of a real number was, in Dedekind's view, made concrete by being viewed as a cut of the set of rational numbers. If one has a particular real number described in some other w a y - - f o r example, as a definite integral--it is easy to see how such a description effects a cut of the set of rational numbers. (Defining a definite integral in this way is virtually the same as defining it in terms of the Greek method of exhaustion.) But if one is attempting, as Dedekind and most of his contemporaries were, to grasp the notion of the most general real number, then one may convince oneself, as Dedekind 8 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992

did and then went on to convince others, that the cut itself provides a "concrete" and intrinsic way in which to conceive of the number. To be convinced by this formulation one must accept a completed infinite. But as mathematicians explored the farther reaches of function t h e o r y - - t h e most general function that is represented by its Fourier series, nondifferentiable continuous functions, and, later on, one-to-one correspondences between the set of real numbers and the set of pairs of real numbers--their resistance to completed infinites weakened to the point of collapse and the Dedekind cut came to be seen as a completed infinite mild enough to be regarded as "concrete." Once this step had been taken, it was natural to regard an infinite set such as an ideal as being concrete. Never mind that the most general ideal, unlike the most general real number, could be described truly concretely by giving a set of generators. Once the exigencies of analysis had convinced mathematicians of the necessity of accepting some transfinite notions as "concrete," they felt forbidden to admit to any qualms about accepting ideals without generators as "concrete." The ideological climate of the time is reflected in a correspondence 3 between Georg Cantor and H. A. Schwarz in 1870. Cantor was pursuing the work of Riemann on functions representable by Fourier series, and he enlisted Schwarz's help in trying to prove a crucial lemma. Schwarz succeeded in proving the lemma, and the collaboration resulted in a substantial advance in the theory of Fourier series. However, there remained some doubt as to whether the proof was rigorous. At issue was the acceptability of a type of nonconstructive existence proof that Weierstrass was then introducing into function theory. Schwarz to Cantor (26 March 1870): "Herr Professor Heine writes me that he cannot declare himself to be in agreement with m y proof of the lemma, and therefore cannot concede that the theorem is settled; but since Herr Heine did not tell me what he found in my proof to take exception to, I have not been able to investigate whether his objection also vitiates the proof for me." Cantor to Schwarz (30 March 1870): The proof has been acknowledged by Herr Weierstrass to be completely rigorous; he specifically scrutinized your contribution to it and found it to be correct. He too has applied the Bolzano theorem and for example has given in his lectures the same proof of the theorem that 'if F'x = 0, then Fx = c" that you give in your letter; he therefore accepts your proof immediately. . . . You speak justifiably of the good fortune we have had to be able to call Weierstrass our teacher; I agree with all my soul . . . . By the way, Herr Kronecker also [in addition to Heine] finds himself in disagreement with the Weierstrass-Bolzano theorem on the lower and upper bounds z, but this will

3 Q u o t e d h e r e f r o m [15].

not prevent me from going ahead with the publication of my proof, because I consider this theorem not just correct but the foundation of the more important mathematical truths. There was probably an historical inevitability in the movement of analysis toward nonconstructive concepts and methods of proof at that time, and even in the ideological impact this movement had on algebra and number theory, but it is an interesting question whether this impact might have been reduced or even deflected altogether had Kronecker published his theory of divisors, as Kummer promised, soon after 1859. D e d e k i n d might never have d e v e l o p e d his theory of ideals, or might never have published it, and would certainly not have enjoyed a period of ten years during which his was the only available generalization of Kummer's theory to arbitrary algebraic number fields. The outcome of an earlier publication of Kronecker's theory would have depended, of course, on the form in which he presented it. When the Grundz~ige did appear in 1882, Weierstrass said of it that "It contains the results of many years of research in the most concise form. However, for readers who have not attended Kronecker's lectures it will be quite hard to understand, so that I fear it will at first be more admired than it is s t u d i e d " [16, p. 93]. I believe that Kronecker's works in general have been more admired than studied, the reason being that so many would-be students were frustrated in their attempts to read them. Camille Jordan said in the introduction to his Traitd des substitutions that he would not include an exposition of the relevant works of Kronecker "which today evoke the envy and the despair of pure mathematicians. ''4 In short, Jordan wanted to include Kronecker's results, but he could not master them. Kronecker did have an exceptional potential student in the person of Dedekind. When the Grundzage appeared, Dedekind did study it carefully and drew up a lengthy commentary on it [3]. Had Kronecker published his theory in, say, 1860, Dedekind would very likely have studied it at least as carefully as he did the later version, and the resulting interaction would have had an enormous impact on the subsequent development of algebraic number theory and of the foundations of mathematics generally. Kronecker intimates [11, w that the theory he finally published in 1881 was the same as the one Kummer had announced in 1859. Although it is hard to believe that twenty-two years of work by a mathematical intellect as powerful as Kronecker's would not have produced substantial modifications, there can be little doubt that the original version, like the published one, and like Kummer's, was based on a divisibility

4 See also Kronecker's collectedworks, vol. 3, part 1, p. 277.

Ernst Eduard Kummer

test. The divisibility test that Kronecker places at the beginning of his exposition of the divisor theory [11, w tests not for divisibility by an ideal prime factor, as Kummer's does, but for divisibility by the (ideal) greatest common divisor, prime or not, of a given set of elements. The test is not, however, presented as a divisibility test but is stated in the following peculiarly Kroneckerian way: THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992 9

Let (x1, (x2. . . . . ~ be algebraic integers. (As was mentioned above, Kronecker's theory applied also to algebraic functions. For the sake of simplicity, only the case of algebraic numbers will be considered at first.) Let ul, u2. . . . . u~ be indeterminates, and let f = o~lu1 + oL2u2 + 999+ cx~u~. Let K be the algebraic number field generated by the oL's and let Nf be the norm of f relative to the extension K D Q. (Kronecker does not introduce K and merely describes Nf somewhat inadequately as the product of all the conjugates of f. Nf is equal to the determinant of the matrix that represents multiplication by f relative to a basis of K over Q.) Then Nf is a polynomial (of degree [K:Q]) in the u's w i t h i n t e g e r coefficients. Let P be the g r e a t e s t common divisor of the coefficients of Nf. (It is a mystery to me why Kronecker chose to denote this integer with the letter P - - p e r h a p s , following Kummer, he was initially thinking of the case in which the divisor has norm a prime.) Let Fro(f), the "form" of f, be defined by Fm(t) = Nf/P. With this notation, Kronecker states that the greatest common divisor of ot1, ot2. . . . . % is "fully represented" by the fraction f/Fro(f). He justifies this assertion by stating and provings that for any coefficients v 1, v2, . . . , v K (including indeterminate coefficients), otlv1 + 0t2V2 + " " " + 0txVx is divisible by f/Fm(f) in the sense that (o~lv1 + ot2v2 + " " " + cL~v~) Fm(f)/f satisfies a polynomial equation with integer coefficients and with leading coefficient 1 and is not divisible by g/Fm(g) for any g = oL1u~ + c~2u~ + " " + (xKu'~. (It seems reasonable to interpret the first of these statements as meaning that f / F m ~ is a common divisor of (x1, ot2. . . . . otx, but I do not understand w h y the second should mean that it is the greatest common divisor--only that it is the greatest of this particular form.) Kronecker claims this representation of the greatest common divisor of the (x's by f / F m ~ makes it "appear 9. . in simple, understandable, natural form, in which . all the abstract properties used in the definitions of Kummer's ideal numbers as well as Dedekind's 'ideals' are united in a concrete algebraic object." In his introduction to w he claims, moreover, that f/Fm~) enables him actually to represent the greatest common divisor of the oL'swithout any symbolism and without the use of any abstraction. (Dedekind's comment: "For me, the notion of a 'form with variables' contains something far more abstract than that of an ideal, which seems to be thoroughly concrete as an assemblage of completely determined numbers having the two basic properties . . . . " [3, p. 60]) I cannot share Kronecker's enthusiasm for the representation of divisors by f/Fm(f), and feel that it is simply incorrect to say that this expression gives a representation of a divisor "ohne Symbolik." If f / F m ~ .

.

s Concerning the proof, see [3, p. 68] and [10]. 10 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992

were the divisor, then, for example, when K -----2, cx1 = 1, CX 2 = V2, f = u + V~v, g = x + V~y, both f/Fm(t) and g/Fm(g) would be the greatest common divisor of 1 and V~; therefore, one should have f / F m ~ = g/Fm(g) and therefore f" Fm(g) = g . Fm(f), which is obviously not the case because the left side has degree I in u and v while the right side has degree 2. The reason f/Fm(f) and g/Fm(g) are equal as divisors is given in Kronecker's next section [11, w VIII]: f/Fm(f) divides g and g/Fm(g) divides f. Thus, despite Kronecker's statement to the contrary, it seems to me that one must regard the representation of the divisor by f/Fro(f) as a symbolic one. To me, it is best seen as symbolizing a divisibility test:

An algebraic integer f3 is divisible by the greatest common divisor of the oL's if and only if f3 . Fm~/f is integral in the sense that its coefficients are algebraic integers. Since it is not obvious that 13 9 Fm(f)/f is a polynomial, it seems better to write Nf/P in place of Fm0~, so that the test is whether the coefficients of (13 9 Nf)/(fP) are algebraic integers. This expression is a polynomial because P is an integer a n d Nf/f is a polynomial. (When Nf is described as Kronecker does it, Nf/f is simply the product of the conjugates of f other than f itself.) Since an algebraic number ~ is by definition divisible by P if and only if ~//P is an algebraic integer, the divisibility test can also be stated:

An algebraic integer ~ is divisible by the greatest common divisor of the cx"s if and only if the coefficients of the polynomial ~ 9 Nf/f are all divisible by P. This undeniably concrete and explicit test seems to me to be the heart of Kronecker's theory. 6 As Kronecker wanted to indicate by his choice of title, 7 his treatise is far from complete9 In particular, the underlying philosophy is not explained. The treatise does contain, however, a number of grand pronouncements on basic principles, one of which provides a natural basis for the theory of divisors. In w he states that from the very beginning he was guided by the principle that the basic notions should remain unchanged when one passes from the rational to the algebraic, s For polynomials with rational coefficients (in one or in several indeterminates) the greatest

6 In terms more congenial to a mathematician of the 1990s, this test is an algorithm for determining w h e t h e r a given algebraic integer 13is in the ideal generated by cx1, ~2. . . . . ~x,. In fact, there is no n e e d to require j3 or the o~'s to be algebraic integers, because the same divisibility test applies to arbitrary algebraic numbers. 7 Dass viele z u m Thema gehOrige Fragen noch unerledigt geblieben, viele b e h a n d e l t e Punkte n/iher a u s z u f ~ h r e n sind, habe ich an d e n einzelnen SteUen der Arbeit selbst h e r v o r g e h o b e n u n d schon durch d e n Titel a n g e d e u t e t [11, Introduction].

8 Diese Erhaltung der Begriffsbestimmungen beim Uebergang vom Rationalen zum Algebraischen w a r die F o r d e r u n g , welche mir y o n v o r n herein als leitendes Princip bei d e r Behandlung der algebraischen Gr6ssen gedient hat.

Richard Dedekind

Leopold Kronecker

common divisor of the coefficients of the product of t w o p o l y n o m i a l s is the p r o d u c t of the g r e a t e s t common divisors of the factors. This, more or less, is Gauss's lemma. The same is not true for polynomials with algebraic coefficients because for such polynomials "the greatest common divisor of the coefficients" has no obvious meaning. Application of Kronecker's principle suggests that one attempt to define the greatest common divisor of the coefficients of a polynomial in such a way that this basic property survives the passage from the rational to the algebraic. This single idea provides a basis for Kronecker's fundamental divisibility test in the following way: Meaning is to be given to the statement that the greatest common divisor of the coefficients o f f = o~lu1 q- O~2U2 -F " ~ ~ -F C~KUK divides the greatest common divisor of the coefficients of g, where g is a polynomial whose only term is a constant ~. Let both f and g be multiplied by Nf/f. The greatest common divisor of the coefficients of f should divide the greatest common divisor of the coefficients of g if and only i f - - b y passage from the rational to the a l g e b r a i c - - t h e greatest common divisor of the coefficients of Nf = f . (Nf/f) divides the greatest common divisor of the coefficients of g 9 (Nf/f). But the greatest common divisor P of the coefficients of Nf is a perfectly meaningful rational number (Nf has rational coefficients) and it is perfectly meaningful to say that P divides the greatest common divisor of the coefficients of g 9 (Nf/f)--this means simply that the coefficients of g - (Nf/f) = g 9 (P. Fm(t)/f) are all divisible by P or, what is the same, that the coefficients of g. Fmq)/f are all algebraic integers. This is precisely Kronecker's test. Kummer defined the multiplicities with which cyclotomic integers were divisible by ideal prime factors and then proved a series of propositions showing that the properties suggested by "ideal primes" held, the main ones being that multiplicities combine in the ex-

Hermann Amandus Schwarz

pected w a y under addition and multiplication, and that a cyclotomic integer r divides another [3 if and only if no ideal prime factor divides a more times than it divides lB. Similarly, although Kronecker seems to feel that he is dealing with a deeper reality that justifies his divisibility test, the structure of his presentation is essentially that of a definition followed by justifying propositions. That is, the divisibility test defines greatest common divisors, and the following pages show that the expected properties of greatest common divisors all hold, one of which is that the greatest common divisor of the coefficients of a product of two polynomials is the product of the greatest common divisors of the factors. A n o t h e r - - b y no means obvious from the definition--is that the greatest common divisor of the a's divides each o~. (The proof of this is in fact the keystone of the theory.) A major difference between Kronecker's approach and the approach of Kummer and Dedekind is that Kronecker's is independent of the ambient field. Whether the greatest common divisor of 0% c~2. . . . . a~ divides depends only on the algebraic numbers o~1, a 2. . . . . r fB, not on the field in which they are considered to lie. Kummer's theory, by contrast, applies only to certain fields; for example, Kummer's theory applies to the field of 5th roots of unity but does not apply in an obvious way even to its subfield Q(V5), not to mention a nonabelian extension of the rationals such as Q(~'~). Dedekind's theory applies to any algebraic number field, but the fundamental concept, that of an ideal, is tied to the field under consideration. The ideal generated by a 1, o~2. . . . . cx~--which is Dedekind's equivalent of the greatest common divisor of the o ( s - depends entirely on the field in which the (x's are considered to lie, and if that field is extended the ideal must be extended accordingly. Both Kummer's and Dedekind's theories can be stated in terms of Kronecker's. In Kummer's original THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

11

theory, which applies to cyclotomic fields of prime exponent h, a prime divisor of a prime q # h can be found as follows: There is an element ~ of the cyclotomic field whose norm is q" times an integer relatively prime to q, where q" is the least power of q congruent to 1 rood ~. The greatest common divisor of q and ~ is a divisor of q that is prime in the cyclotomic field. In fact, in Kronecker's theory, the divisor of q is a product of such prime divisors-- (h - 1)/e distinct ones--conjugate to one another under the automorphisms c~~ oti of the field. Kronecker's test for divisibility by one of t h e s e divisors is e q u i v a l e n t to Kummer's test for divisibility by an ideal prime divisor (see box "Kummer's Original Definition"). The ideals of Dedekind's theory correspond one-to-one to the divisors of Kronecker's---the greatest common divisor of a set of generators giving the divisor corresponding to an ideal and the set of all field elements divisible by a 12

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

divisor giving the ideal corresponding to the divisor. The theorem on unique factorization into divisors prime in a given field which is fundamental to both Kummer and Dedekind is in essence the statement that an integral divisor irreducible in a given field is prime in that field, a proposition that is not difficult to prove. (An integral divisor is irreduciblein K if it cannot be written as a product of two integral divisors in K, neither of which divides 1. It is prime in K if it divides a product of integral divisors only when it divides one of the factors.) The equivalence of Kronecker's theory with Dedekind's in the case of algebraic number fields does not extend to all cases. Kronecker's theory begins with a ring----Z in the case of algebraic number t h e o r y - - i n which elements have greatest common divisors; then e l e m e n t s in its field of q u o t i e n t s have g r e a t e s t common divisors, and Kronecker's theory, passing

from the rational to the algebraic, defines greatest common divisors in algebraic extensions of the field of quotients. If one begins with the ring Q[x,y], which is a ring with unique factorization, the greatest common divisor of x and y is 1. Therefore, the greatest common divisor of x and y in Cl&y), or in any algebraic extension of it, divides t if and only if z is integral over Q[x,y]. The ideal generated by x and y is an ideal in Q[x,y] in Dedekind’s theory, but it does not contain all elements divisible by the greatest common divisor of x and y. Similarly, the ideal generated in Z[x] by 2 and x does not contain all elements (for example, it does not contain 1) divisible by the greatest common divisor of 2 and x. There are, of course, rings other than Z for which the two theories coincide. The most important is the ring Q[x], the ring of polynomials in one indeterminate with rational coefficients. Independently,

Kronecker and Dedekind found that in this case the theory is a useful tool in the study of algebraic curves. Gauss’s introduction to the last section of the Disquisitimes Arithmeticue had indicated close connections between number theory and the theory of lemniscatic functions, as well as “other transcendental functions.” The study of these connections was central to Kronecker’s work, and the principal objective of the Grundziige was to give a unified treatment of the theory of algebraic numbers and algebraic functions. For Dedekind, the main motive for the study of algebraic functions-rational functions on algebraic curves in particular-seems to have come from his collaboration with Heinrich Weber on the edition of Riemann’s collected works; however, he did write to Borchardt in 1877 that he had studied elliptic functions with complex multiplication “a number of years ago” (Dedekind’s We&e, vol. 1, p. 174) in connection with THE MATHEMATICAL U’JTELLIGENCER

VOL. 14, NO. 2,1992

13

the problem of determining the class numbers of cubic fields and "in my a t t e m p t s . . , to pave for myself an easy path into the exceptionally beautiful results of Kronecker, which unfortunately remain just as difficult to reach." The landmark paper of Dedekind and Weber [1] gave a completely algebraic development of the theory, up to and including the Riemann-Roch theorem, and thereby gave a rigorous basis for large portions of Riemann's work on Abelian functions, which had depended on the unproved Dirichlet principle. Let F(x,y) = 0 be a curve in the xy-plane, where F is an irreducible polynomial in two indeterminates with integer coefficients, and let (a,b) be a "point" on the curve in the sense that a and b are algebraic numbers for which F(a,b) = 0. Let K be the algebraic extension of Q[x] obtained by adjoining the algebraic numbers a and b, as well as a root y of the equation F(x,y) = 0, to the field of quotients Q(x) of Q[x]. As an algebraic extension of Q[x], K has a divisor theory, and the greatest common divisor of x - a and y - b is defined; let this divisor be denoted P. Provided (a,b) is a nonsingular point of F = 0, that is, provided the partial derivatives of F are not both zero at (a,b), the divisor P has the following property characteristic of divisors representing "points" in such fields. Any divisor can be written as a quotient of integral divisors, and the greatest common divisor of numerator and denominator can be cancelled to give a representation as a quotient of relatively prime integral divisors. An element u of K is said to be "zero at A," where A is an integral divisor, if A divides the numerator of the divisor of u when it is expressed as a quotient of relatively prime integral divisors. A divisor P that arises from a nonsingular point of F = 0 in the above way (which is of course integral, because x - a is integral over Q[x]) has the property that every element u of K has a "value" at P in the sense that either there is a constant c of K (an element of K algebraic over Q) such that u - c is zero at P or u = ~ at P in the sense that 1/u is zero at P. Let an integral divisor in K be called a place in K if it has this property that elements of K can be "'evaluated" at it in this way. Not only do nonsingular points correspond to places, but an arbitrary divisor in K can, when suitable constants are adjoined to K, be expressed as a product of powers of places. (In particular, if (a,b) is any point of F = 0, singular or not, then the greatest common divisor of x - a and y - b can be expressed, possibly after the adjunction of some constants, as a product of places. This expression amounts to a resolution of the singularity when (a,b) is singular.) There are two fundamental issues in this divisortheoretic formulation of the notion of a p o i n t - - o r , better, a p l a c e - - o n an algebraic curve that the Dedekind-Weber paper dealt with in a way that has been followed down to our own time but which can be han14

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

dled better by a more Kroneckerian approach. The first of these is the issue of what is today called the "ground field." The decomposition of a divisor as a product of powers of places requires, in general, the adjunction of constants, and therefore requires extending K. Since Kronecker's theory is independent of the ambient field, this poses no problems from the Kroneckerian point of view. The divisor theory (ideal theory) of Dedekind and Weber, however, assumes the ambient field to be fixed, which made it necessary for them to include all constants at the outset, that is, to replace Q[x] with the ring of polynomials with coefficients in an algebraically closed field. (Taking their inspiration as they did from Riemann, it was natural for them to start, as they did, with the ring C[x], but they did mention that they could have used the ring of polynomials with algebraic rather than complex coefficients [1, Introduction].) The necessity of using an algebraically closed ground field introduced--and has perpetuated for 110 y e a r s - - a fundamentally transcendental construction at the foundation of the theory of algebraic curves. Kronecker's approach, which calls for adjoining new constants algebraically as they are needed, is much more consonant with the nature of the subject. The other issue is independence of parameter. The above description of the point (a,b) on F = 0 as a divisor P in K depends, of course, on the divisor theory of K, which in turn depends on the description of K as an algebraic extension of Q[x], where x is a particular element of K. If another nonconstant element u of K is used in place of x, and if K is regarded as an algebraic extension of Q[u], a different divisor theory comes into play and some relationship between the two divisor-theoretic depictions of the point (a,b) must be established. Again, Dedekind-Weber's resolution of this matter has become fundamental to the modern approach. What they did, in essence, was to discard ideal theory altogether w h e n they passed from the local (the case when a particular parameter x ~ K is chosen) to the global. As was described above, a nonsingular point gives rise to a way of assigning to each element of K a value that is either a constant of K or ~. They d e f i n e d a " p o i n t " to be an a s s i g n m e n t of "values" K--~ K U oo that arises in this way [1, w This is a fairly satisfactory resolution of the matter; it certainly pleased Dedekind and W e b e r - - t h e y state twice in the space of their brief introduction that it gives a "fully precise and rigorous definition of a 'point' on a Riemann surface.'-9 It does have one shortcoming, however. It gives global meaning to what appear in the local theory as places (in the Dedekind-Weber theory, where the constants of K are an 9 Theycall it einer v611igprf~zisenund allgemeinen Definition des "Punktes der Riemannschen Flfiche' the firsttime, and eine vollkommen priizise und strenge Definition the second time.

algebraically closed field, a place is simply a prime ideal), but it gives no global meaning to divisors other than places. Thus, the theorem which states that every divisor is a product of powers of places has no global meaning because global divisors have no meaning except as products of powers of places. (The group of divisors is defined, in this tradition, as the free abelian group generated by the places.) I give what I regard as a better approach in my book Divisor Theory, where global divisors are defined, in essence, as collections

of local divisors that agree on overlaps in a natural way (see box "Divisor Theory and Algebraic Curves"). Although this global approach to divisors is not, as far as I know, to be found in Kronecker, I regard it as being entirely in the Kroneckerian spirit. Kronecker considered the notion of "divisor" to be more fundamental than that of "prime divisor" (which depends on the ambient field) and he would not have been satisfied by a theory that defined divisors in terms of prime divisors, as the Dedekind-Weber theory does.

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

15

16

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

Their different treatments of these issues reflect the ideological differences between Kronecker and Dedekind. Most evident, perhaps, is the differing attitude toward infinite processes reflected in Kronecker’s use of fields obtained by a finite number of algebraic or transcendental adjunctions to Q, as opposed to Dedekind and Weber’s algebraically closed ground field. Less evident is the related but even more fundamental issue of constructive existence proofs. For example, Dedekind and Weber [1, 93, 71 prove the existence of an integral basis by an argument that does not give a method of constructing one; in effect, they show if there is an integral element not representable in terms of a given basis, then the basis can be modified to produce a new basis that encompasses more integral elements, and they prove that the succession of enlargements produced in this way must terminate with an integral basis, but they do not give any method of determining whether there is a nonrepresentable integral element, or, if there is, any method of finding one. Kronecker, on the other hand, spells out an algorithm [ll, 571 for constructing an integral basis. All of the main theorems of divisor theory can be proved constructively. For example, the proof of the form of Abel’s theorem stated in the “Divisor Theory” box provides a means, given a divisor whose degree is the genus, of finding an equivalent integral divisor. (This construction is similar in spirit to Abel’s proof of the theorem. It shows that what is required can be described as a nontrivial solution of a homogeneous linear system in which the number of variables is greater than the number of equations.) An exception to this statement, at least as far as my

development of the theory is concerned, is the theorem that any divisor can be written as a product of powers of primes. It is easy to prove this constructively in the most important cases, those in which the basic ring is Z (algebraic number theory) or Q[x] (theory of algebraic curves), but in the general case I have been able to prove it only on the basis of the nonconstructive lemma: An integra2 divisor is either irreducible OY it is reducible.

Mathematicians dislike controversy. After all, the clarity and certainty of mathematics are its most attractive qualities and the envy of scholars in other fields. The distinction between constructive and nonconstructive proofs has been so thoroughly obliterated in modern mathematics that “not irreducible” and “reducible” are generally regarded as synonymous and the lemma above is perceived as a tautology. Of course, everyone understands that one might well be confronted with a particular divisor that one could neither factor nor prove to be irreducible, but the received opinion is that such a possibility is of no theoretical importance because the divisor is either factorable or irreducible, regardless of whether one can decide which it is. Leaving aside the question of what, if any, meaning could be given to this article of faith, the question of its impact on the development of modes of expression and thought deserves consideration. Several generations of mathematicians have now been THE MATHFMATICAL

INTELLICFNCER

VOL. 14, NO. 2,1992

17

trained to accept as valid an argument of the form "If the divisor is not irreducible, it can be written as a product of two divisors, neither of which is the unit d i v i s o r . L e t s u c h a p r o d u c t r e p r e s e n t a t i o n be given . . . . " The distinction between being unable to factor and being able to prove irreducibility is not directly denied by such an argument, but it is thrust so far into the background as to become invisible to most mathematicians. (Such a distinction can never be invisible to a n y o n e doing computations, a n d the influence of the more algorithmic thinking inspired by m o d e m computing has caused unease, if not reform, a m o n g mathematicians.) The form of Euclid's Proposition 1 of Book 1 comes as a surprise to m o d e m mathematicians: On a given finite straight line to construct an equilateral triangle. I~ Or Proposition 2: To place at a given point (as an extremity) a straight line equal to a given straight line. These propositions are clearly v e r y different from w h a t we call "propositions" a n d even from m a n y of Euclid's other propositions, such as Proposition 47 of Book 1: In right-angled triangles the square on the side subtending the right angle is equal to the squares on the sides containing the right angle. It does not matter whether the translator was using the w o r d "proposition" in a w a y that had some currency at the time he was writing or whether he was using it simply for lack of a better translation. The point is that Euclid's organization of his subject into "propositions" included constructions among the propositions. There are worse models t h a n Euclid, and I can see advantages in this practice. Instead of stating: "THEOREM. Any algebraic number field has an integral basis." a n d then emphasizing that the proof is constructive, one could state "'THEOREM. To construct an integral basis of an algebraic number field." and give the construction as the proof. The above apparently t a u t o l o g o u s l e m m a could be stated, " L E M M A . To factor a given integral divisor or prove it is irreducible." Mathematicians dislike controversy. After all, the clarity and certainty of mathematics are its most attractive qualities a n d the e n v y of scholars in other fields. W h e n confronted with a disagreement over a mathematical question, we mathematicians tend to become agitated a n d try to resolve it by finding one side to be entirely wrong and the other entirely right. To avoid provoking such agitation, I avoided mentioning in m y book on divisor theory the differences b e t w e e n the f u n d a m e n t a l p h i l o s o p h y of the Kroneckerian approach and the prevalent philosophy of mathematics. Instead, I have followed Kronecker's example H and presented what I hope is a coherent, nat-

m This and the following translations are from Heath [9]. 11Kronecker's reputation for disputatiousness is certainly undeserved as far as his published work is concerned, and may well be undeserved altogether [4], [5], [6], [7]. 18

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

ural, a n d c o n v i n c i n g d e v e l o p m e n t of the s u b j e c t w i t h o u t calling attention to the ways in which it differs from other approaches. However, I could not entirely avoid mentioning the essential point of difference. Section 1.7 of the book reads: The contemporary style of mathematics trains mathematicians to ask "What is a divisor?" and to want the answer to be framed in terms of set theory. Those trained in this tradition will want to think of a divisor as an equivalence class of polynomials, when equivalence of polynomials is the property of representing the same divisor. I believe, however, that instead of asking what a divisor is one should ask what it does. It divides things. Specifically, it divides (or does not divide) polynomials with coefficients in K. The definition of what a divisor does involves a given polynomial, and two polynomials represent the same divisor if the corresponding divisors do the same thing. To d e f i n e w h a t it m e a n s for a divisor to divide something, without defining w h a t the divisor is, is exactly w h a t K u m m e r did. K u m m e r evidently believed in 1846 that his contemporaries would find his definition of "ideal prime factors" satisfactory, but I am sure m y contemporaries will not. I do believe they will be more comfortable regarding it as an equivalence class of polynomials; some might even be more comfortable regarding it as the set of all elements in the algebraic closure divisible by the divisor. My chief concem is that this ideological difference not pose an obstacle to acceptance of the theory. But this is not to say that ideology is unimportant. The p u r p o s e of this s u r v e y of the history a n d the foundational questions of the theory of divisors is to s h o w some of the drawbacks of Dedekind's approach - - a s well as its non-algebraic g e n e s i s - - a n d some of the virtues of Kronecker's altemative. The conviction that set t h e o r y is the correct f o u n d a t i o n for mathematics is deeply e m b e d d e d in contemporary mathematical thinking, and it will not be displaced easily. Nonetheless, I hope that some readers will be encouraged to consider alternatives to set theory as a foundation, n o t only of divisor theory, but of the rest of mathematics as well.

Bibliography 1. R. Dedekind and H. Weber, Theorie der algebraischen Funktionen einer Ver/inderlichen, J. fiir Math. 92 (1882), 181-290. Also, Dedekind's Werke, vol. 1, 238-349. 2. H. M. Edwards, Postscript to "The Background of Kummer's Proof . . .", Arch. Hist. Exact Sci. 17 (1977), 381-394. 3. H. Edwards, O. Neumann, and W. Purkert, Dedekinds "Bunte Bemerkungen" zu Kroneckers "Grundz~ige", Arch. Hist. Exact Sci. 27 (1982), 49-85.

Acadelnic Wavelets A T u t o r i a l in T h e o r y a n d Applications edited by

Charles K. Chui A Volume in the WA VELETANAL YSIS AND ITSAPPLICATIONSSeries

Key Features

9 Covers severalofthe most important areas in wavelets, ranging from the development of the basic theory, such as: 9 Construction and analysis of wavelet bases, and 9 Introduction of some of the key applications, including Mallat' s local wavelet maxima technique in second generation image coding 9 Extensive bibliography is also included in this volume 9 Companion to the first volume in this series, An Introduction to Wavelets, and can be used as supplementary instructional material for a two-semester course on wavelet analysis January 1992,736pp., $69.95 ISBN:0-12-174590-2

Applications

An Introduction to Wavelets Charles K. Chui A Volume in the WAVELET ANAL YSIS AND ITSAPPLICATIONSSeries

Key Features

9 This is an introductory treatise on wavelet analysis, with an emphasis on spline-wavelets and time-frequency analysis 9 This monograph is self-contained, the only prerequisite being a basic knowledge of functiontheory and real analysis 9 Suitable as a textbook for a beginningcourse on wavelet analysis January 1992,288 pp., $49.95 ISBN:0-12-174584-8

Handbook of Differential Equations SECOND EDITION

Numerical Methods for Partial Differential Equations

Daniel Zwillinger

THIRD EDITION

Key Features

William F, Ames

9 Includes an expanded section on numerical methods 9 Presents new sections on finite difference formulas, grid generation, lattice gases, multigrid methods, parallel computers, and software availability 9 New and improved sections on chaos, existence, uniqueness, and stability theorems, inverse problems, normal forms, and exact partial differential equations have been included 9 Computer programs are given when possible January 1992,808pp., $54.95 ISBN:0-12-784391-4

Order from your local bookseller or directly from

W

ACADEMIC PRESS CAL,TOLLF.EE HarcourtBraceJovanovich, Publishers

1-800-321-5068

FAX: 1 - 8 0 0 - 2 3 5 - 0 2 5 6 Book Marketing Department #05042 Quotethis referencenumberfor freepostage 1250 Sixth Avenue, San Diego, CA 92101 andhandlingonyourprepaidorderw,O5042

A Volume in the COMPUTER SCIENCE AND SCIENTIFIC COMPUTING Series

Numerical Methods for Partial Differential Equations, Third Edition reflects the great

accomplishments that have taken place in scientific computation in the fifteen years since the second edition was published. This new edition is a drastic revision of the previous one, with new material on boundary elements, spectral methods, the methods of lines, and invariantmethods. At the same time, the new edition retains the self-contained nature of the older version, and shares the clarity of its exposition and the integrity of its presentation. March 1992,472pp. $59.95(tentative) ISBN:0-12-056761-X

Prices subJeCtto change without notice. ~, 1992 by Academic Press. Inc. All Rights Reserved. S LJSS --O5042.

4. H. M. Edwards, Dedekind's Invention of Ideals, Bull. Lend. Math. Soc. 15 (1983), 8-17. Also in Studies in the History of Mathematics (E. R. Phillips, ed.) MAA, 1988. 5. H. M. Edwards, A n Appreciation of Kronecker, Math. Intelligencer 9 (1987), 28-35. 6. H. M. Edwards, Kronecker's Place in History, History and Philosophy of Modern Mathematics (W. Aspray and P. Kitcher, eds.), Minnesota Studies in the Philosophy of Science, Vol. 11, Univ. of Minn. Press (1988), 139-144. 7. H. M. Edwards, Kronecker's views on the foundations of mathematics, Proceedings of a Conference held at Vassar College in June 1988 (D. Rowe and J. McCleary, eds.), Academic Press (1990). 8. H. M. Edwards, Divisor Theory, Boston: Birkh/iuser (1990) 9. The Thirteen Books of Euclid's Elements (translated, with an introduction a n d commentary by T. L. Heath) 2nd ed., Cambridge: Cambridge University Press (1925). Reprint: New York: Dover (1956). 10. A. Hurwitz, Uber einen Fundamentalsatz der arithmetischen Theorie der algebraischen GrOSen, G6tt. Nachr., Math.-phys. Kl. (1895), 230-240. Also Werke, vol. 2, 198-207. 11. L. Kronecker, Grundziige einer arithmetischen Theorie der algebraischen Gr6ssen, J. fiir Math. 92 (1882), 1-122. Also

12.

13. 14.

15.

16.

published separately by Reimer, Berlin, 1882, and Werke, vol. 2 (1897), 237-387. 12. E. E. Kummer, Zur Theorie der complexen Zahlen, Berlin. Monatsber. (1846), 87-96. Also, J. fiir Math. 35 (1846), 319-326, and Collected Papers, 203-210. E. E. Kummer, Theorie der idealen Primfactoren . . . , Berlin. Abh. (1856), 1-47. Also, Collected Papers, 583-629. E. E. Kummer, Ueber die allgemeinen Reciprocit/itsgesetze . . . . Berlin. Abh. (1859), 19-158. Also, Collected Papers, 699-838. W. Purkert, Cantors U n t e r s u c h u n g e n (iber die Eindeutigkeit der Fourierentwicklung im Lichte seines Briefwechsels mit H. A. Schwarz, NTM 24 (1987), 19-28. K. Weierstrass, Pis'ma Karla Vejergtrassa k Sof'e Kova-

levskoi: 1871-1891 (Briefe von Karl Weierstra]3 an Sofie Kowalewskaja) (P. Ja. Ko~ina-Polubarinova, ed.), Moscow (1973).

Courant Institute of Mathematical Sciences New York University New York, NY 10012 USA THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992 1 9

Order and Disorder in Algebraic Combinatorics* Phil Hanlon

"It is remarkable that in the international organization of the subject-matter of mathematics "Partitions" is considered to be a part of the Theory of Numbers, which is an alternative name for the Higher Arithmetic, whereas it is essentially a subdivision of Combinatory Analysis which is not considered to be within the purview of the Theory of Numbers"--Macmahon. There has always been a fuzzy area between Algebra and Combinatorics as observed by Major Percy Macm a h o n [14] some 75 years ago. But y o u hear the term "Algebraic C o m b i n a t o r i c s " m u c h more these days than you did even 25 years ago. What accounts for the increasing popularity of this field? W h y do Algebra and Combinatorics make a good mix? In this article, I hope to shed some light on these questions. The discussion will focus on two interesting, recent results in Algebraic Combinatorics. We will use these results to illustrate the nature of Algebraic Combinatorics and some reasons for the recent increase in interest in this area. Consider the following game which is played with a deck of n cards (numbered 1,2 . . . . . n). I turn the cards over one at a time. Before turning over each card I ask you to guess w h a t it is. You make y o u r guess and then I show y o u the card so that y o u k n o w w h e t h e r or not your guess was correct. Because y o u see the cards, you can keep track of w h a t cards have already been turned up and use that information to improve y o u r next guess. H o w m a n y guesses do you expect to get right? If the deck if perfectly shuffled (in other words, y o u have no

information about the order of the cards), then y o u r ith guess is correct with probability [n - (i - 1)] - 1. So the n u m b e r of guesses you expect to get correct is 1 E~(n)

=

-

n

1 +

~

(n -

1 1)

+

9 ..

+

+

1.

With a 52-card deck, the n u m b e r E~(52) is approximately 4.5. So with a "totally shuffled" deck of ordinary playing cards you should expect to get a r o u n d four a n d one-half guesses correct.

* Text of a plenary a d d r e s s given to the Canadian Mathematical Society at their a n n u a l m e e t i n g at the University of Waterloo in December 1990. The a u t h o r ' s work is partially s u p p o r t e d by grants from the National Science Foundation. 20 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2 9 1992SpringerVerlagNew York

At the other extreme, suppose you know that we are playing with a deck that has never been shuffled (card 1 on top, then card 2, then card 3, and so on). If you are at all on the ball you should get all n guesses correct. In this case, the number of guesses you expect to get correct is

[ x

x

[

Eo(n ) = n.

x

L

The situation of interest to us lies somewhere between these two extremes. We will open a new (unshuffled) deck, give the deck p riffle shuffles and then begin the game. Let E p ( n ) denote the number of guesses you expect to get correct if you employ the best possible strategy in making those guesses.

Problem 1: C o m p u t e the numbers

x

x

[

Figure 2

Ep(n).

Let me make a few comments about this problem. Recall that a riffle shuffle is where the deck is cut in two parts and these two parts are interleaved in some order. (See Figure 1.) To state Problem 1 precisely, we must make some assumptions about how this riffle , shuffling procedure is carried out. We will assume the following: (1) The probability that the cut occurs between cards i and i + 1 is (i)2-". (2) After this cut has been made, every interleaving of the two parts is equally likely.

run between consecutive x's (in the event of a tie, randomly choose one of the longest runs). Your ith guess is then the top card in this longest run. As mentioned earlier, Diaconis conjectures that this is the optimal strategy; it is still open to prove it. Problem 1 is a typical combinatorial problem. What makes it difficult is its seeming lack of structure. So many different permutations can result from a succession of riffle shuffles. It seems nearly impossible to describe the probability of achieving any given one with p shuffles. As with many combinatorial problems, there are too many possibilities and too little structure. Our second problem involves Hochschild homology of associative C-algebras. For A an associative algebra, we can construct a complex (C,,b,)

. . . . i

i+l

i+2

GUESS

LONGEST RUN

2 3

Cn

b__Z

....

where C, is the nth tensor power of A and the differential b, is defined by ht

vn~al

|

999

| any\

n-i

(--1) i-1 (al |

999|

aiai+l |

9 9 9|

an).

i=1

Figure 1 It is an interesting problem to determine the optim u m strategy for making guesses when you have been told that the deck has been given some number p of riffle shuffles. Problem 1 was suggested by Persi Diaconis, who also conjectures that the following guessing strategy is optimal for all p. To describe the strategy, I need to explain how to guess the ith card given that you know the first (i - 1) cards. In Figure 2 the (i - 1) cards that have already been turned up are marked by x's. You find the longest

It is straightforward to check that b, o b, + 1 = 0, so the image of bn+ 1 is contained in the kernel of bn. The H o c h s c h i l d h o m o l o g y o f A with trivial coefficients is the graded vector space with the nth graded piece Hn(A)

= k e r ( b , ) / i m ( b n+ l).

Consider the problem of trying to refine the Hochschild homology of A, that is, trying to split it into smaller pieces in some way that does not depend on A. One idea is to use the action of the symmetric group Sn on Cn (S, acts on Cn = A| by permutation of tensor THE MATHEMATICAL INTELLIGENCER VOL. 14, N O . 2, 1992

21

positions). Can we find permutations or linear combinations of permutations (one for each n) whose actions intertwine the boundary maps? Define an S-sequence to be a sequence (f,), where f, is in CS,, such that

Theorem 1. (Gerstenhaber and Schack [8]). There exists an infinite family of S-sequences, (%q)) for j = 1,2 . . . . . which satisfy

(a) (Triangularity) e. (j) = 0 if j > n. (b) (Universality) If ([,) is any S-sequence, then

f , _ lb,(a1 (~ . . . (~ a,,) = bnf,,(a 1 ( ~ . . . Q an) for all n and all a 1. . . . . a, (taken from any A). An S-sequence is a valuable thing to have. If (f,) is an S-sequence, then (f, Cn,b,) is a subcomplex of (C,,b,). If, in addition, the fn are idempotents, then the Hochschild complex splits as a direct sum of the subcomplexes

bn+2 fn+lCn+l b,+~ fnCn b, . . . . and

9 9 9 b'+2(1

- fn+l)Cn+l

b,+l. (1 - f,)C,

b,....

The homologies of these two subcomplexes give a direct sum splitting of H.(A). So an S-sequence of idempotents is exactly what we need to obtain, for it will give us, independently of A, a direct sum splitting of H.(A). A trivial example of an S-sequence is to take f, to be the identity permutation in Sn. Are there nontrivial sequences which are S-sequences for all A? The answer is no. Fortunately, that is not the end of the story. If we make the additional assumption that A is commutative, then there are interesting nontrivial S-sequences. For an example, let p, denote the permutation in S, which interchanges i and n + 1 - i for all i, Pn = (1,n)(2,n - 1) . . . . Then fn = ( - 1)"p, is an S-sequence. Let us check that f2b3(a(~b~c) = f3b3(a(~b(~c) under the assumption that a, b, and c come from a commutative ring A. We have b3f3(a(~b~c) = - b3(c ( ~ b ~ a ) = - cbQa + cQba and f2b3(aQbQc) = f2(abQc - aQbc) = cQab - bcQa, You can see that these two expressions are equal if A is commutative. Henceforth, we will assume that our algebras A are commutative. Can we determine or classify all S-sequences? This question is answered by the following beautiful result due to Gerstenhaber and Schack. 22

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

fn = E sgn(fj)en0), j=l where sgn(fj) is the number obtained from fj by applying the sign functional (i.e., by replacing each permutation with its sign). Because of the universal property, this theorem describes all S-sequences. Fix n for a moment. By triangularity, only the first n of these universal S-sequences have nonzero elements in CS,. It follows from a straightforward algebraic argument that these elements e, (1). . . . . e, ~") are pairwise orthogonal idempotents in CS n. Only the last one, e, (n), is a Young idempotent--the central idempotent corresponding to the sign character,

=

1

sgn(r162 o'~Sn

in CS4

e(4

e(42)

e(43)

in CS3

e(1)

e~2)

e~3)

in CS2

e~1)

e~2)

in CS1

et1)

Ssequence

Ssequence

Ssequence

e(44)

Ssequence

Theorem 1 is a typical algebraic result. It gives a simple, elegant solution to the seemingly difficult problem of finding all S-sequences. In some sense, it determines the idempotents e, (i). Gerstenhaber and Schack [8] and, indepedently, Loday [12] give explicit formulas which express the e,, (i) as linear combinations of permutations. In theory, formulas for the %(o should be enough to compute the pieces H(.~ in the Hodge decomposition for any particular algebra A. In practice, this can be difficult. The expressions for the en(i) obtained by Gerstenhaber and Schack and Loday are sums of a combinatorial nature. It is not clear from their expressions how to find a basis for e.(i)C. (or even the dimension of e,(~ Problem 2 is to find more explicit information about the e,(~

P r o b l e m 2: For a fixed c o m m u t a t i v e algebra A : 9 find a basis for e,,(aC,, = e,,(aA| 9 find an expression for the Euler characteristic of

~'~(A), •

= E

(-1)" dim(/-~d3(A))9

yl

In the second part of the problem we will assume some finite-dimensionality constraints on A such as that A be Nm-graded with finite dimension in each graded piece. This assures that dim(A | ) is finite in each graded piece, so we can safely assert that X(0 has the alternative expression X(0 = E

( - 1 ) n dim(e~)(A|

9

n

On the face of it, Algebraic Combinatorics represents an improbable match. Algebraic problems are set in situations that are rich with structure. Algebraists must be adept at bringing all this structure to bear on the questions they are considering. In combinatorial problems, chaos reigns. A typical combinatorial question involves a very complicated situation in which the structure is hidden rather than explicit. The job of the combinatorialist is to discover or impose some structure. Algebra and Combinatorics make a good combination just because they are so different. The strengths of one area match the weaknesses of the other. An algebraist will attack a problem by taking advantage of the algebraic structure to reduce it to something simpler. This simpler, less structured problem is often of a combinatorial nature. We see this in Problem 2. The Gerstenhaber-Schack theorem takes advantage of the algebraic structure inherent in the original problem of splitting the Hochschild homology. Their theorem reduces to Problem 2, which is essentially combinatorial. Another example is the problem of computing the homology of the affine variety obtained by removing a collection of subspaces from C n (or ~"). Goresky and Macpherson [9] (also see the work of Orlick and Solomon [15] on the hyperplane case) use deep methods from algebraic geometry to reduce this problem to the computation of the simplicial homology of a certain poset. In doing so, they distill the algebraic structure out of their problem to come up with a much less structured problem of a combinatorial nature. In the other direction, Algebra can be used to impose structure on a combinatorial problem. Problem 1 provides an example. It turns out that there is a great deal of structure to riffle shuffling. This structure is best described in algebraic rather than combinatorial terms. A second example is the situation that arises in Wilson's proof (see [19]) of the Erd6s-Ko-Rado theo-

rein. This theorem gives, for certain values of t ~ k n, the size of the largest family ~ of k-subsets of an n-set which has the property that any pair of subsets in intersect in at least t points. It is difficult to analyze the combinatorial structure of such families (see [4,5]). However, the multiplicity-free action of S, on the collection of k-subsets of an n-set imposes algebraic structure which Wilson used in his proof. These comments are pertinent at both the theoretical and computational levels. Combinatorialists are experts at doing computations. Unfortunately, their computations often become so complex and unwieldy that they are beyond the reach of modern supercomputers. By imposing structure on the computation, algebraic methods can reduce it to one of reasonable complexity. The article by D. B. Wales and this author [11] gives a case in point. For many algebraic problems, the most effective computational tools are combinatorial in nature. For example, the theory of symmetric functions originated with efforts to devise computational tools in the representation theory of the symmetric and general linear groups (see [13,18]). The computational power of Algebraic Combinatorics is a major reason for increased interest in the field during the last two decades. Sophisticated computing machinery has become a common commodity. With this increase in computational power has come renewed interest in effective computational methods, including those rooted in Algebraic Combinatorics. Bayer and Stillman's MACAULAY and John Stembridge's SF module in MAPLE are examples of commonly used software packages which utilize methods from Algebraic Combinatorics. In summary, I want to emphasize three points about Algebraic Combinatorics: (1) Algebra and Combinatorics are fundamentally different in nature. This improves their compatibility because the strengths of one area match the weaknesses of the other. (2) The interplay between Algebra and Combinatorics is a crucial ingredient in computational methods used by Algebraists and Combinatorialists. (3) Algebraic Combinatorics can reveal connections between seemingly unrelated problems in Algebra and Combinatorics.

Solutions Return now to the two problems put forth at the start of this article. We will comment on their solutions, beginning with the first one. We will sketch the solution to Problem 1 given by Bayer and Diaconis [2]. Recall that the numbers Ep(n) measure h o w well p riffle shuffles will mix up a deck of n cards. To make this more precise, consider the probability distribution THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

Dp on the symmetric group given by: Dp((r) is the probability that a new deck is put in the order cr by p riffle shuffles. The closer this distribution Dp is to uniform, the less you know about the ordering of the deck and the less you can expect to score in our game. So the numbers Ep(n) can be thought of as giving some measure of how close the distribution Dp is to the uniform distribution. Let T be the n! x n! matrix whose r entry is the probability that a deck in the order (r ends up in the order 9 after a single riffle shuffle. It is helpful to think of T as the transition matrix for a Markov chain on S,. The probability Dp(cr) is the 0rth entry in the vector TP(id). The matrix T has 1 as its unique eigenvalue of maximum modulus. The corresponding eigenvector has every entry equal to 1/n! (this eigenvector represents the uniform distribution). The distance of Dp from the uniform distribution is controlled by the eigenvalues of T in particular, the eigenvalue(s) of second highest modulus. The numbers Ep(n) can be computed from the eigenvalues and eigenvectors of T. This reformulates our problem in linear algebraic terms. As yet, we have not significantly reduced the complexity of the problem--the matrix T is every bit as complicated in combinatorial terms as a riffle shuffle. It is easy to see that Tr . . . . = T~,~ for all (r,~-,~ ~ S,, so T commutes with the fight-regular representation of S,. It follows that there exists an element sh E CSn such that T is the matrix for left-multiplication by sh. The key step in [2] is to consider the subalgebra ~ of CS, generated by sh. Clearly, ~ is a commutative, associative algebra with identity. The following remarkable fact is the basis of the Bayer-Diaconis solution.

Proposition. ~ is an n-dimensional, semisimple algebra. This proposition describes nontrivial algebraic structure enjoyed by sh (or equivalently by the riffle shuffling procedure). It is tempting to ask what this proposition means in combinatorial terms. It is a difficult question to answer because the structure imposed by this proposition is algebraic, not combinatorial. This demonstrates our first point: Algebra can introduce structure into a seemingly chaotic combinatorial problem. From standard algebraic results, it follows that ~ is spanned by pairwise orthogonal idempotents En(j), j = 1,2 . . . . . n. Bayer and Diaconis write d o w n expressions for these idempotents. They also establish the following elegant formula for the expansion of sh in terms of the En(j)'s:

sh = ~

2j-n Enq).

j=l

24 ThE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

It follows that the eigenvalues of sh (hence of T) are 1, 1//2, ~/4 . . . . . 1//2n--1. The eigenspace corresponding to the eigenvalue 2j-~ is En(j)CS~. Bayer and Diaconis use this information to obtain precise estimates for how quickly the distributions Dp approach the uniform distribution. For n = 52, they compute the following values for Ep(52):

p

Ep(52)

0

52.000

1

31.165

2

19.693

3

12.921

4

8.796

5

6.560

6

5.509

7

5.012

8

4.761

The solution to Problem 2 is more technical, and so we will say less about it. People working in Algebraic Combinatorics have independently studied the subalgebra of ~e C CS, spanned by the e,(j) (see the work of Solomon [16] and Garsia-Reutenauer [6]). The answer to the first part of Problem 2 follows from results in [6]. A concise Euler characteristic formula appears in [10] and gives an answer to the second part of Problem 2. In both cases, the pertinent results are proved using a mixture of combinatorial and algebraic methods. It is worth pointing out the recent work of Geller and Weibel [7], who use the above-mentioned Euler characteristic formula to compute Hodge decompositions of certain algebras A. These computations were important in their construction of a counterexample to a conjecture of Beilinson [3] and Soul6 [17]. This exemplifies our second point that the interplay between Algebra and Combinatorics is particularly useful at the computational level. On the face of it, there is no connection between the two problems discussed above. Let ~:GSn ---, CS, be the linear map which sends a permutation (r to sgn((r)or. Closer examination of the work in [2] and [6] reveals the amazing fact that e(en(j)) = En(j).

(*)

In fact, Problems 1 and 2 are intimately related by the equation (*). To better understand how this mathematical relationship translates into a concrete connection between the original problems, one must read the

articles by Bayer and Diaconis, Garsia and Reutenauer, and Gerstenhaber and Schack. However, this demonstrates the most valuable contribution made by Algebraic Combinatorics: It helps unify our increasingly disjointed mathematical world.

References 1. M. Barr, Harrison homology, Hochschild homology and triples, J. Algebra 8 (1968), 314-323. 2. D. Bayer and P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Prob. (to appear). 3. A. A. Beilinson, Higher regulators and values of L-functions, J. Soviet Math. 30 (1985), 2036-2070. 4. P. Erd6s, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. (Oxford) 12 (1961), 313-320. 5. P. Frankl, On intersecting families of finite sets, J. Combinatorial Theory A 24 (1978), 146-161. 6. A. Garsia and C. Reutenauer, A decomposition of Solomon's descent algebra, Adv. Math. 77 (1989), 189262. 7. S. Geller and C. Weibel, Lambda operations in HH, HC and K-theory, preprint. 8. M. Gerstenhaber and S. Schack, A Hodge-type decomposition for commutative algebra cohomology, J. Pure Appl. Algebra 48 (1987), 229-247. 9. M. Goresky and R. Macpherson, Stratified Morse Theory, New York: Springer-Verlag (1988). 10. P. Hanlon, The action of S, on the components of the Hodge decomposition of Hochschild homology, Michigan Math. J. 37 (1990), 105-124. 11. P. Hanlon and D. Wales, Computing the discriminants of Brauer's centralizer algebras, Math. Comput. 54 (No. 190) (1990), 771-796. 12. J.-L. Loday, Partition eul6rienne et op6rations en homologie cyclique. C. R. Acad. Sci. Paris S~r. I Math. 307 (1988), 283-286. 13. I. G. Macdonald, Symmetric Functions and Hall Polynomials, New York: Oxford University Press (1979). 14. P. Macmahon, Combinatory Analysis, Vol. 1, New York: Chelsea (1917). 15. P. Orlick and L. Solomon, Combinatorics and topology of complements of hyperplanes, Inv. Math. 56 (1980), 167-189. 16. L. Solomon, A Mackey formula in the group ring of a Coxeter group, J. Algebra 41 (1976), 255-268. 17. C. SoulG Operations en K-th~orie alg6brique, Canad. J. Math. 37 (No. 3) (1985), 488-550. 18. R. Stanley, Theory and applications of plane partitions: Parts I, II, Stud. Appl. Math, 50 (1971), 167-188, 259-279. 19. R. Wilson, The exact bound in the Erd6s-Ko-Rado Theorem, Combinatorica 4 (No. 2-3) (1984), 247-257.

Department of Mathematics University of Michigan Ann Arbor, MI 48109-1003 USA

Harold M. E d w a r d s

Divisor Theory Kronecker's theory of divisors, like Dedekind's theory of ideals, is a broad generalization of Kummer's original theory of "ideal prime factors" in cyclotomic fields. Kronecker never gave an elaborate treatment of the theory of divisors, and the few writers who have done so have failed to show its simplicity, its scope, and its advantages over the now-familiar Dedekind theory. Edwards gives a full development of a general theory of divisors (including topics not treated by Kronecker), together with applications to algebraic number theory and to the theory of algebraic curves. An Appendix on differentials makes possible the statement and proof of the Riemann-Roch theorem for curves.

This book of H. M. Edwards presents in a modern approach a remarkable algebraic technique. [...] it is interesting for both the historian of mathematics and the working specialist in commutative algebra, number theory and algebraic geometry. D. Stefanescu Zentralblatt THREE EASY WAYS TO ORDER ! DIVISOR THEORY by Harold M. Edwards 1990/166 p p / H a r d c o v e r ISBN 0-8176-3448-7 / $34.50 CALL: TOLL-FREE 1-800-777-4643 In NJ please call 201-348-4033 WRITE: Send payment plus $2.50 for postage and handling to: Birkhiuser, Order Fulfillment Dept., Y 578 IN) Box 2485, Secaucus, NJ 07096-2491. VISIT: Your Local Technical Bookstore. Visa, MasterCard, American Express and Discover Charge Cards, as well as personal checks and money orders are acceptable forms or payment. All orders will be processed upon receipt. If an order cannot be fulfilled within 90 days, payment will be refunded. Payable in U.S. currency or its equivalent.

~ Birkhiiuser Boston

Basel

Berlin

THE MATHEMATICAL[NTELLIGENCERVOL. 14, NO. 2, 1992 25

Anatoly Ivanovich Maltsev Radoslav Dimitri(

The Novosibirsk State University, the Institute of Mathematics of the Siberian branch of the USSR Academy of Sciences, and the Siberian Mathematical Society organized an International Conference on Algebra in Akademgorodok from 21 to 26 August 1989. The conference was sponsored by the International Mathematical Union and the Novosibirsk Systems Institute; it honored the eightieth anniversary of the birth of a prominent Soviet mathematician, Anatoly Ivanovich Maltsev (transliterated also as Mal'cev or Malcev). The city of Novosibirsk, together with the town of Akademgorodok (on the banks of the Obsk water reservoir 28 km away), is rightly considered the science center of Siberia. It was founded in 1893 by GarinMikhailovsky, a writer and traveller, on the confluence of the rivers Kamenka and Ob, and its history almost entirely falls within the period since the October revolution. This city's existence is a confirmation of the forecast by M. V. Lomonosov that "The might of Russia will grow through Siberia." The Siberian branch of the USSR Academy of Science was founded in 1957, mainly due to the enthusiastic efforts of the academician M. A. Lavrentiev. The Academy comprises 21 research institutes engaged in fundamental research. The full staff of Akademgorodok consists of about 30,000 people, including about 40 academicians and corresponding members of the Academy. The number of students at the University is relatively small---only about 4000. As in several other places in the Soviet Union, there is a boarding school (named after the academician Lavrentiev) for children talented in mathematics and physics. There are around 550 pupils in the ninth and tenth classes of the 26

school, a number of them drawn from the winners of Siberian mathematical olympiads, and about half of these winners come from the small towns and villages of Siberia, Kazakhstan, the Central Asian republics, and the Far East, and comprise more than 20 Soviet nationalities. There is also a technology club for children from the first to the tenth classes. This concentrated intellectual power of all ages produces remarkable results in all branches of fundamental science. The international organizing committee was chaired by Professor Yu. L. Ershov, Maltsev's student and

THE MATHEMATICAL INTELLIGENCER VOL, 14, NO, 2 9 1992 Springer-Verlag New York

Anatoly I. Maltsev.

successor in Novosibirsk (and the present rector of the university). The conference attracted 750-800 participants with perhaps 300 foreign participants. Many established names in algebra, whether their work was or was not related to that of A. I. Maltsev, were there and the conference gave a glimpse of contemporary research in algebra in the USSR and worldwide. The major fields represented were model theory and algebraic systems, group theory, algebraic geometry, algebraic methods in geometry, analysis and theoretical physics, applied and computer algebra, ring theory, and theory of modules and algebras. Anatoly Ivanovich Maltsev was born on 27 November 1909 in Misheronsky district near Moscow, as the son of a highly qualified glass-blower and once a glass factory director. After completing high school in 1927 he studied mathematics at Moscow State University and graduated in 1931. In the period from 1932 to 1960, Maltsev worked in the Ivanovo Pedagogical Institute near Moscow. His first paper [1] was an original and i n d e p e n d e n t contribution to logic and model theory; in it, he developed deep ideas on the general method of obtaining local theorems especially for the

language of restricted predicate calculus. The following Compactness Theorem is quite famous [2]: Let ~ be an infinite collection of closed first-order formulas of signature fL If every finite subset of 9 is consistent (i.e., there exists an algebraic system of signature ~ in which each formula of the collection is true), then the entire collection is consistent. It is worth noting that for finite or countable signatures this theorem follows from G6del's Completeness Theorem. Maltsev also proved analogous theorems concerning infinite models such as the following: If every finite reduct (A~, ~ ) of every finite submodel (A~, 1~) of an algebraic system 1I = (A, f~) is embeddable in some system ~2f~,~ = (M~,,,, f~), then 1I is embeddable in some ultraproduct of the system M~,,. A local method, rightly called Maltsev's compactness theorems, connecting infinite systems with finite subsystems, is a powerful m e t h o d in algebra and model theory, Abraham Robinson used a similar idea later to substantiate his results in nonstandard analysis. Applications in group theory include local theorems for classes of groups having central or solvable systems. THE MATHEMATICAL 1NTELLIGENCER VOL. 14, NO. 2, 1992

27

Maltsev's career was crucially affected by Andrei Nikolaevich Kolmogorov, a guru of Soviet mathematics who invited Maltsev to study with him in a graduate program. Maltsev always considered himself a student of Kolmogorov, and the friendship was more than just that of an official teacher-student relationship. A minute indication of this was a couple of 1000-kin-long trips down the river Volga, in a simple rowboat containing--besides a pet dog--Maltsev, Kolmogorov, Alexandrov, and Nikolskii, w h o shared thoughts and mathematics during their adventurous trips. Maltsev's paper [3] on the embeddability of a ring into a field was his answer to a question of Kolmogorov and led him in 1939 to be the first to give the necessary and sufficient conditions for the embeddability of a semigroup into a group [4]. The set of necessary and sufficient conditions for the embeddability is in fact countable (in terms of systems of equations) and Maltsev had also shown that no finite subset of these conditions w o u l d suffice to ensure embeddability of a semigroup into a group. His other noteworthy result in the area of semigroups dates from 1952 and states that the lattice of congruences of the semigroup of all functions X ~ X, for an arbitrary set X, is generated qua lattice by congruences of three simple kinds. In 1937 Maltsev defended his dissertation (under Kolmogorov) for a candidate of physics and mathematical sciences in the then flourishing area of "Torsion-free abelian groups of finite rank." He defended his dissertation for the degree of doctor of science in 1941 under the title "Structure of isomorphicaUy representable infinite algebras and groups." Promotion to a professorship came in 1944. Note that Maltsev carefully followed current trends in mathematics, as reflected in the themes of the papers he published. He was for instance the first to use category theory in the Soviet Union. Maltsev discovered important results on representation of infinite linear groups by matrices [5]. Examples include the result on finite approximability of a free group and the theorem that there are countably many locally free groups of finite general rank. A theorem, now called the Maltsev-Kolchin theorem, states that every solvable linear group over an algebraically closed field has a triangulated normal subgroup of finite index that does not exceed a finite integer depending only on the form of the matrices [6]. Another theorem in this area states that every solvable group of integer matrices is polycyclic. The converse of this theorem was proved by Swan and Auslander independently (using different methods) in 1967. Among Maltsev's most important works in algebra are those in the area of Lie groups and algebras. For instance, Maltsev proved that the well-known result of Cartan on embedding of an arbitrary Lie group into a 28

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

complete Lie group cannot be extended to the class of local topological groups [7]. He proved in 1943 that a necessary and sufficient condition for a Lie group to have a faithful linear representation is that the radical of the Lie group as well as its factor group mod this radical have such a representation [8]. It had been known that not every connected Lie group could be reconstructed uniquely from its Lie algebra. The notion of a rational submodule of a Lie algebra introduced by Maltsev characterizes a Lie group uniquely up to finite-leaved coverings [9]-[12]. He described all semisimple subgroups of simple Lie groups of infinite and exceptional classes and proved the conjugacy of semisimple factors in the Levi decomposition of a Lie group or algebra [13], [14]. He also proved a theorem on uniqueness (up to conjugacy) of a Wederburn decomposition of a finite-dimensional associative algebra--a result generalized to other classes of algebras such as alternative and Jordan algebras. Another of Maltsev's contributions is an affirmative solution to Cartan's problem on conjugacy of maximal connected compact subgroups of a connected Lie group G: if F is such a subgroup, then G is homeomorphic to the cartesian product of F and the n-dimensional Euclidean space Rn [12]. These results were generalized to a wider class of topological groups [15] and some of the contributions in this area independently overlapped with those of C. Chevalley, who pointed out a few errors in Maltsev's original paper (see Math. Rev., vol. 7, 1946). One of Maltsev's papers of 1949 deals with nilpotent varieties, i.e., homogeneous spaces with transitive actions of nilpotent Lie groups [16]. He proved that the fundamental group of a nilpotent variety is a finitely g e n e r a t e d nilpotent torsion-free group and conversely, every discrete group with these properties is the fundamental group of a compact nilpotent variety; this variety is uniquely determined by its fundamental group. He also proved a celebrated theorem on the existence and uniqueness of locally nilpotent torsion-free groups [17]. Several papers from the 1950s were concerned with a general theory of topological algebraic systems [18], [19], most importantly the general theory of free topological algebras [20]. Maltsev algebras represent a natural generalization of Lie algebras nested between Lie algebras and binary Lie algebras. A nonassociative anticommutative algebra satisfying the identity J(x,y,xz) = l(x,y,z)x, where l(x,y,z) = (xy)z + (yz)x + (zx)y is the Jacobian of the elements x,y,z, is called a Maltsev algebra (initially called by their creator a Moufang-Lie algebra). For instance, every Lie algebra is a Maltsev algebra. O n the other hand, every two-generated Maltsev algebra (binary Lie algebra) is a Lie algebra. Alternative algebras, Jordan algebras, and Maltsev algebras, together with Lie algebras, are the basic and most extensively studied classes of nonassociative al-

gebras--closely connected with associative algebras; they are sometimes called "algebras close to associative algebras." M a l t s e v w a s e l e c t e d a m e m b e r of the USSR Academy of Sciences in 1958. In 1959 he became the editor in chief of the Siberian Mathematical Journal and established the journal Algebra i logika. Seminar. In 1960 he began his professorship at the Mathematics Institute in Novosibirsk, as well as the headship of the Department of Algebra and Mathematical Logic at the Novosibirsk State University. He became the president of the Siberian Mathematical Society in 1963. From this period, his contributions to mathematics are more in the area of model theory with applications to algebra as well as vice versa. For example, one of the results about the elementary properties of groups (i.e., properties expressible in the language of restricted predicate calculus) states that the elementary theory of finite groups is undecidable [21]. He solved some questions on decidability of various elementary theories, e.g., he proved the undecidability of the elementary theory of free nilpotent groups [22] and that of free solvable groups and of some fields; he also showed that the class of locally free algebras has a decidable theory. ~Fhe theory of algebraic systems--especially varieties and quasivarieties of systems and their characterizations with operations b e t w e e n t h e m - - w a s begun by Maltsev [23]-[26]. He planned to publish a two-volume book in the area of the interaction of mathematical logic and algebra. Only the first volume was published posthumously in 1970, entitled Algebraic Systems [2], which included elementary structures, predicate calculus, and the theory of quasivarieties. Maltsev also established foundations for the theory of constructive algebras--a synthesis of the theory of algebraic systems and the theory of algorithms [27]. In his latter years he devoted much time to thinking about the applications and philosophy of mathematics. He defined a general theory of numeration, enumerated sets, and enumerated classes as well as complete numerations. All these results are in a celebrated book Algorithms and Recursive Functions [28], 1965. His textbook Foundations of Linear Algebra is well known. All his books have been translated into English and other foreign languages. One of Maltsev's unfulfilled wishes was to establish an international mathematical institute in Novosibirsk, but he soon changed his mind about the location as he thought that the cold Siberian winter would deter people from coming (as it is, Siberian winters are about 10~ Celsius warmer than they were 20 years ago). Maltsev was a recipient of major USSR prizes of recognition for intellectual achievements, including the Lenin Prize. Maltsev died on the night 6/7th of July 1967 during an international topological congress in Novosibirsk

Mathematics Institute, Akademgorodok.

Some of Maltsev's books.

for which he was the president of the organizing committee. He was the first of the scientists to be buried in the new Akademgorodok cemetery. (Lavrentiev and some other mathematicians are also buried there.) Maltsev liked very long walks and long-distance swimming. He played the violin from a very early age until he was 30, when he switched to piano---a diversion from his hard work on mathematics that he enjoyed wholeheartedly. He liked history and there are a number of volumes on this subject in his library, including the history of mathematics. For example, a copy of E. T. Bell's Men of Mathematics (in English) and a book by Mark Twain (in Russian translation) are on the shelf. The bookcases also contain his unfinished mathematical papers. Maltsev's widow, Nataly Hostic Maltsev (a university tutor in mathematics) lives in their house in the street named after Maltsev. Two of THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

29

M a l t s e v ' s s o n s - - A n d r e i A. M a l t s e v (a p r o f e s s o r at the N o v o s i b i r s k State University) a n d A r k a d y A. M a l t s e v ( p r o f e s s o r at t h e S t e k l o w M a t h e m a t i c a l Institute) are also m a t h e m a t i c i a n s .

15. 16. 17.

Selected B i b l i o g r a p h y 18. 1. Untersuchungen aus dem Gebiete der mathematischen Logik, Mat. Sb. 1(43) (1936), no. 3, 323-336. 2. Algebraic Systems, Springer-Verlag, 1973. 3. On the immersion of an algebraic ring into a field, Math. Ann. 113 (1937), 686-691. 4. On the embeddability of associative systems into groups I, II, Mat. Sb. 6, 8 (1939), no. 2 and (1940), no. 2, 331-336 and 251-264. 5. On the faithful representation of infinite groups by matrices, Mat. Sb. 8 (1940), no. 3, 405-421 and the AMS translation, Ser II, 45 (1965), 1-18. 6. On some classes of infinite solvable groups, Math. Sb. 28 (1951), no. 3, 567-588. 7. On local and complete topological groups, Dokl. A N USSR 32 (1941), no. 9, 606-608. 8. On linearly connected locally-closed groups, Dokl. A N USSR 40 (1943), no. 3, 108-110. 9. On single connectedness of normal zero-divisors of a Lie group, DokI. A N USSR 34 (1942), no. 1, 12-15. 10. Subgroups of Lie groups in the large, Dokl. A N USSR 36 (1942), no. 1, 5-8. 11. On the structure of Lie groups in the large, Dokl. AN USSR 37 (1942), no. 1, 3-6. 12. On the theory of the Lie groups in the large, Mat. Sb. 16(58) (1945), no. 2, 163-190; Corrections to the above: Mat. Sb. 19 (61) (1946), 523--524. 13. On a decomposition of an algebra into the direct sum of the radical a n d a semisimple subalgebra, Dokl. A N USSR 36 (1942), no. 2, 46-50. 14. On semisimple subgroups of Lie groups, Izv. A N USSR,

Lavrentiev's grave. 30

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

19. 20. 21. 22. 23. 24. 25. 26. 27. 28.

mat. 8 (1944), no. 4, 143-174; A M S Translations 33 (1950), 43p. On solvable topological groups, Mat. Sb. 16 (1945), no. 2, 163-189; AMS Translations 43 (1951), 14p. On a class of homogeneous spaces, Izv. A N USSR, mat. 13 (1949), no. 1, 9-32; AMS Translations 39 (1951), 33p. Nilpotent torsion-free groups, Izv. AN USSR, mat. 13 (1949), no. 3, 201-212. On the general theory of algebraic systems, Mat. Sb. 35 (1954), no. 1, 3-20; AMS Translations, Ser. II, 27 (1963), 125-142. Analytic loops, Mat. Sb. 36 (1955), no. 3, 569-576. Free topological algebras, Izv. A N USSR, mat. 21 (1957), no. 2, 171-198; A M S Translations, Ser II, 17 (1961), 173-200. Undecidability of the elementary theory of finite groups, Dokl. A N USSR 138 (1961), no. 4, 771-774; Soviet Math. Doklady 2 (1961), 714-717. On free soluable groups, Dokl. A N USSR 130 (1960), no. 3, 495-498; Soviet Math. Doklady 1 (1960), 65--68. Groups and other algebraic systems, Mathematics, its content, methods and meaning, Moscow, A N USSR 3 (1956), 248-331. On some bordering questions of algebra and mathematical logic, International Mathematical Congress, Moscow, 1966 (1968), 217-231. Several remarks on quasivarieties of algebraic systems, Algebra and Logic. Seminar 5 (1966), no. 3, 3-9. On multiplication of classes of algebraic systems. Sib. Math. J. 8 (1967), no. 2, 346-365. Constructive algebras I. Usp. Mat. Nauk 16 (1961), no. 3, 3-60; Russian Math. Surveys 16 (1961), no. 3, 77-129. Algorithms and recursive functions, Groningen: WalterNoordhoff Publishing, 1972.

Department of Mathematics Stanford University Stanford, CA 94305 USA

Maltsev's grave.

W. H . F R E E M A N A N D C O M P A N Y EXPLORINGTHEFRONTIERSOFMATHEMATICS Push the power of Mathematica to its limits Mathematica in Action Stan Wagon, Macalester College Stan Wagon, well known to readers of the Mathematical Intelligencer, explores the extraordinary capabilities and virtually limitless potential ofMathematica| for advanced mathematics in this thorough guide.

Mathematica in Action extends your imagination and the power of the program by providing alternative methods to generate threedimensional graphics, iterative graphics, and animations9 Its many valuable shortcuts, complete programs with line-by-line explanations, and hundreds of advanced examples worked in detail help you realize those aims. Whether you are a mathematics teacher, researcher, or enthusiast, you'll find this to be the indispensable sourcebook to own because of i t s 9 detailed examples that use animations to study dynamical systems and Julia Sets 9 attention to high-precision number theory--including many aspects of prime numbers 9 in-depth study of cycloids

Contents A Brief Introduction 9 Prime Numbers 9Rolling Circles 9Surfaces 9 Iterative Graphics 9 Iterative Complex Graphics 9 The Turtle Road to Recursion 9 Advanced Three-Dimensional Graphics 9Some Algorithms of Number Theory 9 Imaginary Primes and Prime Imaginaries 9 Additional Examples 9 . . . . . . Appendix: Supplementary Programs

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

==

Mail to:

1991, 352 pages, 133 illustrations, 4 pp. color plates paper (2202-X) $29.95; cloth (2229-1) $39.95

W.H. Freemanand Company 4419 West 1980 South, Salt Lake City, UT 84104

A remarkable visual exploration of the world of fractals and chaos in a 63-minute, full-color video-FRACTALS: An Animated Discussion

Send m e _ _ copies of FRACTALS: An Animated D i s c u s s i o n ,

with EDWARD LORENZ and BENOIT B. MANDELBROT

(2213-5), individual price $59.95

by H.-O. Peitgen, H. Jiirgens, D. Saupe, C. Zahlten

Educational price $149.95 (includes licensing and duplication rights)

Join the scientific pioneers of Fractal Geometry as they discuss their work and present exciting color animations of the world of fractals, chaos, and self-similarity. The video turns the Mandelbrot set and the Lorenz attractor into visible and easily comprehensible objects as their discoverers, Benoit B. Mandelbrot and Edward Lorenz, discuss the background, history, and details of their work in extended interviews. A 28-page booklet accompanies the video. In it, you'll find the algorithms and mathematical equations that underlie the fractals featured in the video. 1991, VHS, color video, 63 minutes, 995 individual price; $149.95 educational price ; and duplication rights)

Send m e _ _ c o p i e s

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

in

Action, paper (2202-X), at $29.95 hardbound (2229-1), at $39.95

Add $1.95 shipping and handling for the first item $1.25 for each additional item UT, CA, and NY residents please add the appropriate sales tax Total [] I enclose a check or money order payable to

W. H. F r e e m a n and Company Charge to my

[] MasterCard

[] Visa

Expiration date Account # Signature (credit card orders must be

signed)

Name Address

W. H. F r e e m a n and C o m p a n y The book p u b l i s h i n g a r m o f S c i e n t i f i c A m e r i c a n

City State/Zip J701

Symmetry Groups of Fractals C. Alexander, I. Giblin, and D. Newton

This paper contains computer pictures of generalised Mandelbrot and Mandelbar sets, and their associated Julia sets, from which it is evident that their symmetry groups possess an elegant and simple structure. We show that (i) the Mandelbrot set M(p) generated by the iteration zt+ ~ = ztp + c remains invariant under the symmetry transforms of the dihedral group Dp_ 1 (i.e., these are isomet-ries of M(p)); (ii) the Mandelbar set M(p) is invariant under the isometries inDp + 1; and (iii) the Julia sets of points inside M(p) (or M(p)) are invariant under the isometries in either Dp or just the cyclic

32

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2 9 1992

group Cp, depending on whether the seed point is on or off a symmetry axis of the parent Mandelbrot (or Mandelbar) set. The proofs are relatively easy, but showing that there are no other isometries of these sets is not so straightforward. As is often the case in the theory of chaos, what is obvious geometrically is difficult to prove analytically. For the generalised Mandelbrot and Mandelbar sets with even p we have in fact proved that the dihedral symmetry transforms are the only isometries of these sets, but the method does not appear to be applicable to odd p, or to the Julia sets.

Springer Verlag New

York

The S y m m e t r y of Fractals Deterministic fractals possess an incredible amount of symmetry. Indeed, one of their fundamental properties is that of "self-similarity" or "scale-invariance." This could be taken to mean that a deterministic fractal is a fixed point of certain types of contraction mapping (Barnsley, 1988), for example, a similitude (an affine transformation which preserves angles but not distances). But the symmetry of some deterministic fractals may also be described by another type of invariance, under affine transformations that preserve distances as well as angles, i.e., isometries. The set of all such isometries forms the symmetry group of the fractal object. To distinguish between the two types of invariance we construct a deterministic fractal using the iterative procedure illustrated in Figure 1. At each step every square is replaced by five smaller squares as shown, and the structure becomes a fractal of dimension log5/ log3 as k --* ~. The self-similarity of this object in R 2 is captured by the similitude f(x,y) = V3(-y, x), i.e., rotation through 90 ~ plus contraction by a scale factor of 1/9. The fractal is a union of five translations of its image 9 under f, in one-to-one correspondence with its image under f. On the other hand, the fractal is invariant under two types of orthogonal transformations of R2: rotations through 90n ~ (n = 1. . . . . 4) and reflections through its four axes of symmetry. The complete set of such transformations is of course the dihedral group of order 8 D 4 = {a, b la 4 = b2 = (ab)2 = 1}, where a denotes a rotation through 90~ and b is any reflection. The fractal in Figure 1 has a very simple geometric structure, unlike the most famous family of fractals, the Mandelbrot set and its relatives. Self-similarity in the Mandelbrot family is not easy to capture--how could one even attempt to specify a contraction mapping (on the space of non-empty compact subsets of C with the Hausdorff metric) which has the Mandelbrot set as fixed point? By contrast, it seems easy enough to

write down its symmetry group: Reflection through the real axis is the only apparent isometry of the Mandelbrot set (in addition to the identity, of course). For positive integer m, denote by Cm the cyclic group of order m, and let D m = {a, b l a m = b2 = (ab)2 = 1}. So for m /> 3, D m is the symmetry group of rotations and reflections of a regular plane m-gon, D 2 ~ C2 X C 2 the Klein four group, and D 1 -'="C2. Now for a fixed positive integer p and complex numbers z and c, let P(z,c;p) = z p + c and Q(z,c;p) = ~P + c. If F" denotes n-fold composition of the function F, then M(p) = {c E C I Pn(O,c;P) -4* o~} and M(p) = {c E C I Q"(O;c;p) ~ oo} denote the generalised Mandelbrot and Mandelbar sets, respectively. These are illustrated in Figures 2 to 7 for the cases p = 2, 3 and 4. For points c E M(p), denote the corresponding Julia set (defined in the next section) by J(p,c) and_ similarly, J(p,c) denotes the Julia sets for points c E M(p). Several of these are shown in figures 8 to 13. The geometry of these pictures of Mandelbrot, Mandelbar and Julia sets promotes the following observations on the structure of their symmetry groups: 1. For every integer p >i 2, M(p) has symmetry group Dp_ 1 and M (p) has symmetry group Dp+ 1. 2. Let S(p) denote the symmetry axes of M(p). Then J(p,c) has symmetry group Cp ~ c ~ S(p) and symmetry group Dp ~:~ c ~ S(p). 3. The symmetry groups of the Mandelbar Julia sets have the same structure as those of the Mandelbrot Julia sets, according as c is taken off or on a symmetry axis of M(p).

Figure 1. A deterministic fractal of dimension logS/log3. THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

33

Isometries of Mandelbrot and Mandelbar Sets Consider the first observation above. It appears from the figures that M(p) cannot be invariant u n d e r an isornetry of the complex plane which is n o t in Dp_ 1, but do the transfor_ms of Dp_ 1 in fact leave M(p) invariant? Similarly, is M(p) really invariant u n d e r the rotations and reflections of Dp + ~, o r is there some island, some distorted c o p y of M(p) in M(p) that introduces an a s y m m e t r y ? Figure 14 shows a distorted c o p y of M(2) in M(2), but w e k n o w that this does not introduce an a s y m m e t r y into M(2) because C r o w e et al. (1989) have s h o w n that M(2) is invariant u n d e r rotations about the origin t h r o u g h 2"tr/3 and reflections t h r o u g h its symmetry axes. To find isometries of M(p) and M(p), w e introduce the Mandel set Man(f) of a function f:C --~ C. Let c E C and define {zn}, the iterative sequence (IS) associated with c, by

zo = 0 and for n > 0

COROLLARY 1:_Reflection in the real axis is an isometry of both M(p) and M(p).

Proof: Define s(z) = ~, so s(0) = 0 and clearly s is a h o m e o m o r p h i s m . Furthermore, + ~ = (zP + c)

and Z p q- C ~--- (~P q- C ) ,

so by the proposition s(M(p)) = M(p) a n d s(~l(p)) = M(p). Since s a l s o p r e s e r v e s distance, it is an i s o m e t r y of M(p), and of M(p). COROLLARY 2: Rotations about the origin of order p - 1 are isometries of M(p).

Proof." Let s be a rotation s(z) = az, where a = exp(2~ri/k). Clearly s is a h o m e o m o r p h i s m a n d s(0) = 0. To satisfy the c o m m u t a t i o n condition w e n e e d (az)p + ac = a(z p + c),

z.+ l = f(z.)

+ c.

Then

which is true if and only if ap = a, i.e., ap- 1 = 1. Again, rotations preserve distances, so the fact that s(M(p)) = M(p) m e a n s they are isometries of M(p).

Man(f) = {c ~ C I the IS associated with c is bounded}.

COROLLARY3:Rotations_ about theoriginoforder p + 1 are isometries of M(p).

N o w consider a c o n t i n u o u s function s:C --~ C. We say that s iteratively-commutes with f if for all z E C and cCC

Proof: Let s be as in corollary 2. In this case the commutation condition becomes

f(s(z)) + s(c) = s0~(z) + c).

(~P

+ ac = a(z~ + c)

so we n e e d ~P = a, i.e., ap+I = 1. We have s h o w n that the s y m m e t r y g r o u p of M(p) We n o w s h o w that iteratively-commutative h o m e o - contains Dp_ 1 as a s u b g r o u p a n d that of M(p) has the m o r p h i s m s with fixed-point at the origin leave Man(f) s u b g r o u p Dp+l, but to p r o v e o u r first observation w e invariant: n e e d to p r o v e that there are n o other isometries. The following m e t h o d works for even p: P R O P O S I T I O N 1: If s iteratively-commutes with f and s(O) Consider first M(p). N o w complex n u m b e r s c such = O, then s(Man(f)) C Man (t). If also s is a homeomor- that Ic[m- ~ > 2 are not in M(p), but w h e n p is e v e n some phism, then s(Man(t)) = Man(t). c such that [c[p- 1 = 2 are in M(p), viz., those for w h i c h tcp - I + 11 = 1. There are exactly p - 1 of these points Proof: For c E Man(t ) let {zn} be the IS associated with c (viz., the complex n u m b e r s c such that cp-1 = _ 2). and let {wn} be the IS associated with s(c). Since s(0) = Since these are the points in M(p) that lie farthest f r o m 0 and f(s(z)) + s(c) = s(f(z) + c), t h e n a simple induc- the origin, there are no other rotational symmetries of tion shows that w, = s(zn). Since s is c o n t i n u o u s and M(p) (and h e n c e n o o t h e r reflectional s y m m e t r i e s ) (z,} is b o u n d e d , (w,} m u s t also be b o u n d e d , so s(c) E other t h a n the obvious ones. For the M a n d e l b a r set Man(f). N o w if s is h o m e o m o r p h i s m , t h e n {zn} is M(p) it is the p + 1 points satisfying ~/c = - 2 w h i c h b o u n d e d if a n d o n l y if {w,) is b o u n d e d , so c E M a n ~ mark the e n d of the M a n d e l b a r arms, but again o n l y if and only if s(c) ~ Man(t ). for e v e n p. From this general proposition w e d e d u c e three corW h e n p is odd these points are outside the Mandelollaries about isometries of the M a n d e l b r o t a n d Man- brot a n d Mandelbar sets. I n d e e d , for o d d p it is n o delbar sets: let f(z) = z p and g(z) = z-p, p a n integer/> longer an easy matter to locate the points w h i c h lie 2, so that Man(f) = M(p) and Man(g) = M(p). farthest from the origin, since the M a n d e l b r o t a n d 34 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992

Mandelbar sets do not have obvious "spikes," as they do for even p. From Figure 4 the farthest point in M(3) s e e m s to be a p p r o x i m a t e l y c = 0.32779878 + 1.290829i, but this does not appear to have a n y special numerical properties, and iteration z,+ 1 = zn3 + C does not converge in the straightforward m a n n e r that is characteristic of the farthest points w h e n p is even. In short, we have only proved that every rotational symmetry of M(p) has order p - 1 a n d every rotational symmetry of M(p) has order p + 1 for even p. The proof for odd p > 1 remains an open problem. Isometries of Julia Sets Now let's look at our second and third observations on the pictures about s y m m e t r y groups of Julia sets. Let c E M(p) a n d consider the IS {z,} associated with a function f:C ~ C defined by z.+ l = f(z.)

+ c.

The filled-in Julia set associated with c a n d f is Julff, c) = {Zo E C I the IS associated with f is bounded}. Finally, l(p,c) = aJul(f,c) for f(z) = z p a n d J(p,c) = 0Jul(f,c) for f(z) = ~P. PROPOSITION 2: The Julia sets J(p,c) are invariant under rotations of order p for all c E M(p). If c lies on a symmetry axis of M(p), then J(p,c) have reflectional symmetry also. Proof: Suppose that s:C--~ C is a h o m e o m o r p h i s m such that f(s(z)) = flz). Then clearly z0 E Julff, c) if and only if S(Zo) ~ Jul(f,c), so s is a s y m m e t r y of Jul(f,c). Now let f(z) = z p and consider a rotation of order p, s(z) = az where ap = 1. Clearly s is a h o m e o m o r p h i s m andf(s(z)) = f(z), so s is a s y m m e t r y of Jul(f,c). If c lies on a s y m m e t r y axis of M(p) there exists a reflection s in the s y m m e t r y group of M(p) such that s(c) = c. We claim that such an s is also an isometry of J(p,c). Let z 0 @ Jul(f,c) begin the IS {zJ with f(z) = z p and s(c) = c. Let w o = S(Zo) and consider the IS {w,} defined by

order p form the cyclic group C p , a n d a d d i n g a reflection to this yields the dihedral group Dp, we have s h o w n t h a t the isometries of J(p,c) i n c l u d e t h e s e groups. P R O P O S I T I O N 3: The Julia sets J(p,c) are invariant under rotations o f order p for all c E M(p). If c lies on a symmetry axis of M(p), then also J(p,c) has reflectional symmetry. Proof: Take f(z) = ~ and s to be a rotation s(z) = az with = 1 in the proof of proposition 2. The proof of reflectional s y m m e t r y w h e n c lies on a s y m m e t r y axis of M(p) proceeds by induction on the iterative sequences {z,} and {w,} defined by Zn+ 1 =

Zn p q- C

W n + 1 = W n p q- C

just as in proposition 2. As before, the difficult part is to prove w h a t is obvious geometrically--that the Julia sets are not invariant u n d e r rotations other t h a n those of order p. In the absence of obvious "spikes," as we have for M(p) a n d M(p) w h e n p is even, our m e t h o d of proof has not succeeded. It m a y be that a different approach is called for!

Colour Maps u s e d in the G e n e r a t i o n of the Figures Figures 2 to 13 (also s h o w n in color on the cover) use a modified version of a m a p suggested by Clifford Pickover (1990). The m e t h o d consists of examining the size of points in the sequence P"(O,c;p) (for the

W n + 1 = Wn p -}- C.

Now w. = s(z.)~

w.+l

= s(z.)P + c = s ( z d = s(z.+3

+ c)

so, since also s is a h o m e o m o r p h i s m , (w,} is b o u n d e d if and only (z,) is b o u n d e d , i.e., z o ~ Jul(f,c) ~ S(Zo) Jul(f,c). Finally, these symmetries of Jul(f,c) m u s t be isometries of J(p,c) since t h e y are orthogonal transformations and J(p,c) = oJul(f,c) forf(z) = z p. Since the rotations of

Figure 2. The Mandelbrot set M(2). The real axis is its only axis of symmetry, so M(2) has symmetry group D1, the dihedral group of order 2 (=(?2, the cyclic group of order 2). THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992 3 5

Figure 3. The M a n d e l b a r Set M(2). This has three symmetry axes, all through the origin, at angles 0, 2~/3 a n d 47r/3 from the real axis. Its symmetry group is D 3, the dihedral group of order 6.

Figure 6. The Generalised M a n d e l b r o t Set M{4). These are the complex n u m b e r s c for which the iteration zn+~ = z, 4 + c i s b o u n d e d . Its symmetry group is the same as that of M(2).

Figure 4. The Generalised Mandelbrot Set M(3). These are the complex n u m b e r s c for which the iteration zn+ 1 = z, 3 + c is b o u n d e d for complex variable z starting with z o = 0. It has two axes of s y m m e t r y m t h e real axis a n d the imaginary axis---and its symmetry group is D 2 (isomorphic with the Klein four group, C2 x C2).

F_F_F_~ure7. The Generalised M a n d e l b a r Set M(4). For c E M(4) the iteration z,+l = zn4 + c is b o u n d e d . It has five symmetry axes: the real axis (as usual) and lines through the origin at angles ~r/5, 3r 7~/5 a n d 9Ir/5 to the real axis. Hence it has symmetry group D 5.

m

i

Figure 5. The Generalised M a n d e l b a r Set M(3). The iteration z,+ 1 = 5, 3 + c is b o u n d e d for c E M(3) (again with complex variable z starting with zo = 0). Its four symmetry axes are the real a n d imaginary axes and lines through the origin at angle Tr/4 to the other symmetry axes, so its symmetry group is D 4. 36

THE MATHEMATICAL

INTELLIGENCER

V O L . 14, N O . 2, 1992

Figure 8. The Julia Set J(2,c) where c = -.874247 - 0.25365i. Since c is not on the symmetry axis of M(2) ,this Julia set has only one rotational symmetry of order 2, i.e., symmetry group C2.

Figure 9. The Julia Set J(2,c) where c = -1.2. This time c does lie on a symmetry axis so it has an extra reflectional symmetry through the axis from which it was seeded, and therefore D z is its symmetry_group. Had c been taken from another symmetry axis of M(2), the Julia set would have reflectional symmetry through that axis.

Figure 11. The Julia Set J(3,c) where c = -.0539041 + 0.13427i. Now c lies off the symmetry axes of M(3) and so the Julia set has only rotational symmetry of order 3, i.e., symmetry group C3.

Figure 10. The Julia Set J(3,c) where c = 1.0877i. Being purely imaginary, c lies on a symmetry axis of M(3) and so its symmetries include reflection through the imaginary axis as well as rotations of order 3. By the closure axiom for groups, the symmetry group also contains reflections through axes obtained by rotating the imaginary axis through 2~r/3 and 4r and it has dihedral symmetry group D 3.

Figure 12. The Julia Set J(4,c) where c = -1.2. The symmetry is D 4 because c lies on a symmetry axis of M(4).

generalised M a n d e l b a r sets the sequence is Q"(O,c;p)). First pick a size limit d > 2, an iteration m a x i m u m m, a n d a set of colours {C(i)}, w h e r e i d e n o t e s the n u m b e r of iterations required before the size limit is exceeded,

if ever, a n d I < i ~< m. Calculate successive Pn(O,c;p) for n = 1,2 . . . . until an iteration i is reached such that either Ipi(O,c;p)l > d or i = m. In the latter case the sequence is b o u n d e d a n d c is coloured black. If i < m pi(O,c;p)l < d or and either Jim IRe pi(O,c;p) I < d, then colour the point c with C(i). O t h e r w i s e colour it C(i-1). A n iteration m a x i m u m of 500 is u s e d to generate figures 2 to 13, w h i c h are all squarely p r o p o r t i o n e d in THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

37

the c o m p l e x plane (i.e., n o t stretched in real or i m a g inary directions), centred at the origin, a n d of " h e i g h t " a p p r o x i m a t e l y 4. The size limits u s e d w e r e 1500 for p = 2, 80 f o r p = 3 a n d 2 5 f o r p = 4. Figure 14 w a s g e n e r a t e d u s i n g a s t a n d a r d colour m a p , w h e r e the size limit d = 4 a n d c is coloured C(i) w h e n e v e r the sequence is n o t b o u n d e d . A n iteration m a x i m u m of 8192 is used, b u t the p r o g r a m traps orbits of length 64 or less so the i m a g e t o o k only a f e w m i n utes to generate. It is centred o n the point - 1.19085 + 0.206607i, with a height of a p p r o x i m a t e l y 6 x 10 -4.

References

Figure 13. The Julia Set J(4,c) where c = -0.3461 + 1.0651i. In polar coordinates c_-- (1.1, 3r so it lies on the symmetry axis S(3r of M(4). Hence in addition to rotational symmetry of order 4, the Julia set has reflectional symmetry about S(3r Group closure implies the other three symmetry axes of the Julia set are rotations of this axis through r r and 3r Notice that these three are not symmetry axes of M(4), so the only symmetry axes they have in common is the symmetry axis from which the Julia set was seeded.

Barnsley, M, Fractals Everywhere, San Diego: Academic Press (1988). Crowe, W. D., R. Hasson, P. J. Rippon, and P. E. D. StrainClark, "On the Structure of the Mandelbar Set," Nonlinearity 2, (1989), 541-553. Pickover, C., Computers, Pattern, Chaos and Beauty, New York: St. Martin's Press (1990).

School of Mathematical and Physical Sciences University of Sussex Brighton, Sussex BN1 9QH United Kingdom

Figure 14. A Distorted Copy of M(2) in M(2). To our knowledge it has not been shown that the Mandelbar set is connected. If it is, experiments show that the connecting filaments are infinitely thin (as in the Mandelbrot set) and all contain an infinity of small "'islands" such as this. But the order of the attracting cycles in these islands increases as they become smaller, and machine inaccuracies make rigorous boundedness tests very difficult to apply. However, our results show that these islands do not introduce any global asymmetries into the Mandelbrot and Mandelbar sets. 38

THE MATHEMATICAL INTELL1GENCER VOL. 14, NO. 2, 1992

The 100th Anniversary of Mathematics at the University of Chicago Karen V. H. Parshall*

On 1 October 1892, the University of Chicago opened its doors to students on a muddy, unfinished site on the south side of Chicago. In all, some 242 undergraduates and 170 graduate students in arts and sciences-together with more than 80 students of divinity and over 60 unclassified scholars---showed up that day to enroll in the new educational institution led by its first President, William Rainey Harper, and bankrolled by Standard Oil magnate John D. Rockefeller. For well over a year prior to its opening, Harper had been hard at work trying to secure the sort of high-level, research-oriented faculty necessary to carry out the mission he had set for the university, namely, the preparation of undergraduates, the training of future researchers, and the production of original research. By the time classes began, he had succeeded in coaxing to his institution well over 100 staff members, who filled out the academic ranks from tutor to instructor to full professor, and who spanned the specialties from religion to history to the sciences. This faculty, coming to Chicago both from the United States and from abroad, plunged headlong into its tripartite task, producing its first Ph.D.'s in 1896, and substantially extending re-

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

search frontiers in the humanities and in the sciences throughout its first decade of cooperation [1]. Keeping well apace of these developments, the Department of Mathematics very quickly established itself as a national trendsetter. Just how did Harper, an expert in Semitic languages and comparative philology, manage to put together such a strong mathematics faculty? Just how did his three professors of mathematics--Eliakim Hastings Moore, Oskar Bolza, and Heinrich Maschke---craft their as yet unprecedented program? In short, just what w a s the configuration of mathematics at Chicago 100 years ago? Because other American mathematics departments looked particularly to Chicago as a guide in setting up their own research programs in the late 1890s and early 1900s, the answers to these questions shed a great deal of light on the emergence of a mathematical research community in America [2]. When Harper accepted the presidency of the newly forming University of Chicago early in 1891, he turned to the problem of finding a faculty, trying to capitalize on connections he had already made during his own teaching career. Since, as Professor of Semitic Languages in the Yale Divinity School, Harper had come to know his somewhat younger colleague in mathematics, E. H. Moore, he decided to sound Moore out about a post at Chicago. An 1885 Yale Ph.D. in math-

THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2 9 1992Springer-VerlagNew York 39

conditions under which he would be willing to accept a post at Chicago: 1. The status to be Professor of Mathematics. 2. The instruction to be twelve hours weekly, and, at any rate soon, largely graduate work. 3. The salary to be $3000.00 a year. 4. The understanding to be that if there are equivalent inducements to remain in Evanston, I remain here [5]. Moore hastened to emphasize, however, that "I have ventured to suggest the above conditions only in response to the definite request in your last letter. I should then have much preferred a definite offer from you, and now hope to hear from you soon with respect to the matter." [6] In spite of Moore's demands (he was, after all, an Assistant Professor with less than a proven track record as an independent researcher) and his exhibition of what could sometimes be a rather prickly personality, negotiations with Harper continued through the end of April when they apparently stalled over salary. Following a personal interview with Harper, Moore dramatically upped his ante in a letter dated 29 April. "'I am prepared to state now," he wrote, "that a definite offer to me on the conditions informally discussed by us that evening but at a salary of $4000 for a scholastic year would be acceptable to me." [7] He went on to declare that "[t]here are reasons satisfactory to me for Eliakim Hastings Moore considering with quite different favor two possible offers at $4000 and at $3000, and indeed without underematics, Moore had returned to his alma mater in 1887 valuing the evident and weighty attractions you spoke after a brief European study tour that had taken him to of which are connected with the full professorship at G6ttingen and Berlin. Moore spent two teaching- whatever salary." [8] The mathematician was driving a intensive years as a tutor at Yale before taking an As- hard bargain, and neither the prospect of graduatesistant Professorship in 1889 at Northwestern Univer- level teaching nor the opportunity to participate in the sity in Evanston, Illinois. Although still heavily in- Chicago experiment would suffice to shake his resolve. volved in teaching, Moore devoted his summers to the With the end of April, determined both to mind his research in n-dimensional geometry he had begun in budget and to maintain the upper hand in securing his his dissertation [3]. However, he was isolated at an faculty, the President cooled in his pursuit of Moore to institution that did not yet value and support research, focus on faculty appointments for other departments. and he failed to make great strides. Unbeknownst to Moore, however, Harper apparently It is little wonder that Moore was delighted when did not go after a different mathematician. He merely Harper sought not only his advice on the developing left Moore to twist in the wind in hopes he would mathematics program at the new university but also reconsider his demands. The ploy worked, for on 29 his presence on the faculty. Responding to Harper's February 1892, Moore returned his signed and dated letter on 16 February, 1891, Moore acknowledged that contract to Harper, thereby officially accepting a full " . . . it is a pleasure and is appreciated as a high com- professorship in and the acting headship of the Unipliment to me to be thought of by you with reference versity of Chicago's Department of Mathematics. He to the University of Chicago . . . . It is possible you had taken on the task of creating a department from have in mind work of a nature more attractive to me scratch, and he had definite ideas as to what that dethan anything Northwestern may have. Most certainly partment should look like. I appreciate very highly your confidence in me, and In a lengthy letter dated 2 March 1892, Moore prethank you very heartily . . . . " [4] Although judging sented his detailed plan to Harper. He called for a from this reply, Harper had extended neither a definite department of five, who must be " . . . strong teachers, nor a detailed offer early in February, negotiations be- with devotion to the subject and with ambition, ability tween the two men continued. Writing on 23 March, and determination to do original work." [9] Of these, Moore outlined, apparently at Harper's request, the two would be tutors, or younger scholars upon w h o m 40

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

Ryerson Laboratory (early home of the Mathematics Department) ca. 1905

the bulk of the elementary, undergraduate teaching would fall; and two, in addition to himself, would hold permanent staff positions, one each at the ranks of assistant and associate professor. Moore envisioned the possibility of the tutors occasionally offering courses at the graduate level, but he essentially reserved that instruction for the three professors. As he unequivocally put it to Harper, "[t]he advanced courses must be offered; the classes will be small." [10] Ever mindful of the University's mission as expressed by Harper, though, Moore realized that regardless of the emphasis he wished to place on graduate education, he had to cover the full range of the mathematical curriculum from elementary courses to research-level seminars. He thus specified that his two professorial colleagues " . . . should be men of tried ability as teachers along the higher lines; they would divide their work (chiefly) between sophomores and advanced classes." [11] With the labor force so apportioned, Moore assured Harper that " . . . the department would start out fairly well equipped." [12] Yet one question still remained: who would round out the proposed faculty of five? One name immediately came to Moore's mind for a professorship, that of his friend, Henry Seeley White. An 1890 GOttingen Ph.D. under Felix Klein, White had returned to the United States for the spring semester of

the 1889-1890 academic year. He met and befriended Moore while a preparatory school teacher near Evanston; he moved on to an assistantship at Clark University in the fall of 1890. By all accounts a good teacher, and showing real promise as a researcher in both invariant theory and the theory of Abelian integrals, White seemed to satisfy the exacting standards set by both Harper and Moore for the selection of faculty. Moore first put White's name before Harper in his own acceptance letter of 29 February, then repeated his suggestion on 2 March, stating that " . . . [o]ne of Klein's men would be apt to have the broadest mathematical horizon." [13] Felix Klein and the mathematical program he coordinated in G6ttingen enjoyed a high reputation in American mathematical circles. Indeed, throughout the last 15 years of the 19th century, study in Germany, and especially under Felix Klein, represented a valuable credential within the e m e r g e n t American mathematical research c o m m u n i t y [14]. What better way, then, for an American mathematics program to establish itself in research than to appoint those who had learned and imbued the research ethos at the feet of the widely acclaimed master? Moore had adopted a shrewd hiring criterion, but nevertheless the nod did not go to his friend White. By early April, White's name had fallen from contention, replaced by the names of two others who had worked under Klein THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

41

in G6ttingen, William Fogg Osgood and Maxime B6cher [15]. Both instructors at their alma mater, Harvard, in 1892, Osgood and B6cher had traveled to Germany to complete their mathematical education. Osgood studied with Klein and others in G6ttingen from 1887 through 1889, then moved on to Erlangen to take his doctorate under Max Noether in 1890 and returned to Harvard that fall. B6cher, three years Osgood's junior, pursued mathematics abroad from 1888 to 1891 and earned his Ph.D. under Klein in 1891 prior to taking up his Harvard position. Although both men satisfied the "Klein criterion," Moore evidently decided to pursue B6cher rather than Osgood, for on 10 May he reported to Harper that "B6cher's answer ought to be here in two days now." [16] Had he responded positively to Chicago's offer, the programs both at Chicago and at Harvard would have undoubtedly developed quite differently. His rejection, however, sent Moore scurrying for some other suitable candidate at what was fast approaching the eleventh hour. He ultimately found one of his men at then embattled Clark University in Worcester, Massachusetts. In the fall and winter of the 1891-1892 academic year, three-year-old Clark University underwent a major crisis that pitted the President, G. Stanley Hall, against the faculty and the benefactor, Jonas Clark [17]. Virtually the entire Clark faculty submitted its collec-

Oskar Bolza 42

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

tive resignation on 21 January 1892, only to retract its decision somewhat later. Stopping off in Worcester in the winter of 1892 as part of his East Coast faculty finding tour, Harper found the University at the height of its troubles. He therefore had little difficulty in securing a significant percentage of what, up to that time, had been the best research-level faculty ever assembled on American shores. Among the disgruntled faculty members with w h o m Harper spoke was one of Felix Klein's German students, Oskar Bolza. Bolza informed Harper of his intentions to return to Germany at the close of the spring semester, but he highly reco m m e n d e d his friend and fellow Klein student, Heinrich Maschke, who had recently immigrated to the United States and who had taken up an industrial position in New Jersey as an electrical engineer. With B6cher's refusal to leave Harvard for Chicago in May of 1892, Moore immediately went after Maschke and an offer went out to him on 1 June. For Maschke as for Moore earlier, salary proved a sticking point. "The general conditions you mention would suit me very well," Maschke wrote. "[Y]ou will, however, allow me the question whether it would not be possible for you to make the salary $2500 instead of $2000." [18] Again, as with Moore, Harper let the matter drop in order to give the candidate time to bring his pecuniary demands in line with the University's offer. In the meantime, Harper had Moore go back to Bolza to see if he could coax him into postponing his return to Germany and accepting a trial, one-year appointment at Chicago. If at the end of the year Bolza did not like the post, he would obviously be free to leave it; but if it did suit him, the job would be his for the asking. Comparing notes with his friend Maschke, and learning that his negotiations officially remained open, Bolza immediately saw the possibility of the two becoming colleagues in Chicago and entered into negotiations of his own with Moore and Harper. When Bolza made his acceptance of an Associate Professorship contingent upon Maschke's appointment to an Assistant Professorship, however, Harper balked, saying that he could afford to hire either one or the other, but not both. Despite Moore's well-laid plan for a department staffed by three professors and two tutors, Harper had decided that the overall circumstances of the University required him to allocate his limited resources differently. The various parties seemed to be at an impasse until, quite unexpectedly, additional resources came in at the end of June, and Harper authorized the dual appointment. With Harris Hancock, later of the University of Cincinnati, and J. W. A. Young in the two tutorships, the initial Chicago Mathematics Department was complete [19]. It remained only to put together a curriculum at all levels that would satisfy the University's educational goals, and to attract students intellectually capable of meeting those goals.

Quaternions, Theory of the Potential, are given at least once in two years, while other courses of a more special character and the Seminars are intended to introduce to research work." [22] In addition, the graduate students, in concert with the faculty, used the weekly (later biweekly) meetings of the Mathematical Club as a forum both for studying the latest work appearing in the journals and for presenting their own new research results. This combination of advanced coursework, specialized seminar experience, and effective departmental colloquium had the net effect of producing an intense, lively, and conducive research environment for its various participants. During that first year, at least five students-No B. Heller, John Irwin Hutchinson, Herbert Ellsworth Slaught, James Archy Smith, and Mary Frances Winston-accepted fellowships to study mathematics at Chicago. Of these, Heller and Hutchinson had followed Bolza from Clark, and while Hutchinson subsequently took his Ph.D. under Bolza's direction in 1896 (one of the first two Chicago Ph.D.'s in mathematicsthe other was Leonard Eugene Dickson), Heller dropped out of the program after only one year [23]. Smith also left the department before completing a degree, but Slaught and Winston both went on to earn their doctorates in mathematics. Slaught, who came into the Chicago program with a weak background but Heinrich Maschke strong determination, got his degree under E. H. Moore in 1898 for a thesis in algebraic geometry and When classes began in early October 1892, the un- went on to serve on the Chicago faculty until his redergraduates found themselves confronted with a cur- tirement in 1931 [24]. Winston, however, stayed at the riculum unprecedented up to that time in the United University of Chicago for only one year. In spite of the States. They began with an introductory course on ba- fact that German universities did not admit women, sic algebra, plane trigonometry, and analytic geome- she had her sights set on a Gottingen Ph.D. under try; proceeded to a first course in calculus at a time Felix Klein and received a strong endorsement from when this marked the culmination of most American Bolza. Journeying to Germany in 1894, her prospects college mathematics curricula; and finished off with uncertain, Winston eventually earned the first German intermediate work in " ... Algebra, Analytic Geome- doctorate in mathematics awarded to an American try, the Calculus; courses in Differential Equations, woman in 1897, and she indeed did her work under Applications of Calculus to Geometry, Analytical Me- Klein's direction [25]. chanics, Elements of Projective Geometry, Elements of This reasonably promising first class of fellows was Elliptic Functions, Elements of Theory of Functions," succeeded over the next 15 years by classes numbering as well as elective courses in number theory and the among them many of the future stars of American mathematical theories of potential and electricity [20]. mathematics. Leonard E. Dickson, Gilbert A. Bliss, OsAs for the graduate students, they entered a program wald Veblen, Robert L. Moore, George D. Birkhoff, with the following explicitly articulated mission: ". . . and others all developed into productive researchers to give the student a comprehensive view of modem and scholars in the mathematical environment of the mathematics, to develop him to scientific maturity, University of Chicago. By 1900, thanks to an able and and to enable him to follow, without further guidance, energetic faculty, a supportive university administrathe scientific movement of the day, and, if possible to tion, a stream of talented students, and key external take an active part in it by original research." [21] In events like the Chicago World's Fair, the organization order to prepare them to meet these goals, " ... gen- of the Chicago Section of the American Mathematical eral courses on the most important branches of mod- Society, and the founding of the Society's Transactions, ern mathematics such as: Theory of Functions, Elliptic the University of Chicago had clearly earned its repuFunctions, Theory of Invariants, Modern Analytical tation for having the strongest mathematical program Geometry, Higher Plane Curves, Theory of Substitu- in the United States [26]. One hundred years ago, it tions, Theory of Numbers, Synthetic Geometry, took not only talent but a unified effort at all levels of THE MATHEMATICAL INTELLIGENCER VOL. 14, NO.2, 1992

43

16. E. H. Moore to W. R. Harper, 10 May, 1892, UC Archives, UPP 1889-1925, Box 14, Folder 15. 17. For an account of Clark's early history based on documentary evidence, see William A. Koelsch, Clark University 1887-1987: A Narrative History (Worcester: Clark University Press, 1987), pp. 1-40. 18. Heinrich Maschke to W. R. Harper, 6 June, 1892, UC Archives, William Rainey Harper Papers, Box 14, Folder 10. 19. Although Hancock left Chicago for Cincinnati in 1900 in a dispute over promotion with Moore and the University administration, Young stayed on, eventually focusing on mathematical pedagogy. 20. The University of Chicago Annual Register July 1, 1892-July 1, 1893 with Announcements for 1893-1894 (Chicago: University of Chicago Press, 1893), p. 77. References 21. Ibid. 1. The President's Report: Administration--The Decennial Pub- 22. Ibid. lications, 1st ser., vol. 1 (Chicago: University of Chicago 23. Hutchinson wrote his thesis "On the Reduction of a Hyperelliptic Function to Elliptic Functions by a TransforPress, 1902), pp. 11, 175. Thomas Goodspeed published mation of the Second Degree," a topic which Bolza had somewhat different figures in A History of the University of explored under Klein's tutelage in G6ttingen. On earnChicago Founded by John D. Rockefeller: The First Quarter ing his degree, he returned to a faculty position at CorCentury (Chicago: University of Chicago Press, 1916), p. nell University where he remained until his death in 248. 1935. Although he never earned his Chicago doctorate, 2. For more details on the emergence of the American Heller eventually went on to a position at Temple Unimathematical research community, see Karen Hunger versity. Parshall and David E. Rowe, "American Mathematics Comes of Age: 1875-1900," in Peter Duren et al., ed., A 24. Slaught's dissertation topic, "The Cross-Ratio Group of 120 Cremona Transformations of the Plane," reflected Century of Mathematics in America, Part III, (Providence: Moore's combined interest in geometry and group theAmerican Mathematical Society, 1989), pp. 3-28, and our ory. Although Slaught continued to do some work in this book The Emergence of the American Mathematical Research area, his primary interest shifted to matters of matheCommunity: J. J. Sylvester, Felix Klein, E. H. Moore (Provmatical pedagogy. He served as an editor of the American idence: American Mathematical Society), forthcoming. Mathematical Monthly and was instrumental in the found3. Moore received his Ph.D. under the supervision of Huing of the Mathematical Association of America in 1915. bert Anson Newton for a thesis on "Extensions of CerFor more on Slaught, see W. D. Cairns, "Herbert Ellstain Theorems of Clifford and Cayley in the Geometry of worth Slaught: Editor and Organizer," American Mathen Dimensions," subsequently published in the Transacmatical Monthly 45 (1938), 1-10. tions of the Connecticut Academy of Arts and Sciences 7 (1885), 9-26. On Moore and his work, see Gilbert A. 25. Winston's thesis, entitled "Uber den Hermiteschen Fall der Lam4schen Differentialgleichungen," fell squarely Bliss, "Eliakim Hastings Moore," Bulletin of the American within Klein's area of research and teaching interest in Mathematical Society, 39 (1933), 831-838; and "The Scienthe late 1890's. Winston went on to marry a fellow mathtific Work of Eliakim Hastings Moore," op. cit., 40 (1934), ematician, Henry Newson, and effectively left mathe501-514. matics to raise a family. After her husband died sud4. E. H. Moore to W. R. Harper, 16 February, 1891, Unidenly and prematurely in 1910, she eventually secured a versity of Chicago Archives, University Presidents' Pajob at Washburn College in Topeka, Kansas before takpers 1889-1925, Box 17, Folder 2 (hereinafter abbreviated ing the position at Eureka College in Eureka, Illinois that UC Archives, UPP 1889-1925). I thank the University of she held until her retirement in 1942. For more on WinChicago, as always, for permission to quote from its arston, see Betsey S. Whitman, "Mary Frances Winston chives. Newson: The First American Woman to Receive a Ph.D. 5. E. H. Moore to W. R. Harper, 23 March, 1891, UC Arin Mathematics from a European University," Mathematchives, UPP 1889-1925, Box 14, Folder 15. ics Teacher 76 (1983), 576-577. 6. Ibid. Moore's emphasis. 7. E. H. Moore to W. R. Harper, 29 April, 1891, UC Ar- 26. For a detailed account of the role of these external events in establishing Chicago's mathematical reputation, see chives, UPP 1889-1925, Box 14, Folder 15. Karen Hunger Parshall, "Eliakim Hastings Moore and 8. Ibid. the Founding of a Mathematical Community in America: 9. E. H. Moore to W. R. Harper, 2 March, 1892, UC Ar1892-1902," Annals of Science 41 (1984), 313-333, rechives, UPP 1889-1925, Box 14, Folder 15. printed in Peter Duren et al., ed., A Century of Mathemat10. Ibid. zcs in America, Part II (Providence: American Mathemat11. Ibid. Moore's emphasis. ical Society, 1988), pp. 155-175; and Parshall and Rowe, 12. Ibid. The Emergence of the American Mathematical Research Com13. Ibid. munity, Chapters 7 and 8. 14. For more on Felix Klein's role in the emergence of the American mathematical research community, see Parshall and Rowe, The Emergence of the American Mathemat- Departments of Mathematics and History ical Research Community, Chapters 4, 5, and 7. University of Virginia 15. E. H. Moore to W. R. Harper, 25 March, 1892, UC Ar- Charlottesville, VA 22903-3199 chives, UPP 1889-1925, Box 14, Folder 15. USA p a r t i c i p a t i o n - - a d m i n i s t r a t i o n , faculty, a n d s t u d e n t b o d y - - t o create a n d n u r t u r e a D e p a r t m e n t of Mathematics. P e r h a p s there is a lesson h e r e that history can teach in these d a y s of shrinking a c a d e m i c budgets, which s e e m to pit a d m i n i s t r a t i o n s a g a i n s t faculties against s t u d e n t s a n d to divert attention f r o m the real goals of u n i v e r s i t y e d u c a t i o n - - t h a t s a m e tripartite mission as articulated b y H a r p e r in his p l a n for the University of C h i c a g o - - u n d e r g r a d u a t e e d u c a t i o n and the training of future researchers and the p r o d u c t i o n of original research.

44

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

The Spiteful Computer: A Determinism Paradox Ethan Akin

I was an undergraduate at CCNY when I first encountered Russell's paradox as an exercise in Simmons's topology book. I distinctly remember my enjoyment of the looping symmetry of the argument. Delightful. However, a full week passed, and then I suddenly realized that the paradox had not been resolved. Considerably agitated, I hunted up my professor, Jesse Douglas, who told me some home truths about logic and sent me off to read Halmos's "Naive Set Theory." That was many years ago. Lately, I have been troubled by another paradox. Again I can't resolve it, but "Professor Douglas is long dead. So I am presenting this description, not as a challenge, but as an appeal for help. It began with some thoughts about classical determinism a la Laplace out of Newton. Determinism seems to exclude the possibility of free will; and indeed some behaviorists, like B. F. Skinner, suggest that our sense of free will is an illusion arising from incomplete information, just as the subject of a post-hypnotic suggestion feels completely uncoerced as he opens his umbrella in the living room, but we w h o saw the suggestion planted know better. I think the Skinner view is erroneous as well as demoralizing, but like other skeptical positions it is hard to attack by logical argument. Thus, I was delighted when someone pointed out to me that the discussion of spite by Dostoevsky's Underground Man provides an answer to the behaviorist view. When presented with the choice between coffee and tea, I can always, regardless of my tastes, simply out of spite, change my choice w h e n someone attempts to publicly predict my behavior. I was very taken with this argument for the reality of human choice and I trotted it about, showing it off. Finally, I displayed it to my Math Department colleague, Morton Davis. He was not impressed. Shrugging, he remarked: "I can program a computer to do that." Thus crumbled my defense of free will. What remains is a puzzle about determinism. Imagine a system consisting of two computers. The first, very large, is labeled "Laplace," and the second, rather small, is "Baby Dostoevsky." We assume a Newtonian world consisting, at the microscopic level, of atoms whose motion is completely described by a

system of second-order differential equations. Computer Laplace is designed to solve the associated initial-value problem, but its programmed goal is to predict the output of Baby Dostoevsky at time T + 1. It prints this prediction at time T and inputs it to B.D. who has a very simple program: "No." So the output at time T + 1 is 1 if the input at T is 0 and is 0 otherwise. We start the clock running at time t = 0, providing Laplace with the initial position and velocity of all of the particles in the system. By computing the associated solution path, it can observe the state of B.D. at all future times. Notice that the gadgets and their programming are included in the system about which the computations are being run. In particular, Laplace can observe the output of B.D. at T + 1. It prints this state at time t = T and hands it on. But the programming of B.D. then falsifies the prediction. There is a paradox here. This is a completely deterministic world. Pause here to think microscopically. What we interpret as two computers with programming embodied by switches and connecting wires, is, in fact, a vast array of particles moving about, attracting, and colliding with motions described by a system of equations we are assumed to know. The initial po-

THE MATHEMATICAL 1NTELLIGENCER VOL. 14, NO. 2 9 1992 Springer-Verlag New York

45

A Spiteful Human

sitions and velocities determine the future states. So solving the initial value problem provides a prediction of the future. This was the original vision of Laplace (the human). In particular, all of the future outputs of B.D. were determined by the initial data and so are available to the solver, Laplace. "Having obtained this T + 1 output, print it and input it to B.D. at time T," is a macroscopic description of an aspect of the motion of the system, built-in to begin with and so also determined by the initial conditions. But clearly the logic of the programming makes this internal prediction impossible. Clearly, there is no issue of free choice here. From the outside what is happening is so simple as to be dull. The whole issue is predictability from the inside. Furthermore, the possibility of a hypothetical prediction of the "Whatever I say, you will do the opposite" variety is simply irrelevant, as is the observation that Laplace can correctly predict the output by lying about its prediction to B.D. These objections miss the point and misunderstand the predetermined, hardwired nature of the world setup. Also, there seems to be a clich6 that a system cannot predict its own state, but I don't know what this means. Take a piece of wire, bend it to spell out, in script, the word "Frozen," and then freeze it. If you want something less trivial, replace Baby Dostoevsky by Baby Dale Carnegie w h o s e program is "Yes." N o w the prediction works just fine. I am aware of several objections to the description I have given, but none of them seems to resolve the paradox in a completely convincing way. Let me begin with some apparent difficulties which are not serious. First of all, Newton's equations have singularities, and solutions can approach the b o u n d a r y of the domain in finite time. But these triple collisions, blowups, and so forth, are problems for the determinist, not me. I am simply assuming smooth, nonsingular equations on a compact domain as my definition 46

THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992

9 John DePiUis

of determinism. In short, I am assuming a smooth global flow. The second unreal difficulty is the chaosproblem: sensitive dependence upon initial conditions and the related fact that for numerical computations neither the inputs nor the outputs can be given exactly but only up to a certain (arbitrarily small by assumption) error. But we are mathematicians, not physicists nor philosophers of science who are frightened off by accuracy demands of googol many orders of magnitude below the diameter of an atom. By uniform continuity of the flow, for any ~ > 0 and any large T, there exists a 8 > 0 so that initial data of 8 accuracy yield computations of accuracy through time T + 1. The e accuracy needed is only enough so that, in input and output for the Babies, ~ approximations to 0 and 1 can be identified and distinguished. This also takes care of the conversion of continuous to discrete states performed by the Babies. We can choose the time scale so that one time unit is enough in which to change a clear 0 to a clear 1 or vice versa. However, closely related to the chaos problem is one that came up in discussions with another colleague. This more serious catch-up problem may well provide the explanation. As it can compute with 8 accuracy for any positive 8, Laplace is a pretty good computer, but presumably increasing accuracy has an increasing cost measured in time spent calculating. Once Laplace is powered up there will be a time lag while it solves the initial-value problem to T + 1, and this lag will presumably increase as 8 gets smaller. Meanwhile, even with e fixed, 8 gets smaller as T increases. It is not clear that for any T the computation out to T + 1 can be completed before time T. Some rough estimates make this difficulty appear acute. Assuming the flow is Lipschitz, then 8 can be chosen to be e divided by the Lipschitz constant. However, the Lipschitz constant for a flow

on [0, T] tends to grow exponentially with T. So with fixed, 8 is of the order exp( - KT) for some positive K. Unless the lag of computation is o(Iog(1/8)), for T large the lag will grow faster than T and prediction will fail. Of course, we could build a bigger, faster computer. But the computer is part of the system and the lag grows with the size of the system, that is, the number of particles in it. Furthermore, we cannot assume computations are performed with arbitrary quickness, because the calculations are performed by motions of the particles in the system whose velocities are given by the equations of the system. There is a possible escape that should be noted. To save the paradox we don't need to predict for all large T. We only need success for some T. So there might still be a paradox even if long-term prediction fails. Clearly, the catch-up problem is serious. Regardless of its plausibility though, I resist it. There is an appeal to efficiency, or lack thereof, which I don't trust. The whole approach has an aroma of reality that offends my mathematical nose. It was, of course, a physicist who suggested this lag problem to me. However, if the objection could be made rigorous it would be much more interesting than my little paradox, as it would mean that certain sorts of deterministic systems are in principle not predictable except by much larger systems. I'm afraid that my o w n tentative explanation is, if anything, even uglier than the catch-up problem. It has to do not with the prediction mechanism at all, but rather with the introduction of the initial data. Imagine we "photograph" the positions and velocities of all of the particles, and engrave the photo on a metal plate, whose entry into Laplace's input slot starts the clock. The problem is that the plate itself is part of the system and so a description of it must be included as part of the initial data on the plate. Our need for only 8-accuracy may help somewhat. By making the time lag for developing, engraving, and inserting arbitrarily small, the error between the actual positions and velocities at time t = 0 and their pictures on the plate can be made arbitrarily small. Notice that outside the system we can allow ourselves a godlike efficiency. In particular, we have complete control of the plate and how we insert it. So we can draw what we want on it and insert it according to our description. We still have a problem of self-reference. On the plate is a little picture of the plate, containing a picture of the picture, and so forth like the infinitely receding images in facing mirrors. However, by stopping after a finite number of rounds we introduce an error whose size presumably declines with the number of images. The plate shows N nested plates and reality has N + 1. Unfortunately, there is a synergistic effect with the catch-up problem. Describing the images with more detail may require more particles, thus enlarging the system and shrinking 8.

What really bothers me is that the plate, as it slides toward the input slot, may bang into particles from the original system. We could wait until there are no particles in the way before starting, but this seems to be a Maxwell's demon sort of difficulty. Before this renewed onslaught from physics, I simply retreat in perplexity. Since I originally wrote the description of this paradox I have meandered in the vast literature on determinism and free will. An anonymous referee pointed me toward A Primer on Determinism by John Earman, whose interests turned out to be complementary to mine. He is mostly concerned with issues that I have assumed away, like the degree to which the Newtonian universe is really deterministic given collisions, escape to the boundary, and so on. On the other hand, Karl Popper in his lecture "Of Clouds and Clocks" considered the "nightmare of determinism," and Michael Levin described a "paradox of prediction," both more closely related to the problems I am wrestling with. Their discussions take place, however, in the context of free will. So their thinking is contaminated by human minds, as mine was before the current, purified, stainless steel version of the puzzle appeared. Meanwhile, as I have shown this puzzle about, a consensus has developed that the catch-up problem provides the key to the solution. Charles Tresser of IBM put it in a fashion that is not only palatable but elegant: "Usually, these computers are big things analyzing much smaller things. But here, the computer Laplace is analyzing a system as big as itself (bigger even). It seems that the optimal w a y to reveal the future in such a case is to live it." The last epigram feels like a potential conjecture. It would be nice to turn it into an actual theorem.

References 1. Earman, John, A Primer on Determinism, Dordrecht: D. Reidel Publ. Co. (1986). 2. Levin, Michael E., Metaphysics and the Mind-Body Problem, Oxford: Oxford University Press (1979). 3. Popper, Karl R., "Of Clouds and Clocks" (1965) reprinted in Objective Knowledge, Oxford: Oxford University Press, (1972). Department of Mathematics The City College 137 Street and Convent Avenue New York, NY 10031 USA

[Added in proof: A prior, closely related work is Karl Popper's "Indeterminism in Quantum Physics and in Classical Physics, Part II," British Journal for the Philosophy of Science (1950) 1:173-195. In explaining w h y a computer cannot in principle predict its own future behavior, Popper raises several arguments which overlap with mine above, but his interpretation of the results is different from my own.] THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

47

The Doomsday Argument John Leslie

Background If the human race is going to survive for many hundred thousand years, either at its present size or at the much larger size it would reach if it spread through the galaxy, then we are very exceptionally early humans: in the first 0.0001%, perhaps. If, however, the race is going to end shortly, maybe through a pollution crisis, then we are fairly unexceptional because about 10% of all humans who have ever lived are alive today. What, if anything, should a mathematician conclude from this? Brandon Carter, F.R.S., of the Department of Applied Mathematics at Cambridge, stated an anthropic principle in 1974: "'that what we can expect to observe must be restricted by the conditions necessary for our presence as observers.'" Despite the word "anthropic,'" the principle has no special concem with anthropos. It applies to living observers in general, and it is as trivially true as that every puppy is a dog. Still, it could help to throw light on one's observed position in space-time. J. A. Wheeler has pictured an oscillating cosmos in which conditions are life-permitting only during rare oscillations. However, the anthropic principle reminds us that it would have to be during one of those that you have found yourself. Again, R. H. Dicke held that observers could expect to find themselves only in eras after heavy elements had been formed inside stars and then scattered so that observers could be made from them, and before the stars had burned out. He used this anthropic point against P. A. M. Dirac in a way that has become famous. [1] Besides reminding you that you must find yourself at a place and time in which life is possible, anthropic reasoning can encourage you to expect not to find yourself when and where comparatively few observers are found. On some theories now popular among cosmologists, our universe is so gigantic that almost anything will happen somewhere, some day. Black holes emit particles randomly, as S. W. Hawking discov48

ered and Hawking has suggested that, given a large enough collection of such holes, books and television sets and even observers would be emitted occasionally, like sonnets typed by the proverbial monkey. They might actually have been emitted in the earliest hours of the Big Bang. However, observers should not expect to find themselves alive so very early. Likewise, if technologically advanced civilizations were to be found in huge numbers in our universe, considered in its temporal entirety from Big Bang to Big Crunch, then one could not expect to find oneself in the earliest years of the very first such civilization. Be wary, therefore, of accepting the theory that it is there where you personally find yourself! During a lecture given in 1983, Carter applied probabilistic reasoning to the time the human race took to

THE MATHEMATICAL 1NTELLIGENCERVOL. 14, NO. 2 9 1992 Springer Verlag New York

evolve. Why was this very roughly comparable to the total period available, the time between Earth's formation and the date (still, of course, rather far in our future) at which the sun will become unstable? He answered that w h e n a process involves one or more very improbable steps and so is unlikely to be completed within the period available, then it is most likely to be completed when that period has more or less elapsed. The evolution of an intelligent species is a case in point, he suggested. We could thus well have expected to find that our species had appeared roughly when it did. This is an interesting application of the anthropic principle to the situation where observers are likely to find themselves. Even more interesting, and potentially very disturbing, is a further theme that Carter developed in the lecture. (He said that nuclear submarine commanders would do well to contemplate it.) It involves asking where you could expect to find yourself in the history of your species. In the lecture's printed version [2] he hints at this theme only once, and very obscurely: in a Discussion at the end, he says that "something like a man-made ecological disaster . . . might well be discussed with reference to the anthropic principle." However, he has "defended the theme in seminars ever since, particular|y when confronted with the objection that the anthropic principle predicts nothing. It is the theme of the present article. I have developed the theme in four earlier articles: "Risking the World's End," "Is the End of the World Nigh?," "Bayes, Urns and Doomsday," and "Doomsday Revisited." [3] All these join Carter in suggesting that our observed position in time gives us reason to think that the risk that the human race will soon become extinct is typically underestimated, perhaps very severely. Carter has written to me that my presentation of his argument is "technically sound.'" Let us now see what the readers of The Mathematical Intelligencer think. The Argument: A Case of Bayesian Reasoning

What Carter and I do, in a nutshell, is to apply to our position in the total history of the human race the kind of reasoning that can seem so forceful when it is applied to the position of the human race among all technologically advances races. Yes, our technological civilization might be the very first in a universe whose temporal spread from Big Bang to Big Crunch included trillions of such civilizations: One of its civilizations, after all, would be in that very exceptional position. But do not ask us to believe that we are thus positioned, unless you have special grounds to offer us. And similarly, do not ask us to believe that we are among the very earliest humans unless you have excellent reasons for thinking that the h u m a n race will survive such things as nuclear submarines and the pollution crisis.

//

;9

~

/

~ First men

/f f "~'Deferred" Doom

1

'Doom Soon"

1990

Time Brandon Carter's Doomsday Argument. If the human race had been fated to last for many years and to spread through the galaxy, could you at all have expected to find yourself as early as the 1990s?

Carter and I argue that Bayes's Rule is applicable here. Fed into a Bayesian calculation, our observed position in time acts to increase the estimated likelihood that the human race will end shortly. Compare how one ought to reason if winning one of a lottery's first three prizes. Somebody or other had to win them, no matter how many prizes there were in all, just as, no matter how long the h u m a n race was going to last, some people were bound to be born earliest. Still, when my name is one of the first three drawn from an urn then I have more reason to believe that there are only a few names still to be drawn. Bayes's Rule tells us that the probability of some hypothesis, in the light of given evidence, reflects the probability of getting such evidence if the hypothesis is correct. This can be thought to be just common sense. A publisher once organized a raffle with a prize of $300 worth of books. My suspicion was that few would bother to fill in the long entry form, so I filled it in. The books arrived in due course, and my suspicion was strengthened---surely justifiably. Consider a case where there is a 2% probability that an urn with my name in it contains ten names only, and a 98% probability that it contains a thousand. These "prior" probabilities are my personal estimates, before any names are drawn. If my name is among the first three drawn then, Bayes's Rule tells me, the "posterior" probability of there having been only ten names is 2 3 100 10 2 3 98 3 10--6 x 1-0 + ~ • 100--"0 "

"

X

-

-

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992 4 9

or roughly 67%. An estimated probability of only two out of a hundred has been revised to about two out of three. Now, here comes a rather similar calculation, applied to one's temporal position. Simplifying greatly, let us say that the sole alternatives are (i) that the human race will end before A.D. 2150, and (ii) that it will survive for many h u n d r e d thousand more years. Simplifying again, let us say that the chance that a human will be in the 1990s is 1/10 in the case of the shortlasting race, while in that of the long-lasting race it is only 1/1000. Well, suppose you start by thinking that the chance that the race will end by 2150 is only 1%. That is to say, it is 1% prior to taking account of your observed position in time! You now take it into account. If you can use Bayes's Rule just as in the case of your name coming out of the urn, then the revised estimate of the probability of Doom Soon is

Some Objections

Carter's argument is controversial. Beware, though, of calling it silly and trusting the first objection that springs to mind. Let me very quickly reinforce this warning. (i) Do not object that your birth time was not decided by a lottery. You would be forgetting that Bayesian calculations are relevant to vast areas of statistics. (ii) Do not object that any Stone Age man who had used Carter's reasoning would have been led to the mistaken conclusion that his race would end shortly. The answer to this objection is that it would not be a defect in probabilistic reasoning if it led someone very improbably situated, to a mistaken conclusion. Besides, Stone Age men were not facing today's pollution crisis. (iii) Do not object that we know we are alive in the 1990s, and that therefore the figure for the probability of our being there is 1, certainty, no matter how long 1 X - -1 - our race will last. The answer to this is that Bayesian 100 10 calculations can be based on the probability that we 1 1 99 1 would have gotten such evidence, contingent on various l o o x i-6 + 1--66 x lOO---6 hypotheses. (iv) Do not object that your genes are of a sort likely to be found only in or near the 1990s, and that therewhich is slightly over 50%. Let it be said at once that there could be a difficulty fore you had to exist around then. For what Carter is in treating the two cases similarly, because our world asking is how likely a human observer would be to be might be a radically indeterministic one. If it were, in the 1990s and hence have genes of a sort typical of then there would not yet be any firm fact as to how that period. (Consider an experiment involving h u m a n long the human race will last, in contrast to there being embryos in two batches. Those of the first batch were a firm fact as to how many names an urn actually con- of one sex while those of the second were of the other. tains. But while this would reduce the force of Carter's One of the batches contained only two embryos; the reasoning, it would by no means destroy it. (a) For a other, two million. Knowing just that you had been start, it is not clear that our world is radically indeter- one such embryo and that you are female, you ought ministic. It has long been held by philosophers--for to conclude that the large batch was female, very probinstance by Locke, Hume, Mill, and Russell--that de- ably. You must not say to yourself that your genes are terminism would be fully compatible with h u m a n ef- female and that therefore you would necessarily find forts to affect the future. Moreover, even some expert that you were female no matter whether the female physicists, such as Steven Weinberg, still believe that batch was small or large.) so-called quantum indeterminacy is not "out there" in (v) Do not object that if the universe contained two Nature, but instead reflects our necessary ignorance of human races, the one immensely long-lasting and galNature. (b) Even if the world were radically indeter- axy-colonizing and the other short-lasting, and if these ministic, it might well be that its indeterminism would races had the same population figures until A.D. 2150, have no relevance to whether we were going to survive then finding yourself in the 1990s would give you no the pollution crisis or some similar crisis. (c) Suppose, clue as to which race you were in. The answer to this though, that there was a radical indeterminism that objection is that we do not in fact know that the uniwas likely to be relevant. Carter's reasoning could still verse contains two such races, and Carter's reasoning act powerfully against, for example, the theory that it would weaken the supposition. In the situation envisis altogether probable that the human race will survive aged, where should you and I expect to find ourselves? for many hundred thousand years and spread through After 2150, clearly, as the vast majority of h u m a n s the galaxy. Knowing just that in the 1990s it was, say, would find themselves there. Yet we find ourselves 96% probable that the human race's spatiotemporal here, don't we? (vi) Do not object that there would be more chances entirety would include several trillion people, of whom only a few tens of billions had been bom by the 1990s, of being born into a long-lasting race, and that these would you judge it at all likely for a h u m a n to be alive would precisely cancel the lesser chance of being born as early as the 1990s? Surely not. into it early. If only 10 people were ever to be born, 50

THE MATHEMATICAL

INTELLIGENCER

V O L . 14, N O . 2, 1992

n o b o d y should be surprised at being one of the 10---for only those w h o are b o r n can find t h e m s e l v e s anywhere. I have h e a r d other objections but there is no space to list t h e m here. M a y b e y o u will discover o n e that works, though.

Notes 1. The relevant writings of Wheeler and Dicke are reprinted in Physical Cosmology and Philosophy, ed. J. Leslie, New York: Macmillan (1990). The volume also reprints the article in which Carter introduced and baptized the anthropic principle. 2. "The Anthropic Principle and its implications for Biological Evolution," Philosophical Transactions of the Royal Society, London, A 310 (1983), 347-363. 3. These were, respectively, Bulletin of the Canadian Nuclear

Society, 10:3 (1989), 10-15, reappearing with some changes as Interchange, 21:1 (1990), 49-58; The Philosophical Quarterly, 40:158 (1990), 65-72; Interchange (forthcoming); The Philosophical Quarterly (forthcoming). I have also summarised Carter's argument on p. 214 of my Universes, London and New York: Routledge (1989), a book largely concerned with the anthropic principle. Something like the argument is developed by H. B. Nielsen on pp. 454-459 of an article in Acta Physica Polonica, B 20:5 (1989); however, his reasoning may suffer through not taking proper account of prior probabilities. My fullest defense of the argument is "Time and the Anthropic Principle," read to the Soviet Academy of Sciences in Leningrad, November 1990, and now being expanded: I can post copies of its latest version to any who are interested. Department of Philosophy University of Guelph Guelph, Ontario NIG 2W1 Canada

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

51

Ian Stewart* The catapult that Archimedes built, the gambling-houses that Descartes frequented in his dissolute youth, the field where Galois fought his duel, the bridge where Hamilton carved quaternions-not all of these monuments to mathematical history survive today, but the mathematician on vacation can still find many reminders of our subject's glorious and inglorious past: statues, plaques, graves, the cafd where the famous conjecture was made, the desk where the

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

A Transylvanian Lineage Martin Bier

Encyclopedias and textbooks commonly write that the Hungarian mathematician J~inos Bolyai (1802-1860) was born in Kolozsv~r and died in Marosv~s~rhely, two towns in Transylvania. A search for these places in a modern arias would be unsuccessful: both are now part of Romania and are named Cluj and Tirgu Mure~. It is often added that J~inos and his father Farkas would have been more prolific mathematicians had it not been for their geographical isolation. Today Transylvania is still a predominantly rural region where distances are long and travelling is slow. There are many ethnic groups, but foreigners are a rarity. There is a statue of Farkas and J~nos Bolyai (for the latter of w h o m the geometry is named) in T~rgu Mure~ and, about 300 feet from the statue, a m u s e u m that is devoted to them. The museum is just one room in an old and solid building. One enters from a courtyard. A somewhat distinterested woman comes over to unbolt the heavy metal door. She gives an affirmative sigh when I ask if it would be possible to take some pictures. * Column Editor's address: Mathematics Institute, University of Warwick, C o v e n t r y CV4 7AL England.

Romania today. Farkas, the father, studied in G6ttingen, where he became a close friend of Gauss. After his studies he returned to Transylvania and for the next 47 years held

52 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2 9 1992SpringerVerlagNew York

Display case with the skull of Farkas Bolyai and the scalp of J~inos Bolyai.

The statue of Farkas and J~nos Bolyai in Tirgu Mure~.

The graves of Farkas and J~nos Bolyai.

The working desk of Farkas Bolyai.

a position as a science teacher at the Evangelical Reformed College in Tirgu Mure~. He kept trying to find a proof of the parallel postulate, but never got any further than finding and promoting an equivalent formulation of it (three points not on one line are always on some circle). He was a well-rounded person; he published a number of plays, and hanging in the museum are two paintings of his (one of them a selfportrait); one of the display cases contains a cup with the ashes of poems he burnt in discontent. J~nos was taught mathematics by his father from an early age. He, however, opted for a career in the army and, in 1818, went to the Academy of Military Engineering in Vienna. For the next decade and a half his contacts with his father were mostly by mail. Many of the letters are preserved, and photocopies are on display. While in the academy J~inos took on the parallel postulate despite his father's warnings ( " . . . leave the doctrine of parallel lines alone; you should fear it like a sensual passion; it will deprive you of health, leisure and peace---it will destroy all joy in your life"). But Jfinos's approach was different: instead of looking for a proof of the parallel postulate he constructed a geometry that was independent of it. In 1823 he finished the Academy and was stationed in Timi~oara. It was in that same year that his research came to a head; in November he wrote to his father, " . . . from nothing I have created a new, different world." In 1832 Farkas Bolyai published his Tentamen: two thick volumes in Latin containing a systematic and rigorous exposition of geometry, arithmetic, algebra, and analysis. In a twenty-nine-page appendix to his father's first volume J~nos gives a very condensed presentation of his "Absolute Geometry." On the wall above the letter-filled display cases in the museum, there is an explanation of non-Euclidean geometry in Romanian, Hungarian, and German. At the end it states in prominent red letters that nonEuclidean geometry affirms the dialectic-materialist viewpoint that space and matter are one. Since the violent revolution of December 1989 Romania has no official ideology, but it seems as if no one has bothered to rewrite the explanation in a less tendentious manner. Also, one of the display cases is devoted entirely to quotes from J~nos on political issues. In a region with a lot of ethnic friction it is comforting to read that Jfinos loved the Romanians as much as he loved the Hungarians. But it is ironic to see a highlighted quote: "the land, like the air, should belong to all the people together," as outside they are dealing with the complications of giving back to people the lands that were taken away from them in the 1949 collectivization. During his career in the army J~nos was moved around frequently between the many garrisons at the edges of the enormous Austro-Hungarian empire: Lvov (now Ukraine), Olomouc (now Czechoslovakia), Szeged (now Hungary), Oradea and Arad (now Roma54

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

nia) were among the places where he served. Jfinos did not like life in the army, and w h e n his health deteriorated he requested to be pensioned off. Permission was given and in 1833 he moved back to Tirgu Mure~. When asked to do so, Carl Friedrich Gauss commented extensively on the Appendix. In a letter to Farkas he p r o p o s e d names for some basic notions, showed h o w one proof could be done differently, and suggested a way to continue the research. Concerning the Appendix as a whole, he said that he couldn't praise J~inos for it because "praising him would mean praising myself: because all the contents of the work, the way followed by your son, and the results he obtained agree almost from beginning to end with the meditations I had been engaged in for 30-35 years already." From an earlier correspondence of Gauss this appears to be true. However, he exaggerated the number of years. Farkas was delighted that his son had apparently had the same ideas as the famous Gauss, but the son himself was embittered by these comments. Even though he had ample opportunity, J~nos did little mathematics after his retirement at the age of thirty-one. He worked on proving the consistency of his geometry, but never published anything. In 1837 he sent a paper, Responsio, to a competition on the geometric representation of complex numbers. In his unsuccessful entry he made references to the Appendix, which probably hadn't reached the referees. J~inos Bolyai is one of the few 19th-century mathematicians of whom no portrait has remained. Recognition for his work did not come until the 1870s, more than 10 years after his death. The name "BolyaiLobachevski geometry" became established in the last years of the 19th century under the initiative of Henri PoincarC In 1911 the bodies of father and son were exhumed and removed to adjacent graves in the Reformed cemetery of Tirgu Murew The large cemetery is a 10minute walk from the museum. There are no signs to indicate the way to the graves of the two mathematicians and I had to ask a caretaker for the exact location. In his History of Mathematics Florian Cajori relates that Farkas was a very modest man w h o didn't want a monument over his grave, just an apple tree in memory of the apples of Eve and Paris that brought chaos and the apple of Newton that "elevated the earth again into the circle of heavenly bodies." I didn't have the botanical knowledge to check whether it actually was an apple tree, but the tree over the graves was so prominent that, even on the bright, sunny spring day when I was there, a maximal lens opening was needed to take a picture.

Franklin College via Ponte Tresa 29 6924 Sorengo, Switzerland

New Pathways in Serial Isogons Lee C. F. Sallows

If I have stood on the shoulders of giants it is because I tried to see further than they could. --Isogones of Retsina (c. 666 BC)

So I undertook further study of serial-sided polygons--or "golygons" as I playfully dubbed early specimens. Polygons may be defined to include self-crossing as well as simple figures, and so it is with golygons when defined as serial-sided, closed paths on a square

A Pretty Polyomino They say the road to Hell is paved with good intentions. A recent intention of mine was to solve a puzzle in taxicab geometry. During the attempt, absentminded doodling on squared paper led to the incidental discovery of an arresting figure: a polyomino having eight sides of length 1, 2 . . . . . 8 units, the latter occuring in consecutive order around the boundary (see Figure 1). This was already an interesting find. Yet, glancing again at m y sketch the next day, I was seized by a wild surmise. A quick trial at once realised hope: the polyomino has a shape satisfying the Conway criterion [1], and is thus able to pave the plane. Now here was a prize to celebrate. As below, so above: The road to Heaven is paved with good irroentions.

Figure 1. Tiling the plane with a serial-sided polyomino. THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2 9 1992 Springer-Verlag New York 5 5

Figure 2. Three “golygons” of order 16. In all, there are 28 paths of order 16, the remaining 25 being self-crossing.

grid; self-overlapping line segments may occur also. It has been proved that the number of sides in these figures is always a multiple of eight. Figure 2 shows some examples. These polygons formed the focus of a memorable collaboration resulting in a joint article [2]. Interested readers may like to consult this paper, or a subsequent summary [3]. One let-down, howeveramong hundreds of cases discovered, Figure 1 remains the only instance with the paving property! Beyond golygons, however, we have serial-sided isogons (iso, meaning equal; and gon, which means angled) in general. That is to say, closed serial-segment paths in which the absolute angle between consecutive segments (or sides, or edges) is again constant, but not necessarily 90 degrees. The term “absolute” stresses that angle magnitudes are equal; in zig-zag figures the sign of angles at different corners obviously varies. Thus, as with right-angled types, given the angle employed, any serial isogon is completely described by its sequence of left/right turns, as encountered in traversing the path in natural order of edges. Figure 3 shows some examples using angles of 60” and 120”, the earli-

Figure 3. Serial isogons of 60’ and 120”. These are all paths on an isometric grid; the figures opposite are drawn to a smaller scale. (a): N = 9, the shortest path for 60”, a simple polygon. fb): N = 11, the next shortest, a self-crossing path. k): N = 12, one of the two self-crossing paths for this order. (d): Repeating a path with new segments of length N + 1, N + 2, . . . , produces a “second harmonic” (dotted) of the original (a). (e): The sequence of turns in path (a) is changed from 56

THE MATHEMATICAL INTELLIGENCER

VOL. 14, NO. 2.1992

est specimens discovered. N is the order of the path, its number of edges.

/ 3

Rational Isogons For what angles can serial isogons be found? A full answer is still wanting, but an excellent start due to Hans Comet is his proof that at least one such path exists for any angle cx that is a rational fraction of 360 degrees, that is, for which c~ = (re~n) 9 360 ~ m and n both positive integers. The detailed proof is on the long side, but at its heart is a simple recipe for constructing an isogon using any desired rational angle. The notions of edge direction and path turning angle are useful in explaining this. Consider a moving point tracing an isogon in serial order of edges. By the direction, d n, of an edge we mean that of the point tracing it, and by the turning angle, ";, of the path, we mean the angular deflection entailed in changing from one direction to the next. This is simply the (absolute) angle made between any edge and a line

constant2//~/'~ a n g l e AZturning /~ ~_angle 1

edge direction

Figure 4. Every edge (1, 2, 3 . . . . ) points in a certain direction (d 1, d 2, d 3. . . . ). The turning angle ~ is the supplement of the constant angle a.

extending the previous edge, and is equal to 1180-c~ I degrees (see Figure 4). Clearly, if c, is rational then so is % implying that there exists an integer D such that D. T is a whole number. D is of course the denominator in the rational fraction % reduced to lowest terms. Thus, D repeated turns of -r degrees to right or to left equals some whole number of 360-degree rotations, meaning a return to the initial orientation. This shows that the number of available edge directions in any rational isogon cannot exceed D, and that they

s

< \,,,J \ 8

24 4

(g) (h) 12

/

)

RRLRRLRRL to RRRRRLRRRRRLRRRRRL, a variation on Cornet's rule (see text). (f): N = 24, a = 120 ~ one of 20 simple paths from the total of 139 for this order. (g): N = 24, ~x = 120~ a self-crossing path. (h): N = 12, the shortest serial isogon for 120 ~ Note h o w the same figure is contained in (g).

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

57

/20~ 3

6 \

treeo,

1

6~- possibleedges"~ ~2 16

Figure 5. In a path using turning angle ~ = 60~ = V~ 9360' all edge directions will correspond with the directed sides of a regular hexagon. correlate with the sides of a regular D-gon, suitably oriented. In a p a t h using c~ = 120 degrees, for instance, "r = 60 or V6 of 360 degrees, so that D = 6, meaning that every edge parallels a n d points in the same direction as one of the directed sides of a regular hexagon, appropriately aligned (see Figure 5). Cornet's construction rule is n o w easily explained. Starting with the first turn from edge 1 to edge 2, form the rational angle c~ between successive edges so that every following turn is to one side only (say, right), excepting turns D, 2D, 3D, etc., which are m a d e to the other side (left). That is all. A p p e n d i n g segments in this way, we find that at length the open e n d of the first segment is rejoined, the resultant closing angle then m a d e b e t w e e n the longest and shortest edges being oL, as required. The final, automatic re-turn from side N to side 1, an integral multiple of D, will be to the left. But w h a t is the order of the resulting isogon, and w h y is correct closure guaranteed?

Cornet's Proof (D Odd)

d,

14

d5

23

Figure 6. Cornet's Rule produces a serial-sided isogon. The angle of 108 ~ implies 5 edge directions, thus: Repeat 4 turns right, then I turn left, until closure, which occurs after 5 x 5 = 25 segments. The turning angle is 72~ = Vs of 360 ~ dl

d2

d3

d4

ds

1 8 15 17 24

2 9 11 18 25

3 10 12 19 21

4 6 13 20 22

5 7 14 16 23

+ Figure 6 shows an instance of such a path in which N 65 65 65 65 65 = 25 and c~ = 108 degrees. Hence the turning angle ~" = 180 - 108 = 72 ~ or ~/s of 360 degrees, from which D As we see, the rule results in column sums that are = 5, implying 5 available directions. As the figure itself equal. But this is to say that the total distance travelled suggests, the latter correspond to those of a regular pentagon with directed edges all arrowed clockwise. In general, as already seen, the possible edge directions for a n y rational isogon will be those of a similar D-gon, suitably oriented. Starting anywhere, we label these d~, d 2. . . . dD, a r o u n d the D-gon perimeter (see Figure 7). To u n d e r s t a n d w h y the rule m u s t return us to the starting point, consider a table showing h o w edges 1, d5 2, 3 . . . . are allotted to directions d 1 to d5 in Figure 6. Note the step left after every 4 steps right (d5 is of Figure 7. Starting anywhere, the directions of a regular pencourse adjacent to dl). tagon are labelled d 1 to ds.

dl~

58

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

_ / d4

in every direction is the same (65 units). The vectorial s u m or final displacement from start to finish is thus the same in effect as traversing a regular pentagon of side 65; that is, zero displacement, indicating that the path ends where it begins. Furthermore, edge 25, the longest, falls in a column adjacent to dl; the angle formed with edge I is thus 108 degrees, as required. Since the table comprises D rows of D entries, in this case the order of the isogon is D 2 = 25. It is easy to see w h y Cornet's rule must result in a table with these properties w h e n e v e r D is odd. Consider the same table with r 9D subtracted from every n u m b e r in the rth row, row 0 being at the top.

dl

d2

d3

d4

d5

1 3 5 2 4

2 4 1 3 5

3 5 2 4 1

4 1 3 5 2

5 2 4 1 3

15

15

15

15

15

+

A'glance n o w shows that the columns p r o d u c e d by the rule are really cyclic permutations of the n u m b e r s 1, 2 . . . . . D, a d d e d to which are the r terms 0D, 1D, 2D . . . . . (D - 1)D, in every case. Hence column sums must always agree, their totals equalling (!6) 9 D(D 2 + 1), as a simple calculation will show. Likewise, the rows are also cyclic permutations of 1, 2. . . . . D. The table is t h u s a latin square, its bottom row being completed by an entry falling in column d 2. The correct closure angle is thus assured. In this light, Cornet's rule turns out to be not so different from one of those old-fashioned recipes for m a k i n g a magic square! In the above example "r was !/5 of 360 ~ Suppose, instead, the constant angle o~ had been 36 ~ so that "r becomes 144 ~ or V~ of 360 ~ Using arguments similar to the foregoing, it is easy to s h o w that column sums, closure angle, a n d order all remain i n d e p e n d e n t of the numerator in -r, provided the denominator (representing the n u m b e r of directions, D) is u n c h a n g e d if the n e w fraction is reduced to lowest terms. The following table illustrates our example. The corresponding isogon, a sorcerer's pentacle to delight any apprentice, is seen in Figure 8. dl

d2

d3

d4

ds

1 8 15 17 24

4 6 13 20 22

2 9 11 18 25

5 7 14 16 23

3 10 12 19 21

65

65

65

65

65

Figure 8. An isogon of order 25, using an angle of 36 ~ This is a close relative of Figure 6: the same rule applied with the turning angle n o w doubled to 144 ~ = ~/5 of 360 ~ Comet's

Proof (D Even)

What h a p p e n s w h e n the n u m b e r of directions is even? Cornet distinguishes two cases, D = 4k, and D --- 4k + 2; where k is a positive integer. Taking the first, suppose k = 2, so that D --- 8, as in the isogon seen in Figure 9, where 9 is 45 degrees, or !/a of 360 ~ The eight possible edge directions are t h e n indicated by the sides of a regular octagon, as s h o w n in Figure 10. As the labelling reflects, here directions appear in

\ +

Figure 9. A path of order 32, with a = 135~ The turning angle is 45 ~ or !/s of 360 ~ so that D, the number of edge directions (8) is of form D = 4k, k = 2. THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992 59

opposite pairs, s o m e t h i n g that cannot occur w h e n D is odd. The effect of Cornet's rule is this n e w situation is seen in the c o r r e s p o n d i n g table: dl

d2

d3

d4

~1

1 11 21 31

2 12 22 32

3 13 23 25

4 14 24 26

5 15 17 27

6 16 18 28

7 9 19 29

8 10 20 3O

64

68

64

68

64

68

64

68

2 10 18

3 11 13

4 12 14

5 7 15

6 8 16

27

30

27

30

27

30

3

13 2-

14

+

This time c o l u m n s u m s are no longer equal, but those of opposite direction pairs are, a n d thus cancel exactly. The distances traversed in direction dl, for instance, a r e 1 - 5 + 11 - 1 5 - 17 + 21 - 27 + 31 = 0. Hence, as previously, the final vectorial s u m is zero, so again, path start coincides with path finish. H o w ever, the point of p a t h closure, occurring with the first entry to complete a r o w while simultaneously occupying a column adjacent to d 1, n o w falls o n s e g m e n t 32. Thus, N is no longer equal to D 2. I leave it for readers to prove that w h e n D = 4k, N = D2/2. We are left with the second case, D = 4k + 2. For simplicity, s u p p o s e k = 1, so that D = 6, as in the isogon seen in Figure 11. The associated edge directions are r e p r e s e n t e d b y the sides of a regular hexagon. D being even, directions again come in pairs of opposites. The c o r r e s p o n d i n g table for Cornet's rule is then:

1 9 17

11

16

Figure 11. An isogon of order 18, with or = 120". The turning angle is 60* or !/6 of 360*, so that D, the number of edge directions (6) is of form D = 4k + 2, k = 1.

In our examples for even D, "r was respectively 1/8 and !/6 of 360 degrees. Cases for w h i c h the n u m e r a t o r is greater than I are analogous to that looked at for o d d D, as in Figure 12, w h e r e "r is 3/8 of 360 ~ This completes our survey of Cornet's proof that a serial isogon is always constructible for any angle that is a rational fraction of 360 degrees. Paths generated b y his rule are frequently o r n a m e n t a l flowers (or fireworks?) as seen in Figure 13.

+

C o l u m n sums are not equal, and neither are those of opposite direction pairs. H o w e v e r , the total displacem e n t in alternate directions is the same: For d 1, d 3, and ~2 it is 27-30, for d 2, ~ , a n d ~3 it is 30-27. The net effect is thus that of circumscribing a regular (D/2)-gon, or equilateral triangle of side 3, and again equals zero. The column in which the final entry falls remains as it was for D = 4k, so that again N = D2/2.

dl

d3d2~~d4 d3 dl Figure 10. In a regular octagon the edge directions occur in opposite pairs. 60

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

Figure 12. A path of order 32, ot = 45*. This is a relative of Figure 9; "r is now 3/8 of 360~ Cornet's rule is unaffected by the change in numerator.

Z P

P

N

II

II

= 98, u = 51.42°; T = 0/14 of 360°. II

Figure 13. N

mE MAmEMATICAL lNTELLlGENCER VOL. 14, NO.2, 1992

61

Hans Cornet is a retired high school mathematics teacher in The Hague. His work on serial isogons--which continues--is pursued entirely from personal interest; in the absence of this article it would never have been published. I am sincerely grateful to him for the privilege of presenting a significant result, and also for his g e n e r o u s h e l p a n d kind e n c o u r a g e m e n t throughout the preparation of this paper. Dank je, Hans!

P a t i e n c e is a V i r t u e

Trivial variations on Cornet's rule give rise to endless series of isogons for every rational angle. Two methods are as follows. 1) On completing a path of order N, using the same rule, continue adding edges of length N + 1, N + 2, and so on, up to edge 2N. The resulting path is a "second harmonic" of the original. An example is seen in Figure 3(d). The process is endlessly repeatable. 2) Modify Cornet's rule so that the exceptional turns fall on 2D, 4D, 6D, etc. (rather than D, 2D, 3D, . . . ); see Figure 3(e). Compare Figure 6 (N ~- 25) with Figure 14 (N = 50) to see how we go once, then

Figure 14. N -- 50, a = 108~ A variation on Cornet's rule yields a doubled version of Figure 6. This is merely the second term of an infinite series. The process is a close cousin of the "'harmonic" effect seen in Figure 3(d). 62

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

Figure 15. A computer program that plays patience discovered this serial isogon for N = 25 and ot = 108~ This is the same order and angle as Figure 4. twice around the spiral before changing tack. Again, the principle can be expanded without limit. Both methods may be applied alternately in one path. Even including these variants, however, Comet's rule does not account for every rational isogon, as most of the examples of Figure 3 attest. Nevertheless, his approach suggests a way to discover the remaining paths. Imagine a game of patience played with numbered cards and H hats arranged in a ring. Starting anywhere and discarding in turn, 1, 2, 3, . . . , successive cards may be dropped into a hat only if each is adjacent to the last one used. This gives a choice of two hats each time. The aim is to end with the sum of the numbers in every hat the same, provided the last card thrown occupies a hat next to the first one chosen. Alas, some of us are impatient; a brute-force search by computer discovered the following 25-card solution for a game using 5 hats: hi

h2

h3

h4

h5

12 14 16 23

11 13 17 24

4

65

65

1

2

3 5 7 9 19 21

6 15 20 22

65

65

8 10 18 25 + 65

Here the computer has found a second isogon with angle and order as in Figure 6 (ct = 108 degrees, N = 25), but a different sequence of turns. The associated path is quite as crooked as its table (see Figure 15). This shows that although Cornet's rule yields a winning strategy at patience, other solutions may exist. Except

in a few instances for small N, however, the number of solutions extant for each angle/order cannot, as yet, be predicted. As it happens, Figure 15 is one of three distinct solutions for this angle and order. Some readers may enjoy trying to find the missing one for themselves. The isogon in Figure 6 has a further remarkable feature. Recall that 108 degrees is the inside angle of a regular pentagon. N o w look closely at the area bounded by edges 5, 10, 15, 20 and 25, in the centre of the figure. It can be proved that the shape outlined there is indeed a regular pentagon! After this, readers may not be surprised to learn that a regular heptagon nestles at the centre of the analogous path using the heptagon angle of 128.57 degrees. Surprisingly, however, there the pattern ends, for no other such polygons have been found in comparable paths for different angles. This curiosity remains to be explained. Irrational Isogons

Not every isogon is detectable in the way described above. Figure 16 shows a 6-sided path using an angle not expressible as a rational fraction of 360 degrees. Here o~ = arc cos (3/4) radians ( = 4 1 . 4 0 9 6 . . . degrees), as the added parallelogram construction serves to illustrate. Moreover, this is in fact the smallest (shortest path) serial-sided isogon of all. Its discovery is due to a computer program that uses a turtle approach to plot paths as it executes a brute-force search for isogons of any order. Even for N as small as 6, however, the number of different possible angles between 0 and 180 degrees remains infinite. What kind of a program can examine paths for them all? My eventual algorithm turned out surprisingly simple, although humanassisted. In the program, after specifying some N and o~, the order and angle of a path to be investigated, simple trigonometry is used to determine the positions of successive vertices for every possible path, one after another. A path is just a sequence of left/right turns, represented as a string of N bits: 0 = left, 1 = right. When called, a standard routine loads an array with a new permutation of bits that now defines the next path to be plotted. Starting at the origin of the Cartesian plane, edge 1 of the path is assumed coincident with the positive x-axis. On completing a path, the coordinates of the end point of the final segment can be checked. If these were again 0,0 then we would have a closed path, and if the angle calculated between the final segment and the x-axis was again % then the sequence of turns under test would give rise to a serial isogon. What I did was to accept any test whose end point lay within a small window centered on the origin, and whose reentering angle was within 2 ~ of a; then I

1+3 x

\

\

\

5

N\

\

\

X

4 +

\ \\6

%

\

2'~N N

""\\x2 V a r c

\

\

\

cos (4.5/6) 4.5

1

Figure 16. The smallest serial isogon of all is an order 6 path using an angle that cannot be expressed as a rational fraction of 360*: arc cos(u Segments lie along 3 directions.

retested with slightly incremented or decremented path angle to home in on an apparent solution. As the last stage, pencil-and-paper work is necessary to make mathematical sense of the angle empirically arrived at, and verify it is really a solution. For instance, 4 1 . 4 0 9 6 . . . degrees means little until independent reasoning reveals it as arc cos(3/4) radians, as in Figure 16. In practice, running time on my PC became prohibitive for orders above 16. This could doubtless be improved upon, if desired, although examination of higher N is still within reach if the search is restricted to a single angle. In the latter case, when the angle is irrational, a little thought shows that testing paths of uneven order can be skipped. Beyond order 6, the next largest isogons brought to light by the program are two of order 8: one of them the tiling polyomino, the other a related path, but again using an irrational angle (see Figure 17). This fresh discovery prompted a new result covering irrational isogons in which just 3 edge directions, the minimum possible, occur. Below we shall prove that in that case either N = 8k and o~ = arc cos(4k/(4k + 1)), or N = 8k - 2 and cx = arc cos((4k - 1)/4k), where k is an integer.

ref!ect ,

\

\

\

\

"-'r

,\

NN\\N\

.N N

3

,) ~,

"x s

\

I "\"

1

squeezed order 8 p o l y o m i n o

Figure 17. There are two serial isogons of order 8: the tiling polyomino and this related path using an irrational angle of arc cos (%). The figure illustrates their relationship. Segments again exhibit 3 directions. THE MATHEMATICALINTELLIGENCER VOL. 14, NO. 2, 1992 63

N\

\ \

Then, as the perpendicular in the vector diagram helps to show: IB + C I = 2 . IBI. cos(cx)

NN

= 2 . ICI. cos(o0 = (IBI + ICI)" cos( ) = IA I, as seen above,

. ~ / ' 1+3+5+--,N-1

\,,fc

so that cos(a)

Figure 18. In tridirectional isogons the net displacement in each direction can be represented by three vectors.

-

IAI IBI + ICl 1+3+5

+...

+N-

1

2+4+6+...+N Irrational I s o g o n s U s i n g 3 D i r e c t i o n s

Consider a tridirectional isogon in w h i c h oL(and thus "r) is irrational. The net displacement a w a y from the path origin in each direction m a y be r e p r e s e n t e d b y 3 vectors, A, B, C, the angles b e t w e e n t h e m being the same as those b e t w e e n their c o r r e s p o n d i n g directions, as in Figure 18. This will be "r in two out of three cases only, for otherwise 3"r w o u l d equal 360 ~ implying a rational ,r. Evidently the remaining angle is 2 9 180 - 2T = 20~. Thus only one of the three vectors is " c e n t r a l " in bisecting the angle b e t w e e n the two others: A. Significant inferences n o w follow from this. Recall that adjacent isogon edges can only occupy directions separated b y angle "r. S u p p o s e the direction of edge I is that of A, the central vector (later w e shall see that this m u s t be the case). T h e n that of edge 2 is B or C. But the angle b e t w e e n B and C is not % and so edge 3 can only b e l o n g again to A. Similar logic applies to succeeding cases, s h o w i n g that edges of u n e v e n length must all point in direction A, w h o s e magnitude, IA], is thus 1 + 3 + 5 + . . . + (N - 1)(recall N is even). H e n c e IBI + ICI, the c o m b i n e d lengths of the residual edges, m u s t equal the s u m of the remaining e v e n numbers. Moreover, since the p a t h r e p r e s e n t e d is closed, the sum of the vectors is zero. This m e a n s that the resultant of vectors B a n d C m u s t be equal a n d opposite in sign to A, a n d since the angle b e t w e e n B a n d A is the same as that b e t w e e n C a n d A, B a n d C m u s t be equal in length, so that IBI = ICI, with IBI + ICI = 2 + 4 + 6 + . . . + 2m = N, a n d m is an integer. Now, for w h a t values of N is it possible to divide 2, 4, 6 . . . . , 2 m into two groups of equal sum? The question is easier to a n s w e r in terms of their half values, every partition of 2, 4, 6 . . . . , 2 m being mirrored in a parallel partition of 1, 2, 3 . . . . , m, w h o s e total is V2m(m + 1). Bisection of the latter t h e n yields two groups of s u m V4m(m + 1), itself an integer. So, if m is even (and thus m + 1 odd), m will have to be doubly even to allow division b y 4. Or, b y the same argument, if m is odd, t h e n the d o u b l y even term m u s t be m + 1. In summary, either m = 4k or m = 4k - 1, w h e r e k is an integer. H o w e v e r , 2m = N, which s h o w s that N = 8korN= 8 k - 2. 64

T H E MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

N2/4

N

(N + 2)N/4 = N + 2 cx = arc cos(N/(N + 2)); or o~ = arc cos (4k/(4k + 1)) w h e n N = 8k and c~ = arc cos((4k - 1)/4k) w h e n N=8k-2, which is w h a t we set out to prove. We have yet to see what h a p p e n s if edge I is aligned with a non-central vector, B or C. It is easy to see that from w h i c h

1

2

Figure 19. Tridirectional paths using irrational angles have orders of form N = 8k and 8k - 2; here k = 2. Above: one of the 7 paths of order 16; ot = arc cos (%). Below: one of the 4 paths of order 14; ot = arc cos(~,~).

the roles are t h e n reversed, with IAI = 2 + 4 + 6 + . . . + N a n d [ B [ + [C[ = 1 + 3 + 5 + . . . + ( N - 1). H o w e v e r , since the first total is greater t h a n the second, a zero vector s u m w o u l d be impossible, e v e n if ~were 180 ~. Hence, no such path exists. Figures 16 and 17 s h o w the single instances of such isogons for k = 1; w h a t h a p p e n s b e y o n d ? For k = 2 the c o m p u t e r finds four of o r d e r 14 and seven of o r d e r 16, these two totals reflecting the n u m b e r of distinct partitions of 2, 4 . . . . . 14 a n d 2, 4 . . . . 16 into two subsets of equal sum: the edges assigned to directions B a n d C; see Figure 18. M o r e generally, a partition scheme yielding solutions for every k is as follows: {1}: 2,6,10 . . . . . 4k - 2; 8, 4k + 10 . . . . . 8k {2}: 4,8,12 . . . . . 4k - 4; +6 ..... 8k-2 {1}: 2,6,10 . . . . . 4k - 2; +8 ..... 8k-4 N = 8k - 2: {2}: 4,8,12 . . . . . 4k - 4; 6,4k + 10 . . . . . 8k-

4k + 4, 4k +

N = 8k:

4k,4k + 2, 4k 4k,4k + 4, 4k 4k + 2,4k + 2

N=8

The above scheme is easily verified by s u m m i n g the c o m p o n e n t arithmetic series and c o m p a r i n g partition totals. In cases of 3 directions, therefore, we are able to create a n d c o u n t paths for e v e r y possible order. As might be expected, not e v e r y irrational isogon discovered b y c o m p u t e r is tridirectional. Research into these more complicated types continues. Pretty Polyiamonds

Variations o n the serial-sided t h e m e will have occurred to readers: paths w h o s e edge-lengths listen to different laws: arithmetic or g e o m e t r i c series, s e q u e n c e s of primes, etc. Paths in higher d i m e n s i o n s also await investigation. To conclude this s u r v e y of serial planar types, h o w e v e r , I w o u l d like to m e n t i o n one further variation. I already r e p o r t e d the d i s a p p o i n t m e n t that no m o r e serial isogons have been f o u n d that tile. Figure 1 remains u n i q u e in this respect. But Figure 1 is a polyomino: a figure o n a right-angled grid that can itself be tiled with squares. In this light, a n o t h e r a v e n u e to ex-

N=9

N=5

i

9

N=7

Figure 20. The serial-sided polyiamonds of order N ~ 10. THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

65

/ /VVXAAX~

/ Figure 21. Polyiamond analogs of the order 8 tiling polyomino.

plore is that of serial-sided shapes on an isometric grid, or in other words, serial polyiamonds, which are figures that can be tiled with equilateral triangles. Consider first the more general case of closed serial paths, including self-crossing paths, on an isometric grid. Three straight lines cross symmetrically at every node, which means that the angle between successive path segments can be 60 or 120 degrees. Hence, paths are of two kinds: isogonal (using either 60 or 120 degrees), and what I call bisogonal (those mixing both angles). Then, serial-sided polyiamonds correspond to the simple polygons of both types. The fact that every 60 or 120 degree isogon (such as those in Figure 3) is a path on an isometric grid forms the basis of two neat results, due to Martin Gardner: 1) For an angle of 60 degrees, no isogon exists when N = 1 modulo 3 (they seem to exist for all other N > 8); 2) for any isogon with an angle of 120 degrees, N is a multiple of 6. The proofs are not very difficult; one 66

THE MATHEMATICALINTELLIGENCERVOL. I4, NO. 2, 1992

Figure 22. The smallest serial-sided polyiamond tiles in two ways.

hopes they will appear elsewhere. On the other hand, the problem of enumerating 60~ ~ paths for different orders remains unsolved. Computer searches for closed paths on an isometric grid are made easy through the ability to measure movement along three (lattice) coordinates, I, J, K. The turns in a bisogonal path are encodeable as 4-valued elements: 0 = left 60~ 1 = right 60~ 2 = left 120~ 3 = right 120~ say. Integer variables I, J, K are updated after each edge. Exhaustive testing of turn sequences will thus discover every serial path for a given N. A program of this kind has identified 18 serial-sided polyiamonds through order 10. Presented in Figure 20, the set offers an attractive extension to a familar topic in the recreational literature. Glancing over the group, note that one of the shapes is an order-9 isogon, the smallest for 60 degrees. See next how two of the order-8 figures resemble the original polyomino. However, a moment's thought shows that square grid

Springer For Mathematics vvxm/VVVV

P. Ribenboim, Queen's University, Kingston, Ontario, Canada

The Little Book of Big Primes This abridged version of The Book of Prime Numbers, also by Ribenboim, presents records concerning prime numbers. It also explores the interface between computations and the theory of prime numbers. There is an up-to-date historical presentation of the main problems pertaining to prime numbers, as well as many fascinating topics, including primality testing. Written in a light and humorous language, this book is thoroughly accessible to everyone. 1991/app. 304 pp./Softcover/$29.50 ISBN 0-387-97508-X New,

softcover edition available

--

H.-D. Ebbinghaus and H. Hermes, Universitat Freiburg; F. Hirzebruch, Max-Planck-Institut ftir Mathematik, Bonn; M. Koeeher (1924 - 1990) and R. Remmert, Universit~,t Mi.inster; K. Mainzer. Universit~itAugsburg: J. Neukirch. Universitat Regensburg; and A. Prestel, Universit~it Konstanz, all FRG With an Introduction by K. Lamotke English Edition edited by J. Ewing Translated by H.L.S. Orde

Numbers Figure 23. T w o t i l i n g s b y a serial-sided p o l y i a m o n d of order 8.

paths can always be projected onto a parallelogram lattice, after w h i c h it c o m e s as n o s u r p r i s e t h a t t h e s e s h a p e s tile a n a l o g o u s l y to t h e f o r m e r ( F i g u r e 21). M o r e p l e a s i n g is t h e p r e s e n c e of t w o g e n u i n e l y n e w p r e t t y p o l y i a m o n d s , e a c h of w h i c h p a v e s i n t w o d i f f e r e n t w a y s (Figure 22 a n d 23). T h i s s o o n l e a d s i n t o t h e r e a l m of s e r i a l - s i d e d tiles, i n g e n e r a l . But t h a t is a n o t h e r m e s sage i n a d i f f e r e n t b o t t l e f r o m y e t a f u r t h e r o c e a n .

References 1. Schattschneider, D. "Will It Tile--Try the Conway Criterion!" Mathematics Magazine, Vol. 53, No. 4, September 1980, pp. 224-233. 2. Sallows, L., Gardner, M., Guy, R., Knuth, D. "Serial Isogons of 90 Degrees," Mathematics Magazine, Vol. 64, No. 5, Dec. 1991, pp. 315-324. 3. Dewdney, A. K., "Mathematical Recreations," Scientific American, July 1990. Vol. 263, No. 1, pp. 86-89.

Buurmansweg 30 6525 RW Nijmegen The Netherlands

This is a book about the system of numbers - - all kinds of numbers, from integers to p-adics, from rationals to octonions, from reals to infinitesimals. Who first used the standard notation for pi? Why was Hamilton obsessed with quaternions? What was the prospect for"quaternionic analysis" in the 19th century? This is the story about one of the major threads of mathematics over thousands of years. It is a story that will give the reader both a glimpse of the mystery surrounding imaginary numbers in the 17th century and also a view of some major developments in the 20th century. 1991/395 pp., 24 illus./Softcover/$39.00/ISBN 0-387-97497-0

Graduate Texts in Mathematics. Volume 123 Readings in Mathematics

Order Today!

ThreeEasyWaysto Order: 9Call: Toll-Free 1-800-SPRINGE(R):1-800-777-4643. In NJ call 201-348-4033 (8:30 AM --4:30 PM EST). Your reference number is H792. 9Write: Send paymentplus $2.50 for postage and handlingto: Springer-VerlagNew York Inc., - Dept. H792, PO Box 2485, Secaucus. NJ 07096-9812 9Visit: Your local technical bookstore. Instructors: Call or Write for informationon textbook examinationcopies!

@ Springer-Verlag New York Berlin Heidelberg Vienna London Paris Tokyo Hong Kong Barcelona

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.

This issue's column will be devoted to geometry, in fact, to triangles with a brief detour into quadrilaterals. From Euclid to Descartes to Mathematica to Oblivion? Once again our subject is the interaction of mathematics and computers. Computers can solve mathematical problems. They can also pose them, and now, it seems, they may be capable of killing off whole branches of the subject, much in the same w a y professional chess may be killed off when and if a computer becomes the world champion. A potential victim is the most venerable branch of all, Euclidean geometry, meaning specifically, the geometry to be found in the books of Euclid. These thoughts were stimulated by some recent explorations by Clark Kimberling involving centers of triangles, a center being for example the centroid, the center of the inscribed or circumscribed circle, the intersection of the altitudes (orthocenter) etc. where "etc." includes some 91 different notions of center described by Kimberling. It is easy to see h o w one can define centers essentially at will. Namely, if a, b, and c are the lengths of the sides of a triangle and fix, y, z) is some function which is symmetric in y and z, then the corresponding center is the point w h o s e distances from sides a, b, and c are proportional to f(a, b, c), f(b, c, a), and f(c, a, b), respectively. The function f is said to give the trilinear coordinates of the given center. Of course interesting centers are ones which correspond to natural geometric constructions. About half of the centers on Kimberling's list have appeared in the literature and the rest were discovered (invented) by him. One of the striking things that shows up experimentally is that among the 91 centers there are an enormous number of collinearities. Indeed, all 91 points can be covered by only 103 different lines (out of a * C o l u m n editor's address: D e p a r t m e n t of Mathematics, University of California, Berkeley, CA 94720 USA.

possible 4095 if no three of the points were collinear). The classical example of collinearity is the Euler line, which passes through the centroid, the circumcenter, and the orthocenter, with the centroid lying two-thirds of the way from the orthocenter to the circumcenter. This result appears as an exercise in many books on elementary analytic geometry. It was also known that the Euler line passes through the center of the 9-point circle. If you don't remember the definition of the 9-point circle, well neither do I, but in any case its center is midway between the circumcenter and the orthocenter. Kimberling finds eight other centers which also lie on the Euler line. It should be emphasized that these collinearities have all been discovered with a computer by taking a few numerical values for a, b, and c and noting that the various centers line up to within ten or so decimal places. Of course, all but a handful of these collinearities have never before been seen by man or beast. One might think of them as hundreds of new theorems in search of proofs. To take one example, the Fermat point of an acute triangle is the point which minimizes the sum of its distances from the three vertices. The Napoleon point (said to have been discovered by the Emperor himself before he gave up geometry in favor of world conquest) is found by constructing equilateral triangles on each of the three sides of a triangle and then connecting their respective centers to the opposite vertices of the original triangle. The three lines are (theorem) concurrent and their intersection is the Napoleon point. N o w it turns out that, for no apparent reason, the line through the points of Napoleon and Fermat passes through the circumcenter, a fact that could hardly have been predicted. However, once the phenomenon has been observed a proof is immediately at hand. In principle, of course, this was already true after Descartes's discovery of coordinate geometry, but in practice it might be quite difficult and " m e s s y " to derive and solve the polynomial equations involved. This is where symbol-manipulating programs such as Mathematica come in. Mathematica doesn't mind messy. Just feed it

68 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2 9 1992 SpringerVeflag New York

the trilinear coordinates of the three points, which in this case are

but almost never like this

Fermat

{cosec(A + ~r/3), cosec(B + "rr/3), cosec(C + rr/3)} Napoleon {cosec(A + ,rr/6), cosec(B + ~r/6), cosec(C + rr/6)} Circumcenter {cosA, cosB, cosC} where A, B, C are the angles of the triangle. Multiply the first two rows by sin A sin B sin C to get rid of denominators. Mathematica then expands the determinant as a polynomial in sines and cosines, which in this case turns out to be zero, Q.E.D. As another curiosity, there is a second Napoleon point in which the construction is the same except that this time the equilateral triangles are constructed on the inside rather than the outside of the original triangle. In this case the line through this second Napoleon point and the Fermat point passes through the center of the 9-point circle rather than the circumcenter. H o w would one ever find a synthetic proof of that, I wonder but of course Mathematica takes it right in stride. Surely this is a rather strange state of affairs. Everything is being done by the computer. Program A goes on a voyage of exploration and comes up with a vast number of theorems. Then program B takes over and supplies the proofs, and while all this is going on the investigator just sits back and watches. The robots have taken over. It makes one reflect a bit on what we are trying to achieve in doing mathematics. It is certainly impressive to suddenly learn hundreds of new facts in a discipline that people have worked in for more than two millennia. But mathematics, and science generally, is concerned with much more than compiling a huge catalogue of facts. The hope is to find general principles from which the facts can be deduced, and the robots don't seem to be very helpful for this. They tell us what is true but don't tell us why. They supply lots of information but little insight.

Donald N e w m a n has pointed out, however, that almost any way you look at it, a "random triangle'" is much more likely to be obtuse than acute. H o w does one pick a triangle at random? One possibility is to pick three positive numbers for the angles at random subject to the condition that their sum is "ft. If this is the criterion then it is quite easy to see that three out of four triangles are obtuse. This is equivalent to the observation that in the unit 2-simplex in R3 the set of points, all of which have coordinates that are less than 1/2, has 1/4th the area of the simplex. Alternatively, one might pick the side lengths at random from the unit interval and ask, of those triples which correspond to triangles what fraction correspond to acute angles. Here the analysis is more complicated but the answer turns out to be "rr/4. Still another possibility is to pick three points at random on the unit circle. Here the answer is again that three times out of four the triangle will be obtuse. Reason: the triangle will be acute if and only if the origin lies in the convex hull of the three points, which is equivalent to requiring that the origin be a linear combination of the three points considered as vectors and the coefficients all have the same sign; this will happen one time in four.

Problems Another cheerful fact about the square of the hypotenuse (91-7) by D. J. Newman (originally published in A Problem Seminar, Springer-Verlag, 1982). Let F be a finite set of points in a right triangle. Prove that there is a polygonal path through the points such that the sum of the squares of its segments does not exceed the square of the hypotenuse.

Triangles Anyone? If you ask someone to draw a triangle they will almost always draw something like this

or this / / ~ THE MATHEMATICAL INTELL1GENCER VOL. 14, NO. 2, 1992

69

70

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

moving-stick argument again, as I was interested in trying to convey to outsiders, children included, the sort of thing that goes on in mathematics, and I observed that obviously if you take the stick around the triangle a second time you will end up pointing west again, so I asked myself, and I now ask you, is the stick then in exactly its starting position or has it perhaps been shifted to the right or left depending on the shape of the triangle? If you want to think about this you'd better stop reading because I'm about to give the answer. The stick is in its original position. Why? Well, the first trip around the triangle reversed the stick's orientation, and an orientation-reversing mapping has a fixed point. But the second trip was exactly like the first, so it must have the same fixed point and therefore there is no shift. To continue, just today as I started writing this up, I said to myself, o.k., there is a point on the moving stick which ends up back at its starting point. Which point is it? Let's make this a multiplechoice question. The fixed point is, (a) the midpoint of the base, (b) the foot of the altitude, (c) the intersection of the base with the bisector of the opposite angle, (d) none of the above. I leave the answer to you with the following remark: this really is a quickie. Getting back to the children, the moving-stick argument can of course be applied to other polygons. Applying it to the quadrilateral gives precisely the result needed for the boomerang problem above. Of course, now it is not simply a question of whether or not the stick is reversed after its tour of the polygon but also how many times it turned, and this provides a nice intuitive introduction to the very basic notion of winding number. The fixed-point argument, which we gave for the triangle, works in fact for all odd-gons and fails in general for even-gons. In another direction, once you have Proposition 32 and its Corollary that an exterior angle of a triangle is the sum of the opposite interior angles, you can bring in circles and prove, for example, that the inscribed angIe is half of the central angle (this also uses the fact that isosceles triangles have equal base angles (Euclid Proposition 5), but I think most children would accept this as obvious1). If you've forgotten how the proof goes, the pictures below should jog your memory.

i Special Case

General Case

Can average ten-year-olds be expected to follow all this? Perhaps not, but we won't know until we try. And how will we know if they have really understood? One way is to ask them to do a similar problem on their own, for example, what is the relation between angle A and arcs a and b?

(There's no need to frighten the kids by using the customary Greek letters. I remember m y own terror the first time I encountered a ~.) A sequence of hints may be useful here. First, if they have difficulty, tell them what the answer is and ask them to prove it; if that doesn't work, tell them they must draw one more line; then tell them which line to draw, etc. For the people who work it out, the next challenge might be this one:

and so on. With all the current concern about the "'innumeracy'" (dreadful expression!) of school children in the United States, perhaps a modest dose of triangles would be helpful in the enterprise of turning out students who are more "numerate." Actually, one of the nicest aspects of this project is that it has nothing at all to do with numbers.

i Of course w e g r o w n - u p s k n o w that even "obvious" propositions have to be p r o v e d , but surely the concept of rigor has no place in the 5th grade. In fact, the only reason for rigor at any Ievel is to make sure we d o n ' t make mistakes. There is n o t h i n g sacred about rigor for its o w n sake. It was the failure to recognize this fact w h i c h was the blunder that lead to the demise of the n e w math. THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992 71

Jet Wimp*

The Emperor's N e w Mind: Concerning Computers, Minds and the Laws of Physics by Roger Penrose New York: Oxford University Press, 1989 xiv + 466 pp. US$24.95 paperback edition Penguin, 1991, US$12.95

Visions of Symmetry: Notebooks, Periodic Drawings, and Related Work of M. C. Escher by Doris Schattschneider New York: Freeman, 1990 xiv + 354 pp. US$39.95

Reviewed by Marjorie Senechal

theme of his book and local-global problems in aperiodic tiling theory. This prompted me to try to discuss both books in a single essay. It is unfair to both authors since each book is much richer than I will even begin to indicate. But on the other hand--9 The reviews of the central argument of Penrose's book already amount to an entire body of literahare; indeed, they are worthy of a review themselves, since they constitute a learned (sometimes not so learned) debate on the strengths and weaknesses of Penrose's attack on "strong AI." However, none of the reviewers seems to have been struck by Penrose's interesting suggestion that there may be analogies between our thought processes and quasicrystal growth; my aim here is to highlight these remarks.

"'How did he do it? The work of M. C. Escher (Figure 1) provokes that irrepressible question," writes Doris Schattschneider in her preface to the beautifully illustrated and encyclopedic Visions of Symmetry: Notebooks, Periodic Drawings, and Related Work of M. C. Escher. How did he do it? Everyone who has studied the Penrose filings, in any of their guises (Figure 2 and Figure 6), eventually asks this question. And w h y does it seem to be so difficult to establish a theory of aperiodic files? How do they do it ? Seven years after their discovery, solid state scientists all over the world are still trying to understand h o w and w h y atoms organize themselves into crystalline-like alloys with aperiodic atomic struchares known as quasicrystals. These three questions may or may not be related to a fourth: How do we do it? That is, how do we think? This is the central question of Penrose's recent book, The Emperor's New Mind. A deep question underlying all these questions is the classic problem of understanding the relation between local configurations and global structure. Escher's work has been used for many years by crystaUographers to illustrate just this relation for periodic patterns. In several very thought-provoking passages, Penrose discusses a possible analogy between the * Column Editor's address: Department of Mathematics, Drexel Figure 1. From the notebooks of M. C. Escher (Visions of University, Philadelphia, PA 19104USA. Symmetry). 72

THE MATHEMATICAL INTELLIGENCERVOL. 14, NO. 2 9 1992 Springer Verlag New York

Schattschneider's book is also being reviewed elsewhere; in any case, you should look at it instead of reading about it. No review can begin to c o n v e y its f a s c i n a t i n g v i s u a l c o n t e n t . Schattschneider's discussion of Escher's classification system is invaluable, but his ideas become comprehensible only by examining the 150 notebook drawings themselves. (The publisher should be thanked for reproducing all of the drawings in beautiful color, and for keeping the price of the book within reasonable bounds.) Tilings are often compared to jigsaw puzzles. Like the pieces in a puzzle, tiles must be fitted together to fill a given region or space without gaps or overlaps. But jigsaw puzzles are mathematically trivial, while things decidedly are not. The puzzle maker starts with a global solution--a picture--and then cuts it up into shapes in any way she likes. Usually, the shapes are fairly complicated but no two are alike. Thus the puzzle solver, who works locally by matching the outlines and colors of the shapes, cannot make a mistake. Sooner or later the picture is completely reassembled. How does one create a tiling? Any resemblance to jigsaw puzzle-making is superficial: things are to jigsaw puzzles as sonnets are to free verse. There are three principal methods that may be used in combination. In Method A, you start with a simple thing, such Figure 2. Three versions of Penrose's aperiodic tiles (The as the tiling of the plane by squares or hexagons, and Emperor's New Mind). then modify it by altering their boundaries (Figure 3),

Figure 3. Method A: modifying simple filings. From the notebooks of M. C. Escher (Visions of Symmetry). THE M A T H E M A T I C A L [NTELLIGENCER VOL. 14, NO. 2, 1992 73

Figure 4. Method B: trial and error. From Johann Kepler's Harmonice MuncH.

or by dissecting the tiles and regrouping the pieces into new shapes. The mathematical challenge is to do this in such a way that the modified tiles are copies of one or two prototiles. In Method B, you begin with a few prototiles and try to fit copies of them together around a point. If this can be done, then you try to extend the pattern to the entire plane (Figure 4). Method C can only be used if your prototiles can be dissected into smaller copies of themselves. After dissection, you inflate the small tiles to the sizes of the original ones, and dissect again. Continuing ad infinitum, you get a tiling of the plane. Escher's notebooks confirm what we already knew from earlier studies of his work: Escher was a master of Method A. All, or almost all, of his tilings are modifications of simple periodic tilings by polygons. Consequently they all have "'crystallographic" symmetry, that is, rotational symmetries of order two, three, four, or six. Escher's interest in "regular division of the 74

THE MATHEMATICAL [NTELLIGENCER VOL. 14, NO. 2, 1992

plane" was first stimulated by Moorish ornament at the Alhambra palace. After reading a paper by P61ya in which the seventeen plane crystallographic groups were enumerated and illustrated, he began to develop his own pattern theory. He did not use group theory; in any case, group theory provides only a coarse classification because it ignores most of the geometrical and combinatorial relations among the tiles. (See [3] for a detailed discussion of various classification schemes.) In the course of his work, Escher also developed rules for coloring patterns symmetrically and for effecting transitions between classes (Figure 5). Later, guided by diagrams of Coxeter, he created several tilings of the hyperbolic plane, and adapting a puzzle of Penrose, made one tiling with congruent but symmetrically inequivalent tiles. However, despite the enthusiasm of many mathematicians for Escher's art, only his work on color symmetry seems to have prodded us to expand our own theories.

Figure 5. Transitions among tilings. From the notebooks of M. C. Escher (Visions of Symmetry).

Figure 6. Penrose's first tiling. From The Emperor's New

Mind.

Schattschneider argues that Escher's viewpoint was that restrict the ways in which the pentagons and the local: "The crystallographers' and mathematicians' gap tiles can be juxtaposed or matched. He then incorquest is for a logical analysis of a given structure; porated the rules into the tiles themselves by modifyEscher's quest was to discover the various ways in ing their boundaries (Figure 2a). Finally, by applying which to create original periodic patterns in the plane. Method A to his six tiles, Penrose reduced the number They always begin with a pattern; he always began of tiles to two, in two different ways: kites and darts with a blank sheet of paper. Their point of view is a (Figure 2b), and thick and thin rhombs (Figure 2c). All global one--what is the structure of the whole molec- Penrose tilings reflect their pentagonal origins: they all ular array and what are the symmetries of the whole have five-fold rotational symmetry over arbitrarily pattern. Escher's view was a local o n e - - h o w can a sin- large regions. gle motif be surrounded by copies of itself?" But as we One of the most fascinating questions in tiling thehave seen, the piece of paper was not entirely blank ory is: what is the relation between Methods A, B, and because Escher created his motifs by modifying simple C? Robert Ammann, whose aperiodic tiles are distilings in ingenious ways. Method A is only quasilocal. cussed in detail in [3], says he began his investigations Method B---trial and error--is really local. If Escher by studying intersection patterns of superimposed ever used it in its pure form, he must have abandoned grids (families of parallel lines). Independently, N. G. it by the time he began his notebooks. Trial and error deBruijn showed, in 1981, that Penrose's tilings by is not a recommended method for discovering tilings, since it is known that no algorithm exists for determining whether or not an arbitrary shape will tile the plane. The nonexistence of such an algorithm implies, and is implied by, the existence of aperiodic tiles (tiles which fill the plane only nonperiodically). On the other hand, if we want to create a genuinely new tiling we may need to use Method B. Kepler's "notebook"--that is, his drawings in Harmonice Mundi--show that he did use trial and error and began to push beyond the boundaries of periodicity (see Aa of Figure 4). Penrose's discovery of his nonperiodic tilings began with the observation that a regular pentagon can be dissected into six regular pentagons and five triangles. Also, w h e n the pentagons are again divided, only a few more gap shapes appear and thus the gaps can be regarded as tiles (Figure 6). Iteration of the subdivision leads to a tiling of the plane via Method C. Penrose then showed that his tiling could be reconstructed by Figure 7. A tiling with local seven-fold rotational symmejuxtaposing regular pentagons edge-to-edge, as Kepler try. No matching rules are known. Drawing courtesy of A. did in constructing his Aa. To do this, he devised rules Katz. THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992 7 5

rhombs are the topological duals of grid intersection patterns [1]. Consequently, we can construct nontrivial nonperiodic tilings with a small number of rhombic prototiles which have, locally, seven-fold, twelve-fold, or any other desired rotational symmetry (Figure 7). These tilings are completely determined by the orientation and relative positions of the grids. Could we reconstruct them by Method B, starting with loose tiles and fitting them together? Since any rhombus (indeed, any quadrilateral) can tile the plane periodically, we would need some sort of rules to preclude periodicity. Whether or not such rules exist and what forms they can take is a major unsolved problem. So is the relation between matching rules and hierarchical structures. As far as I am aware, all of the nonperiodic filings with matching rules also have hierarchical structures since the matching rules force us to group the tiles into larger tiles, similar to the original ones, over and over again. In other words, the tiling could also have been produced by Method C. It is striking and perhaps significant that the plane filings for which both matching rules and hierarchical structures are known to exist have precisely the same local rotational symmetries as the quasicrystals that have been found so far: eight-fold, ten-fold (including fivefold here), and twelve-fold. No matching rules are known for the tiling of Figure 7, and no quasicrystal with that symmetry has been discovered either. The art historian E. H. Gombrich has written, "aesthetic delight lies somewhere between boredom and confusion" [2]. Escher's tilings are delightful to look at because they are both boring and confusing. The shapes are so surprising that at first one is confused. It does not seem possible that such wiggly creatures can tile. But if you cut out copies of an Escher tile, and play the jigsaw game of reassembling them, you will find that there is usually only one way to put them together, and you will quickly become bored by the tiling's periodicity. Penrose's tilings, on the other hand, are aesthetically delightful in the opposite way: the shapes are not themselves exciting but matching them is fascinating and instructive. At each stage there are choices to be made, even within the constraints imposed by the matching rules. You are unlikely to construct the same tiling twice. The choices imply an uncountable infinity of Penrose tilings. (Penrose has lamented the fact that Escher died shortly before Penrose discovered his tiles; he is sure that Escher could and would have applied Method A to create some startling realizations of his simple shapes. But what would have happened to the delicate balance between boredom and confusion?) One of the most interesting features of the Penrose matching rules is not their power, but their weakness. If you have ever tried to assemble them, you have probably found it difficult to avoid creating regions that cannot be tiled according to the rules. Indeed, Con76

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

way has shown [3] that there are 61 different kinds of "essential holes," for which there is no remedy except to remove some of the tiles you have already placed, and try again. The holes raise the question of whether Penrose's rules can be improved by imposing additional conditions. Interest in this problem has been stimulated by the apparently parallel problem of understanding how quasicrystals grow. Early specimens were riddled with defects, suggesting that defects might be a necessary feature of quasicrystal structure. But more recently, quasicrystals have been created that are almost defectfree. Evidently, the atoms "know" how to assemble themselves. Can we discover how they do it and mimic the process with tiling rules? A few years ago a group of physicists proposed an additional "local" rule which, w h e n added to Penrose's, eliminates the defect problem. Before adding any new tiles, you must search the entire boundary of the configuration for unfilled positions which are forced by the existing configuration. After filling these positions, you can place the next unforced tile as you like (consistent, of course, with Penrose's rules). This procedure works, but is it local? As the configuration grows, so does the region that must be searched. Can a rule be called local if the range to which it must be applied increases without bound? Penrose has shown elsewhere [5] that rules which apply only in a uniformly bounded region cannot preclude defects, because defects can be created at any level of the hierarchy. Thus, they cannot be avoided by the application of truly local rules. Then how do the atoms do it? Penrose suspects that, in contrast with the classical model of crystal growth, quasicrystal growth is nonlocal. Recognizing that the puzzle of quasicrystal growth still appears to be far from being resolved (indeed, the statistical mechanics of ordinary crystal growth is not well understood), he writes, "Nevertheless, one may speculate; and I shall venture my own opinion. First, I believe that some of these quasicrystalline substances are indeed highly organized, and their atomic arrangements are rather close in structure to the tiling patterns that I have been considering. Second, I am of the (more tentative) opinion that this implies t h a t . . , there must be a non-local essentially quantum-mechanical ingredient to their assembly." How does it work? "Many alternative arrangements must coexist in complex linear superposition. A few of these superposed alternatives will grow to very much bigger conglomerations and, at a certain p o i n t . . , one of the alternative arrangements--or, more likely, still a superposition, but a somewhat reduced superposition--will become singled out as the 'actual' arrangement . . . . we have a global problem to solve. It must be a cooperative effort among a large number of atoms all at once." Notice that the global solution eventually

arrived at is not selected a priori at the beginning of growth, but it emerges during the growth process itself. It is not simply the concatenation of independent local decisions, but the result of a sequence of collective reconfigurings by the atoms of the growing crystallite. Is it possible that these decisions are made along a hierarchical chain of command? Whether or not Penrose's arguments turn out to be correct, they are thought-provoking. What are matching rules, anyway? What do we want them to do, and how can they be formulated? Perhaps the search for local, infallible matching rules is too narrowly construed. In fact, more general formulations are being explored (see, for example, [4]). And what does this have to do with the physics of the mind? To quote Penrose once more, "Whichever atomic arrangements finally get resolved (or reduced) as the actuality of the quasicrystal involve the solution of an energy-minimizing problem. In a similar way, so I am speculating, the actual thought that surfaces in the brain is again the solution of some problem, but now not just an energy-minimizing problem. It would generally involve a goal of a much more complicated nature, involving desires and intentions that themsel'ves are related to the computational aspects and capabilities of the brain. I am speculating that the action of conscious thinking is very much tied up with the resolving out of alternatives that were previously in linear superposition." We are still far from a reasonable theory of aperiodic tiles, far from a reasonable theory of quasicrystal growth, and farther still from a reasonable theory of how we think. Still, aperiodic tiles do exist, quasicrystals do exist, and (arguably) we do think. Penrose has given us a lot to think about. In particular, we might pay more attention to transitions between, and hierarchies among, structures. Perhaps we still have things to learn from Escher's notebooks.

References 1. Bruijn, N. G. de, "Algebraic theory of Penrose's nonperiodic filings of the plane, I, II," Nederl. Akad. Wetensch. Indag. Math. 43 (1981) 39-52, 53-66. 2. Gombrich, E. H., The Sense of Order, Ithaca: Comell University Press (1979). 3. Gr/imbaum, B. and Shephard, G. S., Tilings and Patterns, New York: W. H. Freeman, 1987 (the 1989 paperback edition does not include all of the material relevant to this review). 4. Levitov, L. S., "Local rules for quasicrystals," Communications in Mathematical Physics 119 (1988) 627-666. 5. Penrose, R., "Tilings and quasicrystals: a nonlocal growth problem?" in Introduction to the Mathematics of Quasicrystals, edited by M. Jaric, San Diego: Academic Press (1989). Department of Mathematics Smith College Northampton, MA 01063 USA

Mathematical Visions: The Pursuit of G e o m e t r y in Victorian England by Joan Richards San Diego: Academic Press, 1988 266 pp. US$24.95 Reviewed by Thomas Drucker Joan Richards's Mathematical Visions: The Pursuit of Geometry in Victorian England makes enjoyable reading as it chronicles the history of the usefulness of mathematics in a certain society. It also raises questions, if only because of its success, about the usefulness of the history of mathematics. When the history of mathematics is badly done, it is a waste of time to look for ways to justify it as a practice. It is more challenging to ask what the benefits of history of mathematics as a discipline are when it is done well. The history of usefulness and the usefulness of history can be used to cast light on one another. Mathematicians can study the lessons of history, and bask in a sense of the usefulness of their discipline. Instances abound of mathematics done for the sake of beauty and having unexpected applications to other branches of mathematics and science. The contributions of number theory to cryptography and of non-euclidean geometry to the study of astronomy do not prove that everything has an application outside itself, but do indicate the difficulty of dismissing work in any field as inapplicable. Much greater than the time devoted to doing mathematics, however, is the time devoted to teaching it in schools at various levels, with the assumption that most of those engaged in learning will not go on to become professional mathematicians. There are two general arguments for the vast amount of time devoted to the subject: mathematics serves to train the mind, regardless of ultimate career; and the tools of mathematics are skills that are relevant to specific tasks outside the scholastic routine. Both of these arguments are set in the context of the Victorian age in Richards's book. The contrast with chess is instructive (although not a subject discussed by the Victorians). Chess has its grandmasters, the equivalent of professional mathematicians. The mental discipline afforded by the study of chess resembles that inculcated by mathematics. Where chess falls short is in the applicability of its tools to problems outside the game. As Borel once noted, without the element of applicability it would be hard to justify the universal preference for mathematics over chess in the schools. If one asks about the usefulness of the history of mathematics, one group of clients that has had a good deal to say has been the mathematical community. There is no single use to which the history of their discipline has been put by mathematicians. In their role as practitioners of mathematics, they build on both the human beings, and the mathematics of the past. THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992 7 7

As far as personalities are concerned, a good deal of the history of mathematics as used by mathematicians sounds like an Imitation of Newton. The trials and difficulties encountered by those who have left the most lasting marks on the field serve as a warning to later generations not to expect an easy victory. Even if the picturesque details of Galois's life in Eric Temple Bell's Men of Mathematics go beyond the evidence of the sources, Galois cannot be said to have pursued any royal road into mathematics.

ety-century students. This approach has received endorsement from the historical school in the analysis of mathematics presented by Imre Lakatos and Philip Kitcher, among others. At the least, it shakes the student's conviction of the immutability of mathematics. Historians of mathematics live in two worlds. Because the community of historians of mathematics is not large, members of the community spend most of their time in a setting either where the study of mathematics prevails or where the study of history dominates. After having made all the efforts to find an accommodation with mathematicians, the historians of There is always the hope of finding the right mathematics are judged by historical canons as well. Part of the value of Joan Richards's book is its ability to pair of shoulders to stand o n . say something to both communities. The task of understanding history involves seeing The same sort of biographical consolation comes the past through the eyes of its inhabitants. Just as even to those w h o do not see themselves cast in the social sciences, like anthropology, try to approach Newtonian mold. "If I have seen further it is by stand- other cultures on their terms, so the historian uses the ing on ye shoulders of Giants." Robert K. Merton's On evidence of the past to think back into the past. As the Shouldersof Giants traces the history of the aphorism proponents and opponents of relativism have obbest known in its Newtonian form. There is a sort of served, it is impossible to rid oneself of all the intellecfellowship in being part of the mathematical enterprise tual baggage of the present, but it is essential to remain in succession to Newton and Gauss and there is al- as mobile as possible under the load. ways the hope of finding the right pair of shoulders to One fundamental problem afflicting any historian is stand on. the survival of sources from the past. First, just finding Those looking at the mathematics, rather than the the sources can be an infuriatingly slow process. Then mathematicians, of the past are frequently searching there is the problem, once the surviving sources have after nuggets that may have been ignored or misun- been assembled, of ascertaining how typical they are of derstood in the subsequent development of the sub- the age that produced them. The best the historian can ject. Richard Askey practices and advocates this ap- usually do is speculate on the reasons why the survivproach, most accessibly in his contribution to the As- ing sources may not be typical and eschew dogmatism pray and Kitcher collection, History and Philosophy of as a result. Modern Mathematics (University of Minnesota Press, 1988). From this point of view, the historian's obligation is to avoid getting in the way of the mathematics It is impossible to rid oneself of all the inin texts of previous generations. This mining approach to the history of mathematics requires less historical tellectual baggage of the present, but it is essophistication from the mathematician seeking to prac- sential to remain as mobile as possible under the load. tice it. In addition to the use of history by mathematicians outside the classroom, there is some enthusiasm for history's playing a role in the classroom as well. The The practicing historian tends to be wary of drawing simplest way of introducing history is in the form of morals from the past, although popular historians (and anecdotes to spice up the tedium of a lecture or to catch the scholar writing for a general audience) are not rethe interest of the guaranteed nonmathematician. luctant to take up the slack. The best-selling history Views differ on the pedagogical effectiveness of histor- will point out the analogies between previous ages and ical seasoning, but it is easy to see that historical accu- the present. What the historical article will do, in a racy has very little to do with maintaining student in- much more painful, plodding fashion, is reconstruct terest. Stories of dubious authenticity are frequently the past on its own terms and speculate on the relathe most effective---part of the reason for the contin- tionship between people, institutions, and events, ued success of Bell's book. with echoes in later times. A more serious argument for the presence of history The era to which Richard's book is devoted offers a in the classroom is the advantage of following the his- good deal of material to the historian. She uses newstorical line of development. Harold Edwards has de- papers, periodicals, books, and manuscripts of the pevoted several books to reconstructing the work of nine- riod to describe the characters on her stage. In her teenth-century mathematicians for the sake of twenti- search for typicality, she calls up figures little remem78

THE MATHEMATICAL INTELLIGENCER VOL. 14, NO. 2, 1992

bered now, but who propounded certain ideas in their time. The reader has the feeling of being in the midst of a lively discussion on pedagogy and the status of mathematics in society. Richards traces a change in attitude, from the justification of mathematics (and geometry, in particular) in the schools on the grounds of mental discipline, to its serving the training of engineers and businessmen. The changing role of the universities in the Victorian era is seen against the changes in society. The fear of German technological superiority in the wake of the Franco-Prussian war goes far towards explaining curricular alterations. Even within the c o m m u n i t y of mathematicians one can contrast the conservatism of Cayley in his later years with the radicalism of Clifford. Perhaps more unexpected is Richards's way of finding events within mathematics that serve to explain new attitudes toward geometry and the role it should serve. Non-euclidean geometry, she argues on the basis of contemporary quotations, struck a raw nerve, and just could not obtain a fair hearing within the educational (or, indeed, the mathematical) community. What served as a sort of sugar coating for noneuclidean geometry was projective geometry in a form capable of including non-euclidean as well as euclidean geometries. The abuse that non-euclidean geometry had received dwindled into a sort of respectful admiration for the generality that projective geometry achieved. The book ends with the abandonment of the centrality of euclidean geometry and the early work of Bertrand Russell. In so complicated a story, there are some threads that were neglected. Developments in algebra by mid-century receive some attention, but later developments must also have influenced the discussion. The author mentions a number of the unsuccessful proposals for reforming Euclid, but leaves out what ultimately took his place. Even if her focus was on the change in the nature of the geometric curriculum, discussing the terminus would have rounded out the story. Albert Lewis, in a review in Historia Mathematica (August 1990), indicates a number of errors that crept into Richards's text (as well as some cautions about her interpretations). Let me just note that the name of the historian of mathematics Ivor Grattan-Guinness is consistently misspelled and that Grace Chisholm was ranked as a Wrangler at Cambridge in the days before women were admitted to degrees there. None of the other errors on this level got in the way of the text. Richards's book uses the Escher " H a n d with Reflecting Globe" both on the cover and in the text in front of the chapter on projective geometry. The imagery is applicable to the historical enterprise in general, as it seeks to piece together a world that cannot be seen directly. The historian of mathematics uses both internal factors (those of most interest to mathematicians)

M. C. Escher, "Hand with Reflecting Globe" 9 1935 M. C. Escher/Cordon Art, Baarn, Holland

and external (those more accessible to other historians) to map out the geometry of the past. The resulting picture will be a faithful reproduction of neither past nor present, but the task of putting it together is involved in making sense of both. Department of Mathematics Dickinson College Carlisle, PA 17013-2896 USA

THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2, 1992 7 9

Robin Wilson*

Polish Mathematics

In 1982 a set of four stamps was issued to commemorate the International Congress of Mathematicians in Warsaw (eventually held in 1983). This set depicted the four mathematicians Zaremba, Sierpi~ski, Janiszewski, and Banach (whose centenary occurs this year). Stanislaw Zaremba (1863-1943) was an influential applied mathematician, who m a d e major contributions to the theory of partial differential equations (both elliptic and hyperbolic), and potential theory. He was also a pioneer of the use of direct methods in the solution of certain variational problems. Born in the Ukraine and educated in St. Petersburg, he spent a number of years in Paris before becoming professor at the Jagiellonian University in Cracow. Wadaw Sierphiski (1882-1969) wrote more than 700 papers and 50 books in set theory, number theory, and point-set topology. Born in Warsaw, he received his doctorate in Cracow, and later taught and researched in Lw6w, Moscow, and Warsaw. His Outline of Set Theory was one of the first synthetic presentations of the subject, and his books on the continuum hypothesis, cardinal and ordinal numbers, and elementary number theory became classics in their fields. His tireless energy and organizational skills did much to enhance the international reputation of Polish mathematics.

Zygmunt Janiszewski (1888-1920) was a distinguished topologist. Born in Warsaw, he studied in Zurich, G6ttingen, and Paris, where his doctorate was awarded on the basis of an excellent thesis e x a m i n e d by Poincar6, Lebesgue, and Fr4chet. His pioneering work on plane topoiogy laid the ground for much future work. In 1916 he proposed the idea of a Polish School of Mathematics, concentrating particularly on topoiogy, set theory, and logic, and he founded the journal Fundamenta Mathematica. He died at the age of 31, during the great post-war influenza epidemic. Stefan Banach (1892-1945) helped to create modern functional analysis and develop the theory of topological vector spaces; the terms Banach space (a complete real or complex normed space) and Banach algebra (a normed algebra which is a Banach space) are named after him. Born in Cracow, he spent most of his working life in Lw6w. His most influential work was Th~orie des operations lin~aires, published in 1932. His health was shattered during the Nazi occupation of Lw6w, and he died of lung cancer at the age of 53.

* C o l u m n Editor's address: Faculty of M a t h e m a t i c s , T h e O p e n University, Milton Keynes, MK7 6 A A E n g l a n d

80 THE MATHEMATICALINTELLIGENCERVOL. 14, NO. 2 9 1992Springer Verlag New York