betaFeedback

WorksMathematics

Polynomial complexity, random graphs, and strict ergodicity

Abstract

We construct infinite words ww 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.

Paper details

vlnc:W_wwd5dys6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…