Fractal Tilings Derived from Complex Bases Sara Hagey; Judith Palagallo The Mathematical Gazette, Vol. 85, No. 503. (Jul., 2001), pp. 194-201. Stable URL: http://links.jstor.org/sici?sici=0025-5572%28200107%292%3A85%3A503%3C194%3AFTDFCB%3E2.0.CO%3B2-Y The Mathematical Gazette is currently published by The Mathematical Association.
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at http://www.jstor.org/journals/mathas.html. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission.
The JSTOR Archive is a trusted digital repository providing for long-term preservation and access to leading academic journals and scholarly literature from around the world. The Archive is supported by libraries, scholarly societies, publishers, and foundations. It is an initiative of JSTOR, a not-for-profit organization with a mission to help the scholarly community take advantage of advances in technology. For more information regarding JSTOR, please contact
[email protected].
http://www.jstor.org Sun Dec 16 05:57:25 2007
194
THE MATHEMATICAL GAZETTE
Fractal tilings derived from complex bases SARA HAGEY and JUDITH PALAGALLO* Tilings have appeared in human activities since prehistoric times. The mathematical theory of tilings contains a rich supply of interesting and sometimes surprising facts as well as many challenging problems. A vast literature exists on the subject of tiling, and almost every imaginable variant of the question 'How can a space be tiled by replicas of a set?' has been discussed. Figure 1 shows a tiling of a portion of the plane where each tile is of the same size and shape and has a fractal boundary.
FIGURE 1: Tiling of the plane
If we consider the plane to be the set of complex numbers, then such a tiling represents a separation of the complex numbers into distinct classes. We demonstrate a straightforward way to generate such fractal tilings. Then we explain how a particular tiling represents a specific radix expansion of the complex numbers. Generating the tilings
In this paper, all tilings will be generated from 2 x 2 integer matrices of the form
*
Research was supported by Faculty Research Grant #1997-12 from The University of Akron.
FRACTAL TILINGS DERIVED FROM COMPLEX BASES
195
The method to generate a tiling of the plane is best introduced with an example. Example
D
=
I : Set M
{ (( )
Specifically, for z
=
(-; I: )
with m
Define the mappings fj(z)
= =
det M
5
+ M-I
=
2.
Choose
(z) for r,
E
D.
=
Initiate the iteration process by randomly choosing any point zo in the plane and evaluating the two functions above at the point. Then choose recursively and randomly z, E (fl (2,- I ) , f2(zn- ,)), for n = 1, 2, 3, ... After a few iterations, say n 2 100, the generated points lie near the tiling. Figure 2 (the well-known twin dragon [I]) shows the result of several thousand iterations. The algorithm for generating the tiling is based on Barnsley's Random Iteration Algorithm [2]. Classical fractals such as the Cantor set (1883), the Koch curve (1904) and the Sierpinski triangle (1915) can be constructed using the same algorithm.
FIGURE 2: Twin dragon
Figure 2 shows two twin dragon tiles with the location of the points (0, O), (-1, O), (0, I), (1,O) and (0, -1) clearly marked. It is of special significance to the remainder of this paper that each tile contains exactly one ordered pair of integers. We will explain why we are restricting our choice of matrices to those of the form (1) and will also discuss the role of the set D in the construction of the tilings. Finally, we will relate the tilings to radix expansions of the complex numbers found in each tile.
196
THE MATHEMATICAL GAZETTE
Choosing the matrix M In order to use an integer 2 x 2 matrix M to generate a tiling of the plane, M must be an expanding matrix, that is one with all eigenvalues 1 Ai ( > 1. A property of expanding matrices is that for some k > 0. (M-I? is a contraction ma ping. Suppose that M is an expanding 2 x 2 integer matrix with / det M y = m and that D = { r , , r?. . . . . r,.,}. ( A discussion of the careful selection of the members of set D will follow.) Then there is a unique non-empty compact set T such that T = uj'i M-' ( T + ri). r . E D. More precisely, T is the attractor of the iterated function system ) = M ( + ) j = 1. .. . . m } . If we apply the expanding matrix M to the set T, M ( T ) = u;"=1 ( T + r,) = T + D. Geometrically, the dilated set M ( T ) is perfectly tiled by the m translates T, = T + rj of T . I n the previous example, T is the left 'dragon' and M ( T ) = T + D, for D = {(o, 01, (1, 011. Matrices of the form given in (1) are expanding matrices and, therefore. can be used to generate tilings of the plane with fractal boundaries. ( [ 3 ]has a complete discussion of tilings of the plane with fractal boundaries. A geometric way to choose the set D is also explained.) In fact, any matrix M of the form given in (1) is a similariv mapping: i.e. if z is any point in the plane, 1 Mz 1' = m' 1 z2 1. where m = / det M 1. Figure 2 is an example of a similurih tiling, one that is composed of smaller tiles (rep tiles) of the same size, each having the same shape as the whole. In general, since the figure would be composed of nl tiles (m = 2 in our case), the tiles are referred to as m-rep tiles. The boundary of the twin dragon was studied by Mandelbrot [ l ] and he showed that the distance along the boundary between any two points is always infinite.
,
The radix representations of numbers Before addressing the question of selecting members of set D, we will discuss the radix representation of complex numbers. First, we will review some basic facts about radix representations of numbers. A real number x can be represented in any integer base b > I using digits 0, 1, 2, . . . , h - I and has the representation x = C:!, _ c,hl. , The numbers c, are called the digits of the representation. For centuries, the decimal number system reigned supreme. The advent of digital computers brought the binary and octal systems into the limelight. For example, we can write -
(7.125),,,= 111~0012 and ( 1 2 , 2 ) 1 0 = 1100~00112, where the digits under the bar are repeated indefinitely. Representing numbers using positional number systems has a long history. Well-known mathematicians such as Fibonacci, Cauchy, Pascal, Leibniz and Bernoulli all worked on representations of numbers in different bases, including positive integer bases, bases with negative numbers, and complex numbers as bases. (A brief history of positional number systems and arithmetic operations appears in chapter 4 of [4].) The concept of base,
FRACTAL TILINGS DERIVED FROM COMPLEX BASES
197
or radix representation, can be extended to the complex numbers. A Gaussian integer, z = x + iy where x and y are real integers, is said to be expressed in the complex base b if it is written with the finite sum z = 0 crbr. In this paper we restrict the base b = p + iq to a Gaussian integer where p and q are relatively prime.
c:=
Representations of complex numbers We can define an equivalence relation on the set of Gaussian integers Z [ i ] in the following way: Two Gaussian integers zland z2 are equivalent (modulo b) if there exists a Gaussian integer c such that z , - z2 = bc. This equivalence relation separates all the Gaussian integers into tn equivalence 2 classes, where m = ( b I . In particular, if b = -a k i, the j-th equivalence class is the set Cj + bc for all c E Z[ i ] ,j = 0, ... , m - 1 ) . As an 2 example, choose b = -2 + i and m = 1 b 1 = 5. The five equivalence classes for all of the Gaussian integers, modulo b, can be written [(O, 0)l
=
( ( 0 , O), (-2, I ) , ( 2 , -11, ...
1
[ ( I , 011
=
{ ( I , 0 ) . (-2, - 1 1 , (0%31, ...
)
[(2>0)l
=
{ ( 2 >01, ( - 1 , - 1 ) . (-5, - I ) , ...
[(3, 011
=
( ( 3 , 01, ( - 2 , O ) , ( - 1 , 21, ...
I
1
I
[ ( 4 , 011 = ( ( 4 , 0 ) > ( - 1 , 01, (0, 21, ... . Clearly, we could represent each equivalence class with an integer from the set (0. 1 , ... , 4 ) . In general, for b = -n k i and rn = n2 + 1 , the m equivalence classes can be represented by the integers 0, 1, . . . m - 1. These integers are said to form a complete set of coset representatives, modulo b, of Z [ i ]I bZ [ i ] . A standard digit set is any complete set of coset representatives for Z[ i ]1 bZ [ i ] . Using positive integers for the digit sets is the most straightforward generalisation of familiar systems. Bases of the form b = -n + i play an important role in radix expansions. Gauss showed that, since the integers 0 , 1 , ... it2 form a standard digit set, any Gaussian integer z has a unique representation z = C! = 0 crbrin base b with the digits of the representation cr chosen from the set 0, 1, ... n2. The algorithms used to find the representations are extensions of those used with integer bases. Some examples of the unique representations of Gaussian integers with the base b = -1 + i are
.
(2
+
i)lo = ( 1 1 1 1 ) - , + ,
=
(-1
(5 - 3i),o = ( 1 0 1 1 1 0 ) - , + , = (-1 The reader can also verify that (-3
+
+
i)'+ (-1 and
+it + ( - 1
4i)lo = (14400)-2+ ,
+ i)'+
(-1
+
i)
+
1
+ i)' + (-1 + i12+ (-1 + i )
THE MATHEMATICAL GAZETTE
More generally, an arbitrary complex number is said to be represented ,br with each c, an allowable in base b when it is written in the form C:'=-c, digit for the base b. The digits to the left of the radix point (c,. r 2 0 ) determine the Gaussian integer co + clb + . . . +c,b", called the integer part of the expansion. Katai and Szabo [5] showed that the only Gaussian integers that can be used aa a base for all the complex numbers using positive integers as digits, are of the form -n 2 i. The representations need not be terminating or unique, even though such representations are unique for Gaussian integers. For example,
a terminating representation. However, 1 + 3i - (0.010)-,+, = (11.001)_,+, = (1110.100)-,+, 5 and
demonstrate non-terminating expansions of complex numbers. (See [6] for a more complete discussion of complex bases.) For bases not of the form -n i i even a Gaussian integer may have an expansion that never terminates. For example, using the base b = 1 - i, the expansion for -1, using only 0's and 1's as digits, never terminates, but cycles indefinitely. Complex number interpretatioiz of fractal tilings A complex number := p + iq is uniquely identified by the matrix
Complex addition and multiplication then correspond to the addition and multiplication of matrices. If a base b is of the form b = -n + i, then it corresponds to a matrix M as in (1) with det M = m = I b I*. If the base b is used with the standard digit set D = (0, 1, . . . , n 2 } ,then all complex -I numbers { z = Ck= , rkbk},form an m-rep tile that we call T. In general the tile T contains the set of all complex numbers representable with expansions that lie strictly to the right of the radix point; this tile also contains the Gaussian integer 0 + Oi = 0. All of the other m-rep tiles in = r, + T . where r, E D, are just integer translates of the tiling, the sets the tile T. Thus each of the m-rep tiles is congruent to T. (A general discussion of digit sets and tilings can be found in [7] and 181.)
FRACTAL TILINGS DERIVED FROM COMPLEX BASES
199
Furthermore, for a complex number w E T, (j # l), the representation in base b can be written as w = rj + v, where v is the congruent point in the tile T. Thus for any point in the tile Ti, the portion of the expansion which lies to the left of the radix point is the integer rj. Since rl = 0 E T, then each r, is an element of the tile T,; therefore, each tile corresponds to one integer. All of the complex numbers that lie in a specific m-rep tile share the same expansion to the left of the radix point and differ only in the portion of the expansion which lies to the right of the radix point. The iteration process, i.e. repeated multiplication by M-',is repeated division by the complex number b. As in the real case, the random iteration process generates digits which lie to the right of the radix point. Each digit of the representation is in D and is randomly determined by the choice of transformation. In the case of the twin dragon, the tiling was generated using the matrix representing the base b = -1 + i. Thus the only admissible digits are 0 and 1. Therefore, the representation of all the complex numbers would be in terms of 0's and 1's. We see that the attractor tile T is the left tile and the right tile is a translation of T. Example 2: Let b = -2 + i with m = I b l2 = 5. Let D = (0, 1, 2, 3, 4). Define the members of the iterated function system for any z in the plane by fj(2) = (j - 1) + (-2 + i)-' (2) for j = 1, ... , 5. Figure 3 is generated by iterating the functions {fj,j = 1, ... , 5) as previously described. Again note the locations (shown in black) of the integers in D, exactly one per tile.
FIGURE 3: A 5-rep tile
Complex numbers that lie in a specific 5-rep tile share the same expansion to the left of the radix point and differ only in the portion of the expansion which lies to the right of the radix point. The only allowable digits in such expansions are 0, 1,2,3, and 4. We demonstrated earlier that the expansions of complex numbers to a Gaussian integer base need not be unique. If a complex number lies on the fractal boundary of one of these tilings, then it can have two or three representations.
200
THE MATHEMATICAL GAZETTE
Non-integer digits Consider again the complex base b = -2 + i used in Example 2 but with the digit set D = (0, 1 , i , - 1 , - i ) . The members of the iterated function system for any z in the plane are given by f j ( z ) = dj + (-2 + i)-'(z), dj E D, j = 1, ... , 5. When the iteration process is performed, the tiling in Figure 4 results. Each complex number in a given tile has a representation c,br , where the digits are chosen from the set D. For example, (3 - 5i)'o = (10: )-2 + i , where 7 = -i. Figure 1 shows a portion of the plane tiled with 5-rep tiles.
c:=
FIGURE 4: Fractal cross
The method for generating fractal tilings demonstrated previously can be used with any expanding integer matrix. However, if the matrix M represents a base b that is not of the form -n i , then the tiling generated cannot be interpreted in the same manner for the complex numbers. Figure 5 shows a tiling for the base b = 1 - i. The tiles are similar to those in
*
FIGURE 5: Shifted twin dragon
FRACTAL TILINGS DERIVED FROM COMPLEX BASES
20 1
Figure 2, but are shifted in the plane. As noted earlier, the integer -1 has no k representation of the form C, = c,.br, where the digits are chosen from the set (0, 1). The iteration process for generating the tiling approximates the repeating cycles of the expansion. Tilings of the plane can be drawn even though the points in the plane do not have a representation in the base as we have defined it. Note: Many computer resources are available for generating fractals. The Random Iteration Algorithm, presented by Barnsley in [2], can be used with Visual Basic to generate pictures like those in this paper. Generating the fractals in colour presents even more dramatic pictures. References 1. B. B. Mandelbrot, Fractals: form, chance and dimension. Freeman (1977). 2. M. F. Barnsley, Fractals evepwhere, Academic Press (1993). 3. Richard Darst, J. A. Palagallo and T. E. Price, Fractal tilings in the plane, Mathematics Magazine 71 (1998) pp. 12-23. 4. D. E. Knuth, The art of computer programming, Vol. 2: seminumerical algorithms, Addison-Wesley (198 1). 5. I. Katai and J. Szabo, Canonical number systems for complex integers, Acta Sci. Math. (Szeged) 37 (1975) pp. 255-260. 6. W. J. Gilbert, Fractal geometry derived from complex bases, The Mathematical lntelligencer 4 (1982) pp. 78-86. 7. J. C. Lagarias and Y. Wang, Integral self-affine tiles in Rn, Part 11: lattice tilings, J. Fourier Analysis and Applications 3 (1997) pp. 83- 101. 8. Y. Wang, Self-affine tiles, Advances in wavelets, K. S. Lau ed., Springer (1998) pp. 261-285. SARA HAGEYand JUDITH PALAGALLO Department of Mathematics and Computer Science, University of Akron, Akron, OH 44325-4002 USA e-mail: shagey @mr.marconimed.com
[email protected] Mistakes happen -but some leave a bad odour R. C. Gupta: False mathematical eponyms and other miscredits in mathematics. Ganita-BhBrati 19, No. 1-4,11-34 (1997) The author collects 48 cases that are false mathematical eponyms or miscredits in mathematics. It includes 'the theorem of Ceva', 'Euler's formula of exp(it) = cost + i sin t ' , 'Fourier Transformation', 'Homer's Method', 'Jacobians', 'Laplace equation', 'Taylor's Series'. And so on. References are given in full. At the end the author quotes the poem of W. Shakespeare: What's in a name? That which we call a other name would smell as sweat. rose This review, which appeared in Zenrrnlblatr fur Mathematik, 922 (1999), was sent in by Ivor Grattan-Guinness.
an^
http://www.jstor.org
LINKED CITATIONS - Page 1 of 1 -
You have printed the following article: Fractal Tilings Derived from Complex Bases Sara Hagey; Judith Palagallo The Mathematical Gazette, Vol. 85, No. 503. (Jul., 2001), pp. 194-201. Stable URL: http://links.jstor.org/sici?sici=0025-5572%28200107%292%3A85%3A503%3C194%3AFTDFCB%3E2.0.CO%3B2-Y
This article references the following linked citations. If you are trying to access articles from an off-campus location, you may be required to first logon via your library web site to access JSTOR. Please visit your library's website or contact a librarian to learn about options for remote access to JSTOR.
References 3
Fractal Tilings in the Plane Richard Darst; Judith Palagallo; Thomas Price Mathematics Magazine, Vol. 71, No. 1. (Feb., 1998), pp. 12-23. Stable URL: http://links.jstor.org/sici?sici=0025-570X%28199802%2971%3A1%3C12%3AFTITP%3E2.0.CO%3B2-X
NOTE: The reference numbering from the original has been maintained in this citation list.
