2. SIERPINSKI SIEVE


Fractals

It is rather hard to define a fractal, but essentially a fractal is a geometric figure which demonstrates recursion or nesting. This means that the whole figure, or portions of it, appear infinitely within the original figure at smaller and smaller scales. The definition is often extended to include some degree of randomness. The fractal idea is sometimes illustrated with the fern: notice how the whole fern appears in miniature again and again, sometimes reflected and sometimes not. Of course, for a real fern there are only a small number of steps in the downsizing, but it does illustrate the idea.

The Sierpinski sieve (triangle, gasket) is a very simple example of a fractal, but one which has special interest. It is named after a Polish mathematician, Waclaw Sierpinski, who lived 1882 – 1969, and was one of the most influential mathematicians of his time in Poland. He has a crater of the moon named after him!



The sieve

Let’s look at the very simple construction of the Sierpinski Sieve. We start with an equilateral triangle. Join the midpoints of the sides, and eliminate the central triangle, like this. Next, eliminate the central triangle of each of the four black triangles you have obtained to get this. You get the idea. Now just keep on doing this indefinitely, and you finish up with the Sierpinski sieve.

Here is a Java applet by Bill Beaumont which beautifully illustrates the formation of the sieve. Bill was a computer scientist at Adelaide University for many years, but has now retired to Tasmania. This applet just gives the outline of the triangles on the sieve. It is a matter of definition as to whether the sieve fractal is made up of the outlines or the filled triangles.

There are two interesting questions we might ask here.

• The Java applet stops at Step 8. Why do you think this is so? Suppose the base of the initial triangle (Step 0) is represented by 400 pixels. What number of pixels represent each successively smaller sized triangle?

•  A question in the opposite direction is: Does the infinite (ideal) Sierpinski sieve actually exist at all? Think about this. For example, the infinite series 1 + 1/2 + 1/22 + 1/23 + ... is easily shown to have sum 2. But the infinite series 1 + 1/2 + 1/3 + ... has no finite sum at all. The result of carrying out an infinite number of steps is not always clear!





















# The computer screen has a large but finite number of pixels to represent a figure. Step 9 in the sieve process demands a length of less than 1, so there is no point expecting a more detailed representation than that given by Step 8.

# It can be shown, with some difficulty, that the Sierpinski sieve (and fractals in general) actually exists. That is, there is a limiting figure – even if we can’t accurately picture it on our computers!


IFS but no buts

One might think that the distinctive shape of the Sierpinski sieve comes from the shape of the original triangle. But look at this construction, starting with a square. In fact, you can start with any original figure (lying within a square) and obtain the Sierpinski sieve. The final shape appears to have more to do with the construction process than with the shape of the original object.

To make our working easier, let us switch to a right-angled Sierpinski sieve, as below. We will assume that the total sieve has side lengths 1, and that these perpendicular sides lie along the x- and y-axes. Thus the vertex right-angle lies at the origin O. Now let us think about the way this triangle is constructed. We begin with the large outline triangle.

To obtain the next step, we want to replace this large outline triangle T with three smaller subtriangles.

• What simple transformation maps the large outline triangle T to subtriangle 1? Can you describe it? Can you express it in coordinates? (Say w1(x, y) = ... .)

• Now repeat the above for a mapping to subtriangle 2, and then subtriangle 3. Use the notation w2 and w3 respectively.






















# The mappings are a dilatation (scaling) about the origin with scale factor 1/2 in the first case, and then for cases 2, 3, the scaling is followed by a translation.

# The equations of these transformations are:

w1(x, y) = (1/2.x, 1/2.y)         
w2(x, y) = (1/2.x + 1/2, 1/2.y)
w3(x, y) = (1/2.x , 1/2.y + 1/2)

Now to carry out the first step in creating the Sierpinski sieve, we want these three mappings to all happen at once, so we use the notation W(T) to denote the union of the images of triangle T under the three mappings listed above.

• Suppose T1 denotes the union W(T) of the images. What figure would be represented by
             T2 = W(T1)? T3 = W(T2)? ...

Do you see how neat this notation is? We can now write the consecutive steps of the construction of the Sierpinski sieve as

T0 = T, T1 = W(T), T2 = W(W(T)) = W2(T), T3 = W(W(W(T))) = W3(T), ... .

This is an example of an iterated function system or IFS. Other fractals can be generated in a similar way.


The chaos game

Here is a little game you can play, although you will need a computer version to get worthwhile results. We take an equilateral triangle in the plane, and label the vertices 1, 2 and 3. To play the game, you will need a die that gives just three outcomes. An easy way is to take an ordinary die, and read the (opposite) 1, 6 faces as 1, the 2, 5 faces as 2, and the 3, 4 faces as 3.

Now take an arbitrary point z0 in the plane of the triangle. Throw the die to get a 2 say, and choose z1 to be the midpoint of the segment joining z0 to vertex 2. Now throw the die to get a 1 say, and choose z2 to be the midpoint of the segment joining z1 to vertex 1. Next throw the die to get a 3 say, and choose z3 to be the midpoint of the segment joining z1 to vertex 3. Now throw the die to get a 3 say, and choose z4 to be the midpoint of the segment joining z3 to vertex 3. Continue in this way. The lines are included simply as a guide; we are only interested in the plotted points.

You might like to see the results of playing this game in this applet kindly written by Bill Beaumont. Just choose the number of points you want included.


At first sight, the sequence of points {zi} seems to be completely random, but when a lot of points are plotted, something amazing appears. Incredibly, out of the blur of dots, the Sierpinski sieve emerges. Why is this so?

In fact, it turns out not to be surprising at all. We just need to know that the midpoint of the segment joining points (x, y) and (u, v) is ((x + u)/2, (y + v)/2). We can take the coordinates of the vertices of the above triangle to be

1 : (0, 1) ; 2 : (0, 0) ; 3 (1, 0)

either by taking a pair of skewed axes with 2 as the origin, or for the moment thinking of the triangle as being right angled at 2. If we now take the midpoint of a segment linking z = (x, y) to a triangle vertex, we get midpoint coordinates

for 2 : (x/2, y/2) ; for 3 : (x/2 + 1/2, y/2) ; for 1 : (x/2 , y/2+ 1/2).

These are precisely the defining coordinates for the IFS of the Sierpinski sieve.

The one defect in the game may be a few odd initial points in the sequence which don't appear to belong. This defect is avoided if we start with a point of the sieve: for example, a vertex of the triangle.


The Pascal triangle

For many students, any mention of permutations, combinations and binomial expansions is likely to lead to a panic attack! A binomial is simply a polynomial with two variables. Examples are: a2 + b2, u3 – u v + v3.

We shall be interested in expanding binomials of the form (x + y)n where n is a non-negative integer, and looking at the coefficients of the terms. In fact, it will be simpler to look at (1+ x)n as the coefficients will remain the same. See if you can fill in the gaps in the following table. Starting with n = 0 we get:

Binomial
Expansion
Coefficients
(1+ x)0
1
1
(1+ x)1
1 + x
1   1
(1+ x)2
1 + 2x + x2
1   2   1
•   (1+ x)3        
•   (1+ x)4        
•   (1+ x)5        

We can continue indefinitely, but obviously the amount of effort increases as n gets larger. The numbers in the right column form a triangle called the Pascal triangle. Here is an extended version:


• Look at the triangle. What simple patterns can you see? From row 3 on, it is in fact quite easy to write down each row of numbers starting from the row above. Can you spot the simple relationship?





















# Clearly we expect to continue to place 1s down the ends of the rows, and there is an obvious sequence 1, 2, 3, 4, ... on the next diagonal in at each end. There are many other pretty patterns too.

You might also have noticed that in the body of the triangle, each entry is the sum of the two entries immediately above it. This enables us to add further rows to the triangle quite easily.

The entries in the Pascal triangle are called binomial coefficients. Labelling the rows starting with 0 (corresponding to the powers of (1 + x)), the coefficient in the nth row and rth diagonal from the left is denoted nCr or (pronounced ‘n choose r’). There is a formula for this quantity:

                     (*)

For example, checking with the above triangle, 4C2 = 6, 5C3 = 10.

• If you are keen, you might try using the formula in (*) to prove the recurrence relation described above in which each entry is the sum of the two entries immediately above it.

But why have we included the Pascal triangle here? It is a triangle, but ... ! See what happens when we colour each odd entry black, and each even entry white:

Amazing! The Sierpinski sieve miraculously appears. The reason for this is beyond us here, but interested readers can look up Fractals for the Classroom by Peitgen, Jürgens and Saupe (Springer).

We can however investigate a small step along the way, using the ‘each entry is the sum of the two entries above it’.

• In the following tables, the squares represent a triangle entry with the two entries above it. Fill in the missing spaces.

 Odd 
 Odd 
   
Even
 
 Odd 
Even
    
 
Even
Odd
    
 
Even
Even
    
 


 Odd
Odd
      
Colour?
      
Odd
Even
      
Colour?
      
Even
Odd
     
Colour?
     
Even
Even
     
Colour?
     

You can check how this works with particular coefficient entries in the above triangles.

Three dimensional sieve

Finally, we observe that the sieve generalizes easily to higher dimensions. A three dimensional array will look something like this: