Positive integers and are said to be *multiplicatively dependent* if for some . If and 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 -automatic and -automatic, then and are multiplicatively dependent.

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

**Theorem 2.** If is -automatic, then and 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 in theorem 2 is -automatic.

*Proof.* We construct a DFA as follows:

- for each
- for each
- for each

This shows that is -automatic.

In fact, from the following result it follows that the set in theorem 2 is actually -automatic for each :

**Theorem****. **If is -automatic, then it is -automatic for each .

*Proof.* Since is -automatic, there exists a DFA such that . Now we construct a new DFA by defining inductively for each and . This shows that is -automatic.

*Proof of theorem 2.* Since is -automatic, by the pumping lemma there exists a DFA and with such that for all . So for all , i.e. there exist integers such that for all . Note that

So

for each . The right-hand-side above is constant, and is divisible by for each . So it must be identically , i.e.

Since , we have . Hence divides . If we write , then . So . As a result, . Therefore , i.e. and are multiplicatively dependent, as required.

Pingback: Finite automata 3: Non-automatic sets | Samin Riasat's Blog