Skip to content

The half-rate linear programming bound for binary codes is 1/2-1/π

Sep 2026 · arXiv.org · Vol abs/2609.03736 · 2 citations · ⚡ 1 influential · 22 references
Mathematics Computer Science

Abstract

In their work on sphere packing and the modular bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn-Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/\pi+o(1))\sqrt d$. We prove the binary coding analogue: \[ R_D\!\left(\frac12-\frac1\pi\right)=\frac12. \] We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the smallest radius $r$ for which a nonzero Krawtchouk $(\pm1)$-eigenfunction $f$ exists with $f(0) = 0$ and $f(x) \ge 0$ for all $|x| \ge r$, then \[ \frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1\pi. \] The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.

View source

Similar papers

Sep 2026

A Mirror Vanishing Band for Weight Distributions of Binary Linear Codes

Chen and Xie recently proved, using the Ashikhmin--Barg lemma on minimal vectors, that every binary linear $[n,k,d]$ code with $k=n-2d+2+v$ ($v\ge 0$) has no codewords of weight in the interval $[2d-v,\,2d-1]$. Their argument uses two of the five basic properties of minimal vectors established by Ashikhmin and Barg (19...

Xian-Mang He · 0 citations
Preprint Nov 2026

Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs

We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{\Omega(\sqrt{k})}$. This improves on the prior best lower bound of $2^{\Omega(\sqrt{k/\log k})}$, due to [AG24], and shows that the folklore construction o...

Oliver Janzer, P. Manohar · 1 citation
Preprint Oct 2026

Double circulant LCD codes over $\mathbb{F}_2+u\mathbb{F}_2$ and their related binary LCD codes

Linear complementary dual (LCD) codes are linear codes that intersect their dual trivially. We study double circulant (Euclidean) LCD codes over the finite chain ring $R=\mathbb F_2+u\mathbb F_2$, where $u^2=0$. Using the Chinese Remainder Theorem and the factorization of $x^n-1$, we derive an explicit enumeration form...

Xing-Xing Xu, Bo Wu, Jon-Lark Kim · 0 citations
Sep 2026

Norm-One Torus Decompositions and Decoding of Gashkov-Sidel'nikov Codes

Let $q=3^m$, let $K=\mathbb F_{q^2}$, and let \[\mathcal T=\{x\in K^*:\operatorname{N}_{K/\mathbb F_q}(x)=1\}.\] For both cyclic and constacyclic Gashkov-Sidel'nikov codes, we show that the set of signed parity-check column labels is precisely $\mathcal T$. Consequently, the decoding problem separates into two stages:...

Min-Jia Shi, Shi-Tao Li, Yu-Hong Xia et al. · 0 citations
Preprint Oct 2026

Square-root logarithmic bounds for the arithmetic complexity of factorial multiples

Assume that the Riemann zeta function has no zeros in $\Re(s)>1-\delta$, $s\neq1$, for some fixed $0<\delta\leq1/2$. We prove that, for every sufficiently large integer $k$, a positive multiple $m_k k!$ has arithmetic complexity $\tau(m_k k!)\leq\exp(C\sqrt{\log k\log\log k})$, where $C$ depends only on $\delta$. We fi...

Liang Zhang · 0 citations
Oct 2026

Bounds on polynomial approximations of the discrete logarithm function

We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D...

S. Kopparty, Rishabh Kothary, Ashutosh Shankar · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.