Permutation Decoding of AG Codes from Curves Defined by Separated Polynomials
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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} 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), . Mathematics Subject Classification (2020): 94B05, 11T71, 14G50. 1
arXiv:2608. The set Supp(D) = {P1, . , Pn} decomposes under the action of σ into r distinct orbits,
O1, . Mathematics Subject Classification (2020): 94B05, 11T71, 14G50. 1
arXiv:2608. 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. 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].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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).Where the paper says it
Where the paper says it
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 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. 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. 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). 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].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound
- Second-Order Image Characterization with Distortion and Secrecy