God made the integers…-Kronecker

As an immediate corollary of Chaitin’s theorem that for almost all integers \(n \in \mathbb{N}\):

\begin{equation} K_U(n) \sim \log_2(n) \end{equation}

we may use the unique prime factorisation theorem to deduce that all the information in the integers is stored in the prime numbers. That is, for almost all \(n \in \mathbb{N}\):

\begin{equation} n = \prod_{i=1}^k p_i^{\alpha_i} \implies K_U(n) \sim \sum_{i=1}^k \alpha_i \cdot \log_2 p_i \end{equation}

which is consistent with the Law of Conservation of Information. Thus, Chaitin’s theorem that almost all integers are incompressible provides us with a non-trivial information-theoretic interpretation of the unique prime factorisation theorem.