CS 860: Automatic Sequences
University of Waterloo: Winter 2020
Time: Meets Tuesday and Thursday, 1:00 PM - 2:20 PM in DC 2568
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.
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 will be 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
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.
- 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
Solve any of them for bonus marks in the course.
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.
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 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
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 1 notes in pdf format.
- 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
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
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,
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
- Lecture 6, Thursday, January 23 2020.
The Tower of Hanoi problem. Closure properties of automatic
Lecture 6 notes in pdf format.
- Problem Set 1, handed out January 16 2020; due January 30 2020.
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 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)
- 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.
- Yu-Hin Au, Aaron Robertson, and Jeffrey Shallit,
Van der Waerden's theorem and avoidability in words,
Integers 11 (2011), 61-76.
- 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.
- 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,
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.