CS 860: Automatic Sequences
University of Waterloo: Winter 2017
Time: Meets Tuesday and Thursday, 10:30-11:50 AM in DC 2568
Jeffrey Shallit, DC 3134, x 34804, shallit at uwaterloo.ca. Office
hours: Mondays from 11 AM to Noon.
There is a textbook for the course, the book
by Allouche and Shallit, which will give you some idea of what we will
cover. It is now available from the University bookstore.
Errata for the course textbook can be found
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 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
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.
There will be 3 problem sets, with problems of varying difficulty.
There will be a final course project. This can be
Here is information about the course project.
By January 31 you should hand in a 1-page sheet of paper with your name
and what you intend to do.
- 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
- 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
- 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.
During the course, I will mention many interesting open problems.
Solve any of them for bonus marks in the course.
Here is the problems list.
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.
Tentative outline of the course
- Week 1: Introduction to automatic sequences. Course organization.
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
- 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 summaries are here.
- Problem Set 1, distributed Sunday January 15;
due Tuesday January 31 in class.
- Problem Set 2, distributed Tuesday January 31;
due Tuesday February 14 in class.
Some papers relevant to the course
- 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.
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.
- Expansions of algebraic numbers, by Yann Bugeaud. Final version appeared in
Four Faces of Number Theory, European Mathematical Society,
2015, pp. 31-75.
Some papers arising from previous graduate courses
- Soroosh Yazdani,
Multiplicative functions and k-automatic sequences,
Journal de théorie des nombres de Bordeaux 13 (2001)
- Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, and
Jeffrey Shallit, Remarks on privileged words,
Internat. J. Found. Comput. Sci. 27 (2016), 431-442.
- 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.
- 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 Math. 309 (2009), 6245-6254.
- Yu-Hin Au, Aaron Robertson, and Jeffrey Shallit,
van der Waerden's theorem and avoidability in words.
Integers 11 (2011), Paper A7, 15 pp.
- Yu-Hin Au, Generalized de Bruijn words for primitive words and powers,
Discrete Math. 338 (2015), 2320-2331.