Page images
PDF
EPUB

a

DOMAIN OF TWO-DIMENSIONAL
MAPS

Fig. 1. The restrictions 0 ≤ x ≤ 1 (i =
1, 2, 3) and x = 1 limit the domain of the
xi's, and of the iterates of the two-dimensional
quadratic and cubic maps discussed in the
text, to the equilateral triangle shown in (a).
For more convenient graphic display of the
iterates, we introduced the variables S = {(1
X1 X3) and a = 1x2 = (1 − x1 — X3). These
new variables, and the iterates of the maps,
are limited (by the restrictions on the x¡'s) to
the isosceles triangle shown in (b).

+

[merged small][merged small][merged small][merged small][merged small][merged small][merged small][ocr errors][merged small][merged small][merged small]

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:

and

0≤ x ≤1, i = 1,2,3

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 x, x2, and x.) 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 x2, 2x1.x2, 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

[blocks in formation]
[ocr errors][merged small][merged small]

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 0, 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

[merged small][ocr errors][merged small][ocr errors][merged small][merged small]

DEPENDENCE OF LIMIT SET ON
INITIAL POINT OF ITERATION

Fig. 2. A few of our two-dimensional quadratic maps exhibited one of two limiting behaviors under iteration, depending on the location of the initial point. For example, the map defined by the equations below (in both x, and S, a coordinates) iterates to an internal fixed point (So= 0.62448516, ao = 0.09239627) from any initial point within the dark gray region of the reference triangle and to a nodal period of order 3 ((0,0) → (1⁄2, 1⁄2) → (1, 0)) from any initial point within any of the three light gray regions. The "separatrix" demarcating the basins of attraction of the two limit sets was determined experimentally.

[merged small][merged small][merged small][ocr errors][graphic][merged small][subsumed][merged small][merged small][merged small][merged small][merged small]

THREE-DIMENSIONAL QUADRATIC
MAPS WITH INFINITE LIMIT SETS
Fig. 3. The limit sets of a small fraction of
our quadratic transformations in four variables
contain what appear to be infinite numbers of
points. Shown below are three-dimensional
projections of four such limit sets, which were
obtained by photographing plots of succes-
sive iterates on an oscilloscope screen. The
set of axes in the center of each display indi-
cates the orientation of the limit set relative to
the viewer, who is conceived of as stationed
at a certain distance from the origin along the
X2 axis. The limit set for Ta consists of two
"curves," one in the x1, x3 plane and the other
in a plane inclined at 45° to the X1, X3 plane.
Ta evidently transforms these planes into each
other, since successive iterates lie alternately
on the two curves. The limit sets for To, TC,
and Ta are even more complicated, constitut-
ing implausibly tortuous curves in space.

Tax1 = x2 + x2 + 2x2x4

x2 = x2 + 2x1x4 +2X3 X4

x3 = x2 + 2x1x2 + 2X1 X3 x1 = 2x2x3

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;2x2 + di 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 Σ., dij 1. Of several hundred such systems investigated, almost all iterated to a fixed point; in other words, the special quadratic maps we had originally looked at were more interesting than the general case.

[merged small][graphic][graphic]
[graphic]
[graphic]

Tb: x1 = x2 + x2 + 2X3 X4

x2 = x2 + 2x1X4 + 2x2x4

x3 = x2 + 2x1 x2

X1 = 2x1x3 + 2x2X3

Tc: x1 = x2 + x2 + 2x1 x2
x2

x3 = x2 + 2x2x3

X1 = x2 + 2X1X4

= 2X1 X3 + 2X2X4 + 2X3X4

Ta : x1 = x2 + 2x1x4 + 2X2X4 x2 = x2 + x2 + 2x2x3

x3 = x2 + 2x1x2 + 2x3X4 x1 = 2X1 X3

[graphic][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed][subsumed]

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. 4. Shown in (a) is one of two possible limiting behaviors for the map defined by the given equations, namely, convergence to a "mess," an apparently infinite number of points with a complex distribution and no discernible structure. The map iterates to this messy limit set from any initial point within any of the light gray regions in (b). If, however, the initial point lies within any of the dark gray regions, the map iterates to the fixed point So= 0.6259977, ao = 0.1107896. The complicated separatrix was determined experimentally.

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.

[graphic]

Fig. 6.

TWO AMUSING INFINITE LIMIT SETS Examples of two-dimensional cubic maps with infinite limit sets constituting (a) a more irregular closed curve than that illustrated in Fig. 5 and (b) three separate closed

curves.

A PARTICULARLY FASCINATING
INFINITE LIMIT SET

Fig. 7. The infinite limit set of the two-dimensional cubic map defined here consists of seven separate subsets. Each subset is invariant under the seventh power of the transformation; that is, if p is a point in any one of the subsets, the 7th, 14th, 21st,. (7n)th, ... iterates of p are also in that subset. Shown magnified in the inset are the 7th, 14th, 21st, 2695th iterates of a point in the outlined subset of the limit set.

..."

[ocr errors]

and

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.

Ta : x{ = x3 + 3x1x3 + 3x2x3 + 3x3x2 + 6x1x2x3

x2 = x2 + x3 + 3x3x?
xz = 3x1x2 + 3x2x7

[merged small][ocr errors][ocr errors][ocr errors][merged small]

(11a)

(11b)

« PreviousContinue »