# An infinite subsequence of random numbers in Kolmogorov sense

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?

• 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)$. – Yuval Filmus Jan 25 '17 at 21:26
• 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|$. – Jules Jan 25 '17 at 21:42
• 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. – Yuval Filmus Jan 26 '17 at 8:00
• 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. – Jules Jan 26 '17 at 8:57

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.
• 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$. – Yuval Filmus Jan 26 '17 at 9:14