October 30, 2017 | Author: Anonymous | Category: N/A
An introduction to combinatorics on words: balanced words, Lyndon words, and palindromes. Amy Glen ......
An introduction to combinatorics on words: balanced words, Lyndon words, and palindromes Amy Glen School of Engineering & IT Murdoch University, Perth, Australia
[email protected] http://amyglen.wordpress.com
40ACCMCC @ The University of Newcastle December 12–16, 2016 Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
1
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 001001001001001001001001001001 · · ·
I
1100111100011011101111001101110010111111101 · · ·
I
100102110122220102110021111102212222201112012 · · ·
I
1121212121212 · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
2
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 0. 01001001001001001001001001001 . . .
I
1100111100011011101111001101110010111111101 · · ·
I
100102110122220102110021111102212222201112012 · · ·
I
1121212121212 · · ·
↑
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
2
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 0.01001001001001001001001001001 . . . = (2/7)2
I
1100111100011011101111001101110010111111101 · · ·
I
100102110122220102110021111102212222201112012 · · ·
I
1121212121212 · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
2
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 0.01001001001001001001001001001 . . . = (2/7)2
I
1. 100111100011011101111001101110010 . . .
I
100102110122220102110021111102212222201112012 · · ·
I
1121212121212 · · ·
↑
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
2
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 0.01001001001001001001001001001 . . . = (2/7)2
I
1.100111100011011101111001101110010 . . . = ((1 +
I
100102110122220102110021111102212222201112012 · · ·
I
1121212121212 · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
√
5)/2)2
December, 2016
2
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 0.01001001001001001001001001001 . . . = (2/7)2
I
1.100111100011011101111001101110010 . . . = ((1 +
I
10. 0102110122220102110021111102212222201112012 . . .
I
1121212121212 · · ·
√
5)/2)2
↑
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
2
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 0.01001001001001001001001001001 . . . = (2/7)2
I
1.100111100011011101111001101110010 . . . = ((1 +
I
10.0102110122220102110021111102212222201112012 . . . = (π)3
I
1121212121212 · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
√
5)/2)2
December, 2016
2
Background
Intro
Words A word is finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Examples I
001
I
(001)∞ = 0.01001001001001001001001001001 . . . = (2/7)2
I
1.100111100011011101111001101110010 . . . = ((1 +
I
10.0102110122220102110021111102212222201112012 . . . = (π)3
I
[1; 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, . . .] =
Amy Glen (Murdoch University)
√
√
5)/2)2
3
An introduction to combinatorics on words
December, 2016
2
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15). I It lies on the border of discrete mathematics and theoretical computer science,
with applications not only in these two areas (e.g., transcendental number theory, pattern recognition, data compression), but also in other fields, such as theoretical physics (e.g., quasicrystal modelling) and molecular biology (e.g., DNA sequences).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15). I It lies on the border of discrete mathematics and theoretical computer science,
with applications not only in these two areas (e.g., transcendental number theory, pattern recognition, data compression), but also in other fields, such as theoretical physics (e.g., quasicrystal modelling) and molecular biology (e.g., DNA sequences). I Connections with algebra are very deep — indeed, a natural environment of a
finite word is a free monoid.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15). I It lies on the border of discrete mathematics and theoretical computer science,
with applications not only in these two areas (e.g., transcendental number theory, pattern recognition, data compression), but also in other fields, such as theoretical physics (e.g., quasicrystal modelling) and molecular biology (e.g., DNA sequences). I Connections with algebra are very deep — indeed, a natural environment of a
finite word is a free monoid. I Formally, under the operation of concatenation, the set A∗ of all finite words over
A is a free monoid with identity element ε (the empty word) and set of generators A.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15). I It lies on the border of discrete mathematics and theoretical computer science,
with applications not only in these two areas (e.g., transcendental number theory, pattern recognition, data compression), but also in other fields, such as theoretical physics (e.g., quasicrystal modelling) and molecular biology (e.g., DNA sequences). I Connections with algebra are very deep — indeed, a natural environment of a
finite word is a free monoid. I Formally, under the operation of concatenation, the set A∗ of all finite words over
A is a free monoid with identity element ε (the empty word) and set of generators A. I The set of non-empty finite words over A is the free semigroup A+ := A∗ \ {ε}.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15). I It lies on the border of discrete mathematics and theoretical computer science,
with applications not only in these two areas (e.g., transcendental number theory, pattern recognition, data compression), but also in other fields, such as theoretical physics (e.g., quasicrystal modelling) and molecular biology (e.g., DNA sequences). I Connections with algebra are very deep — indeed, a natural environment of a
finite word is a free monoid. I Formally, under the operation of concatenation, the set A∗ of all finite words over
A is a free monoid with identity element ε (the empty word) and set of generators A. I The set of non-empty finite words over A is the free semigroup A+ := A∗ \ {ε}. I It follows immediately that the mathematical research of words exploits two
features: discreteness and non-commutativity.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15). I It lies on the border of discrete mathematics and theoretical computer science,
with applications not only in these two areas (e.g., transcendental number theory, pattern recognition, data compression), but also in other fields, such as theoretical physics (e.g., quasicrystal modelling) and molecular biology (e.g., DNA sequences). I Connections with algebra are very deep — indeed, a natural environment of a
finite word is a free monoid. I Formally, under the operation of concatenation, the set A∗ of all finite words over
A is a free monoid with identity element ε (the empty word) and set of generators A. I The set of non-empty finite words over A is the free semigroup A+ := A∗ \ {ε}. I It follows immediately that the mathematical research of words exploits two
features: discreteness and non-commutativity. The latter aspect is what makes this field a very challenging one.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
Intro
Combinatorics on words I The study of combinatorial properties of words is known as combinatorics on
words (MSC: 68R15). I It lies on the border of discrete mathematics and theoretical computer science,
with applications not only in these two areas (e.g., transcendental number theory, pattern recognition, data compression), but also in other fields, such as theoretical physics (e.g., quasicrystal modelling) and molecular biology (e.g., DNA sequences). I Connections with algebra are very deep — indeed, a natural environment of a
finite word is a free monoid. I Formally, under the operation of concatenation, the set A∗ of all finite words over
A is a free monoid with identity element ε (the empty word) and set of generators A. I The set of non-empty finite words over A is the free semigroup A+ := A∗ \ {ε}. I It follows immediately that the mathematical research of words exploits two
features: discreteness and non-commutativity. The latter aspect is what makes this field a very challenging one. Many easily formulated problems are difficult to solve . . . Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
3
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square). Obtained by iterating the following substitution rule (or morphism) on the letter a: a 7→ b, b 7→ ca, c 7→ cba.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
I
I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square). Obtained by iterating the following substitution rule (or morphism) on the letter a: a 7→ b, b 7→ ca, c 7→ cba. That is: a→b
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
I
I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square). Obtained by iterating the following substitution rule (or morphism) on the letter a: a 7→ b, b 7→ ca, c 7→ cba. That is: a → b → ca
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
I
I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square). Obtained by iterating the following substitution rule (or morphism) on the letter a: a 7→ b, b 7→ ca, c 7→ cba. That is: a → b → ca → cbab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
I
I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square). Obtained by iterating the following substitution rule (or morphism) on the letter a: a 7→ b, b 7→ ca, c 7→ cba. That is: a → b → ca → cbab → cbacabca
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
I
I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square). Obtained by iterating the following substitution rule (or morphism) on the letter a: a 7→ b, b 7→ ca, c 7→ cba. That is: a → b → ca → cbab → cbacabca → cbacabcbabcacbab → · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History I There have been important contributions on “words” dating as far back as the
beginning of the last century. I Many of the earliest contributions were typically needed as tools to achieve some
other goals in mathematics, with the exception of combinatorial group theory which explicitly studies combinatorial problems on words as representing group elements. I Early 1900’s: First investigations by Axel Thue (1863–1922). I
I
I
Thue was the first to construct an infinite word over a 3-letter alphabet {a, b, c} containing no repetitions, i.e., avoiding the pattern XX (called a square). Obtained by iterating the following substitution rule (or morphism) on the letter a: a 7→ b, b 7→ ca, c 7→ cba. That is: a → b → ca → cbab → cbacabca → cbacabcbabcacbab → · · · gives (in the limit) the infinite word cbacabcbabcacbacabcacbabcbacabca · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
4
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
Amy Glen (Murdoch University)
and
XY XY X (called an overlap).
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube) I
and
XY XY X (called an overlap).
Obtained by iterating the following substitution µ on the letter a: µ : a 7→ ab, b 7→ ba.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
and
XY XY X (called an overlap).
I
Obtained by iterating the following substitution µ on the letter a:
I
That is:
µ : a 7→ ab, b 7→ ba. lim µn (a) = abbabaabbaababbabaababbaabbabaab · · ·
n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
and
XY XY X (called an overlap).
I
Obtained by iterating the following substitution µ on the letter a:
I
That is:
µ : a 7→ ab, b 7→ ba. lim µn (a) = abbabaabbaababbabaababbaabbabaab · · ·
n→∞ I
Now called the Thue-Morse word as it was rediscovered by Morse in 1921 (in the context of symbolic dynamics).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
and
XY XY X (called an overlap).
I
Obtained by iterating the following substitution µ on the letter a:
I
That is:
µ : a 7→ ab, b 7→ ba. lim µn (a) = abbabaabbaababbabaababbaabbabaab · · ·
n→∞ I
Now called the Thue-Morse word as it was rediscovered by Morse in 1921 (in the context of symbolic dynamics).
After Thue . . .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
and
XY XY X (called an overlap).
I
Obtained by iterating the following substitution µ on the letter a:
I
That is:
µ : a 7→ ab, b 7→ ba. lim µn (a) = abbabaabbaababbabaababbaabbabaab · · ·
n→∞ I
Now called the Thue-Morse word as it was rediscovered by Morse in 1921 (in the context of symbolic dynamics).
After Thue . . . I 1938: Marston Morse & Gustav Hedlund initiated the formal development of
symbolic dynamics.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
and
XY XY X (called an overlap).
I
Obtained by iterating the following substitution µ on the letter a:
I
That is:
µ : a 7→ ab, b 7→ ba. lim µn (a) = abbabaabbaababbabaababbaabbabaab · · ·
n→∞ I
Now called the Thue-Morse word as it was rediscovered by Morse in 1921 (in the context of symbolic dynamics).
After Thue . . . I 1938: Marston Morse & Gustav Hedlund initiated the formal development of
symbolic dynamics. This work marked the beginning of the formal study of words.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
and
XY XY X (called an overlap).
I
Obtained by iterating the following substitution µ on the letter a:
I
That is:
µ : a 7→ ab, b 7→ ba. lim µn (a) = abbabaabbaababbabaababbaabbabaab · · ·
n→∞ I
Now called the Thue-Morse word as it was rediscovered by Morse in 1921 (in the context of symbolic dynamics).
After Thue . . . I 1938: Marston Morse & Gustav Hedlund initiated the formal development of
symbolic dynamics. This work marked the beginning of the formal study of words. I 1960’s: A systematic study of words initiated by M.P. Schützenberger.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: History . . . I Thue (1912) also constructed an infinite word over {a, b} avoiding factors of the
form XXX = X 3 (called a cube)
and
XY XY X (called an overlap).
I
Obtained by iterating the following substitution µ on the letter a:
I
That is:
µ : a 7→ ab, b 7→ ba. lim µn (a) = abbabaabbaababbabaababbaabbabaab · · ·
n→∞ I
Now called the Thue-Morse word as it was rediscovered by Morse in 1921 (in the context of symbolic dynamics).
After Thue . . . I 1938: Marston Morse & Gustav Hedlund initiated the formal development of
symbolic dynamics. This work marked the beginning of the formal study of words. I 1960’s: A systematic study of words initiated by M.P. Schützenberger. I Recent developments in combinatorics on words have culminated in the publication
of three books by a collection of authors, under the pseudonym of M. Lothaire . . . Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
5
Background
History
Combinatorics on words: Series of Books Lothaire Books 1
“Combinatorics on words”, 1983 (reprinted 1997)
2
“Algebraic combinatorics on words”, 2002
3
“Applied combinatorics on words”, 2005
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
6
Background
History
Combinatorics on words: Series of Books Lothaire Books 1
“Combinatorics on words”, 1983 (reprinted 1997)
2
“Algebraic combinatorics on words”, 2002
3
“Applied combinatorics on words”, 2005
In the introduction to the first edition, Roger Lyndon stated “This is the first book devoted to broad study of the combinatorics of words, that is to say, of sequences of symbols called letters. This subject is in fact very ancient and has cropped up repeatedly in a wide variety of subjects.”
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
6
Background
History
Combinatorics on words: Series of Books Lothaire Books 1
“Combinatorics on words”, 1983 (reprinted 1997)
2
“Algebraic combinatorics on words”, 2002
3
“Applied combinatorics on words”, 2005
In the introduction to the first edition, Roger Lyndon stated “This is the first book devoted to broad study of the combinatorics of words, that is to say, of sequences of symbols called letters. This subject is in fact very ancient and has cropped up repeatedly in a wide variety of subjects.” Combinatorics on words has now become a very active and challenging field in its own right.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
6
Background
Applications
Combinatorics on words: Connections
Number Theory Probability Theory
Discrete Dynamical Systems
Discrete Geometry
Combinatorics on Words
Theoretical Computer Science Algorithmics Automata Theory Computability Codes
Topology Theoretical Physics
Biology
Logic
DNA sequencing, Patterns
algebra Free Groups, Semigroups Matrices Representations Burnside Problems
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
7
Background
I
Complexity
Whilst the study of avoidability and unavoidability of patterns in words is popular, some of the most commonly studied words are those which satisfy one or more strong regularity properties.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
8
Background
Complexity
I
Whilst the study of avoidability and unavoidability of patterns in words is popular, some of the most commonly studied words are those which satisfy one or more strong regularity properties.
I
For instance, words containing many repetitions, periodicities, or palindromes.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
8
Background
Complexity
I
Whilst the study of avoidability and unavoidability of patterns in words is popular, some of the most commonly studied words are those which satisfy one or more strong regularity properties.
I
For instance, words containing many repetitions, periodicities, or palindromes.
I
The extent to which a word exhibits strong regularity properties is generally inversely proportional to its “complexity”.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
8
Background
Complexity
I
Whilst the study of avoidability and unavoidability of patterns in words is popular, some of the most commonly studied words are those which satisfy one or more strong regularity properties.
I
For instance, words containing many repetitions, periodicities, or palindromes.
I
The extent to which a word exhibits strong regularity properties is generally inversely proportional to its “complexity”.
I
Basic measure of complexity: number of distinct factors of each length occurring in a given word.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
8
Background
Complexity
I
Whilst the study of avoidability and unavoidability of patterns in words is popular, some of the most commonly studied words are those which satisfy one or more strong regularity properties.
I
For instance, words containing many repetitions, periodicities, or palindromes.
I
The extent to which a word exhibits strong regularity properties is generally inversely proportional to its “complexity”.
I
Basic measure of complexity: number of distinct factors of each length occurring in a given word. A factor of a given word w is a finite string of contiguous letters occurring in w.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
8
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2 Factors of length 2: {aa, ab, ba} −→ Cw (2) = 3
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2 Factors of length 2: {aa, ab, ba} −→ Cw (2) = 3 Factors of length 3: {aab, aba, baa, bab} −→ Cw (3) = 4
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2 Factors of length 2: {aa, ab, ba} −→ Cw (2) = 3 Factors of length 3: {aab, aba, baa, bab} −→ Cw (3) = 4 Factors of length 4: {aaba, abaa, baab, abab} −→ Cw (4) = 4
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2 Factors of length 2: {aa, ab, ba} −→ Cw (2) = 3 Factors of length 3: {aab, aba, baa, bab} −→ Cw (3) = 4 Factors of length 4: {aaba, abaa, baab, abab} −→ Cw (4) = 4 Factors of length 5: {aabaa, abaab, baaba, aabab} −→ Cw (4) = 4
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2 Factors of length 2: {aa, ab, ba} −→ Cw (2) = 3 Factors of length 3: {aab, aba, baa, bab} −→ Cw (3) = 4 Factors of length 4: {aaba, abaa, baab, abab} −→ Cw (4) = 4 Factors of length 5: {aabaa, abaab, baaba, aabab} −→ Cw (4) = 4 Factors of length 6: {aabaab, abaaba, baabab} −→ Cw (4) = 3
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2 Factors of length 2: {aa, ab, ba} −→ Cw (2) = 3 Factors of length 3: {aab, aba, baa, bab} −→ Cw (3) = 4 Factors of length 4: {aaba, abaa, baab, abab} −→ Cw (4) = 4 Factors of length 5: {aabaa, abaab, baaba, aabab} −→ Cw (4) = 4 Factors of length 6: {aabaab, abaaba, baabab} −→ Cw (4) = 3 Factors of length 7: {aabaaba, abaabab} −→ Cw (4) = 2
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
Factor Complexity The factor complexity function of a finite or infinite word w, denoted by Cw (n), counts the number of distinct factors of w of each length n.
Example w = aabaabab Factors of length 1: {a, b} −→ Cw (1) = 2 Factors of length 2: {aa, ab, ba} −→ Cw (2) = 3 Factors of length 3: {aab, aba, baa, bab} −→ Cw (3) = 4 Factors of length 4: {aaba, abaa, baab, abab} −→ Cw (4) = 4 Factors of length 5: {aabaa, abaab, baaba, aabab} −→ Cw (4) = 4 Factors of length 6: {aabaab, abaaba, baabab} −→ Cw (4) = 3 Factors of length 7: {aabaaba, abaabab} −→ Cw (4) = 2 Factors of length 8: {aabaabab} −→ Cw (4) = 1
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
9
Background
Complexity
The graph of the complexity Cw (n) of w = aabaabab as a function of n (for 0 ≤ n ≤ |w|) is that of a regular trapezoid:
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
10
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following. I
A finite balanced word over {a, b}
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following. I
A finite balanced word over {a, b} — for any two factors u, v of w of the same length the number of a’s in each differs by at most 1, i.e., ||u|a − |v|a | ≤ 1 (or equivalently, ||u|b − |v|b | ≤ 1).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following. I
A finite balanced word over {a, b} — for any two factors u, v of w of the same length the number of a’s in each differs by at most 1, i.e., ||u|a − |v|a | ≤ 1 (or equivalently, ||u|b − |v|b | ≤ 1).
I
A Lyndon word
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following. I
A finite balanced word over {a, b} — for any two factors u, v of w of the same length the number of a’s in each differs by at most 1, i.e., ||u|a − |v|a | ≤ 1 (or equivalently, ||u|b − |v|b | ≤ 1).
I
A Lyndon word — a primitive word that is lexicographically less than all of its conjugates (circular shifts) for the order a < b.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following. I
A finite balanced word over {a, b} — for any two factors u, v of w of the same length the number of a’s in each differs by at most 1, i.e., ||u|a − |v|a | ≤ 1 (or equivalently, ||u|b − |v|b | ≤ 1).
I
A Lyndon word — a primitive word that is lexicographically less than all of its conjugates (circular shifts) for the order a < b.
I
A palindromically rich word
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following. I
A finite balanced word over {a, b} — for any two factors u, v of w of the same length the number of a’s in each differs by at most 1, i.e., ||u|a − |v|a | ≤ 1 (or equivalently, ||u|b − |v|b | ≤ 1).
I
A Lyndon word — a primitive word that is lexicographically less than all of its conjugates (circular shifts) for the order a < b.
I
A palindromically rich word — a word that contains the maximum possible number of distinct palindromic factors (|w| + 1 = 9, including ε).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
The “trapezoidal word” w = aabaabab is an example of each of the following. I
A finite balanced word over {a, b} — for any two factors u, v of w of the same length the number of a’s in each differs by at most 1, i.e., ||u|a − |v|a | ≤ 1 (or equivalently, ||u|b − |v|b | ≤ 1).
I
A Lyndon word — a primitive word that is lexicographically less than all of its conjugates (circular shifts) for the order a < b.
I
A palindromically rich word — a word that contains the maximum possible number of distinct palindromic factors (|w| + 1 = 9, including ε).
Theorem (de Luca 1997) A finite word over {a, b} is balanced if and only if it is a factor of a Sturmian word over {a, b}.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
11
Background
Complexity
Complexity & Periodicity Theorem (Morse-Hedlund 1940) An infinite word w is eventually periodic if and only if Cw (n) ≤ n for some n ∈ N+ .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
12
Background
Complexity
Complexity & Periodicity Theorem (Morse-Hedlund 1940) An infinite word w is eventually periodic if and only if Cw (n) ≤ n for some n ∈ N+ . That is: w is aperiodic ⇔ Cw (n) ≥ n + 1 for all n ∈ N.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
12
Background
Complexity
Complexity & Periodicity Theorem (Morse-Hedlund 1940) An infinite word w is eventually periodic if and only if Cw (n) ≤ n for some n ∈ N+ . That is: w is aperiodic ⇔ Cw (n) ≥ n + 1 for all n ∈ N. I
An infinite word w for which Cw (n) = n + 1 for all n is called Sturmian.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
12
Background
Complexity
Complexity & Periodicity Theorem (Morse-Hedlund 1940) An infinite word w is eventually periodic if and only if Cw (n) ≤ n for some n ∈ N+ . That is: w is aperiodic ⇔ Cw (n) ≥ n + 1 for all n ∈ N. I
An infinite word w for which Cw (n) = n + 1 for all n is called Sturmian.
I
Sturmian words are the aperiodic infinite words of minimal complexity.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
12
Background
Complexity
Complexity & Periodicity Theorem (Morse-Hedlund 1940) An infinite word w is eventually periodic if and only if Cw (n) ≤ n for some n ∈ N+ . That is: w is aperiodic ⇔ Cw (n) ≥ n + 1 for all n ∈ N. I
An infinite word w for which Cw (n) = n + 1 for all n is called Sturmian.
I
Sturmian words are the aperiodic infinite words of minimal complexity.
I
Clearly, Sturmian words are binary since they have two distinct factors of length 1.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
12
Background
Complexity
Complexity & Periodicity Theorem (Morse-Hedlund 1940) An infinite word w is eventually periodic if and only if Cw (n) ≤ n for some n ∈ N+ . That is: w is aperiodic ⇔ Cw (n) ≥ n + 1 for all n ∈ N. I
An infinite word w for which Cw (n) = n + 1 for all n is called Sturmian.
I
Sturmian words are the aperiodic infinite words of minimal complexity.
I
Clearly, Sturmian words are binary since they have two distinct factors of length 1.
I
Their low complexity accounts for many interesting features, as it induces certain regularities in such words without, however, making them periodic.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
12
Background
Complexity
Complexity & Periodicity Theorem (Morse-Hedlund 1940) An infinite word w is eventually periodic if and only if Cw (n) ≤ n for some n ∈ N+ . That is: w is aperiodic ⇔ Cw (n) ≥ n + 1 for all n ∈ N. I
An infinite word w for which Cw (n) = n + 1 for all n is called Sturmian.
I
Sturmian words are the aperiodic infinite words of minimal complexity.
I
Clearly, Sturmian words are binary since they have two distinct factors of length 1.
I
Their low complexity accounts for many interesting features, as it induces certain regularities in such words without, however, making them periodic.
I
They have numerous equivalent definitions and characterisations . . .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
12
Sturmian words
Construction
Geometrical construction of Sturmian words Sturmian words are also known as cutting sequences, obtained by coding the sequence of ‘cuts’ in an integer lattice made by a line y = βx + γ with irrational β > 0, γ ∈ R, in the positive quadrant of R2 .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
13
Sturmian words
Construction
Geometrical construction of Sturmian words Sturmian words are also known as cutting sequences, obtained by coding the sequence of ‘cuts’ in an integer lattice made by a line y = βx + γ with irrational β > 0, γ ∈ R, in the positive quadrant of R2 .
Example The well-known infinite Fibonacci word over the alphabet {a, b}: f = abaababaabaababaaba · · · √
is the Sturmian word obtained from the line with slope β = conjugate: 1/φ) and intercept γ = 0.
5−1 2
(golden ratio
b ba b
a
a
a b
a
a
(0, 0) Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
13
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f =a
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = ab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = aba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaa
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaaba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaabab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaababa
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaababaa
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaababaab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
The infinite Fibonacci word can also be obtained by coding the steps in the path along √ x in the positive quadrant of R2 , the integer lattice directly below the line y = 5−1 2 starting at the point (1, 0).
f = abaababaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
14
Sturmian words
Construction
Morse & Hedlund Characterisation An infinite word s over {a, b} is Sturmian if and only if there exists an irrational α ∈ (0, 1), and a real number ρ, such that s is one of the following two infinite words: sα,ρ , s0α,ρ : N −→ {a, b} defined by ( a sα,ρ (n) = b
if b(n + 1)α + ρc − bnα + ρc = 0, otherwise; (n ≥ 0)
( a s0α,ρ (n) = b
Amy Glen (Murdoch University)
if d(n + 1)α + ρe − dnα + ρe = 0, otherwise.
An introduction to combinatorics on words
December, 2016
15
Sturmian words
Construction
Morse & Hedlund Characterisation An infinite word s over {a, b} is Sturmian if and only if there exists an irrational α ∈ (0, 1), and a real number ρ, such that s is one of the following two infinite words: sα,ρ , s0α,ρ : N −→ {a, b} defined by ( a sα,ρ (n) = b
if b(n + 1)α + ρc − bnα + ρc = 0, otherwise; (n ≥ 0)
( a s0α,ρ (n) = b I
if d(n + 1)α + ρe − dnα + ρe = 0, otherwise.
α is called the slope of s
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
15
Sturmian words
Construction
Morse & Hedlund Characterisation An infinite word s over {a, b} is Sturmian if and only if there exists an irrational α ∈ (0, 1), and a real number ρ, such that s is one of the following two infinite words: sα,ρ , s0α,ρ : N −→ {a, b} defined by ( a sα,ρ (n) = b
if b(n + 1)α + ρc − bnα + ρc = 0, otherwise; (n ≥ 0)
( a s0α,ρ (n) = b
if d(n + 1)α + ρe − dnα + ρe = 0, otherwise.
I
α is called the slope of s
I
ρ is called the intercept of s
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
15
Sturmian words
Construction
Morse & Hedlund Characterisation An infinite word s over {a, b} is Sturmian if and only if there exists an irrational α ∈ (0, 1), and a real number ρ, such that s is one of the following two infinite words: sα,ρ , s0α,ρ : N −→ {a, b} defined by ( a sα,ρ (n) = b
if b(n + 1)α + ρc − bnα + ρc = 0, otherwise; (n ≥ 0)
( a s0α,ρ (n) = b
if d(n + 1)α + ρe − dnα + ρe = 0, otherwise.
I
α is called the slope of s
I
ρ is called the intercept of s
I
If ρ = 0, we have sα,0 = acα
and s0α,0 = bcα
where cα is called the characteristic Sturmian word of slope α. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
15
Sturmian words
Construction
The cutting sequence obtained from the line y = βx + γ with irrational β > 0, γ ∈ R is precisely the Sturmian word sα,ρ with α = β/(1 + β) and ρ = γ/(1 + β).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
16
Sturmian words
Construction
The cutting sequence obtained from the line y = βx + γ with irrational β > 0, γ ∈ R is precisely the Sturmian word sα,ρ with α = β/(1 + β) and ρ = γ/(1 + β). In particular, the cutting sequence obtained from the line y = βx is the characteristic Sturmian word cα with α = β/(1 + β)
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
16
Sturmian words
Construction
The cutting sequence obtained from the line y = βx + γ with irrational β > 0, γ ∈ R is precisely the Sturmian word sα,ρ with α = β/(1 + β) and ρ = γ/(1 + β). In particular, the cutting sequence obtained from the line y = βx is the characteristic Sturmian word cα with α = β/(1 + β)
Example The Fibonacci word f =√abaababaabaababaaba · · · is the characteristic Sturmian word of slope α = (3 − 5)/2.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
16
Sturmian words
Construction
The cutting sequence obtained from the line y = βx + γ with irrational β > 0, γ ∈ R is precisely the Sturmian word sα,ρ with α = β/(1 + β) and ρ = γ/(1 + β). In particular, the cutting sequence obtained from the line y = βx is the characteristic Sturmian word cα with α = β/(1 + β)
Example The Fibonacci word f =√abaababaabaababaaba · · · is the characteristic Sturmian word of slope α = (3 − 5)/2. Sturmian words of the same slope have the same set of factors, so when studying the factors of Sturmian words, it suffices to consider only the characteristic ones. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
16
Sturmian words
Construction
Sturmian words as the limits of sequences of finite words I
The Fibonacci word can also be constructed as the limit of an infinite sequence of so-called finite Fibonacci words {fn }n≥1 , defined by: f−1 = b,
Amy Glen (Murdoch University)
f0 = a,
fn = fn−1 fn−2
An introduction to combinatorics on words
for
n ≥ 1.
December, 2016
17
Sturmian words
Construction
Sturmian words as the limits of sequences of finite words I
The Fibonacci word can also be constructed as the limit of an infinite sequence of so-called finite Fibonacci words {fn }n≥1 , defined by: f−1 = b,
I
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
That is, f1 = ab, f2 = aba, f3 = abaab, f4 = abaababa, f5 = abaababaabaab, etc.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
17
Sturmian words
Construction
Sturmian words as the limits of sequences of finite words I
The Fibonacci word can also be constructed as the limit of an infinite sequence of so-called finite Fibonacci words {fn }n≥1 , defined by: f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
I
That is, f1 = ab, f2 = aba, f3 = abaab, f4 = abaababa, f5 = abaababaabaab, etc.
I
For all n ≥ 0, fn is a prefix of fn+1 , and we have
n ≥ 1.
f = lim fn = abaababaabaab · · · n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
17
Sturmian words
Construction
Sturmian words as the limits of sequences of finite words I
The Fibonacci word can also be constructed as the limit of an infinite sequence of so-called finite Fibonacci words {fn }n≥1 , defined by: f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
I
That is, f1 = ab, f2 = aba, f3 = abaab, f4 = abaababa, f5 = abaababaabaab, etc.
I
For all n ≥ 0, fn is a prefix of fn+1 , and we have
n ≥ 1.
f = lim fn = abaababaabaab · · · n→∞
I
Note that the length |fn | of the n-th finite Fibonacci word fn is the n-th Fibonacci number Fn , defined by F−1 = 1,
Amy Glen (Murdoch University)
F0 = 1,
Fn = Fn−1 + Fn−2
An introduction to combinatorics on words
for
n ≥ 1.
December, 2016
17
Sturmian words
Construction
More generally, any characteristic Sturmian word can be constructed as the limit of an infinite sequence of finite words.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
18
Sturmian words
Construction
More generally, any characteristic Sturmian word can be constructed as the limit of an infinite sequence of finite words. I Let α ∈ (0, 1) be an irrational number with simple continued fraction expansion
1
α = [0; 1 + d1 , d2 , d3 , . . .] =
1
(1 + d1 ) + d2 +
1 d3 + · · ·
where d1 ≥ 0 and all other di > 0.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
18
Sturmian words
Construction
More generally, any characteristic Sturmian word can be constructed as the limit of an infinite sequence of finite words. I Let α ∈ (0, 1) be an irrational number with simple continued fraction expansion
1
α = [0; 1 + d1 , d2 , d3 , . . .] =
1
(1 + d1 ) + d2 +
1 d3 + · · ·
where d1 ≥ 0 and all other di > 0. I To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence {sn }n≥−1 of
words defined by n s−1 = b, s0 = a, sn = sdn−1 sn−2
Amy Glen (Murdoch University)
An introduction to combinatorics on words
for
n ≥ 1.
December, 2016
18
Sturmian words
Construction
More generally, any characteristic Sturmian word can be constructed as the limit of an infinite sequence of finite words. I Let α ∈ (0, 1) be an irrational number with simple continued fraction expansion
1
α = [0; 1 + d1 , d2 , d3 , . . .] =
1
(1 + d1 ) + d2 +
1 d3 + · · ·
where d1 ≥ 0 and all other di > 0. I To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence {sn }n≥−1 of
words defined by n s−1 = b, s0 = a, sn = sdn−1 sn−2
for
n ≥ 1.
For all n ≥ 0, sn is a prefix of sn+1 , which gives obvious meaning to lim sn as an n→∞
infinite word.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
18
Sturmian words
Construction
More generally, any characteristic Sturmian word can be constructed as the limit of an infinite sequence of finite words. I Let α ∈ (0, 1) be an irrational number with simple continued fraction expansion
1
α = [0; 1 + d1 , d2 , d3 , . . .] =
1
(1 + d1 ) + d2 +
1 d3 + · · ·
where d1 ≥ 0 and all other di > 0. I To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence {sn }n≥−1 of
words defined by n s−1 = b, s0 = a, sn = sdn−1 sn−2
for
n ≥ 1.
For all n ≥ 0, sn is a prefix of sn+1 , which gives obvious meaning to lim sn as an n→∞
infinite word. In fact:
Theorem (Fraenkel-Mushkin-Tassa 1978, Brown 1993) For all n ≥ 0, sn is a prefix of cα , and we have cα = lim sn n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
18
Sturmian words
Construction
Example √ The characteristic Sturmian word of slope α = ( 13 − 1)/6 = [0; 2, 3, 3, 3, 3, . . .] is the limit of the standard words {sn }n≥1 given by: s1
= s10 s−1
= ab
s2
= s31 s0
= |{z} ab |{z} ab |{z} ab a s1
s3
= s32 s1
s1
s1
ab = abababa | {z } abababa | {z } |{z} | {z } abababa s2
s2
s2
s1
.. .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
19
Sturmian words
Construction
Example √ The characteristic Sturmian word of slope α = ( 13 − 1)/6 = [0; 2, 3, 3, 3, 3, . . .] is the limit of the standard words {sn }n≥1 given by: s1
= s10 s−1
= ab
s2
= s31 s0
= |{z} ab |{z} ab |{z} ab a s1
s3
= s32 s1
s1
s1
ab = abababa | {z } abababa | {z } |{z} | {z } abababa s2
s2
s2
s1
.. . c √13−1 = lim sn = abababaabababaabababaabababa · · · 6
Amy Glen (Murdoch University)
n→∞
An introduction to combinatorics on words
December, 2016
19
Sturmian words
Construction
Back to the Fibonacci word
Let’s take a closer look at some of the finite Fibonacci words {fn }n≥1 of which the infinite Fibonacci word is the limit: f = lim fn . n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
20
Sturmian words
Construction
Back to the Fibonacci word
Let’s take a closer look at some of the finite Fibonacci words {fn }n≥1 of which the infinite Fibonacci word is the limit: f = lim fn . n→∞
f1 = ab,
f2 = aba,
f3 = abaab,
f4 = abaababa,
f5 = abaababaabaab
Do you notice any structural properties that hold for all these words?
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
20
Sturmian words
Construction
Back to the Fibonacci word
Let’s take a closer look at some of the finite Fibonacci words {fn }n≥1 of which the infinite Fibonacci word is the limit: f = lim fn . n→∞
f1 = ab,
f2 = aba,
f3 = abaab,
f4 = abaababa,
f5 = abaababaabaab
How about now?
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
20
Sturmian words
Construction
Back to the Fibonacci word
Let’s take a closer look at some of the finite Fibonacci words {fn }n≥1 of which the infinite Fibonacci word is the limit: f = lim fn . n→∞
f1 = ab,
f2 = aba,
f3 = abaab,
f4 = abaababa,
f5 = abaababaabaab
All such words take the form P xy where xy ∈ {ab, ba} and P is a palindrome.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
20
Sturmian words
Construction
Theorem (de Luca-Mignosi 1994) Let cα be the characteristic Sturmian word of slope α = [0; 1 + d1 , d2 , d3 , . . .] with cα = lim sn . n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
21
Sturmian words
Construction
Theorem (de Luca-Mignosi 1994) Let cα be the characteristic Sturmian word of slope α = [0; 1 + d1 , d2 , d3 , . . .] with cα = lim sn . n→∞
For all n ≥ 1, there exist uniquely determined palindromes un , vn , pn such that ( pn ab if n is odd, sn = un vn = pn ba if n is even, where |un | = |sn−1 | − 2 and |vn | = |sn | − |sn−1 | + 2.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
21
Sturmian words
Construction
Theorem (de Luca-Mignosi 1994) Let cα be the characteristic Sturmian word of slope α = [0; 1 + d1 , d2 , d3 , . . .] with cα = lim sn . n→∞
For all n ≥ 1, there exist uniquely determined palindromes un , vn , pn such that ( pn ab if n is odd, sn = un vn = pn ba if n is even, where |un | = |sn−1 | − 2 and |vn | = |sn | − |sn−1 | + 2. I
In particular, a characteristic Sturmian word begins with infinitely many palindromes pn , n ≥ 1.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
21
Sturmian words
Construction
Theorem (de Luca-Mignosi 1994) Let cα be the characteristic Sturmian word of slope α = [0; 1 + d1 , d2 , d3 , . . .] with cα = lim sn . n→∞
For all n ≥ 1, there exist uniquely determined palindromes un , vn , pn such that ( pn ab if n is odd, sn = un vn = pn ba if n is even, where |un | = |sn−1 | − 2 and |vn | = |sn | − |sn−1 | + 2. I
In particular, a characteristic Sturmian word begins with infinitely many palindromes pn , n ≥ 1.
I
What form do these palindromes take?
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
21
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I
(glen)+ =
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I
(glen)+ = glenelg
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
(glen)+ = glenelg (race)+ =
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
(glen)+ = glenelg (race)+ = race car
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word)
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) =
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = r
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = ra
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rar
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarc
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrar
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrare
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) =
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) = a
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) = ab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) = aba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) = abaa
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) = abaaba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) = abaabab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Construction
Each pn is P al(v) for some word v ∈ {a, b}∗ . I
P al is the iterated palindromic closure operator [Justin 2005], defined as follows.
I
For a given word w, let w+ denote the unique shortest palindrome beginning with w, called the (right-)palindromic closure of w.
Examples I I
I
(glen)+ = glenelg (race)+ = race car
We define P al(ε) = ε (empty word), and for any word w and letter x, P al(wx) = (P al(w)x)+ .
Examples I
P al(race) = rarcrarerarcrar
I
P al(abab) = abaababaaba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
22
Sturmian words
Notice that
Amy Glen (Murdoch University)
Construction
f1 = ab = P al(ε)ab
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes?
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · ,
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f . ∆ = (ab)(ab)(ab) · · · −→ f = P al(∆) = a Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f . ∆ = (ab)(ab)(ab) · · · −→ f = P al(∆) = ab Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f . ∆ = (ab)(ab)(ab) · · · −→ f = P al(∆) = aba Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f . ∆ = (ab)(ab)(ab) · · · −→ f = P al(∆) = abaa Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f . ∆ = (ab)(ab)(ab) · · · −→ f = P al(∆) = abaaba Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f . ∆ = (ab)(ab)(ab) · · · −→ f = P al(∆) = abaabab Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Notice that
Construction
f1 = ab = P al(ε)ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. .
Can you guess what form f6 takes? Answer: f6 = P al(ababa)ba Extending to infinity, the infinite Fibonacci word f = lim fn = abaababaabaababaababa · · · n→∞
can alternatively be obtained by applying P al to ∆ := (ab)∞ = abababababab · · · , called the directive word of f . ∆ = (ab)(ab)(ab) · · · −→ f = P al(∆) = abaababaaba · · · Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
23
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
Amy Glen (Murdoch University)
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
Amy Glen (Murdoch University)
f0 = a,
fn = fn−1 fn−2
for
An introduction to combinatorics on words
n ≥ 1.
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a That is,
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a That is, f1 = ϕ(a) = ab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a That is, f1 = ϕ(a) = ab,
Amy Glen (Murdoch University)
f2 = ϕ2 (a) = ϕ(ab) = aba
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a That is, f1 = ϕ(a) = ab,
Amy Glen (Murdoch University)
f2 = ϕ2 (a) = ϕ(ab) = aba,
f3 = ϕ3 (a) = ϕ(aba) = abaab, . . .
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a That is, f1 = ϕ(a) = ab, f2 = ϕ2 (a) = ϕ(ab) = aba, and we have f = lim ϕn (a).
f3 = ϕ3 (a) = ϕ(aba) = abaab, . . .
n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a That is, f1 = ϕ(a) = ab, f2 = ϕ2 (a) = ϕ(ab) = aba, and we have f = lim ϕn (a).
f3 = ϕ3 (a) = ϕ(aba) = abaab, . . .
n→∞
Definition 3 f = P al((ab)∞ ) = P al(abababab · · · )
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
Recap: Equivalent definitions of the infinite Fibonacci word f = abaababaabaababaababa · · ·
Definition 1 f is the characteristic Sturmian word cα of slope α = (3 −
√
5)/2 = [0; 2, 1, 1, 1, . . . ].
Definition 2 f = limn→∞ fn where fn is the n-th finite Fibonacci word defined by f−1 = b,
f0 = a,
fn = fn−1 fn−2
for
n ≥ 1.
Note that, for all n ≥ 1, fn is the n-th iterate, starting with the letter a, of the so-called Fibonacci morphism ϕ on {a, b} defined by: a 7→ ab ϕ: b 7→ a That is, f1 = ϕ(a) = ab, f2 = ϕ2 (a) = ϕ(ab) = aba, and we have f = lim ϕn (a).
f3 = ϕ3 (a) = ϕ(aba) = abaab, . . .
n→∞
Definition 3 f = P al((ab)∞ ) = P al(abababab · · · ) Notice that the exponents of a’s and b’s in the √ directive word ∆ = ababababa · · · are all 1 — cf. the continued fraction expansion of (3 − 5)/2. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
24
Sturmian words
Construction
More generally:
Theorem (Fraenkel-Muskin-Tassa 1978, Brown 1993) If α ∈ (0, 1) is an irrational number with simple continued fraction expansion [0; 1 + d1 , d2 , d3 , d4 , . . .], then cα = P al(ad1 bd2 ad3 bd4 · · · )
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
25
Sturmian words
Construction
More generally:
Theorem (Fraenkel-Muskin-Tassa 1978, Brown 1993) If α ∈ (0, 1) is an irrational number with simple continued fraction expansion [0; 1 + d1 , d2 , d3 , d4 , . . .], then cα = P al(ad1 bd2 ad3 bd4 · · · )
Theorem (de Luca 1997) An infinite word s over {a, b} is a characteristic Sturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over {a, b} (not of the form ua∞ or ub∞ ) such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
25
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word:
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = a
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = ab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = aba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abac
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacaba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaa
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaabacaba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaabacabab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaabacababacabaabacaba
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaabacababacabaabacabac
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaabacababacabaabacabacabaabaca · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaabacababacabaabacabacabaabaca · · · Also, t = lim tn where {tn }n≥0 is the sequence of finite Tribonacci words defined by: n→∞
t−1 = c,
t0 = a,
Amy Glen (Murdoch University)
t1 = ab,
tn = tn−1 tn−2 tn−3
An introduction to combinatorics on words
for
n ≥ 2.
December, 2016
26
Sturmian words
Generalisations
A natural generalisation {a, b} −→ A (finite alphabet) gives standard episturmian words . . .
Theorem (Droubay-Justin-Pirillo 2001) An infinite word s over A is a standard episturmian word if and only if there exists an infinite word ∆ = x1 x2 x3 · · · over A such that s = lim P al(x1 x2 · · · xn ) = P al(∆). n→∞
Example: ∆ = (abc)∞ directs the so-called Tribonacci word: t = P al(∆) = abacabaabacababacabaabacabacabaabaca · · · Also, t = lim tn where {tn }n≥0 is the sequence of finite Tribonacci words defined by: n→∞
t−1 = c,
t0 = a,
t1 = ab,
tn = tn−1 tn−2 tn−3
for
n ≥ 2.
We have t2 = abac, t3 = abacaba, t4 = abacabaabac, and so on . . . , where tn is the n-th iterate, starting with the letter a, of the so-called Tribonacci morphism ψ on {a, b, c} defined by a 7→ ab ψ : b 7→ ac c 7→ a Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
26
Sturmian words
Generalisations
A further generalisation: Palindromically rich words I We have seen that characteristic Sturmian words and standard episturmian words
begin with arbitrarily long palindromes.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
27
Sturmian words
Generalisations
A further generalisation: Palindromically rich words I We have seen that characteristic Sturmian words and standard episturmian words
begin with arbitrarily long palindromes. I In fact, all Sturmian and episturmian words are “rich” in palindromes in the sense
that all of their factors contain the maximum possible number of palindromic factors.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
27
Sturmian words
Generalisations
A further generalisation: Palindromically rich words I We have seen that characteristic Sturmian words and standard episturmian words
begin with arbitrarily long palindromes. I In fact, all Sturmian and episturmian words are “rich” in palindromes in the sense
that all of their factors contain the maximum possible number of palindromic factors.
Theorem (Droubay-Justin-Pirillo 2001) Any finite word w of length |w| contains at most |w| + 1 distinct palindromes (including the empty word ε).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
27
Sturmian words
Generalisations
A further generalisation: Palindromically rich words I We have seen that characteristic Sturmian words and standard episturmian words
begin with arbitrarily long palindromes. I In fact, all Sturmian and episturmian words are “rich” in palindromes in the sense
that all of their factors contain the maximum possible number of palindromic factors.
Theorem (Droubay-Justin-Pirillo 2001) Any finite word w of length |w| contains at most |w| + 1 distinct palindromes (including the empty word ε). I Inspired by this result, we initiated a unified study of finite and infinite words that
are characterised by containing the maximal number of distinct palindromes.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
27
Sturmian words
Generalisations
A further generalisation: Palindromically rich words I We have seen that characteristic Sturmian words and standard episturmian words
begin with arbitrarily long palindromes. I In fact, all Sturmian and episturmian words are “rich” in palindromes in the sense
that all of their factors contain the maximum possible number of palindromic factors.
Theorem (Droubay-Justin-Pirillo 2001) Any finite word w of length |w| contains at most |w| + 1 distinct palindromes (including the empty word ε). I Inspired by this result, we initiated a unified study of finite and infinite words that
are characterised by containing the maximal number of distinct palindromes. I Such words are called rich words in view of their palindromic richness.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
27
Sturmian words
Generalisations
A further generalisation: Palindromically rich words I We have seen that characteristic Sturmian words and standard episturmian words
begin with arbitrarily long palindromes. I In fact, all Sturmian and episturmian words are “rich” in palindromes in the sense
that all of their factors contain the maximum possible number of palindromic factors.
Theorem (Droubay-Justin-Pirillo 2001) Any finite word w of length |w| contains at most |w| + 1 distinct palindromes (including the empty word ε). I Inspired by this result, we initiated a unified study of finite and infinite words that
are characterised by containing the maximal number of distinct palindromes. I Such words are called rich words in view of their palindromic richness.
Definition (G.-Justin-Widmer-Zamboni 2009) A finite word w is said to be rich if w contains exactly |w| + 1 distinct palindromes (including ε). Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
27
Sturmian words
Generalisations
A further generalisation: Palindromically rich words I We have seen that characteristic Sturmian words and standard episturmian words
begin with arbitrarily long palindromes. I In fact, all Sturmian and episturmian words are “rich” in palindromes in the sense
that all of their factors contain the maximum possible number of palindromic factors.
Theorem (Droubay-Justin-Pirillo 2001) Any finite word w of length |w| contains at most |w| + 1 distinct palindromes (including the empty word ε). I Inspired by this result, we initiated a unified study of finite and infinite words that
are characterised by containing the maximal number of distinct palindromes. I Such words are called rich words in view of their palindromic richness.
Definition (G.-Justin-Widmer-Zamboni 2009) A finite word w is said to be rich if w contains exactly |w| + 1 distinct palindromes (including ε). An infinite word is rich if all of its factors are rich. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
27
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word. For example:
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word. For example: I
rich is rich.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word. For example: I
rich is rich.
I
poor is rich too!
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word. For example: I
rich is rich.
I
poor is rich too!
I
But plentiful is not rich.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word. For example:
I
I
rich is rich.
I
poor is rich too!
I
But plentiful is not rich.
In the second sentence on this slide, only the following 4 words are not rich: language, consequence, going, unrepeated.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word. For example:
I
I
rich is rich.
I
poor is rich too!
I
But plentiful is not rich.
In the second sentence on this slide, only the following 4 words are not rich: language, consequence, going, unrepeated. This was easy to determine without counting palindromic factors
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
Examples I
abac is rich (it has 5 palindromic factors), whereas abca is not rich.
I
There exist many rich words in the English language – predominantly a consequence of most letters going unrepeated in a given English word. For example:
I
I
rich is rich.
I
poor is rich too!
I
But plentiful is not rich.
In the second sentence on this slide, only the following 4 words are not rich: language, consequence, going, unrepeated. This was easy to determine without counting palindromic factors . . . but how?
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
28
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · · A particularly nice characterisation of rich words is the following.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
A characterisation of palindromically rich words Essentially, a finite (or infinite) word is rich if and only if a new palindrome is introduced at each new position.
Example abaabaaabaaaabaaaaab · · · A particularly nice characterisation of rich words is the following.
Theorem (G.-Justin-Widmer-Zamboni 2009) A finite or infinite word w is (palindromically) rich if and only if all complete returns to palindromes are palindromes, i.e., every factor of w beginning with a palindrome p and ending with the next occurrence of p is a palindrome.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
29
Sturmian words
Generalisations
Extremal rich words On the 2-letter alphabet {a, b}, Sturmian words of the form acα and bcα for some α can be viewed as extremal rich words in the sense that all of the shifts of any Sturmian word of the same slope α lie between acα and bcα in the lexicographical order induced a < b
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
30
Sturmian words
Generalisations
Extremal rich words On the 2-letter alphabet {a, b}, Sturmian words of the form acα and bcα for some α can be viewed as extremal rich words in the sense that all of the shifts of any Sturmian word of the same slope α lie between acα and bcα in the lexicographical order induced a < b, and this property characterises Sturmian words of slope α.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
30
Sturmian words
Generalisations
Extremal rich words On the 2-letter alphabet {a, b}, Sturmian words of the form acα and bcα for some α can be viewed as extremal rich words in the sense that all of the shifts of any Sturmian word of the same slope α lie between acα and bcα in the lexicographical order induced a < b, and this property characterises Sturmian words of slope α.
Notation I
Let T denote the shift map on infinite words: T (x1 x2 x3 x4 x5 · · · ) := x2 x3 x4 x5 · · ·
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
30
Sturmian words
Generalisations
Extremal rich words On the 2-letter alphabet {a, b}, Sturmian words of the form acα and bcα for some α can be viewed as extremal rich words in the sense that all of the shifts of any Sturmian word of the same slope α lie between acα and bcα in the lexicographical order induced a < b, and this property characterises Sturmian words of slope α.
Notation I
Let T denote the shift map on infinite words: T (x1 x2 x3 x4 x5 · · · ) := x2 x3 x4 x5 · · ·
I
Let denote the lexicographic order on words over {a, b} induced by a < b.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
30
Sturmian words
Generalisations
Extremal rich words On the 2-letter alphabet {a, b}, Sturmian words of the form acα and bcα for some α can be viewed as extremal rich words in the sense that all of the shifts of any Sturmian word of the same slope α lie between acα and bcα in the lexicographical order induced a < b, and this property characterises Sturmian words of slope α.
Notation I
Let T denote the shift map on infinite words: T (x1 x2 x3 x4 x5 · · · ) := x2 x3 x4 x5 · · ·
I
Let denote the lexicographic order on words over {a, b} induced by a < b.
Theorem An aperiodic infinite word s on {a, b} is Sturmian if and only if there exists an infinite word u on {a, b} such that au T k (s) bu for all k ≥ 0. Moreover, u is the unique characteristic Sturmian word with the same slope as s.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
30
Sturmian words
Generalisations
Extremal rich words On the 2-letter alphabet {a, b}, Sturmian words of the form acα and bcα for some α can be viewed as extremal rich words in the sense that all of the shifts of any Sturmian word of the same slope α lie between acα and bcα in the lexicographical order induced a < b, and this property characterises Sturmian words of slope α.
Notation I
Let T denote the shift map on infinite words: T (x1 x2 x3 x4 x5 · · · ) := x2 x3 x4 x5 · · ·
I
Let denote the lexicographic order on words over {a, b} induced by a < b.
Theorem An aperiodic infinite word s on {a, b} is Sturmian if and only if there exists an infinite word u on {a, b} such that au T k (s) bu for all k ≥ 0. Moreover, u is the unique characteristic Sturmian word with the same slope as s. This result has been rediscovered several times since early work by P. Veerman (a physicist) in the mid-late 80’s. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
30
Sturmian words
Generalisations
Extremal rich words On the 2-letter alphabet {a, b}, Sturmian words of the form acα and bcα for some α can be viewed as extremal rich words in the sense that all of the shifts of any Sturmian word of the same slope α lie between acα and bcα in the lexicographical order induced a < b, and this property characterises Sturmian words of slope α.
Notation I
Let T denote the shift map on infinite words: T (x1 x2 x3 x4 x5 · · · ) := x2 x3 x4 x5 · · ·
I
Let denote the lexicographic order on words over {a, b} induced by a < b.
Theorem An aperiodic infinite word s on {a, b} is Sturmian if and only if there exists an infinite word u on {a, b} such that au T k (s) bu for all k ≥ 0. Moreover, u is the unique characteristic Sturmian word with the same slope as s. This result has been rediscovered several times since early work by P. Veerman (a physicist) in the mid-late 80’s. [G.-Allouche 2010] Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
30
Sturmian words
Generalisations
Example Recall the Fibonacci word on {a, b} f = abaababaabaababaaba · · · , √ the characteristic Sturmian word cα of slope α = (3 − 5)/2.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
31
Sturmian words
Generalisations
Example Recall the Fibonacci word on {a, b} f = abaababaabaababaaba · · · , √ the characteristic Sturmian word cα of slope α = (3 − 5)/2. f
z }| { aabaababaabaaba · · · abaababaabaaba · · · ≺ babaababaabaaba · ·}· ≺ | {z } | {z af
Amy Glen (Murdoch University)
bf
An introduction to combinatorics on words
December, 2016
31
Sturmian words
Generalisations
Example Recall the Fibonacci word on {a, b} f = abaababaabaababaaba · · · , √ the characteristic Sturmian word cα of slope α = (3 − 5)/2. T (f )
z }| { · ·}· aabaababaabaaba · ·}· ≺ baababaabaaba · · · ≺ babaababaabaaba | {z {z | af
Amy Glen (Murdoch University)
bf
An introduction to combinatorics on words
December, 2016
31
Sturmian words
Generalisations
Example Recall the Fibonacci word on {a, b} f = abaababaabaababaaba · · · , √ the characteristic Sturmian word cα of slope α = (3 − 5)/2. T 2 (f )
z }| { aabaababaabaaba · ·}· ≺ aababaabaaba · · · ≺ |babaababaabaaba · ·}· | {z {z af
Amy Glen (Murdoch University)
bf
An introduction to combinatorics on words
December, 2016
31
Sturmian words
Generalisations
Example Recall the Fibonacci word on {a, b} f = abaababaabaababaaba · · · , √ the characteristic Sturmian word cα of slope α = (3 − 5)/2. T 3 (f )
z }| { aabaababaabaaba · ·}· ≺ ababaabaaba · · · ≺ babaababaabaaba · ·}· | {z {z | af
Amy Glen (Murdoch University)
bf
An introduction to combinatorics on words
December, 2016
31
Sturmian words
Generalisations
Example Recall the Fibonacci word on {a, b} f = abaababaabaababaaba · · · , √ the characteristic Sturmian word cα of slope α = (3 − 5)/2. T 4 (f )
z }| { aabaababaabaaba · ·}· ≺ babaabaaba · · · ≺ babaababaabaaba · ·}· | {z | {z af
bf
and so on . . .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
31
Sturmian words
Generalisations
Example Recall the Fibonacci word on {a, b} f = abaababaabaababaaba · · · , √ the characteristic Sturmian word cα of slope α = (3 − 5)/2. T 4 (f )
z }| { aabaababaabaaba · ·}· ≺ babaabaaba · · · ≺ babaababaabaaba · ·}· | {z | {z af
bf
and so on . . . More generally, over a k-letter alphabet Ak = {a1 , a2 , . . . , ak } with a1 < a2 < · · · < ak , it can be shown that episturmian words of the form a1 s and ak s where s is a standard episturmian word are extremal, in the sense that all shifts of any episturmian word with the same set of factors as s lie between a1 s and ak s in lexicographical order. [G.-Justin-Pirillo 2008] Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
31
Lyndon words
Lyndon words In particular, we note that acα can be viewed as an “infinite Lyndon word” in the sense that it is strictly lexicographically less than all of its proper shifts.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
32
Lyndon words
Lyndon words In particular, we note that acα can be viewed as an “infinite Lyndon word” in the sense that it is strictly lexicographically less than all of its proper shifts.
Definition (Lyndon word) A Lyndon word on an ordered alphabet A is a non-empty primitive word that is the lexicographically least word among its conjugates (a.k.a. circular shifts), i.e., w ∈ A or w ≺ vu for all non-empty words u, v such that w = uv.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
32
Lyndon words
Lyndon words In particular, we note that acα can be viewed as an “infinite Lyndon word” in the sense that it is strictly lexicographically less than all of its proper shifts.
Definition (Lyndon word) A Lyndon word on an ordered alphabet A is a non-empty primitive word that is the lexicographically least word among its conjugates (a.k.a. circular shifts), i.e., w ∈ A or w ≺ vu for all non-empty words u, v such that w = uv.
Example (Finite Fibonacci words and their Lyndon conjugates) fn f1 = ab f2 = aba = P al(a)ba f3 = abaab = P al(ab)ab f4 = abaababa = P al(aba)ba f5 = abaababaabaab = P al(abab)ab .. . Amy Glen (Murdoch University)
Lyndon conjugate ab = aP al(ε)b aab = aP al(a)b aabab = aP al(ab)b aabaabab = aP al(aba)b aabaababaabaab = aP al(abab)b .. .
An introduction to combinatorics on words
December, 2016
32
Lyndon words
Sturmian Lyndon words The Lyndon conjugates of the finite Fibonacci words are precisely the Lyndon factors of the infinite Fibonacci word f .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
33
Lyndon words
Sturmian Lyndon words The Lyndon conjugates of the finite Fibonacci words are precisely the Lyndon factors of the infinite Fibonacci word f . More generally:
Theorem (Berstel-de Luca 1997) Let cα be the characteristic Sturmian word of slope α = [0; 1 + d1 , d2 , d3 , . . .] with cα = lim sn where the words sn are defined as before. n→∞
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
33
Lyndon words
Sturmian Lyndon words The Lyndon conjugates of the finite Fibonacci words are precisely the Lyndon factors of the infinite Fibonacci word f . More generally:
Theorem (Berstel-de Luca 1997) Let cα be the characteristic Sturmian word of slope α = [0; 1 + d1 , d2 , d3 , . . .] with cα = lim sn where the words sn are defined as before. n→∞
The Lyndon factors of cα of length at least 2 are precisely the Lyndon conjugates of the (primitive) standard words sn for all n ≥ 1.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
33
Lyndon words
Sturmian Lyndon words The Lyndon conjugates of the finite Fibonacci words are precisely the Lyndon factors of the infinite Fibonacci word f . More generally:
Theorem (Berstel-de Luca 1997) Let cα be the characteristic Sturmian word of slope α = [0; 1 + d1 , d2 , d3 , . . .] with cα = lim sn where the words sn are defined as before. n→∞
The Lyndon factors of cα of length at least 2 are precisely the Lyndon conjugates of the (primitive) standard words sn for all n ≥ 1. The Lyndon factors of (characteristic) Sturmian words of length at least 2 (i.e., the Lyndon conjugates of standard words) over {a, b} are precisely the words of the form aP al(v)b where v ∈ {a, b}, known as Sturmian Lyndon words or Christoffel words. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
33
Lyndon words
Lyndon words are the ‘primes’ of combinatorics on words A famous theorem concerning Lyndon words asserts that every word w can be uniquely factorised as a non-increasing product of Lyndon words . . .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
34
Lyndon words
Lyndon words are the ‘primes’ of combinatorics on words A famous theorem concerning Lyndon words asserts that every word w can be uniquely factorised as a non-increasing product of Lyndon words . . .
Theorem Any word w ∈ A+ may be uniquely written as a non-increasing product of Lyndon words, i.e., w = `1 `2 · · · `n where the `i are Lyndon words such that `1 `2 · · · `n
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
34
Lyndon words
Lyndon words are the ‘primes’ of combinatorics on words A famous theorem concerning Lyndon words asserts that every word w can be uniquely factorised as a non-increasing product of Lyndon words . . .
Theorem Any word w ∈ A+ may be uniquely written as a non-increasing product of Lyndon words, i.e., w = `1 `2 · · · `n where the `i are Lyndon words such that `1 `2 · · · `n , called the Lyndon factorisation of w.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
34
Lyndon words
Lyndon words are the ‘primes’ of combinatorics on words A famous theorem concerning Lyndon words asserts that every word w can be uniquely factorised as a non-increasing product of Lyndon words . . .
Theorem Any word w ∈ A+ may be uniquely written as a non-increasing product of Lyndon words, i.e., w = `1 `2 · · · `n where the `i are Lyndon words such that `1 `2 · · · `n , called the Lyndon factorisation of w. Example: abaacaab
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
34
Lyndon words
Lyndon words are the ‘primes’ of combinatorics on words A famous theorem concerning Lyndon words asserts that every word w can be uniquely factorised as a non-increasing product of Lyndon words . . .
Theorem Any word w ∈ A+ may be uniquely written as a non-increasing product of Lyndon words, i.e., w = `1 `2 · · · `n where the `i are Lyndon words such that `1 `2 · · · `n , called the Lyndon factorisation of w. Example: abaacaab = (ab)(aac)(aab)
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
34
Lyndon words
Lyndon words are the ‘primes’ of combinatorics on words A famous theorem concerning Lyndon words asserts that every word w can be uniquely factorised as a non-increasing product of Lyndon words . . .
Theorem Any word w ∈ A+ may be uniquely written as a non-increasing product of Lyndon words, i.e., w = `1 `2 · · · `n where the `i are Lyndon words such that `1 `2 · · · `n , called the Lyndon factorisation of w. Example: abaacaab = (ab)(aac)(aab) The origin of the theorem is unclear
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
34
Lyndon words
Lyndon words are the ‘primes’ of combinatorics on words A famous theorem concerning Lyndon words asserts that every word w can be uniquely factorised as a non-increasing product of Lyndon words . . .
Theorem Any word w ∈ A+ may be uniquely written as a non-increasing product of Lyndon words, i.e., w = `1 `2 · · · `n where the `i are Lyndon words such that `1 `2 · · · `n , called the Lyndon factorisation of w. Example: abaacaab = (ab)(aac)(aab) The origin of the theorem is unclear – it is usually credited to Chen-Fox-Lyndon (1958), whose paper does not explicitly contain the statement, but it can be recovered from their results.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
34
Burrows-Wheeler Transform
Burrows-Wheeler Transform In 2003, Manataci et al. proved a remarkable result concerning Sturmian Lyndon words in relation to the Burrows-Wheeler Transform.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
35
Burrows-Wheeler Transform
Burrows-Wheeler Transform In 2003, Manataci et al. proved a remarkable result concerning Sturmian Lyndon words in relation to the Burrows-Wheeler Transform. I
Originally introduced in 1994, the Burrows-Wheeler transform (or BWT for short) is a reversible transformation on words that has proven to be extremely useful in textual data compression.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
35
Burrows-Wheeler Transform
Burrows-Wheeler Transform In 2003, Manataci et al. proved a remarkable result concerning Sturmian Lyndon words in relation to the Burrows-Wheeler Transform. I
Originally introduced in 1994, the Burrows-Wheeler transform (or BWT for short) is a reversible transformation on words that has proven to be extremely useful in textual data compression.
I
The underlying idea consists in grouping together symbols that appear in similar contexts, so that the output of the transformation produces a sequence where most instances of the same symbol occur clustered together, which in turn allows for fast compression rates.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
35
Burrows-Wheeler Transform
Burrows-Wheeler Transform In 2003, Manataci et al. proved a remarkable result concerning Sturmian Lyndon words in relation to the Burrows-Wheeler Transform. I
Originally introduced in 1994, the Burrows-Wheeler transform (or BWT for short) is a reversible transformation on words that has proven to be extremely useful in textual data compression.
I
The underlying idea consists in grouping together symbols that appear in similar contexts, so that the output of the transformation produces a sequence where most instances of the same symbol occur clustered together, which in turn allows for fast compression rates.
I
From this point of view, it is interesting to consider the extremal case in which the BWT produces a perfect clustering of all instances of any symbol.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
35
Burrows-Wheeler Transform
Burrows-Wheeler Transform . . . I The BWT takes as input a word w, and produces as output a permutation
BW T (w), obtained as follows.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
36
Burrows-Wheeler Transform
Burrows-Wheeler Transform . . . I The BWT takes as input a word w, and produces as output a permutation
BW T (w), obtained as follows. I Let M (w) be the matrix composed of all conjugates of w, ordered
lexicographically. Then BW T (w) is the last column of M (w).
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
36
Burrows-Wheeler Transform
Burrows-Wheeler Transform . . . I The BWT takes as input a word w, and produces as output a permutation
BW T (w), obtained as follows. I Let M (w) be the matrix composed of all conjugates of w, ordered
lexicographically. Then BW T (w) is the last column of M (w).
Example For the input word w = f4 = abaababa, the matrix is a a b a a b a a b a b a a b a a b a a b a a b a M (w) = a b a b a a b a a b a a b a a b a b b a b a a b
Amy Glen (Murdoch University)
a a a b b b a a
An introduction to combinatorics on words
b b b a a a a a
December, 2016
36
Burrows-Wheeler Transform
Burrows-Wheeler Transform . . . I The BWT takes as input a word w, and produces as output a permutation
BW T (w), obtained as follows. I Let M (w) be the matrix composed of all conjugates of w, ordered
lexicographically. Then BW T (w) is the last column of M (w).
Example For the input word w = f4 = abaababa, the matrix is a a b a a b a a b a b a a b a a b a a b a a b a M (w) = a b a b a a b a a b a a b a a b a b b a b a a b and the output is the last column
Amy Glen (Murdoch University)
a a a b b b a a
An introduction to combinatorics on words
b b b a a a a a
December, 2016
36
Burrows-Wheeler Transform
Burrows-Wheeler Transform . . . I The BWT takes as input a word w, and produces as output a permutation
BW T (w), obtained as follows. I Let M (w) be the matrix composed of all conjugates of w, ordered
lexicographically. Then BW T (w) is the last column of M (w).
Example For the input word w = f4 = abaababa, the matrix is a a b a a b a a a b a b a a a b a a b a a a b a a b a b M (w) = a b a b a a b b a a b a a b b a a b a b a b a b a a b a and the output is the last column, i.e., BW T (w) = b3 a5 .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
b b b a a a a a
December, 2016
36
Burrows-Wheeler Transform
Burrows-Wheeler Transform . . . I The BWT takes as input a word w, and produces as output a permutation
BW T (w), obtained as follows. I Let M (w) be the matrix composed of all conjugates of w, ordered
lexicographically. Then BW T (w) is the last column of M (w).
Example For the input word w = f4 = abaababa, the matrix is a a b a a b a a a b a b a a a b a a b a a a b a a b a b M (w) = a b a b a a b b a a b a a b b a a b a b a b a b a a b a and the output is the last column, i.e., BW T (w) = b3 a5 .
b b b a a a a a
To make the transformation injective, the position of the input word in the matrix is added to the transform. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
36
Balanced words
Balanced words
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
37
Balanced words
Balanced words
Manataci et al. (2003) proved that the words over {a, b} with Burrows-Wheeler Transforms of the form bi aj are precisely the powers of conjugates of Sturmian Lyndon words, i.e., the powers of strongly balanced words on {a, b}.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
37
Balanced words
Balanced words
Manataci et al. (2003) proved that the words over {a, b} with Burrows-Wheeler Transforms of the form bi aj are precisely the powers of conjugates of Sturmian Lyndon words, i.e., the powers of strongly balanced words on {a, b}.
Definition A finite or infinite word is said to be q-balanced if, for any two of its factors u, v with |u| = |v|, we have ||u|x − |v|x | ≤ q for any letter x, i.e., the number of x’s in each of u and v differs by at most q.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
37
Balanced words
Balanced words
Manataci et al. (2003) proved that the words over {a, b} with Burrows-Wheeler Transforms of the form bi aj are precisely the powers of conjugates of Sturmian Lyndon words, i.e., the powers of strongly balanced words on {a, b}.
Definition A finite or infinite word is said to be q-balanced if, for any two of its factors u, v with |u| = |v|, we have ||u|x − |v|x | ≤ q for any letter x, i.e., the number of x’s in each of u and v differs by at most q. A 1-balanced word is said to be balanced.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
37
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes:
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes: I
aperiodic Sturmian
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes: I I
aperiodic Sturmian periodic Sturmian — which take the form (P al(v)xy)∞ where v ∈ {a, b}∗ and xy ∈ {ab, ba}
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes: I I
I
aperiodic Sturmian periodic Sturmian — which take the form (P al(v)xy)∞ where v ∈ {a, b}∗ and xy ∈ {ab, ba} skew words — ultimately periodic non-recurrent infinite words of the form µ(xp yx∞ ), µ a pure standard (Sturmian) morphism, x, y ∈ {a, b}, x 6= y.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes: I I
I
aperiodic Sturmian periodic Sturmian — which take the form (P al(v)xy)∞ where v ∈ {a, b}∗ and xy ∈ {ab, ba} skew words — ultimately periodic non-recurrent infinite words of the form µ(xp yx∞ ), µ a pure standard (Sturmian) morphism, x, y ∈ {a, b}, x 6= y.
I That is, the family of balanced infinite words consists of the (recurrent) Sturmian
words and the (non-recurrent) skew infinite words, the factors of which are balanced.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes: I I
I
aperiodic Sturmian periodic Sturmian — which take the form (P al(v)xy)∞ where v ∈ {a, b}∗ and xy ∈ {ab, ba} skew words — ultimately periodic non-recurrent infinite words of the form µ(xp yx∞ ), µ a pure standard (Sturmian) morphism, x, y ∈ {a, b}, x 6= y.
I That is, the family of balanced infinite words consists of the (recurrent) Sturmian
words and the (non-recurrent) skew infinite words, the factors of which are balanced. I A finite binary word is balanced if and only if it is a factor of a Sturmian word.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes: I I
I
aperiodic Sturmian periodic Sturmian — which take the form (P al(v)xy)∞ where v ∈ {a, b}∗ and xy ∈ {ab, ba} skew words — ultimately periodic non-recurrent infinite words of the form µ(xp yx∞ ), µ a pure standard (Sturmian) morphism, x, y ∈ {a, b}, x 6= y.
I That is, the family of balanced infinite words consists of the (recurrent) Sturmian
words and the (non-recurrent) skew infinite words, the factors of which are balanced. I A finite binary word is balanced if and only if it is a factor of a Sturmian word.
A finite word w is strongly balanced if w is primitive and w2 is balanced.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
Facts I In the pioneering work of Morse and Hedlund (1940), balanced infinite words over
a 2-letter alphabet were called ‘Sturmian trajectories’ and belong to three classes: I I
I
aperiodic Sturmian periodic Sturmian — which take the form (P al(v)xy)∞ where v ∈ {a, b}∗ and xy ∈ {ab, ba} skew words — ultimately periodic non-recurrent infinite words of the form µ(xp yx∞ ), µ a pure standard (Sturmian) morphism, x, y ∈ {a, b}, x 6= y.
I That is, the family of balanced infinite words consists of the (recurrent) Sturmian
words and the (non-recurrent) skew infinite words, the factors of which are balanced. I A finite binary word is balanced if and only if it is a factor of a Sturmian word.
A finite word w is strongly balanced if w is primitive and w2 is balanced. The strongly balanced words on {a, b} are precisely the conjugates of Sturmian Lyndon words (or equivalently, the conjugates of a standard words). [Jenkinson-Zamboni 2004, Chuan 2004, de Luca-De Luca 2006]
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
38
Balanced words
I
Episturmian words on three or more letters are generally unbalanced in the sense of 1-balance, except, of course, for those on a 2-letter alphabet, which are precisely the (periodic and aperiodic) Sturmian words.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
39
Balanced words
I
Episturmian words on three or more letters are generally unbalanced in the sense of 1-balance, except, of course, for those on a 2-letter alphabet, which are precisely the (periodic and aperiodic) Sturmian words.
I
In fact, Cassaigne, Ferenczi, and Zamboni (2000) proved, by construction, that there exists an episturmian word that is not q-balanced for any q.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
39
Balanced words
I
Episturmian words on three or more letters are generally unbalanced in the sense of 1-balance, except, of course, for those on a 2-letter alphabet, which are precisely the (periodic and aperiodic) Sturmian words.
I
In fact, Cassaigne, Ferenczi, and Zamboni (2000) proved, by construction, that there exists an episturmian word that is not q-balanced for any q.
I
Note, however, that the Tribonacci word is 2-balanced, for example.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
39
Balanced words
I
Episturmian words on three or more letters are generally unbalanced in the sense of 1-balance, except, of course, for those on a 2-letter alphabet, which are precisely the (periodic and aperiodic) Sturmian words.
I
In fact, Cassaigne, Ferenczi, and Zamboni (2000) proved, by construction, that there exists an episturmian word that is not q-balanced for any q.
I
Note, however, that the Tribonacci word is 2-balanced, for example.
A natural question to ask is: “What are the balanced recurrent infinite words on more than two letters?”
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
39
Balanced words
I
Episturmian words on three or more letters are generally unbalanced in the sense of 1-balance, except, of course, for those on a 2-letter alphabet, which are precisely the (periodic and aperiodic) Sturmian words.
I
In fact, Cassaigne, Ferenczi, and Zamboni (2000) proved, by construction, that there exists an episturmian word that is not q-balanced for any q.
I
Note, however, that the Tribonacci word is 2-balanced, for example.
A natural question to ask is: “What are the balanced recurrent infinite words on more than two letters?”
Theorem (Paquin-Vuillon 2007) Up to letter permutation, the balanced episturmian words on a k-letter alphabet {1, 2, . . . , k} (k ≥ 3) with mutually distinct letter frequencies are precisely the shifts of (P al(12 · · · k))∞ .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
39
Balanced words
I
Episturmian words on three or more letters are generally unbalanced in the sense of 1-balance, except, of course, for those on a 2-letter alphabet, which are precisely the (periodic and aperiodic) Sturmian words.
I
In fact, Cassaigne, Ferenczi, and Zamboni (2000) proved, by construction, that there exists an episturmian word that is not q-balanced for any q.
I
Note, however, that the Tribonacci word is 2-balanced, for example.
A natural question to ask is: “What are the balanced recurrent infinite words on more than two letters?”
Theorem (Paquin-Vuillon 2007) Up to letter permutation, the balanced episturmian words on a k-letter alphabet {1, 2, . . . , k} (k ≥ 3) with mutually distinct letter frequencies are precisely the shifts of (P al(12 · · · k))∞ . The importance of this result lies in the fact that it supports Fraenkel’s conjecture (1973): a famous problem that arose in a number-theoretic context and has remained unsolved for over forty years. Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
39
Fraenkel’s conjecture
Fraenkel’s conjecture I
Fraenkel conjectured that, for any fixed integer k ≥ 3, there is only one covering of Z by k Beatty sequences of the form {bαn + βc}n≥1 , where α is rational and β ∈ R.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
40
Fraenkel’s conjecture
Fraenkel’s conjecture I
Fraenkel conjectured that, for any fixed integer k ≥ 3, there is only one covering of Z by k Beatty sequences of the form {bαn + βc}n≥1 , where α is rational and β ∈ R.
I
Note that the sequence of first differences of the terms of a Beatty sequence: {bαn + βc − bα(n − 1) + βc}n≥1 forms a “periodic Sturmian word” (i.e., a purely periodic balanced infinite word) over {k, k + 1} where k = bαc.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
40
Fraenkel’s conjecture
Fraenkel’s conjecture I
Fraenkel conjectured that, for any fixed integer k ≥ 3, there is only one covering of Z by k Beatty sequences of the form {bαn + βc}n≥1 , where α is rational and β ∈ R.
I
Note that the sequence of first differences of the terms of a Beatty sequence: {bαn + βc − bα(n − 1) + βc}n≥1 forms a “periodic Sturmian word” (i.e., a purely periodic balanced infinite word) over {k, k + 1} where k = bαc.
I
A combinatorial interpretation of the conjecture is as follows.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
40
Fraenkel’s conjecture
Fraenkel’s conjecture I
Fraenkel conjectured that, for any fixed integer k ≥ 3, there is only one covering of Z by k Beatty sequences of the form {bαn + βc}n≥1 , where α is rational and β ∈ R.
I
Note that the sequence of first differences of the terms of a Beatty sequence: {bαn + βc − bα(n − 1) + βc}n≥1 forms a “periodic Sturmian word” (i.e., a purely periodic balanced infinite word) over {k, k + 1} where k = bαc.
I
A combinatorial interpretation of the conjecture is as follows.
Fraenkel’s Conjecture Over a finite alphabet consisting of at least three letters, there is only one balanced recurrent infinite word with mutually distinct letter frequencies, up to letter permutation and shifts.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
40
Fraenkel’s conjecture
Fraenkel’s conjecture I
Fraenkel conjectured that, for any fixed integer k ≥ 3, there is only one covering of Z by k Beatty sequences of the form {bαn + βc}n≥1 , where α is rational and β ∈ R.
I
Note that the sequence of first differences of the terms of a Beatty sequence: {bαn + βc − bα(n − 1) + βc}n≥1 forms a “periodic Sturmian word” (i.e., a purely periodic balanced infinite word) over {k, k + 1} where k = bαc.
I
A combinatorial interpretation of the conjecture is as follows.
Fraenkel’s Conjecture Over a finite alphabet consisting of at least three letters, there is only one balanced recurrent infinite word with mutually distinct letter frequencies, up to letter permutation and shifts. The frequency of a letter a in an infinite word x = x1 x2 x3 x4 · · · is lim
n→∞ Amy Glen (Murdoch University)
|x1 x2 x3 · · · xn |a n
An introduction to combinatorics on words
December, 2016
40
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2. [Note that Fk = P al(12 · · · k).]
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2. [Note that Fk = P al(12 · · · k).] I
To date, the conjecture has been proved to be true for k = 3, 4, 5, 6 [Tijdeman 2000 (3 ≤ k ≤ 6), Altman-Gaujal-Hordijk 2001 (k = 4), Barát-Varjú 2003 (k = 7)]
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2. [Note that Fk = P al(12 · · · k).] I
To date, the conjecture has been proved to be true for k = 3, 4, 5, 6 [Tijdeman 2000 (3 ≤ k ≤ 6), Altman-Gaujal-Hordijk 2001 (k = 4), Barát-Varjú 2003 (k = 7)]
I
In particular, for k = 3 the unique balanced infinite word (up to letter permutation and shifts) on the alphabet {1, 2, 3} is (1213121)∞ .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2. [Note that Fk = P al(12 · · · k).] I
To date, the conjecture has been proved to be true for k = 3, 4, 5, 6 [Tijdeman 2000 (3 ≤ k ≤ 6), Altman-Gaujal-Hordijk 2001 (k = 4), Barát-Varjú 2003 (k = 7)]
I
In particular, for k = 3 the unique balanced infinite word (up to letter permutation and shifts) on the alphabet {1, 2, 3} is (1213121)∞ .
I
We see that the frequencies are all different:
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2. [Note that Fk = P al(12 · · · k).] I
To date, the conjecture has been proved to be true for k = 3, 4, 5, 6 [Tijdeman 2000 (3 ≤ k ≤ 6), Altman-Gaujal-Hordijk 2001 (k = 4), Barát-Varjú 2003 (k = 7)]
I
In particular, for k = 3 the unique balanced infinite word (up to letter permutation and shifts) on the alphabet {1, 2, 3} is (1213121)∞ .
I
We see that the frequencies are all different: I
the frequency of the letter 1 is 4/7 because there are four occurrences of the letter 1 in the period;
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2. [Note that Fk = P al(12 · · · k).] I
To date, the conjecture has been proved to be true for k = 3, 4, 5, 6 [Tijdeman 2000 (3 ≤ k ≤ 6), Altman-Gaujal-Hordijk 2001 (k = 4), Barát-Varjú 2003 (k = 7)]
I
In particular, for k = 3 the unique balanced infinite word (up to letter permutation and shifts) on the alphabet {1, 2, 3} is (1213121)∞ .
I
We see that the frequencies are all different: I
I
the frequency of the letter 1 is 4/7 because there are four occurrences of the letter 1 in the period; the frequency of the letter 2 is 2/7;
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Fraenkel’s conjecture. . . The supposedly unique infinite word satisfying the conjecture (up to letter permutations and shifts) on a k-letter alphabet, k ≥ 3, is called Fraenkel’s sequence and is given by (Fk )∞ , where the Fraenkel words {Fi }i≥1 are defined recursively by F1 = 1 and Fi = Fi−1 iFi−1 for all i ≥ 2. [Note that Fk = P al(12 · · · k).] I
To date, the conjecture has been proved to be true for k = 3, 4, 5, 6 [Tijdeman 2000 (3 ≤ k ≤ 6), Altman-Gaujal-Hordijk 2001 (k = 4), Barát-Varjú 2003 (k = 7)]
I
In particular, for k = 3 the unique balanced infinite word (up to letter permutation and shifts) on the alphabet {1, 2, 3} is (1213121)∞ .
I
We see that the frequencies are all different: I
I I
the frequency of the letter 1 is 4/7 because there are four occurrences of the letter 1 in the period; the frequency of the letter 2 is 2/7; and the frequency of the letter 3 is 1/7.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
41
Fraenkel’s conjecture
Tying it all together I
In 2009, we showed that the balanced recurrent rich infinite words are necessarily episturmian and hence obey Fraenkel’s conjecture.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
42
Fraenkel’s conjecture
Tying it all together I
In 2009, we showed that the balanced recurrent rich infinite words are necessarily episturmian and hence obey Fraenkel’s conjecture.
I
Moreover, balanced recurrent weakly rich words (in which complete returns to letters are palindromes) are necessarily episturmian and hence satisfy Fraenkel’s conjecture.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
42
Fraenkel’s conjecture
Tying it all together I
In 2009, we showed that the balanced recurrent rich infinite words are necessarily episturmian and hence obey Fraenkel’s conjecture.
I
Moreover, balanced recurrent weakly rich words (in which complete returns to letters are palindromes) are necessarily episturmian and hence satisfy Fraenkel’s conjecture.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
42
Fraenkel’s conjecture
Tying it all together I
In 2009, we showed that the balanced recurrent rich infinite words are necessarily episturmian and hence obey Fraenkel’s conjecture.
I
Moreover, balanced recurrent weakly rich words (in which complete returns to letters are palindromes) are necessarily episturmian and hence satisfy Fraenkel’s conjecture.
I
Furthermore, any word v for which the BWT of v is the lexicographically greatest perfect clustering on its alphabet is circularly rich, i.e., vv is rich.
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
42
Fraenkel’s conjecture
Plan of attack: Word satisfying the conditions of Fraenkel’s conjecture
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
43
Fraenkel’s conjecture
Plan of attack: Word satisfying the conditions of Fraenkel’s conjecture → purely periodic with (shortest) period having perfectly clustered BWT
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
43
Fraenkel’s conjecture
Plan of attack: Word satisfying the conditions of Fraenkel’s conjecture → purely periodic with (shortest) period having perfectly clustered BWT → circularly rich and balanced
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
43
Fraenkel’s conjecture
Plan of attack: Word satisfying the conditions of Fraenkel’s conjecture → purely periodic with (shortest) period having perfectly clustered BWT → circularly rich and balanced → episturmian
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
43
Fraenkel’s conjecture
Plan of attack: Word satisfying the conditions of Fraenkel’s conjecture → purely periodic with (shortest) period having perfectly clustered BWT → circularly rich and balanced → episturmian Hence Franekel’s conjecture is true! QED
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
43
Fraenkel’s conjecture
Plan of attack: Word satisfying the conditions of Fraenkel’s conjecture → purely periodic with (shortest) period having perfectly clustered BWT → circularly rich and balanced → episturmian Hence Franekel’s conjecture is true! QED Not so easy . . .
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
43
Fraenkel’s conjecture
Plan of attack: Word satisfying the conditions of Fraenkel’s conjecture → purely periodic with (shortest) period having perfectly clustered BWT → circularly rich and balanced → episturmian Hence Franekel’s conjecture is true! QED Not so easy . . . /
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
43
Thank You!
Amy Glen (Murdoch University)
An introduction to combinatorics on words
December, 2016
44
