---
tag: T4403SAMB2
kind: definition
name: Substitution tiling
msc: [37B52, 52C23]
defines: BAN4VASZF0
uses: [0RJF668P1T]
sources:
  - url: https://en.wikipedia.org/wiki/Substitution_tiling
---

## Definition

Let $d \ge 1$.
A tile is a compact subset of $\R^d$ that is the closure of its interior.
A tiling of a set $S \subseteq \R^d$ is a family of tiles whose union is $S$ and whose interiors are pairwise disjoint.
Let $T_1, \ldots, T_m$ be tiles, called prototiles, and let $\lambda > 1$.
A *substitution rule* with expansion factor $\lambda$ assigns to each $i$ a finite tiling $\omega(T_i)$ of $\lambda T_i$ by translates of the prototiles.
It extends to translates by $\omega(T_i + a) = \omega(T_i) + \lambda a$, and to tilings by applying it to each tile.
A patch of a tiling is a finite subfamily of its tiles.
A *substitution tiling* for $\omega$ is a tiling $\mathcal{T}$ of $\R^d$ by translates of the prototiles with the following property.
Every patch of $\mathcal{T}$ is a translate of a patch of $\omega^k(T_i)$ for some $k \ge 0$ and some $i$.

## Remarks

Example: in $\R^2$, let $T_1 = [0,1]^2$, $\lambda = 2$, and let $\omega(T_1)$ be the four unit squares $T_1 + a$ with $a \in \set{0,1}^2$.
Then $\omega^k(T_1)$ is the $2^k \times 2^k$ block of unit squares.
The grid of all unit squares $T_1 + a$, $a \in \Z^2$, is a substitution tiling, since each finite patch of it lies in a translate of some block.
Non-example: for the same rule, a tiling of $\R^2$ by rows of unit squares in which the rows are shifted by $1/2$ against each other is not a substitution tiling.
Its patches across two rows are not translates of patches of the grid.
The Penrose tilings, cut into Robinson triangles, are substitution tilings with expansion factor the golden ratio.
Their prototiles are the finitely many rotated and reflected copies of the two triangles.
More generally, $\lambda$ may be replaced by an expanding [[linear map|0RJF668P1T]] of $\R^d$.