ON MODULAR COMPUTATION OF GRÖBNER

arXiv:1312.6331v1 [] 22 Dec 2013

BASES WITH INTEGER COEFFICIENTS

S. Yu. Orevkov

§1. Introduction. Let A = Z[X], X = (x1 , . . . , xn ). We consider A as a subset of
Q[X], so, if I is an ideal of A, then QI is the ideal of Q[X] generated by I. Given
a ring R, we denote the natural mapping A → A ⊗ R = R[X] by ιR . This note is
devoted to the following algorithmic problem (see [1] for a definition and properties
of Gröbner bases of ideals in polynomial rings over Z).
Problem (P). Suppose that we have an infinite sequence f1 , f2 , . . . of elements
of A (a blackbox producing them one by one). Let I = (f1 , f2 , . . . ) be the ideal
generated by all the fi ’s. Compute the Gröbner base of I under the assumption that
the Gröbner base of QI and the Gröbner bases of ιZ/mZ (I), m ∈ Z, are known.
This problem arises in [5], [6] (see §2 for more details). Our solution is based
on a computation of the exponent of the torsion part of A/I (see [3]), and Main
Lemma in §3 below.
§2. Motivation. More precisely, the algorithmic problem appeared in [5], [6] is
the following. Let F be a finite rank free A-module, M0 a submodule of F (given by
a finite generating set G0 ), τ ∈ HomA (F, A), and ρ1 , . . . , ρp ∈ EndA (F ). Compute
(a Gröbner base of) τ (M ) where M is the minimal submodule of F such that
M0 ⊂ M and ρi (M ) ⊂ M for any i = 1, . . . , p. Theoretically, this problem has
an evident solution, namely, we could computePone by one the Gröbner bases of
p
the modules Mj defined recursively by Mj+1 = i=1 ρi (Mj ) till the moment when
Mj+1 = Mj . We set at this moment M = Mj and I = τ (M ).
However, if the rank of F is very big, then the computation of Gröbner bases of
Mj ’s may be so long that it cannot be performed in practice whereas the Gröbner
bases of (Z/mZ)[X]-modules Mj ⊗ (Z/mZ) can be computed much faster. When
we know them, we can compute the Gröbner bases of Q[X]-modules Mj ⊗Q (see [2]
and §5 below). Therefore we can compute the modules M ⊗(Z/mZ) and M ⊗Q, and
hence the ideals ιZ/mZ (I) and QI. Also we can successively compute the generators
of I of the form τ ρi1 ρi2 . . . ρik (g), g ∈ G0 . So, the problem (P) naturally arises.
§3. Solution to Problem (P). Let the notation be as in Introduction.
Main Lemma. Let I and J be ideals in A such that J ⊂ I. Let m be the exponent
of the torsion part of the abelian group A/J, i. e., m is the minimal positive integer
such that m(QJ ∩ A) ⊂ J. Let m1 , . . . , mt be pairwise coprime integers whose
product is equal to m. Suppose that
(i) QJ = QI, i. e., I and J generate the same ideal in Q[X],
(ii) ιZ/mi Z (J) = ιZ/mi Z (I), i = 1, . . . , t;
Typeset by AMS-TEX

1

2

S. YU. OREVKOV

Then I = J.

Q
Proof. Let ci = m/mi = j6=i mj , i = 1, . . . , t. Since mi ’s are pairwise coprime,
there exist b1 , . . . , bt ∈ Z such that
b1 c1 + · · · + bt ct = 1

(1)

We have to show that I ⊂ J. Let f ∈ I. By Condition (ii), for any i = 1, . . . , t, we
have f = fi + mi hi with fi ∈ J and hi ∈ A. By Condition (i), we have kf ∈ J for
some k ∈ Z, hence, for any i, we have kmi hi = kf − kfi ∈ J, i. e., hi represents
an element of the torsion part of the group A/J. By definition of m, this implies
mhi ∈ J, hence ci f = ci fi + ci mi hi = ci fi + mhi ∈ J. Combined with (1), this
yields
f = b1 (c1 f ) + · · · + bt (ct f ) ∈ J 
Thus we obtain the following solution to Problem (P). We fix any term order
in A. We try one by one all ideals J of the form (f1 , . . . , fk ), k = 1, 2, . . . and for
each of them do the following:
(1) Compute the reduced Gröbner bases of the ideals QI and QJ of the ring
Q[X]. If they do not coincide, then we pass to the next J.
(2) Compute m as in Main Lemma using one of the algorithms given in [3] (see
αt
1
also §4). Let m = pα
1 . . . pt be the factorization of m into prime factors
αi
and let mi = pi .
(3) For each i = 1, . . . , t, compute the reduced Gröbner bases of ιZ/mi Z (I) and
ιZ/mi Z (J). If they do not coincide, then we pass to the next J. If they do
coincide, then we compute the Gröbner base of J and stop the computation.
§4. Computation of m. Several algorithms are discussed in [3] to compute m
(defined in Main Lemma). For the reader’s convenience, we reproduce here the
algorithm which (we quote [3]) ‘seems better suited for practical computations’. It
consists in the following steps:
(1) Fix any term ordering and compute a Gröbner base G of J. Let s be the
least common multiple of the leading coefficients of the elements of G. Then
QJ ∩ A = Z[1/s]J ∩ A.
(2) Let Y be a new indeterminate. Then Z[1/s]J ∩ A = (I, sY − 1) ∩ A. A
Gröbner base Gs of this ideal can be computed using an elimination term
ordering.
(3) Compute m such that mg ∈ J for any g ∈ Gs .
§5. On the modular computation of Gröbner bases over Q. In our notation,
Elizabeth Arnold’s theorem can be formulated as follows (similar theorem holds also
for modules).
Theorem. [2; Th. 7.1]. Let I be a homogeneous ideal in Z[X] and G ⊂ Z[X].
Let QI be the ideal in Q[X] generated by I. Let p be a prime number. We set
Ip = ιFp (I), Gp = ιFp (G). Suppose that:
(1)
(2)
(3)
(4)

Gp is a Gröbner base of Ip ,
G is a Gröbner base of the ideal hGiQ that it generates in Q[X],
QI ⊂ hGiQ ,
LM(Gp ) = LM(G) where “LM” denotes the set of leading monomials.

ON MODULAR COMPUTATION OF GRÖBNER BASES OVER Z

3

Then G is a Gröbner base of QI.
It is claimed in [4; Th. 2.4] that the same statement holds for non-homogeneous
ideals. However, it is wrong as one can see in the simplest example I = (px + 1),
G = {1}.
When the ideal is not homogeneous, it can be homogenized by adding a new
variable and after that one can apply E. Arnold’s theorem. For instance, if we
homogenize the above counter-example, i. e., if we set I = (px + y), G = {y}, then
the condition (3) no longer holds true, so, the contradiction disappears.
Acknowledgment. I am grateful to Vladimir Gerdt for useful discussions.
References
1. W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics, vol. 3, A.M.S., Providence, RI, 1994.
2. E. A. Arnold, Modular algorithms for computing Gröbner bases, J. of Symbolic Computations
35 (2003), 403–419.
3. M. Aschenbrenner, Algorithms for computing saturations of ideals in finitely generated commutative rings. Appendix to: Automorphisms mapping a point into a subvariety, J. of Algebraic Geom. 20 (2011), 785–794 (by B. Poonen).
4. V. Idrees, G. Pfister, S. Steidel, Parallelization of modular algorithms, J. of Symbolic Computations 46 (2011), 672–684.
5. S. Yu. Orevkov, Markov trace on the Funar algebra, arXiv:1206.0765.
6. S. Yu. Orevkov, Cubic Hecke algebras and invariants of transversal links, Doklady Math. (to
appear); arXiv:1307.5862.
Steklov Math. Institute, Moscow
IMT, Université Paul Sabatier (Toulouse-3)
E-mail address: orevkov@math.ups-tlse.fr

