2
$\begingroup$

Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. But:

I want to prove that sequence $\{ax+b\}_{x\in\mathbb{N}}$ contains an infinite subsequence of random numbers. (This is, more-or-less, a statement in an exercise).

EDIT: The actual statement is to show that $\limsup\limits_{x\to\infty}\frac{C_U(ax+b)}{\log (ax+b)}=1$.

I believe the existance of infinitely many random numbers in general, stems from the fact that for a given $k$ we have $|\{x\in\{0,1\}^k: C_U(x)< k\}|< 2^k$ because there are less binary strings of length $\leq k-1$ which may represent input to $U$. So no matter how large a binary representation, we can always find a random number with such a representation (in terms of its length). So, assuming longer $x$ means larger number it represents, we have infinitely many random numbers.

But what about here? We'd want those numbers to be of very specific form. Is there a way to do that? Could you give me a hint?

$\endgroup$
  • 1
    $\begingroup$ When is a sequence of increasing natural numbers Kolmogorov-random? I only know the definition for a bit sequence. If the natural numbers are the positions of 1, then for $a > 1$ every subsequence will not be Kolmogorov-random, since the complexity of the $n$th prefix is at most $n/2 + O(1)$. $\endgroup$ – Yuval Filmus Jan 25 '17 at 21:26
  • $\begingroup$ I mean, I'm looking for a sequence in which all the numbers are Kolmogorov-random. And a number $n$ is random if $C_U(n)\geq \log n$. Which is equivalent to saying that it's binary representation $x$ satisfies $C_U(x)\geq |x|$. $\endgroup$ – Jules Jan 25 '17 at 21:42
  • 1
    $\begingroup$ Suppose that $a = 2^m$ and $b = 0$. The binary representation of $ax$ is thus $\|x\|0^m$, where $\|x\|$ is the binary representation of $x$. The Kolmogorov complexity of this string is at most $\log x+O(\log m+1)$, whereas $\log(ax) = \log x + m$. For large enough $m$, this shows that no number of the form $ax$ can be random. $\endgroup$ – Yuval Filmus Jan 26 '17 at 8:00
  • $\begingroup$ That is insightful, thank you. Which means my intuition to how to solve the problem was wrong :( I changed the content of the post to be more specific. $\endgroup$ – Jules Jan 26 '17 at 8:57
2
$\begingroup$

If $x$ is Kolmogorov random then $C_U(ax+b) \geq \log x - O(\log a + \log b + 1)$ (why?), and so $$ \frac{C_U(ax+b)}{\log (ax+b)} \geq \frac{\log x - O(\log a + \log b + 1)}{\log x + O(\log a + \log b + 1)} = 1 - O\left(\frac{\log a + \log b + 1}{\log x}\right). $$ Since there are infinitely many Kolmogorov random numbers $x$, your result follows.

$\endgroup$
  • $\begingroup$ So, my problem was that I assumed the numbers have to be random, whereas it just suffices that they were "nearly random", i.e. within an additive constant? $\endgroup$ – Jules Jan 26 '17 at 9:08
  • $\begingroup$ That's right. In fact, in most applications it suffices to consider a string $x$ to be random if its Kolmogorov complexity is at least $|x|-C$ for some arbitrary constant $C$. $\endgroup$ – Yuval Filmus Jan 26 '17 at 9:14

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.