UNIFORMLY DISTRIBUTED DISTANCES: A GEOMETRIC APPLICATION OF JANSON’S INEQUALITY

JÁNOS PACH AND JOEL SPENCER

Abstract. Let d_{1} ≤ d_{2} ≤ … ≤ d\binom{n}{2} denote the distances determined by n points in the plane. It is shown that min ∑_{i}(d_{i+1}−d_{i})^{2} = O(n^{−6/7}), where the minimum is taken over all point sets with minimal distance d_{1} ≥ 1. This bound is asymptotically tight.

1. A problem of Erdős on distance gaps

Consider n points in the plane with minimum distance at least one. List the m = \binom{n}{2} distances between them in increasing order: d_{1} ≤ d_{2} ≤ … ≤ d_{m}. The numbers d_{i+1} − d_{i} will be called distance gaps. Erdős raised the following problem. Determine or estimate

f(n) = min ∑_{1≤i<\binom{n}{2}}(d_{i+1} − d_{i})^{2},  (1)

where the minimum is taken over all n-element point sets with minimum distance one. In particular, he asked if this sum can be made arbitrarily small.

This choice of function to be minimized may at first appear to be capricious. Suppose, however, that we fix d_{1} = 1 (which we may assume by a simple scaling argument) and the diameter D = d_{m}. Then if the numbers d_{i} could be chosen arbitrarily, ∑_{1≤i<m}(d_{i+1} − d_{i})^{2} would attain its minimum when the d_{i} are equally spaced. We have

∑_{1≤i<m}(d_{i+1} − d_{i})^{2} ≥ (m − 1)^{2}(\frac{D − 1}{m − 1})^{2} = Ω(D^{2}/n^{2}).  (2)

The geometric constraints make it impossible to achieve perfectly even spacing. It was shown in [EMPS91] that the number of distances belonging to the interval

[D − 1, D] is at most O(D^{3/2}). So even if these distances are evenly spaced, the gaps between them contribute at least Ω(D^{−3/2}) to the sum ∑(d_{i+1} −d_{i})^{2}. Combining this with (2), we obtain

Supported by NSF grant CCR-94-24398, PSC-CUNY Research Award 663472 and OTKA-T-020914. This paper was partly written while Pach was visiting MSRI Berkeley, as part of the Convex Geometry program.

f(n) ≥ min_{D} (Ω(D^{2}/n^{2}) + Ω(D^{−3/2})) = Ω(n^{−6/7}).  (3)

Our main objective is to show that this bound is asymptotically tight.

Theorem 1. There exists a set of n points in the plane with minimum distance at least one such that the distances d_{i} determined by them satisfy

∑_{1≤i<\binom{n}{2}}(d_{i+1} − d_{i})^{2} ≤ cn^{−6/7},

where c is an absolute constant.

It follows from (3) that the diameter D of such a point set must be approximately n^{4/7} and that the interpoint distances must be fairly uniformly distributed in the interval [1, D]. Our construction described in Section 4 is based on a Poisson process. For the analysis, we use the “No Bonds Theorem” (Section 3), which is a continuous version of Janson’s Inequality (Section 2). Sections 5–6 contain the details of the proof of Theorem 1.

2. Janson’s inequality

Let X be a finite underlying set, and let P be a random subset of X, whose elements are chosen independently with probability Pr[x ∈ P] = p_{x}. Let {S_{i} : i ∈ I} be a system of subsets of X, and let A_{i} denote the event that S_{i} ⊆ P. If S_{i} ∩ S_{j} = ∅ then A_{i} and A_{j} are independent. Let

ν = ∑ Pr[A_{i} ∧ A_{j}],

where the sum is taken over all unordered pairs i ≠ j with S_{i} ∩ S_{j} ≠ ∅, and let

M = ∏_{i∈I} Pr[\overline{A}_{i}] = ∏_{i∈I}(1 − Pr[A_{i}]).

Janson’s Inequality [J90]. If Pr[A_{i}] < ε for every i ∈ I, then

M ≤ Pr[∧_{i∈I} \overline{A}_{i}] ≤ Me^{ν/(2−2ε)}.

Let G be a finite graph with vertex set V (G) and edge set E(G). We apply Janson’s Inequality in the specific case when X = V (G) and {S_{i} : i ∈ I} = E(G), i.e., |S_{i}| = 2 for every i. Then

M = ∏_{{x,y}∈E(G)}(1 − p_{x}p_{y}),

and ν is the expected number of “vees” (paths of length two) in G|_{P}, the subgraph of G induced by P.

Corollary. Assume that for every edge {x, y} of a graph G, p_{x}p_{y} ≤ ε. Then,

M ≤ Pr[G|_{P} is empty] ≤ Me^{ν/(2−2ε)}.

Note that if max_{x∈V (G)} p_{x} is small, then M can be well approximated by

∏_{{x,y}∈E(G)} e^{−p_{x}p_{y}} = e^{−μ},

where

μ = ∑_{{x,y}∈E(G)} p_{x}p_{y}

is the expected number of edges in G|_{P}.

3. Poisson processes

Now we extend the Corollary to the continuous cased to be used in the sequel. Let X ⊂ IR^{2} be a bounded Jordan measurable set, and let ∼ be a symmetric binary

relation (graph) on X such that {(x, y) : x ∼ y} is a Jordan measurable subset of IR^{2}×IR^{2}. If x ∼ y for some x, y ∈ X, then they are said to form a bond. Furthermore, let φ be a countably additive finite measure on the Borel subsets of X, defined by

φ(Y) = ∫_{Y} ρ(x)dx,

where ρ : X → [0, +∞), the density function of φ, is Riemann integrable.

Let P ⊂ X be a random multiset given by a Poisson process associated with the measure φ. More precisely, P is a random variable whose values are almost surely unordered i-tuples of X (possibly with repetition) for some non-negative integer i such that

Pr[|P | = i] = \frac{φ^{i}(X)}{i!} · e^{−φ(X)} (i = 0, 1, 2, …),

and for a fixed i, P can be obtained by selecting i points from X independently with uniform distribution with respect to φ and disregarding their order. It is now easy to check that for any Borel set Y ⊆ X,

Pr[|P ∩ Y | = i] = \frac{φ^{i}(Y)}{i!} · e^{−φ(Y)} (i = 0, 1, 2, …),  (4)

where |P ∩ Y | counts the number of points of P belonging to Y with multiplicities. In particular, the expected value of |P ∩ Y | is equal to φ(Y). Moreover, if Y_{1} and Y_{2} are disjoint then |P ∩ Y_{1}| and |P ∩ Y_{2}| are independent random variables.

Let B and V denote the number of bonds and the number of “vees” formed by the elements of P, respectively, i.e.,

B = | {{x, y} : x, y ∈ P, x ∼ y} |,
V = | {(x, {y, z}) : x, y, z ∈ P, y ≠ z, and x ∼ y, x ∼ z} |,

and set μ = E[B], ν = E[V].

Theorem 2. (No Bonds Theorem) Let P ⊂ X be a random multiset obtained by a Poisson process associated with the measure φ, and let B denote the number of bonds between elements of P.

Then, with the above notations and assumptions,

e^{−μ} ≤ Pr[B = 0] ≤ e^{−μ+ν}.

Proof: For a fixed n, place a mesh X_{n} = {(i/n, j/n) : i, j ∈ ZZ} of sidelength n in the plane, and let P_{n} be a random multisubset of X_{n} obtained by the Poisson process associated with the measure

φ_{n}(Y) = ∑_{(\frac{i}{n} , \frac{j}{n})∈Y} φ ([\frac{i}{n}, \frac{i + 1}{n}] × [\frac{j}{n}, \frac{j + 1}{n}])

for any finite subset Y ⊆ X_{n}. If Y consists of a single element x ∈ X_{n} then, by (4),

Pr[x ∈ P_{n}] = ∑_{i=1}^{∞} \frac{φ_{n}^{i}(x)}{i!} · e^{−φ_{n}(x)} = 1 − e^{−φ_{n}(x)}.

Moreover, the events x ∈ P_{n} are independent for all x ∈ X_{n}.

Let G_{n} denote the graph on the vertex set X_{n}, whose two points x, y ∈ X_{n} are joined by an edge if and only if x ∼ y. Furthermore, let B_{n} denote the number of bonds formed by elements of P_{n}, where each bond is counted only once. It follows from the Corollary in the last section that

M_{n} ≤ Pr[B_{n} = 0] ≤ M_{n}e^{ν_{n}},  (5)

where

M_{n} = ∏_{{x,y}∈E(G_{n})}(1 − Pr[x ∈ P_{n}] Pr[y ∈ P_{n}]) ,

ν_{n} = ∑ ; \begin{matrix}(x, \{y, z\}) : \\ xy, xz ∈ E(G_{n}), y ≠ z \end{matrix}Pr[x ∈ P_{n}] Pr[y ∈ P_{n}] Pr[z ∈ P_{n}].

Notice that, as n tends to infinity,

Pr[x ∈ P_{n}] = 1 − e^{−φ_{n}(x)} = 1 − exp (− ∫_{x+[0,1/n]^{2}} ρ(x)dx) → 0

uniformly for all x. Since ρ is Riemann integrable,

lim_{n→∞} M_{n} = lim_{n→∞} exp (− (1 + o(1)) · ∑_{{x,y}∈E(G_{n})}φ_{n}(x)φ_{n}(y))

= exp (−\frac{1}{2} ∫_{x∈X} ∫ \begin{matrix}y ∈ X \\ y ∼ x \end{matrix} ρ(x)ρ(y)dydx) = e^{−μ},

and

lim_{n→∞} ν_{n} = lim_{n→∞} (1 + o(1)) · ∑ ; \begin{matrix}(x, \{y, z\}) : \\ xy, xz ∈ E(G_{n}), y ≠ z \end{matrix}φ_{n}(x)φ_{n}(y)φ_{n}(z)

= \frac{1}{2} ∫_{x∈X} ∫ \begin{matrix}y ∈ X \\ y ∼ x \end{matrix} ∫ \begin{matrix}z ∈ X \\ z ∼ x \end{matrix} ρ(x)ρ(y)ρ(z)dzdydx = ν.

It remains to show that

lim_{n→∞} Pr[B_{n} = 0] = lim_{n→∞} Pr[B = 0],

and then the theorem follows from (5).

By definition, φ_{n}(X_{n}) = φ(X) = ∫_{X} ρ(x)dx. Hence, in view of (4),

Pr[B_{n} = 0] = ∑_{i=0}^{∞} Pr [B_{n} = 0 | |P_{n}| = i] Pr [|P_{n}| = i]

= ∑_{i=0}^{∞} Pr [B_{n} = 0 | |P_{n}| = i] · \frac{φ^{i}(X)}{i!} · e^{−φ(X)},

Pr[B = 0] = ∑_{i=0}^{∞} Pr [B = 0 | |P | = i] · \frac{φ^{i}(X)}{i!} · e^{−φ(X)}.

It suffices to verify that for any fixed i,

lim_{n→∞} Pr [B_{n} = 0 | |P_{n}| = i] = Pr [B = 0 | |P | = i] .  (6)

Restricting P_{n} (and P) to the case |P_{n}| = i (and |P | = i), their points are distributed on X_{n} (on X) independently from each other and uniformly with respect to φ_{n} (φ, respectively). Thus, Pr [B = 0 | |P | = i] can be expressed as ∫ ρ(x_{1}) … ρ(x_{i})dx_{1} … dx_{i} over a Jordan measurable subset of X × … × X ⊆ IR^{2i}, and Pr [B_{n} = 0 | |P_{n}| = i] will approximate it with arbitrary precision, as n → ∞. This proves (6), and hence the theorem. □

4. Outline of the upper bound construction

The aim of this section is to sketch a probabilistic construction for the proof of Theorem 1. The details will be worked out in the next two sections.

As we have indicated in the last paragraph of Section 1, any O(n)-element point set that satisfies the inequality in Theorem 1 must have diameter Θ(n^{4/7}). All of our points will be chosen from the closed disk of radius n^{4/7} around the origin (0, 0) ∈ IR^{2}.

The construction consists of three parts (see Figure).

Figure

Step 1. Define a point set P_{1} by a Poisson process on the rectangle

X_{1} = {(x, y) : |x| ≤ n^{3/7}, |y| ≤ 0.99n^{4/7}}

with constant density function ρ(x, y) ≡ ε, where ε is a small positive number (ε = 10^{−3} will do). If two elements of P_{1} are at distance less than one, delete both of them. (Subsection 5.1 and Section 6.)

Step 2. Define a point set P_{2} by a Poisson process with constant density ε on the region X_{2} given by the polar coordinates

{(r, θ) : 0.9n^{4/7} < r < n^{4/7} − 1, min(|θ|, |θ − π|) < 0.5(n^{4/7} − r)^{−1/4}}.

As in the previous step, delete every pair of points whose distance is less than one. (Subsection 5.2.)

Step 3. We give an explicit construction P_{3} of points on the circle of radius n^{4/7},

{(x, y) : |x|^{2} + |y|^{2} = n^{8/7}},

with minimum distance at least one. (Subsection 5.3.)

Note that the distance between any two points belonging to different P_{i}’s (i = 1, 2, 3) is larger than one. We will show that the number of points in P = P_{1} ∪P_{2} ∪P_{3} is almost surely O(n) and, with probability at least 1/2, the sum of the squares of the distance gaps determined by them satisfies ∑(d_{i+1} − d_{i})^{2} = O(n^{−6/7}).

First we need some terminology. Let us classify all real numbers between 1 and D = 2n^{4/7} (the diameter of our construction). A number t is said to be

moderate if  1 ≤ t ≤ 1.96n^{4/7},
large  if 1.96n^{4/7} < t ≤ D − 3,
extra large if  D − 3 < t ≤ D.

For every j, 1 ≤ j < D = 2n^{4/7} and for all k = 0, 1, 2, …, divide the interval [j, j + 1) into 2^{k} equal subintervals of length 2^{−k}. That is, let

I_{jkl} = [j + (l − 1)2^{−k}, j + l2^{−k}), 1 ≤ l ≤ 2^{k}.

In the sequel, these intervals will be called canonical. Obviously, any interval I ⊂ [1, D) with |I| ≤ 1 has a canonical subinterval

I_{jkl} ⊆ I satisfying |I_{jkl}| ≥ \frac{|I|}{4},

where |I| denotes the length of I.

We say that an interval I is empty if our point set P has no pair of points whose distance belongs to I. Our goal is to show that with large probability the sum of the squares of the distance gaps determined by P is small. We will see that our construction has no distance gaps longer than one. Since for any two consecutive distances, d_{i} and d_{i+1}, (d_{i}, d_{i+1}) is an empty interval, we have

∑_{1≤i<\binom{n}{2}}(d_{i+1} − d_{i})^{2} ≤ 4^{2} · ∑ ; I_{jkl} empty ; canonical |I_{jkl}|^{2}.  (7)

That is why in the rest of the paper we will concentrate on establishing upper bounds for the expected value

E [ ∑ ; I_{jkl} empty ; canonical |I_{jkl}|^{2}] = ∑_{I_{jkl} canonical} |I_{jkl}|^{2} Pr[I_{jkl} is empty].  (8)

5. Bounding the distance gaps

5.1. Moderate distances. First we estimate the part of (8), where the sum is taken over all canonical intervals I_{jkl} for which j is moderate, and the point set is the set P_{1} defined by a Poisson process in the rectangle X_{1}, as described in Step 1 above. The expected number of elements of P_{1} is ε Area(X_{1}) = 3.96εn = Θ(n).

Fix a canonical interval I = I_{jkl} with 1 ≤ j ≤ 1.96n^{4/7}. We want to apply the No Bond Theorem to the case when a pair of points x, y ∈ P_{1} forms a bond if |y −x| ∈ I. Then the expected number of bonds and the expected number of “vees” satisfy

μ = \frac{1}{2} ∫_{x∈X_{1}} ∫ \begin{matrix}y ∈ X_{1} \\ |y − x| ∈ I \end{matrix} ε^{2}dydx = Θ(ε^{2}n min(j, n^{3/7})2^{−k}),

ν ≤ ∫_{x∈X_{1}} ∫ \begin{matrix}y ∈ X_{1} \\ |y − x| ∈ I \end{matrix} ∫ \begin{matrix}z ∈ X_{1} \\ |z − x| ∈ I \end{matrix} ε^{3}dzdydx = Θ(ε^{3}n min(j^{2}, n^{6/7})2^{−2k}).

Thus, by the No Bond Theorem,

Pr[I is empty] ≤ e^{−μ/2} ≤ exp (−Ω(ε^{2}n min(j, n^{3/7})2^{−k})) ,

whenever |I| = 2^{−k} ≤ 1/ min(j, n^{3/7}). In particular,

Pr[I is empty] ≤ exp (−Ω(ε^{2}n^{3/7}))  (9)

holds when |I| = 2^{−k} is roughly equal to n^{−4/7}, and hence (9) is valid for k ≤ (4/7) log_{2} n.

Therefore, the total contribution to (8) of all canonical intervals I_{jkl} for which j is moderate,

∑_{j moderate} |I_{jkl}|^{2} Pr[I_{jkl} is empty]

= ∑_{j=1}^{1.96n^{4/7}} ∑_{k=0}^{\frac{4}{7} log n} ∑_{l=1}^{2^{k}} 2^{−2k} Pr[I_{jkl} is empty]

+ ∑_{j=1}^{1.96n^{4/7}} ∑_{k> \frac{4}{7} log n} ∑_{l=1}^{2^{k}} 2^{−2k} Pr[I_{jkl} is empty]

≤ 1.96n^{4/7} (\frac{4}{7} log n + 1) exp (−Ω(ε^{2}n^{3/7}))

+ ∑_{j=1}^{1.96n^{4/7}} ∑_{k≥ \frac{4}{7} log n} 2^{−k} exp (−Ω(ε^{2}n min(j, n^{3/7})2^{−k}))

≤ exp(−Ω(n^{3/7})) + ∑_{j=1}^{1.96n^{4/7}} O (\frac{1}{ε^{2}n min(j, n^{3/7})}) = O(n^{−6/7}).

Here we used the fact that the sum over k can be majorated by contsant times its largest term.

5.2. Large distances. One can apply a similar argument to estimate the contribution of those canonical intervals I = I_{jkl} to (8), for which j is large. Now we have to consider the Poisson process P_{2} described in Step 2 (see the previous section). Clearly, the expected number of points of P_{2} is equal to

εArea(X_{2}) = 2ε ∫_{0.9n^{4/7}}^{n^{4/7}−1} 0.5(n^{4/7} − r)^{−1/4}rdr = Θ(εn).

Fix a canonical interval I = I_{jkl} with 1.96n^{4/7} < j ≤ D − 3 = 2n^{4/7} − 3, and say that a pair of points forms a bond if their distance belongs to I. Just like in the previous subsection, some routine calculation shows that the expected number of bonds is

μ = Ω(ε^{2}n^{6/7}(D − j)^{5/4}2^{−k}).

The No Bond Theorem now implies that

Pr[I is empty] ≤ e^{−μ/2} ≤ exp (−Ω(ε^{2}n^{6/7}(D − j)^{5/4}2^{−k})) ,

whenever |I| = 2^{−k} ≤ n^{−4/7}. This yields

Pr[I is empty] ≤ exp (−Ω(ε^{2}n^{2/7})) ,

for every k ≤ (4/7) log_{2} n.

Therefore, the total contribution to (8) of all canonical intervals I_{jkl} for which j is large,

∑_{j large} |I_{jkl}|^{2} Pr[I_{jkl} is empty]

≤ ∑_{j=1.96n^{4/7}}^{2n^{4/7}−3} ∑_{k=0}^{\frac{4}{7} log n} ∑_{l=1}^{2^{k}} 2^{−2k} Pr[I_{jkl} is empty]

+ ∑_{j=1.96n^{4/7}}^{2n^{4/7}−3} ∑_{k≥ \frac{4}{7} log n} ∑_{l=1}^{2^{k}} 2^{−2k} Pr[I_{jkl} is empty]

≤ 0.04n^{4/7} (\frac{4}{7} log n + 1) exp (−Ω(ε^{2}n^{2/7}))

+ ∑_{j=1.96n^{4/7}}^{2n^{4/7}−3} ∑_{k≥ \frac{4}{7} log n} 2^{−k} exp (−Ω(ε^{2}n^{6/7}(D − j)^{5/4}2^{−k}))

≤ exp(−Ω(n^{2/7})) + ∑_{j=1.96n^{4/7}}^{D−3} O (\frac{1}{ε^{2}n^{6/7}(D − j)^{5/4}} ) = O(n^{−6/7}).

5.3. Extra large distances. Here we present an explicit (i.e., non-probabilistic) construction of a set P_{3} of O(n^{4/7}) points on the circle of radius n^{4/7} centered at the origin O. Let

P_{3} = {p_{s} : 0 ≤ s ≤ n^{4/7}/2} ∪ {q_{t} : 0 ≤ t ≤ n^{4/7}/2},

where, using polar coordinates (r, θ),

p_{s} = (n^{4/7}, 2sn^{−4/7}), q_{t} = (n^{4/7}, π + 2t(n^{−4/7} + 4n^{−8/7})).

For any t ≥ s, the clockwise angle p_{s}Oq_{t} is

π − 2(t − s)n^{−4/7} − 8tn^{−8/7}.

Thus, the angles p_{s}Oq_{t} (0 ≤ s ≤ t) are fairly densely distributed in the interval (π − 1/2, π); every closed subinterval of length 8n^{−8/7} contains at least one of them. Consider the distances corresponding to these angles. It is easy to see that they divide [2n^{4/7} − 3, 2n^{4/7}] into subintervals of length at most 15n^{−6/7}. Consequently, the sum of the squares of the distance gaps in this interval is at most 45n^{−6/7}, and

∑ ; I_{jkl} empty ; j extra large |I_{jkl}|^{2} = O(n^{−6/7}).  (10)

6. Excluding point pairs at distance less than one

So far we have focused on bounding (8), the expected value of the sum of the squares of the distance gaps determined by our random construction P_{1} ∪ P_{2} ∪ P_{3}. The deterministic part of the construction, P_{3}, satisfies the requirement that it has no two points at distance less than one, and it is also true that the distance between any two points belonging to different P_{i}’s is at least one. However, some of the distances induced by P_{1} and P_{2} may be shorter than one.

In this section, we will deal with this problem. Let P_{i}^{∗} denote the point set obtained from P_{i} by deleting every point x ∈ P_{i} for which there is another point y ∈ P_{i} with |y − x| < 1 (i = 1, 2). In fact, instead of (8), we need an upper bound on

∑_{I_{jkl} canonical} |I_{jkl}|^{2} Pr^{∗}[I_{jkl} is empty],

where Pr^{∗} denotes the probability that a given condition is satisfied for P_{1}^{∗} ∪ P_{2}^{∗} ∪ P_{3}, i.e., after the deletions have been carried out.

Let us concentrate on moderate distances, i.e., on the set P_{1}^{∗}. Fix again a canonical interval I = I_{jkl} with 1 ≤ j ≤ 1.96n^{4/7}. A pair of points {x, y} ⊆ P_{1} is said to form a bond if |y − x| ∈ I. A bond is called bad if there exists z ∈ P_{1} whose distance from x or from y is less than one. In this case, {x, y} ⊈ P_{1}^{∗}. Two bonds {x_{1}, y_{1}} and {x_{2}, y_{2}} are separated if their distance is at least 2. Let μ and ν denote the same as in 5.1.

Lemma 6.1. If k ≥ (4/7) log_{2} n, then the probability that there are at least μ/10 pairwise separated bonds is larger than 1 − e^{−μ/8}.

Proof: We prove the stronger statement that the probability that there is a maximal family F of pairwise separated bonds with |F| < μ/10 is smaller than e^{−μ/8}.

Indeed, this probability is at most

∑_{i< \frac{μ}{10}} ∑_{|F|=i} Pr[F is maximal family of separated bonds].

Since the expected number of i-tuples of bonds is μ^{i}/i!, the above sum cannot exceed

∑_{i< \frac{μ}{10}} \frac{μ^{i}}{i!} · max_{|F|< \frac{μ}{10}} Pr[F is maximal | F consists of bonds].  (11)

The conditional probabilities in the last expression can be bounded by the No Bond Theorem. Delete from X_{1} a unit disk around both points of each bond belonging to F, and restrict the Poisson process to the remaining set. The probability that F is maximal is equal to the probability that no bonds are formed under the restricted process. Hence, this probability is at most e^{−μ′+ν′}, where μ′ < μ and ν′ < ν are the expected number of bonds and “vees” in the restricted process, respectively. If k > (4/7) log_{2} n, then μ′ > μ/2 > 2ν. This yields that the conditional probability in (11) is at most e^{−μ′+ν} < e^{−μ/2+ν} < e^{−μ/4}. Therefore, (11) can be bounded from above by

∑_{i< \frac{μ}{10}} \frac{μ^{i}}{i!} e^{−μ/4} < e^{−μ/8},

as required. □

Lemma 6.2. The probability that there are at least μ/10 pairwise separated bad bonds is at most e^{−μ/8}.

Proof: The expected number of bad bonds is at most 2επμ, because for any bond, the probability that there is a point in the unit disk centered at one of its points is επ. If two point pairs are separated, then the events that they form bad bonds are independent. Thus, the probability that there exist μ/10 bad bonds is at most

\frac{(2επμ)^{μ/10}}{(μ/10)!} < (100ε)^{μ/10} < e^{−μ/8}.

□

It follows from Lemmas 6.1 and 6.2 that if j is moderate and k ≥ (4/7) log_{2} n, then the probability that P_{1}^{∗} contains two points whose distance belongs to I_{jkl} satisfies

Pr^{∗}[I_{jkl} is empty] < 2e^{−μ/8}.

Thus, using the same estimates as in 5.1, we obtain

∑_{j moderate} ∑_{k≥ \frac{4}{7} log n} ∑_{l=1}^{2^{k}} |I_{jkl}|^{2} Pr^{∗}[I_{jkl} is empty] = O(n^{−6/7}).  (12)

On the other hand, the probability that there exist a moderate j, k ≤ (4/7) log_{2} n, and l such that the distance of no two points of P_{1}^{∗} belongs to the canonical interval I_{jkl} is at most

O ( ∑_{j=1}^{1.96n^{4/7}} 2^{−(4/7) log n} Pr^{∗}[I_{j⌈(4/7) log n⌉l} is empty]) = exp(−Ω(n^{3/7})).

The above argument can also be applied to large distances. Then,

∑_{j large} ∑_{k≥ \frac{4}{7} log n} ∑_{l=1}^{2^{k}} |I_{jkl}|^{2} Pr^{∗}[I_{jkl} is empty] = O(n^{−6/7}),  (13)

and the probability that there exist a large j, k ≤ (4/7) log_{2} n, and l such that the distance of no two points of P_{2}^{∗} belongs to the canonical interval I_{jkl} is at most exp(−Ω(n^{2/7})).

Summarizing: With probability 1 − o(1), |P_{1}^{∗} ∪ P_{2}^{∗} ∪ P_{3}| ≤ |P_{1} ∪ P_{2} ∪ P_{3}| = O(n). With probability at least 1−exp(−Ω(n^{2/7})), for every canonical interval I_{jkl} for which j is moderate or large and k ≤ (4/7) log_{2} n, there is a pair of points in P_{1}^{∗} ∪ P_{2}^{∗} ∪ P_{3}, whose distance belongs to I_{jkl}. By (10), (12), and (13), the expected value of the sum of the squares of all other empty canonical intervals satisfies

E [ ∑ ; I_{jkl} empty j moderate or large k ≤ (4/7) log n|I_{jkl}|^{2} ] + ∑ ; I_{jkl} empty ; j extra large|I_{jkl}|^{2} = O(n^{−6/7}).

Hence, by Markov’s inequality, with probability at least 1/2, the sum of the squares of all canonical intervals will be O(n^{−6/7}). In view of (7), this implies that there exists a specific O(n)-element point set P_{1}^{∗} ∪ P_{2}^{∗} ∪ P_{3} with minimum distance one, for which the sum of the squares of the distance gaps is O(n^{−6/7}). This completes the proof of Theorem 1.

References

[EMPS91] P. Erdős, E. Makai, J. Pach, and J. Spencer, Gaps in difference sets, and the graph of nearly equal distances, in: The Victor Klee Festschrift, DIMACS Series, Vol. 4 (P. Gritzmann, B. Sturmfels, eds.), Amer. Math. Soc., Providence, 265–273.

[J90] S. Jansen, Poisson approximation for large deviations, Random Structures & Algorithms 1, 221–229.

János Pach, City College and Courant Institute, NYU, 251 Mercer Street, New York, NY 10012

  E-mail address: pach@cims6.nyu.edu

Joel Spencer, Courant Institute, NYU, 251 Mercer Street, New York, NY 10012

  E-mail address: spencer@cs.nyu.edu