A Generalization of Sturmian Sequences: Combinatorial Structure and Transcendence

By Rebecca N. Risley, Luca Q. Zamboni. 2000

64 citations recorded by the source corpus.

We investigate a class of minimal sequences on a finite alphabet Ak = {1,2,...,k} having (k - 1)n + 1 distinct subwords of length n. These sequences, originally defined by P. Arnoux and G. Rauzy, are a natural generalization of binary Sturmian sequences. We describe two simple combinatorial algorithms for constructing characteristic Arnoux-Rauzy sequences (one of which is new even in the Sturmian case). Arnoux-Rauzy sequences arising from fixed points of primitive morphisms are characterized by an underlying periodic structure. We show that every Arnoux-Rauzy sequence contains arbitrarily large subwords of the form V^2+ε and, in the Sturmian case, arbitrarily large subwords of the form V^3+ε. Finally, we prove that an irrational number whose base b-digit expansion is an Arnoux-Rauzy sequence is transcendental.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/30b3380abc38fb3601910dca44aaacfc2f154e0e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Initial powers of Sturmian sequences (2006, background): “There are a number of recent papers on powers of words occurring in Sturmian sequences (see for instance [2, 3, 8, 9, 18, 17, 28, 34, 42, 45]).”
Sturmian and episturmian words: a survey of some recent results (2007, unknown): “This computation rule is given in [25].”
On the complexity of algebraic numbers I. Expansions in integer bases (2005, background): “N T ] 2 8 N ov 2 00”
Structure of three-interval exchange transformations II: a combinatorial description of the tranjectories (2003, methodology): “1 below; the “if” part uses two new tools, the negative slope expansion which is the algorithm of simultaneous approximation defined and studied in [11], and the hat algorithm first defined in [16] for other types of sequences; the hat algorithm allows us to code a language satisfying the four condi”
Maximal pattern complexity for discrete systems (2002, background): “From the point of view of block complexity, this β is the simplest natural generalization of Sturmian words to a three-letter alphabet, with the Tribonacci substitution, the analogue of the Fibonacci substitution (see also [7, 10]), and is called the tribonacci word.”
Strictly Ergodic Subshifts and Associated Operators (2005, background): “Let (2) θ = 1 a1 + 1 a2 + 1 a3 + · · · be the continued fraction expansion of θ with uniquely determined ak ∈ Z+. Truncation of this expansion after k steps yields rational numbers pk/qk that obey p0 = 0, p1 = 1, pk = akpk−1 + pk−2,(3) q0 = 1, q1 = a1, qk = akqk−1 + qk−2.”
Sur la complexité des nombres algébriques (2004, background): “Plusieurs auteurs ont ensuite utilisé la condition combinatoire de [7] afin d’exhiber de nouveaux exemples de nombres transcendants de faible comblexité (voir [3,4] et [13]).”