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

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$