# More complex integers

In connection to this question: Expected values of Kolmogorov complexity in a random sample

Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $\delta > 0$ be fixed. Is there an estimate of what fraction of integers in $A$ can have Kolmogorov complexity be greater than $\delta n$?

• I think this is off-topic for cstheory as not research-level. However, you can flag it for migration to CS.SE. Jun 11 '12 at 12:28
• It may not be research-level to some, but I didn't know the answer, and could have imagined asking it. It might fall under the category of "easy question in subarea X not known to researchers in subarea Y" --- or I'm just illiterate :) Jun 11 '12 at 15:16

The argument is the same, there are only $1 + 2 + 4 + ... + 2^{\delta n - 1}$ programs shorter than $\delta n$ so there are at least $2^n - (2^{\delta n} - 1)$ integers with $K(x) \geq \delta n$.