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

1. Problem Statement

The paper addresses the fundamental challenge in coding theory of constructing infinite families of binary cyclic codes with length $n = 2^m - 1$ and dimension $k \approx n/2$ that simultaneously possess:

• A large minimum distance ($d$).
• A large dual distance ($d^\perp$).

Context & Motivation:

• Historically, there is a trade-off: as the minimum distance $d$ of a cyclic code increases, the dual distance $d^\perp$ tends to decrease.
• The "Square-root bound" ($d \approx \sqrt{n}$) is a common lower bound for many known constructions.
• While punctured binary Reed-Muller codes achieve $d \cdot d^\perp \approx 2n$, they are limited to specific parameters (odd $m$, specific dimensions).
• Existing constructions for even $m$ or composite $m$ often yield parameters where $d \cdot d^\perp$ is significantly lower (e.g., $\approx n/4$ or $\approx n/16$).
• The goal is to break this trade-off and construct codes where the product $d \cdot d^\perp$ asymptotically approaches $n$ or even $2n$ for a broader range of $m$.

2. Methodology

The authors employ algebraic coding theory techniques, specifically focusing on the defining sets of cyclic codes via 2-cyclotomic cosets.

• Defining Sets & BCH Bound: A binary cyclic code $C$ is defined by a set of roots $Z$ of its generator polynomial. The minimum distance $d$ is lower-bounded by the BCH bound if $Z$ contains a sequence of consecutive integers. The dual distance $d^\perp$ is determined by the consecutive integers in the complement of $Z$ (specifically $-(Z_n \setminus Z)$).
• Symmetry and Rotation: The authors utilize the mapping $\pi$ from integers to binary vectors and the cyclic shift operator $\rho$. They construct defining sets that are unions of cyclotomic cosets by ensuring the set of binary vectors is invariant under rotation ($\rho(\pi(Z)) = \pi(Z)$).
• Case-Specific Constructions: The paper divides the problem into three distinct cases based on the properties of the integer $m$:
  1. $m$ is even: Utilizing rotation-symmetric Boolean function concepts to partition the vector space based on Hamming weights.
  2. $m = p_1 p_2$ (product of two distinct primes): Analyzing the structure of cyclotomic cosets with sizes $p_1$, $p_2$, and $p_1 p_2$ to construct defining sets that exceed the square-root bound.
  3. $m$ is odd: Constructing sets based on the parity of Hamming weights and specific coset leaders to maximize the consecutive sequences in both the defining set and its complement.

3. Key Contributions and Results

The paper presents three main families of constructions, summarized below:

A. Case 1: $m$ is Even

• Construction: The authors define sets $B, T, G$ based on the equality of the first and second halves of binary vectors (rotation symmetry). They partition the space into sets $S_1$ and $S_2$ to form defining sets $Z_1$ and $Z_2$.
• Parameters:
  • Codes with parameters $[2^m-1, 2^{m-1} \pm 1, d]$.
  • Minimum Distance: $d \ge 2^{m/2} - 1$.
  • Dual Distance: $d^\perp \ge 2^{m/2}$.
• Significance: These parameters significantly improve upon previous results (e.g., Tang et al. [26]), where the bounds were roughly $2^{(m-2)/2}$. The product $d \cdot d^\perp \approx n$.

B. Case 2: $m = p_1 p_2$ (Product of Two Distinct Primes)

• Construction: The authors analyze the specific sizes of cyclotomic cosets when $m$ is a product of primes. They construct defining sets by carefully selecting coset leaders to maximize the consecutive sequence length.
• Parameters:
  • Codes with dimension $k = 2^{m-1}$.
  • Minimum Distance: $d$ is significantly larger than the square-root bound. Specifically, for $p_1=2$, $d \ge \frac{2^{2p-4}}{2^p} + \dots$, and for odd primes, $d$ exceeds $\frac{n}{\log_2 n}$.
  • Dual Distance: $d^\perp \ge 2^{\lfloor \log_2 p_1 p_2 \rfloor + 1} - 1$.
• Significance: This construction achieves a minimum distance lower bound much larger than $\sqrt{n}$ and even larger than $\frac{n}{\log_2 n}$ (a bound previously achieved only for prime $m$). The product $d \cdot d^\perp \approx n$.

C. Case 3: $m$ is Odd

The authors present two families for odd $m$:

1. Family 1:
   • Parameters: $[2^m-1, 2^{m-1}, d]$.
   • Distances: $d \ge 2^{(m+1)/2} - 1$ and $d^\perp \ge 2^{(m+1)/2}$.
   • Significance: These parameters match or exceed the punctured binary Reed-Muller codes.
2. Family 2:
   • Parameters: $[2^m-1, 2^{m-1}, d]$.
   • Distances: $d \ge 4 \cdot (2^{(m-1)/2} - 4) + 1$ and $d^\perp \ge 2^{(m-1)/2}$.
   • Significance: This family achieves a larger minimum distance than the punctured Reed-Muller codes and the construction in [28], while maintaining the same dual distance.

• Overall Impact: For these families, $d \cdot d^\perp \approx 2n$.

4. Significance and Conclusion

• Breaking the Trade-off: The paper successfully constructs families where both $d$ and $d^\perp$ are large, challenging the notion that increasing one necessarily drastically reduces the other.
• Asymptotic Bounds:
  • For even $m$ and composite $m=p_1 p_2$, the product $d \cdot d^\perp$ asymptotically approaches $n$.
  • For odd $m$, the product approaches $2n$, matching the performance of punctured Reed-Muller codes but with potentially better minimum distances.
• Novelty: To the best of the authors' knowledge, except for punctured Reed-Muller codes, no other binary cyclic code constructions with length $n=2^m-1$ and dimension $k \approx n/2$ reach the bound $d \cdot d^\perp \approx 2n$.
• Open Problem: The authors propose an open problem: Can $\Delta = \limsup_{n \to \infty} \frac{d \cdot d^\perp}{n}$ be strictly greater than 2? They suggest that while current constructions reach 2, it remains unknown if a family exists that exceeds this limit.

In summary, this work provides significant theoretical advancements in the construction of binary cyclic codes, offering new infinite families with superior parameters compared to existing literature, particularly in balancing minimum distance and dual distance.