11
$\begingroup$

Define $f(n) = \lfloor 2^n \cdot \Omega \rfloor$, that is, $f(n)$ is the first $n$ bits of Chaitin's constant interpreted as a number written in binary.

I am trying to figure out if $f(n)$ can have infinitely many prime values. To show that it cannot, it would suffice to find a way of compressing these prime values to descriptions arbitrarily shorter than $ \log_2{p}$ bits. This seems to be a tricky task as it runs up against the edge cases of the definitions.

Let $L(x) = \lfloor \log_2{x} \rfloor + 1$. Any number $n$ can be encoded in a prefix-free fashion by first emitting the length of the length of its length in unary, then the length of its length in binary, then its length in binary, then the number itself in binary. This uses $2 \cdot L(L(L(n))) + L(L(n)) + L(n)$ bits.

If we have a prime number $p$, we can improve on this by encoding its index $\pi(p)$, and decoding it with a program that finds the $\pi(p)^{th}$ prime. By the prime number theorem, we save $L(L(p)) + O(1)$ bits this way. But the pesky $2 \cdot L(L(L(p)))$ term remains.

There is more information we can take advantage of: the $k^{th}$ prime prefix of $\Omega$ is a special type of prime, because it itself has $k-1$ prime prefixes. So we can count only those primes when decoding it, and heuristically this gives an encoding of size $2 \cdot L(L(L(p))) + L(p) - O(k)$ bits. Or roughly, prime prefixes of $\Omega$ must be triply-exponentially sparse, as long as for some $c \gt 1$ there are always $O(\frac{n}{c^k \cdot \log{n}})$ primes less than $n$ with exactly $k$ prime prefixes. (I still believe something like this is true but my reasoning here is a bit off.)

This approach succeeds on sets with less density than the primes: only a finite number of prefixes of $\Omega$ are primes with prime index (we save $2 \cdot L(L(p))$ bits, bringing the total description length under $L(p)$ by an increasing margin), and similarly only a finite number of prefixes of $\Omega$ are part of a twin prime pair (using Brun's theorem). Generally, any computable set with density $O((\log{n})^{-1-\epsilon})$ for $\epsilon \gt 0$ has a finite intersection with the prefixes of $\Omega$.

What else can be said about this problem?

[EDIT: I realized that I asked a very similar question three years ago, but it has gone unanswered and I've made more progress since then which I've explained above.]

$\endgroup$
  • $\begingroup$ Where do you get the sparsity of primes with prime prefixes in your last paragraph? $\endgroup$ – Steven Stadnicki May 17 '17 at 19:17
  • $\begingroup$ (Also, of course your prefix-free encoding principle can be extended deeper still; you can use $L(n)+L(L(n))+L(L(L(n)))+2L(L(L(L(n))))$ bits, etc. ) $\endgroup$ – Steven Stadnicki May 17 '17 at 19:19
  • $\begingroup$ If $k$ grew faster than $L(L(L(p)))$ then we would be able to compress a large enough prime prefix of $\Omega$ by describing it as the $n^{th}$ prime with $k-1$ prime prefixes. (Based on the heuristic that primality of prefixes is independent.) $\endgroup$ – Dan Brumleve May 17 '17 at 19:20
  • 3
    $\begingroup$ $\Omega$ is not a number - it depends on the model of computation and how programs are encoded. I suppose you are trying to prove something for all values of $\Omega$. $\endgroup$ – Solomonoff's Secret May 17 '17 at 19:41
  • 1
    $\begingroup$ @Solomonoff'sSecret: I think $\Omega$ is mainly used for advertisement purposes; the question really seems to be if a ML random number can have initial pieces equal to a prime infinitely often. $\endgroup$ – user138530 Jun 1 '17 at 5:57

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.