# 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*} &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?

• For $i\neq j$, let $k=\min(i,j)$. Then $z=a^{3k^2+3k+1}$ distinguishes $x=a^{i^3}$ and $y=a^{j^{3}}$. In fact, assume that $k=i$. Then $xz=a^{(i+1)^3}\in L$, while $yz=a^{j^3+3i^2+3i+1}\notin L$. The latter assertion is because $j^3<j^3+3i^2+3i+1<j^3+3j^2+3j+1=(j+1)^3$. Since $j^3+3i^2+3i+1$ is strictly between two consecutive cubes, it cannot itself be a cube.
– plop
May 13, 2021 at 20:55
• Thanks @plop. Would have definitely given you a green mark :) May 13, 2021 at 21:59

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$$).