# Proving the set of powers of 2 over ternary alphabet to be non regular.

It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it.

But the powers of 2 represented in ternary appears to be non regular. Pumping lemma or residue classes is hard to apply as there seems to be very little pattern among the strings. How do I solve it?

In general, for what powers of $k$ represented in base $r$, is the set regular?

• An easy observation is that if both k and r are powers of the same integer, the set is regular. I guess that the converse also holds, but I do not have a proof. – Tsuyoshi Ito Oct 10 '10 at 12:08
• I think this is an exercise in Sipser's book. – Zeyu Oct 10 '10 at 23:53
• Looks like homework. – Warren Schudy Oct 26 '10 at 21:59

Here's an alternative solution (with detailed explanation) using Myhill-Nerode Theorem. I'll use base $3$ and $2$ for readibility, but the proof generalizes for arbitrary bases $r,k$ that are not powers of the same integer.

(1) Show that given any ternary string $x$, there exists another string $y$ such that $xy$ is a power of $2$.

Proof: Given any $x$ (letting $n$ be the number it represents), $\forall k$ and $c\in \{0,\ldots,3^k-1 \}$, there exists $y$ such that $xy$ represents $3^kn + c$. In fact, this characterizes all the numbers $xy$ can represent. Hence, finding the minimal $y$ such that $xy$ is a power of $2$ is depends on finding the smallest integer $k$ such that we have some power of $2$ in the interval $[3^kn,3^k(n+1)-1]$. Taking log base $2$, we need to find $k$ such that we have an integer in the interval $[k\log 3 + \log x, k\log3 + \log(x+1)]$ (dropping the $-1$ here is iffy, but simplifies calculations which do not rely on it). Notice that changing $k$ only affects the $k\log 3$ portion, so we can find a $k$ that gets us arbitrarily close to some integer.

(2) Given some $x$ and the corresponding minimal $y$, show that there exists a string x' such that the corresponding minimal $y'$ has to be larger than $y$. Repeating this gives us infinitely many equivalence classes of strings.

Proof Outline: Since $\log 2^m x = m + \log x$, given an $x$ and its corresponding $y$ and $k$ we can always find some $x' = 2^m x$ where $\log(2^m x + 1) - \log (2^m x)$ is sufficiently tiny such that no integer is contained in $[k\log 3 + m +\log x, k\log3 + \log(2^mx+1)]$. Note that we are implicitly using the fact that $k\log 3 + \log x$ can never be an integer.

In general, for what powers of $k$ represented in base $r$, is the set regular?

Your question is a subcase of Cobham's Theorem (Alan Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Theory of Computing Systems 3(2):186--192, 1969, doi: 10.1007/BF01746527):

Let $S$ be a set of non-negative integers and let $m$ and $n$ be multiplicatively independent positive integers. Then $S$ is recognizable by finite automata in both $m$-ary and $n$-ary notation if and only if it is ultimately periodic

Here by multiplicatively independent one means there does not exist non-zero $p$ and $q$ such that $m^p=n^q$. Cobham cites Büchi for your specific case of powers of some $k$ in base $r$, which is recognizable only if $k$ and $r$ are multiplicatively dependent.

If you are interested in this result, there is a rather nice survey by Véronique Bruyère, Georges Hansel, Christian Michaux, and Roger Villemaire (Logic and $p$-recognizable sets of integers, Bulletin of the Belgian Mathematical Society 1(2), 1994, PDF), which also shows the relationship with Presburger arithmetic.

The pumping lemma implies that there is a sequence like $x_n = c+b(r^{dn}-1)/(r^d-1)$ for some $b,c,d$ such that each $x_n$ is a power of $k$. So $\log_k(x_n)=dn \log_k(r) + const + o(1)$ is always an integer, so $\log_k(r)$ is rational.

Here's an explanation of that formula for $x_n$. The pumping lemma gives strings $u,v,w$ such that every string $x_n=u v^n w$ is a power of $k$. Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, $x_n = u r^{dn+e} + v r^{d(n-1)+e} + v r^{d(n-2)+e} + \dotsb + v r^e + w$ is a power of $d$. So $x_n-x_{n-1} = (u r^d - u + v) r^{d(n-1)+e}$. Writing $b=(u r^d - u + v)r^e$ and $c=x_0-b$ we have $x_n=c+b(r^{dn}-1)/(r^d-1)$.

• (1) I think that you need a term like $er^{dn}$ to deal with the prefix part of the pumping. (2) I cannot follow why $dn\log_k r+O(1)$ being always an integer implies $\log_k r$ is rational. More precisely, as is written, it is false because you can find $0\le\varepsilon_n\lt1$ such that $dn\log_k r+\varepsilon_n$ is an integer. I think that you need something more specific than the O-notation. – Tsuyoshi Ito Oct 10 '10 at 12:47
• If you write the general term as $x * r^{dn+e} + y r^{d(n-1)+e} + y r^{d(n-2)+e} + \dotsb + y r^e + z$ say, then the difference of two terms can be seen to be of the form $b r^{dn}$. – Colin McQuillan Oct 10 '10 at 12:52
• It is constant +o(1), that is not the same as O(1). – domotorp Oct 10 '10 at 12:55
• @domotorp: I think that the item (2) in my previous comment was referring to a portion which was edited in the 5-minute window, but I am not sure. Maybe I could misread the answer. – Tsuyoshi Ito Oct 10 '10 at 12:58
• @Colin: I am not sure what you are claiming by your last comment. It seems to me that your argument shows that a term like $er^{dn}$ is necessary. – Tsuyoshi Ito Oct 10 '10 at 12:59

Let $$L$$ be the set of powers of 2 encoded in base 3. The encoding of $$4^n$$ in base 3 ends with 1, whereas the encoding of $$2\cdot 4^n$$ in base 3 ends with 2. Hence $$L' = L \cap \Sigma^*1$$ is the encoding of all powers of 4.

The encoding of an integer $$m > 0$$ in base 3 takes $$\lceil \log_3 (m+1) \rceil$$ digits. Since neither $$4^n$$ nor $$4^n+1$$ are powers of 3 for $$n>0$$ (since neither is divisible by 3), the encoding of $$4^n$$ takes $$\lfloor \log_3 4^n \rfloor + 1$$ digits.

Let $$N = \{ \lfloor \log_3 4^n \rfloor : n \geq 0 \}$$ (this is a Beatty sequence). Suppose that $$L$$ were regular. Then so would $$L'$$ be. This implies that the set of lengths of words in $$L'$$ is eventually periodic, and so $$N$$ is eventually periodic. In particular, $$N$$ would have rational asymptotic density. However, $$N$$ has asymptotic density $$1/\log_3 4$$, which is irrational.