2
$\begingroup$

Does a random binary sequence almost always have a finite number of prime prefixes?

Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = \sum_{0 \le j \le i}{2^{i-j} \cdot x_j}$, and $F(x) = \cup_{i}{\{X_i\}}$. How can we prove that F(x) almost certainly does not contain an infinite number of primes?

With the prime number theorem as a heuristic we can give a distribution for the number of primes in $F(x)$ so according to this it is always finite, but this is not very convincing.

Instead I was trying to understand this using the notion of an algorithmically random sequence. Any prime prefix $n$ can be described as "the $\pi(n)^{\text{th}}$ prime number" and this description requires $\log{\log{n}}$ fewer bits than describing $n$ itself, but if the sequence has an infinite number of primes it cannot be $c$-incompressible for any $c$ contradicting the definition of an algorithmically random sequence. Is this argument valid?

What is the easiest way to prove this?

$\endgroup$
1
  • 1
    $\begingroup$ The expected number of primes is actually infinite, since the probability that $X_i$ is prime is $\Theta(1/i)$. It is probably the case that whp infinitely many prefixes are prime. You can try proving this using the second moment method. You might have to use a version of the prime number theorem with good bounds on the error. $\endgroup$ – Yuval Filmus Oct 5 '14 at 5:21

Your Answer

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

Browse other questions tagged or ask your own question.