Chapter 1

The

√

n theory

1. Erd˝ os’ original argument

How does one prove that any set, P , of size n determines many dis-

tances? Let us start in two dimensions. We will begin by giving

two proofs of the following theorem. The first proof was originally

published by Erd˝ os in 1946.

Theorem 1.1 (Erd˝ os [12]). Suppose that d = 2 and #P = n. Then

#Δ(P ) n

1

2

.

1st proof. Choose a point, p0, and draw circles around it that each

contain at least one point of P . Continue drawing circles around p0

until all the points in P lie on a circle of some radius centered at

p0. We will refer to this procedure as covering the points of P by

circles centered at p0. We can think of each circle as a level set, or

a set of points that have the same value for some function. In this

case, the function is the distance from the point p0. Suppose that we

have drawn t circles. This means that we can be assured that there

are at least t different distances between points in P and p0. If t is

greater than n

1

2

, then we are already doing very well. But what if

t happens to be small? Note that at least one of the t circles must

contain at least n/t points,1 by the pigeonhole principle. Draw the

1Actually,

this would be

n−1

t

points, but since

n−1

t

≈

n

t

, we will continue with

the simpler notation. This may seem annoying, but it is done intentionally to keep the

most important information at the forefront.

7

http://dx.doi.org/10.1090/stml/056/02