MINIMUM DISTANCE FUNCTIONS OF GRADED IDEALS AND
REED-MULLER-TYPE CODES

arXiv:1512.06868v2 [math.AC] 12 Jun 2016

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*
Abstract. We introduce and study the minimum distance function of a graded ideal in a
polynomial ring with coefficients in a field, and show that it generalizes the minimum distance
of projective Reed-Muller-type codes over finite fields. This gives an algebraic formulation of
the minimum distance of a projective Reed-Muller-type code in terms of the algebraic invariants
and structure of the underlying vanishing ideal. Then we give a method, based on Gröbner bases
and Hilbert functions, to find lower bounds for the minimum distance of certain Reed-Mullertype codes. Finally we show explicit upper bounds for the number of zeros of polynomials in
a projective nested cartesian set and give some support to a conjecture of Carvalho, LopezNeumann and López.

1. Introduction
Let S = K[t1 , . . . , ts ] = ⊕∞
d=0 Sd be a polynomial ring over a field K with the standard grading
and let I 6= (0) be a graded ideal of S of Krull dimension k. The Hilbert function of S/I is:
HI (d) := dimK (Sd /Id ),

d = 0, 1, 2, . . . ,

where Id = I ∩ Sd . By a theorem of Hilbert, there is a unique polynomial hI (x) ∈ Q[x] of degree
k − 1 such that HI (d) = hI (d) for d ≫ 0. The degree of the zero polynomial is −1.
The degree or multiplicity of S/I is the positive integer

(k − 1)! limd→∞ HI (d)/dk−1 if k ≥ 1,
deg(S/I) :=
dimK (S/I)
if k = 0.
Let Fd be the set of all zero-divisors of S/I not in I of degree d ≥ 0:
Fd := { f ∈ Sd | f ∈
/ I, (I : f ) 6= I},
where (I : f ) = {h ∈ S| hf ∈ I} is a quotient ideal. Notice that F0 = ∅.
The main object of study here is the function δI : N → Z given by

deg(S/I) − max{deg(S/(I, f ))| f ∈ Fd } if Fd 6= ∅,
δI (d) :=
deg(S/I)
if Fd = ∅.
We call δI the minimum distance function of I. If I is a prime ideal, then Fd = ∅ for all d ≥ 0
and δI (d) = deg(S/I). We show that δI generalizes the minimum distance function of projective
Reed-Muller-type codes over finite fields (Theorem 4.7). This abstract algebraic formulation of
the minimum distance gives a new tool to study these type of linear codes.
2010 Mathematics Subject Classification. Primary 13P25; Secondary 14G50, 94B27, 11T71.
Key words and phrases. Reed-Muller-type codes, minimum distance, vanishing ideals, degree, Hilbert function.
The first and third author were supported by SNI. The second author was supported by CONACyT.
*Corresponding author.
1

2

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

To compute δI (d) is a difficult problem. For certain family of ideals we will give lower bounds
for δI (d) which are easier to compute.
Fix a monomial order ≺ on S. Let ∆≺ (I) be the footprint of S/I consisting of all the standard
monomials of S/I, with respect to ≺, and let G = {g1 , . . . , gr } be a Gröbner basis of I. Then
∆≺ (I) is the set of all monomials of S that are not a multiple of any of the leading monomials
of g1 , . . . , gr (Lemma 2.5). A polynomial f is called standard if f 6= 0 and f is a K-linear
combination of standard monomials.
P
If ∆≺ (I) ∩ Sd = {ta1 , . . . , tan } and F≺,d = {f = i λi tai | f 6= 0, λi ∈ K, (I : f ) 6= I}, then
using the division algorithm [4, Theorem 3, p. 63] we can write:
δI (d) = deg(S/I) − max{deg(S/(I, f ))| f ∈ Fd }
= deg(S/I) − max{deg(S/(I, f ))| f ∈ F≺,d }.

Notice that Fd 6= ∅ if and only if F≺,d 6= ∅. If K = Fq is a finite field, then the number of
standard polynomials of degree d is nq − 1, where n is the number of standard monomials of
degree d. Hence, we can compute δI (d) for small values of n and q (Examples 7.1 and 7.2).
′
of F≺,d and computing
Upper bounds for δI (d) can be obtained by fixing a subset F≺,d
′
} ≥ δI (d).
δI′ (d) = deg(S/I) − max{deg(S/(I, f ))| f ∈ F≺,d
P
a
′
Typically one uses F≺,d = {f = i λi t i | f 6= 0, λi ∈ {0, 1}, (I : f ) 6= I} or a subset of it.

Lower bounds for δI (d) are harder to find. Thus, we seek to estimate δI (d) from below. So,
with this in mind, we introduce the footprint function of I:

deg(S/I) − max{deg(S/(in≺ (I), ta )) | ta ∈ ∆≺ (I)d } if ∆≺ (I)d 6= ∅,
fpI (d) =
deg(S/I)
if ∆≺ (I)d = ∅,

where in≺ (I) = (in≺ (g1 ), . . . , in≺ (gr )) is the initial ideal of I, in≺ (gi ) is the initial monomial of
gi for i = 1, . . . , s, and ∆≺ (I)d = ∆≺ (I) ∩ Sd .
The contents of this paper are as follows. In Section 2 we present some of the results and
terminology that will be needed throughout the paper.
Some of our results rely on a degree formula to compute the number of zeros that a homogeneous polynomial has in any given finite set of points in a projective space (Lemma 3.2).
In Section 4 we study δI and present an alternative formula for δI , pointed out to us by
Vasconcelos, valid for unmixed graded ideals (Theorem 4.4). If Fd 6= ∅ for d ≥ 1 and I is
unmixed, then, by Lemma 4.1, fpI (d) is a lower bound of δI (d), but even in this case fpI (d)
could be negative (Example 7.3). For this reason we will sometimes make extra assumptions
requiring that dim(S/I) ≥ 1 and that ti is a zero-divisor of S/I for i = 1, . . . , s (cf. Lemma 2.7).
One of our first main results gives some general properties of δI for an interesting class of
graded ideals and show its relation to fpI :
Theorem 4.5. Let I ⊂ S be an unmixed graded ideal of dimension ≥ 1 such that ti is a
zero-divisor of S/I for i = 1, . . . , s. The following hold.
(i)
(ii)
(iii)
(iv)
(v)
(vi)

Fd 6= ∅ for d ≥ 1.
δI (d) ≥ fpI (d) for d ≥ 1.
deg(S/(I, ta )) ≤ deg(S/(in≺ (I), ta )) ≤ deg(S/I) for any ta ∈ ∆≺ (I) ∩ Sd .
fpI (d) ≥ 0.
δI (d) ≥ δI (d + 1) ≥ 0 for d ≥ 1.
If I is a radical ideal and its associated primes are generated by linear forms, then there
is r ≥ 1 such that δI (1) > · · · > δI (r) = δI (d) = 1 for d ≥ r.

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

3

The study of δI was motivated by the notion of minimum distance of linear codes in coding
theory. For convenience we recall this notion. Let K = Fq be a finite field. A linear code is
a linear subspace of K m for some m. The basic parameters of a linear code C are length: m,
dimension: dimK (C), and minimum distance:
δ(C) := min{kvk : 0 6= v ∈ C},
where kvk is the number of non-zero entries of v.
The minimum distance of affine Reed-Muller-type codes has been studied using Gröbner bases
techniques; see [2, 8, 9] and the references therein. Of particular interest to us is the footprint
technique introduced by Geil [8] to bound from below the minimum distance. In this work we
extend this technique to projective Reed-Muller-type codes, a special type of linear codes that
generalizes affine Reed-Muller-type codes [15]. These projective codes are constructed as follows.
Let K = Fq be a finite field with q elements, let Ps−1 be a projective space over K, and let
X be a subset of Ps−1 . The vanishing ideal of X, denoted I(X), is the ideal of S generated by
the homogeneous polynomials that vanish at all points of X. In this case the Hilbert function
of S/I(X) is denoted by HX (d). We can write X = {[P1 ], . . . , [Pm ]} ⊂ Ps−1 with m = |X|.
Fix a degree d ≥ 0. For each i there is fi ∈ Sd such that fi (Pi ) 6= 0. There is a K-linear map
given by


f (Pm )
f (P1 )
m
,...,
.
evd : Sd → K ,
f 7→
f1 (P1 )
fm (Pm )
The image of Sd under evd , denoted by CX (d), is called a projective Reed-Muller-type code of
degree d on X [5, 12]. The basic parameters of the linear code CX (d) are:
(a) length: |X|,
(b) dimension: dimK CX (d),
(c) minimum distance: δX (d) := δ(CX (d)).
The regularity of S/I(X), denoted reg(S/I(X)), is the least integer r ≥ 0 such that HX (d)
is equal to hI(X) (d) for d ≥ r. As is seen below, the knowledge of the regularity of S/I(X) is
important for applications to coding theory. According to [10] and Proposition 2.15, there are
integers r ≥ 0 and r1 ≥ 0 such that
1 = HX (0) < HX (1) < · · · < HX (r − 1) < HX (d) = |X|
for d ≥ r = reg(S/I(X)), and
|X| = δX (0) > δX (1) > · · · > δX (r1 − 1) > δX (r1 ) = δX (d) = 1 for d ≥ r1 ,
respectively. The integer r1 is called the minimum distance regularity of S/I(X). In general
r1 ≤ r (see the discussion below). Using the methods of [19, 23], the regularity of S/I(X) can be
effectively computed when X is parameterized by monomials, but r1 is very difficult to compute.
The Hilbert function and the minimum distance are related by the Singleton bound:
1 ≤ δX (d) ≤ |X| − HX (d) + 1.
In particular, if d ≥ reg(S/I(X)) ≥ 1, then δX (d) = 1. The converse is not true (Example 7.4).
Thus, potentially good Reed-Muller-type codes CX (d) can occur only if 1 ≤ d < reg(S/I(X)).
There are some families where d ≥ reg(S/I(X)) ≥ 1 if and only if δX (d) = 1 [14, 20, 21], but we
do not know of any set X parameterized by monomials where this fails. If X is parameterized
by monomials we say that CX (d) is a projective parameterized code [19, 23].
A main problem in Reed-Muller-type codes is the following. If X has nice algebraic or combinatorial structure, find formulas in terms of s, q, d, and the structure of X, for the basic parameters

4

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

of CX (d): HX (d), deg(S/I(X)), δX (d), and reg(S/I(X)). Our main results can be used to study
this problem, especially when X is parameterized by monomials or when X is a projective nested
cartesian set (see Definition 6.1).
The basic parameters of projective Reed-Muller-type codes have been computed in some
cases. If X = Ps−1 , CX (d) is the classical projective Reed–Muller code. Formulas for its basic
parameters were given in [21, Theorem 1]. If X is a projective torus (see Definition 2.11), CX (d)
is the generalized projective Reed–Solomon code. Formulas for its basic parameters were given
in [20, Theorem 3.5]. If X is the image of a cartesian product of subsets of K, under the map
K s−1 → Ps−1 , x → [x, 1], then CX (d) is an affine cartesian code and formulas for its basic
parameters were given in [9, 14].
We give a formula, in terms of the degree, for the number of zeros in X ⊂ Ps−1 of any
homogeneous polynomial (Lemma 3.2). As a consequence we derive our second main result:
Theorem 4.7. If |X| ≥ 2, then δX (d) = δI(X) (d) ≥ 1 for d ≥ 1.
In particular, if ≺ is a monomial order on S, then
(1.1)

δX (d) = deg(S/I) − max{deg(S/(I, f ))| f ∈ F≺,d }.

This description allows us to compute the minimum distance of Reed-Muller-type codes for
small values of q and s (Corollary 4.8) and it gives an algebraic formulation of the minimum
distance in terms of the algebraic properties and invariants of the vanishing ideal. The formula
of Eq. (1.1) is more interesting from the theoretical point of view than from a computational
perspective. Indeed, if ti is a zero-divisor of S/I(X) for all i, then one has:
δX (d) ≥ fpI(X) (d) ≥ 0 for d ≥ 1.
This inequality gives a lower bound for the minimum distance of any Reed-Muller-type code
over a set X parameterized by relatively prime monomials because in this case ti is a zero-divisor
of S/I(X) for i = 1, . . . , s (Corollary 4.9). Using SAGE [18] and a generator matrix of CX (d) one
can compute the minimum distance of CX (d) in a more efficient way than by using our formula
at least in the case that CX (d) arises from an affine Reed-Muller type code [15].
Let d1 , . . . , ds be a non-decreasing sequence of positive integers with d1 ≥ 2 and s ≥ 2, and
d
let L be the ideal of S generated by the set of all ti tj j such that 1 ≤ i < j ≤ s. It turns out
that the ideal L is the initial ideal of the vanishing ideal of a projective nested cartesian set (see
the discussion below). In Section 5 we study the ideal L and show some degree equalities as a
preparation to show some applications.
Projective nested cartesian codes were introduced and studied in [3] (see Definition 6.1).
This type of evaluation codes generalize the classical projective Reed–Muller codes [21]. As an
application we will give some support for the following interesting conjecture.
Conjecture 6.2. (Carvalho, Lopez-Neumann, and López [3]) Let A1 , . . . , As be subsets of K
and let CX (d) be the d-th projective nested cartesian code on the set X = [A1 × · · · × As ] with
di = |Ai | for i = 1, . . . , s. Then its minimum distance is given by

s
P


(di − 1) ,
 (dk+2 − ℓ + 1) dk+3 · · · ds if d ≤
i=2
δX (d) =
s
P


1
if d ≥
(di − 1) + 1,

i=2

where 0 ≤ k ≤ s − 2 and ℓ are integers such that d =

Pk+1
i=2

(di − 1) + ℓ and 1 ≤ ℓ ≤ dk+2 − 1.

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

5

Let ≺ be the lexicographical order on S with t1 ≺ · · · ≺ ts . Carvalho et. al. found a Gröbner
basis for I(X ) whose initial ideal is L, and obtained formulas for the regularity and the degree
of the coordinate ring S/I(X ) [3] (Proposition 6.3).
They showed the conjecture when the Ai ’s are subfields of Fq , and essentially showed that
their conjecture can be reduced to:
Conjecture 6.4. (Carvalho, Lopez-Neumann,
and López [3]) If f ∈ Sd is a standard polynomial
P
such that (I(X ) : f ) 6= I(X ), 1 ≤ d ≤ si=2 (di − 1), and VX (f ) is the zero set of f in X , then
|VX (f )| ≤ deg(S/I(X )) − (dk+2 − ℓ + 1) dk+3 · · · ds ,
P
where 0 ≤ k ≤ s − 2 and ℓ are integers such that d = k+1
i=2 (di − 1) + ℓ and 1 ≤ ℓ ≤ dk+2 − 1.
P
Let f 6= 0 be a standard polynomial, with respect to ≺, of degree d ≥ 1 with d ≤ si=2 (di − 1)
and (I(X ) : f ) 6= I(X ), and let in≺ (f ) = ta be its initial monomial. We can write
ta = tar r · · · tas s ,

with 1 ≤ r ≤ s, ar ≥ 1, 0 ≤ ai ≤ di − 1 for i > r.
We show an explicit upper bound for the number of zeros of f in X :
Theorem 6.5. |VX (f )| ≤ deg(S/(in≺ (I(X )), ta )) =

r+1
X


(di − ai ) · · · (ds − as )
if ar ≤ dr ,
deg(S/I(X )) −
i=2


deg(S/I(X )) − (dr+1 − ar+1 ) · · · (ds − as ) if ar ≥ dr + 1.

Then we use Theorem 6.5 to give some support for Conjecture 6.4:
Theorem 6.6. If t1 divides ta = in≺ (f ), then

|VX (f )| ≤ deg(S/I(X )) − (dk+2 − ℓ + 1) dk+3 · · · ds ,
P
where 0 ≤ k ≤ s − 2 and ℓ are integers such that d = k+1
i=2 (di − 1) + ℓ and 1 ≤ ℓ ≤ dk+2 − 1.
As a consequence we show that the minimum distance of CX (d) proposed in Conjecture 6.2
is in fact the minimum distance of certain evaluation linear code (Corollary 6.9). Finally in
Section 7, we show some examples that illustrate how some of our results can be used in practice.
For all unexplained terminology and additional information, we refer to [1, 4, 6] (for the theory
of Gröbner bases, commutative algebra, and Hilbert functions), and [16, 26] (for the theory of
error-correcting codes and linear codes).
2. Preliminaries
In this section, we present some of the results that will be needed throughout the paper and
introduce some more notation. All results of this section are well-known. To avoid repetitions,
we continue to employ the notations and definitions used in Section 1.
Let S = K[t1 , . . . , ts ] = ⊕∞
d=0 Sd be a graded polynomial ring over a field K, with the standard
grading, and let (0) 6= I ⊂ S be a graded ideal. We will use the following multi-index notation:
for a = (a1 , . . . , as ) ∈ Ns , set ta := ta11 · · · tas s . The multiplicative group of K is denoted by K ∗ .
As usual, m will denote the maximal ideal of S generated by t1 , . . . , ts , and ht(I) will denote the
height of the ideal I. By the dimension of I (resp. S/I) we mean the Krull dimension of S/I.
The Krull dimension of S/I is denoted by dim(S/I).
One of the most useful and well-known facts about the degree is its additivity:

6

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

Proposition 2.1. (Additivity of the degree [17, Proposition 2.5]) If I is an ideal of S and
I = q1 ∩ · · · ∩ qm is an irredundant primary decomposition, then
X
deg(S/I) =
deg(S/qi ).
ht(qi )=ht(I)

Theorem 2.2. (Hilbert [1, Theorem 4.1.3]) Let I ⊂ S be a graded ideal of dimension k. Then
there is a polynomial hI (x) ∈ Q[x] of degree k − 1 such that HI (d) = hI (d) for d ≫ 0.
If f ∈ S, the quotient ideal of I with respect to f is given by (I : f ) = {h ∈ S| hf ∈ I}. The
element f is called a zero-divisor of S/I if there is 0 6= a ∈ S/I such that f a = 0, and f is called
regular on S/I if f is not a zero-divisor. Notice that f is a zero-divisor if and only if (I : f ) 6= I.
An associated prime of I is a prime ideal p of S of the form p = (I : f ) for some f in S.
Theorem 2.3. [27, Lemma 2.1.19, Corollary 2.1.30] If I is an ideal of S and I = q1 ∩ · · · ∩ qm
is an irredundant primary decomposition with rad(qi ) = pi , then the set of zero-divisors Z(S/I)
of S/I is given by
m
[
pi ,
Z(S/I) =
i=1

and p1 , . . . , pm are the associated primes of I.

In the introduction we defined the regularity of the coordinate ring of a finite set in a projective
space. This notion is defined for any graded ideal.
Definition 2.4. The regularity of S/I, denoted reg(S/I), is the least integer r ≥ 0 such that
HI (d) is equal to hI (d) for d ≥ r.
If I ⊂ S is Cohen-Macaulay and dim(S/I) = 1, then reg(S/I) is the Castelnuovo-Mumford
regularity of S/I in the sense of [7]. If dim(S/I) = 0, then reg(S/I) is the least positive integer
d such that md ⊂ I.
The footprint of an ideal. Let ≺ be a monomial order on S and let (0) 6= I ⊂ S be an ideal.
If f is a non-zero polynomial in S, then one can write
f = λ1 tα1 + · · · + λr tαr ,
with λi ∈ K ∗ for all i and tα1 ≻ · · · ≻ tαr . The leading monomial tα1 of f is denoted by in≺ (f ).
The initial ideal of I, denoted by in≺ (I), is the monomial ideal given by
in≺ (I) = ({in≺ (f )| f ∈ I}).
A monomial ta is called a standard monomial of S/I, with respect to ≺, if ta is not the leading
monomial of any polynomial in I. The set of standard monomials, denoted ∆≺ (I), is called the
footprint of S/I. The image of the standard polynomials of degree d, under the canonical map
S 7→ S/I, x 7→ x, is equal to Sd /Id , and the image of ∆≺ (I) is a basis of S/I as a K-vector
space (see [27, Proposition 3.3.13]). In particular, if I is graded, then HI (d) is the number of
standard monomials of degree d.
A subset G = {g1 , . . . , gr } of I is called a Gröbner basis of I if
in≺ (I) = (in≺ (g1 ), . . . , in≺ (gr )).
Lemma 2.5. [2, p. 2] Let I ⊂ S be an ideal generated by G = {g1 , . . . , gr }, then
∆≺ (I) ⊂ ∆≺ (in≺ (g1 ), . . . , in≺ (gr )),
with equality if G is a Gröbner basis.

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

7

Proof. Take ta in ∆≺ (I). If ta ∈
/ ∆≺ (in≺ (g1 ), . . . , in≺ (gr )), then ta = tc in≺ (gi ) for some i and
c
a
c
some t . Thus t = in≺ (t gi ), with tc gi in I, a contradiction. The second statement holds by
the definition of a Gröbner basis.

Theorem 2.6. (Division algorithm [4, Theorem 3, p. 63]) If f, g1 , . . . , gr are polynomials in S,
then f can be written as
f = a1 g1 + · · · + ar gr + h,
where ai , h ∈ S and either h = 0 or h 6= 0 and no term of h is divisible by one of the initial
monomials in≺ (g1 ), . . . , in≺ (gr ). Furthermore if ai gi 6= 0, then in≺ (f ) ≥ in≺ (ai gi ).
Lemma 2.7. Let G = {g1 , . . . , gr } be a Gröbner basis of I. If for some i, the variable ti does
not divides in≺ (gj ) for all j, then ti is a regular element on S/I.
Proof. Assume that ti f ∈ I. By the division algorithm we can write f = g + h, where g ∈ I and
h is 0 or a standard polynomial. It suffices to show that h = 0. If h 6= 0, then ti in≺ (h) ∈ in≺ (I).
Hence, using our hypothesis on ti , we get in≺ (h) ∈ in≺ (I), a contradiction.

This lemma tells us that if ti is a zero-divisor of S/I for all i, then any variable ti must occur
in an initial monomial in≺ (gj ) for some j.
Theorem 2.8. (Macaulay [27, Corollary 3.3.15]) If I is a graded ideal of S, then S/I and
S/in≺ (I) have the same Hilbert function and the same degree and regularity.
Vanishing ideals of finite sets. The projective space of dimension s − 1 over the field K,
s−1
, or simply Ps−1 , is the quotient space
denoted PK
(K s \ {0})/ ∼
where two points α, β in K s \ {0} are equivalent under ∼ if α = cβ for some c ∈ K ∗ . It is usual
to denote the equivalence class of α by [α].
For a given a subset X ⊂ Ps−1 define I(X), the vanishing ideal of X, as the ideal generated
by the homogeneous polynomials in S that vanish at all points of X, and given a graded ideal
I ⊂ S define its zero set relative to X as
VX (I) = {[α] ∈ X| f (α) = 0, ∀f ∈ I homogeneous} .
In particular, if f ∈ S is homogeneous, the zero set VX (f ) of f is the set of all [α] ∈ X such that
f (α) = 0, that is VX (f ) is the set of zeros of f in X.
Lemma 2.9. Let X be a finite subset of Ps−1 , let [α] be a point in X, with α = (α1 , . . . , αs ) and
αk 6= 0 for some k, and let I[α] be the vanishing ideal of [α]. Then I[α] is a prime ideal,
I[α] = ({αk ti − αi tk | k 6= i ∈ {1, . . . , s}), deg(S/I[α] ) = 1,
T
ht(I[α] ) = s − 1, and I(X) = [β]∈X I[β] is the primary decomposition of I(X).

If X is a subset of Ps−1 it is usual to denote the Hilbert function of S/I(X) by HX .

Proposition 2.10. [10] If X ⊂ Ps−1 is a finite set, then
1 = HX (0) < HX (1) < · · · < HX (r − 1) < HX (d) = |X|
for d ≥ r = reg(S/I(X)).
Definition 2.11. The set T = {[(x1 , . . . , xs )] ∈ Ps−1 | xi ∈ K ∗ ∀ i} is called a projective torus.

8

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

Projective Reed-Muller-type codes. Let K = Fq be a finite field, let X be a subset of Ps−1 ,
and let P1 , . . . , Pm be a set of representatives for the points of X with m = |X|. In this paragraph
all results are valid if we assume that K is any field and that X is a finite subset of Ps−1 instead
of assuming that K is finite. However the interesting case for coding theory is when K is finite.
Fix a degree d ≥ 0. For each i there is fi ∈ Sd such that fi (Pi ) 6= 0. Indeed suppose
Pi = [(a1 , . . . , as )], there is at least one k in {1, . . . , s} such that ak 6= 0. Setting fi (t1 , . . . , ts ) = tdk
one has that fi ∈ Sd and fi (Pi ) 6= 0. There is a K-linear map:


f (P1 )
f (Pm )
|X|
evd : Sd = K[t1 , . . . , ts ]d → K ,
f 7→
,...,
.
f1 (P1 )
fm (Pm )
The map evd is called an evaluation map. The image of Sd under evd , denoted by CX (d), is
called a projective Reed-Muller-type code of degree d over X [5, 12]. It is also called an evaluation
code associated to X [11].
Definition 2.12. The basic parameters of the linear code CX (d) are its length |X|, dimension
dimK CX (d), and minimum distance
δX (d) := min{kvk : 0 6= v ∈ CX (d)},
where kvk is the number of non-zero entries of v.
Lemma 2.13. (a) The map evd is well-defined, i.e., it is independent of the set of representatives
that we choose for the points of X. (b) The basic parameters of the Reed-Muller-type code CX (d)
are independent of f1 , . . . , fm .
′ is another set of representatives, there are λ , . . . , λ in K ∗ such that
Proof. (a): If P1′ , . . . , Pm
1
m
′
Pi = λi Pi for all i. Thus, f (Pi′ )/fi (Pi′ ) = f (Pi )/fi (Pi ) for f ∈ Sd and 1 ≤ i ≤ m.
′ be homogeneous polynomials of S of degree d such that f ′ (P ) 6= 0 for
(b): Let f1′ , . . . , fm
i
i
i = 1, . . . , m, and let


f (Pm )
f (P1 )
′
|X|
,..., ′
f 7→
evd : Sd → K ,
f1′ (P1 )
fm (Pm )

′ . Then ker(ev ) = ker(ev ′ ) and kev (f )k = kev ′ (f )k
be the evaluation map relative to f1′ , . . . , fm
d
d
d
d
for f ∈ Sd . It follows that the basic parameters of evd (Sd ) and ev′d (Sd ) are the same.


Lemma 2.14. Let Y = {[α], [β]} be a subset of Ps−1 with two elements. The following hold.
(i)
(ii)
(iii)
(iv)

reg(S/I(Y)) = 1.
There is h ∈ S1 , a form of degree 1, such that h(α) 6= 0 and h(β) = 0.
For each d ≥ 1, there is f ∈ Sd , a form of degree d, such that f (α) 6= 0 and f (β) = 0.
If X is a subset of Ps−1 with at least two elements and d ≥ 1, then there is f ∈ Sd such
f∈
/ I(X) and (I(X) : f ) 6= I(X).

Proof. (i): As HY (0) = 1 and |Y| = 2, by Proposition 2.10, we get that HY (1) = |Y| = 2. Thus
S/I(Y) has regularity equal to 1.
(ii): Consider the evaluation map
ev1 : S1 −→ K 2 ,

f 7→ (f (α)/f1 (α), f (β)/f2 (β)) .

By part (i) this map is onto. Thus (1, 0) is in the image of ev1 and the result follows.
(iii): It follows from part (ii) by setting f = hd .

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

9

(iv): By part (iii), there are distinct [α], [β] in X and f ∈ Sd such that f (α) 6= 0, f (β) = 0.
Then f ∈
/ I(X). Notice that f (β) = 0 if and only if f ∈ I[β] . Hence, by Theorem 2.3 and
Lemma 2.9, f is a zero-divisor of S/I(X), that is, (I(X) : f ) 6= I(X).

The next result was shown in [19, Proposition 5.2] and [24, Proposition 2.1] for some special
types of Reed-Muller-type codes (cf. Theorem 4.5(vi)). In [19] (resp. [24]) it is assumed that
X is contained in a projective torus (resp. X is not contained in a hyperplane and that there is
f ∈ Sd not vanishing at any point of X).
Proposition 2.15. There is an integer r ≥ 0 such that
|X| = δX (0) > δX (1) > · · · > δX (d) = δX (r) = 1 for d ≥ r.
Proof. Assume that δX (d) > 1, it suffices to show that δX (d) > δX (d + 1). Pick g ∈ Sd such that
g∈
/ I(X) and
|VX (g)| = max{|VX (f )| : evd (f ) 6= 0; f ∈ Sd }.
Then δX (d) = |X| − |VX (g)| ≥ 2. Thus there are distinct points [α], [β] in X such that g(α) 6= 0
and g(β) 6= 0. By Lemma 2.14, there is a linear form h ∈ S1 such that h(α) 6= 0 and h(β) = 0.
Hence the polynomial hg is not in I(X), has degree d + 1, and has at least |VX (g)| + 1 zeros.
Thus δX (d) > δX (d + 1), as required.

The following summarizes the well-known relation between projective Reed-Muller-type codes
and the theory of Hilbert functions.
Proposition 2.16. ([12], [19]) The following hold.
(i)
(ii)
(iii)
(iv)
(v)

HX (d) = dimK CX (d) for d ≥ 0.
deg(S/I(X)) = |X|.
δX (d) = 1 for d ≥ reg(S/I(X)).
S/I(X) is a Cohen–Macaulay reduced graded ring of dimension 1.
CX (d) 6= (0) for d ≥ 1.
3. Computing the number of zeros using the degree

In this section we give a degree formula to compute the number of zeros that a homogeneous
polynomial has in any given finite set of points in a projective space over any field.
An ideal I ⊂ S is called unmixed if all its associated primes have the same height and I is
called radical if I is equal to its radical. The radical of I is denoted by rad(I).
Lemma 3.1. Let I ⊂ S be a radical unmixed graded ideal. If f ∈ S is homogeneous, (I : f ) 6= I,
and A is the set of all associated primes of S/I that contain f , then ht(I) = ht(I, f ) and
X
deg(S/(I, f )) =
deg(S/p).
p∈A

Proof. As f is a zero-divisor of S/I and I is unmixed, there is an associated prime ideal p of
S/I of height ht(I) such that f ∈ p. Thus I ⊂ (I, f ) ⊂ p, and consequently ht(I) = ht(I, f ).
Therefore the set of associated primes of (I, f ) of height equal to ht(I) is not empty and is equal
to A. There is an irredundant primary decomposition
(3.1)

(I, f ) = q1 ∩ · · · ∩ qr ∩ q′r+1 ∩ · · · ∩ q′t ,

10

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

where rad(qi ) = pi , A = {p1 , . . . , pr }, and ht(q′i ) > ht(I) for i > r. We may assume that the
associated primes of S/I are p1 , . . . , pm . Since I is a radical ideal, we get that I = ∩m
i=1 pi . Next
we show the following equality:
(3.2)

p1 ∩ · · · ∩ pm = q1 ∩ · · · ∩ qr ∩ q′r+1 ∩ · · · ∩ q′t ∩ pr+1 ∩ · · · ∩ pm .

The inclusion “⊃” is clear because qi ⊂ pi for i = 1, . . . , r. The inclusion “⊂” follows by noticing
that the right hand side of Eq. (3.2) is equal to (I, f )∩pr+1 ∩· · ·∩pm , and consequently it contains
′
′
I = ∩m
i=1 pi . Notice that rad(qj ) = pj 6⊂ pi for all i, j and pj 6⊂ pi for i 6= j. Hence localizing
Eq. (3.2) at the prime ideal pi for i = 1, . . . , r, we get that pi = Ipi ∩ S = (qi )pi ∩ S = qi for
i = 1, . . . , r. Using Eq. (3.1) and the additivity of the degree the required equality follows. 
Lemma 3.2. Let X be a finite subset of Ps−1 over a field K and let I(X) ⊂ S be its graded
vanishing ideal. If 0 =
6 f ∈ S is homogeneous, then the number of zeros of f in X is given by

deg S/(I(X), f ) if (I(X) : f ) 6= I(X),
|VX (f )| =
0
if (I(X) : f ) = I(X).
Proof. Let [P1 ], . . . , [Pm ] be the points of X with m = |X|, and let [P ] be a point in X, with
P = (α1 , . . . , αs ) and αk 6= 0 for some k. Then the vanishing ideal I[P ] of [P ] is a prime ideal of
height s − 1,
I[P ] = ({αk ti − αi tk | k 6= i ∈ {1, . . . , s}), deg(S/I[P ] ) = 1,
Tm
and I(X) = i=1 I[Pi ] is a primary decomposition (see Lemma 2.9). In particular I(X) is an
unmixed radical ideal of dimension 1.
Assume that (I(X) : f ) 6= I(X). Let A be the set of all I[Pi ] that contain the polynomial f .
Then f (Pi ) = 0 if and only if I[Pi ] is in A. Hence, by Lemma 3.1, we get
X
X
deg S/I[Pi ] = deg S/(I(X), f ).
|VX (f )| =
deg S/I[Pi ] =
[Pi ]∈VX (f )

f ∈I[Pi ]

If (I(X) : f ) = I(X), then f is a regular element of S/I(X). This means that f is not in any of
the associated primes of I(X), that is, f ∈
/ I[Pi ] for all i. Thus VX (f ) = ∅ and |VX (f )| = 0.

4. The minimum distance function of a graded ideal
In this section we study the minimum distance function δI of a graded ideal I and show that
it generalizes the minimum distance function of a projective Reed-Muller-type code. To avoid
repetitions, we continue to employ the notations and definitions used in Sections 1 and 2.
The next result will be used to bound the number of zeros of polynomials over finite fields
(see Corollary 4.3) and to study the general properties of δI .
Lemma 4.1. Let I ⊂ S be an unmixed graded ideal and let ≺ be a monomial order. If f ∈ S is
homogeneous and (I : f ) 6= I, then
deg(S/(I, f )) ≤ deg(S/(in≺ (I), in≺ (f ))) ≤ deg(S/I),
and deg(S/(I, f )) < deg(S/I) if I is an unmixed radical ideal and f ∈
/ I.
Proof. To simplify notation we set J = (I, f ) and L = (in≺ (I), in≺ (f )). We denote the Krull
dimension of S/I by dim(S/I). Recall that dim(S/I) = dim(S) − ht(I). First we show that
S/J and S/L have Krull dimension equal to dim(S/I). As f is a zero-divisor of S/I and I is
unmixed, there is an associated prime ideal p of S/I such that f ∈ p and dim(S/I) = dim(S/p).

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

11

Since I ⊂ J ⊂ p, we get that dim(S/J) is dim(S/I). Since S/I and S/in≺ (I) have the same
Hilbert function, and so does S/p and S/in≺ (p), we obtain
dim(S/in≺ (I)) = dim(S/I) = dim(S/p) = dim(S/in≺ (p)).
Hence, taking heights in the inclusions in≺ (I) ⊂ L ⊂ in≺ (p), we obtain ht(I) = ht(L).
Pick a Gröbner basis G = {g1 , . . . , gr } of I. Then J is generated by G ∪ {f } and by Lemma 2.5
one has the inclusions
∆≺ (J) = ∆≺ (I, f ) ⊂ ∆≺ (in≺ (g1 ), . . . , in≺ (gr ), in≺ (f )) =
∆≺ (in≺ (I), in≺ (f )) = ∆≺ (L) ⊂ ∆≺ (in≺ (g1 ), . . . , in≺ (gr )) = ∆≺ (I).
Thus ∆≺ (J) ⊂ ∆≺ (L) ⊂ ∆≺ (I). Recall that HI (d), the Hilbert function of I at d, is the number
of standard monomials of degree d. Hence HJ (d) ≤ HL (d) ≤ HI (d) for d ≥ 0. If dim(S/I) is
equal to 0, then
X
X
X
deg(S/J) =
HJ (d) ≤ deg(S/L) =
HL (d) ≤ deg(S/I) =
HI (d).
d≥0

d≥0

d≥0

Assume now that dim(S/I) ≥ 1. By the Hilbert theorem, HJ , HL , HI are polynomial
functions of degree equal to k = dim(S/I) − 1. Thus
k! lim HJ (d)/dk ≤ k! lim HL (d)/dk ≤ k! lim HI (d)/dk ,
d→∞

d→∞

d→∞

that is deg(S/J) ≤ deg(S/L) ≤ deg(S/I).
If I is an unmixed radical ideal and f ∈
/ I, then there is at least one minimal prime that does
not contains f . Hence, by Lemma 3.1, it follows that deg(S/(I, f )) < deg(S/I).

Remark 4.2. Let I ⊂ S be an unmixed graded ideal of dimension 1. If f ∈ Sd , then (I : f ) = I
if and only if dim(S/(I, f )) = 0. In this case deg(S/(I, f )) could be greater than deg(S/I).
Corollary 4.3. Let X be a finite subset of Ps−1 , let I(X) ⊂ S be its vanishing ideal, and let ≺
be a monomial order. If 0 6= f ∈ S is homogeneous and (I(X) : f ) =
6 I(X), then
|VX (f )| = deg(S/(I(X), f )) ≤ deg(S/(in≺ (I(X)), in≺ (f ))) ≤ deg(S/I(X)),
and deg(S/(I(X), f )) < deg(S/I(X)) if f ∈
/ I(X).
Proof. It follows from Lemma 3.2 and Lemma 4.1.



The next alternative formula for the minimum distance function is valid for unmixed graded
ideals. It was pointed out to us by Vasconcelos.
Theorem 4.4. Let I ⊂ S be an unmixed graded ideal and let ≺ be a monomial order on S. If
∆≺ (I)pd is the set of homogeneous standard polynomials of degree d and md 6⊂ I, then
δI (d) = min{deg(S/(I : f )) | f ∈ Sd \ I}
= min{deg(S/(I : f )) | f ∈ ∆≺ (I)pd }.
Proof. The second equality is clear because by the division algorithm any f ∈ Sd \ I can be
written as f = g + h, where g ∈ I and h ∈ ∆≺ (I)pd , and (I : f ) = (I : h). Next we show the first
equality. If Fd = ∅, δI (d) = deg(S/I) and for any f ∈ Sd \ I, one has that (I : f ) is equal to I.

12

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

Thus equality holds. Assume that Fd 6= ∅. Take f ∈ Fd . Using that I is unmixed, it is not hard
to see that S/I, S/(I : f ), and S/(I, f ) have the same dimension. There are exact sequences
0 −→ (I : f )/I −→ S/I −→ S/(I : f ) −→ 0, and
f

0 −→ (I : f )/I −→ (S/I)[−d] −→ S/I −→ S/(I, f ) −→ 0.
Hence, by the additivity of Hilbert functions, we get
HI (i) − H(I : f ) (i) = HI (i − d) − HI (i) + H(I,f ) (i) for i ≥ 0.

(4.1)

By definition of δI (d) it suffices to show the following equality
deg(S/(I : f )) = deg(S/I) − deg(S/(I, f )).

(4.2)

If dim S/I = 0, then using Eq. (4.1) one has
X
X
X
X
X
HI (i) −
H(I : f ) (i) =
HI (i − d) −
HI (i) +
H(I,f ) (i).
i≥0

i≥0

i≥0

i≥0

i≥0

Hence, using the definition of degree, the equality of Eq. (4.2) follows. If k = dim S/I − 1 ≥ 0,
by the Hilbert theorem, HI , H(I,f ) , and H(I : f ) are polynomial functions of degree k. Then
dividing Eq. (4.1) by ik and taking limits as i goes to infinity, the equality of Eq. (4.2) holds. 
We come to one of our main results.
Theorem 4.5. Let ≺ be a monomial order and let I ⊂ S be an unmixed ideal of dimension ≥ 1
such that ti is a zero-divisor of S/I for i = 1, . . . , s. The following hold.
(i)
(ii)
(iii)
(iv)
(v)
(vi)

The set Fd = {f ∈ Sd : f ∈
/ I, (I : f ) 6= I} is not empty for d ≥ 1.
δI (d) ≥ fpI (d) for d ≥ 1.
deg S/(I, ta ) ≤ deg S/(in≺ (I), ta ) ≤ deg S/I for any ta ∈ ∆≺ (I) ∩ Sd .
fpI (d) ≥ 0.
δI (d) ≥ δI (d + 1) ≥ 0 for d ≥ 1.
If I is a radical ideal and its associated primes are generated by linear forms, then there
is an integer r ≥ 1 such that
δI (1) > · · · > δI (r) = δI (d) = 1 for d ≥ r.

Proof. (i): Since dim(S/I) ≥ 1, there is 1 ≤ ℓ ≤ s such that tdℓ is not in I, and (I : tdℓ ) 6= I
because tdℓ is a zero-divisor of S/I. Thus tdℓ is in Fd .
(ii): The set Fd is not empty for d ≥ 1 by part (i). Pick a polynomial F of degree d such that
δI (d) = deg(S/I) − deg(S/(I, F )), F ∈
/ I, and (I : F ) 6= I. We may assume that F is a sum of
standard monomials of S/I with respect to ≺ (this follows using a Gröbner basis of I and the
division algorithm). Then, by Lemma 4.1, we get
deg S/(I, F ) ≤ deg S/(in≺ (I), in≺ (F )) ≤ deg S/I,
where in≺ (F ) is a standard monomial of S/I. Therefore δI (d) ≥ fpI (d) for d ≥ 1.
(iii), (iv): Since any standard monomial of degree d is a zero-divisor, by Lemma 4.1, we get
the inequalities in item (iii). Part (iv) follows at once from part (iii).
(v): The set Fd is not empty for d ≥ 1 by part (i). Then, by parts (ii) and (iv), δI (d) ≥ 0.
Pick F ∈ Sd such that F ∈
/ I, (I : F ) 6= I and
deg(S/(I, F )) = max{deg(S/(I, f ))| f ∈
/ I, f ∈ Sd , (I : f ) 6= I}.

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

13

There is h ∈ S1 such that hF ∈
/ I, because otherwise m = (t1 , . . . , ts ) is an associated prime
of S/I, a contradiction to the assumption that I is unmixed of dimension ≥ 1. As F is a zerodivisor of S/I, so is hF . The ideals (I, F ) and (I, hF ) have height equal to ht(I). Therefore
taking Hilbert functions in the exact sequence
0 −→ (I, F )/(I, hF ) −→ S/(I, hF ) −→ S/(I, F ) −→ 0
it follows that deg(S/(I, hF )) ≥ deg(S/(I, F )). This proves that δI (d) ≥ δI (d + 1).
(vi): By Lemma 4.1, δI (d) ≥ 1 for d ≥ 1. Assume that δI (d) > 1. By part (v) it suffices to
show that δI (d) > δI (d+1). Pick a polynomial F as in part (v). Let p1 , . . . , pm be the associated
primes of I. Then, by Lemma 3.1, one has
δI (d) = deg(S/I) − deg(S/(I, F ))
m
X
X
deg(S/pi ) −
deg(S/pi ) ≥ 2.
=
i=1

F ∈pi

Hence there are pk 6= pj such that F is not in pk ∪ pj . Pick a linear form h in pk \ pj ; which
exists because I is unmixed and pk is generated by linear forms. Then hF ∈
/ I because hF ∈
/ pj ,
and hF is a zero-divisor of S/I because (I : F ) 6= I. Noticing that F ∈
/ pk and hF ∈ pk , by
Lemma 3.1, we get
X
X
deg(S/(I, F )) =
deg(S/pi ) <
deg(S/pi ) = deg(S/(I, hF )).
F ∈pi

hF ∈pi

Therefore δI (d) > δI (d + 1).



Corollary 4.6. If I ⊂ S is a Cohen-Macaulay square-free monomial ideal, then there is an
integer r ≥ 1 such that
δI (1) > · · · > δI (r) = δI (d) = 1 for d ≥ r.
Proof. If I is prime, then I is generated by a subset of {t1 , . . . , ts }, deg(S/I) = 1, and Fd = ∅
for all d. Hence δI (d) = 1 for d ≥ 1. Thus we may assume that I has at least two associated
primes. Any Cohen-Macaulay ideal is unmixed [27]. Thus the degree of S/I is the number of
associated primes of I. Hence, we may assume that all variables are zero-divisors of S/I and
the result follows from Theorem 4.5(vi).

The next result gives an algebraic formulation of the minimum distance of a projective ReedMuller-type code in terms of the degree and the structure of the underlying vanishing ideal.
Theorem 4.7. Let K be a field and let X be a finite subset of Ps−1 . If |X| ≥ 2, then
δX (d) = δI(X) (d) ≥ 1 for d ≥ 1.
Proof. Setting I = I(X), by Lemma 2.14, the set Fd := { f ∈ Sd : f ∈
/ I, (I : f ) 6= I} is not
empty for d ≥ 1. Hence, using the formula for VX (f ) of Lemma 3.2, we obtain
max{|VX (f )| : evd (f ) 6= 0; f ∈ Sd } = max{deg(S/(I, f ))| f ∈ Fd }.
Therefore, using that deg(S/I) = |X|, we get
δX (d) = min{kevd (f )k : evd (f ) 6= 0; f ∈ Sd }
= |X| − max{|VX (f )| : evd (f ) 6= 0; f ∈ Sd }
= deg(S/I) − max{deg(S/(I, f ))| f ∈ Fd } = δI (d),
where kevd (f )k is the number of non-zero entries of evd (f ).



14

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

If I is a graded ideal and ∆≺ (I)∩Sd = {ta1 , . . . , tan }, recall that F≺,d is the set of homogeneous
standard polynomials of S/I of degree d which are zero-divisors of S/I:
P
F≺,d := {f = i λi tai | f 6= 0, λi ∈ K, (I : f ) 6= I} .

The next result gives a description of the minimum distance which is suitable for computing
this number using a computer algebra system such as Macaulay2 [13].
Corollary 4.8. If K = Fq , |X| ≥ 2, I = I(X), and ≺ a monomial order, then
δX (d) = deg S/I − max{deg(S/(I, f ))| f ∈ F≺,d } ≥ 1 for d ≥ 1.
Proof. It follows from Theorem 4.7 because by the division algorithm any polynomial f ∈ Sd
can be written as f = g + h, where g is in Id and h is a K-linear combination of standard
monomials of degree d. Notice that (I : f ) = (I : h).

The expression for δX (d) of Corollary 4.8 gives and algorithm that can be implemented in
Macaulay2 [13] to compute δX (d) (see Example 7.2). However, in practice, we can only find
the minimum distance for small values of q and d. Indeed, if n = |∆≺ (I) ∩ Sd |, to compute
δI(X) requires to test the inequality (I(X) : f ) 6= I(X) and compute the corresponding degree of
S/(I(X), f ) for the nq − 1 standard polynomials of S/I.
Corollary 4.9. Let K be a field, let ≺ be a monomial order, and let X be a finite subset of
Ps−1 . If ti is a zero-divisor of S/I(X) for i = 1, . . . , s, then δX (d) ≥ fpI(X) (d) ≥ 0 for d ≥ 1.
Proof. The inequalities δX (d) ≥ fpI(X) (d) ≥ 0 follow from Theorems 4.5 and 4.7.



One can use Corollary 4.9 to estimate the minimum distance of any Reed-Muller-type code
over a set X parameterized by a set of relatively prime monomials because in this case ti is
a zero-divisor of S/I(X) for i = 1, . . . , s and one has the following result that can be used to
compute the vanishing ideal of X using Gröbner bases and elimination theory.
Theorem 4.10. [23] Let K = Fq be a finite field. If X is a subset of Ps−1 parameterized by
monomials y v1 , . . . , y vs in the variables y1 , . . . , yn , then
I(X) = ({ti − y vi z}si=1 ∪ {yiq − yi }ni=1 ) ∩ S,
and I(X) is a binomial ideal.
As an application, Corollary 4.9 will be used to study the minimum distance of projective
nested cartesian codes [3] over a set X . In this case ti is a zero-divisor of S/I(X ) for i = 1, . . . , s
and one has a Gröbner basis for I(X ) [3] (see Section 6).
5. Degree formulas and some inequalities
Let S = K[t1 , . . . , ts ] be a polynomial ring over a field K, let d1 , . . . , ds be a non-decreasing
sequence of positive integers with d1 ≥ 2 and s ≥ 2, and let L be the ideal of S generated by
d
the set of all ti tj j such that 1 ≤ i < j ≤ s. In this section we show a formula for the degree of
S/(L, ta ) for any standard monomial ta of S/L.
Lemma 5.1. The ideal L is Cohen-Macaulay of height s − 1, has a unique irredundant primary
decomposition given by
L = q1 ∩ · · · ∩ qs ,
P
di+1
d
s
where qi = (t1 , . . . , ti−1 , ti+1 , . . . , ts ) for 1 ≤ i ≤ s, and deg(S/L) = 1 + si=2 di · · · ds .

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

15

Proof. Using induction on s and the depth lemma (see [27, Lemma 2.3.9]) it is seen that L is
Cohen-Macaulay. In particular L is unmixed. Since the radical of L is generated by all ti tj with
i < j, the minimal primes of L are p1 , . . . , ps , where pi is generated by t1 , . . . , ti−1 , ti+1 , . . . , ts .
The pi -primary component of L is uniquely determined and is given by LSpi ∩ S. Inverting the
variable ti in LSpi it follows that LSpi = qi Spi . As qi is an irreducible ideal, it is pi -primary
and one has the equality LSpi ∩ S = qi . By the additivity of the degree we obtain the required
formula for the degree of S/L.

Proposition 5.2. [27, Propositions 3.1.33 and 5.1.11] Let A = R1 /I1 , B = R2 /I2 be two
standard graded algebras over a field K, where R1 = K[x], R2 = K[y] are polynomial rings in
disjoint sets of variables and Ii is an ideal of Ri . If R = K[x, y] and I = I1 R + I2 R, then
(R1 /I1 ) ⊗K (R2 /I2 ) ≃ R/I and F (A ⊗K B, x) = F (A, x)F (B, x),
where F (A, x) and F (B, x) are the Hilbert series of A and B, respectively.
Proposition 5.3. Let ta = tar r · · · tas s be a standard monomial of S/L with respect to a monomial
order ≺. If ar ≥ 1, ai = 0 for i < r, and 1 ≤ r ≤ s, then 0 ≤ ai ≤ di − 1 for i > r and

s
X


 deg S/L −
(di − ai ) · · · (ds − as ) − 1 if r = s, as ≤ ds ,




i=2


deg S/L − 1
if r = s, as ≥ ds + 1,
a
deg S/(L, t ) =
r+1
X



(di − ai ) · · · (ds − as )
if r < s, ar ≤ dr ,
deg S/L −




i=2


deg S/L − (dr+1 − ar+1 ) · · · (ds − as )
if r < s, ar ≥ dr + 1.
d

Proof. As f = ta is not a multiple of ti tj j for i < j, we get that 0 ≤ ai ≤ di − 1 for i > r. To
show the formula for the degree we proceed by induction on s ≥ 2. In what follows we will use
the theory of Hilbert functions of graded algebras, as introduced in a classical paper of Stanley
[22]. In particular, we will freely use the additivity of Hilbert series, a formula for the Hilbert
series of a complete intersection [22, Corollary 3.3], the formula of Lemma 5.1 for the degree of
S/L, and the fact that any monomial is a zero-divisor of S/L (this follows from Lemma 5.1).
We split the proof of the case s = 2 in three easy cases.
Case (1): Assume s = 2, r = 1. This case is independent of whether a1 ≤ d1 or a1 ≥ d1 + 1
because the two possible values of deg S/(L, f ) coincide. There are exact sequences
d2

t

2
0 −→ S/(t1 )[−d2 ] −→
S/(L, f ) −→ S/(td22 , f ) −→ 0,
a1

t

1
0 −→ S/(ta22 )[−a1 ] −→
S/(td22 , f ) −→ S/(td22 , ta11 ) −→ 0.

Taking Hilbert series we get
xa1 (1 + x + · · · + xa2 −1 )
xd2
+
+
F (S/(L, f ), x) =
1−x
1−x

dX
2 −1
i=0

x

i

!

aX
1 −1

x

i

i=0

!

.

Writing F (S/(L, f ), x) = h(x)/(1 − x) with h(x) ∈ Z[x] and h(1) > 0, and noticing that h(1) is
the degree of S/(L, f ), we get
deg S/(L, f ) = 1 + a2 = (d2 + 1) − (d2 − a2 ) = deg(S/L) − (d2 − a2 ).
Case (2): Assume s = 2, r = 2, a2 ≤ d2 . In this case (L, f ) is equal to (ta22 ). Thus
deg S/(L, f ) = a2 = (1 + d2 ) − (d2 − a2 ) − 1 = deg S/L − (d2 − a2 ) − 1.

16

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

Case (3): Assume s = 2, r = 2, a2 ≥ d2 + 1. Taking Hilbert series in the exact sequence
d2

t

2
0 −→ S/(t1 , t2a2 −d2 )[−d2 ] −→
S/(L, f ) −→ S/(td22 ) −→ 0,

we obtain
(1 + x + · · · + xd2 −1 )
.
1−x
Thus we may proceed as in Case (1) to get deg(S/(L, f )) = d2 = deg(S/L) − 1.
This completes the initial induction step. We may now assume that s ≥ 3 and split the proof
in three cases.
Case (I): Assume r = s ≥ 3 and as ≤ ds . Thus f = tas s and ai = 0 for i < s. Setting L′ equal
d
to the ideal generated by the set of all ti tj j such that 2 ≤ i < j ≤ s, there is an exact sequence
F (S/(L, f ), x) = xd2 (1 + x + · · · + xa2 −d2 −1 ) +

t

d

1
s−1
0 −→ S/(td22 , . . . , ts−1
S/(L, tas s ) −→ S/(L′ , tas s , t1 ) −→ 0.
, tas s )[−1] −→

Taking Hilbert series one has
d

s−1
F (S/(L, tas s ), x) = xF (S/(td22 , . . . , ts−1
, tas s ), x) + F (S/(L′ , tas s , t1 ), x).

Hence, setting S ′ = K[t2 , . . . , ts ], from the induction hypothesis applied to S ′ /(L′ , tas s ), and
using that deg S ′ /L′ = deg S/L − d2 · · · ds−1 ds (see Lemma 5.1), we obtain
s
X
′
′
di · · · ds−1 (ds − as ) − 1
deg(S/(L, f )) = d2 · · · ds−1 as + deg(S /L ) −
i=3

= deg(S/L) −

s
X

di · · · ds−1 (ds − as ) − 1.

i=2

Case (II): Assume r = s ≥ 3 and as ≥ ds + 1. Using the exact sequence
t

d

1
s−1
0 −→ S/(td22 , . . . , ts−1
, tds s )[−1] −→
S/(L, tas s ) −→ S/(L′ , tas s , t1 ) −→ 0,

we can proceed as in Case (I) to get deg(S/(L, f )) = deg(S/L) − 1.
Case (III): Assume r < s. Then, by assumption, as < ds . Let L′ be the ideal generated by
d
as−1
the set of all ti tj j such that 1 ≤ i < j ≤ s − 1. Setting f ′ = tar r · · · ts−1
and S ′ = K[t1 , . . . , ts−1 ],
there are exact sequences
tds

s
0 −→ S/(t1 , . . . , ts−1 )[−ds ] −→
S/(L, f ) −→ S/(L′ , f, tds s ) −→ 0,

tas

s
0 −→ S/(L′ , f ′ , tds s −as )[−as ] −→
S/(L′ , f, tds s ) −→ S/(L′ , tas s ) −→ 0.

Hence taking Hilbert series, and applying Proposition 5.2, we get
xds
+ F (S ′ /(L′ , f ′ ), x)F (K[ts ]/(tds s −as ), x) + F (S ′ /L′ , x)F (K[ts ]/(tas s ), x).
1−x
Writing F (S/(L, f ), x) = h(x)/(1 − x) with h(x) ∈ Z[x] and h(1) > 0, and noticing that h(1) is
the degree of S/(L, f ), the induction hypothesis applied to S ′ /(L′ , f ′ ) yields the equality
!
r+1
X
(di − ai ) · · · (ds−1 − as−1 ) (ds − as ) + (deg S ′ /L′ )as
deg S/(L, f ) = 1 + deg S ′ /L′ −
F (S/(L, f ), x) =

i=2
r+1
X

= 1 + (deg S ′ /L′ )ds −

(di − ai ) · · · (ds − as ) if ar ≤ dr .

i=2

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

17

or the equality

deg S/(L, f ) = 1 + deg S ′ /L′ − (dr+1 − ar+1 ) · · · (ds−1 − as−1 ) (ds − as ) + deg(S ′ /L′ )as
= 1 + deg(S ′ /L′ )ds − (dr+1 − ar+1 ) · · · (ds − as ) if ar ≥ dr + 1.

To complete the proof it suffices to notice that deg(S/L) = 1 + deg(S ′ /L′ )ds . This equality
follows readily from Lemma 5.1.

Remark 5.4. Cases (1), (2), and (3) can also be shown using Hilbert functions instead of
Hilbert series, but case (III) is easier to handle using Hilbert series.
Lemma 5.5. Let a1 , . . . , ar , a, b, e be positive integers with e ≥ a. Then
(a) a1 · · · ar ≥ (a1 + · · · + ar ) − (r − 1), and
(b) a(e − b) ≥ (a − b)e.
Proof. Part (a) follows by induction on r, and part (b) is straightforward.



The next inequality is a generalization of part (a).
Lemma 5.6. Let 1 ≤ e1 ≤ · · · ≤ em and 0 ≤ bi ≤ ei − 1 for i = 1, . . . , m be integers. Then
!
m
k
m
X
X
Y
bi ek+1 · · · em
(ei − bi ) − (k − 1) −
(ei − bi ) ≥
(5.1)
i=1

i=1

for k = 1, . . . , m, where ek+1 · · · em = 1 and

i=k+1

Pm

i=k+1 bi

= 0 if k = m.

Pk
Proof. Fix m and 1 ≤ k ≤ m. We will proceed by induction
Pbi − 1). If σ = 0,
Pm on σ = i=1 (ei −
then ei − bi − 1 = 0 for i = 1, . . . , k. Thus either 1 − i=k+1 bi < 0 or 1 − m
i=k+1 bi ≥ 1. In
the first case the inequality is clear because the left hand side of Eq. (5.1) is positive and in the
second case one has bi = 0 for i = k + 1, . . . , m and equality holds in Eq. (5.1). Assume that
σ > 0. If k = m or bi = 0 for i = k + 1, . . . , m, the inequality follows at once from Lemma 5.5(a).
Thus, we may assume k < m and bj > 0 for some k + 1 ≤ j ≤ m. To simplify notation, and
without loss of generality, we may assume that j = m, that is, bm > 0. If the right hand side of
Eq. (5.1) is negative or zero, the inequality holds. Thus we may also assume that
(5.2)

m
k
X
X
bi ≥ k.
(ei − bi ) −
i=1

i=k+1

Hence there is 1 ≤ ℓ ≤ k such that eℓ − bℓ ≥ 2.
Case (1): Assume eℓ − bℓ − bm ≥ 1. Setting a = eℓ − bℓ , e = em , and b = bm in Lemma 5.5(b),
we get
(5.3)

(eℓ − bℓ )(em − bm ) ≥ (eℓ − (bℓ + bm ))em .

Therefore using Eq. (5.3), and then applying the induction hypothesis to the two sequences of
integers
e1 , . . . , eℓ−1 , eℓ , eℓ+1 , . . . , em−1 , em ; b1 , . . . , bℓ−1 , bℓ + bm , bℓ+1 , . . . , bm−1 , 0,

18

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

we get the inequalities


m
Y
Y
(ei − bi ) (eℓ − bℓ )(em − bm )
(ei − bi ) = 
i=1

i∈{ℓ,m}
/



≥ 


≥ 

Y

(ei − bi ) (eℓ − (bℓ + bm ))em

i∈{ℓ,m}
/
k
X

(ei − bi ) + (eℓ − (bℓ + bm )) − (k − 1) −

m−1
X

i=k+1

ℓ6=i=1

k
X

=



m
X

(ei − bi ) − (k − 1) −

i=1

bi

i=k+1

!



bi  ek+1 · · · em

ek+1 · · · em .

Case (2): Assume eℓ − bℓ − bm < 1. Setting rℓ = eℓ − bℓ − 1 ≥ 1, one has
bℓ + rℓ = eℓ − 1 ≥ 1, bm − rℓ ≥ 1, eℓ − (bℓ + rℓ ) = 1.
On the other hand, by Lemma 5.5(a), one has
(5.4)

(eℓ − bℓ )(em − bm ) ≥ (eℓ − bℓ ) + (em − bm ) − 1 = (eℓ − (bℓ + rℓ ))(em − (bm − rℓ )).

Therefore using Eq. (5.4), and then applying the induction hypothesis to the two sequences of
integers
e1 , . . . , eℓ−1 , eℓ , eℓ+1 , . . . , em−1 , em ; b1 , . . . , bℓ−1 , bℓ + rℓ , bℓ+1 , . . . , bm−1 , bm − rℓ ,
we get the inequalities


m
Y
Y
(ei − bi ) = 
(ei − bi ) (eℓ − bℓ )(em − bm )
i=1

i∈{ℓ,m}
/



≥ 

Y

i6={ℓ,m}



≥ 

k
X



(ei − bi ) (eℓ − (bℓ + rℓ ))(em − (bm − rℓ ))

(ei − bi ) + (eℓ − (bℓ + rℓ )) − (k − 1) −

ℓ6=i=1

i=k+1

m
k
X
X
(ei − bi ) − (k − 1) −
bi

=

m−1
X

i=1

i=k+1

!



bi − (bm − rℓ ) ek+1 · · · em

ek+1 · · · em . ✷

Proposition 5.7. Let 1 ≤ e1 ≤ · · · ≤ em and 0 ≤ bi ≤ ei − 1 for i = 1, . . . , m be integers. If
b0 ≥ 1, then
!
m
k+1
m
X
X
Y
(ei − bi ) − (k − 1) − b0 −
(ei − bi ) ≥
bi ek+2 · · · em
(5.5)
i=1

i=1

for k = 0, . . . , m − 1, where ek+2 · · · em = 1 and

i=k+2

Pm

i=k+2 bi

= 0 if k = m − 1.

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

19

Proof. If 0 ≤ k ≤ m − 1, then 1 ≤ k + 1 ≤ m. Applying Lemma 5.6, and making the substitution
k → k + 1 in Eq. (5.5), we get
!
m
k+1
m
X
X
Y
(ei − bi ) − k −
(ei − bi ) ≥
bi ek+2 · · · em
i=1

i=1

≥

i=k+2

m
k+1
X
X
(ei − bi ) − (k − 1) − b0 −
bi
i=1

i=k+2

!

ek+2 · · · em ,

where the second inequality holds because b0 ≥ 1.



6. Projective nested cartesian codes
In this section we introduce projective nested cartesian codes, a type of evaluation codes that
generalize the classical projective Reed–Muller codes [21]. As an application we will give some
support to a conjecture of Carvalho, Lopez-Neumann and López.
Let K = Fq be a finite field, let A1 , . . . , As be a collection of subsets of K, and let
X = [A1 × · · · × As ]
be the image of A1 × · · · × As \ {0} under the map K s \ {0} → Ps−1 , x → [x].
Definition 6.1. [3] The set X is called a projective nested cartesian set if
(i) {0, 1} ⊂ Ai for i = 1, . . . , s,
(ii) a/b ∈ Aj for 1 ≤ i < j ≤ s, a ∈ Aj , 0 6= b ∈ Ai , and
(iii) d1 ≤ · · · ≤ ds , where di = |Ai | for i = 1, . . . , s.
If X is a projective nested cartesian set, we call CX (d) a projective nested cartesian code.
Conjecture 6.2. (Carvalho, Lopez-Neumann, and López [3]) Let CX (d) be the d-th projective
nested cartesian code on the set X = [A1 × · · · × As ] with di = |Ai | for i = 1, . . . , s. Then its
minimum distance is given by

s
P


(di − 1) ,
 (dk+2 − ℓ + 1) dk+3 · · · ds if d ≤
i=2
δX (d) =
s
P


1
if d ≥
(di − 1) + 1,

i=2

where 0 ≤ k ≤ s − 2 and ℓ are the unique integers such that d =
1 ≤ ℓ ≤ dk+2 − 1.

Pk+1
i=2

(di − 1) + ℓ and

In what follows X = [A1 × · · · × As ] denotes a projective nested cartesian set and CX (d)
is its corresponding d-th projective Reed-Muller-type code. Throughout this section ≺ is the
lexicographical order on S with t1 ≺ · · · ≺ ts and in≺ (I(X )) is the initial ideal of I(X ).
d

Proposition 6.3. [3] The initial ideal in≺ (I(X )) is generated by the set of all monomials ti tj j
such that 1 ≤ i < j ≤ s,
s
s
X
X
(di − 1).
di · · · ds , and reg(S/I(X )) = 1 +
deg(S/I(X )) = 1 +
i=2

i=2

Carvalho, Lopez-Neumann and López, showed the conjecture when the Ai ’s are subfields of
Fq . They also showed that the conjecture can be reduced to:

20

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

Conjecture 6.4. (Carvalho, Lopez-Neumann, and López [3]) If 0 6= P
f ∈ Sd is a standard
polynomial, with respect to ≺, such that (I(X ) : f ) 6= I(X ) and 1 ≤ d ≤ si=2 (di − 1), then

|VX (f )| ≤ deg(S/I(X )) − (dk+2 − ℓ + 1) dk+3 · · · ds ,
P
where 0 ≤ k ≤ s − 2 and ℓ are integers such that d = k+1
i=2 (di − 1) + ℓ and 1 ≤ ℓ ≤ dk+2 − 1.
We show a degree formula and use this to give an upper bound for |VX (f )|.

Theorem 6.5. Let ≺ be the lexicographical order on S with t1 ≺ · · · ≺ ts and let f 6= 0 be a
standard polynomial with in≺ (f ) = tar r · · · tas s and ar ≥ 1. Then 0 ≤ ai ≤ di − 1 for i > r and
|VX (f )| ≤ deg(S/(in≺ (I(X )), in≺ (f )))

r+1
X


(di − ai ) · · · (ds − as )
deg(S/I(X )) −
=
i=2


deg(S/I(X )) − (dr+1 − ar+1 ) · · · (ds − as )

if ar ≤ dr ,
if ar ≥ dr + 1,

where (di − ai ) · · · (ds − as ) = 1 if i > s and ai = 0 for i < r.

d

Proof. By Proposition 6.3 the initial ideal of I(X ) is generated by the set of all ti tj j such that
1 ≤ i < j ≤ s and the degree of S/(in≺ (I(X )) is equal to the degree of S/I(X ). As in≺ (f )
is a standard monomial, it follows that 0 ≤ ai ≤ di − 1 for i > r. Notice that if f is not a
zero-divisor of S/I(X ), then VX (f ) = ∅. Thus the inequality follows at once from Corollary 4.3
and the equality follows from Proposition 5.3.

The next result gives some support for Conjecture 6.4.
Theorem 6.6. Let ≺ be the lexicographical
P order on S with t1 ≺ · · · ≺ ts . If 0 6= f ∈ Sd is a
standard polynomial such that 1 ≤ d ≤ si=2 (di − 1) and t1 divides in≺ (f ), then
|VX (f )| ≤ deg(S/I(X )) − (dk+2 − ℓ + 1) dk+3 · · · ds ,
P
where 0 ≤ k ≤ s − 2 and ℓ are integers such that d = k+1
i=2 (di − 1) + ℓ and 1 ≤ ℓ ≤ dk+2 − 1.

Proof. By Lemma 3.2 we may assume that (I(X ) : f ) 6= I(X ). Let ta = in≺ (f ) be the initial
monomial of f . By Proposition 6.3, we can write
ta = ta11 · · · tas s ,
with a1 ≥ 1, 0 ≤ ai ≤ di − 1 for i > 1. By Lemmas 3.2 and 4.1 it suffices to show that the
following inequality holds
deg(S/(in≺ (I(X )), ta )) ≤ deg(S/I(X )) − (dk+2 − ℓ + 1) dk+3 · · · ds .
Ps
P
If we substitute −ℓ = k+1
i=2 (di − 1) −
i=1 ai in Eq. (6.1), and use the formula for the degree
of S/(in≺ (I(X )), ta ) given in Theorem 6.5, we need only show that the following inequalities
hold for r = 1:
r+1
X
(6.2)
(di − ai ) · · · (ds − as ) ≥
(6.1)

i=2

k+2
X

(di − ai ) − (k − 1) − a1 −

i=2

(6.3)

s
Y

(di − ai ) ≥

i=r+1

s
X

i=k+3

k+2
X

(di − ai ) − (k − 1) − a1 −

i=2

ai

s
X

!

i=k+3

dk+3 · · · ds if ar ≤ dr ,

ai

!

dk+3 · · · ds if ar ≥ dr + 1,

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

21

for 0 ≤ k ≤ s − 2, where (di − ai ) · · · (ds − as ) = 1 if i > s and ai = 0 for i < r.
Assume r = 1. Then Eqs. (6.2) and (6.3) are the same. Thus we need only show the inequality
s
Y
(di − ai ) ≥
i=2

s
k+2
X
X
ai
(di − ai ) − (k − 1) − a1 −
i=2

i=k+3

!

dk+3 · · · ds ,

for 0 ≤ k ≤ s−2. This inequality follows making m = s−1, ei = di+1 , bi = ai+1 for i = 1, . . . , m,
and b0 = a1 in Proposition 5.7.

The following resembles Conjecture 6.2 when d = 1:
Conjecture 6.7. [25, Conjecture 4.9] Let X be a finite set of points in Ps−1 . If I(X) is a complete
intersection generated by f1 , . . . , fs−1 , with ei = deg(fi ) for i = 1, . . . , s − 1, and 2 ≤ ei ≤ ei+1
for all i, then δX (1) ≥ (e1 − 1)e2 · · · es−1 .
Next we show that the corresponding conjecture is true for projective nested cartesian codes
by proving that Conjecture 6.2 is true for d = 1.
Proposition 6.8. δX (1) = d2 · · · ds .
Proof. It suffices to show that Conjecture 6.4 is true for d = 1, that is, if 0 6= f ∈ S1 is a
standard polynomial such that (I(X ) : f ) 6= I(X ), then we must show the inequality
|VX (f )| ≤ deg(S/I(X )) − d2 · · · ds .
As in≺ (f ) = tr for some 1 ≤ r ≤ s, we can write in≺ (f ) = ta11 · · · tar r · · · tas s , where ar = 1,
ai = 0 for i 6= r, and 2 ≤ d2 ≤ · · · ≤ ds . Therefore, by Theorem 6.5, we get
|VX (f )| ≤ deg(S/I(X )) −

r+1
X

(di − ai ) · · · (ds − as ),

i=2

where (di − ai ) · · · (ds − as ) = 1 if i > s. Hence the proof reduces to showing the inequality
r+1
X
(di − ai ) · · · (ds − as ) ≥ d2 · · · ds .
i=2

If r = s, this inequality follows readily by induction on s ≥ 2. If r < s the inequality also
follows by induction on s by noticing that, in this case, both sides of the inequality have ds as
a common factor because ds appears in all terms of the summation of the left hand side.

Let Ld be the K-vector space generated by all ta ∈ Sd such that t1 divides ta and let Cd be
the image of Ld under the evaluation map evd . From the next result it follows that the minimum
distance of CX (d) proposed in Conjecture 6.2 is in fact the minimum distance of the evaluation
linear code Cd .
CorollaryP
6.9. Let Ld be the K-vector space generated by all ta ∈ Sd such that ta contains t1 .
If 1 ≤ d ≤ si=2 (di − 1), then

max{|VX (f )| : f ∈
/ I(X ), f ∈ Ld } = deg(S/I(X )) − (dk+2 − ℓ + 1) dk+3 · · · ds ,
P
where 0 ≤ k ≤ s − 2 and ℓ are integers, d = k+1
i=2 (di − 1) + ℓ, and 1 ≤ ℓ ≤ dk+2 − 1.

22

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

Proof. Take f ∈ Ld \ I(X ). Let ≺ be the lexicographical order with t1 ≺ · · · ≺ ts and let G
be the Gröbner
P basis of I(X ) given in [3, Proposition 2.14]. By the division algorithm, we can
write f = ri=1 ai gi + g, where gi ∈ G for all i and g is a standard polynomial of degree d.
The polynomial g is again in Ld \ I(X ). Indeed if g ∈
/ Ld , there is at least one monomial of g
thatP
do not contain t1 , then making t1 = 0 in the last equality, we get an equality of the form
0 = ri=1 bi gi + h, where h is a non-zero standard polynomial of I(X ), a contradiction. Hence,
by Theorem 6.6, the inequality ≤ follows because |VX (f )| = |VX (g)|. To show equality notice
that according to the proof of [3, Lemma 3.1], there is a polynomial f of degree d in Ld \ I(X )
whose number of zeros in X is equal to the right hand side of the required equality.

7. Examples
In this section we show some examples that illustrates how some of our results can be used
in practice.
Example 7.1. Let K be the field F3 , let X be the subset of P3 given by
X = {[e1 ], [e2 ], [e3 ], [e4 ], [(1, −1, −1, 1)], [(1, 1, 1, 1)], [(−1, −1, 1, 1)], [(−1, 1, −1, 1)]},
where ei is the i-th unit vector, and let I = I(X) be the vanishing ideal of X. Using Lemma 2.9
and Macaulay2 [13], we get that I is the ideal of S = K[t1 , t2 , t3 , t4 ] generated by the binomials
t1 t2 − t3 t4 , t1 t3 − t2 t4 , t2 t3 − t1 t4 . Hence, using Theorem 4.4 and the procedure below for
Macaulay2 [13], we get
d
deg(S/I)
HI (d)
δI (d)

1
8
4
4

2
8
7
2

3
8
8
1

···
···
···
···

q=3
S=ZZ/q[t1,t2,t3,t4]
I=ideal(t1*t2-t3*t4,t1*t3-t2*t4,t2*t3-t1*t4)
M=coker gens gb I
h=(d)->min apply(apply(apply(apply(toList
(set(0..q-1))^**(hilbertFunction(d,M))(set{0})^**(hilbertFunction(d,M)),toList),x->basis(d,M)*vector x),
z->ideal(flatten entries z)),x-> degree quotient(I,x))
apply(1..2,h)--this gives the minimum distance in degrees 1,2
Example 7.2. Let X be the set in P3 parameterized by y1 y2 , y2 y3 , y3 y4 , y1 y4 over the field F3 .
Using Corollary 4.8, Theorem 4.10, and the following procedure for Macaulay2 [13] we get
1 2 3 ···
d
|X|
16 16 16 · · ·
HX (d)
4 9 16 · · ·
δX (d)
9 4 1 ···
fpI(X) (d) 6 3 1 · · ·
q=3
R=ZZ/q[y1,y2,y3,y4,z,t1,t2,t3,t4,MonomialOrder=>Eliminate 5];
f1=y1*y2, f2=y2*y3, f3=y3*y4, f4=y4*y1
J=ideal(y1^q-y1,y2^q-y2,y3^q-y3,y4^q-y4,t1-f1*z,t2-f2*z,t3-f3*z,t4-f4*z)

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

23

C4=ideal selectInSubring(1,gens gb J)
S=ZZ/q[t1,t2,t3,t4];
I=sub(C4,S)
M=coker gens gb I
h=(d)->degree M - max apply(apply(apply(apply(
toList (set(0..q-1))^**(hilbertFunction(d,M))(set{0})^**(hilbertFunction(d,M)), toList),x->basis(d,M)*vector x),
z->ideal(flatten entries z)),x-> if not
quotient(I,x)==I then degree ideal(I,x) else 0)--The function h(d)
--gives the minimum distance in degree d
h(1), h(2)
f=(x1) -> degree ideal(x1,leadTerm gens gb I)
fp=(d)->degree M - max apply(flatten entries basis(d,M),f)--The
--function fp(d) gives the footprint in degree d
L=toList(1..regularity M)
apply(L,fp)
Example 7.3. Let X be a projective torus in P2 over the field K = F3 . The vanishing ideal
I = I(X) is generated by t21 − t23 , t22 − t23 . The polynomial F = (t1 − t2 )d is a zero-divisor of S/I
because (t1 − t3 , t2 − t3 ) is an associated prime of S/I and F ∈
/ I because F does not vanish at
[(1, −1)]. Hence, Fd 6= ∅. If ≺ is the lexicographical order t1 ≻ t2 ≻ t3 , then td3 is a standard
monomial which is not a zero-divisor of S/I and S/in≺ (I). This causes deg(S/(in≺ (I), t23 )) to
be greater than deg(S/I). Using Macaulay2 [13] we obtain
d
|X|
HI (d)
δI (d)
fpI (d)

1
2
4
4
3
4
2
1
0 −4

···
···
···
···
···

Let CX (d) be a projective Reed-Muller-type code. If d ≥ reg(S/I(X)), then δX (d) = 1. The
converse is not true as the next example shows.
Example 7.4. Let X = {[(1, 1, 1)], [(1, −1, 0)], [(1, 0, −1)], [(0, 1, −1)], [(1, 0, 0)]} and let I be its
vanishing ideal over the finite field F3 . Using Macaulay2 [13] we obtain that reg(S/I) = 3.
Notice that δX (1) = 1 because the polynomial t1 + t2 + t3 vanishes at all points of X \ {[(1, 0, 0)]}.
The next example shows that δI is not in general non-increasing. This is why we often require
that the dimension of I be at least 1 or that I is unmixed with at least 2 minimal primes.
Example 7.5. Let I be the ideal of F5 [t1 , t2 ] generated by t71 , t52 , t21 t2 , t1 t32 . Using Corollary 4.8
and Macaulay2 [13] we get that the regularity of S/I is 7, that is, HI (d) = 0 for d ≥ 7, and
1 2 3 4 5 6 ···
d
deg(S/I) 13 13 13 13 13 13 · · ·
HI (d)
2 3 3 2 1 1 ···
δI (d)
6 2 1 1 2 1 ···
Acknowledgments. We thank the referee for a careful reading of the paper and for the
improvements suggested.

24

JOSÉ MARTÍNEZ-BERNAL, YURIKO PITONES, AND RAFAEL H. VILLARREAL*

References
[1] W. Bruns and J. Herzog, Cohen-Macaulay Rings, Revised Edition, Cambridge University Press, 1997.
[2] C. Carvalho, On the second Hamming weight of some Reed-Muller type codes, Finite Fields Appl. 24 (2013),
88–94.
[3] C. Carvalho, V. G. Lopez Neumann and H. H. López, Projective nested cartesian codes. Preprint 2014,
arXiv:1411.6819.
[4] D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, Springer-Verlag, 1992.
[5] I. M. Duursma, C. Renterı́a and H. Tapia-Recillas, Reed-Muller codes on complete intersections, Appl.
Algebra Engrg. Comm. Comput. 11 (2001), no. 6, 455–462.
[6] D. Eisenbud, Commutative Algebra with a view toward Algebraic Geometry, Graduate Texts in Mathematics
150, Springer-Verlag, 1995.
[7] D. Eisenbud, The geometry of syzygies: A second course in commutative algebra and algebraic geometry,
Graduate Texts in Mathematics 229, Springer-Verlag, New York, 2005.
[8] O. Geil, On the second weight of generalized Reed-Muller codes, Des. Codes Cryptogr. 48 (2008), 323–330.
[9] O. Geil and C. Thomsen, Weighted Reed–Muller codes revisited, Des. Codes Cryptogr. 66 (2013), 195–220.
[10] A. V. Geramita, M. Kreuzer and L. Robbiano, Cayley-Bacharach schemes and their canonical modules,
Trans. Amer. Math. Soc. 339 (1993), no. 1, 163–189.
[11] L. Gold, J. Little and H. Schenck, Cayley-Bacharach and evaluation codes on complete intersections, J. Pure
Appl. Algebra 196 (2005), no. 1, 91–99.
[12] M. González-Sarabia, C. Renterı́a and H. Tapia-Recillas, Reed-Muller-type codes over the Segre variety,
Finite Fields Appl. 8 (2002), no. 4, 511–518.
[13] D. Grayson and M. Stillman, Macaulay2, 1996. Available via anonymous ftp from math.uiuc.edu.
[14] H. H. López, C. Renterı́a and R. H. Villarreal, Affine cartesian codes, Des. Codes Cryptogr. 71 (2014), no.
1, 5–19.
[15] H. H. López, E. Sarmiento, M. Vaz Pinto and R. H. Villarreal, Parameterized affine codes, Studia Sci. Math.
Hungar. 49 (2012), no. 3, 406–418.
[16] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-correcting Codes, North-Holland, 1977.
[17] L. O’Carroll, F. Planas-Vilanova and R. H. Villarreal, Degree and algebraic properties of lattice and matrix
ideals, SIAM J. Discrete Math. 28 (2014), no. 1, 394–427.
[18] SAGE Mathematical Software, http://www.sagemath.org.
[19] C. Renterı́a, A. Simis and R. H. Villarreal, Algebraic methods for parameterized codes and invariants of
vanishing ideals over finite fields, Finite Fields Appl. 17 (2011), no. 1, 81–104.
[20] E. Sarmiento, M. Vaz Pinto and R. H. Villarreal, The minimum distance of parameterized codes on projective
tori, Appl. Algebra Engrg. Comm. Comput. 22 (2011), no. 4, 249–264.
[21] A. Sørensen, Projective Reed-Muller codes, IEEE Trans. Inform. Theory 37 (1991), no. 6, 1567–1576.
[22] R. Stanley, Hilbert functions of graded algebras, Adv. Math. 28 (1978), 57–83.
[23] A. Tochimani and R. H. Villarreal, Vanishing ideals over rational parameterizations. Preprint, 2015,
arXiv:1502.05451v1.
[24] S. Tohǎneanu, Lower bounds on minimal distance of evaluation codes, Appl. Algebra Engrg. Comm. Comput.
20 (2009), no. 5-6, 351–360.
[25] S. Tohǎneanu and A. Van Tuyl, Bounding invariants of fat points using a coding theory construction, J. Pure
Appl. Algebra 217 (2013), no. 2, 269–279.
[26] M. Tsfasman, S. Vladut and D. Nogin, Algebraic geometric codes: basic notions, Mathematical Surveys and
Monographs 139, American Mathematical Society, Providence, RI, 2007.
[27] R. H. Villarreal, Monomial Algebras, Second Edition, Monographs and Research Notes in Mathematics,
Chapman and Hall/CRC, 2015.

MINIMUM DISTANCE FUNCTIONS AND REED-MULLER-TYPE CODES

25

Departamento de Matemáticas, Centro de Investigación y de Estudios Avanzados del IPN,
Apartado Postal 14–740, 07000 Mexico City, D.F.
E-mail address: jmb@math.cinvestav.mx
Departamento de Matemáticas, Centro de Investigación y de Estudios Avanzados del IPN,
Apartado Postal 14–740, 07000 Mexico City, D.F.
E-mail address: ypitones@math.cinvestav.mx
Departamento de Matemáticas, Centro de Investigación y de Estudios Avanzados del IPN,
Apartado Postal 14–740, 07000 Mexico City, D.F.
E-mail address: vila@math.cinvestav.mx

