equ[][]

# Hulls of Projective Reed-Muller Codes

Nathan Kaplan
Department of Mathematics
University of California, Irvine, USA
<EMAIL_ADDRESS>

Jon-Lark Kim
Department of Mathematics
Sogang University, Seoul, Korea
<EMAIL_ADDRESS>

###### Abstract

Projective Reed-Muller codes are constructed from the family of projective
hypersurfaces of a fixed degree over a finite field $\mathbb{F}_{q}$. We
consider the relationship between projective Reed-Muller codes and their
duals. We determine when these codes are self-dual, when they are self-
orthogonal, and when they are LCD. We then show that when $q$ is sufficiently
large, the dimension of the hull of a projective Reed-Muller code is 1 less
than the dimension of the code. We determine the dimension of the hull for a
wider range of parameters and describe how this leads to a new proof of a
recent result of Ruano and San José (2024).

Keywords: Projective Reed-Muller codes; Evaluation codes; Hull of a linear
code.

MSC Classification: 11T71; 94B60; 11T06.

##  1 Introduction

Affine Reed-Muller codes are the multivariate analogues of Reed-Solomon codes.
Codewords come from evaluating polynomials in $n$ variables at the points of
$\mathbb{F}_{q}^{n}$, or equivalently, they correspond to affine
hypersurfaces. There is an extensive literature studying these codes,
including foundational results of Delsarte, Goethals, and MacWilliams [6],
Kasami, Lin, and Peterson [17], and many others.

This paper deals with projective analogues of these codes, the projective
Reed-Muller codes, where codewords correspond to hypersurfaces of a fixed
degree $k$ in $\mathbb{P}^{n}$ defined over $\mathbb{F}_{q}$. These codes also
have an extensive history going back to early work of Lachaud who studied
codes from hyperplanes and codes from quadric hypersurfaces in [18], and
determined the parameters of these codes in the case where $k<q$ in [19].
Sørensen determined the parameters of these codes in general, described the
dual of a projective Reed-Muller code, and studied when these codes are cyclic
[28]. Berger analyzes the automorphism groups of these codes in [4]. More
recently, there has been extensive interest in determining the generalized
Hamming weights of these codes, and in determining Hamming weight enumerators
of these codes in certain cases; see for example [2, 3, 8, 16].

The main focus of this paper is on studying the hulls of projective Reed-
Muller codes. The _hull of a linear code_ $C$ is defined by
$\operatorname{Hull}(C)=C\cap C^{\perp}$. Three particular cases of interest
are when $C$ is _self-dual_ , which means
$C=C^{\perp}=\operatorname{Hull}(C)$, when $C$ is _self-orthogonal_ , which
means $C=\operatorname{Hull}(C)$, and when $C$ is _LCD (linear code with
complementary dual)_ , which means $\operatorname{Hull}(C)$ is trivial. In
addition to the huge literature of self-dual codes, self-orthogonal codes, and
LCD codes (see for example [7, 9, 22, 23]), there have been many recent papers
studying hulls of families of codes more generally, some of which is motivated
by connections to quantum error-correcting codes.

The CSS construction gives a method for constructing a quantum error-
correcting code from a classical linear code, but this construction requires
that the classical code be self-orthogonal. Mathematicians have worked around
this self-orthogonality restriction by using _entanglement assistance_. This
technique allows for the construction of a quantum code from a pair of
classical codes $C_{1},C_{2}\subseteq\mathbb{F}_{q}^{n}$, and the dimension of
the _relative hull of $C_{1}$ with respect to $C_{2}$_, $C_{1}\cap
C_{2}^{\perp}$, plays an important role in analyzing the parameters.

Ruano and San-José have recently determined the dimension of the hulls of
projective Reed-Muller codes over the projective plane [26]. In fact, they
study intersections of pairs of projective Reed-Muller codes over the
projective plane more generally. We will review these contributions in Section
2.4. We give a different proof of one of their results in Section 4. The
results of our paper apply not only to projective Reed-Muller codes over the
projective plane, but also to projective Reed-Muller codes over higher-
dimensional projective spaces. We also note recent work of Gao, Yue, Huang,
and Zhang [10], and of Chen, Ling, and Liu [5], on hulls of generalized Reed-
Solomon codes.

Ruano and San-José investigate applications of their results to the
construction of quantum codes with good parameters in [26]. They study the
construction of quantum codes from projective Reed-Muller codes further in
[27], which focuses on what they call the _hull variation problem for
projective Reed-Muller codes_. Instead of restricting themselves to the study
of $C\cap C^{\perp}$ where $C$ is a projective Reed-Muller code, or even to
$C_{1}\cap C_{2}^{\perp}$ where $C_{1}$ and $C_{2}$ are projective Reed-Muller
codes, they consider $C_{1,\ell}\cap C_{2}^{\perp}$ where $C_{2}$ is a
projective Reed-Muller code and $C_{1,\ell}$ is a code that is monomially
equivalent to a projective Reed-Muller code. By varying the first code one can
vary the dimension of the intersection, which is sometimes desirable for
applications. The idea of varying the intersection by replacing one code with
a code monomially equivalent to it also occurs in work of Anderson et al. [1,
Theorem 4.6], and in work of Guenda et al. [13, Theorem 2.2]. We do not
consider these hull variation problems or the application to quantum codes in
this paper and leave this as a direction for future work.

The main contributions of our paper are as follows. Building on Sørensen’s
analysis of the dual of a projective Reed-Muller code, we completely determine
when projective Reed-Muller codes are self-dual, when they are self-
orthogonal, and when they are LCD. We then show that when $q$ is sufficiently
large, the dimension of the hull of a projective Reed-Muller code is $1$ less
than the dimension of the code. We then determine the dimension of the hull
for a wider range of parameters and explain how this leads to a new proof of a
recent result of Ruano and San José [26]. We give examples throughout the
paper to illustrate our results.

Our paper consists of four sections. Section 2 describes preliminaries on
projective Reed-Muller codes, the hull of a linear code, and duals of
projective Reed-Muller codes. We prove our main results in Sections 3 and 4.
We end the paper by highlighting parameters for which our results do not
determine the dimension of the hull, which suggests a natural direction for
future work.

##  2 Preliminaries

For a general reference on coding theory we recommend [15, 21, 25].

###  2.1 Projective Reed-Muller Codes

Let $\mathcal{P}=\\{P_{1},\dots,P_{N}\\}$ be a subset of points of the affine
space $\mathbb{F}_{q}^{n}$ and let $\mathcal{V}$ be a finite subspace of
polynomials in $\mathbb{F}_{q}[x_{1},\dots,x_{n}]$. Consider the evaluation
map:

$\displaystyle{\mbox{ev}}_{\mathcal{P}}:\mathcal{V}$
$\displaystyle\rightarrow$ $\displaystyle\mathbb{F}_{q}^{N}$ $\displaystyle f$
$\displaystyle\rightarrow$ $\displaystyle(f(P_{1}),\dots,f(P_{N})).$

The evaluation code $\operatorname{ev}(\mathcal{V},P)$ is the image of this
map. The affine Reed-Muller code of order $k$ and length $q^{n}$, which we
denote by ${\mbox{RM}}_{q}^{A}(k,n)$, comes from choosing $\mathcal{V}$ to be
$\mathbb{F}_{q}[x_{1},\dots,x_{n}]_{\leq k}$, the vector space of polynomials
of degree at most $k$, and $\mathcal{P}$ to be the set of all points in the
affine space $\mathbb{F}_{q}^{n}$. This is sometimes referred to as a
_generalized Reed-Muller code_ in the literature. Note that
${\mbox{RM}}_{q}^{A}(k,n)$ depends on a choice of the ordering of the points
of $\mathbb{F}_{q}^{n}$. Recall that two linear codes over $\mathbb{F}_{q}$
are _monomially equivalent_ [15] if one code can be obtained from the other by
permuting the coordinate positions and multiplying each coordinate by a
nonzero element of $\mathbb{F}_{q}$. It is clear that the affine Reed-Muller
codes that arise from different choices are all monomially equivalent.

Let $\mathcal{P}=\\{P_{1},\dots,P_{N}\\}$ be a subset of points in the
projective space $\mathbb{P}^{n}(\mathbb{F}_{q})$. It does not make sense to
evaluate an element of $\mathbb{F}_{q}[x_{0},\dots,x_{n}]$ at a projective
point, so we make a choice of affine representative for each, giving a set
$\mathcal{P}^{\prime}=\\{P_{1}^{\prime},\dots,P_{N}^{\prime}\\}$ with each
$P_{i}^{\prime}\in\mathbb{F}_{q}^{n+1}\setminus(0,0,\ldots,0)$. Let
$\mathcal{V}$ be a subspace of $\mathbb{F}_{q}[x_{0},\dots,x_{n}]_{k}$, the
set of homogeneous polynomials of degree $k$ (including the zero polynomial).
We now define an evaluation code as in the previous paragraph. When
$\mathcal{P}$ consists of all points in $\mathbb{P}^{n}(\mathbb{F}_{q})$ and
$\mathcal{V}$ is all of $\mathbb{F}_{q}[x_{0},\dots,x_{n}]_{k}$, this
construction defines the _projective Reed-Muller code of order $k$ and length_
$N=|\mathbb{P}^{n}(\mathbb{F}_{q})|=(q^{n+1}-1)/(q-1),$ denoted
${\mbox{RM}}_{q}^{P}(k,n)$. In this paper, we write $C_{n,k}^{q}$ for
${\mbox{RM}}_{q}^{P}(k,n)$ and $C_{n,k}^{A,q}$ for ${\mbox{RM}}_{q}^{A}(k,n)$.
As in the previous paragraph, the projective Reed-Muller codes that arise from
different orderings of the points of $\mathcal{P}$ and different choices of
affine representatives in $\mathcal{P}^{\prime}$ are monomially equivalent. In
this paper we follow the convention of Lachaud [18, 19] and Sørensen [28],
where for each projective point we choose the affine representative for which
the left-most nonzero coordinate is equal to $1$. Throughout the rest of this
paper, whenever we write $C_{n,k}^{q}$ we will use this choice of affine
representatives.

To give one basic example, when $k=1$ the projective Reed-Muller code arises
from evaluating linear forms on projective space and one can see that
$C_{n,1}^{q}$ is a $q$-ary simplex code. Lachaud discusses this example, and
$C_{n,2}^{q}$ where codewords come from evaluating quadratic polynomials, in
his initial paper on this topic [18].

Lachaud determined the parameters of the code $C_{n,k}^{q}$ in the case where
$1\leq k<q$.

######  Lemma 2.1.

([19, Theorem 2]) Assume that $1\leq k<q$. Then the code $C_{n,k}^{q}$ has
parameters length $N=\frac{q^{n+1}-1}{q-1}$, dimension $K=\binom{n+k}{k}$,
distance $D=(q-k+1)q^{n-1}$.

If $k\geq n(q-1)+1$, then $C_{n,k}^{q}$ is trivial, that is, the whole space
$\mathbb{F}_{q}^{N}$ [28, Remark 3]. For $1\leq k\leq n(q-1)$, Sørensen
computed the parameters of $C_{n,k}^{q}$. For a recent discussion of
Sørensen’s computation of the minimum distance and also for a characterization
of the minimal weight codewords of $C_{n,k}^{q}$, see the paper of Ghorpade
and Ludhani [11], and also the short note of Sørensen [29].

######  Lemma 2.2.

([28, Theorem 1]) Assume that $1\leq k\leq n(q-1)$. Then the code
$C_{n,k}^{q}$ has parameters

$\displaystyle{\mbox{{\rm length} }}N$ $\displaystyle=$
$\displaystyle\frac{q^{n+1}-1}{q-1},$ $\displaystyle{\mbox{{\rm dimension}
}}K$ $\displaystyle=$ $\displaystyle\sum_{\begin{subarray}{c}t\equiv
k\pmod{q-1}\\\ 0<t\leq
k\end{subarray}}\left(\sum_{j=0}^{n+1}(-1)^{j}\binom{n+1}{j}\binom{t-jq+n}{t-jq}\right),$
$\displaystyle{\mbox{{\rm distance} }}D$ $\displaystyle=$
$\displaystyle(q-s)q^{n-r-1},$

where

$k-1=r(q-1)+s,~{}~{}0\leq s<q-1.$

We remark that if $k<q$, then $r=0$ and $s=k-1$ so that

$D=(q-s)q^{n-r-1}=(q-(k-1))q^{n-1}=(q-k+1)q^{n-1},$

which matches the expression for $D$ in Lemma 2.1.

A different expression for the dimension of $C_{n,k}^{q}$ is given by Mercier
and Rolland [24]. See [11] for a discussion of the equivalence between these
two expressions.

######  Lemma 2.3.

([24, Theorem 4]) Assume that $1\leq k\leq n(q-1)$. Then $C_{n,k}^{q}$ has
dimension

$K=\binom{n+k}{k}-\sum_{j=2}^{n+1}(-1)^{j}\binom{n+1}{j}\sum_{i=0}^{j-2}\binom{k+(i+1)(q-1)-jq+n}{k+(i+1)(q-1)-jq}.$

We briefly recall some notation related to polynomials over finite fields. Let
$F(x_{0},\ldots,x_{n})\in\mathbb{F}_{q}[x_{0},\ldots,x_{n}]$. The _reduced
form of $F(x_{0},\ldots,x_{n})$_, denoted by
$\overline{F}(x_{0},\ldots,x_{n})$, is the polynomial we get by replacing any
factor $x_{j}^{t_{j}}$, where $t_{j}=a(q-1)+b$ with $0<b\leq q-1$, with
$x_{j}^{b}$. That is, $\overline{F}(x_{0},\ldots,x_{n})$ is the polynomial we
get by reducing modulo $x_{j}^{q}-x_{j}$ for each $j$.

######  Proposition 2.4.

For $k$ satisfying $1\leq k<n(q-1)$, we have
$\dim(C_{n,k}^{q})<\dim(C_{n,k+1}^{q})$.

We could give a proof of this using the expression for $\dim(C_{n,k}^{q})$
given in Lemma 2.2, or the one given in Lemma 2.3, but because these
expressions are complicated in general we give a more combinatorial argument.

###### Proof.

In the proof of [28, Theorem 2], Sørensen explains that the dimension of
$C_{n,k}^{q}$ is equal to the number of distinct elements $\overline{m}$ where
$m$ is a monomial in $x_{0},\ldots,x_{n}$ of degree $k$. We call a monomial
$m$ _reduced_ if all of its exponents are at most $q-1$. This is equivalent to
$\overline{m}=m$. We see that $\dim(C_{n,k}^{q})$ is equal to the number of
reduced monomials in $x_{0},\ldots,x_{n}$ of degree $k-j(q-1)$ where $j$ can
take any value satisfying $0\leq j<\frac{k}{q-1}$.

Let $\mathcal{R}_{n,k}^{q}$ denote the set of reduced monomials $\overline{m}$
as $m$ runs through all monomials of degree $k$ in $x_{0},\ldots,x_{n}$. We
will give an injective function
$\varphi\colon\mathcal{R}_{n,k}^{q}\rightarrow\mathcal{R}_{n,k+1}^{q}$ and
then will prove that there exists an element of
$\mathcal{R}_{n,k+1}^{q}\setminus\varphi\left(\mathcal{R}_{n,k}^{q}\right)$.
This shows that $|\mathcal{R}_{n,k+1}^{q}|>|\mathcal{R}_{n,k}^{q}|$,
completing the proof.

Define $\varphi\colon\mathcal{R}_{n,k}^{q}\rightarrow\mathcal{R}_{n,k+1}^{q}$
by $\varphi(m)=\overline{x_{0}m}$. There are two cases to consider.

  1. 1.

First suppose that $x_{0}m=\overline{x_{0}m}$. This occurs precisely when the
exponent of $x_{0}$ in $m$ is less than $q-1$. If $m=\overline{F}$ for some
homogeneous polynomial $F$ of degree $k$, then it is clear that
$x_{0}m=\overline{x_{0}F}$. Therefore, $x_{0}m\in\mathcal{R}_{n,k+1}^{q}$.

  2. 2.

Now suppose that $x_{0}m\neq\overline{x_{0}m}$. This occurs precisely when the
exponent of $x_{0}$ in $m$ is $q-1$. In this case,
$\overline{x_{0}m}=\frac{x_{0}m}{x_{0}^{q-1}}$ and
$\frac{x_{0}m}{x_{0}^{q-1}}$ is reduced. As in the previous case, if
$m=\overline{F}$ for some homogeneous polynomial $F$ of degree $k$, then it is
clear that $\overline{x_{0}m}=\overline{x_{0}F}$. Therefore,
$\overline{x_{0}m}\in\mathcal{R}_{n,k+1}^{q}$.

We have shown that
$\varphi\colon\mathcal{R}_{n,k}^{q}\rightarrow\mathcal{R}_{n,k+1}^{q}$ is
injective. We now show that there exists an element of
$\mathcal{R}_{n,k+1}^{q}\setminus\varphi\left(\mathcal{R}_{n,k}^{q}\right)$.

The definition of $\varphi$ implies that the exponent of $x_{0}$ is nonzero in
every monomial in $\varphi\left(\mathcal{R}_{n,k}^{q}\right)$. Since $k+1\leq
n(q-1)$, there is at least one monomial $x_{0}^{0}x_{1}^{a_{1}}\cdots
x_{n}^{a_{n}}$ for which $\sum_{i=1}^{n}a_{i}=k+1$ and $0\leq a_{i}\leq q-1$
for each $i$. That is, there is at least one reduced monomial of degree $k+1$
in which the exponent of $x_{0}$ is $0$. This is an element of
$\mathcal{R}_{n,k+1}^{q}\setminus\varphi\left(\mathcal{R}_{n,k}^{q}\right)$. ∎

The following fact follows immediately. We will apply it in our proof of
Theorem 3.5.

######  Corollary 2.5.

Suppose $a$ and $b$ are integers satisfying $1\leq a<b\leq n(q-1)$. Then
$\dim(C_{n,b}^{q})-\dim(C_{n,a}^{q})\geq b-a$.

###  2.2 The Hull of a Linear Code

Suppose $x=(x_{1},\ldots,x_{N})$ and $y=(y_{1},\ldots,y_{N})$ are elements of
$\mathbb{F}_{q}^{N}$. Let $\langle x,y\rangle=\sum_{i=1}^{N}x_{i}y_{i}$. The
_dual_ of a linear code $C\subseteq\mathbb{F}_{q}^{N}$ is

$C^{\perp}=\\{y\in\mathbb{F}_{q}^{N}\colon\langle y,c\rangle=0\ \text{ for all
}c\in C\\}.$

The _hull_ of a linear code $C$ is defined by $\operatorname{Hull}(C)=C\cap
C^{\perp}$. A linear code is _self-dual_ if $C=C^{\perp}$ and is _self-
orthogonal_ if $C\subseteq C^{\perp}$. A $K\times N$ matrix $G$ over
$\mathbb{F}_{q}$ is a _generator matrix_ for a linear code
$C\subset\mathbb{F}_{q}^{N}$ of dimension $K$ if the rows of $G$ form a basis
for $C$. We recall a basic fact about the dimension of the hull of a linear
code $C$.

######  Proposition 2.6.

([14, Proposition 3.1]) Let $C\subseteq\mathbb{F}_{q}^{N}$ be a linear code of
dimension $K$ and let $G$ be a generator matrix for $C$. Then
$\operatorname{rank}(GG^{T})=K-\dim(\operatorname{Hull}(C))$.

In particular, $C$ is self-orthogonal if and only if $GG^{T}$ is the zero
matrix and $C$ is LCD if and only if $GG^{T}$ is invertible.

There is a result like this one that can be used to determine the dimension of
$C_{1}\cap C_{2}^{\perp}$ when $C_{1},C_{2}\subseteq\mathbb{F}_{q}^{N}$ are
linear codes that are not necessarily equal [13, Theorem 2.1]. We will not
apply this result in this paper, but at the end of Section 4 when we discuss
further directions for our work we will return to the role that this theorem
would play in our strategy.

###  2.3 Duals of Projective Reed-Muller Codes

In order to study hulls of projective Reed-Muller codes, we need to understand
the dual of a projective Reed-Muller code. It is well known that the dual of
an affine Reed-Muller code is also an affine Reed-Muller code. More precisely,
$C_{n,k}^{A,q}\ {}^{\perp}=C_{n,n(q-1)-k-1}^{A,q}$; see for example [6]. Since
$\mathbb{F}_{q}[x_{1},\dots,x_{n}]_{\leq
k}\subseteq\mathbb{F}_{q}[x_{1},\dots,x_{n}]_{\leq k+1}$, it is clear that if
$\ell=n(q-1)-k-1$ and $k^{\prime}=\min(k,\ell)$ then $C_{n,k^{\prime}}^{q,A}$
is self-orthogonal. Therefore, in all cases we can determine
$\operatorname{Hull}(C_{n,k}^{A,q})$.

The projective analogue of this situation is more complicated since it is not
always the case that the dual of a projective Reed-Muller code is a projective
Reed-Muller code. Sørensen computes the dual of a projective Reed-Muller code
in [28]. Throughout this paper, we write ${\bf 1}=(1,1,\dots,1)$. We recall
the convention that $C_{n,0}^{q}=\mbox{Span}_{\mathbb{F}_{q}}\\{{\bf 1}\\}$,
since the homogeneous polynomials of degree $0$ in $x_{0},\ldots,x_{n}$ are
the constant functions.

######  Theorem 2.7.

([28, Theorem 2]) Let $k$ be an integer satisfying $1\leq k\leq n(q-1)$ and
let $\ell=n(q-1)-k$. Then

  1. (i)

${C_{n,k}^{q}}^{\perp}=C_{n,\ell}^{q}$ for $k\not\equiv 0\pmod{q-1}$.

  2. (ii)

${C_{n,k}^{q}}^{\perp}={{\operatorname{Span}}}_{\mathbb{F}_{q}}\\{{\bf
1},C_{n,\ell}^{q}\\}$ for $k\equiv 0\pmod{q-1}$.

######  Remark 2.8.

Suppose $k$ is an integer satisfying $1\leq k<n(q-1)$ and $k\equiv
0\pmod{q-1}$. Let $\ell=n(q-1)-k$. Theorem 2.7 implies that
${C_{n,k}^{q}}^{\perp}={\mbox{Span}}_{\mathbb{F}_{q}}\\{{\bf
1},C_{n,\ell}^{q}\\}$. In these cases ${\bf 1}\not\in C_{n,\ell}^{q}$, so we
have $C_{n,\ell}^{q}\subsetneq{C_{n,k}^{q}}^{\perp}$. Sørensen does not
explain why ${\bf 1}\not\in C_{n,\ell}^{q}$, so we give a quick proof of this
fact.

Suppose ${\bf 1}\in C_{n,\ell}^{q}$. Note that $\ell\equiv-k\equiv
0\pmod{q-1}$ and that $\ell>0$. At the end of the proof of Theorem 2.7,
Sørensen shows that ${\bf 1}\in{C_{n,\ell}^{q}}^{\perp}$. If $m$ is a positive
integer we have $m\cdot 1=0$ in $\mathbb{F}_{q}$ if and only if the
characteristic of $\mathbb{F}_{q}$ divides $m$. However,

$\langle{\bf 1},{\bf 1}\rangle=\frac{q^{n+1}-1}{q-1}\cdot
1=(q^{n}+q^{n-1}+\cdots+q+1)\cdot 1.$

Since $q$ is a power of $\operatorname{char}(\mathbb{F}_{q})$ it is clear that
$q^{n}+q^{n-1}+\cdots+q+1\equiv 1\pmod{\operatorname{char}(\mathbb{F}_{q})}$.
This implies $\langle{\bf 1},{\bf 1}\rangle\neq 0$ in $\mathbb{F}_{q}$,
contradicting the fact that ${\bf 1}\in{C_{n,\ell}^{q}}^{\perp}$.

Now suppose $k=n(q-1)$. Since
${C_{n,n(q-1)}^{q}}^{\perp}={\mbox{Span}}_{\mathbb{F}_{q}}\\{{\bf 1}\\}$, the
argument in the previous paragraph shows that ${\bf 1}\not\in
C_{n,n(q-1)}^{q}$. This observation implies that
$\operatorname{Hull}(C_{n,n(q-1)}^{q})$ is trivial, or equivalently, that
$C_{n,n(q-1)}^{q}$ is an LCD code.

###  2.4 Hulls of Projective Reed-Muller Codes over the Projective Plane

Ruano and San-José study projective Reed-Muller codes over the projective
plane in [26]. That is, they focus on the $n=2$ case of our general study of
the codes $C_{n,k}^{q}$. Ruano and San-José give a basis for
$\operatorname{Hull}(C_{2,k}^{q})$ for any $1\leq k\leq q-1$ in the following
form.

######  Theorem 2.9.

[26, Corollary 3.12] Let $1\leq k\leq q-1$ and let
$Y=\\{0,1,\ldots,\min\\{k-1,q-1-k-1\\}\\}$.

  * •

If $2k\equiv 0\pmod{q-1}$, then
$C_{2,k}^{q}\cap{C_{2,k}^{q}}^{\perp}=C_{2,k}^{q}$.

  * •

If $2k\not\equiv 0\pmod{q-1}$, a basis for
$C_{2,k}^{q}\cap{C_{2,k}^{q}}^{\perp}$ is given by

$A_{1}^{k}\cup\left(\bigcup_{a_{2}\in Y}x_{1}^{k-a_{2}}x_{2}^{a_{2}}\right),$

where

$A_{1}^{k}=\\{x_{0}^{a_{0}}x_{1}^{a_{1}}x_{2}^{a_{2}}\colon a_{0}>0,\
a_{0}+a_{1}+a_{2}=k,\ 0\leq a_{1},a_{2}\leq q-1\\}.$

Consequently,

$\dim(\operatorname{Hull}(C_{2,k}^{q}))=\binom{k+1}{2}+\min\\{k,q-k-1\\}.$

For any $k$ satisfying $1\leq k<2(q-1)$ except $k=q-1$, Theorem 2.7(i) implies
that ${C_{2,k}^{q}}^{\perp}=C_{2,2(q-1)-k}^{q}$. If $k$ satisfies
$q-1<k<2(q-1)$, then ${C_{2,k}^{q}}^{\perp}=C_{2,\ell}^{q}$ where
$\ell=2(q-1)-k$ satisfies $1\leq\ell<q-1$, and
$\operatorname{Hull}(C_{2,k}^{q})=\operatorname{Hull}(C_{2,\ell}^{q})$. In
this way, we see that Theorem 2.9 gives a basis for
$\operatorname{Hull}(C_{2,k}^{q})$ for all $k$ satisfying $1\leq k\leq
2(q-1)$.

Theorem 2.9 follows from the results we prove in Section 4. We emphasize that
our proof is quite different than the one given by Ruano and San-José. A main
idea in [26] is to view codewords of projective Reed-Muller codes as classes
of polynomials in a quotient ring. They then compute bases of some subspaces
of quotient rings associated to projective Reed-Muller codes by using
techniques from commutative algebra. In particular, the authors work with a
particular basis of the vanishing ideal of the collection of points of
$\mathbb{P}^{2}(\mathbb{F}_{q})$. Our proofs work directly with the linear
algebraic setup of Proposition 2.6, taking sums of polynomials evaluated at
the standard affine representatives of the points of
$\mathbb{P}^{n}(\mathbb{F}_{q})$ to determine the rank of the relevant matrix.

We note that Ruano and San-José actually consider the more general problem of
determining a basis for $C_{2,k_{1}}^{q}\cap C_{2,k_{2}}^{q}$ where $1\leq
k_{1},k_{2},\leq 2(q-1)$. Theorem 2.9 comes from specializing to the case
where $k_{2}=2(q-1)-k_{1}$ [26, Corollary 3.11]. In Section 4 we discuss how
one could adapt our techniques to ammept to give a different proof of this
more general statement about projective Reed-Muller codes with $n=2$.

##  3 Special Classes of Projective Reed-Muller Codes

Our goal is to understand the following question.

######  Question 3.1.

  1. 1.

For which parameters $(n,k,q)$ is the projective Reed-Muller code
$C_{n,k}^{q}$ self-dual?

  2. 2.

For which parameters $(n,k,q)$ is $C_{n,k}^{q}$ self-orthogonal?

  3. 3.

For which parameters $(n,k,q)$ is $C_{n,k}^{q}$ LCD?

  4. 4.

In cases where $C_{n,k}^{q}$ is not self-orthogonal, what can we say about
$\operatorname{Hull}(C_{n,k}^{q})$?

In this section we answer the first three questions. We consider the last one
in Section 4.

We begin this section by applying Theorem 2.7 to answer the first part of
Question 3.1 and determine when a projective Reed-Muller code is self-dual.

######  Theorem 3.2.

Let $1\leq k\leq n(q-1)$. Then $C^{q}_{n,k}$ is self-dual if and only if $q$
and $n$ are odd and $k=\frac{n(q-1)}{2}$.

###### Proof.

Suppose that $q$ and $n$ are odd and $k=\frac{n(q-1)}{2}$. Then $k\not\equiv
0\pmod{q-1}$ because $n$ is odd. Note that $n(q-1)-k=k$. Theorem 2.7(i)
implies that ${C_{n,k}^{q}}^{\perp}={C_{n,k}^{q}}$, proving that
${C_{n,k}^{q}}$ is self-dual.

Conversely, suppose that $C^{q}_{n,k}$ is self-dual. Then its length
$N=q^{n}+q^{n-1}+\cdots+1$ is even. If $q$ is even, then $N$ is odd. Hence $q$
is odd. We complete the proof by considering two cases.

  * •

Suppose that $k\not\equiv 0\pmod{q-1}$. Then by Theorem 2.7(i), we have

${C_{n,k}^{q}}^{\perp}=C_{n,\ell}^{q}=C_{n,n(q-1)-k}^{q}.$

Proposition 2.4 implies that for any $1\leq k,k^{\prime}\leq n(q-1)$ with
$k\neq k^{\prime}$ the codes $C_{n,k}^{q}$ and $C_{n,k^{\prime}}^{q}$ have
different dimensions. Therefore,
${C_{n,k}^{q}}^{\perp}=C_{n,\ell}^{q}=C_{n,k}^{q}$ implies $\ell=n(q-1)-k=k$,
that is, $k=\frac{n(q-1)}{2}$. If $n$ is even, then $k=\frac{n(q-1)}{2}\equiv
0\pmod{q-1}$, which is a contradiction. Hence, $n$ is odd.

  * •

Suppose that $k\equiv 0\pmod{q-1}$. Then we have
${C_{n,k}^{q}}^{\perp}={\mbox{Span}}_{\mathbb{F}_{q}}\\{{\bf
1},C_{n,n(q-1)-k}^{q}\\}$ by Theorem 2.7(ii). Since $C^{q}_{n,k}$ is self-
dual, we know that

$C^{q}_{n,k}={C_{n,k}^{q}}^{\perp}={\mbox{Span}}_{\mathbb{F}_{q}}\\{{\bf
1},C_{n,n(q-1)-k}^{q}\\}.$

This implies that ${\bf 1}\in C^{q}_{n,k}$. By the remark following Theorem
2.7, this is not possible. Therefore, $C^{q}_{n,k}$ is not self-dual.

∎

######  Example 3.3.

Let $q=3$. In order to apply Theorem 3.2, we must have $n$ odd and $k=n$.

For each odd $n$, $C_{n,n}^{3}$ is a self-dual code with parameters
$[N=\frac{3^{n+1}-1}{2},K=N/2,D=3^{\frac{n+1}{2}}]$. In particular,
$C_{1,1}^{3}$ is a ternary self-dual $[4,2,3]$ code, which is known as the
tetracode. When $k=3$, $C_{3,3}^{3}$ is a ternary self-dual $[40,20,9]$ code.
Elkies [8] showed that this code is self-dual in his work on the weight
enumerator of the projective Reed-Muller code $C_{3,3}^{q}$. The weight
enumerator of this code is given by

$\displaystyle
x^{40}+1040x^{31}y^{9}+18720x^{28}y^{12}+1100736x^{25}y^{15}+25761840x^{22}y^{18}$
$\displaystyle+$ $\displaystyle
236377440x^{19}y^{21}+908079120x^{16}y^{24}+1388750720x^{13}y^{27}$
$\displaystyle+$ $\displaystyle
783679104x^{10}y^{30}+137535840x^{7}y^{33}+5468320x^{4}y^{36}+11520xy^{39}.$

A computation in Magma shows that the automorphism group of $C_{3,3}^{3}$ is
isomorphic to $\operatorname{GL}_{4}(\mathbb{F}_{3})$. We refer to [4] for a
detailed discussion of automorphism groups of projective Reed-Muller codes. It
is also interesting to note that the set of codewords of weight 9 form a
2-design. More precisely, there are 1040 codewords of weight 9. Since we are
only considering the supports of these vectors over $\mathbb{F}_{3}$, there
are exactly 520 distinct supports (also called blocks). We have checked using
Magma that for any two distinct positions out of 40, there are exactly 24
blocks containing them, hence we get $\lambda=24$. Therefore we have a
2-$(40,9,24)$ design.

######  Example 3.4.

Let $q=5$. Theorem 3.2 implies that $C_{n,k}^{5}$ is self-dual if and only if
$n$ is odd and $k=2n$. Note that $k-1=2n-1=2(2n^{\prime}+1)-1=4n^{\prime}+1$
for some integer $n^{\prime}\geq 0$. If we write $k-1=4r+s$ where $0<s\leq 4$,
we find $r=n^{\prime}$ and $s=1$. This implies
$r=\frac{2n-2}{4}=\frac{n-1}{2}$. The code $C_{n,k}^{5}$ has parameters
$[N=\frac{5^{n+1}-1}{4},K=N/2,D=4\cdot 5^{\frac{n-1}{2}}]$.

In particular, $C_{1,2}^{5}$ is a self-dual code with parameters $[6,3,4]$
over $\mathbb{F}_{5}$. It is also an MDS code. This code is unique up to
$(1,-1)$-monomial matrix equivalence and is known as $F_{6}$ in the notation
of [20]. A generator matrix of this code is given by

$\left[\begin{array}[]{cccccc}1&0&1&4&4&1\\\ 1&1&0&1&4&4\\\ 1&4&1&0&1&4\\\
\end{array}\right].$

In several places throughout the rest of the paper, we construct a choice of
generator matrix for $C_{n,k}^{q}$. This involves the evaluation map
$\operatorname{ev}(f)$, which depends on an ordered choice of affine
representatives for the points of $\mathbb{P}^{n}(\mathbb{F}_{q})$. Recall
that we are following the convention that for each projective point, we choose
the affine representative for which the left-most nonzero coordinate is equal
to $1$. We fix an arbitrary ordering of these affine representatives to get
$\mathcal{P}^{\prime}$. We will use this ordered choice of affine
representatives $\mathcal{P}^{\prime}$ throughout the rest of the paper.

We now answer the second the second part of Question 3.1 and determine the
projective Reed-Muller codes that are self-orthogonal.

######  Theorem 3.5.

Suppose that $1\leq k\leq n(q-1)$. Then $C_{n,k}^{q}$ is self-orthogonal if
and only if $1\leq k\leq\frac{n(q-1)}{2}$ and $2k\equiv 0\pmod{q-1}$.

###### Proof.

Suppose that $1\leq k\leq\frac{n(q-1)}{2}$ and $2k\equiv 0\pmod{q-1}$. Since
$2k\equiv 0\pmod{q-1}$ and $k\leq\frac{n(q-1)}{2}$, we have
$\ell=n(q-1)-k=k+r(q-1)$ for some $r\geq 0$. By Theorem 2.7,
$C_{n,n(q-1)-k}^{q}\subseteq{C_{n,k}^{q}}^{\perp}$.

In order to prove $C_{n,k}\subseteq{C_{n,k}^{q}}^{\perp}$, it suffices to show
that $C_{n,k}\subseteq C_{n,n(q-1)-k}^{q}$. For each monomial $m$ of degree
$k$, we construct a monomial $m^{\prime}$ of degree $n(q-1)-k$ such that
$\overline{m^{\prime}}=m$. Let $x_{0}^{a_{1}}\cdots x_{n}^{a_{n}}$ be a
monomial of degree $k$, so $0\leq a_{0},\ldots,a_{n}\leq k$ and
$\sum_{i=0}^{n}a_{i}=k$. Let $j$ be the smallest positive integer such that
$a_{j}>0$. The evaluation map sends a polynomial and the reduced form of that
polynomial to the same element of $\mathbb{F}_{q}^{N}$. More precisely,
$x_{j}^{r(q-1)+a_{j}}=x_{j}^{a_{j}}$ at every element of $\mathbb{F}_{q}$.
Therefore

$\operatorname{ev}_{\mathcal{P}}(x_{0}^{a_{1}}\cdots
x_{n}^{a_{n}}x_{j}^{r(q-1)})=\operatorname{ev}_{\mathcal{P}}(x_{0}^{a_{1}}\cdots
x_{n}^{a_{n}}).$

We see that the span of $\operatorname{ev}_{\mathcal{P}}(x_{0}^{a_{1}}\cdots
x_{n}^{a_{n}})$ as we vary over all monomials in $x_{0},\ldots,x_{n}$ of
degree $k$ is a subcode of $C_{n,n(q-1)-k}^{q}$, completing the proof that
$C_{n,k}^{q}$ is self-orthogonal.

We now show that $C_{n,k}^{q}$ is not self-orthogonal in all other cases.
Suppose $\frac{n(q-1)}{2}<k\leq n(q-1)$. Let $\ell=n(q-1)-k$, so
$0\leq\ell<\frac{n(q-1)}{2}$ and $k-\ell=2k-n(q-1)$. We consider two cases.

  1. 1.

Suppose $k-\ell=1$. This implies $k=\frac{n(q-1)+1}{2}$, so in particular $q$
is even and $n$ is odd. Note that $2k=n(q-1)+1\equiv 1\pmod{q-1}$. If $q\neq
2$, then $k\not\equiv 0\pmod{q-1}$ and Theorem 2.7(i) implies that
${C_{n,k}^{q}}^{\perp}=C_{n,\ell}^{q}$. Proposition 2.4 implies that
$\dim({C_{n,k}^{q}}^{\perp})<\dim(C_{n,k}^{q})$, and therefore $C_{n,k}^{q}$
is not self-orthogonal.

Suppose $q=2$. If $n=1$, then $k=1$. It is easy to check that $C_{1,1}^{2}$ is
not self-orthogonal, so we suppose $n>1$. In particular,
$k=\frac{n(q-1)+1}{2}<n(q-1)$. Theorem 2.7 implies that
${C_{n,k}^{q}}^{\perp}={\mbox{Span}}_{\mathbb{F}_{q}}\\{{\bf
1},C_{n,\ell}^{q}\\}$. The argument in Remark 2.8 implies that ${\bf 1}\not\in
C_{n,\ell}^{q}$, so

$\dim({C_{n,k}^{q}}^{\perp})=\dim(C_{n,\ell}^{q})+1\leq\dim(C_{n,k}^{q}).$

If $C$ is a linear code for which $\dim(C^{\perp})\leq\dim(C)$, then $C$ is
self-orthogonal if and only if it is self-dual. But, ${C_{n,k}^{q}}^{\perp}$
contains ${\bf 1}$, and the argument in Remark 2.8 shows that $C_{n,k}^{q}$
does not. We conclude that $C_{n,k}^{q}$ is not self-orthogonal.

  2. 2.

Suppose $k-\ell\geq 2$. By Theorem 2.7,
${C_{n,k}^{q}}^{\perp}\subseteq{\mbox{Span}}_{\mathbb{F}_{q}}\\{{\bf
1},C_{n,\ell}^{q}\\}$, which implies
$\dim({C_{n,k}^{q}}^{\perp})\leq\dim(C_{n,\ell}^{q})+1$. By Corollary 2.5,
$\dim(C_{n,k}^{q})-\dim(C_{n,\ell}^{q})\geq k-\ell\geq 2$. We conclude that
$\dim(C_{n,k}^{q})>\dim({C_{n,k}^{q}}^{\perp})$, so $C_{n,k}^{q}$ is not self-
orthogonal.

Now suppose that $1\leq k\leq\frac{n(q-1)}{2}$ and that $2k\not\equiv
0\pmod{q-1}$. Let $G$ be a generator matrix for $C_{n,k}^{q}$. We will show
that $GG^{T}$ has a nonzero entry. Applying Proposition 2.6 then shows that
$C_{n,k}^{q}$ is not self-orthogonal.

Choose a basis for $C_{n,k}^{q}$ including the monomial $x_{n}^{k}$. Let $G$
be a generator matrix for $C_{n,k}^{q}$ for which the first row is equal to
$\operatorname{ev}(x_{n}^{k})$. Throughout the rest of this proof, let
$f(x_{0},\ldots,x_{n})=x_{n}^{2k}$. The top left entry of $GG^{T}$ is equal to
$\sum_{p\in\mathcal{P}^{\prime}}f(p)$.

We recall the basic fact that for any positive integer $r$, we have

$\sum_{\beta\in\mathbb{F}_{q}}\beta^{r}=\begin{cases}-1&\text{if }r\equiv
0\pmod{q-1}\\\ 0&\text{otherwise}\end{cases}.$ (1)

Because of our choice of affine representatives $\mathcal{P}^{\prime}$ and the
fact that $2k\not\equiv 0\pmod{q-1}$, we have
$\sum_{p\in\mathcal{P}^{\prime}}f(p)=f(0,\ldots,0,1)=1^{2k}=1$. Therefore,
$GG^{T}$ has a nonzero entry and $C_{n,k}^{q}$ is not self-orthogonal. ∎

Theorem 3.5 directly implies the following result.

######  Corollary 3.6.

Suppose that $1\leq k\leq\frac{n(q-1)}{2}$ and $2k\equiv 0\pmod{q-1}$. Then
$C^{q}_{n,k}\subseteq{C^{q}_{n,k}}^{\perp}$ and so
$\operatorname{Hull}(C^{q}_{n,k})=C^{q}_{n,k}$.

######  Example 3.7.

For any odd prime power $q$, $C_{2,\frac{q-1}{2}}^{q}$ is a self-orthogonal
code with parameters
$[N=q^{2}+q+1,K=\frac{(q+3)(q+1)}{8},D=\frac{(q+3)}{2}q]$. For example, when
$q=3$, $C_{2,1}^{q}$ is a self-orthogonal $[13,3,9]$ code over
$\mathbb{F}_{3}$, whose parameters are optimal based on Grassl’s table [12].
When $q=5$, $C_{2,2}^{q}$ is a self-orthogonal $[31,6,20]$ code over
$\mathbb{F}_{5}$, whose parameters are best known based on Grassl’s table
[12].

The following corollary describes a situation for which
${C_{n,k}^{q}}^{\perp}$ is self-orthogonal.

######  Corollary 3.8.

Suppose that $\frac{n(q-1)}{2}\leq k\leq n(q-1)$ and $2k\equiv 0\pmod{q-1}$
but $k\not\equiv 0\pmod{q-1}$. Then ${C_{n,k}^{q}}^{\perp}$ is self-
orthogonal. That is, for any odd positive integer $n\leq r<2n$, we have
${C_{n,\frac{r(q-1)}{2}}^{q}}^{\perp}$ is self-orthogonal.

###### Proof.

Let $\ell=n(q-1)-k$ and note that $\ell\leq\frac{n(q-1)}{2}$. Since
$2\ell\equiv-2k\pmod{q-1}$, we see that $2\ell\equiv 0\pmod{q-1}$, but
$\ell\equiv-k\not\equiv 0\pmod{q-1}$. Theorem 2.7 implies that
${C_{n,k}^{q}}^{\perp}=C_{n,\ell}^{q}$ and Theorem 3.5 implies that
$C_{n,\ell}^{q}$ is self-orthogonal. ∎

######  Example 3.9.

This corollary shows that ${C_{2,3}^{3}}^{\perp}$ is self-orthogonal since
$3-1\leq 3\leq 2(3-1)$ and $6\equiv 0\pmod{2}$, but $3\not\equiv 0\pmod{2}$.
This examples comes from choosing $r=3$ in the second part of the statement of
the corollary.

We next characterize the projective Reed-Muller codes that are LCD. That is,
we determine the $(n,k,q)$ for which $C^{q}_{n,k}\cap{C_{n,k}^{q}}^{\perp}$ is
trivial.

######  Theorem 3.10.

Let $1\leq k<n(q-1)$. Then $C^{q}_{n,k}\cap{C_{n,k}^{q}}^{\perp}$ is
nontrivial. That is, $C_{n,k}^{q}$ is not LCD.

######  Remark 3.11.

As discussed at the end of Remark 2.8, $C_{n,n(q-1)}^{q}$ is LCD. Taken
together with Theorem 3.10 we see that if $1\leq k\leq n(q-1)$, then
$C_{n,k}^{q}$ is LCD if and only if $k=n(q-1)$.

###### Proof of Theorem 3.10.

We prove that $\operatorname{Hull}(C)$ is nontrivial by showing that
$\operatorname{ev}(x_{0}^{k})\in C^{q}_{n,k}\cap{C_{n,k}^{q}}^{\perp}$. Since
$x_{0}^{k}$ is a monomial of degree $k$, it is clear that
$\operatorname{ev}(x_{0}^{k})\in C_{n,k}^{q}$. We need only show that that
$\operatorname{ev}(x_{0}^{k})$ is orthogonal to $\operatorname{ev}(m)$ for
every monomial $m=x_{0}^{b_{0}}x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}$ where each
$b_{i}$ satisfies $0\leq b_{i}\leq k$ and $b_{0}+\cdots+b_{n}=k$.

We compute that
$\langle\operatorname{ev}(x_{0}^{k}),\operatorname{ev}(m)\rangle$ is equal to

$\displaystyle\sum_{p\in\mathcal{P}^{\prime}}(x_{0}^{k}m)(p)$ $\displaystyle=$
$\displaystyle\sum_{\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}}1^{k+b_{0}}\alpha_{1}^{b_{1}}\alpha_{2}^{b_{2}}\cdots\alpha_{n}^{b_{n}}$
$\displaystyle+\sum_{\alpha_{2},\ldots,\alpha_{n}\in\mathbb{F}_{q}}0^{k+b_{0}}1^{b_{1}}\alpha_{2}^{b_{2}}\cdots\alpha_{n}^{b_{n}}$
$\displaystyle+\cdots$
$\displaystyle+\sum_{\alpha_{n}\in\mathbb{F}_{q}}\left(0^{k+b_{0}}\cdots
0^{b_{n-2}}\right)1^{b_{n-1}}\alpha_{n}^{b_{n}}$
$\displaystyle+\left(0^{k+b_{0}}\cdots 0^{b_{n-1}}\right)1^{b_{n}}$
$\displaystyle=$
$\displaystyle\sum_{\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}}\alpha_{1}^{b_{1}}\alpha_{2}^{b_{2}}\cdots\alpha_{n}^{b_{n}}$
$\displaystyle=$
$\displaystyle\left(\sum_{\alpha_{1}\in\mathbb{F}_{q}}\alpha_{1}^{b_{1}}\right)\left(\sum_{\alpha_{2}\in\mathbb{F}_{q}}\alpha_{2}^{b_{2}}\right)\cdots\left(\sum_{\alpha_{n}\in\mathbb{F}_{q}}\alpha_{n}^{b_{n}}\right).$

For a nonnegative integer $b$, Equation (1) implies that
$\sum_{\alpha\in\mathbb{F}_{q}}\alpha^{b}$ is $0$ unless $b\equiv 0\pmod{q-1}$
and $b$ is positive. Since $b_{1}+\cdots+b_{n}\leq k<n(q-1)$, it is not
possible for each of the sums
$\sum_{\alpha_{i}\in\mathbb{F}_{q}}\alpha_{i}^{b_{i}}$ to simultaneously be
nonzero. We conclude that $\operatorname{ev}(x_{0}^{k})$ is orthogonal to
$\operatorname{ev}(m)$. Since $m$ was an arbitrary monomial of degree $k$, we
see that $\operatorname{ev}(x_{0}^{k})\in{C_{n,k}^{q}}^{\perp}$. ∎

##  4 Hulls of Projective Reed-Muller Codes

In the previous section we determined when projective Reed-Muller codes have
certain special properties, that is, when they are self-dual, when they are
self-orthogonal, and when they are LCD. For most parameters, the projective
Reed-Muller code $C_{n,k}^{q}$ does not satisfy any of these special
conditions, but we would still like to understand the dimension of its hull.
In this section we will determine the dimension of
$\operatorname{Hull}(C_{n,k}^{q})$ when $k<q-1$. Replacing $C_{n,k}^{q}$ with
its dual and noting that for any code $C$,
$\operatorname{Hull}(C)=\operatorname{Hull}(C^{\perp})$, we will also
determine the dimension of $\operatorname{Hull}(C_{n,k}^{q})$ when
$(n-1)(q-1)<k<n(q-1)$. We then consider the case where $n=2$ and see how this
recovers a result of Ruano and San-José about dimensions of hulls of
projective Reed-Muller codes over the projective plane. At the end of this
section we summarize the range of parameters for which our results determine
the dimension of $\operatorname{Hull}(C_{n,k}^{q})$.

We begin by determining $\dim(\operatorname{Hull}(C_{n,k}^{q}))$ when $k$ is
not too large relative to $q$.

######  Theorem 4.1.

Suppose that $q>2k+1$. Then

$\dim(\operatorname{Hull}(C^{q}_{n,k}))=\dim(C^{q}_{n,k})-1=\binom{n+k}{k}-1.$

Moreover, a basis for $\operatorname{Hull}(C_{n,k}^{q})$ is given by
$\\{\operatorname{ev}(m)\\}_{m\in\mathcal{M}}$ where $\mathcal{M}$ is the set
of monomials of degree $k$ in $x_{0},x_{1},\ldots,x_{n}$ except for the
monomial $x_{n}^{k}$.

###### Proof.

By Proposition 2.6 it suffices to show that $\operatorname{rank}(GG^{T})=1$
where $G$ is a generator matrix for $C^{q}_{n,k}$. Since $q>2k+1$, Lemma 2.1
implies that $C^{q}_{n,k}$ has dimension $\binom{n+k}{k}$. We take the
lexicographic ordering of the $\binom{n+k}{k}$ monomials of degree $k$ in
$x_{0},\ldots,x_{n}$. We write this ordered list of monomials as
$m_{1},\ldots,m_{\binom{n+k}{k}}$. Note that $m_{\binom{n+k}{k}}=x_{n}^{k}$.
It is clear that
$\operatorname{ev}(m_{1}),\ldots,\operatorname{ev}(m_{\binom{n+k}{k}})$ form
an ordered basis for $C_{n,k}^{q}$. These choices determine a generator matrix
$G$. We will prove that $GG^{T}$ has a single nonzero entry, so in particular,
$\operatorname{rank}(GG^{T})=1$.

The $(i,j)$-entry of $GG^{T}$ comes from taking the sum of the evaluations of
the monomial $m_{i}m_{j}$ over the points of $\mathcal{P}^{\prime}$. Suppose
$m_{i}=x_{0}^{a_{0}}\cdots x_{n}^{a_{n}}$ and $m_{j}=x_{0}^{b_{0}}\cdots
x_{n}^{b_{n}}$ where $0\leq a_{0},\ldots,a_{n},b_{0},\ldots,b_{n}\leq k$ and
$\sum_{\ell=0}^{n}a_{\ell}=\sum_{\ell=0}^{n}b_{\ell}=k$. Recall that $0^{0}=1$
denotes the empty product, so if $r$ is a nonnegative integer, then $0^{r}=1$
when $r=0$ and $0^{r}=0$ otherwise.

Our choice of $\mathcal{P}^{\prime}$ implies that the $(i,j)$-entry of
$GG^{T}$ is

$\displaystyle\sum_{p\in\mathcal{P}^{\prime}}(m_{i}m_{j})(p)$ $\displaystyle=$
$\displaystyle\sum_{\alpha_{1},\ldots,\alpha_{n}\in\mathbb{F}_{q}}1^{a_{0}+b_{0}}\alpha_{1}^{a_{1}+b_{1}}\alpha_{2}^{a_{2}+b_{2}}\cdots\alpha_{n}^{a_{n}+b_{n}}$
$\displaystyle+\sum_{\alpha_{2},\ldots,\alpha_{n}\in\mathbb{F}_{q}}0^{a_{0}+b_{0}}1^{a_{1}+b_{1}}\alpha_{2}^{a_{2}+b_{2}}\cdots\alpha_{n}^{a_{n}+b_{n}}$
$\displaystyle+\cdots$
$\displaystyle+\sum_{\alpha_{n}\in\mathbb{F}_{q}}\left(0^{a_{0}+b_{0}}\cdots
0^{a_{n-2}+b_{n-2}}\right)1^{a_{n-1}+b_{n-1}}\alpha_{n}^{a_{n}+b_{n}}$
$\displaystyle+\left(0^{a_{0}+b_{0}}\cdots
0^{a_{n-1}+b_{n-1}}\right)1^{a_{n}+b_{n}}.$

For any $i$, we have

$\displaystyle\sum_{\alpha_{i+1},\ldots,\alpha_{n}\in\mathbb{F}_{q}}\left(0^{a_{0}+b_{0}}\cdots
0^{a_{i-1}+b_{i-1}}\right)1^{a_{i}+b_{i}}\alpha_{i+1}^{a_{i+1}+b_{i+1}}\cdots\alpha_{n}^{a_{n}+b_{n}}$
$\displaystyle=$ $\displaystyle\left(0^{a_{0}+b_{0}}\cdots
0^{a_{i-1}+b_{i-1}}\right)1^{a_{i}+b_{i}}\left(\sum_{\alpha_{i+1}\in\mathbb{F}_{q}}\alpha_{i+1}^{a_{i+1}+b_{i+1}}\right)\cdots\left(\sum_{\alpha_{n}\in\mathbb{F}_{q}}\alpha_{n}^{a_{n}+b_{n}}\right).$

Recall from Equation (1) that for any nonnegative integer $r<q-1$, we have
$\sum_{\beta\in\mathbb{F}_{q}}\beta^{r}=0$. For any $i,\ a_{i}+b_{i}\leq 2k$.
Since $2k<q-1$, we see that

$\sum_{p\in\mathcal{P}^{\prime}}(m_{i}m_{j})(p)=\left(0^{a_{0}+b_{0}}\cdots
0^{a_{n-1}+b_{n-1}}\right)1^{a_{n}+b_{n}}=\begin{cases}1&\text{ if
}m_{i}=m_{j}=x_{n}^{k}\\\ 0&\text{ otherwise}\end{cases}.$

We conclude that $GG^{T}$ has a single nonzero entry that is equal to $1$, so
in particular this matrix has rank $1$. The claim about the basis for
$\operatorname{Hull}(C_{n,k}^{q})$ follows from the fact that every entry of
$GG^{T}$ except for the one in the lower-right corner is $0$. ∎

######  Remark 4.2.

The assumption $q>2k+1$ plays an important role in the proof of Theorem 4.1 as
$\sum_{\beta\in\mathbb{F}_{q}}\beta^{q-1}=-1\neq 0$.

######  Corollary 4.3.

Suppose that $n(q-1)-\frac{q-1}{2}<k\leq n(q-1)$ and let $\ell=n(q-1)-k$. Then

$\dim(\operatorname{Hull}(C^{q}_{n,k}))=\dim(C^{q}_{n,\ell})-1=\binom{n+\ell}{\ell}-1.$

###### Proof.

For a linear code $C$, it is clear that
$\operatorname{Hull}(C)=\operatorname{Hull}(C^{\perp})$. The assumption on $k$
implies that either $k=n(q-1)$, or $k\not\equiv 0\pmod{q-1}$. In the first
case, ${C_{n,n(q-1)}^{q}}^{\perp}$ is the $1$-dimensional code spanned by
${\bf 1}$. In Remark 2.8 we note that ${\bf 1}\not\in C_{n,n(q-1)}^{q}$, so
the hull is trivial in this case. In the second case, Theorem 2.7(i) implies
that ${C_{n,k}^{q}}^{\perp}=C_{n,\ell}^{q}$. We see that
$1\leq\ell<\frac{q-1}{2}$, which implies $q>2\ell+1$. Applying Theorem 4.1
completes the proof. ∎

With additional effort, the ideas that go into the proof of Theorem 4.1 can be
adapted to compute the dimension of the hull of $C_{n,k}^{q}$ for a wider
range of parameters.

######  Theorem 4.4.

Let $\frac{q-1}{2}<k<q-1$. Then

$\dim(\operatorname{Hull}(C_{n,k}^{q}))=\dim(C_{n,k}^{q})-(2k+1-(q-1)).$

Moreover, a basis for $\operatorname{Hull}(C_{n,k}^{q})$ is given by
$\\{\operatorname{ev}(m)\\}_{m\in\mathcal{M}}$ where $\mathcal{M}$ is the set
of monomials of degree $k$ in $x_{0},x_{1},\ldots,x_{n}$ except for the
monomials $x_{n-1}^{k-a}x_{n}^{a}$ where $q-1-k\leq a\leq k$.

###### Proof.

We follow the strategy from the proof of Theorem 4.1. Since $k<q$, Lemma 2.1
implies that $C^{q}_{n,k}$ has dimension $\binom{n+k}{k}$. We take the
lexicographic ordering of the $\binom{n+k}{k}$ monomials of degree $k$ in
$x_{0},\ldots,x_{n}$ and write this ordered list of monomials as
$m_{1},\ldots,m_{\binom{n+k}{k}}$. It is clear that
$\operatorname{ev}(m_{1}),\ldots,\operatorname{ev}(m_{\binom{n+k}{k}})$ form
an ordered basis for $C_{n,k}^{q}$. These choices determine a generator matrix
$G$. We will characterize the nonzero entries of $GG^{T}$. The form of this
matrix will make it clear that it has rank $2k+1-(q-1)$, and moreover, will
make it clear which monomials of degree $k$ correspond to codewords of
$C_{n,k}^{q}$ that also lie in ${C_{n,k}^{q}}^{\perp}$.

Suppose $m_{i}=x_{0}^{a_{0}}\cdots x_{n}^{a_{n}}$ and
$m_{j}=x_{0}^{b_{0}}\cdots x_{n}^{b_{n}}$ where $0\leq
a_{0},\ldots,a_{n},b_{0},\ldots,b_{n}\leq k$ and
$\sum_{\ell=0}^{n}a_{\ell}=\sum_{\ell=0}^{n}b_{\ell}=k$. Following the
reasoning from the proof of Theorem 4.1, we see that the $(i,j)$-entry of
$GG^{T}$ is given by

$\sum_{p\in\mathcal{P}^{\prime}}(m_{i}m_{j})(p)=\sum_{i=0}^{n}\left(\left(0^{a_{0}+b_{0}}\cdots
0^{a_{i-1}+b_{i-1}}\right)1^{a_{i}+b_{i}}\left(\sum_{\alpha_{i+1}\in\mathbb{F}_{q}}\alpha_{i+1}^{a_{i+1}+b_{i+1}}\right)\cdots\left(\sum_{\alpha_{n}\in\mathbb{F}_{q}}\alpha_{n}^{a_{n}+b_{n}}\right)\right).$

Equation (1) implies that $\sum_{\alpha\in\mathbb{F}_{q}}\alpha^{a+b}=0$
unless $a+b$ is positive and $a+b\equiv 0\pmod{q-1}$. In particular, this is
zero unless $a+b\geq q-1$. Since $2k<2(q-1)$, there is at most one $i$ for
which $a_{i}+b_{i}$ is be both positive and divisible by $q-1$. This implies
that for any $i\leq n-2$,

$\left(0^{a_{0}+b_{0}}\cdots
0^{a_{i-1}+b_{i-1}}\right)1^{a_{i}+b_{i}}\left(\sum_{\alpha_{i+1}\in\mathbb{F}_{q}}\alpha_{i+1}^{a_{i+1}+b_{i+1}}\right)\cdots\left(\sum_{\alpha_{n}\in\mathbb{F}_{q}}\alpha_{n}^{a_{n}+b_{n}}\right)=0.$

We see that

$\sum_{p\in\mathcal{P}^{\prime}}(m_{i}m_{j})(p)=\left(0^{a_{0}+b_{0}}\cdots
0^{a_{n-2}+b_{n-2}}\right)1^{a_{n-1}+b_{n-1}}\left(\sum_{\alpha_{n}\in\mathbb{F}_{q}}\alpha_{n}^{a_{n}+b_{n}}\right)+0^{a_{0}+b_{0}}\cdots
0^{a_{n-1}+b_{n-1}}1^{a_{n}+b_{n}}.$

As in the end of the proof of Theorem 4.1, we have

$\left(0^{a_{0}+b_{0}}\cdots
0^{a_{n-1}+b_{n-1}}\right)1^{a_{n}+b_{n}}=\begin{cases}1&\text{ if
}m_{i}=m_{j}=x_{n}^{k}\\\ 0&\text{ otherwise}\end{cases}.$

We see that $GG^{T}$ has a $1$ in its lower-right corner, which corresponds to
$m_{i}=m_{j}=x_{n}^{k}$.

We now assume that we are not in this special case, meaning that either
$m_{i}$ or $m_{j}$ is not equal to $x_{n}^{k}$. Therefore,

$\sum_{p\in\mathcal{P}^{\prime}}(m_{i}m_{j})(p)=\left(0^{a_{0}+b_{0}}\cdots
0^{a_{n-2}+b_{n-2}}\right)1^{a_{n-1}+b_{n-1}}\left(\sum_{\alpha_{n}\in\mathbb{F}_{q}}\alpha_{n}^{a_{n}+b_{n}}\right).$

This expression is zero unless
$a_{0},b_{0},a_{1},b_{1},\ldots,a_{n-2},b_{n-2}=0$. In order for this
expression to be nonzero it is also necessary that $a_{n}+b_{n}=q-1$. Suppose
$m_{i}=x_{n-1}^{k-a}x_{n}^{a}$ where $0\leq a\leq k$. Then
$\sum_{p\in\mathcal{P}^{\prime}}(m_{i}m_{j})(p)=0$ if $m_{j}$ is not equal to
$x_{n-1}^{k-(q-1-a)}x_{n}^{q-1-a}$. This is a monomial of degree $k$ if and
only if $k-(q-1-a)\geq 0$, which is equivalent to $a\geq q-1-k$.

Each integer $a$ satisfying $(q-1)-k\leq a\leq k$ gives a nonzero entry of
$GG^{T}$. Together with the entry in the bottom-right corner of $GG^{T}$, this
gives $2k-(q-1)+1+1$ nonzero entries of this matrix. Because we used
lexicographic order for the monomials of degree $k$ when defining $G$, the
nonzero entries of $GG^{T}$ are contained in a submatrix in the lower-right
corner of $GG^{T}$. In this submatrix there are nonzero entries on the main
antidiagonal, and then a single $1$ in the lower-right corner. Since the last
row and column of this matrix also contain nonzero entries corresponding to
$\\{m_{i},m_{j}\\}=\\{x_{n}^{k},x_{n-1}^{k-(q-1-k)}x_{n}^{q-1-k}\\}$, we
conclude that the rank of $GG^{T}$ is $2k-(q-1)+1$.

Every monomial $m$ that is not of the form $x_{n-1}^{k-a}x_{n}^{a}$ where
$(q-1)-k\leq a\leq k$ has the property that the entire row corresponding to
$m$ in $GG^{T}$ is zero. The number of such monomials is the dimension of
$\operatorname{Hull}(C_{n,k}^{q})$, so these monomials form a basis for
$\operatorname{Hull}(C_{n,k}^{q})$. ∎

The proof of the following corollary follows the same strategy we used to
deduce Corollary 4.3 from Theorem 4.1.

######  Corollary 4.5.

Suppose that $(n-1)(q-1)<k<n(q-1)-\frac{q-1}{2}$ and let $\ell=n(q-1)-k$. Then

$\dim(\operatorname{Hull}(C^{q}_{n,k}))=\dim(C^{q}_{n,\ell})-(2\ell+1-(q-1))=\binom{n+\ell}{\ell}-(2\ell+1-(q-1)).$

###### Proof.

By the assumption on $k$, Theorem 2.7(i) implies that
${C_{n,k}^{q}}^{\perp}=C_{n,\ell}^{q}$. We see that $\frac{q-1}{2}<\ell<q-1$.
Applying Theorem 4.4 completes the proof. ∎

We now describe how the results of this section give a different proof of
Theorem 2.9 of Ruano and San-José. First note that if
$k\in\left\\{\frac{q-1}{2},q-1,\frac{3(q-1)}{2}\right\\}$, then Theorem 3.5
and Corollary 3.8 determine $\operatorname{Hull}(C_{2,k}^{q})$.

Now suppose that $1\leq k\leq 2(q-1)$ and $2k\not\equiv 0\pmod{q-1}$. Theorems
4.1 and 4.4 together with Corollaries 4.3 and 4.5 determine
$\dim(\operatorname{Hull}(C_{2,k}^{q}))$. When $\min\\{k,q-k-1\\}=k$, the
formula at the end of Theorem 2.9 is equal to the formula in Theorem 4.1,
$\binom{k+2}{2}-1$. When $\min\\{k,q-k-1\\}=q-1-k$, since

$\binom{k+1}{2}+q-1-k=\binom{k+2}{2}-(2k+1-(q-1)),$

the formula from Theorem 2.9 is equal to the formula in Theorem 4.4.

  * •

In the case where $k<\frac{q-1}{2}$, we see how the basis described in Theorem
2.9 consists of all monomials in $x_{0},x_{1},x_{2}$ of degree $k$ except
$x_{2}^{k}$, matching the result of Theorem 4.1.

  * •

In the case where $k$ satisfies $\frac{q-1}{2}<k<q-1$, we see that the basis
described in Theorem 2.9 consists of all monomials in $x_{0},x_{1},x_{2}$ of
degree $k$ except those of the form $x_{1}^{k-a}x_{2}^{a}$ where
$a\in\\{q-1-k,q-k,\ldots,k\\}$, which matches the set of monomials described
in Theorem 4.4.

This completes our proof of Theorem 2.9.

Ruano and San-José not only describe a basis for
$\operatorname{Hull}(C_{2,k}^{q})$ for each $q$, but more generally, they
describe a basis for $C_{2,k_{1}}^{q}\cap C_{2,k_{2}}^{q}$ where $1\leq
k_{1}<k_{2}\leq 2(q-1)$ [26, Theorem 3.9]. Our results in this paper for $n=2$
do not recover this theorem because we focus only on
$C_{2,k}^{q}\cap{C_{2,k}^{q}}^{\perp}$. We briefly describe how one could try
to prove this more general result using our techniques. In place of
Proposition 2.6, we would want to apply [13, Theorem 2.1]. This would allow us
to determine a basis for $C_{2,k_{1}}^{q}\cap{C_{2,k_{2}}^{q}}^{\perp}$ in
terms of the nonzero entries of $G_{1}G_{2}^{T}$, where $G_{1}$ is a generator
matrix for $C_{2,k_{1}}^{q}$ and $G_{2}$ is a generator matrix for
$C_{2,k_{2}}^{q}$. The entries of this matrix correspond to summing a monomial
of degree $k_{1}+k_{2}$ over a collection of affine representatives of the
points of $\mathbb{P}^{2}(\mathbb{F}_{q})$. The difficult case would be when
both $k_{1}$ and $k_{2}$ are large, for example, when $q\leq k_{1}$. This does
match up with [26, Theorem 3.9] where there is a special case that did not
arise in our analysis of $C_{2,k}^{q}\cap{C_{2,k}^{q}}^{\perp}$. We do not
attempt to carry out this argument here.

We close this section by summarizing the cases where the dimension of
$\operatorname{Hull}(C_{n,k}^{q})$ is not determined by the results of this
paper.

  * •

When $1\leq k<\frac{q-1}{2}$, Theorem 4.1 determines the dimension of
$\operatorname{Hull}(C_{n,k}^{q})$.

  * •

When $n(q-1)-\frac{q-1}{2}<k\leq n(q-1)$, Corollary 4.3 determines the
dimension of $\operatorname{Hull}(C_{n,k}^{q})$.

  * •

When $\frac{q-1}{2}<k<q-1$, Theorem 4.4 determines the dimension of
$\operatorname{Hull}(C_{n,k}^{q})$.

  * •

When $(n-1)(q-1)<k<n(q-1)-\frac{q-1}{2}$, Corollary 4.5 determines the
dimension of $\operatorname{Hull}(C_{n,k}^{q})$.

  * •

When $1\leq k\leq\frac{n(q-1)}{2}$ and $2k\equiv 0\pmod{q-1}$, Theorem 3.5
determines the dimension of $\operatorname{Hull}(C_{n,k}^{q})$.

  * •

When $\frac{n(q-1)}{2}\leq k\leq n(q-1)$ and $2k\equiv 0\pmod{q-1}$ but
$k\not\equiv 0\pmod{q-1}$, Corollary 3.8 determines the dimension of
$\operatorname{Hull}(C_{n,k}^{q})$.

In all other cases with $1\leq k<n(q-1)$, Theorem 3.5 implies that
$C_{n,k}^{q}$ is not self-orthogonal and Theorem 3.10 implies that
$C_{n,k}^{q}$ is not LCD. Therefore,
$1\leq\dim(\operatorname{Hull}(C_{n,k}^{q}))<\dim(C_{n,k}^{q})$, but we do not
know the precise value of $\dim(\operatorname{Hull}(C_{n,k}^{q}))$.

A natural next case to consider is when $k$ satisfies
$q-1<k<\frac{3(q-1)}{2}$. It seems likely that one could carry out an analysis
similar to the one given in the proof of Theorem 4.4, but the details would be
more complicated. This is the kind of thing that would be necessary in order
to prove an analogue of Theorem 2.9 for projective Reed-Muller codes
$C_{3,k}^{q}$ corresponding to surfaces in $\mathbb{P}^{3}$. Investigating
this further could be an interesting problem for future work.

### Acknowledgments

We thank Diego Ruano and Rodrigo San-José for helpful comments. N. Kaplan was
supported by NSF Grant DMS 2154223. J.-L. Kim was supported by the National
Research Foundation of Korea (NRF) Grant funded by the Korean government
(NRF-2019R1A2C1088676).

## References

  * [1] S. E. Anderson, E. Camps-Moreno, H. H. López, G. L. Matthews, D. Ruano, and I. Soprunov, Relative hulls and quantum codes, IEEE Trans. Inform. Theory 70 (2024), no. 5, 3190-3201.
  * [2] P. Beelen, M. Datta, and S. Ghorpade, Maximum number of common zeros of homogeneous polynomials over finite fields. Proc. Amer. Math. Soc. 146 (2018), no. 4, 1451-1468.
  * [3] P. Beelen, M. Datta, and S. Ghorpade, A combinatorial approach to the number of solutions of systems of homogeneous polynomial equations over finite fields. Mosc. Math. J. 22 (2022), no. 4, 565-593.
  * [4] T. P. Berger, Automorphism groups of homogeneous and projective Reed-Muller codes, IEEE Trans. Inform. Theory 48 (2002), no. 5, 1035-1045.
  * [5] B. Chen, S. Ling, and H. Liu, Hulls of Reed-Solomon codes via algebraic geometry codes. IEEE Trans. Inform. Theory 69 (2023), no. 2, 1005-1014.
  * [6] P. Delsarte, J. M, Goethals, and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives, Inform. Contr., vol. 16, pp. 403-442, 1970.
  * [7] S. T. Dougherty, J.-L. Kim, B. Ozkaya, L. Sok, P. Solé, The combinatorics of LCD codes: Linear Programming bound and orthogonal matrices, Int. J. Inf. Coding Theory 4 116-128 (2017).
  * [8] N. D. Elkies, Linear codes and algebraic geometry in higher dimensions. Preprint, 2006.
  * [9] L. Galvez, J.-L. Kim, N. Lee, Y. G. Roe and B. S. Won, Some bounds on binary LCD codes, Cryptogr. Commun. 10 719-728 (2018).
  * [10] Y. Gao, Q. Yue, X. Huang, and J. Zhang, Hulls of generalized Reed-Solomon codes via Goppa codes and their applications to quantum codes. IEEE Trans. Inform. Theory 67 (2021), no. 10, 6619-6626.
  * [11] S. R. Ghorpade and R. Ludhani, On the minimum distance, minimum weight codewords, and the dimension of projective Reed-Muller codes, Adv. Math. Commun. 18 (2024), no. 2, 360-382.
  * [12] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at https://www.codetables.de. Accessed on 2024-06-04.
  * [13] K. Guenda, T. A. Gulliver, S. Jitman, and S. Thipworawimon, Linear $\ell$-intersection pairs of codes and their applications. Des. Codes Cryptogr. 88 (2020), no. 1, 133-152.
  * [14] K. Guenda, S. Jitman, T. A. Gulliver, Constructions of good entanglement-assisted quantum error correcting codes, Des. Codes and Cryptogr. 86, 121-136 (2018).
  * [15] W. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003.
  * [16] N. Kaplan, Weight enumerators of Reed-Muller codes from cubic curves and their duals, 16th International Conference “Arithmetic, Geometry, Cryptography, and Coding Theory”, June 19-23, 2017, Contemporary Math., 722, 59-78.
  * [17] T. Kasami, S. Lin, and W. W. Peterson, Polynomial codes, IEEE Trans. Inform. Theory IT-14 (1968), 807-814.
  * [18] G. Lachaud, Projective Reed-Muller codes. In: Coding Theory and Applications (Cachan, 1986). Lecture Notes in Computer Science, vol. 311, pp. 125-129. Springer, Berlin (1988).
  * [19] G. Lachaud, The parameters of projective Reed-Muller codes. Discrete Math. 81(2):217-221, 1990.
  * [20] J. S. Leon, V. Pless, N. J. A. Sloane, Self-dual codes over $GF(5)$, J. Combin. Theory, Ser. A, 32, 178-194 (1982).
  * [21] F. MacWilliams and N. Sloane, The Theory of Error Correcting Codes, North-Holland, London, 1977.
  * [22] J. L. Massey, Reversible codes, Inf. Control 7 (3) 369-380 (1964).
  * [23] J. L. Massey, Linear codes with complementary duals, Discrete Math 106-107 337–342 (1992).
  * [24] D.J. Mercier and R. Rolland, Polynômes homogènes qui s’annulent sur l’espace projectif $\mathbb{P}^{n}(\mathbb{F}_{q})$. J. Pure Appl. Algebra 124 (1998), no. 1–3, 227-240.
  * [25] V. Pless, Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., New York, 1998.
  * [26] D. Ruano and R. San-José, Hulls of projective Reed-Muller codes over the projective plane. (2024) 28 pp. https://arxiv.org/abs/2312.13921.
  * [27] D. Ruano and R. San-José, The hull variation problem for projective Reed-Muller codes and quantum error-correcting codes. (2024) 12 pp.
https://arxiv.org/abs/2312.15308.

  * [28] A. B. Sørensen, Projective Reed-Muller codes. IEEE Trans. Inform. Theory, 37(6):1567-1576, 1991\.
  * [29] A. B. Sørensen, A note on a gap in the proof of the minimum distance for Projective Reed-Muller codes. (2023) 4 pp. https://arxiv.org/abs/2310.03574.


# GRASP EARTH: Intuitive Software for Discovering Changes on the Planet

Waku Hatakeyama
Ridge-i Inc.
<EMAIL_ADDRESS>
&Shirou Kawakita
Ridge-i Inc.
<EMAIL_ADDRESS>
&Ryohei Izawa
Ridge-i Inc.
<EMAIL_ADDRESS>
&Masanari Kimura
Ridge-i Inc.
<EMAIL_ADDRESS>
###### Abstract

Detecting changes on the Earth, such as urban development, deforestation, or
natural disaster, is one of the research fields that is attracting a great
deal of attention. One promising tool to solve these problems is satellite
imagery. However, satellite images require huge amount of storage, therefore
users are required to set Area of Interests first, which was not suitable for
detecting potential areas for disaster or development. To tackle with this
problem, we develop the novel tool, namely GRASP EARTH, which is the simple
change detection application based on Google Earth Engine. GRASP EARTH allows
us to handle satellite imagery easily and it has used for disaster monitoring
and urban development monitoring.

##  1 Introduction

GRASP EARTH is a series of applications which are developed on Google Earth
Engine (GEE) (Gorelick et al., 2017). GEE was launched on 2010 and it has been
served as a cloud computing platform for satellite images. Recently, a number
of applications ranging from deforestation monitoring to disaster monitoring
are created on this platform (Amani et al., 2020). Data availability and
integrated code developing tool are the main reasons why a number of
applications have been created. Among all the applications, Landsat and
Sentinel are the most used data (Amani et al., 2020). Sentinel-1 (Torres et
al., 2012) and Sentinel-2 (Drusch et al., 2012) can acquire Synthetic Aperture
Radar (SAR) images and optical images for each and they show relatively high
resolution among the freely available images. Due to their plenty archived
data, now users are ready for conducting not only single-time analysis but
also time-series analysis.

By utilizing GEE, we developed a family of web application, namely "GRASP
EARTH". GRASP EARTH consists of several applications which combine
comprehensive change detection engine and effective visualizing interface.

###  1.1 Optical and SAR images

Now, the number of satellite data which we can access to has been increasing.
Among those sensors, optical data and Synthetic Aperture Radar (SAR) data have
been frequently used because of its applicability. Optical satellites observe
the reflected sun light from the surface of the Earth. Typical optical sensors
can detect multiple spectral bands which range from about
$400\text{\,}\mathrm{nm}$ to $1000\text{\,}\mathrm{nm}$. Since the vegetation
tends to have a unique spectral profile in infra-red band, optical data is
widely used for precision agriculture and deforestation monitoring in the
tropical rain forests. For example, Hansen et al. (2013) evaluated global
forest change between 2000 and 2012 using 30m resolution optical images.

While optical satellites use the reflected light from Sun, SAR satellites emit
microwave by themselves and observe the reflected signals after interacting
with the surface of the Earth. Since the sensor uses a wavelength ranging from
centimeter to meter, which can see through clouds, SAR satellites can observe
regardless of the weather. Typically, the more number of artifacts exist in
the place, the larger the intensity of returned signals become (Matsuoka &
Yamazaki, 2004). For example, the intensity of the returned signal of the
urban area is larger than that of forest area. Another example of SAR data is
that large part of its signal reflect on the surface of the water, therefore
the returned signals become less when the land is covered with water. This
feature is applied for the flood detection (Shahabi et al., 2020).

##  2 Overview of GRASP EARTH

GRASP EARTH consists of several applications which focus on detecting changes
in different targets.

GRASP EARTH Building111https://ridgei.users.earthengine.app/view/grasp-earth-
building-en is one of the applications which based on Sentinel-1 (SAR
satellite). In this application, backscatter coefficient is statistically
processed and significantly changed areas are highlighted. Therefore, users
can easily detect the area where development is progressing. This information
can be used for development plan in urban areas. In addition, time-series
transition graph can be drawn and users can recognize when the change
occurred.

Overview of the algorithm is as follows: Let $\bm{A}_{\text{c, dateX}}$ and
$\bm{A}_{\text{d, dateX}}$ is sampled areas where new artifacts were
constructed and destructed for each. And dateX means assigned date1 or date2
on control panel.

$\displaystyle\text{threshold}_{\text{blue}}$
$\displaystyle=F_{\text{otsu}}(\bm{A}_{\text{c, date2}}-\bm{A}_{\text{c,
date1}})$ (1) $\displaystyle\text{threshold}_{\text{red}}$
$\displaystyle=F_{\text{otsu}}(\bm{A}_{\text{d, date2}}-\bm{A}_{\text{d,
date1}})$ (2) Blue part
$\displaystyle=\bm{I}_{\text{date2}}-\bm{I}_{\text{date1}}\geq\text{threshold}_{\text{blue}}$
(3) Red part
$\displaystyle=\bm{I}_{\text{date2}}-\bm{I}_{\text{date1}}\leq\text{threshold}_{\text{red}}$
(4)

where, Blue part and Red part are blue area and red area in GRASP EARTH
Building, $F_{\text{otsu}}$ is Otsu thresholding method (Otsu, 1979).

GRASP EARTH Color222https://ridgei.users.earthengine.app/view/grasp-earth-
color-en is Sentine-2 (optical satellite) based application which enables
users to compare two different dated RGB images at the same area. Optical
satellites often suffer from the effect of clouds. To tackle with this
problem, we developed a method to create cloudless images using several images
taken in different dates. First, we collect several images between two weeks
before and two weeks after the assigned date. As a preprocessing, pixels which
contain clouds are removed for each image. Lastly, median filter is applied
along the time direction.

Overview of the algorithm is as follows:

$\displaystyle\bm{I}_{\text{out}}=F_{\text{median}}(\bm{I}\in\mathbb{R}^{d}\otimes\bm{M}_{\text{cloud}}\in\mathbb{R}^{d})$
(5)

where, $I_{\text{out}}$ is the output, $F_{\text{median}}$ is the median
filter, $I$ is the input image, $M_{\text{cloud}}$ is the cloud mask and
$\otimes$ is the operations of mask.

GRASP EARTH Pumice viewer and GRASP EARTH Pumice detector are the derived
version of GRASP EARTH Color. In mid-August, Fukutokuokanoba undersea volcano
erupted and generated a large amount of pumice. The pumice raft reached the
coast of Okinawa, Japan on October 2021, which have plagued the fishing,
tourism and industries there. Dedicated visualizer and detectors, namely GRASP
EARTH Pumice viewer333https://ridgei.users.earthengine.app/view/pumice-viewer-
en and GRASP EARTH Pumice
detector444https://ridgei.users.earthengine.app/view/pumice-detector-en were
developed. Similar to GRASP EARTH Color, Pumice viewer separates windows into
two and shows two different RGB images taken by Sentinel-2. Default area
focuses on where the pumice rafts are easily detected, but users can see other
areas without defining AoI. GRASP EARTH Pumice detector was also developed. In
this application, as shown in eq.6, first Normalized Difference Water Index
(NDWI) is calculated to eliminate sea area. Since the brightness value and
shapes of floating pumice might change, we adapted simple Otsu thresholding
method and it is set as default value.

Overview of the algorithm is as follows: Let $A_{\text{p}}$ is sampled pumice
area, $A_{\text{np}}$ is not sampled pumice area.

threshold $\displaystyle=F_{\text{otsu}}(F_{\text{ndwi}}(A_{\text{p}})\cup
F_{\text{ndwi}}(A_{\text{np}}))$ (6) $\displaystyle\bm{I}_{\text{pumice}}$
$\displaystyle=(\bm{I}\in\mathbb{R}^{d}<\text{threshold})\otimes\bm{M}_{\text{cloud}}\in\mathbb{R}^{d}\otimes\bm{M}_{\text{land}}\in\mathbb{R}^{d}$
(7)

where, $I_{\text{out}}$ is the output, $F_{\text{median}}$ is the median
filter, $I$ is the input image, $M_{\text{cloud}}$ is the cloud mask,
$M_{\text{cloud}}$ is the land mask and $\otimes$ is the operation of mask.

Default value was calculated by sampling about a hundred of pumice pixels and
sea pixels of images over a few days on October 2021, and applied Otsu
thresholding method after cloud masking so that clouds are not misidentified
as pumice. Simple but easily understandable user interface was a key factor of
applying for actual business. Detailed explanation is written in Appendix.

As shown in left picture of Figure 1, satellite data users have conventionally
been required to set their area of interests (AoI) and specific time of
observation before buying or searching satellite images. There are several
drawbacks in this flow. For instance, when we conduct a disaster monitoring,
AoI is not usually set at the beginning. Moreover, illegal deforestation and
the other environmental crises also occur everywhere in the globe. GRASP EARTH
is designed to notice this kind of unpredictable events.

Figure 1: Comparison between the conventional applications and GRASP EARTH.
Conventional applications needed to select the AoI, as shown in left picture,
before analysis. On the other hand, GRASP EARTH helps users to find the AoI.

###  2.1 How to use GRASP EARTH

Figure 2: Left picture shows the screenshot of GRASP EARTH Building and right
picture shows the screenshot of GRASP EARTH Color

Left picture of Figure 2 shows the screenshot of GRASP EARTH Building looking
at Tokyo bay, Japan. There are a number of blue areas and red areas drawn on
the Google map aerial image. Users can assign two different dates on the left
control panel. Blue area shows the place where the value of backscatter
coefficient increases, which means the artifacts are being built in urban
area, while red area shows the place where the value of backscatter
coefficient decreases, which means vice versa. Users can also draw a point or
a polygon on the map. After drawing, the graph of time-series average of
backscatter coefficient over the drawn area comes out, which enables users to
notice when the changes happened.

After identifying characteristics of changes around the world, users can check
RGB images by using GRASP EARTH Color. RGB images are created from Sentinel-2
observation. Right picture of Figure 2 shows the screenshot of GRASP EARTH
Color. As GRASP EARTH Building, users can assign two different dates on the
left control panel. Main window is split into two parts by movable splitter.
The images of date1 and date2 is displayed on left side and right side of the
window for each.

##  3 Examples of GRASP EARTH usage

GRASP EARTH Building enabled users to estimate the effect of natural disaster.
On May 2021, Taiwan experienced severe drought. During this period, several
dams in Taiwan were suffered from low level of water storage. By using GRASP
EARTH Building, users can find the dams which have low levels of water. Figure
3 shows the screenshot of GRASP EARTH Building which shows South Taiwan. In
this scenario, SAR images taken on January 2021 and May 2021 are processed.
There are mainly three blue areas. Backscatter coefficient of water is lower
than that of sand or mud, therefore, those dried areas are colored with blue.

Bottom part of Figure 3 shows the screenshot of Zengwen dam located in South
Taiwan. The north part of dam dried up on May 2021. Combining GRASP EARTH
Building and GRASP EARTH Color, users can find and understand the
environmental issue all over the world.

Conventional process of finding such an issue starts defining the AoI where
drought occurred and analyze data. However, when we face with the natural
disaster, it is difficult to define AoI first. GRASP EARTH enables users to
find the source of problems without defining AoI.

Figure 3: Top picture is the screenshot of GRASP EARTH Building which shows
South Taiwan. Sentinel-1 images of January 2021 and May 2021 are compared.
Several blue areas show where the dam dried up during the period. Bottom
picture show the screenshot of GRASP EARTH Color which zoom in to Zengwen dam
in South Taiwan on January 2021 and May 2021. North area of dam seems to be
suffered from drought.

##  4 Related works

There are several existing change detection applications using satellite data
which have user interfaces similar to our work (Kolodiy & Pidlypna, 2020;
Poortinga et al., 2018; Scheip & Wegmann, 2021; Arévalo et al., 2020; Kennedy
et al., 2018). There are applications such as QGIS
555https://qgis.org/en/site/index.html and Monteverdi
666https://apollomapping.com/blog/free-for-all-monteverdi as viewers for
satellite image data, and for change detection, there is Orfeo ToolBox
(Grizonnet et al., 2017), a satellite image processing library that provides
algorithms that can be used in those applications. ERDAS IMAGINE
777https://www.hexagongeospatial.com/ja-jp/products/power-portfolio/erdas-
imagine/erdas-imagine-remote-sensing-software-package also provides many types
of change detection tools. Since those tools are native applications that run
offline, it requires a large amount of optical and SAR image data to be
downloaded beforehand in order to analyze a large area.

Since the GEE was launched in 2010, it has been able to analyze a wide range
of satellite image data at high speed. Hansen et al. (2013) mapped global
deforestation and increase, and Hird et al. (2017) conducted a wetland
analysis of a large area of Alberta. Another change detection applications
with viewers are implemented on GEE (Poortinga et al., 2018; Scheip & Wegmann,
2021; Arévalo et al., 2020; Kennedy et al., 2018) and those applications
visualize changes in multiple bands such as NDVI, SWIR1, etc.

There are also several change detection applications with viewers on other
platforms such as Land Viewer (Kolodiy & Pidlypna, 2020) and Tellus-DEUCE, an
add-in for Tellus-OS 888https://www.tellusxdp.com/en-us/os/. These
applications extract changes after selecting the area to be investigated and
visualize the changes.

Table 1: Comparison between GRASP EARTH and existing applications. Unit is "unit of time period", w/o AoI is "without Area of Interests", Domain-agnostic is whether the application focus on the specific domain. | Unit | w/o AoI | Optic | SAR | Domain-agnostic
---|---|---|---|---|---
GRASP EARTH | Date |  |  |  |
LT-GEE Kennedy et al. (2018) | Date |  |  | – |
visualize-ccdc (Arévalo et al., 2020) | Date |  |  | – |
HazMapper (Scheip & Wegmann, 2021) | Date |  |  | – | –
EcoDash (Poortinga et al., 2018) | Year |  |  | – | –
Land Viewer (Kolodiy & Pidlypna, 2020) | Date | – |  | – |
Tellus-DEUCE 888 | Date | – |  | – |

Although change detection applications on GEE do not require the selection of
the area to be surveyed, there are issues such as the limited period of time
over which changes can be visualized and the observation targets are limited
to specific domains. Change detection applications on other platforms require
the user to specify the area to be surveyed. GRASP EARTH is an application
that visualizes changes in almost real time on a viewer that does not require
the selection of pre-defined areas. Moreover, GRASP EARTH offers SAR based
change detection algorithm. Therefore, it can be used even the surface of the
Earth is covered with clouds.

##  5 Conclusion and discussion

Due to its low calculation cost, GRASP EARTH enables users to notice changes
around the world with out setting AoI. Moreover, users can access to the
latest data (up to two days before today). Though simple algorithms are
implemented on the applications, they have used for tackling several problems.
If users want to detect pre-defined changes such as detecting the changes in
the number of ships or cars, current version of GRASP EARTH should be
improved. In this case, deep learning based change detection needs to be
integrated. Since GEE platform offers Google Cloud Storage connection,
integration with deep learning is easily achieved.

We can consider future works as follows. First, we can combine the method used
in GRASP EARTH and the deep learning method. If this method is implemented,
users can define AoI and monitoring duration quickly and proceed to dedicated
analysis, which lead to reduce cost of purchasing satellite images and
calculation time. Moreover, we can also consider to utilize text information
on social network service, which can be also help detecting early symptoms for
changes. Such multi-modal analyses may lead to quick response to the natural
disaster.

## References

  * Amani et al. (2020) Meisam Amani, Arsalan Ghorbanian, Seyed Ali Ahmadi, Mohammad Kakooei, Armin Moghimi, S Mohammad Mirmazloumi, Sayyed Hamed Alizadeh Moghaddam, Sahel Mahdavi, Masoud Ghahremanloo, Saeid Parsian, et al.  Google earth engine cloud computing platform for remote sensing big data applications: A comprehensive review.  _IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing_ , 13:5326–5350, 2020.
  * Arévalo et al. (2020) Paulo Arévalo, Eric L Bullock, Curtis E Woodcock, and Pontus Olofsson.  A suite of tools for continuous land change monitoring in google earth engine.  _Frontiers in Climate_ , pp. 26, 2020.
  * Drusch et al. (2012) Matthias Drusch, Umberto Del Bello, Sébastien Carlier, Olivier Colin, Veronica Fernandez, Ferran Gascon, Bianca Hoersch, Claudia Isola, Paolo Laberinti, Philippe Martimort, et al.  Sentinel-2: Esa’s optical high-resolution mission for gmes operational services.  _Remote sensing of Environment_ , 120:25–36, 2012.
  * Gorelick et al. (2017) Noel Gorelick, Matt Hancher, Mike Dixon, Simon Ilyushchenko, David Thau, and Rebecca Moore.  Google earth engine: Planetary-scale geospatial analysis for everyone.  _Remote sensing of Environment_ , 202:18–27, 2017.
  * Grizonnet et al. (2017) Manuel Grizonnet, Julien Michel, Victor Poughon, Jordi Inglada, Mickaël Savinaud, and Rémi Cresson.  Orfeo toolbox: open source processing of remote sensing images.  _Open Geospatial Data, Software and Standards_ , 2(1):1–8, 2017.
  * Hansen et al. (2013) Matthew C Hansen, Peter V Potapov, Rebecca Moore, Matt Hancher, Svetlana A Turubanova, Alexandra Tyukavina, David Thau, Stephen V Stehman, Scott J Goetz, Thomas R Loveland, et al.  High-resolution global maps of 21st-century forest cover change.  _science_ , 342(6160):850–853, 2013.
  * Hird et al. (2017) Jennifer N Hird, Evan R DeLancey, Gregory J McDermid, and Jahan Kariyeva.  Google earth engine, open-access satellite data, and machine learning in support of large-area probabilistic wetland mapping.  _Remote sensing_ , 9(12):1315, 2017.
  * Kennedy et al. (2018) Robert E Kennedy, Zhiqiang Yang, Noel Gorelick, Justin Braaten, Lucas Cavalcante, Warren B Cohen, and Sean Healey.  Implementation of the landtrendr algorithm on google earth engine.  _Remote Sensing_ , 10(5):691, 2018.
  * Kolodiy & Pidlypna (2020) Pavlo Kolodiy and Maryna Pidlypna.  The improvement of the agricultural yields forecasting model using the software product “land viewer”.  _Geomatics and Environmental Engineering_ , 14(1), 2020\.
  * Matsuoka & Yamazaki (2004) Masashi Matsuoka and Fumio Yamazaki.  Use of satellite sar intensity imagery for detecting building areas damaged due to earthquakes.  _Earthquake Spectra_ , 20(3):975–994, 2004.
  * Otsu (1979) Nobuyuki Otsu.  A threshold selection method from gray-level histograms.  _IEEE transactions on systems, man, and cybernetics_ , 9(1):62–66, 1979.
  * Poortinga et al. (2018) Ate Poortinga, Nicholas Clinton, David Saah, Peter Cutter, Farrukh Chishtie, Kel N Markert, Eric R Anderson, Austin Troy, Mark Fenn, Lan Huong Tran, et al.  An operational before-after-control-impact (baci) designed platform for vegetation monitoring at planetary scale.  _Remote Sensing_ , 10(5):760, 2018.
  * Scheip & Wegmann (2021) Corey M Scheip and Karl W Wegmann.  Hazmapper: a global open-source natural hazard mapping application in google earth engine.  _Natural Hazards and Earth System Sciences_ , 21(5):1495–1511, 2021.
  * Shahabi et al. (2020) Himan Shahabi, Ataollah Shirzadi, Kayvan Ghaderi, Ebrahim Omidvar, Nadhir Al-Ansari, John J Clague, Marten Geertsema, Khabat Khosravi, Ata Amini, Sepideh Bahrami, et al.  Flood detection and susceptibility mapping using sentinel-1 remote sensing data and a machine learning approach: Hybrid intelligence of bagging ensemble based on k-nearest neighbor classifier.  _Remote Sensing_ , 12(2):266, 2020.
  * Torres et al. (2012) Ramon Torres, Paul Snoeij, Dirk Geudtner, David Bibby, Malcolm Davidson, Evert Attema, Pierre Potin, BjÖrn Rommen, Nicolas Floury, Mike Brown, et al.  Gmes sentinel-1 mission.  _Remote sensing of environment_ , 120:9–24, 2012.

##  Appendix A Appendix

###  A.1 Additional use case of GRASP EARTH Building 1

Figure 4: Top left picture shows GRASP EARTH Building screenshot of the
Olympic Village in Tokyo, which compares SAR images of January 2016 and
January 2021. Top right picture shows the excerpt of red box in top left
picture. Bottom left picture draws arbitrary AoI and get time series average
of a backscatter coefficient of the area. Bottom right picture shows the graph
excepted from bottom left picture.

GRASP EARTH Building is used for urban development monitoring. Figure 4 shows
the screenshot of GRASP EARTH Building in Tokyo bay area, where the Olympic
village were built from 2017 to 2020. SAR images which were taken in January
2016 and January 2021 are processed and the processed layer is put on the
Google map aerial view. There are several blue dots over the Olympic village,
which means the amount of artifacts has been increased during the period. Time
series signal transition is also available. Users can draw arbitrary shapes by
selecting button from control panel. After drawing the polygon, a graph which
shows the average backscatter coefficient over the drawn area emerges as shown
in bottom left picture of Figure 4. Bottom right picture of Figure 4 shows the
enlarged graph. The average backscatter coefficient increases from September
2016 to March 2017. This signal suggests that the construction started during
this period.

###  A.2 Additional use case of GRASP EARTH Building 2

GRASP EARTH Pumice viewer is shown in Figure 5. Cloudless RGB image creation
method, which is implemented in GRASP EARTH Color, is not implemented in GRASP
EARTH Pumice viewer so that users can detect the exact place of the pumice
raft on the input date. The pumice raft can be seen in the offshore of Okinawa
main island on October 28th, 2021 while the rafts are not seen on November
2nd, 2021.

GRASP EARTH Pumice detector, which is shown in Figure 6 was also used for
checking places of pumice rafts on daily basis. Pumice rafts might emerge
everywhere in the Pacific ocean but its width was only dozens of meters at
that time. Therefore, finding pumice rafts required high resolution satellite
image. GRASP EARTH Pumice detector was created so that it can take over the
arduous task.

Deep Learning based segmentation methods and other pixel based classification
methods are compared but since the shape and the pixel value changed
drastically during the period, we adapted the simple method as described in
Section 2. This application have been used for checking the rough location of
pumice rafts.

Seamless integration of fast satellite images fetching, calculating tools and
visualizer enabled these applications to be widely used from media to local
people. GRASP EARTH Pumice viewer and detector could never been created
without GEE.

Figure 5: Screenshot of GRASP EARTH Pumice viewer. In this application, window
is divided into two and users can compare different two RGB images. The red
box in left picture show the area where pumice rafts are detected. Figure 6:
Screenshot of GRASP EARTH pumice detector. Estimated pumice raft area is
colored in red.