OVERDETERMINED SYSTEMS OF SPARSE POLYNOMIAL
EQUATIONS

arXiv:1307.5788v2 [math.AG] 13 Apr 2014

FRANCESCO AMOROSO, LOUIS LEROUX, AND MARTÍN SOMBRA
Abstract. We show that, for a system of univariate polynomials given in sparse
encoding, we can compute a single polynomial defining the same zero set, in time
quasi-linear in the logarithm of the degree. In particular, it is possible to determine
whether such a system of polynomials does have a zero in time quasi-linear in the
logarithm of the degree. The underlying algorithm relies on a result of Bombieri and
Zannier on multiplicatively dependent points in subvarieties of an algebraic torus.
We also present the following conditional partial extension to the higher dimensional setting. Assume that the effective Zilber conjecture holds. Then, for a system
of multivariate polynomials given in sparse encoding, we can compute a finite collection of complete intersections outside hypersurfaces that defines the same zero
set, in time quasi-linear in the logarithm of the degree.

1. Introduction
A system of polynomial equations
(1.1)

f1 = · · · = fs = 0

is “overdetermined” if the number of equations exceeds the codimension of its zero set.
Our aim is to give algorithms for reducing those systems of equations to a finite number
of “well-determined” systems. We focus on the case when the input polynomials are
sparse in the sense that they have high degree but relatively few nonzero terms and
small coefficients, and we want our algorithms to be as efficient as possible in that
situation.
For univariate polynomials, the reduction of an overdetermined system as in (1.1)
with s ≥ 2, might be done by computing the greatest common divisor of the fi ’s.
However, this strategy does not work in our situation because the gcd of a family of
sparse polynomials is not necessarily sparse, as shown by the following example due
to Schinzel [Schi02]: if a, b ≥ 1 are coprime, then
gcd(xab − 1, (xa − 1)(xb − 1)) =

(xa − 1)(xb − 1)
.
x−1

This polynomial has 2 min(a, b) nonzero terms. Hence, for a, b ≫ 0, both xab − 1 and
(xa − 1)(xb − 1) are sparse, but their gcd is not.
Date: January 27, 2018.
2010 Mathematics Subject Classification. Primary 11Y16; Secondary 12Y05, 68W30.
Key words and phrases. Sparse polynomial, overdetermined system of equations, algebraic torus,
unlikely intersections.
Amoroso and Leroux were partially supported by the CNRS research project PICS “Properties
of the heights of arithmetic varieties”. Amoroso was also partially supported by the ANR research
project “Hauteurs, modularité, transcendance”. Sombra was partially supported by the MICINN
research projects MTM2009-14163-C02-01 and MTM2012-38122-C03-02.
1

2

AMOROSO, LEROUX, AND SOMBRA

This example suggests that one should avoid polynomials vanishing at roots of unity.
Indeed, Filaseta, Granville and Schinzel have shown that, if f, g ∈ Z[x] are given in
sparse encoding and either f or g do not vanish at any root of unity, then gcd(f, g)
e
can be computed with O(log(d))
ops [FGS08]. Here, ops is an abbreviation of “bit
operations”, and the “soft O” notation indicates a bound with an extra factor of type
(log log(d))O(1) and implicit constants depending on the size of the coefficients and
number of nonzero terms of f and g. Their algorithm relies heavily on a theorem of
Bombieri and Zannier on the intersection of a subvariety of the algebraic torus with
subtori of dimension 1 [Schi00, Appendix], see also § 3.
Our first result is an extension of the algorithm of Filaseta, Granville and Schinzel,
allowing the case when both f and g vanish at roots of unity. From now on, we fix
a number field K ⊂ Q. Given f1 , . . . , fs ∈ K[x1 , . . . , xn ], we denote by V (f1 , . . . , fs )
n
their set of common zeros in the affine space An = Q . Polynomials are given in sparse
encoding. Recall that the height of a polynomial is a measure of the bit size of its
coefficients, see § 2.1 for details. The following statement makes the output and the
complexity of our algorithm precise.
Theorem 1.1. There is an algorithm that, given f, g ∈ K[x], computes p1 , p2 ∈ K[x]
such that
p1 | gcd(f, g),

V (p1 ) \ µ∞ = V (gcd(f, g)) \ µ∞ ,

and

V (p2 ) = V (gcd(f, g)) ∩ µ∞ ,

×

where µ∞ denotes the subgroup of Q of roots of unity.
If both f and g have degree bounded by d and height and number of nonzero coeffie
cients bounded by c, this computation is done with O(log(d))
ops, where the implicit
constants depend only on K and c.
This result is a simplified version of Theorem 4.5, which holds for families of univariate polynomials and gives more information about the output polynomials. The
underlying procedure is given by Algorithms 4.2 and 4.3. A preliminary version appears in the second author’s Ph.D. thesis [Ler11].
In the notation of Theorem 1.1, we have that
(1.2)

V (p1 p2 ) = V (f, g).

Hence, given two univariate polynomials with bounded height and number of nonzero
coefficients, we can compute a polynomial which has the same zero set as their gcd,
with complexity quasi-linear in the logarithm of the degree. In particular, we deduce
the following corollary.
Corollary 1.2. Let f, g ∈ K[x] be polynomials of degree ≤ d and height and number
of nonzero coefficients bounded by a constant c. We can decide if
gcd(f, g) = 1
e
with O(log(d))
ops, where the implicit constants depend only on K and c.

A classical result of Plaisted says that computing the degree of the gcd of two
univariate polynomials given in sparse encoding is an NP-hard problem [Pla77]. Using
Plaisted’s techniques in loc. cit., it can be shown that already deciding if the degree
of the gcd is zero, is an NP-hard problem. Hence, if Cook’s conjecture P 6= NP holds,
it is not possible to decide if the degree of the gcd is zero with a complexity which is
polynomial in the height, number of nonzero terms, and logarithm of the degree of the
input polynomials. In contrast to this, Corollary 1.2 shows that this problem can be

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

3

solved with a complexity which is quasi-linear in the logarithm of the degree although,
a priori, not polynomial in the height and number of nonzero terms.
Our algorithms for the multivariate case rely on an effective version of the Zilber
conjecture generalizing the quoted theorem of Bombieri and Zannier. For N ≥ 0, we
× N
denote by GN
m = (Q ) the (split) algebraic torus over Q of dimension N . Recall that a
torsion coset of GN
m is a connected component of an algebraic subgroup or, equivalently,
a translate of a subtorus by a torsion point. The effective Zilber conjecture can then
be stated as follows:
Let W be an irreducible subvariety of GN
m . There exists a finite and
effectively calculable collection Ω of torsion cosets of GN
m of codimenN
sion 1 such that, if B is a torsion coset of Gm and C an irreducible
component of B ∩ W such that
dim(C) > dim(B) − codim(W ),
then there exists T ∈ Ω such that C ⊂ T .
Zilber proposed this conjecture (under the equivalent formulation that we recall in
Conjecture 3.4) in connection with the so-called “uniform Schanuel conjecture” and
motivated by problems from model theory [Zil02]. It is still unproven, but several
interesting cases are already known. When we restrict to dim(B) = 0, the statement
is equivalent to the toric case of the Manin-Mumford conjecture. This is a well-known
theorem of Laurent [Lau84] and an effective proof of it can be found in Schmidt’s
paper [Schm96] or, more explicitly, in the second author’s paper [Ler12]. The result
by Bombieri and Zannier solves the case when we restrict to dim(B) = 1. The case
when W is a curve was proved by Maurin [Mau08], building on previous work by
Bombieri, Masser and Zannier [BMZ99]. Moreover, the closely related “bounded height
conjecture” has been proved by Habegger in the general case [Hab09].
The Zilber conjecture plays a central role in the study of “unlikely intersections” and
has many applications in number theory, see for instance the survey [Cha12] and the
book [Zan12] for accounts of this very active area of research.
A well-determined system of polynomial equations is, by definition, a complete intersection. The solution set of a system of multivariate polynomial equations cannot
always be redefined by a single complete intersection, since it might have components
of different codimensions and, moreover, these components might not be complete
intersections either. Instead, this solution set can be described as a finite union of
complete intersections on open subsets (Proposition-Definition 2.1). Such a decomposition can be understood as a sort of generalization to the multivariate setting of the
polynomial p1 p2 in (1.2) from the univariate case.
The main result of this paper is an algorithm giving a conditional partial computation of this decomposition for an arbitrary system of multivariate polynomials (Algorithm 5.5). The following statement makes the size of its output and its complexity
precise.
Theorem 1.3. Assume that the effective Zilber conjecture holds. There is an algorithm
that, given f1 , . . . , fs ∈ K[x1 , . . . , xn ], computes a finite collection Γ whose elements
are sequences (p1 , . . . , pr , q) of polynomials in K(ω)[x1 , . . . , xn ] with ω a root of unity,

4

AMOROSO, LEROUX, AND SOMBRA

such that either codim(V (p1 , . . . , pr )\V (q)) = r or V (p1 , . . . , pr )\V (q) = ∅, and
[
(1.3)
V (f1 , . . . , fs ) =
V (p1 , . . . , pr )\V (q).
(p1 ,...,pr ,q)∈Γ

If both n and s are bounded by a constant c and each fi is of degree ≤ d and height
and number of nonzero terms bounded by c, then the cardinality of Γ is bounded by
O(1), the order of ω is bounded by O(1), the polynomials in Γ have degree bounded by
dO(1) , height and number of nonzero coefficients bounded by O(1), and the computation
e
is done with O(log(d))
ops, where the implicit constants depend only on K and c.

A previous result in this direction, for systems of three polynomials in two variables,
appears in the second author’s Ph.D. thesis [Ler11].
From (1.3), one can derive a well-determined description of V (f1 , . . . , fs ) by throwing away the empty pieces. The bounds in Theorem 1.3 imply that, if the input
polynomials are sparse, then this decomposition into complete intersections outside
hypersurfaces is defined by polynomials that are also sparse. The actual computation
of such a decomposition from the output of Algorithm 5.5 amounts to deciding when
V (p1 , . . . , pr )\V (q) = ∅ for each (p1 , . . . , pr , q) ∈ Γ. Unfortunately, it is not clear yet
e
how to perform this task with O(log(d))
ops, see Problem 1.5 below.
The idea for the algorithms underlying Theorems 1.1 and 1.3 is inspired by the
method in [FGS08]. It can be explained as follows. First, by decomposing the affine
space into a disjoint union of algebraic tori, the problem can be reduced to the analogous problem on the open subset Gnm ⊂ An . Write
(1.4)

fi =

N
X

αi,j xaj ∈ K[x1 , . . . , xn ],

i = 1, . . . , s,

j=1

with αi,j ∈ K and aj ∈ Zn . Then we consider the homomorphism ϕ : Gnm → GN
m
PN
defined by the exponents aj , j = 1, . . . , s and the linear forms ℓi =
j=1 αi,j yj ,
i = 1, . . . , s. These forms define a linear subvariety W of GN
m such that
(1.5)

ϕ−1 (W ) = V (f1 , . . . , fs ) ∩ Gnm .

Roughly speaking, the next step consists of producing a stratification of W by successively intersecting this subvariety with torsion cosets of codimension 1 produced by the
effective Zilber conjecture. The output of the algorithm is obtained by considering the
inverse image under the homomorphism ϕ of some of the pieces of this stratification.
Several questions arose during our work, and we close this introduction by pointing
out two of them. Both problems have interesting algorithmic consequences and seem
to be related to the study of unlikely intersections in algebraic tori.
Problem 1.4. Give an algorithm for computing the degree of the gcd of two polynomials given in the sparse encoding, of degree ≤ d and bounded height and number of
e
coefficients, with O(log(d))
ops.

An affirmative answer to Problem 1.4 would allow to test divisibility of sparse polynomials with complexity quasi-linear in the logarithm of their degree.
Problem 1.5. In the setting of Theorem 1.3, modify the underlying algorithm to exclude the possibility that V (p1 , . . . , pr )\V (q) = ∅.

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

5

An affirmative answer to Problem 1.5 would allow us to compute the dimension
e
of V (f1 , . . . , fs ) with O(log(d))
ops. In particular, we could then determine whether
e
the zero set V (f1 , . . . , fs ) is empty with O(log(d))
ops, extending Corollary 1.2 to the
multidimensional case.
Acknowledgments. We thank Gaël Rémond and Umberto Zannier for useful discussions about unlikely intersections and the Zilber conjecture. We also thank the referees
for their many remarks that helped us to improve our presentation.
Part of this work was done while the authors met at the Universitat de Barcelona,
the Université de Caen and the Centro di Ricerca Matematica Ennio de Giorgi (Pisa).
We thank these institutions for their hospitality.
2. Notation and auxiliary results
We fix a number field K ⊂ Q. Bold letters denote finite sets or sequences of objects,
where the type and number should be clear from the context: for instance, x might
denote the group of variables {x1 , . . . , xn }, so that K[x±1 ] denotes the ring of Laurent
±1
polynomials K[x±1
1 , . . . , xn ].
e
Given functions f, g : N → R>0 , the Landau symbols f = O(g) and f = O(g)
respectively mean that there are positive constants c1 , c2 ≥ 0 such that, for all m ∈ N,
f (m) ≤ c1 g(m),

f (m) ≤ c1 g(m) max(1, log(g(m)))c2 .

If we want to emphasize the dependence of the constants c1 and c2 on parameters,
eN,h (g), respectively. When these
say N and h, we will write f = ON,h (g) and f = O
parameters are said to be “bounded”, we omit them from the notation as we do, for
instance, in Lemma 2.3.
2.1. Integers and Laurent polynomials. We denote by N, Z and Q the monoid
of natural numbers with 0, the ring of integers and the field of rational numbers,
respectively. At the computational level, integers are represented in bit encoding
and rational numbers are represented as quotients of integers. The complexity of an
algorithm will be measured in bit operations (ops).
A multiplication time function is a function
M: N → N
such that integers of bit length ≤ k can be multiplied using at most M(k) ops. We
also assume that, for k, l ∈ N, this function verifies M(kl) ≤ k2 M(l) and, if k ≥ l, it
also verifies M(k)/k ≥ M(l)/l.
Such a function dominates the complexity of many of the basic computations on Z.
In particular, for integers of bit length ≤ k, division with remainder can be done with
O(M(k)) ops, and their gcd can be computed with O(M(k) log(k)) ops [GG03]. By
the Schönhage-Strassen algorithm [GG03, Theorem 8.24], we can take
e
M(k) = O(k log(k) log(log(k))) = O(k).

The number field K is represented by a monic irreducible polynomial h ∈ Q[z] such
that K ≃ Q[z]/(h). The arithmetic operations of K (sum, difference, multiplication
and division by a nonzero element) can be computed in terms of this representation.
We will not be concerned by their complexity, since it will be absorbed by the constants
in our bounds.

6

AMOROSO, LEROUX, AND SOMBRA
×

For l ≥ 1, we denote by µl the subgroup of Q of roots of unity of order dividing l.
×
We also set µ∞ for the subgroup of Q of all roots of unity. Hence,
[
µ∞ =
µl .
l≥1

i1
iN
For N ≥ 0, an N -tuple of roots of unity η ∈ µN
l is represented as η = (ω , . . . , ω )
with ω a primitive l-th root of unity and 0 ≤ ij ≤ l − 1. A representation of the finite
extension K(η) can be computed in terms of η and a representation of K. Again, the
complexity of computing this representation will play no role in our results.
Laurent polynomials will be represented in sparse encoding: a Laurent polynomial
±1
n
f ∈ K[x±1
1 , . . . , xn ] will be given by a sequence of pairs (aj , αj ) ∈ Z × K, j =
1, . . . , N , such that
N
X
αj xaj .
f=
j=1

We assume that aj 6= ak for j 6= k.
For a vector a = (a1 , . . . , an ) ∈ ZN , we denote its ℓ1 -norm by
|a| = |a1 | + · · · + |an |.

We respectively define the support and the degree of f as
supp(f ) = {aj | αj 6= 0},

deg(f ) =

max

aj ∈supp(f )

|aj |.

When f is a polynomial, this notion of degree coincides with the usual one.
We define the height of f , denoted h(f ), as the Weil height of the projective point
(1 : α1 : · · · : αN ) ∈ PN , see for instance [BG06, Chapter 2] or [Zan09, Chapter 3] for
±1
details. In the particular case when f ∈ Z[x±1
1 , . . . , xn ],
h(f ) = max log |αj |.
j

±1
Ideals of K[x±1
1 , . . . , xn ] are represented by finite families of generators.
×

N
2.2. Subvarieties and locally closed subsets. For N ≥ 0, we set GN
m = (Q )
n
N
and A = Q for the algebraic torus and the affine space over Q of dimension N .
We will mostly work over the algebraic torus and so, for simplicity, we will define and
study subvarieties and locally closed subsets in that setting. Nevertheless the notions
and properties in this subsection can be easily transported to the affine space.
±1
±1
A subvariety of GN
m is the zero set of an ideal of Q[y1 , . . . , yN ]. Following this
convention, a subvariety is not necessarily irreducible. More generally, a locally closed
subset of GN
m is the intersection of a subvariety with a (Zariski) open subset. The
dimension of a locally closed subset is defined as the dimension of its (Zariski) closure.
A locally closed subset is irreducible if its closure is.
Let W be a locally closed subset of GN
m . An irreducible component of W is an
irreducible locally closed subset C ⊂ W that is maximal with respect to inclusion. An
irreducible locally closed subset C ⊂ W is an irreducible component of W if and only
if C is an irreducible component of W and C = C ∩ W . We denote by irr(W ) the finite
collection of the irreducible components of W . There is an irredundant decomposition
[
W =
C.
C∈irr(W )

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

7

±1
], we set
Given a family of Laurent polynomials F = {F1 , . . . , Fs } ⊂ Q[y1±1 , . . . , yN

V (F ) = V (F1 , . . . , Fs ) = {y ∈ GN
m | F1 (y) = · · · = Fs (y) = 0}
for the associated subvariety of GN
m . A family of Laurent polynomials over K can be
considered as a family of Laurent polynomials over Q via the inclusion K ֒→ Q. In
particular, such a family of Laurent polynomials defines a subvariety of GN
m.
We represent a subvariety W of GN
by
a
finite
family
of
Laurent
polynomials
F ⊂
m
±1
±1
Q[y1 , . . . , yN ] such that W = V (F ). More generally, a locally closed subset W
±1
±1
of GN
m is represented by two finite families F , G ⊂ Q[y1 , . . . , yN ] such that W =
V (F ) \ V (G). A subvariety or a locally closed subset of GN
m defined over K are
represented similarly by finite families of Laurent polynomials over K.
±1
Let W be a subvariety of GN
m . If W is a hypersurface, then there exists F ∈ Q[y ]
such that W = V (F ) because the ring Q[y ±1 ] is a unique factorization domain. If
the codimension of W is higher, then W cannot always be described as a complete
intersection. However, it is possible to describe a subvariety or, more generally, a
locally closed subset, as a finite union of complete intersections outside hypersurfaces.
Proposition-Definition 2.1. Let W be a locally closed subset of GN
m . Then there
exists a family of locally closed subsets Wj , j = 1, . . . , t, given as
Wj = V (Fj,1 , . . . , Fj,codim(Wj ) )\V (Gj )
±1
], and satisfying the following conditions:
with Fj,l , Gj ∈ Q[y1±1 , . . . , yN

(1) codim(W ) = codim(W1 ) < · · · < codim(Wt ) ≤ N ;
S
(2) W = ti=1 Wj .

A family of locally closed subset (Wj )j as above is called a complete intersection stratification of W .
If W is defined over K, then (Wj )j can be chosen to be defined over K too. In that
case, the complete intersection stratification is said to be defined over K.
Proof. Set c = codim(W ). We first show that there exist F1 , . . . , Fc , G ∈ Q[y ±1 ] such
that F1 , . . . , Fc is a complete intersection, V (G) contains no irreducible component of
W of codimension c and
W \V (G) = V (F1 , . . . , Fc )\V (G).

(2.1)
Let P , Q ⊂

Q[y ±1 ]

such that W = V (P ) \ V (Q) and set
X
X
Fl =
λl,i Pi , l = 1, . . . , c, and Q =
µ j Qj
i

j

for a choice of λl,i , µj ∈ Q. It can be shown that if this choice is generic in the sense
that the point (λ, µ) does not lie in a certain hypersurface of the parameter space,
then F1 , . . . , Fc defines a complete intersection in the complement of V (Q), and the
hypersurface V (Q) contains no irreducible component of W . Assume that our choice
of λl,i , µj is generic in this sense. Then we have that
W \ V (Q) ⊂ V (F ) \ V (Q)
and, if C is an irreducible component of W of codimension c, then C \ V (Q) is an
irreducible component of both W \ V (Q) and V (F ) \ V (Q).
Choose Q′ ∈ Q[y ±1 ] such that the hypersurface V (Q′ ) contains the irreducible
components of W \ V (Q) of codimension ≥ c + 1 and the irreducible components of
V (F ) \ V (Q) which are not a component of W \ V (Q), and does not contain any of

8

AMOROSO, LEROUX, AND SOMBRA

the other ones. Finally, set G = QQ′ . It is not difficult to verify that the Laurent
polynomials F1 , . . . , Fc , G satisfy (2.1).
If P , Q ⊂ K[y ±1 ], we can also verify that λl,i , µj and the coefficients of Q′ can be
chosen to lie in K, so that F1 , . . . , Fc , G ∈ K[y ±1 ].
Now set W1 = V (F ) \ V (G) with F , G as in (2.1). The intersection W ∩ V (G) has
codimension ≥ c+1, and so we can construct W2 , . . . , Wt by applying this construction
iteratively. The family (Wj )j that we obtain satisfies the conditions (1) and (2). It is
also clear that, if W is defined over K, then so is (Wj )j .

Given a locally closed subset W of GN
m , a complete intersection stratification can
be computed either by applying elimination theory or Gröbner basis algorithms. For
instance, the computation of the first piece W1 in the case when codim(W ) = 2 has
been worked out in detail in the second author’s Ph.D. thesis [Ler11, § 2.2.2]. The
complexity of this procedure will play no role in our results.
Given a map φ : Gnm → GN
m , we denote by
±1
±1
] −→ Q[x±1
φ# : Q[y1±1 , . . . , yN
1 , . . . , xn ]
M
the associated morphism of algebras. If ψ : GN
m → Gm is a further map, then

(2.2)

(ψ ◦ φ)# = φ# ◦ ψ # .

Given an ideal I ⊂ Q[y ±1 ], we denote by φ# (I) the ideal of Q[x±1 ] generated by the
image of I under φ# . We have that
(2.3)

V (φ# (I)) = φ−1 (V (I)).

2.3. Homomorphisms and torsion cosets of algebraic tori. We recall the basic
notation and properties of homomorphisms and algebraic subgroups of tori. We refer
to [BG06, § 3.2] or [Zan09, Chapter 4] for more details, including the proofs of the
quoted results.
n
For n, N ≥ 0, we denote by Hom(Gnm , GN
m ) the set of homomorphism from Gm to
N
N
N
the
Gm , and by Aut(Gm ) the group of automorphisms of Gm . We denote by idGN
m
N
identity automorphism of Gm .
Given a point x = (x1 , . . . , xn ) ∈ Gnm and a vector a = (a1 , . . . , an ) ∈ Zn , we set
xa = xa11 · · · xann . A matrix A ∈ ZN ×n with rows a1 , . . . , aN ∈ Zn gives a homomorn
phism ϕA : Gnm → GN
m defined, for x ∈ Gm , by
ϕA (x) = (xa1 , . . . , xaN ).
The correspondence A 7→ ϕA is a bijection between ZN ×n and Hom(Gnm , GN
m ). Given
matrices A ∈ ZN ×n and B ∈ ZM ×N , we have that
ϕB ◦ ϕA = ϕBA .
We define the size of a homomorphism ϕ ∈ Hom(Gnm , GN
m ) as
size(ϕ) = max |aj |,
j

where aj , j = 1, . . . , N , are the rows of the matrix corresponding to ϕ.
= (1, . . . , 1) the neutral element of GN
We denote by 1GN
m . The subgroup of torsion
m
N is a connected algebraic subgroup or,
N
.
A
subtorus
of
G
points of Gm agrees with µN
m
∞
equivalently, an algebraic subgroup which is the image of a homomorphism. A torsion
coset of GN
m is the translate of a subtorus by a torsion point. A torsion subvariety
is
a
finite union of torsion cosets.
of GN
m

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

9

A submodule Λ of ZN defines an algebraic subgroup of GN
m by
HΛ = V ({y b − 1 | b ∈ Λ}).

(2.4)

The correspondence Λ → HΛ is a bijection between the set of submodules of ZN and
that of algebraic subgroups of GN
m . This correspondence reverses dimension, in the
sense that
codim(HΛ ) = rank(Λ).
The algebraic subgroup HΛ is a subtorus if and only if the subgroup Λ is saturated,
that is, if and only if Λ = RΛ ∩ ZN .
For a submodule Λ of ZN , we denote by Λsat = RΛ ∩ ZN its saturation. Then HΛsat
sat : Λ] such that
is a subtorus and there is a finite subgroup F ⊂ µN
∞ of cardinality [Λ
HΛ = F · HΛsat .

(2.5)

Given a locally closet subset Y ⊂ GN
m , we denote by hY i the minimal algebraic
N
subgroup of Gm containing Y . Equivalently,
\
hY i =
H,
H⊃Y

the intersection being over all algebraic subgroups H of GN
m containing Y . The multiplicative rank of Y is defined as
rank(Y ) = dim(hY i).
GN
m

For instance, a point of
has rank 0 if and only if it is a torsion point, and it has
rank N if and only if its coordinates are multiplicatively independent.
The following lemma studies the behavior of the multiplicative rank under a homomorphism of algebraic tori.
Lemma 2.2. Let ϕ : Gnm → GN
m be a homomorphism, Y ⊂ im(ϕ) a irreducible locally
closed subset and C an irreducible component of ϕ−1 (Y ). Then
rank(C) − dim(C) = rank(Y ) − dim(Y ).
Proof. For each point ξ ∈ Y , we have that ϕ−1 (ξ) is a translate of the kernel of ϕ by
a point of Gnm . Hence dim(ϕ−1 (ξ)) = dim(ker(ϕ)) and, by the theorem of dimension
of fibers,
(2.6)

dim(ϕ−1 (Y )) = dim(Y ) + dim(ker(ϕ))

Set H = hϕ−1 (Y )i for the minimal algebraic subgroup of Gnm containing ϕ−1 (Y ). If
ξ is any point of Y , then ϕ−1 (ξ) ⊂ H. Since ϕ−1 (ξ) is a translate of ker(ϕ) and H is
a group, it follows that ker(ϕ) ⊂ H. Moreover, we have that ϕ(H) = hY i and so there
is an exact sequence 0 → ker(ϕ) → hϕ−1 (Y )i → hY i → 0. We deduce that
(2.7) rank(ϕ−1 (Y )) = dim(hϕ−1 (Y )i)
= dim(hY i) + dim(ker(ϕ)) = rank(Y ) + dim(ker(ϕ)).
N
Let F ⊂ µN
∞ be a finite subgroup and T ⊂ Gm a subtorus such that ker(ϕ) = F · T
as in (2.5) . Let C be an irreducible component of ϕ−1 (Y ). Then the decomposition
of ϕ−1 (Y ) into irreducible components is given by
[
ϕ−1 (Y ) =
ηC.
η∈F

Hence, dim(C) = dim(ϕ−1 (Y )) and rank(C) = rank(ϕ−1 (Y )). The statement then
follows from (2.6) and (2.7).


10

AMOROSO, LEROUX, AND SOMBRA

We represent torsion cosets as complete intersections of binomials whose coefficients
are roots of unity. In precise terms, let B be a torsion coset of GN
m and write B =
ηHΛ with η ∈ µ∞ and HΛ a subtorus of codimension r corresponding to a saturated
submodule Λ ⊂ ZN . Choose a basis bj ∈ ZN , j = 1, . . . , r, of Λ. Then there exist
ξj ∈ µ∞ , j = 1, . . . , r, such that
(2.8)

B = V (y b1 − ξ1 , . . . , y br − ξr ).

The following procedure allows us to compute the preimage of a torsion coset under
a homomorphism.
Algorithm 2.1 (Preimage of a torsion coset)
N
Input: a homomorphism ϕ : Gnm → GN
m and a torsion coset B ⊂ Gm .
−1
±1
Output: either “ϕ (B) = ∅” or a finite collection E ⊂ Q[x ] of binomials with
coefficients in µ∞ .
1. Let A ∈ ZN ×n be the N × n-matrix of ϕ and write B = V (y b1 − ξ1 , . . . , y br − ξr )
with bj ∈ ZN and ξj ∈ µ∞ ;
2. set cj = bj A ∈ Zn , j = 1, . . . , r;
3. compute a basis ek ∈ Zn , k = 1, . . . , t, of the submodule generated by the cj ’s;
P
P
4. compute λk,j , µj,k ∈ Z such that ek =
j λk,j cj and cj =
k µj,k ek ;
Q λk,j
5. set ρk ← j ξj , k = 1, . . . , t;
Q µj,k
= ξj for all j then
6. if
k ρk
7.
return E ← {xek − ρk }1≤k≤t ;
8. else
9.
return “ϕ−1 (B) = ∅”.
10. end if

N
Lemma 2.3. Given a homomorphism ϕ : Gnm → GN
m and a torsion coset B ⊂ Gm ,
Algorithm 2.1 decides if ϕ−1 (B) 6= ∅. If this is the case, it computes a finite collection
E = {xek − ρk }1≤k≤t of binomials in Q[x±1 ] with coefficients in µ∞ such that t =
codim(ϕ−1 (B)) and

(2.9)

ϕ−1 (B) = V (xe1 − ρ1 , . . . , xet − ρt ).

If n and N are bounded, B is given as in (2.8) with ξj ∈ µl with l bounded and
size(ϕ) ≤ d, then each coefficient ρk has order bounded by O(1) and each binomial has
degree bounded by dO(1) (by d in the case n = 1). The complexity of the algorithm is
e
bounded by O(M(log(d)) log(log(d))) = O(log(d))
ops.
Proof. Let notation be as in Algorithm 2.1. By (2.3),
(2.10)

ϕ−1 (B) = V (xc1 − ξ1 , . . . , xcr − ξr ).

Consider the ideals of K[x±1 ] given by
I = (xc1 − ξ1 , . . . , xcr − ξr ),

J = (xe1 − ρ1 , . . . , xet − ρt ).

By construction, we have that xek − ρk ∈ I for all k and, if we set ξj′ =
have similarly that xcj − ξj′ ∈ J for all j. Then
(2.11)

ξj − ξj′ = (xcj − ξj′ ) − (xcj − ξj ) ∈ (xc1 − ξ1 , . . . , xcr − ξr ).

Q

µ

k

ρk j,k , we

Hence, if there exists j such that ξj′ 6= ξj , it follows from (2.10) and (2.11) that
ϕ−1 (B) = ∅. Otherwise, we deduce that I = J and so ϕ−1 (B) = V (J), which proves

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

11

(2.9). Moreover, the binomials xek − ρk , k = 1, . . . , t, form a complete intersection
because the vectors ek , k = 1, . . . , t, are linearly independent. Hence t = codim(B),
as stated.
Now suppose that n and N are bounded, B is given as in (2.8) with ξj ∈ µl with
l bounded, and size(ϕ) ≤ d. The computation of the integers λk,j , µj,k in line 4 can
be derived from the Hermite normal form as defined in [Coh93, Definition 2.4.2], for
the matrix with rows cj , j = 1, . . . , r. This Hermite normal form can be computed
using Algorithm 2.4.5 in loc. cit. using a bounded number of gcd computations and
multiplications of integers of size bounded by log(d). Hence, the integers λk,j , µj,k
have size bounded by O(log(d)) and the complexity of these steps is bounded by
O(M(log(d)) log(log(d))). In particular, deg(xek − ρk ) ≤ dO(1) . When n = 1, we have
that t = 1 and e1 = gcd(c1 , . . . , cr ), and so deg(xe1 − ρ1 ) ≤ d in this case.
The computation in line 5 and the verification in line 6 can be done using repeated
squaring. The overall complexity is bounded by O(M(log(d)) log(log(d))), which completes the proof.

Let T be a torsion coset of GN
m of codimension 1. By (2.8), there is a primitive
vector b ∈ ZN and ξ ∈ µ∞ such that
T = V (y b − ξ).
The following simple lemma gives a monomial change of coordinates putting T into a
standard position.
b
Lemma 2.4. Let T be be a torsion coset of GN
m of codimension 1 given as T = V (y −ξ)
for a primitive vector b ∈ ZN and ξ ∈ µ∞ . Let bj ∈ ZN , j = 1, . . . , N − 1, be a family
of vectors completing b to a basis of ZN and τ ∈ Aut(GN
m ) the automorphism given,
for y ∈ GN
,
by
m
τ (y) = (y b1 , . . . , y bN−1 , y b ).
Then τ (T ) = V (yN − ξ).

Proof. This follows easily from the definitions.



3. Unlikely intersections in algebraic tori
In this section, we collect the different results and conjectures on unlikely intersections in algebraic tori that we will use in the rest of the paper.
As mentioned in the introduction, the algorithm of Filaseta, Granville and Schinzel
relies on a theorem of Bombieri and Zannier. We recall the statement of this result,
in the refined form later obtained by these authors together with Masser in [BMZ07,
Theorem 4.1].
Theorem 3.1. Let W be an irreducible subvariety of GN
m of codimension ≥ 2. There
exists a constant cW depending only on W with the following property. Let ζ ∈ µN
∞,
×
N
a
a
N
1
N
a ∈ Z and α ∈ Q . If (ζ1 α , ..., ζN α ) ∈ W , then there exist b ∈ Z \ {0} such
that
Y
max |bj | ≤ cW and
(ζj αaj )bj = 1.
j

In particular, if α ∈
/ µ∞ , then

P

j

j aj bj = 0.

In theP
special case when ζj = 1 for all j, the existence of the bounded non-trivial
relation j aj bj = 0 was proposed by Schinzel in [Schi65, Conjecture, page 3], anticipating the Zilber conjecture thirty-seven years before its actual formulation!

12

AMOROSO, LEROUX, AND SOMBRA

Remark 3.2. The constant cW in Theorem 3.1 is effectively calculable, as Zannier has
pointed out to us in a personal communication. This is also explained in the remark
following [BMZ07, Theorem 1.6]. Unfortunately, the computation of a bound for this
constant has not been accomplished yet. Obtaining such a bound would enable our
algorithm to be made effective in the univariate case (Algorithm 4.2) and to make
explicit the dependence of its complexity on the height and number of nonzero terms
of the input polynomials.
The following result is a well-known theorem of Laurent giving a positive answer to
the toric case of the Manin-Mumford conjecture [Lau84]. Effective proofs of it can be
found in [Schm96, Ler12].
Theorem 3.3. Let W be a subvariety of GN
m . The collection of torsion cosets contained
in W which are maximal with respect to inclusion is finite. Equivalently, there exists a
finite collection Θ of torsion cosets of GN
m contained in W such that, if B is a torsion
coset contained in W , then there exists T ∈ Θ such that B ⊂ T .
In the context of model theory, Zilber proposed in [Zil02] the following conjecture
on unlikely intersections of subvarieties of GN
m with algebraic subgroups.
Conjecture 3.4 (Zilber conjecture). Let W be a subvariety of GN
m . There exists a
such
that,
if G is a proper
finite collection Ξ of proper algebraic subgroups of GN
m
and
Y
an
irreducible
component
of
G
∩
W
such that
algebraic subgroup of GN
m
(3.1)

dim(Y ) > dim(G) − codim(W ),

then there exists H ∈ Ξ such that Y ⊂ H.
It is not difficult to see that Theorems 3.1 and 3.3 give this conjecture for the
cases when we restrict to algebraic subgroups G with dim(G) = 1 and dim(G) = 0,
respectively.
We will use the following reformulation for locally closed subsets of the Zilber conjecture, which we reinforce by adding the hypothesis that the collection of torsion
cosets can be computed. This is crucial for our algorithmic applications.
Conjecture 3.5. Let W be a locally closed subset of GN
m . There exists a finite and
effectively calculable collection Ω of torsion cosets GN
of
codimension 1 such that, if
m
B is a torsion coset, C an irreducible component of W and Y ⊂ B ∩ C an irreducible
locally closed subset such that
(3.2)

dim(Y ) > dim(B) − codim(C),

then there exists T ∈ Ω such that Y ⊂ T .
Proposition 3.6. Conjecture 3.4 is equivalent to the non-effective version of Conjecture 3.5.
Proof. Suppose that the Zilber conjecture 3.4 holds. Let W ⊂ GN
m be a locally closed
subset and, for each irreducible component Cj of W , let Ξj the finite collection given by
this conjecture applied to the subvariety Cj . We can assume without loss of generality
that each proper algebraic subgroup in Ξj has codimension 1. Consider then the finite
collection Ω of torsion cosets of codimension 1 made of the irreducible components of
the algebraic subgroups in the collections Ξj .
Let B be a torsion coset of GN
m and hBi the minimal algebraic subgroup containing
it. Let C = Cj0 be an irreducible component of W and Y ⊂ B ∩ C an irreducible

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

13

locally closed subset such that (3.2) holds. Let Z be an irreducible component of
hBi ∩ C containing Y . Then
dim(Z) ≥ dim(Y ) > dim(B) − codim(C) = dim(hBi) − codim(C).
It follows that there exists H ∈ Ξj0 such that Z ⊂ H. Since Z is irreducible, there
exists T ∈ Ω such that Z ⊂ T and, a fortiori, Y ⊂ T . Hence, the non-effective version
of Conjecture 3.5 holds with this choice of Ω.
Conversely, suppose that the non-effective version of Conjecture 3.5 holds. Let W
be a subvariety of GN
m and Ω the collection of torsion cosets of codimension 1 given
by this conjecture. Then Ξ = {hT i}T ∈Ω is a finite collection of algebraic subgroups
of codimension 1, and it is easy to verify that it satisfies the conditions of the Zilber
conjecture 3.4.

Definition 3.7. Let W be a locally closed subset of GN
m . An irreducible locally closed
subset Y of W is called atypical if there is a torsion coset B of GN
m and an irreducible
component C of W such that Y ⊂ B ∩ C and dim(Y ) > dim(B) − codim(C). The
exceptional subset of W is defined as
[
W exc =
Y.
Y atypical

Notation 3.8. Suppose that Conjecture 3.5 holds. Given a locally closed subset W
of GN
m , we denote by ΩW a choice of a finite and effectively calculable collection of
torsion cosets of codimension 1 satisfying the conditions of this conjecture. We also
write
[
[
ΩW =
T.
T ∈ΩW

Conjecture 3.5 implies that the
S exceptional set of a locally closed subset W is contained in the torsion subvariety ΩW . In particular, if W is not contained in a proper
exc is a proper subset of W .
torsion subvariety of GN
m , then W
4. The univariate case
In this section, we present an algorithm that, given a system of univariate polynomials with coefficients in the number field K, of degree bounded by d and bounded
height and number of nonzero coefficients, computes a single polynomial defining the
e
same zero set with O(log(d))
ops. Our approach is inspired by the one in [FGS08], but
it is simpler and more geometric.
The following subroutine is one of the main components of the algorithm. It tests
whether a subtorus of codimension 1 contains the image of a homomorphism and, if
this is the case, reduces the dimension of the problem by intersecting the variety under
consideration with that subtorus.
Lemma 4.1. For a given input (ϕ, T, F ), Algorithm 4.1 stops after a finite number of
steps. It decides if im(ϕ) ⊂ T and, if this is the case, its output (ϕ,
e F ) satisfies
(4.1)

e ) = ϕ# (F ).
ϕ
e# (F

e )) = ϕ−1 (V (F )).
In particular, ϕ
e−1 (V (F
If size(ϕ) ≤ d, then size(ϕ)
e ≤ OT (d) and each Fei has degree, height and number of
nonzero coefficients bounded by OT,F (1). The complexity of the algorithm is bounded
by OT (log(d)) + OT,F (1) ops.

14

AMOROSO, LEROUX, AND SOMBRA

Algorithm 4.1 (Reduction of dimension for ideals)
N
Input: a homomorphism ϕ ∈ Hom(Gnm , GN
m ), a subtorus T ⊂ Gm of codimension 1,
±1
±1
and a family of Laurent polynomials Fi ∈ K[y1 , . . . , yN ], i = 1, . . . , s.
N −1 ) and a family
Output: either “im(ϕ) 6⊂ T ”, or a homomorphism ϕ
e ∈ Hom(Gnm , Gm
±1
±1
of Laurent polynomials Fei ∈ K[y1 , . . . , yN −1 ], i = 1, . . . , s.
1. Let A ∈ ZN ×n be the N × n-matrix associated to ϕ and b ∈ ZN a primitive vector
such that T = V (y b − 1);
2. if bA = 0 then
3.
choose τ ∈ Aut(GN
m ) such that τ (T ) = V (yN − 1) as in Lemma 2.4;
N −1 → GN be the standard inclusion identifying GN −1 with the hy4.
let ι : Gm
m
m
N −1 the projection onto the first N − 1
perplane V (yN − 1), and π : GN
m → Gm
coordinates;
5.
return ϕ
e ← π ◦ τ ◦ ϕ and Fei ← (τ −1 ◦ ι)# (Fi ), i = 1, . . . , s;
6. else
7.
return “im(ϕ) 6⊂ T ”;
8. end if

Proof. Let notation be as in Algorithm 4.1. Under the correspondence in (2.4), the
subtorus im(ϕ) is associated to the kernel of the linear map At : ZN → Zn , for the
matrix A in line 1 of the algorithm. Then T = V (y b − 1) contains the image of ϕ
if and only if b ∈ ker(At ) or, equivalently, if bA = 0. Hence, the algorithm decides
correctly whether this holds.
To prove (4.1), assume that im(ϕ) ⊂ T . Consider the diagram
π

τ

GN
OOm
?

T ff

gg

''
τ −1

))

GN
OO m

))
hh

?

ι

V (yN − 1)
ii

))

N −1
Gm

N −1
Gm

where the maps in the second line are induced by the ones in the first line. These
maps in the second line are isomorphisms. Considering the corresponding maps of
K-algebras, we deduce that
e)
(F ) + (y b − 1) = (π ◦ τ )# ((τ −1 ◦ ι)# ((F ) + (y b − 1)) = (π ◦ τ )# (F

because (τ −1 ◦ ι)# (y b − 1) = ι# (yN − 1) = 0. We also have that ϕ# (y b − 1) = 0
because im(ϕ) ⊂ T . Using the functoriality (2.2), it follows that
e )) = ϕ
e ),
ϕ# (F ) = ϕ# ((F ) + (y b − 1)) = ϕ# ((π ◦ τ )# (F
e# (F

e )) = ϕ−1 (V (F )).
as stated. Clearly, this implies that ϕ
e−1 (V (F
Now suppose that size(ϕ) ≤ d. The automorphism τ in line 3 depends only on T .
Hence, the construction of ϕ
e in line 5 implies that size(ϕ)
e ≤ OT (d). The construction
of each Fei , also in line 5, consists of composing Fi with a homomorphism depending
only on T . Hence, the number of nonzero coefficients of Fei is bounded by that of Fi ,
and its degree and height are bounded by OT,F (1).
The verification bA = 0 in line 2 costs OT (log(d)) ops using classical multiplication
of integers. The construction of τ in line 3 uses OT (1) ops. The computations in line 5
of ϕ
e and Fei , i = 1, . . . , s, take OT (log(d)) ops and OT,F (1) ops, respectively, using

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

15

classical multiplication. Hence, the overall complexity of the algorithm is bounded by
OT (log(d)) + OT,F (1) ops.

Remark 4.2. The Laurent polynomials Fei , i = 1, . . . , s, in Algorithm 4.1, line 5, can
be written down, in more explicit terms, as
Fei = Fi ◦ τ −1 (y1 , . . . , yN −1 , 1).

The following procedure computes the non-torsion points in the zero set of a system of univariate polynomials, and gives the first half of the algorithm. It is based
on the strategy described in (1.5). In the univariate setting, we apply Theorem 3.1
to successively intersect the linear subvariety W until all non-torsion points lie in a
hypersurface (while loop between lines 4 and 14 in Algorithm 4.2 below). Once this is
achieved, the hypersurface is described by a single polynomial that we obtain through
a gcd computation, and the non-torsion points are obtained as the inverse image under
a homomorphism of this hypersurface (lines 15 and 16).
For a Laurent polynomial p ∈ K[x±1 ]\{0}, we denote by ord(p) the maximal integer
m such that x−m p ∈ K[x].
Algorithm 4.2 (Non-torsion points)
Input: a family of polynomials fi ∈ K[x], i = 1, . . . , s.
Output: a polynomial p1 ∈ K[x].
PN
S
aj with α
1. Write fi =
i,j ∈ K and aj ∈
j=1 αi,j x
i supp(fi );
PN
2. set Fi ←
j=1 αi,j yj , i = 1, . . . , s and F ← (F1 , . . . , Fs );
3. set k ← 0 and let ϕ ∈ Hom(Gm , GN
m ) be the homomorphism corresponding to the
exponents aj ∈ N, j = 1, . . . , N ;
4. while k < N do
5.
for each irreducible component W of V (F ) of codimension ≥ 2, compute cW as in
Theorem 3.1 and set Φ ← {V (y b − 1) | b ∈ ZN primitive such that maxj |bj | ≤
maxW cW };
6.
while Φ 6= ∅ do
7.
choose T ∈ Φ and apply Algorithm 4.1 to (ϕ, T, F );
8.
if im(ϕ) ⊂ T then
e , ϕ ← ϕ,
9.
set F ← F
e k ← k + 1, Φ ← ∅;
10.
else
11.
set Φ ← Φ \ {T };
12.
end if
13.
end while
14. end while
15. set p ← ϕ# (gcd(F1 , . . . , Fs ));
16. return p1 ← x−ord(p) p.
Theorem 4.3. Given fi ∈ K[x], i = 1, . . . , s, Algorithm 4.2 stops after a finite number
of steps and computes p1 ∈ K[x] such that
 gcd(f , . . . , f ) 
1
s
p1 | gcd(f1 , . . . , fs ) and V
⊂ µ∞ .
p1

If s is bounded and each fi has degree bounded by d and bounded height and number
of nonzero coefficients, then p1 has degree bounded by d, and height and number of

16

AMOROSO, LEROUX, AND SOMBRA

nonzero coefficients bounded by O(1). The complexity of the algorithm is bounded by
O(log(d)) ops.
Proof. For i = 0, . . . , s, the initial value of Fi at line 2 satisfies
(4.2)

ϕ# (Fi ) = fi .

By Lemma 4.1, this holds also for the updated values of Fi and ϕ in line 9. Hence, the
equality (4.2) holds for the final value of Fi as in line 15. For the rest of this proof, we
denote by Fi this final value.
±1
Set P = gcd(F1 , . . . , Fs ). We have that (F1 , . . . , Fs ) ⊂ (P ) ⊂ K[y1±1 , . . . , yN
−k ],
±1
The equality (4.2) implies that (f1 , . . . , fs ) ⊂ (p) ⊂ K[x ] and so
p1 | gcd(f1 , . . . , fs )

in K[x].

Set f = {f1 , . . . , fs } and F = {F1 , . . . , Fs } for short. Let α ∈ V (f ) \ µ∞ , so that
ϕ(α) ∈ V (F ). Let W an irreducible component of V (F ) such that
ϕ(α) = (αa1 , . . . , αaN ) ∈ W.
By Theorem 3.1, W is necessarily of codimension 1. Otherwise, there would exist
T ∈ Φ such that im(ϕ) ⊂ T but, by construction, this is not possible.
±1
This discussion implies that the ideal (F ) ⊂ K[y1±1 , . . . , yN
−k ] becomes principal
N
−k
of ϕ(V (f ) \ µ∞ ). Hence,
when restricted to a suitable neighborhood U ⊂ Gm
(F ) = (P ) on that neighborhood. We deduce that ϕ−1 (U ) is a neighborhood of
V (f ) \ µ∞ and (f ) = ϕ# (p) on ϕ−1 (U ). Thus, V (gcd(f1 , . . . , fs )/p1 ) ∩ ϕ−1 (U ) = ∅
or, equivalently,
 gcd(f , . . . , f ) 
1
s
⊂ µ∞ .
V
p1
This completes the proof of the first part of the statement.
For the second, part, assume that s is bounded and that the fi ’s have degree bounded
by d, and bounded height and number of nonzero coefficients. The construction of
P = gcd(F1 , . . . , Fs ) does not depend on the exponents aj . Hence, the height and
number of nonzero coefficients of P is bounded, and so this also holds for p1 . The fact
that p1 divides gcd(f1 , . . . , fs ) implies that deg(p1 ) ≤ d. The list of linear forms F in
line 2 does not depend on the exponents aj and so, a fortiori, it is independent on the
degree of the input polynomials fi . Therefore, the computations in lines 5 and 15 cost
O(1) ops. By Lemma 4.1, the computation in line 7 costs O(log(d)) ops. Since the
number of iterations in the while loop between lines 4 and 14 is bounded, we conclude
that the overall complexity of the algorithm is bounded by O(log(d)), as stated.

The following procedure computes the torsion points in the zero set of a system
of univariate polynomials, and completes the algorithm. It consists in considering
the finite collection of maximal torsion cosets given by Theorem 3.3 for the linear
subvariety W as in (1.5), and compute with Algorithm 2.1 its inverse image with
respect to the homomorphism ϕ.
Theorem 4.4. Given fi ∈ K[x], i = 1, . . . , s, Algorithm 4.3 stops after a finite number
of steps and computes p2 ∈ K[x] such that
V (p2 ) = V (f1 , . . . , fs ) ∩ µ∞ .
If s is bounded and each fi has degree bounded by d and bounded height and number
of nonzero coefficients, then p2 has degree bounded by O(d) and height and number of
nonzero coefficients bounded by O(1). The complexity of the algorithm is bounded by
e
O(M(log(d)) log(log(d))) = O(log(d))
ops.

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

17

Algorithm 4.3 (Torsion points)
Input: a family of polynomials fj ∈ K[x], j = 1, . . . , s.
Output: a polynomial p2 ∈ K[x].
PN
S
aj with α
1. Write fi =
i,j ∈ K and aj ∈
j=1 αi,j x
i supp(fi );
PN
2. set Fi ←
j=1 αi,j yj , i = 1, . . . , s;
N
3. set W ← V (F1 , . . . , Fs ) ⊂ GN
m , ϕ ∈ Hom(Gm , Gm ) the homomorphism corresponding to the exponents aj ∈ N, j = 1, . . . , N , and Λ ← ∅;
4. compute the collection Θ of maximal torsion cosets of W from Theorem 3.3;
5. for B ∈ Θ do
6.
apply Algorithm 2.1 to the pair (ϕ, B);
7.
if ϕ−1 (B) 6= ∅ then
8.
let E be the output of Algorithm 2.1, write E = {xb − ξ} with b ∈ N and
ξ ∈ µ∞ , and add the binomial xb − ξ to Λ;
9.
end if
10. end for
Q
11. return p2 ← g∈Λ g.
Proof. Write f = (f1 , . . . , fs ) for short and let Θ be as in line 4 of the algorithm. Then
[
V (f ) ∩ µ∞ =
ϕ−1 (B).
B∈Θ

With notation as in line 8, we have that ϕ−1 (B) = V (xb − ξ) because of (2.9). It
follows that
[
V (f ) ∩ µ∞ =
V (g) = V (p2 ).
g∈Λ

The collection Θ is invariant under K-automorphisms of Q and so is p2 . It follows
that p2 ∈ K[x], completing the proof of the first part of the statement.
The construction of W in line 3 and, a fortiori, that of Θ, do not depend on the
exponents aj . Hence, the size of Θ is bounded by O(1) and its computation costs O(1)
ops. Hence, the number of steps in the for loop between lines 5 and 10 is bounded by
O(1). The second part of the statement then follows easily from Lemma 2.3.

Putting together Theorems 4.3 and 4.4, we obtain the following more general and
precise version of Theorem 1.1 in the introduction.
Theorem 4.5. Given fi ∈ K[x], i = 1, . . . , s, Algorithms 4.2 and 4.3 compute p1 , p2 ∈
K[x] such that p1 | gcd(f1 , . . . , fs ),
V (p1 ) \ µ∞ = V (gcd(f1 , . . . , fs )) \ µ∞

and

V (p2 ) = V (gcd(f1 , . . . , fs )) ∩ µ∞ .

If s is bounded and each fi has degree bounded by d, bounded height and number of
nonzero coefficients, then deg(p1 ) ≤ d and deg(p2 ) ≤ O(d), and the height and number
of nonzero coefficients of both p1 and p2 are bounded by O(1). The complexity of the
e
procedure is bounded by O(M(log(d)) log(log(d))) = O(log(d))
ops.
5. The multivariate case

In this section, we present the procedure for the reduction of overdetermined systems
of multivariate polynomial equations. We first give a simple algorithm which allows us
to treat the components of top multiplicative rank. Strictly speaking, this procedure
is not needed to treat the general case, but it is considerably simpler and serves as

18

AMOROSO, LEROUX, AND SOMBRA

a first approach. After this, we give the main procedure (Algorithm 5.5) and prove
Theorem 1.3 in the introduction.
We will express our algorithms in terms of geometrical objects to avoid the burden
of their syntactical treatment in terms of families of Laurent polynomials. As before,
we denote by K a number field together with an inclusion into Q.
5.1. The weakly transverse case. The following is a reformulation of Algorithm 4.1
in terms of locally closed subsets.
Algorithm 5.1 (Reduction of dimension for locally closed subsets)
Input: (n, N, ϕ, T, W ) where n and N are positive integers, ϕ ∈ Hom(Gnm , GN
m ) is a
N
homomorphism, T ⊂ GN
m is a subtorus of codimension 1, and W ⊂ Gm is a locally
closed subset.
N −1 ) and a locally
Output: either “im(ϕ) 6⊂ T ”, or a homomorphism ϕ
e ∈ Hom(Gnm , Gm
f ⊂ GN −1 .
closed subset W
m
±1
±1
1. Take F , G ⊂ Q[y1 , . . . , yN ] such that W = V (F ) \ V (G);
e)
2. apply Algorithm 4.1 to (ϕ, T, F ) and to (ϕ, T, G) and, if im(ϕ) ⊂ T , set (ϕ,
e F
e for its output;
and (ϕ,
e G)
f ← V (F
e ) \ V (G).
e
3. return W
Lemma 5.1. For a given input (ϕ, T, W ), Algorithm 5.1 stops after a finite number
of steps. It decides whether im(ϕ) ⊂ T and, if this is the case, its output satisfies

(5.1)

f ) = ϕ−1 (W ).
ϕ
e−1 (W

f have
If size(ϕ) ≤ d, then size(ϕ)
e ≤ OT (d) and the Laurent polynomials defining W
degree, height and number of nonzero coefficients bounded by OT,F (1). The complexity
of the algorithm is bounded by OT,W (log(d)) ops.
Proof. This follows readily from Lemma 4.1.



Definition 5.2. Let X be an irreducible locally closed subset of Gnm . Following Viada [Via08], we say that X is weakly transverse if it is not contained in any proper
torsion coset or, equivalently, if rank(X) = n.
Remark 5.3. An irreducible locally closed subset X ⊂ Gnm is weakly transverse if and
only if it is not atypical as a subset of itself. If ΩX denotes a finite collection of torsion
cosets of GSnm of codimension 1 as in Notation 3.8, this is equivalent to the condition
that X 6⊂ ΩX .
The following procedure is the natural generalization of Algorithm 4.2 to the multivariate case.

Theorem 5.4. Assume that Conjecture 3.5 holds. Given a subvariety V ⊂ Gnm , Algorithm 5.2 stops after a finite number of steps and its output satisfies:
(1)
V =

[

Z;

Z∈Γ

(2) each Z ∈ Γ is given as the zero set of lZ Laurent polynomials in the complement
of the zero set of a further Laurent polynomial. Moreover, if C is an irreducible
component of Z that is weakly transverse, then codim(C) = lZ .

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

19

Algorithm 5.2 (Reduction of weakly transverse components)
Input: a subvariety V ⊂ Gnm defined by a linearly independent family of Laurent
±1
polynomials in Q[x±1
1 , . . . , xn ];
Output: a finite collection Γ of locally closed subsets of Gnm .
1. Let fi , i = 1, . . . , s, be the Laurent polynomials defining V and write fi =
S
PN
aj with α
supp(fi );
i,j ∈ Q and aj ∈
j=1 αi,j x
PN
Pi N
2. set k ← 0, W ← V ( j=1 α1,j yj , . . . , j=1 αs,j yj ) ⊂ GN
m , t ← 1, W1 ← W , and
n
N
ϕ ∈ Hom(Gm , Gm ) the homomorphism corresponding to the exponents aj ∈ Zn ,
j = 1, . . . , N ;
3. compute the collection ΩW1 of torsion cosets of codimension 1 (Notation 3.8) and
set Φ ← {T ∈ ΩW1 | T is a subtorus};
4. while ∃ T ∈ Φ such that im(ϕ) ⊂ T do
f ) its
5.
apply Algorithm 5.1 with input (n, N − k, ϕ, T, W ) and denote by (ϕ,
e W
output;
f , ϕ ← ϕ,
6.
set W ← W
e k ← k + 1;
7.
compute a complete intersection stratification (Wj )1≤j≤t of W (PropositionDefinition 2.1);
8.
compute the collections ΩWj , j = 1, . . . , t;
S
9.
set Φ ← tj=1 {T ∈ ΩWj | T is a subtorus};
10. end while
11. return Γ ← {ϕ−1 (Wj )}1≤j≤t .
If n is bounded and V is defined over K by a bounded number of Laurent polynomials
of degree ≤ d, of bounded height and number of nonzero coefficients, then the cardinality
of Γ is bounded by O(1), the Laurent polynomials defining each Z ∈ Γ have coefficients
in K, degree bounded by O(d), and height and number of nonzero coefficients bounded
by O(1). The complexity of the algorithm is bounded by O(log(d)) ops.
Proof. If Conjecture 3.5 holds, then the computation of the collections ΩWj in lines 3
and 8 can be done and the algorithm makes sense. At each while loop (lines 4 to 10),
the value of the variable k in line 6 increases by one. Hence, this while loop cannot be
repeated more than N times since when k = N , the collection Φ in line 9 is empty.
Hence, the algorithm stops after a finite number of steps.
N −k
To prove (1), we first show that, after each while loop, the subvariety W ⊂ Gm
N
−k
n
and the homomorphism ϕ ∈ Hom(Gm , Gm ) satisfy
(5.2)

V = ϕ−1 (W ).

By construction, this is clear for the initial values of W and ϕ in line 2. Now suppose
that (5.2) holds at the start of the while loop. If this loop is actually executed, then
there exists a subtorus T ∈ Φ such that im(ϕ) ⊂ T . With notation as in line 5, by
f ). We conclude that (5.2) also holds for the
(5.1) it follows that ϕ−1 (W ) = ϕ
e−1 (W
updated values of W and ϕ in line 6.
N −k the final value of this variFor the rest of this proof, we denote by W ⊂ Gm
able after the last execution of the while
S loop, and (Wj )j its corresponding complete
intersection stratification. Then W = j Wj and so
[
[
V =
ϕ−1 (Wj ) =
Z.
j

Z∈Γ

20

AMOROSO, LEROUX, AND SOMBRA

The first part of (2) follows from the definition of a complete intersection stratification and the construction of Γ in line 11. We now prove the second part. Let
C be an irreducible component of Z ∈ Γ that is weakly transverse and suppose that
codim(C) < lZ . Let Wj be a stratum in the complete intersection stratification of W
of codimension lZ and such that Z = ϕ−1 (Wj ). Let Y be an irreducible component of
Wj ∩ im(ϕ) such that C is an irreducible component of ϕ−1 (Y ). Applying Lemma 2.2
and the fact that C is weakly transverse, we obtain that
(5.3)

codim(C) = rank(C) − dim(C) = rank(Y ) − dim(Y ).

The fact that C is weakly transverse also implies that hY i = im(ϕ) and so rank(Y ) =
e be an irreducible component of Wj containing Y , so that Y ⊂
dim(im(ϕ)). Let C
e From (5.3), we deduce that
im(ϕ) ∩ C.
e
dim(Y ) > dim(im(ϕ)) − codim(C).

Conjecture 3.5 then implies that there exists T ∈ ΩWj such that Y ⊂ T . It follows
that im(ϕ) ⊂ T and that T is a subtorus. But this cannot happen since, otherwise,
the while loop would not been terminated. We deduce that codim(C) ≥ lZ .
On the other hand, since Z is defined by lZ equations in the complement of a
hypersurface, it follows that codim(C) = lZ , proving the second part of (2).
The subvariety W in line 2 does not depend on the exponents aj and so, a fortiori,
is independent on the bound d for the degrees of the polynomials defining V . The
bounds for the size of the output and the complexity of the algorithm then follow
easily from Lemma 4.1.

With notation and assumptions as in Theorem 5.4, denote by Γmax the subset of Γ
consisting of the locally closed subsets Z ∈ Γ such that Z is maximal with respect to
inclusion. Clearly,
[
Z.
V =
Z∈Γmax

Hence, given an irreducible component C of V that is weakly transverse, there exists
Z ∈ Γmax such that C is an irreducible component of the closure Z. By Theorem 5.4(2),
the equations defining Z form a complete intersection in a suitable neighborhood of C.
This observation is clear in the case when all the irreducible components of V are
weakly transverse.
Corollary 5.5. Let notation and assumptions be as in Theorem 5.4. Suppose that all
the irreducible components of V are weakly transverse. Then Algorithm 5.2 gives every
locally closed subset Z ∈ Γmax as a complete intersection outside a hypersurface.

Proof. Let Z ∈ Γmax and C an irreducible component of Z. Then C is an irreducible
component of V , and so it is weakly transverse. By Theorem 5.4(2), the equations
defining Z form a complete intersection in a neighborhood of C. Since this holds for
all the components of Z, it follows that this locally closed subset is given as a complete
intersection outside a hypersurface.

For instance, if we know a priori that dim(V ) = 0 and all points in V have multiplicatively independent coordinates, then
[
V =
Z,
Z

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

21

where the union is over the locally closed subsets produced by Algorithm 5.2 and
given as the zero set of n equations outside a hypersurface. Each of these locally
closed subsets are either of dimension 0, or the empty set.
5.2. The general case. We devote the rest of this section to the general multivariate
case. We first give a simple subroutine which, given a locally closed subset W of an
algebraic torus and a torsion coset of codimension 1, computes their intersection as a
locally closed subset of an algebraic torus of lower dimension.
Algorithm 5.3 (Intersecting with a torsion coset)
Input: N, k ∈ N such that N > k and a quadruple (η, W, T, δ) with η ∈ µk∞ , W ⊂
N −k a locally closed subset defined over K(η), T ⊂ GN −k a torsion coset of
Gm
m
codimension 1, and δ ∈ Aut(GN
m ).
N −k−1 a locally closed subset
e with η
f , δ)
f
e ∈ µk+1
Output: a triple (e
η, W
∞ , W ⊂ Gm
defined over K(e
η ), and δe ∈ Aut(GN
m ).
b
1. Write T = V (y − ξ) for a primitive vector b ∈ ZN −k and ξ ∈ µ∞ ;
N −k ) such that τ (T ) = V (y
2. choose τ ∈ Aut(Gm
N −k − ξ) as in Lemma 2.4 and let
N
−k−1
N
−k
π : Gm → Gm
be the projection onto the first N − k − 1 coordinates;
f ← π(τ (W ) ∩ V (yN −k − ξ)) and δe ← (τ × idGk ) ◦ δ;
e ← ξ × η, W
3. return η
m
Lemma 5.6. For a given input (η, W, T, δ), the output of Algorithm 5.3 satisfies
f × {e
δ−1 ((W ∩ T ) × {η}) = δe−1 (W
η }).

f × {ξ}. We
Proof. With notation as in the algorithm, we verify that τ (W ∩ T ) = W
deduce that
f × {e
f × {e
η }) = δe−1 (W
η }),
δ−1 ((W ∩ T ) × {η}) = (δ−1 ◦ (τ × idGk )−1 )(W
m

as stated.



f in Algorithm 5.3, line 3, can be represented
Remark 5.7. The locally closed subset W
±1
as follows. Write W = V (F ) \ V (G) with Fj , Gl ∈ Q[y1±1 , . . . , yN
−k ]. Then

f = V (F
e ) \ V (G)
e
W
el = Gl ◦ τ −1 (y1 , . . . , yN −k−1 , ξ).
with Fej = Fj ◦ τ −1 (y1 , . . . , yN −k−1 , ξ) and G

In Algorithm 5.4 below, we apply the previous procedure to a subvariety W0 of
GN
m and the torsion cosets successively produced by Conjecture 3.5. We thus obtain a
decomposition of W0 as a union of a finite collection of complete intersections outside
hypersurfaces with empty exceptional subset (Definition 3.7).
Lemma 5.8. Assume that Conjecture 3.5 holds. Given a subvariety W0 ⊂ GN
m defined
over K, Algorithm 5.4 stops after a finite number of steps and its output has the
following properties:
(1)
N
[
[
δ−1 (W × {η});
W0 =
k=0 (W,η,δ)∈Λk

(2) the locally closed subset W in a triple (η, W, δ) ∈ Λk is given by a collection of
Laurent polynomials over K(η) defining a complete intersection in the complement of a hypersurface;

22

AMOROSO, LEROUX, AND SOMBRA

Algorithm 5.4 (Descent)
Input: a subvariety W0 ⊂ GN
m defined over K.
Output: for k = 0, . . . , N , a finite collection Λk of triples (η, W, δ) with η ∈ µk∞ ,
N −k a locally closed subset and δ ∈ Aut(GN ).
W ⊂ Gm
m
1. Set Σ0 ← {(1G0m , W0 , idGN )}, where 1G0m denotes the neutral element of G0m ;
m
2. for k from 0 to N do
3.
set Λk ← ∅ and Σk+1 ← ∅;
4.
for (η, W, δ) ∈ Σk do
5.
compute a complete intersection stratification (Wj )j of W defined over K;
6.
computeSthe collections ΩWj for allSj;
7.
if Wj 6⊂ ΩWj , then add (η, Wj \ ΩWj , δ) to Λk ;
8.
for each j and T ∈ ΩWj do
9.
apply Algorithm 5.3 to (η, Wj , T, δ) and add its output to Σk+1 ;
10.
end for
11.
end for
12. end for
(3) if (η, W, δ) ∈ Λk for some k and Z ⊂ GN
m is an irreducible locally closed subset
contained in δ−1 (W × {η}), then
rank(Z) − dim(Z) ≥ codim(W ).
Proof. If Conjecture 3.5 holds, the computation of the collections ΩWj in line 6 of the
algorithm can be performed and so Algorithm 5.4 stops after a finite number of steps.
We first show that, for k = 0, . . . , N + 1,

 
 k−1
[
[
[
−1
−1
δ (W × {η}) .
δ (W × {η}) ∪
(5.4)
W0 =
l=0 (η,W,δ)∈Λl

(η,W,δ)∈Σk

This is clear for k = 0, because of the definition of Σ0 in line 1 and the fact that
the first union in the right-hand side is empty. For k ≥ 1, the construction of the
collections Λk and Σk+1 in lines 7 and 9 together with Lemma 5.6 implies that

 

[
[
[
−1
−1
−1
δ (W ×{η}) .
δ (W ×{η}) ∪
δ (W ×{η}) =

(η,W,δ)∈Σk

(η,W,δ)∈Λk

(η,W,δ)∈Σk+1

Then (5.4) follows from the inductive hypothesis. For (η, W, δ) ∈ ΣN , the collections
ΩWj are empty. Hence, ΣN +1 = ∅. The statement (1) then follows from the case
k = N + 1 of (5.4).
Statement (2) is clear from the construction of Λk in line 7.
To prove (3), let Z ′ be the locally closed subset of W such that Z = δ−1 (Z ′ × {η}).
The locally closed subset W is equidimensional and has empty exceptional subset,
since it is the complement in Wj of the collection ΩWj . Hence Z ′ is not atypical
(Definition 3.7), which implies that
rank(Z ′ ) − dim(Z ′ ) = codim(W ).
In turn, this implies (3) since rank(Z) = rank(Z ′ ) and dim(Z) = dim(Z ′ ).

S
Remark 5.9. The condition Wj 6⊂ ΩWj in line 7 is equivalent to the fact that Wj
has at least one irreducible component that is weakly transverse, see Remark 5.3. This
test avoids adding to the collection Λk a triple with an empty locally closed set.

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

23

Algorithm 5.5 below gives the procedure for the reduction of overdetermined systems. First, it applies Algorithm 5.4 to decompose the linear subvariety W ⊂ GN
m
into pieces without exceptional subset. Then, it produces the sought decomposition of
the zero set of the given system of equations as the inverse image of these pieces with
respect to the homomorphism ϕ.
Algorithm 5.5 (Reduction of overdetermined systems)
Input: a subvariety V ⊂ Gnm defined over K.
Output: a finite collection Γ of locally closed subsets Y ⊂ Gnm defined over a cyclotomic extension of K.
1. Let fi , i = 1, . . . , s, be the Laurent polynomials defining V and write fi =
PN
S
aj with α
i,j ∈ K and aj ∈
j=1 αi,j x
i supp(fi );
PN
PN
2. set W ← V ( j=1 α1,j yj , . . . , j=1 αs,j yj ) ⊂ GN
m;
3. apply Algorithm 5.4 to W and set (Λk )0≤k≤N for its output;
N
4. let ϕ ∈ Hom(Gn
m , Gm ) be the homomorphism corresponding to the exponents
n
aj ∈ Z , j = 1, . . . , N ;
5. for k from 0 to N do
N −k and π : GN → Gk for the projections onto the first N − k
6.
set π1 : GN
2
m → Gm
m
m
coordinates and the last k coordinates, respectively;
7.
for (η, W, δ) ∈ Λk do
8.
apply Algorithm 2.1 to the homomorphism π2 ◦ δ ◦ ϕ : Gnm → Gkm and the
torsion coset {η} ⊂ Gkm ;
9.
if ϕ−1 (η) 6= ∅ then
10.
let E = {pj }1≤j≤t be the output of Algorithm 2.1;
11.
let Fj , j = 1, . . . , l, and G be the Laurent polynomials over K(η) defining W ;
12.
set pt+j ← Fj ◦ π1 ◦ δ ◦ ϕ, j = 1, . . . , l, and q ← G ◦ π1 ◦ δ ◦ ϕ;
13.
set Y ← V (p1 , . . . , pt+l ) \ V (q) and add Y to Γ;
14.
end if
15.
end for
16. end for

Theorem 5.10. Assume that Conjecture 3.5 holds. Given a subvariety V ⊂ Gnm defined over K, Algorithm 5.5 stops after a finite number of steps and its output satisfies:
(1)
V =

[

Y;

Y ∈Γ

(2) each locally closed subset Y ∈ Γ is either given as a complete intersection in
the complement of a hypersurface, or it is the empty set.
If n is bounded and V is defined by a bounded number of Laurent polynomials of
degree ≤ d, bounded height and number of nonzero coefficients, then the cardinality of
Γ is bounded by O(1), the Laurent polynomials defining each Y ∈ Γ are defined over
a cyclotomic extension of degree O(1), have degree bounded by dO(1) , and height and
number of nonzero coefficients bounded by O(1). The complexity of the algorithm is
e
bounded by O(M(log(d)) log(log(d))) = O(log(d))
ops.

24

AMOROSO, LEROUX, AND SOMBRA

Proof. Let 0 ≤ k ≤ N and (η, W, δ) ∈ Λk be as in line 7 of the algorithm. In case
ϕ−1 (η) 6= ∅, we denote by Y the locally closed subset associated to this triple. By
construction,
(
∅
if ϕ−1 (η) = ∅,
−1
(5.5)
(δ ◦ ϕ) (W × {η}) =
Y
if ϕ−1 (η) 6= ∅.
The decomposition in (1) then follows from the one in Lemma 5.8(1) and the fact that
ϕ−1 (W ) = V .
To prove (2), suppose that Y is nonempty and let C be one of its irreducible components. By (5.5), there is an irreducible component Z of (W × {η}) ∩ im(δ ◦ ϕ) such
that C = (δ ◦ ϕ)−1 (Z). Applying Lemmas 2.2 and 5.8(3), we deduce that
(5.6)

rank(C) − dim(C) = rank(Z) − dim(Z) ≥ codim(W ) = l.

On the other hand, we have that C ⊂ (δ ◦ ϕ)−1 (η) and so rank(C) ≤ n − t, thanks to
Lemma 2.3. Together with (5.6), this implies that
codim(C) = n − dim(C) ≥ t + l.
Since Y is defined by the t+l Laurent polynomials p1 , . . . , pt+l outside the hypersurface
V (q), it follows that codim(C) = t + l. Hence, Y is a complete intersection outside
V (q), as stated.
Now assume that both n and s are bounded and that each fi is of degree ≤ d, of
bounded height and number of nonzero coefficients. The variety W ⊂ GN
m in line 2 does
not depend on d. Hence, the application of Algorithm 5.4 in line 3 produces a output
of size O(1) using O(1) ops. In particular, the collection Γ has cardinality bounded
by O(1). Lemma 2.3 shows that the binomials in the collection E in line 10 have
coefficients in µl for l ≤ O(1), that the Laurent polynomials defining Y have degree,
height and number of nonzero coefficients as predicted by Theorem 5.10, and that
the complexity of this step is bounded by O(M(log(d)) log(log(d))) ops. From this, we
e
deduce that the overall complexity is bounded by O(M(log(d)) log(log(d))) = O(log(d))
ops.


Remark 5.11. For Y ∈ Γ, the defining equations and inequations come from different
sources. In the notation of Algorithm 5.5, the Laurent polynomials pi , i = 1, . . . , t,
are binomials with coefficients in µ∞ , whereas pi , i = t + 1, . . . , t + l come from the
equations defining W . If Y 6= ∅ and C is an irreducible component of Y , we have that
t = n − rank(C),

l = rank(C) − dim(C).

Theorem 1.3 in the introduction follows by decomposing the affine space An as a
disjoint union of tori and applying Theorem 5.10 to each of them.
Proof of Theorem 1.3. Given a subset I ⊂ {1, . . . , n}, we consider the locally closed
subset GI = {x ∈ An | xi 6= 0 if and only if i ∈ I}. The affine space then decomposes
as a disjoint union
G
An =
GI ,
I

G#I
m

and each GI is an algebraic torus
embedded into the standard linear subspace
V ({xi | i ∈
/ I}) of An .
Given a system of equations over An , we can split it into 2n systems of equations
over these algebraic tori. For each I, we solve the corresponding system of equations by
applying Algorithm 5.5 and we multiply the obtained Laurent polynomials by suitable
monomials in order to clear all possible denominators. Finally, we add the set of

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

25

variables xi , i ∈
/ I, to the obtained Q
equations, and we multiply the polynomial defining
the open subset by the monomial i∈I xi .
By Theorem 5.10(1), the resulting polynomials form a collection of systems of equations which define either a complete intersection in the complement of a hypersurface, or the empty set. By Theorem 5.10(2), this collection gives a decomposition of
V (f1 , . . . , fs ) as in (1.3). The rest of the statement follows also from Theorem 5.10. 
Remark 5.12. In practice, there are a number of modifications that can be applied to
our general procedure. They do not affect the theoretical complexity of the algorithms,
but can significantly simplify the computations in concrete examples.
(1) For a given system of equations, it is better to apply Algorithm 5.1 several
times, starting with a subtorus T ⊂ GN
m of codimension 1 of small degree and
the linear subvariety W ⊂ GN
.
If
it
turns
that im(ϕ) ⊂ T , then this procedure
m
reduces the dimension of the ambient space without breaking W into several
pieces, as might happen when applying the descent in Algorithm 5.5.
(2) Both in Algorithms 5.2 and 5.5, one can replace the linear subvariety W ⊂ GN
m
N −1 given by
by the subvariety of Gm


N
N
X
X
αs,j yj
α1,j yj , . . . , αs,1 +
V α1,1 +
j=2

j=2

and ϕ by the homomorphism associated to the vectors aj − a1 , j = 2, . . . , N .
In this way, computations start in a space of dimension N − 1 instead of one
of dimension N .

(3) The locally closed subsets Y of Gnm produced by Algorithm 5.5 have codimension bounded by n. Hence, in line 7 of this algorithm, it suffices to consider
only the triples (η, W, δ) such that codim(W ) ≤ n. Consequently, in line 5 of
Algorithm 5.4, it suffices to compute only the components Wj in the complete
intersection stratification of W of codimension bounded by n. A similar remark
applies to Algorithm 5.2 for the weakly transverse case.
6. Examples
We illustrate with two examples how our algorithms work. We will systematically
use the modifications in Remark 5.12. To shorten the presentation, we will only compute the zeros of these systems in the algebraic torus.
Example 6.1. Let d ≥ 1 and consider the system of polynomials
(6.1) f1 = xd1 x22 − 5xd1 x2 − 2x2 + 10,

d
f2 = xd+1
1 x2 − 2x1 x2 − 2x1 + 4 ∈ Q[x1 , x2 ].

Its zero set in G2m consists of the curve defined by the polynomial xd1 x2 − 2 (which is a
common factor of f1 and f2 ) and the isolated point (2, 5). In the sequel, we describe
how our algorithms give this result.
The support of these polynomials consists of the vectors (d + 1, 1), (d, 2), (d, 1),
(0, 1), (1, 0), (0, 0) ∈ Z2 . Let W ⊂ G5m be the subvariety defined by
F1 = y2 − 5y3 − 2y4 + 10,

F2 = y1 − 2y3 − 2y5 + 4 ∈ Q[y1±1 , . . . , y5±1 ]

and ϕ : G2m → G5m the homomorphism given by
d 2 d
ϕ(x1 , x2 ) = (xd+1
1 x2 , x1 x2 , x1 x2 , x2 , x1 ),

so that V (f1 , f2 ) = ϕ−1 (V (F1 , F2 )).

26

AMOROSO, LEROUX, AND SOMBRA

The subtorus T = V (y2 y3−1 y4−1 − 1) satisfies im(ϕ) ⊂ T . Following Remark 5.12(1),
we apply Algorithm 5.1 at this point, instead of the descent procedure in Algorithm 5.4.
We choose the automorphism τ ∈ Aut(G5m ) given by
τ (y1 , y2 , y3 , y4 , y5 ) = (y1 , y3 , y4 , y5 , y2 y3−1 y4−1 ).
It satisfies τ (T ) = V (y5 − 1). The corresponding output of Algorithm 5.1 for the triple
f ⊂ G4 defined by
(W, T, ϕ) is the subvariety W
m
Fe1 = F1 (y1 , y2 y3 , y2 , y3 , y4 ) = y2 y3 − 5y2 − 2y3 + 10,

Fe2 = F2 (y1 , y2 y3 , y2 , y3 , y4 ) = y1 − 2y2 − 2y4 + 4,

d
and the homomorphism ϕ
e : G2m → G4m given by ϕ(x
e 1 , x2 ) = (xd+1
1 x2 , x1 x2 , x2 , x1 ).
f , ϕ).
Set (W, ϕ) ← (W
e We apply again Algorithm 5.1, this time to the triple (W, T, ϕ)
−1 −1
with T = V (y1 y2 y4 −1). This subtorus satisfies im(ϕ) ⊂ T . We choose τ ∈ Aut(G4m )
given by τ (y1 , y2 , y3 , y4 ) = (y2 , y3 , y4 , y1 y2−1 y4−1 ), which satisfies τ (T ) = V (y4 −1). The
f ⊂ G3 defined by
corresponding output of Algorithm 5.1 is the subvariety W
m

Fe1 = F1 (y1 y3 , y1 , y2 , y3 ) = y1 y2 − 5y1 − 2y2 + 10,
Fe2 = F2 (y1 y3 , y1 , y2 , y3 ) = y1 y3 − 2y1 − 2y3 + 4,

and the homomorphism ϕ
e : G2m → G3m given by ϕ(x
e 1 , x2 ) = (xd1 x2 , x2 , x1 ).
f , ϕ).
Set again (W, ϕ) ← (W
e There is no proper subtorus of G3m of degree independent of d and containing the image of ϕ. Hence, we cannot further apply Remark 5.12(1), at least when d ≫ 0. Instead, we apply the procedure in Algorithm 5.5.
The subvariety W has two irreducible components, of codimension 1 and 2, respectively. Indeed,
W = V (y1 − 2) ∪ V (y2 − 5, y3 − 2).
Following line 3 of Algorithm 5.5, we apply Algorithm 5.4 to this subvariety in order to construct the collections Λk . As in line 1 of this algorithm, we set Σ0 =
{(1G0m , W, idG3m )}, where 1G0m denotes the neutral element of the trivial group G0m . We
now describe what is done in the loop between lines 2 and 12.
Set k = 0. There is only one element in Σ0 , namely (1G0m , W, idG3m ). A complete
intersection stratification of W is given by
W1 = V (y1 − 2)\V (y3 − 2),

W2 = V ((y1 − 2)(y2 − 5), y3 − 2).

It is easy to check that W1 has empty exceptional subset and that the only maximal
atypical subvariety of W2 is given by W2 ∩ T = V (y1 − 2, y3 − 2) for the subtorus
T = V (y1 y3−1 − 1). Hence, we may choose ΩW1 = ∅ and ΩW2 = {T } in line 6 and we
add to Λ0 the triples (1G0m , W1 , idG3m ) and (1G0m , W2 \ T, 1G3m ) in line 7. Let us consider
now the loop between lines 8 and 10. Since ΩW2 consists of the only torsion coset {T },
we apply Algorithm 5.3 to the quadruple (1G0m , W2 , T, idG3m ). We choose τ ∈ Aut(G3m )
given by τ (y1 , y2 , y3 ) = (y1 , y2 , y1−1 y3 ). Thus τ (T ) = V (y3 − 1) as required, and
f × {1},
τ (W2 ∩ T ) = W

f , τ ) as output. We add
f = V (y1 − 2) ⊂ G2 . Hence, Algorithm 5.3 gives (1, W
with W
m
this element to Σ1 in line 9.
f , τ ) and W
f = V (y1 − 2) has no
Set now k = 1. The only element of Σ1 is (1, W
f
atypical locally closed subset. Thus, we choose ΩW
f = ∅ and add (1, W , τ ) to Λ1 in
line 7. The construction of Algorithm 5.4 ends up here.

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

27

We now construct the collection Γ in Algorithm 5.5. Recall that ϕ : G2m → G3m is
the homomorphism given by
ϕ(x1 , x2 ) = (xd1 x2 , x2 , x1 ).
The elements of Λ0 are (1G0m , W1 , idG3m ) and (1G0m , W2 \ T, idG3m ). These triples contribute to Γ with the locally closed subsets
Y1 = V (xd1 x2 − 2)\V (x1 − 2),
Y2 = V ((xd1 x2 − 2)(x2 − 5), x1 − 2)\V (xd−1
1 x2 − 1) = {(2, 5)}.
f , τ ), and it contributes to Γ with the locally closed subset
The only triple in Λ1 is (1, W
1−d
Y3 = V (xd1 x2 − 2, xd−1
)}.
1 x2 − 1) = {(2, 2

By Theorem 5.10, the zero set of the system (6.1) decomposes as Y1 ∪ Y2 ∪ Y3 .
Example 6.2. Let d ≥ 1 and consider the system of polynomials
3d+2 3d
2
x2 + 5x1 + 25,
(6.2) f1 = x3d+1
x3d
2 + x1 x2 + 5, f2 = x1
1

f3 = x1 + x21 x2 + 25x2 ∈ Q[x1 , x2 ].
Its zero set in G2m consists of two points (5ζ, ζ/5) of rank 1, with ζ a primitive third
root of unity. As in the previous example, we will describe how our algorithms give
this result.
The support of f1 and f2 consists of the vectors (0, 0), (3d + 1, 3d), (3d + 2, 3d),
(2, 1), (1, 0), (0, 1) ∈ Z2 . Let W ⊂ G5m be the subvariety defined by
F1 = y1 + y3 + 5,
and ϕ :

G2m

→

G5m

F2 = y2 + 5y4 + 25,

F3 = y4 + y3 + 25y5

the homomorphism given by
3d+2 3d 2
ϕ(x1 , x2 ) = (x3d+1
x3d
x2 , x1 x2 , x1 , x2 ).
2 , x1
1

The subtorus T = V (y1 y2−1 y4 − 1) satisfies im(ϕ) ⊂ T . Following Remark 5.12(1),
we apply Algorithm 5.1 to the triple (W, T, ϕ). We choose τ ∈ Aut(G5m ) given by
τ (y1 , y2 , y3 , y4 , y5 ) = (y2 , y1 y2−1 , y3 , y5 , y1 y2−1 y4 ) as one of the automorphisms that satisfies τ (T ) = V (y5 − 1). The corresponding output of this algorithm is the subvariety
f ⊂ G4 defined by Fei = Fi (y1 y2 , y1 , y3 , y −1 , y4 ), i = 1, 2, 3, that is
W
m
2
Fe1 = y1 y2 + y3 + 5,

Fe2 = y1 + 5y2−1 + 25,

Fe3 = y2−1 + y3 + 25y4 ,

−1 2
e 1 , x2 ) = (x13d+2 x3d
and the homomorphism ϕ
e : G2m → G4m given by ϕ(x
2 , x1 , x1 x2 , x2 ).
f , ϕ).
Set (W, ϕ) ← (W
e We apply again Algorithm 5.1, this time to the triple (W, T, ϕ)
2
with T = V (y2 y3 y4−1 − 1). This subtorus satisfies im(ϕ) ⊂ T . We choose τ ∈ Aut(G4m )
given by τ (y1 , y2 , y3 , y4 ) = (y1 , y2−2 y4 , y2 , y22 y3 y4−1 ), which satisfies τ (T ) = V (y4 − 1).
f ⊂ G3m defined by Fei =
The corresponding output of Algorithm 5.1 is subvariety W
2
Fi (y1 , y3 , y2 , y2 y3 ), i = 1, 2, 3, that is
Fe1 = y1 y3 + y2 + 5, Fe2 = y1 + 5y −1 + 25, Fe3 = y −1 + y2 + 25y2 y 2 ,
3
3d+2 3d 2
(x1 x2 , x1 x2 , x−1
1 ).

3

G2m

3

G3m

and the homomorphism ϕ
e:
→
given by ϕ(x
e 1 , x2 ) =
f
Set again (W, ϕ) ← (W , ϕ).
e We apply for a third time Algorithm 5.1, this time to the
triple (W, T, ϕ) with T = V (y1 y32 − 1). This subtorus satisfies im(ϕ) ⊂ T . We choose
τ ∈ Aut(G3m ) given by τ (y1 , y2 , y3 ) = (y1 , y3 , y1 y32 ), which satisfies τ (T ) = V (y3 − 1).
f ⊂ G2m in the output of Algorithm 5.1 is defined by
The subvariety W
Fe1 = F1 (y −2 , y1 , y2 ) = y −1 + y1 + 5, Fe2 = F2 (y −2 , y1 , y2 ) = y −2 + 5y −1 + 25,
2

2

2

2

2

28

AMOROSO, LEROUX, AND SOMBRA

because the Laurent polynomial Fe3 = F3 (y2−2 , y1 , y2 ) = y2−1 + y1 + 25y1 y22 lies in the
ideal (Fe1 , Fe2 ). The corresponding homomorphism ϕ
e : G2m → G2m is given by ϕ(x
e 1 , x2 ) =
−1 3d 3d
2
(x1 x2 , x1 , x1 x2 ).
f , ϕ).
Again set (W, ϕ) ← (W
e
There exists no proper subtorus of G2m of degree
independent of d such that im(ϕ) ⊂ T . Thus we cannot further apply the Algorithm 5.1
when d ≫ 0. Instead, we apply the general procedure in Algorithm 5.5. As indicated in
Algorithm 5.5, line 3, we apply Algorithm 5.4 to the subvariety W ⊂ G2m to construct
the sets Λk . We describe what is done in the loop in lines 2 to 12 of this algorithm.
Set k = 0 and choose at line 1 the only element of Σ0 , namely (1G0m , W, idG2m ).
The subvariety W consists of the two points (5ζ, ζ/5) with ζ a primitive third root of
unity. In particular, it is 0-dimensional and is already given as a complete intersection.
Moreover, these two points are atypical since
W ∩ Tζ = {(5ζ, ζ/5)}
where Tζ is the torsion coset V (y1 y2 − ζ 2 ) for ζ S∈ µ3 \ {1}. Hence we may choose
ΩW = {Tζ }ζ∈µ3 \{1} in line 6. We have that W ⊂ ΩW and so Λ0 = ∅.
Now fix ζ ∈ µ3 \ {1} and apply Algorithm 5.3 to the quadruple (1G0m , W, Tζ , idG2m ).
We choose τ ∈ Aut(G2m ) given by τ (y1 , y2 ) = (y1 , y1 y2 ). This automorphism satisfies
τ (Tζ ) = V (y2 − ζ 2 ) as required, and
fζ × {ζ 2 }
τ (W ∩ Tζ ) = W

fζ = V (y1 − 5ζ) = {5ζ} ⊂ Gm . The output of Algorithm 5.3 is the triple
with W
fζ , τ ), which we add to Σ1 . Hence, at the end of the loop between lines 8 and 10,
(ζ 2 , W
fζ , τ )}ζ∈µ \{1} .
Σ1 = {(ζ 2 , W
3

fζ has no atypical
Set now k = 1 in the loop between lines 2 and 12. The subvariety W
component because it is 0-dimensional and contains no torsion point. Thus we choose
fζ , τ ) for ζ ∈ µ3 \ {1}. The construction
ΩWζ = ∅ and add to Λ1 the two elements (ζ 2 , W
of Algorithm 5.4 finishes here.
We now construct the collection Γ in Algorithm 5.5. Recall that ϕ : G2m → G2m is
given by
3d 3d
ϕ(x1 , x2 ) = (x21 x2 , x−1
1 , x1 x2 ).
The collection Λ1 contributes to Γ with the locally closed subsets
n
ζ o
for ζ ∈ µ3 \ {1}.
Yζ = V (x21 x2 − 5ζ, x1 x2 − ζ 2 ) \ V (1) =
5ζ,
5
By Theorem 5.10, the zero set of the system (6.2) decomposes as the union of these
two points.
References
[BG06]

E. Bombieri and W. Gubler, Heights in Diophantine geometry, New Math. Monogr., vol. 4,
Cambridge Univ. Press, 2006.

[BMZ99] E. Bombieri, D. Masser, and U. Zannier, Intersecting a curve with algebraic subgroups of
multiplicative groups, Internat. Math. Res. Notices 1999 (1999), 1119–1140.
[BMZ07]

, Anomalous subvarieties — structure theorems and applications, Int. Math. Res.
Notices 2007 (2007), Art. ID rnm057, 33 pp..

[Cha12]

A. Chambert-Loir, Relations de dépendance et intersections exceptionnelles, Séminaire
Bourbaki 2010/11, Astérisque, vol. 348, Soc. Math. France, 2012, pp. 149–188.

SYSTEMS OF SPARSE POLYNOMIAL EQUATIONS

[Coh93]

29

H. Cohen, A course in computational algebraic number theory, Grad. Texts in Math., vol.
138, Springer-Verlag, 1993.

[FGS08] M. Filaseta, A. Granville, and A. Schinzel, Irreducibility and greatest common divisor algorithms for sparse polynomials, Number theory and polynomials, London Math. Soc. Lecture
Notes Ser., vol. 352, Cambridge Univ. Press, 2008, pp. 155–176.
[GG03]

J. von zur Gathen and J. Gerhard, Modern computer algebra. 2nd ed., Cambridge Univ.
Press, 2003.

[Hab09]

P. Habegger, On the bounded height conjecture, Int. Math. Res. Notices 2009 (2009), 860–
886.

[Lau84]

M. Laurent, Équations diophantiennes exponentielles, Invent. Math. 78 (1984), 299–327.

[Ler11]

L. Leroux, Algorithmes pour les polynômes lacunaires, Ph.D. thesis, Université de Caen,
2011, downloadable from http://tel.archives-ouvertes.fr/tel-00580656.

[Ler12]

, Computing the torsion points of a variety defined by lacunary polynomials, Math.
Comp. 81 (2012), 1587–1607.

[Mau08] G. Maurin, Courbes algébriques et équations multiplicatives, Math. Ann. 341 (2008), 789–
824.
[Pla77]

D. A. Plaisted, Sparse complex polynomials and polynomial reducibility, J. Comput. System
Sci. 14 (1977), 210–221.

[Schi65]

A. Schinzel, On the reducibility of polynomials and in particular of trinomials, Acta Arith.
11 (1965), 1–34.

[Schi00]

, Polynomials with special regard to reducibility. With an appendix by Umberto Zannier, Encyclopedia Math. Appl., vol. 77, Cambridge Univ. Press, 2000.

[Schi02]

, On the greatest common divisor of two univariate polynomials. I, A panorama of
number theory or the view from Baker’s garden (Zürich, 1999), Cambridge Univ. Press,
2002, pp. 337–352.

[Schm96] W. M. Schmidt, Heights of points on subvarieties of Gn
m , Number theory (Paris, 1993–1994),
London Math. Soc. Lecture Notes Ser., vol. 235, Cambridge Univ. Press, 1996, pp. 157–187.
[Via08]

E. Viada, The intersection of a curve with a union of translated codimension-two subgroups
in a power of an elliptic curve, Algebra Number Theory 2 (2008), 249–298.

[Zan09]

U. Zannier, Lecture notes on Diophantine analysis. With an appendix by Francesco
Amoroso, Appunti. Sc. Norm. Super. Pisa (N. S.), vol. 8, Edizioni della Normale, 2009.

[Zan12]

, Some problems of unlikely intersections in arithmetic and geometry. With appendixes by David Masser, Ann. of Math. Stud., vol. 181, Princeton Univ. Press, 2012.

[Zil02]

B. Zilber, Exponential sums equations and the Schanuel conjecture, J. London Math. Soc. (2)
65 (2002), 27–44.

Laboratoire de mathématiques Nicolas Oresme, CNRS UMR 6139, Université de
Caen, BP 5186, 14032 Caen Cedex, France
E-mail address: francesco.amoroso@unicaen.fr
URL: http://www.math.unicaen.fr/~amoroso/
Laboratoire de mathématiques Nicolas Oresme, CNRS UMR 6139, Université de
Caen, BP 5186, 14032 Caen Cedex, France
E-mail address: louis.leroux@ac-caen.fr
URL: http://www.math.unicaen.fr/~lleroux/
ICREA & Departament d’Àlgebra i Geometria, Universitat de Barcelona. Gran
Via 585, 08007 Barcelona, Spain
E-mail address: sombra@ub.edu
URL: http://atlas.mat.ub.es/personals/sombra/

