\input{defines.tex}
\documentstyle{article}

\title{When Is 2-Reptile a 3-Reptile?}

\author{Thomas Colthurst}

\begin{document}
\maketitle

\section{Abstract}
A $k$-reptile is a tile which can be dissected into $k$ congruent parts,
each similar to the original tile.  $k$-reptiles appear in many area of
mathematics, including the study of aperiodic tilings, Penrose tiles, and
wavelets.  This paper uses fractal integration to answer the previously
open question:  Can a closed topological disk be both a 2-reptile and a
3-reptile?

\section{Introduction}

A {\em plane tiling} is a countable family of closed sets $T_i$ (called the
{\em tiles}) such that
\begin{itemize}
\item $\union T_i = \rr^2$
\item $\mbox{int} T_i \intersect \mbox{int} T_j = \emptyset$ for $i \neq j$
\end{itemize}

A {\em monohedral tiling} is a tiling in which all the tiles are congruent,
$T_i \cong T_j$ $\forall i,j$.

A {\em $k$-similarity tiling} is a monohedral tiling if every tile is an
union of $k$ smaller copies of itself and if no smaller value of $k > 1$
has this property.

A {\em $k$-reptile} is any closed set which can be dissected into $k$ congruent
parts, each similar to the original tile.

The importance of $k$-reptiles comes, from among other things, the fact
that they generate $k$-similarity tilings which are usually aperiodic.  Also,
multidimensional wavelets naturally have support on reptiles.

Exercise 10.1.4 of Grunbaum and Shepard is marked as an open problem, and
asks:  ``Can a closed topological disk be both a 2-reptile and also a
3-reptile?''  This paper attempts to answer this question for all tiles,
not just topological disks.

\section{Iterated Function Systems}

An {\em Iterated Function System} (IFS) is a compact set of transformations
$W = { w_i }$ on a complete metric space $X$ with contractivity
factor $s_W \leq 1$ such that $d( w_i(x), w_i(y) ) \leq s_W d(x,y)$ $\forall i,x,y$.

From every $k$-reptile we can get an IFS with 
$k$ transformations by specifying contractive similitudes that takes
the reptile to each of its $k$ congruent parts.  The fundamental theorem
of IFS theory states that we can go backwards and recover the reptile
from each IFS:

\begin{theorem}
For every IFS $W = ( \{ w_i \} ,X)$, there is an unique compact set $A_W$
such that $A_W = \union w_i(A_W)$.
\end{theorem}

\section{Fractal Integration}

To integrate over IFSs, we must make them into measures.  To do this,
we attach real weights $p_i$ to each of the transformations in the IFS such
that $\sum p_i = 1$ and call the new object a probabilistic IFS (PIFS).

\begin{theorem}
For every PIFS $W = ( \{ w_i \}, \{ p_i \}, X)$ there exists an unique
normed measure $\mu_W$ with compact support $A_W$ such that
$$\mu_W = \sum p_i \mu_W \circ w_i^{-1}$$
\end{theorem}

We can now integrate over $\mu_W$ by using its recursion property:
$$\int f \, d\mu_W = \int f \, d\sum p_i \mu_W \circ w_i^{-1}
= \sum p_i \int f \, d\mu_W \circ w_i^{-1}
= \sum p_i \int f \circ w_i \, d\mu_W$$

For example, if $W = \{ 1/3 x, 1/3x + 2/3 \}$ (the Cantor set) and
the weights are both $1/2$, then 
$$\int x \, d\mu_W = 1/2 \int 1/3 x \, d\mu_W + 
                     1/2 \int 1/3x + 2/3 \, d\mu_W$$
and 
$$\int x \, d\mu_W = (3/2) \int 1/3 \, d\mu_W = 1/2$$

\section{The Structure of $k$-reptile IFSs}

A {\em just-touching} IFS $W$ is one whose attractor $A_W$ contains
an open set $O$ such that the closure of $O$ is $A_W$ and
the intersection of $w_i(O)$ and $w_j(O)$ is empty for $i \neq j$.

Intuitively, a just-touching IFS is one whose parts don't overlap
too-much.  Note that when $A_W$ is a topological disk, the just-touching
property implies the second (the so-called ``packing'') condition
on a tiling.

\begin{theorem}
The Hausdorff dimension $d$ of a just-touching IFS
made up of similitude transformations $w_i$ with contractivity 
factor $s_i$ satisfies
$$ \sum s_i^d  = 1$$
\end{theorem}

Note that the first (``covering'') property of tilings of $\rr^2$
implies that the tiles must have Hausdorff dimension $2$.

Finally, the condition that a reptile be able to be disected into
congruent copies implies that the contractivity factors of
the transformations in their IFSs must all be the same.  

Combining all of the above considerations to leads to the following
theorem:

\begin{theorem}
The IFS for a $k$-reptile is of the form
$\{ w_1, \ldots, w_k \}$, where
$w_i = s_i z + b_i$ or $w_i = s_i \bar{z} + b_i$,
$s_i$ and $b_i$ are complex numbers, and $|s_i| = \frac{1}{\sqrt{k}}$.
\end{theorem}

\section{The Moment Method}

By the results of the last section, there are three different
possibilities for the form of the IFS of a $2$-reptile, and four
for the IFS of a $3$-reptile.  We consider here only the two forms
which contain no conjugation; the calculations for the other form
combinations are included in the appendix.
 
We have now reduced the problem of showing that no $2$-reptile is a
$3$-reptile to the problem of showing that the IFS 
$W = \{ a_1 z + b_1, a_2 z + b_2 \}$ and the IFS
$W' = \{ c_1 z + d_1, c_2 z + d_2, c_3 z + d_3 \}$ have different
attractors.  By change of coordinates, we can assume that $W$
is of the form $\{ a_1 z, a_2 z + 1 \}$.  As before, we have the
constraints $| a_i | = \frac{1}{\sqrt{2}}$ and $| c_i | =
\frac{1}{\sqrt{3}}$.

To show that $A_W$ and $A_W'$ are different we use the fact that if
we assign equal probabilities to the transformations of a just
touching IFS with Hausdorff dimension $2$, 
the resulting invariant measure is the restriction of
a the Lebesgue measure (scaled by a constant equal to the Hausdorff
measure of $A_W$ -- but since $A_W$ and $A_W'$ have the same Hausdorff
measure, we may neglect this). 

The $n$-th complex moment of a measure $\mu$ is $\int z^n \, d\mu$.  Our
recurence relation for fractal integrals allows to obtain the following
expressions for $m_2(n)$, the $n$-th moment of $\mu_W$ and
$m_3(n)$, the $n$-th moment of $\mu_W'$:

\begin{eqnarray}
m_2(n) & = & 
   1/2 \int a_1^n z^n + \sum_{i=0}^n  \binom{n}{i} a_2^i z^i \, d\mu_W  \\
& = & \frac{ \sum_{i=0}^{n-1} \binom{n}{i} a_2^i m_2(i) }{ 2 - a_1^n - a_2^n }
\end{eqnarray}

$$m_3(n)  =  \frac{ \sum_{i=0}^{n-1} \binom{n}{i} ( c_1^i d_1^{n-i} +
c_2^i d_2^{n-i} + c_3^i d_3^{n-i} ) m_3(i) }{ 3 - c_1^n - c_2^n - c_3^n}$$

 
\begin{thebibliography}{Barnsley 99}

\bibitem[Barnsley 88]{barnsley:everywhere} Barnsley, Michael.  
   {\em Fractals Everywhere.}  Academic Press, San Diego.  1988.

\bibitem[Grunsbaum 8x]{grunsbaum:shepard}  {\em Tilings and Patterns.}

\bibitem[Vrscay 91]{vrscay:ga} Vrscay, Edward R.
   {\em Fractal Geometry and Analysis}  Belair, Jacques and Serge Dubuc, ed.s.
   NATO ASI Series C, Vol. 346.  Kluwer Academic, London.  1991.
   Pages 405-468.

\end{thebibliography}

\end{document}