What is known about irrationality measure of the Chaitin's constant $\Omega$? Is it finite? Can it be a computable number? Can it be $2$?
Irrationality measure of the Chaitin's constant $\Omega$
-
0@VladimirReshetnikov Why not offer a bounty then? – 2012-01-16
1 Answers
Since $\Omega$ is incompressible, its irrationality measure must be 2. In more detail:
If the irrationality measure of $\Omega$ were some $\alpha>2$, pick any $\beta$ in $(2,\alpha)$. Then there would be infinitely many pairs $(p,q)$ of integers $p$ and $q>0$ with $|p/q-\Omega|; since $\Omega\in(0,1)$, such a pair will have $0\le p\le q$.
Given such a pair with $q\ge 2$, let $n:=\lfloor{\beta \log_2 q-1}\rfloor$. Given the triple $(n,p,q)$, we can then determine that the first $n$ bits of $\Omega$ are given by $\lfloor{2^n \Omega}\rfloor=\lfloor{\delta+(2^np/q)}\rfloor,\qquad\delta\in[-\frac{1}{2},\frac12]. \qquad(*)$ Letting $m:=\lfloor{(2^np/q)-\frac{1}{2}}\rfloor$, we can see that the right-hand side of (*) varies over exactly the values $m$ and $m+1$ as $\delta$ runs over $[-\frac12,\frac12]$. Therefore, (*) must hold for either $\delta=-1/2$ or $\delta=1/2$, so the first $n$ bits of $\Omega$ can be computed from the quadruple $(n,p,q,\delta)$, $\delta\in\{\pm \frac12\}.$
Let $K(x)$ be the prefix Kolmogorov complexity of a string $x$ (see e.g. $\S 3.1$, [Li and Vitányi 2008] for this definition.) Then there is some constant $c>0$ such that, for all $n$, if $\Omega[1:n]$ is the first $n$ bits of $\Omega$, then K(\Omega[1:n])\ge n-c \qquad\hbox{(Lemma 3.6.2, [Li and Vitányi 2008].) }\qquad(**) But, using a prefix code, we can code the quadruple $(n,p,q,\delta)$ in no more than $2\log_2 q+O(\log \log q)=\frac{2}{\beta}n+O(\log n)$ bits. Therefore, for infinitely many $n$, $ K(\Omega[1:n])\le\frac{2}{\beta}n+O(\log n), $ contradicting (**).
-
0Even though I don't understand your answer yet, I will award you the bounty since its time is running out and you gave the question serious attention, which is what the bounty was for. – 2012-01-23