A Funny Irregularity

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>2n > 2, the equation an+bn=cna^n + b^n = c^n has no solutions for positive integers aa, bb, and cc.

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={an3:nN}L = \left\{a^{n^3} : n \in \mathbb{N}\right\} is not regular.

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

  1. 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.↩︎

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