Almost all positive integers are incompressible:

Given that \(\mathbb{N}\) is countable and the space of binary strings of finite length \(\{0,1\}^*\) is also countable, we may construct a bijection from \(\mathbb{N}\) to \(\{0,1\}^*\). It follows that every positive integer has a unique binary encoding.

Moreover, almost all positive integers are incompressible since:

\begin{equation} \forall n \in \mathbb{N}^* \forall k < n, |\{x \in \{0,1\}^*:K(x) \geq n -k \}| \geq 2^n(1-2^{-k}) \end{equation}

where \(|x| = n\), the binary length of \(x\), which may be understood as the machine-code representation of an integer.

Proof:

Let’s suppose an integer with binary encoding \(x\) has an algorithmic complexity \(K(x) \leq n-k\). Given that the number of binary strings of binary length less than \(n-k\) is \(2^{n-k} - 1 < 2^{n-k}\) we have:

\begin{equation} 2^n - 2^{n-k} = 2^n(1-2^{-k}) \end{equation}

integers with an algorithmic complexity greater than or equal to \(n-k\).

Corollary:

For \(n > k \geq 10\), more than 99.9% of integers have an algorithmic complexity greater than \(n-k\) since:

\begin{equation} 1-\frac{1}{2^{10}} > 99.9\% \end{equation}

From this we may deduce that less than 1% of integers are compressible.

References:

  1. Lance Fortnow. Kolmogorov Complexity. 2000.
  2. Lance Fortnow. Kolmogorov Complexity and Computational Complexity. 2003.