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
Previous Page Next Page