arXiv:1406.2144v3 [math.AG] 20 Sep 2015

POLYNOMIAL PARTITIONING ON VARIETIES OF
CODIMENSION TWO AND POINT-HYPERSURFACE
INCIDENCES IN FOUR DIMENSIONS
SAUGATA BASU AND MARTÍN SOMBRA

Abstract. We present a polynomial partitioning theorem for finite sets of
points in the real locus of an irreducible complex algebraic variety of codimension at most two. This result generalizes the polynomial partitioning theorem
on the Euclidean space of Guth and Katz, and its extension to hypersurfaces
by Zahl and by Kaplan, Matoušek, Sharir and Safernová.
We also present a bound for the number of incidences between points and
hypersurfaces in the four-dimensional Euclidean space. It is an application of
our partitioning theorem together with the refined bounds for the number of
connected components of a semi-algebraic set by Barone and Basu.

Contents
1. Introduction
2. Preliminaries on Hilbert functions and semi-algebraic geometry
3. Partitioning finite sets on varieties
4. Point-hypersurface incidences
References

1
4
10
13
22

1. Introduction
The polynomial partitioning method was introduced by Guth and Katz in their
seminal paper [GK10]. Applying it in conjunction with the Elekes’ framework [ES11],
they made a breakthrough in a long-standing problem of Erdős on the number of
distinct distances between points in the plane, by nearly proving the distinct distances conjecture. Subsequently, this method has been applied to produce other
new results and simpler proofs of known results in discrete geometry, see for instance [KMS12, ST12].
The Guth-Katz polynomial partitioning method gives a nonlinear decomposition of the Euclidean space, which plays a role analogous to cuttings or trapezoidal
decompositions in the more classical Clarkson-Shor type divide-and-conquer arguments for such problems, see for instance [CEG+ 90].
Date: September 22, 2015.
2010 Mathematics Subject Classification. Primary 52C10; Secondary 13D40, 14P25.
Key words and phrases. Polynomial partitioning, Hilbert functions, connected components of
semi-algebraic sets, point-hypersurface incidences.
Basu and Sombra were partially supported by the IPAM research program “Algebraic Techniques for Combinatorial and Computational Geometry”. Basu was also partially supported by
NSF grants CCF-0915954, CCF-1319080 and DMS-1161629. Sombra was also partially supported
by the MINECO research project MTM2012-38122-C03-02.
1

2

BASU AND SOMBRA

It can be summarized in the result below. For a polynomial g ∈ R[x1 , . . . , xd ],
we denote by V (g) its zero zet in Cd and, for a finite set Q, we denote by card(Q)
its cardinality.
Theorem 1.1 (Guth and Katz [GK10]). Let d ≥ 1 and P ⊂ Rd be a finite subset.
Given ` ≥ 1, there is a nonzero polynomial g ∈ R[x1 , . . . , xd ] of degree bounded by
` such that, for each connected component C of Rd \ V (g),
 card(P) 
,
card(P ∩ C) = Od
`d
where the implicit constant in the O-notation depends only on d.
When applying this result in a concrete situation, one needs to couple it with a
suitable bound for the number of connected components of the semi-algebraic set
Rd \ V (g). This is provided by the classical works of Oleı̆nik, Petrovskiı̆, Milnor
and Thom on the Betti numbers of semi-algebraic varieties [PO49, Mil64, Tho65],
which allow to treat the points in P outside the hypersurface V (g).
However, it is possible that many, or even all, of the points in P are contained
in this hypersurface. The points in P ∩ V (g) are not partitioned, and a separate
argument is needed for handling them. The natural approach would be to apply
a polynomial partitioning theorem on V (g) together with a suitable bound for the
number of connected components of the resulting partition. After this step, it is
also possible that many of the points in P ∩ V (g) are contained in the partitioning
variety of codimension 2. Then one would like to apply a partitioning theorem on
this variety, and so on.
To make this strategy work efficiently, one needs a polynomial partitioning theorem on varieties. For hypersurfaces, such a result has been achieved independently
by Zahl [Zah13] and by Kaplan, Matoušek, Sharir and Safernová [KMSS12], and
applied to incidence problems in R3 . Extending it to varieties of arbitrary codimension has been identified as a major obstacle to apply the polynomial partitioning
method to incidence problems in dimension d ≥ 4, see for instance the discussion
in [KMSS12, §3]. Our main objective in this paper is to present such a result for
irreducible varieties of codimension two.
Given an irreducible algebraic variety X ⊂ Cd we denote by dim(X) and deg(X)
its dimension and degree, respectively. We also denote by δ(X) the minimal integer δ ≥ 1 such that X is an irreducible component of the zero set of a family of
polynomials of degree bounded by δ. These invariants are related by the inequalities (Lemma 2.2)
δ(X) ≤ deg(X) ≤ δ(X)d−dim(X) .
The following is a simplified version of our polynomial partitioning theorem
(Theorem 3.1).
Theorem 1.2. Let d ≥ 1 and X ⊂ Cd an irreducible variety of codimension at most
two. Let P ⊂ Rd ∩X be a finite subset and ` ≥ 6 d δ(X). Then there is a polynomial
g ∈ R[x1 , . . . , xd ] of degree bounded by ` with dim(X ∩ V (g)) = dim(X) − 1 such
that, for each connected component C of Rd \ V (g),


card(P)
card(P ∩ C) = Od
.
deg(X)`dim(X)
When X = Cd , the invariant δ(X) is equal to 1 whereas, when X is a hypersurface, it coincides with deg(X). Hence, Theorem 1.2 reduces in these cases to

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

3

Theorem 1.1 and to the polynomial partitioning theorems in [Zah13, KMSS12],
respectively.
As for the Guth-Katz theorem, the proof of this result is based on the ham
sandwich theorem obtained by Stone and Tukey from the Borsuk-Ulam theorem.
The new key ingredient is the systematic use of the upper and lower bounds for
Hilbert functions due to Chardin [Cha89] and Chardin and Philippon [CP99].
Remark 1.3. The polynomial partition method also applies to problems in computational geometry, in particular to range searching with semi-algebraic sets. Concurrently with this paper, Matoušek and Patáková have also obtained a polynomial
partitioning theorem on varieties [MS14, Theorem 1.1], focused on obtaining efficient range searching algorithms.
For irreducible varieties of codimension two, the Matoušek-Patáková partitioning
theorem is quantitatively weaker than ours. On the other hand, this result holds in a
more general setting, since it can be applied to non-necessarily irreducible varieties
of arbitrary dimension. This greater generality is important for their application
to range searching.
As a test case for Theorem 1.2, we consider the problem of bounding the number
of point-hypersurface incidences. Given a set P of points of Rd and a set V of
subvarieties of Rd or of Cd , we denote by I(P, V) their number of incidences, that
is, the number of pairs (p, V ) ∈ P × V with p ∈ V .
The following fundamental result was proved by Szemerédi and Trotter in 1983,
in response to a problem of Erdős.
Theorem 1.4 (Szemerédi and Trotter [ST83]). Let P be a set of m points of R2
and L a set of n lines in R2 . Then
2

2

I(P, L) = O(m 3 n 3 + m + n).
This theorem has led to an extensive study of incidences of points and curves
in the plane, and of points and varieties in higher dimensions. In particular, it
was extended by Pach and Sharir to incidences between points in the plane and
curves having a bounded degree of freedom [PS98]. Later on, Zahl obtained an
analogous result for the incidences between points in R3 and algebraic surfaces
having a bounded degree of freedom [Zah13]. A similar result was independently
obtained by Kaplan, Matoušek, Sharir and Safernová for the incidences between
points in R3 and unit spheres [KMSS12].
We present the following bound for the number of incidences between points in
R4 and threefolds.
Theorem 1.5. Given k, c ≥ 1, let P be a finite set of points of R4 and H a finite
set of hypersurfaces of C4 satisfying the following conditions:
(a) the degrees of the hypersurfaces in H are bounded by c;
(b) the intersection of any four distinct hypersurfaces in H is finite;
(c) for any subset of k distinct points in P, the number of hypersurfaces in H
containing them is bounded by c.
Set m = card(P) and n = card(H). Then
k−1

3

I(P, H) = Ok,c (m1− 4k−1 n1− 4k−1 + m + n).
This result is an application of Theorem 1.2 together with the refined bounds
for the number of connected components of a semi-algebraic set due to Barone and

4

BASU AND SOMBRA

Basu [BB12, BB13]. Our whole approach is strongly inspired by the treatment of
the unit distance problem in three dimensions in [Zah13, KMSS12].
Theorem 1.5 is a particular case of a conjectural bound for the number of pointhypersurface incidences in Rd (Conjecture 4.1). Related with this, we propose two
further conjectures: a generalization of our polynomial partitioning theorem to varieties of arbitrary codimension (Conjecture 3.4) and a bound for the number of
connected components of a semi-algebraic set depending on the degree of that variety, instead of the Bézout number of a set of defining equations (Conjecture 2.10).
If one can show that these two conjectures are true, it would be an important step
in proving Conjecture 4.1 via the polynomial partitioning method.
Remark 1.6. The results of this paper were announced in the talk [Som14] at the
IPAM workshop “Tools from algebraic geometry”. Shortly afterwards, a proof by
Fox, Pach, Suk, Sheffer and Zahl of a weaker version of Conjecture 4.1 with an
extra factor mε was announced in Sheffer’s blog [She14] and eventually appeared
in [FPS+ 14].
Acknowledgments. We thank Zuzana Safernová/Patáková, Micha Sharir, Noam
Solomon and Joshua Zahl for useful discussions and pointers to the literature. We
also thank the anonymous referees for their remarks and corrections, which have
significantly improved this paper.
Part of this work was done while the authors met at the Institute for Pure and
Applied Mathematics (IPAM) during the Spring 2014 research program “Algebraic
Techniques for Combinatorial and Computational Geometry”.

2. Preliminaries on Hilbert functions and semi-algebraic geometry
Throughout this paper, we denote by N the set of nonnegative integers. 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 , . . . , xd } so that R[x] denotes the polynomial ring R[x1 , . . . , xd ].
Given functions f, g : N → N, the Landau symbol f = O(g) means that there
exists c ≥ 0 such that f (l) ≤ c g(l) for all l ∈ N. If we want to emphasize the
dependence of the constant c on parameters, say d and k, we will write f = Od,k (g).
2.1. Hilbert functions and degree of definition of varieties. Let Pd (C) denote the d-dimensional projective space over the complex numbers. For an equidimensional variety X ⊂ Pd (C), we denote by dim(X) and deg(X) its dimension
and degree, respectively. Recall that the degree of X is classically defined as the
number of points in the intersection of X with a generic linear subspace H of
dimension d − dim(X).
When X is a hypersurface, this variety is defined by a single squarefree homogeneous polynomial g ∈ C[z0 , . . . , zd ], unique up a scalar factor, and we have
deg(X) = deg(g). In the other extreme, when dim(X) = 0, we have deg(X) = #X.
A basic property of the notion of degree of varieties is its behavior with respect
to intersections. In particular, it verifies the following version of Bézout’s inequality [Ful84, Example 8.4.6]: let Xi ⊂ Pd (C), i = 1, . . . t, be equidimensional varieties

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

and Zj , j = 0, . . . , l, the irreducible components of the intersection
l
X
j=0

deg(Zj ) ≤

t
Y

deg(Xi ).

Tt

j=1

5

Xj . Then
(2.1)

i=1

In particular, if g1 , . . . , gd ∈ C[z0 , . . . , zd ] is a family of homogeneous polynomials
whose zero set in Pd (C) is finite, then the cardinality of this zero set is bounded
Qd
by i=1 deg(gi ).
Definition 2.1. Let X ⊂ Pd (C) be an irreducible variety and δ ≥ 1. We say that
X is partially defined at degree δ if there are homogeneous polynomials g1 , . . . , gt ∈
C[z0 , . . . , zd ] of degree bounded by δ such that X is an irreducible component of
the zero set in Pd (C) of these polynomials. Equivalently, there is an open subset
U ⊂ Pd (C) such that X ∩ U 6= ∅ and the zero set in U of g1 , . . . , gt agrees with
X ∩ U.
We denote by δ(X) the degree of partial definition of X, defined as the minimal
integer δ ≥ 1 such that X is partially defined at degree δ.
The degree of a variety and its degree of partial definition are related by the
following inequalities.
Lemma 2.2. Let X ⊂ Pd (C) be an irreducible variety . Then
δ(X) ≤ deg(X) ≤ δ(X)d−dim(X) .
Proof. We first prove the left inequality. Set e = dim(X) and identify the projective
space Pe+1 (C) with the linear subspace of Pd (C) defined by the equations ze+2 =
· · · = zd = 0. Let L ⊂ Pd (C) be a generic linear subspace of dimension d − e − 2.
By making a linear change in coordinates which keeps ze+2 , . . . , zd unchanged, and
changes only the coordinates z0 , · · · , ze+1 , we can assume that L is defined by the
equations z0 = · · · = ze+1 = 0. Now consider the projection
πL : Pd (C) \ L −→ Pe+1 (C)
defined, for a point p ∈ Pd (C) \ L, by setting πL (p) as the unique point in the
intersection of Pe+1 (C) with the linear subspace generated by L and p. In other
words πL ((z0 : · · · : zd )) = (z0 : · · · : ze+1 : 0 : · · · : 0) for (z0 : · · · : zd ) 6∈ L.
Then πL (X), the closure of the image of X under this map, is a hypersurface of
Pe+1 (C) of the same degree as X. This hypersurface is defined by a homogeneous
polynomial fL ∈ C[z0 , . . . , ze+1 ] with
deg(fL ) = deg(πL (X)) = deg(X).
Then the polynomial fL considered as an element of the ring C[z0 , . . . , zd ] is a
homogeneous polynomial of degree deg(X) defining a hypersurface of Pd (C) which
contains X. By choosing sufficiently many linear subspaces L as above, one can construct a family of homogeneous polynomials of degree deg(X) defining the variety
X. Hence δ(X) ≤ deg(X), as stated.
For the right inequality, let g1 , . . . , gt ∈ C[z0 , . . . , zd ] be a family of homogeneous
polynomials of degree ≤ δ(X) having X as an irreducible component of its zero set.
By taking generic linear combinations, we can suppose that t = d − e. Bézout’s
inequality (2.1) then implies that deg(X) ≤ δ(X)d−e , proving the inequality.


6

BASU AND SOMBRA

Remark 2.3. The degree of partial definition of a variety can by much smaller
than its degree. An example is provided by the Grassmannian Gr(1, n), the
space
V2 n+1 
C
via the
parametrizing lines in Pn (C), included in the projective space P
Plücker embedding.
The degree of this Grassmannian is


1
2n − 2
deg(Gr(1, n)) =
,
n−1
n
which clearly grows with n. On the other hand, this variety is cut out by certain
quadratic equations, called the Plücker relations. Hence,
δ(Gr(1, n)) = 2.
For irreducible varieties of codimension 2, we have the following sharpening of
the second inequality in Lemma 2.2.
Lemma 2.4. Let X ⊂ Pd (C) be an irreducible variety of codimension 2. Let δ1 ≥ 1
be the minimal degree of a hypersurface of Pd (C) containing X. Then
deg(X) ≤ δ1 δ(X).
Proof. Let f be a homogeneous polynomial of degree δ1 ≥ 1 vanishing on X. By
the minimality assumption, this polynomial must be irreducible. Since X is of
codimension 2, there are two homogeneous poynomials g1 , g2 of degree ≤ δ(X),
having X as an irreducible component of its zero set. By clearing common factors,
we can also assume that one of these polynomials are coprime. Hence, at least
one of these these polynomials (say g1 ) is not divisible by f . Thus X is also an
irreducible component of the zero set of f and g1 . The lemma then follows from
Bézout’s inequality (2.1).

Given a homogeneous ideal I ⊂ C[z0 , . . . , zd ], the quotient C[z0 , . . . , zd ]/I is a
graded C-algebra. The Hilbert function of I is the function HI : N → N given, for
` ∈ N, by the dimension of the `-th graded piece of this quotient, that is

HI (`) = dimC C[z0 , . . . , zd ]/I ` .
By Hilbert’s theorem, there is a polynomial PI ∈ Q[t] and an integer `0 ∈ N with
HI (`) = PI (`)

for ` ≥ `0 .

d

For an equidimensional variety X ⊂ P (C), we denote by I(X) ⊂ C[z0 , . . . , zd ] its
defining ideal. Then PI(X) is a polynomial of degree dim(X) and leading coefficient
equal to the quotient deg(X)/dim(X)!.
In Theorem 2.5 below, we collect the upper and lower bounds for Hilbert functions that we will use later on. Because of our applications, we restrict to ideals
coming from irreducible projective varieties, although these bounds are valid in
greater generality. Recall that binomial coefficients are defined, for i, n ∈ Z, by

n!
  
if 0 ≤ i ≤ n,
n
= i!(n − i)!

i
0
otherwise.
Theorem 2.5. Let X ⊂ Pd (C) be an irreducible variety of dimension e ≥ 0.
(a) For ` ≥ 0,


`+e
HI(X) (`) ≤ deg(X)
.
e

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

7

(b) For ` ≥ (d − e)(δ(X) − 1) + 1,


` − (d − e)(δ(X) − 1) + e
HI(X) (`) ≥ deg(X)
.
e
Proof. The upper bound in (a) is [Cha89, Théorème on page 306] applied to the
base field C and the ideal I(X). Similar bounds can also be derived from [Nes84]
or [Som14, Proposition 2.11].
The upper bound in (b) is a particular case of [CP99, Corollaire 3]. Indeed,
let g1 , . . . , gt ∈ C[z0 , . . . , zd ] be a family of homogeneous polynomials of degree
≤ δ(X) having X as an irreducible component of its zero set. By taking generic
linear combinations, we can suppose without loss of generality that t = d − e.
Consider the ideals I = (g1 , . . . , gd−e ) and J = I(X). Following the notation in
page 476 of loc. cit., the ideal I hd−ei is defined as the intersection of the isolated
primary ideals of I of codimension d − e. Hence J ⊂ I hd−ei . We can then apply
[CP99, Corollaire 3] to these ideals. In the notation of this result, m = d − e,
di = deg(gi ) for i = 1, . . . , d − e, and r = d − e. This result then implies that, for
Pd−e
` ≥ i=1 deg(gi ) − (d − e),
Pd−e


` + d − i=1 deg(gi )
HI(X) (`) ≥ deg(X)
,
e
which gives the lower bound in (b).



The following result is a consequence of Theorem 2.5(a), and appears as a particular case of [Cha89, Corollaire 3]. We include its proof, for the convenience of
the interested reader.
Proposition 2.6. Let X ⊂ Pd (C) be an irreducible variety of codimension 2. Then
there are coprime polynomials f1 , f2 ∈ I(X) such that
deg(f1 ) deg(f2 ) ≤ d(d − 1) deg(X).
Proof. Set D = deg(X). By Theorem 2.5(a), for ` ≥ 0,


`+d−2
HI(X) (`) ≤ D
.
(2.2)
d−2

1/2
We have H{0} (`) = dimC C[z]` = `+d
c,
d . This implies that, for `1 = b(d(d−1)D)
HI(X) (`1 ) < H{0} (`1 ).
Hence, there is a homogeneous polynomial f1 ∈ I(X) \ {0} with deg(f1 ) ≤ `1 . We
take f1 of minimal degree. Since the variety X is irreducible, this polynomial has
to be irreducible too.
By the exact sequence
×f1

0 −→ C[z] −→ C[z] −→ C[z]/(f1 ) −→ 0,
the Hilbert function of the principal ideal (f1 ) is given by
H(f1 ) (`) = dimC C[z]` − dimC C[z]`−`1

 
 `X

1 −1 
`+d
` − `1 + d
`−j+d−1
=
−
=
. (2.3)
d
d
d−1
j=0

8

BASU AND SOMBRA


Using this, one can verify that, for `2 = max b(d(d − 1)D)1/2 c, bd(d − 1)D/`1 c ,
HI(X) (`2 ) < H(f1 ) (`2 ).
Hence, there is a homogeneous polynomial f2 ∈ I(X) \ (f1 ) with deg(f2 ) ≤ `2 .
Hence, the polynomials f1 , f2 are coprime and satisfy
deg(f1 ) deg(f2 ) ≤ `1 `2 ≤ d(d − 1)D,
as stated.



The next result gives a lower bound for the Hilbert function of the ideal of a
variety X of codimension two. For ` ≥ 0, it exhibits three different behaviors,
depending on the codimension of the zero set of the graded part I(X)` .
Proposition 2.7. There is a constant c = c(d) > 0 with the following property. Let
X ⊂ Pd (C) be an irreducible variety of codimension 2. Let δ1 ≥ 1 be the minimal
degree of a hypersurface of Pd (C) containing X and set δ2 = δ(X). Then

d

if 1 ≤ ` ≤ δ1 − 1,
c (` + 1) + 1
d−1
HI(X) (`) ≥ c δ1 (` + 1)
+1
if δ1 ≤ ` ≤ δ2 − 1,


c δ1 δ2 (` + 1)d−2 + 1 if δ2 ≤ `.
Proof. We have δ1 = min{` ≥ 0 | I(X)` 6= {0}}. Hence, for 1 ≤ ` ≤ δ1 − 1,


`+d
.
HI(X) (`) = H{0} (`) = dimC C[z]` =
d
Thus
HI(X) (`) ≥ c1 (` + 1)d + 1

(2.4)

for a suitable constant c1 > 0 depending only on d, giving the first lower bound.
Let f1 be a nonzero polynomial in I(X) of degree δ1 . By the minimality property
of δ1 , this polynomial must be irreducible. We have δ2 = min{` ≥ δ1 | I(X)` 6=
(f1 )` }. Hence, for δ1 ≤ ` ≤ δ2 − 1,

δX
1 −1 
`−j+d−1
,
HI(X) (`) = H(f1 ) (`) =
d−1
j=0
where the second equality comes from (2.3). It follows that, for δ1 ≤ ` ≤ δ2 − 1,

δ1
δ1 d−1
HI(X) (`) ≥
`−
+ 1 ≥ c2 δ1 (` + 1)d−1 + 1
(2.5)
2(d − 1)!
2
for another constant c2 = c2 (d) > 0.
Finally, we consider the case when ` ≥ δ2 . When ` ≤ 2(δ2 − 1), we deduce
from (2.5) that
HI(X) (`) ≥ HI(X) (δ2 − 1) ≥ c2 δ1 δ2d−1 + 1 ≥ c3 δ1 δ2 (` + 1)d−2 + 1.

(2.6)

Proposition 2.6 implies that d(d − 1) deg(X) ≥ δ1 δ2 . Hence, for ` ≥ 2(δ2 − 1) + 1,
Theorem 2.5(b) implies that


` − 2(δ2 − 1) + d − 2
HI(X) (`) ≥ deg(X)
≥ c4 δ1 δ2 (` + 1)d−2 + 1.
(2.7)
d−2
The result follows from (2.4), (2.5), (2.6) and (2.7) by taking c = mini ci .



PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

9

2.2. Connected components of semi-algebraic sets. As explained in the introduction, the polynomial partitioning method has to be coupled with bounds for the
number of connected components of semi-algebraic sets. When partitioning the Euclidean space Rd , the appropriate bound follows from the Oleı̆nik-Petrovskiı̆-MilnorThom’s bounds for the Betti numbers of a semi-algebraic set [PO49, Mil64, Tho65]:
with notation as in Theorem 1.1, the number of connected components of Rd \ V (g)
is bounded by `(2` − 1)d−1 = O(`d ).
In our situation, we will need the Barone-Basu bound for the number of connected components, with a refined dependence on the degrees of the polynomials
[BB12, BB13]. We recall a simplified version of this result in Theorem 2.8 below.
Given f1 , . . . , fe ∈ R[x1 , . . . , xd ], we denote by V (f1 , . . . , fe ) its zero set in Cd .
For a variety X ⊂ Cd , we denote by X(R) = X ∩ Rd its set of real points. For a
semi-algebraic subset S ⊂ Rd , we denote by cc(S) the set of connected components
of S. The 0-th Betti number b0 (S) coincides with the cardinality of the set cc(S).
Theorem 2.8. There is a constant c = c(d) with the following property. Let
f1 , . . . , fe , g ∈ R[x1 , . . . , xd ] with deg(f1 ) ≤ · · · ≤ deg(fe ) ≤ deg(g) such that
dim(V (f1 , . . . , fi )) = d − i for i = 1, . . . , e. Then both
b0 (V (f1 , . . . , fe )(R) \ V (g))

and
d−e

are bounded by c deg(f1 ) . . . deg(fe ) deg(g)

b0 (V (f1 , . . . , fe , g)(R))
.

Proof. The semi-algebraic set V (f1 , . . . , fe )(R) \ V (g) is the union of the realization
of the sign conditions ±1 of g on V (f1 , . . . , fe )(R). Similarly, V (f1 , . . . , fe , g)(R) is
the realization of the sign condition 0 of g on the same real algebraic variety.
The result follows from [BB13, Theorem 4] and the fact that dim(V (f1 , . . . , fi ))
bounds from above the dimension of the semi-algebraic set V (f1 , . . . , fi )(R), see
Remark 1.10 in loc. cit.

We will also need the technical result below. Given p ∈ Rd and r > 0, we
denote by B(p, r) the open ball in Rd with center p and radius r. Given a variety
W ⊂ Cd and a hypersurface H ⊂ Cd , we denote by B(W, H) the subset of W (R)
of points p ∈ W (R) having an open neighborhood, in the Euclidean topology of
W (R), contained in H. We also set G(W, H) = W (R) \ B(W, H).
Proposition 2.9. Let W ⊂ C4 be a variety and H, K ⊂ C4 two hypersurfaces. Let
b ∈ R[x1 , x2 , x3 , x4 ] be a polynomial defining H. Then there exists ε0 > 0 such that,
f ⊂ C4 containing W , the number of connected
for all 0 < ε ≤ ε0 and any variety W
4
components C of R \ K such that C ∩ G(W, H) ∩ H 6= ∅ is bounded by
f (R) ∩ V (b2 − ε)) \ K).
b0 ((W
Proof. Consider the set of connected components
C = {C ∈ cc(R4 \ K) | C ∩ G(W, H) ∩ H 6= ∅}.
For each C ∈ C choose a point pC ∈ C ∩ G(W, H) ∩ H. Since C is a finite set,
the set of points {pC }C∈C is finite. For each C ∈ C and r > 0, consider also the
semi-algebraic set given by
Ur (pC ) = B(pC , r) ∩ (W (R) \ K).
By the definition of G(W, H), the set Ur (pc ) is not contained in H. Semi-algebraic
sets are locally contractible because of their local conical structure, see for instance

10

BASU AND SOMBRA

[BPR06, Theorem 5.48]. Hence, there exists rC > 0 such that, for all 0 < r ≤ rC ,
the set Ur (pC ) is contractible and, in particular, connected. Set r0 = minC rC .
Choose also qC ∈ Ur0 (pC ) \ H and a semi-algebraic path γC : [0, 1] → Ur0 (pC )
with γ(0) = pC and γ(1) = qC . We have that b2 (qC ) > 0 because qC ∈
/ H. We set
ε0 = minC b2 (qC ).
By the intermediate value theorem, for all C ∈ C and 0 < ε ≤ ε0 , there exists
0 < tC ≤ 1 such that b2 (zC ) = ε with zC = γC (tC ). By construction,
f (R) ∩ V (b2 − ε)) \ K.
zC ∈ (W (R) ∩ V (b2 − ε)) \ K ⊂ (W
Moreover, zC ∈ C because this point is connected by a path to pC . For C, C 0 ∈ C
with C 6= C 0 , the points zC and zC 0 belong to distinct connected components of
f (R) ∩ V (b2 − ε) \ K. Hence, the map C 7→ zC induces an injection between the
W
f (R) ∩ V (b2 − ε)) \ K, which proves the
set of connected components C and cc(W
proposition.

In connection with the application of the polynomial partitioning theorem to incidence problems in higher dimensions, we propose the following conjectural bound
for the number of connected components of a semi-algebraic set in terms of the
degree of the variety instead of the Bézout number of a set of defining equations.
Conjecture 2.10. Let X ⊂ Cd be an irreducible variety and g ∈ R[x1 , . . . , xd ] a
polynomial of degree ` ≥ δ(X). Then there exists a variety Y ⊂ Cd containing X
as an irreducible component such that
b0 (Y (R) \ V (g))
dim(X)

are bounded by Od (deg(X)`

and

b0 (Y (R) ∩ V (g))

).

When X is an irreducible variety of codimension 2, this statement follows easily
from Proposition 2.6 and Theorem 2.8. In this case, the variety Y is given, in the
notation of Proposition 2.6, by the zero set of f1 and f2 .
3. Partitioning finite sets on varieties
Given a set of points P ⊂ Rd and a set of polynomials G ⊂ R[x1 , . . . , xd ], for
each choice of signs γ ∈ {±1}G we put
P(γ) = {p ∈ P | γg g(p) > 0 for all g ∈ G},

(3.1)

If the set of polynomials G is clear from the context, then we say that P(γ) is
realized by γ.
Given g ∈ R[x1 , . . . , xd ] \ {0}, we denote by irr(g) ⊂ R[x1 , . . . , xd ] a complete
and irredundant set of irreducible factors of g. These irreducible factors are unique
up to scalars in R× . To fix their indeterminacy, we choose them to be monic with
respect to some fixed monomial order on R[x1 , . . . , xd ]. With this convention, the
set irr(g) is uniquely defined and
Y
g=λ
q eq
q∈irr(g)
×

with λ ∈ R and eq ∈ N.
For ` ≥ 0, we denote by R[x1 , . . . , xd ]≤` the linear subspace of R[x1 , . . . , xd ] of
polynomials of degree bounded by `. Recall that, for a variety X ⊂ Cd , we denote
by X(R) = X ∩ Rd its set of real points.

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

11

We state and prove our polynomial partitioning theorem in terms of sign conditions. For convenience, we state it for varieties of codimension at most two, even
though we prove it only when the codimension is two. The cases when the codimension is smaller are simpler and can be proven as in [GK10, Zah13, KMSS12].
Theorem 3.1. Let X ⊂ Cd be an irreducible variety of codimension at most two,
P ⊂ X(R) a finite subset and ` ≥ 6 d δ(X). Then there exists g ∈ R[x1 , . . . , xd ]≤`
with dim(X ∩ V (g)) = dim(X) − 1 such that, for each γ ∈ {±1}irr(g) ,


card(P)
.
card(P(γ)) = Od
deg(X)`dim(X)
Remark 3.2. Let S ⊂ Rd be an arbitrary subset. For each connected component C
of S \ V (g), the set P ∩ C is contained in a set of the form P(γ) with γ ∈ {±1}irr(g) .
Hence, Theorem 1.2 in the introduction follows from Theorem 3.1 above by choosing
S = Rd .
`+d
Given ` ≥ 0, we denote by v the Veronese embedding Cd ,→ C( d )−1 given, for
`

a point p = (p1 , . . . , pd ) ∈ Cd , by
v` (p) = (pa )a

(3.2)
P
where a = (a1 , . . . , ad ) ∈ N runs over all nonzero vectors of length |a| = i ai
bounded by `, and where pa denotes the monomial pa1 1 . . . padd . We also denote by
ι the standard inclusion Cd → Pd (C) given by
d

ι(p) = (1 : p1 : · · · : pd ).
d

For a subset E ⊂ R , we denote by aff(E) the smallest affine subspace (or flat)
of Rd containing E. We also denote by I(ι(E)) ⊂ C[z0 , . . . , zd ] the homogeneous
ideal of polynomials vanishing identically on the subset ι(E) ⊂ Pd (C).
Lemma 3.3. With notation as above, let E ⊂ Rd be a subset and ` ≥ 0. Then
dimR (aff(v` (E))) = HI(ι(E)) (`) − 1.
Proof. The ideal I(ι(E)) is generated over R[z], because it is defined by the vanishing of a set of real points. Setting I = I(ι(E)) ∩ R[z], we have

HI(ι(E)) (`) = dimC C[z]/I(ι(E)) ` = dimR (R[z]` ) − dimR (I` ),
(3.3)
where I` denotes the `-th graded part of I.
`+d
Consider the Euclidean space R( d ) with coordinates indexed by the vectors of
Nd+1 of length equal to `, and the pairing defined by
X

X
`+d
b
(
)
d
R[z]` × R
−→ R,
αb z , w 7−→
αb wb ,
(3.4)
|b|=`

b

d+1

of length `.
where b runs over all vectors of N
`+d
Consider the subset {1} × v` (E) ⊂ R( d ) , with 1 ∈ R and v` (E) the image
of E under the Veronese embedding (3.2). The graded part I` coincides with the
annihilator of this subset with respect to the pairing (3.4). Since I` is a linear
`+d
subspace, it also coincides with the annihilator of the linear span in R( d ) of
this subset. Denote by lin({1} × v` (E)) this linear span, which is a linear space
containing {1} × aff(v` (E)) as an affine hyperplane. Hence
dimR (R[z]` ) − dimR (I` ) = dimR (lin({1} × v` (E))) = dimR (aff(v` (E))) + 1. (3.5)

12

BASU AND SOMBRA

The result then follows from (3.3) and (3.5).



Proof of Theorem 3.1. We assume that X is of codimension 2. Let δ1 ≥ 1 be the
minimal degree of a hypersurface of Pd (C) containing X and set also δ2 = δ(X).
Let η ≥ δ2 be an integer to be fixed later on.
Let c = c(d) be the constant in Proposition 2.7 and set c1 = min{c, 2−d }. Put
s1 = log(c1 δ1 δ2d−1 ),

s0 = log(c1 δ1d ),

t = blog(c1 δ1 δ2 η d−2 )c

and

−1 i 1

b(c1 2 ) d c 1
−1 i d−1
`i = b(c−1
c
1 δ1 2 )

1
 −1 −1 −1 i d−2
b(c1 δ1 δ2 2 )
c

for 0 ≤ i < s0 ,
for s0 ≤ i < s1 ,
for s1 ≤ i ≤ t,

where b·c denotes the floor function. We verify that the following conditions hold:
if 0 ≤ i < s0 then 1 ≤ `i ≤ δ1 − 1,
if s0 ≤ i < s1 then δ1 ≤ `i ≤ δ2 − 1,

(3.6)

if s1 ≤ i ≤ t then δ2 ≤ `i ≤ η.
`i +e
Let v`i be the Veronese map of degree `i as in (3.2) and set Ai ⊂ R( e ) − 1
for the affine hull of the image of X(R) under v`i . Let I(ι(X(R))) be the ideal
of polynomials vanishing on the image under ι of the set of real points of X. By
Lemma 3.3,
dimR (Ai ) = HI(ι(X(R))) (`i ) − 1.
(3.7)

Since ι(X(R)) ⊂ ι(X), we have that I(ι(X(R))) ⊃ I(ι(X)) and so
HI(ι(X(R))) (`i ) ≤ HI(ι(X)) (`i ).

(3.8)

We consider first the case when (3.8) is an equality for all i. Since the affine
variety X is irreducible and partially defined at degree δ(X), the same holds for
ι(X), the Zariski closure of ι(X) in projective space. It follows from Proposition
2.7 and the conditions in (3.6) that
HI(ι(X(R))) (`i ) ≥ 2i + 1,

i = 0, . . . , t.

(3.9)

As in the Guth-Katz polynomial partitioning, we will inductively subdivide the
set of points P. We start with C0 = {P}. Having constructed Ci with at most
2i sets, we apply the ham sandwich theorem to the image of these sets under the
map v`i . These images lie in Ai and, by (3.7) and (3.9), this is an affine space of
dimension ≥ 2i . Hence, there is a nonzero linear form on Ai that bisects each of
these images or, equivalently, there is a polynomial gi ∈ R[x1 , . . . , xd ]≤`i bisecting
each of the sets in Ci .
For each Q ∈ Ci , we put Q+ and Q− for the sets of points of Q at which gi > 0
and gi < 0, respectively. We then put
[
Ci+1 =
{Q+ , Q− }.
Q∈Ci

Hence, each of the sets in Ct has cardinality bounded by 2−t card(P).
Qt
Set g = i=0 gi . To bound the degree of g, we write deg(g) = S0 + S1 + S2 with
X
X
X
S0 =
`i , S1 =
`i , S2 =
`i .
0≤i<s0

s0 ≤i<s1

s1 ≤i≤t

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

13

We have that
S0 ≤

sX
0 −1

1
−d

1

i d
(c−1
1 2 ) ≤ c1

2

i=0

s0 +1
d

−1

1

2d − 1

1

≤

2d
1

2d − 1

δ1 .

Similarly, one can verify that
1

S1 ≤

2 d−1
1

2 d−1 − 1

1

δ2

and

S2 ≤

2 d−2
1

2 d−2 − 1

η.

Using that d ≥ 3 and δ1 ≤ δ2 , we deduce that deg(g) ≤ 4 d δ2 + 2 d η. Finally, set
`
− 2δ2 .
2d
Since ` ≥ 6 d δ2 , we have that η ≥ δ2 as required and deg(g) ≤ `, as stated.
On the other hand, the sets in Ct are realized by sign conditions given in terms
of the gi ’s. The sets realized by sign conditions on irr(g) have cardinality bounded
`
by those in Ct . Since η ≥ 6d
, it follows that for each γ ∈ {±1}irr(g) ,
η=

card(P(γ)) ≤

card(P)
card(P)
≤ c2
,
t
2
deg(X)η d−2

where the last inequality follows from Lemma 2.4, and c2 denotes a suitable constant. This proves the statement in the case when X is of codimension 2 and the
inequality (3.8) are equalities for all i.
If the inequality (3.8) is strict for some i, then there is a polynomial gi ∈
I(X(R)) \ I(X) of degree bounded by `i ≤ `. Hence, the hypersurface V (gi ) cuts
X properly and contains its set of real points. In particular, P ⊂ V (gi ). It follows
that g = gi has the appropriate degree and P(γ) = ∅ for all γ ∈ {±1}irr(g) , which
completes the proof for the case when X is of codimension two.
The cases when the codimension of X is either zero or one are simpler and can
be proven as in [GK10, Zah13, KMSS12].

A previous version of this paper contained a polynomial partitioning theorem on
varieties of arbitrary dimension. Whereas the proof of this result contained a gap,
we still think that its statement is correct, and we propose it as a conjecture.
Conjecture 3.4. There is a constant c = c(d) > 0 with the following property. Let
X ⊂ Cd be an irreducible variety of dimension e, P ⊂ X(R) a finite subset and
` ≥ c δ(X). Then there exists g ∈ R[x1 , . . . , xd ]≤` with dim(X ∩V (g)) = dim(X)−1
such that, for each γ ∈ {±1}irr(g) ,
card(P(γ)) ≤ c

card(P)
.
deg(X)`e

4. Point-hypersurface incidences
In this section we prove Theorem 1.5. To this end, we use three levels of polynomial partitioning. This leads to a partition of the Euclidean space R4 into semialgebraic pieces of various dimensions. We bound separately the number of incidences contributed by the points of the set P in each piece. The contribution from
each level of the partitioning is essentially the same, up to constant factors, as the
claimed bound.

14

BASU AND SOMBRA

Proof of Theorem 1.5. The procedure performed at each level is similar. For clarity
and ease of exposition, we prefer to describe each of these level separately, even at
the expense of repeating some of the arguments.
The set of incidences between P and H is the subset of P × H defined by
I(P, H) = {(p, H) ∈ P × H | p ∈ H}.
Hence I(P, H) = card(I(P, H)). For a subset Q ⊂ P, we denote by
I<k (Q, H) = {(p, H) ∈ I(Q, H) | card(H ∩ Q) < k},
I≥k (Q, H) = {(p, H) ∈ I(Q, H) | card(H ∩ Q) ≥ k}
the set of incidences between Q and hypersurfaces of H containing at most k − 1
points of Q and at least k points of Q, respectively. We also set I<k (Q, H) =
card(I<k (Q, H)) and I≥k (Q, H) = card(I≥k (Q, H)). Clearly,
I(Q, H) = I<k (Q, H) + I≥k (Q, H).

(4.1)

In the sequel, the dimension d of the ambient space is fixed to 4. Hence, all
implicit constants in the O-notation depend only on the parameters k and c in the
statement of the theorem.
First level partitioning. Let D ≥ 24 to be fixed later on. By Theorem 3.1, there
exists f ∈ R[x1 , x2 , x3 , x4 ]≤D \ {0} such that, for each γ ∈ {±1}irr(f ) ,
m
,
(4.2)
card(P(γ)) = O
D4
where P(γ) denotes the subset of P realized by the signs γ as in (3.1). Choose a
minimal subset Σ1 ⊂ {±1}irr(f ) realizing all nonempty subsets of this form.
We partition P into the disjoint subsets P0 = P ∩ V (f ) and P(γ), γ ∈ Σ1 . Set
m0 = card(P0 ) and mγ = card(P(γ)) for each γ. Clearly,
X
m0 +
mγ = m.
γ∈Σ1

We first bound the number of incidences with hypersurfaces that contain at least
k points in one of the subsets P(γ). By the hypothesis (c), for each γ ∈ Σ1 and
each subset of k points of P(γ), there are at most c hypersurfaces in H containing
these points. Hence,
 
mγ
I≥k (P(γ), H) ≤ ck
= O(mkγ ).
(4.3)
k
The cardinality of Σ1 or equivalently, the number of nonempty subsets of the form
P(γ), is bounded by the number of connected components of R4 \ V (f ). By Theorem 2.8, applied with e = 0, this number is bounded by O(D4 ). With (4.2) and
(4.3), this implies that
 X  m k 
X
I≥k (P(γ), H) = O
= O(mk D4−4k ).
(4.4)
4
D
γ
γ
We now bound the number of incidences with hypersurfaces that contain at most
k − 1 points in every P(γ). For each H ∈ H, the number of subsets P(γ) having
nonempty intersection with H is bounded by b0 (H(R)\V (f )). By Theorem 2.8, this
number of connected components is bounded by O(D3 ), because the degree of H is

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

bounded by a constant. Hence
It follows that
X

P

γ I<k (P(γ), {H})

15

≤ (k−1) b0 (H \V (f )) = O(D3 ).

I<k (P(γ), H) = O(nD3 ).

(4.5)

γ

From (4.1), (4.4) and (4.5) we deduce that
X
I(P \ P0 , H) =
I(P(γ), H) = O(nD3 + mk D4−4k ).

(4.6)

γ

We then set

mα1 
D = max 24, β1
n

with α1 =

k
1
and β1 =
.
4k − 1
4k − 1

(4.7)

If D = 24, then mα1 n−β1 ≤ 24 and so mk = O(n). In this case, it follows from
(4.6) that I(P \ P0 , H) = O(n + mk ) = O(n). Otherwise,
k−1

3

I(P \ P0 , H) = O(m3α1 n1−3β1 ) = O(m1− 4k−1 n1− 4k−1 ).
In either case,
k−1

3

I(P \ P0 , H) = O(m1− 4k−1 n1− 4k−1 + n).
(4.8)
S
Second level partitioning. Let V (f ) = i∈I Vi be the decomposition of the hypersurface V (f ) into irreducible components. Set Di = deg(Vi ) for each i ∈ I. Then
X
Di = deg(V (f )) ≤ D.
(4.9)
i∈I

We choose a partition of the finite set P0 = P ∩ V (f ) into disjoint subsets Qi ,
i ∈ I, by assigning each point in P0 to one of the subsets Qi corresponding to an
irreducible component Vi it belongs to. Set li = card(Qi ) for each i ∈ I. Then
X
li = m0 .
(4.10)
i

Fix i ∈ I and let Ei ≥ 24Di . By Theorem 3.1, there exists gi ∈ R[x1 , x2 , x3 , x4 ]≤Ei
such that dim(Vi ∩ V (gi )) = 2 and, for each δ ∈ {±1}irr(gi ) ,
 l 
i
card(Qi (δ)) = O
.
(4.11)
Di Ei3
Choose a minimal subset Σ2,i ⊂ {±1}irr(gi ) realizing all nonempty subsets of the
form Qi (δ).
Consider the surface Wi = Vi ∩ V (gi ) = V (fi , gi ) and partition Qi into the
disjoint subsets Qi,0 = Qi ∩ Wi and Qi (δ), δ ∈ Σ2,i . We set li,0 = card(Qi,0 ) and
li,δ = card(Qi (δ)) for each δ. Clearly,

X
[ 
X
li,0 +
li,δ = li and
li,0 = card P ∩
Wi .
δ∈Σ2,i

i

i

We follow the same approach as in the previous case, and we first bound the
number of incidences with hypersurfaces that contain at least k points in some
Qi (δ). Similarly as in (4.3), the hypothesis (c) implies that, for each δ,
 
li,δ
k
I≥k (Qi (δ), H) ≤ ck
= O(li,δ
).
(4.12)
k

16

BASU AND SOMBRA

The cardinality of Σ2,i is bounded by b0 (Vi (R) \ V (gi )) which, by Theorem 2.8, is
bounded by O(Di Ei3 ). With (4.11) and (4.12), this implies that
 X  l k 
X
i
= O(lik Di1−k Ei3−3k ).
(4.13)
I≥k (Qi (δ), H) = O
Di Ei3
δ

δ

We now bound the number of incidences with hypersurfaces that contain at most
k − 1 points in every Qi (δ). Let H ∈ H and, for the moment, suppose that Vi 6⊂ H.
Since Vi is an algebraic variety over C with dim(Vi ) = 3, by [Har77, Chapter I,
Proposition 7.1] we have that either H ∩ Vi is empty or of dimension 2. Moreover,
the degree of H is bounded by a constant. The number of subsets of the form
Qi (δ) with nonempty intersection with H is bounded by b0 ((H ∩ Vi )(R) \ V (gi )).
By Theorem 2.8, this number is bounded by O(Di Ei2 ). If we note by Hi the set of
hypersurfaces of H not containing Vi , then
X
I<k (Qi (δ), Hi ) = O(nDi Ei2 ).
δ

On the other hand, by the hypothesis (b), there are at most 3 hypersurfaces H ∈ H
containing Vi , and each of them contains the li points of Qi . Hence
I<k (Qi \ Qi,0 , H \ Hi ) ≤ I(Qi , H \ Hi ) ≤ 3li .

(4.14)

By (4.13) and (4.14),
I(Qi \ Qi,0 , H) =

X

I(Qi (δ), H) = O(nDi Ei2 + lik Di1−k Ei3−3k + li ).

(4.15)

δ

We set

 l α 2 1 
i
Ei = max 24Di ,
Di
nβ2

with α2 =

k
1
and β2 =
.
3k − 1
3k − 1

(4.16)

If Ei = 24Di , then ( Dlii )α2 n−β2 ≤ 24Di . In this case, the first term in the righthand side of (4.15) controls the second one. Otherwise, both terms are equal up to
a constant factor. We deduce from (4.15) that
(
O(nDi3 + li )
if Ei = 24Di ,
I(Qi \ Qi,0 , H) =
(4.17)
1−2β2 2α2 1−2α2
O(n
li Di
+ li ) otherwise.
By (4.9),
X

k−1

3

nDi3 ≤ nD3 = O(m1− 4k−1 n1− 4k−1 + n),

(4.18)

i

as the term nD3 appears in (4.6) and is accounted for in (4.8). Using the Hölder
inequality as well as (4.9) and (4.10), we get
 X 2α2  X 1−2α2
X
n1−2β2 li2α2 Di1−2α2 ≤ n1−2β2
li
Di
i

i

i

≤ n1−2β2 m02α2 D1−2α2 . (4.19)
We now substitute the value of D from (4.7) and those of α1 , α2 , β1 and β2 in
the above expression. If D = 24, then mk = O(n) and so n1−2β2 m02α2 D1−2α2 =
2
n1−2β2 m2α
= O(n). Otherwise,
0
k−1

3

1−2α2
2
n1−2β2 m2α
≤ n1−2β2 m2α2 (mα1 n−β1 )1−2α2 = m1− 4k−1 n1− 4k−1 .
0 D

(4.20)

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

17

It follows from (4.17), (4.18), (4.19), (4.20) and (4.10) that

 X
[
I P0 \ Qi,0 , H =
I(Qi \ Qi,0 , H)
i

i

=O

X

nDi3 +

i

X

n1−2β2 li2α2 Di1−2α2 +

i

k−1
1− 4k−1

= O(m

n

X 
li
i

3
1− 4k−1

+ n + m0 ).
(4.21)
S
Third level partitioning. For each i ∈ I, let Wi = j∈Ji Wi,j be the decomposition
of the surface Wi = V (fi , gi ) into irreducible components. Set ∆i,j = deg(Wi,j ) for
each j. By Bézout’s inequality,
X
∆i,j = deg(Wi ) ≤ Di Ei .
(4.22)
j∈Ji

We denote by Wi (R)0 and Wi,j (R)0 the set of isolated points of the semi-algebraic
sets Wi (R) and Wi,j (R), respectively. We then choose an arbitrary partition of the
set Qi,0 = Qi ∩ Wi into disjoints subsets Ri,j , j ∈ Ji , such that
Ri,j ⊂ Wi,j (R)

and

Set ei,j = card(Ri,j ) for each j. Then
X

Ri,j ∩ Wi,j (R)0 ⊂ Wi (R)0 .

ei,j = li,0 .

(4.23)

j

Let j ∈ Ji . Being an irreducible component of Wi = V (fi , gi ), the variety Wi,j
is partially defined at degree Ei . Let Fi,j ≥ 24Ei , to be fixed later on. By Theorem
3.1, there exists hi,j ∈ R[x1 , x2 , x3 , x4 ]≤Fi,j such that dim(Wi,j ∩ V (hi,j )) = 1 and,
for each η ∈ {±1}irr(hi,j ) ,
 e

i,j
card(Ri,j (η)) = O
.
(4.24)
2
∆i,j Fi,j
Similarly as before, choose a minimal subset Σ3,i,j ⊂ {±1}irr(hi,j ) realizing all
nonempty subsets of the form Ri,j (η).
Consider the curve Yi,j = Wi,j ∩ V (hi,j ) and partition Ri,j into the disjoint
subsets Ri,j,0 = Ri,j ∩ Yi,j and Ri,j (η), η ∈ Σ3,i,j . Set also ei,j,0 = card(Ri,j,0 ) and
ei,j,η = card(Ri,j (η)) for each η. Hence,
X
ei,j,0 +
ei,j,η = ei,j .
η∈Σ3,i,j

We first bound the number of incidences of Ri,j \ Ri,j,0 with hypersurfaces that
contain at least k points in some Ri,j (η). Similarly as for (4.3) and (4.12), the
hypothesis (c) implies that, for each η,


ei,j,η
I≥k (Ri,j (η), H) ≤ ck
= O(eki,j,η ).
(4.25)
k
By Proposition 2.6, after dehomogenizing, there are coprime polynomials fei,j , gei,j ∈
fi,j =
R[x1 , x2 , x3 , x4 ] such that Wi,j is an irreducible component of the variety W
V (fei,j , gei,j ) and
deg(fei,j ) deg(e
gi,j ) = O(∆i,j ).
(4.26)

18

BASU AND SOMBRA

Since Wi,j is partially defined at degree Ei , we can furthermore deduce that deg(fei,j ), deg(e
gi,j ) ≤
Ei .
The number of nonempty subsets of the form Ri,j (η) is bounded by the number
fi,j (R) \ V (hi,j ), as explained in Remark 3.2. By
of connected components of W
Theorem 2.8 and (4.26), this number of connected components is bounded by
2
2
fi,j (R) \ V (hi,j )) = O(deg(fei,j ) deg(e
b0 (W
gi,j )Fi,j
) = O(∆i,j Fi,j
).

By (4.24), (4.25) and (4.27),
X
X
I≥k (Ri,j (η), H) = O
η

η

ei,j k 
2−2k
= O(eki,j ∆1−k
).
i,j Fi,j
2
∆i,j Fi,j

(4.27)

(4.28)

We now bound the number of incidences of Ri,j \ Ri,j,0 with hypersurfaces that
contain at most k − 1 points in every Ri,j (η). We would like to use an argument
similar to those used above in the case of first and second level partitioning, and
bound, for each H ∈ H, the number of these incidences on H, by k times the
number of connected components of R4 \V (hi,j ) having nonempty intersection with
H ∩Wi,j (R) using Theorem 2.8. However, there are two difficulties in this approach.
First, unlike the prior cases, we do not have the equations defining Wi,j , but rather
fi,j . This is not a serious problem, since clearly
those of a possibly larger variety W
the number of connected components of R4 \ V (hi,j ), met by the possibly larger
fi,j (R) is an upper bound on the number of connected components of
set H ∩ W
4
R \ V (hi,j ) having nonempty intersection with H ∩ Wi,j (R). The second difficulty
is more serious. To apply Theorem 2.8 to obtain a sufficiently good upper bound
fi,j is
(see (4.30) below) we require that the dimension of the intersection H ∩ W
f
one (if H ∩ Wi,j is non-empty), and this requirement might not be satisfied. To
circumvent this difficulty, for each H ∈ H, we partition Wi,j (R) into two semialgebraic subsets, namely Gi,j (H) and Bi,j (H). The non-isolated points of Wi,j (R)
which belong Bi,j (H) are points having an open neighborhood in Wi,j (R) (with
respect to its Euclidean topology) which is contained also in H. Such points have
the bad property that the intersection of Wi,j (R) with a small perturbation of H
could be empty in a neighborhood of such a point. We bound incidences created
by points in the various Bi,j (H) using a separate argument (see inequality (4.40)
below).
On the other hand, to bound the incidences in H ∩ Gi,j (H), we show (using
Proposition 2.9) that it is possible to replace H by a slightly perturbed hypersurface
e ⊂ R4 of degree twice the degree of H, satisfying:
H
(a) every connected component of R4 \ V (hi,j ) having nonempty intersection
e ∩W
fi,j (R);
with H ∩ Gi,j (H) also has a non-empty intersection with H
e ∩W
fi,j is equal to 1 if H
e ∩W
fi,j 6= ∅.
(b) the dimension of H
This, allows us to obtain the necessary estimate (see (4.30) below) on the number
of connected components of R4 \ V (hi,j ) having nonempty intersection with H ∩
Gi,j (H) using Theorem 2.8. We now make the above arguments precise as follows.
Given H ∈ H, we denote by Bi,j (H) ⊂ Wi,j (R) the semi-algebraic subset of
points p ∈ Wi,j (R) having an open neighborhood, in the Euclidean topology of
Wi,j (R), contained in H. We also set Gi,j (H) = Wi,j (R) \ Bi,j (H). Notice that
unlike Bi,j (H), the semi-algebraic set Gi,j (H) is not necessarily contained in H,
and that Wi,j (R)0 ∩ H ⊂ Bi,j (H).

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

19

For any finite subset R ⊂ Wi,j (R) we set
[
[
I B (R, H) =
I(R ∩ Bi,j (H), H) and I G (R, H) =
I(R ∩ Gi,j (H), H).
H∈H

H∈H

We also set I B (R, H) = card(I B (R, H)) and I G (R, H) = card(I G (R, H)).
Clearly,
I(R, H) = I B (R, H) + I G (R, H).
We first treat the incidences in Gi,j (H). Write H = V (b) with b ∈ R[x1 , x2 , x3 , x4 ].
The number of nonempty subsets of the form Ri,j (η) ∩ Gi,j (H) is bounded by the
number of connected components of R4 \V (hi,j ) having nonempty intersection with
H ∩ Gi,j (H). By Proposition 2.9, this number of connected components is bounded
by the number of connected components of the semi-algebraic set
fi,j ∩ V (b2 − ε))(R) \ V (hi,j ) = V (b2 − ε, fei,j , gei,j )(R) \ V (hi,j )
(W

(4.29)

for any ε > 0 sufficiently small. Choosing a possibly smaller ε > 0, we also have
fi,j ∩ V (b2 − ε)) = 1 if W
fi,j ∩ V (b2 − ε) 6= ∅. To see this, observe that
that dim(W
fi,j ) is finite using Sard’s theorem
the set of critical values of b2 restricted to reg(W
[Loj91, page 255], and hence, for all ε > 0 small enough, ε is a regular value
fi,j ). It follows that either W
fi,j ∩ V (b2 − ε) is empty, or
of b2 restricted to reg(W
fi,j ∩ V (b2 − ε)) = 1, using the implicit function theorem (see for example
dim(W
[GH78, page 19]).
For any such choice of ε, by Theorem 2.8 and (4.26), the number of connected
components of the semi-algebraic set in (4.29) is bounded by
O(deg(b2 − ε) deg(fei,j ) deg(e
gi,j ) deg(hi,j )) = O(∆i,j Fi,j ).

(4.30)

Thus
X

G
I<k
(Ri,j (η), H) = O(n∆i,j Fi,j ),

(4.31)

η

where
G
I<k
(Ri,j (η), H) = card(I G (Ri,j (η), H) ∩ I<k (Ri,j (η), H)).

Gathering together (4.28) and (4.31), we obtain that
X
I G (Ri,j \ Ri,j,0 , H) =
I G (Ri,j (η), H)
η


2−2k
.
= O n∆i,j Fi,j + eki,j ∆1−k
i,j Fi,j

(4.32)

We set

 e α 3 1 
i,j
Fi,j = max 24Ei ,
∆i,j
nβ3
e

with α3 =

k
1
and β3 =
.
2k − 1
2k − 1

If Fi,j = 24Ei , then ( ∆i,j
)α3 n−β3 = O(Ei ). In this case, the first term in the
i,j
right-hand side of (4.32) controls the second one and, otherwise, both terms are
equal up to a constant factor. Hence,
(
O(n∆i,j Ei )
if Fi,j = 24Ei ,
G
(4.33)
I (Ri,j \ Ri,j,0 , H) =
1−β3 α3 1−α3
O(n
ei,j ∆i,j ) otherwise.

20

BASU AND SOMBRA

By (4.22) and Bézout’s inequality,
X
X
k−1
3
n∆i,j Ei ≤
nDi Ei2 = O(m1− 4k−1 n1− 4k−1 + n),
i,j

(4.34)

i

as shown when passing from (4.15) to (4.21). Else, applying the Hölder inequality
together with (4.23) and (4.9),
X
α 3  X
1−α3
X
1−α3
3
≤ n1−β3
ei,j
∆i,j
n1−β3 eα
i,j ∆i,j
i,j

i,j

i,j

≤ n1−β3 mα3

X

D i Ei

1−α3

. (4.35)

i

α2 −β 
Recall that Ei = max 24Di , Dlii
n 2 as in (4.16). Hence
X

X
X
D i Ei = O
Di2 + n−β2
li α2 Di 1−α2
i

i

=O

i

X

 X α2  X 1−α2 
Di2 + n−β2
li
Di

i

i

i


= O D2 + n−β2 mα2 D1−α2 .
(4.36)

Recall also that D = max 24, mα1 n−β1 as in (4.7). If D = 24, then mk = O(n).
P
α1 −β1
In this case,
in (4.36) and
i Di Ei = O(1). Otherwise, substituting D = m n
P
the sum i Di Ei into (4.35),
X
1−α3

n1−β3 mα3
Di Ei
= O n1−β3 mα3 (n−β2 mα2 (mα1 n−β1 )1−α2 )1−α3
i


k−1
3
= O m1− 4k−1 n1− 4k−1 .

(4.37)

It follows from (4.33), (4.34), (4.35), (4.36) and(4.37), that
[
 X
[
IG
Qi,0 \ Ri,j,0 , H =
I G (Ri,j \ Ri,j,0 , H)
i

i,j

i,j

=O

X

2−2k
n∆i,j Fi,j + eki,j ∆1−k
F
i,j
i,j

(4.38)

i,j


k−1
3
= O m1− 4k−1 n1− 4k−1 + n .

(4.39)

Finally, we treat the incidences in Bi,j (H). We claim that for each p ∈ Ri,j \
Wi (R)0 there are at most 3 hypersurfaces in H such that p ∈ Bi,j (H). To see
this, observe that p ∈ Bi,j (H) implies that H contains an open neighborhood
U ⊂ Wi,j (R) of p. Since p is not an isolated point of Wi,j (R), if follows that U is
of real dimension at least 1. The claim then follows from the hypothesis (b).
Hence,
I B (Ri,j \ Wi (R)0 , H) ≤ 3ei,j .
(4.40)
The incidences of Qi with hypersurfaces H ∈ H containing Vi are already accounted for in (4.14). Hence, we can suppose that Vi is not contained in H. In this
case, by Theorem 2.8, card(H ∩ Wi (R)0 ) ≤ b0 (V (b, fi , gi )) = O(Di Ei2 ), where b is
the polynomial defining H. Together with (4.14), this implies that
X
I B (Ri,j ∩ Wi (R)0 , H) = O(nDi Ei2 + li )
(4.41)
j

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

21

It follows from (4.40), (4.23) and (4.41) that
X
I B (Ri,j , H) = O(nDi Ei2 + li ) + O(li,0 ) = O(nDi Ei2 + li ).
j

This bound already appears in (4.15). The contribution of the sum of these terms
over i ∈ I is accounted for in (4.21) and can be absorbed into the bound (4.39),
after adding the term m. We conclude that
[

[

k−1
3
I
(4.42)
Qi,0 \ Ri,j,0 , H = O m1− 4k−1 n1− 4k−1 + m + n .
i

i,j

The case of curves and conclusion of the proof. Finally, we bound the number of
incidences that occur on the curves Yi,j = Wi,j ∩S
V (hi,j ).
For each i, j, set Ri,j,0 = Ri,j ∩Yi,j . Let Yi,j = l∈Li,j Yi,j,l be the decomposition
of Yi,j into irreducible components and consider an arbitrary partition of Ri,j,0 into
disjoint subsets Si,j,l , l ∈ Li,j , with Si,j,l ⊂ Yi,j,l for all l.
Let l ∈ Li,j and H ∈ H. If Yi,j,l is not contained in H, then the number
of incidences between Si,j,l and this hypersurface is bounded by card(Yi,j,l ∩ H).
From Bézout’s inequality, we deduce that
(
deg(H) deg(Yi,j,l ) if Yi,j,l 6⊂ H,
(4.43)
I(Si,j,l , {H}) ≤
card(Si,j,l )
if Yi,j,l ⊂ H.
The hypothesis (b) implies that, for each l, there are at most 3 hypersurfaces in H
containing Yi,j,l . It follows from (4.43) that
X X
I(Ri,j,0 , H) =
I(Si,j,l , {H})
l∈Li,j H∈H

=O

X


X
deg(Yi,j,l ) + 3
card(Si,j,l )

l,H

l

= O(n deg(Yi,j ) + card(Ri,j,0 )).

(4.44)

By Bézout’s inequality, deg(Yi,j ) ≤ ∆i,j Fi,j . Using (4.44),

 X
X

[
X
I P ∩ Yi,j , H =
I(Ri,j,0 , H) = O
n∆i,j Fi,j +
card(Ri,j,0 ) . (4.45)
i,j

i,j

i,j

i,j

The first sum in the right-hand side of (4.45) appears in (4.38) and is already
accounted
S for in (4.39). By construction, the family of sets {Ri,j,0 }i,j is a partition
of P ∩ i,j Yi,j . Therefore, the sum of their cardinalities is bounded by m. Hence,


[

k−1
3
(4.46)
I P∩
Yi,j , H = O m1− 4k−1 n1− 4k−1 + m + n .
i,j

The statement now follows by summing up the contributions from (4.8), (4.21),
(4.42) and (4.46).

We close this paper by proposing the next conjecture on the number of pointhypersurfaces incidences in higher dimension.
Conjecture 4.1. Let d, k, c ≥ 1, and let P be a finite set of points of Rd and H a
finite set of hypersurfaces of Cd satisfying the following conditions:
(a) the degrees of the hypersurfaces in H are bounded by c;
(b) the intersection of any family of d distinct hypersurfaces in H is finite;

22

BASU AND SOMBRA

(c) for any subset of k distinct points in P, the number of hypersurfaces in H
containing them is bounded by c.
Set m = card(P) and n = card(H). Then
k−1

d−1

I(P, H) = Od,k,c (m1− dk−1 n1− dk−1 + m + n).
This conjecture is suggested by the bound that follows from the first level of the
polynomial partitioning method applied to this problem. It contains the statements
of the Szemerédi-Trotter theorem 1.4, the results of Zahl and Kaplan, Matoušek,
Sharir and Safernová in three dimensions [Zah13, KMSS12], and Theorem 1.5.
Concurrently with this paper, a proof of a weaker version of this conjecture, with
an extra factor of mε in the bound, has appeared in [FPS+ 14].
References
[BB12]

S. Barone and S. Basu, Refined bounds on the number of connected components of sign
conditions on a variety, Discrete Comput. Geom. 47 (2012), 577–597. 4, 9
[BB13]
S. Barone and S. Basu, On a real analogue of Bezout inequality and the number of
connected components of sign conditions, ArXiv e-prints (2013). 4, 9
[BPR06] S. Basu, R. Pollack, and M.-F. Roy, Algorithms in real algebraic geometry, second ed.,
Algorithms Comput. Math., vol. 10, Springer-Verlag, 2006. 10
[CEG+ 90] K. Clarkson, H. Edelsbrunner, L.J. Guibas, M. Sharir, and E. Welzl, Combinatorial
complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom.
5 (1990), 99–160. 1
[Cha89]
M. Chardin, Une majoration de la fonction de Hilbert et ses conséquences pour
l’interpolation algébrique, Bull. Soc. Math. France 117 (1989), 305–318. 3, 7
[CP99]
M. Chardin and P. Philippon, Régularité et interpolation, J. Algebraic Geom. 8 (1999),
471–481. 3, 7
[ES11]
G. Elekes and M. Sharir, Incidences in three dimensions and distinct distances in the
plane, Combin. Probab. Comput. 20 (2011), 571–608. 1
[FPS+ 14] J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl, A semi-algebraic version of
Zarankiewicz’s problem, e-print arXiv:1407.5705v1, 2014. 4, 22
[Ful84]
W. Fulton, Intersection theory, Ergeb. der Math. und ihrer Grenzgebiete, vol. 3,
Springer-Verlag, 1984. 4
[GH78]
Phillip Griffiths and Joseph Harris, Principles of algebraic geometry, WileyInterscience [John Wiley & Sons], New York, 1978, Pure and Applied Mathematics.
MR 507725 (80b:14001) 19
[GK10]
L. Guth and N. Katz, On the Erdős distinct distance problem in the plane, e-print
arXiv:1011.4105v3, 2010. 1, 2, 11, 13
[Har77]
R. Hartshorne, Algebraic geometry, Graduate Texts in Math., vol. 52, Springer-Verlag,
1977. 16
[KMS12] H. Kaplan, J. Matoušek, and M. Sharir, Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique, Discrete Comput.
Geom. 48 (2012), 499–517. 1
[KMSS12] H. Kaplan, J. Matoušek, M. Sharir, and S. Safernová, Unit distances in three dimensions, Combinat. Probab. Comput. 21 (2012), 597–610. 2, 3, 4, 11, 13, 22
[Loj91]
Stanislaw Lojasiewicz, Introduction to complex analytic geometry, Birkhäuser Verlag,
Basel, 1991, Translated from the Polish by Maciej Klimek. MR 1131081 (92g:32002)
19
[Mil64]
J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964),
275–280. 2, 9
[MS14]
J. Matousek and Z. Safernova, Multilevel polynomial partitions and simplified range
searching, ArXiv e-prints (2014). 3
[Nes84]
Yu. V. Nesterenko, Estimates for the characteristic function of a prime ideal, Mat.
Sb. (N.S.) 123(165) (1984), 11–34. 7
[PO49]
I. G. Petrovskiı̆ and O. A. Oleı̆nik, On the topology of real algebraic surfaces, Izvestiya
Akad. Nauk SSSR. Ser. Mat. 13 (1949), 389–402. 2, 9

PARTITIONING ON VARIETIES AND POINT-HYPERSURFACE INCIDENCES

[PS98]
[She14]
[Som14]

[ST83]
[ST12]
[Tho65]

[Zah13]

23

J. Pach and M. Sharir, On the number of incidences between points and curves, Combin. Probab. Comput. 7 (1998), 121–127. 3
A. Sheffer, Incidences in d-dimensional spaces, two blogs posted at http://
adamsheffer.wordpress.com, 2014. 4
M. Sombra, Bounds for the Hilbert function of polynomial ideals, talk at the IPAM
workshop “Tools from Algebraic Geometry”, https://www.ipam.ucla.edu/schedule.
aspx?pc=ccgws2, 2014. 4, 7
E. Szemerédi and W. T. Trotter, Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392. 3
J. Solymosi and T. Tao, An incidence theorem in higher dimensions, Discrete Comput.
Geom. 48 (2012), 255–280. 1
R. Thom, Sur l’homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), Princeton Univ. Press,
1965, pp. 255–265. 2, 9
J. Zahl, An improved bound on the number of point-surface incidences in three dimensions, Contrib. Discrete Math. 8 (2013), 100–121. 2, 3, 4, 11, 13, 22

Department of Mathematics, Purdue University. West Lafayette, IN 47906, U.S.A.
E-mail address: sbasu@math.purdue.edu
URL: http://www.math.purdue.edu/~sbasu
ICREA & Departament d’À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

