α DOMAIN OF TWO-DIMENSIONAL Fig. 1. The restrictions 0 < x; ≤ 1 (i = + (0,1,0) X2 of them good; it was the collaborator's job to fill in the details. Stan was often of great help here with suggestions on how to evade difficulties, but he himself would not work out anything that required more than a few lines of calculation. In the late 1940s C. J. Everett and Stan wrote three brilliant papers on branching processes in n dimensions- -a technical tour de force. I recently asked Everett how he and Stan had worked together on those papers. Everett's reply was succinct: “Ulam told me what to do, and I did it." In my case collaboration with Stan usually involved a third person. I had given up programming after having had my fill of it during the first three years at Los Alamos. (In the last four years I have had to take it up again.) Among those who did my coding from time to time were Bob Bivins, Cerda Evans, Verna Gardiner, Mary Menzel, Dorothy Williamson, and in particular Myron Stein, who collaborated with me for many years until the pressure of his own work made it impossible. The study Stan and I made of quadratic transformations used the programming skills of Mary Menzel; the results appeared in 1959 as "Quadratic Transformations, Part I"-there never was a Part II-under all three names. The computations were done on the Laboratory's own computer, MANIAC II (now defunct). In the following section I will describe that study in some detail; it will then be unnecessary to say much about the mechanical aspects of our later (and more exciting) generalization to cubic maps, since the underlying assumptions were the same. Quadratic Transformations à la Stein-Ulam Consider three variables x1, x2, and x3 restricted as follows: 0≤ x ≤1, i = 1,2,3 and X1 + x2 + x3 = 1. (8) These restrictions limit the variables to the two-dimensional domain shown in Fig. 1a. If we multiply out (x1+x2+x3)2, we get the six terms x2, x2, x3, 2x1x2, 2x1x3, and 2x2x3. We distribute these six terms among three nonidentical boxes, no box remaining empty. (The boxes correspond to the transformed variables x1, x2, and x3.) This distribution can be done in many ways, in fact, in 540 ways. (The distribution (4,1,1), that is, the distribution such that the first box contains four terms and the second and third boxes each contain one term, can be done in thirty ways, as can the distributions (1,4,1) and (1,1,4); the distributions (3,2,1), (3,1,2), (1,3,2), (1,2,3), (2,1,3), and (2,3,1) each in sixty ways; and the distribution (2,2,2) in ninety.) Let us choose the distribution (3,2,1) to construct an example of a quadratic map. We take three terms, say xỉ, 2x1x2, and 2x2x3, and form their sum; then we sum two other terms, say x2 and x3, leaving the term 2x1x3 to stand alone. The corresponding map is given by the equations new x's back into the right side of Eq. 9 ad infinitum. Biology has not quite disappeared from the problem. If the x's are interpreted as population fractions, Eq. 9 represents the evolution of a population containing three types of individuals randomly mating according to the following rule: mating between types 1 and 1, 1 and 2, and 2 and 3 produces type 1; and mating between types 1 and 3 produces type 3. One could also write this rule as a table or a matrix, forms that are more revealing of the algebraic and group properties of the transformation. Note that if we add up the three rows of Eq. 9, we get x{ + x2 +x3 = (x1 + x2+x3)2, which equals unity because of Eq. 8. Thus the normalization is preserved algebraically. Nevertheless, in carrying out the iterations on MANIAC II we found that D, the sum of the computed x's, could be slightly different from unity because of roundoff. Therefore it was necessary to renormalize after each iteration as follows: x/D →x for all i. The "fixed points" of a transformation (more precisely the "first-order fixed points") are points that remain unchanged under iteration; they are solutions to the equations obtained by removing the primes on the equations defining the transformation. The fixed points for the map given by Eq. 9 are easily determined. First note that x3 = 2x1x3 (obtained from the third row of Eq. 9) implies that x3 = 0 or x1 = . These possibilities, together with x1 = x2 + 2x1x2 + 2x2x3 (obtained from the first row of Eq. 9) and the restriction x1 + x2+x3 = 1, lead to two "nodal" fixed points, (1,0,0) and (0,1,0), and one "internal" fixed point, (, (2 - √2), √2). How does the map given by Eq. 9 behave under iteration? Experimentally, if we choose an initial point (x1, x2, x3) at random, it is highly probable that the successive iterates will converge to the map's internal fixed point. For some initial points, including those such that x3 = 0 and x1 70, the iterates converge to the nodal fixed point (1,0,0). (The other nodal fixed point is nonattractive: iterates diverge from (0,1,0) no matter how close to that point an initial point may be.) So this map has two attractive limit sets, or attractors, each characterized by its "basin of attraction" (the set of initial points that iterate to the attractor). As mentioned above, there are many more maps of the present kind, which we called binary reaction systems. Fortunately, we needed to examine only those that are inequivalent, that is, those that cannot be transformed into each other by some permutation of the indices on the x, 's and the x's (the order of the rows clearly does not matter). It turns out that precisely 97 of the possible 540 maps are inequivalent according to this criterion. The fixed points of all the inequivalent maps were worked out by hand (Stan himself verified some of those calculations), and their limiting behavior under iteration from several randomly chosen initial points was examined numerically. The latter was a very slow process in 1958: MANIAC II could perform only about fifty such iterations per second. Of course, MANIAC II was a stand-alone "dedicated" machine, and that helped make up for its lack of speed. For more convenient graphic display of the results, we arbitrarily introduced two new variables DEPENDENCE OF LIMIT SET ON Fig. 2. A few of our two-dimensional quadratic (0,0) (1,0) (1 + a2 − 352) − a + S + 3aS = a' = ' = — (1 + S2 – 3a2) + a − S − as THREE-DIMENSIONAL QUADRATIC The domain of these new variables is an isosceles triangle in the S, a plane, with unit base and half-unit height (Fig. 1b). Note that the vertices of this "reference triangle" correspond to the nodal points of the original domain. What we found was less than overwhelming. One transformation had an internal periodic limit set of order 3 (that is, its limit set consisted of three internal points traversed in a certain order), four had internal periods of order 2, one showed no limiting behavior at all, and one converged to an internal fixed point as, where r is the distance of the iterate from the fixed point. In addition, a few maps had a "separatrix" (Fig. 2); that is, they showed one of two limiting behaviors (usually convergence to a fixed point or to a periodic limit set of order 2) depending on the location of the initial point. Everything else converged to a fixed point (not necessarily internal) or had nodal periods of order 2 or 3. The interested reader will find a description of the many generalizations we tried in Menzel, Stein, and Ulam 1959. Cubic Maps and Chaos Although some interesting facts emerged from the study described above, Stan and I were disappointed at the lack of variety in the limiting behavior we observed. We even tried to enliven the situation by generalizing the generic map to the form x = d; 1 x2 + d;2 x2 + d;3 x3 + 2d;4 x1x2 + 2dis x1x3 + 2d;6 x2x3, i = 1,2,3, = with the coefficients randomly chosen but restricted by 0 < dij ≤ 1 for all i,j and What to do? Stan and I had, simultaneously, the idea of looking at three-variable cubic maps of the same structure as our quadratics. That is, we would distribute the ten terms arising from expansion of (x1+x2+x3)3 among three boxes and construct the maps in the same way as before. A short calculation (see pp. 7-8 of Stein and Ulam 1964) showed that there were more than 9330 inequivalent maps of this type. (The Fig. 4. exact number turned out to be 9370, arrived at by a more complicated combinatorial calculation.) Perhaps among this plethora of possibilities we would find some systems that showed truly unexpected limiting behavior. I am happy to say that the results far exceeded our expectations. We also considered transformation in three dimensions, specifically quadratics in four variables with x1 + x2 + x3 + x4 = 1. But 34,337 of these are inequivalent (not an easy fact to come by), so we were never able to give them the attention they deserved. (Figure 3 gives a glimpse of some interesting cases.) Unless someone writes a fast program to evaluate automatically the amusement value of limit sets, that is as far as such studies will ever go: the case that comes next (when ranked by the number of inequivalent maps) is that of quartics in three variables, and more than 3,275,101 of these are inequivalent (the exact number is unknown). Returning to our study of cubic maps, we plotted the sets of points obtained by iteration on an oscilloscope screen in the reference triangle of Fig. 1b. "Hard copy" was obtained directly from the screen with a Polaroid camera mounted on the oscilloscope. This method, in addition to being cheaper, was more convenient than the current method, which involves a $20,000 Tektronix terminal with a hard-copy device. There is not enough space to give all the details of what we found; an extensive summary is given in Stein and Ulam 1964, and Figs. 4-7 show some interesting Fig. 5. The two-dimensional cubic map defined by the given equations iterates to an infinite limit set composing the closed curve shown in (a). (Whether the words "infinite" and "curve" can be applied here in the strict mathematical sense is not known.) When this map is iterated from some point p in the limit set, successive iterates do not trace out the curve in an orderly fashion. However, the 71st, 142nd, 213th,..., (71n)th, ... iterates of p, which are plotted in (b), do lie close to each other and trace out the curve in a clockwise direction. Various stages in the iteration of this map are featured in the art work on the opening page of the article. The first image (counted from background to foreground) shows the set of points at which the iterations were begun, namely twenty-one points uniformly distributed along a line segment whose midpoint is coincident with the nonattractive fixed point of the transformation. (The horizontal and vertical coordinates of this fixed point are approximately 0.6149 and 0.1944, respectively.) The second and third images, which are superpositions of the 8th through 15th and the 15th through 22nd sets of iterates, respectively, capture the dynamics of these early iterations. The final image, a superposition of the 1800th through 2700th sets of iterates (and the same as that in (a) here), shows the stable pattern to which the sets of iterates converge. examples of limiting behavior. Again, a large majority of the transformations converged to fixed points or to periodic limit sets (some of quite high order). Of most interest to us, however, were 334 transformations that exhibited no periodic limiting behavior, suggesting that their limit sets contained infinite numbers of points. Some of these appeared to be closed curves or sets of closed curves, although to this day not one has been shown to satisfy the mathematical criteria for a curve. Others bore a striking resemblance to the night sky; at the time these strange limit sets were commonly referred to as messes. The transformation that iterated to the mess shown in Fig. 8 was studied in great detail and received the special name TA. For the record I give its definition here, both in x; and S, a coordinates. |