In one of my recent courses I had to learn about finite automata theory. The main purpose was to understand a generalisation of the celebrated Skolem-Mahler-Lech theorem in positive characteristic. Let denote the set of non-negative integers and be a field. For a linear recurrence , define its zero set to be . Then the Skolem-Mahler-Lech theorem states the following:
Theorem (Skolem-Mahler-Lech, 1953). The zero set of a linear recurrence , where is a field of characteristic , is a finite union of arithmetic progressions along with a finite set.
Derksen in his 2005 paper was able to provide the correct analogue of this result in positive characteristic for the first time:
Theorem (Derksen, 2007). The zero set of a linear recurrence , where is a field of characteristic , is a -automatic set.
To understand this theorem we need to know about finite automata. In this and the next few posts I want to write about some interesting elementary results about automatic sets. Since my knowledge of computer science is epsilon(!), I will mostly touch on some very basic mathematical aspects.
A deterministic finite-state automaton (DFA) is a directed multigraph satisfying certain properties. Firstly, its vertex-set (which we call the set of states) contains a special vertex (or state) , called the initial state. We also have a finite non-empty set of symbols. Each edge of is labelled with a symbol from . As a result, we have a transition function such that if an edge from to is labelled with the symbol , then we write . Finally, we have a set (possibly empty) called the set of accepting or final states.
So can be formally written as a quintuple .
Let be the free monoid on . We can extend the transition function to a map by setting for all and . Thus, to we can associate a language
We call such a language produced from a DFA a regular language. If for some , we say that is accepted by .
Let denote the set of the positive integers, and let be an integer. Define . A subset is said to be -automatic if there exists a DFA such that is precisely the set of those whose base- representation, when regarded as a string in , is accepted by . If is -automatic for some , we say is an automatic set.
For with each we define
In this case we also define to be the length of .
So is -automatic precisely when for some DFA .
Note that we can set to be in for every (if , just create a new state). Thus we may without loss of generality assume that all our DFAs only accept words without leading zeros.
A basic result about regular languages is the pumping lemma:
Lemma (Pumping lemma). If is an infinite regular language, then there exist words with such that for all .
Proof. Since is infinite, there are words of arbitrarily large length in . Let be a word of sufficient length. Then there exist such that . Taking , , shows that for all . Moreover, since , it follows that .
In the following posts we are going to use the pumping lemma, together with other machinery, to derive some interesting results on the automaticity of certain sets.