1 Introduction
Determination of parameters of Reed–Muller type codes has received a lot of attention from several mathematicians in recent past. In this paper, we look at a certain class of codes, called the affine Cartesian codes, that comes naturally as a generalization of Reed–Muller Codes. These codes were introduced in 2013 by Geil and Thomsen [12] in a more general setting of weighted Reed–Muller codes. The name “affine Cartesian codes” was coined by López et al. [17] in 2014. Since then several articles have appeared where the parameters of these codes were studied extensively. Like in the case of Reed–Muller codes, the problem of computing parameters such as minimum distance, generalized Hamming weights etc., of affine Cartesian codes translates to the problem of determination of the maximum number of common zeroes of systems of polynomials satisfying certain properties in a subset of an affine space over a finite field. The fundamental properties of affine Cartesian codes, such as their dimensions and the minimum distances, were obtained in [17]. Later in 2018, the generalized Hamming weights [1] of the affine Cartesian codes were completely determined. This generalizes the classical work [15] of Heijnen and Pellikaan towards the determination of all the generalized Hamming weights of the Reed–Muller codes. Several articles, for example [3, 4], are devoted towards the determination of the next to minimal weights of affine Cartesian codes.
The notion of generalized Hamming weights of a code was introduced by Wei [21] in 1991 in order to characterize the code performance of on a wire tap channel of type II. A generalization of these weights is known as the relative generalized Hamming weight of a code \(C_1\) with respect to a proper subcode \(C_2\). This notion was introduced by Luo et al. [18], again towards studying new characters on the wire tap channel of type II, in 2005 and was further studied in a subsequent article [16] by Liu et al. For the definition of the relative generalized Hamming weights of linear codes we refer to Sect. 2.1.
Anzeige
As the title of the article indicates, we are interested in determining the relative generalized Hamming weights of an affine Cartesian code with respect to a subcode which is again an affine Cartesian code. This work generalizes the result in the article [11] where the authors have determined all the relative generalized Hamming weights of the Reed–Muller codes. Also, the main results of the current article can be viewed as a generalization of the result in [1] which gives all the generalized Hamming weights of affine Cartesian codes. In proving our result in this paper, we follow the footsteps of [1] and [11], where the results were derived using the notion of the so-called footprint bound. Some early articles on footprint bounds include [8, 10, 14] and some recent articles include [2, 13, 20] among others. A somewhat brief discussion of the notion of the footprint bounds is given in Sect. 2.3.
The paper is organized as follows. In Sect. 2, we recall most of the definitions and the known results that will be used in proving our main theorem. In Sect. 3, we deduce Theorem 3.7, which can be viewed as an extension of the famous Kruskal–Katona Theorem in extremal combinatorics. Finally, in Sect. 4, we state and prove the main result of the paper where we compute all the relative generalized Hamming weights of an affine Cartesian code with respect to a smaller affine Cartesian code.
2 Preliminaries
We devote this section to recalling the well-known definitions and results that will be used in the sequel. In particular, we recall the definitions of relative generalized Hamming weights of a code with respect to a smaller subcode and the notion of affine Cartesian codes in the following two subsections. Later, we revisit the notion of the so called footprint bound which helps us in translating the algebraic geometric problem of determination of the maximum number of common zeroes of certain systems of polynomials in a specified subset of the affine space over a projective space into a seemingly different problem in extremal combinatorics. We will conclude this section by introducing some combinatorial notations which will be used in the next section. In particular, none of the results or definitions mentioned in this section are new. For more detailed description of the results that are mentioned here a reader is encouraged to see the references mentioned and the references therein.
2.1 Relative generalized Hamming weights of linear codes
We begin this subsection by recalling the definition of the relative generalized Hamming weights of a code with respect to a proper subcode. Throughout, we will denote by \({\mathbb F}_q\) a finite field with q elements where q is a prime power.
Anzeige
Definition 2.1
[16, Definition 2] Let \(C_2 \subsetneq C_1\) be linear codes and \(\ell := \dim C_1 - \dim C_2\). For \(r = 1, \ldots , \ell \), the r-th relative generalized Hamming weights of \(C_1\) with respect to \(C_2\) (RGHW of \(C_1\) w.r.t. \(C_2\)) is defined aswhere \((C_i)_J = \{c = (c_1, \ldots , c_n) \in C_i \mid c_t =0 \ \text {for} \ t \notin J\}\) for \(i = 1, 2\). The sequence \((M_1 (C_1, C_2), \ldots , M_{\ell } (C_1, C_2))\) is known as the hierarchy of RGHWs of \(C_1\) w.r.t. \(C_2\).
$$\begin{aligned} M_r (C_1, C_2) := \min _{J \subseteq \{1, \ldots , n\}} \{ |J| : \dim ((C_1)_J) - \dim ((C_2)_J) = r \}, \end{aligned}$$
The following Lemma, which can be found as [16, Lemma 1], gives an alternative definition of the RGHWs of a code \(C_1\) w.r.t. a proper subcode \(C_2\).
Lemma 2.2
[16, Lemma 1] Let \(C_2 \subsetneq C_1\) be linear codes and \(\ell = \dim C_1 - \dim C_2\). For \(r = 1, \ldots , \ell \), we havewhere, given a subspace D of \({\mathbb F}_q^n\), the support of D, denoted by \(\mathrm {Supp}(D)\), is given by
$$\begin{aligned} M_r (C_1, C_2) = \min \left\{ |\mathrm {Supp}(D)| : D \subset C_1; D \cap C_2 = \{0\}, \dim D = r\right\} , \end{aligned}$$
(1)
$$\begin{aligned} \mathrm {Supp}(D) := \left\{ i \in \{1, \ldots , n\} \mid c_i \ne 0 \ \text {for some} \ (c_1, \ldots , c_n) \in D \right\} . \end{aligned}$$
In what follows, we will use the Eq. (1) as our definition of the RGHWs.
Remark 2.3
In view of Lemma 2.2, it is clear that if \(C_2 = \{0\}\), then the RGHWs of \(C_1\) w.r.t. \(C_2\) are exactly the generalized Hamming weights of \(C_1\).
2.2 Affine Cartesian codes
In this subsection, we recall the definition of the affine Cartesian codes. Throughout, we will use the convention that the degree of the zero polynomial is \(-1\).
Definition 2.4
Let \(d_1 \le \ldots \le d_m\) be positive integers and \(A_1, \ldots , A_m\) are subsets of \({\mathbb F}_q\) with cardinalities \(d_1, \ldots , d_m\) respectively. Denote by \(\mathcal {A}\) the cartesian product \(\mathcal {A}:=A_1 \times \cdots \times A_m\). Note that \(|\mathcal {A}| = n:= d_1 \cdots d_m\). Further, fix an enumeration \(P_1, \ldots , P_n\) of elements in \(\mathcal {A}\) and a positive integer \(d \le k:=\sum _{i=1}^m (d_i - 1).\) For \(d \le k\), define the subspaceThe mapis a linear map and consequently, for each \(d \le k\), the image \(AC_q (d, \mathcal {A}) := \mathrm {ev}({S_{\le d}}(\mathcal {A}))\) is a linear subspace of \({\mathbb F}_q^n\) and is called an affine cartesian code.
$$\begin{aligned} S_{\le d}{(\mathcal {A})} := \{f \in {\mathbb F}_q[x_1, \ldots , x_m] : \deg _{x_i} f \le d_i -1 \ \mathrm {and} \ \deg f \le d\}. \end{aligned}$$
$$\begin{aligned} \mathrm {ev}: S_{\le k} (\mathcal {A}) \rightarrow {\mathbb F}_q^{|{\mathcal {A}}|} \ \ \ \mathrm {by} \ \ \ \ f \mapsto (f(P_1), \ldots , f(P_n)) \end{aligned}$$
Henceforth, we will write \(A_i := \{{\gamma }_{i, 1}, \ldots , {\gamma }_{i, d_i}\}\) for \(i = 1, \ldots , m\). It is not hard to show that the map \(\mathrm {ev}\) is injective. This implies that the dimension of \(AC_q (d, {{\mathcal {A}}})\) is the same as \(\dim S_{\le d}(\mathcal {A})\). As mentioned in the introduction, we are interested in the determination of the RGHWs of an affine Cartesian code w.r.t. a “smaller” affine Cartesian code. More precisely, our goal is to answer the following:
Question 2.5
Let \(u_1, u_2\) be integers satisfying \(-1 \le u_2 < u_1 \le k\). Determine \(M_r (AC_q (u_1, \mathcal {A}), AC_q (u_2, \mathcal {A}))\), for \(r \le \dim AC_q (u_1, \mathcal {A}) - \dim AC_q (u_2, \mathcal {A})\).
To simplify notations, we will denote \(M_r(u_1, u_2):=M_r (AC_q (u_1, \mathcal {A}), AC_q (u_2, \mathcal {A}))\) and \(\ell :=\dim AC_q (u_1, \mathcal {A}) - \dim AC_q (u_2, \mathcal {A})\). We note that if \(u_2 = -1\), then \(M_r (u_1, u_2)\) are simply the r-th generalized Hamming weights of \(AC_q (u_1, \mathcal {A})\). In the recent work [1], the generalized Hamming weights of affine Cartesian codes were completely determined. To answer the above question we introduce the following sets. For an integer \(r \le \ell \), we define,We endow the set of monomials in \({\mathbb F}_q[x_1, \ldots , x_m]\) with the graded lexicographic order. In the following Lemma we give a necessary and sufficient condition for a subspace of \(AC_q (u_1, \mathcal {A})\) to be a member of \(\mathcal {D}_r\).
$$\begin{aligned} \mathcal {D}_r := \{D \subset AC_q (u_1, \mathcal {A}) \mid D \cap AC_q (u_2, \mathcal {A}) = 0; \dim D = r\}. \end{aligned}$$
Lemma 2.6
Let D be a subspace of \(AC_q (u_1, \mathcal {A})\) of dimension r. Then \(D \in \mathcal {D}_r\) iff there exists \(f_1, \ldots , f_r \in S_{\le k}({{\mathcal {A}}})\) with \(D = \mathrm {Span}\{\mathrm {ev}(f_1), \ldots , \mathrm {ev}(f_r)\}\) satisfying the following three conditions: Consequently, \(|\mathrm {Supp}(D)| = n - |{{\mathsf {Z}}}_{\mathcal {A}} (f_1, \ldots , f_r)|,\) where \({{\mathsf {Z}}}_{{\mathcal {A}}}(f_1, \ldots , f_r)\) denotes the set of common zeroes of \(f_1, \ldots , f_r \in {{\mathcal {A}}}\).
(C1)
\(f_1, \ldots , f_r\) are linearly independent,
(C2)
\(u_2 < \deg {\mathsf {L}}{\mathsf {T}}(f_i) \le u_1\) for \(i = 1, \ldots , r\),
(C3)
\({\mathsf {L}}{\mathsf {T}}(f_i) \ne {\mathsf {L}}{\mathsf {T}}(f_j)\) whenever \(i \ne j\).
Proof
It is easy to see that the three conditions are sufficient. To see that they are also necessary, we begin with \(D \in \mathcal {D}_r\), and a set of r linearly independent polynomials \(f_1, \ldots , f_r\) such that \(D = \mathrm {Span}\{\mathrm {ev}(f_1), \ldots , \mathrm {ev}(f_r)\}\). It is clear that the polynomial \(f_1\) satisfies the condition (C2). For \(2 \le s \le r\), we replace \(f_s\) by a linear combination of \(f_1, \ldots , f_s\) so that the polynomials \(f_1, \ldots , f_s\) satisfy the condition (C3). Clearly the condition (C2) is satisfied for \(f_1, \ldots , f_r\). The last assertion follows trivially. \(\square \)
We now define the following family consisting of sets of r polynomials:It follows directly from Lemma 2.6 thatWe have thus shown that the Question 2.5 is equivalent to the following question:
$$\begin{aligned} \mathcal {C}_r := \{\{f_1, \ldots , f_r \} \mid f_1, \ldots , f_r \ \text {satisfy (C1), (C2), (C3)}\}. \end{aligned}$$
$$\begin{aligned} M_r (u_1, u_2) = n - \max \{|{{\mathsf {Z}}}_{\mathcal {A}} (f_1, \ldots , f_r)| : \{f_1, \ldots , f_r \} \in \mathcal {C}_r\}. \end{aligned}$$
(2)
Question 2.7
For integers \(r, u_1, u_2\) and the set \({{\mathcal {A}}}\) as above, determine
$$\begin{aligned} a_r (u_1, u_2, \mathcal {A}) := \max \{|{{\mathsf {Z}}}_{\mathcal {A}} (f_1, \ldots , f_r)| : \{f_1, \ldots , f_r \} \in \mathcal {C}_r\}. \end{aligned}$$
2.3 The footprint bound
In order to answer Question 2.7 we will use the footprint bound. This method of producing upper bounds on generalized Hamming weights of Reed–Muller type codes is dependent on the theory of Gröbner bases and that of affine Hilbert functions. For a comprehensive reading on these notions, the reader is referred to [7]. Most of what follows in this section can be found in [1, Sect. 2]. We provide a somewhat detailed description of what will be used later for the sake of completeness.
Let us denote by S the polynomial ring \({\mathbb F}_q[x_1, \ldots , x_m]\) and for any integer u we define \(S_{\le u} :=\{f \in S \mid \deg f \le u \}.\) For any ideal I of S, we define \(I_{\le u} := I \cap S_{\le u}\). The affine Hilbert function of I, denoted by \(^a {\mathsf {H}}{\mathsf {F}}_I\), is defined asIt is easy to derive that if I and J are ideals of S with \(I \subset J\), then for any \(u \in {\mathbb Z}\) we have \(^a {\mathsf {H}}{\mathsf {F}}_J(u) \le ^a {\mathsf {H}}{\mathsf {F}}_I (u)\). For a subset \(X \subset {\mathbb F}_q^m\) we define the ideal I(X) to be the ideal of S consisting of polynomials vanishing everywhere in X. For such a subset \(X \subset {\mathbb F}_q^m\), we define its affine Hilbert function, denoted by \(^a {\mathsf {H}}{\mathsf {F}}_X\), as \(^a {\mathsf {H}}{\mathsf {F}}_X := ^a{\mathsf {H}}{\mathsf {F}}_{I(X)}\).
$$\begin{aligned} {}^a{\mathsf {H}}{\mathsf {F}}_I : {\mathbb Z}\rightarrow {\mathbb Z}\ \ \ \ \text {given by} \ \ \ \ ^a{\mathsf {H}}{\mathsf {F}}_I (u) := \dim S_{\le u} - \dim I_{\le u}. \end{aligned}$$
Proposition 2.8
(a)
[7, Sect. 9.3] Let \(\prec \) be any graded order on S. Then
(i)
For any ideal I of S, we have \(^a{\mathsf {H}}{\mathsf {F}}_{{\mathsf {L}}{\mathsf {T}}(I)} (u) = ^a{\mathsf {H}}{\mathsf {F}}_I (u)\).
(ii)
If I is a monomial ideal of S, then \(^a{\mathsf {H}}{\mathsf {F}}_I(u)\) is given by the number of monomials of degree at most u that do not lie in I.
(b)
[19, Lemma 2.1] If \(Y \subset {\mathbb F}_q^m\) is a finite set, then \(|Y| = ^a {\mathsf {H}}{\mathsf {F}}_Y (u)\) for all sufficiently large values of u.
Similar statements as in the above proposition could also be found, albeit in disguise of footprints, in [9, Corollary 4.5] and in [6, Corollary 2.5]. The above Proposition helps us in finding out an upper bound for the quantity \(|{{\mathsf {Z}}}_{\mathcal {A}} (f_1, \ldots , f_r)|\) for a given \(\{f_1, \ldots , f_r \} \in \mathcal {C}_r\). To this end, we see that the polynomials \(g_1, \ldots , g_m \in I(Z_{{{\mathcal {A}}}} (f_1, \ldots , f_r))\), whereAt this juncture, it will be useful to assign some notations for the ideals in question. DefineFurthermore, we have the monomial ideals:It follows trivially from the above discussions that, \(\mathcal {J} \subset \mathcal {I}\) and thatUsing Proposition 2.8 and Eq. (3) we see that for sufficiently large u,Let us write \({{\mathsf {M}}}= \{\mu \in S \ | \ \mu \ \text {is a monomial} \}\). It follows from from Proposition 2.8 (a) (ii) thatFurthermore, if we take \(u \ge \sum _{i=1}^m d_i\), thenWe defineand given any set of monomials \(m_1, \ldots , m_r\), the set of footprints,The previous discussions now imply thatThe upper bound on the number of points on \(Z_{{{\mathcal {A}}}} (f_1, \ldots , f_r)\) thus obtained from Eq. (5) is referred to as the footprint bound. Indeed,In the following subsection, we will introduce some combinatorial notions which will help us to derive the right hand side of the Eq. (6).
$$\begin{aligned} g_j := \prod _{s=1}^{d_j} (x_j - {\gamma }_{j, s}) \ \ \ \ \text {for} \ \ \ \ j = 1, \ldots , m. \end{aligned}$$
$$\begin{aligned} \mathcal {I} := I(Z_{{{\mathcal {A}}}} (f_1, \ldots , f_r)) \ \ \ \text {and} \ \ \ {\mathsf {L}}{\mathsf {T}}(\mathcal {I}):= \ \text {the leading term ideal of} \ \mathcal {I}. \end{aligned}$$
$$\begin{aligned} \mathcal {J} := \langle f_1, \ldots , f_r, g_1, \ldots , g_m \rangle \ \ \ \text {and} \ \ \ \ \mathcal {J}_{\mathsf {Mon}}:= \langle {\mathsf {L}}{\mathsf {T}}(f_1), \ldots , {\mathsf {L}}{\mathsf {T}}(f_r), x_1^{d_1}, \ldots , x_m^{d_m}\rangle . \end{aligned}$$
$$\begin{aligned} \mathcal {J}_{\mathsf {Mon}}\subseteq {\mathsf {L}}{\mathsf {T}}(\mathcal {J}) \subseteq {\mathsf {L}}{\mathsf {T}}(\mathcal {I}). \end{aligned}$$
(3)
$$\begin{aligned} |{{\mathsf {Z}}}_{{{\mathcal {A}}}} (f_1, \ldots , f_r)| = ^a{\mathsf {H}}{\mathsf {F}}_{\mathcal {I}} (u) = ^a{\mathsf {H}}{\mathsf {F}}_{{\mathsf {L}}{\mathsf {T}}(\mathcal {I})} (u) \le ^a{\mathsf {H}}{\mathsf {F}}_{\mathcal {J}_{\mathsf {Mon}}} (u). \end{aligned}$$
(4)
$$\begin{aligned} {}^a{\mathsf {H}}{\mathsf {F}}_{\mathcal {J}_{\mathsf {Mon}}} (u) = |\{\mu \in {{\mathsf {M}}}: \deg \mu \le u, x_i^{d_i} \not \mid \mu , {\mathsf {L}}{\mathsf {T}}(f_j) \not \mid \mu \ \text {for} \ i = 1, \ldots , m \ \text {and} \ j=1, \ldots , r\}|. \end{aligned}$$
$$\begin{aligned} {}^a{\mathsf {H}}{\mathsf {F}}_{\mathcal {J}_{\mathsf {Mon}}} (u) = |\{\mu \in {{\mathsf {M}}}: \deg _{x_i} \mu \le d_i - 1, {\mathsf {L}}{\mathsf {T}}(f_j) \not \mid \mu \ \text {for} \ i = 1, \ldots , m \ \text {and} \ j=1, \ldots , r\}|. \end{aligned}$$
$$\begin{aligned}{{\mathsf {M}}}_{{{\mathcal {A}}}} := \{\mu \in {{\mathsf {M}}}\mid \deg _{x_i} \mu \le d_i -1 \ \text {for} \ i=1, \ldots , m \},\end{aligned}$$
$$\begin{aligned} {{\mathsf {F}}{\mathsf {P}}}_{{\mathcal {A}}}(m_1, \ldots , m_r) := \{\mu \in {{\mathsf {M}}}_{{\mathcal {A}}}: m_i \not \mid \mu \ \text {for} \ i=1, \ldots , r\}. \end{aligned}$$
$$\begin{aligned} |{{\mathsf {Z}}}_{{{\mathcal {A}}}} (f_1, \ldots , f_r)| \le |{{\mathsf {F}}{\mathsf {P}}}_{{\mathcal {A}}}({\mathsf {L}}{\mathsf {T}}(f_1), \ldots , {\mathsf {L}}{\mathsf {T}}(f_r))|. \end{aligned}$$
(5)
$$\begin{aligned} a_r (u_1, u_2, {{\mathcal {A}}}) \le \max \left\{ |{{\mathsf {F}}{\mathsf {P}}}_{{\mathcal {A}}}({\mathsf {L}}{\mathsf {T}}(f_1), \ldots , {\mathsf {L}}{\mathsf {T}}(f_r))| : \{f_1, \ldots , f_r\} \in \mathcal {C}_r\right\} . \end{aligned}$$
(6)
2.4 Some combinatorial tools
In this subsection, we will introduce some combinatorial notions that will help us to translate the problem of determining the right hand side of the Eq. (6) to a problem of extremal combinatorics. LetWe have two natural orderings for the elements of F, namely the lexicographic order and the partial order. Let us writeif \((a_1, \ldots , a_m)\) is less than \((b_1, \ldots , b_m)\) in lexicographic order, i.e. there exists j with \(1 \le j \le m\) such that \(a_i = b_i\) for all \(i < j\) and \(a_j < b_j\). Also we will writeif and only if \((a_1, \ldots , a_m)\) is less than \((b_1, \ldots , b_m)\) in partial order, i.e. \(a_i \le b_i\) for all \(i = 1, \ldots , m\) and for some \(j \in \{1, \ldots , n\}\) we have \(a_j < b_j\).We write \((a_1, \ldots , a_m) \preceq _{lex} (b_1, \ldots , b_m)\) (resp. \((a_1, \ldots , a_m) \preceq _{P} (b_1, \ldots , b_m)\)) if \((a_1, \ldots , a_m) \prec _{lex} (b_1, \ldots , b_m)\) (resp. \((a_1, \ldots , a_m) \prec _{P} (b_1, \ldots , b_m)\)) or \((a_1, \ldots , a_m) = (b_1, \ldots , b_m)\). We have a bijectionIt is clear that for \(\mu _1, \mu _2 \in {{\mathsf {M}}}_{{\mathcal {A}}}\), we have \(\mu _1 \mid \mu _2\) if and only if \(\phi (\mu _1) \preceq _P \phi (\mu _2)\). Now for \(\mathbf{a} = (a_1, \ldots , a_m) \in F\), we define \(\deg (\mathbf{a} ):=a_1+\cdots +a_m\). Let us introduce some subsets of F consisting of elements satisfying certain degree constraints: for any integer u, defineOn a similar note, for integers \(u_1, u_2\) satisfying \(u_2 < u_1\), we defineGiven a subset \(S \subset F\), we define the shadow (resp. footprint) of S in F, denoted by \(\nabla (S)\) (resp. \(\Delta (S)\)) as follows:For an integer u, we define \(\Delta _u (S) := \Delta (S) \cap F_u\) and \(\nabla _u (S) := \nabla (S) \cap F_u\). It now follows from Eq. (6) thatIn the subsequent section, we will derive the exact value of the right hand side in the above inequality. Before concluding this section, we remark that the field \({\mathbb F}_q\) does not play an essential role as long as we are interested in computing the quantity \(a_r (u_1, u_2, {{\mathcal {A}}})\). The inequalities (6) and (7) continue to hold even if we replace \({\mathbb F}_q\) by an arbitrary field having at least \(d_m\) elements.
$$\begin{aligned} F = \{0,\ldots , d_1 - 1\} \times \cdots \times \{0, \ldots , d_m - 1\}. \end{aligned}$$
$$\begin{aligned} (a_1, \ldots , a_m) \prec _{lex} (b_1, \ldots , b_m) \end{aligned}$$
$$\begin{aligned}(a_1, \ldots , a_m) \prec _{P} (b_1, \ldots , b_m)\end{aligned}$$
$$\begin{aligned} \phi : {{\mathsf {M}}}_{{\mathcal {A}}}\rightarrow F \ \ \text {given by} \ \ x_1^{a_1} \cdots x_m^{a_m} \mapsto (a_1, \ldots , a_m). \end{aligned}$$
$$\begin{aligned} F_u := \{\mathbf{a } \in F : \deg (\mathbf{a }) = u\} \ \ \ \text {and} \ \ \ F_{\le u} := \{\mathbf{a } \in F : \deg (\mathbf{a }) \le u\}. \end{aligned}$$
$$\begin{aligned} F_{u_2}^{u_1} := \{\mathbf{a } \in F : u_2 < \deg (\mathbf{a }) \le u_1\}. \end{aligned}$$
$$\begin{aligned} \nabla (S) := \{ \mathbf{b} \in F \mid \mathbf{a} \preceq _P \mathbf{b} \ \text {for some} \ \mathbf{a} \in S\} \ \ \text {and} \ \ \Delta (S) := F \setminus \nabla (S). \end{aligned}$$
$$\begin{aligned} a_r (u_1, u_2, {{\mathcal {A}}}) \le \max \{|\Delta (S)| : S \subset F_{u_2}^{u_1}, |S| = r\}. \end{aligned}$$
(7)
3 Result from combinatorics
Motivated from the discussion in the last section, we now investigate the following question.
Question 3.1
Fix integers \(u_1, u_2\) and r with \(-1 \le u_2 < u_1 \le k\). Denote by \(\mathcal {F}_r\), the family of subsets of \(F_{u_2}^{u_1}\) of cardinality r. Determine \(\max \{|\Delta (S)| : S \in \mathcal {F}_r\}.\)
We remark that if \(d_1 = d_2 = \cdots = d_m = q\), then the answer to this question is known in various cases: Furthermore, in the general situation with \(d_1 \le \cdots \le d_m\), this problem was solved in [1] in the case \(u_2 = -1\) in order to determine the GHWs of the affine Cartesian codes. In order to proceed, we first introduce the following two notations: The following classical Theorem, due to Clements and Lindström, will play an instrumental role in the sequel.
(1)
for \(u_2 = -1\), this question corresponds to the determination of the GHWs of the Reed–Muller codes, which was solved by Heijnen and Pellikaan in [15].
(2)
in general, without any constraint on \(u_2\), the question corresponds to the determination of the RGHWs of the Reed–Muller codes, and as mentioned before, this question was answered by Geil and Martin in [11].
(a)
For and integer u and a subset \(S \subset F_u\), we define L(S) to be the set consisting of the first |S| elements of \(F_u\) in descending lexicographic order.
(b)
For integers \(u_1, u_2\) with \(-1 \le u_2 < u_1 \le k \) and a subset \(S \subset F_{u_2}^{u_1}\), we define N(S) to be the set consisting of the first |S| elements of \(F_{u_2}^{u_1}\) in descending lexicographic order.
Theorem 3.2
[5, Corollary 1] Let \(u < k\) and \(S \subseteq F_u\). Then
$$\begin{aligned}\nabla _{u+1} (L(S)) \subseteq L (\nabla _{u+1} (S)).\end{aligned}$$
The following is an easy corollary of the Theorem 3.2.
Corollary 3.3
In order to prove our main results, we will also need the following lemma that can be found in [1, Lemma 3.4 and Remark 3.5].
Lemma 3.4
Fix integers u, v with \(u < v \le k\) and an element \(\mathbf{y} \in F_v\). If \(\mathbf{a} _\mathbf{y }:= \max _{lex} \{\mathbf{f } \in F_u : \mathbf{f } \le _{lex} \mathbf{y }\}\), then \(\mathbf{a }_\mathbf{y } \preceq _P \mathbf{y }\).
The following two lemmas are motivated from their analogues [1, Lemmas 3.6 and 3.7]. We include the proofs for the sake of completeness.
Lemma 3.5
Let \(u, u_1, u_2\) be integers satisfying \(-1 \le u_2 < u \le u_1 \le k\). Let N(r) denote the first r elements of \(F_{u_2}^{u_1}\) in descending lexicographic order. If \(N_u := N(r) \cap F_u\) and \(r_u := |N_u|\), thenwhere \(N_u^*\) consists of the first \(r_u+1\) elements of \(F_u\) in descending lexicographic order.
$$\begin{aligned}\nabla _{u_1} (N_u) \subseteq N_{u_1} \subseteq \nabla _{u_1} (N_u^*), \end{aligned}$$
Proof
The result is trivially true if \(u = u_1\). So we may assume that \(u < u_1\). Let \(\mathbf{y} \in \nabla _{u_1} (N_u)\). Then there exists \(\mathbf{x} \in N_u\) such that \(\mathbf{x} \preceq _P \mathbf{y} \). Consequently \(\mathbf{x} \preceq _{lex} \mathbf{y} \). Since \(\mathbf{x} \in N(r)\) and \(\mathbf{x} \preceq _{lex} \mathbf{y} \), we have \(\mathbf{y} \in N(r)\). Since \(\mathbf{y} \in F_{u_1}\), we have \(\mathbf{y} \in N(r) \cap F_{u_1} = N_{u_1}\).
Now let \(\mathbf{y} \in N_{u_1}\). Define \(\mathbf{a }:= \max _{lex} \{\mathbf{f } \in F_u : \mathbf{f } \preceq _{lex} \mathbf{y }\}\). From Lemma 3.4, we obtain \(\mathbf{a} \le _P \mathbf{y} \). If \(\mathbf{a} \in N_u\), then \(\mathbf{a} \in N_{u}^*\), which proves the assertion. So we may assume that \(\mathbf{a} \not \in N_u\). Clearly, the set \(N_u\) consists of the first \(r_u\) elements of \(F_u\) in descending lexicographic order. If we write \(N_{u}^* =\{ \mathbf{f} _1, \ldots , \mathbf{f} _{r_u + 1}\}\), then \(\mathbf{a} \preceq _{lex} \mathbf{f} _{r_u + 1}\). If \(\mathbf{a} = \mathbf{f} _{r_u + 1}\), then \(\mathbf{a} \in N_u^*\), and the assertion follows. Now suppose, if possible, that \(\mathbf{a} \prec _{lex} \mathbf{f} _{r_u + 1}\). The maximality of \(\mathbf{a} \) implies that \(\mathbf{y} \prec _{lex} \mathbf{f} _{r_u + 1}\). Since \(\mathbf{y} \in N(r)\), it follows that \(\mathbf{f} _{r_u + 1} \in N(r)\) and hence \(\mathbf{f} _{r_u + 1} \in N_u\). This contradicts \(|N_u| = r_u\). This completes the proof. \(\square \)
Lemma 3.6
With notations as in Lemma 3.5 and \(u_2 < u_1 - 1,\) we have
$$\begin{aligned}|\nabla (N(r))| = r - |N_{u_1}| + |\nabla (N_{u_1})|.\end{aligned}$$
Proof
It follows from Lemma 3.5 that,This implies,Note that, \(N(r) \setminus N_{u_1}\) consists of the first \(r - |N_{u_1}|\) elements of \(F_{u_2}^{u_1 - 1}\) in descending lexicographic order. We obtain by applying (8) to \(N(r) \setminus N_{u_1}\) (on \(F_{u_2}^{u_1 - 1}\)) that \(\nabla _{u_1-1} (N(r) \setminus N_{u_1})) \subset N_{u_1-1}\). Also, \(N_{u_1 - 1} \subset N(r) \setminus N_{u_1}\). This implies that \(\nabla _{u_1-1} (N(r) \setminus N_{u_1}) = N_{u_1-1}\). Repeating the argument iteratively we deduce that,Consequently, \(\nabla (N(r) \setminus N_{u_1}) \cap F_{<u_1} = N(r) \setminus N_{u_1}\), which proves the lemma. \(\square \)
$$\begin{aligned} \bigcup _{u_2 < u \le u_1} \nabla _{u_1} (N_u) \subset N_{u_1}. \end{aligned}$$
(8)
$$\begin{aligned} |\nabla (N(r))|&= |\nabla (N(r)) \cap F_{<u_1}| + |\nabla (N(r)) \cap F_{\ge u_1}| \\&= |\nabla (N(r) \setminus N_{u_1}) \cap F_{<u_1}| + |\nabla (N_{u_1})|. \end{aligned}$$
$$\begin{aligned} \nabla _{u} (N(r) \setminus N_{u_1}) = N_{u} \ \ \ \text {for all} \ \ \ u_2 < u \le u_1-1. \end{aligned}$$
We are now ready to state and prove the main theorem of this section. This is a generalization of [1, Theorem 3.8]. Further special cases, when \(d_1 = \cdots = d_m = q\), appear as [21, Lemma 6], [15, Theorem 5.7] and [11, Lemma 4.6].
Theorem 3.7
Let \(u_1, u_2, u, r\) be integers with \(-1 \le u_2 < u_1 \le k\) and let \(S \subseteq F_{u_2}^{u_1}\) with \(|S| = r\). Then \(|\nabla (N (r))| \le |\nabla (S)|\). In particular, given any \(S \in \mathcal {F}_r\), we have \(|\Delta (S)| \le |\Delta (N(r))|\). Consequently,
$$\begin{aligned}|\Delta (N(r)| = \max \{|\Delta (S)| : S \in \mathcal {F}_r \}.\end{aligned}$$
Proof
For \(u_2 < u \le u_1\), define \(S_u := S \cap F_u\) and \(N_u := N(r) \cap F_u\). When \(u_2 = u_1 - 1\), then the assertion follows directly from Corollary 3.3 (b). Henceforth, we will always assume that \(u_2 < u_1 - 1.\) We distinguish the proof in two cases:
Case 1: Suppose that \(|S_{u_1}| \ge r_{u_1}\). Then \(|S_{u_1}| = r_{u_1} + \alpha \) for some \(\alpha \ge 0\). We may write \(S_{u_1} = S' \cup S''\), where \(S'\) denotes the first \(r_{u_1}\) elements of S in descending lexicographic order and \(S'' = S \setminus S'\). It follows easily that \(|S''| = \alpha \) and that \(S''\) is disjoint from \(\nabla (S)\) and \(\nabla (N_{u_1})\). By applying Corollary 3.3 (b) to \(S'\), we see that \(|\nabla (S')| \ge |\nabla (N_{u_1})|\). This shows that \(|\nabla (S_{u_1})| \ge |\nabla (N_{u_1})| + \alpha \). We note that,This givesThe last equality follows from Lemma 3.6 and the proof is complete in this case. Case 2: Now suppose that \(|S_{u_1}|< r_{u_1}\). Since \(|S|=r=|N(r)|\), there exists and integer u with \(u_2< u <{u_1}\) such that \(|S_u|>|N_u|\) and consequently, \(|N_u^*| \le |S_u|\). By Lemma 3.5 and Corollary 3.3 (a) we have \(|N_{u_1}| \le |\nabla _{u_1}(N_u^*)| \le |\nabla _{u_1}(S_u)|.\) Thus,The inequality \(|\nabla (\nabla _{u_1}(S_u))| \ge |\nabla (N_{u_1})|\) follows from Corollary 3.3 (b) and the last equality follows from Lemma 3.6. The last two assertions are now obvious. \(\square \)
$$\begin{aligned} |\nabla (S)|&= |\nabla _{<u_1} (S)| + |\nabla _{\ge u_1}(S)| \nonumber \\&\ge |\nabla _{<u_1} (S)| + |\nabla (S_{u_1})| \nonumber \\&\ge |S \cap F_{<u_1}| + |\nabla (S_{u_1})| \nonumber \\&= r - |S_{u_1}| + |\nabla (S_{u_1})|. \end{aligned}$$
(9)
$$\begin{aligned} |\nabla (S)| \ge r - |S_{u_1}| + |\nabla (S_{u_1})| \ge r - r_{u_1} - \alpha + |\nabla (N_{u_1})| + \alpha = |\nabla (N(S))|. \end{aligned}$$
$$\begin{aligned} |\nabla (S)|&\ge r-|S_{u_1}|+|\nabla _{\ge {u_1}}(S)| \ \ \ \ \ (\text {follows from (9)})\\&> r - |N_{u_1}|+|\nabla _{\ge {u_1}}(S_u)| \\&= r - |N_{u_1}|+|\nabla (\nabla _{u_1}(S_u))| \\&\ge r - |N_{u_1}|+|\nabla (N_{u_1})|=|\nabla (N(S))|. \end{aligned}$$
In order to answer Question 3.1 we must now determine \(|\nabla (N(r))|\). To proceed we will need the following Lemma that was proved in [1, Lemma 4.2].
Lemma 3.8
[1, Lemma 4.2] Let \(d >0\) be an integer and \(\mathbf{a} _1, \ldots , \mathbf{a} _r\) be the first r elements of \(F_{\le d}\) in descending lexicographic order. Then,Moreover, if \(\mathbf{a} _r = (a_{r, 1}, \ldots , a_{r, m})\) then
$$\begin{aligned} \nabla (\mathbf{a }_1, \ldots , \mathbf{a }_r) = \{\mathbf{a } \in F : \mathbf{a }_r \le _{lex} \mathbf{a }\}. \end{aligned}$$
$$\begin{aligned} |\nabla (\mathbf{a} _1, \ldots , \mathbf{a} _r)| = d_1 \cdots d_m - \displaystyle {\sum _{i=1}^m a_{r, i} \prod _{j=i+1}^m d_j}. \end{aligned}$$
The following Proposition, where we compute the \(|\nabla (N(r))|\) completes our pursuit of answering Question 3.1.
Proposition 3.9
Let \(u_1, u_2, r\) be as above. Assume that \(N(r) := \{\mathbf{a }_1, \ldots , \mathbf{a }_r\}\). Suppose \(\mathbf{a} _r\) is the s-th element of \(F_{\le u_1}\) in descending lexicographic order. Then,
$$\begin{aligned} |\nabla (\mathbf{a }_1, \ldots , \mathbf{a }_r)| = d_1 \cdots d_m - \displaystyle {\sum _{i=1}^m a_{r, i} \prod _{j=i+1}^m d_j} -s + r. \end{aligned}$$
Proof
Let us denote by \(M_{u_1} (s)\) the first s elements of \(F_{\le u_1}\) in descending lexicographic order. Clearly, \(\mathbf{a} _i \in M_{u_1} (s)\) for \(i=1, \ldots , r\). It is easy to see thatwhich proves thatThe assertion now follows from Lemma 3.8 by noting that \(\mathbf{a} _r\) is the s-th element of \(M_{u_1} (s)\) in descending lexicographic order. \(\square \)
$$\begin{aligned} \nabla (\mathbf{a} _1, \ldots , \mathbf{a} _r) = \nabla (M_{u_1} (s)) \setminus \left( M_{u_1} (s) \setminus N(r)\right) , \end{aligned}$$
$$\begin{aligned} |\nabla (\mathbf{a} _1, \ldots , \mathbf{a} _r)| = |\nabla (M_{u_1} (s))| - (s-r). \end{aligned}$$
We have thus answered the Question 3.1 completely and we note it down as the following corollary.
Corollary 3.10
Fix integers \(u_1, u_2\) and r with \(-1 \le u_2 < u_1 \le k\). Denote by \(\mathcal {F}_r\), the family of subsets of \(F_{u_2}^{u_1}\) of cardinality r. Thenwhere \((a_{r, 1}, \ldots , a_{r, m})\) is the r-th element of \(F_{u_2}^{u_1}\) and s-th element of \(F_{\le u_1}\) in descending lexicographic order. In particular,
$$\begin{aligned}\max \{|\Delta (S)| : S \in \mathcal {F}_r\} = \displaystyle {\sum _{i=1}^m a_{r, i} \prod _{j=i+1}^m d_j} +s - r,\end{aligned}$$
(a)
\(a_r (u_1, u_2, {{\mathcal {A}}}) \le \displaystyle {\sum _{i=1}^m a_{r, i} \prod _{j=i+1}^m d_j} +s - r \) and
(b)
\(M_r(u_1, u_2) \ge d_1 \cdots d_m - \displaystyle {\sum _{i=1}^m a_{r, i} \prod _{j=i+1}^m d_j} -s + r.\)
Proof
In the following and the last section of this article, we will produce a set \(\{f_1, \ldots , f_r \} \in \mathcal {C}_r\) for which the upper bound for \(a_r (u_1, u_2, {{\mathcal {A}}})\) given in the Corollary 3.10 is attained.
4 Maximal family of polynomials and the relative generalized Hamming weights of affine Cartesian codes
As mentioned before, we now construct a family of polynomials \(\{f_1,\ldots ,f_r\} \in \mathcal {C}_r\) such that \(|{{\mathsf {Z}}}_{{\mathcal {A}}}(f_1,\ldots ,f_r)|\) attains the upper bound for \(a_r (u_1, u_2, {{\mathcal {A}}})\) as obtained in Corollary 3.10. We call such a family of polynomials as a maximal family. First, recall that, \(A_i=\{\gamma _{i,1},\ldots ,\gamma _{i,d_i}\}\) for \(i=1, \ldots , m\).
Definition 4.1
For \(\mathbf{b} = (b_1, \ldots , b_m) \in F\) define the polynomial,
$$\begin{aligned} f_\mathbf{b } = \prod _{i=1}^m \prod _{j=1}^{b_i}(x_i - \gamma _{i, j}). \end{aligned}$$
We may note that \(\deg f_\mathbf{b } = b_1 + \cdots + b_m\) and with respect to the graded lexicographic order the leading term of\(f_\mathbf{b }\) is given by \({\mathsf {L}}{\mathsf {T}}(f_\mathbf{b }) = x_1^{b_1} \cdots x_m^{b_m}\). We further observe that, We define a map \(\psi : \mathcal {A} \rightarrow F\) given by \((\gamma _{1, i_1}, \ldots , \gamma _{m, i_m}) \mapsto (i_1 - 1, \ldots , i_m - 1)\). The map \(\psi \) is a bijection. It follows easily that for \(\gamma \in {{\mathcal {A}}}\),We have the following proposition which is an analogue of [1, Proposition 4.5].
$$\begin{aligned} f_\mathbf{b } (\gamma ) \ne 0 \iff \psi (\gamma ) \in \nabla (\mathbf{b} ) \end{aligned}$$
(10)
Proposition 4.2
Let \(\mathbf{a} _1, \ldots , \mathbf{a} _r\) be the first r elements of \(F_{u_2}^{u_1}\) in descending lexicographic order and suppose that \(\mathbf{a} _r\) is the s-th element of \(F_{\le u_1}\) in descending lexicographic order. Then,where \(\mathbf{a} _r = (a_{r,1}, \ldots , a_{r, m})\) and \(\mathrm{Supp} (f_\mathbf{a _1}, \ldots , f_\mathbf{a _r}) = \mathcal {A} \setminus {{\mathsf {Z}}}_{{\mathcal {A}}}(f_\mathbf{a _1}, \ldots , f_\mathbf{a _r})\).
$$\begin{aligned} |{\mathrm{Supp}} (f_{\mathbf{a }_1}, \ldots , f_{\mathbf{a }_r})| = d_1 \cdots d_m - \sum _{i=1}^m a_{r,i} \prod _{j=i+1}^m d_j - s + r, \end{aligned}$$
Proof
It follows from Eq. (10) that \(\gamma \in \mathrm{Supp}(f_\mathbf{a _1}, \ldots , f_\mathbf{a _r})\) if and only if \(\psi (\gamma ) \in \Delta (\mathbf{a} _1, \ldots , \mathbf{a} _r)\). Thus, \(|\mathrm{Supp}(f_\mathbf{a _1}, \ldots , f_\mathbf{a _r})| = |\nabla (\mathbf{a} _1, \ldots , \mathbf{a} _r)|\). Since \(\mathbf{a} _1, \ldots , \mathbf{a} _r\) are the first r elements of \(F_{u_1}^{u_2}\) in descending lexicographic order we see that,where the last equality follows from Proposition 3.9. This completes the proof. \(\square \)
$$\begin{aligned}|\mathrm{Supp}(f_\mathbf{a _1}, \ldots , f_\mathbf{a _r})| = |\nabla (\mathbf{a} _1, \ldots , \mathbf{a} _r)| = d_1 \cdots d_m - \displaystyle {\sum _{i=1}^m a_{r, i} \prod _{j=i+1}^m d_j} - s + r,\end{aligned}$$
Finally we may state the main result of this paper where we compute all the RGHWs of an affine Cartesian code with respect to a smaller affine Cartesian code.
Theorem 4.3
Fix integers \(u_1, u_2\) with \(-1 \le u_2 < u_1 \le \sum _{i=1}^m (d_i -1)\). Let \(AC_q (u_1, {{\mathcal {A}}})\) and \(AC_q (u_2, {{\mathcal {A}}})\) denote the corresponding affine Cartesian codes. For any integer \(1 \le r \le \ell := \dim AC_q (u_1, {{\mathcal {A}}}) - \dim AC_q(u_2, {{\mathcal {A}}})\), the r-th RGHW of \(AC_q (u_1, {{\mathcal {A}}})\) with respect to \(AC_q (u_2, {{\mathcal {A}}})\), denoted by \(M_r (u_1, u_2)\) is given bywhere \((a_{r,1}, \ldots , a_{r,m})\) is the r-th element of \(F_{u_2}^{u_1}\) and s-th element of \(F_{\le u_1}\) in descending lexicographic order.
$$\begin{aligned} M_r (u_1, u_2) = d_1 \cdots d_m - \displaystyle {\sum _{i=1}^m a_{r, i} \prod _{j=i+1}^m d_j} -s + r, \end{aligned}$$
Acknowledgements
Open Access funding provided by UiT The Arctic University of Norway. The author expresses his gratitude to Olav Geil for pointing out this problem, Peter Beelen for some enlightening discussions on these topics, and Trygve Johnsen for his careful reading of the manuscript and several comments. The author also thanks the reviewers for their careful reading of the article and their comments. The funding was provided by Norges Forskningsråd (Grant No. 280731).
Open AccessThis 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.