#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

Date: Nov 11, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited (continued)
The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК