Infinitely many primes through regular languages

May 17, 2020

Let MnM_n denote the set of strings consisting of just 11's whose length is a multiple of nn; i.e.

Mn{1n}M_n \triangleq \{1^n\}^*

Clearly, each MnM_n is regular. Additionally, recall that if AA and BB are regular languages, then the intersection ABA \cap B and the complement Aˉ\bar{A} are regular.

By the fundamental theorem of arithmetic, a number is a power of 22 exactly when 22 is the only prime number that divides it, so if there were finitely many primes {2,3,,p}\{2, 3, \dots, p\}, then the set

A={12k:k0}A=\{1^{2^k} : k \geq 0\}

of strings of 11's whose length is a power of 22 is regular as AA is equal to the intersection M2M3MpM_2 \cap \overline{M_3} \cap \dots \cap \overline{M_p} of (finitely many) regular languages.

However, we can show AA is not regular by using the pumping lemma. For k0k \geq 0, then if we let w=12kw = 1^{2^k}, then wAw \in A and w=2kk|w| = 2^k \geq k. If w=xyzw=xyz for strings x,y,zx, y, z with xyk|xy| \leq k and y1|y| \geq 1, then as xy2z=xyz+y|xy^2z| = |xyz| + |y|, xyz=2k|xyz| = 2^k, and y1|y| \geq 1, then xy2z>2k|xy^2z| > 2^k. Additionally, as xyk<2k|xy| \leq k < 2^k and xy+z=xyz|xy| + |z| = |xyz|, then z>0|z| > 0 so

xy2z=x+2y+z<2x+2y+2z=2xyz=2k+1.|xy^2z| = |x| + 2|y| + |z| < 2|x|+2|y|+2|z| = 2|xyz|=2^{k+1}.

Therefore, we have 2k<xy2z<2k+12^k < |xy^2z| < 2^{k+1}, so the length of xy2zxy^2z cannot be a power of two and thus xy2zAxy^2z \notin A. Thus, by the pumping lemma, AA is not regular so there must be infinitely many primes.

This post was adapted from u/JoshuaZ1's comment thread in r/math on different ways of proving the infinitude of primes.