Improve or verify a best-known binary constant-weight code $A(n,d,w)$ with an open gap (e.g. $A(20,6,7)$)
Statement
Let $A(n,d,w)$ denote the maximum number of binary vectors of length $n$, each of Hamming weight exactly $w$, with pairwise Hamming distance at least $d$. Many entries of the maintained table of $A(n,d,w)$ 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(20,6,7)$ — and exhibit an explicit constant-weight code (a list of weight-$w$ binary codewords, pairwise distance $\ge d$) whose size matches or exceeds the current best-known lower bound in Brouwer's table — or improve a bound with a verifiable certificate.
Acceptance. ADVANCES: for a stated open triple $(n,d,w)$ from Brouwer's table (e.g. $(20,6,7)$), a machine-checkable list of $M$ length-$n$ binary vectors for which a verifier confirms (a) every codeword has Hamming weight exactly $w$, (b) every pair has Hamming distance $\ge d$, and (c) $M$ equals or exceeds the current best-known lower bound for $A(n,d,w)$ 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/Delsarte dual 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,w)$ and $M$ attacked.
Background
Constant-weight codes are central to combinatorial coding theory (design theory, tabu/covering constructions, etc.). $A(n,d,w)$ is the size of the largest binary code with all codewords of weight $w$ and minimum distance $d$; because such a code corresponds to a packing of $w$-subsets, lower bounds come from explicit constructions (Steiner systems, cyclic/lexicographic codes, clique search in the Johnson graph, ILP) and upper bounds from linear-programming (Delsarte) and combinatorial arguments. The canonical maintained record is Andries Brouwer's table 'Bounds on A(n,d,w)' (with per-distance sections $d=4,6,8,\dots$), listing lower and upper bounds and linking the extremal constructions; the entry-level gaps (lower < upper) are the open problems. For even $d$ the relevant range is $d=2\delta$; a workstation attack on a lower bound is a maximum-clique / ILP search over the $\binom{n}{w}$ weight-$w$ words where two words are compatible iff their distance is $\ge d$ (equivalently their intersection is small enough). Verification of a claimed lower bound is a direct $O(M^2 n)$ scan: confirm every codeword has weight exactly $w$ and every pair is at distance $\ge d$, then count. This is the classic improve-or-verify-a-record vein: matching a recorded best-known code is an independent reproduction; enlarging it is a new record. NOTE: this table concerns UNRESTRICTED constant-weight codes and is distinct from the linear $[n,k,d]$ best-known-code tables.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Brouwer, Bounds on A(n,d,w) — maintained table of binary constant-weight codes | website |
| REF-02 | Edel, Rains & Sloane — constructions used in constant-weight/kissing tables (context) | doi |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.