# Prove that the language of unary not-prime numbers satisfies the Pumping Lemma

Here is a question from Daniel I. A. Cohen's book Introduction to Computer Theory:

Consider the language:

$\quad \mathrm{PRIME}' = \{ a^n \mid n \text{ is not a prime} \} = \{ \varepsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots \}$

1. Prove that $\mathrm{PRIME}'$ is non-regular.
2. Prove, however, that $\mathrm{PRIME}'$ does satisfy the pumping lemma.

Part 1. is really easy to prove. I start my proof of part 2. like this:

1. We pick $m$ s.t. $m \geq 4$.
2. The opponent picks $w = a^{n^2}$, where $n$ is any prime number greater than m.

Now I don't know how to decompose $w$ into $xyz$. Any help would be appreciated.

Update: According to the answers below, $\mathrm{PRIME}'$ doesn't satisfy the Pumping Lemma we commonly talk about (requiring $|xy| \leq m$). I have checked the book at the library and found there are two versions of the Pumping Lemma in it. The weaker one, which clearly this question refers to, doesn't require a fixed pumping length.

-
Re: Update: Could you please share the statement you are refering to? –  vonbrand Jan 25 '13 at 14:23
@vonbrand, I don't have the book at hand, but you may refer to A note on the Pumping Lemma for regular languages, where the Version I and II of the Pumping Lemma are just those two forms mentioned above. –  Stupident Jan 26 '13 at 4:26

Let $w \in \mathrm{PRIME}'$ with $|w| \geq 5$. Distinguish two cases.

1. $|w|$ is even -- in that case, choose $x = \varepsilon$, $y = aa$ and $z = a^{|w|-2}$. Then, for all $i\geq 0$, we have $|xy^iz|$ is even and greater than two, as $|z| \geq 3$, and therefore not prime; $xy^iz \in \mathrm{PRIME}'$.

2. $|w|$ is odd -- in this case, we can not verify the pumping property. This can be seen as follows.

We have

$\quad \forall m \geq 1.\, \exists n \geq m.\, \forall 1 < k \leq m.\, \gcd(k, n-k) = 1 \qquad (\star)$

that is for every assumed pumping length $m$, there is a longer word $a^n$ which you can not separate into $a^k$ and $a^{n-k}$ with $k \leq m$ (note that $k=1$ trivially violates the pumping property) so that $k$ and $n-k$ share a divisor. Therefore, we can invoke Dirichlet's theorem for every possible separation, which yields that there are (infinitely many) primes you get by $(n-k) + ik$. So we can't find a pumpable split of $a^n$, and thus the pumping property is violated for $a^n$, which is enough to "contradict" the lemma.

$(\star)$ can be shown by contradiction. Pick $n>m$ non-prime so that $n$ has no prime factor $\leq m$, e.g. $n = p^2$ for $p\geq m$ prime. Assume there was a $1<k\leq m$ so that some $1<d\leq k$ divided both $k$ and $n-k$, i.e. $k = id$ and $n-k = jd$ for some natural $i,j$. But then, $n = (i+j)d$, i.e. $d \leq m$ divides $n$, which contradicts the choice of $n$.

-

Pick $xyz$ so that $|y|$ is not coprime to $|xyz|$. This does not work when $|xyz|$ does not have prime factors smaller than the pumping length though. In that case there will be a prime amongst all $|xy^nz|$ by Dirichlet's theorem.

-
Thank you for pointing out Dirichlet's theorem. So do you think the argument "PRIME' does satisfy the pumping lemma" is wrong? –  Stupident Jan 23 '13 at 9:59
@Stupident, it is wrong, unless you have some weird definition of pumping lemma that does not require a fixed pumping length. –  Karolis Juodelė Jan 23 '13 at 11:33
In order to apply the theorem to the effect you state, you need for every $p > 0$ an $n \leq p$ such that for all $k \leq p$, $k$ and $n-k$ are coprime (in particular, not $k$ and $n$ as you claim). It is not clear to me how you pick $n$. –  Raphael Jan 23 '13 at 13:15
@Raphael, note that $\text{gcd}(k, n) = \text{gcd}(k, n-k)$. I'm unsure what your variables mean ($p$ the pumping length, $n = |xyz|$ and $k = |y|$?). Regardless, I don't think I missed anything in my answer... –  Karolis Juodelė Jan 23 '13 at 15:02
In a language like this (one symbol only) it is enough to consider lengths, no need to consider chopping up strings and so. –  vonbrand Jan 23 '13 at 19:33