Deterministic coloring of a family of complexes

I. A. Ivanov-Pogodaev ; A. Ya. Kanel-Belov

Fundamentalʹnaâ i prikladnaâ matematika, Tome 24 (2022) no. 2, pp. 37-180

Résumé

In the famous works “Tilings, substitution systems and dynamical systems generated by them” by S. Mozes and “Matching rules and substitution tilings” by Ch. Goodman-Strauss, important properties of tiling on the plane connecting the language of substitution systems and local rules are investigated. In particular, it is proved that with almost any substitution system of tiles, it is possible to link a system of decorations and local rules to the boundaries of tiles in such a way that any tiling of the plane allowed by the rules will belong to the family generated by this substitution system. Geometric constructions based on tiling and geometric complexes of glued squares open up new opportunities for the study and construction of algebraic objects. An important property of tiling that allows them to be associated with algebraic objects is determinicity. For square tiles whose sides are painted in a finite number of colors, this property means that the colors of the two adjacent sides of each tile uniquely determine the colors of the other pair of sides. J. Kari and P. Papasoglu constructed a deterministic aperiodic set. Thus, the analogue of the theorems of Goodman-Strauss and Mozes with an additional determinicity condition is an important statement in the theory of aperiodic mosaics. We prove an analog of this statement for a specific fixed substitution system. But its arbitrariness allows us to hope for the possibility of improving the construction for the general case. This system is important when constructing an infinite finitely presented nilsemigroup, which solves the problem of L. N. Shevrin and M. V. Sapir. The work is also devoted to the construction of a family of geometric complexes and the introduction of coding of vertices and edges on them. For the resulting complex, both properties are fulfilled simultaneously: finiteness of the set of defining local rules and determinicity on paths of length $2$ on minimal squares.

Bibliographie

[1] Ivanov-Pogodaev I. A., Kanel-Belov A. Ya., “Konechno opredelennaya nilpolugruppa: kompleksy s ravnomernoi elliptichnostyu”, Izv. RAN. Ser. matem., 85:6 (2021), 126–163 | DOI | MR | Zbl

[2] Berger R., The undecidability of the domino problem, Ph.D. Thesis, Harvard University, 1964

[3] Conway J., Lagarias J., “Tiling with polyminoes and combinatorial group theory”, J. Combin. Theory. Ser. A, 53:2 (1990), 183–208 | DOI | MR | Zbl

[4] Durand B., Levin L., Shen A., “Local rules and global order, or aperiodic tilings”, Math. Intelligencer., 27 (2005), 64–68 | DOI | MR | Zbl

[5] Goodman-Strauss Ch., “Matching rules and substitution tilings”, Ann. Math. (2), 147:1 (1998), 181–223 | DOI | MR | Zbl

[6] Gromov M., “Hyperbolic groups”, Essays in Group Theory, MSRI, 8, ed. S. M. Gersten, Springer, 1987, 75–263

[7] Ivanov-Pogodaev I., Malev S., Sapir O., “A construction of a finitely presented semigroup containing an infinite squarefree ideal with zero multiplication”, Int. J. Algebra Comput., 28:8 (2018), 1565–1573 | DOI | MR | Zbl

[8] Kari J., Papasoglu P., “Deterministic aperiodic tile sets”, Geom. Funct. Anal., 9 (1999), 353–369 | DOI | MR | Zbl

[9] Mozes Sh., “Tilings, substitution systems and dynamical systems generated by them”, J. Anal. Math., 53:1 (1989), 139–186 | DOI | MR | Zbl

[10] Robinson R. M., “Undecidability and nonperiodicity for tilings of the plane”, Invent. Math., 12 (1971), 177–209 | DOI | MR | Zbl

[11] Wang Hao, “Proving theorems by pattern recognition. II”, Bell System Tech. J., 40:1 (1961), 1–41 | DOI

[12] Wise D., Non-positively curved squared complexes, aperiodic tilings, and non-residually finite groups, Ph.D. Thesis, Princeton University, 1996

[13] Wise D., “Cubulating small cancellation groups”, Geom. Funct. Anal., 14 (2004), 150–214 | DOI | MR | Zbl