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.

*Last modified: Wed Jun 13 08:53:29 2001
ajh@uiuc.edu
*