Sturmian word
Encyclopedia
In mathematics
, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite
word
.
. Then, a word w is Sturmian if, for all natural numbers n, w has exactly n + 1 distinct factors of length n: that is, the complexity function
of w is n + 1.
Note that there must then be two distinct factors of length 1, implying that word uses exactly 2 symbols from the alphabet (without loss of generality
we can call these 0 and 1). Also, a Sturmian word is necessarily infinite.
over {0,1} is a Sturmian word if and only if there exist two real number
s
and 
, with 
irrational
, such that
for all
. Thus a Sturmian word provides a discretization
of the straight line with slope
and intercept ρ. Without loss of generality, we can always assume 
, because for any integer k we have
All the Sturmian words corresponding to the same slope
have the same set of factors; the word 
corresponding to the intercept 
is the standard word or characteristic word of slope 
. Hence, if 
, the characteristic word 
is the first difference of the Beatty sequence
corresponding to the irrational number
.
The standard word
is also the limit of a sequence of words 
defined recursively as follows:
Let
be the continued fraction
expansion of
, and define
where the product between words is just their concatenation
. Every word in the sequence
is a prefix of the next ones, so that the sequence itself converges
to an infinite word, which is
.
The infinite sequence of words
defined by the above recursion is called the standard sequence for the standard word 
, and the infinite sequence d = (d1, d2, d3, ...) of nonnegative integers, with d1 ≥ 0 and dn > 0 (n ≥ 2), is called its directive sequence.
A famous example of (standard) Sturmian word is the Fibonacci word
; its slope is
, where 
is the golden ratio
.
(1772), the first comprehensive study of them was by Gustav A. Hedlund
and Marston Morse
in 1940. They introduced the term Sturmian, in honor of the mathematician Jacques Charles François Sturm.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite
Infinity
Infinity is a concept in many fields, most predominantly mathematics and physics, that refers to a quantity without bound or end. People have developed various ideas throughout history about the nature of infinity...
word
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
.
Definition
A word is a (potentially) infinite sequence of symbols drawn from a finite alphabet. Call any finite contiguous subsequence of a word a factorSubstring
A subsequence, substring, prefix or suffix of a string is a subset of the symbols in a string, where the order of the elements is preserved...
. Then, a word w is Sturmian if, for all natural numbers n, w has exactly n + 1 distinct factors of length n: that is, the complexity function
Complexity function
In computer science, the complexity function of a string, a finite or infinite sequence u of letters from some alphabet, is the function of a positive integer n that counts the number of different substrings of n consecutive elements from the string u.A Sturmian word is one of minimal...
of w is n + 1.
Note that there must then be two distinct factors of length 1, implying that word uses exactly 2 symbols from the alphabet (without loss of generality
Without loss of generality
Without loss of generality is a frequently used expression in mathematics...
we can call these 0 and 1). Also, a Sturmian word is necessarily infinite.
Discussion
A sequenceSequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
over {0,1} is a Sturmian word if and only if there exist two real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s
and , with irrationalIrrational number
In mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....
, such that
for all
. Thus a Sturmian word provides a discretizationDiscretization
In mathematics, discretization concerns the process of transferring continuous models and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerical evaluation and implementation on digital computers...
of the straight line with slope
and intercept ρ. Without loss of generality, we can always assume , because for any integer k we have
All the Sturmian words corresponding to the same slope
have the same set of factors; the word corresponding to the intercept is the standard word or characteristic word of slope . Hence, if , the characteristic word is the first difference of the Beatty sequenceBeatty sequence
In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiplesof a positive irrational number...
corresponding to the irrational number
.The standard word
is also the limit of a sequence of words defined recursively as follows:Let
be the continued fractionContinued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on...
expansion of
, and define
where the product between words is just their concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
. Every word in the sequence
is a prefix of the next ones, so that the sequence itself convergesLimit of a sequence
The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...
to an infinite word, which is
.The infinite sequence of words
defined by the above recursion is called the standard sequence for the standard word , and the infinite sequence d = (d1, d2, d3, ...) of nonnegative integers, with d1 ≥ 0 and dn > 0 (n ≥ 2), is called its directive sequence.A famous example of (standard) Sturmian word is the Fibonacci word
Fibonacci word
thumb|350px|Characterization by a [[cutting sequence]] with a line of slope 1/\varphi or \varphi-1, with \varphi the [[golden ratio]].A Fibonacci word is a specific sequence of binary digits...
; its slope is
, where is the golden ratioGolden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...
.
History
Although the study of Sturmian words dates back to Johann III BernoulliJohann III Bernoulli
Johann III Bernoulli , grandson of Johann Bernoulli, and son of Johann II Bernoulli. He studied at Basel and at Neuchâtel, and when thirteen years of age took the degree of doctor in philosophy. At nineteen he was appointed astronomer royal of Berlin...
(1772), the first comprehensive study of them was by Gustav A. Hedlund
Gustav A. Hedlund
Gustav Arnold Hedlund , an American mathematician, was one of the founders of symbolic and topological dynamics.-Biography:Hedlund was born May 7, 1904, in Somerville, Massachusetts. He did his undergraduate studies at Harvard University, earned a masters degree from Columbia University, and...
and Marston Morse
Marston Morse
Harold Calvin Marston Morse was an American mathematician best known for his work on the calculus of variations in the large, a subject where he introduced the technique of differential topology now known as Morse theory...
in 1940. They introduced the term Sturmian, in honor of the mathematician Jacques Charles François Sturm.