Research · Papers · Exact answers in open problems · ML-096
Bounds and search limits on the constant-weight code size A(13,4,5)
A(13,4,5) ∈ [123, 129]
Published 2026-09-06
For everyone
Plain summary
A binary constant-weight code is a set of equal-length binary sequences that all contain the same number of ones and differ from each other by at least a set number of positions. Finding the largest possible code for given parameters is a classic coding theory problem. For length 13, weight 5, and minimum difference 4, this maximum size is written A(13,4,5) and sits between 123 and 129.
Local search finds two distinct codes of size 123 within seconds, but three 25-minute runs failed to reach size 124. Automated solvers trying to prove size 129 impossible timed out between 1500 and 1800 seconds. Extending 17 known optimal length-12 codes through a 13th coordinate adds at most 38 words, whereas reaching size 129 requires 49. If those 17 codes cover every optimal length-12 configuration, the maximum size cannot exceed 128.
Result
The maximum size of a binary constant-weight code with length 13, minimum Hamming distance 4, and weight 5 satisfies:
A(13,4,5) ∈ [123, 129]
If the 17 sampled optimal (12,4,5) codes of size 80 cover all isomorphism classes of optimal (12,4,5) codes, then:
A(13,4,5) ≤ 128
Setting and definitions
Let A(n,d,w) be the maximum size of a binary code of length n, minimum Hamming distance d, and constant weight w. An (n,d,w) code is a subset of GF(2)ⁿ whose codewords all have Hamming weight w and pairwise distance at least d.
Shortening an (n,d,w) code on coordinate i isolates the codewords with a zero at that position, forming an (n-1,d,w) code on the remaining coordinates. Codewords with a one at coordinate i form extension blocks that project to an (n-1,d,w-1) code.
Method
Lower bounds were tested with local search. The procedure produced two non-isomorphic codes of size 123 within seconds. Three separate 25-minute search runs failed to construct a code of size 124.
Upper bounds were evaluated using CDCL SAT solvers:
- Direct refutations at size 129 with lexicographic-leader symmetry breaking timed out between 1500 and 1800 seconds across two solvers.
- Shortening-anchored encodings at size 129, which fix an optimal 80-word (12,4,5) subcode across 12 coordinates, also timed out between 1500 and 1800 seconds on two solvers.
- For comparison on synthesis, CDCL was tasked with building an optimal 80-block code at n = 12 and failed to terminate within 10 minutes, whereas local search finds one in 5 seconds.
Extension analysis was performed on 17 sampled optimal (12,4,5) codes of size 80. Each sample admits at most 38 extension blocks through a 13th coordinate. Constructing a code of size 129 requires an optimal 80-word shortening and 49 extension blocks (80 + 49 = 129).
Discussion
CDCL solvers fail on both synthesis and refutation for these parameters. They cannot construct optimal n = 12 codes within 10 minutes and time out on size-129 refutations at n = 13.
The upper bound of 128 remains conditional because the register lacks an exhaustive classification of all optimal (12,4,5) codes of size 80. If an unclassified optimal (12,4,5) code permits 49 extension blocks, size 129 remains viable. Resolving the bound requires solving the anchored SAT instance or classifying all optimal (12,4,5) codes.
For everyone — the takeaway
What this means
Pinning down the exact capacity of this code is stalled by search limits. Heuristic search finds 123-word configurations almost instantly but cannot reach 124. Logic solvers cannot finish checking whether 129 words is possible. Structural tests suggest the ceiling is at most 128, but proving that requires classifying all optimal length-12 building blocks.
Attribution and prior art
Register references
- Register entry: ML-096
- Companion entry: MF-191
- Receipt lane:
lanes/cwcode-13-4-5/WALL.md - Receipt directory:
receipts/
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 (3 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.