Cavity approach to sphere packing in Hamming space.

Area of Science:

• Statistical Mechanics
• Information Theory
• Combinatorial Optimization

Background:

• The hard sphere packing problem is a fundamental challenge in discrete geometry and statistical physics.
• Understanding packing densities and structures in high-dimensional spaces like Hamming space is crucial for applications in coding theory and data compression.

Purpose of the Study:

• To investigate hard sphere packing in Hamming space using the cavity method.
• To determine the maximum packing rates and analyze the resulting structures.
• To develop efficient algorithms for finding dense packings.

Main Methods:

• Application of the cavity method, including replica symmetric (RS) and replica symmetry breaking (RSB) approximations.
• Analysis of asymptotic behavior of packing rates.
• Development of a recursive algorithm for crystalline packings in ultrametric spaces.
• Design of a message-passing algorithm based on cavity equations.

Main Results:

• Both RS and RSB approximations yield maximum packing rates asymptotically matching the Gilbert-Varshamov lower bound.
• The RS approximation predicts crystalline solutions where spheres occupy specific subspaces based on diameter parity.
• A recursive algorithm effectively generates these crystalline packings in ultrametric spaces.
• The message-passing algorithm efficiently reproduces known maximum packings across various dimensions and sphere counts.

Conclusions:

• The cavity method provides accurate predictions for hard sphere packing in Hamming space.
• Identified crystalline structures offer a pathway to constructing efficient packing algorithms.
• The developed message-passing algorithm demonstrates practical utility for finding dense sphere packings.