# Iterated function system on the plane

Let $r_1, r_2, r_3$ be three nonnegative real numbers with $r_1^2+r_2^2+r_3^2 <1$. Can you find three similitudes $f_1,f_2,f_3$ on $\mathbb{R}^2$ with similarity ratios $r_1,r_2,r_3$ resp. and a nonempty open set $O \subset \mathbb{R}^2$ such that $f_i(O) \subset O$ and $f_i(O) \cap f_j(O)=\emptyset$ for $i \neq j$ ?

(Natural generalizations thinkable but I stuck at this stage.)

-
This is a pretty question. I hope there's an answer where the open sets are the interiors of polygons! – John Wiltshire-Gordon Jul 9 '13 at 15:03
where did this come from? – john mangual Jul 9 '13 at 17:21
Is the answer clear (on way or the other) in the case of two non-negative real numbers? – Aaron Meyerowitz Jul 10 '13 at 8:29
@Aaron: the answer is positive in that case. This can be seen by taking as the set $O$ a right triangle with $r_1$ and $r_2$ as the short side-lengths (and by taking the obvious mappings $f_1$ and $f_2$). – Tapio Rajala Jul 10 '13 at 8:48
It takes a 3 megabyte book to answer this question? – Gerald Edgar Jul 10 '13 at 14:15

Given the other (incorrect) answers, I think it is worth to give a detailed proof of the following partial negative answer: if the maps $f_i$ are only allowed to be homotheties, then there is no such open set $O$ if $\max(r_1+r_2,r_2+r_3,r_3+r_1)>1$ (which is certainly possible, for example take $r_1=r_2=0.6; r_3=0.1$).

In fact, I claim the following.

Fact: already for two numbers $r_1,r_2$ such that $r_1+r_2>1$, it is not possible to find homotheties $f_1, f_2$ of $\mathbb{R}^2$ with ratios $r_1,r_2$, and a nonempty open set $O\subset\mathbb{R}^2$ such that $f_1(O)\subset O$, $f_2(O)\subset O$ and $f_1(O)\cap f_2(O)=\varnothing$. This clearly implies the claim above.

In order to do this I recall some notation and facts. Given a finite collection of strictly contractive similarity maps $g_1,\ldots, g_m$, $m\ge 2$, on $\mathbb{R}^2$, there exists a unique nonempty compact set $E$ such that $E=\bigcup_{i=1}^m g_i(E)$. This set is called the self-similar set associated to the iterated function system (IFS) $g_1,\ldots,g_m$.

We say that an IFS $(g_1,\ldots,g_m)$ satisfies the Open Set Condition (OSC) if there exists a nonempty open set $O$ such that $g_i(O)\subset O$ for $i=1,\ldots,m$ and the $g_i(O)$ are pairwise disjoint.

Note that with this (standard) terminology, the question in the OP can be reformulated as follows: does there exist an IFS $(g_1,g_2,g_3)$ satisfying the OSC where the similarity ratio of $g_i$ is $r_i$?

The similarity dimension of the IFS $(g_1,\ldots,g_m)$ is the unique real number $s$ such that $\sum_{i=1}^m r_i^s=1$, where $r_i$ is the similarity ratio of $g_i$.

We then have the following classical result due to Hutchinson (a proof can be found in e.g. Falconer's textbook "Fractal Geometry: mathematical foundations and applications", Chapter 9).

Theorem. If $(g_1,\ldots,g_m)$ satisfies the open set condition, then the Hausdorff dimension of the associated self-similar set $E$ equals the similarity dimension $s$.

We can now prove the stated fact. Let $r_1,r_2\in (0,1)$ be such that $r_1+r_2>1$. Let $f_1,f_2$ be homotheties with contraction ratio $r_1,r_2$. Since $r_1+r_2>1$, the similarity dimension of the IFS $(f_1,f_2)$ is strictly larger than $1$.

On the other hand, if we let $p_1,p_2$ be the fixed points of $f_1,f_2$ and $E$ is the closed segment joining them, then one can check directly that $E=f_1(E)\cup f_2(E)$, or in other words the self-similar set associated to $(f_1,f_2)$ is $E$. But $E$ has Hausdorff dimension $1$ (or $0$ when $p_1=p_2$) which is strictly less than the similarity dimension, so the open set condition cannot hold. This is exactly the claimed fact.

-
Thanks for correcting. – MichaelNgelo Jul 11 '13 at 3:22

A good solution may involve (the interior of) sets with boundary of fractal dimension. However, using just right triangles one can get around $\frac{4}{5}$ of the possibilities (in a sense made precise below) and very slightly more using rectangles as well.

I'll focus on the squared ratios $\rho_i=r_i^2$ with $\rho_1+\rho_2+\rho_3 \le 1.$ So I will allow $r_i=0$ and allow the sum to actual equal $1$. I find it easier to consider the triples in all $6$ possible orders. So the set of possible $\rho$ triples can be thought of as a body $\mathbf{B}$ comprising part, or perhaps all, of the pyramid $\mathbf{P}$ in $\mathbb{R}^3$ with corners at the origin and the points $(1,0,0)$ , $(0,1,0)$ and $(0,0,1).$ The volume of $\mathbf{P}$ is $\frac{1}{6}.$ My claim is that the volume of $\mathbf{B}$ is over $\frac{4}{5}$ of this. If a point $P=(\rho_1,\rho_2,\rho_3)$ is in $\mathbf{B}$ so are all the points of the box determined by the origin and $P$. So $\mathbf{B}$ could be specified were one able to described the surface made of the points in each radial direction furthest from the origin.

Certainly the the points with $\rho_1+\rho_2+\rho_3=1$ are of interest. As was kindly pointed out to me, we can achieve the triples $(t,1-t,0)$ using (the interior of) a right triangle with legs of lengths $\sqrt{t},\sqrt{1-t}$ and the usual division by the perpendicular to the hypotenuse. Iterating this for one of the sub-triangles (picture at the end) gives us triples of the form $(t,t^2,1-t-t^2)$ where $0 \le t \le \frac{\sqrt{5}-1}{2}.$ Here is a sketch of these points making up the boundary of the equilateral triangle and $6$ internal curves.

I can't really picture the body made up of all the boxes determined by these points and the origin, but the volume , roughly estimated by counting the included points of the form $(\frac{a}{100},\frac{b}{100},\frac{c}{100})$ , is somewhere between $0.83$ and $0.86$ of the total volume of $\mathbf{P}$ depending on if I use the floor or round in estimating. All the points with $\rho_1+\rho_2+\rho_3 \le 0.75$ appear to be achieved however then things start to fall off.

Certainly the point $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ is not accounted for. That can be achieved using a rectangle with sides $3 \times \sqrt{3}$ partitioned into three rectangles of with sides $1 \times \sqrt{3}.$ That increases the volume of $\mathbf{B}$ but not by very much.

Below is an sketch of possibly missing points with $\rho_1+\rho_2+\rho_3=0.9.$

The small triangle missing in the center comes from the rectangle just mentioned. So a good goal (as might have been obvious) would be triples like $(0.48.0.48.0.04)$, $(0.94,0.03,0.03)$ and $(0.32,0.32,0.36)$ with two equal components close to but not equal to $\frac{1}{2}$ or $0$ or $\frac{1}{3}$ and sum equal to, or nearly equal to , $1$.

Another interesting rectangle partition is a $4 \times 2\sqrt{2}$ rectangle partitioned in half and then one half again partitioned in half. However this gives the same result $(\frac{1}{2}, \frac{1}{4},\frac{1}{4})$ as an isosceles right triangle.

I thought of a clever (I thought) ways to pack a figure with similar copies which fill it mostly but not completely. However the $\rho$-triple is $(t^2,t^4,t^4)$ for $t=\frac{\sqrt{5}-1}{2}$ so this is not as good as the triangle construction $(1-t^2-t^4 ,t^2,t^4).$ The proportion covered increases and the pieces rotate if we hold one leg fixed and shrink the other, but this seems likely to be turning into the triangle situation. I don't think varying the angle would help.

-

partial solution

Something like this should work. We are given $r_1, r_2, r_3 > 0$ with $r_1^2+r_2^2+r_3^2<1$. Let $s$ be such that $r_1^s+r_2^s+r_3^s = 1$; this $s$ is the similarity dimension of our IFS. Then $0 < s < 2$.

We will choose three points $p_1, p_2, p_3$ in the plane. Our three maps will be $f_1(x) = r_1 (x - p_1)+p_1$, $f_2(x) = r_2 (x - p_2)+p_2$, $f_3(x) = r_3 (x - p_3)+p_3$. So $f_i$ has fixed point $p_i$ and contraction ratio $r_i$. Let $K$ be the attractor of the IFS $(f_1,f_2,f_3)$. That is, $K$ is a nonempty compact set with $K = f_1(K) \cup f_2(K) \cup f_3(K)$.

By a theorem of K. Falconer, for almost all choices of the three points $p_1, p_2, p_3$, the Hausdorff dimension of $K$ is $s$.

In fact, it should be true (since $s < 2$) that for almost all choices of $p_1,p_2,p_3$, the images $f_1(K), f_2(K),f_3(K)$ are pairwise disjoint. IF that happens, then an $\epsilon$-neighborhood of $K$ will work as the open set $O$ for small enough $\epsilon$.

Even if the images $f_1(K), f_2(K),f_3(K)$ are not pairwise disjoint, I seem to recall a theorem to the effect that if the Hausdorff dimension coincides with the similarity dimension, then the open set condition must hold (which is the existence of open set $O$ requested in the theorem).

-
There are multiple issues with this answer. Falconer's theorem requires the norm of the maps to be $<1/2$, in this case this means $r_1,r_2,r_3<1/2$ in which case the result is trivial. In fact for this family of IFS's, the fixed points $p_1,p_2,p_3$ play no role, as long as they're in general position the self-similar sets obtained are all affine images of each other. It is also most definitely not true that the open set condition holds if the Hausdorff dimension equals the similarity dimension (only the converse is true), so there is no reason to believe the pieces $f_i(K)$ will be disjoint. – Pablo Shmerkin Jul 10 '13 at 18:51
In fact, if the similarities are homotheties, then open set condition CANNOT hold if $r_i+r_j>1$ for some $1\le i<j\le 3$. This is because for an IFS consisting of two planar homotheties $f_i,f_j$ with ratios $r_i,r_j$, the attractor is the (possible degenerate) segment joining the fixed points and thus has Hausdorff dimension $1$ (or $0$) which is strictly smaller than the similarity dimension, so the open set condition cannot hold. So much less can it hold if you add yet another map. – Pablo Shmerkin Jul 10 '13 at 18:55

Corrected:

Let $R = \max \{r_1+r_2, r_2+r_3, r_3+r_1 \}$. This can be done when $R \leq 1$.

Take 3 non-collinear points $p_1,p_2,p_3$ on the plane and take the usual self-similar maps $f_i(x)=r_i(x−p_i)+p_i, 1 \leq i \leq 3$, and let $O$ be the interior of the triangle formed by the 3 points.

-
Solving for $K = f_1(K) \cup f_2(K) \cup f_3(K)$ this generalizes the Sierpinski triangle. – john mangual Jul 10 '13 at 16:51
To see that this does not work take for instance $r_1=r_2=r_3 > \frac12$. – Tapio Rajala Jul 10 '13 at 16:59
This works (for any triangle) only if $R\le1$. – Emil Jeřábek Jul 10 '13 at 17:02
We were told $r_1^2 +r_2^2 + r_3^2 < 1$ so $r_1, r_2, r_3 < 1$. If all three are equal, they start being disjoint at $r = \frac{1}{4}$. Yes, it doesn't have to be equilateral. – john mangual Jul 10 '13 at 18:26
@MichaelNgelo: I’d suggest you correct the post, rather than delete it. This is a simple construction showing that the answer is yes (even using just homotheties) if $\max\{r_1+r_2,r_1+r_3,r_2+r_3\}\le1$, which complements Pablo Shmerkin’s answer. – Emil Jeřábek Jul 11 '13 at 11:40

Due to nuances in English language, hopefully the term Similarity or Affine Transformation is the same was your "similitude". Functions $z \mapsto az + b,\; a \overline{z} + b$ in the complex plane. Or even homothety where rotations are excluded.

We can let our open set be a square, $O = \square$. Then for any three ratios $r_1, r_2, r_3 < 1$ we can shrink our square by these factors and translate the image so that the images of $f_i(\square), f_j(\square)$ intersect.

The condition $r_1^2 + r_2^2 + r_3^2 < 1$ plays some other role I guess. Perhaps I'm missing something. I wonder if this supposed to generate a fractal.

-
You need the images not to intersect, and all of them to fit in the original open set. The condition $r_1^2+r_2^2+r_3^2\le1$ is clearly necessary as long as $O$ has finite Lebesgue measure. – Emil Jeřábek Jul 10 '13 at 12:25
OK. When you rescale, the factor shrinks by $r^2$ so for 3 disjoint copies to fit in the original, $r_1^2 + r_2^2 + r_3^2 \leq 1$. – john mangual Jul 10 '13 at 15:49