CS 860: Automatic Sequences

University of Waterloo: Winter 2017

Time: Meets Tuesday and Thursday, 10:30-11:50 AM in DC 2568

 

Instructor

Jeffrey Shallit, DC 3134, x 34804, shallit at uwaterloo.ca. Office hours: Mondays from 11 AM to Noon.

Textbook

There is a textbook for the course, the book Automatic Sequences, by Allouche and Shallit, which will give you some idea of what we will cover. It is now available from the University bookstore.

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

Course Description

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:

Prerequisites

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.

Evaluation

There will be 3 problem sets, with problems of varying difficulty.

There will be a final course project. This can be

  1. 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
  2. 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
  3. 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.
Here is information about the course project. By January 31 you should hand in a 1-page sheet of paper with your name and what you intend to do.

There will be no midterm or final.

Open problems

During the course, I will mention many interesting open problems. Solve any of them for bonus marks in the course.

Here is the problems list.

Sequences

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.

Tentative outline of the course

Lectures

Lecture summaries are here.

Problem Sets

Some papers relevant to the course

Some papers arising from previous graduate courses