Small codes

• Published in: arXiv.org 2023-09
• Main Author: Balla, Igor
• Format: Article
• Language: English
• Subjects: Binary codes
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2305.19047

Determining the maximum number of unit vectors in \(\mathbb{R}^r\) with no pairwise inner product exceeding \(\alpha\) is a fundamental problem in geometry and coding theory. In 1955, Rankin resolved this problem for all \(\alpha \leq 0\) and in this paper, we show that the maximum is \((2+o(1))r\) for all \(0 \leq \alpha \ll r^{-2/3}\), answering a question of Bukh and Cox. Moreover, the exponent \(-2/3\) is best possible. As a consequence, we conclude that when \(j \ll r^{1/3}\), a \(q\)-ary code with block length \(r\) and distance \((1-1/q)r - j\) has size at most \((2 + o(1))(q-1)r\), which is tight up to the multiplicative factor \(2(1 - 1/q) + o(1)\) for any prime power \(q\) and infinitely many \(r\). When \(q = 2\), this resolves a conjecture of Tiet\"av\"ainen from 1980 in a strong form and the exponent \(1/3\) is best possible. Finally, using a recently discovered connection to \(q\)-ary codes, we obtain analogous results for set-coloring Ramsey numbers.