American Mathematical Monthly, volume 105, number 2, February 1998

Volume 105, Number 2

February 1998

Yueh-Gin Gung and Dr. Charles Y. Hu Award for Distinguished Service

105

The Use of Tagged Partitions in Elementary Real Analysis

107

The Dynamics of a Family of One-Dimensional Maps

118

Hunter S. Snevily Douglas B. West

The Bricklayer Problem and the. Strong Cycle Lemma

131

Craig M. Johnson

A Computer Search for Free Actions on Surfaces

144

Division Algebras-Beyond the Quaternions

154

Graphical Discovery of a New Identity for Jacobi Polynomials

163

Philippe Revoy

The Generalized Level of a Non Prime Finite Field Is Two

167

Wolfgang KOhn Zuzana KOhn

Cutting High-Dimensional Cakes

168

Kempe Revisited

170

Linda R. Sons Russell A. Gordon Susan Bassein

John C. McConnell

NOTES Brian Gerard Lawrence Roberts

UNSOLVED PROBLEMS Joan Hutchinson Stan Wagon PROBLEMS AND SOLUTIONS REVIEWS Gerald L. Alexanderson Jean Pedersen William Goldman

175

II

Invertible • Polyhedron Models.

186

Distributed by Snyder Engineering

Topology and Geometry.

192

By Glen E. Bredon TELEGRAPHIC REVIEWS

AN OFFICIAL PUBLICATION OFTHE MATHEMATICAL ASSOCIATION OF AMERICA

195

NOTICE TO AUTHORS The MONTHLY publishes articles, as well as notes and other features, about mathematics and the profession. Its readers span a broad spectrum of mathematical Interests, and include professional mathematicians as well as students of mathematics at all collegiate levels. Authors are invited to submit articles and hotes that bring interesting mathematical ideas to a wide audience of MONTHLY readers. The MONTHLY'S readers expect a high standard of exposition; they expect articles to Inform, stimulate, challenge, enlighten, and even entertain. MONTHLY articles are meant to be read, enjoyed, and discussed, rather than just archived. Articles may be expositions of old or new results, historical or biographical essays, speculations or definitive treatments, broad developments, or explorations of a single application. Novelty and generality are far less Important than clarity of exposition and broad appeal. Appropriate figures, diagrams, and photographs are encouraged; Notes are short, sharply focussed, and possibly informal. They are often gems that provide a new proof of an old theorem, a novel presentation of a familiar theme, or a lively discussion of a single issue. Articles and Notes should be sent to the Editor: ROGER A. HORN 1515 Minerai Square, Room 142 University of Utah Salt Lake City, UT 84112 Please send your email address and 3 copies of the complete manuscript (including all figures with captions and lettering), typewritten on only one side of the paper. In addition, send one original copy of all figures without lettering, drawn carefully in black ink on separate sheets of paper. Letters to the Editor on any topic are invited; please send to the MONTHLY'S Utah office. Comments, criticisms, and suggestions for making the MONTHLY more lively, entertaining, and informative are welcome. See the MONTHLY section of MAA Online for current information such as contents of issues, descriptive summaries of forthcoming articles, tips for authors, and preparation of manuscripts in TEX: http://www.maa.org/ Proposed problems or solutions should be sent to: DANIEL ULLMAN, MONTHLY Problems Departm'ent of Mathematics The George Washington University 2201 G Street, NW, Room 428A Washington, DC 20052 Please send 2 copies of all problems/solulions material, typewritten on only one side of the paper.

EDITOR:

ROGER A. HORN month/[email protected]

ASSOCIATE EDITORS: WILLIAM ADKINS DONNA BEERS RALPH BOAS RICHARD BUMBY JAMES CASE JANE DAY JOHN DUNCAN PETER DUREN GERALD EDGAR JOHN EWING JOSEPH GALLIAN ROBERT GREENE RICHARD GUY PAUL HALMOS GUERSHON HAREL DAVID HOAGLIN

VICTOR KATZ STEVEN KRANTZ JIMMIE LAWSON CATHERINE COLE McGEOCH RICHARD NOWAKOWSKI ARNOLD OSTEBEE KAREN PARSHALL EDWARD SCHEINERMAN ABE SHENITZER WALTER STROMQUIST ALAN TUCKER DANIEL ULLMAN DANIEL VELLEMAN ANN WATKINS DOUGLAS WEST HERBERTWILF

EDITORIAL ASSISTANTS: ARLEE CRAPO NANCY J. DEMELLO Reprint permission: MARCIA P. SWARD, Executive Director Advertising Correspondence: Mr. JOE: WATSON, Advertising Manager Change of address, missing issues inquiries, and other subscription correspondence: MAA Service Center [email protected]

All at the address: The Mathematical Association of America 1529 Eighteenth Street, N.W. Washington, DC 20036 Microfilm Editions: University Microfilms International, Serial Bid coordinator, 300 North Zeeb Road, Ann Arbor, MI 48106. The AMERICAN MATHEMATICAL MONTHLY (iSSN 0002-9890) is published monthly except bimonthly June-July and August-September by the Mathematical Association of America at 1529 Eighteenth Street, N.W., Washington, DC 20036 and Montpelier, VT. Copyrighted by the Mathematical Association of America (incorporated), 1998, including rights to this journal issue as a whole and, except where otherwise noted, rights to each Individual contribution. General permission is granted to Institutional Members of the MAA for noncommercial reproduction in limited quantities of individual articles (in whole or in part) provided a complete reference is made to the source. Second class postage paid at Washington, DC, and additional mailing offices. Postmaster: Send address changes to the American Mathematical Monthly, Membership / Subscription Department, MAA, 1529 Eighteenth Street, N.W., Washington, DC, 200361385.

Yueh-Gin Gung and Dr. Charles Y. Du Award for Distinguished Service to Alice Turner Schafer Linda R. Sons

The curriculum vitae of Alice Turner Schafer lists two specializations: abstract algebra (group theory) and women in mathematics. As early as her high school years Alice exhibited a love for mathematics and an interest in teaching as a career. As a mathematics educator she championed the full participation of women in mathematics. She has been a strong role model for many women, and has worked to establish support groups for women in mathematics, to eliminate barriers women face in their study of mathematics and participation in the mathematics community, and to provide opportunity and encouragement for women in mathematics. She was one of the central figures in the early days of the Association for Women in Mathematics (AWM), through which she has helped to change the place of women in American mathematics. Yet her service goes far beyond her work on behalf of women. Alice Turner is a native of Virginia, where she spent her school years, earning a B.A. in mathematics from the University of Richmond. Lacking the financial means to attend graduate school, she taught secondary school mathematics for three years and then entered the University of Chicago, where she earned an M.S. and a Ph.D. Her dissertation in projective differential geometry was supervised by E. P. Lane and her published research in this area appeared in the Duke Mathematical Journal and in the American Journal of Mathematics. At the University of Chicago Alice met Richard Schafer, who was seeking a Ph.D. in mathematics. They were married as they completed their degrees. Their union has been blessed with two sons and three grandchildren. The Schafers' marriage was an early example of the "two-body problem" and the "commuter marriage." Alice's first postgraduate position was at Connecticut College followed by one at The lohns Hopkins Applied Physics Laboratory. She then held positions at the University of Michigan, Douglass College, Swarthmore College, Drexel Institute of Technology, and the University of Connecticut before 1998]

AWARD FOR DISTINGUISHED SERVICE TO ALICE TURNER SCHAFER

105

returning to Connecticut College where she advanced to full Professor. Moving to Wellesley College (by now Richard was at M.I.T), she soon became department head and the Helen Day Gould Professor of Mathematics, retiring in 1980. Indefatigable, Professor Schafer continued teaching, at Simmon's College and in the management program at Radcliffe College Seminars. Upon Richard's retirement from M.I.T., they moved to Arlington, VA, where Alice became Professor of Mathematics at Marymount University, retiring once again in 1996. While living in the Boston area, Professor Schafer joined with then-graduate student Linda Rothschild and Bhama Srinivasan to organize a group of women mathematicians and students who met every few weeks to discuss common problems and goals. The group anticipated both the A WM and a similar organization in Europe. At the Atlantic City mathematics meetings in 1971, Mary Gray led a women's caucus of the Mathematics Action Group in organizing the A WM. Alice Schafer served as the second president and under her guidance the Association was incorporated, secured financial footing, and established an office at Wellesley College. Professor Schaefer prepared A WM to become a full member of the Conference Board of the Mathematical Sciences, and she and Mary Gray attained international recognition for A WM through its sponsorship of programs at the International Congress of Mathematicians at Vancouver. Essential to the high regard in which A WM is now held by men and women are the excellent mathematical invited talks at its sessions, a feature begun by Schafer. Even after her presidency, Alice Schafer has continued for two decades to give dedicated service and guidance to A WM. Her successors in the presidency rely on her wisdom and good counsel. In recognition of Professor Schafer's contributions, A WM now awards an annual prize in her honor for excellence in mathematics by undergraduate women. Throughout her career, Professor Schafer sought to eliminate barriers to women in mathematics and to promote human rights for all mathematicians. She directed the Wellesley Mathematics Project (continued jointly with Wesleyan University) aimed at reducing fear of mathematics for women. She helped to prepare lists of women who were eligible for grants and fellowships, including invited lectureships. She chaired the AMS Committee on Postdoctoral Fellowships and the Committee on Human Rights, and served on Committee Wand the National Council for the American Association of University Professors. She has chaired the mathematics section of the American Association for the Advancement of Science. Professor Schafer has served on the CBMS Committee on Women in the Mathematical Sciences for six years and has worked for many years for the MAA Women and Mathematics Program. Three times in recent years, through the People-to-People program, she led delegations to China-one connecting women research mathematicians, one concerning mathematics education, and one concerning women's issues in mathematics and science. Professor Schafer is known for her love of people, her boundless energy, and her fierce determination for a just cause. Her lifetime achievements and her pioneering efforts to secure opportunities for all mathematicians make her a most worthy recipient of the Yueh-Gin Gung and Dr. Charles Y. Hu award for Distinguished Service to Mathematics. Northem Illinois University, DeKalb, IL 60115-2854 [email protected]

106

AWARD FOR DISTINGUISHED SERVICE TO ALICE TURNER SCHAFER

[February

The Use of Tagged Partitions in Elementary Real Analysis Russell A. Gordon

The purpose of this paper is to present alternate proofs of several well known results in elementary real analysis. An alternate proof of a theorem provides a new way of looking at the theorem and this fresh perspective is often enough to justify the new approach. However, a new proof of an old result that is conceptually easier and points the way to generalizations of the result has obvious benefits. This is the case, in my opinion, for several of the proofs presented in this paper. The results to be considered here all depend on the Completeness Axiom; every nonempty bounded set of real numbers has a supremum. Throughout this paper, the universe is the set of real numbers, denoted by R. Several useful statements that are equivalent to the Completeness Axiom are given in the following list: 1. 2. 3. 4.

Every Cauchy sequence converges. Every bounded monotone sequence converges. Every bounded sequence contains a convergent subsequence. The intersection of a nested sequence of closed and bounded intervals is non empty.

One of these equivalent statements provides the theoretical basis for results such as the Intermediate Value Theorem, the Extreme Value Theorem, and the integrability of continuous functions. All of the proofs in this paper use a consequence of the Completeness Axiom that involves tagged partitions of an interval. The motivation for this concept can be found in the theory of the Riemann integral. Although tagged partitions usually appear only in the context of Riemann sums, we will show that tagged partitions can be used successfully to prove results about differentiable functions and continuous functions as well. In other words, the method of tagged partitions is quite versatile. For the reader who chooses to skim this article as opposed to reading it fully, I would like to highlight the proofs of Theorems 3, 10, and 14. The proof of Theorem 3 is a good illustration of this new approach while the proofs of Theorems 10 and 14 are simpler than the standard proofs found in current textbooks. We begin with the definition of 8-fine tagged partitions. This concept has its origins in the theory of the Henstock integral. A thorough treatment of the Henstock integral can be found in [2]. Definition. A partition of an interval [a, b] is a finite collection of non-overlapping closed intervals whose union is [a, b]. A tagged partition of [a, b] is a partition of [a, b] with one point, referred to as the tag, chosen from each interval comprising the partition. A tagged partition of [a, b] will be denoted by {(C i , [Xi-I' xJ): 1 .:::; i .:::; n}, where a =xo <Xl <X 2 < ... < XIl-I <Xn = b

and c i E [Xi-I' xJ is the tag of the interval [Xi-I' xJ for each index i. Now let 8 be a positive function defined on [a, b]. A 8-fine tagged partition of [a, b] is a 1998]

THE USE OF TAGGED PARTITIONS

107

tagged partition {(C i , [Xi-I' xJ): 1 ~ i ~ n} of [a, b] that satisfies [Xi-I,XJ ~ (c i - 8(cJ,c i + 8(cJ) for each index i. In words, the positive function 8 (which is often referred to as a gauge) determines the size of the interval associated with a given tag. In the theory of the Riemann integral, the function 8 is a constant function that determines the mesh size of the partition. The introduction of the positive function 8 leads to a subtle but profound change in focus. It takes a few moments of reflection to grasp fully the concept of a 8-fine tagged partition and some experience with such partitions to appreciate the extent to which they can be used. In applications that involve the use of 8-fine tagged partitions, the positive function 8 is usually designed to guarantee that something "good" happens. Here are some specific examples that give some idea of the versatility of the function 8; the proofs presented in this paper provide further illustrations. 1. Suppose that 8: [0, 1] ~ R is defined by

8 ( x) =

{X /2, ~ 0 ~ x ~ 1; .01, If x - o.

Note that the interval (x - 8(x), x + 8(x)) does not contain 0 unless x = o. Consequently, any 8-fine tagged partition of [0, 1] must have 0 as a tag. Using similar ideas, it is possible to force any finite number of points to be tags. 2. Let {Ik} be a sequence of open intervals in (a, b), let G = U ~~ Ilk' and let H = [a, b] \ G. For each x E G, there exists an index k and a positive number 8(x) such that (x - 8(x), x + 8(x)) ~ I k • (In essence, 8(x) represents the distance from the point x to the closed set H.) For each x E H, let 8(x) = 1. This defines a positive function 8 on [a, b]. Suppose that {(C i , [Xi_I> xJ): 1 ~ i ~ n} is a 8-fine tagged partition of [a, b] and let So = {i: ci E G}. Since the intervals in the partition are non-overlapping, 00

E

E [Uk)'

(Xi - Xi-I) ~

k~l

iES G

where [Uk) denotes the length of the interval I k . In addition, if [Xi-I' xJ n =1= 0, then c i E H. That is, any tagged interval that intersects H has a tag that belongs to H and the sum of the lengths of the intervals that do not intersect H is governed by the sequence {Ik}. 3. Suppose that F: [a, b] ~ R is differentiable at each point of [a, b] and let E > O. For each x E [a, b], there exists 8(x) > 0 such that H

IF(t) - F(x) - F'(x)(t -

x)1

~

Elt - xl

for all t E [a, b] that satisfy It - xl < 8(x). If {(Ci,[X i - I ' Xi)): 1 ~ i ~ n} is a 8-fine tagged partition of [a, b], then (omitting some algebraic details)

li~ P'(cJ(xi -

xi-d - (F(b) - F(a))

=Ii~ (F'(cJ(Xi -Xi-I) -

I

(F(xJ -F(Xi-d))1

n

~

E IF'(cJ(x i -

Xi-I) - (F(xJ - F(xi-d)1

i~l

n

~

E E(Xi -

xi-d

i~l

=E(b-a).

108

mE USE OF TAGGED PARTITIONS

[February

In other words, every 8-fine tagged partition of [a, b] generates a Riemann sum of F' that is close to F(b) - F(a). This represents a proof that, in some sense, every derivative is integrable and this observation is the motivation for the development of the Henstock integral. The interested reader should consult [1] for an elementary discussion of the generality of this integral. When working with the Riemann integral, one normally thinks of the intervals as being chosen first (each interval with length less than a prescribed constant 8) then a tag is picked for each interval. There is no question as to the existence of tagged partitions in this case. The positive function 8 essentially reverses this process. The tags must be chosen first; then intervals of the "right size" are chosen for each tag. For an arbitrary positive function 8, the existence of 8-fine tagged partitions is no longer obvious. If the infimum of the set {8(x): x E [a, b]} is positive, then it is clear that 8-fine tagged partitions of [a, b] exist-this is essentially the constant 8 case once again. If the infimum is 0 (as is the case in Examples 1 and 2), then a proof of the existence of 8-fine tagged partitions is required. This is the content of the following theorem. Theorem 1. If 8 is a positive function defined on the interval [a, b], then there exists a 8-fine tagged partition of [a, b].

Proof" Let E be the set of all points x E (a, b] for which there exists a 8-fine tagged partition of [a, x]. The set E is not empty since it contains the interval (a, a + 8(a))-the one element set {(a, [a, x])} is a 8-fine tagged partition of [a, x] for each x E (a, a + 8(a)). Let z = sup E and note that z E [a, b]. To complete the proof, it is sufficient to prove that z belongs to E and that z = b. E or there is a point u E E such that z - 8(z) < !Jli be a 8-fine tagged partition of [a, u] and let !Jli 1 =!Jli U {(z, [u, z])}. Then !Jli 1 is a 8-fine tagged partition of [a, z] and this shows that z E E. Now suppose that z < b. Let v be a point in [a, b] such that z < v < z + 8(z) and let !Jli 2 =!Jli1 U {(z, [z, v])}. Then !Jli2 is a 8-fine tagged partition of [a, v] and it follows that vEE, a contradiction to the fact that z is an upper bound of the set E. We conclude that z = b. •

u

Since z = sup E, either z E < z. In the latter case, let

This proof of the existence of 8-fine tagged partitions makes direct use of the Completeness Axiom. One may also prove this result using the Nested Intervals Theorem (statement 4 in the introduction); the details are left to the reader. When requested to give a proof of this result, students often try a direct approach; the actual construction of a 8-fine tagged partition. This is not difficult if the number of points where the function 8 "goes to 0" is finite. Such attempts by students offer good opportunities to discuss the full generality of functions and sets. The similarities between the proof of the existence of 8-fine tagged partitions of [a, b] and the proof (at least one of the standard proofs) that the interval [a, b] is a compact set are evident. This is no accident-the two statements are actually equivalent. However, compact sets are a difficult concept for many students since the typical student finds open covers, finite subcovers, and manipulations with large collections of sets rather abstract. A positive function 8 seems easier to visualize and the end result, a tagged partition, is easy to grasp: start with a piece of string, cut it into pieces of various lengths, and mark a point on each piece. In addition, the definition of a 8-fine tagged partition seems a little more motivated than the open cover definition of a compact set. For the record, I am not 1998]

THE USE OF TAGGED PARTITIONS

109

advocating the elimination of the concept of compact sets; I just feel that this concept should not appear early in a first course in real analysis. Tagged partitions can be used to prove the standard results on continuous functions that involve the Completeness Axiom such as the Intermediate Value Theorem, the Extreme Value Theorem, and the uniform continuity theorem. The usual proofs of these results use properties of st?quences and are not difficult. The proofs using 8-fine tagged partitions are not any easier, but they do illustrate another way to think about these theorems. In this method of proof for the Intermediate Value Theorem, the existence of the positive function 8 is a simple consequence of the definition of a continuous function. However, unlike the proof using the Nested Intervals Theorem, the following proof does not yield a method for finding the point c. Theorem 2. Suppose that f: [a, b] ~ R is continuous on [a, b]. If L is a number between fCa) and fCb), then there exists a point c E (a, b) such that fCc) = L. Proof' Suppose that f(a) < L < f(b); the proof for f(b) < L < fCa) is similar. Assume that fCx) =1= L for all x E [a, b]. Since f is continuous at each point x of [a, b], if fCx) < L, there satisfy It - xl < if f(x) > L, there satisfy It - xl <

exists 8(x) > 0 such that fCt) < L for all t 8(x); exists 8(x) > 0 such that f(t) > L for all t 8(x).

E

[a, b] that

E

[a, b] that

This defines a positive function 8 on [a,b]. Let {(Ci,[xi_px;l): 1 ~ i ~ n} be a 8-fine tagged partition of [a, b]. Note that for each index i either f(x) < L for all x E [Xi-I' x;l or f(x) > L for all x E [Xi-I' xJ Since f(x o) = f(a) < L, we find that f(x) < L for all x E [x o, Xl]. Since f(x l ) < L, we find that f(x) < L for all x E [Xl' x 2 ]. After a finite number of similar steps, we find that f(b) = f(x n ) < L, a contradiction. Hence, there exists a point c E (a, b) such that fCc) = L. • We next prove that a continuous function defined on [a, b] is bounded on [a, b]. The proof of this result using subsequences is an indirect proof, but with 8-fine tagged partitions, a direct proof is possible. Theorem 3. Iff: [a, b]

~

R is continuous on [a, b], then f is bounded on [a, b].

Proof' Since f is continuous on [a, b], for each X E [a, b] there exists a positive number 8(x) such that If(t) - f(x)1 < 1 for all t E [a, b] that satisfy It - xl < 8Cx). This defines a positive function 8 on [a, b]. Let {Cc i , [Xi-I' xJ): 1 ~ i ~ n} be a 8-fine tagged partition of [a, b] and let M = max{ If(c) I: 1 ~ i ~ n}. Given a point X E [a, b], there is an index j such that X E [x j _ P x) and thus If(x)1 ~ If(x) - f(cj)1 + If(cj)1 < 1 + M. This shows that the function f is bounded by 1 + M.

•

The proof of the preceding result reveals that the continuity hypothesis is not all that crucial. The continuity of f at the point x is only used to obtain a local bound for the function f. A function f is locally bounded at a point x if there exist positive numbers M and 8 such that If(t) I ~ M for all t that satisfy It - xl < 8. A slight modification in the proof of Theorem 3 yields the following stronger result. 110

THE USE OF TAGGED PARTITIONS

[February

Theorem 4. If f: [a, b] ~ R is locally bounded at each point of [a, b], then f is I bounded on [a, b]. Proof' Since f is locally bounded at each point of [a, b], for each x E [a, b] there exist positive numbers M(x) and 8(x) such that If(t) I .::;; M(x) for all t E [a, b] that satisfy It - xl < 8(x). This defines a positive function 8 on [a, b]. Let {(c i , [X i - i , Xi)): 1.::;; i .::;; n} be a 8-fine tagged partition of [a, b] and let M = max{M(c): 1 .::;; i .::;; n}. Given a point x E [a, b], there is an index j such that x E [x j _ i , x) and thus If(x) I .::;; M(c j ) .::;; M. This shows that the function f is bounded by M. •

Corollary 5. Iff: [a, b] ~ R has one-sided limits at each point of [a, b], then f is bounded on [a, b]. Proof' It is a routine exercise to prove that a function with one-sided limits at a

point is locally bounded at that point.

•

The Extreme Value Theorem states that a continuous function defined on a closed interval [a, b] assumes its maximum and minimum values. Once it has been established that such a function is bounded on [a, b] (Theorem 3), it is necessary to find points c, d E [a, b] such that f(d .::;; f(x) .::;; f(d)for all x E [a, b]. One way to proceed is to let M = sup{f(x): x E [a, b]}, assume that f(x) < M for all x E [a, b], and define a continuous function g on [a, b] by g(x) = 1/(M - f(x)). The fact that g is then bounded on [a, b] leads to a contradiction. Here is a proof that makes direct use of 8-fine tagged partitions. Theorem 6. Iff: [a, b] ~ R is continuous on [a, b], then there exist points c, d E [a, b] such that f(c) .::;; f(x) .::;; f(d) for all x E [a, b]. Proof' We prove that there exists a point d E [a, b] such that f(x) .::;; f(d) for all x E [a, b]; the proof of the existence of a point c is quite similar (or one can consider the function -f). Let M = sup{f(x): x E [a, b]} and suppose that f(x) < M for all x E [a, b]. Since f is continuous on [a, b], for each x E [a, b] there exist positive numbers 8(x) and a(x) such that f(t) < M - a(x) for all t E [a, b] that satisfy It - xl < 8(x). (For example, one could let a(x) = (M - f(x)) /2.) This defines a positive function 8 on [a, b]. Let {(c i , [X i - i , x;l): 1 .::;; i .::;; n} be a 8-fine tagged partition of [a, b], let a = min{ a(c): 1 .::;; i .::;; n}, and note that a is a positive number. Fix x E [a, b] and choose an index j such that x E [xj-l> x j ]. It follows that f(x) <M- a(c j ) .::;;M- a.

This inequality, valid for all x E [a, b], contradicts the definition of the number M. Hence, there exists a point d E [a, b] such that f(d) = M and it follows that f(x) .::;;f(d)forall x

E

[a,b].

•

Another familiar result about continuous functions that involves the Completeness Axiom is the fact that a continuous function on the closed interval [a, b] is uniformly continuous on [a, b]. The typical proof of this fact either uses sequences and the Bolzano-Weierstrass Theorem or open covers and the Heine-Borel Theorem. Since the Completeness Axiom lies behind the proof of this result, the uniform continuity theorem can also be proved using 8-fine tagged partitions. The 1998]

THE USE OF TAGGED PARTITIONS

111

following proof is similar to the proof that uses the Heine-Borel Theorem, but it does not require the full power of compact sets. Theorem 7. Iff: [a, b] [a, b].

~

R is continuous on [a, b], then f is uniformly continuous on

Proof' Let E> O. For each x E [a, b] choose 8(x) > 0 so that If(O - f(x)1 < E/2 for all t E [a, b] that satisfy It - x I < 2 8(x). This defines a positive function 8 on [a, b]. Let {(C i , [Xi-I' x;l): 1 ~ i ~ n} be a 8-fine tagged partition of [a, b] and let 8 = min{8(c): 1 ~ i ~ n}. Suppose that s, t E [a, b] with It - sl < 8 and choose an index j such that s E [x j - I , x) Note that

Is - cjl < 8(c j ); It - cjl ~ It -

sl + Is - cjl < 8 + 8(c j )

~

28(c j ).

It follows that

If(t) - f(s)1 ~ If(t) - f(cj)1

This shows that the function

+ If(c j ) - f(s)1 < E.

•

f is uniformly continuous on [a, b].

It is possible to use 8-fine tagged partitions to extend the previous result and several others as well to the case in which the domain of the function is an arbitrary closed and bounded set rather than a closed and bounded interval. We will consider a set to be closed if its complement is an open set (and assume that the reader is familiar with open sets). To illustrate the adjustments that are necessary, we will prove the following result. Theorem 8. Let K be a closed and bounded set. Iff: K f is uniformly continuous on K.

~

R is continuous on K, then

Proof' Let a = inf K and let b = sup K; then K ~ [a, b] and a, bE K. Let E> O. Define a positive function 8 on [a, b] as follows:

if x E K choose 8(x) > 0 so that If(t) - f(x) I < E/2 for all t E K that satisfy It - xl < 28(x); if x E [a, b] \K choose 8(x) > 0 so that (x - 8(x), x + 8(x)) n K = 0. Let {(Ci,[Xi-l,x;l): 1 ~ i ~ n} be a 8-fine tagged partition of [a,b]. By the definition of 8, it follows that ci E K whenever [Xi-I' x;l n K =1= 0. Let SK = {i: c i E K} and let 8 = min(8(c): i E SK}' Suppose that s, t E K with It - sl < 8 and choose an index j such that s E [x j - I , x) Note that

Is - cjl < 8(c j ); It - cjl ~ It -

Since cj

E

sl + Is - cjl < 8 + 8(c j )

~

28(c j ).

K, it follows that

If(t) - f(s)1 ~ If(t) - f(cj)1

This shows that the function

+ If(c j ) - f(s)1 <

f is uniformly continuous on K.

E.

•

We now turn to integration theory and prove that continuous functions are Riemann integrable. The typical proof of this result uses the uniform continuity of a continuous function on a closed and bounded interval. The use of 8-fine tagged 112

THE USE OF TAGGED PARTITIONS

[February

partitions to prove that continuous functions are Riemann integrable eliminates the need to mention uniform continuity. The proof of this result involves the Cauchy criterion for Riemann integrability and there are various ways to formulate this criterion. For our purposes, a function f is Riemann integrable on [a, b] if and only if for each E> 0 there exists a partition {[X i - 1' x;l: 1 ~ i ~ n} of [a, b] such that n

E w(j, [X i- 1 , X;])(Xi -

Xi-i)

<

E,

i=l

where the oscillation, w(f, [c, d]), of the function f on the interval [c, d] is defined by w(f,[c,dD

= sup{lf(t) - f(s)l: s,t

E

[c,d]}.

It provides one measure of the variability of a function in an interval.

Theorem 9. Iff is continuous on [a, b], then f is Riemann integrable on [a, b]. Proof" Let E > O. Since f is continuous on [a, b], for each X E [a, b] there exists 8(x) > 0 such that If(t) - f(x)1 < E for all t E [a, b] that satisfy It - xl < 8(x). This defines a positive function 8 on [a, b]. Let {(c i , [X i -l' xJ): 1 ~ i ~ n} be a 8-fine tagged partition of [a, b]. Based upon the definition of 8, it is easy to see that w(f, [Xi-l' Xi]) ~ 2E for each index i. It follows that n

n

Ew(j,[x i -l>x;])(X i -x i -d ~ E2E(X i -X i - 1 ) =2E(b-a). i=l i=l

Hence, the function

f is Riemann integrable on [a, b].

•

An interesting and important result in the theory of the Riemann integral concerns necessary and sufficient conditions for a function to be Riemann integrable: a function f is Riemann integrable on [a, b] if and only if f is bounded and continuous almost everywhere on [a, b]. Recall that a set E has measure zero if for each E > 0 there exists a sequence Uk} of open intervals such that E ~ U k=l Ik and L,k=ll(Ik) < E; a property is said to hold almost everywhere if it fails to hold only at points in a set of measure zero. It is not difficult to prove that a Riemann integrable function is bounded and continuous almost everywhere. The proof of the converse is more difficult. Consequently, this result (or at least its proof) is usually omitted in introductory real analysis courses. The proofs that I have seen (not including those involving the Lebesgue integral) require a knowledge of compact sets and the details of the construction of the partition are quite tedious. The proof given here is the simplest one that I have found. Note the similarities between the following proof and the proof of Theorem 9. In particular, the use of uniform continuity to prove the preceding result clouds the essential issues involved with Riemann integrability. Theorem 10. Iff is bounded and continuous almost everywhere on [a, b], then f is Riemann integrable on [a, b]. Proof" Let M be a bound for the function f on [a, b], let D be the set of all points f is not continuous at x, and let E > O. Since D has measure zero, there exists a sequence Uk} of open intervals such that D ~ U k=l Ik and

x E [a, b] such that

1998]

THE USE OF TAGGED PARTITIONS

113

< elM. Define a positive function 8 on [a, b] as follows: if x$. D use the continuity of f at x to choose 8(x) > 0 so that If(t) - f(x)1 < e/2 for all t E [a, b] that satisfy It - xl < 8(x); if xED choose 8(x) > 0 so that (x - 8(x), x + 8(x» ~ Ik for some index k.

r.k~ll(Ik)

Let {(C i , [X i - 1, xJ): 1 ~ i

~ n}

So = {i: Since the intervals

be a 8-fine tagged partition of [a, b] and define $.

Ci

[X i - 1 ' Xi]

D}

and

SD = {i:

Ci

ED}.

are non-overlapping, we find that

n

E w(f, [X i - 1 , x;l)( Xi

- xi-d

i~l

~

E

e( Xi

- Xi-l)

~ e(b - a)

+ 2M

+

E

2M( Xi

- Xi- 1)

E IUd k~l

< e(b - a + 2). Hence, the function

f is Riemann integrable on [a, b].

•

Finally, we consider the use of 8-fine tagged partitions to prove results in which the derivative is involved. One of the simplest results of this type is the fact that a function with a positive derivative on an interval is increasing on that interval. This result is usually proved in calculus textbooks as an easy application of the Mean Value Theorem. Tracing the roots of the Mean Value Theorem leads to the Extreme Value Theorem, so it becomes apparent that the Completeness Axiom is needed in the proof of this monotonicity result. Since there are several intermediate results prior to the Mean Value Theorem (in the usual scheme), it is easy to forget that the Completeness Axiom is relevant to this result. There are several advantages to the proof given here-namely, the Completeness Axiom is more apparent, continuity is not used explicitly, and few preliminary results are needed. We want to prove that a function that has a positive derivative at each point of an interval is increasing on that interval. As a reminder that there is indeed something to prove here, consider the function F: [ -1, 1] -7 R defined by F(x)

=

{X/2 + X2 sin(1/x), 0,

if x =1= 0; if x = o.

This function has a positive derivative at 0, but it is not increasing on any open interval that contains O. This indicates that a proof of some sort is needed for the result under discussion. The purpose of the mono tonicity result is to extract global information (F is increasing on an interval) from local information (F ' is positive at each point). Theorem 11. Suppose that F: [a, b] -7 R is differentiable at each point of [a, b] (appropriate one-sided limits are assumed at a and b). If F'(x) > 0 for each x E [a, b], then F is increasing on [a, b]. 114

THE USE OF TAGGED PARTITIONS

[February

Proof' For each x E [a, b] use the fact that F'(x) > 0 to choose 8(x) > 0 so that F(t) - F(x)

----->0 t-x

for all t E [a, b] that satisfy 0 < It - xl < 8(x). This defines a positive function 8 on [a, b]. Suppose that a :::;; u < v :::;; b and let {(Ci' [Xi-I> xJ): 1 :::;; i :::;; n} be a 8-fine tagged partition of [u, v]. For each index i, we find that F(Xi-l) :::;; F(c) :::;; F(x) and at least one of these inequalities is strict. It follows that n

F(v) - F(u) =

E (F(x;)

- F(Xi-d)

>

0

i=1

which is equivalent to F(u) < F(v). Therefore, the function F is increasing on [a, b]. • The statement of Theorem 11 is not quite as general as that found in most calculus books. Using a simple continuity argument, one can use the preceding result to prove the following result. Theorem 12. Suppose that F: [a, b] ~ R is continuous on [a, b] and differentiable at each point of (a, b). If F'(x) > 0 for each x E (a, b), then F is increasing on [a, b].

Variations of the argument found in the proof of Theorem 11 can be used to prove the following facts: a. If F'(x) ~ 0 for each x b. If F'(X) = 0 for each x

E

E

[a, b], then F is nondecreasing on [a, b]. [a, b], then F is constant on [a, b].

However, it is also possible to use Theorem 11 to prove each of these facts. The details are left for the interested reader. In addition, the hypotheses of Theorem 11 can be weakened in several ways. Some of these versions of the monotonicity result involve upper and lower derivates, but we will be content to prove a simpler version. This version illustrates how 8-fine tagged partitions can deal with an exceptional set that is countable. A property is said to hold nearly everywhere if the set of points where it fails to hold is countable. Theorem 13. Suppose that F is continuous on [a, b]. If F is differentiable nearly everywhere on [a, b] and if pi > 0 nearly everywhere on [a, b], then F is nondecreasing on [a,b]. Proof: Let D be the set of all points x E [a, b] such that either F I (x) does not exist or F'(x) :::;; 0 and express D as a sequence {d k : k E Z+}. Let E> O. For each x E [a, b] \D; use the fact that F'(x) > 0 to choose 8(x) > 0 so that F(t) - F(x)

----->0 t-x

for all t E [a, b] that satisfy 0 < It - xl < 8(x). If x = d k , use the continuity of F at x to choose 8(x) > 0 so that IF(t) - F(x)1 < E/2 k for all t E [a, b] that satisfy It - xl < 8(x). This defines a positive function 8 on [a, b]. Suppose that a :::;; u < v :::;; b and let {(c i , [Xi-I> xJ): 1 :::;; i :::;; n} be a 8-fine tagged partition of [u, v]. By combining intervals if necessary, we may assume that each tag occurs only once. 1998]

THE USE OF TAGGED PARTITIONS

115

Let So

=

{i:

Ci

$.

D}

and

SD

=

{i: ci ED}.

Note that F(x) - F(X i_ l ) > 0 for each i E So and that F(x) - F(X i- l ) > -2(E/2 k ) for some unique k for each i E SD. It follows that n

F(v) - F(u) =

E (F(x;)

- F(X i- I ))

i~l

=

E

(F(x;) - F(Xi_d)

+

E

(F(x;) - F(xi-d)

= -2E. Since E > 0 was arbitrary, we find that F(v) nondecreasing on [a, b].

~

F(u). Therefore, the function F is •

Our final result is the fact that an absolutely continuous singular function is constant. This result, which is outside the realm of elementary real analysis, is important in Lebesgue integration theory. In most current textbooks (see [3] for instance), the proof of this result uses the Vitali Covering Lemma. This lemma is familiar to students at this level since it is used in the proof that monotone functions are differentiable almost everywhere. Since the. concepts involved in the Vitali Covering Lemma are difficult for many students, the following proof may be easier to understand. Theorem 14. Suppose that F is absolutely continuous on [a, b]. If F' = 0 almost everywhere on [a, b], then F is constant on [a, b].

Proof: Let E be the set of all points x E [a, b] for which either F'(x) does not exist or F'(x) =1= O. By hypothesis, the set E has measure zero. Let E > 0 and choose a positive number YJ such that L:i~IIF(t) - F(s)1 < E whenever Us i, tJ: 1 ~ i ~ n} is a finite collection of non-overlapping intervals in [a, b] that satisfy L:i~llti - sil < YJ. Since E has measure zero, there exists a sequence Uk} of open intervals such that E ~ U~~IIk and L:~~II(Ik) < YJ. Define a positive function l5 on [a, b] as follows: if x $. E use the fact that F'(x) = 0 to choose l5(x) > 0 so that IF(t) - F(x)1 ~ Elt - xl for all t E [a, b] that satisfy It - xl < l5(x); if x E E choose l5(x) > 0 so that (x - l5(x), x + l5(x)) ~ Ik for some index k. Let {(C i , [Xi-I' Xi]): 1 ~ i ~ n} be a l5-fine tagged partition of [a, b] and define So = {i: c i $. E}

and

SE = {i: ci

Note that IF(x) - F(Xi-I)1 ~ E(X i - Xi-I) for each i

E iES E

116

(Xi - xi-d ~

E l(Ik)

E

<

E}.

E

So and that

YJ.

k~l

THE USE OF TAGGED PARTITIONS

[February

It follows that

IF(b) -F(a)1 =liE(F(X;) -F(Xi_1))1 ~L IF(x;) - F(Xi_1)1

~

L

E(Xi -xi-d +

+

L

IF(x;) - F(Xi_1)1

E

iESo

~E(b-a+l).

Since E > 0 was arbitrary, we find that F(b) = F(a). Similarly, it can be shown that F(x) = F(a) for all x E (a, b). This completes the proof. • My aim in this paper has been to demonstrate the versatility of 8-fine tagged partitions and their use outside the context of integration theory. Although I do not anticipate the use of 8-fine tagged partitions to transform the teaching of real analysis, I hope this discussion provides new insight into old results. By introducing 8-fine tagged partitions early, the transition to integration theory and the abstract notion of a compact set can be made easier. In addition, some of the ideas here would make good "research" questions for advanced undergraduates. REFERENCES 1. R. G. Bartle, Return to the Riemann Integral, Amer. Math. Monthly 103 (1996), 625-632. 2. R. A. Gordon, The integrals of Lebesgue, Denjoy, Perron, and Henstock, Graduate Studies in Mathematics, Vol. 4, American Mathematical Society, Providence, RI, 1994. 3. H. L. Royden, Real analysis, 3rd ed., Macmillan, New York, 1988.

RUSSELL A. GORDON received a BA from Blackburn College, an MS from Colorado State University, and a PhD from the University of Illinois. His dissertation, written under the influence of Jerry Uhl, mutated into a graduate textbook on nonabsolute integration. He has also written a textbook on elementary real analysis, which explains his current interest/preoccupation with this subject. Beyond academia, his three sons keep him busy, especially an active 3 year old. A weekly date with his wife Brenda is a welcome change of pace from a very busy life. He also enjoys running, playing basketball, and hiking in the mountains. Whitman College, Walla Walla, WA 99362 [email protected]

1998]

TIlE USE OF TAGGED PARTITIONS

117

The Dynamics of a Family of One-Dimensional Maps Susan Bassein

The purpose of this paper is to classify the dynamics of the following two-parameter family of very simple maps from the unit interval to itself: for given < a < 1 b :;:; 1, let [ be the map from [0, 1] to [0, 1] whose graph consists of two and straight line segments extending from (0, b) to (a, 1) to (1,0), as illustrated in Figure 1.

°

°:;:;

y

b

~--------~------------~---x

a Figure 1. The graph of I(x) with a

=

0.4 and b

=

0.3.

Algebraically, I - b

[(x) =

{

b+--x

ifO:;:;x
1_ x a I-a

ifa:;:;x:;:;1.

It is not hard to see that any interesting dynamics of any map from [0, 1] to [0, 1] whose graph consists of two, joined line segments ends up (after scaling and reflecting as necessary) in a square region in which the graph meets the left edge, has its peak on the top edge, and descends to the lower right corner, as illustrated in Figure 1. Despite the simplicity of its maps, this family exhibits a surprising variety of dynamics. In Section 2 we see non-chaotic maps with attracting and non-attracting periodic behavior. In Section 3 we show that every map in the family with a

118

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

[February

non-degenerate homoclinic point exhibits chaotic behavior. Section 3 also clarifies the meaning of one commonly-used criterion in the definition of chaos. Section 4 is devoted to maps that are chaotic on the entire interval [0, 1] and have no attracting periodic behavior. In Section 5 we provide an elementary example of the general concept of renormalization by investigating maps that absorb all the points of [0, 1] into subintervals on which there is chaos that mimics the dynamics seen on the whole interval in Section 4. In Section 6 we complete the classification by describing an infinite sequence of maps that alternate between having and not having attracting periodic behavior amid the chaos. I chose to study maps of the form shown in Figure 1 because they closely resemble the mathematical models of electronic circuits described in [1] and [2]. Because we need only elementary geometry and algebra to obtain our results, our analysis can be used in an early introduction of dynamical systems to students [7]. For example, one could give undergraduates (or even strong high school students) the general outline of our analysis and ask them to fill in the details of some or all of the sections, depending on their level and abilities, as an independent project. A more challenging project would be to try to extend the analysis to a wider class of maps, such as those with graphs made from two curves with either fixed or bounded concavity. A particular map in this family was studied in [6]; see [4] and [5] for more general analyses of one-dimensional dynamics. 1. PRELIMINARIES. The orbit of a point x under a map I is the set of IO(x) = x, Il(X) = I(x), 12(X) = l(j(x», P(x) = l(j(j(x»), and so on. To determine the dynamics of I means to describe the orbits of all points in the domain of I. In particular, a point x is periodic if there is an n > such that rex) = x. The smallest such n is called the prime period of x and the orbit of x is called an

°

n-cycle.

Throughout this paper, I and J represent closed intervals larger than a single point. The length of an interval I is deno~ed by III. The images of a set Sunder repeated mapping by I are denoted I(S), 12 (S), and so on. Because our maps are continuous, the images of I are also closed intervals. A map I from an 'infinite subset S of [0, 1] to itself is chaotic if: (1) it is topologically transitive: if U and V are open intervals, each of which contains a point in S, there is an n > such that r(U Ii S) and V Ii S

°

have a point in common and (2) periodic points are dense in S: if U is an open interval that contains a point of S, then it contains a periodic point in S. Although the traditional definition of chaos [5, p. 50] includes the criterion of sensitive dependence, [3] shows that sensitive dependence follows from (1) and (2). Further, if S is all of [0, 1], then [8] shows that even (2) is a consequence of (1).

Intuitively, (1) means that even if the orbit of a particular point in S doesn't "wander" throughout S, the set of orbits of its neighbors in S does. Section 3 provides some insight into the significance of (2). We can trace the single application of the map to a point x by drawing line segments from (x, x) to (x,/(x» to (j(x),/(x», as illustrated in Figure 2. A portion of the orbit of x can be drawn by repeating this process to move from (j(x), I(x» to (j(x), 12(X» to (j2(X), j2(x», and so on. Note that the map has a fixed point at x = 1/(2 - a), where the graph crosses the line y = x, which means 1998]

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

119

y

~

_ _ _ _ _ _ _ _ _ _ _ _ _ _- L_ _ _ _ _ _ _ _

~__

X

c

Figure 2. The fixed point c and a portion of the orbit of x

=

0.15.

that /(1/(2 - a» = 1/(2 - a). For notational convenience, we denote this fixed point by c. Because the absolute value of the slope of the graph is greater than 1 at the fixed point, the fixed point is repelling, which means that points near the fixed point are mapped further away from the fixed point. In particular, if I c [a, 1], then 1/(1)1 > III because 1/(1)1/111 = Islopel = 1/(1 - a) > 1. To classify the dynamics of the maps in the family, we interpret the a and b of each map as the coordinates of a point in a unit square in (a, b)-space and decompose that square into the regions shown in Figure 3. Each region corresponds to a subfamily of maps that have similar dynamics and can be analyzed by means of the same general strategy.

b

L-________________________~__ a

Figure 3. Regions of different dynamics in (a, b)-space.

120

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

[February

2. NON-CHAOTIC DYNAMICS WITH AND WITHOUT AN ATTRACTING CYCLE. The simplest region to analyze is the one defined by b > 1 - a + a 2 , which is shaded in the diagram on the left in Figure 4. The significance of this inequality results from 1 - a + a 2 > a and f(l - a + a 2) = a, which, as shown by the dashed lines in the graph in the middle of Figure 4, implies that f([O, aD c [b,l] £; [1 - a + a 2, 1] so that f2([O, aD = [0, feb)] £; [0, a]. y

b

y a

a b

--"'_a

l . . . - -_ _ _

"'-----------'-- x

"---------'- x

Figure 4. The region with b > 1 - a + a 2 , a typical graph, and an attracted orbit.

Because f is linear on both [0, a] and [a, 1], f2 is linear on [0, a]. It follows that if Ie [0, a], then If2(I)1 = (f2(0)/a) III < III. In particular, there is a point x E [0, a] for which f2(X) = x and for every y E [0, a],. y =F x we have If2(y) - f2(X)

1= (J2(0)/a)ly -

xl < Iy - xl·

This inequality implies that, as illustrated on the right on Figure 4, the 2-cycle {x, f(x)} is attracting. Further, the basin of attraction is all of [0, 1] except the fixed point, which means the orbit of every point except c approaches the 2-cycle, because, as one can see from the graph, the orbit of every point except c eventually enters the interval [0, a]. In particular, f is not chaotic on any set. The condition b = 1 - a + a 2 defines the lower boundary of the region we are considering. When that condition holds, the 2-cycle is no longer attracting because f2([0, aD = [0, a]; in fact, f2(X) = a - x for x E [0, a] and every point in [0, a] except the one in the 2-cycle has period 4. 3. THE REGIONS FOR WHICH b < c. Before we perform detailed analyses on the regions in (a, b)-space for which b < c, which are shaded in the diagram on the left side of Figure 5, it is useful to determine some general consequences of

y

b

a

b ~~

_____

~

____

~x

c

Figure 5. The regions for which b < c and a typical graph.

1998]

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

121

this condition on b. In particular, in each of those regions there is some set upon which f acts chaotically. The presence of chaos for these regions can be deduced from more general results about maps with non-degenerate homoclinic points [5, §1.16]; the simplified proof here is tailored to the simple form of the maps being considered. The horizontal dashed line in the graph on the right hand side of Figure 5 shows a geometric meaning of b < c that plays a central role in creating chaotic behavior: the fixed point is contained in the interior of f([O, aD. The point d will be used in Proposition 3 and Section 4. Proposition 1. Assume b < c. If c

E

I, then there is an n such that r(I)

=

[0, 1].

°

Proof' First we claim that there is an m ~ such that 1 E fm(I), so that [c,l] C fmc!). If 1 E I, then we are done. If a E I, then 1 E f(J) and we are done. Otherwise, I C (a, 1) and If(I)1 = (1/(1 - a» III > III because the slope of the right hand side of the graph is 1/(1 - a). Therefore, the images of I expand exponentially until, for some k, either 1 E fk(I) or a E fk(J). If a E fk(J), then 1 E fk+l(J), which completes the proof of the claim. It follows from [c, 1] E fm(I) that [0, c] cfm+l(J) and then [b, 1] C fm+Z(J). If b :s; a, then [a, 1] cfm+Z(J), so [0,1] cfm+3(I) and we are done. If b > a, then write [b,l] = [b, c] U [c, 1]. From [b, c] c [a, c], we obtain f([b, cD c [c, 1] and If([b, cDI = (1/(1 - a»I[b, c]l. Then either a E P([b, cD or IfZ([b, cDI = (1/(1 - a»ZI[b, c]l. Therefore, the images of [b, c] expand exponentially under repeated applications of fZ until they contain [a, c]. Since [c,l] c P([c, ID, we • then have [a, 1] cfP(J) for some p. Then [0, 1] CfP+l(!).

Proposition 2. If for every interval I c [0, 1], there is an n such that r(I) = [0, 1], then f is chaotic on [0,1] and there are no attracting periodic orbits. Proof' The map f is topologically transitive because every I eventually maps to all of [0, 1]. It is easy to show that periodic points are dense, without appealing to [8]: since for every I there is an n > such that r(I) = [0, 1] :::) I, the continuity of r implies that there is some x E I such that rex) = X. We can also show sensitive dependence without appealing to [3]: since for every I there is an n > such that r(I) = [0,1], for every x E I there is ayE I such that Ir(x) - r(y)1 ~ t. Finally, if there were an attracting periodic orbit, each of its points would be contained in an interval that was contracted toward the orbit points by repeated application of f, contrary to the hypothesis. •

°

°

We make use of the following proposition in Section 6 to show that in certain cases there is chaos hiding in apparently orderly dynamics. Its proof provides additional insight into the conditions defining chaos. Proposition 3. Assume b < C. Define So = {x for which there is an n

°

> such that rcx) = c}

and let S = closure of So. Then f is chaotic on S. Proof' We have f(S) c S because f(So) c So and f is continuous. We use Figure 5 to trace a "backwards orbit" in So from c to show that So, and therefore S, is infinite. Start with Co = c and construct cl , cz,... satisfying fCc k+ l) = c k by reversing the process illustrated in Figure 2, as follows. Let

122

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

[February

[0, a) satisfy f(d) = c, as shown in Figure 5, and set c I = d. We find (c, 1] such that f(c 2 ) = C I by drawing a horizontal line from (d, d) to the right until it meets the graph. Then we find c 3 E [a, c) such that f(c 3 ) = C 2 by drawing a horizontal line from (C 2 , c 2 ) to the left until it meets the· graph. Because the absolute value of the slope of the graph to the right of x = a is greater than 1, repeating this process produces an infinite sequence of points that spiral in toward (c, c) and never cycle. Next we prove topological transitivity. Suppose x E Un Sand y E V n S. Since S is the closure of So, there are Xo E Un So and Yo E V n So. We show that there is a p > such that Yo E fP(U n S). Let k > be such that fk(XO) = c, let m > be such that fm(yo) = c, and let I be such that Xo E leU. Therefore, C E fk(I) and by Proposition 1, there is an n such that fk+n(I) = [0,1]. Then there is a z E I such that fk+n(z) = Yo and f k+n+m(z) = c, so Z E S. This proves that Yo Efk+n(I n S) cfk+n(u n S), as required. Finally, we prove that periodic points are dense in S. If U contains a point of S, then U contains a point Xo E So. Again letting Xo E leU, by Proposition 1 there is an n > such that r(I) = [0, 1]. Therefore, there is an interval II c I such that r(Il) = I. Consequently, there is an XI E II such that r(x l ) = x o, so XI E So. In the same way, there is an 12 c II such that r(I2) = II and an X2 E 12 n So such that r(x 2) = XI' and so on. Let 100 be the intersection of all the I k. Then r(Ioo) c 100 because if X is in every Ik+1 then r(x) is in every I k. Since {Xk} c InS, it has an accumulation point Xoo E InS. But Xoo must also be in every Ik n S, so Xoo E 100 n S. If 100 contains more than x oo , it also contains a point in So and consequently eventually maps to all of [0, 1], which contradicts r(Ioo) c 100 I. Therefore r(xoo ) = XOO' And since Xk ~ x oo ' we have Xoo E InS . d

E

C2 E

°

°

°

°

*

•

Remark. The usual interpretation [5, p. 50] of condition (2) in the definition of chaos is that it guarantees "an element of regularity". On the other hand, Proposition 3 illuminates a different effect: without condition (2), the map f would be chaotic on So despite the fact that the orbit of every point in So ends at the fixed point. Perhaps some strengthening of condition (1) would be more intuitively reasonable than condition (2) and would achieve the same end. 4. CHAOS ON THE ENTIRE INTERVAL WITH NO ATTRACTING PERIODIC ORBITS. The next simplest regions to analyze are those defined by b < C and either b < 1 - a or b ~ 1 - a and b > a. These are shaded in the diagram on the left in Figure 6.

y

b

a

y

a

c

b ~=~==~_a

"---_ _ _ _---"_ x

"---_ _

~_---"_

x

Figure 6. Two regions for which b < c and typical graphs for each.

1998]

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

123

The condition b < 1 - a guarantees that (1 - b)/a, the slope of the left side of the graph of f, is greater than 1, as seen in the graph in the middle of Figure 6. The condition b > a implies that if x is less than a, then f(x) is greater than a, as seen in the graph on the right in Figure 6. Proposition 4 shows that if either of these conditions is met, then for every interval I, there is an n such that r(1) = [0, 1]. Proposition 2 then implies that f is chaotic on all of [0, 1] and that there are no attracting periodic orbits, as illustrated in Figure 7.

y

y

a

a

==============~-x

Figure 7. An orbit for each region in Figure 6.

In the proof of Proposition 4, we need to know that repeated applications of f expand certain intervals. The following lemma shows that if b < c, then a small interval that contains a is expanded by f2 even though the image of that interval under f is folded. Lemma. Assume b < c and let dE [0, a) be such that f(d) = c, as illustrated in Figure 5. If a E I c [d, c], then IP(I)I ~ (c/(c - d» III. Proof" Figure 5 shows that P([d, cD = [0, c], so If2(1)1 = (c/(c - d» III when 1= [d, c]. Now suppose a E I = [p, q] c [d, c]. By similar triangles, if f(p) = f(q), then once again IP(I)I = (c/(c - d» III. If f(p) =1= f(q), then I is contained inside a larger interval 1= [p', q'] for which f(p') = f(q') and either p' = p or q' = q, so that fU) = f(l). Therefore, If2(1)1 = IPU)I = (c/(c - d» III > (c/(c - d» III. •

Proposition 4. If b < c and either b < 1 - a or b I c [0, 1], there is some n such that r(1) = [0, 1].

> a, then for every interval

Proof" Let dE [0, a) be such that f(d) = c, as shown in Figure 5. By Proposition 1, if either eEl or dEI, we are done. Otherwise, either (1) I c [0, d) or (2) Ie (d, c) or (3) Ie (c, 1]. In case (2) we have IP(I)I ~ (c/(c - d» III by the preceding lemma. In case (3), we have If(1)1 = (1/(1 - a» III. Now consider case (1). If b < 1 - a then If(l)1 = «1 - b)/a) III and (1 - b)/a > 1. If b > a instead, then f(l) c [a, 1] so

iP(I)i 124

1- b

=

1

-a- I-a III

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

[February

and the factor in front of III is greater than 1 because b < C = 1/(2 - a) < 1 + a 2 • Therefore, the images of any interval that satisfies conditions (1), (2), or (3) expand exponentially until they are too large to satisfy those conditions and • therefore must contain either c or d.

a

5. CHAOS ON A SUBINTERVAL WITH NO ATTRACTING PERIODIC ORBITS. Figure 8 shows the region defined by c ~ b < 1 - a + a 2 , a typical graph, and a typical orbit. The graph shows that f(b) > a, f2([0, f(b))) c [0, f(b )], and the orbit of every non-fixed point eventually enters [0, f(b)] and remains there under mapping by f2. In this section, we prove that some power of f exhibits chaos on an interval c [0, f(b)] and has no attracting periodic orbits, as shown on the right in Figure 8.

b

Y

a

Y

a

l-a+a 2 b

'----_ _ _ _---'"_a

Figure 8. The region for which c ~ b < 1 - a

+ a 2 , a typical graph, and an orbit.

We show that P maps the interval [0, f(b)] to itself in essentially same way that a member of the family, with different values of a and b, maps [0,1] to itself. The portion of the graph of f in the rectangle 0 ~ x ~ f(b), b ~ Y ~ 1 is a right-left reflection of a miniature copy of a member of the family. The graph of f2 on [0, f(b)] looks very similar to that portion of the graph of f, except that it is upside down, with the peak pointing down at the bottom, because f has a negative slope on [b, 1]. Therefore, we can renormalize [5, p. 133] the mapping p on [0, f(b)] to a map fI on [0, 1] by linear scalings and reflections of the input and output. The graph of fI is obtained from the portion of the graph of f in the rectangle o ~ x ~ f(b), b ~ Y ~ 1 by a right-left reflection and an expansion by 1/f(b) = (1 - a)/(1 - b) in the horizontal direction and by 1/(1 - b) in the vertical direction. Let a I and b I be the parameters of fI as a member of the family we are studying. Since the slope of the right side of the graph of f is 1/(1 - a), the slope of the left side of the graph of fI is (1 - bI)/a I = 1/(1 - a)2 > 1, from which it follows that b I < 1 - a I. Therefore, the map (a, b) ~ (aI' b I) carries the region in (a, b)-space defined by c ~ b < 1 - a + a 2 to the region in (aI' bI)-space defined by 0 ~ b I < 1 - aI' as illustrated in Figure 9. In Section 4 we showed that if b I < c I = 1/(2 - a I ), which defines the darker portion of the region in the diagram on the right side of Figure 9, then the dynamics of fI are chaotic on all of [0, 1] and there are no attracting periodic orbits. It follows that the same holds true for f2 on [0, f(b)] if (a, b) is in the corresponding portion of the region in (a, b)-space, which is the darker portion of the region in the diagram on the left side of Figure 9. If b I ~ c I, then another 1998]

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

125

b

~--------------~a

Figure 9. Mapping from (a, b)-space to (aI' bl)-space.

renormalization shows that the dynamics of f4 on a still smaller interval are equivalent to those of a map f2 on [0,1] with parameters (a 2, b 2). These either satisfy b 2 < c 2 = 1/(2 - a 2 ) or the parameters can be renormalized again. We now show that every point for which c.:::; b < 1 - a + a 2 lands in the chaotic region of Section 4 after a finite number of renormalizations. We need algebraic formulas for a k+1 and b k+1 in terms of a k and b k , for which we may assume 1/(2 - a k ) = c k .:::; b k < 1 - a k . First note that a k+1

=

1 - ak --b-Uk(bk) - a k ) 1- k

1-

=

ak(l - ak) b

1-

k

> 1 - (1- a k )

=

ak ·

Then from (1 - bk+1)/ak+l = 1/(1 - ak)2 we obtain bk + 1 = 1 -

ak + 1

(1 - a k )

2

= 1-

1

(1 - ad

2

+

ak

(1 - ad(l - b k )

.

Now we show that bk+dbk < 1 - (ad(l - a 1))2 < 1, from which it follows that b 2, b 3 , ••• decrease exponentially until bn < 1/(2 - an) for some n. To do so, consider b k+1 as a function of b k : its graph for 1/(2 - a k ) .:::; b k .:::; 1 - a k is a concave upward hyperbola that passes through (1/(2 - ak)' 0) and (1 - a k , 1 - ad(l - ak)2). Therefore bk+1 bk

--.:::;

1 - ad(1- ak )2 1-a k

=

(

1-

ak )( ak ) 2 1+-----. (l-a k ) 1- ak

We obtain an easy overestimate for the right hand side of the equation as follows. From 1 - ad(l - a k )2 < 1 - a k/(l - a k ) we have bk+dbk < 1 - (ak/(l a k ))2, whose right hand side is a decreasing function of a k . Since a k +1 > a k , we see that bk+dbk < 1 - (ad(l - a 1))2 as claimed. 6. CHAOS WITH AND WITHOUT ATTRACTING PERIODIC POINTS. Figure 10 shows the final region, in which 1 - a .:::; b .:::; a. We know from Proposition 3 that there is chaos on some subset of [0, 1] whenever (a, b) is in this region. However, if (a, b) is in one of the infinitely many "petals" shaded darker in Figure 10, then the map has an attracting n-cycle amid the chaos. The length of that n-cycle is the same throughout each petal, with n = 3 in largest petal, n = 4 in the next, and so on. These petals extend down from (1, 1) to the curve defined by b = 1/(1 + a). The diagram on the left in Figure 11 shows a typical orbit being attracted to a 4-cycle. 126

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

[February

b

~------------------------~--a Figure 10. The region for which 1 - a ::;; b ::;; a and additional detail.

y

a

b

Figure 11. Three typical orbits for 1 - a ::;; b ::;; a.

If (a, b) is outside the petals, there are no attracting cycles and either 1 is chaotic on all of [0, 1] or a power of 1 is chaotic on a subinterval, as illustrated by the orbits shown in the middle and on the right side of Figure 11. We use the following basic strategy for all the parts of the region shaded in Figure 10. From b :?: 1 - a we know that the slope of the left side of the graph is no more than 1. If in fact b > 1 - a, then that slope is less than 1. In that case, if repeatedly mapping an interval results in several images on the left side of the graph for each image on the right, then the cumulative contraction that the interval experiences on the left side may more than compensate for its expansion on the right side and produce a net contraction and an attracting cycle. And whether or not the slope of the graph is strictly less than 1, if an interval contains a, then the contraction it experiences from the fold in the graph at that point may produce an attracting cycle or it may allow a renormalization as in Section 5. To investigate these issues, for given a and b, let m be the smallest integer for which Im(o) > a. Note that since 1(0) = b :::;; a, we have m :?: 2. It follows that for each point to the right of a that an orbit contains, it contains no more than m points in [0, a]. Further, we can also construct an (m + I)-cycle with m points in [0, a] as follows. First we find x E [0, a] such that r,-l(x) = a: if 1',,-1(0) = a, then x = 0 and if Im-l(o) < a, then since r,-l(b) = llIl(O) > a, the required x lies in between 0 and b. Therefore, n + 1 (x) = O. If x = 0, then we are done. If x > 0 = Im+l(x), then by decreasing x, which increases n +1 (x), we eventually

r

1998]

r

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

127

find a point with x = fm+l(x), as required. We call the (m + I)-cycle so constructed the fundamental (m + I)-cycle. To derive an inequality that determines m from a and b, note that for 1 .::; k .::; m we have 1-b (l-b)2 (l_b)k-1 1-«I-b)/a)k fk(O) = b + - - b + - - b + ... + - b= b. 1-(I-b)/a a a a

Some algebra shows that this is greater than a if and only if ((1 - b) / a)k < (1 a) /b, from which we conclude that

l_b)m-1 I-a (l-b)m (->-->-a b a

(1)

Now we can determine when there are attracting cycles such as the one illustrated on the left in Figure 11. First we show that if there is an attracting n-cycle, then the fundamental (m + I)-cycle is attracting, so that we may restrict our attention to that cycle. Let k be the number of points in the n-cycle that are also in [0, a]. If the cycle contains a, let I be an interval with a as its right endpoint and so small that no other image of I contains a. Otherwise, let I be an interval containing a point in the cycle and so small that no image of I contains a. Then

Ir(I)1

1 b)k( 1 )n-k = ( -a1_ a III

and the cycle is attracting only if the factor multiplying III is less than 1. Because the orbit contains no more than m points in [0, a] for each point it contains to the right of a, we know that k .::; men - k) so the cycle can be attracting only if l-b)m 1 ( - - --<1. a 1- a

(2)

But if this inequality holds, then the fundamental (m + I)-cycle is also attracting. We can combine inequalities (I) and (2) to conclude that for each m = 2,3, ... , there is an attracting cycle for given a and b if and only if (l-a)(l-b) (l-b)nl ---a-b---'::; - a < 1 - a.

(3)

Inequality (3) defines the petals. Finally, note that (1 - a)(1 - b) / ab < 1 - a only when b > 1/(1 + a), which therefore determines where the lower tip of each petal is. Now suppose that (a, b) lies outside the petals so that there are no attracting cycles. First consider the case in which a is in the fundamental (m + I)-cycle. We show that the images of any I expand to [0, 1] and therefore that f is chaotic on all of [0,1] by Proposition 3, as illustrated in the middle diagram in Figure 11. If a f/:. fk(I) for 0.::; k .::; m, then Ifm+l(nl ~ ((1 - b)/a)m(lj(1 - a»III > III. . Therefore, the images of I expand exponentially until a E fP(n for some p. Let J = fP+2(I). Then 0 E J and therefore a E fm-l(]) C [a, 1], from which it follows that 1 b)m-l( 1 ifm+I(J)i= ( - a I-a

128

)2 IJI>IJI

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

[February

°

and Efm+l(J). It follows that the images of J under f m+1 expand until they contain [0, b]. Since the images of [0, b] under f cover all of [0, 1], one of them must contain c, the fixed point, so we are done by Proposition 1. Next consider the case in which f m - 1 (0) < a, so that a is not in the fundamental (m + I)-cycle. Let < P < b be such that fm(p) = rn(O), so that f m- 1 ([0, p D is the base of the little triangle at the top of the graph in Figure 12. Then If m- 1 ([0,pDI = «1 - b)/a)m-lp and with f(d) = c as in Proposition 4, we have

°

Irn+ ([0,p]) 1·= 1

c (l-b)m-l c - d -ap

= (1 -

a

b

(l-b)m

+ ab)(1 - a) - a -

p.

y a

b

~--

____

~

______________

~L--X

P

Figure 12. The point p.

If «1 - b)/a)m :=:; (1 - b + ab)(1 - a)/a, which holds in a thin sliver below each petal, then fm + 1 ([0, p D c [0, p] and we can generalize the renormalization of f2 that was done in Section 5, in which m was equal to 1, as follows. Let 1= fm-l(fm+l([O, p])). Then [fm-l(o), a] c I cf m- 1 ([0, pD, from which it follows that fm+l(I) = I. The portion of the graph of f that lies above I is the right-left reflection of a miniature copy of a member of the family, so we can renormalize f m+1 on I to a map fl on [0, 1]. Since the absolute value of the slope of the right side of the graph of f is greater than the slope on the left side, the opposite is true for fl and its parameters therefore satisfy (1 - b 1 )/a 1 > 1. Then by the same reasoning as in Section 5, f m + 1 is chaotic on a subinterval of [0,1], as illustrated on the right in Figure 11. On the other hand, if «1 - b)/a)m > (1 - b + ab)(1 - a)/a, then once again the images of every interval expand to all of [0, 1] and f is chaotic on all of [0, 1].

7. CONCLUSION. Much of the interest in dynamical systems derives from examples of simple systems with complicated behavior. By exhibiting elementary examples of attracting periodic orbits, chaos, non-degenerate homo clinic points, renormalization, and an intricate pattern of dynamics, this paper adds to the body of literature demonstrating that the study of dynamical systems provides a fertile ground for exploration, both at the educational and research levels. 1998]

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

129

We were able to keep our classification of the dynamics of the family of maps at an elementary level because the graphs of the maps consist of two straight lines. It would be interesting to discover how much of the pattern of dynamics we saw would be preserved in passing to a less restrictive family of maps. In particular, the graphs of the maps that inspired this study, the models of the electronic circuits in [1] and [2], can be obtained from the graph in Figure 1 by replacing the left line segment by a concave down curve and the right line segment by a concave up curve. REFERENCES 1. 2. 3.

4. 5. 6. 7. 8.

S. Bassein, Order and chaos on your desk, Amer. Math. MOII/hly 102 (1995) 409-416. S. Bassein, Mathematics Electrified!, Grant Puhlishing, Berkeley, 1996. J. Banks, J. Brooks, G. Cairns, G. Davis, and P. Stacey, On Devaney's Definition of Chaos, Amer. Math. Monthly 99 (1992) 332-334. P. Collet and J.-P. Eckmann, Iterated maps of the ill/erval as {~Yllamical ~ystems, Birkhiiuser, Boston, 1980. R. L. Devaney, All Introduction to Chaotic DYllamical Systems, Benjamin/Cummings, Reading, 1986. S. N. MacEachern and L. M. Berliner, Aperiodic Chaotic Orhits, Amer. Math. MOllthly 100 (1993) 237-241. M. T. Weiss, An Early Introduction to Dynamics, Amer. Math. Monthly 98 (199]) 635-641. M. Vellekoop and R. Berglund, On lntclvals, Transitivity = Chaos, Amer. Math. MOllthly 101 (]994) 353-355.

SUSAN BASSEIN has spent more than a decade wandering through the fields of optimal control theory, astronomy, music, electronics, dynamical systems, and randomness looking for ways to use mathematics to make sense of the world, hoth for herself and for her students. She is now performing statistical analyses for a project to reduce the use of fungicides on wine grapes in California. Departmell/ of Mathematics alld Computer Sciellce, Mills College, Oaklaml, CA 94613 [email protected]

J must study politics and war that my sons may have liberty to study mathematics and philosophy. My sons ought to study mathematics and philosophy, geography, natural history, naval architecture, navigation, commerce, and agriculture in order to give their children a right to study painting, poetry, music, architecture, statuary, tapestry, and porcelain. John Adams (1735-1826), in a letter to Abigail Adams, May 12, 1780

l__ ._._._____.____.________ . .__.____________.__._____. _._. ___. ._. _._._. _____.

130

DYNAMICS OF A FAMILY OF ONE-DIMENSIONAL MAPS

[February

The Bricklayer Problem and the Strong Cycle Lemma Hunter S. Snevily and Douglas B. West

1. THE PROBLEM. One of the most familiar brand names in the world of toys is Lego™; the name immediately brings interlocking building blocks to mind. Interlocking blocks fit together in restricted ways. Typically, a block of order q (length q + 1) has q + 1 protrusions on its top and q + 1 indentations on its bottom, so that the indentations on the bottom of one block can lock on to the protrusions on the top of another. Here q is a positive integer, and the width and height of a block are unimportant. For q = 1 and q = 2, Figure 1 shows the q ways in which one block can sit on top of two others.

Figure 1. Bricks of order q, for q

=

1 and q

=

2.

In this paper, we solve a counting problem about building stacks of such blocks, which we call bricks. We have a linear base of length m on which we can place bricks. The bricks sitting directly on the base can start at any integer position, as long as they fit on the base and don't overlap. When two bricks are contiguous, sharing a common end, we can place another brick on top of them. Since we want the blocks to interlock, it must cover part of each brick below it. The protrusions and indentations then restrict it to q possible positions, covering a positive integer amount of each brick it rests on. Again bricks cannot overlap. We call a configuration built by these rules a q-stack. The bricklayer problem. How many different q-stacks can be built on a base of length m? For example, when m = 4 and q = 1, there are five q-stacks, including three with one brick, one with two bricks, and one with three bricks that appears in Figure 1. When m = 5 and q = 1, there are nine q-stacks. When m = 6 and q = 2, there are seven q-stacks, two of which appear in Figure 1. 1998]

ruE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

131

The bricklayer problem is related to a host of other problems in combinatorial enumeration. We solve it by establishing a bijection from the set of q-stacks on a base of length m to a special set of sequences of O's and l's. This leads us to related counting problems because these special sequences generalize the solutions to the famous Ballot Problem. Consider an election that ends in a tie, with k votes for each of two candidates. If the votes are counted in a random order, with all sequences equally likely, we may wonder what the probability is that the first candidate never trails. Using O's to designate votes for the first candidate and l's to designate votes for the second, we are asking for the fraction of sequences with k l's and k O's such that every prefix (initial segment) has at least as many O's as l's. These sequences are the ballot sequences of length 2k. To compute the desired probability, we count the ballot sequences and divide bye:). We will see shortly that the number of ballot sequences of length 2k is the kth Catalan number Ck , defined by Ck = k

+1 1 (2k) k .

.More generally, a sequence is q-satisfying if in each prefix the number of O's is at least q times the number of l's. We will establish a bijection between the q-stacks on a base of length m and the q-satisfying sequences of length m. Thus we reduce the bricklayer problem to the counting of q-satisfying sequences. The Cycle Lemma of Dvoretzky and Motzkin [5] provides one of the many proofs that the Catalan numbers count the ballot sequences. With equal ease it enables us to count the q-satisfying sequences of length m. After doing so, we develop the bijection to solve the Bricklayer Problem. Subsequently, we explore generalizations of the Cycle Lemma and applications of these generalizations. 2. THE CYCLE LEMMA AND GENERALIZED CATALAN NUMBERS. To facilitate our discussion, we introduce terminology to describe various arrangements of O's and l's. A q-dominating sequence (as defined in [3]) is a sequence of l's and O's such that in each prefix the number of O's is more than q times the number of l's. A (k, I)-sequence is a sequence of k l's and I O's. A (k, I)-arrangement is a cyclic arrangement of k l's and I O's. By this we mean that rotating the arrangement does not change it, but we maintain a fixed direction; a flip or reversal produces a different arrangement. . A special case of the Cycle Lemma states that every (k, k + I)-arrangement can be cut in exactly one position to obtain a I-dominating (k, k + I)-sequence. The first element of this sequence (the element after the cut) must be a O. Deleting this o yields a ballot sequence, and the process is reversible. Thus the ballot sequences and the (k, k + I)-arrangements are equinumerous. Since k and k + 1 are relatively prime, the number of (k, k + I)-arrangements (and ballot sequences of length 2k) is exactly the Catalan number (2k + 1) 1 ( 2k) + 1 k + 1 = k + 1 k = Ck • The Cycle Lemma thus "explains" one 0 in a (k, k + I)-arrangement. Kierstead 2k

1

and Trotter [9] generalized this to give combinatorial meaning to each o. We present their result in Section 4 and extend it slightly. Our task at present is to prove the Cycle Lemma and use it to count the q-satisfying sequences of length m. Figure 2 illustrates the Cycle Lemma (and its proof) when (k, q, p) = (2,2,3); the 132

THE BRICKlAYER PROBLEM AND THE STRONG CYCLE LEMMA

[February

o o Q

1

Q

Q

Figure 2. 2-dominating sequences from a (2, 7)-arrangement.

underscored O's are those that begin 2-dominating sequences when the arrangement is read clockwise. Theorem 1. (The Cycle Lemma-Dvoretzky and Motzkin [5]) For k, q, p ~ 0, every (k, qk + P )-arrangement breaks to form a q-dominating sequence in exactly p places. Proof' The statement is trivial for k = 0; we proceed by induction. For k > 0, let a be a (k, qk + p)-arrangement. By the pigeonhole principle, between some pair of the I's in a there are more than q O's. Let S be a set of q + 1 consecutive positions consisting of q O's followed immediately by a 1 (illustrated by the outside arc in Figure 2). None of the q + 1 positions of S can start a q-dominating sequence. A position outside S starts a q-dominating sequence if and only if it starts a q-dominating sequence in the (k - 1, q(k - I) + P )-arrangement a' obtained from a by deleting S. The number of q-dominating starting places in a thus equals the number of • q-dominating starting places in a', which by the induction hypothesis is p.

Corollary 2. The number of q-satisfying (k, qk + p - I)-sequences and the number of q-satisfying sequences of length m, respectively, are p (q+I)k+P-I) qk +p k

and

lm/r:+l)J k=O

m- (q + I)k + 1 (m). m - k

+1

k

Proof' A sequence is q-satiSfying if and only if the sequence obtained by adding a o at the front is q-dominating. Thus the q-satisfying (k, qk + p - I)-sequences and the q-dominating (k, qk + P )-sequences are equinumerous. By the Cycle Lemma, each (k, qk + P )-arrangement has p positions that yield q-dominating sequences. Thus in each class of (k, qk + p)-sequences equivalent under cyclic rotation, the fraction that are q-dominating is p /(k + qk + p). Since the fraction is the same over all classes, we need not worry about periodicity. We conclude that the number

of q-dominating (k, qk + P )-sequences is (( q+ l)k + p) k P , which equals the . k +qk+p formula claimed. Each q-satisfying sequence of length m has k I's and m - k O's, for some k. By setting m - k = qk + p - 1, we obtain p = m - (q + I)k + 1 and can use the preceding formula to count these sequences. Thus the term for k in the summation is precisely the number of q-satisfying sequences of length m that have k I's .

•

1998]

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

133

/I\l\ A

abc ((abc)de)

--+

d

e

abc

(a(bcd)e)

abcldel

--+

d

e

abcdlel

U

abc (ab( cde))

--+

d

e

abcdell

Figure 3. The rooted plane ternary trees with five leaves.

Dershowitz and Zaks [3] gave two applications of the Cycle Lemma and provided references to several proofs of it. Many applications (and many proofs) have been given for the special case p = 1. These lead to the generalized Catalan numbers, defined by

cq = 11

1 qn

+1

( (q

+ 1) n ) . n

By Corollary 2, C% is the number of q-satisfying (n, qn)-sequences. There are other ways to generalize the Catalan numbers by introducing additional parameters, but this is the generalization appropriate for our discussion. For example, the generalized Catalan numbers arise in counting the rooted plane trees with qn + 1 leaves in which every non-leaf vertex has exactly q + 1 children. By "plane tree", we mean that the left-to-right order of children matters. Figure 3 shows the three such trees when q = 2 and n = 2. By working up from the leaves, combining q + 1 subtrees at each non-leaf vertex, we see that each tree corresponds to a product of qn + 1 elements in order using a non-associative q + 1-ary operator. Conversely, from such a product we obtain the corresponding tree. Sands [14] was interested in counting the ways to form such a product. In order to count the products, we convert the tree to a sequence of objects and markers. We do this by traversing the tree; beginning at the root, walk around the tree, keeping our left hand on it, until we have traversed every edge twice. We record an object for each leaf when it is visited and a marker for each non-leaf vertex when the subtree rooted at that node is completed. Figure 3 shows the resulting sequences when q = n = 2. The sequence corresponding to each tree (that is, each bracketing) is "post-fix" notation for the formation of the product; the marker specifies application of the operation to the q most recent objects on the stack, replacing them by a single object. By converting markers to 1's and objects to O's, we obtain an (n, qn + 1)sequence. For each such sequence produced in this way, the number of objects that precede the ith marker must exceed qi, since applying a q + 1-ary operator i times converts qi + 1 objects into one object. Sands observed by an easy induction on n that the q-dominating condition is also sufficient. Thus these bracketings (or these trees) are equinumerous with the q-satisfying (n, qn)-sequences, and there are C% of them. When q = 1, we obtain the ballot sequences and the ordinary Catalan numbers. Other counting problems solved by the Catalan numbers generalize in analogous ways. Hilton and Pedersen [8] observed that C% counts the subdivisions of a convex polygon into n disjoint (q + 1)-gons by noncrossing diagonals. This generalizes a bijection between binary trees with n + 1 leaves and dissections of an n + 2-gon 134

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

[February

into triangles, where the root becomes one edge of the polygon and the leaves become the other edges. In light of these generalizations, we use the name q-ballot sequences for the q-satisfying sequences with exactly n l's and qn a's. 3. q-SATISFYING SEQUENCES AND THE BRICKLAYER PROBLEM. Before attacking the full generality of the bricklayer problem, we consider how the bijection works when q = 1. Propp (see [12]) observed that the ordinary Catalan numbers solve a simple coin-stacking problem. We begin with a base row of n coins. Each coin not in the base row rests on two coins in the row immediately below it. Figure 4 illustrates such a stack with a base row of 6 coins.

Figure 4. A stack of coins and its conversion.

Let an be the number of distinct stacks that can be built on a base of length n, with a o = 1. If the number of contiguous coins at the beginning of the first row above the base is k - 1, then the stack is completed by building one stack based on these k - 1 coins and another based on the last n - k coins of the original base. Summing over the possible values of k yields an = Lk=l a k - 1 a n- k for n ;;::: 1. This is the well-known recurrence satisfied by the Catalan numbers. It arises for the ballot sequence model by letting 2k be the minimum length of a nonempty prefix with the same number of a's and l's. The recurrence suggests a natural bijection. Replace each coin by a wedge, as shown on the right in Figure 4. View each wedge as having width 2. The wedge for a coin above the base rests on the apexes of the wedges for its supporting coins. Now follow the ouoJine of the mound of wedges. Each step up is a 0, each step down is a 1. Each step moves one unit right, so there are 2n steps. We end !'it the base, so there are n steps of each type. Since the mound never dips below the base, the result is a ballot sequence. The statement that this is a bijection is a special case of our main theorem. We generalize to the bricklayer problem by viewing the coins as bricks of length 2 = q + 1. We drop the requirement that the base be full to allow bases of all lengths rather than merely multiples of q + 1. For this more general problem, the proof is simpler. In the special case where m = (q + l)n and the base is filled by n bricks, there will be C% stacks, corresponding to the q-ballot sequences. Recall our conditions for q-stacks in the bricklayer problem: 1) The base has length m. 2) The bricks have length q + 1. 3) Each brick not directly resting on the base rests on two contiguous bricks

immediately below it and covers a positive integer amount of the tops of each. Thus a brick has q possible positions in relation to the two bricks below it. Theorem 3. In the bricklayer problem with a base of length m, the number of q-stacks with n bricks resting directly on the base, and the total number of q-stacks, respectively, 1998]

ruE BRICKLAYER PROBLEM AND ruE STRONG CYCLE LEMMA

135

are

m- (q + l)n + 1 (m) m-n+l

n

and

lm/~+l)J 11=0

m- (q + l)n + 1 (m). m - n

+1

n

Proof Fix q. Let the length of a q-stack be the length of the base. Let Sm be the

set of q-stacks of length m. Let Qm be the set of q-satisfying sequences of length m. We establish a bijection f: Sm ~ Qm. Furthermore, f restricts to a bijection from S~I to Q;:', where S;:' is the subset of Sm consisting of stacks having n bricks resting on the base and Q:~ is the subset of Qm consisting of the sequences with n l's. By Corollary 2, establishing this bijection completes the proof. To define f on a stack A E Sm' we begin by shaving the top corners of each brick along a line from the bottom corner to a point at distance one from the top corner along the top edge. Each brick becomes a symmetric trapezoid with upper edge of length q - 1 and lower edge of length q + 1 (a wedge when q = 1). Shaving the bricks is an invertible process (mathematically, not physically), so we henceforth treat Sm in this form. For A E Sm (shaved), we define f(A) by reading the top outline of the stack, recording a 0 for each up-slant or horizontal step, and recording a 1 for each down-slant. Since we record one bit for each increase in the horizontal coordinate, the length of f(A) is m. Figure 5 illustrates the correspondence for one stack with (q, m, n) = (2,12,3) and for all stacks with (q, m, n) = (2,9,3). Among the q-satisfying sequences, the q-dominating sequences are those that have no q-ballot prefix. We prove the further property that, within each pair

~

000101000100

001001001

~

000100011

~

000101001

~

001001001

~

000011001

~

001000101

~

001000011

~

000100101

~

~ ~ ~ ~

000010011

000010101

000001011

000000111

Figure 5. Shaved q-stacks and the corresponding q-satisfying sequences.

136

TIlE BRICKLAYER PROBLEM AND TIlE STRONG CYCLE LEMMA

[February

(s::" Q::,), f matches the q-dominating sequences with the stacks not covering the first space on the base. We use induction on m. When m = 1, there are no bricks, and the empty stack in sf maps to the sequence 0 in Qp. For m > 1, we consider three types of stacks and the corresponding sequences, showing first that f restricts as desired. If A E S::, does not cover the first space of the base, then f(A) consists of 0 followed by f(A ' ), where A' is obtained from A by deleting the first space of the base. By the induction hypothesis, f(A' ) E Q::'-l' so f(A) E Q::, and f(A) is q-dominating. If A E S::, covers the first space, let m' = k(q + 1) be the step on which the outline of A first returns to the base (in the top example of Figure 5, k = 2 and m ' = 6). If m ' < m, then A is the concatenation of a stack A' E S!, and a stack A" E S::'-=-~" and f(A) is the concatenation of f(A ' ) and f(A"). By the induction hypothesis, f(A ' ) is a q-ballot sequence and f(A") is q-satisfying, so f(A) E Q~, and f(A) is not q-dominating. If m ' = m, then m = (q + 1)n and every notch in the lowest row of bricks is covered by a higher brick. Let A' be the stack obtained from A by deleting the bottom row of bricks and the first and last space of the base. Since every brick above the first row covers one notch, A' E S::,-=-~. Also, f(A) is obtained from f(A ' ) by adding 0 at the beginning and 1 at the end. By the induction hypothesis, f(A ' ) E Q::'-=-~. Adding 0 at the beginning and 1 at the end of a q-satisfying sequence with these parameters yields a q-satisfying sequence, so f(A) E Q(q+l)n" The sequence without the final 1 is q-dominating and has no q-ballot prefix, but the full f(A) is a q-ballot sequence and is not q-dominating. To show that f is invertible, consider a E Q::'. If a is q-dominating, then no stack covering the first space has image a. Let a' be the q-satisfying sequence obtained by deleting the initial 0 of a. By the induction hypothesis, there exists one stack A' E S::'-l such that f(A' ) = a' . Among the stacks in S::, not covering the first space, there is thus one stack A such that f(A) = a. If a is not q-dominating, then a has a q-ballot prefix. Let m' be the length of the shortest q-ballot prefix a' of a, having k 1's. Since a' has qk O's, the remainder a" of a is in Q::'-=-~,. We have observed that a proper q-ballot prefix of length m ' < m arises in f(A) if and only the outline of A first returns to the base after m ' steps. By the induction hypothesis, there is one A E S!, such that f(A) = ai, and there is one A" E A;:,-=-km , such that f(A") = a", and the concatenation yields the unique A such that f(A) = a. If a is not q-dominating and m ' = m, then m = (q + 1)n and a is a q-ballot sequence with no proper q-ballot prefix. Before the final 1, a is q-dominating, and deleting the initial 0 and final 1 yields a q-satisfying sequence a' of length m - 2. We have observed that if f(A) is a q-ballot sequence with no proper q-ballot prefix, then A has n - 1 bricks in the second row, and f(A) is obtained by adding o at the beginning and 1 at the end of f(A' ) for the stack A' E S::,-=-~ obtained by deleting the bottom row of A and shortening the base at both ends. By the induction hypothesis, there is one A' E S::,-=-~ such that f(A ' ) = ai, and thus there • is one A such that f(A) = a. The proof yields a recurrence for the number c m n of q-satisfying sequences of length m with n 1's. We have c l , 0 = 1, and c l , n = 0 for n =1= 1. For m > 1, Cm,n = cm-l,n

+

Em ,n c m-2,n-l

+

E

c(q+l)k,kcm-(q+l)k,n-k'

(*)

O::;;,k<m/ (q+l)

1998]

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

137

where Em n is 1 if m = (q + 1)n and is 0 otherwise. Bailey [1] obtained another recurrenc~ for the case q = 1 and used it to obtain the first statement of Corollary 2 in that case. The Catalan recurrence an = Lk=l a k - 1 a ll - k is simpler than (*) because removing the initial 0 and trailing 1 from a ballot sequence that has no balanced prefix yields a shorter ballot sequence. This statement does not generalize; when a q-ballot sequence of length (q + 1)n has no proper q-ballot prefix (such as 000100011 for q = 2 and n = 3), removing the bits after the penultimate 1 and removing enough leading O's to reduce to length (q + 1)(n - 1) need not produce a q-ballot sequence. We can obtain a natural recurrence for generalized Catalan numbers by modeling the formation of bracketings. We know that C~ counts both the q-ballot sequences with n l's and the bracketings of a product involving n applications of a q + 1-ary operator. Hilton and Pedersen [8] observed that the last application of the operator combines q + 1 segments, each of which is a shorter q-dominating (n i , qni + 1)-sequence. Thus q+l

q

=

L

nC~, i=l

'

where the summation runs over all choices of q + 1 positive integers n l ,· •• , n q + 1 that sum to n - 1. The initial condition is C8 = 1.

4. (k, qk + 1)-ARRANGEMENTS. Kierstead and Trotter [9] strengthened the Cycle Lemma on (k, k + 1)-arrangements, showing that each 0 plays a special role. For 1 ~ i ~ k + 1, they proved that every (k, k + 1)-arrangement has a unique linearization ending in a 0 such that exactly i of the prefixes ending at O's have more O's than l's. They noted that this result is implicit in the work of Feller [6] and Narayana [11], and they used it to construct new explicit perfect matchings in the bipartite graph of the inclusion relation on the k-sets and k + I-sets of a 2k + I-element set. Their elegant proof of a technically stronger statement extends directly to (k, qk + 1)-arrangements. Figure 6 shows a (clockwise) (3,7)arrangement and its O-linearizations, indicating the number of 2-good O-intervals in each and underscoring the positions that end 2-good O-intervals. Within a cyclic arrangement a = ao, ... ,a n- 1 of O's and l's, we denote the list ai+l"'" a j (indices modulo n) by G, The linearization of a ending at position i is G, i]. For a fixed linearization, we use O-interval to mean a prefix ending at a O. If a i = 0, then G, i] is a O-linearization, and the full list G, i] is the trivial O-interval.

n.

0

1

0

0

1

0

0 0

1

0

Q

1

1 0 1 001 0 0 0

3

lOOlOOQQIQ

6 4

QIOQQQIQIQ lOOQQIQIOQ

7 5 2

QQQIQIQQIQ QQIQIOQIOQ QIOIOOIOOQ

Figure 6. 2-good O-intervals in O-linearizations of a (3, 7)-arrangement.

138

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

[February

We use wo(I) and w 1(I) to denote the number of O's and l's in I, respectively. A O-interval I is q-good if wo(I) > qw 1(I). In every O-linearization of a (k, qk + p)arrangement with p > 0, the trivial O-interval is q-good.

+ I)-arrangement and 1 :;;; i :;;; qk + 1, then there is a unique O-linearization (ji' jJ of a in which exactly i O-intervals are q-good. Furthermore, for i :;;; qk, the O's that end q-good O-intervals in (ji' jJ also end q-good O-intervals in (ji + l' ji+ 1] (we call this the nesting property). Lemma 4. (Strong Cycle Lemma) If a is a (k, qk

Prool Given a (k, qk + I)-arrangement a, let the deficiency of an interval I = (r, s] be 8(r, s] = qw 1(I) - wo(I). Given a O-linearization (r, r], let D(r) = j: {8(r,j] < 0 and aj = OJ; this is the set of indices ending q-good O-intervals for (r, r]. Note that r E D(r). Since 1 :;;; ID(j)1 :;;; qk + 1 for all j, it suffices to prove that the sets of the form D(j) are distinct and are linearly ordered by inclusion. Let r, s be the positions of two O's. Since 8(r, s] + 8(s, r] = -1, exactly one of (r, s] and (s, r] has negative deficiency and is q-good. When (r, s] is q-good, we claim that D(s) c D(r). Note that s E D(r), but r Ii/:. D(s). Now consider j E D(s); we have two cases. If j E (r, s], then 8(r, j] = 8(s, j] - 8(s, r] < O. If j E (s, r], then 8(r,j] = 8(s,j] + 8(r,s] < O. In each case, we obtain j ED(r). •

The Strong Cycle Lemma can also be proved by constructing ji+l explicitly from ji' but that takes longer. As an application, we obtain a result of Chung and Feller

that generalizes the Ballot Problem discussed earlier. We obtain the simple Ballot Problem by setting I = 0 and interchanging A and B. The Chung-Feller proof used analytic methods. Corollary 5. (Chung-Feller [2]) Let I be an integer in {O, ... , n}. In a random sequence of n A's and n B's, the probability is 1/(n + I) that there are exactly I choices of i such that the ith A precedes the ith B.

Prool Given a sequence b of n A's and n B's, convert A's to O's, B's to l's, and append a 0 at the end; call this sequence b'. The sequence b' is a O-linearization of an (n, n + I)-arrangement a. Because n + 1 and 2n + 1 are relatively prime, exactly n + 1 sequences of n A's and n B's yield the same (n, n + I)-arrangement. By the Strong Cycle Lemma, the n + 1 O-linearizations of a have different numbers of I-good O-intervals. The ith B in b precedes the ith A in b if and only if the ith 0 in b' is a I-good O-interval. By grouping the sequences into sets of size n + 1 yielding the same cyclic arrangement, we see that the number of sequences with exactly I values where the ith A precedes the ith B is independent of I. •

We next extend the Strong Cycle Lemma by specifying an arbitrary set of O's in a (k, qk + I)-arrangement. Lemma 6. (Stronger Cycle Lemma) If a is a (k, qk + I)-arrangement, S is a set of t positions containing O's, and 1 :;;; i :;;; t, then there is a unique O-linearization
Prool Define deficiency as in Lemma 4, but let D(r) = {j: 8(r,j] < 0 and j E S}. Since 1 :;;; D(r) :;;; t, it suffices to show that the sets D(r) for rES are distinct and ordered by inclusion. Given r, s E S, the proof of this is as in Lemma 4. • 1998]

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

139

Viewing the elements of a (k, k + I)-arrangement as exponents on - 1 yields a cyclic arrangement of k + 1 positive l's and k negative l's. The ordinary Cycle Lemma provides a unique starting position such that all the partial sums are positive. Raney [13] proved more generally that every cyclic arrangement of integers summing to + 1 has a unique starting position such that all partial sums are positive. The Stronger Cycle Lemma for q = 1 provides a short proof of a further generalization. In Figure 7, we indicate the number of positive partial sums in each successive linearization of a clockwise arrangement- and underscore the positions that end positive partial sums.

2

3

-1

-2

2

1

-5

-2

3

5 2

-1

~

-5

-1 .

~

~

-5

3

3

~

-5

3

1

-5

3

-2

8 4 7 6 9

3

-2 1 -2

1

-2 1 -2

-2 1 -2

-2 3

3 ~

~

-2 1 -2 ~

-2 1 -2

1 -2

-2 3

~

3

-1

3

2 -1 2 -5

3

~ ~

-1

~

-1

~

2 -1 2 -5

~

-1

~

-5

~

-1

~

-5

~

-2

~

Figure 7. Positive partial sums in an arrangement summing to

~

~

-5 ~

~

-2

-2 1

-2

1

+ 1.

Corollary 7. (Montagh [10]) Given a cyclic a"angement of n integers summing to + 1 and an integer I E {l, ... , n}, there is a unique linearization of the a"angement such that exactly I of the partial sums are positive. Proof' Let b denote the arrangement of integers. Form a cyclic arrangement a of l's and O's by replacing each nonnegative integer bi by a single 1 followed by 1 + b i consecutive O's, and replacing each negative b i by 1 - bi consecutive l's followed by one O. The resulting a is a (k, k + I)-arrangement, where k = n + lL:lb;l!2J. Let S be the n-set of O's that end maximal consecutive segments of O's. The O-linearizations ending in S correspond naturally to linearizations of b; the number of positive partial sums in a linearization of b equals the number of I-good O-intervals ending in S in the corresponding O-linearization of a. By Lemma 6, these numbers are distinct for the n linearizations ending in S. •

In this application, the "nesting property" says that the numbers ending positive partial sums in the I - lth arrangement also end positive partial sums in the Ith arrangement. Graham, Knuth, and Patashnik [7, p. 346] presented a geometric proof of Raney's original result, which upon closer examination also yields MonHigh's generalization. (Dershowitz and Zaks [3] observed that the geometric approach can also be used to prove the Cycle Lemma itself.) Encode the integer arrangement ai' ... ,an as a walk in the plane, starting from the origin and moving (+ 1, +a) from the current position when the ith number is encountered. The ending position is (n,1). Figure 8 shows two periods of the walk for the sequence 2, -1,2, -5,3, -2,1, -2,3. 140

THE BRICKlAYER PROBLEM AND THE STRONG CYCLE LEMMA

[February

Figure 8. A geometric argument.

The unique starting position from which all the partial sums are positive follows the last occurrence of the minimum in the first period. All other positions have a non-positive partial sum ending at that position, but partial sums starting after it are positive. All but one partial sum is positive when we start after the previous occurrence of the minimum or, when the minimum is unique, after the last occurrence of the next smallest value. For each I < n, let bl be the position in the first period from which I + 1 partial sums are positive. Then bl - 1 is obtained from. bl by moving to the previous occurrence of the same height as b l or, if bl is the first occurrence of that height, the last occurrence of the next larger height. When n = (q + 1)k + 1 and the sequence consists only of l's and -q's, summing to + 1 requires that exactly k terms equal -q. Following Graham, Knuth, and Patashnik (with a shift of index), we call such a sequence a q-Raney sequence if all the partial sums are positive (this requires the first term to be a 1). They prove that there are Cl such sequences. This follows immediately from Corollary 7 when 1= n, since Cl equals the number of (k, qk + 1)-arrangements. The Strong Cycle Lemma also yields a short direct proof that the number of q-ballot sequences with k ones is Cff. As before, prepending a 0 shows that these . are equinumerous with the q-dominating (k, qk + 1)-sequences. By the Strong Cycle Lemma, the reverse a' of such a sequence a has a unique O-linearization such that no O-interval is q-good. The reverse of this O-linearization is the unique cyclic permutation of a such that wo(I) > qw1(I) for every prefix I (whether ending at a 0 or a 1). Hence we conclude again that the q-ballot sequences of length (q + 1)k are equinumerous with the (k, qk + 1)-arrangements. The result of Kierstead and Trotter, extended to the Strong Cycle Lemma, distinguishes the O's of a (k, qk + 1)-arrangement in a combinatorial fashion. We close this section by presenting another combinatorial distinguishing of these O's that extends to (k, i)-arrangements whenever k and I are relatively prime. In the case I = k + 1, it yields matchings different from the matchings of Kierstead and Trotter [9] between the middle levels of the lattice of subsets of a 2k + I-element set; further diSCUSSIon appears in [4]. Theorem 8. (Snevily [15]) If k and I are relatively prime, then the position-sums of the O-linearizations of a (k, i)-a"angement a belong to distinct congruence classes modulo I, where the position-sum of a O,l-vector is the sum of the indices of its l's. Proof" We cycle through the O-linearizations, decreasing the position-sum by k mod I for each successive O-linearization. From one linearization of a, we move to the next by moving the bit in position 1 to position n = k + I and shifting each other bit down by one. If we have a O-linearization with a 0 in position 1, then a single shift takes us to the next O-linearization and decreases the position-sum by k. If the bit in position 1 is a 1, then we make additional shifts before moving the first 0 to the back. For each shift in which a 1 moves from the front to the back, we 1998]

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

141

decrease the position by one for k - 1 1's and increase it by k + I - 1 for one 1. The net change in the position-sum is (k + I - 1) - (k - 1) = I. Thus this operation does not change the congruence class of the position sum. Only the last shift to reach the next O-linearization changes the congruence class, again reducing it by k modulo I. • 5. (k, qk + P )-ARRANGEMENTS WITH P > 1. In light of our results about q-satisfying sequences of arbitrary lengths, it is natural to seek comparable extensions of the Strong Cycle Lemma to (k, qk + p)-arrangements. Unfortunately, when p > 1 it is possible for complementary intervals to be q-good. The simple proof of the Strong Cycle Lemma used when p = 1 thus fails in the general case, and generalizations for p > 1 make weaker statements about q-good intervals. We mention two special cases of our final theorem: every O-linearization of a (k, qk + p )-arrangement has at least pO-intervals that are q-good, and there are at least p O-linearizations in which every O-interval is q-good.

Theorem 9. (Extended Strong Cycle Lemma) If a is a (k, qk + P )-a"angement and p ~ i ~ qk + p, then a has at least qk + 2p - i O-linearizations that have at least i q-good O-intervals. Proof" The crux of the proof is the augmentation property: If b is a O-linearization of a (k, I)-arrangement with I > qk, and b' is obtained from b by inserting a 0, then b' has more q-good O-intervals than b. To prove this, we partition b as I 10IzO ... ItO, where the intervals Ij contain no ends of q-good O-intervals, and the t elements indicated by O's are the ends of the q-good O-intervals (some of the I/s may be empty). The location of the first q-good O-interval implies that WO( 1 ) = qW 1( 1 ). The location of each successive q-good O-interval implies that woUj ) = qw 1Uj ) - 1 for each j > 1. To form b' , we insert a 0 in some II" obtaining I;. Each o ending a q-good O-interval in b does so also in b'. In addition, the last 0 in I; (which mayor may not be the added 0) also ends a q-good O-interval in b'. We now prove the theorem by induction on p. When p = 1, the desired statement is a weakening of the Strong Cycle Lemma. For p > 1, we begin by finding a O-linearization in which every O-interval is q-good. To do this, delete p - 1 O's arbitrarily to obtain a (k, qk + 1)-arrangement ii. By the Strong Cycle Lemma, ii has a unique O-linearization in which every O-interval is q-good. Each time we replace one of the deleted O's, the augmentation property implies that again every O-interval is q-good. After replacing all the deleted O's, we have a O-linearization b of a in which every O-interval is q-qood. Let a' be the (k, qk + p - 1)-arrangement obtained by deleting the last element of b from a. Consider i such that p ~ i ~ qk + p; we have p - 1 ~ i - 1 ~ qk + p - 1 and qk + 2(p - 1) - (i - 1) = qk + 2p - i - 1. By the induction hypothesis, a' has at least qk + 2p - i - 1 O-linearizations in which at least i - 1 O-intervals are q-good. By' the augmentation property, the replacement of the missing 0 converts these to O-linearizations of a in which at least i O-intervals are q-good. Since every O-interval in b is q-good, b provides the additional needed O-linearization. •

The extended Strong Cycle Lemma is best possible in the sense that all its lower bounds may hold with equality simultaneously. This is achieved by the (k, qk + p)arrangement in which all the 1's appear together and all the O's appear together, which has exactly pO-linearizations in which all O-intervals are q-good and one O-linearization in which exactly i O-intervals are q-good for each p ~ i < qk + p. 142

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

[February

On the other hand, there may be more O-linearizations with at least i O-intervals that are q-good than guaranteed by the extended Strong Cycle Lemma, so its inequalities cannot be replaced by equalities. When p = tk, consider the periodic (k, qk + P )-arrangement a in which each 1 is followed by a string of exactly q + t O's before the next 1. This arrangement has exactly q + t "types" of O-linearizations. When the first 1 in a O-linearization of a appears after position q, every one of the (q + Ok O-intervals is q-good; there are (t + 1)k such O-linearizations. This already is k more than guaranteed by the Lemma, so the guarantee is exceeded when the desired number of q-good O-intervals is i > (q - 1)k + p. When the first 1 appears in position j + 1 for some 0 ~ j ~ q, the number of O-intervals that are not q-good is L~~oq - j - it, where r = min{k - 1, l(q - j)/d}. There are k such O-linearizations for each j. When k> 1, in this class of (k, qk + p)-arrangements every O-linearization has more than pO-intervals that are q-good. REFERENCES 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

D. F. Bailey, Counting arrangements of l's and -1's, Math. Mag. 69 (1996), 128-131. K. L. Chung and W. Feller, Fluctuations in coin tossing, Proc. Nat. Acad. Sci. USA 35 (1949), 605-608. N. Dershowitz and S. Zaks, The cycle lemma and some applications, Europ. I. Comb. 11 (1990), 35-40. D. A. Duffus, H. A. Kierstead, and H. S. Snevily, An explicit I-factorization in the middle of the Boolean lattice, I. Comb. Th. (A) 65 (1994), 334-342. A. Dvoretzky and T. Motzkin, A problem of arrangements, Duke Math. I. 14 (1947),305-313. W. Feller, An Introduction to Probability and Its Applications I, 3rd edition. Wiley & Sons, 1968. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, 1989. P. Hilton and J. Pedersen, Catalan numbers, their generalization, and their uses, Math. Intelligencer 13 (1991), 64-75. H. A. Kierstead and W. T. Trotter, Explicit matchings in the middle levels of the Boolean lattice, Order 5 (1988), 163-171. B. Montagh, A simple proof and a generalization of an old result of Chung and Feller, Discrete Math. 87 (1991), 105-108. T. Narayana, Lattice Path Combinatorics with Statistical Applications. Math. Expositions 23, Univ. of Toronto Press, 1979. A. M. Odlyzko and H.S. Wilf, The Editor's Corner: n coins in a fountain, Amer. Math. Monthly 95 (1988), 840-843. G. N. Raney, Functional composition and power series reversion, Trans. Amer. Math. Soc. 94 (1960), 441-451. A. D. Sands, On generalized Catalan mlmbers, Discrete Math. 21 (1978), 219-221. H. S. Snevily, Combinatorics of finite sets. Ph.D. Thesis, University of Illinois, 1991.

HUNTER S. SNEVILY received his Ph.D. from the University of Illinois under Douglas West. He was a Bateman Research Instructor at Caltech (1991-93) and is' now an Associate Professor of Mathematics at the University of Idaho. His research interests are extremal set theory, graph theory, and combinatorial properties of permutations. His nonmathematical interests are spending time with his family, traveling, playing poker, and hiking. He would have titled the present monthly article "Another Brick in the Wall", but the second author did not wish to mix Pink Floyd and mathematics. University of Idaho, Moscow, ID [email protected] DOUGLAS B. WEST studied at Princeton and M.I.T., birthed in combinatorics by Daniel Kleitman in 1978. He teaches at the University of Illinois, previously at Princeton and (as a visitor) at Stanford and Berkeley. An Associate Editor of the Monthly and Vice Chair of the SIAM Discrete Math Activity Group, he has written two books: Introduction to Graph Theory and (with John D'Angelo) Mathematical Thinking: Problem-Solving and Proofs. His research interests include graph theory and partially ordered sets. He plays squash avidly and sings in the chorus of the Illinois Opera Theatre. University of Illinois, Urbana, IL [email protected]

1998]

THE BRICKLAYER PROBLEM AND THE STRONG CYCLE LEMMA

143

A Computer Search for Free Actions 'on Surfaces Craig M. Johnson

1. INTRODUCTION. Topologists like to push, deform, and generally mistreat certain types of objects. In particular, they hold a long-time fascination with surfaces because they are so visually accessible. Here a closed surface is a compact, connected 2-manifold without boundary. By a standard classification theorem, the orientable surfaces (other than the 2-sphere) consist only of connected sums of k copies of the torus Tk = T#T# ... #T and the non-orientable surfaces consist only of sums of k copies of the real projective plane Uk = RP2# ... #RP2. The integer k is called the genus of the surface. A connected sum of two surfaces is obtained by cutting out a 2-disc "hole" on each surface and then gluing them together along the boundaries of the two holes. T2 = T#T is shown in Figure 1.

Figure 1. The closed surface T2.

Movement of a point on a surface can be performed by a member of a finite group according to a prescribed action of the group. A group G acts on a space X if every element in G induces a homeomorphism from X onto itself. An action on an orientable surface is said to be orientation-preserving if no element of G induces a reversal of a pair of vectors in the basis for any coordinate frame on the surface. Otherwise, it is orientation-reversing. For example, if you rotate a bicycle tire around its axle through a quarter-tum, you have physically carried out an action by the generator g of the finite group Z4 = {l, g, g2, on the torus T. A half-tum performs the action of g2 and so on; see Figure 2. This particular action is

e}

Figure 2. Orientation-preserving free action by Z4 on the torus T.

144

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

[February

orientation-preserving because the tire is not turned "inside out" by the application of any of the elements of Z4' Moreover, no points of T are left fixed by any member of Z4 (other than the identity) and so we call the action ftxed~point free or simply, a free action. The question we explore was introduced to me by Larry Cusick: Are there any orientation-reversing free actions on Tk by finite groups? One reason I found this question interesting is that the search for actions led to a search for group homomorphisms of a certain specialized type and this, in turn, lent itself to a computer investigation. Linkage between topology and computers intrigues me since it has not been too many years since I foolishly swore to several witnesses that most topological problems had the glorious virtue of being unassailable by computer techniques. Such pretentiousness calls for public penance. 2. PRELIMINARY NOTIONS. A covering of a base space B is a fundamental concept in topology. It is a space-map pair (X, p) with p: X ~ B continuous and surjective and satisfying this condition: Every point b E B has an open neighborhood U such that p-1(U) is a disjoint union of open sets in X, each of which is mapped homeomorphically by ponto U. For example, the real numbers R along with the map p: R~Sl defined by p(t) = (cos 27Tt, sin 27Tt) together form a covering of the unit circle by the reals; see Figure 3.

0/' +--r----~--_r----~--~--~~.

1

2

3

4

5 30/ = 5

RjZ..,SIO Sl

0/

E 1T 1S 1 ..,

po a'

R

6

=

Z a

0,0)

Figure 3. The action of a member of 1Tl Sl on R corresponding to the covering map pet) = (cos 21Tt, sin 21Tt).

If X and B are path connected and locally path connected spaces, let p: (X, x) ~ (B, b) be a covering map such that p(x) = b. Then the induced

homomorphism p*: 7T1(X, x) ~ 7T 1(B, b) on the fundamental groups is injective. Each loop in 7T 1(B, b) can be lifted to a path connecting two points in p-1(b) and so gives rise to a well-defined action of 7T1(B, b) on p-1(b). For instance, in the preceding example, let a E 7T l(Sl, (1, 0)) be the loop beginning at (1,0) and wrapping around the circle twice. For rn E p-1((1, 0)), we wish to define ma. There exists a path a': I ~ R having initial point m and terminal point m + 2 such that po a' = a. We then define rna = m + 2; see Figure 3. Those coverings (X, p) of a space B for which p * 7T l(X, x) is a normal subgroup of 7T1(B, b) form an important class called regular coverings. For a 1998]

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

145

regular covering, the group G of automorphisms of X operates transitively on p-l(b) for b E B and we may dispense with basepoint notation. Also, the quotient group 'TT'lB/p*'TT'lX must be isomorphic to G, providing us with the following short exact sequence 1 ~ 'TT'lX ~ 'TT'lB ~ G ~ 1. f

g

For 1 ~ G 1 - G 2 - G 3 ~ 1 to be a short exact sequence of groups and homomorphisms, we must have f injective, g surjective, and im f = ker g. Therefore, it must be the case that G 2 /G 1 ~ G 3 • On the other hand, if we are given a connected, locally path-connected topological space X and a finite group G acting freely on X, then the projection p: X ~ X/G of X onto its orbit space provides a regular covering. Thus, we have the associated short exact sequence 1 ~ 'TT'lX ~ 'TT'l(X/G) ~ G ~ 1.

Consequently, one way to examine free actions is to study exact sequences of this type. Substantial work has been done on orientation-preserving free actions on closed surfaces by A. Edmonds in [3] and [4]. Because we wish to determine orientation-reversing (henceforth abbreviated as "o.r." free actions on closed surfaces by finite groups, • We consider only actions on the orientable surfaces Tk, and • We consider only actions by groups of even order, because no element of odd order can reverse orientation and odd ordered groups contain only elements of odd order. The following classification theorem is well-known. Theorem 2.1. [7, p. 33] Closed swfaces Sl and S2 are homeomorphic if and only if their Euler characteristics are equal and both are orientable or both are nonorientable. Thus, orientability and Euler characteristic (denoted by X(,» completely classify a surface. For example, X(Tk) = 2(1 - k) and X(U k ) = 2 - k. Lemma 2.2. [1] If G is a finite group of order 2n, acting freely and o.r. on T" r + 1 , then the orbit space Tnr+1/G is homeomorphic to U r+2 •

Prool T" r + 1 is a connected and locally connected space. Therefore, the natural projection map p: T nr +1 ~ T"r+1/G is a regular cover. Since T nr +1 is a closed surface, Tnr+1/G must also be a closed surface. Since the action of G is o.r., Tnr+1/G must be nonorientable. Now, the Euler characteristics of any covering space and its orbit space are related by the formula IGI . X(X/G) = X(X). Thus, x(Tnr+1/G) =

X(T nr +1)

IGI

-2nr

= - - = -r. 2n

Since we must have a nonorientable surface with Euler characteristic -r, Tnr+1/G ~

U r +2 •

•

By Lemma 2.2, if G acts freely, orientation-reversing on T" r+ 1 with IG I = 2n, then there exists an associated exact sequence 1 ~ 'TT'lT nr +1 ~ 'TT'lU r+2 ~ G ~ 1.

146

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

[February

On the other hand, suppose we begin with an epimorphism a: 7T 1U r +2 ~ G, where G is a finite group of even order. Lemma 2.3. [1] Let a: 7T 1U r +2 ~ G be an epimorphism where IGI

=

2n. Then

either

i) ker a;::: 7Tlu2nr+2 in which case G acts freely on u 2nr +2, or ii) ker a;::: 7T 1T nr +1 in which case G acts freely and o.r. on Tnr+l. Proof" ker a is a normal subgroup of

7T pr+2. It is well-known [7, p. 175] that there must exist a corresponding regular covering p: X ~ U r + 2 for which P*7T 1 X = ker a. Since p * is injective, we have the short exact sequence

1

~

P.

7T 1 X -+ 7T 1U r

+2

-

a

G

~

l.

By the discussion following the definition of regular coverings, we know G is isomorphic to the automorphism group of X and so acts freely on X. By the Euler formula, x(X) = IGlx(U r+2 ) = -2nr. Because U r+2 is a closed surface, X must be a closed surface also. Therefore, the only two choices for X are u 2nr + 2 and T nr + 1 from which the stated two cases result. • Lemma 2.2 and case GO of Lemma 2.3 combine to form the following theorem, which is the point of all the preceding information. Theorem 2.4. Let G be a finite group. If IGI = 2n, then G acts freely and o.r. on T nr +1

if and only if there exists a short exact sequence

We now wish to develop a theorem (Theorem 2.7) that provides our basis for determining which groups act freely and o.r. on orientable surfaces. The fundamental group of Uk is:

In this presentation, even though the length of two representations of a specific word may vary, the parity is well-defined. It is straightforward to show that no word can be both an odd and an even product of generators. Now, if Z2 is the cyclic group of order 2 with non-trivial element T, we let

ge the special epimorphism defined by e( a) =

/a j are a set of generators for

7T 1U r+ 2.

T for j = 1, ... , r + 2, where the The following lemma is immediate.

Lemma 2.5. Consider the map e: 7T 1u r+2 ~ Z2 that sends every generator of 7T 1U r +2 to the non-identity element T of Z2. Then ker e is the subgroup of 7T 1U r+ 2 consisting of all words of even length. Definition. [1] If a: 7T 1u r+2 ~ G is an epimorphism and G is finite, then define Na = a kere. 1998]

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

147

Notice that [G: NaJ = iGi/iNai =

[7T P r+ 2 : ker a] / [ a- 1( Na ) : ker a]

= [7Tpr+2: a-1(Na)] (by Lagrange's Theorem since ker a < a-1(Na)) = [7Tpr+2:kere]/[a- 1(Na):kere] (sincekere< a-1(Na)) =

2/[ a- 1( Na ) : ker e] .

This implies the following remark. Remark 2.6. The only possible values for [G: Na ] are 1 or 2. Let a: 7T 1U r + 2 -) G be an epimorphism for iGi = 2n. L. Cusick [1] showed that if [G: Na ] = 2, then ker a;: 7T1Tnr+l. The converse is true as well and was proved in my doctoral dissertation [6, p.lO]. According to Theorem 2.4, if ker a;: 7T 1T nr +1, then G acts freely and o.r. on Tnr+l. As it turns out, the subgroup Na is composed of the elements of G that preserve orientation on Tnr+l. So, if [G: Na] = 1, then G = Na and G does not contain an element that reverses orientation. Since this is not the case, we must have [G: Na ] = 2 by Remark 2.6. Theorem 2.7. If a: 7T 1U r + 2 -) G is an epimorphism and iGi = 2n, then [G: Na ] = 2 if and only if ker a;: 7Tlmr+l. 3. THE COMPUTER SEARCH FOR FREE ACTIONS. We now use Theorem 2.7 to put the computer to work looking for free o.r. actions on orientable surfaces of small genus. We examine groups of even order less than 15. If a group G of order 2n acts freely on a surface T n +1, then X(Tn+1/G) = -1, T n+1/G = U 3 , and the action must be o.r. (The Euler formula prevents G from acting freely on a surface of genus less than n + 1.) This situation corresponds to Theorem 2.4 with r = l. We now have the sequence 1 -) 7T 1T n+1 -) 7T 1U 3 -) G -) l. Theorem 2.7 gives us a means for determining all such sequences (if any) for a given G by employing a computer to repeatedly perform the steps in the following algorithm: • • • •

Construct all possible homomorphisms a: 7T 1U 3 -) G. Determine which of these are epimorphisms. For each epimorphism a, compute the subgroup Na• If Na is a proper subgroup of G, then [G: Na] = 2 and we have an o.r. free action. If Na is all of G, then we do not have an o.r. free action.

Before we begin our search, we quickly address the preliminary question: Are any of the free actions discovered using the preceding algorithm equivalent in a natural way? The notion of equivalence used here is the same as that presented by A. Edmonds in [3] and [4]. Let ORF(G, Tn+l) denote the set of o.r. free actions of G on Tn+l. Then each element cfJ of ORF(G, Tn+l) can be thought of as an injective homomorphism cfJ: G -) Homeo(T n + 1 ) where Homeo(T n + 1 ) is the group of homeomorphisms of T n + 1 and each cfJ(g), g *- 1, has no fixed points. The action of Homeo(T n + 1 ) on itself by conjugation induces an action of Homeo(T n + 1 ) on ORF(G, m+l). The collection ORF(G, T n + 1 )* of Homeo(T n + 1 )-orbits is the set of equivalence classes

148

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

[February

of o.r. free actions of G on Tn+l. This means that CPI and CP2 are equivalent o.r. free actions if there exists a homeomorphism h: T n + l -) T n + l such that CP2(g) h = h CPI(g) for every g E G. Now let EPz<7Tp3, G) be the set of epimorphisms a of 7Tp3 onto G such that [G: N a ] = 2. The set of automorphisms of 7Tp3, Aut(7T I U 3), acts on EPZ<7T I U 3, G) by precomposition: a· {3 = a {3-I.for a E EP2(7TP3, G), {3 E Aut(7TP3). The collection EPZ<7T IU 3,G)* of Aut(7T IU 3)-orbits is the set of equivalence classes of EP2( 7T IU 3, G) under this action. This means that epimorphisms a l and a2 are equivalent if there exists an element {3 in AUt(7TP3) such that a 2 = a l o {3-I. A proof of the following theorem can be found in [6, p. 15]. 0

0

0

Theorem 3.1. Let CPI' CP2 E ORF(G, Tn+l) be the free actions on T n+l corresponding to epimorphisms aI' a 2 E EPz<7Tp3, G). Then CPI is equivalent to CP2 if and only if al is equivalent to a 2. Corollary 3.2. There is a bijection ORF(G, m+ l )* ~ EP2(7T I U 3, G)*. Definition. Let 7Tp3 = (aI' a 2, a 31(a l )2(a 2)2(a3)2 = 1) and let a be an element of EPz<7Tp3, G). We can represent a by the ordered triple (gl' g2' g3) of elements of G where a(a l ) = gl' a(a2) = g2' and a(a 3) = g3. We call this triple a Hurwitz system [4] for the epimorphism a. Remark 3.3. It is immediate that if aI' a2 E EPz<7Tp3, G) possess Hurwitz systems that are permutations of each other, then a l is equivalent to a2 as are the free actions CPI' CP2 in ORF(G, Tn+l) that correspond to aI' a 2.

Now we can get down to business and consider the groups of even order ~ 14 for possible o.r. free actions on orientable surfaces. Specifically, for a given n, each group of order 2n is checked for actions of this type on Tn+l. (Recall that this is the maximal order group that can act on T n + l in this manner.) We stop with order 14 simply because each group must be tested individually and the number of groups of order 16 and greater becomes prohibitively large. The alternating group A4 need not be checked, because IA41 = 12 and A4 has no subgroups of order 6 [5, p. 51]. It follows that A4 cannot have a subgroup of index 2, and so Theorem 2.7 eliminates A4 as a candidate. We list the presentations for the non-cyclic groups under consideration [5, pp. 96-99]. TABLE

1. Presentations for the non-cyclic groups of small order.

Order

Group

4 6 8 Z2 X Z4

Q8 D4 10

1998]

Presentation

(a, = 1, b 2 = 1, ab = ba) 3 (a, bla = 1, b 2 = 1, ba = a-1b) (a,b,ela 2 = 1,b 2 = 1,e 2 = 1, ab = ba, ae = ea, be = eb) (a, bla 4 = 1, b 2 = 1, ab = ba) (a, bla 4 = 1, b 4 = 1, ba = a-1b) (a, bla 4 = 1, b 2 = 1, ba = a-1b) (a,bla S = 1,b 2 = 1,ba = a-1b) (a, bla 6 = 1, b 2 = 1, ab = ba) (a, bla 6 = 1, b 2 = 1, ba = a-1b) (a, bla 6 = 1, b 2 = a 3 , ba = a-1b) (a, bla7 = 1, b 2 = 1, ba = a-1b) bla 2

Ds

12

Z2 X Z6

14

D6 W D7

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

149

4. THE ALGORITHM. Because manual construction of epimorphisms and deter-

mination of corresponding Na subgroups would be a very large, tedious computational task prone to error, I wrote a family of computer programs to do these labors. Here is an example of how the basic algorithms were implemented in the case of G = D 4 , the dihedral group of order 8. The algorithm is displayed by the flowchart in Figure 4. Comments Step 2

Potential a represented by (gl' g2. g3)·

Step 3

Check if a is a homomorphism.

Step 4

Generation of a( 1T 1U3 }.

Check to see if a is onto. Generation of N" = a(even words}. Step 5

Check if [0:

N"l =

2.

Figure 4. Flowchart for the determination of Hurwitz systems from D4 •

Question. Does

D4

act freely, orientation-reversing, on T 5?

Step 1. The 8 elements of

D4 are generated and stored as integer 3-by-3 matrices. Representation of the generators by integer matrices is essential. Approximations associated with storage of real values and roundoff errors that occur in arithmetic operations with real values would lead to unreliable results. We let

a=[~o ~ =~l' b=[~ ~ ~l

1 -1 1 0 0 serve as the generating matrices. It is easily verified that a 4 = I, b 2 = I, and ba = a-lb, where I is the 3-by-3 identity matrUc, and that a and b generate an 8 element group. 150

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

[February

Step 2. Since 7r I U 3 = (aI' a z , a 31(a l )Z(a Z)Z(a 3)Z = 1), three elements of D4 , call them gl' gz, g3' are selected as the images of aI' a z, a 3 under a homomorphism a: 7r I U 3 ~ D 4 • Step 3. In order for a to be a homomorphism, it must preserve the relation in 7rp3. Compute the product (gl)Z(gZ)Z(g3)z, If it fails to equal the identity, we return to the previous step and pick 3 new elements of D 4 • Step 4. Determine whether a, characterized by (gl' gz, g3)' is an epimorphism or not. This is done by computing the subgroup a(7r I U 3 ) and counting the number of elements in it. Specifically: (i) Place gl' gz, g3 into an array. (ii) Compute all possible products using elements from this array. (iii) If a new distinct element is formed, add this element to the array and go back to (ii). (iv) Repeat the loop formed by (ii) and (iii) until no new elements are formed. The resulting array contains the elements of a( 7r IU 3 ). This process must terminate in a finite number of loops, since a(7r I U 3 ) forms a subgroup of D 4 • (v) Count the number of elements in the array. If this number does not equal 8 (in which case it must be 1, 2, or 4), return to Step 2.

Step 5. Compute Na = a(ker 8). By Lemma 2.5, ker 8 consists of all even words in 7r I U 3• Therefore Na consists of the images of those even words under a. So we begin the list of Na elements by computing all possible products gigj and loading only the distinct products. Then we repeat (ii) through (iv) as in Step 4. The final array contains only the images of even words of 7r I U 3 and thus the elements of Na. If the number of these elements equals 4, then [G: Na ] = 2 and we have a free action associated with the epimorphism a where a(a l ) = gl' a(az) = g2' a(a 3 ) = g3' Note that a E EPZ(7r I U 3, D 4 ) possessing Hurwitz system (gl' gz, g3)' Step 6. Return to Step 2 until all possible triples (gl' gz, g3) have been chosen. Remark 4.1. The preceding steps imply that a Hurwitz system (gl' gz, ated with an element a of EPz(7rp3, G) must satisfy the 3 conditions:

i) (gl)Z(gZ)Z(g3)2 = 1. ii) gl' gz, g3 must generate G. iii) the subgroup Na of even words generated by the pairs 2in G.

gigj

g3)

associ-

must have index

The algorithm yielded 24 free actions of D4 on T5. Each free action is associated with a member of EPZ(7r IU 3, D 4 ) which in turn is characterized by a Hurwitz system of elements from D 4 . They are: (a, a, b); (a, a, ab); (a, a, aZb); (a, a, a 3 b); (a, b, a 3 ); (a, ab, a 3 ); (a, aZb, a 3 ); (a, a 3 , a 3 b); (b, b, ab); (b, b, a 3 b); (b, ab, ab); (b, ab, aZb); (b, ab, a 3 b); (b, aZb, a 3 b); (b, a 3 , a 3 ); (b, a 3 b, a 3 b); (ab, ab, aZb); (ab, aZb, aZb); (ab, aZb, a 3 b); (ab, a 3 , a 3 ); (aZb, aZb, a 3 b); (aZb, a 3 , a 3 ); (aZb, a 3 b, a 3 b); (a 3 , a 3 , a 3 b).

1998]

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

151

We know by Remark 3.3 that permuted systems of elements represent equivalent free actions. Hence, only one permutation is listed for each particular system. However, it is not known whether all of these 24 systems represent non-equivalent o.r. free actions. Therefore, 24 serves only as an upper bound for the number of equivalence classes of o.r. free actions by D 4 • Determination of the actual number of equivalence classes of o.r. free actions is an interesting area for further study. The following table lists the upper bound for the possible number of o.r. free actions admitted by the other groups of small order. The matrix representations of the group generators and the actual Hurwitz systems of elements associated with the actions are available upon request. As in the preceding example, permutations of a particular system are not counted. Table 2 displays some interesting patterns. For instance, observe that there exist no o.r. free actions by Z4' Z8' and Z12. This turns out to be a special case (r = 1) of the following fact concerning free actions by cyclic groups of even order. TABLE 2. Upper Bounds for O.R. Free Actions on T n + 1 by Groups of Order 2n, n ~ 7. Group

Surface

Z2

T2 T3 T3 T4 T4 T5 T5 T5 T5 T5 T6 T6 T7 T7 T7 T7 T7 TS TS

Z4 Z2 X Z2 Z6

D3 Zs Z2 X Z2 X Z2 Z2 X Z4

Qs D4 ZlO

D5 Z12 Z2 X Z6

A4 D6 W

Z14 D7

ZZn

1 0 6 3 7

0

28 12 0

24 6 30 0 30 0

42 0 11 77

acts freely and o.r. on T nr + 1 for every n ~ acts freely and o.r. on T nr + 1 if and only if n is odd.

Theorem 4.2. Ifr is even, then

is odd, then

Upper Bound

ZZn

o.

Ifr

The proofs are straightforward (see [6] for details), but one observation here is that such results may never have been speculated without a computer to do the dirty work. Technology has become an indispensable tool in our continuing search to discover beautiful connections in science, mathematics, and nature. ACKNOWLEDGMENT. This paper would not have been possible without the assistance of Larry W. Cusick, whose generosity seems to be without bound. I also wish to thank Daniel H. Gottlieb for his support and many valuable suggestions.

152

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

[February

REFERENCES 1.

2. 3. 4. 5.

6. 7.

8. 9.

10.

L. W. Cusick, Finite Regular Covers of Surfaces, Canad. Math. Bull. 29 (2) (1986), 185-190. L. W. Cusick, Free Actions on Spaces with Non-zero Euler Characteristic, Topology Appl. 33 (1989), 185-196. A. L. Edmonds, Surface Symmetry I, Michigan Math. J. 29 (1982), 171-183. A. L. Edmonds, Surface Symmetry II, Michigan Math. J. 30 (1983), 143-154. T. W. Hungerford, Algebra, Holt, Rinehart and Winston, Inc., New York, 1974. C. M. Johnson, Orientation-Reversing Free Actions on Closed Orientable Swfaces by Finite Groups, Ph.D. Dissertation, Purdue University, 1989. W. S. Massey, Algebraic Topology: An Introduction, Harcourt, Brace & World, Inc., New York, 1967. R. E. Mosher and M. C. Tangora, Cohomology Operations and Applications in Homotopy Theory, Harper & Row, New York, 1968. J. J. Rotman, Theory of Groups: An Introduction, Second Edition, Allyn & Bacon, Boston, 1973. E. H. Spanier, Algebraic Topology, McGraw-Hill, New York, 1966.

CRAIG M. JOHNSON received his B.S. from the University of Illinois and his Ph.D. from Purdue University. He taught for eight enjoyable years at College of the Sequoias in central California before joining the faculty at Marywood University in scenic Northeast Pennsylvania. His main interests are algebraic topology and the enrichment of mathematics courses for the non-major. His book, Functions of Mathematics for the Liberal Arts, is due out within the next year from Brooks/Cole. He enjoys chess, astronomy, and the piano, although most of his spare time is spent yakking with his wife, Debra, and sharing in the lives of his two terrific sons, Scott and Nick. Marywood University, Scranton, PA 18509 [email protected]

From the MONTHLY 75 years ago, Volume 30, 1923

HistOlY of the Theory of Numbers. By L. E. DICKSON, Volume Ill, Quadratic and Higher Forms. With a Chapter on the Class Number, by G. H. CRESSE. Carnegie Institution, Washington, D.C. March, 1923. v + 313 pages. The astonishing rapidity with which Professor Dickson has made the manuscript ready for the printer and has seen through the press the first three volumes (1919, 1920, 1923) of his monumental history of the theory of numbers must be a cause for admiration on the part of everyone who has witnessed the performance; and the surprise only increases when the reader finds that each volume is done perhaps even more skillfully than the preceding one. In the preface to the third volume we are told that it has been completed promptly owing to the f,avorable reception accorded to the first two volumes. The preface to the second volume closed with a sentence referring to the third as the concluding volume; but in the third now before us we have (on page 3) a reference forward to volume IV. The reviewer ventures to predict that the favorable reception of the third volume will give the author still more reason for proceeding promptly with the fourth if his astonishing supply of energy is holding out well enough to. leave him still susceptible to such int1uencc. (p. 259)

1998]

A COMPUTER SEARCH FOR FREE ACTIONS ON SURFACES

153

Division Algebras-Beyond the Quaternions John C. McConnell

1. INTRODUCTION. Why do we know so few division algebras? Most mathematicians know of the real quaternions but many might have difficulty giving any other examples of division algebras or a method for constructing them. A division algebra is, of course, an associative ring in which each nonzero element has an inverse and that is finite-dimensional over its centre, which is a field. Hamilton discovered the real quaternions on 16 October 1843. As complex numbers could be used to represent points in the plane, Hamilton was trying to find an extension of the complex numbers that could be used to represent points in 3-space. He finally constructed the real quaternions, a division algebra that is four-dimensional over its centre, the real numbers. The price he had to pay was that multiplication in the real quaternions is non-commutative. Mter the construction of the real quaternions, the search for other examples of division algebras was rather slow. In 1877, Frobenius [Fl, proved that the only division algebras over IR (i.e., those whose centre contained IR and that are finite-dimensional over IR) are the real numbers, the complex numbers, and the quaternions; this was also proved independently by C. S. Peirce [Pel Some division rings that are not finite-dimensional over their centres were constructed for use in geometry; there is such an example in Hilbert's Foundations of Geometry [Hi, Sect. 33]. Based on a 'twisted' power series construction, it is a non-archimedean ordered division ring. Hilbert used it to exhibit a geometry in which Desargues' theorem holds but Pascal's theorem does not. In 1905, Wedderburn [WI] proved that any finite division algebra is a field, i.e., a division algebra whose centre is a finite field must be commutative. In his famous paper [W2 ], Wedderburn showed that extending the centre of a division algebra to its algebraic closure L turns the division algebra into a complete matrix ring over L; he deduced that the dimension of a division algebra over its centre is a square. But, up to 1906, no progress had been made on what to us now would be a natural question: describe the division algebras with centre K, where K is a field other than IR (for example, Q or any other algebraic number field). In 1906, Dickson made the first step in this direction with his abstract [DIl. Dickson defined what are now called cyclic algebras and remarked that, for appropriate choices of the parameters, the resulting algebra is a division algebra. But no details were given. Dickson waited until March 1913 to write up the paper [D 2 ] containing the division algebra part of his 1906 abstract, but we do not know what Dickson wrote in the original version of this paper. Wedderburn saw the original version and proved a general theorem (in November 1913; see [D 2 , p. 33]), which gave a sufficient condition for Dickson's construction to yield a division algebra. Dickson then revised his paper shortly before its publication in January 1914 and quoted (incorrectly!) Wedderburn's result. From the introduction to Wedderburn's April 1914 paper [W3]' it is clear that in the original version of his paper, Dickson had managed to construct examples of division algebras only of dimension 4 or 9 over the centre. Wedderburn's theorem is now usually obtained as a corollary to more general theorems about crossed products and the Brauer group; see [Pi, 15.1 Corollary d]. 154

DIVISION ALGEBRAS-BEYOND THE QUATERNIONS

[February

This is unfortunate, as Dickson's construction and Wedderburn's proof use only a little Galois theory and linear algebra; the proof is a gem of the algebraist's art. Our goal is to put Wedderburn's theorem in its historical context and to present Dickson's construction and Wedderburn's proof in a self-contained form readily accessible to a wide audience. Further, Dickson and Wedderburn considered only the question of when a cyclic algebra is a division algebra and did not consider related questions such as: When is it simple? When is it a complete matrix ring over the ground field? We use their methods to answer these questions. 2. QUATERNIONS. The standard example of a finite dimensional division algebra is Hamilton's quaternions IHI, which has dimension 4 over its centre IR, {l, i, j, k} as an IR-basis, and multiplication table i 2 =/=k 2 = -1, ij= -ji=k, jk= -kj=i, ki= -ik=j. To see that IHI is a division algebra note that if 0 *- a1 + bi + cj + dk, then (a1 + bi + cj + dk)(a1 - bi - cj - dk) = a 2 + b 2 + c 2 + d 2 *- O. Another way of looking at IHI helps to motivate the concept of a cyclic algebra. Let C = 1R1 + lRi and let e denote 'complex conjugation', the non-identity automorphism of Cover R Then IHI = C1 + Cj, and for a E C, ja = e( a )j,

j2 = -1.

3. GALOIS EXTENSIONS. Let L be a finite Galois extension of a given field K, and let G = Gal(L/K) be the Galois group of Lover K. Recall that L is a finite Galois extension of K when the number of automorphisms of L that act as the identity on K coincides with the dimension of Lover K, and then the elements fixed by all of these automorphisms are just the elements from K. We write elements of K as a, b, ... , elements of L as a, (3, ... , and elements of G as e, 4>, .... The dimK(L) is denoted by n. Let EndK(L) denote the ring of K-linear transformations from L to L. By taking a basis for Lover K, EndK(L) can be identified with the ring Mn(K) of all n X n-matrices over K. Now consider the subring A of EndK(L) generated by multiplications by the elements of L and the automorphisms from G. Let e E G and a, (3 E L. Then in EndK(L), ( ea ) ( (3) = e ( a (3) = e ( a) e ( (3) = (e ( a) e)( (3), and so ea = e(a)e. Thus each element of A can be written as a linear combination L:a.fJ. of the elements of G, with coefficients on the left from L. A standard theorem of Galois theory, the Dedekind Independence Theorem, asserts that the elements of G are linearly independent over L, i.e., that L:ases = 0 if and only if all the coefficients as are zero; see [J, Sect. 4.14]. Since the dimension of Lover K is n and there are n automorphisms in Gal(L/K), the dimension of A over K is n 2 and so A is the whole of Mn(K).

4. CYCLIC EXTENSIONS. Consider now the case when G is a cyclic group of order n, generated bye, say. Thus A = Mn(K) has basis 1, e, ... , en- I as a left vector space over L and the relations are ea = e(a)e, en = 1. In A, e is not the only invertible element j of A that induces e on L (i.e., for which ja = e(a)j); any L-multiple ')Ie, ')I *- 0, would also do. Now (')Ie)n = (')Ie)( ')Ie) ... (')Ie) = ')Ie ( ')I) '" e n- I ( ')I) en = N( ')I )en, 1998]

DIVISION ALGEBRAS-BEYOND THE QUATERNIONS

155

where N( 1') denotes the norm of l' (i.e., the product of the images of l' under the elements of the Galois group), which is an element of K. Let K* and L* denote the nonzero elements of K and L, respectively, and let N(L*) denote the set of norms of elements of L*. Note that N(a) = an for all a E K. 5. CYCLIC ALGEBRAS. We are now in a position to define a cyclic algebra, as given by Dickson in 1906. It is denoted by A = (L/K, (J, a) (or by ~(a) if K, L, and (J are clear), where L is a finite Galois extension of a field K with cyclic Galois group (of order n), (J is a generator of the Galois group, and a E K*. As a left L-vector space, A has a basis consisting of the powers 1, j, jZ, ... , -1 of an element j and the relations are j a = (J ( a) j for a E L, = a.

r

r

Proposition 5.1. (i) If there exists l' E L such that b = N( l' )a, then ~(a) and ~(b) are isomorphic as K-algebras, i.e., there is a ring isomorphism that is the identity on K. (ii) In particular, if a E N(L*), then ~(a) "" ~(1) "" Mn(K).

Proal These are clear from the preceding comments; for (i) there is an isomor_ phism from ~(a) to ~(b) that is the identity on L and sen~ 1'j to j. The converse of 5.1 (i) is also true, but the proof requIres the Skolem-Noether Theorem, which enables us to assume that the given isomorphism is the identity on L, from which the result follows easily; the converse to (ii) is given in Proposition

6.2. Consider the case K = IR, L = C, and (J = complex conjugation. For a = a + ib E C, N(a + ib) = (a + ib)(a - ib) = a Z + b Z , which can be any positive real number. Since the group of non-zero real numbers modulo the group of positive real numbers is just {l, - 1} there are, up to isomorphism, just two cyclic algebras . ~(a) corresponding to a = 1 and a = -1: Mz
Proal A routine calculation shows that the product of elements of the form asF is associative. The proof that ~(a) is simple is the same as the proof of the Dedekind Independence Theorem mentioned earlier (by taking the difference between suitable left and right L-multiples of a non-zero element one can produce _ a unit of the form asF). The remainder is straightforward. 6. CALCULATIONS IN ~(a). We wish to talk about the product of elements in for different values' of a, so let V denote the underlying additive group of ~(a), V = L1 + Lj + ... +Lr-l, and regard the elements of Vas polynomials in j with coefficients from L. ~(a)

Lemma 6.1. (i) Let f, g E V. If deg f + deg g < n, then deg fg = deg f + deg g and the product fg in ~(a) is independent of a. (ii) If f = / + a r_ 1 / - 1 + ... + a o E V, with 1 ~ r ~ n - 1, then there exists g = r-r + f3n_r_d n- r- 1 + ... + f30 E V (independent of a) such that, for all a E K*, deg (gf) < deg f (in ~(a)). Further, the non-constant terms of gf are independent of a and the constant term of gf in ~(a) is a + f30 ao. 156

DIVISION ALGEBRAS-BEYOND THE QUATERNIONS

[February

en

Proof" is clear. (ii) Consider a product (r-r

+

f3n-r-1 r-r-1

+ ... + f3o)(jr + a r_ 1/- 1 + '" + 0. 0 ),

where the f3s are to be determined recursively. Setting the coefficient of r- 1 equal to 0 in the product determines f3n-r-1' setting the coefficient of r-(n-r) equal to 0 determines f30. The rest is clear. • A linear transformation on a finite-dimensional vector space is injective if and only if it is surjective, and hence in a finite-dimensional algebra an element is either a unit or is a zero-divisor. Proposition 6.2. W(a) is isomorphic to W(l) (as K-algebras) if and only if a

E

N(L*).

Proof" = See Proposition 5.1Oi). = W(a) "" W(l) "" Mn(K) has a left ideal I (corresponding to the sum of the first n - 1 columns) such that the factor space has dimension n over K, or dimension one over L. In W(a) a nonzero left ideal is principal since it is generated by a monic polynomial of least degree. Since W(a)/I is one-dimensional over L, 1= W(a)(j - a) for some a E L. For f = j - a and g as in Lemma 6.1, g(j - a) has degree less than one, and since j - a is not a unit, g(j - a) = O. Calculating

the coefficients of g yields a

=

N( a).

•

This result has been called 'Wedderburn's criterion', e.g., in [R, pp. 196 and 270], but note that the name 'Wedderburn's norm criterion' is often used for Theorem 6.4. For n = 2 and n = 3, if W(a) is not a division algebra then by Lemma 6.1 it has a zero-divisor of the form j - a, and then the argument in the proof of Proposition 6.2 yields a E N(L*). This argument covers what Dickson had in 1906 and in the original version of [D 2 ]. Dickson gives his argument for n = 3 in [D 2 ] but it is more complicated than that just given. However knowledge of Wedderburn's theorem on simple algebras [W2 ] (a simple algebra that is finite-dimensional over its centre is a complete matrix ring over a division algebra) immediately yields more information.

en

If a $. N(L*), then W(a) is a complete matrix ring over a noncomCorollary 6.3. mutati12 division algebra with centre K. (ii) Let n = [L:K] be a prime. If a $. N(L*), then W(a) is a division algebra.

en

Proof" By Proposition 5.2, W(a) is simple with centre K, and W(a) ~ Mn(K), so W(a) "" Ms(D), where D is a noncommutative division algebra with centre K. (in Since W(a) = Ms(D), counting dimensions over K yields n 2 = s 2 t, where t = [D:K], so, either s = nand t = 1 with W(a) "" Mn(K), and a E N(L*) by Proposition 6.2, or, s = 1, t = n 2 , and W(a) = D. •

Matrix Representation. Before starting on the proof of Wedderburn's Theorem we require a representation of W(a) by matrices over L, and we also want to observe how these matrices depend on a. In his paper, Wedderburn gave a direct construction of idempotents in terms of elements of W(a). We now know that an easy way to get a representation by matrices is to let elements act as linear transformations on a finite-dimensional vector space, and that is what we do here. 1998]

DIVISION ALGEBRAS-BEYOND TIlE QUATERNIONS

157

The two approaches are equivalent; we end up with the same matrices as Wedderburn did! Regard W(a) as a left vector space over L and as a right space (or module) over itself, each of these actions being given by multiplication. Since the actions are on opposite sides, they commute. For f E W(a), right multiplication by f is an L-linear transformation on W(a) and so can be represented by a matrix, M(j) say, once we have ·chosen an appropriate basis over L. The matrix representing f is given as follows. If Vs is the s-th basis element, then write v.f as a linear combination of the basis elements; the coordinates in this linear combination are the entries of the s-th row of the matrix representing f. As a left vector space over 1 and this is the basis we use. We now calculate L, W(a) has a basis 1, j, ... , M(J) for a general element f E W(a). For a E L, j'a = (}S(a)j' and so M(a) is a diagonal matrix with entries a, (}(a), ... , (}n-l(a). Now

r-

for s for s

+ r .:::; n + r ~ n,

1 and

so

M(jr) = ( 0 aIr Now let 1 .:::; r':::; n - 1 and let f = / + ar_ 1/- 1 + ... +a o. Then M(j) = M(/) + M(ar_l)M(/-l) + ... +M(ao)· Since we need to calculate the determinant of M(j), we describe it in more detail using its diagonals. (Since the M( as) are diagonal matrices the reader can readily visualise this matrix, which may be easier than following the detailed discussion!) We index the diagonals by their left hand entry, so the main diagonal is the e 11 -diagonal. On this diagonal are the entries of the diagonal matrix M(a o). The entries on the e 12 , ... , e1r-diagonals come from M(a 1), ... , M(ar-l)' respectively. The entries on the e1(r+l)-diagonal are all 1. On the diagonals above that all entries are O. The entries on the en1 , ... , e(n-r+2) cdiagonals come from M(a 1), ... , M(a r - 1 ) respectively, but all are multiplied by a. The entries on the e(n_r+l)cdiagonal are all a's. The entries on the e(n-r)l' ... ' e 21 -diagonals are all O. Now, treating a as a parameter, we expand the determinant of M(j) as a polynomial in a. The highest power of a that can be obtained comes from the a's on the e(n_r+l)cdiagonal. The only other term in the polynomial that we need is the constant term, and that must come from the main diagonal, so detM(f) = (_I)(n-r)r a r + ... +N(a o). Note: this leading coefficient turns out to be important! In [W3 ] it is given incorrectly and this appears not to be a printer's error. He really was 'one of us'! We are now in a position to prove Wedderburn's norm criterion [W3]. Theorem 6.4. Let K be an infinite field. W(ao) is a division algebra.

If

aD $. N(L*) for 1 .:::; r .:::; n - 1, then

Proof" If W(a o) is not a division algebra, then it has zero-divisors. Choose a zero-divisor f of least degree in j and, without loss of generality, make f monic, say f = / + a r_ 1/- 1 + ... + ao, where 1 .:::; r .:::; n - 1. By Lemma 6.1, there exists a g with deg gf < deg f, so, by the choice of f, gf = 0 (J is a unit if gf is a unit) and, in particular, its constant term is zero. Lemma 6.1 ensures that a o + f30 ao = 0, 158

DIVISION ALGEBRAS-BEYOND TIlE QUATERNIONS

[February

so f3oao = -ao. Now we consider the product gf in K*, Lemma 6.1 ensures that

~(a)

for arbitrary a. For all

a E

gf=a

+

f3oao =a -ao,

so M(g )M(f) = M(a - ao). Now taking determinants yields [( _l)'(n-r)a n- r + ... +N( (30)] [( _1)(n-r)ra r + ... +N(ao)] = (a - ao)n.

This holds for all nonzero a in the infinite field K, so this expression is an identity in a, i.e., if we replace a by an indeterminate x, then this relation holds in the polynomial ring L[x]. Now L[x] is a unique factorisation domain, so the left hand side of the polynomial expression gives a factorisation of (x - a o)". But the only possible factors are an element of L times a power of x - ao. Thus, for the second factor (in a) we have ( _1)(n-r)r a r

+ ... + N( 0. 0 ) =

(_l)(n-r)r( a - a o)'.

Equating constant terms now yields N(ao) = (-l)(n-r)r(-l)'(a o)' = (-l(ra(j, as r2 == r mod 2. Finally, N(( _1)' 0. 0 ) = N(( -l)')N(a o) = (-l(rN(a o ) = aD'

•

as required.

7. NOTES. (i) An alternative, but rather more sophisticated, version of the preceding proof can be found in [L, p. 233f]. (in We have not actually given any examples of division algebras other than the quaternions! For n = 2 and characteristic K =/= 2, L has to be a square-root extension K(a) of K, where 0.= Ib say, the non-identity automorphism sends a to - a, and a cyclic algebra then looks like quaternions (and is called a generalised quaternion algebra) with 0. 2

= b, j2 = a, ja = -aj.

It is easy to construct similar examples, with 2 replaced by n, with K containing a primitive nth root of 1, and L an nth root extension of K. For more details see [C, Sect. 7.7] or [Pi, Sects. 1.6 and 15.4]. Dickson gave a nice example of a division algebra, where L has dimension 3 over K = Q, but L is not a cube-root extension of K, [D 3 , Sect. 48] or [L, p. 238]. (iii) For more information on Wedderburn's contributions to algebra see [Ar], [Pal, and [Ta].

8. HISTORICAL REMARKS. (i) Dickson's misquotation in [D 2 ] of Wedderburn's norm criterion was to assert that if a is not a norm then the corresponding 'cyclic algebra is a division algebra. This is false (see §9), but from Corollary 6.3 we do know that in this case a noncommutative division algebra is present. (in In [D 2 ] and [W3 ], Dickson and Wedderburn considered only the question of when a cyclic algebra is a division algebra. Neither mentioned the results about simplicity (from Proposition 5.2), about when it is a complete matrix ring over the base field (from Proposition 6.2), or the consequences of Wedderburn's simple algebra theorem (from Corollary 6.3), even though these are all elementary. , Presumably their attention was concentrated on constructing new examples of division algebras. The result mentioned after Proposition 5.1 (that ~(a) = 'l?(b) if 1998]

DIVISION ALGEBRAS-BEYOND THE QUATERNIONS

159

and only if b = N( y )a) is attributed to [W4 ] by Van der Waerden [VW, p. 201]. But none of these results appear explicitly in [W4 ] or even in the book [D 3 ]. It would be interesting to know when these results first appeared explicitly. (iii) In Van der Waerden's book, [VW, p. 201], Wedderburn's norm criterion is wrongly attributed to Dickson. In Appendix 1 of his book [D 3 ], Dickson gives Wedderburn's statement and proof, but he describes it in a footnote: "Announced by the author in [D I ]. The proof by Wedderburn in [W3 ] has been amplified here by the addition of (1) to (10)." The amplification just consists of the addition of the said equation numbers and the correction of the erroneous leading coefficient mentiohed earlier. This choice of the word 'announced' was unfortunate because, as noted earlier, Dickson appears to have had positive results only for small values of n. But since in the instruction to the book, Dickson thanks Wedderburn for his cordial cooperation in its production, too much should not be read into his choice of wording. However, in the revised and expanded German edition [D 4 , Section 42], Dickson proved Wedderburn's theorem, but this time he made no mention of its origins, and indeed made no reference to [W3] anywhere in the book. German readers naturally assumed that the theorem was entirely due to Dickson. 9. GOING FURTHER. Wedderburn's norm criterion is a sufficient condition for W(a) to be a division algebra, but it is not a necessary condition; see [AI] (which

uses ideas from [B]) or [L, p. 236]. For this paragraph, let K be an algebraic number field; the proof of the following statements requires deep results from algebraic number theory. In this case Wedderburn's norm criterion is both necessary and sufficient for W(a) to be a division algebra. In fact [Ha, Thm. 5'], if r is the least integer such that ar E N(L*), then W(a) ~ Ms(D) (D a division algebra), where rs = n. Further, as was noted in [W3 ], there always are elements a E K* satisfying Wedderburn's norm criterion, so for any cyclic Galois extension of K there are (many) cyclic algebras that are division algebras. (That there are many depends on a knowledge of the Brauer group of Lover K, which is beyond the scope of this article.) So any cyclic Galois extension L of K occurs as a maximal subfield of a division algebra with centre K. The cyclic condition cannot be deleted. For example, with K = (D and L = (D( Ii, i) (with Galois group the four-group Cz X C z), L is not a maximal subfield of a division algebra with centre (D, see [S, Theorem 4.2(i)]. Finally, the Albert-BrauerHasse-Noether Theorem [BH], [AH] or [Pi, Sect. 18.4], states that any division algebra D with centre K is a cyclic algebra over K; so if dimK(D) = n Z, then inside D there is a cyclic Galois extension L with dimK(L) = n. Given a division algebra D with centre K, there are infinitely many non-isomorphic subfields L of D for which D is a cyclic algebra; and given a finite set of divison algebras with centre K and having the same dimension over K, then they can all be regarded as cyclic algebras constructed from a single extension field L of K, see [S, §5]. Indeed, the ABHN-theorem starts from the question: When are two cyclic algebras based on different Galois extensions of K isomorphic? See [Ha]. In contrast to the algebraic number field case, if K is the rational function field Ox), then K has finite cyclic Galois extensions but there are no division algebras with centre K other than K itself; this is Tsen's Theorem, [Ts] or [Pi, Sect. 19.4]. For suitable K, there are division algebras with centre K that are not cyclic algebras, the first such example being obtained from a tensor product of cyclic division algebras. This result is usually attributed to Albert [A 2 ] (see [Pi, Sect.· 15.7]), but at least equal credit should be given to Brauer and Hasse. Albert's 160

DIVISION ALGEBRAS-BEYOND THE QUATERNIONS

[February

paper extended the work of Brauer [B, Sect. 5], in which Brauer constructed a division algebra for which the index and exponent were distinct. But in [Ha, Thm. 5], Hasse proved that the index and exponent coincide for a division algebra that is a cyclic algebra. Thus, Brauer's example cannot be a cyclic algebra. Hasse appears to have been unaware of Brauer's example as, after stating Theorem 5 in [Ha], he immediately raised as a major open problem the question of whether there can be a non-cyclic division algebra. For L a non-cyclic Galois extension of K, the concept corresponding to a cyclic algebra is a cross-product algebra. If D is a division algebra with centre K having dimension n 2 over K, then any maximal subfield L of D has dimension n over K. If among these maximal subfields L, one is a Galois extension of K, then D is a cross-product algebra over K. It was conjectured that all division algebras would be cross-product algebras, but a counterexample was found by Amitsur in 1972; see [Am], [R, 7.1.30] or [Pi, Sect. 20.8]. ACKNOWLEDGMENTS. I thank Louis Rowen, David Saltman, Aidan Schofield and Martin Taylor for mathematical information, and Karen Parshall for historical advice.

REFERENCES [Ad [A 2 ] [AH] [Am] [Ar] [B] [BH] [C] [Dd [D 2 ] [D 3 ] [D4 ] [F] [Ha] [Hi] [J] [L] [Pal [Pel [Pi] [R] [S]

1998]

A. A. Albert, A note on cyclic algebras of order sixteen, Bull. Amer. Math. Soc. 37 (1931),

727-730. A. A. Albert, A construction of non-cyclic normal division algebras, Bull. Amer. Math. Soc. 38 (1932),449-456. A. A. Albert and H. Hasse, A determination of all normal division algebras over an algebraic number field, Trans. Amer. Math. Soc., 34 (1932),722-726. S. A. Amitsur, On central division algebras, Israel I. Math. 12 (1972), 408-420. E. Artin, The influence of J.H.M. Wedderburn on the development of modern algebra, Bull. Amer. Math. Soc. 56 (1950), 65-72. R. Brauer, Untersuchungen iiber die arithmetischen Eigenschaften von Gruppen linearer Substitutionen, Zweite Mitteilung, Math. Z. 31 (1930), 733-747. R. Brauer, H. Hasse, and E. Noether, Beweis eines Hauptsatzes in der Theorie der Algebren, I. Reine Angew. Math. (Crelle) 167 (1932), 399-404. P. M. Cohn, Algebra, 2nd. edn, Vol. 3, J. Wiley, Chichester-New York, 1991. L. E. Dickson, Abstract: Linear algebras in which division is always uniquely possible, Bull. Amer. Math. Soc. 12 (1905-6), 441-2. L. E. Dickson, Linear associative algebras and abelian equations, Trans. Amer. Math. Soc. 15 (1914), 31-46. L. E. Dickson, Algebras and their Arithmetics, University of Chicago Press, Chicago, 1923. Algebren und ihre Zahlentheorie, Orell Fiissli, Zurich, 1927. G. Frobenius, Uber lineare Substitutionen und bilineare Formen, I. Reine Angew. Math. (Crelle) 84 (1877), 1-63. H. Hasse, Theory of cyclic algebras over an algebraic number field, Trans. Amer. Math. Soc. 34 (1932), 171-214; Addition, 727-730. D. Hilbert, Grundlagen der Geometrie, 2nd. edn, Teubner, Leipzig, 1903. N. Jacobson, Basic Algebra 1, W. H. Freeman and Co., San Francisco, 1974. T. Y. Lam, A First Course in Noncommutative Rings, Graduate Texts in Mathematics No. 131., Springer-Verlag., Heidelberg, 1991. K. H. Parshall, Joseph H. M. Wedderburn and the Structure Theory of Algebras, Arch. Hist. Exact Sci. 32 (1985), 223-349. B. Peirce, Linear associative algebra with Notes and Addenda by C. S. Peirce, Amer. I. Math. 4 (1881), 97-229. R. S. Pierce, Associative Algebras, Graduate Texts in Mathematics No. 88, Springer-Verlag, Heidelberg, 1982. L. Rowen, Ring Theory, Vol. 2, Academic Press, San Diego, 1988. M. M. Schacher, Subfields of division rings 1, I. of Algebra 9 (1968),451-477.

DIVISION ALGEBRAS-BEYOND THE QUATERNIONS

161

[Tal [Tsl [VWl [Wd [W2 l [W3 l [W4 l

H. S. Taylor, Joseph Henry Maclagen Wedderburn 1882-1948, Obitumy Notices of Fellows of the Royal Society 6 (1948-49), 619-625. c. C. Tsen, Divisionalgebren tiber Funktionkorpern, Gott. Nach. (1933), 335-339. B. L. Van der Waerden, A Histo/y of Algebra, Springer-Verlag, Heidelberg, 1985. J. H. M. Wedderburn, A theorem on finite algebras, Trans. ArneI'. Math. Soc. 6 (1905), 349-53. J. H. M. Wedderburn, On hypercomplex numbers, Proc. London. Math. Soc. 6 (1907),77-118. J. H. M. Wedderburn, A type of primitive algebra, Trans. ArneI'. Math. Soc. 15 (1914), 162-166. J. H. M. Wedderburn, On division algebras, Trans. ArneI'. Math. Soc. 22 (1921) 129-135.

JOHN MCCONNELL was born in 1941 in Northern Ireland. He obtained his PhD. under Alfred Goldie in 1965, and has been a professor at the University of Leeds since 1989. He and his colleague Chris Robson are the authors of Noncommutative Noetherian Rings. While planning a graduate level textbook on ring theory, he asked himself why he knew so few division algebras. Setting out to extend his knowledge led to Wedderburn's paper, which at first he could not comprehend. In due course, an elementary argument emerged from the gloom, and he wanted to share it. School of Mathematics, University of Leeds, Leeds LS2 9fT, England [email protected]

From the MONTHLY 100 years ago, Volume 5,1898 In order to increase our subscription list for next year, we will allow each old subscriber who secures one new subscriber to remit us three dollars in full payment for one year's subscription to the MONTHLY for both. (p. 283) In recent years all the simple groups of the finite continuous groups have been found. It would be a great step forward if all the simple groups of the groups of a finite order could also be found. Several new infinite systems of such groups have recently been discovered by Professors Moore and Burnside, and by Dr. Dickinson but the progress towards the complete solution of this problem is exceedingly slow. Any discoveries that throw light on this subject are of great interest. As problems of somewhat smaller interest in themselves we may mention the proof of the existence or non-existence of simple groups of an odd order .... (pp. 198-199) Proposition XXXI. Now 1 say there will be, of the aforesaid common pelpendiculars in two distinct points, no detenninate limit, such that under a smaller and smaller acute angle made at the point A, it would not always be possible to attain (in hypothesis of acute angle) to such a common perpendicular in two distinct points ay is less than any assignable length R. Proof For in so far as the thing were otherwise; if from the point K in BX assigned at any however great distance from the point B, a perpendicular KL is erected, to which from point A (by Euclid 1. 12) the perpendicular AL is supposed let fall, KL ought to be greater than the length R .... (p. 1)

162

DIVISION ALGEBRAS-BEYOND THE QUATERNIONS

[February

NOTES Edited by: Jimmie D. Lawson

Graphical Discovery of a New Identity for Jacobi Polynomials Brian Gerard and Lawrence Roberts

During the summer of 1995 the authors engaged in an undergraduate research program that investigated various conjectures about orthogonal polynomials. While exploring the graphic capabilities of Mathematica, we generated Figure 1, which shows, on a single set of axes, the graphs of pJa,f3l, the fifth degree Jacobi Polynomials, for /3 = 0.9 and a taking the values 0,1,2, ... ,6. We observed that the curves in the figure appear to intersect at extrema, but our advisors were skeptical about whether this actually happened. We used Mathematica to confirm that it did, which led us to conjecture that p'~a+l, (3)(x) - p~a,(3)(x) = 0 whenever x is an extremum of p~a, (3). Before we prove this conjecture, we review some pertinent details about Jacobi polynomials.

Figure 1. Jacobi polynomials pJa, f3) for f3

=

.9 and

Ci

=

0,1, " . , 6

For a pair (a, /3), a, /3 > -1, p~a,(3)(x) is defined for any non-negative integer n by the Rodrigues formula p(a,f3)(x) = II

1998]

(

-

1) /I

2I1n!(1 _ x) a(1

+ x)f3

(d- )

NOTES

dx

II

[(1-x)a+lI(l +x)f3+ II ] .

163

The p~a, (3) are polynomials of degree n that satisfy the oithogonality criterion

r

p~a,(3)(x)p~a,(3)(x)(1_x)a(1 +x)(3 dx = 0

(m =/= n).

-1

This relation is equivalent to

r

xmp~a,(3)(x)(1-x)"'(1 +x)(3 dx = 0

(m

=

0,1, ... ,n - 1)

(1)

-1

where the integrals are interpreted as improper integrals if a < 0 or {3 < O. We note for later use that (1) determines p~a, (3) up to a constant factor, which is chosen so that

n+a) p~a,(3)(1) = ( n =

r(n+a+1)

rea + 1)f(n + 1)'

(2)

We also use two standard identities: p~a,(3)(

-x) =

d

_p(a,(3)(x) = dx

(_1)"p~(3,a)(x),

n+a+{3+1 2

n

and

p(a+1,(3+1)(x) n-l

(3) (4)

•

The first is easily derived from Rodrigues' formula, but the second is a little more subtle [3, (4.5.5)]. The Jacobi polynomials are discussed in detail in the standard references [1], [2], [3]. With this information we see that our conjecture implies that p~a+ I, (3) - p~a, (3) has all the zeros of !:...p(a, (3) but p(a+ I, (3) - p(a, (3) has degree nand !:...p(a, (3) has dx"'

n

dx"

II

degree n - 1. In order to compare these we must locate an additional zero of the first polynomial. From (2) and (3) we see that x = -1 is a root of p~a+l, (3) p~a, (3). Thus, in light of (4) we are led to the equivalent conjecture that for some constant k (5)

We did not find any formula like this in the literature; nevertheless, we can prove Theorem.

(6) Proof' Let

p(a+l,(3)(X) _ p(a,(3)(x) R(x)

=

n.

II

x+1

Then if m = 0, 1, ... , n - 2 we have

r

xmR(x)(1 _X)"'+I(1 +X)(3+1 dx

-1

=

r -r

Xmp~a+l,(3)(x)(1 - X)"'+I(1 + X)(3 dx

-1

(1_X)Xmp~a,(3)(x)(1-x)"'(1 +X)(3 dx

-1

=0

164

NOTES

[February

since the degree of xnl(1 - x) is m + 1, which is less than n. Thus (5) holds for • some k. That k = t follows by setting x = 1 in (5) and using (2). The theorem leads to several other relationships. For example, when (6) is applied to each term we obtain 1

k

L

Z(x + 1)

p~~tj,/3+1)(X)

j=l

k

L

=

[p'~a+j,ln(x) _p~a+j-l,~)(x)] =p~a+k,~)(x) _p'~a,~)(x).

j=l

A simple application of (6) together with (3) yields p~a,~+l)(x)

-

p~a,~)(x)

1

= Z(x -

l)p~~tl,~+l)(X).

Now let

f f( Ci + 1) -

k

Il a f( Ci)

=

\

Il~(

f( Ci )

1l:- 1f( Ci»)

if k = 1 if k > 1.

Then it is easy to obtain the following formulas:

( + l)k

Il:p~a,~)(x)

=

ll:p~a,ln(x)

=

Il~p~a,~)(x)

(-d) dx

1

"4(x 2 -

k

p(a,~)(x)

=

n

p~~tk,~+k)(X)

x 2k

(X + l)k x - 1

f( n + Ci + f3 + 1 + k) Ilk p(a,~)(x) f(n + Ci + f3 + l)(x + l)k a n

1)p~a+2,~+2)(x) = p~~il,~+l)(X)

Ilk Il j p(a, ~)( X) a ~ n

=

P~~2~+1)(X)

-

p~~il,~)(X)

+ P~~2~)(X)

( X + l)k(x - l)j p(a+k-:j, ~+k+j)( ) 2k+j n-k-} X .

We observed similar properties for the Laguerre polynomials, but we leave that exploration to the reader. The referee noted that (6) follows from a more general identity. Let (b)o = 1 and (b)n = b(b + 1) ... (b + n - 1) when n > O. The hypergeometric series is defined by

Then

2Fl(a,b + l;c;t) -2Fl(a,b;c;t)

1998]

=

(~)2Fl(a + 1,b + l;c + l;t).

NOTES

(7)

165

Formula (7) can be proved readily by subtracting the two series on the left and manipulating the result into an hypergeometric form. We recover (6) from (7) upon substituting the identity [3, (4.21.2)]

p
F (-n n + a + f3 + l'" a +2 11-X) '-(n+a) n 21'

and using the symmetry relation (3). However, with (7), the referee notes, we can also establish analogous identities for the Meixner and Krawtchouk polynomials. The Meixner polynomials are orthogonal with respect to a· discrete measure with mass [(b)x * eX]jx! at x = 0,1,2, ... where b > 0 and 0 < e < 1. They can be represented by

MIl(x; b, e)

=2F1 (

e -

1)

(8)

-n,- x; b;-e- ,

which defines them with a slightly different normalization from those defined by [2, p. 225]. The analogous formula for the Meixner polynomials is

Mn(x + 1; b, e) - Mn(x; b, e) =

n(e - 1) be Mn- 1 (x; b

+ 1, e).

The Krawtchouk polynomials are polynomials orthogonal on x = 0, 1, 2, ... , N with respect to the binomial distribution (~~x(1 p)N-x, where 0 < P < 1. We can obtain the Krawtchouk polynomials from (8) by letting b = - N and replacing (e - l)/e by lip:

-

(9) again with a different normalization from [2]. The analogous formula in this case is Kn(N, x

+ 1) - K,,(N, x) = - (nINp)K n_ 1 (N - 1, x).

These two formulas are discrete analogs of the differentiation formula for the Jacobi polynomials (4). ACKNOWLEDGMENTS. We thank Professors Alan L. Schwartz and William C. Connett for their time, advice and help. Both authors were supported by NSF grant DMS9404316. REFERENCES M. Abramovitz and 1. A. Stegun (eds.), Handbook of mathematical functions, National Bureau of Standards, Applied Mathematics Series, vol. 55, Superintendent of Documents, Washington, D.C., 1964. 2. A. Erdelyi, W. Magnus, F. Oberhettinger, and F. G. Tricomi, Higher transcendental functions, vol. 2, McGraw-Hill Book Company, New York, 1953. 3. G. Szeg6, Orthogonal polynomials, second ed., Colloquium Publications, vol. 23, Amer. Math. Soc., Providence, RI, 1967. 1.

Dept. of Mathematics and Computer Science, University of Missouri-St. Louis, St. Louis, MO University of California, Berkeley, CA 94720-0001 [email protected]

166

NOTES

[February

The Generalized Level of a Non Prime Finite Field Is Two Philippe Revoy The object of this note is to prove the theorem of the title. Recall that the quadratic level of a ring A is the smallest integer s, or 00, such that -1 = at + ... +a; has a solution with a i EA. This level, also called stufe, is an invariant used in the algebraic theory of quadratic forms [2]. Generalizing this definition, we let sr(A) be the smallest integer s such that -1 = af + ... +a;' has a solution with a i EA. Properties of the sequence sr are investigated in [3], [4], and [5]. For a finite field F, the situation is simpler: we suppose the characteristic p is different from two and F = IFq, q = pn. The group F* is cyclic of order q - 1 = 2 h m', where m' is odd: as - 1 = a(q-1)/2, sr(F) = 1 for r < h. If r ~ h, a 2r-order power in F* is just a 2 h -order power, that is exactly an odd order element of the group F*. So sr(F) = sh(F) for all r ~ h and we denote this integer by s(F) and call it the generalized level of F. This analysis shows that s(F) is the smallest integer s such that -1 = b 1 + ... + bs where bi is an element of odd order in F*. In [1], the authors prove that s(F) is two or three if q = pn, n ~ 2, and they conjecture the true value is 2. For n = 1, it is not even known if s(F) is bounded; for IFp' p a Fermat prime, s(lFp) is p - 1 and there are other p for which s(F) is bigger than 2 [1]. Theorem. s(F) = 2. The proof involves consideration of different cases: if p = 3, -1 = 1 + 1, so s(F) = 2. If p > 3 and n is even, q == 1 mod 3. Then X 3 - 1 splits completely over F, so there is an a in F* such that -1 = a + a 2 • As a and a 2 are of order 3 in F*, s(F) = 2. If n = 3, we use the fact that there is an x in F* of trace 0: x + u X + U 2 X = 0, where u: x ~ x P is the Frobenius automorphism of F. This gives -1 = XP-1 + Xp2-1. As x q- 1 = 1, the order of x p- 1 divides p2 + P + 1 and is odd; therefore s(F) = 2. Suppose now n is odd and greater than 3: q - 1 = (p - 1)m', where m' is odd. The integer 2h divides p - 1 and m' is greater than p4, so 2/z < q1/5. Consider the Fermat curve (C): X 2h + y2h + Z2 h = o. As -1 is not a 2 h -order power, this curve has no rational point over IFq with XYZ =1= O. The genus of the curve is g = (2/z - 1)(2/z - 2)/2, thus smaller than 1/2. Then the Weil inequality for (C), INc - q - 11 ::;; 2gq1/2, gives that N c , the number of rational points of Cover IFq, is at least one. This means s(lFq) = 2. Finally, note that most of these arguments are already in [1] or [5] except in the case of IFp3. The last argument, applied to IFp'" with odd n =1= 1, and r.ixt' = 0 gave the bound 3 for s(F) in [1]. Interesting results for other fields and rings are in [5].

iq

1998]

NOTES

167

REFERENCES 1. Y. Amice and B. Kahn, Sommes de puissances dans les corps finis, in !oumees Arithmetiques de Geneve (1991), Asterisque 209 (1992), 115-135. 2. T. Y. Lam, The Algebraic Theory of Quadratic Forms, Benjamin, New York, 1973. 3. J. C. Parnami, M. K. Agrawal, and A. R. Rajwade, On the fourth power stufe of a field, Rend. del Circ. Matern. di Palermo 30 (1981), 245-254. 4. J. C. Parnami, M. K. Agrawal, and A. R. Rajwade, On the fourth power stufe of p-adic completions of algebraic number fields, Rend. Sem. Mat. Univers. Politecn. Torino 44, (1) (1985),141-153. 5. Ph. Revoy, Niveaux superieurs des corps et des anneaux, C.R.Acad. Sci. Paris 207 (1988), 203-206.

PHILIPPE REVOY was a student in Ecole Normale Superieure in Paris and teaches at Montpellier University since 1967 where he is professor in Mathematics, with a Doctorat d'Etat submitted in 1975 under the guidance of professor Artibano MICALI. His research interests are Lie algebras, quadratic forms and Clifford algebras, specially those of forms of higher degrees, but also elementary number theory about which he has a few publications. Depa/1ement des Sciences Mathimatiques, Universite Montpellier II, Place Eugene Bataillon, 34095 Montpellier cedex 05, France

Cutting High-Dimensional Cakes Wolfgang Kuhn and Zuzana Kuhn Consider the problem of partitioning a cake such that each piece has a certain measure. Typically, an algorithm solving such a problem (for example, the algorithm of Banach and Knaster for fair division in [2]) uses hyperplanes to cut the cake. Continuity arguments require that these hyperplanes do not carry positive measure. In [1], Jones proves (Corollary 1) that, for dimension m = 3, the direction set of all hyperplanes of positive measure has Lebesgue measure zero on the unit sphere. However, the result holds in any dimension. Because Jones' proof cannot be extended to m > 3, we communicate an elegant proof which is even shorter than the one given in [1]. Let iL be a finite measure defined on (0 ~ R m , 93), where 93 is the Borel O"-algebra in Rm. Recall that a k-flat is a k-dimensional affine subspace of Rm. For o ::;; k ::;; m, let Ak be the set of all k-flats of iL-positive measure that do not contain any sub-flat of prpositive measure. Let sm-1 be the unit sphere in Rm. Theorem. Let iL be a finite atomless measure on (0, 93), define the direction set V = {y E sm-1: y is perpendicular to some hyperplane with iL-positilX! measure}, and let TJ be Lebesgue measure on sm-1. Then TJ(V) = O. Proof" If h is a k-flat, let h.L denote the subspace of dimension (m - k) orthogonal to h. Because each y E V belongs to h.L Ii sm -1 for some 0 ::;; k < m

and some h

E

Ak , m-l

TJ(V) ::;; TJ(Tl

U

h.L liS m -

1)

k=O hEAk

168

::;;

I: I:

TJ(h.L liS m -

1 );

(1)

k=O hEAk

NOTES

[February

we use sub-additivity and the fact that the sets Ak are countable by the theorem in [1]. For each 0;:5; k < m and h E A k , the set h 1- nS m - 1 is a (m - 1 - k)dimensional sub-manifold of sm-I, and therefore has 7]-measure zero for k > O. For k = 0, observe that JL is atomless, which implies that Ao is empty. We conclude that all terms in the sum in (1) are either zero or void, proving the assertion. • REFERENCES 1.

2.

M. L. Jones, A note on a cake cutting algorithm of Banach and Knaster, Amer. Math. Monthly 104 (1997) 353-355. H. Steinhaus, Sur la division progmatique, Econometrika (Supplement) 17 (1949) 315-319.

Konrad-Zuse-Zentrum fUr Informationstechnik Berlin, Takustrasse 7, D-14195 Berlin-Dahlem, Germany [email protected] School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332 [email protected]

Fun Things For Professors To Do on the First Day of Class Wear a hood with one eyehole. Periodically make strange gurgling noises. Deliver your lecture through a hand puppet. If a student asks you a question directly, say in a high-pitched voice, "The Professor can't hear you ... you'll have to ask me, Winky Willy." If you are asked a question, walk silently over to the student, hand him your piece of chalk, and ask, "Would YOU like to give the lecture, Mr. Smartypants?" Pick out random students, ask them questions, and time their responses with a stop watch. Record their times in your grade book while muttering "tsk, tsk." Wear mirrored sunglasses and speak only in Turkish. Ignore all questions. Ask the class to read Jenkins through Johnson in the local phone book by the next lecture. Vaguely imply that there will be a quiz. Have one of your graduate students sprinkle flower petals ahead of you as you pace back and forth. Every so often, freeze in mid-sentence and stare off into space for several minutes. After a long, awkward silence, resume your sentence and proceed normally. Announce to the students that their entire grade will be based on a single-question oral final exam. Imply that this could happen at any moment. Turn off the lights, play a tape of crickets chirping, and begin singing Peter, Paul, and Mary songs. Announce that last year's students have almost finished their class projects. Tell your students that they must do all their work in base 11. Require them to use a complicated symbol (name it after yourself) to denote the number 10.

1998]

NOTES

169

UNSOLVED PROBLEMS Edited by Richard Nowakowski

In this department the MONTHLY presents easily stated unsolved problems dealing with notions ordinarily encountered in undergraduate mathematics. Each problem should be accompanied by relevant references (if any are known to the author) and by a brief description of known partial or related results. Typescripts should be sent to Richard Nowakowski, Department of Mathematics & Statistics & Computing Science, Dalhousie University, Halifax NS, Canada B3H 3J5, [email protected]

Kempe Revisited Joan Hutchinson and Stan Wagon In 1879 A. B. Kempe gave the following method for 4-coloring any planar map [1]. A practical way of colouring any map is this. Number the districts in succession, always numbering a district which has less than six boundaries, not including those boundaries which have a district already numbered on the other side of them. When the whole map is numbered, beginning with the highest number, letter the districts in succession with four letters, a, b, c, d, rearranging the letters whenever a district has four round it, so that it may have only three, leaving one to letter the district with. When the whole map is lettered, colour the districts, using different colors for districts lettered differently.

Kempe was wrong in the sense that the coloring method he proposed-the method of Kempe chains alluded to in the phrase "rearranging the letters"-does not always work (details of Kempe's method are in the Appendix). Heawood spotted the flaw in 1890 (de la Vallee-Poussin did as well, independently, in 1896), but the labelled graph shown in Figure l(a), due to A. Errera [3] in 1921, is more

(b)

(a)

Figure 1. (a) Errera's counterexample to Kempe's proof, in the form of a labeled graph. (b). The coloring that would arise when only the top vertex remains to be colored. The red-yellow chain (thick) and the red-blue chain (dashed) force Kempe's method to attempt to eliminate green at vertices 10 and 12, which cannot be done in this case.

170

UNSOLVED PROBLEMS

[February

elegant than Heawood's example, which requires that all vertices but one be precolored. In fact, Errera's counterexample is more easily described as a spherical map: five hexagons around the equator, five pentagons in the mid-latitudes north and south, and two pentagons at the poles. Or: take a dodecahedron, split it along its equatorial zigzag, and insert five hexagons. Remarkably, this spherical structure is related to fullerene molecules.

Figure 2. Errera's 17-country counterexample is a symmetric map on the sphere.

The reader who follows Kempe's method through for the labelled graph of Figure l(a), always choosing the first vertex of degree less than or equal to five according to the labelling, will find that the order in which the vertices get colored is 17,16,15, ... ,3,2,1 and the Kempe chains get badly tangled at the last step and one cannot free up a color. Figure l(b) shows that situation when only vertex 1 remains. The red-yellow (17 to 3) and red-blue (17 to 5) chains shift attention to the green-blue chain from 10 and the green-yellow chain from 12; when vertex 9, the blue neighbor of vertex 10, is switched to green, it leads to a green-yellow chain from 12 to 3. Kempe failed to anticipate this situation, which causes his method of freeing up a color for vertex 1 to fail. But the example depends heavily on the ordering of the vertices; Kempe's method can work for some orderings and not for others. Indeed, experiments show that Kempe's method works for approximately 90% of random labellings of the Errera graph. Question 1. Does every planar graph have some vertex-labelling for which Kempe's coloring method (as in the Appendix) succeeds in 4-coloring the graph? Motivation. The idea of combining randomness with Kempe chains in the hope of producing a reliable 4-coloring algorithm has been considered by Morgenstern and Shapiro [7]; see also [6]. Here is one way to do it. Follow Kempe's instructions to the letter except that, when it comes time to remove a vertex of degree 5 or less, do so by making a random choice among the possibilities. This is equivalent to giVing the vertices a random shuffle at the very beginning. Then follow Kempe's instructions.

1998]

UNSOLVED PROBLEMS

171

This randomized algorithm works pretty well in practice. For example, our Mathematica implementation needs only a few minutes to color the 341-vertex Moore graph [9, p. 90], which is somewhat resistant to 4-coloring. A complete probabilistic analysis might be difficult, and the algorithm's asymptotic behavior might not be very good, since large graphs will likely contain several disjoint copies of the Errera graph and the probability of success for n such copies is 0.9 n • Question 1 asks only whether there can be a planar graph that, no matter how the vertices are chosen for the inductive step, foils Kempe's method. We conjecture that no such all-purpose Kempe counterexample exists. If there is a proof, it will probably use the four-color theorem, for that tells us that at least one four-coloring exists. In fact, we can show using the four-color theorem that a graph of maximum degree 5 never foils the randomized Kempe method. There is a better way to deal with the Errera example. As observed by Kittell [5] in 1935, if one switches the colors on chains defined by adjacent vertices in the ring of neighbors, one might get to a situation where Kempe's method works. Kittell uses the phrase tangent chain for a chain defined by adjacent vertices. The result of making such a switch using vertices 3 and 5 in the Errera graph is shown in Figure 3. Now the green vertex 10 has no yellow neighbors, so it can be changed to yellow, and the green vertex 12 has no blue neighbors, so it can be changed to blue. This frees up green for vertex 1 and the impasse is resolved.

Figure 3. After a Kempe interchange is performed on the yellow-blue chain starting from vertex 3 (see Figure 1) the resulting graph, shown here, has a simplified structure. A green-yellow interchange based at vertex 10 can be made, as well as a green-blue interchange based at 12, freeing up green.

The potential resolution offered by tangent chains leads to the following algorithm, which we call KK for Kempe-Kittell. It has been implemented by Morgenstern and Shapiro [7] in slightly different form; their tests of graphs having up to 512,000 vertices yielded no failures or restarts. Algorithm KK has no problem on any number of disjoint copies of the Errera graph, and so is superior to the randomized Kempe algorithm mentioned earlier. Algorithm KK

1. Start with a labelled planar graph. 2. Let v be the first vertex of degree 5 or less; delete it and color the rest by induction.

172

UNSOLVED PROBLEMS

[February

3. Try to use Kempe's method of color-interchanges to free up a color for v. 4. If Kempe's chains get tangled in step 3, make random Kempe-interchanges until the impasse is resolved. Precisely, choose w, a neighbor of v, at random and then choose a color different from w's with which to make an interchange on a chain from w. If this fails to free up a color, keep the new coloring, again choose a random neighbor w of v and a random color different from w's, and make another color-switch on a chain from w. Continue until the impasse is resolved. If this fails to work within, say, 100 switches, start over at step 1 with a random labelling of the vertices. Question 2. Does algorithm KK always succeed?

In essence this question was posed by Kittell, who asked whether any planar graph could be colored by an inductive method that used the first available color and used some sequence of Kempe color-changes if no color was available. Of course, he knew that an existence proof for such a sequence would yield the 4-color theorem. We now know that the 4-color theorem is true (see [8]). Can we prove that for any planar graph there is an appropriate, even if hard-to-find, sequence of Kempe color switches that 4-colors the graph? An affirmative answer to either question could be viewed as partial vindication for Kempe, for it would show that an algorithm using almost nothing that is not in Kempe's proof can 4-color any planar graph. APPENDIX: DETAILS OF KEMPE'S METHOD. Assume a labeled planar graph is given. We use R, G, B, Y for red, green, blue, and yellow. Removal of vertices. Euler's formula implies that every planar graph has a vertex of degree 5 or less. Choose the first such vertex and remove it. Then, in the planar graph that remains, choose the first vertex of degree 5 or less, and remove it. Continue until only one vertex is left. Color it red. Then add the next vertex back in and color it according to the following rules. Adding vertices back and coloring. If a vertex v is to be added back and its neighbors in the already-colored part of the graph consume three or fewer colors, there is no problem. Give v the first available color. A difficulty arises if v's neighbors (there are at most 5 of them) use all 4 colors. In that case, try to eliminate a color by a Kempe chain. Suppose the colors on the neighbors, in circular order, are R, G, B, Y, G (if there are four neighbors, follow an essentially identical strategy). Start with red, letting u be the vertex so colored. Let w be the neighbor of v. colored blue. Look at the connected component of u among all vertices colored R or B. If w is not in this component, switch all Rs and Bs on the component, thus freeing up R for use on v. If, on the other hand, the target w does show up on the chain, then try to make a color-switch using the pair R-y' If that fails, try to eliminate green by chaining from the first green to yellow and then from the other green to blue. Kempe's quite-believable topological argument shows that the Kempe chain method will always succeed in eliminating a color. But the argument is wrong. See [2], [4], [9] or Kempe's paper in [1] for more details. ACKNOWLEDGMENTS. We are grateful to Frank Bernhart for the information that the explicit counterexample is due to Errera and to Dan Sanders for valuable help with references. The Errera graph is pretty and is more informative than Heawood's construction; we think it should be used whenever one is trying to illustrate Kempe's oversight.

1998]

UNSOLVED PROBLEMS

173

REFERENCES 1. 2. 3. 4. 5. 6. 7. 8. 9.

N. L. Biggs, E. K Lloyd, and R. J. Wilson, Graph Theory, 1736-1936, Oxford Univ. Press, Oxford, 1976. E. B. Burger and F. Morgan, Fermat's last theorem, the four color conjecture, and Bill Clinton for April Fools' Day, this MONlliLY 104 (1997) 246-255. A. Errera, Du Colorage des Cartes et de Quelques Questions d'Anaysis Situs, Thesis, GauthierVillars, Paris, 1921, 66 pp. J. P. Hutchinson and S. Wagon, The four-color theorem, Mathematica in Education and Research 6:1 (1997) 42-51. I. Kittell, A group of operations on a partially colored map, Bull. Amer. Math. Soc. 41 (1935) 407-413. D. W. Matula, G. Marble, and J. D. Isaacson, Graph coloring algorithms, in: Graph Theory and Computing (R. C. Read, ed.), Academic Press, New York, 1972, pp. 109-122. C. A. Morgenstern and H. D. Shapiro, Heuristics for rapidly four-coloring planar graphs, Algorithmica 6 (1991) 869-891. N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas, A new proof of the four-colour theorem, Electron Res. Announcements, Amer. Math. Soc. 2 (1996) 17-25 T. L. Saaty and P. C. Kainen, The Four Color Problem, McGraw-Hill, New York, 1977.

Macalester College, St. Paul, MN 55105 [email protected]; [email protected]

174

UNSOLVED PROBLEMS

[February

PROBLEMS AND SOLUTIONS Edited by Gerald A. Edgar, Daniel H. Ullman, and Douglas B. West with the collaboration of Paul T. Bateman, Duane M. Broline, Ezra A. Brown, Richard T. Bumby, Glenn G. Chappell, Randall Dougherty, Ira M. Gessel, Bart Goddard, Jerrold R. Griggs, Douglas A. Hensley, Richard Holzsager, John R. Isbell, Robert Israel, Murray S. Klamkin, Daniel J. Kleitman, Fred Kochman, Frederick W. Luttmann, Frank B. Miles, Richard Pfiefer, Leonard Smiley, John Henry Steelman, Kenneth Stolarsky, Richard Stong, Charles Vanden Eynden, and William E. Watkins.

Proposed problems and solutions should be sent in duplicate to the MONTHLY problems address on the inside front cover. Submitted problems should include solutions and relevant references. Submitted solutions should arrive at that address before July 31, 1998; Additional information, such as generalizations and references, is welcome. The problem number and the solver's name and address should appear on each solution. An acknowledgement will be sent only if a mailing label is provided. An asterisk (*) after the number of a problem or a part of a problem indicates that no solution is currently available.

PROBLEMS 10641. Proposed by Jerrold R. Griggs, University of South Carolina, Columbia, Sc. Determine all pairs m, n of positive integers such that an m-by-n rectangle can be tiled by congruent pieces shaped like 8:J, fonned by removing a I-by-l square from one corner of a 2-by-2 square. 10642. Proposed by David M. Bradley, Dalhousie University, Halifax, NS, Canada. (a) Suppose ao, a I, a2, ... is a sequence of nonnegative real numbers with ao = 1 satisfying, for a given constant c > 1, L~n ak ::: can for every n :::: O. For each n :::: I, find the largest possible value of an in terms of c. (b) Suppose f: [0, (0) -+ [0, (0) is a nonnegative, nonincreasing function with f(O) = 1 f(t)dt ::: f(x) for every x :::: O. For each x > 0, find the largest possible satisfying value of f(x).

ixoo

10643. Proposed by David Callan, University of Wisconsin, Madison, WI. Let Dn = n! 'LJ=o( -1)j Ii! denote the nth derangement number, the number of permutations on n letters without fixed points. Show that for nonnegative integers nand k, min{n.k} (k) (k + n k (k) L . Dk+n-j = k! L · k j=O } j=O }

i)

Dn-j.

10644. Proposed by Mihaly Bencze, Brasov, Romania. Given an acute triangle with sides of length a, b, and c, inradius r, and circumradius R, prove that r abc -- < -r~~~==~~~~==~ 2R - J2(a 2 + b 2)(b 2 + c 2)(c 2 + a2)

10645. Proposed by J. Gross, G. Trenkler, and S.-O. Troschke, University of Dortmund, Germany. Let k > 2 be an integer. Characterize the n-by-n complex matrices A such that Ak

= AA*.

1998]

PROBLEMS AND SOLUTIONS

175

10646. Proposed by Hassan Ali Shah Ali, Tehran, Iran. Find the maximum of n?=1 (1 - Xi) over all nonnegative XI, X2, ..• , Xn with L:?=I = l.

xl

10647. Proposed by S.c. Locke, Florida Atlantic University, Boca Raton, FL. Let G be a connected simple graph, and let I(G) be the minimum value of d(u) + d(v) + d(u, v) over distinct vertices u, v E V(G), where d(u) is the degree of vertex u and d(u, v) is the distance from u to v. (a) Suppose G is a connected simple graph and I (G) 2:- 6. Prove that G contains a connected 3-vertex subgraph X such that G - VeX) is connected. (b) For each k 2: 3, construct a connected simple graph G with I(G) 2: 2k - I, but with no connected k-vertex subgraph X such that G - VeX) is connected. (c)* Suppose G is a connected simple graph and I(G) 2: 2k, where k > 3. Must G contain a connected k-vertex subgraph X such that G - VeX) is connected? (d)* Suppose G is a connected simple graph and I(G) 2: 2k, where k > 3. Must G contain a k-vertex path P such that G - V(P) is connected?

SOLUTIONS A Symmetric Sum 10407 [1994, 793]. Proposed by Roy Mathias, College 01 William & Mary, Williamsburg, VA. Let AI, ... , An+ I and IL I, ... , ILn be 2n + 1 given real numbers such that AI :::: IL I .:::: A2 :::: IL2 :::: ... :::: An :::: ILn :::: An+1 and IL I < IL2 < ... < ILn. Show that n

n{Ai-ILj:i=I, ... ,(n+I)}

L j=1 n {ILi -

. ILj : = I

.. = 1, ... ,n, i= J } I

1 ((n+1

2:

n)2

L Ai - L ILi i=l i=l

n

+L

;=1

ILr -

n+l) Ar .

L i=l

In particular, deduce that n

f;

n{2(i -

j) - 1 : i

n {2(i -

=

1, ... , (n

j) : i = I, ... , n, i

+ 1) }

i=

j }

n(n + 1) =---2

Solution I by lean-Pierre Grivaux, Lycee Chap tal, Paris, France. The first equation is true without any restriction on the numbers Ai. The proof is by induction on n. The case n = 1 may be taken as the basis of the induction by interpreting the empty product in the denominator on the left side of the desired equation to be 1. For n 2: 2, consider each side of the desired equation as a function of X = AI. Let cJ> (x) be the expression on the left side, and let III (x) be the expression on the right. It is clear that both cJ> (x) and III (x) are affine functions, so it suffices to show that they are equal if x = /1, I or if x = J.L2. If x = J.L I, the term in cJ> (J.L I) with j = 1 is zero and the remaining terms give a sum of the same type omitting Al and J.LI. On the other side, the terms involving J.LI in III(J.LI) cancel, leaving an expression of the same type omitting AI and J.L I. The inductive hypothesis then gives cJ>(J.Ld = 1II(J.Ll). The same holds when x = J.L2, except that now it is Al and J.L2 that are omitted when cJ>(J.l2) and 1II(J.l2) are simplified, so cJ>(J.L2) = 1II(J.L2). Thus cJ>(Al) = III(Ad. Solution II by the proposer. We use methods of matrix analysis and refer to R. A. Horn and c,R. Johnson, Matrix Analysis, Cambridge, 1985, indicated by [HJ]. The inequalities on Ai and J.Lj assure that all terms on the left are negative. Let .----,------------{Ai - J.Lj : i = 1, ... , (n + 1)}

-n n {J.Li -

176

J.Lj : i = 1, ... , n, i

PROBLEMS AND SOLUTIONS

i= j} [February

Then all aj are real. Let D

=

diag({L I, {L2, ... , {Ln) be the n-by-n diagonal matrix whose

entries are the {L), and leta be the column vector with entries aj . Let u and let

=

r:.?::i Ai - r:.?=1 {Li

Then the eigenvalues of fj are AI, A2, ... , An+1 [HJ, Theorem 4.3.10]. Now, if X is an m-by-m real symmetric matrix with eigenvalues Ai, then r:.r=1

Al

r:.rj=1 IXij 12 [HJ, Theorem 2.S.4(c)]. Applying this to fj gives

n+1

n

n

I>l = Ldii = L{LJ + u 2 + La]' i=1 i,j j=1 j=1

Rearranging these terms gives the desired result. Solution III by Robin 1. Chapman, University of Exeter, Exeter, U. K. The inequalities in the problem statement are superfluous; all that is needed is that {LI, ... , {Ln are distinct.

Let f(X) = nj~f (X - Aj) and g(X) = n7=1 (X - {Lj). The partial fraction expansion of f(X)/g(X) is f( X)

n

(t.

--=X+a+"--.lg(X) X - A)

.f;;!

for some a, where n{{Lj - Ai : i (t. -

=

+ I)}

1, ... , (n

~--~-----------------

] - nUL)

-{Li: i = 1, ... ,n,i #j}

For large X we can expand as a power series in 1/ X and get f(X) = X +a g(X)

+

(t

f({Lj») X-I j=1 g'({Lj)

+

O(X- 2).

Hence the left hand side of the desired identity is the coefficient of X-I in (*). Let s) and t) denote the j -th elementary symmetric functions of AI, ... , An+ I and of {L I, ... , {Ln, respectively, Then f(X) Xn+1 - SIX n + S2xn-1 - .. . g(X) = xn - tlxn-l

=

X

+ (tl

- s[)

+

f2xn-2 - .. .

+ (S2 -

t2

+ fl(tl

- SI»X- 1 + O(X- 2),

and so the left hand side of the desired identity is S2 - t2

+ t~ -

Sltl = L AiAj - L {Li{L) i<j i<)

+L

{L}

)

+2L i<j

{Li/-L,j - L Ai{L) i.j

Solution IV by Mourad E. H. Ismail, University of South Florida, Tampa, FL. This identity is a special case of Corollary 8.8 of R. W. Gosper, M. E. H. Ismail, and R. Zhang, On some strange summation formulas, Illinois 1. Math 37 (1993) 240-277. In formula 8.9, replace x by z + An+ I and for k = 1, ... , n replace bk by {Lk and ak by {Lk - Ak. The result then follows by expanding both sides of formula 8.9 in powers of z-I and equating the coefficients of C 2 . Further identities may be obtained from the other coefficients, Solved also by J. C. Binz (Switzerland), D. Callan, S. Ehrich (Germany), G. Keselman, J. H. Lindsey II, O. P. Lossers (The Netherlands), A Nijenhuis, A. Pedersen (Denmark), C. Popescu (Belgium), R. Stong, Y. Yang, and NSA Problems Group.

1998]

PROBLEMS AND SOLUTIONS

177

One-quarter Isoperimetric

10422 [1994, 1014]. Proposed by Adam Fieldsteel, Wesleyan University, Middletown, CT. Let f : [0, 1] ~ JR be a C 1 strictly increasing function with f(1) = L, where L is the length of the graph of f. (a) Show that 1 f(x)dx ~ 7r/4.

10 (b) Show that 101 f (x) dx = 7r /4 only if the graph of f

is a quarter circle.

Solution I by A. Meir, York University, North York, Ontario, Canada. We assume that f is a C 1 function but do not require that it be increasing. Integration by parts yields

Id f(x) dx = f(1) - Id Xf'(X) dx. Since f(1) = L = 101 J1 + (f1(x))2 dx, we obtain 10 1 f(x)dx = 10 1 (~-xZ)dx,

where

z=

(1)

f'ex).

For any a, bE JR+, a ~ 0, then

(../b - Ja)2

= (b - 1)(1 - a)

+ (1 - v'ab( Hence, if b ~ 1 ~ (2)

with equality only if ab = 1. Setting b = 1 + Z2 and a = 1 - x 2 in (2), we get

~-~~XZ, with equality only if (1 + z2)(l Equations (1) and (3) imply

10t

x 2) =.1, that is, if z =

f(x)dx

(3)

x/~.

~ t ~dx =~,

10

(4)

4

with equality only if z = f'ex) = x / ~ for all x

E

[0, 1]. Equation (4) demonstrates

(a), and the condition for equality integrates to f(x) = C -~, that is, the graph of y = f(x) is a quarter circle. This gives (b). Furthermore, since f(1) = L, we must have C = 7r/2. Solution II of (a) by Kenneth Schilling, University of Michigan, Flint, MI. We show that for any increasing function f: [0, 1] ~ JR,lol f(x) dx+L - f(1) ~ 7r /4, where L is the length of the graph of f. (Since all increasing functions are integrable and have rectifiable graphs, differentiability need not be assumed. In fact, we need not even assume continuity, provided that we understand L to be defined as the limit of lengths of polygonal approximations. By this definition, a jump discontinuity in f of height h contributes h to the value of L.) We bound the integral by its lower Riemann sum for a partition into n equal pieces, and we bound the arc length by the length of an inscribed polygon determined by the same partition. For readability, let ak = f(k/n) for k = 0,1, ... , n. Then

t

10

f(x)dx

+

L - f(1)

~t

k=l

=

(a kn

I

+V

I(ak - ak_I)2

t (V

I(ak - ak_d 2 +

k=1

°

+~) n

~ - ~(ak n n

-

an

ak-d).

(*)

Now, for fixed r > and s E (0, 1), consider g(x) = J x 2 + r2 - sx, defined for x > 0. The usual methods of calculus show that g takes its minimum at x = r s / ~, and that this minimum value is r~. Applying this result to each summand in (*) (taking 178

PROBLEMS AND SOLUTIONS

[February

x = ak-ak-I, r = l/n ands = k/n) bounds the sum in (*) below by L~=I

As n --+

00,

this sum converges to

Jol

v'1="X2 dx =

1T /4,

~J1

-

(k/n)2.

completing the proof of (a).

Editorial comment. Other solutions either transformed the problem into the standard isoperimetric problem or used methods of the calculus of variations to construct an Euler-Lagrange differential equation characterizing the minimizing function. Several readers noted that the function identified in (b) as giving the extreme value is not itself C I on [0, 1], since I' (x) is unbounded as x --+ 1. However, the graph y = I (x) does have an infinitely differentiable parameterization, and the minimum is unique among such functions. The selected solutions show that (a) holds with weaker hypotheses. Guaranteeing a strict inequality with weaker hypotheses appears to be more delicate. However, it suffices to show that, if y = I (x) is not the graph of a quarter circle, then there is a function g to

which one of the solutions of (a) applies with

Jd I (x) dx > Jd g(x) dx.

Solved also by R. J. Chapman (U. K.), D. A. Darling. J. H. Lindsey II, A. Pechtl (Germany), P. D. Scofield, A. A. Tarabay (Lebanon), N. S. Thornber, D. Velleman, A. Witkowski (Poland), NSA Problems Group, and the proposer.

Projections Summing to Zero 10471 [1995, 655]. Proposed by Stephen Semmes & Richard Stong, Rice University, Houston, TX. Suppose V is a (possibly infinite-dimensional) vector space over C and PI, P2, ... , Pn are projections on V. For which n is it the case that if PI + P2 + ... + Pn = 0, then all the Pi are zero? Solution by Richard Holzsager, American University, Washington, DC. The result holds for n :s 3. Suppose A, B, C are projections with A + B + C = O. Let u be in the range of A, so that Au = u. Let v = Bu, so Bv = v. We have Cu = -Au - Bu = -u - v, from which it follows that C(u + v) = u + v, so Cv = 2(u + v). It now follows that Av = -Bv - Cv = -2u - 3v. Since A2 = A, we have -2u - 3v = -2Au - 3Av = -2u + 6u + 9v. Thus u = -2v. This implies that Bu = -u/2. Since B is a projection, u must be O. Since u was an arbitrary member of the range of A, A must be 0, and similarly for Band C. For n = 4, the following infinite matrices provide a counterexample:

$[-; -;] $[-~ -~ ]$... , $[=; ;] $[=~ ~ ]$... , [-~ -~] $[-! -!] $[-~ -~] $''',

PI = [ 1 ] P2 = [ 1 ]

P3 =

P4=[=~ ~]$[=! !]$[=~ ~]$"" The 2-by-2 direct summands are projections, because they have determinant 0 and trace 1. From these, one easily obtains counterexamples for n > 4. Finally, all such examples must be infinite-dimensional. In a finite-dimensional space, the trace of a projection is its rank, and the trace is additive, so any sum of projections has positive trace. Editorial comment. Pei Yuan Wu observed that the complete solution appears in H. Bart, T. Ehrhardt, and B. Silbermann, Zero sums of idempotents in Banach algebras, Int. Eqs. Oper. Theory 19 (1994) 125-134. Solved also by P. Y. Wu (China) and by the proposers.

1998]

PROBLEMS AND SOLUTIONS

179

Residues Modulo a Gaussian Integer

10497 [1996, 75]. Proposed by Klaus Huber, Darmstadt, Germany. The Gaussian integers are those complex numbers x + i Y for which x and y are integers. Given a complex number z, let [z] denote the closest Gaussian integer to z, let z* denote the complex conjugate of z, and let N(z) = zz*. It is known that, if p is a rational prime with p == 1 (mod 4), then p = a 2 + b 2 for integers a and b in an essentially unique way, and hence p = T(7r* for rr a Gaussian integer in an essentially unique way. Reduction modulo rr is defined by y mod rr = y - [yrr* /rrrr*] rr. A reduced set of residues {ai : i = 1, ... , p - 1} modulo the Gaussian integer rr .can be defined by choosing g to be a primitive root modulo p and setting ai

= gi mod rr. Show that Lf':-/ N(ai) =

(p2 - 1)/6.

Solution by Lorraine L. Foster, Northridge, CA. Write rr = a + bi, where a and bare (ordinary) integers. Since p is odd, we can choose integers Uj, Vj, rj, and Sj such that gja = pUj + rj, gjb = pVj + Sj, Irjl < p/2, and ISjl < p/2. Since g is a primitive root "lodulo p and a is relatively prime to p, we conclude that the integers gj a are incongruent and nonzero modulo p (for 1 ::::: j ::::: p - 1). Thus {rl' r2, ... , rp-d =

{-S!, ... , -2, -1, 1,2, ... , S!}, and p-l

j=1

Similarly

LJ,:-/ s} =

k=1

1)

(2

(p-l)/2

L r} = 2 L

k2 = P P 12

.

p(p2 - 1)/12. Define y'j = "j - vji. Since the real and imaginary

parts of gj /rr - Yj = (rj - sji)/ p are both less than 1/2 in absolute value, we conclude that Yj is the closest Gaussian integer to gj /rr. Also,

Hence p-l

LN(aj) j=1

1 (P-l P-I) Lr}+ LsJ P j=1 j=1

=-

1

2

=~. 6

Solved also by R. 1. Chapman (U. K.), R. Holzsager. A. N. 't Woord (The Netherlands), GCHQ Problems Group (U. K.). USA Problems Group, and the proposer.

Sums of Four Nonindependent Squares

t.

10503 [1996, 172]. Proposed by Dragomir .f)okovic, University of Waterloo, Waterloo, Ontario, Canada. Show that {x 2 + (x + 1)2 + y2 + Z2: x, y, Z E Z} is the set of positive integers not divisible by 4. Solution by J. Merzel, Holy Names College, Oakland, CA. Since all terms are squared, the desired set S contains only positive integers. Since x 2 + (x + 1)2 == I mod 4 and y2 + Z2 ¥= 3 mod 4, S contains no multiple of 4. If n is a positive integer not divisible by 4, then 2n - 1 is a positive odd integer not congruent to 7 modulo 8. By the three-squares theorem (Theorem I of Chapter 20 in L. J. Mordell, Diophantine Equations, Academic Press, 1969), we can write 2n - I = a 2 + b 2 + c 2 for integers a, b, c. We may take a to be odd, which forces band c to have the same parity. Now n = x 2 + (x + 1)2 + y2 + Z2 with x = (a - 1)/2, Y = (b - c)/2, and z = (b + c)/2. Editorial comment. Lorraine L. Foster located the result in L. E. Dickson's History of the Theory of Numbers, Volume 2, Carnegie Institution, 1919. The result is attributed to Euler

180

PROBLEMS AND SOLUTIONS

[February

for even integers (p. 278) and to Pollock for odd integers (p. 291). Andrew Adler and James T. Lewis observed independently that the solution for odd integers appears in A. Adler and 1. Coury, The Theory of Numbers: A Text and Source Book of Problems, Jones and Bartlett, 1995, p. 259, problem 8-88. Solved also by A. Adler (Canada), B. D. Beasley, J. T. Bruening, R. J. Chapman (U. K.), D. R. Estes, J.-C. Evard, L. L. Foster, T. Hagedorn, R. Holzsager, M. S. Klamkin (Canada), N. Komanda, 1. T. Lewis, A. Pedersen (Denmark), A. Stadler (Switzerland), R. Stong, T. V. Trif, R. B. Tucker, C. Vanden Eynden, M. Vowe, P. G. Walsh (Canada), K. Williams (Canada), A. N. 't Woord (The Netherlands), USA Problems Group, GCHQ Problems Group (U. K.), and the proposer.

Another P61ya Urn Scheme 10504 [1996, 172]. Proposed by Richard Hamming, Naval Postgraduate School, Monterey, CA, and Roger Pinkham, Stevens Institute of Technology, Hoboken, NJ. An urn contains a amber beads and b black beads with a and b both greater than zero. A bead is selected at random. If it is black, sampling stops; otherwise, it is replaced, an additional amber bead is added, and the process is repeated. Let N be the number of steps until the process stops. (a) Show that E(N) is finite if b > 1 and find its value. (b) Show that E(N) is infinite if b = 1. (c) If n trials with b 1 are performed, and Nl, N2, ... , N n are the numbers of steps to completion in these trials, and N is their average, show that

=

asn

~

00.

Solution by Richard Stong, University of California-San Diego, La Jolla, CA. (a) If b > 1, then E(N) = (a + b - l)/(b - 1). Since (a + i - l)/(a + b + i - l) is the probability that the ith step does not stop the process, we have Prob{N > k} = k . (a+k-l)! (a+b-l)! W h'IC h ten d s to zero i=1 ( a + I. - 1)/(a + b +.I - 1) • Th e pro d uct IS (a-I)! (a+b+k-I)!'

n

faster than l/k,andthuskProb{N > k} ~ O. In this setting,E(N) = L~oProb{N > k}. . (a+k-I)! I ( (a+k-I)! (a+k)!) . . By usmg (a+b+k-I)! = b-I (a+b+k-2)! - (a+b+k-I)! ,we convert thIS to a telescopmg sum and obtain (a+k-l)!(a+b-l)! L = k=o(a-l)!(a+b+k-l)! oo

E(N) =

(a+b-l)!(a-l)!

a+b-l = ----:--(b-l)(a-I)!(a+b-2)! b-l

. lds Pro b{N > k} = (a-I)! (a+k-I)!a! a an d (b) Wh en b = I , the same argumen t Yle (a+k)! = a+k' hence E(N) ~ L~o a/(a + k). This sum is the tail of a harmonic series, and thus E(N) is infinite. (c) This statement is false. We prove instead that Prob { (N / In n) - a > E} ~ O.

I

Given an integer M, let N+ Prob{N> M} = a/(a

+ M).

= min(N, M).

I

As computed in (b), Prob{N+

=f.

N} =

Similarly, let Nt = min(Ni' M), and let N+ be the average

-+-+of these values. Since N =f. N requires some Ni to exceed M, we have Prob{N =f. N} :::; na/(a

+ M).

If M is much larger than an, we may work with N+ instead of N. Note that

E(N+)

= E(N+) = L

M-I

00

k=O

1998]

Prob{N+ > k}

=L

_a_ k=O a + k

PROBLEMS AND SOLUTIONS

= a In(M/a) + 0(1), 181

and 00

n Var(N+)

= Var(N+)

< E«N+)2)

= L(2k + l)Prob{N+

> k}

k=O

+ 1) a +k

M-I a(2k = L k=O

M-I a(2k + 2a) < L =2aM. k=O a +k

-+

-+

NowletM = LanlnnJ,sothatE(N lInn) =a+O(lnlnnllnn)andVar(N lInn) = O((lnn)-I). Chebyshev's inequality ensures that Prob

N - a 1> I < 11 --+ Inn

Var(N -+ lInn)

+

E

Since Prob{N+ =f:. N}:::: nal(a Prob

I

= O((lnn)- ).

(E-IE(N Ilnn)-aI)2

+ LanlnnJ) =

III:n -

al >

E

O((lnn)-I), we get

I: :

O((ln n)-I).

Solved also by A. Adler, R. A. Agnew, D. A. Darling, M. N. Deshpande (India), P. Griffin, R. A. Groenveld, J. Haigh (U. K.), V. Hernandez (Spain), E. Hertz, R. Holzsager, P. B. Humphrey, J. H. Lindsey II, L. E. Mattics, T. V. Trif (Romania), P. Trojovsky (Czech Republic), M. Vowe (Switzerland), J. T. Ward, GCHQ Problems Group (U. K.), and the proposers.

A Circular Locus for the Centroid 10542 [1996, 600]. Proposed by Jean Anglesio, Garches, France. Let e be the circumcircle of a triangle AoBoCo and let ~ be the incircle. It is known that, for each point A on e, there is a triangle ABC having e for circumcircle and ~ for incircle. Show that the locus of the centroid G of triangle ABC is a circle that is traversed three times by G as A traverses e once, and determine the center and radius of this circle. Solution by Albert Nijenhuis, Seattle, WA. Let M and I be the centers of e and~, respectively, and let Rand r be their respective radii. Given ABC, let N be its nine-point (Feuerbach) circle, with center N = N(ABC). The circles N and ~ are internally tangent, and when the triangle is isosceles, their point of tangency is at the midpoint of the base. The points N, G, and M are collinear with G between N and M and with NG: GM = 1: 2. We consider first the locus of N and show that it is a circle. Since J is fixed, and N is tangent to ~ with radius R12, it follows that the locus must lie on the circle £.- with center I and radius RI2 - r. We show next that every point of £.- is in the locus of N. The points where £.- intersects the line 1M are the nine-point centers of the two isosceles triangles whose bases are perpendicular to 1M. (No other triangles ABC have either of these nine-point centers, since in such a triangle the points M, I and the orthocenter would be collinear, which implies the triangle would be isosceles, with base perpendicular to the line MI.) Let these triangles be AIBICI and A2B2C2, with AI, A2, BI, B2, CJ, C2 in circular order. As a variable triangle ABC "rotates" from position AIBICI to A2B2C2, with A moving along the short arc AIA2, the point N(ABC) moves from N(AIBICI) to N(A2B2C2) along one half of £.-, while a similar "rotation" from position Al BI CI to C2A2B2 would, by symmetry, produce the other half of £.-. From this it follows that every point of £.- is in the locus of N, and that the mapping from e to £.- has degree ±3. The locus of G is the circle obtained from £.- by a contraction toward M with factor 2/3. Its center lies between M and I, at distance (2/3)M I from M. Its radius is 213 that of £.-, that is (R - 2r)/3. Editorial comment. Clark Kimberling found a reference in Gallatly's 1913 book The Modern Geometry of the Triangle. On pages 19-20, there is a proof that the locus of G is a circle,

182

PROBLEMS AND SOLUTIONS

[February

but not that it is traversed three times. This is in a whole chapter on "Poristic Triangles," in which circular loci are established for 6 centers, including the Nagel and Gergonne points. Solved also by J. E. Dawson (Australia), 1. H. Lindsey II, B. Mirman, R. Tauraso (Italy), and the proposer.

No Other Critical Point 10551 [1996, 808]. Proposed by Raphael M. Robinson, University of California, Berkeley, CA. Suppose that f (x, y) is continuous and nonnegative for x 2 + y2 :s 1, that fx (x, y) and fv(x, y) are continuous for x 2 + y2 < 1, and that f(O, 0) = f(1, 0) = O. Must there be a p~int (x, y) with 0 < x 2 + y2 < 1 where fAx, y) = fv(x, y) = O? Solution by Albert Nijenhuis, Seattle, WA. No. Let f(x, y) = (y+9x(l-x»)2 +x 2(l-x). Denote D = {(x, y) I x 2 + y2 :s 1}. Obviously, f(x, y) :::: 0 in D. Since both terms are nonnegative in D, both must vanish for f(x, y) to vanish. This takes place at (0,0) and (1, 0) but at no other points of D. The partial derivatives of f are It (x, y) = 2(y + 9x (1 x) )(9 - 18x) + 2x - 3x 2 and fv(x, y) = 2(y + 9x(1 - x»). For both of these to vanish we must have y + 9x(1 - x) = 0 and 2x - 3x 2 = O. The only solutions are (0,0) and (2/3, -2), but the latter point does not belong to D. Solved also by G. G. Chappell, T. Goebeler & T. Williams, S. S. Kim (Korea), J. H. Lindsey II, R. Martin (Germany), C. G. Petalas & T. P. Vidal is (Greece), R. Reynolds, A. N. 't Woord (The Netherlands), GCHQ Problems Group (U. K.), and the proposer.

Beke's Functional Equation 10559 [1996, 903]. Proposed by Michael Golomb, Purdue University, West Lafayette, IN. Determine the class U of real-valued differentiable functions that satisfy the functional equation u(2x) = 2u(x)u'(x) for all real x and that are real analytic near x = O. Solution by Denis Constales, University of Ghent, Ghent, Belgium. The solutions are u (x) = 0, u(x) = x, and the three families u(x) = exp(ax)/(2a) (for a =1= 0), u(x) = sin(ax)/a (for a > 0), and u(x) = sinh(ax)/a (for a > 0). Writing u(x) = Co + ctX + C2x2 + ... and taking derivatives of both sides of u(2x) = 2u (x )u' (x) leads to the following equations in the coefficients Ck: (1)

Co = 2ClCO, 2ct = 4COC2 + 2ci '

(2)

+ 6ct C2 , 8c0C4 + 8ct C3 + 4c~ ,

4C2 = 6COC3

(3)

8C3 =

(4)

and, for general k > 1, since the right-hand side is (d/dx)(u(x)2), k

2 k- lck_l = k

L CmCk-m,

k = 1,2, ....

(5)

m=O

=

Case 1. If Co =1= 0, then (1) implies that Cl 1/2, (2) determines C2, etc., and by induction (5) determines Cko hence there is at most one solution with given Co =1= o. It is straightforward to verify that for any real a =1= 0, u(x) = exp(ax)/(2a) is a solution and that co = 1/(2a) for it; varying a =1= 0 produces all possible non-zero Co values. Case 2. If Co = 0, then (1) holds trivially and (2) leads to ct = 0 or ct = 1. If Cl = 0, then (3) implies C2 = 0, and by induction (5) implies Ck-l = O. Hence we obtain u(x) = 0, which is a solution of the equation. Finally, if Cl = 1, then (3) implies C2 = 0 and (4) holds trivially. For k :::: 5, Ck is multiplied by zero in (5) and hence does not occur; the coefficients of Ck-l in (5) are 2k - 1 on the left-hand side and 2k on the right-hand side. These coefficients are different, so (5) determines Ck-l uniquely (given a choice of C3). For a > 0, sin(ax)/a, 1998]

PROBLEMS AND SOLUTIONS

183

sinh(ax)/a, and x are solutions with Co = 0, CI = 1 and C3 given by -a 2/6, a 2/6, and 0, respectively. All choices of C3 can be obtained this way, so these are the only solutions. Editorial comment. Joseph Wiener pointed out that the solution appears in two papers: E. Beke, Uber eine Funktional-Differentialgleichung, Mat. Fiz. Lapok 48 (1941) 387-392; and J. Wiener, On the analytic solutions of Beke's functional equation, Ucen. Zapiski Ryazan Gos. Pedagog. Inst. 102 (1971) 15-17. Solved also by K. F. Andersen (Canada), D. Bialostocki & G. Bialostocki, D. Callan, P. R. Chernoff, D. A. Darling. T. Jager, D. Laugwitz (Germany), J. H. Lindsey II, J. H. van Lint (Netherlands), A. Nijenhuis, E. C. Schlesinger, S. Sertiiz (Turkey), 1. H. Steelman, P. Szeptycki, J. Wiener, Ancorage Math Solutions Group, GCHQ Problems Group (U. K.), KFUPM Problems Group (Saudi Arabia), NCCU Problems Group, WMC Problems Group, and the proposer.

Ordered Affine Geometry 10560 [1996, 903]. Proposed by Emre Alkan, Bosphorus University, Istanbul, Turkey. Consider a convex quadrilateral ABCD, and choose points P, Q, R, and S on sides AB, BC, CD, and DA, respectively, with IPAI = IPBI

IRDI and IQBI = ISAI. IRCI IQCI ISDI

Let K denote the area of ABC D, and let KA, KB, Ke, and KD denote the areas of SAP, PBQ, QCR, and RDS, respectively. Show that K4 ~ 212KAKBKeKD' and determine a necessary and sufficient condition for equality.

Composite solution by Walther Janous, Ursulinengymnasium, Innsbruck, Austria; Murray S. Klamkin, University of Alberta, Edmonton, Alberta; Victor Pambuccian, Arizona State University West, Phoenix, AZ; and Florin Postelnicu, Tempe, AZ. The property involves only ratios of lengths of collinear segments and ratios of areas of coplanar triangles and quadrangles; it belongs therefore to affine geometry. Also, the statement remains valid if the two given ratio constraints are left out. Let P, Q, R, S divide the respective sides AB, BC, CD, and DA in ratios K: (1-K),).,: (1-).,), JL: (1- JL), and v: (1- v), respectively, for 0 < K, )." JL, v < 1. Furthermore, let FA, F B , Fe, and FD denote the areas of triangles DAB, ABC, BCD, and CD A, respectively. Then FA + Fe = K and FB + FD = K. Triangles SAP and DAP have collinear bases and the same height (from P). The ratio of their areas is therefore IASI / IADI = 1 - v. Similarly, triangles DAP and DAB have collinear bases and the same height, and the ratio of their areas is IAPI / IABI = K. Consequently, K A / FA = (1 - V)K and so K A = FA (1 - V)K. By analogous arguments, KB = FB(1 - K»." Ke = Fe(1 - ).,)JL, and KD = FD(1 - JL)v, so that KAKBKeKD =

[(1- K)K ][(1- ).,».,][(1

-/L)/L][(1- V)V][FAFc][FBFD].

For each of the six products in square brackets, the sum of its two factors is constant, I or K. Since xy :::: «x + y)/2)2, we have

and equality holds if and only if there is equality in all six applications of xy :::: «x + y)/2)2. This occurs if and only if K = )., = /L = v = 1/2 and FA = FB = Fe = FD = K/2. We have K = )., = /L = v = 1/2 if and only if P, Q, R, S bisect their respective sides. Since the triangles ABC and ABD have the same base, they have the same area (that is, FA = FB) if and only if they have the same height. Thus FA = FB = Fe = FD = K/2 holds if and only if ABC D is a parallelogram.

Editorial comment. This problem is a generalization, from triangle to quadrilateral, of problem #6 on the Eighth International Mathematical Olympiad, which asks for a proof that if

184

PROBLEMS AND SOLUTIONS

[February

P, Q, and R are points on AB, BC, and CA, respectively, then one of the triangles RAP, P BQ, or QC R has area at most 1/4 of the area of ABC. NCCU Problems Group gave examples to show that the property cannot be extended to the cases in which the quadrangle is not convex or is replaced by a polygon with more than four sides. Solved also by R. Akhlaghy & F. Sami, J. Anglesio (France), M. Benedicty, R. J. Chapman (U. K.), J. E. Dawson (Australia), T. Hermann, K. S. Kedlaya, N. Lakshmanan, J. H. Lindsey II, C. A. Minh, A. Nijenhuis, A. Pedersen (Denmark), C. G. Petal as (Greece), K. Schilling, R. Tauraso (Italy), M. Vowe (Switzerland), R. L. Young, T. Zerger, GCHQ Problems Group (U. K.), and the proposer.

The Measure of Rolle's Theorem 10567 [1997, 68]. Proposed by Donald Girod, Canis ius College, Buffalo, NY. Let f : [0,1] --+ IR be a continuous function with f(O) = f(I) = 0. Show that the Lebesgue measure of {h : f(x + h) = f(x) for some x E [0, I]} is at least 1/2. Solution by Walter Stromquist, Wagner Associates, Malvern, PA. The set S = {h E [0, 1] : f(x+h) = f(x) for some x E [0, l]}isclosedandsohasaLebesguemeasure.ltsimageS' under the reflection h ++ I-h has the same Lebesgue measure. We show that SUS' = [0, 1], which implies that the common Lebesgue measure of Sand S' must be at least 1/2. Choose h E [0, 1]. Let Xo and Xl be points in [0, I] where f attains its minimum and maximum values, respectively, and define g: [0, 1] --+ IR by g(x) =

I

f(x

f(x

+ h) -

+h -

f(x)

1) - f(x)

if X + h if x

+h

.:s

1;

> 1.

°

Then g is continuous, g(xo) ~ 0, and g(xJ} .:s 0, so g(X2) = for some X2 E [0, 1]. If X2 + h .:s 1 then f(X2 + h) = f(X2) and h E S. If X2 + h > 1 then X2 - (1 - h) E [0,1] and f(X2 - (1 - h)) = f(X2), so 1 - h E S, and h E S'. Thus every h E [0, 1] is in SUS'. Solved also by M. Bowron, P. Budney, R. Holzsager, G. L. Isaacs, V. Keselj & V. Lucic (Canada), N. Komanda, 1. H. Lindsey II, W. A. J. Luxemburg, S. C. Matz, K. Schilling, GCHQ Problems Group (U. K.), NCCU Problems Group, and the proposer.

Continuous Bijections without Homeomorphism 10569 [1997, 69]. Proposed by W M. Priestley, University of the South, Sewanee, TN. Let X and Y be countable sets of real numbers (each endowed with the subspace topology). If there exist one-to-one continuous maps of X onto Y and of Y onto X, does it follow that X and Y are homeomorphic? Solution by Walter Stromquist, Wagner Associates, Malvern, PA. No. Let X = {x: x is rational and x < O} U {"', 1/8, 1/4, 1/2, 1,2,4,8, .. ·} and Y = XU {O}. Then X and Y cannot be homeomorphic because Y contains a point (namely, 0) that is a limit point of isolated points, and X contains no such point. A one-to-one continuous map f of X onto Y can be defined by f (x) = x if x < 1, f(l) = 0, and f(x) = x/2 if x > 1. A one-to-one continuous map g of Y onto X can be defined, in part, by g(y) = y - 1 if y < 1. Since the unmatched points of Y are all isolated, g remains continuous no matter how we extend it. There remains a countable infinity of unmatched points in each of X and Y, so there exists a one-to-one map of the unmatched points of Y onto the unmatched points of X. We can extend g to all of Y using any such map. Editorial comment. The proposer notes that any counterexample must (by a theorem of Sierpinski) use constructions with infinitely many isolated points. But he notes that in general two topological spaces without isolated points, each admitting a continuous bijection onto the other, still need not be homeomorphic. Solved also by J. Cobb, 1. Ferrer (Spain), R. Holzsager, A. W. Schurle, and the proposer.

1998]

PROBLEMS AND SOLUTIONS

185

REVIEWS Edited by Underwood Dudley Mathematics Department, De Pauw University, Greencastle, IN 46135

"Invertible" Polyhedron Models. Distributed by Snyder Engineering, 7552 Dumas Drive, Cupertino, California 95014.

Reviewed by Gerald L. Alexanderson and Jean Pedersen We recently discovered the existence of some polyhedral models originating in what was once East Germany and we would like to call them to the attention of enthusiasts of polyhedral geometry who may not have discovered them yet. The seven models are large-suitable for demonstrations to groups of students and mathematicians-colorful and meticulously constructed with cloth hinges at the edges. Moreover, some have internal magnets allowing for easy transformation from one state to another. The models, all Platonic solids in their original state, are each decomposable into pieces that can be reassembled to form "stellations" having the same underlying symmetry as the original polyhedron. The process of transforming them is a kinetic process with interesting intermediate states. And, in almost any state, they are stunningly beautiful. There is no standard language of which we are aware to describe the kinds of dissections involved, though there is a literature on these polyhedra, albeit, it seems, only in German. One such booklet is Umstulpmodelle der Platonische Korper, by Wolfgang Maas and Immo Sykora, published by Kaspar Hauser Therapeutikum, Berlin, 1993. The language we use is, we hope, descriptive, but it may not appear standard even to experienced geometers. With the exception of one of the three cubes, these seven models of the Platonic solids all have the characteristic that when they are disassembled they come apart into three or more pieces so that the original polyhedron can be "turned inside out," leaving a cavity in the shape of the original polyhedron. To be more precise, the models are constructed so that the pyramids (whose bases are the faces of the original polyhedron, with height equal to the perpendicular distance from the center of the base face to the center of the polyhedron) can be repositioned pointing outwards, rather than inwards. On some of the models the pyramids are partitioned into parts, apparently so they can be maneuvered properly. We will refer to these models, with the exception of the unusual cube, as invertible polyhedra.

There are two features shared by all the invertible models. The first is that the coloring of the original solid destroys the symmetry of the underlying group, reducing the symmetry group of the polyhedron to a cyclic or dihedral group-or worse, to a centrally symmetric figure. However, in each case, when the polyhedron is reassembled in its inverted form its surface is monochromatic so that the entire symmetry group of the underlying polyhedron is again revealed: A4 for the tetrahedron, S4 for the cube and octahedron, and As for the dodecahedron and icosahedron. This feature, with the color of the inverted model being always

186

REVIEWS

[February

different from the colors of the base model, is very helpful in making the transition from the original to the inverted model. The second feature shared by all the invertible models is that there is always a piece of the model that forms a rotating ring of tetrahedra or, in just one case, two conjoined rotating rings of tetrahedra. The tetrahedra are, of course, not regular, and the number of them in each ring varies depending on the Platonic solid being inverted. A third feature, mentioned previously, is that in the more complicated models magnets have been strategically placed inside the pieces. This greatly reduces the frustration of having only two hands with which to hold the various parts in place when making the transition from the original to the inverted model, or vice versa. Despite the effect of the magnets we would advise anyone trying to manipulate the models to do so on a surface with a coefficient of friction at least equivalent to that of a plush carpet, since otherwise it is somewhat tricky to hold any of the rotating rings in the proper position long enough to put the magnetized pieces in place. (Snyder Engineering, the importer and distributor of these models, has available a video tape that demonstrates how the models are taken apart and reassembled. The tape, a poster, and a detailed price list are available for $10 from Snyder Engineering.) The manufacturer of these remarkable models claims that these are the only possibilities for constructing invertible models of the Platonic solids. Although we cannot say how it might be done otherwise, we are not so sure that this is true. For one thing, the tetrahedron is not the only polyhedron that may be used to construct a rotating ring of polyhedra. Any polyhedron that has opposite edges that are not parallel in space may be used to construct a rotating ring. A simple example is the truncated tetrahedron. A less obvious example is the heccaidecadeltahedron, the convex polyhedron having sixteen equilateral triangles for faces. Perhaps the reader would like to try to find other ways of constructing these invertible models. We now describe briefly some of the models, with comments about why we found them to be mathematically interesting. We will not try to be comprehensive, nor to describe the tactile pleasure of handling the models since, like so much of mathematicS, it is really better to do it yourself. As P6lya said, "Mathematics is not a spectator sport!" We will leave most of the mysteries of the models for readers to discover for themselves, either by viewing the video tape devoted to them or, even better, by actually manipulating the models. The only non-invertible polyhedron in the set is a cube composed of three pieces, credited to Paul Schatz. It is shown in Figure 1. (All of the figures in this review are taken from the poster and are reproduced courtesy of Werkstatt fUr Platonische Karper, Berlin') When the two congruent non-convex solid pieces are removed from opposite vertices what remains is a rotating ring of six tetrahedra. When this ring is revolved it can be laid on a flat surface so that its boundary forms a perfect equilateral triangle, with no hole in the center, or it can be maneuvered and laid on a flat surface so that its boundary forms a regular hexagon, with an equilateral triangular hole in its center. It is, of course, not difficult to arrange the ring in space so that you can reassemble the cube by inserting the pieces that originally came from opposite vertices. We are confident that this model, though remarkably simple compared with the other models, still has secrets to reveal. The second model, due to Franz Sykora (see Figure 2), is of an invertible regular tetrahedron. It too has just three pieces. There are two pieces that when removed from opposite edges leave a rotating ring of eight tetrahedra. Oddly 1998]

REVIEWS

187

Figure 1

Figure 2

enough we found this model to be the most difficult to reassemble, in both directions. What helped us was remembering that the cavity had to be the regular tetrahedron with which we started, and then we finally had to think of the symmetries involved. The inverted polyhedron is a 12-faced polyhedron, known as the triakis tetrahedron, and has the expected symmetry of the proper rotation group A 4 • The third model, credited to Konrad Schneider (see Figure 3) is of an invertible cube. Again, there are just three pieces. The top and bottom pieces in Figure 3 each consist of a square pyramid with a tetrahedron attached, with cloth hinges, to

188

REVIEWS

[February

Figure 3

each edge of the base. The third piece is a rotating ring of eight tetrahedra. What is particularly pleasing about this model is that when it is reassembled it forms the rhombic dodecahedron where one can see clearly that the pyramids that sit on the faces of the original cube are just the right height so that the edges of the cube disappear into twelve rhombic faces lying on the edges of the original cube. In fact, the short diagonals of the rhombic faces clearly outline the original cube, if one thinks of how this rhombic dodecahedron sits inside the cubical lattice, and the model shows very vividly why the rhombic dodecahedron must be a space-filler. The second invertible cube, credited to Wolfgang Maas, has five pieces (see Figure 4): two congruent parts consisting of six tetrahedra, two congruent parts

Figure 4

1998]

REVIEWS

189

consisting of two tetrahedra, and a single piece consisting of two conjoined rotating rings of eight tetrahedra. The surface of the finished inverted model is, of course, the same as that of the previous cube, although some of its rhombic faces show not just one but two of the diagonals. The octahedron, credited to Friedemann and Immo Sykora, and the dodecahedron, by Wolfgang Maas, are both composed of just three pieces (see Figures 5 and 6(a»: one piece from each of two opposing faces and a rotating ring that sits between them. For the octahedron the rotating ring is composed of twelve

FigureS

(b)

(a) Figure 6

190

REVIEWS

[February

tetrahedra and for the dodecahedron the ring has twenty tetrahedra. Not surprisingly, you can position the rotating rings in interesting ways in the intermediate stages. The resulting inverted polyhedra resemble, but are not quite, the stella octangula (from the octahedron) and the small stellated dodecahedron (from the dodecahedron), as in Figure 6(b). Although their faces are not extensions of the original face planes of the underlying polyhedra they are, nevertheless, beautiful models and they show very vividly, by the removal of one of the smaller pieces, that these are the inversions they claim to be. The icosahedron, by Immo Sykora, is the most complicated model, consisting of two pieces that are compounds of four tetrahedra, six pieces that are compounds of two tetrahedra, and a spectacular rotating ring of thirty-six tetrahedra (see Figures 7(a), (b), (c)). The model comes with a base icosahedron and a stand, so that you can build the inverted model around it. Without the base model, the stand, and the magnets that are strategically placed within the smaller pieces we would not have been able to assemble the inverted model. With these aids it was

(b)

(a)

(d)

(c) Figure 7

1998]

REVIEWS

191

actually rather easy (well, at least possible!) and immensely satisfying. The resulting model, shown in Figure 7(d), has pyramids on its faces that are too high to be the first stellation of the icosahedron and not high enough to be the great stellated dodecahedron. Despite this minor (and unavoidable!) fault the inverted model is very beautiful to behold. Santa Clara University, Santa Clara, California 95053-0290 [email protected],[email protected]

Topology and Geometry. By Glen E. Bredon. Springer-Verlag, 1993, xiv $69.

+ 557 pp.,

Reviewed by William Goldman The book under review is an excellent textbook suitable for a sequence in algebraic and differential topology. Parts of it have been used here at the University of Maryland for the basic two-semester sequence in topology for the last four years. The book comprehensively treats basic algebraic topology and is highlighted by many interesting applications and topics not always covered in other texts. The author chose his topics admirably, providing strong motivation for a subject that can appear unnecessarily abstract and unmotivated. This ambitious book covers homotopy theory and homology theory, some differential topology (vector bundles, tubular neighborhoods, and transversality) and Lie groups. Although the book covers the Gysin and Wang exact sequences and the Steenrod cohomology operations, it doesn't get into spectral sequences. Similarly, it treats de Rham theory and differential forms, but it doesn't get to harmonic theory or Morse theory. It can't cover everything, of course, but, being 557 pages IQng, its scope is still enormous. The book is full of exercises of varying difficulty and contains an excellent index. The book starts with a discussion of general topology. This is not a comprehensive treatment of the subject, but I feel the author devotes the right amount of time to this for most applications. The second chapter deals with differentiable manifolds, which is quite appropriate since so much topological intuition derives from these examples. Furthermore, many theorems have alternate proofs in the smooth case, which can be shorter and more intuitive than homological proofs. The difficulty, of course, is that much more theory must be developed to handle the additional structure. However, this material is so fundamental nowadays that students should see this early. The book contains many examples, but not as many near the beginning as later in the text. A discussion of more examples near the beginning would make the text more accessible to beginning students. The section on the fundamental group ends with a description of SO(3), basic to many applications. The theory is illustrated by an experiment ("undoing a double twist"), which should be very useful to a student learning the abstract theory. After singular homology is introduced, the Eilenberg-Steenrod axioms are stated. From these, basic applications are derived, such as the Brouwer fixed point theorem and the nonexistence of nonsingular vector fields on even-dimensional

192

REVIEWS

[February

spheres. Degree theory is discussed and leads to an extensive treatment of CW-complexes and cellular homology. This machinery permits many deep applications such as the generalized Jordan curve theorem and invariance of domain. A whole section is devoted to the proof of the generalized Schoenflies theorem. Though the theorem is not used elsewhere in the book, it is an interesting and highly nontrivial application to geometric topology. I feel that including these gems makes the book particularly valuable and inviting to a reader interested in learning algebraic topology and its relations to other fields of mathematics. Simplicial complexes are only introduced here, and the chapter concludes with the Lefschetz-Hopf fixed point theorem. Computation of the fundamental group of a simplicial complex is not discussed, but that is probably not a significant omission. The next section treats cohomology, starting right in with a discussion of exterior algebra, followed by exterior differential forms. Since most students at this level will have seen multivariable integration, probably a typical student feels more comfortable with differential forms than with general singular cochains. Singular cohomology theory can seem abstract and unmotivated and I think Bredon's approach introduces the concepts in a clearer and more direct way than the approaches used in other texts. A complete proof of de Rham's theorem is followed by the treatment of singular cohomology. It is here that the derived functors Ext and Tor are introduced and the universal coefficient theorem is proved. A whole section is devoted to complex projective space, certainly an important and basic example. Explicit calculations with differential forms are given, as well as the relationship with their cell structure and the Hopf map. This nontrivial example illustrates many of the ideas developed earlier in the book. A reader willing to put in the effort to study this example carefully will benefit greatly. Hopfs theorem classifying self-maps of S" up to homotopy is proved here, foreshadowing the obstruction theory later to come. The chapter concludes with a ten-page discussion of differential forms on compact Lie groups, certainly a basic (and historical) example in differential geometry. Invariant differential forms are discussed, and the rank of H 3 (G) is identified with the number of simple factors of a compact semisimple Lie group G. The next chapter, entitled "Products and Duality," develops the standard theory of cross, cup, slant, and cap products, with abundant examples to illustrate the abstract theory. Before discussing Poincare duality from the algebraic viewpoint, a section on the "classical outlook" develops the more intuitive approach for triangulated manifolds. Applications include the cohomology of complex projective spaces, Thom's theorem on the vanishing of the signature of a boundary, examples (lens spaces) of closed 3-manifolds with isomorphic homotopy, and homology groups that are not homotopy-equivalent. The next section discusses intersection theory, the Euler and Stiefel-Whitney characteristic classes, and Lefschetz numbers. Since smooth manifolds have been developed, the index of a vector field can be defined and the Poincare-Hopf theorem is discussed as the infinitesimal case of the theorem. A topological proof of the fundamental theorem of algebra is given here. (Actually, four such proofs may be found in the book.) Another application is the uniqueness of maximal tori in compact Lie groups. The Gysin sequence is used to compute the cohomology of Stiefel manifolds and the unitary group. The Steenrod squares are defined and developed, although the Adem relations are quoted without proof. These cohomology operations are then applied to show that S"-l is parallelizable only if n is a power of 2. (Using deeper methods, Adams showed that n must be 1, 2, or 4.) The relations of these results with division algebras are discussed. The chapter concludes with a discussion of plumbing and an example of 1998]

REVIEWS

193

a non-smoothable topological manifold. Certainly a wealth of interesting and highly nontrivial mathematics is discussed here. Homotopy theory is discussed in the last chapter. Whitehead products, the Whitehead and Hurewicz theorems, and the exact homotopy sequence of a fibration are discussed. The homotopy group 7Tn+ Z (sn) is computed. The discussion of obstruction theory is particularly welcome, since I have often tried to direct graduate students to this subject, but unfortunately most references with which I am familiar are not recent. It seems that the author included everything that could be done without spectral sequences. This is entirely appropriate, since a thorough treatment of this material would add quite a bit to an already enormous book. Some of the students here who have read the book give it high marks for comprehensibility, while others have found it difficult. When I taught point-set topology from it, the treatment of quotient spaces in particular received favorable comments. I heard comments like "It's all there" and "It's a great book to have." The section on paracompactness was too short for some, although I found it quite satisfactory. I didn't like the definition of properly discontinuous action (a personal pet peeve): the definition given in the book, which I call "wandering," implies that the quotient map is a branched covering but doesn't imply the quotient is Hausdorff. (To assure that the quotient space is Hausdorff, the action is usually assumed to be a proper action.) However, this is a very small issue in light of the grand scope of this book. For some novice students, the book may be a bit too difficult or comprehensive. Such students might be overwhelmed by its size and scope and could find it hard to extract the intuitions and conceptualizations peculiar to the subject. But even for novice students, the book makes an excellent reference. It can be used to complement an easier more intuitive book that is less ambitious. In our department we offer graduate qualifying examinations in topology, and selections from the book comprise the syllabus. It is quite suitable at this level. The author has provided a real service in putting all this material together in one place in a well-organized and motivated manner. Furthermore, this book will enable a motivated student to appreciate the place of algebraic topology in modern mathematics. University of Maryland, College Park, Maryland 20742 [email protected]

194

REVIEWS

[February

TELEGRAPHIC REVIEWS Edited by Arnold Ostebee with the assistance of the Mathematics Departments of Carleton, MacaIester, and St. Olaf Colleges Telegraphic Reviews are designed to alert readers in a timely manner to new books appropriate to mathematics teaching and. research. Special codes classify reviews by subject area and appropriate use:

T: Textbook

P: Professional Reading

C .. Computer Software

L ; Undergraduate Library

1-4: Semester ** : Special Emphasis S : Supplementary Reading 13: Grade L e v e l ? ? : Questionable Readers are advised that price information is subject to change. Selected books receive a second, more extensive review in the Monthly. Books submitted for review should be sent to Book Reviews Editor, American Mathematical Monthly, St. Olaf College, 1520 St. Olaf Avenue, Northfield, MN 55057-1098.

History, P, L. Leading Personalities in Statistical Sciences: From the Seventeenth Century to the Present. Eds: Norman L. Johnson, Samuel Kotz. Ser. in Prob. & Stat. Wiley, 1997, xxiii + 399 pp, $49.95 (P). [ISBN 0-471-163813] Brief chronicles of more than 100 important contributors to probabilistic and statistical methods from the Bernoulli's to Deming. Numerous photographs. A lovely text. MK History, P. Mathematics from Leningrad to Austin: George G. Lorentz' Selected Works in Real, Functional and Numerical Analysis. Ed: Rudolph A. Lorentz. Birkhauser Boston, 1997, $189 set, [ISBN 0-8176-3923-3] set. Volume 1, xxxvi + 548 pp; Volume 2, xxviii + 648 pp. Combinatorics, P. Enumerative Combinatories, Volume 1. Richard P. Stanley. Stud. in Adv. Math., V.49. Cambridge Univ Pr, 1997, xi + 325 pp, $59.95. [ISBN 0-521-55309-1] Republication of the 1986 Wadsworth edition (TR, March 1987) with supplementary problems, errata, and addenda. Combinatorics, P. Incidence Algebras. Eugene Spiegel, Christopher J. O'Donnell. Pure & Appl. Math., V. 206. Marcel Dekker, 1997, ix + 335 pp, $125. [ISBN 0-8247-0036-8] Incidence algebras are a tool for studying partially ordered sets and thus relate to many combinatorial problems. DB Number Theory, P. Cohomology of Drinfeld Modular Varieties, Part II: Automorphic Forms, Trace Formulas and Langlands Correspondence. Gerard Laumon. Stud. in Adv. Math., V. 56. Cambridge Univ Pr, 1997, xi + 366 pp, $64.95. [ISBN 0-521-47061-7]

1998]

Number Theory, P*, L**. Pi: A Source Book. Lennart Berggren, Jonathan Borwein, Peter Borwein. Springer-Verlag, 1997, xix + 716 pp, $59.95. [ISBN 0-387-94924-0] 70 carefully selected papers document the history of rr. Includes research literature and historical studies as well as a few pieces of a light-hearted sort (e.g., the 1897 Indiana bill to legislate the value of rr). An invaluable resource. AO Linear Algebra, P. Introduction to Matrix Analysis, Second Edition. Richard Bellman. SIAM, 1997, xxviii + 403 pp, $32 (P). [ISBN 0-89871-399-4] Republication of the 1970 McGraw-Hill edition (TR, January 1971). Linear Algebra, T(17: 1), P, L. Nonnegative Matrices and Applications. R.B. Bapat, T.E.S. Raghavan. Eney. of Math. & Its Applic., V.64. Cambridge Univ Pr, 1997, xiii + 336 pp, $64.95. [ISBN 0-521-57167-7] Theory and applications of entry-wise nonnegative matrices (including game theory, combinatorics, inequalities, optimization, and mathematical economics). Assumes only a minimal background in linear algebra. AO Ring Theory, P. Non-Commutative Valuation Rings and Semi-Hereditary Orders. Hidetoshi Marubayashi, HaruoMiyamoto, Akira Ueda. KMono. in Math., V. 3. Kluwer Academic, 1997, viii + 191 pp, $99. [ISBN 0-7923-4562-2] Complex Analysis, T(16-17: 1, 2), S**, P, L**. Visual Complex Analysis. Tristan Needham. Clarendon Pr, 1997, xxiii + 592 pp. [ISBN 0-19-853447-7] Delivers what its title promises, and more: an engaging, broad, thorough, and often deep, development of un-

TELEGRAPHIC REVIEWS

195

dergraduate complex analysis and related areas (non-Euclidean geometry, harmonic functions, etc.) from a geometric point of view. The style is lucid, informal, reader-friendly, and rich with helpful images (e.g., the complex derivative as an "amplitwist"). A truly unusual and notably creative look at a classical subject. PZ Differential Equations, P. Existence Theory for Nonlinear Ordinary Differential Equations. Donal O'Regan. Math. & Its Applic., V. 398. Kluwer Academic, 1997, 196 pp, $109. [ISBN 0-7923-4511-8] Differential Equations, P. Oscillation Theory of Two-Term Differential Equations. Uri Elias. Math. & Its Applic., V. 396. Kluwer Academic, 1997, vii+217pp, $119. [ISBNO-7923-4447-2] Partial Differential Equations, P. Fine Regularity of Solutions of Elliptic Partial Differential Equations. Jan Maly, William P. Ziemer. Math. Surveys & Mono., V. 51. AMS, 1997, xiv + 291 pp, $75. [ISBN 0-8218-0335-2] From the Abstract: "The object of this book is to provide a comprehensive exposition of the interplay between nonlinear potential theory and the analysis of boundary behavior of weak solutions of elliptic PDEs in divergence form." Partial Differential Equations, P. Quasilinear Elliptic Equations with Degenerations and Singularities. Pavel Drabek, Alois Kufner, Francesco Nicolosi. Ser. in Nonlinear Analysis & Applic., V. 5. Walter de Gruyter, 1997, xii + 219 pp, $98.95. [ISBN 3-11-015490-0] Partial Differential Equations,:P. The Analysis ofSolutions ofElliptic Equations. Nikolai N. Tarkhanov. Math. & Its Applic., V. 406. Kluwer Academic, 1997, xx + 479 pp, $245. [ISBN 0-7923-4531-2] Revised and expanded translation of the 1991 Russian monograph Laurent Series for Solutions of Elliptic Equations. Partial Differential Equations, P. Inverse Stefan Problems. N.L. Gol'dman. Math. & Its Applic., V.412. Kluwer Academic, 1997, viii + 250 pp, $139. [ISBN 0-7923-4588-6] Theory and methods for solving inverse Stefan problems for quasilinear parabolic equations in domains with free boundaries. Partial Differential Equations, P. Harmonic Analysis and Nonlinear Differential Equations. Eds: Michel L. Lapidus, Lawrence H. Harper, Adolfo J. Rumbos. Contemp. Math., V. 208. AMS, 1997, xii + 350 pp, $59 (P). [ISBN 08218-0565-7] Proceedings of a 1995 conference at the University of California, Riverside, held to honor V.L. Shapiro. Dynamical Systems, P. Dynamics of OneDimensional Maps. A.N. Sharkovsky, et al.

196

Math. & Its Applic., V. 407. Kluwer Academic, 1997, ix + 261 pp, $165. [ISBN 0-7923-45320] A revised and updated translation of the original (1989) Russian text.

Dynamical Systems, P. Recurrence in Topological Dynamics: Furstenberg Families and Ellis Actions. Ethan Akin. Ser. in Math. Plenum Pr, 1997, ix + 265 pp, $75. [ISBN 0-306-45550-1] Numerical Analysis, T(17: 1), P, L. Applied Numerical Linear Algebra. James W. Demmel. SIAM, 1997, xi + 419 pp, $45 (P.). [ISBN 089871-389-7] Topics: solution of linear systems, least squares problems, eigenvalue problems, and the singular value decomposition. Covers both direct and iterative algorithms. Discusses how cache-based computer memories affect algorithm design. AO Numerical Analysis, C, P. ScalAPACK Users' Guide. L.S. Blackford, et al. SIAM, 1997, xxvi + 325 pp, $49.50 (P), with CD ROM. [ISBN 0-89871-397-8] "A library of high-performance linear algebra routines for distributed-memory message-passing MIMD computers and networks of workstations supporting parallel virtual machine (PVM) and/or message-passing interface (MPI). It is a continuation of the LAPACK project." Operator Theory, P. Operator Algebras and Applications. Ed: Aristides Katavolos. NATO ASI Ser. C, Vol. 495. Kluwer Academic, 1997, xi + 467 pp, $198. [ISBN 0-7923-4625-4] Proceedings of a 1996 NATO Advanced Study Institute held in Greece. Operator Theory, P. Pseudo-Differential Operators, Singularities, Applications. Yuri V. Egorov, Bert-Wolfgang Schulze. Oper. Theory: Adv. & Applic., V. 93. Birkhauser Boston, 1997, xiii + 349 pp, $139.50. [ISBN 0-81765484-4] Functional Analysis, P. Topological Nonlinear Analysis II: Degree, Singularity and Variations. Eds: Michele Matzeu, Alfonso Vignoli. Prog. in Nonlinear Diff. Eqts. & Their Applic., V.27. Birkhauser Boston, 1997, vii + 601 pp, $120. [ISBN 0-8176-3886-5] 9 survey papers based on presentations at a 1995 workshop held in Italy. Functional Analysis, P. Series in Banach Spaces: Conditional and Unconditional Convergence. Mikhail I. Kadets, Vladimir M. Kadets. Transl: Andrei Iacob. Oper. Theory: Adv. & Applic., V. 94. Birkhauser Boston, 1997, viii + 156 pp, $84. [ISBN 0-8176-54011] A comprehensive survey. An appendix dis-

TELEGRAPHIC REVIEWS

[February

cusses similar problems in vector-valued Riemann integration. Functional Analysis, P. The Theory of Cubature Formulas. S.L. Sobolev, V.L. Vaskevich. Math. & Its Applic., V. 415. Kluwer Academic, 1997, xxi + 416 pp, $207. [ISBN 0-7923-4631-9] Revised and updated translation of the 1996 Russian edition. Functional Analysis, P. Idempotent Analysis and Its Applications. Vassili N. Kolokoltsov, Victor P. Maslov. Math. & Its Applic., V. 401. Kluwer Academic, 1997, xii + 305 pp, $159. [ISBN 0-7923-4509-6] The authors define idempotent analysis to be the study of semimodules of functions ranging in a semiring with idempotent addition. Text develops theory and presents diverse applications. Analysis, P. Advanced Topics in Difference Equations. Ravi P. Agarwal, PatriciaJ.Y. Wong. Math. & Its Applic., V. 404. Kluwer Academic, 1997, ix + 507 pp, $245. [ISBN 0-7923-45215] Collects the author's recent research results on difference equations and inequalities. Algebraic Geometry, P. Birational Algebraic Geometry. Eds: Yujiro Kawamata, Vyacheslav V. Shokurov. Contemp. Math., V. 207. AMS, 1997, xx + 152 pp, $35 (P). [ISBN 0-82180769-2] Proceedings of a 1996 conference held at Johns Hopkins University in memory of Wei-Liang Chow. Algebraic Geometry, P. Geometry of Higher Yoichi Dimensional Algebraic Varieties. Miyaoka, Thomas Peternell. DMV Sem., B.26. Birkhauser Boston, 1997, vi + 217 pp, $34.50 (P). [ISBN 0-8176-5490-9] Algebraic Geometry, P. Algebraic Geometry. Ed: Sinan Sertoz. Lect. Notes in Pure & Appl. Math., V. 193. Marcel Dekker, 1997, xvi + 382 pp, $165 (P). [ISBN 0-8247-0123-2] Papers from a 1995 summer school at Bilkent University (Turkey). Differential Geometry, P. Topics in SingularityTheory. Eds: A. Khovanskii, A. Varchenko, V. Vassiliev. AMS Transl., Ser. 2, Vol. 180. AMS, 1997, xiii + 255 pp, $89. [ISBN 08218-0807-9] 21 papers collected to honor V.1. Arnold. Differential Geometry, P. Two-Dimensional Conformal Geometry and Vertex Operator Algebras. Yi-Zhi Huang. Prog. in Math., V. 148. Birkhauser Boston, 1997, xii + 280 pp, $54.50. [ISBN 0-8176-3829-6] Differential Geometry, P. Geometry of Foliations. Philippe Tondeur. Mono. in Math., V. 90. Birkhauser Boston, 1997, viii + 305 pp, $98. [ISBN 0-8176-5741-X]

1998]

Differential Geometry, P. Gauge Field Theory and Complex Geometry, Second Edition. Yuri I. Manin. Springer-Verlag, 1997, xii + 346 pp, $129. [ISBN 0-387-18275-6] New edition (First Edition, TR, February 1989) incorporates corrections, an addendum on recent developments written by S. Merkulov, and an updated list of references. Geometry, P. Mostly Finite Geometries. Ed: Norman L. Johnson. Lect. Notes in Pure & AppL Math., V. 190. Marcel Dekker, 1997, xxi + 424 pp, $165 (P). [ISBN 0-8247-0035X] Proceedings of a 1996 conference at the University of Iowa held to honor T.O. Ostrom. Algebraic Topology, P. Generalized Etale Cohomology Theories. J.E Jardine. Prog. in Math., V. 146. Birkhauser Boston, 1997, x + 317 pp, $79.50. [ISBN 0-8176-5494-1] Operations Research, P. Ten Years LNMB.· Eds: W.K. Klein Haneveld, O.J. Vrieze, L.C.M. Kallenberg. CWI Tract, V. 122. Centrum voor Wiskunde en Informatica, 1997, iii + 382 pp, Dfi. 70 (P). [ISBN90-6196-475-X] 41 papers collected in recognition of the tenth anniversary of the founding of the Dutch Network of Operations Research. Articles on combinatorial optimization, discrete mathematics, stochastic operations research, and game theory. Optimization, P. Numerica: A Modeling Language for Global Optimization. Pascal Van Hentenryck, Laurent Michel, Yves Deville. MIT Pr, 1997, xvii + 210 pp, $25 (P). [ISBN 0-262-72027-2] Numerica uses interval and local methods together with constraint satisfaction techniques to solve global optimization problems (e.g., find all solutions to a system of nonlinear constraints, find all optima of a nonlinear objective function subject to a set of nonlinear constraints). The methods used guarantee correctness, completeness, finite termination, and certainty. Book describes the design, functionality, and implementation of Numerica as well as some hints on using it effectively. AO Optimization, P. Foundations of Mathematical Optimization: Convex Analysis without Linearity. Diethard Pallaschke, Stefan Rolewicz. ,Math. & Its Applic., V. 388. Kluwer Academic, 1997, xii+582 pp, $254. [ISBNO-7923-4424-3] Optimization, T(17-18: 2), P. Optimization: Algorithms and Consistent Approximations. Elijah Polak. Appl. Math. Sci., V. 124. Springer-Verlag, 1997, xx + 779 pp, $69.95. [ISBN 0-387-94971-2] "Optimality conditions, algorithms, and discretization techniques for nonlinear programming, semiinfinite optimization, and optimal control prob-

TELEGRAPHIC REVIEWS

197

lems." Introduces optimality functions as a theoretical tool for studying optimality conditions. Presents an abstract theory of optimization algorithms that deals with convergence conditions, algorithm implementation, and consistent approximations. AO Optimization, T(18: 1, 2), C. Bayesian Heuristic Approach to Discrete and Global Optimization: Algorithms, Visualization, Software, and Applications. Jonas Mockus, et al. Nonconvex Optim. & Its Applic., V. 17. Kluwer Academic, 1997, xv + 396 pp, $190, with disks. [ISBN 0-7923-4327-1] Discusses a wide variety of optimization techniques, including "greedy," "permutation," "deterministic," and "stochastic" search approaches. Includes a variety of applications. LINUX version of global optimization software is on disk. MK Optimal Control, P. Conflict-Controlled Processes. A. Chikrii. Math. & Its Applic., V. 405. Kluwer Academic, 1997, xx + 403 pp, $210. [ISBN 0-7923-4522-3] Focuses on methods for classical pursuit-evasion problems. Optimal Control, P. Relaxation in Optimization Theory and Variational Calculus. Tomas Roubfcek. Ser. in Nonlinear Analysis & Applic., V. 4. Walter de Gruyter, 1997, xiv + 474 pp, $158.95. [ISBN 3-11-014542-1] Probability, P. Advances in Combinatorial Methods and Applications to Probability and Statistics. Ed: N. Balakrishnan. Birkhauser Boston, 1997, xxxiv + 562 pp, $79.95. [ISBN 0-8176-3908-X] 32 survey papers collected to honor Sri Gopal Mohanty. Sections: Lattice Paths and Combinatorial Methods; Applications to Probability Problems; Applications to Urn Models; Applications to Queueing Theory; Applications to Waiting Time Problems; Applications to Distribution Theory; Applications to Nonparametric Statistics. Probability, P. Probability and Lattices. Eds: W. Vervaat, H. Holwerda. CWI Tract, V. 110. Centrum voor Wiskunde en Informatica, 1997, 154 pp, Dfl. 40 (P). [ISBN 90-6196-441-5] 6 papers on the qualitative theory of extremal processes and random capacities. Stochastic Processes, P. Some Aspects of Brownian Motion, Part II: Some Recent Martingale Problems. Marc Yor. Lect. in Math. Birkhauser Boston, 1997, xii + 144 pp, $27.50 (P). [ISBN 0-8176-5717-7] Notes from lectures given at ETH ZUrich between 1991 and 1993. Stochastic Processes, P. Stochastic Analysis. Paul Malliavin. Ser. of Compo Stud. in Math., V.313. Springer-Verlag, 1997, xi + 343 pp,

198

$125. [ISBN 3-540-57024-1] Focuses on geometric point of view. Links methods of classical analysis and differential geometry. Stochastic Processes, P. Nonparametric Estimation for a Windowed Line-Segment Process. BJ. Wijers. CWI Tract, V. 121. Centrum voor Wiskunde en Informatica, 1997, ii + 152 pp, Dfl. 40 (P). [ISBN 90-6196-474-1] Mathematical Statistics, T(17: 1). Matrix Analysisfor Statistics. James R. Schott. Ser. in Prob. & Stat. Wiley, 1997, xii + 426 pp, $59.95. [ISBN 0-471-15409-1] A coherent and comprehensive collection of matrix/linear algebra results needed for statistical methods. Plenty of statistical examples and lots of exercises. Topics range from eigenvalues and eigenprojections, including extremal properties, to partitioned matrices, Kronecker products, Toeplitz matrices, and matrix differentiation. MK Statistical Methods, T(I6-17). Survival Analysis: Techniques for Censored and Truncated Data. John P. Klein, Melvin L. Moeschberger. Stat. for Biology & Health. Springer-Verlag, 1997, xiv + 502 pp, $59.95. [ISBN 0-38794829-5] Excellent, well-written text. Includes a wide array of relevant examples from the applied literature without skipping mathematical detail. Numerous exercises. Topics range from introductory definitions of hazard function and censoring to proportional hazards and frailty models. MK Statistical Methods, T(17-18). Machine Learning and Statistics: The Interface. Eds: G. Nakhaeizadeh, C.C. Taylor. Sixth-Generation Compo Techn. Ser. Wiley, 1997, xvii + 343 pp, $64.95. [ISBN 0-471-14890-3] Papers from 'a workshop held in Catania, Sicily, following the European Conference in Machine Learning (1994). Material accessible to non-experts. Wide variety of topics: statistical properties of tree-based algorithms, DIPOL-a hybrid piecewise linear classifier, distance-based decision trees, fuzzy controllers, and probabilistic symbolic classifiers. MK Statistical Methods, T(I6-17), C. Introduction to Time Series and Forecasting. Peter J. Brockwell, Richard A. Davis. Texts in Stat. Springer-Verlag, 1996, xiii + 420 pp, $64.95, with disk. [ISBN 0-387-94719-1] A thorough, applied text with numerous examples and exercises. Topics include stationary processes, ARMA and ARIMA models, spectral analyses, non-stationary and seasonal models, multivariate time-series, and state-space models. Assumes only a knowledge of basic calculus, matrix algebra, and elementary statistics. Disk includes data and software. MK

TELEGRAPHIC REVIEWS

[February

Statistical Methods, T*(17-18: 2). Bayesian Forecasting and Dynamic Models, Second Edition. Mike West, Jeff Harrison. Ser. in Stat. Springer-Verlag, 1997, xiv + 680 pp, $59. [ISBN 0-387-94725-6] The text for modern courses on time-series, dynamic linear models, and forecasting. Beautifully written exposition is filled with philosophical, statistical, and mathematical insights. Numerous thoughtful examples and exercises. Updates the First Edition (TR, April 1990) and includes new material on retrospective time-series analysis, decompositions in state-space framework, time-varying parameter estimation, and MCMC methods for dynamic models. MK Statistics, P. Advances in Statistical Decision Theory and Applications. Eds: S. Panchapakesan, N. Balakrishnan. BirkhauserBoston, 1997, xIx + 448 pp, $79.95. [ISBN 0-8176-3965-9] 28 survey papers collected to honor Shanti S. Gupta. Sections: Bayesian Inference; Decision Theory; Point and Interval Estimation; Tests of Hypothesis; Ranking and Selection; Distributions and Applications; Industrial Applications. Statistics, P**, L**. Breakthroughs in Statistics, Volume III. Eds: Samuel Kotz, Norman L. Johnson. Ser. in Stat. Springer-Verlag, 1997, xxv + 559 pp, $89.95. [ISBN 0-387-94039-1] The third volume in a series collecting important papers written during the past 110 years. Each paper is preceded by an introduction that provides background and other information. Statistics, P. Advances in the Theory and Practice of Statistics: A Volume in Honor of Samuel Kotz. Eds: Norman L. Johnson, N. Balakrishnan. Ser. in Prob. & Stat. Wiley, 1997, xxviii + 629 pp, $69.95. [ISBN 0-471-15574-8] 38 papers in ten sections: Statistics in the World; Models; Biostatistics; Testing and Estimation; Univariate Distributions; Multivariate Distributions; Characterizations; Probability; Bayes Theory; Descriptive Statistics. Mathematical Computing, S(13-14). Applied Mathematics with Maple. m>ran Andersson. Studentlitteratur, 1997, 448 pp, SEK 413 (P). [ISBN 91-44-00149-5] First half is a general introduction to the symbolic and graphical capabilities of Maple V Release 4. Second half illustrates use of Maple to solve problems in linear algebra, calculus, differential equations, and probability and statistics. AO Computer Science, P. Lecture Notes in Control and Information Sciences-226: Workshop on High Performance Computing and Gigabit Local Area Networks. Eds: G. Cooperman,

1998]

G. Michler, H. Vinck. Springer-Verlag, 1997, 234 pp, $50 (P). [ISBN 3-540-76169-1] Proceedings of a 1996 workshop held at Essen University (Germany). Papers focus on interactions among parallel algorithms, network protocols, and network hardware. Computer Science, P. Multimedia Computing. Ed: T. Ishiguro. Proc. of Sixth NEC Res. Symp. SIAM, 1997, ix + 169 pp, $33.50. [ISBN 089871-372-2] Proceedings of a 1995 symposium held in Tokyo. Numerical Applications (Economics), P. Methods in Finance. Eds: L.c.G. Rogers, D. Talay. Cambridge Univ Pr, 1997, x + 326 pp, $54.95. [ISBN 0-521-57354-8] 16 survey articles on numerical methods useful in financial analysis. Based on presentations at a 1995 workshop at Cambridge University. Applications (Economics), T(I6-17: 1), L. General Equilibrium Theory: An Introduction. Ross M. Starr. Cambridge Univ Pr, 1997, xxiii + 250 pp, $59.95; $19.95 (P). [ISBN 0-521-56414-X; 0-521-56473-5] Mathematically rigorous, self-contained. introduction. Topics include the Arrow-Debreu model, welfare economics, the core and core convergence, futures markets. AO Applications (Physics), P. Using REDUCE in High Energy Physics. A.G. Grozin. Cambridge Univ Pr, 1997, xiv + 384pp, $80. [ISBN 0-52156002-0] Applications (Quantum Theory), P. Classical Nonintegrability, Quantum Chaos. Andreas Knauf, Yakov G. Sinai. DMV Seminar, B. 27. Birkhauser Boston, 1997, vi + 98 pp, $24.50 (P). [ISBN 0-8176-5708-8] Applications (Systems Theory), P. Lecture Notes in Control and Information Sciences227: Control of Uncertain Systems with Bounded Inputs. Eds: Sophie Tarbouriech, Germain Garcia. Springer-Verlag, 1997, xiv + 186 pp, $40 (P). [ISBN 3-540-76183-7] IO papers on fundamental ideas and concepts in robust and constrained control. Applications, P. The Emergence of Complexity in Mathematics, Physics, Chemistry and Biology. Ed: Bernard Pullman. Princeton Univ Pr, 1996, xix + 472 pp, $39.50 (P). [ISBN 0-691-01238-5] Proceedings of the 1992 plenary session of the Pontifical Academy of Sciences. Reviewers DB: David Bressoud, Macalester; MK: Michael Kahn, St. Olaf; AO: Arnold Ostebee, St. Olaf; PZ: Paul Zorn, St. Olaf.

TELEGRAPHIC REVIEWS

199