Loop corrections for hard spheres in Hamming space
Abolfazl Ramezanpour, Saman Moghimi-Araghi · Journal of Statistical Mechanics Theory and Experiment · 2025
Abstract We begin with an exact expression for the entropy of a system of hard spheres within the Hamming space. This entropy relies on probability marginals, which are determined by an extended set of belief propagation (BP) equations. The BP probability marginals are functions of auxiliary variables that are introduced to model the effects of loopy interactions on a tree-structured interaction graph. We explore various reasonable and approximate probability distributions, ensuring that they align with the exact solutions of the BP equations. Our approach is based on an ansatz for (in)homogeneous cavity marginals respecting the permutation symmetry of the problem. Through a thorough analysis, we aim to minimize errors in the BP equations. Our findings support the conjecture that the maximum packing density asymptotically conforms to the lower bound proposed by Gilbert and Varshamov. The presented formulation of the problem is useful to obtain upper bounds for the packing entropy within a class of BP probability marginals. Moreover, it enables different approximations in both the structure of BP messages and the role of auxiliary variables.