# Minimum number of contractions needed to obtain a particular invariant set

Consider the Koch curve $G \subseteq \mathbb{R}^2$. Clearly $G$ is the invariant set (IS) of the iterated function system (IFS) $\lbrace \phi_1, \phi_2, \phi_3, \phi_4 \rbrace$. Where (not wanting to jump between $\mathbb{R}^2$ and $\mathbb{C}$ but doing so for ease):

$\phi_1(x) = \frac{1}{3} x$, $\phi_2(x) = \frac{1}{3} (x \exp(\frac{i \pi}{3}) + 1)$, $\phi_3(x) = \frac{1}{3} (x \exp(-\frac{i \pi}{3}) + 1 + \exp(\frac{i \pi}{3}))$, $\phi_4(x) = \frac{1}{3} (x + 2)$

However can we do better? i.e. can we find an IFS consisting of fewer contractions such that its IS is $G$?

In this case, yes. The IFS $\lbrace \psi_1, \psi_2 \rbrace$ also has $G$ as its IS where:

$\psi_1(x) = \frac{1}{\sqrt{3}} x \exp(-\frac{5 i \pi}{6}) + \frac{1}{3} (1 + \exp(\frac{i \pi}{3}))$, $\psi_2(x) = \frac{1}{\sqrt{3}} x \exp(\frac{5 i \pi}{6}) + 1$

And as we know that an IFS consisting of a single contraction has a single point as its IS, we know that this is the best that we can do.

If $G \subseteq \mathbb{R}^n$ is the IS of the IFS $\lbrace \phi_1, \phi_2, \ldots, \phi_m \rbrace$ when can we tell if there exists an IFS with $G$ as its IS and consisting of strictly less than $m$ contractions?

As a specific example: how about the Sierpinski gasket / carpet? Can we do better that the obvious 3 / 8 construction IFS?

-
Can you, please, comment on what makes the $\psi$ IFS work? What is the relation between the semigroups generated by $\phi$ and $\psi$? –  Victor Protsak Jul 18 '10 at 9:41
Ah - although it might not be obvious at first, $\psi_1$ and $\psi_2$ were chosen such that $\psi_1 \circ \psi_2 = \phi_1$, $\psi_1 \circ \psi_1 = \phi_2$, $\psi_2 \circ \psi_2 = \phi_3$ and $\psi_2 \circ \psi_1 = \phi_4$. But is dont think this process will generalise well. –  Mark Bell Jul 18 '10 at 18:40

An interesting question. Of course there is some ambiguity in the formulation "when can we tell".

Certainly in explicit examples, one may be able to apply ad-hoc methods. For example, things are easier for the Sierpinski gasket and carpet, since these have identifiable features in terms of their complementary regions.

For example, if we wish to write the Sierpinski gasket as a union of smaller copies, it should be fairly easy to see that each complementary region must be mapped to another complementary region. But this means that each contraction must correspond to one of the "smaller triangles" that appear in the usual gasket contraction, and we need at least three of these to make up the whole gasket.

The same type of argument should work for the Sierpinski carpet.

EDIT: Let me provide a few additional arguments to illustrate what I mean in the case of the Sierpinski gasket and carpet.

## Lemma

Any equilateral triangle contained in the Sierpinski gasket is the triangle surrounding one of the "children" in the usual construction.

## Proof

An exercise for the reader. (Hint: Note that the only way for a straight line in the gasket to begin in one of the standard triangles but not end there is to pass through the two points by which it is connected to the rest of the gasket.)

## Corollary

If $A$ is an affine similarity that maps the Sierpinski gasket into itself, then $A$ can be written as a finite composition of the three maps from the "standard" IFS that generates the gasket.

A similar argument works for the carpet. Here it is not enough to consider the outer square, but if we add the first generation squares to it, the same works. To state this, let A be the union of the boundaries of nine squares that are joined together to form a larger square; e.g. $$A=\{(x,y)\in[0,3]^2: x\in\{0,1,2,3\} \text{ or } y\in\{0,1,2,3\}\}$$. Let us call any image of A under an affine similarity a "3-by-3 grid".

## Lemma

The outer boundary of any nine-by-nine grid contained in the Sierpinski gasquet is the boundary of one of the squares occuring in the usual construction.

Again, I will leave the proof as an exercise. The claim that the usual system is optimal then follows immediately once more.

-
But intuitively the Koch curve appears to consists of 4 smaller copies of itself, so I'm not sure that it will "be fairly easy to see that ...". Although we have that if $G$ is the IS of an IFS consisting of $m$ contractions, then $\text{Dim}_H(G)$ < m\$. This then gives us a lower bound on the number of contractions needed (for the Serpinski Gasket & Carpet, 3). So in the case of the Gasket we have an optimal solution, but for the carpet we may be able to do better. Can we? Can we prove that we can't? –  Mark Bell Aug 3 '10 at 13:39
I am not sure what you mean here. The gasket and carpet are two-dimensional sets, and of course you need at least two contractions to find them. The point about the Koch curve is that you can also write it as two copies of the same shape, as demonstrated in your post. As I state in my answer, the difference with the gasket and carpet are that you have additional topological things that need to be preserved: complementary regions. That's what makes these cases easier, and shows the IFS given are indeed optimal. –  Lasse Rempe-Gillen Aug 4 '10 at 11:15

Perhaps you can consult some of the literature on "finite type condition" for IFSs.
That's if you are willing to allow overlap in the IFS.

MR1488232 (98i:28010)
MR1825981 (2002c:28010)
MR2304331 (2008m:28007)

When I did my computations on Barnsley's Wreath,
MR1117877 (92j:58062)
I used an IFS with 6 transformations. Barnsley's text that first describes this, though, says it was done with 5 transformations (but doesn't describe them).

-
I'm sorry, but what are these codes? MR1117877 (92j:58062)? I tried googling them but couldn't find anything. Thanks. –  Mark Bell Aug 5 '10 at 9:50
Mathematical Reviews (in your university library) or MathSciNet (on line by subscription). So try links like ams.org/mathscinet-getitem?mr=1117877 and go from there. Maybe that would have been a better way to list these. –  Gerald Edgar Aug 5 '10 at 12:12