Is {a^n: n is a product of exactly two primes} regular?

Question

I am struggling to prove the following question.

$L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$

I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $m$ is a constant of Pumping Lemma. Now let $w = a^M$ where $M > m$ and $M$ is a co-prime number. Clearly $w$ is in the language and $|w| > m$.

Now let $y=a^j$ where $j$ is between $1$ and $m$, with $|xy| \leq m$ and $|y| \geq 1$.

This is where I am getting stuck. I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $M$, but can't figure it out.

Answer 1

Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.

Answer 2

Here is yet another proof. It is known that the number of integers at most $n$ which are the product of two primes is $o(n)$, see for example this answer, which gives the asymptotic $\frac{n\log\log n}{\log n}$. This means that your language is infinite yet has vanishing asymptotic density. This is impossible for a regular unary language.

Answer 3

There is an alternative to the “pumping” lemma which I find easier: After each possible input, determine the set of continuations that would complete a string of the language. You can use each of those sets as a state in the finite state machine for the language, so if there is a finite number of those sets then the language is regular- if there are infinitely many different sets, the language is irregular.

In your case, after processing k symbols, a further pq-k symbols for primes p, q gives a string in the language. We’ll need some statement about primes. One statement is: The gaps between primes are arbitrarily long. Let p, q be consecutive primes with a larger gap q-p than any previous gap. After processing 2p symbols, the smallest even number of symbols to give a product of two primes is 2(q-p). Therefore, after processing 2p symbols you are in a different state than after processing 2p’ symbols for any prime p’ < p.