Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime

Question

In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular.

I have not been able to solve this one:

The set of strings of 0s and 1s, beginning with a 1, and interpreted as an integer, that integer is prime.

My attempt:

Assume to the contrary that the language is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s = 101$. The pumping lemma guarantees s can be broken into 3 substrings, x, y, z such that $|xy| \leq p$ and $y \neq \epsilon$....

Obviously this is where it breaks down, because I haven't given a string that is of at least length $p$ (ie $s = 10^p1$).

Answer 1

I believe what you are missing is Fermat's Little Theorem: If $p$ is a prime and $p$ does not divide $a$, then $a^{p-1}\equiv 1 \mod p$.

I'll give an example application in base 10. Let's assume that 2039 is the prime to which the pumping lemma is applied and the decomposition is 2 03 9. That is the pumping lemma would imply that all strings of the form $2(03)^n9$ denote prime numbers. At least it is true for $n\in\{0,1,2\}$. But without further calculation I know that it fails for $n=28$: The number $N=2030303030303030303030303030303030303030303030303030303039$ is divisible by $29$, which is the number at $n=0$. To see this, observe that $N = 20\cdot 100^{28} + \sum\limits_{0\leq i< 28}30\cdot 100^i + 9 = 20\cdot 100^{28} + 30\cdot\frac{100^{28}-1}{100-1} + 9$ and apply Fermat's theorem. Here, we also use that $29$ does not divide $100-1$.

I hope from this you are able to solve the exercise.

Answer 2

One way to show that this language isn’t regular is to use the following theorem:

Let $L$ be a regular language over $\Sigma$, and let $c_n = |L \cap \Sigma^n|$. There exists a modulus $m \geq 1$ such that for all $0 \leq r < m$ there exist real $C,\lambda \geq 0$ and integer $k \geq 0$ such that the following asymptotic estimate holds for $n \equiv r \pmod{m}$: $$ c_n \sim Cn^k \lambda^n. $$

In your case, $c_n$ is the number of primes between $2^{n-1}$ and $2^n-1$. According to the prime number theorem, the number of primes up to $2^n$ is asymptotic to $2^n/n \log 2$, and so $$ c_n \sim \frac{1}{\log 2} \left( \frac{2^n}{n} - \frac{2^{n-1}}{n-1} \right) \sim \frac{1}{2\log 2} \frac{2^n}{n}. $$ This contradicts the theorem above.