Construction of cyclic codes with large minimum distance from power functions over odd characteristic finite fields

Technical Summary: Construction of Cyclic Codes with Large Minimum Distance from Power Functions over Odd Characteristic Finite Fields

Problem Statement
Cyclic codes with dimensions exceeding half the code length ($k > v/2$) and minimum distances greater than the square root of the code length ($d > \sqrt{v}$) are highly desirable for applications requiring high transmission efficiency and strong error correction, such as communication systems, post-quantum cryptography, and radar. While significant progress has been made in constructing such codes over binary fields (characteristic 2), the construction of non-binary cyclic codes using power functions with known differential uniformity over finite fields of odd characteristic has received comparatively less attention. This paper addresses the gap in constructing infinite families of $q$-ary cyclic codes (where $q$ is a power of an odd prime) that achieve favorable parameters, specifically targeting dimensions $k > (q^m - 1)/2$ and minimum distances $d > \sqrt{q^m - 1}$.

Methodology
The authors employ the trace sequence approach to construct cyclic codes. The methodology involves the following steps:

1. Sequence Definition: For a given finite field $\mathbb{F}_{q^m}$ and a primitive element $\alpha$, a sequence $s_\infty = (s_t)_{t \ge 0}$ is defined via the trace function: $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, where $F(x)$ is a selected power function over $\mathbb{F}_{q^m}$.
2. Generator Polynomial Determination: The cyclic code $C_F$ is generated by the minimal polynomial $M_s(x)$ of the sequence $s_\infty$. The dimension of the code is determined by the linear span ($L_s$) of the sequence, which corresponds to the number of non-zero coefficients in the trace expansion of the sequence.
3. Power Function Selection: The paper selects specific monomials $F(x) = x^d$ with known differential uniformity over $\mathbb{F}_{q^m}$ (where $q$ is odd). The selection criteria depend on the parity of $m$ and the specific structure of the exponent $d$.
4. Algebraic Analysis:
   • Linear Span: The authors utilize $q$-adic expansions, Lucas' Theorem, and properties of cyclotomic cosets to expand the trace function and identify the non-zero terms. This allows for the exact calculation of the linear span $L_s$ and the construction of the generator polynomial $M_s(x)$.
   • Minimum Distance Bounds: The lower bounds on the minimum distance $d$ are established using the BCH bound and the Hartmann-Tzeng bound. This involves identifying consecutive integers or specific sets within the defining set (the roots of the generator polynomial).
   • Exact Distances: For specific cases, the authors construct explicit codewords of specific weights to determine the exact minimum distance, often relating the constructed codes to known primitive BCH codes.

Key Contributions and Results
The paper presents several infinite families of $q$-ary cyclic codes of length $v = q^m - 1$ with dimensions exceeding $v/2$. The specific constructions and results are categorized by the power functions used:

1. Ternary Codes from $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ odd):

   • Constructed over $\mathbb{F}_{3^m}$.
   • The linear span is $3m + N_3(m)$, yielding dimension $3^m - 1 - 3m - N_3(m)$.
   • The minimum distance $d$ satisfies $3 \le d \le 8$.
   • Example: For $m=5$, a $[242, 226, 5]$ code is obtained, which is almost optimal.

2. $p$-ary Codes from $x^{p^{m/2} + 2}$ ($m$ even, $p$ odd):

   • Constructed over $\mathbb{F}_{p^m}$.
   • The linear span depends on $p$ and $m$ (e.g., $N_p(m) + 5m/2$ for $p=3$).
   • Minimum distance bounds are established: $d \ge 3$ (for $p=3$), $d \ge 5$ (for $p \ge 5, p \nmid m$), and $d \ge 4$ (for $p \ge 5, p \mid m$).
   • Exact distances are determined for specific cases (e.g., $d=5$ for $p=5, p \nmid m$).

3. Codes from $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$ odd):

   • This construction addresses a specific case where the exponent is a geometric series sum.
   • The paper derives a general formula for the linear span involving sums of $N_p(k)$ terms.
   • Significance: This construction partially resolves Open Problem 5.31 posed by Ding [35], which concerned the dimension and generator polynomial of cyclic codes for $t = (m+1)/2$ with $m$ odd.
   • Lower bounds on $d$ are provided, ranging from 2 to $2^{t-2} + 2$ depending on $q$ and $t$.

4. Ternary Codes from $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ odd):

   • Utilizes a monomial that is a Perfect Nonlinear (PN) function or 4-uniform depending on $m$.
   • The linear span is calculated as $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$.
   • Minimum distance bounds are established, with $d \ge 8$ under specific divisibility conditions.

5. $p$-ary Codes from $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$):

   • Generalizes previous binary results to odd characteristic.
   • The linear span is derived using $p$-adic expansions and specific set definitions ($\hat{\Gamma}(t)$).
   • The minimum distance lower bounds are shown to be significantly better than the square root of the code length in many cases (e.g., $d \ge p^h + 2$).
   • Exact distances are determined for cases where $h | m$, showing the code is equivalent to a narrow-sense primitive BCH code with designed distance $p^h + 1$.

6. Codes from $x^{2 \cdot p^{m/2} - 1}$ and $x^{p^{2h} - p^h + 1}$:

   • These sections handle even and odd $m$ respectively with specific exponents.
   • The authors derive complex expressions for the linear span and minimal polynomials.
   • Theorem 11 and Theorem 13 demonstrate that the lower bounds on minimum distance for these families are often significantly superior to the square root bound ($\sqrt{v}$).

Significance and Claims
The paper claims to extend the binary framework of Ding and Zhou [14] to a non-binary setting. The primary significance lies in:

• Parameter Improvement: The constructed codes achieve dimensions $k > (q^m - 1)/2$ and minimum distances $d > \sqrt{q^m - 1}$, balancing code rate and error-correcting capability effectively.
• Resolution of Open Problems: The work partially resolves Open Problem 5.31 from Ding [35] regarding the ternary cyclic code defined by $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ with $m$ odd.
• Optimality: Several constructed codes (and their duals) are identified as optimal or almost optimal when compared against the Database of best known linear codes [47].
• Theoretical Advancement: The paper provides explicit formulas for the linear span and generator polynomials for infinite families of codes, utilizing advanced number-theoretic tools (cyclotomic cosets, $p$-adic expansions, Lucas' Theorem) to handle the complexities of odd characteristic fields.

The authors conclude that these constructions provide a rich source of codes suitable for demanding applications and suggest that further exploration of power functions over odd characteristic fields could yield more optimal families. They also note the potential for these codes to be used in constructing quantum error-correcting codes via the CSS construction.