Minimum number of contractions needed to obtain a particular invariant set

Question

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.

But what about in general?

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?

Answer 1

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.

Answer 2

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).