RANDOM SAMPLING IN COMPUTATIONAL ALGEBRA:
HELLY NUMBERS AND VIOLATOR SPACES

arXiv:1503.08804v3 [cs.DM] 23 Dec 2015

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

Abstract. This paper transfers a randomized algorithm, originally used in geometric optimization,
to computational problems in commutative algebra. We show that Clarkson’s sampling algorithm
can be applied to two problems in computational algebra: solving large-scale polynomial systems and
finding small generating sets of graded ideals. The cornerstone of our work is showing that the theory
of violator spaces of Gärtner et al. applies to polynomial ideal problems. To show this, one utilizes
a Helly-type result for algebraic varieties. The resulting algorithms have expected runtime linear in
the number of input polynomials, making the ideas interesting for handling systems with very large
numbers of polynomials, but whose rank in the vector space of polynomials is small (e.g., when the
number of variables and degree is constant).

Keywords: Violator spaces, ideal generators, solving polynomial systems, randomized algorithm
in algebra, large sparse systems.
AMS subject classification: 68W20, 68R05, 12Y05, 13P10, 14Q10, 08A40.
1. Introduction
Many computer algebra systems offer excellent algorithms for manipulation of polynomials. But
despite great success in the field, many algebraic problems have bad worst-case complexity. For
example, Buchberger’s [13, 14, 18] groundbreaking algorithm, key to symbolic computational algebra today, computes a Gröbner basis of any ideal, but it has a worst-case runtime that is doubly
exponential in the number of variables [22]. This presents the following problem: what should one do
about computations whose input is a very large, overdetermined system of polynomials? In this paper,
we propose to use randomized sampling algorithms to ease the computational cost in such cases.
One can argue that much of the success in computation with polynomials (of non-trivial size) often
relies heavily on finding specialized structures. Examples include Faugère’s et al. fast computation
of Gröbner bases of zero-dimensional ideals [25, 26, 27, 29, 35], specialized software for computing
generating sets of toric ideals [1], several packages in [32] built specifically to handle monomial
ideals, and the study of sparse systems of polynomials (i.e., systems with fixed support sets of
monomials) and the associated homotopy methods [45]. A more recent example of the need to find
good structures is in [16], where Cifuentes and Parrilo began exploiting chordal graph structure in
computational commutative algebra, and in particular, for solving polynomial systems. Our paper
exploits combinatorial structure implicit in the input polynomials, but this time akin to Helly-type
results from convex discrete geometry [36].
At the same time, significant improvements in efficiency have been obtained by algorithms that
involve randomization, rather than deterministic ones (e.g. [10, 43]); it is also widely recognized
that there exist hard problems for which pathological examples requiring exponential runtimes occur
only rarely, implying an obvious advantage of considering average behavior analysis of many algorithms. For example, some forms of the simplex method for solving linear programming problems
have worst-case complexity that is exponential, yet [44] has recently shown that in the smoothed
analysis of algorithms sense, the simplex method is a rather robust and fast algorithm. Smoothed
analysis combines the worst-case and average-case algorithmic analyses by measuring the expected
1

2

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

performance of algorithms under slight random perturbations of worst-case inputs. Of course, probabilistic analysis, and smoothed analysis in particular, has been used in computational algebraic
geometry for some time now, see e.g., the elegant work in [8, 9, 15]. The aim of this paper is to
import a randomized sampling framework from geometric optimization to applied computational
algebra, and demonstrate its usefulness on two problems.
Our contributions. We apply the theory of violator spaces [31] to polynomial ideals and adapt
Clarkson’s sampling algorithms [17] to provide efficient randomized algorithms for the following
concrete problems:
(1) solving large (overdetermined) systems of multivariate polynomials equations,
(2) finding small, possibly minimal, generating sets of homogeneous ideals.
Our method is based on using the notion of a violator space. Violator spaces were introduced
in 2008 by Gärtner, Matoušek, Rüst, and Škovroň [31] in a different context. Our approach allows
us to adapt Clarkson’s sampling techniques [17] for computation with polynomials. Clarkson-style
algorithms rely on computing with small-size subsystems, embedded in an iterative biased sampling
scheme. In the end, the local information is used to make a global decision about the entire system.
The expected runtime is linear in the number of input elements, which is the number of polynomials
in our case (see [12] for a more recent simplified version of Clarkson’s algorithm for violator spaces).
Violator spaces naturally appear in problems that have a natural linearization and a sampling size
given by a combinatorial Helly number of the problem. While violator spaces and Clarkson’s algorithm have already a huge range of applications, to our knowledge, this is the first time such sampling
algorithms are being used in computational algebraic geometry. For an intuitive reformulation of
Helly’s theorem for algebraic geometers, see Example 2.1. Main ingredients of violator spaces are
illustrated through Examples 2.2, 3.2 and 3.6. A typical setup where problem (1) can be difficult
and a randomized algorithm appropriate can be found in Example 4.8.
Before stating the main results, let us fix the notation used throughout the paper. We assume the
reader is acquainted with the basics of computational algebraic geometry as in the award-winning
undergraduate textbook [18]. Denote by K a (algebraically closed) field; the reader may keep K = C
in mind as a running example. Let f1 = 0, . . . , fm = 0 be a system of m polynomials in n+1 variables
with coefficients in K. We usually assume that m ≫ n. As is customary in the algebra literature,
we write f1 , . . . , fm ∈ R = K[x0 . . . , xn ] and often denote the polynomial ring R by a shorthand
notation K[x]. We will denote by (f1 , . . . , fm ) ⊂ R the ideal generated by these polynomials; that
is, the set of all polynomial combinations of the fi ’s. Note that if F = {f1 , . . . , fm } is a set of
polynomials, the ideal (f1 , . . . , fm ) will equivalently be denoted by (F ).
A polynomial is said to be homogeneous if all of its terms are of same degree; an ideal generated
by such polynomials is a homogeneous ideal. In this paper, the ideals we consider need not be
homogeneous; if they are, that will be explicitly stated. In that case, the set of all homogeneous
polynomials of total degree d will be denoted by [R]d . Finally, denote by V(S) the (affine) variety
defined by the set of polynomials S ∈ R, that is, the Zariski closure of the set of common zeros of
the polynomials in the system S. Therefore, the concrete problem (1) stated above simply asks for
the explicit description of the variety (solution set) corresponding to an ideal (system of polynomial
equations). The concrete problem (2) asks to find a smaller (e.g., minimal with respect to inclusion)
set of polynomial equations that generate the same ideal - and thus have the exact same solution
set.
Solving large polynomial systems. Suppose we would like to solve a system of m polynomials
in n + 1 variables over the field K, and suppose that m is large. We are interested in the coefficients
of the polynomials as a way to linearize the system. To that end, recall first that the d-th Veronese

HELLY NUMBERS AND VIOLATOR SPACES IN COMPUTATIONAL ALGEBRA
n+d
d

embedding of Pn is the following map νd : Pn → P(

3

)−1 :

d
(x0 : · · · : xn ) 7→ (xd0 : xd−1
0 x1 : · · · : xn ).

The map νd induces a coefficient-gathering map for homogeneous polynomials in fixed degree d:
n+d
coeff d : [R]d → K ( d )


X
α
cα x 7→ cα1 , . . . , cα n+d ,
( d )
α:|α|=d

xαi

where
corresponds
to the i-th coordinate of the d-th Veronese embedding. We follow the usual
P
notation |α| = i αi . Therefore, if f is a homogeneous polynomial of deg(f ) = d, coeff(f ) is a vector
n+d
in the K-vector space K ( d ) . This construction can be extended to non-homogeneous polynomials
in the following natural way. Consider all distinct total degrees d1 , . . . , ds of monomials that appear
in a non-homogenous polynomial f . For each di , compute the image under coeff di of all monomials
of f of degree di . Finally, concatenate all these vectors
into the total coefficient vector of f , which

we will call coeff(f ) and which is of size n+d+1
,
the
number
of monomials in n + 1 variables of
n+1
(total) degree ranging from 0 to d. In this way, a system f1 , . . . , fm of polynomials
in n variables

of degree at most d can be represented by its coefficient matrix of size n+d+1
×
m.
Each column
n+1
of this matrix corresponds to the vector produced by the map coeff d above. This map allows us to
think of polynomials as points in a linear affine space, where Helly’s theorem applies.
We utilize this construction to import Clarkson’s method [17] for solving linear problems to algebraic geometry and, in particular, we make use of Helly-type theorems for varieties. Helly-type
theorems allow one to reduce the problem of solving the system to repeated solution of smaller
subsystems, whose size is a Helly number of intersecting linear spaces. As a result, our algorithms
achieve expected linear runtime in the number of input equations.
Theorem 1.1. Let F = {f1 , . . . , fm } ⊂ R be a system of polynomials, and let δ be the dimension of
the vector subspace generated by the coefficient vectors of the fi ’s, as described above.
Then there exists a sampling algorithm
that outputs F ′ = {fi1 , . . . , fiδ } ⊂ F such that V(F ) = V(F ′ )

in an expected number O δm + δO(δ) of calls to the primitive query that solves a small radical ideal
membership problem. F and F ′ generate the same ideal up to radicals.
It is important to point out that our sampling algorithm will find a small subsystem of the input
system that, when solved with whatever tools one has at their disposal, will give the same solution
set as the original (input) system. Here by ‘small’ we mean a system of size δ, where δ is polynomially
bounded or constant when the number of variables is constant or when the degree d is small.
That the rank δ of the coefficient matrix of the system of polynomials gives the combinatorial
dimension for this problem is shown in Theorem 4.11. There are several interesting special cases of
this result. For example, we obtain [21, Corollary 2] as a corollary: if f1 , . . . , fm ∈ K[x0 , . . . , xn ] are
homogeneous and
 of degree at most d each, then the dimension δ of the vector subspace they generate
(see Lemma 4.6). Of course, in many situations in practice, this bound is not sharp,
is at most n+d
d
as many systems are of low rank. For example, this situation can arise if the monomial support
of the system is much smaller than the total number of monomials of degree d. In light of this,
Theorem 4.11 gives a better bound for low-rank systems. Note that we measure system complexity
by its rank, that is, the vector space dimension δ, and not the usual sparsity considerations such as
the structure of the monomial support of the system. Further, our result applies to non-homogeneous
systems as well. Its proof is presented in Section 4, along with the proof of Theorem 1.1.

4

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

Computing small generating sets of ideals. The problem of finding “nice” generating sets of
ideals has numerous applications in statistics, optimization, and other fields of science and engineering. Current methods of calculating minimal generating sets of ideals with an a priori large number
of generators are inefficient and rely mostly on Gröbner bases computations, since they usually involve ideal membership tests. Of course there are exceptional special cases, such as ideals of points
in projective space [40] or binomial systems [1]. Our second main result shows how to efficiently
extract a small or close to minimal generating set for any ideal from a given large generating set and
a bound on the size of a minimal generating set.
Theorem 1.2. Let I = (H) be an ideal generated by a (large) finite set of homogeneous polynomials
H, and suppose that γ is a known upper bound for the 0-th total Betti number β(R/I).
Then there exists a randomized algorithm that computes a generating set of I of size γ in expected
number of O(γ|H| + γ γ ) calls to the primitive query that solves a small ideal membership problem.
In particular, if γ = β(R/I), the algorithm computes a minimal generating set of I.
The proof is presented in Section 5.
2. A Warm-Up: Algebraic Helly-type theorems and the size of a meaningful sample
A Helly-type theorem has the following form: Given a family of objects F , a property P , and
a Helly number δ such that every subfamily of F with δ elements has property P , then the entire
family has property P. (See [19, 23, 47, 4].) In the original theorem of E. Helly, F is a finite family
of convex sets in Rn , the constant δ is n + 1, and the property P is to have a non-empty intersection
[34]. Here we are looking for non-linear algebraic versions of the same concept, where the objects in
F are algebraic varieties (hypersurfaces) or polynomials; the property desired is to have a common
point, or to generate the same ideal; and the Helly constant δ will be determined from the structure
of the problem at hand. To better understand the algorithms that we present, it is instructive to
consider two intuitive easy examples that highlight the fundamental combinatorial framework. The
first one is an obvious reformulation of Helly’s theorem for algebraic geometers.
Example 2.1. Let H = {L1 , L2 , . . . , Ls } be a family of affine linear subspaces in Rn . Consider the
case when s is much larger than n. One would like to answer the following question: when do all of
the linear varieties have a nonempty intersection? It is enough to check whether each subfamily of
H with n + 1 elements has a non-empty intersection, as that would imply, by Helly’s Theorem, that
H also has a non-empty intersection. Thus, in practice, one can reduce the task of deciding whether
∩si=1 Li 6= ∅ to the collection of smaller queries ∩n+1
j=1 Lij . However, instead of testing all possible
s 
n+1 many (n + 1)-tuples, we may choose to randomly sample multiple (n + 1)-tuples. Each time
we sample, we either verify that one more (n + 1)-tuple has a non-empty intersection thus increasing
the certainty that the property holds for all (n + 1)-tuples, or else find a counterexample, a subfamily
without a common point, the existence of which trivially implies that ∩si=1 Li = ∅. This simple idea
is the foundation of a randomized approach. For now we ask the reader to observe that n + 1 is the
dimension of the vector space of (non-homogeneous) linear polynomials in n variables.
Example 2.2. The next example is just slightly more complicated, but illustrates well some key
concepts. Consider next H = {f1 (x1 , x2 ), f2 (x1 , x2 ), . . . , fs (x1 , x2 )}, a large family of affine real plane
curves of degree at most d. Imagine that H is huge, with millions of constraints fi , but the curves
are of small degree, say d = 2. Nevertheless, suppose that we are in charge of deciding whether the
curves in H have a common real point. Clearly, if the pair of polynomials f, g ∈ H intersect, they
do so in finitely many points, and, in particular, Bezout’s theorem guarantees that no more than d2
intersections occur. One can observe that if the system H has a solution, it must pass through some
of the (at most d2 ) points defined by the pair f, g alone. In fact, if we take triples f, g, h ∈ H, the
same bound of d2 holds, as well as the fact that the solutions for the entire H must also be part of

HELLY NUMBERS AND VIOLATOR SPACES IN COMPUTATIONAL ALGEBRA

5

the solutions for the triplet f, g, h. Same conclusions hold for quadruples, quintuples, and in general
δ-tuples. But how large does an integer δ have to be in order to function as a Helly number? We
seek a number δ such that if all δ-tuples of plane curves in H intersect, then all of the curves in H
must intersect. The reader can easily find examples where δ = d does not work, e.g., for d ≥ 2.
To answer the question posed in Example 2.2, we refer to Theorem 4.11 in Section 4. Without
re-stating the theorem here, we state the following Corollary and note that it gives a nice bound on
δ. Corollary 2.3 is implied by the observation that there are only d+2
monomials in two variables
2
of degree ≤ d (which says they span a linear subspace of that dimension inside the vector space of
all polynomials) and Theorem 4.11.
Corollary 2.3. Let H = {f1 (x, y), f2 (x, y), . . . , fs (x, y)} be a family of affine real plane curves of
degree at most d. If every δ = d+2
of the curves have a real intersection point, then all the curves
2
in H have a real intersection point. If we consider the same problem over the complex numbers, then
the same bound holds.
Thus, it suffices to check all δ-tuples of curves for a common real point of intersection, and if all of
those instances do intersect, then we are sure all |H| polynomials must have a common intersection
point, too. The result suggests a brute-force process to verify real feasibility of the system, which
of course is not a pretty proposition, given that |H| is assumed to be very large. Instead, Section 3
explains how to sample the set of δ-tuples in order to obtain a solution to the problem more efficiently.
Notice that it is important to find a small Helly number δ, as a way to find the smallest sampling
size necessary to detect common intersections. It turns out that in this example and in the case
when all fi are homogeneous, the Helly number is best possible [28].
3. Violator spaces and Clarkson’s sampling algorithms
The key observation in the previous section was that the existence of Helly-type theorems indicates
that there is a natural notion of sampling size to test for a property of varieties. Our goal is to import
to computational algebra an efficient randomized sampling algorithm by Clarkson. To import this
algorithm, we use the notion of violator spaces which we outline in the remainder of this section. We
illustrate the definitions using Example 2.2 as a running example in this section.
In 1992, Sharir and Welzl [41] identified special kinds of geometric optimization problems that
lend themselves to solution via repeated sampling of smaller subproblems: they called these LP-type
problems. Over the years, many other problems were identified as LP-type problems and several
abstractions and methods were proposed [2, 3, 11, 33, 37]. A powerful sampling scheme, devised by
Clarkson [17] for linear programming, works particularly well for geometric optimization problems in
small number of variables. Examples of applications include convex and linear programming, integer
linear programming, the problem of computing the minimum-volume ball or ellipsoid enclosing a
given point set in Rn , and the problem of finding the distance of two convex polytopes in Rn . In
2008, Gärtner, Matoušek, Rüst and Škovroň [31] invented violator spaces and showed they give a
much more general framework to work with LP-type problems. In fact, violator spaces include all
prior abstractions and were proven in [42] to be the most general framework in which Clarkson’s
sampling converges to a solution. Let us begin with the key definition of a violator space.
Definition 3.1 ([31]). A violator space is a pair (H, V), where H is a finite set and V a mapping
2H → 2H , such that the following two axioms hold:
Consistency: G ∩ V(G) = ∅ holds for all G ⊆ H, and
Locality:
V(G) = V(F ) holds for all F ⊆ G ⊆ H such that G ∩ V(F ) = ∅.
Example 3.2 (Example 2.2, continued). To illustrate our definition, we consider Example 2.2 of s
real plane curves {f1 , . . . , fs } = H.

6

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

A violator operator for testing the existence of a real point of intersection of a subset F ⊂ H of the
curves should capture the real intersection property. One possible way to define it is the following
map Vreal : 2H → 2H :
Vreal (F ) = {h ∈ H : V R (F ) ) V R (F ∪ {h})} ,
where V R (F ) is the set of common real intersection points of F , in other words, the real algebraic
variety of F . Note that, by definition, Vreal (F ) = ∅ if the curves in F have no real points of intersection. Before explaining why Vreal captures the real intersection property correctly (see Example 3.6),
let us show that the set (H, Vreal ) is a violator space according to Definition 3.1.
Consistency holds by definition of Vreal : for any h ∈ F , V R (F ) = V R (F ∪{h}), and so h 6∈ Vreal (F ).
To show locality, we begin by showing the auxiliary fact that V R (F ) = V R (G). The inclusion
V R (G) ⊆ V R (F ) is direct. This is because for any S ′ ⊆ S it is always the case that V R (S ′ ) ⊇ V R (S).
We need only show V R (F ) ⊆ V R (G). Recall F ⊆ G ⊆ H and G ∩ Vreal (F ) = ∅. Consider g ∈ G.
By the assumption, g does not violate F , and the proper containment V R (F ) ) V R (F ∪ {g}) does
not hold. Therefore the equality V R (F ) = V R (F ∪ {g}) must hold. By iteratively adding elements
of G r F to F and repeating the argument, we conclude that indeed V R (F ) = V R (G).
Finally, we argue that V R (F ) = V R (G) implies Vreal (F ) = Vreal (G). We first show Vreal (F ) ⊂
Vreal (G). Take h ∈ Vreal (F ). Then V R (G) = V R (F ) ) V R (F ∪ {h}) = V R (F ) ∩ V R ({h}) =
V R (G)∩V R ({h}) = V R (G∪{h}). The last and third-to-last equalities follow from the fact that for any
two sets S1 , S2 , one always has V R (S1 ∪S2 ) = V R (S1 )∩V R (S2 ). The containment Vreal (F ) ⊃ Vreal (G)
follows in a similar argument. Thus (H, Vreal ) is a violator space.
Every violator space comes equipped with three important components: a notion of basis, its
combinatorial dimension, and a primitive test procedure. We begin with the definition of a basis of
a violator space, analogous to the definition of a basis of a linear programming problem: a minimal
set of constraints that defines a solution space.
Definition 3.3 ([31, Definition 7]). Consider a violator space (H, V ). B ⊆ H is a basis if B ∩V(F ) 6=
∅ holds for all proper subsets F ⊂ B. For G ⊆ H, a basis of G is a minimal subset B of G with
V(B) = V(G).
It is very important to note that a violator operator can capture algebraic problems of interest
as long as the basis for that violator space corresponds to a basis of the algebraic object we study.
Violator space bases come with a natural combinatorial invariant, related to Helly numbers we
discussed earlier.
Definition 3.4 ([31, Definition 19]). The size of a largest basis of a violator space (H, V ) is called
the combinatorial dimension of the violator space and denoted by δ = δ(H, V ).
A crucial property was proved in [31]: knowing the violations V(G) for all G ⊆ H is enough to
compute the largest bases. To do so, one can utilize Clarkson’s randomized algorithm to compute
a basis of a violator space (H, V) with m = |H|. The results about the runtime and the size of the
sets involved are summarized below. The primitive operation, used as black box in all stages of the
algorithm, is the violation test primitive.
Definition 3.5. Given a violator space (H, V), some set G ( H, and some element h ∈ H \ G, the
primitive test decides whether h ∈ V(G).
The running example illustrates these three key ingredients.
Example 3.6 (Example 3.2, continued). In the example of s real plane curves, the violator operator
we defined detects whether the polynomials have a real point of intersection. Note that a basis would
be a (minimal) set of curves B = {fi1 , . . . , fiδ }, for some δ < s, such that either the curves in B
have no real point of intersection, or the real points of intersection of the curves in B are the real

HELLY NUMBERS AND VIOLATOR SPACES IN COMPUTATIONAL ALGEBRA

7

intersection of all of H = {f1 , . . . , fs }. If the set F has no real intersection point, then Vreal (F ) = ∅ by
definition, so that set F could be a basis in the sense that it is a certificate of infeasibility for this realintersection problem. If, on the other hand, F does have a real intersection point, and Vreal (F ) = ∅,
then this means that F is a basis in the sense that the curves in F capture the intersections of all of

H. The combinatorial dimension for general H is provided by Corollary 2.3, and it equals δ = d+2
2 .
However, special structure of the curves in H may imply a smaller combinatorial dimension.
The primitive query simply checks, given fi ∈ H and a candidate subset G ⊆ H, whether the
set of real points of intersection of G ∪ {fi } is smaller than the set of real points of intersection of
the curves in G alone. The role of the primitive query is therefore not to find a basis directly, but
to check, instead, whether a given candidate subset G can be a basis of H. This can be done by
checking whether fi ∈ Vreal (G) for all fi ∈ H \ G. Clearly, given the primitive test, a basis for H can
be found by simply testing all sets of size at most δ, but that would be a waste because the number
of times one would need to call the primitive would be O(|H|δ+1 ).
As we will see, this brute-force approach can be avoided. Namely, in our current
 example, the
d+2
randomized algorithm from Theorem 3.7 below will only sample subsets of δ = 2 curves from the
set {f1 , . . . , fs }, and find a basis of the violator space of size δ in the sense explained above.
The sampling method in [17] avoids a full brute-force approach. It is presented in two stages,
referred to as Clarkson’s first and second algorithm. We outline these below.
Clarkson’s first algorithm, in the first iteration, draws a small random sample R ⊂ G, calls the
second stage to calculate the basis C of R, and returns C if it is already a basis for the larger subset
G. If C is not already a basis, but the elements of G \ C violating R are few, it adds those elements
to a growing set of violators W , and repeats the process with C being calculated as the basis of the
set W ∪ R for a new randomly chosen small R ⊂ G \ W . The crucial point here is that |R| is much
smaller than |G| and, consequently, it acts as a Helly number of sorts.
Clarkson’s second algorithm (Basis2) iteratively picks a random small (6δ2 elements) subset R of
G, finds a basis C for R by exhaustively testing each possible subset (BruteForce;) taking advantage
of the fact that the sample R is very small, and then calculates the violators of G \ C. At each
iteration, elements that appear in bases with small violator sets get a higher probability of being
selected.
This idea is very important: we are biasing the sampling process, so that some constraints will
be more likely to be chosen. This is accomplished by considering every element h of the set G as
having a multiplicity m(h); the multiplicity of a set is the sum of the multiplicities of its elements.
The process is repeated until a basis of G is found, i.e. until V(G \ C) is empty.
Again, as described above, all one needs is to be able to answer the Primitive query: Given
G ⊂ H and h ∈ H \ G, decide whether h ∈ V (G). The runtime is given in terms of the combinatorial
dimension δ(H, V ) and the size of H. The key result we will use in the rest of the paper concerns
the complexity of finding a basis:
Theorem 3.7. [31, Theorem 27] Using Clarkson’s algorithms, a basis of H of a violator space (H, V)
can be found by answering the primitive query an expected O δ |H| + δO(δ) times.

It is very important to note that, in both stages of Clarkson’s method, the query h ∈ V(C)
is answered via calls to the primitive as a black box. In our algebraic applications, the primitive
computation requires solving a small-size subsystem (e.g., via Gröbner bases or numerical algebraic
geometry methods), or an ideal membership query applied to the ideal generated by a small subset
of the given polynomials. On the other hand, the combinatorial dimension relates to the Helly
number of the problem which is usually a number that is problem-dependent and requires non-trivial
mathematical results.

8

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

Algorithm 1: Clarkson’s first algorithm
input : G ⊆ H, δ: combinatorial complexity of H
output: B, a basis for G
1
2
3
4
5
6
7
8
9
10
11
12
13
14

if |G| ≤ 9δ2 then
return Basis2(G)
else
W ←∅
repeat
p
R ← random subset of G \ W with ⌊δ |G|⌋ elements.
C ← Basis2(W ∪ R)
V ← {h ∈ G \ C s.t. h ∈ V(C)}
p
if |V | ≤ 2 |G| then
W ←W ∪V
end
until V = ∅
end
return C.

Algorithm 2: Clarkson’s second algorithm: Basis2(G)
input : G ⊆ H; δ: combinatorial complexity of H.
output: B: a basis of G
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

if |G| ≤ 6δ2 then
return BruteForce(G)
else
repeat
R ← random subset of G with 6δ2 elements.
C ← BruteForce(R)
V ← {h ∈ G \ C s.t. h ∈ V(C)}
if m(V ) ≤ m(G)/3δ then
for h ∈ V do
m(h) ← 2m(h)
end
end
until V = ∅
end
return C.

In the two sections that follow we show how violator spaces naturally arise in non-linear algebra
of polynomials.
4. A violator space for solving overdetermined systems
We discuss our random sampling approach to solve large-size (non-linear) polynomial systems by
applying Clarkson’s algorithm. In particular, we prove Theorem 1.1 as a corollary of Theorem 4.11.
This result is motivated by, and extends, Helly-type theorems for varieties from [21] and [28], which

HELLY NUMBERS AND VIOLATOR SPACES IN COMPUTATIONAL ALGEBRA

9

we use to show that the above algorithms apply to large dense homogeneous systems as well (Corollary 4.7).
First, we define a violator space that captures (in the sense explained in the previous section)
solvability of a polynomial system.
Definition 4.1. [Violator Space for solvability of polynomial systems] Let S ⊂ H be finite subsets
of polynomials in R. Define the violator operator Vsolve : 2H → 2H to record the set of polynomials
in H which do not vanish on the variety V(S). Formally,
Vsolve (S) = {f ∈ H : V(S) is not contained in V(f )}.

Lemma 4.2. The pair (H, Vsolve ) is a violator space.
Proof. Note that Vsolve (S) ∩ S = ∅ by definition of Vsolve (S), and thus the operator satisfies the
consistency axiom.
To show locality, suppose that F ( G ⊂ H and G ∩ Vsolve (F ) = ∅. Since F ( G we know that
V(G) ⊆ V(F ). On the other hand, T
by definition, G ∩ Vsolve (F ) = ∅ implies that V(F ) ⊆ V(g) for all
g ∈ G. Thus V(F ) is contained in g∈G V(g) = V(G). But then the two varieties are equal.
To complete the argument we show that V(F ) = V(G) implies Vsolve (F ) = Vsolve (G). If h ∈
Vsolve (F ) then V(h) cannot contain V(F ) = V(G), thus h ∈ Vsolve (G) too. The argument is symmetric, hence Vsolve (F ) = Vsolve (G).

It follows from the definition that the operator Vsolve gives rise to a violator space for which a
basis B of G ⊂ H is a set of polynomials such that V(B) = V(G). Therefore, a basis B ⊂ G will
either be a subset of polynomials that has no solution and as such be a certificate of infeasibility of
the whole system G, or it will provide a set of polynomials that are sufficient to find all common
solutions of G, i.e., the variety V(G).

Next, we need a violation primitive test that decides whether h ∈ Vsolve (F ), as in Definition 3.5.
By the definition above, this is equivalent to asking whether h vanishes on all irreducible components
of the algebraic variety V(F ). As is well known, the points of V(F ) where the polynomial h does
not vanish correspond to the variety associated with the saturation ideal ((F ) : h∞ ). Thus, we may
use ideal saturations for the violation primitive. For completeness, we recall the following standard
definitions. The saturation of the ideal (F ) with respect to f , denoted by ((F ) : f ∞ ), is defined to
be the ideal of polynomials g ∈ R with f m g ∈ I for some m > 0. This operation removes from
the variety V(F ) the irreducible components on which the polynomial f vanishes. Recall that every
variety can be decomposed into irreducible components (cf. [18, Section 4.6] for example). The
corresponding algebraic operation is the primary decomposition of the ideal defining this variety.
Lemma 4.3 (e.g. [5, Chapter 4]). Let ∩m
i=1 Qi be a minimal primary decomposition for the ideal I.
The saturation ideal (I : f ∞ ) equals ∩f ∈/ √Qi Qi .
m
∞
m
∞
∞
Proof. It is known that
√ (∩i=1 Qi : f )∞= ∩i=1 (Qi : f ). We observe further that (Qi : f ) = Qi if

f does not belong to Qi and (Qi : f ) = (1) otherwise.

This allows us to set up the primitive query for (H, Vsolve ). However we do not need to calculate
the decomposition explicitly, but can instead carry it out using elimination ideals via Gröbner bases,
as explained for example in [18, Exercise 4.4.9].
Observation 4.4. The primitive query for (H, Vsolve ) is simply the saturation test explained above.
Remark 4.5. There is an obvious reformulation of these two ingredients that is worth stating
explicitly. Namely, since a basis B for the violator space (H,p
Vsolve ) ispa set of polynomials such
that V(B) = V(H), the strong Nullstellensatz implies that (B) = (H). Thus a basis determines the ideal of the input system up to radicals, and we could have named the violator operator

10

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

Vsolve ≡ Vradical instead. Furthermore, a polynomial
p h vanishing on all irreducible components of
the algebraic variety V(F ) is equivalent to h ∈ (F ), i.e., h belonging to the radical of the ideal
(F ). In particular, the primitive query for Vsolve can also be stated as the radical ideal membership
test. This test
p can be implemented using Gröbner bases, as explained for example in [18, Proposition
4.2.8]: h ∈ (F ) if and only if 1 ∈ (F, 1 − yh) ⊆ K[x0 , . . . , xn , y]. Therefore, computation of one
Gröbner basis of the ideal (F, 1 − yh) suffices to carry out this test.
Finally, we solve the problem of finding a combinatorial dimension for Vsolve . For this, consider,
as a warm up, the simpler situation where we have a Helly-type theorem for hypersurfaces defined
by homogeneous polynomials. This was proved by Motzkin [39] and then later reproved by Deza
and Frankl [21], and it provides us with a combinatorial dimension for guaranteeing that a largescale homogeneous system has a solution. Its proof relies on thinking of the polynomial ring R as a
K-vector space (see also the discussion before Definition 4.9).
Lemma 4.6 ([21], Corollary 2). Let f1 , . . . , fm ⊂ R be a system of homogeneous polynomials,
that is, fi ∈ [R]di , and define d = max{di }. Suppose that every subset of p = n+d
polynomials
d
{fi1 , . . . , fip } ⊂ {f1 , . . . , fm } has a solution. Then the entire system {f1 , . . . , fm } does as well.
Lemma 4.6 provides the combinatorial dimension that, along with the variety membership primitive from Observation 4.4, allows us to apply Clarkson’s algorithms to the violator space (H, Vsolve ).
Corollary 4.7. Let (f1 , . . . , fm ) ⊂ R be an ideal generated by m homogeneous polynomials in n + 1
variables of degree at most d; fi ∈ [R]di and d = max{di }. Let δ = n+d
d . Then there is an
adaptation of Clarkson’s sampling algorithm that, in an expected O δm + δO(δ) number of calls to
the primitive query 4.4, computes {fi1 , . . . , fiδ } such that V(f1 , . . . , fm ) = V(fi1 , . . . , fiδ ).
In particular, this algorithm is linear in the number of input equations m, and a randomized
polynomial time algorithm when the number of variables n + 1 and the largest degree d are fixed.
Furthermore, we can extend it to actually solve a large system: once a basis B = {fi1 , . . . , fiδ } for the
space ({f1 , . . . , fm }, Vsolve ) is found, then we can use any computer algebra software (e.g. [6, 32, 46])
to solve fi1 = · · · = fiδ = 0.
Note that Lemma 4.6 can be thought of as a statement about the complexity of Hilbert’s Null-
stellensatz. If (f1 , . . . , fm ) = R (i.e., V(f1 , . . . , fm ) = ∅), then there exists a subset of size δ = n+d
d
polynomials {fi1 , . . . , fiδ } such that V(fi1 , . . . , fiδ ) = ∅ as well. In particular, there is a Nullstel
is, in fact, only an upper bound,
lensatz certificate with that many elements. The dimension n+d
d
attainable only by dense systems. However, in practice, many systems are very large but sparse, and
possibly non-homogeneous. Let us highlight again that the notion of ‘sparsity’ we consider is captured by a low-rank property of the system of polynomial equations, made explicit below in terms of
the coefficient matrix. This is crucially different from the usual considerations of monomial supports
(Newton polytopes) of the system; instead, we look at the coefficients of the input polynomials - that
is, we linearize the problem and consider the related vector spaces, as illustrated in the following
example.
Example 4.8. Consider the following system consisting of two types of polynomials: polynomials of
the form x2i − 1 for i = 1, . . . , n, and polynomials of the form xi + xj for the pairs {i, j : i 6≡ j mod 2}
along with the additional pair i = 1, j = 3. This system has m = n2 + n + 1 equations, and the
interesting situation is when the number of variables is a large even number, that is, n = 2k for any
large integer k. This system of polynomials generates the 2-coloring ideal of a particular n-vertex
non-chordal graph. (See [20] and references therein for our motivation to consider this particular
system.)

HELLY NUMBERS AND VIOLATOR SPACES IN COMPUTATIONAL ALGEBRA

11

Consider a concrete graph. Take the n-cycle with all possible even chords, and one extra edge
{1, 3}. Thus the pairs {i, j} are indexed by edges of the graph G on n nodes where all odd-numbered
vertices are connected to all even-numbered vertices, and with one additional edge {1, 3}.
We wish to decide if the system has a solution, but since there are n2 + n + 1 many polynomials,
we would like to try to avoid computing a Gröbner basis of this ideal. Instead, we search for a
subsystem of some specific size that determines the same variety. It turns out that the system
actually has no solution. Indeed, a certificate for infeasibility is a random subsystem consisting of
the first n quadratic equations, n − 1 of the edge equations xi + xj with {i, j : i 6≡ j mod 2}, and
the additional equation x1 + x3 . For example, the first n − 1 edge polynomials will do to construct
a 2n-sized certificate of this form. Why is the number n + (n − 1) + 1 = 2n so special?
To answer this question, let us linearize the problem: to each of the polynomials f associate
a coefficient (column) vector coeff(f ) ∈ C2n+1 whose coordinates are indexed by the monomials
appearing in the system x21 , . . . , x2n , 1, x1 , . . . , xn . Putting all these column vectors in one matrix
produces the coefficient matrix of the system of the form


In
0
 − 1 0,
0
E
where In is the n × n identity, −1 is the row vector with all entries −1, and E is the vertex-edge
incidence matrix of the graph G. Since it is known that the rank of an edge-incidence matrix of an
n-vertex connected graph is n − 1, the rank of this matrix is δ = n + (n − 1) + 1 = 2n.
Remarkably, the magic size of the infeasibility certificate equals the rank of this coefficient matrix.

This motivating example suggests that the desired Helly-type number of this problem is captured
by a natural low-rank property of the system. To define it precisely, let us revisit the extension of
the Veronese embedding to non-homogeneous polynomials explained in the Introduction. Here we
adopt the notation from [7, Section 2] and consider polynomials in R of
 degree up to d as a K-vector
d+n+1
n+1
n+1
has dimension n+1 , which, of course, equals the
space denoted by Cd . The vector space Cd
number of monomials in n + 1 variables of (total) degree from 0 to d. In this way, any polynomial
f ∈ R is represented by a (column) vector, coeff(f ) ∈ Cdn+1 , whose entries are the coefficients of f .
Thus, any system S ⊂ R defines a matrix with |S| columns, each of which is an element of Cdn+1 .
Definition 4.9. A system S ⊂ R is said to have rank D if dimK hSi = D, where hSi is the vector
subspace of Cdn+1 generated by the coefficients of the polynomials in S.
We need to also make the notion of Helly-type theorems more precise in the setting of varieties.
Definition 4.10 (Adapted from Definition 1.1. in [28]). A set S ⊂ R is said to have the D-Helly property if for every nonempty subset S0 ⊂ S, one can find p1 , . . . , pD ∈ S0 with V(S0 ) = V(p1 , . . . , pD ).
The following result, which implies Theorem 1.1, is an extension of [28] to non-homogeneous
systems. It also implies (the contrapositive of) Lemma 4.6 when restricted to homogeneous systems,
in the case when the system has no solution. The proof follows that of [28], although we remove the
homogeneity assumption. We include it here for completeness.
Theorem 4.11. Any polynomial system S ⊂ R of rank D has the D-Helly property.
In other words, for all subsets P ⊂ S, there exist p1 , . . . , pD ∈ P such that V(P) = V(p1 , . . . , pD ).

Proof. Let P ⊂ S be an arbitrary subset of polynomials, and denote by hPi ⊂ Cdn+1 the vector
subspace it generates. Let d0 = dimK hPi. We need to find polynomials p1 , . . . , pD such that
V(p1 , . . . , pD ) = V(P). Note that d0 ≤ D, of course, so it is sufficient to consider the case P = S.
Choose a vector space basis hp1 , . . . , pD i = hPi = hSi. It suffices to show V(p1 , . . . , pD ) ⊆ V(S);
indeed, the inclusions V(S) ⊆ V(P) ⊆ V(p1 , . . . , pD ) already hold.

12

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

Suppose, on the contrary, there exists x = (x0 , . . . , xn ) ∈ Cn+1 and p ∈ S such that p(x) 6= 0 but
pi (x) = 0 P
for all i = 1, . . . , D. Since pi ’s generate S as a vector space, there exist constants γi ∈ K
with p = i γi pi , implying that p(x) = 0, a contradiction.


The proof above is constructive: to find a subset p1 , . . . , pD ∈ S0 , one only needs to compute a
vector space basis for hS0 i. Thus, linear algebra (i.e., Gaussian elimination) can construct this subset
in time O(|S0 |3 ). The sampling algorithm based on violator spaces is more efficient.
Proof of Theorem 1.1. From Lemma 4.2, we know that ({f1 , . . . , fm }, Vsolve ) is a violator space.
Theorem 4.11 shows that it has a combinatorial dimension, and Observation 4.4 shows that there
exists a way to answer the primitive test. Having these ingredients, Theorem 3.7 holds and it is
possible for us to apply Clarkson’s Algorithm again.

Remark 4.5 provides the following interpretation of Theorem 4.11:
Corollary 4.12. Let I = (f1 , . . . , fm ) ⊂ R and let D = dimK hf1√
, . . . , fm
pi. Then, for all subsets P
of the generators f1 , . . . , fm , there exist p1 , . . . , pD ∈ P such that P = (p1 , . . . , pD ).
5. A violator space for finding generating sets of small cardinality

In this section, we apply the violator space approach to obtain a version of Clarkson’s algorithm
for calculating small generating sets of general homogeneous ideals as defined on page 3. As in
Section 4, this task rests upon three ingredients: the appropriate violator operator, understanding
the combinatorial dimension for this problem, and a suitable primitive query which we will use as a
black box. As before, fixing the definition of the violator operator induces the meaning of the word
‘basis’, as well as the construction of the black-box primitive.
To determine the natural violator space for the ideal generation problem, let I ⊂ R be a homogeneous ideal, H some initial generating set of I, and define the operator VSmallGen as follows.
Definition 5.1. [Violator Space for Homogeneous Ideal Generators] Let S ⊂ H be finite subsets of
R. We define the operator VSmallGen : 2H → 2H to record the set of polynomials in H that are not
in the ideal generated by the polynomials in S. Formally,
VSmallGen (S) = {f ∈ H : (S, f ) ) (S)}.
Equivalently, the operator can be viewed as VSmallGen (S) = {f ∈ H : f 6∈ (S)}.
Lemma 5.2. The pair (H, VSmallGen ) is a violator space.
Proof. Note that VSmallGen (S) ∩ S = ∅ by definition of VSmallGen (S), and thus the operator satisfies
the consistency axiom.
To show locality, suppose that F ( G ⊂ H and G ∩ VSmallGen (F ) = ∅. Since F ( G, (F ) ⊆ (G).
On the other hand G ∩ VSmallGen (F ) = ∅ implies that G ⊆ (F ) which in turn implies that (G) ⊆ (F ).
Then the ideals are equal. Then, because (G) = (F ) we can prove that VSmallGen (F ) = VSmallGen (G).
Note first that (G) = (F ), holds if and only if (G, h) = (F, h) for all polynomials h ∈ H.
Finally, to show VSmallGen (F ) = VSmallGen (G), we note that h ∈ VSmallGen (F ) if and only if
(G, h) = (F, h) ) (F ) = (G), and this chain of equations and containment holds if and only if
h ∈ VSmallGen (G). Therefore, locality holds as well and VSmallGen is a violator space operator.

It is clear from the definition that (H, VSmallGen ) is a violator space for which the basis of G ⊂ H
is a minimal generating set of the ideal (G).
The next ingredient in this problem is the combinatorial dimension: the size of the largest minimal
generating set. This natural combinatorial dimension already exists in commutative algebra, namely,
it equals a certain Betti number. (Recall that Betti numbers are the ranks βi,j of modules in the
minimal (graded) free resolution of the ring R/I; see, for example, [24, Section 1B (pages 5-9)].)

HELLY NUMBERS AND VIOLATOR SPACES IN COMPUTATIONAL ALGEBRA

13

Specifically, the number β0,j is defined as the number of elements of degree j required among any set
of minimal generators
of I. The (0-th) total Betti number of R/I, which we will denote by β(R/I),
P
simply equals j β0,j , and is then the total number of minimal generators of the ideal I. It is well
known that while I has many generating sets, every minimal generating set has the same cardinality,
namely β(R/I). In conclusion, it is known that
Observation 5.3. The combinatorial dimension for (H, VSmallGen ) is the (0-th) total Betti number
of the ideal I = (H); in symbols, β(R/I) = δ(H, VSmallGen ).
Although it may be difficult to exactly compute β(R/I) in general, a natural upper bound for
β(R/I) is the Betti number for any of its initial ideals (the standard inequality holds by uppersemicontinuity; see e.g. [38, Theorem 8.29]). In particular, if H is known to contain a Gröbner
basis with respect to some monomial order, then the combinatorial dimension can be estimated by
computing the minimal generators of an initial ideal of (H), which is a monomial ideal problem and
therefore easy. In general, however, we only need β(R/I) < |H| for the proposed algorithms to be
efficient.
The last necessary ingredient is the primitive query for VSmallGen .
Observation 5.4. The primitive query for VSmallGen , deciding if h ∈ VSmallGen (G) given h ∈ H
and G ⊂ H, is an ideal membership test.
Of course, the answer to the query is usually Gröbner-based, but, as before, the size of the
subsystems G on which we call the primitive query is small: (O(δ2 )). In fact, it is easy to see that
many small Gröbner computations for ideal membership cost less than the state-of-the-art, which
includes at least one large Gröbner computation.
Proof of Theorem 1.2. From Lemma 5.2 we know (H, VSmallGen ) is a violator space and we have
shown it has a combinatorial dimension and a way to answer the primitive test. Having these
ingredients, Theorem 3.7 holds and it is possible for us to apply Clarkson’s Algorithm.

Remark 5.5. Intuitively, the standard algorithm for finding minimal generators needs to at least
compute a Gröbner basis for an ideal generated by |H| polynomials, and in fact it is much worse
than that. One can simplify this by skipping the computation of useless S-pairs (e.g. as in [30]), but
improvement is not by an order of magnitude, overall. The algorithm remains doubly exponential in
the size of H for general input. In contrast, our randomized algorithm distributes the computation
into many small Gröbner basis calculations, where “many” means no more than O(β|H| + β β ), and
“small” means the ideal is generated by only O(β 2 ) polynomials.
To conclude, in a forthcoming paper we will study further the structure of our violator spaces
and discuss the use of more LP-type methods for the same algorithmic problems. We also intend to
present some experimental results for the sampling techniques we discussed here. We expect better
performance of the randomized methods versus the traditional deterministic algorithms.
Acknowledgements
We are grateful to Nina Amenta, Robert Ellis, Diane Maclagan, Pablo Soberón, Cynthia Vinzant,
and three anonymous referees for many useful comments and references. The first author is grateful
to IMA, the Institute of Mathematics and its Applications of the Univ. of Minnesota for the support
received when this paper was being written. He was also supported by a UC MEXUS grant. This
work was supported by the NSF grant DMS-1522662.

14

JESÚS A. DE LOERA, SONJA PETROVIĆ, AND DESPINA STASI

References
[1] 4ti2 team. 4ti2-a software package for algebraic, geometric and combinatorial problems on linear spaces combinatorial problems on linear spaces.
[2] N. Amenta. Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem. In Proceedings of the 10th Annual Symposium on Computational Geometry (SCG), pages 340–347. ACM Press, 1994.
[3] N. Amenta. Helly theorems and generalized linear programming. Discrete and Computational Geometry, 12:241–
261, 1994.
[4] Nina Amenta, Jesús A. De Loera, and Pablo Soberón. Helly’s theorem: New variations and applications. Preprint.
arXiv:1508.07606. math.MG (math.CO).
[5] M. F. Atiyah and I. G. Macdonald. Introduction to commutative algebra. Addison-Wesley Publishing Co., Reading,
Mass.-London-Don Mills, Ont., 1969.
[6] D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler. Bertini: Software for numerical algebraic
geometry. Available at bertini.nd.edu with permanent doi: dx.doi.org/10.7274/R0H41PB5.
[7] K. Batselier, P. Dreesen, and B. De Moor. The geometry of multivariate polynomial division and elimination.
SIAM Journal on Matrix Analysis and Applications, 34(1):102–125, 2013.
[8] C. Beltrán and L.M. Pardo. On Smale’s 17th problem: a probabilistic positive solution. Foundations of Computational Mathematics, 8(1):1–43, 2008.
[9] C. Beltrán and L.M Pardo. Smale’s 17th problem: average polynomial time to compute affine and projective
solutions. J. Amer. Math. Soc., 22(2):363–385, 2009.
[10] E. R. Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation, 24(111):713–735,
1970.
[11] H. Björklund, S. Sandberg, and S. Vorobyov. A discrete subexponential algorithm for parity games. In Proc. 20th
Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 663–674. Springer-Verlag, 2003.
[12] Y. Brise and B. Gärtner. Clarkson’s algorithm for violator spaces. In 21st Canadian Conference on Computational
Geometry (CCCG2009), pages 9–12, 2009.
[13] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Leopold-Franzens University, 1965.
[14] B. Buchberger. Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue
class ring of a zero dimensional polynomial ideal (English translation). Journal of Symbolic Computation, 41(34):475–511, 2006.
[15] P. Bürgisser and F. Cucker. On a problem posed by Steve Smale. Annals of Mathematics, 174(3):1785–1836, 2011.
[16] D. Cifuentes and P. Parrilo. Exploiting chordal structure in polynomial ideals: a Gröbner bases approach. Preprint:
arXiv:1411.1745v1 [cs.SC].
[17] K. L. Clarkson. Las Vegas algorithms for linear and integer programming. Journal of the ACM, 42(2):488–499,
1995.
[18] D. Cox, J.B. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic
Geometry and Commutative Algebra. Springer, 2007.
[19] L. Danzer, B. Grünbaum, and V. Klee. Helly’s theorem and its relatives. In Proc. Sympos. Pure Math., Vol. VII,
pages 101–180. Amer. Math. Soc., Providence, R.I., 1963.
[20] J. A. De Loera, S. Margulies, M. Pernpeintner, E. Riedl, D. Rolnick, G. Spencer, D. Stasi, and J. Swenson. Graphcoloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases. In
International Symposium on Symbolic and Algebraic Computation (ISSAC), 2015.
[21] M. Deza and P. Frankl. A Helly type theorem for hypersurfaces. J. Combin. Theory Ser. A, 45(1):27–30, 1987.
[22] T.W. Dube. The structure of polynomial ideals and Gröbner bases. SIAM Journal of Computing, 19(4):750–773,
1990.
[23] J. Eckhoff. Helly, Radon, and Carathéodory type theorems. In Handbook of convex geometry, Vol. A, B, pages
389–448. North-Holland, Amsterdam, 1993.
[24] D. Eisenbud. The geometry of syzygies, volume 229 of Graduate Texts in Mathematics. Springer-Verlag, New York,
2005. A second course in commutative algebra and algebraic geometry.
[25] J.-C. Faugére, P. Gaudry, L. Huot, and G. Renault. Polynomial systems solving by fast linear algebra. arXiv
preprint arXiv:1304.6039, 2013.
[26] J.-C. Faugére, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero dimensional Gröbner bases by
change of ordering. Journal of Symbolic Computation, 16(4):329–344, 1993.
[27] J.-C. Faugére, P.-J. Spaenlehauer, and J. Svartz. Sparse Gröbner bases: the unmixed case. arXiv preprint
arXiv:1402.7205, 2014.
[28] P. Frankl. Helly-type theorems for varieties. European J. Combin., 10(3):243–245, 1989.

HELLY NUMBERS AND VIOLATOR SPACES IN COMPUTATIONAL ALGEBRA

15

[29] S. Gao. Counting Zeros over Finite Fields Using Gröbner Bases. PhD thesis, MS Thesis in Logic and Computation,
2009.
[30] S. Gao, V. M Rodrigues, and J. Stroomer. Gröbner basis structure of finite sets of points. Preprint. Available on
http://www.math.clemson.edu/~ sgao/papers/GBstr.pdf. Last accesed: November 2015., 2003.
[31] B. Gärtner, J. Matoušek, L. Rüst, and P. Škovroň. Violator spaces: structure and algorithms. Discrete Appl.
Math., 156(11):2124–2141, 2008.
[32] D. R. Grayson and M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available
at http://www.math.uiuc.edu/Macaulay2/.
[33] N. Halman. Discrete and lexicographic Helly theorems and their relations to LP-type problems. PhD thesis, Tel-Aviv
University, 2004.
[34] E. Helly. Über mengen konvexer Körper mit gemeinschaftlichen Punkten. Jahresbericht der Deutschen
Mathematiker-Vereinigung, 32(175–176), 1923.
[35] Y. N. Lakshman. On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal. In
Proceedings of the twenty-second annual ACM Symposium on Theory of Computing, pages 555–563. ACM, 1990.
[36] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New
York, 2002.
[37] J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16(4–5):498–
516, 1996.
[38] E. Miller and B. Sturmfels. Combinatorial commutative algebra. Graduate Texts in Mathematics. Springer, 2005.
[39] T. S. Motzkin. A proof of Hilbert’s Nullstellensatz. Math. Z., 63:341–344, 1955.
[40] I. Ramella. Algoritmi di Computer Algebra relativi agli ideali di punti dello spazio proiettivo. PhD thesis, Universita
degli studi di Napoli “Federico II”, 1990.
[41] M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems. In Proc. 9th Symposium on Theoretical Aspects of Computer Science (STACS), volume 577 of Lecture Notes in Computer Science,
pages 569–579. Springer-Verlag, 1992.
[42] P. Škovroň. Abstract models of optimization problems. PhD thesis, Charles University, Prague, 2007.
[43] R. Solovay and V. Strasse. A fast Monte-Carlo test for primality. SIAM Journal of Computing, 6(1), 1977.
[44] D.A. Spielman and S.H. Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice.
Communications of the ACM, 52(10):76–84, 2009.
[45] B. Sturmfels. Sparse elimination theory. Mathematical Sciences Institute, Cornell University, 1991.
[46] J. Verschelde. PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. Available at
http://homepages.math.uic.edu/∼jan/download.html.
[47] R. Wenger. Helly-type theorems and geometric transversals. In Handbook of discrete and computational geometry,
CRC Press Ser. Discrete Math. Appl., pages 63–82. CRC, Boca Raton, FL, 1997.
J. De Loera, Department of Mathematics, University of California, Davis.
E-mail address: deloera@math.ucdavis.edu
S. Petrović, Applied Mathematics Department, Illinois Institute of Technology.
E-mail address: Sonja.Petrovic@iit.edu
D. Stasi, Applied Mathematics Department, Illinois Institute of Technology.
E-mail address: despina.stasi@gmail.com

