# 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 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.