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. It will also be worth 50% of the course mark. 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. (Revised on January 28 2020)

- Lecture 7, Tuesday, January 28 2020.
Proving a sequence not 2-automatic. Sequences that are
k
^{i}-automatic are also k^{j}-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.
- 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.

- Cobham's original paper
- Semenov's paper
- Jason Bell's paper extending Cobham to k-regular sequences
- Durand's paper extending Cobham to a larger class of morphic words
- Byszewski-Konieczny's paper on the density version of Cobham
- Byszewski-Konieczny-Krawczyk's paper on the factors in common between two automatic sequences
- Mol-Rampersad-Shallit-Stipulanti's paper on longest agreeing prefix between two automatic sequences

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

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