Every finite point set P in the real plane carries a collection of
distinct distances at each of its pins x in P. Two questions attach to
this data. How few distinct distances can a single pin see, and how
many pins can be bad at once. The second question is the sharper one,
and the answer below is that bad pins can never occupy a positive
fraction of a large configuration.
For x in P, write
D_x(P) = { |y - x| : y in P, y != x }.
Erdos asked in 1957 whether some pin always sees at least n^(1 - eps)
distinct distances, for every fixed eps > 0. The question is Problem
16 of Some unsolved problems (Michigan Math J 4(3):291-300, 1957).
./erdos1957-unsolved-prob.pdf
"Let S be a finite point set in the plane, let N(S) denote
the number of different values which occur among the
distances, and f(n) the least value that N(S) can have.
It can be conjectured that f(n) > n^{1-eps} for large n
and, further, that there exists a point p_i at which more
than n^{1-eps} different values occur among the distances."
Some unsolved problems, Problem 16 (1957)
The theorem below proves a strictly stronger statement: at all but
o(n) pins the count reaches n^(1 - eps).
The right object to track is not just the count but the multiplicity
of any single distance at a pin. For distinct x, y in P define
k_P(x,y) = #{ z in P \ {x} : |z - x| = |y - x| }.
So k_P(x,y) counts every point at the same distance from x as y is,
including y itself. Different pairs use their own source point, and
two pairs with the same numerical distance but different sources are
treated separately.
For n >= 2 and s > 0 put
F_n(s) = sup_{ P subset R^2, |P| = n }
( #{ (x,y) in P^2 : x != y, k_P(x,y) >= n^s }
/ ( n (n - 1) ) ).
Theorem. For every fixed s > 0, F_n(s) -> 0 as n -> infinity.
The convergence is uniform: no separation, general position, or
coordinate hypothesis is imposed, and the constants only depend on s.
The exponent s is fixed; the theorem supplies no explicit rate of
decay.
Corollary. For every fixed eps > 0,
sup_{ P subset R^2, |P| = n }
( #{ x in P : |D_x(P)| < n^(1 - eps) } / n ) -> 0.
In particular every sufficiently large n-point planar set has a pin
determining at least n^(1 - eps) distinct nonzero distances.
Proof of the corollary. For eps >= 1 the assertion is trivial; every
pin with n >= 2 sees at least one distance. Suppose 0 < eps < 1 and
take s = eps/2. A pin with fewer than n^(1 - eps) distance classes
can place at most n^(1 - eps + s) neighbours in classes of size below
n^s, so it contributes at least n - 1 - n^(1 - eps/2) pairs counted
by F_n(s). If there are b such bad pins, then for all large n
b/n <= (n-1) F_n(eps/2) / ( n - 1 - n^(1 - eps/2) ) -> 0.
The bound is uniform in P.
The corollary is nearly sharp. If P consists of the vertices of a
regular polygon together with its centre, the centre sees a single
nonzero distance. Exceptional pins are unavoidable; the theorem only
says that such pins cannot fill a positive fraction of the
population.
History and external context. Erdos opened both the distinct-distance
and the repeated-distance questions in 1946.
./erdos1946-amm-distances-n.pdf
The original note introduces the quantity that later became the
object of study. Denote by f(n) the least number such that any set of
n points of the plane contains some point that determines at least
f(n) distinct distances to the remaining points. The note points out
that the integer square lattice provides sets for which the union of
all such distances has size O(n / sqrt(log n)). The present question
fixes one source and measures the count at that source. In that
reformulation the lattice is not the extremal example; a symmetric
configuration close to a regular polygon can make a single pin see
just one distance.
Guth and Katz proved that every planar n-point set determines at
least a constant times n / log n distinct distances.
./guth-katz-2015-annals.pdf
"In this paper, it is shown that a set of N points in R^2 has at
least c N/log N distinct distances, thus obtaining the sharp
exponent in a problem of Erdos."
On the Erdos distinct distance problem in the plane,
Ann. of Math. 181 (2015)
Their conclusion concerns the union over all sources; the pinned
version fixes the source and asks for the worst single-source count
in the same configuration.
Pinned bounds grew historically by combining incidence geometry with
progressively sharper counting. Solymosi and Toth obtained the order
n^(6/7).
./solymosi-toth-2001.pdf
"It is shown that every set of n points in the plane has an
element from which there are at least c n^{6/7} other elements
at distinct distances, where c > 0 is a constant."
Distinct Distances in the Plane, Discrete Comput. Geom.
25 (2001)
Katz and Tardos pushed every exponent below
(48 - 14 e) / (55 - 16 e) = 0.864137...
in their paper A new entropy inequality for the Erdos distance
problem.
./katz-tardos-2004.pdf
Each of these papers guarantees that some pin in every configuration
is good. The sharper pinned conjecture asks for order n / sqrt(log n)
distances at a pin; the introduction to Bisectors and pinned distances
documents the distinction between the real planar problem and
pinned-distance theorems over other fields.
./lund-petridis-2020.pdf
"Erdos also made a refinement of this conjecture. This
refinement is that among any set A of N points in R^2,
there must occur a point a in A such that the remaining
points of A are at Omega(N log^{-1/2}(N)) different
distances from a. This is often called the pinned
distances conjecture."
Bisectors and pinned distances, Discrete Comput. Geom.
64 (2020)
The almost-every-pin corollary above resolves the weak pinned
conjecture in the form in which it appears as Conjecture 4.7 of
Generalised Erdos distance theory on graphs.
./dewar-etal-2025-weak-pinned.pdf
Outline of the argument. Assume the theorem fails. Then a positive
density of ordered distinct pairs have sources whose distance fiber is
as large as n^s. Record these pairs as a directed graph, and let theta
be the limiting edge density. A deletion procedure on the graph forces
both a density bound from below and a fiber size bound from above,
giving good control of large and small subsets.
Work inside a number field K subset C that contains the coordinates of
every point. Write x = (u,v) and set Z_1(x) = u + iv and Z_2(x) = u -
iv, with i = sqrt(-1). The squared distance factors exactly:
|x - y|^2 = ( Z_1(y) - Z_1(x) ) ( Z_2(y) - Z_2(x) ).
The product formula in K, applied to both coordinates, balances the
logarithms of these differences across all places, so on a single
fiber the sum of the two coordinate depths is a fixed constant.
To turn logarithms of distances into integers, nested partitions are
built from randomly shifted square grids at each complex place. The
grid depth differs from the raw logarithmic depth by a small error
Delta whose distribution is independent of the pair and which has an
exponential tail. Replacing any cell with more than half the points by
its complement keeps the cell size balanced and produces an exact
additive identity: the total overlap of two distinct points, summed
over all levels, all coordinates and all places, equals a function of
the first point plus a function of the second point plus a constant.
That identity produces a nonnegative scale W, the expected overlap of
two distinct uniform points plus a correction for giant complements.
Two facts pin down W. The variance estimate compares the fiber law and
the uniform law cell by cell and shows that cells of size at most
n^(1-c) carry only o(W+1) of the overlap; the same variance estimate
compares the incoming-neighbour law at each target with the uniform
law.
Then W either stays bounded or grows without bound along some
subsequence. In the unbounded case, cells of mass bounded away from
zero define weighted trees; transporting mass along these trees uses a
classical distance formula for trees, and comparison of the fiber law
with the uniform law turns the fiber equation into an impossibility
for three independent uniform vertices. In the bounded case, one
complex embedding is normalized so that the two coordinate laws have
nonatomic weak limits; the variance estimate preserves the fiber
equation in the limit and yields a family of Mobius maps between the
two limits. A short order-statistics argument rules out any such
family when both limit laws are nonatomic. Both alternatives are
impossible, hence the theorem.
The proof of the main theorem begins. Assume for the rest of the
argument that the conclusion fails at some exponent: for at least one
positive t the numbers F_n(t) do not tend to zero. Define
Theta(t) = limsup_{n -> infinity} F_n(t),
s_* = sup { t > 0 : Theta(t) > 0 }.
Each F_n, and hence Theta, is nonincreasing. And F_n(t) = 0 vanishes
for t >= 1 because a distance class at a pin has at most n - 1
points. So 0 < s_* <= 1. Assuming the theorem fails means Theta(t) >
0 for some positive t, hence s_* > 0. Fix
0 < c < s_*/3,
max { c, (1-c) s_* } < s < s_*,
c < gamma < s,
choosing s to be a continuity point of Theta. Such an s exists
because a monotone function has at most countably many
discontinuities. Set theta = Theta(s) > 0; positivity follows from
s < s_* and monotonicity of Theta. All asymptotic estimates below are
with respect to the sequence of configurations constructed in the
next step; their constants may depend on (c, s, gamma, theta) but not
on n or on the configurations.
Two types of probability laws at a graph. Once the directed graph E
of large-fiber pairs is chosen, several probability measures attached
to it will appear repeatedly. The piece of terminology that makes
the pair laws usable is this: two edges lie in the same fiber when both share
their source and their squared distance. Write x_e for the source of
a fiber e, F_e subset of P minus {x_e} for its target set, and k_e =
|F_e|. Let d^-(y) denote the number of incoming edges at y.
The laws are these.
alpha: uniform probability measure on P.
pi: uniform on the n(n-1) distinct ordered pairs in P.
q: uniform on E, with source and target marginals q_X and q_Y.
mu_e: uniform on F_e.
rho_y: uniform on the incoming neighbours of y, defined when
d^-(y) > 0.
To sample q, choose a fiber e with probability k_e / |E| and then
choose y with law mu_e, setting x = x_e. Equivalently, sample y with
law q_Y and then x with law rho_y. These laws are attached to the
finite graph; the laws do not depend on any of the absolute values
introduced later.
The extraction of the graph from the failure of the theorem controls
not only its density and fiber sizes but also how much of a fiber can
sit inside a small subset of vertices. That last control is what lets
fibers be compared with the uniform distribution.
Tail lemma. If r_N -> s and M_N -> infinity, then
sup_{ m >= M_N } ( F_m(r_N) - theta )_+ -> 0,
where the supremum is over integers m >= 2 and (u)_+ = max { u, 0 }.
Proof. Fix eps > 0. Continuity of Theta at s gives delta > 0 with
Theta(s - delta) < theta + eps/2. By the definition of limsup, F_m(s
- delta) <= Theta(s - delta) + eps/2 for all large m. For all large
N, r_N >= s - delta, and every m >= M_N then lands in this range.
Monotonicity of F_m in its argument gives F_m(r_N) <= theta + eps.
Extremal graph proposition. Under the present supposition there is a
sequence of finite sets P subset of R^2 of real algebraic points,
with n = |P| -> infinity, and nonempty directed graphs E on P, with
these properties. Their densities d_n = |E| / [n (n-1)] tend to
theta, and every fiber has k_e >= n^(s - o(1)), uniformly in e. There
is a fixed constant B_0 such that, pointwise,
q <= B_0 pi, q_X, q_Y <= B_0 alpha,
(q_X + q_Y)/2 >= (1 - o(1)) alpha,
and
q_Y { y : d^-(y) < n^gamma } = O(n^(gamma - 1)) = o(1).
Put lambda_n = 1/log n. For every subset C subset of P, writing m =
|C| and p_e = mu_e(C),
E_e [ 1_C(x_e) p_e 1_{ p_e >= lambda_n } ]
<= (1 + o(1)) pi(C^2) when m > n^(1-c),
<= o(1) pi(C^2) when m <= n^(1-c).
All errors are uniform in vertices, fibers and subsets.
Proof of the proposition. Three steps: passing to a sequence of
algebraic configurations that preserves every distance equality;
deleting low-degree vertices and small fibers; and the subset
estimate.
Step 1. For fixed N, the numerator defining F_N(s) takes values in
the finite set {0, 1, ..., N(N-1)}, so it attains its maximum on some
configuration. Choose N -> infinity with F_N(s) -> theta and one
attaining configuration for each N.
That configuration can be replaced by one with real algebraic
coordinates without changing any distance class. Label its points
1, ..., N and write the coordinate variables as (u_i, v_i), with
D_{ij} = (u_i - u_j)^2 + (v_i - v_j)^2. Require D_{ij} > 0 for i <
j, and prescribe for every pair of unordered pairs either the
equality D_{ij} = D_{kl} or the disequality D_{ij} != D_{kl} that
holds in the original configuration. These are finitely many
polynomial conditions over Q: a disequality can be encoded as
(D_{ij} - D_{kl})^2 > 0. Their existential sentence holds over R, so
by transfer for real closed fields it holds over the real algebraic
numbers. The standard reference for real closed fields and their
model theory is Lecture 9 of Kuhlmann's notes.
./kuhlmann-2009-rcf-notes09.pdf
The resulting points are distinct and retain the exact
distance-equality pattern, so every fiber size is unchanged and the
value of F_N(s) is preserved. The real threshold N^s need not enter
the transferred system: it only compares against the integer class
sizes, which are preserved. No bound on the degrees or the heights of
the algebraic coordinates is imposed.
Step 2. On this algebraic configuration, keep every edge counted by
F_N(s). Each initial fiber has at least N^s edges. Put
K_N = N^s / log N,
f_N = log K_N / log N = s - (log log N) / log N,
m_0 = ceil(N / 2).
For all large N, f_N > 0. The tail lemma gives
b_N := max_{ m_0 <= m <= N } ( F_m(f_N) - theta )_+ -> 0.
Set
t_N = b_N + |F_N(s) - theta| + 1 / log N,
eta_N = sqrt(t_N),
so eta_N -> 0 and eventually theta - eta_N > 0.
Whenever a remaining nonempty fiber has fewer than K_N edges, discard
it. If the current vertex count is m and a vertex has combined in-
and out-degree below 2 (theta - eta_N) (m - 1), delete that vertex
and all its incident edges. Clean out small fibers after every vertex
deletion and continue until all degree lower bounds hold.
There are at most N(N-1)/N^s initial fibers. Restricting the vertex
set never splits a source-distance fiber, and each initial fiber can
be discarded at most once, costing fewer than K_N edges each. All
fiber cleanups together therefore cost at most N(N-1)/log N edges.
If the deletion process reaches m_0 vertices, write A_N = N(N-1) and
B_N = m_0(m_0 - 1). The vertex deletions cost fewer than
2 (theta - eta_N) sum_{ m = m_0+1 }^N (m - 1)
= (theta - eta_N) (A_N - B_N)
edges. After all cleanups, at least
F_N(s) A_N - (theta - eta_N) (A_N - B_N) - A_N / log N
edges remain. Their excess over (theta + b_N) B_N is at least
eta_N (A_N - B_N) - t_N A_N
= eta_N A_N ( 1 - B_N/A_N - eta_N ) > 0
for large N, because B_N/A_N -> 1/4. But every remaining edge has a
fiber of at least K_N = N^{f_N} >= m_0^{f_N} edges, whose density is
at most F_{m_0}(f_N) <= theta + b_N, a contradiction.
So the process stops on a set P of size n > m_0 with a graph E whose
fibers all have size at least K_N. Summing the degree lower bounds and
using the definition of b_N gives
theta - eta_N <= d_n <= F_n(f_N) <= theta + b_N.
The upper bound applies because K_N >= n^{f_N}. Thus d_n -> theta,
and k_e >= K_N >= n^{s - o(1)} uniformly in e.
Step 3. For every edge, q(x,y)/pi(x,y) = 1/d_n, so B_0 = 2/theta
works in the first inequality for large n. Summing over one
coordinate gives the marginal bounds. At every vertex the degree lower
bound gives
(q_X(x) + q_Y(x))/2
>= ((theta - eta_N)/d_n) alpha(x)
>= ((theta - eta_N)/(theta + b_N)) alpha(x)
= (1 - o(1)) alpha(x).
Only the sum of the two marginals is bounded below; separate lower
bounds are not needed. For targets of small incoming degree,
q_Y { y : d^-(y) < n^gamma }
<= n n^gamma / |E| = O(n^(gamma - 1)),
which is o(1) since gamma < s < 1.
Step 4. Define
T_n = lambda_n K_N = N^s / (log N log n).
Since N/2 < n <= N, there is a sequence delta_n -> 0 with T_n >=
n^{s - delta_n}; in particular T_n -> infinity. Multiplying the left
side of the subset estimate by |E| counts exactly the edges (x_e, y)
in C x C with |F_e cap C| >= lambda_n k_e. Every such pair satisfies
k_C(x_e, y) >= |F_e cap C| >= T_n.
A nonzero contribution therefore needs m - 1 >= T_n, because the
source sits in C and is excluded from its own distance class. Hence
all bounded subsets contribute zero for large n; the cases m = 0 and
m = 1 give zero at every n.
For m > n^{1-c}, the positive exponent s - delta_n gives T_n >=
n^{s - delta_n} >= m^{s - delta_n}. The tail lemma gives F_m(s -
delta_n) <= theta + o(1) uniformly in these sizes. Divide the pair
count by |E|:
E_e [ 1_C(x_e) p_e 1_{ p_e >= lambda_n } ]
<= ((theta + o(1))/d_n) (m(m-1)/(n(n-1)))
= (1 + o(1)) pi(C^2).
For m <= n^{1-c}, choose a fixed s' with s_* < s' < s/(1-c),
possible because s < s_* and c < s_*/3. For large n,
T_n >= n^{s - delta_n} >= n^{(1-c) s'} >= m^{s'}.
The definition of s_* gives Theta(s') = 0, so F_m(s') -> 0 as m ->
infinity. Every contributing subset has m >= T_n + 1, so
sup_{ m >= T_n + 1 } F_m(s') -> 0,
again only integer sizes considered. Dividing this pair count by |E|
gives o(1) pi(C^2) uniformly over all contributing small subsets; the
other subsets contribute zero. This also covers s' > 1, when the
corresponding pair count is identically zero.
From now on the sequence P and its graph E from the proposition are
fixed. In particular every k_e >= n^gamma for large n. The graph
and its sampling laws are now fixed.
The arithmetic model. The remaining proof is arithmetic. The two
coordinate maps and the nested grids are built now; the maps turn
logarithms of distances into sums of nonnegative overlaps.
Two coordinate maps. Take one algebraic configuration from the
extremal-graph proposition. Fix a number field K subset of C
containing all its coordinates and the imaginary unit i = sqrt(-1).
For a point x = (u,v) put
Z_1(x) = u + iv, Z_2(x) = u - iv.
Both maps are injective, because u and v are real in the chosen
embedding. At another complex embedding K -> C the two coordinates
need not be complex conjugates; their injectivity and the algebraic
factorisation are the only properties used. For distinct x, y the
squared distance factors exactly in K:
t(x,y) = ( Z_1(y) - Z_1(x) ) ( Z_2(y) - Z_2(x) ).
Place-by-place depth. Let v run over the places of K. At a finite
place above a prime p, use the absolute value extending |p|_p =
p^{-1}, and let sigma_v = [K_v : Q_p] / [K : Q]. At an archimedean
place v, all of which are complex since i is in K, use complex
modulus and sigma_v = 2/[K : Q]. The normalised product formula
(Milne, Algebraic Number Theory, Theorems 7.14-7.15 and Lemma 8.6)
reads
sum_v sigma_v log |z|_v = 0 (z in K, z != 0),
sum_{ v | infinity } sigma_v = 1.
./milne-ant-2020.pdf
The weights convert the norm-based finite absolute values and
squared complex moduli in that reference to the values used in this section,
after division by [K : Q]. Below, logarithms are natural.
For a fixed configuration only finitely many finite places make any
coordinate difference a nonunit, because each nonzero element of K
has nonzero valuation at only finitely many prime ideals.
At a place v, define the raw depths
i_j(x,y) = -log |Z_j(x) - Z_j(y)|_v, x != y, j = 1, 2.
The place is suppressed in the notation. On a fiber F_e with source
x_e and squared distance t_e, the factorisation yields
i_1(x_e, y) + i_2(x_e, y) = h_e, h_e = -log |t_e|_v,
y in F_e.
The number h_e does not depend on the choice of y in the fiber. This
is the fiber equation; it is the entire reason the proof works.
Nested grids at complex places. At a finite place put d_j(x,y) =
i_j(x,y). The ultrametric inequality makes d_j(x,y) >= r an
equivalence relation. At a complex place the same nesting is
obtained from random square grids, with a controlled error.
Independently of all vertex and fiber sampling, choose a uniformly
random orientation and xi uniform on [0, log 2). Grid side lengths
are l_m = e^xi 2^m for m in Z, with l_0 = e^xi in [1,2). Choose a
shift uniform modulo l_0 in each oriented axis. To obtain the shift
modulo l_{m+1} from that modulo l_m for m >= 0, add 0 or l_m with
probability 1/2 each, independently at every step and in each axis.
For m < 0 reduce the initial shift modulo l_m. Every shift is uniform
modulo its side length and the resulting half-open square grids are
nested. Use such a grid family for each coordinate j.
This recursive shift construction appears in Arora's polynomial-time
approximation scheme for Euclidean TSP, Section 2.1, in the form of
randomly shifted quadtree grids.
./arora1998-euclidean-tsp.pdf
For distinct points let d_j(x,y) denote minus the logarithm of the
smallest grid side at which the two images share a cell. Put
d_j(x,x) = +infinity and, for x != y,
Delta_j(x,y) = d_j(x,y) - i_j(x,y).
The three depth quantities play distinct roles.
i_j(x,y): raw logarithmic depth, -log |Z_j(x) - Z_j(y)|_v.
d_j(x,y): sharing depth in the nested hierarchy.
Delta_j(x,y): hierarchy error, d_j(x,y) - i_j(x,y).
Grid error lemma. At every complex place the depths are almost surely
finite on distinct pairs. The distribution of Delta_j(x,y) is
independent of the distinct pair, of the place and of the
configuration. Its finite mean is an absolute constant kappa, and
absolute constants C_0, b_0 > 0 satisfy
Pr( |Delta_j(x,y)| > u ) <= C_0 e^{-b_0 u} (u >= 0).
At finite places Delta_j = 0.
Proof. Write R > 0 for the separation of the two complex values and
(a,b) for their displacement along the oriented axes. At side length
l a uniform shift gives a sharing probability of
(1 - |a|/l)_+ (1 - |b|/l)_+.
Sharing is impossible if l < R/sqrt(2), while separation has
probability at most (|a| + |b|)/l <= sqrt(2) R/l. The separation
events shrink as the grids coarsen, with probabilities going to zero,
so almost surely the pair eventually shares a cell and there is a
smallest sharing scale.
Write Delta = d_j(x,y) + log R. A sharing side gives Delta <=
log sqrt(2). For u >= 0 let l be the largest grid side no larger than
R e^u, so l > R e^u / 2. On {Delta < -u} the pair is separated at
that side, so
Pr(Delta < -u) <= 2 sqrt(2) e^{-u}.
This proves the tail and a uniform first absolute moment.
For any real u the event {Delta >= u} is sharing at the largest side
l <= R e^{-u}. The law of l/R depends only on u, by the uniform
logarithmic phase, and the displacement direction relative to the
axes is uniform. The sharing formula therefore makes the entire law
of Delta independent of the pair. Only countably many random
variables and cell tests are used, so all these events are
measurable.
Removing the giant cell. Discard the null event on which any
distinct-pair depth is not finite. For a place and coordinate j let
Pi_j(r) denote the partition with sharing criterion d_j(x,y) >= r,
for r in R. These partitions are nested as r grows. Call a cell
giant if its size exceeds n/2, and denote such a cell, when it
exists, by G_j(r). Replace the giant by its complement and keep all
other cells. The resulting C_j(r) is a multiset: if the complement
already occurs as another cell, it occurs twice. Every C in C_j(r)
has alpha(C) <= 1/2. Multiplicities matter because the entire
argument is an integral of pairwise overlaps and no term can be
discarded.
This replacement removes the overlap of all pairs at very coarse
scales. The cost is a function of each endpoint separately, which
cancels when pair laws with the same combined marginals are
compared. On a fixed realised hierarchy define
M_j = sup { r : G_j(r) exists },
S_j(x) = int over { r : G_j(r) exists } 1_{ x not in G_j(r) } dr,
L_j(x,y) = int_R sum_{ C in C_j(r) } 1_C(x) 1_C(y) dr,
x != y.
Additive identity for a fixed hierarchy. For each realised hierarchy
on n >= 2 points the displayed quantities are finite, and for
distinct x, y,
d_j(x,y) = M_j + L_j(x,y) - S_j(x) - S_j(y).
The quantities are integrable over the grids. At every finite place where all
distinct coordinate differences are units, M_j = S_j = L_j = 0.
Proof. Suppress j. Let d_- and d_+ be the minimum and maximum of the
finitely many distinct-pair depths. Below d_- the partition has only
the cell P; above d_+ it has only singletons. A giant at any level
has a giant ancestor at every coarser level, so a giant exists on an
initial ray with endpoint M in [d_-, d_+], up to an immaterial
endpoint convention.
Let o(r) = 1_{ d(x,y) >= r }, g(r) = 1_{ G(r) exists }, and
t(r) = sum_{ C in C(r) } 1_C(x) 1_C(y). Expanding the giant
indicator through its complement gives, pointwise,
o(r) - g(r) = t(r)
- 1_{ G(r) exists, x not in G(r) }
- 1_{ G(r) exists, y not in G(r) }.
The integral of the left side is d(x,y) - M. Each term on the right
vanishes outside [d_-, d_+] on a distinct pair, and t(r) <= 2.
Integrating proves the identity, with bounds
0 <= S(x) <= d_+ - d_-,
0 <= L(x,y) <= 2 (d_+ - d_-),
|M| <= max { |d_-|, |d_+| }.
These are grid-integrable by the grid error lemma, since the
configuration has finitely many pairs and finite raw depths. At a
finite place with all raw depths zero, d_- = d_+ = 0, proving the
final assertion. Ties affect neither the identity nor any integral.
The empty complement of P and singleton occurrences contribute zero
to every distinct-pair overlap. L_j(x,x) is not defined: singleton
cells persist to arbitrarily fine scales, so that integral would
diverge. This is the only place where the off-diagonal restriction
matters, and it is why every subsequent estimate keeps a strict
distinct-pair convention.
Averaging over places and grids. For a nonnegative or integrable
quantity depending on the place and grids, write
avg(H) = sum_v sigma_v E_grids H,
I(g) = avg( sum_{ j=1 }^2 int_R sum_{ C in C_j(r) } g dr ).
There is no grid randomness at finite places. The integrand g may
depend on the coordinate, level and cell occurrence. All sums over
C_j(r) retain multiplicities. Set
S^*(x) = avg( S_1(x) + S_2(x) ),
L^*(x,y) = avg( L_1(x,y) + L_2(x,y) ), x != y.
The additive-identity lemma and the finite set of nonunit places show
that these and avg( M_1 + M_2 ) are finite. For each distinct pair the
product formula and the grid error lemma give
avg( d_1(x,y) + d_2(x,y) ) = 2 kappa.
Taking expectations in the depth identity is therefore legitimate
and gives an additive identity,
L^*(x,y) = b_* + S^*(x) + S^*(y), x != y,
with b_* = 2 kappa - avg( M_1 + M_2 ). In particular a signed law on
distinct pairs with zero total mass and zero sum of its two
marginals integrates to zero against L^*. This consequence is exact;
no diagonal sampling error is involved.
The three nonnegative finite scales used below are
W_2 = I( pi(C^2) ) = E_pi L^*(x,y),
A = E_alpha S^*(x),
W = W_2 + A.
The quantity W_2 measures distinct-pair overlap after the giant is
replaced; A measures the average time spent outside the giant. The
additive identity relates these scales to the graph and fiber laws.
Cell overlap and the integrated overlap identity. For a cell
occurrence C, write a = alpha(C) and p = mu_e(C). Both are random
variables on the paired hierarchical and fiber data. The cell
contribution to the total overlap is
q(C^2) = E_e 1_C(x_e) mu_e(C),
the probability that a q-random edge has both endpoints in C,
averaged over the fiber choice.
Combining the additive identity with (q_X + q_Y)/2 >= (1 - eps_n)
alpha and q <= B_0 pi from the extremal graph proposition gives
W_2 - o(1) A <= I( q(C^2) ) <= B_0 W_2.
The lower bound uses W_2 = b_* + 2 A and S^* >= 0. Writing out
E_q L^*(x,y) = W_2 + sum_{x in P} ( q_X(x) + q_Y(x)
- 2 alpha(x) ) S^*(x),
the second term is at least -(1 + eps_n) A, so
E_q L^*(x,y) >= W_2 - (1 + eps_n) A = W_2 - o(1) A.
The upper bound uses L^* <= B_0 ( b_* + S^* + S^* ) pointwise,
multiplied by q and integrated.
Small cells carry little of the overlap. Introduce, for 0 < lambda
< 1/2,
T(lambda) = I( E_e 1_C(x_e) p 1_{ p < lambda } ).
The convention is that C ranges over all cell occurrences of C_j(r),
with multiplicity, and p = mu_e(C). The integrand is at most q(C^2),
and hence finite. T(lambda) is the part of I(q(C^2)) in which a
typical selected fiber is small inside the current cell.
Small-fiber lemma. For the prepared graph and its hierarchies, if 0
< lambda < 1/2, 2/n <= tau <= 1, and H >= 1, then
T(lambda) <= C_sf ( ( lambda/tau^2 + lambda ) W_2
+ tau A + lambda H + e^{-b_1 H} ),
where b_1 > 0 is absolute and C_sf depends only on B_0 and the
grid-error constants.
Proof. Fix a place, a grid, and a coordinate j; suppress them in the
notation. Let q(C^2) and p be the cell overlap and the fiber mass of
an occurrence C of the current hierarchical family. Three broad
classes of C occur.
Class (i): a >= tau. Then m = |C| >= tau n >= 2, so pi(C^2) >=
a^2/2. The integrand of T(lambda) is at most lambda <= 2 lambda
pi(C^2)/tau^2. Summing and integrating gives at most 2 lambda
W_2/tau^2.
Class (ii): C is the complement occurrence of a giant, with a < tau.
Its contribution q(C^2) is at most B_0 pi(C^2) <= B_0 tau a, because
pi(C^2) <= a^2 <= tau a on m <= n. The integral of a over all
giant-complement occurrences equals A by the definition of S^*. This
class contributes at most B_0 tau A.
Class (iii): C is an actual nongiant cell with a < tau and p <
lambda. This is the main case. Fix the two entire realized
hierarchies. Let j be the coordinate of C, j' the other coordinate,
and H_v = H at archimedean places, H_v = 0 otherwise. For a fiber e
with source x and U = C, define two cells in the j'-hierarchy,
V_- = Pi_{j'}( h_e - r - H_v )(x),
V_+ = Pi_{j'}( h_e - r + H_v )(x),
with V_+ subset V_- by nesting. The two complementary errors on U
are
D^- = mu_e( P \ (U union V_-) ),
D^+ = mu_e( U cap V_+ ).
By the fiber equation i_j(x,y) + i_{j'}(x,y) = h_e on F_e, a point y
contributes to D^- exactly when d_j(x,y) < r < h_e - H_v -
d_{j'}(x,y), and to D^+ exactly when h_e + H_v - d_{j'}(x,y) <= r
<= d_j(x,y). Integrating over r gives
int D^- dr = E_{y ~ mu_e} ( h_e - d_j - d_{j'} - H_v )_+,
int D^+ dr = E_{y ~ mu_e} ( d_j + d_{j'} - h_e - H_v )_+.
Their sum is the expectation of ( |Delta_j + Delta_{j'}| - H_v )_+.
At nonarchimedean places both sides vanish. At archimedean places the
two-sided tail of Delta_j + Delta_{j'} satisfies
Pr( |Delta_j + Delta_{j'}| > u ) <= 2 C_0 e^{-b_0 u/2},
by the two-sided tail of each Delta and the union bound. Integrating
this tail and averaging over fibers gives
avg( E_e int (D^- + D^+) dr ) <= C e^{-b_1 H},
with absolute constants C, b_1 > 0. No independence of Delta_j and
Delta_{j'} is used.
Three subcases exhaust class (iii).
Sub-case (a): V_- is nongiant. Because mu_e(V_-) + D^- >= 1 - p >
1/2,
p <= 2 lambda ( mu_e(V_-) + D^- ).
Discard other restrictions on U and change levels by r' = h_e - r -
H_v. A pair sharing a nongiant cell in the j'-hierarchy at r'
contributes to L_{j'}. The main term is at most 2 lambda E_q L_{j'},
summed over both coordinates and places bounded by 2 B_0 lambda W_2.
The error D^- is bounded by the tail of Delta_j + Delta_{j'},
weighted by 2 lambda < 1.
Sub-case (b): V_- is giant and V_+ is not. For a fixed source x, the
levels at which its j'-cell is giant form an initial interval, by
nesting. The two levels defining V_- and V_+ straddle its endpoint,
so the allowed r has length at most 2 H_v. Since p < lambda, this
costs at most 2 lambda H_v per fiber. Summing and averaging over
places gives at most 4 lambda H.
Sub-case (c): V_+ is giant. This is the final case, since V_+ subset
V_-. Split
p = D^+ + mu_e( U \ V_+ ).
The first term is covered by the D^+ tail of the previous sub-case.
For the second term, change levels to r' = h_e - r + H_v for each
fiber. At fixed new level r', every counted pair has y outside
G_{j'}(r') and shares an actual j-cell of size below tau n at some
original level.
For fixed target y in P, let N_j(y) be the union of all actual
j-cells containing y of size below tau n, over all levels. By
nesting these cells form a chain, so |N_j(y)| < tau n (empty union
allowed). Every possible source x of this target lies in N_j(y) \
{y}, even though the selected levels vary with the fiber. Each edge
keeps weight 1/|E| after the level change. The mass at level r' is
therefore at most
sum_{y not in G_{j'}(r')} sum_{ x in N_j(y) \ {y} } q(x,y)
<= ( B_0 / ( n (n-1) ) )
sum_{ y, |N_j(y)| > 1 } ( |N_j(y)| - 1 )
<= B_0 tau alpha( P \ G_{j'}(r') ).
The final step uses |N_j(y)| - 1 <= tau (n-1) <= tau n because tau
<= 1. Integrating and averaging gives at most B_0 tau A.
The three subcases, the two earlier classes, and the initial split
together prove the lemma. Threshold ties only touch endpoints of
level intervals; all rearranged integrands are nonnegative, so
Tonelli's theorem applies.
Applying the lemma. Recall lambda_n = 1/log n, tau = lambda_n^{1/3},
H = lambda_n^{-1/2}. Then
T(lambda_n) <= C_sf ( lambda_n^{1/3} W + lambda_n^{1/2}
+ e^{-b_1 lambda_n^{-1/2}} )
= o(W+1).
Define the small-cell overlap
W_2,sm = I( pi(C^2) 1_{ |C| <= n^{1-c} } ).
Split I(q(C^2)) into the part with mu_e(C) < lambda_n, contributing
T(lambda_n) = o(W+1), and the part with mu_e(C) >= lambda_n. On the
latter, the subset estimate from the extremal graph proposition,
which is uniform in every cell C, bounds
I( q(C^2) 1_{ mu_e(C) >= lambda_n } )
<= ( 1 + o(1) ) ( W_2 - W_2,sm ) + o(1) W_2,sm.
Adding T(lambda_n) and comparing with the lower bound from the
integrated overlap identity gives
W_2,sm = o(W+1).
This estimate holds before either subsequence of W is chosen.
Variance lemma. Let F be a probability-law-on-subsets family with
weights omega_B >= 0 supported on subsets B of P of size k >=
n^gamma (with B of size 0 or 1 allowed but contributing zero
distinct pair); let nu_B be uniform on B; require E_F nu <= M alpha
for one fixed M > 0. Let p = mu_e(C) and a = alpha(C) for arbitrary
cell occurrences C, and let m = |B|. Then
I( E_F [ (p - a)^2 1_{ m > n^{1-c} }
+ (1/2) p^2 1_{ m <= n^{1-c}, p >= 2/k } ] )
<= C_M ( n^{c - gamma} W_2 + W_2,sm ) = o(W+1),
with C_M depending only on M.
Proof. Fix a place and grid. Two probabilities on distinct ordered
pairs are compared with pi. Let P_B be the uniform law on distinct
ordered pairs from B x B. Define R_B as follows: take X uniform on
B. If k < n, conditionally on X take Y uniform from B \ {X} with
probability k/n, and uniformly from P \ B otherwise. If B = P set
R_B = P_B = pi; the outside branch has zero probability.
The first marginal of R_B is nu_B and its second marginal is pi.
Indeed, a point y in B receives mass (k-1)(1/k)(k/n)(1/(k-1)) =
1/n, and a point y outside B receives mass k(1/k)((n-k)/n)/(n-k) =
1/n. Thus the signed measure P_B - 2R_B + pi has total mass zero,
first marginal alpha(B)*(nu_B - alpha)/... more precisely first and
second marginals summing to zero (marginal of P_B minus twice
marginal of R_B plus marginal of pi equals pi_B - 2nu_B + pi plus
pi_B - ...). In any case, the sum of first and second marginals is
zero. The additive overlap identity gives
I( P_B(C^2) - 2R_B(C^2) + pi(C^2) ) = 0.
The identity is over finite integrals. Any probability law on
distinct pairs is bounded by n(n-1) pi pointwise, so each of the
three nonnegative terms has finite integral because W_2 < infinity.
Averaging over the family is allowed.
The three cell probabilities, with b = |B cap C| and p = b/k, are
P_B(C^2) = b(b-1) / ( k(k-1) )
= p^2 - p(1-p)/(k-1),
R_B(C^2) = p ( (k/n)( (b-1)/(k-1) ) + (m-b)/n )
= a p - (k/n) p(1-p)/(k-1),
pi(C^2) = m(m-1) / ( n(n-1) )
= a^2 - a(1-a)/(n-1).
The middle identity continues to hold at k = n by the direct
definition of R_B. With H_B(C) = P_B(C^2) - 2 R_B(C^2) + pi(C^2),
H_B(C) = (p - a)^2 + ( (2k/n) - 1 ) p(1-p)/(k-1)
- a(1-a)/(n-1).
Write avg_H = E_F H_B and omega = E_F 1 <= 1. The last term of
H_B is multiplied by omega in the averaged formula.
First suppose m > n^{1-c}. Since 1/(k-1) <= 2 n^{-gamma} and
1/(n-1) <= 2 n^{-gamma} and E_F p <= M a, the formula gives
avg_H(C) >= E_F (p - a)^2 - 2 (M + 1) n^{-gamma} a.
For every m >= 2, a^2/2 <= pi(C^2) <= a^2. Since a > n^{-c}, so
n^{-gamma} a <= 2 n^{c - gamma} pi(C^2), hence
avg_H(C) >= E_F (p - a)^2 - 4 (M + 1) n^{c - gamma} pi(C^2).
Next suppose 2 <= m <= n^{1-c}. If p >= 2/k, then b >= 2 and
P_B(C^2) = p^2 (k/(k-1)) ((b-1)/b) >= (1/2) p^2.
Since P_B(C^2) is always nonnegative, this proves
P_B(C^2) >= (1/2) p^2 1_{ p >= 2/k } for every B.
Also R_B(C^2) <= a p, and therefore E_F R_B(C^2) <= M a^2 <=
2M pi(C^2). Discarding the nonnegative omega pi(C^2) term yields
avg_H(C) >= (1/2) E_F [ p^2 1_{ p >= 2/k } ] - 4 M pi(C^2).
Finally, if m = 0 or m = 1, all three pair probabilities vanish
exactly. For a singleton, p is either zero or 1/k, so the small-cell
term in the conclusion vanishes too; a singleton cannot satisfy
m > n^{1-c}. This exact cancellation treats the infinite singleton
tails. The separate correction terms in H_B are never integrated
over those tails.
Integrating the two lower bounds on their respective regions, using
the exact zero on empty and singleton cells, and applying the signed
identity gives
I( E_F [ (p - a)^2 1_{ m > n^{1-c} }
+ (1/2) p^2 1_{ m <= n^{1-c}, p >= 2/k } ] )
<= 4 (M + 1) n^{c - gamma} W_2 + 4 M W_2,sm.
Doubling proves the stated inequality with C_M = 8(M+1).
All the cell estimates hold for arbitrary subsets of P. These
include giant complements and count repeated cell occurrences with
their original multiplicity. In the case B = P the signed
expression and the large-cell variance vanish; the small-cell term
may equal a^2, which is absorbed by 2 pi(C^2). Finally, c < gamma,
W_2 <= W, and W_2,sm = o(W+1) give
I( E_F [ (p - a)^2 1_{ m > n^{1-c} }
+ (1/2) p^2 1_{ m <= n^{1-c}, p >= 2/k } ] )
= o(W+1).
Application to fiber and incoming laws. Two families are used. For
the fiber laws mu_e, with weights k_e/|E|, the weights sum to one
and
E_e mu_e = q_Y <= B_0 alpha,
by the extremal graph proposition. Their support sizes satisfy
k_e >= n^{s - o(1)} >= n^gamma for all large n, since gamma < s.
The large-cell term of the variance is therefore an honest variance
of mu_e against alpha.
For the incoming laws rho_y, retain the targets with d_y >= n^gamma,
and use weights q_Y(y) = d_y/|E|. The weighted mean is dominated by
q_X:
sum_{ y : d_y >= n^gamma } q_Y(y) rho_y <= q_X <= B_0 alpha.
Each retained law is uniform on its d_y incoming sources, and the
support size d_y >= n^gamma is at least the threshold. The omitted
q_Y-mass is O(n^{gamma - 1}) = o(1) by the extremal graph
proposition, so the truncation introduces an error of the same
order.
The overlap scale in the two regimes. The scale W = W_2 + A is
nonnegative and finite for every configuration. Starting from any
counterexample sequence, either W is bounded along a subsequence or
it is unbounded along a subsequence.
Unbounded overlap scale. First, W_2 >= c_1 W for some absolute c_1
> 0. Fix a place and grids. Write S = S_1 + S_2 and L = L_1 +
L_2. Choose a fiber e with its edge weight and then Y, Y'
independently with law mu_e. The additive identity and the fiber
equation give
S(Y) = M_1 + M_2 - S(x_e) - h_e + L(x_e,Y)
- Delta_1(x_e,Y) - Delta_2(x_e,Y).
All source-neighbour pairs are distinct. The first-moment bound, the
normalization of the archimedean weights, and the overlap identity
give
avg( E |S(Y) - S(Y')| ) <= 2 avg( E_q L(x,y) ) + O(1)
= O(W_2) + O(1).
To compare with A, use the pointwise bound
S^*(x) >= A - 2 W_2 (n > 2).
Indeed the average of L^*(x,y) over the n-1 labels y != x equals
W_2 + ((n-2)/(n-1)) ( S^*(x) - A ) and is nonnegative, so
S^*(x) >= A - ((n-1)/(n-2)) W_2. Hence
avg( E min { S(Y), S(Y') } ) >= A - O(W_2) - O(1).
Together with the inequality min{a,b} <= (a+b)/2 and the trivial
bound on E S(Y) this gives W_2 >= c_1 W with c_1 = 1/4 for all
large n.
Cut masses. Fix delta < 1/4 and take a Lipschitz weight function w
from [0,1] to [0,1] with w(u) = w(1-u), w = 0 on [0,delta/2]
union [1-delta/2,1], and w = 1 on [delta,1-delta]. For the original
partitions put
ell_j = int_R sum_{ B in Pi_j(r) } w(alpha(B)) dr.
Replacing a giant by its complement preserves every summand by
symmetry, occurrences still counted separately, so
W << avg( ell_1 + ell_2 ) <<_delta W.
Splitting the contribution of a <= delta according to p < 2 delta or
p >= 2 delta, and using the small-fiber lemma at lambda = 2 delta
and tau = lambda^{1/3},
I( 1_{ a <= delta } q(C^2) )
<= T(2 delta) + o_delta(W)
<= O( delta^{1/3} W ) + o_delta(W).
The constant in O(delta^{1/3}) is independent of delta. Therefore
I( 1_{ a > delta } ) >> W,
I( 1_{ a >= delta/4 } ) <<_delta W.
The first inequality uses q(C^2) <= 1; for the second, a >= delta/4
implies pi(C^2) >= a^2/2 >= delta^2/32 for large n, so a bound
O_delta(1) is o(W) along the present subsequence.
Cell distances. For a probability nu on P and distinct a_0, a_1 in P
define
D_j^nu(a_0, a_1)
= int_R w( nu { z : d_j(a_1, z) - d_j(a_0, z) >= u } ) du.
For any y in P also define
D_j^nu(infinity, y)
= int_R w( nu { z : d_j(y, z) >= u } ) du.
Splitting the first integral at zero and using w(t) = w(1-t) gives
exactly the two cell contributions above their common depth.
Tree transport. For two probabilities rho, alpha on the leaves of a
finite tree with edge lengths l_j(B) summing to ell_j, the least
expected D_j-distance among couplings of the two laws is
T_j(rho, alpha)
= sum_{ B != P } l_j(B) | rho(B) - alpha(B) |
= int_R sum_{ B in Pi_j(r) } w(alpha(B)) | rho(B) - alpha(B) | dr,
the finite-tree form of Section 2, Equation (5) of Evans and Matsen,
The Phylogenetic Kantorovich-Rubinstein Metric for Environmental
Sequence Diversity (Journal of Mathematical Biology 64, 2012).
./evans-matsen-2012-phylo-kr.pdf
A short proof: across each edge above B every coupling moves at
least |rho - alpha| units of mass. Conversely first match common
mass at each leaf, work upward, and route surplus from a child
subtree to deficits in other child subtrees; across each edge the
moved mass is exactly the absolute imbalance. Decomposing into
leaf-to-leaf paths gives a coupling that attains the displayed cost.
Transport estimates. Since q_Y = E_e mu_e, convexity and the cut
mass bounds give
avg( T_j(q_Y, alpha) ) = o(W),
avg( E_{q_Y} T_j(rho_y, alpha) ) = o(W).
The second estimate restricts to targets with d^-(y) >= n^gamma.
The omitted q_Y-mass is O(n^{gamma - 1}) = o(1); since every
transport cost is at most ell_j, the omission costs
o(1) avg(ell_j) = o(W) by the ell_j bound.
Tree fluctuation. Lemma: let a finite tree have nonnegative edge
lengths summing to L, with path pseudometric d, and let alpha be a
probability on its vertices. Suppose every edge of positive length
separates two sets of alpha-mass at least delta/2, 0 < delta < 1. If
X, X', Y are independent with law alpha,
E | d(X, Y) - d(X', Y) |
>= delta^2 L / ( 32 ( ceil(16/delta) + 1 ) ).
Proof. There is nothing to prove if L = 0. For every fixed y the
expected distance from X to y is at least delta L / 2, since each
positive edge separates y from mass at least delta/2. Since every
distance is at most L,
Pr { d(X, y) >= delta L / 4 } >= delta / 4.
Traverse the tree in a closed walk crossing every edge twice, of
total length 2L. Partition this walk into
M = ceil(16/delta) + 1 intervals of length at most delta L / 8, and
assign each vertex to an interval containing one of its visits. The
resulting classes have diameter at most delta L / 8, and
Pr { d(X', Y) <= delta L / 8 } >= sum_{ r=1 }^M alpha(C_r)^2
>= 1/M.
Conditional on Y the far event for X and the near event for X' are
independent, and the far probability is at least delta/4 uniformly.
So both events occur with probability at least delta/(4M). On their
intersection the absolute distance difference is at least delta L /
8. Summing finishes the estimate.
Contradiction in the unbounded case. In the tree for D_j every
positive edge has both side masses greater than delta/2, by the
support condition on w. Apply the fluctuation lemma with
L = ell_j, sum over j = 1, 2, and average over places and grids.
The transport estimates and the iid-tree overlap formula give
W << o(W),
which is impossible since W > 0. This excludes every subsequence on
which W -> infinity.
Bounded overlap scale. Choose one complex embedding and normalize
each coordinate so that the uniform laws have nonatomic limits. The
variance estimate gives the same limits for the fiber laws and for
the conditional incoming laws. The exact fiber equation then forces
a family of Mobius maps between those limits that cannot exist.
Normalize. From the depth identity and the grid-error tail, for j
= 1, 2,
E_grids E_pi | i_j(x,y) - M_j |
<= E_grids E_pi ( L_j(x,y) + S_j(x) + S_j(y)
+ |Delta_j(x,y)| )
= O(1).
Set m_j = E_pi i_j(x,y). For each realized grid, |m_j - M_j| <=
E_pi |i_j - M_j|, hence E_pi |i_j - m_j| = O(1). Normalize the
coordinates
U_j(x) = e^{m_j} Z_j(x) + b_j,
with translation b_j chosen immediately below. Then
E_pi | log |U_j(x) - U_j(y)| | <= C_1.
Only distinct pairs occur.
Tail decay. Write alpha_n^j = (U_j)_* alpha. The bound above implies
(alpha_n^j tensor alpha_n^j){ |z - z'| > R } <= C_1 / log R.
Choose R_0 > 1 with the right side below 1/2. Averaging over a
center at an empirical point gives a radius-R_0 disk containing at
least half the mass. Take b_j so this center moves to zero. For
R > 2R_0 pairs between this disk and the complement of the radius-R
disk have distance at least R/2, so
alpha_n^j{ |z| > R } <= 2 C_1 / log(R/2).
For any center z_0 in C and 0 < r < 1/2,
alpha_n^j( B(z_0,r) )^2 <= 1/n + C_1 / log(1/(2r)).
The diagonal mass of independent pairs in the ball is at most 1/n,
and every remaining pair has distance at most 2r.
Limits. Let S = C-hat be the Riemann sphere with the chordal metric,
and P(S) its probability measures. This space is compact and
metrizable for weak convergence; the open-set inequality and the
compactness of measures used in this section are the Portmanteau and Prokhorov
theorems in the form given by Sections 3 and 5 of van Gaans,
Probability Measures on Metric Spaces (Leiden, 2003).
./van-gaans-2003-weak-compactness.pdf
Along a common subsequence, alpha_n^j => beta_j on S for j = 1, 2.
Applying Portmanteau to the open spherical sets
( { |z| > R } union { infinity } ) in the tail bound and letting R
-> infinity, then to the open disks in the ball bound and letting r
downward to 0, each beta_j is a nonatomic probability measure on C.
Test convergence. For either family in the variance lemma put
nu_n^j = (U_j)_* nu. Then every phi in C(S) satisfies
E_F | int phi d nu_n^j - int phi d beta_j | -> 0.
Push every realized grid through z -> e^{m_j} z + b_j; this shifts
levels by -m_j and leaves the integration over all levels
unchanged. Fix R > 0 and 0 < eps < 1. At normalized levels in
I_eps = [-log eps, -log eps + 1]
the actual square cells have sides between eps/(2e) and eps. At
most N = N(R, eps) squares meet the radius-R disk, uniformly in the
grid and the level. For each actual cell B', let C be its
transformed occurrence: C = B' unless B' is the giant, in which
case C = P \ B'. Both measures have total mass one, so
| nu(B') - alpha(B') | = | nu(C) - alpha(C) |.
For those with |C| > n^{1-c}, Cauchy-Schwarz over the family, grids,
unit level interval, and at most N occurrences gives an integrated
sum of mean absolute discrepancies at most sqrt(N V_v). For the
others, including an empty giant complement,
E_F | nu(C) - alpha(C) | <= (B_0 + 1) alpha(C)
<= (B_0 + 1) n^{-c}.
Approximate phi on each square by its value at any point of the
square. The oscillation is at most omega_phi(sqrt(2) eps), with
omega_phi the uniform modulus of continuity in the spherical metric.
The remaining squares lie outside the radius-R disk with mean family
mass at most B_0 alpha_n^j{ |z| > R }. Integrating the test-function
estimate over grids and the unit interval gives
E_F | nu_n^j phi - alpha_n^j phi |
<= 2 omega_phi( sqrt(2) eps )
+ (B_0 + 1) ||phi||_infty alpha_n^j{ |z| > R }
+ ||phi||_infty ( sqrt(N V_v) + (B_0 + 1) N n^{-c} ).
For fixed R, eps let n -> infinity, then let R -> infinity and
eps downward to 0. The tail bound and alpha_n^j => beta_j prove
test convergence for nu_n^j. For the incoming laws, restoring all
omitted targets changes a mean test discrepancy by at most
2 ||phi||_infty times their o(1) total q_Y-mass, so test convergence
holds in full q_Y-expectation for rho_y as well.
Joint limit. For a q-edge (x,y) in fiber e, consider the joint
random object
( U_1(x), U_2(x), U_1(y), U_2(y),
(U_1)_* mu_e, (U_2)_* mu_e ) in S^4 x P(S)^2.
Take a subsequential weak limit Q with four coordinate entries
(a, b, a', b'). The last two entries equal ( beta_1, beta_2 )
almost surely. To justify this simultaneously for all tests, choose
a countable dense (f_r) in the unit ball of C(S). The metric
d_t( mu, beta ) = sum_{ r >= 1 } 2^{-r} | mu f_r - beta f_r |
metrizes weak convergence. The test convergence on finitely many
tests, followed by a bound on the series tail, gives convergence of
this metric to zero in mean for each fiber projection. Passing to Q
proves the assertion.
The inequality q <= B_0 pi <= 2 B_0 alpha tensor alpha implies
that each limiting same-coordinate pair law is dominated by
2 B_0 beta_j tensor beta_j, because the inequality passes to the
limit against every nonnegative continuous test on S^2. Since
beta_j is nonatomic and gives infinity mass zero,
a, b, a', b' in C, a != a', b != b',
a' in supp beta_1, b' in supp beta_2,
Q-almost surely.
Mobius obstruction. On the open domain of finite quadruples with
a != a' and b != b', put t' = (a' - a)(b' - b) and consider
Phi(z) = b + t' / (z - a) (z in S).
For each prelimit edge its two fiber projection measures are related
by a Mobius formula of this form, with its four coordinates in place
of (a, b, a', b'). Indeed, normalization multiplies the original
fiber product by e^{m_1 + m_2}, and evaluation at y identifies the
new product as (U_1(y) - U_1(x))(U_2(y) - U_2(x)). The limit
therefore obtains
beta_2 = Phi_* beta_1, Q-almost surely.
The Mobius equation cannot hold. For Z of law beta_2, the variable
-log |Z - b'| is nonconstant. Nonatomicity gives r_0 > 0 with
p = beta_2{ |z - b'| >= r_0 } > 0, and support membership of b'
gives 0 < r < r_0 with q = beta_2{ |z - b'| < r } > 0. For
-log r_0 < u < -log r, the upper tail of -log |Z - b'| lies in
[q, 1 - p], a nondegenerate interval.
The full-beta_1-measure equality set contains a sequence a_k != a'
tending to a', which exists because a' lies in supp beta_1 and
beta_1 is nonatomic. For z outside the null countable set
{ a', a_1, a_2, ... },
log ( |z - a_k| / |z - a'| ) -> 0.
So these variables converge to zero in beta_1-probability. By the
Mobius equation, the corresponding probability on beta_2 puts its
mass inside disks around b' whose radii shrink to zero with k, in
direct contradiction with q > 0. The right side is a fixed positive
number; the left side must tend to zero.
Bounded case excluded. Every subsequence of W is either bounded or
unbounded; the unbounded alternative was excluded above, and the
bounded alternative leads to the Mobius obstruction. The theorem
follows.
Every finite planar point set determines one distance fiber per
ordered distinct pair. The product formula across all places of the
number field turns one fiber into a collection of balanced
logarithmic relations, and nested random grids turn those relations
into nonnegative overlaps whose total W = W_2 + A has only two
regimes. Each regime contradicts the fiber equation.
Three properties of the plane drive the argument. Real and complex
coordinates provide two coordinate maps whose product is exactly
the squared distance, so distances become products of algebraic
coordinates. Random translations, dilations and rotations put
coordinate differences in generic scale. The binomial ratio
ceil(N/2)(ceil(N/2)-1)/(N(N-1)) tends to 1/4, and this is where
the constant 1/4 enters through the deletion step.
No separation, algebraic independence, or general-position
hypothesis is imposed. The threshold s is fixed, the continuity
point is chosen once, and the two final alternatives cover every
failure mode of the theorem.
For every fixed eps > 0 and every finite planar
point set P of size n, at least n - o(n) of the pins of P determine
at least n^{1 - eps} distinct nonzero distances. The weak pinned
Erdos distinct-distance conjecture follows.