{"id":"cca7e3f9-91f0-4332-a09c-59b331a1767c","arxiv_id":"2411.16028","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For even d, A_q(n,d,w) is asymptotically (q-1)^{t-1} binom(n,t)/binom(w,t) with t = w - d/2 + 1, matching the Johnson bound.","lead":"This paper proves that for fixed alphabet size, weight, and even minimum distance, the largest constant weight code has size asymptotically equal to the Johnson bound, matching the known odd distance case. It resolves an open question posed by Liu and Shangguan by constructing nearly optimal codes with a random constraint trick.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the delicate pair-codegree estimate behind alpha(f)=O(n^{-1}) checks out for all vertex-pair types, so Kahn's theorem applies.","rationale":"The reader correctly identifies the pair-codegree estimate and the resulting alpha(f)=O(n^{-1}) as the load-bearing external premise in the application of Kahn's theorem. I examined this premise in detail. The one-sentence proof in the paper omits the case analysis, but the estimate is correct: for every pair of vertices, the number of edges containing both is bounded by the number of weight-w supports containing the union of the relevant index sets, times a constant number of value completions. The largest support count occurs when the union has size t+1, giving O(n^{w-t-1}); this happens for V2-V2 pairs with index overlap t-1 and for V1-V2 pairs with the V2 index set contained in the V1 set. All other cases give smaller exponents. Since typical V2 degrees are Theta(n^{w-t}) and V1 degrees are lower order, Delta ~ n^{w-t}, so alpha(f) is O(n^{-1}). For any fixed epsilon in Kahn's lemma, sigma is a fixed positive constant, so for sufficiently large n the condition alpha(f)<sigma holds on the high-probability event. The remaining steps, from fractional matching size to a valid code, are consistent: the matching size is asymptotically |V2|/(w choose t), and the vertex-disjointness conditions enforce exactly the support-intersection and value-agreement restrictions needed for minimum distance d. The paper is terse in places, but I found no internal inconsistency or unsupported assumption that threatens the central claim.","tokens_in":7211,"tokens_out":43838,"duration_ms":424136,"concrete_test":"Independently enumerate the four vertex-pair types (V1-V1, V1-V2, V2-V2) and recompute the maximum number of edges containing both vertices as a function of n, keeping the exact constants for the cases |U∩V|=t-1 and T⊂A. If any pair type has codegree Omega(n^{w-t}), then alpha(f) would not be O(n^{-1}) and the Kahn step would fail; if all exponents are at most w-t-1, the central claim stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof's most load-bearing step is the terse claim that any two vertices of the random hypergraph H lie in O(n^{w-t-1}) edges together, which is needed to conclude alpha(f) < sigma for Kahn's fractional matching theorem. I checked this estimate for every vertex-pair type. For two V2 vertices with index sets U,V, the largest possible common-edge count occurs when |U∩V|=t-1: any edge containing both has support containing U∪V of size t+1, so there are at most binom(n-(t+1), w-(t+1)) * (q-1)^{w-t-1} = O(n^{w-t-1}) such edges; if values disagree on the overlap the count is zero. For a V1 vertex A and a V2 vertex v, the maximum occurs when T⊂A, giving the same O(n^{w-t-1}) bound. For two V1 vertices the exponent is at most w-t-2. Thus max pair codegree is O(n^{w-t-1}) deterministically, and with Delta ~ n^{w-t} this gives alpha(f)=O(n^{-1}), which is eventually below any fixed sigma. The edge case t=w is also safe: pair codegrees are 0, so alpha(f)=0. No flaw found.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7374,"tokens_out":25060,"duration_ms":235403,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 4, degree-concentration paragraph"},{"comment":"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.","section":"Section 4, application of Lemma 1"},{"comment":"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.","section":"Section 3, odd-d paragraph"},{"comment":"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.","section":"Section 3, even upper-bound proof"}],"recommendation":"minor_revision","confidential_remarks":"This is a solid short note. The only issues are local matters of presentation and quantifier clarity in the use of Kahn's theorem and in the union-bound argument; I found no substantive gap in the proof. It fits the scope of the journal and should be published after a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is the short version: this note resolves the even-distance case of the Johnson bound for constant weight codes, and the proof is sound. The reader's ACCEPT is right, and the stress-test check of the pair-codegree estimate holds up on reading.\n\nThe new thing is the random linear constraint trick: for each t-subset T of coordinates, impose sum_{i in T} x_i = B_T mod (q-1) on every codeword containing T, with B_T random. This forces any two codewords whose supports meet in exactly t positions to differ in at least two of those positions. That is exactly what is needed for even distance, and it is not a routine extension of Liu-Shangguan's odd-distance argument. The construction plus Kahn's fractional matching theorem gives a matching size that matches the upper bound.\n\nThe paper does several things well. It keeps the proof self-contained aside from two standard tools. The concentration argument for V2 degrees is careful, with the McDiarmid differences handled correctly. The matching-to-code correspondence is argued cleanly. The citation pattern is healthy: Kahn, McDiarmid, Liu-Shangguan, and standard coding theory references; no reliance on the author's own prior work.\n\nSoft spots are minor. The claim that any two vertices lie in O(n^{w-t-1}) edges together is stated without proof. I checked all three vertex-pair types, as the stress-test note did, and the bound is correct; the worst case is two V2 vertices with index sets overlapping in t-1 positions, giving the deterministic bound. But a referee should ask the author to spell this out. The same goes for the degree concentration step: it is terse, and while the union bound is valid, the details would be easier to verify if written out. The final remark about failing to extend to constant composition codes is honest and does not undermine the main result.\n\nThis paper is for researchers working on constant weight codes, q-ary codes, and Johnson-type bounds. It is a genuine answer to an explicit open question. It deserves a serious referee and, with the small clarifications requested, publication.\n\nRecommendation: send to review, with a request for a brief expansion of the pair-codegree argument.","headline":"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.","tokens_in":7957,"tokens_out":4936,"would_cite":true,"duration_ms":44340,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05D05","94B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For even minimum distance, constant-weight codes attain the classical upper bound asymptotically.","keywords":["constant weight codes","even minimum distance","asymptotic formula","random hypergraph","fractional matching","pigeonhole principle","q-ary codes","packing codes"],"falsifier":"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.","tokens_in":6928,"feed_emoji":"🧮","tokens_out":9970,"duration_ms":81180,"temperature":0.7,"pith_summary":"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.","feed_headline":"Even-distance codes match the upper bound asymptotically","feed_subtitle":"Random hypergraph construction meets the bound for fixed q, w, and even d.","key_machinery":"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).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the fractional matching theorem used to extract an integral matching from a fractional one.","marker":"[14]"},{"why":"Provides the odd-distance case and the open question answered here.","marker":"[15]"},{"why":"Establishes the upper bound that the construction matches.","marker":"[13]"},{"why":"States the upper bound that serves as the comparison target.","marker":"[6]"},{"why":"Gives the concentration inequality used to control random degrees.","marker":"[16]"}],"fun_headline_variants":["Even-distance constant-weight codes asymptotically optimal","Random parity codes hit even-distance optimum","Optimal even-distance codes via random hypergraph","Even-distance codes achieve asymptotic upper bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Even-distance constant-weight codes asymptotically optimal","Random parity codes hit even-distance optimum","Optimal even-distance codes via random hypergraph","Even-distance codes achieve asymptotic upper bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000766,"raw_usage":{"total_tokens":3377,"prompt_tokens":906,"completion_tokens":2471,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":2417}},"tokens_in":522,"tokens_out":2471,"duration_ms":17974,"temperature":1.0,"reasoning_tokens":2417,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:37:57.324058+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Liu and C","cited_arxiv_id":null,"evidence_quote":"Provides the odd-distance case and the open question answered here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the upper bound that the construction matches."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the upper bound that serves as the comparison target."},{"cited_title":"McDiarmid","cited_arxiv_id":null,"evidence_quote":"Gives the concentration inequality used to control random degrees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the fractional matching theorem used to extract an integral matching from a fractional one."}],"review_version":1}