October 30, 2017 | Author: Anonymous | Category: N/A
Codes. Logic. Probability Theory. Biology. DNA sequencing, Patterns. Discrete Geometry. Amy Glen ......
Palindromic sequences in Number Theory Amy Glen The Mathematics Institute @ Reykjavík University
[email protected] http://www.ru.is/kennarar/amy
Department of Mathematics and Statistics @ University of Winnipeg
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
1 / 48
Outline
1
Combinatorics on Words Sturmian & Episturmian Words
2
Some Connections to Number Theory Continued Fractions & Sturmian Words Palindromes & Diophantine Approximation Transcendental Numbers Miscellaneous
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
2 / 48
Combinatorics on Words
Outline
1
Combinatorics on Words Sturmian & Episturmian Words
2
Some Connections to Number Theory Continued Fractions & Sturmian Words Palindromes & Diophantine Approximation Transcendental Numbers Miscellaneous
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
3 / 48
Combinatorics on Words
Starting point: Combinatorics on words 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 (Reykjavík University)
Palindromes in Number Theory
April 2009
4 / 48
Combinatorics on Words
Starting point: Combinatorics on words 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
A word w is a finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet).
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
4 / 48
Combinatorics on Words
Starting point: Combinatorics on words 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
A word w is a finite or infinite sequence of symbols (letters) taken from a non-empty finite set A (alphabet). Example with A = {a, b, c}: w = abca, w ∞ = abcaabcaabca · · · Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
4 / 48
Combinatorics on Words
Combinatorics on words: A brief history
Relatively new area of Discrete Mathematics
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
5 / 48
Combinatorics on Words
Combinatorics on words: A brief history
Relatively new area of Discrete Mathematics Early 1900’s: First investigations by Axel Thue (repetitions in words)
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
5 / 48
Combinatorics on Words
Combinatorics on words: A brief history
Relatively new area of Discrete Mathematics Early 1900’s: First investigations by Axel Thue (repetitions in words) 1938: Marston Morse & Gustav Hedlund Initiated the formal development of symbolic dynamics.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
5 / 48
Combinatorics on Words
Combinatorics on words: A brief history
Relatively new area of Discrete Mathematics Early 1900’s: First investigations by Axel Thue (repetitions in words) 1938: Marston Morse & Gustav Hedlund Initiated the formal development of symbolic dynamics. This work marked the beginning of the study of words.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
5 / 48
Combinatorics on Words
Combinatorics on words: A brief history
Relatively new area of Discrete Mathematics Early 1900’s: First investigations by Axel Thue (repetitions in words) 1938: Marston Morse & Gustav Hedlund Initiated the formal development of symbolic dynamics. This work marked the beginning of the study of words. 1960’s: Systematic study initiated by M.P. Schützenberger.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
5 / 48
Combinatorics on Words
Combinatorics on words: Complexity Most commonly studied words are those which satisfy one or more strong regularity properties; for instance, words containing many repetitions or palindromes.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
6 / 48
Combinatorics on Words
Combinatorics on words: Complexity Most commonly studied words are those which satisfy one or more strong regularity properties; for instance, words containing many repetitions or palindromes. A palindrome is a word that reads the same backwards as forwards. Examples: eye, civic, radar, glenelg (Aussie suburb).
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
6 / 48
Combinatorics on Words
Combinatorics on words: Complexity Most commonly studied words are those which satisfy one or more strong regularity properties; for instance, words containing many repetitions or palindromes. A palindrome is a word that reads the same backwards as forwards. Examples: eye, civic, radar, glenelg (Aussie suburb). The extent to which a word exhibits strong regularity properties is generally inversely proportional to its “complexity”.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
6 / 48
Combinatorics on Words
Combinatorics on words: Complexity Most commonly studied words are those which satisfy one or more strong regularity properties; for instance, words containing many repetitions or palindromes. A palindrome is a word that reads the same backwards as forwards. Examples: eye, civic, radar, glenelg (Aussie suburb). The extent to which a word exhibits strong regularity properties is generally inversely proportional to its “complexity”. Basic measure: Number of distinct blocks (factors) of each length occurring in the word.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
6 / 48
Combinatorics on Words
Combinatorics on words: Complexity Most commonly studied words are those which satisfy one or more strong regularity properties; for instance, words containing many repetitions or palindromes. A palindrome is a word that reads the same backwards as forwards. Examples: eye, civic, radar, glenelg (Aussie suburb). The extent to which a word exhibits strong regularity properties is generally inversely proportional to its “complexity”. Basic measure: Number of distinct blocks (factors) of each length occurring in the word. Example: w = abca has 9 distinct factors: a, b, c, ab, bc, ca, abc, bca, abca. | {z } | {z } | {z } | {z } 1
Amy Glen (Reykjavík University)
2
3
Palindromes in Number Theory
4
April 2009
6 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words Theorem (Morse-Hedlund 1940) An infinite word w is ultimately periodic if and only if w has less than n + 1 distinct factors of length n for some n.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
7 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words Theorem (Morse-Hedlund 1940) An infinite word w is ultimately periodic if and only if w has less than n + 1 distinct factors of length n for some n. Sturmian words Aperiodic infinite words of minimal complexity – exactly n + 1 distinct factors of length n for each n.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
7 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words Theorem (Morse-Hedlund 1940) An infinite word w is ultimately periodic if and only if w has less than n + 1 distinct factors of length n for some n. Sturmian words Aperiodic infinite words of minimal complexity – exactly n + 1 distinct factors of length n for each n. Pioneering work by Morse & Hedlund in 1940 (symbolic dynamics).
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
7 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words Theorem (Morse-Hedlund 1940) An infinite word w is ultimately periodic if and only if w has less than n + 1 distinct factors of length n for some n. Sturmian words Aperiodic infinite words of minimal complexity – exactly n + 1 distinct factors of length n for each n. Pioneering work by Morse & Hedlund in 1940 (symbolic dynamics). Low complexity accounts for many interesting features, as it induces certain regularities, without periodicity.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
7 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words Theorem (Morse-Hedlund 1940) An infinite word w is ultimately periodic if and only if w has less than n + 1 distinct factors of length n for some n. Sturmian words Aperiodic infinite words of minimal complexity – exactly n + 1 distinct factors of length n for each n. Pioneering work by Morse & Hedlund in 1940 (symbolic dynamics). Low complexity accounts for many interesting features, as it induces certain regularities, without periodicity. Points of view: combinatorial; algebraic; geometric.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
7 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words Theorem (Morse-Hedlund 1940) An infinite word w is ultimately periodic if and only if w has less than n + 1 distinct factors of length n for some n. Sturmian words Aperiodic infinite words of minimal complexity – exactly n + 1 distinct factors of length n for each n. Pioneering work by Morse & Hedlund in 1940 (symbolic dynamics). Low complexity accounts for many interesting features, as it induces certain regularities, without periodicity. Points of view: combinatorial; algebraic; geometric. References in: Combinatorics, Symbolic Dynamics, Number Theory, Discrete Geometry, Theoretical Physics, Theoretical Computer Science. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
7 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words Theorem (Morse-Hedlund 1940) An infinite word w is ultimately periodic if and only if w has less than n + 1 distinct factors of length n for some n. Sturmian words Aperiodic infinite words of minimal complexity – exactly n + 1 distinct factors of length n for each n. Pioneering work by Morse & Hedlund in 1940 (symbolic dynamics). Low complexity accounts for many interesting features, as it induces certain regularities, without periodicity. Points of view: combinatorial; algebraic; geometric. References in: Combinatorics, Symbolic Dynamics, Number Theory, Discrete Geometry, Theoretical Physics, Theoretical Computer Science. Numerous equivalent definitions & characterisations . . . Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
7 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: A special family of finite Sturmian words Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
8 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
9 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
10 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
11 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
12 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
13 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
14 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
15 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
Amy Glen (Reykjavík University)
3 5
Palindromes in Number Theory
April 2009
16 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
3 5
a L(5,3) = a Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
17 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
a
3 5
a L(5,3) = aa
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
18 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
3 5
b a
a L(5,3) = aab
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
19 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
b a
3 5
a
a L(5,3) = aaba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
20 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
b a
3 5
a
a
a L(5,3) = aabaa
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
21 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
3 5
b b a
a
a
a L(5,3) = aabaab
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
22 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
3 5
b b a
a
a
a
a L(5,3) = aabaaba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
23 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower Christoffel word of slope
3 5
b b b a
a
a
a
a L(5,3) = aabaabab
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
24 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Construction Lower & Upper Christoffel words of slope
3 5
a b
a
a
a
b
a b a
a
a
b
b a
b
a
L(5,3) = aabaabab
Amy Glen (Reykjavík University)
U(5,3) = babaabaa
Palindromes in Number Theory
April 2009
25 / 48
Combinatorics on Words
Sturmian & Episturmian Words
From Christoffel words to Sturmian words Sturmian words: Obtained *similarly* by replacing the line segment by a half-line: y = αx + ρ with irrational α ∈ (0, 1), ρ ∈ R.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
26 / 48
Combinatorics on Words
Sturmian & Episturmian Words
From Christoffel words to Sturmian words Sturmian words: Obtained *similarly* by replacing the line segment by a half-line: y = αx + ρ with irrational α ∈ (0, 1), ρ ∈ R. Example:
y=
√
5−1 2 x
−→ Fibonacci word a a a a
a
a
a
b
b
b
b
f = abaababaabaababaaba · · · (note: disregard 1st a in construction) Standard Sturmian word of slope Amy Glen (Reykjavík University)
√
5−1 2 ,
golden ratio conjugate
Palindromes in Number Theory
April 2009
26 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Historical notes Before the 20th century: J. Bernoulli, 1771 (Astronomy) A. Markoff, 1882 (continued fractions) E. Christoffel, 1871, 1888 (Cayley graphs)
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
27 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Historical notes Before the 20th century: J. Bernoulli, 1771 (Astronomy) A. Markoff, 1882 (continued fractions) E. Christoffel, 1871, 1888 (Cayley graphs) After the 20th century: J. Berstel, 1990 J.-P. Borel & F. Laubie, 1993
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
27 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Properties Examples Slope q/p L(p, q) U(p, q)
3/4 aababab bababaa
Amy Glen (Reykjavík University)
4/3 abababb bbababa
7/4 aabaabaabab babaabaabaa
Palindromes in Number Theory
5/7 aababaababab bababaababaa
April 2009
28 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Properties Examples Slope q/p L(p, q) U(p, q)
3/4 aababab bababaa
4/3 abababb bbababa
7/4 aabaabaabab babaabaabaa
5/7 aababaababab bababaababaa
Properties L(p, q) = awb ⇐⇒ U(p, q) = bwa
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
28 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Properties Examples Slope q/p L(p, q) U(p, q)
3/4 aababab bababaa
4/3 abababb bbababa
7/4 aabaabaabab babaabaabaa
5/7 aababaababab bababaababaa
Properties L(p, q) = awb ⇐⇒ U(p, q) = bwa |L(p, q)|a = p, |L(p, q)|b = q =⇒ |L(p, q)| = p + q
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
28 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Properties Examples Slope q/p L(p, q) U(p, q)
3/4 aababab bababaa
4/3 abababb bbababa
7/4 aabaabaabab babaabaabaa
5/7 aababaababab bababaababaa
Properties L(p, q) = awb ⇐⇒ U(p, q) = bwa |L(p, q)|a = p, |L(p, q)|b = q =⇒ |L(p, q)| = p + q L(p, q) is the reversal of U(p, q)
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
28 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words: Properties Examples Slope q/p L(p, q) U(p, q)
3/4 aababab bababaa
4/3 abababb bbababa
7/4 aabaabaabab babaabaabaa
5/7 aababaababab bababaababaa
Properties L(p, q) = awb ⇐⇒ U(p, q) = bwa |L(p, q)|a = p, |L(p, q)|b = q =⇒ |L(p, q)| = p + q L(p, q) is the reversal of U(p, q) Christoffel words are of the form awb, bwa where w is a palindrome.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
28 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words & palindromes
Theorem (folklore) A finite word w is a Christoffel word if and only if w = apb or w = bpa where p = Pal (v ) for some word v over {a, b}.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
29 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words & palindromes
Theorem (folklore) A finite word w is a Christoffel word if and only if w = apb or w = bpa where p = Pal (v ) for some word v over {a, b}. Pal is the iterated palindromic closure function: Pal (ε) = ε (empty word)
and Pal (wx) = (Pal (w )x)+
for any word w and letter x.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
29 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Christoffel words & palindromes
Theorem (folklore) A finite word w is a Christoffel word if and only if w = apb or w = bpa where p = Pal (v ) for some word v over {a, b}. Pal is the iterated palindromic closure function: Pal (ε) = ε (empty word)
and Pal (wx) = (Pal (w )x)+
for any word w and letter x. v + : Unique shortest palindrome beginning with v .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
29 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ =
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ =
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ =
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top s
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ =
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) =
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a a
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a a b a
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a a b a Pal (abc) = a b a c a b a
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a a b a Pal (abc) = a b a c a b a Pal (race) =
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a a b a Pal (abc) = a b a c a b a Pal (race) = rarcrarerarcrar
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a a b a Pal (abc) = a b a c a b a Pal (race) = rarcrarerarcrar L(5, 3) = aabaabab = aPal (aba)b
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Palindromic closure: Examples (race)+ = race car (tie)+ = tie it (tops)+ = top spot (ab)+ = aba Pal (aba) = a b a a b a Pal (abc) = a b a c a b a Pal (race) = rarcrarerarcrar L(5, 3) = aabaabab = aPal (aba)b L(7, 4) = aabaabaabab = aPal (abaa)b Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
30 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words: Palindromicity
Theorem (de Luca 1997) An infinite word s over {a, b} is a standard 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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
31 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words: Palindromicity
Theorem (de Luca 1997) An infinite word s over {a, b} is a standard 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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
∆: directive word of s.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
31 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Sturmian words: Palindromicity
Theorem (de Luca 1997) An infinite word s over {a, b} is a standard 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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
∆: directive word of s. Example: Fibonacci word is directed by ∆ = (ab)(ab)(ab) · · · .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
31 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
Amy Glen (Reykjavík University)
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = a
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = ab
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = aba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = abaa
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = abaaba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = abaabab
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = abaababaaba · · ·
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
Recall: Fibonacci word
a a a a
a
Line of slope
a
a
b
b
b
b √
5−1 2
−→ Fibonacci word
∆ = (ab)(ab)(ab) · · · −→ f = abaababaaba · · · Note: Palindromic prefixes have lengths (Fn+1 − 2)n≥1 = 0, 1, 3, 6, 11, 19, . . . where (Fn )n≥0 is the sequence of Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, . . . , defined by: F0 = F1 = 1, Fn = Fn−1 + Fn−2 for n ≥ 2. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
32 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word:
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r=a
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = ab
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = aba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abac
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacaba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacabaa
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacabaabacaba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacabaabacabab
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacabaabacababacabaabacaba
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacabaabacababacabaabacabac
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacabaabacababacabaabacabac abaabaca · · ·
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
33 / 48
Combinatorics on Words
Sturmian & Episturmian Words
A generalisation: Episturmian words {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 Pal (x1 x2 · · · xn ) = Pal (∆). n→∞
Example: ∆ = (abc)(abc)(abc) · · · directs the Tribonacci word: r = abacabaabacababacabaabacabac abaabaca · · ·
Note: Palindromic prefixes have lengths ((Tn+2 + Tn + 1)/2 − 2)n≥1 = 0, 1, 3, 7, 14, 27, 36 . . . where (Tn )n≥0 is the sequence of Tribonacci numbers 1, 1, 2, 4, 7, 13, 24, 44, . . . , defined by: T0 = T1 = 1, T2 = 2, Tn = Tn−1 + Tn−2 + Tn−3 Amy Glen (Reykjavík University)
Palindromes in Number Theory
for n ≥ 3. April 2009
33 / 48
Some Connections to Number Theory
Outline
1
Combinatorics on Words Sturmian & Episturmian Words
2
Some Connections to Number Theory Continued Fractions & Sturmian Words Palindromes & Diophantine Approximation Transcendental Numbers Miscellaneous
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
34 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Continued fractions Every irrational number α > 0 has a unique continued fraction expansion 1
α = [a0 ; a1 , a2 , a3 , . . .] = a0 +
1
a1 +
1 a3 + · · · where the ai are non-negative integers, called partial quotients, with a0 ≥ 0 & all other ai ≥ 1. The n-th convergent to α is the rational number: pn = [a0 ; a1 , a2 , . . . , an ], n ≥ 1. qn a2 +
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
35 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Continued fractions Every irrational number α > 0 has a unique continued fraction expansion 1
α = [a0 ; a1 , a2 , a3 , . . .] = a0 +
1
a1 +
1 a3 + · · · where the ai are non-negative integers, called partial quotients, with a0 ≥ 0 & all other ai ≥ 1. The n-th convergent to α is the rational number: pn = [a0 ; a1 , a2 , . . . , an ], n ≥ 1. qn Example: a2 +
√
= 0.61803 . . . = [0; 1, 1, 1, . . .] Golden ratio (conjugate): τ¯ = 1/τ = 5−1 2 1 , ... Convergents: 11 = 1, = 12 , 23 , 35 , 58 , . . . , FFn−1 1 n 1+ 1 Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
35 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Continued fractions Every irrational number α > 0 has a unique continued fraction expansion 1
α = [a0 ; a1 , a2 , a3 , . . .] = a0 +
1
a1 +
1 a3 + · · · where the ai are non-negative integers, called partial quotients, with a0 ≥ 0 & all other ai ≥ 1. The n-th convergent to α is the rational number: pn = [a0 ; a1 , a2 , . . . , an ], n ≥ 1. qn Example: a2 +
π = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, . . .] Convergents: 3, 22/7, 333/106, 355/113, . . . Note: 2[1, 1, 1, 3, 32] = 355/113 = 3.14159292 ≈ π . . . → v. good approx. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
35 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2
Amy Glen (Reykjavík University)
for n ≥ 1
Palindromes in Number Theory
−→
|sn | = Fn+1
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2 f = ab
Amy Glen (Reykjavík University)
for n ≥ 1
−→
|sn | = Fn+1
s1 , length F2 = 2
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2 f = aba
Amy Glen (Reykjavík University)
for n ≥ 1
−→
|sn | = Fn+1
s2 , length F3 = 3
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2 f = abaab
Amy Glen (Reykjavík University)
for n ≥ 1
−→
|sn | = Fn+1
s3 , length F4 = 5
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2 f = abaababa
Amy Glen (Reykjavík University)
for n ≥ 1
−→
|sn | = Fn+1
s4 , length F5 = 8
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2
f = abaababaabaab
Amy Glen (Reykjavík University)
for n ≥ 1
−→
|sn | = Fn+1
s5 , length F6 = 13
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2
f = abaababaabaababaababa
Amy Glen (Reykjavík University)
for n ≥ 1
−→
|sn | = Fn+1
s6 , length F7 = 21
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . Example: Recall the Fibonacci word is f := cα with α = [0; 1, 1, 1, 1, . . .]. s−1 = b, s0 = a,
and sn = sn−1 sn−2
for n ≥ 1
−→
|sn | = Fn+1
f = abaababaabaababaababa · · ·
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . In general: |sn | = qn+1 for all n
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . In general: |sn | = qn+1 for all n
sn = Pal (v )xy for some v ∈ {a, b}∗ and {x, y } = {a, b}
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . In general: |sn | = qn+1 for all n
sn = Pal (v )xy for some v ∈ {a, b}∗ and {x, y } = {a, b} cα = Pal (ad1 bd2 ad3 bd4 · · · )
Amy Glen (Reykjavík University)
E.g. f = Pal (abababa . . .)
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Continued Fractions & Sturmian Words
Standard Sturmian words: CF-based construction Suppose α = [0; d1 , d2 , d3 , . . .]. To the directive sequence (d1 , d2 , d3 , . . .), we associate a sequence (sn )n≥−1 of words defined by dn s−1 = b, s0 = a, sn = sn−1 sn−2 ,
n ≥ 1.
For all n ≥ 1, sn−1 is a prefix of sn and the standard Sturmian word cα corresponding to the line of slope α through (0, 0) is given by cα = limn→∞ sn . In general: |sn | = qn+1 for all n
sn = Pal (v )xy for some v ∈ {a, b}∗ and {x, y } = {a, b} cα = Pal (ad1 bd2 ad3 bd4 · · · )
E.g. f = Pal (abababa . . .)
Many nice combinatorial properties of cα are related to the CF of α. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
36 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Basics of Diophantine Approximation Diophantine Approximation is concerned with the approximation of real numbers by rational numbers.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
37 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Basics of Diophantine Approximation Diophantine Approximation is concerned with the approximation of real numbers by rational numbers. How good is an approximation of a real number ξ by a rational number p/q?
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
37 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Basics of Diophantine Approximation Diophantine Approximation is concerned with the approximation of real numbers by rational numbers. How good is an approximation of a real number ξ by a rational number p/q? Rudimentary measure: |ξ − p/q| → the smaller the better.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
37 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Basics of Diophantine Approximation Diophantine Approximation is concerned with the approximation of real numbers by rational numbers. How good is an approximation of a real number ξ by a rational number p/q? Rudimentary measure: |ξ − p/q| → the smaller the better.
A more sophisticated measure: Comparison of |ξ − p/q| to the size of q (in terms of some function φ(q)).
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
37 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Basics of Diophantine Approximation Diophantine Approximation is concerned with the approximation of real numbers by rational numbers. How good is an approximation of a real number ξ by a rational number p/q? Rudimentary measure: |ξ − p/q| → the smaller the better.
A more sophisticated measure: Comparison of |ξ − p/q| to the size of q (in terms of some function φ(q)).
Typically, it is asked whether or not an inequality of the form |ξ − p/q| < φ(q) has infinitely many rational solutions p/q.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
37 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Basics of Diophantine Approximation Diophantine Approximation is concerned with the approximation of real numbers by rational numbers. How good is an approximation of a real number ξ by a rational number p/q? Rudimentary measure: |ξ − p/q| → the smaller the better.
A more sophisticated measure: Comparison of |ξ − p/q| to the size of q (in terms of some function φ(q)).
Typically, it is asked whether or not an inequality of the form |ξ − p/q| < φ(q) has infinitely many rational solutions p/q. Relation to continued fractions: Best rational approximations to real numbers are produced by truncating their CF expansions.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
37 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Basics of Diophantine Approximation Diophantine Approximation is concerned with the approximation of real numbers by rational numbers. How good is an approximation of a real number ξ by a rational number p/q? Rudimentary measure: |ξ − p/q| → the smaller the better.
A more sophisticated measure: Comparison of |ξ − p/q| to the size of q (in terms of some function φ(q)).
Typically, it is asked whether or not an inequality of the form |ξ − p/q| < φ(q) has infinitely many rational solutions p/q. Relation to continued fractions: Best rational approximations to real numbers are produced by truncating their CF expansions. CF theory → for every irrational number ξ, the inequality |ξ − p/q| < 1/q 2 always has infinitely many rational solutions p/q. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
37 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromes & Diophantine Approximation
Roy 2003, 2004: Introduced a “palindromic prefix method” in the study of simultaneous approximation to a real number and its square.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
38 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromes & Diophantine Approximation
Roy 2003, 2004: Introduced a “palindromic prefix method” in the study of simultaneous approximation to a real number and its square. Roy’s work inspired Fischler (2006) to study infinite words with “abundant palindromic prefixes”.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
38 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromes & Diophantine Approximation
Roy 2003, 2004: Introduced a “palindromic prefix method” in the study of simultaneous approximation to a real number and its square. Roy’s work inspired Fischler (2006) to study infinite words with “abundant palindromic prefixes”. Also of interest in Physics in connection with the spectral theory of one-dimensional Schrödinger operators. [Hof, Knill, Simon 1995]
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
38 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromes & Diophantine Approximation
Roy 2003, 2004: Introduced a “palindromic prefix method” in the study of simultaneous approximation to a real number and its square. Roy’s work inspired Fischler (2006) to study infinite words with “abundant palindromic prefixes”. Also of interest in Physics in connection with the spectral theory of one-dimensional Schrödinger operators. [Hof, Knill, Simon 1995] Important notion is palindromic complexity – the number of distinct palindromic factors of each length.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
38 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromes & Diophantine Approximation
Roy 2003, 2004: Introduced a “palindromic prefix method” in the study of simultaneous approximation to a real number and its square. Roy’s work inspired Fischler (2006) to study infinite words with “abundant palindromic prefixes”. Also of interest in Physics in connection with the spectral theory of one-dimensional Schrödinger operators. [Hof, Knill, Simon 1995] Important notion is palindromic complexity – the number of distinct palindromic factors of each length. Fischler introduced palindromic prefix density . . .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
38 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density Let w = w1 w2 w3 · · · be an infinite word (with each wi a letter).
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
39 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density Let w = w1 w2 w3 · · · be an infinite word (with each wi a letter).
Let (ni )i ≥1 be the seq. of lengths of the palindromic prefixes of w. Note: (ni )i ≥1 is an increasing sequence if w begins with arbitrarily long palindromes.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
39 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density Let w = w1 w2 w3 · · · be an infinite word (with each wi a letter).
Let (ni )i ≥1 be the seq. of lengths of the palindromic prefixes of w. Note: (ni )i ≥1 is an increasing sequence if w begins with arbitrarily long palindromes. Fischler (2006): The palindromic prefix density of w is defined by ni +1 −1 dp (w) := lim sup ni i →∞ with dp (w) := 0 if w begins with only finitely many palindromes.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
39 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density Let w = w1 w2 w3 · · · be an infinite word (with each wi a letter).
Let (ni )i ≥1 be the seq. of lengths of the palindromic prefixes of w. Note: (ni )i ≥1 is an increasing sequence if w begins with arbitrarily long palindromes. Fischler (2006): The palindromic prefix density of w is defined by ni +1 −1 dp (w) := lim sup ni i →∞ with dp (w) := 0 if w begins with only finitely many palindromes. Note: 0 ≤ dp (w) ≤ 1 for any infinite word w.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
39 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density Let w = w1 w2 w3 · · · be an infinite word (with each wi a letter).
Let (ni )i ≥1 be the seq. of lengths of the palindromic prefixes of w. Note: (ni )i ≥1 is an increasing sequence if w begins with arbitrarily long palindromes. Fischler (2006): The palindromic prefix density of w is defined by ni +1 −1 dp (w) := lim sup ni i →∞ with dp (w) := 0 if w begins with only finitely many palindromes. Note: 0 ≤ dp (w) ≤ 1 for any infinite word w.
If w = v ∞ = vvvvv · · · (purely periodic), then 1 if v = pq for some palindromes p, q dp (w) = 0 otherwise. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
39 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density . . . Question: What is the maximal palindromic prefix density attainable by a non-periodic infinite word? Answer:
Theorem (Fischler 2006) For any infinite non-periodic word w, we have dp (w) ≤
Amy Glen (Reykjavík University)
Palindromes in Number Theory
1 τ
√ (= ( 5 − 1)/2).
April 2009
40 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density . . . Question: What is the maximal palindromic prefix density attainable by a non-periodic infinite word? Answer:
Theorem (Fischler 2006) For any infinite non-periodic word w, we have dp (w) ≤
1 τ
√ (= ( 5 − 1)/2).
Fischler’s bound is optimal . . .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
40 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindromic prefix density . . . Question: What is the maximal palindromic prefix density attainable by a non-periodic infinite word? Answer:
Theorem (Fischler 2006) For any infinite non-periodic word w, we have dp (w) ≤
1 τ
√ (= ( 5 − 1)/2).
Fischler’s bound is optimal . . . The Fibonacci word f = abaababaaba · · · , whose sequence of palindromic prefix lengths is given by: (ni )i ≥1 = (Fi +1 − 2)i ≥1 = 0, 1, 3, 6, 11, 19, 32, . . . ,
has maximal palindromic prefix density amongst non-periodic infinite words. That is: Fi +2 − 2 −1 = 1/τ. dp (f) = lim sup i →∞ Fi +1 − 2 Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
40 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindrome prefix density . . . There is an easy formula to compute dp (cα ). [de Luca 1997] Not so for standard episturmian words. But it can be verified that . . .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
41 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindrome prefix density . . . There is an easy formula to compute dp (cα ). [de Luca 1997] Not so for standard episturmian words. But it can be verified that . . . Any standard episturmian word satisfies ni +1 ≤ 2ni + 1 for any i. Recall: The Tribonacci word r = abacabaabacababacab · · · has palindromic prefix lengths Ti +2 + Ti + 1 (ni )i ≥1 = −2 = 0, 1, 3, 7, 14, 27, 36 . . . 2 i ≥1
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
41 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Palindrome prefix density . . . There is an easy formula to compute dp (cα ). [de Luca 1997] Not so for standard episturmian words. But it can be verified that . . . Any standard episturmian word satisfies ni +1 ≤ 2ni + 1 for any i. Recall: The Tribonacci word r = abacabaabacababacab · · · has palindromic prefix lengths Ti +2 + Ti + 1 (ni )i ≥1 = −2 = 0, 1, 3, 7, 14, 27, 36 . . . 2 i ≥1 Fischler 2006: Introduced a natural generalisation of standard episturmian words . . .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
41 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Fischler’s words with abundant palindromic prefixes Definition (Fischler 2006) An infinite word w is said to have abundant palindromic prefixes if the sequence (ni )i ≥1 is infinite and satisfies ni +1 ≤ 2ni + 1 for any i ≥ 1.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
42 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Fischler’s words with abundant palindromic prefixes Definition (Fischler 2006) An infinite word w is said to have abundant palindromic prefixes if the sequence (ni )i ≥1 is infinite and satisfies ni +1 ≤ 2ni + 1 for any i ≥ 1. Fischler gave an explicit construction of such words, as well as those which satisfy ni +1 ≤ 2ni + 1 for sufficiently large i.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
42 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Fischler’s words with abundant palindromic prefixes Definition (Fischler 2006) An infinite word w is said to have abundant palindromic prefixes if the sequence (ni )i ≥1 is infinite and satisfies ni +1 ≤ 2ni + 1 for any i ≥ 1. Fischler gave an explicit construction of such words, as well as those which satisfy ni +1 ≤ 2ni + 1 for sufficiently large i. Construction is similar to that of iterated palindromic closure Pal for standard episturmian words.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
42 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Fischler’s words with abundant palindromic prefixes Definition (Fischler 2006) An infinite word w is said to have abundant palindromic prefixes if the sequence (ni )i ≥1 is infinite and satisfies ni +1 ≤ 2ni + 1 for any i ≥ 1. Fischler gave an explicit construction of such words, as well as those which satisfy ni +1 ≤ 2ni + 1 for sufficiently large i. Construction is similar to that of iterated palindromic closure Pal for standard episturmian words. Any standard episturmian word has abundant palindromic prefixes, but not conversely.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
42 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
Fischler’s words with abundant palindromic prefixes Definition (Fischler 2006) An infinite word w is said to have abundant palindromic prefixes if the sequence (ni )i ≥1 is infinite and satisfies ni +1 ≤ 2ni + 1 for any i ≥ 1. Fischler gave an explicit construction of such words, as well as those which satisfy ni +1 ≤ 2ni + 1 for sufficiently large i. Construction is similar to that of iterated palindromic closure Pal for standard episturmian words. Any standard episturmian word has abundant palindromic prefixes, but not conversely. Example: (abcacba)∞ = abcacbaabcacbaabcacba · · · has abundant palindromic prefixes, but it is not standard episturmian. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
42 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words. Characteristic property: All ‘complete returns’ to palindromes are palindromes.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words. Characteristic property: All ‘complete returns’ to palindromes are palindromes. Examples aaaaaa · · ·
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words. Characteristic property: All ‘complete returns’ to palindromes are palindromes. Examples aaaaaa · · ·
abbbbbb · · ·
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words. Characteristic property: All ‘complete returns’ to palindromes are palindromes. Examples aaaaaa · · ·
abbbbbb · · ·
abaabaaabaaaab · · ·
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words. Characteristic property: All ‘complete returns’ to palindromes are palindromes. Examples aaaaaa · · ·
abbbbbb · · ·
abaabaaabaaaab · · ·
(abcba)(abcba)(abcba) · · ·
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words. Characteristic property: All ‘complete returns’ to palindromes are palindromes. Examples aaaaaa · · ·
abbbbbb · · ·
abaabaaabaaaab · · ·
(abcba)(abcba)(abcba) · · ·
Sturmian and episturmian words
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Palindromes & Diophantine Approximation
A further generalisation: Rich words Glen-Justin (2007): Initiated a unified study of finite and infinite words that are characterized by containing the maximal number of distinct palindromes, called rich words. Characteristic property: All ‘complete returns’ to palindromes are palindromes. Examples aaaaaa · · ·
abbbbbb · · ·
abaabaaabaaaab · · ·
(abcba)(abcba)(abcba) · · ·
Sturmian and episturmian words Infinite words with abundant palindromic prefixes Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
43 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions Long-standing Conjecture (Khintchine 1949) The CF expansion of an irrational algebraic real number α is either eventually periodic (iff α is a quadratic irrational) or it contains arbitrarily large partial quotients.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
44 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions Long-standing Conjecture (Khintchine 1949) The CF expansion of an irrational algebraic real number α is either eventually periodic (iff α is a quadratic irrational) or it contains arbitrarily large partial quotients. Alternatively: An irrational number whose CF expansion has bounded partial quotients is either quadratic or transcendental.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
44 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions Long-standing Conjecture (Khintchine 1949) The CF expansion of an irrational algebraic real number α is either eventually periodic (iff α is a quadratic irrational) or it contains arbitrarily large partial quotients. Alternatively: An irrational number whose CF expansion has bounded partial quotients is either quadratic or transcendental. Liouville (1844): Transcendental CF’s whose sequences of partial quotients grow very fast (too fast to be algebraic)
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
44 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions Long-standing Conjecture (Khintchine 1949) The CF expansion of an irrational algebraic real number α is either eventually periodic (iff α is a quadratic irrational) or it contains arbitrarily large partial quotients. Alternatively: An irrational number whose CF expansion has bounded partial quotients is either quadratic or transcendental. Liouville (1844): Transcendental CF’s whose sequences of partial quotients grow very fast (too fast to be algebraic) Transcendental CF’s with bounded partial quotients: Maillet (1906) Baker (1962, 1964) Shallit (1979) Davison (1989) Queffélec (1998) Allouche, Davison, Queffélec, Zamboni (2001) Adamczewski-Bugeaud (2005) Amy Glen (Reykjavík University)
9 > > > > > > > =
transcendence criteria from DA
> > > > > > > ;
Palindromes in Number Theory
April 2009
44 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental. More generally:
Theorem (Allouche-Davison-Queffélec-Zamboni 2001) Any Sturmian continued fraction – of which the partial quotients forms a Sturmian word on two distinct positive integers – is transcendental.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental. More generally:
Theorem (Allouche-Davison-Queffélec-Zamboni 2001) Any Sturmian continued fraction – of which the partial quotients forms a Sturmian word on two distinct positive integers – is transcendental. Proved by showing that Sturmian continued fractions admit very good approximations by quadratic real numbers.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental. More generally:
Theorem (Allouche-Davison-Queffélec-Zamboni 2001) Any Sturmian continued fraction – of which the partial quotients forms a Sturmian word on two distinct positive integers – is transcendental. Proved by showing that Sturmian continued fractions admit very good approximations by quadratic real numbers. In particular, they used the fact that any Sturmian word begins with arbitrarily long squares (words of the form XX = X 2 ). Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental. More generally:
Theorem (Allouche-Davison-Queffélec-Zamboni 2001) Any Sturmian continued fraction – of which the partial quotients forms a Sturmian word on two distinct positive integers – is transcendental. Proved by showing that Sturmian continued fractions admit very good approximations by quadratic real numbers. In particular, they used the fact that any Sturmian word begins with arbitrarily long squares (words of the form XX = X 2 ). Example: f = aba · ababaabaababaababaabaababaaba · · · Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental. More generally:
Theorem (Allouche-Davison-Queffélec-Zamboni 2001) Any Sturmian continued fraction – of which the partial quotients forms a Sturmian word on two distinct positive integers – is transcendental. Proved by showing that Sturmian continued fractions admit very good approximations by quadratic real numbers. In particular, they used the fact that any Sturmian word begins with arbitrarily long squares (words of the form XX = X 2 ). Example: f = abaab · abaabaababaababaabaababaaba · · · Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental. More generally:
Theorem (Allouche-Davison-Queffélec-Zamboni 2001) Any Sturmian continued fraction – of which the partial quotients forms a Sturmian word on two distinct positive integers – is transcendental. Proved by showing that Sturmian continued fractions admit very good approximations by quadratic real numbers. In particular, they used the fact that any Sturmian word begins with arbitrarily long squares (words of the form XX = X 2 ). Example: f = abaababa · abaababaababaabaababaaba · · · Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions: Examples Let ξa,b := [0; a, b, a, a, b, a, b, a, a, b, a, . . .] where the sequence of partial quotients is the Fibonacci word on positive integers a, b. Any Fibonacci continued fraction is transcendental. More generally:
Theorem (Allouche-Davison-Queffélec-Zamboni 2001) Any Sturmian continued fraction – of which the partial quotients forms a Sturmian word on two distinct positive integers – is transcendental. Proved by showing that Sturmian continued fractions admit very good approximations by quadratic real numbers. In particular, they used the fact that any Sturmian word begins with arbitrarily long squares (words of the form XX = X 2 ). Example: f = abaababaabaab · abaababaabaababaaba · · · Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
45 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions . . . In fact: Any irrational number having a CF expansion with sequence of partial quotients forming a recurrent rich infinite word is either quadratic or transcendental by . . .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
46 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions . . . In fact: Any irrational number having a CF expansion with sequence of partial quotients forming a recurrent rich infinite word is either quadratic or transcendental by . . .
Theorem (Adamczewski-Bugeaud 2007) If the sequence of partial quotients (an )n≥0 in the CF expansion of a positive irrational number ξ := [a0 ; a1 , a2 , . . . , an , . . .] begins with arbitrarily long palindromes, then ξ is either quadratic or transcendental.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
46 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions . . . In fact: Any irrational number having a CF expansion with sequence of partial quotients forming a recurrent rich infinite word is either quadratic or transcendental by . . .
Theorem (Adamczewski-Bugeaud 2007) If the sequence of partial quotients (an )n≥0 in the CF expansion of a positive irrational number ξ := [a0 ; a1 , a2 , . . . , an , . . .] begins with arbitrarily long palindromes, then ξ is either quadratic or transcendental. Palindromes must begin at a0 .
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
46 / 48
Some Connections to Number Theory
Transcendental Numbers
Transcendental continued fractions . . . In fact: Any irrational number having a CF expansion with sequence of partial quotients forming a recurrent rich infinite word is either quadratic or transcendental by . . .
Theorem (Adamczewski-Bugeaud 2007) If the sequence of partial quotients (an )n≥0 in the CF expansion of a positive irrational number ξ := [a0 ; a1 , a2 , . . . , an , . . .] begins with arbitrarily long palindromes, then ξ is either quadratic or transcendental. Palindromes must begin at a0 . Proof of theorem rests on Schmidt’s Subspace Theorem (1972).
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
46 / 48
Some Connections to Number Theory
Miscellaneous
Further work Continued fractions provide a strong link between: arithmetic/Diophantine properties of an irrational number α, and symbolic/combinatorial properties of Sturmian words of slope α.
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
47 / 48
Some Connections to Number Theory
Miscellaneous
Further work Continued fractions provide a strong link between: arithmetic/Diophantine properties of an irrational number α, and symbolic/combinatorial properties of Sturmian words of slope α.
Strict episturmian words (or Arnoux-Rauzy sequences) naturally generalise and extend this rich interplay. [Rauzy 1982, Arnoux-Rauzy 1991]
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
47 / 48
Some Connections to Number Theory
Miscellaneous
Further work Continued fractions provide a strong link between: arithmetic/Diophantine properties of an irrational number α, and symbolic/combinatorial properties of Sturmian words of slope α.
Strict episturmian words (or Arnoux-Rauzy sequences) naturally generalise and extend this rich interplay. [Rauzy 1982, Arnoux-Rauzy 1991] Recall: Directive word of cα is determined by the CF of α. That is: If α = [0; d1 , d2 , d3 , d4 . . .], then cα = Pal (ad1 bd2 ad3 bd4 · · · ).
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
47 / 48
Some Connections to Number Theory
Miscellaneous
Further work Continued fractions provide a strong link between: arithmetic/Diophantine properties of an irrational number α, and symbolic/combinatorial properties of Sturmian words of slope α.
Strict episturmian words (or Arnoux-Rauzy sequences) naturally generalise and extend this rich interplay. [Rauzy 1982, Arnoux-Rauzy 1991] Recall: Directive word of cα is determined by the CF of α. That is: If α = [0; d1 , d2 , d3 , d4 . . .], then cα = Pal (ad1 bd2 ad3 bd4 · · · ). Likewise, the directive word of a k-letter Arnoux-Rauzy word is determined by a multi-dimensional continued fraction expansion of the frequencies of the first k − 1 letters. [Zamboni 1998, Wozny-Zamboni 2001]
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
47 / 48
Some Connections to Number Theory
Miscellaneous
Further work Continued fractions provide a strong link between: arithmetic/Diophantine properties of an irrational number α, and symbolic/combinatorial properties of Sturmian words of slope α.
Strict episturmian words (or Arnoux-Rauzy sequences) naturally generalise and extend this rich interplay. [Rauzy 1982, Arnoux-Rauzy 1991] Recall: Directive word of cα is determined by the CF of α. That is: If α = [0; d1 , d2 , d3 , d4 . . .], then cα = Pal (ad1 bd2 ad3 bd4 · · · ). Likewise, the directive word of a k-letter Arnoux-Rauzy word is determined by a multi-dimensional continued fraction expansion of the frequencies of the first k − 1 letters. [Zamboni 1998, Wozny-Zamboni 2001] Deep properties studied in the framework of dynamical systems, with connections to geometrical realisations such as Rauzy fractals. Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
47 / 48
Some Connections to Number Theory
Miscellaneous
Thank you!
Amy Glen (Reykjavík University)
Palindromes in Number Theory
April 2009
48 / 48
