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 d*eterministic 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.