Permutation Decoding of AG Codes from Curves Defined by Separated Polynomials

arXiv:2608.03592 · cs.IT, math.AG, math.IT · Submitted 2026-08-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Permutation Decoding of AG Codes from Curves Defined by Separated Polynomials".

Jane: Here's the gist of the paper. Permutation decoding is an efficient algebraic decoding method introduced by MacWilliams

27: for linear codes possessing a sufficiently rich automorphism group This approach has been successfully applied to several important families of codes, including cyclic codes, Reed–Muller codes, Hadamard codes, and algebraic geometry codes <ref:2608.03592#pg15>.

Tom: In this work, we investigate permutation decoding for algebraic geometry (AG) codes arising from algebraic curves defined by separated polynomials <ref:2608.03592#pg12>.

Jane: Permutation Decoding Concepts Permutation decoding is an efficient algebraic decoding method introduced by MacWilliams

27: for linear codes possessing a sufficiently rich automorphism group The method exploits permutations from the automorphism group of the code to move error positions outside a fixed information set <ref:2608.03592#pg13>.

Tom: Specifically, if C is a linear code with automorphism group Aut(C), one searches for a set of permutations, called a PD-set (permutation decoding set), such that every correctable error pattern can be displaced from the information positions by at least one permutation in the set

23: Algebraic Geometry Codes and Structure The Algebraic Geometry code (AG code) C(D, G) arising from the curve X is defined as C(D, G):= (f(P1),..., f(Pn)) ∈ Fn q: f ∈ L(G), where L(G) = (f ∈ Fq(X): (f) ≥ −G)∪0 denotes the Riemann-Roch space associated to divisor G <ref:2608.03592#pg15>.

Paper summary: Jane: So we've been looking at this paper, "Permutation Decoding of AG Codes from Curves Defined by Separated Polynomials," and what they’ve shown is that using the automorphism groups of these specific algebraic curves gives us a way to build efficient decoding sets for algebraic geometry codes.

Tom: Basically, the thesis is that you take those symmetries from the curve itself and use them to construct permutations on the code, which lets you move error positions outside your information set more effectively.

Lu: They introduced this idea by defining a class of curves called SAP curves, and they showed that for one-point codes on these curves, you can get permutation decoding sets that correct burst errors supported on coordinates sharing a common coordinate.

Meng: The implication for me is that if we are working with codes derived from structured geometric objects, we might be able to design corrections that are tailored to the structure of the noise itself rather than just treating it as random corruption.

Jane: That's right, and they highlighted special cases like Hermitian curves where you get even stronger decoding sets by using additional automorphisms. They also showed that for certain special curves, you can handle errors occurring at any two rational-point positions with a set size related to q times the number of those specific points.

Tom: The main thing to remember is that this method provides a constructive way to design these decoding sets based on the underlying geometry, which simplifies how we approach correcting structured burst errors in these AG codes.

Lu: And looking ahead, they suggest that this technique isn't limited just to SAP curves; the authors are pointing toward applying it to other families of codes, like maximal curves or Deligne–Lusztig curves, with large automorphism groups.

Meng: For production, I'm still waiting on a concrete analysis of the runtime versus a baseline decoder. We know the method works theoretically for these specific error patterns and sizes, but we need to see how much faster it actually runs on massive datasets before we commit resources.

Jane: That’s fair, Meng. The paper is building the foundation by showing that this interplay between curve automorphisms and code structure is a powerful design tool, even if the engineering side still needs more work on complexity.

Conclusion: Tom: So we've looked at this paper, "Permutation Decoding of AG Codes from Curves Defined by Separated Polynomials," and what they're showing is that using the symmetries built into these specific geometric curves lets us design much smarter ways to correct errors in algebraic geometry codes.

Jane: That sounds really complicated. Can you tell me, if we put that in simple terms, what does this mean for someone just listening? Is it a new way to fix bad data?

Lu: It's about using the structure of the curve—the way its points are arranged and how they map onto each other—to create a specific set of moves on the code. This set is called a permutation decoding set, and it lets us shift error positions around in a clever way so we can fix them.

Meng: So, what's the actual gain here? What kind of errors are we talking about? Is this for random noise, or something more specific?

Tom: It’s specifically for burst errors. The authors show that by using these curve symmetries, you can correct bursts that happen in positions related to points sharing a certain coordinate. They even found ways to handle errors occurring at any two rational point positions on some special curves.

Jane: That's interesting because normally decoding is just about finding the closest valid codeword. This paper suggests we can use the geometry itself as a guide for where those errors are likely to be, which sounds like it could be much more efficient than brute-force searching.

Lu: Exactly. The power comes from exploiting the automorphism group of these curves to build these permutations automatically, and that structure dictates exactly which error patterns you can handle efficiently.

Meng: From a deployment standpoint, I need to know how big this set of permutations gets. How much computational overhead is there for building this set versus just running a standard decoder? Because if it’s too slow, it doesn't matter if the theory is cool.

Tom: The paper shows that for certain special curves, the size of these required sets can be managed effectively, especially when you look at specific error types. It’s not about making the set infinitely large; it’s about finding a manageable size that works for certain error distributions.

Jane: So if I'm listening to this show and I'm dealing with data from a curve like this, what does that imply for the kind of errors I should expect to see? Are these burst errors common in the real world applications of these codes?

Tom: These specific burst patterns are associated with points having shared first or second coordinates. So, if you know the structure of your underlying algebraic geometry code, you can anticipate and target those specific types of corruption.

Lu: And this isn't just theoretical; they're extending this work from older types of curves to a whole new family defined by separated polynomials, which gives us a much broader class of codes to look at.

Meng: Broader class is good, but I still need to know where this stops working. The authors mention specific conditions for the "SAP curves." If my real-world data doesn't fit those exact geometric constraints, does the whole permutation decoding idea fall apart immediately?

Jane: That’s a fair caution. It tells us that while the technique is powerful, it relies heavily on those very specific geometric properties of the curve to work reliably.

Tom: The authors are pointing toward other families of curves too—like Deligne–Lusztig curves and Suzuki curves—where we might find similar symmetry-based decoding methods, so this opens up a lot more avenues for research.

Lu: Yeah, the implication is that we need to keep looking at these codes with rich automorphism groups because that’s where you find these kinds of powerful decoding tools.

Meng: So yeah, it’s an interesting theoretical tool with very specific geometric prerequisites, but it definitely gives us a better map for understanding what kind of structural errors we should be worried about in these advanced codes.

cs.IT, math.AG, math.IT

Submitted: 2026-08-04

Updated: 2026-11-12

License: http://creativecommons.org/publicdomain/zero/1.0/

Importance score: 81/100

The gist: Permutation decoding is an efficient algebraic decoding method introduced by MacWilliams [27] for linear codes possessing a sufficiently rich automorphism group This approach has been successfully…

Key concepts

Permutation Decoding
An efficient algebraic decoding method that uses permutations from a code's automorphism group to move error positions outside a fixed information set. It works by finding a set of permutations (a PD-set) that can displace any correctable error pattern.
Algebraic Geometry Codes (AG Codes)
These codes are constructed from algebraic curves defined over finite fields. They are defined using Riemann-Roch spaces associated with divisors on the curve, providing a rich structure for coding theory applications.
SAP Curves
A fundamental class of algebraic curves over finite fields characterized by specific conditions involving additive polynomials, a point P*, and an automorphism. These curves possess rich arithmetic and geometric structure that is exploited for decoding.

Terminology

Summary

Permutation decoding is an efficient algebraic decoding method introduced by MacWilliams [27] for linear codes possessing a sufficiently rich automorphism group This approach has been successfully applied to several important families of codes, including cyclic codes, Reed–Muller codes, Hadamard codes, and algebraic geometry codes <ref:2608. p. 1

Where the paper says it

The main advantage of permutation decoding lies in its ability to simplify the decoding procedure by combining syndrome decoding with the symmetry properties of the code. This approach has been successfully applied to several important families of codes, including cyclic codes, Reed–Muller codes, Hadamard codes, and algebraic geometry codes.

03592#pg15>. In this work, we investigate permutation decoding for algebraic geometry (AG) codes arising from algebraic curves defined by separated polynomials <ref:2608. p. 0
Where the paper says it

CASTELLANOS, GUILHERME TIZZIOTTI, AND WILSON OLAYA-LEON´ Abstract. In this work, we investigate permutation decoding for algebraic geometry (AG) codes arising from algebraic curves defined by separated polynomials.

03592#pg12>.

Permutation Decoding Concepts

Permutation decoding is an efficient algebraic decoding method introduced by MacWilliams [27] for linear codes possessing a sufficiently rich automorphism group The method exploits permutations from the automorphism group of the code to move error positions outside a fixed information set <ref:2608.03592#pg13>. Specifically, if C is a linear code with automorphism group Aut(C), one searches for a set of permutations, called a PD-set (permutation decoding set), such that every correctable error pattern can be displaced from the information positions by at least one permutation in the set [23]

Algebraic Geometry Codes and Structure

The Algebraic Geometry code (AG code) C(D, G) arising from the curve X is defined as C(D, G):= (f(P1),..., f(Pn)) ∈ Fn q: f ∈ L(G), where L(G) = (f ∈ Fq(X): (f) ≥ −G)∪0 denotes the Riemann-Roch space associated to divisor G <ref:2608. p. 3

Where the paper says it

The Algebraic Geometry code (AG code) C(D, G) arising from the curve X is defined as C(D, G) := {(f(P1), . , f(Pn)) ∈ F n q : f ∈ L(G)}, where L(G) = {f ∈ Fq(X ) : (f) ≥ −G}∪{0} denotes the Riemann-Roch space associated to divisor G.

03592#pg15>. The set Supp(D) = (P1,. p. 3
Where the paper says it

On the other hand, we get a structure of Fq[t]-module on C(D, G) in the following way. The set Supp(D) = {P1, .

.., Pn) is isomorphic to the symmetric group Sn, and each σ ∈ P(Supp(D)) induces an Fq-linear mapping ˜σ of the code C(D, G) to Fn q by setting σ˜(f(P1),. p. 3
Where the paper says it

, Pn} be the support of the divisor D. Since #Supp(D) = n, we have that the permutation group P(Supp(D)) on Supp(D) is isomorphic to the symmetric group Sn, and each σ ∈ P(Supp(D)) induces an Fq-linear mapping ˜σ of the code C(D, G) to F n q by setting σ˜(f(P1), .

.., f(Pn)):= (f(σ(P1)),..., f(σ(Pn))) <ref:2608. p. 0
Where the paper says it

Mathematics Subject Classification (2020): 94B05, 11T71, 14G50. 1 arXiv:2608.

03592#pg15>. The set Supp(D) decomposes under the action of σ into r distinct orbits, O1,. p. 3
Where the paper says it

The set Supp(D) = {P1, . , Pn} decomposes under the action of σ into r distinct orbits, O1, .

.., Or <ref:2608. p. 0
Where the paper says it

Mathematics Subject Classification (2020): 94B05, 11T71, 14G50. 1 arXiv:2608.

03592#pg15>. Associated to a codeword (f(P1),. p. 2
Where the paper says it

The Information positions are the coordinates of a codeword that contain the symbols corresponding to the original message. The set of indices associated with these coordinates is called an information set, while the indices in its complement are referred to as check positions.

.., f(Pn)) ∈ C(D, G), we consider the polynomials hi(t) = O Xi−1 j=0 f(Pi,j)t j, i = 1,. p. 1
Where the paper says it

In [25], Lichtenwalner, L´opez, Matthews and Seneviratne investigated permutation decoding for AG codes arising from Hermitian and Norma-trace curves. In this paper, we consider permutation decoding of AG codes on curves defined by separated polynomials, generalizing the results presented in [25].

.., r>

SAP Curves and Automorphisms

Curves over finite fields defined by separated polynomials constitute a fundamental class of algebraic curves with rich arithmetic and geometric structure <ref:2608.03592#pg17>. A curve X∗ is called a SAP curve if it satisfies conditions (1), (2), and (3) involving additive polynomials, a point P∗, and an automorphism σ <ref:2608. p. 5

Where the paper says it

6 Note that, by definition of σ, we have ord(σ) = ord(α), hence ord(σ) | (q−1). Since X ∗ is defined by separated polynomials f and g, with f additive, and admits an automorphism that fixes an Fq-rational point such that its Weierstrass semigroup is generated by the degrees of f and g, from now on we will refer to a curve with these characteristics as SAP curve, Separable Additive Polynomial curve.

03592#pg18>. Special SAP curves are those that meet conditions (1) and (2) involving g(0)=0 and g(−a)=g(a), as well as the existence of an automorphism ϕωa a,b <ref:2608. p. 6
Where the paper says it

7 Although the problem of calculating the group of atomomorphisms for SAP curves in general is a difficult problem, we identified that some SAP curves have sets of automorphisms of interest for obtaining r-PD sets for some burst errors. In this sense we will call special SAP curve, and denote them by X ∗∗, those that meet the following conditions: (1*) g(0) = 0 and g(−a) = g(a) for all a ∈ F ∗ q ; (2*) if (a, b) ∈ X ∗∗(Fq), then (a) there exists ωa(x) ∈ Fq[x] such that ωa(0) = 0, ωa(−a) = −ωa(a) and f(ωa(a)) = 2g(a).

03592#pg18>.

Permutation Decoding Results

Theorem 4.1 shows that for a one-point code on the SAP curve X∗ and λ as in Proposition 3. p. 6

Where the paper says it

A straightforward computation shows that ωa(0) = 0, ωa(−a) = ωa(a) = −ωa(a), f(ωa(x)) = 0 = 2g(a) and by [21, Proposition 3. 1], for all (a, b) ∈ Fq 2 (Y2), ϕ ωa a,b : ( x 7→ x + a, y 7→ y + a 2qx 2 + a qx + b is an automorphism of C(D, λP∞), where D is the sum of all q 3 2 rational affine points of Y2 and P∞ is the only rational point at infinity of the Y2.

7 with i ≤ r − m, the set of permutations is a partial ν-PD set of sizel for bursts errors occurring in coordinates corresponding to points belonging to Qb <ref:2608. p. 2
Where the paper says it

The Information positions are the coordinates of a codeword that contain the symbols corresponding to the original message. The set of indices associated with these coordinates is called an information set, while the indices in its complement are referred to as check positions.

03592#pg15>. Theorem 4.3 establishes that for special SAP curves X∗∗, there exists a partiall-PD set of size q for burst errors impacting positions indexed by Pa, with a ∈ Fq <ref:2608. p. 6
Where the paper says it

7 Although the problem of calculating the group of atomomorphisms for SAP curves in general is a difficult problem, we identified that some SAP curves have sets of automorphisms of interest for obtaining r-PD sets for some burst errors. In this sense we will call special SAP curve, and denote them by X ∗∗, those that meet the following conditions: (1*) g(0) = 0 and g(−a) = g(a) for all a ∈ F ∗ q ; (2*) if (a, b) ∈ X ∗∗(Fq), then (a) there exists ωa(x) ∈ Fq[x] such that ωa(0) = 0, ωa(−a) = −ωa(a) and f(ωa(a)) = 2g(a).

03592#pg18>. Furthermore, Theorem 4. p. 1
Where the paper says it

This approach has been successfully applied to several important families of codes, including cyclic codes, Reed–Muller codes, Hadamard codes, and algebraic geometry codes. Furthermore, the construction of small PD-sets remains an active research topic due to its direct impact on decoding efficiency and computational complexity [16].

5 shows that for special SAP curves X∗∗, the set of permutations is a partial 2-PD set of size q · B capable of handling errors occurring at any two rational-point positions <ref:2608.03592#pg18>.

Conclusion and Future Work

The results presented here extend previous work on permutation decoding of AG codes from Hermitian and norm-trace curves to a broader family of curves defined by separated polynomials <ref:2608.03592#pg18>. They demonstrate that the interplay between the automorphism group of a curve and the geometric structure of its rational points provides a powerful tool for the design of efficient decoding strategies <ref:2608. p. 0

Where the paper says it

For these codes, we obtain permutation decoding sets that correct burst errors supported on coordinates associated with rational points sharing a common coordinate. We further identify a subclass of special SAP curves, including Hermitian curves, generalized Hermitian curves, and certain maximal curves, for which additional automorphisms yield more powerful decoding sets.

p. 0
Where the paper says it

For these codes, we obtain permutation decoding sets that correct burst errors supported on coordinates associated with rational points sharing a common coordinate. We further identify a subclass of special SAP curves, including Hermitian curves, generalized Hermitian curves, and certain maximal curves, for which additional automorphisms yield more powerful decoding sets.

03592#pg18>. Future research may focus on extending these techniques to AG codes arising from other families of curves with large automorphism groups, such as other maximal curves, Deligne–Lusztig curves, Suzuki and Ree curves, Giulietti–Korchm´aros curves, and related Galois-covered curves <ref:2608. p. 1
Where the paper says it

Hence, codes possessing large automorphism groups are particularly well suited for this decoding technique. This observation naturally motivates the study of AG codes arising from curves over finite fields defined by separated polynomials, since many such curves are known to admit rich and highly structured automorphism groups.

03592#pg18>. The construction of smaller PD-sets and a detailed analysis of the computational complexity of the resulting decoding procedures also remain promising directions for further study <ref:2608. p. 1
Where the paper says it

This approach has been successfully applied to several important families of codes, including cyclic codes, Reed–Muller codes, Hadamard codes, and algebraic geometry codes. Furthermore, the construction of small PD-sets remains an active research topic due to its direct impact on decoding efficiency and computational complexity [16].

03592#pg18>.

Pruning redundant reasoning tokens

The results presented here extend previous work on permutation decoding of AG codes from Hermitian and norm-trace curves to a broader family of curves defined by separated polynomials <ref:2608.03592#pg18>. They demonstrate that the interplay between the automorphism group of a curve and the geometric structure of its rational points provides a powerful tool for the design of efficient decoding strategies <ref:2608.03592#pg18>.

How the training signal is built

The construction of information and check positions for C(D, λP∗) is described by using the orbits of σ to obtain a description of information positions for C(D, λP∗), following the approach introduced in [8] via the root diagram of these codes <ref:2608. p. 6

Where the paper says it

Information positions for C(D, λP∗ ) In this section, we consider one-point AG codes C(D, λP∗ ) arising from a SAP curve X ∗ . We use the orbits of σ to obtain a description of information positions for C(D, λP ∗ ), following the approach introduced in [8] via the root diagram of these codes.

03592#pg15>. The characterization of information and check positions will be used in the following section to get a permutation decoding <ref:2608. p. 0
Where the paper says it

In this work, we investigate permutation decoding for algebraic geometry (AG) codes arising from algebraic curves defined by separated polynomials. Using automorphisms of the underlying curves, we construct permutation automorphisms of the associated algebraic geometry codes and exploit the resulting orbit structure to determine information and check positions.

03592#pg15>.

Where the gains come from

The gains come from exploiting automorphisms of the underlying curves to construct permutation automorphisms of the associated algebraic geometry codes and using their resulting orbit structure to determine information and check positions The results demonstrate that permutation decoding can be used to correct specific burst-error patterns associated with rational points sharing the same first or second coordinate <ref:2608. p. 0

Where the paper says it

In this work, we investigate permutation decoding for algebraic geometry (AG) codes arising from algebraic curves defined by separated polynomials. Using automorphisms of the underlying curves, we construct permutation automorphisms of the associated algebraic geometry codes and exploit the resulting orbit structure to determine information and check positions.

03592#pg18>. Furthermore, for the subclass of special SAP curves, permutation decoding can be used to correct burst errors in positions indexed by points with a common first coordinate <ref:2608. p. 0
Where the paper says it

For these codes, we obtain permutation decoding sets that correct burst errors supported on coordinates associated with rational points sharing a common coordinate. We further identify a subclass of special SAP curves, including Hermitian curves, generalized Hermitian curves, and certain maximal curves, for which additional automorphisms yield more powerful decoding sets.

p. 0
Where the paper says it

For these codes, we obtain permutation decoding sets that correct burst errors supported on coordinates associated with rational points sharing a common coordinate. We further identify a subclass of special SAP curves, including Hermitian curves, generalized Hermitian curves, and certain maximal curves, for which additional automorphisms yield more powerful decoding sets.

03592#pg18>. The construction of a partial 2-PD set capable of handling errors occurring at any two rational-point positions is demonstrated <ref:2608. p. 5
Where the paper says it

In this sense, we present the following result that will be used in the Theorem 4. 1, where we present a partial ν-PD set that correct errors in a certain one-point AG code.

p. 5
Where the paper says it

In this sense, we present the following result that will be used in the Theorem 4. 1, where we present a partial ν-PD set that correct errors in a certain one-point AG code.

03592#pg18>.

The results presented here extend previous work on permutation decoding of AG codes from Hermitian and norm-trace curves to a broader family of curves defined by separated polynomials <ref:2608.03592#pg18>. The construction of information and check positions for C(D, λP∗) is described by using the orbits of σ to obtain a description of information positions for C(D, λP∗), following the approach introduced in [8] via the root diagram of these codes <ref:2608.03592#pg15>. The gains come from exploiting automorphisms of the underlying curves to construct permutation automorphisms of the associated algebraic geometry codes and using their resulting orbit structure to determine information and check positions The results demonstrate that permutation decoding can be used to correct specific burst-error patterns associated with rational points sharing the same first or second coordinate <ref:2608.03592#pg18>. Furthermore, for the subclass of special SAP curves, permutation decoding can be used to correct burst errors in positions indexed by points with a common first coordinate <ref:2608.03592#pg18>. The construction of a partial 2-PD set capable of handling errors occurring at any two rational-point positions is demonstrated <ref:2608.03592#pg18>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI system can perform permutation decoding for algebraic geometry codes arising from curves defined by separated polynomials using automorphisms of underlying curves to construct partial permutation decoding sets.

  2. The improved system can correct burst errors supported on coordinates associated with rational points sharing a common coordinate, as demonstrated in Theorem 4.1 and Example 4.2.

  3. For special SAP curves, the system can establish additional decoding sets that allow the correction of burst errors in positions indexed by points with a common first coordinate, culminating in the construction of a partial 2-PD set capable of handling errors occurring at any two rational-point positions (Theorem 4.5).

Abstract

In this work, we investigate permutation decoding for algebraic geometry (AG) codes arising from algebraic curves defined by separated polynomials. Using automorphisms of the underlying curves, we construct permutation automorphisms of the associated algebraic geometry codes and exploit the resulting orbit structure to determine information and check positions. We introduce a class of curves, called SAP curves (Separated Additive Polynomial curves), and investigate one-point AG codes defined on them. For these codes, we obtain permutation decoding sets that correct burst errors supported on coordinates associated with rational points sharing a common coordinate. We further identify a subclass of special SAP curves, including Hermitian curves, generalized Hermitian curves, and certain maximal curves, for which additional automorphisms yield more powerful decoding sets.

Sources

Related papers