跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.22441 · v1

On the Kissing Number of Craig's Lattice and Spherical List Decoding

首次提交 2026-11-17 17:12
版本更新 2026-11-17 17:12
雷达观测 2026-11-18 19:42
arXiv ↗PDF ↗

摘要

Craig's lattices Ap−1kA_{p-1}^k are a family of lattices with large kissing numbers, i.e., relative to their dimension n=p−1n = p-1, they contain a large number of shortest nonzero vectors. Specifically, for small k=o(log⁡p/log⁡log⁡p)k = o(\log p / \log \log p), a lower bound of Bacher (2015) shows that Ap−1kA_{p-1}^k has a super-polynomial kissing number of ω(nk)ω(n^k). Craig's lattices are therefore attractive candidates for the construction of spherical codes. In this work, we introduce a polynomial-time list decoder for spherical codes obtained from Craig's lattices for angular distance below 45∘45^\circ. Our second main result shows that Bacher's lower bound is asymptotically tight for k=o(log⁡p/log⁡log⁡p)k = o(\log p / \log \log p). Finally, we introduce an efficient algorithm for computing the kissing number of Ap−1kA_{p-1}^k. Using this algorithm, we compute their kissing number in dimensions up to 521. Based on this data, we pose the open question whether the kissing number of Ap−1kA_{p-1}^k with k≈pk \approx \sqrt{p} grows like eΘ(n)e^{Θ(\sqrt{n})} in dimension n=p−1n=p-1. Concurrent work by Laarhoven and Kominers as well as Bennett, Hhan, Li and Stephens-Davidowitz proves such a bound for very closely related lattices.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-17 17:12 · 最新观测版本

On the Kissing Number of Craig's Lattice and Spherical List Decoding

Craig's lattices Ap−1kA_{p-1}^k are a family of lattices with large kissing numbers, i.e., relative to their dimension n=p−1n = p-1, they contain a large number of shortest nonzero vectors. Specifically, for small k=o(log⁡p/log⁡log⁡p)k = o(\log p / \log \log p), a lower bound of Bacher (2015) shows that Ap−1kA_{p-1}^k has a super-polynomial kissing number of ω(nk)ω(n^k). Craig's lattices are therefore attractive candidates for the construction of spherical codes. In this work, we introduce a polynomial-time list decoder for spherical codes obtained from Craig's lattices for angular distance below 45∘45^\circ. Our second main result shows that Bacher's lower bound is asymptotically tight for k=o(log⁡p/log⁡log⁡p)k = o(\log p / \log \log p). Finally, we introduce an efficient algorithm for computing the kissing number of Ap−1kA_{p-1}^k. Using this algorithm, we compute their kissing number in dimensions up to 521. Based on this data, we pose the open question whether the kissing number of Ap−1kA_{p-1}^k with k≈pk \approx \sqrt{p} grows like eΘ(n)e^{Θ(\sqrt{n})} in dimension n=p−1n=p-1. Concurrent work by Laarhoven and Kominers as well as Bennett, Hhan, Li and Stephens-Davidowitz proves such a bound for very closely related lattices.

查看此版本解读 →查看此版本原文 ↗