Ergodic Theory and Dynamical Systems

Survey Article

Rank and symbolic complexity

Sébastien Ferenczia1

a1 lnstitut de Mathématiques de Luminy, CNRS-UPR 9016, Case 930-163 avenue de Luminy, F13288 Marseille Cedex 9, France (e-mail: ferenczi@iml.univ-mrs.fr)

Abstract

We investigate the relation between the complexity function of a sequence, that is the number p(n) of its factors of length n, and the rank of the associated dynamical system, that is the number of Rokhlin towers required to approximate it. We prove that if the rank is one, then lim , but give examples with lim for any prescribed function G with G (n) = 0(an) for every a > 1. We give exact computations for examples of the ‘staircase’ type, which are strongly mixing systems with quadratic complexity. Conversely, for minimal sequences, if p(n) < an + b for some a ≥ 1, the rank is at most 2[a], with bounded strings of spacers, and the system is generated by a finite number of substitutions.

(Received May 31 1994)

(Revised July 31 1995)