How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

Question

Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular language using the pumping lemma?

I cannot seem to find any sort of pattern for ternary representations of $S$, and so I'm finding it really difficult to prove this using the pumping lemma.

I tried to make a few strings in $L$ and got $\{1, 11, 22, 121, 1012, 2101, \dots\}$ but cannot find any sort of pattern that leads to using the pumping lemma. So, how would you prove that this is not a regular language using the pumping lmma? Thanks in advance.

Answer 1

This answer is a simpler version of Colin McQuillan's answer to the same question.

---

Suppose the language is regular. The pumping lemma gives strings $u,v,w$ such that every string $x_n=u v^n w$ is a power of $2$.

Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, we have $$ x_n = u 3^{dn+e} + v 3^{d(n-1)+e} + v 3^{d(n-2)+e} + \dots + v 3^e + w.$$ So, $$x_{n+1}-3^dx_n = v3^e + w - 3^dw.$$

Note that the right-hand side is a constant as $n$ goes to infinity. Letting $c$ be the right-hand side, we have $$\frac{x_{n+1}}{x_n} - 3^d= \frac{c}{x_n}.$$

Since $x_{n+1}$ is a bigger power of 2 than $x_n$, $\dfrac{x_{n+1}}{x_n}$ is always an integer. That means the right-hand side is always an integer as well. Since $\dfrac c{x_n}$ goes to $0$ as $n$ goes to infinity, it must become 0 eventually.

Well, when it does become 0, we have $\dfrac{x_{n+1}}{x_n}=3^d$, which cannot happen since the left-hand side, a power of 2 that is greater than 1, can never be a power of 3.

---

Here is an easy exercise.

Exercise. Check that the above proof works the same if you replace 3 by any positive integer that is not a power of 2.