{\beta}egin{document}

 {\alpha}uthor{Peter Beelen}
{\alpha}ddress{
Department of Applied Mathematics and Computer Science,\newline \indent
Technical University of Denmark, 
2800 Kgs. Lyngby, Denmark}
{\mathbf e}mail{pabe@dtu.dk}

{\alpha}uthor{Mrinmoy Datta}
{\alpha}ddress{
Department of Mathematics,
Indian Institute of Technology Hyderabad,\newline \indent
Kandi, Sangareddy, Telanagana,   502285, India}

{\mathbf e}mail{mrinmoy.datta@math.iith.ac.in} 

{\alpha}uthor{Sudhir R. Ghorpade}
{\alpha}ddress{Department of Mathematics, 
Indian Institute of Technology Bombay,\newline \indent
Powai, Mumbai 400076, India}
{\mathbf e}mail{srg@math.iitb.ac.in}

\mathcal Mathcal Subjclass[2010]{Primary 14G15, 11G25, 14G05; Secondary 11T71, 94B27, 51E20}

\keywords{Finite field, projective algebraic variety, footprint bound, projective Reed-Muller code, generalzed Hamming weight.}

{\delta}ate{}

{\beta}egin{abstract}
We give a complete conjectural formula for the  number $e_r(d,m)$ of maximum possible ${\mathcal Mathbb F}_q$-rational points on a projective algebraic variety defined by 
$r$ linearly independent homogeneous polynomial equations of degree $d$ in $m+1$ variables with coefficients in the finite field ${\mathcal Mathbb F}_q$ with $q$ elements, when $d<q$. It is shown that this formula holds in the affirmative for several values of $r$. In the general case, 
we give explicit lower and upper bounds for $e_r(d,m)$ and show that they are sometimes attained.
Our approach uses a relatively recent result, 
called the projective footprint bound, together with results from extremal combinatorics such as the Clements-Lindstr\"om Theorem and its variants. Applications to the problem of determining the generalized Hamming weights of projective Reed-Muller codes are also included.

{\mathbf e}nd{abstract}

\mathcal Maketitle

\mathcal Mathcal Section{Introduction}
\label{sec:intro}
Fix a prime power $q$ and positive integers $r,d,m$. Let ${\mathcal Mathbb F}_q$ denote the finite field with $q$ elements and ${\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]$ the polynomial ring in $m+1$ variables $x_0, x_1, {\delta}ots , x_m$ with coefficients in ${\mathcal Mathbb F}_q$. For any homogeneous polynomials $F_1, {\delta}ots , F_r$ in ${\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]$, let
$V(F_1, {\delta}ots , F_r)$ denote the closed subvariety of the projective $m$-space ${\mathbb P}^m$ (over an algebraic closure of ${\mathcal Mathbb F}_q$) given by the vanishing of $F_1, {\delta}ots , F_r$, and let $V(F_1, {\delta}ots , F_r)({\mathcal Mathbb F}_q)$ be the set of its ${\mathcal Mathbb F}_q$-rational points,
i.e., the set of all ${\mathcal Mathbb F}_q$-rational common zeros in ${\mathbb P}^m$ of $F_1, {\delta}ots , F_r$. Define
{\beta}egin{equation}
\label{erdm}
e_r(d,m) := \mathcal Max_{F_1, {\delta}ots , F_r} \left| V(F_1, {\delta}ots , F_r)({\mathcal Mathbb F}_q) \right|,
{\mathbf e}nd{equation}
where the maximum is over all possible families $\{F_1, {\delta}ots , F_r\}$ of $r$ linearly independent homogeneous polynomials of degree $d$ in $ {\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]$. Note that the condition on linear independence implies that $r$ can be at most ${\beta}inom{m+d}{d}$. Note also that an obvious upper bound for $e_r(d,m)$ is $\mathsf{p}_m$,  where for $j\in \mathsf{Z}Z$, by $\mathsf{p}_j$ we denote $|{\mathbb P}^j({\mathcal Mathbb F}_q)|$, i.e., $\mathsf{p}_j:= q^j + q^{j-1} + {\delta}ots + q + 1$ if $j\ge 0$, and 
$\mathsf{p}_j:=0$ if $j< 0$.

Explicit determination of $e_r(d,m)$ is an open problem, in general,  and it has been of some interest for about two decades. 
While it is easy to see that $e_r(1,m) = \mathsf{p}_{m-r}$ for $r\le m+1$ and $e_r(d,1)= d-r+1$ for $r\le d+1 \le q$ (see, e.g., \cite[\S\,2.1]{DG2}), the case of $r=1$ is rather nontrivial. Here it was conjectured by M. Tsfasman that

{\beta}egin{equation}
\label{TConj}
e_1(d,m) = dq^{m-1} + \mathsf{p}_{m-2}  \quad \mathcal Mathcal Text{for } d \le q.
{\mathbf e}nd{equation}
This was subsequently proved by Serre \cite{Se} and, independently, by S{\o}rensen \cite{So} in 1991.
In the general case, an intricate formula for $e_r(d,m)$ for $d< q-1$ was conjectured by Tsfasman and Boguslavsky (cf. \cite{Bog, DG}), and this was proved in the affirmative by Boguslavsky \cite{Bog} in 1997 for $r=2$. The case of $r>2$ remained open for a considerable time.

Eventually, it was proved in \cite{DG2} and \cite{DG} that the conjectural formula of Tsfasman and Boguslavsky is true if $r\le m+1$, and it can be false if $r> m+1$. In \cite{DG2}, a new conjectural formula for $e_r(d,m)$ was proposed for many (but not all) values of $r$, namely  
for $r\le {\beta}inom{m+d-1}{d-1}$. We will refer to this as the {\mathbf e}mph{incomplete conjecture}. To state it, let us first define an important combinatorial quantity whose genesis lies in the work of Heijnen and Pellikaan \cite{HP} related to an affine counterpart of the problem of finding $e_r(d,m)$. 
For $1\le r \le {\beta}inom{m+d}{d}$, we define
$$
H_r(d,m):= \mathcal Mathcal Sum_{i=1}^m {\alpha}lpha_i q^{m-i}, \quad \mathcal Mathcal Text{where $({\alpha}lpha_1, {\delta}ots, {\alpha}lpha_m)$ is the $r^{\rm th}$ element of } Q^m_{\le d},
$$
and where $Q^m_{\le d}$ denotes the collection, ordered in descending lexicographic order, of all

$m$-tuples $({\beta}eta_1, {\delta}ots , {\beta}eta_m)$ of integers satisfying $0\le {\beta}eta_i <q$ for $i=1, {\delta}ots , m$ and ${\beta}eta_1+\cdots + {\beta}eta_m \le d$. For example, if $d<q$, then $H_1(d,m) = dq^{m-1}$ and $H_{{\beta}inom{m+d}{d}}(d,m)=0$,

since $(d,0, {\delta}ots , 0)$ and $(0,0, {\delta}ots , 0)$ are clearly the first and the last $m$-tuples of $Q^m_{\le d}$ 
in descending lexicographic order. As a convention, we set
{\beta}egin{equation}
\label{convention}

H_0(d,m) := q^m \mathcal Mathcal Text{ for } d,m\ge 0
 \quad \mathcal Mathcal Text{and} \quad H_1(d,m) := 0  \mathcal Mathcal Text{ if $d=0$ or $m=0$}.

{\mathbf e}nd{equation}
In this way, $H_r(d,m)$ is defined for all nonnegative integers $r,d,m$ with $r \le {\beta}inom{m+d}{d}$.
The ``incomplete conjecture" of 
\cite{DG2} can now be stated as follows.

{\beta}egin{equation}
\label{IC}
e_r(d,m) = H_r(d-1,m) + \mathsf{p}_{m-1} \quad \mathcal Mathcal Text{ for $1\le r \le{\beta}inom{m+d-1}{d-1}$ and $1\le d < q$.}
{\mathbf e}nd{equation}
For example, if $r=1$, then this says that $e_1(d,m) = (d-1)q^{m-1} + \mathsf{p}_{m-1}$, which agrees with the Serre-S{\o}rensen formula {\mathbf e}qref{TConj}. Note also that {\mathbf e}qref{IC} holds trivially when $d=1$ or $m=1$. Results of \cite{DG2} prove {\mathbf e}qref{IC} in the affirmative if $r\le m+1$ and $d < q-1$. The validity of {\mathbf e}qref{IC} was extended further in \cite{BDG} to $r\le {\beta}inom{m+2}{2}$ and $1< d < q$. This, then, is currently the best known general result as far as an explicit determination of $e_r(d,m)$ is concerned. Apart from this, the last few values of $e_r(d,m)$ were determined in \cite{DG3} using the connection with coding theory (explained in Section \ref{sec:codes})
 and the work of S{\o}rensen \cite{So};
more precisely, it is shown in \cite[Thm. 4.7]{DG3} that
{\beta}egin{equation}
\label{LastFew}
e_{{\beta}inom{m+d}{d} - t} (d,m) = t \quad \mathcal Mathcal Text{for } t=0,1, {\delta}ots , d.
{\mathbf e}nd{equation}

We are now ready to describe the main results of this paper. First, we extend {\mathbf e}qref{IC} to a conjectural formula for $e_r(d,m)$ for all permissible values of $r,d,m$ with $d<q$. To state this ``complete conjecture'', let us first observe that
{\beta}egin{equation}
\label{Pascal}
{\beta}inom{m+d}{d} = {\beta}inom{m+d-1}{d-1} + {\beta}inom{m+d-2}{d-1} + \cdots + {\beta}inom{d-1}{d-1}
{\mathbf e}nd{equation}
and that 
for any positive integer $r <  {\beta}inom{m+d}{d}$, there are unique integers $i,j$ 
such that
$$
r = {\beta}inom{m+d-1}{d-1} 
+ \cdots + {\beta}inom{m+d-i}{d-1} + j, 
\ \,
0\le i \le m, \mathcal Mathcal Text{ and } 0 \le j <  {\beta}inom{m+d-i-1}{d-1}.
$$
By convention, and in accordance with {\mathbf e}qref{Pascal}, we set $i:=m$ and \hbox{$j:=  {\beta}inom{m+d-i-1}{d-1}=1$} when $r =  {\beta}inom{m+d}{d}$. With $i$ and $j$ thus defined (for a given value of $r$),
the ``complete conjecture" states that
{\beta}egin{equation}
\label{CC}
e_r(d,m) = H_j(d-1,m-i) + \mathsf{p}_{m-i-1} \quad \mathcal Mathcal Text{ for $1\le r \le{\beta}inom{m+d}{d}$ and $1\le d < q$.}
{\mathbf e}nd{equation}
Note that if $r < {\beta}inom{m+d-1}{d-1}$, then $i=0$ and $j=r$, whereas if $r={\beta}inom{m+d-1}{d-1}$, then
$i=1$ and $j=0$. Thus {\mathbf e}qref{CC} reduces to {\mathbf e}qref{IC} in this case, thanks to our conventions.  In particular, from \cite[Thm. 5.3]{BDG}, we see that {\mathbf e}qref{CC} holds in the affirmative if $r\le {\beta}inom{m+2}{2}$.

We provide further evidence for the ``complete conjecture" in this paper by showing that it holds in the affirmative for
an additional $md$ values of $r$, namely for
$$
r =\! {\beta}inom{m+d-1}{d-1}  + \cdots + {\beta}inom{m+d-i}{d-1} - t \quad \mathcal Mathcal Text{where } 1\le i \le m \mathcal Mathcal Text{ and } 0 \le t \le d-1;
$$
in fact, for $r$ as above, we obtain $e_r(d,m) =  \mathsf{p}_{m-i} + t$. These results 

are also valid when $i=m+1$, but in view of {\mathbf e}qref{Pascal}, this case is 
already  covered by  {\mathbf e}qref{LastFew}.	

In the general case, we show that the conjectural formula is always a lower bound even when $d=q$, that is,
{\beta}egin{equation}
 \label{LB}
e_r(d,m) \ge H_j(d-1,m-i) + \mathsf{p}_{m-i-1} \quad \mathcal Mathcal Text{for $1\le r \le{\beta}inom{m+d}{d}$ and $1\le d \le q$.}
{\mathbf e}nd{equation}
The conjectural formula {\mathbf e}qref{CC} as well as the 
lower bound {\mathbf e}qref{LB} for $e_r(d,m)$ can be  described by the alternative formula 
$$
\mathsf{p}_{s_d-d} +  \lfloor q^{s_{d-1}-d+1} \rfloor+ \lfloor q^{s_{d-2}-d+2} \rfloor + \cdots + \lfloor q^{s_1-1} \rfloor, 

$$
where $s_1, {\delta}ots , s_d$ are unique integers satisfying the $d$-binomial expansion
$$
{\beta}inom{m+d}{d} - r = {\beta}inom{s_d}{d} + {\beta}inom{s_{d-1}}{d-1} + \cdots + {\beta}inom{s_1}{1} \quad \mathcal Mathcal Text{and} \quad 
s_d > s_{d-1} > \cdots > s_1 \ge 0.
$$

We also find in this paper an explicit upper bound for $e_r(d,m)$ using methods from extremal combinatorics and a projective counterpart of $H_r(d,m)$, that we denote by $K_r(d,m)$. More precisely, we show that 
for $1\le r \le{\beta}inom{m+d}{d}$ and $1\le d < q$,
{\beta}egin{equation}
 \label{UB}
e_r(d,m) \le K_r(d,m), \quad \mathcal Mathcal Text{where} \quad K_r(d,m) := \mathcal Mathcal Sum_{i=0}^{m}  a_i \mathsf{p}_{m-i-1},

{\mathbf e}nd{equation}
and where $(a_0, a_1, {\delta}ots , a_m)$ is the $r$-th element, in descending lexicographic order, of the set of all $(m+1)$-tuples $(b_0, b_1, {\delta}ots , b_m)$ of nonnegative integers satisfying $b_0+b_1+ \cdots + b_m = d$. It is also shown that this upper bound is attained for several values of $r$. In turn, this plays a crucial role in ascertaining the validity of {\mathbf e}qref{CC} for the additional $md$ values of $r$ mentioned earlier.

The determination of $e_r(d,m)$ is directly related to the determination of the generalized Hamming weights (also known as higher weights) of 
the projective Reed-Muller codes $\mathrm{PRM}_q(d,m)$, which go back to Lachaud \cite{La}. This connection has been explained in \cite[\S\,4]{DG3} when $d\le q$. We elucidate it further in Section \ref{sec:codes} by noting that in general (when $d$ can be larger than $q$), it is more natural to consider a variant of $e_r(d,m)$, called $\overline{e}_r(d,m)$, wherein one takes into account the vanishing ideal of ${\mathbb P}^m({\mathcal Mathbb F}_q)$. This also brings to the fore a basic notion of projective reduction that was enunciated in \cite{BDG18}. We remark that the affine counterpart of the problem of determining $\overline{e}_r(d,m)$ corresponds to determining the generalized Hamming weights of Reed-Muller codes $\mathrm{RM}_q(d,m)$, and this has been solved by V. Wei \cite{W} when $q=2$, and by Heijnen and Pellikaan \cite{HP}, in general. (See also \cite{BD}.)

The methods used in proving the main results of this paper differ significantly from those in our earlier works such as \cite{DG2} and \cite{BDG}. Here we adopt a combinatorial approach and the groundwork for this has been laid in \cite{BDG18} where a {\mathbf e}mph{projective footprint bound} for the number of ${\mathcal Mathbb F}_q$-rational points of arbitrary projective algebraic varieties defined over ${\mathcal Mathbb F}_q$ was obtained. This groundwork is combined in this paper with methods from extremal combinatorics and a culmination of ideas such as the Kruskal-Katona Theorem, a lemma of Wei \cite[Lem. 6]{W}, the Clements-Lindstr\"om Theorem, and a theorem of Heijnen \cite[Appendix A]{H} (see also \cite[Thm. 5.7]{HP} and \cite[Thm. 3.8]{BD}).
These feed into the results in Sections \ref{combin}, \ref{combin2} and \ref{sec:er} that form the technical core of this paper. 
For a leisurely introduction to extremal combinatorics and some of the classical results mentioned above, one  may refer to

the book of Anderson \cite{A}. 

\mathcal Mathcal Section{A Lower Bound and a Conjecture}
\label{sec:new}

In this section, we shall prove the lower bound {\mathbf e}qref{LB} and formally state our ``complete conjecture" concerning $e_r(d,m)$. Recall that $e_r(d,m)$  is defined by {\mathbf e}qref{erdm} for positive numbers $r,d,m$ with $r \le {\beta}inom{m+d}{d}$. One can extend the definition to include the trivial cases when $r$ or $d$ or $m$ is zero, or simply, set the following convention.
 {\beta}egin{equation}
\label{convention-erdm}

e_0(d,m) := \mathsf{p}_m \mathcal Mathcal Text{ for } d,m\ge 0
 \quad \mathcal Mathcal Text{and} \quad e_1(d,m) := 0  \mathcal Mathcal Text{ if $d=0$ or $m=0$}.

{\mathbf e}nd{equation}
Thus $e_r(d,m)$ is defined for all nonnegative integers $r,d,m$ satisfying $r \le {\beta}inom{m+d}{d}$.

In the remainder of this section, $m$ denotes a positive integer and, as usual, ${\mathcal Mathbb F}_q$ denotes the finite field with $q$ elements.

\mathcal Mathcal Subsection{Zeros of Affine Varieties over Finite Fields}\label{subsec:Hr1}
Let $r, d$ be any nonnegative integers. 
Given any polynomials $f_1, {\delta}ots , f_r\in {\mathcal Mathbb F}_q[x_1, {\delta}ots , x_m]$, we shall denote
by $Z(f_1, {\delta}ots, f_r)({\mathcal Mathbb F}_q)$ the set of all ${\mathcal Mathbb F}_q$-rational points of the affine algebraic variety in ${\mathbb A}^m$ (over an algebraic closure of ${\mathcal Mathbb F}_q$) defined by $f_1, {\delta}ots , f_r$; in other words,
$$
Z(f_1, {\delta}ots, f_r)({\mathcal Mathbb F}_q) =\{ (a_1,{\delta}ots , a_m)\in {\mathcal Mathbb F}_q^m : f_j(a_1,{\delta}ots , a_m) =0 \mathcal Mathcal Text{ for all } j=1,{\delta}ots ,r\}.  
$$
Note that if $r=0$, then $Z(f_1, {\delta}ots, f_r)({\mathcal Mathbb F}_q) ={\mathcal Mathbb F}_q^m$. 
We shall now define a natural affine analogue of  $e_{r}(d,m)$.  
For $0\le r \le {\beta}inom{m+d}{d}$, we define 
$$
e^{{\mathbb A}}_r(d,m):=\mathcal Max_{f_1, {\delta}ots, f_r} |Z(f_1, {\delta}ots, f_r)({\mathcal Mathbb F}_q)|,
$$
where the maximum is taken over families of $r$ linearly independent polynomials $f_1, {\delta}ots , f_r$ of degree $\le d$ in ${\mathcal Mathbb F}_q[x_1, {\delta}ots , x_m]$.

As explained in \cite[\S 2.1]{BDG}, the result of Heijnen and Pellikaan \cite[Thm. 5.10]{HP} in the case $d<q$ can be stated as follows. Here $H_r(d,m)$ is as defined in the introduction, including the conventions given in {\mathbf e}qref{convention}. 

{\beta}egin{theorem}[Heijnen-Pellikaan]
\label{Hr1}

If $0\le d < q$ and $0\le r \le
{\beta}inom{m+d}{d} $, then
$$
{e}^{{\mathbb A}}_r(d,m)  = H_r (d, m).

$$
{\mathbf e}nd{theorem}

A more general version of this result will be discussed later (in \S\,\ref{subsec:RedEqns}).

\mathcal Mathcal Subsection{A Lower Bound for $e_r(d,m)$}
We begin by noting a simple and well-known fact whose proof is outlined for the sake of completeness.

{\beta}egin{lemma}\label{lem:binom}
Let $d$ be a positive integer. Then
{\beta}egin{equation}
\label{Pascal2}
{\beta}inom{m+d}{d} = \mathcal Mathcal Sum_{a=1}^{m+1}{\beta}inom{m+d-a}{d-1} .

{\mathbf e}nd{equation}

Moreover, for any nonnegative integer $r <  {\beta}inom{m+d}{d}$, there are unique integers $i,j$ with

{\beta}egin{equation}
\label{BinomExp}
r = j + \mathcal Mathcal Sum_{a=1}^{i}{\beta}inom{m+d-a}{d-1} , \quad
0\le i \le m, \quad \mathcal Mathcal Text{and} \quad 0 \le j <  {\beta}inom{m+d-i-1}{d-1}.
{\mathbf e}nd{equation}
{\mathbf e}nd{lemma}

{\beta}egin{proof}
The identity in {\mathbf e}qref{Pascal2} follows easily from induction on $m$. 
If $0\le r <  {\beta}inom{m+d}{d}$, then  the largest nonnegative integer $i$ such that $\mathcal Mathcal Sum_{a=1}^{i}{\beta}inom{m+d-a}{d-1} \le r$ clearly satisfies $0\le i \le m$, thanks to {\mathbf e}qref{Pascal2}.
Thus
{\mathbf e}qref{BinomExp} holds with $j: = r - \mathcal Mathcal Sum_{a=1}^{i}{\beta}inom{m+d-a}{d-1}$.
{\mathbf e}nd{proof}

We remark that although $m$ is assumed to be a fixed positive integer, the identity in {\mathbf e}qref{Pascal2} holds trivially also when $m=0$, and this fact may be tacitly assumed in the sequel. Our next result is 
a general lower bound for $e_r(d,m)$ when $d\le q$.

{\beta}egin{theorem}\label{lem:lower}
Let $d,r$ be positive integers with

$d \le q$ and $r \le {\beta}inom{m+d}{d}$,
and let $i,j$ be as in 
{\mathbf e}qref{BinomExp}
if 
$r < {\beta}inom{m+d}{d}$, while  $i:=m$ and $j:=  {\beta}inom{m+d-i-1}{d-1}=1$ if 
$r = {\beta}inom{m+d}{d}$. Then

$$
e_r(d,m) \ge H_j(d-1,m-i)+\mathsf{p}_{m-i-1}.
$$

{\mathbf e}nd{theorem}

{\beta}egin{proof}
If $r = {\beta}inom{m+d}{d}$, then clearly, $e_r(d,m) =0$ and 
$H_1(d-1, m-m) + \mathsf{p}_{m-m-1} = 0$, 
as per the conventions in equation {\mathbf e}qref{convention}. Now assume that
$r < {\beta}inom{m+d}{d}$, and let $i, j$ be as in {\mathbf e}qref{BinomExp}. We shall prove the desired inequality
by producing a set $B$ 
of $r$ linearly independent polynomials in ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_{m}]_{d}$ with the property 
that $|V(B)({\mathcal Mathbb F}_q)| = H_j(d-1,m-i)+\mathsf{p}_{m-i-1}$.

First, for each positive integer
$a\le i$, let $\mathcal Mathcal{B}_{a}$ be a basis of the ${\mathcal Mathbb F}_q$-vector space $x_{m-a+1}{\mathcal Mathbb F}_q[x_0,{\delta}ots,x_{m-a+1}]_{d-1}$; for instance, 
$\mathcal Mathcal{B}_{a}$ can be the set of monomials of
degree $d$ in $x_0,{\delta}ots,x_{m-a+1}$ that are divisible by $x_{m-a+1}$. Clearly, the sets $\mathcal Mathcal{B}_{a}$ are disjoint and $|\mathcal Mathcal{B}_{a}| = {\beta}inom{m+d-a}{d-1}$ for $1\le a \le i$. Note ~that
$$
V\Big({\beta}igcup_{a=1}^i \mathcal Mathcal{B}_{a} \Big)({\mathcal Mathbb F}_q)=\{(a_0:\cdots:a_m) \in {\mathbb P}^m({\mathcal Mathbb F}_q) \, | \, a_m=\cdots=a_{m-i+1}=0\},
$$

Next,  since $d-1< q$, by Theorem \ref{Hr1}, we obtain $j$ linearly independent polynomials $f_1, {\delta}ots, f_j$ each
of degree 
at most $d-1$
in the polynomial ring ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_{m - i - 1}]$ such that
$
|Z_{m-i}(f_1, {\delta}ots, f_j) ({\mathcal Mathbb F}_q)| = H_j (d-1, m - i),
$
where $Z_{m-i}(f_1, {\delta}ots, f_j)$ denotes the set of common zeroes of $f_1, {\delta}ots, f_j$ in the $(m-i)$ dimensional affine subspace  of ${\mathbb P}^m$ given by  $\{ [a_0:\cdots:a_m] : a_{m-i} =1, \; a_s = 0 \ \mathcal Mathcal Text{for }
m-i< s \le m\}$. 
Let $F_1, {\delta}ots , F_j$ be the 
polynomials 
obtained, respectively, by homogenizing $f_1, {\delta}ots , f_j$ to degree $d$ with respect to the variable $x_{m-i}$.
Clearly, $F_1, {\delta}ots , F_j \in {\mathcal Mathbb F}_q[x_0, {\delta}ots, x_{m - i }]_d$~and  they are linearly independent.

Also, ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_{m - i }] \cap \mathcal Mathcal{B}_{a}$ is empty

for each $a=1, {\delta}ots , i$. Consequently, $B$ is a linearly independent subset of ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_{m }]_d$~and
$$
|B| =  j + \mathcal Mathcal Sum_{a=1}^i {\beta}inom{m+d-a}{d-1}  = r \quad \mathcal Mathcal Text{where} \quad
B:= \{F_1, {\delta}ots , F_j\} \cup \Big({\beta}igcup_{a=1}^i \mathcal Mathcal{B}_{a} \Big),
$$
with the 
convention that the relevant sets are empty if $j=0$ or $i=0$.
Further, by intersecting $V(B) = V(F_1, {\delta}ots , F_j) \cap V(\cup_{a=1}^i \mathcal Mathcal{B}_{a})$ with the affine patch $\{x_{m-i}=1\}$ and the hyperplane $\{x_{m-i}=0\}$ of ${\mathbb P}^m$, we see that
$|V(B)({\mathcal Mathbb F}_q)|$ equals
$$

|Z_{m-i}(f_1, {\delta}ots, f_j) ({\mathcal Mathbb F}_q)|  + \left| \{ [a_0:\cdots:a_m] \in {\mathbb P}^m({\mathcal Mathbb F}_q) : a_m=\cdots=a_{m-i}=0\} \right|,
$$

which is $H_j(d-1,m-i)+\mathsf{p}_{m-i-1}$, as desired.

{\mathbf e}nd{proof}

We remark that when $d=q$, the lower bound in Theorem \ref{lem:lower} is not attained, in general. This is shown in \cite[\S\,6]{BDG}, where exact values of $e_r(q,m)$ are obtained for $1\le r \le m+1$. 

\mathcal Mathcal Subsection{The ``Complete Conjecture"}
It appears plausible that the lower bound in Theorem \ref{lem:lower} is attained when $d< q$. More precisely, we conjecture the following.

{\beta}egin{conjecture}\label{conj:extended}

Let $d,r$ be 
integers with
$1\le d < q$ and $1\le r \le {\beta}inom{m+d}{d}$,
and let $i,j$ be as in 
{\mathbf e}qref{BinomExp}
if 
$r < {\beta}inom{m+d}{d}$, while  $i:=m$ and $j:=  {\beta}inom{m+d-i-1}{d-1}$ if 
$r = {\beta}inom{m+d}{d}$. Then
$$
e_r(d,m)=H_j(d-1,m-i)+\mathsf{p}_{m-i-1}.
$$
{\mathbf e}nd{conjecture}

As noted in the introduction, if $1 \le r \le {\beta}inom{m+d-1}{d-1}$, then Conjecture \ref{conj:extended} reduces to \cite[Conjecture 6.6]{DG2}. The case $d=1$ of Conjecture \ref{conj:extended} holds trivially, while the case $d=2$ follows from the work of Zanella \cite{Z}. Further, it was shown in \cite{BDG} that Conjecture \ref{conj:extended} holds when $2 \le d<q$ and $r \le {\beta}inom{m+2}{2}$.

We will now describe an alternative formulation of Conjecture \ref{conj:extended} 
deduced from the alternative description of $H_r(d,m)$ given in \cite{B}. Before stating it, let us recall that given any positive integer $d$, we can express every nonnegative integer $N$ as 
$$
N =\mathcal Mathcal Sum_{a=1}^d {\beta}inom{s_a}{a}

 \quad \mathcal Mathcal Text{for unique $s_a\in \mathsf{Z}Z$ 
with} \quad
s_d > s_{d-1} > \cdots > s_1 \ge 0.
$$
This is called the {\mathbf e}mph{$d$-binomial representation} of $N$ or the {\mathbf e}mph{$d$-th Macaulay representation} of $N$. 
We will find it convenient to consider $m_a:= s_a -a$ for $1\le a \le d$ so as to write the above expansion for $N$ as 
{\beta}egin{equation}\label{eq:MacaulayRep}
N = \mathcal Mathcal Sum_{a=1}^d {\beta}inom{m_a+a}{a} 

\ \mathcal Mathcal Text{ for unique $m_a\in \mathsf{Z}Z$ 
with } \
m_d \ge m_{d-1} \ge \cdots \ge m_1 \ge -1.
{\mathbf e}nd{equation}
We may refer to $(m_d, {\delta}ots , m_1)$ as the {\mathbf e}mph{Macaulay $d$-tuple} corresponding to $N$. Observe that if $M$ is any nonnegative integer, then 

{\beta}egin{equation}\label{eq:MacaulayCoeff}
0\le N <{\beta}inom{M+d}{d} \mathcal Longrightarrow 
M -1 \ge m_d \ge m_{d-1} \ge \cdots \ge m_1 \ge -1.
{\mathbf e}nd{equation}
 The following result is a direct consequence of the proof of \cite[Thm. 3.1]{B} and we remark that its proof

does not use the theorem of Heijnen-Pellikaan (Theorem \ref{Hr}). 

{\beta}egin{lemma}\label{lem:pabe}
Assume that $1\le d < q$ and $0 \le r \le {\beta}inom{m+d}{d}$. Suppose the Macaulay $d$-tuple corresponding to 

${\beta}inom{m+d}{d} -r$ is $(m_d, {\delta}ots , m_1)$. Then 

$$
H_r(d,m) = \mathcal Mathcal Sum_{a=1}^d \lfloor q^{m_a} \rfloor.
$$ 
{\mathbf e}nd{lemma}

{\beta}egin{proof}

If $r=0$, then  $H_r(d,m)=q^m$, in accordance with our convention {\mathbf e}qref{convention}. On the other hand, the
Macaulay $d$-tuple corresponding to ${\beta}inom{m+d}{d}$ is clearly $(m, -1, {\delta}ots , -1)$. So the desired equality holds when $r=0$. 
For $1 \le r \le {\beta}inom{m+d}{d}$, the desired equality 

 is a special case of \cite[Thm. 3.1]{B} and its proof, since for $d< q$, the dimension $\rho_q(d,m)$ of the Reed-Muller code $\mathrm{RM}_q(d,m)$ is 
${\beta}inom{m+d}{d}$.
{\mathbf e}nd{proof}

{\beta}egin{corollary}\label{cor:MacExp}
Assume that $1\le d \le q$ and $1\le r \le {\beta}inom{m+d}{d}$. Let $i,j$ be as in 
{\mathbf e}qref{BinomExp}
if 
$r < {\beta}inom{m+d}{d}$, while  $i:=m$ and $j:=  {\beta}inom{m+d-i-1}{d-1}$ if 
$r = {\beta}inom{m+d}{d}$. Also let $(m_d, {\delta}ots , m_1)$ be the Macaulay $d$-tuple corresponding to 

${\beta}inom{m+d}{d} -r$.  Then
$$

H_j(d-1,m-i)+\mathsf{p}_{m-i-1} = \mathsf{p}_{m_d} + \mathcal Mathcal Sum_{a=1}^{d-1} \lfloor q^{m_a} \rfloor.
$$
{\mathbf e}nd{corollary}

{\beta}egin{proof}
First, note that if $d=1$, then $i=r$ and $j=0$, and so in view of {\mathbf e}qref{convention}, $H_j(d-1, m-i) +\mathsf{p}_{m-i-1} =
q^{m-r} + \mathsf{p}_{m-r-1} =\mathsf{p}_{m-r}$. Also,  the Macaulay $1$-tuple corresponding to $m+1-r$  is clearly $(m-r)$. Thus 
the desired equality holds when $d=1$. 

Likewise, if $i=m$, then clearly $j$ is $0$ or $1$ and 
${\beta}inom{m+d}{d} -r$ is $1$ or $0$, thanks to {\mathbf e}qref{Pascal2}; in this case, $m_a=-1$ for $1\le a < d$, whereas $m_d$ is $0$ or $-1$ according as $j$ is $0$ or $1$. Hence, in view of {\mathbf e}qref{convention}, the desired equality also holds when $i=m$. 

Now suppose $d>1$ and $0\le i < m$.    
Then  $1\le d-1 < q$ and $1\le  r < {\beta}inom{m+d}{d}$.  

Using the equality in {\mathbf e}qref{BinomExp} 

together with {\mathbf e}qref{Pascal2}, we can write 
{\beta}egin{eqnarray*}
{\beta}inom{m+d}{d} - r & =&  
{\beta}inom{m+d-i-1}{d-1} - j 
+ \mathcal Mathcal Sum_{a=1}^{m-i} {\beta}inom{m+d-i-a-1}{d-1}  \\
 & =&  {\beta}inom{m+d-i-1}{d} +  {\beta}inom{m+d-i-1}{d-1} - j  ,
{\mathbf e}nd{eqnarray*}
where the last equality follows from 
 {\mathbf e}qref{Pascal2} with $m$ replaced by $m-i-1$. In case $j=0$, the last expression is simply ${\beta}inom{m+d-i}{d}$, and in this case $m_d=m-i$ while $m_a=-1$ for $1\le a < d$. Thus, in view of {\mathbf e}qref{convention}, we see that when $j=0$, 
$$

H_j(d-1,m-i)+\mathsf{p}_{m-i-1} = q^{m-i} +\mathsf{p}_{m-i-1} =\mathsf{p}_{m-i} =
\mathsf{p}_{m_d} + \mathcal Mathcal Sum_{a=1}^{d-1} \lfloor q^{m_a} \rfloor,
$$
as desired. Now suppose $0< j < {\beta}inom{m+d-i-1}{d-1}$. By {\mathbf e}qref{eq:MacaulayCoeff} and Lemma \ref{lem:pabe}, it follows that if $(\mathcal Mu_{d-1}, {\delta}ots , \mathcal Mu_1)$ is the Macaulay $(d-1)$-tuple corresponding to $ {\beta}inom{m+d-i-1}{d-1} - j$, then 
$m-i-1 \ge \mathcal Mu_{d-1} \ge {\delta}ots \ge \mathcal Mu_1$, and further, 
{\beta}egin{equation}\label{eq:Hj}
{\beta}inom{m+d-i-1}{d-1} - j  =  \mathcal Mathcal Sum_{a=1}^{d-1} {\beta}inom{\mathcal Mu_a+a}{a} \quad \mathcal Mathcal Text{and} \quad 
H_j(d-1,m-i) = \mathcal Mathcal Sum_{a=1}^{d-1} \lfloor q^{\mathcal Mu_a} \rfloor .
{\mathbf e}nd{equation}
Substituting this in the expression obtained earlier for ${\beta}inom{m+d}{d} - r$, we see that 
$$
{\beta}inom{m+d}{d} - r  = {\beta}inom{m+d-i-1}{d} + \mathcal Mathcal Sum_{a=1}^{d-1} \lfloor q^{\mathcal Mu_a} \rfloor .
$$

This 
together with 
the uniqueness of Macaulay $d$-tuples implies that $m_d = m-i-1$ and $m_a = \mathcal Mu_a$ for $1\le a < d$. 
Consequently,  
{\mathbf e}qref{eq:Hj} yields the desired equality

{\mathbf e}nd{proof}

In view of Corollary \ref{cor:MacExp}, 
the lower bound in Theorem \ref{lem:lower} and 
the conjectural formula for $e_r(d,m)$ in Conjecture \ref{conj:extended} can be written as 
$$
\mathsf{p}_{m_d} + \mathcal Mathcal Sum_{a=1}^{d-1} \lfloor q^{m_a} \rfloor,
$$
where $(m_d, {\delta}ots, m_1)$ is the Macaulay $d$-tuple corresponding to ${\beta}inom{m+d}{d} -r$.  

\mathcal Mathcal Section{Projective Reduction, Shadows and Footprints}
\label{sec:prelim} 

In this section, we review some preliminary notions and results, which will be useful to us in the remainder of the paper. Throughout this section, $m$ denotes a positive integer and ${\mathcal Mathbb F}_q$ the finite field with $q$ elements.

\mathcal Mathcal Subsection{Projective Reduction}
\label{subsec:projred}
Recall that a monomial $\mathcal Mu \in {\mathcal Mathbb F}_q[x_1, {\delta}ots, x_m]$ given by $\mathcal Mu = x_1^{{\alpha}lpha_1} \cdots x_m^{{\alpha}lpha_m}$ is said to be \mathcal Mathcal Textit{reduced} if $0 \le {\alpha}lpha_i \le q-1$ for all $i = 1, {\delta}ots, m$ and a polynomial $F \in {\mathcal Mathbb F}_q[x_1, {\delta}ots, x_m]$ is said to be reduced if it is an ${\mathcal Mathbb F}_q$-linear combination of reduced monomials. It is 
well-known (see, e.g., \cite[Ch. 2]{Joly} or \cite{G}) 
that the set of all reduced monomials gives rise to a basis of the ${\mathcal Mathbb F}_q$-vector space ${\mathcal Mathbb F}_q[x_1, {\delta}ots, x_m] / I ({\mathbb A}^m ({\mathcal Mathbb F}_q))$, where $I ({\mathbb A}^m ({\mathcal Mathbb F}_q))$ denotes the ideal consisting of all polynomials in ${\mathcal Mathbb F}_q[x_1, {\delta}ots, x_m]$ vanishing at every point of ${\mathbb A}^m ({\mathcal Mathbb F}_q)$. More precisely, any element of ${\mathcal Mathbb F}_q[x_1, {\delta}ots, x_m] / I ({\mathbb A}^m ({\mathcal Mathbb F}_q))$ can be written uniquely as $\mathcal Mathcal Tilde{f} + I ({\mathbb A}^m ({\mathcal Mathbb F}_q))$ for some reduced polynomial $\mathcal Mathcal Tilde{f}$.

A projective analogue of the above notion and result is given in \cite[\S\,2]{BDG18}.
We recall this below. Here, and hereafter,

we denote by $\mathcal Mathbb M$ the set of all monomials in the $m+1$ variables $x_0,{\delta}ots, x_{m}.$
{\beta}egin{definition}
For a nonnegative integer $a$, 
let $\overline{a}$ be the unique integer satisfying
$$
0 \le \overline{a} < q\quad \mathcal Mathcal Text{and} \quad
\overline{a} =
{\beta}egin{cases}
0  \ \ \mathcal Mathrm{if} \  a=0 \\
\mathcal Mathcal Tilde{a}  \ \ \mathcal Mathrm{if} \ a > 0 \ \ \mathcal Mathrm{and} \  \mathcal Mathcal Tilde{a} {\mathbf e}quiv a({\rm mod} \ {q-1}), \ \mathcal Mathrm{where} \ 0 < \mathcal Mathcal Tilde{a} \le q-1.
{\mathbf e}nd{cases}$$
Let $\mathcal Mu  \in \mathcal Mathbb M$. If $\mathcal Mu \neq 1$, then we may write $\mathcal Mu =x_0^{a_0}\cdots x_{\mathbf e}ll^{a_{\mathbf e}ll}$, where $0 \le {\mathbf e}ll \le m$ and $a_0, {\delta}ots , a_{\mathbf e}ll$ are nonnegative integers with $a_{\mathbf e}ll>0$. Define

$$
\overline{\mathcal Mu}:=x_0^{\overline{a_0}} \cdots x_{{\mathbf e}ll-1}^{\overline{a_{{\mathbf e}ll-1}}} x_{\mathbf e}ll^{a_{\mathbf e}ll+\mathcal Mathcal Sum_{j=0}^{{\mathbf e}ll-1}(a_j-\overline{a_j})}.
$$
If $\mathcal Mu=1$, then we define $\overline{\mathcal Mu}=1$. Note that $\overline{\mathcal Mu}\in \mathcal Mathbb M$ with ${\delta}eg \overline{\mathcal Mu} = {\delta}eg \mathcal Mu$. We call $\overline{\mathcal Mu}$ the {\mathbf e}mph{projective reduction} of $\mathcal Mu$.
Any polynomial $F \in {\mathcal Mathbb F}_q[x_0, {\delta}ots, x_m]$ can be written uniquely as $F = \mathcal Mathcal Sum_{i=1}^n c_i \mathcal Mu_i$ where $c_i \in {\mathcal Mathbb F}_q\mathcal Mathcal Setminus\{0\}$ and $\mathcal Mu_i \in \mathcal Mathbb M$. We define $\overline{F}$, the {\mathbf e}mph{projective reduction} of $F$, as $\overline{F} = \mathcal Mathcal Sum_{i=1}^n c_i \overline{\mathcal Mu_i}$.
A monomial $\mathcal Mu \in \mathcal Mathbb M$ (resp.~polynomial $F \in {\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]$) is said to be \mathcal Mathcal Textit{projectively reduced} if $\overline{\mathcal Mu}=\mathcal Mu$ (resp.~$\overline{F}=F$).
{\mathbf e}nd{definition}
It is easy to see from the definition that a reduced polynomial is projectively reduced. In particular, a polynomial of degree $d \le q-1$ is necessarily reduced and hence projectively reduced. A polynomial of degree $q$ is not necessarily reduced but is always projectively reduced. Clearly, a polynomial of degree $d >q$ may not even be projectively reduced. It is easy to see that if $F\in {\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]$, then
{\beta}egin{equation}\label{eq:redeval}
F(c_0, {\delta}ots , c_m) = \overline{F}(c_0, {\delta}ots , c_m) \quad \mathcal Mathcal Text{for all } (c_0, {\delta}ots , c_m) \in {\mathcal Mathbb F}_q^{m+1}.
{\mathbf e}nd{equation}
For further properties of projective reduction and projectively reduced polynomials we refer to \cite[Proposition 2.2]{BDG18}.

Throughout this article, we 
denote by $\mathcal Mathbb Mb$ the set of projectively reduced monomials in $m+1$ variables $x_0, {\delta}ots , x_m$. Further, for any nonnegative integer $e$, we denote by $\mathcal Mathbb Mb_e$ the set of all projectively reduced monomials in $\mathcal Mathbb Mb$ of degree $e$. Clearly, $\mathcal Mathbb Mb$ equals the disjoint union $\coprod_{e \ge 0}\mathcal Mathbb Mb_e$.

Let $I({\mathbb P}^m ({\mathcal Mathbb F}_q))$ denote the ideal of ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_m]$ generated by the 
homogeneous polynomials that vanish at all points of ${\mathbb P}^m ({\mathcal Mathbb F}_q)$. It was shown by Mercier and Rolland \cite{MR} that this ideal is equal to  the ideal $\Gamma_q({\mathcal Mathbb F}_q)$ of ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_m]$ generated by
$\{x_i^qx_j-x_ix_j^q \mathcal Mid 0 \le i < j \le m\}$.

It was further proved in \cite[Theorem 2.8]{BDG18} that the set $\{x_i^qx_j-x_ix_j^q \mathcal Mid 0 \le i < j \le m\}$ forms a universal Gr\"{o}bner basis for $\Gamma_q({\mathcal Mathbb F}_q)$.
To conclude this subsection, we note that the projectively reduced monomials give rise to a  basis of the ${\mathcal Mathbb F}_q$-vector space ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_m] / I ({\mathbb P}^m ({\mathcal Mathbb F}_q))$.  More precisely, any element of ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_m] / I ({\mathbb P}^m ({\mathcal Mathbb F}_q))$ can be written uniquely as $f + I ({\mathbb P}^m ({\mathcal Mathbb F}_q))$, where $f$ is a projectively reduced polynomial.
For a proof, see 
\cite[Corollary 2.10]{BDG18}.

\mathcal Mathcal Subsection{Shadows and Footprints}
\label{subsec:pfb}

Given $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb M$ and  a nonnegative integer $e$, define

$$
\nabla_e(\mathcal Mathcal S) := \{\mathcal Mu \in \mathcal Mathbb Mb_e : \nu \mathcal Mid \mathcal Mu \ \mathcal Mathrm{for \ some} \ \nu \in \mathcal Mathcal S\} \ \ \mathcal Mathrm{and} \ \ \ \Delta_e(\mathcal Mathcal S):= \mathcal Mathbb Mb_e \mathcal Mathcal Setminus \nabla_e(\mathcal Mathcal S).
$$
The set $\nabla_e(\mathcal Mathcal S)$ is called the \mathcal Mathcal Textit{shadow} of $\mathcal Mathcal S$ in $\mathcal Mathbb Mb_e$, while the set $\Delta_e (\mathcal Mathcal S)$ is known as the \mathcal Mathcal Textit{footprint} of $\mathcal Mathcal S$ in $\mathcal Mathbb Mb_e$.

Recall that by a {\mathbf e}mph{term order} on $\mathcal Mathbb M$, 
one means a total order $\mathsf{p}rec$ 
on the set $\mathcal Mathbb M$ of all monomials in $x_0,{\delta}ots,x_m$ such that (i) $1 \mathsf{p}reccurlyeq \mathcal Mu$ for all $\mathcal Mu\in \mathcal Mathbb M$, and (ii) $\mathcal Mu \nu \mathsf{p}reccurlyeq  \mathcal Mu' \nu$ whenever $\mathcal Mu, \mathcal Mu', \nu \in \mathcal Mathbb M$ are such that $\mathcal Mu \mathsf{p}reccurlyeq \mathcal Mu'$. 

Let  $\mathsf{p}rec$ be  any term order on $\mathcal Mathbb M$ for which $x_0 \mathcal Monord x_1 \mathcal Monord \cdots \mathcal Monord x_m$. For example, we can take $\mathsf{p}rec$ to be the lexicographic order
$\prec_{\mathrm{lex}}$ defined by
{\beta}egin{equation}\label{def:lex}
x_0^{a_0} \cdots x_{m}^{a_{m} } \prec_{\mathrm{lex}}  x_0^{b_0} \cdots x_{m}^{b_{m} }  
\mathcal Longleftrightarrow 
\mathcal Mathcal Text{the first nonzero entry of }\mathcal Mathrm{b}-\mathcal Mathrm{a} \mathcal Mathcal Text{ is positive,}
{\mathbf e}nd{equation}
where $\mathcal Mathrm{b}-\mathcal Mathrm{a}$ denotes the difference tuple $(b_0 - a_0, {\delta}ots , b_m -a_m)$.

Other examples of such term orders are also possible. 
For now, we just fix a  term order $\mathsf{p}rec$ on $\mathcal Mathbb M$ for which $x_0 \mathcal Monord x_1 \mathcal Monord \cdots \mathcal Monord x_m$. 
For a nonzero polynomial $F \in {\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]$, we denote by $\mathrm{lm}_{\mathsf{p}rec}(F)$ or simply $\mathrm{lm}(F)$, the {\mathbf e}mph{leading monomial} of $F$, i.e., the largest monomial (w.r.t $\mathsf{p}rec$) appearing in $F$ with a nonzero coefficient.
For any set $\mathcal Mathcal S$ of nonzero polynomials in ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]$ and any nonnegative integer $e$, we define
$$
\mathrm{lm}(\mathcal Mathcal S):=\{\mathrm{lm}(F) : F \in \mathcal Mathcal S\}, \quad \nabla_e(\mathcal Mathcal S):=\nabla_e(\mathrm{lm}(\mathcal Mathcal S)) \quad  \mathcal Mathrm{and} \quad \Delta_e(\mathcal Mathcal S):=\Delta_e(\mathrm{lm}(\mathcal Mathcal S)).
$$

The following important result from \cite{BDG18} relates footprints in $\mathcal Mathbb Mb_e$ to the number of ${\mathcal Mathbb F}_q$-rational points of projective algebraic varieties defined over ${\mathcal Mathbb F}_q$. 
Here, and hereafter, for an assertion depending on a nonnegative integer $e$, the expression
``for all $e \gg 0$" means that the assertion holds for all large enough values of $e$, i.e., there is a nonnegative integer $e_0$ such  that the assertion holds for all $e\ge e_0$.

{\beta}egin{theorem}[Projective ${\mathcal Mathbb F}_q$-Footprint Bound] 
\label{thm:qfootprint}
Let $\mathcal Mathcal S=\{F_1, {\delta}ots , F_r\}$ 
be a set of nonzero, projectively reduced homogeneous polynomials in ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]$. Write $\mathcal X=V(\mathcal Mathcal S)$ for the corresponding algebraic variety in ${\mathbb P}^m$. Then 
$$
|\mathcal X({\mathcal Mathbb F}_q)| \le |\Delta_e(\mathcal Mathcal S)| \quad \mathcal Mathcal Text{for all } e\gg 0.
$$
{\mathbf e}nd{theorem}

{\beta}egin{proof}

Since $F_1, {\delta}ots , F_r$ are projectively reduced, $\mathrm{lm} (\mathcal Mathcal S) \mathcal Mathcal Subseteq \mathcal Mathbb Mb$. Thus the
notion of footprint $\Delta_e(\mathcal Mathcal S)$ defined above coincides with 
that of projective ${\mathcal Mathbb F}_q$-footprint $\overline{\Delta}_e(\mathcal Mathcal S)$ defined in \cite[Def. 3.10]{BDG18}. 
So the desired result follows from \cite[Thm. 3.12]{BDG18}.
{\mathbf e}nd{proof}

We can decompose 
$\mathcal Mathbb Mb$ into disjoint subsets by considering the last variable appearing in a given monomial. Thus, following \cite{BDG18},
 we define
 $$
 \mathcal Mathbb Mb^{(0)} = \{x_0^a : a \ge 0\} \quad \mathcal Mathcal Text{and  for $1 \le {\mathbf e}ll \le m$,}\quad
 \mathcal Mathbb Mb^{({\mathbf e}ll)}:=\{x_0^{a_0} \cdots x_{{\mathbf e}ll}^{a_{{\mathbf e}ll}} \in \mathcal Mathbb Mb :  a_{\mathbf e}ll >0\}.
 $$

Further, for any 
integers $e, {\mathbf e}ll$ with $e\ge 0$ and $0\le {\mathbf e}ll \le m$, define $\mathcal Mathbb Mb_e^{({\mathbf e}ll)}:= \mathcal Mathbb Mb^{({\mathbf e}ll)} \cap \mathcal Mathbb Mb_{e}$.
Evidently, 
$\mathcal Mathbb Mb = \coprod_{{\mathbf e}ll=0}^m \mathcal Mathbb Mb^{({\mathbf e}ll)}$ and $\mathcal Mathbb Mb_e = \coprod_{{\mathbf e}ll=0}^m \mathcal Mathbb Mb_e^{({\mathbf e}ll)}$.
It is easy to see that 
$$
|\mathcal Mathbb Mb_e^{({\mathbf e}ll)}|=q^{\mathbf e}ll \ \mathcal Mathcal Text{ for } e \ge {\mathbf e}ll(q-1)+1 \quad \mathcal Mathcal Text{and hence} \quad |\mathcal Mathbb Mb_e|=\mathsf{p}_m \ \mathcal Mathcal Text{ for } e \ge m(q-1)+1.
$$
We refer to \cite[Section 2.1]{BDG18} for more details.

The sets $\mathcal Mathbb Mb_e^{({\mathbf e}ll)}$ help us in decomposing the shadows or footprints into several disjoint components. To this end,
we define
{\beta}egin{equation}\label{eq:deltaeell}
\nabla_e^{({\mathbf e}ll)}(\mathcal Mathcal S):=\nabla_e(\mathcal Mathcal S) \cap \mathcal Mathbb Mb_e^{({\mathbf e}ll)}  \quad \mathcal Makebox{and} \quad \Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S):=\Delta_e(\mathcal Mathcal S) \cap \mathcal Mathbb Mb_e^{({\mathbf e}ll)}.
{\mathbf e}nd{equation}
For any 
$\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb$ and any nonnegative integer $e$, it is clear that 
{\beta}egin{equation}\label{eq:disjointshfp}
|\nabla_e(\mathcal Mathcal S)|= \mathcal Mathcal Sum_{{\mathbf e}ll=0}^m |\nabla_e^{({\mathbf e}ll)}(\mathcal Mathcal S)| \quad \mathcal Makebox{and} \quad
|\Delta_e(\mathcal Mathcal S)|= \mathcal Mathcal Sum_{{\mathbf e}ll=0}^m |\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S)|.
{\mathbf e}nd{equation}

Given a nonnegative integer ${\mathbf e}ll \le m$, by specializing the variables $x_{{\mathbf e}ll+1},{\delta}ots,x_m$ to $1$, we
can associate to a subset of 
$\mathcal Mathbb Mb$, a set of projectively reduced monomials in $x_0, {\delta}ots , x_{{\mathbf e}ll}$ as follows.

{\beta}egin{definition}\label{def:sl}
Let $\mathcal Mathcal S \mathcal Mathcal Subset \mathcal Mathbb Mb$. For $0 \le {\mathbf e}ll \le m$, we define
$$
\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}:=\{x_0^{a_0} \cdots x_{{\mathbf e}ll}^{a_{{\mathbf e}ll}}  \in \mathcal Mathcal S : 0 \le a_j < q \ \mathcal Mathrm{for \ all} \ j< {\mathbf e}ll\}.$$
{\mathbf e}nd{definition}

Note  that if $0\le {\mathbf e}ll \le m$ and if $\mathcal Mu \in \mathcal Mathcal S \mathcal Mathcal Setminus \mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}$,  then either (i) $x_i \mathcal Mid \mathcal Mu$ for some $i > {\mathbf e}ll$,  or (ii)  $\mathcal Mu = x_0^{a_0} \cdots x_{j}^{a_{j}}$ with $a_j >q$ for some $j < {\mathbf e}ll$.

In either case, it is easily seen that 
$\nabla_e^{({\mathbf e}ll)} (\mathcal Mu) = {\mathbf e}mptyset$. This shows that

{\beta}egin{equation}\label{eq:ssl}
\nabla_e^{({\mathbf e}ll)}(\mathcal Mathcal S)=\nabla_e^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}) \quad \mathcal Mathcal Text{and hence} \quad \Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S)=\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}) \quad \mathcal Mathcal Text{for any } e \ge 0.
{\mathbf e}nd{equation}

The following reformulation of Theorem \ref{thm:qfootprint} will be useful to us later.

{\beta}egin{corollary}\label{cor:qfootprint}

Let $F_1,{\delta}ots,F_r$ 
be any nonzero projectively reduced homogeneous polynomials in ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]$,
and let  $\mathcal X=V(F_1,{\delta}ots,F_r)$ be the corresponding projective variety in ${\mathbb P}^m$. 
Also, let $\mathcal Mathcal S=\{\mathrm{lm}(F_1),{\delta}ots,\mathrm{lm}(F_r)\}.$ Then 
$$
|\mathcal X({\mathcal Mathbb F}_q)| \le \mathcal Mathcal Sum_{{\mathbf e}ll=0}^m|\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle})| \quad \mathcal Mathcal Text{for all } e\gg 0.
$$

{\mathbf e}nd{corollary}

{\beta}egin{proof}

From equation {\mathbf e}qref{eq:ssl} and the second part of equation {\mathbf e}qref{eq:disjointshfp}, we  see 
that
{\beta}egin{equation}\label{eq:footprint}
|\Delta_e(\mathcal Mathcal S)|= \mathcal Mathcal Sum_{{\mathbf e}ll=0}^m |\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle})|.
{\mathbf e}nd{equation}
Thus the desired result follows from Theorem \ref{thm:qfootprint}.
{\mathbf e}nd{proof}

\mathcal Mathcal Section{Affine Combinatorics}
\label{combin}

In this section, we will consider some results from extremal combinatorics together with their generalizations and variants that will be useful for us later. These results are mainly concerned with sets of monomials in ${\mathbf e}ll$ variables that are reduced in the usual (or the affine) sense. Throughout this section, $m$ will be a fixed positive integer and ${\mathbf e}ll, d$ as well as $a_i, b_i$ denote nonnegative integers with ${\mathbf e}ll \le m$.

\mathcal Mathcal Subsection{Shadows and Footprints in the Hypercube}
\label{subsec:3.1}

For $0 \le {\mathbf e}ll \le m$, define
$$
\mathcal Mathbb H^{({\mathbf e}ll)}:=\{x_0^{a_0}\cdots x_{{\mathbf e}ll-1}^{a_{{\mathbf e}ll-1}} \, : \, 0 \le a_j \le q-1  \mathcal Makebox{ for all $j=0,{\delta}ots {\mathbf e}ll-1$}\}.
$$
Note that the ``exponent map" given by

$x_0^{a_0}\cdots x_{{\mathbf e}ll-1}^{a_{{\mathbf e}ll-1}} \longmapsto (a_0,{\delta}ots,a_{{\mathbf e}ll-1})$ lets us identify the set
$\mathcal Mathbb H^{({\mathbf e}ll)}$ 
with  $Q^{\mathbf e}ll$, where $Q:=\{0,1, {\delta}ots,q-1\}$, and thus we may refer to
$\mathcal Mathbb H^{({\mathbf e}ll)}$ as the (${\mathbf e}ll$-dimensional) {\mathbf e}mph{hypercube}. We remark that when $q=2$, elements of
$\mathcal Mathbb H^{({\mathbf e}ll)}$ can be identified with subsets of $\{0, {\delta}ots , {\mathbf e}ll-1\}$, whereas in general, they may be viewed as multisets formed by the elements  of $\{0, {\delta}ots , {\mathbf e}ll-1\}$. We will, however, stick to viewing
$\mathcal Mathbb H^{({\mathbf e}ll)}$ as the set of reduced monomials in ${\mathbf e}ll$ variables $x_0, {\delta}ots , x_{{\mathbf e}ll-1}$.

Divisibility of monomials gives a natural partial order on $\mathcal Mathbb H^{({\mathbf e}ll)}$, which corresponds, via the exponent map, to the ``product order"  $\le_P$ on $Q^{\mathbf e}ll$ defined

by  $(a_0,{\delta}ots,a_{{\mathbf e}ll-1}) \le_P (b_0,{\delta}ots,b_{{\mathbf e}ll-1})$ if and only if $a_i \le b_i$ for all $i=0,{\delta}ots,{\mathbf e}ll-1$.
On the other hand, the usual lexicographic order on $Q^{\mathbf e}ll$ corresponds to the total order on $\mathcal Mathbb H^{({\mathbf e}ll)}$, which we denote, as in {\mathbf e}qref{def:lex}, by $\prec_{\mathrm{lex}}$. 
Note that 
if 
$\mathcal Mu, \nu \in \mathcal Mathbb H^{({\mathbf e}ll)}$ are such that 

$\nu \mathcal Mid \mathcal Mu$, i.e.,  $\nu$ divides $\mathcal Mu$,  then $\nu \prec_{\mathrm{lex}}eq \mathcal Mu$.

As before, for a nonnegative integer $d$, we define
$$
\mathcal Mathbb H^{({\mathbf e}ll)}_d:=\{\mathcal Mu \in \mathcal Mathbb H^{({\mathbf e}ll)}\, : \, {\delta}eg \mathcal Mu =d\} \quad \mathcal Makebox{and} \quad
\mathcal Mathbb H^{({\mathbf e}ll)}_{\le d}:=\{\mathcal Mu \in \mathcal Mathbb H^{({\mathbf e}ll)}\, : \, {\delta}eg \mathcal Mu  \le d\}.
$$

The sets $\mathcal Mathbb H^{({\mathbf e}ll)}_{< d}, \ \mathcal Mathbb H^{({\mathbf e}ll)}_{\ge d}$ and $\mathcal Mathbb H^{({\mathbf e}ll)}_{> d}$ are defined analogously. 

We will now define 
shadow and footprint in the context of the hypercube  $\mathcal Mathbb H^{({\mathbf e}ll)}$. To avoid confusion with the notions defined in \S\,\ref{subsec:pfb}, we will use a different notation.

For any 
$\mathcal Mathcal T \mathcal Mathcal Subseteq \mathcal Mathbb H^{({\mathbf e}ll)}$, the {\mathbf e}mph{shadow} and {\mathbf e}mph{footprint} of $\mathcal Mathcal T$ in $\mathcal Mathbb H^{({\mathbf e}ll)}$ are denoted by $\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal T)$ and $\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal T)$, respectively, and defined by 
$$
\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal T):=\{\mathcal Mu \in \mathcal Mathbb H^{({\mathbf e}ll)} \, : \, \nu \mathcal Mid \mathcal Mu \ \mathcal Makebox{for some $\nu \in \mathcal Mathcal T$}\} \quad \mathcal Makebox{and} \quad  \mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal T):=\mathcal Mathbb H^{({\mathbf e}ll)} \mathcal Mathcal Setminus \mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal T).
$$
For a nonnegative integer $d$, we also define,
$$
\mathsf {FP}_d^{({\mathbf e}ll)}(\mathcal Mathcal T):=\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal T) \cap \mathcal Mathbb H^{({\mathbf e}ll)}_{d} \quad \mathcal Makebox{and} \quad \mathsf {FP}_{\le d}^{({\mathbf e}ll)}(\mathcal Mathcal T):=\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal T) \cap \mathcal Mathbb H^{({\mathbf e}ll)}_{ \le d}.
$$
The sets $\mathsf {FP}^{({\mathbf e}ll)}_{< d}(\mathcal Mathcal T), \ \mathsf {FP}^{({\mathbf e}ll)}_{\ge d}(\mathcal Mathcal T)$ and $\mathsf {FP}^{({\mathbf e}ll)}_{> d}(\mathcal Mathcal T)$ are defined 
analogously. 
Moreover, the corresponding subsets of $\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal T)$ are also defined in a similar manner.

{\beta}egin{definition}

Let ${\mathbf e}ll, d, \rho, \rho'$ be integers satisfying $0\le d \le {\mathbf e}ll(q-1)$, $0 \le {\mathbf e}ll \le m$, $0 \le \rho \le |\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}|$, and $0 \le \rho' \le |\mathcal Mathbb H^{({\mathbf e}ll)}_d|.$

Define
{\beta}egin{eqnarray*}
\mathcal M_d^{({\mathbf e}ll)}(\rho) &: =& \mathcal Mathcal Text{the set of first $\rho$ elements of $\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$ in descending lexicographic order,} \\
\mathcal L_d^{({\mathbf e}ll)}(\rho') &: =& \mathcal Mathcal Text{the set of first $\rho'$ elements of $\mathcal Mathbb H_{d}^{({\mathbf e}ll)}$ in descending lexicographic order}.
{\mathbf e}nd{eqnarray*}
{\mathbf e}nd{definition}

Note that if ${\mathbf e}ll, \rho, \rho'$ are positive and $d<q$, then both $\mathcal M_d^{({\mathbf e}ll)}(\rho)$ and $\mathcal L_d^{({\mathbf e}ll)}(\rho')$ contain $x_0^d$, which is the largest element of $\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$ as well as $\mathcal Mathbb H_{d}^{({\mathbf e}ll)}$ in 
lexicographic order. Also, 
for a fixed $d\ge 0$, the set $\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$ is finite and $\prec_{\mathrm{lex}}$ is a total order on it.

Consequently,  a 
set of the form $\mathcal M_d^{({\mathbf e}ll)}(\rho)$ can be characterized as a
subset $\mathcal Mathcal T$ of $\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$ that is {\mathbf e}mph{upwards closed}, which means $\mathcal Mu \in \mathcal Mathcal T$ whenever
$\mathcal Mu, \mathcal Mu' \in \mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$ with $\mathcal Mu' \prec_{\mathrm{lex}} \mathcal Mu$ and $\mathcal Mu' \in \mathcal Mathcal T$. 
Similarly, sets of the form $\mathcal L_d^{({\mathbf e}ll)}(\rho')$ can be characterized as upwards closed subsets of
$\mathcal Mathbb H_{d}^{({\mathbf e}ll)}$.

\mathcal Mathcal Subsection{Extremal Combinatorics}
We will now discuss some combinatorial results that help us determine the subsets of $\mathcal Mathbb H_{d}^{({\mathbf e}ll)}$ (resp. $\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$) of a given cardinality that have footprint of the maximum possible size.   
We begin with a result due to Heijnen and Pellikaan \cite[Prop. 5.9]{HP}. Its formulation below is as in \cite[Lem. 4.2]{BD}, where  the result
is proved in a more general setting.

{\beta}egin{proposition}
\label{prop:shadow}
Let ${\mathbf e}ll, d, \rho$ be integers satisfying $1\le {\mathbf e}ll \le m$, $0\le d \le {\mathbf e}ll(q-1)$, and $1\le \rho \le |\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}|$. Also,

let ${\alpha}lpha$ be the $\rho^{\rm th}$ element of   $\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$, i.e., the smallest element of
$\mathcal M_d^{({\mathbf e}ll)}(\rho)$ in lexicographic order. Then
$$
\mathsf {SH}^{({\mathbf e}ll)}(\mathcal M_d^{({\mathbf e}ll)}(\rho))=\{\mathcal Mu \in \mathcal Mathbb H^{({\mathbf e}ll)} \, : \, {\alpha}lpha \prec_{\mathrm{lex}}eq \mathcal Mu\}.
$$
Consequently,  $\mathsf {SH}^{({\mathbf e}ll)}(\mathcal M_d^{({\mathbf e}ll)}(\rho)) \cap \mathcal Mathbb H_{\le d}^{({\mathbf e}ll)} = \mathcal M_d^{({\mathbf e}ll)}(\rho)$.
{\mathbf e}nd{proposition}

{\beta}egin{corollary}\label{cor:compressed}

Let ${\mathbf e}ll, d, \rho$ be integers satisfying $1\le {\mathbf e}ll \le m$, $1\le d \le {\mathbf e}ll(q-1)$, and $0 \le \rho \le |\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}|$. Then $\mathsf {SH}_d^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho))=\mathcal L_d^{({\mathbf e}ll)}(\rho')$ for some
nonnegative  integer $\rho'$. 
Moreover, if $\rho$ is positive, then so is $\rho'$.
{\mathbf e}nd{corollary}

{\beta}egin{proof}
If $\rho = 0$, then $\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho)$ is empty, and hence so is its shadow in $\mathcal Mathbb H^{({\mathbf e}ll)}$.

Thus we can take $\rho'=0$ in this case.
Now suppose $\rho \ge 1$. 
First, note that
$\mathsf {SH}_d^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho))$ is nonempty. 
Indeed,  $d-1<{\mathbf e}ll(q-1)$ and so we can write $d-1 = j(q-1)+a_j$ for unique integers $j, a_j$ with
$0\le j  \le {\mathbf e}ll -1$ and $0\le a_j < q-1$. Since $\rho\ge 1$, the set   $\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho)$ contains $\nu:= x_0^{q-1}\cdots x_{j-1}^{q-1}x_j^{a_j}$, 
being the largest element of  this set 
in lexicographic order. Now $\mathcal Mu:= \nu x_{{\mathbf e}ll -1}$ is clearly in $\mathsf {SH}_d^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho))$. 

To complete the proof, it suffices to show that $\mathsf {SH}_d^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho))$ is upwards closed. Assume the contrary.
Then there exist $\mathcal Mu, \mathcal Mu' \in \mathcal Mathbb H_d^{({\mathbf e}ll)}$ such that $\mathcal Mu' \in \mathsf {SH}_d^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho))$ and
$\mathcal Mu' \prec_{\mathrm{lex}} \mathcal Mu$,  but $\mathcal Mu \not\in \mathsf {SH}_d^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho))$. 
Let $\nu \in \mathcal M_{d-1}^{({\mathbf e}ll)}(\rho)$ be such that $\nu \mathcal Mid \mathcal Mu'.$  Then $\nu \prec_{\mathrm{lex}}eq \mathcal Mu'$.
Also, let $\nu'$ be the least element of $\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho)$ in lexicographic order.
Then $\nu' \prec_{\mathrm{lex}}eq \nu$ and $\nu \prec_{\mathrm{lex}}eq \mathcal Mu'$, since $\nu \mathcal Mid \mathcal Mu'$. Consequently, 
$\nu' \prec_{\mathrm{lex}} \mathcal Mu.$ By the previous proposition, $\mathcal Mu \in \mathsf {SH}_d^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho)),$ which is a contradiction.
{\mathbf e}nd{proof}

The following 
result is due to Clements and Lindstr\"om \cite[Cor. 1]{CL} (see also \cite[Thm. 3.1]{BD}). 
The case $q=2$ of it 
is equivalent to the Kruskal-Katona theorem.

{\beta}egin{theorem}[Clements--Lindstr\"om]

\label{thm:CL}
Let $\mathcal Mathcal T \mathcal Mathcal Subseteq \mathcal Mathbb H_d^{({\mathbf e}ll)}$ with $|\mathcal Mathcal T| = \rho'$. 
Then
$$
\mathsf {SH}_{d+1}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho')) \mathcal Mathcal Subseteq \mathcal L_{d+1}^{({\mathbf e}ll)}(|\mathsf {SH}_{d+1}^{({\mathbf e}ll)}(\mathcal Mathcal T)|) \ \mathcal Mathrm{and \ hence} \ |\mathsf {FP}_{d+1}^{({\mathbf e}ll)}(\mathcal Mathcal T)| \le |\mathsf {FP}_{d+1}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho'))| .
$$
{\mathbf e}nd{theorem}

As in \cite[Cor. 3.2]{BD}, the following corollary can be deduced easily from the above theorem 
by using induction on $e$.

{\beta}egin{corollary}\label{cor:Wei}
Let $\mathcal Mathcal T \mathcal Mathcal Subseteq \mathcal Mathbb H_d^{({\mathbf e}ll)}$ with $|\mathcal Mathcal T| = \rho'$, and let $e$ be an integer  $\ge d$.

Then
$$
\mathsf {SH}_{e}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho')) \mathcal Mathcal Subseteq \mathcal L_{e}^{({\mathbf e}ll)}(|\mathsf {SH}_{e}^{({\mathbf e}ll)}(\mathcal Mathcal T)|); \ \mathcal Mathcal Text{ in particular, } \  \left| \mathsf {SH}_{e}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho')) \right| \le |\mathsf {SH}_{e}^{({\mathbf e}ll)}(\mathcal Mathcal T)|.
$$

Consequently,
$|\mathsf {FP}_{e}^{({\mathbf e}ll)}(\mathcal Mathcal T)| \le |\mathsf {FP}_{e}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho'))|$ and hence 
$|\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal T)| \le |\mathsf {FP}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho'))|.$
{\mathbf e}nd{corollary}

The following theorem can be traced back to Wei \cite[Lemma 6]{W} and it
gives an analogue of the last inequality for subsets of $\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$.

{\beta}egin{theorem}[Wei]  \label{thm:Wei}
Let $\mathcal Mathcal T \mathcal Mathcal Subset \mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}$ be a subset with $|\mathcal Mathcal T|=\rho.$ Then 
$$ |\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal T)| \le |\mathsf {FP}^{({\mathbf e}ll)}(\mathcal M_d^{({\mathbf e}ll)}(\rho))|.$$
{\mathbf e}nd{theorem}

Strictly speaking, Lemma 6 of Wei \cite{W} proves the above theorem for the special case when $q=2$. 
A general version is stated in Heijnen and Pellikaan \cite[Thm.~5.7]{HP}, although in a slightly different way. A detailed proof appears in Appendix A of Heijnen's thesis \cite{H}. We refer to \cite[Thm. 3.8]{BD} for a similar result in a more general setting. We conclude this subsection by proving the  following common generalization of the results of Clements--Lindstr\"om (Corollary \ref{cor:Wei}) and of Wei and Heijnen--Pellikaan  (\hbox{Theorem \ref{thm:Wei}}).  Indeed, Corollary \ref{cor:Wei} corresponds to the case $\rho'=\rho$, while Theorem \ref{thm:Wei} corresponds to the case $\rho'= 0$.

{\beta}egin{theorem}\label{thm:affinecomb}
Assume that ${\mathbf e}ll, d, \rho$ are positive integers with ${\mathbf e}ll \le m$,  $d\le {\mathbf e}ll (q-1)$, and  $\rho \le |\mathcal Mathbb H_{\le d}^{({\mathbf e}ll)}|$.
Let $\mathcal Mathcal T \mathcal Mathcal Subseteq \mathcal Mathbb H^{({\mathbf e}ll)}_{\le d}$ with $|\mathcal Mathcal T| = \rho$. If $ \rho' := |\mathcal Mathcal T \cap \mathcal Mathbb H_d^{({\mathbf e}ll)}|$, then
$$
|\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal T)| \le |\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal U)|, \quad \mathcal Makebox{where} \quad \mathcal Mathcal U:=\mathcal L_d^{({\mathbf e}ll)}(\rho') \cup \mathcal M_{d-1}^{({\mathbf e}ll)}(\rho - \rho').
$$
{\mathbf e}nd{theorem}

{\beta}egin{proof}

Let $ \rho' := |\mathcal Mathcal T \cap \mathcal Mathbb H_d^{({\mathbf e}ll)}|$ and $ \mathcal Mathcal U:=\mathcal L_d^{({\mathbf e}ll)}(\rho') \cup \mathcal M_{d-1}^{({\mathbf e}ll)}(\rho - \rho')$.
It suffices to show that $|\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal U)| \le |\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal T)|.$

We will do this by distinguishing two cases.

\mathcal Mathcal Smallskip

\noindent
{{\beta}f Case 1:} $\mathcal L^{({\mathbf e}ll)}_d (\rho') \mathcal Mathcal Subseteq \mathsf {SH}^{({\mathbf e}ll)}_d (\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho'))$.

Let $\mathcal Mu \in \mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal U)$. Then there is $\nu \in \mathcal Mathcal U$ such that $\nu \mathcal Mid \mathcal Mu$.  Suppose
$\nu \in \mathcal L^{({\mathbf e}ll)}_d (\rho') $.  Since $\mathcal L^{({\mathbf e}ll)}_d (\rho') \mathcal Mathcal Subseteq \mathsf {SH}^{({\mathbf e}ll)}_d (\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho'))$, there is $\nu' \in \mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho')$ such that
$\nu' \mathcal Mid \nu$, and hence $\nu'\mathcal Mid \mathcal Mu$. 
This shows that  $\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal U) = \mathsf {SH}^{({\mathbf e}ll)} ( \mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho') )$.
Consequently,
$$
 |\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal U){\beta}ig| = {\beta}ig|\mathsf {SH}^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho')){\beta}ig| \le {\beta}ig|\mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal T \cap \mathcal Mathbb H_{\le d-1}^{({\mathbf e}ll)}){\beta}ig| \le {\beta}ig| \mathsf {SH}^{({\mathbf e}ll)}(\mathcal Mathcal T) {\beta}ig|,
$$

where the penultimate inequality is a consequence of Theorem \ref{thm:Wei} (applied to shadows instead of footprints), while the last inequality follows since $\mathcal Mathcal T \cap \mathcal Mathbb H_{\le d-1}^{({\mathbf e}ll)} \mathcal Mathcal Subseteq \mathcal Mathcal T$.

\mathcal Mathcal Smallskip

\noindent
{{\beta}f Case 2:} $\mathcal L_d^{({\mathbf e}ll)}(\rho') \not\mathcal Mathcal Subseteq \mathsf {SH}^{({\mathbf e}ll)}_d(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho'))$.

\mathcal Mathcal Smallskip

By Corollary \ref{cor:compressed},  
$\mathsf {SH}^{({\mathbf e}ll)}_d(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho')) = \mathcal L_d^{({\mathbf e}ll)}(\rho'')$ for some nonnegative integer $\rho''$. Hence $\mathcal L_d^{({\mathbf e}ll)}(\rho') \not\mathcal Mathcal Subseteq \mathcal L_d^{({\mathbf e}ll)}(\rho'')$ and this implies that $\rho'\not\le \rho''$, i.e., $\rho'' < \rho'$. It follows that $\mathsf {SH}^{({\mathbf e}ll)}_d(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho')) \mathcal Mathcal Subseteq \mathcal L_d^{({\mathbf e}ll)}(\rho')$. Consequently,
{\beta}egin{equation}\label{eq:shadow2}
\mathsf {SH}_{\ge d}^{({\mathbf e}ll)}(\mathcal Mathcal U)
= \mathsf {SH}_{\ge d}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho')) \cup \mathsf {SH}_{\ge d}^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho'))
= \mathsf {SH}_{\ge d}^{({\mathbf e}ll)}(\mathcal L_d^{({\mathbf e}ll)}(\rho')).
{\mathbf e}nd{equation}
On the other hand, $\mathsf {SH}^{({\mathbf e}ll)}_{<d} (\mathcal Mathcal U)=\mathsf {SH}^{({\mathbf e}ll)}_{<d} (\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho'))=\mathsf {SH}^{({\mathbf e}ll)}(\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho')) \cap \mathcal Mathbb H_{< d}^{({\mathbf e}ll)}$, and so by Proposition \ref{prop:shadow}.
we see that

{\beta}egin{equation}\label{eq:shadow1}
\mathsf {SH}^{({\mathbf e}ll)}_{<d} (\mathcal Mathcal U)= 
\mathcal M_{d-1}^{({\mathbf e}ll)}(\rho-\rho').
{\mathbf e}nd{equation}

Using equations {\mathbf e}qref{eq:shadow2} and {\mathbf e}qref{eq:shadow1}, we obtain
$$
|\mathsf {SH}^{({\mathbf e}ll)} (\mathcal Mathcal U)|  
= \rho - \rho'+|\mathsf {SH}^{({\mathbf e}ll)}_{\ge d} (\mathcal L_d^{({\mathbf e}ll)}(\rho'))|  \le \rho-\rho'+|\mathsf {SH}^{({\mathbf e}ll)}_{\ge d} (\mathcal Mathcal T \cap \mathcal Mathbb H^{({\mathbf e}ll)}_d)|,
$$
where the last inequality follows from Corollary \ref{cor:Wei}. Now since $|\mathcal Mathcal T \cap \mathcal Mathbb H^{({\mathbf e}ll)}_{<d}| = \rho - \rho'$, 
$$
{\beta}ig|\mathsf {SH}^{({\mathbf e}ll)} (\mathcal Mathcal U) {\beta}ig|  \le {\beta}ig|\mathsf {SH}^{({\mathbf e}ll)}_{<d} (\mathcal Mathcal T \cap \mathcal Mathbb H^{({\mathbf e}ll)}_{<d}){\beta}ig| + {\beta}ig|\mathsf {SH}^{({\mathbf e}ll)}_{\ge d} (\mathcal Mathcal T \cap \mathcal Mathbb H^{({\mathbf e}ll)}_d){\beta}ig|.

$$
Hence $|\mathsf {SH}^{({\mathbf e}ll)} (\mathcal Mathcal U)| \le |\mathsf {SH}^{({\mathbf e}ll)}_{<d} (\mathcal Mathcal T)| +|\mathsf {SH}^{({\mathbf e}ll)}_{\ge d} (\mathcal Mathcal T)|= |\mathsf {SH}^{({\mathbf e}ll)} (\mathcal Mathcal T)|$, as desired.

{\mathbf e}nd{proof}

\mathcal Mathcal Section{Specializations and Expanders}
\label{combin2}

In order to effectively relate the two notions $\Delta_e$ and $\mathsf {FP}$ of footprint considered in the previous two sections, we will introduce two maps, denoted $\sigma^{({\mathbf e}ll)}$ and $\mathsf{p}hi$, on the space of projectively reduced monomials in $x_0, {\delta}ots , x_{m}$ and prove some of their properties. Throughout this section, $m$ is a fixed positive integer, while ${\mathbf e}ll, d, e$ denote nonnegative integers satisfying
${\mathbf e}ll \le m$.

\mathcal Mathcal Subsection{Specialization}

For any nonnegative integer ${\mathbf e}ll \le m$, we define 
$$
\sigma^{({\mathbf e}ll)}: \mathcal Mathbb Mb \mathcal Mathcal To \mathcal Mathbb Mb \cup \{0\}
\quad \mathcal Makebox{by} \quad \sigma^{({\mathbf e}ll)}(\mathcal Mu) := 
{\beta}egin{cases} 
x_0^{a_0}\cdots x_{{\mathbf e}ll-1}^{a_{{\mathbf e}ll-1}} & \mathcal Makebox{if }\mathcal Mu =x_0^{a_0}\cdots x_{{\mathbf e}ll-1}^{a_{{\mathbf e}ll-1}}x_{\mathbf e}ll^{a_{\mathbf e}ll},\\
0 & \mathcal Makebox{if } \mathcal Mu \not\in {\mathcal Mathbb F}_q[x_0,{\delta}ots,x_{\mathbf e}ll], \\
{\mathbf e}nd{cases} 
$$
with the usual convention that an empty product equals $1$. 
We may refer to $\sigma^{({\mathbf e}ll)}$ as the {\mathbf e}mph{specialization map} at level ${\mathbf e}ll$, since it corresponds to specializing the variables $(x_{\mathbf e}ll,x_{{\mathbf e}ll+1},{\delta}ots,x_m)$ to $(1,0,{\delta}ots,0)$.

{\beta}egin{proposition}\label{prop:divisible}
Let ${\mathbf e}ll, d, e$ be nonnegative integers such that $e \ge d+m(q-1)$ and ${\mathbf e}ll \le m$.
Suppose $\mathcal Mu  \in \mathcal Mathbb Mb_d\cap {\mathcal Mathbb F}_q[x_0,{\delta}ots,x_{\mathbf e}ll]$ and $\nu \in \mathcal Mathbb Mb_e^{({\mathbf e}ll)}.$

Then 
$$
\mathcal Mu \mathcal Mid \nu  \iff \sigma^{({\mathbf e}ll)}(\mathcal Mu) \mathcal Mid \sigma^{({\mathbf e}ll)}(\nu).
$$
{\mathbf e}nd{proposition}

{\beta}egin{proof}
We can write $\mathcal Mu = x_0^{a_0} \cdots x_{{\mathbf e}ll}^{a_{{\mathbf e}ll}}$ 
and $\nu=x_0^{b_0}\cdots x_{{\mathbf e}ll-1}^{b_{{\mathbf e}ll-1}}x_{\mathbf e}ll^{b_{\mathbf e}ll}$ for some nonnegative integers $a_j, b_j$ for $0\le j \le {\mathbf e}ll$ such that

$b_j \le q-1$
for all $j \le {\mathbf e}ll-1$ and $b_{{\mathbf e}ll} >0$.  Note that
$\sigma^{({\mathbf e}ll)}(\mathcal Mu)=x_0^{a_0}\cdots x_{{\mathbf e}ll-1}^{a_{{\mathbf e}ll-1}}$ and $\sigma^{({\mathbf e}ll)}(\nu)=x_0^{b_0}\cdots x_{{\mathbf e}ll-1}^{b_{{\mathbf e}ll-1}}.$

If $\mathcal Mu \mathcal Mid \nu$, then $a_i \le b_i$ for $0\le i \le {\mathbf e}ll$, and this 
readily implies that $\sigma^{({\mathbf e}ll)}(\mathcal Mu) \mathcal Mid \sigma^{({\mathbf e}ll)}(\nu).$ To prove the converse, suppose  $\sigma^{({\mathbf e}ll)}(\mathcal Mu) \mathcal Mid \sigma^{({\mathbf e}ll)}(\nu).$ Then $a_i \le b_i \le q-1$ for 
$0 \le i \le {\mathbf e}ll-1.$
Since $\mathcal Mathcal Sum_{i=0}^{{\mathbf e}ll } a_i = d$ and $\mathcal Mathcal Sum_{i=0}^{{\mathbf e}ll} b_i = e$, we obtain

$$
b_{{\mathbf e}ll} - a_{{\mathbf e}ll} = e-d + \mathcal Mathcal Sum_{i=0}^{{\mathbf e}ll - 1} (a_i - b_i) \ge m(q-1) - {\mathbf e}ll  (q-1)  \ge 0.
$$

This shows that $\mathcal Mu \mathcal Mid \nu$. 
{\mathbf e}nd{proof}

{\beta}egin{remark}
\label{rem:sigmam}
Suppose $0\le d < q$. Then $\mathcal Mathcal Sigma^{(m)}$ gives a bijection of $\mathcal Mathbb Mb_d = \mathcal Mathbb M_d$ onto $\mathcal Mathbb H^{(m)}_{\le d}$. Indeed, if $\mathcal Mu = x_0^{a_0} \cdots x_{m}^{a_{m}} \in \mathcal Mathbb Mb_d$, then clearly,  $0\le a_i \le d \le q-1$  for $0\le i \le m$; 
also $a_0 + {\delta}ots + a_{m -1} \le d$. Moreover, $a_m = d -  a_0 - {\delta}ots - a_{m -1}$, and so $\mathcal Mu$ is determined by $\sigma^{(m)}(\mathcal Mu)=x_0^{a_0}\cdots x_{m-1}^{a_{m-1}} \in \mathcal Mathbb H^{(m)}_{\le d}$.

A similar reasoning shows that $\mathcal Mathcal Sigma^{(m)}$ preserves lexicographic order, i.e., for any
$\mathcal Mu, \nu \in \mathcal Mathbb Mb_d$, we have $\mathcal Mu \prec_{\mathrm{lex}} \nu \iff \mathcal Mathcal Sigma^{(m)}(\mathcal Mu) \prec_{\mathrm{lex}} \mathcal Mathcal Sigma^{(m)}(\nu)$.
{\mathbf e}nd{remark}

The following result gives a useful relation between the two notions of footprint.

{\beta}egin{theorem}\label{thm:projectivetoaffine}

Let $d, e$ be any nonnegative integers 
such that  $e \ge d + m(q-1)$ and let $\mathcal Mathcal S \mathcal Mathcal Subset \mathcal Mathbb Mb_d$. Then
$$
|\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle})|=|\mathsf {FP}^{({\mathbf e}ll)}(\sigma^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}))| \quad \mathcal Mathcal Text{for all nonnegative integers } {\mathbf e}ll \le m, 
$$
and consequently,
$$
|\Delta_e(\mathcal Mathcal S)|=\mathcal Mathcal Sum_{{\mathbf e}ll=0}^{m}|\mathsf {FP}^{({\mathbf e}ll)}(\sigma^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}))|.
$$
{\mathbf e}nd{theorem}

{\beta}egin{proof}

Fix a nonnegative integer ${\mathbf e}ll \le m$. It is clear from Definition \ref{def:sl}  that $\sigma^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}) \mathcal Mathcal Subseteq \mathcal Mathbb H^{({\mathbf e}ll)}.$
From Proposition \ref{prop:divisible}, we see that the map
$$
\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}) \mathcal Mathcal To \mathsf {FP}^{({\mathbf e}ll)}(\sigma^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle})) \quad \mathcal Mathcal Text{defined by} \quad \mathcal Mu \longmapsto \sigma^{({\mathbf e}ll)}(\mathcal Mu)
$$
is well-defined. Moreover, since $e \ge d + m(q-1)$, this map is easily seen to be a bijection. This yields the first assertion in the theorem. Consequently, we obtain the last assertion from equation  {\mathbf e}qref{eq:footprint}.
{\mathbf e}nd{proof}

\mathcal Mathcal Subsection{Footprint Expander}
In this subsection, we consider a degree-preserving map $\mathsf{p}hi$ on sets of projectively reduced monomials in $x_0, {\delta}ots , x_m$ such that 
$\mathsf{p}hi$ is injective and has the property that

$|\Delta_e(\mathcal Mathcal S)|\le |\Delta_e(\mathsf{p}hi(\mathcal Mathcal S))|$ for any $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb$ and $e\gg 0$.  For this reason, $\mathsf{p}hi$ may be referred to as an {\mathbf e}mph{expander} map.

{\beta}egin{definition}\label{def:phi}
Let $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb$. 

If $\mathcal Mu=x_0^{i_0}\cdots x_m^{i_m} \in \mathcal Mathcal S$, then define
$$
\mathsf{p}hi(\mathcal Mu) :=
{\beta}egin{cases}
\mathcal Mu  \sigmarac{x_{m-1}}{x_m}  &  \mathcal Mathrm{if} \   x_0^{i_0}\cdots x_{m-2}^{i_{m-2}}x_{m-1}^{i_{m-1}+i_m} \not\in \mathcal Mathcal S  \ \mathcal Mathrm{and} \  i_{m-1} + 1 <q,\\
\mathcal Mu  &  \mathcal Mathrm{otherwise.}
{\mathbf e}nd{cases}
$$
{\mathbf e}nd{definition}

Note that if $i_m =0$, then  $x_0^{i_0}\cdots x_{m-2}^{i_{m-2}}x_{m-1}^{i_{m-1}+i_m} = \mathcal Mu \in \mathcal Mathcal S$. Hence, in the first case of the definition, we must have 
$i_m >0$. In particular, $\mathsf{p}hi (\mathcal Mu)$ is always a monomial, and we obtain a well-defined map $\mathsf{p}hi: \mathcal Mathcal S \mathcal Mathcal To \mathcal Mathbb Mb$, which preserves degrees.

{\beta}egin{proposition}
Let $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb$. Then the map $\mathsf{p}hi: \mathcal Mathcal S \mathcal Mathcal To \mathcal Mathbb Mb$ is injective and it satisfies
$$
\mathcal Mathcal S^{\langle m-1 \rangle}=\mathsf{p}hi(\mathcal Mathcal S^{\langle m-1 \rangle}) \mathcal Mathcal Subseteq \mathsf{p}hi(\mathcal Mathcal S)^{\langle m-1 \rangle}
\quad \mathcal Mathcal Text{and} \quad \mathsf{p}hi(\mathcal Mathcal S^{\langle m \rangle}) = \mathsf{p}hi(\mathcal Mathcal S)^{\langle m \rangle}.
$$
{\mathbf e}nd{proposition}

{\beta}egin{proof}
It is easy to see that $\mathsf{p}hi$ is injective. Also, as noted earlier, $\mathsf{p}hi(\mathcal Mu) = \mathcal Mu$ in case $\mathcal Mu \in \mathcal Mathcal S^{\langle m-1 \rangle}$. This implies that $\mathcal Mathcal S^{\langle m-1 \rangle}=\mathsf{p}hi(\mathcal Mathcal S^{\langle m-1 \rangle}) \mathcal Mathcal Subseteq \mathsf{p}hi(\mathcal Mathcal S)^{\langle m-1 \rangle}$. To prove that $\mathsf{p}hi(\mathcal Mathcal S^{\langle m \rangle}) = \mathsf{p}hi(\mathcal Mathcal S)^{\langle m \rangle}$, suppose   $\mathcal Mu = x_0^{i_0} \cdots x_m^{i_m} \in \mathcal Mathcal S^{\langle m \rangle}$. 
Then $i_j < q$ for $0 \le j \le m-1$.
In case $\mathsf{p}hi(\mathcal Mu) = \mathcal Mu$, then clearly,  $\mathsf{p}hi(\mathcal Mu) \in \mathsf{p}hi(\mathcal Mathcal S)^{\langle m \rangle}$. In particular, if $i_{m-1} = q-1$, then $\mathsf{p}hi (\mathcal Mu) \in \mathsf{p}hi(\mathcal Mathcal S)^{\langle m \rangle}$ because in this case, $i_{m-1} + 1 = q$ and so $\mathsf{p}hi(\mathcal Mu) = \mathcal Mu$.  On the other hand, if $i_{m-1} < q-1$ and $\mathsf{p}hi (\mathcal Mu) \neq \mathcal Mu$, then $\mathsf{p}hi(\mathcal Mu) = x_0^{i_0} \cdots x_{m-1}^{i_{m-1} + 1} x_m^{i_m -1}$. Since $i_{m-1} + 1 < q$, we obtain $\mathsf{p}hi(\mathcal Mu) \in \mathsf{p}hi(\mathcal Mathcal S)^{\langle m \rangle}$. This shows that $\mathsf{p}hi(\mathcal Mathcal S^{\langle m \rangle}) \mathcal Mathcal Subseteq \mathsf{p}hi(\mathcal Mathcal S)^{\langle m \rangle}$. In order to prove the reverse inclusion, we take $\mathcal Mu \in \mathsf{p}hi(\mathcal Mathcal S)^{\langle m \rangle}$. Since $\mathcal Mu \in \mathsf{p}hi (\mathcal Mathcal S)$, there exists $\mathcal Mu' \in \mathcal Mathcal S$ such that $\mathsf{p}hi(\mathcal Mu') = \mathcal Mu$. It is trivial to see that $\mathcal Mu' \in \mathcal Mathcal S^{\langle m \rangle}$. 
{\mathbf e}nd{proof}

We now give a series of lemmas and a proposition leading to the result that $\mathsf{p}hi$ does not decrease footprints in $\mathcal Mathbb Mb_e$ for all large enough $e$.

{\beta}egin{lemma}\label{claim1}
Let $\mathcal Mathcal S$ be a finite subset of $\mathcal Mathbb Mb$. Then $\Delta_e^{(m)}(\mathcal Mathcal S) \mathcal Mathcal Subseteq \Delta_e^{(m)}(\mathsf{p}hi(\mathcal Mathcal S))$ for all $e\gg 0$.
{\mathbf e}nd{lemma}

{\beta}egin{proof}

It suffices to show that $\nabla_e^{(m)} (\mathsf{p}hi(\mathcal Mathcal S)) \mathcal Mathcal Subseteq \nabla_e^{(m)} (\mathcal Mathcal S)$ for all $e\gg 0$.
To this end, let $\nu \in \nabla_e^{(m)} (\mathsf{p}hi(\mathcal Mathcal S)).$ Then $\nu \in \mathcal Mathbb Mb_e^{(m)}$ and there exists $\mathcal Mu \in \mathsf{p}hi(\mathcal Mathcal S)$ such that $\mathcal Mu \mathcal Mid \nu.$
If $\mathcal Mu \in \mathcal Mathcal S$, then $\nu \in \nabla_e^{(m)} (\mathcal Mathcal S).$
Suppose $\mathcal Mu \not \in \mathcal Mathcal S$.  Since $\mathcal Mu \in \mathsf{p}hi(\mathcal Mathcal S)$, it follows~from Definition~\ref{def:phi} that
$\mathcal Mu x_m/x_{m-1} \in \mathcal Mathcal S.$ In particular, $x_{m-1} \mathcal Mid \mathcal Mu$ and $(\mathcal Mu/x_{m-1}) \mathcal Mid \nu.$
Further, since $\nu \in \mathcal Mathbb Mb_e^{(m)}$, we see that ${\delta}eg_{x_m} \nu \gg 0$ for all $e\gg 0$, whereas
${\delta}eg_{x_m} \mathcal Mu$ is bounded since $\mathcal Mathcal S$ is finite. Consequently, 
$(\mathcal Mu x_m/x_{m-1} )\mathcal Mid \nu$,  
and so  $\nu \in \nabla_e^{(m)} (\mathcal Mathcal S)$ for 
$e\gg 0$.

{\mathbf e}nd{proof}

{\beta}egin{lemma}\label{claim2}

Let $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb$. 
Then $\Delta_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S)) \mathcal Mathcal Subseteq \Delta_e^{(m-1)}(\mathcal Mathcal S)$ for all $e\ge 0$.
{\mathbf e}nd{lemma}
{\beta}egin{proof}
Fix a nonnegative integer $e$.  
We will show that $\nabla_e^{(m-1)} (\mathcal Mathcal S) \mathcal Mathcal Subseteq \nabla_e^{(m-1)} (\mathsf{p}hi(\mathcal Mathcal S))$.
Let $\nu \in \nabla_e^{(m-1)} (\mathcal Mathcal S)$. Then $\nu \in \mathcal Mathbb Mb_e^{(m-1)}$ and there exists $\mathcal Mu \in \mathcal Mathcal S$ such that $\mathcal Mu \mathcal Mid \nu.$ In particular, ${\delta}eg_{x_m} \mathcal Mu \le {\delta}eg_{x_m} \nu = 0$, and so
$\mathsf{p}hi(\mathcal Mu) = \mathcal Mu$. It follows that $\mathcal Mu \in \mathsf{p}hi(\mathcal Mathcal S)$ and so $\nu \in \nabla_e^{(m-1)} (\mathsf{p}hi(\mathcal Mathcal S)).$

{\mathbf e}nd{proof}

{\beta}egin{lemma}\label{claim3}
Let $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb$ and  let  $e$ be a nonnegative integer.  Suppose $\nu \in \Delta_e^{(m-1)}(\mathcal Mathcal S)$ and $\mathcal Mu \in \mathcal Mathbb Mb$ satisfy $\mathcal Mu \mathcal Mid \nu$. Then $\mathcal Mu \not \in \mathcal Mathcal S^{\langle m-1 \rangle}.$
{\mathbf e}nd{lemma}

{\beta}egin{proof}
Since $\Delta_e^{(m-1)}(\mathcal Mathcal S) = \Delta_e^{(m-1)}(\mathcal Mathcal S^{\langle m-1 \rangle})$, this follows directly.
{\mathbf e}nd{proof}

{\beta}egin{lemma}\label{nonempty}
Let $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb$ and let $e$ be a nonnegative integer. Suppose there exists
$\nu \in \Delta_e^{(m-1)}(\mathcal Mathcal S) \mathcal Mathcal Setminus \Delta_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S))$, i.e., 
$\nu \in \nabla_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S)) \mathcal Mathcal Setminus \nabla_e^{(m-1)}(\mathcal Mathcal S).$ Then the set
$\{ \mathcal Mu \in \mathcal Mathcal S :  {\delta}eg_{x_{m-1}} \mathcal Mu <q \ \mathcal Makebox{and} \ \mathcal Mu \mathcal Mid (\nu  x_m)\}$

is nonempty.

{\mathbf e}nd{lemma}
{\beta}egin{proof}
Since $\nu \in \nabla_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S)) = \nabla_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S)^{\langle m-1 \rangle})$, there exists $\mathcal Mathcal Tilde{\mathcal Mu} \in \mathsf{p}hi(\mathcal Mathcal S)^{\langle m-1 \rangle}$ such that $\mathcal Mathcal Tilde{\mathcal Mu} \mathcal Mid \nu$. Moreover, $\nu \not\in \nabla_e^{(m-1)}(\mathcal Mathcal S)$ implies $\mathcal Mathcal Tilde{\mathcal Mu} \not\in \mathcal Mathcal S.$ Hence $x_{m-1} \mathcal Mid \mathcal Mathcal Tilde{\mathcal Mu}$ and $\mathcal Mathcal Tilde{\mathcal Mu}x_m/x_{m-1} \in \mathcal Mathcal S.$ 
Let $\mathcal Mu := \mathcal Mathcal Tilde{\mathcal Mu}x_m/x_{m-1}$.
Note that $\mathcal Mu$ is projectively reduced since $\mathcal Mu \in \mathcal Mathcal S$.
Further, ${\delta}eg_{x_m} \mathcal Mu > 0$ since $\mathsf{p}hi(\mathcal Mu) \ne \mathcal Mu$. This implies that ${\delta}eg_{x_{m-1}} \mathcal Mu <q.$
Also, since $\mathcal Mathcal Tilde{\mathcal Mu} \mathcal Mid \nu$, we see that $\mathcal Mathcal Tilde{\mathcal Mu}/x_{m-1}$ divides $\nu$ and so 
$\mathcal Mu \mathcal Mid (\nu x_m)$.
{\mathbf e}nd{proof}

{\beta}egin{proposition}\label{injective}
Let $\mathcal Mathcal S \mathcal Mathcal Subset \mathcal Mathbb Mb$ be a finite set. Then 
$$
{\beta}ig|\Delta_e^{(m-1)}(\mathcal Mathcal S) \mathcal Mathcal Setminus \Delta_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S)){\beta}ig| \le {\beta}ig|\Delta_e^{(m)}(\mathsf{p}hi(\mathcal Mathcal S)) \mathcal Mathcal Setminus \Delta_e^{(m)}(\mathcal Mathcal S) {\beta}ig| \quad \mathcal Mathcal Text{for all $e\gg 0$. }
$$
{\mathbf e}nd{proposition}
{\beta}egin{proof}
For a nonnegative integer $e$ and $\nu  \in \Delta_e^{(m-1)}(\mathcal Mathcal S) \mathcal Mathcal Setminus \Delta_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S))$,  
define 
$$
S_\nu:=\{ \mathcal Mu \in \mathcal Mathcal S :  {\delta}eg_{x_{m-1}} \mathcal Mu <q \mathcal Mathcal Text{ and } \mathcal Mu \mathcal Mid (\nu  x_m^j) \ \mathcal Mathrm{ for \ some} \ j >0  \}.
$$
By Lemma \ref{nonempty},  
the set  $S_\nu$ is nonempty. Moreover, since $\mathcal Mathcal S$ is a finite set, we see that 
$$
k_{\nu} := \mathcal Min \{ {\delta}eg_{x_{m-1}}\! \mathcal Mu : \mathcal Mu \in S_{\nu}\} \quad \mathcal Mathcal Text{and} \quad
E:= \mathcal Max \{{\delta}eg_{x_m} \! \mathcal Mu : \mathcal Mu \in \mathcal Mathcal S\}
$$
are well-defined, and
$$
S_\nu =\{ \mathcal Mu \in \mathcal Mathcal S :  {\delta}eg_{x_{m-1}} \mathcal Mu <q \mathcal Mathcal Text{ and } \mathcal Mu \mathcal Mid (\nu  x_m^E ) \}.
$$

For $e \ge 0$, consider the map
$
\mathsf{p}si: \Delta_e^{(m-1)}(\mathcal Mathcal S) \mathcal Mathcal Setminus \Delta_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S)) \mathcal Mathcal To \mathcal Mathbb Mb_e
$ 
given by
$$
\nu=x_0^{i_0}\cdots x_{m-1}^{i_{m-1}} \longmapsto x_0^{i_0}\cdots x_{m-2}^{i_{m-2}} x_{m-1}^{k_\nu}x_{m}^{i_{m-1}-k_\nu}.
$$

Clearly, the map $\mathsf{p}si$ is injective and to prove the proposition, it is enough to show that the image of $\mathsf{p}si$ is contained in $\Delta_e^{(m)}(\mathsf{p}hi(\mathcal Mathcal S)) \mathcal Mathcal Setminus \Delta_e^{(m)}(\mathcal Mathcal S)$, provided $e\gg 0$. 

Let us fix $e\ge 0$ and $\nu = x_0^{i_0}\cdots x_{m-1}^{i_{m-1}} \in \Delta_e^{(m-1)}(\mathcal Mathcal S) \mathcal Mathcal Setminus \Delta_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S))$. Also, for simplicity, let us write $k= k_{\nu}$. From Lemma \ref{nonempty}, we see that 
$k <q$.

By the definition of $k$, there exists $\mathcal Mu^* \in \mathcal Mathcal S$ with ${\delta}eg_{x_{m-1}} \mathcal Mu^*=k$ such that $\mathcal Mu^* \mathcal Mid (\nu x_m^E)$.
Now since $\nu \in \mathcal Mathbb Mb^{(m-1)}_e$, we see that $i_j < q$ for $0\le j < m-1$, whereas $i_{m-1} \gg 0$ if $e\gg 0$. Hence $E \le i_{m-1} - k$ if $e \gg 0$.  This implies that
$\mathcal Mu^* \mathcal Mid \mathsf{p}si(\nu)$ whenever  $e \gg 0$. Since $\mathcal Mu^* \in \mathcal Mathcal S$, we conclude that $\mathsf{p}si(\nu) \not \in \Delta_e^{(m)}(\mathcal Mathcal S).$
We now prove that $\mathsf{p}si(\nu) \in \Delta_e^{(m)}(\mathsf{p}hi(\mathcal Mathcal S))$ for $e\gg 0$ by distinguishing  two cases.

\mathcal Mathcal Smallskip

\noindent
\mathcal Mathcal Textbf{Case 1:} $k=q-1.$

Since $\nu \in \nabla_e^{(m-1)}(\mathsf{p}hi(\mathcal Mathcal S))$, there exists $\mathcal Mu \in \mathsf{p}hi(\mathcal Mathcal S)$ such that $\mathcal Mu \mathcal Mid \nu$.

Let $\mathcal Mathcal Tilde{\mathcal Mu} \in \mathcal Mathcal S$ be such that $\mathcal Mu=\mathsf{p}hi(\mathcal Mathcal Tilde{\mathcal Mu}).$ 
Then either $\mathcal Mathcal Tilde{\mathcal Mu}=\mathcal Mu$ or $\mathcal Mathcal Tilde{\mathcal Mu}=\mathcal Mu x_m/x_{m-1}.$ If $\mathcal Mathcal Tilde{\mathcal Mu} = \mathcal Mu$, then $\nu \in \nabla_e^{(m-1)}(\mathcal Mathcal S)$, which is a contradiction. Thus $\mathcal Mathcal Tilde{\mathcal Mu}=\mathcal Mu x_m/x_{m-1}.$

Since $\mathcal Mu \mathcal Mid \nu,$ clearly $\mathcal Mathcal Tilde{\mathcal Mu} \mathcal Mid (\nu x_m)$. Hence $\mathcal Mathcal Tilde{\mathcal Mu} \in S_\nu.$ From the assumption that $k=q-1$, we conclude that ${\delta}eg_{x_{m-1}}(\mathcal Mathcal Tilde{\mathcal Mu})=q-1.$
But then $\mathcal Mu=\mathsf{p}hi(\mathcal Mathcal Tilde{\mathcal Mu})=\mathcal Mathcal Tilde{\mathcal Mu}$ which is again 
a contradiction. Therefore, the case $k = q-1$ can not occur.

\mathcal Mathcal Smallskip

\noindent
\mathcal Mathcal Textbf{Case 2:} $k<q-1.$

Suppose, if possible,  $\mathsf{p}si(\nu) \in  \nabla_e^{(m)}(\mathsf{p}hi(\mathcal Mathcal S))$. Then there  exists
$\mathcal Mu \in \mathsf{p}hi(\mathcal Mathcal S)$ such that $\mathcal Mu \mathcal Mid \mathsf{p}si(\nu)$. Write $\mathcal Mu=x_0^{j_0}\cdots x_{m}^{j_{m}}$.  Then $j_0 \le i_0, {\delta}ots, j_{m-2} \le i_{m-2}$ and $j_{m-1} \le k <q-1$.
Note that  $x_0^{j_0}\cdots x_{m-2}^{j_{m-2}} x_{m-1}^{j_{m-1}+j_m} \mathcal Mid \nu$ whenever $e \gg 0$.  This implies that $x_0^{j_0}\cdots x_{m-2}^{j_{m-2}} x_{m-1}^{j_{m-1}+j_m} \not \in \mathcal Mathcal S,$ since $\nu \in \Delta_e^{(m-1)}(\mathcal Mathcal S).$
Choose $\mathcal Mathcal Tilde{\mathcal Mu} \in \mathcal Mathcal S$ such that $\mathsf{p}hi (\mathcal Mathcal Tilde{\mathcal Mu}) = \mathcal Mu$. If $\mathcal Mathcal Tilde{\mathcal Mu} = \mathcal Mu$, then  by the  definition of $\mathsf{p}hi$ and the fact that  $x_0^{j_0}\cdots x_{m-2}^{j_{m-2}} x_{m-1}^{j_{m-1}+j_m} \not \in \mathcal Mathcal S$, we conclude that $j_{m-1} \ge q-1$, which is a contradiction.
Therefore 
$\mathcal Mathcal Tilde{\mathcal Mu} \neq \mathcal Mu.$ This implies that  $\mathcal Mathcal Tilde{\mathcal Mu} = x_0^{j_0}\cdots x_{m-1}^{j_{m-1}-1}x_{m}^{j_{m}+1} \in \mathcal Mathcal S.$ Furthermore, $\mathcal Mathcal Tilde{\mathcal Mu} \mathcal Mid \nu x_m^j$ whenever $j \ge j_m + 1$ and $e \gg 0$.
Thus $\mathcal Mathcal Tilde{\mathcal Mu} \in S_{\nu}$. 
But then ${\delta}eg_{x_{m-1}} \mathcal Mathcal Tilde{\mathcal Mu} = j_{m-1} - 1 < j_{m-1} \le k$, and this contradicts the minimality of $k$ if $e\gg 0$.  Hence $\mathsf{p}si(\nu) \in  \Delta_e^{(m)}(\mathsf{p}hi(\mathcal Mathcal S))$ 
for  $e\gg 0$. 
{\mathbf e}nd{proof}

{\beta}egin{theorem}\label{phi} Let $\mathcal Mathcal S \mathcal Mathcal Subset \mathcal Mathbb Mb$ be a finite set. Then
$|\Delta_e(\mathcal Mathcal S)| \le |\Delta_e(\mathsf{p}hi(\mathcal Mathcal S))|$ for 
$e \gg 0$.
{\mathbf e}nd{theorem}

{\beta}egin{proof}
Since $\mathsf{p}hi(\mathcal Mu)=\mathcal Mu$ for all $\mathcal Mu \in \mathcal Mathcal S$ with ${\delta}eg_{x_m} \mathcal Mu=0$ and since ${\delta}eg_{x_{m-1}} \mathsf{p}hi (\mathcal Mu) > 0$ if $\mathsf{p}hi (\mathcal Mu) \neq \mathcal Mu$, it is clear that
$\mathcal Mathcal S^{\langle j \rangle} = \mathsf{p}hi(\mathcal Mathcal S)^{\langle j \rangle}$ for $j=0, {\delta}ots, m-2$. Hence
$$\Delta_e^{(j)} (\mathcal Mathcal S) = \Delta_e^{(j)} (\mathcal Mathcal S^{\langle j \rangle}) = \Delta_e^{(j)} (\mathsf{p}hi(\mathcal Mathcal S)^{\langle j \rangle})= \Delta_e^{(j)} (\mathsf{p}hi(\mathcal Mathcal S)) \ \ \mathcal Mathrm{for \ all} \ j =0, {\delta}ots, m-2.$$
Thus it is enough to show that
$$|\Delta_e^{(m)}(\mathcal Mathcal S)| + |\Delta_e^{(m-1)}(\mathcal Mathcal S)| \le |\Delta_e^{(m)}(\mathsf{p}hi (\mathcal Mathcal S))| + |\Delta_e^{(m-1)}(\mathsf{p}hi (\mathcal Mathcal S))| .$$ This follows directly from Proposition \ref{injective} in view of
Lemmas \ref{claim1} and \ref{claim2}. 
{\mathbf e}nd{proof}

\mathcal Mathcal Section{Number of Solutions of Equations over Finite Fields}
\label{sec:er}

Throughout this section, $m$ denotes a fixed positive integer, while $d, r$ are nonnegative integers. 
Recall that $e_r(d,m)$ has been defined by {\mathbf e}qref{erdm} and the conventions {\mathbf e}qref{convention-erdm} whenever 

$ r \le {\beta}inom{m+d}{d}$. 
In this section, we shall prove our main results concerning 
$e_r(d,m)$

and a related quantity, called $\overline{e}_r(d,m)$ that we shall define shortly.

\mathcal Mathcal Subsection{Projectively Reduced Equations}\label{subsec:RedEqns}
As in \S\,\ref{subsec:projred},
let $\Gamma_q({\mathcal Mathbb F}_q)$ denote  the ideal of ${\mathcal Mathbb F}_q[x_0, {\delta}ots, x_m]$ generated by
$\{x_i^qx_j-x_ix_j^q \mathcal Mid 0 \le i < j \le m\}$. 
Evidently, $\Gamma_q({\mathcal Mathbb F}_q)$ is a homogeneous ideal and if we let $\Gamma_q({\mathcal Mathbb F}_q)_d$ denote its $d^{\rm th}$ homogeneous component, then its vector space dimension is known, e.g.,  from

\cite[Thm. 5.2]{MR}, namely 
{\beta}egin{equation}\label{eq:rd}
r_d:= {\delta}im_{{\mathcal Mathbb F}_q} \Gamma_q({\mathcal Mathbb F}_q)_d = \! \mathcal Mathcal Sum_{j=2}^{m+1} (-1)^j {{m+1}\choose{j}} \mathcal Mathcal Sum_{i=0}^{j-2} {{d+(i+1)(q-1) - jq + m}\choose{d+(i+1)(q-1) - jq }}
{\mathbf e}nd{equation}
for any $d\ge 0$.

As noted in 
\S\,\ref{subsec:projred}, the space of projectively reduced polynomials in ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]$ can be identified with ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]/\Gamma_q({\mathcal Mathbb F}_q)$. In particular, $r_d \le {{m+d}\choose{d}}$ and the dimension of this space of projectively reduced polynomials in ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d$
is ${\beta}inom{m+d}{d} - r_d$ for any nonnegative integer $d$. This also shows that
{\beta}egin{equation}\label{eq:Mbard-rd}
|\mathcal Mathbb Mb_d| =  {{m+d}\choose{d}} - r_d \quad \mathcal Mathcal Text{for any $d\ge 0$.}
{\mathbf e}nd{equation}
Using this or otherwise (see, e.g.,  \cite[p. 237]{MR}), we readily see that

{\beta}egin{equation}\label{eq:rdvalues}
 r_d = 0 \mathcal Mathcal Text{ if } d\le q, \ r_{q+1} = {{m+1}\choose{2}}, \ \mathcal Mathcal Text{and} \
 r_d = {{m+d}\choose{d}} - \mathsf{p}_m \mathcal Mathcal Text{ if } d > m(q-1). 

 {\mathbf e}nd{equation}

{\beta}egin{definition}\label{def:ebar}

For any $d\ge 0$ and $1\le r \le {\beta}inom{m+d}{d} - r_d$,
we define
{\beta}egin{equation}\label{eq:ebardm}
\overline{e}_r(d,m):=\mathcal Max_{G_1, {\delta}ots, G_r} |V(G_1, {\delta}ots, G_r)({\mathcal Mathbb F}_q)|,
{\mathbf e}nd{equation}
where the maximum is taken over all possible sets $\{G_1, {\delta}ots, G_r\}$ of $r$ linearly independent, projectively reduced polynomials in ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d.$ As a natural convention, we set $\overline{e}_0(d,m):=0$.
{\mathbf e}nd{definition}

It is clear 
that $\overline{e}_r(d,m) \le e_r(d,m)$ for all $d\ge 0$ and
$1 \le r \le {\beta}inom{m+d}{d} - r_d$. 
A more precise relationship is given by the following.

 {\beta}egin{theorem}\label{ers}
Let $d, r$ be nonnegative integers such that $r \le {\beta}inom{m+d}{d} - r_d$. Then

$$
e_{r+r_d}(d,m)=\overline{e}_{r}(d,m).
$$
In particular, $e_r(d,m)=\overline{e}_r(d,m)$ if $d \le q.$
{\mathbf e}nd{theorem}

{\beta}egin{proof}
Fix a basis $\{\Phi_1, {\delta}ots , \Phi_{r_d}\}$ of the ${\mathcal Mathbb F}_q$-vector space $\Gamma_q({\mathcal Mathbb F}_q)_d$. We will show that $e_{r+r_d}(d,m) \ge \overline{e}_{r}(d,m)$ and $e_{r+r_d}(d,m) \le \overline{e}_{r}(d,m)$.

Let $G_1, {\delta}ots, G_r \in {\mathcal Mathbb F}_q[x_0, {\delta}ots, x_m]_d$ be linearly independent and projectively reduced polynomials such that $|V(G_1, {\delta}ots, G_r)({\mathcal Mathbb F}_q)|=\overline{e}_r(d,m).$ Then every nontrivial linear combination of $G_1, {\delta}ots, G_r$ is projectively reduced and therefore it does not belong to $\Gamma_q({\mathcal Mathbb F}_q)_d$. Consequently, the polynomials $G_1, {\delta}ots, G_r, \Phi_1, {\delta}ots, \Phi_{r_d}$ are linearly independent. Since $\Phi_1, {\delta}ots, \Phi_{r_d}$ vanish everywhere on ${\mathbb P}^m ({\mathcal Mathbb F}_q)$, we see that  $V(G_1, {\delta}ots, G_r)({\mathcal Mathbb F}_q)=V(G_1, {\delta}ots, G_r, \Phi_1, {\delta}ots, \Phi_{r_d})({\mathcal Mathbb F}_q)$.
It follows that
$$
e_{r+r_d}(d,m) \ge |V(G_1, {\delta}ots, G_r, \Phi_1, {\delta}ots, \Phi_{r_d})({\mathcal Mathbb F}_q)| = |V(G_1, {\delta}ots, G_r)({\mathcal Mathbb F}_q)| = \overline{e}_r(d,m).
$$

To prove the other inequality, suppose $F_1,{\delta}ots,F_{r+r_d}$ are linearly independent polynomials in
${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d$ such that $|V(F_1,{\delta}ots,F_{r+r_d})({\mathcal Mathbb F}_q)|=e_{r+r_d}(d,m).$ Let $V_{r+r_d}$ denote the ${\mathcal Mathbb F}_q$-linear span of $F_1,{\delta}ots,F_{r+r_d}$. Then
$$
{\delta}im_{{\mathcal Mathbb F}_q} \sigmarac{V_{r+r_d} + \Gamma_q({\mathcal Mathbb F}_q)_d}{ \Gamma_q({\mathcal Mathbb F}_q)_d }

\ge {\delta}im_{{\mathcal Mathbb F}_q} V_{r+r_d} - {\delta}im_{{\mathcal Mathbb F}_q} \Gamma_q({\mathcal Mathbb F}_q)_d
= (r+ r_d) - r_d = r.
$$

So we can find $F'_1, {\delta}ots , F'_r \in V_{r+r_d}  + \Gamma_q({\mathcal Mathbb F}_q)_d$ that are  linearly independent (mod $\Gamma_q({\mathcal Mathbb F}_q)_d$). 
Let $G'_i = \overline{F}'_i$ denote the projective reduction of $F'_i$. Then $G'_1, {\delta}ots , G'_r$ are linearly independent and projectively reduced polynomials in ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d$. Hence as in the previous paragraph, we see that $G'_1, {\delta}ots, G'_r, \Phi_1, {\delta}ots, \Phi_{r_d}$ are linearly independent.
 Also, $F'_i -G'_i \in  \Gamma_q({\mathcal Mathbb F}_q)$ for all $i=1, {\delta}ots , r$. 
It follows that
{\beta}egin{eqnarray*} 
e_{r+r_d}(d,m) & \ge & |V(G'_1, {\delta}ots, G'_r, \Phi_1, {\delta}ots, \Phi_{r_d} )({\mathcal Mathbb F}_q)| \\
&= & |V(G'_1,{\delta}ots,G'_r)({\mathcal Mathbb F}_q)|\\
&= & |V(F'_1,{\delta}ots,F'_r)({\mathcal Mathbb F}_q)|\\
 & \ge & |V(F_1,{\delta}ots,F_{r+r_d})({\mathcal Mathbb F}_q)| \\
 &=& e_{r+r_d}(d,m).
{\mathbf e}nd{eqnarray*}  
Consequently, equality holds throughout, and in particular,

$$
\overline{e}_r(d,m) \ge |V(G'_1,{\delta}ots,G'_r)({\mathcal Mathbb F}_q)|= e_{r+r_d}(d,m).
$$

This proves that $e_{r+r_d}(d,m)=\overline{e}_{r}(d,m)$. Finally, if $d\le q$, then $r_d=0$, and therefore $e_{r}(d,m)=\overline{e}_{r}(d,m)$ in this case.

{\mathbf e}nd{proof}

{\beta}egin{remark}
As noted in \cite[Rem. 6.2]{DG2}, one has $e_r(d,m)=\mathsf{p}_m$ if $0 \le r \le r_d.$ Indeed, it is clear that for any $r\ge 0$ one has $e_r(d,m) \le |{\mathbb P}^m({\mathcal Mathbb F}_q)|=\mathsf{p}_m$, while for $r \le r_d$, one may choose linearly independent polynomials $G_1,{\delta}ots,G_r \in \Gamma_q({\mathcal Mathbb F}_q)_d$ and deduce that $e_r(d,m) \ge |V(G_1,{\delta}ots,G_r)({\mathcal Mathbb F}_q)|=\mathsf{p}_m.$
{\mathbf e}nd{remark}

The vanishing ideal of ${\mathbb A}^m({\mathcal Mathbb F}_q)$ is easy to determine; it is precisely the ideal of ${\mathcal Mathbb F}_q[x_1, {\delta}ots , x_m]$ generated by $\{x_i^q - x_i : 1\le i \le m\}$. It is not difficult to see (using, e.g., the principle of inclusion-exclusion) that the dimension of the ${\mathcal Mathbb F}_q$-vector space of polynomials of degree $\le d$ in this vanishing ideal is given by
$$
\rho_d:= \mathcal Mathcal Sum_{j=1}^m (-1)^{j-1} {\beta}inom{m}{j} {\beta}inom{m+d - jq}{d-jq} \quad \mathcal Mathcal Text{for all } d\ge 0.
$$
In case $d < q$, one can directly see that $\rho_d=0$.
Since the dimension of the ${\mathcal Mathbb F}_q$-vector space of polynomials of degree $\le d$ in ${\mathcal Mathbb F}_q[x_1, {\delta}ots , x_m]$ is clearly ${\beta}inom{m+d}{d}$, we see that $\rho_d \le {\beta}inom{m+d}{d}$ for all $d\ge 0$.

We have seen in \S\,\ref{subsec:Hr1} an affine analogue of $e_{r}(d,m)$, namely,
$e^{{\mathbb A}}_r(d,m):$. Here is a natural affine analogue of $\overline{e}_{r}(d,m)$. 
For $0\le r \le {\beta}inom{m+d}{d} - \rho_d$, we define
$$

\overline{e}^{{\mathbb A}}_r(d,m):=\mathcal Max_{g_1, {\delta}ots, g_r} |Z(g_1, {\delta}ots, g_r)({\mathcal Mathbb F}_q)|,
$$
where the maximum is taken over $r$ linearly independent and reduced polynomials $g_1, {\delta}ots , g_r$ of degree $\le d$ in ${\mathcal Mathbb F}_q[x_1, {\delta}ots , x_m]$. 

Arguing similarly as in the proof of Theorem~\ref{ers}, we see that
$$
e^{{\mathbb A}}_{r+\rho_d} (d,m) = \overline{e}^{{\mathbb A}}_r(d,m) \quad \mathcal Mathcal Text{for } 1\le r \le
{\beta}inom{m+d}{d} - \rho_d.
$$
Moreover, $e^{{\mathbb A}}_r(d,m) = \overline{e}^{{\mathbb A}}_r(d,m) $ if $d< q$, whereas $e^{{\mathbb A}}_r(d,m) = q^m$ if $r\le \rho_d$.

The result of Heijnen and Pellikaan \cite{HP} that was alluded to in the introduction solves the problem of determining $\overline{e}^{{\mathbb A}}_r(d,m) $.
A special case of this (when $d<q$) was stated earlier (Theorem~\ref{Hr1}). Here is the general version.

{\beta}egin{theorem}[Heijnen-Pellikaan]
\label{Hr}
Let $d$ be a nonnegative integer. Then
$$
\overline{e}^{{\mathbb A}}_r(d,m)  = H_r (d, m) \quad \mathcal Mathcal Text{for } 1\le r \le
{\beta}inom{m+d}{d} - \rho_d.
$$
{\mathbf e}nd{theorem}

\mathcal Mathcal Subsection{An Upper Bound}

In this subsection we will use the combinatorial results in Sections \ref{combin} and \ref{combin2} to obtain an upper bound for $e_r(d,m)$ when $d < q$. As we have seen in the last subsection, when $d \le q$, the
quantities $e_{r}(d,m)$ and $\overline{e}_{r}(d,m)$ coincide. Thus, we will work with $\overline{e}_{r}(d,m)$, and we begin by relating it with the ``maximal footprint" 
defined as follows.

{\beta}egin{definition}
Given any nonnegative integers $d, r$ and $e$ with $1\le r\le |\mathcal Mathbb Mb_d|$, i.e., $1\le r \le  {\beta}inom{m+d}{d} - r_d$,  define
$$
A_r(d,m;e):= \mathcal Max\{ |\Delta_e(\mathcal Mathcal S)| : \mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb_d \mathcal Mathcal Text{ with } |\mathcal Mathcal S| = r\}.
$$
{\mathbf e}nd{definition}

The relation between $A_r(d,m;e)$ and $\overline{e}_{r}(d,m)$ is given by the lemma below. 
In the remainder of this section, we consider the lexicographic order $\prec_{\mathrm{lex}}$ on the set $\mathcal Mathbb M$ of all monomials in $x_0, {\delta}ots , x_m$. For $0\ne F\in {\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]$, the largest monomial (w.r.t. $\prec_{\mathrm{lex}}$) appearing in $F$ (with a nonzero coefficient) will be denoted by $\mathrm{lm}(F)$.

{\beta}egin{lemma}\label{lem:distinctLM}
Let $d, r$ be nonnegative integers with $1\le r\le   {\beta}inom{m+d}{d} - r_d$. Then
$$
\overline{e}_{r}(d,m) = \mathcal Max_{F_1, {\delta}ots , F_r} |V(F_1, {\delta}ots , F_r)({\mathcal Mathbb F}_q)|,
$$
where the maximum is over all possible
sets $\{F_1, {\delta}ots , F_r\}$ of linearly independent and projectively reduced polynomials in ${\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]_d$ such that $\, \mathrm{lm}(F_1), {\delta}ots, \mathrm{lm}(F_r)$ are distinct. Consequently,
$$
\overline{e}_{r}(d,m)  \le A_r(d,m;e) \quad \mathcal Mathcal Text{for all } e \gg 0.
$$
{\mathbf e}nd{lemma}

{\beta}egin{proof}
If $G_1, {\delta}ots , G_r\in {\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]_d$ are linearly independent and projectively reduced, then we can easily obtain $F_1, {\delta}ots , F_r\in {\mathcal Mathbb F}_q[x_0, {\delta}ots , x_m]_d$ that are linearly independent and projectively reduced such that $\mathrm{lm}(F_1), {\delta}ots , \mathrm{lm}(F_r)$ are distinct and $V(F_1, {\delta}ots , F_r) = V(G_1, {\delta}ots , G_r)$. For example, we can obtain them recursively by taking $F_1:=G_1$ and
for $1< i  \le r$, taking 
$F_i := G_i - c_1F_1 -  {\delta}ots c_{i-1} F_{i-1}$, where $c_1, {\delta}ots , c_{i-1}\in {\mathcal Mathbb F}_q$ are chosen in such a way that none among 
$\, \mathrm{lm}(F_1), {\delta}ots , \mathrm{lm}(F_{i-1})$ appear in $F_i$. 
This proves the first assertion. The second assertion follows from the first using the projective ${\mathcal Mathbb F}_q$-footprint bound 
(Theorem \ref{thm:qfootprint}).
{\mathbf e}nd{proof}

The following result could be viewed as a projective analogue of Theorem~\ref{thm:Wei}, which in turn, arose from the works of Clements--Lindstr\"om \cite{CL}, Wei \cite{W} and Heijnen-Pellikaan \cite{HP, H}. 
For any  integers $d, r$ with $d\ge 0$ and $1\le r \le {\beta}inom{m+d}{d} - r_d$,  we denote by 
$\mathcal M_d(r)$  the set of first $r$ elements of $\mathcal Mathbb Mb_d$ in descending lexicographic order, and for any $d\ge 0$, we set
$\mathcal M_d(r)$ to be the empty set if $r=0$.
{\beta}egin{theorem}\label{thm:upperbound}

Let $d, r$ be integers with $1\le d < q$ and $1\le r \le {\beta}inom{m+d}{d} - r_d$.

Then
{\beta}egin{equation}
\label{eq:ProjWei}
|\Delta_e (\mathcal Mathcal S)| \le {\beta}ig|\Delta_e (\mathcal M_d(r)){\beta}ig|  \quad \mathcal Mathcal Text{for all } e \gg 0 \mathcal Mathcal Text{ and }\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb_d \mathcal Mathcal Text{ with } |\mathcal Mathcal S|=r.
{\mathbf e}nd{equation}
Consequently, $A_r (d, m; e) = |\Delta_e (\mathcal M_d(r))|$ and $\overline{e}_{r}(d,m)  \le |\Delta_e (\mathcal M_d(r))|$
for 
\hbox{$e \gg 0$.}
{\mathbf e}nd{theorem}

{\beta}egin{proof}
We prove {\mathbf e}qref{eq:ProjWei} by 
induction on $m$. Suppose $m=1$ and \hbox{$\mathcal Mathcal S =\! \{\mathcal Mu_1,{\delta}ots,\mathcal Mu_r\} \! \mathcal Mathcal Subseteq \! \mathcal Mathbb Mb_d$.} We may assume, without loss of generality, that $\mathcal Mu_1 \succ_{\mathrm{lex}} \cdots \succ_{\mathrm{lex}} \mathcal Mu_r$. Since 
the set $ \mathcal Mathbb Mb_d$ consists 
of $x_0^d \succ_{\mathrm{lex}} x_0^{d-1}x_1 \succ_{\mathrm{lex}} \cdots \succ_{\mathrm{lex}} x_1^d$, we obtain 
 ${\delta}eg_{x_0} \mathcal Mu_r < \cdots < {\delta}eg_{x_0} \mathcal Mu_1$.

Now observe that if $e \gg 0$, then $\Delta_e^{(0)}(\mathcal Mathcal S)={\mathbf e}mptyset$ if $x_0^d \in \mathcal Mathcal S$, whereas   $\Delta_e^{(0)}(\mathcal Mathcal S)=\{x_0^e\}$ if $x_0^d \not\in \mathcal Mathcal S$. 
Also, if $i:={\delta}eg_{x_0} \mathcal Mu_r$ and $e\ge i-1$, then $\Delta_e^{(1)}(\mathcal Mathcal S)=\{x_0^{i-1}x_1^{e-i+1},{\delta}ots,x_1^e\}$, and so 
 $|\Delta_e^{(1)}(\mathcal Mathcal S)|={\delta}eg_{x_0} \mathcal Mu_r.$
Consequently,  if $x_0^d \in \mathcal Mathcal S$, then ${\delta}eg_{x_0} \mathcal Mu_r \le d-r+1$ and
$$
|\Delta_e(\mathcal Mathcal S)|=|\Delta_e^{(0)}(\mathcal Mathcal S)|+|\Delta_e^{(1)}(\mathcal Mathcal S)|=0+{\delta}eg_{x_0} \mathcal Mu_r \le d-r+1 \quad \mathcal Mathcal Text{for all } e \gg 0,
$$
whereas if $x_0^d \not \in \mathcal Mathcal S$, then ${\delta}eg_{x_0} \mathcal Mu_r \le d-r$ and
$$
|\Delta_e(\mathcal Mathcal S)|=|\Delta_e^{(0)}(\mathcal Mathcal S)|+|\Delta_e^{(1)}(\mathcal Mathcal S)|=1+{\delta}eg_{x_0} \mathcal Mu_r \le d-r+1 \quad \mathcal Mathcal Text{for all } e \gg 0.
$$
On the other hand,  $\mathcal M_d(r)=\{x_0^d,x_0^{d-1}x_1,{\delta}ots,x_0^{d-r+1}x_1^{r-1}\}$ and a similar reasoning shows that $|\Delta_e(\mathcal M_d(r))|=d-r+1$ for all $e \gg 0$.

Next suppose $m>1$ and {\mathbf e}qref{eq:ProjWei}  holds for all values of $m$ smaller than the given one.

Consider any $\mathcal Mathcal S \mathcal Mathcal Subseteq \mathcal Mathbb Mb_d$ with $|\mathcal Mathcal S| = r$ and let $r':= |\mathcal Mathcal S^{\langle m-1 \rangle}|$.
By Theorem \ref{thm:projectivetoaffine}, 
$$
|\Delta_e(\mathcal Mathcal S)|=\mathcal Mathcal Sum_{{\mathbf e}ll=0}^m |\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S)|=\mathcal Mathcal Sum_{{\mathbf e}ll=0}^m |\mathsf {FP}^{({\mathbf e}ll)}(\mathcal Mathcal Sigma^{({\mathbf e}ll)}(\mathcal Mathcal S^{\langle{\mathbf e}ll\rangle}))|.
$$
Moreover $\mathcal Mathcal S^{\langle m \rangle}=\mathcal Mathcal S$, since $d<q$. This implies that $|\mathcal Mathcal S| = |\sigma^{(m)} (\mathcal Mathcal S^{\langle m \rangle})| = r$ and $\sigma^{(m)} (\mathcal Mathcal S^{\langle m \rangle}) \mathcal Mathcal Subset \mathcal Mathbb H_{\le d}^{(m)}$. Hence by Theorem \ref{thm:affinecomb}, 
$$
|\Delta_e^{(m)}(\mathcal Mathcal S)|=|\mathsf {FP}^{(m)}(\mathcal Mathcal Sigma^{(m)}(\mathcal Mathcal S^{\langle m \rangle}))| \le |\mathsf {FP}^{(m)}(T)|,

$$
where $T=\mathcal L_d^{(m)}(r') \cup \mathcal M_{d-1}^{(m)}(r-r')$.

Now define
$$
\mathcal Mathcal T := \mathcal L_d^{(m)}(r') \cup x_m\mathcal M_{d-1}(r-r'),

$$
where $x_m\mathcal M_{d-1}(r-r')=\{x_m \mathcal Mu \, : \, \mathcal Mu \in \mathcal M_{d-1}(r-r')\}.$ 
Since $d<q$, we readily see that 
$\mathcal Mathcal T \mathcal Mathcal Subset \mathcal Mathbb Mb_d$, $|\mathcal Mathcal T|=r$, and $\sigma^{(m)}(\mathcal Mathcal T)=T.$ 
Therefore by Theorem~\ref{thm:projectivetoaffine},
$$
|\Delta_e^{(m)}(\mathcal Mathcal S)|  \le |\mathsf {FP}^{(m)}(\sigma^{(m)}(\mathcal Mathcal T) )| =  |\Delta_e^{(m)}(\mathcal Mathcal T)|.
$$

On the other hand, by the induction hypothesis, 
$$
\mathcal Mathcal Sum_{{\mathbf e}ll=0}^{m-1} |\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S)| \le \mathcal Mathcal Sum_{{\mathbf e}ll=0}^{m-1} |\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal T)|.
$$

Consequently, from equation {\mathbf e}qref{eq:disjointshfp} and the definition of $\mathcal Mathcal T$, it follows that
{\beta}egin{equation}\label{eq:rearrange}
|\Delta_e(\mathcal Mathcal S)| = \mathcal Mathcal Sum_{{\mathbf e}ll=0}^m  |\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S)|  \le  \mathcal Mathcal Sum_{{\mathbf e}ll=0}^m |\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal T)|

=   |\Delta_e(\mathcal L_d^{(m)}(r') \cup x_m\mathcal M_{d-1}(r-r'))|.
{\mathbf e}nd{equation}
With this in view, we can replace $\mathcal Mathcal S$ by $\mathcal L_d^{(m)}(r') \cup x_m \mathcal M_{d-1}(r-r')$. Thus, to prove {\mathbf e}qref{eq:ProjWei}, it suffices to show that $|\Delta_e(\mathcal Mathcal S)| \le |\Delta_e(\mathcal Mathcal T)|$ for all $e \gg 0$, where we now take

$$
\mathcal Mathcal S :=\mathcal L_d^{(m)}(r') \cup x_m \mathcal M_{d-1}(r-r')  \quad \mathcal Mathcal Text{and} \quad \mathcal Mathcal T:=\mathcal M_d(r) .
$$

In view of Remark \ref{rem:sigmam}, 
$\sigma^{(m)}(\mathcal Mathcal T)=\mathcal M_d^{(m)}(r)$. Also clearly,  $\mathcal Mathcal T^{\langle m-1 \rangle} = \mathcal L_d^{(m)}(s')$ and $\mathcal Mathcal T \mathcal Mathcal Setminus \mathcal Mathcal T^{\langle m-1 \rangle}=x_m\mathcal M_{d-1}(r-s')$
 for some 
 $s' \ge 0$. 
Now we distinguish two cases.

\mathcal Mathcal Smallskip

\noindent
{{\beta}f Case 1:} $r' < s'.$

Let ${\alpha}lpha$ be the $(r'+1)^{\rm th}$ element of $\mathcal Mathbb H_d^{(m)}$. Since $r'<s'$, we see that ${\alpha}lpha \in \mathcal L_d^{(m)}(s')$ and ${\alpha}lpha \not \in \mathcal L_d^{(m)}(r').$ In particular, ${\alpha}lpha \in \mathcal Mathcal T \mathcal Mathcal Setminus \mathcal Mathcal S.$ We claim that there exists ${\beta}eta \in \mathcal Mathcal S$ such that ${\beta}eta \prec_{\mathrm{lex}} {\alpha}lpha.$
Suppose, if possible, the claim is false. Then ${\alpha}lpha \prec_{\mathrm{lex}}eq {\beta}eta$ for every ${\beta}eta \in \mathcal Mathcal S$. Since ${\alpha} \in \mathcal Mathcal T$ and $\mathcal Mathcal T = \mathcal M_d(r)$, this will imply that ${\beta}eta \in \mathcal Mathcal T$ for all ${\beta}eta\in \mathcal Mathcal S$. Thus, $\mathcal Mathcal S \mathcal Mathcal Subset \mathcal Mathcal T$. Further, the fact that $|\mathcal Mathcal S| = |\mathcal Mathcal T| =r$ implies that $\mathcal Mathcal S = \mathcal Mathcal T$.
But this is a contradiction since 
 ${\alpha}lpha \in \mathcal Mathcal T \mathcal Mathcal Setminus \mathcal Mathcal S.$
Hence the claim is true. Note that if ${\beta}eta \in \mathcal Mathcal S$ is such that ${\beta}eta \prec_{\mathrm{lex}} {\alpha}lpha$, then ${\alpha}lpha \not \in \mathcal L_d^{(m)}(r')$ implies that ${\beta}eta \not \in \mathcal L_d^{(m)}(r')$, and so ${\beta}eta \in x_m \mathcal M_{d-1}(r-r')$.

Now choose $\gamma = x_0^{i_0}\cdots x_{m}^{i_{m}}$ to be the largest (in lexicographical order) element of $\mathcal Mathcal S$ such that $\gamma \prec_{\mathrm{lex}} {\alpha}lpha.$ Then, as noted above, $\gamma  \in x_m \mathcal M_{d-1}(r-r')$.
Consider $\mathcal Mu: =  \gamma x_{m-1}/x_m$. Since $\gamma  \in x_m \mathcal M_{d-1}(r-r')$ and $d< q$, we see that $\mathcal Mu \in \mathcal Mathbb Mb_d$. Moreover, $\mathcal Mu \succ_{\mathrm{lex}} \gamma$ and in fact, $\mathcal Mu$ is the immediate successor of $\gamma$ in $ \mathcal Mathbb Mb_d$ in the lexicographic order. Hence $\gamma \prec_{\mathrm{lex}} {\alpha}lpha$ implies that $\mathcal Mu \prec_{\mathrm{lex}}eq {\alpha}lpha$. In case $x_m\mathcal Mid \mathcal Mu$, then $\mathcal Mu  \in x_m \mathcal M_{d-1}(r-r')$ because $\mathcal Mu \succ_{\mathrm{lex}} \gamma$ and  $x_m \mathcal M_{d-1}(r-r')$ is upwards closed in $x_m \mathcal Mathbb Mb_{d-1}$. But then $\mathcal Mu \in \mathcal Mathcal S$, and this contradicts the maximality of $\gamma$. Thus $x_m \nmid \mathcal Mu$, i.e., $i_m=1$ and $\mathcal Mu \not \in \mathcal Mathcal S$.  In particular, since $d< q$, we see that $i_{m-1}+1 < q$ and $x_0^{i_0}\cdots x_{m-2}^{i_{m-2}} x_{m-1}^{i_{m-1}+i_{m}} = \mathcal Mu  \not \in \mathcal Mathcal S$. Hence by Definition \ref{def:phi}, 
$\mathcal Mu = \mathsf{p}hi(\gamma) \in \mathsf{p}hi(\mathcal Mathcal S)^{\langle m-1 \rangle}$, even though $\gamma \not \in \mathcal Mathcal S^{\langle m-1 \rangle}$. On the other hand, if $\nu \in \mathcal Mathcal S^{\langle m-1 \rangle}$, then clearly, $\mathsf{p}hi(\nu) = \nu$, and
so $\nu \in \mathsf{p}hi(\mathcal Mathcal S)^{\langle m-1 \rangle}$.
 This shows that $r'':=|\mathsf{p}hi(\mathcal Mathcal S)^{\langle m-1 \rangle}|>|\mathcal Mathcal S^{\langle m-1 \rangle}|=r'.$ Moreover,

 by Theorem \ref{phi},  $|\Delta_e(\mathcal Mathcal S)| \le |\Delta_e(\mathsf{p}hi(\mathcal Mathcal S))|.$ Now, if $r'' < s'$, then we iterate the procedure by replacing $\mathcal Mathcal S$ with $\mathsf{p}hi(\mathcal Mathcal S)$. Else we proceed to the next case.

\mathcal Mathcal Smallskip

\noindent
{{\beta}f Case 2:} $r' \ge s'.$

In this case, for  ${\mathbf e}ll=0,{\delta}ots,m-1$, 
$$
\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal S)=\Delta_e^{({\mathbf e}ll)}(\mathcal L_d^{(m)}(r')) \mathcal Mathcal Subseteq \Delta_e^{({\mathbf e}ll)}(\mathcal L_d^{(m)}(s'))=\Delta_e^{({\mathbf e}ll)}(\mathcal Mathcal T) \quad \mathcal Mathcal Text{for all $e \gg 0$}.
$$
Moreover, $\sigma^{(m)}(\mathcal Mathcal T)=\mathcal M_d^{(m)}(r)$ and so by Theorem \ref{thm:Wei},
$$
|\Delta_e^{(m)}(\mathcal Mathcal S)|=|\mathsf {FP}^{(m)}(\sigma^{(m)}(\mathcal Mathcal S^{\langle m \rangle}))| \le |\mathsf {FP}^{(m)}(\sigma^{(m)}(\mathcal Mathcal T))|=|\Delta_e^{(m)}(\mathcal Mathcal T)|
\quad \mathcal Mathcal Text{for all $e \gg 0$}.
$$
Hence  from equation {\mathbf e}qref{eq:disjointshfp}, we obtain $|\Delta_e(\mathcal Mathcal S)| \le |\Delta_e(\mathcal Mathcal T)|$ for all $e \gg 0$, as desired.

{\mathbf e}nd{proof}

We are now ready to obtain an upper bound for $e_r(d,m)$ mentioned 
in the introduction. For any integers $d, r$ with $d\ge 0$ and $1\le r\le {\beta}inom{m+d}{d} - r_d$,

let us define
$$
K_r(d,m):=  \mathcal Mathcal Sum_{j=0}^{m-1}a_j \mathsf{p}_{m-1-j},
$$
where $(a_0, {\delta}ots , a_m)$ denotes the $r^{\rm th}$ element, in lexicographic order, of the set of $(m+1)$-tuple $(b_0, {\delta}ots , b_m)$ of nonnegative integers such that $b_0+\cdots + b_m =d$, or in other words, $a_0, {\delta}ots , a_m$ are unique nonnegative integers such that  $x_0^{a_0}\cdots x_m^{a_m}$ is  the smallest monomial in $\mathcal M_d(r)$ in lexicographic order.

{\beta}egin{theorem} 
\label{prop:upper}
Let $d,r$ be integers such that $1\le d<q$ and $1 \le r \le {\beta}inom{m+d}{d}.$ Then $A_r (d, m;e) =K_r(d,m)$ for all $e\gg 0$. Consequently,
$$
e_r(d,m) \le K_r(d,m).
$$
{\mathbf e}nd{theorem}

{\beta}egin{proof}
Let $x_0^{a_0}\cdots x_m^{a_m}$ be the smallest monomial in $\mathcal M_d(r)$ in lexicographic order.
In view of Theorem \ref{thm:upperbound}, it suffices to show that
$$
|\Delta_e(\mathcal M_d(r))|  =   \mathcal Mathcal Sum_{j=0}^{m-1}a_j \mathsf{p}_{m-1-j} \quad \mathcal Mathcal Text{for all $e \gg 0$}.
$$
We will prove this by induction on $m$.
The case $m=1$ is easy, since we have already noted in the proof of Theorem \ref{thm:upperbound} that $|\Delta_e(\mathcal M_d(r))|=d-r+1=(d-r+1)\mathsf{p}_0$ and  $x_0^{d-r+1}x_1^{r-1}$ is the smallest monomial in $\mathcal M_d(r)$ in lexicographic order if $m=1$.

Now suppose that $m>1$ and the result holds for all values of $m$ smaller than the given one.

In view of 
Remark \ref{rem:sigmam}, 
$\mathcal Mathcal Sigma^{(m)}(\mathcal M_d(r)) = \mathcal M_d^{(m)}(r)$ 

and therefore 
from equation {\mathbf e}qref{eq:ssl} and Theorem \ref{thm:projectivetoaffine}, we see that

$$
|\Delta_e^{(m)}(\mathcal M_d(r))|=|\mathsf {FP}^{(m)}(\mathcal M_d^{(m)}(r))|=\mathcal Mathcal Sum_{j=0}^{m-1} a_j q^{m-1-j} \quad \mathcal Mathcal Text{for all $e \gg 0$},
$$
where the last equality follows from \cite[Prop. 5.9]{HP} (see also \cite[Lem. 4.2]{BD}).
On the other hand, from equations {\mathbf e}qref{eq:disjointshfp} and {\mathbf e}qref{eq:ssl}, we  see 
that 

{\beta}egin{eqnarray*}
|\Delta_e(\mathcal M_d(r))| &=& |\Delta_e^{(m)}(\mathcal M_d(r))|+\mathcal Mathcal Sum_{j=0}^{m-1}|\Delta_e^{(j)}(\mathcal M_d(r)^{\langle j \rangle})|  \\
&= & |\Delta_e^{(m)}(\mathcal M_d(r))|+ |\Delta_e ( \mathcal M_d(r)^{\langle m-1 \rangle})| \quad \mathcal Mathcal Text{for all $e \ge 0$},
{\mathbf e}nd{eqnarray*}
Note that the smallest monomial in $\mathcal M_d(r)^{\langle m-1 \rangle}$ equals $x_0^{a_0} \cdots x_{m-2}^{a_{m-2}} x_{m-1}^{a_{m-1} + a_m}.$
Hence using the induction hypothesis, we obtain
$$
|\Delta_e(\mathcal M_d(r))| = \mathcal Mathcal Sum_{j=0}^{m-1}a_j q^{m-1-j}+\mathcal Mathcal Sum_{j=0}^{m-2} a_j \mathsf{p}_{m-2-j}=\mathcal Mathcal Sum_{j=0}^{m-1}a_j \mathsf{p}_{m-1-j} \quad \mathcal Mathcal Text{for all $e \gg 0$}.
$$
This completes the proof.

{\mathbf e}nd{proof}

As an application of Theorem \ref{prop:upper}, 
we show below that Conjecture \ref{conj:extended} holds (in the affirmative) for some 
``large" values of $r$.

{\beta}egin{lemma}\label{lem:equal}

Let $d$ be a positive integer with $d < q$ and let $r =\mathcal Mathcal Sum_{a=1}^i {\beta}inom{m+d-a}{d-1}$ for some 
positive integer $i \le m+1$. Then Conjecture \ref{conj:extended} holds 
and
$$
e_r(d,m)=\mathsf{p}_{m-i}.

$$
{\mathbf e}nd{lemma}

{\beta}egin{proof}
If $i=m+1$, then by equation {\mathbf e}qref{Pascal2}, $r = {\beta}inom{m+d}{d}$, and in this case it is clear that  $e_r(d,m)=0=\mathsf{p}_{m-i}$. Now suppose $i\le m$ so that $r < {\beta}inom{m+d}{d}$. We claim that
the $(r+1)^{\rm th}$ monomial of $\mathcal Mathbb Mb_d$ in descending lexicographical order is given by $x_i^d.$ This is clear if $i=m$, and the general case follows by decreasing induction on $i$ if we note that for $i< m$, the monomials $\mathcal Mu \in \mathcal Mathbb Mb_d$ that satisfy $x_i^d \succ_{\mathrm{lex}}eq \mathcal Mu \succ_{\mathrm{lex}} x_{i+1}^d$ are precisely the monomials of degree $d$ in the $m-i+1$ variables $x_i, {\delta}ots , x_m$ that are divisible by $x_i$, and the number of such monomials is clearly ${\beta}inom{m-i+d-1}{d-1}$, i.e., ${\beta}inom{m+d-(i+1)}{d-1}$.
From the above claim, it follows that the $r^{\rm th}$ monomial of $\mathcal Mathbb Mb_d$ in descending lexicographical order is given by $x_{i-1}x_m^{d-1}.$ Hence 
Theorem \ref{prop:upper} implies that  $e_r(d,m) \le \mathsf{p}_{m-1-(i-1)}=\mathsf{p}_{m-i}$, while 
Theorem \ref{lem:lower} shows 
that
$$
e_r(d,m) \ge \mathsf{p}_{m-i-1}+H_0(d-1,m-i)=\mathsf{p}_{m-i-1}+q^{m-i}=\mathsf{p}_{m-i}.
$$
This proves the lemma.

{\mathbf e}nd{proof}

In the next section, we use a little trick from coding theory and 
results proved in this section to prove the validity of Conjecture \ref{conj:extended} for some more 
values of $r$. 

\mathcal Mathcal Section{Connection with Projective Reed-Muller Codes}
\label{sec:codes}

We begin by recalling some basics about 
linear codes and the notion of generalized Hamming weight that is relevant for us. We will then consider the projective Reed-Muller codes, and show that the determination of their generalized Hamming weights is intimately related to the problem considered in this paper.

As before, $m$ will denote a fixed positive integer. Moreover, $n,k$ are positive integers with $k\le n$.

\mathcal Mathcal Subsection{Generalized Hamming weights and projective Reed-Muller codes}
Recall that a {\mathbf e}mph{$q$-ary $[n,k]$ (error-correcting linear)} {\mathbf e}mph{code} 
is defined as a $k$-dimensional ${\mathcal Mathbb F}_q$-linear subspace of ${\mathcal Mathbb F}_q^n$. 
If $C$ is a $q$-ary $[n, k]$ code, then the parameters $n$ and $k$ are known, respectively, as the {\mathbf e}mph{length} and the {\mathbf e}mph{dimension} of $C$.
For any 
$D \mathcal Mathcal Subseteq {\mathcal Mathbb F}_q^n$, we define the {\mathbf e}mph{support} of $D$ to be the subset 
$$
\mathcal Mathcal Supp(D) = \{i \in \{1,{\delta}ots, n\} :  c_i \neq 0 \ \mathcal Mathrm{for \ some} \ (c_1,{\delta}ots, c_n) \in D\} 

$$
and the {\mathbf e}mph{support weight} of $D$, denoted $\mathcal Mathrm{w}_H(D)$, to be the cardinality of $\mathcal Mathcal Supp (D)$.

Let $C$ be a $q$-ary $[n, k]$ code. For $1 \le r \le k$, the $r^{\rm th}$ {\mathbf e}mph{generalized Hamming weight} (also known as the $r^{\rm th}$ {\mathbf e}mph{higher weight}) of $C$ is defined to be
$$
d_r(C):=\mathcal Min \{\mathcal Mathrm{w}_H(D) :  D \mathcal Mathcal Text{ subspace of } C \mathcal Mathcal Text{ with } {\delta}im D=r\}.
$$

Note that $d_1 (C)$ is the minimum distance of $C$.

The notion of generalized Hamming weights was 
introduced by Wei \cite{W} 
and he showed that for any $q$-ary $[n, k]$ code $C$,

{\beta}egin{equation}\label{mon}
1 \le d_1(C) < d_2(C) {\delta}ots <d_k (C) \le n.
{\mathbf e}nd{equation}
Also, it is clear that $d_k(C)=n$ if $C$ is {\mathbf e}mph{nondegenerate}, i.e., $C$ is not contained in a coordinate hyperplane of ${\mathcal Mathbb F}_q^n$.

We now recall the projective Reed-Muller codes, 
introduced by Lachaud \cite{La}.

Let $P_1,{\delta}ots,P_{\mathsf{p}_m}$ be some fixed 
representatives  in ${\mathcal Mathbb F}_q^{m+1}$ 
for the $\mathsf{p}_m$ points of ${\mathbb P}^m({\mathcal Mathbb F}_q)$, e.g., 
we could represent each point of ${\mathbb P}^m({\mathcal Mathbb F}_q)$ by
an  $(m+1)$-tuple of elements of ${\mathcal Mathbb F}_q$, not all zero, such that the 
last nonzero coordinate is $1$. Consider 
the linear map
$$
\mathrm{ev}: {\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m] \mathcal Mathcal To {\mathcal Mathbb F}_q^{\mathsf{p}_m} \quad \mathcal Makebox{given \ by} \quad \mathrm{ev}(F)=(F(P_1), {\delta}ots, F(P_{\mathsf{p}_m})).
$$
The $d^{\rm th}$ order {\mathbf e}mph{projective Reed-Muller code}, denoted by $\mathrm{PRM}_q(d,m)$, is defined as the image of the space of homogeneous polynomials of degree $d$ in $x_0,{\delta}ots,x_m$ with coefficients in ${\mathcal Mathbb F}_q$, under the map $\mathrm{ev}$, i.e.,
$\mathrm{PRM}_q(d,m):=\mathrm{ev}({\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d).$
Note that $\mathrm{PRM}_q(d,m)$ is 
a nondegeneate linear code of length $\mathsf{p}_m$. 
A formula for the dimension of $\mathrm{PRM}_q(d,m)$ can be deduced from the observations in 
\S\,\ref{subsec:projred} and \S\,\ref{subsec:RedEqns}. Indeed, these observations show 
that 

the kernel of the  map $\mathrm{ev}$ restricted to ${\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d$ is precisely $\Gamma_q({\mathcal Mathbb F}_q)_d$; 
consequently, 

in view of equations {\mathbf e}qref{eq:rd} and {\mathbf e}qref{eq:Mbard-rd}, and with $r_d$ as in {\mathbf e}qref{eq:rd}, we see that
$$
\mathrm{PRM}_q(d,m) \cong \sigmarac{{\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d}{\Gamma_q({\mathcal Mathbb F}_q)_d} \quad \mathcal Mathcal Text{and} \quad
{\delta}im \mathrm{PRM}_q(d,m) = |\mathcal Mathbb Mb_d| = {\beta}inom{m+d}{d} - r_d.
$$
Thus we see that the dimension, say $k_q(d,m)$, of $\mathrm{PRM}_q(d,m)$ is given by

$$

k_q(d,m)= {\beta}inom{m+d}{d} - 
\mathcal Mathcal Sum_{j=2}^{m+1} (-1)^j {{m+1}\choose{j}} \mathcal Mathcal Sum_{i=0}^{j-2} {{d+(i+1)(q-1) - jq + m}\choose{d+(i+1)(q-1) - jq }}.
$$
In view of {\mathbf e}qref{eq:rdvalues}, this formula simplifies to ${\beta}inom{m+d}{d}$ if $d\le q$ and to
$\mathsf{p}_m$ if $d\ge m(q-1)+1$. In fact, if $d\ge m(q-1)+1$, then 

 $\mathrm{PRM}_q(d,m) = {\mathcal Mathbb F}_q^{\mathsf{p}_m}$. Thus projective Reed-Muller codes are of interest only when $d\le m(q-1)$. The 
 following result of S{\o}rensen \cite[Thm. 1]{So} gives an alternative formula for the dimension and an explicit formula for the 
 minimum distance of projective Reed-Muller codes of an arbitrary order. 

{\beta}egin{theorem}[S{\o}rensen] 
\label{thm:soe}
Suppose $1 \le d \le m(q-1)$. Then the projective Reed-Muller code $\mathrm{PRM}_q(d,m)$ is a nondegenerate linear code with
{\beta}egin{enumerate}
\item[{\rm (i)}]
${\delta}isplaystyle{{\delta}im \mathrm{PRM}_q(d,m) = \mathcal Mathcal Sum_{\mathcal Mathcal Substack{t=1 \\ t {\mathbf e}quiv d \mathsf{p}mod{q-1} }}^d \left( \mathcal Mathcal Sum_{j=0}^{m+1} (-1)^j {\beta}inom{m+1}{j}{\beta}inom{t-jq+m}{t-jq} \right),}$
\item[{\rm (ii)}]
$d_1(\mathrm{PRM}_q(d,m)) = (q-s)q^{m-t-1},$ where $s$ and $t$ are  unique integers such that 
$d-1 = t(q-1) + s$ and $\, 0 \le s < q-1.$
{\mathbf e}nd{enumerate}
{\mathbf e}nd{theorem}

\mathcal Mathcal Subsection{Connection with Homogeneous Equations over Finite Fields} 
It was noted in \cite[\S\,4.2]{DG} that if $d\le q$, then $d_r(\mathrm{PRM}_q(d,m))=\mathsf{p}_m-{e}_r(d,m)$ for 
each positive integer $r \le {\beta}inom{m+d}{d}$. We observe 
that there is a more general relation.
{\beta}egin{lemma}
\label{lem:drer}
Let $d,r$ be any integers with $d\ge 1$ 
and $1\le r \le {\beta}inom{m+d}{d} - r_d$. Then
{\beta}egin{equation}\label{dr}
d_r(\mathrm{PRM}_q(d,m))=\mathsf{p}_m-\overline{e}_r(d,m).
{\mathbf e}nd{equation}
{\mathbf e}nd{lemma}

{\beta}egin{proof}

Clearly, for any $r$-dimensional subspace $D$ of  $\mathrm{PRM}_q(d,m),$ there exist $r$ linearly independent, projectively reduced polynomials $F_1,{\delta}ots,F_r \in {\mathcal Mathbb F}_q[x_0,{\delta}ots,x_m]_d$
such that $D$ is the ${\mathcal Mathbb F}_q$-linear span of $\mathrm{ev}(F_1), {\delta}ots , \mathrm{ev}(F_r)$,

and moreover, 
$$
\mathcal Mathrm{w}_H(D)=\mathsf{p}_m-|\{i \, : \, F_j(P_i)=0\ \mathcal Makebox{for all $1 \le j \le r$}\}|=\mathsf{p}_m - |V(F_1,{\delta}ots,F_r)({\mathcal Mathbb F}_q)|.
$$
This yields the desired equality.
{\mathbf e}nd{proof}

{\beta}egin{corollary}\label{cor:ermono}

Let $d$ be an integer satisfying $1\le d\le q$.
Then
$$
e_1(d,m) > e_2(d,m) > {\delta}ots > e_{{\beta}inom{m+d}{d}}(d,m) = 0.
$$
{\mathbf e}nd{corollary}

{\beta}egin{proof}

By Theorem \ref{ers}, if $d\le q$, then $\overline{e}_r(d,m) = {e}_r(d,m)$ for $1\le r \le {\beta}inom{m+d}{d}$. So the desired inequalities follow from equation {\mathbf e}qref{mon} and Lemma \ref{lem:drer}. It is obvious from the definition that $e_{{\beta}inom{m+d}{d}}(d,m) = 0$, or alternatively, it follows from noting that $\mathrm{PRM}_q(d,m)$ is always a nondegenerate code.
{\mathbf e}nd{proof}

The following result generalizes Lemma \ref{lem:equal} as well as \cite[Thm. 4.7]{DG}, and extends the validity of
Conjecture \ref{conj:extended} 
for some  additional values of $r$.

{\beta}egin{theorem}\label{eq'}
Suppose $1\le d < q$ and $r=\mathcal Mathcal Sum_{a=1}^i {\beta}inom{m+d-a}{d-1} - t$ for some
positive integer $i \le m+1$. 
and nonnegative integer $t < d$. 
Then
$$
e_r(d,m)=\mathsf{p}_{m-i}+t \quad \mathcal Mathrm{and \ consequently,} \quad
d_r(\mathrm{PRM}_q(d,m))=\mathsf{p}_m-\mathsf{p}_{m-i}-t.
$$
{\mathbf e}nd{theorem}

{\beta}egin{proof}

By Lemma \ref{lem:equal}, $e_{r+t}(d,m)=\mathsf{p}_{m-i}$.  In particular, the result holds if $t=0$.

Now assume that $1\le t < d$. 

As in the proof of Lemma \ref{lem:equal}, we 
observe that the $r^{\rm th}$ monomial of $\mathcal Mathbb Mb_d$ in descending lexicographical order is given by $x_{i-1}x_{m-1}^{t}x_m^{d-1-t}.$ 
Hence Theorem \ref{prop:upper} implies
that $e_r(d,m) \le \mathsf{p}_{m-i}+t$, whereas

Corollary \ref{cor:ermono} implies that $e_r(d,m) \ge t + e_{r+t}(d,m)=t+\mathsf{p}_{m-i}.$ This yields the desired results. 
{\mathbf e}nd{proof}

{\beta}egin{example}
Suppose $m=2$ and $d=4$. Assume that $q > 4$. First, we know from \cite[Thm. 5.3]{BDG} that

equation {\mathbf e}qref{IC} is valid for all $r \le {\beta}inom{m+2}{2}$. Thus we know $e_r(d,m)$ for $1\le r\le 6$. Next, Lemma \ref{lem:equal} covers the values $r= 10, 14$ and $15= {\beta}inom{2+4}{4}$, since $10 =  {\beta}inom{5}{3}$, while $14 =  {\beta}inom{5}{3} + {\beta}inom{4}{3}$ and
$15 = {\beta}inom{5}{3} + {\beta}inom{4}{3} + {\beta}inom{3}{3}$. The remaining values are taken care of by Theorem \ref{eq'}.  Consequently, we can write down  the complete set of generalized Hamming weights of
$\mathrm{PRM}_q(4,2)$ for $q\ge 5$. A similar conclusion holds when $(m, d) = (2, 3)$ and $q\ge 4$.

{\mathbf e}nd{example}

Finally, we remark that  since $\overline{e}_r(d,m) = {e}_r(d,m)$ when  $d\le q$,
it is clear from 
{\mathbf e}qref{dr} that the results and conjectures about $e_r(d,m)$ in Section \ref{sec:er} can be easily reformulated in terms of $d_r(\mathrm{PRM}_q(d,m))$. As a sampling of one such result, we give below
a  reformulation of Theorem \ref{prop:upper} 
in the spirit of that in \cite[Thm. 5.10]{HP}.

{\beta}egin{proposition}\label{prop:boundgenHweight}
Let $r, d$ be positive integers with  
$d<q$ and $r \le {\beta}inom{m+d}{d}.$ Further, let 
$\mathcal Mathcal{Q}_{d}^m := \{({\alpha}_0, {\delta}ots, {\alpha}_m) \in Q^{m+1} :  \mathcal Mathcal Sum_{i=0}^m {\alpha}_i = (m+1)(q-1) - d \}$, where as in~\S\,\ref{subsec:3.1}, $Q:=\{0,1 , {\delta}ots, q-1\}$.   If $({\beta}eta_0,{\delta}ots,{\beta}eta_m)$ is the $r^{\rm th}$ element of $\mathcal Mathcal{Q}_{d}^m$ in ascending lexicographic order, then

$$d_r(\mathrm{PRM}_q(d,m)) \ge m+1+\mathcal Mathcal Sum_{j=0}^{m-1} {\beta}eta_j \mathsf{p}_{m-1-j}.$$
{\mathbf e}nd{proposition}

{\beta}egin{proof}
Let $x_0^{a_0}\cdots x_m^{a_m}$ be the smallest monomial in $\mathcal M_d(r)$ in lexicographic order. Then  Lemma \ref{lem:drer} and
Theorem \ref{prop:upper} imply that
{\beta}egin{align*}
d_r(\mathrm{PRM}_q(d,m)) \ge & \  \mathsf{p}_m - \mathcal Mathcal Sum_{j=0}^{m-1}a_j \mathsf{p}_{m-1-j}\\
                   = & \  m+1 + \mathcal Mathcal Sum_{j=0}^{m-1}(q-1)\mathsf{p}_{m-1-j}- \mathcal Mathcal Sum_{j=0}^{m-1}a_j \mathsf{p}_{m-1-j}\\
                   = & \ m+1 + \mathcal Mathcal Sum_{j=0}^{m-1}(q-1-a_j)\mathsf{p}_{m-1-j}.
{\mathbf e}nd{align*}
The result now follows by noting that the $(m+1)$-tuple $(q-1-a_0,{\delta}ots,q-1-a_m)$ is the $r^{\rm th}$ element of $\mathcal Mathcal{Q}_{d}^m$ in ascending lexicographic order.

{\mathbf e}nd{proof}

{\beta}egin{remark}
\label{rem:RVV}
In a recent work, Ramkumar, Vajha and Vijay Kumar \cite{RVV} have 
determined all the generalized Hamming weights of what they call the ``binary projective Reed-Muller code". However, the code they consider is not $\mathrm{PRM}_2(d,m)$ as defined above (and studied by Lachaud \cite{La}, S{\o}rensen \cite{So}, and others), but, in fact, a puncturing of a subcode of $\mathrm{PRM}_2(d,m)$. Indeed, they consider evaluations at points of ${\mathbb P}^m({\mathbb F}_2)$ (which, in this case, is just ${\mathbb F}_2^{m+1} \mathcal Mathcal Setminus\{(0,{\delta}ots, 0)\}$) of polynomials in ${\mathbb F}_2[x_0, {\delta}ots , x_m]_d$ that are reduced in the affine sense. The resulting code is degenerate, in general, and so they puncture it suitably so as to obtain a nondegenerate code, say $C_2(d,m)$ for $1\le d\le m$. 
The length of $\mathrm{PRM}_2(d,m)$ is $2^{m+1}-1$, while that of $C_2(d,m)$ is $2^{m+1}-\mathcal Mathcal Sum_{i=0}^{d-1} {\beta}inom{m}{i}$. Likewise, the dimension of $\mathrm{PRM}_2(d,m)$ is ${\beta}inom{m+2}{2}$, while that of $C_2(d,m)$ is ${\beta}inom{m+1}{2}$. Evidently, the generalized Hamming weight $d_r(C_2(d,m))$, for which a formula is given 
in \cite{RVV}, 
provides an upper bound for 

$d_r(\mathrm{PRM}_2(d,m))$ when $1\le r \le {\beta}inom{m+1}{2}$, but the equality does not hold, in general. 
{\mathbf e}nd{remark}

\mathcal Mathcal Section*{Acknowledgements}

Peter Beelen would like to thank IIT Bombay where parts of
this work were carried out when he was there in January 2017 as a Visiting Professor.
Sudhir Ghorpade would like to thank the Technical University of Denmark for short visits 
in June 2017 and July 2018 when some of this work was done.

Peter Beelen gratefully acknowledges  the support from The Danish Council of Scientific Research (DFF-FNU) for the project {\mathbf e}mph{Correcting on a Curve}, Grant No. 8021-00030B.  
Mrinmoy Datta is grateful for the support received 
from 
The Danish Council for Independent Research (Grant No. DFF-6108-00362) and the Research Council of Norway (Project No. 280731). 
 Sudhir Ghorpade gratefully acknowledges the support from  Indo-Norwegian Research grant INT/NOR/RCN/ICT/P-03/2018 from the Dept. of Science and Technology, Govt. of India and the Research Council of Norway (DST-RCN), MATRICS grant MTR/2018/000369 from the Science and Engineering Research Board, Govt. of India, and Award grant 12IRAWD009 from the Industrial Research and Consultancy Centre (IRCC), IIT Bombay. 
 
We are also thankful to the referee for some helpful comments and to Rati Ludhani for her careful proofreading of a preliminary version of this article. 
 

{\beta}egin{thebibliography}{22}

{\beta}ibitem{A}
I. Anderson, {\mathbf e}mph{Combinatorics of finite sets}, 
Dover, 
Mineola, NY, 2002.

{\beta}ibitem{B} P.~Beelen, 
A note on the generalized Hamming weights of Reed-Muller codes, 
{\mathbf e}mph{Appl. Algebra Engrg. Comm. Comput.} {{\beta}f 30} (2019), 
233--242.
{\beta}ibitem{BD} P.~Beelen and  M.~Datta, Generalized Hamming weights of affine Cartesian codes,

{\mathbf e}mph{Finite Fields Appl.} {{\beta}f 51} (2018), 130--145.

{\beta}ibitem{BDG} P.~Beelen, M.~Datta and S. R.~Ghorpade, Maximum number of common zeros of homogeneous polynomials over finite fields, 
{\mathbf e}mph{Proc. Amer. Math. Soc.} 
{{\beta}f 146} (2018), 1451--1468.

{\beta}ibitem{BDG18} P.~Beelen, M.~Datta and S. R.~Ghorpade, Vanishing ideals of projective spaces over finite fields and a projective footprint bound,  
{\mathbf e}mph{Acta Math. Sin. (Engl. Ser.)} {{\beta}f 35} (2019), 
47--63.

{\beta}ibitem{Bog}  M. Boguslavsky, On the number of solutions of polynomial systems, {\mathbf e}mph{Finite Fields Appl.} {{\beta}f 3}  (1997), 287--299.

{\beta}ibitem{CL} G. F.~Clements and B.~Lindstr\"om, A generalization of a combinatorial theorem of Macaulay, 
{\mathbf e}mph{J. Combin. Theory Ser. A} {{\beta}f 7} (1969), 230--238.

{\beta}ibitem{DG3} M.~Datta and S. R.~Ghorpade, On a conjecture of Tsfasman and an inequality of Serre for the number of points on hypersurfaces over finite fields,

{\mathbf e}mph{Mosc. Math. J.} {{\beta}f 15} 
(2015), 715--725.

{\beta}ibitem{DG2} M.~Datta and S. R.~Ghorpade, Number of solutions of systems of homogeneous polynomial equations over finite fields, 
{\mathbf e}mph{Proc. Amer. Math. Soc.} {{\beta}f 145} 
(2017), 525--541.

{\beta}ibitem{DG} M.~Datta and S. R.~Ghorpade, Remarks on Tsfasman-Boguslavsky conjecture and higher weights of projective Reed-Muller codes, {\mathbf e}mph{Arithmetic, Geometry, Cryptography and Coding Theory}, pp. 157--169, 

{\mathbf e}mph{Contemp. Math.} {{\beta}f 686}, Amer. Math. Soc., Providence, 2017. 

{\beta}ibitem{G}
S. R.~Ghorpade, A note on Nullstellensatz over finite fields, {\mathbf e}mph{Contributions in Algebra and Algebraic Geometry}, pp. 23--32, {\mathbf e}mph{Contemp. Math.}, {{\beta}f 738}, Amer. Math. Soc., Providence, 2019. 

{\beta}ibitem{HP} P.~Heijnen and R. Pellikaan,  {Generalized Hamming weights of $q$-ary Reed-Muller codes}, {\mathbf e}mph{IEEE Trans. Inform. Theory} {{\beta}f 44} (1998), 181--196.

{\beta}ibitem{H}P. W.~Heijnen, Some classes of linear codes, Ph.D. thesis, Technical University of Eindhoven, Netherlands, Aug 1999. 

{\beta}ibitem{Joly}
J.-R. Joly,  \'Equations et vari\'et\'es alg\'ebraiques sur un corps fini, {\mathbf e}mph{Enseign. Math.}, \mathcal Mathcal Textbf{19} (1973), 1--117.

{\beta}ibitem{La}
G.  Lachaud,  Projective  Reed-Muller  codes, Coding  theory  and  applications  (Cachan,1986), {\mathbf e}mph{Lecture Notes in Comput. Sci.}, vol. 311, Springer, Berlin, 1988, 125-129.

{\beta}ibitem{MR}
D.-J. Mercier and R. Rolland, Polyn\^{o}mes homog\`{e}nes qui s'annulent sur l'espace projectif
${\mathbb P}^m({\mathcal Mathbb F}_q)$, {\mathbf e}mph{J. Pure Appl. Algebra} {{\beta}f 124} (1998), 227--240.

{\beta}ibitem{RVV}
V. Ramkumar, M. Vajha, and P. Vijay Kumar, Determining the generalized Hamming weight hierarchy of the binary projective Reed-Muller code,  {\mathcal Mathcal Tt arXiv:1806.02028v1}, June 2018. 

{\beta}ibitem{Se}
J.-P.~Serre, Lettre \`a M. Tsfasman, 
Journ\'ees Arithm\'etiques (Luminy, 1989).
{{\mathbf e}m Ast\'erisque} No. 198-200 (1991), 351--353.

{\beta}ibitem{So}
A. B. S{\o}rensen, Projective Reed-Muller codes, {\mathbf e}mph{IEEE Trans. Inform. Theory} {{\beta}f 37} (1991), 1567--1576.

{\beta}ibitem{W}V. K.~Wei, Generalized Hamming weights for linear codes,  {\mathbf e}mph{IEEE Trans. Inform. Theory} {{\beta}f 37} (1991), 1412--1418.

{\beta}ibitem{Z}
C.~Zanella, Linear sections of the finite Veronese varieties and authentication systems defined using geometry,  {\mathbf e}mph{Des. Codes Cryptogr.} {{\beta}f 13}, 
(1998), 199--212.
{\mathbf e}nd{thebibliography}

{\mathbf e}nd{document}