Introduction
This paper will deal with properties of certain non-linear transformations in Euclidean spaces--mostly in two or three dimensions. In the main they will be of very special and simple algebraic form. We shall be principally interested in the iteration of such transformations and in the asymptotic and ergodic properties of the sequence of iterated points. Very little seems to be known, even on the purely topological level, about the properties of specific non-linear transformations, even when these are bounded and continuous or analytic. The transformations we study in this paper are in fact bounded and continuous, but in general many-to-one, i.e., not necessarily homeomorphisms. In one dimension such transformations are simply functions with values lying in the domain of definition; for example, if f(x) is continuous and nonnegative in the interval [0.1] and max[f(x)] < 1, then x' f(x) is a
transformation* of the type considered. Even in one dimension, however, nothing resembling a complete theory of the ergodic properties of the iterated transformation exists. On the algebraic side, we study in this paper the invariant points (fixed points), finite sets (periods)-and invariant subsets (curves) of these transformations-together with the means of obtaining them constructively. The topological properties of two (not necessarily one-dimensional) transformations S(p), T(p) are identical under a homeomorphism H: when S(p) = H[T[H-l(p)]]. When S and T are themselves homeomorphisms-and for one dimen sion-necessary and sufficient conditions for conjugacy are known.1 When S and T are one-dimensional, but not necessarily one-to-one, it is possible to give a set of necessary conditions for conjugacy; no meaningful sufficient conditions, however, are known.
For example, the set of fixed points of S has to be topologically equivalent to those of T. The same must hold for the set of periodic points, i.e., points such that the nth power of the transformation returns the point to its original position. The attractive and repellent fixed points must correspond, etc. These conditions are known from the corresponding study of homeomorphisms. For many-to-one transformations one may generalize these conditions by considering the tree of a point. For a given transformation T we define the tree of a point P as the smallest set Z of points such that: a) P belongs to Z. b) If a point Q belongs to Z, then T(Q) belong to Z. c) If Q belongs to Z, then all points of the form T-1 (Q) belong to Z.
Obviously, for two transformations to be conjugate, the trees of corresponding points must be combinatorially equivalent and, in addition, their topological interrelations must be the same.**
The present study was initiated several years ago2 with the consideration of certain homogeneous, quadratic transformations which we called binary reaction systems. A typical example is the following: x1 = x2 + 2x132 , I = 2x1X3 + 2X2X3, (1) 2 X3 - X1 ,
* Here and throughout the paper a primed variable always represents the value obtained on the next iterative step. In a more explicit notation, the above equation would read: x( n+ l) = f(x(n)). ** One-dimensional transformations are considered in more detail in Appendix I.
where we consider initial points P with coordinates xl,x2,X3 satisfying: O < Xi < 1, x + x2+x3= 1 . (2) Since xI + x2 + x3=(Xl +x 2 +x3)2
the transformation (1) maps the two-dimensional region (2) into some sub-region of itself. The choice of these transformations was motivated by certain physical and biophysical considerations. For example, the set of equations (1) could be interpreted as determining the composition of a hypothetical population whose individuals are of three types, conventionally labeled 1, 2, and 3. The xi would then represent the fraction of the total population which consists of individuals of type "i." The transformation can be thought of as a mathematical transcription of the mating rule:
type 2 and type 2 produce type 1 , type 3 and type 3 produce type 1 , type I and type 2 produce type , (3) type I and type 3 produce type 2, type 2 and type 3 produce type 2, type 1 and type 1 produce type 3 .
For any assigned initial composition, i.e., any initial vector (x1 , x2, x3 ) satisfying (2), we may then ask: What is the final (or limiting) composition of the population after infinitely many "generations," that is, after infinitely many matings according to the scheme (3)? In the present context, a mating rule can be defined as a system of three non-linear first-order difference equations of the form: x1= fi(x1,X 2,X 3), x2 = f2(xl, 2, x3), (4) X3= f3 (Xl, x2, x3)
where each fi is the sum of some subset of the six homogeneous monomials x2, x2 , x 3, 2x1X2, 21 Xl3 , 2x2x3, and each such term must belong to one and only one fi. Two transformations are called equivalent if they are conjugate under the (linear) transformation defined by a given permutation of the indices 1,2,3. (This is the only linear homeomorphism which preserves the homogeneous quadratic character of the transformation.) Under this definition of equivalence, it turns out that there are 97 inequivalent transformations of the above type. It
quickly becomes apparent that, despite their formal simplicity, these transformations are very difficult to study analytically, particularly if one is interested in their iterative properties. For example, for most initial points in the region of definition, the sequence of iterates generated by repeated application of the transformation given by equation (1) converges to a set of three points: P2 = T(pl) , p3 = T(p 2) , (5) P1 = T(p3)
Using a standard terminology to be explained in detail below, we say that the "limit set" is a "period of order three." It is clear by inspection of transformation (1) that another limit set exists; if we write pi = (XI = 1, x2 = X3 = 0), P2 = (XI = X2 =0, X3 = 1), then P2 = T(pi), pi = T(p2) (6) In addition there is the algebraic fixed point of (1): p = T(p) . (7) The general initial vector, however, always leads to (5). Certain other quadratic transformations show an even more complicated behavior.
An example is the transformation: x1= x2+ x3 + 2X1X2, x2 = X12+ 2x2x3, x3 = 2xx3 (8)
This bears a close formal relationship to (1); in fact, they differ only by the exchange of a single term. The limit sets, however, are quite different. Transformation (8) has an attractive fixed point with coordinates: 1 = , x3 . (9) 31=2, 2- 4 '3= 4 (9)
It also has a limit set of the type (6) with pi = (1, 0, 0), P2 = (0, 1,0). In this case, both limit sets are observed. It is found experimentally that the set of initial points leading to (9) is separated from those leading to the oscillatory limiting behavior (6) by a closed curve surrounding the fixed point (figure 2 of chapter 10). The analytical nature of this boundary curve remains unknown.
In view of the complicated behavior exhibited by these examples, we felt it would be useful to study these transformations numerically,
making use of the powerful computational aid afforded by electronic computing machines. From one point of view our present paper may be looked on as an introduction, through our special problems, to modern techniques in experimental mathematics with the electronic computer as an essential tool. Over the past decade these machines have been extensively employed in solution of otherwise intractable problems arising in the physical sciences. In addition to solving the particular practical problem under consideration, this work has in some cases resulted in significant theoretical advances. Correspondingly, attempts to solve difficult physical problems have led to considerable improvements in the logical and technical design of computers themselves. In contrast, the use of electronic computers in pure mathematics has been relatively rare.* This may be partly due to a certain natural conservatism; in our opinion, however, the neglect of this important new research tool by many mathematicians is due simply to lack of information. In other words, the average mathematician does not yet realize what computers can do. It is our hope that the present paper will help to demonstrate the effectiveness of high-speed computational techniques
in dealing with at least one class of difficult mathematical problems. With this end in mind, we have devoted the first section of our paper to a brief discussion of how computing machines can be used to study problems in pure mathematics. Much of this section is introductory in character, and is meant primarily for those readers who have had no firsthand experience in the use of computers. It also includes, however, a description of the numerical techniques used in this study; these may be of interest even to seasoned practitioners.
After our study of quadratic transformations in three variables,** we decided to investigate the iterative properties of other classes of polynomial transformations. As a natural generalization of the quadratics described above, we consider transformations of the form: xi -fi(x,...,Xk) (i = to k), (10) where the fi are disjoint sums of the homogeneous monomials which arise on expanding the expression: / k\ m F - xi (11) i=l
* Perhaps the greatest computational effort has been expended on problems in number theory. See refs. 2 and 5. ** We shall not discuss this work here. Full details are contained in the above references. That report contains, in addition, some fragmentary results on a few particular quadratic transformations in higher dimensional spaces.
The number of such terms, each taken with its full multinomial coefficient, is Nm ().m + k- )(12) By construction, kY,fi=F ,i=l so that if we take k xi= 1, xi > 0, (13) i=l
the (additive) normalization of the xi is preserved. We are then dealing with positive transformations in a bounded portion of the Euclidean space of k - 1 dimensions, i.e., just the hyperplane defined by (13). If m = 2, k = 3, these transformations are the 97 quadratics in three variables introduced above. The bulk of the present paper is devoted to the case m = k = 3, i.e., cubic transformations in three variables; there are 9370 independent transformations of this form. We have also examined the 34337 quadratic transformations in four variables, but our analysis of the results is not yet complete (January, 1963); for this case (m = 2, k = 4) we include only some statistical observations and a few interesting examples. These three cases-m = 2, k = 3; m 2, k = 4; m = 3, k = 3--are the only ones for which an exhaustive survey is at present feasible. For other values of m and k the number of transformations to be studied is much too large.
The determination of the exact number Tkm of inequivalent transformations for arbitrary m and k is an unsolved combinatorial problem. It can, of course, be reduced to enumerating those transformations which are invariant under one or more operations of the symmetric group on the k indices, but no convenient way of doing this is known. The problem, however, is not of much practical significance. A lower limit T*m to the number Tk of inequivalent transformations is given by: TkF = Sk, (14)
where Sj is the Stirling number of the second kind. S, is also the number of ways of putting i objects in j identical boxes, no box being left empty. This underestimates Tk by assuming in effect that each transformation has k! non-identical copies, i.e., that no transformation is invariant under any permutation (except the identity). The following table illustrates the trend:
The Tk were obtained by direct enumeration-using, of course, all known shortcuts. For m = 2, k = 4, this enumeration was actually performed on a computer. In view of the huge values of the Tk'm in the lower half of this table, it is unlikely that anyone will be interested in attempting a comprehensive numerical study of these transformations for values of m and k larger than those we have considered.
A general discussion of our results for the cubics in three variables and the quadratics in four variables is given in section II; the reader will also find there formal definitions of a few basic concepts and an explanation of the special terminology employed throughout the paper. Perhaps the most interesting result of this study is our discovery of limit sets of an extremely "pathological" appearance. The existence of such limit sets was quite unexpected,*-and is indeed rather surprising in view of the essential simplicity of the generating transformations. Sections III and IV are concerned with the effect--on the iterative properties of our transformations-of two types of structural generalization. Specifically, in section III we consider the one-parameter generalization-called by us the "At-modification"-which consists in replacing equation (10) by: i = (1- At)Xi + tfi(xl,... ,Xk) (i = I to k), 0 < At < 1 . (12a)
This generalization has the special property of leaving the fixed points of the transformation invariant, although their character-i.e., whether they are attractive or repellent-may be altered. The detailed
* Quadratic transformations in three variables apparently do not exhibit similar pathologies.
discussion of the behavior of such transformations under variations of the parameter At is limited to the cubic case.
Section IV describes the result of introducing small variations in the coefficients of the monomials which make up the various fi. Again we deal only with the cubic case, and indeed only with a few interesting examples chosen from our basic set of 9370 transformations. Let us denote the Nk monomials (e.g., x3 , 3x2x2,6x1x2x3,...) in the expansion of (11) by the symbol Mj, j = 1 to Nk. The assignment of a particular index to a particular monomial is arbitrary.
Then we have k fi= E dijMj,<i<k, (13a) j=l with dij = 1 or 0, (14a) k E i= 1. (15) i=l
The generalization then consists in relaxing the restriction (14). If this were done subject only to the condition that the dij all be nonnegative, we should be dealing with a (k - 1)Nk parameter family of positive, bounded, homogeneous polynomial transformations. At present nothing significant can be said about this class as a whole. As explained in section IV, our procedure has been to study one-parameter families of transformations which are in a certain sense "close" to some particular transformation of our original set.*
In section V we give a brief, heuristic discussion of the connection between our transformations-which are really first-order non-linear difference equations--and differential equations in the plane. Our conclusion is that the connection is not, in fact, very close, and that the techniques so far developed for treating non-linear differential equations do not seem suitable for handling the problems discussed in this paper.
* Some analogous but rather unsystematic investigations were carried out on quadratics in three variables, and are contained in the report cited in ref. 2. Subsequent to the appearance of that report we made some studies (unpublished) on quadratics with randomly chosen positive coefficients satisfying (15). For quadratics (at least in three variables), the conclusion seems to be that such randomly chosen transformations are most likely to lead under iteration to simple convergence for almost all initial points.
The final section of our main text-section VI--contains a description of a class of piece-wise linear transformations on the unit square. These transformations exhibit interesting analogies with our polynomial transformations in three variables. Relatively little work has been done on this "two-dimensional broken linear" case, but the preliminary results we report seem to indicate that a detailed study might prove worthwhile.
There are two appendices: Appendix I is largely devoted to an extended discussion of certain non-linear transformations in one dimension, on the unit interval. Some of these are special cases of our cubics in three variables; others originated independently of our principal study. It is perhaps rather surprising how little can be said theoretically even about this simple one-dimensional case. It turns out that some of the same phenomena are observed in one dimension as are found in the plane-e.g., the apparently discontinuous behavior of limit sets as a function of a monotonically varying parameter. Of course, the repeated iteration of a one-dimensional transformation is a much simpler matter than the corresponding process in several dimensions. However, as we soon discovered, great care must be taken to avoid the phenomenon of "spurious convergence." This point is discussed in some detail and a few-rather alarming-examples are given.
Appendix II contains the bulk of the photographic evidence- including the "pathology" of the limit sets-on which the discussion of sections III and IV is based. These pictures, together with others scattered throughout the main body of the text, constitute in a sense the unique contribution of this paper. In retrospect, it seems unlikely that our investigation could have been successfully carried out without the visual aid afforded by the oscilloscope and the polaroid camera. Put in the simplest terms, unless one knows precisely what one is looking for, mere lists of numbers are essentially useless. Automatic plotting devices however, such as the oscilloscope, allow one to tell at a glance what is happening. Very often the picture itself will suggest some change in the course of the investigation-for example, the variation of some hitherto neglected parameter. The indicated modification can often be effected in a few seconds and the result observed on the spot.*
Visual display is of very great value when one is in effect studying sets of points in the plane; when one passes to three dimensions automatic plotting ceases to be merely a convenience and becomes essential. * This interaction of man and computing machine has sometimes been referred to as "synergesis."3
A glance at our pictures of three-dimensional limit sets--the result of iterating certain quadratic transformations in four variables-should convince even the most skeptical reader. In our opinion, it would be virtually impossible to make sense out of a mere numerical listing of coordinates of the points plotted in these photographs.
Of the many who have helped with this work, there are three to whom we are particularly indebted: Cerda Evans, Verna Gardiner, and Dorothy Williamson. These ladies did the actual coding and supervised all the machine calculations. Without their help this paper could not have been written.