A Funny Irregularity March 11, 2021

Fermat’s Last Theorem was, until its resolution in the 1990s, arguably the most well-known open mathematical conjecture in the world. No doubt this is partly due to the vast gap between the simplicity of the theorem and the difficulty of its proof. If you’re not familiar with it, I’m sure you can find countless expositions online, but for the purposes of this post, I’ll just restate the main result here: when $n > 2$, the equation $$a^n + b^n = c^n$$ has no solutions for positive integers $a$, $b$, and $c$.

The following is, in my opinion, a very funny application of Fermat’s Last Theorem to a problem in theoretical computer science. This is inspired by a problem from 15-251 a couple of semesters ago at Carnegie Mellon, although I’ve of course modified the problem, because I don’t want to be posting solutions to homework problems on the Internet.¹ This is not the standard (or indeed, intended) solution to the problem, but when I thought of it, I decided it was worth writing down.

The problem is this:

Prove that the language $L = \left\{a^{n^3} : n \in \mathbb{N}\right\}$ is not regular.

A silly solution: suppose $L$ were regular. Then by the pumping lemma,² it must be the case that $a^{n^3 + tk} \in L$ for some $n, k \ge 1$ and any $t \ge 0$. In particular, choose $t = k^2$: $$a^{n^3 + k^3} \in L.$$ But then this implies that $n^3 + k^3 = m^3$ for some $n, k, m \ge 1$, which contradicts Fermat’s Last Theorem!