Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$

Question

I need to prove that the following language is not regular by showing there are infinite pairwise distinct equivalence classes: $$ L = \{a^{n^3} \mid n \geq 1\} \subseteq \{a\}^* $$

Looking at a few examples, I intuitively noticed that for each $i \geq 1$ there is an equivalence class $[a^{i^3}] \neq [a^{j^3}]$ for $i \neq j$ because the number of $a$'s we need to add increases exponentially with $i/j$. Thus for every $i$ we can add a suffix of $a$'s to reach the next higher power $(i+1)^3$ but the length of that suffix is different for every other power, so that each equivalence class only actually contains the representative itself.

Example: $$ \begin{align*} &n = 1 \implies a \\ &n = 2 \implies a^8 \\ &n = 3 \implies a^{27} \\ \vdots \end{align*} $$ Then $$ \begin{align*} & [a] = \{x \in \{a\}^* \mid a \; R_L \; x\} = a \\ & [a^8] = \{x \in \{a\}^* \mid a^8 \; R_L \; x\} = a^8 \\ \vdots \end{align*} $$ Consider $[a]$. For $z = a^7$ we get $az = aa^7 = a^8 \in L$, but starting from $i \geq 2$, we have that $a^{i^3}z \notin L$.

How can I write this down in a more formal/rigorous way?

Answer 1

More generally, you can use Myhill–Nerode to prove the following characterization:

For $A \subseteq \mathbb{N}$, let $L(A) = \{ a^n : n \in A \}$.

The language $L(A)$ is regular iff $A$ is eventually periodic.

In particular, if $A$ is an infinite set with density zero then $L(A)$ is not regular. Here density zero means:

$$ \lim_{n\to\infty} \frac{|A \cap \{0,\ldots,n-1\}|}{n} = 0. $$

This shows that $\{a^{n^k} : n \in \mathbb{N}\}$ is not regular for any $k \geq 2$.

---

Let us prove the claimed characterization. If $A$ is periodic, say with period $m$, then $L(A)$ is clearly regular: it is accepted by a circular DFA with $m$ states. If $A$ is eventually periodic then there is a periodic $B$ such that $L(A),L(B)$ differ in finitely many words, and so standard closure operations show that $L(A)$ is regular.

Now suppose that $L(A)$ is regular. The equivalent class of $a^m$ is the set $E_m = \{ k \in \mathbb{N} : m+k \in A \}$. Since there are finitely many equivalence classes, there exist $m < p$ such that $E_m = E_p$, that is, for all $k \in \mathbb{N}$, $m + k \in A$ iff $p + k \in A$. In other words, for all $\ell \geq m$, $\ell \in A$ iff $\ell + (p-m) \in A$. Hence $A$ is eventually periodic (with period $p-m$).