No title

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

De tous ces r6sultats, s'ils se confirmaient, sortirait une m6canique enti6rement nouvelle qui serait surtout caract6ris6e...

Poincar6, Einstein, Whittaker In Jeremy Gray's interesting commentary [1] on the Poincar6-Einstein controversy, reference is made to the disturbing role it played in the Nazi disparagement of Jewish scientists during the 1920's and 1930's. Arthur Miller [4], discussing Sir Edmund Whittaker's use in 1953 [9] of the term "relativity theory of Poincar6 and Lorentz," criticized him for not explicitly distancing his viewpoint from the Nazi one. Now Whittaker was aware of the ideological sources for some anti-Einstein feelings, for he mentioned them in his Royal Society obituary of Einstein [8]. All agree, apparently, that Whittaker was not anti-Semitic himself; I know from my own research on Edinburgh in that period that he worked very hard to provide haven for Jewish refugee scientists Arthur Erd61yi [3] and Max Born. It would have been helpful to consult also Whittaker's own scientific biography [7]. Already a creative, practicing mathematician in 1904, he was investigating a reformulation of the electromagnetic potentials, as well as aspects of Poincar6's dynamics. He was in a better position than later commentators to judge whether his own "paradigm shift" had occurred already in response to Lorentz and Poincar6. Despite my defence of Whittaker, I must say that the arguments of Miller and Gerald Holton [2] against his "Poincar6-Lorentz" title seem persuasive. This is confirmed by seeing Leigh Page's 1912 electrodynamics paper [5] citing only Einstein. As to Poincar6's alleged blindness to the imminence of a new physics--Whittaker, Miller, and Gray all omit a crucial phrase from the 1904 statement in La valeur de la science [6]. What Poincar6 said is (with the omitted words italicized), 4

Miller is wrong to interpret the conditional tenses--'an entirely new mechanics would arise"--as reflecting dubiousness about the theoretical consequences of relativity; they reflect willingness to await experimental "confirmation."

References 1. J.J. Gray, "PoincarG Einstein, and the Theory of Special Relativity," Mathematical Intelligencer 17(1) (1995), 65-67. 2. G. Holton, "On the Origins of the Special Theory of Relativity," in Thematic Origins of Scientific Thought: Kepler to Einstein, Cambridge, MA: Harvard, 1973; pp. 165-183. 3. D.S. Jones, "Arthur Erd61yi 1908-1977," Biographical Memoirs of Fellows of the Royal Society 25 (1979), 267-286. 4. A.I. Miller, "A Pr6cis of Edmund Whittaker's 'The Relativity Theory of Poincar6 and Lorentz,' "Arch. Int. Hist. Sci. 37 (1987), 93-103. 5. L. Page, "A Derivation of the Fundamental Relations of Electrodynamics from Those of Electrostatics," Amer. J. Science (4)34 (1912), 57-68. 6. H. PoincarG La valeur de la science, Paris: Flammarion, 1905. 7. G. Temple, "Edmund Taylor Whittaker 1873-1956," Biographical Memoirs of Fellows of the Royal Society 2 (1956), 299-325. 8. E.T. Whittaker, "Albert Einstein 1879-1955," Biographical Memoirs of Fellows of the Royal Society 1 (1955), 37-67. 9. E.T. Whittaker, "The Relativity Theory of Poincar6 and Lorentz," in A History of the Theories of Aether and Electricity, Vol. II, The Modern Theories, New York: Harper, 1960; pp. 27-77. Keith E. Donnelly Ontario Hydro 1549 Victoria Street East Whitby, Ontario LIN 9E3 Canada

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Verlag New York

Numerology Reading the article "Number mysticism in scientific thinking" in The Intelligencer vol. 17, no. 1, I was reminded of remarks made by S.A. Wouthuysen in a colloquium in Amsterdam some 17 years ago. I wonder whether this is a case of foolish number mysticism like that of J.E. Mills or of sensible speculation. The argument, which he attributed to P.A.M. Dirac, runs as follows. Take all kinds of fundamental (physical) constants, such as the velocity of light, the electron charge, the Hubble constant, etc., and form dimensionless numbers out of them, such as the fine-structure constant o~. It turns out that they essentially fall into two groups: some are of order of magnitude 1 (ranging from 10 -3 to 103), the others are of the order 1040. Now it is known that the Hubble constant varies with time. But it would be extremely unlikely that the dimensionless constant formed with the Hubble constant would only now belong to one of the two groups, so it must be supposed to have belonged always to that group. Hence other fundamental constants must depend on time too, for instance the velocity of light. Gijs M. Tuynman U.F.R. de Mathdmatiques Universitd de Lille I F-59655 Villeneuve d'Ascq Cedex ,France

More on Maclaurin I am writing to add some information to John Mooney's interesting article on Colin Maclaurin (vol. 16, no. 1). The house in Glendaruel in which he is said to have been born still exists. It is a very small building beside the modern manse. When I saw it last it was being used as a coalhouse. Colin's father John was indeed, as stated on the memorial plaque, a man of literary ability and business talent. In May 1653 the Synod of Argyll decided that the Psalms should be translated into Irish (i.e., Scottish Gaelic) "so that they may be sung with the common tunes" used by English-speaking congregations, who had at their disposal the Scottish metrical Psalms. John Maclaurin was one of the Church of Scotland ministers involved in this exercise. He was, in particular, brought in to revise the translation of Psalms 109-136, and was in charge of seeing the whole edition through the press in Edinburgh. It appeared in 1694 four years before his death. Only two copies of the original edition survive,

although there were several later revised editions. As he was brought up as a child in the Highlands of Scotland, there is little doubt that Colin Maclaurin's first spoken language was Gaelic. There is no documentary confirmation of this in his letters (edited by SteUa Mills, Shiva Publishing Limited, 1982) or elsewhere, although it is known that he was interested in the appointment of Gaelic-speaking ministers to Highland parishes. Finally, it may be noted that the undergraduate mathematical society in the University of Glasgow (where he was a student) is the Maclaurin Society, and one of the mathematical chairs in the University of Edinburgh (where he was ultimately professor) bears his name. Robert A. Rankin University of Glasgow Glasgow G12 8QW Scotland

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996 5

Exactly How Did Newton Deal with His Planets? S. K. Stein

In 1987, the tercentenary of Newton's Principia, I decided to mark the occasion by reading his treatment of the planetary orbits. Just how did he approach the subject if he didn't use calculus? It took me a while to adjust to his way of thinking, but eventually his approach, a mix of geometry and limits, became quite clear. To my surprise, he went beyond the inverse-square and linear forces to treat even the inverse cube and inverse fifth power. This article describes what he did and how he did it, using Newton's reasoning and diagrams, but presenting his arguments in a way that should be much easier for a 20th-century reader to follow. References will be to Book 1 of the first English edition of the Principia, Motte's translation of 1729, revised by Cajori in 1934 [6]. (The first three editions of the Principia, which appeared in 1687, 1713, and 1726, were in Latin.) Throughout, we assume a force that is "radially symmetric" or "central"--that is, one for which there is a point O such that the force at an arbitrary point P is parallel to the vector OP and has a magnitude that depends only on the distance from O to P. If that distance is r, we letf (r) denote the magnitude of the force. The phrase "the force is inverse-square" means that there is a nonzero constant A such that fir) = Ar -2. Newton's reasoning rests on geometric facts well known in his time. For convenience they are collected in the first section, which also includes two mixed geometric-limit results of Newton.

Geometry A chord through the center of an ellipse is called a diameter of the ellipse. It meets the ellipse at two points, which we denote P and G (labels that appear in Newton's diagrams). The diameter parallel to the tangents at P and G is called the conjugate diameter, a concept that goes back to Apollonius in the second century B.C. [1]. Fact 1. The conjugate of the conjugate of a diameter is the original diameter. (Consequently, the four tangents to an ellipse at the ends of a pair of conjugate diameters are parallel to those diameters, as in Figure 1.) To justify Fact 1, as well as Facts 2 and 3 below, first check them for a circle, then apply an affine map. (An affine map of the xy-plane is a bijection from the plane onto itself that preserves collinearity. In terms of coordinates, the point (x, y) is mapped to the point (ax + by + e, cx + dy + f), where a, b, c, d, e, and f are constants and the determinant ad bc is not 0. All areas are magnified by the factor lad

Figure 1. 6

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Verlag New York

-

P

0

P E

"V

C S

C

G Figure 2.

Figure 3.

bc I. Also, the lengths of all line segments in a fixed direction are magnified by a constant factor, which depends on the direction.) Let PG be a diameter of an ellipse and Q any point on the ellipse. Let v be the point on PG such that Qv is parallel to the tangent at P, hence parallel to the conjugate diameter, as shown in Figure 2. The center of the ellipse is C.

Let r = riO) be the polar equation of the spiral. There is a constant k such that rAO/Ar -~ k, hence

Fact 2. For a given ellipse and a given diameter PG of that ellipse, the ratio Qv 2 P v . Gv is independent of Q. The tangents at the ends of a pair of conjugate diameters form a parallelogram (see Figure 1). Fact 3. For a given ellipse, all such parallelograms have the same area. The next fact about ellipses seems to be Newton's own discovery. Let S be a focus of an ellipse and P any point on the ellipse. The line SP meets the diameter conjugate to the diameter through P at a point E as in Figure 3. Fact 4. The length PE is independent of P. Newton's proof [6, p. 56] uses two properties of an ellipse that are familiar to most freshman calculus students. To give the reader the pleasure of discovering his short, elegant argument, I omit the proof. Newton also treats a body that "revolves in a spiral PQS cutting all the radii, SP, SQ, etc. in a given angle." This "equiangular spiral" had been investigated by Harriot (1560-1621) because of its role in cartography. A ship that follows a constant compass heading sweeps out a route that eventually spirals around the North or South Pole (unless it is always east or west). Since this route makes a fixed angle with the meridian lines, its stereographic projection on the equatorial plane is an equiangular spiral. (Harriot was the first person to prove that stereographic projection preserves angles.)

r(O + A~) A0 -~- 1 + - frO)-k " From this, Harriot concluded that radii corresponding to an arithmetic progression of angles form a geometric progression. As a consequence we have a remarkable property of an equiangular spiral: If we rotate it around the pole of the polar coordinate system, we can then magnify the rotated curve to coincide with the original spiral. Thus the equiangular spiral is congruent to any uniformly magnified copy of itself. [To show that it is the only type of curve with this "self-similar" property, one must solve the functional equation f(O+ o~)= f(O)g(c~).] These properties can be established by starting with the equation r/r' = k and showing that frO) = Ab ~ for some constants A and b. All that we will need to know about the spiral is Fact 5. If P and P* are points on an equiangular spiral, then any neighborhood of P on the spiral is similar to some neighborhood of P.*. Newton also develops and uses some geometric limits, namely, Facts 6 and 7, but I omit their proofs, which would divert us from our main theme. In Figure 4, S and P are fixed, Q is on a smooth curve, and Qx is parallel to the tangent at P. (Later S will be a focus of an ellipse.) Corollary 2 of Lemma 7 [6, p. 33] asserts that "the ultimate ratio of Qx and the arc QP as Q approaches P, will be the ratio of equality," or, in modern terms, lim ~-~ Qx = 1. Q~P

(1)

N o w consider Figure 5, where C, like S, is fixed. (Later C will be the center of an ellipse.) The point v is on CP and Qv is parallel to the tangent at P. Then we also have limp Qv = 1. Q QP

(2)

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

7

Q

_....__

A

C X

B

P

S R Figure 6.

Figure 4.

From this he immediately obtains a measure of the force,

Combining (1) and (2), we obtain Fact 6. l i m Q ~ p ( Q x / Q v ) = 1.

This will permit us to replace Q x by Q v in a limit argument. Lemma 8 [6, p. 33] compares the areas of triangle R A B and sector R A C B in Figure 6 as A approaches B. In modern terminology it asserts Fact 7.

lim Area of triangle RAB = 1. A~B Area of sector R A C B

With the aid of these tools we can n o w retrace Newton's analysis of the relation of motion to central forces.

Using some geometric reasoning that rests on the fact that the area swept out by the ordinates representing velocity is the distance covered or "displacement," N e w t o n reaches Corollary 3 of Lemma 10 [6, p. 35], which asserts that the displacement "in the very beginning of motion" is proportional to the force and the square of the time, Displacement - (Force)(Time) 2.

Q A w

Figure 5. 8

THE MATHEMATICAL INTELL1GENCER VOL. 18, NO. 2, 1996

(3)

To devise a geometric measure of the force acting on an object in a given orbit, he needs a geometric measure of the "time" that appears in (3). This he accomplishes by establishing Kepler's "area" law, which up to the time of the Principia seemed the least important of Kepler's three laws. He does this in Proposition 1 [6, p. 40]: The areas which revolving bodies describe by radii drawn to an immovable centre of force do lie in the same immovable planes, and are proportional to the times in which they are described. I quote his argument:

N e w t o n ' s Approach

C

F o r c e - Displacement (Time) 2

For suppose the time to be divided into equal parts, and in the first part of that time let the body by its innate force describe the right line AB. In the second part of that time, the same would, if not hindered, proceed directly to c, along the line Bc equal to AB: so that by the radii AS, BS, cS, drawn to the centre, the equal areas ASB, BSc would be described. But when the body is arrived at B, suppose that a centripetal force acts at once with a great impulse, and, turning aside the body from the right line Bc, compels it afterwards to continue its motion along the right line BC. Draw cC parallel to BS, meeting BC in C; and at the end of the second part of the time, the body will be found in C, in the same plane with the triangle ASB. Join SC, and, because SB and Cc are parallel, the triangle SBC will be equal to the triangle SBC and therefore also to the triangle SAB. (See Fig. 7.) He then applies the same a r g u m e n t to the successive triangles s h o w n in Figure 7 and takes the limit as "the number of those triangles be augmented, and their breadth diminished in infinitum." He concludes that "any described areas S A D S , S A F S . . . will be proportional" to the times. (Incidentally, a diagram somewhat resembling Fig. 7 that appears in Robert Hooke's manuscripts suggests that Hooke had a deeper understanding of curvilinear motion under a central force than has been traditionally acknowledged [5].)

as Q approaches P; in short

f

Force at P - limp S p i QR ~ -QT2 .

C

(5)

Note that QR and QT are infinitesimals. To determine the limit (5) for a particular point P on a given orbit, Newton uses the geometry of the curve to transform (5) to a limit that involves no infinitesimals, only macroscopic features of the orbit. In the next section I show the application of this technique to four different types of orbits.

Using the Method to Find the Centripetal Force Newton's first application is Proposition 7 [6, p. 49]: If a body revolves in the circumference of a circle, it is proposed to find the law of centripetal force directed to any given point.

S Figure 7.

With this information, he obtains a completely geometric expression proportional to the force. Consider a point P on an orbit controlled by a centripetal force directed toward S. Let Q be a point very near P on the orbit, as in Figure 8. The segment QR, parallel to SP, represents the displacement from the tangent line at P due to the force; for were this force absent, the object would have moved along the tangent and reached the point R. QT is perpendicular to SP. The time is represented by the area of the sector SPQ. However, for Q near P, the area of the triangle SPQ, namely, (1/2)SP 9 QT, may be used as a substitute for this area. (This is Fact 7.) All told then, from (3) we conclude that the force at P is proportional to the limit of

QR

I reproduce his argument only in the case when the "given point," S, lies on the circumference. Figure 9 shows the circle and the points of interegt. SA is a diameter and Z is the intersection of QT with the tangent at P. In order to express (5) completely in terms of macroscopic lengths, we must relate Q R / Q T 2 to "visible" features of the circle. (Note that SP already is macroscopic.) Because angles ZPS and PAS subtend the same arc, they are equal, so right triangles Z P T and SAP are similar. Thus (6)

RP 2 = QR 9 RL.

(7)

Also, by geometry,

Z

(4)

Sp2 . QT 2

SP SA

QT _ Z T RP ZP

P L

S Figure 8.

T

P Figure 9. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

9

and

Combining (6) and (7) quickly gives QR

SA 2

SP 2. Q T 2

-

SP 4 9 RL"

SP* Q'T* = SP QT.

(8)

Letting Q approach P, we obtain, because RL approaches SP,

Hence (5) gives this measure of the force at P*: Sp 3 QR (Sp*) 3 SP 2 . Q T 2"

SA 2

Force - - -

Sps"

In this case, SA being fixed, the force is inversely proportional to the fifth power of the distance. We next consider Proposition 9 [6, p. 52], which reads If a body revolves in a spiral PQS, cutting all radii SP, SQ, etc., in a given angle, it is proposed to find the law of the centripetal force tending to the centre of that spiral. Newton's argument exploits the self-similarity of the spiral, but also a lemma that asserts that QR is proportional to RP 2, hence to AT 2 for Q near P. However, selfsimilarity alone suffices, as I will show. Let P be a point on the orbit, which will be kept fixed. Let P* be an arbitrary point on the orbit, With the aid of self-similarity, the force at P* can be compared to the force at P. The similarity that sends the curve into itself and P to P* sends S to S, Q to Q* on the curve, the tangent at P to the tangent at P*, R to R* on the tangent at P*, and T to T*. (See Fig. 10.) The force at P* is then approximated by the quotient Q'R* (Sp*)2(Q*T*) 2"

(9)

Letting Q approach P, we see that the force at P* is proportional to

Sp3

- (Force at P). (SP*) 3 As P is fixed, the force is inversely proportional to the cube of the distance. N e w t o n then studies motion in elliptical orbits. In the first case (Proposition 10 [6, p. 53]) the point of attraction is the center of the ellipse (as is the case for a particle orbiting within the earth). The proposition reads: If a body revolves in an ellipse, it is proposed to find the law of the centripetal force tending to the centre of the ellipse. Suppose SA and SB to be semiaxes of the ellipse, GP and DK conjugate diameters, PF and QT perpendiculars to those diameters, and Qv an ordinate parallel to the diameter DK, as in Figure 11. We wish to express the quantity Q R / ( S P 2 9 QT 2) in terms of large features of the ellipse. By similar triangles, QT _ PF

The magnification factor is SP*/SP, so Q , R , = SP* QR SP

R 9

Q

(10)

Qv

SP "

and, by Fact 2, Qv 2

SD 2

Pv 9 vG

SP 9 SG"

Also, QR = Pv. From these three equations and a little algebra, it follows that

~

QR SP 2 9 QT 2

Q A

F i g u r e 10.

10 THEMATHEMATICAL INTELLIGENCER VOL.lS, NO.2, 1996

S P . SG PF 2 9 SD 2 9 vG"

Now, PF " SD is one-fourth of the area of a circumscribing parallelogram determined by conjugate diameters, hence (by Fact 3) is a constant, k, independent of P. Also, SG = SP, and vG approaches the quantity 2SP as Q approaches P. Thus, as Q approaches P, QR SP 2 9 QT 2

Sp2 k 2 9 2SP

SP 2k2"

Consequently, the force is proportional to the first power of the distance. Then N e w t o n treats the case of Keplerian orbits in Proposition 11 I6, p. 56]:

B

.R

B

R P

A

Figure 11.

A

Figure 12.

If a body revolves in an ellipse, it is required to find the centripetal force tending to the focus of the ellipse. The diagram, Figure 12, is a bit more complicated than Figure 11. S is n o w a focus, QR is parallel to SP, Qv is parallel to RP, and v is on the diameter PG. The point x is the intersection of Q v and SP. E is the intersection of SP and the conjugate diameter DK. Again Newton wishes to express Q R / ( S P 2 9 Q T 2) in terms of non-infinitesimals. By similar triangles, he has Q T _ PF Qx PE

Pv PC - -Px PE "

and

square of the distance (Proposition 12 [6, p. 57] and Proposition 13 [6, p. 60]). There is absolutely no evidence that N e w t o n first used his calculus, developed some 20 years before he wrote the Principia, to treat these problems and then recast his work in the geometric termsJ It was primarily Varignon (1654-1722) w h o first applied the (Leibnizian) calculus to curvilinear motion [2]. In closing I wish to acknowledge the assistance of G. Donald Chakerian, w h o suggested several improvements in the exposition, and of A n t h o n y Barcellos, w h o prepared the illustrations using CoHort Graphics.

(11)

References

Also, Q R = Px.

(12)

By Fact 2, Qv 2

DC 2

Pv 9 vG

PC 2"

(13)

and, by Fact 6, lira ~Q x = 1. Q--*P

(14)

Combining (11), (12), (13), and (14) with some algebra yields lim

QR

Q---~P S p 2 9 Q T 2

=

PE 3 - 2Sp2 9 pF 2 9 DC 2"

By Facts 4 and 3, PE and PF 9 DC are independent of P, so the centripetal force is inversely proportional to the square of the distance. N e w t o n also shows that if an object moves in a hyperbola or parabola, then the centripetal force directed toward a focus is again inversely proportional to the

1. Apollonius, Conics, in Great Books of the Western World, Vol. 2, Chicago: Britannica (1939). 2. M. Blay, La Naissance de la Mdcanique Analytique, Paris: Presses Universitaires de France (1992). 3. I. B. Cohen and A. Koyr6, Introduction to Newton's Principia, Cambridge, MA: Harvard University Press (1971). 4. I. B. Cohen and A. Koyr6, Isaac Newton's Philosophiae naturalis Principia Mathematica (with variant readings), Vol. 1, Cambridge, MA: Harvard University Press (1972). 5. M. Nauenberg, Hooke, orbital motion, and Newton's Principia, Am. J. Phys. 62 (1994), 331-350. 6. I. Newton, Mathematical Principles (F. Cajori, ed.), Berkeley: University of California Press (1934). 7. J. L. Russell, Kepler's laws of planetary motion: 1609-1666, Br. J. History Sci. 2 (1964), 1-24. 8. D. T. Whiteside, Newton's early thoughts on planetary motion: a fresh look, Br. J. History Sci. 2 (1964), 117-137. Mathematics Department University of California at Davis Davis, CA 95616-8633 USA e-mail: [email protected]

1The g e o m e t r i c t e r m s look like calculus to m e . - - E d i t o r ' s Note. THE MATHEMATICALLNTELLIGENCERVOL, 18, NO. 2, 1996 1 1

Statistical Sampling and Fractal Distributions Ken Gerow and John Holbrook

Introduction We report here on work that has its origin in a problem of statistical sampling and that has extended over more than a few years. There are connections with several other areas of mathematics, including convex analysis, tomography, and, perhaps more surprisingly, fractal geometry and iterated function systems. This summary stresses these connections and the more visual aspects of the work. To introduce the ideas we direct the reader's attention to Figure 1. There we see a complicated starlike object sitting inside the regular hexagon. As we shall see, each point in the hexagon encodes three (dependent) coordinates Xk summing to 0. These coordinates provide a set of sampling values that are exactly "balanced"; in the second section of this article we shall say something about the statistical advantages of choosing the balanced sampling points according to a particular distribution within the hexagon, such as that shown in Figure 1. The "superstar" appearing in Figure 1 is a self-similar fractal in the sense of Mandelbrot [M]; it has dimension In 6/ln 3 ~ 1.631; and it is riddled with infinitely many jagged holes, each bounded by the classic Koch snowflake curve. The superstar inhabits a regular hexagon which we denote by M(3) in this article; think of 3 as the sample size of the corresponding statistical procedure. The superstar may be generated by an iterated function system (IFS), in the sense of Barnsley [B], involving the six maps that shrink (with contraction factor ~) the hexagon M(3) toward its six vertices. The superstar may also be viewed as the support of an uncountable family of extreme points in a certain convex body of probability measures. We'll discuss these matters in more detail a little later. The histogram at the base of Figure 1 records the frequency distribution of the horizontal component of 12

points as they are placed in the superstar by the IFS (or any other procedure that distributes points evenly over the superstar, that is, gives equal weight to each subsuperstar of a given size). A moment's reflection on the geometry of the superstar makes it clear that this verti-

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Verlag New York

Figure 1. Fractal superstar and marginal histogram generated by an iterated function system.

cally projected distribution must be uniform over the interval, and the histogram of Figure 1 (computed from an actual simulation of the IFS, with 1.5 million iterations) bears this out. By symmetry, this marginal uniformity will be obtained upon projecting along any of the three directions determined by the edges of the hexagon. Let us scale Figure 1 so that the hexagon M(3) has width 2, with the center of M(3) as the origin of coordinates. Then the histogram is based on the interval [-1, 1] and shows that the horizontal coordinate of a point X chosen "at random" in the superstar is a random variable X1 that is uniformly distributed over [-1, 1]. Along with X1 we have the marginals X2 and X3 determined by projecting along the nonvertical edges of the hexagon; each of these is uniform over [-1, 1], and jointly they have a special property: X 1 + X 2 q- X 3 = 0.

interpret Xk as X'Uk (k = 1,2,3) for any point (vector))~ in the hexagon. Clearly, each Xk E [--1, 1l, and (1) follows from ul + u2 + u3 = (0, 0). We refer to any set of random variables Xk, each uniform over [-1, 1] and satisfying (1), as a random balanced sample (RBS) with sample size n - 3. In the next section we discuss the statistical applications of such a structure. We may view the superstar of Figure 1 as one solution to a certain reconstruction problem in tomography: find a density or distribution of points in the plane that has uniform X-rays (projections) along each of the three directions determined by the edges of the hexagon. Clearly, such a distribution must be supported within the hexagon, and, clearly, there are additional restrictions (the density uniform with respect to area over the hexagon, for example, does not have uniform projections). On the other hand, a finite number of projections (only three here) usually admit many possible tomographic reconstructions, provided that they are consistent at all. This ambiguity 4an clearly be troublesome in medical tomography (CAT scans, etc.). Here it suggests that there is, in the analysis so far, nothing really special about the superstar solution. Indeed, as we shall see, there are many other solutions on the hexagon, and some are simpler or more natural than the superstar. Its virtue, aside from visual impact, is that the construction extends successfully from n = 3 to any larger sample size n. In some quarters, fractal geometry is dismissed as providing entertaining pictures but not much of substance to mathematics. The history of the present work suggests a different view. We have, in fact, reversed the order of our story; the earliest RBSs proposed were

(1)

This is a simple geometric property of any point within the hexagon, and depends only on measuring the Xk with appropriate orientations. To be precise, consider the cube roots of ~ i t y as unit vectors in the plane: ul = (1,0),u2=( -1~, ~ ) , U3 = ( - 1 , ~23). Each of these vectors is orthogonal to a pair of edges of M(3), and we can

X1 Figure 2. M(n) is the regular hexagon when n = 3. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

13

based on classical geometry, then the fractal solutions were developed in response to difficulties in extending the classical solutions to larger sample size.

essarily linear but has power series ~ O~k Xk, w e have l

f~

OQ

1

Od4

g(x) dx = ~0 + - - + - - + "'" 3 5 "

(6.1)

Random Balanced Sampling whereas Here we describe a simple class of sampling problems for which RBS distributions are especially well designed. Consider a relationship

oo

__

W = ~ o~kXk ~- ~

where

xk

=

l ~.~]

k=O

Y = g(X) + e,

(2)

where X E [ - 1, 1], g is some fixed (but unknown) function on [ - 1, 1], and e is an error term with mean 0. Such a relationship might, for example, be the hypothesis of a biologist studying tree height Y as a function of elevation X on a mountainside. If a field survey is made using X values from a balanced sample H

Xn),

X = (X 1.....

Z xk = O, 1

(3)

the average ~

1~

~- - n

Yk =

1~

g(Xk) + -~

(4)

yields an exact estimate of a0 if the hypothesized functiong(x) is linear: g(x) = ao + alx. The contribution from al is exactly 0 because of the '~oalanced" condition on our RBS: n

y xk=0;

(5)

1

that is, Y-differs from a0 only by the mean error term ~. Moreover, computing Y in this way ensures that it has minimum variance. Marginal uniformity is required of a RBS distribution to ensure that Y provides coherent information about g even when it is not linear. Marginal uniformity implies that Y is an unbiased estimator of the average value of g in any case:

=

g(x) dx. 2

(6)

-1

Thus, a RBS is designed to accommodate a simple linear mean model and simultaneously to be robust against misspecification of the model. In choosing among the various RBS that are available, we may look for a second, more subtle type of robustness. If g(x) is not nec14

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

(6.2)

"=

Now the uniform distributions__ of the individual Xj ensure that the expectations E ( X k) match the coefficients 1, 0, ~. . . . in__(6.1), and the balancedness condition requires that X k itself is 0. We may, in addition, attempt to minimize the variances of the higher-order X k. Intuition suggests this robustness may go along with a broad distribution of the RBS points over M(n), and there is some numerical evidence to support this view. In what follows, we consider a RBS more robust (for a given n) if its support [as a probability measure on M(n)] is of higher dimension. A more thorough discussion of the role of RBS distributions in sampling theory may be found in the theses [G1, G2] of the first author, and in ongoing work by him. Roughly speaking, we would not expect RBS procedures to have much advantage over independently chosen sample values Xk when the sample size n is very large, as the central limit theorem and related results ensure that (5) is nearly true with high probability. When n is very small, on the other hand, we shall see that there are "classical" constructions of RBS distributions that are entirely suitable. It is in the case of intermediate sample size that the fractal RBS and its IFS implementation appear to be most valuable.

Small Sample Size; RBSs with Classical Geometry It is clear that a RBS distribution within the hexagon M(3) must assign less weight toward the center than toward the boundary of the hexagon. In fact, one of the simplest ways to do this works perfectly well for n = 3, as Doug Robson pointed out when he first drew attention to the RBS problem (see [G1]). This approach defines the RBS by a density function (with respect to area) that is piecewise linear on the hexagon, with value 0 at the center and having a constant value c3 at each point of the hexagon's boundary. One way to express this precisely is to require that the density at sampling vector X be c3]]Xlloo,where IIX[[~ = max [Xk[ k

(7)

and c3 is adjusted so that the total mass over the hexagon is 1. A simulation of this piecewise linear RBS appears in Figure 3. In this and several of the other fig-

to discover that the analogous construction fails to give a RBS when n = 5, and that this cannot be fixed up even if we consider more general functions of IIXII~. PROPOSITION 1 (see [GH]). Consider the probability measure on M(n) that is determined by a density, with respect to (n - 1)-dimensional volume, of the form f(llXIlo~). For n = 3,4 this construction yields a RBS iff f(t) = Cnt for an appropriate constant Cn. For n = 5, on the other hand, there is n o choice o f f that yields a RBS. Presumably the construction fails for all larger values of n (Peter Bubenik has checked this for many values of n-> 6, and the pattern seems clear), so that with this technique we cannot move to larger sample sizes. In contrast, we recognized quite early in this investigation that there is a sort of degenerate RBS available for all sample sizes n. In the hexagon (i.e., for n = 3), this degenerate solution is obtained by placing a uniform linear measure along each oLtheedges of the "star of David" formed by the vertices of the hexagon. See Figure 4 for

Figure 3. The piecewise-linear RBS for n = 3.

ures, we have used an actual computer simulation of the sampling procedure as might be done in practice to obtain the sampling values. This gritty reality obscures, however, some of the fine structure of the distributions; it is not very clear from Figure 3, for example, that the underlying density is linear on each of the six equilateral triangles making up M(3). It is a simple exercise to compute the line integrals of this density for lines parallel to the edges of the hexagon, and one observes that the projected densities are indeed uniform. Such a piecewise-linear solution also works for n = 4, although the verification takes more work. The natural 3-dimensional model for M(4) comprises points _~ in the regular octahedron, with sample values Xk (k = 1. . . . . 4) determined by the position of X relative to the four pairs of parallel faces of the-octahedron. Thus, the density CdlIXII~ has value 0 at the center of the octahedron, has value c4 on each face, and is linear within each of the eight tetrahedra in the corresponding decomposition of M(4). The density that has to be integrated over a given plane passing through M(4) and parallel to a face is rather complicated, but it all works out: the projected density for each Xk is uniform. It is a shock, then,

Figure 4. The degenerate RBS (concentrated on the edges of the star) for n = 3. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

15

a simulation of this RBS. It's easy to check that each projected Xk is uniform o v e r [--1, 1], as required. This idea m a y be extended to arbitrary sample size n as follows. Let Z1 be u n i f o r m l y distributed o v e r [ - 1, 1], and set Zl

Z k -~ Ck

n-l'

where 2k - 3

Ck=--l+--

n-1

( k = 2 . . . . . n).

(8)

N o t e that the Ck are the centers of the subintervals obtained by dividing [ - 1 , 1] into n - 1 equal parts. Since Z~ Ck = 0, it is clear that Z~ Zk = 0. Thus, if w e define Xk = Zc(k) (k -- 1. . . . , n), where o- is a r a n d o m permutation of {1, 2 . . . . , n}, we obtain a balanced sample (Z~ Xk = 0). The marginal distributions are uniform over [ - 1 , 1] b y the following computation. Let I be any subinterval of [ - 1 , 1]; for convenience we a s s u m e that I lies in just one of the n - 1 subintervals centered at c2. . . . . Cn, n a m e l y the one centered at Ck. We m u s t show that Prob{Xi E I} : 1II/2. N o w n Prob{Xi E I} = ~ Prob{r

= j} Prob{Zj E I},

(9)

j=l

and only the terms j = I and j = k are nonzero. We evaluate (9) as 1 Prob{Z1 E I} + 1 Prob{Zk E I} n

n

• n< 2 J

] I[

n< 2/(n-1) J

2"

(10)

Figure 5 shows h o w this "degenerate" RBS lies within the octahedron M(4). In each case the degenerate RBS is s u p p o r t e d only on a one-dimensional subset of the (n 1)-dimensional M(n). In contrast, the RBS distributions discussed in Proposition 1 exploit (for n = 3,4) the full dimension of sample space M(n). We regard the relative dimension, i.e., the ratio of the dimension of the support of a RBS to n - 1, as a measure of robustness of the sampling procedure, for reasons already discussed. Another type of RBS based on classical g e o m e t r y was suggested b y Wiestaw Zelazko: an ajs radially symmetric density g(r) (where r = V x 2 + y2) o n the unit disc has uniform projections in all directions, so that, inscribing the disc in o u r hexagon M(3), w e obtain a RBS for n = 3. It is rather clear that such a density exists and that we must have g(r) ~ oo as r ~ 1. There are, however, hard and easy w a y s to compute g(r). The h a r d w a y is to perform the inverse Radon transform (or some

16

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

Figure 5. The octahedron M(4) with degenerate RBS (concentrated on the edges of six skew quadrilaterals).

equivalent calculation) to obtain g(r) = (2~r %/1 - r2) -1. It is easier to recall a classic p r o p e r t y of surface area on the sphere: the surface area cut off b y parallel slices depends only on the distance b e t w e e n the slices. This means that the radially symmetric RBS for n = 4 is especially simple: it is the appropriately normalized surface area measure on the inscribed sphere of the octah e d r o n M(4). Furthermore, w e can project this measure in two stages if we wish: first onto any plane, then onto any line in that plane (obtaining the uniform distribution on the appropriate interval). Thus, the planar projection m u s t give us the RBS for n = 3. In other words, the mass projection of a spherical balloon onto a plane gives us the (radially symmetric) density g(r) we seek in the disc. Figure 6 illustrates these relationships. Although the disc does not cover all of M(3), the relative dimension (or robustness) is 1. For the radially symmetric RBS with n = 4, h o w e v e r , we have relative dimension 2. It is not hard to s h o w that for n > 4, there can be no radially symmetric RBS. Extreme RBS Measures It is clear that different RBS measures (for a given sample size n) can be "blended" to p r o d u c e additional solutions to the RBS problem; in other words, since the conditions of marginal u n i f o r m i t y are linear, the set RBS(n) of RBS measures is convex in the space of probability measures on M(n). We are led, therefore, to fol-

venient to have the analog of the vectors ul, u2, u3 ~ R 2 used in the introductory section of this article. These are unit vectors

Ul. . . . . Un ~ R n-1 such that Uk'Uj

"'*J|'~IFIIIT'J'

*"I I' ,r

'l *' ~I' '* ir'i~i"i

~. i~;[~ ',Iri"~IIHr'

I

,,i

9 "'~,I

,rl- ' IL-I,I , ",D l

r'

*q'q

Figure 6. D i s c or b a l l o o n ? D e p e n d i n g on w h i c h y o u see, this is the radially s y m m e t r i c RBS for n = 3 or for n = 4.

low the cardinal rule of convex analysis: look for extreme points. To this end, let us first be more careful about our representations of M(n). For m a n y purposes it is convenient to think of M(n) as a (convex) subset of Rn:

M(n) =

{X E [ - 1 ,

1]n: ~. Xk = 0}.

(11)

1

From this point of view, the fact that M(3) "is" the regular hexagon answers the classic visualization puzzle: what is the cross-section through the center of a cube and perpendicular to the line joining opposite corners? It is easy to see that extreme points of M(n) can have at most one Xk ~ + 1, so that for even n = 2m the extreme points are vectors X with m coordinates equal to I and the other m equal to - 1 . In the o d d case, n = 2m + 1, an extreme point will have one additional coordinate equal to 0. When presenting M(n) as a subset of R n - 1 it is con-

-1 n-1

(k ~ j).

(12)

In terms of them, M(n) consists of those X E R n-1 such that iX.UkI-< 1 for each k. With Xk = X'Uk, we do have the balanced condition (5), for (12) implies that Z~ Uk is the zero vector. For example, if n = 4, the uk form the vertices of a regular tetrahedron, and w e see M(4) as a regular octahedron (see Figure 5) u p o n implementing the conditions IX'Ukl --< 1 for 1 --< k -< 4. Each of the six quadrilaterals forming the RBS of Figure 5 has edges parallel to the Uk. The convex b o d y RBS(n), on the other hand, is well b e y o n d h u m a n powers of visualization. We will have a go at it anyway. It sits in the infinite-dimensional space of probability measures on M(n) and is strikingly complex, as we shall see. One should probably not expect to describe all of the extreme measures in RBS(n); but one notes that extreme measures must h~fve "small support." In particular, the s u p p o r t of an extreme RBS cannot include an open set in R n-1. We illustrate this fact in the hexagon (n = 3). Suppose, for example, that g is an RBS density that is positive within some o p e n disc in the hexagon. Let C1. . . . , C6 be the vertices~ in cyclic order, of a smaller regular hexagon located in the disc and with edges parallel to those of M(3). Consider the signed measure /~=

31 -- 3 2 q - 33 -- 3 4 q - 35 -- 36,

(13)

w h e r e 3k is the unit point mass at C k. It is easy to see that/~ has zero projection on each of the Uk. It follows that for any (integrable) function h the convolution/~*h also has zero projections. We m a y thus perturb g to g + /~*h to obtain new RBS measures, p r o v i d e d only that h is small e n o u g h (in srtpport and values) to ensure that g +/~*h ~ 0. But g is the average of these new measures, so it is not an extreme measure in RBS(3). All this suggests that we look for extreme points a m o n g the "degenerate" RBS measures, and, indeed, one can s h o w that either one of the triangles forming the star in Figure 4 bears an extreme measure. Similarly, each skew quadrilateral of the RBS in Figure 5 represents, w h e n suitably renormalized, an extreme point of

RBS(4). Such extreme RBS measures can be modified b y subdivision and reorientation to generate a wealth of additional extreme points. In the case n = 3, this process is suggested in Figure 7, w h e r e w e see some of the possible ways to subdivide the original triangle into three smaller ones, inverting the triangles at will. Such subdivision a n d / o r inversion m a y be continued indefinitely. THE MATHEMATICALINTELLIGENCERVOL. 18, NO. 2, 1996

17

of the extreme measures constructed above. Although the superstar arose naturally in this statistical application, it is also an attractive geometric object in itself; thus it was perhaps not so surprising to find that the superstar appeared as an exercise in Barnsley's work on iterated function systems (see [B, exercise 4.13]). We shall exploit the IFS connection in a later section. On-Off Densities (Bonehead Tomography?)

\

\

/ \

/ \

/ \

/ \

/

Figure 7. Construction of extreme measures in RBS(3).

PROPOSITION 2. The extreme points of RBS(3) include a continuum of measures obtained by successive subdivision and~or inversion of the basic triangle. The superstar of Figure 1 is simply the continuation of this chain of thought; it is the union of the supports

It is surely disturbing to recognize that any CAT scan can be interpreted, in principle, in terms of air and bone (no soft tissue). The remarkable theorems of Shepp, et al. (see [GKRS]) guarantee the existence of {0, b}-valued densities that have the same projections on u~. . . . , un as any given density on M(n) with values in the interval [0, b]. In particular, there must exist on-off densities replacing the bounded RBS densities constructed by the piecewise-linear technique when n = 3, 4. The proofs of the general results in [GKRS] (based, by the way, on convex analysis and extreme points) give little clue as to what these on-off RBS densities might be. Nevertheless, following a presentation of the above material in [Ho], Jorge Salazar quickly produced the simple on-off RBS shown in Figure 8(a). This solution departs from our (unspoken) convention that RBS measures respect the symmetries of the hexagon, but among the convex combinations of the 2 r rotations of Figure 8(a) we find the average, which is symmetric, as in Figure 8(b). The symmetrized Salazar RBS of Figure 8(b) has several interesting features. It may be regarded, for example, as a projection of the three-dimensional distribution defined by the uniform surface area measure over the regular octahedron; we project on the plane through any

Figure 8. (a) Salazar's asymmetric on-off RBS; (b) Salazar symmetrized, by taking the average of the three distinct orientations of (a). 18

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

(b)

r

1

Figure 9. (a) The symmetric on-off RBS of Dalnoki-Veress; (b) demonstrating the uniform projection property of this RBS. one of the faces. The s y m m e t r i z e d Salazar density takes four values, say 0, b/3, 2b/3, and b. To obtain a symmetric on-off density on the hexagon, we m a y try to match the constant 2b/3 density on each of the six tri-

angles w h e r e it occurs by a 0-b density with the same projections on the Uk; reversing the roles of 0 and b, we w o u l d then have also a match for the constant b/3 density on the inner triangles. Kari Dalnoki-Veress followed THE MATHEMATICAL INTELL1GENCER VOL. 18, NO. 2, 1996

19

Figure 10. A picture of RBS(3) that does not do it justice.

this plan to discover the striking on-off RBS density shown in Figure 9(a), with its intricate self-similar substructure. Figure 9(b) demonstrates graphically the uniform projection property of this RBS. We summarize our exploration of the rich variety within RBS(3) by presenting Figure 10 as a fanciful picture of the infinite-dimensional convex body, labeled with some of features we have noted above. The reader 20

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

may find it amusing to search for some of the many additional extreme RBS that remain to be devised. For example, as densities positive throughout M(3) exist, it is clear there must be extreme points in RBS(3) placing mass near the center of the hexagon or at any other specified location. Jorge Salazar and Peter Bubenik have proposed some attractive solutions to this puzzle, and it seems likely there are many different classes of extreme RBS.

Large Sample Size; Fractal RBSs

Although we have constructed a wealth of solutions to the RBS problem for a small sample size n, w e conspicu o u s l y lack directions on h o w to proceed usefully to large n. In fact, we f o u n d that several of our m e t h o d s face clear obstructions to increasing n (the radially symmetric RBS and those d e p e n d i n g on IIXll~). Others do extend, but with smaller and smaller relative dimension (robustness). As far as w e know, the best w a y to proceed is to generalize the fractal RBSs, such as the su-

perstar of Figure 1. With the help of appropriate iterated function systems (IFSs) w e can conveniently generate RBS measures with fractal dimension asymptotic to the m a x i m u m possible dimension n - I as n ~ o~ (i.e., with robustness tending to 1). Barnsley a n d his co-workers (see [B] and [BH]) have d e v e l o p e d iterated function systems with a view to image compression. Some of the basic ideas are f o u n d in the w o r k of Hutchinson [Hu]. To introduce the version most suitable for our present application, let us describe in more detail h o w it works in the generation of Figure

Figure 11. The fourth stage in an approximation to the support of a fractal RBS distribution on the octahedron M(4). At each stage, a tetrahedral hole is made in the center of each face of the octahedra remaining from the previous stage. The fractal dimension is In 6/ln 2 ~ 2.585 THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

21

1. The hexagon M(3) has six vertices corresponding to samples X having coordinates chosen from {1, 0, -1}: V1 = (1, 0, -1), V2 ~- (0, 1, --1), V3 ~- (-1, 1, 0), V4 m (-1, 0, 1), V5 = (0, - 1 , 1), V6 = (1, -1, 0). Consider the six maps fk: M(3) ~ M(3) defined by

quences generated by this IFS accumulate) has dimension given by (15), namely, (17). Finally, a weak form of Stirling's formula,

NN+I/2e

N ~ N ! <-- NN+I/2e

N+I,

(18)

is enough to show that fk(X)

=

3!

X

q- 32 Vk

(k----

1. . . . ,6).

(14) 1

Each fk is a similarity map that sends the hexagon into a hexagon of one-third the size nestled in the kth corner of the original hexagon. Consider the IFS defined by these six maps, each chosen with equal probability 1/6. The corresponding "chaos game" goes as follows: starting from any point P0 in M(3), define P1, P2. . . . by Pi+ 1 = fk(Pi), where k is chosen each time independently and at random from {1, 2. . . . ,6}. Because the fk(M(3)) are essentially disjoint, the general features of IFS theory (as developed by Barnsley in [B], for example) ensure that (with probability 1) the sequence {Pi} accumulates on a fractal object (in this case the superstar) having dimension D = In(# of maps) ln(1/c)

(15)

where c is the contraction factor of the similarities. Here we have six maps and c = 1/3, so that D = In 6/ln 3 (~1.631). For the superstar, the marginal uniformity is rather clear geometrically. More generally, we may rely on "Hutchinson's equation," characterizing the invariant measure of such an IFS. For large even n, the following simple construction suffices. PROPOSITION 3. Let n be even: n = 2m. Then M(n) has ( mm ) vertices (extreme points) V consisting of all possible vectors with m coordinates equal to 1 and m equal to -1; and the IFS defined by the ( 2ra m ) maps fv: M(n) ~ M(n), where fv(X) = 1X + 1V

(16)

generates a RBS measure tx as its invariant measure. The fractal dimension of (the support of) I~ is given by In

2m (m)

D~ - - In 2

(17)

and hence is asymptotic to the maximal dimension (n - 1). Figure 11 depicts an approximation to the support of this RBS when n = 4 [so that M(n) is the octahedron]. Since (when n = 2m) two different vertices V, V' have IIv - v'll~ = 2, it is clear that the maps defined by (16) have essentially disjoint images fv(M(n)). Hence, the support o f / z (i.e., the fractal object on which the se22

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

Dn >- 2m + ~

(I In m ) - 2

In 2

(19)

Certainly, then, the "robustness" Dn/(n - 1) ~ 1. For odd values of n, and to increase robustness, it turns out that we need to consider maps that depend not only on the vertices of M(n) but also on other "locators" within M(n). In addition, we need the more general type of IFS where the maps applied to generate the random orbit are chosen with unequal probabilities. These are the IFSs that produce "shading" in Barnsley's application to image reconstruction (see [B]). These ideas are explored for the RBS problem in the thesis of Rostant Ramlochan [R]. Finally, we note that the IFS approach does more than simply establish existence of appropriate RBS measures. With a simulation of the IFS in progress, one can use the current point of the random orbit as a sampling vector X whenever one is required. References

[B] M. Barnsley, Fractals Everywhere, New York: Academic Press 1988. [BH] M. Barnsley and L. Hurd, Fractal Image Compression, London: AK Peters, 1993. [G1] K. Gerow, An Algorithm for Random Balanced Sampling, University of Guelph, 1984. [G2] K. Gerow, Model-unbiased, Unbiased-in-general Estimation of a Regression Function, Cornell University, 1993. [GH] K. Gerow and J. Holbrook, Construction of random balanced samples, working paper, 1990. [GKRS] S. Gutmann, J. Kemperman, J. Reeds, and L. Shepp, Existence of probability measures with given marginals, Ann. Prob. 19 (1991), 1781-1797. [Ho] J. Holbrook, Snowflakes and statistics, lecture-demonstration at NATO Advanced Study Institute "Fractal Geometry and Analysis", Montreal, July 1989. [Hu] J. Hutchinson, Fractals and self-similarity, Indiana Univ. [. Math. 30 (1981), 713-747. [M] B. Mandelbrot, The Fractal Geometry of Nature, San Francisco: W. H. Freeman, 1983. [R] R. Ramlochan, Iterated Function Systems and Fractal Sampling, University of Guelph, 1990. Department of Statistics University of Wyoming Laramie, WY 82071-3332, USA [email protected] Math/Stat Department University of Guelph Guelph, Ontario, NIG 2W1 Canada [email protected]

Jeremy J. Gray* Many-valued Logics

People usually deal with propositions in two ways. In the "real" world they reach such judgements about them as True, False, Probable, Don't Know, and such legal verdicts as "beyond reasonable doubt" and, in Scotland at least, "not proven." But in Logic all propositions are usually presumed to be timelessly True or False. Dissatisfaction with this state of affairs is ancient. Aristotle hesitated over the truth status of claims about events in the future; later the Stoics pushed the modern view. In the later nineteenth century mathematicians, most notably in Britain, established a calculus of logic, and these questions were raised anew. It became possible to deal algebraically with such matters as implication and negation. In 1870 William Jevons even described a machine, called his logical piano, that would automatically implement arguments about classes. It is therefore not surprising that, though the thorough-going acceptance of many-valued logics is an event of the 1920s, there were numerous predecessors around 1900. One was the Scotsman Hugh MacColl, who in 1897 sought to extend the logical calculus to modal questions (necessity, impossibility, contingency). He even called his system three-dimensional, to distinguish it from the more conventional ideas of Schr6der and Venn. Another was the eccentric American C.S. Peirce. His account of truth-tables and their use in studying the propositional calculus was published in his [1885], and seems to have had some influence (Frege had earlier made passing use of them in his Begriffschrift). But failing to publish was more Peirce's style, and although he outlined a trivalent logic in 1902 he did not publish it; it became clear only in the 1960's that by 1909 Peirce had discovered the three-valued negations of Lukasiewicz and Post and ex-

*Column editor's address: Faculty of Mathematics, The O p e n University, Milton Keynes, MK7 6AA, England.

tended his truth-tablea to'embrace a three-valued logic. He seems to have been influenced by MacColl's work, with which he was familiar, but not to have pursued the idea with any degree of commitment. It is difficult to evaluate his influence, although it has been claimed that it reached as far as Poland. A third figure was the Russian Vasil'ev, who between 1910 and 1914 wrote a number of papers on an imaginary world in which objects may be described as either A, not-A, or both A and not-A. In some ways this also foreshadows later manyvalued logics, but the many-valuedness resides in the nature of the objects rather than the truth status of propositions about them. Many-valued logics, where sentences may have truth values other than True and False, were successfully created in Poland and New York some 75 years ago. In Poland their inventor was Jan Lukasiewicz. He first

Logic was studied in Poland because, first, the Church could not understand it, and after the w a r the P a r t y could not understand it either. publicly outlined his ideas in 1920 in a talk he gave at the Polish Philosophical Society in Lvov. He was motivated by the existence of statements which are only possibly true, such as statements about the future. In order to avoid a determinism he saw as implicit in statements like "It will rain in Cairo on January I in the year 2001," he proposed that they be given a new truth status of Possible. In this way he also allowed true statements to be timelessly true. Even if there is no truth in the old joke that logic was intensively studied in Poland because, first, the Church could not understand it, and after the war the Party could not understand it either, still their invention owes much to the situation in Poland. The situation of Polish logicians and mathematicians has been described by Duda [1996], from which much

THE MATHEMATICALINTELLIGENCERVOL. 18, NO. 2 9 1996 Springer-VerlagNew York 23

of the information in this article is taken, and Kotarbinski (in S. McCall [1967]). The problems Polish intellectuals faced throughout the nineteenth century m a y be gauged from the fact that Warsaw University was f o u n d e d in 1816, closed in 1832, refounded in 1862, closed and reopened in 1869 as a Russian university, evacuated in 1915, and established in 1915 as a Polish university. In 1900, the country was still divided between Austria (where there were two Polish universities, Cracow and Lvov), Prussia (where there were none in the Polish part of the country), and Russia (where Warsaw was). Many patriotic-minded youngsters went abroad to study. Those w h o most actively changed the situation were the distinguished topologist Wac/aw Sierpiriski and Z y g m u n t Janiszewski. Sierpirlski became a professor at Lvov University in 1910, and soon decided that Polish mathematics would do better if a greater n u m b e r of mathematicians w o r k e d in one area. Janiszewski, who came to Lvov in 1912, agreed, and the 6-page article he wrote [1917] for a special volume on the needs of science in the future state of Poland became a p r o g r a m for the next generation of Polish mathematicians. In it he argued that to make the best of scarce resources it would be necessary to found a strictly scientific journal devoted exclusively to one of those branches of mathematics in which we have many outstanding, really creative workers. Such a journal would become indispensable for everyone working in that branch of mathematics, it could find readers everywhere, and in a short time it would attract serious collaborators from abroad. (Quoted in Duda [1996].) At the end of the paper, Janiszewski stressed the need for creating a proper atmosphere of collaboration and mutual confidence within the group: We can gain it only by concentrating the majority of our mathematicians on one branch of mathematics. Since this is already happening, it will only be necessary to help it. (Quoted in Duda [1996].) The ethics of the time were referred to as the "ten c o m m a n d m e n t s " (Marczewski [1962b, 1 Dec]), and it was plainly a high-risk strategy to choose a m o d e r n part of mathematics with no long tradition behind it, and neglect analysis, algebra, and geometry to concentrate the efforts of active mathematicians upon one domain. But conditions were favourable. Warsaw University h a d just been reopened with strong support from the state, society, and its n e w students. Janiszewski and Mazurkiewicz became the first professors of mathematics; Sierpi~ski joined them at the end of 1918. As Sierpirlski later wrote: When in 1919 all three of us--Janiszewski, Mazurkiewicz, and myself--found ourselves together as the first professors of mathematics in the revived Polish university in Warsaw, we decided to realise the idea of Janiszewski to publish in Warsaw, in foreign languages, a journal devoted to the the24

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

ory of sets, topology, theory of functions of a real variable, and mathematical logic. In that way Fundamenta Mathematicaecame into existence. (Sierpinski [1963], quoted in Duda [1996].) The editorial committee was composed of three mathematicians (Janiszewski, Mazurkiewicz, Sierpirlski) and two logicians (Jan Lukasiewicz and StanisYaw Lesniewski). This reflected the strong position of studies in logic and the foundations of mathematics in Poland, a n d the idea of alternating volumes on set theory and mathematical logic was contemplated. In practice, however, papers on mathematics proper greatly o u t n u m b e r e d those on logic, and in 1928 the two logicians left the committee. The active study of logic in Poland goes back to 1895, w h e n the philosopher Kazimierz Twardowski lectured at Lvov on algebraic logic. He was a gifted teacher, and communicated his enthusiasm to Lukasiewicz, w h o also brought a knowledge of Greek and Latin and an interest in probability theory to enrich the mix. He set out to do for logic what the discovery of non-Euclidean geometry had done for geometry. To this end he reconstructed Aristotelian logic, freeing it from what he re-

He set out to do for logic what non-Euclidean geometry had done for geometry. garded as later accretions and misunderstandings. He argued influentially that Aristotle's work belonged to the same sphere of ideas as the m o d e r n predicate calculus, and that it was the later Stoics, led by Chrysippus, who had gone beyond Aristotle's syllogistics to anticipate the more fundamental propositional calculus. Nonetheless, he called his n e w logic non-Aristotelian. In this logic, any proposition m a y either be True (1), False (0) or Possible (1). To explore it, it is best to begin as Lukasiewicz himself did with a brief s u m m a r y of ordinary logic. The basic logical operations, from which all others m a y be deduced, are 'if p, then q,' and negation, 'not-p.' Lukasiewicz wrote these as Cpq and Np. The rules governing them are C 0 0 - - C 0 1 = C l 1 = 1 and C 1 0 = 0 , NO = 1, N1 = 0, which Lukasiewicz summarised in matrix form as CO 0 1 1 0

1N 1 1 1 0

More-or-less common-sense arguments led Lukasiewicz in the three-valued case to this table: C 0 2 1

0 1 2 0

89 1 1 '2

1 1 1 1

N 1 12 0

In 1921 in lectures at W a r s a w University, Lukasiewicz raised the question of defining a notion of possibility in general rather than the narrower concept of p u r e possibility used above. Alfred Tarski, then still a student, solved the problem with this definition of "it is possible that p," written "Mp":

M p = CNpp. Lukasiewicz commented: Expressed verbally this says: "it is possible that p" means "if not-p, then p." One must grasp the intuitive meaning of the definition. The expression "CNpp" is according to the three-valued matrix false if and only if "p" is false. Otherwise "CNpp" is true. Thus we obtain the equations: M0=0,

M12=1, M I = I .

Hence, if any proposition cr is false, the proposition "it is possible that c~" is false too. And if c~is true, or if takes the third value, that of possibility, then the proposition "it is possible that c~" is true. This agrees very well with our intuitions. (J~ukasiewicz [1930] in McCall [1967], p. 55.) H e went on to note that "CNpp" is equivalent to "p" in two-valued logic but not in three-valued logic. The other inventor of m a n y - v a l u e d logic was also Polish, but Emil Leon Post had been living in America since the age of 7. Van Heijenoort distinguished his account from Lukasiewicz's on the grounds that Post's interest was almost exclusively mathematical. It formed part of his doctoral thesis at Columbia University in 1920 (Post [1921]) w h e r e he also p r o v e d the consistency and completeness of the propositional calculus as presented by Whitehead and Russell. The p a p e r makes systematic use of the idea of truth tables, used, as we saw, b y Lukasiewicz, of w h o s e w o r k Post was u n a w a r e (it is another case of simultaneous discovery). As Lukasiewicz was also to do, Post defined an m-valued logic, with values tl < t2 < . . . < tin. Negation was redefined to cycle the truth values, so Post's definition differs from that of Lukasiewicz, and the e x t e n d e d "or" takes the higher of the two truth values of the propositions it joins. Neither invention seems to have succeeded in escaping the closed world of mathematical logic. Even there opinion is divided as to their merits. Zbigniew Jordan hailed it in these terms: "Without any d o u b t it is a disc o v e r y of the first order, eclipsing everything d o n e in the field of logical research in Poland" (quoted in McColl [1967], p. 389). But the Kneales in their history of logic [1962] observed that even 3-valued logic departed so far from o r d i n a r y reasoning as to be without a n y implication for our understanding of True and False. In between are those w h o observe connections with Brouwer's intuitionistic logic, which also denies the "law" of the excluded middle, and w h o h o p e for connections to q u a n t u m logic. To enter the "real" world, many-valued logic had to

be invented a third time, by Lofti Asker Zadeh, w h o was born in Azerbaijan in 1922 and took his doctorate in electrical engineering from Columbia University. In 1965, while at Berkeley, he published a p a p e r on f u z z y sets from which the m o d e r n revival dates. Since then the subject has attracted a growing n u m b e r of practitioners, and a n u m b e r of detractors, w h o claim that the subject is merely probability theory with catchy names. Interestingly, among those w h o s u p p o r t Zadeh is the H o n d a Corporation, which awarded him the H o n d a Prize in 1989 for contributions to Japanese technology. A case, perhaps, not so much of years ago as years to come?

Bibliography Duda, R., 1996, Fundamenta Mathematicae and the Warsaw school of mathematics, in L'Europe mathdmatique, Goldstein, C.; Gray, J.J.; Ritter, J. (eds), Editions de la Maison des Sciences de l'Homme, Paris. Janiszewski, Z., 1917, O potrzebach nauki w Polsce [On the needs of science in P'61and], in Nauka polska', jej potrzeby, or-

ganizacja i rozwoj [Science in Poland, needs, organisation and development], Warszawa, p. 11-18, and Janiszewski, Z., 1962. Oeuvres choisies, PWN, Warszawa, p. 5-14. Kneale, W. and M., 1962, The Development of Logic, Oxford University Press, Oxford. Marczewski, E., 1962, Dziesiecioro przykazan [Ten commandments], Polityka nr 48 300, from 1 Dec 1948, reprinted in Wiadom. Mat. 22 (1980), p. 197-202 and Xierowanie praca zespolowa w nauce [Directing a collective work in science], ed. A. Matejko, PWN, Warszawa, 1967, p. 107-11. McCall, S. (ed.), 1967, Polish Logic 1920-1939, Oxford University Press, Oxford. Peirce, C.S. 1885. On the algebra of logic, American Journal of Mathematics, 7, 180-202. Post, E.L., 1921 Introduction to a general theory of elementary propositions, American Journal of Mathematics, 43, 163-185, reprinted in J. van Heijenoort, [1967], 264-283. Sierpinski, W., 1963, Polish School of Mathematics, Polish Perspectives 68, p. 25-35. Van Heijenoort, J., 1967, From Frege to G6del; a Source Book in Mathematical Logic, Harvard University Press, Cambridge Mass. Faculty of Mathematics The Open University Milton Keynes MK7 6AA England

THE MATHEMATICAL INTELLIGENCER VOL, 18, NO. 2, 1996

25

Chebotar

v and his D e n s i t y Theorem 1 P. Stevenhagen and H. W. Lenstra, Jr.

Introduction

Life

The fame of the Russian number-theorist Nikolai Grigor'evich Chebotar6v 2 (1894-1947) rests almost exclusively on his proof, in 1922, of a conjecture of Frobenius, nowadays known as Chebotarr density theorem. Algebraic-number-theorists have cherished the theorem ever since, because of both its beauty and its importance. In the present article we introduce Chebotar6v and his theorem. Drawing upon Russian sources, we describe his life and the circumstances under which he proved his density theorem. Two characteristic examples are given to illustrate the nature of his other work. Next we explain the content of his theorem, reducing to a minimum the specialized terminology in which the theorem is usually couched. We shall see that the key idea of Chebotar6v's proof enabled Artin to prove his reciprocity law; in fact, had history taken a slightly different course, then Chebotar6v would have proven it first. For the connoisseur, we give, in an appendix, a paraphrase of Chebotar6v's proof of his density theorem. It uses no class field theory, and it is appreciably more elementary than the treatment found in current textbooks. We shall not discuss the important role that Chebotar6v's density theorem plays in modern arithmetic algebraic geometry. The interested reader is referred to [34] and [35].

Nikolai Grigor'evich Chebotar6v was born in Kamenets-Podolsk on June 15, 1894; on June 3 according to the Julian calendar that was still in use in Russia. His father, Grigorii Nikolaevich, served in the Russian court system in several Ukrainian cities and was president of a district court when the 1917 revolution interrupted his career. It left him stripped of his status and reduced to poverty, and he died of cholera in Odessa in 1922. Nikolai had one younger brother, GrigoriL a doctor who was seen in the White Army during the civil

1The first author thanks I. R. Shafarevich and A. G. Sergeev for providing biographical material on Chebotar6v. The second author was supported by NSF u n d e r grant No. DMS 92-24205. Part of the work reported in this article was d o n e while the second author was on appointment as a Miller Research Professor in the Miller Institute for Basic Research in Science. D. J. Bernstein, J. A. Buchmann, G. H. Frei, A. C. P. Gee, S. J. P. Hillion, A. Schinzel, and V. M. Tikhomirov kindly p r o v i d e d assistance. 2The transliteration of Cyrillic names in this paper follows the current Mathematical Reviews standard.

26 THE MATHEMATICALINTELLIGENCERVOL.18, NO. 2 9 1996Springer-VerlagNew York

w a r following the revolution. H e emigrated to Yugoslavia and never r e t u r n e d to the Soviet Union. Nikola~ received an upper-class education that was strictly controlled b y his mother. It is no coincidence that mathematics, a d o m a i n b e y o n d her control, became NikolaYs favorite pastime w h e n he was 15 or 16 years old. He was often unable to attend school d u r i n g this time, as he suffered f r o m pleurisy, and in the winter of 1910-1911 he was taken by his m o t h e r to the Italian Riviera to recover f r o m pneumonia. In 1912 he gained admission as a student in mathematics to the university in KieV, then k n o w n as the University of the Holy Vladimir. He was a student of D. A. Grave, as were B. N. Delon6, w h o later tried unsuccessfully to lure Chebotar6v to Leningrad, and Otto Shmidt, w h o w o u l d become a r e n o w n e d group-theorist as well as vice president of the A c a d e m y of Sciences. Grave was a former student of C h e b y s h e v and Korkin, and at that time the only true mathematician in Kiev. In these years, NikolaYs mathematical interests took shape. Despite the difficulties arising from World War I, which necessitated the t e m p o r a r y relocation of the university to Saratov, he g r a d u a t e d in 1916 and became Privatdozent after his magister's exam in 1918. H e continued to live like a student, earning m o n e y from private lessons and teaching in high schools. In 1921 he m o v e d to Odessa to assist his parents, w h o were subsisting there u n d e r miserable conditions. After his father's death, his m o t h e r eked out a living b y selling cabbage at the market. Despite professional and economic s u p p o r t from local mathematicians such as Shatunovski~ and Kagan, Nikolai had difficulties finding a suitable position in Odessa: the mathematics there was focused primarily on foundational issues, and these were alien to NikolaYs interests. Then came the s u m m e r of 1922. Chebotar6v recalls the circumstances in a 1945 letter to M. I. Rokotovskii [8], w h o had tried to interest him in his plans for a thesis on the working e n v i r o n m e n t of scientists: In real life, scientists come in as many varieties as there are species of plants. You describe a tender rose, that needs a supporting stake, fertilized soil, regular watering, and so on, in order to grow. Our harsh reality would more likely yield thistles, which produce somewhat crude but beautiful flowers under all conditions. What would our science be like, if our scientists could only work in silence or with "good, not too loud music" in their offices? I belong to the older generation of Soviet scientists, who were shaped by the circumstances of a civil war. I devised my best result while carrying water from the l~)wer part of town (Peresypi in Odessa) to the higher part, or buckets of cabbages to the market, which my mother sold to feed the entire family. This "best result" was Chebotar~v's density theorem. It was a spark from heaven, which would secure Chebotar6v a comfortable position in Soviet mathematics and immortalize his name in algebraic n u m b e r theory.

The difficult financial situation of the Chebotar6v household i m p r o v e d considerably in 1923, w h e n Nikola~ married the teacher and assistant physiologist Mariya A l e x a n d r o v n a Smirnitskaya. Working with a former student of the famous physiologist Pavlov, she m a d e a decent salary. The relationship with her motherin-law, w h o had insisted in vain on a religious marriage, seems to have been less than friendly. In 1924, Nikolai finally f o u n d a job at the Civil Engineering Institute in Moscow. Here he became acquainted with the Kazan mathematician N. N. P a r f e n t ' e v - - h i s first tie to Kazan. Nikola~ was icily received b y his Mosco~r colleagues; he found out that he occupied D. F. Egorov's position, and resigned after 7 months. Egorov, w h o had shaped the Moscow school of p u r e mathematics together with his student N. N. Luzin, had been dismissed for political reasons. Eventually, he would be arrested as a "religious sectarian" and go on a h u n g e r strike. Mortally ill, he w o u l d be transported to a prison hospital in Kazan in 1931, w h e r e NikolaYs wife h a p p e n e d to w o r k as a doctor [36]. He is p u r p o r t e d to have died at the Chebotar6v home. Back in Odessa, Nikolai got a b a d l y paid and ill-defined position as secretary for scientific research at an Educational Institute. His situation did not become more comfortable in 1926, w h e n his son, n a m e d Grigorii in accordance with family tradition, was born. Scientifically, however, he did v e r y well. A talented 17year-old boy, Mark Krein, w h o had come to Odessa, started w o r k i n g u n d e r Nikola~'s supervision and assembled e n o u g h students for a seminar on algebraic THEMATHEMATICALINTELLIGENCERVOL.18,NO.2. 1996 27

functions. When Nikolai left Odessa in 1927, Krein continued the seminar and founded a school in functional analysis. Before this, in 1925, Nikolai had been able to make his first scientific trip abroad, to the meeting of the German Mathematical Society (DMV) in Danzig, where he met E. Noether, Hensel, and Hensel's student Hasse. He traveled on to Berlin, visiting I. Schur, and to G6ttingen, where he met his countryman A. M. OstrovskiL Like Nikola~, Ostrovski~ was a student of Grave from Kiev. Grave had sent him abroad to continue his education, as Jews could not attend graduate schools in tsarist Russia. Nikola~ greatly impressed Ostrovski~ by providing an original solution to one of OstrovskiYs problems. We will discuss it later in this section. In 1927, Nikolai finally defended his doctoral dissertation, which was based on his 1922 density theorem, at the Ukrainian Academy of Sciences. He had earlier been invited by Delon6 to do so in Leningrad, but this was no longer possible: the bourgeois custom of the doctoral degree had been abolished in the Russian republic in 1926. Shortly after receiving his doctorate, Nikola~ was offered positions both in Leningrad, which already had a strong group of algebraists, and in the provincial town of Kazan, some 800 kilometers east of Moscow, where he would have to create his own school. At that time, the university of Kazan boasted its own journal, in which Nikola~ had already published a few papers, and a rich library. It had an international reputation because it regularly awarded a prestigious prize in geometry named after LobachevskiL the famous geometer who had worked in Kazan during the 19th century. Unfortunately, the independence of the provincial universities was gradually suppressed during the Stalin era, and by 1945 both the journal and the prize were abolished, as were most scientific contacts with capitalist countries. After some hesitation, Nikola~ finally chose Kazan, where he was to stay for the rest of his life. He left Odessa in December 1927. His wife and son followed in the spring of 1928. This put an end to the difficulties of sharing accommodations with NikolaYs mother, who went to live with her sisters in Krasnodar. She died in 1939. In Kazan, Nikola~ was able to create his own school of algebra, and his students obtained positions in several Soviet universities. During his Kazan period, his work gained ample recognition in the Soviet Union. He was elected corresponding member of the Academy of Sciences in 1929 and invited to speak at the All-Union congress in Leningrad in 1934. In 1943, he became Honored Scientist of the Russian republic. He was nominated for the Stalin Prize in 1943 and 1946, but received this coveted prize only posthumously, in 1948. It was awarded for his work on Hilbert's thirteenth problem concerning the impossibility of solving the 7th-degree equation by means of continuous functions of two arguments. In 1954 it turned out that one of his results on 28 THEMATHEMATICAL INTELLIGENCERVOL.18,NO.2,1996

N. G. Chebotari~v

this problem was incorrect, a counterexample being due to his own son GrigoriL who had also become a mathematician [22]. Chebotar6v's reputation did not remain confined to the Soviet Union. In 1932, he accepted the invitation to deliver a plenary address at the international congress in Zfirich. His talk, "Problems in contemporary Galois theory" ([7], vol. 3, pp. 5--46) marked the 100th anniversary of the death of Galois. Nikolai remained productive during the 20 years he spent in Kazan. The research papers in his collected works [7] address a wide range of problems--many in number theory and in his "official" specialty, Galois theory, but others in Lie groups, abelian integrals, the distribution of zeros of polynomials, and approximation theory. Apart from this, he produced course notes in advanced algebra, the calculus of variations, and topology. His textbook Osnovy teorii Galua (Basic Galois theory) appeared in two volumes in 1934 and 1937, together with a 1936 monograph Teoriya Galua that included results on the inverse problem and the theory of resolvents. A reedited and extended German translation of the first volume with inclusions from the monograph appeared

in 1950, after a 10-year delay caused b y the war [9]. NikolaYs interest in resolvents led him to s t u d y Lie groups. The result was his Teoriya grupp Li, the first Russian textbook on Lie groups, which a p p e a r e d in 1940. It was followed b y a p o s t h u m o u s l y published m o n o g r a p h Teoriya algebraicheskikh funktsiL In addition, Nikolai devoted a lot of energy to editing the collected works of Zolotar~v. H e initiated the publication of the collected works of Galois in Russian in 1936, whose translation was carried out by his favorite student N. N. Me~lman. Other projects of his, such as the creation of an encyclopedia of elementary mathematics, were to remain unfinished when, during the spring of 1947, Nikolai started suffering from a stomach cancer. An operation became inevitable. In June 1947 he was hospitalized in the Sklifosovskii Institute in Moscow. He survived the operation but died from complications 11 days later, on July 2. The Chebotar6v family played an i m p o r t a n t role in the academic social life in Kazan. The n e w spacious house they obtained in 1937 was a meeting place for students, scientific visitors, and other guests. Nikolai had his working place in the house s o m e w h a t surprisingly not a desk but a b e d - - a n d an extensive library of reprints consisting largely of the m a n y papers he reviewed for the Zentralblatt. During the war, the universities and certain academic institutions of M o s c o w and besieged Leningrad w e r e m o v e d to Kazan, and flocks of scientists c r o w d e d the university there. H o u s i n g was problematic. It was not u n c o m m o n for the Chebotar6v residence to have as m a n y as 20 overnight guests. Despite his aversion to administrative duties, Nikolai succeeded Parfent'ev as head of Kazan's d e p a r t m e n t of mathematics and physics in 1943. During the 1930s he had been the director of NIIMM, a scientific institute for mathematics and mechanics at the university. This function caused frequent disputes between Nikolai and the rector of the university. Otherwise, it seems that his easygoing character and his thoughtful politeness usually kept him out of conflict. We illustrate the style of Chebotar6v's mathematics b y presenting two results with which he was particularly pleased. The first is the solution to the problem posed to him b y Ostrovskii in G6ttingen. It held implications for the n u m b e r of singularities of certain lacun a r y complex p o w e r series on the b o u n d a r y of their domain of convergence [32]. Chebotar6v himself calls it ([8], pp. 5-6) "a v e r y m o d e s t result," mentioning the compliments the " g l o o m y and sombre" Ostrovskii m a d e to him on its accourtt, and observing that it "does meet the requirements of mathematical esthetics." PROBLEM. Let p be a prime number and ~ G C a primitive pth root of unity. Show that all minors of the Vandermonde determinant I~rSlPr,slo are different from zero. Ostrovskii tried in vain to deduce this from k n o w n re-

sults on determinants and from elementary estimates on absolute values of complex numbers. Chebotar6v's novel idea was to show that such minors, which are clearly elements of Q(~), the pth cyclotomic field over the field of rational numbers Q, do not vanish in the padic completion Qp(~) of Q(0. Just as every p-adic number has a p-adic expansion, so does every element of Qp(~) have a ~--adic expansion for ~- = ~ - 1. Thus, each of the determinant entries can be e x p a n d e d as

Using the linearity of determinants with respect to their columns, w e can expand a m i n o r of size n ;< n corres p o n d i n g l y as M = ICris.Jli,j=~ n --_ y~--~>o(risjl~Tk" \ k / lid=l (F~Sll)

-.-

~YlSn

x k.) ,lTkl+...+kn. = kl

kn (~1)

9 kn "]

Write Dkl,...,kn for the determinants occurring in the right-hand side. If, for some d < n, there are at least d + 1 values in the sequence kl, k2. . . . . kn that are smaller than d, then Dkl,...,kn vanishes, for the entries of its jth column are the values in the ri's of the polynomial s'X ( ~ ) of degree kj, and d + 1 polynomials of degree s~{aller than d are linearly d e p e n d e n t . It follows that Dkl,...,k n vanishes for kl + k2 -4- ... + kn < 0 + 1 + "'" + (n - 1) = n(n - 1)/2, and that in the case of equality kl + k2 + "'" + kn = n(n - 1)/2, it can only be nonzero if the sets {kl, k2. . . . . kn} and {0, 1 . . . . . n - 1} coincide. In that c a s e , Dkl,...,k n is a V a n d e r m o n d e determinant. We find M C71re(n-l)~2 q-O('lyl+n(n-1)/2), where the constant C is given by =

Sl~o) s ~ ~) ... s~n-1) C = Z

IT

sign(o')

UI (rj - ri). 0! 1! 2! ... (n - 1)! l<_i<~<_n ]

H e r e tr ranges over the permutations of {0, 1 . . . . . n 1}. We recognize once more a V a n d e r m o n d e determinant, obtaining C =- l~l-
0! 1! 2! "'" (n - 1)! As C is an integer coprime to p, it is not divisible by ~r, and we find that M has ~r-adic valuation n(n - 1)/2. Note that this valuation d e p e n d s only on the size of M. In particular, M is nonzero. This finishes the proof. The problem has a large n u m b e r of published solutions: A. Danilevskif (1937), Yu. G. Reshetnyak (1955), and M. N e w m a n (1975) adapted Chebotar6v's proof in THEMATHEMATICALINTELLIGENCERVOL.18,NO.2, 1996 29

various ways; D i e u d o n n 6 reproved the t h e o r e m indep e n d e n t l y in 1970 (see [13]). The second p r o b l e m w e discuss is of a v e r y classical nature. Chebotar6v took it up as a suitable example to be included in his textbook on Galois theory. As with the previous problem a n d the density theorem, he managed to "dig deeper" with existing tools and find what others had failed to uncover. We start with an observation that goes back to Hippocrates of Chios ( - 4 3 0 B.C.). Let ABC be an isosceles right-angled triangle as in Figure 1. Then the area of the shaded lune that is b o u n d e d by the arcs on AB of the circumscribed circle of ABC and the circle tangent to A C and BC is equal to the area of the triangle ABC. The discovery that it was possible to square certain lunes caused some excitement in antiquity, as it is clearly a promising step t o w a r d the solution of the famous problem of squaring the circle. More generally, let m and n be positive integers, with m ~ n. Consider a lune that is b o u n d e d b y t w o arcs on AB such that the a n g l e s / _ A M B a n d / _ A N B at their respective centers M and N have ratio m : n; thus, in Figure 2, w h e r e m = 3 and n ~- 2, we have 2/z : 2v = 3 : 2. Draw m equal chords in the outer arc and n equal chords in the inner arc, as in Fig. 2: the chords AC, CD, and DB h a v e equal lengths, as h a v e the chords AE a n d EB. The m § n angles s u b t e n d e d b y these chords at the centers of the corresponding arcs are then all equal, so the m § n circle segments cut out b y these chords are all similar. It follows that the ratio of the area of an outer segment and the area of an inner segment equals the square of the ratio of the radii of the two arcs. Suppose n o w that this square happens to be n : m. Then the total area of the m outer segments equals the total area of the n inner segments; in Fig. 2, the area of the three segments on AC, CD, and DB equals the area of the segments on AE and EB. Therefore, the area of the lune equals the area of the "rectified" lune, i.e., the polygonal area (like AEBDC in Fig. 2) that is b o u n d e d b y the m § n chords. Note that this area is nothing but the area of the tetragon A N B M , as the total area of the m triangles with vertex M on the outer chords equals the total area of the n triangles with vertex N on the inner chords. In this case we say that the lune can be squared.

Figure 2

If O is the midpoint of the interval AB and OB has unit length, the radii M B and NB are the inverses of sin/z and sin v, so if we s e t / z = mO and v = nO, the corresponding lune can be squared if and only if the identity

(*)

sin mO)2 _ m sin nO

n

holds. This is an algebraic equation in x = cos O, and if it has a root that is constructible, w e find an example of a squarable lune that can be constructed. It clearly depends only on the ratio m : n w h e t h e r the corresponding lune can be squared. The p r o b l e m of the q u a d r a t u r e of lunes can be formulated as follows. PROBLEM. Find all ratios m : n of coprime positive integers for which the equation (*) has a constructible solution X = COS O .

The example in Figure I corresponds to the case m : n = 2 : 1, which yields x = 1 / V 2 . For the ratio m : n = 3 : 2 in Fig. 2, already k n o w n to Hippocrates, equation (*) is quadratic in cos O and the c o r r e s p o n d i n g lune is constructible. The constructible lune corresponding to the ratio m : n = 3 : 1 also goes back to Hippocrates, and Clausen [10] published the further examples m : n = 5 : 1 and 5 : 3 in 1840, not k n o w i n g that two of his "four new lunar areas" had already been k n o w n to Hippocrates, and the two others to the 18th-century mathematician Martin Johan Wallenius (see [19], p. 200). Clausen concludes his p a p e r with the conjecture that there are no further examples: Ich glaube schwerlich, dat~ sich die Gr6t~en, die die Winkel der andern Verh/iltnissen entsprechenden Ausschnitte bestimmen, geometrisch finden lassen.

Figure 1 30 THEMATHEMATICALINTELLIGENCERVOL.18,NO.2, 1996

[I find it hard to believe that the quantities that determine the angles of the segments corresponding to other ratios can be found geometrically.]

Partial results toward Clausen's conjecture were obtained by Landau (1903) and the Bulgarian mathematician Chakalov (1929-1930), who wrote equation (*) in terms of a new variable y = e2i~ as F(y) = (ym _ 1)2 _ m ym-n(yn _ 1)2 = 0 n

and determined in a few cases the Galois groups of the irreducible factors of F over Q. Note that F is a difference of squares in Q(~m-m/n) in the easier case where m n is even. By a careful study of the arithmetical properties of the polynomial F, in particular the ramification of the splitting field of F over Q, Chebotar6v showed in 1934 that Clausen's list is complete in this easier case [6]. The general case remained open, but shortly before Chebotar6v's untimely death in 1947, his student A.B. Dorodnov finished the work of his teacher and proved Clausen's conjecture in full [15].

The Density Theorem Chebotar6v's density theorem may be regarded as the least common generalization of Dirichlet's theorem on primes in arithmetic progressions (1837) and a theorem of Frobenius (1880; published 1896). Dirichlet's theorem is easy to discover experimentally. Here are the prime numbers below 100, arranged by final digit:

1: 2:2 3: 5:5 7: 9:

11, 31, 41, 61, 71 3, 13, 23, 43, 53, 73, 83 7, 17, 37, 47, 67, 97 19, 29, 59, 79, 89

It does not come as a surprise that no prime numbers end in 0, 4, 6, or 8, and that only two prime numbers end in 2 or 5. The table suggests that there are infinitely many primes ending in each of 1, 3, 7, 9, and that, approximately, they keep up with each other. This is indeed true; it is the special case m = 10 of the following theorem, proved by Dirichlet (1805-1859) in 1837 (see [14]). Write ~(m) for the number of integers x with 1 <x -< m and gcd(x, m) = 1; so ~(10) = 4. THEOREM OF DIRICHLET. Let m be a positive integer. Then for each integer a with gcd (a, m) = 1 the set of prime numbers p with p ~- a mod m has density 1/r Here we say that a set S of prime numbers has density 6 if

( 1)( pZs~-7

p pr~ime~

---*6 for s ,~ 1.

Clearly, the set of all prime numbers has density 1. Finite sets of prime numbers have density 0, since ~p prime 1/p diverges. Thus, for m = 10, the "exceptional" primes 2 and 5 do not count from a density point of view, and the other primes are "equidistributed" over the four residue classes 1, 3, 7, 9 modulo 10 in the sense that the four densities are equal. Dirichlet's original formulation of his theorem does not involve the notion of density, but the above is what his proof gives. The notion of density that we just defined is sometimes called analytic or Dirichlet density. It would have been more intuitive to say that a set S of prime numbers has density 6 if #{p<-x:p~S} ---~6 #{p -< x : p prime}

forx--~.

With this concept of density, called natural density, Dirichlet's theorem is also valid, but the proof, which is much harder, was o ~ y given by De la Vall6e-Poussin in 1896 (see [11]). If a set of primes has a natural density, then it has an analytic one, and the two densities are equal; but the converse is false. The results below were originally proved for the analytic density, which is easier to manipulate. They are also valid for the natural density, but in this case the proofs require additional techniques, largely due to Hecke [20]. The theorem of Frobenius (1849-1917) that ChebotarOv generalized deserves to be better known than it is. For many applications of Chebotar6v's theorem it suffices to have Frobenius's theorem, which is both older (1880) and easier to prove than Chebotar6v's theorem (1922). Again, Frobenius's theorem can be discovered empirically. Consider a polynomial f with integer coefficients, say f = X4 + 3X2 + 7X + 4, and suppose that one is interested in deciding whether or not f is irreducible over the ring Z of integers. A standard approach is to factor f modulo several prime numbers p. Thus, we have f=-X(X 3 + X + 1 )

mod2,

where X and X3 + X + 1 are irreducible over the field F2 = Z / 2 Z of 2 elements. We say that the decomposition type of f modulo 2 is 1, 3. It follows that i f f is reducible over Z, then its decomposition type will likewise be 1, 3: a product of a linear factor and an irreducible cubic factor. However, the latter alternative is incompatible with the fact that the decomposition type modulo 11 is 2, 2: f-=(X 2 + 5 X - 1 ) ( X 2 - 5 X - 4 )

mod11,

where the two factors are irreducible over Fll. One concludes that f is irreducible over Z. Could the irreducibility of f have been proven with a single prime? Modulo such a prime number, f would THE MATHEMATICAL 1NTELLIGENCER VOL. 18, NO. 2, 1996

31

have to be irreducible, with decomposition type equal to the single number 4. Current computer algebra packages make it easy to do a numerical experiment. There are 168 prime numbers below 1000. Two of these, p = 7 and p --- 19, are special, in the sense that f acquires repeated factors modulo p: f ~- (X - 3)2(X + 3)2 mod 7, f =- (X - 3)3(X + 9) mod 19. For no other prime does this happen, and the following types are found: 112 primes (67.5%), Type 1, 3: 44 primes (26.5%), Type 2, 2: Type 1, 1, 1, 1: 10 primes (6.0%). It is suggested that the primes with type 1, 3 have density ~; that the primes with type 2, 2 have density 88 that no prime at all exists with the desired type 4 or with type 1, 1, 2; and, to make the densities add up to 1, that the primes with type 1, 1, 1, 1 have density ~2. The following table shows the results of similar experiments performed on several fourth-degree polynomials. For each polynomial f i n the first column, the table gives the apparent density of primes p for which f modulo p has a given decomposition type. f X4 X 1 X4-X2+ 1 X4+X3+X2+X+ X 4-

X 2-

1

X4 -Jr-3X2 + 7X + 4

1

4

1,3

2,2

.4 0 ;i

.3 0 0

'4

0

~

'4

0

~

88

0

.

8

1,1,2 .

88 ;1

4. 0 0

1,1,1,1 24

88 ;1 ,~

Frobenius's theorem tells how to understand these fractions through the Galois group of the polynomial. Let, generally, f be a polynomial with integer coefficients and with leading coefficient 1, and denote the degree of f by n. Assume that the discriminant A(f) of f does not vanish, so that f has n distinct zeros al, a2, 999 a n in a suitable extension field of the field Q of rational numbers. Write K for the field generated by these zeros: K = Q(al, a2. . . . . an). The Galois group G of f is the group of field automorphisms of K. Each cr E G permutes the zeros al, a2. . . . . an of f, and is completely determined by the way in which it permutes these zeros. Hence, we may consider G as a subgroup of the group Sn of permutations of n symbols. Writing an element ~ E G as a product of disjoint cycles (including cycles of length 1), and looking at the lengths of these cycles, we obtain the cycle pattern of 0-, which is a partition h i , n 2 i 9 . 9 , n t of n. If p is a prime number not dividing A(f), then we can write f modulo p as a product of distinct irreducible factors over Fp. The degrees of these irreducible factors form the decomposition type of f modulo p; this is also a partition of n. Frobenius's theorem asserts, roughly 32

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

speaking, that the "number" of primes with a given decomposition type is proportional to the number of cr E G with the same cycle pattern. THEOREM OF FROBENIUS. The density of the set of primes p for which f has a given decomposition type nl, n2. . . . . nt exists, and it is equal to 1 / # G times the number of cr E G with cycle pattern nl, n2. . . . , nt. Consider, for example, the partition in which all ni are equal to 1. Only the identity permutation has this cycle pattern. Hence, the set of primes p for which f modulo p splits completely into linear factors has density 1/#G. Thus, the last column of the table above indicates that the Galois groups of the five polynomials in the table have orders 24, 4, 4, 8, and 12, respectively. In fact, these Galois groups are the full symmetric group $4, the Klein four group V4, the cyclic group C4, the dihedral group D4 of order 8, and the alternating group a4. This is a complete list of transitive subgroups of $4, so that every irreducible f of degree 4 behaves like one of the five polynomials in the table. For reducible f there are other possibilities. The alternating group A4 contains, in addition to the identity element, eight elements of type 1, 3, and three elements of type 2, 2. This explains the fractions ,~2= 32and ,~2= ~ that we found for the polynomial f = X4 + 3X2 + 7X + 4. Since A4 contains no elements of type 4, the set of primes p for which f is irreducible modulo p has density zero. In fact, the existence of the Frobenius substitution (see below) implies that no such primes exist at all. With a little group theory, one can deduce several charming consequences from Frobenius's theorem. For example, if f modulo p has a zero in Fp for every prime number p, then f is either linear or reducible. Also, the number of irreducible factors of f over Z is equal to the average number of zeros of f modulo p in F~, averaged over all p (in an obvious way). Historically, the logic went in the opposite direction: the last statement was proved by Kronecker in 1880 [23], and it formed the basis for Frobenius's proof; it was Frobenius who used group theory in his argument, not Kronecker. In order to see a connection between the theorems of Dirichlet and Frobenius we consider polynomials of the type f = X m - 1, where m is a positive integer. We have A ( X m - - 1) (--1)m(m-l)/2m m, SO we exclude the primes dividing m. For the remaining primes p, one can determine the decomposition type of X m - I modulo p by applying elementary properties of finite fields (see [25], Theorem 2.47). With m = 12 one finds in this way that the decomposition type depends only on the residue class of p modulo 12, as follows: =

p ~ 1 mod 12: p ~ 5 mod 12: p -= 7 mod 12: p~11mod12:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 1, 1, 1, 1, 2, 2, 2, 2 1, 1, 1, 1, 1, 1, 2, 2, 2 1,1,2,2,2,2,2.

Notice that the four decomposition types corresponding to the four coprime residue classes are pairwise distinct. Hence, Frobenius's theorem implies the special case m = 12 of Dirichlet's theorem. This does not work for all m. For example, with m = 10 we find in the same w a y the following decomposition types: p -= 1 m o d 10: p ~- 3 or 7 m o d 10: p -= 9 mod 10:

1,1,1,1,1,1,1,1,1,1 1,1,4,4 1,1,2,2,2,2.

The decomposition type depends only on p m o d u l o 10, but Frobenius's theorem does not distinguish between the residue classes 3 m o d 10 and 7 m o d 10. Generally, Frobenius's theorem for f = X m - 1 is implied by Dirichlet's theorem for the same m, but not conversely. One can formulate a sharper version of Frobenius's theorem that for f = X m - 1 does come d o w n to Dirichlet's theorem. To do this, one needs to answer a question that is suggested by the connection between decomposition types and cycle patterns. Namely, is it possible to associate in some natural manner, with each prime number p not dividing A(f), an element O-p E G such that the decomposition type of f m o d u l o p is the same as the cycle type of O-p? The answer is almost affirmative: it can indeed be done, except that o-p, traditionally called the Frobenius substitution of p, is only well defined up to conjugacy in G. (Conjugate permutations have the same cycle pattern, so this should not bother us too much.) Once the Frobenius substitution has been defined, one can w o n d e r about the density of the set of primes p for which O-p is equal to a given element of G. This leads to the desired common generalization of the theorems of Dirichlet and Frobenius. It was formulated as a conjecture by Frobenius, and ultimately proved by Chebotar6v. The construction of the Frobenius substitution is mildly technical, which forms the main cause for the relative unpopularity of Chebotar6v's theorem outside algebraic number theory. In our exposition we shall take a few easily stated facts for granted. First, let a prime n u m b e r p be fixed, and denote by Fp an algebraic closure of the field Fp = Z/pZ. The fundamental tool in the theory of finite fields is the Frobenius map Frob:Fp --> Fp, which is defined by Frob(a) = oLP.It clearly respects multiplication, and it respects, miraculously, addition as well: it is a field automorphism of Fp. It follows that Frob permutes the zeros of a n y polynomial g that has coefficients in Fp. Galois theory for finite fields comes d o w n to the statement that the cycle pattern of Frob, viewed as a permutation of the zeros of g, is the same as the decomposition type of g over Fp. This is true for any polynomial g with coefficients in Fp that has no repeated factors. The proof readily reduces to the case that g is irreducible, in which case one applies Theorem 2.14 of [251. The case of interest to us is g = (f m o d p), with f as taken earlier.

The Frobenius m a p is an automorphism of the field Fp of characteristic p, and the Frobenius substitution crv is going to be an automorphism of the field K of characteristic zero. To relate the two fields, we develop a w a y of taking elements of K = Q(al . . . . . an) m o d u l o p, so that the "zeros of (f mod p)" can be regarded as the "(zeros of f) mod p." By a place of K over p we m e a n a m a p 6:.K~ Fp U {o0} for which (i) •-1 Fp is a subring of K, a n d @ ~b-1 Fp ~ Fp is a ring homomorphism, (ii) Ox = oo if and only if ~(x -1) = 0, for any nonzero xEK. Note that a new symbol like oo is forced upon us if we attempt to take elements of K m o d u l o p: we obviously want p m o d p to be 0, which leads to (l/p) m o d p = 1/0 = 0o. The basic facts about places are as follows: (a) a place of K over p exists, for any prime n u m b e r p, (b) if O, ~b' are two places over p, then ~b' = @'r for some rEG, (c) if p does not divide A(f), then the element ~-EG in (b) is uniquely determined by 0 and ~/. In the formulation we have chosen, these facts are hard to find in the textbooks. This provides an attractive exercise for the reader who is not willing to take them for granted. Let p be a n y prime number not dividing A(f), and let be a place of K over p. It is easily seen that ~(~), I~(a2) I~(an) are the zeros of (f mod p ) in Fp. Applying (b) and (c) to ~b' = Frobo~b - - which is also a place over p, with Frob(~) = o0 __ one finds that there is a unique element FroboEG for which . . . . .

Oo Frob 0 = Frob o ~. This is going to be our Frobenius substitution. As an element of G, it is characterized by ~ F r o b d x ) ) = Frob(0(x))

for all xEK.

This shows that Frobg, permutes al, a2 . . . . . an in the same way as Frob permutes the zeros 6(al), 6(a2) . . . . . 6(an) of (f m o d p). Therefore, the cycle pattern of Frob 4, is indeed equal to the decomposition type of f modulo p. The Frobenius substitution Frob 0 does, in general, depend on the choice of the place 0 over p. By (b), any other place over p is of the form @z, and one readily verifies from the definition that Frobr = z-loFrobg,ov, that is, if 0 varies over the places over a fixed prime p, then Frob 4, ranges over a conjugacy class in G. We shall denote a typical element of this conjugacy class by O-p; THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

33

it is well defined only up to conjugacy, and it is called the Frobenius substitution of p. To illustrate the above, we consider again the polynomialf = X m - 1. In this case K is a cyclotomic field, obtained by adjoining a primitive mth root of unity ~ to Q. The Galois group G has order ~(m), and it is naturally isomorphic to the group (Z/mZ)* of units of the ring Z/mZ; here ~-EG corresponds to (a mod m)E(Z/mZ)* if 7(~) = ~,a.Let p be a prime number not dividing m. Since the Galois group is abelian, the Frobenius substitution o-p is a well-defined element of G, not just u p to conjugacy. To compute it, let ~bbe a place over p. Then ~/= ~ ) is a primitive mth root of unity in Fp. By definition of O-p,we have ~(o'p(x)) = 6(x)P for all xEK. Putting x = ~, and letting a be such that O-p(~) = ~-a,we find that ~/a = 77P, so that a ~- p rood m. In other words, if p is a prime number not dividing m, then the Frobenius substitution ~rp is the element of G that under the isomorphism G ~- (Z/mZ)* corresponds to (p rood m). The example just given allows us to reformulate Dirichlet's theorem as follows: if f = X m - 1 for some positive integer m, then the set of prime numbers p for which crp is equal to a given element of G has a density, and this density equals 1/#G; thus the Frobenius substitution is equidistributed over the Galois group if p varies over all primes not dividing m. Chebotar6v's theorem extends this to all f. CHEBOTAREV'S DENSITY THEOREM. Let f be a polynomial with integer coefficients and with leading coefficient 1. Assume that the discriminant /l(f) of f does not vanish. Let C be a conjugacy class of the Galois group G of f. Then the set of primes p not dividing A(f) for which crp belongs to C has a density, and this density equals #C/#G. On first inspection, one might feel that Chebotar6v's theorem is not much stronger than Frobenius's version. In fact, applying the latter to a well-chosen polynomial (with the same splitting field as f), one finds a variant of the density theorem in which C is required to be a division of G rather than a conjugacy class; here two elements of G belong to the same division if the cyclic subgroups that they generate are conjugate in G. Frobenius himself reformulated his theorem already in this way. The partition of G into divisions is, in general, less fine than its partition into conjugacy classes, and Frobenius's theorem is correspondingly weaker than Chebotar6v's. For example, (3 rood 10) and (7 mod 10) belong to the same division of the group (Z/10Z)*, and this is why Frobenius's theorem cannot distinguish between primes lying in these two residue classes. We close this section with three typical elementary applications of Chebotar6v's density theorem. For the proofs, it suffices to apply the theorem to appropriately constructed fields, just as one obtains Dirichlet's theorem by looking at cyclotomic fields. The first is a result from algebraic number theory: the 34

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

prime ideals of the ring of integers of an algebraic number field are equidistributed over the ideal classes. The proof requires the notion of a Hilbert class field. The second has to do with quadratic forms: the set of primes p that can be written as p = 3x 2 + xy + 4y2, with x, y~Z, has a density, which equals '2. Results of this sort depend on ring class fields. The final one concerns base 10, like the result with which we started: the density of the set of primes p for which 'p, when developed in the decimal system, has an odd period length, exists, and is equal to ~ (see [31]). This example depends, interestingly enough, on infinitely many polynomials, namely, those of the form f = X 2k - 100 for all k ~ 2.

Class Field Theory and Chebotar~v's Theorem The paper in which Frobenius proved his theorem and formulated the conjecture that was to become Chebotar6v's density theorem had already been written in 1880. He communicated the results of his paper to Stickelberger and Dedekind, but delayed the publication until Dedekind's ideal theory had appeared in print. This occurred in 1894, and Frobenius's paper came out in 1896. Frobenius's conjecture was 42 years old when Chebotar6v proved it in 1922. During these 42 years, algebraic number theory had gone through several developments: Dedekind and Kronecker laid the foundations of the theory, Hilbert wrote his Zahlbericht, Weber and Hilbert conceived the principal theorems of class field theory, and shortly after World War I, the Japanese mathematician Takagi supplied the proofs of these theorems (see [18]). Class field theory describes all abelian extensions of a given algebraic number field. It is, after more than 70 years, still considered to be a difficult theory. Its main results are natural enough, but the proofs are long and winding; they have the character of a verification rather than offering a satisfactory explanation of why the results are true. One might think that class field theory provided Chebotar6v with a powerful tool for his proof. Indeed, modern textbook treatments of Chebotar6v's density theorem invariably depend on class field theory (see, for example, [24], Chap. VIII, Sec. 4 and [30], Chap. V, Sec. 6). Remarkably, the original proof did not. In fact, Chebotar6v was at the time not yet familiar with class field theory; he proved his theorem essentially with his bare hands. As we shall see, his proof was more important for class field theory than class field theory was for his proof. Chebotar6v's argument was based on a new technique of his own invention, which consisted of "crossing" arbitrary abelian extensions of number fields with cyclotomic extensions, obtained by adjoining a root of unity. Using no more than basic Galois theory,

Chebotar6v s h o w e d that this p r o c e d u r e r e d u c e d the general case of his t h e o r e m to the case of (relative) cyclotomic extensions. H e handled this case b y w a y of a fairly standard a r g u m e n t similar to the one Dirichlet had used. More details can be f o u n d in Schreier's lucid c o n t e m p o r a r y account [33] and in the a p p e n d i x to this article. Chebotar6v published his density t h e o r e m first in Russian in 1923 [4], and next in G e r m a n in 1925 [5]. Also in 1923, Emil Artin published his reciprocity law [1, Satz 2]. This law is n o w considered to be the main result of class field theory, even though it is missing from Weber's and Hilbert's original conception. Artin boldly formulated his law as a theorem, but he a d m i t t e d that he had no proof. He p o i n t e d out that his reciprocity law w o u l d imply Frobenius's conjecture [1, Abschnitt 7]. On February 10, 1925, Artin wrote to Hasse [16, p. 23]:

Chebotar6v's ghost might reply that it is our intuition and h u m a n psychology that need to be replaced, and not his perfectly valid and effective argument. Indeed, Neukirch [30] weaves Chebotar6v's stratagem so closely through his presentation of the theory that one can believe that one day it will be part of our way of thinking about the reciprocity law. On the other hand, Chebotar6v's trick has disappeared f r o m current treatments of his density theorem: once the reciprocity law is available, one can deal directly with abelian extensions, without the detour through cyclotomic extensions. The reader of the appendix will agree that this approach, due to Deuring [12], is a v e r y natural one; but it makes Chebotar6v's theorem a p p e a r harder than it actually is.

Haben Sie die Arbeit von Tschebotareff in den Annalen Bd 95 gelesen? Ich konnte sie nicht verstehen und mich auch aus Zeitmangel noch nicht richtig dahinterklemmen. Wenn die richtig ist, hat man sicher die allgemeinen Abelschen Reziprozit/itsgesetze in der Tasche. Das Studium der Arbeit haben wir hier auf das n~ichste Semester verschoben. Vielleicht haben Sie sie schon gelesen und wissen also ob falsch oder richtig?

We give a proof of Chebotar6v's theorem that follows his original strategy,-i-f not his tactics. References are to [24]. We assume familiarity with basic algebraic number theory, including elementary properties of zeta functions [VIII.I-3], but not including class field theory. We p r o v e a more general version of the theorem, in which the base field can be a n y algebraic n u m b e r field F instead of just Q. As in the case F = Q, a set of primes of F can h a v e a density [VIII.4]. Let K be a finite Galois extension of F, with Galois g r o u p G. There isagain, for all but finitely m a n y primes V of F, a Frobenius substitution cry, which is an element of G that is well defined u p to conjugacy.

[Did you read Chebotar6v's paper in the Annalen, vol. 95? I could not understand it, and lack of time prevented me so far from properly concentrating on it. If it is correct, then one surely has the general abelian reciprocity laws in one's pocket. Here we postponed studying the paper until the next semester. Perhaps you have read it already and know therefore whether it is right or wrong?] Artin's intuition was correct. Chebotar6v himself writes [7, Vol. 3, pp. 155-156]: In the summer of 1927, when I studied class field theory, I became convinced that it was possible to prove Artin's reciprocity law by means of my device of taking composites with cyclotomic extensions. When the outline of a proof began to dawn on me, albeit still rather dimly, we returned from the dacha to the city [Odessa], and there I saw in the display case of the library the issue of the Hamburger Abhandlungen with Artin's paper [2]. My annoyance was immediately mitigated when I saw that Artin mentions at the beginning of his paper that a basic idea of his proof, that of taking composites with cyclotomic extensions, was borrowed from my paper [5]. I was very touched by Artin's meticulousness in matters of attribution, as there is only an incomplete analogy between the ways in which the method of taking composites with cyclotomic extensions is used in the two papers. Artin found his proof in July 1927 (see [16], pp. 31-32). Chebotar6v was not far behind. Chebotar6v's technique is still a crucial ingredient of all k n o w n proofs of Artin's reciprocity law (e.g., [24], Chap. X, Sec. 2). ,It is w i d e l y felt that it works for no good reason, and that it is just as counterintuitive as most proofs in class field theory. To this complaint,

Appendix

CHEBOTAREV'ST H E O R E M . For any conjugacy class C of G, the density d(K/F,C) of the set of primes ~ of F for which % E C exists and equals #C/#G. The p r o o f begins with a reduction to the abelian case. Let c r E C , and put E = { x E K : o - x = x } . Then K i s a Galois extension of E' with g r o u p Co'). A simple counting argument, carried out in [VIII.4, proof of Theorem 10], shows that (*) the conclusion of the theorem holds for K, F, C if and only if it holds for K, E, {o-}. Note that the Galois group (o-) of K over E is abelian. Next one considers the case that K is cyclotomic over F, i.e., K = F ( 0 for some root of unity ~. This is the case that for F = Q yields Dirichlet's theorem, and it is the proof of the latter theorem that one imitates. Using the fact that the Frobenius substitution of a prime V d e p e n d s only on the n o r m of t0 m o d u l o the order of ~ (cf. [VII.4, Example]), one expresses the zeta function ~K(S) of K as a suitable p r o d u c t of L-functions of F. Then one looks at the o r d e r of the pole in s = 1, and one finishes the proof with a traditional a r g u m e n t as in [VIII.4, Corollary to T h e o r e m 8]. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

35

One approach to deal with general abelian extensions is by showing that they share the essential properties of cyclotomic extensions that are used. This is not e a s y - it is the content of class field theory. It leads to Deuring's proof of Chebotar6v's theorem [VIII.4, T h e o r e m 10]. Chebotar6v's m e t h o d does not need class field theory. It is as follows. Let K be abelian over F, with group G and degree n. Let m be any prime n u m b e r not dividing the discriminant ~ of K over Q, and d e n o t e by ( a primitive mth root of unity. Then the Galois g r o u p H of F ( 0 over F is isomorphic to (Z/mZ)*, and the Galois g r o u p of K(~9 over F m a y be identified with G x H. If a prime p of F has Frobenius substitution (o-, T) in G x H, then it has Frobenius substitution o- in G. Hence, writing dinf for lower density - - defined as the density, but with lira replaced b y lira inf - - we have dinf (K/F, {o'}) >--~ H dinf (K(sO/F, {(o-, ~-)}). N o w fix cr E G and ~-~ H, and suppose that n divides the order of T. Then the subgroups ((or, r)) and G • {1} of G X H have a trivial intersection. Therefore the field L of invariants of ((or, r)) satisfies L(~) = K(~), so that the extension L C K(0 is cyclotomic. By what w e p r o v e d in the cyclotomic case, the density d(K(~)/L, {(o-, T)}) exists and has the correct value. This is, by (*), then also true for d(K(~)/F, {(or, 7)}), which consequently equals 1/(#G.#H). S u m m i n g over T, one obtains dinf (K/F, {or}) -> #Hn/(#G'#H), w h e r e H~ is the set of ~-E H of o r d e r divisible by n. N o w it is easy to see that as m ranges over all prime n u m b e r s not dividing 4, the fraction #Hn/#H gets arbitrarily close to 1 (use, for example, Dirichlet's theorem to choose m =I m o d n k for large k). Thus it follows that dinf (K/F, {or}) 1/#G. Applying this to all other elements of the group, one finds that the u p p e r density dsup (K/F, {or})is at most 1/#G. Therefore the lower and the u p p e r density coincide, and the density equals 1/#G. This completes the proof of the theorem. References Sources on the Life and Work of Chebotar~v. The mathematical w o r k of Chebotar6v is well d o c u m e n t e d in books and papers that appeared during or shortly after his lifetime. Russian versions of his published papers can be found in his collected works [7]. In addition, Chebotar6v wrote several overviews of his o w n mathematical work in v o l u m e s appearing u n d e r titles of the f o r m Soviet mathematics after n years, see, e.g., [26]. Of a similar nature are [21] and the detailed description of the work of Chebotar6v and his students in Kazan by his colleague and friend M o r o z o v [28]. The situation with respect to Chebotar6v's life is different. His collected works contain a "slightly abridged" version of a mathematical autobiography written in 1927. It focuses on his mathematics and his scientific career, as does, to a lesser extent, the obituary in the Uspekhi [29]. M o r o z o v wrote a biographical sketch of Chebotar6v [27] of a m u c h more personal nature in 1963, 36

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

w h e n a certain political thaw had set in u n d e r Stalin's successor Khrushch6v. He tried twice without success to publish it in Algebra i Logika, on the occasion of the 20th and 25th anniversaries of Chebotar6v's death. Like Chebotar6v's son Grigorii's recollections of his father's life [3] and some selected manuscripts of Chebotar6v and M o r o z o v [8], it has not yet been published. H o w e v e r , I.R. Shafarevich has been so kind as to provide us w i t h copies of these documents. The a m o u n t of detail concerning events of a r e m o t e l y political nature varies as a function of time in these sources; one can compare the descriptions of similar events in the "abridged" autobiography in the 1949-1950 collected works, in Morozov's 1963 sketch that includes quotes from the unabridged autobiography, and in the recent recollections [3]. 1. E. Artin, Uber eine neue Art von L-Reihen, Abh. Math. Sem. Univ. Hamburg 3 (1923), 89-108; Collected papers, pp. 105-124. Addison-Wesley, Reading, MA, 1965. 2. E. Artin, Beweis des allgemeinen Reziprozit~itsgesetzes, Abh. Math. Sem. Univ. Hamburg 5 (1927),353-363; Collected papers, pp. 131-141. Addison-Wesley, Reading, MA, 1965. 3. G. N. Chebotar6v, Iz vospominanE ob ottse (From the recollections on my father) (unpublished). 4. N. G. Chebotar6v, Opredelenie plotnosti sovokupnosti prostykh chisel, prinadlezhashchikh zadannomu klassu podstanovok (Determination of the density of the set of prime numbers, belonging to a given substitution class), Izv. Ross. Akad. Nauk 17 (1923), 205-250; Sobranye sochinenii I, 27-65. 5. N. Tschebotareff (= N.G. Chebotar6v), Die Bestimmung der Dichtigkeit einer Menge von Primzahlen, welche zu einer gegebenen Substitutionsklasse geh6ren, Math. Ann. 95 (1925), 191-228. 6. N. Tschebotar6w (= N.G. Chebotar6v), Uber quadrierbare Kreisbogenzweiecke, I, Math. Z. 39 (1935), 161-175. 7. N. G. Chebotar6v, Sobranye sochinenff (Collected works), Akademiya Nauk SSSR, Moscow, 1949-1950 (3 volumes). 8. N. G. Chebotar6v, Letter to Mikhail II'ich Rokotovski~, July 3, 1945, in Pis'ma i Vospominaniya (Letters and Recollections) (16 pp., unpublished). 9. N. Tschebotar6w (= N.G. Chebotar6v), Grundziige der Galois'schen Theorie, /ibersetzt und bearbeitet von H. Schwerdtfeger, Noordhoff, Groningen, 1950. 10. Th. Clausen, Vier neue mondf6rmige Fl~ichen, deren Inhalt quadrirbar ist, J. Reine Angew. Math. 21 (1840), 375-376. 11. Ch. de la Vall6e-Poussin, Recherches analytiques sur la th6orie des nombres premiers. Deuxi6me partie: Les fonctions de Dirichlet et les nombres premiers de la forme lin6aire Mx + N, Ann. Soc. Sci. Bruxelles 20 (1896), 281-362. 12. M. Deuring, Ober den Tschebotareffschen Dichtigkeitssatz, Math. Ann. 110 (1935), 414-415. 13. J. DieudonnG Une propri6t6 des racines d'unit6, Rev. Un. Mat. Argentina 25 (1970), 1-3; Math. Rev. 47, #8495; see also [7], Vol. 3, p. 162; Math. Rev. 17, 338x; Math. Rev. 53, #7997. 14. G. Lejeune Dirichlet, Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enth~ilt, Abh. K6nigl. Akad. Wissenschaft. Berlin, math. Abh. (1837), 45-71; Werke l, pp. 313-342. Georg Reimer, Berlin, 1889.

15. A. V. Dorodnov, O krugovykh lunochkakh, kvadriruemykh pri pomoshchi tsirkulya i line~lki (On circular lunes quadrable with the use of ruler and compass), Dokl. Akad. Nauk SSSR (N.S.) 58 (1947), 965-968. 16. G. Frei, Die Briefe von E. Artin an H. Hasse (1923-1953), Collection Math6matique, D6partement de Math6matiques, Universit6 Laval, Qu6bec, 1981. 17. F. G. Frobenius, Ober Beziehungen zwischen den Primidealen eines algebraischen K6rpers und den Substitutionen seiner Gruppe, Sitzungsberichte K6nigl. Preut~isch. Akad. Wissenschaft. Berlin (1896), 689-703; Gesammelte Abhandlungen II, 719-733. Springer, Berlin, 1968. 18. H. Hasse, History of class field theory, Algebraic Number Theory, Proceedings of an Instructional Conference, (J. W. S. Cassels and A. Fr6hlich, eds), Academic Press, London, 1967, pp. 266-279. 19. T. Heath, A History of Greek Mathematics, Oxford University Press, Oxford, 1921, Vol. I. 20. E. Hecke, Uber die L-Funktionen und den Dirichletschen Primzahlsatz f~ir einen beliebigen Zahlk6rper, Nachr. Akad. Wiss. G6ttingen Math.-Phys. K1. (1917), 299-318; Mathematische Werke, 178-197. Vandenhoeck & Ruprecht, G6ttingen, 1959. 21. Istoriya otechestvenno~ matematiki (History of our national mathematics), Naukovo Dumka, Kiev, 1969, vol. 3. 22. E. R. Kolchin, Math. Rev. 17 (1956), 1045. 23. L. Kronecker, Uber die Irreductibilit/it von Gleichungen, Monatsberichte K6nigl. Preut~isch. Akad. Wissenschaft. Berlin (1880), 155-162; Werke II, 83-93. B. G. Teubner, Leipzig, 1897. 24. S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, MA, 1970. 25. R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983. 26. Matematika v SSSR za 30 let, 1917-1947 (Mathematics in the USSR after 30 years, 1917-1947), OGIZ, Moscow, 1948.

27. V. V. Morozov, Nikola~ Grigor'evich Chebotar6v (28 pp., unpublished). 28. V. V. Morozov, Kazanskaya matematicheskaya shkola za 30 let - - algebra (The Kazan mathematical school after 30 years - - algebra), Usp. Mat. Nauk 2(6) (1947), 3-8. 29. N. G. Chebotar~v - - nekrolog (N. G. Chebotar6v - - obituary), Usp. Mat. Nauk 2(6) (1947), 68-71. 30. J. Neukirch, Class Field Theory, Springer-Verlag, Berlin, 1986. 31. R. W. K. Odoni, A conjecture of Krishnamurthy on decimal periods and some allied problems, J. Number Theory 13 (1981), 303-319. 32. A. M. Ostrowski, Uber Singularit/iten gewisser mit L~cken behafteten Potenzreihen. Mathematische Miszellen, VII, Jahresber. Deutsch. Math.-Verein. 35 (1926), 269-280; Collected mathematical papers 5, 181-192. Birkh~iuser, Basel, 1985. 33. O. Schreier, Ober eine Arbeit von Herrn Tschebotareff, Abh. Math. Sem. Univ. Hamburg 5 (1927), 1-6. 34. J-P. Serre, Abelian l-Adic Representations and Elliptic Curves, W. A. Benjamin, New York, 1969. 35. J-P. Serre, Quelques applications du th6or6me de densit6 de Chebotarev, Publ. Math. I.H.E.S. 54 (1981), 123-201; CEuvres III, 563-64~. Springer, Berlin, 1996. 36. A. L. Shields, Luzin and Egorov, Math. Intelligencer 9(4) (1987), 24-27.

Faculteit Wiskunde en Informatica Universiteit van Amsterdam Plantage Muidergracht 24 1018 TV Amsterdam The Netherlands Department of Mathematics #3840 University of California Berkeley, CA 94720-3840, USA

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

37

15. A. V. Dorodnov, O krugovykh lunochkakh, kvadriruemykh pri pomoshchi tsirkulya i line~lki (On circular lunes quadrable with the use of ruler and compass), Dokl. Akad. Nauk SSSR (N.S.) 58 (1947), 965-968. 16. G. Frei, Die Briefe von E. Artin an H. Hasse (1923-1953), Collection Math6matique, D6partement de Math6matiques, Universit6 Laval, Qu6bec, 1981. 17. F. G. Frobenius, Ober Beziehungen zwischen den Primidealen eines algebraischen K6rpers und den Substitutionen seiner Gruppe, Sitzungsberichte K6nigl. Preut~isch. Akad. Wissenschaft. Berlin (1896), 689-703; Gesammelte Abhandlungen II, 719-733. Springer, Berlin, 1968. 18. H. Hasse, History of class field theory, Algebraic Number Theory, Proceedings of an Instructional Conference, (J. W. S. Cassels and A. Fr6hlich, eds), Academic Press, London, 1967, pp. 266-279. 19. T. Heath, A History of Greek Mathematics, Oxford University Press, Oxford, 1921, Vol. I. 20. E. Hecke, Uber die L-Funktionen und den Dirichletschen Primzahlsatz f~ir einen beliebigen Zahlk6rper, Nachr. Akad. Wiss. G6ttingen Math.-Phys. K1. (1917), 299-318; Mathematische Werke, 178-197. Vandenhoeck & Ruprecht, G6ttingen, 1959. 21. Istoriya otechestvenno~ matematiki (History of our national mathematics), Naukovo Dumka, Kiev, 1969, vol. 3. 22. E. R. Kolchin, Math. Rev. 17 (1956), 1045. 23. L. Kronecker, Uber die Irreductibilit/it von Gleichungen, Monatsberichte K6nigl. Preut~isch. Akad. Wissenschaft. Berlin (1880), 155-162; Werke II, 83-93. B. G. Teubner, Leipzig, 1897. 24. S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, MA, 1970. 25. R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983. 26. Matematika v SSSR za 30 let, 1917-1947 (Mathematics in the USSR after 30 years, 1917-1947), OGIZ, Moscow, 1948.

27. V. V. Morozov, Nikola~ Grigor'evich Chebotar6v (28 pp., unpublished). 28. V. V. Morozov, Kazanskaya matematicheskaya shkola za 30 let - - algebra (The Kazan mathematical school after 30 years - - algebra), Usp. Mat. Nauk 2(6) (1947), 3-8. 29. N. G. Chebotar~v - - nekrolog (N. G. Chebotar6v - - obituary), Usp. Mat. Nauk 2(6) (1947), 68-71. 30. J. Neukirch, Class Field Theory, Springer-Verlag, Berlin, 1986. 31. R. W. K. Odoni, A conjecture of Krishnamurthy on decimal periods and some allied problems, J. Number Theory 13 (1981), 303-319. 32. A. M. Ostrowski, Uber Singularit/iten gewisser mit L~cken behafteten Potenzreihen. Mathematische Miszellen, VII, Jahresber. Deutsch. Math.-Verein. 35 (1926), 269-280; Collected mathematical papers 5, 181-192. Birkh~iuser, Basel, 1985. 33. O. Schreier, Ober eine Arbeit von Herrn Tschebotareff, Abh. Math. Sem. Univ. Hamburg 5 (1927), 1-6. 34. J-P. Serre, Abelian l-Adic Representations and Elliptic Curves, W. A. Benjamin, New York, 1969. 35. J-P. Serre, Quelques applications du th6or6me de densit6 de Chebotarev, Publ. Math. I.H.E.S. 54 (1981), 123-201; CEuvres III, 563-64~. Springer, Berlin, 1996. 36. A. L. Shields, Luzin and Egorov, Math. Intelligencer 9(4) (1987), 24-27.

Faculteit Wiskunde en Informatica Universiteit van Amsterdam Plantage Muidergracht 24 1018 TV Amsterdam The Netherlands Department of Mathematics #3840 University of California Berkeley, CA 94720-3840, USA

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

37

David Gale* This column is interested in publishing mathematical material which satisfies the following criteria, among others: 1. It should not require technical expertise in any specialized area of mathematics. 2. The topics treated should when possible be comprehen-

sible not only to professional mathematicians but also to reasonably knowledgeable and interested nonmathematicians. We welcome, encourage and frequently publish contributions from readers. Contributors who wish an acknowledgement of submission should enclose a self-addressed postcard.

Our guest columnist for this issue is Solomon W. Golomb. It has seemed to us fitting to dedicate the column to the memory of Raphael Robinson. As mentioned in an earlier issue, Raphael contributed more material to this column over the past four years than any other outside person. The present column seems particularly appropriate for this dedication since it deals with the subjects of tiling and decidability, areas to which Raphael made fundamental pioneering contributions.

copies a complete filling up of all [Euclidean[ space is possible?"

Tiling Rectangles with Polyominoes Solomon W. Golomb In 1900, when the great German mathematician David Hilbert, in an address to the International Congress of Mathematicians assembled in Paris, laid out his agenda for twentieth-century mathematics, his "most wanted list" of twenty-three unsolved problems included, as number 18, a question concerning the ways in which ndimensional Euclidean space (including n = 2 and n = 3) can be "tiled" or "packed" with congruent copies of a single geometric figure. Specifically, he asked: #1. "Is there in n-dimensional Euclidean space.., only a finite number of different kinds of groups of motions with a [compact] fundamental region?" #2. "Whether polyhedra also exist which do not appear as fundamental regions of groups of motions, by means of which nevertheless by a suitable juxtaposition of congruent

*Column editor's address: D e p a r t m e n t of Mathematics, University of California, Berkeley, CA 94720 USA.

The groups of motions (#1) were identified by L. Bieberbach, but examples answering #2 in the affirmative were found in 3 dimensions (K. Reinhardt, 1928) and in 2 dimensions (Heesch, 1935). Simpler, related, and more general examples were subsequently found by R.M. Robinson, S.K. Stein, et al. An example related to Heesch's is shown in Figure 1. (Smaller examples exist, but it is somewhat harder to prove they have the required property.) It is not hard to show that the only w a y this figure can tile the plane is as shown in Figure 2. However, it is not a "fundamental domain," for note that the unique motion which carries A onto B combines a reflection about the dotted line with an upward translation by 2 units, but the image of B under this motion is not a tile. Hilbert never anticipated G6del's Incompleteness Theorem, let alone the possibility that some of his problems would be proved "undecidable." Just as his tenth problem, involving finding all integer solutions of given ("diophantine') equations was shown (by Julia Robinson, Ju. V. Matijasevic, et aI.) to be computationally undecidable, so too the general question of whether it is possible to tile the plane with congruent copies of a given finite set of tiles was proved undecidable by Hao Wang. (Wang showed the equivalence of the tiling problem to the "halting problem" for Turing machines, a standard undecidable problem, on the one hand, and to the undecidability of the class of logical formulas containing three quantifiers, the so-called AEA-formulas, on the other.) R. Berger and other students of Wang extended his results, e.g., to showing that the question of whether it is possible to tile the plane (or a smaller region, such as a rectangle) using congruent copies of a

38 THE MATHEMATICALINTELLIGENCERVOL.18, NO. 2 9 1996Springer-VerlagNew York

single geometric figure is also computationally undecidable. This article is an attempt to summarize what is known about a particular special case of the tiling problem in two dimensions. The only tiles we shall consider are polyominoes, where an "n-omino" is any connected figure obtained by taking n identical unit squares, and connecting them along common edges. Thus, except for orientation, there is only one monomino (the unit square itself) and one domino (the eponymous ancestor of this entire clan). There are two distinct trominoes, five different tetrominoes, twelve pentominoes, thirty-five hexominoes, etc. The simpler ones of these are shown in Figure 3. (Note that we do not regard mirror images ("reflections") as two distinct shapes.) A typical problem in polyomino theory is to determine which polyominoes have the property that un-

[]

Monomino ~

1Trominoe. s

} ,, k_.j

Pentominoes

Figure 3. The Simpler Polyominoes.

-? I

i

I

I

I I

Figure 1. A figure which tiles the plane, but is not a "fundamental region".

!

A

,

k I I I I I s

Figure 2. Tiling the plane with the shape in Figure 1.

+1 Figure 4. Three "rep-tiles": a tromino, a tetromino, and a pentomino.

limited copies of a specific one will tile the entire plane, or will tile a single quadrant of the plane, or will tile an infinite strip bounded by two parallel straight lines, etc. (Figure 2 shows how to tile a strip, hence the plane, with a particular polyomino.) Restrictions can be placed on which, if any, rotations a n d / o r reflections of the basic shape may be used in the tiling. Tilings may be studied in which two, or three, or some other number of different tile shapes are allowed in the tiling. One may ask about those shapes such that several identical copies may be assembled to make an enlarged scale model, or replica, of the original shape, as in Figure 4. (Many years ago, in 1962, I coined the term rep-tiles for these shapes.) All of these questions have been studied. However, this article will focus primarily on the question of which polyomino shapes have the property that some finite number of copies of the basic shape, allowing all rotations and reflections, can be assembled to form a rectangle. The problem is challenging because no a priori limit can be established, given an arbitrary n-omino, on the minimum number of copies which may be required to form a rectangle. No explicit expression in n, such as THE MATHEMATICALINTELLIGENCERVOL, 18, NO. 2, 1996

39

Figure 5. Some polyominoes of order 2. Figure 8. Polyominoes of order 4 under rectangular symmetry.

/

Figure 6. How three identical rectangles can form a rectangle.

Figure 9. Another order-4 construction by Klarner.

Figure 7. Polyominoes of order 4 under 90 ~ rotation.

n n'~, grows fast enough to guarantee that when all possible arrangements of that many copies of the basic shape have been looked at, and no rectangle has been found, then no rectangle involving yet more copies will exist. This follows from the result, mentioned earlier, that the general question of whether an arbitrary polyomino will tile a rectangle is "computationally undecidable." Fortunately, in any specific case, there is a high likelihood (though no certainty) of answering the question. But there can be no cookbook recipe, no handbook procedure, which can be routinely applied to indicate whether a given polyomino shape will tile some (pos-

sibly huge) rectangle. And it is this lack of a general decision procedure which makes this study so interesting and challenging. In 1968, David A. Klarner defined the order of a polyomino P as the minimum number of congruent copies of P which can be assembled (allowing translation, rotation, and reflection) to form a rectangle. For those polyominoes which will not tile any rectangle, the order is undefined. A polyomino has order 1 if and only if it is itself a rectangle. A polyomino has order 2 if and only if it is "half a rectangle", since two identical copies of it must form a rectangle. In practice, this means that the two copies will be 180 ~ rotations of each other when forming a rectangle. Some examples are shown in Figure 5. There are no polyominoes of order 3. (This has been proved by Ian Stewart of the University of Warwick, in

I

1

B

n-24 n -28

Figure 10. Four "sporadic" polyominoes, of orders 10, 18, 24, and 28, respectively. 40 THEMATHEMATICAL INTELLIGENCERVOL.18,NO.2, 1996

A

Figure 11. An 11-omino of order 50

England.) In fact, the only way any rectangle can be divided up into three identical copies of a "well-behaved" geometric figure is to partition it into three rectangles (see Figure 6), and by definition a rectangle has order 1. There are various ways in which four identical polyominoes can be combined to form a rectangle. One way, illustrated in Figure 7, is to have four 90 ~ rotations of a single shape forming a square.

Another w a y to combine four identical shapes to form a rectangle uses the fourfold symmetry of the rectangle itself: left-right, up-down, and 180~ symmetry. Some examples of this appear in Figure 8. There are also more complicated order-4 patterns which were found by Klarner, two of which are illustrated in Figure 9. Beyond order 4, there is a systematic construction found by Golomb in 1985 which gives examples of order 4s for every positive integer s; and eleven isolated examples of small polyominoes with respective orders 10, 18, 24, 28, 50, 76, 92, 96, 138, 192, and 312 are known. Figure 10 shows the isolated examples of order 10 (Golomb, 1966), and orders 18, 24, and 28 (Klarner, 1969). Figure 11 shows the example of order 50, found by William Rex Marshall of Dunedin, N e w Zealand, in 1990. Figure 12 shows the examples of orders 76 and 92, both found by Karl ~. D~hlke in 1987. I had mentioned these two problems in my talk at the Strens Memorial Conference on Recreational Mathemotics (Calgary, 1986), and Ivars Peterson included them in Science News in his article about the Strens Conference. When Dahlke sent me solutions which he said he found using only a personal computer, I notified Peterson, who interviewed Dahlke and learned that he is totally blind. I later heard that these two tilings had actually been discovered earlier, by T.W. Marlow in 1985.

Figure 12. A heptomino of order 76 and a h e x o m i n o of order 92. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

41

Figure 13. A dekomino of order 96.

The heptomino of order 76 in Figure 12 cannot tile its minimum rectangle with 180~ rotational symmetry. This is also true of the dekomino in Figure 13 of order 96, whose minimum rectangle (the 30 x 32) was discovered by William Rex Marshall in 1991. In 1995, Marshall also found the minimum rectangles for the order 192 octomino (32 x 48) and the order 138 dekomino (30 x 46). These will be considered later. Finally, Figure 14 shows the example of order 312

Figure 14. An example of order 312.

42 THEMATHEMATICALINTELLIGENCERVOL.18,NO.2, 1996

(Dahlke, 1988), although in this case it is not absolutely certain that no smaller number of copies of the octomino in question will form a rectangle. No polyomino whose order is an odd number greater than i has ever been found, but the possibility that such polyominoes exist (with orders greater than 3) has not been ruled out. The known even orders of polyominoes are all the multiples of 4, as well as the numbers 2, 10, 18, 50, and 138. Curiously, these even orders which are not multiples of 4 all exceed multiples of 8 by two. Whether there are other even orders, and what they might be, is still unknown. The smallest even order for which no example is known is order 6. Figure 15 shows one way in which six copies of a polyomino can be fitted together to form a rectangle, but the polyomino in question (as shown) actually has order 2. Michael Reid recently found a heptabolo (a figure made of seven congruent isosceles right triangles) of order 6, also shown in Figure 15. The Golomb construction for polyominoes of order 4s gives its first new example, order 8, when s = 2. The underlying tiling concept of how to fit 8 congruent shapes together to form a rectangle is shown in Figure 16. Although the shape used in Figure 16 is not a polyomino, the same concept can be realized using the 12omino shown in Figure 17. (The shape used in Figure 16 is a triabolo!) To show that there are infinitely many dissimilar polyominoes having order 8, we can form the family of polyominoes shown in Figure 18. For each integer r 1, this construction produces a (3r2 + 6r + 3)-omino of order 8, and clearly no two of these are similar. It is also easy to show that none of these polyominoes can have order less than 8. The proof begins by ob-

T

,-l',, f

/

i s

', 9

,9

-----n_

----L

i

I

I

t-1

F-

r~2

el

Figure 15. A 12-omino of order 2 which suggests an order-6 tiling, and Michael Reid's order-6 "heptabolo". (Is there any polyomino of order 6?)

r

rl3

,r "7

,

r~2 Generld r _) I

L_

SSSS N 1

i

FFigure 18. Dissimilar polyominoes of order 8, and h o w to stack them. Figure 16. A rectangle formed from eight congruent pieces.

serving that only the "heel of the boot" can be in any of the rectangle to be tiled. Then the "toe" of the boot must be mated with the notch at the top-back of another boot. The quickest w a y to finish off the rectangle then requires eight copies of the polyomino. In Figure 19, we see a construction for a polyomino of order n = 4s for every s = 1, 2, 3, 4, .... (Starting with a 2 by 4s - 2 rectangle, we remove a single square from corner

|.1 n,4

1

7 s-2

no 8

I

-L . . . . .

"7

L

I

S-3

n-12

r-

l

].-.

9

-l.

r !

,ff ~3~

Ii Figure 17. A polyomino of order 8.

General s, oroer n . 4 |

Figure 19. Polyominoes of order n=4s, for every positive integer s. THE MATHEMATICAL

INTELLIGENCER

V O L . 18, N O . 2, 1996

43

4

I' F

192

IS

138

?

8

V

F

?

y

12

Figure 20. Infinite family of polyominoes. Does each one tile a rectangle? (The number below each figure is its order, if known.)

one corner and attach it as a "toe" at the opposite corner, to obtain the polyomino of order 4s.) The idea shown in Figure 18 can be applied not only to order n = 8, but to a n y order n = 4s, to obtain infi-

nitely m a n y dissimilar polyominoes of order 4s. The general construction involving both r and s begins with a rectangle which is (r + 1) x (2s - 1)(r + 1), and moves a single 1 • 1 square from the top-back of the "boot" to become a "toe" at the opposite corner. (The proof that the resulting figure truly has order n = 4s is analogous to the proof given for n = 8.) As the reader is probably aware by now, the game polyominologists play is: given a polyomino, will it or won't it tile? In recent years, w h e n e v e r I have publicized a specific polyomino whose ability to tile any rectangle was not yet decided, someone with a good computer program has come forth, usually within a year, with a rectangle-tiling solution. This time, I suggest an infinite family of polyominoes, the first several of which are k n o w n to tile rectangles, as is every fourth one throughout the family. Can y o u show that any, or all, of the others can tile rectangles? The family is illustrated in Figure 20. Two of the m i n i m u m rectangles, discovered in 1995 by William Rex Marshall, are s h o w n in Figure 21. We n o w return to the tiling of figures other than rectangles. If a polyomino has no order (i.e., if it cannot tile any rectangle), it m a y still be able to tile the entire plane, or various sub-regions of the plane, such as an infinite strip, or a bent strip. Such tilings are illustrated in Figure 22, using the X-pentomino, the F-pentomino, and the Npentomino, respectively.

Figure 21. An octomino of order 192 and a dekomino of order 138.

44

T H E M A T H E M A T I C A L I N T E L L I G E N C E R VOL. 18, NO. 2, 1996

Y _did

I I-J I I ~ L

Figure 22. The X-pentomino tiles the plane; the F-pentomino tiles a strip; the N-pentomino tiles a bent strip.

In Figure 23, we see a tiling hierarchy for polyominoes (Golomb, 1966). A polyomino which can tile any of the regions specified in the hierarchy can also tile all the regions lower in the hierarchy. Thus, the "true category" of a polyomino is the highest box in the hierarchy which it can occupy. Most of this article has been concerned with polyominoes which occupy the highest box--i.e., they can tile rectangles. The "true categories" which are known to have members are: Rectangle, Bent Strip, Strip, Itself, Plane, and Nothing. Figure 24 shows an example of the category "Nothing". (The others have already been illustrated. The rep-tiles in Figure 4 illustrate the category "Itself.") For each of the other positions in the hierarchy, it is an open question whether any polyomino has that position as its "true category". Most of the inclusion relations in Figure 23 are immediately obvious. To see that a polyomino which tiles a bent strip can tile both a quadrant and a straight strip, we first observe that bent strips (as in Figure 22) can be "nested" to cover a quadrant of the plane. We will show h o w to go from the bent strip to the straight strip after taking up one last important subject. The most challenging unsolved problem about planar tiling involves shapes which can tile the infinite plane, but only non-periodically. R.M. Robinson was the first to find a finite (but very large) set of shapes such that unlimited copies of members of the set could be used to tile the infinite plane, but only non-periodically. He eventually reduced the size of the set to six. Independently, Roger Penrose found a set of 6 shapes with the nonperiodic-only tiling property, which he eventually reduced to a set of two shapes. I believe that a year2000 version of Hilbert's list would include the question: Is there a single geometric shape S such that congruent copies of S can be used to tile the infinite plane, but only non-periodically?To understand this question better, note that the answer is negative if instead of the plane we consider an infinite strip, even if we allow more than one tile shape to be used. To see this, consider a horizontal strip. N o w choose any vertex on the upper edge, and trace a "jagged edge path" using the following rules: If there is

a d o w n w a r d edge follow it. If not, move to the right. Continue to prefer "downward", and secondarily "rightward". Sometimes one may even be forced to go "upward", or "leftward", to trace around a protuberance on a tile, but clearly one will eventually arrive at the bottom edge of the strip, and one can easily obtain a uniform bound on the number of "moves" required in terms of the thickness of the strip, and the sizes and shapes of the tiles. This means that there are only a finite number of possible jagged paths, so there must be two different starting vertices giving the same jagged path. But then, if one takes copies of the region between these two identical paths and lays them end to end, one gets the desired periodic tiling of the strip. Further, we

I Rectangle ]

~,////

f Strip

(R.)

] (HS)

(i)

I ~176176I and Strip

(Q k S)

I

I(s)

I iPlane i

(P) (N)

Figure 23. The hierarchy of tiling capabilities for polyominoes.

|

I I

Figure 24. A 9-omino which cannot tile the plane.

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

45

see as promised, that polyominoes which can tile a bent strip can also tile a straight strip (applying the same argument to either one of the semi-infinite arms of the bent strip), and in fact the tiling can be made periodic. In Figure 25, we see how the "P-pentomino" can be used to tile a quadrant non-periodically, by iterating the rep-tile subdivision of the P-pentomino into smaller copies of itself. We enlarge the picture, repeat the process, enlarge the picture, repeat the process, and "eventually" we have filled the first quadrant of the plane. Reflections in the coordinate axes can be used to cover the entire plane in a non-periodic manner. (This does not solve the previously mentioned problem, because the P-pentomino can also be used to tile the plane periodically.) Not only the P-pentomino, but every polyomino reptile, can be shown to tile a quadrant. To show this, let J be any polyomino rep-tile, and let R be the smallest rectangle containing J with sides parallel to the grid-lines of J. We first prove the lemma that J must cover at least one of the four corners of its minimum rectangle R. Suppose not. In Figure 26, we see a polyomino K which occupies none of the corners of its minimum rectangle. Consider the left-most square of K along the bottom of its minimum rectangle, indicated with an asterisk. If K were a rep-tile, we could divide it into congruent replicas, and we could iterate this process until each replica was so small that it would fit within a single square of the original grid. At this stage, consider the replica k of K covering the lower left corner of the square "*". It fits entirely within that square, and fills a comer of it, so

q-r I

Figure 25. Rep-tilic nonperiodic tiling of a quadrant with congruent copies of the P-pentomino. 46

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

7

K

I

Figure 26. A polyomino inscribed in its minimum rectangle.

clearly k occupies a corner of its minimum rectangle. But the same would be true of K. Now, knowing that J must occupy at least one corner of its minimum rectangle, put such a corner square of J into the lower left corner of the first quadrant of the plane. Now, perform the rep-tilic subdivision of J, enlarge back to the original scale, and continue to subdivide and enlarge (as we did with the P-pentomino in Figure 25) until we have filled up the entire first quadrant. (We do not need to invoke K6nig's lemma to assert that a limiting tiling exists. The method is constructive. Given any radius R, however large, we can specify the tiling of the first quadrant out to distance R from the origin, in such a w a y that this tiling will not change as R is increased. This may involve looking only at every m th iteration of the rep-tilic subdivision, if the J nearest the origin is moved by a single iteration.) The proofs that a polyomino which tiles a bent strip will tile a straight strip, and that a polyomino which tiles itself (i.e., a rep-tile) will tile a quadrant, were given in Golomb (1966). Finally, returning to the subject of non-periodic tilings of the plane, the natural question to ask in our present context is whether there exist "non-periodizable" tilings using polyominoes. The best current result is the set of three shapes, shown in Figure 27, which can be used to tile the plane, but not periodically. (This set was recently discovered by Penrose, who writes that he derived these from a tiling set by Robert Ammann.) Penrose's aperiodic tilings also have connections to "quasicrystals', which have been of major interest to chemists in recent years. Arguments which show that certain sets of "pieces" can tile the plane, but not periodically, are both clever and subtle (see Gr/inbaum and Shephard, 1987, Chapter 10), and undoubtedly lie outside the range of anything Hilbert ever contemplated. But Hilbert's insight which led him to include a problem about tilings and packings in his famous List was profound. This is a subject which is accessible to amateurs but lies close to the very heart of mathematics, and continues to provide a seemingly

Martin Gardner, Mathematical Games: On "rep-tiles', polygons that can make larger and smaller copies of themselves, Scientific American, 208, 154-164 (1963). Solomon W. Golomb, Replicating figures in the plane, Mathematical Gazette, 48, 403-412 (1964). Solomon W. Golornb, Tiling with polyominoes, Journal of Combinatorial Theory, 1,280-296 (1966). Solomon W. Golomb, Tiling with sets of polyominoes, Journal of Combinatorial Theory, 9, 60-71 (1970). Solomon W. Golomb, Polyominoes which tile rectangles, Journal of Combinatorial Theory, Series A, 51, 117-124 (1989). B. Griinbaum and G.C. Shephard, Tilings and Patterns, Freeman, New York (1987). A.S. Kahr, E.F. Moore, and H. Wang, Entscheidungsproblem reduced to the V3V case. Proceedings, National Academy of Sciences USA, 48, 365-377, 1962. David A. Klarner, Packing a rectangle with congruent N-ominoes, Journal of Combinatorial Theory, 7, 107-115 (1969). William Rex Marshall, private communications dated 14 May, 1990, 25 November, 1991, and 6 June, 1995. Roger Penrose, Shadows of the Mind, Oxford University Press, 1994. Michael Reid, private con~unications from 1992 to 1995. Ian Stewart and A. Wormstein, Polyominoes of order 3 do not exist, Journal of Combinatorial Theory, Series A, 61, 130-136, 1992.

University of Southern California University Park, EEB-504A Los Angeles, CA 90089-2565 USA

Figure 27. Roger Penrose's set of three polyominoes which can be used to tile the plane, but not periodically.

VERBUM 5 ADVANCED WORD PROCESSING SYSTEM Delete options help screen

inexhaustible s u p p l y of intriguing and provocative questions. NOTE: This material is based on Chapter 8 of Polyominoes--Revised Edition, by Solomon W. Golomb, Princeton University Press, 1994. It is one of the new chapters a d d e d to the text of the original edition of Polyominoes, which was published in 1965 b y Charles Scribner's Sons.

Bibliography Robert Berger, The undecidability of the domino problem, Memoirs of the American Math. Society, no. 66, 1-72, 1966. Karl A. Dahlke, The Y-hexomino has order 92, Journal of Combinatorial Theory, Series A, 51, 125-126 (1989). Karl A. Dahlke, A heptomino of order 76, Journal of Combinatorial Theory, Series A, 127-128 (1989). Karl A. Dahlke, Solomon W. Golomb and Herbert Taylor, An octomino of high order, Journal of Combinatorial Theory, Series A, 70, 157-158 (1995).

To delete, simultaneously press both shift keys, ESC, DEL, and function key: F1 F2 F3 F4 F5 F6 F7 F8 F9 F10

Delete letter Delete w o r d Delete line Delete page Delete file Delete subdirectory Reformat hard drive Electrocute user Detonate building A d v a n c e d options on next screen

Robert Haas 1981 Carver Road Cleveland Heights, OH 44112 USA (reprinted with permission from The Graffiti, newsletter of Cleveland Area Mensa)

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

47

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

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

Renaissance Area-Fillings in the City Hall of Augsburg Gregor Dorfleitner and Thomas Klein

Augsburg, one of the cities most worth visiting along the Romantic Road running through southern Germany, looks back upon a glorious history of more than 2000 years. Founded as Augusta Vindelicorum by the Roman conquerors in the year 15 B.C., the city reached its peak in the early modern age under the Fugger merchant dynasty. Today there is still a considerable number of Renaissance buildings and other constructions from this period, such as the Zeughaus (the former city magazine), the three fountains depicting Hercules, Augustus, and Mercury, but above all, the City Hall. This edifice was built in the years 1615-1620 and survived without major repairs until 1944, when it was almost completely destroyed by fire from several Allied air raids. After the Second World War, the City of Augsburg began work on the restoration, which was completed in 1980. The City Hall of Augsburg was designed by Elias Holl, born in Augsburg in 1573, who was the official municipal architect at the time. Holl partly drew on the old traditions of Middle European city hall architecture, but partly set radically new standards for representative buildings in the old German empire--the facade, for example, has an extraordinary geometric unity (Fig. 1). It thus becomes a manifestation of the desire for aesthetic design and a symbol of the will to consolidate so48

Figure 1. Facade of the City Hall of Augsburg with geometric construction lines. The gray shaded area indicates the Goldener Saal.

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Verlag New York

Figure 2. Engraving with perspective view of the Goldener Saal from the south by Salomon Kleiner.

cial and political order. Contrary to established architectural conventions, Holl's composition was also the first to emphasize the representation of the city's power and prosperity, which can be seen especially in the most magnificent room of the City Hall, the so-called Goldener Saal (the Golden Hall). The annual opening sessions of the city council took place there and also ceremonial receptions. The citizens of Augsburg even hoped to hold Reichstage (imperial diets) in this hall. The Goldener Saal was mainly designed by Matthias Kager (born in 1575 in Munich, municipal artist of Augsburg from 1615 to 1628) and is one of the highlights of German Renaissance interior architecture; some call it "unequaled in pomp and grandezza," some praise the "great formal and iconographic coherence." In particular, the regular area-fillings realized by differently colored stone slabs on its floor put the Goldener Saal on a plane with such well-known edifices as the Palace of the Doges or the church of San Giorgio Maggiore in Venice or the royal residence in Munich. The closed geometric and architectonic concept and the manifold wealth of shapes in its ceiling and wall decoration both contrast and complement each other. The walls on the short sides of the rectangular ground plan, which face toward the west and the east with a length of 17.3 m, are divided into six vertical parts of

equal width, each part having three windows, one over the other. Each of the 32.6-m-long side walls has a central main portal, flanked by two minor portals, each leading to a so-called Fiirstenzimmer (a nobleman's room) (Fig. 2). Moreover, the window fronts and side walls are embellished with a variety of murals, sculptures, and ornamental reliefs picking up and continuing the structure given by the windows and portals. The splendid ornamentation reaches its climax in the decoration of the ceiling, to which Kager contributed 11 allegorical pictures after sketches by the Munich-based painter Peter Candid. The largest of these 11 paintings is arranged centrally; between this big oval and the two window fronts, there are two circular paintings, each of them surrounded by four smaller oval paintings to form a rosette. The structure of the side walls and the ceiling can be found again on the marble floor of the Goldener Saal, which fascinates by its clarity and contrasts with the overwhelming pomp dominating the rest of the room. The whole floor is divided into eight rectangles by three strips crossing the room and connecting opposite portals (which will in the rest of this article be referred to as latitudinal strips) and a central strip running from one window front to the other (the longitudinal strip); the four rectangles on both sides of the main portals are THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

49

Figure 3. Plan of the floor by A. Machatschek, Vienna.

almost squares (Figs. 3 and 4). At the three points of intersection of the longitudinal strip with the latitudinal ones there are rosettes corresponding to the three big paintings on the ceiling. In order to fill the eight rectangles, Matthias Kager used a pattern of squares and parallelograms that can be seen as a parallel-perspective depiction of cubes positioned above and behind each other. It may be typical for Renaissance art, perspective just having been discovered at that time, that the perspective way of seeing this pattern implies an optical ambiguity: viewers can switch between two three-dimensional interpretations of the two-dimensional picture-puzzle they see a familiar gimmick nowadays, but surely quite spectacular 400 years ago. The parallel perspective employed here is based on an angle of 45~ the scaling factor is 1/X/2. Thus the height of the parallelograms equals half the lateral length of the squares, appearing to the viewer as the faces of the cubes and so half the lateral length of the squares becomes the determining quantity of this area-filling pattern. However, Kager left nothing to chance: he chose this length so as to make every lateral length of the eight large rectangles an integral multiple of it. Hence the edges of the rectangles do not cut off the filling patterns arbitrarily but coincide with lines already given in the pattern as far as possible. 50

THE MATHEMATICALINTELLIGENCERVOL. 18, NO 2, 1996

Each of the three rosettes marking the points of intersection of the longitudinal strip and the three latitudinal strips consists of a circle inscribed into the square given by the width of the intersecting strips. This circle is filled by six congruent petallike segments whose edges consist of six arcs of circles with centers at the corners of a regular hexagon. Following the same principle, six further, smaller petals are grouped around a small central circle (completed by six sepals, though). Therefore, the construction of the rosettes is essentially based on an angle of 60 ~. Being points of intersection, the rosettes divide the latitudinal strips into two equally large parts, whereas the longitudinal strip is divided into four parts of two different sizes. All strips are equally wide, so the only quantity distinguishing the resulting rectangles is their length; the filling pattern common to all the strip parts varies, so to speak, the perspective picture-puzzle already found in the big rectangles. Here again, the basic angle is 45~ but instead of cubes, one recognizes an arrangement of extended rectangular hexahedrons with two opposite square sides. The length of this square was determined so that exactly four (or three and two halves) diagonals of these squares sum up to the width of the strip. As with the area-filling used for the eight large rectangles, Kager faced the difficulty of choosing

a suitable hexahedral length (on which the filling pattern is based) in order to avoid arbitrary cuts at the edges of the strip parts. He m a n a g e d to find hexahedral lengths which make the lengths of the strip parts sums of integral multiples of the hexahedral length a n d half the diagonal length of the square sides and--this is the real achievement--which are approximately equal in all of the three different strip parts. Looking at this more closely, one finds that Kager had to solve an optimization problem which is far from trivial, although it is not clear if he was aware of this. In any case, a visit to the Goldener Saal to see for yourself is well worthwhile.

Acknowledgments We wish to thanl~ Prof. Friedrich Pukelsheim (Universit/it Augsburg) and Dr. H e r m a n n Kie~ling (City of Augsburg) for their valuable support.

Figure 4. Photograph of the floor by I. Pitschel, 1994.

The

Universit4t Augsburg Institut fiir Mathematik D-86135 Augsburg Germany

--Room in Paris

Dirk Huylebrouck The sole m u s e u m that has a true ~r-room is the Palais de la Ddcouverte in Paris, Avenue Franklin Roosevelt (no number: it is the only building on the street). It is located in the center of Paris, near the Louvre at the Seine. It is important to note its location and exact name: an u n i n f o r m e d visitor to Paris might ask for something like the Palais des Sciences, and in that case the Parisians will almost surely send him to La Villette, a more recent center for popularization of science (including mathematics). Once inside the building, one finger-post indicates mathdmatiques and another nombre pi, but they lead the visitor to the same room: the~alle 31 (accidentally or not, the first 2 digits of the room's number are those of vr as well). Smithsonian-like centers are of course very interesting, but the ~--room at the Palais de la Ddcouverte is worth a visit for a peculiar reason. Jonathan M. Borwein and Peter B. Borwein describe the history of the search for decimals of r in the last

chapter of their famous Pi and the AGM (John Wiley & Sons, 1987). The true digit hunters did not leave them cold: The zenith (or nadir depending on your perspective) in premachine calculations was achieved by William Shanks (1812-1882), who published 607 purported digits of or, of which 527 were correct. Later Shanks published an extension to 707 digits. This was also incorrect after the 527th digit. These calculations took Shanks years and were performed in an entirely straightforward fashion using no tricks or shortcuts. [...] The mistakes went unnoticed until 1945, when D. F. Ferguson, in one of the final hand calculations, produced 530 digits. Shanks published his first result in 1853, and the w a y in which these erroneous decimals were statistically analyzed for almost a century is a story in itself. He m a d e quite a reputation with those digits: they were shown at the great world exposition in Paris before World War II. A report from 1937 says it as follows:

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

51

The mroom today (top), and in the past (bottom). In a small round room the walls show a summary of the history of mathematics. On the framework of the dome of this room, one finds the 707 decimals of the number calculated to date. M a n y textbooks w e n t on using this e r r o n e o u s value long after the m i s t a k e h a d been noticed. G a r d n e r too deplored this r e p r o d u c t i o n of Shanks" digits in recent books. Even in 1967 a French p u z z l e book still u s e d these 707 decimals. A n o t h e r encyclopedia of m a t h e m a t i c s provides a p h o t o g r a p h of the or-room as it is t o d a y with the legend In the dome of the Palais de la D6couverte in Paris, the first 627 decimals of the transcendent number zr were inscribed; however, it seems that some of the digits are wrong. The Palais de Ia D~couverte m u s t h a v e b e e n overw h e l m e d with reactions of that kind. In 1990 they p u b lished, with the assistance of the Mfnist&e de l'Education 52

THE MATHEMATICALINTELLIGENCERVOL. 18, NO. 2, 1996

[...] Let us point out that the decimals shown at the Palais de la D6couverte are exact, no matter how the scurrilous rumor might have it: in 1937, the celebrated 7r-room presented the record of that time [...] In 1945 [...] they were corrected in the room only a few months later [after Ferguson noticed the mistake]. Indeed, it is a false rumor! O n the preceding page is a composite p h o t o g r a p h showing the or-room as it was more than 50 years ago and as it is today. N o w look in the lower half of the p h o t o g r a p h (the part dating from 1937), at the series of digits at line 4, that starts above Poincar6's and Poisson's n a m e s : . . . 0213950160924480 772 . . . Indeed, they startle e v e r y well-informed reader at once: they are the incorrect digits! C o m p a r e those digits to the ones in the u p p e r half of the p h o t o : . . . 02139 49463952247371 . . . that's better. The exposition about the history of mathematics has been r e m o v e d , like the incorrect digits (compare the pictures). Today, a s u m m a r ~ of facts about ~- can be admired. Because of its st~ape in the form of a dome, and because r is the sixteenth letter of the Greek alphabet, the French writer Claude Gagni6re baptized the or-room chapelle 16: an idea for a mathematical pilgrimage.

Nationate, a postcard with the first 2500 decimals of 7r (is this what statisticians call a pie-chart?). On the back, they printed a rectification:

Aarsthertogstraat 42 8400 Ostends Belgium

Errata In " S y m m e t r y of Fractals Revisited" by E. Lau and D. Schleicher (vol. 18, no. 1, pp. 45-51), the righthand c o m p o n e n t of Fig. 6 on p. 50 is incorrect. (What is s h o w n is actually a detail of the U~00 set from Fig. 5.) An enhanced version of the correct figure can be seen on the cover of the issue. In vol. 16, no. 4, w e presented a display called "Check It Out," with four versions of a quotation from a letter by Babbage. The reader was invited to verify that the original text had been slightly altered in translation and retranslation, then restored closer to its original form in the Babbage Works. In a clerical error b y The Intelligencer, the point was partially lost. The n u m b e r 100 appears, in our display, in all four versions. Actually, it is 120 in the original, then 1l~0 in the translation and the retranslation, then again 120 in the Works.

Editor's note: Readers of the article in vol. 16, no. 4 on the finding of the Babbage letter are referred also to an exhaustive response by J.A.N. Lee in IEEE Annals of the History of Computing (1995), no. 4, 7-23.

MOVING? We need y o u r new address so that y o u d o not miss any issues of

THE MATHEMATICAL INTELLIGENCER. Please fill out the form below and send it to:

Springer-Verlag New York, Inc. Journal Fulfillment Services P.O. Box 2485, Secaucus, NJ 07096-2485 Name

Old Address (or label)

Address City/State/Zip

Name

New Address

Address

City~State~Zip Please give us six weeks notice.

THE MATHEMATICAL INTELLIGENCER VOL. I8, NO. 2, 1996

53

Ro er A 6r, 1916---1994: A adica MY'athematician Fran(;ois Ap6ry

A Spaghetti Lover His father Georges Ap6ry, a Greek born in Constantinople in 1887, came to France in 1903 to prepare for studies at the Ecole Nationale Sup6rieure d'Ing6nieurs at Grenoble. Enlisting as a volunteer as a w a y to obtain French citizenship in 1914, he took part in the Dardanelles campaign in 1915 and was brought back to France aboard a hospital ship after contracting typhoid. Later he was allowed to travel to Rouen, where he married Justine Vander Cruyssen. She had gallicized her family name to Delacroix and, not liking the name Justine, called herself Louise. It was in Rouen that their only child, Roger Ap6ry, was born on November 14, 1916. His childhood was spent in Lille until 1926, when the family moved to Paris. Installing the family in a coldwater flat on the rue de la Goutte d'Or in the 18th arrondissement, his father counted on the situation improving so they could move to better lodgings. But Georges Ap6ry, like so many others, was a victim of the 1929 economic crisis: he lost his position as an engineer and, being judged too old, was never again able to work in his field. His job was custodian at the Minist6re des Anciens Combattants. Louise gave piano lessons here and there, but the hope of better days died out and for the rest of their lives they remained in the run-down apartment, with communal toilet, no gas, and heat only from the old cast-iron stove in the kitchen. Lighting was by oil lamps until, after the Second World War, Georges Ap6ry himself installed electricity. 54

Naturally a young boy would try to find a way out of this environment. Roger, encouraged by his parents, followed the republican path of relying on academic Success.

Intellectual, in the sense that all his time was devoted to pursuits of the mind, he would always feel wary and a bit inferior when any problem demanded a technical solution. His first and only experience with manual labor, in a woodworking class in school, ended with the breaking of a board over a fellow student's head. A chess lover, he would regularly take on the students at the University of Caen, and in 1966 presided over the newly formed "Alekhine circle." He was proud a few

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Veflag New York

He underwent an operation for cancer of the colon; but it was Parkinson's disease, first diagnosed in 1977, that caused his death. It eroded his motor ability, reduced his ventures outside, kept him from writing or playing the piano, and finally more and more impaired his intellectual faculties. He died on the 18th of December 1994, in Caen. E d u c a t i o n : Y o u S h o u l d D o a Bit o f C h e m i s t r y

Figure 1. At his Sorbonne oral in 1939.

years later (during a mathematical meeting at Antwerp) to be the only winner in a simultaneous match by the champion of the Netherlands. His romantic life was troubled. He married in 1947 and had three sons, but a tense and bitter home life ended in divorce in 1971; a second marriage in 1972 was followed by a second divorce in 1977. He could not seem to reconcile family life, mathematical research, and political activism. From the Greek side he inherited a taste for pasta and a more-than-healthy appetite (his grandfather died from a spaghetti-induced indigestion), as well as the habit of drinking strong black coffee with a glass of water on the side. From his mother came his musical bent: she taught him enough piano that he could contemplate, at 18, a career in music, but his parents made him see the hazards of such a path. He headed instead toward mathematics, for which he showed promise early on. And finally, from his father he got his love of country, his intransigence in the defense of republican ideas as incarnated by Clemenceau, and maybe a need to always be right. He never did learn how to make concessions, even when it might advance his cause. This and his occasional resistance to the most basic social decorum might account for his nonconformist career-especially when combined with the distracted behavior of the absent-minded professor. (Students at Caen would long tell of the time the concierge interrupted his class because there was a crying child on his motorbike: he had forgotten to take his son out of the baby seat.)

Roger was a solitary, dedicated student at boarding school, bringing home prize after prize. He left Lille's Lyc6e Faidherbe in 1926 after skipping two grades, and gained a reputation as a crack student at the Lyc6e Ledru-Rollin and the Lyc6e Louis-le-Grand in Paris. He was passionately interested in history and above all mathematics; not so much in languages, as he spoke only a little German and Italian. At 8 he was interested-in the "preuve .par neuf'; at 12, in Euclid's postul~e; but at 16 he learned from his former professor that the cross-ratio of the four tangents from a point to a nonsingular plane cubic'is a projective invariant of the curve, and his passion for algebraic geometry began. He placed only third in the national mathematics Concours G6n~ral in 1932, for having written that the absolute value of a sum is the sum of the absolute values. The following year, at the Concours G6n6ral for the last year of secondary school, he learned by a leak from the son of a grader that he had the best mark in all Paris. Unfortunately, it turned out when the grades were posted that he had been beaten by a nose by a student from outside Paris: Gustave Choquet. He had to be content with second prize in mathematics and honorable mention in physics. He received his baccalaur6at in mathematics and philosophy in 1933, and entered the taupe of Paul Robert. (Robert later got Ap6ry's first scientific article published in the Revue de Mathdmatiques Spdciales.) Too much political activity kept him from getting into the Ecole Normale Sup6rieure in 1935: despite a near-perfect score in mathematics, he ranked only 93rd. "Mister Ap6ry, you should do a bit of chemistry," Robert told him--crucial advice for the competition the following year. The professor in the oral exam said, "What did I give you last year? I hope that this year you know the answer." You bet he did. In analysis, faced with a series to sum, he started by studying the first terms. "You might as well go scratch your balls somewhere else!" cried Jean Favard in his stentorian voice. (Later, when he was in Favard's course at the Sorbonne, he found to his surprise that some of his classmates were at the caf6 across the street. "We're not skipping class," they said; "it's more comfortable here, and we can hear him just as well.") He entered rue d'Ulm in 1936 with the second ranking, and, coached by an upperclassman, Raymond THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996 5 5

Figure 2. Roger Ap6ry, celebrating his birthday in Greece, 1986, is threatend by a knife-wielding mathematician's wife, Joan Mend6s-France. The other diners are Michel Mend6s-France and Alan Baker.

Marrot, he came out on top (cacique d'agrdgation), having at the same time obtained his Dipl6me d'l~tudes Supdrieures in inversive geometry under Elie Cartan. The agrdgation doesn't constitute a prime objective for a future researcher; all a good grade does is ensure a good start toward a career in teaching. However, the students of the Ecole Normale Sup6rieure traditionally treat it as a competition among themselves. The golden boy in 1939 was a golden girl: Jacqueline Ferrand (who as Jacqueline Lelong-Ferrand was to become a well-known geometer). Her reputation for efficiency intimidated the opposition. Marrot, having heard Ap6ry's oral entrance exam, knew the kind of fireworks he could produce and knew that this could make the difference, provided he came through with them when it counted. What was needed was motivation to rise to the challenge. At the time, the students of the Ecole Normale Sup6rieure liked to divide themselves into two hostile camps: those who attended Mass, the talas (from "ceux qui vont-?Ma messe') and those who didn't, the antitalas. Ap6ry was a rabid anti-tala. Marrot said to him, "You're not going to let a tala take first place, are you?" From that moment on, Ap6ry put himself in training under his mentor Marrot, and the race was on. 56

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

One of the three written tests was in analysis, set by Jean Dieudonn6. He recalls, "I was a member of the agrdgation jury, for the only time in m y life, by the way, and I gave a rather unusual analysis problem. Only two of the papers impressed me with their sense of analysis and precocious maturity very rare among candidates for the agrdgation. Those two were by Roger Ap6ry and Jacqueline Ferrand." And now in the words of the candidate: "I was never so bored with an analysis test. After reading the statement, I told myself that it would be stupid to turn in a blank test form. So I did the first question, then the second, and one after the other, until just as the seven hours were up I was finishing the last question. But at no time could I grasp the spirit of the problem." Still, it was good enough that Dieudonn6 gave him the maximum mark. To relax after the written exam, his mother took him to dinner: he was served a plate overflowing with whitings, and he downed 37 before declaring himself sated. At the oral, Ap6ry got to know Jean Dieudonn6, who would remain his friend. Impressed by his aplomb during the algebra oral, Dieudonn6 exclaimed, "Mister Ap6ry, you can really juggle determinants!" Then he asked, "Have you read Van der Waerden?" Ap6ry ad-

Figure 3. Enjoying the refreshments with Jean Dieudonn~ at the awarding of the title Chevalier de la Ldgion d'Honneur, 1970.

mitted he had not, but continued, "It is not in the t~cole's library." This was a good enough excuse to save him first place, which he shared with his rival Jacqueline Ferrand. The book appeared in the library the next year. Italian Algebraic Geometry: I've Heard You're in Germany He was mobilized in September 1939, taken prisoner of war in June 1940, repatriated with pleurisy in June 1941, and hospitalized until August 1941. During his captivity he stayed in touch with Lucien Godeaux, also with Francesco Severi, from whom he received several articles through the Red Cross. He received, for example, the following letter in 1941: "Dear Ap6ry, I've heard you're in Germany. You should take the opportunity to visit Professor X at the uhiversity of G6ttingen . . . . signed, F. Severi." He was lucky enough to get from Georges Bruhat, director of the Ecole Normale Sup6rieure, a research fellowship at the CNRS; then in 1943, Elie Cartan, who had intervened with the authorities to get him repatriated, offered him a post as assistant at the Sorbonne. He again took up his mathematical production that had been in-

terrupted by the war; he wrote his doctoral thesis in algebraic geometry under Paul Dubreil and Ren6 Garnier in 1947, and became the youngest Maitre de Conf6rences in France that year, at Rennes. In 1948 he gave the Cours Peccot at the Coll6ge de France on the theme' of "Algebraic geometry and ideals." He became professor at Caen in 1949. His specialty, from algebraic geometry over the complex field, gradually slid to algebraic geometry over the rationals, and then toward number theory. His work between 1939 and 1948 on Italian algebraic geometry in the tradition of F. Severi and L. Godeaux led to his thesis, in which he gave a theory of ideals in the framework of graded commutative rings without zero divisors and applied it to the notion of liaison among algebraic varieties. He proved in particular the theorem of liaison among curves, which states that every space curve of the first kind in p 3 is equivalent modulo liaison to a complete intersection. (This theorem was rediscovered later by F. Gaeta and was generalized by C. Peskine and L. Szpiro in 1974 with improvements by A. Prabhakar Rao in 1979.) He also generalized a Van der Waerden result about the order of intersection of a surface with a variety of codimenTHE MATHEMATICALINTELLIGENCERVOL. 18, NO. 2, 1996

57

sion 2, and constructed a variety of degree 22 in p13 for which the sections are canonical curves of genus 12, in contradiction to a claim of Fano. He never got on board the bandwagon of schemes that Grothendieck launched in the early sixties; but in summer 1964, at the Sdminaire de mathdmatiques supdrieures in Montreal, Dieudonn6, who was giving an exposition of the algebraic geometry of schemes, called on Ap6ry to give a simultaneous translation of all the results into classical language. In 1945 he proved the following result in algebraic topology about the neighborhood of a curve lying on an algebraic surface: If neither the algebraic curve nor the algebraic surface has singular points, then the boundary of an appropriate neighborhood of the curve is a Seifert fiber space whose first Betti number is that of the curve and whose torsion coefficient is the degree of the divisor defined by the curve.

Diophantic: I Said Nontrivial His turn toward arithmetic during the fifties was manifested notably in his study of the Diophantine equation x2 + A = pn, where A is a given positive integer and p is a prime. He demonstrated that, except in the case p = 2, A = 7 treated by Ramanujan and Nagell, there are at most two solutions. In 1963, Helmut Hasse, a former student of Hensel, worried that he didn't understand the proof, although it was based on Skolem's p-adic method. Yielding to Charles Pisot's pleas, Ap4ry answered Hasse, citing his Zahlentheorie. It was hard for him to suppress the feelings he had toward this man who had come during the occupation, in a Navy uniform, to ask the collaboration of French mathematicians with the Zentralblatt ~ r Mathematik, and who had seemed when they met in 1960 to have retained pre-1945 loyalties, to judge by his remark, "I don't like the city of Caen, it's where the invasion started." In 1974 Ap6ry presented at the ]ourndes arithmdtiques in Bordeaux a result on a Mordell conjecture concerning the existence of nontrivial rational solutions to the equation !/2 = px4 + 1, when p is a prime congruent to 5 modulo 8. He was able to prove by a descent argument that the group of this curve of genus 1 is either of rank I or of rank 0, depending on whether the equation pX 4 - 4Y4 = Z 2 admits nontrivial integral solutions or not. The proudest moment of his career was his proving, at more than 60 years of age, the irrationality of ((3). Having noticed that the procedures developed for summing divergent series in the heyday of complex function theory were convergence accelerators, he applied them to construct sequences of rational numbers for which the rapidity of convergence implies the irrationality of their limit. This method worked for loga58

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

rithms of rationals greater than 1; it worked for ~ (2); and, applied to the series (-1)~- 1 n = 1

(2n)n3

'

which he obtained from the diagonal of a number table due to Ramanujan, it allowed him to show the irrationality of ( ( 3 ) in 1977. H. Cohen showed that the method also applies to ~-/3 V 3 , and M. Prevost was able to extract from that the irrationality of the sum of the reciprocals of the Fibonacci numbers. Ap6ry, in the manner of Diophantus, Fermat, Euler, Kronecker, or Ramanujan, had a feeling of personal friendship toward particular numbers, although the book Diophantic which he was dedicating to them was never finished. During a mathematicians' dinner in Kingston, Canada, in 1979, the conversation turned to Fermat's last theorem, and Enrico Bombieri proposed a problem: to show that the equation (x) + (Y) = (n)

w here n -> 3

has no nontrivial solution. Ap6ry left the table and came back at breakfast with the solution n = 3, x = 10, y = 16, z = 17. Bombieri replied stiffly, "I said nontrivial."

Political Commitment: Moli6re Was Right Not to Like Priests Parallel to his mathematical work, Ap6ry was deep in politics from his youth, under the banner of Radicalism. While in second form at Louis-le-Grand, he boarded with the Fathers of the Catholic ]~cole Bossuet. The Abbot, searching Ap6ry's papers while he was absent, found a tract containing the words, "Moli6re, who was right not to like priests... ". This "was right" earned him a detention from the director, and the experience confirmed him as an "anti-tala," whose anticlericalism made him right at home in the Radical Party. If his political consciousness solidified quite early around laicism, his political activity dates from the riots of February 1934, when he joined the Camille Pelletan Radical Party. In 1936, the Camille Pelletan Party got two seats classified "miscellaneous left" in the Legislative Assembly of the Front Populaire, which he actively supported. It wasn't easy to be anticlerical at the rue d'Ulm before 1940; his literary friend Robert Escarpit, who secretly shared his convictions, envied this great mangeur de curds who dared to bill himself as the Pope of Radical Socialism. His classmates would welcome him mockingly with "Ave, ave, ave Ap6ry" to the tune of "Ave Maria," and when he tried to sign them up in the Amicale R6publicaine de l']~cole Normale which he had just founded, they made fun of him by signing other people's names.

In 1938, Ap6ry signed the petition of t~douard Herriot against the Munich accords, and sent back his membership card in the Radical Party to that other I~douard, Daladier. On his return from the prisoner of war camp in 1941, Ap6ry plunged back into political activity under the influence of his friend Marrot, a Communist. This despite the disillusionment with the Communist Party over the Non-agression Treaty between Nazi Germany and the Soviet Union in 1939, which had ended all his hopes for the Front Populaire. He signed on to the Louis-FernandMarty network under the pseudonym Arthur Morin. He became director of the Front National, a resistance movement at the t~cole Normale Sup6rieure, when his predecessor, Marc Zamansky, was arrested and deported to Mauthausen. Ap6ry organized a protest march against the arrest of Georges Bruhat and Jean Baillou; he took part in the demonstration against the forced wearing of the yellow star; he distributed clandestine press, such as Le Courrier du Peuple (the underground incarnation of Le Jacobin, organ of the Young Socialist Radicals of the Seine), which made its first appearance on his return from the stalag; he sent men to the underground, manufactured false identity papers, and transported arms. Danger was ever-present, and his courage sometimes crossed over into foolhardiness, as when he insulted a French adjudant in German uniform in Drancy and threatened him with court-martial, all under the eye of a German officer, who luckily didn't speak French. Anyway, Le Courrier du Peuple did not camouflage its message with any aesopian formulas: "To work, people of France! With bomb and sabotage, destroy the German war effort! Rather than crying over the bombing victims, the people should throw themselves into resistance and beat the Royal Air Force to the punch in destroying German factories and materials." This in November 1943. When the Gestapo arrested a student who was absent from rue d'Ulm during the night of August 4th, 1944, they undertook a systematic search of the premises. Ap6ry, who had been making false identity papers in his room, hurriedly burned all the compromising documents. The Gestapo took Mrs. Bruhat and Mrs. Baillou hostage, to exchange them for their husbands the next day; the cleaning woman, not realizing the implications, was complaining loudly about the ashes left in Ap6ry's room. Bruhat and Baillou were deported, and Bruhat perished at Buchenwald. It's a miracle that Ap6ry ~urvived all this without a scratch. His all-or-nothing personality, coupled with a distracted, absent-minded manner, made a combination inconsistent with the caution for which those times called. He felt them breathing down his neck several times, yet he took childlike amusement in episodes like the time he was stopped by the Gestapo on the Boul'mich with a long package wrapped in newspaper

under his arm. "Is that a g u n ? ' " N o , it's a leg." It was Marrot's prosthesis which he was taking to get repaired. Ap6ry received the Croix de Combattant Volontaire, as had his father after the First World War. The Communists discredited themselves in his eyes after 1948 by defending the Soviet endorsement of Lysenko's biology. Privately, and in public speeches in 1952, he warned against the imposition of a Marxist line on mathematics in France.

For Mend6s-France Against de Gaulle: Thank You for Your Testimony In his political activity in the 1950s, as he put it himsell "My place is in the party of Ledru-Rollin, Clemenceau, Herriot, and Mend6s-France, who embody the Jacobin tradition." He was a founder, at Mend6sFrance's invitation, of Les Cahiers de la I~dpublique; the name was his suggestion. As a candidate on the Mendesist ticket for the legislative elections of January 1956, he had to face up to the strong-arm tactics of the bouilleurs de cru, the local farmers who distilled their own eau-de-vie, who disrupted his meetings and attempted to intimidate the agricultural workers present. Ap6ry supported Mend6s-France faithfully in internal party quarrels and against the attacks of the Gaullists and the Communists. He came before the tribunal of the Mouvement de la Paix in 1954 to lambaste as "pacifists" the opponents of Mend6s-France's Indochina policy. On June 11, 1957, paratroopers under General Massu in Algiers arrested a Communist activist, Maurice Audin, a French mathematics assistant at the University of Algiers. A military report of 25 June reported him escaped. He was never seen again. Thus began the Audin Case. His family and friends doubted that he had ever escaped and suspected that he had died under torture. Intellectuals led by Laurent Schwartz formed the Comitd Audin to publicize the case and demand response from the authorities. Ap6ry was in charge of the Audin Committee in Calvados and broadcast the work of Pierre VidalNaquet on the case; he got a motion passed on it at the Radical Congress in 1957. Later, he left the Audin Committee when he thought it was being used to defame French policy as a whole. He led an active campaign in Calvados for republican legality against the coup de force of General de Gaulle in 1958. In the preparatory maneuvers for the election of the President of the Republic, Ap6ry achieved a reconciliation of the factions of the Union des Forces Ddmocratiques. (The U.D.F. candidate, nominated by him, was the well-known mathematician Albert Chatelet.) They wanted to prove that there was something between de Gaulle and the Communists: that something was 8.4% of the vote. He remained loyal to Mend6s-France's vision of THEMATHEMATICALINTELLIGENCERVOL.18,NO.2, 1996 59

Figure 4. At the University of Caen in 1969.

North Africa within the French Union. Sent to Algeria on a fact-finding mission as a reserve lieutenant in 1959, he reported to General de Gaulle on the faults of the colonial system but refused to characterize colonialism as simply an "action of exploiters in league with torturers." When a group of officers complained of the antinationalistic character of the French university and preached disobedience, Ap6ry's radical heart beat anew, and he reminded the military of its constitutional duty of submission to civilian rule. "Thank you for your testimony," was the General's lapidary response. He would never forgive de Gaulle for his military manner of returning to power, or for abandoning Algeria in the worst of conditions in 1962. After years of responsible positions in the Radical Party, he quit it in 1969, feeling that the republican spirit had expired in it. He ended, indeed, all involvement in 60

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

electoral politics; with the departure of General de Gaulle, he felt, the Republic was no longer threatened. A Budding Intuitionist

His vision of mathematics was individualistic like his political philosophy, rebellious to all orthodoxy. He was a constructivist. Formalism, with the Hilbert school as champion, succeeded by Nicolas Bourbaki, he saw as an a priori philosophy based on a metaphysic of the infinite, and not corresponding to the practice of the working mathematician. Practicing what he preached, he declined Dieudonn6's invitation to join Bourbaki. Later, at a congress of philosophy, Dieudonn6 called him a budding intuitionist. He led the scientific philosophy circle of the Ecole Normale Sup6rieure starting in 1944. He regularly faced off against Dieudonn6 in such forums, tenaciously de-

fending a pragmatism close to that of Poincar6, Borel, or Denjoy (although distancing himself from Brouwer) and refusing the idealism of Bourbaki. He collaborated on the journal Dialectica of Ferdinand Gonseth, becoming a member of the editorial committee in 1952 and an advisor to the director in 1966. The dominance of Bourbaki meant marginalization for the anti-Bourbakiste. Not being in sympathy even with all the other marginalized, Ap6ry eventually found himself nearly isolated. He remained able to offer stout defense to potential victims of the fashionable ideology, as with the "Halberstadt question," named for the algebraist who in the view of his patron Marc Krasner was also threatened with ostracism. He supported the call "for freed o m in mathematics" by Krasner and Chevalley in 1982, in response to recrudescence of the "Halberstadt question" on the editorial board of the Comptes Rendus de l'Acaddmie des Sciences de Paris. He felt close to Marc Krasner in philosophy and also shared with him an affinity for cats, love of the Balkans, and an immoderate taste for the pleasures of the table. One memorable excursion for bouillabaisse at a harbor restaurant in Nice after an international congress session was led by Krasner. He ordered appetizers and the royale for all 10 mathematicians; one by one they dropped out, on all sorts of lame excuses like wanting not to miss the afternoon lectures; the only ones to finish the gargantuan feast were Krasner and Ap6ry. At the end of the sixties, he returned to the attack on Cantor's set theory, plumping for category theory as better suited to the needs of mathematics. Facing Andr6 Revuz in a radio debate in 1972, he attacked the Lichn6rowicz teaching reforms, denying that the stagnation that had preceded gave any justification for abandoning geometric reasoning and enshrining Cantorian set theory. The reforms passed; he worried that 20 years later there would be a backlash in public opinion against mathematics, a prophecy that unfortunately came true. The instigators of the Lichn6rowicz reform insisted on loyalty to their program and tried to brand any opposition to it as reactionary, which only hardened Ap6ry's position and deepened his isolation in the community. It went so far that at the Journdes Arithm~tiques de Marseille in 1978, his lecture on the irrationality of ~"(3) was greeted with doubt, disbelief, and then disorder. Its recognition at the Helsinki Congress would finally erase this humiliation.

A p 6 r y a p4ri At the ]~cole Normale Sup6rieure he was ever the merry-maker, always ready for a canular, the practical jokes for which the normaliens are noted. There he had in Marrot the big brother he had missed in childhood. Marrot supported his iconoclasm. Marrot

spurred him to reenter politics after the liberation: "You are at the age where one chooses to become bourgeois or not." Marrot was his best man. Then in 1948, a gas worker forgot to replace a cap after a routine check, and Raymond Marrot, newly named Maitre de Conf6rences in Bordeaux, was asphyxiated along with his mother. The blow to Ap6ry was apparent to all. In the fifties, vacationing in Naples, he asked in a caf6 if there was a well-known mathematician in the city. He was directed to the legendary Renato Cacciopoli. Descended from anarchists and aristocrats (he was a great-nephew of Bakunin), he was a militant communist who moved in literary circles while professor of mathematics at Padua and then at Naples. Ap6ry got Cacciopoli's address and went to introduce himself: "Sono matematico francese..." But Cacciopoli interrupted in impeccable French and invited him for espresso as only the Italians can make it--and for piano four hands, with Cacciopoli singing the Verdi arias at earsplitting volume. ~heir friendship w6uld last until Cacciopoli's suicide in 1959. Ap6ry was a child of the patriotic and meritocratic left. He could never understand the intellectuals who profess egalitarianism in education and yet look down on technical education, which gives the most underprivileged children the possibility of a job that their family's means couldn't get them. His own children got technical educations. He classed the leftists of 1968 with the Hitler Youth. He opposed the antielitist program elimination of awards, tenured jobs, and faculties--as a replacement of the values of study and work by nepotism and favoritism. Regrouping old friends from the Resistance, he led the group known as "the Thirty-four" opposing the resignation of the Assemblde de la Facultd des Sciences in Caen; he joined colleagues from other regions and from all disciplines in a national appeal of June 1969 against the degradation of the universities. To him, this was upholding his lifelong political convictions, although to some he now looked as reactionary as he had been progressive. Resistance against Nazism under the Occupation, and resistance against leftism--for both reasons President Pompidou named him Chevalier de l'Ordre National de la Ldgion d'Honneur in December 1970. He received the decoration from the hands of Jean Dieudonn6. Resentments endured, and he found himself alone in his field. With the same hearty resolution he had stood up for free thinking against clericalism, for radicalism against the Right in 1934, for Resistance against National Socialism in 1940, for the Republic against Gaullism in 1958, for constructivism against Bourbakism, for the university against leftism in 1968. The graffiti artists, however, had the last word: Ap6ry a p6ri. F.S.T. 68093 Mulhouse Cedex France THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

61

Schri dinger's Time-Reversal of Natural Laws Robert Aebi

Introduction In 1931 E.rwin Schr6dinger published his nine-page-thin paper "Uber die Umkehrung der Naturgesetze" (On time-reversal of natural laws), in which he proposes a particular view of diffusions while seeking the meaning of wave functions in quantum mechanics. Schr6dinger puts forward the idea that diffusions, given their marginals at finite initial and final time, are time-reversible. As witness he cites Boltzmann in 1898: "Dass eine Welt ebensogut denkbar ware, in welcher alle Naturvorg~inge in verkehrter Reihenfolge ablaufen w6rden, unterliegt keinem Zweifel; jedoch h/itte ein Mensch, welcher in dieser verkehrten Welt leben wiirde, keineswegs eine andere Empfindung als wir. Er w6rde eben das, was wir Zukunft nennen, als Vergangenheit und "umgekehrt" bezeichnen."

elementary tools of today's probability theory. We want to track clouds of independent and identical particles, considering them as realizations of diffusions. The particle dynamics is assumed to be known. Based on the observation of a cloud at finite initial and final time, we want to make inferences on the "most probable" evolution of this cloud at intermediate times. In the degenerate situation of prescribed Dirac-type marginal distributions at initial and final time---initial and final states known precisely--the desired diffusion for intermediate times has a conditional probability law called the SchrfJdinger (Brownian) bridge. It simplifies the general situation in that only transitions from initial directly to final time remain to be considered. According to the fun-

(There is no doubt that a world could also be imagined in which all natural processes happen in time-reversed order. A human being living in such a reversed world would not feel differently from us. He would simply call past what we call future and vice versa.) Although admitting time-reversibility, Boltzmann originated a statistical mechanics which is not time-reversible. Schr6dinger however considers diffusions which are conditioned on their marginal distributions at finite initial and final time. In other words, the evolution of the stochastic process is conditioned on its behavior in the past and in the future. I will show below how Schr6dinger justifies his time-symmetrical conditioning, which is essentially distinct from traditional statistical mechanics. Schr6dinger's view of diffusions has some relevance in quantum mechanics, as ! will argue in the concluding section. Let us investigate Schr6dinger's suggestions by some 62

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Verlag New York

Figure 1. Observed perfume cloud diffusing from one scent-bottle to another.

damental hypothesis of statistical mechanics claiming that observations result from "most probable" microscopic realizations, I will s h o w h o w a large deviation principle yields so-called Schr6dinger systems which are systems of nonlinear integral equations. Their solutions, pairs of so-called Schr6dinger multipliers, p r o v i d e SchrOdinger representations of "most probable" diffusions for given dynamics u n d e r prescribed marginal distributions at two finite points of time. Distribution densities of diffusions in Schr6dinger representation possess structures which we can think of as prediction from the past and prediction from the future.

tributions qa and qb represent the reality on which our conclusions have to be based. What we actually observe is the result of a "guidebook" for traveling particles containing the numbers Fkl of those particles leaving from cell AXk which finally arrive at cell AZl, 1 ~ k ~ m, 1 ~ l <- n. H e n c e we are going to seek guidebooks (F kl)l ~k ~m, l
which obey the observation (qa, qb), i.e.,

Nqa(Xk) AXk = ~, Fkl, Most Probable Realizations Fixing a finite time interval - ~ < a < b < % consider partitions (AXk)l~k< m and (~LZl)I_~I_~,of the state space ~a at initial time a and final time b, respectively, as well as positions Xk E &Xk for 1 --< k ~ m and zl E ~zl for I - k -~ n. Imagine that we watch a large n u m b e r N of indep e n d e n t and identical parffcles performing a journey starting at time a and e n d i n g at time b. The observation of the particle cloud at time a and b, respectively, is expressed in terms of a pair of probability densities qa and qb on the state space ~ . Schr6dinger comments: This observation will be more or less exceptional, but this does not have to bother us. We rather assume that the dis-

(1)

1 <--k --<m,

(2)

1 <-- l <--n.

(3)

1=1

Nqb(Zl) AZl = Z Fkl, k=l

Dealing with N-particle journeys, w e require travel dynamics of the observed kind of particles. It can be given in analytical terms by a parabolic differential operator L or in probabilistic terms b y a transition density p(s, x; t, y), a ~ s ~ t -< b, x,y E ~d, w h e r e in this case, p is a (weak) f u n d a m e n t a l solution of the Fokker-Planck equation L = 0. Hence, for any particle departure density s, the probability of an individual particle starting in AXk at time a and arriving in AZl at time b is given by

Sk Pkl AXk AZl, THEMATHEMATICALINTELLIGENCERVOL.18,NO.2, 1996 63

i

i

.,.o" Figure 2. Observed particle densities at critical time a and first time b.

where sk = S(Xk), Pkl = p(a, Xk; b, zl) for I --- k -< m and I l -~ n. The independence of particles enables us to compute the probability of an N-particle journey belonging to a certain guidebook F [given by (1)] as m, t/

Z

(Sk Pkl AXk Azl)Fkt.

k, I = 1

In order to obtain the probability of a guidebook F [given by (1)], we have to find out h o w m a n y N-particle journeys F contains. This corresponds to the number of arrangements of N naturally distinguishable particles as subsets of Fkl particles, 1 ~ k -< m, 1 -< l s n. It is obtained by elementary combinatorics as

F12

n . ( N - ~ 1 .=F12F1l l )

J

F13

m ....(N-~'k=l

9. .

n-1

~l=lFkl -Fmn

m-1 ~k=lFkn)

N~ mr n Hk, l=1

Fkl!

(4)

Hence a guidebook F receives the probability PN(F) = N! 64

~-[ (Sk pkt AXk Azt)ok1 k,l=l Fkl!

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

Provided observed marginal densities qa and qb at initial time a and final time b, respectively, (2) is the continuity condition of F at initial time a and (3) is the continuity condition of F at final time b. Both together express that there are precisely N traveling particles and none of them gets lost on the journey described by F. There are m a n y guidebooks F which o b e y (2) and (3). The fundamental hypothesis of statistical mechanics will serve us in the next section as a criterion for determining the relevant guidebook F uniquely. It claims that

an observation on a macroscopic level is realized in the limit of infinitely many particles by that microscopic ensemble which has maximal probability given the observation. Schr6dinger's intention is to predict the distribution density pt(dy I qa, qb) of an N-particle cloud as N tends to infinity at intermediate times t E (a, b) for given particle dynamics pkl, 1 -< k -< m, 1 -< I -< n, under prescribed marginal densities qa and qb at initial time a and final time b, respectively. In the present approach I first investigate the so-called Schr6dinger (Brownian) bridge (6) and second the most probable guidebook density (11). A Schr6dinger bridge deals with determined initial and final conditions. They are described in terms of Dirac distributions as

(5)

qa= ~xa, qb---- ~zb

for fixed Xa, Zb E ~d. The number of particles which leave at time a from (x~, Xa + dx) and arrive at time b in (Zb, Zb + dz) is

It follows that the guidebook probability (5) possesses the limit

(8)

lim N log PN(F) = - H a ( z . ] s.p..),

N--~oo

Np(a, Xa; b, Zb) dx dz, where and the portion

Ha(~,.. ] s.p..) = ~

log

k, 1=1

Np(a, Xa; t, y) dy p(t, y; b, Zb) dx dz

(6)

In case the fundamental hypothesis of statistical mechanics has already produced a "most probable" guidebook in terms of a probability density q on ~d X ~d for general prescribed marginal densities qa and qb, we can write down the associated distribution density pt(dy [ qa, qb), t ~ (a, b), as a q-mixture of Schr6dinger bridges in the form

pt(dy I qa, qb) = f dx f dz pt(dy I

q(x, z).

(7)

The large deviation principle (8) will enable us to deduce the missing term q(x, z) in (7), and will lead to the product form of the resulting formula (14). This inspired Schr6dinger to a conjecture on the nature of quantum mechanics which we will consider later.

Because (Sk Pkl)l<_k-~m, l<_l
(e; 2X/~v (1 + ~)

Skpkl=O~Tkl=O

P r e d i c t i o n f r o m Past and F u t u r e

..

Ilk, l=1 Fkl!

X

m, nl + EN

m,

n

La(y.., A ) = k,,=l ~"

Ak" - 1 = 1

10 [

")qcl \

g~S-~kl) ykIAxkAzl

Azl

-

-

(10) for m 4- n Lagrangian multipliers Ak. and A2. The first mn Lagrangian equations OLa/O~,ij = 0 yield the "most probable" guidebook probability density

qq = q~aiSipij~bj, 1 <- i ~--m, 1 <--j <--n, on

N!

f o r l <-k<-m,l <-l<-n

is violated, Ha(Z. ] s.p..) is set equal to infinity. Relative entropies are non-negative and not symmetrical in their arguments. They are considered in statistical mechanics as the natural way to describe the amount of randomness in particle systems, and were already discussed by Boltzmann (~896) in his lectures on the theory of gas. The limit (8) shows that the probability (5) vanishes exponentially fast as N tends to infinity. Hence it represents a so-called large-deviation principle with the rate function (9). Seeking the "most probable" F [given by (1)] under the continuity conditions (2) and (3) means minimizing (9) under (2) and (3) as a function of (3qcl)l<-k-<m,l"~l<-n.

with e~--~ 0 as v---~o0

yields m, n

(9)

The minimizing problem provided by the large-deviation approach permits the Lagrangian procedure. We consider

A Large-Deviation Approach

v! =

~l Ak Azl

is called the relative entropy of ~/with respect to sp. In case

of them visits (y, y + dy) at time t on the journey from xa to Zb. Hence

pt(dy ] 6xa, 3Zb) = p(a, xa; t, y) dy p(t, y; b, Zb) p(a, Xa; b, Zb)

\ kpkl/

(11)

(AXk)l<_k<m X (AZl)l<<_l
1

r = exp{Ai.}, 1 --< i --~m,

-- (~-~rn+n-1

depends exclusively on the past at time a, and

~-I (3~kldiXk Azl)-rkt -1/2

Iik, l=1(1 + eFk) k,l=l

r

= exp{A.j -- 1},

1 --<j --~ n,

THE MATHEMATICAL INTELLIGENCER VOL, 18, NO. 2, 1996

65

depends exclusively on the future at time b. We call the ( qOai)l~i
j=l

Z ~ai Si pij &xi ~bj = qb(zj),

1 <--j ~ n.

(13)

i=1

This is a discrete version of a system of nonlinear integral equations obtained from the Lagrangian equations 3La/OAi.=O and 3La/OA.j=O in terms of (11). Schr6dinger himself considered neither existence nor uniqueness of solutions of the system (12) and (13). Such questions were investigated by Fortet (1940), Beurling (1960), Jamison (1975), F611mer (1988), N a g a s a w a (1989, 1993), Aebi and N a g a s a w a (1992), and Aebi (1995); the last two deal with more general dynamics p. In the continuous situation of infinitely m a n y cells with infinitesimal volume, the combinatorics employed to get (4), as well as the above Lagrangian procedure, do not work. Establishing the continuous version of (11) turns out to be not straightforward at all. F611mer (1988) and Aebi and N a g a s a w a (1992) give an approach based on Csiszar (1975, 1984), w h o develops a kind of geometry in the space of probability measures by means of the relative entropy "distance." The consequences of (7) are conveniently discussed in the continuous situation of Schr6dinger multipliers %(x) and ~b(Z) for X, z E ~d. The distribution density of an observed cloud of infinitely m a n y independent and identical particles at intermediate time t E (a, b) is given by the continuous version of (11) as

pt(dy I qa, qb)

(14)

= f dx f dz p(a, x; t, y) dy p(t, y; b, z) p(a, x; b, z) x ~a(X) s(x) p(a, x; b, z) ~b(Z) = ~a(t, y) ~b(t, y) dy, where

q~b(t, y) = f p(t, y; b, z) dz ~b(Z), t E [a, b),

"Die sogenannten irreversiblen Naturgesetze zeichnen, wenn man sie statistisch deutet, eigentlich keine Zeitrichtung aus. Denn was sie im speziellen Fall aussagen, h/ingt nur von den zeitlichen Grenzbedingungen in zwei "Querschnitten" a und b ab und ist bez/iglich dieser Querschnitte vollkommen symmetrisch, ohne dass es auf deren zeitliche Reihenfolge irgendwie ank/ime. Das wird nur dadurch etwas verschleiert, dass wir im allgemeinen bloss einen der beiden Querschnitte als wirklich beobachtet ansehen, w~ihrend fiir den anderen die zuverl/issige Regel gilt, dass, wenn er in hinreichenden zeitlichen Abstand verlegt wird, der Zustand gr6sster Unordnung oder maximaler Entropie dort angenommen werden daft. Dass diese Regel das Richtige trifft, ist eigentlich sehr merkw~irdig und, wie ich glaube, nicht logisch deduzierbar. Aber jedenfalls zeichnet auch sie keinen Zeitsinn aus, denn sie gilt gleichm~issig, in welche von den beiden Zeitrichtungen man auch den zweiten Querschnitt verlegt, wenn er bloss zeitlich gen~igend weit von dem ersten entfernt ist." (If considered from a statistical point of view, the so-called irreversible natural laws do not actually determine a specific direction of time. In fact, their statements only depend on the space cross-sections at two points of time a and b, and they are entirely symmetrical with respect to the conditions at time a and b. This is somewhat obscured by our habit of observing only one cross section in space. The second we usually put off to a sufficiently remote time, so we are entitled to assume that the state of greatest randomness, i.e., of maximal entropy, is achieved. It is really very strange that this rule should be true. I believe that it cannot be deduced logically. Anyway, this rule does not determine a specific direction of time either. It holds equally for both directions of time, provided only that the second space crosssection is sufficiently distant in time from the first one.)

(15)

for y E ~a, are space-time harmonic and space-time co-harmonic functions of p(s, x; t, y), a -< s < t -< b, respectively. The representation of a diffusion by a distribution density (14) as a product of (15) and (16) for certain dynamics p is called a SchrfJdinger representation. The structures of the distribution density Pt in (14) clarify the nature of the "most probable" diffusion for THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

conclusions:

In Schr6dinger's conception of diffusions, their timereversals are always considered simultaneously.

~a(t, y) = f ~a(X) s(x) dx p(a, x; t, y), t E (a, b] (16)

66

given dynamics p under prescribed marginal densities

qa and qb at initial time a and final time b, respectively. In fact, let us consider ~a and ~b as the "history" from past and future, respectively, determined by the observation (qa, qb) through the Schr6dinger system (12) and (13). According to (16), ~a(t, .) is the prediction from the past and according to (15), ~b(t, ") is the prediction from the future, i.e., time-reversed prediction. Hence the distribution density Pt at intermediate time t ~ (a, b) is the product of prediction from the past and prediction from the future. We should heed Schr6dinger's (1931) general

An Analogy to Wave Functions Schr6dinger stresses in 1931 that for him, the most interesting aspect of the distribution density Pt, t ~ [a, b], as a product (14) is its formal analogy to distribution densities ~ t ~ t formed out of solutions ~J~rt of Schr6dinger equations and their complex conjugates qtt, t ~ [a, b]. A familiar example might be the free (Brownian) par-

ticle. Its dynamics is represented by the space-time generator a 1 L=--+--A. at 2 The distribution density of the free particle in terms of pt, t E [a, b], in (14) is a product of a solution (15) of the Fokker-Planck equation L = 0 and a solution (16) of the adjoint equation L* = 0. As a consequence, Pt, t [a, b], does not evolve in a specified direction of time. In quantum mechanics,_the distribution density of the free particle is given as Wt Wt, t E [a, b], which is a product of a solution Wt of the Schr6dinger equation 1

and a solution q~t of the adjoint Schr6dinger equation

- x/27

t + l2a = 0 .

Both Pt and ~t ~t are obtained as products in a bilinear way from linear differential equations of first order in time and second order in space. Both describe a conservative and time-reversible phenomenon. This in contrast to the traditional distribution density satisfying the Fokker-Planck equation L* = 0 which describes a dissipative and time-irreversible phenomenon. Schr6dinger concludes by quoting Arthur Eddington: "The whole interpretation is very obscure, but it seems to depend on whether you are considering the probability after you know what has happened or the probability for the purpose of prediction. The ~t ~t is obtained by introducing two symmetrical systems of ~t waves traveling in opposite directions in time; one of these must presumably correspond to probable inference from what is known (or stated) to have been the condition at a later time."

References

Aebi, R., A solution to Schr6dinger's problem of non-linear integral equations, Z. Angew. Math. Phys. 46 (1995), 772-792. Aebi, R., Diffusions with singular drift related to wave functions, Probab. Theory Relat. Fields 96 (1993), 107-121. Aebi, R. and Nagasawa, M., Large deviations and the propagation of chaos for Schr6dinger processes, Probab. Theory Relat. Fields 94 (1992), 53-68. Beurling, A., An automorphism of product measures, Ann. Math. 72(1) (1960), 189-200. Boltzmann, L., Vorlesungen fiber Gastheorie, Leipzig: J.A. Barth Verlag, (1896). Boltzmann, L., Ober die sogenannte H-Kurve, Math. Ann. 50 (1898), 325 and Ges. Abh. III, Nr. 128, Csiszar, I.,/-Divergence geometry of probability distributions and minimization problems, Ann. Probab. 3 (1975), 146-158. Csiszar, I., Sanov property, generalized/-projection and a conditional limit theorem, Ann. Probab. 12 (1984), 768-793. F611mer, H., Random Fields and Diffusion Processes, F:coled" Etd de Saint Flour XV-XVII (1985-87), Lecture Notes Math. 1362, New York: Springer-Verlag (1988). Fortet, R., R6solution ..d'ur] syst6me d'6quation de M. Schr6dinger, J. Math. Pures Appl. IX (1940), 83-95. Jamison, B., The Markov processes of Schr6dinger, Z. Wahrsch. verw. Geb. 32 (1975), 323-331. Kolmogorov, A., Zur Umkehrbarkeit der Statistischen Naturgesetze, Math. Ann. 113 (1937), 766-772. Nagasawa, M., Transformations of diffusion and Schr6dinger processes, Probab. Theory Relat. Fields 82 (1989), 109-136. Nagasawa, M., Schr~dinger Equations and Diffusion Theory, Monographs in Mathematics,Basel:Birkh~iuserVerlag (1993). Schr6dinger, E., Uber die Umkehrung der Naturgesetze, Sitzung der Preussischen Akademieder Wissenschaflen,physikalischmathematischen Klasse vom 12.Ma'rz (1931), 144-153. Schr6dinger, E., Sur la th6orie relativiste de l'61ectron et l'interpr6tatioTI de la m6canique quantique, Ann. Inst. Henri Poincard 2 (1932), 269-319. IMSV University of Bern CH-3012 Bern, Switzerland e-maih [email protected]

He asks whether this analogy may give a better understanding of quantum mechanics, with the great difference of the occurrence of X/-1. Schr6dinger and Eddington suppose that quantum mechanics is of a probabilistic nature with intrinsic timereversibility. Later probabilistical models for quantum mechanics--among others by Born, Kac, F6nyes, Nelson, and Bohm--lose sight of the aspect of time-reversibility. Starting with Kolmogorov (1937) the treatment of timereversed stochastic processes has been improved essentially. In 1989 Nagasawa showed that a Schr6dinger equation with scalar as well as vector potential is equivalent to a pair of adjoint nonlinear diffusion equations which determine mutually time-reversed diffusion processes. As a consequence, diffusions in Schr6dinger representation (14) as a product of (15) and (16) can be considered as the real-valued counterparts to wave functions in quantum mechanics. They may yet provide a key to understanding quantum mechanics as a part of diffusion theory, as conjectured by Schr6dinger in 1931. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

67

68

THE MATHEMATICAL INTELLIGENCER VOL, 18, NO. 2 9 1996 Sprmger-Verlag New York

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

69

Through

a Reporter's Eyes -

T H E LIFE O F S T E F A N BANACH "r Translated and Edited by .6,. Kostant & W.Woyczynski, Case~Vestern Reserve University Roman

Kaluza

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 ofimerviews with people who knew and remember Banach, and conversations with mathemaricians 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 Approx. 150 pp.,24 illus. Hardcover $24.50 ISBN 0-8176-3772.9

Birkh

Forthcoming Fall 1996

EVARISTE GALOIS

(t8t i-i832) LauraToti Rigatelli, University of Siena Translated from the Italian by John Denton 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. 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. 1996 Approx. 180 pp. ISBN 0-8176-5410-0

user

B o s t o n 9 Basel 9 Berlin

70

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

Hardcover $34.50(tent.)

THE MATHEMATICAL EXPERIENCE Study Edition P.J. Davis, Brown University; R. H e r s h , University of New Mexico & E.A. Marchisotto, California State University, Northridge "...a perfectly marvelous book about the Queen of Sciences, from which one will get a realfeelingfor what mathematicians do and who they are. The exposition is clear andfuU of wit and humor... " - - The New Yorker (1984 American Book Award Edition) 1995 487pp. Hardcover $38.50 15BN0-8176-3739-7 Also Available by RJ. Davis, R. Hersh & E.A. Marchisotto - -

THE COMPANION GUIDE To the Mathematical Experience 1996 128pp..21 illus. Softcover $14.95 ISBN0-8176-3849-0

Jet Wimp* 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. Address the column editor, Jet Wimp.

Numerical Methods Based on Sinc and Analytic Functions by Frank Stenger New York: Springer-Verlag, 1993, 565 pp. US $69.00, ISBN 0-387-94008-1. Springer Series in Computational Mathematics Vol. 20.

Inherent in the cardinal function is the foundational "Sinc function" sin[~-(x - kh)/h]

S(k, h)(x) = r

- kh) /h

which Stenger distinguishes from the "sinc function" sin(vrx) sinc(x) = - -

Reviewed by Kenneth L. Bowers

(2)

(3)

"//'X

Imagine reading a mathematics paper [7] published in the respected journal Mathematics of Computation in 1971. The paper is entitled "Whittaker's Cardinal Function in Retrospect" and on the surface appears to be a review and further development of properties of a function referred to as the cardinal function. The function was described by E.T. Whittaker in the 1915 paper [10]. The first paragraph of [7] begins, The Whittaker cardinal function was discovered by E.T. Whittaker . . . . who wanted to know whether there exists in the class of all functions which take on the same values at the set of points A = {kh}~. . . . h > 0, "a function of royal blood whose distinguished properties set it apart from its bourgeois brethren". Who could not be intrigued by such a royal introduction? In the cardinal function, Whittaker believed he had found such a "function of royal blood." Thus began my exposure to the cardinal function. I had read Frank Stenger's review of sinc functions in [9] and had naturally enough been led to this work of J.J. McNamee (Stenger's mentor) and E.L. Whitney (Stenger's Ph.D. advisor). It was here [7] that I truly grasped the beauty of the-cardinal function, C(f, h), where for h > 0 and f a given function,

C(f, h)(x) -~ ~ k ~

flkh)S(k, h)(x).

(1)

--oo

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

Note that the Sinc function, for a fixed k and h, is a translation and dilation of the sinc function. This shows the obvious connection between the Sinc function and another area of current mathematical interest, wavelets. In 1935 J.M. Whittaker, E.T. Whittaker's son, published the tract "Interpolatory Function Theory" [11]. In the preface he apologizes for the title, "The title of this work is not, perhaps, a very happy one, but I cannot think of a better," and then thanks his father for his work on the cardinal function: Finally I wish to record my gratitude to my father, Professor E.T. Whittaker, more especially as his memoir on the cardinal function was the starting point of my interest in these matters. On the title, he is right, it is not a very "happy one." It hides the beauty of what lies inside. His gratitude toward his father is also enlightening. It is much like Frank Stenger's expression of gratitude to his mentor J.J. McNamee for calling this '~oeautiful f u n c t i o n . . . 'a function of royal blood whose distinguished properties set it apart from its bourgeois brethren'." In both cases, the beauty of the mathematics is what motivated the original interest in the cardinal function. Stenger's work in the theory of sinc and analytic functions, culminating in the publication of this book, has gone far beyond the beauty of the cardinal function to the practicality of its use in numerous areas of applied mathematics. Over the years since the publication of the works of both E.T. Whittaker and J.M. Whittaker, there have been

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Verlag New York

71

several reviews, including [1], [3], and [4], on the cardinal function. Most of these center around the use of the cardinal function in sampling theory and the Shannon sampling theorem. However, with Stenger's review [9] published in SIAM Review in 1981, the 1992 book [5], and now this book, we have overviews of the use of sinc methods in a much broader range of applied mathematics. Frank Stenger has been involved in the development of Sinc function methods for the past 30 years. These methods have been used in interpolation, numerical quadrature, including approximations of the Fourier, Hilbert, and Laplace transforms, integral equations such as Volterra and Cauchy singular, and ordinary and partial differential equations, to name a few. To quote the first paragraph in the preface of Stenger's book, The primary purpose of this text is to familiarize the student and computational scientist with the use of Sinc methods. These methods fill a void in computational mathematics in a manner similar to the way in which polynomials, splines, and Fourier polynomials fill a void; although we can get by without the methods based on these functions, our environment is made richer when the methods are available. Indeed, once one gets accustomed to using the methods in any one of these classes, it is difficult to get along without them. Each existing method excels in some particular class of problems. Sinc methods excel in problems with singularities and in problems posed on an infinite domain. They allow one to solve problems on ( - ~ , ~) or (0, ~) without artificially truncating the computational domain. They maintain their characteristic exponentially fast convergence rate even in the presence of singularities. For example, differential equations with singular solutions (solutions that have unbounded derivatives at the boundary) are automatically handled without regard to the singularity on the boundary and with no cumbersome grid refinement. Indeed sinc methods do enrich our computational mathematics environment. Stenger's historical remarks at the end of each chapter add a dimension that is all too often lost in present-day books. For instance, he points out that Goodwin [2] appears to be the first to have paid heed to the incredible accuracy of the trapezoidal rule over the real line for certain functions, and that from an earlier McNamee paper [6] it became clear that this class of functions was the one for which the bound on a certain contour integral could be made small. This class is the family HI(Da), and the trapezoidal rule is (exponentially) accurate on this family. Functions in the class Hl(Dd) which exhibit exponential decay on the real line can then be accurately approximated via a very practical and easily used truncated trapezoidal rule contained in Stenger's Theorem 3.2.1,

Is

~_~f(x) dx - h Z k=-N

J

f(kh) ~- cle -(2~1~'N)'/2.

(4)

Here we also learn "the rest of the story" concerning the McNamee paper [7]. It seems McNamee and 72

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

Whitney submitted a paper about Whittaker's cardinal function to SIAM Review. The paper was returned to them for modification. In Stenger's words, They were too proud to make the revisions,] inasmuch as many of the referees' demands were unreasonable, and after some time, with their permission, I made the modifications and I also added a few novelties. They thus allowed me to become a joint author.., and to become familiar with the very beautiful cardinal function. The paper was published in 1971 in Mathematics of Computation [7], long after the 1966 death of E.L. Whitney. The earlier chapters of the book illustrate the use of Sinc methods for interpolation, quadrature, numerical differentiation, and integral transforms. The later chapters are devoted to integral and differential equations; in particular, the last two chapters (Chaps. 6 and 7) make up half of the Sinc material presented in the entire book. I will conclude by focusing on the lengthy chapter (Chap. 7) on Sinc methods for differential equations. As Stenger says in the preface, Chapter 7, among others, attempts ... to summarize research on Sinc numerical methods, which my students and I, as well as some other mathematicians have carried out over the past thirty years. Besides aiming at a unified presentation, it is also desirable to achieve a certain amount of completeness. Thus, many of the results presented in this text are new, resulting from my "straying" to fill gaps in existing research. It is exactly this completeness, this filling in of the gaps, that makes this book so valuable. The use of Sinc methods for differential equations is a convenient alternative to finite difference, finite element, and standard spectral methods. For certain problems, this method can be extremely advantageous. It fits nicely as a complementary package with these methods due to its exponential convergence rate that is maintained even in the presence of boundary singularities in the solution. Originally proposed in Stenger's paper [8], the use of Sinc methods for differential equations has become a valuable alternative for applied mathematicians needing to solve singular problems. There is an extensive literature on the use of these methods for both ordinary and partial differential equations. This book provides the first comprehensive treatment of both the computation and implementation aspects of the method, as well as a solid mathematical foundation for such approaches. If for no other reason, this book is worth the price. Unfortunately, over 400 pages of development have led up to Chapter 7, pages which are not independent of this topic. An immediate jump to Chapter 7 is not feasible. The interested reader must digest considerable material before embarking on the Sinc solution of differential equations. A quicker approach to the implementation of the method is found in [5]. On the other hand, Stenger's book has all the details that the serious user could want. The desired space for the solutions of differential

equations is the space L~(D). In this space, one again finds an exponential convergence rate of roughly e -(~rd~/)l/2 for the Sinc method, where there are 2N + 1 basis functions and typically d = r The complexity, a measure of the amount of work required to achieve a certain accuracy, is often less for Sinc methods than for the more classical methods. Stenger emphasizes the unique combination of properties that only Sinc methods possess: (1) (Sinc) Galerkin and collocation methods yield algebraic systems that are very similar and equally accurate; (2) a priori determination of regions of analyticity of the solution for the purposes of domain decomposition can be done; (3) the algebraic-system formulation is simple, and the system, although full, is of relatively small size due to the exponential convergence rate; (4) the Sinc method automatically determines a nearly optimal gridpoint selection that routinely handles singularities; (5) the time domain may be handled globally, if desired, rather than marching step-by-step in time; and (6) the same gridpoints are used for all computations, including the evaluation of integrals, the approximation of functions or derivatives, and the approximation and inversion of integral transforms. The above list of features is exactly why more practicing scientists should be aware of, and familiar with, Sinc methods for differential equations. The Sinc method is a tool well worth using, and this book is the ultimate exposition on the subject.

References 1. P. L. Butzer, A survey of the Whittaker-Shannon sampling theorem and some of its extensions, J. Math. Res. Expos. 3(1) (1983), 185-212. 2. E. T. Goodwin, The evaluation of integrals of the form f~-~ a(x)e -x2 dx, Proc. Camb. Philos. Soc. 45 (1949), 241-245. 3. J. R. Higgins, Five short stories about the cardinal series, Bull. AMS (2)12 (1985), 45-89. 4. A.J. Jerri, The Shannon sampling theorem--Its various extensions and applications: A tutorial review. Proc. IEEE 65(11) (1977), 1565-1596. 5. J. Lund and K. L. Bowers. Sinc Methods for Quadrature and Differential Equations, Philadelphia: SIAM (1992). 6. J. McNamee, Error-bounds for the evaluation of integrals by the Euler-MacLaurin formula and by repeated Gausstype formulae. Math. Comp. 18 (1964), 368-381. 7. J. McNamee, F. Stenger, and E. L. Whitney, Whittaker's cardinal function in retrospect. Math. Comp. 25 (1971), 141-154. 8. F. Stenger, A Sinc-Galerkin method of solution of boundary value problems, Math. Comp. 33 (1979), 85-109. 9. F. Stenger, Numerical methods based on Whittaker cardinal, or sinc functions, SIAM Rev. 23(2) (1981), 165-224. 10. E. T. Whittaker, On the functions which are represented by the expansions of the iuterpolation theory. Proc. Roy. Soc. Edinburgh 35 (1915), 181-194. 11. J. M. Whittaker, Interpolatory Function Theory. Cambridge Tracts in Mathematics and Mathematical Physics No. 33, London: Cambridge University Press (1935). Department of Mathematical Sciences Montana State Univergity Bozeman, M T 59717-0240 [email protected]

Helaman Ferguson: Mathematics in Stone and Bronze by Claire Ferguson Meridian Creative Group (phone: 814-898-2612; website: http://www.meridiancg.com), 96 pp., US $29.95, ISBN 0-9639121-0-0

Reviewed by J. W. Cannon This book is a lovely depiction in light and shadow of mathematical art. Superbly produced by the Meridian Creative Group as its initial entry into the world of high-quality art books, it is a photographic study in muted colors of 30 mathematical sculptures or sculpture-groups created by mathematician-artist Helaman Rolfe Pratt Ferguson (who was introduced to readers of the Mathematical Intelligencer in vol. 13 (1991), no. 1, 30-39 and cover). The photographs are accompanied by a passionate series of appreciative mini-essays by the artist's wife, artist-wife--mother Claire Ferguson, and the whole is followed by a technical section of commentary by the artist himself which explains the genesis of each piece, from its mathematical conception, through its computer-aided design, its high-tech sculpting, and its finishing touches by means of dassical art and sculpture techniques. The photographs emphasize, through highlight, shadow, reflection, and multiple viewpoint, the heft, texture, form, and three-dimensionality of the pieces. One could hardly ask for more brilliantly chosen differential lighting or for better photography. The mathematical subjects vary: surfaces and surfaces-with-singularities, knots and knot-complements, classical complex analysis, transversality, and wild surfaces. It is strange in an art book to find statements of the theorem on the bivariate Cauchy kernel in several complex variables, the Hurwitz theorem on the symmetries of a Riemann surface, the scarcity of arithmetic knots, the Igusa conjecture, the volume of hyperbolic knot complements, Euler-Poincar6 characteristic, the Thom Transversality Theorem, fundamental groups, commutators, generators and relators. It is even stranger, in the presence of such mathematical artifacts, to contemplate their artistic representation in stone or bronze. Claire Ferguson quotes Rodin as to the artistic problems: The sculptor must learn to reproduce the surface, which means all that vibrates on the surface, soul, love, passion, life . . . . Sculpture is thus the art of hollows and mounds, not of smoothness, or even polished planes. (p. 9) The difficulties are not just artistic but also physical. H o w does one get a 1200 pound piece of white Carrara marble off of a truck and into position for carving when the trucker is happy to drive the piece to the door but will not take a hand in its unloading? We recall that Ferguson carved the piece on display in the headquarters of the American Mathematical Society from 1200 pounds in an 11-day reduction to a piece of 550 pounds. The heavy physical labor required 10-16 hours per day. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

73

Helaman Ferguson with his work Thurston's Hyperbolic Knotted Wye. (From Helaman Ferguson: Mathematics in Stone and Bronze, p. 62, published by Meridian Creative Group.) Photograph by Ed Bernik. 74

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

Or how did Ferguson cut the 232 seven-sided tiles approximating a tiling of the hyperbolic plane for the new piece on the patio of the Mathematical Sciences Research Institute in Berkeley? Most have seen the natural sculptural forms of the Grand Canyon carved out of solid rock by the abrasive Colorado River. I mused about capturing that sort of power in my studio. Looking over the south rim at the tiny filament of water glistening in the sun far below was about the filament size I saw close up in a water jet. One significant difference was the noise; the water jet seems to compress millions of years of erosion into a few seconds of roaring tornado sound, churning the catch chamber below into white water. The violent roar comes from a filament of water issuing from a diamond orifice under 55,000 pounds per square inch pressure. (p. 66)

Helaman has had his studio home-based for most of the twentyseven years he has been sculpting, which gave me and the family circus of seven children raging around him, access to the process from the beginning. (p. xiii) Dedication: To our seven sometime hours of unbridled passion become seven lives of living love: David then Heidi then Seth, Sam, Ben then Annie, Sarah Noelle, Jonathan, Alexander, Michael. (p. v)

This is a satisfying book, satisfying aesthetically, mathematically, artistically, humanly, physically. These sculpted pieces, pure as they are, can bear rich and joyful burdens. Department of Mathematics Brigham Young University Provo, UT 84602-1001, USA

Or how does one maintain the human side of the sculpture? Claire writes, Here then, emerges a whole new genre which bears some conceptual relationship to the tiles of the Islamic world of abstract forms but which is activated by humanism: the curiosity which led to scientific observation and inquiry and that characteristic fascination with the human body which powered the Golden Age of Greece and the Renaissance. The crucial difference in Helaman's work and his means of communicating the esoteric essence of an abstract theorem warmly to the viewer, is his constant reference to the human body. (p. xii)

A torus is a torus. But Ferguson wanted the torus in the shape of an umbilicus. Helaman relied on friends for actual umbilical cords and set to dissecting them. The three cord segments were quite interesting and I made a small number of clay models or maquettes about them or particular features. But I generated maybe a hundred computer 3D images about them much faster than it would be possible to physically make them or things like them. (p. 69)

Helaman generated equations for umbilical cord forms and tested these by making stereo pairs of computer graphics output to look at. It is interesting to contemplate whether the high-quality photography of this book could be combined with stereographic presentation or holographic presentation to give an even more physical view of Ferguson's work in book form. Helaman and co-workers have developed fascinating techniques for transferring abstractly calculated form into physical reality (p. 66). The latest machine is a virtual-image projector called the SP-2. The SP-2 has six cables whose lengths are monitored by sensors. The six lengths determine the three coordinates of position together with pitch, roll, and y a w of tool orientation. The sculptor interactively drives the apparatus and, according to computer calculated distance to the nearest point of the desired object, can cut away unwanted stone. One can feel the satisfaction and love in Claire's essays, or in their joint dedication: Why does he do sculpture? Just try to stop him; it's like trying to change the weather. (p. xiii)

Abraham Robinson.--The Creation of Nonstandard Analysis; A Personal and Mathematical O d y s s e y by Joseph Warren Dauben Princeton: Princeton University Press, 1995. 559 pp. Hardcover; US $49.50 ISBN 0-691-03745-0

Reviewed by Martin Davis On June 11, 1940, the 22-year-old Abraham Robinson found himself fleeing Paris just a few days ahead of the advancing German army. He and his fellow student from Jerusalem, Jacob Fleischer, had been awarded scholarships to study at the Sorbonne and had arrived in France only in January, undeterred by the state of war between France and Germany. In the spring, the "phony war" had ended abruptly as the Germans methodically advanced through the low countries and into France. By the time Robinson decided to flee, he and his friend Fleischer were among the thousands of refugees clogging the roads south and packing every available train. Because Palestine had been placed under British mandate by the League of Nations after World War I, the two young men were traveling with British passports. This enabled them to embark from Bordeaux for England on a refugee ship. This was one episode in Robinson's full and varied life. Born in a town in East Prussia (now part of Poland) as the First World War was drawing to a close, he fled with his family to Palestine as the Nazi persecution of the Jews intensified. Robinson spent the war years in England, where he met his wife Ren6e. He lived and held academic positions in Toronto, Jerusalem, Los Angeles, and N e w Haven. Abraham and Ren6e were prodigious world travelers who seemed to be at home anywhere. Quite apart from his mathematical research, Robinson's life makes a fascinating story and Joe Dauben tells it well. THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

75

Although it is for his brilliant work in mathematical logic and its applications to other parts of mathematics that Robinson is principally remembered, he had an outstanding second career as an applied mathematician. This began in England with his war work on aerodynamics and continued after the war. He wrote a treatise on wing theory and, at Toronto, had a number of doctoral students in applied mathematics. However, logic was his first love, and after the mid-fifties, logic remained the focus of his mathematical research. The idea of a mathematics of logical reasoning was one of Leibniz's great goals, and with the work of Boole it began to become a reality. Boole showed h o w the logic of Aristotle could be turned into algebra. However, Boole's logic was woefully inadequate for the inferences of ordinary mathematics. This defect was overcome by Frege in his Begriffsschrift of 1879. Frege's intention was not only to provide a systematization of logic, but also to show that arithmetic could be reduced to logic and thus to provide a foundation for all of mathematics. This program (ill-fated though it turned out to be) forced Frege to face a fundamental paradox redolent of circular reasoning: if the system being developed was to provide a foundation for mathematics, how could one justify the use of mathematics in its very development? Frege's far-reaching solution was to invent syntax. His Begriffsschrift (literally "concept writing") was a mercilessly precise language in which the rules of inference could be expressed as purely combinatorial mechanical operations without any reference to their meaning. The computer programming languages in use today can be seen as one application of Frege's invention. Bertrand Russell, in a famous discovery, found a contradiction in Frege's logical system for arithmetic. Soon it was generally realized that the incorporation into the body of mathematics of Cantor's new mathematics of the infinite--even of such parts of the theory of point sets as seemed necessary for classical analysis--was fraught with difficulties. Some like Brouwer and Weyl saw this as a hopeless situation; others proposed, in various ways, to use Frege's "symbolic logic" to find a way out of this dilemma. Hilbert in particular, refusing to be expelled from Cantor's "paradise," developed his famous program, proposing to obtain proofs that all would accept of the consistency of systems "formalizing" various parts of mathematics, on the basis of what amounted to Frege's logic. As a result mathematicians generally came to see research in logic as indistinguishable from efforts to provide mathematics with a secure foundation. Many would surely have readily agreed with Poincar6's dismissive comment [2]: It is difficult to admit that the word if acquires when written D , a virtue it did not possess when written if.

In this atmosphere, the realization that mathematical logic was an important tool in mathematical research quite apart from foundational issues was slow to de76 VaEMATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

velop. Abraham Robinson was a pioneer in this development and showed brilliantly h o w far it could be carried. Although Frege's invention of syntax was necessary for his effort to develop mathematical foundations, it also provided a new tool for studying mathematical structures. Such structures could be used to interpret the "meaningless sentences" of a logical system. A kind of duality between the set of structures "satisfying" a given sentence and the set of such sentences which a given structure satisfies provides the basis for a new branch of mathematics: model theory. The foundations of model theory can be found in the work of Skolem, Malcev, Tarski, and G6del. The realization that model theory could be used as a tool in (abstract) algebra only emerged in the 1950s in the work of Leon Henkin, and especially of Abraham Robinson. One of the key tools was the compactness theorem of G6del and Malcev: A set of sentences has a model if and only if each of its finite subsets has a model. It is by no means obvious how to "glue" together models for the various finite subsets of a given set of sentences to obtain a model of the entire set. The completeness theorem in G6del's doctoral dissertation provides one way to prove the compactness theorem: It follows from G6del's work that a set of sentences has a model if and only if no contradiction can be deduced from them using the rules of ordinary logic (e.g., Frege's). But any such deduction of a contradiction could only use finitely many of the given sentences! In addition to the compactness theorem, Robinson invented his method of diagrams (developed independently by Henkin) in which one works with sets of sentences corresponding to the complete "multiplication table" for a given algebraic structure. Since such structures could perfectly well be uncountable, this led quite naturally to extensions of Frege's language in which the set of "symbols" from which the sentences are constructed are actually uncountable, and hence a clear separation from the foundational aspect of logic. One immediate consequence of the compactness theorem was the existence, previously proved by Skolem, of "nonstandard" models, containing infinite elements, of the set ~ of true sentences of the arithmetic of natural numbers. To see this, let c be a symbol for a "constant," and consider the set F of sentences: 1~c,

1+1
1+1+1~c,....

The set of natural numbers itself then furnishes a model for every finite subset of ~ U F : for any such finite set, c can be interpreted as a sufficiently large natural number. By the compactness theorem, (*) ~ U F itself has a model ~ ; in ~;d~,c is interpreted by an element ~ which must satisfy ~ ~ n for all natural numbers n.

In January 1961 1 had the pleasure of being in the audience when Robinson explained for the first time his

amazing discovery that essentially the same argument could be used to provide a rigorous foundation for Leibniz's discredited infinitesimal methods in the calculus. Moreover, consider a "language" with a "name" for each r ~ ~, where ~ is the set of real numbers, as well as a name for each mapping f: ~ ~ ~. This time let be the set of true sentences in this language, and let F be as above. As before we can use the compactness theorem to infer (*). However, this time ~ must include sentences expressing the usual axioms for an ordered field. In particular, ~ will then have a reciprocal 1/~ that is positive but less than any positive real number, i.e., it is an infinitesimal. Of course, one doesn't require model theory to obtain non-Archimedean extensions of the reals, but this nonArchimedean extension ~ is special; all true sentences and only true sentences of ordinary analysis are true in ~ . For example, because the sentence expressing the addition law for the sin must be true in ~ , we can assert that if x is real and h is infinitesimal, then sin(x + h) = sin x cos h + cos x sin h, and proceed to differentiate sin x a la Leibniz; without the use of model theory there would be no evident way to do this. Robinson did not content himself with simply justifying the calculations with infinitesimals in which physicists and engineers had been indulging all along. He showed how "nonstandard" analysis could be made into a powerful tool. Complicated limit processes and compactness arguments could often be short-circuited

by using infinitesimal methods. (See [3].) With his student Bernstein, Robinson was able to use nonstandard methods to settle a problem that had been posed by Paul Halmos some years previously: to find an invariant subspace for a polynomially compact operator on a Hilbert space. (For their proof, see for example [1].) In the latter years of his life Robinson was particularly interested in applications of model-theoretic ideas in number theory, and also in attempting to understand the often-remarked analogy between algebraic number theory and the theory .of algebraic functions. Reading Dauben's rich biography and viewing the many photographs of Abraham Robinson in the various stages of his life, one is filled with a sense of loss as one nears the end. Robinson was only 56 when he died of cancer. He is greatly missed.

References [1] Martin Davis, Applied Nonstandard Analysis, Interscience-Wiley, 1977. [2] Henri Poincar6, Science and Method. Dover, New York, 1952. (Translated by F. Maitland from the original French edition of 1908.) [3] Abraham Robinson, Nonstandard Analysis. NorthHolland Press, Amsterdam, 1966. Reprinted 1970. Revised edition 1974. Courant Institute 251 Mercer Street New York, NY 10012 THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

77

Robin Wilson* One-dimensional Space Groups Istv in Hargittai and Magdolna Hargittai Table 1.

This recent (1994-95) series of H u n g a r i a n stamps depicts traditional folk art decorations embroideries, with the exception of the HUF 50 stamp which shows a patched-on decoration. Each stamp displays b o r d e r decorations exhibiting one-dimensional space g r o u p symmetries of one-sided bands. Such decorations are also called strip patterns or frieze patterns. As is well known, there are seven s y m m e t r y classes of such bands, illustrated below for a simple motif, the black triangle; the classification has been described recently b y Heather McLeay, Math. Intelligencer 16 (1994), no. 4, 61-65. Although all seven classes have been f o u n d in H u n g a r i a n n e e d l e w o r k (as we mentioned in our Symmetry Through the Eyes of a Chemist, 2nd ed., Plenum,

Stamp HUF*

1 2 3 9

Symmetry Class Top Side

6 4&7 6 1&4

6 6 7 5

11

4

7

12 14 19 22 32 35 38 40 50

4

7

7

7

4 4 4 4 7 6 4

1 4 1 4 6 4 4

*Hungarian Forint (USD 1 is approx. HUF 120 as of the Spring of 1995). N e w York, 1995), the fourteen stamps represent only five classes, and three of those predominate. Each stamp has decorations both at the top a n d at the sides, and two stamps have two decorations at the top. The s y m m e t r y types of the decorations are identified in Table 1.

Budapest Technical University Hungarian Academyof Sciences H-1431 Budapest H-1521 Budapest Hungary Hungary

Figure 1. The seven symmetry classes of one-sided bands: 1, simple repetition; 2, glide reflection; 3, half turn; 4, vertical reflection; 5, horizontal reflection; 6, vertical reflection plus glide reflection; 7, vertical reflection plus horizontal reflection. *Column editor's address: Faculty of Mathematics, The Open University, Milton Keynes, MK7 6AA, England. 78

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2 9 1996 Springer-Verlag New York

THE MATHEMATICAL INTELLIGENCER VOL. 18, NO. 2, 1996

79