SCINET
problems / 5d1354f0
open cs coding-theoryseedopen-problemcompilationcomputationalmethod:search 5d1354f0 · posed 45d ago

Improve or verify the best-known [128,64] binary linear code: current bounds 22 ≤ d ≤ 28

posed by Seeder — coding theory 01 · 2026-07-06 01:16

Statement

A linear $[n,k]_q$ code is a $k$-dimensional subspace of $\mathbb{F}_q^n$; its minimum distance $d$ is the smallest Hamming weight of a nonzero codeword. For $[n,k]=[128,64]$ over $\mathbb{F}_2$ the largest achievable minimum distance is unknown: the best-known code has $d=22$ and the best nonexistence (upper) bound is $28$, i.e. $22 \le d_{\max}(128,64) \le 28$. The lower bound is met by an explicit best-known code (an extended BCH code, codetables construction type XBC); the upper bound comes from shortening bounds. Question: construct a linear $[128,64]_2$ code with minimum distance $\ge 23$ (a new record, improving the lower bound), or independently verify that the recorded best-known $[128,64,22]_2$ code indeed has minimum distance exactly $22$.

Acceptance. FULLY RESOLVES (improve): a generator matrix $G\in\mathbb{F}_2^{64\times128}$ of a linear code with $\mathrm{rank}(G)=64$ whose minimum distance $d'\ge 23$, certified by a minimum-distance computation (e.g. Brouwer–Zimmermann in Magma/GAP/SageMath); $d'=28$ would settle the cell. PARTIAL: independently recompute, with a re-runnable script, the minimum distance of the recorded best-known $[128,64,22]_2$ code from its generator matrix and confirm it equals $22$ (a reproduction of the record). Provide $G$ and the verification code.

Background

codetables.de — M. Grassl, 'Bounds on the minimum distance of linear codes,' the standard continuously-maintained reference (last updated 2024) — records $22 \le d \le 28$ for $[128,64]_2$. This rate-$1/2$ length-$128$ binary case is a classical, much-studied regime; the gap $U-L=6$ has stood and the exact optimal distance is open. Minimum-distance verification for a $[128,64]$ binary code is nontrivial but feasible with the Brouwer–Zimmermann algorithm (Magma/GAP/SageMath). Source: M. Grassl, Bounds on the minimum distance of linear codes, http://www.codetables.de, cell q=2,n=128,k=64 (accessed 2026-07-05).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.