The weight hierarchy of decreasing norm-trace codes
- Open Access
- 01.04.2025
Erschienen in:
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by (Link öffnet in neuem Fenster)
Abstract
1 Introduction
Generalized Hamming weights for linear codes were introduced by Wei in 1991 [47] as a tool in characterizing code performance on the wire-tap channel of type II. Wei noted an application to t-resilient functions; established properties of the weight hierarchy, meaning the collection of generalized Hamming weights; and determined the generalized Hamming weights for first-order Reed-Muller codes, Hamming codes, extended Hamming codes, duals of Hamming codes, Reed-Solomon codes, and any maximum distance separable (MDS) code. Other related independent developments were Helleseth, Kløve, and Mykkeltveit [27, 28]. A flurry of activity followed. For instance, Feng, Tzeng, and Wei [16] obtained bounds on the generalized Hamming weights of several families of BCH codes and cyclic codes; see also [30]. The generalized Hamming weights of convolutional codes were considered by Rosenthal and York in [41], and more recently with an alternative definition by Gorla and Salizzoni [23].
In [48], Yang, Kumar, and Stichtenoth initiated the study of generalized Hamming weights of algebraic geometry codes in 1994. In 1998, Heijnen and Pellikaan gave in [26] an order bound on the generalized Hamming weights similar to the Feng-Rao bound on the minimum distance of a code. This order bound allowed Heijnen and Pellikaan to find the weight hierarchy for higher-order Reed-Muller codes and to provide insight into the family of one-point algebraic geometry codes. Later, Barbero and Munuera determined the weight hierarchy for one-point Hermitian codes in [2]. Additional work on generalized Hamming weights of algebraic geometry includes [8, 15].
Anzeige
Additional applications of generalized Hamming weights include improved bounds on the list size in list decoding algorithms for tensor products and interleaved codes [22]. There has also been recent work on the generalized Hamming weights of many other well-known families of codes, such as affine Cartesian codes [4], hyperbolic codes [11], projective Reed-Muller codes [5, 43], and matrix-product codes [42], to mention some.
In this paper, we determine the generalized Hamming weights of extended norm-trace codes. While the weight distribution of norm-trace codes has been previously studied [3, 6], we note that, in general, there is no relation between the weight distribution and the weight hierarchy of a linear code. The weight hierarchies of the norm-trace and Hermitian codes are special cases of our results, allowing us to recover the results of Barbero and Munuera [2]. The codes we consider are defined on the extended norm-trace curve, denoted by \({\mathcal {X}}_u\), which is the affine curve defined over the finite field \({\mathbb {F}}_{q^s}\) with cardinality \(q^s\) by the equationwhere u is a positive integer such that \(u \mid \frac{q^s - 1}{q - 1}\). Norm-trace codes are defined using the norm-trace curve which is the special case when \(u= \frac{q^s - 1}{q - 1}\), meaning the affine curve over \({\mathbb {F}}_{q^s}\) defined bywhere \({{\,\textrm{N}\,}}(x)\) is the norm and \({{\,\textrm{Tr}\,}}(y)\) is the trace, both taken with respect to the extension \({\mathbb {F}}_{q^s}/{\mathbb {F}}_q\). Taking in addition \(s=2\) and \(u= \frac{q^s - 1}{q - 1}\) (resp., \(u \mid \frac{q^s - 1}{q - 1}\)) gives the special case of the Hermitian curve defined by \(x^{q+1}=y^q+y\) (resp., its quotient \(x^{u}=y^q+y\)) over \({\mathbb {F}}_{q^2}\).
$$\begin{aligned} x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y, \end{aligned}$$
$$\begin{aligned} {{\,\textrm{N}\,}}(x)={{\,\textrm{Tr}\,}}(y) \end{aligned}$$
We focus in this work on decreasing norm-trace codes, which are codes defined by evaluating monomials on the rational points of the curve \({\mathcal {X}}_u\). To define the codes, enumerate the rational points on \({\mathcal {X}}_u\) so that \({\mathcal {X}}_u = \left\{ P_1,\ldots ,P_n \right\} \subseteq \mathbb {F}_{q^s}^2\) and \(n=u(q-1)q^{s-1}+q^{s-1}\). The evaluation map, denoted \(\textrm{ev}\), is the \(\mathbb {F}_{q^s}\)-linear map given byLet \(\mathcal {M} \subseteq \mathbb {F}_{q^s}[x,y]\) be a set of monomials closed under divisibility, meaning that if \(M\in \mathcal {M}\) and \(M^\prime \) divides M, then \(M^\prime \in \mathcal {M}\). Let \(\mathcal {L}(\mathcal {M})\) be the \(\mathbb {F}_{q^s}\)-subspace of \(\mathbb {F}_{q^s}[x,y]\) generated by the set \(\mathcal {M}\). We call the image of \(\mathcal {L}(\mathcal {M})\) under the evaluation map, denoted by \(\textrm{ev}(\mathcal {M})\), a decreasing norm-trace code. We can see that the extended norm-trace codes introduced and recently studied in [7] and [31] are particular instances of decreasing norm-trace codes; norm-trace codes and generalizations also appear in [9]. Moreover, we check later that the family of decreasing norm-trace codes contains, as a specific case, the family of one-point algebraic geometry codes over the norm-trace curve (in particular, it contains the family of one-point algebraic geometry codes over the Hermitian curve).
$$\begin{aligned} \begin{array}{lccc} \textrm{ev}:& \mathbb {F}_{q^s}[x,y] & \rightarrow & \mathbb {F}_{q^s}^{n}\quad \\ & f & \mapsto & \left( f(P_1),\ldots ,f(P_n)\right) . \end{array} \end{aligned}$$
We organize this paper as follows. The necessary background is contained in Sect. 2. In Sect. 3, we determine the weight hierarchy of decreasing norm-trace codes. In Sect. 4, we find the generalized Hamming weights for a class of Reed-Muller-type codes defined over the norm-trace curve. In Sect. 5, we show how to adapt our techniques to study the relative generalized Hamming weights of decreasing norm-trace codes. As an application, we consider one-point algebraic geometry codes on the extended norm-trace curve, a particular case of decreasing norm-trace codes, and we use them to construct impure quantum codes.
Anzeige
2 Preliminaries
We use the standard notation from finite fields and coding theory. Let \(\mathbb {F}_q\) be the finite field with q elements. The set of polynomials in variables \(x_1, \dots x_m\) with coefficients in \({\mathbb {F}}_q\) is denoted by \({\mathbb {F}}_q[x_1, \dots , x_m]\). The affine plane over \({\mathbb {F}}_q\) is denoted by \(\mathbb A^2({\mathbb {F}}_q)\).
Let C be an [n, k, d] code C over \({\mathbb {F}}_q\), meaning a k-dimensional \(\mathbb {F}_q\)-subspace of \({\mathbb {F}}_q^n\) with minimum distance \(d:=\left\{ {{\,\textrm{wt}\,}}(c): c \in C \setminus \{ 0\} \right\} \) where the weight of \(w \in {\mathbb {F}}_q^n\) is \({{\,\textrm{wt}\,}}(w):=\left|\left\{ i \in [n]: w_i \ne 0 \right\} \right|\) and \([n]:=\left\{ 1, \dots , n \right\} \). The support of the code C is
$$\begin{aligned} {{\,\textrm{supp}\,}}(C):=\left\{ i \in [n]: \exists c \in C \text { with } c_i \ne 0 \right\} . \end{aligned}$$
Definition 2.1
The \(r^{th}\)-generalized Hamming weight of an [n, k, d] code C iswhere \(r \in [k]\). The weight hierarchy of C is the set
$$\begin{aligned} d_r(C):=\min \left\{ \left| {{\,\textrm{supp}\,}}(C') \right|: C' \text { is a subcode of } C \text { of dimension } r \right\} , \end{aligned}$$
$$\begin{aligned} \left\{ d_r(C): r \in [k] \right\} . \end{aligned}$$
Notice that \(d_1(C)\) is the minimum distance of C. We may write \(d_r\) to mean \(d_r(C)\) if the code C is evident from the context. Wei obtained the following general properties of the generalized Hamming weights in [47].
Theorem 2.2
Monotonicity For an [n, k] linear code C with \(k>0\), we have
$$\begin{aligned} 1\le d_1(C)<d_2(C)<\cdots <d_k(C)\le n. \end{aligned}$$
Corollary 2.3
Generalized Singleton Bound For an [n, k] linear code C, we have
$$\begin{aligned} d_r(C)\le n-k+r, \; 1\le r\le k. \end{aligned}$$
Theorem 2.4
Duality Let C be an [n, k] code. Then
$$\begin{aligned} \{d_r(C):1\le r\le k\}=\{1,2,\dots ,n\}\setminus \{n+1-d_r(C^\perp ):1\le r\le n-k\}. \end{aligned}$$
We will now introduce some basic tools from commutative algebra and Gröbner basis that we will use throughout the article. We refer to [14, 46] for the details we may not cover in what follows.
Let \(\mathcal {M}\) be a set of monomials of \({\mathbb {F}}_{q^s}[x_1, \ldots , x_m]\) with a monomial order \(\prec \), meaning a total order in which the least monomial is 1 and \(M_1 \prec M_2\) implies \(M M_1 \prec M M_2\) for all \(M, M_1, M_2 \in \mathcal {M}\). For \(f \in {\mathbb {F}}_{q^s}[x_1,\ldots , x_m] \setminus \{ 0 \}\), the initial (or leading) monomial of f is the greatest monomial with respect to \(\prec \) which appears in the expansion of f, denoted by \({{\,\textrm{in}\,}}(f)\). Given an ideal \(I \subseteq {\mathbb {F}}_{q^s}[x_1, \ldots , x_m]\), its initial ideal is \({{\,\textrm{in}\,}}(I):= ({{\,\textrm{in}\,}}(f): f \in I )\). A Gröbner basis for I is a finite set \(\mathcal G \subseteq I\) such that for every polynomial \(f \in I {\setminus } \{0\}\), \({{\,\textrm{in}\,}}(f)\) is a multiple of \({{\,\textrm{in}\,}}(g)\) for some \(g \in \mathcal G\). In this case, \(\mathcal {G}\) generates I. Given a Gröbner basis \(\mathcal G\) for I, the footprint of I is the setwhere \(\mathbb {M} \subset \mathbb {F}_{q^s}[x_1,\dots ,x_m]\) is the set of all monomials. Let \(A\subset \mathbb {F}_{q^s}[x_1,\dots ,x_m]\). We may abuse the notation and define \(\Delta (A)\) as the footprint of the ideal generated by A. For an ideal \(I\subset {\mathbb {F}}_{q^s}[x_1,\ldots , x_m]\), the set \(\Delta (I)\) forms a basis for \({\mathbb {F}}_{q^s}[x_1,\ldots , x_m]/I\) as an \(\mathbb {F}_{q^s}\)-vector space. Therefore, if we consider a set of (classes of) polynomials in \({\mathbb {F}}_{q^s}[x_1,\ldots , x_m]/I\), we may assume that they only have monomials from \(\Delta (I)\) in their expansion, and if they differ in at least one monomial (for example, the initial monomial), then they are linearly independent in \({\mathbb {F}}_{q^s}[x_1,\ldots , x_m]/I\).
$$\begin{aligned} \Delta (I):=\left\{ M \in \mathbb {M}: M \not \in {{\,\textrm{in}\,}}(I) \right\} =\left\{ M \in \mathbb {M}: {{\,\textrm{in}\,}}(g) \not \mid M \ \ \forall g \in \mathcal G \right\} , \end{aligned}$$
The S-polynomial of \(g,g' \in \mathcal G\), with leading coefficients \(c,c'\), respectively, is the polynomialwhere \(f, f' \in {\mathbb {F}}_{q^s}[x_1, \ldots , x_m]\) are the monomials of least degree such that \( f' {{\,\textrm{in}\,}}(g)=f {{\,\textrm{in}\,}}(g')\). For an ideal I whose associated variety V(I) is finite, the footprint bound states that the variety has cardinality bounded by the footprint of the ideal, that isMoreover, equality holds when I is a radical ideal (for the details, see [14, Thm. 6 and Prop. 7, Chapter 5 §3]).
$$\begin{aligned} S(g,g')=c'f'g-cfg' \in I, \end{aligned}$$
$$\begin{aligned} \left|V(I)\right| \le \left|\Delta (I)\right|. \end{aligned}$$
We now review the necessary prerequisites on the curves of interest. Let \(s \ge 2\) be an integer. Define the polynomials \({{\,\textrm{N}\,}}(x):=x^{\frac{q^s-1}{q-1}}\) and \({{\,\textrm{Tr}\,}}(y):=y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y^q + y\) in \(\mathbb {F}_{q^s}[x,y]\). The trace with respect to the extension \({\mathbb {F}}_{q^s}/{\mathbb {F}}_q\) is the mapThe norm with respect to the extension \({\mathbb {F}}_{q^s}/{\mathbb {F}}_q\) is the mapThe norm-trace curve, denoted by \(\mathcal {X}\), is the affine plane curve over \(\mathbb {F}_{q^s}\) given by the equationThe curve \(\mathcal {X}\) has been extensively studied in the literature to construct linear codes [7, 18, 33, 39, 40]. We are interested in a slightly more general curve. Let u be a positive integer such that \(u \mid \frac{q^s - 1}{q - 1}\). The extended norm-trace curve, denoted by \({\mathcal {X}}_u\), is the affine curve over \({\mathbb {F}}_{q^s}\) defined by the equationThe curve \(\mathcal X_u\) has genus \(g=\frac{(u-1)(q^s-1)}{2}\) [39, Theorem 13]. In [12], the authors use the rational points of the curve \({\mathcal {X}}_u\) to construct a family of decreasing evaluation codes, which contains, as a particular case, the extended norm-trace codes [7, 31]. In particular, in [12], the authors obtain the following result about the structure of the rational points of \(\mathcal X_u\).
$$\begin{aligned} \begin{array}{lccc} {{\,\textrm{Tr}\,}}: & {\mathbb {F}}_{q^s} & \rightarrow & {\mathbb {F}}_q \\ & \alpha & \mapsto & {{\,\textrm{Tr}\,}}(\alpha )=\alpha +\alpha ^q+\cdots +\alpha ^{q^{s-1}}. \end{array} \end{aligned}$$
$$\begin{aligned} \begin{array}{lccc} {{\,\textrm{N}\,}}: & {\mathbb {F}}_{q^s} & \rightarrow & {\mathbb {F}}_q \\ & \alpha & \mapsto & {{\,\textrm{N}\,}}(\alpha )=\alpha \cdot \alpha ^q \cdots \alpha ^{q^{s-1}}=\alpha ^{\frac{q^s-1}{q-1}}. \end{array} \end{aligned}$$
$$\begin{aligned} x^{\frac{q^s - 1}{q - 1}} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y. \end{aligned}$$
$$\begin{aligned} x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y. \end{aligned}$$
Lemma 2.5
For every \(\gamma \in \mathbb {F}_q\), define \(A_\gamma :=\{(\alpha ,\beta )\in \mathbb {A}^2(\mathbb {F}_{q^s}): {{\,\textrm{Tr}\,}}(\beta )=\alpha ^u=\gamma \}\). Then, we have \(\mathcal {X}_u=\bigcup _{\gamma \in \mathbb {F}_q}A_\gamma \). Moreover, \(\left|A_0\right|=q^{s-1}\) and \(\left|A_\gamma \right|=uq^{s-1}\) for all \(\gamma \in \mathbb {F}_q^*\).
Remark 2.6
For each \(\gamma \in \mathbb {F}_q\), we have thatFix \(\gamma \in \mathbb {F}_q\). For each \(\alpha \) with \(\alpha ^u=\gamma \), there are exactly \(q^{s-1}\) points in \(\mathcal {X}_u\) such that its first coordinate is \(\alpha \). For each \(\beta \) such that \({{\,\textrm{Tr}\,}}(\beta )=\gamma \), there are exactly u points in \(\mathcal {X}_u\) such that its second coordinate is \(\beta \) if \(\gamma \ne 0\), and one point if \(\gamma =0\).
$$\begin{aligned} A_\gamma =\{\alpha \in \mathbb {F}_{q^s}: \alpha ^u=\gamma \} \times \{\beta \in \mathbb {F}_{q^s}: {{\,\textrm{Tr}\,}}(\beta )=\gamma \}. \end{aligned}$$
The vanishing ideal of a set of points is defined by the set of all polynomials that vanish on every point. Consider the vanishing ideal \(I_{\mathcal {X}_u}:=I(\mathcal {X}_u)=({{\,\textrm{Tr}\,}}(y)-x^u,x^{q^s}-x,y^{q^s}-y)\) associated with the extended norm-trace curve. From [12, Prop. 2.2], we haveWe define the weight \(w(x^ay^b)\) of the monomial \(x^ay^b\) asThe weight of a polynomial is the maximum weight of the monomials that appears in the support of the polynomial. We consider the weighted degree lexicographic ordering given by the following:For this weighted degree lexicographic order, in [12], the authors prove that the generators from Equation (1) form a Gröbner basis, and thereforeGiven \(f\in \mathbb {F}_{q^s}[x,y]\), we denoteWe have thatThe second equality is always true. The first one follows from [34, Prop 6.2.12]. Assume \({{\,\textrm{in}\,}}(f)=x^ay^b\), with \(0\le a\le u(q-1)\) and \(0\le b\le q^{s-1}-1\). Following the proof of [19, Prop. 4], let \(f=x^ay^b+f'\) and \(g={{\,\textrm{Tr}\,}}(y)-x^u=y^{q^{s-1}}-x^u+g'\), with \(w(f')<aq^{s-1}+bu\) and \(w(g')<uq^{s-1}\). Then we can compute the following S-polynomial:We have \({{\,\textrm{in}\,}}(S(g,f))=x^{a+u}\) because \(w(x^ag')<a+uq^{s-1}\) and \(w(y^{q^{s-1}-b}f')<(a+u)q^{s-1}\), whereas \(w(x^{a+u})=(a+u)q^{s-1}\). Therefore, we have \(({{\,\textrm{in}\,}}({I_{\mathcal {X}_u}}),x^ay^b,x^{a+u}) \subset {{\,\textrm{in}\,}}({I_{\mathcal {X}_u}},f)\), which impliesUsing Equation (2), we can conclude thatLet \(F=\{f_1,\dots ,f_r\}\) be a set of linearly independent polynomials in \(\mathbb {F}_{q^s}[x,y]/{I_{\mathcal {X}_u}}\). Let \({{\,\textrm{in}\,}}(f_i)=x^{a_i}y^{b_i}\), for \(1\le i \le r\), with \(a_1\le \cdots \le a_r\). We can assume that \((a_i,b_i)\ne (a_j,b_j)\) for \(i\ne j\). We defineArguing as above, we can get the boundwhere \({V_{\mathcal {X}_u}}(F)\) is the set of common zeroes of F in \(\mathcal {X}_u\). Since this will be the main object of study, we denoteAs the number of common zeroes of F is related to the support of the subcode D generated by the evaluation of the polynomials in F, Inequality (3) gives the following bound for the support of this subcode:
$$\begin{aligned} I_{\mathcal {X}_u}=({{\,\textrm{Tr}\,}}(y)-x^u,x^{u(q-1)+1}-x). \end{aligned}$$
(1)
$$\begin{aligned} w(x^ay^b)=aq^{s-1}+ub. \end{aligned}$$
$$\begin{aligned} x^ay^b< x^{a'}y^{b'} \iff w(x^ay^b)<w(x^{a'}y^{b'}), \text { or } w(x^ay^b)=w(x^{a'}y^{b'}) \text { and } b<b'. \end{aligned}$$
$$\begin{aligned} {{\,\textrm{in}\,}}(I_{\mathcal {X}_u})=(y^{q^{s-1}},x^{u(q-1)+1}). \end{aligned}$$
(2)
$$\begin{aligned} {V_{\mathcal {X}_{u}}}(f):=\{ P\in \mathcal {X}_u\mid f(P)=0\}. \end{aligned}$$
$$\begin{aligned} \left|{V_{\mathcal {X}_{u}}}\right|=\left|\Delta ({I_{\mathcal {X}_{u}}},f)\right|=\left|\Delta ({{\,\textrm{in}\,}}({I_{\mathcal {X}_{u}}},f))\right|. \end{aligned}$$
$$\begin{aligned} S(g,f)=x^ag-y^{q^{s-1}-b}f=-x^{a+u}+x^ag'-y^{q^{s-1}-b}f'. \end{aligned}$$
$$\begin{aligned} \left|{V_{\mathcal {X}_u(f)}}\right|=\left|\Delta ({{\,\textrm{in}\,}}({I_{\mathcal {X}_u}},f))\right|\le \left|\Delta ({{\,\textrm{in}\,}}({I_{\mathcal {X}_u}}),x^ay^b,x^{a+u})\right|. \end{aligned}$$
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(f)\right|\le \left| \Delta (y^{q^{s-1}},x^{\min \{a+u, u(q-1)+1\}},x^{a}y^{b})\right|. \end{aligned}$$
$$\begin{aligned} F_{{{\,\textrm{in}\,}}}:=\{ {{\,\textrm{in}\,}}(f): f\in F\}=\{ x^{a_i}y^{b_i}: 1\le i \le r\}. \end{aligned}$$
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(F)\right|\le \left|\Delta (\{{y^{{q^{s-1}}}},x^{\min \{a_{1}+u, u(q-1)+1\}}\} \cup {F_{{{\,\textrm{in}\,}}}})\right|, \end{aligned}$$
(3)
$$\begin{aligned} \Delta ^*(F):=\Delta (\{{y^{{q^{s-1}}}},x^{\min \{a_{1}+u, u(q-1)+1\}}\} \cup {F_{{{\,\textrm{in}\,}}}}). \end{aligned}$$
$$\begin{aligned} \left|{{\,\textrm{supp}\,}}(D)\right|\ge \left|\mathcal {X}_u\right|-\left|\Delta ^*(F)\right|. \end{aligned}$$
(4)
3 Decreasing norm-trace codes
Let \(\mathcal {L}(\mathcal {M}) \subseteq \mathbb {F}_{q^s}[x,y]\) be the \(\mathbb {F}_{q^s}\)-subspace generated by a set of monomials \(\mathcal {M} \subseteq \mathbb {F}_{q^s}[x,y]\) that is closed under divisibility. Let \(\left\{ P_1,\ldots ,P_n \right\} \subseteq \mathbb {F}_{q^s}^2\) be the rational points of the extended norm-trace curve \({\mathcal {X}}_u\) defined over the finite field \({\mathbb {F}}_{q^s}\) by the equationwhere \(n=u(q-1)q^{s-1}+q^{s-1}\) and u is a positive integer such that \(u \mid \frac{q^s - 1}{q - 1}\). Recall a decreasing norm-trace code is defined byIn this section, we determine the weight hierarchy of decreasing norm-trace codes by proving that the footprint-like bound given in Inequality (3) is always attained with these codes. We start with a lemma that provides a formula for the number of elements in the footprint.
$$\begin{aligned} x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y, \end{aligned}$$
$$\begin{aligned} \textrm{ev}(\mathcal {M}) = \{ \left( f(P_1),\ldots ,f(P_n)\right) : f \in \mathcal {L}(\mathcal {M}) \}. \end{aligned}$$
Lemma 3.1
Let \(r\ge 1\) and \(Z=\{x^{a_i}y^{b_i}:1\le i\le r\}\subset \Delta (y^{q^{s-1}},x^{u(q-1)+1})\) be such that \(a_1<\cdots <a_r\), \(b_1>\cdots > b_r\). Additionally, assume that \(a_r-a_1<u\). Let \(v=\min \{a_1+u, u(q-1)+1\}\). Then
$$\begin{aligned} \left|\Delta ^*(Z)\right|=\left|\Delta (\{y^{q^{s-1}},x^{v}\} \cup Z)\right|=a_1q^{s-1}+b_r(v-a_1)+\sum _{i=1}^{r-1} (a_{i+1}-a_i)(b_i-b_r). \end{aligned}$$
Proof
As \(a_r-a_1<u\), we have \(a_i<v\) for \(i=1,\dots ,r\). We have the decompositionwhere \(Z'=\{x^{a_i-a_1}y^{b_i-b_r},1\le i\le r\}\) (see Fig. 1). It is easy to obtain thatFinally, we have thatThis completes the proof. \(\square \)
$$\begin{aligned} \Delta (\{y^{q^{s-1}},x^{\min \{a_1+u, u(q-1)+1\}}\} \cup Z)=\Delta (y^{q^{s-1}},x^v,x^{a_1}y^{b_r})\cup (x^{a_1}y^{b_r}\cdot \Delta (Z')), \end{aligned}$$
$$\begin{aligned} \left|\Delta (y^{q^{s-1}},x^v,x^{a_1}y^{b_r})\right|=a_1q^{s-1}+b_r(v-a_1). \end{aligned}$$
$$\begin{aligned} \left|\Delta (Z')\right|=\sum _{i=1}^{r-1} (a_{i+1}-a_i)(b_i-b_r). \end{aligned}$$
Fig. 1
Example of the decomposition of the footprint used in the proof of Lemma 3.1 with \(r=3\)
We present now the main result of this section, in which we show how to construct sets of polynomials attaining the footprint-like bound in Inequality (3).
Theorem 3.2
Let \(\mathcal {M}\subset \Delta (y^{q^{s-1}},x^{u(q-1)+1})\) be a decreasing set and \(1\le r\le \left|\mathcal {M}\right|\). Let \(\mathcal {N}_r:=\{ N=\{M_1,\dots ,M_r\}\subset \mathcal {M}: M_i\ne M_j \text { for } i\ne j \}\). Then, the \(r^{th}\) generalized Hamming weight of the decreasing extended norm-trace code is
$$\begin{aligned} d_r({{\,\textrm{ev}\,}}(\mathcal {M}))=\left|\mathcal {X}_u\right|-\max \left\{ \left|\Delta ^*(N)\right|, N \in \mathcal {N}_r\right\} . \end{aligned}$$
Proof
We consider \(N=\{{x^{{a_i}}}y^{b_i}, 1\le i\le r\}\subset \mathcal {M}\), with \(a_1\le \cdots \le a_r\). We will find a set of polynomials F such that \(N={F_{{{\,\textrm{in}\,}}}}\) andwhich proves the result by also considering Inequality (4). We now divide the proof into the following cases:Case (1) Assume \(a_1+u\le u(q-1)+1\), i.e., \(a_1\le u(q-2)+1\).
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(F)\right|=\left|\Delta ^*(F)\right|=\left|\Delta ^*({F_{{{\,\textrm{in}\,}}}})\right|=\left|\Delta ^*(N)\right|, \end{aligned}$$
$$\begin{aligned} {\left\{ \begin{array}{ll} \text {(1)} & a_1\le u(q-2)+1 {\left\{ \begin{array}{ll} \text {(1.1)} & N \text { as in Lemma } 3.1\\ \text {(1.2)} & N \text { not as in Lemma }3.1 {\left\{ \begin{array}{ll} \text {(1.2.1)} & x^{a_j}y^{b_j} | x^ay^b\\ \text {(1.2.2)} & x^{a_1+u} | x^ay^b\\ \end{array}\right. }\\ \end{array}\right. }\\ \text {(2)} & a_1\ge u(q-2)+2 {\left\{ \begin{array}{ll} \text {(2.1)} & N \text { as in Lemma } 3.1\\ \text {(2.2)} & N \text { not as in Lemma } 3.1 \end{array}\right. }\\ \end{array}\right. } \end{aligned}$$
Case (1.1) Consider the case when N is as in Lemma 3.1. In particular, \(a_r-a_1<u\). Fix \(\gamma \in \mathbb {F}_q^*\). In what follows, whenever we consider a collection of elements of \(\mathbb {F}_{q^s}\), we may assume they are pairwise distinct. Consider elements \(\alpha _1,\dots ,\alpha _{a_1}\) such that \(\alpha _i^u\ne \gamma \), for \(1\le i \le a_1\). Note that we can do this because \(a_1\le u(q-2)+1\) and Remark 2.6. We also consider \(\alpha '_1,\dots ,\alpha '_{a_r-a_1}\) such that \((\alpha '_i)^u=\gamma \), for \(1\le i \le a_r-a_1\) (recall \(a_r-a_1<u\)), and \(\beta _1,\dots ,\beta _{b_1}\) such that \({{\,\textrm{Tr}\,}}(\beta _i)=\gamma \), for \(1\le i \le b_1\). Take \(F:= \{f_1,\dots ,f_r\}\), wherefor \(j=1,\dots ,r\). By construction, any point \((\alpha ,\beta )\in \mathcal {X}_u\), with \(\alpha =\alpha _i\), for some \(1\le i\le a_1\), is a common zero of F. The same happens if \(\beta =\beta _i\), for some \(1\le i\le b_r\). These two sets of zeroes are disjoint since \(\alpha _i^u\ne \gamma ={{\,\textrm{Tr}\,}}(\beta _i)\). We obtain \(a_1q^{s-1}+b_r u\) zeroes in this way. By Lemma 2.5 and Remark 2.6, and by inspection of the polynomials in F, it is clear that any other common zero \((\alpha ,\beta )\) of F must have \(\alpha =\alpha '_i\) for some \(1\le i \le a_r-a_1\), and \(\beta =\beta _i\) for some \(b_r+1\le i\le b_1\). If \(\alpha =\alpha '_i\), with \(a_{j}-a_1+1\le i\le a_{j+1}-a_1\) for some \(1\le j\le r-1\), then \((\alpha ,\beta )\) is a common zero of \(\{f_{j+1},\dots ,f_{r}\}\). As \((x-\alpha )\) is not a factor of the rest of the polynomials in F, we must have \(\beta =\beta _\ell \) for some \(b_{r+1}+1\le \ell \le b_j\). This gives \((a_{j+1}-a_j)(b_j-b_{r})\) zeroes, counting for all the possible i with \(a_j-a_1+1\le i\le a_{j+1}-a_1\) and \(\ell \) with \(b_{r+1}+1\le \ell \le b_j\). Considering the sum over all possible j, with \(1\le j \le r-1\), and using Lemma 3.1, we obtain thatCase (1.2) Assume that N is not as in Lemma 3.1. Then, when we consider the setthere are some monomials that are multiples of the others. Therefore, we can consider \(N'\subset N\) such that \(N'\) satisfies the conditions from Lemma 3.1. Arguing as in Case (1.1), we can find a set of \(r'<r\) polynomials \(F'\) such that \({F'_{{{\,\textrm{in}\,}}}}=N'\) andFor each monomial \(x^ay^b\in N\setminus N'\), we know that there is some j such that \(x^{a_j}y^{b_j}\in N'\) and \(x^{a_j}y^{b_j}\) divides \(x^ay^b\), or \(x^{a_1+u}\) divides \(x^{a}y^b\).
$$\begin{aligned} f_j=\prod _{i=1}^{a_1}(x-\alpha _i)\prod _{i=1}^{a_j-a_1}(x-\alpha '_i)\prod _{i=1}^{b_j}(y-\beta _i) \end{aligned}$$
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(F)\right|=\left|\Delta ^*(F)\right|=\left|\Delta (\{y^{q^{s-1}},x^{\min \{a_1+u, u(q-1)+1\}}\} \cup {F_{{{\,\textrm{in}\,}}}})\right|. \end{aligned}$$
$$\begin{aligned} \{y^{q^{s-1}},x^{a_1+u}\} \cup N, \end{aligned}$$
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(F')\right|=\left|\Delta (\{{{y}^{{{q}^{s-1}}}},x^{a_1+u}\} \cup N')\right|=\left|\Delta (\{{{y}^{{{q}^{s-1}}}},{x^{a_{1}+u}}\} \cup N)\right|. \end{aligned}$$
Case (1.2.1) If \(x^{a_j}y^{b_j}\) divides \(x^ay^b\), we consider the polynomialIt is clear thatbecause we are just increasing the multiplicity of the zeroes of \(f_j\in F'\), and \({{\,\textrm{in}\,}}(f_{a,b})=x^ay^b\).
$$\begin{aligned} f_{a,b}=f_j(x-\alpha _1)^{a-a_j}(y-\beta _1)^{b-b_j}. \end{aligned}$$
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(F')\right|=\left|{V_{\mathcal {X}_u}}(F'\cup \{f_{a,b}\})\right| \end{aligned}$$
(5)
Case (1.2.2) If \(x^{a_1+u}\) divides \(x^ay^b\), we consider the polynomialHere, Equation (5) also holds because any common zero \((\alpha ,\beta )\) of \(F'\) has \(\alpha =\alpha _i\) for some \(1\le i \le a_1\), or \(\alpha ^u=\gamma \). We also have \({{\,\textrm{in}\,}}(f_{a,b})=x^ay^b\).
$$\begin{aligned} f_{a,b}=(x^u-\gamma )\left( \prod _{i=1}^{a_1}(x-\alpha _i)\right) (x-\alpha _1)^{a-a_1-u}(y-\beta _1)^{b}. \end{aligned}$$
In both cases (1.2.1) and (1.2.2), we obtain that, for any common zero \((\alpha ,\beta )\) of \(F'\), \((\alpha ,\beta )\) is also a zero of \(f_{a,b}\). Therefore, applying this procedure for every \(x^ay^b\in N\setminus N'\), we can obtain a set F withand \({F_{{{\,\textrm{in}\,}}}}=N\).
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(F)\right|=\left|{V_{\mathcal {X}_u}}(F')\right|=\left|\Delta ^{*}(F)\right| \end{aligned}$$
Case (2) We assume \(a_1\ge u(q-2)+2\). We fix \(\gamma \in \mathbb {F}_q^*\). As \(\mathcal {M}\subset \Delta (y^{q^{s-1}},x^{u(q-1)+1})\), we have \(a_i\le u(q-1)\), for \(1\le i \le r\), which implies \(a_r-u(q-2)\le u\). Hence, we can choose \(\alpha _1,\dots ,\alpha _{u(q-2)+1}\) such that \(\alpha _i^u \ne \gamma \), for \(1\le i\le u(q-2)+1\), and \(\alpha '_1,\dots ,\alpha '_{a_r-u(q-2)-1}\) such that \((\alpha '_i)^u=\gamma \), for \(1\le i \le a_r-u(q-2)-1\). Note that, since \(u(q-2)+2\le a_1\le a_r\), we have \(a_r-u(q-2)-1\ge 1\). As before, we consider \(\beta _1,\dots ,\beta _{b_1}\) such that \({{\,\textrm{Tr}\,}}(\beta _i)=\gamma \), for \(1\le i \le b_1\).
Case (2.1) Assuming N is as in Lemma 3.1, we consider the polynomialsfor \(j=1,\dots ,r\), and \(F=\{f_1,\dots ,f_r\}\). In order to count the number of common zeroes, we note thatdivides \(f_j\), for \(1\le j \le r\). This polynomial has \(a_1q^{s-1}\) zeroes \((\alpha ,\beta )\) with \(\alpha =\alpha _i\) or \(\alpha =\alpha _i'\), and \(ub_r\) zeroes with \(\beta =\beta _i\), for some i. If we consider these zeroes together, we are considering the zeroes with \(\alpha =\alpha '_i\) twice since \((\alpha '_i)^u=\gamma \), which are \((a_1-u(q-2)-1)b_r\) zeroes. Thus, in this way we obtain \(a_1q^{s-1}+(u(q-1)+1-a_1)b_r\) common zeroes of F. Looking at the rest of the factors of the \(f_j\) and counting as before, we obtain \(a_1q^{s-1}+(u(q-1)+1-a_1)b_r+\sum _{i=1}^{r-1}(a_{i+1}-a_i)(b_i-b_r)\) common zeroes in total. By Lemma 3.1, we obtain that \(\left|{V_{\mathcal {X}_u}}(F)\right|=\left|\Delta ^*(F)\right|\).
$$\begin{aligned} f_j=\prod _{i=1}^{u(q-2)+1}(x-\alpha _i)\prod _{i=1}^{a_j-u(q-2)-1}(x-\alpha '_i)\prod _{i=1}^{b_j}(y-\beta _i), \end{aligned}$$
$$\begin{aligned} \prod _{i=1}^{u(q-2)+1}(x-\alpha _i)\prod _{i=1}^{a_1-u(q-2)-1}(x-\alpha '_i)\prod _{i=1}^{b_r}(y-\beta _i) \end{aligned}$$
Remark 3.3
In Theorem 3.2, requiring \(\mathcal {M}\) to be a decreasing set ensures that all the polynomials considered in the proof belong to \(\mathcal {L}(\mathcal {M})\). For a non-decreasing set, we would only obtain a lower bound for \(d_r({{\,\textrm{ev}\,}}(\mathcal {M}))\).
If we wanted to compute \(d_r({{\,\textrm{ev}\,}}(\mathcal {M}))\) directly using the definitions, usually this would require to consider \(\mathcal {F}=\{ F=\{f_1,\dots ,f_r\}\subset \mathcal {L}(\mathcal {M}) \}\), check which sets of \(\mathcal {F}\) are linearly independent, and compute \(\Delta ({I_{\mathcal {X}_u}}, F)\). Sincethis becomes unfeasible in most cases. Using Theorem 3.2, we only need to check the value of \(\Delta ^*(N)\) forsets of monomials. Moreover, the computation of \(\Delta ^*(N)\) itself is straightforward (e.g., using Lemma 3.1 and some variations of it).
$$\begin{aligned} \left|\mathcal {F}\right|=\left( {\begin{array}{c}q^{s\left|\mathcal {M}\right|}-1\\ r\end{array}}\right) , \end{aligned}$$
$$\begin{aligned} \left|\mathcal {N}_r\right|=\left( {\begin{array}{c}\left|\mathcal {M}\right|\\ r\end{array}}\right) \end{aligned}$$
In the next section, we show a way to find \(d_r({{\,\textrm{ev}\,}}(\mathcal {M}))\) directly, without having to check the value of \(\Delta ^*(N)\) for every \(N\in \mathcal {N}_r\), for some particular sets of monomials \(\mathcal {M}\).
4 Generalized Hamming weights of Reed-Muller-type codes over the norm-trace curve
Let \(\left\{ P_1,\ldots ,P_n \right\} \subseteq \mathbb {F}_{q^s}^2\) be the rational points of the extended norm-trace curve \({\mathcal {X}}_u\) defined over the finite field \({\mathbb {F}}_{q^s}\) by the equationwhere \(n=u(q-1)q^{s-1}+q^{s-1}\) and u is a positive integer such that \(u \mid \frac{q^s - 1}{q - 1}\). Let \(0\le d\le u(q-1)(q^{s-1}-1)\). The set of bivariate monomials of degree less than or equal to d that are contained in \(\Delta (y^{q^{s-1}},x^{u(q-1)+1})\) is denoted byLet \(\mathcal {L}(\mathcal {M}_{\le d})\) be the \(\mathbb {F}_{q^s}\)-subspace generated by \(\mathcal {M}_{\le d}\). The Reed-Muller-type code over the norm-trace curve is given byLet \({{\,\textrm{Cart}\,}}_{u}(d)\) be an affine Cartesian code [37] obtained by evaluating \(\mathcal {L}(\mathcal {M}_{\le d})\) at the points of a Cartesian set \(Z_1\times Z_2 \subseteq \mathbb {F}_{q^s}\times \mathbb {F}_{q^s}\), where \(\left|Z_1\right|=u(q-1)+1\) and \(\left|Z_2\right|=q^{s-1}\). Note that the length and dimension of \({{\,\textrm{Cart}\,}}_u(d)\) are the same as the Reed-Muller-type code over the norm-trace curve \({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d})\). We start with a technical lemma that we will use later.
$$\begin{aligned} x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y, \end{aligned}$$
$$\begin{aligned} \mathcal {M}_{\le d}:= {\mathbb {F}}_{q^s}[x,y]_{\le d}\cap \Delta (y^{q^{s-1}},x^{u(q-1)+1}). \end{aligned}$$
$$\begin{aligned} \textrm{ev}(\mathcal {M}_{\le d}) = \{ \left( f(P_1),\ldots ,f(P_n)\right) : f \in \mathcal {L}(\mathcal {M}_{\le d}) \}. \end{aligned}$$
Lemma 4.1
Let \(\mathcal {M}\subset \Delta (y^{q^{s-1}},x^{u(q-1)+1})\) be a decreasing set with \(1\le r\le \left|\mathcal {M}\right|\). Consider \(N\subset \mathcal {M}\) with \(\left|N\right|=r\) such thatand let \(a_1\) be the lowest power of x appearing in any monomial in N. Then either \(x^{a_1+u} \in N \) or \(x^{a_1+u}\not \in \mathcal {M}\).
$$\begin{aligned} \left|\Delta ^*(N)\right|=\max \left\{ \left|\Delta ^*(M')\right|: M'\subset \mathcal {M},\left|M'\right|=r\right\} , \end{aligned}$$
Proof
We can assume \(N=\{x^{a_i}y^{b_i}, 1\le i\le r\}\subset \mathcal {M}\), with \(a_1\le \cdots \le a_r\). Assume \(x^{a_1+u}\not \in N\) and \(x^{a_1+u} \in \mathcal {M}\). By the definition of \(\Delta ^*(N)\), we have that \(\left|\Delta ^*(N)\right|=\left|\Delta ^*(N\cup \{x^{a_1+u}\})\right|\). Due to the proof of Theorem 3.2, we can find a set of polynomials \(F\subset \mathcal {L}(\mathcal {M})\) such that \(F_{{{\,\textrm{in}\,}}}=N\cup \{x^{a_1+u}\}\) andThis implies \(d_{r+1}({{\,\textrm{ev}\,}}(\mathcal {M}))\le \left|\mathcal {X}_u\right|-\left|\Delta ^*(N\cup \{x^{a_1+u}\})\right|=\left|\mathcal {X}_u\right|-\left|\Delta ^*(N)\right|=d_{r}({{\,\textrm{ev}\,}}(\mathcal {M}))\), where the last equality follows from the maximality of \(\left|\Delta ^*(N)\right|\). This contradicts the monotonicity of the generalized Hamming weights from Theorem 2.2. \(\square \)
$$\begin{aligned} \left|V_{\mathcal {X}_u}(F)\right|=\left|\Delta ^*(N\cup \{x^{a_1+u}\})\right|=\left|\Delta ^*(N)\right|. \end{aligned}$$
Let M(r) denote the first r elements of \(\mathcal {M}_{\le d}\) in descending lexicographic order with \(x>y\). For the case with \(\left|Z_1\right|\le \left|Z_2\right|\), in [4] the authors prove that M(r) is the set of monomials that maximizes \(\left|\Delta (y^{\left|Z_2\right|},x^{\left|Z_1\right|},M(r))\right|\). In the next result, we show that M(r) also maximizes \(\left|\Delta ^*(M(r))\right|\) if \(u\ne \frac{q^s-1}{q-1}\).
Lemma 4.2
Let \(0\le d\le u(q-1)(q^{s-1}-1)\) and \(N\subset \mathcal {M}_{\le d}\) with \(\left|N\right|=r\). If \(u\ne \frac{q^s-1}{q-1}\), then
$$\begin{aligned} \left|\Delta ^*(M(r))\right|\ge \left|\Delta ^*(N)\right|. \end{aligned}$$
Proof
Since \(u\ne (q^s-1)/(q-1)\) and \(u\mid (q^s-1)/(q-1)\), we haveTherefore, \(u\le q^{s-1}-1\). Let \(N\subset \mathcal {M}_{\le d}\) with \(\left|N\right|=r\) be such thatBy Lemma 4.1, we can assume that either \(x^{a_1+u}\in N\) or \(x^{a_1+u}\not \in \mathcal {M}_{\le d}\). If \(x^{a_1+u}\not \in \mathcal {M}_{\le d}\), then we haveTo see this, denote \(v'=\min \{ u, u(q-1)+1-a_1 \}\) and note thatwhere \(N/x^{a_1}\) denotes the set of the monomials of N divided by \(x^{a_1}\) (similarly for \(M(r)/x^{a_1}\)). Since \(x^{a_1+u}\not \in \mathcal {M}_{\le d}\), the r elements of \(M(r)/x^{a_1}\) and \(N/x^{a_1}\) are contained in \(\Delta (y^{q^{s-1}},x^{v'})\) (the power of x of those monomials is lower than \(v'\)). By [4, Prop. 3.8], we knowsince this is the inequality that arises when considering a Cartesian code over a product of two sets of sizes \(v'\) and \(q^{s-1}\) (recall that \(u\le q^{s-1}-1\), which implies \(v'\le q^{s-1}-1\)).
$$\begin{aligned} u\le \frac{1}{2}(q^{s-1}+q^{s-2}+\cdots +1)<\frac{2q^{s-1}}{2}=q^{s-1}. \end{aligned}$$
$$\begin{aligned} \left|\Delta ^*(N)\right|=\max \left\{ \left|\Delta ^*(M')\right|: M'\subset \mathcal {M}_{\le d},\left|M'\right|=r\right\} . \end{aligned}$$
$$\begin{aligned} \left|\Delta ^*(M(r))\right|\ge \left|\Delta ^*(N)\right|. \end{aligned}$$
$$\begin{aligned} \begin{aligned}&\left|\Delta ^*(M(r))\right|=a_1(q^{s-1}-1)+\left|\Delta \left( (M(r)/x^{a_1})\cup \{ y^{q^{s-1}},x^{v'}\}\right) \right|,\\&\left|\Delta ^*(N)\right|=a_1(q^{s-1}-1)+\left|\Delta \left( (N/x^{a_1})\cup \{ y^{q^{s-1}},x^{v'}\}\right) \right|, \end{aligned} \end{aligned}$$
(6)
$$\begin{aligned} \left|\Delta \left( (M(r)/x^{a_1})\cup \{ y^{q^{s-1}},x^{v'}\}\right) \right|\ge \left|\Delta \left( (N/x^{a_1})\cup \{ y^{q^{s-1}},x^{v'}\}\right) \right| \end{aligned}$$
If we assume now that \(x^{a_1+u}\in N\), then (6) still holds, but some elements of \(M(r)/x^{a_1}\) and \(N/x^{a_1}\) are not contained in \(\Delta (y^{q^{s-1}},x^{v'})\) because they are multiples of \(x^{v'}\). LetBy the definition of M(r), we must have \(r''\le r'\). If \(r''<r'\), there is \(\tilde{r}\) such that \(\left|(M(r+\tilde{r})/x^{a_1})\cap \Delta (y^{q^{s-1}},x^{v'})\right|=r'\), and \((M(r+\tilde{r})/x^{a_1})\cap \Delta (y^{q^{s-1}},x^{v'})\) are precisely the first \(r'\) elements of \(\Delta (y^{q^{s-1}},x^{v'})\) in descending lexicographic order Hence, by [4, Prop. 3.8], we haveSince \(M(r)/x^{a_1}\subset M(r+\tilde{r})/x^{a_1}\), we obtain the result. \(\square \)
$$\begin{aligned} \begin{aligned} \left|(N/x^{a_1})\cap \Delta (y^{q^{s-1}},x^{v'})\right|=r'<r, \, \left|(M(r)/x^{a_1})\cap \Delta (y^{q^{s-1}},x^{v'})\right|=r''<r. \end{aligned} \end{aligned}$$
$$\begin{aligned} \left|\Delta \left( (M(r+\tilde{r})/x^{a_1})\cup \{ y^{q^{s-1}},x^{v'}\}\right) \right|\ge \left|\Delta \left( (N/x^{a_1})\cup \{ y^{q^{s-1}},x^{v'}\}\right) \right|. \end{aligned}$$
Due to Lemma 4.2, we can directly obtain \(d_r({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d}))\) when \(u\ne \frac{q^s-1}{q-1}\), and we can also relate the generalized Hamming weights of these decreasing norm-trace codes with the ones from Cartesian codes.
Theorem 4.3
Let \(0\le d\le u(q-1)(q^{s-1}-1)\) and \(1\le r\le \left|\mathcal {M}_{\le d}\right|\). If \(u\ne \frac{q^s-1}{q-1}\), then \(r^{th}\) generalized Hamming weight isAs a consequence, if \(u\le \frac{q^{s-1}-1}{q-1}\), we haveMoreover, for any u such that \(u\mid \frac{q^s-1}{q-1}\), we have the bound
$$\begin{aligned} d_r({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d}))=\left|\mathcal {X}_u\right|-\left|\Delta ^*(M(r))\right|=\left|\mathcal {X}_u\right|-\left|\Delta (M(r),y^{q^{s-1}},x^{u(q-1)+1})\right|. \end{aligned}$$
$$\begin{aligned} d_r({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d}))=d_r({{\,\textrm{Cart}\,}}_u(d)). \end{aligned}$$
$$\begin{aligned} d_r({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d}))\ge d_r({{\,\textrm{Cart}\,}}_u(d)). \end{aligned}$$
Proof
We start with the case \(u\ne (q^s-1)/(q-1)\). By Theorem 3.2 and Lemma 4.2, we haveNow we claim \(\Delta ^*(M(r))=\Delta (M(r),y^{q^{s-1}},x^{u(q-1)+1})\). Indeed, let \(a_1\) be the smallest power of x in M(r). If \(a_1+u\ge u(q-1)+1\), the claim follows from the definition of \(\Delta ^*\). If \(a_1+u< u(q-1)+1\), then \(x^{a_1}y^{b_1}\in M(r)\), for some \(b_1\). If \(b_1=0\), we have \(x^{a_1}\mid x^{a_1+u}\). If \(b_1>0\), by the definition of M(r), this implies \(x^{a_1+1}\in M(r)\). Since \(x^{a_1+1}\mid x^{a_1+u}\), we have proved the claim. By [4], if \(u(q-1)\le q^{s-1}-1\), we have \(d_r({{\,\textrm{Cart}\,}}_u(d))=\left|\mathcal {X}_u\right|-\left|\Delta (M(r),y^{q^{s-1}},x^{u(q-1)+1})\right|\).
$$\begin{aligned} d_r({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d}))=\left|\mathcal {X}_u\right|-\left|\Delta ^*(M(r))\right|. \end{aligned}$$
With respect to the bound, we note that for any set \(N\subset \mathcal {M}_{\le d}\), we have \(\Delta ^*(N) \subset \Delta (N\cup \{y^{q^{s-1}},x^{u(q-1)+1}\})\). Thus,By choosing N with maximum \(\left|\Delta ^*(N)\right|\), we obtain the stated lower bound. \(\square \)
$$\begin{aligned} d_r({{\,\textrm{Cart}\,}}_u(d))\le \left|\mathcal {X}_u\right|-\left|\Delta (N\cup \{y^{q^{s-1}},x^{u(q-1)+1}\})\right|\le \left|\mathcal {X}_u\right| - \left|\Delta ^*(N)\right|. \end{aligned}$$
By Theorem 4.3, the codes \({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d})\) are on par with \({{\,\textrm{Cart}\,}}_u(d)\) if \(u\le \frac{q^{s-1}-1}{q-1}\), and they can perform better in other cases. Now, we give an example with each of the cases of Theorem 4.3, showing how decreasing norm-trace codes can outperform Cartesian codes.
Example 4.4
Let \(q=3\), \(s=2\), \(d=4\) and \(r=3\). For \(u=1\), we have \(u\le (q^{s-1}-1)/(q-1)=1\), andThis is obtained with the set \(M(3)=\{y^2x^2,yx^2,x^2\}\). If we consider \(u=2\) instead, we obtainIn this case, \(M(3)=\{x^4,yx^3,x^3\}\). Finally, if \(u=4=(q^s-1)/(q-1)\), we haveThis value is attained with \(N=\{yx^3,yx^2,y^2x^2\}\ne M(3)=\{x^4,yx^3,x^3\}\) (\(\left|\mathcal {X}_u\right|-\Delta ^*(M(3))\) gives 18 in this case).
$$\begin{aligned} d_3({{\,\textrm{ev}\,}}(\mathcal {M}_{\le 4}))=d_3({{\,\textrm{Cart}\,}}_1(4))=3. \end{aligned}$$
$$\begin{aligned} d_3({{\,\textrm{ev}\,}}(\mathcal {M}_{\le 4}))=6>5=d_3({{\,\textrm{Cart}\,}}_2(4)). \end{aligned}$$
$$\begin{aligned} d_3({{\,\textrm{ev}\,}}(\mathcal {M}_{\le 4}))=17>9=d_3({{\,\textrm{Cart}\,}}_4(4)). \end{aligned}$$
Moreover, these examples also showcase the importance of considering the extra monomial \(x^{a+u}\) in the definition of \(\Delta ^*(F)\). Otherwise, the footprint approach would give the same bound for the generalized Hamming weights as the one we have for Cartesian codes.
In Example 4.4, for the case \(u=4\), the set of monomials N which gives the maximum value of \(\Delta ^*(N)\) does not correspond to M(r), nor to the analogous set obtained by choosing \(y>x\) in the ordering of the elements. This shows that for \(u=\frac{q^s-1}{q-1}\), the description of the set N that maximizes \(\left|\Delta ^*(N)\right|\) gets more involved. We will now study the case \(u=\frac{q^s-1}{q-1}\) in more detail.
Let \(0\le a_1\le u(q-1)\), and letConsider \(M_{a_1}'(r)\), the set formed by the first r elements of \(\mathcal {M}^{a_1}_{\le d}\) in descending lexicographic order with \(y>x\) (for \(r\le 0\), we will define \(M_{a_1}'(r)=\emptyset \)). Since \(u=\frac{q^s-1}{q-1}>q^{s-1}\), by [4] this set maximizes \(\left|\Delta (y^{q^{s-1}},x^u,N)\right|\) for any \(N\subset \mathcal {M}^{a_1}_{\le d}\). If \(d\ge a_1+u\), we consider the setWe denote \(r_{a_1}:=\left|T_{a_1}\right|=\frac{(d-a_1-u)(d-a_1-u+1)}{2}\). In the next result, we show that we only need to consider a few sets of monomials to compute the generalized Hamming weights as in Theorem 3.2.
$$\begin{aligned} \mathcal {M}^{a_1}_{\le d}:=\mathbb {F}_{q^s}[x,y]_{\le d-a_1}\cap \Delta (y^{q^{s-1}},x^u). \end{aligned}$$
$$\begin{aligned} T_{a_1}:=\{ x^ay^b\mid a_1+u\le a \le d, 0\le b \le d-a \}. \end{aligned}$$
Proposition 4.5
Let \(u=\frac{q^s-1}{q-1}\), \(1\le d \le u(q-1)(q^{s-1}-1)\) and \(1\le r\le \left|\mathcal {M}_{\le d}\right|\). For each \(0\le a_1\le d\), considerDenote \(r'=r_{a_1}+d-q^{s-1}-a_1+2\) and considerThen we haveMoreover,
$$\begin{aligned} \mathcal {N}(a_1):=\{ N \subset \mathcal {M}_{\le d}\;: \left|N\right|=r, \; a_1=\min \{ a\mid x^ay^b\in N, \text { for some }b \} \}. \end{aligned}$$
$$\begin{aligned} N_{a_1}={\left\{ \begin{array}{ll} x^{a_1}\cdot M'_{a_1}(r) & \text { if } d<a_1+u, \\ x^{a_1}\cdot M'_{a_1}(r-r_{a_1})\cup T_{a_1} & \text { if } d\ge a_1+u \text { and } r\ge r'. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} \left|N_{a_1}\right|=\max \left\{ \left|\Delta ^*(N)\right|: N\subset \mathcal {N}(a_1), \left|N\right|=r \right\} . \end{aligned}$$
$$\begin{aligned} d_r({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d}))=\left|\mathcal {X}_u\right|-\max \biggl \{ \left|\Delta ^*(N_{a_1})\right| \biggr .: \begin{aligned}&0\le a_1\le \min \{d,u(q-1)\} \\&d<a_1+u \text { or } d\ge a_1+u \text { and } r\ge r' \end{aligned}\biggl .\biggr \}. \end{aligned}$$
Proof
Fix \(0\le a_1\le d\) and \(1\le d \le u(q-1)(q^{s-1}-1)\). Assume first \(d<a_1+u\). For any \(N\in \mathcal {N}(a_1)\), we have the monomials \(x^ay^b\) with \(0\le a <a_1\), and the monomials \(x^ay^b\) with \(a_1+u\le a \le u(q-1)\) in \(\Delta (y^{q^{s-1}},x^{u(q-1)+1})){\setminus } \Delta ^*(N)\). Therefore, the differences between different sets \(N\in \mathcal {N}(a_1)\) arise from the monomials \(x^ay^b\) with \(a_1\le a <a_1+u\), and we have to find the set N that maximizes the number of monomials in \(\Delta ^*(N)\) in this region. This is equivalent to finding the set \(N' \subset \mathcal {M}_{\le d}^{a_1}\) that maximizes the number of monomials in \(\Delta (y^{q^{s-1}},x^u,N)\) (we then multiply the monomials of \(N'\) by \(x^{a_1}\)). By [4], we know that this set is \(M_{a_1}'(r)\).
If \(d\ge a_1+u\), we have \(x^{a_1+u}\in \mathcal {M}_{\le d}\). Following the idea of the proof of Lemma 4.1, if \(r\ge r'>r_{a_1}\), then \(T_{a_1}\subset N_{a_1}\). Restricting ourselves to the subsets \(N\subset \mathcal {M}_{\le d}\) such that \(T_{a_1}\subset N\), the problem of finding \(N_{a_1}\) among them is as in the previous case, since again the differences arise from the monomials \(x^ay^b\) with \(a_1\le a <a_1+u\). Note that \(r\ge r'\) ensures that \(\min \{a\mid x^ay^b\in x^{a_1}\cdot M'_{a_1}(r-r_{a_1})\}=a_1\).
We will use Theorem 3.2 to finish the proof. It is clear thatAssume \(r< r'\). By Lemma 4.1, ifthen we should have \(T_{a_1}\subset N_{a_1}\). This is a contradiction if \(r<r_{a_1}\). If \(r\ge r_{a_1}\), we have \(T_{a_1}\subset N_{a_1}\), and the argument from above shows that the set N with \(r-r_{a_1}\) elements that maximizes the number of monomials in \(\Delta (y^{q^{s-1}},x^u,N)\) is \(M_{a_1}'(r-r_{a_1})\). The set \(x^{a_1}\cdot M'_{a_1}(r-r_{a_1})\cup T_{a_1}\) has r monomials. We haveSince \(r<r'\), this is not equal to \(a_1\). This means thatwith \(a'_1>a_1\), a contradiction with Equation (7). \(\square \)
$$\begin{aligned} \max \left\{ \left|\Delta ^*(N)\right|, N \subset \mathcal {N}_r\right\} =\max \left\{ \left|\Delta ^*(N_{a_1})\right|, 0\le a_1\le \min \{d,u(q-1)\}\right\} . \end{aligned}$$
$$\begin{aligned} \left|\Delta ^*(N_{a_1})\right|=\max \left\{ \left|\Delta ^*(N)\right|, N \subset \mathcal {N}_r\right\} , \end{aligned}$$
(7)
$$\begin{aligned} a'_1=\min \{a\mid x^ay^b\in x^{a_1}\cdot M'_{a_1}(r-r_{a_1})\cup T_{a_1}\}={\left\{ \begin{array}{ll} a_1+u & \text { if } r=r_{a_1},\\ d-q^{s-1}-r+r_{a_1}+2 & \text { if } r>r_{a_1}. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} \left|\Delta ^*(N_{a'_1})\right|> \left|\Delta ^*(N_{a_1})\right|, \end{aligned}$$
Example 4.6
Continuing with Example 4.4, for the case \(u=4\) it is easy to check that
$$\begin{aligned} N=\{yx^3,yx^2,y^2x^2\}=x^2\cdot \{ yx,y,y^2\}=x^2 \cdot M_2'(3)=N_2. \end{aligned}$$
Proposition 4.5 allows us to compute the generalized Hamming weights by considering, at most, \(\min \{d,u(q-1)\}+1\) sets of monomials. Although this is already relatively easy to compute, we show now a particular case in which we can directly obtain the generalized Hamming weights.
Corollary 4.7
Let \(u=\frac{q^s-1}{q-1}\), \(1\le d < q^{s-1}\) and \(1\le r\le \left|\mathcal {M}_{\le d}\right|\). Then
$$\begin{aligned} d_r({{\,\textrm{ev}\,}}(\mathcal {M}_{\le d}))=\left|\mathcal {X}_u\right|-\left|\Delta ^*(M'_0(r))\right|. \end{aligned}$$
Proof
From Proposition 4.5, if \(\mathcal {N}_{a_1}\ne \emptyset \) we haveConsider \(b_1=\min \{b\mid y^b \in M'_{a_1}(r)\}\), \(b_2=\min \{b \mid x^ay^b\in M'_{a_1}(r) \text { for some }a>0\}\), and \(\lambda =\min \{a\mid x^ay^{b_1}\in M'_{a_1}(r)\}\). Defining \(a_2=a_1+\lambda \) and using Lemma 3.1, it is straightforward to check thatIf we want to compare this with \(\left|\Delta ^*(N_{a'_1})\right|\), for some \(a'_1=a_1+\varepsilon \) with \(\varepsilon >0\), we see that the corresponding values of \(b_1,b_2,a_2\) for \(a'_1\) become \(b'_1=b_1-\varepsilon \), \(b'_2=b_2-\varepsilon \), and \(a_2=a_2+\varepsilon \). The difference iswhich means that \(N_0=M_0'(r)\) maximizes \(\left|\Delta ^*(N_{a_1})\right|\). \(\square \)
$$\begin{aligned} N_{a_1}=x^{a_1}\cdot M'_{a_1}(r). \end{aligned}$$
$$\begin{aligned} \left|\Delta ^*(N_{a_1})\right|=a_1q^{s-1}+b_2u+(a_2-a_1)(b_1-b_2). \end{aligned}$$
$$\begin{aligned} \left|\Delta ^*(N_{a_1})\right|-\left|\Delta ^*(N_{a'_1})\right|=-\varepsilon q^{s-1}+\varepsilon u=\epsilon \left( \frac{q^s-1}{q-1}-q^{s-1}\right) >0, \end{aligned}$$
5 Relative generalized Hamming weights of decreasing norm-trace codes and quantum codes
Relative generalized Hamming weights were introduced to characterize the security of linear ramp secret-sharing schemes. The r-the relative generalized Hamming weight of a pair of codes \(C_1\) and \(C_2\) with \(C_2\subset C_1\) is the smallest number such that any set of shares of that size allows to recover r q-bits of information about the secret for any set of that size, and the m-th relative generalized Hamming weight of the pair of codes \(C_1^\perp \subset C_2^\perp \) gives the smallest size of a set of shares that can determine m q-bits of information about the secret [21, 35]. These parameters have been studied for many different families of codes [4, 17, 20], and in particular, for one-point algebraic geometry codes [13, 21]. In what follows, we study the relative generalized Hamming weights of decreasing norm-trace codes and their relation to impure quantum codes. We start by defining the relative generalized Hamming weights of a pair of codes using the definition from [36, Lemma 1].
Definition 5.1
Let \(C'\subset C\subset \mathbb {F}_{q^s}^n\) be two linear codes, and consider r with \(1\le r \le \dim C -\dim C'\). The r-th relative generalized Hamming weight of C and \(C'\), denoted \(M_r(C,C')\), isIt is useful to note that the condition \(D\cap C'=\{0\}\) is equivalent to the condition \(D\setminus \{0\}\subset C\setminus C'\). That is why, in many cases, one studies the subcodes of \(C\setminus C'\) (disregarding the vector 0) for computing the relative generalized Hamming weights.
$$\begin{aligned} M_r(C,C')=\min \{ \left|{{\,\textrm{supp}\,}}(D)\right|: D \text { is a subcode of } C \text { with } \dim D=r, \; D\cap C'=\{0\}\}. \end{aligned}$$
From the definition, it is clear that the relative generalized Hamming weights are a generalization of generalized Hamming weights obtained by considering \(C'=\{0\}\). Moreover, for \(1\le r \le \dim C-\dim C'\), we haveThus, we can always bound the relative generalized Hamming weights from below using the generalized Hamming weights, and we can use the results from the previous sections to obtain bounds for the relative generalized Hamming weights. With respect to decreasing norm-trace codes, it is possible to use the techniques from the previous section to obtain the relative generalized Hamming weights. The idea is similar to that of the relative footprint from [32].
$$\begin{aligned} M_r(C,C')\ge d_r(C). \end{aligned}$$
(8)
Theorem 5.2
Let \(\mathcal {M}_2\subset \mathcal {M}_1\subset \Delta (y^{q^{s-1}},x^{u(q-1)+1})\) be decreasing sets. Let \(1\le r \le \left|\mathcal {M}_1\right|-\left|\mathcal {M}_2\right|\), and let \(\mathcal {M}_{1,2}^r\) be the set of all subsets M of \(\{{{\,\textrm{in}\,}}(f)\mid f\in \mathcal {L}(\mathcal {M}_1)\setminus \mathcal {L}(\mathcal {M}_2)\}\) with r elements. ThenMoreover, if \(x^ay^b\in \mathcal {M}_1\setminus \mathcal {M}_2\) implies \(x^ay^b>x^{a'}y^{b'}\), for all \(x^{a'}y^{b'}\in \mathcal {M}_2\) (we abbreviate this by writing \(\mathcal {M}_1\setminus \mathcal {M}_2> \mathcal {M}_2\)), then
$$\begin{aligned} M_r({{\,\textrm{ev}\,}}(\mathcal {M}_1),{{\,\textrm{ev}\,}}(\mathcal {M}_2))\ge \left|\mathcal {X}_u\right|-\max \{\Delta ^*(M)\mid M \in \mathcal {M}_{1,2}^r\}. \end{aligned}$$
$$\begin{aligned} M_r({{\,\textrm{ev}\,}}(\mathcal {M}_1),{{\,\textrm{ev}\,}}(\mathcal {M}_2))= \left|\mathcal {X}_u\right|-\max \{\Delta ^*(M)\mid M \subset \mathcal {M}_1\setminus \mathcal {M}_2,\;\left|M\right|=r\}. \end{aligned}$$
(9)
Proof
Consider \(R_r\) the set of all subsets \(F=\{f_1,\dots ,f_r\}\subset \mathcal {L}(\mathcal {M}_1)\setminus \mathcal {L}(\mathcal {M}_2)\) of size r such that \({{\,\textrm{in}\,}}(f_1),\dots ,{{\,\textrm{in}\,}}(f_r)\) are different. From [32] we haveTaking into account that \(\left|\Delta ({I_{\mathcal {X}_u}},F)\right|=\left|{V_{\mathcal {X}_u}}(F)\right|\) and the bound (3), we obtainIf \(\mathcal {M}_1\setminus \mathcal {M}_2>\mathcal {M}_2\), then, for any \(f\in \mathcal {L}(M_1)\setminus \mathcal {L}(M_2)\), we have \({{\,\textrm{in}\,}}(f)\in \mathcal {M}_1\setminus \mathcal {M}_2\). Indeed, if we had \({{\,\textrm{in}\,}}(f)\in \mathcal {M}_2\), by the hypothesis \(\mathcal {M}_1\setminus \mathcal {M}_2>\mathcal {M}_2\) this would imply that all the monomials of f are in \(\mathcal {M}_2\), which implies \(f\in \mathcal {L}(M_2)\), a contradiction. Thus, \(\mathcal {M}_{1,2}^r\) is the set of all subsets M of monomials in \(\mathcal {M}_1\setminus \mathcal {M}_2\) of size r, and we have to prove that the equality holds in the bound we have proved above.
$$\begin{aligned} M_r({{\,\textrm{ev}\,}}(\mathcal {M}_1),{{\,\textrm{ev}\,}}(\mathcal {M}_2))=\left|\mathcal {X}_u\right|-\max \{\left|\Delta ({I_{\mathcal {X}_u}},F)\right|\mid F\in R_r\}. \end{aligned}$$
$$\begin{aligned} \begin{aligned} M_r({{\,\textrm{ev}\,}}(\mathcal {M}_1),{{\,\textrm{ev}\,}}(\mathcal {M}_2))&\ge \left|\mathcal {X}_u\right|-\max \{\Delta ^*(F)\mid F\in R_r\}\\&=\left|\mathcal {X}_u\right|-\max \{\Delta ^*(M)\mid M \in \mathcal {M}_{1,2}^r\}. \end{aligned} \end{aligned}$$
By the proof of Theorem 3.2, for each set \( M \subset \mathcal {M}_1\setminus \mathcal {M}_2\) with size r, we can find a set of r polynomials F such that \(M={F_{{{\,\textrm{in}\,}}}}\). Since \({F_{{{\,\textrm{in}\,}}}}\subset \mathcal {M}_1\setminus \mathcal {M}_2\), this implies that \(F\subset \mathcal {L}(M_1)\setminus \mathcal {L}(M_2)\). Moreover, we haveBy choosing M such thatwe see that the lower bound we have obtained is attained by \(F\subset \mathcal {L}(\mathcal {M}_1)\setminus \mathcal {L}(\mathcal {M}_2)\), which concludes the proof. \(\square \)
$$\begin{aligned} \left|{V_{\mathcal {X}_u}}(F)\right|=\Delta ^*(F)=\Delta ^*(M). \end{aligned}$$
$$\begin{aligned} \max \{\Delta ^*(M): M\subset \mathcal {M}_1\setminus \mathcal {M}_2,\;\left|M\right|=r\}=\Delta ^*(M), \end{aligned}$$
From [12], we have the following result.
Theorem 5.3
Assume \(\mathcal {X}_u=\{P_1,\dots ,P_n\}\) and let \(\mathcal {M}\subset \Delta (y^{q^{s-1}},u^{u(q-1)+1})\) be a decreasing set. The dual code \({{\,\textrm{ev}\,}}(\mathcal {M})^\perp \) is equivalent to \({{\,\textrm{ev}\,}}(\mathcal {M}^c)\), whereMore precisely,whereand \(\star \) denotes the component-wise product of vectors.
$$\begin{aligned} \mathcal {M}^c:=\left\{ \frac{x^{u(q-1)}y^{q^{s-1}-1}}{x^ay^b}: x^ay^b\in \Delta (y^{q^{s-1}},x^{u(q-1)+1})\setminus \mathcal {M}\right\} . \end{aligned}$$
$$\begin{aligned} {{\,\textrm{ev}\,}}(\mathcal {M})^\perp =\beta \star {{\,\textrm{ev}\,}}(\mathcal {M}^c), \end{aligned}$$
$$\begin{aligned} \beta _i:={\left\{ \begin{array}{ll} u^{-1} & \text { if the } x\text {-coordinate of }P_i \text { is nonzero,}\\ 1 & \text { otherwise,} \end{array}\right. } \end{aligned}$$
Remark 5.4
Since \(\mathcal {M}^c\) is decreasing if \(\mathcal {M}\) is decreasing, and \(\beta \) does not depend on \(\mathcal {M}\), we can also use Theorem 5.2 to compute the relative generalized Hamming weights of the duals of a pair of decreasing norm-trace codes.
As stated in [12], the family of decreasing norm-trace codes contains one-point algebraic geometry codes over the norm-trace (in particular, Hermitian codes). With the usual notation \(C(D_u,\lambda P_\infty )\) for one-point algebraic geometry codes, we consider \(D_u=\sum _{P_i\in \mathcal {X}_u}P_i\). Then, the evaluation ofgives a basis for \(C(D_u,\lambda P_\infty )\). Since this is a decreasing set, we can use Theorem 3.2 to compute the generalized Hamming weights of this code. This recovers, in particular, the result by Barbero and Munuera [2], although in a less explicit way. Nevertheless, our techniques cover all the one-point algebraic geometry codes over the extended norm-trace curve.
$$\begin{aligned} \mathcal {L}_\lambda =\left\{ x^ay^b\in \Delta (y^{q^{s-1}},x^{u(q-1)+1})\mid aq^{s-1}+bu\le \lambda \right\} \end{aligned}$$
As a particular case of Theorem 5.2, if one considers a pair of one-point algebraic geometry codes over \(\mathcal {X}_u\), then we always have the equality in (9). The relative generalized Hamming weights of one-point algebraic geometry codes have been previously studied in [21] using the Feng-Rao bound. In our case, we use a footprint-like approach. Moreover, the authors in [21] check that their bound is often tight for Hermitian codes, and in our case, we prove that our bound is always tight for norm-trace codes (in particular, for Hermitian codes). The particular case of Hermitian codes is studied in more depth in [13].
The first relative generalized Hamming weight (also called relative minimum distance) of a pair of codes (and their duals) also has applications to quantum codes. As we show next, from a nested pair of codes \(C_2\subset C_1\), one can construct a quantum error-correcting code (QECC) that encodes \(\dim C_1-\dim C_2\) logical qudits using n physical qudits. QECCs codes can correct two different types of errors, namely phase-shift errors and qudit-flip errors. The error-correction capabilities of the code for each type of error are denoted by \(\delta _z\) and \(\delta _x\), respectively, meaning that this code can correct up to \(\lfloor (\delta _z-1)/2\rfloor \) phase-shift errors and up to \(\lfloor (\delta _x-1)/2\rfloor \) qudit-flip errors. The error correction capabilities of the QECC are given precisely by the first relative generalized Hamming weight of the nested pair of codes \(C_2\subset C_1\) and their duals \(C_1^\perp \subset C_2^\perp \). We now provide the precise statement of the CSS construction that we use to construct quantum codes, which was obtained independently by Calderbank and Shor [10] and Steane [45].
Theorem 5.5
Let \(C_2\subset C_1\subset \mathbb {F}_{q^s}^n\) be linear codes. Then, we can construct an asymmetric quantum code with parameterswhere \(\delta _z=M_1(C_1,C_2)\) and \(\delta _x=M_1(C_2^\perp ,C_1^\perp )\).
$$\begin{aligned} [[n,\dim C_1-\dim C_2,\delta _z/\delta _x]]_{q^s}, \end{aligned}$$
If \(M_1(C_1,C_2)=d_1(C_1)\) and \(M_1(C_2^\perp ,C_1^\perp )=d_1(C_2^\perp )\), we say that the corresponding quantum code is pure, and is called impure otherwise (recall (8)). Impure quantum codes are desired since they have decoding advantages and are, in general, difficult to obtain using classical codes [1, 25].
Notice that, by considering \(C_1^\perp \subset C_2^\perp \) in the previous result, we obtain a quantum code with the same parameters, but with \(\delta _z\) and \(\delta _x\) exchanged. In all of our examples, we will choose the codes with \(\delta _z\ge \delta _x\) since phase-shift errors are more likely to occur than qudit-flip errors [29], but one can always obtain also a quantum code with the minimum distances exchanged by using the duals.
The following example shows how to obtain asymmetric quantum codes with good parameters using one-point codes over the norm-trace curve.
Example 5.6
Let \(q=5\), \(s=2\), and \(u=3\). Then, we have \(\left|\mathcal {X}_u\right|=65\). Consider the set \(\mathcal {M}_2=\{1,y,x,y^2\}\) and \(\mathcal {M}_1=\mathcal {M}_2\cup \{xy\}\). The codes \(C_1={{\,\textrm{ev}\,}}(\mathcal {M}_1)\) and \(C_2={{\,\textrm{ev}\,}}(\mathcal {M}_2)\) have parameters \([65,5,57]_{25}\) and \([65,4,59]_{25}\), respectively. The minimum distances can be obtained with Theorem 3.2 (or [12, Thm. 4.3]). With respect to the dual codes, we use Theorem 5.3. Note that \(\mathcal {M}_1^c=\Delta (x^{13},y^5)\setminus \{ (x^{12}y^3)/M \mid M\in \mathcal {M}_1\}=\Delta (x^{13},y^5)\setminus \{x^{11}y^3,x^{12}y^2,x^{11}y^4,x^{12}y^3,x^{12}y^4\}\), and \(\mathcal {M}_2^c=\mathcal {M}_1^c\cup \{ x^{11}y^3\}\). Then \(C_1^\perp =\beta \star {{\,\textrm{ev}\,}}(\mathcal {M}_1^c)\) and \(C_2^\perp =\beta \star {{\,\textrm{ev}\,}}(\mathcal {M}_2^c)\). As before, we can compute the parameters and obtain \([65,60,3]_{16}\) and \([65,61,3]_{16}\). If we just use the minimum distances of \(C_1\), \(C_2\), and their duals, using Theorem 5.5 we obtain a quantum code with parameters \([[65,1,\ge 57/\ge 3]]_{16}\). In this case, we can use (9) since \(C_1\) and \(C_2\) are constructed with monomials with increasing weighted degrees. Note that, since \(d_1(C_1)<d_2(C_2)\), we have \(d_1(C_1)=M_1(C_1,C_2)=57\). However, for the duals, we have \(M_1(C_2^\perp ,C_1^\perp )=4>d_1(C_1^\perp )=3\). This is because \(\mathcal {M}_2^c\setminus \mathcal {M}_1^c=\{ x^{11}y^3\}\), and it is straightforward to check that \(\Delta ^*(x^{11}y^3)=61\). Thus, by using Theorem 5.5, this time with the relative minimum distances, the corresponding quantum code has parameters \([[65,1,57/4]]_{16}\), and this code is impure.
We now introduce a way to check the goodness of these codes that have been previously used in [13, 17]. Assume that we have a pair of linear codes \(C_2\subset C_1\subset \mathbb {F}_{q^s}^n\) of codimension \(\ell \) and \(M_1(C_1,C_2)=\delta _z\). Then we consider the greatest value \(g(\ell ,\delta )\) such that the tables of best-known linear codes ensure the existence of \(C,C'\subset \mathbb {F}_{q^s}^n\) with \(\dim C-\dim C'=\ell \), \(d_1(C)=\delta _z\), and \(d_1({C'}^\perp )\ge g(\ell ,\delta _z)\). If we had \(C'\subset C\), by Theorem 5.5 this would give rise to a quantum code with parameters \([[n,\ell , \ge \delta _z/\ge g(\ell ,\delta _z)]]_{q^s}\). In Table 1, we show some of the quantum codes that we can obtain by considering \(C_1=C(D_u,\lambda _1 P_\infty )\) and \(C_2=C(D_u,\lambda _2 P_\infty )\), with \(\lambda _2<\lambda _1\), in Theorem 5.5. Note that the codes we obtain can give the same parameters as the best-known codes and even outperform them in some cases. This is remarkable since, using the best-known codes, we do not have \(C'\subset C\) in general (in fact, it is quite unlikely). The most commonly used table of best-known linear codes is [24]. However, this table only covers linear codes over finite field sizes of at most 9. Since the finite fields we are considering for norm-trace codes can be bigger, we will use [44] instead to compute \(g(\ell ,\delta )\). Also, since a similar approach is taken in [13] for Hermitian codes, we will not consider the case with \(s=2\) and \(u=(q^s-1)/(q-1)=q+1\), since it corresponds precisely to the Hermitian curve.
In Table 1, if there is no code C with \(d_1(C)=\delta _z\), we have considered the code with the highest dimension and \(d_1(C)> \delta _z\), and we have marked this cases with \(^*\). Impure codes are marked with \(^\star \), and all of them satisfy \(M_1(C_1,C_2)=d_1(C_1)\), \(M_2(C_2^\perp ,C_1^\perp )>d_2(C_2^\perp )\), except the codes \([[32,1,15/8]]_8\) and \([[32,1,12/10]]_8\), which have both \(M_1(C_1,C_2)>d_1(C_1)\) and \(M_2(C_2^\perp ,C_1^\perp )>d_2(C_2^\perp )\). We highlight a couple of particular cases now. For \(q=5\), \(s=2\), and \(u=3\), we obtain several codes whose \(d_x\) surpasses the value \(g(\ell ,\delta _z)\). However, these codes are not impure, and what is happening is that we are actually using codes that surpass the best-known parameters of linear codes in [44]. Indeed, the codes \([65,3,60]_{25}\), \([65,4,59]_{25}\) and \([65,55,8]_{25}\), corresponding to \(\lambda \) equal to 5, 6 and 58, respectively, have better minimum distance than the codes stated in [44] for the same length and dimension (this explains why g(2, 60) and g(3, 59) cannot be computed for \([[65,2,60/2]]_{25}\) and \([[65,3,59/2]]_{25}\), respectively). We also highlight the code \([[45,1,41/3]]_{25}\), for \(q=5\), \(s=2\) and \(u=2\). This code has \(\delta _x=3>2=g(\ell ,\delta _z)\), but the classical codes used for its construction do not have better parameters than those in [44]. Therefore, the fact that the code performs better than the theoretical quantum code constructed with the best-known linear codes shows how, by considering the relative minimum distance in Theorem 5.5, we can obtain impure quantum codes with excellent performance. We also note that all the codes presented in Table 1 surpass the Gilbert-Varshamov bound for asymmetric quantum codes [38, Thm. 4].
Table 1
Parameters of the quantum codes corresponding to the pairs of codes \(C(D_u,\lambda _1 P_\infty )\), \(C(D_u,\lambda _2 P_\infty )\), with \(\lambda _2<\lambda _2\)
\((\lambda _1,\lambda _2)\) | Parameters | \(g(\ell ,\delta _z)\) |
|---|---|---|
\(q=2, s=3, u=7\) | ||
(4, 0) | \([[32,1,28/2]]_8\) | 2 |
(8, 7) | \([[32,1,24/3]]_8\) | 4 |
(11, 8) | \([[32,1,21/4]]_8^\star \) | \(4^*\) |
(15, 14) | \([[32,1,18/6]]_8^\star \) | 6 |
(19, 18) | \([[32,1,15/8]]_8^\star \) | 8 |
(23, 22) | \([[32,1,12/10]]_8^\star \) | 11 |
(7, 0) | \([[32,2,25/2]]_8\) | 2 |
(12, 8) | \([[32,2,20/4]]_8^\star \) | 5 |
(16, 14) | \([[32,2,16/5]]_8^\star \) | 6 |
(8, 0) | \([[32,3,24/2]]_8\) | 2 |
\(q=2, s=4, u=15\) | ||
(8, 0) | \([[128,1,120/2]]_{16}\) | 2 |
(16, 15) | \([[128,1,112/3]]_{16}\) | 3 |
(23, 16) | \([[128,1,105/4]]_{16}^\star \) | \(4^*\) |
(31, 30) | \([[128,1,98/6]]_{16}^\star \) | 7 |
(24, 16) | \([[128,2,104/4]]_{16}^\star \) | 4 |
(32, 30) | \([[128,2,96/5]]_{16}^\star \) | 7 |
\(q=3, s=2, u=2\) | ||
(2, 0) | \([[15,1,13/2]_{9}\) | 2 |
(4, 3) | \([[15,1,11/3]_{9}\) | 3 |
(5, 4) | \([[15,1,10/4]_{9}\) | 4 |
(6, 5) | \([[15,1,9/5]_{9}\) | 5 |
(7, 6) | \([[15,1,8/6]_{9}\) | 6 |
(8, 7) | \([[15,1,7,7]_{9}\) | 7 |
(3, 0) | \([[15,2,12/2]_{9}\) | 2 |
(5, 3) | \([[15,2,10/3]_{9}\) | 3 |
(6, 4) | \([[15,2,9/4]_{9}\) | 4 |
(7, 5) | \([[15,2,8/5]_{9}\) | 5 |
(8, 6) | \([[15,2,7/6]_{9}\) | 6 |
(4, 0) | \([[15,3,11/2]_{9}\) | 2 |
(6, 3) | \([[15,3,9/3]_{9}\) | 3 |
(7, 4) | \([[15,3,8/4]_{9}\) | 4 |
(8, 5) | \([[15,3,7/5]_{9}\) | 5 |
(9, 6) | \([[15,3,6/6]_{9}\) | 6 |
\(q=5, s=2, u=2\) | ||
(2, 0) | \([[45,1,43/2]]_{25}\) | 2 |
(4, 2) | \([[45,1,41/3]]_{25}^\star \) | 2 |
(6, 5) | \([[45,1,39/4]]_{25}\) | 4 |
(8, 7) | \([[45,1,37/5]]_{25}\) | 5 |
(9, 8) | \([[45,1,36/6]]_{25}\) | 6 |
(10, 9) | \([[45,1,35/7]]_{25}\) | 7 |
(4, 0) | \([[45,2,41/2]]_{25}\) | 2 |
(7, 5) | \([[45,2,38/4]]_{25}\) | 4 |
(8, 6) | \([[45,2,36/5]]_{25}\) | 5 |
(9, 7) | \([[45,2,35/6]]_{25}\) | 6 |
(5, 0) | \([[45,3,40/2]]_{25}\) | 2 |
(8, 5) | \([[45,3,37/4]]_{25}\) | 4 |
(10, 7) | \([[45,3,35/5]]_{25}\) | 5 |
\(q=5, s=2, u=3\) | ||
(3, 0) | \([[65,1,62/2]]_{25}\) | \(2^*\) |
(6, 5) | \([[65,1,59/3]]_{25}\) | 2 |
(8, 6) | \([[65,1,57/4]]_{25}^\star \) | 4 |
(11, 10) | \([[65,1,54/6]]_{25}^\star \) | 6 |
(14, 13) | \([[65,1,51/8]]_{25}\) | 7 |
(16, 15) | \([[65,1,49/9]]_{25}\) | 9 |
(5, 0) | \([[65,2,60/2]]_{25}\) | − |
(8, 5) | \([[65,2,57/3]]_{25}\) | 3 |
(9, 6) | \([[65,2,56/4]]_{25}^\star \) | 4 |
(12, 10) | \([[65,2,53/5]]_{25}\) | 6 |
(14, 12) | \([[65,2,51/6]]_{25}\) | 6 |
(15, 13) | \([[65,2,50/8]]_{25}\) | 7 |
(6, 0) | \([[65,3,59/2]]_{25}\) | − |
(9, 5) | \([[65,3,56/3]]_{25}\) | 3 |
(13, 10) | \([[65,3,52/5]]_{25}\) | 6 |
(15, 12) | \([[65,3,50/6]]_{25}\) | 6 |
(16, 13) | \([[65,3,49/8]]_{25}\) | 7 |
6 Future work
Similarly to Sect. 4, it would be interesting to study how to construct the set of monomials that gives the maximum value of \(\Delta ^*\) for one-point algebraic geometry codes over the extended norm-trace curve. Similarly, another research direction would be to generalize these techniques for other families of curves and, more generally, different families of decreasing evaluation codes.
Declarations
Competing interests
The authors declare no competing interests.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
