# How many “compressible” strings are there?

Let's say that a string of length $$N$$ is "compressible" iff its Kolmogorov complexity is less than $$N$$. To keep it simple, we can assume binary strings for this.

It is easy to see that almost all binary strings of length $$N$$ are incompressible by using the pigeonhole principle.

So my question is, how many strings of length $$N$$ are compressible?

In particular, let's assume that $$K(S)$$ is the Kolmogorov complexity of binary string $$S$$, which is of length $$N$$. Then I have the following three questions:

1. Of the $$2^N$$ binary strings $$S$$ of length $$N$$, how many have $$K(S) \leq N-1$$?
2. Of the $$2^N$$ binary strings $$S$$ of length $$N$$, how many have $$K(S) \leq N/2$$?
3. Of the $$2^N$$ binary strings $$S$$ of length $$N$$, how many have $$K(S) \leq \log N$$?

All of the above are for sufficiently large $$N$$.

A simple counting argument shows that the number of strings of length $$N$$ such that $$K(S) \leq M$$ is at most $$2^{M+1}$$.
Conversely, considering the program $$\Pi$$ that gets an integer $$r$$ and a string $$x$$, and outputs $$x$$ together with $$r$$ many zeroes. Going over all strings of length $$\ell$$, this gives us $$2^\ell$$ many strings whose complexity is at most $$\ell + O(\log N)$$. Choosing $$\ell = M - O(\log N)$$, this shows that the number of strings of length $$N$$ such that $$K(S) \leq M$$ is at least $$2^M/N^{O(1)}$$.
This answers your first two questions up to a small multiplicative error. I suspect that the answer to the third one depends heavily on $$N$$.
• thank you for the answer - do you think the third one depends on $N$ beyond just if $N$ is large enough? – Mike Battaglia Nov 19 '19 at 20:19
• It might depend on the Kolmogorov complexity of $N$. – Yuval Filmus Nov 19 '19 at 20:21