18
$\begingroup$

Let

$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$

Is $L$ regular?

This question looked suspicious at the first glance and I've realized that it is connected with the twin prime conjecture. My problem is that the conjecture has not been resolved yet, so I am not sure how can I proceed with deciding that the language is regular.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Note that if $P=\{a^p:p,p+2\in\mathbb{P}\}$ then $L$ is a quotient: $L=P/a^{\ast}$ (or, it is the set of prefixes of $P$). In general, for any unary language $P$ the language $P/a^{\ast}$ is regular. $\endgroup$ – sdcvvc Dec 9 '12 at 20:25
  • $\begingroup$ An amusing variant is $L = \{ a^p : p \text{ and } p+2 \text{ are prime} \}$. This is regular iff the twin prime conjecture is false. $\endgroup$ – Yuval Filmus Apr 30 '14 at 2:36
17
$\begingroup$

If the twin prime conjecture is true, then $L = a^{*}$, which is regular. If the twin prime conjecture is not true, then there are finitely many twin primes; indeed, there is a largest pair of twin primes $\{p, p + 2\}$. In this case, $L = \{a^{n} | n < p + 1\}$, a finite language. In either case, you get a regular language, so I think it's safe to conclude that $L$ is a regular language... we just won't know which one it is until the twin prime conjecture is resolved.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ <been doing too much intuitionistic logic> Could the twin prime conjecture be undecidable? $\endgroup$ – Gilles♦ Mar 14 '12 at 22:44
  • $\begingroup$ @Gilles Is undecidable really the correct term here? Either there are infinitely many twin primes or there are not. $\endgroup$ – Zach Langley Mar 14 '12 at 23:25
  • $\begingroup$ @ZachLangley Not necessarily: the twin prime conjecture (TP) could be undecidable (in the sense of independent from usual mathematical axioms). But my comment was a joke (impossible to get if you don't know what intuitionistic logic is; in fact, from “TP or not TP”, we can deduce “$L$ is finite or $L$ is $L=a^*$”, so $L$ is regular anyway. $\endgroup$ – Gilles♦ Mar 15 '12 at 0:29
11
$\begingroup$

Yes, this language is regular. The twin prime conjecture need not be resolved in order to see this:

Suppose the twin prime conjecture is true, that is, for any $n$, we can find a prime $p \geq n$ such that $p+2$ is prime. Then in particular, $L = \{ a^n | n \in N \}$, as the condition is always true. This last language is expressible by $a^*$ and hence regular.

Suppose the twin prime conjecture is false. Then there exists some $N$ such that there exists some prime $p$ such that $p+2$ is prime, and for every $n > N$, there exists no $p$ such that $p+2$ is prime. In this case, $L = \{ a^n | n \leq N \}$, which is a finite language, and therefore regular.

By case distinction, we conclude that $L$ is regular.

|cite|improve this answer
$\endgroup$
9
$\begingroup$

It is regular in either case.

  • If there are infinitely many twin primes, then $L=\{a^n:n\geq 0\}=L(a^*)$.
  • If there are finitely many twin primes, then $L$ is finite, therefore regular.
|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.