New lower bounds for binary constant-weight codes: $A(23,6,10)\geq 2979$ and $A(24,6,10)\geq 4214$

Christian Lysenstoeen

REVIEW 1 major objections 2 minor 12 references

New lower bounds for binary constant-weight codes: $A(23,6,10)\geq 2979$ and $A(24,6,10)\geq 4214$

T0 review · 1 major / 2 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper constructs explicit binary constant-weight codes that prove A(23,6,10)≥2979 and A(24,6,10)≥4214, exceeding the best surviving codes and two long-lost 1990 bounds.

desk verdict Four new lower bounds backed by unusually rigorous verification; but Theorem 3's model description likely over-constrains and needs fixing before the exactness claim stands. read the letter →

arxiv 2607.19550 v1 pith:EPUWVD3W submitted 2026-07-21 cs.IT math.COmath.IT

Christian Lysenstoeen This is my paper

classification cs.ITmath.COmath.IT MSC 94B6505B4090C27

keywords constant-weightcodeslowerboundsA(ndw)maximum-weightindependentsetcoordinatedecompositionlostcomputationalverificationexchangedryness

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper reports explicit code listings that settle two open lower-bound records for binary constant-weight codes and improve two further entries. By fixing one coordinate half to a known code and selecting the other half via a maximum-weight independent set search on the full compatible pool, the author produces codes of sizes 2979 and 4214 for the (23,6,10) and (24,6,10) cells, surpassing the surviving codes of 2969 and 4174 and the 1990 bounds of 2970 and 4200, whose original listings were lost. The same construction improves A(23,6,11) and A(24,6,8). The paper also proves the incumbent 2969-word code is insertion-maximal and dry under exchanges deleting at most three codewords, and analyzes codes invariant under prime-order permutations, excluding most cycle types. Every bound is backed by multiple independent verifiers and released code files.

What carries the argument

The load-bearing construction is the coordinate decomposition: an (n,d,w) code splits into an (n-1,d,w) code on coordinate 0 and an (n-1,d,w-1) code on coordinate 1, with a cross-compatibility constraint one intersection unit weaker than the internal constraint. Fixing the zero-half to the best known code reduces the search for the one-half to a single maximum-weight independent set problem on the dense graph whose vertices are the cross-pool words and whose edges join words with intersection exceeding the allowed threshold. The search is carried out by a recent dense-graph MWIS heuristic with verified reproducibility, and all produced codes are checked by a dependency-free validator that re

What would settle it

Run the released independent validator on the four code files; if any file's size differs from the stated value, or any pair of words in a file has Hamming distance below 6, the claimed bounds are false. A second falsifier: solve the maximum-weight independent set problem on the specified cross-pool for the (23,6,10) construction and check whether the 796-word solution is actually a compatible set and whether any larger compatible set exists.

Watch

Extended reading notes

Core claim

The central claim is that the four parameter cells admit explicit codes of sizes 2979, 4214, 3539, and 1855, established by a coordinate decomposition: freeze a known code on the last coordinate value 0, then pick the largest possible set of compatible words from the cross-pool on the value 1. The 2979-word code concatenates a 2183-word (22,6,10) code with 796 compatible weight-9 words; the 4214-word code cascades a 2978-word (23,6,10) code with 1236 weight-9 words. The paper further claims the previous 2969-word incumbent is locally optimal in a strong sense: no insertion is possible, no exchange of candidates with at most two blockers improves it, and no hole-refill deleting at most three

Load-bearing premise

The entire result rides on the released code files being exactly what they claim: each file must contain the stated number of distinct words, and the dependency-free validator must compute pairwise Hamming distances correctly; a silent bug in the validator or a mismatched file would invalidate every headline bound.

Editorial extensions

If this is right

If the codes are valid, two of the nine lost 1990 bounds are now re-attained and surpassed, removing them from the open-problems list.
The incumbent 2969-word code cannot be improved by any insertion, any exchange of low-blocker candidates, or any depth-3 hole-refill, local moves that suffice to improve many other cells.
The coordinate-decomposition plus MWIS heuristic is a reproducible template: for cells with small gaps and rich cross-pools it reaches or exceeds values that eluded 35 years of reconstruction.
The released code files let any reader re-verify all four bounds with a dependency-free script.
The four bounds were independently re-verified by the reference table's maintainer, who subsequently improved them via local polishing to 2981, 3550, 1857, and 4216—the paper's own numbers are 2979, 3539, 1855, and 4214.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The success on the two cells suggests that some of the remaining lost 1990 bounds may be attainable with the same decomposition, rather than overcounts; the A(18,6,6) 144-to-133 precedent keeps the overcount possibility alive for others.
The depth-4 exchange problem left open here is a natural next target: if resolved, it would either certify the 2969-word code as exchange-optimal one level deeper or find an improvement.
The method's walls—the large-gap weight-8 chain and the composition-capped weight-12 cell—point to cells where a different construction input or a better cross-pool bound would be needed.
The measured calibration factor for heuristic saturation is based on a single cycle type; extending the calibration to more known cells would sharpen the heuristic evidence against low-order automorphisms.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline results are the four explicit codes, and they are real: A(23,6,10)>=2979, A(24,6,10)>=4214, A(23,6,11)>=3539, A(24,6,8)>=1855. Two of these surpass the long-lost 1990 BSSS bounds, and all four have been independently verified by two in-house checkers, a third dependency-free validator, and Brouwer himself. That is exactly how computational coding theory should be done, and the released code files make the lower bounds checkable by any skeptic. The Johnson decomposition plus CHILS trick is a nice practical advance; it breaks the previous ~660 ceiling on the B-half, and the paper is honest about what is heuristic versus exact. I also appreciate the symmetry analysis: the orbit-based exclusions are properly proven, and the heuristic saturation caps are labeled as measured, not certified.

Now the soft spot. Theorem 3, the depth-3 hole-refill dryness result, is described in a way that looks formally wrong. The text says the model includes "pairwise-conflict cuts xs + xs' <= 1 (43,105 pre-seeded for shared-blocker pairs)." If that means cuts are added for pairs of candidates that share a blocker, then the model is over-constrained: two candidates can both conflict with the same incumbent word yet be mutually compatible, and once that blocker is deleted both could be inserted. Adding such a cut forbids a valid exchange and makes the infeasibility report meaningless. The "soundness of the relaxation" paragraph only justifies lazily omitting conflict cuts; it says nothing about adding invalid ones. The stress-test note has this right. I suspect the phrase is a lazy shorthand for "pre-seeded conflict pairs that were found via blocker overlap," but as written it reads as an invalid constraint set, and the burden is on the author to clarify or re-run. This does not touch the four code-validity claims, which stand on the files, but it undermines the abstract's statement that every improving exchange deleting at most three codewords is excluded. The self-test on A(18,6,6) does not rescue it either, because the same flawed model could plausibly pass that instance.

Minor point: the "solution merges" saturation evidence is heuristic, and the paper does say so, so that is fine. The open items (depth-4, 13+1^10) are appropriately labeled.

Who should read this: anyone working on constant-weight codes or on verified computational combinatorics. It deserves a proper peer review, but not in its current form. I would send it out and ask the author to fix Theorem 3's model description, ideally by replacing the shared-blocker cuts with true pairwise-conflict cuts and re-proving infeasibility. If that fails, the exchange theorem should be retracted or demoted to heuristic, while the four lower bounds remain the paper's solid contribution.

Referee Report

1 major / 2 minor

Summary. The paper constructs explicit binary constant-weight codes demonstrating A(23,6,10) ≥ 2979, A(24,6,10) ≥ 4214, A(23,6,11) ≥ 3539, and A(24,6,8) ≥ 1855, thereby surpassing two bounds from the 1990 BSSS table whose code listings were lost and improving two further cells. The constructions use a Johnson coordinate split with a fixed A-half and a CHILS-selected B-half from the full cross-pool. The paper also reports exact infeasibility results on insertion maximality and depth-3 hole-refill exchanges for the 2969-word incumbent, a symmetry analysis of prime-order automorphisms, a reimplementation of the 1990 improver, and a reproduction-distance analysis. All claimed codes are available as ancillary files, with multiple independent verifiers.

Significance. The four lower bounds are significant if the released code files are valid: they recover two lost 1990 bounds and improve two additional cells, and the explicit code files constitute an unusually verifiable computational result. The paper ships three independent validity checks, including a dependency-free pure-Python validator, and the table's maintainer verified the submissions. The exact exchange and symmetry claims are supported by two solver families and a self-test on A(18,6,6)=133. The CHILS result (reaching B-size 796 versus an earlier perceived cap of ~660) is an instructive demonstration that search-strength saturation can masquerade as structural upper bounds. The reproduction-distance quantification (lexicode 2377 → incumbent 2969 → lost 2970) is a useful community baseline.

major comments (1)

[Section 3, Theorem 3] The computational verification of Theorem 3 states that the CP-SAT model includes 'pairwise-conflict cuts xs + xs′ ≤ 1 (43,105 pre-seeded for shared-blocker pairs)'. Sharing a blocker does not make two candidates mutually incompatible: if the shared blocker is deleted (yc = 1), both candidates can be inserted simultaneously, provided they are themselves at distance at least 6. The linking constraints xs ≤ yc already prevent insertion when the blocker is not deleted; the extra cuts are therefore invalid and over-constrain the model. Consequently the reported infeasibility may be an artifact of these constraints, not a proof that no depth-3 hole-refill improvement exists. The 'soundness of the relaxation' paragraph justifies only the omission of constraints, not the addition of invalid ones. This directly affects the abstract's claim that exact computations 'exclude every improving exchang

minor comments (2)

[Section 7 / code names] Please define the 'H' suffix in code names such as a22.6.10.2183H on first use; presumably it refers to the heuristic origin in Brouwer's table, but it is not stated.
[Abstract and Section 7 note] The abstract's statement 'All four bounds are now listed in Brouwer's online table' is true only for the period before the maintainer's polishing. Since the live table now lists 2981, 3550, 1857, and 4216, consider clarifying that the original codes remain in the table's code archive under the original names.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: lower bounds are sizes of explicitly listed, independently verified code files; no fitted parameter is renamed as prediction.

full rationale

The four lower bounds are established by explicit code files verified by two independent verifiers plus a third dependency-free validator; the final sizes are counts of listed files, not outputs of a fitted model. CHILS only finds a candidate B-half, whose validity is re-checked independently. The local-optimality computations are exact finite checks on a given incumbent, not derived from the target bound. No self-citation is load-bearing: the reference table and CHILS are external artifacts. The 1.25x calibration is explicitly labeled indicative and is not used for the four bounds. The only issue found is a correctness concern in Theorem 3's model: 'pairwise-conflict cuts xs + xs' <= 1 (43,105 pre-seeded for shared-blocker pairs)' appears to add constraints that may be invalid for the depth-3 exchange problem, since sharing a blocker does not itself make two insertions incompatible; if literal, the infeasibility proof would not establish the stated theorem. That concern does not make the main claim circular.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claims rest on explicit code files and the correctness of the verification tooling, not on fitted parameters or invented entities. The only fitted number (1.25× calibration) is explicitly labeled indicative and used only for heuristic saturation estimates, not in any theorem or exact bound.

free parameters (1)

heuristic saturation calibration factor = 1.25 (approx)
Section 4: measured on the known 23-cycle type to correct greedy-only probes; explicitly labeled 'indicative rather than certified'; not used in any theorem or exact bound.

assumptions (5)

standard math Standard equivalence: for even d, d(u,v)≥d iff |u∩v|≤w−d/2.
Section 1, used throughout to convert distance to intersection constraints.
standard math Johnson decomposition splits an (n,d,w) code into an (n−1,d,w) and (n−1,d,w−1) code with cross-constraint |a∩b|≤w−d/2.
Section 5; the construction's backbone.
domain assumption The published codes a22.6.10.2183H, a22.6.11.2636H, a23.6.8.1439H, and the prior 2978-word code are valid codes as stated in Brouwer's table and in this paper.
Section 5; the new codes are built by fixing these A-halves; if any is invalid, the corresponding lower bound is unsupported.
domain assumption CP-SAT, CBC, and SCIP return correct optimality/infeasibility certificates for the models described.
Sections 3-4; exact theorems rely on solver outputs; cross-checked across two solver families but ultimately trust in solver correctness is assumed.
domain assumption The independent verifier and the validator scripts correctly implement minimum-distance checks.
Sections 2 and 7; all four code files are validated by these scripts; a bug in the validator would invalidate the claimed sizes.

how reviews work

0 comments

Cite this review

Pith. "Pith review of New lower bounds for binary constant-weight codes: $A(23,6,10)\geq 2979$ and $A(24,6,10)\geq 4214$." pith.science (2026). https://pith.science/paper/EPUWVD3W

@misc{pith2026260719550,
  author       = {Pith},
  title        = {Pith review of: New lower bounds for binary constant-weight codes: $A(23,6,10)\geq 2979$ and $A(24,6,10)\geq 4214$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EPUWVD3W}},
  note         = {Machine review of arXiv:2607.19550}
}

abstract

Let $A(n,d,w)$ denote the maximum size of a binary constant-weight code of length $n$, minimum distance $d$, and weight $w$. We construct explicit codes proving $A(23,6,10)\ge 2979$ and $A(24,6,10)\ge 4214$. These improve the best surviving explicit codes of sizes 2969 and 4174 and surpass the corresponding 1990 bounds 2970 and 4200 of Brouwer, Shearer, Sloane and Smith, whose code listings were lost. We also obtain $A(23,6,11)\ge 3539$ and $A(24,6,8)\ge 1855$. All four bounds are now listed in Brouwer's online table. The constructions use a coordinate decomposition in which one half is fixed to a known code and the complementary half is selected from its full cross-compatible pool using CHILS for maximum-weight independent set. For the 2969-word $A(23,6,10)$ incumbent, exact computations with two solver families prove insertion maximality and exclude every improving exchange deleting at most three codewords. We also analyze codes invariant under prime-order permutations: several cycle types are excluded exactly, the $5+1^{18}$ type has upper bound 499, and reproducible heuristic saturation evidence is reported for the remaining types, with $13+1^{10}$ left open. Code files, an independent validator, model descriptions, and computational logs are released.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

12 extracted references · 2 linked inside Pith

[1]

A. E. Brouwer, J. B. Shearer, N. J. A. Sloane, and W. D. Smith,A new table of constant weight codes, IEEE Trans. Inform. Theory36(1990), no. 6, 1334–1380

1990
[2]

A. E. Brouwer,Bounds for binary constant weight codes, online table, https://aeb.win. tue.nl/codes/Andw.html
[3]

Großmann, K

E. Großmann, K. Langedal, and C. Schulz,Concurrent iterated local search for the maximum weight independent set problem, Proc. 23rd International Symposium on Experimental Algorithms (SEA 2025), LIPIcs vol. 338, Schloss Dagstuhl, 2025, pp. 22:1–22:18. Extended version: arXiv:2412.14198

arXiv 2025
[4]

E. S. Kramer and D. M. Mesner, t-designs on hypergraphs, Discrete Math.15(1976), 263–296

1976
[5]

Braun, J

M. Braun, J. Humpich, A. Laaksonen, and P. R. J. ¨Osterg˚ ard,New lower bounds on binary constant weight error-correcting codes, J. Combin. Math. Combin. Comput.111(2019), 213–223

2019
[6]

Agrell, A

E. Agrell, A. Vardy, and K. Zeger,Upper bounds for constant-weight codes, IEEE Trans. Inform. Theory46(2000), no. 7, 2373–2395

2000
[7]

Schrijver,New code upper bounds from the Terwilliger algebra and semidefinite program- ming, IEEE Trans

A. Schrijver,New code upper bounds from the Terwilliger algebra and semidefinite program- ming, IEEE Trans. Inform. Theory51(2005), no. 8, 2859–2866

2005
[8]

H. K. Kim and P. T. Toan,Improved semidefinite programming bound on sizes of codes, IEEE Trans. Inform. Theory59(2013), no. 11, 7337–7345

2013

Show all 12 references

[9]

S. C. Polak,Semidefinite programming bounds for constant-weight codes, IEEE Trans. Inform. Theory65(2019), no. 1, 28–38

2019
[10]

Perron and F

L. Perron and F. Didier,CP-SAT(part of Google OR-Tools), Google, https://developers. google.com/optimization
[11]

Forrest et al.,COIN-OR CBC (branch-and-cut MIP solver), https://github.com/ coin-or/Cbc

J. Forrest et al.,COIN-OR CBC (branch-and-cut MIP solver), https://github.com/ coin-or/Cbc
[12]

Bolusani et al.,The SCIP Optimization Suite 9.0, Technical Report, Zuse Institute Berlin, 2024, arXiv:2402.17702.https://scipopt.org

S. Bolusani et al.,The SCIP Optimization Suite 9.0, Technical Report, Zuse Institute Berlin, 2024, arXiv:2402.17702.https://scipopt.org. 9

2024 arXiv

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

A. E. Brouwer, J. B. Shearer, N. J. A. Sloane, and W. D. Smith,A new table of constant weight codes, IEEE Trans. Inform. Theory36(1990), no. 6, 1334–1380

1990

[2] [2]

A. E. Brouwer,Bounds for binary constant weight codes, online table, https://aeb.win. tue.nl/codes/Andw.html

[3] [3]

Großmann, K

E. Großmann, K. Langedal, and C. Schulz,Concurrent iterated local search for the maximum weight independent set problem, Proc. 23rd International Symposium on Experimental Algorithms (SEA 2025), LIPIcs vol. 338, Schloss Dagstuhl, 2025, pp. 22:1–22:18. Extended version: arXiv:2412.14198

arXiv 2025

[4] [4]

E. S. Kramer and D. M. Mesner, t-designs on hypergraphs, Discrete Math.15(1976), 263–296

1976

[5] [5]

Braun, J

M. Braun, J. Humpich, A. Laaksonen, and P. R. J. ¨Osterg˚ ard,New lower bounds on binary constant weight error-correcting codes, J. Combin. Math. Combin. Comput.111(2019), 213–223

2019

[6] [6]

Agrell, A

E. Agrell, A. Vardy, and K. Zeger,Upper bounds for constant-weight codes, IEEE Trans. Inform. Theory46(2000), no. 7, 2373–2395

2000

[7] [7]

Schrijver,New code upper bounds from the Terwilliger algebra and semidefinite program- ming, IEEE Trans

A. Schrijver,New code upper bounds from the Terwilliger algebra and semidefinite program- ming, IEEE Trans. Inform. Theory51(2005), no. 8, 2859–2866

2005

[8] [8]

H. K. Kim and P. T. Toan,Improved semidefinite programming bound on sizes of codes, IEEE Trans. Inform. Theory59(2013), no. 11, 7337–7345

2013