Small codes

Abstract

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 \le 0$ and in this paper, we show that the maximum is $(2+o(1))r$ for all $0\le \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äväinen 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.

7 pages; bounds for all q are obtained, presentation is improved

References in corpus (1)

• Sphere packing bounds via spherical codes