No title

II=l~liomw~:ill

Chandler

Davis

Our New Look

I

eginning with this issue, w e are introducing a n e w look. The previous design served us well over many years. In the n e w format, m u c h care w a s given to preserving the basics and planning for n e e d e d changes. Our aim w a s to provide m o r e flexibility in han-

B

dling varied content, a stronger distinction b e t w e e n articles and departments, and greater suitability to electronic formats, type, and layout that are being used n o w and being created for the future.

Chandler D a v i s Editor-in-Chief

STATEMENT OF OWNERSHIP, MANAGEMENT, AND CIRCULATION(Required by 39 U.S.C. 3685). (1) Publication title: Mathematical InteUigencer. (2) Publication No. 001-656. (3) Filing Date: 10/1/96. (4) Issue Frequency: Quarterly. (5) No. of Issues Published Annually: 4. (6) Annual Subscription Price: $45.00. (7) Complete Mailing Address of Known Office of Publication: 175 Fifth Avenue, New York, NY 10010-7858; Contact Person, Joe Kozak, Telephone 212-460-1500, EXT 303. (8) Complete Mailing Address of Headquarters or General Business Office of Publisher: 175 Fifth Avenue, New York, NY 10010-7858. (9) Full Names and Complete Mailing Addresses of Publisher, Editor, and Mmlaglng Editor: Publisher: Springer-Verlag New York Inc., 175 Fifth Avenue, New York, NY 10010-7858. Editors: Dr. Chandler Davis, Department of Mathematics, University of Toronto, Toronto, Canada M5S 1A1. Managing Editor: Spnnger-Verlag New York, Inc., 175 Fifth Avenue, New York, NY 10010-7858. Owner: Springer-Veriag Export GmbH, Tiergartenstrasse 17, D-6912I Heidelberg, Germany, and Springer-Veriag Gmbh, Heidelberger Platz 3, D-12197 Berlin, Germany. Known Bondholders, Mortgagees, and Other Security Holders Owning or Holding 1 Percent or More of Total Amount of Bonds, Mortgages, or Other Securities: Dr. Konrad Springer, Heidelberger Platz 3, D-14197 Berlin, Germany. (12) The purpose, function, and nonprofit status of this organization and the exempt status for federal income tax purposes: Has Not Changed During Preceding 12 Months. (13) Publication Name: Mathematical Intelligencer. (14) Issue Date for Circulation Data Below: Summer 1996. (15) Extent and Nature of Circulation: (a.) Total No. Copies (Net Press Run): Average No. Copies Each Issue During Preceding 12 Months, 8900; Actual No. Copies of Single Issue Published Nearest to Filing Date, 8800. Co.) Paid and/or Requested Circulation: (1) Sales Through Dealers and Carriers, Street Vendors, and Counter Sales: Average No. Copies Each Issue During Preceding 12 Months, 1999; Actual No. Copies of Single Issue Published Nearest to Filing Date, 1978. (2) Paid or Requested Mail Subscriptions: Average No. Copies Each Issue During Preceding 12 Months, 4855; Actual No. Copies of Single Issue Published Nearest to Filing Date, 4875. (c.) Total Paid and/or Requested Circulation: Average No. Copies Each Issue During Preceding 12 Months, 6854; Actual No. Copies of Single Issue Published Nearest to Filing Date, 6873. (d.) Free Distribution by Mail: Average No. Copies Each Issue During Preceding 12 Months, 375; Actual No. Copies of Single Issue Published Nearest to Filing Date, 150. (e.) Free Distribution Outside the Mail: Average No. Copies Each Issue During Preceding 12 Months, 476; Actual No. Copies of Single Issue Published Nearest to Filing Date, 436. (f.) Total Free Distribution: Average No. Copies Each Issue During Preceding 12 Months, 851; Actual No. Copies of Single Issue Published Nearest to Filing Date, 586. (g.) Total Distribution: Average No. Copies Each Issue During Preceding 12 Months, 7705; Actual No. Copies of Single Issue Published Nearest to Filing Date, 7459. (h.) Copies Not Distributed: (1) Office Use, Leftovers, Spoiled: Average No. Copies Each Issue During Preceding 12 Months, 672; Actual No. Copies of Single Issue Published Nearest to Filing Date, 1341. (2) Return from News Agents: Average No. Copies Each Issue Dunng Preceding 12 Months, 523; Actual No. Copies of Single Issue Published Nearest to Filing Date, 0. (i.) (Sam of 15g, 15h(1), and 15h(2)): Average No. Copies Each Issue During Preceding 12 Months, 8900; Actual No. Copies of Single Issue Published Nearest to Filing Date, 8800. Percent Paid and/or Requested Circulation: Average No. Copies Each Issue During Preceding 12 Months, 88.96; Actual No. Copies of Single Issue Published Nearest to Filing Date, 92.14. (16) This Statement of Ownership will be printed in the Winter 1996 issue of this publication. I certify that all information furnished on this form is true and complete.

Craig Van Dyck Chief Operating Officer VOLUME 19, NUMBER 1, 1997

3

Lc

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.

Beppo Levi Among Physicists in Argentina

Anthropomorphic Origin of Platonic Solids?

llow m e to m a k e a small correction to N. S c h a p p a c h e r and R. S c h o o f ' s "Years Ago" article on B e p p o Levi (The Mathematical Intelligencer, vol. 18, no. 1, pp. 57-69). The p h o t o on p. 67 s h o w s the p a r t i c i p a n t s in the 1948 meeting o f the AsociaciSn F i s i c a Argentina, in front of the Observatorio A s t r o n S m i c o Nacional in C S r d o b a - not the UniSn Matemfitica Argentina. I k n o w b e c a u s e I a m in the photo, together with m y teacher, Guido Beck, and o t h e r physicists, notably Richard Gans and Enrique Gaviola, and a numb e r of g r a d u a t e students. Levi c a m e often to o u r p h y s i c s meetings, w h e r e he b e r a t e d us v e h e m e n t l y for using Dirac's delta pseudofunction, the prec u r s o r of Laurent Schwartz's distributions. He w a s also keenly i n t e r e s t e d in logic, the history of mathematics, a n d philosophy. He w r o t e in Spanish an extensive criticism o f certain a s p e c t s of m a t h e m a t i c a l logic, titled Correrias en la ldgica, a n d a penetrating analysis of Euclid's geometry, Leyendo a Euclides. I a m particularly grateful to him b e c a u s e he h e l p e d me out with s o m e integrals o f p r o d u c t s of Bessel functions, a n d w a s instrumental in m y a p p o i n t m e n t to the chair of p h i l o s o p h y of s c i e n c e at the Universidad de Buenos Aires in 1957. Beppo Levi w a s r e m a r k a b l y energetic yet subtle, and he w a s r i g o r o u s yet interested in a wide range o f intellectual pursuits. Last, but n o t least, he was g e n e r o u s with his t i m e even in old age.

nowledge of the five regular poly.hedra s e e m s to have originated in several environments, u n r e l a t e d to e a c h other, e.g., in China 2200 B.C., the British Isles b e f o r e 1400 B.C., and G r e e c e a r o u n d 500 B.C.1 It is usually suggested that the derivation of the Platonic solids w a s i n s p i r e d by observations of mineral crystals. Doing garden w o r k on stiff soil, I have c o m e to realise that the symmetrical bodies m o s t readily p r e p a r e d from plastic clay, in the a b s e n c e of a flat surface to w o r k on, are tetrahedra, cubes, spheres, and cylinders. The series t e t r a h e d r o n - c u b e - s p h e r e is relev a n t in the p r e s e n t context, since one o f the p r o p e r t i e s of Platonic solids is that they can b e c i r c u m s c r i b e d in a sphere, and with increasing n u m b e r of faces the p o l y h e d r a b e c o m e m o r e sphere-like. These t h r e e clay objects c o u l d be an alternative s o u r c e of inspiration. In o r d e r to m a k e a t e t r a h e d r o n or cube, the t w e e z e r grips f o r m e d b y t h u m b and forefinger are utilized, while in o r d e r to p r e p a r e a sphere, the p a l m s of the h a n d are used. If the design of the h u m a n h a n d w a s the ultim a t e origin of the Platonic solids, it is n o t so surprising that t h e s e a b s t r a c t p o l y h e d r a have b e e n reinvented several times.

A

MARIO BUNGE Foundations and Philosophy of Science Unit McGill University Montr6al, Qu& Canada H3A lW7

'4

THE MATHEMATICALINTELLIGENCER9 1997 SPRINGER-VERLAGNEWYORK

K

STAFFAN HANSEN Inorganic Chemistry 2 Lund University P.O. Box 124 S-221 00 Lund, Sweden l"Polyedrar," exhibition by S.G. Fregert and S. Holmer, Lund University Library, UB 2.

Distributing Many Points

on a

Sphere -'.

B.

S A F F

A N

D

A.

B.

J.

K

U I J

L A

A

R ,c

he problem of distributing a large number of points u n i f o r m l y over the surface of a t s p h e r e has not only inspired mathematicalresearchers,it has attracted the attention ~f:/t/~176 ogous problem is simply that of uniformly distributing points on the circumference of a disk, and equally spaced points provide an obvious answer. So we are faced with this question: What sets of points on the sphere imitate the role of the roots of unity on the unit circle? One way such points can be generated is via optimization with respect to a suitable criterion such as "generalized energy." Although there is a large and growing literature concerning such optimal spherical configurations of N points when N is "small," here we shall focus on this question from an asymptotic perspective (N--~ ~). The discovery of stable carbon-60 molecules (Kroto, et al., 1985)* with atoms arranged in a spherical (soccer ball) pattern has had a considerable influence on current scientific pursuits. The study of this C60 buckminsterfifllerene also has an elegant mathematical component, revealed by F.R.K. Chung, B. Kostant, and S. Sternberg [5]. Now the search is on for much larger stable carbon molecules! Although such molecules are not expected to have a strictly spherical structure (due to bonding constraints), the construction of large stable configurations of spherical points is of interest here, as an initial step in hypothesizing more complicated molecular net structures. In electrostatics, locating identical point charges on the sphere so that they are in equilibrium with respect to a

::t:u;hifi;l:: ::/i~:l :i~t;~ Coulomb potential law is a challenging problem, sometimes referred to as the dual problem for stable molecules. Certainly, uniformly distributing many points on the sphere has important applications to the field of computation. Indeed, quadrature formulas rely on appropriately chosen sampled data-points in order to approximate area integrals by taking averages in these points. Another example arises in the study of computational complexity, where M. Shub and S. Smale [22] encountered the problem of determining spherical points that maximize the product of their mutual distances. These various points of view clearly lead to different extremal conditions imposed on the distribution of N points. Except for some special values of N (e.g., N = 2, 3, 6, 12, 24) these various conditions yield different optimal configurations. However, and this is the main theme of this article, the general pattern for optimal configurations is the same: points (for N large) appear to arrange themselves according to a hexagonal pattern that is slightly perturbed in order to fit on the sphere. To make this more precise, we introduce some notation. We denote by S 2 the unit sphere in the Euclidean space R3: S 2 = {x E R 3 : Jxt = 1}.

Lebesgue (area) measure on S 2 is denoted by ~, so that

*Curl, Kroto, and Smalley received the 1996 Nobel Prize in Chemistry for their work on fullerenes. 9 1997SPRINGERVERLAGNEWYORK,VOLUME19. NUMBER1, 1997 5

4~r. A generic subset o f S 2 with N elements will be denoted by (ON. Associated with a configuration (ON= {Xb X 2 , . . . , XN} is a partitioning of the sphere into Dirichlet (Voronoi) cells Dl, 9 9 9 DN: o ~ S 2) =-

D j := {x E S2 : ix - xj] = m i n

l<_k<_N

(

8~" ~1/2 N -1/2 _ CN_2/3 <_ dN <-- ( 8Ir ~1/2 N_l/2.

]X -- Xk]}, j = I, . . . , N.

These Dirichlet cells are closed subsets of S 2 satisfying N

L J Dj = S 2,

were obtained first by W. Habicht and B. L. van der Waerden [13]. They proved that for some constant C > 0,

The essential idea for establishing the lower bound is to project the hexagonal tiling of the plane onto the sphere, from which the dominant term

Dj A Dk has empty interior i f j r k.

j=l

8 N : = ( ~ 3 3 ) 1 / 2 N -1/2

For large numbers of points, we have observed experimentally (numerically) that all but exactly 12 of the Dirichlet cells for an optimal configuration are hexagonal. The exceptional cells are p e n t a g o n s .

can be seen to arise via the following heuristic argument. For a planar hexagonal lattice normalized so that the minimal distance between points is 1, {m + n e i~r/3 : m , n E Z},

Why Hexagons? In the plane, we have the regular hexagonal tiling, and the centers and vertices of such hexagons solve several impog2.nt extremal problems in the plane. One example is the b e s t - p a c k i n g problem: Arrange nonoverlapping disks of the same fixed radius so that the number of disks per unit area is maximized. Likewise, the so-called best-coveri n g p r o b l e m is solved by the same points generated from the hexagonal tiling. We cannot tile the sphere using only hexagons. This is a consequence of the formula for the Euler characteristic: F - E + V = 2, where F is the number of faces, E is the number of edges, and V is the number of vertices. A modification of the hexagonal pattern such as the addition of some pentagonal faces is needed for spherical tessellation. Again, from the Euler characteristic, it follows that any tiling of the sphere consisting exclusively of hexagons and pentagons must have exactly 12 pentagons (assuming exactly 3 edges emanate from each vertex). These 12 pentagons may be viewed as the deformations (perturbations) in the hexagonal pattern, enabling it to fit on the sphere. As an example, we have for N 32 the familiar soccer ball design, which has 12 pentagonal and 20 hexagonal faces. The dual structure of the soccer ball consisting of carbon atoms placed at the vertices of the faces is the previously mentioned C60 molecule. Another, rather ancient and more complicated example is depicted on the cover of The M a t h e m a t i c a l InteUigencer, vol. 17, no. 3 (summer 1995), as the tiling of the ball beneath the lion's paw in a statue guarding the gates of a Chinese palace (finding the pentagonal faces amongst the many hexagonal ones there is an amusing diversion).

the Dirichlet cell of each lattice point is a hexagon with area ~/3/2. Considering an optimal arrangement of N points on the sphere, we now imagine that a typical point is the center of a Dirichlet cell whose projection on a tangent plane is part of a suitably scaled hexagonal lattice. (Here, we ignore the 12 pentagonal cells.) The required scaling factor ~N is obtained by equating total areas: N ~r 2

~N = 4rr,

which gives the value 8N = (ST'/V~) 1/2 N - u 2 for the approximate minimal distance between points. The technique of hexagonal projections has also been recently employed by the authors to study a general class of minimal-energy problems that we now describe.

Extremal Energy Fekete points x~, x ~ , . . . , x?v on the sphere are points that minimize

=

Best Packing on the Sphere This is one of the most studied problems in the mathematical literature dealing with spherical point arrangements. It is also referred to as T a m m e s ' s p r o b l e m , or the h a r d - s p h e r e s problem. It asks us to maximize the smallest distance among N points on the sphere. (For background, see, e.g., [6].) Asymptotic results on dN :=

6

min ]xj Xl,... , xNES2 l<--j
THE MATHEMATICALINTELLIGENCER

-

-

Xk]

E(1, (ON) : =

Z

l <_j
]Xj -- Xk] -1.

Physically, this represents the energy of N charged particles that repel each other according to Coulomb's law. More generally, one may consider points that minimize the s-energy E(s, (ON):=

Z Ixj -- xkl -s, l <j
S > O.

As s -~ ~, with N fLxed, the s-energy is increasingly dominated by the term involving the smallest of the distances. In this sense, the problem leads to the best-packing problem. Of related interest are points that maximize the product of the distances

17 Ixj- x l.

1--<j
This is equivalent to minimizing the logarithmic energy E(O, O.)N) : ~

1 7. log ix j _ xkl' l <_j
and extremal points for this problem are called logarithm i c extreme points or elliptic Fekete points. Finally, we mention the criterion of maximizing the sum of powers of the distances

Ixj - xkl%

>o.

l <_j
This problem is only interesting for a < 2; for even N and a >- 2, an extremal configuration is obtained by placing half the points at the north pole and the other half at the south pole. Extensive computations for optimal configurations and their corresponding extremal energies have been reported in a number of articles. Most deal with the Coulomb case (s = 1) [10,12], but other values have also been considered [4,19,21]. A particularly convenient listing is provided by Hardin, Sloane, and Smith, who have made their findings accessible via the internet address netlib.att.com. For large numbers N (say, N -> 100), these computations are far from trivial, and in fact are sometimes used for testing global optimization routines [2]. The bad (yet fascinating) news arising from computations is that there are many local minima for the s-energy problem that are not global minima. In addition, the local minima have energies very close to the global minimum. These facts make it very difficult to determine the precise minimum. It is estimated that the number of distinct local minima (ignoring rotations and reflections of the sphere) grows exponentially with N (see [liD. On the other hand, the good news is that, with only a handful of exceptions, the structures of extremal configurations computed for 32 ~ N ~ 200 with s -- 0 and s = 1 do indeed exhibit the hexagonal-pentagonal pattern of Dirichlet cells. See, for example, Figure 1, which shows 122 points in equilibrium along with their Dirichlet cells for the case s = 1. Its dual structure (the cage formed by the cells), which is displayed in Figure 2, provides a spherical candidate for the network pattern of carbon-240 molecules. All of the figures in this article were provided by Yanmu Zhou and appear along with extensive tables in his thesis [26].

Asymptotics for Extremal Energies Although the precise determination of optimal configurations for large N seems remote at best, explicit constructions of configurations that are close to optimal may well be within reach. A first step toward this goal is to determine precise asymptotics for the extremal energies. Results in this direction are due to G. Wagner, E.A. Rakhmanov, E.B. Saff, and Y.M. Zhou (for 0 < s < 2 and for logarithmic extremal points), and the authors (for s > 0). R. Alexander [1], J. Beck [3], and K. B. Stolarsky [23] have obtained results for the maximal distance sums. Denote by %(s, N) the minimal energies:

Figure 1. The 122 electrons in equilibrium and their Dirichlet cells.

is finite; indeed, a simple calculation shows its value to be 21 s/(2 - s). This enables the direct use of potential-theoretic tools. Wagner [24,25] and Rakhmanov, Saff, and Zhou [20] have thereby shown that 2--8

%(s, N) -- 2 - s N 2 - R N s ,

0<s<2,

N->2,

(2)

where for some positive constants C1 = Cl(s) and C2 = C2(s), C1 ~ l + s / 2

< ~P"

<

(3)

C2Nl+s/2

Thus, the dominant term in the energy is provided by A~/2 times the energy Z(s) for the uniform distribution. The case of minimal logarithmic energy (which in a limiting sense corresponds to s = 0) can be likewise treated, yielding

'(4)

%(0, N) = ~- log

'

N 2 - ~ N log N - RN, O, N - 2 ,

(4)

with C l N <- RN, o <- GN. The challenging next step is to determine whether the limit

RN•8

lim - -

N----~= N 1+s/2

actually exists (for each fLxed s --> 0). For the case s = 1 of Fekete points, we conjecture that it does exist and equals

%(s, N) := min{E(s, wN) : O)g C 82}, S ~ 0. For 0 < s < 2, the energy integral

I(s)

-

ix

(4qr)2 S xS

_

y[S dG(x) dtr(y)

(1)

(89

(V -n + 1 0.55305 . . . , VOLUME 19, NUMBER 1, 1997

7

In this direction, we quote the following result of Rakhmanov-Saff-Zhou [20,26]: For every N--> 2, there are subsets D1,..., ON o f S 2 such that

N ~J Dj = S 2, Dj A Dk has empty interior i f j r k, (6) j=l o-(Dj) = 4~r/g, diam (Dj) -< 7A/N, j = 1 , . . . , N. The essential feature here is the sufficiency of the constant 7 appearing in the diameter estimate. Although it is not sharp (in fact, the value 6 suffices for N -> 3100), it cannot be replaced by a constant less than 4. (The best asymptotic constant is not known.) Figure 3 illustrates this partitioning for N = 400. To show the usefulness of such a partition, we prove the lower bound of Inequality (3); that is, Rg, s >- CIN 1+s/2 for 0 < s < 2. This argument is much simpler than the original one by Wagner and yields a numerical value for the constant C1. Using the sets in Eqs. (6), we put do-* := (N/4~)do- and do-* : = do'*]Di. Then choosing the points x b . . . , XN randomly and independently from D 1 , . . . , DN, respectively, we get for the expected value of the energy

Figure 2. Dual structure for 122 electrons in equilibrium.

which involves the value of the Riemann zeta function at 1/2. This conjectured limit is again derived from considerations of the hexagonal-pentagonal tiling of the sphere (see [17]). Computational results up to 200 points give a value close to 0.5523 [12,20]. For s -> 2, the energy integral (1) is infinite and the representation (2) no longer meaningful because the remainder becomes dominant. This transition in asymptotic behavior is likely due to the fact that for s - 2, the influence on the energy of "nearby points" starts to grow substantiaily. In fact, for s = 2, the authors [17] have shown (using spherical harmonics) that %(2, N) lim N2 log N N---~

fff

Z

1 1

=--2

fnj

ff

--~"=i fD, I(s) N2 -< ~ -

Ixi

-

1

do-~(Xl) do-~(x2)"" do-~v(XN)

s

x_ 1 s do~i(x) do-~(y)

1

do'*(x) do-*(y) 1

lx-Yl s _ ~N, i=1

do~i(x ) do-*(y)

1

I(S) N2

[diam(Di)]~ -< -~

~1 Nl+S/2" -

1 8'

and for s > 2,

C1Nl+s/2 <--~(S, N) <- C ~ 1+s/2, where C1 and C2 are positive constants (depending on s). Moreover, a hexagonal tiling projection technique yields the upper estimate 1 (~/3/s/2 limN____)~supN -1-s/2 ~(s, N) <- ~ \ - ~ / ~L(S),

S>

2,

(5)

where ~L(S) is the zeta function of the quadratic number field Q(~/-Z-~). Also, we have conjectured that inequality (5) holds with equality for the ordinary limit.

Equal-Area Partitioning For various purposes it is useful to have a partitioning of the sphere into N equal-area parts with small diameters. It is not difficult to see that the optimal diameter lengths should have order N-1/2. 8

THE MATHEMATICALINTELLIGENCER

Figure 3. Partition of the sphere into 400 equal-area parts with diameters <- 7 / ~ - ~

Since the expected value is b o u n d e d by [I(s)/2]N 2 (1/7S)N 1+s/2, there is also a configuration that meets this bound. Consequently, Inequality (3) holds with C1 = 1/7 s. Without the equal-area requirement, partitioning the sphere into N parts of small diameters is a problem related to best packing; that is, to the optimal separation of points on the sphere. In fact, the previously mentioned result of Habicht and van der Waerden resulting from hexagonal tiling projections leads to an asymptotic order of

4

2 ~

~ 4.398

for an attainable size of the diameters. Certainly, we expect that optimal s-energy configurations possess a "well-separation" property; that is, the distance between any pair of points of the configuration should be b o u n d e d below by C / ~ . At this writing, such results have been established for s = 0 [21], s = 1 [8], and s > 2 [17]. Separation properties also play an important role in the analysis of quadrature formulas, as we now explain.

Spherical Designs Of practical importance is the use of uniformly distributed points on the sphere for numerical integration purposes. For example, in the analysis of satellite data from the earth's surface, one frequently wants to approximate integrals over a sphere by arithmetic averages at some wellchosen points. The mathematical problem is to choose configurations (ON = {Xl,N,. 9 XN,N} (typically N is very big) such that the difference 1N 1 fs 2 f ( x ) da(x) - -~ ~ f(Xj, N) j=l

is small (maybe even zero) for a large class of functions. Various classes of functions have been considered in the literature. As an example we mention the class of indicator functions of spherical caps which leads to the notion of spherical cap discrepancy. All considered classes give rise to a sequence of configurations (ON that are asymptotically u n i f o r m l y distributed in the sense that for every spherical cap A with area

o A) lim N-'~c~

#{I < _ j < _ N : x j ~ v E A } N

1 (A) 4~ " ~

---

which means that for large N, each spherical cap gets its fair share of points. This is equivalent to the property that

lim - 1- ~N f(xj~v) =

1 JSC2f ( x )

da(x)

N "-->:~ N j = 1

for every continuous f u n c t i o n f on S 2. When dealing with smooth functions, it is natural to consider the class of polynomials up to a certain degree. This leads to the notion of spherical designs, which was introduced in 1977 by P. Delsarte, J. M. Goethals, and J. J. Seidel [9], and is so named because of certain analogies with com-

binatorial designs. By definition, a configuration WN = {Xb 9 9 9 XN} is a spherical t-design if

l fs2 f ( x )

4qr

d(r(x) = ~1 NZ f ( x j )

(7)

j=l

for all polynomials f in three variables of degree -< t. Spherical t-designs with small N and large t p r o v i d e excellent integration formulas for smooth functions. However, there seem to be no explicit constructions available that work for large t. Extensive computer searches by Hardin and Sloane [14] have led to the discovery of spherical t-designs for t up to 13 with conjectured minimal number of points. For example, they found a spherical 13-design with 94 points. We use N(t) to denote the minimum number of points for which a spherical t-design exists. From our asymptotic point of view, we want to study the behavior of N(t) as t --~ o~. It is not so hard to show that N(t) >- Ct 2. This may be viewed as a natural bound, since S 2 is a two-dimensional algebraic variety. The space of polynomials of degree -< t restricted to the sphere has dimension (t + 1) 2. So the requirements for a spherical design constitute (t + 1) 2 equations, and from this, one can show that one needs at least Ct 2 points. A rather difficult problem seems to be the following. P r o v e ( o r d i s p r o v e ) : N(t) = O(t 2) for t ~ oo. Hardin and Sloane [14] even conjecture that N(t)<89 2 (1 + o(1)). The best result so far is due to J. Korevaar and J. L. H. Meyers [16]. They proved N(t) = O(t3). An interesting relation with extremal energies was pointed out by Korevaar [15]. Introducing the modified Coulomb energy E(1, r; (ON):=

1 Z ' rxkl' l<_j
where r is a parameter, 0 < r < 1, he considers the minimizing configurations (O~). It follows from Korevaar's results that if the minimizing configurations are well separated [i.e., if there is a constant C > 0 such that [x~r) _ x(kr)l >_ C

l<_j
for a l l N a n d all r E (0, 1)], then N(t) = O(t 2) as t --) oo. This approach clearly merits further study.

Spiral Points A variety of algorithms has been p r o p o s e d for the explicit construction of uniformly distributed points on the sphere. Some begin with uniformly distributed points over a rectangular area which are then transformed via cylindrical projection onto the sphere. Others employ sequences of rotations of the sphere which, under stereographic projection, correspond to M6bius transformations in the plane (cf. [t8]). A popular and simple technique is that o f icosahedral dissection, which proceeds as follows: For each triangular face of the icosahedron, the midpoints of the sides are joined to form four new triangles. The centers of the new VOLUME 19, NUMBER 1, 1997

9

Motivated by h e x a g o n a l tilings and n u m e r i c a l experimentation, Rakhmanov, Saff, a n d Zhou [20] have r e c e n t l y i n t r o d u c e d the following simple construction, w h i c h app e a r s for large N to have a c o n s i d e r a b l e advantage o v e r the a b o v e - m e n t i o n e d algorithms. Using s p h e r i c a l coordin a t e s (0, ~b), 0 -< 0 -< ~-, 0 <- r -- 2~r, we set

Ok=arccos(hk), 3.6

Ck=(,#k_l + ~

hk=--l-{ 1

~ )

2 ( k - 1) (N-l)'

2<-k<-N -1,r162

=

(8)

=0.

(81r~t/2

1

~3.809

1 .

that is, (r

1-
(mod2~-),

close to

-- ~bk-1) ~V/1 -- h 2 ~ 3.809

The choice o f the s m a l l e r c o n s t a n t 3.6 in Eqs. (8) is b a s e d on n u m e r i c a l e x p e r i m e n t a t i o n and can be v i e w e d as an acc o m m o d a t i o n to the fact that d i s t a n c e s shrink w h e n a hexagonal lattice is orthogonally p r o j e c t e d from a tangent plane to the sphere. [More generally, in Eqs. (8) one can introduce a p a r a m e t e r C in p l a c e of 3.6 a n d a d j u s t its value a p p r o p r i a t e l y for the application at hand.] At least for N up to 12,000, the generalized spiral points aN have energies in r e a s o n a b l e a g r e e m e n t with representations (2) a n d (4). F o r example, on c o m p a r i n g c o m p u t e d values for the energy of spiral p o i n t s with the theoretical estimates for the minimal energy w h e n s = 0, it can be p r o v e d that E(0, ~)N) -- ~(0, N) ~ 114 log N,

2 -< N --- 12,000,

and it is likely that the aN actually p e r f o r m m u c h b e t t e r than this e s t i m a t e indicates. An a s y m p t o t i c analysis of these generalized spiral points awaits further investigation.

ACKNOWLEDGMENTS

Figure 5. Construction of g e n e r a l i z e d spiral points for N = 6.

10

THE MATHEMATICAL INTELLIGENCER

The research ofE. B. Saff was supported, in part, by the U.S. National Science Foundation under Grant DMS-9501130. A. B. J. Kuijlaars is supported by a fellowship of the Belgian National Fund for Scientific

4. B. Bergersen, D. Boal, and P. Palffy-Muhoray, Equilibrium configurations of particles on a sphere: the case of logarithmic interactions, J. Phys. A: Math. Gen. 27 (1994), 2579-2586. 5. F. R. K. Chung, B. Kostant, and S. Sternberg, Groups and the buckyball, in Lie Theory and Geometry (J.-L. Brylinski, R. Brylinski, V. Guillemin and V. Kac, eds.), Progress in Mathematics No. 123, Boston: Birkh&user (1994), pp. 97-126.6. J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, 2nd ed., New York: Springer-Verlag (1993). 7. J. Cui and W. Freeden, Equidistribution on the sphere, SlAM J. Sci. Comp. (to appear). 8. B. E. J. Dahlberg, On the distribution of Fekete points, Duke Math. J. 45 (1978), 537-542. 9. P. Delsarte, J. M. Goethals, and J.J. Seidel, Spherical codes and designs, Geom. Dedicata 6 (1977), 363-388. 10. T. Erber and G. M. Hockney, Equilibrium configurations of N equal charges on a sphere, J. Phys. A: Math. Gen. 24 (1991), L1369-L1377. 11. T. Erber and G. M. Hockney, Comment on "Method of constrained global optimization," Phys. Rev. Lett. 74 (1995), 1482. 12. L. Glasser and A. G. Every, Energies and spacings of point charges on a sphere, J. Phys. A: Math. Gen. 25 (1992), 2473-2482. 13. W. Habicht and B. L. van der Waerden, Lagerung von Punkten auf der Kugel, Math. Ann. 123 (1951), 223-234. 14. R. H. Hardin and N. J. A. Sloane, McLaren's improved snub cube and other new spherical designs in three dimensions, Discr. Comp. Geom. 15 (1996), 429-442. 15. J. Korevaar, Chebyshev-type quadratures: use of complex analysis and potential theory, in: Complex Potential Theory (P. M. Gauthier and G. Sabidussi, eds.), Dordrecht: Kluwer (1994), 325-364. 16. J. Korevaar and J. L. H. Meyers, Spherical Faraday cage for the case of equal point charges and Chebyshev-type quadrature on the sphere, Integral Transforms and Special Functions 1 (1993), 105-117. 17. A. B. J. Kuijlaars, and E. B. Saff, Asymptotics for minimal discrete energy on the sphere, Trans. Am. Math. Soc. (to appear). 18. A. Lubotzky, R. Phillips, and P. Sarnak, Hecke operators and distributing points on the sphere I, Comm. Pure AppL Math. 39 (1986),

Research. The a u t h o r s are especially grateful to Y a n m u Zhou for preparing t h e illustrations. REFERENCES

1. R. Alexander, On the sum of distances between N points on a sphere, Acta Math. Acad. ScL Hungar. 23 (1972), 443-448. 2. E. L. AItschuler, T. J. Williams, E. R. Ratner, F. Dowla, and F. Wooten, Method of constrained global optimization, Phys. Rev. Lett. 72 (1994), 2671-2674. 3. J. Beck, Sums of distances between points on a sphere--an application of the theory of irregularities of distribution to discrete geometry, Mathematika 31 (1984), 33-41.

149-186. 19. T. W. Melnyk, O. Knop, and W. R. Smith, Extremal arrangements of points and unit charges on a sphere: equilibrium configurations revisited. Can. J. Chem. 55 (1977), 1745-1761. 20. E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou, Minimal discrete energy on the sphere, Math. Res. Lett. 1 (1994), 647-662. 21. E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou, Electrons on the sphere, in Computational Methods and Function Theory (R. M. All, St. Ruscheweyh, and E. B. Saff, eds.), Singapore: World Scientific (1995), pp. 111-127. 22. M. Shub and S. Smale, Complexity of Bezout's theorem II1: condition number and packing, J. Complexity 9 (1993), 4-14. 23. K. B. Stolarsky, Sums of distances between points on a sphere. II. Proc. Am. Math. Soc. 41 (1973), 575-582. 24. G. Wagner, On the means of distances on the surface of a sphere (lower bounds), Pacific J. Math. 144 (1990), 389-398. 25. G. Wagner, On the means of distances on the surface of a sphere II (upper bounds), Pacific J. Math. 153 (1992), 381-396. 26. Y. M. Zhou, Arrangements of points on the sphere, Thesis, University of South Florida, 1995. VOLUME 19, NUMBER 1, 1997

11

i~'Jl~ili[:-]nr.li[,-~-ai

= l , l ( : - ] i i (- - ~ . l l i i~- : t

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

i,,[:-],li~ll

Alexander

Shen,

Editor

I

t is always nice to see a simple solution for a difficult problem. Simple but h a r d to f i n d - - o t h e r w i s e the p r o b lem w o u l d n ' t be that difficult. The solution m a y require an u n e x p e c t e d construction, o r use s o m e seemingly u n r e l a t e d theory. In the latter c a s e w e often feel uncomfortable: Is this t h e o r y really relevant? Or is there s o m e o t h e r simple solution which does not use it at all? Here a r e s o m e e x a m p l e s of such "mysterious solutions."

I

S e m i - I n t e g e r Rectangles This p r o b l e m is well k n o w n a m o n g p e o p l e rtmning the Moscow Olympiad. We call a rectangle semi-integer (for lack of a b e t t e r n a m e ) if one of its sides has integer length.

If the upper-left r e c t a n g l e also has integer vertical side, w e are done: the vertical side of the initial rectangle is a s u m of two integers a n d therefore is an integer. Otherwise, w e get the following picture:

PROBLEM. A rectangle is cut into several semi-integer rectangles ( w h o s e sides are parallel to the sides of the initial rectangle). Prove that the initial rectangle is also a semi-integer one. Here is one example.

The s a m e reasoning s h o w s that the only nontrivial c a s e is the following one:

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

12

If all five small rectangles in the picture are semi-integer, then the big one is semi-integer too. Let us c h e c k that. Consider the lower-left rectangle. A s s u m e that its vertical side is an integer. (On the picture, w e indicate a semi-integer rectangle b y covering it with lines p a r a l l e l to the integer side.)

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER-VERLAG NEW YORK

ll l l

N o w w e recall that the interior rectangle is a semi-integer one; assume, for example, that its horizontal side is an integer:

fD r

9 a c i" jl -1 Then the horizontal side of the big rectangle h a s length a + b - c, w h i c h is an integer. Now I give a (rather unexpected) proof for the general case. The proof uses periodic functions f : R ~ R with period 1 and mean value 0 (so f a + i f ( x ) d x = 0 for a n y a). Let us call t h e m test functions. I f f i s a test function and T C R is an interval of integer length, t h e n f T f ( X ) d x = 0. This p r o p e r t y is characteristic for intervals o f integer length: if U is an interval w h o s e length is n o t an integer, it is e a s y to c o n s t r u c t a t e s t f u n c t i o n f s u c h that f u f ( x ) dx 0. F o r example, if U = [a,a + h] w h e r e h ~ 7/, t a k e f ( x ) = sin 2 v ( x - a); t h e n

f(x)dx =

sin 2 ~ dt =

1 2~r (1 - cos 2rrh) > 0

N o w w e a p p r o a c h the m a i n p o i n t of the proof. C o n s i d e r two t e s t functions f a n d g, a n d c o m b i n e t h e m into a function o f t w o variables:

r

= f(x).g(y)

Such a function will also b e called a test function (of two variables, so no confusion arises). LEMMA 1 For any semi-integer rectangle D C R 2 (with sides parallel to OX and OY) and f o r any test f u n c t i o n 4) of two variables,

fD r

dx dy

=

O.

LEMMA 3 The rectangle is a semiinteger one i f and only i f it covers equal amounts of black and white f o r any placement of the rectangle on the board. (We assume that in any such placement the rectangle sides are parallel to the board lines.)

Indeed, i f D = S x T w h e r e S,T C are intervals, t h e n

fs

•

dx dy =

f ( x ) g ( y ) dx dy =

One of the factors in the right-hand side is 0 b e c a u s e one of the intervals S and T has integer length. (End of proof.) Now, if some rectangle H can be cut into semi-integer rectangles, the statement of the l e m m a remains valid: for any test function 4) of two variables we have

fH q~(x,y) d x dy = O. Indeed, the integral is the sum of integrals over small rectangles. Therefore, it r e m a i n s to p r o v e the following

A rectangle H is given. I f f o r any test f u n c t i o n r of two variables we have fH r dx dy = O, then H is a semi-integer rectangle. LEMMA

2

Indeed, if D = S x T and c~(x,y) =

f(x).g(y), then

fD q~(x,y) dx dy

If n e i t h e r of the intervals S and T has integer length, one c a n find test functions f a n d g s u c h t h a t b o t h factors in the right-hand side are non-zero. (See the discussion above.) Remark. We can m a k e an elementary p r o o f out o f this one in the following way. Using "meanders" as t e s t functions f a n d g, w e get a b l a c k and white b o a r d m a d e o f 1/2 • 1/2 squares: I

There is a n o t h e r e l e m e n t a r y p r o o f similar in spirit. I n s t e a d of a b l a c k and white b o a r d lemma, c o n s i d e r a series of b l a c k straight lines with slope 1 going through all integer points:

/// /// /// LEMMA 4 The semi-integer rectangle covers the same amount of black lines independent of the placement; this property is characteristic f o r semiinteger rectangles.

However, all t h e s e p r o o f s m a k e us (at least me) uncomfortable: the result is o b t a i n e d by a simple t r i c k which d o e s not s e e m to b e r e l e v a n t to the "essence of the problem." Question: Can one find a natural, "comfortable" solution for this problem? Another question: Can w e replace 7/ b y an arbitrary subgroup G o f the additive group R and consider "semi-G-rectangles" (one of the sides has length in G) instead of semi-integer rectangles? Reformulation: a s s u m e that a rectangle is cut into s m a l l e r rectangles; w e select one of the sides for each of small rectangles. Prove that at least one of the sides of the big rectangle is an integer linear c o m b i n a t i o n of the sides selected.

1

E E F

Cube and Tetrahedron While the p r o b l e m in the p r e c e d i n g s e c t i o n is a pastime, the n e x t e x a m p l e is f a m o u s theorem:

I I I I I F I

I

I

I

I

I

THEOREM 1 A cube cannot be decomposed into polyhedral parts which can f o r m a regular tetrahedron of the same volume. VOLUME 19, NUMBER 1, 1997

13

(This statement is in contrast with the two-dimensional situation, where for any two polygons of the s a m e area such a polygonal decomposition is possible.) The simple (but r a t h e r strange) p r o o f g o e s as follows. We find a "quasivolume" invariant, i.e., a function v defined on p o l y h e d r a which h a s p r o p e r ties similar to the v o l u m e function: (1) if p o t y h e d r a A a n d B a r e congruent, then v(A) = v(B); (2) v is additive: if a p o l y h e d r o n A is cut into p i e c e s A1 . . . . , An, t h e n

B

A

v(A) = v(A1) + "" + v(An) Ifa cube Cand a tetrahedron Twere cut into congruent pieces, t h e n not only w o u l d their v o l u m e s b e equal, but also v(C) and v(T) w o u l d b e equal for the s a m e reason. Therefore, it is enough to find a function v satisfying (1) and (2) such that v(C) ~ v(T). This function is cons t r u c t e d as follows. Let a p o l y h e d r o n P b e given. C o n s i d e r all edges e l , . . . , ek of the p o l y h e d r o n P. F o r e a c h edge ei cons i d e r the angle ai at ei (i.e., the angle f o r m e d b y the p l a n e s t h a t m e e t at ei). Then w e define v(P) = Z e~(ai), w h e r e f i s s o m e function w h i c h will be specified later. It is evident that v(A) = v(B) for c o n g r u e n t A a n d B (for any function J0. However, to m e e t the req u i r e m e n t (2) w e n e e d a v e r y special function. It should satisfy the following conditions:

(a) f ( a + f~) = f ( a ) + f(~); (b) f(~-) = 0 (Why m u s t such a function exist at all? This question will be d i s c u s s e d later.) Let m e explain w h y v i s additive. F o r example, c o n s i d e r a t e t r a h e d r o n A B C D w h i c h is divided by a p l a n e B C E into t w o t e t r a h e d r a A B C E a n d BCDE. Let us c o m p a r e v(ABCD) and v(ABCE) + v(BCDE). What is the diff e r e n c e b e t w e e n t h e s e two sums? The e d g e AD in the first one is r e p l a c e d by "[4

THE MATHEMATICALINTELLIGENCER

C

D t w o e d g e s A E a n d ED, b u t the angle is the same, so the c o r r e s p o n d i n g t e r m s s u m up quite nicely. The angle a at the edge B C is n o w divided into t w o angles fl a n d y, b u t a = fl + 7 and theref o r e f ( a ) = f(fi) + f(7). Two n e w edges B E and E C appeared. E a c h of t h e m app e a r s twice, b o t h in v(ABCE) and v(BCDE), a n d the sum of the corres p o n d i n g angles is equal to ~r. Recalling that f ( a ) + f ( f l ) is equal to f ( a + [3) and t h e r e f o r e is equal to 0 w h e n a + [3 = ~-, we are done. Of course, the additive p r o p e r t y o f v should be c h e c k e d for the g e n e r a l case, but the i d e a is m o r e o r less clear, so w e s t o p here. Now, h o w to c o n s t r u c t a f u n c t i o n f with the required p r o p e r t i e s (a) and (b) a b o v e ? It is easy to see that t h e s e c o n d i t i o n s implyf(27r) = 0,f(~r/3) = 0 and, in general, f(r~r) = 0 for any rational r. Therefore, the only continuous function with this p r o p e r t y is the zero function, and w e have to l o o k for a d i s c o n t i n u o u s one. In fact, the w o r d "construct" is misleading; w e c a n n o t c o n s t r u c t s u c h a function, w e can only p r o v e its exist e n c e using the a x i o m of choice. C o n s i d e r R as a v e c t o r s p a c e o v e r t h e field Q (having infinite dimension). Using the a x i o m of choice, w e p r o v e that any {)-independent s u b s e t o f can be e x t e n d e d to a {)-basis. Then the values o f f on a basis m a y b e c h o s e n arbitrarily; after that f is e x t e n d e d uniquely o n t o ~ using Q-linearity. It rem a i n s to a p p l y this p r o c e d u r e using {~r} as the Q - i n d e p e n d e n t set and to de-

m a n d t h a t f ( ~ ) = 0; w e still have a lot o f f r e e d o m c h o o s i n g values o f f on the o t h e r basis vectors. Now r e t u r n to o u r cube C and tetrah e d r o n T. All the angles at the cube edges are right angles, so v ( C ) = 0. (Indeed, f(~-/2) + f(~r/2) = f(1r) = 0, as m e n t i o n e d above.) It r e m a i n s to s h o w t h a t f ( a ) # 0 w h e r e a is the angle at Tedges. More precisely, we have to c h e c k that f can be chosen in such a w a y t h a t f ( a ) ~ 0. To do that w e n e e d the ratio a / ~ to be irrational, so the set {a,~} will be Q-independent, which is indeed the case. So goes the proof. Isn't it very strange that a g e o m e t r i c question a b o u t p o l y h e d r a h a s something to do with the a x i o m of choice? There a r e general arguments that s h o w that the a x i o m o f choice can be eliminated from any p r o o f of the theorem. (Indeed, for a n y given n u m b e r of vertices u s e d in the decomposition, the question w h e t h e r this d e c o m p o s i t i o n is p o s s i b l e o r n o t c a n b e f o r m u l a t e d in the e l e m e n t a r y t h e o r y of reals, which is, according to a f a m o u s Tarski result, decidable. Therefore the existence o f a d e c o m p o s i t i o n (for a given n u m b e r o f vertices) c a n b e r e p h r a s e d as an arithmetic statement. And w e k n o w from G6del that any arithmetic statem e n t which can b e p r o v e n with the axiom o f choice can be p r o v e n without it.) The question remains: w h y d o e s such a nice s h o r t p r o o f use such a plainly irrelevant tool as the a x i o m o f choice?

Remembering Olga Taussky H

A

N

D

L

E

R

D

Ci A

V

I

!

lga Taussky is remembered by m a n y f o r her lectures. One w a s A WM's Noether Lecture i n 1981; this had a special resonance, f o r she had k n o w n E m m y Noether both at GSttingen and at B r y n Mawr. Others r e m e m b e r Olga as author of some beautiful research papers, as teacher, as collaborator, and as someone whose zest for mathematics was deeply felt and contagious. Born in 1906 in (the Moravian part of) the AustroHungarian empire, she felt a powerful call to mathematics early in life. Her first research, at the University of Vienna (DPhil 1930 under Philipp Furtwfingler), was on algebraic number theory, and she never stopped regarding that as her primary field. However, she acknowledged as equally important her initiation to functional analysis by Hans Hahn at Vienna, and to algebraic systems by Emmy Noether at G6ttingen. Their perspectives affected her work lifelong. (A recent paper of hers, perhaps her last paper, was a reminiscence of Hahn.) The field she is most identified with--which might be called "linear algebra and applications" though "real and complex matrix theory" would be preferred by some--did not have autonomous existence in the 1930s, despite the textbook by C.C. MacDuffee. Her stature in that field is the very highest, as was palpable in the standing ovation after her survey talk at the second Raleigh conference in 1982.2 In tracing her professional development, I will say a little about how the field came together. Like other Jews in Germany and Austria, Olga Taussky would have had to leave by about 1938 to be safe. Some delayed as long as they could; some, too long. She left in 1934. ~This note is slightly revised from that in the Newsletter of the Association for Women in Mathematics 26 (1996), no. 1, 7-9. Thanks to John Todd and many others who shared their memories of OIga. 2Later published as "How I became a torchbearer for matrix theory," American Mathematical Monthly 9 (1988), 801-812.

She moved, after a year at Bryn Mawr, to Girton College Cambridge, and remained in England until after World War II. It is amusing to hear the story of her job interview, where a member of the committee asked her, with motivation we can imagine, "I see you have written several joint papers. Were you the senior or the junior author?" Another member of the committee was G.H. Hardy, who interjected, "That is a most improper question. Do not answer it!" At another interview she was asked, "I see you have collaborated with some men, but with no women. Why?" Olga replied that that was why she was applying for a position in a women's college!3 It is less amusing to learn that the senior woman mathematician insisted that women students not do their theses with Olga, even when male colleagues considered her the most suited to the projected research, because it would be damaging to their careers to have a woman supervisor. In 1938, while both were working at the University of London, Olga Taussky and John Todd married. Jack's scientific background was rather different--classical analysis--and his personal background was different-Presbyterian northern Irish. But their ensuing collaboration over 57 years was close and extraordinarily fruitful. There were few joint papers, but they talked everything over, and everything either did was influenced by the other. Olga went into applied work for the Ministry of Aircraft Production during the War. The problems included analysis of aircraft designs for their stability properties. The 3The Mathematical Intelligencer 16 (1994), no. 2, 34.

9 1997 SPRJNGER-VERLAGNEW YORK, VOLUME19, NUMBER1, 1997

15

Taussky at Bryn Mawr, 1 9 3 4 . (Photograph courtesy of E. Hlawka.)

Olga

tools were the localization of eigenvalues, stability analysis (testing whether the real parts of all eigenvalues are <0, or anyway not too far above 0), and numerical computation. The Todds' war work coincided with the start of the great expansion of number-crunching technique; Jack did, but Olga did not, keep always adept at the most powerful computational methods. Don't imagine Olga uttering only abstract notions and Jack only results of machine computations. Her curiosity extended to the details of numerical examples; his encompassed the theory. A good example is the Hilbert matrix, a passion they shared. At the end of the war they moved to the US National Bureau of Standards, first in Washington and then in Los Angeles. This was the period when, stimulated by the coming of peace and the computer revolution, the new matrix theory community was being established by people such as the Todds, Alston Householder, Magnus Hestenes, Fritz Bauer, Ky Fan, Alexander Ostrowski, Hehnut Wielandt... My friends tell me never to start such a list, because it would be tedious if I tried to make it complete, and it is unpleasantly invidious to mention a few and omit others just as important. My apologies. I have listed enough to make clear that I am talking about an international development. The group at the National Bureau of Standards included a few of the leaders, and the other leaders were not entirely absent. The opening of (many) borders and easing of (many) security restrictions after the War enabled most of the rest to keep in touch. What now look like fundamental theorems of matrix theory--Gaussian elimination, the Canchy interlacing theorem, the Cayley-Hamilton theorem, Sylvester's inertia 16

THE MATHEMATICALINTELLIGENCER

theorem, the Smith and Jordan forms, Perron-Frobenius theory, the variational principle for eigenvalues, and see below--were known and had not been entirely forgotten. They weren't taught much: there is an "introductory linear algebra course" everywhere now, but then nowhere; as a consequence, when I began graduate study in physics in 1946, four different courses I took began with about six weeks on "vectors." What happened in the following decade was the recognition of matrix theory as a body of doctrine and as a necessary tool-kit for the scientist. Simultaneously it recognized itself as a "field" of research; recognition by others took l o n g e r . . , or should I say will take longer? It had been several years since the Todds had taught. Olga had grown up in a world where women---even Emmy Noether--might be barred from university professorships. It was most welcome when Caltech invited her and Jack to join the faculty in 1957. The offer was (as was usual at the time) for the husband to become Professor and the wife Research Associate; but their offices were adjacent and the same size, and Olga was welcome to conduct seminars and supervise theses. As she did. They never ceased to appreciate Caltech's hospitality. The anomaly in their status ceased to look ideal when, in 1969, a very young Assistant Professor of English was glorified by the press as the first woman ever on Caltech's faculty. The first, indeed! What about Olga? I saw no sign that Olga held this against the young woman herself; but it did rub her the wrong way; she went straight to the administration and had her rank changed. Effective in 1971, she was Professor. By this time she was already an Elder Statesman of matrix theory. Let me attempt to say briefly why her contributions were so important to the field. I'm sorry she is not here to read my remarks, but if she were, I'm afraid she would be impatient with me for trying to single out two particular clusters of papers, when I know she did much more. There is a reason for my choice: the papers I will talk about cast an influence on the research of hundreds of people over the decades since. (1) GERSHGORIN CIRCLES. The basic idea is diagonal dominance. Assume a square matrix A has dominant diagonal in the sense that, for each i, the diagonal entry a{~ exceeds in absolute value Ri, defmed as the sum of the laijl f o r j ~= i. Theorem: A is then non-singular. This can also be phrased as a statement about the spectrum of A: it must be contained in the union of the "Gershgorin circles," whose centers are the aii and whose radii are the Ri. S. Gershgorin didn't invent the idea, but he illustrated its use in numerical estimation of eigenvalues (1931). Olga revived it during the War. She remembered it from student days--but wait: she had not been doing numerical math then, so why did she know this theorem? She had loved it when she heard it as a lemma in algebraic number

4"A recurring theorem on determinants," American Mathematical Monthly 56 (1949), 672-676. 5For more detail, see Hans Schneider, "OIga Taussky-Todd's influence on matrix theory and matrix theorists," Linear & Multilinear AIg. 5 (1977), 197-224. This article is excellent on inertia theorems too,

theory from her director Furtwfingler! Later, her fellow emigr~ Alfred Brauer and she strengthened the theorem and p r o m o t e d the method. Olga's 1949 article 4 was especially widely read. In it, she explained the idea and traced it back to L. Ldxs' (1881), she told s o m e of its applications, transmissions, and independent rediscoveries over the decades, and she initiated a productive program of research into other kinds of diagonal dominance. 5 In its later culmination, this program was led by Olga's friend Richard Varga. (2) INERTIA THEOREMS. A. Lyapunov (1892) had showed the usefulness of what are now called "Lyapunov functions" in stability analysis of linear differential equations. Suppose the vector function x ( t ) satisfies dx/dt = A x , for a given (constant) matrix A. We w o n d e r whether all solutions go to zero as t--~ oo - - o r equivalently, whether all eigenvalues of A have negative real part. It would be enough to fmd a (constant) positive-definite matrix H such that the function L ( x ) = x * H x goes to 0. Differentiating, and substituting d x / d t = A x twice, we rmd L ' ( x ) = x * ' H x + x * H x ' = x * ( A * H + H A ) x . Evidently the wishedfor property of H is that the matrix C = A * H + H A be negative-definite. Bear in mind that C and H are hermitian, so their definiteness is easy to check, whereas A, the key matrix, is usually very non-normal. Olga in the years 1950-1964 called attention to these ideas and the discrete-time analogue, put them in a wider context, and led in the creation of a general inertia theory. Let me quote a theorem which shows where this development goes; it was contributed to first by Olga, then by A. Ostrowski, H. Schneider, D. Carlson, C.T. Chen, H. Wimmer. Assume A has no eigenvaiues with real part 0. Assume A * H + H A = C is positive 6 semi-definite. Then (i) A has at least as many eigenvaiues with negative real part as H does, and at least as many with positive real part; (ii) equality holds if the matrix [C, CA, CA 2, . . .] has full rank in particular, if C is non-singular. In the first few years at Caltech, it was easier to attract students from the physical sciences than from mathematics (but of course the students of the physical sciences at Caitech were very good). As years went by, more thesis students came Olga's way. Her former advisees have had large roles, and some of the starring roles, in the burgeoning of matrix theory since 1960. Olga Taussky always wished to ease the way of younger w o m e n in mathematics, and was sorry not to have more to work with. She said so, and she showed it in her life. Marjorie Senechai recalls giving a paper at an American Mathematical Society meeting for the fn~st time in 1962, and feeling quite alone and far from home. Olga turned the whole experience into a pleasant one by coming up to Marjorie, all smiles, introducing herself, and saying, "It's so nice to have another w o m a n here! Welcome to mathematics!" It's so nice that a leading mathematician was such a lovely h u m a n being.

6It was negative a moment ago, wasn't it? The conventional choice of sign is not the choice that makes sense in the application. Sorry. VOLUME 19, NUMBER1. 1997

17

Renewal of the

Doctorate of Olga Taussky Todd "

D

M

U

N

D

H

L

A

W

K

/~

he University of Vienna has the gracious custom of celebrating a f e w of its more out-

t

standing graduates anew on the fiftieth anniversary of their doctorate. Olga Taussky Todd was so honored, and enjoyed the experience thoroughly. A distinctive perspective on her life is given by the tribute to her pronounced at that ceremony on June 17,

1980 by Professor E d m u n d Hlawka. Many thanks to Glenna F. Burckel for the English translation (here slightly abridged).--Editor's Note Most esteemed Doctor! In its first meeting of the academic year 1979/80 the Faculty of Sciences of the University of Vienna has agreed to renew your doctoral degree on the occasion of your Golden Jubilee. With this honor, which the Faculty bestows very sparingly, it wants to honor your accomplishments in teaching and research. You, Prof. Taussky Todd, have been active in many areas of mathematics. Your greatest love, however, was for number theory and algebra. You have performed outstandingly in many areas of research and acquired a worldwide reputation through your work. Even in your youth you were interested in number theory, and the work which you wrote during your schooldays in Linz, "From the binomial to the polynomial theorem," shows your mathematical gift. Your father, an industrial chemist, died early;, thus you and your two sisters were prematurely obliged to earn money. Nevertheless it was possible for you to study, and indeed you studied mathematics, astronomy, chemistry, and philosophy at the University of Vienna; you also spent a semester at the University of Zurich. You were particularly influenced by the mathematicians Phillipp Furtwfingler, Hans Hahn, and Karl Menger, and the philosopher Moritz Schlick. Among others Hans Hornich, Eugene Lukacs, and Kurt GSdel studied with you. You wrote your dissertation under the supervision of Phillipp FurtwiJngler, who was then working on the prin18

THE MATHEMATICAL INTELLIGENCER9 1997 SPRINGER-VERLAG NEW YORK

cipal ideal theorem of class-field theory, the last of the classfield theorems in Hilbert's program, which was not yet proven. Emil Artin had reduced this last theorem to one about meta-abelian groups. Furtwfingler succeeded in proving this theorem too, and he suggested as a topic your strengthening this result in which you succeeded splendidly. I quote now the evaluation of your dissertation: The undersigned has shown in a not yet published treatise that the so-called principal ideal theorem can be sharpened considerably in certain cases. If the classnumber of the field is 2n, it can be shown that every ideal class of the field becomes an unramified, relatively quadratic field in the principal class. The author investigates the cases in which the ground field has 2 or 3 basis classes of order 1 (l an arbitrary odd prime), and solves them. It is shown that the relationships here are not as simple as in the case l = 2. The work shows that the writer is capable of carrying out her own research in this difficult area; the content of the work is suitable for publication.

The treatise therefore satisfies in every w a y the legal requirements f o r a dissertation. 16.1.1930 Approved: Furtwfingler Wirtinger

The dean at that time was the physicist Gustav Jaeger. Your dissertation was published in Crelle's journal, vo1.168, 1932. Its theme provided material for a public lecture in the Viennese Mathematical Society on 5/30/1930. You also spoke about it in the meeting of the natural science researchers in K6nigsberg on 9/4/1930. Moreover you gave a second lecture at this gathering on the next day entitled "A metric geometry of groups." You spoke again on class field theory at the German mathematicians' meeting in Bad Elster on 9/14/31. And you also worked in class field theory later in your career. Above all I emphasize the big work you published in 1934 with Arnold Scholz, a long and very significant paper. In 1952 you composed a beautiful obituary to the highly gifted Arnold Scholz, who died young. Then in 1931-2 you were Courant's assistant in G6ttingen. This was a consequence of your lecture in Bad Elster. In G6ttingen the honorable task was assigned to you to collaborate with Wilhelm Magnus and H. Ulm in the publication of the collected articles of Hilbert, most particularly the first and second volumes. Hilbert himseff was very pleased with your performance, as he makes clear in the foreword to these volumes. You wrote a fine obituary on Hilbert in 1953. And you lectured about your research on 5/24/32 in G6ttingen, and wrote up the lectures of E. Artin on class field theory. This manuscript circulated for a long time among insiders, and finally it appeared in English translation as Appendix 1 in H. Cohn's book, A Classical

Invitation to Algebraic Number Theory. In 1932 you returned to Vienna and were private assistant to Hans Hahn and Karl Menger until 1934. Next you spent a year, 1934-5, at Bryn Mawr College with Emmy Noether, who together with Emil Artin developed the abstract method in algebra, all wonderfully presented in the book by van der Waerden. After a short stay in Vienna where you published some work on skew-rings with Phillipp Furtwfingler, you went to Girton College in Cambridge as research fellow. In these years (1935-7) you worked mainly in topological algebra. From 1937 on you were at Westfield College of the University of London. You had extensive and varied instructional duties, activities often far removed from your area of research. During that period you met John (Jack) Todd, later your husband, who was similarly occupied at King's College. His field was analysis. Prof. T o d d - to anticipate---was among the fn~st active in the area of numerical mathematics and wrote important articles and books in this field. I mention only the books Introduction

to the Constructive Theory of Functions, Numerical Algebra, and Numerical Analysis. All mathematicians, moreover, owe Prof. Todd great thanks as the savior of the Mathematical Research Institute at Oberwolfach in 1945. The researcher-couple married in 1938. Military service was required of him when war broke out. This service occasioned repeated changes of location. If I'm not mistaken, the couple had to move 18 times. The honoree worked primarily in aerodynamics in the so-called Flutter-group. You, Prof. Olga Todd, were occupied with the theory of partial differential equations, with Erd~lyi, Temple, et al. You also had the opportunity to ap-

Olga Taussky Todd. (Photograph courtesy of Caltech.)

ply the methods of algebra to the theory of partial differential equations. I would like to draw particular attention to your first articles about eigenvalues of matrices and all the articles on matrix theory, which later became your major area of research. In 1947-8 the researcher-couple went to work at the National Bureau of Standards in Washington, then at its branch office in Los Angeles. In between came a stay in Princeton in 1948, where, among other things, they worked with S. Chowla. In 1957 the pair received job offers from the California Institute of Technology in Pasadena, where they have worked ever since. They catalyzed very lively activity there, and a number of important mathematicians emerged from their school. They spurred their students on in their work by charm and firm leadership. They never stinted on praise when one of their students achieved a beautiful result, and they often deferred publishing their own results in order to promote their students. During this time they also published an abundance of articles concerned with the most varied areas of mathematics. Your articles on the theory of matrices are particularly numerous. You have shown how matrix computation can permeate the most varied areas of mathematics. I would like first to draw attention to your 1940 article on the infinite Hilbert matrix (1/(i + 3)), then your articles on the powers of matrices, which are treated from the standpoint of topological algebra; likewise, the articles that you wrote in collaboration with your husband Jack in 1940 should be singled out, and that leads us to the connection of matrix calculation with the theory of algebraic number fields. Here a close connection to cyclotomic fields is made. VOLUME 19, NUMBER 1, 1997

19

Next I would like to mention the long article written with Dade and Zassenhaus in Mathematische Annalen, vol. 148 in 1963 entitled "On the theory of orders." Here you consider semigroups of the ideal classes of matrices, where all matrices have integer entries. In additional articles you consider so-called ideal-matrices, matrices whose entries are whole numbers and which transform an integral basis of an algebraic number field into a basis of an ideal. Your investigation of symmetric integral matrices whose determinants are the discriminants of algebraic number fields is especially interesting; you studied the eigenvalues of these symmetric matrices. Your interest also extended to the commutators of matrices, primarily in connection with the investigations of Jordan, Frobenius, and Bieberbach. We recall theorem 197 in Speiser's book on group theory: it sets out conditions under which a unitary matrix A and its commutator with the unitary matrix B commute with each other. You have also been concerned with when a matrix A is similar to its transpose, A and the similarity transformation both having integer entries. You have investigated when the matrix associated with a normal basis of a normal extension is itself a normal matrix. This question, which you settled completely in the case of an abelian number field, leads in the general case to questions about the group-matrix. It turns out that the group-matrix of a group is normal if and only if the group is abelian or hamiltonian. In addition I would like to single out the long article which you published with Zassenhaus in Aequationes Mathematicae 5 (1970), which treats the first cohomology group of the general linear group over a field. A general investigation of the functional equations of the logarithm is found here too. This article certainly belongs to the basic works in the field. I would like to mention the article which you wrote with your husband and K.Fan, which appeared in the Monatshefte and which treats a discrete counterpart of the Wirtinger inequality. The number of articles about eigenvalues of matrices is particularly large; I would like to draw attention just to the articles on matrices with property L (at first in collaboration with T.S. Motzkin, later independently): A pair of matrices A, B is said to have property L, if the eigenvalues of every linear combination of A and B are linear combinations of the eigenvalues of A and B. The pair is said to have property P if the eigenvalues of every polynomial in A and B are polynomials in the eigenvalues of A and B having the same coefficients. I pick out one theorem on commutators of matrices: Let A and B be two 2 x 2 integer matrices. Then the determinant of their commutator has a negative norm in the number field generated by the eigenvalues of A and in that generated by the eigenvalues of B. You also worked on quaternions and Cayley numbers. I

20

THE MATHEMATICALINTELLIGENCER

would like to focus on your definition of the 2-row determinant of quaternions, which provides an interesting identity. As to your love for sums of squares, you have written about it repeatedly, and your article "Sums of Squares" in the American Mathematical Monthly 77 (1970), 805-30 is famous. For this you received the Lester Ford Prize of the Mathematical Association of America. Finally I single out the 1975 article "From Pythagoras' theorem via sums of squares to celestial mechanics," Math. InteUigencer 10(1988), no. 4, 52-55. Recently you have studied pairs of integers each of which is a sum of 3 squares and whose product has this property too. A close connection with investigations of Witt and Reichardt comes to light. Of your many articles--their total is about 170--only a few could be highlighted. From a great symphony only a few measures could be played. Studying the work again and again, one is astonished by the wealth of ideas. In Austria, you are a member of the Austrian Academy of Science and also a recipient of the Honorary Cross for Science and Art. Among foreign distinctions, I would like to point out that in the United States you were named Woman of the Year in 1963. You received the M.A. degree at Cambridge ex officio, as its first female fellow. A change of statute in Cambridge was required for this. You were also honored by a commemorative volume which professional colleagues dedicated to you. (See [3].) As speaker you are much in demand throughout the world. Thus we are especially delighted that you maintained steady contact with Austria, and that you were ready to accept a position as guest professor in Vienna. We wish you, most honored Madame Olga Taussky Todd, continued great success in science and good health ad multos annos. Translator's note: More details on the life and work of Prof. Taussky Todd can be found on pp. 311-336 of [1], pp. 225-235 of [2], and pp. xxxiv-xlvi of [3], which also contains a bibliography of her work through 1976. REFERENCES 1, Mathematical People: Profiles and Interviews, D.J. Albers and G.L. Alexanderson, editors. Birkh~iuser Boston (1985), Cambridge, Massachusetts. MR 86b:01040. 2, Women of Mathematics, A biobibliographic sourcebook, L.S. Grinstein and P.J. Campbell, editors. Greenwood Press (1987), Westport, Connecticut. MR 89b:01071. 3. Number Theory and Algebra. Collected Papers Dedicated to Henry B. Mann, Arnold E. Ross, and Olga Taussky-Todd. H. Zassenhaus, editor. Academic Press (1977), New York. MR 58 #10227. 4. Emmy Noether, A tribute to her life and work, J.W. Brewer and M.K. Smith, editors. Marcel Dekker (1981), New York. MR 83j:01073. Institute for Technical Mathematics TU Vienna Weidner Hauptstr. 8-10 A-1040 Vienna Austria

Notes from Math 223:

Olga Taussky Todd's

Matrix Theory Course, 1976-1977 I

e

E

L

E

N

E

S

H

A

P

I

R

O

was a graduate student at Caltech f r o m 1976 to 1979, and during the 1976-1977 academic year I took the advanced m a t r i x theory course, Math 223, taught by Olga Taussky Todd. This experience made me want to work in m a t r i x theory w i t h Olga Taussky Todd; it was a privilege to be her student. This article will discuss some of

the m a t e r i a l Olga p r e s e n t e d in this course, and s t e m s f r o m a talk I gave at the Caltech S y m p o s i u m in h o n o r of Olga T a u s s k y T o d d (April 13, 1996). The c o n t e n t s are b a s e d on m y class n o t e s and on the articles in which the t h e o r e m s originally appeared. The c o u r s e a s s u m e d familiarity with basic ideas and m e t h o d s in linear algebra. Olga's lectures were a b o u t specific a r e a s a n d t h e o r e m s in m a t r i x t h e o r y that she w a s int e r e s t e d in and on w h i c h she h a d worked. She certainly m e n t i o n e d various b o o k s w e should look at and k n o w about, b u t m u c h of the material p r e s e n t e d in the c o u r s e w o u l d n o t be found in textbooks. Over and over again, Olga p r e s e n t e d delightful a n d fascinating t h e o r e m s w h i c h linked t o g e t h e r facts which I w o u l d not have guessed were related. The richness and variety of techniques and m e t h o d s also fascinated me, as I began to see h o w linear algebra and matrix t h e o r y w e r e u s e d in so m a n y a r e a s of m a t h e m a t i c s a n d h o w t h e o r e m s and proofs in linear a l g e b r a come from m a n y areas of mathematics. Olga once told us, "To get full insight into m a t r i x t h e o r y is like fmding r o a d s in a jungle." Many of the t h e o r e m s w e s t u d i e d c o n c e r n e d p r o p e r t i e s o f c o m m u t i n g m a t r i c e s and generalizations of c o m m u t a tivity. If w e d i s c o v e r a p r o p e r t y w h i c h a pair, o r set, of commuting m a t r i c e s has, then w e can s t u d y that p r o p e r t y m o r e carefully a n d try to see w h a t c a n be said a b o u t o t h e r sets of m a t r i c e s w h i c h have that property; or, w e can try to generalize that property. Notice that the equation A B = B A m a y be r e w r i t t e n as A B - B A = O. This d r a w s our atten-

tion to the additive (or Lie) c o m m u t a t o r [A, B] = A B - BA. If A and B are invertible, then A B = B A m a y b e rewritten as A B A - 1 B 1 = L This d r a w s o u r a t t e n t i o n to the multiplicative (or group) c o m m u t a t o r ABA 1B- 1. The first theo r e m p r o v e n in the course, due to P u t n a m a n d Wintner [25], involves b o t h t y p e s of c o m m u t a t o r . THEOREM. L e t A a n d B be n o n s i n g u l a r , n x n m a t r i c e s over a f i e l d F; a s s u m e the c h a r a c t e r i s t i c o f F is g r e a t e r t h a n n. A s s u m e t h a t A c o m m u t e s w i t h A B - B A . Then A B -~ A - 1 B - I is nilpotent.

The original article o f P u t n a m and Wintner [25] conc e r n s b o u n d e d o p e r a t o r s in a Hilbert space. Olga p r e s e n t e d the finite-dimensional version of the t h e o r e m , with a p r o o f due to Herstein [14]. Note that the additive c o m m u t a t o r A B - B A has trace zero. A 1937 article b y S h o d a [28] s h o w s that i f M i s a square m a t r i x of trace zero, with e l e m e n t s in a field F of characteristic zero, then t h e r e exist m a t r i c e s A and B over F such that M = A B - B A . Albert and M u c k e n h o u p t [1] later p r o v e d that this result holds for any field. T a u s s k y writes o f h e r fascination with Shoda's t h e o r e m in [32]. The multiplicative c o m m u t a t o r , A B A - ~ B -1, has d e t e r m i n a n t 1; S h o d a s h o w e d t h a t if M is a square m a t r i x o f d e t e r m i n a n t 1, with e l e m e n t s in an algebraically c l o s e d field F, then M m u s t be a multiplicative c o m m u t a t o r . R.C. Thompson, w h o w a s a s t u d e n t of Olga's, deals with this result for general fields in [34]; this w o r k is b a s e d on his Ph.D. dissertation. 9 1997 SPRINGER-VERLAGNEWYORK, VOLUME 19, NUMBER 1, 1997

21

Rather than try to review everything done in that course, I will focus on three areas. T h e s e are the things that I rem e m b e r m o s t vividly from t h e course, and, in reviewing m y notes, I found m y s e l f still intrigued b y them. Simultaneous triangularization of sets of m a t r i c e s 9 Higher-order c o m m u t a t o r s : the K a t o - T a u s s k y - W i e l a n d t c o m m u t a t o r relations 9 Results about multiplicative c o m m u t a t o r s of unitary matrices and cramped matrices 9

nilpotent. Moreover, for any polynomial p, the eigenvalues ofp(A1, A 2 , . 9 At)(AiAj - AjAi) will all be zero, so the mat r i x p(A1, A2, . . . , A t ) ( A i A j - A j A i ) is nilpotent. McCOY'S THEOREM.

T H E O R E M . S u p p o s e A], . . . , A t a r e n x n m a t r i c e s ,

over

the f i e l d F, w h i c h c o m m u t e ; i.e., A i A j = A j A i f o r all i a n d j . A s s u m e F c o n t a i n s the e i g e n v a l u e s o f t h e s e m a t r i c e s . T h e n , t h e r e i s a n o n s i n g u l a r m a t r i x S, w i t h d e m e n t s i n F, s u c h t h a t all o f the m a t r i c e s S - ; A i S a r e u p p e r t r i a n gular.

This classic result is p r o v e n b y induction on n; the key step is to s h o w that the c o m m u t a t i v i t y of the m a t r i c e s implies t h a t they have a c o m m o n eigenvector. If the field F is the c o m p l e x numbers, t h e n one can use a unitary similarity for the similarity S. DEFINITION. We say A1, 9 9 9 A t are s i m u l t a n e o u s l y t r i a n g u l a r i z a b l e if there is a n o n s i n g u l a r matrix S such that all o f the m a t r i c e s S - 1 A i S are u p p e r triangular. Thus, commuting m a t r i c e s are simultaneously triangularizable. However, triangular m a t r i c e s n e e d n o t c o m m u t e , so the c o n v e r s e is not true. The challenge then is to exa m i n e this p r o p e r t y o f s i m u l t a n e o u s t r i a n g u l a r i z a b i l i t y a n d s e e exactly w h a t it d o e s tell us a b o u t the set o f matrices. Let's think a b o u t the eigenvalues. Olga once told m e that w h e n e v e r matrices c a m e up in a p r o b l e m it w a s a g o o d i d e a to l o o k at the eigenvalues, for they w o u l d reveal something important. A s s u m e the m a t r i c e s A1, 9 9 9 A t are all in triangular form; then the diagonal entries are the eigenvalues. Let aij d e n o t e the i t h eigenvalue o f the m a t r i x Aj. When t w o triangular m a t r i c e s are added, w e a d d the diagonal entries; w h e n t h e y are multiplied, c o r r e s p o n d i n g diagonal entires are multiplied. Let p(X1, X2, 9 9 9 X t ) d e n o t e a p o l y n o m i a l in the n o n c o m m u t i n g variables )(i, X2 . . . . . Xt. Then, the i t h diagonal e n t r y ofp(A1, A 2 , 9 9 9 , A t ) is p ( c ~ i l , Oli2, . . . , C~it) . Hence, if A1, . . . , At c a n be s i m u l t a n e o u s l y triangularized, then t h e r e is an ordering of the eigenvalues o f the A j ' s such that for a n y p o l y n o m i a l p, the eigenvalues ofp(A1, A2, 9 9 9 At) will be P ( a i l , c~i2, 9 9 9 ait). This is called

A1,

. . . ,

1. A1, 9 9 9 A t a r e s i m u l t a n e o u s l y

A t be n x n m a t r i c e s o v e r

triangularizable.

h a v e p r o p e r t y P. 3. F o r e a c h p a i r i a n d j , a n d e a c h p o l y n o m i a l p, the m a trix p(A1, A2, . 9 9 , At)(AiAj - AjAi) is nilpotent. 2. A 1 , . 9

Simultaneous Triangularization of Sets of Matrices This topic begins with a b a s i c result going b a c k to F r o b e n i u s [8].

Let

a f i e l d F w h i c h c o n t a i n s the e i g e n v a l u e s o f all o f the m a trices. T h e n the f o l l o w i n g a r e e q u i v a l e n t :

At

We have a l r e a d y s e e n that (1) implies (2), and (2) implies (3); the real h e a r t of the result is that (3) implies (1). The p r o o f in m y class n o t e s is an a r g u m e n t showing that if (3) holds, then the m a t r i c e s A1, 9 9 9 A t have a c o m m o n eigenvector; one then p r o c e e d s by induction. This argument u s e s matrix techniques and is b a s e d on the p r o o f given b y Drazin, Dungey, a n d Gruenberg in [4]. However, Olga also pointed out that McCoy's theorem can be derived using the Wedderburn t h e o r e m on semisimple rings with m i n i m u m condition. Let ~ denote the algebra generated by the matrices A b 9 9 9 At, and let !~ denote the radical of this algebra. Condition (3) of McCoy's theorem says that the c o m m u t a t o r A i A j - A j A i generates a nil ideal and, hence, is in ~ . (The algebra :~ is an Artinian ring, so the "large" and "small" radicals are the same. This tells us that the "small" radical contains all nil ideals and, hence, contains the e l e m e n t A i A j - A j A i [36], Chap. 13.) Hence, the ring ~ / ~ is semisimple and commutative. The Wedderburu theorem says that the semisimple ring ~ / ~ is a direct sum of matrix rings over fields. But ~/!~ is commutative, so these matrix rings are size 1 • 1 and, hence, ~ / ~ can be diagonalized. A n o t h e r a p p r o a c h , showing the c o n n e c t i o n b e t w e e n McCoy's t h e o r e m a n d Lie's theorem, c a n b e found in a 1956 article by Harley F l a n d e r s [5]. T H E O R E M 1. L e t ~ be a n a l g e b r a o f n i l p o t e n t l i n e a r t r a n s f o r m a t i o n s o n a v e c t o r s p a c e V, w i t h dim V > 1. Then there is a non-zero, proper subspace U of V which is invariant under ~.

Proof. If ~ = O, w e can use any s u b s p a c e o f V, so a s s u m e r 0. Then w e can find x in V such that ~ x r 0. As every e l e m e n t of ~ is nilpotent, x c a n n o t satisfy A x = x for any A in ~ . Hence, x is not in ~ x . Let U = z~x. 9 Once w e have this fact, we can use induction to prove that the algebra ~ can b e s i m u l t a n e o u s l y triangularized. McCoy's t h e o r e m then follows from the following result, also in the F l a n d e r s article [5]:

p r o p e r t y P.

Thus, a set of m a t r i c e s which is simultaneously trangularizable has p r o p e r t y P. A t h e o r e m of McCoy [18] gives the converse. McCoy's t h e o r e m also involves a third property, w h i c h is equivalent to p r o p e r t y P. Suppose A b 9 9 9 At is a set o f m a t r i c e s which has p r o p e r t y P. Then all of the eigenvalues of A i A j - A j A i will be zero; hence, A i A j - A j A i is 22

THE MATHEMATICAL INTELLIGENCER

T H E O R E M 2. L e t F be a f i e l d ; let :~ be a n a l g e b r a o f l i n -

ear transformations o f a v e c t o r s p a c e V o v e r F; let dim V > 1. S u p p o s e t h e r e i s a n i l i d e a l ~ o f ~ s u c h t h a t Olga at Caltech. (Photograph by Joanne Chris; used by permission.)

Figure 2.

~/v3~ is commutative. Then there is a non-zero, proper subspace U o f V w h i c h is i n v a r i a n t u n d e r ~ .

Condition (3) of the McCoy t h e o r e m says that for all i a n d j , the c o m m u t a t o r A i A j - AjAi is in the radical, ~ , of the a l g e b r a ~ g e n e r a t e d by A ~ , . . . , A t. Hence, the quotient alg e b r a ~ / ~ is c o m m u t a t i v e and t h e t h e o r e m applies. An ind u c t i o n argument then s h o w s t h a t ~ can b e p u t in u p p e r triangular form. Now, A i A j - AjAi is t h e (additive) c o m m u t a t o r o f Ai and Aj, so w e might e x p e c t this to have s o m e t h i n g to do with Lie algebras. An associative a l g e b r a (such as an algeb r a o f linear t r a n s f o r m a t i o n s o r m a t r i c e s ) can b e conside r e d as a Lie algebra by defming the Lie p r o d u c t s as [x, y] = x y - yx. T h e o r e m s 1 a n d 2 are then corollaries o f w e l l - k n o w n results from the t h e o r y of Lie algebras; T h e o r e m 1 follows from E n g e r s theorem, and T h e o r e m 2 follows from Lie's theorem.

to look at "higher-order" commutators, such as [A, [A, B]].

F o r example, w e have the "Jacobson lemma" [15]. 4ACOBSON LEMMA. Let ~ be a f i n i t e - d i m e n s i o n a l algebra over a f i e l d o f characteristic O. For a, b i n ~ , let a' = [a, b]. I f a' c o m m u t e s w i t h a, then a' is nilpotent.

A 1962 article b y T a u s s k y and Wielandt [33] establishes an explicit linear relation satisfied b y higher-order commutators. Let A a n d B d e n o t e n • n m a t r i c e s over a field F. Consider the i t e r a t e d c o m m u t a t o r s Bi [A, B], B2 = [A, Bi], =

ENGEL'S THEOREM. Let :~ be a L i e algebra o f linear transf o r m a t i o n s on a vector space L, such that each element o f ~ is nilpotent. Then there exists a nonzero vector v i n L such that ~ v = O.

Bi = [A, Bi-1]. LIE'S THEOREM. Let ~ be a solvable Lie algebra o f linear t r a n s f o r m a t i o n s on a vector space L over an algebraically closed f i e l d o f characteristic 0, w i t h dim L = n > 1. Then there is a non-zero, proper subspace M o f L w h i c h is inv a r i a n t u n d e r v~. To o b t a i n T h e o r e m 2 from Lie's theorem, note that if ~ / ~ is commutative, the ideal ~ c o n t a i n s all the c o m m u t a t o r s of e l e m e n t s of ~ , so ~ c o n t a i n s the derived a l g e b r a [~, ~ ] . But !~ is a nil ideal, so it c a n be p u t in strictly upp e r triangular form. This tells us !~ is solvable and, hence, so is ~ . In [12], F e r g u s Gaines a n d R o b e r t C. Thompson, b o t h s t u d e n t s o f Olga's, s t u d i e d the c a s e w h e r e the field F d o e s not c o n t a i n the eigenvalues o f the m a t r i c e s A i , . . . , At, obtaining a version of McCoy's t h e o r e m in which the matrices a r e p u t into b l o c k triangular form, w h e r e the corres p o n d i n g diagonal b l o c k s of the m a t r i c e s will commute.

T. Kato and O. Taussky [17] observed that for 2 x 2 matrices, B3 = (~1 - ~2) 2 B1, where ~i and ~2 are the eigenvalues of A. In [33], Taussky and Wielandt generalized this result. Let C be an m x m m a t r i x with eigenvalues 71, 99 -, 7m, and let D b e a n n • n m a t r i x with eigenvalues t t l , . . . , 3n. Define a linear t r a n s f o r m a t i o n hc~) on the s p a c e of m x n m a t r i c e s by AC,D(X)= C X - X D . The eigenvalues of h c 2 are t h e n the m n n u m b e r s {~/i - ~j I i = 1 , . . . , m, j = 1 , . . . , n}. (One w a y to s h o w this is to write the matrix X as a c o l u m n v e c t o r with m n entries; the m a t r i x for hc, D then turns out to be I ( ~ C - DtQI.) If C = D = A, w e have the m a p AA(X) = A X - XA. The eigenvalues Of AA are {ai - ajl i , j = 1 , . . . , n}, so the characteristic p o l y n o m i a l o f hA is f(Z)

= Zn

H iCj

[Z - - (0~i -- O~j)] = Z n

H

[Z 2 -- (O~i -

OLj)2].

i<j

F r o m the C a y l e y - H a m i l t o n theorem, f ( h A ) = 0. However, McCoy's t h e o r e m tells us t h a t Property P is a r a t h e r strong condition: sets of matrices with p r o p e r t y P can be triangularized. M. Kac suggested the idea o f p r o p e r t y L : w e say A a n d B have p r o p e r t y L if there is an ordering el, 99 9 o~ o f t h e eigenvalues of A, a n d ill, 99 9 fin of the eigenvalues of B s u c h that for any x a n d y, the m a t r i x x A + y B has eigenvalues x a i + y[3i. Motzkin a n d Taussky s t u d i e d the L p r o p e r t y in [23] and [24]. Higher-Order Commutators: The Kato-Taussky-Wielandt C o m m u t a t o r Relation N o w let's return to the equation A B = BA, which w e m a y r e w r i t e as [A, B] = 0. We might try to generalize the equation [A, B] = 0, or d e s c r i b e w a y s in w h i c h [A, B] is "close to" zero. F o r example, w e might think of a matrix as being close to zero if it is nilpotent (all eigenvalues are zero), o r if m a n y of its eigenvalues are zero. It turns out to be fruitful 24

THE MATHEMATICALINTELUGENCER

the minimal p o l y n o m i a l o f hA actually h a s s m a l l e r degree.

The factor z n c o r r e s p o n d s to the eigenvalue 0. The eigens p a c e for 0 is the s p a c e of all n x n m a t r i c e s which commute w i t h A a n d this s p a c e has d i m e n s i o n at least n. Hence, the o p e r a t o r hA satisfies Z H

(Z 2 -- (O~i -- aj)2], a p o l y n o m i a l o f d e g r e e 2N + 1,

~<J

w h e r e N = n ( n - 1)/2.

Now multiply out this polynomial, and let ~k d e n o t e the kth e l e m e n t a r y s y m m e t r i c function o f the (el - aj)2, w h e r e i, j = 1 , . . . , n. Then AA satisfies z 2N+1 - 81 z 2N-i + 52 z 2N-3 . . . .

+ (--1) g ~N z

= O.

Substituting AA for z, a n d applying the resulting operator to B, we obtain B2N+] -- 3 1 B 2 g - i + 52 B2N-3 . . . .

+ (--1) N ~NB 1 ---O.

However, this is not the p r o o f Olga p r e s e n t e d to us in the course. The article b y T a u s s k y and Wielandt actually establishes a m o r e general v e r s i o n of this t h e o r e m for rings, a n d the p r o o f is quite different. THEOREM [33]. L e t R be a r i n g a n d let F be its center. L e t

a, b be i n R; set bl = a b - ba a n d bi = a b i - 1 - bi-~a. S u p p o s e a s a t i s f i e s a n e q u a t i o n f ( a ) = 0, w h e r e f ( x ) = X n - - ~21x n - 1 -[- "~2x n - 2 . . . . "{'- ( - - 1 ) n Tn a n d each ~i is i n F. L e t N = n ( n - 1)/2. Then, b2g+l - ( ~ l b 2 N - t + (~2b2N-3 -"'" + (--1) N ~N bl = 0, w h e r e 8k = r ( ~1, . 9 9 ~/n).

The p o i n t here is to give an explicit formula for the coefficients t~i in t e r m s of the ~i's; this is done b y specifying the function (I)k: it is the unique p o l y n o m i a l with integer coefficients w h i c h e x p r e s s e s the kth e l e m e n t a r y function o f the N functions (xi - xj) 2 in t e r m s of the e l e m e n t a r y s y m m e t r i c functions of the x~'s. The p r o o f of the t h e o r e m boils d o w n to an algebraic identity a b o u t polynomials. F u r t h e r w o r k on such c o m m u t a t o r relations was d o n e b y Olga's s t u d e n t F e r g u s Gaines [9,11]. Gaines s h o w e d that pairs of m a t r i c e s which satisfied s t r o n g e r c o m m u t a t o r relations c o u l d be p u t in b l o c k triangular form.

Results About Multiplicative Commutators of Unitary Matrices and Cramped Matrices Now w e l o o k at s o m e results a b o u t c o m m u t a t o r s of the form A B A - 1 B 1, w h e r e A and B are unitary m a t r i c e s a n d B is cramped. The eigenvalues of a unitary m a t r i x are c o m p l e x numb e r s of m o d u l u s 1; hence, they c o r r e s p o n d to p o i n t s on the unit circle. We say a unitary m a t r i x is c r a m p e d if its eigenvalues lie on an arc w h i c h is less than ~r; i.e., less t h a n a semicircle. THEOREM 3 ( F r o b e n i u s [7]). L e t A a n d B be n • n u n i t a r y m a t r i c e s . L e t C = A B A - 1 B -1. A s s u m e that B i s c r a m p e d a n d that A C = CA. T h e n A B = BA. My n o t e s contain several p r o o f s of this theorem. The first is the p r o o f given by Frobenius. Later in the n o t e s I find a s i m p l e r p r o o f using the n u m e r i c a l range; this p r o o f c o m e s from an article b y Marcus and T h o m p s o n [19], w h i c h generalizes the result to n o r m a l matrices. DEFINITION. Let A be an n X n c o m p l e x matrix. T h e f i e l d

o f values, o r n u m e r i c a l range, o f A is

~ ( A ) = {x* A x ] x is in C n and x * x = 1}. The set ~ ( A ) is a set o f c o m p l e x numbers, r e g a r d e d as a set of p o i n t s in R 2, using the usual c o r r e s p o n d e n c e b e t w e e n a c o m p l e x n u m b e r a + ib and the p o i n t (a, b). P e r h a p s the m o s t b a s i c result a b o u t the field of values is that it is a closed, c o n v e x set in R 2 [13,35]. ff X is an eigenvalue of A, with eigenvector x, where x * x = 1, then x*A x = ~, so ~(A) contains the eigenvalues of A. Hence, it contains the polygon formed by taking the convex hull of the eigenvalues. F o r any unitary matrix U, w e have ~ ( U * A U ) = ~(A), so ~ ( A ) is invariant under unitary similarity. When A is normal, w e can diagonalize A with a uni-

tary similarity and then show that the numerical range is just the convex hull of the eigenvalues. When n -< 4, the converse is true, but for n --- 5, one can construct non-normal matrices whose numerical range is the convex hull of the eigenvalues [22,27]. I f A is a 2 • 2 matrix, then ~(A) is an ellipse; the foci are the eigenvalues, and the m i n o r axis has length r = tr(A*A) - (1~112 + 1~112).fiX ---- ei is the ith unit coordinate vector, then x*Ax = a i i , so ~ ( A ) always contains the diagonal entries of A. Here is the connection between the field of values and cramped matrices. Unitary matrices are normal, so the field of values of a unitary matrix will be the convex hull of its eigenvalues. These eigenvalues lie on the unit circle, so the matrix is cramped if and only if 0 is not in the field of values. "~2

An hl

Now, w e can state a m o r e general v e r s i o n of T h e o r e m 3 given by Marcus and T h o m p s o n [19]. THEOREM. L e t A a n d B be n o n s i n g u l a r n o r m a l m a t r i c e s ; let C = A B A - 1 B -1 a n d s u p p o s e C is n o r m a l . I f 0 is n o t i n ~ ( B ) a n d A C = CA, then C = I (i.e., A B = BA). Proof. Since A and C are b o t h n o r m a l and commute, w e can simultaneously diagonalize t h e m with a unitary similarity. Applying this s a m e similarity to B, our n e w m a t r i c e s U~AU, U*CU, and U*BU still satisfy all the hypotheses. So, w e m a y a s s u m e A and C are diagonal; let ai be the i t h diagonal entry of A and let ci b e the ith diagonal entry of C. F r o m C = ABA -1 B -1, w e have CBA = AB. C o m p u t e the i j entry to see that ci aj bij = ai bij. F o r i = j , w e get ciai bii = a bii. Since ai r O, this gives us ci bii = bii. But 0 is not in ~(B), SO bii r 0, and h e n c e ci = 1 for every i. Thus, C - - / . 9

T h o m p s o n and Marcus further generalized this result as follows [19]. Let B b e a n o r m a l m a t r i x with eigenvalues h i , . . . , ~ . The field of values of B is the c o n v e x hull of t h e s e eigenvalues. F o r any integer k b e t w e e n 1 and n, let Fk(B) be the c o n v e x hull of all s u m s of the form ()til + Ai2 + ..- + )tik)/k. Then FI(B) = ~(B), and one can s h o w that Irk-1 ~ I ~ k 9 THEOREM. L e t A a n d B be n o n s i n g u l a r n o r m a l m a t r i c e s , let C = A B A - 1 B -1, and s u p p o s e C is n o r m a l . I f O is n o t i n Fr+ 1 ( B ) , then 1 is a n e i g e n v a l u e o f C o f m u l t i p l i c i t y at least n - r. In [30], Taussky had investigated the structure of unitary matrices B such that the unitary matrix A c o m m u t e s with C = A B A - 1B - 1. Suppose A has been diagonalized with a uniVOLUME 19, NUMBER 1, 1997

25

t a w similarity; we can then assume A is a direct sum of scalar matrices of the form ajInj, where al, 9 9 o~t are the distinct eigenvalues of A and nj is the multiplicity of aj. Then the s a m e similarity transformation will put B into the form PW, where P is a permutation matrix and W is a direct sum of t diagonal blocks; the j t h block has size nj. Marcus and T h o m p s o n [19] also generalized this result to normal matrices. Now, let's return to the original t h e o r e m of F r o b e n i u s ( T h e o r e m 3). References [6] a n d [7] b y F r o b e n i u s are conc e r n e d with giving an alternative p r o o f of a t h e o r e m of J o r d a n a b o u t finite m a t r i x groups. T h e o r e m 3 m a y b e u s e d to p r o v e t h e following result in group theory. T H E O R E M . Suppose A and B are u n i t a r y matrices and generate a f i n i t e group. A s s u m e A and B are both cramped and that the eigenvalues of A lie on an arc of less than 7/3. Then A B = BA.

Here is a s k e t c h of the proof. Let a l , . . . , an be the eigenvalues of A. B e c a u s e t h e s e lie on an arc of less than 7/3, w e have lai - aj 12 < K < 1. We can also apply a unitary similarity to A and p u t it in diagonal form. Now l o o k at the Schur n o r m of I - C. We get

I1 -

ABA-1B-'II 2

oil 2 = IlI-

= flBA - A II 2 = IlA(I - B) = F. id

-

-

-

(I

-

B)AI] 2

= Z

Is, -

2

- b jl 2 < KIII-

BII 2

zd

N o w c o n s t r u c t the following s e q u e n c e of c o m m u t a t o r s :

C1 = A B A - 1 B -1, C2 = A C1A-1C1 -I,

Ck+l = A Ck A-1Ck -1. We have s h o w n that III - Clll2 < Kill - BII2. We can apply the s a m e a r g u m e n t to A and C1 to get III - C2112
See [3] (Chapt. 5, Sect. 36), w h e r e a s t r o n g e r result by I. Schur [26] is proven. REFERENCES

1. A. A. Albert and B. Muckenhoupt, On matrices of trace zero, Michigan J. Math. 4 (1958), 1-3. 2. L. Bieberbach, 0ber einen Satz des Hrn. C. Jordan in der Theorie der endlichen Gruppen linearer Substitutionen, Sitzungsber. Akad. Wiss. Berlin (1911), 231-240. 3. C. W. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras, John Wiley and Sons, New York, 1962. 4. M. P. Drazin, J. W. Dungey, and K. W. Gruenberg, Some theorems on commutative matrices, J. London Math. Soc. 26 (1951), 221-228. 5. H. Flanders, Methods of proof in linear algebra, Am. Math. Monthly 63 (1956), 1-15. 6. G. Frobenius, 0ber der von L. Bieberbach gefundenen Beweis eines Satzes von C. Jordan, Sitzungsber. Akad. Wiss. Berlin (1911), 241-248. 7. G. Frobenius, @ber unit~re Matrizen, Sitzungsber. Akad. Wiss. Berlin (1911), 373-378. 8. G. Frobenius, 0ber vertauschbare Matrizen, Sitzungsber. Akad. Wiss. Berlin (1896), 601-614. 9. F.J. Gaines, Kato-Taussky-Wielandt commutator relations, Linear AIg. App. 1 (1968), 127-138. 10. F.J. Gaines, Kato-Taussky-Wielandt commutator relations and characteristic curves, Pacific J. Math. 61 (1975), 121-128. 11. F.J. Gaines, Some generalizations of commutativity for linear transformations of a finite dimensional vector space, Ph.D. thesis, California Institute of Technology, Pasadena, 1966. 12. F.J. Gaines and R.C. Thompson, Sets of nearly triangular matrices, Duke Math. J. 35 (1968), 441-453. 13. F. Hausdorff, Der Wertevorrat einer Bilinearform, Math. Z 3 (1919), 314-316. 14. I.N. Herstein, On a theorem of Putnam and Wintner, Prec. Am. Math. Soc. 9 (1958), 363-364. 15. N. Jacobsen, Rational methods in the theory of Lie algebras, Ann. Math. (2) 36 (1935), 875-881. 16. C. Jordan, Memoire sur les equations differentielles lin6aires h integrale alg6brique, Jour for reine and angew. Math. 84 (1878), 89-215. 17. T. Kate and O. Taussky, Commutators of A and A*, J. Washington Acad. ScL 46 (1956), 38-40. 18. N.H. McCoy, On the characteristic roots of matrix polynomials, Bull. Am. Math. Soc. 42 (1936), 592-600. 19. M. Marcus and R.C. Thompson, On a classical commutator result, J. Math. Mech. 16 (1966), 583-588. 20. M. Marcus and W. Watkins, Annihilating polynomials for similarity and commutator mappings, Linear MultilinearAIg. 2 (1974), 81-84. 21. G.A. Miller, H. Blichfeldt, and L.E. Dickson, Theory and Application of Finite Groups, 2nd ed., Stechert, New York, 1938. 22. B.N. Moyls and M.D. Marcus, Field convexity of a square matrix, Prec. Am. Math. Soc. 6 (1955), 981-983. 23. T.S. Motzkin and O. Taussky, Pairs of matrices with property L, Trans. Am. Math. Soc. 73 (1952), 108-114. 24. T.S. Motzkin and O. Taussky, Pairs of matrices with property L, II, Trans. Am. Math. Soc. 80 (1955), 387-401. 25. C.R. Putnam and A. Wintner, On the spectra of group commutators, Prec. Am. Math. Soc. 9 (1958), 360-362.

26. I. Schur, 0ber Gruppen periodischer Substitutionen, Sitzungsber, Preuss. Akad. Wiss., (1911), 619-627. 27. H. Shapiro and O. Taussky, Alternative proofs of a theorem of Mcyls and Marcus on the numerical range of a square matrix, Linear Multilinear Alge. 8 (1980), 337--340. 28. K. Shoda, Einige S&tze Qber Matrizen, Japan. J. Math. 13 (1937), 361-365. 29. O. Taussky, Generalized commutators of matrices and permutations of factors in a product of three matrices, Studies in Mathematics and Mechanics presented to Richard von Mises, Academic Press, New York, 1954, pp. 67-68. 30. O. Taussky, Commutators of unitary matrices which commute with one factor, J. Math. Mech. 10 (1961), 175-178. 31. O. Taussky, A generalization of matrix commutativity, LinearAIge. Applic. 2 (1969), 349-353. 32. O. Taussky, How I became a torchbearer for matrix theory, Am. Math. Monthly 9 (1988), 801-812. 33. O. Taussky and H. Wielandt, Linear relations between higher order commutators, Proc. Am. Math. Soc. 13 (1962), 732-735. 34. R.C. Thompson, Commutators in the special and general linear groups, Trans. Am. Math. Soc. 101 (1961), 16-33. 35. O. Toeplitz, Das algebraische Analogon zu einem Satze von Fejer, Math. Z. 2 (1918), 187-197. 36. B.L. van der Waerden, Algebra, Frederick Ungar, New York, 1970, Vol. 2. 37. H. Zassenhaus, A remark on a paper of O. Taussky, J. Math. Mech. 10 (1961), 179-180.

VOLUME 19, NUMBER 1, 1997

27

I~vAlh-'Ti|*[:-]iil':ii["-]~-Illt'l.]nnlnil~l*li|[:-l-'ll Marjorie

Mathematics in Albania Peter R. Christopher

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

Please send all submissions to the Mathematical Communities Editor, Marjerie Senechal, Department of Mathematics, Smith College, Northampton, MA 01063, USA; e-mail: [email protected] ~)8

Senechal,

Editor

y p a r e n t s w e r e among the large n u m b e r s of Albanians in the early y e a r s of this century who fled the p o v e r t y of their h o m e l a n d and resettled in the West. F o r m a n y years, I w o u l d have liked to arrange a visit to m y ancestral country, but m y efforts c a m e to nothing: A m e r i c a n s and m o s t other W e s t e r n e r s were n o t a l l o w e d to enter that country. Albania's isolation after World War II (though self-imposed) has b e e n comp a r e d to that of Tibet. Finally, in 1990, I was a l l o w e d to participate in a twow e e k tour. In a d d i t i o n to meeting m a n y relatives, I m e t with Albanian mathematicians at the University of Tirana. I found, to m y surprise, that despite their isolation a n d the c o n t i n u e d p o v e r t y o f the country, m a t h e m a t i c s in Albania w a s alive and relatively well. In 1992 an IREX grant to study the state of m a t h e m a t i c s in Albania gave m e the o p p o r t u n i t y to r e t u r n there for nine months, a n d I v o l u n t e e r e d to t e a c h at the University of Tirana. Albania w a s then still in turmoil following a p e r i o d of a n a r c h y b e t w e e n the end o f comm u n i s m a n d the elections of March, 1992. R e s e a r c h conditions w e r e n o t ideal, b u t the Albanian m a t h e m a t i c i a n s t o o k m e u n d e r their wing and p r o v i d e d the n e c e s s a r y guidance. Much of the story that I relate here was told to m e b y P r o f e s s o r A l e k o Minga during long strolls along Tirana's wide boulevards. He held m e captive not only with the p o w e r of his a n e c d o t e s but also with his arm f'Lrmly l o c k e d in mine ( s o m e r e a d e r s will recognize this as a c u s t o m in certain c o u n t r i e s outside of the United States). The story of m a t h e m a t i c s in Albania is a blend of the familiar and the strange. Some o f the p r o b l e m s with w h i c h A l b a n i a n m a t h e m a t i c i a n s have had to deal are the lot of mathematicians everywhere. But other p r o b l e m s w e r e unique, reflecting Albania's unique situation. Albania has always b e e n different: its language and culture, b o t h o f w h i c h derive from the an-

M

THE MATHEMATICAL INTELLIGENCER9 1997 SPRINGER-VERLAG NEW YORK

cient Illyrian, have r e m a i n e d distinct from those of its Balkan neighbors despite centuries of d o m i n a t i o n by invading Greeks, Romans, Slavs, and Turks. Albania first gained its indep e n d e n c e in 1912, b u t w a r s and econ o m i c crises k e p t the country backw a r d and poor. World War II saw o c c u p a t i o n by b o t h the Italians and the Germans, and a civil w a r b e t w e e n nationalists and c o m m u n i s t partisans. The partisans w e r e victorious, and Albania b e c a m e a c o m m u n i s t country after the war. No o t h e r E u r o p e a n c o u n t r y was so i s o l a t e d and so totally d o m i n a t e d by a single p e r s o n a l i t y for s u c h a long p e r i o d o f time. Albania's charismatic dictator, E n v e r H o x h a (the "o" is p r o n o u n c e d as in the English w o r d "more"; the "xh" is like the soft "g" in "gem"), w a s an unwavering adm i r e r of Stalin from his s t u d e n t days in Paris in the 1930's until his own d e a t h in 1985. During t h e H o x h a years, Albania was t r a n s f o r m e d from the m o s t b a c k w a r d c o u n t r y in E u r o p e to the brink of modernity: life e x p e c t a n c y l e a p e d from 35 to 72 years, illiteracy d r o p p e d from 80% to a l m o s t zero, w o m e n were e m a n c i p a t e d (to s o m e extent), even the r e m o t e s t villages w e r e electrified, and the country bec a m e an e x p o r t e r o f h y d r o e l e c t r i c p o w e r and chrome. But it r e m a i n e d poor, and the regime p e r h a p s the cruelest and m o s t r e p r e s s i v e of all its counterparts. Most Albanians believe that on balance, the evil of H o x h a ' s regime outweighed the good. Had he lived to see the end o f the c o m m u n i s t era, he might have e x p e r i e n c e d a Ceaucescu-style exit. The history o f m a t h e m a t i c s in Albania has never b e e n written, and this article is only a beginning. A d e e p e r historical s t u d y w o u l d go at least as far b a c k as Gjon Gazulli (1400-1465) and Leonik T o m e u (14561531), and include Albanian mathematicians, p a s t and present, w h o lived and w o r k e d outside o f Albania. I will focus on m a t h e m a t i c s d o n e in Albania,

beginning with the establishment of its first university, the University of Tirana, in 1957. The Albanian-Soviet Connection

The first faculty of the University of Tirana were taken from the Institute of Sciences (created in 1947) and from the Polytechnic and Pedagogical Institutes. Headed by Professor Petraq Pilika, the University's mathematics department included two older mathematicians who had been educated in France, three young graduates of Albanian institutions, several who had been trained in East Bloc countries, and two Soviet women mathematicians who had settled in Tirana after marrying Albanian students at the University of Moscow. A young visiting mathematician, Leonard Ivanovich Kaminin, completed the group. Under the direction of Kaminin and Pilika, mathematics quickly became a serious subject. During his two-year stay, 19571959, Kaminin set the standard for the future of mathematics in Albania. Since none of the Albanian mathematicians held a doctorate, Kaminin prepared them for research. Seminars were offered four afternoons a week on real analysis, functional analysis, applications of functional analysis (following Sobol'ev), and pedagogical issues. Kaminin, who also conducted a special seminar on mathematical physics, created strong ties between the University of Tirana and the University of Moscow. Russian texts and their translations provided a foundation for the library at the University of Tirana. Because the books sold for pennies, students had the luxury of building their own libraries. Within a year, the Albanian mathematicians had made such progress that a visiting mathematician, A.I. Guseinov from Soviet Azerbaijan, was caught off guard by the depth they demanded, and had to ask for a week off to redesign the lecture notes for his seminar. The Albanian mathematicians realized their strength and became more ambitious. Soon students and faculty began to travel to Moscow for further study and advanced degrees. A 1958 edition of the Albanian quarterly Bulletin of Natural Sciences featured a research paper by Kaminin and

Albanian mathematicians Petraq Pilika, Aristokli Cifligu, Aleko Minga, and Kristian Bukuroshi. Pilika was the first to complete his doctorate at the University of Moscow in 1961. His thesis "Some Fundamental Theorems of Nikolskii Spaces" appeared as several papers in Russian journals. Approximately 25 freshman students were enrolled in the mathematics program each year. The passive voice of the verb "enroll" is appropriate: in almost all cases students were "drafted" into mathematics. The workload was heavy, with a large majority of students failing their first year, and the prospective reward for graduating was a teaching assignment in a remote mountain village. The mathematics department was the most ruthless of the University of Tirana, but the students who survived were active in mathematical research by their third year. However, deans will be deans everywhere: while his superiors were away studying in Moscow, acting department head Aleko Minga, then 24, received a call from the Minister of Education who complained, "We can not support 13 faculty for 5 students. If you keep this up, we'll reduce mathematics to a service department." The mathematics department escaped this fate by winning the support of a higher authority--a pattern that would recur throughout the department's history. Kaminin adapted readily to life in Albania. The mathematicians admired and respected him, and were fascinated by his personal discipline, which required him to listen to music at a fixed hour each evening. When Kaminin first arrived in Tirana, he met with all the mathematicians and one physicist and asked, to everyone's horror, "Which of you is the appointed spy?" Such openness was unheard of; the response was a weak denial that there could possibly be a spy among them. After a long silence, Kaminin pointed an accusatory fmger at the lone physicist and said, "It must be you!" The great burst of laughter broke the ice. Following Kaminin's successful two-year stint in Tirana, the Soviets sent Anatolii Kostyuchenko, a specialist in generalized functions, who gave a seminar on the work of Gelfand.

Kostyuchenko was considered capable and friendly, but he was more aloof than Kaminin had been. Albanian mathematicians suspected that the Soviet embassy had advised him to limit his social involvement. Indeed, Kostyuchenko stayed in Albania for only one year: the first signs of SovietAlbanian disagreement became visible early in 1960. Soon Enver Hoxha split openly with the Soviets, attacking Khrushchev's "revisionist" leanings in a David-Goliath battle of words; by December, 1961, diplomatic relations between the two countries had been severed. All students from Albania, undergraduate and graduate, were expelled from the Soviet Union and other Eastern European countries, in a painful process vividly described by the Albanian writer Ismail Kadare in a semi-autobiographical novel (available in French as Le cr@uscule des dieux de la steppe). Communication between the University of Tirana and other Eastern European universities came to a halt. Scientific and cultural agreements with Albania were canceled, and foreign specialists were withdrawn from Albania. What to do with the one thousand returned students? The teaching load of the faculty of the University of Tirana was increased to an average of 25 hours per week. Mathematics students were accommodated in on-going seminars and research projects, but mathematics education at the University of Tirana was changed forever. Hoxha on M a t h e m a t i c s

To whom could the orphaned Albania now turn? There was considerable underground agitation to fill the vacuum by looking westward, but it was brutally suppressed. China, Albania's most promising suitor, was not particularly attractive to the general Albanian populace because of geographical distance and perceived cultural differences. But China would win Hoxha's hand. Meanwhile, influenced by the persuasiveness of Pilika and others, and also by the writings of Marx and Engels, Enver Hoxha became a strong advocate of mathematics. On August 25, 1962, he convened the intelligentsia of Tirana and delivered a rambling speech in which he extolled the virtues VOLUME 19, NUMBER 1, 1997

29

of m a t h e m a t i c s and declared mathematical training to be national priority. The speech filled fifty pages w h e n it was p u b l i s h e d later in a "little red book." The following excerpt (my translation) conveys its flavor: 9 . . That is why we particularly call upon our studious and wonderful youth to embrace the sciences--sciences in general, but mathematics in particular, not just for the reasons I have mentioned, but also because mathematics, my dear young people, has its own romanticism, its own poetry, always youthful vigor, so tied to the new generation. Since I am speaking with so much passion about science, and especially about mathematics, quite possibly the youth may be laughing, the way I myself have laughed when I was young, because I must confess, comrades, that I did not much care for mathematics, and I believe that the mathematics classes in high school may be responsible for hastening the growth of my beard. But the truth is that mathematics has her own great poetry, she is passionate and not as brutal as I remember. Ask professors of mathematics, ask physicists and chemists, professors and your schoolmates in these fields, they will and must enthuse you. But someone may say, "You yourself, Comrade Enver, have said that you did not enjoy mathematics, whereas now you associate it with poetry." I wish to reply, my young comrades, that . . . the work with which the Party has charged me points out to me each day the important role of mathematics. Today, not only physics, chemistry, astronomy, atomic theory, etc. are strongly linked to mathematics, but it must also be said that a science is perfect only when it is expressible in mathematical terms. Somewhere, I have read that mathematics has gained so much ground that even in biology, the Italian scholar, Vito Volterra, I believe, has found equations for the struggle of life. We have all heard about the marvelous computing machines9 Even the wonderful mind of Euclid could not imagine such a thing, others came after him and created the mathematical "thinking" machine. Therefore, I have the right to say, my dear young comrades, that mathematics is a wonderful science, and if I were able to return to your age, if I had at my school desk the minds and capabilities that you have today, I would go into mathematics. The little red book was treasured by Tirana's mathematicians, who exTHE MATHEMATICAL INTELLIGENCER

Enver Hoxha in 1957 (AP/Wide World Photos).

ploited--perhaps a b u s e d - - i t fully. Before long, the best students from the best schools were drafted into mathematics and received stipends for room and board even if they lived at home. It became easier to retain mathematics professors with "questionable" political backgrounds. Mathematics was propagandized in the schools. Such preferential treatment was not appreciated by the other academic disciplines. The medical school argued that the best students were needed in the field of medicine. Party officials were concerned that, in their zeal to recruit the best students, the mathematics department was too casual about the political histories of the students' families. But the mathematicians could c o u n t e r every argument by quoting from the little red book. This arrogance eventually boomeranged, and mathematicians found themselves on the defensive, forced to justify their work with concrete applications. The group found its salvation in linear programming in 1964, when Vladimir Jorgji and Vasilaq Kedhi produced linear programming solutions to real problems that resulted in measurable economic savings. (Kedhi used graph theory to minimize the cost of transporting coal from mines.) The Cultural Revolution

Beginning in 1965, Albanians were sent to China to complete their doctoral dis-

sertations; among them were Osman Kraja, who w e n t to the Institute of Mathematics at the Chinese Academy of Sciences, and Shaban Baxhaku, who received his degree in differential geometry u n d e r Su Bu Chin at the University of Shanghai; Mina Naqo also w e n t to China to specialize in functional analysis. The Albanians in China received royal treatment, stayed in the best hotels and had a t t e n d a n t s assigned to take care of their needs, but their stay in China was cut short by the Chinese Cultural Revolution. The ripples of the Cultural Revolution were felt in faraway Albania, which adopted revolutionary practices of its own. University faculty were subjected to "forced circulation" in rural and m o u n t a i n o u s regions in the country, and were obliged to toil alongside their students for one m o n t h each year, tilling fields or digging canals. Indeed, Albania outdid China by b a n n i n g religion, to b e c o m e the world's only officially atheist state. At the University, class time had to be set aside for distracting ideological notions and n e w courses such as 'History of the People's Labor Party of Albania.' Extremists argued for further cuts in education, such as reducing the school year to five and one-half m o n t h s (for~ tunately, this never materialized) and reducing the university programs by a year. In 1966 the m a t h e m a t i c s departm e n t had initiated a five-year program culminating in the equivalent of a master's degree. The m a t h e m a t i c s faculty successfully argued its case a n d maintained its full program, b u t other dep a r t m e n t s s u c c u m b e d to the cuts. As a group, the m a t h e m a t i c i a n s were cohesive and trusted one another, and so were able to discuss in private that which could cost them dearly ff overheard in public. This cohesiveness and m u t u a l trust was a survival m e c h a n i s m that served them well t h r o u g h o u t the various phases of A l b a n i a n communism. During this particular phase, strange though it surely was, the repercussions on mathematics were kept relatively light. For example, u n d e r the forced circulation requirement, mathematicians were assigned to n e a r b y high schools or industrial centers, instead of to the mountains. Their success in m a i n t a i n i n g the

cialized preparation for the proposed borders in the Balkans were drawn by five-year mathematics program gave Center of Mathematical Computing. the European powers in the wake of the department the courage to argue The Center was ready by 1971, the collapse of the Ottoman Empire. that the program should be modernequipped with Chinese X-2 computers, Ever since Enver Hoxha and Marshal ized with new courses in probability copies of second-generation Soviet Tito had ungracefully parted company theory and computer science. The sucmachines. Under the jurisdiction of the shortly after World War II, communicess of mathematical applications and University of Tirana, the Center was cation between the two groups o f the need to solve problems with large headed by Kristian Bukuroshi, one of Albanians had been virtually non-exisnumbers of variables led mathematicians to request a sophisticated com- the mathematicians who had been tent. The development of mathematics in Kosova is part of the history of trained in China. puter center in Albania. The idea was Albanian mathemataccepted in princiics, but that is a sepple by the Party leadarate story. Suffice ers, although there it to say here that was concern that there were regular such a center might faculty exchanges bring with it bourbetween the Unigeois and revisionist versity of Tirana and ideas, and enormous the University of amounts of time and Prishtina for over a energy went into decade, resulting in countering such conjoint mathematical ceres. In 1966, a delresearch, design of egation from the curricula, and mathUniversity of Tirana, ematics texts. Perled by Pilika, had haps their greatest gone to China to achievement was the seek a pledge from creation of a unified the Chinese to equip mathematical lanthe proposed center guage, for over the and to provide the years the separated necessary training. twin peoples had inThe Chinese agreed, vented their own but implementation terminology. was delayed by the In the early Cultural Revolution. 1970's Albania also Meanwhile, new famade overtures to culty had to be cultisome western navated to prepare for tions. Cooperation the proposed comwith UNESCO beputing center and for gan, and a number other institutes and of graduate students centers expecting and faculty were almathematical applilowed to study at cations. The fivewestern universiyear (as well as the ties. By a process of four-year) program elimination, France continued to enroll was the country of students; 71 were House at dusk, Theth, Albania, 1994. Photograph by Stan Sherer. choice: the United graduated between States and England were out of the T h e Erratic P e n d u l u m 1970 and 1974. Of these, 32 continued in mathematics, 15 went into high-school In 1970, cooperation began between question; Spain was still ruled by the University of Tirana and the Franco, and Italy was not considered teaching, 9 to the computer center, and University of Prishtina in Yugoslavia, a sufficiently advanced. Also, there was 15 to various other centers. (Guaranteed employment was not one of the com- large university whose faculty and stu- an attachment to the French because dents were mainly Albanians from the they had historically played an impormunist system's worst features.) autonomous province of Kosova. The tant role in Albanian education. Aleko In 1970, as the reins of control beAlbanians of Yugoslavia had been geo- Minga was one of several young gan to loosen, four Albanian mathegraphically separated from their rela- Albanian instructors sent to France; he maticians and two electrical engineers tives in Albania proper when national studied functional analysis at the were sent to China for a year of speVOLUME 19, NUMBER 1, 1997

31

Italy and the Balkans.

University o f Paris. Aleko recalls that he a n d his colleagues s e e m e d to be especially well treated: for example, he w a s given the key to Gustave Choquet's office, which he s h a r e d with him, while s t u d e n t s from o t h e r n a t i o n s w a i t e d e n d l e s s l y for a p p o i n t m e n t s with Choquet. However, A l b a n i a n m a t h e m a t i c i a n s were f o r b i d d e n - - b y their o w n g o v e r n m e n t - - t o travel outside of Paris. Of course, in F r a n c e o r elsewhere, Albanians h a d to m a i n t a i n a strict c o d e o f behavior; t h e y could not, for e x a m p l e , e x t e n d their h a n d to an American, or even to a Soviet. Despite such restrictions, e x p o s u r e to F r e n c h m a t h e m a t i c s b r o u g h t a s t r e a m of fresh ideas for m a t h e m a t i c s in Albania. The c o n t e n t and t e a c h i n g of analysis a n d algebra w a s m o d e r n ized, a n d efforts were m a d e to inform public opinion a b o u t the n e e d for 32

THE MATHEMATICALINTELLIGENCER

m a t h e m a t i c s reform. A qualifying summ e r p r o g r a m for high school t e a c h e r s was i n t r o d u c e d to u p d a t e their knowledge of m a t h e m a t i c s . At the University, m a t h e m a t i c a l r e s e a r c h revived with n e w vigor. Then the p e n d u l u m swung a w a y from the West, a n d a n o t h e r c a m p a i g n began against foreign influences in Albania. P o r t i o n s o f the m a t h e m a t i c s library h a d to b e p u t on reserve, available only by p e r m i s s i o n of the faculty. Especially v u l n e r a b l e w e r e texts representing or describing a c h i e v e m e n t s of Western m a t h e m a t i c i a n s - - w o r s t of all, American. Thus a translation o f George Polya's H o w To Solve It referred to Polya as a Hungarian b u t failed to m e n t i o n that he w a s a prof e s s o r at Stanford. Objectionable p a g e s w e r e s y s t e m a t i c a l l y torn out o f books.

It is not clear w h y H o x h a alternately t i g h t e n e d and l o o s e n e d the reigns of control. Occasionally, i n c r e a s e d pressure s e e m e d to b e a r e s p o n s e to w o r l d events, such as the Cuban Missile Crisis o r the Chinese Cultural Revolution. But at o t h e r times adjusting the pressure s e e m e d to be c o m p l e t e l y arbitrary. I p o s e d this question to Aleko during one of our strolls. He a n s w e r e d with a parable, one that is told in m a n y cultures: A family of eight was feeling the pressure of living cramped in one little room. Why, the father asked, should his family suffer so? He went to the village elder to seek his help. The elder advised the man to get a dog, and the father, against his own judgment, did as advised. He soon found that the dog created more of a problem, so that living

conditions were worse than before. He returned to the ~llage elder, who responded to the new complaints with the advice to bring a cow into the home. The father, respectful of the elder, followed instructions, but quickly found that conditions at home were intolerable, and he returned to the elder in a rage. This time the elder advised the father to get rid of the cow. After doing so the family noticed an immediate improvement, but they were still cramped for space. Now the elder advised them to get rid of the dog. This too resulted in a great improvement, and the family was now content. And so it w a s that Albanians a d a p t e d to the swings in conditions, from b a d to worse, to b a d again. E a c h swing had its o w n set of victims, resisters in t e n s of thousands, w h o suff e r e d the c o n s e q u e n c e s in i n t e r n m e n t c a m p s or in prisons. Mishel F u n d o w a s a m e m b e r o f the first group o f m a t h e m a t i c i a n s s e l e c t e d for a m o r e rigorously a p p l i e d "forced circulation," which n o w required n o t m o n t h s b u t y e a r s of sacrifice. A rising star o f the Albanian m a t h e m a t i c s community, Mishel was the n e p h e w o f Kristaq Fundo, one of the p i o n e e r s o f m a t h e m a t i c s e d u c a t i o n in Albania. But t h e r e was a flaw in his family history: his father h a d b e e n a political p r i s o n e r for eight years. Mishel was "sentenced" to serve six y e a r s as a high-school m a t h e m a t i c s t e a c h e r in a small village n e a r the s o u t h e r n city of Berat. It w a s b y no m e a n s the w o r s t p o s s i b l e assignment, b u t it w a s a serious interr u p t i o n o f his r e s e a r c h career. Even H o x h a h i m s e l f w o u l d n o t e this folly later. Other mathematicians, w h o s e n a m e s w e r e further d o w n the list, w e r e s p a r e d in the n e x t wave of leniency. In 1975, two Chinese m a t h e m a t i cians, specialists in differential equations, arrived in Albania to offer a fourm o n t h s e m i n a r to the small group of specialists in that area. P e r h a p s u n d e r o r d e r s f r o m their government, the Chinese f o c u s e d strictly on business, to the p o i n t of n o t even speaking with m e m b e r s of the department. Other small r e s e a r c h groups c o n t i n u e d to w o r k intensively, n o t a b l y the group in geometry, h e a d e d b y Baxhaku. The functional analysis and topology group was h e a d e d by Skender Gjinushi, w h o

had just returned from France, having defended his dissertation under Choquet at the University of Paris. This group, perhaps the m o s t productive, inchided Bubuqe P e p o (a leading w o m a n mathematician), Mishel Fundo (until his transfer), and Xhezair Teliti. A small fund b e c a m e available for subscriptions to foreign journals, s o m e of which were sent free of charge from the world's master photocopier, China. Other journals were b a r t e r e d in exchange for Albania's own Bulletin of Natural Sciences. The p e r i o d 1975-1980 was filled with mathematical activity: several faculty, including Agim Karcanaj, Petraq Petro, and Vasillaq Kedhi, received doctorates; courses w e r e strengthened and seminars flourished; n e w applications increased public awareness. Applications to economics b r o a d e n e d to include problems such as the optimal rationing of animal feed, the design of experiments to test softs for minerals, and the distribution of hydroelectric energy. Mathematicians were assigned to any of several scientific research centers, such as the small computer center near the oil fields of the city of Fier. Optimizing the cutting of fabric in the clothing industry was said to have resulted in savings of 10-15%. Higher education in Albania had not been confined to Tirana. In the 1960's branches of the University of Tirana, mainly emphasizing engineering or economics, had o p e n e d in the cities of Durres, Korce, Vlore, Shkoder, and

Berat. Some branches had specialized locations such as the tractor manufacturing plant, textile factories, or hydroelectric plants. Parallel with the develo p m e n t of the University of Tirana, several pedagogical institutes expanded from two- to three-, and, by 1982, to fouryear institutes. Some of these have since developed into full-fledged independent universities, each with its own cadre of mathematicians. Agriculmrai institutes and military colleges also had mathematics departments. Bonkers

over Bunkers

In 1978 Hoxha, citing Mao Tse-Tung's increasing revisionistic tendencies, s e v e r e d relations with China. The mom e n t u m of r e c e n t gains w o u l d keep Albania afloat for the n e x t several years, giving the illusion that the little c o u n t r y could m a k e it on its own. Albania h a d cheering squads, those w h o c h a m p i o n underdogs, in all corn e r s of the world, b u t e c o n o m i c and social realities w o u l d eventually prevail. It was in this p e r i o d that the regime, in a seemingly p a r a n o i d effort to p r o t e c t Albania f r o m attack, built an e s t i m a t e d 600,000 c o n c r e t e bunkers, eventually covering the entire land with them, like s o m e n i g h t m a r e of the artist Christo. T h e s e h e m i s p h e r i c a l structures, ten to t w e n t y feet in diameter, can still be s e e n in fields, mountains, even front yards. But H o x h a h a d not c o m p l e t e l y lost his logic. In his collection On Science II, 1976-1984, a

The author with Albanian mathematicians A. Minga (r|, V. Kedhi, and their wives, Elsa and Keti. VOLUME 19, NUMBER 1, 1997

The Golden Age of Albanian Mathematics

Albanian children in a mathematics class in the city of Korce.

compilation of his conversations and notes on Arab civilization and Greek philosophy, Hoxha revealed some revisionism of his own, as he reconsidered the case of Mishel Fundo. The excerpts below, from the section on "Experience Gained To Be Applied to the Needs of our Country," also show Hoxha's continued interest in mathematics: I k n o w that a brilliant m a t h e m a t i c i a n has been sent as a teacher to a small village. This should not h a p p e n / T o send to a s m a l l village a p e r s o n w h o . . , has been sent out o f the c o u n t r y f o r graduate studies, where, moreover, he has m a d e such a p o s i t i v e i m p r e s s i o n that his professors have said, "What is this u n i v e r s i t y o f y o u r s that produces such a capable person?" This should not h a p p e n / T h u s a m a t h e m a t i c i a n so capable is sent o f f to teach school at a t i m e w h e n the oil i n d u s t r y a n d other areas o f the e c o n o m y greatly need such people. Oil requires precise c a l c u l a t i o n s / . . . I n this regard the m a t h e m a t i c s o f George Boole helps considerably. B u t the m a t h e m a t i c s o f Boole is n o t understood by m a n y . This has b e e n . . , studied by Fundo, who is a capable m a t h e m a t i c i a n . Boolean mathem a t i c s does not deal w i t h ten digits, but w i t h two. I f you do not k n o w Boolean m a t h e m a t i c s , then you cannot compute, because there are m i l l i o n s a n d m i l l i o n s o f operations, a n d these are better handled w i t h two digits than w i t h ten. This m a t h e m a t i c s had fallen into oblivion, but the A m e r i c a n s have seized it, a n d i t has only recently been applied. THE MATHEMATICAL INTELLIGENCER

In 1981 Hoxha re-emphasized his two priorities for scientific development, energy and the mathematical sciences. Encompassed in the latter was an ambitious plan to create a national computer network with two central locations, linked to 48 peripheral points in Tirana and later to be extended to the whole country. Equipment and personnel training were to be contributed by UNESCO, while Albania was responsible for the construction of facilities. The winning contract for the computers was, surprisingly, the American firm Honeywell. However, no Americans were directly involved; the company representative was from Argentina, and specialization and training took place in France. The first computer scientists were converts from mathematics--Maksim Raco and Petraq Papajorgji. Computer Science became a separate department with its own five-year program, headed by Kristian Bukuroshi. The Center for Computational Mathematics, an impressive structure, opened in 1984, separate from the University of Tirana. This center was transformed, in 1986, to the Institute of Informatics and Applied Mathematics (INIMA). More than a name change, this involved a complete restructuring, with a new main mission as headquarters of the central computer network. In mathematics, INIMA supported sections in operations research, probability and statistics, and mathematical methods of computation.

The first Albanian national conference on mathematics was organized by the Academy of Sciences and the University of Tirana in 1984. The first conference emphasized achievements to date and prospects for the future, rather than current scientific research. Extensive media coverage accomplished its implicit purpose--heightened public interest in, and continued support for, mathematics. The second conference, organized jointly with the Department of Computer Science and held in 1989, had a much stronger research emphasis. Sixty-eight papers representing 89 authors were presented in two plenary sessions (others had been rejected); 29 of the authors were from the departments of Mathematics and Computer Science at the University of Tirana, 27 were from INIMA, and 33 were from other scientific and educational institutions. Some of the presentations were concerned with applications of mathematics: "Studies in random processes and in queuing theory h a v e . . , led to recommendations on the use of the Port of Durres, with an annual savings of 14 million lek"; "These methods have brought about a better and deeper understanding of the mechanics of many processes, especially in the sector of oil--for example, the motion of seismic waves, the distribution of special stresses..."; "... methods of distributing coal, with 1500 variables and 245 conditions"; "1.7 million dollars can be saved from 1988 to 1989 by a restructuring of (the methods of) exporting chrome." The Conference also had an esoteric side, as the following titles show: "Generalization of two Lemmas of Phelps"; "H-Locally Convex Weak Topologies"; "Results on Quasi-ideals and Their Generalization in Semi-rings." The 1989 Conference represented the fruits of earlier intensive mathematical labor. By this time, there were more faculty with doctorates, several had had the opportunity to go out of the country (for short intervals), and foreign lecturers were invited to Tiran& A reorganization of the mathematics department in 1987 increased the number of Divisions (Chairs) from two to five, namely: Topology and Functional Analysis (P. Pilika), Algebra and Geometry (P.

Petro), Differential Equations (S. Xhemalce), Probability and Statistics (L1. Pt~a), and Applied Mathematics (V. Kedhi). In 1989, Applied Mathematics split into Operations Research (V. Kedhi) and Numerical Analysis (F. Hoxha). There had also been great progress on the pedagogical front. A national committee to modernize school mathematics, grades 1-12, was formed in 1980. Aleko Minga, who headed the committee, credits high school teacher Kujtim Dedej for the positive outcome. Kujtim and others completed a document which included a record of the experiences in mathematics education of other countries (particularly the United States, Russia, and France), critiques of Albania's traditional programs and texts, and a platform for modernization. New texts, worksheets, and teaching materials were carefully designed, together with new teaching methodologies. A massive experiment was implemented, testing the "new math" for two years in each class, and covering all areas of the country, even the remotest mountain villages. The teachers received extensive training (unlike some experiments in other countries) and embraced the program. In 1988, the new program began in earnest in the first grade. Tests prepared by the Ministry of Education measured the performances of 69,096 first grade students; 61.7% of the students were judged excellent, 34.67% good, and 3.62% weak. These numbers indicated that things were on the right track. The program was to be implemented in successive grades each year. But, unexpectedly, there would be no track to ride by the fourth year. After Hoxha's death in 1985, his successor, Ramiz Alia, began to make concessions to an increasingly disenchanted populace. Not only was the well of the economy running dry, but Albanians were becoming increasingly aware of the changes taking place in Eastern Europe, which they followed attentively on Yugoslav and Italian television. Many Westerners first became aware of Albania through television footage showing young people climbing embassy walls and descending upon tankers headed for Italy. But the role of university students in the polit-

The f o r m e r m o n u m e n t to Lenin In Tirana.

ical revolution that followed was largely overlooked. New dormitories were being built to alleviate overcrowding, but the government was on the verge of an economic crisis and most of them were still incomplete in September 1990. After two days without lights in the dorms, students organized a demonstration, chanting, "Drita! Drita!" (Lights! Lights!) through the streets of Tirana, but the chant quickly changed to "Democracia!". This

The f o r m e r Hoxha M u s e u m , now housing USIA offices and an A m e r i c a n library, Tirana. Youths use the pyramidal building as a slide.

was followed by a series of protests and demands: that "Enver Hoxha" be dropped as the formal name of the University of Tirana, that courses be depoliticized, and that requirements for "productive work" and "military service" be abolished. Albania's revolution, although relatively bloodless, left the country in tumult, with institutions, industries, infrastructure totally destroyed. On March 22, 1992, after a period of chaos and a vacuum in law and order, Albanians elected a democratic government to try to create something from the ashes. Like everyone else, Albania's mathematicians were blessed with new-found freedoms, but also new-found problems. How would they survive on a professor's salary of 30 dollars per month? How would they or their children deal with the chaos and corruption? Should they become entrepreneurs, and forsake mathematics? Some found their way out of the country (Mishel Fundo to Greece, Kristian Bukuroshi to Canada, Bubuqe Pepo to France). Others found new directions within the country (Xhezair Teliti became Minister of Education; Skender Gjinushi heads the Social Democratic Party). Education gave way to the pressing need to put bread on the table. Besides, there were no funds, no texts, no windows in school buildings, no chalk, and of course no materials to continue the new mathematics program in elementary schools. But by the beginning of 1993, if one strained a bit, one could see some signs of progress. For one thing Luigj Gjoka had a new pair of eyeglasses! Luigj was head of mathematics at the Polytechnic University, a new independent institution formed from the engineering disciplines of the University of Tirana. For months, he had seen the world through glasses with one lens completely shattered. The Polytechnic was showing promise of becoming a progressive institution under the leadership of its rector, Gezim Karapici. American texts were adopted, so that some classes would be conducted in English. Some mathematics faculty in Tirana were getting back to their research, even with extremely heavy teaching loads. They asked me, for instance, where they should send papers for publication and VOLUME 19, NUMBER 1, 1997

35

how to establish contacts with their counterparts in America. Perhaps most encouraging was the reorganization, in January of 1993, of the Shoqate Shqiptar e Matematikes (Albanian Mathematics Society). I am pleased to have been present for the historic event, and proud to be the organization's first foreign member. As one of its first activities, the group planned a national mathematics Olympiad. The Olympiads have been held regularly since then, despite almost overwhelming obstacles (to buy paper for 1000 tests at a cost of 13 cents apiece was well-nigh prohibitive in 1993). There is much more to learn about mathematics in Albania. What were the new discoveries of Albanian mathematicians and what was mere retracing and reinvention? One would need much careful study of the mathematics articles in the Bulletin to show exactly what mathematics was created and what were its applications. Mathematics educators will be interested to examine the content and methods of the new pre-college mathematics program in Albania which was THE MATHEMATICAL INTELLIGENCER

so promising until it was interrupted. How is mathematics in Albania faring during these extended "transition" years, and what are its prospects for tomorrow? Those of us who root for underdogs look forward to the return of a free mathematical tradition. REFERENCES

Fjalori Enciklopedik Shqiptar (Albanian Encyclopedic Dictionary), Akademia e Shkenceve e RPSSH, Tirana, 1985. Davis, C., "A Mathematical Visit to China", Notices of the American Mathematical Society,

19 (1972), 167-169. Hoxha, E., (Untitled speech to the intelligentsia). N.Sh. Botimeve "Naim Frasheri", Tirana, 1962, 19-23. Hoxha, E., "Per Shkencen, 1976-1984" (On Science, 1976-1984), Shtepia Botuese "8 Nentori", Tirana, 1985. Kadare, I., Le cr~puscule des dieux de la steppe, Fayard, 1981. Maudit, C., "Mission en Albanie," Gazette des Mathematiciens no. 52, Juin, 1992, 64-66. Mina, N, "Nje Intelektual i Squar--doc. Aleko Minga" (An Outstanding Intellectual--Dr. Aleko Minga), in Shkenca dhe Jeta (Science and Life), no. 4 (124), 1990, 20-23.

-Ioarfrost

Patterns ;

.

P

.

B

R

U

T

E

f

he night had been clear and fresh. Pleasant sunshine was illuminating the early morning. Entering the youngest girls' room to wake them up, I opened the blue curtain. On the window-pane was a marvellous artistic arabesque (Figure 1). We were struck with admiration. It took me a few minutes to run d o w n and get the c a m e r a to take some shots. A close-up view is shown in Figure 2. Then I went to the eldest girl's room, whose window faces the same direction, about 8 meters away. A similar pattern appeared, but some of the crystals of hoarfrost had begun to coalesce (see Figure 3). We can not model the growth of such dendritic patterns deterministically: the local variations of temperature and humidity, in space and in time, are crucial to the result and are too f'me to trace in detail. Anyway, what has to be explained is not all the dozens of branches individually, but the overall branching pattern. The situation is similar in other arborescent patterns: the formation of ramifying or converging flows of water across stones, the ramifying of plants, or (closest to our Fig-r. 1.

case) the condensation of tiny drops of water on a window-pane. Some models of formation of regular patterns of icy dendrites can be found in the literature, e.g., [5]. Here our dendrites are curved, perhaps by a temperature gradient sweeping up the pane. A local description would involve partial differential equations of second order with Cauchy's condition, as described geometrically by W. Shi's theory [4]. It is hard to account for the bifurcations we observe in terms of the models in [2]. Perhaps a random distribution of impurities has contributed to the appearance of disturbances, cf. [1]. Unfortunately, the magnificent study [3] of the growth of plants clearly can not be adapted to our problem. To bring our local understanding of the freezing process into a global simulation of the formation of these arborescences is an open challenge. 9 1997 SPRINGER-VERLAG NEWYORK, VOLUME 19, NUMBER 1, 1997

37

Figure 2.

Figure 3.

REFERENCES

1. D. Bideau & A. Hansen (eds.), Disorder and GranularMedia, Elsevier, Amsterdam, 1993. 2. M. Golubitsky & D. Schaeffer, Singularities and Groups in Bifurcation Theory (2 vol.), Springer-Verlag, New York, 1985. 3. P. Prusinkiewicz & A. Lindenmayer, The Algorithmic Beauty of Plants, Springer-Verlag, New York, 1990. 3~

THE MATHEMATICALINTELLIGENCER

4. W.H. Shi, Solutions analytiques de quelques equations aux d6riv~es partielles en m6canique des fluides, Masson, Paris, 1992. 5. J. Villain & A. Pimpinelli, Physique de la Croissance Cristalline, Eyrolles, Paris, 1995.

| | o [ : . ] l ~ V A ~ - ' i l n T - . ~ | l r . | | [ , - I ~ - l | [ o l t l d [ - - ' ~ | lan

Pythagoras and Crotone W.S. Anglin

Stewart,

Editor I

out 525 B.C. P y t h a g o r a s immir a t e d to Crotone, Italy, w h e r e he f o u n d e d the f a m o u s P y t h a g o r e a n Siblinghood (it included w o m e n as well as men). In 1994 Crotone is one of the bestk e p t s e c r e t s o f t h e travel industry. I visited it r e c e n t l y a n d was happily surp r i s e d to find t h a t I was one of v e r y few tourists. It w a s e a s y to get a hotel.

A~

There w e r e plenty o f p a r k i n g spaces. The b e a c h was n o t crowded. Crotone's amenities are partly due to its terrible r e p u t a t i o n in tourist books. Italy: The Rough Guide has this to say:

George Gissing, visiting in 1897, called Crotone "a squalid little town, "and it's not much better now, most of its seafront

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

Crotone beach with surrounding hills.

famous conjecture was made, the desk where the famous initials are scratched, birthplaces, houses, memorials. Does your hometown have a mathematical tourist attraction? Have you encountered a mathematical sight on your travels? If so, we invite you to submit to this column a picture, a description of its mathematical significance, and either a map or directions so that others may follow in your tracks.

Please send all submissions to the The Mathematical Tourist Editor,

lan Stewart, Mathematics Institute, University of Worwick, Coventry CV4 7AL England e-mail: ins@maths,warwick.ac.uk

Crotone's cathedral (with Pythagoras Street on the right). 9 1997SPRINGER-VERLAGNEWYORK,VOLUME19, NUMBER1, 1997 39

Bishop's insignia in the c a t h e d r a l front wall a t Crotone.

g i v e n over to i n d u s t r y - - t h o u g h the v i e w isn't so bad once you get past the port, and it's a good base f o r the beaches that spread to the s o u t h and f o r the Greek r a i n s at Capo Colonna. There's not a lot to see i n Crotone itself. [1]

What The R o u g h G u i d e , and other books, are referring to is the industrial belt that surrounds Cro-tone, that makes it difficult even to find Crotone and that is indeed uglier than the pits of Mordor. However, once you have managed to get into the town itself, everything is enjoyable. There is a beautiful, long sand beach surrounded by an arc of hills. The water (in August) is great for swimming, and the night sky is great for star-gazing. There are some charming town squares with palm trees and fascinating little

C r o t o n e ' s road along the beach.

40 THEMATHEMATICALINTELLIGENCER

shops--including some superb ice cream bars. The mathematical tourist will be pleased to find a Pythagoras Street rtmning up past the old cathedral and a Pythagoras school--devoted to correspondence courses! The bishops of Crotone go back to the fifth century, and they long ago adopted an insignia which includes a hat with 10 tassels arranged in triangular formation, perhaps in memory of the Pythagorean belief that 10 is the holiest of all numbers, for it represents the universe, being the sum of all the possible geometric dimensions [2]. I took a walk out on the surrounding hills and I looked at the ships in the Mediterranean. I walked up into the old city to the museum (which was being renovated), and I saw a woman watching her television through the window, from outside her house. Probably because of the heat in the room where the television was, she had put her chair in the cooler street! I ate an inexpensive and excellent fish dinner in an outdoor restaurant near the beach (one of several places that takes the AMEX card), and I traced a geometrical diagram in the sand, just as Pythagoras no doubt did. At night, I strolled along the road by the sea, looking at the young Italian couples, thinking about Pythagoras and Theano, and picking out some of the constellations. Yes, I stopped for another dish of ice cream before heading back to the warm hospitality of Hotel Bologna. But please tell nonmathematicians that Crotone is a boring industrial town not worth visiting!

C r o t o n e s t r e e t sign in the south wail of the cathedral. REFERENCES

1. R. Belford, M. Dunford, and C. Woolfrey,

Italy: The Rough Guide, London: Rough Guides (1993). 2. C. B. Boyer and U. C. Merzbach, A History of Mathematics, 2nd ed, New York: John Wiley & Sons (1989). 3. K. S. Guthrie, The Pythagorean Sourcebook and Library, Grand Rapids, MI: Phanes Press (1987). Institute for the History and Philosophy of Science and Technology University of Toronto Toronto, Canada MSS 1K7

Pythagoras c o r r e s p o n d e n c e school in Crotone.

Buildings in C r o t o n e ' s industrial zone.

The Pavements of the Cosmati Kim

Williams

I was pleased to see Istvfin Hargittal's short piece, "Octagons Abound," coupled with Brian J. Loe's article on a Penrose tiling in this column a short time ago (Mathematical InteUigencer, vol. 17 (1995), no. 2, 52-54). As both articles rightly point out, the floor plane of any architectural space provides a perfect medium for exploring

[]

[]

[]

1:3

[]

[]

[]

[]

D

[]

D

[]

1:3

[]

O

[]

]-1

Figure 1. T h e typical basilican plan consists of a nave and two side aisles which terminate in semi-circular apses.

the infinite possibilities of tiling patterns. Readers of the InteUigencer know from my essay on the geometry of the pavement of the Baptistery of Florence (vol. 16 (1994), no. 2, 18-24) that I have studied pavements for some years. However, nothing has surlSrised me as much as when, returning to my studio after a trip to study the medieval pavements of the Cosmati family, I flipped open the copy of the InteUigencer which had arrived in that day's mail to find the very patterns I had just been studying in Rome, in Ian Stewart's article (vol. 17 (1995) no. 1, 52-64) on Sierpifiski's Gasket! That these patterns found in pavements almost 1000 years old should fascinate mathematicians in our own century brought home to me in a concrete way the timelessness of geometry. I'd like to share with you some of what I have learned about the Cosmati, and where the visitor to Rome and vicinity can find their work. The pavements known as "Cosmatesque" take their name from several families of marbleworkers who decorated a large number of churches during the twelfth and thirteenth centuries, most of them in or close to Rome, but others as far north as Pisa. (While different families had different surnames, we know from their signatures that many of the individual members were named "Cosmas," so this became the name by which the whole group is known.) The Cosmati decorated in a distinctive style altars, balusters, choirs, candle stands, ambones, bishops' thrones, pulpits . . . . and pavements. All of their decoration was based on geometric patterns, but because the broad area of the floor plane provided a blank canvas, so to speak, upon which designs could be laid at will, it is the pavements which contain the greatest number of mathematical ideas. One of these ideas is bilateral symmetry, which is expressed in the layout of the pavement as a whole. Another is that there are many ways to tile the plane. A third idea is patterns that are self-similar. It is in this last context that we will find Sierpifiski's Gasket. Cosmatesque pavements are found in churches with the basilican plan, that is, churches consisting of a long

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

'41

and circular segments, which were combined in seemingly infinite ways. This is a step beyond the technique of mosaic, in which the tesserae are essentially all square. The Cosmati tesserae were cut from marble originally used to decorate older Roman monuments which had fallen in disuse. And because the Romans, the original "conspicuous consumers," used rare and precious marbles quarried in the farthest reaches of the Empire, Cosmatesque pavements also display a wide range of color, rendering the patterns particularly beautiful. Now we can imagine the marbleworker who laid these pavements 800 or 900 years ago. Having measured the space to determine the layout and proportions of the pavement, he brings with him to the site the curved sections which form the interlacing bands and the porphyry roundels which he has precut in his shop, and he lays them out along the axis of the nave. (Perhaps while he works, he thinks of the flasks of fragrant wine and 3). olive oil which he will reBoth the guiUoche and Figure 2. Plan of the p a v e m e n t of S. M a r i a in C o s m e d i n in Rome. the quincunx patterns, the C o s m a t e s q u e p a v e m e n t s share a c o m m o n s c h e m e , and are sym- ceive as pay for his work.) Now he has to c o m p o s e the leitmotifs of Cosmatesque m e t r i c a l about the longitudinal axis. |After G.B. Giovenale.| designs for the intermedipavements, are based on ate bands. Close to him are circular geometries. Each is bread; because columns were built baskets and baskets of tiles, of differc o m p o s e d of interlacing bands framing with a gradation of diameter k n o w n as ent shapes and different sizes. He beroundels, or disks: in the guiUoche, entasis, the disks so cut varied in di- gins by using the largest tile which will roundels are arranged linearly (Fig. 7); fit the band, then lays the next largest ameter. in the quincunx four disks surround a Geometric patterns, often fractal in tile in the interstice, then the next, uncentral disk. These are fun to construct character, appear between the bands til fmally he places the very smallest in the m a n n e r of the ancient Greeks, and the roundels and in the interstices tiles into their place. When the tiles are with a c o m p a s s and straightedge (Fig. between the bands and the borders in all the same shape, he creates, without 4a and 4b). While the interlacing bands both the guiUoche and the quincunxes. even knowing it, Sierpitiski's Gasket. which form the motives are always uniIdentical patterns are used in the rec- (Fig. 6.) form in width, the roundels, usually of The most complete and most autangles on either side of the axis. (Fig. either reddish-purple or green 5.) To create their patterns, the Cosmati thentic, that is, least restored, CosmaEgyptian porphyry, are never of exused tesserae or tiles cut into a variety tesque pavements may be found in actly the same diameter. That is beRome in S. Maria in Cosmedin (the of geometric shapes, such as triangles, cause they were created by slicing columns as we would slice a loaf of squares, hexagons, rectangles, circles, church with the "Bocca della Verith," central corridor, the nave, which terminates in a semicircular apse, flanked by narrower aisles on either side, which terminate in proportionally smaller apses. (Fig. 1.) The basilican plan is symmetric about the longitudinal axis of the nave, and that axis becomes a line of bilateral synunetry for the pavement design. All Cosmatesque pavements share the same basic layout: the axis is articulated by a serpentine motive called a guilloche and may be accented by another similarly interlaced motive, the quincunx, while the area on either side of the axis is subdivided into rectangles. (Fig. 2.) Each rectangle is filled with a tiling pattern based usually upon either the three regular or a few of the eight semi-regular t'flings of the plane, but patterns are sometimes based on circles as well. The symmetric ar-rangement of the rectangles about the axis is reinforced by the fact that decorative geometric patterns appearing in a rectangle on one side of the axis appear in the corresponding rectangle on the other side (Fig.

~2

THE MATHEMATICALtNTELLIGENCER

Figure 3. The interior of the Basilica of S. Clemente, Rome.

F i g u r e 4. (a) C o n s t r u c t i o n o f t h e g u i l l o c h e ; (b) C o n s t r u c t i o n o f t h e q u i n c u n x .

44

THEMATHEMATICALINTELLIGENCER

the stone d i s k carved like a h u m a n face with an o p e n m o u t h w h i c h w a s supp o s e d to bite the h a n d s o f liars) a n d in S. Clemente. Other Cosmatesque pavem e n t s are f o u n d in S. Maria in A r a c o e l i at the t o p of the Capitoline Hill; in S. Maria in Trastevere, S. Maria Maggiore, and S. Lorenzo fuori le Mura (all o f w h i c h are d e s c r i b e d in the Blue Guide to Rome.) Those w h o can't visit Rome, but are close to London, m a y be surp r i s e d to h e a r that a C o s m a t e s q u e quincunx m a y be found in W e s t m i n s t e r Abbey. Visitors will be a m a z e d at the variety of tiling patterns; m a t h e m a t i c i a n s will be a m u s e d to find that the circle always c o m e s r o u n d again. G e o m e t r i c patterns, like fragrant wine and olive oil, m a y b e a p p r e c i a t e d t o d a y as t h e y w e r e c e n t u r i e s ago. REFERENCES

Beny, Roloff and Gunn, Peter. The Churches of Rome. (London: Weidenfield and Nicolson, 1981 .) Giovenale G.B. La Basilica di S. Maria in Cosmedin. (Rome: P. Sansaini Editore, 1927.) Glass, Dorothy. Studies on Cosmatesque Pavements. British Archaeological Reports International Series, Vol. 82. (Oxford: B.A.R., 1980.) Hutton, Edward. The Cosmati. (London: Routledge and Kegan, Ltd., 1950.) Macadam, Alta. Blue Guide to Rome, 5th ed. (New York: W.W. Norton, 1994.) Williams, Kim. Patterns and Space. (To be published by Anchorage Press, Houston, Texas, 1996.) Via Mazzini 7 1-50054 Fucecchio Florence, Italy

Figure 6. Author's rendering of the Sierpinski's Gasket beside two of the quineunxes in the choir of S. Maria in Cosmedin, Rome.

BELOW: Figure 7. Author's rendering of the nave guilloche of S. Clemente, Rome.

VOLUME19.NUMBER1. 1997 45

Thomas Harriot: Father of English Algebra? Muriel

Seltman

Eddie

Mizzi

and

Stay, traveller, lightly tread; Near this spot lies all that was mortal

Of that most celebrated man THOMAS HARRIOT. He was that most learned Harriot

Of Syon on the River Thames; By birth and education An Oxonian Who cultivated all the sciences And excelled in all-In Mathematics, Natural Philosophy, Theology. A most studious searcher after truth, A most devout worshipper of the Triune God, At the age of sixty, or thereabouts, He bade farewell to mortality, not to life. The Year of our Lord 1621, July 2. [1]

' h e n the distinguished Elizabethan dramatist Christopher Marlowe was being investigated for disseminating atheistic doctrines, one of the accusations made against him was an assertion by him that "Moyses was but a Jugler, & that one Heriots being Sir W. Raleighs man can do more than he." This passing reference is to a man of remarkable and original genius, some-one who, according to D.T. Whiteside [2], has good claim to be considered Britain's greatest mathematical scientist before Newton. Who, then, was Thomas Harriot, and how did the bronze memorial to him come to be placed in the entrance hall of the Bank of England, an institution founded some 70 years or so after his death? Records concerning Thomas Harriot's early life are exiguous. The Oxford University Register suggests that he was born in Oxford in 1560 and graduated from the University in 1580. He subsequently entered the service of Sir Walter Ralegh as a mathematical tutor, giving lessons in navigation to him and his sea captains. Ralegh sent Harriot out to the newly founded North Carolina colony of "Virginia" as a surveyor with Sir Richard Grenville's expedition of 1585. Harriot returned to England at the end of the following year, having learnt, among other things, how to "drink" tobacco smoke. He published at London in 1588 A

W

Thomas Harriot's memorial plaque in the Bank of England's entrance hall (9 Governor and Company of the Bank of England). 46

briefe and true report o f the n e w f o u n d land o f Virginia, an early de-

scription of the colony that included a survey of the merchantable commodi-

THE MATHEMATICALINTELLIGENCER9 1997 SPRINGERVERLAGNEW YORK

ties to be found there as well as a warm and sympathetic account of the religion and customs of the native Indians. Harriot had learnt the Indians' language, and moreover, according to John Aubrey [3], contrived "an Alphabet . . . for the American language, like Devills." A briefe and true report was well received, and was included in the third volume of Hakluyt's Principall navigations. It turned out to be the only work published by Harriot in his lifetime. It was Ralegh who introduced Harriot to Henry Percy, ninth earl of Northumberland, "the Wizard Earl," and when in about 1598 Harriot left Ralegh's patronage Northumberland gave him an annual pension and living quarters in Syon House, Isleworth. Harriot and his mathematical friends, Walter Warner and Thomas Hughes, who became known as Northumberland's "three magi," would often visit him during his imprisonment in the Tower after the Gunpowder Plot of 1605. Harriot continued his studies and observations at Syon House until his death, on 2 July 1621, from a cancerous tumour in the nose. Thomas Harriot possessed a deep and extensive knowledge of the exact sciences of his day. In astronomy his lunar observations in 1609, with the newly invented telescope, predate those of Galileo; he, too, observed the moons of Jupiter and calculated their orbits and periods; and he was a diligent observer of sunspots and comets. In optics he formulated the sine law of refraction in about 1601, some 20 years before Willebrord Snell, who is usually credited with the discovery, and used this law to derive a mathematical description of the rainbow. In mechanics he correctly deduced, even before Galileo had begun to study the dynamics of unresisted free fall, that the path of a projectile moving under gravity with a resistance proportional to its speed is a tilted parabola. In navigation he solved original theoretical problems, demonstrating for example that the stereographic projection is anglepreserving, and applied the results to the practical concern of constructing accurate navigational tables. These are but a few of his achievements, and yet in spite of his technical ability and ex-

The B a n k of England, near the f o r m e r St. Christopher's C h u r c h (which burned down during the G r e a t Fire) w h e r e T h o m a s Harriot was buried.

pertise Harriot was in his own view and that of his contemporaries primarily a mathematician: "As to Harriot, he was so learned, salth Dr. Pell, that had he published all he knew in algebra, he would have left little of the chief mysteries of that art unhandied."[4] The tragedy is that Harriot published nothing of his algebra himself, and it is this neglected area of his work that we shall focus on here. Histories of mathematics refer to the work associated with his name, the A r t i s a n a l y t i c a e p r a x i s (1631), chiefly in connection with his supposed in-

vention of the inequality signs < and >; in so doing they unwittingly connive in a picture that not only is false, but falls to credit him with his real achievements. For Harriot, in effect, brought the latest developments in Continental algebra to England, particularly through his familiarity with Vi~te's work, which he then developed upon independently and significantly. We now know that Harriot was not directly responsible for the P r a x i s , which was put together after his death from papers which are no longer extant by Walter Warner (and, perhaps, one or

two others), when Nathaniel Torporley had failed to complete the task which had been assigned to him in Harriot's will. Torporley was a respected mathematician of the day, reputed to have been associated with Vi~te himself. The manuscripts that we do have (in the British Library and Petworth) cannot have been the origin of the P r a x i s , not only on account of their disorder and incoherence, but also because there are significant differences between them and the published work. Notably, the inequality signs associated with his name are never found in his handwriting in the manuscripts but appear throughout as ~ and ~:2~. Similarly, equality is denoted in the manuscripts by II and not by -- (the sign introduced by Robert Recorde), as in the P r a x i s . The significance of the inequality signs lies in the fact that this is the first time that such signs were used and accorded the same status as the equality sign. There are similarities, however, as well as differences between the manuscripts and the book. Theory of equations and numerical solutions are found in both, and some of the content and layout of the P r a x i s echoes that of the manuscripts, although its errors and inconsistencies attest to the mathematical shortcomings of its editor, Warner. Harriot's notation is extremely workmanlike and, apart from the lack of the exponent, perfectly suited to algebraic manipulation. Although he follows Vi~te in using vowels for unknowns and consonants for knowns (both lower case), it is free of words and their abbreviations and is fully symbolic. He writes in the manuscripts, using _] for multiplication [5]: b-a

c - a df +

II

aa

bcdf - bdfa + dfaa - baaa - cdfa + bcaa - caaa + aaaa

ii 0000 Ergo:

bcdf II

a nb

+ bdfa - bcaa + baaa

a n c

+ cdfa - dfaa + caaa

a a II - d f

-

aaaa

a II ~/ - d f VOLUME 19, NUMBER 1, 1997

4'7

Note the homogeneity, even extending to zero, which is treated as a calculable entity. This last feature is remarkable for his time. He is not afraid of equating all terms to zero and even, elsewhere, to a negative quantity. But most importantly in the above example, note the inclusion of an imaginary root without comment. Harriot's advances in the theory of equations include a method of "solution" by a sort of reverse factorization, shown briefly in the same example above. The Praxis does likewise, but in a more explicatory way. The weli-known inequalities between arithmetic and geometric means (and their generalizations in powers) appear in both the manuscripts and the Prax/s, and form the basis in the latter of an ingenious attempt at determining the number of (positive) roots in an equation by comparing it with a canonical equation, the number of whose (positive) roots is known, by means of a device closely resembling a discriminant. The method works for positive room; apart from two examples [6], only positive roots are considered in the Prax/s, which may well have been intended for students. The final theoretical part of the Prax/s is devoted to removing one term in an equation and changing the root; in this, Vi~te's De aequationum recognitione et emendatione is followed pretty closely, albeit with Harriot's highly superior notation. It is, however, with respect to negative and complex roots that the most significant differences occur between the P r a x i s and the manuscripts. Although the P r a x i s states that equations involving negative roots are to be disregarded as they are useless ( " t a m q u a m inutiles negliguntur") and those involving the square-root of a negative quantity are referred to as "impossible" because they are "inexplicable" (meaning unsolvable in this context), a different picture emerges in the manuscripts. Here, negative roots are almost always given, without comment. As for complex roots, called by Harriot "noetic," a folio exists [7] in which a biquadratic is fully worked through and solved in terms of one positive, one negative, and two complex roots, whose values are written [8] ~ 48

THE MATHEMATICALINTELLIGENCER

5 II a,

- 7 II a,

aII+l+

~-32,

all+l-

~-32.

Elsewhere in the manuscripts [9], a number of imaginary solutions are given, although not in all cases in which such solutions exist. The most likely explanation is that the lists of equations in the manuscripts in which solutions are not derived but are merely stated, and in which complex roots are not given, are simply examples for students to work through, and the complex roots are omitted for pedagogical reasons. There are, in addition [10], at least three cubic equations for which only two real roots are given; and it turns out that of the three roots of these equations, two are coincident. However, coincident roots are found elsewhere [11]. The second part of the Praxis consists of the numerical solution of equations up to the fifth degree, and the method used, as in the examples given in the manuscripts, differs little from that of Vi~te (De numerosa potestat u m recognitione). Harriot's notation is particularly useful in this field. For, instead of Vi~te's use of C, Q, and N (standing for the cube of the unknown, its square, and the unknown itself), together with verbal explanations in Latin which appear to us to be very convoluted, Harriot's presentation is crystal clear. It is designed for easy manipulation and very largely speaks for itself. The impact of this must have been considerable, supplying the basis for further advances. Harriot's contribution to algebra, therefore, is considerably greater than that with which he is normally credited. He brought Britain into the mainstream of Continental developments through his wide-ranging theoretical and practical concerns and the accessibility of his methodology and notation. He himself was in the mainstream, as his references to Stevin, Bombelli, Stifel, and ViSte in the manuscripts testify. His achievements later prompted John Wallis to comment that Harriot had laid the foundation "without which the whole superstructure of Descartes had never been" [12]--a remark he later toned down.

Apart from algebra, other branches of pure mathematics are to be found in the enormous volume of Harriot manuscripts. Examples are worked in binary notation; there is work on Pythagorean triples; meridional parts are calculated with a treatment closely resembling calculus; and there is the quadrature of the equiangular spiral [13]. Thomas Harriot died on 2 July 1621 in the house of his friend Thomas Buckner in Threadneedle Street. He was buried in the nearby churchyard of St. Christopher's parish church, and a memorial plaque was placed in the chancel of the church. Although St. Christopher's was completely destroyed in the Great Fire in 1666, the wording of Harriot's memorial was, quite fortuitously, preserved in the 1633 edition of John Stowe's The survey of London. The Bank of England was founded in 1694 but did not occupy its present site near the former St. Christopher's church in Threadneedle Street until 1734. Three hundred and fifty years after Harriot's death a bronze plaque bearing the original epitaph was installed in a niche in the entrance hall of the bank. A yet more poignant epitaph might be furnished by Harriot's friend William Lower's urgings to him to publish his discoveries. On 6 February 1610 he wrote to Harriot [14]: Doe you not here startle, to see every day some of your inventions taken from you; for I remember longe since you told me as much [as Kepler has just published] that the motions of the planets were not perfect circles. So you taught me the curious way to observe weight in Water, and within a while after Ghetaldi comes out with it, in print. A little before Vieta prevented you of the Gharland for the greate invention of Algebra. al these were your deues and manie others that I could mention; and yet too great reservednesse hath rob'd you of these glories. Nevertheless, more than 250 years later, on 5 September 1883, J.J. Sylvester was to write to Arthur Cayley a letter in which he acknowledged Harriot to be "the man who fwst introduced the

Algebralcal Zero into Analysis, the father of current Algebra." [15]. ACKNOWLEDGMENTS

Need help with your tensor analysis?

The authors would like to thank the Curator and staff of the Museum & Historical Research Centre of the Bank of England for the photograph of Harriot's plaque and for their kind and generous help. REFERENCES

1. The translation is John Shirley's. See John W. Shirley, Thomas Harriot: a biography. Oxford University Press, 1983, p. 474. 2. D. T. Whiteside, "In search of Thomas Harriot." History of Science, Xlll (1975), 3. 4. 5. 6.

7.

8.

9. 10. 11. 12.

13.

14. 15.

p. 61. O. L. Dick (ed.), Aubrey's brief lives. London, Penguin, 1972, p. 281. Quoted in Shirley, op. cit., p. 9. British Library ADD. MSS 6783, f. 156r. Thomas Harriot, Artis analyticae praxis. London, 1631, Section 5, Problems 9, 11, pp. 95, 97. Pointed out in R. C. H. Tanner, "Thomas Harriot as mathematician. A legacy of hearsay." Physis, IX (1967), p. 262. This can be found in Stephen P. Rigaud, Supplement to Dr. Bradley's miscellaneous works: with an account of Harriot's astronomical papers. Oxford University Press, 1833, p. 52 and Plate 5. British Library ADD. MSS 6783, f. 49r, for example. British Library ADD. MSS 6783, f. 52v, for example. British Library, ADD. MSS 6783, f. 422r. Quoted in A. M. Clerke, "Thomas Harriot." Dictionary of national biography. Oxford University Press. J. V. Pepper, "The study of Thomas Harriot's manuscripts. II. Harriot's unpublished papers." History of Science, 6 (1967), 17-40. Quoted in Shirley, op. cit., p. 1. J. Fauvel, "J.J. Sylvester and the papers of 'Old Father Harriot'." The Harrioteer, September, 1996.

School of Education

MathTensor A d v a n c e d T o n s e w A n a l y s i s for M a t h e m a t i c a Developed by L e ~ a r d P a r k ~ and ~ e v ~ z M, Christe~mm

Now compatible

MathemsUea

3.0

Contaet your Mathematiea Dealer o~.

General Purpose System Over 275 Functions and Objects Differential Forms Concrete and Abstract Indices Mowmm4yMathSolutio~s, Ine, Programmability Powerful Simplification Capabilities User Definable Tensors P.O. B o x 16175 E a s y T ensor Input C h a p e l H i l l , NC 27516 USA Readable Tensor Output Compute Rlemann Tensors P h o n e : 919-382-5584 o r 4 1 4 - 9 6 4 - 6 2 8 4 and Related Objects F a x : 919-382-8979 o r 4 1 4 - 9 6 4 - 6 2 8 4 381 P a g e M a t h T e n s o r B o o k f~om Addison-Wesley Email: mathtensor Pwolfram.com Web: h t t p : / s m e . v n c t . n c t / M a i h T e n s o r . h t m l Export Suppm't

M a t h T e n s o r , Inc.

M ~ is a T ~ a z ~ k of MathTeu~ In~ Msthsmatiaa il 9R~gis/amd Tradsmaz~kof Wol/~am~

In~

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

THE MATHEMATICAL INTELLIGENCER. Please fill out the f o r m b e l o w and send it to:

Springer-Verlag New York Inc. Journal Fulfillment Services P.O. Box 2485, Secaucus, NJ 07096-2485 Name Old Address (or l a b e l )

University of Greenwich Eltham London, SE9 2HB UK

Address City/State/Zip Name

New Address

Oxford Centre for Innovation Mill Street Oxford OX2 0JX UK e-mail: eddie.mizzi@MCR1 .poptel.org.uk

with

Address City/State/Zip Please give us six weeks

notice.

VOLUME19, NUMBER1, 1997 49

The Quest

Or

I. H . B A I L E Y ,

t

J. M. BORWEIN,

AND

S. P L O U F F [

his articlegivesa briefhistoryof the analysisand computationof themathematical constant =3.14159. includinga numberofformulasthathavebeenusedtocom~::: thr~:~ tn;~eSr~cSOmeoeXm~it :nagtireCeo~td~ve:~?snt::~t;: c~i;c~lS::di~S:;n~ 71"

m

m

high-order convergent algorithms, a n d a n e w l y d i s c o v e r e d s c h e m e that p e r m i t s a r b i t r a r y individual h e x a d e c i m a l digits o f ~- to b e computed. F o r further details of the history of qr up to a b o u t 1970, the r e a d e r is referred to P e t r B e c k m a n n ' s r e a d a b l e a n d entertaining b o o k [3]. A listing o f m i l e s t o n e s in the history o f the c o m p u t a t i o n of ~r is given in Tables 1 and 2, w h i c h w e believe to be m o r e c o m p l e t e t h a n o t h e r readily a c c e s s i b l e sources.

The Ancients In one of the earliest a c c o u n t s ( a b o u t 2000 B.C.) of ~-, the 1 B a b y l o n i a n s used the a p p r o x i m a t i o n 3 ~ = 3.125. At this s a m e time o r earlier, a c c o r d i n g to an a c c o u n t in an a n c i e n t Egyptian document, Egyptians w e r e assuming that a circle with d i a m e t e r nine has the s a m e a r e a as a square of side eight, w h i c h implies ~r= 256/81 = 3.1604 . . . . Others of antiquity w e r e content to use the simple a p p r o x i m a t i o n 3, as e v i d e n c e d b y the following p a s s a g e from the Old Testament: Also, he m a d e a m o l t e n s e a o f ten cubits from b r i m to brim, r o u n d in compass, a n d five cubits the height 50

P. B . B O R W E I N ,

THE MATHEMATICALINTELLIGENCER9 1997 SPRINGER-VERLAGNEW YORK

thereof; and a line of thirty cubits did c o m p a s s it r o u n d about. (I Kings 7:23; see also 2 Chron. 4:2) The first r i g o r o u s m a t h e m a t i c a l calculation of the value of 1r was due to A r c h i m e d e s of Syracuse ( - 2 5 0 B.c.), w h o u s e d a g e o m e t r i c a l s c h e m e b a s e d on i n s c r i b e d and circ u m s c r i b e d p o l y g o n s to obtain the b o u n d s 3 ~10 < ~r < 3 k7' or in o t h e r words, 3 . 1 4 0 8 . . . < 7r < 3 . 1 4 2 8 . . . [11]. No one was able to i m p r o v e on A r c h i m e d e s ' s m e t h o d for m a n y centuries, although a n u m b e r of p e r s o n s u s e d this general m e t h o d to obtain m o r e a c c u r a t e a p p r o x i m a t i o n s . F o r example, the a s t r o n o m e r Ptolemy, w h o lived in A l e x a n d r i a in A.D. 150, u s e d the value 3 ~~7 = 3.141666.. ., and the fifthcentury Chinese m a t h e m a t i c i a n Tsu Chung-Chih u s e d a variation of A r c h i m e d e s ' s m e t h o d to c o m p u t e ~ c o r r e c t to seven digits, a level n o t attained in E u r o p e until the 1500s.

The Age of Newton As in o t h e r fields of science and m a t h e m a t i c s , p r o g r e s s in the quest for qr in medieval times o c c u r r e d mainly in the Islamic world. AI-Kashi of S a m a r k a n d c o m p u t e d 7r to 14 p l a c e s in a b o u t 1430. In the 1600s, with the discovery of calculus by Newton

tABLE

1. H i s t o r y o f ~T C a l c u l a t i o n s

(Pre-2Oth-Century

TABLE

2. History

o f 7;- C a l c u l a t i o n s

120th Centur

Babylonians

2000? B.C.E,

1

3.125 (3 {)

Ferguson

1946

620

Egyptians

2000? B,C,E.

0

3.16045 [4 (~)2]

Ferguson

Jan. 1947

710

China

1200? B.C,E.

0

3

Ferguson and Wrench

Sep. 1947

Bible (1 Kings 7:23)

550? B,C.E.

0

3

Smith and Wrench

1949

808 1,120

Archimedes

250? B.C.E,

3

3.1418 (ave.)

Reitwiesner, et aL (ENIAC)

1949

2,037

Hon Han Shu

A.D. 130

0

3.1622 (= ~ / 1 0 ?)

Nicholson and Jeenel

1954

3,092

Ptolemy

150

3

3.14166

Felton

1957

Chung Hing

250?

0

3.16227 ('~1"0)

Genuys

Jan. 1958

10,000

Wang Fau

250?

0

3.15555 (1::)

Feiton

May 1958

10,021

Liu Hui

263

5

3,14159

Guilloud

1959

16,167

Siddhanta

380

4

3.1416

Shanks and Wrench

1961

100,265

Tsu Ch'ung Chi

480?

7

3.1415926

Guilloud and Filliatre

1966

250,000

Aryabhata

499

4

3.14156

Guilloud and Dichampt

1967

500,000

Brahmagupta

640?

0

3,162277 (= "k/'~)

Guilloud and Bouyer

1973

1,001,250

AI-Khowarizmi

800

4

3,1416

Miyoshi and Kanada

1981

2,000,036

Fibonacci

1220

3

3.141818

Guilloud

1982

2,000,050

AI-Kashi

1429

14

Tamura

1982

2,097,144

Otho

1573

6

3.1415929

Tamura and Kanada

1982

4,194,288

Viete

1593

9

3.1415926536 (ave.)

Tamura and Kanada

1982

8,388,576

7,480

Romanus

1593

15

Kanada, Yoshino, and Tamura

1982

16,777,206

Van Ceulen

1596

20

Ushiro and Kanada

Oct. 1983

10,013,395

Van Ceulen

1615

35

Gosper

1985

17,526,200

Newton

1665

16

Bailey

Jan. 1986

29,360,111 33,564,414

Sharp

1699

71

Kanada and Tamura

Sep. 1986

Seki

1700?

10

Kanada and Tamura

Oct. 1986

67,108,839

Kamata

1730?

25

Kanada, Tamura, Kubo, et aL

Jan. 1987

134,217,700

Machin

1706

100

De Lagny

1719

127

Takebe

1723

Matsunaga

1739

Vega

Kanada and Tamura

Jan. 1988

201,326,551

Chudnovskys

May 1989

480,000,000

41

Chudnovskys

June 1989

525,229,270

50

Kanada and Tamura

July 1989

536,870,898

1794

140

Kanada and Tamura

Nov. 1989

1,073,741,799

Chudnovskys

Aug. 1989

1,011,196,691

Chudnovskys

Aug. 1991

2,260,000,000

(112 correct)

Rutherford

1824

208

Strassnitzky and Dase

1844

200

(152 correct)

Clausen

1847

248

Chudnovskys

May 1994

4,044,000,000

Lehmann

1853

261

Takahashi and Kanada

June 1995

3,221,225,466

Rutherford

1853

440

Kanada

Aug. 1995

4,294,967,286

Shanks

1874

707

Kanada

Oct. 1995

6,442,450,938

(527 correct)

and Leibniz, a n u m b e r o f substantially n e w formulas for ~r w e r e discovered. One o f t h e m can be easily derived by recalling that tan-Ix =

(1 - t 2 + t4 -

1 ~ t2 x3

x5

=x--~-+

x7

5

t 6 + -..) dt

1

1

4

, ~3 . 2

1

7 +

+

9

1

1

1

9

11 +

Regrettably, this series converges so slowly that hundreds o f terms w o u l d be required to c o m p u t e the numerical value o f ~- to e v e n t w o digits accuracy. However, by e m p l o y i n g the trigonometric identity + tan -1

1

+ ~5 . 2

7.27

) e''"

(;1

~-= 1 - ~ + g - ~ - +

-- = tan-: 4

o(1

x9

Substituting x = 1 gives the w e l l - k n o w n Gregory-Leibniz formula ~-

( w h i c h f o l l o w s f r o m the addition formula for the tangent function), one obtains

~ 3.3

,

,

+ ~5 " 3

7"3 ~

) +''"

'

w h i c h converges m u c h m o r e rapidly. An e v e n faster formula, due to Machin, can be obtained b y e m p l o y i n g the identity ~r 4

4 t a n -1

(1)

- tan -1

(1)

in a similar way. Shanks u s e d this s c h e m e to c o m p u t e rr to 707 decimal digits accuracy in 1873. Alas, it w a s later f o u n d that this c o m p u t a t i o n w a s in error after the 527th decimal place. VOLUME19, NUMBER1, 1997 51

N e w t o n d i s c o v e r e d a similar series for the arcsine function: 1.x 3 sin-Ix=x+--+

1.3.x

2"3

5

1.3.5.x +

2"4-5

v + ""-

2"4"6"7

can b e c o m p u t e d from this f o r m u l a by noting that ~/6 = s i n - l ( 1 / 2 ) . An even faster f o r m u l a of this type is

( 1 ~" = -3- -~~

1

+ 24 -3 : 23

1

1

5 " 25 - 7 " 27

9 " 29

) "

N e w t o n h i m s e l f u s e d this p a r t i c u l a r formula to c o m p u t e ~-. He p u b l i s h e d only 15 digits, b u t l a t e r sheepishly admitted, "I a m a s h a m e d to tell you h o w m a n y figures I carried t h e s e c o m p u t a t i o n s , having no o t h e r b u s i n e s s at the time." In the 1700s, the m a t h e m a t i c i a n Euler, arguably the m o s t prolific m a t h e m a t i c i a n in history, d i s c o v e r e d a numb e r of n e w formulas for ~-. A m o n g these are ~2

6 17.4 90

1 -1+

7

1 +

1 +

+ "'

1 -i+

1 +

1 +

1 +

1 +

+ ""

A related, m o r e rapidly c o n v e r g e n t series is ~ 6

3 m=l

m2(2m)

9

These formulas, despite their i m p o r t a n t theoretical implications, a r e n ' t very efficient for c o m p u t i n g ~r. One motivation for c o m p u t a t i o n s of ~r during this time w a s to see if the decimal e x p a n s i o n of 7r repeats, thus disclosing t h a t ~- is the ratio of t w o integers (although h a r d l y a n y o n e in m o d e r n times seriously believed this). The question w a s settled in the late 1700s, w h e n L a m b e r t a n d Legendre p r o v e d that ~- is irrational. Some still w o n d e r e d w h e t h e r ~- might be the r o o t of s o m e algebraic equation with integer coefficients (although, as before, few really b e l i e v e d t h a t it was). This question was finally settled in 1882 w h e n Lindemann p r o v e d that ~r is transcendental. L i n d e m a n n ' s p r o o f also settled o n c e and for all, in the negative, the ancient G r e e k question of w h e t h e r the circle could be squared with rule a n d compass. This is b e c a u s e c o n s t r u c t i b l e n u m b e r s are n e c e s s a r i l y algebraic. In the annals of ~r, the m a r c h of the nineteenth-century p r o g r e s s s o m e t i m e s faltered. Three y e a r s p r i o r to the t u r n o f the century, one Edwin J. Goodman, M.D. i n t r o d u c e d into the Indiana House of R e p r e s e n t a t i v e s a "new M a t h e m a t i c a l truth" to enrich the state, which w o u l d profit from the royalties ensuing from this discovery. Section t w o of his bill included the p a s s a g e disclosing the fourth i m p o r t a n t fact that the ratio of the d i a m e t e r and c i r c u m f e r e n c e is as five-fourths to four; Thus, one of G o o d m a n ' s n e w m a t h e m a t i c a l "truths" is that 1~= 3.2. The Indiana H o u s e p a s s e d the bill unanim o u s l y on Feb. 5, 1897. It then p a s s e d a Senate c o m m i t t e e and w o u l d have b e e n e n a c t e d into law h a d it not b e e n for the last-minute intervention of Prof. C. A. Waldo of P u r d u e 52

THE MATHEMATICALINTELLIGENCER

University, w h o h a p p e n e d to h e a r s o m e of the deliberation while on o t h e r business.

The Twentieth Century With the d e v e l o p m e n t of c o m p u t e r t e c h n o l o g y in the 1950s, ~r was c o m p u t e d to t h o u s a n d s and then millions of digits, in both decimal a n d binary b a s e s (see, for example, [17]). These c o m p u t a t i o n s w e r e facilitated b y the discovery of some a d v a n c e d algorithms for performing the required high-precision arithmetic operations on a computer. F o r example, in 1965, it w a s found that the n e w l y discovered fast Fourier transform (FFY) could be used to p e r f o r m high-precision multiplications m u c h m o r e rapidly than conventional schemes. These m e t h o d s dramatically l o w e r e d the computer time required for computing ~ and o t h e r mathematical constants to high precision. See [1], [7], and [8]. In spite of t h e s e advances, until the 1970s all c o m p u t e r evaluations for ~- still e m p l o y e d classical formulas, usually a variation of Machin's formula. Some n e w infmite series formulas w e r e d i s c o v e r e d by the Indian m a t h e m a t i c i a n Ramanujan a r o u n d 1910, but these w e r e n o t well k n o w n until quite r e c e n t l y w h e n his writings w e r e widely published. One of t h e s e is the r e m a r k a b l e f o r m u l a 1 ~-

2 ~f2 9801

~ 2_.

k=0

(4k)!(1103 + 26,390k) (k!)43964a

Each t e r m o f this series p r o d u c e s an additional eight correct digits in the result. G o s p e r u s e d this f o r m u l a to compute 17 million digits of ~ in 1985. Although R a m a n u j a n ' s series is c o n s i d e r a b l y m o r e efficient than the classical formulas, it s h a r e s with t h e m the p r o p e r t y that the n u m b e r of t e r m s one m u s t c o m p u t e inc r e a s e s linearly with t h e n u m b e r of digits d e s i r e d in the result. In o t h e r words, if one wishes to c o m p u t e ~ to twice as m a n y digits, t h e n one m u s t evaluate twice as m a n y t e r m s of the series. In 1976, Eugene Salamin [16] and Richard Brent [8] ind e p e n d e n t l y d i s c o v e r e d a n e w algorithm for ~-, which is b a s e d on the a r i t h m e t i c - g e o m e t r i c m e a n a n d s o m e ideas originally due to G a u s s in the 1800s (although, for s o m e reason, Gauss n e v e r s a w the c o n n e c t i o n to computing ~). This algorithm p r o d u c e s a p p r o x i m a t i o n s t h a t converge to ~ m u c h m o r e rapidly than any classical formula. The Salamin-Bre~s algorithm m a y be s t a t e d as follows. Set a 0 = 1, b 0 = l / V 2 , ands0=l/2. Fork=l, 2, 3 , . . . compute ak--

ak-1 + bk-1 2 '

bk = ~ / a k Ck

=

l b k - 1,

a 2 - b 2,

Sk = S k - 1 -- 2kck, 2a 2 Pk =

Sk

Then P k c o n v e r g e s q u a d r a t i c a l l y to ~r. This m e a n s that each iteration of this algorithm a p p r o x i m a t e l y d o u b l e s the

n u m b e r of c o r r e c t digits. To be specific, successive iterations p r o d u c e 1, 4, 9, 20, 42, 85, 173, 347, and 697 c o r r e c t digits of ~r. Twenty-five iterations are sufficient to c o m p u t e 7r to over 45 million decimal digit accuracy. However, each of these iterations m u s t be p e r f o r m e d using a level of num e r i c p r e c i s i o n t h a t is at least as high as that d e s i r e d for the final result. The S a l a m i n - B r e n t algorithm requires the e x t r a c t i o n of square r o o t s to high precision, o p e r a t i o n s not required, for example, in Machin's formula. High-precision square r o o t s c a n b e efficiently c o m p u t e d by m e a n s of a N e w t o n iteration s c h e m e that e m p l o y s only multiplications, plus s o m e o t h e r o p e r a t i o n s o f m i n o r cost, using a level o f numeric p r e c i s i o n that doubles with each iteration. The total c o s t o f c o m p u t i n g a square r o o t in this m a n n e r is only a b o u t t h r e e t i m e s the c o s t o f p e r f o r m i n g a single full-precision multiplication. Thus, algorithms s u c h as the S a l a m i n - B r e n t s c h e m e can b e i m p l e m e n t e d very rapidly on a computer. Beginning in 1985, two of the p r e s e n t authors ( J o n a t h a n and P e t e r Borwein) d i s c o v e r e d s o m e additional algorithms of this t y p e [5-7]. One is as follows. Set a0 = 1/3 and So =

b e e n e m p l o y e d by Yasumasa Kanada o f the University of Tokyo in several c o m p u t a t i o n s of ~r o v e r the p a s t 10 years o r so. In the latest of these computations, K a n a d a comp u t e d over 6.4 billion decimal digits on a Hitachi supercomputer. This is p r e s e n t l y the w o r l d ' s r e c o r d in this arena. More recently, it has b e e n further s h o w n that there are algorithms that g e n e r a t e m t h - o r d e r c o n v e r g e n t approxim a t i o n s to 7r for a n y m. An e x a m p l e of a nonic (ninthorder) algorithm is the following: Set a0 = 1/3, r0 = (~v/-3 1)/2, and So = (1 - r3) 1/3. Iterate t = 1 + 2rk, u = [9rk(1 + rk + ~)],/3, v = t 2 + t u + U 2,

m =

1}

a k + l = m a k + 32k-1(1 -- m),

(1 - rk) 3 Sk+l = (t + 2 U ) , ' r k + l = (1 -- S3k)1/3.

(N//3 - 1)/2. Iterate 3 rk+l = 1 + 2 ( 1 - s 3 )

V3 '

r k + l -- 1 Sk+l

2

--

'

a k + l = ~k+lak -- 3k(~+1 -- 1).

Then 1/ak converges c u b i c a l l y to ~r--each iteration app r o x i m a t e l y triples the n u m b e r of c o r r e c t digits. A quartic algorithm is as follows: Set a0 = 6 - 4 N / 2 a n d Y0 = N / ~ - 1. Iterate

1

-

(1

-

y4)1/4

Yk+l = 1 + (1 - y4)1/4 , ak+l = ak(1 + Yk+l) 4 -- 22k+3Yk+l(1 + Yk+l + Y~+I). Then 1/ak c o n v e r g e s q u a r t i c a l l y to ~r. This p a r t i c u l a r algorithm, t o g e t h e r with the S a l a m i n - B r e n t scheme, h a s :IGURE

Time in seconds 3000

Grego~ t-Leibniz

Brent-Salaminno FFT

2500 Machin 2000

27(1 + sk + s~)

4 Borwein-Gar,/annonicFFT

Borwein cubic FFT

1000 ~-

Borwein q

Then 1/ak c o n v e r g e s n o n i c a l l y to 7r. It should b e noted, however, that t h e s e higher-order algorithms do n o t a p p e a r to be faster as c o m p u t a t i o n a l s c h e m e s than, say, the S a l a m i n - B r e n t or the Borwein quartic algorithms. Although fewer iterations are required to achieve a given level of p r e c i s i o n in the higher-order schemes, e a c h iteration is m o r e expensive. A c o m p a r i s o n of actual c o m p u t e r run t i m e s for various ~- algorithms is s h o w n in Figure 1. These run t i m e s are for c o m p u t i n g ~- in b i n a r y to various p r e c i s i o n levels on an IBM RS6000/590 workstation. The a b s c i s s a of this plot is in h e x a d e c i m a l d i g i t s - - m u l t i p l y these n u m b e r s by 4 to obtain equivalent b i n a r y digits, or b y log10(16) = 1 . 2 0 4 1 2 . . . to obtain equivalent d e c i m a l digits. Other i m p l e m e n t a t i o n s on o t h e r s y s t e m s m a y give s o m e w h a t different r e s u l t s - for example, in K a n a d a ' s r e c e n t c o m p u t a t i o n o f ~- to over six billion digits, the quartic algorithm r a n s o m e w h a t faster than the S a l a m i n - B r e n t algorithm (116 h o u r s v e r s u s 131 hours). But the overall picture from s u c h c o m p a r i s o n s is unmistakable: t h e m o d e r n s c h e m e s run m a n y t i m e s faster than the classical schemes, especially w h e n i m p l e m e n t e d using F F F - b a s e d arithmetic. David and Gregory Chudnovsky of Columbia University have also done s o m e very high-precision computations of ~in recent years, alternating with Kanada for the world's record. Their most recent computation (1994) p r o d u c e d over four billion digits of ~- [9]. They did not employ a high-order convergent algorithm, such as the Salamin-Brent or Borwein algorithms, but instead utilized the following infinite series (which is in the spirit of Ramanujan's series above):

tiC FFT

1 -T-"= Brenf-,%-~l"llin FFT

Number of HEX digits

,~ 12 k~= 0

( - 1 ) k (6k)!(13,591,409 + 545,140,134k)

(3k)! (k!) 3 640,3203k+3/2

E a c h t e r m o f this s e r i e s p r o d u c e s an a d d i t i o n a l 14 c o r r e c t digits. The C h u d n o v s k y s i m p l e m e n t e d this f o r m u l a with a verdi clever s c h e m e that e n a b l e d t h e m to utilize the results VOLUME 19, NUMBER 1, 1997

53

of a certain level of precision to extend the calculation to even higher precision. Their program was run on a homebrewed supercomputer that they have assembled using private funds. An interesting personal glimpse of the Chudnovsky brothers is given in [14]. Computing Individual Digits of 7r At several junctures in the history of 7r, it was widely believed that virtually everything o f interest with regard to this constant had been discovered and, in particular, that no fundamentally new formulas for 7r lay undiscovered. This sentiment was even suggested in the closing chapters of Beckmann's 1971 b o o k on the history of ~- [3], p. 172. Ironically, the Salamin-Brent algorithm was discovered only 5 years later. A m o r e recent reminder that we have not c o m e to the end of humanity's quest for knowledge about 7r came with the discovery of the Rabinowitz-Wagon "spigot" algorithm for Ir in 1990 [15]. In this scheme, successive digits of 7r (in any desired base) can be c o m p u t e d with a relatively simple recursive algorithm based on the previously generated digits. Multiple-precision computation software is not required; therefore, this scheme can be easily implemented on a personal computer. Note, however, that this algorithm, like all of the other schemes mentioned above, still has the property that in order to compute the dth digit of ~r, one must first (or simultaneously) compute each of the preceding digits. In other words, there is no "shortcut" to computing the dth digit with these formulas. Indeed, it has been widely assumed in the field (although never proven) that the computational complexity of computing the dth digit is not significantly less than that of computing all of the digits up to and including the dth digit. This may still be true, although it is probably very hard to prove. Another c o m m o n feature of the previously k n o w n ~- algorithms is that they all appear to require substantial amounts of computer memory, amounts that typically grow linearly with the n u m b e r of digits generated. Thus, it was with no small surprise that a novel scheme was recently discovered for computing individual hexadecimal digits of ~- [2]. In particular, this algorithm (1) produces the dth hexadecimal (base 16) digit of 7r directly, without the need of computing any previous digits, (2) is quite simple to implement on a computer, (3) does not require multiple-precision arithmetic software, (4) requires very little memory, and (5) has a computational cost that grows only slightly faster than the index d. For example, the one millionth hexadecimal digit of ~- can be c o m p u t e d in only a minute or two on a current RISC workstation or high-end personal computer. This algorithm is not fundamentally faster than other k n o w n schemes for computing all digits up to some position d, but its elegance and simplicity are, nonetheless, of considerable interest. This scheme is based on the following remarkable new formula for qr:

1(4 ~=

i=0

~

8i+1

1 8i+4

THE MATHEMATICAL INTELLIGENCER

8i+5

1) 8i+6-

"

The proof of this formula is not very difficult. First, note that for any k < 8,

1" l / ~ x k - i -------~ 1 - x dx

~I/X/2iZO "0 X k-l+si dX

= -

-

1~

1

2k/2 i=0 16i(8i + k) Thus, we can write

~=o~

8i+1

8i+4

[

llX/2

8i+5

8i+6

4 N / 2 - 8x 3 - 4 N / 2 x 4 - 8x 5

]:J

dx,

which on substituting y := V 2 x b e c o m e s

Soly 4 _ 2,o,,_1o y3+4y_4

dy =

S ~4,,

dy 4y -

8

y2 _ 2y + 2 dy

~r,

reflecting a partial fraction decomposition of the integral on the left-hand side. However, this derivation is dishonest, in the sense that the actual route of discovery was m u c h different. This formula was actually discovered not by formal reasoning, but instead by numerical searches on a computer using the "PSLQ" integer-relation-finding algorithm [10]. Only afterward was a p r o o f found. A similar formula for 7r2 (which also w a s first discovered using the PSLQ algorithm) is as follows: 1 / 16 ~-2 = i=~0=1-~ / (8i + 1) 2 16

16 (8i + 2) 2 4

- ----------~ (8i + 4) - -(8i - - - -+- - -5)~

8 (8i + 3) 2 4

2

\

- (-------------~ 8 i + 6) + ~(8i )+ 7)

'

Formulas of this type for a few other mathematical constants are given in [2]. Computing individual hexadecimal digits of ~- using the above formula crucially relies on what is k n o w n as the binary algorithm for exponentiation, wherein one evaluates x n by successive squaring and multiplication. This reduces the n u m b e r of multiplications required to less than 2 log2(n). According to Knuth, this technique dates back at least to 200 B.C. [13]. In our application, we need to obtain the exponentiation result modulo a positive integer c. This can be efficiently done with the following variant of the binary exponentiation algorithm, wherein the result of each multiplication is reduced modulo c: To compute r = b n rood c, first set t to be the largest p o w e r of 2 -< n, and set r = 1. Then A: if n - t then

r (-- b r

mod c;

n *-- n - t;

endif

t+--t~2

if t - 1 then r *-- r 2 m o d c;

go to A;

endif

Upon exit from this algorithm, r has the desired value. Here "mod" is used in the binary operator sense, namely as the binary function defined b y x m o d y : = x - [ x / y ] y . Note that

the above algorithm is entirely performed with positive integers that do not exceed c 2 in size. As an example, when computing 349 m o d 400 by this scheme, the variable r assumes the values 1, 9, 27, 329, 241, 81, 161, 83. Indeed 349 = 239299329230617529590083, so that 83 is the correct result. Consider now the first of the four sums in the formula above for 77=. $1 =

2

k=0

'

106

~ 0 164-k frac(164 $1) = = 8k +-------i-m o d 1 a 16a - k m o d 8k + 1 = ~'~ 8k + 1 mod 1 k=O

~ 16a -e - m o d 1. k=4+1 8k + 1

For each term of the first summation, the binary exponentiation scheme can be used to rapidly evaluate the numerator. In a computer implementation, this can be done using either integer or 64-bit floating-point arithmetic. Then floating-point arithmetic can be used to perform the division and add the quotient to the sum mod 1. The second summation, where the exponent of 16 is negative, may be evaluated as written using floating-point arithmetic. It is only necessary to compute a few terms of this second summation, just enough to ensure that the remaining terms sum to less than the "epsilon" of the floating-point arithmetic being used. The final result, a fraction between 0 and 1, is then converted to base 16, yielding the (d + 1)th hexadecimal digit, plus several additional digits. Pull details of this scheme, including some numerical considerations, as well as analogous formulas for a n u m b e r of other basic mathematical constants, can be found in [2]. Sample implementations of this scheme in both Fortran and C are available from the web site http://www.cecm.sfu.ca/personal/

pborwein/. As the reader can see, there is nothing very sophisticated about either this new formula for ~r, its proof, or the scheme just described to c o m p u t e hexadecimal digits of 7r using it. In fact, this same scheme can be used to compute binary (or hexadecimal) digits of log(2) based on the formula log(2) - k= 1 k2k' which has been k n o w n for centuries. Thus, it is astonishing that these methods have lain undiscovered all this time. Why shouldn't Euler, for example, have discovered them? The only advantage that today's researchers have in this regard is advanced computer technology. Table 3 gives some hexadecimal digits of ~- c o m p u t e d using the above scheme. One question that immediately arises is whether or not there is a formula of this type and an associated computa-

Hex digits beginning at this position 26C65E52CB4593

107

17AF5863EFED8D

108

ECB840E21926EC

10~

85895585A0428B

101o

921 C73C6838FB2

Fabrice Bellard tells us that he recently completed the computation of the 100 billion'th hexadecimal digit by this method, this gives:

16k(8k + 1) '

First observe that the hexadecimal digits of S~ beginning at position d + 1 can be obtained from the fractional part of 164 S~. Then we can write

+

Position

9C381872D27596F81 DOE...

tional scheme to compute individual decimal digits of ~-. Alas, no decimal scheme for ~r is k n o w n at this time, although there is for certain constants such as log(9/10)-see [2]. On the other hand, there is not yet any proof that a decimal scheme for ~- cannot exist. This question is currently being actively pursued. Based on some numerical searches using the PSLQ algorithm, it appears that there are no simple formulas for ~- of the above form with 10 in the place of 16. This, of course, does not rule out the possibility of completely different formulas that nonetheless permit rapid computation of individual decimal digits of ~-.

Why?. A value of ~r to 40 digits would be more than enough to compute the circumference of the Milky Way galaxy to an error less than the size of a proton. There are certain scientific calculations that require intermediate calculations to be performed to significantly higher precision than required for the final results, but it is doubtful that anyone will ever need more than a few hundred digits of ~rfor such purposes. Values of ~- to a few thousand digits are sometimes employed in explorations of mathematical questions using a computer, but we are not aware of any significant applications beyond this level. One motivation for computing digits of ~r is that these calculations are excellent tests of the integrity of computer hardware and software. This is because if even a single error occurs during a computation, almost certainly the fmal result will be in error. On the other hand, if two independent computations of digits of 7r agree, then most likely both computers performed billions or even trillions of operations flawlessly. For example, in 1986, a 7r-calculating program detected some obscure hardware problems in one of the original Cray-2 supercomputers [1]. The challenge of computing ~r has also stimulated research into advanced computational techniques. For example, some new techniques for efficiently computing linear convolutions and fast Fourier transforms, which have applications in many areas of science and engineering, had their origins in efforts to accelerate computations of ~-. Beyond immediate practicality, decimal and binary expansions of qr have long been of interest to mathematicians, who have still not been able to resolve the question of whether the expansion of 7r is normal [18]. In particular, it is widely suspected that the decimal expansions of 7r, e, V 2 , N / ~ , and many other mathematical constants all have the property that the limiting frequency of any digit is one-tenth, and the limiting frequency of any n-long string VOLUME19, NUMBER1, 1997 55

of decimal digits is 10 - n (and similarly for binary expansions). Such a g u a r a n t e e d p r o p e r t y could, for instance, be the basis of a reliable p s e u d o - r a n d o m - n u m b e r generator for scientific calculations. Unfortunately, this assertion has not been proven in even one instance. Thus, there is a continuing interest in performing statistical analyses on the expansions of t h e s e n u m b e r s to see if there is any irregularity that w o u l d m a k e t h e m look unlike r a n d o m sequences. So far, such studies of high-precision values of 7r have not disclosed any irregularities. Along this line, n e w formulas and s c h e m e s for computing digits of qr are of interest because they m a y suggest n e w a p p r o a c h e s to the normality question. Finally, t h e r e is a m o r e fundamental m o t i v a t i o n for computing ~-, the challenge, like that of a lofty m o u n t a i n or a major sporting event: "it is there." ~ is easily the m o s t fam o u s of the b a s i c c o n s t a n t s of mathematics. Every technical civilization h a s to m a s t e r ~-, and w e w o n d e r if it m a y be equally inevitable that s o m e o n e feels the challenge to raise the p r e c i s i o n of its computation. The c o n s t a n t ~- has r e p e a t e d l y s u r p r i s e d h u m a n i t y with n e w and u n a n t i c i p a t e d results. If anything, the discoveries of this century have b e e n even m o r e startling, with r e s p e c t to the p r e v i o u s state o f knowledge, t h a n t h o s e of p a s t centuries. We g u e s s from this that even m o r e s u r p r i s e s lurk in the depths of u n d i s c o v e r e d k n o w l e d g e regarding this fam o u s constant. ACKNOWLEDGMENT

The a u t h o r s wish to a c k n o w l e d g e helpful information from Yasumasa K a n a d a o f the University of Tokyo. REFERENCES

1. D. H. Bailey, The computation of pi to 29,360,000 decimal digits using Borweins' quartically convergent algorithm, Mathematics of Computation 42 (1988), 283-296. 2. D. H. Bailey, P. B. Borwein, and S. Plouffe, On the rapid computation of various polylogarithmic constants, (to appear in Mathematics of Computation). Available from http://www.cecm.sfu/personal/pborwein/. 3. P. Beckmann, A History of Pi, New York: St. Martin's Press (1971). 4. L. Berggren, J. M. Borwein, and P. B. Borwein, A Sourcebook on Pi, New York: Springer-Verlag (to appear). 5. J. M. Borwein and P. B. Borwein, Pi and the AGM- A Study in Analytic Number Theory and Computational Complexity, New York: Wiley (1987). 6. J. M. Borwein and P. B. Borwein, Ramanujan and pi, Scientific American (February 1987), 112-117. 7. J. M. Borwein, P. B. Borwein, and D. H. Bailey, Ramanujan, modular equations, and approximations to pi, or how to compute one billion digits of pi, American Mathematical Monthly 96 (1989), 201219. Also available from the URL http://www.cecm.sfu.ca/personal/ pborwein/. 8. R. P. Brent, Fast multiple-precision evaluation of elementary functions, Journal of the ACM 23 (1976}, 242-251. 9. D. Chudnovsky and C. Chudnovsky, personal communication (1995). 10. H. R. P. Ferguson and D. H. Bailey, Analysis of PSLQ, an integer relation algorithm, unpublished, 1996. 56

THE MATHEMATICALINTELLIGENCER

VOLUME 19, NUMBER 1, 1997

57

The Whitehead

Heritage ~ E

T

E

R

H

I

L

T

O

N

A

N

D

I

O

A

N

J

A

M

E

,'

he ninetieth anniversary of the birth of J.H.C. (Henry) Whitehead occurred in November 1994. Following his u n t i m e l y death 35 years ago, several accounts of his life and work were published; see References B. These give some idea of the m a n he was, his dedication to mathematics and his contributions to research in m a n y fields. The a n n i v e r s a r y p r o v i d e s a g o o d o p p o r t u n i t y to reflect on his achievements, particularly his influence on m a t h e m a t ics today. This is the principal p u r p o s e of this article. However, w e w o u l d also like to recall a very remarkable man. F o r although W h i t e h e a d ' s influence m u s t b e att r i b u t e d p r e d o m i n a n t l y to his d e e p m a t h e m a t i c a l insights, it is also u n d o u b t e d l y true that his c h a r a c t e r and p e r s o n ality w e r e strongly influential in attracting s o m e of the b e s t young mathematicians, British a n d otherwise, o f his d a y to his school. We will have m o r e to s a y a b o u t this in o u r concluding remarks, but w e w o u l d like to briefly r e m i n i s c e h e r e a b o u t Whitehead, the man. We w e r e b o t h students of Whitehead, b u t w e w e r e also f o r t u n a t e to count Whitehead as a p e r s o n a l friend. F o r one of us (PH), the friendship b e g a n b e f o r e our days as res e a r c h students. Whitehead a n d PH w e r e b o t h involved in the e n t e r p r i s e of decoding high-grade G e r m a n ciphers, at Bletchley Park; indeed, PH a r r i v e d in Bletchley P a r k a y e a r b e f o r e Whitehead, that is, in J a n u a r y 1942--so that a relationship n o t m e r e l y of collegiality b u t of close friendship grew, w h i c h w a s s u s t a i n e d after the w a r w h e n he w a s invited to b e c o m e Whitehead's r e s e a r c h student, in 1946. He even h a d t h e privilege o f living in Whitehead's h o m e in North Oxford, getting to k n o w his family, and learning at first h a n d w h a t was involved in doing m a t h e m a t i c a l re58

THE MATHEMATICALINTELUGENCER9 1997 SPRINGER-VERLAG NEW YORK

s e a r c h effectively. S o m e years later, the o t h e r a u t h o r (IJ) was similarly privileged to enjoy the W h i t e h e a d s ' hospitality w h e n t h e y h a d m o v e d out to the Oxfordshire countryside. In fact W h i t e h e a d w a s friendly with all his s t u d e n t s - to w h o m he w a s a l w a y s " H e n r y " - - a n d the p e r s o n a l relationships W h i t e h e a d e s t a b l i s h e d so easily u n d o u b t e d l y helped him to t r a n s m i t to t h e m the e s s e n c e o f his ideas and his intense e n t h u s i a s m for mathematics. His excellent relationships with o t h e r topologists e n s u r e d a s t e a d y s t r e a m of a c a d e m i c visitors to Oxford, a n d the s e m i n a r he s t a r t e d shortly after his return to Oxford from w a r w o r k remains as active today, inspired by the t r a d i t i o n he established, as it w a s during his lifetime.

Homotopy Theory As we have said, Whitehead w o r k e d in m a n y fields; b u t p r o b a b l y his g r e a t e s t contribution was to the d e v e l o p m e n t o f h o m o t o p y theory. Indeed, it might b e said that he pion e e r e d the evolution of the study of the h o m o t o p y relation in topology into a m a t u r e homotopy theory. In so doing, he showed, as in all his work, a r e m a r k a b l e c o m b i n a t i o n of deep insight a n d t e c h n i c a l power. As always, he s a w - - a n d d e v e l o p e d - - c o n n e c t i o n s bet w e e n t o p o l o g y a n d o t h e r p a r t s of m a t h e m a t i c s . Principally but, as we will show, certainly not exclusively, he l o o k e d

for algebraic invariants of h o m o t o p y type. He recognized that a c o m p l e t e set of algebraic invariants w o u l d be ext r e m e l y h a r d to obtain and e x t r e m e l y h a r d to use, so that t h e r e had to b e a trade-off b e t w e e n manageability on the one hand, a n d generality on the other. First, however, in the i n t e r e s t s of computability, the t o p o l o g i c a l s p a c e s s h o u l d a d m i t a c o m b i n a t o r i a l structure. To this end he i n t r o d u c e d the i d e a of a C W - s t r u c t u r e , a s t r u c t u r e m u c h m o r e general t h a n t h a t o f a simplicial complex, b u t having m a n y a d v a n t a g e s over that of a simplicial complex, while still leading to r e a d i l y a c c e s s i b l e chainc o m p l e x e s a n d h e n c e to h o m o l o g y groups. In t w o p a p e r s [A14] in 1949, he i n t r o d u c e d CW-complexes (C = closurefinite, W = w e a k topology) a n d s h o w e d their p o w e r and i m p o r t a n c e . Let us only m e n t i o n h e r e t h a t the n - s p h e r e has a n a t u r a l CW-structure with j u s t t w o cells (of dimensions 0 a n d n), w h e r e a s a simplicial d i s s e c t i o n o f S n as the b o u n d a r y of an (n + 1)-simplex requires (2 n+2 - 2) simplexes. Moreover, the chain g r o u p s (with integer coefficients) of a CW-complex K c o u l d b e r e p r e s e n t e d as the (singular) h o m o l o g y groups H n ( K n, I ~ ~ 1), with the n-cells constituting a basis, and the b o u n d a r y o p e r a t o r being the composite H n ( K n, K n - i )

~-~Tin 1(/~ -1) /-~ H n - ] ( K n - l , / ~ - 2 ) .

(1)

Here, 0 is c o m p u t e d by m e a n s of the attaching m a p s for the n-cells; c o r r e s p o n d i n g to each n-cell e n, there is a characteristic m a p h : D r', S n-1 --~ K n, K n-1 w h i c h is a relative h o m e o m o r p h i s m of D n - - S n 1 o n t o e n, and Oen is j u s t the h o m o l o g y class of h[S n- 1. The n o t i o n of CW-complex has n o w held s w a y a m o n g h o m o t o p y theorists for over 45 y e a r s - - a wonderful r e c o r d for the d o m i n a n c e o f an idea. We routinely a n n o u n c e in our p a p e r s that our s p a c e s will be a s s u m e d to be CW-complexes, or at least to have the h o m o t o p y type of CW-complexes. This enables us to t a k e a d v a n t a g e of the cell structure; b u t also it validates W h i t e h e a d ' s very p o w e r f u l r e a l i s a t i o n theorems. Thus, Whitehead s h o w e d in [A14] that if a m a p f of p o i n t e d , p a t h - c o n n e c t e d CW-complexes induces isomorp h i s m s of the h o m o t o p y groups, then it is a h o m o t o p y equivalence. Indeed, if f : X - - ) Y and X and Y are finitedimensional, it suffices to c h e c k t h a t f . : ~rrX ~- ~rr Yfor r -1, 2 , . . . , m a x ( d i m X + 1, dim Y). N o w w h a t is r e m a r k a b l e a b o u t this t h e o r e m is that the h o m o t o p y groups b y no m e a n s constitute a c o m p l e t e set of invariants of h o m o t o p y type; specialists in h o m o t o p y t h e o r y k n o w h o w to construct c o m p a c t CW-complexes o f different h o m o t o p y t y p e s having i s o m o r p h i c h o m o t o p y groups. The key to W h i t e h e a d ' s a r g u m e n t is that the i s o m o r p h i s m s of homot o p y groups should be g e o m e t r i c a l l y induced, i.e., i n d u c e d by a m a p of the s p a c e s concerned. A striking variant of this t h e o r e m is o b t a i n e d if one a d d s the condition t h a t X and Y be simply connected. Then one m a y r e p l a c e h o m o t o p y groups b y h o m o l o g y groups in the hypotheses. In a third variant, one d o e s n o t require simplec o n n e c t e d n e s s b u t one a s k s t h a t f i n d u c e an i s o m o r p h i s m o f f u n d a m e n t a l groups of X and Y and of the h o m o l o g y groups o f t h e i r u n i v e r s a l covers. It is n o t e w o r t h y that it is

not sufficient to require that f induce an i s o m o r p h i s m of fundamental groups a n d h o m o l o g y groups of X a n d Y. In fact, Whitehead had p r o v e d s o m e related results earlier [A13], before he p r e s e n t e d the c o n c e p t of a CWcomplex; in the earlier version he had c o n s i d e r e d s p a c e s d o m i n a t e d by ANRs (absolute n e i g h b o r h o o d r e t r a c ~ ) . However, the later c o m b i n a t o r i a l setting for his realisability t h e o r e m s p r o v e d far m o r e congenial a n d serviceable because the rich structure of his c e l l - c o m p l e x e s m a d e t h e m so useful and easy to handle. As we have said, the h o m o t o p y groups o f a CW-complex do not t h e m s e l v e s d e t e r m i n e its h o m o t o p y type. To do this, a far m o r e c o m p r e h e n s i v e set of algebraic invariants is required. However, b y restricting the CW-complexes one might be able to require less. Whitehead p r o d u c e d , in 1949, a r e m a r k a b l e p a p e r [ A l l ] , in which he gave a c o m p l e t e (finite) set of c o h o m o l o g y invariants for simply-connected, compact, 4-dimensional CW-complexes. When Whitehead i n f o r m e d Hassler Whitney of this result, the latter is rep o r t e d to have b e e n at first highly sceptical, n o t believing t h a t such a relatively simple system could p o s s i b l y suffice. Whitehead also p u b l i s h e d [A21] a few y e a r s later the solution of the m o r e general p r o b l e m for (n - 1)-connected, compact, (n + 2)-dimensional CW-complexes [A15]. This solution, with n -> 3, is, in fact, even s i m p l e r than that of the original problem, since n o w one is in the stable range for the h o m o t o p y g r o u p s concerned, and s o m e v e r y delicate, unstable c o h o m o l o g y o p e r a t i o n s w h i c h e n t e r into the d e s c r i p t i o n w h e n n = 2 are simply r e p l a c e d b y the S t e e n r o d square if n -> 3. This p r o g r a m o f r e s e a r c h is currently being c o n t i n u e d u n d e r the l e a d e r s h i p of Baues [C1]. Whitehead was also r e s p o n s i b l e for introducing n e w algebraic invariants into h o m o t o p y theory. In 1941, in a very significant p a p e r [A12] in which he d i s c u s s e d the effect on the h o m o t o p y groups o f attaching a cell to a s p a c e X, he i n t r o d u c e d a binary o p e r a t i o n n o w universally k n o w n as the Whitehead product. We will give here a d e s c r i p t i o n of this o p e r a t i o n m o r e c o n s i s t e n t with the c u r r e n t p o i n t of view. One m a y r e g a r d the p r o d u c t s p a c e of t w o spheres, S ~ x S ~, as f o r m e d from the union S ~ V S ~ (with b a s e point identified) b y the a t t a c h m e n t of an ( m + n)-cell e m+n. Thus, there is a relative h o m e o m o r p h i s m D TM X D n, D TM X S n - 1 U S m - 1 X D n ---e S m X S n, S m V S n,

w h i c h is j u s t the p r o d u c t m a p km X kn, w h e r e kq pinches the b o u n d a r y of the q-ball Dq to a point. The b o u n d a r y of D m X D n is topologically the s p h e r e S re+n-l, and the restriction of km x kn to the b o u n d a r y is the u n i v e r s a l W h i t e h e a d p r o d u c t m a p Wm,n : S r e + n - 1 --->S m V S n. Now, given a E ~m(X), a n d fl E ~r,~(X), w e m a y m a p S ~ V S ~ ---) X b y mapping I Svn b y a and S n by/3. Then the c o m p o s i t i o n with Wm,n yields a m a p S re+n-1 --~ X w h i c h w e write [a,/3] and call the W h i t e h e a d p r o d u c t of a and/3. One m a y s h o w that [a, /3], for m , n -> 2, is bilinear, c o m m u t a t i v e (in the g r a d e d sense), and (again in the graded s e n s e ) satisfies a J a c o b i identity. It is also closely c o n n e c t e d to the m o d e m lit is standard practice to confuse maps and their homotopy classes. VOLUME 19, NUMBER 1, 1997

59

generalised version of the Freudenthal suspension [C3], for the Whitehead product is highly unstable in that it is killed by suspension; indeed, often the kernel of the suspension consists entirely of Whitehead products. It is also significant that the Whitehead product vanishes in any H-space (space with continuous multiplication with two-sided identity). Finally, let us mention that the Whitehead p r o d u c t is the only universally defined operation on h o m o t o p y groups, apart from the obvious compositions. Not all these facts were known to Whitehead; but they testify to his remarkable insight in discovering this product. Another of Whitehead's important discoveries was the exact homotopy sequence. He did not invent exact sequences; moreover, the exact homology sequence of a pair of spaces antedated the h o m o t o p y sequence. But Whitehead wrote d o w n quite explicitly the six inclusions involved in the statement of the exact sequence and proved them in Theorem 13 of a paper published during the Second World War [A10], whose title "On the Groups ~rr(Vn,m) and SphereBundles" did not guarantee it would be a best-seller. Whitehead was extremely adept, and enormously conscientious, in using the work of others. He espoused the principle that he would not use any result he could not himself prove. One effect of this self-discipline was that, in the process of gaining a complete understanding, he was often able to improve on the original statement of the result. A very good example of this was his improvement of Papakyriokopoulos's statement and proof of the sphere theo r e m - - s e e item (f) later in the article and [A25]. A second example was his mastery of the Freudenthal suspension theorem, which led to his o w n generalised formulation [A17] prescribing conditions under which the characteristic map for an n-cell induces an isomorphism of relative hom o t o p y groups 7rr(Dn, S n-l) ~ 7~r(ZU e n, Z). The ordinary Freudenthal theorem is recovered by taking X to be a point. A third example was his m u c h simplified view of the important Cartan-Serre-Whitehead invariants. Suppose t h a t X i s (n - 1)-connected. By first attaching (n + 2)-cells, then (n + 3)-cells, and so on, one may embed X in a space Y which has the nth h o m o t o p y group of X but no other hom o t o p y groups. Thus, Y is an Eilenberg-MacLane space, specifically, Y = K(~nX, n), and the embedding X ~ Yrepresents an element in the c o h o m o l o g y group Hn(x; ~'nX). This element is the required invariant. Unfortunately, this little gem was buried in a paper [A20] with the forbidding title "The G-dual of a Semi-exact Couple." There is much more to tell. A notable omission from our story is [A18], which Whitehead titled laconically "A Certain Exact Sequence." In this paper, he introduced the F-groups, destined to play a key role in both algebra and topology. But we must leave space to deal, however inadequately, with one of his most important contributions outside the mainstream of h o m o t o p y theory.

Simple Homotopy Theory Early in his career, Whitehead was very much attracted to the H a u p t v e r m u t u n g (= main conjecture) of t o p o l o g y - are two homeomorphic combinatorial manifolds combinatorially equivalent? (This question was finally answered by ~I~

THE MATHEMATICALINTELLIGENCER

Kirby and Siebenmann in the negative). Both he and Max Newman, his mentor at this early stage of his work, were inspired in m u c h of their work before the war by this problem. Newman has said that Whitehead was led to invent simple homotopy theory (don't let the w o r d "simple" fool you!) by his attempt to study the corresponding problem in h o m o t o p y t h e o r y - - i f two finite simplicial complexes have the same h o m o t o p y type, can one be transformed into the other by a sequence of allowed combinatorial moves? Whitehead showed, first in [A9] and then, after the war, in a much more algebraic version [A16], in which he was also able to incorporate his new combinatorial models, the CWcomplexes, that the answer was, in general, negative. There is a single obstruction, located in a group depending on the fundamental group ~rl (which, of course, two polyhedra of the same h o m o t o p y type share), and n o w always referred to as the Whitehead group of 7;-1,written Whitehead 7;"1. We will describe its construction below. Thus, if f : X--) Y is a h o m o t o p y equivalence, there is an obstruction ~ ( f ) , located in Whitehead ~rl, t o f being a simple h o m o t o p y equivalence; that is, a finite composition of maps corresponding to allowed combinatorial moves. In fact, f is a simple homotopy equivalence if and only if v ( f ) = 0; we call ~ ( f ) the Whitehead torsion of f (see [C4]). These ideas of Whitehead helped to inspire the Wall obstruction to f i n i t e ness [C6,C7]. Whitehead described the group which n o w bears his name as follows. We consider the general linear group GL(~_Tr, n), where ;77r is the integral group ring of the group 7r. There are then natural embeddings GL(~_Tr, n) C_ GL(~_Tr, n + 1), enabling us to define the inductive limit GL(77r). We pass to the abelianization and factor out diagonal matrices with _+ (group elements) on the diagonal. The result is Whitehead ~r. It is immediately striking that Whitehead is adopting a construction very close to that used much later in algebraic K-theory to build K1ZTr. Eckmann and Maumary [C2] gave, in 1970, a beautiful way of looking at simple h o m o t o p y theory which would surely have delighted Whitehead had he lived to read it. We will reproduce their approach, briefly, here. Let Y be obtained from X by attaching an n-cell e n and an (n + 1)-cell en+l in the following sense. Let us suppose given an (n + 1)-ball D n+l with boundary sphere divided into two hemispheres D~ and Dn-, with equator S ~- 1. There is then a map ~b : D n+l --~ Ysuch that ~bD~ C X n and r n-1 C X n-l, d)IDn+l is a h o m e o m o r p h i s m onto e n+l, &IDn_ is a h o m e o m o r p h i s m onto e n (see Fig. 1). We then say that Y is an elementary e x p a n s i o n of X with associated (simple) equivalence the inclusion i : X ~ Y; and X is an elementary contraction of Y with associated (simple) equivalence the retraction r : Y---) X. A map s : X ~ X', which is a finite composition of such elementary expansions and contractions, is a simple equivalence; thus far we have not departed from Henry's o w n development of the theory. We now construct a commutative group E(X), as follows. Consider maps f : X---) Y, where Y can be any finite CW-complex of the same h o m o t o p y type as X, and f is a cellular h o m o t o p y equivalence. Declare two such maps f : X---) Y and g : X---~ Z to be "equivalent" if there exists a

simple equivalence s : Y--+ Z such that sf = g. Let E(X) be the set of all such equivalence classes. The "sum" (f} + (g} of two such equivalence classes is defined to be the equivalence class of the inclusion X C M, where M is the "double mapping cylinder"; that is, the union of the mapping cylinder o f f and the mapping cylinder of g, pasted together along their common subset X. With this definition, Eckmann and Maumary show that E(X) is a commutative group, naturally isomorphic to the Whitehead group Whitehead ~'1 (X). Some Further Contributions We now describe briefly some of Whitehead's other major contributions, all of which continue to be of current interest and importance; for a fuller discussion, see [B3]. Our purpose here is to show his remarkable combination of breadth, depth, and insight. (a) In two papers published in 1936 [A3, A4], Whitehead described certain systems of generators of a free group. This work is currently attracting considerable interest not only among group-theorists but also among theoretical computer scientists. The whitehead transformations have been used by the latter in studying rewriting systems; see, for example, [C5]. (b) whitehead formulated a famous conjecture on 2dimensional complexes: a 2-dimensional subcomplex of a 2-dimensional aspherical complex is asphericai. Inspired by his work on adding relations to homotopy groups [A8], we would reformulate the conjecture as follows: one cannot render a nonaspherical 2-dimensional complex aspherical by attaching 2-cells. This conjecture remains open and is one of the main topics discussed in the London Mathematical Society Lecture Notes Volume 197 (1994). (c) whitehead [A2, A5] proved two famous and fundamental lemmas in the cohomology of Lie algebras (known as the two Whitehead lemmas). Letg be a finite-dimensional semisimple Lie algebra and let A be a finite-dimensional gmodule. Then H1Cq; A) = H 2 ( g ; A ) = 0. From these lemmas follows, for example, the following theorem of Levi-Malcev: Every fmite-dimensional Lie algebra g is the split extension of a semisimple Lie algebra by the radical (unique maximal solvable ideal) of g. (d) In collaboration with Stuart Cairns, whitehead pioneered research into the problem of introducing differentiability into combinatorial topological structures. In 1940 he published a paper [A7] on Cl-complexes: a Cl-triangu -

lation of a manifold M is a simplicial triangulation in which each closed simplex embeds in M by a nondegenerate C 1map. Whitehead, of course, participated in the renaissance of differential and geometric topology which started in the early 1950s. (e) Whitehead introduced in an early paper [A6] the idea of regular neighbourhood and showed that every complex embedded in a manifold M has regular neighbourhoods in M. This idea was taken up, in the 1950s, by many topologists in the renaissance of geometric topology. In particular, his regular-neighbourhood theorem allows one to fmd a manifold (with boundary) in the homotopy type of any polyhedron. (t) Almost a century ago, Poincar6 made his celebrated conjecture to the effect that a simply-connected three-dimensionai compact manifold must be a sphere. Since that time, numerous purported proofs have been announced, but the conjecture remains open. Whitehead at one time thought he had a proof [All but he retracted it not long afterward. However, the many investigations he made in this area led to some of the cornerstones of geometric topology, such as the sphere theorem to the effect that an orientable three-dimensionai manifold with nontriviai second homotopy group contains an embedded 2-sphere. (g) The Whitehead link (see Fig. 2) is a famous example in knot theory, constituting a nontrivial link where each component is contractible in the complement of the other. There has been a great deal of renewed interest in knot theory in recent years, largely due to its relevance to particle physics and developmental biology. (h) Whitehead collaborated with Edwin Spanier in the creation of S-theory, which they described as "a first approximation to homotopy theory" [A19]: this is usually called stable homotopy theory nowadays. The (generalized) Freudenthal suspension provides a function S : IX, Y] --) [SX, Sty, where IX, Y] is the set of pointed homotopy classes of pointed maps from X to Y. Moreover, [SX, SI~ is a group, [S2X, S2y] is an abelian group, and S : [SX, SI~ --) [S2X, S2y] is a homomorphism. Thus, we may form the direct limit under S, which we write {X, Y}. This is an abelian group "approximating" [X, Y]; it is much easier (but not easy!) to study than [X, II]. A particular feature of the theory Spanier and Whitehead developed was the duality. A fmite CW-complex X may be embedded in a sphere of sufficiently high dimension. Its complement in such a sphere then has a uniquely determined S-type, which is def'med to be the dual of the S-type of X; see [A23] and [A24].

VOLUME 19, NUMBER 1, 1997

61

Concluding Remarks Of the topologists who were active in the United Kingdom before the Second World War it is u n d o u b t e d l y Whitehead who has had the greatest influence. We have already described the direct influence of his work, b u t the indirect influence is no less important. Graham Higman, his only pre-war research student, is himself the head of a n "invisible college" in algebra of over 100 students, grad students, a n d so on. There are at least as m a n y again in the more topological college which goes b a c k to the group of research s t u d e n t s Whitehead gathered around him after the Second World War, including the authors of this article. Members of this college include such leading researchers as Simon Donaldson and Mike Hopkins, neither of w h o m could have k n o w n Whitehead b u t who may well be described as students of his, several times removed. Whitehead died in P r i n c e t o n early in May 1960, so that his professional career lasted barely 35 years. Although it is hardly possible to convey a clear idea of what he was

like as a m a n to those who did not have the privilege of knowing him, p e r h a p s something of his personality appears in a letter which one of us (IJ) received from him just a few weeks before his death. After c o m m e n t i n g on some news from Oxford he wrote: The last 6 weeks have been very good for me mathematically. I have written 2 papers, including a draft of a collaborative paper with Chris Zeeman and Roger Penrose. The latter (on imbedding) arose out of a conversation after an LMS dinner which you may remember. I think it is good and the experts here are quite excited about it. Most of the young people who impress me most--and there are a lot of them--are interested in smooth manifolds, regular neighbourhoods, simple homotopy types and all these things, some old, some new, which lie so near my heart. It is immensely invigorating! It is a long time since I heard anyone refer to a CSS complex! On Friday I am going to start a course of 4 lectures on simple homotopy types and it seems likely that a lot of people will attend. Will you tell Bill Browder that the lessons in poker that I had in Chicago have proved valuable. Dan Hughes paid us a visit and organized a game (hours of play 9:00 p.m. till 7:30 a.m., but only the next morning*I) and I won about $125. I was the only winner out of 5--most satisfactory! Poor Dan lost $90. I have been working very hard and have had some gay parties. But I confess that, when the pressure eases off, I feel very homesick. Best wishes, Henry. *i.e., we only played for 101, not 34~ or 5889hours. REFERENCES A: Partial I.Ist of Whitehead Publications

1. Certain theorems about three-dimensional manifolds (I), Quart. J. Math. (2) 5 (1934), 308-320. 2. On the decomposition of an infinitesimal group, Proc. Camb. Phil. Soc. 32 (1936), 229-237. 3. On certain sets of elements in a free group, Proc. London Math. Soc. (2) 41 (1936), 48-56. 4. On equivalent sets of elements in a free group, Ann. Math. (2) 37 (1936), 782-800. 5. Certain equations in the algebra of a semi-simple infinitesimal group, Quart. J. Math. (2) 8 (1937), 220-237. 6. Simplicial spaces, nuclei and m-groups, Proc. London Math. Soc. (2) 45 (1939), 243-327. 7. On Cl-complexes, Ann. Math. (2) 41 (1940), 809-824. 8. On adding relations to homotopy groups, Ann. Math. (2) 42 (1941), 409-428. 9. On incidence matrices, nuclei and homotopy types, Ann. Math. (2) 42 (1941), 1197-1239. 10. On the groups ~rr(Vn,m)and sphere-bundles, Proc. London Math. Soc. (2) 48 (1944), 243-291. 11. On simply-connected 4-dimensional polyhedra, Commen. Math. Helv. 22 (1949), 48-92. 12. Note on a theorem due to Borsuk, Bull. Amer. Math. Soc. 54 (1948), 1125-1132. 13. 9 the homotopy type of ANR's, Bull. Amer. Math. Soc. 54 (1948), 1133-1145. 14. Combinatorial homotopy, Bull. Amer. Math. Soc. 55 (1949), Part I 213-245; Part II 453-496. 15. The homotypy type of a special kind of polyhedron, Ann. Soc. Polonaise Math. 21 (1948), 176-186. 62

THE MATHEMATICALINTELLIGENCER

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

23. 24. 25.

Simple homotopy types, Amer. J. Math. 72 (1950), 1-57. Note on suspension, Quart. J. Math. (2) 1 (1950), 9-22. A certain exact sequence, Ann. Math. (2) 52 (1950), 51-110. (with E. Spanier) A first approximation to homotopy theory, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 655-660. The G-dual of a semi-exact couple, Proc. London Math. Soc. (3) 3 (1953), 385-416. On the (n + 2)-tuple of an (n - 1)-connected complex (n -> 4), Proc. London Math. Soc. (3) 4 (1954), 1-23. (with E. Spanier) The theory of carriers and S-theory, Algebraic Geometry and Topology, Princeton, NJ: Princeton University Press, 1957, pp. 329-360. (with E. Spanier) Duality in homotopy theory, Mathematika 2 (1955), 56-80. (with E. Spanier) Duality in relative homotopy theory, Ann. Math. (2) 67 (1958), 203-238. On finite cocycles and the sphere theorem, Colloq. Math. 6 (1958), 271-281.

B: C o m m e n t a r i e s on W h | t e h e a d ' s Life and W o r k

1. P.J. Hilton, Memorial tribute to J.H.C. Whitehead, Enseignement math6matique 7 (1961), 107-125. 2. I.M. James, Reminiscences of a topologist, Mathematical Intelligencer 12 (1) (1960), 50-55. 3. J.W. Milnor, The work of J.H.C. Whitehead, The Mathematical Works of J.H.C. Whitehead, New York: Pergamon Press, 1962, pp. xxi-xxxiii. 4. M.H.A. Newman, John Henry Constantine Whitehead, Biogr. Mem. Roy. Soc. 7 (1961), 349-363. 5. M.H.A. Newman and B. Whitehead, A biographical note, The Mathematical Works of J.H.C. Whitehead, New York: Pergamon Press, 1962, pp. xv-xix. 6. S. Wylie, John Henry Constantine Whitehead, J. London Math. Soc. 37 (1962), 257-273.

C: Other Publications Cited

1. H.J. Baues and M. Hennes, The homotopy classification of (n - 1)connected (n + 3)-dimensional polyhedra, n --- 4. Topology 30 (1991), 373-408. 2. B. Eckmann and S. Maumary, Le groupe des types simples d'homotopie sur un polyedre, Essays on Topology and Related Topics (M#moires d~dies ~ George de Rham), New York: Springer-Vertag, 1970, pp. 173-187. 3. H. Freudenthal, Uber die Klassen der Sph&renabbildungen, Compositio Math. 5 (1937), 299-314. 4. J. Milnor, Whitehead torsion, Bull. Amer. Math. Soc. 72 (1966), 358-426. 5. C. Squier, A finiteness condition for rewriting systems, J. Theoret. Computer Sci. 131 (1994), 27"1-294. 6. C.T.C. Wall, Finiteness conditions for CW-complexes, Ann. Math. (2) 81 (1965), 55-69. 7. C.T.C. Wall, Finiteness conditions for CW-complexes II, Proc. Roy. Soc. London Ser. A 295 (1966), 129-139.

VOLUME 19, NUMBER 1, 1997

63

Fermat's Last

Theorem and Hilbert's

Program 1 )

A

N

I

E

L

J

V

E

L

L

E

M

A

ost mathematicians are aware of the controversies in the foundations of mathematics that occurred earlier in this century: the de~

n

bate between the logicists and the intuitionists, and Hilbert's proposal of a program that he hoped would resolve the issue. But the

controversies have died d o w n since then, and few mathematicians w o r r y about these issues anymore. The r e c e n t exc i t e m e n t over the p r o o f of F e r m a t ' s Last T h e o r e m p r o v i d e s an o p p o r t u n i t y to r e e x a m i n e t h e s e issues, b e c a u s e Wiles's p r o o f is an excellent e x a m p l e of precisely the kind of mathematics that Hilbert h o p e d to justify with his program. It is often r e m a r k e d that the s t a t e m e n t of F e r m a t ' s Last T h e o r e m is conceptually v e r y simple. P e r h a p s less widely r e c o g n i z e d is that it is also logically quite simple. If one w r i t e s it with all the quantifiers at the beginning (in w h a t is k n o w n as p r e n e x f o r m ) , all of t h e s e quantifiers are universal: The t h e o r e m says that f o r all positive integers x, y, z, and n, if n is greater than 2 t h e n x n + yn # z n. Logicians call s t a t e m e n t s of this kind II1 s t a t e m e n t s . B e c a u s e the

s t a t e m e n t has this simple form, it can be thought of as making a p r e d i c t i o n a b o u t the o u t c o m e s of certain calculations: If one c h o o s e s any positive integers x, y, z, a n d n with n > 2 and c o m p u t e s x n + yn and z n, the results will be different. It is of c o u r s e straightforward to p e r f o r m these calculations to c h e c k any p a r t i c u l a r instance o f F e r m a t ' s Last Theorem. The c o n t e n t of F e r m a t ' s Last T h e o r e m is thus, in a sense, directly observable, in a w a y that m a n y o t h e r t h e o r e m s are not. The t h e o r e m says no m o r e n o r less than that if certain finite calculations are p e r f o r m e d , certain results will b e achieved. 2 Of course, the t h e o r e m m a k e s p r e d i c t i o n s a b o u t infinitely m a n y such calculations, so the truth o f the t h e o r e m cannot be e s t a b l i s h e d by simply p e r f o r m i n g the calcula-

41 would like to thank Alexander George, Faan Tone Liu, Joseph Moore, and David Velleman for helpful comments on earlier drafts of this paper. 2In his paper "On the infinite" (in Paul Benacerraf and Hilary Putnam, Philosophy of Mathematics: Selected Readings, 2nd ed., Cambridge: Cambridge University Press, 1983, pp. 183-201, a translation of "0ber das Unendliche," Math. Annalen 95 (1926), 161-190), Hilbert makes a distinction between what he calls finitary statements and infinitary, or ideal statements. According to Hilbert, finitary statements are meaningful; infinitary statements are not meaningful, but are useful in deriving finitary statements in the same way that, for example, the imaginary number i is sometimes useful in deriving facts about the real numbers. He describes mathematics as "a stock of two kinds of formulas: first, those to which the meaningful communications of finitary statements correspond; and, secondly, other formulas which signify nothing and which are the ideal structures of our theory" (p. 196, italics original). Although Hilbert was not very precise about where the line between finitary and infinitary should be drawn, it appears that he would have considered Fermat's Last Theorem to be a finitary statement. Certainly each instance of the theorem is a finitary statement, and the theorem itself can be thought of as just a shorthand way of asserting all of its instances. Hilbert considered such a statement to be "a hypothetical judgment which asserts something for the case when a numerical symbol is given" (p. 194). In the case of Fermat's Last Theorem, four numerical symbols must be given-namely, numerals to be substituted for x, y, z, and n. 64

THE MATHEMATICALINTELLIGENCER9 1997 SPRINGERVERLAGNEW YORK

tions. This is why a proof was needed. And Wiles has n o w provided such a proof, thus settling the matter. But does Wiles's proof really settle the matter? Of course, there could still be a mistake in the proof, despite the extensive scrutiny the p r o o f has received from many mathematicians, but this is not my concern here. Let us grant the correctness of Wiles's proof. My question is, does the existence of a mathematically correct proof guarantee that the theorem is true? Does it guarantee that, if we continue to perform the calculations involved in checking instances of the theorem, we will never find a counterexample? Most mathematicians will surely consider this to be a silly question. If the p r o o f is correct then the theorem must be true, and if the theorem is true then checking instances will never result in the discovery of a counterexample. But let us examine more closely our reasons for believing this. Although the concepts involved in the s t a t e m e n t of Fermat's Last Theorem are quite simple, the concepts involved in Wiles's p r o o f are not nearly so simple. If Wiles's p r o o f referred only to the positive integers, and made use of only elementary properties of these integers such as Peano's axioms, it would be more difficult to imagine that there could be any reason to doubt the reliability of the proof. But in fact the proof involves not only the positive integers, but also real numbers, complex numbers, sets of such numbers, functions between such sets, and so on. These concepts are all far more complex than the positive integers. For example, even a single real number is, in a sense, infinitely complex, since it takes infinitely many digits of a decimal expansion to specify it precisely. The set R contains uncountably many of these infmitely complex numbers. Are we really sure that reasoning with such complex concepts can be trusted to yield accurate predictions about the o u t c o m e s of calculations involving positive integers?

The most straightforward way to try to justify the reasoning in proofs like Wiles's 3 is to give careful definitions of all the concepts involved, and then try to establish that, when the statements in the p r o o f are interpreted according to these definitions, they can all be derived using valid rules of deductive logic and must therefore all be true. Since the statement of Fermat's Last Theorem is the l~ast statement of Wiles's proof, this would establish that the theorem is true. This was the approach used by the logicists, including Frege, Russell, and Whitehead, in their attempt to provide a foundation for mathematics. 4 But today most people regard the logicist program as being at best only partially successful. As a result of the w o r k of the logicists we can say that all concepts of mathematics can be def'med from the single undef'med concept set, and all theorems of mathematics can be deduced from a simple system of axioms about sets. The most widely used axiom system for set theory is the Zermelo-Fraenkel system, usually abbreviated ZF. But this still leaves open the question of the meaning of the w o r d "set" and the truth of the ZF axioms. Must we believe in the existence of the universe of all sets, and the truth of the ZF axioms for this universe, to be convinced that Wiles's p r o o f can be trusted? 5 There have been many mathematicians who would not have been willing to accept indiscriminate use of ZermeloFraenkel set theory to establish the truth of Fermat's Last Theorem. Certainly Brouwer 6 would not have, nor would Weyl. 7 Perhaps less well-known among mathematicians is the fact that Lebesgue, Borel, and Baire questioned the correctness of certain kinds of reasoning that are accepted today, such as nonconstructive existence proofs. 8 It was precisely to defend proofs like Wiles's against such worries that Hilbert p r o p o s e d his foundational program. 9 Hilbert's great insight was to recognize that there was another way to establish the reliability of proofs like Wiles's. To see h o w this could be done, imagine what it

3By "proofs like Wiles's" I mean proofs in which reasoning involving infinitary statements is used to justify a finitary conclusion. (See note 2 for the meanings of these terms.) 4See, for example, Frege's The Foundations of Arithmetic: A Iogico-mathematical enquiry into the concept of number (Oxford: Blackwell, 1950, a translation of Die Grundlagen der Arithmetik: Eine Iogisch-mathematische Untersuchung Ober den Begriff der Zahl, Breslau: Koebner, 1884), or Russell and Whitehead's Principia Mathematica, 2nd ed. (Cambridge: Cambridge University Press, 1925-1927). 5Because of the use of concepts that go beyond the positive integers, it appears unlikely that Wiles's proof can be formalized using Peano's axiom system for arithmetic, usually abbreviated PA. It certainly can be formalized in ZF, but the full strength of ZF is not needed for the proof. Most likely the proof can be carried out in a formal system intermediate in strength between PA and ZF. A number of such systems have been studied; for example, see Solomon Feferman's paper "Theories of finite type related to mathematical practice" (in Jon Barwise, ed., Handbook of Mathematical Logic, Amsterdam: North-Holland, 1977, pp. 913-971). It would be an interesting project to determine exactly what axioms are needed for Wiles's proof. However, as far as I know this project has not yet been carried out. Furthermore, my concern in this paper is not so much with Wiles's proof itself, but rather with the use of infinitary reasoning in mathematics in general, Wiles's proof being a particularly striking and interesting example. Thus, for the purposes of this paper I will continue to refer to ZF. 6Brouwer was the founder of intuitionism. In his paper "lntuitionism and Formalism" (Bulletin of the AMS 20 (1913), pp. 81-96, reprinted in Benacerraf and Putnam, pp. 77-89) he writes: "In the domain of finite sets in which the formalist axioms have an interpretation perfectly clear to the intuitionists, unreservedly agreed to by them, the two tendencies differ solely in their method, not in their results; this becomes quite different however in the domain of infinite or transfinite sets, w h e r e . . , the formalist introduces various concepts, entirely meaningless to the intuitionist." As a result, he concludes that "extended fields of research, which are without significance for the intuitionist are still of considerable interest to the formalist." 7See Weyl's The Continuum: A Critical Examination of the Foundation of Analysis (New York: Dover, 1987, a translation of Das Kontinuum: Kritische Untersuchungen [~ber die Grundlagen derAnalysis, Leipzig: Veit, 1918). In the preface Weyl writes that "the house of analysis.., is to a large degree built on sand. I believe that I can replace this shifting foundation with pillars of enduring strength. They will not, however, support everything which today is generally considered to be securely grounded. I give up the rest, since I see no other possibility" (p. 1). 8For example Lebesgue, in a letter to Borel, writes: "1 believe that we can only build solidly by granting that it is impossible to demonstrate the existence of an object without defining it" (italics original). This letter is part of an exchange of letters among Lebesgue, Borel, Baire, and Hadamard that was published in Bulletin de la Societe Mathematique de France, vol. 33 (1905), pp. 261-273. The quotation above is from an English translation that can be found in Appendix 1 of Gregory Moore's book Zermelo's Axiom of Choice: Its Origins, Development, and Influence, New York: Springer-Verlag, 1982. VOLUME 19, NUMBER1, 1997 65

Theorem were false then such an arrangement of symbols would mean if, despite the correctness of Wiles's proof, a could not exist. Displaying the arrangement of symbols counterexample to Fermat's Last Theorem were found. The would thus establish the truth of the theorem. Although counterexample could be confirmed by a finite calculation, this proof would probably be regarded by mathematicians and this calculation would then be a proof that Fermat's as less interesting or informative than Wiles's proof, the Last Theorem was false. The calculation, together with objects discussed in this proof--finite arrangements of Wiles's proof, would therefore constitute a contradiction symbols--would be conceptually simpler than the numin ZF. Thus, if we only knew that such a contradiction could bers, sets, and functions used in Wiles's proof. In fact, by not occur--in other words, if we knew that ZF was conusing G6del's method of assigning numbers to finite s i s t e n t - - t h e n we could be sure, based on Wiles's proof, arrangements of symbols, the reasoning about arrangethat no counterexample to Fermat's Last Theorem would ments of symbols in this proof could be replaced by reaever be found. Hilbert's insight was to recognize that we soning about natural numbers. Thus, Hilbert's program need not believe the ZF axioms to be true, or even meanwould have shown that, although the use of complex mathingful, to be convinced by the proof. We need only believe ematical objects might be helpful in proving Fermat's Last the axioms to be consistent. Theorem, talk about such objects could always in princiIn fact, consistency of the axioms would appear to be ple be eliminated from any proof in favor of reasoning that not only sufficient to guarantee the reliability of proofs in refers only to natural numZF, but also necessary. After all, bers. 11 if the axioms were inconsistent D o e s a m a t h e m a t i c a l l y correct Of course, today we know, by then all statements, both true proof guarantee that w e will n e v e r G6del's Second Incompleteness and false, would be provable Theorem, that such a consisfrom the axioms. In this case find a c o u n t e r e x a m p l e ? tency proof cannot be found. In the existence of a proof of fact, if ZF is consistent, then even using the full resources Fermat's Last Theorem in ZF would establish nothing about of ZF it is not possible to prove the consistency of ZF. the theorem's truth. This raises an interesting question: Should we say that Hilbert's program, then, was to establish the reliability what Wiles has established is not that Fermat's Last of proofs like Wiles's by proving the consistency of a sysTheorem is true, but rather that i f ZF is consistent then tem of axioms for mathematics, to One might wonder at this Fermat's Last Theorem is true? 12 Hilbert's program, had it point what such a proof would accomplish. After all, if been successful, would have allowed us to remove the qualWiles's proof cannot to be trusted, why should we trust the ification about consistency. Does the failure of his program consistency proof?. But note that the concepts involved in mean that the qualification must be maintained? consistency are quite simple. Logicians define proofs to be It might be thought that the consistency of ZF is suffifinite arrangements of symbols satisfying certain easily ciently well-established that it is not worth worrying about. checkable conditions, far simpler than the infinitely comAfter all, mathematicians have been working with ZF for plex real numbers of Wiles's proof. Consistency means the most of this century, and no contradictions have been disnonexistence of two such proofs establishing opposite concovered yet. But remember, millions of cases of Fermat's clusions. It is reasonable to hope that a proof of the nonexLast Theorem had already been established by direct comistence of such a contradiction might be found using only putation before Wiles wrote his proof. The mathematics simple finite combinatorial reasoning that would be concommunity still felt that a proof was needed, not to invincing even to those who might question Wiles's proof. crease our confidence in the theorem, but to establish it This was Hilbert's hope. with certainty. Even if we believe that ZF is very likely to Here's another way of looking at Hilbert's idea. If the be consistent, it is still reasonable to ask whether Wiles's desired consistency proof could be found, it would also proof establishes with certainty that Fermat's Last provide us with a new, conceptually simpler proof of Theorem is true, or merely that the truth of the theorem Fermat's Last Theorem. Much of the proof would look exfollows from the consistency of ZF. actly like Wiles's proof, but it would be interpreted differIt is not uncommon in set theory to include the consisently. Rather than regarding Wiles's proof as a meaningful tency of ZF as a hypothesis in a theorem. For example, in discussion of complex concepts, we would simply regard 1963 Cohen proved that the continuum hypothesis is not it as an arrangement of symbols of a certain special kind. provable in ZF, but his proof required the assumption of The consistency proof would show that if Fermat's Last

9In "On the infinite", Hilbert lists two goals for his program. The first is very famous: "Wherever there is any hope of salvage, we will carefully investigate fruitful definitions and deductive methods . . . . No one shall drive us out of the paradise which Cantor has created for us." However, the second gives a more specific description of what he hoped to accomplish: "We must establish throughout mathematics the same certitude for our deductions as exists in ordinary elementary number theory, which no one doubts and where contradictions and paradoxes arise only through our own carelessness~' (p. 191). Hilbert's mention of "contradictions and paradoxes" is of course a reference to the paradoxes in set theory, such as Russell's paradox, that arose near the turn of the century. 1~ axiom system Hilbert had in mind is not exactly the same as ZF. However, a proof of the consistency of ZF would certainly fulfill the goals of Hilbert's program. 11More formally: If the consistency of ZF could be proven from, say, Peano's axioms, it would follow that any H1 statement of number theory that was provable in ZF would also be provable in PA. If this were true we would say that ZF was a conservative extension of PA for [[1 statements of number theory. 12Of course, if it could be shown that Wiles's proof could be carried out in some axiomatic system weaker than ZF, then only the consistency of this weaker system would be needed as a hypothesis. 66

THE MATHEMATICALINTELLIGENCER

the consistency of ZF. His theorem is usually stated as saying, not that the continuum hypothesis is not provable in ZF, but rather that if ZF is consistent then the continuum hypothesis is not provable. To be sure, there is an important difference between Cohen's proof and Wiles's. The assumption that ZF is consistent is actually used in the reasoning of Cohen's proof, but Wiles's proof uses only ordinary mathematical reasoning and makes no reference to the consistency of ZF. It is only in thinking about whether or not Wiles's proof can be trusted that we are led to wonder about the consistency of ZF. For those who believe in the existence of the universe of all sets, and who believe that the ZF axioms are true statements about this universe, there is no reason to doubt the reliability of Wiles's proof. But for those who are skeptical about the existence of such a universe, the question remains: Should we be convinced by Wiles's proof that no counterexample to Fermat's Last Theorem will ever be found, or merely that i f ZF is consistent then no counterexample will be found? 13 I will not try to answer this question here. But I hope that by considering this question readers will be led to a greater appreciation of the significance of Hilbert's program, and the questions in the foundations of mathematics that remain unresolved to this day because of the failure of that program.

13Another way of thinking about this question is to consider formalizing the proof in different axiomatic systems. As we have already observed, Wiles's proof is formalizable in ZF, but probably not in PA. Thus, Fermat's Last Theorem is provable in ZF, but it is still not known whether or not it is provable in PA. However, the statement "if ZF is consistent then Fermat's Last Theorem is true" can be encoded in the language of number theory (by G6del numbering), and this encoded statement is provable in PA. The proof is simply the numerical encoding of our description of how a counterexample to Fermat's Last Theorem would lead to an inconsistency in ZF. Thus, the hypothesis that ZF is consistent is not needed for the proof of Fermat's Last Theorem if the proof is formalized in ZF, but it may be needed if the proof is formalized in PA. One's assessment of whether or not the hypothesis that ZF is consistent is needed for the proof of Fermat's Last Theorem might therefore depend on what axiom system one chooses to use.

VOLUME 19, NUMBER 1, 1997 67

II;(:-l'l[:-l','l.-1 J e t W i m p ,

Editor

I

The Problem of the Earth's Shape from Newton to Clairaut The Rise of Mathematical Sciencein EighteenthCentury Paris and the Fall of "Normal" Science by John L. Greenberg CAMBRIDGE, CAMBRIDGE UNIVERSITY PRESS, 1995, xviii + 781 pp. US $60.00, ISBN 0-521-38541-5

REVIEWED B Y J E R E M Y J. G R A Y

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.

he shape of the Earth was a controversial matter from before the time of Newton to the mid-18th Century, when it was agreed fmally that it was flatter at the poles, as Newton had predicted. So great was the interest in the question that the expedition to Lapland, led by Maupertuis, which resolved the question in 1736, earned its leader the title of the "Great Flattener." There was also a mathematical side, in which rival Cartesian and Newtonian hypotheses were made to yield testable predictions. This struggle, much analysed in the historical literature, has been generally regarded as one of the decisive victories for Newtonianism, converting the French from their previous adherence to the ideas of Descartes. And so it was. But this is often taken to mean that it was a victory for a paradigm, in which apparent problems are reduced to puzzles and then solved. Not so, says a recent book, it's much more exciting than that. John L. Greenberg's book The prob-

T

lem of the Earth's shape from Newton to Clairaut (Cambridge University

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

Press, 1995) would be a remarkable work even if the author had not been afflicted, as he tells us in the preface, with spastic paraparesis, an insidiously progressive form of multiple sclerosis. At the end of 620 pages of closely written text telling a fascinating story, he summarises the methodological issues

THE MATHEMATICALINTELLIGENCER9 1997 SPRINGER-VERLAG NEW YORK

underpinning his approach. Anyone concerned about relations between mathematics and physics, and between pure and applied mathematics, will fmd what he says illuminating and thought-provoking. It has wider resonances, too, for the Kuhnian dichotomy of revolutionary and normal science, which is something of an orthodoxy these days. He begins by taking historians of mathematics and science to task. "Historians of physics," he writes, "avoid the mathematics of physics, while historians of mathematics focus primarily on technical mathematics and exclude the physical contexts." Thus Todhunter, an eminent 19thcentury writer on this subject, simply ignored Clairaut's mathematics, "because he assumed that the mathematics already existed." In fact, "the partial differential calculus that Clairaut used to create his theory of figures of equilibrium of 1743 was itself brand new." The theme of the book is indeed the simultaneous, to-and-fro creation of new mathematics and new physics. What we have had hitherto, however, has been offered as "normal science": puzzle-solving within a paradigm. In this case, the paradigm of all paradigms, Newton's Principia, is taken to have proved itself successful in governing work on the shape of the Earth. Greenberg rejects, and refutes, this view. Normal science "as it is usually defined, is an idea that is readily and eagerly upheld by historians of science and philosophers of science who, following the physicists, view mathematics as purely utilitarian instead of an essential component of the science into which it enters. Like the physicists, these historians and philosophers treat mathematics as a language that could in theory be eliminated from science." What these people do not appreciate is that mathematics "need not simply serve as a vehicle for expressing scientific developments." Indeed, "the mathematics for doing [something]

m a y not exist, and it need not ever be invented." The story of the shape o f the Earth that Greenberg tells is one w h e r e m a t h e m a t i c s intervenes in an essential way. Thus Clairaut t u r n e d to mathematics to resolve differences b e t w e e n himself a n d Maclaurin, although b o t h count as Newtonians, and even t h e n he w a s unsuccessful: the m a t h e m a t i c a l p r o b l e m he formulated he could not solve. Unsuccessful, but not in vain, for the r e s e a r c h led him to n e w foundations for the theory of the equilibrium of fluids that Euler and others after him found useful. In 1739, at the height of the controversy, Clairaut w a s 26, and a l r e a d y a m e m b e r of the F r e n c h Acad~mie des Sciences o f 8 years' standing, a n d a veteran o f the trip to Lapland. His b o o k on the s h a p e of the Earth w a s to app e a r in 1743. His rival, nine y e a r s his senior, w a s Fontaine, w h o l a c k e d the c h a r m a n d the luck the y o u n g e r m a n had in abundance. It w a s F o n t a i n e w h o i n t r o d u c e d the partial differential calculus to France, Clairaut w h o drove it to success. The m a t h e m a t i c s that Clairaut c r e a t e d is the beginnings o f the t h e o r y of e x a c t differentials in 2 and 3 variables. The s o u r c e of this invention, G r e e n b e r g argues, is Clairaut's infinitesimal analysis of channels in a h o m o g e n e o u s fluid mass. The p h y s i c a l c o n t e x t f o r c e d the evaluation of line integrals along s k e w channels (curved paths). More t h a n that, conditional equations like

aP

aQ

ax

Oy

"only really a t t r a c t e d attention after and as a result o f having a p p e a r e d in Clairaut's t h e o r y of 1743." At this time Clairaut w a s engaged in a p o l e m i c with F o n t a i n e a b o u t the partial differential calculus, and a l m o s t b o u n c e d F o n t a i n e off the stage. So Euler in 1750 attrib u t e d the integrability c o n d i t i o n for the equation

simplify F o n t a i n e ' s mathematics, b u t to interpret it geometrically. So, for example, c o n s t a n t values of integrals of c o m p l e t e differentials are i n t e r p r e t e d as level s u r f a c e s of the effective gravity. A n d it w a s Clairaut and d ' A l e m b e r t w h o a p p l i e d it in physics and astronomy, which is w h a t c a u s e d the subject to c a t c h on, r a t h e r than the pure analysis itself. As Greenberg observes in passing, there are a n u m b e r of other m o m e n t s in the history of science w h e r e the interactions of m a t h e m a t i c s and physics have b e e n similarly rich. The socially and intellectually m u c h m o r e elaborate engagement with Witten's ideas m a y be j u s t such an e x a m p l e today. Nor d o e s bringing b a c k m a t h e m a t i c s into the history of science vitiate Kuhn's observations, once m a t h e m a t i c s loses its a u r a of inevitability. Greenberg is h a p p y to allow that there m a y still be revolutions in science, even in mathematics. But if his b o o k is an e x t e n d e d e x a m p l e of what riches can be found in the history of a mathematical science b y taking neither the m a t h e m a t i c s nor the scientific context for granted, it is also more. It forces us to c o n s i d e r what is the relationship b e t w e e n an idea in physics and its e x p r e s s i o n in mathematics and w h a t is going on when, conversely, a mathematical i d e a is given a physical interpretation. This should be m o r e than enough stimulation for any philosopher of m a t h e m a t i c s not hopelessly lost in the aridities of Hilbertian formalism, in which m a t h e m a t i c s is r e d u c e d to questions about the nature of sets. Faculty of Mathematics and Computing Open University Milton Keynes, MK7 6AA England

Space-Filling Curves by H a n s S a g a n NEW YORK, SPRINGER-VERLAG(UNIVERSITEXT),1994.

Q(x, y, z ) d x + R(x, y, z ) d y + S(x, y, z ) d z = 0

U.S. $29.95, ISBN 0-387-94265-3

REVIEWED BY JOHN HOLBROOK

to Clairaut a n d d'Alembert, w h e r e a s , in d ' A l e m b e r t ' s opinion, the c o n d i t i o n had b e e n d i s c o v e r e d b y Fontaine. Clairaut's contribution w a s not j u s t to

athematicians-in-training are commonly astounded when they first confront the space-

M

filling curve p h e n o m e n o n : the "curves" that we so glibly s k e t c h on the p l a n e as lines and l o o p s may, in s o m e cases, fill up a whole region. Together with the related p h e n o m e n o n o f n o w h e r e differentiable y e t c o n t i n u o u s functions, space-filling curves teach students the i m p o r t a n t lesson that continuity is a boldly p e r m i s s i v e concept. I s u p p o s e m o s t s t u d e n t s s e l d o m reflect further on the m y s t e r y o f space-filling curves, e x c e p t p e r h a p s during occasional lectures to their o w n intermediate analysis students. Yet the story is richer than m a n y o f us might imagine, with a h o s t of attractive examples, interactions with o t h e r b r a n c h e s of mathematics, a n d even "applications." Hans Sagan's b o o k m a k e s this s t o r y m u c h m o r e a c c e s s i b l e t h a n ever before. Space-Filling Curves is a goodnatured, enthusiastic b o o k with m a n y charming touches, and Sagan himself aptly d e s c r i b e s its c h a r a c t e r in his preface: This monograph is neither a textbook nor an encyclopedic treatment of the subject nor a historical account, but is a little of each.

Of these t h r e e c o m p o n e n t s of Sagan's m o n o g r a p h , I think m o s t readers of the M a t h e m a t i c a l InteUigencer will find the "historical account" to be the m o s t rewarding, b e c a u s e they will a l r e a d y have a b r o a d m a t h e m a t i c a l exp e r i e n c e to d r a w upon. F o r the s a m e reason, they will be able to decide for t h e m s e l v e s w h i c h p a s s a g e s to skim (there is c o n s i d e r a b l e repetition a n d pointless detail), a n d w h e n to r e p h r a s e the o c c a s i o n a l p e c u l i a r def'mition o r m i s p l a c e d emphasis. F o r the s t u d e n t w h o turns to this b o o k to learn ab initio about space-filling curves and their lore, there is g r e a t e r danger. The m a i n points are not m a d e clearly or concisely enough for such a reader, who, I fear, will run out of s t e a m working through the u n n e c e s s a r y details and will be confused b y s o m e a s p e c t s of the exposition. By a "space-filling curve" we should p r o b a b l y m e a n a c o n t i n u o u s function f : [0, 1]--) R n, w h e r e n > 1 and yet f([0, 1]) has n o n e m p t y interior. Sagan uses a closely r e l a t e d defmition: his space-filling curves have positive J o r d a n content. This is a little different VOLUME 19, NUMBER1, 1997

69

because the whole curve has then to be Jordan measurable, and it is certainly harder for the beginner to interpret than is the "nonempty interior" formulation. In all but one respect (I'll come to that later), I likely represent the typical reader of Sagan's book, so let me summarize what I found in "SpaceFilling Curves" that I didn't know (or knew only hazily) before. (1) Peano's first description (in 1890) of a space-filling curve was given entirely in terms of ternary expansions of the variables, and was thus devoid of geometry (see, however, chapter X of H. Kennedy's book [2] on Peano). It was Hilbert who quickly (1891) clarified the geometric features of such constructions. (2) "Peano, Hilbert," is only the beginning of a long list of famous names that may be attached to space-filling curves. A continuation should include, at the least, E.H. Moore, Osgood, Ceshro, Sierpifiski, Knopp, P61ya, Lebesgue, Hahn, Mazurklewicz, Steinhaus, Schoenberg, Salem, Zygmund. While all of these contributed interesting variations on the theme, Osgood, Hahn-Mazurkiewicz, Steinhaus, and Salem-Zygmund added striking new material: see (3), (4), (5), and (6), below. (3) Although a one-to-one curve ("Jordan curve") cannot be space-filling, as Netto had observed some years before Peano's discovery, Osgood pointed out that Jordan curves can nevertheless have positive Lebesgue measure in the plane. Such curves (or rather their images in R 2) c a n n o t be Jordan measurable, for otherwise their interiors would have positive Jordan content, contradicting Netto's theorem. (4) Hahn and Mazurklewicz characterized continuous images of [0, 1] in such a way that [0, 1] 2, [0, 1] 3, . . . are obviously included. (5) Steinhaus pointed out in 1936 that there is a striking connection between space-filling curves and probability theory. If X and Y are independent random variables on the probability space [0, 1] (with Lebesgue measure) and are at the same time continuous (but not constant) on [0, 1] as a metric space, t h e n f = (X, Y) defines '70

THE MATHEMATICALINTELLIGENCER

a space-filling curve (filling a rectangle); conversely, many classical spacefilling curves (for example, the Peano and Hilbert constructions) have just such independent random variables as coordinate functions. (6) Salem and Zygmund found that analytic functions on the disc may have continuous extensions to the circle with space-filling curves as their boundary values. (7) There are applications of the patterns of space-filling curves to such problems as the travelling salesman problem. Sagan says little about these applications in his text, but one may explore them by following his bibliography (see Bartholdi and Platzman, for example). The same goes for certain more mathematical applications: those, for example, to the smoothness of functions (see Sagan's references to Garsia and Milne). (8) A connection between spacefilling curves and the classical imbedding of separable Banach spaces as subspaces of C[0, 1] is inevitable. We have discussed this connection with students and colleagues over the years, but Sagan's references (see Donoghue, for example) provided our first clues to the literature. Although Sagan doesn't seem to treat this connection in his text, it is one of the treats he has hidden for enterprising readers of his bibliography. (9) We have strildng quantitative versions of Netto's theorem (see (3) above). Hahn and Mazurkiewicz showed, for example, that a curve filling the square must have triple-points and that these must be dense in the square. On the other hand, it is possible to avoid quadruple-points entirely. (10) The observation that once a square-filling c u r v e f = (~b, ~) has been constructed, one can painlessly fill cubes, hypercubes, etc, simply by using (,/,, ,/,or ~o,/.,o,/,, 4,or162162 goes back a long way. Sagan refers to Steinhaus (1936), but see the remarks below concerning (10). My own encounters with items (5) and (10) explain why I am not quite the typical reader of Space-FiUing Curves. With admirable tact, Sagan points out that circa 1980 a number of us rediscovered the Steinhaus results and, unaware (as were referees and editors, it

might be noted) that they were forty years old, published them! Results that form part of the trunk or branches of the mathematics tree are automatically remembered, but it seems that individual flowers, though very beautiful, may be largely forgotten. More recently, I came across the account by Mark Kac (see his introductory autobiographical essay in [1]) of his participation, as a young research assistant, in these discoveries of Steinhaus. Kac recalls the astonishment and delight with which he and Steinhaus recognized the connection between spacefilling curves and stochastic independence (the mathematical theory of which was, at that time, not widely understood; Kac and Steinhaus were hammering it out as they went along). Astonishment and delight were my reactions too, so I guess what I learned from my experience was this: those who are ignorant of mathematical history may have the pleasure of repeating it. Sagan includes biographical sketches of the main characters in his story. These and the photographs that accompany them are a welcome feature of the book. Faithful subscribers to The Mathematical InteUigencer can find such information about Hans Sagan himself by looking up his article [4] in volume 15. Now for some grumbling. Sagan seems to suggest (p. 112) that the Steinhaus recipe (10) for generating higher-dimensional space-filling curves from the planar case is somehow tied to stochastic independence. It is not. Again the Kac recollections in [1] are helpful: it appears that Steinhaus was responding to Sierpifiski's slightly earlier discovery of the recipe. Sagan's definition of "curve" confuses it with its image; he repeats this interpretation several times, so I guess he really means it. For him, the square is the Peano curve (which is therefore the Hilbert curve, the Sierpi~ski curve, etc.). This is not merely eccentric, in my view; it's wrong. To show that a space-filling curve cannot be (everywhere) differentiable, Sagan seems to rely on a recent and relatively sophisticated result of Morayne (see p. 79). I believe, however, that it has been understood al-

most from the beginning that a differentiable curve must be of area (Jordan content) zero. One can, in fact, cover such a curve by a finite number of narrow strips. Sagan includes two extended expository accounts--of the HahnMazurkiewicz theorem and its background (in chapter 6) and of fractal sets and iterated function systems (in chapter 9). Some of this material is quite elementary (nothing wrong with that) but there are logical jumps that seem unfair to the reader who needs to start at that elementary level. In proving Netto's theorem, for example, Sagan uses the connectedness of the square minus a point, yet the previous discussion of connected sets provides no basis for this. In fact, Sagan's account of Netto's result only mystifies it, it seems to me; surely the essential observation is just that a continuous map of the circle to the line must overwrite itself ("intermediate value theorem"). The "Heighway dragon" is certainly, among other things, an elegant spacefilling curve. I'm not sure Sagan is fair, however, when he judges it "the latest original space-filling curve ..." Starting, for example, from the index of B. Mandelbrot's landmark book [3], one is led to several other good candidates. In spite of a few critical comments, I am grateful for Sagan's book about space-filling curves, and predict that many will enjoy its account of working in this area, which is, as the author so nicely puts it, like skating on the edge of reason. Is that not part of our fascination with mathematics as a whole? REFERENCES

1. K. Baclawski and M. D. Donsker (editors), Mark Kac: Probability, Number Theory, and Statistical Physics; Selected Papers, MIT Press, 1979. 2. H. C. Kennedy, Selected Works of Giuseppe Peano, University of Toronto Press, 1973. 3. B. Mandelbrot, The Fractal Geometry of Nature, San Francisco: W. H. Freeman, 1983. 4. H. Sagan, A geometrization of Lebesgue's space-filling curve, Mathematical Intelligencer 15 (1993), no. 4, 37-43.

John A. Holbrook Mathematics and Statistics University of Guelph Guelph, Ontario N1G 2W1 Canada e-mail: [email protected]

Handbook of Lie Group Analysis of Differential Equations; Applications in Engineering & Physical Sciences Edited by Nail H. Ibragimov BOCA RATON, FL: CRC Press, 1994. 400 pp. US $97.00, ISBN 0849328640

REVIEWED BY ROBERT GILMORE

his CRC handbook deals with the applications of Lie s group-theoretical methods to the analysis and solution of ordinary and partial differential equations. It is useful and important in a number of ways. First, N. H. Ibragimov, a major modem contributor to this exciting and growing area, is both editor of and chief contributor to this volume.* Of the 17 chapters in this volume, he is author or coauthor of eight, and provided major editorial guidance for the remaining nine. His colleagues include W. F. Ames, R. L. Anderson, V. A. Dorodnitsyn, E. V. Ferapontov, R. K. Gazizov, and S. R. Svirshchevskii. These authors constitute a coherent "school" of proselytizers for and extenders of Lie's methods for studying differential equations. What Ibragimov brings to this handbook is an editorial vision of content and of uniformity in style and presentation. The CRC Press is to be lauded for its handbook series. In traditional professional publications (refereed journals and conference proceedings), an editor generally has a broad general knowledge which doesn't extend to enormous depths in some of the fields the journal covers. The editor farms out manuscripts to anonymous referees, who then report back and may either reject or recommend substantive or stylistic changes. In this model, the

T

author and referees are seldom allies, often antagonists; little uniformity in style results. In the model of collaboration which the CRC Press is endorsing, there is a collegial relation between the (contributing) editor and the other authors. Rather than anony~mity, there is strong interaction. The individual authors work under firm guidelines to ensure adherence to a single vision. This model is good for the field, good for the contributors, and good for the audience. Needless to say, this handbook is highly recommended to workers in the field. The volume is divided into three parts. Part A consists of seven chapters. These review rapidly the results of Lie and their generalizations. The aim of this part is to bring together all the mathematical machinery for the study of differential equations and to present it in a simple way without the obfuscating intrusion of rigor. This part was largely coauthored by Ibragimov and Anderson. Part B consists of Chapters 8-15. These collect the results of grouptheoretical analyses in one place. These results deal with the classification, characterization, and solutions of differential equations using symmetry techniques. These results go back to the time of Lie. Point, contact, Lie-B~tcklund, and nonlocal symmetries are tabulated. Noether's theorem is presented and its applications for constructing conserved quantities are listed. Part C consists of Chapters 16 and 17. This part deals with the transformation from the late 19th century to the late 20th century: the mapping of continuous differential equations to fmitedifference equations, and the implementation of numerical procedures for solving the resulting fmite-difference equations. These two chapters were written by Ames and Dorodnitsyn, respectively. The bibliography is extensive and is largely confined to some classics in the field, the school represented by the editor and contributing authors and their colleagues, and some closely related schools. *The reader may wish to consult the article on this aspect of Lie's work by N.H. Ibragimov in the Mathemat-

ical Intelligencer 16, no. 1 (1994), 20 28. VOLUME 19, NUMBER 1, 1997

71

Is this volume useful? Partly. Like any handbook, it is useful for those already familiar with the subject; m u c h less so for those approaching it for the first time. If you don't already k n o w the material, you should pick up a didactic text in this area (the older, the better). On the other hand, if y o u already k n o w the m a t e r i a l - - n o matter h o w well--this is an excellent source that can be held in one hand. It summarizes well m u c h of what you might know, and contains material which will be n e w to you. This volume forms a valuable part of m y library, but is not one from which I would like to learn. Lie's contribution to the study of differential equations was a profound insight sustained by some elementary calculus. The profound insight was that differential equations could be simplif i e d or solved by change o f variables.

The technical component from calculus was the chain rule. The types of transformations between indep-endent (x E R m) and dependent (y E R n) variables treated in Ibragimov's book are x, y depend on

Type of transformation

x x, y

x, y, y ' x, y, y', . . . , y(k) x, y, y',

...,

y(k),

...,

Geometric Point Contact Lie-Bficklund y("~o)

it can be written in the form p = dy/dx = f ( x ) . In this form, we have reduced it to "quadratures." Lie's objective was to determine a new coordinate system [(R, S, T), called canonical coordinates] in which F is independent of the "middle variable" S. If an infinitesimal transformation (Lie symmetry) x---)~Y=x+~ y--> ~ = y + ~? p-->~=p+ ~

leaves the surface invariant, then F(x, y, p) = 0 ) F(~, ~, p--) = F(x, y, p) + eX F(x, y, p) + . . . .

x:

Tx

O,

9

The expression above contains the leading terms of the Taylor series expansion of the function F(~, ~, p--) = e ~c F(x, y, p) at (x, y, p). For contact transformations, ~ = ~(x, y) and ~? = ~?(x, y). Since p = dy/dx, ~ is not independent of ~ and ~?: it is given by the p r o l o n g a t i o n f o r m u l a (a chain-rule result) ~(x, y, p ) = ~?x + (~?y - ~x)P - ~yp2.

One carries out the transformation to canonical coordinates by solving linear partial differential equations

Nonlocai Here, ~Yand ~ are transformed coordinates; y', y " , . . , are derivatives of the first, s e c o n d , . . , order. I will illustrate Lie's basic a p p r o a c h for first-order (depends on p = dy/dx in the "classical" notation) ODEs (x, y E R 1) of arbitrary degree (power with which dy/dx occurs). A firstorder ODE can be represented by a surface F(x, y, p) = 0

subject to the constraint p-

dy dx"

This equation is relatively simple to solve if F is independent of y, for then '~

THE MATHEMATICALINTELLIGENCER

These equations are often simple to solve. For instance, R(x, y) can be determined by the method of characteristics:

F(R, - - , T) = O, dS dR

- f(R, T).

These two equations can be combined to solve for S by quadratures: S = f f ( R , T(R)) dR.

Here is an example of Lie's method and the use of material collected in this handbook. If one needed to solve the first-order ODE F(x, y, p) = x p + y x y 2 = 0, one would first attempt to determine its Lie symmetry. This is done by applying the infinitesimal generator X to F and requiring X F = 0 when F = 0. This leads to a set of d e t e r m i n i n g equations

~(p _ y2) + ~?(1 - 2xy) + ( n x + ( v y - &-)p - ~ p 2 ) x = 0,

which must be satisfied when xp + y - x y 2 = 0. It is not always an easy

matter to guess these solutions. However, symbol manipulation codes have been developed which perform such computations. A simple solution to the determining equations above is ~=x, ~ =-y (and, therefore, ~ = - 2 p ) . We could also obtain this result by observing that the original equation is invariant under the scale transformation x---> ~x, y--> A-ly, and, therefore, p --~ A-2p. Canonical coordinates R, S, and T for this equation are determined from Table 1: R = xy, S = In y, and T = x2p. In these coordinates, the equation and constraint reduce (by computation and from Table 1, respectively) to

dx

dy

dS

T/R

~(x, y)

~?(x, y)"

dR

T+R"

Table 1 contains the transformations from original (x, y, p) to canonical (R, S, T) coordinates for a number of Lie symmetries (~, ~?, ~). Much of this forms the subjects of Chapters 8 and 9 in the handbook. In canonical coordinates, the surface and constraint equations transform to

These are combined to provide the quadrature dS

1

1

dR

R

R 2"

Solution by quadratures is immediate: S = In R + 1/R + c, where the parame-

ter c is the Lie group parameter for

Infinitesimal generators ~(x, y)

Quadrature

Natural coordinates

~/(x, y)

~lx, y , p)

R(x, y)

S(x, y)

T(x, y , p)

0

1

0

x

y

p

T

1

0

0

y

x

p

1/T

1/a

-1/b

0

ax + by

bx - ay

p

(b - a h ( a + b h

x

0

-p

y

In x

xp

1/T

0

y

p

x

In y

p/y

T

x/a

y/b

(lib - lla)p

yblxa

b Iny

p/x{aYb 1)

(bT/R)/(bT - aF~ l/b)) (T/R)/(T - R)

dS/dR

x

y

0

y/x

In y

p

x

-y

- 2p

xy

In y

x2p

(T/R)/(T + It)

2x

y

-p

y2/x

In y

yp

(T/R)/(2T - R)

x

2y

p

y/x 2

In y

p/x

(T/R)/(T - 2R)

y

0

p2

y

x/y

x - y/p

- T/R 2

0

x

1

x

y/x

xp - y

T/R 2

x

1 +p2

"~x2+y 2

tan -1 (y/x)

y 1

y/x

a

x

a x

(.ox

y)/x 2

(y

xp)/(x+yp)

T/R

y/x

x

1

x 2 - 2ay

x/a

y

p

x - a Iny

x/a

p/y

(1/a)/(1 - aT)

b

-p

eY/xb

y/b

e y * pb

[(1/(bR)]/[1 - b(R/T) l/b]

y

b

_p2

y2 _ 2bx

y/b

y - b/p

1/(2bT)

0

e f(x)

f'e ~

x

ye r

p _yf,

Te-f(R)

x2

xy

y/x

1/x

xy

y2

yp

xy

0

-yp

0

xy

g(y)

0

0 f(x)

y -xp

(xp - y)/x 2 x

ap

xp

y

1/T

1/(2aT)

1/T

y/x

1/y

y/p - x

1/(TR 2)

y

(In x)/y

y/xp - In x

T/R 2

y + xp

x

(In y)/x

xp/y - In y

T/R 2

_ g , p2

y

x/g

1/p - (g'/g)x

T/g(R)

f(x)

f"

x

y/f

fp - f 'y

T/f 2(R)

0

-f'p

y

F (where F'f = 1)

pf

1/T

-- xp 2

--x p 2

0

g(y)

g'p

x

G (where G 'g = 1)

p/g

T

x k+l

kxky

xk(k2y/x -- p)

y/x k

X -k

xp -- k y

-k/T

kxyk

yk+ l

yk(p _ k2xp2/y)

x/yk

y k

y/p - k x

-k/T

"translations" under which the equation is invariant. The solution is n o w easily obtained by substituting for the original variables: y = -[x(c + In x)] -1. Canonical c o o r d i n a t e s can be u s e d to a n s w e r m a n y o t h e r questions. The m o s t general first-order ODE invariant u n d e r a Lie s y m m e t r y group (~, 7/, 0 is given by an arbitrary function o f the canonical c o o r d i n a t e s R a n d T: G(R, - - , T) = 0. F o r example, the m o s t general first-order, first-degree ODE with Lie s y m m e t r y ~ = x, 77 = - y is x2p = g(xy) [g(z) = - z + z 2 for the equation t r e a t e d above]. The m o s t general firsto r d e r equation with this s y m m e t r y is G(xy, x2p) = O. The m o s t general seco n d - o r d e r ODE with this s y m m e t r y dep e n d s on the invariant coordinate

dT2xy'+x2y"( ~y+xy'

dT) ' V R,T,~ =0.

Similar results hold

for the

most

general kth-order ODEs invariant u n d e r this group: G(R, T, T(1),..., d k- 1T/dRk- 1) = 0. These r e m a r k s s h o w that Lie's a p p r o a c h to the s t u d y of differential equations is a generalization of the m e t h o d of dimensional analysis. The b o o k also covers the s t u d y of s y m m e t r y and c o n s e r v a t i o n laws well. These results are all special c a s e s of, o r d e s c e n d a n t s of, N o e t h e r ' s theorem. When a set of differential equations is derivable from an Action Principle

I = f L(x, y, y ' , . . . ) dx, one can c o n s t r u c t the c o r r e s p o n d i n g E u l e r - L a g r a n g e equations from the first variation

8I = 0 ~ E(L) = O. If the E u l e r - L a g r a n g e equations are invariant u n d e r an n - p a r a m e t e r symme-

try group, then integration b y parts is a d d e d to the arsenal o f tools available. The chain rule and integration by p a r t s can be u s e d t o g e t h e r to c o n s t r u c t an e x p r e s s i o n for the first variation of the Action Integral:

+ i=12Di(Ji(L,

v)))dx.

Two inner p r o d u c t s o c c u r in this exp r e s s i o n for the first variation. One (over a) o c c u r s in the s p a c e of the infinitesimal Lie group g e n e r a t o r s which leave the E u l e r - L a g r a n g e equations invariant. The functions v ~ (characteristics of the t r a n s f o r m a t i o n ) are related to the infinitesimal g e n e r a t o r s of the s y m m e t r i e s of the Euler-Lagrange equations. The o t h e r inner p r o d u c t occurs in the s p a c e of i n d e p e n d e n t variables. The o p e r a t o r s Di are the partial VOLUME 19, NUMBER1, 1997 73

derivatives alax~, p r o l o n g e d b y the chain rule. This inner p r o d u c t is a generalized divergence. The s y m m e t r i e s of the E u l e r Lagrange equations m a y o r m a y not leave t h e Action Integral invariant. Two c a s e s m a y occur:

8I = 0. Then E~,(L) = 0, t h e r e f o r e DiJi(L, v) = 0, and the vect o r with c o m p o n e n t s Ji(L, v) is conserved.

~I = f Di(Bi) dx. In this case, DiJi is not conserved, b u t Ji(L, v) - B / is a c o n s e r v e d quantity. Where do w e go from here? Ibragimov's h a n d b o o k is a p r o j e c t e d multivolume series. The material in Volume 1 reflects the b i a s e s of the editor and authors. Ibragimov entertains p r o p o s a l s for inclusion of additional topics in future volumes. One very imp o r t a n t topic that should be included in s o m e future volume is c o m p u t e r related. Lie's results are algorithmic in nature. Computation o f the infinitesimal g e n e r a t o r s from the determining equations can be a nightmare, b u t this nightm a r e can be automated; so also can the c o m p u t a t i o n of the c o m m u t a t i o n relations a n d reduction of a solvable group to canonical form. C o m p u t a t i o n of Euler-Lagrange equations and components o f conserved currents is also algorithmic, and can p r o c e e d in brainless fashion provided only that the bookkeeping is sound (i.e., excellent for computers). Many of these algorithms have b e e n i m p l e m e n t e d in s y m b o l manipulation languages such as MACSYMA, MAPLE, MATHEMATICA, and REDUCE. Ibragimov would d o an enorm o u s service to the c o m m u n i t y b y summarizing all available c o m p u t e r implem e n t a t i o n s of Lie's, Noether's, and later algorithms for studying differential equations. It is one of the ironies of the 20th century that the algorithms w h i c h w e r e developed by Lie for constrncting analytic solutions for ODEs have only b e e n p r o p e l l e d to their maturity b y the d e v e l o p m e n t o f high-powe r e d computers, which can alternatively b e used to construct numerical solutions to these s a m e equations. The CRC Press is implementing a useful and important vision: the collab74

THE MATHEMATICAL~NTELLIGENCER

orative but unified handbook. Scientific inquiry has progressed to the point where it is difficult for a single author to master sufficient detail, even in his/her own area, to provide a h a n d b o o k of the depth and scope which the CRC Press n o w routinely attempts to publish. But these are only stopgap efforts. Handbooks do not present introductory, didactic material effectively. To learn the field, you m u s t begin elsewhere. The endpoint of this evolutionary p r o c e s s is to place all this material (textbook, handbook, etc.) in some hyperlinked format. Then an editor and contributors can coauthor chapters in broad areas, as in the present volume, while other editor/author combinations could link this advanced material to more didactic chapters written at a more elementary level. If s o m e o n e or some organization offers sufficient guidance, this extension from p a p e r to the electronic domain will vastly extend the importance, the usefulness, and the audience for the subject of the handbook. Department of Physics and Atmospheric Science Drexel University Philadelphia, PA 19104, USA e-mail: [email protected]

The Knot Book; An Elementary Introduction to the Mathematical Theory of Knots by Colin Adams NEW YORK: W. H. FREEMAN& Co,, 1995 US $32.95, ISBN; 071672393XCT REVIEWED BY DE WITT SUMNERS

a t h e m a t i c s does suffer from an image problem. Mathema-ticians find it v e r y difficult to explain (even to an i n t e r e s t e d audience) w h a t m a t h e m a t i c s is, w h a t m a t h e m a t i c i a n s do, and w h y n o n - m a t h e m a t i c i a n s should care a b o u t the subject. One culprit is the minimalist style of r e s e a r c h m a t h e m a t i c s writing, in which a w o r d is on the p r i n t e d page if and only if it is essential to the argument. This style

M

p r o d u c e s clean, elegant, highly comp r e s s e d proofs, w h e r e j u s t enough detail is p r e s e n t so that a professional m a t h e m a t i c i a n (that is, one skilled in the intricacies of the subdiscipline) can fill in the r e s t of the details and b e convinced of the c o r r e c t n e s s of the argument. The minimalist style w o r k s well for internal t r a n s m i s s i o n of inform a t i o n within m a t h e m a t i c s subcommunities; the style l e a d s to disaster (or at least indifference) w h e n used for t r a n s m i s s i o n of information to other m a t h e m a t i c s s u b d i s c i p l i n e s or to the outside world. Mathematics desperately n e e d s m o r e first-rate e x p o s i t o r y writing; we m a t h e m a t i c i a n s n e e d to constantly r e m i n d a n d convince our scientific p e e r s a n d the general public that we are doing interesting and ultimately "useful" stuff. The Knot Book b y Colin A d a m s is a fine piece of e x p o s i t o r y writing. I k n o w from first-hand c o n v e r s a t i o n s with chemists, m o l e c u l a r biologists, and high-school m a t h t e a c h e r s that they and their s t u d e n t s fred The Knot Book both a c c e s s i b l e and useful. Everyone has e x p e r i e n c e d tying and tmtying knots; the s u b j e c t is highly visual and i m m e d i a t e l y c o n n e c t s to the r e a d e r ' s intuition. As a vehicle for getting people interested in mathematics, knot t h e o r y is an e x c e l l e n t "hook." Moreover, there is r e c e n t a n d intense interaction b e t w e e n k n o t t h e o r y and a numb e r of scientific disciplines. A combination o f k n o t t h e o r y and statistical m e c h a n i c s is proving to be very useful in theoretical a n d l a b o r a t o r y p o l y m e r chemistry; k n o t t h e o r y is a very g o o d d e s c r i p t o r and d e t e c t o r of spatial isom e r s of large and small molecules. In l a b o r a t o r y m o l e c u l a r biology, knot theory is useful in the s t u d y of metabolic enzymes that change the topology of cellular DNA. The incredible interaction b e t w e e n m a t h e m a t i c s and theoretical physics s t e m m i n g from the w o r k of J o n e s a n d Witten has knot theory as a focus. In o t h e r words, knot t h e o r y is hot, a n d lots of p e o p l e are int e r e s t e d in it. Colin A d a m s ' s b o o k is built to surf this big w a v e o f interest, and S U R F ' S UP, DUDE! This b o o k grew out of a series of undergraduate r e s e a r c h projects in which Colin A d a m s participated at Williams College. As Colin puts it, "My

group of students has usually worked on knot theory. Every summer, I would fmd myself teaching the same material over again, without a reference at the right level. It was such beautiful material that I decided it would be worth writing a book." And write a book he did. This book proves Colin a master at squeezing the formality out and revealing the interest in the subject. At every juncture, he takes pains to explain geometric ideas in everyday language. This means that explanations are incomplete and often lack the precision of formal mathematical language, but this is the whole point of the exercise. There is plenty of time to cross the t's and dot the i's after you are hooked on mathematics. If you never get interested in mathematics in the first place, then formality is both irksome and irrelevant. In the preface to the book, Colin thanks (among others) his alter ego, scoutmaster Mel Slugbate. At the MAA-AMS 1994 summer Minneapolis Mathfest I had the delightful experience of hearing Mel Shigbate (Colin Adams in scoutmaster costmne) stand in for his "brother-in-law" Colin as the Pi Mu Epsilon banquet lecturer. Mel began by explaining about knot merit badges, and finished off by tiling 3space with trefoil bricks. It was a bravura performance, demonstrating Colin's ability to get sophisticated ideas across at an elementary level. With very few exceptions, the book assumes only high school algebra as a background; in fact, chapters 1-5 need only elementary geometric intuition as a guide; the arguments are based on planar knot diagrams. The book has multiple illustrations on almost every page. Chapter 1 is the most important chapter in the book, in getting the basics across and inducing people to read the rest of the book. It has a very nice discussion of knot and link diagrams and Reidemeister moves, for example showing a sequence of Reidemeister moves which convert the figure 8 knot to its mirror image, illustrating the dynamics of a knot changing its spatial conformation. One very nice feature of the book is the exercises, ranging from elementary to starred to unsolved (circa 1994). As a prime example of the type of knot theory problem that elementary school students can get inter-

ested in, consider the stick number s(K) of the knot type K--the minimum number of straight sticks needed to make K. There is now a web site called "Erd6s for Kids" (http://csr.uvic.ca/ -e4k/) where stick number is one of the problems that the kids are working on. This kind of interest is exactly what "The Knot Book" sets out to generate, and the success of that effort is evident. Chapter 2 provides a description of knot tabulation and the work of Conway and Thistlethwaite; chapters 3-5 do more "descriptive" knot theory, introducing unknotting number, bridge number, genus and Seifert surfaces, torns and hyperbolic knots, with lots of explanatory pictures. The new (post-Jones) knot theory is introduced in chapter 6, which contains a lovely exposition of the Kauffman approach to the bracket and Jones polynomials; chapter 6 continues with the Alexander and HOMFLY polynomials, and uses the new polynomials to detect chirality (changes in knot type upon taking mirror images). I found Chapter 7 particularly interesting (naturally, since I work in this area!): applications of knot theory to biology, chemistry, and physics. As mentioned earlier, one aim of knot theory is to describe and enumerate spatial conformations of 1-dimensional objects in 3-space, and this is particularly useful in studying molecular conformation and changes in conformation caused by chemical and biological agents. The chapter describes the tangle model for site-specific DNA recombination, the synthesis of small knotted molecules, and the chirality of molecules. A very nice account of the connection between knots and statistical mechanics is given, including the Ising and Potts lattice models and partition functions. Chapter 8 discusses knots and links in graphs, and proves the Conway-Gordon result that every 3-space embedding of the complete graph on 7 vertices contains a knotted Hamiltonian cycle. Chapter 9 discusses some non-diagrammatic aspects of knot theory, in which knots are studied by means of the knot complements in 3-space. Chapter 10 has a brief excursion to higher-dimensional knot theory (2-spheres in 4-space, 3-spheres in 5-space).

The book suffers, as do most first editions, with some typos and misprints in both the text and the figures. For example (this list is not exhaustive), there is a missing minus sign in the genus formula in Exercise 4.19; some crossings are not resolved in the diagram~s on page 117; Figure 7.17 has direct repeats and inverted repeats switched; and Figure 7.20 is the mirror image of the correct enzyme mechanism. The problem in Figure 7.20 arises because the tangle sign convention of Sumners and Ernst differs from that of Conway, and Adams uses the Conway tangle sign convention throughout the book. The problems mentioned in the above paragraph are minor, and do not detract from an otherwise excellent exposition. This book is indeed suitable as an introductory topology textbook, and a resource book for all, including professional knot theorists. Non-mathematicians and beginning mathematicians will find it a fascinating introduction to a beautiful subject; scientists with a professional interest in the use of knot theory in their research will find it very useful; knot theorists will benefit from the unique point of view and methods of exposition of the subject. I highly recommend this book to all! Department of Mathematics Florida State University Tallahassee, FL 32306-3027 USA e-mail: [email protected]

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

99, ISBN 0-297 81642 X

REVIEWED B Y J O H N MALITO

AA | have a dream" is how Ian Stewart | b e g i n s this book. In his dream | Stewart is surrounded by nothing, which he fills in with space. He then slowly adds to this space, modifying it until the final chapter, when his dream has become as complex as Nature herself is. Stewart says this sort of virtual unreality machine is "present inside every mathematician's head," VOLUME 19, NUMBER 1, 1997

75

and adds that the collective mathematical mind has created a universe of its own, a mental universe wherein dreams are real. The reader is invited to journey into this mathematical dreamscape. And as the pages of this dreamlogue turn, readers will find themselves changing in the way they view both mathematics and the world. That is, Stewart makes it abundantly clear that mathematics is about much more than numbers, those ethereal symbols that have become much too self-important, just as words have in our everyday languages. Mathematics is about Nature's patterns, and it is as much about space and time, or shapes and rhythms, as it is about numbers. In fact, this book is subtitled "Discovering Order and Pattern in the Universe," because order and pattern can always be reduced to numbers like the primes, the golden number (ap), Feigenbaum's number (t~), and the Fibonacci series. Stewart tends to claim most of history's scientific advances for Mathematics. Perhaps he claims too much? He draws examples from ecology, biology, chemistry, and physics wherefrom mathematicians have sought out "generalities that cut across the obvious subdivisions." This is also what a scientist does, but Stewart argues that mathematicians and scientists have always learned different lessons. He does concede, however, that scientists are beginning to realise that "determinism and predictability are not synonymous." He also argues for the pursuance of "pure" mathematics, as the "pursuance of safe research will impoverish us all." So-called applied mathematics will take care of itself, but "the dreamers and mavericks must be allowed some free rein, too." In some instances, Stewart's treatment of science may be somewhat cavalier. For example, he assumes the answer to an ongoing debate when he employs a particular virus for his demonstration of broken symmetry in living systems. He casually over-generalises in places, then splits mathematical hairs elsewhere in the book. The value of the hair-splitting, however, does come through when he presents detailed case studies for three phenomena: the rhythm of falling liquid 76

THE MATHEMATICAL INTELLIGENCER

drops, the predator-prey population cycle, and the number of petals on a plant. Each is a study in the origins of nature's numbers. Deep mathematical regularities are detected in natural forms so that nature, rather than being complicated, is simple. The problem is that the simplicities of nature are not always easy to detect. "I have another dream" is how Stewart begins to end his book. This time, however, his dream is a dream in the other sense of the word. That is, he envisions and hopes for a new way of thinking. He calls this morphomatics. It is essentially a new kind of mathematics that would deal with nature's patterns as emergent phenomena. It would be an "effective mathematical theory of form." While acknowledging that many branches of science are moving in the opposite direction, Stewart insists that the relatively new concepts of symmetry breaking, chaos, fractals, and others are "bits and pieces" of morphomatics. The creative importance of this would be immense. Stylistically, "Nature's Numbers" is a good read because of its manysidedness. Stewart touches on several

aspects of mathematics including the humanistic, the political, and the philosophical. It is an elusive book, a chameleon that changes hue often, back and forth from pure prose to pure chattiness. The book begins with simple concepts such as counting and builds towards the more difficult concepts like fractal geometry and chaos theory. Stewart gives defmitions all along the way, but at the higher complexity levels we can understand why the less mathematical mind must ascribe Nature's patterns to random disorder. In fine, this book should appeal to many and varied readers, but for the mathematician, I would suggest that it be read in one sitting in a comfortable setting. You will find yourself riding an escalator, advancing upward, level after level, each one more interesting than the one before. What you actually find at the top will depend on you.

Department of Chemistry Cork Regional Technical College Rossa Avenue, Bishopstown Cork, Ireland

I

" It's a one-year timer. It gives an added sense of urgency to my research grant. "

Erratum

Due to a computer output problem during composition, part of Figure 4 as well as the mathematics from several equations were dropped from "The Trigonometry of Escher's Woodcut "Circle Limit III" ", by H.S.M. Coxeter (vol. 18, no. 4, pp. 42-46). Here we reproduce Figure 4, as well as the corrected text from pp. 45-46. Please also note that the decimal point in "45.3" in the final series of results was incorrectly placed in the original printing.

(1/AB)

q

/'3 =

- AB

1 - AB 2

2 + x/AB

2AB + x

1 - 2-3/2(18 - 10V2 - 1 0 ~ + 6"~/-6) = 21/4(-1 + 2 ~ + V 3 - X/6) + 2-1/4(V2 - 1

=

A

C

02

Figure 4. The similar triangles

= 2-1/4

2_1/4/ CA01

5 - 3 X / 2 - 3"~/-3 + 2X/6

O1AC and 02AB. =

Finally, the triangles

- 9 + 6X/2 + 5"~/3- 3X/6 21/4(3 _ 21~/-3 + X/6)

and

BA02

are similar,

2_1/4(

- 2 + ~/2 + X/3

- 1 + 2X/6

3)

(--1 + 2X/-6)(-2 + 5N/-2 + 3X/-3 + 4X/-6) -3 ( - 2 + V 2 + "V/-3)(-2 + 5X/2 + 3 V 3 + 4V6)

= 2 - 1 / ' 4 ( 5 0 + 13t~/-2 +2317X/-3- 8X/-~ - 3 )

(~v/-3 - 1)(V3 + 2)

r2

~

- 1

rl

G

- 2 = (V6-

=2_1/4(-19+

2)('V~ + X/2) =

13V2+23171r

- 8~f6 )

3 _ X/2 _ V 3 + V/-6 0.3375915 and

and

(1 + V 2 - X/-3)(3 - ~ -

X/3 + "Vf6)= ~v/2(- 1 + 2~72 + X / 3 - N/6);

d3 = r3 + A B

= 2 -3/4 3 + 27~/2 + 7X/3 - 6X/6 23 -~ 0.998189.

hence AB

= 2-3/4(-1 + 2 V 2 + V 3 - X/-6) ~ 0.6605975.

The Third Circle

Since Escher's bounding circle has diameter 41 cm, our results rl -~ 1.10816, r2 ~ 1.8048, r3 ~ 0.3376,

Looking again at Figure 3, we see that

dl ~- 1.3572, d2 ~ 2.2104, d3 ~ 0.9982

d 2 = 1 + r 2 - xr 3

and, since the third circle passes through B,

22.7, 37.0, 6.92,

d3 - r3 = A B .

Thus, 1 - xr3

d3 + r3 - - - , AB

1 - xr3

2r3 - - -

AB

should be multiplied by 20.5 to obtain the distances in centimetres:

AB,

27.8, 45.3; 20.46.

These distances agree perfectly with actual measurements in the w o o d c u t itself. VOLUME 19, NUMBER 1, 1996

79

Abel

N IELS HENRIKABEL (1802-1829) was a Norwegian mathematician who died of tuberculosis at the age of twenty-six. His greatest achievement was to prove the impossibility of solving the general quintic equation by means of radicals. As a result of his work on this problem and others, he received a stipend that enabled him to travel to Germany and France. In Germany he met Leopold Crelle and published many papers in early issues of Crelle's Journal, thereby helping it to become the leading German mathematical journal during the nineteenth century. During his travels he obtained fundamental results on elliptic functions, the convergence of series, and 'Abelian integrals.' His name is also associated with Abel-

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

THE MATHEMATICAL INTELLIGENCER 9 1997 SPRINGER-VERLAG NEW YORK

ian functions, Abel's integral equation, and Abelian groups. Abel's attempts to have his mathematical work recognized by the mathematical community and his lack of success in obtaining an academic post form a sorry tale. Tragically, Abel died just two days before a triumphant letter arrived from Crelle telling him that he had at last been appointed a professor at the University of Berlin. The left-hand stamp below was issued in 1929 as one of a set of four stamps commemorating the 100th anniversary of Abel's death. The right-hand stamp, issued in 1983, depicts Gustav Vigeland's statue of Abel in Oslo. Also shown below is a 500-kroner banknote featuring Niels Abel.