L'auto-assemblage est le processus dans lequel les composants d'un système, qu'il s'agisse de molécules, de polymères, de colloïdes ou de particules macroscopiques, s'organisent en structures ordonnés à la suite d'interactions locales entre les composants eux-mêmes, sans intervention extérieure. Cette thèse concerne l'autoassemblage de pavages apériodiques. Les pavages apériodiques (le pavage Penrose en est un exemple célèbre) servent de modèle mathématique pour les quasi-cristaux -les cristaux qui n'ont pas la symétrie de translation. En raison de la disposition atomique spécifique de ces cristaux, la question de savoir comment ils se forment reste toujours sans réponse. L'objectif de cette thèse est de développer un algorithme de croissance pour une classe particulière de pavages apériodiques -les pavages octogonaux de type fini. Afin d'imiter la croissance de quasi-cristaux réels, nous demandons que l'algorithme soit local: les pièces doivent être ajoutées une par une, en utilisant uniquement les informations locales et aucune donnée ne doit être stockée entre les étapes. Les simulations corroborent la conjecture que l£algorithme que nous avons mis au point permet de former des pavages apériodiques, modulo une proportion inévitable mais négligeable de pavés manquants.

First, I would like to express my gratitude to my referees, Nicolas Bédaride and Emmanuel Jeandel for reading this manuscript, writing reviews and providing helpful suggestions. I also wish to thank Florent Becker, Frédérique Bassino, and Olivier Bodini for agreeing to be part of the jury committee.

With many thanks to my thesis director Thomas Fernique, who introduced me to the world of aperiodic tilings, for spending hours explaining various concepts, for teaching me how to ask questions and how to search for answers, for his guidance and consistent support he provided during these three years.

I am grateful to all of those with whom I have had the pleasure to work during this project. I would like to thank Pavel Kalougine for patient explanations about cut-and-project tilings which provided me with invaluable insights, Thierry Monteil for teaching me how to use SAGE and his pieces of advice on programming. I had great pleasure of working with Sébastien Labbé and the inspiring discussions on Wang tilings we had at LaBRI. Special thanks go to Michael Rao for the quadrocopter.

There are a lot of people who have provided support during these years. I would like to thank all of you for your help, whether it was scientific advice or moral support during the time of need. With a special mention to Dmitry Ponomarev, Sergey Dovgal, Natalia Kharchenko, Liubov Tupikina, and Victor Hubert Lutfalla who all helped me in numerous ways during various stages of my PhD.

I would like to thank team CALIN of Laboratoire d'Informatique de Paris Nord for providing a great working environment. Last but not least, I would like to express gratitude to my family and friends for their patience and unwavering support. Special thanks to Orlov Arseniy, Daria Savvina, Zakharov Ilya, Tikhonov Anton, Jamie Lynn, and also to Carlos Ureña Martín for our monkey business. I hope no one will be offended for my failure to mention them personally. Quasicrystals are physical solids with aperiodic atomic structure and symmetries forbidden in classical crystallography. They were discovered by Dan Shechtman in 1982 who subsequently won the Nobel prize for his discovery in 2011. In section 1.2 we give a short survey on the series of events that lead the scientific community to accept the existence of quasicrystals. In section 1.3 we state the current state-of-art of the two major open problems regarding quasicrystals. The first one is the question of stability. The two main stabilisation mechanisms we briefly cover are the energy and entropy stabilisation scenarios. The second question is how quasicrystals grow, the one we focus in this thesis. In recent studies, the growth of nearly perfect quasicrystals is observed via high-resolution transmission electron microscopy e.g., in [START_REF] Nishimoto | Experimental observation of quasicrystal growth[END_REF]. However, the mechanism of how quasiperiodic order propagates long-range in still unclear.

To represent the peculiar atomic structure of quasicrystals Levine and Steinhardt in [START_REF] Levine | Quasicrystals: A new class of ordered structures[END_REF] proposed the Penrose tilings [START_REF] Penrose | The role of aesthetics in pure and applied mathematical research[END_REF]. A tiling is a covering of a Euclidian plane by given geometric shapes (called tiles) with no holes or overlarpping. Penrose tilings are the most famous example of a tiling without translational symmetry. In section 1.4 we provide the reader with the second historical survey on the discovery of the first sets of tiles which admit only non-periodic tilings of the plane. Such tilesets are called aperiodic. In section 1.5 we introduce notable aperiodic tilesets and discuss their properties.

Aperiodic tilings are used to model quasicrystals and answer questions about the growth from the theoretical point of view. In section 1.6 we list the majority of proposed approaches on the growth problem including the algorithm of Onoda et al. [START_REF] Onoda | Growing perfect quasicrystals[END_REF] known as OSDS rules which permits to grow an infinite Penrose tiling starting from an imperfect seed.

Discovery of quasicrystals

In November 1984 Dan Shechtman published a paper [START_REF] Shechtman | Metallic phase with long-range orientational symmetry and no translational symmetry[END_REF] with the report of analuminum-magnesium alloy with 10-fold or icosahedral symmetry, i.e., rotational symmetry with angle 2π 10 , as it was shown via electron diffraction. In the same time, sharp Bragg peaks of the diffraction pattern suggested long-range order in the material. That was a clear violation of the fundamental principles of solid-state physics at the time. A diffraction pattern similar to the one found by Shechtman is depicted in Figure 1.1. To understand the impact of the discovery first we must understand the noncrystallographic symmetries and why their appearance in the diffraction images of solids was that surprising. The classical definition of a crystal is as follows: a crystal is a substance in which the constituent atoms, molecules, or ions are packed in a regularly ordered, repeating three-dimensional pattern. In other words, structural elements of a crystal are disposed on a lattice in 3-dimensional space. Crystals are characterized by space-group symmetries of their respected lattices. The 230 possible space groups were found independently by Fedorov, Barlow and Schoenflies, see [START_REF] Lalena | From quartz to quasicrystals: probing nature's geometric patterns in crystalline substances[END_REF] for a historical survey. The complete classification also shows us that there are many symmetries which are impossible in the classical definition of crystal. This is known as a crystallographic restriction.

Theorem 1.2 (the crystallographic restriction) Rotational symmetry with angle 2π

n is called n-fold rotational symmetry. A lattice L in R d with d = 2 or d = 3 can have n-fold rotational symmetry only for n ∈ {1, 2, 3, 4, 6}.

X-ray diffraction is a common and powerful technique widely used in crystallography to determine the atomic and molecular structure of a crystal. After a crystal is illuminated with a beam of X-rays, it is scattered in many specific directions and form a diffraction pattern. The diffraction patterns contain information about the structure of the crystal including the symmetry of the atomic arrangement.

The alloy discovered by Shechtman possess a symmetry which is forbidden in periodic crystals, that suggested that atoms in the material are structured in a non-periodic manner. The paper published in December 1984 coauthored by Levine and Steinhardt [START_REF] Levine | Quasicrystals: A new class of ordered structures[END_REF] named the phenomenon as a quasicrystallinity and the novel substance as a quasiperiodic crystal or quasicrystal.

Initially, the scientific community reacted to the discovery with scepticism and even hostility. Linus Pauling (who won a Nobel prize in Chemistry) once said that "There is no such thing as quasicrystals, only quasi-scientists". The head of the research group where Shechtman worked told him to leave the team for "bringing disgrace". It took a long time to convince the community about the veracity of the result. In fact, it took Shechtman nearly two years to publish the initial report.

In order to describe the atomic structure of the new material Levine and Steinhardt in [START_REF] Levine | Quasicrystals: A new class of ordered structures[END_REF] proposed Penrose tilings [START_REF] Penrose | The role of aesthetics in pure and applied mathematical research[END_REF]. Penrose tilings, the most celebrated example of an aperiodic tiling, manifested not only 10-fold symmetry but also the diffraction pattern very similar to the one found by Shechtman. Along with Penrose tilings, there exist infinitely many other aperiodic tilings with various types of symmetries forbidden in classical crystals but found in quasicrystals. Using the aperiodic tilings as a discrete model appeared a very fruitful approach, and we will cover some of the results in the following sections.

The debate about the foundations of crystallography started by Schechtman also inspired other groups to search for quasicrystals. Within a few years, there had been reported quasicrystals with decagonal [START_REF] Bendersky | Quasicrystal with one-dimensional translational symmetry and a tenfold rotation axis[END_REF] and pentagonal symmetry [START_REF] Bancel | Icosahedral aluminium -transition-metal alloys[END_REF], octagonal symmetry [START_REF] Wang | Two-dimensional quasicrystal with eightfold rotational symmetry[END_REF] and dodecagonal symmetry [START_REF] Ishimasa | New order state between crystalline and amorphous in Ni -Cr particles[END_REF]. The growing number of examples left no choice but to admit the existence of crystals with aperiodic atomic structure.

Eventually, the ice cracked, in 1992 the International Union of Crystallography altered the definition of a crystal. The current definition is based on the properties of the diffraction pattern of the material and goes as follows: By "Crystal" is meant any solid having an essentially discrete diffraction diagram. For his discovery, Shechtman won a Nobel prize in chemistry in 2011. For a brief history of the events, we advise to read [START_REF] Steinhardt | Quasicrystals: a brief history of the impossible[END_REF].

Stability and growth problems

Stability. Despite the abundance of quasicrystals synthesized in labs, there was not a consensus whether quasicrystallinity is a fundamental state of matter or the quasicrystals appear only as metastable phases under very specific (and unnatural) conditions. Common view was that aperiodic atomic structure is too complicated to be stable. Roger Penrose once said "For this reason, I was somewhat doubtful that nature would actually produce such quasicrystalline structures spontaneously. I couldn't see how nature could do it because the assembly requires non-local knowledge". The discussion on what governs the stability of quasicrystals is still ongoing. Possible stability mechanisms include energetic stabilisation and entropy stabilisation, see [START_REF] Boissieu | Stability of quasicrystals: Energy, entropy and phason modes[END_REF] for an overview.

Energy stabilization scenario suggests that quasicrystals can indeed be a state of minimal energy of the system, as in the case of classical crystals, and that short range atomic interactions suffice to provide an aperiodically ordered structure. This is the case of tilings with local rules model. We will thoroughly describe it in the following sections.

Entropy stabilisation scenario suggests that quasicrystals are always metastable phases and that aperiodic atomic order is governed by phason flips (a local rearrangement of atoms that leave the free energy of the system unchanged) and structural disorder even if the state is not energetically preferred. This is the case of random tiling model [START_REF] Henley | Random tiling models[END_REF], [START_REF] Cohn | A variational principle for domino tilings[END_REF]. Think of a random packing of two or more types of geometrical tiles which fills the space. The system is assumed to maximize entropy by forming a structure with the highest symmetry allowed and possibly from a quasicrystalline structure.

Energy stabilisation scenario would allow quasicrystals to be formed naturally. After years of a thorough search for samples in museums, Luca Bindi, head of the Division of Mineralogy of the Museo di Storia Naturale of the Universita di Firenze, found a specimen labeled "khatyrkite" from Khatyrka region of the Koryak mountains in the Chukotka, the north-eastern part of the Kamchatka peninsula [START_REF] Bindi | Natural quasicrystals[END_REF] [BYL + 15]. Diffraction pattern of one of the phases revealed icosahedral symmetry. Establishing that the sample was indeed formed naturally took another two years and even an expedition to the Koryak mountains. Analysis of one of the samples containing khatyrkite revealed that it was from a meteorite. Futher investigation of the khatyrkite showed that it most likely was formed under extreme pressure followed by rapid cooling, where the entropic effects are not as important as energetic and kinetic [START_REF] Bindi | Icosahedrite, al63cu24fe13, the first natural quasicrystal[END_REF].

Growth. Another argument supporting the theory that quasicrystals can be stabilised via short range interactions was given by Onoda et al. in [START_REF] Onoda | Growing perfect quasicrystals[END_REF] They found an algorithm for growing a perfect Penrose tiling around a certain defective seed using only the local information. A defective seed is a pattern made from Penrose rhombuses which is not a subset of any Penrose tiling. The finding broke the belief that non-local information is essential for building quasicrystalline types of structure. We will describe the algorithm in detail in section 1.6.3. Moreover, in [START_REF] Nagao | Experimental observation of quasicrystal growth[END_REF] the growth of quasicrystals was directly observed (see Figure 1.2 with high-resolution transmission electron microscopy (HRTEM). Edagawa and his team produced decagonal quasicrystal consisting of Al 70.8 Ni 19.7 Co 9.5 . The growth process featured frequent errors-and-repair procedures and maintained nearly perfect quasiperiodic order at all times. Repairs, as concluded, were carried via so-called phason flips, which is qualitatively different from the ideal growth models.

This leads us to the problematics of this thesis. Crystals can grow, both classic ones and the quasicrystals. Various methods of growth will be covered in substantial chapters. Local interactions between particles guide them into their respected places along the crystal lattice. Let us view the growth of crystals from the viewpoint of pure geometry. The question transforms into the following: how to algorithmically assemble the atomic structure of a growing crystal using only the local information? Classical crystals exhibit the unit cell which makes the question trivial: as long as we can see an instance of the unit cell, we know the structure. The question becomes much harder as we proceed to quasicrystals as there is no translational symmetry and no unit cell.

More precisely we search for a local self-assembly algorithm for aperiodic tilings and by the locality constraint we mean the following:

• units of a growing cluster must be added one by one

• at each step only finite neighbourhood is allowed to be observed Figure 1.2: The positions of the growth front at t = 0, 2.1, 4.9, 11.3, and 13.6 s are marked by red curves.

• no information must be stored between the steps Relationship between aperiodic tilings and quasicrystals is another case, one of many, in the history of sciences when mathematical structures underlying the physical phenomenon were discovered before the phenomenon itself. First examples of aperiodic tilings were found two decades before the Shechtman discovery and without any physical motivation but rather from the needs of mathematics.

Discovery of aperiodic tilings

Tiling theory deals with various ways a surface can be filled with copies of basic shapes without gaps and overlaps. The set of basic shapes is called a prototile set and the elements are called tiles. An important class of prototile sets was introduced by Hao Wang in 1961 [START_REF] Wang | Proving theorems by pattern recognition II[END_REF]. A Wang tile is a unit square with colored edges. The colors represent so-called matching rules. Two Wang tiles can be attached one to another only edge-to-edge and only if the colors of abutting edges match. One of the important questions regarding a set of Wang tiles is whether or not the set admits a tiling of a plane. In general, the definition of a tiling is the following:

Definition 1.3 A tiling of the Euclidian d-dimensional space is a set {t i | i ∈ N} ⊂ R d of non-empty closed subsets t i ∈ R d , such that ∪ i∈N t i = R d and interiors int(t i ) ∩ int(t j ) = ∅.
The set of equivalence classes of tiles up to translations, if finite, is called a prototile set. Definition 1.4 A pattern is a non-empty subset of a tiling.

In 1961 Wang conjectured that if a Wang tileset admits a tiling, then there exists a periodic tiling, i.e. one with a translation invariance. Wang posed to his student, Robert Berger, a question whether it is possible to algorithmically decide if a given Wang tileset admits a tiling. This question is known as Tiling problem or Domino problem. In fact, if Wang's conjecture were true, then the problem would be indeed decidable. It suffices to run an exhaustive search for tilings of larger and larger rectangles until either a periodically repeating pattern will be found or a rectangle that is impossible to tile. The algorithm will run indefinitely only if all the possible tilings are non-periodic. Definition 1.5 A prototile set is called aperiodic if admits only aperiodic tilings.

In 1966, Berger [START_REF] Berger | The Undecidability of the domino problem[END_REF] proved the undecidability of Domino problem. The proof contained an explicit construction of the first aperiodic prototile set. The first set was huge and consisted of 20,426 tiles. Subsequently, aperiodic sets with fewer and fewer tiles were discovered. In 1971 Raphael M. Robinson [START_REF] Robinson | Undecidability and nonperiodicity for tilings of the plane[END_REF] found a simpler proof of a Domino problem with a smaller set of six tiles up to isometry or 56 if we forbid rotations and reflections. Shortly after, in 1974 Roger Penrose [START_REF] Penrose | The role of aesthetics in pure and applied mathematical research[END_REF] discovered another tileset, based on pentagons rather than squares, with six tiles, and subsequently reduced the number of tiles to just two.

Notable aperiodic prototile sets

In this section we provide descriptions of notable aperiodic tilings and their properties. The building blocks of tilings, the prototiles, often come with a set of instructions on how to put them together. Those instructions can be of the form of a decoration of a tile, much like in the case of Wang tiles. Sometimes they can be embedded in the shape of a tile as, e.g., notches and cuts, exactly like in jigsaw puzzles. Such rules are limited in the sense that they act on a very short distance and only directly affect tiles which are adjusted but such rules could also allow longrange information transfer. Another way to define matching rules is via a finite set of allowed patterns (also finite), such rules will be explored in the second chapter.

Robinson tilings

The first example is the Robinson tilings. The tileset is depicted in Figure 1.3, it consists of six tiles shaped as unit squares decorated with two types of arrows. The tiles can be rotated and reflected. The red and green arrows represent matching rules. Two tiles can be put together only edge-to-edge and only if an arrow head matches the arrow tail. Bumpy tiles are subject to an additional restriction: each two by two square patterns of a tiling must contain at least one bumpy corner. Another representation of the tileset, where decorations are replaced to notches and cuts, is depicted in Figure 1.4. Any tiling made with Robinson tileset is called a Robinson tiling.

Theorem 1.7 (Extension theorem [START_REF] Grunbaum | Tilings and patterns, chapter 8[END_REF]) For any finite set of prototiles T in R d , if for any r > 0 there exists tiling of a ball of radius r using tiles from T , then T admits a tiling of R d .

The key feature of a Robinson tiling is the hierarchical structure of so-called supertiles. We call a bumpy corner a supertile of order 0. A supertile of order 1 can be obtained as follows: first we place four supertiles of order 0 in corners of a 3 × 3 square. We orient them so that the decorations, the red arrows, also form a squarethat is the only way to place them so that the resulting square will be tileable. Then we place a corner tile in the center of the 3 × 3 square, this defines the orientation of the supertile. The four remaining tiles are determined uniquely, they are forced to be arm tiles. A supertiles of order n is obtained in a similar manner. First, we place four supertiles of order n -1 in the corners of a (2 n+1 -1) × (2 n+1 -1) square, oriented in a way so that the red arrow decorations form a (2 n +1)×(2 n +1) square. Then we put a corner tile in the center of the new supertile and fill what is left with arm tiles. See Figure 1.5 for example. Lemma 1.8 A Robinson tiling consists of one, two or four infinite order supertiles. Theorem 1.9 Robinson tileset is aperiodic.

Proof. By Lemma 1.8 there is at least one supertile of infinite order in any Robinson tiling. Its hierarchy of self-intersecting squares (see Figure 1.6) made from red arrow decorations ensures the aperiodicity. We prove this by a contradiction. Suppose there is a periodic tiling with period p. In order to translate a supertile of order k into another supertile of order k, the translation vector must be at least of length 2 k+1 -1, that is the length of the side of the supertile. Since there exists a supertile of infinite order in any Robinson tiling, we can find a supertile or order k with side length greater than p which implies no translational symmetry.

Penrose tilings

Here we explore the celebrated Penrose tilings. In 1972 Roger Penrose, influenced by Kepler's investigation on Archimedean tilings of the plane, discovered several sets of prototiles that tile the plane only in an aperiodic manner. The original set (known as Penrose P1) consisted of six types of tiles: three types of a pentagon tile and a star, a boat, and a diamond (see Figure 1.8). Subsequently, Penrose discovered another two modifications of the original prototile set, successfully reducing the number of tiles to two: a kite and dart tiling, known as Penrose P2 (see Figure 1.9) and a rhombus tiling (Figure 1.14). In this section, we limit our attention to the rhombus Penrose tileset depicted in Figure 1.10 also known as Penrose P3. It is not important which of the modifications to take since all of them can be transformed one to another locally due to the property of local derivability.

First, for a pattern P in R n and A ⊂ R n , we define P A to be the subset of P that consists of all tiles of P which intersect A, so P A = {t ∈ P | t ∩ A = ∅}. Definition 1.10 A tiling T ∈ R d is said to be locally derivable from a tiling T ∈ R d , when a compact neighbourhood K ⊂ R d of 0 exists such that, whenever (x + T ) K = (y + T ) K holds for x, y ∈ R d , one also has (x + T ) {0} = (y + T ) {0}.

A tiling P is locally derivable from a tiling P , if and only if there exists a rule to construct the part of P around any given point from the sole knowledge of Kneighbourhood of that point in P . Local derivability is reflexive and transitive. See Inflation and deflation. The first two questions we ask about the tileset is whether it admits a tiling and if all of the tilings are aperiodic. To prove both the existence and aperiodicity we use the hierarchical structure of the tilings, evident through operations of inflation and deflation.

Inflation consists of decomposition followed by rescaling by φ 2 , the golden ratio. The decomposition rules for Penrose tiling depicted in Figure 1.13. Staring with a pattern of a Penrose tiling, each tile is decomposed into a pattern with smaller tiles according to the decomposition rules. After a rescaling with proper factor, so that the size of tiles in the resulting pattern is the same as it was initially, we obtain a bigger Penrose pattern. The process can be iterated ad infinitum.

Iterating the inflation starting from a single tile we get a sequence of patterns that cover larger and larger balls. By the extension theorem 1.7, this ensures the existence of a Penrose tiling. Note that the extension theorem does not give us an example of the tiling, but merely states the existence.

Along with the decomposition, there is an inverse operation of composition. It is executed by grouping the tiles together to form bigger tiles. Similarly, to the inflation operation, the deflation combines composition and rescaling. In practice, both decomposition and composition correspond to drawing lines, the edges of a new tiling, on the existing one. Both operations are defined uniquely, meaning that there is only one way to apply composition or decomposition to a pattern. This gives us the necessary tools to prove aperiodicity:

Theorem 1.12 Penrose tileset is aperiodic.

Proof. Suppose there is a periodic Penrose tiling with a period p. If we apply the composition, the resulting tiling must be also periodic and with the same period since the composition and decomposition rules are well-defined. By applying several compositions in a row we can make the individual tiles as big as we want. Now we apply the series of decompositions until the length of a tile is greater than p. Then any individual tile, if translated by p, will necessarily intersect its initial position. Contradiction.

Cartwheel tiling and Conway worms. The exists a special tiling made from Penrose rhombuses called the Cartwheel tiling (see [START_REF] Gardner | Penrose Tiles to Trapdoor Ciphers[END_REF] and [START_REF] Grunbaum | Tilings and patterns, chapter 8[END_REF]). To construct the tiling we start with a decagonal pattern C 0 depicted in the center of

C = lim n→∞ C 2n .
The notion of limit is well-defined in this case since each C 2k is contained inside C 2k+2 . The same can be done with odd elements of the sequence, but then the limit tiling will be reflected along the vertical axis. Interesting properties of the Cartwheel tiling include: Theorem 1.13 ([Gru87]) In any Penrose tiling every tile lies inside a cartwheel C 2n of every order n ≥ 1.

Theorem 1.14 ( [START_REF] Grunbaum | Tilings and patterns, chapter 8[END_REF]) Any finite pattern of a Penrose tiling is a subpattern of a cartwheel pattern C i , when i is big enough.

The ten ribbon-like patterns radiating from the center are called Conway worms. They are built up of a sequence of short and long units made up of three tiles each. A Conway worm along with its possible orientations is depicted in Figure 1.12. It is assembled from the hexagonal patterns with two possible orientations: the two ways to tile the interior of the hexagons in according to the matching rules. There are five directions of Conway worms possible in any Penrose tilings. The notion of Conway worm and its generalization in the case of 4 → 2 cutand-project tilings will play an important role in the self-assembly algorithm we introduce in the following chapters.

Repetitivity. Although Penrose tilings lack periodicity, there is a somewhat resembling feature: every pattern of a Penrose tiling necessary repeats itself infinitely often. Moreover, a copy of a pattern could be found within a closed ball of fixed radius around any vertex of a tiling, where the radius depends only on the size of the pattern. This property is known as quasiperiodicity or repetitivity: The set K is the search space for the pattern T (x + K). To further quantify the notion, we can choose K = K r to be the closed ball of radius r, and the search space K also to be the closed ball B(R, 0) of radius R > r. By choosing the minimal R possible, we define the repetitivity function R(r). Definition 1.17 A repetitive tiling T of R d is called linearly repetitive when its repetitivity function satisfies R(r) = O(r) as r → ∞.

Theorem 1.18 Penrose tilings are linearly repetitive. Sketch of the proof. Once more we can use the composition and decomposition tricks. Let us apply the n-composition to our tiling until the tiles become as big, so that the pattern P = T (x + K) contains at most one vertex of the tiling for all x ∈ R with n = O (log (diam(P ))). Let v denote the closest vertex of the tiling (with bigger tiles) to our pattern. The 2-pattern around v, i.e., the configuration of tiles where each tile shares v as a vertex, repeats itself with bounded gap k ∈ R. It is easily seen since, for example, every 2-pattern lies inside a Cartwheel of order 4 and repeats inside of it. To find a copy of P first we search for another reoccurrence of the 2-pattern around vertex V and then apply n-decomposition. Another occurrence of P will necessarily be inside the 2-pattern decomposed n times. Thus, the search radius is bounded by kφ n .

Cut-and-project scheme. Many of the properties of Penrose tilings are derived from a so-called cut-and-project scheme. The method, first introduced by DeBruijn [DB81] in 1981, is based on the discovery that Penrose tilings can be obtained by projecting certain points from higher dimensional lattices to a 2-dimensional plane. The method was subject of many generalizations (see [START_REF] Baake | Aperiodic Order, volume 149 of Encyclopedia of mathematics and its applications[END_REF] for a comprehensive overview), here we introduce a version known as canonical cut-and-project. Definition 1.19 Canonical n → d cut-and-project scheme is a set consisting of a total space R n , a physical space or a slope E -a d-dimensional subspace of R n , an internal space E ⊥ -another subspace of R n subject to a direct sum decomposition E ⊕ E ⊥ = R n , a lattice Z n , and two natural projections π : R n → E and π ⊥ : R n → E ⊥ satisfying the conditions that π| Z n is injective and π

⊥ (Z n ) is dense in E ⊥ .
A tiling is generated from a canonical cut-and-project scheme in two steps. First, we select the vertices of Z n which lie inside the stripe S -the Minkowski sum of E and the unit hypercube. Then we project them onto E to get the set of vertices of a tiling: Two vertices v 1 , v 2 ∈ V share an edge if their respected preimages z 1 , z 2 ∈ Z n are at distance 1 from each other. The number of different directions of edges, therefore, corresponds to the dimension of the total space. This an extremely powerful tool to generate tilings and Penrose tilings, again, serve as the first example: Theorem 1.20 (De Bruijn, 1981) Penrose tilings can be generated via canonical 5 → 2 cut-and-project scheme with the slope generated by

V = {π(z) | z ∈ Z n ∩ S}.
u =       1 cos(2π/5) cos(4π/5) cos(6π/5) cos(8π/5)       v =       0 sin(2π/5) sin(4π/5) sin(6π/5) sin(8π/5)      
For any Penrose tiling, there exists a translation of the slope such that the tiling can be generated via the cut-and-project scheme with that specific slope and vice versa. Therefore, Penrose tilings can be defined as 5 → 2 cut-and-project tilings instead of the classical Penrose definition with the decorated prototiles. This fact leads us to an interesting conclusion. The decorations of the tiles can sort-of-speech, lock the slope in higher dimensions!

Ammann-Beenker tilings

Another important example of an aperiodic tiling, this time with 8-fold symmetry, is the Ammann-Beenker tilings depicted in Figure 1.15. The prototile set consists of a unit square and a rhombus with a π/4 angle. The tiling was discovered independently, but with different methods, by Ammann in the 1970s and Beenker [START_REF] Beenker | Algebraic theory of non-periodic tilings of the plane by two simple building blocks: a square and a rhombus[END_REF] in 1982. In his search for an aperiodic prototileset, amateur mathematician Ammann defined the tilings in a similar manner as Penrose did, as a tiling with the given prototileset. On the other hand Beenker, following the approach of DeBruijn, defined the tilings via a 4 → 2 cut-and-project scheme with a slope generated by:

u =     1 cos(π/4) cos(2π/4) cos(3π/4)     v =     0 sin(π/4) sin(2π/4) sin(3π/4)    
For Ammann-Beenker tilings, as in the case of Penrose tilings, there exist composition and decomposition rules, which are also defined uniquely. Consequently, the proof of existence and aperiodicity is the same as for Penrose tilings since all the necessary tools are in place.

However, there is one particular difference between the two that will be important in the later sections. Ammann-Beenker tilings can not be characterized by their matching rules except if decorations are added, meaning that the slope of the Ammann-Beenker is not locked by the collection of finite patterns. In fact, there exist indefinitely many 4 → 2 cut-and-project tilings with different slopes which have the same set of patterns as in an Ammann-Beenker tiling.

Self-assembly and deceptions

In general, self-assembly is the process in which the components of a system, whether molecules, polymers, or macroscopic particles, are organised into ordered structures as a result of local interactions between the components themselves, without exterior guidance. The idea that quasicrystal growth is driven by short-range atomic interactions leads to the question of self-assembly of aperiodic tilings. It is unclear how atoms of a growing quasicrystal can arrange themselves in such a particular order only by means of local interactions. The problem has attracted a lot of attention and, in an attempt to mimic the quasicrystal growth, several models for self-assembly of aperiodic tilings were proposed. In this section we cover the majority of developed approaches.

Deceptions

Before we list existing algorithms, we describe the notion of deception -one of the main obstacle for building such algorithms. Adding tiles one by one, even in according to matching rules, may lead to a pattern that is impossible to extend to a tiling of the entire plane, an example is in Figure 1.16. A deception is a pattern that is not only impossible to extend to a tiling but also it is impossible to notice by the local inspection that the pattern is not a subset of any tiling, see Figures 1.17 • every (r -1)-pattern of P is a subset of some tiling of the plane • P itself is not a subset of any tiling of the plane. In the case of Penrose tilings, it is easy to prove the existence of deceptions of all orders. There is an example of a deception in Figure 1.17. By inflating the pattern we get a bigger deception of a higher order. Iterating the process we can construct a deception or arbitrary larger order. That means that in the case where we do have a choice on which tile to add, there is no upper boundary on the size of the pattern that must be observed to ensure the correct placement. This property is referred as non-locality of Penrose tilings, first proved by Penrose in [START_REF] Penrose | Tilings and quasicrystals: A non-local growth problem[END_REF]. Also, see [START_REF] Ross | Non-local growth of penrose tilings[END_REF] for a detailed explanation.

Aperiodic tilings with matching rules model the structure of quasicrystals which are energetically stabilized. However, for all of such tilings, the problem of guaranteeing the perfect growth of arbitrary large patterns seemed particularly hard [START_REF] Steinhardt | The Second Kind of Impossible: The Extraordinary Quest for a New Form of Matter[END_REF]. As Dworkin and Shieh conjectured: Local matching rules alone (i.e., without added features such as probabilistic interactions) are insufficient to guarantee defect-free growth.

Exploring probabilistic algorithms

In [START_REF] Van Ophuysen | Strictly local growth of penrose patterns[END_REF] authors explore a family of self-assembly algorithms for Penrose tilings which allow defects. However, not all the defects are permitted, the only type of defect allowed is when two edges with different directions of an arrow meet. Authors call such edges green. They build an expanded and ordered vertex atlas, adding vertex configurations with green edges and sorting the atlas with respect to the number of green edges, prioritizing configurations with the fewer number of mismatches.

Mechanism of adding a tile for all the algorithms is the same: whenever a vertex on the surface of a growing cluster is selected, it must be completed to a vertex configuration in according to the priorities assigned to the vertex atlas (the expanded and ordered atlas with possible mismatches). Every algorithm starts with a prechosen seed. The algorithms differ only in the vertex selection method.

Examples of the algorithms provided include the one the authors call as oldest. At the start it makes the list of all vertices, it chooses a vertex on top of the list, completes it with the minimal number of green edges in according to the priority list, then adds new vertices to the bottom of the list and deletes the vertices which are complete. The loop continues with once again choosing a vertex on top.

The second algorithm is called nearest. One vertex in a seed is named as the origin. The algorithm chooses the nearest incomplete vertex to the origin and completes it to a vertex configuration in according to the priority list. Repeat.

The idea is to find some specific order of selection so that the pattern will be defect free or, at least, the number of defects will be minimal. However, authors conclude that such algorithm cannon possibly work and the number of defects grows rather quickly. An important observation they made is the following: most of the defects can be fixed by flipping tiles in a hexagon pattern i.e., changing the orientation of corresponding Conway worms.

Penrose self-assembly algorithm

Onoda et al. in [START_REF] Onoda | Growing perfect quasicrystals[END_REF] (see also [START_REF] Socolar | Simple octagonal and dodecagonal quasicrystals[END_REF]) described a self-assembly algorithm for Penrose tiling known as OSDS rules, the main algorithm we are interested in. For any arbitrary large disk and arbitrary small ε > 0, the algorithm generates a pattern of a Penrose tiling that covers the disk with probability 1 -ε. The idea behind the algorithm is to use matching rules (or equivalently the 1-atlas) of Penrose tiling and the fact that Penrose tilings are characterized by matching rules to identify the tiles that we can add without fear of making a mistake.

Starting with a big enough pattern of a Penrose tiling as a seed, the algorithm randomly chooses an edge on the boundary and tries all the possibilities available to add a tile. For each possibility it checks the configuration around the two vertices of the chosen edge. If there is only one choice of a tile such that both of the configurations are allowed by the matching rules (or the atlas), then we can safely add the selected tile because we do not have a choice. Such tiles are called forced. That means that the algorithm, while only the forced tiles are added, is attempting to build an empire of the seed pattern.

Eventually and inevitably, the algorithm will exhaust all the forced tiles and reach a so-called dead surface, a pattern where there is more than a single valid choice everywhere. Then authors prove that there exists a finite set of patterns with special edges, the set is explicitly listed, with the following properties:

• any dead surface has at least one special edge

• adding the thick tile to a special edge will never introduce a mistake

• new forced tiles will be available after the fat tile is added Onoda et al. prove that we can safely add a thick tile to a special edge only when the dead surface is already present. By design, the algorithm is allowed neither to observe the whole boundary of the growing pattern nor to store any information between the steps. It means that it is impossible to know if we already reached the dead surface at any given moment. To make the algorithm truly local, authors introduce the probabilistic aspect: wherever the algorithm chooses a special edge, the fat tile is added with a small probability α. The smaller the α, the smaller the risk to add a tile before the dead surface is reached. We can vary the parameter α depending on the size of a disk we want to cover and the chosen room for error ε.

The algorithm:

Data: Initial seed P with at least one forced tile and α > 0 while TRUE do pick at random an edge on the boundary of P ; if there is a forced tile along the edge then add that tile to P ; else if the edge is special then add the fat tile with probability α; end end This, however, makes the algorithm prone to mistakes: if the fat tile is added before reaching the dead surface, it may lead to a pattern which cannot be extended to a tiling. Assuming no mistakes are being made, the algorithm should move from one dead surface to another indefinitely. For a pattern there is a unique smallest dead surface that contains it, which means that growing a pattern to a dead surface is deterministic -the result does not depend on the edge selection order. However, the algorithm itself is not deterministic and different runs produce different tilings. The choice happens when we select a special edge. Adding a fat tile to different special edges steer the self-assembly to different results. As authors have concluded, the algorithm can produce any tiling that has the seed as a subset.

Sketch of the proof. The first step of the proof is to provide the complete classification of dead surfaces. Observing the possible dead surfaces, one might see that there is only a handful of macro shapes they can be of. Suppose we have a finite set of dead surfaces, one of each shape. Authors claim that all the other dead surfaces can be obtained from the set by inflation or deflation procedure. That gives us the complete classification depicted in Figure 1.20. The proof is done via an exhaustive search: it appears that patterns with edges with more than one choice of a tile are all aligned as they are on the border of a Conway worm. This suggests (and we will see the reasons in the following chapters) that each choice made is actually the choice of the orientation of a Conway worm. Moreover, the dead surfaces themselves are, in fact, the patterns surrounded by Conway worms. There are exactly five types of angles in which two worms can intersect each other (see Figure 1.19). Convex polygons that we can build with those five angles are precisely the macro shapes of dead surfaces.

The only restriction on the size of the seed is that it must have at least one forced tile. Suppose we have grown the seed to a dead surface. Now, when we have to make a choice, a mistake is possible! However, the nature of mistakes is simple, the only danger is to choose orientations of two Conway worms such that they will be incompatible with each other in the intersection. To avoid this the special edges (or marginal, as they are called in the original paper) are introduced. The special edges are the edges in the intersection of two Conway worms. The selection of special edges set is done so that each dead surface has at least one such edge. In fact, the choise of special edges set is not unique. Adding a thick tile to a special site locks orientations of both Conway worms. This gives us an informal explanation of why adding a thick tile to a special site never introduces a mistake.

The key idea for the proof is the following: operations of inflation and growing a pattern to a dead surface commute. Instead of growing a pattern to a dead surface directly, we can first inflate the pattern until there are only a few tiles remain, add all the forced tiles and then deflate it back to the original size. Now, we do not have to check infinitely many dead surfaces if the mistake has been made but just the smallest ones of each macro shape.

The final part is to prove that OSDS rules do not preclude the growth of any Penrose tiling which has the seed as a subset. The pattern we get after adding a thin tile instead of thick tile to a special edge can also be obtained by adding the thick tile to a different marginal site. It also suffices to check the property only for the smallest dead surfaces of each type.

Defective seeds

Also, as authors state, there is a set of defective seeds, i.e. ones which are not allowed by the matching rules but nevertheless, if we start the growth with such a seed, the algorithm will produce infinite tiling of the plane except for the decagonal region in the center of the seed and, most importantly, will never encounter a dead surface during the growth. The decapod is an example of such a seed, it is depicted in Figure 1.21. The decapod can be constructed from the cartwheel tiling by flipping the Conway worms which pass through the center of the cartwheel, so that all of them have the same orientation.

There is a family of 62 patterns (up to rotation and reflection) similar to the decapod, each constructed by flipping the worms in various ways. One of them is the cartwheel, 60 of them produce infinite growth with untileable region in the center, and the remaining one does not, see Figure 1.23. A rule of thumb is the following, if there are three consecutive Conway worms with the same orientation, then there will be infinite growth.

Sketch of the proof. Authors introduce the notion of charge to prove the infinite growth starting from the decapod. For a closed loop of edges of a Penrose pattern, the charge is the number of single arrows pointing in the clockwise direction minus the number of single arrows pointing in the counterclockwise direction. Charge of a closed loop of edges of a Penrose pattern is always zero. The charge value of the decapod is 10. Carefully observing single arrows on the straight faces and corners of a dead surface, authors notice that the charge of any dead surfaces, including the defective ones, is equal to either ±1 or 0 since adding a tile does not change the charge of a pattern. Consequently, growth starting from the decapod will never produce a dead surface.

We note that strictly speaking the proof only shows that there will always be a forced tile and says nothing about the location of the forced tile. If all the forced tiles are grouped, for example, in the first quadrant of the plane, then the growth will never stop but there will be regions that will never be covered. However, the simulations we made suggest that the growth from decapod will cover everything except for the untileable region in the canter of the seed.

Local growth of icosahedral quasicrystalline tilings

Another paper by Socolar and Hann [START_REF] Hann | Local growth of icosahedral quasicrystalline tilings[END_REF] describes the growth of an aperiodic tiling with icosahedral symmetry in R 3 . The growth algorithm itself is very similar to the OSDS rules. This time the tiling is 3-dimensional, it is generated via 6 → 3 cut-and-project scheme with the slope generated by:

v 1 = (φ, 1, 0) v 2 = (φ, -1, 0) v 3 = (0, φ, 1) v 4 = (0, φ, -1) v 5 = (1, 0, φ) v 6 = (-1, 0, φ)
The tiling has so-called worm planes -structural elements similar to Conway worms. Flipping some of the worm planes, authors construct a defective seed (similar to the decapod) with the following property: the projection of the seed to the perpendicular space fixes the position of the window.

The growth algorithm always starts with the defective seed. It utilises the same idea of forced tiles but omits the notion of special edges. Instead, there is always a small probability to add an unforced tile -a tile which is not uniquely determined by a local configuration. Unlike the decapod seed in the case of Penrose tilings, any tiling that contains the mentioned defective seed must contain a matching rule violations outside the seed. This leads to the growing pattern to have defective vertex configurations, but, as simulations suggest, this does not preclude the growth.

Layered growth

Another modification of the OSDS algorithm is discussed in [START_REF] Jeong | Growing perfect decagonal quasicrystals by local rules[END_REF]. Common criticism of OSDS rules includes that they require either nonlocal information or arbitrarily small growth rates. To overcome the issues, author proposed to transfer the algorithm to 3D and grow a 3-dimensional aperiodic structure consisting of 2dimenional aperiodic Penrose tilings stacked on top of each other along the third dimension.

The seed consists of two patterns stacked vertically, the decapod on the bottom layer and cartwheel on the top. Growth of the decapod, as we know from the work of Onoda et al., continues ad infinitum without ever encountering a dead surface. The difference between the cartwheel tiling and the tiling emerging from the decapod seed is only in the orientations of the semi-infinite Conway worms starting from the central decagonal pattern. All the other Conway worms are the same for both tilings and also they are of finite lengths.

The main idea of the proposed algorithm is to use the infinite growth of the decapod to propagate some of the information to the top layer and assist the growth of the cartwheel tiling. Authors introduce the notion of a launching site. A launching site is thick rhombus tile in the hexagonal region at the end of a Conway worm pattern. The launching sites can be identified locally and they are used to copying the orientation of a Conway worm from the bottom layer to the top layer.

Authors define vertical and horizontal growth rules. Horizontal rules are precisely OSDS rules for both layers. Vertical rules allow us to copy the thick tile from a launching site from the bottom layer to the top layer to assist the growth past a dead surface. Using both vertical and horizontal rules allows to successfully grow the cartwheel tiling.

Also, we note that there exist quasicrystals where 2D aperiodic atomic layers are stacked periodically along the third dimension which makes the algorithm physically reasonable.

Pair-potentials

Another approach to the growth problem is to use the molecular dynamics simulation. In molecular dynamics, the system of particles is contained inside a fixed container. Particles are allowed to interact with each other and move inside the container for a finite period of time. Their trajectories are computed numerically by solving Newton's equations of motion. Forces between the particles are calculated using the interatomic potentials, predefined prior to the simulation. The simplest case of a potential is pair-potential, a function that evaluates the potential energy of two interacting objects. Examples of pair potentials include the Coulomb's law in electrodynamics, Newton's law of universal gravitation in mechanics.

One might expect complicated atomic interactions to be necessary for selfassembly of quasicrystals due to the fact that most of the available quasicrystalline phases are found inside multicomponent intermetallic systems. However, Engel et al. in [START_REF] Engel | Computational self-assembly of a one-component icosahedral quasicrystal[END_REF] describe the simulation of the growth of one-component (meaning that all the particles are of a single type) quasicrystal with oscillating pair potential with three wells. The potential combines repulsion at short distances with fading oscillation of frequency k and phase shift φ inducing an attraction at certain distances r between the particles:

V (r) = 1 r 15 + 1 r 3 cos(k(r -1.25) -φ).
The system is contained inside a cube with periodic boundary conditions with mentioned potential. After fine-tuning the parameters, the simulation starts with a random arrangement of atoms with small density. Slowly decreasing the temperature, the atoms, trying to minimize their potential energy, arrange themselves, as simulations show, into the nearly perfect quasicrystal with icosahedral symmetry.

Also, we note that this approach to the growth problem has some similarities with the growth model imposed by OSDS rules: the potential favours certain local configurations of particles. These configurations can be interpreted as elements of an atlas of a tiling. Chapter 2

Planar octagonal tilings with local rules

Introduction

In the original definition, Penrose used the decorated tiles to define the class of Penrose P3 tilings. Alternatively, we can use the vertex stars, or as we call them in this work, the collection 2-patterns for the same purpose. Definition 2.1 A set of tiles of a tiling made of polygons with vertices which are at most r edges away from a vertex x is called the r-pattern centered in x and denoted by P (x, r).

Collection of all 2-patterns, there are seven of them up to a translation in any Penrose P 3 tiling, defines the same tilings class. Meaning that any tiling with undecorated Penrose rhombuses which have the same collection of 2-patterns is necessary a Penrose P 3 tiling. In general, the set of all r-pattern is called a vertex atlas or r-atlas:

Definition 2.2
The set of all r-patterns of a tiling T up to a translation is called the r-atlas and denoted by A T (r).

See Figure 2.1 for an example.

DeBruijn in [START_REF] De Bruijn | Algebraic theory of Penrose's nonperiodic tilings od the plane[END_REF] showed that Penrose tilings can be equivalently defined as 5 → 2 cut-and-project tilings with the specific slope. That means the decorations on tiles (or alternatively the 2-atlas) can uniquely define the 2-dimensional plane in R 5 . Ability to fix the slope in higher dimensional space solely through finite patterns is referred to as local rules.

Local rules seem to be necessary for local self-assembly of cut-and-project tilings. Suppose we are trying to build a tiling without local rules. By the definition of local 33 self-assembly, the algorithm must make decisions based solely on local configurations. And if the local configurations cannot uniquely define the slope or enforce planarity at all, we cannot possibly hope to stay inside the same cut-and-project class at all times. In section 2.3 we explore the cut-and-project method in detail.

Up to date the only family of cut-and-project tilings with a complete characterization of local rules are the planar octagonal tilings of finite type [START_REF] Bedaride | Weak local rules for planar octagonal tilings[END_REF]. We introduce the family in section 2.2 and state the main results on local rules and how to identify if a given tiling admit them in section 2.5. Planar octagonal tilings is the class of tilings for which we define the local self-assembly algorithm in the next chapter.

Planar octagonal tilings with local rules

Octagonal tilings are simply the tilings made of rhombuses with four distinct edgedirections. This gives us six rhombus prototiles in total: Definition 2.3 Consider the prototile set:

{λv i + µv j , 0 ≤ λ, µ ≤ 1}, 0 ≤ i, j ≤ 3.
where v i and v j (i = j) are noncollinear vectors in R 2 . Any tiling of R 2 with the above prototile set is called octagonal.

Note that this definition permits non-periodic tilings as well as tilings which are impossible to generate via a cut-and-project scheme. Now, we further restrict ourselves to octagonal tilings which can be interpreted as digitizations of 2-planes in R 4 . For this purpose we introduce the notion of lift:

Lift Imagine we walk on an octagonal tiling and each step we take must be along an edge. Standing on a vertex, there is only a handful of options where we can step off it to the next one due to the finite number of edge-directions, just four in our case. Then, to each vertex we pair a tuple of 4 integers, where each integer is the number of steps we have to take in the corresponding direction from the 2.2. PLANAR OCTAGONAL TILINGS WITH LOCAL RULES initial position. This codes the position of the vertex relative to the starting one.

Interpreting the set 4-tuples as elements of Z 4 , we sort-of-speech, lift vertices of our 2-dimensional tiling to 4-dimensional space:

Definition 2.4 A lift is an injective mapping of vertices of a pattern to a subset of Z n done in the following manner. Let {v i } n i=0 be set of edges of a rhombus tiling T up to a translation. First, we map each v i to a basis vector e i of Z n . Afterwards, an arbitrary vertex is mapped to the origin. Then a vertex x = n i=1 a i v i of a pattern is lifted to 4 i=1 a i e i . We denote a lift of a pattern P by P .

Definition 2.5 Lifted r-pattern with x mapped to the origin denoted by P (x, r).

The set of lifted patterns of an r-atlas with centers mapped to the origin is denoted by A T (r).

Thus vertices of every octagonal tiling can be lifted to Z 4 . Since we are interested in tilings with local rules, first, we pick a subset of octagonal tilings whose lifted vertices are close to a plane, in other words the ones which can be seen as digitizations of surfaces in higher dimensional spaces: Definition 2.6 An octagonal tiling is called planar if there exists a 2-dimensional affine plane E in R 4 such that the tiling can be lifted into the stripe E + [0, 1] 4 . Then E is called the slope of the tiling. Now, for planar octagonal tilings we define the notion of local rules using an r-altas, the collection of all r-patterns, as follows: Definition 2.7 A planar tiling T with the slope E is said to admit local rules if there exists r > 0 such that, any rhombus tiling T with A T (r) ⊂ A T (r), T is also planar with the same slope E.

We define local rules via an atlas i.e. the set of allowed patterns, alternatively they can be defined with via a set of forbidden patterns. Sometimes tilings with local rules are called tilings of finite type due to similarities with subshifts of finite type (see [START_REF] Lind | An Introduction to symbolic dynamics and coding[END_REF] and [Rob04] ).

Our main example of a planar octagonal tiling with local rules will be the Golden-Octagonal (see Figure 2.2) introduced in [START_REF] Bedaride | When periodicities enforce aperiodicity[END_REF], with the slope generated by:

u = (-1, 0, φ, φ), v = (0, 1, φ, 1),

Cut-and-project scheme

In this section we define and discuss properties of projections method, arguably the most versatile method to generate as well as to study aperiodic tilings. Here we closely follow Chapter 7 of [START_REF] Baake | Aperiodic Order, volume 149 of Encyclopedia of mathematics and its applications[END_REF].

Definition 2.8 A n → d cut-and-project scheme consists of a physical space E R d , an internal space E ⊥ R n-d , a lattice Z n in E × E ⊥ = R n and the two natural projections π : R n → E and π ⊥ : R n → E ⊥ along with conditions that π| L is injective and that π ⊥ is dense in

E ⊥ . R d R d × R n-d R n-d π(Z n ) Z n π ⊥ (Z n ) ⊃ π π ⊥ ⊃ ⊃ dense * 1-1 (2.1)
For a cut-and-project scheme, there is a bijection between π(L) and π ⊥ (L), hence there is a well-defined map called the star map between E and E ⊥ :

x → x * := π ⊥ (π |L ) -1 (x) .
A bounded subset W of internal space with non-empty interior is called a window or acceptance domain. If the boundary ∂W has zero Lebesgue measure, it is called regular. In the canonical cut-and-project scheme, the window is chosen to be W = π([0, 1] n ) and lattice L to be Z n . The window acts as a filter for points which are to be projected. Using the star map, the projection set can be written as

Λ(W ) := {x ∈ Z n | x * ∈ W }.
Summary of a n → d canonical cut-and-project scheme is depicted in the diagram 2.1, our to-go method for generating planar octagonal tilings. Before we formulate some of the properties of projection sets, we need to introduce some general notions about point sets.

Point sets. Countable union of points is called a point set. In particular, every projection set is a point set.

Definition 2.9 A point set Λ in R d is said to be discrete if for every x ∈ Λ there exists an open ball B r (x) ∈ R n that does not contain any other point in Λ. A point set is called uniformly discrete if the exists r > 0 such that for all x ∈ Λ it holds B r (x) ∩ Λ = {x}.

For a point set we can define a notion of density, the average number of points per unit volume, assuming the quantity exists. With Λ r = Λ ∩ B r (0), we define the lower and upper density as: The basic assumption of solid-state matter seen as a collection of atoms, hence modelled by point sets is embodied in the following definition. Definition 2.13 A point set Λ in R d is a Delone set if it is uniformly discrete and relatively dense.

dens(Λ) = lim
Hence, for a Delone set Λ, there exist two radii 0 < r < R < ∞ such that every ball of radius r contains at most one point of Λ and every ball of radius R -at least one point of Λ. See [START_REF] Delone | A local criterion for regularity of a system of points[END_REF] for further reading. Proof. By definition, for r > 0, if Λ has finite local complexity, it follows that B r (t)∩Λ with t ∈ Λ produces only finitely many patches up to translations. For any pair x, y ∈ Λ with x -y ≤ r there exists a patch which contains them. Therefore, (Λ -Λ) ∩ B r (0) is finite. Since r > 0 was arbitrary, the closure Λ -Λ is discrete.

If closure Λ-Λ is discrete it follows that (Λ-Λ)∩B r (0) is finite for all 0 < r < ∞. Hence we can arrange elements of Λ -Λ in a sequence {z i | i ∈ N \ {0}} with z 0 = 0 such that z i ≤ z i+1 for i ≥ 0. Then, any patch of Λ of diameter 2r can be written as {x + z i | i ∈ I} with x ∈ Λ and a finite I ⊂ {i | z i ≤ r}. Since r was arbitrary, Λ has finite local complexity.

Further restricting the set of sort-of-speech interparticle distances Λ -Λ to be relatively dense gives us the definition of Meyer set.

Definition 2.15 ([BG13]

) A point set Λ in R d is a Meyer set if Λ is relatively dense and Λ -Λ is uniformly discrete. Thus, every Meyer set is a Delone set, since uniform discreteness of Λ-Λ implies uniform discreteness of Λ. General properties of projection sets in terms of point sets are summarized in the following theorems: Theorem 2.16 ([BG13]) For a cut-and-project scheme and a window W ⊂ E ⊥ • If W is bounded, then Λ(W ) has finite local complexity and hence is uniformly discrete;

• If W has non-empty interior, then Λ(W ) is relatively dense in R d ;

• if W is bounded and has non-empty interior ( i.e., a model set), then Λ(W ) is a Meyer set.

Lemma 2.17 For an n → d cut-and-project scheme and a bounded non-empty window W . If π ⊥ | Z n is 1-to-1, then the projection set Λ(W ) is non-periodic.

Proof. By contradiction, suppose there exists z ∈ R d such that Λ(W ) = Λ(W ) + z.

Then z = π( z) for some z ∈ Z n \ {0} and the projection set can be written as:

Λ(W ) + z = Λ(W ) + π( z) = Λ(W + z * ).
Now we need to show that Λ(W ) = Λ(W + z * ) whenever z * = 0. Note that z * = 0 by our assumption. Consider U = W o \ (W + z * ), a non-empty set. Since

π ⊥ (L) is dense in W , Λ(U ) is also not empty. Now, Λ(W ) = Λ(W + z * ) follows from Λ(U ) ⊂ Λ(W ) \ Λ(W + z * ).
An important property of a projection set is the uniform distribution of Λ * , when put in a sequence in a right manner, inside the window. First it was proved in for the icosahedral case in [START_REF] Elser | Comment on "quasicrystals: A new class of ordered structures[END_REF] and then in [START_REF] Schlottmann | Cut-and-project sets in locally compact abelian groups[END_REF] in the general case.

Theorem 2.18 Let Λ = Λ(W ) be a projection set for an n → d cut-and-project scheme, with a compact window W = W o . Order the points of Λ according to their distance from 0, and collect them in an exhaustive sequence (x i ) i∈N such that x i+1 ≥ x i for all i ∈ N, for some norm in R d . Then, the sequence (x * i ) i∈N is uniformly distributed in W .

Patterns and subregions

Project set description along with the uniform distribution property guaranteed by Theorem 2.18 permits us with tools to compute relative frequencies of arbitrary finite patterns of a given cut-and-project set. First, for a pattern P ⊂ Λ(W ) we can write the repetition set:

rep(P ) = {t ∈ L | t + P ⊂ Λ} = {t ∈ L | t * + P * ⊂ W o } =: Λ(W (P ))
The latter can be viewed as a model set by itself with the same physical space but modified window W (P ) ⊂ W . For t ∈ L, the inclusion t * + P * ⊂ W o is equivalent to x * ∈ W o -t * for all x ∈ P and

W (P ) = x∈P (W -x * ) := R(P ).
(2.2)

This way we can establish a link between r-patterns of cut-and-project tiling and subregions of its window, see Figure 2.3. Given an r-atlas, we can dissect the window into polygonal subregions, each subregion W p associated with an element of the r-atlas P = P (x, r) with the following property: the projection of a vertex y to the window falls into the subregion associated with P (x, r), if and only if P (y, r) = P (x, r). The similar technique was used in [START_REF] Julien | Complexity and cohomology for cut and projection tilings[END_REF] and also [START_REF] Haynes | Gaps problems and frequencies of patches in cut and project sets[END_REF] to compute the complexity i.e., the total number of elements in r-atlas of a given cut-and-project tiling.

The relative frequency of a pattern is then written as a proportion of the volume of the window W to the volume of the subregion of the window W (P ) corresponding to the pattern P : Corollary 2.19 ([BG13]) Let Λ be a regular projection set for the general cutand-project scheme (R d , H, L), with a compact window W = W o . If P ⊂ Λ(W ) and P = P ∩ K for some compact K, the relative frequency of P (per point of Λ) is given by rel freq

Λ (P ) = vol x∈P (W -x * ) vol(W )
which is related to the absolute frequency of P by abs freq Λ = dens(Λ) rel freq Λ (P )

Figure 2.3: The division of the window of an Ammann-Beenker tiling corresponding to its 1-patterns.

Also, the function 2.2 is a useful tool for determining if a given set of tiles T , each taken from the prototile set, belongs to an octagonal tiling. The lift of T may be done with any vertex projected to the origin, since we are only interested in the shape of R(T ), the vertex which is projected to the origin is referred as distinguished. If R(T ) is empty, then, simply put, there is not enough space for all the vertices to fit into the window, thus T is not a subset of any tiling. If dim R(T ) = 2 then T is a subset of any big enough r-pattern P (x, r) with x ∈ R(T ) which means it belongs to tilings.

The relative cluster frequencies are numbers in the unit interval and can be used to define an invariant probability measure on the set of patterns of a given cut-and-project tiling as follows. First, we define the notion of cylinder set: Definition 2.20 Given a pattern P of a tiling with a slope E, the cylinder set Cyl(P ) is the intersection of all planar tilings with slopes parallel to E which have P as a subset.

We note that the notion is similar to the notion of cylinder for a subshift [START_REF] Lind | An Introduction to symbolic dynamics and coding[END_REF]. To a cylinder set Cyl(P ) we assign the measure µ(Cyl(P )) := rel freq Λ (P ), where Λ is the corresponding cut-and-project point set. In particular, µ(Cyl(Λ)) = 1. Using the σ-algebra generated by the cylinder sets, µ extends to a positive measure, as in [START_REF] Billingsley | Probability and Measure[END_REF].

Corollary 2.21 For any ε > 0 there exists a finite pattern P of a planar tiling such that the cylinder set of P covers at least measure 1 -ε of the physical space.

Shadows and subperiods

To characterize the planar octagonal tilings with local rules, we need to introduce the notions of shadow and subperiod.

Definition 2.22 The ijk-shadow of an octagonal tiling T with a slope E is the orthogonal projection of its lift onto the space generated by e i , e j and e k .

Let T be a planar octagonal tiling with the slope E, suppose there exists a vector with exactly three rational components, along e i , e j , and e k for example. The projection of T to the space generated by those three basis vectors gives us a planar 3 → 2 tiling (the ijk-shadow), let E l be its slope. Since there is a rational vector in the E l , there is also an integer vector p in E l . Therefore, if x ∈ Z 3 belongs to the tiling, it follows that {x + Zp} belongs to it as well. Thus, we have a periodic direction. The prime period is the object of our interest: Definition 2.23 If an ijk-shadow of an octagonal tiling is periodic, the prime period of the shadow, an integer vector, is called an ijk-subperiod. A lift of a subperiod is any vector of R which projects on the subperiod in the ijk-shadow.

First, it turns out that periodicity of shadows enforces planarity: Theorem 2.24 ([BF15]) The subperiods of an octagonal tiling enforce irrational planarity if and only if three of them, each in a shadow with only one period, can be lifted in an irrational non-degenerated plane onto pairwise non-collinear vectors. This holds when subperiods characterize finitely many slopes.

The complete characterization of all the planar octagonal tilings with local rules is given by: Theorem 2.25 ([BF17]) A 2-dimensional plane in R 4 admits local rules if and only if it has exactly four subperiods and it is uniquely determined by them. For an octagonal tiling with local rules the radius of local rules is the maximum of norms of lifted subperiods.

As an example, four shadows along with subperiods of a Golden-Octagonal tiling are depicted in Figure 2 In order to check if a given set of subperiods uniquely determines the slope of a tiling, and in the same time existence of local rules by Theorem 2.25, one can use the Grassmann coordinates.

Grassmann coordinates. A Grassmannian G(k, n) is the space consisting of all k-dimensional subspaces of an n-dimensional vector space R n (or C n ). A special case G(1, N + 1) of a Grassmannian space is called a projective space and denoted as P N . The Grassmannian G(k, n) can be embedded into P ( k n )-1 , which induces the topology and gives rise to so-called Grassmann coordinates.

Fix n, k and a basis in R n . Let S k ∈ G(k, n) be a k-dimensional subspace. Now, we want to map S k to a point in P ( k n )-1 . First, we write a k × n matrix A, where each row is a basis vector of the subspace S k . Let I be a set of tuples of the form (i 1 , . . . , i k ), where 1 ≤ i j ≤ n and i 1 < • • • < i j . For I ∈ I, let A I be the minor of A where only columns with indices i 1 , . . . , i k are selected. Then, Grassmann coordinate of S k is the tuple of determinants of minors A I for all I ∈ I, thus an n k -tuple (defined up to a multiplicative factor). Associating each space S k with its Grassmann coordinates gives us a topology preserving map (the embedding) Φ : G(n, k) → P ( k n )-1 (see [START_REF] Hodge | Methods of Algebraic Geometry[END_REF] for a detailed explanation). The map is injective but not surjective. The tuples which are indeed coordinates of a k-space must satisfy certain quadratic equations called Plucker relations:

Definition 2.26 For G ∈ Φ(G(n, k)).
For all 1 ≤ s ≤ n and any coordinates G I , G J with I = i 1 , . . . , i k and J = j 1 , . . . j k it holds that

G I G J = k λ=1 G i 1 ...i s-1 j λ i s+1 ...i k G j 1 ...j λ-1 isj λ+1 ...j k
Theorem 2.27 For N ∈ N, If x ∈ P N satisfies Plucker relations, then there exists a k-space S k ∈ P N with coordinate x. Now back to the planar octagonal tilings. For a 2-dimensional plane in R 4 generated by u = (u 1 , . . . , u 4 ), v = (v 1 , . . . , v 4 ), the Grassmann coordinates are the 6 real numbers:

G ij = det u i u j v i v j = u i v j -u j v i , i < j,
satisfying the Plucker relation:

G 12 G 34 = G 13 G 24 -G 14 G 23 .
A set of subperiods represents rational dependencies between the coordinates of the respected shadows. Those dependencies can be written with Grassmann coordinates:

Proposition 2.28 ([BF15]) If a planar tiling has an ijk-subperiod (p, q, r), then:

pG jk -qG ik + rG ij = 0.
The relations above along with the Plucker relations yield us a system of polynomial equations. The solution gives us all the 2-dimensional planes in R 4 with the requested set of subperiods. For a planar tiling, the question if the set of subperiods uniquely defines the slope then can be transformed into a question if the mentioned system has a unique solution. The latter can be checked algorithmically, thus giving us an effective way of generating planar octagonal tilings with local rules.

Proposition 2.29 Even if the system of polynomial equations has not one but finitely many solutions, we still can state the existence of local rules. Indeed, for such a system we can keep increasing the radius of local rules i.e., the diameter of the atlas until we eliminate all the slopes except for one.

In the case of Golden-Octagonal tilings, we have the following relations, first the ones given by the subperiods in view of Proposition 2.28:

G 13 = G 23 , G 12 = G 14 , G 14 = G 34 , G 23 = G 24 .
and Plucker relation:

G 12 G 34 = G 13 G 24 -G 14 G 23 .
The system of relations above, after the normalization G 12 = 1, gives us 1 = x 2 -x, where x = G 13 = G 23 = G 23 . The finite number of solutions, namely the Golden-Octagonal slope and its algebraic conjugate, hence guaranteeing the existence of local rules by Theorem 2.25 in view of Proposition 2.29. It remains to show that the subperiods enforce planarity using the Theorem 2.24. Indeed, they lift into pairwise non-collinear vectors:

q 1 = p 1 + (1 -φ)e 1 , q 2 = p 2 + φe 2 , q 3 = p 3 + φe 3 , q 4 = p 4 + (1 -φ)e 4 .
The situation is different in the case of Ammann-Beenker tilings. There are also four distinct subperiods:

• 234-subperiod p 1 = e 2 -e 4 • 134-subperiod p 2 = e 1 + e 3 • 124-subperiod p 3 = e 2 + e 4 • 123-subperiod p 4 = e 1 -e 3
The corresponding relations on the Grassmann coordinates are:

G 12 = G 23 , G 12 = G 14 , G 14 = G 34 , G 23 = G 34 .
Plugging these into the only Plucker relation G 12 G 34 = G 13 G 24 -G 14 G 23 witg the normalization G 12 = 1 gives us a 1-dimensional system of solutions written as G 13 G 24 = 2. Threating G 13 as a parameter t, the solutions are 2-planes in R 4 with the following Grassmann coordinates written in lexicographic order: E 0 := (0, 0, 0, 0, 1, 0), E t>0 := (1, t, 1, 1, 2/t, 1), E ∞ := (0, 1, 0, 0, 0, 0).

Therefore by Theorem 2.25 Ammann-Beenker tilings do not have local rules.

Examples

There are countably many octagonal tilings with local rules. Here we present some of them to illustrate the growth in the following sections.

Example 2.30 A tiling with local rules is depicted in Figure 2.5, with a slope generated by

u =     √ 3 + 1 1 √ 3 + 1 0     , v =     √ 3 + 1 √ 3 1 √ 3 + 1     .
The set of subperiods: • 234-subperiod p 1 = e 2 + 2e 4

• 134-subperiod p 2 = e 1 + e 3

• 124-subperiod p 3 = 2e 1 + e 2 + e 4

• 123-subperiod p 4 = 2e 1 + 2e 2 -e 3

The corresponding relations:

G 12 + 2G 13 = 2G 23 , G 12 -G 14 = -2G 24 , G 14 = G 34 , 2G 23 = -G 24 .
Example 2.31 Another tiling with local rules is depicted in Figure 2.6, with slope generated by

u =     0 2φ -1 2φ -1 2φ     , v =     1 1 2φ 2φ     .
The set of subperiods:

• 234-subperiod p 1 = 5e 3 + 4e 4

• 134-subperiod p 2 = e 1 + e 3

• 124-subperiod p 3 = -e 1 + 4e 2 + 4e 4

• 123-subperiod p 4 = e 2 + e 3

The corresponding relations: Chapter 3

G 12 = G 13 , 4G 12 -4G 14 = G 24 , G 14 = G 34 , 4G 23 = 5G 24 .
Self-assembly of tilings with local rules

Introduction

In this chapter we introduce our generalization of the OSDS rules algorithm. Along with it we also propose two modifications in sections 3.2.2 and 3.2.3. The modifications will allow us to understand the growth process better by looking at it at different perspectives. We provide the reader with observations on how the algorithm works in section 3.3. In the sections 3.4 and 3.5 we provide our insights on what governs the growth and how the information transfer during the growth.

Local growth algorithm

We aim to understand whether it is possible to grow an aperiodic tiling via a local self-assembly algorithm. The meaning of the locality constraint is the following: at each step, the algorithm must have access only to a finite neighbourhood around a randomly chosen vertex of a seed -a finite pattern of a tiling we are trying to expand. Given the local neighbourhood, the algorithm must identify the set of vertices which are to be added to the seed (or it may decide that there is not enough information to add a tile or a vertex and do nothing). Finally, the algorithm must not store any information between the steps.

In chapter 1, we have described the OSDS rules self-assembly algorithm in subsection 1.6.3. Which, as authors claimed, is able to produce any Penrose tiling of the plane that has the seed as a subset. In our generalization of the algorithm, we have chosen to make it as simple as possible. We add the tiles if and only if they are forced but, and that is the crucial difference, we allow the forced tiles to be distanced from the growing pattern and not share any edges with it. This allows us to jump over the undefined tiles and, as simulations suggest, grow the cylinder set of the seed or, as it was called in [START_REF] Gardner | Penrose Tiles to Trapdoor Ciphers[END_REF], the empire of the seed.

In this section, we define our generalization of the OSDS rules algorithm as well as several modifications. We note that the algorithm works with octagonal tilings with local rules, but easily generalizable to higher dimensions.

Realisation via atlas

This is the main version of the algorithm. It uses an r-atlas in the decision process. The algorithm starts with an r-pattern of chosen octagonal tiling with local rules as a seed. The minimal diameter of the seed depends on the set of subperiods of the tiling (or on the radius of local rules) we are trying to build, we will expand on this idea in the following sections.

Now we are ready to define the local self-assembly algorithm. As input the algorithm receives:

• the seed S -a pattern of a planar tiling T ;

• the growth radius r ∈ N -the distance we are allowed to observe around any given vertex, should be greater than the diameter of local rules;

• the atlas A = A T (r);

The algorithm: while TRUE do pick at random a vertex v ∈ S; get the set of forced tiles F r (C S (v, r)); add the forced tiles {F r (C S (v, r)) + v} to S; end The algorithm is deterministic, the result does not depend on the vertex selection order. Since we add only the tiles which are forced, at most it generates the intersection of all the tilings with atlas A(r) which have S as a subset. For the tilings with local rules, the property of sharing the same r-atlas, if r is greater than the radius of local rules, can be replaced with the property of having the same slope, i.e., the cylinder set.

Realisation via region

The main version of the algorithm uses an r-atlas in the decision process and requires it as an input to start the computation. Alternatively we can use the information about the window to identify the forced tiles. Imagine we are trying to grow a pattern, we have chosen a vertex and got the corresponding vertex configuration C(x, r). We know that all the vertices in the configuration, if projected to the internal space, are inside the window. In some cases, this information alone is sufficient to identify a forced tile even if the precise position of the window is unknown. If, for example, the projections of the vertices of a tile are inside the convex hull of C * (x, r), then we can be sure that they belong to the window since the convex hull is a subset of the window. Consequently, the tile is forced by the C(x, r). However, using just the convex hull is not enough, this criterion is much weaker than the previously mentioned decision process with the atlas.

We can expand on this idea if we know the shape of the window. Since our tiling has local rules, we can safely assume that the shape is known since the slope is determined uniquely by an r-atlas, if the radius r is large enough. How to use the shape to identify the forced vertices? The idea remains the same, based on the vertices in C * (x, r), we can compute the geometrical region which necessary belongs to the window and use it as a filter: if vertices of a tile, when projected, hit this region, then they are inside the window and, therefore, are forced. See Figure 3.2 for an example.

Let us use the region function to do this. Consider R(C(x, r)), the subregion of the window where x * must belong to, so that all the other vertices in C(x, r) could fit inside the window. Every y + W , where y ∈ R(C(x, r)), is a possible window position relative to x, the center of the vertex configuration. The subset of the window W C defined by the C(x, r) is given by the intersection of all the viable positions:

W C = y∈R(C(x,r)) (W + y).
Then, if we want to check if a vertex v (or a tile, since the tile is defined by its vertices) is forced, we add it to the vertex configuration, we lift it and project the lifted vertex to the perpendicular space. If it lands inside W C , then it is forced by C(x, r). This way of defining the forced tiles (or vertices) is equivalent to the definition via an r-atlas, see section 3.2.4. Figure 3.2: Golden-Octagonal tiling. On the left there is a vertex configuration of radius 8 with center marked with red. On the right there is the same configuration viewed inside the window. We do not know the precise position of the window, but using the region function we can estimate where the center of the configuration is projected inside the window: the center must belong to the marked triangular area.

Realisation using shadow periodicity

Another approach is to use periodicity of shadows to identify the forced tiles. This will allow us to pinpoint the areas on the boundary of the growing pattern where certain types of tiles are inevitably forced. This will also allow us to control the shape of the growing pattern.

One can obtain an ijk-shadow by shrinking all the tiles with edges parallel to π(e l ) to 0, where {i, j, k, l} = {1, 2, 3, 4}, and then gluing the tiling back together so there are no empty gaps. Since the tiles with an edge parallel to π(e 1 ) form stripes, such glueing is always possible, see Figure 3.3 for an example.

An ijk-shadow of an octagonal tiling has all types of tiles except for those with an edge parallel to π(e l ), the missing edge. This leaves us with 3 types of tiles in a single shadow. Each pair of shadows have a single type of tile in common. For instance, for ijk and ijl shadows the common tile is of type t ij , since it is the only one with edges available in both shadows at the same time.

In the following paragraphs we introduce the method of shadow voting, a different way to identify forced tiles for a planar octagonal tiling with local rules. Each shadow can vote for a tile using the fact that there exists a periodic direction. To identify such a tile near a vertex, we simply continue a given pattern seen in a shadow along the periodic direction and note the tile near the vertex, if it exists, which is suggested by the continuation. We show that if two shadows vote for the same tile, then the tile is forced.

Let E be a slope of an octagonal planar tiling T with local rules. Let π s i for i ∈ {1, 2, 3, 4} be the projection operator from R 4 to the space generated by e j , e k and e l , where {i, j, k, l} = {1, 2, 3, 4}. Consider four planes E i = π s i (E), the slopes of the shadows of T . There are direct sum decompositions R 3 = E i + E ⊥ i with projection operators π i : R 3 → E i and π ⊥ i : R 3 → E ⊥ i . See the following diagram:

C(x, r) ⊂ R 4 R 3 C(x, r) ⊂ R 2 R 2 ⊃ E i πs i π i lif t (3.1)
For a vertex configuration C(x, r), consider the patterns r) is a lifted vertex configuration projected to the shadow. Such configurations will be called shadow vertex configurations. For a shadow vertex configuration, it is easy to identify some of the forced tiles due to periodicity. All the tiles in the set {C i (x, r) + Z -→ p i } \ {C i (x, r)}, where p i is the subperiod of the shadow, are forced. For a vertex x of C(x, r) we say that a vertex configuration C i (x, r) votes for a tile t if t ∈ {C i (x, r) + Z -→ p i } and t / ∈ C i (x, r). See Figure 3.4.

C i (x, r) := π i (π s i ( C(x, r))), i = 1, 2, 3, 4. Each C i (x,
Proposition 3.3 Let C(x, r) be a vertex configuration of a planar tiling with local rules. If there are two shadow vertex configurations C i (x, r) which vote for the same tile t which have a common vertex with C(x, r), then t is forced.

Proof. Suppose that the shadow vertex configurations which vote for t are C 1 (x, r) and C 2 (x, r). Each C i (x, r) could only make a mistake in i-th coordinate. So if C 1 (x, r) votes for t that means that it is either the tile t or a translated tile t + ke 1 , for k ∈ Z. However, in the second case, there is an edge parallel to e 1 that must be present in the C 2 (x, r) but by our assumption, it is not. This contradiction implies that t is forced.

Links between the modifications

The first and the second modifications of the local self-assembly algorithm are completely equivalent for the reason that an r-pattern P (x, r) is an element of an atlas if and only if dim(R(P (x, r))) = 2, as we have discussed in the section 2.4.

Lemma 3.4 Let P be a pattern of a planar tiling with local rules, for x ∈ P and f ∈ Z 4 with f 1 = 1. If there are three different shadow patterns C i (x, r) that vote for the edge f , then f belongs to the cylinder set of C(x, r), i.e., is forced.

Proof. Let f be parallel to π(e 4 ) and let us notice that

R i C i (x, r) ∪ π i (f + x) = R i C i (x, r) , i = 1, 2, 3,
because there exists a vertex y ∈ C i (x, r) such that π ⊥ i (f + x) = y. Therefore, for k = ±1:

R C(x, r) ∪ (f + x) = i=1,2,3,4 R i C i (x, r) ∪ kπ i (e 4 ) + Re ⊥ i = = i=1,2,3,4 R i C i (x, r) + Re ⊥ i = = R C(x, r) .
Since adding f to the vertex configuration does not change R(C(x, r)), then f is forced. Lemma 3.5 It a tile is forced via shadow vote, then it is also forced by the region vote.

Proof. Here we use the similar idea as in the previous Lemma. Let the forced tile near a vertex x to be of type t = t 12 . Consequently, the two shadows that vote must be of type 234 and 134. First, we notice that 1. Initial pattern of a Golden-Octagonal tiling.

2. We remove all the edges parallel to π(e 1 ).

3. And then we glue the tiling back together to get a 234-shadow. 1. Initial vertex configuration C(x,r). We are trying to add a tile to the marker vertex x.

6. The new tile is forced via shadow vote two shadows vote for it. The first thing we notice looking at Figure 3.5 is that the growth pattern misses some tiles which are aligned along almost straight lines and, see Figure 3.11 for a bigger picture, that those straight lines are not becoming denser as we move away from the seed. There are empty hexagons in the empty stripes, each hexagon permits exactly two ways to be covered, both compatible with an atlas.

In Figure 3.12 there are two growth patterns of a Golden-Octagonal tiling with growth radius 6 emerging from two seeds S 1 and S 2 , where S 1 is a subset of S 2 . For that reason, G(S 1 ) is a subset of G(S 2 ). Let us note that the two patterns differ only along the stripes of missing tiles: there are some tiles along those stripes in G(S 2 ) which are missing in G(S 1 ). This reminds us of Conway segments, the patterns which have played an important role in the OSDS rules algorithm we described in subsection 1.6.3. Compare with the growth pattern of the octagonal planar tiling introduced in Examples 2.30 depicted in Figure 3.13.

k-worms

Now, as we suspect that the straight segments resembling Conway worms play an important role, we generalize the notion in the case of planar octagonal tilings with local rules: Definition 3.8 For a planar octagonal tiling with local rules T and vertex x ∈ T , we define a subperiod line of vertex x of type i as the set:

{y ∈ T | y i = x i + q i , i ∈ {0, 1, 2, 3} \ {i}},
where q i is the lifted subperiod of type i. Definition 3.9 A subperiod line of type l of an octagonal tiling with local rules will be called an l-worm if it contains a vertex (and therefore countably many vertices) with exactly three edges, parallel to π(e i ), π(e j ), and π(e k ) respectively. Each lworm will necessarily have a vertex with exactly four edges, such vertices will be called breakpoints.

To understand the meaning of the definition we need to understand how the vertices of a k-worm are distributed inside the window. We recall the notion of star map, the mapping between the vertices of the tiling and points in the window: Proof. Let p = p i e i + p j e j + p l e l be a subperiod of type k (the prime period of the ijl-shadow) and p = p + µe k be the lift of p. Note that π( p) = 0. For a pair of consecutive vertices x and y in a subperiod line there exists λ ∈ Z such that

x → x * := π ⊥ (π |L ) -1 (x) .
π ⊥ (x -y) = π ⊥ (p + λe k ) = π ⊥ ( p + (λ -µ)e k ) = (λ -µ)e k .
Therefore a projection to the window of any vertex in a subperiod line can be written as π ⊥ (x + qe k ) for some q ∈ R which concludes the proof.

A k-worm is a special case of a subperiod line with vertices, if they are projected to the window, being relatively close to the edge of the window, the edge which is parallel to π ⊥ (e k ). As in Figure 2.3, having exactly three edges around a vertex x means that x * belong to the triangular subregion near the respected edge since it corresponds to the 1-patterns with exactly 3 edges. An example of a k-worm is depicted in Figure 3.7.

Vertices forming a suberiod line of type k are densely distributed along a line parallel to π ⊥ (e k ) if projected in the window. Therefore, for a k-worm, if some of the vertices land in the above-mentioned triangular region, there will be others who miss it, the so-called breakpoints. Frequency of breakpoints along a subperiod line of type k gives us information on how close is the k-worm to the border of the window: ones with a fewer number of breakpoints are closer.

This suggests that k-worms are the main channels of information spread. For example, if we consider as a seed the set S w = {G 2 \ G 1 }, where S 1 and S 2 are the seed patterns in Figure 3.12, what will happen? S w consists of k-worms which are present in G 2 but not in G 1 . Those worms are closer to the window borders than any other present in G(S 1 ). Starting the growth from S w will give us exactly the same pattern as we have started with S 2 , see Figure 3.8. Meaning that the k-worms contain all the information as in S 2 . Indeed, the k-worms are the most useful vertices in the self-assembly. Since they are near the borders of the window, they tell us a lot about the position of the window in the higher dimensional space.

Similarly to the original Conway worms of Penrose tilings, the 2-patterns which surround a k-worm permit just two orientations which persists along the worm, see Figure 3.9 for an example. In Figure 3.15 the only missing tiles are the horizontal 1-worms and if we know at least a single vertex, it fixes the orientation of the whole worm pattern.

Growth radius. For all the different slopes with local rules we checked, the algorithm behaves in the same manner. The only thing we need to adjust is the growth radius. First, the growth radius should allow jumping over the empty hexagonal regions where two or more worm segments intersect each other, see Figure 3.10. Consequently, the minimum radius is six edges. Second, the growth radius must greater than the radius of local rules. In the shadow vote modification the radius must be big enough to allow the algorithm to observe tiles in each shadow which are one period away. In the same time, the second condition permits filling the k-worms if at least one vertex is known. We will talk more about the worm-filling property later in the Chapter.

Trying to grow a tiling without local rules. If we use the self-assembly algorithm to build a tiling which does not admit local rules, e.g., an Ammann-Beenker tiling in Figure 3.14, there will be no infinite growth. There are still some forced tiles, the number of forced tiles depends on the size of the seed, but eventually all of them will be exhausted. The empty stripes, similar to the ones we see in the local rules case, are also evident but they become more and more dense as we move away from the seed, see Figure 3.14 for an example.

The algorithm does not work with tilings without local rules for an obvious reason. If there are infinitely many slopes with the same atlas, it is impossible to choose a single one using solely the atlas.

Remark 3.11 This, however, does not mean that a local self-assembly algorithm does not exist. Ammann-Beenker tilings, for example, have the minimal proportion of square tiles along all the other 4 → 2 tilings which share the atlas with Ammann-Beenker. A possible algorithm could use that and, in the moments when a choice is needed, do not place a square tile. This, however, only one of the possibilities still waiting to be explored. A growth pattern with approximately million vertices, the seed is marked with red. The empty stripes do not become denser as we move away from the seed. In this simulation to speed up the computation at each step we add all the forced vertices in the same time, this results in the growth pattern to be shaped as octagon.

Mechanics of the growth and information transfer

In this section, we use the third modification of the algorithm, the one which uses periodicity of shadows, to control the shape of the growing cluster and identify tiles which are inevitably forced.

Using shadow partially. In view of Lemma 3.5, since each pair of shadows have only one type of tile in common, we can be sure that for a vertex configuration all the tiles of this type are forced if the corresponding two shadow vertex configurations vote. In order to vote a shadow vertex configuration C i (x, r) must have enough tiles along its period, and therefore, the original vertex configuration C(x, r) must have enough tiles along i-th subperiod. To identify the areas of the growing cluster where we have enough information for the shadows to vote, we provide following definition:

Definition 3.12 For a pattern P , the set ijk (P ) is defined by ijk (P ) := {x ∈ Cyl(P )|∃y n ∈ P : x ∈ subperiod line of y n of type n, n = i, j, k}.

The tiles in ijk (P ) of a pattern P , assuming it is big enough, is the set of vertices of tiles for which we have enough information along the respected subperiods 3.4. MECHANICS OF THE GROWTH AND INFORMATION TRANSFER 65 Figure 3.12: Growth patterns G 6 (S 1 ) and G 6 (S 2 ) with seeds, both marked with red, S 1 and S 2 respectively, where S 1 is a subset of S 2 . Figure 3.13: A growth pattern of a planar octagonal tiling introduced in Example 2.30. The seed is marked with red.

(the growth radius must be chosen accordingly) to place them via the shadow vote algorithm. That leads us to the following lemma: Lemma 3.13 For a pattern P of an octagonal planar tiling with local rules all the tiles in ijk (P ) of types t kl , t il , and t jl which share a vertex with a tile in P are forced via the shadow vote procedure only using the shadows jkl,ikl, and ijl.

Proof. The only type of shadow that does not vote is the ijk-shadow. For each pair of shadow which vote, for example ijl and jkl, we conclude that they place a tile of type t jl since it is the only type of tile they have in common and by Lemma 3.5 the tile is forced.

Moreover, in some cases and if the growth radius is big enough, we can state that all the tiles in the ijk (P ) are forced via shadow vote. As in the case of the Golden-Octagonal tiling, see Figure 3.15 for an example. Proposition 3.14 For a pattern P of a Golden-Octagonal tiling all the tiles in ijk (P ) of types t kl , t il , and t jl are forced via the shadow vote procedure only using the shadows jkl, ikl, and ijl (see Figure 3.15).

Moreover for a Golden-Octagonal tiling, the only case of a vertex which is impossible to place via voting procedure in ijk is when it belongs to a octagonal pattern which surround a vertex of a l-worm as in Figure 3. 15. In other words, all the vertices are forced except for some of the l-worms. Lemma 3.15 Consider a pattern P of an octagonal planar tiling with local rules. If there is an l-worm w with a breakpoint in ijk (P ), then all the vertices in w ∩ ijk (P ) are forced via shadow vote.

An example is depicted in Figure 3.16. If we allow to use the 234-shadow during the growth of the pattern P depicted in Figure 3.15, every 1-worms with a breakpoint lying inside P will be forced.

Growth viewed in the window

In this section we discuss mechanics of the growth viewed inside the window.

Guiding principle. The r-atlas determines the shape of the window, i.e., the slope of the tiling. The size of the seed dictates the precision of window position: the bigger the seed the more we know about the position of the window.

Cylinder set. Recall that the cylinder set of a pattern P of a planar octagonal tiling with local rules is the set of tiles which appear in all the planar tilings with the same r-atlas (assuming r is big enough) which contain P as a subset, i.e., all the planar tilings whose window contains P * . The vertices of the cylinder set are those which project in the corresponding subregion of the window:

W (P ) := s∈R 2 {W + s | W + s ⊃ P * } ⊂ W.
The cylinder set is the maximal set of tiles that can be grown (even non-locally) if we known only the local rules of E and the initial seed and also add only the forced tiles, i.e., do not allow any arbitrary choice while the growth continues. We conjecture that, if r is large enough, it actually grows the whole cylinder set.

Note that since P * is a finite set of points, the window can always be slightly shifted so that it still contains P * . When performing such a shift, points of Z n which project into the window near its boundary can enter or exit the window: these are the points where the tilings which contain P are different, the k-worms. They are aligned along the subperiods in the tiling and along the boundary of the window in the perpendicular space. This is why the cylinder set of P has small holes aligned along specific directions. The larger is P , the lesser the window can be shifted and the sparser are the lines of holes (but the distance between holes in each line stays the same).

Why does it grow. Each vertex configuration C(v, r) of a pattern P yields us an approximation of the position of the window. The precision of this approximation depends on the information contained in the configuration and is not easily quantized.

At least, since the points of Z n are equidistributed in the perpendicular space by Theorem 2.18, for any ε > 0 there is s > 0 such that if C(v, r) contains a ball of radius s, then the Haussdorff distance between W (P (v, r)) and W (P ) is at most ε.

Let w be a vertex in the cylinder set which does not belong to C(v, r) and which is within distance r from the vertex v. Then w appear in each pattern of the r-atlas if and only if w * ∈ W (C(v, r)). Locally, we know only W (C(v, r)) and not W (P ), but since W (C(v, r)) ⊂ W (P ), if w * ∈ W (C(v, r)) then w * ∈ W (P ) thus w is forced and will be added by the growth process. Some vertices may fall in W (P )\W (C(v, r)), these are not added because the information locally available does not suffice to ensure that they belong to the cylinder set. Since the points of Z n are uniformly distributed in W , for r large enough, some points withing distance r from v must fall in W (C(v, r)). Moreover, since W (P )\W (C(v, r)) is usually very small, this should be the case of most of them.

Of course, we want a new point w, i.e., the points which does not already belong to P . Once again, uniform distribution ensures that for s big enough, if B(v, r) contains a ball of radius s which does not intersect P , then one of these points in this ball must fall in W (C(v, r)). Such a point is new and forced.

Revisiting OSDS rules algorithm. Now we can interpret the growth via OSDS rules from slightly different perspective. Recall that a dead sufrace is a pattern surrounded by Conway worms with orientations not forced by the seed pattern. Each time we add a tile to a special edge, we fill some of the undefined Conway worms. This, sort-of-speech, adds the information about the position of the slope and allows us to grow a bigger pattern until the next set of undefined Conway worms is reached. The set of undefined Conway, assuming the initial seed pattern is big enough, is actually rather sparse but since the OSDS rules algorithm cannot jump over them, we are forced to make a choice at each dead surface.

Remark 3.16 Looking in Figure 3.11 we see how the dead surfaces as in the OSDS rules algorithm would have looked like if we were unable to jump over the tiles which are not forced by the seed pattern.

To sum things up, there is r > s > 0 such that any point v in P such that both P (v, r) and B(v, r)\C(v, r) contain a ball of radius s, then a point of the cylinder set is added to P by the growth process. This does not ensure the growth because it relies on the shape of the growth pattern, which is not controlled. However, it shows that at least in the vicinity of locally flat boundaries of P there are points which are added, supporting the growth of round-shaped patterns suggested by simulations.

Examples

In this sections we provide examples of octagonal tilings with local rules for which we have tested the local self-assembly algorithm. Each example was grown up to 100000 vertices.

Example 3.17 An octagonal tiling with local rules with a slope generated by

u =     √ 3 + 2 √ 3 + 2 0 1     , v =     √ 3 + 2 √ 3 + 3 √ 3 + 2 0     ,
The subperiod relations:

G 13 = G 23 , G 12 = -G 14 , G 14 = G 34 , G 23 + 3G 24 = 3G 34 .
Example 3.18 An octagonal tiling with local rules with a slope generated by

u =     0 1 √ 17 + 1 √ 17     , v =     √ 17 + 1 √ 17 0 √ 17 + 1     ,
The subperiod relations:

G 12 -G 23 = G 13 , 33G 12 -16G 24 = 17G 14 , G 13 +G 34 = 0, 50G 23 -33G 34 = 16G 24 .
Example 3.19 An octagonal tiling with local rules with a slope generated by

u =     2φ 2φ -1 2φ -1 0     , v =     0 2φ -1 1 2φ -1     ,
The subperiod relations:

3G 12 -2G 23 = 5G 13 , G 12 = G 14 , 5G 13 + 4G 34 = 5G 14 , G 24 = G 34 .
Example 3.20 An octagonal tiling with local rules with a slope generated by

u =     1 0 √ 5 + 1 1     , v =     0 √ 5 √ 5 + 1 √ 5 + 1     ,
The subperiod relations:

4G 12 -G 23 = 5G 13 , G 12 = -G 14 , G 13 = G 14 , G 23 + G 34 = 0.
Example 3.21 An octagonal tiling with local rules with a slope generated by

u =     √ 5 1 0 1     , v =     0 √ 5 + 1 √ 5 √ 5     ,
The subperiod relations:

G 12 -G 23 = G 13 , G 14 -5G 24 , G 13 = G 14 , G 23 + G 34=0 .
Example 3.22 An octagonal tiling with local rules with a slope generated by

u =     √ 3 + 1 √ 3 √ 3 + 1 0     , v =     1 √ 3 + 1 0 √ 3 + 1     ,
The subperiod relations:

2G 12 -4G 13 + 3G 23 = 0, 2G 12 + G 14 -4G 24 = 0, G 14 -G 34 = 0, G 23 + G 34 = 0.
Example 3.23 An octagonal tiling with local rules with a slope generated by

u =     2φ 1 2φ 2φ -1     , v =     2φ -1 0 2φ 1     ,
The subperiod relations:

G 13 -G 23 = 0, G 12 + G 14 + 4G 24 = 0, 4G 13 -4G 14 + 5G 34 = 0, 4G 24 + G 34 = 0.

Example 3.24 An octagonal tiling with local rules with a slope generated by

u =     0 1 2φ -1 2φ -1     , v =     1 2φ 2φ 0     ,
The subperiod relations:

4G 12 -G 23 = 0, 5G 12 + G 14 -G 24 = 0, G 13 -G 14 = 0, G 24 -G 34 = 0.
Example 3.25 An octagonal tiling with local rules with a slope generated by

u =     1 √ 2 + 1 0 √ 2     , v =     √ 2 + 1 √ 2 √ 2 0     ,
The subperiod relations:

2G 12 -G 13 +3G 23 = 0, 2G 12 -2G 14 -G 24 = 0, G 13 +G 14 -G 34 = 0, G 24 -G 34 = 0.

Example 3.26 An octagonal tiling with local rules with a slope generated by

u =     0 1 √ 5 √ 5     , v =     1 0 1 √ 5     .
The subperiod relations:

G 12 + G 23 = 0, G 14 + G 24 = 0, G 13 -G 14 = 0, 5G 23 -G 24 -G 34 = 0.
Example 3.27 An octagonal tiling with local rules with a slope generated by

u =     √ 3 √ 3 + 1 1 1     , v =     1 √ 3 √ 3 + 1 0     ,
The subperiod relations:

G 12 +3G 13 -2G 23 = 0, G 12 +2G 14 -G 24 = 0, G 13 +G 14 +G 34 = 0, G 23 -3G 24 +4G 34 = 0.
Example 3.28 An octagonal tiling with local rules with a slope generated by

u =     0 √ 2 + 1 1 √ 2 + 1     , v =     1 √ 2 √ 2 0     ,
The subperiod relations:

2G 13 + G 23 = 0, G 12 -G 14 = 0, G 13 + G 14 -G 34 = 0, G 24 -G 34 = 0.
Example 3.29 An octagonal tiling with local rules with a slope generated by

u =     1 √ 3 + 1 0 1     , v =     √ 3 1 √ 3 + 1 √ 3 + 1     ,
The subperiod relations:

2G 12 + G 23 = 0, 2G 12 + G 14 + G 24 = 0, G 13 + G 34 = 0, G 23 -2G 24 -2G34 = 0.
Example 3.30 An octagonal tiling with local rules with a slope generated by

u =     √ 2 + 1 √ 2 + 1 √ 2 0     , v =     √ 2 + 1 1 √ 2 + 1 1     ,
The subperiod relations:

2G 12 + G 13 + G 23 = 0, G 14 -G 24 = 0, G 13 -G 14 = 0, G 23 -3G 24 + 2G = 0.
Example 3.31 An octagonal tiling with local rules with a slope generated by

u =     1 √ 5 0 √ 5 + 1     , v =     0 1 √ 5 + 1 √ 5 + 1     ,
The subperiod relations:

4G 12 + G 13 -G 23 = 0, 4G 12 -G 24 = 0, G 13 -G 14 = 0, 2G 23 -G 24 + G = 0.
Example 3.32 An octagonal tiling with local rules with a slope generated by

u =     √ 3 1 √ 3 + 1 √ 3 + 1     , v =     1 0 √ 3 √ 3 + 1     ,
The subperiod relations:

2G 12 + G 13 + G 23 = 0, 2G 12 + G 14 = 0, 2G 13 -3G 14 + 2G 34 = 0, G 24 -G = 0.
Example 3.33 An octagonal tiling with local rules with a slope generated by

u =     √ 6 √ 6 √ 6 1     , v =     √ 6 √ 6 + 1 0 √ 6 + 1     ,
The subperiod relations:

G 12 -G 13 + G 23 = 0, 5G 14 -6G 24 = 0, G 13 + G 14 = 0, G 23 + G 34 = 0.

Example 3.34 An octagonal tiling with local rules with a slope generated by

u =     1 √ 7 √ 7 √ 7     , v =     1 1 1 √ 7 + 1     ,
The subperiod relations:

G 12 -G 13 + G 23 = 0, 7G 14 -G 24 = 0, G 13 -8G 14 + G 34 = 0, 7G 23 + G 24 = 0.
Example 3.35 An octagonal tiling with local rules with a slope generated by

u =     0 √ 2 √ 2 + 1 √ 2 + 1     , v =     √ 2 + 1 √ 2 + 1 0 √ 2     ,
The subperiod relations:

G 13 -G 23 = 0, 4G 12 -3G 14 + G 24 = 0, G 13 -G 14 = 0, 3G 23 -G 24 + 4G 34 = 0.
Example 3.36 An octagonal tiling with local rules with a slope generated by

u =     √ 3 1 0 √ 3     , v =     1 0 1 √ 3     ,
The subperiod relations:

G 12 + G 23 = 0, 3G 12 + G 14 + G 24 = 0, G 13 + G 34 = 0, G 24 + G 34 = 0.
Example 3.37 An octagonal tiling with local rules with a slope generated by

u =     √ 3 + 1 √ 3 √ 3 1     , v =     √ 3 1 √ 3 √ 3     ,
The subperiod relations:

3G 12 -G 13 + 2G 23 = 0, 2G 14 -3G 24 = 0, G 13 -G 14 + G 34 = 0, G 23 -G 34 = 0.

Example 3.38 An octagonal tiling with local rules with a slope generated by

u =     √ 17 + 1 1 1 √ 17 + 1     , v =     0 1 √ 17 √ 17     ,
The subperiod relations:

9G 12 -G 13 -8G 23 = 0, G 12 -G 14 -16G 24 = 0, G 13 -G 14 = 0, 17G 24 -G = 0.

Example 3.39 An octagonal tiling with local rules with a slope generated by

u =     √ 13 + 1 0 √ 13 + 1 1     , v =     √ 13 + 1 1 0 √ 13 + 1     ,
The subperiod relations:

G 12 + G 23 = 0, G 12 -G 14 -12G 24 = 0, G 13 + G 34 = 0, 2G 23 + 12G 24 + G = 0.

Example 3.40 An octagonal tiling with local rules with a slope generated by

u =     √ 2 √ 2 + 1 √ 2 √ 2 + 1     , v =     √ 2 0 1 1     ,
The subperiod relations:

3G 12 -G 13 + 4G 23 = 0, 2G 12 -G 14 + 2G 24 = 0, G 14 -2G 34 = 0, G 23 -G = 0.

Example 3.41 An octagonal tiling with local rules with a slope generated by

u =     √ 5 + 1 √ 5 + 1 √ 5 √ 5     , v =     √ 5 + 1 1 √ 5 + 1 0     ,
The subperiod relations:

5G 12 + G 13 + 4G 23 = 0, G 12 -G 14 = 0, G 14 -G 34 = 0, 5G 23 -G 24 + 6G 34 = 0

Example 3.42 An octagonal tiling with local rules with a slope generated by

u =     √ 3 + 1 1 1 0     , v =     √ 3 √ 3 + 1 0 √ 3     ,
The subperiod relations:

G 12 -3G 13 + 4G 23 = 0, 3G 12 -4G 14 + G 24 = 0, G 13 + G 34 = 0, G 24 -G 34 = 0.

Example 3.43 An octagonal tiling with local rules with a slope generated by

u =     0 √ 17 √ 17 1     , v =     1 √ 17 + 1 1 0     ,
The subperiod relations:

G 12 -G 13 = 0, G 12 + G 14 -G 24 = 0, G 14 -G 34 = 0, G 23 -17G 34 = 0.

Example 3.44 An octagonal tiling with local rules with a slope generated by

u =     1 √ 7 + 1 1 0     , v =     0 √ 7 + 1 √ 7 + 1 1     ,
The subperiod relations:

G 12 -G 13 = 0, G 12 -G 24 = 0, G 14 -G 34 = 0, G 23 -G 24 -6G 34 = 0

Example 3.45 An octagonal tiling with local rules with a slope generated by

u =     √ 6 √ 6 √ 6 + 1 0     , v =     √ 6 + 1 1 1 1     ,
The subperiod relations:

G 12 -6G 23 = 0, G 14 -G 24 = 0, G 13 -6G 14 + 7G 34 = 0, G 23 -G 24 + G 34 = 0.

Example 3.46 An octagonal tiling with local rules with a slope generated by

u =     √ 2 √ 2 + 1 √ 2 + 1 √ 2 + 1     , v =     1 1 √ 2 0     ,
The subperiod relations:

G 12 + G 23 = 0, G 14 -G 24 = 0, G 13 -3G 14 + 2G 34 = 0, G 23 -G 24 + G 34 = 0.

Example 3.47 An octagonal tiling with local rules with a slope generated by

u =     0 √ 10 + 1 1 1     , v =     1 √ 10 √ 10 0     ,
The subperiod relations:

10G 13 + G 23 = 0, G 12 -G 14 -G 24 = 0, G 13 -G 14 = 0, G 24 -G 34 = 0.

Example 3.48 An octagonal tiling with local rules with a slope generated by

u =     1 sqrt13 + 1 0 1     , v =     √ 13 + 1 √ 13 + 1 √ 13 + 1 √ 13     ,
The subperiod relations:

G 12 -G 13 + G 23 = 0, 12G 14 + G 24 = 0, G 13 + G 34 = 0, G 23 -G 24 + 2G 34 = 0.

Example 3.49 An octagonal tiling with local rules with a slope generated by

u =     √ 3 + 1 √ 3 1 √ 3     , v =     √ 3 √ 3 + 1 √ 3 √ 3     ,
The subperiod relations:

3G 12 -5G 13 +6G 23 = 0, G 14 +G 24 = 0, G 13 -G 14 +G 34 = 0, 3G 23 -G 24 +2G 34 = 0.

Example 3.50 An octagonal tiling with local rules with a slope generated by

u =     0 1 √ 7 √ 7 + 1     , v =     1 √ 7 + 1 1 1     ,
The subperiod relations:

6G 12 +G 13 -G 23 = 0, 5G 12 +2G 14 -G 24 = 0, G 13 -G 14 +G 34 = 0, 2G 23 -G 24 -5G 34 = 0.

Example 3.51 An octagonal tiling with local rules with a slope generated by

u =     1 1 1 √ 10 + 1     , v =     √ 10 0 √ 10 + +1 1     ,
The subperiod relations:

G 12 -G 13 +G 23 = 0, G 12 -G 14 -9G 24 = 0, 8G 13 +2G 14 -G 34 = 0, 2G 23 +8G 24 +G 34 = 0.

Example 3.52 An octagonal tiling with local rules with a slope generated by

u =     1 0 √ 7 √ 7     , v =     0 √ 7 √ 7 √ 7 + 1     ,
The subperiod relations:

G 12 -G 13 = 0, 7G 12 -7G 14 -G 24 = 0, G 13 -G 34 = 0, G 23 -G 24 = 0.

Example 3.53 An octagonal tiling with local rules with a slope generated by

u =     √ 5 + 1 0 1 1     , v =     √ 5 1 1 √ 5 + 1     ,
The subperiod relations:

G 13 + G 23 = 0, G 12 -G 14 -5G 24 = 0, 6G 13 -G 14 + G 34 = 0, G 23 -G 24 = 0.

Example 3.54 An octagonal tiling with local rules with a slope generated by

u =     1 a -1 1 1     , v =     1 1 a a -1     ,
The subperiod relations:

4G 12 + 5G 13 -G 23 = 0, G 12 + G 14 = 0, G 13 -G 14 + G 34 = 0, G 24 + 4G 34 = 0.

Example 3.55 An octagonal tiling with local rules with a slope generated by

u =     √ 6 + 1 √ 6 + 1 1 √ 6 + 1     , v =     0 √ 6 + 1 √ 6 + 1 1     ,
The subperiod relations:

G 12 -G 13 = 0, G 12 -G 14 + G 24 = 0, 4G 13 + 2G 14 + 5G 34 = 0, G 23 + G 24 = 0.

Figure 3.14: Ammann-Beenker tiling. A growth pattern emerging from the seed marked with red. There is no infinite growth. Simulation shows that the empty regions become denser as we move away from the seed until there are no more forced tiles to add at all. Chapter 4

Defective seeds

Growth started with r-patterns as seeds will leave infinitely many empty lines but there is a way to improve. There are certain types of defective seeds, just as in the mentioned OSDS rules algorithm, such that the resulting growth pattern, as simulations suggest, will cover the entire plane except for finite (and untileable) region. Here we present a way to construct such defective seeds.

Lemma 4.1 For any tiling with local rules T and for any R > max(||p i || 1 ) , where {p i } is the set of subperiods of T , there exists a seed D with the following properties:

• every subpattern in D of radius R is correct, i.e., it is a subset of a tiling with the same slope

• R(D) consists of a single point Proof.

We start with a planar tiling T with local rules and a slope E. Consider a new tiling we get by translating the slope E in a direction parallel to one of the sides of the window and then using it in the cut-and-project scheme. What is the difference between the initial tiling and the new one? Some points P old of the initial tiling, the ones with projection on E ⊥ close to the side of the window, disapear in the translated tiling. They are replaced with a set of new points P new with projection close to the other side of the window. Since our tiling has local rules, both sets P old and P new are in fact a collection of families of subperiod lines. The smaller the translation the smaller is the difference. We can vary s to make the subperiod lines that change after the translation as far from each other as necessary.

Consider two vectors s 1 = π ⊥ (e 1 ) and s 2 = π ⊥ (e 2 ). Both translations along s 1 and s 2 introduce series of flips along subperiod lines, each parallel to the subperiods p 1 and p 2 respectively. We assume that s 1 and s 2 are small enough so that the distance between the subperiod lines is at least 5R for both translations. Choose 83 two arbitrary non-collinear subperiod lines, let c ∈ T be the closest vertex to their intersection (if there are more than one, choose any). This point will be the center of the defective seed. Let S := P (c, 2R) \ P (c, R). By construction S contains only two subperiod lines, each line has two segments because of the cut we have made. Now, all we need is to flip one of those segment in each line of flips as depicted in Figure 4.1 to get the seed D with desired properties.

By construction, the region in the window which corresponds to the defective seed R(D) = {point} since D contains two flip lines with mixed orientations as depicted in Figure 4.2. Notice that every centered subpattern of D of radius R is indeed correct because it is a subset of a tiling with the slope E, E + s 1 , E + s 2 or E + s 1 + s 2 . As our simulations suggest, the growth starting from such a defective seed will cover the entire plane except for the untileable region inside the seed. The behaviour is exactly similar to the decapod seed in the case of Penrose tilings. An example of such a growth pattern is depicted in Figure 4.3. We still can see some of the empty stripes but unlike the legal seeds they eventually disapear during the growth.

Conclusion

We have developed a generalisation of OSDS rules algorithm which works not only with Penrose tilings but with a broader class of tilings namely the 4 → 2 cut-andproject tilings with local rules. The generalised algorithm is completely deterministic, a tile is added if and only if there is only one way to so. This algorithm grows large round-shaped patterns, up to an unavoidable but neglectable proportion of missing tiles. The proportion of missing tiles can be made arbitrarily small by taking the starting seed to be big enough. The algorithm is easily generalizable to higher dimensions. This suggests that, contrary to the popular belief firmly rooted in many physicists, there is no need for complex concepts to explain the growth of quasicrystals! These findings strongly support the conjecture that the local selfassembly algorithms are quite general and exist for all the cut-and-project tilings with local rules.

  CONTENTS 3.2.3 Realisation using shadow periodicity . . . . . . . . . . . . . 52 3.2.4 Links between the modifications . . . . . . . . . . . . . . . . 54 3.3 Growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.1 k-worms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4 Mechanics of the growth and information transfer . . . . . . . . . . 64 3.5 Growth viewed in the window . . . . . . . . . . . . . . . . . . . . . 67 3.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Figure 1 . 1 :

 11 Figure 1.1: Electron diffraction pattern of an Al -M n -P d alloy with icosahedral symmetry, similar to the one found by Shechtman.

Definition 1 . 1 A

 11 point set is called a lattice in R d if there exist d vectors b 1 , . . . , b d such thatL = Zb 1 ⊕ • • • ⊕ Zb d := { d i=1 m i b i | m 1 , . . . , m d ∈ Z},together with the requirement that its R-span is R d . The set {b 1 , . . . , b d } is then called a basis of the lattice L.

Theorem 1 .

 1 6 ([START_REF] Berger | The Undecidability of the domino problem[END_REF]) Domino problem is undecidable.

Figure 1 . 3 :

 13 Figure 1.3: Robinson prototileset. Tiles of type (a) are called bumpy corners, tiles of type (b) are called corners, and the tiles (c) -(d) are called arms.

Figure 1 . 4 :

 14 Figure 1.4: Another representation of Robinson prototileset.

Figure 1 . 5 :

 15 Figure 1.5: Supertiles of the second and third order.

Figure 1 .

 1 7 for an example. Definition 1.11 If two tilings are locally derivable from each other, they are called mutually locally derivable.

Figure 1 . 6 :

 16 Figure 1.6: Robinson hierarchy. (a) -supertiles of order 1, (b) -supertiles of order 2 and (c) -supertiles of order 3.

Figure 1 . 7 :

 17 Figure 1.7: Local derivability of Penrose P 1 from Penrose P 3. Drawing the lines on rhombuses as depicted in the bottom, one can construct a Penrose P 1 tilings from a Penrose P 3 tilings locally.

Figure 1 .

 1 Figure 1.8: Original Penrose prototile set. Notches and cuts represent matching rules.

Figure 1 . 9 :

 19 Figure 1.9: Penrose kite and dart prototile set.

Figure 1 .

 1 Figure 1.10: Penrose prototile set. Two tiles must be attached one to another only edge to edge and only in a way that arrows match.

Lemma 1 .

 1 15 ([Gru87]) A Penrose tiling contains arbitrary long Conway worms.

Figure 1 .

 1 Figure 1.11: Cartwheel tiling.

Figure 1 .

 1 Figure 1.12: An unresolved Conway worm (center) paired with two possible orientations (left and right).

Figure 1 .

 1 Figure 1.13: Penrose decomposition.

Figure 1 .

 1 Figure 1.14: A patch of a Penrose tiling.

Figure 1 .

 1 Figure 1.15: Ammann-Beenker tiling.

  and 1.18. More precisely: Definition 1.21 A finite set P on non-overlapping tiles in R d is called a deception of order r, if it is homeomorphic to a d-ball and

Figure 1 .

 1 Figure 1.16: A pattern made with Robinson tileset that is impossible to extend to a tiling.

Figure 1 .

 1 Figure 1.17: A rather small deception for Penrose tiling.

Theorem 1 .

 1 22 ([DS95]) Every aperiodic prototile set in R 2 admits deceptions of all orders.

Figure 1 .

 1 Figure 1.18: Example of a deception for Penrose tiling.

Figure 1 .

 1 Figure 1.19: The rhombic pattern is an example of a dead surface. The borders of the pattern match the borders of a Conway worm. The Conway worm can also be flipped indicating that all the edges on the right side are not forced. Each corner of a dead surface is an exterior of an intersection of two Conway worms, the five possible corners of a dead surface are depicted around the rhombic dead surface.

Figure 1 .

 1 Figure 1.21: The central pattern of the cartwheel tiling (left) and the decapod (right). The decapod can be obtained from the cartwheel by flipping the Conway worms so that all of them have the same orientation.

Figure 1 .

 1 Figure1.22: The growth pattern emerging from decapod seed. As our simulations suggest, the growth continues in every possible direction.

Figure 1 .

 1 Figure 1.23: The dead surface emerging from the only decapod which does not produce infinite growth.

Figure 2 . 1 :

 21 Figure 2.1: 2-atlas of Penrose tiling i.e. the set of all possible 2-patterns around a vertex up to a rotation.

Figure 2

 2 Figure 2.2: A Golden-Octagonal tiling.

  r→∞ sup card(Λ r ) vol(B r ) and dens(Λ) = lim r→∞ inf card(Λ r ) vol(B r ) Note that the inequality 0 ≤ dens(Λ) ≤ dens(Λ) ≤ ∞ is well-defined. If the lower and upper densities coincide, one speaks about density: Definition 2.10 If the upper and the lower density of a point set Λ ⊂ R d coincide, the corresponding value is called the density of Λ and denoted by dens(Λ). Definition 2.11 A point set Λ ⊂ R d is relatively dense if there exists r > 0 such that for any x ∈ Λ, the set B r (x) ∩ Λ is not reduced to {x}. Definition 2.12 A point set Λ ⊂ R d has finite local complexity if for any compact K ⊂ R d the set {(t + K) ∩ Λ|t ∈ R d } contains only finitely many elements up to translations.

  Proposition 2.14 ([START_REF] Lagarias | Meyer's concept of quasicrystal and quasiregular sets[END_REF]) Λ has finite local complexity if and only if the closure of Λ -Λ is discrete.

  .4. The subperiods are: • 234-subperiod p 1 = e 3 + e 4 • 134-subperiod p 2 = e 1 + e 3 • 124-subperiod p 3 = e 2 + e 4 • 123-subperiod p 4 = e 1 + e 2

Figure 2

 2 Figure 2.4: Shadows of a Golden-Octagonal tiling. Each has one periodic direction.

Figure 2

 2 Figure 2.5: A tiling from Example 2.30.

Figure 2

 2 Figure 2.6: A tiling from Example 2.31.

Figure 2 . 7 :

 27 Figure 2.7: Shadows of a tiling from Example 2.30. Periodic direction marked with red.

Definition 3. 1

 1 The set of vertices of a pattern P which are not further than r edges away from a vertex x is called the vertex configuration of radius r and denoted by C(x, r). Lifted vertex configuration with x mapped to the origin is denoted by P (x, r).A vertex configuration is an r-pattern with possibly some vertices missing, see Figure 3.1 for an example.

Figure 3 . 1 :

 31 Figure 3.1: A vertex configuration of radius 4 of a Golden-Octagonal tiling, the center is marked with black.

F

  r (C(x, r)) := {tiles ∈ A \ C(x, r)}.

Figure 3

 3 Figure 3.3: Construction of a 234-shadow by removing all the edges parallel to π(e 1 ).

  2. C(x,r) seen in the 234-shadow. No forced tiles. 3. C(x,r) seen in the 134-shadow. Marked tiles are forced due to periodicity. 4. C(x,r) seen in the 124-shadow. Marked tiles are forced due to periodicity. 5. C(x,r) seen in the 123-shadow. Marked tiles are forced due to periodicity.

Figure 3 . 4 :

 34 Figure 3.4: Shadow voting example.

  Subperiod line of vertex x of type k is the set of vertices along the periodic direction in ijl-shadow, see Figure3.6 for an example. Lemma 3.10 Vertices of a subperiod line of type k if projected to the window are aligned along a line parallel to π ⊥ (e k ).

Figure 3

 3 Figure 3.5: Golden-Octagonal tiling growth process.

Figure 3 . 6 :

 36 Figure 3.6: An example of a subperiod line of a Golden-Octagonal.

2.

  In the window the vertices of the 1-worm are close to the respected border.

Figure 3

 3 Figure 3.7: An example of a 1-worm of a Golden-Octagonal tiling.

Figure 3

 3 Figure 3.8: Growth of a Golden-Octagonal tiling starting from seed which consists only of k-worms.

Figure 3

 3 Figure 3.9: Golden-Octagonal tiling. Two 1-worms with different orientations are marked with grey. The breakpoints are marked with red. The pattern around a breakpoint defines the orientation of entire worm.

Figure 3 .

 3 Figure 3.10: Golden-Octagonal tiling. An example of a pattern with missing tiles where two worms intersect each other.

Figure 3 .

 3 Figure3.11: Golden-Octagonal tiling. A growth pattern with approximately million vertices, the seed is marked with red. The empty stripes do not become denser as we move away from the seed. In this simulation to speed up the computation at each step we add all the forced vertices in the same time, this results in the growth pattern to be shaped as octagon.

Figure 3 . 15 :

 315 Figure 3.15: Golden-Octagonal tiling. The seed P is marked with red, all the tiles in 234 (P ) are forced with radius 6.

Figure 3 .

 3 Figure3.16: Golden-Octagonal tiling. The seed P is marked with red, all the tiles 1-worms with breakpoints inside 234 (P ) are forced with radius 6.

Figure 4 . 1 :

 41 Figure 4.1: Final step in defective seed construction: flipping the segments of the flip lines.

Figure 4 . 2 :

 42 Figure 4.2: Flip lines with mixed orientations.

Figure 4

 4 Figure 4.3: A growth pattern emerging from a defective seed constructed for the Golden-Octagonal tilings. The seed is marked with red.

Figure 1.20: The only possible shapes of dead surfaces.

Acknowledgements

Now, since the window W can be decomposited as a direct sum of the windows of shadows, for k, l = ±1 we write

Once again, since adding t to the vertex configuration does not change R(C(x, r)), then t is forced.

Growth

In this section, we provide arguments about the behaviour of the proposed selfassembly algorithm and formulate the main conjecture. We discuss how seed affects the growth, what are the restrictions on the growth radius and discuss the importance of the k-worms, a straight patterns which are the generalization of Conway worms.

Definition 3.6 We denote the limit growth pattern emerging from seed S with growth radius r as G r (S) or G(S).

How the choice of the seed affects the growth. The algorithm is completely deterministic since only the forced tiles are added. That means that we do not making any choices during the growth process and the resulting pattern is as most the intersection of all the planar octagonal tilings with the same slope, i.e., the empire of the cylinder set of the seed. In particular, although the places where tiles are added are chosen at random, the final grown pattern does not depend on the order these places have been chosen. The simulations we carried with all the planar octagonal tilings mentioned in this thesis support the following conjecture: Conjecture 3.7 For a planar octagonal tiling with local rules T and pattern S taken as a seed, there exists a growth radius, such that the self-assembly algorithm generates the cylinder set of the seed.