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:


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