arXiv:1710.01435v1 [math.AC] 4 Oct 2017

AN ALGORITHM FOR COMPUTING THE HILBERT–SAMUEL
MULTIPLICITIES AND REDUCTIONS OF ZERO-DIMENSIONAL
IDEALS OF COHEN–MACAULAY LOCAL RINGS
TAKAFUMI SHIBUTA AND SHINICHI TAJIMA

Abstract. In this paper, we present an algorithm for computing the minimal
reductions of m-primary ideals of Cohen–Macaulay local rings. Using this
algorithm, we are able to compute the Hilbert–Samuel multiplicities and solve
the membership problem for the integral closure of m-primary ideals.

1. Introduction
Let (R, m, K) be a Noetherian local ring, and J ⊂ R a m-primary ideal. The
Hilbert–Samuel multiplicity is one of the most important invariant in the commutative ring theory. The Hilbert–Samuel multiplicity eR (J) of J is defined by
d!
ℓ(R/J k )
k→∞ k d
were ℓ(M ) denotes the length of an R-module M . The Hilbert–Samuel multiplicities
has deep relation with integral closure of ideals. If R is formally equidimensional,
for m-primary ideals J1 ⊂ J2 ⊂ R, eR (J1 ) = eR (J2 ) if and only if J2 ⊂ J 1 [4]. In [3],
Mora and Rossi gave an algorithm for computing the Hilbert–Samuel multiplicities
of primary ideals. An ideal Q ⊂ J is called a reduction of J if there exists r > 0
satisfying QJ r = J r+1 . It is known that e(Q) = e(J) holds if Q is a reduction of
J.
In this paper, we give an algorithm for computing reductions of m-primary ideals
when R is a Cohen-Macaulay ring of dimension d. As application of this algorithm,
we can compute the Hilbert–Samuel multiplicities, and can solve the membership
problem for integral closures. Since it is known that d generic linear combinations
of a system of generators ideals generate a reduction, one can construct probabilistic algorithm for computing reductions of ideals if the coefficient field is infinite.
However, this method is probabilistic, and the size of coefficients of the output
can be large. If the coefficient field is finite, this method can not be applied. Our
algorithm is deterministic. We also give a way of computing reductions with small
coefficients. The membership problem for integral closure of ideals can be solved
using the algorithm for computing reductions of ideals. Our algorithm works even
if the input ideal is generated by formal series with infinitely many terms.
eR (J) = lim

2. Preliminaries
In this paper, S = KJxK = KJx1 , . . . , xn K denotes a formal series ring in indeterminates x = (x1 , . . . , xn ) over arbitrary field K. We denote by m the unique
1 +1
maximal ideal of S. We write x1 = x1 · · · xn and xα+1 = xα
· · · xnαn +1 for
1
α = (α1 , . . . , αn ). For a ring R and an R-module M , we denote by ℓR (M ) = ℓ(M )
1

2

TAKAFUMI SHIBUTA AND SHINICHI TAJIMA

the length of M . For B ⊂ M , hBiR = hBi denotes R-submodule of M generated
by B.
2.1. Matlis duality. Our algorithm is based of Matlis duality theorem. Here, we
give a brief review of Matlis duality. Let E = ES the injective hull of the residue
field S/m of S. It is known that E is isomorphic to the top local cohomology group
n
n
Hm
(S) ([1] Proposition 3.5.4). The local cohomology module Hm
(S) has a relative
Čech cohomology representation
n
−1
Hm
(S) ∼
= K[x−1
1 , . . . , xn ]

with an S-module structure defined by


1

1
β−α+1
xα · β+1 =
x

x
 0

1
x1 · · · xn

if β − α ∈ Zn≥0 ,
otherwise.

and its bilinear extension. In this paper, we identify E with the above Čech cohon
mology representation of Hm
(S),
−1
E = K[x−1
1 , . . . , xn ]

1
,
x1 · · · xn

1
and we call α+1 a term of E. An S-submodule of E generated by terms is called
x
a term module in this paper.
Definition 2.1. For an S-module M , we write M ∨ := HomS (M, E). The functor
(−)∨ = HomS (−, E) is called the Matlis duality functor.
Now, we recall the Matlis duality theorem.
Theorem 2.2 (Matlis). Let M be a Noetherian S-module, and N an Artinian
S-module. Then the following hold.
(1) S ∨ ∼
= S.
= E, and E ∨ ∼
∨
(2) M is Artinian, and N ∨ is Noetherian.
(3) There are natural isomorphism M ∨∨ ∼
= N.
= M and N ∨∨ ∼
If M is of finite length, then ℓ(M ) = ℓ(M ∨ ). For an ideal J ⊂ S, we can identify
(S/J)∨ with the submodule {η ∈ E | Jη = 0} of E. By Theorem 2.2, for f ∈ S,
f ∈ J if and only if f η = 0 for all η ∈ (S/J)∨ .
2.2. Integral closure. Here, we recall some basic facts on the integral closure
of ideals. See [1] Section 4, and [2] for details. Let (R, n, K) be a local ring of
dimension d, and J ⊂ R a n-primary ideal.
Definition 2.3. We say that x ∈ R is integral over J if there exists m ∈ N and
ci ∈ J i such that
xm + c1 xm−1 + · · · + cm = 0.
Theorem 2.4. Let OCd ,O be the ring of analytic germs at the origin O ∈ Cd . Let
J = hf¯1 , . . . , f¯r i ⊂ OCd ,O and g ∈ OCd ,O . Then the following are equivalent.
(1) g ∈ J.

AN ALGORITHM FOR THE HILBERT–SAMUEL MULTIPLICITIES

3

(2) There exist a open neighborhood U of O and a constant C > 0, such that,
for any x ∈ U , it holds that
|g(x)| ≤ C(|f¯1 (x)| + · · · |f¯r (x)|).
(3) g ∈ H 0 (X, OX (−F )) where X → (Cd , O) is a log resolution of J, and F is
the divisor JOX = OX (−F ).
See [6] for the equivalence of (i) and (ii).
Example 2.5. Let J = hx2 , y 2 i ⊂ OC2 ,O , g = xy. Then g ∈ J since g 2 − c = 0
where c = x2 y 2 ∈ J 2 .
As |xy| ≤ 12 (|x2 | + |y 2 |), g and J satisfy (2).
The blowing-up X → C2 of C2 at the origin is a log resolution of J. Then
X = U ∪ V where U = {(x, y/x) | x 6= 0} and V = {(x/y, y) | y 6= 0}. On
U , g = x2 · y/x ∈ JOU = hx2 , x2 (y/x)2 i = hx2 i. On V , g = y 2 · x/y ∈ JOV =
hy 2 (x/y)2 , y 2 i = hy 2 i. Thus g and J satisfy (3).
For simplicity, we consider a complete local ring R = S/I of dimension d where
S = KJx1 , . . . , xn K. We denote by n the unique maximal ideal of R.
Definition 2.6. The Hilbert–Samuel multiplicity eR (J) of an n-primary ideal J ⊂
R is defined by
d!
eR (J) = lim d ℓ(R/J k ).
k→∞ k
Definition 2.7. Let Q ⊂ J ⊂ R be ideals. Q is said to be a reduction of J if
QJ r = J r+1 for some integer r > 0.
Reductions and Hilbert–Samuel multiplicities are useful tools for theory of integral closure.
Theorem 2.8 ([4]). Assume that R = S/I is equidimension. Let J1 ⊂ J2 ⊂ R be
n-primary ideals. Then eR (J1 ) = eR (J2 ) if and only if J2 ⊂ J 1 .
By this theorem, we are able to solve the membership problem for the integral
closure of an n-primary ideal using Hilbert–Samuel multiplicity.
Proposition 2.9. Assume that R = S/I is equidimension. For f ∈ R and nprimary ideal J, f ∈ J if and only if eR (J) = eR (hJ, f i.
Since Cohen–Macaulay rings are equidimensional, this criterion is applicable if
R is Cohen–Macaulay.
Proposition 2.10. If J1 is a reduction of J2 , then eR (J1 ) = eR (J2 ).
Corollary 2.11. Assume that R is Cohen–Macaulay. Let J ⊂ R be an n-primary
ideal, and Q ⊂ an n-primary ideal generated by d elements. Then eR (J) = ℓ(R/Q)
is and only if Q is a reduction of J.
It is known that d generic liner combinations of a system of generators of J
generates a reduction of J.
Theorem 2.12. Let J = hf1 , . . . , fm i, and assume that K is an infinite field. There
existsP
a Zariski open set U ⊂ K d×m , such that for (aij )i,j ∈ U , Q = hg1 , . . . , gd i,
gj = i aij fi (1 ≤ j ≤ d), is a reduction of J.

4

TAKAFUMI SHIBUTA AND SHINICHI TAJIMA

3. Composition series with term orders
Recall that S = KJxK = KJx1 , . . . , xn K. In this section, we define term orders,
and give composition series of N ⊂ E with ℓ(N ) < ∞ uniquely determined by a
given term order. We need this composition series later for constructing algorithms.
Definition 3.1. A total order ≺ on the set of terms of E is called term order on
E if for any α, β, γ ∈ Zn≥0 , the following conditions hold
1
1
 α+1 ,
1
x
x
1
1
1
1
(2) α+1 ≺ β+1 implies α+γ+1 ≺ β+γ+1 .
x
x
x
x
In Gröbner basis theory, a total oder ≺ on the set of terms of the polynomial
ring K[x1 , . . . , xn ] is said to be a term order if for any α, β, γ ∈ Zn≥0 , the following
conditions hold (1) 1  xα , and (2) xα ≺ xβ implies xα+γ ≺ xβ+γ . Giving a
term order defined in Definition 3.1 is essentially equivalent to giving a term order
in meaning of Gröbner basis theory, thus it is easy to implement in a computer
algebra system equipped with a package for Gröbner basis. It is known that term
orders on the set of terms of the polynomial rings are well-ordering. Thus we have
the following.
(1)

Proposition 3.2. A term order on E is a well-ordering.
P

1

∈ E, and a term order ≺ on E, we call
)
(
1
cα 6= 0
LT≺ (η) := max
≺
xα+1

Definition 3.3. For η =

cα

xα+1

the leading term of η with respect to ≺.
Since any element of E has only finitely many terms, the leading term is welldefined. For a subset N ⊂ E, LT≺ (N ) = {LT≺ (η) | η ∈ N }.
Definition 3.4. For an S-submodule of E, we call N :E m := {η ∈ E | mη ∈ N }
the colon module of N .
Lemma 3.5. If η ∈ N :E m then LT≺ (η) ∈ LT≺ (N ) :E m.
Proof. For any 1 ≤ i ≤ n, xi η ∈ N . It is easy to show that LT≺ (xi η) = xi LT≺ (η)
if xi LT≺ (η) 6= 0. Thus xi LT(η) = 0 or xi LT≺ (η) ∈ LT≺ (N ) holds for any i. This
show that LT≺ (η) ∈ LT≺ (N ) :E m.

The Matlis duality of S/M where M is a monomial ideals is easy to understand.
A monomial not contained in a monomial ideal M is called a standard monomial
of M .
Lemma 3.6. Let M ⊂ S be a monomial ideal with a minimal system of monomial

r 
\
(i)
β1
βr(i)
αk
n
∨
α1
x1 , . . . , xn
generators {x , . . . , x }, αi ∈ Z≥0 , and let N = (S/M ) . Let
i=1

(i)

(i)

be the irredundant irreducible decomposition of M , and let β (i) = (β1 , . . . , βn ).
Then the following hold.

AN ALGORITHM FOR THE HILBERT–SAMUEL MULTIPLICITIES

(1)

(

1

xβ+1
space.

β

x is a standard monomial of M

(2) If ℓ(S/M ) < ∞, then

(

1
xβ (1)

,...,

1
xβ (r)

)

)

5

is a basis of N as a K-vector

is a minimal system of generators

of N .
(3) N :E m is generated by N and

(

1
xα1 +1

,...,

1
xαk +1

)

as an S-module.

For an S-submodule N ⊂ E, we define two term modules.
Definition 3.7. We denote by T1 (N ) the submodule of N generated by terms
contained in N .
Definition 3.8. We denote by T2 (N ) the submodule of E generated by terms
appearing in N .
We note that T1 (N ) ⊂ N ⊂ T2 (N ), and T1 (N ) is the maximal S-submodule of
E contained in N generated by terms of E, and T2 (N ) is the minimal S-submodule
of E containing N generated by terms of E. For an ideal J ⊂ S, let MJ be the
minimal monomial ideal containing J. Then (S/MJ )∨ = T1 (N ).
Theorem 3.9. Let N ⊂ E be an S-module of finite length. Let N0 = T1 (N ), and
define ξi and Ni inductively as follows: choose ξi ∈ N so that
LT≺ (ξi ) = min{LT≺ (η) | η ∈ N, LT≺ (η) 6∈ LT≺ (Ni−1 )},
≺

and set Ni = Ni−1 + Sξi . Then we obtain a sequence of S-modules
N0 = T1 (N ) ⊂ N1 ⊂ N2 ⊂ · · · ⊂ Nk−1 ⊂ Nk = N.
The following hold.
(1) Ni /Ni−1 ∼
= K for all 1 ≤ i ≤ k.
(2) Ni does not depend on the choice of ξi .
(3) LT≺ (ξ0 ) ≺ LT≺ (ξ1 ) ≺ · · · ≺ LT≺ (ξk−1 ) ≺ LT≺ (ξk ).
(4) ξi can be chosen so that any term of ξi is not in LT≺ (Ni−1 ), and such ξi
is unique up to multiplication by K × .
Proof. First, we claim that Ni−1 contains the set
Ai−1 := {η | η ∈ N, LT≺ (η) ≺ LT≺ (ξi )}
for all 1 ≤ i ≤ k. Assume to the contrary that Ai−1 6⊂ Ni−1 . Let η ∈ Ai−1
with LT≺ (η) minimal among those η 6∈ Ni−1 . Then, by the choice of ξi , it holds
that LT≺ (η) ∈ LT≺ (Ni−1 ). Take η ′ ∈ Ni−1 such that LT≺ (η) = LT≺ (η ′ ) and let
ζ = η − η ′ . Then ζ 6= 0, ζ ∈ N , ζ 6∈ Ni−1 , and LT≺ (ζ) ≺ LT≺ (η). As ζ ∈ Ai−1 ,
this contradicts the minimality of the leading term of η. Thus the claim is proved.
Since LT≺ (xj ξi ) ≺ LT≺ (ξi ), we have xj ξi ∈ Ai−1 ⊂ Ni−1 for any j. Thus
mξi ∈ Ni−1 which shows (1). To prove (2), assume to the contrary that LT≺ (ξi ) ≻
LT≺ (ξi+1 ) for some i. Then ξi+1 ∈ Ai−1 ⊂ Ni−1 which contradicts to ξi+1 6∈ Ni .
Thus (2) holds true. We will prove (3). Let ξ ∈ E be an element satisfying the
same conditions as ξi and ξi 6= ξ. Then ξ − ξi ∈ N and LT≺ (ξ − ξi ) ≺ LT≺ (ξi ) as

6

TAKAFUMI SHIBUTA AND SHINICHI TAJIMA

LT≺ (ξi ) = LT≺ (ξ). Hence ξ − ξi ∈ Ni−1 , and thus Ni−1 + Sξi = Ni−1 + Sξ. (4)
holds true by Gaussian elimination.

Definition 3.10. Let J ⊂ S be an ideal with a system of generators F = (f1 , . . . , fm ),
fi ∈ S, and Γ = (τ1 , . . . , τp ) a sequence of terms E with τ1 ≻ · · · ≻ τp . For
(i)
(i)
1 ≤ i ≤ m, Let s1 , . . . , sqi be all terms appearing in {fi τj | 1 ≤ j ≤ p}. We define
(i)
(i)
MF,Γ ∈ K qi ×p as a qi × (p + 1) matrix whose (j, k)-entry is the coefficient of sj in


(1)
MF,Γ


..
.
fi τk . We define MF,Γ as the block matrix 
.


(m)
MF,Γ
For Γ = (τ1 , . . . , τp ) and c = (c1 , . . . , cp )T where v T denotes the transpose of the
P
(i)
vector v, let η = Γ · c = pi ci τi . Then MF,Γ · c = 0 if and only if fi η = 0, and
MF,Γ · c = 0 if and only if Jη = 0.
We will give an algorithm for computing the Matlis dual of S/J where J is an
m-primary ideal (Algorithm 1). We omit describing the computations for term modules. By Lemma 3.6, they are computable by solving some combinatorial problems.

Algorithm 1 Algorithm for computing (S/J)∨
Input: A system of generators F = (f1 , . . . , fm ) of an m-primary ideal J ⊂ S.
∨
Output: A K-basis
)
( of (S/J) .
1
1
J α+1 = 0 , and N ← hBi.
1: Compute B =
xα+1
x
(
)
1
1
1
2: L1 ← ∅, L2 ←
∈ N :E m, α+1 6∈ N .
xα+1 xα+1
x
3: while L1 6= L2 do
4:
τ0 ← min≺F (L2 \L1 ).
5:
Γ ← (τ0 , τ1 , . . . , τp ) where τ1 ≻ · · · ≻ τp and
(
)
1
1
1
1
{τ1 , . . . , τp } =
∈ T2 (N ) :E m, α+1 6∈ LT≺ (N ), α+1 ≺ τ0 .
xα+1 xα+1
x
x
6:
7:
8:

9:
10:
11:
12:

if MΓ,F · c = 0 for some 0 6= c = (c0 , c1 , . . . , cp )T P
∈ K p+1 then
B ← B(∪ {ξ}, N ← hN, ξi where ξ := Γ · c = ci τi . )
1
1
1
L2 ←
∈ LT≺ (N ) :E m, α+1 6∈ LT≺ (N ) .
α+1
α+1
x
x
x
)
(
1
.
else L1 ← L1 ∪
xγ+1
end if
end while
return B

Proof of the correctness of Algorithm 1. This algorithm is essentially same as the
algorithm in [5]. Here, we give a proof

AN ALGORITHM FOR THE HILBERT–SAMUEL MULTIPLICITIES

7

Since S is a Noetherian ring and (S/I)∨ is a Noetherian S-module, the ascending
condition holds for ideals of S and submodules of (S/I)∨ . In each step of the while
1
∈ L1 i ⊂ S or the S-submodule N of (S/I)∨
loop, the monomial ideal hxα | xα+1
become larger, this algorithm terminate in finite time.
We will prove that N ’s and ξ’s computed in this algorithm are Ni ’s and ξi ’s in
Theorem 3.9 provided N = (S/J)∨ . The module N in line 1 is T1 ((S/J)∨ ). Thus
0-th N coincides with N0 . Assume that (i − 1)-th N is obtained in the algorithm
and it coincides with Ni−1 . Since ξi ∈ Ni−1 , we have LT≺ (ξi ) ∈ LT≺ (Ni−1 ) :E m.
As ξi ∈ Ni−1 ⊂ T2 (Ni−1 ), the terms of ξi except for LT≺ (ξi ) is in
(

1

1

xα+1

xα+1

∈ T2 (Ni−1 ) :E m,

1
xα+1

6∈ LT≺ (N ),

1
xα+1

)

≺ LT≺ (ξi ) .

As L1 is the list of terms which are less than LT≺ (ξi−1 ) or proven not to be the
leading term of ξi , min≺ L2 \L1 is the candidates of LT≺ (ξi ). Thus there exists
c satisfying the condition in line 6, the ξ in line 7 should be ξi , and the new N
is Ni . Therefore, by induction, this algorithm construct the composition series in
Theorem 3.9. Hence the output is (S/J)∨ .

P
α
is computable if the
Remark 3.11. We say that a power series
α∈Z≥0 cα x
function α 7→ cα is computable. Even if η is a computable power series with
1
infinite terms, η α+1 can be computed in finite time since there exist only finitely
x
1
many terms xβ of S such that xβ α+1 6= 0. Therefore, Algorithm 1 is applicable
x
for J generated by computable power series if it is guaranteed that J is m-primary.
However, it is known that even if J is generated by computable power series, it
is not decidable whether J is m-primary or not. Let P (y1 , . . . , yr ) ∈ Z[y1 , . . . , yr ]
be a polynomial, and p1 , . . . , pr first r prime numbers. For a ∈ Z≥0 , we set
ca =



1
0

mr
1
if a = pm
and P (m1 , . . . , mr ) = 0
1 · · · pr
otherwise

P
a
and let f (x1 ) =
a ca x1 . Then f is computable, and f 6= 0 if and only if the
equation P (y1 , . . . , yr ) = 0 has a non-negative integer solution. It is known that
there is no algorithm for deciding this. Therefore, there is no algorithm for deciding
whether an ideal hf (x1 )i ⊂ KJx1 K is m-primary or not.

4. Algorithm
4.1. An algorithm for computing Hilbert–Samuel multiplicities and reductions. Let I ⊂ S = KJxK = KJx1 , . . . , xn K be an ideal with a system of generators g1 , . . . , gr . We assume that R = S/I is Cohen–Macaulay. Let f1 , . . . , fm ∈ S
such that J := hf1 , . . . , fm iR ⊂ R be an n-primary ideal.
Let t = (tij )1≤i≤d,d+1≤j≤m where tij ’s are indeterminates over K. Let K =
K(ti,j | i, j), S ′ = KJx1 , . . . , xn K, and R′ = S ′ /IS ′ . Since ℓR (R/J k ) = ℓR′ (R′ /J k R′ ),

8

TAKAFUMI SHIBUTA AND SHINICHI TAJIMA

eR (J) = eR′ (JR′ ). We set
*
Qt

Pt

:=

:=

*

fj +

m
X

tij fi

i=d+1

fj +

m
X

tij fi

i=d+1
′

+

⊂ R′ ,

1≤i≤d

+R

′

+ IS ′ ⊂ S ′ .

1≤i≤d

Then Qt is a image of Pt in R , and a reduction of JR′ . Thus we have
eR (J) = eR′ (JR′ ) = ℓR′ (R′ /Qt ) = ℓS ′ (S ′ /Pt ).
For a = (aij )i,j ∈ K d×(m−d), We set
*
m
X
Qa := fj +
aij fi
i=d+1

+

1≤i≤d

⊂ R.
R

Since the image of a Zariski open set under a surjection contains a Zariski open
set, there is a Zariski open set U ⊂ K d×(m−d) such that Qa is a reduction of J
for a ∈ U by Theorem 2.12. By Corollary 2.11, the Zariski open set U coincides
with the set {a ∈ K d×m−d | Qa is a reduction of J}. We will give nn algorithm for
computing Hilbert–Samuel multiplicities and reductions (Algorithm 2).
Theorem 4.1.
(1) Algorithm 2 compute eR (J).
(2) For a = (aij )i,j ∈ K d×(m−d) satisfying the following two conditions, Qa is
a reduction of J.
(a) c(a) 6= 0 for all c(t) ∈ PolyList.
(b) For any M (t) ∈ MatList, the linear equation M (a)y = 0 has no solution. Here, M (a) is the matrix obtained by substituting a to t in
M (t).
Proof. By Algorithm 2, the output |B| of Algorithm 1 coincides with ℓ(S ′ /Pt ).
As we have shown before, eR (J) = eR′ (JR′ ) = ℓR′ (R′ /Qt ) = ℓS ′ (S ′ /Pt ). Thus
eR (J) = |B|.
If a satisfies (a) and (b), the computations applying Algorithm 1 to Pa proceeds
essentially same as ones applying Algorithm 1 to Pt . Thus, ℓ(R/Qa) = ℓ(S/Pa ) =
eR (J). Therefore Qa is a reduction of J since R is Cohen–Macaulay.

We not that the set of a ∈ PolyList satisfying (a) and (b) forms a Zariski open
set. Thus conditions (a) and (b) together express what generic linear combinations
means explicitly. If we choose coefficients using random numbers, the coefficients
tend to be large. We are able to look for a reduction with small coefficients using
Theorem 4.1. Once we obtain a reduction Q of J, we may use Q for solving
membership problem of J; for f ∈ S, f ∈ J if and only if e(hQ, f i) = ℓ(R/Q).
4.2. Modulo p method. The main part of the algorithms presented in this paper
is solving linear equations. By using so-called modular method, one can reduce
computational time of this part. For simplicity, assume that K = Q and the
coefficients of fi ’s and gj ’s are in Z. Then the entries of matrices MΓ,F appearing
in Algorithm 2 is in the polynomial ring Z[tij | 1 ≤ i ≤ d, d + 1 ≤ j ≤ m]. Applying
Gaussian elimination to such matrices is a hard task in general. By Theorem 3.9
(4), the dimension of the solution space of MΓ,F x = 0 is at most 1. Here, we give
a effective method for solving linear equations with matrices of this type.

AN ALGORITHM FOR THE HILBERT–SAMUEL MULTIPLICITIES

9

Algorithm 2 Algorithm for computing eR (J) and reductions of J
Input: m-primary ideal J = hf1 , . . . , fm iR ⊂ R, and an ideal I = hg1 , . . . , gr i ⊂ S
such that R/I is Cohen–Macaulay.
Output: eR (J), PolyList, MatList.
1: PolyList ← ∅, MatList ← ∅.
Pm
P
2: F ← (f1 +
ti1 fi , . . . , fd + m
t f , g , . . . , gr ).
i=d+1
(
)i=d+1 id i 1
1
1
3: Compute B =
J α+1 = 0 , and N ← hBi.
xα+1
x
(
)
1
1
1
4: L1 ← ∅, L2 ←
∈ N :E m, α+1 6∈ N .
xα+1 xα+1
x
5: while L1 6= L2 do
6:
τ0 ← min≺F (L2 \L1 ).
7:
Γ ← (τ0 , τ1 , . . . , τp ) where τ1 ≻ · · · ≻ τp and
(
)
1
1
1
1
{τ1 , . . . , τp } =
∈ T2 (N ) :E m, α+1 6∈ LT≺ (N ), α+1 ≺ τ0 .
xα+1 xα+1
x
x
8:
9:
10:
11:

12:
13:
14:
15:

if MΓ,F · c = 0 for some 0 6= c = (c0 (t), c1 (t), . . . ,P
cp (t))T ∈ K[t]p+1 then
B ← B ∪ {ξ}, N ← hN, ξi where ξ := Γ · c = ci τi .
PolyList
)
( ← PolyList ∪ {c1 (t)}.
1
1
1
∈ LT≺ (N ) :E m, α+1 6∈ LT≺ (N ) .
L2 ←
xα+1 xα+1
x
(
)
1
else L1 ← L1 ∪
, MatList ← MatList ∪ {MΓ,F }.
γ+1
x
end if
end while
return |B|, PolyList, MatList.

Let R = Z[t] = Z[t1 , . . . , tr ], and K = Q(t1 , . . . , tr ) the fractional field of R. Let
M ∈ Rn×m be an n×m matrix. Let p be a prime number and 0 ≤ a1 , . . . , an ≤ p−1.
Then p = hp, t1 −a1 , . . . , tn −an i is a maximal ideal of R, and R/p = Fp . We denote
M mod p by M ∈ Fpn×m . Let x = (x1 , . . . , xm )T be a vector of indeterminates.
For a vector c = (c1 , . . . , cm )T , we call supp(c) := {i | ci 6= 0} the support of c. For
a subset Λ ⊂ {1, . . . , n}, [M ]Λ denotes the submatrix of M consisting of the i-th
columns of M for i ∈ Λ.
Proposition 4.2. Let the notation be as above. Assume that the dimension of the
solution space in K m of the linear equations M x = 0 is at most 1.
(1) If the linear equation M x = 0 does not have non-trivial in Fm
p , then M x = 0
does not have non-trivial in K m .
(2) Assume that M c = 0 for some c ∈ Fm
p . If p is generic, that is, p is sufficiently large and a1 , . . . , ar is generically chosen, then the linear equation
[M ]supp(c) y = 0 has a solution in K |supp(c)| where y = (yi | i ∈ supp(c)).
Proof. We will prove the contraposition of (1). Assume that M x = 0 has a nontrivial, which is equivalent to that any m-minor of M is zero. Then any m-minor
of M is also zero, and thus M x = 0 has a non-trivial solution.

10

TAKAFUMI SHIBUTA AND SHINICHI TAJIMA

Assume that p is generic. Let Ii (M ) ⊂ R be the ideal generated by all iminors of M for i = m − 1, m. Since the dimension of the solution space in K m
of the linear equations M x = 0 is at most 1, we have Im−1 (M ) 6= 0. As p is
generic, Im−1 (M ) 6= 0, and thus the dimension of the solution space in Fm
p of
the linear equations M x = 0 is also at most 1. Since M x = 0 has a non-trivial
solution, Im (M ) = 0. As p is generic, this implies Im (M ) = 0. Then there exists
0 6= c(t) = (c1 (t), . . . , cm (t))T ∈ Z[t]m which is a K-basis of the solution space of
M x = 0. Let c = c(t) mod p. As p is generic, supp(c(t)) = supp(c), and c is a
Fp -basis of the solution space of M x = 0. This proves the assertion of (2).

If [M ]supp(c) y = 0 in (2) has no solution, we should take another p or solve
M x = 0 directly, but it rarely happens. Using Proposition 4.2, we can reduce the
computation time of Algorithm 2.
References
[1] W. Bruns, J. Herzog, Cohen–Macaulay Rings, Cambridge Studies in Advanced Mathematics,
39, Cambridge, Cambridge University Press, 1993.
[2] C. Huneke, I. Swanson, Integral closure of ideals, rings, and modules, London Mathematical
Society Lecture Note Series, vol. 336, Cambridge University Press, Cambridge, 2006
[3] T. Mora, M.E. Rossi, An algorithm for the Hilbert-Samuel function of a primary ideal, Comm.
Algebra 23 no. 5(1995), 1899–1911.
[4] D. Rees, A-transforms of local rings and a theorem on multiplicities of ideals, Proc. Cambridge
Phil. Soc. 57 (1961), 8–17.
[5] S. Tajima, Y. Nakamura and K. Nabeshima, Standard bases and algebraic local cohomology
for zero dimensional ideals, Advanced Studies in Pure Mathematics 56 (2009), 341–361.
[6] B. Teissier, Variétiés polaries. II. Multiplicitiés polaries, sections planes, et conditions de Whitney, Algebraic Geometry (La Rábida 1981), Lect. Notes. Math. 961(1983), 314–491.
Department of Information Science, Kyushu Sangyo University
E-mail address: tshibuta@ip.kyusan-u.ac.jp
Graduate School of Pure and Applied Sciences, University of Tsukuba
E-mail address: tajima@math.tsukuba.ac.jp

