Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$ 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*}
  &amp;n = 1 \implies a \\
  &amp;n = 2 \implies a^8 \\
  &amp;n = 3 \implies a^{27} \\
  \vdots
\end{align*}
$$
Then
$$
\begin{align*}
&amp; [a] = \{x \in \{a\}^* \mid a \; R_L \; x\} = a \\
&amp; [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?
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 &lt; 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$).