Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-26T12:46:28.386Z Has data issue: false hasContentIssue false
  • English
  • Français

Rank and symbolic complexity

Published online by Cambridge University Press:  19 September 2008

Sébastien Ferenczi
Sébastien Ferenczi
Affiliation:
lnstitut de Mathématiques de Luminy, CNRS-UPR 9016, Case 930-163 avenue de Luminy, F13288 Marseille Cedex 9, France (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Type
Survey Article
Information
Ergodic Theory and Dynamical Systems , Volume 16 , Issue 4 , August 1996 , pp. 663 - 682
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[A]Adams, T. M.. Smorodinsky's conjecture. Submitted, 1993.Google Scholar
[AF]Adams, T. M. and Friedman, N. A.. Staircase mixing. Submitted, 1992.Google Scholar
[AR]Arnoux, P. and Rauzy, G.. Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991), 199–215.Google Scholar
[C]Cassaigne, J.. Facteurs spéciaux des suites de complexité sous-affine. Preprint.Google Scholar
[Ch]Chacon, R. V.. A geometric construction of measure-preserving transformations. Proc. Fifth Berkeley Symp. on Mathematical Statistics and Probability. University of California Press, Berkeley, CA, 1965, pp. 335–360.Google Scholar
[Co]Cobham, A.. Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192.CrossRefGoogle Scholar
[deJ]del Junco, A.. Transformations with discrete spectrum are stacking transformations. Canadian J. Math. 24 (1976), 836–839.CrossRefGoogle Scholar
[F]Ferenczi, S.. Les transformations de Chacon: combinatoire, structure géométrique, liens avec les systèmes de complexité 2n + 1. Bull. Soc. Math. France 123 (1995), 271–292.Google Scholar
[HM1]Hedlund, G. A. and Morse, M.. Symbolic dynamics. Am. J. Math. 60 (1938), 815–866.Google Scholar
[HM2]Hedlund, G. A. and Morse, M.. Symbolic dynamics II. Sturmian trajectories. Am. J. Math. 62 (1940), 1–42.Google Scholar
[K]Kalikow, S.. Twofold mixing implies threefold mixing for rank-1 transformations. Ergod. Th. & Dynam. Sys. 4 (1984), 237–259.CrossRefGoogle Scholar
[O]Ornstein, D. S.. On the root problem in ergodic theory. Proc. Sixth Berkeley Symp. on Mathematical Statistics and Probability. University of California Press, Berkeley, CA, 1970, pp. 347–356.Google Scholar
[ORW]Ornstein, D. S., D. J. Rudolph and B. Weiss. Equivalence of measure preserving transformations. Mem. Am. Math. Soc. 262 (1982).Google Scholar
[Q]Queffelec, M.. Substitution dynamical systems—spectral analysis. Lecture Notes in Mathematics 1294. Springer, Berlin, 1987.Google Scholar