Blowups and Tops of Overlapping Iterated Function Systems

In “Fractals in the large” strichartz Robert Strichartz observes that fractal structure is characterized by repetition of detail at all small scales. He asks “Why not large scales as well?” He proposes two ways to study large scaling structures using developments of iterated function systems. Here we review geometrical aspects of his paper and make a contribution in the area of tiling theory.

In his first approach, Strichartz defines a reverse iterated function system (r.i.f.s.) to be a set of $m>1$ expansive maps

acting on a locally compact discrete metric space $M$, where every point of $M$ is isolated. Here the large scaling structures are the invariant sets of $T$, sets $S\subset M$ which obey

Why does does Strichartz restrict his definition to functions acting on discrete metric spaces? (i) He establishes that there are interesting nontrivial examples. (ii) He shows that such objects (act as a kind of skeleton to) play a role in his second kind of large scale fractal structure that he calls a fractal blowup. Probably he had other reasons related to situations where his approach to analysis on fractals could be explored.

In Section 2 we present notation for iterated function systems (i.f.s.) acting on $\mathbb{R}^{n}$. We are particularly concerned with notation for chains of compositions of functions and properties of addresses of points on fractals. In Section 3 we review Strichartz’ definition and basic theorem concerning invariant sets of reverse iterated function systems, and we compare them to the corresponding situation for contractive i.f.s. We describe some kinds of invariant sets of contractive i.f.s. and consider how they compare to Strichartz’ large scaling structures. It is a notable feature of Strichartz’ definition that he restricts attention to functions acting on compact discrete metric spaces. We mention that, if this restriction is lifted, sometimes very interesting structures, characterized by repetition of structure at large scales, may be obtained. See for example Figure 2.

In Section 4 we define fractal blowups, Strichartz’ second kind of large scale fractal structure, and present his characterization of them, when the open set condition (OSC) is obeyed, as unions of scaled copies of an i.f.s. attractor, with the scaling restricted to a finite range. We outline the proof of his characterization theorem using different notation, anticipating fractal tops. We recall Strichartz’ final theorem on the topic, where he restricts attention to blowups of an i.f.s. all of the same scaling factor. Here he combines his two ideas: he reveals that the fractal blowup is in fact a copy of the original fractal translated by all the points on an invariant set of a r.i.f.s.

In Section 5 we discuss how tilings of blowups can be extended to overlapping i.f.s. In tilings it was shown how, in the overlapping (OSC not obeyed) case, tilings of blowups can be defined using an artificial recursive system of “masks”. Here the approach is more natural, but we pay a price–sequences of tilings are not necessarily nested. Here tilings are defined by using “fractal tops”, namely attractors with their points labelled by lexicographically highest addresses. The needed theory of fractal tops is developed in Subsection 5.1. Then in Subsection 5.2 we use these top addresses to define and establish the existence of tilings of some blowups for overlapping i.f.s. The main theorem concerns the relationship between the successive tilings that may be used to define a tiling of a blowup. In Subsection 5.3 we present an example involving a tile that resembles a leaf.

Strichartz’ paper has overlap with bandt2 , published about the same time by Christoph Bandt. Both papers consider the relationship between i.f.s. theory and self-similar tiling theory. Current work in tiling theory does not typically use the mapping point of view, but both Bandt and Stricharz do. Bandt is particularly focused on the open set condition and the algebraic structure of tilings, but also has a clear understanding of tilings of blowups when the OSC is obeyed.

Strichartz’ paper also contains measure theory aspects that we do not discuss. But from the little we have focused on here, much has been learned concerning the subtlety, the depth, and the elegant simplicity of the mathematical thinking of Robert Strichartz.

Let $\mathbb{N=\{}1,2,\dots\}.$ An iterated function system (i.f.s.) is a set of functions

mapping a space $\mathbb{X}$ into itself, with $m\in\mathbb{N}$. An invariant set of $F$ is $S\subset\mathbb{X}$ such that

We use the same symbol $F$ for the i.f.s. and for its action on $S$, as defined here.

The i.f.s. $F$ is said to be contractive when $\mathbb{X}$ is equipped with a metric $d$ such that $d(f_{i}x,f_{i}y)\leq\lambda d(x,y)$ for some $0<\lambda<1$ and all $x,y\in\mathbb{X}$. If $\mathbb{X=R}^{n},\$we take $d$ to be the Euclidean metric. A contractive i.f.s. on $\mathbb{R}^{n}$ is associated with its attractor $A$, the unique non-empty closed and bounded invariant set of $F$ hutchinson . But Strichartz is also interested in the case where the underlying space is discrete and the maps are expansive.

We use addresses to describe compositions of maps. Addresses are defined in terms of the indices of the maps of $F$. Let $\Sigma=\left\{1,2,\dots,m\right\}^{\mathbb{N}}$, the set of strings of the form $\mathbf{j}=j_{1}j_{2}\dots$ where each $j_{i}$ belongs to $\left\{1,2,\dots,m\right\}$. We write $\Sigma_{n}=\left\{1,2,\dots,m\right\}^{n}$ and let $\Sigma_{\mathbb{N}}=\cup_{n=1}^{\infty}\Sigma_{n}.$ The address $\mathbf{j}\in\Sigma$ truncated to length $n$ is denoted by $\mathbf{j}|n=j_{1}j_{2}\dots j_{n}\in\Sigma_{\mathbb{N}},$ and we define

Define a metric $d$ on $\Sigma$ by $d(\mathbf{j},\mathbf{k})=2^{-\max\{n|j_{m}=k_{m},m=1,2,...,n\}}$ for $\mathbf{j}\neq\mathbf{k}$, so that $\left(\Sigma,d\right)$ is a compact metric space.

The forward orbit of a point $x$ under (the semigroup generated by) $F$ is

Here we do not allow $\mathbf{j}|n$ to be the empty set, so $x$ is not necessarily an element of its forward orbit under the i.f.s. Indeed, $x$ is a member of its forward orbit if and only if $x$ is a fixed point of one of the composite maps $f_{\mathbf{j}|n}$.

Now let $F$ be a contractive IFS of invertible maps on $\mathbb{R}^{n}$. Then a continuous surjection $\pi:\Sigma\rightarrow A$ is defined by

The limit is independent of $x$. The convergence is uniform in $\mathbf{j}$ over $\Sigma,$ and uniform in $x$ over any compact subset of $\mathbb{R}^{n}$. We say $\mathbf{j}\in\Sigma$ is an address of the point $\pi(\mathbf{j})\in A$.

We define $i:\Sigma\rightarrow\Sigma$ by $i(\mathbf{j)=}ij_{1}j_{2}\dots$ But we may also write $k_{1}k_{2}...k_{l}\mathbf{j}$ to mean the address $k_{1}k_{2}\dots k_{l}j_{1}j_{2}\dots\in\Sigma.$ Let $\sigma:\Sigma\rightarrow\Sigma$ be the shift operator defined by $\sigma(\mathbf{j)=}j_{2}j_{3}\dots$ . It is well-known that

for all $i\in\{1,2,...m\},\mathbf{j\in}\Sigma$.

A notable shift invariant subset of $\Sigma$ is the set of disjunctive addresses $\Sigma_{dis}$. An address $\mathbf{j}\in\Sigma$ is disjunctive when, for each finite address $i_{1}i_{2}i_{3}\dots i_{k}\in\left\{1,2,\dots,m\right\}^{k}$, there is $l\in\mathbb{N}$ so that $j_{l+1}...j_{l+k}=i_{1}i_{2}i_{3}\dots i_{k}$. The set of disjunctive addresses $\Sigma_{dis}\subset\Sigma$ is totally invariant under the shift, according to $\sigma\left(\Sigma_{dis}\right)=\Sigma_{dis}.$ A point $a\in A$ is disjunctive if there is a disjunctive address $\mathbf{j}\in\Sigma$ such that $\pi(\mathbf{j})=a$. Disjunctive points play a role in the structure of attractors. For example, if the i.f.s. obeys the open set condition (OSC) and its attractor has non-empty interior, then all the disjunctive points belong to the interior of the attractor bandt . Recall that $F$ obeys the OSC when there exists a nonempty open set $O$ such that $\cup f_{i}(O)\subset O$ and $f_{i}(O)\cap f_{j}(O)=\emptyset$ whenever $i\neq j.$

In his first approach to large scaling structures, Strichartz defines a reverse iterated function system (r.i.f.s.) to be a set of $m>1$ expansive maps

acting on a locally compact discrete (i.e. every point is isolated) metric space $M$. We write $T$ and $t_{i}$ in place of $F$ and $f_{i}$ to distinguish this special kind of i.f.s. A mapping $t_{i}:M\rightarrow M$ is said to be expansive if there is a constant $r>1$ such that $d(t_{i}x,t_{i}y)\geq rd(x,y)$ for all $x\neq$ $y$ in $M.$ An expansive mapping is necessarily one-to-one and has at most one fixed point.

In this case Strichartz’s large scaling structures are the invariant sets of r.i.f.s.; that is, sets $S\subset M$ which obey

By requiring that $M$ is discrete, Strichartz restricts the possible invariant sets to be discrete.

Let $P$ be the fixed points of $\{t_{\mathbf{i}|k}:M\rightarrow M|k\in\mathbb{N},\mathbf{i}\in\Sigma\}$. Contrast Theorem 3.1 with Theorem 3.2.

EXAMPLE 1 Let $M=\mathbb{Z}$, $T=\{t_{i}:M\rightarrow M;t_{1}(x)=2x,t_{2}(x)=2x-1\}.$ It is readily verified that $M$ is invariant for this r.i.f.s, $T.$ It consists of the forward orbits of the fixed points of $t_{1}$ and $t_{2}.$

EXAMPLE 2 Strichartz presents the following example of a r.i.f.s. Let $M$ be the set of integer lattice points $\mathbb{Z}^{2}$ in the plane, lying between or on the lines $y=\rho x$ and $y=\rho x+1$ where $\rho+\rho^{2}=1,$ $\rho=\left(\sqrt{5}-1\right)/2.$ The r.i.f.s. comprises the two maps

These maps are expansive on $M$, even though when viewed as transformations acting on $\mathbb{R}^{2},$ they contract pairs of points that lie on any straight line with slope $-1/\rho$. The fixed point of $t_{1}$ is $(0,0)$ and of $t_{2}$ is $(0,1),$ both of which lie in $M.$ The union of the forward orbits of these two points is $M$. So this unlikely looking set of discrete points is invariant under the r.i.f.s.

This example yields, by projection onto the line $y=\rho x,$ an example of a quasi-periodic linear tiling using tiles of lengths $\rho$ and $1+\rho.$ Strichartz also points out that by projection onto the perpendicular line $y=-x/\rho$ of a natural measure on $M$ one obtains, after renormalizing, the unique self-similar measure on $[0,1]$ associated with the overlapping i.f.s. $f_{1}(x)=\rho x$, $f_{2}(x)=\rho x+1$ with equal probabilities.

Theorem 3.1 leads one to wonder: What are the invariant sets of an i.f.s.? Usually the focus is on compact invariant sets, namely attractors. The following Theorem is simply a list of some of the invariant sets of a contractive i.f.s. The wealth of such invariants here stands in sharp contrast to Theorem 3.1.

There are other invariant sets. For example, let $A$ be a Sierpinski triangle, the attractor of an i.f.s. $F_{sierp}$ in the usual way. Let $B$ be the union of the sides of all triangles in $A.$ Then $B$ is an invariant set for $F_{sierp}$. It is not covered by Theorem 3.2.

We note that the invariant set in (4) is also invariant under the inverse i.f.s.

The orbit under $F^{-1}$ of the attractor $A$ is invariant under $F^{-1}.$ This set may be referred to as the fast basin of $A$ with respect to $F$, see fastbasin . It is an example of a set which is “invariant in the large”, admitted when Strichartz’ constraint, that the underlying space is discrete and locally compact, is lifted.

Figure 2 illustrates the fast basin associated with (left) a Sierpinski triangle i.f.s. and (right) a different i.f.s. of three similitudes of scaling factor $1/2.$ Fast basins are interesting from a computational point of view, because they comprise the points $x$ in $\mathbb{R}^{n}$ for which there is an address $\mathbf{j\in}\Sigma_{\mathbb{N}}$ such that $f_{\mathbf{j}}(x)\in A$.

Strichartz uses r.i.f.s. to analyze the structure of what he christened “fractal blowups”. These structures have been used to develop differential operators on unbounded fractals, see for example strichartz2 ; teplyaev .

Let $F$ be an i.f.s. of similitudes. The maps take the form

where $0<r_{j}<1,$ $b_{j}\in\mathbb{R}^{n}$ and $U_{j}$ is an orthogonal transformation. It is convenient to write $r_{j}=r^{a_{j}}$ where $r=\max\left\{r_{j}\right\}$, so that $1\leq a_{j}<a_{\max}$ . A blowup $\mathcal{A}$ of $A$ is the union of an increasing sequence of sets

where $A_{j}=f_{-\mathbf{k}|j}\left(A\right)$ for some fixed $\mathbf{k}\in\Sigma$ and all $j\in\mathbb{N}$. We have

Strichartz starts with a more general definition of a blowup, but restricts consideration to the one given here.

Strichartz unites his two ideas, reverse i.f.s. and blowups, by considering the case where $f_{j}\left(x\right)=rx+b_{j}$ for all $j,$ and studying the blowup $\mathcal{A}\left(\overline{\mathbf{1}}\right)$ where $\overline{\mathbf{1}}\mathbf{=}$ $111\dots,$ that is

That is, $\mathcal{A}\left(\overline{\mathbf{1}}\right)$ is the Minkowski sum of the attractor of the i.f.s. and an invariant set of a r.i.f.s.

In this Section we study tilings of fractal blowups in the case of overlapping i.f.s. attractors. First, in Subsection 5.1 we give relevant theory of fractal tops. In Subsection 5.2 we show how fractal tops may be used to generate tilings of fractal blowups for overlapping i.f.s. The approach here is distinct from the one in tilings . In Subsection 5.3 we illustrate fractal tops for an i.f.s. of two maps, with overlapping attractor that looks like a leaf, suggesting applications to modelling of complicated real-world images.