# PadChannel: Improving CNN Performance through Explicit Padding Encoding

Juho Kim
Faculty of Applied Science and Engineering
University of Toronto, Toronto, ON, Canada
<EMAIL_ADDRESS>
###### Abstract

In convolutional neural networks (CNNs), padding plays a pivotal role in
preserving spatial dimensions throughout the layers. Traditional padding
techniques do not explicitly distinguish between the actual image content and
the padded regions, potentially causing CNNs to incorrectly interpret the
boundary pixels or regions that resemble boundaries. This ambiguity can lead
to suboptimal feature extraction. To address this, we propose PadChannel, a
novel padding method that encodes padding statuses as an additional input
channel, enabling CNNs to easily distinguish genuine pixels from padded ones.
By incorporating PadChannel into several prominent CNN architectures, we
observed small performance improvements and notable reductions in the
variances on the ImageNet-1K image classification task at marginal increases
in the computational cost. The source code is available at
https://github.com/AussieSeaweed/pad-channel

##  1 Introduction

Figure 1: The means of the best single crop top-1 accuracies on the
ImageNet-1K validation across each run for each model architecture with and
without PadChannel.

Figure 2: The standard deviations of the best single crop top-1 accuracies on
the ImageNet-1K validation across each run for each model architecture with
and without PadChannel.

In the realm of convolutional neural networks (CNNs), padding plays a pivotal
role, ensuring spatial dimensions remain consistent during convolution
operations even when part of the kernel lies outside of the original image. A
myriad of padding techniques exists, such as zero padding, reflect padding,
and replication padding. G. Liu et al. found that, although traditional
padding methods often perform at comparable levels, zero padding sometimes
emerges as the superior choice [5].

A critical examination of traditional padding techniques like zero padding
reveals a significant limitation: such methods do not provide a clear
demarcation between the actual image content and the padded regions. As a
result, CNNs must discern these boundaries, and while these can be learned,
the process is not without ambiguity. This inherent vagueness can potentially
hinder optimal feature extraction, emphasizing the need for a more distinct
representation [5].

To address this ambiguity when it comes to padding, we developed PadChannel.
The PadChannel technique introduces a mask of ones as an extra input channel.
When used in combination with zero padding, the values at the extra input
channel in the padded areas are zero while the values remain as one for the
original image pixels. This clear distinction helps to overcome the
limitations of conventional padding methods, significantly improving the
ability of CNNs to learn and represent the features accurately with a simple
method.

We show that by integrating PadChannel into VGG [9] and ResNet [4]
architectures, we achieve performance improvements and reductions in variances
on the ImageNet-1K image classification dataset [1], as shown in Figures 2 and
2, at little to almost no additional computational cost.

In the following sections, we delve into the specifics of PadChannel, its
implementation, and a detailed analysis of our experimental results.

##  2 Related Works

The advent of CNNs has been a breakthrough in the field of computer vision.
Central to the functioning of CNNs is the concept of convolution operations,
which often uses padding to maintain spatial dimensions across convolutional
layers. Commonly adopted padding methods include zero-padding, where
boundaries are filled with zeros; reflect padding, where borders mirror
adjacent pixels; and replication padding, which extends the closest border
pixels [5]. These techniques serve the primary purpose of preserving
dimensionality but offer no added contextual information for the model,
potentially causing CNNs to erroneously interpret the regions near the
boundary or regions that resemble image boundaries. This ambiguity can lead to
incorrect feature extraction.

Recognizing these limitations, researchers have sought innovative padding
techniques to address these challenges. A notable contribution is by G. Liu et
al., who introduced partial convolution-based padding. This method involves
re-weighing the convolution results near image boundaries. The convolutional
weights are calculated using a mask that spans the entire input image [5]. Our
proposed PadChannel borrows from this idea, yet presents a distinct mechanism
by passing it as a separate input channel to the first convolutional layer.

In the domain of CNNs, the concept of using masks as input channels has
garnered considerable attention. For example, deepfillv2, proposed by Yu et
al. for the image inpainting task, augments the input image with two
additional input channels, one to denote holes in the image and another as a
user sketch to guide the inpainting process [11]. The success of DeepFillV2
underscores the potential advantages of providing CNNs with more explicit
spatial information. In the context of PadChannel, the extra input channel can
help CNNs easily infer which part of the kernel lies outside of the original
image thereby giving it a rough positional orientation.

There have been various attempts to directly supply positional information to
enhance spatial awareness in CNNs. For instance, R. Liu et al. introduced
CoordConv, which encodes the horizontal and vertical positions as distinct
input channels. This results in the first CNN layer accepting five input
channels: three dedicated to the RGB data and two for the x and y coordinates,
respectively [6]. Outside of traditional CNNs, Dosovitskiy et al. proposed the
vision transformer (ViTs) for various computer vision tasks. ViTs divide the
image into fixed-size patches and linearly embed them into vectors. A key
feature is their use of positional embeddings, which aids spatial awareness by
associating groups of pixels with their relative positions in the image [2].

These groundbreaking strategies lay the foundation for our novel padding
method: PadChannel. This method is designed to mitigate the challenges of
traditional padding, offering a more explicit and efficient mechanism for CNNs
to interpret image boundaries, at negligible extra computation cost.

##  3 Methodology

Figure 3: Diagrams of the first convolutional layer with or without
PadChannel.

###  3.1 Model Architectures

We selected four popular CNN architectures for exploration: VGG11-BN, VGG16-BN
[9], ResNet18, and ResNet50 [4]. These models were chosen not only due to
their popularity and widespread use in computer vision but also thanks to
their diversity in size and architecture, allowing us to study the general
applicability of PadChannel. In addition, the official PyTorch recipes for the
aforesaid models are identical, which makes them convenient to train and
compare [7].

PadChannel was integrated by modifying the first convolutional layer of each
model to accept four input channels instead of the standard three RGB input
channels. During the forward pass, a mask of one is concatenated with the
input image batch as the new input channel in addition to the RGB values. With
the subsequent application of zero padding, the values in the fourth channel
corresponding to the padded regions become 0, while regions containing the
original pixels retain the value 1. The modified input image transformation at
the first CNN layer can be represented as

$X=[X,1]$

where $X$ is the input image, as visualized in Figure 3. With this additional
information carried by the fourth input channel, CNNs can more directly
understand and interpret boundary pixels.

This clearer demarcation aids the network in focusing on genuine image content
and reduces potential pitfalls associated with interpreting padded regions.
Note that this makes PadChannel only compatible with zero padding. Other
traditional padding techniques such as reflect padding will retain the value
$1$ in the padded regions, which defeats the whole purpose of introducing a
new fourth channel to clearly mark the regions corresponding to the original
image pixels from the padding.

While this technique was only applied on the first layer, this technique can
technically be applied to all convolutional layers. The design choice of only
modifying the first layer was informed by two reasons. First, adding an extra
input channel to every convolutional layer will add a non-trivial
computational cost to the overall network. Second, the behavior of PadChannel
or encoding of certain positional information can be learned in the subsequent
layers. For instance, PadChannel can be achieved in the later layers through
the zeroing out of certain weights and the presence of a non-zero bias
corresponding to certain output channels. By only applying PadChannel to the
first layer, we provide the network with additional useful information while
avoiding a significant increase in the computational cost.

To ensure the consistency of our experiments, the modified convolutional
layers are initialized with weights using Kaiming initialization [3], as
typically done for convolutional layers in PyTorch.

###  3.2 Dataset and Data Augmentation

Our experimentations utilize the ImageNet-1K dataset, a popular choice for
image classification tasks, due to its extensive and diverse range of images
[1]. ImageNet-1K provides over a million labeled images across one thousand
different classes, offering a comprehensive and varied set of data crucial for
training robust and accurate models. This diversity in the dataset helps in
reducing model bias and improves generalizability, making it an ideal choice
for developing and benchmarking image classification algorithms.

The choice of ImageNet-1K is also motivated by its widespread use in the
machine learning community. Its standardization and consistent annotation
process ensure reliability and reproducibility in our experiments.

For data augmentation, we relied on the default transformations used by
PyTorch’s classification reference scripts [7]. These augmentations, which
include resizing, random crops, random horizontal flips, and color
normalizations during training, and resizing, centered crops, and color
normalization during evaluations, are crucial for preventing overfitting and
improving model robustness. The choice of these specific augmentations is
guided by their proven effectiveness in enhancing the performance of deep
learning models on the ImageNet dataset. By simulating various real-world
scenarios and introducing variability, these transformations help in training
models that are not only accurate but also resilient to variations in new,
unseen images.

###  3.3 Training Strategy

Models were trained using the official PyTorch recipes for each respective
architecture, guaranteeing standardized training procedures, with the
exceptions of the learning rate and the number of epochs. The learning rate
was scaled from the default 0.01 to 0.00125 as we trained the models on a
single GPU instead of eight GPUs as the recipe was designed for. Then, the
learning rate was divided by 10 every 30 epochs. As done by Wu et al. and G.
Liu et al., the models were trained for 100 epochs instead of the standard 90
[10, 5].

To ensure unbiased comparisons, the PadChannel-integrated models and their
regular counterparts were trained under identical conditions. To account for
variability during training, each network was trained 5 times, as done by G.
Liu et al., leading to a total of 40 sets of trained ImageNet-1K model weights
[5]. In this paper, other traditional padding methods aside from zero padding
are not explored, as they have already been well-reviewed by G. Liu et al.,
who found zero padding to generally be a good choice among the conventional
padding methods [5].

###  3.4 Hardware and Software Setup

The models were trained on a single NVIDIA 4090 GPU with Python 3.11.5,
PyTorch 2.0.1, and CUDA 11.7.

###  3.5 Evaluation Metrics

After each epoch, models were evaluated on the ImageNet-1K validation set [1].
To provide a high-level view of our models’ performances, we report the single
crop top-1 accuracies of each run by selecting the model checkpoint that
exhibits the highest validation set accuracy.

Additionally, to assess the computational efficiency of PadChannel, we report
the total number of parameters and multiply-accumulate operations (MACs) for
each model, highlighting the small to negligible increases in the
computational cost.

In summary, our methodology is designed to provide a rigorous and unbiased
assessment of PadChannel’s efficacy compared to the performances of baseline
models.

##  4 Results

Architecture | Best Top-1 | Mean | Stdev
---|---|---|---
Run 1 | Run 2 | Run 3 | Run 4 | Run 5
VGG11-BN | $71.276\%$ | $71.154\%$ | $70.894\%$ | $70.910\%$ | $71.120\%$ | $71.071\%$ | – | $0.165\%$ | –
VGG11-BN-PC | $70.940\%$ | $71.030\%$ | $71.058\%$ | $71.204\%$ | $71.120\%$ | $71.070\%$ | $-0.000\%$ | $0.099\%$ | $-0.066\%$
VGG16-BN | $74.070\%$ | $74.072\%$ | $74.308\%$ | $74.226\%$ | $74.412\%$ | $74.218\%$ | – | $0.149\%$ | –
VGG16-BN-PC | $74.270\%$ | $74.230\%$ | $74.122\%$ | $74.396\%$ | $74.184\%$ | $74.240\%$ | $+0.023\%$ | $0.103\%$ | $-0.046\%$
ResNet18 | $70.152\%$ | $70.496\%$ | $70.314\%$ | $70.250\%$ | $70.292\%$ | $70.301\%$ | – | $0.126\%$ | –
ResNet18-PC | $70.200\%$ | $70.292\%$ | $70.316\%$ | $70.506\%$ | $70.290\%$ | $70.321\%$ | $+0.020\%$ | $0.113\%$ | $-0.013\%$
ResNet50 | $76.286\%$ | $76.436\%$ | $76.372\%$ | $76.638\%$ | $76.428\%$ | $76.432\%$ | – | $0.130\%$ | –
ResNet50-PC | $76.582\%$ | $76.702\%$ | $76.780\%$ | $76.592\%$ | $76.546\%$ | $76.640\%$ | $+0.208\%$ | $0.097\%$ | $-0.032\%$
Table 1: The best single crop top-1 accuracies on the ImageNet-1K validation
set for each run. The checkpoint that yields the highest such value is
selected for each run. The model names with the suffix “-PC” denote that the
PadChannel was applied to the corresponding architecture.

The single crop best top-1 validation set accuracies for each run are shown in
Table 1. We observed that models incorporating PadChannel generally achieved
higher or at least similar mean validation set accuracy compared to their
counterparts without PadChannel. This trend is observable across different
models, though the extent of improvement varies. Specifically, for VGG11-BN,
there was an insignificant change in accuracy ($-0.000\%$), with a high
p-value of $0.5018$, indicating no statistical significance in the difference
observed. Similarly, for VGG16-BN and ResNet18, the increases in accuracy were
marginal ($+0.023\%$ and $+0.020\%$, respectively) and the p-values ($0.3928$
for VGG16-BN and $0.3988$ for ResNet18) suggest these differences are not
statistically significant.

In contrast, for ResNet50, we observed a more notable improvement in accuracy
($+0.208\%$), and the corresponding p-value of $0.0104$ indicates this
improvement is indeed statistically significant at the $5\%$ level. This
finding suggests that the implementation of PadChannel in the ResNet50
architecture led to a meaningful enhancement in model performance that is
unlikely to be due to chance.

These results are encouraging, as they imply that PadChannel does not
detrimentally impact model performance. In fact, in certain cases, it appears
to provide additional context for the models, aiding in the interpretation of
images. Notably, the greater success of PadChannel in ResNet architectures, as
evidenced by the statistical significance in the case of ResNet50, hints at
the possibility that the residual connections in these networks might be more
effective in utilizing the information provided by the fourth channel in
subsequent convolutional layers. The varying degrees of improvement and their
statistical significance across different architectures emphasize the need for
further investigation into how different network designs might interact with
additional channels like PadChannel.

In addition, consistent drops in the standard deviations of the validation set
accuracies are observed across all network architectures: VGG11-BN
($-0.066\%$); VGG16-BN ($-0.046\%$); ResNet18 ($-0.013\%$); ResNet50
($-0.032\%$). The presence of PadChannel seems to help stabilize the training
process. This observation suggests that the process of learning to discern the
boundary regions has a high variability and providing explicit information
regarding the padding statuses can facilitate a reduction in this variance.

Architecture | # Params | Diff | % Diff
---|---|---|---
w/o PC | w/ PC
VGG11-BN |  $132.9$M |  $132.9$M | $+576$ | $+0.0004\%$
VGG16-BN |  $138.4$M |  $138.4$M | $+576$ | $+0.0004\%$
ResNet18 |  $11.7$M |  $11.7$M | $+3136$ | $+0.027\%$
ResNet50 |  $25.6$M |  $25.6$M | $+3136$ | $+0.012\%$
Table 2: The number of parameters for each tested architecture with and without PadChannel. Architecture | GMACs | Diff | % Diff
---|---|---|---
w/o PC | w/ PC
VGG11-BN | $7.66$ | $7.69$ | $+0.03$ | $+0.377\%$
VGG16-BN | $15.55$ | $15.58$ | $+0.03$ | $+0.186\%$
ResNet18 | $1.83$ | $1.86$ | $+0.04$ | $+2.155\%$
ResNet50 | $4.13$ | $4.17$ | $+0.04$ | $+0.952\%$
Table 3: The Giga Multiply-Accumulate operations (GMACs) for each tested
architecture with and without PadChannel.

The numbers of parameters in the models with and without PadChannel are shown
in Table 2. The percentage increases in the number of parameters due to
PadChannel compared to the baseline models are in the hundredths for ResNet
models and ten-thousandths for VGG models. The GMACs for each model with and
without PadChannel are shown in Table 3. The table shows marginal increases in
the computational cost across all models ranging from $+0.186\%$ for VGG16-BN
to $+2.155\%$ for ResNet18.

Figure 4: The training curves for the ResNet50 models with and without
PadChannel.

Figure 4 illustrates the training curves representing the validation set
accuracies at each epoch, averaged across five runs, for the ResNet50 model
architecture with and without PadChannel. These curves indicate that models
equipped with PadChannel tend to reach specific accuracy benchmarks more
quickly than their counterparts without PadChannel. For instance, the curve
marked “with PC” achieves an accuracy of $75.75\%$ at Epoch $73$, while the
“without PC” curve reaches the same accuracy level three epochs later, at
Epoch $76$. This pattern demonstrates a faster convergence rate for models
incorporating PadChannel. The difference may be attributed to the additional
fourth channel, which potentially reduces the burden of learning to
distinguish the boundary regions. Consequently, the model can more efficiently
focus on interpreting the input features that are less influenced by padding.

##  5 Conclusion

This paper presented a novel padding technique: PadChannel. Through our
extensive evaluations, we demonstrated that this method not only increases the
accuracies of CNN architectures and reduces their variance in the image
classification task but also fosters faster convergence compared to the
standard models. The efficacy of PadChannel suggests that providing explicit
boundary information aids in the network’s feature discrimination ability, a
hypothesis that invites further theoretical investigation. Due to its
flexibility, PadChannel can easily be applied to other CNN architectures from
many domains not explored in this paper, including semantic segmentation,
object detection, and more by augmenting the corresponding architecture’s
first convolutional layer to incorporate PadChannel. Exploring the theoretical
foundations of PadChannel’s effectiveness, alongside its broader impact and
applicability, presents promising directions for future research.

##  6 Acknowledgment

We acknowledge the use of ChatGPT, based on GPT-4, an AI language model, in
order to enhance the readability of the paper by correcting grammar, polishing
language, and improving clarity throughout all sections [8].

## References

  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 248–255, 2009.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 1026–1034, 2015.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778, 2016.
  * Liu et al. [2023] Guilin Liu, Aysegul Dundar, Kevin J. Shih, Ting-Chun Wang, Fitsum A. Reda, Karan Sapra, Zhiding Yu, Xiaodong Yang, Andrew Tao, and Bryan Catanzaro.  Partial convolution for padding, inpainting, and image synthesis.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(5):6096–6110, 2023.
  * Liu et al. [2018] Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski.  An intriguing failing of convolutional neural networks and the coordconv solution.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pages 9628–9639, 2018.
  * maintainers and contributors [2016] TorchVision maintainers and contributors.  Torchvision: Pytorch’s computer vision library.  https://github.com/pytorch/vision, 2016.
  * OpenAI [2023] OpenAI.  Gpt-4 technical report, 2023.
  * Simonyan and Zisserman [2015] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition, 2015\.
  * Wu and He [2018] Yuxin Wu and Kaiming He.  Group normalization.  _arXiv:1803.08494_ , 2018.
  * Yu et al. [2019] Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S Huang.  Free-form image inpainting with gated convolution.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 4471–4480, 2019.


# Nonperiodic tilings related to Stern’s diatomic series and based on tiles
decorated with elements of $\mathbb{F}_{p}$

Rémy Sigrist

###### Abstract

This paper presents the construction and various properties of substitution
tilings related to Stern’s diatomic series and based on tiles decorated with
elements of $\mathbb{F}_{p}$ for some odd prime number $p$. These substitution
tilings are additive in a sense that will be clarified later and lead to new
nonperiodic tilings in one and two dimensions.

1.732

###### Contents

  1. 1 Introduction
  2. 2 Stern’s diatomic series
  3. 3 Substitution $\sigma$
    1. 3.1 Tiles
    2. 3.2 Substitution rule
    3. 3.3 Examples
    4. 3.4 Additivity
    5. 3.5 Symmetries
    6. 3.6 Positions within supertiles
    7. 3.7 Patterns of zeros
    8. 3.8 Irreducibility
    9. 3.9 Primitivity
  4. 4 Tiling $S_{t}$
    1. 4.1 Construction
    2. 4.2 Automaticity
    3. 4.3 Self-similarity
    4. 4.4 Nonperiodicity
  5. 5 Tiling $H_{b,c}$
    1. 5.1 Construction
    2. 5.2 Automaticity
    3. 5.3 Self-similarity
    4. 5.4 Nonperiodicity
  6. 6 One-dimensional case
    1. 6.1 Substitution $\tau$
    2. 6.2 Tiling $V_{y}$
    3. 6.3 Tiling $W_{t}$
  7. 7 Acknowledgments
  8. A Code sample (PARI/GP)
  9. B Other substitutions
    1. B.1 Substitution $\sigma_{1}$
    2. B.2 Substitution $\sigma_{2}$
    3. B.3 Substitution $\sigma_{3}$
    4. B.4 Substitution $\sigma_{4}$
    5. B.5 Substitution $\sigma_{5}$
    6. B.6 Substitution $\sigma_{6}$
    7. B.7 Substitution $\sigma_{7}$

##  1 Introduction

Substitution tilings form a fascinating area of mathematics at the confluence
of several lines of research. For an introduction to the theory of
substitution tilings, see Priebe [5]. Also, the Tilings Encyclopedia [2]
provides a wealth of examples of nonperiodic substitution tilings.

In this paper, we will present a two-dimensional substitution $\sigma$ and a
one-dimensional substitution $\tau$ with construction rules similar to that of
Stern’s diatomic series, based on tiles decorated with elements of
$\mathbb{F}_{p}$ for some odd prime number $p$. We will describe the
construction, various properties, including additivity and primitivity, and
tilings for both substitutions. These tilings will be shown to be automatic,
self-similar and nonperiodic.

The usage of finite fields in the framework of aperiodic tilings was
previously explored by Prunescu [6].

######  Definition 1.1.

Throughout this document, and unless defined explicitly, $p$ will denote an
arbitrary odd prime number, $\mathbb{F}_{p}$ will correspond to the finite
field of order $p$, and $\mathbb{F}_{p}^{*}=\mathbb{F}_{p}\setminus\\{0\\}$.

##  2 Stern’s diatomic series

######  Definition 2.1.

Stern’s diatomic series (see Lehmer [3]) can be computed by the following
procedure (see figure 1):

  * •

start with an array of two values: $0$ and $1$,

  * •

repeatedly: insert between each pair of adjacent values, say $x$ and $y$, the
value $x+y$,

  * •

the limiting array is Stern’s diatomic series.

010110112101121323101121323143525341

Figure 1: The construction of Stern’s diatomic series

######  Remark 2.2.

The substitutions $\sigma$ and $\tau$ will use a similar construction rule:

  * •

start with “sites” decorated with “values” (in our context: taken from
$\mathbb{F}_{p}$),

  * •

repeatedly: insert between each pair of “adjacent” sites, say decorated with
values $x$ and $y$, a new site decorated with the value $x+y$.

######  Definition 2.3.

Stern’s diatomic series is also known as Dijkstra’s “fusc” function (see OEIS
[4] sequence A002487). The “fusc” function satisfies:

$fusc(0)=0$ (1) $fusc(1)=1$ (2) $fusc(2n)=fusc(n)$ (3)
$fusc(2n+1)=fusc(n)+fusc(n+1)$ (4)

##  3 Substitution $\sigma$

This section presents the construction, associated notations and various
properties of the substitution $\sigma$.

These notations and properties will allow us to build tilings of the plane in
sections 4 and 5, and provide tools to prove that these tilings are automatic,
self-similar and nonperiodic.

The substitution $\sigma$ is related to the OEIS [4] sequence A355855.

###  3.1 Tiles

######  Definition 3.1.

The tiles on which the substitution $\sigma$ operates correspond to
equilateral triangles with unit side length whose corners are decorated with
elements of $\mathbb{F}_{p}$ and oriented either upwards or downwards as
depicted in figure 2:

  * •

the upward tile whose bottom left, bottom right and top corners are
respectively decorated with the values $x$, $y$ and $z$ will be denoted by
$\bigtriangleup(x,y,z)$ (or $\bigtriangleup xyz$ when there is no ambiguity),

  * •

the downward tile whose top right, top left and bottom corners are
respectively decorated with the values $x$, $y$ and $z$ will be denoted by
$\bigtriangledown(x,y,z)$ (or $\bigtriangledown xyz$ when there is no
ambiguity).

$x$$y$$z$$x$$y$$z$

Figure 2: The upward tile $\bigtriangleup xyz$ and the downward tile
$\bigtriangledown xyz$

######  Definition 3.2.

The sets of upward, downward and all tiles will be denoted, respectively, by
$U$, $D$ and $T$:

$U=\\{\bigtriangleup xyz\mid x,y,z\in\mathbb{F}_{p}\\}$ (5)
$D=\\{\bigtriangledown xyz\mid x,y,z\in\mathbb{F}_{p}\\}$ (6) $T=U\cup D$ (7)

######  Definition 3.3.

We will also be interested in sets of tiles having at least one nonzero
corner:

$U^{*}=U\setminus\\{\bigtriangleup 000\\}$ (8)
$D^{*}=D\setminus\\{\bigtriangledown 000\\}$ (9) $T^{*}=U^{*}\cup D^{*}$ (10)

######  Definition 3.4.

We will associate to any tile $t$ the row matrix $[t]$ with the values at its
three corners as follows: $\forall x,y,z\in\mathbb{F}_{p}$:

$[\bigtriangleup xyz]=[\bigtriangledown xyz]=[x\ y\ z]$ (11)

###  3.2 Substitution rule

######  Definition 3.5.

The substitution $\sigma$ transforms a tile into four tiles as depicted in
figures 3 and 4.

$\rightarrow$$x$$y$$z$$x$$x+y$$x+z$$x+z$$y+z$$z$$x+y$$y$$y+z$$y+z$$x+z$$x+y$

Figure 3: The substitution rule for the upward tile $\bigtriangleup xyz$

$\rightarrow$$x$$y$$z$$x$$x+y$$x+z$$x+z$$y+z$$z$$x+y$$y$$y+z$$y+z$$x+z$$x+y$

Figure 4: The substitution rule for the downward tile $\bigtriangledown xyz$

######  Definition 3.6.

$\forall k\in\mathbb{N}$, $\forall t\in T$, $\sigma^{k}(t)$ is called a
“$k$-supertile” or simply a “supertile”. A subset of tiles in a supertile is
called a “patch”.

######  Definition 3.7.

As depicted in figure 5:

  * •

$\forall u\in U$: the central, bottom left, bottom right and top tile in
$\sigma(u)$ will be denoted respectively by $\alpha(u)$, $\beta(u)$,
$\gamma(u)$ and $\delta(u)$,

  * •

$\forall d\in D$: the central, top right, top left and bottom tile in
$\sigma(d)$ will be denoted respectively by $\alpha(d)$, $\beta(d)$,
$\gamma(d)$ and $\delta(d)$.

$\alpha(u)$$\beta(u)$$\gamma(u)$$\delta(u)$$\sigma(u)$$\alpha(d)$$\beta(d)$$\gamma(d)$$\delta(d)$$\sigma(d)$

Figure 5: Tiles in $1$-supertiles

######  Lemma 3.8.

$\forall t\in T$, using the notation introduced in definition 3.4, we can
conveniently relate $\alpha(t)$, $\beta(t)$, $\gamma(t)$ and $\delta(t)$ to
$t$ by means of multiplication by certain matrices $A$, $B$, $C$ and $D$ as
follows:

$[\alpha(t)]=[t]\cdot\underbrace{\begin{bmatrix}0&1&1\\\ 1&0&1\\\
1&1&0\end{bmatrix}}_{A}$ (12)
$[\beta(t)]=[t]\cdot\underbrace{\begin{bmatrix}1&1&1\\\ 0&1&0\\\
0&0&1\end{bmatrix}}_{B}$ (13)
$[\gamma(t)]=[t]\cdot\underbrace{\begin{bmatrix}1&0&0\\\ 1&1&1\\\
0&0&1\end{bmatrix}}_{C}$ (14)
$[\delta(t)]=[t]\cdot\underbrace{\begin{bmatrix}1&0&0\\\ 0&1&0\\\
1&1&1\end{bmatrix}}_{D}$ (15)

###### Proof.

$\forall x,y,z\in\mathbb{F}_{p}$:

$[\alpha(\bigtriangleup xyz)]=[\bigtriangledown(y+z,x+z,x+y)]=[y+z\ x+z\
x+y]=[x\ y\ z]\cdot A=[\bigtriangleup xyz]\cdot A$ (16) $[\beta(\bigtriangleup
xyz)]=[\bigtriangleup(x,x+y,x+z)]=[x\ x+y\ x+z]=[x\ y\ z]\cdot
B=[\bigtriangleup xyz]\cdot B$ (17)

The other cases are similar. ∎

######  Lemma 3.9.

The matrices $A$, $B$, $C$ and $D$ are invertible in $\mathbb{F}_{p}^{3\times
3}$.

###### Proof.

$\det(A)=2$ (18) $\det(B)=\det(C)=\det(D)=1$ (19)

∎

######  Remark 3.10.

The matrix $A$ is not invertible in $\mathbb{F}_{2}^{3\times 3}$.

######  Lemma 3.11.

The functions $\alpha$, $\beta$, $\gamma$ and $\delta$ are permutations of
$T$.

###### Proof.

This is a consequence of lemmas 3.8 and 3.9 and of the fact that $\alpha$
inverts tile orientations, and $\beta$, $\gamma$ and $\delta$ preserve tile
orientations. ∎

######  Lemma 3.12.

$\forall k\in\mathbb{N}$, $\forall t\in T$, the values at the three extreme
corners of $\sigma^{k}(t)$ are exactly the values at the corners of $t$.

###### Proof.

The property is trivially satisfied for all $0$-supertiles (i.e. for all
tiles).

Suppose that, for some $k\in\mathbb{N}$, the property is satisfied for all
$k$-supertiles.

Applying $\sigma$ again to some upward $k$-supertile $s$:

  * •

let $t$ be the tile at the bottom left corner of $s$,

  * •

$\beta(t)$ is the tile at the bottom left corner of $\sigma(s)$,

  * •

$\forall x,y,z\in\mathbb{F}_{p}$, $\beta(\bigtriangleup
xyz)=\bigtriangleup(x,x+y,x+z)$, so $\beta$ preserves values at bottom left
corners,

  * •

hence the bottom left corners of $s$ and $\sigma(s)$ hold the same value,

  * •

the reasoning for the bottom right and top corners is similar.

The reasoning for downward $k$-supertiles is identical. ∎

######  Definition 3.13.

Following lemma 3.12, we will associate to any supertile $s$ the row matrix
$[s]$ with the values at its three extreme corners as follows: $\forall
k\in\mathbb{N}$, $\forall t\in T$:

$[\sigma^{k}(t)]=[t]$ (20)

######  Lemma 3.14.

For any supertile, the corners that meet at the same point hold the same
value.

###### Proof.

The property is trivially satisfied for all $0$-supertiles (i.e. for all
tiles) as only one corner can meet at a given point.

Suppose that, for some $k\in\mathbb{N}$, the property is satisfied for all
$k$-supertiles.

Applying $\sigma$ again to some $k$-supertile $s$,

  * •

the corners added and meeting in the middle of an edge in contact with a
single tile will hold the same value (see figures 3 and 4),

  * •

the corners added and meeting in the middle of a common edge to two tiles of
$s$ only depend on the values at the ends of this edge, say $v$ and $w$, and
they will hold the same value $v+w$ (see figure 6).

∎

$v$$w$$v$$w$$\rightarrow$$v$$v$$w$$w$$v+w$$v+w$$v+w$$v+w$$v+w$$v+w$

Figure 6: The corners that meet at the same point hold the same value.

We will therefore, from now on, simplify the figures by indicating just the
values where the corners meet (see figure 7).

$\rightarrow$$x$$z$$y$$x$$x+z$$z$$x+y$$y+z$$y$

Figure 7: The “simplified” substitution rule for the upward tile
$\bigtriangleup xyz$

###  3.3 Examples

Figure 8 depicts $\sigma^{k}(\bigtriangleup 122)$ for
$k=0\mathinner{\ldotp\ldotp}2$ (for $p=3$); values are given numerically.

122100122111000120212102

Figure 8: $\sigma^{k}(\bigtriangleup 122)$ for $k=0\mathinner{\ldotp\ldotp}2$
(for $p=3$)

Replacing numerical values by colors gives greater insight into the variety of
patterns; the next examples will use the following color schemes:

  * •

for $p=3$: white = $0$, blue = $1$ and red = $2$; see figures 9, 10 and 11,

  * •

for $p=5$: white = $0$, cyan = $1$ magenta = $2$, yellow = $3$ and black =
$4$; see figures 12 and 13.

$1$$2$$2$$1$$0$$0$$0$$2$$1$$0$$1$$2$$0$$0$$1$$1$$1$$1$$1$$0$$0$$1$$0$$0$$1$$1$$0$$0$$2$$1$$2$$2$$0$$1$$0$$1$$2$$1$$0$$0$$1$$2$$1$$1$$0$$2$$0$$2$$1$$2$$0$$0$$0$$1$$0$$0$$1$$1$$1$$1$$0$$1$$1$

Figure 9: Colored representation of $\sigma^{k}(\bigtriangleup 122)$ for
$k=0\mathinner{\ldotp\ldotp}2$ (for $p=3$)

Figure 10: Colored representation of $\sigma^{k}(\bigtriangleup 122)$ for
$k=0\mathinner{\ldotp\ldotp}3$ (for $p=3$)

1.732

Figure 11: Colored representation of $\sigma^{8}(\bigtriangleup 121)$ (for
$p=3$)

Figure 12: Colored representation of $\sigma^{k}(\bigtriangleup 123)$ for
$k=0\mathinner{\ldotp\ldotp}3$ (for $p=5$)

1.732

Figure 13: Colored representation of $\sigma^{8}(\bigtriangleup 111)$ (for
$p=5$)

###  3.4 Additivity

######  Lemma 3.15.

$\forall k\in\mathbb{N}$, $\forall
m,x,y,z,x^{\prime},y^{\prime},z^{\prime}\in\mathbb{F}_{p}$, we have the
following identities:

$\sigma^{k}(\bigtriangleup xyz)+\sigma^{k}(\bigtriangleup
x^{\prime}y^{\prime}z^{\prime})=\sigma^{k}(\bigtriangleup(x+x^{\prime},y+y^{\prime},z+z^{\prime}))$
(21) $m\cdot\sigma^{k}(\bigtriangleup
xyz)=\sigma^{k}(\bigtriangleup(mx,my,mz))$ (22)

and also:

$\sigma^{k}(\bigtriangledown xyz)+\sigma^{k}(\bigtriangledown
x^{\prime}y^{\prime}z^{\prime})=\sigma^{k}(\bigtriangledown(x+x^{\prime},y+y^{\prime},z+z^{\prime}))$
(23) $m\cdot\sigma^{k}(\bigtriangledown
xyz)=\sigma^{k}(\bigtriangledown(mx,my,mz))$ (24)

where additions and scalar multiplications on supertiles are performed
componentwise on each corner (see figure 14 and 15).

###### Proof.

The property is satisfied for all $0$-supertiles (i.e. for all tiles);
$\forall m,x,y,z,x^{\prime},y^{\prime},z^{\prime}\in\mathbb{F}_{p}$:

$\bigtriangleup xyz+\bigtriangleup
x^{\prime}y^{\prime}z^{\prime}=\bigtriangleup(x+x^{\prime},y+y^{\prime},z+z^{\prime})$
(25) $m\cdot\bigtriangleup xyz=\bigtriangleup(mx,my,mz)$ (26)

Suppose that, for some $k\in\mathbb{N}$, the property is satisfied for all
$k$-supertiles.

For any $k$-supertile $s$, $\sigma(s)$ is obtained by applying $\sigma$ to
each tile in $s$, so we just have to prove that $\sigma$ is additive, which is
equivalent to prove that $\alpha$, $\beta$, $\gamma$ and $\delta$ are
additive.

$\forall m,x,y,z,x^{\prime},y^{\prime},z^{\prime}\in\mathbb{F}_{p}$:

$\displaystyle\alpha(\bigtriangleup xyz+\bigtriangleup
x^{\prime}y^{\prime}z^{\prime})$
$\displaystyle=\alpha(\bigtriangleup(x+x^{\prime},y+y^{\prime},z+z^{\prime}))$
(27)
$\displaystyle=\bigtriangledown(y+y^{\prime}+z+z^{\prime},x+x^{\prime}+z+z^{\prime},x+x^{\prime}+y+y^{\prime})$
(28)
$\displaystyle=\bigtriangledown(y+z,x+z,x+y)+\bigtriangledown(y^{\prime}+z^{\prime},x^{\prime}+z^{\prime},x^{\prime}+y^{\prime})$
(29) $\displaystyle=\alpha(\bigtriangleup xyz)+\alpha(\bigtriangleup
x^{\prime}y^{\prime}z^{\prime})$ (30)
$\displaystyle\alpha(m\cdot\bigtriangleup xyz)$
$\displaystyle=\alpha(\bigtriangleup(mx,my,mz))$ (31)
$\displaystyle=\bigtriangledown(my+mz,mx+mz,mx+my)$ (32)
$\displaystyle=m\cdot\bigtriangledown(y+z,x+z,x+y)$ (33)
$\displaystyle=m\cdot\alpha(\bigtriangleup xyz)$ (34)

The reasoning for the other cases is identical. ∎

+=$1$$0$$2$$0$$1$$2$$2$$1$$1$$0$$1$$0$$0$$2$$1$$0$$2$$1$$0$$1$$2$$1$$2$$1$$1$$0$$1$$2$$2$$2$$1$$2$$0$$0$$2$$1$$0$$0$$2$$1$$1$$1$$2$$1$$0$

Figure 14: $\sigma^{2}(\bigtriangleup 110)+\sigma^{2}(\bigtriangleup
021)=\sigma^{2}(\bigtriangleup 101)$ (for $p=3$)

$2\cdot$$=$$1$$4$$0$$4$$3$$2$$0$$2$$4$$4$$0$$2$$3$$0$$3$$0$$2$$2$$3$$2$$0$$0$$3$$2$$4$$4$$2$$4$$0$$3$$2$$3$$3$$4$$2$$3$$3$$2$$3$$2$$4$$4$$3$$4$$0$$2$$3$$4$$2$$3$$0$$3$$1$$4$$0$$4$$3$$3$$0$$4$$1$$0$$1$$0$$4$$4$$1$$4$$0$$0$$1$$4$$3$$3$$4$$3$$0$$1$$4$$1$$1$$3$$4$$1$$1$$4$$1$$4$$3$$3$$1$$3$$0$$4$$1$$3$

Figure 15: $2\cdot\sigma^{2}(\bigtriangleup 123)=\sigma^{2}(\bigtriangleup
241)$ (for $p=5$)

######  Remark 3.16.

These identities are reminiscent of generalized additivity in some elementary
cellular automata discovered by Wolfram [8].

###  3.5 Symmetries

$\forall k\in\mathbb{N}$, $\forall x,y,z\in\mathbb{F}_{p}$:

  * •

if $x=y=z$ then $\sigma^{k}(\bigtriangleup xyz)$ and
$\sigma^{k}(\bigtriangledown xyz)$ have reflection and 3-fold rotational
symmetries (see figure 13),

  * •

if $x=y$ or $y=z$ or $z=x$ then $\sigma^{k}(\bigtriangleup xyz)$ and
$\sigma^{k}(\bigtriangledown xyz)$ have reflection symmetry (see figure 11),

  * •

if one of $x$, $y$ or $z$ is $0$ and the two others values sum to $0$ (i.e.,
the two other values are opposite) then $\sigma^{k}(\bigtriangleup xyz)$ and
$\sigma^{k}(\bigtriangledown xyz)$ have reflection “odd” symmetry: the values
at two symmetrical corners with respect to the bisector passing through the
corner of value $0$ are opposite (see figure 27).

Some patches can induce other types of symmetry (see for example remark 5.10).

###  3.6 Positions within supertiles

######  Definition 3.17.

Let:

$\Sigma=\\{\alpha,\beta,\gamma,\delta\\}$ (35)

######  Remark 3.18.

$\Sigma$ will be used as an alphabet:

  * •

$\forall k\in\mathbb{N}$, $\Sigma^{k}$ will denote the set of words of length
$k$ over $\Sigma$,

  * •

$\varepsilon$ will denote the “empty word” (i.e. the only element of
$\Sigma^{0}$),

  * •

$\Sigma^{*}=\bigcup_{k\in\mathbb{N}}\Sigma^{k}$ will denote the set of finite
words over $\Sigma$,

  * •

$\forall d\in\Sigma$, $\forall k\in\mathbb{N}$, “$d^{k}$” will denote “$d$
repeated $k$ times”,

  * •

$\forall k,k^{\prime}\in\mathbb{N}$, $\forall w\in\Sigma^{k}$, $\forall
w^{\prime}\in\Sigma^{k^{\prime}}$, “$ww^{\prime}$” will denote the
“concatenation of $w$ and $w^{\prime}$” (and will belong to
$\Sigma^{k+k^{\prime}}$).

######  Definition 3.19.

$\forall k\in\mathbb{N}$, a $(k+1)$-supertile contains four $k$-supertiles
(see figure 16):

  * •

for an upward $(k+1)$-supertile $s$: the central, bottom left, bottom right
and top $k$-supertiles within $s$ will be respectively given positions
$\alpha$, $\beta$, $\gamma$ and $\delta$,

  * •

for a downward $(k+1)$-supertile $s$: the central, top right, top left and
bottom $k$-supertiles within $s$ will be respectively given positions
$\alpha$, $\beta$, $\gamma$ and $\delta$.

$\alpha$$\beta$$\gamma$$\delta$$\alpha$$\beta$$\gamma$$\delta$

Figure 16: Positions within supertiles

######  Theorem 3.20.

$\forall k\in\mathbb{N}$, the position of any tile $t$ within a $k$-supertile
is uniquely defined by a word $w\in\Sigma^{k}$ such that $\forall n\in
0\mathinner{\ldotp\ldotp}k-1$, $w_{n}$ is the position of the
$(k-n-1)$-supertile containing $t$ within the $(k-n)$-supertile containing $t$
(see figure 17).

###### Proof.

The property is satisfied for all $0$-supertiles (i.e. for all tiles):
$0$-supertiles contain a unique tile whose position correspond to the empty
word $\varepsilon$.

Suppose that, for some $k\in\mathbb{N}$, the property is satisfied for all
$k$-supertiles.

A tile $t$ in a $(k+1)$-supertile $s$ belongs to one of the four
$k$-supertiles $s^{\prime}$ in $s$. If $s^{\prime}$ is at position $d$ in $s$,
and $t$ is at position $w$ in $s^{\prime}$, then $t$ is at position $dw$ in
$s$. ∎

$\varepsilon$$\varepsilon$$\alpha$$\beta$$\gamma$$\delta$$\alpha$$\beta$$\gamma$$\delta$$\alpha\alpha$$\alpha\beta$$\alpha\gamma$$\alpha\delta$$\beta\alpha$$\beta\beta$$\beta\gamma$$\beta\delta$$\gamma\alpha$$\gamma\beta$$\gamma\gamma$$\gamma\delta$$\delta\alpha$$\delta\beta$$\delta\gamma$$\delta\delta$$\alpha\alpha$$\alpha\beta$$\alpha\gamma$$\alpha\delta$$\beta\alpha$$\beta\beta$$\beta\gamma$$\beta\delta$$\gamma\alpha$$\gamma\beta$$\gamma\gamma$$\gamma\delta$$\delta\alpha$$\delta\beta$$\delta\gamma$$\delta\delta$$\alpha\alpha\alpha$$\alpha\alpha\beta$$\alpha\alpha\gamma$$\alpha\alpha\delta$$\alpha\beta\alpha$$\alpha\beta\beta$$\alpha\beta\gamma$$\alpha\beta\delta$$\alpha\gamma\alpha$$\alpha\gamma\beta$$\alpha\gamma\gamma$$\alpha\gamma\delta$$\alpha\delta\alpha$$\alpha\delta\beta$$\alpha\delta\gamma$$\alpha\delta\delta$$\beta\alpha\alpha$$\beta\alpha\beta$$\beta\alpha\gamma$$\beta\alpha\delta$$\beta\beta\alpha$$\beta\beta\beta$$\beta\beta\gamma$$\beta\beta\delta$$\beta\gamma\alpha$$\beta\gamma\beta$$\beta\gamma\gamma$$\beta\gamma\delta$$\beta\delta\alpha$$\beta\delta\beta$$\beta\delta\gamma$$\beta\delta\delta$$\gamma\alpha\alpha$$\gamma\alpha\beta$$\gamma\alpha\gamma$$\gamma\alpha\delta$$\gamma\beta\alpha$$\gamma\beta\beta$$\gamma\beta\gamma$$\gamma\beta\delta$$\gamma\gamma\alpha$$\gamma\gamma\beta$$\gamma\gamma\gamma$$\gamma\gamma\delta$$\gamma\delta\alpha$$\gamma\delta\beta$$\gamma\delta\gamma$$\gamma\delta\delta$$\delta\alpha\alpha$$\delta\alpha\beta$$\delta\alpha\gamma$$\delta\alpha\delta$$\delta\beta\alpha$$\delta\beta\beta$$\delta\beta\gamma$$\delta\beta\delta$$\delta\gamma\alpha$$\delta\gamma\beta$$\delta\gamma\gamma$$\delta\gamma\delta$$\delta\delta\alpha$$\delta\delta\beta$$\delta\delta\gamma$$\delta\delta\delta$$\alpha\alpha\alpha$$\alpha\alpha\beta$$\alpha\alpha\gamma$$\alpha\alpha\delta$$\alpha\beta\alpha$$\alpha\beta\beta$$\alpha\beta\gamma$$\alpha\beta\delta$$\alpha\gamma\alpha$$\alpha\gamma\beta$$\alpha\gamma\gamma$$\alpha\gamma\delta$$\alpha\delta\alpha$$\alpha\delta\beta$$\alpha\delta\gamma$$\alpha\delta\delta$$\beta\alpha\alpha$$\beta\alpha\beta$$\beta\alpha\gamma$$\beta\alpha\delta$$\beta\beta\alpha$$\beta\beta\beta$$\beta\beta\gamma$$\beta\beta\delta$$\beta\gamma\alpha$$\beta\gamma\beta$$\beta\gamma\gamma$$\beta\gamma\delta$$\beta\delta\alpha$$\beta\delta\beta$$\beta\delta\gamma$$\beta\delta\delta$$\gamma\alpha\alpha$$\gamma\alpha\beta$$\gamma\alpha\gamma$$\gamma\alpha\delta$$\gamma\beta\alpha$$\gamma\beta\beta$$\gamma\beta\gamma$$\gamma\beta\delta$$\gamma\gamma\alpha$$\gamma\gamma\beta$$\gamma\gamma\gamma$$\gamma\gamma\delta$$\gamma\delta\alpha$$\gamma\delta\beta$$\gamma\delta\gamma$$\gamma\delta\delta$$\delta\alpha\alpha$$\delta\alpha\beta$$\delta\alpha\gamma$$\delta\alpha\delta$$\delta\beta\alpha$$\delta\beta\beta$$\delta\beta\gamma$$\delta\beta\delta$$\delta\gamma\alpha$$\delta\gamma\beta$$\delta\gamma\gamma$$\delta\gamma\delta$$\delta\delta\alpha$$\delta\delta\beta$$\delta\delta\gamma$$\delta\delta\delta$

Figure 17: Positions within $k$-supertiles for $k=0\mathinner{\ldotp\ldotp}3$

######  Remark 3.21.

$\forall k\in\mathbb{N}$, within a $k$-supertile $s$:

  * •

the central tile has position $\alpha^{k}$,

  * •

the bottom left tile (when $s$ is upward) or the top right tile (when $s$ is
downward) has position $\beta^{k}$,

  * •

the bottom right tile (when $s$ is upward) or the top left tile (when $s$ is
downward) has position $\gamma^{k}$,

  * •

the top tile (when $s$ is upward) or the bottom tile (when $s$ is downward)
has position $\delta^{k}$.

######  Lemma 3.22.

A tile $t$ at position $w$ within a supertile $s$ has the same orientation as
$s$ if and only if the number of $\alpha$’s in $w$ is even.

###### Proof.

The position $w$ of a tile $t$ within a supertile $s$ can be interpreted as a
descent from $s$ to $t$, where each $\alpha$ induces an inversion of
orientation. Those inversions are canceled when they occur an even number of
times. ∎

######  Definition 3.23.

Similarly to definition 3.13, we will associate to any position $d\in\Sigma$
the square matrix $[d]$ as follows:

$[\alpha]=A$ (36) $[\beta]=B$ (37) $[\gamma]=C$ (38) $[\delta]=D$ (39)

Also, $\forall k\in\mathbb{N}$, $\forall w\in\Sigma^{k}$:

$[w]=[w_{0}]\mathinner{\ldotp\ldotp}[w_{k-1}]$ (40)

In particular:

$[\varepsilon]=I_{3}$ (41)

######  Theorem 3.24.

For any supertile $s$, and any tile $t$ at position $w$ in $s$:

$[t]=[s]\cdot[w]$ (42)

###### Proof.

The property is satisfied for $0$-supertiles (i.e. for tiles): $\forall t\in
T$:

$[t]\cdot[\varepsilon]=[t]\cdot I_{3}=[t]$ (43)

Suppose that, for some $k\in\mathbb{N}$, the property is satisfied for all
$k$-supertiles.

For any $(k+1)$-supertile $s$, and any tile $t$ within $s$: $t$ appears at
position $w$ within some $k$-supertile $s^{\prime}$ at position $d$ within $s$
(and the position of $t$ within $s$ is $dw$).

$[s^{\prime}]=[s]\cdot[d]$ (44) $[t]=[s^{\prime}]\cdot[w]$ (45)

Hence:

$[t]=[s]\cdot[d][w]=[s]\cdot[dw]$ (46)

∎

######  Lemma 3.25.

A supertile $s$ is uniquely determined by one of its tile $t$ and the position
$w$ of $t$ within $s$.

###### Proof.

From theorem 3.24, we can write:

$[s]=[t]\cdot[w]^{-1}$ (47)

Also, lemma 3.22 relates the orientations of $t$ and $s$. ∎

###  3.7 Patterns of zeros

######  Lemma 3.26.

A supertile $s$ contains an all-zero tile ($\bigtriangleup 000$ or
$\bigtriangledown 000$) if and only if $s$ was built starting from an all-zero
tile.

###### Proof.

If $s$ contains $t\in\\{\bigtriangleup 000,\bigtriangledown 000\\}$, say at
position $w$, then:

$[s]=[t]\cdot[w]^{-1}=[0\ 0\ 0]\cdot[w]^{-1}=[0\ 0\ 0]$ (48)

∎

######  Lemma 3.27.

$\forall m\in\mathbb{F}_{p}^{*}$, $\forall k\in\mathbb{N}$, $\forall t\in T$,
the $0$’s at the corners of $m\cdot\sigma^{k}(t)$ and $\sigma^{k}(t)$ are
exactly located at the same places.

###### Proof.

This is a consequence of additivity (see section 3.4). ∎

Figure 18 represents $0$’s in $\sigma^{9}(\bigtriangleup 100)$ and
$\sigma^{9}(\bigtriangleup 200)$ (for $p=3$).

1.732

Figure 18: Representation of $0$’s (as black pixels) in
$\sigma^{9}(\bigtriangleup 100)$ and $\sigma^{9}(\bigtriangleup 200)$ (for
$p=5$)

######  Lemma 3.28.

Tiles with two $0$’s and some other value $c$ will yield lines of $0$’s and
$c$’s parallel to the side holding the two $0$’s upon repeated applications of
$\sigma$. This pattern is visible in figures 10, 11 and 13 as white and
colored lines respectively for $0$’s and $c$’s.

###### Proof.

See figure 19. ∎

$0$$0$$c$$\rightarrow$$0$$0$$0$$c$$c$$\rightarrow$$0$$0$$0$$0$$0$$c$$c$$c$$c$
Figure 19: Lines of $0$’s and $c$’s

######  Lemma 3.29.

Tiles with one $0$ and two opposite other values $+c$ and $-c$ will yield
lines alternating $0$’s and opposite pairs $+c$ / $-c$ upon repeated
applications of $\sigma$. This pattern passes though the center of figure 27.

###### Proof.

See figure 20. ∎

$0$$-c$$+c$$\rightarrow$$0$$-c$$+c$$0$$\rightarrow$$0$$0$$0$$-c$$-c$$+c$$+c$
Figure 20: Lines alternating $0$’s and opposite pairs $+c$ / $-c$

######  Lemma 3.30.

Tiles with one $0$ remain in the corner holding that $0$ upon repeated
applications of $\sigma$.

###### Proof.

See figure 21. ∎

$0$$c$$d$$\rightarrow$$0$$c$$d$ Figure 21: Persistence of $0$’s at corners

######  Lemma 3.31.

$\forall k\in\mathbb{N}$, $\forall t\in\\{\bigtriangleup 100,\bigtriangleup
010,\bigtriangleup 001,\bigtriangledown 100,\bigtriangledown
010,\bigtriangledown 001\\}$, the values at three corners forming an
equilateral triangle in $\sigma^{k}(t)$ with the same center as
$\sigma^{k}(t)$ cannot all equal $0$ (see figure 22).

###### Proof.

If this was the case, say for $\sigma^{k}(\bigtriangleup 100)$, then, by
symmetry, the values at the same three corners in $\sigma^{k}(\bigtriangleup
010)$ and in $\sigma^{k}(\bigtriangleup 001)$ would also equal $0$. Due to
additivity ($\bigtriangleup xyz=x\cdot\bigtriangleup 100+y\cdot\bigtriangleup
010+z\cdot\bigtriangleup 001$), the values at the same three corners in any
upward $k$-supertile would equal $0$. This is a contradiction as from lemma
3.25, we can force a nonzero value at one of these three corners.

The reasoning for downward supertiles is similar. ∎

$\sigma^{k}(t)$ Figure 22: Three corners forming an equilateral triangle with
the same center as $\sigma^{k}(t)$

###  3.8 Irreducibility

######  Theorem 3.32.

$(T^{*},\sigma)$ is irreducible.

###### Proof.

$\forall t,t^{\prime}\in T$, let the relation $t\sim t^{\prime}$ mean that
$\exists k\in\mathbb{N}$ such that $t^{\prime}$ appears in $\sigma^{k}(t)$.

The relation “$\sim$” is naturally reflexive and transitive:

  * •

$t$ appears in $\sigma^{0}(t)$,

  * •

if $t^{\prime}$ appears in $\sigma^{k}(t)$ and $t^{\prime\prime}$ appears in
$\sigma^{k^{\prime}}(t^{\prime})$, then $t^{\prime\prime}$ appears in
$\sigma^{k+k^{\prime}}(t)$.

######  Lemma 3.33.

$\forall x,y,z\in\mathbb{F}_{p}$, $\bigtriangleup
xyz\sim\bigtriangleup(x,x+y,x+z)$.

$\bigtriangleup(x,x+y,x+z)$ appears in $\sigma(\bigtriangleup xyz)$ (see
figure 3).

######  Lemma 3.34.

$\forall x\in\mathbb{F}_{p}^{*}$, $\forall d,y,z\in\mathbb{F}_{p}$,
$\bigtriangleup xyz\sim\bigtriangleup(x,d+y,d+z)$.

Applying lemma 3.33 $k$ times, we have $\bigtriangleup
xyz\sim\bigtriangleup(x,kx+y,kx+z)$. As $x$ is invertible, $k\rightarrow kx$
runs through $\mathbb{F}_{p}$.

######  Lemma 3.35.

$\forall y\in\mathbb{F}_{p}^{*}$, $\forall d,x,z\in\mathbb{F}_{p}$,
$\bigtriangleup xyz\sim\bigtriangleup(d+x,y,d+z)$.

Similar to lemma 3.34.

######  Lemma 3.36.

$\forall z\in\mathbb{F}_{p}^{*}$, $\forall d,x,y\in\mathbb{F}_{p}$,
$\bigtriangleup xyz\sim\bigtriangleup(d+x,d+y,z)$.

Similar to lemma 3.34.

######  Lemma 3.37.

$\forall x,y,z\in\mathbb{F}_{p}$, when $(y,z)\neq(0,0)$, $\bigtriangleup
xyz\sim\bigtriangleup(x+2,y,z)$.

To show $\bigtriangleup xyz\sim\bigtriangleup(x+2,y,z)$, we will apply each of
the lemmas 3.35, 3.36 and 3.37 once, in some appropriate order, based on the
following identity:

$\bigtriangleup 200=\bigtriangleup 101+\bigtriangleup 110-\bigtriangleup 011$
(49)

Figure 23 describes the different cases to consider and table 1 indicates an
appropriate order of lemmas for each case.

$y=0$$y=1$$y\neq 0,1$$x=0$$x\neq 0$$x=0$$x\neq 0,p-1$$x=p-1$$x=0$$x\neq
0$$z=0$db$z=1$aaecd$z\neq 0,1$aabce

Figure 23: Different cases for lemma 3.37 Case | Order of lemmas
---|---
a | $\bigtriangleup xyz\stackrel{{\scriptstyle\ref{lemma:irr2}}}{{\sim}}\bigtriangleup(x,y-1,z-1)\stackrel{{\scriptstyle\ref{lemma:irr3}}}{{\sim}}\bigtriangleup(x+1,y-1,z)\stackrel{{\scriptstyle\ref{lemma:irr4}}}{{\sim}}\bigtriangleup(x+2,y,z)$
b | $\bigtriangleup xyz\stackrel{{\scriptstyle\ref{lemma:irr2}}}{{\sim}}\bigtriangleup(x,y-1,z-1)\stackrel{{\scriptstyle\ref{lemma:irr4}}}{{\sim}}\bigtriangleup(x+1,y,z-1)\stackrel{{\scriptstyle\ref{lemma:irr3}}}{{\sim}}\bigtriangleup(x+2,y,z)$
c | $\bigtriangleup xyz\stackrel{{\scriptstyle\ref{lemma:irr3}}}{{\sim}}\bigtriangleup(x+1,y,z+1)\stackrel{{\scriptstyle\ref{lemma:irr2}}}{{\sim}}\bigtriangleup(x+1,y-1,z)\stackrel{{\scriptstyle\ref{lemma:irr4}}}{{\sim}}\bigtriangleup(x+2,y,z)$
d | $\bigtriangleup xyz\stackrel{{\scriptstyle\ref{lemma:irr3}}}{{\sim}}\bigtriangleup(x+1,y,z+1)\stackrel{{\scriptstyle\ref{lemma:irr4}}}{{\sim}}\bigtriangleup(x+2,y+1,z+1)\stackrel{{\scriptstyle\ref{lemma:irr2}}}{{\sim}}\bigtriangleup(x+2,y,z)$
e | $\bigtriangleup xyz\stackrel{{\scriptstyle\ref{lemma:irr4}}}{{\sim}}\bigtriangleup(x+1,y+1,z)\stackrel{{\scriptstyle\ref{lemma:irr3}}}{{\sim}}\bigtriangleup(x+2,y+1,z+1)\stackrel{{\scriptstyle\ref{lemma:irr2}}}{{\sim}}\bigtriangleup(x+2,y,z)$
Table 1: Order of lemmas for lemma 3.37

######  Lemma 3.38.

$\forall x,x^{\prime},y,z\in\mathbb{F}_{p}$, when $(y,z)\neq(0,0)$,
$\bigtriangleup xyz\sim\bigtriangleup x^{\prime}yz$.

Applying lemma 3.37 $k$ times, we have $\bigtriangleup
xyz\sim\bigtriangleup(x+2k,y,z)$. As $2$ is invertible, $k\rightarrow x+2k$
runs through $\mathbb{F}_{p}$.

######  Lemma 3.39.

$\forall x,y,y^{\prime},z\in\mathbb{F}_{p}$, when $(x,z)\neq(0,0)$,
$\bigtriangleup xyz\sim\bigtriangleup xy^{\prime}z$.

Similar to lemma 3.38.

######  Lemma 3.40.

$\forall x,y,z,z^{\prime}\in\mathbb{F}_{p}$, when $(x,y)\neq(0,0)$,
$\bigtriangleup xyz\sim\bigtriangleup xyz^{\prime}$.

Similar to lemma 3.38.

######  Lemma 3.41.

$\forall x,y,z\in\mathbb{F}_{p}$, when $(x,y,z)\neq(0,0,0)$, $\bigtriangleup
xyz\sim\bigtriangleup 111$ and $\bigtriangleup 111\sim\bigtriangleup xyz$.

If $x\neq 0$, then $\bigtriangleup xyz\sim\bigtriangleup xy1\sim\bigtriangleup
x11\sim\bigtriangleup 111$ and $\bigtriangleup 111\sim\bigtriangleup
x11\sim\bigtriangleup xy1\sim\bigtriangleup xyz$.

The other cases ($y\neq 0$ and $z\neq 0$) are similar.

######  Lemma 3.42.

$\forall x,y,z\in\mathbb{F}_{p}$, when $(x,y,z)\neq(0,0,0)$, $\bigtriangledown
xyz\sim\bigtriangledown 111$ and $\bigtriangledown 111\sim\bigtriangledown
xyz$.

Similar to lemma 3.41.

Noting that $\bigtriangleup 111\sim\bigtriangledown 222$ and that
$\bigtriangledown 111\sim\bigtriangleup 222$, and using lemmas 3.41 and 3.42,
we can now prove that $\forall t,t^{\prime}\in T^{*}$, $t\sim t^{\prime}$: as
depicted in figure 24, we have a “$\sim$” path from any tile $t$ to any tile
$t^{\prime}$. ∎

$\bigtriangleup xyz$$\bigtriangleup 222$$\bigtriangledown
x^{\prime}y^{\prime}z^{\prime}$$\bigtriangleup 111$$\bigtriangledown
111$$\bigtriangleup x^{\prime}y^{\prime}z^{\prime}$$\bigtriangledown
222$$\bigtriangledown xyz$

Figure 24: $\forall t,t^{\prime}\in T^{*}$, $t\sim t^{\prime}$

###  3.9 Primitivity

######  Theorem 3.43.

$(T^{*},\sigma)$ is primitive.

###### Proof.

$\forall t,t^{\prime}\in T^{*}$, let $d(t,t^{\prime})$ denote the least
$k\in\mathbb{N}$ such that $t^{\prime}$ appears in $\sigma^{k}(t)$; $d$ is
well defined as $(T^{*},\sigma)$ is irreducible.

The tile $\bigtriangleup 011$ is particular as $\bigtriangleup 011$ appears in
$\sigma(\bigtriangleup 011)$.

Let:

$\displaystyle m=\max_{t\in T^{*}}d(t,\bigtriangleup 011)$ (50) $\displaystyle
n=\max_{t\in T^{*}}d(\bigtriangleup 011,t)$ (51)

$\forall t,t^{\prime}\in T^{*}$, $t^{\prime}$ appears in $\sigma^{m+n}(t)$:

$t\underbrace{\xrightarrow{\sigma^{d(t,\bigtriangleup 011)}}\bigtriangleup
011\xrightarrow{\sigma^{m-d(t,\bigtriangleup 011)+n-d(\bigtriangleup
011,t^{\prime})}}\bigtriangleup 011\xrightarrow{\sigma^{d(\bigtriangleup
011,t^{\prime})}}}_{\xrightarrow{\sigma^{m+n}}}t^{\prime}$ (52)

∎

Figures 25 and 26 present examples of patches that appear in all sufficiently
large supertiles respectively for $p=3$ and $p=5$.

1.732

Figure 25: Colored representation of a patch (for $p=3$)

1.732

Figure 26: Colored representation of patch (for $p=5$)

##  4 Tiling $S_{t}$

###  4.1 Construction

######  Definition 4.1.

$\forall t\in T$, $\forall k\in\mathbb{N}$, let:

$s_{t}(k)=\sigma^{k}(\alpha^{-k}(t))$ (53)

######  Lemma 4.2.

$\forall t\in T$, the sequence $\\{s_{t}(k)\\}_{k\in\mathbb{N}}$ defines a
family of nested supertiles sharing the same central tile $t$.

###### Proof.

$\forall k\in\mathbb{N}$: the central $k$-supertile of $s_{t}(k+1)$ satisfies:

$[\alpha(s_{t}(k+1))]=[\alpha^{-k-1}(t)][\alpha]=[t][\alpha^{-k-1}][\alpha]=[t][\alpha^{-k}]=[s_{t}(k)]$
(54)

so $s_{t}(k)$ is “nested” in the center of $s_{t}(k+1)$.

Also, the central tile of $s_{t}(k)$ (at position $\alpha^{k}$) satisfies:

$[\alpha^{k}(s_{t})]=[s_{t}]\cdot[\alpha^{k}]=[t]\cdot[\alpha^{-k}]\cdot[\alpha^{k}]=[t]$
(55)

∎

######  Lemma 4.3.

$\forall t\in T$, the sequence $\\{s_{t}(k)\\}_{k\in\mathbb{N}}$ has a limit,
say $S_{t}$, that constitutes a tiling of the plane.

###### Proof.

The sequence $\\{s_{t}(k)\\}_{k\in\mathbb{N}}$ is a family of nested
supertiles, whose incircle radius tends to infinity, hence, by arguments
applied in Smilansky and Solomon [7], its limit exists in the sense of
“Chabauty–Fell topology” and corresponds to a tiling of the plane. ∎

Figure 27 presents the first steps of the construction of $S_{\bigtriangleup
021}$ (for $p=3$); the thick lines correspond to the boundaries of the first
nested supertiles; the color scheme is the one used in section 3.3.

Figure 27: Colored representation of $s_{\bigtriangleup 021}(k)$ (as nested
supertiles) for $k=0\mathinner{\ldotp\ldotp}4$ (for $p=3$)

######  Remark 4.4.

$\forall t\in T$, $S_{t}$ inherits the symmetries of $t$.

######  Remark 4.5.

$\forall m\in\mathbb{F}_{p}$, $\forall t,t^{\prime}\in U$ (or $\forall
t,t^{\prime}\in D$):

$S_{t}+S_{t^{\prime}}=S_{t+t^{\prime}}$ (56) $m\cdot S_{t}=S_{mt}$ (57)

###  4.2 Automaticity

For an in-depth introduction to automaticity, see Allouche and Shallit [1].

######  Definition 4.6.

Let $M$ be the deterministic finite automaton with the following
characteristics:

  * •

the set of states is $Q=\\{+1,-1\\}\times\mathbb{F}_{p}^{3\times 3}$,

  * •

the input alphabet is $\Sigma$,

  * •

the initial state is $q_{0}=(+1,I_{3})$,

  * •

the transitions from state $(f,m)$ are performed as follows:
Input symbol Output state $\alpha$ $(+f,[\alpha]^{-1}\cdot m\cdot[\alpha])$
$\beta$ $(-f,[\alpha]^{-1}\cdot m\cdot[\beta])$ $\gamma$
$(-f,[\alpha]^{-1}\cdot m\cdot[\gamma])$ $\delta$ $(-f,[\alpha]^{-1}\cdot
m\cdot[\delta])$

  * •

$\forall w\in\Sigma^{*}$, the final state of the automaton after processing
the input $w$, say $(f,m)$, encodes a tile $t^{\prime}$ as follows:

    * –

if $f=+1$ then $t$ and $t^{\prime}$ have the same orientation,

    * –

if $f=-1$ then $t$ and $t^{\prime}$ have opposite orientations,

    * –

also:

$[t^{\prime}]=[t]\cdot[m]$ (58)

######  Theorem 4.7.

$\forall t\in T$, the tiling $S_{t}$ is $4$-automatic and can be computed with
$M$.

###### Proof.

The incircle radius of nested prototiles $\\{s_{t}(k)\\}_{k\in\mathbb{N}}$
increases without limit, so for any tile $t^{\prime}$ in the plane, $\exists
k\in\mathbb{N}$ such that $t^{\prime}$ belongs to $s_{t}(k)$.

As seen in theorem 3.20, the position of $t^{\prime}$ within $s_{t}(k)$ is
characterized by a word $w\in\Sigma^{k}$.

Suppose that the final state of $M$ after processing $w$ equals $(f,m)$.

By construction, $m$ satisfies:

$m=\underbrace{[\alpha]^{-1}\ldots[\alpha]^{-1}}_{k\mathrm{\ times}}\cdot
I_{3}\cdot[w_{0}]\ldots[w_{k-1}]=[\alpha]^{-k}\cdot[w]$ (59)

Also, $t^{\prime}$ is at position $w$ within $s_{t}(k)$, so:

$[t^{\prime}]=[s_{t}(k)]\cdot[w]=[\alpha^{-k}(t)]\cdot[w]=[t]\cdot[\alpha]^{-k}\cdot[w]=[t]\cdot
m$ (60)

So $m$ gives access to $[t^{\prime}]$.

By construction, $f=+1$ if and only if $w$ contains an even cumulative number
of $\beta$’s, $\gamma$’s and $\delta$’s.

From lemma 3.22:

  * •

$t$ has the same orientation as $s_{t}(k)$ if and only if $k$ is even ($t$ is
at position $\alpha^{k}$),

  * •

$t^{\prime}$ has the same orientation as $s_{t}(k)$ if and only if $w$
contains an even number of $\alpha$’s,

  * •

so $t$ and $t^{\prime}$ have the same orientation if and only if $k$ and the
number of $\alpha$’s in $w$ have the same parity,

  * •

this is equivalent to say that the cumulative number of $\beta$’s, $\gamma$’s
and $\delta$’s in $w$ is even.

So $f$ gives access to the orientation of $t^{\prime}$. ∎

######  Remark 4.8.

If $k$ is not minimal, then the input will have extra leading $\alpha$’s; this
will not alter the final state as $q_{0}\xrightarrow{\alpha}q_{0}$.

######  Remark 4.9.

$\\#\Sigma=4$, so $S_{t}$ is “4”-automatic.

######  Remark 4.10.

Once the orientation of the central tile is fixed, we can interpret the
position $w$ of any tile in the plane as a base-$4$ integer, by assigning the
values $0$, $1$, $2$ and $3$ to $\alpha$, $\beta$, $\gamma$ and $\delta$
respectively (see figure 28).

$0$$1$$2$$3$$10$$11$$12$$13$$20$$21$$22$$23$$30$$31$$32$$33$$100$$101$$102$$103$$110$$111$$112$$113$$120$$121$$122$$123$$130$$131$$132$$133$$200$$201$$202$$203$$210$$211$$212$$213$$220$$221$$222$$223$$230$$231$$232$$233$$300$$301$$302$$303$$310$$311$$312$$313$$320$$321$$322$$323$$330$$331$$332$$333$$0$$1$$2$$3$$10$$11$$12$$13$$20$$21$$22$$23$$30$$31$$32$$33$$100$$101$$102$$103$$110$$111$$112$$113$$120$$121$$122$$123$$130$$131$$132$$133$$200$$201$$202$$203$$210$$211$$212$$213$$220$$221$$222$$223$$230$$231$$232$$233$$300$$301$$302$$303$$310$$311$$312$$313$$320$$321$$322$$323$$330$$331$$332$$333$

Figure 28: Positions in the plane as base-$4$ integers (the central tile has
position $0$)

###  4.3 Self-similarity

######  Theorem 4.11.

$\forall t\in T^{*}$, the tiling $S_{t}$ is self-similar.

###### Proof.

$\forall k\in\mathbb{N}$:

$\sigma(s_{t}(k))=s_{\alpha(t)}(k+1)$ (61)

So, to the limit when $k\rightarrow\infty$:

$\sigma(S_{t})=S_{\alpha(t)}$ (62)

Let $h_{p}$ be defined as:

$h_{p}=\left\\{\begin{array}[]{cl}3&\mathrm{if\ }p=3\\\ ord_{p}(4)&\mathrm{if\
}p>3\end{array}\right.$ (63)

When $p=3$:

$A^{2h_{3}}=A^{6}=I_{3}$ (64)

$\forall n\in\mathbb{N}$, we have (in $\mathbb{Z}^{3\times 3}$):

$A^{2n}=\frac{4^{n}+2}{3}\cdot I_{3}+\frac{4^{n}-1}{3}\cdot A$ (65)

So when $p>3$, in $F_{p}$:

$4^{2h_{p}}=1$ (66)

And:

$A^{2h_{p}}=\frac{1+2}{3}\cdot I_{3}+\frac{1-1}{3}\cdot A=I_{3}$ (67)

So, $\forall k\in\mathbb{N}$:

$\alpha^{2h_{p}}=id_{T}$ (68)

Applying $\sigma^{2h_{p}}$ to $S_{t}$:

$\sigma^{2h_{p}}(S_{t})=S_{\alpha^{2h_{p}}(t)}=S_{t}$ (69)

$S_{t}$ is self-similar with respect to $\sigma^{2h_{p}}$. ∎

###  4.4 Nonperiodicity

######  Theorem 4.12.

$\forall t\in T^{*}$, the tiling $S_{t}$ is nonperiodic.

###### Proof.

As a consequence of primitivity and self-similarity, $S_{t}$ contains all
supertiles $\sigma^{k}(t^{\prime})$ where $k\in\mathbb{N}$ and $t^{\prime}\in
T^{*}$.

In particular, $\forall k\in\mathbb{N}$, $S_{t}$ contains
$\sigma^{k}(\bigtriangleup 110)$.

As depicted in figure 29:

  * •

$\sigma(\bigtriangleup 110)$ contains a diamond patch combining
$\bigtriangleup 121$ and $\bigtriangledown 112$,

  * •

$\sigma^{k+1}(\bigtriangleup 110)$ contains a diamond patch combining
$\bigtriangleup(k+1,k+2,1)$ and $\bigtriangledown(k+1,1,k+2)$,

  * •

we will fix $k=p-2$ to continue.

$\sigma^{0}$$\sigma^{1}$$\sigma^{k+1}$$1$$1$$0$$\rightarrow$$1$$1$$1$$2$$\xrightarrow{k}$$1$$k+1$$k+1$$k+2$
Figure 29: From $\bigtriangleup 110$ to diamond patch

As depicted in figure 30:

  * •

$\sigma^{p-1}(\bigtriangleup 110)$ contains a diamond patch combining
$\bigtriangleup(-1,0,1)$ and $\bigtriangledown(-1,1,0)$,

  * •

$\sigma^{p}(\bigtriangleup 110)$ contains a diamond patch combining
$\bigtriangleup 011$ and $\bigtriangledown 011$.

  * •

$\sigma^{p+1}(\bigtriangleup 110)$ contains a hexagonal patch with $1$’s
around a central $2$.

$\sigma^{p-1}$$\sigma^{p}$$\sigma^{p+1}$$-1$$0$$1$$-1$$\rightarrow$$1$$0$$0$$1$$\rightarrow$$1$$1$$1$$2$$1$$1$$1$
Figure 30: From diamond patch to hexagonal patch

As depicted in figure 31:

  * •

$\sigma^{k^{\prime}+p+1}(\bigtriangleup 110)$ contains a hexagonal patch with
a central $2$, surrounded by values $2k^{\prime}+1$, themselves surrounded by
values $2k^{\prime}-1$ and $4k^{\prime}-2$,

  * •

we fix $k^{\prime}=\frac{p-1}{2}$ to continue.

$\sigma^{p+1}$$\sigma^{k^{\prime}+p+1}$$1$$1$$1$$2$$1$$1$$1$$\xrightarrow{k}$$2$$2k^{\prime}+1$$2k^{\prime}+1$$2k^{\prime}+1$$2k^{\prime}+1$$2k^{\prime}+1$$2k^{\prime}+1$$2k^{\prime}-1$$2k^{\prime}-1$$2k^{\prime}-1$$2k^{\prime}-1$$2k^{\prime}-1$$2k^{\prime}-1$$4k^{\prime}-2$$4k^{\prime}-2$$4k^{\prime}-2$$4k^{\prime}-2$$4k^{\prime}-2$$4k^{\prime}-2$
Figure 31: Iterating substitution $\sigma$ on hexagonal patches

As depicted in figure 32:

  * •

$\sigma^{\frac{3p+1}{2}}(\bigtriangleup 110)$ contains a hexagonal path of
$0$’s only in contact with nonzero values,

  * •

this hexagonal path of $0$’s doubles in size at each application of $\sigma$
(see section 3.7),

  * •

$\sigma^{w+\frac{3p+1}{2}}(\bigtriangleup 110)$ contains a hexagonal path of
$0$’s with side length $2^{w}$ only in contact with nonzero values.

$\sigma^{\frac{3p+1}{2}}$$2$$0$$0$$0$$0$$0$$0$$p-2$$p-2$$p-2$$p-2$$p-2$$p-2$$2p-4$$2p-4$$2p-4$$2p-4$$2p-4$$2p-4$$\rightarrow$$\sigma^{\frac{3p+3}{2}}$$2$$2$$2$$2$$2$$2$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$p-2$$2p-4$$2p-4$$p-2$$2p-4$$2p-4$$p-2$$2p-4$$2p-4$$p-2$$2p-4$$2p-4$$p-2$$2p-4$$2p-4$$p-2$$2p-4$$2p-4$
Figure 32: Hexagonal paths of $0$’s

Suppose that $S_{t}=S_{t}+x$ for some vector $x\neq 0$. We can find a
hexagonal path of $0$’s, say $h$, with an incircle with diameter $>\lvert
x\lvert$. $h$ would necessarily collide with $h+x$ (and this would induce
forbidden all-zero tiles), hence $S_{t}$ cannot be periodic (see figure 33). ∎

$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$x$

Figure 33: Collision of hexagonal paths of $0$’s

##  5 Tiling $H_{b,c}$

###  5.1 Construction

######  Definition 5.1.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, let $h_{b,c}$
be the hexagonal patch of six tiles with the value $c$ at the center and six
$b$’s around as depicted in figure 34.

$b$$b$$b$$c$$b$$b$$b$ Figure 34: Patch $h_{b,c}$

######  Lemma 5.2.

$\forall t\in T^{*}$, $b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$,
$h_{b,c}$ appears in $\sigma^{k}(t)$ for some $k\in\mathbb{N}$.

###### Proof.

From section 4.4, we know that this is the case for $h_{1,2}$.

Also, $\forall k\in\mathbb{N}$, $h_{1+2k,2}$ appears in $\sigma^{k}(h_{1,2})$;
as $k\rightarrow 1+2k$ runs through $\mathbb{F}_{p}$, we can find all the
patches $h_{b,2}$ with $b\in\mathbb{F}_{p}$.

Through additivity (see section 3.4), we can write $h_{b,c}=\frac{c}{2}\cdot
h_{\frac{2b}{c},2}$. ∎

######  Lemma 5.3.

$b\in\mathbb{F}_{p}$, $\forall k\in\mathbb{N}$, $\forall t\in T^{*}$,
$h_{b,0}$ does not appear in $\sigma^{k}(t)$.

###### Proof.

∎

$\forall b\in\mathbb{F}_{p}$, let $k$ be the least integer such that $h_{b,0}$
appears in $\sigma^{k}(t)$.

Note that $b\neq 0$ as an all-zero tile cannot appear in $\sigma^{k}(t)$.

If the $b$’s were generated during the $k$-th application of $\sigma$, then
$h_{b,0}$ would appear in $\sigma^{k-1}(t)$: this is a contradiction as $k$
was supposed to be minimal.

If the central $0$ was generated during the $k$-th application of $\sigma$,
then this $0$ would be the sum of two surrounding and opposite $b$’s: this is
a contradiction as $2b\neq 0$ (as $p$ is an odd prime number).

######  Lemma 5.4.

$B^{p}=C^{p}=D^{p}=I_{3}$ (70)

###### Proof.

$B^{k}=\begin{bmatrix}1&1&1\\\ 0&1&0\\\
0&0&1\end{bmatrix}^{k}=\begin{bmatrix}1&k&k\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$
(71)

Hence:

$B^{p}=\begin{bmatrix}1&p&p\\\ 0&1&0\\\
0&0&1\end{bmatrix}=\begin{bmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}=I_{3}$
(72)

The cases for $C$ and $D$ are similar. ∎

######  Lemma 5.5.

$\beta^{p}=\gamma^{p}=\delta^{p}=id_{T}$ (73)

###### Proof.

This follows from lemma 5.4 and the fact that $\beta$, $\gamma$ and $\delta$
preserve tile orientations. ∎

######  Remark 5.6.

This means that $\forall k\in\mathbb{N}$, $\forall t\in T$, $t$ appears at the
three extreme corners of $\sigma^{kp}(t)$; see right supertile in figure 10.

######  Definition 5.7.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, $\forall
k\in\mathbb{N}$, let:

$h_{b,c}(k)=\sigma^{kp}(h_{b,c})$ (74)

######  Lemma 5.8.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, the sequence
$\\{h_{b,c}(k)\\}_{k\in\mathbb{N}}$ defines a sequence of nested patches
sharing sharing the same central value $c$ surrounded by $b$’s.

###### Proof.

$h_{b,c}(0)$ is composed of six tiles $s_{0},\ldots,s_{5}$ sharing the same
central value $c$ surrounded by $b$’s.

Following remark 5.6, $h_{b,c}(1)$ is composed of six supertiles
$\sigma^{p}(s_{0}),\ldots,\sigma^{p}(s_{5})$ sharing the same central value
$c$ surrounded by $b$’s (see figure 35).

So $h_{b,c}(0)$ is nested in $h_{b,c}(1)$.
Applying $\sigma^{p}$ again, $h_{b,c}(1)$ is nested in $h_{b,c}(2)$,
$h_{b,c}(2)$ is nested in $h_{b,c}(3)$, etc. ∎

$b$$s_{0}$$\sigma^{p}(s_{0})$$s_{0}$$c$$b$$b$$s_{0}$$b$$b$$s_{1}$$\sigma^{p}(s_{1})$$s_{1}$$c$$b$$b$$s_{1}$$b$$b$$s_{2}$$\sigma^{p}(s_{2})$$s_{2}$$c$$b$$b$$s_{2}$$b$$b$$s_{3}$$\sigma^{p}(s_{3})$$s_{3}$$c$$b$$b$$s_{3}$$b$$b$$s_{4}$$\sigma^{p}(s_{4})$$s_{4}$$c$$b$$b$$s_{4}$$b$$b$$s_{5}$$\sigma^{p}(s_{5})$$s_{5}$$c$$b$$b$$s_{5}$$b$$c$

Figure 35: $h_{b,c}(0)$ is nested in $h_{b,c}(1)$

######  Lemma 5.9.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, the sequence
$\\{h_{b,c}(k)\\}_{k\in\mathbb{N}}$ has a limit, say $H_{b,c}$, that
constitutes a tiling of the plane.

###### Proof.

The arguments are similar to that of lemma 4.3. ∎

Figure 36 presents the first steps of the construction of $H_{2,1}$ (for
$p=3$); the thick lines correspond to the boundaries of the first nested
patches; the color scheme is the one used in section 3.3.

Figure 37 presents the central part of $H_{0,1}$.

######  Remark 5.10.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, $H_{b,c}$ has
reflection and 6-fold rotational symmetries.

Figure 36: Colored representation of $h_{2,1}(k)$ for $k=0,1$ (for $p=3$)

1.732

Figure 37: Colored representation of the central part of $H_{0,1}$ (for $p=3$)

######  Remark 5.11.

$\forall m,c,c^{\prime}\in\mathbb{F}_{p}^{*}$, $\forall
b,b^{\prime}\in\mathbb{F}_{p}$:

$H_{b,c}+H_{b^{\prime},c^{\prime}}=H_{b+b^{\prime},c+c^{\prime}}\mathrm{\
(provided\ that\ }c+c^{\prime}\neq 0\mathrm{)}$ (75) $m\cdot
H_{b,c}=H_{mb,mc}$ (76)

###  5.2 Automaticity

######  Definition 5.12.

Let $N$ be the deterministic finite automaton with the following
characteristics:

  * •

the set of states is $R=\\{+1,-1\\}\times\mathbb{F}_{p}^{3\times 3}$,

  * •

the input alphabet is $\Sigma$,

  * •

the initial state is $r_{0}=(+1,I_{3})$,

  * •

the transitions from state $(f,m)$ are performed as follows:
Input symbol Output state $\alpha$ $(-f,[\beta]^{-1}\cdot m\cdot[\alpha])$
$\beta$ $(+f,[\beta]^{-1}\cdot m\cdot[\beta])$ $\gamma$ $(+f,[\beta]^{-1}\cdot
m\cdot[\gamma])$ $\delta$ $(+f,[\beta]^{-1}\cdot m\cdot[\delta])$

  * •

$\forall w\in\Sigma^{*}$, the final state of the automaton after processing
the input $w$, say $(f,m)$, encodes a tile $t$ as follow:

    * –

if $f=+1$, then $t$ is an upward tile,

    * –

if $f=-1$, then $t$ is a downward tile,

    * –

also:

$[t]=[c\ b\ b]\cdot m$ (77)

######  Theorem 5.13.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, the tiling
$H_{b,c}$ is $4$-automatic and can be computed with $N$.

###### Proof.

As depicted in figure 38:

  * •

$H_{b,c}$ can be divided into six sectors (related to the six tiles composing
the central hexagonal patch $h_{b,c}$),

  * •

any tile $t_{s}$ in sector $s$ belong to a family $t_{0},\ldots,t_{5}$ where
$t_{r}$ belongs to sector $r$ and is obtained by rotating counterclockwise
$t_{0}$ by $60\cdot r$ degrees around the origin.

Sector $0$$t_{0}$$x$$y$$z$Sector $1$$t_{1}$$x$$y$$z$Sector
$2$$t_{2}$$x$$y$$z$Sector $3$$t_{3}$$x$$y$$z$Sector $4$$t_{4}$$x$$y$$z$Sector
$5$$t_{5}$$x$$y$$z$$c$$b$$b$$b$$b$$b$$b$

Figure 38: $H_{b,c}$ divided into six sectors

The incircle radius of nested prototiles $\\{h_{b,c}(k)\\}_{k\in\mathbb{N}}$
increases without limit, so $\forall r\in 0\mathinner{\ldotp\ldotp}5$, for any
tile $t_{r}$ in sector $r$ in the plane, $\exists k\in\mathbb{N}$ such that
$t_{r}$ belongs to $h_{b,c}(k)$.

$t_{0}$ belongs to $\sigma^{kp}(\bigtriangleup bcc)$.

As seen in theorem 3.20, the position of $t_{0}$ within
$\sigma^{kp}(\bigtriangleup bcc)$ is characterized by a word
$w\in\Sigma^{kp}$.

Suppose that the final state of $N$ after processing $w$ equals $(f,m)$.

By construction, $m$ satisfies:

$m=\underbrace{[\beta]^{-1}\ldots[\beta]^{-1}}_{kp\mathrm{\ times}}\cdot
I_{3}\cdot[w_{0}]\ldots[w_{kp-1}]=\underbrace{[\beta]^{-kp}}_{=id_{T}\mathrm{\
(see\ lemma~{}\ref{lemma:bcdi})}}\cdot[w]=[w]$ (78)

Also, $t_{0}$ is at position $w$ within $\sigma^{kp}(\bigtriangleup bcc)$, so:

$[t_{0}]=[\sigma^{kp}(\bigtriangleup bcc)]\cdot[w]=[\bigtriangleup
bcc]\cdot[w]=[b\ c\ c]\cdot[w]=[b\ c\ c]\cdot[m]$ (79)

So $m$ gives access to $[t_{0}]$.

By construction, $f=+1$ if and only if $w$ contains an even number of
$\alpha$’s.

From lemma 3.22:

  * •

$t_{0}$ has the same orientation as $\bigtriangleup bcc$ (i.e. is an upward
tile) if and only if the number of $\alpha$’s in $w$ is even.

So $f$ gives access to the orientation of $t_{0}$.

If $r\neq 0$, then $t_{r}$ can be deduced from $t_{0}$ as follows:

  * •

$[t_{r}]=[t_{0}]\cdot\begin{bmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\end{bmatrix}^{r}$
(80)

  * •

$t_{0}$ and $t_{r}$ have the same orientation if and only if $r$ is even.

∎

######  Remark 5.14.

If $k$ is not minimal, then the input will have extra leading $\beta$’s; this
will not alter the final state as $r_{0}\xrightarrow{\beta}r_{0}$.

######  Remark 5.15.

$\\#\Sigma=4$, so $H_{b,c}$ is “4”-automatic.

######  Remark 5.16.

We can interpret the position $w$ of any tile in sector $0$ as a base-$4$
integer, by assigning the values $1$, $0$, $2$ and $3$ to $\alpha$, $\beta$,
$\gamma$ and $\delta$ respectively; tiles whose position does not contain
$\alpha$’s form a Sierpiński triangle (see figure 39).

$0$$1$$2$$3$$10$$11$$12$$13$$20$$21$$22$$23$$30$$31$$32$$33$$100$$101$$102$$103$$110$$111$$112$$113$$120$$121$$122$$123$$130$$131$$132$$133$$200$$201$$202$$203$$210$$211$$212$$213$$220$$221$$222$$223$$230$$231$$232$$233$$300$$301$$302$$303$$310$$311$$312$$313$$320$$321$$322$$323$$330$$331$$332$$333$

Figure 39: Positions in the sector $0$ as base-$4$ integers (the bottom left
tile has position $0$)

###  5.3 Self-similarity

######  Theorem 5.17.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, the tiling
$H_{b,c}$ is self-similar.

###### Proof.

$\sigma^{p}(H_{b,c})=H_{b,c}$ (81)

∎

###  5.4 Nonperiodicity

######  Theorem 5.18.

$\forall b\in\mathbb{F}_{p}$, $\forall c\in\mathbb{F}_{p}^{*}$, the tiling
$H_{b,c}$ is nonperiodic.

###### Proof.

Similar to section 4.4. ∎

##  6 One-dimensional case

The structure of this section is similar to that of sections 3 to 5.

For reasons of simplicity, we will omit the proofs when they do not present
any particular difficulty.

###  6.1 Substitution $\tau$

####  6.1.1 Tiles

######  Definition 6.1.

Tiles on which the substitution $\tau$ operates correspond to horizontal unit
segments whose endpoints are decorated with elements of $\mathbb{F}_{p}$ as
depicted in figure 2:

  * •

the tile whose left and right endpoints are decorated respectively with the
values $x$ and $y$ will be denoted by $\square(x,y)$ (or $\square\ xy$ when
there is no ambiguity).

$x$$y$

Table 2: The tile $\square\ xy$

######  Definition 6.2.

The set of tiles will be denoted by $P$:

$P=\\{\square\ xy\mid x,y\in\mathbb{F}_{p}\\}$ (82)

######  Definition 6.3.

We will also be interested in the set of tiles having at least one nonzero
endpoint:

$P^{*}=P\setminus\\{\square\ 00\\}$ (83)

######  Definition 6.4.

We will associate to any tile $t$ the row matrix $[t]$ with the values at its
two endpoints as follows: $\forall x,y\in\mathbb{F}_{p}$:

$[\square\ xy]=[x\ y]$ (84)

####  6.1.2 Substitution rule

######  Definition 6.5.

The substitution $\tau$ transforms a tile $t=\square\ xy$ into two tiles
$\lambda(t)=\square(x,x+y)$ and $\rho(t)=\square(x+y,y)$ as depicted in figure
40.

$x$$y$$t$$\rightarrow$$x$$x+y$$\lambda(t)$$x+y$$y$$\rho(t)$

Figure 40: The substitution rule for the tile $\square\ xy$

######  Lemma 6.6.

$\forall k\in\mathbb{N}^{*}$, $\forall t\in P$, using the notation introduced
in definition 6.4, we can conveniently relate $\lambda(t)$ and $\rho(t)$ to
$t$ by means of multiplication by certain matrices $L$ and $R$ as follows:

$[\lambda(t)]=[t]\cdot\underbrace{\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}}_{L}$
(85) $[\rho(t)]=[t]\cdot\underbrace{\begin{bmatrix}1&0\\\
1&1\end{bmatrix}}_{R}$ (86)

######  Lemma 6.7.

The matrices $L$ and $R$ are invertible in $\mathbb{F}_{p}^{2\times 2}$.

######  Lemma 6.8.

The functions $\lambda$ and $\rho$ are permutations of P.

######  Lemma 6.9.

$\forall k\in\mathbb{N}$, $\forall t\in P$, the values at the two extreme
endpoints of $\tau^{k}(t)$ are exactly the values at the endpoints of $t$.

######  Definition 6.10.

Following lemma 6.9, we will associate to any supertile $s$ the row matrix
$[s]$ with the values at its two extreme endpoints as follows: $\forall
k\in\mathbb{N}$, $\forall x,y\in\mathbb{F}_{p}$:

$[\tau^{k}(\square\ xy)]=[x\ y]$ (87)

######  Lemma 6.11.

Endpoints that meet at the same point hold the same value.

We will therefore, from now on, simplify the figures by indicating just the
values where the endpoints meet (see figure 41).

$x$$y$$\rightarrow$$x$$x+y$$y$

Figure 41: The “simplified” substitution rule for the tile $\square\ xy$

######  Remark 6.12.

$\forall k\in\mathbb{N}$, $\forall x,y,z\in\mathbb{F}_{p}$, the bottom border
of $\sigma^{k}(\bigtriangleup xyz)$ matches $\tau^{k}(\square\ xy)$ (see
figure 42).

$1$$2$$2$$1$$2$$1$$0$$0$$1$$0$$0$$2$$1$$0$$2$$0$$1$$2$$0$$0$$1$$0$$1$$1$$1$$1$$1$$1$$0$$0$$1$$0$$1$$0$$0$$1$$1$$0$$1$$0$$2$$1$$0$$2$$2$$2$$0$$2$$2$$1$$0$$1$$2$$1$$0$$2$$0$$1$$2$$1$$1$$0$$2$$0$$2$$1$$2$$0$$0$$0$$1$$0$$0$$0$$1$$1$$1$$1$$0$$1$$1$

Figure 42: $\sigma^{k}(\bigtriangleup 122)$ and $\tau^{k}(\square\ 12)$ for
$k=0\mathinner{\ldotp\ldotp}2$ (for $p=3$)

####  6.1.3 Examples

Figure 43 depicts $\tau^{k}(\square\ 12)$ for $k=0\mathinner{\ldotp\ldotp}4$
numerically (for $p=3$).

121021102212110221210201211022120102

Figure 43: $\tau^{k}(\square\ 12)$ for $k=0\mathinner{\ldotp\ldotp}4$ (for
$p=3$)

Figure 44 depicts $\tau^{k}(\square\ 12)$ for $k=0\mathinner{\ldotp\ldotp}4$
graphically with colors (for $p=3$).

Figure 44: Colored representation of $\tau^{k}(\square\ 12)$ for
$k=0\mathinner{\ldotp\ldotp}4$ (for $p=3$)

Figure 45 depicts $\tau^{k}(\square\ 12)$ for $k=0\mathinner{\ldotp\ldotp}4$
graphically with colors (for $p=5$).

Figure 45: Colored representation of $\tau^{k}(\square\ 12)$ for
$k=0\mathinner{\ldotp\ldotp}4$ (for $p=5$)

####  6.1.4 Additivity

######  Lemma 6.13.

$\forall m,x,y,x^{\prime},y^{\prime}\in\mathbb{F}_{p}$, $\forall
k\in\mathbb{N}$, we have the following identities:

$\tau^{k}(\square\ xy)+\tau^{k}(\square\
x^{\prime}y^{\prime})=\tau^{k}(\square(x+x^{\prime},y+y^{\prime}))$ (88)
$m\cdot\tau^{k}(\square\ xy)=\tau^{k}(\square(mx,my))\\\ $ (89)

where additions and scalar multiplications on supertiles are performed
componentwise on each endpoint (see figure 46).

+=104233022033134143132312110

Figure 46: $\tau^{3}(\square\ 12)+\tau^{3}(\square\ 03)=\tau^{3}(\square\ 10)$
(for $p=5$)

####  6.1.5 Symmetries

$\forall k\in\mathbb{N}$, $\forall x,y\in\mathbb{F}_{p}$:

  * •

if $x=y$ then $\tau^{k}(\square\ xy)$ has reflection symmetry: the values at
two symmetrical endpoints with respect to the center of the supertile are
equal,

  * •

if $x=-y$ then $\tau^{k}(\square\ xy)$ has reflection “odd” symmetry: the
values at two symmetrical endpoints with respect to the center of the
supertile are opposite and sum to $0$ (see figures 43 and 44).

####  6.1.6 Positions within supertiles

######  Theorem 6.14.

$\forall k\in\mathbb{N}$, $\forall n\in 0\mathinner{\ldotp\ldotp}2^{k}-1$, let
$w\in\\{0,1\\}^{k}$ be the binary expansion of $n$. The $n$-th tile $t$ within
a $k$-supertile $s$ satisfies:

$[t]=[s]\cdot[w]$ (90)

where:

$[0]=L,[1]=R$ (91)

######  Lemma 6.15.

A supertile $s$ is uniquely determined by one of its tile $t$ and the position
$w$ of $t$ within $s$.

####  6.1.7 Patterns of zeros

######  Lemma 6.16.

A supertile $\tau^{k}(t)$ contains $\square\ 00$ if and only if $t=\square\
00$.

######  Lemma 6.17.

$\forall m\in\mathbb{F}_{p}^{*}$, $\forall k\in\mathbb{N}$, $\forall t\in P$,
the $0$’s at the endpoints of $m\cdot\tau^{k}(t)$ and $\tau^{k}(t)$ are
exactly located at the same places.

######  Remark 6.18.

Tiles with one $0$ remain in the endpoint holding that $0$ upon repeated
applications of $\tau$:

$\tau(\square\ 0y)=\square\ 0y\ \square\ yy$ (92) $\tau(\square\ x0)=\square\
xx\ \square\ x0$ (93)

######  Lemma 6.19.

$\forall k\in\mathbb{N}$, $\forall t\in\\{\square\ 10,\square\ 01\\}$, the
values at two symmetrical endpoints in $\tau^{k}(t)$ with respect to the
center of $\tau^{k}(t)$ cannot both equal $0$.

####  6.1.8 Irreducibility

######  Theorem 6.20.

$(P^{*},\tau)$ is irreducible.

######  Lemma 6.21.

$\forall x\in\mathbb{F}_{p}^{*}$, $\forall y,y^{\prime}\in\mathbb{F}_{p}$,
$\square\ xy\sim\square\ xy^{\prime}$.

###### Proof.

$\square\ xy\sim\square(x,x+y)$.
$\forall k\in\mathbb{N}$, applying this relation $k$ times, we obtain
$\square\ xy\sim\square(x,kx+y)$.
As $x$ is invertible, $k\rightarrow kx+y$ runs through $\mathbb{F}_{p}$. ∎

######  Lemma 6.22.

$\forall x,x^{\prime}\in\mathbb{F}_{p}^{*}$, $\forall y\in\mathbb{F}_{p}^{*}$,
$\square\ xy\sim\square\ x^{\prime}y$.

###### Proof.

Similar to lemma 6.21. ∎

######  Lemma 6.23.

$\forall t\in P^{*}$, $t\sim\square\ 11$ and $\square\ 11\sim t$.

###### Proof.

Let $[t]=[x\ y]$ (necessarily, $(x,y)\neq(0,0)$).
If $x\neq 0$, then:

  * •

$\square\ xy\sim\square\ x1\sim\square\ 11$,

  * •

$\square\ 11\sim\square\ x1\sim\square\ xy$.

If $y\neq 0$, then:

  * •

$\square\ xy\sim\square\ 1y\sim\square\ 11$,

  * •

$\square\ 11\sim\square\ 1y\sim\square\ xy$.

Hence, $\forall t,t^{\prime}\in P^{*}$, $t\sim\square\ 11\sim t^{\prime}$. ∎

####  6.1.9 Primitivity

######  Theorem 6.24.

$(P^{*},\tau)$ is primitive.

###  6.2 Tiling $V_{y}$

####  6.2.1 Construction

######  Lemma 6.25.

$\forall y\in\mathbb{F}_{p}$, the sequence $\\{\tau^{k}(\square\
0y)\\}_{k\in\mathbb{N}}$ has a limit, say $V_{y}$, that constitutes a tiling
of the half-line.

###### Proof.

The substitution $\tau$ can be seen as a $2$-uniform morphism operating on the
alphabet $P$.

As $\tau(\square\ 0y)=\square\ 0y\square\ yy$ starts with $\square\ 0y$, the
given limit exists (and is a pure morphic word). ∎

Figure 47 presents the first steps of the construction of $V_{3}$ (for $p=5$).

Figure 47: Colored representation of $\tau^{k}(\square\ 03)$ for
$k=0\mathinner{\ldotp\ldotp}4$ (for $p=5$)

######  Lemma 6.26.

$V_{y}$ is directly related to Dijkstra’s “fusc” function: the ($0$-based)
$n$-th tile in $V_{y}$ equals:

$V_{y}(n)=y\cdot\square(fusc(n)\ mod\ p,fusc(n+1)\ mod\ p)$ (94)

###### Proof.

The construction of $V_{y}$ mimics that of Stern’s diatomic series (see figure
1). ∎

######  Remark 6.27.

$\forall m,y,y^{\prime}\in\mathbb{F}_{p}$:

$V_{y}+V_{y^{\prime}}=V_{y+y^{\prime}}$ (95) $m\cdot V_{y}=V_{my}$ (96)

####  6.2.2 Automaticity

######  Theorem 6.28.

$\forall y\in\mathbb{F}_{p}$, the tiling $V_{y}$ is $2$-automatic.

###### Proof.

As a fixed point of a $2$-uniform morphism, $V_{y}$ is $2$-automatic. ∎

Let $O$ be the deterministic finite automaton with the following
characteristics:

  * •

the set of states is $\mathbb{F}_{p}^{2\times 2}$,

  * •

the input alphabet is $\\{0,1\\}$,

  * •

the initial state is $I_{2}$,

  * •

the transitions from state $m$ are performed as follows:
Input symbol Output state $0$ $L^{-1}\cdot m\cdot L$ $1$ $L^{-1}\cdot m\cdot
R$

  * •

$\forall w\in\\{0,1\\}^{*}$, the final state of the automaton after processing
the input $w$, say $m$, encodes a tile $t^{\prime}$ as follows:

$[t^{\prime}]=[0\ y]\cdot m$ (97)

$V_{y}$ can be computed with $O$.

####  6.2.3 Self-similarity

######  Theorem 6.29.

$\forall y\in\mathbb{F}_{p}$, the tiling $V_{y}$ is self-similar.

###### Proof.

$\tau(V_{y})=V_{y}$ (98)

∎

####  6.2.4 Nonperiodicity

######  Theorem 6.30.

$\forall y\in\mathbb{F}_{p}^{*}$, the tiling $V_{y}$ is nonperiodic.

###### Proof.

######  Remark 6.31.

As $y$ is invertible, the periodicity of $V_{y}$ is equivalent to the
periodicity of the “fusc” function reduced modulo $p$.

Suppose that $V_{y}$ is periodic.

######  Lemma 6.32.

The least period of $V_{y}$ would be odd.

If $V_{y}$ is $2m$-periodic with $m>0$, then:

$fusc(n)=fusc(2n)=fusc(2n+2m)=fusc(2(n+m))=fusc(n+m)$ (99)

So we can assume that the period is odd.

As $V_{y}$ is primitive and self-similar, $\forall k\in\mathbb{N}$, $V_{y}$
contains $\tau^{k}(\square(\frac{1}{2},\frac{1}{2}))$.

$\forall k\geq 0$:

  * •

the two central tiles of $\tau^{k+1}(\square(\frac{1}{2},\frac{1}{2}))$ are
$\square(k+\frac{1}{2},1)$ and $\square(1,k+\frac{1}{2})$,

  * •

in particular, when $k=p-\frac{1}{2}$, we have the central tiles $\square\ 01$
and $\square\ 10$ (in that order).

$\forall k^{\prime}>0$:

  * •

$\tau^{k^{\prime}-1}(\square\ 01\ \square\ 10)$ contains $2^{k^{\prime}}$
tiles,

  * •

the leftmost being $t=\square\ 01$ and the rightmost being
$t^{\prime}=\square\ 10$,

  * •

the tiles $t$ and $t^{\prime}$ are at distance $2^{k^{\prime}}-1$, and $t\neq
t^{\prime}$.

Suppose that $V_{y}$ is $m$-periodic (with $m$ odd):

  * •

$m$ divides $2^{ord_{2}(m)}-1$,

  * •

so the leftmost and rightmost tiles in $\tau^{ord_{2}(m)-1}(\square\ 01\
\square\ 10)$ must be the same, a contradiction,

  * •

such supertiles appear infinitely many times in $V_{y}$,

  * •

hence $V_{y}$ is neither periodic nor eventually periodic.

∎

######  Corollary 6.33.

The function “$k\rightarrow fusc(k)\mod p$” is not eventually periodic.

###  6.3 Tiling $W_{t}$

####  6.3.1 Construction

######  Lemma 6.34.

$L^{p}=I_{2}$ (100)

######  Lemma 6.35.

$\forall t\in P$, the sequence $\\{\tau^{kp}(t)\\}_{k\in\mathbb{N}}$ has a
limit, say $W_{t}$, that constitutes a tiling of the half-line.

###### Proof.

The substitution $\tau^{p}$ can be seen as a $2^{p}$-uniform morphism
operating on the alphabet $P$.

As $\tau^{p}(t)$ starts with $t$, the given limit exists (and is a pure
morphic word). ∎

Figure 48 presents the first steps of the construction of $W_{\square\ 10}$
(for $p=5$).

Figure 48: Colored representation of $\tau^{kp}(\square\ 10)$ for $k=0,1$ (for
$p=5$)

######  Lemma 6.36.

$\forall y\in\mathbb{F}_{p}$:

$V_{y}=W_{\square\ 0y}$ (101)

######  Remark 6.37.

$\forall m\in\mathbb{F}_{p}$, $\forall t,t^{\prime}\in P$:

$W_{t}+W_{t^{\prime}}=W_{t+t^{\prime}}$ (102) $m\cdot W_{t}=W_{mt}$ (103)

####  6.3.2 Automaticity

######  Theorem 6.38.

$\forall t\in P$, $W_{t}$ is $2$-automatic.

We can use the same automaton as in section 6.2.2 to compute $W_{t}$.

####  6.3.3 Self-similarity

######  Theorem 6.39.

$\forall t\in P$, $W_{t}$ is self-similar.

###### Proof.

$\tau^{p}(W_{t})=W_{t}$ (104)

∎

####  6.3.4 Nonperiodicity

######  Theorem 6.40.

$\forall t\in P^{*}$, $W_{t}$ is nonperiodic.

###### Proof.

Suppose that $W_{t}$ is $m$-periodic for some $m>0$.

We know that $V_{1}$ is nonperiodic, so for some $n\in\mathbb{N}$,
$V_{1}(n)\neq V_{1}(n+m)$.

Let $k\in\mathbb{N}$ be such that $n+m<2^{k}$.

As $W_{t}$ is primitive and self-similar, it contains infinitely many copies
of $\tau^{k}(\square\ 01)$. This $k$-supertile has two different tiles at
distance $m$, so $W_{t}$ cannot be periodic or eventually periodic. ∎

##  7 Acknowledgments

I would like to express my very great appreciation to Mihai Prunescu, Neil
Sloane and Dirk Frettlöh for their valuable and constructive suggestions.

##  Appendix A Code sample (PARI/GP)

The following PARI/GP program creates an image of $\sigma^{8}(\bigtriangleup
120)$ (for $p=3$). This image is used on the front page.

\\\ draw point at triangular coordinates z

\\\ with color v (0 = white)

dot(z,v) = {

if (v,

plotcolor(w, [ 2, /*blue*/

4, /*red*/

5, /*cornsilk*/

1, /*black*/

3, /*sienna*/

7 /*gainsborough*/ ][lift(v)]);

plotpoints(w, [2*real(z)+imag(z)], [imag(z)]);

);

}

\\\ draw tile or supertile

\\\ z(c)

\\\ / \

\\\ / \

\\\ x(a)-----y(b)

stern(a,b,c, x,y,z, k) = {

if (k==0,

\\\ tile

dot(a,x);

dot(b,y);

dot(c,z),

\\\ k-supertile

stern(a,(a+b)/2,(a+c)/2, x,x+y,x+z, k-1);

stern((a+b)/2,b,(b+c)/2, x+y,y,y+z, k-1);

stern((a+c)/2,(b+c)/2,c, x+z,y+z,z, k-1);

stern((a+c)/2,(b+c)/2,(a+b)/2, x+z,y+z,x+y, k-1);

);

}

{

p = 3; \\\ 3, 5 or 7

my (k = 8, x = 1, y = 2, z = 0);

\\\ draw sigma^k(/\xyz) for current odd prime number p

plotinit(w=0, width=2048, height=2048);

plotscale(w, 0,width, 0,height);

stern(0,2^k,I*2^k, Mod(x,p),Mod(y,p),Mod(z,p),k);

plotdraw(w);

plotkill(w);

}

##  Appendix B Other substitutions

This section describes substitutions similar to $\sigma$ that operate on
triangles or on squares with corners decorated by elements of $F_{p}$ and
exhibit interesting graphical features.

For all of these substitutions, corners that meet at the same point hold the
same value.

When operating on equilateral triangles, as with $\sigma$, the substitution
rule for $\bigtriangledown xyz$ can be obtained by turning a half turn that
for $\bigtriangleup xyz$.

###  B.1 Substitution $\sigma_{1}$

The substitution $\sigma_{1}$ operates on equilateral triangles and transforms
a tile into four tiles as depicted in figure 49. This substitution uses
multiplication instead of addition.

See figure 50 for an example of supertile.

$\rightarrow$$x$$z$$y$$x$$xz$$z$$xy$$yz$$y$

Figure 49: The substitution rule for $\sigma_{1}$

1.732

Figure 50: Colored representation of $\sigma_{1}^{8}(\bigtriangleup 123)$ (for
$p=5$)

###  B.2 Substitution $\sigma_{2}$

The substitution $\sigma_{2}$ operates on equilateral triangles and transforms
a tile into nine tiles as depicted in figure 51.

This substitution is related to the OEIS sequence A356097.

See figure 52 for an example of supertile.

$\rightarrow$$x$$y$$z$$x$$x$$x$$x+y+z$$z$$z$$z$$y$$y$$y$

Figure 51: The substitution rule for $\sigma_{2}$

1.732

Figure 52: Colored representation of $\sigma_{2}^{6}(\bigtriangleup 012)$ (for
$p=3$)

###  B.3 Substitution $\sigma_{3}$

The substitution $\sigma_{3}$ operates on equilateral triangles and transforms
a tile into nine tiles as depicted in figure 53.

This substitution is related to the OEIS sequence A356096.

See figure 54 for an example of supertile.

$\rightarrow$$x$$y$$z$$x$$2x-y$$2x-z$$x+y+z$$2z-x$$2z-y$$z$$2y-x$$2y-z$$y$

Figure 53: The substitution rule for $\sigma_{3}$

1.732

Figure 54: Colored representation of $\sigma_{3}^{5}(\bigtriangleup 112)$ (for
$p=3$)

###  B.4 Substitution $\sigma_{4}$

The substitution $\sigma_{4}$ operates on equilateral triangles and transforms
a tile into nine tiles as depicted in figure 55.

This substitution is related to the OEIS sequence A356002.

See figure 56 for an example of supertile.

$\rightarrow$$x$$y$$z$$x$$2x+y$$2x+z$$x+y+z$$x+2z$$y+2z$$z$$x+2y$$2y+z$$y$

Figure 55: The substitution rule for $\sigma_{4}$

1.732

Figure 56: Colored representation of $\sigma_{4}^{5}(\bigtriangleup 111)$ (for
$p=4$)

###  B.5 Substitution $\sigma_{5}$

The substitution $\sigma_{5}$ operates on equilateral triangles and transforms
a tile into nine tiles as depicted in figure 57.

This substitution is related to the OEIS sequence A356098.

See figure 58 for an example of supertile.

$\rightarrow$$x$$y$$z$$x$$x-y$$x-z$$x+y+z$$z-x$$z-y$$z$$y-x$$y-z$$y$

Figure 57: The substitution rule for $\sigma_{5}$

1.732

Figure 58: Colored representation of $\sigma_{5}^{5}(\bigtriangleup 011)$ (for
$p=2$)

###  B.6 Substitution $\sigma_{6}$

The substitution $\sigma_{6}$ operates on squares and transforms a tile into
nine tiles as depicted in figure 59.

This substitution is related to the OEIS sequence A356245.

See figure 60 for an example of supertile.

$\rightarrow$$w$$x$$y$$z$$w$$w+x$$w+x$$x$$w+y$$w+x+y$$w+x+z$$x+z$$w+y$$w+y+z$$x+y+z$$x+z$$y$$y+z$$y+z$$z$

Figure 59: The substitution rule for $\sigma_{6}$ Figure 60: Colored
representation of $\sigma_{6}^{5}(\square 1111)$ (for $p=3$)

###  B.7 Substitution $\sigma_{7}$

The substitution $\sigma_{7}$ operates on isosceles right triangles and
transforms a tile into four tiles as depicted in figure 61.

This substitution is related to the OEIS sequence A358871.

See figure 62 for an example of supertile.

$\rightarrow$$x$$y$$z$$x$$y$$z$$x+y$$x+z$$y+z$

Figure 61: The substitution rule for $\sigma_{7}$ Figure 62: Colored
representation of $\sigma_{7}^{9}(\bigtriangleup 110)$ (for $p=2$)

## References

  * [1] Jean-Paul Allouche, Jeffrey Shallit, “Automatic Sequences: Theory, Applications, Generalizations”, Cambridge University Press, 2003
  * [2] Dirk Frettlöh, Edmund Harriss, Franz Gähler, “Tilings encyclopedia”, published electronically at https://tilings.math.uni-bielefeld.de
  * [3] D. H. Lehmer, “On Stern’s diatomic series”, Amer. Math. Monthly 36 (1929), 59–67
  * [4] The OEIS Foundation Inc. (2022), “The On-Line Encyclopedia of Integer Sequences”, published electronically at https://oeis.org
  * [5] Natalie Priebe Frank, “A primer on substitution tilings of the Euclidean plane”, https://arxiv.org/abs/0705.1142 [math.DS]
  * [6] Mihai Prunescu, “Self-similar carpets over finite fields”, https://arxiv.org/abs/0708.0899 [math.NT]
  * [7] Yotam Smilansky, Yaar Solomon, “Multiscale Substitution Tilings”, https://arxiv.org/abs/2003.11735 [math.DS]
  * [8] Stephen Wolfram, “A New Kind of Science”, Wolfram Media, Inc., May 2002, published electronically at https://www.wolframscience.com/nks/