# The minimum distance of a parameterized
code over an even cycle

Eduardo Camps-Moreno  Department of Mathematics, Virginia Tech, Blacksburg, VA
USA<EMAIL_ADDRESS>,  Jorge Neves  University of Coimbra, Department of
Mathematics, CMUC, 3000-143 Coimbra, Portugal<EMAIL_ADDRESS>and  Eliseo
Sarmiento  Escuela Superior de Física y Matemáticas
Instituto Politécnico Nacional
Mexico City, Mexico<EMAIL_ADDRESS>
###### Abstract.

We compute the minimum distance of the parameterized code of order $1$ over an
even cycle.

###### Key words and phrases:

minimum distance, parameterized linear codes

###### 2020 Mathematics Subject Classification:

13P25, 14G50, 14G15, 11T71, 94B27

Partially supported by the Centre for Mathematics of the University of Coimbra
(funded by the Portuguese Government through FCT/MCTES, DOI
10.54499/UIDB/00324/2020). The authors use Macaulay2 [6] in the computations
of examples.

_Data availability_. Data sharing not applicable to this article as no
datasets were generated or analyzed during the current study.

##  1\. Introduction

Defined by Rentería, Simis and Villarreal in [14], and by González and
Rentería in [2], parameterized linear codes are evaluation codes over a
projective toric subset parameterized by a set of Laurent monomials, over a
finite field $\mathbb{F}$. From the start, the case when the exponent vectors
of the Laurent monomials form the incidence matrix of a graph is a case of
major interest. Let us explain this in detail. Let $G$ be a simple graph, with
vertex set $V_{G}=\left\\{1,2,\dots,n\right\\}$ and
$E_{G}=\left\\{e_{1},\dots,e_{s}\right\\}$. Fix a finite field, $\mathbb{F}$,
of order $q$ and, for any
$\mathbf{x}=(x_{1},\dots,x_{n})\in(\mathbb{F}^{*})^{n}$ and any edge
$e_{k}=\left\\{i,j\right\\}\in E_{G}$, denote $e_{k}(\mathbf{x})=x_{i}x_{j}$.
Denote the subset of $\mathbb{P}^{s-1}$ consisting of the points with nonzero
coordinates by $\mathbb{T}^{s-1}$.

######  Definition 1.1.

The _projective toric subset parameterized by $G$_ is

$X=\left\\{(e_{1}(\mathbf{x}):\dots:e_{s}(\mathbf{x}))\in\mathbb{P}^{s-1}:\mathbf{x}\in(\mathbb{F}^{*})^{n}\right\\}\subseteq\mathbb{T}^{s-1}.$

To avoid a the trivial case, we assume throughout this article that
$|\mathbb{F}|=q>2$. Denoting by $S=\mathbb{F}[t_{1},\dots,t_{s}]$ the
polynomial ring with variables in bijection with $E_{G}$ and coefficients in
$\mathbb{F}$ and choosing an ordering of the points of
$X=\left\\{P_{1},\dots,P_{m}\right\\}$, define, for each $d\geq 0$, a linear
map $\operatorname{ev}_{d}\colon S_{d}\to\mathbb{F}^{m}$ given by

$\textstyle
f\mapsto\left(\frac{f}{t_{1}^{d}}(P_{1}),\dots,\frac{f}{t_{1}^{d}}(P_{m})\right).$

######  Definition 1.2.

The image of $\operatorname{ev}_{d}$ is called the parameterized code of order
$d$ over $G$ and $\mathbb{F}$. We denote these linear subspaces by
$C_{X}(d)\subseteq\mathbb{F}^{m}$.

Up to linear equivalence, the codes $C_{X}(d)$ do not depend on the choice of
ordering of the edges of graph nor on the ordering of the points of $X$.

Denote the vanishing ideal of $X$ by $I(X)\subseteq
S=\mathbb{F}[t_{1},\dots,t_{s}]$. It is by now well-known that the properties
of the family of evaluation codes given by $C_{X}(d)$, as $d\geq 0$, tie into
the algebraic properties of the quotient $S/I(X)$. The three basic parameters
of a code $C\subseteq\mathbb{F}^{m}$ are the length ($m$, the dimension of
their ambient space), the dimension and the minimum distance, _i.e._ ,

$\min\left\\{\|\mathbf{w}\|:0\not=\mathbf{w}\in C\right\\}.$

The length of $C_{X}(d)$, $m=|X|$, which is constant as $d\geq 0$, can be
given by the multiplicity degree of $S/I(X)$. An explicit formula for this
parameter is known. If $b_{0}(G)$ denotes the number of connected components
of $G$ and $\gamma$ is the number of those that are non-bipartite, then

(1) $m=|X|=\deg
S/I(X)=\left\\{\begin{array}[]{ll}\frac{1}{2^{\gamma-1}}(q-1)^{n-m+\gamma-1}&\text{if
$\gamma\geq 1$ and $q$ is odd,}\\\ (q-1)^{n-m+\gamma-1}&\text{if $\gamma\geq
1$ and $q$ is even,}\\\ (q-1)^{n-m-1},&\text{if $\gamma=0$}\\\
\end{array}\right.$

(_cf_. [14, Corollary 3.8] and [12, Theorem 3.2]). Concerning the parameter
dimension, from Definition 1.2, it follows that

$\dim_{\mathbb{F}}C_{X}(d)=\dim_{\mathbb{F}}\left(S/I(X)\right)_{d}.$

In other words the dimension function of $C_{X}(d)$ coincides with the Hilbert
function of $S/I(X)$. Unlike the case of the length, no formula holding for a
general $G$ is known for the dimension function. We know of formulas for the
dimension function only in the following cases: _i_) when $X$ coincides with
the torus $\mathbb{T}^{s-1}$, _i.e._ , when $G$ is either a forest or a non-
bipartite unicyclic graph [1, Proposition 2.2]; _ii_) when $G$ is a complete
bipartite graph [3, Theorem 5.2]; _iii_) when $G$ is an even cycle and
$\mathbb{F}$ is a field with $q=3$ elements — _cf_. [11, Theorem 2.8]. On the
other hand, the behaviour of the Hilbert function of $S/I(X)$ also yields
another important piece of information about the family of linear codes
$C_{X}(d)$. Since $S/I(X)$ is a Cohen–Macaulay, dimension $1$ graded ring, we
know that the Hilbert function eventually becomes constant and equal to $m$.
This means that for a certain value of $d$ onward the codes $C_{d}(X)$ are
trivial, as they coincide with their ambient space. This value of $d$ is the
regularity index of $S/I(X)$ or, in this case equivalently, the
Castelnuovo–Mumford regularity of $S/I(X)$. For the past years, several
authors have focused on the computation of the regularity of $S/I(X)$ — _cf._
[3, 5, 10, 12, 8, 7]. When $X$ is equal to $\mathbb{T}^{s-1}$, $I(X)$ is equal
to the complete intersection

$(t_{1}^{q-1}-t_{s}^{q-1},\dots,t_{s-1}^{q-1}-t_{s}^{q-1})$

and, accordingly, $\operatorname{reg}S/I(X)=(s-1)(q-2)$ — _cf_. [4]. If $G$ is
bipartite, $2$-connected and affords a nested ear decomposition, then the
regularity is equal to

$\textstyle\frac{n+\epsilon-3}{2}(q-2),$

where $\epsilon$ denotes the number of even ears — _cf_. [8, Theorem 4.4]. If
$q=3$, the regularity is equal to the maximum cardinality of a subset of edges
that contains no more than half the edges of any Eulerian, even cardinality,
subgraph of $G$ — _cf_. [9, Theorem 4.13]. The regularity is known for a few
more special families of graphs such as complete graphs and complete bipartite
graphs — _cf_. [5] and [3], respectively — however, so far, we know of no
formula for the regularity of $S/I(X)$ that holds for a general graph and
$q>3$.

The minimum distance of $C_{X}(d)$ has remained unknown, for most cases. When
$X$ coincides with the torus and $d<\operatorname{reg}S/I(X)=(q-1)(s-1)$, we
know that the minimum distance of $C_{X}(d)$ is equal to

$(q-1)^{s-(k+2)}(q-1-\ell)$

where $k$ and $\ell$ are such that $d=k(q-2)+\ell$, $k\geq 0$ and
$1\leq\ell\leq q-2$ — _cf_. [15, Theorem 3.5]. This formula can be used to
express the minimum distance for the case when $G$ is a complete bipartite
graph, _cf_. [3]. For no other classes of graphs do we know a formula for the
minimum distance. A complete answer to this question seems, at present, a very
difficult problem.

The purpose of this article is to give a formula for the minimum distance of
$C_{X}(1)$ when $G$ is an even cycle. This result is significant not only
because it provides a closed formula for an unknown parameter, but also
because it lays the groundwork for exploring minimum distances across a wider
range of graph structures. In the next section we describe the corresponding
set $X$ and linear code $C$, together with the length and dimension of the
latter. In Section 3, we state and prove our main result, Theorem 3.1.

##  2\. Preliminaries

###  2.1. The set of points

Let $G=\mathcal{C}_{2k}$ be an even cycle of length $2k\geq 4$. The toric
subset parameterized by $\mathcal{C}_{2k}$ is given by:

(2)
$X=\left\\{(x_{1}x_{2}:x_{2}x_{3}:\dots:x_{2k-1}x_{2k}:x_{2k}x_{1})\in\mathbb{P}^{2k-1}:x_{i}\in\mathbb{F}^{*},1\leq
i\leq 2k\right\\}.$

Using (1) we deduce that $X$ has cardinality equal to $m=(q-1)^{2k-2}$.

###  2.2. The code

Recalling that $S=\mathbb{F}[t_{1},\dots,t_{2k}]$, the code $C_{X}(1)$ is the
image of the map $\operatorname{ev}_{1}\colon S_{1}\to\mathbb{F}^{m}$ given by

$\textstyle
t_{i}\mapsto\left(\frac{t_{i}}{t_{1}}(P_{1}),\dots,\frac{t_{i}}{t_{1}}(P_{m})\right).$

for $i=1,\dots,2k$. For the remainder of this article we will denote this code
by $C$. Since by [12, Theorem 5.9], the vanishing ideal of $X$ is generated by
binomials of degree $\geq 2$, we deduce that

$\dim_{\mathbb{F}}C=\dim_{\mathbb{F}}(S/I(X))_{1}=\dim_{\mathbb{F}}S_{1}=2k.$

Hence $C$ is a code of length $m=(q-1)^{2k-2}$ and dimension $2k$.

###  2.3. Number of zeros of forms

The set $X$ is the image of a map $\mathbb{T}^{2k-1}\to\mathbb{T}^{2k-1}$ that
sends $(x_{1}:\cdots:x_{2k})$ to
$(x_{1}x_{2}:\cdots:x_{2k-1}x_{2k}:x_{2k}x_{1})$. This is a group homomorphism
which, according to [12, Lemma 3.1], has kernel of cardinality $q-1$. Hence,
given a homogeneous polynomial $F\in\mathbb{F}[t_{1},\dots,t_{2k}]$, the
computation of the cardinality of $Z(F)\cap X$ can be achieved by counting the
number of zeros of

$f=F(x_{1}x_{2},\dots,x_{2k-1}x_{2k},x_{2k}x_{1})\in\mathbb{F}[x_{1},\dots,x_{n}]$

on $\mathbb{T}^{2k-1}$ and dividing this number by $(q-1)$. Similarly, the
cardinality of $Z(f)\cap\mathbb{T}^{2k-1}$ is equal to the number of
$(a_{1},\dots,a_{2k})\in(\mathbb{F}^{*})^{2k}$ such that
$f(a_{1},\dots,a_{2k})=0$, divided by $q-1$.

######  Definition 2.1.

Given $f_{1},\dots,f_{\ell}\in\mathbb{F}[x_{1},\dots,x_{n}]$, denote by
$\mathbf{z}(f_{1},\dots,f_{\ell})$ the number of
$(a_{1},\dots,a_{2k})\in(\mathbb{F}^{*})^{2k}$ such that

$f_{1}(a_{1},\dots,a_{2k})=\cdots=f_{\ell}(a_{1},\dots,a_{2k})=0.$

By the previous discussion we get following lemma.

######  Lemma 2.2.

Given $F\in S$, if
$f=F(x_{1}x_{2},\dots,x_{2k-1}x_{2k},x_{2k}x_{1})\in\mathbb{F}[x_{1},\dots,x_{n}]$,
the cardinality of $Z(F)\cap X$ is $\mathbf{z}(f)/(q-1)^{2}$.

##  3\. The result

######  Theorem 3.1.

Let $X\subseteq\mathbb{P}^{2k-1}$ be the toric subset parameterized by a cycle
of length $2k\geq 4$, let $m=|X|=(q-1)^{2k-2}$, and let
$C=C_{X}(1)\subseteq\mathbb{F}^{m}$ be the corresponding evaluation code of
order $1$. Then the minimum distance of $C$ is

$\left\\{\begin{array}[]{ll}(q-1)^{2k-3}(q-2),&\text{if $k=4$ and $q>3$, or
$k\geq 5$,}\\\ \frac{(q-1)^{2k}-q^{k}(q-2)-1}{q(q-1)},&\text{if $k=2$, or
$k=3$, or $k=4$ and $q=3$}.\end{array}\right.$

Since $C$ is the subspace of $\mathbb{F}^{m}$ obtained by evaluating forms of
degree one at the points of $X$, to prove Theorem 3.1, we need to show that

$\max_{F\in S_{1}}|Z(F)\cap
X|=\left\\{\begin{array}[]{ll}(q-1)^{2k-3},&\text{if $k=4$ and $q>3$, or
$k\geq 5$,}\\\ \frac{(q-1)^{2k-1}+q^{k}(q-2)+1}{q(q-1)},&\text{if $k=2$, or
$k=3$, or $k=4$ and $q=3$}.\end{array}\right.$

To estimate $|Z(F)\cap X|$, with $F\in S_{1}$, we will distinguish between two
cases, corresponding to Propositions 3.2 and 3.4, below.

######  Proposition 3.2.

If
$F=\alpha_{1}t_{1}+\cdots+\alpha_{2k}t_{2k}\in\mathbb{F}[t_{1},\dots,t_{s}]$
is a nonzero linear form such that $\alpha_{i}=0$, for some $i$, then

$|Z(F)\cap X|\leq(q-1)^{2k-3}$

and equality is attained, for example, for $F=t_{1}-t_{2}$.

###### Proof.

Let $f=F(x_{1}x_{2},\dots,x_{2k-1}x_{2k},x_{2k}x_{1})$. By our assumptions
there exists $i$ such that $f=h+\beta x_{i}x_{j}$ with $\beta\not=0$ and
$h\in\mathbb{F}[x_{1},\dots,\widehat{x_{i}},\dots,x_{2k}]$. This implies that
if an element of $(\mathbb{F}^{*})^{2k}$ is a zero of $f$ then $h$ does not
vanish and the $i$th coordinate is determined by the value of the remaining
coordinates. In other words,

$\mathbf{z}(f)\leq(q-1)^{2k-1},$

which, by Lemma 2.2, says that $|Z(F)\cap X|\leq(q-1)^{2k-3}$. When
$F=t_{1}-t_{2}$ we get $f=x_{1}x_{2}-x_{2}x_{3}$ and, since $x_{1}x_{2}$ does
not vanish on any element of $(\mathbb{F}^{*})^{2k}$,

$\mathbf{z}(f)=(q-1)^{2k-1}\implies|Z(F)\cap X|=(q-1)^{2k-3}.\qed$

To deal with the case when all $\alpha_{i}$ are nonzero, we will need the next
lemma.

######  Lemma 3.3.

Let $2\leq r\leq 2k$. If
$g=\sum_{i=1}^{r-1}\beta_{i}x_{i}x_{i+1}\in\mathbb{F}[x_{1},\dots,x_{2k}]$ is
such that $\beta_{1},\dots,\beta_{r-1}$ are nonzero, then

(3) $\mathbf{z}(g)=q^{-1}[(q-1)^{r}+(-1)^{r-1}(q-1)^{2}](q-1)^{2k-r}.$

###### Proof.

Let us use induction on $r$. If $r=2$ then $g=\beta_{1}x_{1}x_{2}$, with
$\beta_{1}\not=0$, and hence $\mathbf{z}_{2}(g)=0$, which agrees with the
formula given. Fix $r<2k$ and assume that the statement holds for $r$. Given

$\textstyle
g=\sum_{i=1}^{r}\beta_{i}x_{i}x_{i+1}\in\mathbb{F}[x_{1},\dots,x_{2k}]$

with $\beta_{1},\dots,\beta_{r}\not=0$, let us write
$g=h+\beta_{r}x_{r}x_{r+1}$, where

$\textstyle h=\sum_{i=1}^{r-1}\beta_{i}x_{i}x_{i+1}.$

Now, an element of $(\mathbb{F}^{*})^{2k}$ is a zero of $g$ if and only if it
not a zero of $h$ and in this case its $r+1$ coordinate is determined by
$0=h+\beta_{r}x_{r}x_{r+1}$. Hence

$\mathbf{z}(g)=(q-1)^{2k-1}-\mathbf{z}(h)(q-1)^{-1},$

which, by induction is equal to

$\begin{array}[]{l}(q-1)^{2k-1}-q^{-1}[(q-1)^{r}+(-1)^{r-1}(q-1)^{2}](q-1)^{2k-r-1}\\\
=q^{-1}[q(q-1)^{r}-(q-1)^{r}-(-1)^{r-1}(q-1)^{2}](q-1)^{2k-r-1}\\\
=q^{-1}[(q-1)^{r+1}+(-1)^{r}(q-1)^{2}](q-1)^{2k-r-1}.\qed\end{array}$

######  Proposition 3.4.

If
$F=\alpha_{1}t_{1}+\cdots+\alpha_{2k}t_{2k}\in\mathbb{F}[t_{1},\dots,t_{s}]$
is such that all $\alpha_{i}$ are nonzero, then

$|Z(F)\cap X|\leq\frac{(q-1)^{2k-1}+q^{k}(q-2)+1}{q(q-1)},$

with equality if and only if
$\alpha_{1}\alpha_{3}\cdots\alpha_{2k-1}=(-1)^{k}\alpha_{2}\alpha_{4}\cdots\alpha_{2k}$.

###### Proof.

Let $f=F(x_{1}x_{2},\dots,x_{2k-1}x_{2k},x_{2k}x_{1})$. By Lemma 2.2, we need
to show

(4) $\mathbf{z}(f)\leq q^{-1}\bigl{[}(q-1)^{2k}+q^{k}(q-2)(q-1)+q-1\bigr{]}$

with equality if and only if
$\alpha_{1}\alpha_{3}\cdots\alpha_{2k-1}=(-1)^{k}\alpha_{2}\alpha_{4}\cdots\alpha_{2k}$.
We will argue by induction on $k\geq 2$. Assume $k=2$, so that

$\begin{array}[]{l}f=\alpha_{1}x_{1}x_{2}+\alpha_{2}x_{2}x_{3}+\alpha_{3}x_{3}x_{4}+\alpha_{4}x_{4}x_{1}\\\
\phantom{f}=\alpha_{1}x_{1}x_{2}+\alpha_{2}x_{2}x_{3}+(\alpha_{3}x_{3}+\alpha_{4}x_{1})x_{4}\\\
\phantom{f}=g+hx_{4}\end{array}$

where we are denoting $g=\alpha_{1}x_{1}x_{2}+\alpha_{2}x_{2}x_{3}$ and
$h=\alpha_{3}x_{3}+\alpha_{4}x_{1}$. If we let $x_{1},x_{2},x_{3}$ vary in
$\mathbb{F}^{*}$, a zero of $f$ has $x_{4}\in\mathbb{F}^{*}$ determined by the
values of $g$ and $h$, unless both quantities are zero. Thus, using Lemma 3.3,

$\begin{array}[]{l}\mathbf{z}(f)=\mathbf{z}(g,h)+(q-1)^{3}-\mathbf{z}(g)(q-1)^{-1}-\mathbf{z}(h)(q-1)^{-1}+\mathbf{z}(g,h)(q-1)^{-1}\\\
\phantom{\mathbf{z}(f)}=(q-1)^{-1}q\mathbf{z}(g,h)+(q-1)^{3}-\mathbf{z}(g)(q-1)^{-1}-\mathbf{z}(h)(q-1)^{-1}\\\
\phantom{\mathbf{z}(f)}=(q-1)^{-1}q\mathbf{z}(g,h)+(q-1)^{3}-q^{-1}[(q-1)^{3}+(q-1)^{2}]-(q-1)^{2}\\\
\phantom{\mathbf{z}(f)}=(q-1)^{-1}q\mathbf{z}(g,h)+(q-1)^{3}-2(q-1)^{2}\\\
\phantom{\mathbf{z}(f)}=(q-1)^{-1}q\mathbf{z}((\alpha_{1}-\alpha_{2}\alpha_{4}\alpha_{3}^{-1})x_{1}x_{2},\alpha_{3}x_{3}+\alpha_{4}x_{4})+(q-1)^{3}-2(q-1)^{2}\\\
\phantom{\mathbf{z}(f)}\leq q(q-1)^{2}+(q-1)^{3}-2(q-1)^{2}\\\
\phantom{\mathbf{z}(f)}=(q-1)^{2}[2q-3]\end{array}$

which coincides with (4) for $k=2$. Moreover, equality above holds if and only
if

$\alpha_{1}-\alpha_{2}\alpha_{4}\alpha_{3}^{-1}=0\iff\alpha_{1}\alpha_{3}=(-1)^{2}\alpha_{2}\alpha_{4}.$

Consider the induction step. Let $f\in\mathbb{F}[x_{1},\dots,x_{2k+2}]$ be

$\begin{array}[]{l}f=\alpha_{1}x_{1}x_{2}+\cdots+\alpha_{2k}x_{2k}x_{2k+1}+\alpha_{2k+1}x_{2k+1}x_{2k+2}+\alpha_{2k+2}x_{2k+2}x_{1}\\\
\phantom{f}=g+hx_{2k+2},\end{array}$

where we $g=\alpha_{1}x_{1}x_{2}+\cdots+\alpha_{2k}x_{2k}x_{2k+1}$ and
$h=\alpha_{2k+1}x_{2k+1}+\alpha_{2k+2}x_{1}$. Arguing as in the case of $k=2$,

(5)
$\mathbf{z}(f)=(q-1)^{-1}q\mathbf{z}(g,h)+(q-1)^{2k+1}-\mathbf{z}(g)(q-1)^{-1}-\mathbf{z}(h)(q-1)^{-1}.$

Since $\mathbf{z}(g,h)=\mathbf{z}(f^{\prime},h)$, where

$f^{\prime}=\alpha_{1}x_{1}x_{2}+\cdots+\alpha_{2k-1}x_{2k-2}x_{2k-1}-\alpha_{2k}\alpha_{2k+2}\alpha_{2k+1}^{-1}x_{2k}x_{1},$

by induction,

$\mathbf{z}(g,h)\leq q^{-1}[(q-1)^{2k}+q^{k}(q-2)(q-1)+(q-1)](q-1)$

with equality if and only if

(6)
$\begin{array}[]{c}\alpha_{1}\alpha_{3}\cdots\alpha_{2k-1}=(-1)^{k}\alpha_{2}\alpha_{4}\cdots\alpha_{2k-2}[-\alpha_{2k}\alpha_{2k+2}\alpha_{2k+1}^{-1}]\\\
\iff\alpha_{1}\alpha_{3}\cdots\alpha_{2k-1}\alpha_{2k+1}=(-1)^{k+1}\alpha_{2}\alpha_{4}\cdots\alpha_{2k-2}\alpha_{2k}\alpha_{2k+2}.\end{array}$

Using this, we deduce that

$\begin{array}[]{l}(q-1)^{-1}\bigl{[}q\mathbf{z}(g,h)-\mathbf{z}(h)\bigr{]}\leq(q-1)^{2k}+q^{k}(q-2)(q-1)+(q-1)-(q-1)^{2k}\\\
\phantom{(q-1)^{-1}\bigl{[}q\mathbf{z}(g,h)-\mathbf{z}(h)\bigr{]}}=q^{k}(q-2)(q-1)+(q-1)\end{array}$

Together with Lemma 3.3, this yields from (5)

$\begin{array}[]{l}\mathbf{z}(f)\leq
q^{k}(q-2)(q-1)+(q-1)+(q-1)^{2k+1}-q^{-1}[(q-1)^{2k+1}+(q-1)^{2}]\\\
\phantom{\mathbf{z}(f)}=q^{-1}[(q-1)^{2k+2}+q^{k+1}(q-2)(q-1)+(q-1)],\end{array}$

with equality if and only if (6) holds. ∎

We are now ready to prove the main result.

###### Proof of Theorem 3.1.

By Propositions 3.2 and 3.4

$\textstyle\max\limits_{F\in S_{1}}|Z(F)\cap
X|=\max\left\\{(q-1)^{2k-3},\frac{(q-1)^{2k-1}+q^{k}(q-2)+1}{q(q-1)}\right\\}.$

Observe that

$\textstyle(q-1)^{2k-3}-\frac{(q-1)^{2k-1}+q^{k}(q-2)+1}{q(q-1)}=\frac{(q-1)^{2k-2}-q^{k}(q-2)-1}{q(q-1)}$

and denote the expression $(q-1)^{2k-2}-q^{k}(q-2)$ in the numerator of this
fraction by $\Delta(k,q)$. We want to show that

$\Delta(k,q)>0\iff\bigl{(}k>5\text{ and }q>2\bigr{)}\text{ or
}\bigl{(}k=4\text{ and }q>3\bigr{)}.$

Since

$\begin{array}[]{l}\Delta(2,q)=(q-1)^{2}-q^{2}(q-2)<q^{2}-q^{2}(q-2)<0,\\\
\Delta(3,q)=(q-1)^{4}-q^{3}(q-2)<q[(q-1)^{3}-q^{2}(q-2)]=q[-q^{2}+3q-1]<0,\end{array}$

we may reduce to $k\geq 4$. By direct computation,
$\Delta(4,3)=2^{6}-3^{4}<0$. Hence, if $k=4$ we may reduce to $q>3$. In this
situation, $q-1\geq\frac{3}{4}q$ and this yields:

$\textstyle\Delta(4,q)=(q-1)^{6}-q^{4}(q-2)\geq\frac{3^{5}}{4^{5}}q\cdot
q^{4}(q-2)-q^{4}(q-2),$

the right side of which is positive if $3^{5}q>4^{5}$ which is equivalent to
$q\geq 5$. Since, by direct computation, $\Delta(4,4)=3^{6}-4^{4}\cdot 2>0$ we
conclude that $\Delta(4,q)>0$ if and only if $q>3$. Finally, assume that
$k\geq 5$. Since

$\begin{array}[]{l}\Delta(k,q)=(q-1)^{2k-2}-q^{k}(q-2)\\\
\phantom{\Delta(k,q)}=(q-1)^{2}\Delta(k-1,q)+(q-1)^{2}q^{k-1}(q-2)-q^{k}(q-2)\\\
\phantom{\Delta(k,q)}=(q-1)^{2}\Delta(k-1,q)+[q^{2}-3q+1]q^{k-1}(q-2)\\\
\end{array}$

and $q^{2}-3q+1>0$ for $q>2$, from the positivity of $\Delta(4,q)$, for $q>3$
we get $\Delta(k,q)>0$, for $q>3$. Finally, if $q=3$

$\textstyle\Delta(k,3)=2^{2k-2}-3^{k}>0\iff k>\frac{\ln(4)}{\ln(4)-\ln(3)}\iff
k\geq 5.\qed$

######  Example 3.5.

Consider $G=\mathcal{C}_{4}$, where $k=2$. Then $C$ is a code of length
$(q-1)^{2}$ and dimension $4$. According to Theorem 3.1, its minimum distance
is

$\textstyle\frac{(q-1)^{4}-q^{2}(q-2)-1}{q(q-1)}=(q-2)^{2}.$

This agrees with the results of [3] and [15]. Indeed, since $\mathcal{C}_{4}$
is a complete bipartite graph $\mathcal{K}_{2,2}$, by [3, Theorem 5.5], the
minimum distance of $C$ is the square of the minimum distance of the
evaluation code over $\mathbb{T}^{1}$ of order $1$, which, by [15, Theorem
3.5], is equal to $(q-2)$.

### Acknowledgments

The authors thank Manuel González-Sarabia for his helpful comments.

## References

  * [1] I. M. Duursma, C. Rentería, H. Tapia-Recillas, Reed-Muller codes on complete intersections., Appl. Algebra Eng. Commun. Comput. 11 (6) (2001) 455–462.  doi:10.1007/s002000000047.
  * [2] M. González Sarabia, C. Rentería Márquez, Evaluation codes associated to some matrices, Int. J. Contemp. Math. Sci. 2 (13-16) (2007) 615–625.  doi:10.12988/ijcms.2007.07060.
  * [3] M. González Sarabia, C. Rentería Márquez, Evaluation codes associated to complete bipartite graphs, Int. J. Algebra 2 (1-4) (2008) 163–170.
  * [4] M. González Sarabia, C. Rentería Márquez, M. A. Hernández de la Torre, Minimum distance and second generalized Hamming weight of two particular linear codes, Congr. Numerantium 161, 105–116 (2003).
  * [5] M. González Sarabia, C. Rentería Márquez, E. Sarmiento Rosales, Parameterized codes over some embedded sets and their applications to complete graphs, Math. Commun. 18 (2) (2013) 377–391.
  * [6] D. R. Grayson, M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
  * [7] A. Macchia, J. Neves, M. Vaz Pinto, R. H. Villarreal, Regularity of the vanishing ideal over a parallel composition of paths, J. Commut. Algebra 12 (3) (2020) 391–407.  doi:10.1216/jca.2020.12.391.
  * [8] J. Neves, Regularity of the vanishing ideal over a bipartite nested ear decomposition, J. Algebra Appl. 19 (7) (2020) 28, id/No 2050126.  doi:10.1142/S0219498820501261.
  * [9] J. Neves, Eulerian ideals, Commun. Algebra 51 (2) (2023) 552–564.  doi:10.1080/00927872.2022.2106372.
  * [10] J. Neves, M. Vaz Pinto, Vanishing ideals over complete multipartite graphs, J. Pure Appl. Algebra 218 (6) (2014) 1084–1094.  doi:10.1016/j.jpaa.2013.11.005.
  * [11] J. Neves, M. Vaz Pinto, Parameterized codes over graphs, São Paulo J. Math. Sci. (17) (2023) 306–319.  doi:10.1007/s40863-022-00335-7.
  * [12] J. Neves, M. V. Pinto, R. H. Villarreal, Vanishing ideals over graphs and even cycles, Commun. Algebra 43 (3) (2015) 1050–1075.  doi:10.1080/00927872.2012.714025.
  * [13] J. Neves, M. Vaz Pinto, R. H. Villarreal, Joins, ears and Castelnuovo-Mumford regularity, J. Algebra 560 (2020) 67–88.  doi:10.1016/j.jalgebra.2020.05.014.
  * [14] C. Rentería-Márquez, A. Simis, R. H. Villarreal, Algebraic methods for parameterized codes and invariants of vanishing ideals over finite fields, Finite Fields Appl. 17 (1) (2011) 81–104.  doi:10.1016/j.ffa.2010.09.007.
  * [15] E. Sarmiento, M. Vaz Pinto, R. H. Villarreal, The minimum distance of parameterized codes on projective tori, Appl. Algebra Eng. Commun. Comput. 22 (4) (2011) 249–264.  doi:10.1007/s00200-011-0148-2.