On the complexity of subshifts and infinite words
Journal of the European Mathematical Society · 05.01.2026
DOI: 10.4171/jems/1753 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the European Mathematical Society, erschienen am 05.01.2026. Verfasst von Be’eri Greenfeld und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
We characterize the complexity functions of subshifts up to asymptotic equivalence. The complexity function of every aperiodic subshift is non-decreasing, submultiplicative and grows at least linearly. We prove that, conversely, every function satisfying these conditions is asymptotically equivalent to the complexity function of a recurrent subshift, equivalently, a recurrent infinite word. Our construction is explicit, algorithmic in nature and is philosophically based on constructing certain ‘Cantor sets of integers’, whose ‘gaps’ correspond to blocks of zeros. We also prove that every non-decreasing submultiplicative function is asymptotically equivalent, up to a linear error term, to the complexity function of a minimal subshift.
Zitieren
APA
Greenfeld, B., Moreira, C. G., & Zelmanov, E. (2026). On the complexity of subshifts and infinite words. Journal of the European Mathematical Society. https://doi.org/10.4171/jems/1753
Vancouver
Greenfeld B, Moreira CG, Zelmanov E. On the complexity of subshifts and infinite words. Journal of the European Mathematical Society. 2026. doi:10.4171/jems/1753
BibTeX
@article{Greenfeld2026,
author = {Greenfeld, Be’eri and Moreira, Carlos Gustavo and Zelmanov, Efim},
title = {On the complexity of subshifts and infinite words},
journal = {Journal of the European Mathematical Society},
year = {2026},
doi = {10.4171/jems/1753}
}
EUVIMED