The Setting
Let be a configuration of points in the plane whose points carry two injective coordinates , with values in a number field , and put . For each point of the plane, the choice and makes the squared distance , so a set of points on which is constant lies on one circle about . A fiber with pinned point in is a set of points of on which is constant.
Each place of and each coordinate give a multiscale hierarchy of cells on : the balls of the -adic absolute value at a finite place , the cells of a randomly rotated, dilated and shifted dyadic grid at an archimedean one. A large fiber samples a cell through its uniform law, which gives the proportion , while the whole configuration gives it . The question is how far the two proportions stray apart, on average over a weighted family of large sets and over all cells counted with their mass, compared with how often a random pair of distinct points of falls in a common cell. The library states a bound for a single cell, for a random cell with additive overlap (defined below) and for the total over the hierarchy, together with two rates: for families of sets of at least points, where is an exponent with , and for the fibers and the incoming neighborhoods of a prepared graph (defined below).
Uniform Laws and the Variance Cell
For a subset of , the uniform law on gives each point of the mass and every other point the mass , so that a subset of receives ; the uniform law on is , with . The uniform law on distinct ordered pairs of gives each pair of distinct points of the mass ✦, and is the probability that such a pair lies in ✦; we write .
The mixed pair probability of a subset of gives a pair of distinct points with the mass when and when , and every other pair the mass ✦; is its total over the pairs in .✦ The signed cell term of a subset of is (1)✦
Let be a finite family of real weights and subsets of , and let be a real threshold. The variance cell of a subset of is (2)✦ written when the family is fixed.
A random subset of is a measurable map from a measure space to the subsets of , these carrying the discrete -algebra. The pair overlap of a random subset of at distinct points , of is the measure of the event that both lie in .✦ A random subset of has additive overlap when there are a real number and a real function on with for all distinct , .
Cells, Masses and Scales
An ultrametric depth on is a real function on ordered pairs of points of , symmetric in the two points, with for pairwise distinct , , .✦ The cell of a point at level is the set made of and the points with ✦, and is the set of these cells.✦ A giant at level is a cell of with more than points✦, and is the union of the giants.✦ The transformed family is the multiset made of the cells of with at most points and the complements of the giants .✦ For a subset of with at least two points, the cell mass is the total length of the levels at which occurs in , counted with multiplicity, (3)✦ and when . The potential of a point is the length of the set of levels at which a giant exists and lies outside .✦
Each coordinate gives depths at the places of . At a finite place , the finite place depth of distinct points , is the raw depth .✦ The bad places of are the finite places at which the difference of some pair of distinct points is not a unit.✦
At an archimedean place , with complex embedding , a random grid enters. A phase and grid sample consists of a phase and two axis sequences of reals.✦ The full sample law draws uniformly from , uniformly from and, independently of them and of each other, the two axis sequences, whose terms are independent: the term of index is uniform on , and the term of index is or with probability each.✦ Two points of the plane share a cell at scale when, on each axis, they lie in the same half-open interval of length of the grid offset by the sum of the terms of index to of that axis sequence.✦ The hierarchy depth of , is , where is the least scale at which the rotated and rescaled points and share a cell.✦ The sample is good at when the hierarchy depth of and , as a function of the pair of distinct points of , is an ultrametric depth on .✦ The archimedean depth is the function on pairs of distinct points of that gives , the hierarchy depth of and when is good at , and otherwise.✦
With the archimedean weight , where is for a real place and for a complex one, the global cell mass of a subset of for the coordinate is (4)✦ Here is drawn from the full sample law. The potential of a point of for the coordinate is the weighted sum, with the weights of (4), of the potentials over the archimedean places and of the potentials over the bad finite places.✦ The total cell mass of a subset of is , and the total potential of a point of is . A real function on the subsets of has the total over places, coordinates, grids, levels and cells (5)✦
The overlap scale , the small overlap scale at an exponent , the potential scale and the scale are (6)
Prepared Graphs
A fiber system on a finite vertex set , with fibers indexed by a finite set , assigns to each fiber a source in and a target set not containing , two distinct fibers with the same source having disjoint target sets.✦ The edges of a fiber system are the pairs with , and denotes the set of edges.✦ The fiber weight is the mass that the uniform law on gives to the edges of .✦ The incoming neighbors of a vertex form the set of vertices with ✦, and is the mass gives to the edges ending at .✦ At a threshold , the retained family assigns to each vertex the retained set with retained weight when , and with otherwise.
Let . For a proportion and a set of vertices, the heavy count is the number of edges inside carried by the fibers with source in that keep at least the proportion of their targets in .✦ A fiber system on is a prepared graph with density , exponents , and error when , , every vertex has out-degree, the number of edges leaving it, plus in-degree, the number of edges ending at it, at least , every fiber has more than targets, and every set of vertices has , and when .✦
For a sequence of fiber systems on vertex sets , with , injective coordinates of in a number field and the total of (5) for them, the fiber variance and the incoming variance are (7) the first for the fiber weights and target sets of , the second for its retained family at threshold .
The Claim
Theorem 1. Let be a finite set of points with a finite family of weights with and subsets of with at least two points each. Let , , and be real numbers with , with for every and , and suppose that for every point of .
(a) For every subset of , (8)✦
(b) For every random subset of on a measure space with additive overlap and with integrable over , (9)✦
(c) If and , are injective coordinates of in a number field , then (10)✦
(d) Let , and . Let be a sequence of finite sets with , each with injective coordinates , in a number field , with uniform law , total , scale and small overlap scale at . For each let be a finite family of weights with and subsets of such that, for all large , every has at least points and pointwise. If , then (11)✦
(e) Let , and , and let be a prepared graph on a finite set with density , exponents , and error , where , and . Let , be injective coordinates of in a number field such that for every fiber of there is with for all . Then (12)✦
In the paper, the result reads: for a finite family of probability measures , each uniform on a set with , with nonnegative weights of total mass at most one and pointwise, and with , and , one has , with depending only on .
The library’s bound carries the explicit coefficients and at any threshold where the paper has , and , and gives the rate as the limits (11) and (12).
What Is Checked
The claim is stated over the variance cell (2) of a weighted family of uniform laws on subsets of a finite set, the uniform pair law and the signed cell term (1), the pair overlap of a random subset, the total (5) built from the cell masses of the finite place and archimedean depths of two injective coordinates in a number field, the scales (6), and the fiber and incoming variances (7) of prepared graphs on whose fibers is constant. About these constructions the library proves that the finite place depth at each finite place and the archimedean depth at each archimedean place and sample are ultrametric depths, and that an injective coordinate has only finitely many bad places.