Short Course I: Finite automata in number theory June 12 - June 22, 11 am - noon, Room 159 Altgeld Hall

Course Description: Consider the sequence 0110100110010110... whose n'th term is defined as 1 if n has an odd number of 1's in its binary expansion, and 0 otherwise (starting with n=0). This sequence, called the Thue-Morse sequence, is an example of a larger class of sequences that can be generated by a so-called "finite automata", and which have a number of remarkable properties and arise in surprising variety of contexts. For example, the same sequence can be obtained by the following, seemingly very different construction: Starting with the string 0, replace at each step 0 by 01 and 1 by 10. This generates the sequences 01, 0110, 01101001, 0110100110010110, etc., which converge to the Thue-Morse sequence. Yet another, completely different, method of generating the Thue-Morse sequence is through paper folding, as explained in the article referenced below. There are many questions that one can ask about such 0-1 sequences. For example, does the sequence contain 0's and 1's in approximately equal proportions? More precisely, given a (large) N, how large can the excess of 0's over 1's (or 1's over 0's) be among the first N elements of the sequence? If one considers subsequences indexed by an arithmetic progression (e.g., the subsequence consisting of the 1st, 4th, 7th, etc. elements), is it still true that 0's and 1's occur equally often? What about more complicated subsequences, such as the terms indexed by primes, or by squares?

References: Of the many articles that have been written on this subject, here are three that are very readable and which approach the topic from quite different angles:

• J.-P. Allouche, Finite Automata in Number Theory (in French), Exposit. Math. 5 (1987). A general survey, emphasizing the "automata" aspect.
• J. Dekking et al., Folds!, Math. Intelligencer 4 (1982). A series of 4 articles on paperfolding, which, as mentioned, leads to sequences of the type described above.
• J. Brillhart and P. Morton, Amer. Math. Monthly 103 (1996), 854-869. A nice "case study in mathematical research", suitable for undergraduates. This paper might lead to some research projects.