Proving that L is not regular by showing that $\equiv_L$ has infinite index

Question

Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has finite index
We show: $\equiv_L$ has infinte equivalence classes.
$a^{3^i}$ $\not\equiv$ $a^{3^{i+k}}$, $k>0$
-> equivalence classes: [a], [aaa], [$a^3$]...
Every $a^{3^i}$ is a different equivalence class. Therefore $\equiv_L$ has an infinite amount of equivalence classes $\rightarrow$ L is not regular. qed.

How to show that the classes are different?

Answer 1

Let me prove a stronger claim: every two words over $\{a\}$ are inequivalent with respect to your language. What this means is that for every $i \neq j$, there is a word $w \in a^*$ such that either $a^i w \in L$ and $a^j w \notin L$, or vice versa. Since $w \in a^*$, in fact $w = a^k$ for some $k$, and so we need to prove the following:

If $i \neq j$ are natural numbers then there exists a natural number $k$ such that exactly one of $i+k,j+k$ is a power of 3.

Let $a_i$ be the smallest power of 3 which is at least $i$, and define $a_j$ similarly. If $a_i \neq a_j$, say $a_i < a_j$, then we can take $k = a_i$. So suppose $a_i = a_j = a$. Without loss of generality, $i < j$, and so $i+a < j+a$. The next power of 3 after $i+a$ is $3(i+a)$, and after $j+a$ is $3(j+a)$. Let $k = 2i+3a$. Then $i + k$ is a power of 3 by definition, but $j+a < j + k < 3(j+a)$ is not a power of 3.

Answer 2

Here is a simpler proof. We will show that for every $\ell$, the equivalence relation $\equiv_L$ has at least $\ell$ equivalence classes.

Given $\ell$, find $n$ such that $3^{n+1} - 3^n \geq \ell$. Consider the $3^{n+1} - 3^n$ words $a^0,a^1,\ldots,a^{3^{n+1}-1-3^n}$. I claim that they are pairwise inequivalent. Indeed, suppose $0 \leq i < j \leq 3^{n+1} - 1 - 3^n$. Let $k = 3^{n+1} - j$. Then $$ 3^n + 1 \leq k \leq k + i < k + j = 3^{n+1}. $$ In particular, $k + i$ is not a power of 3, whereas $k + j$ is a power of 3. Hence $a^i a^k \notin L$ whereas $a^j a^k \in L$, showing that these $3^{n+1} - 3^n \geq \ell$ are pairwise inequivalent. Hence there are at least $\ell$ equivalence classes.