## 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.

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