research papers
Multidimensional color codes for chair tilings
^{a}Department of Physics, BenGurion University of the Negev, Beersheba, Israel, and ^{b}Department of Computer Science, BenGurion University of the Negev, Beersheba, Israel
^{*}Correspondence email: shelomo.benabraham@gmail.com
Ordered aperiodic structures have been of interest to the crystallographic community for several decades, and study of them has in turn led to the study of lattice substitution systems, model sets and chair tilings. In this work a color code for chair tilings in arbitrary dimensions is presented. In two and three dimensions, it is expedient to translate the digital codes into colors. An explicit example of a threedimensional color coding covering one octant is constructed. The tiling is then extended to the whole threedimensional space and an indication is given of how to do this in arbitrary dimensions. Illustrations of some fourdimensional objects are also shown. The principle of color coding can be applied to other complex tilings such as brick tiling.
Keywords: chair tilings; letter codes; digital codes; color codes; aperiodic structures; quasicrystals.
1. Introduction
The interest of the crystallographic community in ordered aperiodic structures was aroused by two significant innovations, the introduction of the , 1980) and, mainly, the discovery of quasicrystals (short for quasiperiodic crystals) by Shechtman et al. (1984).
approach for dealing with modulated structures by Janner & Janssen (1977The work reported in this paper is part of a project generalizing onedimensional sequences and twodimensional structures to higher dimensions (BenAbraham & Quandt, 2011; BenAbraham et al., 2013, 2014; Lee et al., 2016). A preliminary short report on the present subject was published in the Proceedings of ICQ 13 (Flom & BenAbraham, 2017).
Lee & Moody (2001) studied lattice substitution systems and model sets and, among other things, generalized the chair tiling in principle to arbitrary dimensions. They also proved for chair tilings in all dimensions that, if each chair is marked with a single scattering point in a consistent way, for instance at the inner corner, then the set of points from the chairs of any one kind (orientation) is a model set and hence a purepoint (Bragg) diffraction set. Consequently, the diffraction spectrum of the entire tiling is pure point since it is a union of all partial spectra.
Robinson put forward a fourcolor code for the twodimensional chair tiling. Here we generalize this code to arbitrary dimensions. We call the result Color Code for Chair Tiling (CCCT in what follows). Incidentally, statements about d dimensions are valid even in zero and one dimension, but these cases are extremely degenerate so they are of no interest. We explicitly elaborate the threedimensional case. The twodimensional chair tiling (sometimes also called the tiling) is well known. A thorough discussion can be found in the paper by Robinson (1999), and see also Baake & Grimm (2013).
Solomyak (1997) studied the dynamics of selfsimilar tilings and, among others, proved that the chair tiling is purepoint diffractive. Robinson followed this with a thorough discussion of the twodimensional chair tiling and put forward a fourcolor substitution tiling which codes for the twodimensional chair tiling. A reader seriously interested in the mathematical background of the subject is advised to read these three seminal treatises. For what is to follow, we advise the reader who is not familiar with projections from higherdimensional spaces to read Flatland by Abbott (1884) and consult Wikipedia on the subject (https://en.wikipedia.org/wiki/Fourdimensional_space), where numerous relevant items are presented.
2. Preliminaries
In order to consider a ddimensional chair tiling it is worthwhile starting with a basic configuration: a ddimensional cube (in what follows Q_{d}, or simply Q when there can be no confusion) with edge length of two units and composed of 2^{d} unit cubes q_{d}, or simply q when there can be no confusion. Figs. 1 and 2 show this for two and three dimensions, respectively. If necessary, we shall also denote by q(c) a q of color c.
A ddimensional chair C_{d} (or simply C when there can be no confusion) is a Q_{d} with one q removed. Fig. 3 shows this for three dimensions.
A chair is a reptile. That is to say, it can be tiled by smaller copies of itself ad infinitum. By the same token, it induces by inflation an infinite substitution tiling.
The original way of constructing the twodimensional chair tiling is by inflation, and this is shown in Fig. 4.
The conventional way to label the q's is by arrows along one of the body diagonals, with the arrows pointing towards the center of the respective Q; this is shown in Fig. 5 for two dimensions. It is, however, convenient and expedient to translate the arrow labeling into an alphabet of 2^{d} letters/digits/colors. In what follows we shall usually refer to them simply as colors. The assignment of arrows, number codes and colors for two dimensions is shown in Table 1.

To make this paper selfcontained, and also for comparison with the construction of the twodimensional chair tiling by inflation, we recall Robinson's labeling by a color code and construction by substitution. The substitution is shown in Fig. 6, which also displays the twodimensional protochairs (shown by thick lines) and their cyclic color change. Yet there is a caveat: the orientation of the chairs depends on the sector. What is shown is valid in the upper right quadrant [1 1]. In the lower left quadrant all chairs will be reflected (flipped) around the diagonal of unequal squares. Incidentally, we remark that while the generally accepted way of labeling the colors is by the digits 0, 1, 2, 3, Robinson originally denoted them p, q, r, s, respectively. Generations 0 to 3 of the tiling are shown in Fig. 7, where the resulting twodimensional chairs and their inflation are also explicitly shown. We observe that the block substituting for q(c) is always a Q_{2}, with the q diametrically opposite to q(c) replaced by q(c) itself.
3. Multidimensional color codes
For completeness, as well as for comparison with the construction by CCCT substitution, we start by showing the basics of the threedimensional inflation (Fig. 8). An exploded view of the inflation is shown in Fig. 9.
The assignment of arrows, number codes and colors for three dimensions is shown in Table 2. The convention for three dimensions is as follows. The number codes of diametrically opposite q_{3}'s are of opposite parity and sum to 7. This rule immediately generalizes to any dimension except 2. In higher dimensions the coding by actual colors becomes impractical. Thus, it would be probably rather hard to find 2^{d} sufficiently different hues for d ≥ 4. We observe that, within a Q_{d} in any dimension, the parity of the nearest neighbors of a given q_{d} is opposite to that of q_{d}. In any even dimension (such as two dimensions) the substitution upholds this rule. On the other hand, in any odd dimension (such as three dimensions) the substitution violates this rule, since the initial q replaces its diametrical counterpart even though their parities are opposite.

In any dimension d, the symmetry of the entire structure is that of a ddimensional cube colored by 2^{d} colors. It is easy to see that the symmetry of Q_{d} propagates throughout the whole structure in all generations. Thus, in two dimensions, the group is 4′m′, and in three dimensions the group is m′3′m′, where the prime indicates a change of color.
The starting q stays invariant throughout the main body diagonal which is the propagation direction of the structure. Consequently, its corresponding chair also propagates with it diagonally. Thus, for instance, in three dimensions starting with 0, all q's in the main diagonal are 0's (yellow) and stay surrounded by the remaining six q's of the respective chair.
The twodimensional code tiling substitution generalizes to arbitrary dimensions. A twodimensional representation of Q_{3} is shown in Fig. 10; this is required for construction of the threedimensional case. For three dimensions we show the substitution explicitly in Fig. 11. Generations 0, 1, 2 of the threedimensional CCCT starting with 0 are shown in Fig. 12.
4. Tiling the whole space
What has been said up to now refers to tilings that cover one sector (quadrant, octant etc.). In order to extend the tiling to the whole ddimensional structure, one must start by seeding the basic configuration Q_{d} and continue therefrom. For two dimensions this is shown in Fig. 13. A large twodimensional picture can also be found in the book by Baake & Grimm (2013) even though it is in a quite different context. The diligent reader is invited to do that for three dimensions and/or look at the supporting information, which shows the sixteen 16 × 16 matrices of the third generation of the threedimensional CCCT. Here we focus on three dimensions. Projections of the hull of the second generation of threedimensional CCCT are shown in Fig. 14.
5. Four dimensions
In principle, there is no problem extending the construction to any dimension, but the requirements on space grow exponentially. Therefore, we limit ourselves to presenting only some basics. As has already been said, it is practically impossible to find 16 distinguishable hues. Therefore, to represent the fourdimensional version with colors we choose to assign the same color to diametrically opposite q_{4}'s. Displaying the whole fourdimensional inflation would take too much space, so we show in Fig. 15 only the inflation starting with 0 (yellow).
A twodimensional projection of the fourdimensional colored basic configuration Q_{4} is shown in Fig. 16. A twodimensional projection of the fourdimensional colored chair C_{4} is shown in Fig. 17. Finally, Fig. 18 shows a twodimensional projection of part of the hull of the second generation of the fourdimensional CCCT. We remark that the isometric (short for axonometric) threedimensional projection of a 4cube is a rhombic dodecahedron and that, in turn, projects to two dimensions as a regular octagon partitioned as shown in the figure.
6. Conclusions
We have constructed a coding substitution tiling of chair tilings in arbitrary dimensions. In two and three dimensions, it is expedient to translate the digital codes into colors. We have constructed an explicit example of a threedimensional color coding covering one octant. We have then extended the tiling to the whole threedimensional space and indicated how to do this in arbitrary dimensions. We have also shown illustrations of some fourdimensional objects. The principle of color coding can be applied to other complex tilings such as the brick tiling.
Supporting information
Figures showing the 16 matrices, each 16x16, of CCCT. Each figure is a layer of the third generation of the 3D tiling mentioned in Section 4. DOI: https://doi.org/10.1107/S2053273322004065/ae5109sup1.pdf
References
Abbott, E. A. (1884). Flatland: A Romance of Many Dimensions. London: Seeley and Co. Google Scholar
Baake, M. & Grimm, U. (2013). Aperiodic Order. Vol. 1, A Mathematical Invitation. Cambridge University Press. Google Scholar
BenAbraham, S. I., Flom, D., Richman, R. A. & Shapira, D. (2014). Acta Phys. Pol. A, 126, 435–437. CAS Google Scholar
BenAbraham, S. I. & Quandt, A. (2011). Philos. Mag. 91, 2718–2727. CAS Google Scholar
BenAbraham, S. I., Quandt, A. & Shapira, D. (2013). Acta Cryst. A69, 123–130. CrossRef IUCr Journals Google Scholar
Flom, D. & BenAbraham, S. I. (2017). J. Phys. Conf. Ser. 809, 012025. CrossRef Google Scholar
Janner, A. & Janssen, T. (1977). Phys. Rev. B, 15, 643–658. CrossRef CAS Web of Science Google Scholar
Janner, A. & Janssen, T. (1980). Acta Cryst. A36, 399–408. CrossRef CAS IUCr Journals Web of Science Google Scholar
Lee, J.Y., Flom, D. & BenAbraham, S. I. (2016). Acta Cryst. A72, 391–394. CrossRef IUCr Journals Google Scholar
Lee, J.Y. & Moody, R. V. (2001). Discrete Comput. Geom. 25, 173–201. Web of Science CrossRef Google Scholar
Robinson, E. A. Jr (1999). Indagationes Math. 10, 581–599. CrossRef Google Scholar
Shechtman, D., Blech, I., Gratias, D. & Cahn, J. W. (1984). Phys. Rev. Lett. 53, 1951–1953. CrossRef CAS Web of Science Google Scholar
Solomyak, B. (1997). Ergod. Th. Dyn. Sys. 17, 695–738. CrossRef Web of Science Google Scholar
This is an openaccess article distributed under the terms of the Creative Commons Attribution (CCBY) Licence, which permits unrestricted use, distribution, and reproduction in any medium, provided the original authors and source are cited.