 Main
PRecursive Integer Sequences and Automata Theory
 Author(s): Garrabrant, Scott Michael
 Advisor(s): Pak, Igor
 et al.
Abstract
An integer sequence {a n } is called polynomially recursive, or Precursive, if it satisfies a nontrivial linear recurrence relation of the form
q_0(n)a_n + q_1(n)a_{n−1} + . . . + q_k(n)a_{n−k} = 0 ,
for some q_i(x) ∈ Z[x], 0 ≤ i ≤ k. The study of Precursive sequences plays a major role in modern Enumerative and Asymptotic Combinatorics. Precursive sequences have Dfinite (also called holonomic) generating functions.
This dissertation is on the application of automata theory to the analysis of Precursive integer sequences, and is broken into three selfcontained chapters. Chapters 1 and 2 contain negative results, simulating Turing machines within combinatorial structures to show these structures are not counted by a Precursive sequence. In Chapter 1, we answer a question of Maxim Kontsevich by showing [1]u_n is not always Precursive when u ∈ Z[GL(k, Z)]. In Chapter 2, we disprove the celebrated NoonanZeilberger conjecture by showing that pattern avoidance is not Precursive. These two chapters give the first results that disprove Precursiveness using automata theory. Historically, results of this form have been mostly proven using analysis of the asymptotics.
Chapter 3 gives a full analysis of the class of integer sequences counting irrational tilings of a constant height strip. This class is a subset of Precursive sequences, and we prove the equivalence of three definitions of this class: counting functions of irrational tilings, binomial multisums, and diagonals of Nrational generating functions. In this analysis, we count paths through a labelled graph in a way that is equivalent to counting strings accepted by a given deterministic finite automaton where each letter appears n times.
Main Content
Enter the password to open this PDF file:













