Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSubstitutive structure of Jeandel-Rao aperiodic tilings
147
0
0.0
(
0
)
Added by
S\\'ebastien Labb\\'e
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Sebastien Labbe
Ask ChatGPT about the research
No Arabic abstract
Jeandel and Rao proved that 11 is the size of the smallest set of Wang tiles, i.e., unit squares with colored edges, that admit valid tilings (contiguous edges of adjacent tiles have the same color) of the plane, none of them being invariant under a nontrivial translation. We study herein the Wang shift $Omega_0$ made of all valid tilings using the set $mathcal{T}_0$ of 11 aperiodic Wang tiles discovered by Jeandel and Rao. We show that there exists a minimal subshift $X_0$ of $Omega_0$ such that every tiling in $X_0$ can be decomposed uniquely into 19 distinct patches of sizes ranging from 45 to 112 that are equivalent to a set of 19 self-similar and aperiodic Wang tiles. We suggest that this provides an almost complete description of the substitutive structure of Jeandel-Rao tilings, as we believe that $Omega_0setminus X_0$ is a null set for any shift-invariant probability measure on $Omega_0$. The proof is based on 12 elementary steps, 10 of which involve the same procedure allowing one to desubstitute Wang tilings from the existence of a subset of marker tiles. The 2 other steps involve the addition of decorations to deal with fault lines and changing the base of the $mathbb{Z}^2$-action through a shear conjugacy. Algorithms are provided to find markers, recognizable substitutions, and shear conjugacy from a set of Wang tiles.
rate research
Read More
We define a partition $mathcal{P}_0$ and a $mathbb{Z}^2$-rotation ($mathbb{Z}^2$-action defined by rotations) on a 2-dimensional torus whose associated symbolic dynamical system is a minimal proper subshift of the Jeandel-Rao aperiodic Wang shift defined by 11 Wang tiles. We define another partition $mathcal{P}_mathcal{U}$ and a $mathbb{Z}^2$-rotation on $mathbb{T}^2$ whose associated symbolic dynamical system is equal to a minimal and aperiodic Wang shift defined by 19 Wang tiles. This proves that $mathcal{P}_mathcal{U}$ is a Markov partition for the $mathbb{Z}^2$-rotation on $mathbb{T}^2$. We prove in both cases that the toral $mathbb{Z}^2$-rotation is the maximal equicontinuous factor of the minimal subshifts and that the set of fiber cardinalities of the factor map is ${1,2,8}$. The two minimal subshifts are uniquely ergodic and are isomorphic as measure-preserving dynamical systems to the toral $mathbb{Z}^2$-rotations. It provides a construction of these Wang shifts as model sets of 4-to-2 cut and project schemes. A do-it-yourself puzzle is available in the appendix to illustrate the results.
An aperiodic tile set was first constructed by R.Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals) We present a new construction of an aperiodic tile set that is based on Kleenes fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. The flexibility of this construction allows us to construct a robust aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. This property was not known for any of the existing aperiodic tile sets.
Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $(3+epsilon)omega(G)+6$ colors, for any constant $epsilon>0$, where $omega(G)$ is the clique number of $G$. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68omega(G)$ colors in $O(2^{sqrt{log log n}})$ rounds. Moreover, when $omega(G)=O(1)$, the algorithm runs in $O(log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4omega(G)$, which would imply the existence of a $O(log n)$ round algorithm coloring any unit-disk graph $G$ with (approximatively) $4omega(G)$ colors.
We define a Wang tile set $mathcal{U}$ of cardinality 19 and show that the set $Omega_mathcal{U}$ of all valid Wang tilings $mathbb{Z}^2tomathcal{U}$ is self-similar, aperiodic and is a minimal subshift of $mathcal{U}^{mathbb{Z}^2}$. Thus $mathcal{U}$ is the second smallest self-similar aperiodic Wang tile set known after Ammanns set of 16 Wang tiles. The proof is based on the unique composition property. We prove the existence of an expansive, primitive and recognizable $2$-dimensional morphism $omega:Omega_mathcal{U}toOmega_mathcal{U}$ that is onto up to a shift. The proof of recognizability is done in two steps using at each step the same criteria (the existence of marker tiles) for proving the existence of a recognizable one-dimensional substitution that sends each tile either on a single tile or on a domino of two tiles.
The goal of this chapter is to illustrate a generalization of the Fibonacci word to the case of 2-dimensional configurations on $mathbb{Z}^2$. More precisely, we consider a particular subshift of $mathcal{A}^{mathbb{Z}^2}$ on the alphabet $mathcal{A}={0,dots,18}$ for which we give three characterizations: as the subshift $mathcal{X}_phi$ generated by a 2-dimensional morphism $phi$ defined on $mathcal{A}$; as the Wang shift $Omega_mathcal{U}$ defined by a set $mathcal{U}$ of 19 Wang tiles; as the symbolic dynamical system $mathcal{X}_{mathcal{P}_mathcal{U},R_mathcal{U}}$ representing the orbits under some $mathbb{Z}^2$-action $R_mathcal{U}$ defined by rotations on $mathbb{T}^2$ and coded by some topological partition $mathcal{P}_mathcal{U}$ of $mathbb{T}^2$ into 19 polygonal atoms. We prove their equality $Omega_mathcal{U} =mathcal{X}_phi=mathcal{X}_{mathcal{P}_mathcal{U},R_mathcal{U}}$ by showing they are self-similar with respect to the substitution $phi$. This chapter provides a transversal reading of results divided into four different articles obtained through the study of the Jeandel-Rao Wang shift. It gathers in one place the methods introduced to desubstitute Wang shifts and to desubstitute codings of $mathbb{Z}^2$-actions by focussing on a simple 2-dimensional self-similar subshift. SageMath code to find marker tiles and compute the Rauzy induction of $mathbb{Z}^2$-rotations is provided allowing to reproduce the computations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
