Cut The Knot!An interactive column using Java applets
by Alex Bogomolny
Dot Patterns and the Sierpinski Gasket
In the last column, we looked into simple patterns exhibited by addition and multiplication tables. The next logical step would be to investigate the tables corresponding to various operations in modular arithmetic. But let's, for a change, look into things triangular.
So, how many ways are there to define the Sierpinski gasket (also known as the Sierpinski triangle)? I counted a respectable 9 but undoubtedly there are more. I would be happy to be advised of additional ones.
In the drawing area of the applet below, we have either rows of digits or circles with colors corresponding to the digits. Patterns in the drawing area are defined row-by-row starting from the upper row which consists of clickable digits (or circles.) The value p of a node is defined by values (q1 and q2) of the two nodes immediately above it according to the following formula:
where N is the modulus of the arithmetic used. Think of the applet as presenting a finite view of an infinite lattice of nodes filling the lower half plane. All omitted nodes are assigned the value of 0. The applet has the following controls:
(Please note that when the number of rows is close to the maximum of 50, the drawing is slow. Be patient.)
I'll make just a few observations for the case of the binary system (N = 2). Assume the rows are numbered from 0, the next being 1, and so on. For every node p, only dots in the upside down triangle above it, may affect its value. However, dots in rows 1,2,4,... - all powers of 2 - only depend on the values of their extreme ancestors - L(p) and R(p). The proof is by induction and uses the simple identity a + a = 0 (mod 2). This is why in the rows corresponding to the powers of 2 there are only 2 nonzero dots. Each of these two dots propagates in exactly the same pattern as in the triangle above them. The two patterns do not interfere until they meet at a row that is the next power of 2, and so on. We see the birth of the self-similarity characteristic of Sierpinski gasket.
In row 1, two nonzero dots are next to each other. In row 2, they are one dot apart. In row 4, there are 3 zero dots. In row 2n, there are 2n-1 of them. Therefore, we may generate lower rows of the Sierpinski gasket by repeating these patterns in the upper row. Each nonzero dot in the upper row emits a Sierpinski gasket. The whole pattern is a superposition of the gaskets.
Obviously, if the upper row contains only zero dots, all the dots below it are zero. The same is true when the upper row is filled with nonzero dots. So there are two starting arrangements for the upper row that result in the same pattern from the first row downwards. Is this true of any such pattern? Yes, of course. Two arrangements in the upper row complementary to each other (i.e., never having the same dot in the same position) generate the same pattern from the first row down.
Starting with a single nonzero dot, it is always the case that rows 2n-1 consist of a contiguous segment of nonzero dots whereas rows 2n-2 contain an alternating pattern.
If N is prime, each row number Nn contains only 2 nonzero dots. For composite N, the situation is not that simple. Much depends on the value at the apex of the triangle. With N = 6, we may observe patterns from both N = 2 and N = 3.
Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much programming experience. He holds an M.S. degree in Mathematics from the Moscow State University and a Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at email@example.com
Copyright © 1997-1998 Alexander Bogomolny