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

We can formally put them together into the following lemma:

**Lemma 1. **If is an infinite automatic set, then there exist distinct and integers and such that for all .

*Proof. *Say is -automatic. By the pumping lemma we can take for some with . Note that these are distinct as we don’t allow leading zeros. The conclusion now follows from .

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 and integers and such that for all . Then

for all . Now pick large enough so that . Then

by Fermat’s little theorem, a contradiction.

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

**Theorem 3.** Let such that as . Then the set is not automatic.

*Proof.* Assume the contrary. Then there exist integers such that for all , where and are fixed integers. Then as , a contradiction.

**Corollary 1.** The set of factorials is not automatic.

*Proof.* Take in theorem 3.

**C****orollary 2. **The set of Fermat numbers is not automatic.

*Proof. *Take in theorem 3.

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

**Theorem 4.** Let such that as , where is a real number such that for any . Then the set is not automatic.

*Proof.* Assume the contrary. Then by lemma 1 there exist distinct positive integers such that for all , where and are fixed integers. Now

for all . Therefore, as , it follows that for some . But this is impossible, as for any .

**Corollary 3.** The set of Fibonacci numbers is not automatic.

*Proof.* Let denote the -th Fibonacci number. Note that as , and that for all . So the result follows by theorem 4.

In the exact same manner we also get:

**Corollary4.** The set of Lucas numbers is not automatic.