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.^{1} 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,^{2} 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!

If this isn’t enough “anonymization,” I’ll take this post down. I do think that the modified problem differs substantially enough from the original that it wouldn’t be of much help for solving it. And at any rate, it’s not like I have any readers.↩︎

If you haven’t heard of this, it just says that, if $L$ is regular, then there exists some constant $k$ such that you can split any $x \in L$ of length $|x| \ge k$ into the form $x = uyv$, with $uy^nv \in L$ for all $n \ge 1$. This is vacuously true for finite languages. For infinite languages, the intuition is that there must be some loop consuming $y$ in the corresponding DFA. You can then “pump” this loop by going around it as many times $n$ as you want without changing the behavior of the DFA.↩︎