Famous L-systems of mathematical history

 

One of the great themes of nineteenth century mathematics was the collective efforts of many mathematicians to put the methods of calculus and higher analysis on a firm rigorous foundation. The bane of modern calculus students, the - definition of limits, is one of the great highlights of this efforts. With the powerful new ideas about the exact notions of ``limits'' and ``continuity,'' mathematicians were at last able to explore entirely new kinds of geometric objects.

A pioneering study of the nature of sets and real numbers was undertaken by Georg Cantor in the last half of the nineteenth century. Although the idea of real numbers as infinite decimal expansions had existed for some time before Cantor, Cantor was the first to realize some of the surprising implications presented by this idea. Perhaps his most famous argument is the simple observation that given any enumeration of real numbers in decimal form, say:

where each is an integer and each is a digit from 0 to 9, we can always find a real number not on the list by choosing to be a different digit from (and 9, to avoid numbers that end in all 9's). This diagonal argument proves that the set of real numbers are uncountable. It was at one time a bitter pill for philosophers to accept that there were irrational numbers; Cantor's argument shows much more. In any definable sense, the vast majority of numbers are not rational, nor even algebraic (solutions of polynomial equations with rational coefficients).

This shift in mathematical philosophy, although it seems almost devoid of controversy today, is similar to the transformation that has taken place in dynamics over the past several decades. The predictable smoothly varying long-term behavior that was so highly prized before is now known to be the exception rather than the rule. The limiting geometry and dynamics is far more likely to be fractal or chaotic in nature. We will return to this theme later in the course.

Cantor's manipulation of decimal expansions reflects a perception of digit expansions as a symbolic dynamical system. The symbolic states are simply the digits 0 through 9. A decimal expansion is a listing of the states over each generation; the number itself is the behavior of the dynamical system. This idea suggests all kinds of curious things to consider. Cantor formulated a particularly interesting set based on restricting the ``symbolic dynamical systems'' of digit expansions. We need to make a slight variation from our usual system of expansion. Since there is nothing sacred about the use of the base 10, we can also work with expansions to other bases, particularly base 3. In base 3, there are exactly three digits 0, 1, and 2. A digit expansion of a number (called a ternary expansion) takes the usual form

where each digit is 0, 1, or 2. The actual number is composed of powers of 3 (instead of powers of 10) as a series:

Cantor defined a set C to consist of all numbers with a ternary expansion that used only 0's and 2's but no 1's. An expansion that ended with all 2's is allowed in C. The diagonal argument can be used to show that C is again uncountable, and therefore in that sense is has a great many points. However, as we shall see, it appears as a wispy smattering of points in line, with no length in any sense.

To ``plot'' the Cantor set, we shall consider only those points in the unit interval [0,1]. Considering the first digit, points beginning with do not occur in C, with two exceptions. The endpoints and have at least one possible expansion in all 0's and 2's and so belong to C. Thus, in trying to carve out C, we must first cut away the middle third of the interval (1/3,2/3). When we consider the second digit, we must also eliminate expansions beginning and . These correspond to the middle thirds of the remaining intervals (1/9,2/9) and (7/9,8/9). This process of cutting out middle thirds continues indefinitely. The residue that's left over is the Cantor set.

It turns out that this process can be described by a very simple L-system (called CantorDust in FRACTINT):

Axiom F
F=FGF
G=GGG

The angle is irrelevant in this case. We begin with a straight line segment F and replace it by a pattern of draw one step, move a second step, and draw the third step. This carries out the carving of the middle thirds. The sequence of the generations is shown below.

  
Figure 15: Generations of the Cantor L-system

The dust-like limit at the end is hardly impressive; yet, this kind of dusty distribution appears throughout nature, for instance, the clumpy distribution of matter in the universe. Mandelbrot calls this kind of geometric object fractal dust.

Since Euclid, the distinctions between points, lines and planes had seemed intuitively clear. With the description of the Cantor set, Cantor had raised a dusty cloud that was neither pointlike nor much like a line. Cantor next turned his attention to the difference between a line and a plane. For twenty years Cantor strove to prove that there were in some sense far more points in the plane than there are in the line. It was a shock to himself and to the world to find that this was untrue. The truth comes from again a kind of symbolic dynamical approach. Any pair of digit expansions

can be threaded together to form a single expansion

and conversely any single digit expansion may be unthreaded into a pair of digit expansions. This idea (with a little elaboration) proves that the points in and may be placed in one-to-one correspondence. Cantor had already accepted the idea of ``one-to-one correspondence'' as the means for deciding when two infinite sets had the same number of elements.

This mapping between and is highly artificial in the sense that points which are near one another in may be unthreaded into two points in which are not close to one another. That is to say, Cantor's correspondence is not continuous. There remained the question of whether or not there is a mapping which satisfies all the following conditions:

1. f is one-to-one, meaning that if then .
2. f is onto, meaning that every point in may be expressed as f(x) for some point x in .
3. f is continuous (in the notation of the calculus, this would be written

   

4. The inverse mapping is continuous.

It was widely believed that this was impossible, until the world was again shaken by the discovery by Peano of a mapping that is continuous and onto! A continuous mapping from the unit interval into the plane is generally thought of as a curve. Thus, Peano's example is known as a area-filling or space-filling curve. Similar constructions can produce curves that fill any finite-dimensional cube . The underlying idea is dynamical in nature; Peano's construction can be achieved by an L-system, and the three examples Peano1-3 in FRACTINT are three variations of the construction. We shall discuss the original and ``dullest'' version (Mandelbrot's term in [Man83]).

Peano1 { ; Adrian Mariano
; from The Fractal Geometry of Nature by Mandelbrot
Angle 4
Axiom F-F-F-F
F=F-F+F+F+F-F-F-F+F }

The starting configuration is a square. We may think of the first generation of our mapping as mapping the unit interval as imply as possible on this square, in particular, is the bottom side, is the right side, is the top side, and is the left side.

Each side of the previous configuration is replaced by a nine segment configuration shown in this figure. This figure also shows the path of the curve by rounding the corners. The quarter-interval that was mapped to the original segment may now be divided into nine equal subintervals, and each of these ninths is mapped in the simplest way to the corresponding segment in the generating pattern. Stitching all these segments together gives a second continuous mapping . Continuing this process, we obtain a sequence of continuous functions that converge uniformly to a continuous function . The image of the limit function is a solid square. Generation 2 is shown in this figure. Without making the paths clear, the images of later generations are not very informative, since they depict only successively finer tilings by squares. Some curved versions are shown in [Man83].

  
Figure 16: Peano production rule

  
Figure 17: Second generation Peano curve

With the discovery of the Peano curves, the question of whether or not there was a function satisfying properties 1-4 above (such a map is called a homeomorphism) became more precarious. The final answer that this is impossible was provided by Brouwer in the early twentieth century and is based on some subtle mathematics that finally established the rigorous notion of topological dimension. For more information about Cantor's part in this story, the reader may consult the informative account of Cantor's life and work in [Dun90].