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?

Improve this question
$\endgroup$
4
  • 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
    Commented Jan 25, 2017 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
    Commented Jan 25, 2017 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
    Commented Jan 26, 2017 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
    Commented Jan 26, 2017 at 8:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 26, 2017 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
    Commented Jan 26, 2017 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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