{"id":"arxiv/2611.08973","url":"https://arxiv.org/abs/2611.08973","tags":["math.DS","math.CO"],"score":0,"title":"Polynomial complexity, random graphs, and strict ergodicity","domain":"math.DS","source":"arxiv","authors":["Be'eri Greenfeld","Paul-Henry Leemann","Carlos Gustavo Moreira","Efim Zelmanov"],"reviews":0,"subject":"math.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-06","reactions":{}}