pith. sign in

arxiv: 2504.11010 · v2 · submitted 2025-04-15 · 💻 cs.IT · math.IT

New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance

Lingqi Zheng , Weijun Fang , Rongxing Qiu This is my paper

Pith reviewed 2026-05-22 21:06 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords binary cyclic codesminimum distancedual distancedefining setssquare-root boundReed-Muller codescyclotomic cosets
0
0 comments X

The pith

Binary cyclic codes of length 2^m-1 and dimension near n/2 can be built with both minimum distance and dual distance at least roughly sqrt(n).

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

The paper gives explicit algebraic constructions for binary cyclic codes of length n=2^m-1. When m is even the new codes have dimension 2^{m-1} plus or minus 1 and satisfy d at least 2^{m/2} minus 1 together with d_perp at least 2^{m/2}. When m is odd two families are presented whose distances multiply to roughly 2n asymptotically. These parameters improve earlier constructions that lost one distance when the other grew, and the product bound is reached only by punctured Reed-Muller codes among known cyclic codes of this dimension.

Core claim

The authors construct families of binary cyclic codes with parameters [2^m-1, 2^{m-1} plus or minus 1, d] where d is at least 2^{m/2} minus 1 and d_perp is at least 2^{m/2} when m is even; when m is the product of two distinct primes they obtain codes with k equal to (n plus 1)/2 and d larger than n over log base 2 of n; when m is odd they obtain two families with d at least 2^{(m+1)/2} minus 1 and d_perp at least 2^{(m+1)/2}, or d at least 2^{(m+3)/2} minus 15 and d_perp at least 2^{(m-1)/2}, so that the product d times d_perp reaches 2n asymptotically.

What carries the argument

Defining sets in the cyclotomic cosets that determine the generator polynomial of the cyclic code.

If this is right

  • The codes correct more errors while keeping a good dual distance useful for applications such as cryptography.
  • Infinite families exist where both distances grow like the square root of the length.
  • For odd m the product of the two distances is asymptotically 2n, approaching the best possible for dimension near n/2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same defining-set technique might be adapted to obtain similar simultaneous lower bounds for non-cyclic linear codes or for lengths that are not Mersenne numbers.
  • Explicit generator polynomials for moderate m could be used to test whether the actual distances exceed the proven lower bounds.
  • The constructions suggest that the usual trade-off between d and d_perp for cyclic codes is not as strict as earlier examples indicated.

Load-bearing premise

The algebraic constructions via defining sets actually produce codes whose minimum distances meet or exceed the stated lower bounds.

What would settle it

Compute the true minimum distance of the generator polynomial for the smallest even m (such as m=4 giving n=15) and check whether it is at least 3.

read the original abstract

Binary cyclic codes are worth studying due to their applications and theoretical importance. It is an important problem to construct an infinite family of cyclic codes with large minimum distance $d$ and dual distance $d^{\perp}$. In recent years, much research has been devoted to improving the lower bound on $d$, some of which have exceeded the square-root bound. The constructions presented recently seem to indicate that when the minimum distance increases, the minimum distance of its dual code decreases. In this paper, we focus on the new constructions of binary cyclic codes with length $n=2^m-1$, dimension near $n/2$ and both relatively large minimum distance and dual distance. When $m$ is even, we construct a family of binary cyclic codes with parameters $[2^m-1,2^{m-1}\pm1,d]$, where $d\ge 2^{m/2}-1$ and $d^\perp\ge2^{m/2}$. Both the minimum distance and the dual distance are significantly better than the previous results. When $m$ is the product of two distinct primes, we construct some cyclic codes with dimensions $k=(n+1)/2$ and $d>\frac{n}{\log_2n},$ where the lower bound on the minimum distance is much larger than the square-root bound. When $m$ is odd, we present two families of binary $[2^m-1,2^{m-1},d]$ cyclic codes with $d\ge2^{(m+1)/2}-1$, $d^\perp\ge2^{(m+1)/2}$ and $d\ge2^{(m+3)/2}-15$, $d^\perp\ge2^{(m-1)/2}$ respectively, which leads that $d\cdot d^\perp$ can reach $2n$ asymptotically. To the best of our knowledge, for the binary cyclic codes with length $n=2^m-1$ and dimension $k=(n\pm1)/2$, except for the punctured binary Reed-Muller codes, there is no other construction of binary cyclic codes that reaches this bound.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript constructs new families of binary cyclic codes of length n=2^m-1 with dimension k near n/2. For even m it gives [n, 2^{m-1}±1, d] codes with d≥2^{m/2}-1 and d^⊥≥2^{m/2}. For m the product of two distinct primes it gives codes with k=(n+1)/2 and d>n/log_2 n. For odd m it gives two families of [n, 2^{m-1}, d] codes, one with d≥2^{(m+1)/2}-1 and d^⊥≥2^{(m+1)/2}, the other with d≥2^{(m+3)/2}-15 and d^⊥≥2^{(m-1)/2}, so that d·d^⊥ reaches 2n asymptotically; these are asserted to be the only such constructions besides punctured Reed-Muller codes.

Significance. If the distance lower bounds are rigorously established, the constructions would supply explicit algebraic families of high-rate binary cyclic codes whose (d,d^⊥) trade-off improves on prior work and, for odd m, asymptotically matches the product bound previously achieved only by punctured RM codes. The even-m and two-prime-m families also exceed the square-root bound in a regime where both distances are controlled simultaneously.

major comments (3)
  1. [§3] §3 (even-m construction): the BCH-bound argument requires that the chosen defining set in GF(2^m)^* produces a run of at least 2^{m/2}-2 consecutive powers; when m is composite the cyclotomic cosets may introduce gaps that shorten the designed distance below the claimed 2^{m/2}-1. An explicit verification that no such gaps occur (or a corrected bound) is needed for the central claim.
  2. [§4] §4 (odd-m second family): the lower bound d≥2^{(m+3)/2}-15 is obtained by a variant of the BCH bound that subtracts a fixed constant; the derivation of the constant 15 and confirmation that it remains valid for all odd m (including those with multiple prime factors) must be supplied, because any m-dependent increase in the subtracted term would prevent d·d^⊥ from reaching 2n asymptotically.
  3. [Introduction] Comparison paragraph (Introduction): the assertion that only punctured Reed-Muller codes previously attained the d·d^⊥≈2n bound for k=(n±1)/2 must be supported by a precise statement of the parameters of the new codes versus the punctured RM codes; without this it is unclear whether the new families are genuinely distinct or merely re-derivations.
minor comments (2)
  1. [Abstract] The abstract claims 'd·d^⊥ can reach 2n asymptotically' but does not state the precise rate at which the product approaches 2n; a short sentence giving the leading term would improve clarity.
  2. [Table 1] Table 1 (or the parameter table for small m) should list both the designed distance from the BCH argument and the actual minimum distance obtained by exhaustive search for at least one composite even m (e.g., m=6) to illustrate that the bound is attained.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will revise the paper accordingly to improve rigor and clarity.

read point-by-point responses

  1. Referee: [§3] §3 (even-m construction): the BCH-bound argument requires that the chosen defining set in GF(2^m)^* produces a run of at least 2^{m/2}-2 consecutive powers; when m is composite the cyclotomic cosets may introduce gaps that shorten the designed distance below the claimed 2^{m/2}-1. An explicit verification that no such gaps occur (or a corrected bound) is needed for the central claim.

    Authors: We thank the referee for highlighting this potential issue. In our even-m construction the defining set is explicitly chosen as a union of cyclotomic cosets corresponding to consecutive exponents in GF(2^m)^* that remain consecutive after accounting for the coset action, because the even-m condition ensures alignment via quadratic subfield properties. We will add an explicit lemma in the revised Section 3 proving that no gaps occur in the required run of length 2^{m/2}-2 for all even m (including composites), thereby confirming the BCH bound yields d ≥ 2^{m/2}-1 without reduction. revision: yes

  2. Referee: [§4] §4 (odd-m second family): the lower bound d≥2^{(m+3)/2}-15 is obtained by a variant of the BCH bound that subtracts a fixed constant; the derivation of the constant 15 and confirmation that it remains valid for all odd m (including those with multiple prime factors) must be supplied, because any m-dependent increase in the subtracted term would prevent d·d^⊥ from reaching 2n asymptotically.

    Authors: We agree the derivation must be supplied in full. The constant 15 bounds the maximum gap size in the defining set for the second odd-m family and is obtained by estimating the number of cyclotomic cosets that can intersect a given interval of length roughly 2^{(m+3)/2}; this number is at most 15 independently of m because it is controlled by the binary weight and the fixed structure of the generator polynomial for odd m. We will include the complete proof in the revised Section 4, verifying the bound holds uniformly for all odd m (including those with multiple prime factors) and thus preserves the asymptotic d · d^⊥ ≈ 2n. revision: yes

  3. Referee: [Introduction] Comparison paragraph (Introduction): the assertion that only punctured Reed-Muller codes previously attained the d·d^⊥≈2n bound for k=(n±1)/2 must be supported by a precise statement of the parameters of the new codes versus the punctured RM codes; without this it is unclear whether the new families are genuinely distinct or merely re-derivations.

    Authors: We will strengthen the introduction with a precise parameter comparison. Punctured Reed-Muller codes achieve [2^m-1, 2^{m-1}, d] with d ≈ 2^{⌊m/2⌋} and d^⊥ ≈ 2^{⌈m/2⌉} for odd m. Our two odd-m families use distinct defining sets (specific unions of cosets not matching the RM zero set) and yield the stated bounds d ≥ 2^{(m+1)/2}-1 with d^⊥ ≥ 2^{(m+1)/2} and d ≥ 2^{(m+3)/2}-15 with d^⊥ ≥ 2^{(m-1)/2}. We will add a short table or paragraph contrasting the constructions and parameters to clarify they are new algebraic families. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algebraic constructions are direct and self-contained

full rationale

The paper defines binary cyclic codes explicitly via defining sets in GF(2^m)^* and applies standard bounds (BCH and variants) to obtain the stated distance lower bounds. These steps consist of direct algebraic definitions and applications of known inequalities to the chosen roots; no quantities are defined in terms of the target distances, no parameters are fitted to data subsets and then renamed as predictions, and no load-bearing steps reduce to self-citations or prior ansatzes by the same authors. The central claims therefore rest on independent algebraic content rather than circular reduction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only; no free parameters, invented entities, or non-standard axioms are mentioned. The work relies on standard facts about cyclic codes over finite fields of characteristic 2.

pith-pipeline@v0.9.0 · 5933 in / 1214 out tokens · 28547 ms · 2026-05-22T21:06:52.155408+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Cyclic error-correcting codes in two symbol s,

    E. Prange, “Cyclic error-correcting codes in two symbol s,” TN-57-103, Tech. Rep., 1957

    work page 1957

  2. [2]

    Codes correcteurs d’erreurs,

    A. Hocquenghem, “Codes correcteurs d’erreurs,” Chiffers, vol. 2, pp. 147–156, 1959

    work page 1959

  3. [3]

    On a class of error cor recting binary group codes,

    R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error cor recting binary group codes,” Information and control , vol. 3, no. 1, pp. 68–79, 1960

    work page 1960

  4. [4]

    On the dimension and minimum distance of BCH codes over GF( q),

    Z. H. D. Y ue, “On the dimension and minimum distance of BCH codes over GF( q),” J. Electron., vol. 13, no. 3, pp. 216–221, 1996

    work page 1996

  5. [5]

    Minimum cyclotomic coset repr esentatives and their applications to BCH codes and goppa co des,

    D.-W. Y ue and G.-Z. Feng, “Minimum cyclotomic coset repr esentatives and their applications to BCH codes and goppa co des,” IEEE Transactions on Information Theory , vol. 46, no. 7, pp. 2625–2628, 2000

    work page 2000

  6. [6]

    On the minimum distance of composite-l ength BCH codes,

    D. Y ue and H. Zhu, “On the minimum distance of composite-l ength BCH codes,” IEEE Communications Letters , vol. 3, no. 9, pp. 269–271, 1999

    work page 1999

  7. [7]

    Some new r esults on dimension and bose distance for various classes of BCH codes,

    A. Cherchem, A. Jamous, H. Liu, and Y . Maouche, “Some new r esults on dimension and bose distance for various classes of BCH codes,” Finite Fields and Their Applications , vol. 65, p. 101673, 2020

    work page 2020

  8. [8]

    Parameters of Several Classes of BCH Codes,

    C. Ding, “Parameters of Several Classes of BCH Codes,” IEEE Transactions on Information Theory , vol. 61, no. 10, pp. 5322–5330, 2015

    work page 2015

  9. [9]

    The Bose and Minimum Distance of a Class of BCH Codes,

    C. Ding, X. Du, and Z. Zhou, “The Bose and Minimum Distance of a Class of BCH Codes,” IEEE Transactions on Information Theory , vol. 61, no. 5, pp. 2351–2356, 2015

    work page 2015

  10. [10]

    Two Families of LCD BCH C odes,

    S. Li, C. Li, C. Ding, and H. Liu, “Two Families of LCD BCH C odes,” IEEE Transactions on Information Theory , vol. 63, no. 9, pp. 5699–5717, 2017

    work page 2017

  11. [11]

    Dimensions of three types of B CH codes over GF( q),

    H. Liu, C. Ding, and C. Li, “Dimensions of three types of B CH codes over GF( q),” Discrete Mathematics, vol. 340, no. 8, pp. 1910–1927, 2017

    work page 1910

  12. [12]

    Five families of the narrow-sen se primitive BCH codes over finite fields,

    B. Pang and X. K. S. Zhu, “Five families of the narrow-sen se primitive BCH codes over finite fields,” Designs, Codes and Cryptography, vol. 89, no. 12, pp. 2679–2696, 2021

    work page 2021

  13. [13]

    An infinite family of binary cy clic codes with best parameters,

    Z. Sun, C. Li, and C. Ding, “An infinite family of binary cy clic codes with best parameters,” IEEE Transactions on Information Theory , vol. 70, no. 4, pp. 2411–2418, 2024

    work page 2024

  14. [14]

    Self-dual cyclic codes with square -root-like lower bounds on their minimum distances,

    H. Chen and C. Ding, “Self-dual cyclic codes with square -root-like lower bounds on their minimum distances,” IEEE Transactions on Information Theory, 2025

    work page 2025

  15. [15]

    Cyclic and negacyclic codes with opti mal and best known minimum distances,

    H. Chen and Y . Wu, “Cyclic and negacyclic codes with opti mal and best known minimum distances,” IEEE Transactions on Information Theory , vol. 70, no. 12, pp. 8628–8635, 2024

    work page 2024

  16. [16]

    Self-dual negacycl ic codes with variable lengths and square-root-like lower b ounds on the minimum distances,

    C. Xie, H. Chen, C. Ding, and Z. Sun, “Self-dual negacycl ic codes with variable lengths and square-root-like lower b ounds on the minimum distances,” IEEE Transactions on Information Theory , vol. 70, no. 7, pp. 4879–4888, 2024

    work page 2024

  17. [17]

    Two classes of constacyclic codes with a square-root-like lower bound,

    T. Chen, Z. Sun, C. Xie, H. Chen, and C. Ding, “Two classes of constacyclic codes with a square-root-like lower bound, ” IEEE Transactions on Information Theory , vol. 70, no. 12, pp. 8734–8745, 2024

    work page 2024

  18. [18]

    A new upper bound for linear codes and vanishing partial weight distributions,

    H. Chen and C. Xie, “A new upper bound for linear codes and vanishing partial weight distributions,” IEEE Transactions on Information Theory , vol. 70, no. 12, pp. 8713–8722, 2024

    work page 2024

  19. [19]

    Another infinite family of bin ary cyclic codes with best parameters known,

    Y . Wu, Z. Sun, and C. Ding, “Another infinite family of bin ary cyclic codes with best parameters known,” IEEE Transactions on Information Theory , vol. 70, no. 6, pp. 4110–4116, 2024

    work page 2024

  20. [20]

    Infinite families of cycli c and negacyclic codes supporting 3-designs,

    X. Wang, C. Tang, and C. Ding, “Infinite families of cycli c and negacyclic codes supporting 3-designs,” IEEE Transactions on Information Theory , vol. 69, no. 4, pp. 2341–2354, 2023

    work page 2023

  21. [21]

    W. C. Huffman and V . Pless, Fundamentals of error-correcting codes . Cambridge university press, 2010

    work page 2010

  22. [22]

    Polynomial codes and finite geom etries,

    E. Assmus Jr and J. Key, “Polynomial codes and finite geom etries,” Handbook of coding theory , vol. 2, no. part 2, pp. 1269–1343, 1998

    work page 1998

  23. [23]

    Cyclotomic constructions of cyclic codes wit h length being the product of two primes,

    C. Ding, “Cyclotomic constructions of cyclic codes wit h length being the product of two primes,” IEEE transactions on information theory , vol. 58, no. 4, pp. 2231–2236, 2011

    work page 2011

  24. [24]

    On cyclic codes of composite length and the mi nimum distance,

    M. Xiong, “On cyclic codes of composite length and the mi nimum distance,” IEEE Transactions on Information Theory , vol. 64, no. 9, pp. 6305–6314, 2018

    work page 2018

  25. [25]

    On cyclic codes of composite leng th and the minimum distance II,

    M. Xiong and A. Zhang, “On cyclic codes of composite leng th and the minimum distance II,” IEEE Transactions on Information Theory , vol. 67, no. 8, pp. 5097–5103, 2021

    work page 2021

  26. [26]

    Binary [n, (n + 1)/2] cyclic codes with good minimum distances,

    C. Tang and C. Ding, “Binary [n, (n + 1)/2] cyclic codes with good minimum distances,” IEEE Transactions on Information Theory , vol. 68, no. 12, pp. 7842–7849, 2022

    work page 2022

  27. [27]

    Five infinite families of bina ry cyclic codes and their related codes with good parameters ,

    H. Liu, C. Li, and C. Ding, “Five infinite families of bina ry cyclic codes and their related codes with good parameters ,” Finite Fields and Their Applications, vol. 91, p. 102270, 2023

    work page 2023

  28. [28]

    Several families of binary cyclic codes with go od parameters,

    Z. Sun, “Several families of binary cyclic codes with go od parameters,” Finite Fields and Their Applications , vol. 89, p. 102200, 2023

    work page 2023

  29. [29]

    Explicit cyclic and quasi- cyclic codes with optimal, best known parameters and large r elative minimum distances,

    C. Xie, H. Chen, and C. Y uan, “Explicit cyclic and quasi- cyclic codes with optimal, best known parameters and large r elative minimum distances,” IEEE Transactions on Information Theory , vol. 70, no. 12, pp. 8688–8697, 2024. 25

    work page 2024

  30. [30]

    F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes . Elsevier, 1977, vol. 16

    work page 1977

  31. [31]

    A construction method of balanced rotation symmetric boolean functions on arbitr ary even number of variables with optimal algebraic immunity,

    S. Mesnager, S. Su, and H. Zhang, “A construction method of balanced rotation symmetric boolean functions on arbitr ary even number of variables with optimal algebraic immunity,” Designs, Codes and Cryptography , vol. 89, pp. 1–17, 2021

    work page 2021

  32. [32]

    Bounds on the minimum distance of linear cod es and quantum codes,

    M. Grassl, “Bounds on the minimum distance of linear cod es and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on 2025-03-18

    work page 2007