ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.423733 J. Algebra Comb. Discrete Appl. 5(2) • 71–83 Received: 18 October 2017 Accepted: 9 March 2018 Journal of Algebra Combinatorics Discrete Structures and Applications The root diagram for one-point AG codes arising from certain curves with separated variables Research Article Federico Fornasiero, Guilherme Tizziotti Abstract: Heegard, Little and Saints introduced in [8] an encoding algorithm for a class of AG codes via Gröbner basis more compact compared with the usual encoding via generator matrix. So, knowing that the main drawback of Gröbner basis is the high computational cost required for its calculation, in [12], the same authors introduced the concept of root diagram that allows the construction of an algorithm for computing a Gröbner basis with a lower complexity for one-point Hermitian codes. In [4], Farrán, Munuera, Tizziotti and Torres extended the results obtained in [12] for codes on norm-trace curves. In this work we generalize these results by constructing the root diagram for codes arising from certain curves with separated variables that has certain special automorphism and a Weierstrass semigroup generated by two elements. Such family of curves includes the norm-trace curve, among other curves with recent applications in coding theory. 2010 MSC: 11T71, 13P10 Keywords: AG codes, Gröbner basis, Root diagram 1. Introduction In the early 1980s, V.D. Goppa constructed error-correcting codes using algebraic curves, the called algebraic geometric codes (AG codes), see [6] and [7]. The introduction of methods from algebraic geometry to construct good linear codes was one of the major developments in the theory of error- correcting codes. From that moment many studies and applications on this theory have emerged. In [8], Little, Saints and Heegard noted that any linear code with a nontrivial automorphism has the structure of a module over a polynomial ring and so that the theory of Gröbner bases for modules gives a compact description and implementation of a systematic encoder, which is similar to the usual one for cyclic codes. This encoding method is efficient and also interesting from a theoretical point of view. It is known that Federico Fornasiero; Department of Mathematics, Universidade Federal de Pernambuco, Brazil (email: fed- erico@dmat.ufpe.br). Guilherme Tizziotti (Corresponding Author); Department of Mathematics, Universidade Federal de Uberlândia, Brazil (email: guilhermect@ufu.br). 71 https://orcid.org/0000-0003-1026-0546 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 the main drawback of Gröbner basis is the high computational cost required for its calculation. Indeed, it is well known that the complexity of computing a Gröbner basis is doubly exponential in general. But, in [12], using an appropriate automorphism of the Hermitian curve, Little et al. introduced the concept of root diagram that allows construction of an algorithm for computing a Gröbner basis with a lower complexity for one-point Hermitian codes. In other words, the root diagram is the key to the construction of the algorithm given in [12, Proposition 4.4]. In [4], the results of [12] were extended to codes arising from the norm-trace curve, which is a generalization of the Hermitian curve. In this work, using the same techniques used in [12] and [4], we will construct the root diagram for codes arising from certain curves, which we will denote by X?, with separated variables that has certain special automorphism and a Weierstrass semigroup generated by two elements (see (1), (2) and (3) in Section 3). In addition to Hermitian and norm-trace curves, we have important examples of such curves X? with recent applications in coding theory, namely: the maximal curve with plane model yq + y = xq r+1, see [11]; a quotient of the Hermitian curve with plane model yq + y = xm, see [13]; and curves on Kummer extensions, see [2]. This paper is organized as follows. In Section 2 we recall some background on Gröbner basis for modules, AG codes and root diagram. In Section 3 we present a way to construct the root diagram for one-point AG codes C arising from X?. Finally, in Section 4 we present examples of those curves and the necessary information to construct the root diagram studied in the previous section. 2. Background We will denote a finite field with q elements by Fq. Let X be a projective, non-singular, geometrically irreducible algebraic curve of genus g > 0 over Fq; throughout the paper we will refer to this simply as curve. If ]X(Fq) is the number of Fq-rational points on X , then ]X(Fq) ≤ q + 1 + 2g √ q. This inequality is so-called Hasse-Weil bound and if ]X(Fq) = q + 1 + 2g √ q the curve X is called a maximal curve. Let Fq(X) be the field of rational functions on X . For a Fq-rational point P on X let H(P) := {n ∈ N0 ; ∃f ∈ Fq(X) with div∞(f) = nP}, where N0 is the set of nonnegative integers and div∞(f) denotes the divisor of poles of f. The set H(P) is a numerical semigroup, called Weierstrass semigroup of X at P and its complement G(P) = N0\H(P) is called Weierstrass gap set of P . As an important result, the cardinality of the set G(P) is equal to genus g of X , see Theorem 1.6.8 in [15]. 2.1. Gröbner basis for Fq[t]-modules We will introduce some notations about Gröbner basis for Fq[t]-modules that are needed later. For a complete treatment on this topic see [1] and [3]. A monomial m in the free Fq[t]-module Fq[t]r is an element of the form m = tiej, where i ≥ 0 and e1, . . . ,er is the standard basis of Fq[t]r. Fixed a monomial ordering, for all element f ∈ Fq[t]r, with f 6= 0, we may write f = a1m1 + · · · + a`m`, where, for 1 ≤ i ≤ `, 0 6= ai ∈ Fq and mi is a monomial in Fq[t]r satisfying m1 > m2 > ... > m`. The term a1m1 is called leading term of f and denoted by LT(f), the coefficient a1 and the monomial m1 are called leading coefficient, LC(f), and leading monomial, LM(f), respectively. A Gröbner basis for a submodule M ⊆ Fq[t]r is a set G = {g1, . . . ,gs} such that {LT(g1), . . . ,LT(gs)} generates the submodule LT(M) formed by the leading terms of all elements in M. The monomials in LT(M) are called nonstandard while those in the complement of LT(M) are the standard monomials for M. We recall that every submodule M ⊆ Fq[t]n has a Gröbner basis G, which induces a division algorithm: given f ∈ Fq[t]r there exist a1, . . . ,as,RG ∈ Fq[t]r such that f = a1g1 + . . .+ asgs + RG (see [1, Algorithm 1.5.1] or [3, Theorem 3]). In this work we will use the POT (position over term) ordering over Fq[t]r which is defined as follows. Let {e1, . . . ,er} be the standard basis in Fq[t]r, with e1 > ... > er. The POT ordering on Fq[t]r is defined 72 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 by tiej > t ke` if j < `, or j = ` and i > k. We say that f ∈ Fq[t]r is reduced with respect to a set P = {p1, . . . ,pl} of non-zero elements in Fq[t]r if f = 0 or no monomial in f is divisible by a LM(pi), i = 1, . . . , l. A Gröbner basis G = {g1, . . . ,gs} is reduced if gi is reduced with respect to G −{gi} and LC(gi) = 1 for all i, and non-reduced otherwise. Every submodule of Fq[t]r has a unique reduced Gröbner basis (see [1], Theorem 3.5.22). 2.2. Linking AG codes and Fq[t]-modules Let P1, . . . ,Pn,Q1, . . . ,Q` be n + ` distinct Fq-rational points on X and let m1, . . . ,m` be integers. Consider the divisors D = P1 + · · ·+ Pn and G = m1Q1 + · · ·+ m`Q`. The algebraic geometry code (AG code) CX(D,G) arising from the curve X is defined as CX(D,G) := {(f(P1), . . . ,f(Pn)) ∈ Fnq : f ∈L(G)} , (1) where L(G) is the space of rational functions f on X such that f = 0 or div(f) + G ≥ 0, where div(f) denote the (principal) divisor of the function f ∈ L(G). The number n is the length of CX(D,G), and the dimension of CX(D,G) is its dimension as an Fq-vector space, which is generally denoted by dim(CX(D,λP)) := k. The elements in CX(D,G) are called codewords. If G = m1Q1 the AG code CX(D,m1Q1) is called one-point AG code. For more details about AG codes, see e.g. [10]. Let Supp = {P1, . . . ,Pn} 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 a Fq-linear mapping σ̂ of the code CX(D,G) to Fnq by setting σ̂(f(P1), . . . ,f(Pn)) := (f(σ(P1)), . . . ,f(σ(Pn))). The mapping σ̂ is an automorphism of the code CX(D,G)) if σ̂(CX(D,G)) = CX(D,G). In [7], Goppa already observed that the underlying algebraic curve induces automorphism of the associated AG codes as follows. Proposition 2.1. Let Aut(X) = {σ : X → X ; σ is birational } be the automorphism group of X over Fq and, for divisors D and G, consider the subgroup AutD,G(X) = {σ ∈ Aut(X) : σ(D) = D and σ(G) = G} . Then, each σ ∈ AutD,G(X) induces an automorphism of CX(D,G) by σ̂(f(P1), . . . ,f(Pn)) = (f(σ(P1)), . . . ,f(σ(Pn))) . Assume that X has a nontrivial automorphism σ ∈ AutD,G(X) and let H be the cyclic subgroup of Aut(X) generated by σ. Let Supp(D) = O1 ∪ . . . ∪ Or be the decomposition of the support of D into disjoint orbits under the action of σ. Then, by Proposition 2.1, the entries of the codewords in CX(D,G) will be cyclically permuted in several blocks by σ. We will denote σ0 = Id, where Id is the identity automorphism, and, for a positive integer j, σj = σ ◦σ ◦ . . .◦σ︸ ︷︷ ︸ j . In this way, for each i = 1, . . . ,r, pick any one point Pi,0 ∈ Oi and enumerate the other points on Oi as Pi,j = σj(Pi,0), where j runs from 1 to |Oi|−1. Using this fact, we get the following result. Lemma 2.2. Let CX(D,G) be an AG code arising from X over Fq and let σ ∈ AutD,G(X) be a nontrivial automorphism. If Supp(D) = O1 ∪ . . .∪Or is the decomposition of the support of D into disjoint orbits under the action of σ, then there is a one-to-one correspondence between CX(D,G) and a submodule C of the free module Fq[t]r. 73 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 Proof. Suppose that Supp(D) = O1 ∪ . . .∪Or is the decomposition of the support of D into disjoint orbits under the action of σ. For each i = 1, . . . ,r, let Oi = {Pi,0, . . . ,Pi,|Oi|−1}, where Pi,j = σ j(Pi,0) for each j = 1, . . . , |Oi|−1, and let hi(t) = ∑|Oi|−1 j=0 f(Pi,j)t j. The r-tuples (h1(t), . . . ,hr(t)) can be seen also as an element of the Fq[t]-module A =⊕r i=1 Fq[t]/〈t |Oi| − 1〉. So, the collection C̃ of r-tuples obtained from all f ∈ L(G) is closed under sum and multiplication by t. Define C := π−1(C̃), where π is the natural projection from Fq[t]r onto⊕r i=1 Fq[t]/〈t |Oi|−1〉. Thus, we get a one-to-one correspondence between CX(D,G) and C ≤ Fq[t]r. By the previous lemma, an AG code CX(D,G) can be identified with a submodule C ≤ Fq[t]r and thus the standard theory of Gröbner basis for modules may be applied. Suppose that CX(D,G) has length n and dimension k. A Gröbner basis G = {g(1), . . . ,g(r)} for C ≤ Fq[t]r with exactly r elements allows us to obtain a systematic encoding of C. Since {LT(g(1)), . . . ,LT(g(r))} generates LT(C), it follows that the nonstandard monomials appearing in the r-tuples (h1(t), . . . ,hr(t)) can be obtained from the g(i)’s. By ordering these monomials in decreasing order we obtain the so-called information positions of (h1(t), . . . ,hr(t)), which are the first k mono- mials ml = tilejl, l = 1, . . . ,k. Let V C(h1(t), . . . ,hr(t)) be the vector of coefficients of the terms of (h1(t), . . . ,hr(t)) listed in the POT order. We have the following systematic encoding algorithm: Algorithm 2.3. Input: A Gröbner basis G, monomials {m1, . . . ,mk} and w = (w1, . . . ,wk) ∈ Fkq. Output: c(w) ∈ C = C(X ,D,G). 1. Set f := w1m1 + · · ·+ wkmk. 2. Compute f = a1g(1) + . . . + arg(r) + RG. 3. Return c(w) := V C(f −RG). This method is more compact compared with the usual encoding via generator matrix. The total amount of computation is roughly the same and the amount of necessary stored data is lower in this method, of order r(n−k) against k(n−k) when encoding via generator matrix. More details about this encoding algorithm can be found in [8]. 2.3. The root diagram Consider the one-point AG code C = CX(D,λP) and suppose that X has an automorphism σ fixing the divisors D and G = λP . Suppose also that the order of σ is a factor of q−1. Let C be the submodule of Fq[t]r associated to C by the automorphism σ. Using the POT ordering we can get a Gröbner basis G = {g1, . . . ,gr} for C such that gi = (0, . . . ,0,g (i) i (t),g (i+1) i (t), . . . ,g (r) i (t)), for all i = 1, . . . ,r, see [[8], Proposition II.B.4]. Note that, if deg(g(i)i (t)) = di, then g (i) i (t) has di distinct roots in F ∗ q = Fq \ {0}. In fact, let qi = (t |Oi| − 1)ei. Note that qi ∈ π−1(0, . . . ,0) and we have that qi ∈ C. Since |Oi| divides the order of σ, it follows that t|Oi| − 1 divides tq−1 − 1 = ∏ a∈F∗q (t − a). Now, LT(g(i)) = g(i)i (t) divides LT(qi) = t |Oi| −1, and the claim follows from the fact that tq−1 −1 has q −1 distinct roots in Fq. For i = 1, . . . ,r, let Ri ⊆ F∗q be the set of roots of t|Oi| − 1. By a root diagram DC for the code C, we mean a table with r rows. For each i, the boxes on the i-th row correspond to the elements of Ri. We mark the roots of g(i)i (t) on the i-th row with a X in the corresponding box. By Proposition II.C.1 in [8], there is a Fq-basis for C in one-to-one correspondence with the non- standard monomials in C. That is, terms of the form t`ej appearing as leading terms of some element of C, with ` ≤ |Oj|−1. Now, if there are mj empty boxes on row j of the root diagram, then g (i) j (t) has |Oj|−mj roots and LT(g(j)) = t|Oj|−mj. So, we obtain mj nonstandard monomials t`ej. This fact gives us the following important result. 74 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 Proposition 2.4. ([12], Proposition 2.3) The dimension of the code C is equal to the number of empty boxes in the root diagram DC. 3. The root diagram for certain one-point AG codes Let X? be the curve defined over Fq by affine equation f(y) = g(x) and that has the following conditions: 1. f(T),g(T) ∈ Fq[T ], deg(f) = a and deg(g) = b, with gcd(a,b) = 1; 2. there exists a point P on X? such that div∞(x) = aP , div∞(y) = bP, and H(P) = 〈a,b〉; 3. there exists σ ∈ AutD,G(X?), where G = λP for some positive integer λ, given by σ(x) = αx and σ(y) = αty, for some positive integer t and some α ∈ F∗q. We observe that if the order of α is equal to ord(α) := ν, then, by the definition of σ, it follows that the order of σ is equal to ν which divides q −1. We can ask if curves with such conditions do exist or if there are a large number of them. By [15, Prop. 6.4.1] and [9, Lemma 12.2 and Th. 12.9], we have that the curves defined over a finite field Fqs by the affine equation yq n + y = xm, with gcd(q,m) = 1, are examples of curves that satisfy the above conditions if m(qn−1) divides qs−1. We note that it is hard to study automorphisms of curves in general, especially without giving the equation that defines it. In particular, with the results on automorphisms known to date, we can not present general examples of curves satisfying the above conditions. For a study on automorphism of algebraic curves we refer the reader to [9, Ch. 11 and 12], particularly in the Section 12.1 results on automorphisms of curves given by separated polynomials can be found. Let D = P1 + . . . + Pn, with Pi 6= P for all i = 1, . . . ,n, a divisor on X? and let Supp(D) = O1 ∪ . . .∪Or ∪Or+1 ∪ . . .∪Or+s be the decomposition of the support of D into disjoint orbits under the action of σ. In this section we will describe the root diagram for one-point AG codes CX?(D,λP). Note that, by definition of σ, if Q = (0,η) ∈ Oi, for some η ∈ Fq, then Oi = {(0,η),(0,αtη), . . . ,(0,αt.tiη)}, where ti is the smallest nonnegative integer such that αt.(ti+1) = 1. Analogously, if Q = (ω,0) ∈ Oi, for some ω ∈ Fq, then Oi = {(ω,0),(αω,0), . . . ,(αν−1ω,0)}. Let Or+1, . . . ,Or+s be the orbits that contains Fq-rational points on X? of the form (0,η) or (ω,0). We will work with the first r rows of the root diagram DC for the code CX?(D,λP), the results for the last s rows are similar can be obtained in particular cases. For each i = 1, . . . ,r, suppose that Oi = {Pi,0,Pi,1, . . . ,Pi,|Oi|−1}, where Pi,0 = (xi,yi), with xi 6= 0 and yi 6= 0, and Pi,j = σ j(Pi,0) = (αjxi,α jtyi). So, from the definition of σ it follows that |O1| = . . . = |Or| = ord(α) = ν. Associated with the decomposition of the support of D into disjoint orbits under the action of σ as above, let us assume the following conditions: (I) for each i = 1, . . . ,r, there exists a polynomial Mi(y) such that the orbit Oi is the intersection of Supp(D) with the curve Mi(y) = 0 and, for all i, Mi(y) is a non-zero constant when restricted to each of the orbits Ok, k 6= i; (II) for each 1 ≤ i ≤ r and 0 ≤ j ≤ |Oi| − 1 = ν − 1, there exists a polynomial Bi,j(x,y) such that Bi,j(x,y) vanishes at each point of Oi except Pi,j. In the Proposition 3.3 and the Theorem 3.4 below, the reader will see that the existence of these polynomials is fundamental to obtain the root diagram for one-point AG codes CX?(D,λP). Let κ be the smallest positive integer such that ακt = 1. The next result gives us a way to get Mi(y). Proposition 3.1. Let κ, Oi and Pi,j = σj(Pi,0) = (αjxi,αjtyi) be as above. If (∗) α`tyi 6= α`tyk, for all ` = 0,1, . . . ,κ−1 and k 6= i, 75 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 then Mi(y) = ∏κ−1 `=0 (y −α `tyi) satisfies the condition (I) above. Proof. By the definition of κ, it follows that the orbit Oi is the intersection of Supp(D) with the curve Mi(y) = 0. The condition (∗) implies that Mi(y) is a non-zero constant when restricted to each of the orbits Ok, k 6= i. Note that the condition (∗), which is the key to getting a polynomial Mi(y) as in (I), depends on the decomposition of the support of D and the coordinates of the points on such support. We obtain Bi,j(x,y) in a similar way by using a solution of an interpolation problem. Lemma 3.2. For i = 1, . . . ,r and j = 0, . . . , |Oi|− 1, let Mi(y) and Bi,j(x,y) be as (I) and (II) above. Then, div∞(Mi) = (ρ1b)P and div∞(Bi,j) = (ρ2a + ρ3b)P, where ρ1,ρ2 and ρ3 are nonnegative integers. Proof. We have that div∞(x) = aP and div∞(y) = bP . Then, the result follows from the fact that Mi(y) and Bi,j(x,y) are polynomials. Let ρ1,ρ2 and ρ3 be as the previous lemma. So, for λ ≤ (ρ2a+ρ3b)+r(ρ1b), we can get the following information about the root diagram DC. Proposition 3.3. Let CX?(D,λP) and σ be as above. Let DC be the root diagram for CX?(D,λP). Fix i, 1 ≤ i ≤ r, and let ρ1, ρ2 and ρ3 be as above. 1. If λ ≥ (i− 1)(ρ1b), then the i-th row of DC is not full, in the sense that not every box in the i-th row are marked with X; 2. If λ ≥ (ρ2a + ρ3b) + (i− 1)(ρ1b), then the row is empty, in the sense that none of the boxes in the i-th row is marked with X. Proof. Let C ≤ Fq[t]r be the submodule associated to CX?(D,λP), where D = P1 + . . . + Pn and Pi 6= P for all i = 1, . . . ,n. 1. Suppose that λ ≥ (i−1)(ρ1b). By Lemma 3.2, the function Fi(x,y) = M1(x,y) · · ·Mi−1(x,y) belongs to L(λP) and hence (Fi(P1), . . . ,Fi(Pn)) ∈ CX?(D,λP). By computing (Fi(P1), . . . ,Fi(Pn)), we observe that C contains an element of the form (0, . . . ,0,hi(t), . . . ,hr(t)) with i−1 zeroes and hi(t) = ∑|Oi|−1 j=0 Fi(Pi,j)t j. Since Fi(Pi,j) = M1(Pi,j) · · ·Mi−1(Pi,j) = constant c 6= 0 , we have hi(t) = c. ∑|Oi|−1 j=0 t j and thus h(1) 6= 0 as |Oi| divides q−1. Therefore the i-th row of DC is not full, since g(i)i (t) divides hi(t). 2. Now, suppose λ ≥ (ρ2 +ρ3b)+(i−1)(ρ1b). So, by Lemma 3.2, Gi(x,y) = Bi,0(x,y)Fi(x,y) ∈ L(λP) and Gi(Q) = 0 for Q ∈ O1 ∪O2 ∪ . . .∪Oi−1. Moreover, Gi(Q) = 0 for all Q ∈ Oi \{Pi,0}. Then the element of C corresponding to (Gi(P1), . . . ,Gi(Pn)) verifies h1(t) = h2(t) = . . . = hi−1(t) = 0 and hi(t) = Gi(Pi,0) = c 6= 0. Thus, C contains the element (0, . . . ,0,c,hi+1(t), . . . ,hr(t)). So, the i-th row of DC is empty. Let N be the number of Fq-rational points on X?. By Riemann-Roch Theorem, it follows that if λ < N, then the dimension of the one-point AG code CX?(D,λP) is equal to the dimension of the Riemann-Roch space L(λP). In this case, we complete the information about the root diagram DC. 76 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 Theorem 3.4. Let DC be the root diagram for CX?(D,λP). If there is i ∈{1, . . . ,r} such that (i−1)(ρ1b) ≤ λ < (ρ2a + ρ3b) + (i−1)(ρ1b), then the i-th row of DC is neither full, nor empty, and the complement of the set of roots marked on row i of the diagram is the set Ei = {α−(β+γb) ∈ F∗q | 0 ≤ β ≤ b−1, 0 ≤ γ ≤ ρ1 −1, (i−1)(ρ1b) + βa + γb ≤ λ}. Proof. Let C ≤ Fq[t]r be the submodule associated to CX?(D,λP). Let Di ⊂ F∗q be the set of non- marked boxes in row i, where 1 ≤ i ≤ r. We will show that Di = Ei. Let Fi(y) be as in the previous proposition and consider fi(x,y) = Fi(y)xβyγ. By Lemma 3.2 and the conditions over β and γ given in the definition of Ei, we have that fi(x,y) ∈ L(λP). So, associated to fi(x,y) we get an element h = (h1(t), . . . ,hr(t)) ∈ C. Since Fi(Q) = 0 for all Q ∈ O1 ∪ . . . ∪ Oi−1, it follows that hk(t) = 0, for k = 1, . . . , i − 1. Let Pi,j = σ(Pi,0) = (αjxi,α`jyi) ∈ Oi. Thus, fi(Pi,j) = Fi(Pi,j)αjβx β i α `jγy γ i = Fi(Pi,j)x β i y γ i α j(β+`γ), for all j = 0,1, . . . , |Oi|− 1. Now, Fi(Pi,j), x β i and y γ i are all non-zero constants and independent of j. Taking bi = Fi(Pi,j)x β i y γ i 6= 0, we have hi(t) = |Oi|−1∑ j=0 fi(Pi,j)t j = |Oi| · bi |Oi|−1∑ j=0 (α(β+`γ)t)j whose roots are all distinct from α−(β+`γ). Con- sequently, α−(β+`γ) is not a root of g(i)i (t) and hence Ei ⊆ Di. By Proposition 2.4, dim(CX?(D,λP)) = ∑ ]Di. Since H(P) = 〈a,b〉 and λ < N, we have that dim(CX?(D,λP)) = ]{(β,γ) ∈ N20 ; 0 ≤ β ≤ b−1 and βa + γb ≤ λ}. Let Êi = {(β,γ) ∈ N20 | 0 ≤ β ≤ b − 1,0 ≤ γ ≤ ρ1 − 1, (i − 1)(ρ1b) + βa + γb ≤ λ}. Thus, ]{(β,γ) ∈ N20 ; 0 ≤ β ≤ b − 1 and βa + γb ≤ λ} = ∑ ]Êi and, since ∑ ]Êi = ] ∑ Ei, it follows that∑ ]Di = ∑ ]Ei. Therefore, Ei = Di. Let Fi(y) be as above. Then, we have that Fi(Q) = ci ∈ F∗q, for all Q ∈ Oi. With the conditions of the above theorem, fix an index i, 1 ≤ i ≤ r, where the row i of DC is neither full, nor empty. Let αk1,αk2, . . . ,αk` be the roots marked on the row i and let p(t) = ∏` j=1(t − α kj) be the unique monic polynomial of degree ` with these roots. Note that, including zeroes for powers of t higher than the number of roots, we can write p(t) = ∑|Oi|−1 j=0 ajt j, where aj = 0 for j > `. Consider the function fi(x,y) = Fi(y) ci  |Oi|−1∑ j=0 aj Bi,j(x,y) Bi,j(Pi,j)   Then, by the definition of Fi(y) and Bi,j(x,y), it is clear that fi(x,y) ∈ L(λP) and its associated module element h ∈ C has i−1 leading zero components and i-th component hi(t) equal to p(t). Using this fact and the same procedures used in [12, Section 4, pp. 306] and [4, Section 4, pp. 60], namely • RootDiagram[i]: returns a list of the roots corresponding to the marked boxes in line i of DC; • Boxes[i]: the number of boxes in row i of DC, that is Boxes[i] = |Oi|; • Evaluate[i,point]: a procedure which takes as input the coefficients {ak} of the unique monic polynomial over Fq having the marked elements on a row number i as roots and a point Pi,j on Oi, and evaluates the function fi(x,y) as above at a point Pi,j; we have the following algorithm, which is completely analogous to Proposition 4.4 in [12] and Algorithm 4.2 in [4]. 77 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 Algorithm 3.5. Input: the root diagram DC, the N Fq-rational points Pi,j of Supp(D) = O1∪. . .∪Or∪Or+1∪Or+s. Output: a non-reduced Gröbner basis G = {g(1),g(2), . . . ,g(r+s)} of C. 1. G := {} 2. for i from 1 to r + s do 3. if |RootDiagram[i]|< Boxes[i] then 4. for k from 1 to r + s do 5. g(i)k := 0 6. if k ≥ i then 7. for j from 0 to Boxes[k]−1 do 8. g(i)k := g (i) k + Evaluate[i,Pk,j]t j ek 9. end for 10. end if 11. end for 12. else 13. g(i) := (tBoxes[i] −1) ei 14. end if 15. G := G∪{g(i)} 16. end for 17. return G Remark 3.6. Note that this algorithm makes use only of interpolation and function evaluation problems. As studied in [12] and [4], it has a computational complexity much lower than the complexity of general Gröbner basis algorithms. In particular, it does not use divisions or reductions that would increase the complexity, as in the case of Buchberger’s algorithm. 4. Examples 4.1. The maximal curve yq + y = xq r+1 Let Xq,qr+1 be the curve defined over Fq2r by the affine equation yq + y = xq r+1, where q is a prime power and r an odd integer. Note that when r = 1 the curve is just the Hermitian curve. The curve Xq,qr+1 has genus g = qr(q−1)/2, one single singular point P∞ = (0 : 1 : 0) at infinity and other q2r+1 Fq2r-rational points. Thus, this curve is a maximal curve over Fq,qr+1 because its number of Fq2r-rational points equals the upper Hasse-Weil bound, namely equals q2r + 1 + 2gqr. Furthermore, H(P∞) = 〈q,qr + 1〉, see [14], and σ : x 7→ αx y 7→ αq r+1y (2) with α ∈ F∗ q2r such that α(q r+1)(q−1) = 1, is an automorphism of Xq,qr+1, see [11]. Note that σ has order (qr + 1)(q −1). So, the order of σ divides q2r −1. Note that under the action of the automorphism σ above the q2r+1 Fq2r-rational points on Xq,qr+1 are disposed in q(qr−1 +· · ·+q+1)+2 orbits, where q(qr−1 +· · ·+q+1) of them has length (qr +1)(q−1) and the remaining two orbits, one has length q−1 and the other has length 1. In fact, for the definition of the automorphism σ, it is clear that: • σ(0,0) = (0,0), and so we have a one orbit with a single point; 78 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 • all the q −1 Fq2r-rational points (0,b), with b 6= 0, form an orbit with length q −1, since σ(0,b) = (0,αq r+1b) and α ∈ F∗ q2r is such that α(q r+1)(q−1) = 1; • the other q2r+1 −q = q(qr + 1)(qr −1) Fq2r-rational points (x,y) ∈Xq,qr+1, with x 6= 0 and y 6= 0, are arranged in q(qr−1 + · · ·+ q + 1) orbits of length (qr + 1)(q −1). Let α be as in (2). Let F∗ q2r = 〈a〉 and t ∈ {0,1, . . . ,q2r − 2} be such that α = at. So, given Pi,0 = (a ti,ali) ∈ Oi, the other points Pi,j on Oi are Pi,j = σj(Pi,0) = (ati+jk,ali+jk(q r+1)), with j ∈{1, . . . ,(qr + 1)(q −1)−1}. Then, for i = 1, . . . ,r and j = 0, . . . ,(qr + 1)(q −1)−1, we get Mi(y) := q−2∏ j=0 (y −ali+jk(q r+1)) = yq−1 −ali(q−1), (3) and Bi,j(x,y); = q−2∏ s=1 (y −ali+k(q r+1)(j+s)) (qr+1)−1∏ s=1 (x−ati+k(j+s)). (4) Since div∞(x) = qP∞ and div∞(y) = (qr + 1)P∞, we have that • div∞(Mi(y)) = (q −1)(qr + 1)P∞; that is, Mi(y) ∈ L((q −1)(qr + 1)P∞), for all i = 1, . . . ,r; • div∞(Bi,j(x,y)) = ((q−2)(qr +1)+q((qr +1)−1))P∞; that is, Bi,j ∈ L(q.qr +(q−2)(qr +1))P∞), for all 1 ≤ i ≤ r) e 0 ≤ j ≤ (qr + 1)(q −1)−1. With the notations on the previous section we have that: • a = q and b = qr + 1; • P = P∞; • div∞(x) = qP∞ and div∞(y) = (qr + 1)P∞; • H(P∞) = 〈q,qr + 1〉; • ρ1 = q −1, ρ2 = qr and ρ3 = q −2. Thus, using the Proposition 3.3 and the Theorem 3.4, we can get the root diagram for one-point codes CXq,qr+1(D,λP∞) and then the Gröbner basis for the module C associated to CXq,qr+1(D,λP∞) by Algorithm 3.5. Example 4.1. Consider the curve X2,9 : y2 +y = x9 over F64 and the code C = C(X2,9,D,20P∞), where D is the sum of the 128 F64-rational points distinct of P∞ = (0 : 1 : 0). Let α be a generator of F∗64. The automorphism σ(x,y) = (α7x,y) decomposes the points in Supp(D) into sixteen orbits, being fourteen of 79 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 length 9 and two of length 1: O1 = {P1,0 = (α,α18),P1,1 = (α8,α18), . . . ,P1,8 = (α57,α18)}, O2 = {P2,0 = (α,α54),P2,1 = (α8,α54), . . . ,P2,8 = (α57,α54)}, O3 = {P3,0 = (α2,α36),P3,1 = (α9,α36), . . . ,P3,8 = (α58,α36)}, O4 = {P4,0 = (α2,α45),P4,1 = (α9,α45), . . . ,P4,8 = (α58,α45)}, O5 = {P5,0 = (α3,α31),P5,1 = (α10,α31), . . . ,P5,8 = (α59,α31)}, O6 = {P6,0 = (α3,α59),P6,1 = (α10,α59), . . . ,P6,8 = (α59,α59)}, O7 = {P7,0 = (α4,α9),P7,1 = (α11,α9), . . . ,P7,8 = (α60,α9)}, O8 = {P8,0 = (α4,α27),P8,1 = (α11,α27), . . . ,P8,8 = (α60,α27)}, O9 = {P9,0 = (α5,α47),P9,1 = (α12,α47), . . . ,P9,8 = (α61,α47)}, O10 = {P10,0 = (α5,α61),P10,1 = (α12,α61), . . . ,P10,8 = (α61,α61)}, O11 = {P11,0 = (α6,α55),P11,1 = (α13,α55), . . . ,P11,8 = (α62,α55)}, O12 = {P12,0 = (α6,α62),P12,1 = (α13,α62), . . . ,P12,8 = (α62,α62)}, O13 = {P13,0 = (α7,α21),P13,1 = (α14,α21), . . . ,P13,8 = (1,α21)}, O14 = {P14,0 = (α7,α42),P14,1 = (α14,α42), . . . ,P14,8 = (1,α42)}, O15 = {P15,0 = (0,1)}, O16 = {P16,0 = (0,0)}. Since the set of roots of t9 − 1 in F64 is {1,α7,α14,α21,α28,α35,α42,α49,α56}, Proposition 3.3 and Theorem 3.4 (where a = 2, b = 9, ρ1 = 1, ρ2 = 8, ρ3 = 0 and λ = 20) give the following root diagram. α7 α14 α21 α28 α35 α42 α49 α56 1 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 4.2. A quotient of the Hermitian curve Let Xq,m be the curve defined over Fq2 by the affine equation yq + y = xm, where q is a prime power and m > 2 is a divisor of q + 1. This curve is a quotient of the Hermitian curve and has genus g = (q−1)(m−1)/2, a single point at infinity, denoted by P∞, and other q(1 + m(q−1)) Fq2-rational points. One may notice that P∞ = (0 : 1 : 0) if m = q + 1, and P∞ = (1 : 0 : 0) if m 6= q + 1. In [5], it is shown that Xq,m is a maximal curve and in [13], G. Matthews studied Weierstrass semigroup and algebraic codes arising from Xq,m. In addition, we have that H(P∞) = 〈m,q〉, see [5, Theorem 3]. Let F∗ q2 = 〈α〉 and k such that mk = q + 1. Then, 80 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 τ : x → αkx y → αq+1y (5) is an automorphism of Xq,m of order m(q −1), which divides q2 −1. It is not hard to see that under the action of the automorphism τ above the q(1 + m(q − 1)) Fq2- rational points on Xq,m are disposed in q+2 orbits, where q of them has length m(q−1) and the remaining two orbits, one has length q −1 and the other has length 1. Taking r = q and the first r orbits given by points on Xq,m of the form P = (a,b) with a,b 6= 0. So, for each i = 1, . . . ,r, given Pi,0 = (α`i,αti) ∈ Oi, the other points Pi,j on Oi are Pi,j = σj(Pi,0) = (α`i+jk,αti+j(q+1)), with j ∈{1, . . . ,m(q −1)−1}. That is, Oi = {Pi,j = (α`i+jk,αti+j(q+1)) ; j = 0, . . . ,m(q −1)−1}. Then, for i = 1, . . . ,r and j = 0,1, . . . ,m(q −1)−1, we get Mi(y) = q−2∏ j=0 (y −αti+j(q+1)) and Bi,j(x,y) = q−2∏ s=0,s6=j (y −αti+s(q+1)) m(q−1)−1∏ s=0,s6=j (x−α`i+sk). So, since div∞(x) = qP∞ and div∞(y) = mP∞, it follows that • div∞(Mi(y)) = (q −1)mP∞; that is, Mi(y) ∈ L((q −1)mP∞), for all i = 1, . . . ,r; • div∞(Bi,j(x,y)) = ((q − 2)m + (m − 1)q)P∞; that is, Bi,j ∈ L((m − 1)q + (q − 2)m)P∞), for all 1 ≤ i ≤ r) and 0 ≤ j ≤ m(q −1)−1. With the notations on the previous section we have that: • a = q and b = m; • P = P∞; • (x)∞ = qP∞ and (y)∞ = mP∞; • H(P∞) = 〈q,m〉; • ρ1 = q −1, ρ2 = q −2 and ρ3 = m−1. Therefore, we can get the root diagram for one-point codes CXq,m(D,λP∞) and then the Gröbner basis for the module C associated to CXq,m(D,λP∞). Example 4.2. Consider the curve X? : y5 +y = x3 over F25 and the code C = CX?(D,30P∞), where D is the sum of the 65 F25-rational points distinct of P∞. Let α be a generator of F∗25. The automorphism τ(x,y) = (α2x,α6y) decomposes the points in Supp(D) into seven orbits, being five of length 12, one of 81 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 length 4 and one of length 1: O1 = {P1,0 = (1,α),P1,1 = (α2,α7), . . . ,P1,11 = (α22,α19)}, O2 = {P2,0 = (1,α20),P2,1 = (α2,α2), . . . ,P2,11 = (α22,α14)}, O3 = {P3,0 = (1,α4),P3,1 = (α2,α10), . . . ,P3,11 = (α22,α22)}, O4 = {P4,0 = (1,α5),P4,1 = (α2,α11), . . . ,P4,11 = (α22,α23)}, O5 = {P5,0 = (1,α18),P5,1 = (α2,1), . . . ,P5,11 = (α22,α12)}, O6 = {P6,0 = (0,α3),P6,1 = (0,α9),P6,2 = (0,α15),P6,3 = (0,α21)}, O7 = {P7,0 = (0,0)}. Since the set of roots of t12 −1 and t4 −1 in F25 are {1,α2,α4,α6, . . . ,α22} and {1,α6,α12,α18}, respec- tively. So, Proposition 3.3 and Theorem 3.4 (where a = 5, b = 3, ρ1 = 4, ρ2 = 3, ρ3 = 2 and λ = 30) give the following root diagram. α2 α4 α6 α8 α10 α12 α14 α16 α18 α20 α22 1 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X Acknowledgment: The authors would like to thank the anonymous referees for very useful com- ments and suggestions that improved the presentation of this work. References [1] W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, Providence, RI: American Mathe- matical Society, 1994. [2] A. S. Castellanos, A. M. Masuda, L. Quoos, One– and two–point codes over Kummer extensions, IEEE Trans. Inform. Theory 62(9) (2016) 4867–4872. [3] D. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, Springer, New York, 1998. [4] J. I. Farrán, C. Munuera, G. Tizziotti, F. Torres, Gröbner basis for norm–trace codes, J. Symb. Comput. 48 (2013) 54–63. [5] A. Garcia, P. Viana, Weierstrass points on certain non–classical curves, Arch. Math. 46(4) (1986) 315–322. [6] V. D. Goppa, Codes on algebraic curves, Dokl. Akad. Nauk SSSR 259(6) (1981) 1289–1290. [7] V. D. Goppa, Algebraic–geometric codes, Izv. Akad. Nauk SSSR Ser. Mat. 46(4) (1982) 762–781. [8] C. Heegard, J. Little, K. Saints, Systematic encoding via Gröbner bases for a class of algebraic– geometric Goppa codes, IEEE Trans. Inform. Theory 41(6) (1995) 1752–1761. [9] J. W. P. Hirschfeld, G. Korchmáros, F. Torres, Algebraic Curves over a Finite Field, Princeton University Press, Princeton, 2008. [10] T. Høholdt, J. van Lint, R. Pellikaan, Algebraic geometry codes, in Handbook of Coding Theory, V. S. Pless, W. C. Huffman, R. A. Brualdi (Eds.), v. 1, Elsevier, Amsterdam, 1998, 871–961. [11] S. Kondo, T. Katagiri, T. Ogihara, Automorphism groups of one–point codes from the curves yq+y = xq r+1, IEEE Trans. Inform. Theory 47(6) (2001) 2573–2579. [12] J. Little, K. Saints, C. Heegard, On the structure of Hermitian codes, J. Pure Appl. Algebra, 121(3) (1997) 293–314. [13] G. L. Matthews, Weierstrass semigroups and codes from a quotient of the Hermitian curve, Des. Codes Cryptogr. 37(3) (2005) 473–492. 82 https://doi.org/10.1109/TIT.2016.2583437 https://doi.org/10.1109/TIT.2016.2583437 https://doi.org/10.1016/j.jsc.2012.05.001 https://doi.org/10.1016/j.jsc.2012.05.001 https://doi.org/10.1007/BF01200462 https://doi.org/10.1007/BF01200462 https://mathscinet.ams.org/mathscinet-getitem?mr=628795 https://mathscinet.ams.org/mathscinet-getitem?mr=670165 https://doi.org/10.1109/18.476247 https://doi.org/10.1109/18.476247 https://mathscinet.ams.org/mathscinet-getitem?mr=2386879 https://mathscinet.ams.org/mathscinet-getitem?mr=2386879 https://doi.org/10.1109/18.945272 https://doi.org/10.1109/18.945272 https://doi.org/10.1016/S0022-4049(96)00067-9 https://doi.org/10.1016/S0022-4049(96)00067-9 https://doi.org/10.1007/s10623-004-4038-5 https://doi.org/10.1007/s10623-004-4038-5 F. Fornasiero, G. Tizziotti / J. Algebra Comb. Discrete Appl. 5(2) (2018) 71–83 [14] A. Sepúlveda, G. Tizziotti, Weierstrass semigroup and codes over the curve yq + y = xq r+1, Adv. Math. Commun. 8(1) (2014) 67–72. [15] H. Stichtenoth, Algebraic Function Fields and Codes, Springer–Verlag, Berlin, 1993. 83 https://dx.doi.org/10.3934/amc.2014.8.67 https://dx.doi.org/10.3934/amc.2014.8.67 https://mathscinet.ams.org/mathscinet-getitem?mr=2464941 Introduction Background The root diagram for certain one-point AG codes Examples References