THE SZEMEREDI-TROTTER CELL DECOMPOSITION

TERENCE TAO

Abstract. Some notes on the cell decomposition lemma of Szemeredi and Trotter.

1. Introduction

The purpose of this note is to prove the following cell decomposition lemma of Szemeredi and Trotter.

Theorem 1.1. Let r > 0 be a number, and μ be a positive compactly supported measure in R^{2} with total mass μ(R^{2}) ≥ r, and the property that μ(S) < r for all squares S of sufficiently small side-length.

Then there exists a finite collection {S_{i}} of disjoint open squares in the plane such that μ(S_{i}) ∼ r for each i, and μ(⋃_{i} S_{i}) ∼ μ(R^{2}).

Proof By a random translation argument we may assume that μ(∂S) = 0 for all dyadic squares S. We also assume that there exists a large dyadic square S_{max} which contains the support of μ. Henceforth all dyadic squares are implicitly assumed to be contained in S_{max}.

We consider the empty set to be the unique dyadic square of side-length 0, and call it the empty square. The empty square is of course a sub-square of every square.

We define certain dyadic squares to be black by the following inductive procedure:

Definition 1.2. A dyadic square S is said to be black if μ(S\S′) > r for all black squares S′ ⊊ S.

Thus, for instance, the empty square is automatically black.

We now observe the following properties of black squares.

If S is a non-empty black square, then μ(S) > r.  (1)

If S, S′ are dyadic squares, we define S ∨ S′ to be the smallest dyadic square containing both S and S′. From (1) and Definition 1.2 we see

The set of black squares is closed under ∨ .  (2)

As an easy consequence of (2) and Definition 1.2 we have

Lemma 1.3. If S is a dyadic square, then there is a unique maximal black subsquare c(S) of S, and μ(S\c(S)) ≤ r.

We call c(S) the core of S. Since μ(S_{max}) > r, we see that c(S_{max}) must be non-empty. In particular, we have at least one non-empty black square.

If S is a black square, define S_{1}, …, S_{4} to be the four immediate sub-squares of S. We define the shell s(S) of S to be

s(S) = ⋃_{i=1}^{4} S_{i}\c(S_{i}).

From Lemma 1.3 we see that

μ(s(S)) ≤ 4r.  (3)

We say that a black square S is singular if at most one of the cores c(S_{i}) is nonempty. From Definition 1.2 we see that

μ(s(S)) > r  (4)

for singular S.

Let X be the union of the s(S), where S ranges over all the singular black squares. We now claim that

4μ(S ∩ X) − μ(S\X) > 4r  (5)

for all non-empty black squares S.

We prove (5) by induction on the side-length of S. Suppose (5) has been shown for all non-empty black squares shorter than S. We divide into several cases, depending on how many of the c(S_{i}) are empty.

If all the c(S_{i}) are empty, then S is singular, and (5) follows from (4).

Now suppose all but one of the c(S_{i}) are empty, say c(S_{1}) is non-empty. Then S is still singular; by applying the induction hypothesis to c(S_{1}) we obtain (5).

Finally, assume at least two of the c(S_{i}) are non-empty. Applying the induction hypothesis to each of them, adding up (so we get at least 8r on the right-hand side), and then subtracting s(S) using (3), we obtain (5).

In particular, by applying (5) to S = c(S_{max}) we see that

μ(X) ≥ \frac{1}{5}μ(c(S_{max})) + \frac{4}{5}r;

by Lemma 1.3 we thus have

μ(X) ∼ μ(R^{2}).

The set X consists of disjoint shells s(S), each of which contains between r and 4r points. Since s(S) is equal to a dyadic square with at most four dyadic sub-squares removed, one can check that it can be covered by O(1) squares. The Lemma then follows from a pigeonholing argument, choosing for each s(S) the square which contains the most measure.

We can apply the lemma to the case when μ is a sum of delta masses, to obtain

Corollary 1.4. Let P be a finite set of points with cardinality at least r. Then there exists a disjoint collection of open squares {S_{i}} each containing ∼ r points from P, and such that ⋃ S_{i} contains a positive fraction of the points in P.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu