OVER AND
OVER AGAIN

Preface

Transformation and iteration are two of the most basic notions in mathematics. The three parts of this book discuss a variety of transformations and their iterations, arranged in order of sophistication. Chapters one through nineteen discuss iterations in elementary mathematics. Most problems in this part come from mathematical olympiads of different countries, many from China, drawn largely from the first author's extensive experience as coach of the Chinese delegation at the International Mathematical Olympiads (IMO).

We give special attention to transformations with a smoothing property. A variety of measures of smoothness occurs in our discussions. For example, for ordered n-tuples (a₁, a₂, . . . , a_n) we have occasion to consider the difference max_i{a_i} - min_i{a_i} or the number of sign changes in the sequence; these can be regarded as measures of smoothness. Equilateral triangles can be considered the smoothest of all triangles. Similarly, the regular n - gon can be regarded as the smoothest of all n - sided polygons. In the set of all curve segments having given initial and terminal points, it is reasonable to identify the line segment joining these two points as the smoothest. Circles are considered the smoothest of all closed curves.

Two theorems contained in the first part should be spotlighted. The first (in Chapter 16) is the beautiful theorem discovered by Douglas and Neumann independently in the early 1940's; it gives a process for constructing a regular n - gon from an arbitrary n - gon by means of a sequence of transformations. Professor Neumann's simple and elementary proof is based on complex number computation, and prerequisite material is provided in Chapter 13. In contrast, the theorem in Chapter 18 is a classical result. It says that of all closed curves of a given length, the circle encloses the maximal area. The treatment of this theorem is based upon the Steiner transformation, which is smoothing.

Chapters 19-22 address functional iterations. Basic properties of continuous functions are briefly reviewed in Chapter 19. As a simple illustration Newton's method for finding roots is presented in Chapter 21. Chapter 23 discusses the main result of Li and Yorke's famous paper Period Three Implies Chaos and the beautiful theorem due to Sharkovskii is stated without proof. These chapters provide a basic knowledge about dynamical systems and chaos-a topic which has rapidly developed during the past two decades and which finds application in mathematics, physics, and other sciences.

The last part of the book involves Bézier curves and surfaces; they play an important role in computer aided geometric design (CAGD), a new branch of applied mathematics and computer science. They are a common research interest of the two authors. Bézier techniques are based on Bernstein polynomials, devised in the early 1900's, but which had no numerical application until the early 1960's. Bézier curves and surfaces enable a designer to produce a smooth and pleasing shape, and a program to direct a machine tool to actually create it, by adjusting the locations of control points. The designer does not need to know how this works, but the details of the process have connections with much interesting mathematics, and we explore this. For instance, we obtain estimates for the distances between the control points and the curve; this yields the Weierstrass approximation theorem. Some smoothing and convexity-preserving properties of the Bernstein transformation can be formulated as theorems. As a preparation we included a chapter on variation diminishing matrices.

Spline functions were discussed by 1. J. Schoenberg in the 1940's and have become powerful tools in interpolation and approximation theory, as well as in CAGD. Chapter 27 discusses cubic spline functions for purposes of interpolation, and B-spline bases of higher degrees are presented in Chapter 28 by means of moving averages, a popular method for smoothing functions.

Chapters 1 - 18 require only high school mathematics, with a few exceptions. The level of the book becomes considerably more advanced in the later chapters. The additional background material required is mainly the basics of real analysis. This is not difficult for students who have an aptitude for mathematics and it is presented in an Appendix. It is the length and complexity of many of the discussions which makes the later chapters more difficult.

The first author conceived the idea for this book and began collecting material for it while serving as an associate member of the International Center for Theoretical Physics, Trieste, Italy. He greatly appreciated the hospitality of Professor Abdus Salam, the director of the Center. At the invitation of the second author, he first spent 20 months at Brigham Young University and greatly enjoyed the academic atmosphere at the Department of Civil Engineering and the hospitality of its faculty. In this setting both authors quickly developed a deep mutual respect, which led to the realization of this book.