Pith. sign in

REVIEW 4 minor 23 references

Asymptotically optimal constant weight codes with even distance

T0 review · 0 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read For even minimum distance, constant-weight codes attain the classical upper bound asymptotically.

desk verdict A short, clean proof of the even-distance constant weight code bound that answers an open question; the pair-codegree estimate is terse but correct. read the letter →

arxiv 2411.16028 v1 pith:PP5FWDVI submitted 2024-11-25 math.CO

Patrick Bennett This is my paper · ORCID
classification math.CO MSC 05C6505D0594B25
keywords constantweightcodesevenminimumdistanceasymptoticformularandomhypergraphfractionalmatchingpigeonholeprincipleq-arypacking
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

This paper answers a recent open question about the largest possible size of a q-ary constant-weight code when the minimum distance is even. It proves that, for fixed alphabet size q, weight w, and even distance d, the maximum number of code words is asymptotically equal to a classical upper bound: (q-1)^{t-1} binom(n,t)/binom(w,t) with t = w - d/2 + 1. The proof works by constructing a random hypergraph whose matchings correspond exactly to valid codes, then using a fractional matching theorem to show that a matching of almost the full size exists. The result matters because it shows the standard pigeonhole upper bound is sharp for even distances, completing the asymptotic picture left open after the odd-distance case was proved.

What carries the argument

The proof's engine is a random hypergraph H whose vertices are (t+1)-subsets of the coordinate set and t-subsets of coordinate-symbol pairs, and whose hyperedges are code words of weight w satisfying the random modulo-(q-1) sum condition on every t-subset of their support. A matching in H is exactly a code with minimum distance d, because two edges sharing a (t+1)-set vertex would violate the support-intersection limit, while sharing a t-set of coordinate-symbol pairs would violate the disagreement condition. The load-bearing tool is a fractional matching theorem for bounded hypergraphs (Lemma 1), which guarantees that if a fractional matching has pairwise vertex overlap parameter $\alpha$ below a small threshold, then an integral matching exists with size at least (1-epsilon) times the fractional value. The random choice of the sum conditions makes the pairwise overlap of vertices only O(1/n), placing $\alpha$ below the threshold, so the fractional matching induced by the constant weight 1/$\Delta$(H) yields the desired integral matching of size about (q-1)^{t-1} binom(n,t)/binom(w,t).

What would settle it

For fixed q, w, and even d, compute the number of code words containing two fixed vertices of the form {(i_1,x_{i_1}),...,(i_t,x_{i_t})} whose underlying index sets overlap in t-1 positions. The proof requires this count to be O($n^{{w-t-1}}$); if for any parameters it is instead $\Omega$($n^{{w-t}}$) for infinitely many n, the $\alpha$(f)=O(1/n) bound fails and the construction collapses. Alternatively, any family of even-distance constant-weight codes larger than (1+epsilon) times the upper bound for arbitrarily large n would disprove the asymptotic formula.

Watch

Extended reading notes

Core claim

The central discovery is that the maximum size A_q(n,d,w) of a q-ary constant-weight code of length n, weight w, and even minimum distance d is (1+o(1)) (q-1)^{t-1} binom(n,t)/binom(w,t) for t = w - d/2 + 1, matching the classical upper bound exactly. The construction assigns to every t-subset T of coordinates an independent random element B_T of the nonzero symbols, and keeps only those weight-w words whose nonzero entries on each t-subset of their support sum to B_T modulo q-1. These random 'parity' conditions force any two code words whose supports overlap in exactly t positions to differ in at least two of those positions, which raises the minimum distance from the naive 2(w-t)+1 to the required d = 2(w-t)+2. Thus the upper bound is achieved asymptotically, not just approached.

Load-bearing premise

The proof relies on the estimate that any two vertices of the random hypergraph lie together in only O($n^{{w-t-1}}$) edges, which makes the fractional matching overlap parameter of order 1/n and lets the fractional matching theorem apply; if some pair of vertices, particularly two vertices from the second layer with nearly identical index sets, shared substantially more edges, the theorem's threshold would not be met and the claimed matching size would not follow.

Editorial extensions

If this is right

  • For every fixed q, w, and even d, there exist codes whose size is (1-o(1)) times the upper bound, so the upper bound is asymptotically tight and A_q(n,d,w) is known.
  • Combined with the odd-distance result, the asymptotic value of A_q(n,d,w) is now settled for all fixed q, w, d with 2 <= d <= 2w.
  • The random parity constraints produce explicit (randomly generated) codes attaining the bound; in principle, one can sample a code of the promised size with high probability.
  • The proof confirms that the pigeonhole-principle proof of the upper bound is not only necessary but sufficient in the limit, for even distances as well as odd.

Reading between the lines

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

  • The same random-constraint trick may generalize to constant-composition codes, although the paper notes its own attempt did not match the bound; a different choice of random conditions might close the gap.
  • Because the theorem requires fixed q, w, d, a natural next step is to ask whether the formula remains valid when the alphabet size or weight grows slowly with n; the current proof's o(1) term depends on these parameters.
  • The O(1/n) pairwise overlap estimate suggests the same fractional-matching framework could prove asymptotically optimal packings in other structures where random constraints can be used to forbid close pairs, such as generalized Steiner systems.
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.

Referee Report

0 major / 4 minor

Summary. The paper proves Theorem 2, an asymptotic formula for A_q(n,d,w) when d is even: for fixed q, w and even d with 2 ≤ d ≤ 2w, and t = w − d/2 + 1, it shows A_q(n,d,w) = (1+o(1)) (q−1)^{t−1} binom(n,t)/binom(w,t), matching the Johnson upper bound. The proof constructs a random hypergraph H whose V1 vertices are (t+1)-subsets of [n] and whose V2 vertices are t-sets of nonzero coordinate-value pairs satisfying random equations sum_{i∈T} x_i ≡ B_T (mod q−1). Edges correspond to weight-w words that satisfy all equations on their support. A constant fractional matching f(e)=1/Δ(H) is shown to have α(f)=O(n^{−1}) via pairwise codegree estimates, so Kahn's theorem yields a matching of size (1−o(1))f(H). The matching is then translated into a constant-weight code of minimum distance at least d. Concentration of V2 degrees is established with McDiarmid's inequality.

Significance. The result answers exactly the even-distance question posed by Liu and Shangguan and completes the picture for fixed q, w, d: the Johnson bound is asymptotically tight for both parities of d. The proof is clean and self-contained modulo two standard external tools, Kahn's fractional matching theorem and McDiarmid's inequality. The key technical step is the pair-codegree estimate behind α(f)=O(n^{−1}); it is correct for all vertex-pair types, including the delicate V2–V2 case where the index sets nearly coincide. The paper introduces no fitted parameters or ad hoc assumptions, and the matching-to-code correspondence is carefully argued. This is a short but natural and worthwhile contribution.

minor comments (4)
  1. [Section 4, degree-concentration paragraph] The sentence 'Now by the union bound over all choices for v ∈ V2' is imprecise because V2 itself is random. The proof should union-bound over all O(n^t (q−1)^t) possible tuples v with distinct indices and nonzero entries; for any tuple that happens to lie in V2, its degree equals D_v, so the previous concentration estimate applies.
  2. [Section 4, application of Lemma 1] The step from α(f)=O(n^{−1}) to a matching 'of size asymptotically f(H)' should spell out the quantifier: for each fixed ε>0, Lemma 1 supplies σ=σ(ε), and since α(f)<σ for all sufficiently large n one obtains ν(H) ≥ (1−ε)f(H); because ε is arbitrary, this gives ν(H)∼f(H). As written, the dependence of σ on ε is hidden.
  3. [Section 3, odd-d paragraph] The sentence 'Liu and Shangguan [15] recently proved Theorem 2 is asymptotically optimal' should refer to Theorem 1 (the Johnson upper bound), since Theorem 2 is the even-distance result proved in this paper.
  4. [Section 3, even upper-bound proof] In the pigeonhole argument, 'we associate a vector in [q−1]^{t−1} specifying the entries of x̄ on some arbitrary t−1 indices in T' is correct, but the wording could be read as specifying entries on all of T; please clarify that the vector is on the chosen (t−1)-subset. There are also minor typos, including 'a a vector' and 'on supp(x̄)' where 'on T' is meant.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the even-distance lower bound is derived from external tools (Kahn's fractional matching theorem, McDiarmid's inequality) and a deterministic pair-codegree estimate, with no fitted parameter renamed as a prediction and no load-bearing self-citation.

full rationale

The paper's central claim, Theorem 2, is an asymptotic formula for A_q(n,d,w) in the even-distance case. The proof is a self-contained construction: random values B_T are chosen, a hypergraph H is built, a constant fractional matching f(e)=1/Delta is exhibited, and Kahn's theorem (Lemma 1, an external result) converts the fractional matching into an integral matching whose size asymptotically matches the Johnson upper bound. The estimate alpha(f)=O(n^{-1}) rests on the explicit claim that any two vertices of H lie together in O(n^{w-t-1}) edges; this is a direct counting bound on the hypergraph construction, not an assumption equivalent to the desired theorem. The Johnson upper bound (Theorem 1) is cited from external prior work and is used only as the benchmark for optimality, not as an ingredient in the lower-bound construction. The Liu-Shangguan odd-distance result is used only as motivation and as the source of the question addressed; it is not an input that implies the even-distance formula. No parameters are fitted to data, no prediction is a renamed fit, and there are no self-citations at all. The paper even reports a genuine limitation in the concluding remarks concerning constant-composition codes, which further indicates the argument is not being forced to a predetermined answer. Therefore no circular step can be exhibited, and the honest verdict is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof introduces no fitted constants and no new entities. The random values B_T are uniform random choices, not fitted parameters. The external theorems (Kahn's fractional matching theorem, McDiarmid's inequality) are cited and standard. The domain assumptions (fixed q,d,w, n->infinity, nonzero entries range over a complete residue system modulo q-1) are stated.

assumptions (4)
  • standard math Kahn's fractional matching theorem (Lemma 1): an l-bounded hypergraph with a fractional matching f of pair-codegree alpha(f) < sigma has a matching of size at least (1-epsilon)f(H).
    External theorem cited as [14], used in Section 4 to convert a fractional matching into a large integral matching.
  • standard math McDiarmid's bounded differences inequality (Lemma 2).
    External theorem cited as [16], used in Section 4 to prove concentration of the vertex degrees in the random hypergraph.
  • domain assumption The entries of a constant weight codeword are nonzero and range over {1,...,q-1}, which is a complete residue system modulo q-1.
    Used to argue that in equation (4) the remaining entry is uniquely determined among nonzero entries and that |V2|=(q-1)^{t-1} binom(n,t).
  • domain assumption q, d, w are fixed while n tends to infinity; all asymptotics are with respect to n.
    The main theorem is stated under this regime, and the proof relies on it for estimates such as the degree concentration.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Asymptotically optimal constant weight codes with even distance." pith.science (2026). https://pith.science/paper/PP5FWDVI

@misc{pith2026241116028,
  author       = {Pith},
  title        = {Pith review of: Asymptotically optimal constant weight codes with even distance},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PP5FWDVI}},
  note         = {Machine review of arXiv:2411.16028}
}
abstract

A $q$-ary code $C$ of length $n$ is a set of $n$-dimensional vectors (code words) with entries in $\{0, \ldots, q-1\}$. We say $C$ has constant weight $w$ if each code word has exactly $w$ nonzero entries. We say $C$ has minimum distance $d$ if any two distinct code words in $C$ differ in at least $d$ entries. We let $A_q(n, d, w)$ be the largest possible cardinality of any $q$-ary code of length $n$ with constant weight $w$ and minimum distance $d$. Very recently, Liu and Shangguan gave an asymptotically sharp estimate for $A_q(n, d, w)$ where $q, d, w$ are fixed, $d$ is odd and $n \rightarrow \infty$. In this note we answer a question of Liu and Shangguan by obtaining such an estimate in the case where $d$ is even.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Agrell, A

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

    work page 2000

  2. [2]

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

    work page 1990

  3. [3]

    Y. M. Chee, S. H. Dau, A. C. H. Ling, and S. Ling. Linear size optima l q-ary constant-weight codes and constant-composition codes. IEEE Trans. Inform. Theory , 56(1):140–151, 2010

    work page 2010

  4. [4]

    Y. M. Chee, F. Gao, H. M. Kiah, A. C. H. Ling, H. Zhang, and X. Zha ng. Decompositions of edge- colored digraphs: a new technique in the construction of constant -weight codes and related families. SIAM J. Discrete Math. , 33(1):209–229, 2019

    work page 2019

  5. [5]

    Y. M. Chee, H. M. Kiah, and P. Purkayastha. Estimates on the siz e of symbol weight codes. IEEE Trans. Inform. Theory , 59(1):301–314, 2013

    work page 2013

  6. [6]

    Y. M. Chee and S. Ling. Constructions for q-ary constant-weight codes. IEEE Trans. Inform. Theory , 53(1):135–146, 2007

    work page 2007

  7. [7]

    W. Chu, C. J. Colbourn, and P. Dukes. Constructions for permu tation codes in powerline communica- tions. Des. Codes Cryptogr. , 32(1-3):51–64, 2004

    work page 2004

  8. [8]

    D. J. Costello and G. D. Forney. Channel coding: The road to cha nnel capacity. Proceedings of the IEEE, 95(6):1150–1177, 2007

    work page 2007

Show all 23 references
  1. [9]

    T. Etzion. Optimal constant weight codes over Zk and generalized designs. Discrete Math., 169(1-3):55– 82, 1997

    1997

  2. [10]

    T. Etzion. A new approach for examining q-Steiner systems. Electron. J. Combin. , 25(2):Paper No. 2.8, 24, 2018

    2018

  3. [11]

    G. Ge. Construction of optimal ternary constant weight code s via Bhaskar Rao designs. Discrete Math., 308(13):2704–2708, 2008

    2008

  4. [12]

    R. L. Graham and N. J. A. Sloane. Lower bounds for constant w eight codes. IEEE Trans. Inform. Theory, 26(1):37–43, 1980

    1980

  5. [13]

    S. M. Johnson. A new upper bound for error-correcting code s. IRE Trans., IT-8:203–207, 1962

    1962

  6. [14]

    J. Kahn. A linear programming perspective on the Frankl-R¨ odl- Pippenger theorem. Random Structures Algorithms, 8(2):149–157, 1996

    1996

  7. [15]

    Liu and C

    M. Liu and C. Shangguan. Approximate generalized Steiner syst ems and near-optimal constant weight codes. J. Combin. Theory Ser. A , 209:Paper No. 105955, 19, 2025

    2025

  8. [16]

    McDiarmid

    C. McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser. , pages 148–188. Cambridge Univ. Press, Cambridge, 1989

    1989

  9. [17]

    P. R. J. ¨Osterg ˚ a rd and M. Svanstr¨ om. Ternary constant weight codes. Electron. J. Combin. , 9(1):Re- search Paper 41, 23, 2002

    2002

  10. [18]

    S. C. Polak. Semidefinite programming bounds for constant-we ight codes. IEEE Trans. Inform. Theory , 65(1):28–38, 2019

    2019

  11. [19]

    J. A. Wood. The structure of linear codes of constant weight. Trans. Amer. Math. Soc. , 354(3):1007– 1026, 2002

    2002

  12. [20]

    Wu and P

    D. Wu and P. Fan. Constructions of optimal quaternary const ant weight codes via group divisible designs. Discrete Math., 309(20):6009–6013, 2009

    2009

  13. [21]

    Zhang and G

    H. Zhang and G. Ge. Optimal ternary constant-weight codes o f weight four and distance six. IEEE Trans. Inform. Theory , 56(5):2188–2203, 2010

    2010

  14. [22]

    Zhang and G

    H. Zhang and G. Ge. Optimal quaternary constant-weight cod es with weight four and distance five. IEEE Trans. Inform. Theory , 59(3):1617–1629, 2013

    2013

  15. [23]

    Zhang, X

    H. Zhang, X. Zhang, and G. Ge. Optimal ternary constant-we ight codes with weight 4 and distance 5. IEEE Trans. Inform. Theory , 58(5):2706–2718, 2012. Department of Mathematics, Western Michigan University, K alamazoo, MI, USA Email address : patrick.bennett@wmich.edu

    2012

Pith tools

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