No title

II=lt~ll(.,~RII

Chandler

Davis J

Our Own Babel

4

h, h o w free w e are in proclaiming our o w n uniquei ness! Mathematics is the one science w h e r e results endure. It is the one scholarly discipline w h e r e the truth o f an assertion can b e unchallenged. Whatever the schisms, t h e y do n o t r o b us of this intellectual unity. So w e say. Our uniqueness is not all pleasant. Ours is the one scientific field w h e r e refereeing a p a p e r is most thankless. In almost any other natural or social science, the author n e e d only describe w h a t w a s done, and the referee need only inspect it to see that that w a s a reasonable thing to do. In ours, the author is s u p p o s e d to do it b e f o r e the reader's eyes; and m o r e serious, the referee is s u p p o s e d to do it again before approving the paper. Some short-cuts are possible, but s t i l l . . , try to explain to a chemist h o w very high is the ratio of referee's to author's effort in our field; try to explain to a dean h o w hard w e w o r k to earn our m e m b e r s h i p in the mathematicians' sodality, over and above the w o r k that s h o w s in our c.v.! Another concomitant of the w a y w e work, at least in the last century or so, is a certain splintering of the field. Where else do y o u find colleagues so unable to understand each other's papers? Even the anthropologists, w h o often decry each other's w r o n g approaches, at least k n o w what is being said. But with us--diagram-

O

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER-VERLAG NEW YORK

c h a s e r s don't k n o w w h a t a Lipschitz condition is, analysts don't k n o w w h a t a solvable group is, and m a n y "pure" mathematicians don't k n o w w h e t h e r it's the Schr6dinger equation or the Navier-Stokes equation that is non-linear. We are loyal to o u r fellow mathematicians, and w e are. confident (at least w h e n a n y nonm a t h e m a t i c i a n s might b e listening) that their w o r k is important, but w e s u r e wish w e k n e w why. It s e e m s that in a mere century our Edenic discourse has b e e n replaced b y a babble of m a n y tongues. There is a f a m o u s j o k e a b o u t a b o y in a cultivated Central Europ e a n family. His m o t h e r s p o k e to him in French, his father in German, a n d his n u r s e m a i d in Hungarian. The child u n d e r s t o o d t h e m all, b u t didn't say a w o r d himself until he w a s four: he thought he w a s s u p p o s e d to have his o w n language. Alas, the j o k e is true of us. E a c h of us is entitled to m a k e up a n e w private language and start speaking it. Is t h e r e salvation for us? Well, m a y b e t h e r e is. Let's see. We should really try, here and there, to create an island of c o m p r e hension in the middle of the din, a privileged s p a c e w h e r e mathematicians s p e a k to each o t h e r and are u n d e r s t o o d . It is the highest aim o f m y editorship that o n e such island shall b e - - s h a l l continue to b e - - T h e Mathematical

InteUigencer.

Letters

to

the

Editor

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

Mirror Paradoxes In Mathematical Entertainments in Mathematical Intelligencer 18, no. 3, David Gale asks why do mirrors not reverse top and bottom. But they can reverse top and bottom, as one can see when looking at the reflection of a mountain in a lake. PETER BORCHERDS School of Physics and Space Research The University of Birmingham, B15 21-iEngland e-mail: [email protected]

David Gale responds: But if a person is reflected in the lake, one will see her with her watch on her left wrist. Schr6dinge~s Time Reversal and Quantum Mechanics Robert Aebi comments in The Intelligencer (vol. 18 (1996), no. 2, 6267) on SchrSdinger's idea of 1931. It is true that this idea remained little known until the 1980s. It then got wider circulation because the mathematical relation between this idea and regular quanann mechanics was, at last, discovered [8]. This connection is built on works of S. Bernstein, R. Fortet, A. Beurling, and especially B. Jamison. It involves ideas inspired by E. Nelson [6] but adds new insights. I have called the resulting stochastic processes "Bernstein diffusions," because the famous Russian probabilist S. Bernstein was one of the very first readers of SchrSdinger and suggested many crucialproperties of these diffusions [2]. SchrSdinger's idea is at the origin of an international research program called "Euclidean quantum mechanics" which is already ten years old. The adjective "Euclidean" refers to the fact that, in Schr(idinger's considerations, the equation of motion of the (complex) quantum wave function is replaced by the corresponding heat equation (actually by two equations). In other words, SchrSdinger was

looking for an analogue of quantum mechanics and not for a probabilistic interpretation of his wave equation (that was discovered in 1966 by E. Nelson). This seems to underlie serious conceptual confusions regarding SchrSdinger's idea. For readers of The Mathematical InteUigencer really interested in the physical and mathematical implications of those ideas, and in the history of their development, I recommend two recent reviews of Euclidean quantum mechanics [4], [9]. The second one stresses especially the close relationship with Feynman"s path-integral approach to quantum mechanics. Mthough mathematically hopeless, Feymnan's strategy constitutes, indeed, an invaluable guide. From the technical point of view, Euclidean quantum mechanics involves, nowadays, ideas from stochastic analysis (notably Malliavin's stochastic calculus of variations [3]), stochastic control theory, classical mechanics [5] (because quantum theory is also a mechanics), Lie group theory [7], functional analysis [1], etc. It should be stressed that this research program on the relations between quantum physics and classical probability theory is intended to lead to new theorems in regular quantum mechanics. Such a theorem, discovered in this way, is announced in [7]. Different though it is from Aebi's considerations [10], this program might appropriately have been mentioned in his InteUigencer exposition. REFERENCES 1. S. AIbeverio, K. Yasue, J. C. Zambrini, Ann. Inst. H. Poincar6, Phys. Theorique 49 (1989), 259-308. 2. S. Bernstein, "Sur les liaisons entre les grandeurs al6atoires," Verh. des Intern. Mathematikerkongr., Band I, Zurich, 1932. 3. A. B. Cruzeiro, J. C. Zambrini, J. Funct. Anal. 96 (1991), 62-95 4. A. B. Cruzeiro, J. C. Zambrini, "Euclidean Quantum Mechanics: an Outlook," in

9 1997 SPRINGER-VERLAGNEWYORK,VOLUME19, NUMBER2, 1997

5

5. 6. 7.

8. 9.

10.

Stochastic Analysis and Applications in Physics, ed. A. J. Cardoso et al, NATO ASI Series voh 449, Kluwer, 1994; pp. 59-97. B. Djehiche, T. Kolsrud, C. R. Acad. Sci. Paris 321 (1995), S6rie I, 330-344. Quantum Fluctuations, E. Nelson, Princeton Series in Physics, 1985. M. Thieullen, J. C. Zambrini, "Probability and quantum symmetries I. The theorem of Noether in Schr6dinger's Euclidean Quantum Mechanics," Ann. Inst. H. Poincar& Phys. Th~orique, to appear. J. C. Zambrini, J. Math. Physics 27 (1986), 9, 2307-2330. J. C. Zambrini, "From quantum physics to probability theory and back," in Chaos: the Interplay belween Stochastic and Deterministic Behaviour, ed. P. Garbaczewski et al, Springer Lect. Notes in Physics, no. 457, 1995; pp. 393-431. J. C. Zambrini, Book review of Schr5dinger Diffusion Processes by R. Aebi, Birkh&user Verlag (1996), in The Mathematical Gazette, March 1997.

J. C. ZAMBRINI Grupo de Fisica Mathemb.tica Universidade de Lisboa Av. Prof. Gama Pinto, 2 1699 Lisbon Codex Portugal

In D e f e n s e of C u r t i s In H. A s l a k s e n ' s article on quaternionic d e t e r m i n a n t s (Mathematical Intelligencer 18 (1996), no. 3, 57-65), he has n x n quaternion m a t r i c e s e m b e d d e d as a s u b a l g e b r a o f 2n x 2n c o m p l e x matrices, and he n e e d s to k n o w that a c o m p l e x inverse o f a quaternion matrix is again quaternionic. F o r this he gives an a d hoc proof, observing that the s t a n d a r d b o o k b y Curtis has an err o n e o u s argument. It m a y be w o r t h pointing out t h a t t h e general proposition in Curtis is n o n e t h e l e s s true. Indeed, s u p p o s e t h a t b is an invertible e l e m e n t of a finite-dimensional (associative) a l g e b r a B. As the p o w e r s of b are linearly d e p e n d e n t , it follows that b -1 is equal to a p o l y n o m i n a l in b, and thus the inverse lies in every subalgeb r a containing b. WILLIAM C. WATERHOUSE Department of Mathematics Penn State University University Park, PA 16802

6

THE MATHEMATICALINTELLIGENCER

:)ninior

Defense of the Conceptual' Pierre Schapira The Opinion column offers mathematicians the opportunity to write about any issue of interest to the international mathematical community. Disagreement and controversy are welcome. The views and opinions expressed here, however, are exclusively those of the author, and neither the publisher nor the editor-in-chief endorses or accepts responsibility for them. An Opinion should be submitted to the editor-inchief, Chandler Davis.

t is strange to find now, at the outset of the twenty-first century, when the classic notion of reality is in constant retreat before the virtual, the imaginary, and the conceptual, that the idea of the conceptual is so ill-esteemed by the public and is given bad marks by many who claim to be in the intellectual 61ite. This return to the "concrete" is especially striking in the schools, with the transformation of mathematics curricula. Axiomatics and reasoning are practically eliminated in favor of the new beacon of pedagogy, "awareness." Youngsters no longer have to think about space of two or three dimensions starting from some axioms from which theorems follow; on the contrary, they are given a big, unordered stack of properties which lines and planes have to have (if some are immediate consequences of others, that is not mentioned), and they are only to contemplate them passively. You may be sure that the conceptual's little sister, rigor, does not come out of this adventure unscathed. One gets the impression that the equation

I

conceptual = ~litist = reactionary is widely accepted, and therefore passed on by the media. I will not take up the second of these equalities; it too seems absurd, but it is not the subject here. And yet the perception of our environment is ever less direct and less physical, it comes more and more via abstract representations, not always pictures. Take the example of warfare. After fighting unarmed, then with manual weapons (requiring contact), people turned to using projectiles. To besiege a city means to have an enemy who is 1This is a translation of an article in Le Monde for 26 April 1996, incorporating subsequent revisions by the author.

imagined and not seen, and in modern aerial combat there is a computer screen interposed. But war is not only a matter of gunpowder and lasers, and "ideological combat" is essentially conceptual combat. If the enemy's axiomatic foundations can be disturbed, as for example by surreptitiously undermining the separation of church and state in a democratic society, that is surely more devastating than a few bombs in the metro. Now mathematics is the site par exceUence of conceptual knowledge and learning--though (luckily) not all conceptual thinking is mathematical. Everyday thinking borrows more and more from mathematics, and yesterday's abstract becomes today's concrete. Statistics (especially in these days of great epidemics) enter everyday language; one reads time modulo 12 (as 11 + 3 = 2); one follows nonEuclidean geodesics in travelling by the cheapest route rather than the shortest. In a discussion, numbers or a table or a graph qualify as "concrete" arguments. And yet how long the path is to arrive at the concept of number (even positive)! New ideas, however, always seem too "abstract"--even (this always surprises lay people) to scientists. Even to mathematicians (who may even be the leaders of this rear-guard action). "Applied" mathematicians often regard their "pure" colleagues as artists (cutrate dancers) spinning theoretical constructs which are no doubt pleasing to those who understand them but are totally useless. And among these so called "pure" mathematicians much the same dichotomy reappears. Analysts are sure that the (Lebesgue) integral is concrete, and leave diagramchasing to the fanatics of (homological) algebra. Think of Siegel (a very great mathematician) saying of Grothendieck (an even greater mathe-

9 1997 SPRINGER-VERLAGNEWYORK, VOLUME 19, NUMBER2, 1997

7

matician, in my opinion) that one can't prove serious theorems by repeating "Om, Om." (A pun between the tantric "Ore" and the algebraist's "Horn.") Can it be that "abstract" means simply "new" and "concrete" means "well understood, well absorbed"?. 9 . which would make the opposition between them merely a new incarnation of the struggle between reaction and progress, conservatism and modernity. In France, Claude AllSgre, internationally renowned geophysicist who was responsible for higher education for years under President Mitterand, recently published The D e f e a t o f P l a t o (Fayard), one of the most savage broadsides against conceptual thought (or just against thought?).

8

THE MATHEMATICALINTELLIGENCER

Without great philosophical pretensions, one might suppose that the debate on "theory and practice" was a thing of the past. But behold, we are

scientific ignorance, by never opening a physics journal, could you say this could exist without the formidable machinery of mathematics. Furthermore, mathematics and physics are so intertwined today (as formerly) that one of the greatest contemporary mathematicians, E. Witten, i s . . 9a physicist9 But maybe you will answer that such physicists are really mathematicians in disguise? As you can't quite get away with challenging the necessity of conceptual tools in essential human activities, and the sciences in particular, one often hears the doctrine that we have enough theory to proceed. Mathematics (or ideas in general) are too far ahead of their potential applications. In other words, we're well enough supplied already, don't bring us new ideas, we wouldn't know what to do with them9 The doctrine of "zero inventory" in conceptual goods. If you want to make France a second-rate intellectual power, that is indeed the policy to follow. One of the roles of schools in a democracy is surely to enable the younger generation to understand the world, and that requires theoretical tools. Even short of understanding the world, just reading a good mystery or sciencefiction novel takes something in the way of theoretical tools: take the books of Dan Simmons. The tools will always look too sophisticated to the old-timers of all ages who decide the secondary school curricula, secure in their blindness. But understanding of the world by the general population (which does include the intellectual decision-makers of the era) is crucial. Without it, the door is open to all kinds of bigotry and obscurantism, and with them, tyranny.

Conceptual-- oppressive Conceptual- advanced Conceptual- not yet familiar Do we have enough concepts already? served up again the paradox of the chicken and the egg, in its version physics and/or mathematics, but now it is resolved: the mathematicians always arrive late for the action, it is the physicists who discover and the mathematicians are left to set things in order, to label the discoveries of others, maybe to slant things in the process 9 May one recall a few points to those who have spared five minutes for thought in their life? Such as, that raw experimentation without any theoretical apparatus does not exist, and conversely, theory exists and develops only through experiment. And "experiment" is not always synonymous with lab benches, telescopes, computers (or any other hardware). When Fermat stated his famous "theorem" (proved only last year)--that for n > 2 the equation z n = x n § yn has no solutions in integers--must he not have begun with experiments, taking n = 3 and trying values for x, y, z? Isn't that as concrete as interpreting a change of trajectory in a bubble chamber? Even if All~gre were right, if it were true that the mathematicians always came after the others, would it be so redundant? Could you do chemistry without the notion of group, or physics without the notion of Riemannian manifold? Only by maintaining absolute

Institut de Mathematiques Universite Case82 Paris Vl 75252 Paris Cedex 05 France e-mail: [email protected]

DNA Computing: Arrival of Biological

Mathematics

ome forth into the light of things,

"C

Let nature be your teacher."

The field usually referred to as mathematical biology is a highly interdisciplinary area that lies at the intersection of mathematics and biology. Classical illustrations include the development of stochastic processes and statistical methods to solve problems in genetics and epidemiology. As the name used to describe work in this field indicates,with "biology" the noun and "mathematical" the modifying adjective, the relationship between mathematics and biology has so far been one-way. Typically, mathematical results have emerged from or have been used to solve biological problems (see [24] for a comprehensive survey). In contrast, Leonard Adleman [1] succeeded in solving an instance of the Directed Hamiltonian Path Problem solely by manipulating DNA strings. This marks the first instance of the connection being reversed: a mathematical problem is the end toward which the tools of biology are used. To be semantically correct, instead of categorizing the research in DNA computing as belonging to mathematical biology, we should be employing the mirror-image term biological mathematics for the field born in November 1994. Despite the complexity of the technology involved, the idea behind biological mathematics is the simple observa-

(WORDSWORTH[53]) tion that the following two processes, one biological and one mathematical, are analogous: (a) the very complex structure of a living being is the result of applying simple operations (copying, splicing, etc.) to initial information encoded in a DNA sequence; Co) the resultf(w) of applying a computable function to an argument w can be obtained by applying a combination of basic simple functions to w [49]. If noticing this analogy were the only ingredient necessary to cook a computing DNA soup, we would have been playing computer games on our DNA laptops a long time ago! It took, in fact, the ripening of several factors and a renaissance mind like Adieman's, a mathematician knowledgeable in biology, to bring together these apparently independent processes. Adelman realized that not only are they similar but, thanks to the advances in molecular biology technology, one can use the biological to simulate the mathematical. More precisely, DNA strings can be used to encode information while enzymes can be employed to simulate simple computations, in a way described below. (See [29] for more detailed explanations of molecular biology terms.)

9 1997 SPRINGER-VERLAG NEW YORK VOLUME 19, NUMBER 2, 1997

9

FIGURE 1

DNA ( d e o x y r i b o n u c l e i c acid) is f o u n d in every cellular organism as the s t o r a g e m e d i u m for genetic information. It is c o m p o s e d o f units called nucleotides, distinguished by the chemical group, o r base, a t t a c h e d to them. The four b a s e s are adenine, guanine, cytosine, and thymine, abb r e v i a t e d as A, G, C, a n d T. (The n a m e s o f the b a s e s are also c o m m o n l y u s e d to refer to the n u c l e o t i d e s that contain them.) Single n u c l e o t i d e s are l i n k e d t o g e t h e r endto-end to form DNA strands. A short single-stranded polynucleotide chain, usually less than 30 n u c l e o t i d e s long, is called an oligonucleotide. The DNA s e q u e n c e h a s a polarity: a sequence o f DNA is distinct from its reverse. The two distinct ends o f a DNA sequence are k n o w n u n d e r the n a m e of the 5' end a n d the 3' end, respectively. T a k e n as pairs, the nucleotides A a n d T and the n u c l e o t i d e s C and G are said to be complementary. Two c o m p l e m e n t a r y singles t r a n d e d DNA s e q u e n c e s with o p p o s i t e p o l a r i t y will j o i n t o g e t h e r to form a d o u b l e helix in a p r o c e s s called basepairing or annealing. The reverse p r o c e s s - - a d o u b l e helix coming a p a r t to yield its two c o n s t i t u e n t single s t r a n d s - - i s called melting (Fig. 1). A single s t r a n d o f DNA can be likened to a string consisting of a c o m b i n a t i o n of four different symbols, A, G, C, T. Mathematically, this m e a n s w e have at o u r disposal a fourletter alphabet 5: = {A, G, C, T} to encode information, which is m o r e than enough, considering that an electronic comp u t e r needs only two digits, 0 and 1, for the s a m e purpose. Some of the simple operations that can be p e r f o r m e d on DNA sequences are a c c o m p l i s h e d by a n u m b e r of commercially available enzymes that execute a few basic tasks. One class of enzymes, called restriction endonucleases, will recognize a specific s h o r t sequence of DNA, k n o w n as a restriction site. Any double-stranded DNA that contains the restriction site within its sequence is cut b y the enzyme at

10

THE MATHEMATICAL INTELLIGENCER

that location (Fig. 2). A n o t h e r enzyme, called DNA liga,se, will b o n d together, or "ligate," the end of a DNA s t r a n d to a n o t h e r strand. The DNA polymerases p e r f o r m several flmctions, including replication o f DNA. The replication rea c t i o n requires a guiding DNA single strand called a template, a n d a shorter oligonucleotide called a p r i m e r , w h i c h is a n n e a l e d to it. Under t h e s e conditions, DNA p o l y m e r a s e catalyzes DNA synthesis b y successively adding n u c l e o t i d e s to one end of the primer. The p r i m e r is thus e x t e n d e d in one direction until the d e s i r e d s t r a n d that starts with t h e p r i m e r a n d is c o m p l e m e n t a r y to the template is o b t a i n e d (Fig. 3). Finally, using enzymes called exonucleases, either d o u b l e - s t r a n d e d or single-stranded DNA molecules m a y b e selectively destroyed. The e x o n u c l e a s e s chew up DNA molecules from the end in; s o m e o f t h e m w o r k on single strands, w h e r e a s others w o r k on double strands. There are o t h e r enzymes that could potentially be useful, but for o u r m o d e l s of computation t h e s e are sufficient. The p r a c t i c a l possibilities o f encoding information in a DNA s e q u e n c e and of p e r f o r m i n g simple b i o - o p e r a t i o n s w e r e u s e d in [1] to solve a s e v e n - n o d e instance o f t h e D i r e c t e d Hamiltonian P a t h Problem. A d i r e c t e d g r a p h G with d e s i g n a t e d vertices Vin a n d Vout is said to have a Hamiltonian p a t h if and only if t h e r e exists a s e q u e n c e o f c o m p a t i b l e "one-way" e d g e s el, e2, 9 9 9, ez (i.e., a p a t h ) that begins at vin, ends at Vout, a n d enters every o t h e r vert e x e x a c t l y once.

:IGURE :

:IGURE

,~

edges. Hence, the ligation reaction resulted in the formation of DNA molecules encoding random paths through the graph. To implement Step 2, the product of Step 1 was amplified by polymerase chain reaction. (See the next section and Fig. 3.) In the process, only those molecules encoding paths that began with Vm and ended with Your were amplified. For implementing Step 3, a technique called gel electrophoresis was used, which makes possible the separation of DNA strands by length (Fig. 4). The molecules are placed at the top of a wet gel, to which an electric field is applied, drawing them to the bottom. Larger molecules travel more slowly through the gel. After a period, the molecules spread out into distinct bands according to size. Step 4 was accomplished by iteratively using a process called affinity purification. This process permits single strands containing a given subsequence v (encoding a vertex of the graph) to be filtered out from a heterogeneous pool of other strands (Fig. 5). After synthesizing strands complementary to v and attaching them to magnetic beads, the heterogeneous solution is passed over the beads. Those strands containing v anneal to the complementary sequence and are retained. Strands not containing v pass through without being retained. To implement Step 5, the presence of a molecule encoding a Hamiltonlan path was checked. This was done by amplifying the result of Step 4 by polymerase chain reac-

IGURE

,

The following (nondeterministic) algorithm solves the problem: S t e p 1. Generate random paths through the graph. S t e p 2. Keep only those paths that begin with Vm and end with Vout. S t e p 3. If the graph has n vertices, then keep only those paths that enter exactly n vertices. S t e p 4. Keep only those paths that enter all of the vertices of the graph at least once. S t e p 5. If any paths remain, say YES; otherwise say NO. To implement Step 1, each vertex of the graph was encoded into a random 20-nucleotide strand (20-letter sequence) of DNA. Then, for each (oriented) edge of the graph, a DNA sequence was created consisting of the second half of the sequence encoding the source vertex and the first half of the sequence encoding the target vertex. A solution containing multiple copies of the sequences encoding edges was then mixed, under reacting conditions, with a solution containing a population of sequences complementary to the vertex-encoding strands. The complements of the vertices acted as splints ligating, that is, linking together, DNA sequences corresponding to compatible

VOLUME 19, NUMBER 2, 1997

11

:IGURE

tion and then determining the DNA sequence of the amplified molecules. A remarkable fact about Adleman's result is that not only does it give a solution to a mathematical problem but also the problem solved is a hard computational problem in the sense explained below (see [17] and [19]). Problems can be ranked in difficulty according to how long the best algorithm to solve the problem will take to execute on a single computer. Algorithms whose running time is bounded by a polynomial (respectively, exponential) function, in terms of the size of the input describing the problem, are in the "polynomial-time" class P (respectively, the "exponential-time" class EXP). A problem is called intractable if it is so hard that no polynomial-time algorithm can possibly solve it. A special class of problems, apparently intractable, including P and included in EXP, is the "nondeterministic polynomial-time" class, or NP. The following inclusions between classes of problems hold: P C NP C_ EXP C_ Universal. NP contains the problems for which no polynomial-time algorithm solving them is known but that can be solved in polynomial time by using a nondeterministic computer

12

THE MATHEMATICALINTELLIGENCER

(a computer that has the ability to pursue an unbounded number of independent computational searches in parallel). The Directed Hamiltonian Path Problem is a special kind of problem in NP known as "NP-complete." An NPcomplete problem has the property that every other problem in NP can be reduced to it in polynomial time. Thus, in a sense, NP-complete problems are the "hardest" problems in NP. The question of whether or not the NP-complete problems are intractable, mathematically formulated as "Does P equal NP?", is now considered to be one of the foremost open problems of contemporary mathematics and computer science. Because the Directed Hamiltonian Path Problem has been shown to be NP-complete, it seems likely that no efficient (i.e., polynomial-time) algorithm can be found for solving it with an electronic computer. Following [1], in [32] a potential DNA experiment was described for finding a solution to another NP-complete problem, the Satisfiability Problem. The Satisfiability Problem consists of a Boolean expression, the question being whether or not there is an assignment of truth values---true or false---to its variables, that makes the value of the whole expression true. DNA algorithms have since been proposed for expansion of symbolic determinants [31], the road coloring problem [25], matrix multiplication [36], addition [20], exascale computer algebra problems [50], and so on. In [10], a "molecular program" was given for breaking the U.S. government's Data Encryption Standard (DES). DES encrypts 64-bit messages and uses a 56-bit key. Breaking DES means that given one (plain-text, ciphertext) pair, we can fred a key which maps the plain text to the cipher text. A conventional attack on DES would need to perform an exhaustive search through all of the 256 DES keys, which, at a rate of 100,000 operations per second, would take 10,000 years. In contrast, it was estimated that DES could be broken by using molecular computation in about 4 months of laboratory work. The problems mentioned above show that molecular computation has the potential to outperform existing computers. One of the reasons is that the operations molecular biology currently provides can be used to organize massively parallel searches. It is estimated that DNA computing could yield tremendous advantages from the point of view of speed, energy efficiency, and economic information storing. For example, in Adleman's model [2] the number of operations per second could be up to approximately 1.2 • 1018. This is approximately 1,200,000 times faster than the fastest supercomputer. Whereas existing supercomputers execute 109 operations per joule, the energy efficiency of a DNA computer could be 2 • 1019 operations per joule; that is, a DNA computer could be about 101~ times more energy efficient [1]. Finally, according to [1], storing information in molecules of DNA could allow for an information density of approximately 1 bit per cubic nanometer, whereas existing storage media store information at a density of approximately 1 bit per 1012 urn3. As estimated in [6], a single DNA memory could hold more words than all the computer memories ever made.

Can DNA Compute Everything?

IGURE

The potential advantages of DNA computing versus electronic computing are clear in the case of problems like the Directed Hamiltonian Path Problem, the Satisfiability Problem, and breaking DES. On the other hand, these are only particular problems solved by means of molecular biology. They are one-time experiments to derive a solution to a particular sort of combinatorial problem. This immediately leads to two fundamental questions, posed already in [1] and [19]: (1) What kind of problems can be solved by DNA computing? (2) ls it possible, at least in principle, to design a programmable DNA computer? More precisely: (1) Is the DNA model of computation computationally complete in the sense that the action of any computable function (or, equivalently, the computation of any Turing machine) can be carried out by DNA manipulation? (2) Does there exist a universal DNA system; that is, a system that, given the encoding of a computable function as an input, can simulate the action of that function for any argument? [Here, the notion of function corresponds to the notion of a program in which an argument w is the input of the program and the value f(w) is the output of the program. The existence of a universal DNA system amounts, thus, to the existence of a DNA computer capable of nmning programs.] Opinions differ as to whether the answer to these questions has practical relevance. One can argue as in [11] that from a practical point of view, it may not be that important to simulate a Turing machine by a DNA computing device. Indeed, one should not aim to fit the DNA model into the Procrustean bed of classical models of computation, but try to completely rethink the notion of computation. However, the question of computational completeness of the class of DNA algorithms is relevant to practical efforts to design algorithms. At any time, some GSdel-minded person might come up with the announcement that a problem one had been working on was impossible in principle to solve by DNA manipulation, or that the DNA computer one had been constructing was, in fact, unattainable even in theory. The theoretical proof of existence at least dispels shadows where such threats to one's projects might be lurking. Computational completeness and tmiversality of DNAbased devices have been investigated for most of the models of DNA computation that have so far been proposed. The existing models of DNA computation are based on various combinations of a few primitive biological opera-

tions: 9 Synthesizing a desired polynomial-length strand, used in all models (Fig. 6). In standard solid-phase DNA synthesis, a desired DNA molecule is built up nucleotide by nucleotide on a support particle in sequential coupling steps. For example, the first nucleotide (monomer), say

A, is bound to a glass support. A solution containing C is poured in, and the A reacts with the C to form a twonucleotide (2-mer) chain AC. After washing the excess C solution away, one could have the C from the chain AC coupled with T to form a 3-mer chain (still attached to the surface), and so on. Mixing: pour the contents of two test tubes into a third one to achieve union [2]. Mixing can be performed by rehydrating the tube contents (if not already in solution) and then combining the fluids together into a new tube, by pouring and pumping, for example. Annealing: bond together two single-stranded complementary DNA sequences by cooling the solution, as illustrated in Fig. i. (See [11] and [51].)Annealing in vitro is also known as hybridization. Melting: break apart a double-stranded DNA into its singlestranded complementary components by heating the solution, as described in Fig. 1. (See [11] and [51].) Melting in vitro is also known under the name of denaturation. Amplifying (copying): make copies of DNA strands by using the polymerase chain reaction (PCR) as illustrated in Fig. 3. (See [2], [5], and [31].) PCR is an in vitro method that relies on DNA polymerase to quickly amplify specific DNA sequences in a solution. PCR involves a repetitive series of temperature cycles, with each cycle comprising three stages: denaturation of the guiding template DNA to separate its strands, then cooling to allow annealing to the template of the primer oligonucleotides, which are specifically designed to flank the region of DNA of interest, and, finally, extension of the primers by

VOLUME 19, NUMBER 2, 1997

13

GURI

9

9

9

9 9

14

DNA polymerase. Each cycle of the reaction doubles the number of target DNA molecules, the reaction giving, thus, an exponential growth of their number. Separating the strands by length using gel electrophoresis as used in Step 3 of Adelman's experiment and depicted in Fig. 4. Extracting those strands that contain a given pattern as a substring by using affmity purification, as used in Step 4 of Adleman's experiment and depicted in Fig. 5. Cutting DNA double strands at specific sites by using restriction enzymes as explained in Fig. 2. (See [8], [22], and [43].) Ligating: paste DNA strands with compatible sticky ends by using DNA ligases. (See [22] and [51].) Substituting: substitute, insert, or delete DNA sequences by using PCR site-specific oligonucleotide mutagenesis, as shown in Fig. 7 (see [9] and [28]). The process is a variation of PCR in which a change in the template can be induced by the process of primer modification, namely one can use a primer that is only partially complementary to a template fragment. (The modified primer should contain enough bases complementary to the template to make it anneal despite the mismatch.) After the primer is extended by the polymerase, the newly ob-

THE MATHEMATICAL INTELLIGENCER

tained strand will consist of the complement of the template in which a few oligonucleotides seem "substituted" by other, desired ones. Marking single strands by hybridization: complementary sequences are attached to the strands, malting them double-stranded. The reverse operation is u n m a r k i n g of the double strands by denaturing, that is, by detaching the complementary strands. The marked sequences will be double-stranded while the unmarked ones will be single-stranded [5], [33], [44]. Destroying the marked strands by using exonucleases [33] or by cutting all the marked strands with a restriction enzyme and removing all the intact strands by gel electrophoresis [5]. Detecting and Reading: given the contents of a tube, say "yes" if it contains at least one DNA strand, and "no" otherwise [1], [2]. PCR may be used to amplify the result and then a process called sequencing is used to actually read the solution. The basic idea of the most widely used sequencing method is to use PCR and gel electrophoresis. Assume we have a homogeneous solution, that is, a solution containing mainly copies of the strand we wish to sequence, and very few contaminants (other strands). For detection of the positions of A's in the target strand, a blocking agent is used that prevents the templates from being extended beyond A's during PCR. As a result of this modified PCR, a population of subsequences is obtained, each corresponding to a different occurrence of A in the original strand. Separating them by length using gel electrophoresis will reveal the positions where A occurs in the strand. The process can then be repeated for each of C, G, and T, to yield the sequence of the strand. Recent methods use four different fluorescent dyes, one for each base, which allows all four bases to be processed simultaneously. AS the fluorescent molecules pass a detector near the bottom of the gel, data are output directly to an electronic computer. The bio-operations listed above, and possibly others, will then be used to write "programs" which receive a tube containing DNA strands as input and return as output either "yes" or "no" or a set of tubes. A computation consists of a sequence of tubes containing DNA strands. There are pros and cons for each model (combination of operations). The ones using operations similar to Adleman's have the obvious advantage that they can already be successfully implemented in the lab. The obstacle preventing the large-scale automatization of the process is that most bio-operations are error-prone and rely on mainly manual handling of tubes. In contrast, the model introduced by Tom Head in [22] aims to be a "one-pot" computer with all the operations carried out, in principle, by enzymes. Moreover, it has the theoretical advantage of being a mathematical model with all the claims backed up by mathematical proofs. Its disadvantage is that the current state of the art in biotechnology has not yet allowed practical implementation. Before a practical DNA-based computer is constructed, our thinking will probably pass

through a wide variety of models, adopting complementary features from each: the appearance of different models at this early stage should be taken as an encouragement rather than a waste. In the remainder of the article, let us restrict our attention to the splicing s y s t e m model of DNA recombination that has been introduced in the seminal article of Head [22] as early as 1987. A formal definition of the splicing operation (a combination of cut and paste), that can be used as the sole primitive for carrying out a computation, is given in the next section. This is followed by a discussion of the proof that for the DNA model based on splicing, we can affmnatively answer both questions posed at the beginning of this section.

A Mathematical Model: Splicing Systems As a DNA strand can be likened to a string over a fourletter alphabet, a natural way to model DNA computation is within the framework of formal language theory, which deals with letters and strings of letters. Before presenting the technical background and formal definition of the splicing s y s t e m model, I briefly describe the abstraction process that leads from the actual DNA recombination (a combination of cutting by restriction enzymes and ligation by DNA ligases) to the mathematical operation of splicing. (The reader can consult [22] and [39] for details.) Consider the following two double strands of DNA: 5'CCCCCTCGACCCCC3' 3'GGGGGAGCTGGGGG5'

5'AAAAAGCGCAAAAA3' 3'TTTTTCGCGTTTTT5'

and two restriction enzymes ( T a q I a n d S c i N I ) , recogmtionsites are 5'TCGA3' 3'AGCT5'

whose

5'GCGC3' 3'CGCG5'

respectively. The effect of the enzymes on t h e t w o g i v e n DNA strands is the cutting, by each enzyme, of the strand containing its restriction site as a subsequence. As a result, four newDNA strands are produced: 5 ' C C C C C T CGACCCCC3' 3 ' G G G G G A G C TGGGGG5'

5'AAAAAG CGCAAAAA3' 3 ' T T T T T C G C GTTTTT5'

Note that the sticky end of the first strand is complementary to the sticky end of the last one; the same thing happens with the second and third strand. The DNA strands with compatible ends can now be ligated by DNA ligase, the result being 5' C C C C C T C G C A A A A A 3 ' 3' G G G G G A G C G T T T T T 5 '

5'AAAAAGCGACCCCC3' 3' T T T T T C G C T G G G G G 5 '

The above combination of cut and paste performed by enzymes is an instance of D N A recombination. Its mathematical abstraction, called the splicing operation, is defined under the following assumptions: (i)

We consider strings of symbols, rather than doublestranded structures. (Due to the complementarity AT and C-G, no loss of information occurs.)

(ii) The size of the alphabet is not restricted to four letters. (This generalization seems reasonable, as any alphabet can be encoded into a binary one.) (iii) The length of sites and the number of enzymes working together is not restricted. (This is a rather liberal supposition, but the splicing system aims to be an abstract general model of DNA computation, not necessarily confmed to today's biotechnology.) With these assumptions in mind, we are almost ready for the definition of the splicing operation and splicing system as mathematical objects. The exposition requires a few formal language notions and notations, introduced in the following. (For further formal language notions, the reader is referred to [45].) An alphabet is a finite nonempty set; its elements are called letters or symbols. X* denotes the free monoid generated by the alphabet ~ under the operation of catenation (juxtaposition). The elements of Z* are called words or strings. The empty string (the null element of Z*) is denoted by A. A language over the alphabet Z is a subset of •*. For instance, if X = {a, b}, then aaba, aabbb = a2b s are words over Z, and the following sets are languages over X: L1 ---- {)~}, L2 = {a, ba, aba, abbaa}, and Ls = {aP I p prime}. Since languages are sets, we may define the set-theoretic operations of union, intersection, difference, and complement in the usual fashion. The catenation of languages L1 and L2, denoted L1L2, is defined by L1L2 = {uv I u E L1, v E L2}. A finite language can always be defined by listing all of its words. Such a procedure is not possible for infinite languages; therefore, other devices for the representation of infmite languages have been developed. One of them is to introduce a generative device and defme the language as consisting of all the words generated by the device. A generative g r a m m a r is an ordered quadruple V = (N, T , S , P ) , where N and T are disjoint alphabets, S E N, and P is a finite set of ordered pairs (u, v) such that u and v are words over N U T and u contains at least one letter of N. The elements of N are called n o n t e r m i n a l s and those of T terminals; S is called the axiom. Elements (u, v) of P are called r e w r i t i n g rules or productions and are written u ---> v. If x = xlux2, y = xlvx2, and u ---> v E P, then we write x ~ y and say that x derives y in the grammar G. The reflexive and transitive closure of the derivation relation is denoted by ~*. The language generated by G is L(G) = {w E T*] S ~ * w}. Intuitively, the language generated by the grammar G is the set of words over the terminal alphabet that are derived from the axiom by repeatedly applying the rewriting rules. Grammars are classified by imposing restrictions on the forms of productions. A grammar is called type 0 if no restriction is applied to the rewriting rules, and is called regular if each rule of P is of the form A --) aB, A --> a, with A, B E N, a E T U {A}.The family of finite languages will be denoted by FIN, the family of languages generated by

VOLUME 19, NUMBER 2, 1997

15

regular grammars by REG, and the family of languages generated by type-0 grammars by 3~0. Using these formal language theory prerequisites, I can proceed now to define the s p l i c i n g o p e r a t i o n . As described in [22] and modified in [18], given an alphabet }~ and two strings x and y over ~, the splicing o f x and y according to the splicing rule r consists of two steps: (i) cut x and y at certain positions determined by the splicing rule r and (ii) paste the resulting prefLx of x with the suffLx of y, respectively, the prefLx of y with the sUffLx of X. Using the formalism introduced in [37], a s p l i c i n g rule r over ~ is a w o r d of the form al#fll$a2#fl2, where al, ill, a2, and/32 are strings over }~, and # and $ are markers not belonging to ~. We say that z and w are obtained by s p l i c i n g x and y according to the splicing rule r = al#Pl$a2#fl2, and we write (x, y) --->r (Z, W), if and only if X

----

XiOtlfllX ~ and

z

Y = Y2a2f12Y'2

w = Y2a2fllx~

for some Xl, x~, Y2, Y~ E ~*. The words atfll and a2f12 are called s i t e s of the splicing; x and y are called the t e r m s of the splicing. The splicing rule r determines both the sites and the positions of the cutting: between oL1 and fll for the fffst term and between a2 and/32 for the second. Note that the site O~lf~1 c a n occur more than once in x, and the site O~2f~2 c a n OCCur more than once in y. Whenever this happens, the sites are chosen nondeterministically. As a consequence, the result of splicing x and y can be a set containing m o r e than one pair (z, w). Let me illustrate the way splicing works by using it to simulate the addition of two positive numbers, n and m. If we consider the alphabet ~ = {a, b, c} and the splicing rule r = a#b$c#a, then the splicing of x = anb and y = ca m according to r yields the words a n+m and cb. Indeed, (anb, ca m) = (x, y ) = (a n-1 Xl

(i) M ( x ) >- 1, M ( y ) >- 1 if x r y [resp., M ( x ) >- 2 if x = y] (ii) (x, y) "->r (Z, W) according to a splicing rule r E R (iii) M ' ( x ) = M ( x ) - 1, M ' ( y ) [resp., M' (x) = M ( x ) (iv) M ' (z) = M ( z ) + 1, M' ( w ) [resp., M' (z) = M ( z ) +

b A , A c a

al fll X~

a~)-->r

Y2 a2 ~2

t Y2

Xl

0r ~2

Y2

c

b )

Y2a2 fllXl

= ( a n + m , c b ) -- ( z , w ) .

The splicing operation can be used as a basic tool for building a generative mechanism, called a s p l i c i n g s y s t e m . Given a set of strings (axioms) and a set of splicing rnles, the generated language will consist of the strings obtained as follows. Starting from the set of axioms, we iteratively use the splicing rules to splice strings from the set of axioms and/or strings obtained in the preceding splicing steps. If the classical notion of a set is used, we implicitly assume that, after splicing x and y and obtaining z and w, we can use again x or y as terms of the splicing; that is, the strings are not "consumed" by splicing. Similarly, there is no restriction on the number of copies of the newly ob-

THE MATHEMATICAL INTELLIGENCER

= M ( y ) - 1 if x r y 2 if x = y] = M(w) + 1 ifz v w 2 if z = w]

Informally, having a "set" of strings with a certain number (possibly infmite) of available copies of each string, the next "set" is produced by splicing two of the existing strings. After performing a splicing, the terms of the splicing are c o n s u m e d (their multiplicity decreases by 1), whereas the products of the splicing are added to the "set" (their multiplicity increases by 1). T h e l a n g u a g e g e n e r a t e d by a splicing system ~/is defined as L(y) = {w E T*IA ~ * M

a

(a n-l~ a a a ~ _ ~ ,

16

DEFINITION 1. A s p l i c i n g s y s t e m is a quadruple y = (•, T, A, R), where ~ is an alphabet, T C ~ is the terminal alphabet, A is a multiset over X*, and R C ~*#}~*$Z*#Z* is the set of splicing rules.

A splicing system ~, defines a binary relation ~ on the family of multisets of Z* as follows. For multisets M and M', M ~ M' holds iff there exist x, y E supp(M) and z, w E supp(M') such that

XiO~l~2Y~

=

talned z and w. More realistic is the assumption that some of the strings are only available in a limited n u m b e r of copies. In mathematical terms, this translates into using, instead of sets, the notion of m u l t i s e t s , where one keeps track o f the number of copies of a string at each moment. In the style of [14], if N is the set of natural numbers, a multiset of }~* is a mapping M : Z* ---> N U {~}, where for a w o r d w E ~*, M ( w ) represents the number of occurrences of w. Here, M ( w ) = ~ is taken to mean that there are unboundedly many copies of the string w. The set supp (M) = {w ~ X*I M ( w ) r 0} is called the s u p p o r t of M. With this modification of the notion of a set, we are n o w ready to introduce splicing systems.

and

w E supp(M)},

where A is the set of axioms and ~ * is the reflexive and transitive closure of ~ . For two families of type-0 languages, F1 and F2, denote H(F1, F2) = {L(~/)I~/= (Z, T, A, R), A E F1, R E F2}.

[The notation H(F1, F2) c o m e s from the initial of Tom Head, w h o first introduced the notion of splicing.] For example, H(FIN, REG) denotes the family of languages generated by splicing systems where the set of axioms is finite and the set of rules is a regular language. A splicing system 3, = (Z, T, A, R) with A E / ' 1 and R ~ F2 is said to be of type (F1, F2). Splicing systems have been extensively studied in the literature: the generative p o w e r of different types of splicing systems, decidability problems, variations of the main model (splicing systems with permitting/forbidding contexts, linear and circular splicing systems, splicing systems

on graphs, distributed splicing systems). For details, the reader is referred to [27] and [39] and their references. T h e E x i s t e n c e of D N A C o m p u t e r s

Having def'med a mathematical model of DNA computation, I n o w proceed to a n s w e r - - f o r this m o d e l - - t h e questions regarding the computational completeness and universality of DNA computing. I start by showing that the splicing systems are computationally complete. By computational completeness of splicing, we mean that every algorithm (effective procedure) can be carried out by a splicing system. It is obvious that this is not a mathematical definition of computational completeness. For an adequate definition, the intuitive notion of an algorithm (effective procedure) must be replaced by a formalized notion. Since 1936, the standard accepted model of universal computation has been the Turing machine introduced in [48]. The Church-Turing thesis, the prevailing paradigm in c o m p u t e r science, states that no realizable computing device can be more powerful than a Turing machine. One of the main reasons that the Church-Turing thesis is widely accepted is that very diverse alternate formalizations of the class of effective procedures have all turned out to be equivalent to the Turing machine formalization. These alternate formalizations include Markov normal algorithms, Post normal systems, type-0 grammars, and "computable" functions. Showing that the splicing systems are computationally complete amounts thus, for example, to showing that the action of any computable function can be realized by a splicing system, where the term "computable fimction" is detailed below (see [49]). Mappings of a subset of the Cartesian p o w e r set N n into N, where n -> 1 and N is the set of natural numbers, are referred to as p a r t i a l f u n c t i o n s . If the domain of such a function equals N n, then the function is t e r m e d total. Examples of total functions (for different values of n) are as follows: T h e z e r o f u n c t i o n : Z ( x o ) = 0, for all x0 @ N. T h e s u c c e s s o r f u n c t i o n : S ( x o ) = x0 + 1, for all x0 E N. T h e p r o j e c t i o n f u n c t i o n s , for all i, n, and x i E N , 0 <- i <-- n : un+li

Ix0,

Xl,

9 9 9 ,Xn)

= xi"

The class o f p a r t i a l r e c u r s i v e f u n c t i o n s can be defined as the smallest class which contains certain basic functions and is closed under certain operations. An (n + 1)-ary function f is defmed by the r e c u r s i o n s c h e m e from the functions g and h if f ( O , x l , . 9 9 , Xn) = g ( x ] , 9 9 9 , Xn), f ( k + 1, Xl, 9 9

Xn) = h C f ( k , x l , 9 9 9 Xn), k, x t , 9 9 9 Xn).

The operation of c o m p o s i t i o n associates to the functions h, go, 9 9 9 gk the f u n c t i o n f defined by f(xo, xl,.

9

Xn)

=

h(go(xo,.

9

Xn),. 9

gk(XO,...,

Xn)),

which is defined exactly for those arguments (x0, 9 9 9 Xn) for

which each ofgi, 0 -< i - k, as well as the corresponding value of h is defined. We say that f is defined by using the m i n i m i z a t i o n operation on g, if ~(Xo, . 9

Xn)

= [ (/~y)[g(y, x0,. 9 [undefined

Xn) = 0]

if there is such a y otherwise,

whose value, for a given (x0,. 9 Xn), is the smallest value of y for which g ( y , Xo, 9 9 9 x n ) = 0, and which is undefmed if no such y exists. A f u n c t i o n f i s defined p a r t i a l - r e c u r s i v e l y if (i) it is the zero function, the successor function, or a projection function, (ii) it is defined by composing functions which are defmed partial-recursively, (iii) it is defined by the recursion scheme f r o m functions which are defined partial-recursively, or (iv) it is defmed using the minimization operation on a function that is defined partial-recursively and is total. It was proved that a f u n c t i o n f i s partial recursive if and only if there is a Turing machine which computes the values of f. On the other hand, according to the Church-Turing thesis, everything that can be effectively computed by any kind of device, can be computed by a Turing machine. As a consequence, partial-recursive functions came to be k n o w n also under the name of ( e f f e c t i v e l y ) c o m p u t a b l e functions.

The formal language notion equivalent to the notion of a computable function is the notion of a type-O l a n g u a g e ; that is, a language generated by a grammar with no restriction imposed on its rewriting rules. One can prove that a language is type 0 if and only if its characteristic function is computable. By the c h a r a c t e r i s t i c f u n c t i o n of a language L C Z* we mean the function ~b of ~* such that ~b(w) = 1 if w E L, and 4) is undefmed otherwise. Recalling the notation ~0 for the family of type-0 languages, the result proving the computational completeness of splicing systems can be formulated as follows. THEOREM 1. ~0 ----H(FIN, FIN).

Informally, the theorem states that every type-0 language can be generated by a splicing system with finitely many axioms and fmitely m a n y rules. Given a type-0 grammar G generating the language L(G), the p r o o f of the inclusion ~0 C / / ( F I N , FIN) consists of two steps: (a) construct a splicing system 7 ~ H(FIN, FIN), that simulates the rewriting rules of the g r a m m a r G, and (b) prove that the constructed splicing system generates the given type0 language, i.e., show the equality L(7) = L ( G ) . The reverse inclusion can be proved directly or by involdng the ChurchTuring thesis. (The proof techniques used in Theorem 1 were suggested in [14] and first developed in [38]. The reader is referred to [16] for details.) In terms of computable functions, Theorem 1 states that the w o r k of any computable function can be carried out by a splicing system. Equivalently, Theorem 1 tells that everything that is Turing-computable can be computed also by

VOLUME 19, NUMBER 2, 1997

17

this DNA model of computation. This answers the question what kinds of algorithms (effective procedures, computable functions) can be simulated by DNA computing devices based on splicing, and the answer is: all of them. Theorem 1 shows that every program (computable function) can be simulated by a finite splicing system, but this does not say anything about the existence of a programmable DNA computer based on splicing. To this end, it is necessary to find a universal splicing system, i.e., a system with all components but one fixed, able to behave as any given splicing system ~/when a code of T is introduced in the set of axioms of the universal system. Formally, DEFINITION 2. Given an alphabet T and two families of type-0 languages, F1 and F2, a construct

Tu = (Zu, T, Au, Ru), where Zu is an alphabet, T C Zu, Au E F t , and Ru C_ Zu#Xu$Xu#Zu, Ru E F2, is said to be a universal splicing system of type (F1, F2), if for every ~/= (Z, T, A, R) of type (F~, F~), F~, F~ _ ~0, there exists a language A 7 such that Au U A~ E F t and L(T) = L(T~]), where T~ = (Zu, T,

Au U A~, Ru). Note that the type of the universal system is fixed, but the universal system is able to simulate systems of any type (F~, F~), when F~ and F~ are families of type-0 languages, that is, languages with a computable characteristic function. Based on Defmition 2 we are now in position to state the main universality result. THEOREM 2. For every given alphabet T, there exists a splicing system, with finitely many axioms and finitely many rules, that is universal for the class of systems with the terminal alphabet T.

The proof is based on Theorem 1 and on the existence of universal type-0 grammars (or, equivalently, universal Turing machines). For the details of the proof, the reader is referred to [16]. Another proof, based on the fact that a language generated by a Post system can be generated by a splicing system, can be found in [15]. The interpretation of Theorem 2 from the point of view of DNA computing is that, theoretically, there exist universal programmable DNA computers based on the splicing operation. A program consists of a single string to be added to the axiom set of the universal computer. The program has multiplicity one, while an unbounded number of the other axioms is available. The "fixed" axioms of the computer can be interpreted as the "energy" that has to be constantly supplied to the DNA computer for running the programs. The only bio-operations used in these computers are synthesis, splicing (cut/ligate), and extraction (which in mathematical terms amounts to the intersection of the result with T*, where T is the terminal alphabet). In the case of splicing systems, we can conclude that Theorem 2 provides an affirmative answer to the question of the existence of programmable DNA computers.

18

THE MATHEMATICALINTELLIGENCER

Results analogous to Theorems 1 and 2 have been obtained for several variants of the splicing systems model presented here. For example, similar results hold if the condition that the axiom set be a multiset is replaced by a control condition: a splicing rule is applicable only when certain stI%ngs, called permitting contexts, are present in the terms of splicing (see [16]). Constructions showing how to simulate the work of a Turing machine by a DNA model of computation that uses a certain combination of bio-operations have also been proposed in [2], [9], [11], [40], [42-44], [47], [51], and [52]. In an optimistic way, one can think of an analogy between these results and the work on fmding models of computation carried out in the thirties, which has laid the foundation for the design of electronic computers. Down to Earth: Implementation Techniques As expected, the transition from the ideal world of math-

ematics to the empirical world of the molecular biology. laboratory is full of challenges. Indeed, playing Pygmalion is not easy, as all scientists who attempted to blow life over their mathematical models of a DNA computer can attest. Despite the progress achieved, the main obstacles to creating a practical DNA computer still remain to be overcome. These obstacles are roughly of two types [2]: 9 Practical, arising primarily from difficulties in dealing with large-scale systems and in coping with errors; 9 Theoretical, concerning the versatility of DNA computers and their capacity to efficiently accommodate a wide variety of computational problems. This section will touch on both issues, focusing on practical implementation techniques of existing models of DNA computers. I will point out possible pitfalls in implementing each of the bio-operations enumerated in this article. None of the problems encountered seems clearly insurmountable: being aware of their existence is the first step toward overcoming them. To start from the beginning, synthesis of a DNA strand can sometimes result in the strand annealing to itself and creating a hairpin structure. Even the seemingly straightforward mixing operation can sometimes pose problems: if DNA is not handled gently, the sheer forces from pouring and mixing will fragment it. Also of concern for this operation is the amount of DNA which remains stuck to the walls of the tubes, pumps, pipette tips, and so forth and is, thus, "lost" from the computation. Hybridization has also to be carefully monitored because the thermodynamic parameters necessary for annealing to occur are sequence dependent. This is important because, depending on the conditions under which the DNA reactions occur, two oligonucleotides can hybridize without exact matching between their base-pairs. Hybridization stringency refers to the number of complementary base-pairs that have to match for DNA oligonucleotides to bond. It depends on reaction conditions (salt concentration, temperature, relative percentage of A's and T's to G's and C's, duration of the reaction) and it increases with temperature. One solution for increasing hybridization strin-

gency is the choice of good encodings for the input information of the problem [13]. Another solution proposed in [7] to avoid self-annealing and mismatches is encoding using specially chosen sequences as spacers that separate the information bits. Amplification by PCR is used with the assumption that by maintaining a surplus of primer to template, one can avoid undesired template-template interactions. As pointed out in [26], this assumption is not necessarily valid. Indeed, experimental evidence points to the possibility of the creation of complex structures like folded DNA, complexes between several strands, and incorrect ligation products. This might further affect the accuracy of using the gel electrophoresis technique for separation of strands by length. Indeed, in the presence of complex structures, the mobility of the strands will not depend only on their length, as desired, but also on the DNA conformation (shape). As a possible solution, the use of denaturing or single-stranded gels for analysis is recommended in [26]. Moreover, by keeping concentrations low, heteroduplex (double strands with mismatches) formation and template-template interactions can be minimized. Separation of strands by length and extraction of strands containing a given pattern can also be inefficient, and this might pose problems with the scale-up of the test-tube approach. An alternative methodology has been proposed in [33]: the set of oligonucleotides is initially attached to a surface (glass, silicon, gold, or beads). They are then subjected to bio-operations such as marking, unmarldng, and destruction, in order to obtain the desired solution. This method greatly reduces losses of DNA molecules that occur during extraction by affinity purification. Its drawbacks are that it relies on marking and unmarking, which, in turn, assume specificity and discrimination of single-base mismatches. Although these processes have proved reliable when using 15-mer sequences, they become more difficult for shorter or longer polynucleotide strands. Another problem is that the scale of the computation is restricted by the two-dimensional nature of the surface-based approach: one cannot reach too high an information-storing density. Extraction of those strands that contain some given pattern is not 100% efficient and can at times inadvertently retain strands that do not contain the specified sequence. Although the error rate is reasonable in case only a few extractions are needed, if the number of extractions is in the hundreds or thousands, problems arise even if 95% efficiency of extraction is assumed. Indeed, the probability of obtaining a strand encoding the solution, while at the same time obtaining no strands encoding illegal solutions, is quite low. As another possible solution, in [5] the operation remove was proposed as a replacement for extract. The compound operation remove removes from a set of strands all strings that contain at least one occurrence of a given sequence. The operation is achieved by first marking all the strands that contain the given sequence as a substring and then destroying the marked strands. The advantage of the method is that the restriction enzymes used for the remove operation have a far lower error rate than

extraction. One of the drawbacks is that, although the initial tube might contain multiple copies of each strand, after many remove operations the volume of material might be depleted below an acceptable empirical level. This difficulty can be avoided by periodic amplification by PCR. Cutting (cleavage) of a DNA strand by a restriction endonuclease is also referred to as digestion of the DNA by that enzyme. The process can sometimes produce partial digestion products. One must test all protocols for the effectiveness of the restriction enzyme used, and it is often necessary to fred means to remove undigested material. Similarly, the accuracy of ligation is high, but not perfect. A ligase might ligate the wrong molecule to a sticky end, if it bears a close resemblance to the target molecule. Detection and sequencing conventionally require enzymatic reactions and gel electrophoresis that are expensive and laborious processes. A possible solution to these drawbacks is using a technique that achieves sequencing by hybridization, offering a one-step automated process for reading the output [34]. In this method, target strands are hybridized to a complete set of oligonucleotides synthesized on a flat solid surface (e.g., an array containing all the possible 8-mers) and then the target is reconstructed from the hybridization data obtained. However, to avoid errors arising from self-annealing, a restricted genetic alphabet is recommended with this method, using only two of the four bases. In this way, the test-tube contents would be resistant to intramolecular reactions but not to intermolecular reactions. Besides the accuracy of bio-operations, another peril of the implementation of DNA computations is that the size of the problem influences the concentration of reactants, and this, in turn, has an effect on the rate of production and quality of final reaction products. In [30], an analysis of Adleman's experiment showed that an exponential loss of concentration occurs even on sparse digraphs and that this loss of concentration can become a significant consideration for problems not much larger than those solved by Adleman. For volume-decreasing DNA algorithms, an errorresistant solution seems to be the repeated application of PCR to the intermediate products [12]. However, this cannot always be the solution, as not all algorithms are volume-decreasing. Indeed, as pointed out in [21], one barrier to scalable DNA computation is the weight of DNA. In some cases [3], to achieve the desirable error rate, approximately 23 Earth masses of DNA were needed--not an acceptable design! A combination of algorithm transformations might be required to reduce the amount of DNA. Indeed, I should not go on talking only of troubles with the biotechnology used to implement the bio-operations, as if the only way to advance the DNA computing research were to wait for progress in biotechnology. I must turn to a complementary approach: improving the accuracy of DNA computing by novel programming techniques, the use of probabilistic algorithms, and other modifications of the classical mathematical problem-solving tools. The idea of algorithm transformation has already been suggested in the cases where the DNA algorithm amounts

VOLUME 19, NUMBER 2, 1997

19

to sorting a huge library of initial candidate solution complexes into those which encode a solution to a problem and those which do not. In such cases (Including Adleman's experiment), the main errors are false positives, false negatives, and strand losses. A possible solution to these types of problems is to change the algorithms by using intelligent space and time trade-offs. In [2], a basic transformation called repeating was introduced. The transformation makes use of a slowdown factor of M, proposing for a given algorithm A a new algorithm A' that has a smaller error rate than A, as follows: 9 Repeat M times: Run A on input/, producing tubes Y and N. Discard tube N and rename tube Y as t u b e / . 9 Return tube I as the "Yes" tube and an empty tube as "No." This approach is of value when the original algorithm A is known to place very reliably good sequences into the "Yes" tube (i.e., low false negatives) but also to place bad sequences often into the "Yes" tube (i.e., high false positives). A corresponding variation of the above transformation can be used if the algorithm is known to have high false negatives and low false positives. This and similar methods are used in [3] and [44]: the model employs stickers (short complementary sequences) to mark the "on" bits, whereas the unmarked bits are considered "off." The advantage of the proposed sticker model is that it does not rely on short-lived materials as enzymes and that it does not involve processes that are costly in terms of energy, such as PCR. Counter to this, one might prefer relying on PCR for solving problems, inasmuch as it has proved to be less error-prone [31]. We have so far seen that several major roadblocks have been overcome at the theoretical level of DNA computation research, suggesting that real applications of molecular computation could be feasible in the future. This section, which discusses implementation techniques and the associated error rates, indicates that many substantial engineering challenges remain at almost all stages. However, keep in mind that the issues of actively monitoring and adjusting the concentration of reactants, as well as fault tolerance, are all addressed by biological systems in nature: cells need to control the concentrations of various compounds, to arrange for rare molecules to react, and to deal with undesirable by-products of their own activity. There is no reason why these problems, which have successfully been dealt with in vivo, should not have solutions in vitro. As a step in this direction, in [30] a mechanism is suggested, based on membranes that separate volumes (vesicles) and on active systems that transport selected chemicals across membranes. Moreover, [4] and [50] suggest how familiar computer design principles for electronic computers can be exploited to build molecular computers. Having addressed the practical obstacles, let me briefly

return to the theoretical questions in the construction of a molecular computer. One of the most debated theoretical issues is whether a DNA computer will outperform and finally replace the electronic computer in all practical applications, or whether there will be only special classes of applications for which DNA computers will be preferred. DNA is an attractive medium for computation because of its potential parallelism resulting from the possibility of having up to 10 is bytes represented in a single test tube of DNA solution. Also attractive is its high information storage density of 1023 bytes per kilogram, which dwarfs the human genome, 109 bytes [50]. These features make it tempting to conjecture that a DNA computer will be faster and more efficient than an electronic one, no matter what the application. Maybe so; but the following parallel suggests that we should not expect it to be so, even in theory. In many realms of life, where the processing of large amounts of data quickly, efficiently, and in parallel is involved, humans outshine the fanciest computers. Examples of such situations are our daily social encounters of persons, when the computers inside our skulls evaluate, in a split second, data fed by our sense organs about their shape, size, color, sound, smell, posture, movement, and expression [35]. The information is then processed at lightning speed and out comes the answer: friend or stranger, to smile or not to smile, to touch or not to touch. The most mode m electromechanical robots pale in comparison, having difficulties even in processing the parallel sensory input necessary for moving in a less-thanclumsy fashion, let alone in socializing. On the other hand, when faced with the task of adding up a million 50-digit numbers, an electronic computer will outperform the human brain anytime. So perhaps we should not expect the DNA computer to replace the electronic computer. Those problems whose algorithms can be highly parallelized could possibly become the domain of DNA computers, whereas the ones whose algorithms are inherently sequential might remain the speciality of electronic computers. Indeed, the search for a "killer application"--that is, an application for which the DNA-based-solution has obvious advantages over the electronic one--is one of the main directions of research in the area. Along with it, substantial effort is being invested in testing the bio-operations for implementability, and in finally choosing a set of "primitives" that will form the basics of a molecular high-level programming language. Last, but not least, it is expected that the experimental work of probing the limits of biomolecular computation will lead to insights into the information-handling capacities of cellular organisms.

How should our ancestors be designated

"Homo sapiens" or

"Homo computans"?

20

THE MATHEMATICALINTELLIGENCER

Meta-thoughts on Biomathematics We have seen that the bio-operations are quite different from the usual arithmetical operations. Indeed, even more striking than the quantitative differences between a virtual

DNA computer and an electronic computer are the qualitative differences between the two. DNA computing is a new way of thinldng about computation altogether. Perhaps this is how nature does mathematics: not by adding and subtracting, but by cutting and pasting, by insertions and deletions. Perhaps the primitive functions we currently use for computation are just as dependent on the history of humanldnd, as counting in base 10 is dependent on our having 10 fingers. In the same way humans moved on to counting in other bases, maybe it is time to branch out by considering other ways of computing. The fact that phenomena happening inside living organisms (copying, cutting, and pasting of DNA strands) could be computations in disguise suggests that life itself may consist of a series of complex computations. As life is one of the most complex natural phenomena, we could generalize by conjectm~g the whole cosmos to consist of computations. The differences between the diverse forms of matter would then only reflect various degrees of computational complexity, with the qualitative differences pointing to huge computational speed-ups. From chaos to inorganic matter, from inorganic to organic, and from that to consciousness and mind, perhaps the entire evolution of the universe is a history of the ever-increasing complexity of computations. Of course, the above is only a hypothesis, and the enigma whether modern man is "Homo sapiens" or "Homo computans" still awaits solving. But this is what makes DNA computing so captivating. Not only could it help compute faster and more efficiently, but it stirs the imagination, it opens deeper philosophical issues, and it tantalizes with the promise of horizons yet unseen. To a mathematician, DNA computing suggests that perhaps mathematics is the foundation of all there is. Indeed, mathematics has already proven to be an intrinsic part of sciences like physics and chemistry, or music, visual arts (see [23]), and linguistics, to name just a few. The discovery of DNA computing, indicating that mathematics also lies at the root of biology, makes one wonder whether mathematics isn't, in fact, the core of all known and (with non-Euclidean geometry in mind) possible reality. Maybe indeed, Plato was right: Truth, Beauty, and Good are one and the same. Maybe, indeed [41], material things are mere instances of "ideas" that are everlasting, never born nor perishing. By intimating that--besides everything else---mathematics lies at the very heart of life, DNA computing suggests we take Plato's philosophy one step further: the eternal "ideas" reflected in the ephemeral material world could be mathematical ones. If this were the case, and the quintessence of reality is the objective world of mathematics, then we should feel privileged to be able to contemplate it. ACKNOWLEDGMENTS

This article has benefited from discussions with Leonard Adleman, Chandler Davis, Mark Gijzen, Greg Gloor, Tom Head, Jarkko Karl, Gheorghe Paun, Clive Reis, Arto Salomaa, Gabriel Thierrin, and Gary Walsh, to all of whom I wish to express my gratitude. Special thanks are due to Luiz Merkle for the graphical illustrations of molecular

processes. It would be impossible to separately point out all written sources that have influenced this article. Therefore, adopting Seneca's maxim "Whatever is well said by anyone belongs to me" [46], I want to thank all the authors in the references.

REFERENCES

1. L. Adleman, Molecular computation of solutions to combinatorial problems, Science 266 (Nov. 1994), pp. 1021-1024. 2. L. Adleman, On constructing a molecular computer, ftp://us.edu/ pub/csinfo/papers/adleman . 3. L. Adleman, P. Rothemund, S. Roweis, and E. Winfree, On applying molecular computation to the Data Encryption Standard, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 28-48. 4. J. Amenyo, Mesoscopic computer engineering: Automating DNA-based molecular computing via traditional practices of parallel computer architecture design, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 217-235. 5. M. Amos, A. Gibbons, and D. Hodgson, Error-resistant implementation of DNA computation, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 87-101. 6. E. Baum, Building an associative memory vastly larger than the brain. Science 268 (April 1995), 583-585. 7. E. Baum, DNA sequences useful for computation, Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 122-127. 8, D. Beaver, Computing with DNA, J. Computat. Biol. 2(1) (1995). 9. D. Beaver, A universal molecular computer, http://www.transarc. com/-beaver/research/alternative/molecute/molec.html. 10. D. Boneh, R. Lipton, and C. Dunworth, Breaking DES using a molecular computer, http://www.cs.princeton.edu/-dabo. 11. D. Boneh, R. Lipton, C. Dunworth, and J. Sgall, On the computational power of DNA, http://www.cs.princeton.edu/-dabo. 12. D. Boneh, C. Dunworth, J. Sgall, and R. Lipton, Making DNA computers error resistant, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 102-110. 13. R. Deaton, R. Murphy, M. Garzon, D. Franceschetti, and S. Stevens, Good encodings for DNA-based solutions to combinatorial problems, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 131-140. 14. K.L. Deninnghoff and R.W. Gatterdam, On the undecidability of splicing systems, Int. J. Computer Math. 27(1989), pp. 133-145. 15. C. Ferretti, S. Kobayashi, and T. Yokomori, DNA splicing systems and Post Systems, in First Annual Pacific Symposium on Biocomputing, 1996. 16. R. Freund, L. Kari, and G. Paun, DNA computing based on splicing: the existence of universal computers, http://www.csd.uwo. ca/-lila. 17. M. Garey and D. Johnson, Computers and Intractability. A Guide to the Theory of NP-completeness, San Francisco: W.H. Freeman and Company (1979). 18. R.W. Gatterdam, DNA and twist free splicing systems, in Words, Languages and Combinatorics II, (M. Ito and H. Jergensen, eds.), Singapore, World Scientific Publishers (1994), pp. 170-178. 19. D.K. Gifford, On the path to computation with DNA. Science 266 (Nov. 1994), pp. 993-994. 20. F. Guarnieri and C. Bancroft, Use of a horizontal chain reaction for

VOLUME 19, NUMBER 2, 1997

21

21. 22.

23. 24. 25.

26.

27. 28. 29. 30.

31.

32. 33.

34.

35. 36.

37. 38. 39. 40. 41. 42.

43.

22

DNA-based addition, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 249-259. J. Hartmanis, On the weight of computations. Bull. Eur. Assoc. Theoret. Computer Sci. 55 (1995), pp. 136-138. T. Head, Formal language theory and DNA: An analysis of the generative capacity of recombinant behaviors. Bull. Math. Biol. 49 (1987), pp. 737-759. D. Hofstadter, Gddel, Escher, Bach: An Eternal Golden Braid, New York: Basic Books (1979). F. Hoppensteadt, Getting started in mathematical biology, Notices AMS 42(9) (1995). N. Jonoska and S. Karl, A molecular computation of the road coloring problem, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 148-158. P. Kaplan, G. Cecchi, and A. Libchaber, DNA-based molecular computation: Template-template interactions in PCR, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 159-171. L. Karl, DNA computers: Tomorrow's reality. Bull. Eur. Assoc. Theoret. Computer Sci. 59 (1996), pp. 256-266. L. Karl and G. Thierrin, Contextual insertions/deletions and computability, Inform. Computat. 131, no. 1 (1996), pp. 47-61. J. Kendrew, et al. (eds.), The Encyclopedia of Molecular Biology, Oxford: Blackwell Science (1994). S. Kurtz, S. Mahaney, J. Royer, and J. Simon, Active transport in biological computing, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 111-121. T. Leete, M. Schwartz, R. Williams, D. Wood, J. Salem, and H. Rubin, Massively parallel DNA computation: Expansion of symbolic determinants, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 49-66. R. Lipton, DNA solution of hard computational problems, Science 268 (April 1995), pp. 542-545. Q. Liu, Z. Guo, A. Condon, R. Corn, M. Lagally, and L. Smith, A surface-based approach to DNA computation, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 206-216. K. Mir, A restricted genetic alphabet for DNA computing, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 128-130. D. Morris, Intimate Behavior, New York: Random House (1971). J. Oliver, Computation with DNA: Matrix multiplication, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 236-248. G. Paun, On the splicing operation, DiscreteAppl. Math. 70 (1996), pp. 57-79. G. Paun, On the power of the splicing operation, Int. J. Computer Math. 59(1995), pp. 27-35. G. Paun and A. Salomaa, DNA computing based on the splicing operation, Math. Japon. 43(3) (1996), pp. 607-632. Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996). Plato, Great Dialogues of Plato, New York: The New American Library (1956). J. Reif, Parallel molecular computation: models and simulation, in SPAA '95 (to appear); also at http://www.cs.duke.edu/-reif/ HomePage. html. P. Rothemund, A DNA and restriction enzyme implementation of

THE MATHEMATICALINTELLIGENCER

44.

45. 46. 47. 48.

49. 50.

51. 52.

53.

Turing machines, abstract at http://www.ugcs.caltech.edu/-pwkr/ oett.html. S. Rowels, E. Winfree, R. Burgoyne, N. Chelyapov, M. Goodman, P. Rothemund, and L. Adleman, A sticker based architecture for DNA computation, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 1-27. A. Salomaa, Formal Languages, New York: Academic Press (1973). L.'Seneca, Letters from a Stoic, Harmondswerth: Penguin (1969). W. Smith and A. Schweitzer, DNA computers in vitro and in vivo, NEC Technical Report 3/20/95 (1995). A.M. Turing, On computable numbers, with an application to the Entscheidungsproblem,Proc. London Math. Soc. Ser. 2, 42 (1936), pp. 230-265. A. Yasuhara, Recursive Function Theory and Logic, New York: Academic Press (1971). R. Williams and D. Wood, Exascale computer algebra problems interconnect with molecular reactions and complexity theory, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 260-268. E. Winfree, On the computational power of DNA annealing and ligation, http.'//dope.caltech.edu/winfree/DNA.html. E. Winfree, X. Yang, and N. Seeman, Universal computation via self-assembly of DNA: Some theory and experiments, in Proceedings of the 2nd DIMACS Workshop on DNA-Based Computers (1996), pp. 172-190. W. Wordsworth, The tables turned, in Wordsworth's Poems, (P. Wayne, ed.) London: Dent (1965).

The Glass

Bead Game I

0 ~

0

H

N

W

I

L

S

0

n 1943, the novelist Hermann Hesse completed the novel which represents the quintessence of his imagination and vision, and for which, three years later, he was awarded the Nobel Prize for Literature. The novel is Das Glasperlenspiel, or The Glass Bead Game. It is set some f o u r or five centuries hence in a state called Kastalien.

This state dedicates itself to the cultivation of scholarship, and the members of its ruling elite live in a quasi-monastic society and develop their minds by studying and playing the glass bead game. The twentieth century is regarded by them as an age neither culturally nor intellectually impoverished but without much idea of the role of culture; an age in which philosophy and literaWre were thought to be the greatest achievements of the era from the end of the Middle Ages. The scholars of Kastalien, on the other hand, "have for generations given the palm to mathematics and music." Mathematics and music have been linked together since the time of Pythagoras. Mathematics has been described as the science of pattern and music as the art of pattern, and the two disciplines have many common features. Both require a high degree of creative thought, and in both cases, creation is subject to rigorous constraints. For the composer, these constraints ensure that the pattern to which the listener responds have appropriate complexity and prevalence, are not obscured by incidental details, and can be related to previous musical experience. They enable creativity, and facilitate rather than preclude musical expression. In the twentieth century, composers introduced a variety of new rigorous techniques yielding score for artistic inspiration, and composers such as Berio and Schnittke demonstrated that a very tightly structured composition can accommodate remarkably diverse elements.

The fundamental test of the success of a musical composition remains, of course, its effectiveness in performance. The glass bead game is a highly developed language drawing on several disciplines, principally mathematics and music. It originated, in the middle of the 21st century, in a game played by musicians and musicologists in England and Germany to develop their memory and contrapuntal skill. One player would call out in musical notation a theme from a classical composition, and another would answer by continuing it or adding a contrasting theme, and so on. The progress of the game was recorded on a frame modelled on the abacus, with metal wires corresponding to lines of the musical stave, and coloured beads to the notes. The idea was then adopted by mathematicians; instead of notes, they used strings of mathematical symbols expressing mathematical statements. Then it was taken up by other scholarly disciplines. It was used by philologists to shed light on problems in linguistics, and within architecture to establish links between the visual arts and mathematics. The final phase in its development was the creation of a language of symbols and formulas unifying mathematics and music, and it became contemplative rather than competitive. The game might start from one, two, or three themes, for example, a theme from Bach, a mathematical statement, an astronomical configuration, or perhaps some text from the Latin Mass; parallels

9 1997 SPRINGER-VERLAG NEW YORK, VOLUME 19, NUMBER 2, 1997

23

:IGURE

and relationships would be established between concepts from different disciplines. Back in the twentieth century, the borders between different disciplines are rather sharply delineated and they are reinforced by the administrative structures of the institutions and societies dedicated to scholarship. The barriers of communication separating scientists and nonscientists are certainly no less now than they were forty years ago, when C. P. Snow identified the concept of the "two cultures." Four or five centuries seem a long time to wait for a reconciliation of ideas from different disciplines. So, being not convinced that Hesse's glass bead game is only a metaphor, I have tried to accelerate progress by playing the glass bead game. I am probably the first person to have done so, and because of my lack of experience I have used only two themes, a theme from Bach and a statement in group theory. The short piece of music above is the Order Fughetta. It sounds quite effective in performance. It makes good use of its fugal subject and is convincing Bach pastiche: apart from its brevity, there is little to betray that it was not written by Bach. What has the Order Fughetta to do with Hesse's game? The f'lrst two bars come from material in bars 1 and 3 of the fugue from Bach's famous Toccata and Fugue in D minor (BWV 565), transposed up a fifth. Now consider the mathematical statement the group has order at most six.

2'4

THE MATHEMATICALINTELLIGENCER

This can be e x p r e s s e d in various ways in the first-order language of group theory, and one of t h e s e is as follows: 3D 3C 3H 3A VG VF VE D=FVE=HVE=AVE=DVE=CV F=CVF=HVF=AVF=HV G=DVG=CVG=HVG=A. This e x p r e s s e s t h e fact that t h e r e is a n o n - e m p t y subs e t which has at m o s t f o u r elements and w h i c h h a s nontrivial intersection with every s u b s e t having t h r e e elements. There are m o r e elegant w a y s of e x p r e s s i n g this fact; t h e a b o v e choice is m a d e b e c a u s e of the m u s i c a l exigencies. The G e r m a n n o m e n c l a t u r e for notes, a c c o r d i n g to w h i c h B~ is called B a n d B is called H, w a s c o n v e n t i o n a l long before Bach u s e d BACH as a fugal subject. The symb o l s 3 and V are m a t h e m a t i c a l variants of the o r d i n a r y letters E and A, and the s y m b o l V, which to a m a t h e m a t i c i a n m e a n s "or," m e a n s to a m u s i c i a n that n o t e s a r e to be detached. The s t a t e m e n t C = D surely m e a n s that t h e notes C, D a r e to be p l a y e d simultaneously. The m u s i c o f the top t w o v o i c e s of the fughetta, up to the first n o t e s o f b a r 6, omitting the four n o t e s ringed in b a r 2, is p r e c i s e l y the s t a t e m e n t that the group h a s o r d e r at m o s t six.

VOLUME 19, NUMBER 2, 1997

25

i~vAl_p.p~|iI:_]np.l|[..~.ui~(~4a,P:li,nii[~Jil(--1

LuckyNumbers and 2187 Martin Gardner

This column is devoted to mathematics for fun. What better purpose is there for mathematics? To appear here, a theorem or problem or remark does not need to be profound (but it is allowed to be); it may not be directed only at specialists; it must attract and fascinate. We welcome, encourage, and frequently publish contributions from readers---either new notes, or replies to past columns.

Please send all submissions to the Mathematical Entertainments Editor, Alexander Shen, institute for Problems of Information Transmission, Ermolovoi 19, K-51 Moscow GSP-4, 101447 Russia; e-mail:[email protected]

2(}

Alexander

Shen,

Editor

I

When I was told that Martin Gardner had submitted an article f o r the Entertainments column, I tried to remember when I had heard his n a m e f o r the f i r s t time. I failed: it seemed that Gardner's books had always been there. I remember m y high school friends playing the game of Hex or following the evolution of Life; we learned about these games (as well as m a n y other things) f r o m Russian translations of Gardner's books. I have on m y bookshelf two editions of the R u s s i a n translation of his book "Mathematics: Magic and Mystery"; the second edition (1967) was printed in 100,000 copies; the f i f t h one (1986) in 700,000 copies. I don't know whether Gardner got a cent of royalties f r o m Soviet publishers, but the deep gratitude of millions of his Soviet readers is unquestionable. Let me thank Dr. Gardner f o r his existence--and f o r sending an article f o r this column! he house where I grew up as a child in Tulsa, Oklahoma, has an address of 2187 S. Owasso. Of course I never forgot this number. Many years ago, when I was visiting my imaginary friend Dr. Irving Joshua Matrix, the world's most famous numerologist, I asked him if there was anything remarkable about 2187. He immediately replied: "It is 3 raised to the power of 7. If you write it in base 3 notation it is 10,000,000." "I'm amazed you would know that!" I exclaimed. "Anything else unusual about 2187?" "My dear chap," Dr. Matrix responded with a heavy sigh, "every number has endless unusual properties. Exchange the last two digits of 2187 to make 2178, multiply by 4, and you get 8712, the second number backward. Take 2187 from 9999 and the result is 7812, its reversal. Multiplying 21 by 87 produces 1827, the same digits in a different order. And have you noticed that the first four digits of the constant e, 2718, and the number of cubic inches in a cubic foot, 123 = 1728, are each permutations of 2187? You might ask your readers how quickly they can insert plus or minus signs inside 2187 to make the expression add to zero." I was struggling to jot all this down on my notepad when Dr. Matrix added: "And 2187 is, of course, one of the lucky numbers." I had never heard of lucky numbers. What follows is a summary of what I

T

THE MATHEMATICALINTELLIGENCER9 1997 SPRgNGER-VERLAG NEW YORK

learned about them from Dr. Matrix, and from the references listed at the end of this article. The notion of lucky numbers originated about 1955 with Stanislaw Ulam, the great Polish mathematician who coinvented the H-bomb and was the father of cellular automata theory. It is one of the most studied types of what are called "sieve numbers." The oldest, most important sieve numbers are the primes. They are called sieve numbers because they can be generated by what is known as the Sieve of Erathosthenes. Imagine all the positive integers written in counting order. Cross out all multiples of 2, except 2. The next uncrossed-out number is 3. Cross out all multiples of 3, except 3. Continue in this way, sieving out multiples of 5, 7, 11, and so on. The numbers that remain (except for the special case of 1) are the primes. The sieving process is slow and tedious, but if continued to infinity it will identify every prime. Using a sieve for generating lucky numbers is similar. Curiously, it produces numbers closely related to primes even though they are mixtures of primes and composites (nonprimes). Here is how the procedure works. Step 1: Cross out every second number: 2, 4, 6, 8 , . . . , leaving only the odd integers.

Step 2: Note that the second uncrossed-out integer is 3. Cross out every third n u m b e r not yet eliminated: 5, 11, 17, 2 3 , . . . . Step 3: The third surviving number from the left is 7. Cross out every seventh integer not yet crossed out: 19, 3 9 , . . . . Step 4: The fourth n u m b e r from the left is 9. Cross out every ninth number not yet eliminated, starting with 27. As you continue in this fashion you will see that certain integers permanently escape getting killed. Ulam called them "lucky numbers." Figure 1 lists all the luckles less than 1,000. Eratosthenes's sieve abolished all numbers except the primes. The procedure is based on division. Ulam's sieve, on the contrary, is based entirely on a number's position in the counting series. Using Eratosthenes's sieve you have to count every integer as you go along. Using Ulam's sieve you count only the integers not previously eliminated. Although the luckles are identified by a sieving process completely different from Eratosthenes's sieve, the amazing thing is that luckies share m a n y properties with primes. The density of luckies in a given interval among the counting numbers is extremely close to the density of primes in the same interval. For example, there are 25 primes less than 100, and 23 luckles less than 100. The overall asymptotic density for each type of n u m b e r is the same! The distances between successive primes and the distances between successive luckies keep growing longer as the numbers grow in size. These distances also are almost the same for both number types. The n u m b e r of twin primes--primes that differ by 2 - is close to the n u m b e r of twin luckies. There are eight twin primes less than 100, and seven twin luckies in the same interval. Although primes play a much m o r e significant role in n u m b e r theory than luckles, the similarities suggest that m a n y of the properties of primes are less unique than previously assumed. Their properties may be more a p r o d u c t of sieving than anything else!

The most notorious unsolved problem i n v o l m g primes, now that Fermat's last Theorem has been proved, is the Goldbach conjecture. It states that every even number greater than 2 is the sum of two primes. There is a similar unsolved conjecture about luckies: that every even number is the sum o f two luckies. This has been computer tested for integers up to 100,000, and perhaps further than that, in recent years, without finding an exception. In a 1996 booklet about number problems, Charles Ashbacher, of Cedar Rapids, Iowa, conjectures that every lucky number appears at the tail of a larger lucky. For example, 7 is at the end of 37; 9 at the end of 49; 15 at the end of 615; and so so on. Lucky 87 is at the end of m y old house number 2187. Lucky 579 is at the end of lucky 96579. Ashbacher wrote a computer program that verified his conjecture for 22 of the first 100 luckles. This suggests, he writes, that his conjecture is a good bet. It is easy to determine if certain large n u m b e r s are not lucky. Consider 98765. We can quickly tell it is not lucky because it has a digital r o o t of 8. The digital root of a n u m b e r is its equivalence modulo 9 - - t h a t is, the remainder when divided by 9. If there is no remainder, the digital root is 9. A digital root is quickly obtained by adding the digits of a number, then adding again if the sum has m o r e than one digit, and continuing this w a y until just one digit remains. Lucky numbers display all digital roots except 2, 5, and 8. Why? Because all n u m b e r s with those three digital roots have the form 3k + 2 and the first two s i e m g steps eliminate them all. Dr. Matrix called my attention to the curious fact that 13, considered the

i 3 7 9 13 15 21 25 31 33 37 43 67 69 73 75 79 87 93 99 105 iii 141 151 159 163 169 171 189 193 235 237 241 259 261 267 273 283 327 331 339 349 357 361 367 385 429 433 451 463 475 477 483 487 537 541 553 559 577 579 583 591 643 645 651 655 673 679 685 693 741 745 769 777 781 787 801 805 883 885 895 897 903 925 927 931 991 993 997

most unlucky of all numbers, is the fifth lucky, the sixth prime, and the seventh Fibonacci number. A few weeks after m y meeting with Dr. Matrix I received from him a fax message listing the following identities: 2187 2187 2187 2187 2187 2187

4+ 4+ 44-

1234 = 3421 12345 = 14532 123456 = 125643 1234567 = 1236754 12345678 = 12347865 123456789 = 123458976

Note h o w the sums on the right are permutations of the numbers added to 2187. It has been proved that no polynomial formula will generate only primes, and I would guess that the same is true for the luckies. However, simple quadratic formulas will generate sequences of primes and luckles. One way to search for such formulas w a s invented by Ulam. On a square grid write the integers in a spiral fashion as shown in Figure 2, and indicate the luckies by color. Note that nine luckies clump along a diagonal. Applying the calculus of finite differences to these luckies w e discover that they are generated by 4x 2 + 2x 4- 1, as x takes the values - 3 , - 2 , - 1 , 0, 1, 2, 3, 4, 5. The spiral can start with any higher number to reveal clumps along different diagonals. Leonhard Euler found t h a t x 2 + x 4- 41 generates forty primes by letting x take values 0 through 39. If you write the integers in a spiral starting with 41, these primes will fill the entire diagonal of a 40 x 40 grid! Is there a quadratic formula equally rich, or perhaps even richer, in finding a clump of luckies? I will be interested

49 51 63 115 127 129 195 201 205 285 289 297 391 393 399 489 495 511 601 613 615 699 717 723 819 823 831 933 937 957

133 211 303 409 517 619 727 841 961

135 219 307 415 519 621 729 855 975

223 319 421 529 631 735 867 979

231 321 427 535 639 739 873 981

Figure 1. A computer printout of lucky numbers less than 1 , 0 0 0 , supplied by Charles Ashbacher. Note that '99 will be a lucky year.

VOLUME 19, NUMBER2, 1997

27

llt~O -112--113--114 - 7 ~ 6 -116-

-117--118--I19--120--121-78--79-780--81--82

!

I

!

47 - -

-

108

1

-22--23-

! I

! I

I

I

107

70

41

20

I

I

I

I

I

40

19

6 | I

106

!

i

! I

! I

105

68

39

28

I

I

I

I

,

,

103

66

- 24 --

48 -~49~-

50

I

I

25 - - 26

51

84

- - ( ~ - - 10

~7)"- 8 ,

-

2 I

5 -- 4 -

! i

102

-

35 - -

-

I

I

I

27

52

85

I

I

I

I

11 I

28 I

53 !

86 I

12

29

54

|

!

!

30

55

- 14 -

-

-

-

-

I

I 89

6 0 - - 59 ~ - 58 - - 57

I 101--100-~99~-

"

97

i

96

95 - 9 4

J

" ~

88

56

I

I I

65 - - 6 4 - - ~ 6 3 ) - - 62 - - 61 -

83

I 90

I 92~-91

Figure 2. Ulam's spiral technique for finding Quadratic lucky-rich formulas.

in hearing f r o m a n y r e a d e r w h o fmds s u c h a formula. There is a classic p r o o f b y Euclid that there is a n infinity of primes. Although it is e a s y to s h o w t h e r e is also an infinity o f l u c k y numbers, the question of w h e t h e r an infinite n u m b e r o f luckies a r e p r i m e s remains, a s far as I know, unproved. Also unsolved is w h e t h e r t h e r e is an infmity of twin luckies. Dr. Matrix e n j o y s p r a c t i c a l jokes. When w e t a l k e d a b o u t 2187 he p o i n t e d out t h a t if this n u m b e r is divided b y 9999 the quotient is .218721872187 . . . . I w a s m o m e n t a r i l y s u r p r i s e d until I realized that any i n t e g e r of n digits, n o t m a d e entirely o f nines, w h e n divided b y a n u m b e r consisting of n nines, prod u c e s a d e c i m a l f r a c t i o n in which t h e original n u m b e r is r e p e a t e d endlessly as the quotient's period. "Ulam d i s c o v e r e d l u c k y n u m b e r s with his lucky imagination," Dr. Matrix added. "Note the letters at positions 2, 1, 8, and 7 in LUCKY IMAGINATION. What do t h e y spell?" The first t h r e e l u c k y n u m b e r s are 1, 3, a n d 7. N o w 137 n o t only is a p r i m e b u t it is one of the m o s t interesting of all three-digit n u m b e r s . It is, of course, the n o t o r i o u s free-structure constant,

28

THE MATHEMATICAL

INTELLIGENCER

the m o s t m y s t e r i o u s o f all c o n s t a n t s in physics. I m e n t i o n e d this to Dr. Matrix. This p r o m p t e d him to t a l k for twenty m i n u t e s a b o u t 137. Here are s o m e highlights of w h a t he said: C h e c k the King J a m e s Bible's fn~st chapter, third verse, a n d s e v e n t h word. The w o r d is "light." Dr. Mato_x rem i n d e d m e that the fine-structure cons t a n t is intimately c o n n e c t e d with light. The reciprocal o f 137, o r 1 divided b y 137, p r o d u c e s the d e c i m a l fraction 007299270072992700 . . . . The p e r i o d is a palindrome! Partition 137 into 13 a n d 7. The thirt e e n t h letter of the a l p h a b e t is M a n d the seventh is G - - m y t w o initials! Chlorophyll, which t a k e s light from the s u n to give energy to plants, is m a d e o f exactly 137 atoms. Dr. Matrix a s k e d m e to w r i t e m y old h o u s e n u m b e r twice, 21872187, a n d p u t the n u m b e r into m y h a n d calculator. This number, he i n f o r m e d me, is e x a c t l y divisible b y 137. I p e r f o r m e d t h e division and sure enough, the reado u t d i s p l a y e d the integer 159651. I got a n even greater surprise w h e n Dr. matrix a s k e d m e to turn the c a l c u l a t o r upside down. The n u m b e r w a s the s a m e inverted!

Dr. Matrix n e x t a s k e d me to divj'de 159651 b y 73. The result w a s 2187! I later d i s c o v e r e d that this w a s a n o t h e r of Dr. Matrix's hoaxes. Any n u m b e r o f the f o r m o f ABCDABCD is evenly divisible b y 137 and 73. The r e a s o n ? ABCDABCD is the p r o d u c t o f ABCD and 10001. The two prime f a c t o r s o f 10001 a r e 137 and 73, so dividing ABCABCD b y t h o s e two n u m b e r s will naturally r e s t o r e ABCD. Of c o u r s e the quotient after the first division is n o t likely to b e invertible. "Is t h e r e any connection," I asked, "between the lucky n u m b e r s a n d 666, the f a m o u s n u m b e r of the B e a s t in New T e s t a m e n t prophecy?" Dr. Matrix p u t his fmgertips together a n d c l o s e d his e m e r a l d e y e s for a full m i n u t e before he spoke. "Consider y o u r old h o u s e n u m b e r 2187, a n d t h e fwst four luckies 1, 3, 7, 9. Omit the 1 in e a c h n u m b e r to leave 287 a n d 379. A d d the two n u m b e r s a n d you g e t 666. By the way, I f o r g o t to m e n t i o n e a r l i e r that if you divide 18, the m i d d l e digits of 2187, b y 27, the first a n d l a s t digits, the quotient is .66666666 . . . . . " I c o n c l u d e with a mind-reading t r i c k of m y o w n t h a t involves 2187. A s k s o m e o n e to p u t this n u m b e r into a calculator's display. With y o u r b a c k turned, tell him to multiply it b y a n y n u m b e r he likes without revealing this n u m b e r to you. He n e x t calls out, in any order, e a c h digit in the p r o d u c t exc e p t o n e n o n z e r o digit. You at o n c e n a m e t h e missing digit. H o w do y o u do it? As he calls o u t digits, k e e p adding t h e m in y o u r h e a d until y o u k n o w the digital r o o t o f t h e i r sum. This is easily done by casting o u t nines a s e x p l a i n e d earlier. If the digital r o o t is 9, he omitted 9. If less t h a n 9, he left o u t a digit equal to t h e difference b e t w e e n 9 and the digital root. F o r e x a m p l e , if the digital r o o t is 2, he o m i t t e d 7. I leave it to you to figure out w h y this a l w a y s w o r k s with 2187. Hint: 2187 has a digital r o o t of 9. REFERENCES

"On Certain Sequences of Integers Defined by Sieves." Vema Gardiner, R. Lazarus, Nicholas Metropolis, and Stanislaw Ulam. Mathematics Magazine, Vol. 31, 1956, pp. 117-122.

"The Lucky Number Theorem." David Hawkins and W. W. Briggs. Mathematics Magazine, Vol. 31, 1957-58, pp. 81-84, 277-280. A Collection of Mathematical Problems. Stanislaw Ulam. (Interscience, 1960), p. 120.

"Prime-like Sequences Generated by a Sieve Process." W. E. Briggs. Duke Mathematical Journal, Vol. 30, 1963, pp. 297-312. "Sieve-generated Sequences." Marvin Wunderlich. The Canadian Journal of Mathematics, Vol. 18, 1966, pp. 291-299. "A General Class of Sieve-generated Sequences." Marvin Wunderlich, Acta Arithmetica, Vol. 16, 1969, pp. 41-56. Excursions in Number Theory. C. Stanley Ogilw and John T. Anderson. (Dover, 1988), pp. 100-102. The Penguin Dictionary of Curious and Interesting Numbers. David Wells. (Penguin,

1986), pp. 13, 32-33. Unsolved Problems in Number Theory. Richard K. Guy. (Second edition, Springer-Verlag,

1994), pp. 108-109. Zero to Lazy Eight. Alexander Humez, et al. (Simon and Schuster, 1993), pp. 198-200. Collection of Problems on Smarandache Notions. Charles Ashbacher. (Erhus University

Press, 1996), pp. 51-52. 3001 Chestnut Road Hendersonville, NC 28792-1223, USA

VOLUME 19, NUMBER 2, 1997

29

Fubini Foiled: Katok's Paradoxical Example in Measure Theory

natole Katok has proved the following (unpublished): There exists a measurable set E of area one in the unit square (0, 1) x [0, 1], together with a f a m i l y of disjoint smooth real analytic curves F~ which fill out this square, so that each curve F~ intersects the set E in at most a single point. In o t h e r words, w e c a n c o n s t r u c t a set o f full two-dimensional Lebesgue m e a s u r e b y selecting at m o s t one point from e a c h F/3. The c o n s t r u c t i o n is c o m p l e t e l y explicit and natural. (The c u r v e s in question d e p e n d c o n t i n u o u s l y on the p a r a m e t e r fl E [0, 1], a n d form a t o p o l o g i c a l foliation of the square.) Note however, in any s u c h e x a m p l e , that F/3 cannot d e p e n d s m o o t h l y on the p a r a m e t e r ft. In the case of a s m o o t h l y p a r a m e t e r i z e d family, it follows easily from Fubini's T h e o r e m t h a t E m u s t intersect a l m o s t every r ~ in a set of full o n e - d i m e n s i o n a l Lebesgue m e a s u r e . ) Figure 1 s h o w s an e x a m p l e of such a family of curves, b a s e d on a c o n s t r u c t i o n similar but n o t identical I to that of Katok. To begin o u r construction, w e will n e e d B o r e r s Strong L a w o f Large Numbers. S u p p o s e t h a t w e toss a bia s e d coin, w h i c h l a n d s with the "zero" side up with probability p(0) = p a n d lands with the "one" side up with probability p(1) = 1 - p. Then, for a sequence o f n i n d e p e n d e n t coin tosses, w e o b t a i n a sequence o f n bits, w h e r e the probability of a given s e q u e n c e (bl, 9 9 9 , bn) is given by the p r o d u c t rule probability(bl,...,

bn) = p ( b l ) "" p(bn).

(1)

Jakob Bernoulli, 300 years ago, s h o w e d that the frequency

of ones, that is the ratio (bz + "'" + bn)/n, is likely to be close to p(1) if n is large. Emile Borel s h a r p e n e d this result as follows. Consider an infinite sequence of coin tosses. F o r m u l a (1) gives rise to a probability measure, called the (p(0), p(1))BernouUi product measure, on the space [0, 1}N consisting of all infmite sequences (bl, b2,. 9 .) of zeros and ones. Borel s h o w e d that the limiting frequency

lim (bz + "'" + bn)/n

n-.~oo

exists a n d is precisely equal to p(1), with p r o b a b i l i t y 1. In o t h e r words, this limit equals p ( 1 ) for all s e q u e n c e s in {0, 1}N outside of a s u b s e t o f m e a s u r e zero with r e s p e c t to the Bernoulli p r o d u c t m e a s u r e . We can restate this result using only real v a r i a b l e s (ins t e a d o f coin tosses) as follows. Let x vary over the circle R/Z, a n d let the p a r a m e t e r p v a r y over the o p e n unit interval (0, 1). F o r each p, define a p i e c e w i s e linear m a p fp of d e g r e e t w o from the circle Rfs to itself by the f o r m u l a

~

x/p fp(x) = [ ( x - p)/(1 - p)

for x C I0 (p) = [0, p) c P,JZ for x ~ Ii(p) = [p, 1) C R/Z, (2)

as p l o t t e d in Figure 2.

1Katok's example is based on a family of degree-two Blaschke products mapping the unit circle to itself. I am grateful to C. Pugh for describing it to me. A different version of the construction, based on tent maps of the interval, has been given by J. Yorke, also unpublished.

30

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER VERLAG NEW YORK

infinitely m a n y ones do not occur. C o m p a r e the R e m a r k s at t h e e n d o f this article 9 In t e r m s of this coding, n o t e t h a t f p c o r r e s p o n d s to t h e shift m a p

IGURE

TX

( b l , b2, b3, 9 9 .) ~-> (b2, b3, b4. 9 .) 9

It is n o t difficult to check t h a t the Lebesgue m e a s u r e on R/Z c o r r e s p o n d s precisely to the (p(0), p ( 1 ) ) - B e r n o u l l i p r o d u c t m e a s u r e on {0, 1}N; that is, the length of the interval consisting o f all x for w h i c h t h e a s s o c i a t e d s y m b o l sequence starts with some s p e c i f i e d finite sequence (bl, , bn) o f bits is equal to the p r o d u c t p(bl) "'" P(bn). The Strong Law o f Large N u m b e r s can n o w be r e s t a t e d as follows: Choose s o m e fixed p a r a m e t e r p and c o n s i d e r the m a p fp. For Lebesgue almost every point x E R/Z, the 9

9

9

f r e q u e n c y o f ones in the associated symbol sequence (bl, b2, b3, 9 9 .) is defined and equal to p ( 1 ) = 1 - p.

P

)

(Alternatively, w e c a n t h i n k o f f p as a d i s c o n t i n u o u s m a p from the unit interval [0, 1] to itself. The a r g u m e n t w o u l d b e the s a m e in either case.) It is e a s y to see t h a t e a c h fp is measure-preserving. In fact, for any interval J C [0, 1] of length 6(J), t h e preima g e f p l ( J ) consists of an interval in Io(p) of l e n g t h p ( 0 ) ~ ( J ) t o g e t h e r with an interval in I i ( p ) o f length p ( 1 ) ~ ( J ) , so that the total length is 6 ( f p l ( j ) ) = g ( j ) . [Here again, w e set p ( 0 ) = p a n d p ( 1 ) = 1 - p.] F o r f i x e d p , w e c a n c o d e e a c h p o i n t x E R/Z b y an infinite sequence (bl, b2, b3, 9 9 .) E {0, 1} N of bits, defined as follows. Let x = x l ~-~ x2 ~-+ x3 ~ "'"

(3)

b e the orbit o f x u n d e r f p , and set each b n equal to zero o r one according to w h e t h e r xn belongs to the interval I0(P) o r I i ( p ) m o d u l o Z. We will call (bl, b2, 9 . .) the symbol sequence a s s o c i a t e d with x and fp. (Note: Almost every s y m b o l sequence in {0, 1}N can occ u r in this construction. However, s e q u e n c e s ending with

Let E C (0, 1) • R/Z b e t h e set consisting of all p a i r s (p, x ) s u c h that the frequency o f ones, for the symbol sequence o f x u n d e r the action offp, is defined and equal to 1 - p. It is n o t difficult to c h e c k t h a t E is a m e a s d r a b l e set. F o r e a c h fixed p, let Cp d e n o t e t h e circle {p} • R/Z C (0, 1) • R/Z. Since the i n t e r s e c t i o n o f E with each Cp has o n e - d i m e n s i o n a l Lebesgue m e a s u r e 6I(E A Cp) = 1, it follows f r o m Fubini's T h e o r e m that E h a s t w o - d i m e n s i o n a l Lebesgue m e a s u r e

e2(E)

=

~t(E

N

Cp)

dp =

i.

Next, define a family of smooth curves F~ as follows9 Let fi be any number in the interval [0, l)9 Form the basetwo expansion

fl = O9

"'" (base 2) ---- Zbn/2n,

and let F~ b e the set of all pairs (p, x ) E (0, 1) • R/Z s u c h that t h e s y m b o l sequence o f x u n d e r t h e m a p f p is equal to ( b l , b2, b3, 9 9 9 Clearly the F~ are disjoint sets with u n i o n equal to (0, 1) x R/Z. To p r o v e t h a t each F~ is a s m o o t h real analytic curve, w e p r o c e e d as follows. F o r each orbit (3), it follows easily from (2) that

Xn

=

bnp(O)

+ Xn+l

p(bn)9

A s t r a i g h t f o r w a r d induction t h e n s h o w s that x = Xl is given by the s e r i e s

x=x(p, ~) = p(O)(bl + p(bl)(b2 + p(b2)(b3 + " " ) ' " ) ' " ) = p(O)(bl + b2P(bl) + b3p(bl)p(b2) + b4p(bl)p(b2)P(b3) + "").

0

I0

p

I1

(4)

S e t p ( 0 ) = p = (1 + t)/2 a n d p ( 1 ) = 1 - p = (1 - t)/2. If ItI -< c < 1, t h e n the n t h t e r m in the series (4) has a b s o l u t e value at m o s t [(1 + c)/2] n. Hence, this series converges uniformly. If fact, this is true even if w e allow c o m p l e x v a l u e s of t with It[ --< c < 1. Hence, b y t h e Weierstrass Uniform Convergence Theorem, for e a c h fixed fl the series (4) defines x as an analytic function o f t t h r o u g h o u t the interval It] < 1, or as an analytic function o f p t h r o u g h o u t the in-

VOLUME 19, NUMBER2, 1997

31

fu2(x) ----2x (rood Z); that is, there is a unique h o m e o m o r phism hp : R/Z --) 1UZ which conjugates fl/2 tofp, so that

fp =

hp o f l / 2 o hp 1.

In fact, this conjugating h o m e o m o r p h i s m is given by the formula hp(fi) = x(p, /3) and is continuous in both variables. If fl E [0, 1) has base-two expansion fl = ~ bn/2 n, note that the symbol sequence of fl under fl/2 is (bl, b2, 9 . .) and that the symbol sequence of hp(~) underfp is this same sequence (bl, b2, . . .). Details of these arguments will be left to the reader 9 BIBLIOGRAPHY

Billingsley, P. Probability and Measure, New York: John Wiley & Sons (1979) [for Fubini's Theorem and the Law of Large Numbers]. Feller, W., An Introduction to Probability Theory and its Applications, New York: John Wiley & Sons (1950, 1957) [for the Law of Large Numbers]. Rudin, W., Real and Complex Analysis, New York: McGraw-Hill (1974) [for Fubini's Theorem and Weierstrass's Theorem].

terval 0 < p < 1. Evidently, F~ is just the graph of this real analytic function p ~ x(p, fl). Finally, since a given symbol sequence can have at most one limiting frequency lim(bl + ... + bn)/n =- 1 - p, it follows that each F~ can intersect the measurable set E in at most a single point (p, x ( p , ~)). Remarks

The function fl ~-) x(p, /~) is strictly m o n o t o n e and maps the interval [0, 1) onto itself. Hence, it is a homeomorphism. In fact, it follows easily that the correspondence (p, fl) ~-> (p, x(p, fl)) maps the product space (0, 1) • R/Z homeomorphically onto itself. Here is an alternative argument. It is clear that expression (4) depends continuously on the two variables p E (0, 1) and (bl, 02, . 9 .) E {0, 1}N, where we give this space of sequences the cartesian product topology. The correspondence (51, 52, 9 9 .) ~

~ , 5n/2 n ~

[0, 1]

from symbol s e q u e n c e to real variable is n o t quite oneto-one, as every dyadic rational m/2 n has two distinct base-two expansions, ending either with infinitely m a n y zeros or with infinitely m a n y ones. However, a straightforward c o m p u t a t i o n s h o w s that these two expansions give rise to the s a m e s u m x(p, fl), and it follows easily that the c o r r e s p o n d e n c e (p, fl) ~-> x(p,/3) is indeed continuous. We can interpret these constructions dynamically as follows. It is not hard to show that each fp : R/Z ~-~ R/Z is tmiquely topologically conjugate to the angle-doubling map

3 ~)

THE MATHEMATICALINTELLIGENCER

iL'Al~'Ti~i[~i~t-;.li[~F';.t|O'a[,]~l|il|ili||[.~.Z,--'-ai M a r j o r i e

Two Communities and Vertical Integration This column is a forum for discussion of mathematical communities throughout the world, and through all time. Oar definition of "mathematical community" is the broadest. We include "schools" of mathematics, circles of correspondence, mathematical societies, student organizations, and informal communities of cardinality greater than one. What we say about the communities is just as unrestricted. We welcome contributions from mathematicians of all kinds and in all places, and also from scientists, historians, anthropologists, and others.

Please send all submissions to the Mathematical Communities Editor, Marjorie Senechal, Department of Mathematics, Smith College, Northampton, MA 01063, USA; e-mail: senechal@minkowski'smith'edu

Senechal,

Editor

The Connecticut Valley Mathematical Community The Connecticut River begins in the wilds of southern Canada, winds its way through New England and eventually merges with the Atlantic ocean at New Haven, Connecticut. In the middle of Western Massachusetts, the fertile river valley nurtures an abundant crop of educational institutions: the Five Colleges (the University of Massachusetts and Smith, Amherst, Mount Holyoke, and Hampshire Colleges) are only a few miles from its banks, and other famous institutions, including Williams College, Holy Cross College, Worcester Polytechnic Institute, and Clark University, are within easy driving distance. Over sixty years ago, when the University of Massachusetts was still known as "Mass Aggie"--it was founded in the 1860's as the Massachusetts Agricultural College--and Hampshire College was yet unborn, the local mathematicians founded the Connecticut Valley Collquium, which is still held four times a year (at Mount Holyoke in the fall, UMass and Amherst in the winter, Smith in the spring). From its early days, the CVC attracted prominent mathematicians to the area and brought the local mathematical community together: the dinners after the lectures were an integral part of the event. Today the Valley mathematical community is much too large to eat together, and besides, few of us have time for such dinners anymore. In any case, the community has splintered into many subdisciplines, each with its own seminar. But the CVC is still beloved by the older faculty for historical reasons, and it occupies a special niche in the area as the only colloquium expressly intended for a broad mathematical audience. Today research mathematics is a Valley industry, despite the fact that UMass is the only one of the five "colleges" that grants doctoral degrees.

i

The others are four-year liberal arts colleges, attended by undergraduates (and master's degree candidates, in some programs). Liberal arts colleges, with their relatively heavy teaching responsibilities, are not generally regarded as suitable homes for active researchers. But in fact many research mathematicians have taught in colleges over the decades, and today research is often part of the college teacher's job description. Here in the Valley the research community is stratflied by discipline, not by institutional affiliation. It might be otherwise were it not for Five Colleges, Inc., an organization that provides support for many joint programs and joint seminars, and is the clearing house for multi-college grants. The high-school and middle-school teachers constitute a second mathematical community in the Valley. This community too is lively, with its own professional association, MathWest, which Five Colleges, Inc. helped create and continues to encourage. But although many of the teachers have worked with college and university faculty in workshops and projects over the years, the community of highschool/middle-school mathematics teachers and the community of teacher/ scholars remain quite distinct. There is good will, but little interaction. The existence of two communities seems quite natural to most of us because membership in anything as vague as a "mathematical community" is largely a matter of self-identification. Most high-school and middle-school teachers identify themselves as teachers first and mathematicians second, while for most university and college faculty the reverse is the case. This state of affairs is typical in the United States. But what is natural is not necessarily desirable, and many now decry this state of affairs. You have only to pick up a recent

VOLUME 19, NUMBER 2, 1997

copy of the AMS Notices or the MAA's Focus to discover the depth and breadth of professional alarm over U.S. students' level of achievement in mathematics and science, the innumeracy and scientific illiteracy of the general public, the failure of just about everyone to appreciate the beauty of mathematics, a n d - - o f c o u r s e - - t h e reduction in government support for pure research. A few writers posit a direct link between these shortcomings and the imminent decline and fall of the United States. The situation would be different, some argue, if we, the research community knew how to communicate the excitement and significance of our research to the larger c o m m u n i t y - - o r even just to the community of highschool mathematics teachers, ff only the teachers could see mathematics through our eyes! When, in 1989, the national Science Foundation announced a new "experimental activity" to help bridge the gap between education and research, Valley mathematicians answered the call to action.

The Regional Geometry Institutes "All too frequently," the NSF explained in its proposal solicitation, "research and education are separated more than is desirable. This experiment is designed to illustrate a means of cooperation that allows researchers, educators, and students to benefit from one another's presence and participation in a common program." The vehicle for this cooperation was to be several "Regional Geometry Institutes," where "research mathematicians will congregate to learn new geometry tools and to interact with mathematics educators, as well as undergraduate and secondary students." The RGIs were not buildings, but events that would take place on university campuses or other suitable sites. Each RGI was to have an Advanced Research Component (ARC) for research mathematicians and a Creative Education Component (CEC) for educators, which were to be integrated in some effective way. The NSF's new program held great appeal for the Valley geometers: in fact, it seemed designed for us. We all

THE MATHEMATICAL INTELLIGENCER

knew one another, both as long-term colleagues with many collaborations and through the very active Valley Geometry Seminar, and many of us had already had considerable experience in organizing national and international conferences. Also, we knew many of the local teachers, thanks to all those workshops. With the assistance of Five Colleges, Inc., we designed a program of month-long summer institutes to be held in 1991, 1992, and 1993. We chose "Geometry in the Machine Age" as our overall theme. The computer would be the great leveler at our R G I - - r e s e a r c h e r s and educators would teach one another. In our proposal we explained that "the overall theme of the institute will be the interaction between geometry and computation." Our goals were "integrative and participatory." "Geometry in the Machine Age" was one of three RGIs funded by the NSF. As it turned out, the computers were neither levelers nor integrators. The teachers and the researchers had very different goals: the teachers were more interested in educational software, the researchers in high-powered research software tools. But other integrating mechanisms were built into the program: some of the lectures were for e v e r y o n e - - t h e s e were billed as "all-

Institute"--and there were occasional panel discussions of educational issues. During coffee breaks, meals, and evening events the two groups mixed socially. Donal O'Shea of Mount Holyoke College was the director for the overall three-year program, but since the subfields differed from year to year (differential geometry, algebraic geometry, discrete geometry), each summer program had its own ARC and CEC directors, program committees, and so forth. The three ARC successive directors were Rob Kusner of UMass, David Cox of Amherst, and myself. Marty Conway, a high-school teacher in Longmeadow High School, was the Principal Investigator with special re7 sponsibility for the CEC. Our research programs were built around several series of lectures by invited speakers, each series lasting one or two weeks. Generous funding made it possible to invite excellent speakers from far and wide, and they in turn attracted excellent participants. Faculty participants also gave lectures as time permitted, and computer workshops were tucked in and around the other events. Some of the researchers brought problems with them; others used the RGI as an opportunity to retool. The intellectual atmosphere was

Ludwig Danzer and Marjorie Senechal at the RGI, 1993.

Struggling with geometry at the workshop. (Photo by Dixie Trollinger.)

electrifying. The t e a c h e r s also c a m e f r o m far and wide, a s well as from nearby. F o r the first t w o years, the CEC directors, a s s i s t e d b y Marty and b y m a s t e r t e a c h e r s Bridget Arvold and J i m Ebert, d e v e l o p e d s p e c i a l p r o g r a m s for them. In the first year, the ARC and CEC p r o g r a m s w e r e l i n k e d thematically, while in the s e c o n d y e a r they w e r e "separate b u t equal." In the third year, however, w e a b a n d o n e d the twoc o m p o n e n t m o d e l . W h a t led us to do this, and w h a t w e l e a r n e d as a result, is t h e s u b j e c t of this article. As director-elect o f the third-year p r o g r a m , I o b s e r v e d the RGI in its first t w o y e a r s from time to time. The m o o d w a s friendly a n d the p a r t i c i p a n t s in both programs rated their experiences highly. But I s e n s e d a c o n t r a d i c t i o n bet w e e n the t w o - c o m p o n e n t m o d e l on the one h a n d a n d the goal o f a comm o n p r o g r a m on the other. A c o m m o n p r o g r a m would, o r could, o r should, e n c o u r a g e m a t h e m a t i c a l interaction, a m o s t desirable goal. But h o w could we have one c o m m o n p r o g r a m if in fact w e h a d two? I w o n d e r e d h o w w e might r e s t r u c t u r e the RGI to f o s t e r genuine "vertical integration." Vertical Integration? Although the t e r m "vertical integration" did not a p p e a r in the original pro-

p o s a l solicitation, the e x p r e s s i o n w a s u s e d informally at the NSF as t h e conc e p t o f t h e RGI d e v e l o p e d [1] a n d was p a r t o f o u r v o c a b u l a r y as w e develo p e d o u r proposal. At the time, the p h r a s e s e e m e d benign; o u r only conc e r n w a s the e x t e n t to w h i c h it could be achieved. I a m less c o m f o r t a b l e with it in retrospect. Vertical? We all agree t h a t mathem a t i c s is a hierarchical subject: every layer o f n e w k n o w l e d g e is built on all the e a r l i e r ones and is itself a prerequisite for the next. We are less willing to a d m i t - - i n p r i n t - - t h a t o u r profession is hierarchical as well [2], b u t w e all k n o w t h a t it is true. With s e v e r a l notable exceptions, the top p l a c e s o f the h i e r a r c h y are awarded, b y t a c i t b u t c o m m o n consent, to m a t h e m a t i c i a n s w h o s e p o s i t i o n s allow t h e m to s p e n d as m u c h time as they like on t h e i r research. The n e x t level is p e o p l e d b y t h o s e w h o s e teaching duties a r e light and c l o s e l y linked to their r e s e a r c h , a n d s o o n d o w n to the high-school t e a c h e r s w h o t e a c h all d a y e v e r y day. Integration? This was easily a c c o m plished. As one of our evaluators, R o n a l d Narode, noted the first summer, "The r e s e a r c h e r s give m a t h e m a t ics t a l k s to the teachers. The res e a r c h e r s d e s c r i b e their intellectual activities in talks to the teachers. The

r e s e a r c h e r s offer the tutorial s e r v i c e s to the teachers. All the t e a c h e r s n e e d do is a s k for assistance, and t h e y would b e w e l c o m e d by t h e m a t h e m a t ics r e s e a r c h c o m m u n i t y . . . . " [3] In o t h e r w o r d s , "vertical integration" g r a c i o u s l y afforded t e a c h e r s an o p p o r t u n i t y to see w h a t real m a t h e matics is a n d to interact with r e a l mathematicians. As N a r o d e explained, "the chief c o n c e r n for the s u m m e r RGI is the geometry. To the e x t e n t that t h e r e s e a r c h e r s a r e the e x p e r t s in this field, t h e y r e p r e s e n t the 'upper c l a s s ' of the m a t h e m a t i c s community." Noblesse oblige w a s built into the v e r y c o n c e p t o f the RGI. Not that m o s t r e s e a r c h e r s w e r e aloof o r snobbish. "With few e x c e p tions, the r e s e a r c h e r s d e s c r i b e their int e r a c t i o n s with the t e a c h e r s as b e i n g p l e a s a n t and refreshing . . . . Some o f the r e p o r t e d a d v a n t a g e s in having t h e t e a c h e r s at the c o n f e r e n c e are: m o r e w o m e n are a t t e n d a n t t h a n n o r m a l l y attend m a t h e m a t i c s c o n f e r e n c e s (rep o r t e d b y m e n and w o m e n res e a r c h e r s ) . . , t h e t e a c h e r s provide a social outlet for s o m e o f the res e a r c h e r s w h o tire of c o n s t a n t m a t h e matical d i s c u s s i o n and w h o a p p r e c i a t e the c o m p a n y o f 'normal' people." There w a s a n o t h e r benefit as well: ".... the t a l k s which w e r e r e c o m m e n d e d for a general a u d i e n c e w e r e thought to b e m o r e intelligible to t h e research community .... As one res e a r c h e r e x p r e s s e d , 'When m a t h e m a t i cians p r e t e n d to give a t a l k to t e a c h ers, they g e n e r a l l y give a talk t h a t a m a t h e m a t i c i a n c a n understand.' " Despite the p l e a s a n t a t m o s p h e r e , the "natural" h i e r a r c h y w a s all t o o app a r e n t at the RGI, although it r a r e l y c a m e out as blatantly as w h e n one res e a r c h e r a s k e d the evaluator, "What are they [the teachers] doing here?" I was not h a p p y with this vision of vertical integration. The p r o b l e m w a s n o t simply t h a t these p a r t i c u l a r individuals had t h e s e particular attitudes. The issue w a s deeper: in the United States, t h e high-school/middle-school m a t h e m a t ics t e a c h e r s a n d the t e a c h e r / s c h o l a r s constitute n o t only t w o communities, but two distinct cultures, and the gulf b e t w e e n t h e m is wide.

VOLUME 19, NUMBER 2, 1997

As Narode explained, "The culture of the mathematics research community (researchers, graduate students, and undergraduates) is a culture of intellectual fLxation, private cogitation, individual accomplishment, and readfly recognizable success. The highest value is knowledge which is also its own reward . . . . The difficulty of the intellectual task of creating new mathematics is apparent to all of the researchers. They do not pretend to understand much of the mathematics which their colleagues describe to them, nor are they troubled by this lack of understanding . . . . Contrary to the individual culture of the mathematicians, the high school teachers are 'other d i r e c t e d ' . . . Furthermore, the teachers echo the recent NCTM Standards which values communication and cooperation among students learning mathematics . . . . One of the teachers described the difference between the two cultures thus: 'The researchers are totally self-centered. All they really care about is their own task or problem.'" The two-cultures problem [4] led us, in the third year, to replace the twocomponent model with a more unified program that would engage all the participants in parallel mathematical problems. While some parts of the program were of interest only to researchers and others only to teachers, there was a large common core. The first of each of the main lecture series was to be accessible to the entire Institute; to this end, the speakers were asked to send an outline to the associate director, Doris Schattschneider, a month or so in advance. Doris used these outlines to provide the teachers with some of the background and terminology they would need to follow the talks. (That cultural gap had appeared: the teachers expected to understand the lectures they attended and were unhappy if they could not.) The speakers met with the teachers fight after their first lectures for questions and discussion, and also led an afternoon "hands-on" problem-solving workshop later in the week. It worked! Many of the participants soon found common mathematical interests (especially after the researchers

36

THE MATHEMATICALINTELLIGENCER

discovered the workshops). Most of the teachers tackled the problems they were given with great enthusiasm and made presentations (but only to their group) of their progress in solving them. In other words, they experienced the "research mode" and found it refreshing. It helped, of course--but I do not believe it to have been crucial--that the topic that summer was discrete geometry, which can be studied both hands-on and hands-off at many different levels. But today, over three years later, I am appalled that it never occurred to me to plan an integrated education program as well: to invite famous educators to give lecture series, to brief the researchers before their lectures on some of the subtleties of pedagogical issues and to debrief them afterwards, and to plan participatory workshops for them. Our common program was a common program in researchers' terms. Vertical integration was no longer noblesse oblige, it was cultural imperialism.

The Search for Community I do not doubt that RGIs, their successors (RIMSs, or Regional Institutes in the Mathematical Sciences), and other programs that bring researchers and teachers together are valuable professional experiences for the participants [5]. But can they really address the two-

cultures problem? Looking back on the RGI experience, I realize that we gave little if any thought to sustaining mathematical community, beyond encouraging everyone to stay in touch via the Internet. Today, the two mathematical communities in the Valley may appreciate one another a little better than they did before, but they are not much closer. Teachers still don't attend the CVC, and it is the rare researcher who shows up at MathWest. We, the organizers, were thoroughly exhausted by the RGI, and have gone back to tending our mathematical gardens. If we believe that mutual appreciation will really help to solve America's math and science woes, or that it is an important goal even without the threat of Armageddon, then we should thinl( beyond the conference mode. Why not approach the mathematical two-culture problem in the same way that we build understanding between national cultures? International exchange programs, such as the Fulbright program, do far more than international conferences possibly can to expand the participants' world outlook and increase their understanding of other peoples and the problems of other societies. Ultimately, exchange programs benefit society at large, as many participants become leaders in their disciplines, in industry, and in government. It is this

larger benefit that persuades the U.S. Congress to continue supporting the Fulbright program. By analogy, the NSF might establish a competitive and prestigious two-way fellowship program between the teaching and research cultures. Under such a program, large numbers of high school teachers might spend a year at a university working with college and university faculty on research projects and also helping them to assess the quality of their undergraduate teaching. Conversely, a year-long fellowship in a high school or community college, during which a young researcher could experience the highs and lows of "real teaching," work closely with teachers on curricular development, and help to bring the wealth of mathematical culture into the schools, might become a valued part of the graduate or postdoctoral training of research mathematicians. I am sure that readers of this colunto--in many countries--have other, probably much better, suggestions. The subject is wide open for discussion, and I hope that you will join in.

As we look for programmatic solutions, we should also examine the values that are the root of the problem in the first place. The difficulty we have in conveying the importance and beauty of mathematics is not (only) a matter of public relations. Its deeper source is the insularity and hierarchical structure of the (United States) research community, and our attitude toward the people we want most to persuade. REFERENCES

1. John Polking, oral communication 2. V. I. Arnold, "Topological problems of the theory of wave propagation," Section 1, Uspekhi Mat. Nauk 51:1, 3-50 (Russian Math. Survey 51:1, 1-47), 1996. 3. R. Narode, Assessment Report of the NSF/ Five Colleges Regional Geometry Institute: Geometry in the Machine Age, 1991 4. C. P. Snow, The Two Cultures, and a Second Look, Cambridge, Cambridge University Press, 1964. 5. William Velez, "Integration of Research and Education: what does it mean and how can it be accomplished?", Notices Amer. Math. Soc. 43 (10), October 1996, pp. 1142-1145.

VOLUME 19, NUMBER 2, 1997 3 7

Two Places at Once:

A Remembrance of

Paul Erdds nyone entering the faded old building of the Mathematical Institute of the Hungarian Academy of Sciences in the past 20 years could immediately tell rwhether Paul Erd6s was in town. I f he was, the large black door of the director's office was wide open, and the place was bustling with people. A secretary w o u l d b e typing Erd6s's latest m a n u s c r i p t and complaining a b o u t his scratchy, childish handwriting. A n o t h e r s e c r e t a r y might b e on the phone, trying to m a k e airline reservations for E r d 6 s ' s forthcoming lecture t o u r through several continents. The librarians w o u l d b e b u s y locating articles he requested, a n d running u p s t a i r s to x e r o x them. There w o u l d b e a s t e a d y s t r e a m of friends a n d colleagues, here to t a k e up the t h r e a d of c o n v e r s a t i o n o r w o r k left off the d a y - - o r s o m e t i m e s several m o n t h s - - b e f o r e . Meanwhile, E r d 6 s w o u l d be sitting in t h e director's velvet-upholstered armchair, in the m i d d l e of a p h o n e call. He was a l m o s t a l w a y s in the middle o f a p h o n e call. Or dialing. Or cursing o u t the telephone c o m p a n y b e c a u s e all the lines w e r e busy. (Oddly enough, m o s t of his t e l e p h o n e calls w e r e quite short. After asking a c o u p l e o f quick questions, he usually s k e t c h e d his latest i d e a s r e l a t e d to a mathematical p r o b l e m . Finally, he w o u l d list all the p l a c e s and telephone n u m b e r s w h e r e he could be r e a c h e d during the rest of the day.) It w a s only n a t u r a l that he should o c c u p y the d i r e c t o r ' s office. Here he w a s c l o s e r to the secretaries, the a r m c h a i r s were m o r e c o m f o r t a b l e and, what's more, from this office one could m a k e d i r e c t international calls. E v e r y d i r e c t o r of the Mathematical Institute since its founding in 1950 has b e e n a good friend o f Erd6s. They w e r e m o r e than h a p p y to let him use their office. Paul Erd6s w a s a "monarch," af-

THE MATHEMATICAL INTELLtGENCER 9 1997 SPRINGER VERLAG NEW YORK

t e r all. He w a s one of the b r i g h t e s t m a t h e m a t i c a l luminaries o f o u r century. Though it is t o o early to j u d g e the true d i m e n s i o n s of his influence on m a t h e m a t i c s and m a t h e m a t i c a l life, it is clearly e n o r m o u s . Simultaneous Games Most of us, ordinary mortals, do not k n o w w h i c h w a y to turn w h e n several p e o p l e w a n t to see us at the s a m e time. But E r d 6 s was at h o m e in situations like this. He w a s v e r y p r o u d o f his ability to do s e v e r a l things simultaneously. He c o u l d c h a t with a guest a b o u t politics, analyze t w o different m a t h e m a t i c a l p r o b l e m s with two others, a n d r e a d a b o o k - - a l l at once. He w o u l d e m b a r r a s s his h o s t s w h e n on top o f t h e s e activities h e ' d also c o n t e n d w i t h dinner. The guests w o u l d all be seated, waiting for the first course, w h e n all of a sudd e n Paul w o u l d j u m p up a n d r u s h to the t e l e p h o n e to call s o m e o n e he h a d b e e n w o r k i n g with earlier that day. He w o u l d quickly explain a f r e s h i d e a that s t r u c k him as relevant to a problem, and, possibly, the key to its solution. By acting this way, he w o u l d set a difficult t a s k for his host; after d i n n e r h e ' d have to c o n v i n c e his spouse that E r d 6 s w a s n o t a rude man, he did n o t w a n t to insult anyone. In fact, w h e n any of his friends w a s in serious trouble, he c a l l e d i m m e d i a t e l y and t r i e d to b e of help. Nevertheless, in his universe m a t h e m a t i c s s t o o d so high above the ordi-

Paul Erd6s: A r e c e n t p i c t u r e ( c o u r t e s y o f T e r m 6 s z e t Vil~ga).

VOLUME19, NUMBER2, 1997 39

nary aspects of life that he sometimes could not resist the he received (and accepted) some 20 honorary degrees vnd temptation to drop everything else. memberships in distinguished academies, he attributed He dazzled his acquaintances by his knowledge of everythem partly to his old age. He always said that he would one's telephone number. Although he published an enorbe happy to trade all of his titles for a beautiful theorem. mous number of papers, when someone asked about any He meant it, too. of his theorems, he always remembered the title of the paper, the name of the journal where it appeared, and the Child Prodigy year of publication. He even knew the exact page numbers. Pgfl Erd6s was born in Budapest on March 26, 1913. While But he was gifted with total recall of more than just numhis mother was in the hospital giving birth, her three- and bers. Sometime towards the end of the 1950s, in the guestfive-year-old daughters fell ill with scarlet fever and died. house of the Hungarian Academy at Mfitrahfiza, my father inPaul grew up as an overprotected only child. Fearful of controduced him to a colleague of his, the historian Lajos Elekes. tagious diseases, his parents kept him away from public Paul, who was interested in practically everything, immedischools, and he completed most of his studies as a private ately engaged him in a conversation. It was his habit to ask student. Both his parents were high-school mathematics people: "What's your profession?" As soon as he found out teachers, so they instructed Paul themselves. But they also that Elekes was writing a book about the 15th-century hired tutors and a German governess. Paul's father fell into Hungarian general and governor, Jfinos Hunyadi, he proRussian captivity during World War I, and returned to Hungary only in 1920. This was the first time he could talk ceeded to inquire about the causes of the catastrophic defeat of the Hungarian army by the Turks in the battle of Varna, to his son. Soon after that, he started to teach Paul English and introduced him to the realm of prime numbers. in 1444. The conversation soon broke up, perhaps because it was lunchtime, and continued a year later at the same place. In a recent lecture at E6tv6s University, Budapest, Paul When Paul noticed Elekes, he recognized him right away and described the child he once was as a "bit of a prodigy." shouted from afar: "So why did Hunyadi lose at Varna?" When he was four, he discovered negative numbers, and Roughly 15 years later, I witnessed Paul approaching the he was able to multiply four-digit integers in his head. From famous Hungarian poet, Ferenc Juhfisz. "What's your prothe age of 13 he was a regular problem solver of K6MaL, a first-rate Hungarian mathematics journal for high school fession," he asked, as usual. Everybody around felt somewhat embarrassed, because Juhfisz then was at the peak students. At the end of every year, his picture appeared of his career. The whole country knew his face, especially among the photos of the most successful students. his characteristic moustache. He often appeared on TV, the In 1930, he was admitted to the university of Budapest, literary magazines and supplements were full of his poetry, and in the same year (at the age of seventeen!) he made and he published one volume after another, wherever he his fn'st important mathematical discovery: he found an elwent, he was instantly recogementary proof of the famous nized. He obviously enjoyed theorem of Chebyshev, according to which between any his being a celebrity and was not used to questions like that. positive integer greater than 1 "I am a poet," he declared and its double there is a prime proudly. Paul innocently number. He liked to quote Nathan Fine's words: asked, "And how do you make a living?" Paul spent relatively Chebyshev said little time in Hungary, he aland I say it again: most never watched TV, and There is always a prime he did not regularly follow the between n and 2n. Hungarian journals. So he In his doctoral dissertation, could hardly have heard of Juhhsz before. He certainly did written under the supervision not want to offend him, of Leopold Fej~r, he proved some far-reaching generalizathough. In fact, I doubt that he ever wanted to hurt anyone's tions of this theorem. The year he defended his thesis, feelings. he was only twenty-one. It is true, however, that he During his student never paid much attention to titles, ranks, and decorations. years, he met Tibor Gallai, Gy6rgy Szekeres, and Paul If he was interested in a question, he was eager to discuss it Turgm, who became lifelong friends and collaborators. with anyone, be he an Einstein They often attended D~nes or a cabdriver. He was much K6nig's lectures on graph theless prejudiced than anyone else I have ever met. Although The lO-year-old Paul and his parents. ory at Budapest's Technical

40

THE MATHEMATICALINTELLIGENCER

Erd6s's season ticket for half-fare travel on the Hungarian State Railways. (Notice his signature hardly changed in 70 years.)

University. Answering a question raised in one of these lectures, the 18-year-old Erd6s found an exciting extension of a theorem of Menger to infmite graphs. (His proof was inchided in KSnig's classical monograph published in 1936.) One year later, Erd6s and Szekeres made a brilliant discovery that led to the publication of their first joint paper. It is rightly regarded now as a starting point of Ramsey theory and combinatorial geometry. From 1934 to 1938, Paul worked in Manchester and spent only his vacations in Hungary. He often recalled that before he left for England, he had never had to butter his own bread. This turned out to be a fairly easy skill to master, but he never learned how to prepare food for himself. Once I spent a few days with Paul in his apartment in Budapest. When I entered the kitchen in the evening, I was met with a horrible sight. The floor was covered by pools of blood-like red liquid. The trail led to the refrigerator. I opened the door, and to my great surprise saw a carton of tomato juice on its side with a gaping hole. Paul must have felt thirsty and after some reflection, decided to get the juice out of the carton by stabbing it with a big knife. The many mathematics contests for elementary and high school students, the problem sessions of K6MaL, and the special mathematics programs in a network of selected schools in Hungary have always brought to the surface some extraordinarily gifted children. Paul never missed an opportunity to talk to them. He tried to accept all invitations, whether they came from an elementary school in a

remote provincial town, a topnotch Budapest Gymnasium, or Trinity College, Cambridge. Some of the most talented children he discovered were Attila M&t~, Lajos P6sa, and Imre Ruzsa. P6sa was a real child prodigy. He was twelve when the outstanding Hungarian logician and pedagogue, R6zsa P&er, introduced him to Paul, and one year later Erd6s and P6sa were already writing a joint paper in graph theory. Paul referred to children as "epsilons." He loved to hold babies in his arms. While doing this, he usually asked, "Isn't it remarkable how calm this epsilon is?" (The parents, especially if they did not know him, were less calm.) At airports, in restaurants, on the streets, he would accost people with small children. "How old is this epsilon? Very cute! Tell me, is it a boss or a slave?" (At this point, someone had to explain to the astonished parents that the question referred to whether the child was female or male, respectively.) If the child was not so young, he or she could hardly get away without seeing the following performance. Paul would pull a coin from his pocket and place it on the back of his hand. Then he would suddenly snatch his hand away, letting the coin fall, but catching it with the same hand before it hit the ground. Most kids would just stand there gaping. Either because they appreciated the difficulty of the trick, or because they had no idea what this strange man was doing. But they rarely cried. When the conversation shifted to epsilons, Paul liked to recall the following episode. His mother asked a lady how

VOLUME 19, NUMBER 2, 1997

41

m a n y children she had. "Seven," she a n s w e r e d . Aunty AImus (this is w h a t I called Paul's mother), w h o could never get over t h e tragic loss o f her daughters, n o d d e d appreciatively: "Then y o u are a rich woman." Fight for Freedom

In t h e p a s t 20 y e a r s Paul E r d 6 s b e c a m e , m o s t likely, the b e s t - k n o w n m a t h e m a t i c i a n in the world. His unique fame and p o p u l a r i t y is e x p l a i n e d mainly by his u n p a r a l l e l e d scientific a c h i e v e m e n t s and also by the fact t h a t he w a s in c o n t a c t with a l m o s t all the leading m a t h e m a t i c i a n s of his time. He p u b l i s h e d j o i n t p a p e r s with 458 people, but the n u m b e r of t h o s e w h o s e c a r e e r was p r o f o u n d l y influenced b y his i n n u m e r a b l e questions, p r o b l e m s - - a n d o v e r 1500 art i c l e s - i s m u c h higher. Most p e o p l e are f a s c i n a t e d by records, and it is i m p o s s i b l e to c o m p e t e with the above numbers. They are staggering. However, one has to be careful with n u m b e r s . They m a y lead us to believe t h a t w e are closer to u n d e r s t a n d i n g of an e x t r a o r d i n a r y p h e n o m e n o n than w e really are. A movie b y Werner Herzog e n d s with the d i s s e c t i o n o f the b o d y of the m a i n character, K a s p a r Hauser, w h o h a d h a d a peculiar life and an original w a y of thinking. The d o c t o r s and scholars are relieved to find that his liver w a s oversized and his brain also h a d s o m e special features. They have no

d o u b t t h a t these irregularities a c c o u n t for Kaspar Hausex's c u r i o u s personality. Allegedly, Einstein's brain w a s also s u b j e c t to t h o r o u g h analysis in an a t t e m p t to u n l o c k the u l t i m a t e s e c r e t o f his genius. In m o s t of Erd6s's obituaries, it was e m p h a s i z e d that he led an u n a s s u m i n g life. He o w n e d a l m o s t nothing, n o t even books. He traveled a r o u n d the w o r l d with two half-empty suitcases, containing only his laundry, his toilet bag, a n d his p o c k e t radio. After the d e a t h of his m o t h e r in 1971, w h i c h he never quite got over, he t r a v e l e d mostly b y himself. He found it hard to stay in the s a m e town for longer t h a n t w o weeks. As m a t h e m a t i c i a n s like to say, Paul w a s " e v e r y w h e r e dense" on the earth. If you w a n t to s e e him, j u s t s t a y in one p l a c e and w a i t - - h e will s o o n a p p e a r . . . He r e m a i n e d single all his life, and he never t o o k a j o b t h a t required serious c o m m i t m e n t . If his w o r k or scientific i n t e r e s t d r e w him to a n o t h e r place, he did not hesitate for a m o m e n t . He w a s r e a d y on a f e w h o u r s ' notice to fly to, say, Singapore with only a h u n d r e d dollars in his p o c k e t . W h e r e v e r there were active m a t h e m a t i c i a n s , he w a s m o s t w e l c o m e , so he did not have to w o r r y a b o u t a c c o m m o d a tions a n d money. This life-style, free of conventional restrictions, m u s t also have c o n t r i b u t e d to Erd6s's c o l o s s a l scientific success. It is n o t an accident that Paul d e v e l o p e d such a life-style.

Erd6s talking about mathematics to elementary school children in Szt~linv~ros in 1955. Pictures of Stalin and Lenin are above the blackboard.

.,4~

T H F i~AATIMFiXAATINAI IRITFI I I~Ft~I~.FI~

F a t e and history w e r e n o t so gracious to him as, say, to Gauss. They did n o t lay at his feet the p r o s p e c t o f a peaceful a n d c o m f o r t a b l e middle-class life. In 1919, during the short-lived Hungarian Soviet Republic, Paul's m o t h e r was h e a d m i s t r e s s of a high school. Because of this, she was l a t e r b a n n e d from t e a c h i n g for the rest of h e r life. This "bit of a prodigy," who g r e w up in a strongly anti-Communist a n d anti-semitic political environment, felt f r o m the very beginning that s o o n e r o r l a t e r there would b e no p l a c e for h i m in his own country. When it b e c a m e c l e a r that G e r m a n y ' s appetite for t e r r i t o r i e s w a s not satisfied b y the Anschluss, and that it w o u l d s o o n a t t a c k Czechoslovakia, Paul said goodbye to his p a r e n t s a n d left Hungary. When he r e t u r n e d 10 years later, n o n e of his close r e l a t i v e s - - s a v e his m o t h e r and one of his a u n t s - - w e r e alive. Like his p a r e n t s a n d m o s t of his lifelong friends, Paul h a d always b e e n a leftist at heart. But he w a s n e v e r blind to t h e m i s t a k e s a n d c r i m e s c o m m i t t e d by the C o m m u n i s t regimes. As soon as the first s h o w trials got u n d e r w a y in Hungary, Paul p a c k e d his s u i t c a s e s again, said g o o d b y e to his mother, and left. By t h e time the first victim o f these trials, Lhszl5 Rajk, w a s s e n t e n c e d to death, Paul w a s b a c k in the United S t a t e s - - b u t with no s t e a d y income. He w a s a l r e a d y a famous m a t h e m a t i c i a n , yet he w a s n o t e x a c t l y o v e r w h e l m e d with offers. He w a s n o t i n t e r e s t e d in an acad e m i c p o s i t i o n with r e g u l a r teaching duties, b u t he w o u l d n o t have r e j e c t e d a s e r i o u s r e s e a r c h fellowship. He w a s also m o r e a n d m o r e c o n c e r n e d a b o u t t h e chilling effects of the McCarthy era. He sadly r e c o u n t e d the t i m e w h e n he w a n t e d to t e l e p h o n e his m o t h e r from a friend's h o u s e to c o n g r a t u l a t e h e r on her 70th birthday. His host, however, did n o t a l l o w him to m a k e the call, b e c a u s e he did n o t w a n t to be s u s p e c t e d of a s s o c i a t i n g with Communists. This fear was not unfounded. Soon a f t e r w a r d it t u r n e d o u t t h a t the FBI h a d p u t t o g e t h e r a sizeable file on Paul. They k e p t r e c o r d s o f his v a s t c o r r e s p o n d e n c e , a n d held it against him that he w a s in c o n t a c t with c o l l e a g u e s from C o m m u n i s t countries, especially Hungary and China (e.g., he c o l l a b o r a t e d with Loo-Keng Hua). In 1954, Paul w a s invited to s p e a k at the International Congress of M a t h e m a t i c i a n s in Amsterdam. He n e e d e d a re-entry visa to the United States. The I m m i g r a t i o n Service s e n t an officer to the M a t h e m a t i c s D e p a r t m e n t o f the University of Notre Dame, w h e r e Erd6s w a s w o r k i n g at the time. "What is your o p i n i o n a b o u t Marx?" the officer a s k e d him during the c o u r s e o f an interview. "I do not feel c o m p e t e n t to j u d g e Marx," Paul a n s w e r e d " b e c a u s e I have r e a d only the Communist Manifesto b y him. But I do believe he w a s a great philosopher." Then he was a s k e d w h e t h e r he w o u l d visit Hungary if t h e Hungarian authorities g u a r a n t e e d that he c o u l d leave t h e c o u n t r y w h e n e v e r he w a n t e d to. "Of c o u r s e I would!" he replied. "My m o t h e r lives t h e r e as well as s o m e of m y b e s t friends." His visa application w a s t u r n e d down, b u t Paul d e c i d e d to p a r t i c i p a t e in the congress, anyway. He p a c k e d again

and left the United States. He w a s n o t allowed to r e t u r n for nine years. His A m e r i c a n friends had b e g g e d him to stay, walt a y e a r and submit a n e w petition. Before he left, he s p e n t his last night at the h o m e o f Harold N. Shapiro, who fiercely criticized his decision: "I should k n o c k y o u on t h e h e a d a n d tie y o u up to s t o p y o u from leaving!" Paul r e m a i n e d firm. He sadly replied, "O.K., then tie m e up!" His case w a s r e c o n s i d e r e d only in 1963, two years after Kennedy b e c a m e president. F r o m A u g u s t 1955 on, Paul s p e n t a couple o f m o n t h s a y e a r in Hungary. In 1973, again for political reasons, this p a t t e r n w a s broken. The Bolyai Mathematical Society cele b r a t e d E r d 6 s ' s 60th birthday by organizing a big conference at Keszthely with h u n d r e d s o f participants. The Hungarian authorities denied an e n t r y p e r m i t to the Israeli guests. Paul w a s furious. He called a high-ranking p a r t y official and l o d g e d a vigorous protest, but to no avail. He v o w e d n o t to return to Hungary for a long time. Indeed, h e did n o t r e t u r n until 1976, and t h e n only to visit one of his b e s t friends, Paul Turfin, w h o w a s dying. (While remaining affiliated w i t h the Hungarian A c a d e m y for decades, Paul was also " p e r m a n e n t visiting p r o f e s s o r " at the Technion in Halfa.) Thus, one cannot explain E r d 6 s ' s v a g a b o n d life style simply by his restless nature. He c h o s e to be free, and for that he h a d to m a k e serious sacrifices. He did not let anyone r e s t r i c t his free m o v e m e n t a n d work, n o t Hitler, n o t Joe (after J o s e p h S t a l i n - - t h i s is h o w he referred to Russia and to t h e C o m m u n i s t powers), a n d n o t Sam (the United States), either. He did not believe t h a t the glory of the sup e r p o w e r s w o u l d last forever, b u t J o e ' s s u d d e n collapse s u r p r i s e d him. In the spring o f 1989, I b e t him 5000 forints that t h e Soviet Union w o u l d disintegrate within a year. I lost, b u t l a t e r Paul a d m i t t e d t h a t I h a d w o n a "moral victory." He added, with a little c o n c e r n in his voice: Once S a m and J o e w e n t up the hill To fetch a pail o f water. And J o e fell d o w n and b r o k e his c r o w n And Sam c a m e tumbling after.

Golden Age In 1956, Paul Erd6s w a s e l e c t e d a m e m b e r of the Hungarian A c a d e m y o f Sciences. He did n o t c a r e a b o u t ranks o r titles, b u t this m e m b e r s h i p I a m sure he t o o k a little m o r e seriously. He often flew b a c k from o v e r s e a s for a few d a y s to p a r t i c i p a t e in the general a s s e m b l y a n d to cast his v o t e for n e w m e m b e r s . When one o f his colleagues was e l e c t e d to be a c o r r e s p o n d i n g m e m b e r , he typically c o n g r a t u l a t e d him as follows: "I a m glad that y o u b e c a m e a demigod!" Several t i m e s a y e a r Paul a n d his m o t h e r s p e n t a couple o f w e e k s in the g u e s t h o u s e o f the A c a d e m y at Mhtrah~iza. Most of the guests w e r e scholars, but t h e r e w e r e also a few writers. Paul usually tried to arrange his p r o g r a m so that he and his m o t h e r w o u l d c o m e when t h e Turgms a n d m y p a r e n t s were also there. On such occasions, they laid a big table for the ten o f us in the dining r o o m o f the guesthouse. Most o t h e r t a b l e s w e r e small, and t h e y

VOLUME 19, NUMBER 2, 1997

43

rewrite well-known lines of Hungarian poetry. The central theme of their "compositions" was old age and senility, the two things that terrified them most. For instance, Erd6s paraphrased two famous lines by Sfindor Pet6fi as follows. One thought disturbs me, that I may decease In slowly progressing Alzheimer's disease.

Erd6s's mother in the guesthouse of the Hungarian Academy of Sciences in M&trah&za in 1969.

were occupied by elderly couples who rarely spoke to each other. Sometimes I caught their envious glances, because our table was so much livelier. The three Pauls, Erd6s (P.E.), Tur~in (P.T.), and Pach (P.P.)., were a fount of stories, jokes and ideas. (They used to call each other by their initials, like newspapermen, who sign their articles that way.) It lent a special flavor to the conversation that P.E. often talked to his mother in English. Aunty Annus started to accompany her son on his trips when she was eightyfour, and she decided to learn English. I will never forget how she would turn to Paul and ask: "Palk6, how do you call the fruit 'szilva' in English?" "Plimm, mother, plimm!" was his answer. It is quite remarkable that, although Erd6s started to study English at the age of eight and spent most of his life in English-spealdng countries, he had a very heavy accent. Recently, a documentary film was made about him, including interviews with several other Hungarian mathematicians. Paul was the only one whose English had to be subtitled. He did not have a good ear for music, and he did not particularly like it either. Turfin loved to listen to music while working, and he knew the classical repertoire very well. When Erd6s entered Turfin's study, he would stop and ask, "What is this noise?" It was among Erd6s's and Turgm's favorite diversions to

44

THE MATHEMATICALINTELLIGENCER

Erd6s quoted these "masterpieces" often and with pride, their questionable literary merit notwithstanding. Almost 20 years after TuVan's death, Erd6s no longer remembered exactly which line was written by him and which by Turgm. Both of them loved the poeins of Endre Ady and the "Westerners," a group of progressive Hungarian poets and writers who published their work in the periodical "Nyugat" (West). Whenever Ady's name was brought up in a conversation, Erd6s remarked, "He was a great poet, but a trivial person!" (In Erd6s-ese, "trivial" is "mean.") Paul never forgave Ady for breaking up with his long-time mistress by writing a devastating and humiliating farewell poem to her. "Have a game of ping-pong with me," said Turfin, "ancl I tell who you are." Indeed, if one pays attention, one can often sense how inventive, how generous one's partner is, how he can deal with failure or bad luck, how he can hold up under pressure, etc. As soon as Erd6s took his stand behind the ping-pong table, it was clear that he was an amateur and could not be a serious opponent. He even held the paddle in a strange way, as if he did not want to soil his hand with it. His serves were totally ridiculous; it was not hard to smash them. But then came the surprise: Paul easily repelled the attack! His reflexes were fantastic. One could not help thinldng that in his nervous system impulses somehow traveled a lot faster. Turfin had much better technique, he affected a Chinese style with spectacular motions. He was very proud of having won a table-tennis championship on board the Queen Mary. Erd6s and Turfin always put up a good fight. T u r ~ moved around like a pro, while Erd6s remained still and blocked the shots. When he missed a ball, he shouted out: "Fascism!"

Erd6s, Szekeres, and Tur~tn in the middle of a game of pingpong in 1958, during Szekeres's first visit to Hungary after the war. (The "dark man" at the left is unidentified.)

b e t t e r at r e c o n s t r u c t i n g an a r g u m e n t from fragments. Both o f t h e m liked to p l a y with us kids, a n d t h e y a l m o s t Rdnyi's dashing a n d witty c o m m e n t s , which even an epa l w a y s won. If any o f us m a n a g e d to p l a c e a g o o d shot, silon c o u l d appreciate, m a d e it e v e n m o r e fun to w a t c h E r d 6 s e x c l a i m e d with a smile of recognition, "Look! The them. e p s i l o n d o e s not surrender! He's fighting on . . ." He deWhen t h e g r o w n u p s w e n t for a walk, or p l a y e d pingf e a t e d m e even in 1984, in Calgary, in the b a s e m e n t of Eric pong, or w e r e hax~_ng coffee, a n d t h e scene b e c a m e quiet, Milner's house, although b y that time his eyesight had I s n e a k e d o v e r to the table to c a t c h a glance at "higher w e a k e n e d considerably. He did not see the high b a l l s at all. mathematics," i.e., at the n o t e s s c a t t e r e d on the table. I w a s At M~trahfiza, the t h r e e Pauls (Erd6s, T u r ~ , a n d Pach) a s t o n i s h e d w h e n I first s a w t o o k long e x c u r s i o n s in the t h e e n d - p r o d u c t o f their work: s u r r o u n d i n g hills. E r d 6 s w e n t strange letters, numbers, along mainly for the c o m p a n y . signs, arrows, scribble-scrabAnd, of course, it n e v e r h u r t to ble. Yet I felt that I, too, w o u l d get s o m e exercise. like to b e a scientist. I h a d n o T u r ~ enjoyed thick, overd o u b t t h a t the Laws of t h e g r o w n forests, a n d n a t u r e in Universe w e r e written in this general. He liked to e x p l o r e m y s t e r i o u s language. Othern e w p a t h w a y s - - j u s t as in his wise, h o w could mathematimathematics---and we were cal p r o b l e m s s p a r k such ent h e r e f o r e often late for lunch. t h u s i a s m in these brilliant a n d One o f his favorite slogans f a m o u s people! w a s "Don't stray from the unIndeed, they were at t h e b e a t e n path!" All t h r e e had the s a m e irre- Erd6s on the top of an observation tower in Sopron in fall 1969. p e a k o f their c a r e e r s then. They "conjectured and proved," sistible a d o l e s c e n t i m p u l s e to He had an adolescent impulse to climb every peak he saw. t h e y f o u n d e d schools, initiclimb each and e v e r y p e a k a t e d n e w theories, p u b l i s h e d t h e y saw. Not far f r o m the influential b o o k s a n d articles, a n d t r a v e l e d all over t h e guesthouse at M~ttrahs there is a fairly tall steel obserworld. T h e y l e c t u r e d at every i m p o r t a n t university f r o m vation tower. One h a s to climb up three s t e e p l a d d e r s to Beijing to Calgary. They had a w o r l d l y air a b o u t them. They get to the top. Quite a few rungs are missing, a n d t h e w h o l e o w n e d fine t w e e d jackets, listened to p o c k e t radios, a n d s t r u c t u r e s h o w s t h e r a v a g e s of time. Until v e r y recently, w o r e s h o e s that required no laces! Such things do not esErd6s, w h e n e v e r he visited the guesthouse, i n s i s t e d on c a p e a teen-ager's attention. c l a m b e r i n g up this tower, defying the warnings o f his anxious friends. I will n e v e r f o r g e t Turfin's o w n d e t e r m i n e d atAgainst the Supreme t e m p t to get to the top in the Fascist s u m m e r of 1975, w h e n he w a s E r d 6 s ' s w a y o f thinking w a s already fast losing his stxength. v e r y c l o s e to the ideas of t h e I also vividly r e m e m b e r F r e n c h Enlightenment. He beE r d 6 s and Turfin w o r k i n g tolieved d e e p l y that all g r e a t g e t h e r in M~trahgtza. They p r o b l e m s facing m a n k i n d have w e r e often j o i n e d b y Vera rational solutions. In his o w n Turfin-S6s (my aunt) a n d way, he always tried to do Affrdd Rdnyi, w h o w a s k n o w n everything to further truth. to e v e r y b o d y as "Buba." Turgm As a profane e x t e n s i o n often chided Erd6s for talking of an idea from Anatole France's "nonsense" and a s k e d h i m to novel, Revolt of the Angels, he r e p h r a s e his ideas m o r e preliked to call F a t e the "Supreme cisely. Erd6s had an incrediFascist." ( F a s c i s m had b e e n bly quick mind, and he w a n t e d the d e t e r m i n i n g e x p e r i e n c e o f to explain everything at the Erd6s in his e l e m e n t , 1 9 5 5 . his y o u n g e r years, so it is n o t s a m e rate o f speed, o c c a s i o n surprising that he used it as a ally skipping and jumping. m e t a p h o r for Evil.) He said, m o r e or less as a joke, that life (Only m u c h later, w h e n I w a s a s e n i o r at EStvSs University was a game, in which our o p p o n e n t w a s the Supreme Fascist a n d h a d s t a r t e d to c o l l a b o r a t e with Erd6s myself, did I fully (S.F.). The S.F. gets two points if w e do something m e a n u n d e r s t a n d w h y T u r i n h a d c o m p l a i n e d so vehemently. and one p o i n t if w e fail to do good. In this game, only the S o m e t i m e s it t o o k m e a d a y to w o r k out the details of a S.F. can win, b u t it should be our goal to keep his score low. p r o o f that h a d b e e n o u t l i n e d by Erd6s in five minutes. And Paul E r d 6 s w a s certainly an international g r a n d m a s t e r 10 y e a r s earlier he m u s t have b e e n even faster!) The misat this game. When anyone n e e d e d his help, he was t h e r e u n d e r s t a n d i n g w a s often s o r t e d out by m y aunt, w h o w a s

VOLUME 19, NUMBER 2, 1997

45

Erd6s and R6nyi in A a r h u s in 1 9 5 7 .

for them. He disbursed money among needy friends and distant relatives. He told them to keep it as long as they wished, and one day, when they were rich, they could return it. In the same spirit, he assumed legal and financial responsibility for a girl he had never met before, who wanted to move to Vienna to fulfill her dream of becoming a musician. (She succeeded!) After the sudden death of his mother in 1971, Erd6s's apartment in Budapest was used mostly by visiting mathematicians, old friends like Lee Lorch, Ggtbor Szeg6, Gy6rgy Szekeres, or colleagues with temporary housing problems. He often mentioned that half a century ago Americans tended to be far less tolerant and open-minded about cultural differences and alternative life-styles than they are nowadays. Princeton had several elegant "restricted" neighborhoods, where no Jews or Italians were allowed to reside. Many colleagues at the University and at the Institute felt uneasy about the presence of this outspoken Hungarian Jew who approached them with a kind of childish openness, and often showed up uninvited in their ofrices to discuss a mathematical question. They could not understand why he never opened a checking account or owned a house or applied for a proper teaching job. He kept producing the most beautiful results, among them his ground-breaking papers on probabilistic number theory with A. Wintner and M. Kac, and on approximation theory with Turf, l, yet the Institute for Advanced Study did not renew his fellowship for the year 1939. John von Neumann, like other leading mathematicians, was aware, certainly, of

THE MATHEMATICALINTELLIGENCER

Erd6s's extraordinary qualities and achievements, but did not lift a ringer to help him. It is very likely that these events also contributed to Erd6s's willingness to support those slightly quirky or eccentric mathematicians who were known to be gifted, but whom most people tried to avoid for this very reason. His political experience had taught him to raise his voice every time he believed an organization, government, or authority was infringing on an individual's private life and freedom. He highly respected his Communist friends who took part in the underground resistance against the Nazis, and lived through the infernos of Fascism and Stalinism. He also respected American civil rights activists, many of whom paid a very high price for their dreams and ideals. He often took a stand on much smaller issues, as well. Recently, he renounced his honorary doctorate from the University of Waterloo, in protest against the unfair dismissal of a colleague. The sensational mathematical event of 1948 was Atle Selberg's and Paul Erd6s's discovery in Princeton of an elementary proof of the celebrated Prime Number Theorem. This result, conjectured by Gauss, and first established simultaneously by Hadamard and de la Vall~e Poussin using heavy analytical tools, states that the number of primes smaller than n is asymptotically equal to n/log n. Selberg and ErdSs agreed to publish their results back to back in the same journal, indicating precisely their individual contributions. Unfortunately, it happened otherwise. Allegedly, not long after they made their discovery, it came to Selberg's ears that "Erd6s and someone else" had found an elementary proof of the Prime Number Theorem. He was so upset that he rushed ahead with the publication of his paper. Two years later, partly for this proof, he received the Fields Medal (the highest prize in mathematics, com-

Erd6s in Princeton in 1 9 4 1 . T h e Institute f o r A d v a n c e d Study did not r e n e w his fellowship.

Erd6s recei~/ing an honorary degree in Cambridge, England, /991.

Anyone else would have been depressed by such developments, and discouraged from doing joint work. But Paul did not care too much whether he deserved a Fields Medal. He was distressed only because he lost forever one of his greatest collaborators, A. Selberg. He continued to travel perpetually around the world, producing an infmite stream of questions, conjectures, and proofs. I have never met a more generous and noble-minded person than Paul. Wherever he went, his route was marked by a trail of mathematical ideas and discoveries. Like a missionary, he found followers everywhere. His famous problem surveys provide enough material, ideas, and open questions for another generation of researchers. I have no doubt that his mathematical diaries, kept for almost six decades, also hold a few scientific surprises. According to Erd6s, a wicked pastime of the "Supreme Fascist" is to try to keep secret the most beautiful mathematical theorems and laws of nature. But in this awesome struggle, Erd6s won some impressive victories against him. He found dozens of theorems and proofs which will surely be cited for centuries, if mankind survives. One of them is the following inductive argument, which proves that the product of all primes that do not exceed n is at most 4n. If n -< 4, then the statement is obviously true. Assume that we have already verified the statement for all positive integers smaller than n, and we want to prove it for n. We can assume that n is odd. The product of all primes that do not exceed n can be written as

V[P = l~P

p'
parable only to a Nobel Prize), which he more than deserved. Erd6s also published his contribution, for which the American Mathematical Society awarded him the (somewhat less prestigious) Cole Prize in 1951. Erd6s's role in the elementary proof of the Prime Number Theorem has been underestimated by the mathematical establishment. His colleagues at Princeton treated him especially coldly.

2p<--n+ l

V[p.

n + l<2p<--2n

By the induction hypothesis, the first factor on the righthand side is at most 4(n+1)/2. And now comes a brilliant idea, a surprising step so characteristic of Erd6s. Notice that the second factor can be bounded from above by ( ~ ) , be-cause every prime larger than (n+ 1)/2 occurs in the factorization of this binomial coefficient. Therefore,

Two places at once--a picture of Erd~;s taken and processed by Kurt Mahler.

VOLUME 19, NUMBER 2, 1997

47

~I p<-4 p
~ "

(+)

< - 4 ~ " 2 n-1 = 4 n,

as required. It is w o r t h noting that the a b o v e s t a t e m e n t immediately implies a w e a k e r version of o n e side of the P r i m e N u m b e r Theorem: the n u m b e r of p r i m e s s m a l l e r than n is at m o s t c n / l o g n, w h e r e c is a suitable constant. Paul was invited t o lecture at so m a n y p l a c e s t h a t he could not a c c e p t all t h e invitations he received. His m o t h e r w o u l d r e m i n d him: "Palkd, not even y o u c a n be in two p l a c e s at once!". But, in the end, this is exactly w h a t h a p p e n e d .

48

THE MATHEMATICALINTELUGENCER

lan Stewart,

|d,[~laL'J~'il,[q|Jl~.tt[r

Riccati's Grave in the Cathedral

of Treviso (Italy) Giorgio Tomaso Bagni

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 quaternious--

Editor

I

A egregie cose il forte animo accendono l'urne de'forti, o Pindemonte

--Ugo Foscolo acopo Riccati (Venice 1676-Treviso 1754) was one of the most important and original Italian mathematicians of the eighteenth century. Three of Jacopo Riccati's sons, Vincenzo (1707-1775), Giordano (1709-1790), and Francesco (1718-1791), worked actively in several branches of mathematics, too. Jacopo and Vicenzo Riccati did not try to obtain general methods to solve differential equations: they considered some special classes of differential equations, in particular those now named after them. The grave of Jacopo, Vincenzo, Giordano, and Francesco Riccati can be visited in Treviso, the town near Venice in which the mathematicians lived. In the Cathedral of Treviso, in

J

Duomo square, the Riccati family grave was placed in a lateral chapel, on the left-hand side of the left aisle. The last descendant of the Riccati Family was Giacomo (or Jacopo, 1747-1808), son of Francesco; the fme Riccati Chapel was then neglected and transformed into a passageway towards a secondary door, in the direction of the Baptistery. The tombstone is now placed under the inner wooden door. The inscription "Riccatae Gentis M" is engraved on the tombstone, a simple pink marble slab. On the white ceiling, several stuccoworks recall the instruments used by mathematicians and architects (the nave and the aisles of the Cathedral of Treviso were designed by Giordano Riccati): pens, rulers, pairs of compasses, set-squares. Dipartimento di Matematica Universit& di Bologna Italy

not all of these monuments to mathematical history survive today, but the

Figure 1. T h e inscription "Riccatae Gentis M" engraved on the tombstone.

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 The Mathematical Tourist Editor, lan Stewart, Universit&tAugsburg, Institut for Mathematik, D-86135 Augsburg, Germany

Figure 2. Stuccoworks on the ceiling of the Rlccati Chapel. 9 1997 SPRINGER-VERLAG NEW YORK VOLUME 19, NUMBER 2, 1997

49

The Story of a

Shopping

a 0 ~

n 1982 the University Library in Copenhagen celebrated its 500th anniversary. One of the chief librarians for the natural and medical sciences suggested that to celebrate the occasion, the various subjects in the library be presented on shopping bags from IRMA, a food store chain in the Copenhagen area. (IRMA is just an old Danish girl's

name.) The University Library arranged to decorate a series of 15 of IRMA's b r o w n paper shopping bags. I was asked to design a shopping bag with a mathematical theme. This gave me a lot to think about. I wanted to show that mathematics is not only theoretical but has something to do with grasping the world in which we live, and that a theory can result from the c o m b i n e d efforts of mathematicians in m a n y countries over a comparatively long period. This was not an easy task, but I ended up choosing Dirac's String Problem. The solution of this problem was the result of mathematicians in several countries gradually developing a full understanding. The final step was made by Ed Fadell, w h o s e w o r k I had come to admire in connection with m y research on braids, configuration spaces, and their relations to polynomial covering spaces. Briefly, Dirac's String Problem is to explain mathematically why you can untwist a double twisting of loose (or elastic) strings with fLxed ends without cutting it up, and why, on the other hand, you cannot do it with strings having only a single twisting. The problem originated in Dirac's notion of spin, which he introduced in the 1920's in connection with relativistic quantum mechanical models for the elementary particles.

50

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER-VERLAG NEW YORK

There is also an application to the problem of transferring electrical current to a rotating plate without the wires getting tangled and breaking. The application does not really need an understanding of the mathematics. But never mind, showing people that you can untwist a number of strings with a double twisting always surprises them; as a matter of fact, m a n y people don't believe it until they untwist the strings themselves. I think that the problem illustrates h o w mathematics is like a sixth sense in h u m a n beings, by which we "sense" (understand) counter-intuitive phenomena. When the bag was produced, it was the first time four colors were used on a shopping bag in Denmark. I was fortunate that some of my colleagues at the Institute of Drawing made excellent figures out of m y sketches. The bag was produced in a quantity of 200,000. I received 25 "reprints" and a small n u m b e r o f unfolded bags, which will serve as posters. From one of these posters, the present copies, in reduced size, have been made. When I am in high spirits, I say that I must be the mathematician who has had the m o s t copies published, except for Euclid. When I am in low spirits, I say that I m u s t be the mathematician whose w o r k has been placed in the m o s t wastebaskets. Presenting the shopping bag to the Rector of the Technical University of Denmark, where I am a pro-

Translation of text: front of the bag

SOME TOPOLOGICAL PUZZLES: DIRAC'S STRING PROBLEM

A bottle opener is attached to two posts (e.g., two table legs) by elastic strings (or loose strings) as shown in Figure 1 [see left]. The bottle opener is now turned one full turn as shown in Figure 1. This leads to Figure 2, where the strings are twisted. Now keep the bottle opener fixed and try to see whether it is possible to manipulate the elastic strings so that the twisting is removed. If you do not succeed it is not surprising. Mathematically it can in fact be proved that it is impossible. Now turn the bottle opener another full turn, so that altogether we have made two full turns (Figure 3). In Figure 3 everything looks a bit more

The front of the bag (figure numbers added for clarity).

Translation of text: b a c k of the bag S O L U T I O N TO: DIRAC'S STRING PROBLEM

The String Problem is not just a curiosity. It was invented by the famous English physicist P.A.M. Dirac, who was awarded the Nobel Prize in physics in 1933, to demonstrate the property half-spin of elementary particles, like neutrons. Dirac himself used a pair of scissors for the demonstration. The mathematics behind the impossibility of removing the twisting of strings in Figure 2 was almost clarified by the English mathematician M.H.A. Newman in 1942, and by that time the problem had already been known for some years. The proof uses a deep theory of mathematical braids developed by the eminent German mathematician E. Artin in the 1920's. In 1962 the American mathematician E. Fadell in a scientific paper 12 pages long presented the first complete proof. How one can manipulate the elastic strings so that the twisting of strings in Figure 3 is removed, is shown in the following series of pictures [see

exploits the principle behind the String Problem. Adams provided an ingenious solution to the problem of transferring electrical current to a rotating plate without the wires getting tangled and breaking. The principle

twisted. Again keep the bottle opener fixed and see whether the twisting can now be removed by taking the strings over and around the bottle opener. This time it is possible to do it. If you give up, the solution can be found on the other side of the bag.

is exactly that after 2 full turns one has untwisted wires as in the initial position. It should be remarked that the number of strings in Dirac's String Problem is without importance. The back of the bag.

right]. There is a technical application, patented in 1971 by the American D.A. Adams, which

VOLUME 19, NUMBER 2, 1997

51

f e s s o r of m a t h e m a t i c s , I told him, "Here y o u s e e a p i e c e of applied m a t h e m a t i c s which can actually be c a r r i e d out." It was quite entertaining to do the work. A n d it did generate s o m e i n t e r e s t - - I have had quite a few c o m m e n t s on it over the years. Since w e m a t h e m a t i c i a n s are so m o d e s t (true!), I w a s afraid that Dirac's String P r o b l e m w o u l d n o t b e enough to c o m p l e t e l y d e c o r a t e one shopping bag. In m y proposal, I therefore a d d e d a small "mathematical gem" on h o w to move a ring from o n e end of a string p a s s i n g through a hole, obviously t o o small, to the o t h e r e n d o f the string. This gem w a s used, b u t on a s e c o n d m a t h e m a t i c a l shopping bag. BIBLIOGRAPHY

E. Fadell, Homotopy groups of configuration spaces and the string problem of Dirac, Duke Math. J. 29 (1962), 231-242. V.L. Hansen, Braids and Coverings--Selected topics, London Math. Soc. Student Texts 18, Cambridge University Press, 1989. V.L. Hansen, The Magic World of Geometry--Ill. The Dirac String Problem, Elemente der Mathematik 49 (1994), 149-154.

52

THE MATHEMATICAL INTELLIGENCER

On Points Constructible from Conics

0

1. 2. 3. 4.

ne i m p o r t a n t concern o f a n c i e n t Greek m a t h e m a t i c s w a s the c o n s t r u c t i o n o f p o i n t s i n the plane u s i n g an u n m a r k e d r u l e r and compass. They were unable to decide w h e t h e r or not c e r t a i n c o n s t r u c t i o n s were possible, m o s t notably:

The duplication Trisection of an Construction of The squaring of

of the c u b e a r b i t r a r y angle the r e g u l a r seven-sided p o l y g o n the circle.

One learns in a Galois t h e o r y course h o w to c h a r a c t e r i z e algebraically points t h a t are constructible in this sense, and it follows that t h e s e f o u r p r o b l e m s are i n d e e d i m p o s s i b l e to solve. This is a beautiful a c h i e v e m e n t o f the algebraic f o r m u l a t i o n of g e o m e t r i c p r o b l e m s : the n e w m a t h e m a t i c s s t a r t e d b y Descartes and F e r m a t in the 17th century. A natural question is, What p o i n t s can be c o n s t r u c t e d if w e are a l l o w e d to d r a w conics? In antiquity, it w a s k n o w n h o w to solve p r o b l e m s 1 and 2 using p a r a b o l a s and hyperbolas. The solutions a r e given in T h e o r e m s A a n d B below, w h i c h I found m e n t i o n e d in several p l a c e s and in one b o o k as e x e r c i s e s (with solutions). There was no m e n t i o n of a solution using c o n i c s of the h e p t a g o n p r o b l e m (nor of the origin o f T h e o r e m B). This is w h a t got m e started. In this article I c h a r a c t e r i z e algebraically t h e set of p o i n t s that can be c o n s t r u c t e d from conics, a n d as a corollary p r o v e that p r o b l e m 3 can b e solved. P r o b l e m 4 is not solvable due to the t r a n s c e n d e n c e of ~-. The editor of this j o u r n a l urged me to find t h e origin of T h e o r e m B. While doing this, I found out that A r c h i m e d e s h a d solved p r o b l e m 3. His solution is remarkable.

In [3], w h i c h I consulted first, T h e o r e m B is t r a c e d to Pappus. Later, I consulted H e a t h ' s s e c o n d w o r k [4], w h i c h is a c o n d e n s e d version of [3], e x c e p t for one m a j o r addition: A r c h i m e d e s ' s solution o f the h e p t a g o n p r o b l e m (see p. 340). The G r e e k m a n u s c r i p t is lost, but the great A r a b g e o m e t e r Thabit ibn Qurra (836-911) m a d e a translation. It w a s only in the 1920s that C. S c h o y f o u n d Qurra's translation in Cairo (Heath's w o r k [3] is f r o m 1921). Let m e n o w give the n e c e s s a r y defmitions to m a k e t h e c o n c e p t of "constructible from conics" precise. The G r e e k g e o m e t e r s defined a conic s e c t i o n (or simply conic) to b e the locus o f intersection of a right circular cone with a plane. Excluding circles and lines, t h e following f o c u s - d i rectrix p r o p e r t y of conics w a s d i s c o v e r e d (it is implicit in Euclid's "Surface Loci" and explicitly s t a t e d as a proposition in P a p p u s ' s "Lemmas to the Surface Loci" [4], p. 153 and p. 266): the locus of a p o i n t w h i c h m o v e s so that its distance f r o m a fLxed point (called a focus) is in a c o n s t a n t ratio (called t h e eccentricity) to its d i s t a n c e from a fixed straight line (called a directrix) is a conic section; it is an ellipse, a p a r a b o l a or a h y p e r b o l a according as t h e given ratio is less than, equal to, or g r e a t e r t h a n unity. See Figure 1. Let S = {P1, - 9 9 , Pn} be n p o i n t s in the plane. Defme sets Sm for m = 1, 2 , . . . as follows: $1 = S, and Sm+l is the union of Sm a n d (1) the set o f p o i n t s of intersections of pairs of lines connecting distinct p o i n t s of Sm, (2) the

9 1997 SPRINGER-VERLAG NEW YORK, VOLUME 19, NUMBER 2, 1997

QI // e2 ~. . . . . ///////l /////

Q2 Q

F(///

%""

-FP - =i e PiQi

\\\~X\\x. \k\

Q3

P4I-- ....

Q4

Hence, L ( w ) = K(8, w, /3); so [L(w):K(8, w)] is at m o s t 3, b u t in any case L(w) = K(8, w)([3) with/33 E K(8, w). We have shown that if a is a r o o t of x 3 + p x + q = O, t h e n t h e r e exist fields K c K(8) C K(8, w) C K(8, w, [3) s u c h that ~2 E K, w 3 E K(8), [33 ~ K(8, w), and a E K(8, w, [3). In the terminology of T h e o r e m 2 below, the roots o f a cubic equation belong to a (2, 3 ) - t o w e r over K. The c a s e of quartic p o l y n o m i a l s is t r e a t e d in a similar way (see [2], p. 115), a n d in particular one defines a sequence of fields K C K ( a l ) C K(al, a2) C K(al, a2, a3) C K ( a l , a2, an, a4), w h e r e a l n E K a n d c~inEK(cel, . . , ai-1) f o r i = 2 , 3 , 4 , a n d n E {2, 3}; the roots of the quartic equation will belong to K(al, a2, a3, a4). So w e again have a (2, 3 ) - t o w e r over K. The G r e e k s w e r e unable to duplicate the cube a n d tris e c t any given angle, only using a ruler and c o m p a s s . However, they w e r e able to do s o in o t h e r ingenious ways: using conics and "movable" mechanisms. Plato cons t r u c t e d one such m e c h a n i s m for duplicating the cube. We will n e e d the following. .

:IGUR!

set of points o f i n t e r s e c t i o n s of lines s p e c i f i e d in (1) with circles having c e n t e r s in Sm and radii equal to s e g m e n t s having e n d p o i n t s in Sin, (3) the set o f p o i n t s o f intersections of lines s p e c i f i e d in (1) with all p a r a b o l a s , ellipses, and h y p e r b o l a s having foci in Sin, directrix lines w h i c h are lines as specified in (1), and eccentricities equal to the length of a s e g m e n t having endpoints in Sin, a n d (4) the set of points of i n t e r s e c t i o n s of pairs of conics d e f m e d in (2) and (3). Let C(S) = Om=l Sm. We call this the set of p o i n t s conicconstructible f r o m S. C o m p a r e w i t h [5], p. 216. We will only c o n c e r n ourselves with S = {P, Q}. Choose a coordinate s y s t e m in w h i c h P = (0, 0) a n d Q = (1, 0), and identify p o i n t s in the p l a n e with c o m p l e x n u m b e r s z = x § iy. F r o m n o w on, w e call a c o m p l e x n u m b e r z a conic-constructible p o i n t if z ~ C(P, Q), a n d write (~ ins t e a d of C(P, Q). Cardano's F o r m u l a s and S o m e R e s u l t s of t h e Greeks To begin, we n e e d no t h e o r y of equations m u c h b e y o n d C a r d a n o ' s f o r m u l a s in A r s Magna; see [5], p. 205. Let K be a field of c h a r a c t e r i s t i c n o t equal to 2 o r 3, a n d let f = x 3 + a2x2 + a l x + ao b e an irreducible cubic o v e r K. Let y = 1 X + ~a2. T h e n f = y3 + p y + q, w h e r e p -- a l - ~1a 22 and q = ao + -~a 3 - 1-a2a3l' Cardano s h o w e d h o w to solve y3 + p y + q = 0 and, therefore, h o w to solve x 3 + a2x2 + a l x + a0 = 0. Let L b e a splitting field of x 3 + p x + q over K. There is a 8 ~ L s u c h that 82 = A = 4p 3 - 27q 2, the discriminant o f x 3 + p x + q. Let w be a cube r o o t of unity different from 1. We k n o w that w 2 + w + 1 = 0, so p ( x ) = x 2 + x + i is the m i n i m u m polynomial o f w o v e r K, unless w ~ K. Consider the d i a g r a m of fields s h o w n in Figure 2. In the field L ( w ) , set [3 = 0/1 § WOl 2 § W2OL3 a n d 3' = a l § W2a2 + W(~3, w h e r e al, a2, and a3 are t h e t h r e e r o o t s of x3 + p x + q = O . It follows that [33 a n d 73 are the e l e m e n t s O • ~(2w + 1)8. Hence,/33 a n d 73 belong to the field K(8, w), w h i c h is an extension o f d e g r e e at m o s t 4 over K; a n d if it has degree 4 it has a subfield K(8) of degree 2 o v e r K. Note that 3~ = -3p/[3, a n d t h a t a l = 1([3 + 73), ol2 : 1(W213 § WT), and a3 = 1(w[3 + w 2 0 .

THE MATHEMATICAL INTELLIGENCER

THEOREM A (Menaechmus, - 3 5 0 B.C., t u t o r of A l e x a n d e r the Great). Given the length a, one can determine u s i n g parabolas a segment o f the length c such that c3 = a. Proof. The construction is c o n t a i n e d in H g u r e 3. The p a r a b o l a P1 has the c o n s t r u c t i b l e p o i n t (0, 41-)as focus a n d the c o n s t r u c t i b l e line y _- - ~1 as directrix. Its c a r t e s i a n equation is y = x 2. The p a r a b o l a P2 has the c o n s t r u c t i b l e p o i n t (a/4, 0) as focus a n d the c o n s t r u c t i b l e line x = - a / 4 as directfix. Its cartesian equation is x -- y2/a. The p o i n t s of i n t e r s e c t i o n are given b y solving

y4 y=xe=--

a2 ,

so y ( a 2 - y3) = 0, and so y = 0, ~aha2. Hence, the p o i n t lab e l e d Q is (a u3, a2/3). T H E O R E M B (Pappus, -- third c e n t u r y A.D.). Given a n angle AABC, one can construct a n angle whose m e a s u r e is a third o f the m e a s u r e o f AABC. Proof. The construction is contained in Hgure 4. Given points A, B, and C, draw the circle V about B with radius BA, a n d construct the h y p e r b o l a H of eccentricity 2 having focus A and directrix BC. Then, H intersects the arc of V be-

L(w)

L

K(& w)

K(8)

I

K FIGURE 2

The Algebraic Characterization P1

In this section, I characterize, in terms of field extensions, the points constructible by conics. THEOREM 1 The set C o f conic-constructible p o i n t s is the smallest subfield o f C closed u n d e r conjugation and square and cube roots. Proof. It is well known how to construct from z and z' (in fact, using only ruler and compass) z + z', zz', and z/z' if z' # 0, 5, and Vzz. Now suppose z = re i~ is given. To con-

I

( - a / 4 , 0)

o:474; :IGURE :

tween B A and B C in a point E. Let P be the foot of the perpendicular from E to BC; let Q be the midpoint of EA. By defmition of hyperbola, the segments EP, EQ, and A Q are all equal; so triangles BPE, BQE, and BQA are all congruent; therefore, angles PBE, EBQ, and QBA are all equal, providing the trisection of angle ABC. The proof also covers the case of obtuse given angle, as the reader may readily verify. By the 17th century, it was known how to solve any equation of degree 4 or less using conics, see [1], p. 155 (the reference was supplied by the referee). This follows from Theorems A and B together with the observations preceding. Since a point z = x + i y is constructible if and only if x and y are, in order to construct the heptagon it is necessary and sufficient to construct the numbers cos(2~r/7) and sin(27r/7); hence, it is enough to construct one of them, say cos(2 rr/7). If we could write down an equation of degree at most 4 with coefficients which were known to be constructible, we would be done. It is possible to write down an equation of degree 6 with integer (hence, constructible) coeff• which has cos(2~r/7) as a solution. One could try to factor this polynomial over ~ or over a quadratic extension of Q and thus solve the problem. I will not pursue this any further, but proceed to the algebraic characterization.

C

P

V

struct any one of the three cube roots of z, one has to determine a length d equal to r 1/3 and an angle a equal to 0/3. This was done by the Greeks as explained above. Now let C' be a subfield of (3 closed under conjugation and square and cube roots. I will show that points obtained by intersecting conics whose definitions involve points of C' and lengths of segments joining points of C' all belong to C'. This shows that C' ~ C. As in the classical case, if z = x + y i E C', x and y real, then x, y ~ C', and conversely. It follows that if the conic is constructed from data belonging to C', then its ecluation a x 2 + bxy + cy 2 + d x + ey + f = 0

(where a, b, c, d, e, and f are real) has its coefficients in C'. Let E ' be another conic with equation a ' x 2 + b ' x y + c'y 2 + d ' x + e ' y + f

=0

with real coefficients belonging to C' (assume E ~ E' and neither E nor E ' is a line). Then E fq E ' has at most four points. The x-coordinates (or y-coordinates, depending on the coefficients of the equations) of these points are obtained by solving these two equations simultaneously. This leads to either P(x) = 0 or Q(y) = O, where P and Q are polynomials with real coefficients belonging to C' of degree at most 4. By what we noted before, it follows that the roots of these polynomials are obtained by taking square and cube roots of elements in C'. Supposing we have determined in this way the x-coordinates of the points of intersection, say, we may determine the y-coordinates by substitution and solving a quadratic equation. Hence, if x + i y is an intersection point, it is in C'. It remains to show how one can construct the polynolnials P(x) or Q(y) mentioned above. The troublesome term is the x y term. We have three combinations to consider: (a) b = b ' = 0 Co) bb' ~ 0

(c) b = 0, b' ~ 0 (or vice versa) Case (a) is simple. Multiplying appropriately and adding both equations, one finds that the points of intersection of E and E' are given by the points of intersection of E (say) and E", where E" is a conic with equation

B A :IGUR!

a"x 2 + d ' x + e"y + f " =

0

or c"y 2 + d"x + e"y + f " = O.

VOLUME 19, NUMBER 2, 1997 5 5

By substitution, either P ( x ) = 0 or Q(y) = 0, with P a n d Q of degree at m o s t 4 a n d real coefficients in C'. Case (b) can be r e d u c e d to case (c) b y multiplying app r o p r i a t e l y (so that b' = b = 1, say) a n d subtracting. So the points o f E n E ' are the same a s t h o s e in E f3 E", w h e r e E" is a conic with no x y term. Suppose the conic E has an x y t e r m b u t t h a t E ' does not. It follows t h a t the axis o f the conic E ' is at fight angles with our (x, y ) - c o o r d i n a t e system. We can translate, using ruler and c o m p a s s , b o t h conics E -->/~ and E ' ---)E' so that the center o f E ' is at (0, 0). Note that the coefficients o f the cartesian equations of E a n d E ' still belong to C'. We distinguish t h r e e situations: I. J~' is a parabola. In this case, E ' h a s an equation of the f o r m y = a x 2 + f l o r x = 0/y2 + /3 with 0 / , / 3 E C ' n ~ . B y substitution in the equation of /~, one r e a d i l y obtains an equation P(x) =0

or

Q(y) = 0

of degree at m o s t 4, as desired. In this way, w e get ~7 r3 E ' C C', and b y translation, E r~ E ' c C'. II. ~7' is a circle o r an ellipse. In this c a s e , / ~ ' has an equation o f t h e f o r m x2/a2 + y2/~2 = 1, 0/, fl E C' n R. Suppose the equation o f / ~ is a x 2 + b x y + cy 2 + d x § ey + f = 0; writing x 2 = a2(1 - y 2 / / 3 2 ) and substituting,

s u r e K / ~ o f Q(z)/Q has d i m e n s i o n 2n3 m (m, n @ N ) OVer ~ .

Proof. S u p p o s e z is conic-constructible. By T h e o r e m 2, it is c o n t a i n e d in a (2, 3 ) - t o w e r Q(0/1, 9 9 . , al). We m a y ass u m e this (2, 3 ) - t o w e r is a Galois extension o v e r Q (see L e m m a 5, p. 255 of [5]). Hence, t h e n o r m a l closure K/Q of Q ( z ) / ~ , w h i c h is a subfield o f Q(0/1, 9 9 9, o/t), h a s dimens i o n 2n3 m over Q. Conversely, s u p p o s e the n o r m a l c l o s u r e K/Q o f Q(z)/Q has d i m e n s i o n 2s3 t over Q. The Galois group G = G a l ( K / ~ ) has o r d e r 2s3 t. By Burnside's p-q t h e o r e m (see [6], p. 240), G is solvable. Therefore, G has a c o m p o s i t i o n series G = G1 ~> G2 E> G3 "'" ~> Gk = 1 such t h a t Gi/Gi+l is o f o r d e r 2 o r 3. By t h e m a i n t h e o r e m of Galois theory, we have a s e q u e n c e o f subfields Fi of K such t h a t Q = F 1 C F2 C F3 C ... C F~ = K, w h e r e [Fi+vFi] = 2 or 3. Write F i + l = Fi(0/i). Any degree2 e x t e n s i o n is o b t a i n e d b y adjoining a square root. If t h e e x t e n s i o n Fi+JFi is of d e g r e e 3 and n o t o b t a i n e d by adj o i n i n g a cube root, t h e n t h e t o w e r at the i t h e x t e n s i o n F i C F i + l can be replaced b y a sequence Fi C L / C L~ C L'~', 0/i E L~'which is a (2, 3 ) - t o w e r as e x p l a i n e d above. Hence, z belongs to a (2, 3 ) - t o w e r over Q and so is cons t r u c t i b l e by T h e o r e m 2.

Constructible Regular Polygons aa 2 1 -

+ cy 2 + ey + f = x(-by

- d) = - x ( b y + d).

Squaring a n d substituting again gives Iaa2(1-

Y--~2)+ cy2 + ey

THEOREM 4. The regular n - s i d e d polygon is conic-con-

§

as desired. III./~' is a hyperbola, with equation x2/Ol2 is t r e a t e d as above.

structible i f and only i f n = 2S3tP3 ...pi ""Pk, w h e r e s,

--

y2/~2 = 1. This

The following is a useful criterion to find out w h e n a point z is conic-constructible. THEOREM 2. L e t z E C be given. Then z i s conic-constructible i f a n d o n l y i f z is contained i n a subfield o f hE,and C o f the f o r m ~(0/1, a2, 9 9 9 , 0/1), w h e r e 0/1 0/iIt E Q(0/1, 9 9 9 0/i-1) f o r 2 <- i < I a n d n ~ {2, 3}. Call such a f i e l d a (2, 3 ) - t o w e r over Q. Proof. Let C' b e the set of c o m p l e x n u m b e r s c o n t a i n e d in a (2, 3 ) - t o w e r o v e r ~ . Because C is c l o s e d u n d e r square and cube roots, w e get C ~ C'. F o r t h e o t h e r inclusion, note that C' is a subfield of C c l o s e d u n d e r square and cube roots. Since Q(0/1, 9 9 9, 0/I) = Q(-~I, 9 9 9, ~/), it follows that C' is c l o s e d u n d e r conjugation.

The n e x t result is the m a i n point. THEOREM 3. A c o m p l e x n u m b e r z is conic-constructible

i f and only i f z is algebraic over Q a n d the n o r m a l clo-

156

THE MATHEMATICALINTELLIGENCER

Next let us find out w h i c h regular polygons are constructible.

2, 3; Pi ~ Py, 3 <- i, j <- k; a n d the p r i m e f a c tors o f pi - 1 are 2 or 3. Proof: F o l l o w i n g G a u s s , o n e h a s t o c o n s t r u c t t h e n u m b e r z = e 2~'~/n. L e t F ~ b e t h e c y c l o t o m i c f i e l d o f n t h r o o t s o f unity. Fn/Q is G a l o i s a n d h a s d e g r e e ~ ( n ) . I f n = 2s3 t p~3 "'" P kek, S --> 1, t --> 1, t h e n r = 2s3 t - lp33- 1 ( p 3 -- 1) ... t >~ 0, p i r

SpringerNewsMathematics

2 or 3 as its prime divisors.

Hans Hahn Gesammelte Abhandlungen / Collected Works

COROLLARY. T h e 7 - g o n is c o n i c - c o n s t r u c t i b l e .

L. S c h m e t t e r e r ,

Pk k - 1 . (Pk -- 1). I f t = 0 o r s = 0, o n e o b t a i n s a s i m i l a r f o r m u l a ; s o ei = 1 ( i = 3 , . . . ,

k), a n d P i - 1 m u s t o n l y h a v e

Like Descartes and Pascal, Hans Hahn (1879-1934) was both an eminent mathematician and a highly influential philosopher. He founded the Vienna Circle and was the teacher of both Kurt G6del and Karl Popper. His senfinal contributions to functional analysis and general topology had a huge impact on the development of m o d e m analysis. Hahn's passionate interest in the foundations of mathematics, vividly described in Sir Karl Popper's foreword (which became his last essay) had a decisive influ-. ence upon Kurt G6del. Like Freud, Musil or Sch6nberg, Hahn became a pivotal figure in the feverish intellectual climate of Vienna between the two wars.

Proof. 0 ( 7 ) = 6 = 2 9 3. R e m a r k s . It t u r n s o u t t h a t e l l i p s e s a r e s u p e r f l u o u s i n t h e construction of new points. Can one get by using only lines, circles, and hyperbolas? Conics are curves of genus zero. What points do we get i f w e a r e a l s o a l l o w e d t o d r a w c u r v e s o f g e n u s 1, i.e., c u bics? REFERENCES

1. L. Bieberbach, Theorie der Geometrischen Konstruktionen, Birkh~user, Bern, 1952. 2. D.J.H. Garling, A Course in Galois Theory, Cambridge University Press, Cambridge, 1986. 3. T.L. Heath, A History of Greek Mathematics, Oxford University Press, Oxford, 1960. 4. T.L. Heath, A Manual of Greek Mathematics, Dover Publications, New York, 1963. 5. N. Jacobson, Basic Algebra I, W.H. Freeman & Co., New York, 1985. 6. D. Robinson, A Course in the Theory of Groups, Springer-Verlag, New York, 1982.

Now complete: Bd. 3 ! Vol. 3: 1997. XIII, 581 pages. Cloth, US $142.O0.ISBN 3-211-82781-1 In the third volume, Hahn's writings on harmonic analysis, measure and integration, complex analysis and philosophy are collected and commented on by Jean-Pierre Kahane, Heinz Bauer, Ludger Kaup, and Christian Thiel. This volume also contains excerpts of Hahn's letters and accounts by students and colleagues.

Bd. 2 / Vol. 2: 1996. XIII, 545 pages. Cloth, US $130.0O.ISBN 3-211-82750-1 The second volume of Hahn's Collected Works deals with fimctional analysis, real analysis and hydrodynamics. The conunentaries are written by Wilhelm Frank, Davis Preiss, and Alfred Kluwick.

MOVING? We need your New address

K. S i g m m l d ( H r s g J e d s )

so that you do not miss

any issues of

Bd. 1 / Vol. 1: 1995. XII, 511 pages. Cloth, US $130.00.ISBN 3-211-82682-3

THE MATHEMATICAL INTELLIGENCER.

The first volume contains Hahn's ground-breaking contributions to functional analysis, the theory of curves, and ordered groups. Commentary by Harro Heuser, Hans Sagen, and Laszlo Fuchs.

P l e a s e fill o u t t h e f o r m b e l o w a n d s e n d it to:

S p r i n g e r - V e r l a g N e w York, I n c . Journal Fulfillment Services P.O. Box 2485, S e c a u c u s , NJ 07096-2485

To Order: Call 1-800-SPRINGER (8:30 AM - 5:30 PM ET) or Fax: 201-3484505. By Mail: Springer-Verlag New York, Inc., P.O. Box 2485, Secaucus, NJ 07096-2485. Please include $3.00 for shipping one book, $1.00 for each additional. (Residents of CA, IL, MA, NJ, NY, PA, TX, VA, or VT, add sales tax. Canadian residents add 7% GST.) Payment may be made by check, purchase order, or major credit card.

Name Old

Address (or label)

Address City/State/Zip

Name New

Address

Address City/State/Zip

Please give us six weeks notice.

~

SpringerWienNewYork Sachsenplatz 4-6, P.O. Box 89, A-1201 Wien New York, NY 10010, 175 Fifth Avenue Heidelberger Platz 3, D-14197 Berlin Tokyo 113, 3-13, Hongo 3-chome, Bunkyo-ku

VOLUME 19, NUMBER2, 1997 5 7

How to Do and Write Math

R e e-& rch ~

f

~

any experienced researchers could write a better article on the topic. But they didn't write this, so I did. This advice is ,for the newcomer, the beginner, who may have cried in the night, "How the beck do you do math research, anyhow?"

I deal separately with two topics. How do you do it? How do you write it? How Do You Do Research? Where do you get the idea? Or, as it's often put, where do you fend your problems? There are several places, some worse than others. Let us assume you already have an "adviser" and a "field" or "area," and your adviser has already told you that this year's hot problem in your area is say "the Uniqueness Problem." Maybe your thesis was a partial s o l u t i o n - uniqueness subject to Condition A. Your first publication! What next? 1. One popular strategy is, chip away at Condition A. In your next paper, weaken it to Condition A'. And then condition A" for the paper after that. You'll quite possibly become known as an expert on weakening Condition A. 2. Another idea is to keep your eye on the Uniqueness Problem itself. Half a dozen other hot shots and sharpies like you are already in the race. Keep up with them by email or face to face. See how to strengthen X's new trick by simply terming his metric and then bringing in Y's old trick from last year. Write it up fast, to get it out before Z.

58

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER-VERLAG NEW YORK

If you have speed and stamina, you may become known as one of the active young generation working on the Uniqueness Problem. 3. There are still other ways to go. You may struggle to remedy the deficiencies in your education, which you only now recognize. You may start to look at journals outside your field. If you behave in this non-standard way, you will occasionally spot an anomaly. A curious parallel between seemingly unrelated results, or an unnoticed, unexploited regularity. Figure out what's going on. You'll end up with a publication, even several publications. You may then notice a crowd of eager youngsters peeking over your shoulder, looking for generalizations and specializations and extensions of your idea. 4. Generalization. A much-traveled high road to publication. Professor Q has a result on LP-spaces. Generalize it to abstract Banach space. Then again, to Fr6chet spaces. Then perhaps still again, even to Hausdorff spaces. Three solid papers in just one month. If you had been thoughtless, you could have done Hausdorff in the first place. But that would have been only one paper. I warn y o u - - t h i s is not the way to go! You'll acquire a life-long reputation as a trifler and nose-picker.

Before you generalize, ask two questions. Does the generalization include at least one interesting special case that wasn't already covered? Does proving the generalization require a new idea, not standard in the generalized context? If the answer to both is No, keep it for a dissertation problem for your first marginal, weak student. 5. Specialization is underrated as a research tactic. If Professor Y has a nice theorem on Banach space, does bringing it down to Lp yield some surprising concrete formulas, or some unexpected connection with probability or p.d.e.? Of these five roads, linking hitherto unrelated fields or methods or results is the one most apt to be a winner. It does require you to k n o w a little about two different areas. If you like to hide in y o u r office till your proofs are all complete and then astonish your colleagues, you're at a serious disadvantage. Talking to others can be helpful. It may be hard to find anybody who'll listen. One w a y is to find s o m e b o d y else who's also looking for s o m e b o d y to listen. She listens about your sub-von Neumannian hyper-loops, you listen about her semi-Markovian submartingales.

Writing It Your first big decision is: are you writing to be understood, or to not be understood? In a letter to Florimond De Beaune, Ren~ Descartes wrote, on February 20, 1639, " . . . in the case of the tangents, I have only given a simple example of analysis, taken indeed from a rather difficult aspect and I have left out m a n y of the things which could have been added so as to make the practice of the analysis more easy. I can assure you, nevertheless, that I have omitted all that quite deliberately, except in the case of the asymptote, which I forgot. But I felt sure that certain people, who boast that they k n o w everything, would not miss the chance of saying that they knew already what I had written, if I had m a d e myserf easily intelligible to them. I should not then have had the pleasure, which I have since enjoyed, of noting the irrelevance of their objections." Some mathematicians write so as not to be understood, without consciously recognizing that as their goal. Sleepwalking has its advantages. But since you're reading this paper, I presume you want to know what you're doing. Some tips on h o w not to be understood, gleaned from the recent literature. 1) Don't explain w h y you're doing what you're doing, bey o n d a cryptic remark like "The Uniqueness Problem is related to the construction and classification problems for sub-yon Neumannian hyper-loops." 2) Don't explain in any meaningful way what has already been done. Do give r e f e r e n c e s - - a t least 30, mostly in French. 3) Avoid natural language. Anything that can be said in English can be said in symbols, if you make an honest effort. 4) Don't repeat anything already stated in any of y o u r references. Not many readers will track them d o w n in the library, especially if your references aren't in the library.

5) Use m a n y different type faces. Gothic is good. But double and triple subscripts may be rejected by the printer. 6) Write "it's easy to see" and "a short calculation shows" and "it follows immediately" and "by a well-known argument of Nicomachus" as often as y o u dare. So m u c h for that. What if y o u want to be understood? Writing to be understood is more trouble than writing not to be understood. Over y o u r lifetime, it will cut down your "productivity." There's a popular belief that understandable writing is bad for your reputation. "If I can understand it, it must be trivial." Don't be intimidated by this belief. Defy it. Mathematicians are grateful to mathematicians w h o write understandably. They are understandably more likely to read understandable papers. Writing understandably means, of course, not following the practices recommended above for being not understood. A good w a y to write an understandable paper is to have one central idea. State it at the beginning. Carry it out in successive stages. Point out as you go that you're carrying out the central idea you stated at the beginning. Your w o r k may not have such a unified, coherent character. Maybe you did several interrelated things, all relevant to the Uniqueness Problem. Then make a clear separation of your paper into parts, each o f which is unified. In the introduction, explain why you have organized the paper as you have. Where different sections of the paper are connected, discuss the connection in both places. Taking up a few lines of print to save your reader a few minutes of trouble is legitimate.

If y o u w a n t to o m i t an argument o r a calculation, give a short outline of w h a t y o u ' r e omitting, so t h a t an intere s t e d r e a d e r really h a s a c h a n c e to fill it in. Use the highest s t a n d a r d s of c o m p o s i t i o n of which you are capable. Never a p r o n o u n w h o s e r e f e r e n c e is fuzzy in the slightest. Short w o r d s rather than long. Concrete nouns and verbs rather t h a n abstract. Active voice r a t h e r than passive. Short, g r a m m a t i c a l sentences. Paragraphing according to the flow of ideas. Be consistent in using the p a s t tense o r the present, in having as a subject "you" o r "we" or "one." If you use a foreign word, do tell us w h a t it means. When y o u ' r e fmished, p u t your p a p e r a w a y for a week. Reread it. In each sentence, l o o k for u n n e c e s s a r y words. Cross t h e m out.

60

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER VERLAG NEWYORK

In each paragraph, l o o k for u n n e c e s s a r y sentences. Cross t h e m out. L o o k especially for u n e x p l a i n e d t e r m s and c o n c e p t s . E x p l a i n them. Put y o u r p a p e r away for a n o t h e r week. R e r e a d it. Correct it again. Continue putting it a w a y for a week, rereading it a n d c o r r e c t i n g it, until it is perfect. You've done y o u r duty. S e n d it in. E x p e c t complaints and r e q u e s t s for m o r e changes. REFERENCE Descartes, R. Oeuvres, ed. C. Adam and P. Tannery, 12 vols., Paris, L. Cert, 1897-1910, ii 511, 18-20; Corr. III, 185

If y o u w a n t to o m i t an argument o r a calculation, give a short outline of w h a t y o u ' r e omitting, so t h a t an intere s t e d r e a d e r really h a s a c h a n c e to fill it in. Use the highest s t a n d a r d s of c o m p o s i t i o n of which you are capable. Never a p r o n o u n w h o s e r e f e r e n c e is fuzzy in the slightest. Short w o r d s rather than long. Concrete nouns and verbs rather t h a n abstract. Active voice r a t h e r than passive. Short, g r a m m a t i c a l sentences. Paragraphing according to the flow of ideas. Be consistent in using the p a s t tense o r the present, in having as a subject "you" o r "we" or "one." If you use a foreign word, do tell us w h a t it means. When y o u ' r e fmished, p u t your p a p e r a w a y for a week. Reread it. In each sentence, l o o k for u n n e c e s s a r y words. Cross t h e m out.

60

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER VERLAG NEWYORK

In each paragraph, l o o k for u n n e c e s s a r y sentences. Cross t h e m out. L o o k especially for u n e x p l a i n e d t e r m s and c o n c e p t s . E x p l a i n them. Put y o u r p a p e r away for a n o t h e r week. R e r e a d it. Correct it again. Continue putting it a w a y for a week, rereading it a n d c o r r e c t i n g it, until it is perfect. You've done y o u r duty. S e n d it in. E x p e c t complaints and r e q u e s t s for m o r e changes. REFERENCE Descartes, R. Oeuvres, ed. C. Adam and P. Tannery, 12 vols., Paris, L. Cert, 1897-1910, ii 511, 18-20; Corr. III, 185

Ih'd[~-:U~-m'_'~4[.~- J e r e m y

Gray

KGnig r

Hadamard and KUrsch,k, and Abstract Algebra

Column Editor's address: Faculty of Mathematics, The Open University, Milton Keynes, MK7 6AA, England

I

The

Hungarian mathematician Gyula (Julius) KGnig is a forgotten man of algebraic geometry, yet he contributed significantly to it by writing

his Einleitung in die aUgemeine Theorie der algebraischen Gr6ssen [1903], published simultaneously in German and Hungarian. There is a passing reference to it in van der Waerden's essay [1971] which is not entirely accurate. It runs, in its entirety, as follows: "Elimination theory was developed by Kronecker and his school." But KSnig spent his working life in Budapest, having studied at Vienna and Heidelberg. He claimed no personal acquaintance with Kronecker or reliance on correspondence or letters. Rather, he seems to have set himself the task, as he turned 50, of writing a useful b o o k sorting out an important topic for which no guide existed. He found much to criticise. The original papers were very hard to read and remained restricted to a small circle of readers. They had therefore, he said, failed in their principal purpose, and so he had set himself the task of popularising the spirit of Kronecker's method. He succeeded, drawing others into the field w h o went on to discover better results, simpler and more general methods; and then, with the rise of E m m y Noether's school after the First World War, his book was covered up and forgotten. KSnig and his work are vividly described in Sz6nfissy [1992], w h o calls KGnig "a great man of the nation" (p. 333) and credits him with establishing Hungarian mathematics as a significant force. This he did as m u c h by his own w o r k as by his magnetic personality and the breadth of his organisational work: training teachers and engineers as well as professional mathematicians, lecturing on everything from pure analysis to e c o n o m i c s and history of mathematics. Sz6nfissy writes (p. 241) that Hungarian "secondary school education benefited for

decades from his textbook on algebra." KSnig helped found the Hungarian Mathematical Society, worked with publishers, and w a s three times Rector of the Technical University. In research, it w a s his habit to work on one area of mathematics at a time, publish several papers and then a monograph summarising the field, and then move on. He worked on algebra, then analysis and partial differential equations, and, finally, on Cantorian set theory, w h e r e he is better remembered for his unsuccessful atteznpt on Cantor's continuum hypothesis than for several smaller but secure contributions (see Moore [1982]). Sz~nfissy's discussion of KSnig's Einleitung is rather brief. In fact, the b o o k possesses two aspects of interest. One is the novel mathematical concepts it introduces; the other is the insights of a sharp critic of the period. From the standpoint of the early history of field theory, KSnig's book introduced some useful terminology and made some interesting distinctions. He based his a c c o u n t on the twin concepts of an orthoid domain and a holoid domain. These correspond exactly to our c o n c e p t s of a field (of characteristic 0) and a (commutative) ring with a unit 1 such that no sum of the form 1 § 1 + ... § 1 vanishes; Sz~nhssy incorrectly glosses a holoid domain as an integral domain.

Fields and Kronecker's Domains of Rationality As KGnig saw it, a field (called aKGrper by Dedekind) is an orthoid domain (a certain vagueness in Dedekind's definitions and certain methodological differences, aside). He advocated the terms orthoid and holoid because, in this branch of mathematics at least, they are naturally juxtaposed. But a field or orthoid domain is not the same concept as Kronecker's domain of rationality. K6nig argued first that Kronecker's

9 1997 SPRINGER-VERLAG NEW YORK, VOLUME 19, NUMBER 2, 1997

61

equation with coefficients in the natural d o m a i n of rationality D. In particular, this is true of the quantities o~n, so D and the domain o f rationality (Xl, , Xm, w], . . . , o~) coincide.] The smallest n u m b e r n of e l e m e n t s wi, is t h e r e f o r e the o r d e r of the d o m a i n of rationality thought o f a s an algebraic e x t e n s i o n of its underlying n a t u r a l dom a i n of rationality. The e l e m e n t s 01, , o)n themselves f o r m a basis for the d o m a i n o f rationality. But an ort h o i d d o m a i n is not n e c e s s a r i l y a dom a i n of rationality. F o r e x a m p l e , the d o m a i n of all algebraic n u m b e r s is an o r t h o i d d o m a i n that is n o t a d o m a i n of rationality. The d o m a i n s of real and of c o m p l e x n u m b e r s are l i k e w i s e o r t h o i d b u t not, K6nig s e e m s to suggest, dom a i n s o f rationality. Wl,

Gyula K6nig natural d o m a i n s w e r e o b t a i n e d by taking any finite set o f / z e l e m e n t s from any holoid or o r t h o i d domain, and forming the function field in t h e m (so nontrivial relations can exist among these generators). This gave an orthoid d o m a i n that, he said, K r o n e c k e r called a d o m a i n of rationality. It might be that j u s t one e l e m e n t w a s chosen, and it w a s equal to 1, in w h i c h c a s e the absolute d o m a i n o f rationality w a s obtained, which he d e n o t e d (1) (and w e denote by Q, the rational numbers). If the /z quantities w e r e c o m p l e t e l y undetermined, the resulting domain w a s the natural d o m a i n of rationality i n / z indeterminates, w r i t t e n (xl, x2, 9 9 9, x~), which w e w o u l d write ~ ( x l , x2, 9 . ., x~). It follows t h a t every domain of rationality is an algebraic extension of a natural d o m a i n of rationality. [Proof. Pick x. F o r m p o l y n o m i a l s in x with at least one n o n z e r o coefficient. Either none vanish o r one at least does. In the first case, the d o m a i n of rationality is (x), i.e., Q(x). In the s e c o n d case, x is an algebraic n u m b e r and (x), i.e., Q(x), is an algebraic extension. The p r o o f for a n y n u m b e r of e l e m e n t s x follows by induction.] Conversely, if all the elements of an orthoid domain can be written in the form r l (ol + "'" + rn (an, where the ri belong to a natural d o m a i n of rationality D = (Xl, 9 9 9 Xm), then the orthoid domain is a d o m a i n of rationality. [Proof: First, s h o w every w in the orthoid domain satisfies a polynomial

6 ~l

THE MATHEMATICALtNTELLIGENCER

9

9

9

9

.

.

9

9

Kronecker's Fundamental Theorem K(inig w a s particularly p l e a s e d to offer an e l e m e n t a r y p r o o f o f K r o n e c k e r ' s F u n d a m e n t a l Theorem. This is the result K r o n e c k e r p r o v e d after so m u c h effort in 1883, and w h i c h H.M. E d w a r d s rightly says r e m a i n s o b s c u r e ([1990], p. 10). It had b e e n given a n e w p r o o f b y the F r e n c h m a t h e m a t i c i a n J u l e s Molk, who h a d s t u d i e d u n d e r K r o n e c k e r in Berlin in 1882-1884. On his r e t u r n to Paris, he t o o k his D o c t o r a t ~s S c i e n c e s at the S o r b o n n e in 1884; the t h e s i s w a s later published, lightly revised, in A c t a M a t h e m a t i c a (Molk [1885]). It is a summary, with a few simplifications, of K r o n e c k e r ' s ideas, c o u p l e d with strongly w o r d e d claims for its merits. K~inig i n t r o d u c e d it for t w o polynomials in one variable: f ( x ) = Z ai x m - i a n d g ( x ) = E b i x n-~, w h o s e p r o d u c t is f ( x ) g ( x ) = ~ Cixm+n-i. The t h e o r e m claims that there are identities connecting the p r o d u c t s a i b j a n d the hom o g e n e o u s linear e x p r e s s i o n s in the ck. Similarly, in general, t h e r e are identities connecting the p r o d u c t s of the coefficients of any n u m b e r o f polynomials a n d the coefficients o f the product. KSnig w e n t on to offer a truly elem e n t a r y (and for that matter, simple) p r o o f o f this result 9 He t h e n e x p l a i n e d j u s t w h y it is so significant. What Kronecker, Molk, a n d K6nig proved, in their different ways, is that

the m o d u l a r s y s t e m g e n e r a t e d by t h e p r o d u c t s a i b j a n d the Ck are equivalent, in an e x t e n d e d sense of the t e r m d u e to Kronecker. To explain it, let t h e m o d u l e g e n e r a t e d b y the p r o d u c t s a i b j be d e n o t e d AB, and that g e n e r a t e d b y the Ck b e d e n o t e d C. Then, certainly, C is divisible b y AB. Conversely, e v e r y aibj is the r o o t of a p o l y n o m i a l equation v m + g l v m - 1 + ... g m = 0 w h o s e coefficients a r e divisible by s u c c e s s i v e p o w e r s of C (gi by Ci). K r o n e c k e r called s u c h a function v divisible b y C in an e x t e n d e d sense. L a n d s b e r g p o i n t e d out in 1899 ([1899], p. 313) t h a t Hilbert's Nullstellensatz s h o w s t h a t t h e c o n c e p t s o f equivalence for s y s t e m s o f equations a n d for the c o r r e s p o n d i n g m o d u l a r s y s t e m s are not e x a c t l y the. same. This p r o b l e m h a d a l r e a d y b e e n s p o t t e d a n d dealt with by Kronecker, in e x a c t l y t h e t h e o r e m w e are discussing w h i c h p r o c l a i m e d the equivalence of t h e m o d u l a r systems A B a n d C in this sense 9 The G e n e r a l i s e d N o e t h e r Theorem and the Nullstellensatz KSnig's b o o k is at its m o s t g e o m e t r i c a l in C h a p t e r 7 (Linear Diophantine p r o b lems, g e n e r a l t h e o r e m s and a l g e b r a i c theory). He p o s e d the situation this way. Given a (possibly strict) h o l o i d d o m a i n A, a n d a form d o m a i n o v e r it [A, x l , . 9 . , Xm], l e t F i j ( i = 1 , . . . , k , j = O , . . . , l) be forms in that domain. The p r o b l e m is to find forms X1, 9 9 9 Xi in the given d o m a i n so that t h e following k linear Diophantine equations in the I u n k n o w n s are satisfied: FiiX1 + Fi~2

+ "" + F~IX~ = F~o

(i = 1,..

9, k).

Two c a s e s h a d to be distinguished: w h e n A is orthoid, a n d w h e n A is the integers ( c o r r e s p o n d i n g to an algebraic a n d an arithmetic formulation o f the problem) 9 This d o e s not s o u n d remotely geometrical; rather, it is a ref m e m e n t o f the general thrust o f the book, w h i c h is elimination theory. The turn to g e o m e t r y c a m e 40 p a g e s into the Chapter, in w "The g e n e r a l i s e d N o e t h e r Theorem": the first time the t h e o r e m w a s p r o v e d for k > 2 functions in k variables. The t h e o r e m applied to such situations as this. Let Fi, 1 -< i --- 3, be t h r e e

polynomials in three variables x, y, and z. Assume that the equations Fi = 0 each separately defme an algebraic surface in 3-space, and that these surfaces meet in a fmite set of points (~lj, ~j, ~3j), 1 -< j -< r. Necessary and sufficient conditions for a given polynomial dp in x, y, and z to belong to the divisor system defined by the Fi were then given in terms of the existence of forms Hij such that (I) - Z~k H ijFi vanishes to suitable orders at the points (~tj, ~2j, ~j)- K6nig then observed that the necessary condition for an arbitrary form CA = ~ to belong to a modular system (F1, F2, 9 . 9 Fk) is that dp vanishes at the c o m m o n zeros of the Fi, but that this is not sufficient. Instead, as Hilbert had shown, if qb vanishes at those points, then some p o w e r of it belongs to the modular system. This is Hilbert's Nullstellensatz. K6nig then s h o w e d how to replace Hilbert's "rather complicated" p r o o f and establish the theorem as a simple corollary of the elimination theory developed in this book. It is striking h o w little geometry there is in the book; the geometrical terminology is confined to a footnote. Kiics9 and bladamacd K6nig's w o r k seems to have achieved its goal of making Kronecker's w o r k m o r e accessible. In particular it was adopted by the English mathematician F.S. Macaulay in his b o o k published in 1916 (and again recently). He was led to read it by a conversation with Brill and Noether at the International Congress of Mathematicians in Heidelberg in 1904, at which he had presented a paper. Another person w h o took it up was the Hungarian mathematician J6zsef Ktirschfik. He w a s educated in Budapest, organised seminars with K6nig, and helped him during the writing of his Einleitung. He also shared something of his mentor's breadth of interests and his influence: there is a prize competition n a m e d after him for school leavers in mathematics and physics. In the early 1890s, he came into contact with Hadamard because of his study of the relation between the simple pole of a p o w e r series and its coefficients. This w a s an influence on Hadamard's deci-

sion to investigate what conditions on a p o w e r series yield particular types of singularity. Jules Molk then encouraged them to expand on Landsberg's article in the Encydopddie der Mathematischen Wissenschaften when he came to organise the French version of the Encyclopddie (of which Molk was editor-in-chief). The result is a m u c h larger article than the German original (Hadamard and Kiirschgtk [19101911]), and its comments provide an interesting view of h o w all this material was regarded in 1910-1911. It is not clear, however, what impact this article had; references to it are hard to find. Let us take it, then, as a snapshot of the times. The first part was published on 30 August 1910. The title is interesting in itself: "General properties of fields and algebraic varieties." Landsberg's had been "IBlc Algebraic varieties. IC5 Arithmetic theory of algebraic quantities" (so it is clear that the editors had not been sure where to place it). Generally speaking, Hadamard and Kiirschgtk kept Kronecker's a p p r o a c h at a distance, setting off material specifically of that nature in square b r a c k e t s [ . . . ] . They reviewed the proliferating terminology carefully: The term "known quantities" had given w a y to Dedekind's "field," which was the same thing as K6nig's orthoid domain. Kronecker's domain of rationality was also a field--more precisely, a fmite or algebraic extension of the rationals (the terms "f'ntite" and "algebraic" were regarded as s y n o n y m s by Hadamard and Ktirsch~k). There were two types of field, number fields and function fields, but every field contained the field of rational numbers, which they denoted R. Hadamard and Ktirschs regarded the simplest function field as the function field in n variables, which they denoted indifferently R. The coefficients were to be unrestricted numerically, which m e a n s complex numbers. If the coefficients were restricted in any way, say to be rational, they wrote the field RR. They admitted this was back-to-front from Kronecker's approach. What they called finite or algebraic fields in the strict sense of the w o r d were simple algebraic extensions of R,

R~, or R, which Kronecker had called derived domains of rationality, reserving the term "natural" for just the fields R, RR, or R. They also presented the concept of a field in purely formal terms (analogous to that of a group, they said). A commutative group is a field, they said, w h e n it also admits an associative multiplication with a multiplicative identity that is not a divisor of zero, and when every element that is not a divisor of zero has a unique multiplicative inverse. Weber's defmition was more restrictive, they observed: the multiplication must be commutative, and there are no zero divisors. K6nig's orthoid domains satisfied all these conditions and were of characteristic 0. What he called a hyperorthoid domain dropped the condition about divisors of 0; for example, the domain {a + bx: a, b E C, x 2 = 0}. K6nig called a domain pseudo-orthoid if it had no divisors of 0, but was not of characteristic 0. They arose, for example, by taking numbers modulo a prime. So, pseudoorthoid domains were also fields in Weber's sense of the term. Hadamard and Ktirsh~tk settled on the definition of field that agreed with K6nig's orthoid domain. A holoid domain satisfies all the defining conditions of an orthoid domain except those relating to division. From a holoid domain, one can always form an orthoid d o m a i n - - i t s field of fractions. The algebraic integers form a holoid domain. The algebraic integers in a field K likewise form a holoid domain, as do subdomains generated over the rational integers by a fmite set of algebraic integers. Such domains were called Art or Species by Kronecker, Ordnung by Dedekind, and rings or integral domains by Hilbert. In the s e c o n d fascicule published on 15 February 1911, the authors plunged into the theory of modular systems: Hilbert's invariant theory and Kronecker's Fundamental Theorem. Hadamard and Ktirschgtk showed that Hilbert's NullsteUensatz implies Noether's Fundamental Theorem (the AF § BG Theorem). Significantly, by n o w they had had time to take on board Steinitz's "Algebraische Theorie der K6rper," published in 1910. It is

VOLUME 19, NUMBER 2, 1997

clear from the clarity of the exposition and the new generality of expression just why Steinitz's paper had the foundational effect that it did. Several factors then conspired to make the contribution of K6nig disappear, of which one might well be that Emmy Noether may have found it uncongenial. Its emphasis on explicit methods, exemplified by Macaulay's tract, certainly runs counter to her taste for abstract methods. But another reason might be that, in the ceaseless struggle for the soul of algebraic geometry, algebra may bring rigour but it makes few friends.

Hadamard, J. and KLirschhk, J. (1910-1911). Propri~tes generales des corps et des variet6s algebriques, Encycl. Sci. Math. pures Appl. 1(2), 235-385.

Moore, G.H. (1982). Zermelo's Axiom of Choice, New York: Springer-Verlag.

K6nig, G. (1903). Einleitung in die allgemeine

Steinitz, E. (1910). Algebraische Theorie der

Theorie der algebraischen Grdssen, Leipzig: Teubner.

K6rper, J. for Reine u. Angew. Math. 137; reprinted in Steinitz (1930).

Kronecker, L. (1882). GrundzOge einer arithmetischen Theorie der algebraischen Gr6ssen, J. for Reine u. Angew. Math. 92, 1-122.

Steinitz, E. (1930). Algebraische Theorie der Kdrper (R. Baer and H. Hasse, eds.), Leipzig: Walter de Gruyter.

Kronecker, L. (1883). Zur Theorie der Formen h6herer Stufen, Monatsberichte Akad. Wiss. Berlin, 957-960.

Sz6nhssy, B. (1992). History of Mathematics in Hungary until the 20th Century, New York: Springer-Verlag.

Landsberg, G. (1899). IBlc. Algebraische Gebilde. IC5 Arithmetische Theorie algebraischer

van der Waerden, B.L. (1971). The foundation of algebraic geometry from Severi to Andr6 Weil, Arch. History Exact Sci. 7(3), 171-180;

GrOssen, Encycl. Math. Wissensch. 1 284-319. BIBLIOGRAPHY

Edwards, H.M. (1990) Divisor Theory. Boston: Birkh&user.

Through

a Reporter'sEyes -

THE LIFE OF STEFAN BANACH Roman Kaluza t Translated and Edited by A. Kostant & W.Woyczynski, Case Western Reserve University 1995 marked the 50th anniversary of Stefan Banach's death, but until now, the general English speaking public has had no access to an in-depth life story of a mathematician whose name is one of those most often encountered in modern mathematical research. This small volume, originally written in Polish by a well known reporter, is an effort to fill the gap in the biographical literature. It is based on original archival sources, dozens of interviews with people who knew and remember Banach, and conversations with mathematicians who are familiar with Banach's work and its impact on modern mathematics. The author presents engaging descriptions of Banach's personality and the unusual milieu in which he worked.

1996 137pp.,24illus. Harclcover $24.50 ISBN0-8176-3772-9

Birkh

user

Boston * Basel * Berlin

THEMATHEMATICALINTELLIGENCER

Molk, J. (1885). Sur une notion qui comprend celle de la divisibilite, Acta Math. 6, 1-166.

Macaulay, F.S. (1916). Algebraic Theory of Modular Systems, Cambridge: Cambridge University Press.

reprinted in van der Waerden (1983), 1-10. van der Waerden, B.L. (1983) Zur algebrais: chen Geometrie, New York: Springer-Verlag.

EVARISTE GALOIS (1811-1832)

THE MATHEMATICAL EXPERIENCE

Laura Toti Rigatelli, University of Siena Translated from the Italian by John Denton

Study Edition RJ. Davis, Brown University; R. Hersh, University of New Mexico & E.A. Marchisotto, California State University, Northridge

Evariste Galois' short life was lived against the turbulent background of the restoration of the Bourbons to the throne of France, the 1830 revolution in Paris, and the accession of Louis-Philippe. This new and scrupulously researched biography of the founder of modern algebra sheds much light on a life led with great intensity and a death met tragically under dark circumstances. Sorting speculation from documented fact, it offers the fullest and most exacting account ever written of Galois' life and work.

"...aperfectly marvelous book about the Queen of Sciences, 3s which o n e will get a realfeelingfor what mathematicians do and who they are. The exposition is clear andfull of wit and humor... " - - The New Yorker (1984 American Book Award Edition)

1995 487pp. Hardcover $38.50 15BN0-8176-3739-7

It took more than seventy years to fully understand the French mathematicians' first memoir which formulated the famous "Galois Theory" concerning the solvability of algebraic equations by radicals, from which group theory would follow.

Also Available by PJ. Davis, R, Hersh & E.A. Marchisotto - THE COMPANION GUIDE co The Mathematical Experience

1996 150 pp. Hardcover $29.50 ISBN 0-8176-5410-0

1996 128pp.,21illus. 5of~cover$14.95 ISBN0-8176-3849-0

Series:VitaMathemadea.VolumeI I

I1=,~,,[~,,,~--~ J e t W i m p ,

Editor

I

Nature's Numbers by Ian Stewart LONDON: WEIDENFELD & NICOLSON, 1995. X + 164 PP. HARDCOVER: s

ISBN 0-297-81642-X.

REVIEWED BY FREEMAN DYSON ~

Feel like writing a review for The Mathematical Intelligencer? You are welcome to submit an unsolicited review of a book of your choice; or, if you would welcome being assigned a book to review, please write us, telling us your expertise and your predilections.

his book describes in clear and simple language a view of mathematics with which I profoundly disagree. It gives me a good opportunity to say why I disagree, to put his view and mine into historical perspective. Stewart's book is about the new wave in mathematics that grew around the ideas of non-linear dynamics, chaos theory, and complexity theory. The new wave began with classical physics, especially the physics of fluids. It flourished and became popular when computers were able to simulate classical motions accurately and display them dramatically. Stewart emphasizes the fact that the style of the new mathematics is visual rather than analytical. He ends his book with a prediction, that a new discipline which he calls "morphomatics" will give us deep understanding of natural patterns, especially the patterns of biological growth and form. I have no quarrel with any of Stewart's positive statements. He has every right to be enthusiastic about the new visual style of mathematical thinking. The visual style has made mathematics more accessible to the general public and more concerned with things that the general public can understand. Pictures of clouds or water droplets bring mathematics to millions whom differential equations will never reach. A LOYALISTOF THE LINEAR. I disagree with Stewart when he makes neg-

T

1This book was reviewed by John Malito in The Mathematical lntelligencer vol. 19, no. 1, 75-76. The

Column Editor's address: Department of Mathematics, Drexel University, Philadelphia, PA 19104 USA.

present utterly different review is reprinted with permission from the American Mathematical Monthly 103 (1996), 610-612.

ative statements about old-fashioned non-visual mathematics, the mathematics of equations and exact solutions. He is especially negative about quantum mechanics. He hopes that quantum mechanics will one day turn out to be an effect of classical chaos working in some undiscovered realm of hidden variables. He is blind to the beauty of quantum mechanics, a beauty that is to me transcendent and overwhelming. The idea of explaining quantum mechanics with classical models is to me as absurd as the efforts of James Clerk Maxwell to explain his electromagnetic theory with mechanical models. The beauty of Maxwell's equations becomes visible only when you abandon mechanical models, and the beauty of quantum mechanics becomes visible only when you abandon classical think-

ing. It is easy to see why Stewart dislikes quantum mechanics. Quantum mechanics runs counter to the two cardinal principles of the new wave of mathematics. Quantum mechanics is precisely linear, and profoundly nonvisual. The linearity of quantum mechanics leads to an amazing richness of exact mathematical structures and exact solutions. The abstract nature of quantum concepts such as particle spins or anticommuting fields makes them impossible to visualize. There is no way to represent the quantum world by a picture on a computer screen. A picture is a good tool for describing a classical fluid, but it cannot describe a quantum fluid such as liquid helium. The beauty of quantum mechanics is an abstract beauty. The symmetries of quantum systems are described in the abstract language of Lie Algebras rather than in the visual language of geometry. The dynamics of quantum systems cannot be simulated by motions in our familiar three-dimensional world. The space of quantum mechanics is Hilbert space, a space with infinitely many dimensions.

9 1997 SRRINGER-VERLAGNEW YORK, VOLUME19, NUMBER2, 1997

Einstein s a i d in his t r i u m p h a n t presentation of the t h e o r y of general relativity to t h e P r u s s i a n A c a d e m y o f Sciences in Berlin in 1915, "Hardly anyb o d y who has really g r a s p e d the theory will be able to e s c a p e from its magic." In m y view, this s t a t e m e n t is as true of q u a n t u m m e c h a n i c s as o f general relativity. Once you have exp e r i e n c e d t h e v a s t n e s s o f Hilbert s p a c e and the p o w e r o f functional analysis, you do not w a n t to go b a c k to the small w o r l d of c l a s s i c a l m e c h a n i c s a n d three-dimensional geometry. But Stewart has n o t really g r a s p e d quant u m m e c h a n i c s a n d is i m m u n e to its magic. CHANGING OF THE GUARD. Stewart a n d I belong to different generations. When I was a s t u d e n t 50 y e a r s ago, the n e w wave in m a t h e m a t i c s w a s a b s t r a c t algebra, the n e w w a v e in physics w a s quantum mechanics. As a student, with the normal a r r o g a n c e of youth, I cons i d e r e d the n e w stuff to be the only stuff w o r t h k n o w i n g and d e s p i s e d everything that h a d gone before. I t o o k p r i d e in n o t r e a d i n g any p a p e r s that were m o r e t h a n 5 y e a r s old. Quantum m e c h a n i c s w a s elegant and powerful. Classical p h y s i c s w a s ugly a n d complicated, not w o r t h the time it w o u l d t a k e to learn it. So I j u m p e d over classical p h y s i c s a n d m a d e a c a r e e r doing the fashionable stuff, understanding the quantum t h e o r y o f e l e c t r o m a g n e t i c processes. Now, 50 y e a r s later, the fashions have c o m e a n d gone, the fashionable h a s b e c o m e u n f a s h i o n a b l e a n d the unfashionable h a s b e c o m e fashionable. Stewart loves h y d r o d y n a m i c s and despises quantum mechanics, just as I loved quantum m e c h a n i c s and des p i s e d h y d r o d y n a m i c s 50 y e a r s ago. Stewart is n o w f a s h i o n a b l e a n d I a m unfashionable. That is as it should be. Changing fashions a r e an essential p a r t of the growth o f m a t h e m a t i c s . I do n o t regret the change o f fashion. I only wish to p o i n t out the i m p e r m a n e n c e of all fashions a n d t h e i m p o r t a n c e o f keeping u n f a s h i o n a b l e a r e a s of mathem a t i c s alive. MARYCARTWRIGHT IN THE COUNTRY OF THE BLIND. In 1942, w h e n I was a student in C a m b r i d g e and quantum m e c h a n i c s w a s riding high, I h e a r d a

66

THE MATHEMATICALINTELLIGENCER

Dame Mary Cartwright

l e c t u r e by Mary Cartwright a b o u t the Van d e r Pol equation. Cartwright h a d b e e n w o r k i n g with L i t t l e w o o d on the s o l u t i o n s of the equation, w h i c h des c r i b e the output of a n o n l i n e a r radio amplifier w h e n the input is a p u r e sinewave. The w h o l e d e v e l o p m e n t o f radio in World War Two d e p e n d e d on highp o w e r amplifiers, a n d it w a s a m a t t e r o f life a n d d e a t h to have amplifiers t h a t did w h a t t h e y were s u p p o s e d to do. The soldiers were p l a g u e d with amplitiers that misbehaved, and b l a m e d the m a n u f a c t u r e r s for their erratic behavior. Cartwright and Littlewood discove r e d that the m a n u f a c t u r e r s w e r e n o t to blame. The equation itself was to blame. They discovered that as you raise the gain of the amplifier, the solutions of the equation b e c o m e m o r e and m o r e irregular. At low p o w e r the s o l u t i o n h a s the s a m e p e r i o d a s the input, b u t as the p o w e r i n c r e a s e s you see solutions with double the period, then w i t h quadruple the period, a n d finally y o u have solutions that are not periodic at all. Cartwright and Littlewood exp l o r e d the behavior of the solutions in detail and discovered the p h e n o m e n a that later b e c a m e k n o w n as "chaos." They p u b l i s h e d all this in a p a p e r in the

Journal of the London Mathematical Society, which a p p e a r e d in 1945. That w a s a b a d time to publish.

P a p e r in E n g l a n d w a s scarce a n d few c o p i e s o f the j o u r n a l w e r e printed. M a t h e m a t i c i a n s everywhere w e r e still busy fighting the war. The p a p e r att r a c t e d no attention. In 1949 Mary Cartwright c a m e to P r i n c e t o n a n d t a l k e d a b o u t the w o r k again. Again she a t t r a c t e d no attention. Littlewood w a s not helpful. In the f o r e w o r d to Littlewood's c o l l e c t e d p a p e r s is a description w r i t t e n b y Littlewood a b o u t his c o l l a b o r a t i o n with Cartwright: T w o rats fell into a can of milk. After s w i m m i n g for a time one o f t h e m realized his h o p e l e s s fate and d r o w n e d . The o t h e r persisted, a n d at last the milk w a s t u r n e d into butter and he c o u l d get out. Littlewood does not say w h e t h e r the rat w h o d r o w n e d was himself o r Cartwright. In either case, the passage m a k e s clear that Littlewood did not understand the importance of the w o r k that he and Cartwright had done. Only Cartwright u n d e r s t o o d it, and she is not a p e r s o n w h o likes to blow her o w n trumpet. She put the Van der Pol equation aside and went on to a distinguished career in analytic function theory and university administration. She b e c a m e President of the London Mathematical Society in 1961, and Dame Mary (the fe-

male equivalent of a knighthood) in 1969. By that time, the p h e n o m e n a of c h a o s had been rediscovered by E d w a r d Lorenz. A few years later, they w e r e given their m o d e r n names. I tell this story o f the Van d e r Pol equation b e c a u s e it illustrates vividly the b l i n d n e s s of m a t h e m a t i c i a n s to disc o v e r i e s in unfashionable fields. I was m y s e l f as blind as e v e r y b o d y else to the i m p o r t a n c e of Cartwright's work. W h e n I h e a r d her lecture in 1942, I rem e m b e r being delighted with the b e a u t y of h e r results. She h a d disent a n g l e d w h a t Littlewood h i m s e l f called "the d r a m a t i c fine s t r u c t u r e of solutions." I could see the b e a u t y of her w o r k but I could not s e e its importance. I said to myself, "This is a lovely p i e c e of work. Too b a d it is only a practical w a r t i m e p r o b l e m a n d not real mathematics." I did n o t say, "This is the beginning o f a n e w era, a n e w w a y of doing mathematics." I d i d n o t say, "This is the birth of a n e w field of mathe m a t i c s that I could s p e n d t h e r e s t of m y life exploring." I m i s s e d an opportunity to be the p i o n e e r o f a n e w field, b e c a u s e I s h a r e d the t a s t e s a n d prejudices of my contemporaries. DE G U S T I B U S . . . The d i s a g r e e m e n t b e t w e e n Stewart and m e is mainly a m a t t e r of taste. My m a t h e m a t i c a l t a s t e s w e r e f o r m e d at a t i m e w h e n the m o s t c o m m o n adjectives in mathem a t i c a l conversation w e r e "deep" and "trivial." First-rate m a t h e m a t i c s w a s deep, all the rest w a s triviai. Logical d e p t h w a s the essential virtue that w e l o o k e d for in mathematics. Stewart is n o t i n t e r e s t e d in logical depth. His b o o k contains m a n y e x a m p l e s of mathe m a t i c a i description, b u t n o t one that I w o u l d c o n s i d e r deep. F o r him the language of m a t h e m a t i c s is f o r m a n d patt e r n that can be visually displayed. The essential virtue of m a t h e m a t i c s is to d i s p l a y p a t t e r n s t h a t a p p e a r in a wide v a r i e t y o f different c i r c u m s t a n c e s . His e x a m p l e s are well c h o s e n to illustrate the p o w e r o f m a t h e m a t i c s to bring p r o c e s s e s from p o p u l a t i o n b i o l o g y and e m b r y o l o g y and m e t e o r o l o g y into a unified picture. F o r me, an old-fashi o n e d analyst, these e x a m p l e s are visually interesting b u t m a t h e m a t i c a l l y triviai. I miss the d e p t h that c o m p l e x analysis brought to n u m b e r theory, the

d e p t h t h a t Lie algebras a n d fibre-bundles b r o u g h t to physics. I see s o m e parallels b e t w e e n t h e shifts o f fashion in m a t h e m a t i c s a n d in music. In music, the n e w p o p u l a r styles o f jazz a n d r o c k b e c a m e fashi o n a b l e a little earlier t h a n the n e w m a t h e m a t i c a l styles of c h a o s a n d c o m p l e x i t y theory. Jazz and r o c k w e r e long d e s p i s e d b y classical musicians, b u t have e m e r g e d as art f o r m s m o r e a c c e s s i b l e t h a n classical m u s i c to a w i d e s e c t i o n of the public. Jazz a n d r o c k are n o longer to be d e s p i s e d as p a s s i n g fads. Neither are c h a o s a n d c o m p l e x i t y theory. But still, c l a s s i c a l m u s i c a n d classical m a t h e m a t i c s a r e n o t dead. Mozart lives, a n d so d o e s Euler. W h e n the w h e e l of f a s h i o n t u r n s o n c e more, q u a n t u m m e c h a n i c s a n d h a r d a n a l y s i s will once again b e in style. Institute for Advanced Study Princeton, NJ 08540 USA

An EquationThat Changed the World; Newton, Einstein, & the Theory of Relativity by Harald Fritzsch (translated f r o m German by Karin Heusch) CHICAGO: UNIVERSITYOF CHICAGOPRESS, 1994. 300 pp. US $29.95, ISBN 0226265579 REVIEWED B Y KENNETH Y A R N A L L

h e r e are a lot of b o o k s on Special Relativity. It s e e m s e v e r y o n e h a s h a d a go at explaining this beautiful theory, full o f o d d and u n e x p e c t e d cont r a d i c t i o n s of C o m m o n Sense, to t h e lay audience. One begins to a p p r o a c h b o o k s on the subject with the attitude, "Oh, a n o t h e r one?" N o w Haraid Fritzsch has w r i t t e n a b o o k on Relativity, and this one d a r e s to be different. The p r e t e n s e o f the b o o k is a p p e a l i n g - - A l b e r t Einstein explains his t h e o r y to the one p e r s o n in history w h o deserves m o s t to k n o w a b o u t it, I s a a c Newton, while a m o d e m - d a y t h e o r e t i c a l physicist listens in and m o d e r a t e s the dialogue. Not only

T

d o e s F r i t z s c h p r o m i s e to explain Special Relativity t o the masses, but he offers us a ringside seat at the meeting of two o f the titans of Western intellect. As an e x p l a n a t i o n of Relativity, t h e b o o k d o e s very nicely; indeed, it's as clearly w r i t t e n a n e x p o s i t i o n on t h e subject a s I've r e c e n t l y read. As a glimpse o v e r the s h o u l d e r o f genius, though, it falls short. This narrative device o p e n s the b o o k to literary criticism that o t h e r w o r k s on the s u b j e c t might evade; it's h e r e w h e r e I was disappointed. First, t h e g o o d stuff. The Newtonmeets-Einstein c o n c e i t d o e s lend itself to a very n a t u r a l e x p o s i t i o n of the subject. Fritzsch h a s Einstein and t h e m o d e r n - d a y p h y s i c i s t (a fictional professor n a m e d Hailer) l e a d the w a y through t h e r e v i s i o n s to Newton's theory that l e a d to Relativity. To motivate the results, t h e e x p e r i m e n t s t h a t drove Einstein's d i s c o v e r i e s (e.g., the M i c h e l s o n - M o r l e y e x p e r i m e n t ) are described. I've t a l k e d to p e o p l e who, unfamiliar with the history of physics, have a vague n o t i o n that w h a t e v e r Relativity is, it p o p p e d out of thin air (or m a y b e that s h o u l d be, thin ether) a n d into Einstein's mind. Fritzsch's b o o k w o u l d be a nice corrective. By the end o f the b o o k , y o u ' r e left with a clear u n d e r s t a n d i n g that the universe i m p o s e d Relativity on Einstein, not the other w a y around. I don't m e a n to imply that the b o o k m a k e s this t h e o r y s e e m mundane. The N e w t o n character, although rapidly u n d e r s t a n d i n g everything e x p o s e d to him, maintains a sense o f awe. The e x p l a n a t i o n d o e s fail short at a few points along t h e way. I'll m e n t i o n one of t h e m here, w h i c h I h a s t e n to admit reflects a p e r s o n a l peeve. Chapter 9, on the p h e n o m e n o n of time dilation, is a critical m o m e n t in the t e x t - - t h e rest of the s u b j e c t s in the b o o k rely directly on the results in this chapter. Just w h e n the Lorentz transform is a b o u t to b e derived, c o m e s the disclaimer:

[The reader who might experience difficulties with mathematical equations should skip the following little calculations.] (p. 114)

VOLUME 19, NUMBER2, 1997

67

This sort of warning seems to be appearing in more and more books on science, and it strikes me as exactly wrong. To allow the reader to pass over the next two pages of easy algebra is to pretend it isn't relevant, when, in fact, it's exactly what is relevant. Seeing that the experimentally verified hypothesis of Einstein (that the speed of light is a constant, independent of observer) implies v i a the laws o f a r i t h m e t i c bizarre but observable phenomena like time, space, and mass dil a t i o n - t h a t is the opportunity the book has to make salient the importance of both halves of physics, the experimental and the theoretic. The reader should not be left off the hook here. Otherwise, the author covers the subject matter well. M1 the neat results are there: the properties mentioned above, the wave/particle duality of light, the twin paradox and some of its friends, a glimpse into the structure of space-time (including a bit of information on its metric structure in Chapter 13 which I particularly liked), and some excursions, at the end, into particle physics. There is even a little, slightly political, philosophy concerning the role of nuclear energy in Chapter 18, which isn't heavy-handed or out of place. In all, for a book aimed at the lay reader, it is nicely informative and the explanation is usually clear and uncluttered. My quarrel with the structure of the book is that, whereas it promises a dialogue between Einstein and Newton, what it supplies sounds more like two (or three) versions of the same voice, reading a script for the benefit of the audience they know to be listening. The Newton character asks the questions, the Einstein character answers them, and the Hailer character is appealed to occasionally when the subject matter becomes a bit more mode m (one thing I did have to remind myself several times is that the Einstein here is a young one, and that character has little knowledge of many of the subjects that occupied Einstein in his later years). Otherwise, it is somewhat difficult to distinguish between who is saying what, as they all sound essentially the smne--a

68

THE MATHEMATICALINTELLIGENCER

sort of scientific R o s e n c r a n t z and G u i l d e n s t e r n are Dead, with another character thrown into the mix. Not having access to the original German, I don't know whether this is a fault of the author or the translator. The only difference between the characters in this play is what they know, and at times even that is a bit strained. Can anyone really believe that Newton would feel compelled to explain to Einstein, The length 1 of the distance between two points A and B . . . , whose square is expressed mathematically by the equation l2 = (xA - xB) 2 + (yA - yB) 2 + (zA - zB) 2

(p. 154) especially after they've spent several days together? Mas, such lapses in character are the rule, not the exception, and the illusion of the conversation between giants is never really achieved. Without this illusion, Fritzsch's effort is simply another pretty good book on a widely attacked subject, and not the exceptional one that it might have been. College of William and Mary P.O. Box 8795 Williamsburg, VA 23187 USA e-mail: [email protected]

Handbook of Combinatorics R. L. Graham, M. Gr6tschel and L. Lovdsz, editors AMSTERDAM AND CAMBRIDGE:ELSEVIERAND THE MIT PRESS, 1996 VOL 1:1100PP., US$175.00,ISBN 0-26207-170-3 VOL. 2:1250PP., US$175.00, ISBN 0-26207-171-1

REVIEWED BY HERBERT S. WILF

he explosive growth of discrete mathematics over the past 20 years has gone hand in hand with the rise in public awareness and use of computers, which are inherently discrete, and with the rise of mathematics and science in general during the post-Sputnik years. The subject is now so large and diverse, encompassing enumeration,

T

graphs, randomness, algorithms, complexity analysis, coding, matroids, formal languages, optimization, discrete geometry, identities and special functions, partially ordered sets, algebraic combinatorics, asymptotic estimation, Ramsey theory, extremal set theory, and so forth, that there simply cannot be a handbook of combinatorics. But there is a Hand-book o f Combinatorics, and it is a superb exposition of many of the aspects of the subject, written by those who created and/or enriched the fields about which they write. This is a collection of 44 individual "chapters," most of which are really books in themselves, with the organization, length, scope, bibliography, etc. that you would expect to fend in a book. For example, chapter 22 is A s y m p t o t i c e n u m e r a t i o n methods, by Andrew Odlyzko, and it is about 170 pages long, including a 17-page bibliography. Taken in itself, this one chapter is an outstanding book about asymptotics, and it can be compared only with de Bruijn's classic A s y m p t o t i c methods i n analysis, of 1958, to which it is in part a worthy successor, in part an update, and in part complementary. Chapter 25 is R a m s e y theory. Well, if there is a chapter with a sweeping title like that, it would have to be an authoritative statement about the current state of the subject, written by an expert. It is and it is. Jaroslav Ne~et~il is the author, and he has written a splendid, self-contained survey of Ramsey theory, with a huge bibliography, to which I would unhesitatingly direct any bright undergraduate or graduate student (or colleague---or myselfi.) for a reading course in the subject. The very first chapter, B a s i c graph theory: paths a n d circuits, by J. A. Bondy, is a 108-page clear and sharp mini-book on its subject, with a 17-page bibliography, that seems to be easily the best "book" available in that area. Here is a list of all of the chapters: Basic graph theory: paths and circuits; Connectivity and network flows; Matchings and extensions; Coloring, stable sets and perfect graphs: Embeddings and minors; Random graphs; Hypergraphs; Partially ordered sets; Matroids; Matroid minors; Matroid op-

timization and algorithms; Permutation groups; Finite geometries; Block designs; Association schemes; Codes; Extremal problems in combinatorial geometry; Convex polytopes and related complexes; Point lattices; Combinatorial number theory; Algebraic enumeration; Asymptotic enumeration methods; Extremal graph theory; Extremal set systems; Ramsey theory; Discrepancy theory; Automorphism groups, isomorphism, reconstruction; Combinatorial optimization; Computational complexity; Polyhedral combinatorics; Tools from linear algebra; Tools from higher algebra; Probabilistic methods; Topological methods; Combinatorics in operations research; Combinatorics in electrical engineering and statics; Combinatorics in statistical physics; Combinatorics in chemistry; Applications of combinatorics to molecular biology; Combinatorics in computer science; Combinatorics in pure mathematics; Infmite combinatorics. The chapters are for the most part very up-to-date, and are written with the sophisticated viewpoints that we expect from true experts. Bollobfis's chapter on extremal graph theory is a good example of that. It is a narrative of what is known, what is new, what is unknown, and how it all ties together, with a profuse bibliography, and it is a rich meal for the intelligence. The level of the chapters is fairly consistently pegged at "here is a map of the frontier," and the authors will then try to tell you exactly what is known and what the principal remaining questions are. The highest standards of breadth and depth of scholarship are followed, almost without exception. The editors are to be commended not only for the conception of the work, but for the details, and there were thousands of them, of its execution. The uniformity of the formatting of the chapters, the wonderfully comprehensive bibliographies, the unusual, virtually unprecedented, amount of between-chapter cross referencing, the completeness of the index, the extreme rarity of typos, and the impeccable choices that they have made for their contributors, all attest to the quality of the editorial work. What is there to complain about? That of course is a very subjective

question, and here is this reviewer's very subjective reply. I enjoy counting things. I do combinatorics mainly because ! like counting things, but these two volumes emphasize other areas of the subject. But "counting things" is at the core of combinatorics, and a number of its shining stars are not in these volumes. I miss the shower of recent important results about Young tableaux, about the combinatorics of words, about automated proofs of identities and symbolic manipulation in general, and about formal languages. The triumphs of the theory of formal languages, largely due to Marcel Schtitzenberger, when applied by the LABRI group (Viennot, Delest, Bousquet-M~lou, etc., at Bordeaux) to the counting of many varieties of polyominoes that had been thought to be beyond reach, are nowhere in sight in these volumes. The art of bijection has been polished to a high luster recently, with far-reaching work having been done on integer partitions, lattice paths, and tableaux, to name just a few areas. A marvellous chapter, or even a few of them, might have been written on bijective methods, but there is none. The names of many of the most important figures in enumerative combinatorics appear here far too infrequently. The reason for these omissions, of course, is that the editors were aiming in other directions. They note in their preface that "it was inevitable that some areas had to be left o u t . . . " The brilliant quality of most of the contributions to the present volumes makes me hope for a third volume, one that will fill in some of the enumerative gaps. A work of this scale invites statistical measures. The two volumes together weigh nearly five pounds, and cost $300, which works out to $60 per pound. This compares with, for example, about $26 per pound for A = B , of which I am one of the authors, so on a unit pricing basis, we are the better buy per pound. However, just to highlight the treachery of such comparisons, this work of about 2200 pages costs about 13 cents per page, vs. 18 cents for A = B . What conclusion can I draw? Theirs is a "best buy," but ours uses fancier paper. The index, which is absolutely outstanding, contains the information that

works of Paul Erd0"s are cited on 173 pages, i.e., on about 6.2% of all of the pages--a beautiful tribute to his numerous seminal contributions to the subject. Discrete mathematics is fortunate indeed to have had such a great creative force in its midst. Discrete mathematics is also fortunate to have the Handbook o f C o m b i n a t o r i c s in its midst. It will be a standard reference for students and workers in the field for a long time to come. Mathematics Department University of Pennsylvania Philadelphia, PA 19104, USA e-mail: [email protected]

She Does Math!; Real-Life Problemsfrom Women on the Job edited by Ma rl a P a r k e r WASHINGTON: MATHEMATICALASSOCIATIONOF AMERICA, 1995, 272 p. US $27.50; ISBN 0883857022 REVIEWED B Y MARCl PERLSTADT

oo many of us were forced to take algebra when the time and energy could have been devoted to subjects that were truly beneficial individually and nation-

T

ally. Algebra isn't essential to much of anything. Once adding, subtracting, multiplying and dividing are mastered---by eighth grade usually--why insist on more? Algebra has little to do with mathematics. It's a language, a way of symbolic communication that a few people find fascinating and practical, while most don't.... Would millions of high school students trudge into their algebra classes i f they weren't a gate through which they were forced to pass to enter college? And in a f ew years would they submit to college algebra i f it weren't a requirement to graduate? Not likely. Algebra is more loathed than learned . . . . I happen to think algebra is a useless torture. "Who Needs Algebra?", Colman McCarthy, The Washington Post, April 20, 1991

VOLUME 19, NUMBER2, 1997

69

le m a t h e m a t i c i a n s have a small image p r o b l e m . It w o u l d be comforting to think t h a t c o l u m n i s t Colman McCarthy's v i e w s a r e held only by an unenlightened fringe and shouldn't c o n c e r n us. Unfortunately, it a p p e a r s that a large s e g m e n t of o u r society feels entirely c o m f o r t a b l e lacking any m a t h e m a t i c a l b a c k g r o u n d . Most citizens are end u s e r s in o u r technological s o c i e t y - - c o n t e n t to merely turn on a computer, a television, a calculator. Many adults will readily tell y o u that they never use any m a t h e m a t i c s in their day-to-day life, save for making change and p e r h a p s taking a few meas u r e m e n t s w h e n t h e r e are h o m e repairs to be done. The attitude exp r e s s e d in the a b o v e c o l u m n is s h a r e d n o t only by m a n y s t u d e n t s but b y their p a r e n t s as well. They h a v e n ' t a clue as to why anyone s h o u l d s t u d y mathematics. Mathematicians t h e m s e l v e s s e e m s o m e w h a t s c h i z o p h r e n i c w h e n discussing the situation. On the one h a n d we have b e e n t o l d that calculus (and m a t h e m a t i c s in general) should be a "pump and n o t a filter," that it is so vital to so m a n y c a r e e r s that students will face e x c e e d i n g l y b l e a k futures if w e can't s o m e h o w t e a c h t h e m this material. At the s a m e time, almost every p e r s o n t e a c h i n g m a t h e m a t i c s has at s o m e point e n c o u n t e r e d a class populated b y the C o l m a n McCarthys of the world. Thus e v e n a m o n g mathematicians there have b e e n calls to e x e m p t students w h o d o n o t a p p e a r mathematically inclined f r o m taking real m a t h c o u r s e s a n d to p l a c e t h e m in m a t h e m a t i c s a p p r e c i a t i o n classes. Why should m a t h e m a t i c s , we are asked, be foisted u p o n unwilling students? One bit of reality testing as to t h e i m p o r t a n c e of m a t h e m a t i c s for the average A m e r i c a n c a n b e s e e n in the annual survey o f b a s i c skills testing cond u c t e d b y the A m e r i c a n Management Association. B a s e d on the r e s p o n s e s received, the A s s o c i a t i o n e s t i m a t e s roughly 40% o f m e m b e r c o m p a n i e s currently t e s t j o b a p p l i c a n t s for basic m a t h skills, up f r o m 27.6% in 1990. Those c o m p a n i e s w h o t e s t only for m a t h skills f o u n d a deficiency rate of 47%. Those c o m p a n i e s testing only for

W

70

THE MATHEMATICALINTELLIGENCER

literacy skills found a deficiency rate o f 32%. The deficiency rate for all comp a n i e s (those testing m a t h and/or lite r a c y ) was 36.3%. The r e p o r t further details that 87% of firms t h a t test j o b a p p l i c a n t s will not hire t h o s e w h o do n o t p a s s p r e - e m p l o y m e n t tests. It s e e m s clear that there s h o u l d be real c o n c e r n a b o u t the m a t h e m a t i c a l training o f o u r children. E d u c a t o r s have s u g g e s t e d numerous remedies. We m a t h e m a t i c s teachers have b e r a t e d o u r s e l v e s for our "boring" lectures and have sought to m a k e things m o r e entertaining. All s o r t s o f changes have b e e n p r o p o s e d at all levels from e l e m e n t a r y s c h o o l t h r o u g h graduate school. High schools a r e looking at so-called fusion m a t h e matics, calculus is being "reformed," a n d "proof" has b e c o m e a dirty word. Despite a lot o f mutual b a c k - p a t t i n g b y m e m b e r s of the National Council o f T e a c h e r s of M a t h e m a t i c s a n d o t h e r ref o r m - m i n d e d m a t h e m a t i c i a n s , it rem a i n s to be s e e n w h e t h e r a n y of these s u g g e s t e d changes will significantly affect s t u d e n t achievement. It is h a r d to imagine a surge in s t u d e n t achievem e n t without a c o r r e s p o n d i n g surge in t h e a m o u n t o f effort t h a t s t u d e n t s are willing to devote to their courses. If y o u s e e evidence of this surge, let m e know. Perhaps mathematicians are at a real disadvantage when trying to cope with totally disinterested students. It's hard for us to understand that m o s t people don't find mathematics as m u c h fun as w e do. When students w o n d e r why they have to learn this or that, w e really think they should learn it b e c a u s e it's neat. Most students, however, will require us to m a k e a very strong case for learning material that does not particularly appeal to them. This has resulted in ongoing attempts to introduce m o r e applications into the curriculum. S o m e h o w a reluctant American p o p u l a c e has to learn enough mathematics to qualify for productive j o b s in our economy. She Does Math! is an a t t e m p t to m a k e it clear that m a t h e m a t i c s is far m o r e t h a n a w a y of filtering a n d ranking s t u d e n t s for college admission. The b o o k p r e s e n t s short a u t o b i o g r a p h i c a l s k e t c h e s of 38 w o m e n w h o use mathe m a t i c s in their careers. The c a r e e r s

s p a n a wide spectrum, including n o t only s c i e n c e and engineering b u t also o t h e r fields, such as nursing, a r c h a e o l ogy, dietetics. Following e a c h s k e t c h are s o m e s a m p l e m a t h e m a t i c a l p r o b lems t h a t arise in e a c h w o m e n ' s p r o fessional c a r e e r (with solutions in t h e b a c k o f the book). The b o o k a p p e a r s to be a i m e d at middle school, high school, a n d college females (although it w o u l d certainly b e equally useful for males of the s a m e age) a n d their parents. The s h o r t bio g r a p h i e s p r e s e n t e d run t h e gamut, from w o m e n w h o really a d o r e d m a t h in high school, to w o m e n w h o h a t e d it but later f o u n d out they n e e d e d it. What y o u do get is a sense of j u s t h o w m a n y different types of c a r e e r s n e e d m a t h e m a t i c s . This m a y or m a y n o t imp r e s s a n a d o l e s c e n t intent u p o n skipping a l g e b r a o r geometry, b u t it m a y help give p a r e n t s the b a c k b o n e to p u s h the i s s u e with children. It m a y also serve to r e m i n d s o m e m a t h e m a t i c s professors why math appreciation c o u r s e s s h o u l d not be offered as an alteruative to "real" m a t h c o u r s e s while children a r e still at an age w h e r e their future c a r e e r c h o i c e s are far from certain. While it is true that m a n y p e o p l e m a n a g e to find c a r e e r s that require minimal m a t h (you can always be a c o l u m n i s t for the Washington Post), giving up on m a t h in high s c h o o l really limits future choices. The b i o g r a p h i e s m a k e for s o m e interesting reading. Even m a n y collegeage s t u d e n t s s e e m to a s s u m e t h a t career p a t h s a r e linear a n d y o u h o p o n one a n d j u s t continue. They m a y b e una w a r e o f all the zigs and zags p e o p l e go t h r o u g h during their careers. Here they will find w o m e n w h o b a s i c a l l y k n e w all along w h a t t h e y w a n t e d to do, as well a s t h o s e w h o t o o k a while to find themselves. They changed m a j o r s and c a r e e r s and survived the experience nicely. And, they all l e a r n e d the value o f m a t h e m a t i c s in their careers. More p r o b l e m a t i c is the a t t e m p t to provide a glimpse o f the type of mathematical p r o b l e m s each w o m a n d e a l s with. The b o o k is a d d r e s s e d to a r a t h e r large audience, and the p r o b l e m s w e r e c h o s e n so as to require little m o r e t h a n arithmetic, algebra, geometry, trig, and calculus. It is p r e t t y h a r d in one o r t w o

p a g e s to give s o m e o n e w h o h a s no i d e a o f the terminology in y o u r field a samp l e o f the p r o b l e m s you w o r k on. Thus s o m e of the p r o b l e m s e c t i o n s p r e s e n t w h a t m a y s e e m like a huge deluge of d a t a in the form of definitions and o t h e r basic information, f o l l o w e d by a f e w problems. Though the p r o b l e m s in s o m e c a s e s m a y involve little m o r e t h a n arithmetic, t h e r e is a lot of material p r e s e n t e d in c o n d e n s e d form, perh a p s so m u c h that eyes will glaze over. Also, since the b o o k limits itself to s t a n d a r d t y p e s of p r o b l e m s t h a t the aud i e n c e can easily handle, s o m e r e a d e r s m a y find m a n y of the p r o b l e m s disappointing for their l a c k o f challenge. T h u s this is not the b o o k to give an une m p l o y e d m a t h Ph.D. so t h a t he or she c a n get s o m e idea o f the o p p o r t u n i t i e s available for m a t h e m a t i c i a n s in industry. I n d e e d the only t w o m a t h e m a t i c i a n s in the b o o k are professors. Who should r e a d this b o o k ? The bio g r a p h i e s alone m a y b e e n o u g h to justify having a t e e n a g e r (male o r female) t a k e a l o o k at it. The p r o b l e m s e c t i o n s o f t h e b o o k should certainly be r e a d b y a u t h o r s of texts in high s c h o o l mathe-

m a t i c s a n d calculus. There are s o m e "real-world" applications t h e r e t h a t could b e suitably i n c o r p o r a t e d into texts. In addition, any m a t h e m a t i c i a n w h o has forgotten that a s t u d e n t ' s inability to h a n d l e simple p r o b l e m s s u c h as c o n v e r s i o n of units and ratios c o u l d lead to d i s a s t e r in the real w o r l d w o u l d

fred in this v o l u m e s o m e h a n d y cantionary exercises. Department of Mathematics and Computer Science Drexel University Philadelphia, PA 19104, USA e-mail: [email protected]

o

But the way some kids treat her, she might as well be from another planet. Just because she has epilepsy. Epilepsy doesn't make her weird. It doesn't affect her abilities, her sense of humor, or her qualities as a friend. Kids with epilepsy or any disability. Let's count 'em in. Get the facts. Write or call The Epilepsy Foundation of America, 1-800-EFA-1000. Or contact your local EFA affiliate.

VOLUME 19, NUMBER 2, 1997

71

I-l~.~,m~,,~Jt~--

Robin

Stamps of

Wilson

E

I

veryone is familiar with the usual rectangular stamps. However, there are several stamps whose shape is less c o m m o n - - i n particular:

9 the equilateral triangles of Malaysia and Austria

Unusual

Shape I 9 the isosceles right-angled triangles of Pakistan and Ghana

9 the 1858 scalene triangle of Colombia

9 the differently shaped trapezia of Monaco, Malta and Malaysia

Please send all submissions to the Stamp Corner Editor, Robin Wilson, Faculty of Mathematics, The Open University, Milton Keynes, MK7 GAA, England

72

Further unusual shapes will appear in the next Stamp Comer.

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER-VERLAG NEW YORK