Tag Archives: finite automata

Finite automata 3: Non-automatic sets

The key ingredients in our proof of the special case of Cobham’s theorem were the pumping lemma and the following fact:

(*)\qquad [ab^{n+1}c]_q-q^{|b|}[ab^nc]_q=\text{constant}

We can formally put them together into the following lemma:

Lemma 1. If S\subseteq\mathbb N is an infinite automatic set, then there exist distinct s_0,s_1,\ldots\in S and integers A>1 and B such that s_{n+1}=As_n+B for all n.

Proof. Say S is q-automatic. By the pumping lemma we can take s_n=[ab^nc]_q for some a,b,c\in\Sigma_q^* with |b|\ge 1. Note that these are distinct as we don’t allow leading zeros. The conclusion now follows from (*). \square

Lemma 1 can be a powerful tool in proving that sets are not automatic, because it transforms a question from automata theory into the language of simple unary recurrences. For instance, we can use it to easily prove the following theorem of Minsky and Papert:

Theorem 1 (Minsky and Papert, 1966). The set of prime numbers is not automatic.

We are actually able to prove the following stronger result:

Theorem 2 (Schützenberger, 1968). An infinite set of prime numbers is not automatic.

Proof. Assume the contrary. Then by lemma 1 there exist distinct prime numbers p_1,p_2,\dots and integers A>1 and B such that p_{n+1}=Ap_n+B for all n\ge 1. Then

p_{n+j}\equiv B(A^{j-1}+\dots +A+1)\pmod{p_n}

for all j,n\ge 1. Now pick n large enough so that p_n\nmid A(A-1). Then

\displaystyle p_{n+p_n-1}\equiv\frac{B(A^{p_n-1}-1)}{A-1}\equiv 0\pmod{p_n}

by Fermat’s little theorem, a contradiction. \square

Note that lemma 1 implies that any set whose elements increase very rapidly cannot be automatic. To put it formally:

Theorem 3. Let f:\mathbb N\to\mathbb N such that f(n+1)/f(n)\to\infty as n\to\infty. Then the set \{f(1),f(2),f(3),\dots\} is not automatic.

Proof. Assume the contrary. Then there exist integers 0<s_0<s_1<\cdots such that f(s_{n+1})=Af(s_n)+B for all n, where A>1 and B are fixed integers. Then f(s_{n+1})/f(s_n)\to A as n\to\infty, a contradiction. \square

Corollary 1. The set \{1!,2!,3!,\dots\} of factorials is not automatic.

Proof. Take f(n)=n! in theorem 3. \square

Corollary 2. The set \{2^{2^0}+1,2^{2^1}+1,2^{2^2}+1,\dots\} of Fermat numbers is not automatic.

Proof. Take f(n)=2^{2^{n-1}}+1 in theorem 3. \square

It is possible to use lemma 1 in other ways to show that sets are not automatic. For example:

Theorem 4. Let f:\mathbb N\to\mathbb N such that f(n+1)/f(n)\to\alpha as n\to\infty, where \alpha is a real number such that \alpha^m\not\in\mathbb N for any m\in\mathbb N. Then the set \{f(1),f(2),f(3),\dots\} is not automatic.

Proof. Assume the contrary. Then by lemma 1 there exist distinct positive integers s_0,s_1,\dots such that f(s_{n+1})=Af(s_n)+B for all n, where A>1 and B are fixed integers. Now

\displaystyle\lim_{n\to\infty}\frac{f(n+m)}{f(n)}=\alpha^{m}

for all m\in\mathbb N. Therefore, as f(s_{n+1})/f(s_n)\to A, it follows that A=\alpha^m for some m\in\mathbb N. But this is impossible, as \alpha^m\not\in\mathbb N for any m\in\mathbb N. \square

Corollary 3. The set \{0,1,1,2,3,5,\dots\} of Fibonacci numbers is not automatic.

Proof. Let F_n denote the n-th Fibonacci number. Note that F_{n+1}/F_n\to\varphi=(1+\sqrt 5)/2 as n\to\infty, and that \varphi^m=F_m\varphi+F_{m-1}\not\in\mathbb N for all m\in\mathbb N. So the result follows by theorem 4. \square

In the exact same manner we also get:

Corollary4. The set \{2,1,3,4,7,11,\dots\} of Lucas numbers is not automatic.

Advertisements

Leave a comment

Filed under Analysis, Combinatorics, Number theory

Finite automata 2: Cobham’s theorem

Positive integers x and y are said to be multiplicatively dependent if x^m=y^n for some m,n\in\mathbb N. If x and y are not multiplicatively dependent, we say they are multiplicatively independent. Cobham’s theorem states the following:

Theorem 1 (Cobham, 1969). If an infinite set is both p-automatic and q-automatic, then p and q are multiplicatively dependent.

We are not going to prove theorem 1, but let us prove the following special case:

Theorem 2. If S=\{1,p,p^2,\dots\} is q-automatic, then p and q are multiplicatively dependent.

At first glance it is perhaps not obvious that theorem 2 is a special case of theorem 1. So let us show that it indeed is:

Theorem 3. The set S in theorem 2 is p-automatic.

Proof. We construct a DFA (\Sigma_{p},Q,q_0,\delta,F) as follows:

  • Q=\{q_0,q_1,q_2\}
  • F=\{q_1\}
  • \delta(q_0,0)=q_0
  • \delta(q_0,1)=q_1
  • \delta(q_0,j)=q_2 for each j\in\Sigma_p\backslash\{0,1\}
  • \delta(q_1,k)=q_2 for each k\in\Sigma_p
  • \delta(q_2,k)=q_2 for each k\in\Sigma_p

Final project - Dropbox 2014-10-26 16-30-09

This shows that S is p-automatic. \square

In fact, from the following result it follows that the set S in theorem 2 is actually p^k-automatic for each k\in\mathbb N:

Theorem. If S\subseteq\mathbb N is p-automatic, then it is p^k-automatic for each k\in\mathbb N.

Proof. Since S is p-automatic, there exists a DFA \Gamma=(\Sigma_{p},Q,q_0,\delta,F) such that S=\{[w]_p:w\in\mathcal L_\Gamma\}. Now we construct a new DFA (\Sigma_{p^k},Q,q_0,\delta',F) by defining \delta'(q,p^j+r)=\delta(q,r) inductively for each j\in\{1,2,\dots,k-1\} and r\in\{0,1,\dots,p^j-1\}. This shows that S is p^k-automatic. \square

Proof of theorem 2. Since S=\{1,p,p^2,\dots\} is q-automatic, by the pumping lemma there exists a DFA \Gamma=(\Sigma_{q},Q,q_0,\delta,F) and a,b,c\in\Sigma_q^* with |b|\ge 1 such that ab^nc\in\mathcal L_\Gamma for all n\ge 0. So [ab^nc]_q\in S for all n\ge 0, i.e. there exist integers 0\le k_0< k_1<\cdots such that [ab^nc]_q=p^{k_n} for all n. Note that

[ab^nc]_q=q^{n|b|+|c|}[a]_q+q^{(n-1)|b|+|c|}[b]_q+\cdots+q^{|c|}[b]_q+[c]_q.

So

p^{k_{n+1}}-q^{|b|}p^{k_n}=[c]_q+q^{|c|}[b]_q-q^{|b|}[c]_q

for each n\ge 0. The right-hand-side above is constant, and is divisible by p^{k_n} for each n\ge 0. So it must be identically 0, i.e.

q^{|c|}[b]_q=(q^{|b|}-1)[c]_q.

Since |b|\ge 1, we have \gcd(q^{|c|},q^{|b|}-1)=1. Hence q^{|c|} divides [c]_q. If we write [c]_q=c_0+c_1q+\cdots+c_mq^m, then q^{|c|}=q^{m+1}>[c]_q. So [c]_q=0. As a result, [b]_q=0. Therefore q^{|b|}=p^{k_{n+1}-k_n}, i.e. p and q are multiplicatively dependent, as required. \square

1 Comment

Filed under Combinatorics, Number theory

Finite automata 1: Automatic sets

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 \mathbb N_0 denote the set of non-negative integers and K be a field. For a linear recurrence f:\mathbb N_0\to K, define its zero set to be \{n\in\mathbb N_0 : f(n)=0\}. Then the Skolem-Mahler-Lech theorem states the following:

Theorem (Skolem-Mahler-Lech, 1953). The zero set of a linear recurrence f:\mathbb N_0\to\mathbb K, where K is a field of characteristic 0, 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 f:\mathbb N_0\to K, where K is a field of characteristic p>0, is a p-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 \Gamma satisfying certain properties. Firstly, its vertex-set Q (which we call the set of states) contains a special vertex (or state) q_0, called the initial state. We also have a finite non-empty set \Sigma of symbols. Each edge of \Gamma is labelled with a symbol from \Sigma. As a result, we have a transition function \delta:Q\times\Sigma\to Q such that if an edge from q_1 to q_2 is labelled with the symbol a\in\Sigma, then we write \delta(q_1,a)=q_2. Finally, we have a set F\subseteq Q (possibly empty) called the set of accepting or final states.

So \Gamma can be formally written as a quintuple (\Sigma,Q,q_0,\delta,F).

Let \Sigma^* be the free monoid on \Sigma. We can extend the transition function \delta to a map \delta:Q\times\Sigma^*\to Q by setting \delta(q_0,wa)=\delta(\delta(q_0,a),w) for all a\in\Sigma and w\in\Sigma^*. Thus, to \Gamma we can associate a language

\mathcal L_\Gamma:=\{w\in\Sigma^*:\delta(q_0,w)\in F\}\subseteq\Sigma^*.

We call such a language produced from a DFA a regular language. If w\in\mathcal L_\Gamma for some w\in\Sigma^*, we say that w is accepted by \Gamma.

Let \mathbb N denote the set of the positive integers, and let k>1 be an integer. Define \Sigma_k:=\{0,1,\dots,k-1\}. A subset S\subset\mathbb N is said to be k-automatic if there exists a DFA \Gamma=(\Sigma_k,Q,q_0,\delta,F) such that S is precisely the set of those j\in\mathbb N whose base-k representation, when regarded as a string in \Sigma^*, is accepted by \Gamma. If S\subseteq\mathbb N is k-automatic for some k>1, we say S is an automatic set.

For w=w_nw_{n-1}\cdots w_0\in\Sigma_k^* with each w_i\in\Sigma_k we define

[w]_k:=w_nk^n+w_{n-1}k^{n-1}+\cdots+w_0.

In this case we also define |w|:=n+1 to be the length of w.

So S\subseteq\mathbb N is k-automatic precisely when S=\{[w]_k:w\in\mathcal L_\Gamma\} for some DFA \Gamma.

Note that we can set \delta(q,0) to be in Q\backslash F for every q\in Q (if F=Q, 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 \mathcal L is an infinite regular language, then there exist words a,b,c with |b|\ge 1 such that ab^nc\in\mathcal L for all n\ge 0.

Proof. Since \mathcal L is infinite, there are words of arbitrarily large length in \mathcal L. Let w=w_nw_{n-1}\cdots w_0\in\mathcal L be a word of sufficient length. Then there exist 0\le i<j\le n such that w_i\cdots w_0=w_j\cdots w_0\in\mathcal L. Taking a=w_n\cdots w_j, b=w_{j-1}\cdots w_i, c=w_{i-1}\cdots w_0 shows that ab^nc\in\mathcal L for all n\ge 0. Moreover, since i<j, it follows that |b|\ge 1. \square

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.

Leave a comment

Filed under Algebra, Combinatorics, Number theory