3

Prove that the language $\{bin(p) \mid p\ \text{is prime}\}$ is not regular, where $bin(p)$ denotes the binary representation of $p$. I should use the pumping lemma. But I have a problem. Could you help me? Any clues?

Edit. This question is asking whether the set of primes is $2$-recognizable. A set $X$ of natural numbers is $k$-recognizable (or $k$-automatic) if the language consisting of the base-$k$ representations of the elements of $X$ is accepted by a finite automaton. More details on this theory can be found in the survey article

V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and $p$-recognizable sets of integers. Journées Montoises (Mons, 1992). Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 2, 191--238.

The following example is an illustation of a much more general result of this theory. Let $$ T = \{n \in \mathbb{N} \mid \text{the binary representation of $n$ contains an odd number of $1$'s}\}. $$ Then the infinite binary word $t = t_0t_1t_2 \dotsm$ defined by $t_n = 1$ if and only if $n \in T$ is the Thue-Morse sequence, obtained by iterating the substitution $0 \to 01$ and $1 \to 10$.

J.-E. Pin
  • 40,163
user220688
  • 509
  • 1
    Try Dirichlet's theorem: If a and b are relatively prime then the arithmetic progression an+b contains infinitely many primes. – marty cohen Mar 16 '15 at 23:40
  • I do not understand why this question should be off-topic. Compare it to Prove that this language is not regular for instance. This question is actually interesting and nontrivial. – J.-E. Pin Mar 17 '15 at 10:19
  • @marty-cohen How do you want to use Dirichlet's theorem for this question? – J.-E. Pin Mar 17 '15 at 10:29
  • @J.-E.Pin: I don't know remember what regular language and pumping lemma are (I once did take a look, but I've lost it). I somehow suspect that the idea may be to use the fact that if $p$ is an odd prime number and $2^m>p$, then the arithmetic sequence $x_k=k\cdot2^m+p$ contains infinitely many primes. – Jyrki Lahtonen Mar 17 '15 at 10:41
  • @J.-E.Pin: Also. You seem to have an interest in salvaging this question. Feel free to edit it extensively. May be describe how you would attack it yourself? That would improve the question, and make it a prime candidate for reopening. – Jyrki Lahtonen Mar 17 '15 at 10:43
  • @jyrki-lahtonen Thank you for your comment. I already edited the question, but just on a cosmetic level. But if I edit extensively, it might become a different question, making the comments obsolete, so I am not sure this is the right way to proceed. P.S. Being a "prime candidate" makes indeed sense for this question... – J.-E. Pin Mar 17 '15 at 10:59
  • What should I think about it ? Is it tricky problem ? – user220688 Mar 17 '15 at 15:07
  • Using Dirichlet's theorem: Perhaps choose a and b so that a prime an+b would have a form (i.e., 1, lots of zeros, lots of ones) that would not be regular. I have no idea if this would work. – marty cohen Mar 17 '15 at 20:00

2 Answers2

2

The answer is negative: the set of primes is not $2$-recognizable. A proof is given in [1], example 4 and in [2], Corollary 1.43. The proof relies on a property of $k$-recognizable languages due to Cobham (1972).

Let $(x_n)_{n \geqslant 0}$ be an increasing sequence of natural numbers. If the set $\{x_n \mid n \geqslant 0\}$ is $k$-recognizable, then either $$ \limsup_{n \to \infty}\ (x_{n+1} − x_n) < \infty \quad \text{or}\quad \limsup_{n \to \infty}\ \frac{x_{n + 1}}{x_n} > 1. $$ Let $p_n$ be the $n$-th prime number. Since $n! + 2, n!+3, \dotsm, n! +n$ are consecutive composite numbers, one has $\limsup_{n \to \infty}\ (p_{n+1} − p_n) = + \infty$. Moreover, it is a consequence of the prime number theorem that $\limsup_{n \to \infty}\ \frac{p_{n + 1}}{p_n} = 1$ (see Prime gap on Wikipedia).

[1] N. Rampersad, Abstract Numeration Systems in Language and Automata Theory and Applications, LNCS 6638, 65-79 (2011)

[2] M. Rigo, Formal Languages, Automata and Numeration Systems, Volume 2, John Wiley & Sons, 2014.

Conclusion. This proof answers the EDIT part of the question, but not the first part. Finding a proof relying on the pumping lemma is still an interesting challenge.

J.-E. Pin
  • 40,163
  • 1
    These is a proof relying on the pumping lemma here: https://math.stackexchange.com/a/1232511 – a3nm Nov 27 '19 at 13:55
  • @a3nm The linked answer relies on a strong version of the pumping lemma. Quoting the last line of this answer: "I do not know if it is possible to prove that the language of primes is not regular using only the simpler version of the Pumping Lemma. My gut feeling is that it would be very difficult, probably impossible." – J.-E. Pin Nov 27 '19 at 14:10
  • Oh, I didn't realize this counted as a strong version of the pumping lemma. It's close to the version I teach in an elementary formal languages class. :) But yeah if you can only use a pumping lemma with no control whatsoever on where you pump, I have no idea whether it can be done -- fun question! – a3nm Nov 27 '19 at 20:57
0

Hint: If your pumping string is has length $>1$ then you can use the result that there is always a prime between $n$ and $2n$ for any natural number $n > 1$. So that only leaves the cases when your pumping string is either just '0' or '1'.

user2566092
  • 26,142