25/10/2014 · 7:30 pm
↓ Jump to Comments

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.

Leave a comment

Filed under Analysis, Combinatorics, Number Theory

Tagged as , ,

Leave a comment