Ramezanpour A, Zecchina R
Physics Department and Center for Computational Sciences, Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Torino, Italy.
Phys Rev E Stat Nonlin Soft Matter Phys. 2012 Feb;85(2 Pt 1):021106. doi: 10.1103/PhysRevE.85.021106. Epub 2012 Feb 6.
In this paper we study the hard sphere packing problem in the Hamming space by the cavity method. We show that both the replica symmetric and the replica symmetry breaking approximations give maximum rates of packing that are asymptotically the same as the lower bound of Gilbert and Varshamov. Consistently with known numerical results, the replica symmetric equations also suggest a crystalline solution, where for even diameters the spheres are more likely to be found in one of the subspaces (even or odd) of the Hamming space. These crystalline packings can be generated by a recursive algorithm which finds maximum packings in an ultrametric space. Finally, we design a message passing algorithm based on the cavity equations to find dense packings of hard spheres. Known maximum packings are reproduced efficiently in nontrivial ranges of dimensions and number of spheres.
在本文中，我们通过腔方法研究汉明空间中的硬球填充问题。我们表明，复制对称和复制对称破缺近似都给出了填充的最大速率，其渐近地与吉尔伯特和瓦尔沙莫夫的下界相同。与已知的数值结果一致，复制对称方程还暗示了一种晶体解，其中对于偶数直径，球体更有可能出现在汉明空间的子空间（偶数或奇数）之一中。这些晶体填充可以通过一种递归算法生成，该算法在超度量空间中找到最大填充。最后，我们基于腔方程设计了一种消息传递算法来找到硬球的密集填充。在维度和球体数量的非平凡范围内，已知的最大填充能够被高效地重现。
