July 12, 2026
We obtain a Wei-type duality between the footprint bound and the dual footprint bound for the generalized Hamming weights of an evaluation code. This duality applies between the Andersen-Geil and Feng-Rao bounds as well. We also prove that the footprint and dual footprint bounds cannot be used to guarantee the asymptotic goodness of a family of evaluation codes.
The footprint bound is a classical result in algebraic geometry, bounding the number of rational points defined by an ideal in terms of its footprint [1]. This idea has proven fruitful for bounding the minimum distance of linear codes [2]–[4], since it is closely related to the number of zeroes of polynomials over a finite field. The generalized Hamming weights (GHWs) of a linear code, introduced in [5], provide an extension of the minimum distance, which has found several applications [6], [7]. Moreover, it is related to the number of common zeroes of sets of polynomials and can therefore also be studied using the footprint bound. Among other properties, the GHWs of a linear code satisfy the so-called Wei duality, which implies that the GHWs of a linear code are determined by those of its dual, and vice versa. A further extension of this concept is given by the relative generalized Hamming weights (RGHWs) of a pair of linear codes [8], which have applications in secret sharing [9] and quantum error-correction [10], [11]. There are two related bounds, the Feng-Rao bound [12], and the Andersen-Geil bound (sometimes called the Feng-Rao bound for primary codes) [13], which generalize the footprint bound in the affine setting and can also be used to bound the RGHWs of linear codes [14]. The computation of the GHWs and RGHWs of linear codes is, in general, NP-hard [15], and the footprint and Feng-Rao-type bounds have been used to obtain them for many of the most well-known families of codes [14], [16]–[23].
Finding constructions for asymptotically good families of codes has proven a challenging problem. In fact, many of the most well-known algebraic families of codes are known to be asymptotically bad, e.g., Reed-Muller codes, Cartesian codes, hyperbolic codes [24], binary primitive narrow-sense BCH codes [25], and several classes of cyclic codes [26], [27]. One of the most important examples of asymptotically good families of codes is given by AG codes [28], [29]. The authors consider the Goppa bound to prove that the corresponding codes are asymptotically good. Since the Feng-Rao and Andersen-Geil bounds are stronger, these bounds can be used to certify asymptotic goodness, in the sense that one can prove that certain families of codes are asymptotically good using them instead of the actual minimum distance of the code.
In this paper, we study the footprint bound and the dual footprint bound from a combinatorial perspective. In particular, in Section 3 we prove that there is a Wei-type duality between the values of the footprint bound and the dual footprint bound, and, more generally, between the values of the Andersen-Geil bound and the Feng-Rao bound. This implies that the footprint bound is sharp if and only if the dual footprint bound is sharp. Moreover, we show that the dual footprint bound coincides with the footprint bound of the dual code whenever the dual code is also obtained as a monomial code via an order-reversing bijection. This covers several well-known families of codes, such as Cartesian codes [30] and decreasing norm-trace codes [31]. These results also apply analogously to the Andersen-Geil and Feng-Rao bounds.
In Section 4, we prove that the footprint bound cannot be used to guarantee that a family of codes is asymptotically good, i.e., if we have a family of codes with non-vanishing asymptotic rate, the quotient of the footprint bound of the corresponding codes, divided by the length, will vanish. Furthermore, we show a similar result for the footprint bound for GHWs and RGHWs, and the result also holds for the dual footprint bound. As a consequence, any family of evaluation codes for which the footprint bound is sharp is asymptotically bad, recovering the well-known results for Reed-Muller codes, Cartesian codes, or hyperbolic codes [24].
Let \({\mathbb{F}}_q\) be a finite field with \(q\) elements. A linear code \(C\) is a linear subspace of \(\mathbb{F}_q^n\). Its dual code is the orthogonal space with respect to the Euclidean inner product, and is denoted by \(C^\perp\). Given a vector \(c\in \mathbb{F}_q^n\), we denote its Hamming weight by \(\mathop{\mathrm{{wt}}}(c):=\left|\left\{i:c_i\neq 0 \right\}\right|\), which is the number of nonzero coordinates of \(c\). We say that \(C\) is an \([n,k,d]\) code if \(C\subset \mathbb{F}_q^n\), \(\dim C=k\), and \(d:=\min \left\{\mathop{\mathrm{{wt}}}(c):c\in C\setminus \left\{0\right\}\right\}\). The parameters \(n, k, d\) are called the length, dimension, and minimum distance, respectively. Given a subcode \(D\subset C\), that is, a linear subspace of \(C\), we denote \[\mathop{\mathrm{{supp}}}(D):=\left\{1\leq i \leq n:\exists c\in D \text{ with } c_i\neq 0\right\}.\]
Definition 1. Let \(1\leq r \leq k=\dim C\). The \(r\)-th generalized Hamming weight (GHW) of \(C\) is a generalization of the minimum distance introduced in [5], and is defined by \[d_r(C):=\min \left\{ \@ifstar{\abs}{\abs*}{ \mathop{\mathrm{{supp}}}(D) }: D \textrm{ is a subcode of } C \textrm{ of dimension } r \right\}.\]
It follows from the definition that \(d_1(C)\) is the minimum distance of \(C\). From [5] we have the following general properties of the GHWs of a code.
Theorem 1 ((Monotonicity)). For an \([n,k]\) linear code \(C\) with \(k>0\) we have \[1\leq d_1(C)<d_2(C)<\cdots <d_k(C)\leq n.\]
Theorem 2 ((Duality)). Let \(C\) be an \([n,k]\) code. Then \[\{d_r(C):1\leq r\leq k\}\sqcup \{n+1-d_r(C^\perp):1\leq r\leq n-k\}=\{1,2,\dots,n\}.\]
The relative generalized Hamming weights (RGHWs) were introduced in [8], and they extend the notion of GHWs.
Definition 2. Let \(C_2\subset C_1 \subset \mathbb{F}_q^n\) be two linear codes, and \(k_1=\dim C_1\), \(k_2=\dim C_2\). Let \(r\) with \(1\leq r \leq k_1-k_2\). The \(r\)-th relative generalized Hamming weight of \(C_1\) and \(C_2\), denoted by \(M_r(C_1,C_2)\), is \[M_r(C_1,C_2)=\min \{ \@ifstar{\abs}{\abs*}{\mathop{\mathrm{{supp}}}(D)} : D \text{ is a subcode of C_1 with } \dim D=r, \; D\cap C_2=\{0\}\}.\]
For \(1\leq r \leq k_1-k_2\), we have \[M_r(C_1,C_2)\geq d_r(C_1).\] If \(C_2=\left\{0\right\}\), we recover the usual GHWs. The RGHWs are also strictly increasing [8], although we do not have a duality result as in Theorem 2 (see [32]).
Theorem 3. Let \(C_2\subset C_1\subset \mathbb{F}_q^n\) be linear codes with \(\dim C_1=k_1\), \(\dim C_2=k_2\). Then \[1\leq M_1(C_1,C_2)< M_2(C_1,C_2)<\cdots < M_{k_1-k_2}(C_1,C_2)\leq n.\]
While it is possible to derive the GHWs and RGHWs of some linear codes directly from the definitions, e.g., see [5] for binary Reed-Muller codes or [33] for matrix-product codes, we usually require additional structure to compute them. In particular, in this work we consider evaluation codes. Let \({\mathbb{X}}=\left\{P_1,\dots,P_n\right\}\subset \mathbb{F}_q^m\) be a set of \(n\) points. We denote its vanishing ideal by \(I({\mathbb{X}})\), which is the ideal generated by the polynomials in \(\mathbb{F}_q[x_1,\dots,x_m]\) that vanish at all the points of \({\mathbb{X}}\). We define the evaluation map by \[\begin{array}{lccc} {\rm ev_{\mathbb{X}}}\colon &\mathbb{F}_q[x_1,\dots,x_m] &\rightarrow& \mathbb{F}_q^{n}\quad \\ &f & \mapsto& \left(f(P_1),\ldots,f(P_n)\right). \end{array}\] We may denote it by \(\mathop{\mathrm{{ev}}}\) if there is no confusion about the evaluation points. We denote by \(\text{Mon}\) the set of monomials of \(\mathbb{F}_q[x_1,\dots,x_m]\). Given a monomial order and any ideal \(I\subset \mathbb{F}_q[x_1,\dots,x_m]\), we consider \(\mathop{\mathrm{{in}}}(I)\), the initial ideal of \(I\) with respect to that order. The footprint of \(I\) is \[\Delta(I):=\left\{x^\alpha \in \text{Mon}: x^\alpha \not \in \mathop{\mathrm{{in}}}(I)\right\}.\] The set \(\Delta(I)\) is a basis for \(\mathbb{F}_q[x_1,\dots,x_m]/I\) [34]. Consider \(\mathbb{L}\subset \text{Span}_\mathbb{F}_q(\Delta(I({\mathbb{X}})))\). Then the evaluation code associated to \({\mathbb{X}}\) and \(\mathbb{L}\) is \(\mathop{\mathrm{{ev}}}(\mathbb{L})\). Let \({\mathbb{M}}\subset \Delta(I({\mathbb{X}}))\). If \(\mathbb{L}=\text{Span}_\mathbb{F}_q({\mathbb{M}})\), we say that \(\mathop{\mathrm{{ev}}}(\mathbb{L})\) is a monomial code, and we denote it by \(C({\mathbb{X}},{\mathbb{M}})\).
Let \(V(I)\) be the affine variety associated to \(I\), i.e., the set of all common zeroes of the polynomials in \(I\). The footprint bound states that \[\label{eq:footprint95bound} \left|V(I)\right|\leq \left|\Delta(I)\right|,\tag{1}\] with equality if \(I\) is radical (see [1]). Let \(f\in \mathbb{L}\). Using 1 , we get \[\label{eq:proof95footprint} \left|V_{\mathbb{X}}(f)\right|:=\@ifstar{\abs}{\abs*}{V(f)\cap {\mathbb{X}}}= \@ifstar{\abs}{\abs*}{\Delta(I({\mathbb{X}})+(f))}\leq \left|\Delta(I({\mathbb{X}}))\cap \Delta(f)\right|=\left|\Delta(I({\mathbb{X}}))\cap \Delta(\mathop{\mathrm{{in}}}(f))\right|.\tag{2}\] This can be directly used to lower-bound the minimum distance of evaluation codes: \[d_1(\mathop{\mathrm{{ev}}}(\mathbb{L}))\geq n-\max\left\{\left|\Delta(I({\mathbb{X}}))\cap \Delta(x^\alpha)\right|:x^\alpha \in \mathop{\mathrm{{in}}}(\mathbb{L})\right\},\] where \(\mathop{\mathrm{{in}}}(\mathbb{L}):=\left\{\mathop{\mathrm{{in}}}(f):f\in \mathbb{L}\right\}\). If we consider instead a linearly independent set \(F=\left\{f_1,\dots,f_r\right\}\subset \mathbb{L}\), and \(V_{\mathbb{X}}(F)=V(F)\cap {\mathbb{X}}\), the same reasoning as 2 gives a bound for the GHWs: \[\label{eq:ghw95footprint95bound} \begin{align} d_r(\mathop{\mathrm{{ev}}}(\mathbb{L}))&\geq n-\max\left\{\left|\Delta(I({\mathbb{X}}))\cap \Delta(\mathbb{S})\right|:\mathbb{S}\in \binom{\mathop{\mathrm{{in}}}(\mathbb{L})}{r}\right\}\\ &\geq\min\left\{\left|\Delta(I({\mathbb{X}}))\setminus \Delta(\mathbb{S})\right|:\mathbb{S}\in \binom{\mathop{\mathrm{{in}}}(\mathbb{L})}{r}\right\}, \end{align}\tag{3}\] where we have used the fact that \(\left|\Delta(I({\mathbb{X}}))\right|=n\), which follows from 1 , and the notation \(\binom{A}{r}\) for the subsets of \(A\) with size \(r\). This is what we call footprint bound in the context of coding theory. We can interpret 3 combinatorially. For a set of monomials \(A\subset \mathbb{F}_q[x_1,\dots,x_m]\), we consider \(\varphi(A):=\left\{\alpha : x^\alpha \in A\right\}\). Then we denote \(X:=\varphi( \Delta(I({\mathbb{X}})))\) and \(L:=\varphi(\mathop{\mathrm{{in}}}(\mathbb{L}))\). For \(\beta \in \mathbb{N}^m\), we denote \(\nabla_X(\beta):=\left\{\alpha \in X:\beta \preceq \alpha \right\}\), where \(\prec\) denotes the usual partial order in \(\mathbb{N}^m\). The set \(\nabla_X(\beta)\) is called the (upward) shadow of \(\beta\) (with respect to \(X\)). For a subset \(S\subset \mathbb{N}^m\), we denote \(\nabla_X(S):=\bigcup_{s\in S}\nabla_X(s)\). Then 3 is translated to \[\label{eq:footprint95bound95combinatorial} d_r(\mathop{\mathrm{{ev}}}(\mathbb{L}))\geq \mathop{\mathrm{FB}}_X^r(L):=\min\left\{ \left|\nabla_X(S)\right|:S\in \binom{L}{r}\right\}.\tag{4}\]
Example 1. The bound from 4 is sharp for Reed-Muller codes [16], Cartesian codes [17], hyperbolic codes [22], codes over simplices [35], and square-free Cartesian codes [21]. It is also known not to be sharp for some AG codes; see, e.g., [20].
In [36], a similar bound for the GHWs of \(\mathop{\mathrm{{ev}}}(\mathbb{L})^\perp\) is derived: \[\label{eq:footprint95bound95combinatorial95dual} d_r(\mathop{\mathrm{{ev}}}(\mathbb{L})^\perp)\geq \mathop{\mathrm{FB}}_X^{r,\perp}(L):=\min\left\{ \left|\nabla^\perp_X(S)\right|:S\in \binom{X\setminus L}{r}\right\},\tag{5}\] where \(\nabla^\perp_X(\beta):=\left\{\alpha \in X:\alpha \preceq \beta \right\}\) and \(\nabla^\perp_X(S):=\bigcup_{s\in S}\nabla_X^\perp(s)\). We call this bound dual footprint bound.
Remark 4. Note that the bounds 4 and 5 for \(\mathop{\mathrm{{ev}}}(\mathbb{L})\) are the same as those we would obtain for \(C({\mathbb{X}},{\mathbb{M}})\), with \({\mathbb{M}}=\mathop{\mathrm{{in}}}(\mathbb{L})\). Thus, we can restrict ourselves to monomial codes \(C({\mathbb{X}},{\mathbb{M}})\).
One can generalize these techniques to bound the RGHWs of evaluation codes [37]. Let \(\mathbb{L}_2\subset\mathbb{L}_1 \subset \text{Span}_\mathbb{F}_q(\Delta(I({\mathbb{X}})))\) be two linear spaces, and, for \(1\leq r \leq \dim \mathbb{L}_1-\dim \mathbb{L}_2\), consider \({\mathbb{M}}_{1,2}^r:=\binom{\mathop{\mathrm{{in}}}(\mathbb{L}_1\setminus \mathbb{L}_2)}{r}\). Let \(M_{1,2}^r:=\binom{\varphi(\mathop{\mathrm{{in}}}(\mathbb{L}_1\setminus \mathbb{L}_2))}{r}\). Then \[\label{eq:fprelative95ugly} M_r(\mathop{\mathrm{{ev}}}(\mathbb{L}_1),\mathop{\mathrm{{ev}}}(\mathbb{L}_2))\geq \min \{\left|\nabla_X(M)\right| : M \in M_{1,2}^r\}.\tag{6}\] Following Remark 4, we usually restrict ourselves to monomial codes in this context. Let \({\mathbb{M}}_2\subset {\mathbb{M}}_1\), and we denote \(M_i=\varphi({\mathbb{M}}_i)\), for \(1\leq i \leq 2\). Assume that \(\alpha \in M_1\setminus M_2\) implies \(\alpha \succ\beta\), for any \(\beta \in M_2\). Then the previous bound can be rewritten as \[\label{eq:fprelative} M_r(C({\mathbb{X}},{\mathbb{M}}_1),C({\mathbb{X}},{\mathbb{M}}_2))\geq \min \left\{\left|\nabla_X(M)\right|: M \in \binom{M_1\setminus M_2}{r}\right\}:=\mathop{\mathrm{FB}}_X^r(M_1,M_2).\tag{7}\]
Similarly, for dual codes, we get \[\label{eq:fprelative95dual} M_r(C({\mathbb{X}},{\mathbb{M}}_2)^\perp,C({\mathbb{X}},{\mathbb{M}}_1)^\perp)\geq \min \left\{\left|\nabla_X^\perp(M)\right|: M \in \binom{M_1\setminus M_2}{r}\right\}:=\mathop{\mathrm{FB}}_X^{r,\perp}(M_1,M_2).\tag{8}\]
Definition 3. We say that a set \(A\subset {\mathbb{N}}^m\) is decreasing (or downward closed) if, for every \(\alpha \in A\), we have \(\left\{\beta\in {\mathbb{N}}^m :\beta \preceq \alpha\right\}\subset A\). Similarly, we say that a set of monomials \({\mathbb{M}}\subset \text{Mon}\) is decreasing if the set \(\varphi({\mathbb{M}})\) is decreasing. Given \(U\subset X \subset {\mathbb{N}}^m\), we say that it is increasing (or upward closed) if, for every \(\alpha \in U\), we have \(\left\{\beta\in X :\alpha \preceq \beta\right\}\subset U\), i.e, if \(X\setminus U\) is decreasing.
Remark 5. By construction, the sets \(X\) and \(\Delta(I({\mathbb{X}}))\) from the previous section are decreasing. If we consider a code \(C({\mathbb{X}},{\mathbb{M}})\) where \({\mathbb{M}}\) is not decreasing, we obtain the same bound in 4 as if we considered \({\mathbb{M}}'\), the smallest decreasing set that contains \({\mathbb{M}}\), and the code \(C({\mathbb{X}},{\mathbb{M}}')\) has a higher rate.
Similarly, if \(x^\alpha\in {\mathbb{M}}\) and \(x^{\alpha'}\not\in {\mathbb{M}}\), \(\alpha'\preceq\alpha\), then \({\mathbb{M}}'={\mathbb{M}}\setminus \{x^\alpha\}\) will give a code \(C({\mathbb{X}},{\mathbb{M}}')^\perp\) with higher rate and same bound in 5 as \(C({\mathbb{X}},{\mathbb{M}})^\perp\).
Therefore, if we aim at maximizing 4 or 5 individually, we may restrict ourselves to decreasing sets.
All the bounds we have given for \(C({\mathbb{X}},{\mathbb{M}})\) are expressed purely combinatorially in terms of \(X=\varphi(\Delta(I({\mathbb{X}})))\) and \(M=\varphi({\mathbb{M}})\). Thus, the analysis in the following sections will directly consider two decreasing sets \(M\subset X\subset {\mathbb{N}}^m\), rather than some particular \({\mathbb{M}}\) and \({\mathbb{X}}\).
In this section, we show that both the bounds 4 and 5 are “Wei duals” of each other, i.e., they satisfy a relation similar to that of Theorem 2. Therefore, the footprint bound is sharp if and only if the dual footprint bound is sharp. By Remark 4, without loss of generality, we may think about monomial codes. Thus we consider \(M\), which is the set of exponents of the set of monomials we evaluate.
Assume that we have fixed \(M\subset X\subset {\mathbb{N}}^m\), with \(X\) a decreasing set, and let \(n=\left|X\right|\), \(k=\left|M\right|\). We define now two sequences of numbers which are closely related to the bounds 4 and 5 : \[\Gamma(w):=\max \left\{\left|U\cap M\right|: U \text{ is increasing}, \; \@ifstar{\abs}{\abs*}{U}=w \right\},\] \[\Gamma^\perp(w):=\max \left\{\left|V \cap (X\setminus M)\right|: V \text{ is decreasing}, \; \@ifstar{\abs}{\abs*}{V}=w \right\}.\] We consider the sequences \(\left\{u_r\right\}_{r=1}^k\) and \(\left\{u^\perp_r\right\}_{r=1}^{n-k}\), where \(w\in \left\{u_r\right\}_{r=1}^k\) if and only if \(\Gamma(w)-\Gamma(w-1)=1\), and \(w\in \left\{u^\perp_r\right\}_{r=1}^{n-k}\) if and only if \(\Gamma^\perp(w)-\Gamma^\perp(w-1)=1\). Note that both \(\Gamma\) and \(\Gamma^\perp\) are increasing, and they can increase at most by 1 (you may take \(U\) with \(\left|U\right|=w\), and remove a minimal element to obtain another increasing \(U'\) with \(\left|U'\right|=w-1\), and thus \(\Gamma(w-1)\geq \Gamma(w)-1\); similarly for \(\Gamma^\perp\)).
Lemma 1. Let \(M\subset X\subset {\mathbb{N}}^m\) with \(X\) a decreasing set, and let \(1\leq r \leq \left|M\right|\), \(1\leq r'\leq \left|X\right|-\left|M\right|\). We have \[u_r=\min \left\{\left|U\right|: U \text{ is increasing,}\left|U\cap M\right|\geq r\right\} \text{ and}\] \[u_{r'}^\perp= \min \left\{\left|V\right|: V \text{ is decreasing,}\left|V\cap (X\setminus M)\right|\geq r'\right\}.\]
Proof. By definition, we have \[u_r=\min\left\{w: \Gamma(w)\geq r\right\} \text{ and } u_{r'}^\perp=\min \left\{w:\Gamma^\perp(w)\geq r'\right\},\] since \(\Gamma\) and \(\Gamma^\perp\) increase by at most 1 when increasing \(w\) by 1, which gives the result. ◻
Lemma 2. Let \(M\subset X\subset {\mathbb{N}}^m\) with \(X\) a decreasing set. Then \(u_r=\mathop{\mathrm{FB}}_X^r(M)\) and \(u_{r'}^\perp=\mathop{\mathrm{FB}}_X^{r',\perp}(M)\), for any \(1\leq r \leq \left|M\right|\) and \(1\leq r'\leq \left|X\right|-\left|M\right|\).
Proof. Consider \(A\subset M\) with \(\left|A\right|=r\) such that \(\left|\nabla_X(A)\right|=\mathop{\mathrm{FB}}_X^r(M)\). Then \(\nabla_X(A)\) is an increasing set, and \(\left|\nabla_X(A)\cap M\right|\geq r\). Thus, \(u_r\leq\left|\nabla_X(A)\right|=\mathop{\mathrm{FB}}_X^r(M)\) by Lemma 1. Now take \(U\) increasing such that \(\left|U\right|=u_r\), and \(\left|U\cap M\right|\geq r\). We can take \(A\subset U\cap M\) with \(\left|A\right|=r\), and then \(\nabla_X(A)\subset U\), i.e., \(\mathop{\mathrm{FB}}_X^r(M)\leq \left|U\right|=u_r\). The proof for \(u_{r'}^\perp\) is analogous. ◻
Theorem 6. Let \(M\subset X\subset {\mathbb{N}}^m\) with \(X\) a decreasing set. Then \[\left\{\mathop{\mathrm{FB}}_X^r(M)\right\}_{r=1}^{\left|M\right|}\sqcup \left\{n+1-\mathop{\mathrm{FB}}_X^{r',\perp}(M)\right\}_{r'=1}^{\left|X\right|-\left|M\right|} =\left\{1,\dots,\left|X\right|\right\}.\]
Proof. Let \(n=\left|X\right|\) and \(k=\left|M\right|\). Consider \(U\) an increasing set of size \(w\). Then \(V:=X\setminus U\) is a decreasing set with size \(n-w\). We have \[\left|V\cap M\right|=\left|V\right|-\left|V \cap (X\setminus M)\right| \text{ and }\left|U\cap M\right|=\left|M\right|-\left|V \cap M\right|.\] Substituting the first expression in the second one, we obtain \[\left|U\cap M\right|=k-n+w+\left|V \cap (X\setminus M)\right|.\] If we fix \(w\), then \(k-n+w\) is constant, and then \[\max_{\left|U\right|=w}\left|U\cap M\right|=k-n+w+\max_{\left|V\right|=n-w}\left|V \cap (X\setminus M)\right|.\] This also implies \(\Gamma(w)=k-n+w+\Gamma^\perp(n-w)\). Taking differences, we obtain \[\Gamma(w)-\Gamma(w-1)=1+\Gamma^\perp(n-w)-\Gamma^\perp(n-w+1).\] Thus, since we know \(\Gamma(w)-\Gamma(w-1)\in \left\{0,1\right\}\), we get \(\Gamma(w)=\Gamma(w-1)+1\) if and only if \(\Gamma^\perp(n-w)-\Gamma^\perp(n-w+1)=0\). In other words, \(w\in \left\{u_r\right\}_{r=1}^{k}\) if and only if \(n-w+1\not \in \left\{u_{r'}^\perp\right\}_{r'=1}^{n-k}\). We finish the proof by Lemma 2. ◻
Remark 7. As a consequence of Theorem 6, the footprint bound is sharp for all the GHWs if and only if the dual footprint bound is sharp for all the GHWs.
Example 2. In [35], the authors prove that, for some evaluation codes defined over a simplex (introduced in [38]), the footprint bound is sharp. Consequently, by Theorem 6, the dual footprint bound is sharp for their dual codes.
Corollary 1. Let \(M\subset X\subset {\mathbb{N}}^m\) with \(X\) a decreasing set. Then \[\mathop{\mathrm{FB}}_X^1(M)<\mathop{\mathrm{FB}}_X^2(M)<\cdots <\mathop{\mathrm{FB}}_X^{\left|M\right|}(M),\] \[\mathop{\mathrm{FB}}_X^{1,\perp}(M)<\mathop{\mathrm{FB}}_X^{2,\perp}(M)<\cdots <\mathop{\mathrm{FB}}_X^{\left|X\right|-\left|M\right|,\perp}(M).\]
Proof. This is a consequence of Theorem 6, since non-strict monotonicity follows directly from the definitions. ◻
Remark 8. Corollary 1 can also be proven directly: given a set \(B\in \binom{M}{r}\) such that \(\left|\nabla_X(B)\right|=\mathop{\mathrm{FB}}_X^r(M)\), if we consider \(B'\in \binom{M}{r-1}\) obtained by removing a minimal element of \(B\), we get \(\mathop{\mathrm{FB}}_X^{r-1}(M)\leq \left|\nabla_X(B')\right|\leq \left|\nabla_X(B)\right|-1<\mathop{\mathrm{FB}}_X^r(M)\), and similarly for the dual footprint. Moreover, this also proves the strict monotonicity from Corollary 1 for the bounds from 7 and 8 .
Analogous results to Theorem 6 and Corollary 1 can be obtained for the Feng-Rao bound [12] and the Andersen-Geil bound [13]. Let \(\mathcal{Y}\) be a smooth projective curve over \(\mathbb{F}_q\), let \(P_1,\dots,P_n,Q\) be distinct \(\mathbb{F}_q\)-rational points of \(\mathcal{Y}\), and let \(D=P_1+\cdots+P_n\). Using the usual notation for one-point AG codes \(C(D,\lambda Q)\), we consider the Weierstrass semigroup \(H(Q)\) for \(Q\in \mathcal{Y}\), and \(H^*(Q)\subset H(Q)\) is the finite set of non-gaps where the dimension of the corresponding one-point AG code actually increases, i.e., \[H^*(Q)=\left\{\lambda \in H(Q):C(D,\lambda Q)\neq C(D,(\lambda-1)Q)\right\}.\] Note that \(H^*(Q)\) depends on \(D\), and \(\left|H^*(Q)\right|=n\). For each \(\lambda \in H^*(Q)\), we choose \(f_\lambda \in \mathcal{L}(\infty Q)\) with \(-v_Q(f_\lambda)=\lambda\). We may consider \(M\subset H^*(Q)\). For \(\alpha,\beta\in {\mathbb{N}}\), we define the relation \(\alpha \preceq_Q \beta\) if and only if \(\beta-\alpha \in H(Q)\). For any \(S\subset H^*(Q)\), we can consider \(\nabla_Q(S)=\left\{\beta \in H^*(Q):\exists \alpha \in S:\alpha \preceq_Q \beta\right\}\) and \(\nabla^\perp_Q(S)=\left\{\alpha \in H^*(Q):\exists \beta \in S:\alpha \preceq_Q \beta\right\}\). We denote \[\mathcal{C}_M(D,Q):=\text{Span}_{\mathbb{F}_q}\left\{\mathop{\mathrm{{ev}}}_{\left\{P_1,\dots,P_n\right\}}(f_\lambda):\lambda\in M\right\}.\] We define the Andersen-Geil bound as in 4 , and the Feng-Rao bound as in 5 , using the alternative definitions for \(X\) (\(H^*(Q)\) plays the role of \(X\)), \(M\), \(\preceq_Q\), \(\nabla_Q\), and \(\nabla_Q^\perp\) (similarly for the bounds for the RGHWs from 7 and 8 ), i.e., we define
\[\label{eq:andersen95geil} d_r(\mathcal{C}_M(D,Q))\geq \mathop{\mathrm{AG}}_Q^r(M):=\min\left\{ \left|\nabla_Q(S)\right|:S\in \binom{M}{r}\right\},\tag{9}\] \[\label{eq:feng95rao} d_r(\mathcal{C}_M(D,Q)^\perp)\geq \mathop{\mathrm{FR}}_Q^{r}(M):=\min\left\{ \left|\nabla^\perp_Q(S)\right|:S\in \binom{H^*(Q)\setminus M}{r}\right\}.\tag{10}\]
For \(r=1\), these bounds have been shown to be consequences of each other in [39]. In general, they also satisfy the following Wei-type duality and strict monotonicity.
Theorem 9. With the notation as above, we have \[\left\{\mathop{\mathrm{AG}}_Q^r(M)\right\}_{r=1}^{\left|M\right|}\sqcup \left\{n+1-\mathop{\mathrm{FR}}_Q^{r'}(M)\right\}_{r'=1}^{n-\left|M\right|} =\left\{1,\dots,n\right\}.\] Moreover, \[\mathop{\mathrm{AG}}_Q^1(M)<\cdots<\mathop{\mathrm{AG}}_Q^{|M|}(M)\] and \[\mathop{\mathrm{FR}}_Q^{1}(M)<\cdots< \mathop{\mathrm{FR}}_Q^{n-|M|}(M).\]
Proof. It follows from the proofs of Theorem 6 and 1, with \(X=H^*(Q)\) and with \(\nabla_X\) and \(\nabla_X^\perp\) replaced by \(\nabla_Q\) and \(\nabla_Q^\perp\), respectively. ◻
Example 3. In [20], the authors consider a modified footprint bound, which is sharp for decreasing norm-trace codes. Since the duals are monomially equivalent to decreasing norm-trace codes, one can use the same bound for the dual codes, and it is also sharp. In [40], the author shows that this footprint bound equals the Andersen-Geil bound for primary codes (or Feng-Rao for the dual codes). Thus, arguing as above, one can also deduce the sharpness of the Feng-Rao bound from Andersen-Geil’s, or vice versa.
In many well-known cases, the dual of a monomial evaluation code is monomially equivalent to another monomial evaluation code that uses the same evaluation points [41]–[43]. The following result shows that, in those cases, the footprint bound associated with the monomials that define the dual coincides with the dual footprint bound.
Proposition 10. Let \(\phi:X\to X\) be an order-reversing bijection, meaning \(\alpha\preceq \beta\) if and only if \(\phi(\beta)\preceq \phi(\alpha)\). Let \(M_2\subset M_1\subset X\) such that \(\alpha \in M_1\setminus M_2\) implies \(\alpha \succ\beta\), for any \(\beta \in M_2\), and consider \(M_i^\perp:=\phi(X\setminus M_i)\), for \(i=1,2\). Then, for \(1\leq r \leq \left|M_1\right|-\left|M_2\right|\), we have \[\mathop{\mathrm{FB}}_X^{r,\perp}(M_1,M_2)=\mathop{\mathrm{FB}}_X^{r}(M_2^\perp,M_1^\perp) \text{ and } \mathop{\mathrm{FB}}_X^{r,\perp}(M^\perp_2,M^\perp_1)=\mathop{\mathrm{FB}}_X^{r}(M_1,M_2).\]
Proof. Let \(B\in \binom{M_1\setminus M_2}{r}\), and consider \(B^\perp:=\phi(B)\subset M_2^\perp\setminus M_1^\perp\). Since \(\phi\) is order-reversing, we have \(\phi(\nabla_X^\perp(B))=\nabla_X(B^\perp)\). Indeed, \(\alpha\in \phi(\nabla^\perp_X(B))\) if and only if there is \(\beta\in B\) and \(\gamma\) such that \(\alpha=\phi(\gamma)\) and \(\gamma \preceq \beta\), i.e., we have \(\phi(\beta) \preceq \alpha\), which is equivalent to \(\alpha \in \nabla_X(B^\perp)\). Therefore, \(\left|\phi(\nabla_X^\perp(B))\right|=\left|\nabla_X^\perp(B)\right|=\left|\nabla_X(B^\perp)\right|\), and we obtain the first equality by taking the minimum over all \(B\in \binom{M_1\setminus M_2}{r}\). The second equality follows from \(\phi(\nabla_X(B))=\nabla^\perp_X(B^\perp)\), which can be proven in an analogous way. ◻
For simplicity, in the next examples we assume \(M_1=X\), and thus \(\mathop{\mathrm{FB}}_X^{r,\perp}(X,M)=\mathop{\mathrm{FB}}_X^{r,\perp}(M)\), \(\mathop{\mathrm{FB}}_X^{r}(M^\perp,\left\{0\right\})=\mathop{\mathrm{FB}}_X^{r}(M^\perp)\).
Example 4. Let \({\mathbb{X}}=A_1\times \cdots \times A_m\) be a Cartesian product of sets \(A_i\subset \mathbb{F}_q\) of size \(\left|A_i\right|=d_i\), for \(1\leq i \leq m\). Then \(X=\left\{0,\dots,d_1-1\right\}\times \cdots \times \left\{0,\dots,d_m-1\right\}\). Let \(\phi:X\to X\) be the map defined by \(\phi(\alpha):=(d_1-1,\dots,d_m-1)-\alpha\). It is clear that it is an order-reversing bijection. For any decreasing set of monomials \({\mathbb{M}}\subset \mathbb{F}_q[x_1,\dots,x_m]\), consider \(M=\varphi({\mathbb{M}})\) and \(M^\perp:=\phi(X\setminus M)\) as above. It follows from [41] that the dual of \(C({\mathbb{X}},{\mathbb{M}})\) is monomially equivalent to \(C({\mathbb{X}},{\mathbb{M}}^\perp)\), where \({\mathbb{M}}^\perp:=\left\{x^\alpha \in \mathbb{F}_q[x_1,\dots,x_m]:\alpha \in \phi(X\setminus M)\right\}\). By Proposition 10, we have that \(\mathop{\mathrm{FB}}_X^{r,\perp}(M)=\mathop{\mathrm{FB}}_X^{r}(M^\perp)\), for any \(1\leq r \leq \@ifstar{\abs}{\abs*}{X}-\@ifstar{\abs}{\abs*}{M}\).
As with Proposition 10, if we consider a one-point AG code \(\mathcal{C}_M(D,\lambda Q)\) such that its dual is of the form \(\mathcal{C}_{M^\perp}(D,\lambda^\perp Q)\), and there exists \(\phi:H^*(Q)\to H^*(Q)\) an order reversing bijection such that \(M^\perp=\phi(H^*(Q)\setminus M)\), then \[\mathop{\mathrm{FR}}_Q^r(M)=\mathop{\mathrm{AG}}_Q^r(M^\perp), \qquad 1\leq r\leq n-|M|.\] A similar result follows for the bounds of the RGHWs of pairs of such codes, which are defined in an analogous manner to 7 and 8 .
Example 5. Consider a one-point AG code \(C(D,\lambda Q)\) such that \(C(D,\lambda Q)^\perp\simeq C(D,(\mu -\lambda )Q)\), up to monomial equivalence, and consider \(\phi(\alpha)=\mu+1-\alpha\). If we assume \[\phi(H^\ast(Q))=H^\ast(Q), \text{ or, equivalently, } \alpha\in H^\ast(Q) \iff \mu+1-\alpha\in H^\ast(Q),\] then \(\phi\) is an order-reversing bijection. Consequently, if \(M:=\{\alpha\in H^\ast(Q):\alpha\le \lambda\}\) and \(M^\perp:=\{\alpha\in H^\ast(Q):\alpha\le \mu -\lambda\}\), then \(M^\perp=\phi\bigl(H^\ast(Q)\setminus M\bigr)\). It follows that \[\mathop{\mathrm{FR}}_Q^r(M)=\mathop{\mathrm{AG}}_Q^r(M^\perp)\] for \(1\leq r\leq n-|M|\).
The condition \(H^\ast(Q)=\mu+1-H^\ast(Q)\) is satisfied in some well-known cases. For example, if \(D\) corresponds to the sum of all the affine rational points of the Hermitian curve and \(Q\) corresponds to the point at infinity, we have \[H^\ast(Q)=\left\{iq+j(q+1):0\le i\le q^2-1,\; 0\le j\le q-1\right\}.\] Then we know that \(C(D,\lambda Q)^\perp\simeq C(D,(q^3+q^2-q-2-\lambda)Q)\). If we take \(\mu=q^3+q^2-q-2\), then we can check that \(H^\ast(Q)=\mu+1-H^\ast(Q)\) (note that \(\mu+1=(q^2-1)q+(q-1)(q+1)\)), and the map \(\phi(\alpha)=\mu+1-\alpha\) is an order-reversing bijection.
The condition \(H^\ast(Q)=\mu+1-H^\ast(Q)\) is closely related to the conditions required to obtain isometry dual flags of one-point AG codes. A complete flag is a sequence of codes \(\left\{0\right\}=C_0\subsetneq C_1\subsetneq \cdots \subsetneq C_n= \mathbb{F}_q^n\), and its dual flag is \(\left\{0\right\}=C_n^\perp \subsetneq C_{n-1}^\perp \subsetneq\cdots \subsetneq C_0^\perp=\mathbb{F}_q^n\). A flag is isometry-dual if there is an isometry \(g\) such that \(g(C_i)=C^\perp_{n-i}\), for \(0\leq i \leq n\). The condition \(H^\ast(Q)=\mu+1-H^\ast(Q)\) implies that the associated flag is isometry dual (assuming that the dual of \(C(D,\lambda Q)\) is as in Example 5). For example, if \(n\geq 2g+2\), one can take \(\mu=n+2g-2\) (see [44], [45]).
We devote this section to proving that the footprint bound is insufficient to guarantee that a family of evaluation codes is asymptotically good, in the following sense.
Definition 4. Given a sequence of codes \(\{C_n\}_{n=1}^\infty\), we say that it is asymptotically good if we have \[\liminf_{n\to \infty }\frac{\dim(C_n)}{n}>0 \text{ and }\liminf_{n\to \infty }\frac{d_1(C_n)}{n}>0.\]
We start with a technical lemma, which will lead to Theorem 11, the main result of the section.
Lemma 3. For any decreasing set \(X\subset {[0,q-1]^m}\) with \(\@ifstar{\abs}{\abs*}{X}=n_X\geq 2\), we have \[\label{eq:lemma95gamma} \sum_{z\in X}\prod_{i=1}^m (z_i+1)\leq n_X^\gamma,\tag{11}\] where \(\gamma=\log_q\left(\frac{q(q+1)}{2}\right)\).
Proof. We argue by induction on \(m\). Let \(m=1\). Then \(X=\{0,\dots,n_X-1\}\), and we need to show that \[\label{eq:base95case95inducion} \sum_{z\in X}\prod_{i=1}^m (z_i+1)=\frac{n_X(n_X+1)}{2}\leq n_X^\gamma.\tag{12}\] By taking base-\(n_X\) logarithms, it is enough to show that \(f(x)=\log_x\left(\frac{x(x+1)}{2}\right)\leq \gamma=f(q)\), for all \(2\leq x \leq q\) (recall that \(X\subset [0,q-1]\), and \(n_X\leq q\)). This follows from the fact that the function is strictly increasing for \(x> 1\).
Now we assume \(m>1\). For each \(j\in \{0,\dots,q-1\}\), consider \[X_j:=\{z\in [0,q-1]^{m-1}:(z,j)\in X\}.\] By adding elements of \(X\) with a fixed last coordinate, we can write \[\label{eq:eq95random} \sum_{(z,j)\in X}\prod_{i=1}^{m-1} (z_i+1)(j+1)=\sum_{j=0}^{q-1}(j+1)\left( \sum_{z\in X_j}\prod_{i=1}^{m-1}(z_i+1) \right).\tag{13}\] For every \(j\) such that \(\@ifstar{\abs}{\abs*}{X_j}\geq 2\), the induction hypothesis gives \[\sum_{z\in X_j}\prod_{i=1}^{m-1}(z_i+1) \leq n_{X_j}^{\gamma}.\] The same inequality is immediate when \(\@ifstar{\abs}{\abs*}{X_j}\leq 1\). Hence, summing in 13 , we obtain \[\label{eq:first95inequality} \sum_{z\in X}\prod_{i=1}^m(z_i+1) \leq \sum_{j=0}^{q-1}(j+1)n_{X_j}^{\gamma}.\tag{14}\] Note that \(n_X=\sum_{j=0}^{q-1} n_{X_j}\), which follows from the fact that \(X=\bigsqcup_{j=0}^{q-1} X_j\times \{j\}\). Thus, to finish the proof, we have to prove \[\sum_{j=0}^{q-1}(j+1)n_{X_j}^\gamma\leq n_X^\gamma = \left(\sum_{j=0}^{q-1} n_{X_j}\right)^\gamma .\] We denote \(p_j:=n_{X_j}/n_X\). Since \(X_{0}\supset X_{1}\supset \cdots \supset X_{q-1}\), we have \(p_0\geq p_1\geq \cdots \geq p_{q-1}\geq 0\) and \(\sum_{j=0}^{q-1}p_j=1\), and we have to show that \[\sum_{j=0}^{q-1}(j+1)p_j^\gamma \leq 1.\] Consider \(g(p_0,\dots,p_{q-1}):=\sum_{j=0}^{q-1}(j+1)p_j^\gamma\), which is strictly convex. Indeed, since \(\gamma>1\), we have that \(x^\gamma\) is strictly convex in \([0,\infty)\) (this can be checked using derivatives and the definition for \(x=0\)), and thus \(g\) is strictly convex because it is a sum of strictly convex functions. Therefore, we are trying to find the maximum of a strictly convex function over a closed convex polytope \(\mathcal{P}\) (the standard simplex, with the extra condition \(p_0\geq p_1\geq \cdots \geq p_{q-1}\)). This implies that the maximum is attained at one of the vertices of \(\mathcal{P}\). The vertices of \(\mathcal{P}\) are the points \(P_k\) with \(p_0=\cdots=p_{k-1}=1/k\), and \(p_j=0\) for \(j=k,\dots,q-1\) (this can be seen, for example, by considering the change of variables \(z_k=(k+1)(p_k-p_{k+1})\), \(0\leq k \leq q-2\), and \(z_{q-1}=q p_{q-1}\), which maps \(\mathcal{P}\) to the standard simplex). We have \[\label{eq:g95of95p} g(P_k)=\sum_{j=0}^{k-1}(j+1)\frac{1}{k^\gamma}=\frac{k(k+1)}{2k^\gamma}\leq 1.\tag{15}\] For \(2\leq k\leq q\), the last inequality follows from the one-dimensional case 12 , while \(g(P_1)=1\). Thus, \[g(p_0,\dots,p_{q-1})\leq1\] for every point in \(\mathcal{P}\). ◻
Theorem 11. Let \(\{M_m\}_{m=1}^\infty\), \(\{X_m\}_{m=1}^\infty\) be two sequences of sets such that \(\emptyset \neq M_m\subset X_m\subset {[0,q-1]^m}\) and \(X_m\) is decreasing, for \(m\geq 1\). Assume that \(\lim_{m\to \infty}\@ifstar{\abs}{\abs*}{X_m}=\infty\). Then \[\lim_{m\to \infty}\frac{\@ifstar{\abs}{\abs*}{M_m}\mathop{\mathrm{FB}}^1_{X_m}(M_m)}{\@ifstar{\abs}{\abs*}{X_m}^2}=0.\] As a consequence, if both \(\lim_{m\to \infty} \@ifstar{\abs}{\abs*}{M_m}/\@ifstar{\abs}{\abs*}{X_m}\) and \(\lim_{m\to \infty} \mathop{\mathrm{FB}}^1_{X_m}(M_m)/\@ifstar{\abs}{\abs*}{X_m}\) exist, then either \(\lim_{m\to \infty} \@ifstar{\abs}{\abs*}{M_m}/\@ifstar{\abs}{\abs*}{X_m}=0\) or \(\lim_{m\to \infty} \mathop{\mathrm{FB}}^1_{X_m}(M_m)/\@ifstar{\abs}{\abs*}{X_m}=0\).
Proof. Let \(n_m:=\@ifstar{\abs}{\abs*}{X_m}\), and denote \(\@ifstar{\abs}{\abs*}{M_m}=a_m n_m\), \(\mathop{\mathrm{FB}}^1_{X_m}(M_m)=b_m n_m\). Consider \[S:=\sum_{P\in M_m}\mathop{\mathrm{FB}}^1_{X_m}(P).\] We clearly have \(S\geq \@ifstar{\abs}{\abs*}{M_m}\mathop{\mathrm{FB}}^1_{X_m}(M_m)=a_mb_m n_m^2\), and also \[\label{eq:bound95on95S} S=\sum_{P\in M_m} \sum_{\substack{z \in X_m \\ z \succeq P}} 1\leq \sum_{P\in {[0,q-1]^m}} \sum_{\substack{z \in X_m \\ z \succeq P}} 1 = \sum_{z \in X_m} \sum_{\substack{P\in {[0,q-1]^m}\\ P \preceq z}} 1 = \sum_{z \in X_m} \prod_{i=1}^m(z_i+1)\leq n_m^\gamma,\tag{16}\] where we have used Lemma 3 for the last inequality. Thus, we have \[a_mb_m n_m^2\leq S \leq n_m^\gamma,\] which implies \[\label{eq:n95gamma} a_mb_m\leq n_m^{\gamma-2}.\tag{17}\] Note that \(\gamma<2\), since \(q(q+1)/2<q^2\). Thus, the right-hand side of 17 tends to 0 when \(m\to \infty\), forcing \(\lim_{m\to \infty}a_mb_m =0\). ◻
Corollary 2. Let \(\mathbb{L}_m\subset \mathbb{F}_q[x_1,\dots,x_m]/I({\mathbb{X}}_m)\) be a sequence of linear subspaces, with respect to a sequence of sets of points \({\mathbb{X}}_m\subset \mathbb{F}_q^m\). Let \(L_m=\varphi(\mathop{\mathrm{{in}}}(\mathbb{L}_m))\) and \(X_m=\varphi(\Delta(I({\mathbb{X}}_m)))\). Let \(k_m:=\@ifstar{\abs}{\abs*}{L_m}/\@ifstar{\abs}{\abs*}{X_m}\), \(\delta_m:=\mathop{\mathrm{FB}}^1_{X_m}(L_m)/\@ifstar{\abs}{\abs*}{X_m}\), and assume \(\lim_{m\to\infty}\left|X_m\right|=\infty\). Then it is not possible to have both \[\liminf_{m\to \infty }k_m>0 \text{ and }\liminf_{m\to \infty }\delta_m>0.\] In other words, the footprint bound cannot be used to guarantee asymptotic goodness.
Note that these results do not imply that the family of monomial codes, or even decreasing monomial codes, is bad. However, they imply that, to guarantee asymptotic goodness, we need to use other bounds, or improvements of the footprint, such as the one used in [20]. We now introduce a new notion closely related to that of asymptotic goodness (see [46], where this idea was studied in the context of asymptotically good secret sharing schemes).
Definition 5. Let \(r\geq 1\). We say that a sequence of codes \(C_n\subset \mathbb{F}_q^n\) is \(r\)-asymptotically good if we have both \[\liminf_{n\to \infty }\frac{\dim(C_n)}{n}>0 \text{ and }\liminf_{n\to \infty }\frac{d_r(C_n)}{n}>0.\] For the second quotient to make sense, we must have \(\dim(C_n)\geq r\) (we could also define \(d_r(C)=0\) if \(r>\dim(C)\)). This is guaranteed to happen for \(n\) sufficiently large if we have \(\liminf_{n\to \infty }\frac{\dim(C_n)}{n}>0\).
By the definition, it is clear that if a sequence of codes is \(r\)-asymptotically good, it will be \(j\)-asymptotically good for every \(j\geq r\). We can also obtain sequences which are \(r\)-asymptotically good but not \(r-1\)-asymptotically good.
Lemma 4. Let \(r\geq 2\) and let \(\{C_n\}_{n=1}^\infty\) be an asymptotically good sequence of codes. Consider the family defined by \(C'_n=C_n\) for \(n<r-1\), and \(C'_n=C_n+\langle e_1,\dots,e_{r-1}\rangle\) for \(n\geq r-1\). The sequence \(\{C'_n\}_{n=1}^\infty\) is \(r\)-asymptotically good, but not \(r-1\)-asymptotically good.
Proof. Since \(\{C_n\}_{n=1}^\infty\) is asymptotically good, for a sufficiently large \(n\), we have \(d_r(C_m)> d_1(C_m)>r\), and \(\dim(C_m)\geq r\), for every \(m\geq n\). Consider \(D\subset C'_m\), a subcode with \(\dim D=r\). By the definition of \(C'_m\), we have that \(D\) contains \(c\in C'_m\setminus \langle e_1,\dots,e_{r-1}\rangle\), and we also have \(\mathop{\mathrm{{wt}}}(c)\geq d_1(C_m)-(r-1)\). Thus, \(d_r(C'_m)\geq \@ifstar{\abs}{\abs*}{\mathop{\mathrm{{supp}}}(D)}\geq d_1(C_m)-(r-1)\). This proves that \(\{C'_n\}_{n=1}^\infty\) is \(r\)-asymptotically good. That \(\{C'_n\}_{n=1}^\infty\) is not \(r-1\)-asymptotically good follows from the fact that, for sufficiently large \(n\), we have \(d_{r-1}(C'_n)=r-1\), since \(C'_n\) contains the subcode \(\langle e_1,\dots,e_{r-1}\rangle\). ◻
Even though the footprint bound is not sufficient to prove asymptotic goodness, one might think it could still be sufficient to prove \(r\)-asymptotic goodness; however, in the next result we prove that this is not the case.
Corollary 3. Let \(r\geq 1\). Under the same hypotheses of Theorem 11, and, additionally, \(|M_m|\geq r\) for all sufficiently large \(m\), we have \[\lim_{m\to \infty}\frac{\@ifstar{\abs}{\abs*}{M_m}\mathop{\mathrm{FB}}^r_{X_m}(M_m)}{\@ifstar{\abs}{\abs*}{X_m}^2}=0.\] As a consequence, the footprint bound cannot be used to guarantee \(r\)-asymptotic goodness, for any \(r\geq 1\).
Proof. Let \(n_m = \@ifstar{\abs}{\abs*}{X_m}\) and \(\@ifstar{\abs}{\abs*}{M_m} = a_m n_m\). Let \(P_1, \dots, P_r\) be the \(r\) elements in \(M_m\) with the smallest individual footprints \(\mathop{\mathrm{FB}}^1_{X_m}(P_i)\). By the definition of the footprint bound \[\begin{align} \mathop{\mathrm{FB}}^{r}_{X_m}(M_m)\leq \mathop{\mathrm{FB}}^{r}_{X_m}(\{P_1,\dots,P_r\}) \leq \left| \bigcup_{i=1}^r \{x \in X_m \mid x \succeq P_i\} \right| &\leq \sum_{i=1}^r \mathop{\mathrm{FB}}^1_{X_m}(P_i)\\ &\leq \frac{r}{\@ifstar{\abs}{\abs*}{M_m}} \sum_{P \in M_m} \mathop{\mathrm{FB}}^1_{X_m}(P), \end{align}\] where in the last step we have used that the sum of the smallest footprints is lower than \(r\) times the average footprint. Using 16 we obtain \[\mathop{\mathrm{FB}}^{r}_{X_m}(M_m) \leq\frac{r}{\@ifstar{\abs}{\abs*}{M_m}} \sum_{P \in M_m} \mathop{\mathrm{FB}}^1_{X_m}(P)\leq r \frac{n_m^\gamma}{a_m n_m}.\] Multiplying both sides by \(a_m / n_m\), we get \[\frac{\@ifstar{\abs}{\abs*}{M_m}\mathop{\mathrm{FB}}^{r}_{X_m}(M_m)}{\@ifstar{\abs}{\abs*}{X_m}^2} \leq r n_m^{\gamma - 2}.\] Since \(r\) is fixed and \(\gamma < 2\), the right-hand side tends to 0 as \(m \to \infty\). ◻
We can also consider the relative footprint bound and a sequence of nested sets (or codes), similar to [46], but we obtain the same negative result.
Corollary 4. Let \(r\geq 1\). Let \(\{M^1_m\}_{m=1}^\infty\), \(\{M^2_m\}_{m=1}^\infty\), \(\{X_m\}_{m=1}^\infty\) be three sequences of sets such that \(\emptyset \neq M^2_m\subset M^1_m\subset X_m\subset {[0,q-1]^m}\) and \(X_m\) is decreasing, for \(m\geq 1\). Assume that \(\alpha \in M_m^1\setminus M_m^2\) implies \(\alpha \succ\beta\), for any \(\beta \in M_m^2\), and that \(\lim_{m\to \infty}\@ifstar{\abs}{\abs*}{X_m}=\infty\). Also assume that \(|M_m^1\setminus M_m^2|\geq r\) for all sufficiently large \(m\). Then \[\lim_{m\to \infty}\frac{\@ifstar{\abs}{\abs*}{M^1_m\setminus M^2_m}\mathop{\mathrm{FB}}^r_{X_m}(M^1_m,M^2_m)}{\@ifstar{\abs}{\abs*}{X_m}^2}=0.\]
Proof. Let \(n_m = \@ifstar{\abs}{\abs*}{X_m}\) and \(\@ifstar{\abs}{\abs*}{M^1_m\setminus M^2_m} = a_m n_m\). The proof is then analogous to that of Corollary 3, considering \(D_m:=M^1_m\setminus M^2_m\) instead of \(M_m\), and relative footprints. ◻
If we are considering the setting in which we do not have the condition that \(\alpha \in M_m^1\setminus M_m^2\) implies \(\alpha \succ\beta\), then we have to consider the bound from 6 . Although that bound does not have a purely combinatorial description, we may still consider \(\varphi(\mathop{\mathrm{{in}}}(\mathbb{L}_m^1\setminus \mathbb{L}_m^2))\) instead of \(M_m^1\setminus M_m^2\) in the proof of Corollary 4, and an analogous result follows.
Remark 12. Note that the proof of Corollaries 3 and 4 holds even if \(r\) is not a constant, as long as \(r=o(n_m^{2-\gamma})\).
Similar arguments show that the bounds for the RGHWs of the dual codes are also insufficient to obtain asymptotically good codes. Indeed, Lemma 3 is already written appropriately for the dual footprint bound; see also the last equality in 16 .
Example 6. The footprint bound is sharp for codes considered in [35], which implies they are asymptotically bad. Similarly, Theorem 11 recovers that hyperbolic codes are asymptotically bad, see [24].
While the value of the footprint bound may depend on the chosen monomial ordering, which determines \(X=\varphi(\Delta(I({\mathbb{X}})))\) in terms of \({\mathbb{X}}\), once we have chosen that ordering, that fixes \(X\), and the previous results apply, i.e., it will still satisfy the Wei-type duality and the asymptotic badness.
In this paper, we have proven a Wei-type duality for the footprint bound and, more generally, for the Andersen-Geil and the Feng-Rao bounds. We have also obtained that the footprint bound cannot be used to prove that a family of codes is asymptotically good. This motivates the study of modified footprints as in [2], [20], [24], [47], [48], which may be able to bypass this restriction. It would also be interesting to see whether it is possible to prove similar results for generalizations of the footprint bound to projective and weighted projective spaces.