Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem

Question

Let $L=\{ a^c \mid c \text{ is composite} \}$. Prove that $L$ is not regular using the pumping lemma. You can use Dirichlet's theorem, which states that if $(a,b) = 1$ then there are infinitely many prime numbers of the form $an+b$.

I am thinking about this question for a lot of days and I don't find it trivial, do you have any hints to give me about how to start the proof? please, I can see the connection between the pumping lemma and Dirichlet's theorem but I don't know how this is helping me, because the pumping lemma talks about a Periodicity, and Dirichlet's theorem talks about prime numbers and not composite so I will need to use the Complementary group

Answer 1

Suppose towards a contradiction that $L$ is regular and let $p$ be a prime number larger than $L$'s pumping length. Since $a^{p^2} \in L$, by the pumping lemma we know that there is some $1 \le k < p$ such that $a^{ki+p^2} \in L$ for all $i \ge -1$.

Since $k$ cannot have $p$ as a prime factor, $k$ and $p^2$ must be coprime and Dirichlet's theorem guantees the existence of some $n$ such that $kn+p^2$ is prime. The contradiction follows by choosing $i=n$.

If we replace "regular" by "context-free", the proof above shows $L$ is not context-free.

Answer 2

Let p be a prime. Since there are infinitely many primes, p is followed by n composite numbers for some n dependent on p, and then by another prime q.

After processing $a^p$ you are in a state S that is rejecting. In that state, if you process further a's, then the next n states are accepting, and the state after that is rejecting.

If the prime p is followed by n composite numbers and another prime q, and the prime p' ≠ p is followed by n' composite numbers and another prime q', and n ≠ n', then after accepting $c^p$ and $c^{p'}$ you must be in different states S and S', because in one state processing n+1 c's puts you back into a rejecting state for the first time, and in the other state you switch to a rejecting state either earlier (if n' < n) or later (if n' > n).

Gaps between primes get arbitrary large, therefore the numbers n' get arbitrary large, therefore there must be an infinite number of different state. Therefore there is no finite state machine for your language.

Sorry, no pumping lemma and no Dirichlet's theorem used.

PS. The same argument can be used for the language $c^n$ where n is / is not element of an infinite set with arbitrary large gaps between elements. For example $n = \lfloor p \log p \rfloor$ for some prime p, or $n = k!$ for some integer k.