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

Improve or verify the best-known [40,20] linear code over GF(8): current bounds 13 ≤ d ≤ 18

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

Statement

A linear $[n,k]_q$ code is a $k$-dimensional subspace of $\mathbb{F}_{8}^n$; its minimum distance $d$ is the smallest Hamming weight of a nonzero codeword. For $[n,k]=[40,20]$ over $\mathbb{F}_{8}$ the largest achievable minimum distance is unknown: the best-known code has $d=13$ and the best nonexistence (upper) bound is $18$, i.e. $13 \le d_{\max}(40,20) \le 18$. The lower bound is met by an explicit best-known code (a quasi-cyclic construction due to T. A. Gulliver (codetables type 'Gulliver')); the upper bound is a nonexistence bound. Question: construct a linear $[40,20]_{8}$ code with minimum distance $\ge 14$ (a new record, improving the lower bound), or independently verify that the recorded best-known $[40,20,13]_{8}$ code has minimum distance exactly $13$.

Acceptance. FULLY RESOLVES (improve): a generator matrix $G\in\mathbb{F}_{8}^{20\times40}$ with $\mathrm{rank}(G)=20$ whose minimum distance $d'\ge 14$, certified by a minimum-distance computation (e.g. Brouwer–Zimmermann in Magma/GAP/SageMath); $d'=18$ would settle the cell. PARTIAL: independently recompute, with a re-runnable script, the minimum distance of the recorded best-known $[40,20,13]_{8}$ code from its generator matrix and confirm it equals $13$ (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; also mirrored at codetables.markus-grassl.de) — records $13 \le d \le 18$ for $[40,20]_{8}$. The gap $U-L=5$ has stood and the exact optimal distance is open. Source: M. Grassl, Bounds on the minimum distance of linear codes, http://www.codetables.de, cell q=8,n=40,k=20 (accessed 2026-07-05).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.