Duality and decoding of linearized Algebraic Geometry codes

1. Problem Statement

The paper addresses the decoding of Linearized Algebraic Geometry (LAG) codes, a family of error-correcting codes introduced in [BC24] that operate in the sum-rank metric. These codes generalize both classical Algebraic Geometry (AG) codes (Hamming metric) and linearized Reed–Solomon codes.

While LAG codes offer significant advantages—such as lengths not limited by the alphabet size and parameters approaching the sum-rank Singleton bound—prior to this work, no efficient decoding algorithm existed for the general LAG setting. The specific challenges addressed are:

• Duality: The lack of a clear characterization of the dual code for LAG codes, which is essential for syndrome-based decoding.
• Decoding: The absence of a polynomial-time decoding algorithm capable of correcting errors up to the theoretical limit in the sum-rank metric.
• Mathematical Framework: The need to extend classical function field theory (Riemann–Roch, Serre duality) to the context of division algebras over function fields to support these codes.

2. Methodology

The authors develop a comprehensive mathematical framework based on the theory of division algebras over function fields to solve the decoding problem.

A. Mathematical Foundations

• Setting: Let $K$ be a function field of an algebraic curve over a field $F$. Let $L/K$ be a cyclic extension of degree $r$ with Galois group generated by $\theta$. The authors consider the cyclic division algebra $D = L[T; \theta] / (T^r - x)$, where $x \in K$.
• Riemann–Roch Spaces: They define Riemann–Roch spaces $\Lambda_D(A)$ associated with divisors $A$ on $D$.
• Extended Divisors: To handle evaluation constraints, they introduce extended divisors $(A, W)$, consisting of a divisor $A$ and a subspace $W$ of the residual algebras at evaluation places.
• Differentials and Residues: They construct a module of differentials $\Omega_D$ and define residue endomorphisms. Crucially, they establish a Serre-type duality between the adelic space of $D$ and the differential space of the adjoint algebra $D^\dagger = L[T; \theta] / (T^r - x^{-1})$.

B. Key Theoretical Results

1. Riemann–Roch Theorem for Extended Divisors: The authors prove a generalized Riemann–Roch theorem for the pair $(A, W)$, relating the dimension of the space $\Lambda_D(A, W)$ to the dimension of a dual space involving the adjoint algebra $D^\dagger$ and a canonical divisor $K$.
   $$\lambda_D(A, W) = r \deg(A, W) + r(1-g) + \lambda_{D^\dagger}(K + \text{CoN}_r(D) - A, W^\perp)$$
2. Duality of Codes: Using the residue theorem and the Serre duality established above, they prove that the dual of a linearized AG code is a Linearized Differential (LD) code. Specifically:
   $$\text{LAG}_D(A, \mathcal{D})^\perp = \text{LD}_{D^\dagger}(A, \mathcal{D}) = \text{LAG}_{D^\dagger}(K + \text{CoN}_r(D) - A, \mathcal{D})$$
   This result identifies the dual code as another LAG code defined over the adjoint algebra, enabling the use of syndrome decoding.

C. Decoding Algorithm

The authors propose a polynomial-time decoding algorithm (Algorithm 1) analogous to the classical decoding of AG codes (e.g., the Guruswami-Sudan or Berlekamp-Massey-Sakata approaches adapted for AG codes). The algorithm proceeds in two main steps:

1. Error Localization:
   • The algorithm seeks a non-zero "localizing function" $f$ in a specific Riemann–Roch space of the adjoint algebra ($\Lambda_{D^\dagger}(A_1)$).
   • This function is found by solving a linear system where the syndrome of the received word vanishes when multiplied by $f$. The existence of such a function is guaranteed by the Riemann–Roch theorem if the error weight is below a certain threshold.
2. Syndrome Solving:
   • Once the localizing function $f$ is found, it restricts the possible locations of the error to the kernel of the evaluation of $f^\dagger$.
   • The algorithm then solves a second linear system to recover the error values within this restricted space.

3. Key Contributions

• Theoretical Extension: The paper successfully extends the Riemann–Roch theorem and Serre duality to the setting of cyclic division algebras over function fields, introducing the concept of extended divisors to handle evaluation constraints.
• Duality Characterization: It provides the first explicit characterization of the dual of LAG codes, showing they are isomorphic to LAG codes over the adjoint algebra.
• Decoding Algorithm: It presents the first polynomial-time decoding algorithm for general LAG codes with unramified evaluation places.
• Error Correction Capability: The algorithm can correct errors of sum-rank weight up to:
  $$\rho_{algo} = \left\lfloor \frac{d^*(A) - g - 1}{2} \right\rfloor$$
  where $d^*(A)$ is the designed minimum distance and $g$ is the genus of the division algebra. This matches the decoding radius of classical AG codes in the Hamming metric.
• Implementation: The authors provide a SageMath implementation of the algorithm, demonstrating its feasibility and providing benchmarks on various Kummer and Artin–Schreier-Witt extensions.

4. Results

• Correctness: The authors prove that the algorithm correctly decodes any error with sum-rank weight $\leq \rho_{algo}$, assuming the evaluation places are unramified and a specific non-split rational place exists (Hypothesis 2.2.7).
• Complexity: The complexity of the algorithm is polynomial in the number of evaluation places ($s$) and the degree of the extension ($r$). This is achieved because the dimensions of the involved Riemann–Roch spaces are linear in $r$, and the linear systems solved are of manageable size.
• Benchmarks: The SageMath implementation (Appendix A) successfully decodes random errors for various code parameters (e.g., degrees 2 through 8 extensions) within seconds on standard hardware, validating the theoretical complexity.

5. Significance

This work is significant for several reasons:

• Bridging Theory and Practice: It transforms LAG codes from a theoretical construction with good parameters into a practical coding scheme with a viable decoding mechanism.
• Generalization: It unifies the theory of classical AG codes and linearized Reed–Solomon codes under a single framework (division algebras), showing that the powerful tools of algebraic geometry apply to the sum-rank metric.
• Cryptographic and Storage Applications: Sum-rank metric codes are critical for network coding, distributed storage, and post-quantum cryptography (specifically code-based cryptography). The ability to decode these codes efficiently makes LAG codes a strong candidate for these applications, particularly where long code lengths are required without increasing the alphabet size.
• Mathematical Innovation: The introduction of the adjoint algebra and the specific duality theorem for division algebras opens new avenues for research in non-commutative algebraic geometry and coding theory.

In summary, the paper establishes the theoretical duality of linearized AG codes and leverages this to construct an efficient, provably correct decoding algorithm, significantly advancing the state-of-the-art in sum-rank metric coding.