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.
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
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,
- 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.
(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 9 notes in pdf format.
- 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.
Slides for Lecture 10
- 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.
Slides for Lecture 11
- 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.
Slides for Lecture 12
- Lecture 13, February 25 2020. k-regular sequences: their
closure properties, and lots of examples. Solutions to assignment
2 are available on LEARN now.
Notes for Lecture 13
- 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.
Slides for Lecture 14
- 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.
Notes for Lecture 15
- 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.
Notes for Lecture 16
- 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
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).)
Notes for Lecture 17
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.
Open Problem 14.
- 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.
Notes for Lecture 18
- 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 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.