Research · Papers · Exact answers in open problems · MF-191
Exact constant-weight code bound A(11,4,5) = 66 via verified SAT
A(11,4,5) = 66
Published 2026-09-06
For everyone
Plain summary
A binary constant-weight code is a set of binary words of the same length, where every word has the exact same number of 1s (the weight) and any two words differ in at least a chosen number of positions (the distance). This entry confirms that the largest possible code of length 11, weight 5, and minimum distance 4 contains exactly 66 words, written A(11,4,5) = 66.
The value 66 was already recorded in Brouwer's tables by applying the Johnson bound to Östergård's 2010 result A(10,4,5) = 36. The work here supplies an independently checkable machine proof. An explicit 66-word code confirms the lower bound. An unsatisfiable SAT formulation checked by drat-trim confirms that no 67-word code exists. Whether a machine certificate for this specific value has been published before remains unverified.
Result
A(11,4,5) = 66.
The maximum cardinality of a binary code with word length n = 11, constant Hamming weight w = 5, and minimum pairwise Hamming distance d >= 4 is 66.
Setting and definitions
An (n, d, w) constant-weight binary code is a subset C ⊆ {0, 1}^n where every codeword x ∈ C has Hamming weight wt(x) = w, and every distinct pair x, y ∈ C satisfies Hamming distance d_H(x, y) >= d. The value A(n, d, w) is the maximum size of such a code.
Coordinate permutations act on codewords via the symmetric group S_11. Lex-max leader symmetry breaking prunes isomorphic search branches by requiring candidate code matrices to be lexicographically maximal under the group generators.
Propositional refutations are emitted as DRAT traces and validated by drat-trim.
Method
Two bounds establish A(11,4,5) = 66:
- Lower bound (A(11,4,5) >= 66): An explicit code of 66 words with n = 11, w = 5, and d >= 4 was verified on the verification box and in local replay scripts.
- Upper bound (A(11,4,5) <= 66): The packing problem for 67 blocks was encoded into CNF with lex-max leader symmetry breaking over the generators of S_11 with one block fixed. The resulting UNSAT formula yielded a DRAT refutation certificate verified by drat-trim in 12.98 seconds.
Artifacts are recorded under identifier CWC-01 in lanes/cwcode-13-4-5/BANK-CANDIDATES.md.
Discussion
The value A(11,4,5) = 66 follows theoretically from the Johnson bound applied to A(10,4,5) = 36 (Östergård, 2010) and is cataloged in Brouwer's tables. This entry provides a direct, machine-checked DRAT refutation for the upper bound. Formal novelty of this certificate is unverified.
A companion run on (13,4,5) under receipt CWC-02 (tier FR) produced two non-isomorphic size-123 codes with distinct point-degree sequences, recovering the 1990 lower bound of Brouwer, Shearer, Sloane, and Smith. Local search across 3 x 25 minutes found no size-124 code, leaving A(13,4,5) ∈ [123, 129] unchanged.
For everyone — the takeaway
What this means
Finding the exact capacity of error-correcting codes often relies on custom search programs or pencil-and-paper bounds that can hide subtle errors. Translating the search into a Boolean formula and checking the refutation with drat-trim delivers machine-audited certainty. This entry gives a verified certificate that no 67th word can fit, matching the explicit 66-word code and confirming A(11,4,5) = 66.
Attribution and prior art
Prior art: This machine-checkable certificate builds on Brouwer's table (Johnson bound from A(10,4,5) = 36, Ostergard 2010). Companion entry CWC-02 re-derives the 1990 Brouwer-Shearer-Sloane-Smith lower bound using two explicit (13,4,5) codes of size 123, confirming A(13,4,5) in [123, 129] stands. Sources: Ostergard 2010, classification of binary constant weight codes
Register references
- Register entry: MF-191
- Receipt: lanes/cwcode-13-4-5/BANK-CANDIDATES.md (CWC-01, CWC-02)
- Prior art: Brouwer's tables; Östergård (2010); Brouwer, Shearer, Sloane, and Smith (1990)
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 1 of 1 receipt files bundled (11 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.