Improve or verify a best-known binary code $A(n,d)$ (linear or nonlinear) with an open gap (e.g. $A(17,4)$)
Statement
Let $A(n,d)$ denote the maximum number of binary vectors of length $n$ with pairwise Hamming distance at least $d$ — over ALL codes, linear or nonlinear. Many entries in the maintained table of $A(n,d)$ have an open gap between the best-known lower bound (a largest explicit code) and the best-known upper bound. Choose such an open case — for instance $A(17,4)$ — and exhibit an explicit binary code (a list of codewords with pairwise distance $\ge d$) whose size matches or exceeds the current best-known lower bound in Brouwer's table, with a verifier — or improve a bound with a certificate.
Acceptance. ADVANCES: for a stated open pair $(n,d)$ from Brouwer's table (e.g. $(17,4)$), a machine-checkable list of $M$ length-$n$ binary vectors for which a verifier confirms (a) all codewords are distinct, (b) every pair has Hamming distance $\ge d$, and (c) $M$ equals or exceeds the current best-known lower bound for $A(n,d)$ recorded in the table at submission time. FULLY RESOLVES: such a code with $M$ strictly exceeding the best-known lower bound (a new record), OR a verifiable improved upper bound (e.g. an LP dual / combinatorial certificate) that strictly lowers the best-known upper bound — ideally closing the gap. Provide the codeword list / certificate plus the verification script and the exact $(n,d)$ and $M$ attacked.
Background
$A(n,d)$ is the fundamental extremal quantity of binary coding theory: the largest packing of Hamming balls of radius $\lfloor (d-1)/2\rfloor$. Unlike the linear $[n,k,d]$ tables (Grassl / codetables.de), $A(n,d)$ allows nonlinear codes, so many records are held by nonlinear constructions and the best lower and upper bounds frequently disagree. The canonical maintained record is Andries Brouwer's table 'Bounds for the size of a binary code' (covering roughly $n\le 28$, even $d$), which lists best-known lower bounds (from explicit/greedy/algebraic/computer-search codes) and upper bounds (from linear programming, shortening/puncturing, and ad hoc arguments), and flags the open gaps. A lower-bound attack is a maximum-clique / ILP / stochastic search over $\{0,1\}^n$ with edges between words at distance $\ge d$; upper bounds come from the Delsarte LP and combinatorial reductions. Verification of a claimed lower bound is a direct scan: confirm all codewords are distinct length-$n$ binary vectors, every pair is at Hamming distance $\ge d$, and count. Matching a recorded best-known size is an independent reproduction of the record; enlarging it is a new record. NOTE: this is the UNRESTRICTED-code table (nonlinear allowed), distinct from best-known LINEAR $[n,k,d]$ tables.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Brouwer, Bounds for the size of a binary code A(n,d) — maintained table (linear & nonlinear) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.