# On the Minimum Distance, Minimum Weight Codewords, and the Dimension of
Projective Reed-Muller Codes

Sudhir R. Ghorpade  Department of Mathematics, Indian Institute of Technology
Bombay,
Powai, Mumbai 400076, India<EMAIL_ADDRESS>and  Rati Ludhani  Department
of Mathematics, Indian Institute of Technology Bombay,
Powai, Mumbai 400076, India<EMAIL_ADDRESS>
###### Abstract.

We give an alternative proof of the formula for the minimum distance of a
projective Reed-Muller code of an arbitrary order. It leads to a complete
characterization of the minimum weight codewords of a projective Reed-Muller
code. This is then used to determine the number of minimum weight codewords of
a projective Reed-Muller code. Various formulas for the dimension of a
projective Reed-Muller code, and their equivalences are also discussed.

This article is an expanded version of the talk given by the first named
author at the conference ALCOCRYPT, held at CIRM, Luminy, France, in February
2023. The talk is available in the Audiovisual Mathematics Library of CIRM and
on YouTube.

Sudhir Ghorpade is partially supported by the grant DST/INT/RUS/RSF/P-41/2021
from the Department of Science & Technology, Govt. of India, and the IRCC
award grant 12IRAWD009 from IIT Bombay.

Rati Ludhani is supported by Prime Minister’s Research Fellowship
PMRF-192002-256 at IIT Bombay.

##  1\. Introduction

Reed-Muller codes constitute a widely studied and fairly well-understood class
of linear codes. These codes were introduced, in the binary case, by Muller
[21], and further studied by Reed [22] in 1954. (See [23] for an account of
the early history.) Generalizations of Reed-Muller codes to the $q$-ary case
were considered and extensively studied in the following decade by Kasami,
Lin, and Peterson [16] and by Delsarte, Goethals, and MacWilliams [10]. As a
result of this, and also subsequent work, notably by Berger and Charpin [7]
and by Heijnen and Pellikaan [14], we know a great deal about $q$-ary Reed-
Muller codes of an arbitrary order. For instance, the length, dimension,
minimum distance, characterization and enumeration of minimum weight
codewords, duals, automorphisms, and generalized Hamming weights, are
completely known. For convenience of reader and ease of reference, a brief
summary of several of the known results is given in §2.1.

Projective Reed-Muller (PRM) codes in the general $q$-ary case, but of order
$d<q$, were introduced by Lachaud [17] in 1986. (See Section 3 of [13] for an
account of the history.) The length and dimension as well as bounds for the
minimum distance of PRM codes of order $d<q$, and the exact minimum distance
in the case $d=2$ and $q=2^{e}$, $e\geq 2$, were obtained by Lachaud [17].
Some of these ideas and results go back to Manin’s course of lectures during
1981-82 at Moscow State University, and are sketched in Chapter I, Section 3,
Example 2 b) of [28]. Tsfasman conjectured a sharp bound for the number of
${\mathbb{F}}_{q}$-rational points of a projective hypersurface of a given
degree $d\leq q$. This bound was proved in the affirmative by Serre [26], and
it was then shown by Lachaud [18] how the minimum distance of PRM codes of
order $d\leq q$ can be obtained as a consequence of Serre’s inequality.
Independently, Sørensen [27] gave explicit formulas for the length, dimension,
and the minimum distance of PRM codes not just of order $d\leq q$, but of an
arbitrary order. Further, he determined the duals of PRM codes as well.
Sørensen’s work has had a considerable impact as is indicated by the number of
citations to [27]. Moreover, PRM codes continue to be of considerable current
interest, and while the automorphism group is known (cf. [6]), the question
about the determination of their generalized Hamming weights is still open in
general even though there has been significant progress lately (see, e.g., [5]
and references therein for the current state of the art).

Recently, while revisiting Sørensen’s proof for the minimum distance of PRM
codes of an arbitrary order, we noticed that there was a gap in the argument.
While we realized later that the gap can be fixed and the result is correct as
stated, we were able to obtain an alternative proof of Sørensen’s result by
suitably adapting the arguments of Serre [26]. An additional dividend of this
alternative proof is that it leads to a characterization of the minimum weight
codewords of a projective Reed-Muller code. Since such a characterization is
not given in Sørensen’s paper [27] and it did not seem to be readily available
in the literature, we initially thought that it was new. However, we later
found that Rolland [25, Lem. $2.3$] has already given a characterization of
the minimum weight codewords of a PRM code using different methods; see also
Ballet and Rolland [2, Thm. 8] for a detailed proof of Rolland’s result.
Nonetheless, we believe that the alternative proof given here and the
resulting characterization is of some interest. Another noteworthy feature of
our proof is the use of the notion of projective reduction that was developed
and systematically used in [4], and this seems quite natural in the context of
PRM codes. We also give an explicit formula for the number of minimum weight
codewords of a PRM code of an arbitrary order. As far as we know, this appears
to be new and somewhat nontrivial, even after knowing a characterization of
the minimum weight codewords. Finally, we review various formulas for the
dimension of a PRM code of an arbitrary order and make some remarks on their
equivalence. We also include a direct proof of one of the dimension formulas
using the notion of projective reduction. An appendix reproduces a hitherto
unpublished proof of M. Quercia about the equivalence of two classical
formulas for the dimension of a PRM code.

##  2\. Basics of Reed-Muller and Projective Reed-Muller Codes

Fix, throughout this paper, a prime power $q$ and a positive integer $m$. As
usual, $\mathbb{Z}$ denotes the set of integers and ${\mathbb{F}}_{q}$ the
finite field with $q$ elements. Given any $b\in\mathbb{Z}$ and $a$ in an
integral domain $\mathsf{R}$ containing $\mathbb{Z}$ as a subring, the
corresponding binomial coefficient is defined by

${a\choose
b}:=\begin{cases}\displaystyle{\frac{a(a-1)\cdots(a-b+1)}{b!}}&\text{ if
}b\geq 0,\\\\[7.5pt] 0&\text{ if }b<0.\end{cases}$

This is, in general, an element of the quotient field of $\mathsf{R}$. In case
$\mathsf{R}=\mathbb{Z}$, it is in $\mathbb{Z}$.

###  2.1. Reed-Muller Codes

Let $\nu\in\mathbb{Z}$ with $\nu\geq 0$, and let
${\mathbb{F}}_{q}[X_{1},\ldots,X_{m}]_{\leq\nu}$ denote the space of all
polynomials in $m$ variables with coefficients in ${\mathbb{F}}_{q}$ of
(total) degree $\leq\nu$. Write
${\mathbb{F}}_{q}^{m}=\\{{{P}}_{1},\ldots,{{P}}_{q^{m}}\\}$. Consider the
evaluation map

$\displaystyle\text{ev}:{\mathbb{F}}_{q}[X_{1},\ldots,X_{m}]_{\leq\nu}\to{\mathbb{F}}_{q}^{q^{m}}\quad{\rm
defined\;by\;}\quad f\mapsto
c_{f}:=\left(f({{P}}_{1}),\ldots,f({{P}}_{q^{m}})\right).$

Clearly ev is a linear map and its image is a nondegenerate linear code of
length $q^{m}$; this code is called the _(generalized) Reed-Muller code_ of
order $\nu$, and it is denoted by $\mathrm{RM}_{q}(\nu,m)$.

It is easy to see that if $\nu<q$, then the map ev is injective and so $\dim\
\mathrm{RM}_{q}(\nu,m)={{m+\nu}\choose{\nu}}$; see, e.g., [11, Lem. 2.1].
Also, if $\nu<q$, then it follows from Ore’s inequality (see, e.g., [11, Cor.
2.7]) that the minimum distance of $\mathrm{RM}_{q}(\nu,m)$ is
$(q-\nu)q^{m-1}$. On the other hand, if $\nu\geq m(q-1)$, then it is not
difficult to see (using, for instance, a slight modification of the argument
in [12, Rem. 2]) that the map $\mathrm{ev}$ is surjective and so
$\mathrm{RM}_{q}(\nu,m)={\mathbb{F}}_{q}^{q^{m}}$. With this in view, we shall
assume that $0\leq\nu\leq m(q-1)$. In this general case, the restriction of
$\mathrm{ev}$ to the space of all _reduced_ 111A polynomial
$f\in{\mathbb{F}}_{q}[X_{1},\ldots,X_{m}]$ is said to be _reduced_ if
$\deg_{X_{i}}f\leq q-1$ for each $i=1,\dots,m$. polynomials in
${\mathbb{F}}_{q}[X_{1},\ldots,X_{m}]_{\leq\nu}$ is injective (see, e.g., [11,
Lem. 2.1]); consequently, the dimension, say $\rho_{q}(\nu,m)$, of
$\mathrm{RM}_{q}(\nu,m)$ is given by the number of reduced monomials in $m$
variables of degree $\nu$, and it is explicitly given by either of the
following formulas.

$\sum_{s=0}^{\nu}\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{s-iq+m-1}{s-iq}=\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{m+\nu-
iq}{m}.$ (1)

One may refer to [1, Thm. 5.4.1] for a proof of the first formula, and to [24,
Prop. 5] or [12, Lem. 1] for a direct proof of the second formula.

Kasami-Lin-Peterson [16] showed that if $\nu\in\mathbb{Z}$ with $0\leq\nu\leq
m(q-1)$ is written as ${\nu=t(q-1)+s}$ for unique $t,s\in\mathbb{Z}$ such that
$t\geq 0$ and $0\leq s<q-1$, then the minimum distance of
$\mathrm{RM}_{q}(\nu,m)$ is $(q-s)q^{m-t-1}$. Furthermore, with $t,s$ as
above, Delsarte-Goethals-MacWilliams [10] showed that
$c\in\mathrm{RM}_{q}(\nu,m)$ is a minimum weight codeword if and only if
$c=\text{ev}(f)$, where

$f=\omega_{0}\left(\prod_{i=1}^{t}(1-\ell_{i}^{q-1})\right)\prod_{j=1}^{s}(\ell_{t+1}-\omega_{j})$
(2)

for some linearly independent polynomials
$\ell_{1},\ldots,\ell_{t+1}\in{\mathbb{F}}_{q}[X_{1},\dots,X_{m}]$ of degree
$1$, and some $\omega_{0},\omega_{1},\dots,\omega_{s}\in{\mathbb{F}}_{q}$ with
$\omega_{0}\neq 0$ and $\omega_{1},\dots,\omega_{s}$ distinct. For an
alternative proof of this characterization, see [19]. Here it should be
understood that when $s=0$, the second product in (2) is empty (and hence
equal to $1$) and in this case only the existence and linear independence of
$t$ polynomials
$\ell_{1},\ldots,\ell_{t}\in{\mathbb{F}}_{q}[X_{1},\dots,X_{m}]$ of degree $1$
is asserted in the characterization. Delsarte-Goethals-MacWilliams [10]
further observed that the number of minimum weight codewords of
$\mathrm{RM}_{q}(\nu,m)$ is given by

$(q-1)q^{t}{{m}\brack{t}}_{q}M_{s},\quad\text{where}\quad
M_{s}:=\begin{cases}\displaystyle{{q\choose s}{{m-t}\brack{1}}_{q}}&\text{ if
}s>0,\\\\[7.5pt] 1&\text{ if }s=0.\end{cases}$ (3)

Here, and hereafter, for any $a,b\in\mathbb{Z}$, we denote, as usual, by
${{a}\brack{b}}_{q}$ the Gaussian binomial coefficient given by

${{a}\brack{b}}_{q}:=\begin{cases}\displaystyle{\frac{(q^{a}-1)(q^{a}-q)\cdots(q^{a}-q^{b-1})}{(q^{b}-1)(q^{b}-q)\cdots(q^{b}-q^{b-1})}}&\text{
if }0\leq b\leq a,\\\\[7.5pt] 0&\text{ otherwise}.\end{cases}$

Delsarte-Goethals-MacWilliams [10] also showed that the dual of
$\mathrm{RM}_{q}(\nu,m)$ is given by $\mathrm{RM}_{q}(m(q-1)-\nu-1,m)$, where
by convention, $\mathrm{RM}_{q}(-1,m)$ is the trivial code $\\{\mathbf{0}\\}$.
As indicated in the Introduction, the automorphism group as well as the
generalized Hamming weights of $\mathrm{RM}_{q}(\nu,m)$ are known, and for
these, we refer to the papers of Berger and Charpin [7] and of Heijnen and
Pellikaan [14] as well as Beelen and Datta [3].

###  2.2. Projective Reed-Muller Codes

Fix, in the remainder of this paper, a positive integer $d$. Given any
$k\in\mathbb{Z}$, let

$p_{k}:=\begin{cases}1+q+q^{2}+\cdots+q^{k}&\text{ if }k\geq 0,\\\ 0&\text{ if
}k<0.\end{cases}$

Each point of the $m$-dimensional projective space
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ over ${\mathbb{F}}_{q}$ admits a unique
representative in ${\mathbb{F}}_{q}^{m+1}$ in which the last nonzero
coordinate is $1$. Let $\mathsf{P}_{1},\ldots,\mathsf{P}_{p_{m}}$ be an
ordered listing of such representatives in ${\mathbb{F}}_{q}^{m+1}$ of points
of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. Let
${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ denote the space of homogeneous
polynomials in ${\mathbb{F}}_{q}[X_{0},\dots,X_{m}]$ of degree $d$ together
with the zero polynomial. Consider the evaluation map

$\displaystyle\operatorname{Ev}:{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}\to{\mathbb{F}}_{q}^{{p_{m}}}\quad{\rm
defined\;by}\quad F\mapsto
c_{F}:=(F({\mathsf{P}}_{1}),\ldots,F({\mathsf{P}}_{p_{m}})).$ (4)

Note that $\operatorname{Ev}$ is a linear map and its image is a nondegenerate
linear code of length $p_{m}$. This code is said to be the _projective Reed-
Muller code_ of order $d$ and length $p_{m}$, and it is denoted by
$\mathsf{PRM}_{q}(d,m)$.

A convenient way to study the projective Reed-Muller code is to use the notion
of projective reduction, which was introduced in [4] and employed in [11] to
determine the vanishing ideal of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. Let us
recall that the projective reduction $\overline{\mu}$ of a monomial
$\mu\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$ of positive degree is defined as
follows. Write $\mu=X_{0}^{a_{0}}\cdots X_{\ell}^{a_{\ell}}$ for unique
nonnegative integers $a_{0},\dots,a_{\ell}$ with $a_{\ell}>0$ so that
$X_{\ell}$ is the last variable in $\mu$. For $0\leq i\leq\ell-1$, let
$\overline{a}_{i}=a_{i}$ if $0\leq a_{i}\leq q-1$, whereas if $a_{i}\geq q$,
then let $\overline{a}_{i}$ be the unique integer such that
$\overline{a}_{i}\equiv a_{i}\ (\mathrm{mod}\ q-1)$ and
$1\leq\overline{a}_{i}\leq q-1$. We then define

$\overline{\mu}:=X_{0}^{\overline{a}_{0}}\cdots
X_{\ell-1}^{\overline{a}_{\ell-1}}X_{\ell}^{a_{\ell}+\sum_{i=0}^{\ell-1}(a_{i}-\overline{a}_{i})}.$

The monomial $\overline{\mu}$ is uniquely determined by $\mu$ and it has the
same degree as $\mu$. In case $\mu=1$, we set $\overline{\mu}:=1$. Observe
that $\overline{\mu}({\mathsf{P}})=\mu({\mathsf{P}})$ for all
${\mathsf{P}}\in{\mathbb{F}}_{q}^{m+1}$. We say that a monomial $\mu$ is
_projectively reduced_ if $\overline{\mu}=\mu$. These notions extend by
${\mathbb{F}}_{q}$-linearity to arbitrary polynomials in
${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$. Now let

$C_{q}(d,m):=\\{f\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}:f\text{ is
projectively reduced}\\}.$

Note that $C_{q}(d,m)$ is a ${\mathbb{F}}_{q}$-linear subspace of the
polynomial ring ${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$.

######  Lemma 2.1.

The restriction ${\rm Ev}|_{C_{q}(d,m)}$ of the evaluation map defined in (4),
to $C_{q}(d,m)$, is injective. Moreover, $\mathsf{PRM}_{q}(d,m)={\rm
Ev}(C_{q}(d,m))$.

###### Proof.

The first assertion follows from Lemma 3.1 of [11], and the second assertion
follows from Lemma 3.2 and Theorem 3.3 of [11]. ∎

######  Corollary 2.2.

If $F$ is a nonzero polynomial in $C_{q}(d,m)$, then $|V(F)|\leq p_{m}-1$.

###### Proof.

This is an immediate consequence of Lemma 2.1. ∎

######  Lemma 2.3.

If $d\geq m(q-1)+1$, then
$\mathsf{PRM}_{q}(d,m)=\mathsf{PRM}_{q}(m(q-1)+1,m)={\mathbb{F}}_{q}^{{p_{m}}}$.

###### Proof.

Let $\nu\in\\{1,\dots,p_{m}\\}$. Write
${\mathsf{P}}_{\nu}\in{\mathbb{F}}_{q}^{{{m+1}}}$ as
${\mathsf{P}}_{\nu}=(a_{0},\dots,a_{j_{\nu}-1},1,0,\ldots,0)$ for unique
$j_{\nu}\in\\{0,1,\dots,m\\}$ and
$a_{0},\ldots,a_{j_{\nu}-1}\in{\mathbb{F}}_{q}$. Now assume that $d\geq
m(q-1)+1$. Define the polynomial $F_{\nu}=F_{\nu}(X_{0},\dots,X_{m})$ by

$\displaystyle
F_{\nu}:=X^{d-m(q-1)}_{j_{\nu}}\prod\limits_{i=0}^{j_{\nu}-1}\left(X_{j_{\nu}}^{q-1}-(X_{i}-a_{i}X_{j_{\nu}})^{q-1}\right)\prod\limits_{k=j_{\nu}+1}^{m}(X_{j_{\nu}}^{q-1}-X_{k}^{q-1}).$
(5)

Clearly, $F_{\nu}\in{\mathbb{F}}_{q}[X_{0},\dots,X_{m}]_{d}$. Observe that
$F_{\nu}({\mathsf{P}}_{\nu})=1$ and $F_{\nu}({\mathsf{P}}_{\mu})=0$ for any
$\mu\in\\{1,\dots,p_{m}\\}$ with $\mu\neq\nu$. Hence any
$\lambda=(\lambda_{1},\dots,\lambda_{p_{m}})\in{\mathbb{F}}_{q}^{p_{m}}$ can
be written as $\lambda=\operatorname{Ev}(F)$, where
$F=\lambda_{1}F_{1}+\cdots+\lambda_{p_{m}}F_{p_{m}}$. It follows that
$\mathsf{PRM}_{q}(d,m)={\mathbb{F}}_{q}^{{p_{m}}}$. ∎

We remark that the polynomial (5) was used by Sørensen in [27, Lem. 3].

##  3\. Minimum Distance of Projective Reed-Muller Codes

In view of the results of the previous section, every codeword of
$\mathsf{PRM}_{q}(d,m)$ is of the form $\text{Ev}(F)$ for a unique
$F\in{C_{q}(d,m)}$, and determining the Hamming weight of this codeword
corresponds to finding the number of zeros in
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ of $F$.

For any $f_{1},\ldots,f_{r}\in{\mathbb{F}}_{q}[X_{1},\ldots,X_{m}]_{\leq d}$,
we denote by $Z(f_{1},\ldots,f_{r})$ the set of common zeros of
$f_{1},\ldots,f_{r}$ in $\mathbb{A}^{m}({\mathbb{F}}_{q})$, whereas for
$F_{1},\ldots,F_{r}\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$, we denote by
$V(F_{1},\ldots,F_{r})$ the set of common zeros of $F_{1},\ldots,F_{r}$ in
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. By a _hyperplane_ in
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ we shall mean a subset of the form
$V(L)$, where $L$ is a nonzero homogeneous linear polynomial in
${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$. We shall denote by
$\widehat{{\mathbb{P}}^{m}}$ the set of all hyperplanes in
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. Note that the cardinality of
$\widehat{{\mathbb{P}}^{m}}$ is $p_{m}$. Also note that if $P,P^{\prime}$ are
distinct points of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$, then
$|\\{H\in\widehat{{\mathbb{P}}^{m}}:P\in H\\}|=p_{m-1}$ and
$|\\{H\in\widehat{{\mathbb{P}}^{m}}:P,P^{\prime}\in H\\}|=p_{m-2}$.

######  Lemma 3.1.

Let $F$ be a nonzero projectively reduced polynomial in
${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$. Suppose $L$ is a nonzero
homogeneous linear polynomial in ${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$ such
that the hyperplane $V(L)$ is contained in $V(F)$. Then $L$ divides $F$.

###### Proof.

By a linear change of coordinates, we may assume that $L=X_{m}$. Separating
the monomials in $F$ that are divisible by $X_{m}$, we can write $F=X_{m}G+R$
for some homogeneous and projectively reduced polynomials
$G\in{\mathbb{F}}_{q}[X_{0},\dots,X_{m}]_{d-1}$ and
$R\in{\mathbb{F}}_{q}[X_{0},\dots,X_{m-1}]_{d}$. Since $V(X_{m})\subseteq
V(F)$, we see that $R(\mathsf{P})=0$ for all
$\mathsf{P}\in{\mathbb{P}}^{m-1}({\mathbb{F}}_{q})$. But $R$ is projectively
reduced, and so it follows from Lemma 2.1 that $R$ is the zero polynomial.
Thus, $X_{m}$ divides $F$. ∎

######  Theorem 3.2.

Let $F$ be a nonzero polynomial in $C_{q}(d,m)$. Then

$|V(F)|\leq p_{m}-\lceil{(q-s)q^{m-t-1}\rceil},$ (6)

where $t,s$ are unique integers such that $d-1=t(q-1)+s$ with $t\geq 0$ and
$0\leq s<q-1$. Moreover, if $1\leq d\leq m(q-1)$ and if the equality holds in
(6), then $V(F)$ is a union of at most $d$ distinct hyperplanes in
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$.

###### Proof.

In case $d\geq m(q-1)+1$, or equivalently, $t>m-1$, then
$\lceil{(q-s)q^{m-t-1}\rceil}=1$, and so (6) is a consequence of Corollary
2.2.

Now assume that $1\leq d\leq m(q-1)$. Then $t\leq m-1$ and therefore

$p_{m}-\lceil{(q-s)q^{m-t-1}\rceil}\geq p_{m}-q^{m}>0.$

In particular, (6) holds trivially if $V(F)$ is empty. Thus we shall assume
that $V(F)$ is nonempty.

We will use induction on $m$. First, suppose $m=1$. Then, $d\leq q-1$, and
hence $t=0$. Consequently,
$p_{m}-\lceil{(q-s)q^{m-t-1}\rceil}=p_{1}-(q-s)q^{1-0-1}=s+1=d$. Thus (6) is a
consequence of the elementary fact that a nonzero homogeneous polynomial of
degree $d$ in two variables over a field $F$ has at most $d$ non-proportional
zeros in $F^{2}\setminus\\{(0,0)\\}$. Moreover since hyperplanes in
${\mathbb{P}}^{1}({\mathbb{F}}_{q})$ are given by points, we also see that if
$m=1$ and if the equality holds in (6), then $V(F)$ is a union of exactly $d$
distinct hyperplanes in ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$.

Next, suppose $m>1$ and the result holds for smaller values of $m$. Define

$\displaystyle\Gamma:=\\{H\in\widehat{{\mathbb{P}}^{m}}:H\subseteq V(F)\\}.$

In view of Lemma 3.1, we see that $\Gamma$ can contain at most $d$ distinct
hyperplanes in ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. Write

$\Gamma=\\{H_{1},\ldots,H_{\ell}\\}\quad\text{and}\quad\mathcal{L}=\bigcup_{i=1}^{\ell}H_{i}$

for some nonnegative integer $\ell\leq d$. We shall now divide the proof in
two mutually exclusive and exhaustive cases.

Case 1. $\mathcal{L}=V(F)$.

In this case, we must have $\ell\geq 1$ since $V(F)$ is nonempty. By a linear
change of coordinates, we may assume that $H_{1}=V(X_{m})$. In view of Lemma
3.1, we see that $F(X_{0},\ldots,X_{m-1},0)=0$ and
$f(X_{0},\ldots,X_{m-1}):=F(X_{0},\ldots,X_{m-1},1)$ is a nonzero reduced
polynomial in ${\mathbb{F}}_{q}[X_{0},\ldots,X_{m-1}]_{\leq d-1}$. Thus

$\displaystyle|V(F)|$ $\displaystyle=$
$\displaystyle|V(F(X_{0},\ldots,X_{m-1},0))|+|Z(f)|$ $\displaystyle\leq$
$\displaystyle p_{m-1}+q^{m}-\lceil{(q-s)q^{m-t-1}\rceil}$ $\displaystyle=$
$\displaystyle p_{m}-\lceil{(q-s)q^{m-t-1}\rceil},$

where the second step uses the formula (recalled in § 2.1) for the minimum
distance of Reed-Muller code $\mathrm{RM}_{q}(d-1,m)$ and the fact that
$\mathrm{ev}(f)$ is a nonzero codeword of this code since $f$ is nonzero
reduced polynomial. Thus (6) is proved in Case 1.

Case 2. $\mathcal{L}\neq V(F)$.

In this case, there exists some $P\in V(F)\setminus\mathcal{L}$. In
particular, a hyperplane in ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ passing
through $P$ can not be contained in $V(F)$. For sections of $V(F)$ by such
hyperplanes, we make the following

Claim: If $H$ is any hyperplane in ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ such
that $H\not\subseteq V(F)$, then

$|V(F)\cap H|\leq p_{m-1}-\lceil{(q-s)q^{m-t-2}\rceil}.$

To prove this, fix a hyperplane $H$ in ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$
such that $H\not\subseteq V(F)$. By a linear change of coordinates, we may
assume that $H=V(X_{m})$. As in the proof of Lemma 3.1, we can write
$F=X_{m}G+R$ for some homogeneous and projectively reduced polynomials
$G\in{\mathbb{F}}_{q}[X_{0},\dots,X_{m}]_{d-1}$ and
$R\in{\mathbb{F}}_{q}[X_{0},\dots,X_{m-1}]_{d}$. Since $V(X_{m})\not\subseteq
V(F)$, we see that $R$ is a nonzero polynomial in $C_{q}(d,m-1)$. Also,
$V(F)\cap H=V(R)\cap H$ is the zero set of $R$ in
${\mathbb{P}}^{m-1}({\mathbb{F}}_{q})$. Hence by the induction hypothesis,
$|V(F)\cap H|\leq p_{m-1}-\lceil{(q-s)q^{m-t-2}\rceil}$. This proves the
chaim.

Recall that we had chosen $P\in V(F)\setminus\mathcal{L}$. Following Serre
[26], we consider the incidence set

$\mathcal{I}:=\\{(P^{\prime},H):P^{\prime}\in V(F)\setminus\\{P\\}\text{ and
}H\in\widehat{{\mathbb{P}}^{m}}\text{ with }P,P^{\prime}\in H\\}.$

This set can be counted in two different ways as follows. On the one hand,

$|\mathcal{I}|\;=\sum_{P^{\prime}\in
V(F)\setminus\\{P\\}}\sum_{\begin{subarray}{c}H\in\widehat{{\mathbb{P}}^{m}}\\\
P,P^{\prime}\in H\end{subarray}}1\;=\sum_{P^{\prime}\in
V(F)\setminus\\{P\\}}p_{m-2}\;=\;p_{m-2}(|V(F)|-1).$

On the other hand,

$\displaystyle|\mathcal{I}|$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}H\in\widehat{{\mathbb{P}}^{m}}\\\ P\in
H\end{subarray}}\sum_{\begin{subarray}{c}P^{\prime}\in V(F)\setminus\\{P\\}\\\
P^{\prime}\in H\end{subarray}}1$ $\displaystyle=$
$\displaystyle\sum\limits_{\begin{subarray}{c}H\in\widehat{{\mathbb{P}}^{m}}\\\
P\in H\end{subarray}}\left(|V(F)\cap H|-1\right)$ $\displaystyle\leq$
$\displaystyle\sum\limits_{\begin{subarray}{c}H\in\widehat{{\mathbb{P}}^{m}}\\\
P\in H\end{subarray}}\left(p_{m-1}-\lceil{(q-s)q^{m-t-2}\rceil}-1\right)$
$\displaystyle=$ $\displaystyle
p_{m-1}\left(p_{m-1}-\lceil{(q-s)q^{m-t-2}\rceil}-1\right)$

where the inequality in Step 3 follows from the claim above. On comparing both
these values of $|\mathcal{I}|$, we obtain

$\displaystyle|V(F)|$
$\displaystyle\leq\frac{p_{m-1}(p_{m-1}-\lceil{(q-s)q^{m-t-2}\rceil}-1)}{p_{m-2}}+1$
$\displaystyle=\frac{(p_{m-1})^{2}-p_{m-1}+p_{m-2}}{p_{m-2}}-\frac{p_{m-1}\lceil{(q-s)q^{m-t-2}\rceil}}{p_{m-2}}$
$\displaystyle=\frac{(p_{m-1})^{2}-q^{m-1}}{p_{m-2}}-\frac{p_{m-1}}{p_{m-2}}\lceil{(q-s)q^{m-t-2}\rceil}$
$\displaystyle=\frac{(q^{m}-1)^{2}-q^{m-1}(q-1)^{2}}{(q^{m-1}-1)(q-1)}-\left(\frac{q^{m}-1}{q^{m-1}-1}\right)\lceil{(q-s)q^{m-t-2}\rceil}$
$\displaystyle=\frac{q^{m+1}-1}{q-1}-\left(\frac{q^{m}-1}{q^{m-1}-1}\right)\lceil{(q-s)q^{m-t-2}\rceil}$
$\displaystyle<p_{m}-q\lceil{(q-s)q^{m-t-2}\rceil},$

where the last inequality follows since $q^{m}-1>q^{m}-q$. Thus,

$\displaystyle|V(F)|$ $\displaystyle<$
$\displaystyle\begin{cases}p_{m}-(q-s)q^{m-t-1}&\text{ if }t<m-1,\\\
p_{m}-q&\text{ if }t=m-1\end{cases}$ $\displaystyle\leq$
$\displaystyle\begin{cases}p_{m}-(q-s)q^{m-t-1}&\text{ if }t<m-1,\\\
p_{m}-(q-s)&\text{ if }t=m-1\end{cases}$ $\displaystyle=$ $\displaystyle
p_{m}-\lceil{(q-s)q^{m-t-1}\rceil}.$

This yields (6). Moreover, since the ineequality in (6) is strict in Case 2,
the second assertion is proved as well. ∎

######  Corollary 3.3.

Assume that $1\leq d\leq m(q-1)+1$. Then the minimum distance of projective
Reed-Muller code $\mathsf{PRM}_{q}(d,m)$ is

$\displaystyle{(q-s)q^{m-t-1}},$

where $t,s$ are unique integers such that $d-1=t(q-1)+s$ with $t\geq 0$ and
$0\leq s<q-1$. Moreover, if $\omega_{1},\ldots,\omega_{s}$ are any distinct
elements of ${\mathbb{F}}_{q}$ and if

$G:=X_{t}\prod_{i=0}^{t-1}(X_{i}^{q-1}-X_{t}^{q-1})\prod_{j=1}^{s}(X_{t+1}-\omega_{j}X_{t}),$
(8)

then $c_{G}=\mathrm{Ev}(G)$ is a minimum weight codeword of
$\mathsf{PRM}_{q}(d,m)$.

###### Proof.

Since $d\leq m(q-1)+1$, we see that $t\leq m$ and moreover, if $t=m$, then
$s=0$. Thus, $\lceil{(q-s)q^{m-t-1}\rceil}={(q-s)q^{m-t-1}}$. Hence Theorem
3.2 shows that

$d(\mathsf{PRM}_{q}(d,m))\geq{(q-s)q^{m-t-1}}.$ (9)

Next, suppose $\lambda_{1},\ldots,\lambda_{s}$ are distinct elements of
${\mathbb{F}}_{q}$ and $G$ is the polynomial given by (8). Clearly,
$G\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ and $G$ has zeros at all points
of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ except those of the form
$(0:\cdots:0:1:a_{t+1}:a_{t+2}:\cdots:a_{m})$, where $a_{t+1}\neq\omega_{j}$
for $j=1,\ldots,s$ and $a_{r}\in{\mathbb{F}}_{q}$ for $r=t+2,\ldots,m$. Thus
$|V(G)|=p_{m}-{(q-s)q^{m-t-1}}$. This, together with (9) shows that the
minimum distance of $\mathsf{PRM}_{q}(d,m)$ is ${(q-s)q^{m-t-1}}$ and
moreover, $c_{G}=\mathrm{Ev}(G)$ is a minimum weight codeword of
$\mathsf{PRM}_{q}(d,m)$. ∎

######  Remark 3.4.

The proof of minimum distance given by Sørensen [27, Thm. 1] has a mistake in
the case $t=m-1$, i.e., when $d-1=(m-1)(q-1)+s$, $0\leq s<q-1$. According to
the argument in [27, p. 1569], if ${\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus
V(F)=\\{P_{1},\ldots,P_{e}\\}$, then we can find linear homogeneous
polynomials $G_{i}(X),i=1,\ldots,e-1$ such that $G_{i}(P_{j})=\delta_{ij}$ for
$i=1,\ldots,e-1,\ j=1,\ldots,e$.222If one is writing equalities such as
$G_{1}(P_{1})=1$, then one should take $P_{1},\dots,P_{e}$ to be certain fixed
representatives in ${\mathbb{F}}_{q}^{m+1}$ of points of
${\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(F)$, but this is tacitly
understood in [27] and stated explicitly in Section II of [27]. Also, unlike
in [27], we have denoted $|{\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(F)|$
by $e$ (rather than $t$) so as to avoid a conflict with the notation used in
this paper.  However, this does not seem correct, since it is possible that
some $P_{j}$ is a linear combination of the other points $P_{i}$. Also,
$H(X)=F(X)\prod_{i=1}^{e-1}G_{i}(X)$ does not imply that
$V(H)={\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus\\{P_{e}\\}$. To correct
this, we may use a weaker condition. Namely, for each positive integer $i\leq
e-1$, take $G_{i}(X)$ to be a linear homogeneous polynomial such that
$V(G_{i})$ is a hyperplane which passes through $P_{i}$ but not through
$P_{e}$. This is possible since $P_{i},P_{e}$ are distinct points of
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. [See, for example, Lemma 4.1 below.]
Then $H(X):=F(X)\prod_{i=1}^{e-1}G_{i}(X)$ does have the property that
$V(H)={\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus\\{P_{e}\\}$.

######  Remark 3.5.

An alternative proof of the formula for the minimum distance of
$\mathsf{PRM}_{q}(d,m)$ is given by Carvalho, Neumann, and Lopez [9, Cor. 3.9
(c)], where they derive it from a more general result on projective nested
cartesian codes.

##  4\. Minimum Weight Codewords of Projective Reed-Muller Codes

In this section, we characterize the minimum weight codewords of projective
Reed-Muller codes in terms of homogeneous polynomials whose images under the
evaluation map (4) are these codewords. We begin with a simple observation.

######  Lemma 4.1.

Given any $A,B\in{\mathbb{P}}^{m}({\mathbb{F}}_{q})$ with $A\neq B$, there is
a homogeneous linear polynomial $L\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$
such that $L(A)=0$ and $L(B)\neq 0$.

###### Proof.

Let $A=(a_{0}:a_{1}:\cdots:a_{m})$ and $B=(b_{0}:b_{1}:\cdots:b_{m})$ be
distinct elements of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. Since $A\neq B$,
there are integers $i,j$ with $0\leq i<j\leq m$ such that
$a_{i}b_{j}-a_{j}b_{i}\neq 0$. Now $L=a_{i}X_{j}-a_{j}X_{i}$ has the desired
properties. ∎

Let us recall that the codewords of $\mathsf{PRM}_{q}(d,m)$ are of the form
$c_{F}$, defined as in (4), where $F$ varies over the elements of
${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$. The _support_ of such a codeword
is given by the set

$\mathrm{Supp}\left(c_{F}\right)=\left\\{\mathsf{P}\in\\{\mathsf{P}_{1},,\ldots,\mathsf{P}_{p_{m}}\\}:F(\mathsf{P})\neq
0\right\\},$

where $\mathsf{P}_{1},\ldots,\mathsf{P}_{p_{m}}$ are as in §2.2. For any
$F\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$, we can clearly identify
$\mathrm{Supp}\left(c_{F}\right)$ with
${\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(F)$. In case $c_{F}$ is a
minimum weight codeword, i.e., a nonzero codeword of least Hamming weight, we
can say a little more.

######  Lemma 4.2.

Let $F\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ be such that $c_{F}$ is a
minimum weight codeword of $\mathsf{PRM}_{q}(d,m)$. Then for any
$G\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$,

$V(F)=V(G)\Longleftrightarrow\mathrm{Supp}\left(c_{F}\right)=\mathrm{Supp}\left(c_{G}\right)\Longleftrightarrow
c_{F}=c_{\lambda G}\text{ for some nonzero }\lambda\in{\mathbb{F}}_{q}.$

###### Proof.

The first equivalence as well as the reverse implication in the second
equivalence is obvious. Suppose
$\mathrm{Supp}\left(c_{F}\right)=\mathrm{Supp}\left(c_{G}\right)$. Pick any
${\mathsf{P}}_{\nu}\in\mathrm{Supp}\left(c_{F}\right)$. Then
$F({\mathsf{P}}_{\nu})\neq 0\neq G({\mathsf{P}}_{\nu})$, and so there is
$\lambda\in{\mathbb{F}}_{q}$ with $\lambda\neq 0$ such that
$F({\mathsf{P}}_{\nu})=\lambda\,G({\mathsf{P}}_{\nu})$. Consequently,
$\mathrm{Supp}(c_{F-\lambda
G})\subseteq\mathrm{Supp}(c_{F})\setminus\\{{\mathsf{P}}_{\nu}\\}$. Since
$c_{F}$ is a minimum weight codeword, it follows that $c_{F-\lambda G}=0$,
that is, $c_{F}=c_{\lambda G}$. ∎

We are now ready to prove the main result of this section.

######  Theorem 4.3.

Assume that $1\leq d\leq m(q-1)+1$ and let $\,t,s$ be unique integers such
that $d-1=t(q-1)+s$ with $t\geq 0$ and $0\leq s<q-1$.Then
$c\in{\mathbb{F}}_{q}^{{p_{m}}}$ is a minimum weight codeword of
$\mathsf{PRM}_{q}(d,m)$ if and only if $c=c_{Q}$ for some
$Q\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ of the form

$\displaystyle
Q=L_{t}\prod_{i=0}^{t-1}\left(L_{t}^{q-1}-L_{i}^{q-1}\right)\prod_{j=1}^{s}(L_{t+1}-\omega_{j}L_{t})$
(10)

where $L_{0},\ldots,L_{t+1}$ are linearly independent homogeneous linear
polynomials in ${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$ and
$\omega_{1},\ldots,\omega_{s}$ are distinct elements of ${\mathbb{F}}_{q}$.
[Here it is understood that if $s=0$, then the second product in (10) is empty
(and hence equal to $1$) and in this case only the existence and linear
independence of $L_{0},\ldots,L_{t}$ is asserted.]

###### Proof.

If $Q$ is as in (10), then it is clear that
$Q\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ and moreover, by a linear
change of coordinates, we see that $|V(Q)|=|V(G)|$, where $G$ is as in (8).
Thus Corollary 3.3 implies that $c_{Q}$ is a minimum weight codeword of
$\mathsf{PRM}_{q}(d,m)$.

To prove the converse, let $F\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ be a
nonzero polynomial such that $|V(F)|=p_{m}-(q-s)q^{m-t-1}$. We need to show
that there exists some $Q\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ of the
form (10) such that $c_{F}=c_{Q}$. To this end, let us first consider the
extreme case when $d=m(q-1)+1$ so that $t=m$ and $s=0$. In this case
$|V(F)|=p_{m}-1$ and so there is unique $\nu\in\\{1,\dots,p_{m}\\}$ such that
$F({\mathsf{P}}_{\nu})\neq 0$ and $F(\mathsf{P}_{\mu})=0$ for all
$\mu\in\\{1,\dots,p_{m}\\}$ with $\mu\neq\nu$. Thus if $F_{\nu}$ is as in (5),
then by Lemma 4.2, $c_{F}=c_{\omega_{0}F_{\nu}}$ for some
$\omega_{0}\in{\mathbb{F}}_{q}$ with $\omega_{0}\neq 0$. Now, if as in the
proof of Lemma 2.1, we write
${\mathsf{P}}_{\nu}=(a_{0},\dots,a_{j_{\nu}-1},1,0,\ldots,0)$, and we let

$L_{t}=L_{m}=\omega_{0}X_{j_{\nu}}\quad\text{and}\quad
L_{i}=\begin{cases}(X_{i}-a_{i}X_{j_{\nu}})&\text{if }0\leq i<j_{\nu},\\\
X_{i+1}&\text{if }j_{\nu}\leq i\leq m-1,\end{cases}$

then $L_{0},\dots,L_{t}$ are linearly independent and it is clear from (5)
that $F$ is as in (10).

Thus, we will now assume that $1\leq d\leq m(q-1)$. Then $0\leq t\leq m-1$ and
$0\leq s\leq q-2$. This implies that

$p_{m}-|V(F)|=(q-s)q^{m-t-1}\geq 2.$ (11)

Further, since $|V(F)|$ attains the bound in (6), we see from Theorem 3.2 that
there is a positive integer $r\leq d$ and homogeneous linear polynomials
$G_{1},\dots,G_{r}$ in ${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$ such that the
corresponding hyperplanes $V(G_{1}),\dots,V(G_{r})$ are distinct (i.e.,
$G_{1},\dots,G_{r}$ are pairwise linearly independent) and

$V(F)=\bigcup_{i=1}^{r}V(G_{i}).$

We claim that $r=d$. To see this, assume the contrary, i.e., suppose $1\leq
r<d$. In view of (11), there are
$A,B\in{\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(F)$ such that $A\neq B$.
Hence by Lemma 4.1, there is a homogeneous linear polynomial $L$ in
${\mathbb{F}}_{q}[X_{0},\dots,X_{m}]$ such that $L(A)=0$ and $L(B)\neq 0$. Now
consider $G:=L^{d-r}G_{1}\cdots G_{r}$. Then
$G\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ and $G(P)=0$ for all $P\in
V(F)\cup\\{A\\}$. Also $c_{G}$ is a nonzero codeword of
$\mathsf{PRM}_{q}(d,m)$ since $G(B)\neq 0$. But the Hamming weight of $c_{G}$
is smaller than that of $c_{F}$ since $|V(G)|>|V(F)|$. This contradicts the
assumption that $c_{F}$ is a minimum weight codeword. Hence the claim that
$r=d$ is proved.

Now let $G:=G_{1}\cdots G_{d}$. Then $V(F)=V(G)$. Hence by Lemma 4.2, there is
$\lambda\in{\mathbb{F}}_{q}$ with $\lambda\neq 0$ such that $c_{F}=c_{\lambda
G}$. We can thus assume without loss of generality that $F$ is a product of
$d$ pairwise linearly independent homogeneous linear factors, and moreover by
a linear change of coordinates, we may assume that one of the linear factors
is $X_{m}$. Consequently, we can write $F=X_{m}F_{1}$ for some
$F_{1}\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d-1}$ such that $F_{1}$ is not
divisible by $X_{m}$. Thus, if we let
$f_{1}(X_{0},\dots,X_{m-1})=F_{1}(X_{0},\dots,X_{m-1},1)$, then $f_{1}$ is a
polynomial in ${\mathbb{F}}_{q}[X_{0},\ldots,X_{m-1}]$ of degree ${d-1}$.
Moreover, by intersecting $V(F)$ with the hyperplane $V(X_{m})$ and its
complement in ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$, we see that

$p_{m}-(q-s)q^{m-t-1}=|V(F)|=p_{m-1}+|Z(f_{1})|\ \text{ and so }\
|Z(f_{1})|=q^{m}-(q-s)q^{m-t-1}.$

It follows that $\mathrm{ev}(f_{1})$ can be viewed as a minimum weight
codeword of the Reed-Muller code $\mathrm{RM}_{q}(d-1,m)$. Hence by [10, Thm.
2.6.3], $\mathrm{ev}(f_{1})=\mathrm{ev}(f)$ for some
$f\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m-1}]$ of the form (2), i.e.,

$f=\omega_{0}\left(\prod_{i=1}^{t}(1-\ell_{i}^{q-1})\right)\prod_{j=1}^{s}(\ell_{t+1}-\omega^{\prime}_{j})$

for some linearly independent polynomials
$\ell_{1},\ldots,\ell_{t+1}\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m-1}]$ of
degree $1$, and some
$\omega_{0},\omega^{\prime}_{1},\dots,\omega^{\prime}_{s}\in{\mathbb{F}}_{q}$
with $\omega_{0}\neq 0$ and $\omega^{\prime}_{1},\dots,\omega^{\prime}_{s}$
distinct. Now

$F(X_{0},\ldots,X_{m})=X_{m}^{d}F_{1}\bigg{(}\frac{X_{0}}{X_{m}},\ldots,\frac{X_{m-1}}{X_{m}},1\bigg{)}\
=X_{m}\bigg{(}\\!X_{m}^{d-1}f_{1}\bigg{(}\frac{X_{0}}{X_{m}},\ldots,\frac{X_{m-1}}{X_{m}}\bigg{)}\bigg{)}$

and so if we let

$Q(X_{0},\ldots,X_{m}):=X_{m}\left(X_{m}^{d-1}f\left(\frac{X_{0}}{X_{m}},\ldots,\frac{X_{m-1}}{X_{m}}\right)\right),$

then we see that $Q\in{\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]_{d}$ and
$F({\mathsf{P}}_{\nu})=Q({\mathsf{P}}_{\nu})$ for each $\nu=1,\dots,p_{m}$,
and hence $c_{F}=c_{Q}$. Moreover if we let

$L_{i}(X_{0},\ldots,X_{m}):=X_{m}\left(\ell_{i+1}\left(\frac{X_{0}}{X_{m}},\ldots,\frac{X_{m-1}}{X_{m}}\right)\right)\quad\text{for
$i=0,1,\dots,t-1$,}$

and also let $L_{t}:=\omega_{0}X_{m}$ and in case $s>0$, we further let

$L_{t+1}(X_{0},\ldots,X_{m}):=X_{m}\left(\ell_{t+1}\left(\frac{X_{0}}{X_{m}},\ldots,\frac{X_{m-1}}{X_{m}}\right)\right),$

then we see that $L_{1},\dots,L_{t+1}$ are nonzero homogeneous linear
polynomials in ${\mathbb{F}}_{q}[X_{0},\ldots,X_{m}]$ and moreover

$Q=L_{t}\prod_{i=0}^{t-1}\left(L_{t}^{q-1}-L_{i}^{q-1}\right)\prod_{j=1}^{s}(L_{t+1}-\omega_{j}L_{t})\quad\text{where}\quad\omega_{j}:=\frac{\omega^{\prime}_{j}}{\omega_{0}}\text{
for }j=1,\dots,s.$

It remains to show that $L_{0},\dots,L_{t+1}$ are linearly independent, or
more precisely, if $s=0$, then $L_{0},\dots,L_{t}$ are linearly independent,
whereas if $s>0$, then $L_{0},\dots,L_{t+1}$ are linearly independent. To this
end, first suppose $s=0$. Since $\ell_{1},\ldots,\ell_{t}$ are linearly
independent, it is clear that $L_{0},\ldots,L_{t-1}$ are linearly independent.
Now if $L_{0},\dots,L_{t}$ were linearly dependent, then $X_{m}$ would be a
${\mathbb{F}}_{q}$-linear combination of $L_{0},\dots,L_{t-1}$. On the other
hand, since $|V(Q)|=|V(F)|=p_{m}-q^{m-t}<p_{m}$ , there is some
$A\in{\mathbb{P}}^{m}({\mathbb{F}}_{q})$ such that $Q(A)\neq 0$. In
particular, $L_{t}(A)\neq 0$, but $L_{i}(A)=0$ for $i=0,1,\dots,t-1$, which
shows that $X_{m}$ cannot be a ${\mathbb{F}}_{q}$-linear combination of
$L_{0},\dots,L_{t-1}$.

Next, suppose $s>0$. As before, the linear independence of
$\ell_{1},\ldots,\ell_{t+1}$ shows that $L_{0},\dots,L_{t-1},L_{t+1}$ are
linearly independent. Fix an arbitrary element $A$ of
${\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(Q)$. Since $Q(A)\neq 0$, we
must have $L_{t}(A)\neq 0$ and $L_{i}(A)=0$ for $i=0,1,\dots,t-1$. In
particular, we can find a unique representative of $A$ in
${\mathbb{F}}_{q}^{m+1}$, say
$\mathsf{A}=(\mathsf{a}_{0},\mathsf{a}_{1},\dots,\mathsf{a}_{m})$, such that
$\mathsf{a}_{m}=1$. Suppose, if possible, $X_{m}$ is a
${\mathbb{F}}_{q}$-linear combination of $L_{0},\dots,L_{t-1},L_{t+1}$. Then
$L_{t+1}(\mathsf{A})$ is necessarily equal to a fixed nonzero scalar in
${\mathbb{F}}_{q}$, say $\lambda$, which is independent of the choice of $A$
in ${\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(Q)$. It follows that
$|{\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(Q)|$ is at most

$|\\{\mathbf{a}=(a_{0},\dots,a_{m-1})\in{\mathbb{F}}_{q}^{m}:\ell_{i}(\mathbf{a})=0\text{
for }i=1,\dots,t\text{ and }\ell_{t+1}(\mathbf{a})=\lambda\\}|=q^{m-t-1},$

where the last equality follows since $\ell_{1},\ldots,\ell_{t+1}$ are
linearly independent polynomials of degree $1$. But then

$(q-s)q^{m-t-1}=|{\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(Q)|\leq
q^{m-t-1},$

which is a contradiction since $s<q-1$. This shows that $L_{0},\dots,L_{t+1}$
are linearly independent. ∎

##  5\. Enumeration of Minimum Weight Codewords

In this section, we will use Theorem 4.3 to prove the following.

######  Theorem 5.1.

Assume that $1\leq d\leq m(q-1)+1$ and let $t,s$ be unique integers such that
$d-1=t(q-1)+s$ with $t\geq 0$ and $0\leq s<q-1$.Then the number of minimum
weight codewords of $\mathsf{PRM}_{q}(d,m)$ is equal to

$\left(q^{m+1}-1\right){{m}\brack{t}}_{q}N_{s},\quad\text{where}\quad
N_{s}=\begin{cases}1&{\rm if}\ s=0,\\\
\displaystyle{\frac{1}{s+1}\binom{q}{s}{\genfrac{[}{]}{0.0pt}{}{m-t}{1}}_{q}}&{\rm
if}\ s\neq 0.\end{cases}$ (12)

Before giving a proof of this result, it will be convenient to set some
notation and terminology, and also some preliminary results which will be
useful to us in the sequel. First, let us fix $d,t$ and $s$ as in the
statement of Theorem 5.1. We shall denote by $\mathcal{M}_{q}(d,m)$, and often
simply by $\mathcal{M}$, the set of all minimum weight codewords of
$\mathsf{PRM}_{q}(d,m)$. The polynomial ring
${\mathbb{F}}_{q}[x_{0},\dots,x_{m}]$ in $m+1$ variables with coefficients in
${\mathbb{F}}_{q}$ will be denoted by $R$, and for any nonnegative integer
$e$, we denote by $R_{e}$ the space of homogeneous polynomials in $R$ of
degree $e$, including the zero polynomial. In particular, $R_{1}$ is the
$(m+1)$-dimensional ${\mathbb{F}}_{q}$-vector space of homogeneous linear
polynomials in $R$. We shall use a slight variant of the notion of support of
a codeword of $\mathsf{PRM}_{q}(d,m)$. Namely, given any $F\in R_{d}$, we let

$\mathrm{supp}(c_{F})=\\{P\in{\mathbb{P}}^{m}({\mathbb{F}}_{q}):F(P)\neq
0\\}={\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus V(F).$

Thus, the only difference between $\mathrm{supp}(c_{F})$ and
$\mathrm{Supp}(c_{F})$ is that the former comprises of points of
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ rather than their chosen representatives
in ${\mathbb{F}}_{q}^{m+1}$. Let $\mathcal{P}({\mathbb{P}}^{m})$ denote the
set of all subsets of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. In view of Lemma
4.2, we see that the map $\Phi:\mathcal{M}\to\mathcal{P}({\mathbb{P}}^{m})$
defined by $\Phi(c):=\mathrm{supp}(c)$ has the property that

$|\mathcal{M}|=(q-1)|\Phi(\mathcal{M})|.$ (13)

Continuing with notations, for any $e\in\mathbb{Z}$ with $-1\leq e\leq m$, we
denote by $\mathcal{G}_{e}({\mathbb{P}}^{m})$ the Grassmannian consisting of
all $e$-dimensional projective linear subspaces333As per the standard
conventions, the empty subset of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$, which
corresponds to the zero subspace of ${\mathbb{F}}_{q}^{m+1}$, is the only
projective linear subspace of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ of
dimension $-1$. of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. It is elementary and
well-known that the cardinality of $\mathcal{G}_{e}({\mathbb{P}}^{m})$ is the
Gaussian binomial coefficient ${{m+1}\brack{e+1}}_{q}$. Here is a useful
preliminary result.

######  Lemma 5.2.

Let $K_{0},\dots,K_{r}\in R_{1}$ be linearly independent. Then the map

$\theta:{\mathbb{F}}_{q}^{m+1}\to{\mathbb{F}}_{q}^{r+1}\quad\text{defined
by}\quad\theta(\mathbf{a}):=\left(K_{0}(\mathbf{a}),\dots,K_{r}(\mathbf{a})\right)$

is surjective.

###### Proof.

Extend $\\{K_{0},\dots,K_{r}\\}$ to a ${\mathbb{F}}_{q}$-vector space basis
$\\{K_{0},\dots,K_{m}\\}$ of $R_{1}$. Then the map
$\widehat{\theta}:{\mathbb{F}}_{q}^{m+1}\to{\mathbb{F}}_{q}^{m+1}$ defined by
$\widehat{\theta}(\mathbf{a}):=(K_{0}(\mathbf{a}),\dots,K_{m}(\mathbf{a}))$ is
an ${\mathbb{F}}_{q}$-vector space isomorphism. In particular,
$\widehat{\theta}$ is surjective, and hence so is $\theta$. ∎

The following lemma will prove Theorem 5.1 in the special case when $s=0$.

######  Lemma 5.3.

Assume that $s=0$ so that $d=t(q-1)+1$ with $0\leq t\leq m$. Then

$|\mathcal{M}_{q}(d,m)|=\left(q^{m+1}-1\right){{m}\brack{t}}_{q}.$

###### Proof.

If $t=0=s$, then $\mathsf{PRM}_{q}(d,m)$ is the simplex code of length
$p_{m}$, dimension $m+1$ and minimum distance $q^{m}$. In this case, every
nonzero codeword is a minimum weight codeword and so the desired formula
clearly holds. We now assume that $t\geq 1$. Consider the incidence set
$\mathcal{I}$ and the map $\tau:\mathcal{I}\to\Phi(\mathcal{M})$ defined by

$\mathcal{I}:=\\{(E,H)\in\mathcal{G}_{m-t}({\mathbb{P}}^{m})\times\mathcal{G}_{m-t-1}({\mathbb{P}}^{m}):H\subseteq
E\\}\quad\text{and}\quad\tau(E,H):=E\cap H^{c},$

where by $H^{c}$ we denote the complement of $H$ in
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$, i.e.,
$H^{c}:={\mathbb{P}}^{m}({\mathbb{F}}_{q})\setminus H$. Note that if
$(E,H)\in\mathcal{I}$, then there are linearly independent
$L_{0},\dots,L_{t}\in R_{1}$ such that $E=V(L_{0},\dots,L_{t-1})$ and
$H=V(L_{0},\dots,L_{t})$. Consequently,

$E\cap H^{c}=\mathrm{supp}(c_{F})\quad\text{where}\quad
F:=L_{t}\prod_{i=0}^{t-1}\left(L_{t}^{q-1}-L_{i}^{q-1}\right).$

Thus $\tau$ is well-defined. Moreover, Theorem 4.3 shows that $\tau$ is
surjective. We claim that $\tau$ is also injective. To see this, let
$(E,H),\,(E^{\prime},H^{\prime})\in\mathcal{I}$ be such that
$\tau(E,H)=\tau(E^{\prime},H^{\prime})$. Suppose, if possible, $H\neq
H^{\prime}$. Then there are linearly independent $L_{0},\dots,L_{t}\in R_{1}$
and linearly independent $L^{\prime}_{0},\dots,L^{\prime}_{t}$ in $R_{1}$ such
that $E=V(L_{0},\dots,L_{t-1})$, $H=V(L_{0},\dots,L_{t})$,
$E^{\prime}=V(L^{\prime}_{0},\dots,L^{\prime}_{t-1})$, and
$H^{\prime}=V(L^{\prime}_{0},\dots,L^{\prime}_{t})$. Since $H,H^{\prime}$ have
the same dimension and $H\neq H^{\prime}$, we must have $H\not\subseteq
H^{\prime}$. Hence there is some $j\in\\{0,\dots,t\\}$ such that
$L^{\prime}_{j}$ does not vanish on $H$. This implies that
$L_{0},\dots,L_{t},L_{j}^{\prime}$ are linearly independent. First, suppose
$0\leq j\leq t-1$. By Lemma 5.2, there exists
$\mathbf{a}\in{\mathbb{F}}_{q}^{m+1}$ such that
$L_{0}(\mathbf{a})=\cdots=L_{t-1}(\mathbf{a})=0$ and
$L_{t}(\mathbf{a})=1=L^{\prime}_{j}(\mathbf{a})$. Next, suppose $j=t$. Again,
by Lemma 5.2, there exists $\mathbf{b}\in{\mathbb{F}}_{q}^{m+1}$ such that
$L_{0}(\mathbf{b})=\cdots=L_{t-1}(\mathbf{b})=0$ and $L_{t}(\mathbf{b})=1$,
but $L^{\prime}_{t}(\mathbf{b})=0$. Note that these $\mathbf{a}$ and
$\mathbf{b}$, when they exist, are necessarily nonzero. Thus, in either case,
if $P$ is the point of ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$ corresponding to
$\mathbf{a}$ or $\mathbf{b}$ (according as $0\leq j<t$ or $j=t$), then $P\in
E\cap H^{c}$, but $P\not\in E^{\prime}\cap H^{\prime c}$. But this contradicts
the assumption that $\tau(E,H)=\tau(E^{\prime},H^{\prime})$. So we must have
$H=H^{\prime}$, and therefore $E=E^{\prime}$. Thus we have shown that $\tau$
is bijective. Consequently, in view of (13), we obtain

$|\mathcal{M}_{q}(d,m)|=(q-1)|\mathcal{I}|=(q-1){\genfrac{[}{]}{0.0pt}{}{m+1}{m-t+1}}_{q}{\genfrac{[}{]}{0.0pt}{}{m-t+1}{1}}_{q}=\left(q^{m+1}-1\right){{m}\brack{t}}_{q},$

as desired. ∎

Next, we consider the case when $s\neq 0$. By Theorem 4.3, we know that a
minimum weight codeword of $\mathsf{PRM}_{q}(d,m)$ is of the form $c_{F}$,
where

$F=L_{t}\prod_{i=0}^{t-1}\left(L_{t}^{q-1}-L_{i}^{q-1}\right)\prod_{j=1}^{s}(L_{t+1}-\omega_{j}L_{t})$
(14)

for some linearly independent $L_{0},\dots,L_{t+1}\in R_{1}$ and some distinct
$\omega_{1},\dots,\omega_{s}\in{\mathbb{F}}_{q}$. The support of such a
codeword is given by $V(L_{t})^{c}\cap V(L_{0},\dots,L_{t-1})\cap W$, where

$W=\bigcap_{j=1}^{s}V(L_{t+1}-\omega_{j}L_{t})^{c}=\bigcup_{\mu}V(L_{t+1}-\mu
L_{t}),$

where $\mu$ varies over elements of
${\mathbb{F}}_{q}\setminus\\{\omega_{1},\dots,\omega_{s}\\}$. It is, however,
possible that a different choice $L^{\prime}_{0},\dots,L^{\prime}_{t+1}\in
R_{1}$ could give rise to the same support. In effect, one can replace $L_{t}$
by a linear combination of the form $L_{t}+\sum_{i=0}^{t-1}c_{i}L_{i}$ or one
can even swap it with a factor of the form $(L_{t+1}-\omega_{j}L_{t})$. Thus
one has to be a little more careful while counting the possible supports of
minimum weight codewords. To do it systematically, we consider a set
$\mathcal{J}$ and a map $\Psi$ defined as follows.

Let $\mathcal{P}_{s}({\mathbb{F}}_{q})$ denote the set of all subsets of
${\mathbb{F}}_{q}$ containing $s$ elements, and let

$\mathcal{J}:=\left\\{(E,L_{t},L_{t+1},S)\in\Lambda:E\not\subseteq
V(L_{t})\text{ and }E\cap V(L_{t})\not\subseteq V(L_{t+1})\right\\},$

where $\Lambda:=\mathcal{G}_{m-t}({\mathbb{P}}^{m})\times R_{1}\times
R_{1}\times\mathcal{P}_{s}({\mathbb{F}}_{q})$. Define
$\Psi:\mathcal{J}\longrightarrow\Phi(\mathcal{M})$ by

$\Psi(E,L_{t},L_{t+1},S):=(E\setminus
V(L_{t}))\cap\Big{(}\\!\bigcup_{\mu\in{{\mathbb{F}}_{q}\setminus
S}}\\!V(L_{t+1}-\mu L_{t})\Big{)}\ \text{ for
}(E,L_{t},L_{t+1},S)\in\mathcal{J}.$

Note that if $(E,L_{t},L_{t+1},S)\in\mathcal{J}$, then there are polynomials
$L_{0},\dots,L_{t-1}\in R_{1}$ such that $E=V(L_{0},\dots,L_{t-1})$ and
$L_{0},\dots,L_{t+1}$ are linearly independent, and moreover,
$\Psi(E,L_{t},L_{t+1},S)=\mathrm{supp}(c_{F})$, where $F$ is given by (14).
This shows that $\Psi$ is well-defined. Furthermore, Theorem 4.3 shows that
$\Psi$ is surjective. The next few lemmas will help us analyze the fibres of
$\Psi$.

######  Lemma 5.4.

Let $(E,L_{t},L_{t+1},S)$ and
$(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$ be elements of
$\mathcal{J}$ such that
$\Psi(E,L_{t},L_{t+1},S)=\Psi(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$.
Then $E=E^{\prime}$.

###### Proof.

By our hypothesis, we can find
$L_{0},\dots,L_{t-1},L^{\prime}_{0},\dots,L^{\prime}_{t-1}\in R_{1}$ such that
$E=V(L_{0},\dots,L_{t-1})$,
$E^{\prime}=V(L^{\prime}_{0},\dots,L^{\prime}_{t-1})$, and the subsets
$\\{L_{0},\dots,L_{t+1}\\}$ and $\\{L^{\prime}_{0},\dots,L^{\prime}_{t+1}\\}$
of $R_{1}$ are linearly independent; moreover, if $F$ is given by (14) and
$F^{\prime}$ is given by (14) with $L_{i}$ replaced by $L^{\prime}_{i}$ for
$0\leq i\leq t+1$ and $S$ by $S^{\prime}$, then

$\Psi(E,L_{t},L_{t+1},S)=\mathrm{supp}(c_{F})=\mathrm{supp}(c_{F^{\prime}})=\Psi(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime}).$
(15)

Now suppose, if possible, $E\neq E^{\prime}$. Then one among
$L^{\prime}_{0},\dots,L^{\prime}_{t-1}$, say $L^{\prime}_{0}$, must be such
that $L_{0},\dots,L_{t-1},L^{\prime}_{0}$ are linearly independent. In case
$L_{0},\dots,L_{t+1},L^{\prime}_{0}$ are also linearly independent, then by
Lemma 5.2, we can find $P\in E$ such that $L_{t}(P)\neq 0$ and $L_{t+1}(P)=\mu
L_{t}(P)$ for some $\mu\in{\mathbb{F}}_{q}\setminus S$ and moreover,
$L^{\prime}_{0}(P)\neq 0$. But then
$P\in\mathrm{supp}(c_{F})\setminus\mathrm{supp}(c_{F^{\prime}})$, which
contradicts (15). Thus $L_{0},\dots,L_{t+1},L^{\prime}_{0}$ are linearly
dependent, and so we can find $c_{0},\dots,c_{t+1}\in{\mathbb{F}}_{q}$ such
that

$L^{\prime}_{0}=c_{0}L_{0}+\ldots+c_{t-1}L_{t-1}+c_{t}L_{t}+c_{t+1}L_{t+1}\quad\text{and}\quad
c_{t},c_{t+1}\text{ are not both zero.}$

Now since $|S|=s\leq q-2$, there exist distinct
$\mu_{1},\mu_{2}\in{\mathbb{F}}_{q}\setminus S$. By Lemma 5.2, we can find
$P_{1},P_{2}\in E$ such that $L_{t}(P_{i})\neq 0$ and
$L_{t+1}(P_{i})=\mu_{i}L_{t}(P_{i})$ for $i=1,2$. It follows that
$P_{1},P_{2}\in\mathrm{supp}(c_{F})=\mathrm{supp}(c_{F^{\prime}})$, and hence
$L^{\prime}_{0}(P_{i})=0$ for $i=1,2$. On the other hand,
$L^{\prime}_{0}(P_{i})=(c_{t}+c_{t+1}\mu_{i})L_{t}(P_{i})$ for $i=1,2$. But
then $c_{t}+c_{t+1}\mu_{1}=0=c_{t}+c_{t+1}\mu_{2}$, which implies that
$c_{t+1}=0$ (since $\mu_{1}\neq\mu_{2}$), and hence $c_{t}=0$. Thus we obtain
a contradiction. This proves that $E=E^{\prime}$. ∎

######  Lemma 5.5.

Suppose $(E,L_{t},L_{t+1},S)\in\mathcal{J}$ and
$S^{\prime}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ have the property that
$\Psi(E,L_{t},L_{t+1},S)=\Psi(E,L_{t},L_{t+1},S^{\prime})$. Then
$S=S^{\prime}$.

###### Proof.

Suppose, on the contrary, $S\neq S^{\prime}$. Pick some $\omega\in S$ such
that $\omega\not\in S^{\prime}$. By Lemma 5.2, we can find $P\in E$ such that
$L_{t}(P)\neq 0$ and $L_{t+1}(P)=\omega L_{t}(P)$. Then
$P\in\Psi(E,L_{t},L_{t+1},S^{\prime})$, while
$P\not\in\Psi(E,L_{t},L_{t+1},S)$, which is a contradiction. ∎

######  Lemma 5.6.

Let $(E,L_{t},L_{t+1},S)\in\mathcal{J}$. Then there are exactly $q^{t+1}(q-1)$
elements in $\mathcal{J}$ of the form $(E,L_{t},L^{\prime}_{t+1},S^{\prime})$
such that $\Psi(E,L_{t},L_{t+1},S)=\Psi(E,L_{t},L^{\prime}_{t+1},S^{\prime})$.

###### Proof.

Suppose $L^{\prime}_{t+1}\in R_{1}$ and
$S^{\prime}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ are such that
$\Psi(E,L_{t},L_{t+1},S)=\Psi(E,L_{t},L^{\prime}_{t+1},S^{\prime})$. Choose
$L_{0},\dots,L_{t-1}\in R_{1}$ such that $E=V(L_{0},\dots,L_{t-1})$ and
$\\{L_{0},\dots,L_{t+1}\\}$ as well as
$\\{L_{0},\dots,L_{t},L^{\prime}_{t+1}\\}$ are linearly independent. In case
$\\{L_{0},\dots,L_{t+1},L^{\prime}_{t+1}\\}$ is also linearly independent,
then by Lemma 5.2, we can find $P\in E$ such that $L_{t}(P)\neq 0$,
$L_{t+1}(P)=\mu L_{t}(P)$, and $L^{\prime}_{t+1}(P)=\omega L_{t}(P)$ for some
$\mu\in{\mathbb{F}}_{q}\setminus S$ and $\omega\in S$. But then
$P\in\Psi(E,L_{t},L_{t+1},S^{\prime})\setminus\Psi(E,L_{t},L^{\prime}_{t+1},S^{\prime})$,
which is a contradiction. Thus there are
$c_{0},\dots,c_{t+1}\in{\mathbb{F}}_{q}$ such that

$L^{\prime}_{t+1}=c_{0}L_{0}+\ldots+c_{t-1}L_{t-1}+c_{t}L_{t}+c_{t+1}L_{t+1}.$
(16)

Note that $c_{0},\dots,c_{t+1}$ are uniquely determined by $L^{\prime}_{t+1}$
since $\\{L_{0},\dots,L_{t+1}\\}$ is linearly independent. Moreover,
$c_{t+1}\neq 0$ since $\\{L_{0},\dots,L_{t},L^{\prime}_{t+1}\\}$ is also
linearly independent. On the other hand, if
$c_{0},\dots,c_{t+1}\in{\mathbb{F}}_{q}$ are picked arbitrarily with
$c_{t+1}\neq 0$, and if $L^{\prime}_{t+1}$ is given by (16), then we will show
that there exists unique $S^{\prime}$ in $\mathcal{P}_{s}({\mathbb{F}}_{q})$
such that $\Psi(E,L_{t},L_{t+1},S)=\Psi(E,L_{t},L^{\prime}_{t+1},S^{\prime})$.
To prove the existence, note that for any $\lambda\in{\mathbb{F}}_{q}$,

$L^{\prime}_{t+1}-\lambda L_{t}=c_{t}L_{t}+c_{t+1}L_{t+1}-\lambda
L_{t}=c_{t+1}\left(L_{t+1}-\frac{\lambda-
c_{t}}{c_{t+1}}L_{t}\right)\quad\text{on points of }E.$

Thus if we take $S^{\prime}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ such that
${\mathbb{F}}_{q}\setminus S^{\prime}=\\{\mu
c_{t+1}+c_{t}:\mu\in{\mathbb{F}}_{q}\setminus S\\}$, then

$E\cap\Big{(}\bigcup_{\mu^{\prime}\in{{\mathbb{F}}_{q}\setminus
S^{\prime}}}\\!V(L^{\prime}_{t+1}-\mu^{\prime}L_{t})\Big{)}=E\cap\Big{(}\bigcup_{\mu\in{{\mathbb{F}}_{q}\setminus
S}}\\!V(L_{t+1}-\mu L_{t})\Big{)}.$

This implies that
$\Psi(E,L_{t},L_{t+1},S)=\Psi(E,L_{t},L^{\prime}_{t+1},S^{\prime})$. The
uniqueness of $S^{\prime}$ (for the given choice of $L^{\prime}_{t+1}$) is an
immediate consequence of Lemma 5.5. Since $L^{\prime}_{t+1}$ of the form (16)
can be chosen in exactly $q^{t+1}(q-1)$ ways, the lemma is proved. ∎

######  Lemma 5.7.

Let $(E,L_{t},L_{t+1},S)\in\mathcal{J}$. Then there are exactly
$(s+1)(q-1)^{2}q^{2t+1}$ elements
$(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$ in $\mathcal{J}$
such that
$\Psi(E,L_{t},L_{t+1},S)=\Psi(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$.

###### Proof.

Write $\sigma:=\Psi(E,L_{t},L_{t+1},S)$. Choose $L_{0},\dots,L_{t-1}\in R_{1}$
such that $E=V(L_{0},\dots,L_{t-1})$ and $\\{L_{0},\dots,L_{t+1}\\}$ is
linearly independent. Now if
$(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$ is in
$\Psi^{-1}(\sigma)$, i.e., it is an element of $\mathcal{J}$ such that
$\Psi(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})=\sigma$, then by
Lemma 5.4, $E^{\prime}=E$, and therefore,
$\\{L_{0},\dots,L_{t-1},L^{\prime}_{t},L^{\prime}_{t+1}\\}$ is also linearly
independent. Further, as before, we can use Lemma 5.2 to show that
$\\{L_{0},\dots,L_{t+1},L^{\prime}_{t}\\}$ is linearly dependent. Thus exactly
one of the following two cases are possible.

Case 1. $L^{\prime}_{t}:=b_{0}L_{0}+\dots+b_{t}L_{t}$ for some
$b_{0},\dots,b_{t}\in{\mathbb{F}}_{q}$.

In this case, we must have $b_{t}\neq 0$. Further, given any
$b_{0},\dots,b_{t}\in{\mathbb{F}}_{q}$ with $b_{t}\neq 0$, if we take
$L^{\prime}_{t}:=b_{0}L_{0}+\dots+b_{t}L_{t}$, then we can show that there is
a unique $S^{*}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ for which
$\Psi(E,L_{t},L_{t+1},S)=\Psi(E^{\prime},L^{\prime}_{t},L_{t+1},S^{*})$.
Indeed, the uniqueness of $S^{*}$ is clear from Lemma 5.5, whereas for the
existence, it suffices to observe that for any $\lambda\in{\mathbb{F}}_{q}$,

$L_{t+1}-\lambda L^{\prime}_{t}=L_{t+1}-\lambda b_{t}L_{t}\quad\text{on points
of }E,$

and so we can take $S^{*}=\\{\mu/b_{t}:\mu\in{\mathbb{F}}_{q}\setminus S\\}$.
It follows that there are exactly $q^{t}(q-1)$ choices of
$b_{0},\dots,b_{t}\in{\mathbb{F}}_{q}$ with $b_{t}\neq 0$ and a corresponding
unique choice of $S^{*}$ for which
$L^{\prime}_{t}:=b_{0}L_{0}+\ldots+b_{t}L_{t}$ satisfies
$\Psi(E,L_{t},L_{t+1},S)=\Psi(E^{\prime},L^{\prime}_{t},L_{t+1},S^{*})$.
Furthermore, for any such choice of $L^{\prime}_{t}$ and
$S^{*}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$, by Lemma 5.6, there are exactly
$q^{t+1}(q-1)$ choices of $L^{\prime}_{t+1}$ and corresponding unique choice
of $S^{\prime}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ for which
$\Psi(E^{\prime},L^{\prime}_{t},L_{t+1},S^{*})=\Psi(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$.
It follows that there are exactly $q^{t}(q-1)\times
q^{t+1}(q-1)=q^{2t+1}(q-1)^{2}$ elements
$(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$ in
$\Psi^{-1}(\sigma)$ for which $L^{\prime}_{t}:=b_{0}L_{0}+\ldots+b_{t}L_{t}$
for some $b_{0},\dots,b_{t}\in{\mathbb{F}}_{q}$ with $b_{t}\neq 0$.

Case 2. $L^{\prime}_{t}=b_{0}L_{0}+\dots+b_{t+1}L_{t+1}$ for some
$b_{0},\dots,b_{t+1}\in{\mathbb{F}}_{q}$ with $b_{t+1}\neq 0$.

In this case, we claim that $-b_{t}/b_{t+1}\in S$. To prove this, assume the
contrary. Use Lemma 5.2 to choose $P\in E$ such that $L_{t}(P)\neq 0$ and
$L_{t+1}(P)=\left(-b_{t}/b_{t+1}\right)L_{t}(P)$. Then $P\in\sigma$, since
$-b_{t}/b_{t+1}\not\in S$. On the other hand, our choice of $P$ implies that

$L^{\prime}_{t}(P)=b_{t}L_{t}(P)+b_{t+1}L_{t+1}(P)=0$

and therefore
$P\not\in\Psi(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})=\sigma$,
which is a contradiction. Thus the claim is proved. We shall now show that for
any fixed choice of $b_{0},\dots,b_{t+1}\in{\mathbb{F}}_{q}$ with $b_{t+1}\neq
0$ and $-b_{t}/b_{t+1}\in S$, if we take
$L^{\prime}_{t}=b_{0}L_{0}+\dots+b_{t+1}L_{t+1}$, and $L^{*}_{t+1}:=L_{t}$,
then there is a unique $S^{*}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ such that
$(E,L^{\prime}_{t},L^{*}_{t+1},S^{*})\in\mathcal{J}$ and
$\Psi(E,L^{\prime}_{t},L^{*}_{t+1},S^{*})=\sigma$. To see this, first note
that $\\{L_{0},\dots,L_{t-1},L^{\prime}_{t},L^{*}_{t+1}\\}$ is linearly
independent. Further, if we take $S^{*}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$
such that

${\mathbb{F}}_{q}\setminus S^{*}=\left\\{\frac{1}{b_{t}+\mu
b_{t+1}}:\mu\in{\mathbb{F}}_{q}\setminus S\right\\}.$

then $S^{*}$ is well-defined since $-b_{t}/b_{t+1}\in S$. Moreover, if for any
$\mu^{*}\in{\mathbb{F}}_{q}\setminus S^{*}$, we write $\mu^{*}=1/(b_{t}+\mu
b_{t+1})$ for some $\mu\in{\mathbb{F}}_{q}\setminus S$, then on points of $E$,
we have

$L^{*}_{t+1}-\mu^{*}L^{\prime}_{t}=L_{t}-\frac{1}{b_{t}+\mu
b_{t+1}}(b_{t}L_{t}+b_{t+1}L_{t+1})=\frac{-b_{t+1}}{b_{t}+\mu
b_{t+1}}\left(L_{t+1}-\mu L_{t}\right).$

Consequently,

$(E\setminus
V(L^{\prime}_{t}))\cap\Big{(}\\!\bigcup_{\mu^{*}\in{{\mathbb{F}}_{q}\setminus
S^{*}}}\\!V(L^{*}_{t+1}-\mu^{*}L^{\prime}_{t})\Big{)}=(E\setminus
V(L_{t}))\cap\Big{(}\\!\bigcup_{\mu\in{{\mathbb{F}}_{q}\setminus
S}}\\!V(L_{t+1}-\mu L_{t})\Big{)}=\sigma.$

This shows the existence of a polynomial $L^{*}_{t+1}\in R_{1}$ and a set
$S^{*}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ such that
$(E,L^{\prime}_{t},L^{*}_{t+1},S^{*})\in\mathcal{J}$ and
$\Psi(E,L^{\prime}_{t},L^{*}_{t+1},S^{*})=\sigma$. The uniqueness of $S^{*}$
for the given choice of $L^{*}_{t+1}$ is clear from Lemma 5.5. Moreover, by
Lemma 5.6, there are exactly $q^{t+1}(q-1)$ choices of $L^{\prime}_{t+1}$ and
corresponding unique choice of
$S^{\prime}\in\mathcal{P}_{s}({\mathbb{F}}_{q})$ for which
$\Psi(E^{\prime},L^{\prime}_{t},L^{*}_{t+1},S^{*})=\Psi(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$.
Since $b_{0},\dots,b_{t+1}\in{\mathbb{F}}_{q}$ such that $b_{t+1}\neq 0$ and
$-b_{t}/b_{t+1}\in S$ can be chosen in $s(q-1)q^{t}$ ways, we see that there
are exactly $q^{t+1}(q-1)\times s(q-1)q^{t}=sq^{2t+1}(q-1)^{2}$ elements
$(E^{\prime},L^{\prime}_{t},L^{\prime}_{t+1},S^{\prime})$ in
$\Psi^{-1}(\sigma)$ for which $L^{\prime}_{t}$ is as in Case 2.

By combining the counts in Case 1 and Case 2, we obtain the desired result. ∎

We are now ready to prove the main result of this section.

_Proof of Theorem 5.1._ If $s=0$, then the desired formula (12) follows from
Lemma 5.3. If $s\neq 0$, then by Lemma 5.7,

$|\Psi^{-1}(\sigma)|=(s+1)(q-1)^{2}q^{2t+1}\quad\text{for all
}\sigma\in\Phi(\mathcal{M}).$ (17)

It follows that

$\displaystyle|\Phi(\mathcal{M})|$
$\displaystyle=\frac{|\mathcal{J}|}{(s+1)(q-1)^{2}q^{2t+1}}$
$\displaystyle=\frac{1}{(s+1)(q-1)^{2}q^{2t+1}}{{m+1}\brack{m-t+1}}_{q}\left(q^{m+1}-q^{t}\right)\left(q^{m+1}-q^{t+1}\right){q\choose
s}$
$\displaystyle=\frac{1}{s+1}{{m+1}\brack{t}}_{q}{{m-t+1}\brack{1}}_{q}{{m-t}\brack{1}}_{q}{q\choose
s}$
$\displaystyle=\frac{\left(q^{m+1}-1\right)}{(s+1)(q-1)}{{m}\brack{t}}_{q}{\genfrac{[}{]}{0.0pt}{}{m-t}{1}}_{q}{q\choose
s}.$

By combining this with (13), we obtain the desired formula. $\Box$

######  Remark 5.8.

The formula (12) for the number of minimum weight codewords of the projective
Reed-Muller code $\mathsf{PRM}_{q}(d,m)$ is evidently a positive integer when
$s=0$. In case $s\neq 0$, we can easily rewrite (12) as

$\frac{\left(q^{m+1}-1\right)(q^{m}-1)}{(q+1)(q-1)}{{m-1}\brack{t}}_{q}{{q+1}\choose{s+1}},$

and this readily shows that it is a positive integer. In the special case when
$t=m-1$ and $s=q-k$, where $2\leq k\leq q-1$, the formula reduces to

$\frac{(q-1)}{(q+1)}p_{m}p_{m-1}{{q+1}\choose{k}}.$

It may be interesting to note that this is precisely equal to $(q-1)$ times
the number of collections of $k$ collinear points in
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. For geometric interpretations such as
this, and more, we refer to Kaplan and Matei [15], especially §3.3 of their
paper.

##  6\. Dimension Formulas for Projective Reed-Muller Codes

Fix throughout this section $m,d\in\mathbb{Z}$ such that $m\geq 1$ and $1\leq
d\leq m(q-1)+1$. As before, let $\,t,s$ be unique integers such that
$d-1=t(q-1)+s$ with $t\geq 0$ and $0\leq s<q-1$. An explicit formula for the
dimension of a PRM code of an arbitrary order $d$ was first given by Sørensen
[27]. It is as follows.

$\displaystyle\displaystyle{\alpha_{q}(d,m):=\sum_{\begin{subarray}{c}e=1\\\
e\equiv d\ (\mathrm{mod}\
q-1)\end{subarray}}^{d}\left(\sum_{j=0}^{m+1}(-1)^{j}\binom{m+1}{j}\binom{e-jq+m}{e-jq}\right).}$
(18)

Later Mercier-Rolland [20] gave another formula for the dimension of PRM codes
of order $d$ using the dimension of vanishing ideal of
${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. This one is as follows.

$\displaystyle\beta_{q}(d,m):=\binom{m+d}{d}-\sum_{j=2}^{m+1}(-1)^{j}{{m+1}\choose{j}}\sum_{i=0}^{j-2}{{d+(i+1)(q-1)-jq+m}\choose{d+(i+1)(q-1)-jq}}.$
(19)

Around the same time444A comment on the dates of publication of [20] and [24]
can be found in [11, Remark 3.4]., Rentería and Tapia-Recillas [24, Prop. 12]
gave the following nice formula for the dimension of $\mathsf{PRM}_{q}(d,m)$:

$\gamma_{q}(d,m):=\sum_{i=0}^{m}\sum_{j=0}^{i}(-1)^{j}\binom{i}{j}\binom{i+d-1-jq}{i}.$
(20)

More recently, Can, Joshua and Ravindra [8, Prop. 3.5] have proposed another
formula for the dimension of PRM codes of order $d$, which is as follows.

$\displaystyle\displaystyle{\delta_{q}(d,m):=\sum_{\begin{subarray}{c}e=1\\\
e\equiv d\ (\mathrm{mod}\ q-1)\end{subarray}}^{d}\left(\sum_{j=0}^{\lfloor
e/q\rfloor}(-1)^{j}\binom{m+1}{j}\binom{e-jq+m}{m}\right).}$ (21)

Can, Joshua and Ravindra [8] further alleged that the formula of Sørensen [27]
is wrong and wrote that the expression on the right in (18) is equal to $0$.
This is, in fact, not correct. To clear the confusion, let us first note that
the binomial coefficients are (and always should be!) defined as in the
beginning of Section 2. In particular, ${a\choose b}$ is zero when $b<0$. In
fact, if $a,b\in\mathbb{Z}$, then

${a\choose b}=0\Longleftrightarrow\text{either }b<0\text{ or }b>a\geq 0.$ (22)

Furthermore, the identity ${a\choose b}={a\choose{a-b}}$ is not absolute, but
conditional. In the first place it requires that $a\in\mathbb{Z}$ and in fact,
for any $a,b\in\mathbb{Z}$

${a\choose b}={a\choose{a-b}}\Longleftrightarrow\text{either }a\geq 0\text{ or
}a<b<0.$ (23)

We remark in passing that on the other hand, the Pascal triangle identity,
viz.,

${a\choose{b-1}}+{a\choose{b}}={{a+1}\choose{b}}$ (24)

is an absolute identity in the sense that it is valid for all $b\in\mathbb{Z}$
and all $a$ in any integral domain containing $\mathbb{Z}$ as a subring. At
any rate, in view of (22), the summation over $j$ in (18) is, in effect, over
$0\leq j\leq\min\\{m+1,\lfloor e/q\rfloor\\}=\lfloor e/q\rfloor$ for any
positive integer $e\leq d$, where the last equality follows since $e\leq d\leq
m(q-1)+1\leq mq$. Moreover, for $0\leq j\leq\lfloor e/q\rfloor$, by (23), we
obtain $\binom{e-jq+m}{e-jq}=\binom{e-jq+m}{m}$. Thus it is clear that
$\alpha_{q}(d,m)=\delta_{q}(d,m)$. In other words, the formulas of Sørensen
and of Can, Joshua and Ravindra are, in fact, the same! The argument in
Section 3 of [8] to conclude that $\alpha_{q}(d,m)=0$ uses their Lemma 3.3,
which is perfectly fine, but then it uses the “identity”
$\binom{e-jq+m}{e-jq}=\binom{e-jq+m}{m}$ for arbitrary nonnegative integer
$j$, which as we have noted in (23), is not always true. [There is also a typo
in the definition given in [8, p. 6] of the polynomial $P(x)$; namely, $t$
should be replaced throughout by $t+m$ in the expression on the right, but
this is minor].

The equivalence of (18) and (19) is rather nontrivial. As mentioned in [20], a
direct proof of this was given by Michel Quercia, but to the best of our
knowledge, this has not been published. The argument of Michel Quercia was
made available to us by Robert Rolland, and we have reproduced it in the
appendix to this paper. We give below an alternative argument to prove the
equivalence of these formulas. This alternative argument uses the following
simple combinatorial lemma, which has been given, for instance, by Sørensen
[27].

######  Lemma 6.1.

Let $n,a,b$ be any nonnegative integers and let $N(a,n,b)$ denote the number
of ways in which one can place $a$ objects in $n$ blocks such that no block
contains more than $b$ objects. Then

$N(a,n,b)=\sum_{j=0}^{n}(-1)^{j}{{n}\choose{j}}{{a-j(b+1)+n-1}\choose{a-j(b+1)}}.$
(25)

###### Proof.

See [27, Lem. 5]. Or use an argument as in the proof of [12, Lem. 1]. ∎

######  Remark 6.2.

Given any nonnegative integers $n,a,b$, it is clear from the description of
$N(a,n,b)$ that it is the number of monomials in $n$ variables of degree $a$
such that the degree in each variable is at most $b$. In particular, if
$0\leq\nu\leq n(q-1)$, then $N(\nu,n,q-1)$ is the number of reduced monomials
of degree $\nu$ in $n$ variables, and so we see that
$N(\nu,n,q-1)=\rho_{q}(\nu,n)-\rho_{q}(\nu-1,n)$, where $\rho_{q}(\nu,n)$ is
given by (1) if $n\geq 1$ and where by convention, $\rho_{q}(0,0):=1$ and
$\rho_{q}(k,n):=0$ if $k\in\mathbb{Z}$ with $k<0$. This can also be seen
directly by comparing (1) with the formula in Lemma 6.1 and using the Pascal
triangle identity (24). Note also that the degree of a reduced monomial in $n$
variables is always $\leq n(q-1)$ and so

$\rho_{q}(\nu,n)=\rho_{q}\left(\min\\{\nu,\,n(q-1)\\},\;n\right)\quad\text{for
any nonnegative integers }\nu,\,n.$ (26)

This is clear from the description of $\rho_{q}(\nu,n)$ as the number of
reduced monomials in $n$ variables of degree $\leq\nu$, and also from the
formula (1) because if $\nu>n(q-1)$, then using (1), (25), and successive
applications of (24), we see that

$\rho_{q}(\nu,n)=\rho_{q}(n(q-1),\,n)+\sum_{a=n(q-1)+1}^{\nu}N(a,\,n,\,q-1)\;=\;\rho_{q}(n(q-1),\,n),$

where the last equality follows since any distribution of $n(q-1)+1$ or more
objects in $n$ blocks will result in at least one block containing $q$ or more
objects.

We are now ready to prove that the two dimension formulas $\alpha_{q}(d,m)$
and $\beta_{q}(d,m)$ given by (18) and (19) are equal.

######  Proposition 6.3.

$\alpha_{q}(d,m)=\beta_{q}(d,m)$.

###### Proof.

First note that we may rewrite (19) as

$\displaystyle\beta_{q}(d,m)=\binom{m+d}{d}-\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}\sum_{\begin{subarray}{c}e=d+(q-1)\\\
e\equiv d\ (\mathrm{mod}\
q-1)\end{subarray}}^{d+(j-1)(q-1)}{{e-jq+m}\choose{e-jq}}.$

Also note that by separating terms in (18) corresponding to $e=d$ and $j=0$ as
well as $e=d$ and $j\geq 1$, we can write

$\displaystyle\alpha_{q}(d,m)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}1\leq e<d\\\ e\equiv d\ (\mathrm{mod}\
q-1)\end{subarray}}\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}{{e-jq+m}\choose{e-jq}}$
$\displaystyle\qquad+\binom{m+d}{d}+\;\sum_{j=1}^{m+1}(-1)^{j}{{m+1}\choose{j}}{{d-jq+m}\choose{d-jq}}$

Thus $\alpha_{q}(d,m)=\beta_{q}(d,m)$ is equivalent to the equality

$\displaystyle\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}\sum_{\begin{subarray}{c}e=1\\\
e\equiv d\ (\mathrm{mod}\
q-1)\end{subarray}}^{d+(j-1)(q-1)}{{e-jq+m}\choose{e-jq}}=0,$ (27)

Define

$\displaystyle
c:=\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}\sum_{\begin{subarray}{c}e\equiv
d\ (\mathrm{mod}\ q-1)\\\ -\infty<e\leq
d+(j-1)(q-1)\end{subarray}}{{e-jq+m}\choose{e-jq}}.$

Then the expression on the left in (27) is equal to $c-1$ if $d$ is a multiple
of $q-1$, and is equal to $c$ otherwise. Thus it is enough to show that $c=1$
if $d$ is a multiple of $q-1$ and $c=0$ if $d$ is not a multiple of $q-1$. Now

$\displaystyle c$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{m+1}\sum_{k=0}^{\infty}(-1)^{j}{{m+1}\choose{j}}{{d+(j-1)(q-1)-k(q-1)-jq+m}\choose{d+(j-1)(q-1)-k(q-1)-jq}}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}{{d+(j-1)(q-1)-k(q-1)-jq+m}\choose{d+(j-1)(q-1)-k(q-1)-jq}}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}{{d-(k+1)(q-1)-j+m}\choose{d-(k+1)(q-1)-j}}$
$\displaystyle=$ $\displaystyle\sum_{k=0}^{\infty}N(d-(k+1)(q-1),\;m+1,\;0)$

where the last equality uses Lemma 6.1 and the notation therein. But
evidently,

$\displaystyle N(d-(k+1)(q-1),\;m+1,\;0)=\begin{cases}1&\text{if
}d=(k+1)(q-1),\\\ 0&\text{if }d\neq(k+1)(q-1).\end{cases}$

This implies that $c=1$ if $d$ is a multiple of $q-1$, and $0$ otherwise. ∎

We will now consider the formula $\gamma_{q}(d,m)$ of Rentería and Tapia-
Recillas [24, Prop. 12]. They proved it using an ideal-theoretic approach and
the notion of Hilbert functions. (See also [9, Cor. 3.9 (b)], where Carvalho,
Neumann, and Lopez derive the same formula from a more general result on
projective nested cartesian codes.) Moreover, [24, Lem. 9] implies that
$\gamma_{q}(d,m)$ can be related to the dimensions of certain Reed-Muller
codes. We show below that the notion of projective reduction can also be used
to give a short direct proof of the formula of Rentería and Tapia-Recillas for
the dimension of $\mathsf{PRM}_{q}(d,m)$.

Recall that we had defined the Reed-Muller code $\mathrm{RM}_{q}(\nu,m)$ for
any $\nu\in\mathbb{Z}$ with $0\leq\nu\leq m(q-1)$. We shall find it convenient
to extend this definition a bit so as to set $\mathrm{RM}_{q}(0,0)$ to be the
$1$-dimensional code of length $1$, namely, ${\mathbb{F}}_{q}$. This is
consistent with the formula (1) given earlier, namely,

$\rho_{q}(\nu,m):=\dim\mathrm{RM}_{q}(\nu,m)=\sum_{j=0}^{m}(-1)^{j}\binom{m}{j}\binom{m+\nu-
jq}{m}$

and also with convention $\rho_{q}(0,0):=1$, which was stated earlier.

######  Theorem 6.4.

The dimension of the code $\mathsf{PRM}_{q}(d,m)$ is given by

$\sum_{i=0}^{m}\rho_{q}(d-1,\,i)=\sum_{i=0}^{m}\sum_{j=0}^{i}(-1)^{j}\binom{i}{j}\binom{i+d-1-jq}{i}=\gamma_{q}(d,m).$
(28)

###### Proof.

Let $E$ be the set of all $(m+1)$-tuples of nonnegative integers whose sum is
equal to $d$. For $\mathbf{a}=(a_{0},\ldots,a_{m})\in E$, let
$\ell(\mathbf{a}):=\max\\{j\in\\{0,1,\dots,m\\}:a_{j}>0\\}$. Note that this is
well-defined since $d\geq 1$. Define

$B:=\\{\mathbf{a}=(a_{0},\ldots,a_{m})\in E:a_{j}<q\text{ for }0\leq
j<\ell(\mathbf{a})\\}.$

It is clear from Lemma 2.1 that $\dim\mathsf{PRM}_{q}(d,m)=|B|$. Now observe
that

$B=\coprod_{i=0}^{m}B_{i}\quad\text{where for }0\leq i\leq m,\quad
B_{i}:=\\{\mathbf{a}\in B:\ell(\mathbf{a})=i\\}.$

For $i\in\\{0,1,\dots,m\\}$, the map $\mathbf{a}\mapsto(a_{0},\dots,a_{i-1})$
is readily seen to be a bijection of $B_{i}$ onto the set of exponent vectors
of reduced monomials in $i$ variables of degree $\leq d-1$; consequently,
$|B_{i}|=\rho_{q}(d-1,\,i)$. This yields the desired formula. ∎

Finally, we give a direct proof of the equivalence of the dimension formulas
of Sørensen and Rentería–Tapia-Recillas.

######  Proposition 6.5.

$\alpha_{q}(d,m)=\gamma_{q}(d,m)$.

###### Proof.

First, note that (18) can be written in the notation of Lemma 6.1 as

$\alpha_{q}(d,m)=\\!\sum_{\begin{subarray}{c}e=1\\\ e\equiv d\ (\mathrm{mod}\
q-1)\end{subarray}}^{d}\\!N(e,m+1,q-1).$ (29)

Fix any $e\in\\{1,\dots,d\\}$. Then $N(e,m+1,q-1)$ is the number of reduced
monomials of degree $e$ in $m+1$ variables $x_{0},\dots,x_{m}$. Given such a
reduced monomial, if $x_{i}$ is the last variable appearing in it, then it
must be of the form $\mu\,x_{i}^{j_{i}}$, where $1\leq j_{i}\leq q-1$ and
$\mu$ is a reduced monomial in $x_{0},\dots,x_{i-1}$ of degree $e-j_{i}$. Note
that the degree $e-j_{i}$ of $\mu$ satisfies $e-q+1\leq e-j_{i}\leq e-1$.
Conversely, any reduced monomial in $x_{0},\dots,x_{i-1}$ of degree $a$, where
$e-q+1\leq a\leq e-1$, would give rise (upon multiplication by $x_{i}^{e-a}$)
to a unique reduced monomial of degree $e$ in $x_{0},\dots,x_{i}$ with a
positive exponent for $x_{i}$. Thus partitioning reduced monomials of degree
$e$ in $x_{0},\dots,x_{m}$ by the last variable appearing in them, we see that

$N(e,m+1,q-1)=\sum_{i=0}^{m}\big{(}\rho_{q}(e-1,\,i)-\rho_{q}(e-q,\,i)\big{)}.$

On the other hand, since $d=t(q-1)+s+1$ with $0\leq t\leq m$ and $0\leq
s<q-1$, the parameter $e$ in the summation in (29) takes values of the form
$r(q-1)+s+1$, where $r$ ranges from $0$ to $t$. Thus, we see that

$\alpha_{q}(d,m)=\sum_{r=0}^{t}N(r(q-1)+s+1,\,m+1,\,q-1)=\sum_{r=0}^{t}\sum_{i=0}^{m}\big{(}A(r,i)-A(r-1,i)\big{)},$

where $A(k,i):=\rho_{q}(k(q-1)+s,\,i)$ for $-1\leq k\leq t$ and $0\leq i\leq
m$. Now, by interchanging the summations over $i$ and $r$, and then observing
that the inner sum is telescoping, and moreover, $A(-1,i)=0$, we obtain

$\alpha_{q}(d,m)=\sum_{i=0}^{m}A(t,i)=\sum_{i=0}^{m}\rho_{q}(d-1,\,i).$

This proves that $\alpha_{q}(d,m)=\gamma_{q}(d,m)$. ∎

## Acknowledgements

We are grateful to Robert Rolland and Michel Quercia for sharing with us a
direct proof of the equivalence of formulas (18) and (19), and we thank M.
Quercia for permitting us to reproduce his proof in the appendix below. We
also thank Nathan Kaplan for his interest in this work and for bringing [15]
and the geometric interpretation mentioned in Remark 5.8 to our attention.
Thanks are also due to Hiram Lopez and the reviewers of a preliminary version
of this article for some useful remarks and pointers to relevant literature.

## Appendix: Quercia’s Proof of Equivalence of Dimension Formulas

Here we reproduce Michel Quercia’s original proof of the equivalence of the
formulas, due to Sørensen and Mercier-Rolland, for the dimension of projective
Reed-Muller codes. We use notations consistent with this article.

######  Proposition 6.6 (Quercia).

Let $q$ be a prime power and let $d,m$ be positive integers such that $d\leq
m(q-1)+1$. Also, let $\alpha_{q}(d,m)$ and $\beta_{q}(d,m)$ be given by (18)
and (19), respectively. Then $\alpha_{q}(d,m)=\beta_{q}(d,m)$.

###### Proof.

As in the proof of Proposition 6.3, the assertion
$\alpha_{q}(d,m)=\beta_{q}(d,m)$ is equivalent to the equality

$\displaystyle\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}\sum_{\begin{subarray}{c}e\equiv
d\ (\mathrm{mod}\ q-1)\\\ 0<e\leq
d+(j-1)(q-1)\end{subarray}}{{e-jq+m}\choose{e-jq}}=0.$ (30)

Define

$\displaystyle
c:=\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}\sum_{\begin{subarray}{c}e\equiv
d\ (\mathrm{mod}\ q-1)\\\ -\infty<e\leq
d+(j-1)(q-1)\end{subarray}}{{e-jq+m}\choose{e-jq}}.$ (31)

Observe that the expression on the left in (30) is equal to $c-1$ if $d$ is a
multiple of $q-1$, and is equal to $c$ otherwise. Thus it is enough to show
that $c=1$ if $d$ is a multiple of $q-1$ and $c=0$ if $d$ is not a multiple of
$q-1$. We use a functional approach to prove this.

Let $\mathcal{E}$ be the $\mathbb{Z}$-module of the sequences
$u=(u_{n})_{n\in\mathbb{Z}}$ which take integer values and vanish in the
vicinity of $-\infty$ (i.e., for each
$u=(u_{n})_{n\in\mathbb{Z}}\in\mathcal{E}$, there is $n_{0}\in\mathbb{Z}$ such
that $u_{n}=0$ for all $n\in\mathbb{Z}$ with $n<n_{0}$). Denote by $I$ the
identity mapping of $\mathcal{E}$ and $T$ the transfer operator defined by

$(Tu)_{n}=u_{n+1}\quad\text{for }n\in\mathbb{Z}.$

The sequence $u^{(m)}$, defined by

$(u^{(m)})_{n}=\binom{n+m}{n}\quad\text{for }n\in\mathbb{Z},$

belongs to $\mathcal{E}$ and the number $c$ as defined in (31) is the term
with index $0$ of the sequence $x=Lu^{(m)}$ where

$L=\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}\sum_{\begin{subarray}{c}e\equiv
d\ (\mathrm{mod}\ q-1)\\\ -\infty<e\leq d+(j-1)(q-1)\end{subarray}}T^{e-jq}.$

Note that the above series has a value as an $\mathcal{E}$-endomorphism.
Define

$\Delta:=\sum_{k\leq 0}T^{k(q-1)}=(I-T^{-q+1})^{-1}.$

Then

$\displaystyle L$
$\displaystyle=\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}T^{d+(j-1)(q-1)-jq}\Delta$
$\displaystyle=\sum_{j=0}^{m+1}(-1)^{j}{{m+1}\choose{j}}T^{d-j-q+1}\Delta$
$\displaystyle=T^{d-q+1}\Delta(I-T^{-1})^{m+1}$

On the other hand, $(I-T^{-1})u^{(m)}=u^{(m-1)}$. This implies that

$\displaystyle(I-T^{-1})^{m+1}u^{(m)}=u^{(-1)},$

where $u^{(-1)}$ is the sequence belonging to $\mathcal{E}$ defined by

$(u^{(-1)})_{0}=1\quad\text{and}\quad(u^{(-1)})_{n}=0\text{ if
$n\in\mathbb{Z}$ with }n\neq 0.$

Thus $x=Lu^{(m)}=T^{d-q+1}\Delta u^{(-1)}$ is given by

$x_{n}=\begin{cases}1&\text{if }n\equiv-d(\text{mod }q-1)\text{ and }n>-d,\\\
0&\text{otherwise}.\end{cases}$

Considering $x_{0}$, we obtain the desired result. ∎

## References

  * [1] E. F. Assmus Jr. and J. D. Key, _Designs and their Codes_ , Cambridge Tracts in Math., 103, Cambridge Univ. Press, 1992.
  * [2] S. Ballet and R. Rolland, On low weight codewords of generalized affine and projective Reed-Muller codes, _Des. Codes Cryptogr._ 73 (2014), 271–297.
  * [3] P. Beelen and M. Datta, Generalized Hamming weights of affine Cartesian codes, _Finite Fields Appl._ 51 (2018), 130–145.
  * [4] P. Beelen, M. Datta and S. R. Ghorpade, Vanishing ideals of projective spaces over finite fields and a projective footprint bound, _Acta Math. Sin. (Engl. Ser.)_ 35 (2019), 47–63.
  * [5] P. Beelen, M. Datta and S. R. Ghorpade, A combinatorial approach to the number of solutions of systems of homogeneous polynomial equations over finite fields, _Moscow Math J._ 22 (2022), 565–593.
  * [6] T. Berger, Automorphism groups of homogeneous and projective Reed-Muller codes, _IEEE Trans. Inform. Theory_ 48 (2002), 1035–1045.
  * [7] T. Berger and P. Charpin, The automorphism group of generalized Reed-Muller codes, _Discrete Math._ 117 (1993), 1–17.
  * [8] M. B. Can, R. Joshua and G. V. Ravindra, Higher Grassmann codes II, _Finite Fields Appl._ 89 (2023), Art. 102211, 21 pp.
  * [9] C. Carvalho, V. G. L. Neumann and H. H. Lopez, Projective nested cartesian codes, _Bull. Braz. Math. Soc._ 48 (2017), 283–302.
  * [10] P. Delsarte, J. M. Goethals and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives, _Information and Control_ 16 (1970), 403–442.
  * [11] S. R. Ghorpade, A note on Nullstellensatz over finite fields, in: _Contributions in Algebra and Algebraic Geometry_ (Aurangabad, 2017), _Contemp. Math._ , 738, Amer. Math. Soc., Providence, 2019, pp. 23–32.
  * [12] S. R. Ghorpade and R. Ludhani, On the purity of resolutions of Stanley-Reisner rings associated to Reed-Muller codes, in: _Algebra and Related Topics with Applications_ (Aligarh, 2019), _Springer Proc. Math. Stat._ 392, Springer, Singapore, 2022, pp. 325–335.
  * [13] S. R. Ghorpade, C. Ritzenthaler, F. Rodier and M. A. Tsfasman, Arithmetic, geometry, and coding theory: Homage to Gilles Lachaud, _Contemp. Math._ , 770, Amer. Math. Soc., Providence, 2021, 131–150.
  * [14] P. Heijnen and R. Pellikaan, Generalized Hamming weights of $q$-ary Reed-Muller codes, _IEEE Trans. Inform. Theory_ 44 (1998), 181–196.
  * [15] N. Kaplan and V. Matei, Counting plane cubic curves over finite fields with a prescribed number of rational intersection points, _Eur. J. Math._ 7 (2021), 1137–1181.
  * [16] T. Kasami, S. Lin and W. W. Peterson, New generalization of the Reed-Muller codes–Part I: Primitive Codes, _IEEE Trans. Inform. Theory_ IT-14 (1968), 189–199.
  * [17] G. Lachaud, Projective Reed-Muller codes, in: _Coding Theory and Applications_ (Cachan, 1986), Lecture Notes in Comput. Sci., 311, Springer, Berlin, 1988, pp. 125–129.
  * [18] G. Lachaud, The parameters of projective Reed-Muller codes, _Discrete Math._ 81 (1990), 217–221.
  * [19] E. Leducq, A new proof of Delsarte, Goethals and MacWilliams theorem on minimal weight codewords of generalized Reed-Muller codes, _Finite Fields Appl._ 18 (2012), 581–586.
  * [20] D. J. Mercier and R. Rolland, Polynômes homogènes qui s′annulent sur l′espace projectif ${\mathbb{P}}^{m}({\mathbb{F}}_{q})$. _J. Pure Appl. Algebra_ 124 (1998), 227–240.
  * [21] D. E. Muller, Application of Boolean algebra to switching circuit design and to error detection, _IRE Trans. Electron. Comput._ EC-3 (1954), 6–12.
  * [22] I. S. Reed, A class of multiple-error-correcting codes and the decoding scheme, _IRE Trans. Inform. Theory_ 4 (1954), 38–49.
  * [23] I. S. Reed, A brief history of the development of error correcting codes, _Comput. Math. Appl._ 39 (2000), 89–93.
  * [24] C. Rentería and H. Tapia-Recillas, Reed-muller codes: an ideal theory approach, _Comm. Algebra_ 25 (1997), 401–413.
  * [25] R. Rolland, Number of points of non-absolutely irreducible hypersurfaces, in: _Algebraic Geometry and its Applications_ (Papette, 2007), _Ser. Number Theory Appl._ 5, World Scientific, Singapore, 2008, pp. 481–487.
  * [26] J.-P. Serre, Lettre á M. Tsfasman, _Journées Arithmétiques (Luminy,1989)_ , Astérisque No. 198-199-200 (1991), 351–353.
  * [27] A. B. Sørensen, Projective Reed-Muller codes, _IEEE Trans. Inform. Theory_ 37 (1991), 1567–1576.
  * [28] S. G. Vlèduts and Yu. I. Manin, Linear codes and modular curves, _J. Sov. Math._ 30 (1985), 2611–2643.