Errata for the course textbook can be found
here.
**If you find a new, previously unreported error, report it to the instructor
to get a bonus point in your course mark (subject to approval).**

- automatic sequences
- fixed points of morphisms
- relationship between automatic sequences and algebra over a finite field
- automatic real numbers
- frequency and entropy
- transcendence theory of real numbers
- Cobham's big theorem
- combinatorics on words
- relationship between automatic sequences and logic
- k-regular sequences and combinatorial enumeration

There will be a final course project. This can be

- reading a paper or papers from the literature, writing a 5-15 page report on them, and presenting them in class in a 15-30 minute presentation; or
- working on an open research problem or problems, writing a 5-15 page report, and presenting your results in class in a 15-30 minute presentation; or
- writing or re-writing Wikipedia pages on various topics discussed in class (a list will be provided). This option is available for those who are a bit presentation-phobic.

There will be no midterm or final.

- Week 1: Introduction to automatic sequences. Course organization.
Base-
*k*representation. Automata (DFA, DFAO, NFA). Transducers. Examples of automatic sequences. The Thue-Morse sequence. The Rudin-Shapiro sequence. Finite-state functions. Robustness of the definition of automatic sequence. The Kolakoski sequence. - Week 2: Morphisms: uniform and non-uniform. The infinite
Fibonacci word. Cobham's little theorem. Example: the tower of Hanoi.
The
*k*-kernel. Closure properties of automatic sequences. - Week 3: Paperfolding and paperfolding sequences. Connection to continued fractions. Introduction to Christol's theorem.
- Week 4: Proof of Christol's theorem. Transcendence in finite characteristic. Transcendence of the finite field analogue of π. Sturmian and characteristic words.
- Week 5: the logical approach to automatic sequences. Synchronized
sequences. Using the
`Walnut`automatic theorem-proving software. - Week 6:
*k*-regular sequences. Examples and applications. Basic results. Using`Walnut`with k-regular sequences. - Week 7: automatic real numbers. Transcendence. Subword complexity. Automatic sets of rational numbers.
- Week 8: Cobham's big theorem. Applications. General (non-uniform) morphisms. Frequency of letters. Return words.
- Week 9: TBA
- Weeks 10-12: student presentations.

- Lecture 1, Tuesday, January 7 2020. What is an automatic
sequence? Notation. Introduction to what we will cover in the
course: computational, logical, algebraic, combinatorial, and
number-theoretic properties of automatic sequences and their
generalizations.

Open Problem #1: Is the first-order logical theory FO(**N**, +, P_{2}, P_{3}) decidable? Here P_{k}is the predicate "is a power of k".

Open Problem #2: are the binary or decimal expansions of π, e, or log 2 automatic sequences? - Lecture 2, Thursday, January 9 2020. Various kinds of
representations of numbers: ordinary base-k representation,
representations in negative bases, Fibonacci representation,
greedy representations, etc. Formal definition of automatic
sequences. Robustness of the definition of automatic
sequence.
Lecture 2 notes in pdf format.

- Lecture 3, Tuesday, January 14 2020. Proof that if
*f*is a finite-state function, so is*f*^{R}defined by*f*^{R}(w) =*f*(w). Relationship between DFAO, DFA, regular languages, and regular expressions. Morphisms. Prolongable morphisms. Uniform morphisms. Fixed points of prolongable morphisms. Cobham's little theorem (statement).Lecture 3 notes in pdf format.

- Lecture 4, Thursday, January 16 2020. Proof of Cobham's little
theorem. Example: the Rudin-Shapiro sequence expressed as image
of fixed point of morphism. The k-kernel. Eilenberg's theorem: a
sequence is k-automatic iff the k-kernel is finite. Proof of
the theorem. A heuristic procedure to determine if a sequence
is k-automatic. The paperfolding sequence. The sequence (s(n)) of run
lengths of the Thue-Morse sequence.
Open Problem #3:
why do some
of the sequences in the 2-kernel of (s(n)) agree for so long,
without being identical?
Lecture 4 notes in pdf format.

- Lecture 5, Tuesday, January 21 2020. More on paperfolding.
Continued fractions. The folding lemma.
Relationship between paperfolding and
continued fractions.
Lecture 5 notes in pdf format.

Here is some Maple code that you can use to expand rational functions into continued fractions. The two main functions are

`cfps(p,x)`, which expands a rational function p (i.e., an approximation to Laurent series in x^{-1}) as a continued fraction, and`cvgts(L)`, which converts the list L of partial quotients to a matrix giving the numerators and denominators of the last and next-to-last convergents. Try, for example,read(cfs): cfps(x^(-1)+x^(-2)+x^(-4),x); cvgts(%);

If you want to expand a rational function p as a power series in x^{-1}, then use`taylor(p, x=infinity, n)`to get the first n terms. - Lecture 6, Thursday, January 23 2020.
The Tower of Hanoi problem. Closure properties of automatic
sequences. Transducers.
Lecture 6 notes in pdf format.

- Problem Set 1, handed out January 16 2020; due January 30 2020.

- What is an automatic sequence?, by Eric Rowland,
*Notices of the AMS***62**(2015), 274-276. - Number theory and formal languages, by Jeffrey Shallit, in
*Emerging Applications of Number Theory*, Vol. 109 of IMA Volumes in Mathematics and its Applications, pp. 547-570. - The
ubiquitous Prouhet-Thue-Morse sequence, by Jeffrey Shallit, in C.
Ding. T. Helleseth, and H. Niederreiter, eds.,
*Sequences and Their Applications: Proceedings of SETA '98*, Springer-Verlag, 1999, pp. 1-16. - Expansions of algebraic numbers, by Yann Bugeaud. Final version appeared in
*Four Faces of Number Theory*, European Mathematical Society, 2015, pp. 31-75.

- Soroosh Yazdani,
Multiplicative functions and
*k*-automatic sequences,*Journal de théorie des nombres de Bordeaux***13**(2001) 651-658. - E. Grant, J. Shallit, and T. Stoll,
Bounds for the discrete correlation of infinite sequences on
*k*symbols and generalized Rudin-Shapiro sequences.*Acta Arith.***140**(2009), 345-368. - Mathieu Guay-Paquet and Jeffrey Shallit,
Avoiding squares and overlaps over the natural numbers.
*Discrete Mathematics***309**(2009), 6245-6254. [link] - Yu-Hin Au, Aaron Robertson, and Jeffrey Shallit,
Van der Waerden's theorem and avoidability in words,
*Integers***11**(2011), 61-76. [link] - Chen Fei Du, Jeffrey Shallit, and Arseny Shur,
Optimal bounds for the similarity density of the Thue-Morse word
with overlap-free and 7/3-power-free infinite binary words,
*Internat. J. Found. Comput. Sci.***26**(2015), 1147-1165. - Yu-Hin Au, Generalized de Bruijn words for primitive words and powers,
*Discrete Math.***338**(2015), 2320-2331. - Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, and
Jeffrey Shallit, Remarks on privileged words,
*Internat. J. Found. Comput. Sci.***27**(2016), 431-442. - Chuan Guo, Jeffrey Shallit, Arseny M. Shur,
Palindromic rich words and run-length encodings,
*Information Processing Letters***116**(2016) 735-738. - Yu Hin (Gary) Au, Christopher Drexler-Lemire, and Jeffrey Shallit,
"Notes and note pairs in Norgard's infinity series",
*J. of Mathematics and Music***11**(1) (2017) 1-19. DOI: here. - Samin Riasat, Infinite products involving binary digit sums,
in D. Marc Kilgour, Herb Kunze, Roman Makarov, Roderick Melnik, Xu Wang,
eds.,
*Recent Advances in Mathematical and Statistical Methods: IV AMMCS*, Springer, 2018, pp. 59-68. - Jean-Paul Allouche, Samin Riasat, Jeffrey Shallit:
More Infinite Products: Thue-Morse and the Gamma function,
Ramanujan J.
**49**(2019), 115-128. - Lukas Fleischer, Samin Riasat, Jeffrey Shallit, New Bounds on Antipowers in Binary Words, arxiv preprint, December 17 2019.
- Aseem R. Baranwal, Jeffrey Shallit,
Critical exponent
of infinite balanced words via the Pell number system,
arxiv Preprint, February 1 2019.
In Mercas R., Reidenbach D. (eds.)
*Combinatorics on Words. WORDS 2019.*Lecture Notes in Computer Science, vol. 11682, Springer, 2019, pp. 80-92. Available here.