Lattice packings of cross-polytopes from Reed-Solomon codes and Sidon sets. (English) Zbl 1539.11096
Packings for the \(L_1\) metric are considered, that is packing of cross polytopes. The Minkowski-Hlawka lower bound for the density of such packings is \(2^{-n+o(n)}\). But this construction is non-constructive.
The previous construction of packings had asymptotic densities of the form \(2^{ -n \ln \ln n + O(n)}\) for dimension \(n = (p - 1) / 2\).
The authors give two constructions which are better by a factor \(2^{n / (\ln n) (1 + o(1))}\). The first construction is based on Reed-Solom codes and the notion of Sidon sets in abelian groups.
The previous construction of packings had asymptotic densities of the form \(2^{ -n \ln \ln n + O(n)}\) for dimension \(n = (p - 1) / 2\).
The authors give two constructions which are better by a factor \(2^{n / (\ln n) (1 + o(1))}\). The first construction is based on Reed-Solom codes and the notion of Sidon sets in abelian groups.
Reviewer: Mathieu Dutour Sikirić (Zagreb)
MSC:
| 11H31 | Lattice packing and covering (number-theoretic aspects) |
| 52C17 | Packing and covering in \(n\) dimensions (aspects of discrete geometry) |
| 05B40 | Combinatorial aspects of packing and covering |
| 11B83 | Special sequences and polynomials |
| 11H71 | Relations with coding theory |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
References:
| [1] | R. C.Bose and S.Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv.37 (1962), no. 1, 141-147. · Zbl 0109.03301 |
| [2] | J. H.Conway and N. J. A.Sloane, Sphere Packings, Lattices and Groups, 3rd ed., Springer, Berlin, 1999. · Zbl 0915.52003 |
| [3] | R.Crandall and C.Pomerance, Prime Numbers, A Computational Perspective, 2nd ed., Springer, Berlin, 2005. · Zbl 1088.11001 |
| [4] | N. D.Elkies, A. M.Odlyzko, and J. A.Rush, On the packing densities of superballs and other bodies, Invent. Math.105 (1991), no. 1, 613-639. · Zbl 0736.52008 |
| [5] | N.Gargava and V.Serban, Dense packings via lifts of codes to division rings. https://doi.org/10.48550/arXiv.2111.03684 · doi:10.48550/arXiv.2111.03684 |
| [6] | S. W.Golomb and L. R.Welch, Perfect codes in the Lee metric and the packing of polyominoes, SIAM J. Appl. Math.18 (1970), no. 2, 302-317. · Zbl 0192.56302 |
| [7] | R.Granger, T.Kleinjung, and J.Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Trans. Amer. Math. Soc.370 (2018), no. 5, 3129-3145. · Zbl 1428.11210 |
| [8] | P. M.Gruber and C. G.Lekkerkerker, Geometry of Numbers, 2nd ed., North‐Holland, Amsterdam, 1987. · Zbl 0611.10017 |
| [9] | T.Kleinjung and B.Wesolowski, Discrete logarithms in quasi‐polynomial time in finite fields of fixed characteristic, J. Amer. Math. Soc.35 (2022), no. 2, 581-624. · Zbl 1487.11113 |
| [10] | M.Kovačević and V. Y. F.Tan, Improved bounds on Sidon sets via lattice packings of simplices, SIAM J. Discrete Math.31 (2017), no. 3, 2269-2278. · Zbl 1384.11017 |
| [11] | M.Kovačević and V. Y. F.Tan, Codes in the space of multisets—coding for permutation channels with impairments, IEEE Trans. Inform. Theory64 (2018), no. 7, 5156-5169. · Zbl 1401.94100 |
| [12] | S. N.Litsyn and M. A.Tsfasman, Constructive high‐dimensional sphere packings, Duke Math. J.54 (1987), no. 1, 147-161. · Zbl 0638.10032 |
| [13] | K.O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin.#DS11 (2004), 39 (electronic). · Zbl 1142.11312 |
| [14] | C. A.Rogers, Packing and Covering, Cambridge Univ. Press, Cambridge, 1964. · Zbl 0176.51401 |
| [15] | R. M.Roth, Introduction to Coding Theory, Cambridge Univ. Press, Cambridge, 2006. · Zbl 1092.94001 |
| [16] | R. M.Roth and P. H.Siegel, Lee‐metric BCH codes and their application to constrained and partial‐response channels, IEEE Trans. Inform. Theory40 (1994), no. 4, 1083-1096. · Zbl 0816.94023 |
| [17] | J. A.Rush, A lower bound on packing density, Invent. Math.98 (1989), 499-509. · Zbl 0659.10033 |
| [18] | J. A.Rush, Constructive packings of cross polytopes, Mathematika38 (1991), no. 2, 376-380. · Zbl 0757.52016 |
| [19] | J. A.Rush, A bound, and a conjecture, on the maximum lattice‐packing density of a superball, Mathematika40 (1993), no. 1, 137-143. · Zbl 0785.52007 |
| [20] | V.Shoup, Searching for primitive roots in finite fields, Math. Comp.58 (1992), no. 197, 369-380. · Zbl 0747.11060 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
