{"id":"6e42bf15-b885-4cdf-8a0e-ad8878a53add","arxiv_id":"2507.10068","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"BiD codes, built from a 3x3 Kronecker kernel, have proven minimum distance growing at least as N^0.543 at any fixed rate, faster than Reed-Muller's N^0.5.","lead":"This paper introduces BiD codes, a family of error-correcting codes built from three-by-three matrix products, and shows they can match or beat Reed-Muller codes in simulations. The main theoretical result is a proof that these codes can have minimum distance growing faster than Reed-Muller codes as blocklength grows.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the recursive distance bounds and Theorem 3.5 are internally consistent; only the simulation/ML-decoder claims remain under-supported, and they are not load-bearing for the asymptotic result.","rationale":"The reader's conditional verdict is reasonable, but their named weakest assumption (the external Berman distance formulas) is not, in my view, the most load-bearing item: those formulas are published, standard, and consistent with the paper's own tables for small lengths. The mathematical argument for the central asymptotic claim appears sound: Theorem 3.1's recursive lower bound is derived from a complete case analysis, Appendix F's induction algebra checks out, and the CLT rate-selection argument in Appendix I is valid. The simulation claims, by contrast, rest on an unquantified 'essentially-ML' approximation and on unreleased code/data; this is a real limitation of the paper's practical claims, but it does not threaten Theorem 3.5. Hence I report no significant objection to the central result and recommend leaving the reader's conditional verdict unchanged.","tokens_in":19780,"tokens_out":12949,"duration_ms":136958,"concrete_test":"Independently verify the base case of the Appendix F induction by computing the true minimum distance of the dual Berman code CA(5,{0,1,2}) (length 243, dimension 51), e.g. by an exhaustive syndrome-based or linear-algebra enumeration; if the value is not 27, the induction base in Theorem 3.2 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the chain supporting Theorem 3.5 and found no load-bearing flaw. Theorem 3.1's case analysis in Appendix D is internally consistent for all cases it claims to cover, and Appendix F correctly propagates the second lower bound 3^{m-r2} * 2^{r1+r2-m} through D2, D3, and D4a, with the |W|=1 case only making the argument easier. The CLT-based rate selection in Appendix I gives r1/m, r2/m -> 2/3, yielding liminf log(dmin)/log N >= log 6 / log 27. The external Berman distance formulas in Theorem 2.1 are standard and are consistent with the small-length tables in the paper, so I do not treat them as a live threat. The genuinely under-verified part is not the asymptotic theorem but the empirical 'essentially-ML' claim: lambda_max and eta are not reported, no code or data are provided, and the empirical ML lower-bound check does not prove that the SCOS decoder reaches ML performance. These caveats affect the simulation-based comparisons, not the correctness of Theorem 3.5.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Berman-intersection-dual Berman (BiD) codes, abelian codes of length 3^m obtained by intersecting Berman codes with dual Berman codes. It shows that these codes admit a simple generator-matrix description as rows of a Kronecker power of a 3x3 kernel, derives recursive bounds on their minimum distance (Theorem 3.1), closed-form lower bounds (Theorem 3.2), exact minimum distances for two special weight sets (Theorems 3.3 and 3.4), and an asymptotic result (Theorem 3.5): for every fixed rate R in (0,1), there exists a sequence of BiD codes with rate converging to R and liminf log(d_min)/log N >= log 6/log 27 ≈ 0.543, exceeding the N^{0.5} growth of Reed-Muller codes at the same rate. The paper also reports simulations at length 243 in the BI-AWGN and erasure channels, using a successive-cancellation ordered-search (SCOS) decoder with claimed essentially-ML performance, and compares favorably with RM, RM-Polar, and CRC-aided Polar codes.","tokens_in":19953,"tokens_out":23707,"duration_ms":224744,"significance":"The main theoretical contribution is substantial and appears correct. Theorem 3.5 provides a proved family of binary linear codes with a minimum-distance growth exponent strictly larger than 1/2 at every fixed rate, improving on the long-studied Reed-Muller family under a simple kernel-based construction. The proof is a genuine lower-bound argument, not a restatement of an assumption: it uses known Berman-code distances as base cases and a CLT-based rate selection. The recursive distance bounds in Theorem 3.1 are supported by a detailed case analysis in Appendix D, and the closed-form bounds in Theorem 3.2 are checked against numerically computed bounds in the tables. The paper also gives an explicit generator-matrix description and an adaptation of the SCOS decoder. The main weakness is experimental: the claimed essentially-ML performance is not fully substantiated due to missing decoder parameters and supporting curves, but this does not affect the correctness of the asymptotic theorem. If the simulation details are clarified or the claims softened, the paper would be a solid contribution to algebraic coding theory.","major_comments":[],"minor_comments":[{"comment":"The SCOS decoder parameters λmax and η are not reported, and the empirical lower bound on the ML BLER used to justify the 'essentially-ML' claim is not shown in any figure. Please provide these values and the lower-bound curve, or a link to code/data, so that the simulation results are reproducible. Without this, the abstract's statement about ML decoding is not verifiable.","section":"Section 5.1, Appendix J"},{"comment":"The proof of the first lower bound in Theorem 3.2 (the expression 4^{r1} 3^{m-r1-r2}) is only sketched with 'the proof of the other expression follows similar steps.' Since this bound is used to generate Fig. 2 at practical lengths, please include a complete induction or a detailed outline to make the theorem fully self-contained.","section":"Appendix F"},{"comment":"In the paragraph before Theorem 3.5, 'N = 2 m' appears to be a typo for 'N = 2^m' when referring to RM codes; please correct it.","section":"Section 3"},{"comment":"The entry for BiD(5,2,2) lists d_min as 48–54, but Section 5.1 states that simulations show the exact minimum distance is 48. Please update the table entry to 48, or add a footnote explaining the discrepancy.","section":"Table I"},{"comment":"The paper uses the permuted kernel AAA'_3 in simulations but develops the recursion and distance bounds for AAA_3. Please clarify explicitly that Corollary 2.5 and the distance bounds of Section 3 apply unchanged to AAA'_3, because the row sets of a given weight are identical up to row permutation.","section":"Section 2.2"},{"comment":"The phrase 'larger distance than RM codes asymptotically' may be read as a claim about exact distances; Theorem 3.5 establishes a lower bound on the growth exponent. Consider rewording to 'provably larger asymptotic distance growth' for precision.","section":"Abstract"}],"recommendation":"minor_revision","confidential_remarks":"The theoretical results appear sound and the paper is a strong candidate for publication after the experimental details are addressed. The main concern is the lack of reproducibility of the simulations; in particular, the missing SCOS parameters and the absent ML lower-bound curve. I would encourage the editor to ask for these to be added or for the claims to be moderated. The asymptotic theorem is not affected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this paper proves a binary linear code family from a 3x3 kernel with minimum distance growing like N^0.543 at any fixed rate, beating the N^0.5 of Reed-Muller codes. That is a real result, not a restatement of an assumption. I went through the recursion and the CLT-based rate selection in Appendix I, and the asymptotic exponent is supported by a genuine lower-bound argument.\n\nWhat is new: the spectral code family CA(m,W) already appeared in the authors' previous paper [9], but the Hamming-weight row-selection construction from A3^otimes m is new, as are the recursive distance bounds, the closed-form lower bound, and the asymptotic exponent. The paper is honest about the limits: the distance comparison is against a lower bound, and the decoder complexity is high. The only self-citation is to their own prior definition of the spectral codes, and the base distance formulas are from published Berman code results; that's legitimate.\n\nSoft spots, in proportion: the simulation section is the weakest part. The SCOS decoder is claimed to be essentially ML, but the parameters lambda_max and eta are not reported, and no code or data are provided. The empirical lower bound on ML BLER does not establish that SCOS actually reaches ML. This doesn't threaten the distance theorems, but it caps the practical claims. The length-243 versus length-256 comparison is apples-to-oranges in blocklength, though they acknowledge it. Also, the closed-form lower bound may be loose; for a few small codes the exact distance is not pinned down, but that's a minor point.\n\nOverall, the central mathematical contribution is solid and deserves serious refereeing. I recommend sending it to review. A revision should either report the decoder parameters or soften the essentially-ML claim, and ideally share the simulation code. But the asymptotic distance result is the kind of thing the information theory community should engage with, and I'd bring it to reading group.","headline":"A proven N^0.543 distance exponent for a 3x3 kernel code family is the real deal; the simulations are under-supported and should be cleaned up before publication.","tokens_in":20545,"tokens_out":1556,"would_cite":true,"duration_ms":17774,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B60","94B65"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces BiD codes, binary linear codes of length $3^m$ from a $3\\times3$ kernel, and proves their minimum distance grows at least as $N^{0.543}$ at every fixed rate, exceeding the $N^{0.5}$ growth of Reed-Muller codes.","keywords":["BiD codes","Berman codes","Reed-Muller codes","minimum distance","3x3 kernel","abelian codes","polar codes","successive cancellation ordered search"],"falsifier":"Compute the true minimum distance of $\\mathrm{BiD}(5,3,3)$, length 243, by exhaustive search or integer programming; the paper's Table I leaves its distance somewhere between 22 and 36, so finding any codeword of weight below 22 would falsify the closed-form lower bound of Theorem 3.2.","tokens_in":19561,"feed_emoji":"📡","tokens_out":11657,"duration_ms":117281,"temperature":0.7,"pith_summary":"BiD codes are binary abelian codes of length $3^m$ that can be read directly off the Kronecker-power matrix $A_3^{\\otimes m}$: keep exactly the rows whose Hamming weights lie in a chosen window. The paper's central claim is that for every fixed rate $R\\in(0,1)$ there is a sequence of such codes whose minimum distance grows at least as fast as $N^{0.543}$, asymptotically faster than the $N^{0.5}$ growth of constant-rate Reed-Muller codes. That claim rests on a recursive bound that specializes to the closed-form lower bound $d_{\\min}\\ge\\lceil\\max\\{4^{r_1}3^{m-r_1-r_2},\\,3^{m-r_2}2^{r_1+r_2-m}\\}\\rceil$, and the recursion is tight for every BiD code of length up to $3^5$ except four parameter pairs. Simulations at length 243 in erasure and Gaussian channels put BiD block error rates close to, and sometimes below, those of Reed-Muller, RM-Polar, and CRC-aided Polar codes under essentially maximum-likelihood decoding. If the asymptotic claim holds, BiD codes form a kernel-constructed algebraic family whose rate-distance trade-off crosses the benchmark set by Reed-Muller codes.","feed_headline":"3×3 kernel codes outdistance Reed–Muller at every fixed rate","feed_subtitle":"A proved exponent log 6/log 27 ≈ 0.543 beats the 0.5 exponent of constant-rate Reed–Muller codes.","key_machinery":"The carrying object is the row-weight recursion for the block matrices $G_{m,w}$: each weight-$w$ submatrix of $A_3^{\\otimes m}$ splits as the vertical stack of $(1,1,1)\\otimes G_{m-1,w}$, $(1,1,0)\\otimes G_{m-1,w-1}$, and $(1,0,1)\\otimes G_{m-1,w-1}$, with repetition and single-parity-check codes as the $w=0$ and $w=m$ endpoints. Combined with the direct-sum decomposition $\\mathcal{C}_A(m,W)=\\oplus_{w\\in W}\\mathcal{C}_A(m,\\{w\\})$, this splits any BiD codeword into three shorter codewords and supports an exhaustive case analysis on the number of nonzero slices. The recursion terminates at Berman and dual-Berman codes, whose minimum distances $2^{r+1}$ and $3^{m-r}$ are taken as base cases, and the closed-form bound of Theorem 3.2 is then evaluated along the rate-converging sequence $r_1,r_2\\sim 2m/3$. The asymptotic exponent appears after writing the minimum distance in terms of $N=3^m$ and taking the liminf.","core_discovery":"A Berman-intersection-dual Berman code $\\mathrm{BiD}(m,r_1,r_2)$ is the intersection of a Berman code of order $r_1-1$ and the dual of a Berman code of order $r_2$; in the spectral description of abelian codes it is $\\mathcal{C}_A(m,\\{r_1,\\ldots,r_2\\})$, meaning exactly those vectors whose frequency-domain entries vanish outside Hamming-weight levels $r_1$ through $r_2$. The main discovery is that this algebraic intersection has a simple kernel description: its generator matrix is the submatrix of $A_3^{\\otimes m}$, with $A_3=[1\\,1\\,1;\\,1\\,1\\,0;\\,1\\,0\\,1]$, consisting of rows with weights between $2^{r_2}3^{m-r_2}$ and $2^{r_1}3^{m-r_1}$. The recursive distance bound (Theorem 3.1) analyzes the three length-$3^{m-1}$ slices of a codeword and yields the two closed-form lower bounds of Theorem 3.2. Choosing $r_1,r_2$ near $2m/3$ makes the rate converge to any prescribed $R$ and makes the exponent $\\log d_{\\min}/\\log N$ approach at least $\\log 6/\\log 27>0.543$, exceeding the $0.5$ limiting exponent of constant-rate Reed-Muller codes.","pith_inferences":["A natural extension would apply the same slice recursion to kernels larger than $3\\times3$; the asymptotic exponent would then be governed by the row-weight spectrum of the kernel, suggesting a general family of distance-growth lower bounds indexed by kernel size.","The non-tight recursion cases (for example $(m,r_1,r_2)=(5,3,3)$) are concrete places to test whether the closed-form bound is loose or the recursion itself loses information; an exact determination there could guide a tighter theorem.","Because the paper's AWGN results use essentially-ML SCOS decoding with high node-visit counts, a natural next experiment is to measure BLER at fixed decoder complexity, which could reverse the practical ordering at low latency.","The abelian ideal structure of BiD codes may admit transform-domain decoding, which would address the paper's stated bottleneck of high decoding complexity without changing the distance guarantees."],"forward_implications":["At any fixed rate in $(0,1)$, BiD codes provide a constructive sequence with minimum distance growing at least as $N^{0.543}$, so the claimed improvement over Reed-Muller's $N^{0.5}$ applies across the whole rate range, not just at capacity.","The recursive bound yields exact minimum distances for all BiD codes of length up to $3^5$ except four parameter choices, so the construction comes with reliable finite-length distance data for practical blocklengths.","Because the codes are defined by row selection from a $3\\times3$ kernel, the same encoding transform used for polar codes realizes them, and successive-cancellation-style decoders can be adapted without changing the kernel.","Simulations at length 243 place BiD and dynamically frozen dBiD codes at or below the block error rates of Reed-Muller, RM-Polar, and CRC-aided Polar codes at matched rates in erasure and AWGN channels, under essentially maximum-likelihood decoding.","The observed weight-48 codeword in $\\mathrm{BiD}(5,2,2)$ shows the closed-form bound is tight for at least one practical code, and the four untight cases mark where exact distances remain open."],"supporting_citations":[{"why":"defines the abelian codes $\\mathcal{C}_A(m,W)$ in the spectral domain, including the direct-sum decomposition, the dual relationship, and the inverse-DFT generator construction that the kernel description must reproduce.","marker":"[9]"},{"why":"one of the cited sources for the exact Berman and dual-Berman minimum distances $2^{r+1}$ and $3^{m-r}$ that serve as recursion base cases.","marker":"[10]"},{"why":"the second cited source for those Berman minimum distances, backing Theorem 2.1.","marker":"[11]"},{"why":"supplies the rate-selection argument via binomial and central-limit estimates and the Reed-Muller asymptotic comparison used to turn the closed-form bound into Theorem 3.5.","marker":"[15]"},{"why":"gives the benchmark that among $2\\times2$-kernel constructions the Reed-Muller row-selection rule maximizes minimum distance, fixing the $0.5$ exponent BiD codes must beat.","marker":"[16]"},{"why":"sets up the polar and Reed-Muller rate-distance relation for kernel constructions and the constant-rate Reed-Muller sequence whose exponent is $0.5$.","marker":"[4]"},{"why":"provides the successive-cancellation ordered search decoder used to obtain essentially maximum-likelihood block error rates for BiD codes in the AWGN simulations.","marker":"[12]"}],"fun_headline_variants":["BiD codes beat Reed-Muller with a 3x3 kernel","3×3 kernel codes outdistance Reed–Muller asymptotically","New algebraic codes exceed Reed-Muller distance asymptotically","Exponent 0.543 beats RM's 0.5 in algebraic codes","Kronecker 3×3 codes rival RM, better at long lengths"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole distance proof assumes the previously published minimum distances of Berman codes and their duals are correct; if those numbers were wrong, the recursive base cases, the closed-form bound, and the asymptotic exponent would collapse.","fun_headline_variants_meta":{"raw":{"variants":["BiD codes beat Reed-Muller with a 3x3 kernel","3×3 kernel codes outdistance Reed–Muller asymptotically","New algebraic codes exceed Reed-Muller distance asymptotically","Exponent 0.543 beats RM's 0.5 in algebraic codes","Kronecker 3×3 codes rival RM, better at long lengths"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001119,"raw_usage":{"total_tokens":4676,"prompt_tokens":984,"completion_tokens":3692,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":3598}},"tokens_in":600,"tokens_out":3692,"duration_ms":29693,"temperature":1.0,"reasoning_tokens":3598,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:41:09.132131+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the true minimum distance of $\\mathrm{BiD}(5,3,3)$, length 243, by exhaustive search or integer programming; the paper's Table I leaves its distance somewhere between 22 and 36, so finding any codeword of weight below 22 would falsify the closed-form lower bound of Theorem 3.2.","supporting_citations":[{"cited_title":"Berman codes: A generalization of Reed–Muller codes that achieve BEC capacity,","cited_arxiv_id":null,"evidence_quote":"defines the abelian codes $\\mathcal{C}_A(m,W)$ in the spectral domain, including the direct-sum decomposition, the dual relationship, and the inverse-DFT generator construction that the kernel description must reproduce."},{"cited_title":"Semisimple cyclic and Abelian codes. II,","cited_arxiv_id":null,"evidence_quote":"one of the cited sources for the exact Berman and dual-Berman minimum distances $2^{r+1}$ and $3^{m-r}$ that serve as recursion base cases."},{"cited_title":"On a family of abelian codes and their state complexities,","cited_arxiv_id":null,"evidence_quote":"the second cited source for those Berman minimum distances, backing Theorem 2.1."},{"cited_title":"Reed–Muller codes achieve capacity on erasure channels,","cited_arxiv_id":null,"evidence_quote":"supplies the rate-selection argument via binomial and central-limit estimates and the Reed-Muller asymptotic comparison used to turn the closed-form bound into Theorem 3.5."},{"cited_title":"Polar codes for channel and source coding,","cited_arxiv_id":null,"evidence_quote":"gives the benchmark that among $2\\times2$-kernel constructions the Reed-Muller row-selection rule maximizes minimum distance, fixing the $0.5$ exponent BiD codes must beat."},{"cited_title":"Channel polarization: A method for constructing capacity- achieving codes for symmetric binary-input memoryless channels,","cited_arxiv_id":null,"evidence_quote":"sets up the polar and Reed-Muller rate-distance relation for kernel constructions and the constant-rate Reed-Muller sequence whose exponent is $0.5$."},{"cited_title":"Successive Cancellation Ordered Search Decoding of Modified GN-Coset Codes,","cited_arxiv_id":null,"evidence_quote":"provides the successive-cancellation ordered search decoder used to obtain essentially maximum-likelihood block error rates for BiD codes in the AWGN simulations."}],"review_version":1}