Statistical Physics of Coding for the Integers
This work addresses compression of integers, which is incremental as it builds on existing coding theory with a novel physics-based interpretation.
The paper tackles the problem of compressing natural numbers using the zeta distribution, developing a statistical-mechanical interpretation and proposing a coding scheme that nearly achieves ideal code length, with asymptotic linearity in entropy and analysis of phase transitions.
We study a paradigm of coding for compression of the natural numbers via the zeta distribution and develop a statistical-mechanical interpretation, both in terms of Hagedorn systems and a Bose gas with energy levels given by logarithms of prime numbers. We also propose a simple coding scheme for the zeta distribution that nearly achieves the ideal code length. For block coding of vectors of natural numbers, we derive the micro-canonical entropy function and demonstrate its asymptotic linearity implying that its behavior is analogous to that of a Hagedorn system. We also derive the large deviations rate function, and provide a formula for the best coding parameter in the large deviations sense. We show that due the Hagedorn-type phase transition there is only partial equivalence of ensembles, due to the degeneration of the domain of the partition function.