2025/08/22 by Greenfeld, Be'eri, Moreira, Carlos Gustavo, Zelmanov, Efim
#Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics #Rings and Algebras (math.RA)
paper · doi:10.48550/arxiv.2508.16840
We study the asymptotics and fine-scale behavior of quantitative combinatorial measures of infinite words and related dynamical and algebraic structures. We construct infinite recurrent words w whose complexity functions pw(n) are arbitrarily close to linear, but whose discrete derivatives are not bounded from above by pw(n)/n. Moreover, we construct words of polynomially bounded complexity whose discrete derivatives exceed pw(n)/nε infinitely often, for every given ε>0. These provide negative answers in a strong sense to an open question of Cassaigne from 1997, showing that his theorem on words of linear complexity is best possible. Next, we characterize, up to a linear multiplicative error, the complexity functions of strictly ergodic subshifts, showing that every non-decreasing, submultiplicative function arises in this setting. This gives the first `industrial' construction of strictly ergodic subshifts of prescribed subexponential complexity. We then investigate quantitative recurrence in uniformly recurrent words and, as an application, address a question of Bavula from 2006 related to holonomic inequalities on the spectrum of possible filter dimensions of simple associative algebras: we construct simple algebras of prescribed filter dimension in [1,∞) and essentially settling the problem entirely in the graded case. Throughout, we construct uniformly recurrent words of linear complexity and with arbitrary polynomial recurrence growth.