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

Final project - Dropbox 2014-10-26 16-30-09

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

Advertisements

1 Comment

Filed under Combinatorics, Number theory

One response to “Finite automata 2: Cobham’s theorem

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s