## Time: Meets Tuesday and Thursday, 1:00 PM - 2:20 PM in DC 2568

### Instructor

Jeffrey Shallit, DC 3134, x 34804, shallit at uwaterloo.ca. Office hours: 2:30 - 3:20 PM Wednesdays, or by appointment, or when office door is open. If office door is closed, please don't knock!

### Keeping in touch

We will use Piazza for course announcements.

### Textbook

There is a textbook for the course, the book Automatic Sequences, by Allouche and Shallit, which will give you some idea of what we will cover. It will be available from the University bookstore.

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).

### Course Description

Automatic sequences are sequences that lie in between the most ordered sequences (ultimately periodic sequences) and the least ordered sequences (random sequences). They are simple in many ways; yet surprisingly subtle in their properties. In this course, you will see definitions and examples of these sequences, and the many places they occur in mathematics and computer science. The relationship between automatic sequences and other areas of mathematics, including combinatorics, algebra, number theory, and logic, will be explored. Students will get to see many open problems, some of which are quite accessible. (Several published papers arose from previous versions of the course.) Some of the topics we will cover include:
• 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

### Prerequisites

General mathematical sophistication is the most important prerequisite. You should be very comfortable with formal mathematical proofs, especially proofs by induction. A knowledge of basic automata theory at the level of Waterloo's CS 360 or 365 would be helpful, but not essential. Knowledge of basic algebra (groups, rings, fields) at the level of Waterloo's PMATH 347/348 would be helpful, but not essential. Knowledge of basic combinatorics (generating functions, etc.) at the level of Waterloo's MATH 239/249 and CO 330 would be helpful, but not essential.

### Evaluation

There will be 3 problem sets, with problems of varying difficulty. They are worth 50% of the course mark.

There will be a final course project. It will also be worth 50% of the course mark. This can be

1. 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
2. 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
3. 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.
Information about the course project is here. The important dates are: choose project by Thursday, February 6 2020, and hand in a 1-page sheet with your project and a selection of references then. Present project in class in the last three weeks; hand in written portion by last day of class. More details about the oral presentation, including how you will be evaluated, are here.

There will be no midterm or final.

### Open problems

During the course, I will mention many interesting open problems. Solve any of them for bonus marks in the course.

### Sequences

A basic tool that everybody in the course should know about is the On-Line Encyclopedia of Integer Sequences, available at https://oeis.org. If you explore a sequence that does not appear there, please submit it. You can gain bonus points for submitting interesting sequences.

### Tentative outline of the course

• 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.

### Lectures

• 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, +, P2, P3) decidable? Here Pk 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 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 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 5, Tuesday, January 21 2020. More on paperfolding. Continued fractions. The folding lemma. Relationship between paperfolding and continued fractions.

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. (Revised on January 28 2020)

• Lecture 7, Tuesday, January 28 2020. Proving a sequence not 2-automatic. Sequences that are ki-automatic are also kj-automatic. Introduction to formal power series over a finite field. Lots of examples! Statement of Christol's theorem. Open Problem #4: from the open problems page: the Endrullis-Hendriks transducer problem.

Lecture 7 notes in pdf format. (Updated Thursday January 30 at 5:00 AM.)

• Lecture 8, Thursday, January 30 2020. Christol's theorem: proof and applications (sections 12.2, 12.3, 12.4 of the course text). The proof in the course text has some minor errors, which are corrected in the handwritten lecture notes.

Solutions to Problem Set 1 are now available on LEARN.

Lecture 8 notes in pdf format. (Updated Thursday January 30 at 2:45 PM).

• Lecture 9, February 4 2020. Applications of Christol's theorem. The Carlitz zeta function. Transcendence of the formal series analogue of π. Application to transcendence over Q(x). Theta series.

• Lecture 10, February 6 2020. Proof of Cobham's Theorem 8. Introduction to the "logical approach" to automatic sequences. There is the (very rough) draft of a 200+-page text on these ideas available on LEARN.

• Lecture 11, February 11 2020. More on the "logical approach" to automatic sequences. Problem Set 2 is now available; it is due in two weeks.

• Lecture 12, February 13 2020. More on the "logical approach" to automatic sequences. We mentioned many open problems, numbered 5 to 12, on the problems page.

• Lecture 13, February 25 2020. k-regular sequences: their closure properties, and lots of examples. Solutions to assignment 2 are available on LEARN now.

• Lecture 14, February 27 2020. More on the "logical" approach to automatic sequences. k-synchronized sequences. Proving that subword complexity is k-synchronized. Here is the predicate for Thue-Morse showing that subword complexity is synchronized. We continued with the slides for Lecture 12 (linked above) and started the following set of slides.

• Lecture 15, March 3 2020. Cobham's big theorem: if a sequence is k-automatic and l-automatic, for k and l multiplicatively independent, then it is ultimately periodic.

• Lecture 16, March 5 2020. Generalizations of Cobham's theorem. Introduction to automatic real numbers. Proof that the Lehr space L(k,b) is a Q-vector space.

Here are links to some of the papers mentioned in today's lecture. They should work if you are on campus, or signed into the UW library.

• Lecture 17, March 10 2020. I handed back the marked assignment #2. Proof that automatic reals are either rational or transcendental. My notes are based on this survey paper of Bugeaud, but I have simplified the proof quite a bit, at the cost of being a little less general. (Bugeaud's proof works for any sequence of subword complexity O(n).)

Open problems: are any of the classical transcendental numbers, like π, e, ln 2, etc., automatic numbers? Probably not, but no one currently knows how to prove it.

• Lecture 18, March 12 2020. Did the proof that L(k,b) is not closed under product (from notes for Lecture 16). Began discussion of Sturmian words and Ostrowski numeration.

### Problem Sets

• Problem Set 1, handed out January 16 2020; due January 30 2020. Solutions are available on LEARN.

• Problem Set 2, handed out February 11 2020; due February 25 2020. Solutions are now available on LEARN.

• Problem Set 3, handed out March 5 2020; due March 24 2020.

### Some papers written by students in previous graduate courses similar to this one

• 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.