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 AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 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 AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 2/48 CombinatoricsonWords Outline 1 Combinatorics on Words Sturmian & Episturmian Words 2 Some Connections to Number Theory Continued Fractions & Sturmian Words Palindromes & Diophantine Approximation Transcendental Numbers Miscellaneous AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 3/48 CombinatoricsonWords Starting point: Combinatorics on words Number Theory Probability Theory Discrete Geometry DynamDiicscalr eStyes tems Combinatorics on Words ComThpueoterre tSicciaeln ce Topology Algorithmics Theoretical Physics Automata Theory Computability Codes Biology Logic DNA sequencing, Patterns algebra Free Groups, Semigroups Matrices Representations Burnside Problems AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 4/48 CombinatoricsonWords Starting point: Combinatorics on words Number Theory Probability Theory Discrete Geometry DynamDiicscalr eStyes tems Combinatorics on Words ComThpueoterre tSicciaeln ce Topology Algorithmics Theoretical Physics Automata Theory Computability Codes 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 (alphabet). A AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 4/48 CombinatoricsonWords Starting point: Combinatorics on words Number Theory Probability Theory Discrete Geometry DynamDiicscalr eStyes tems Combinatorics on Words ComThpueoterre tSicciaeln ce Topology Algorithmics Theoretical Physics Automata Theory Computability Codes 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 (alphabet). A Example with = a,b,c : w = abca, w = abcaabcaabca ∞ A { } ··· AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 4/48 CombinatoricsonWords Combinatorics on words: A brief history Relatively new area of Discrete Mathematics AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 5/48 CombinatoricsonWords Combinatorics on words: A brief history Relatively new area of Discrete Mathematics Early 1900’s: First investigations by Axel Thue (repetitions in words) AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 5/48 CombinatoricsonWords 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. AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 5/48 CombinatoricsonWords 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. AmyGlen (ReykjavíkUniversity) PalindromesinNumberTheory April2009 5/48