Polynomial complexity, random graphs, and strict ergodicity
Abstract
We construct infinite words w whose complexity functions are quadratically bounded, but whose discrete derivatives are not linearly bounded, resolving a question of Cassaigne. Moreover, we construct infinite words of polynomially bounded complexity, and subshifts of quasi-linear complexity, whose discrete derivatives do not decay compared to their complexity functions, thus exhibiting a typical exponentially-growing behavior. As an application, we give the first examples of subshifts of polynomial complexity whose Rauzy graphs do not have Benjamini-Schramm limits. Finally, we realize (up to an inevitable linear error factor) every function satisfying the necessary conditions, as the complexity function of a minimal, uniquely ergodic, cube-free subshift, strengthening previous realization results in this direction, and derive consequences for the growth of simple algebras and just-infinite semigroups satisfying nontrivial laws.
Related
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- Sharp detection thresholds for random geometric graphs with polynomial average degrees
- On the exponential ergodicity of the McKean-Vlasov SDE depending on a polynomial interaction
- Tempered Langevin diffusions with polynomial-tailed targets: explosions, moment thresholds and ergodicity
- Ergodicity of (co)expanding on average random dynamical systems
BibTeX
@misc{greenfeld2026polynomial,
title = {{Polynomial complexity, random graphs, and strict ergodicity}},
author = {Be'eri Greenfeld and Paul-Henry Leemann and Carlos Gustavo Moreira and Efim Zelmanov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08973},
eprint = {2611.08973},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08973},
}
RIS
TY - UNPB
TI - Polynomial complexity, random graphs, and strict ergodicity
AU - Be'eri Greenfeld
AU - Paul-Henry Leemann
AU - Carlos Gustavo Moreira
AU - Efim Zelmanov
PY - 2026
DA - 2026/11/06
PB - arXiv
DO - 10.48550/arxiv.2611.08973
UR - https://arxiv.org/abs/2611.08973
AB - We construct infinite words w whose complexity functions are quadratically bounded, but whose discrete derivatives are not linearly bounded, resolving a question of Cassaigne. Moreover, we construct infinite words of polynomially bounded complexity, and subshifts of quasi-linear complexity, whose discrete derivatives do not decay compared to their complexity functions, thus exhibiting a typical exponentially-growing behavior. As an application, we give the first examples of subshifts of polynomial complexity whose Rauzy graphs do not have Benjamini-Schramm limits. Finally, we realize (up to an inevitable linear error factor) every function satisfying the necessary conditions, as the complexity function of a minimal, uniquely ergodic, cube-free subshift, strengthening previous realization results in this direction, and derive consequences for the growth of simple algebras and just-infinite semigroups satisfying nontrivial laws.
ER -