OctoInformBeta

OpenAI preprint, September 2026 · §5. Variance from off-diagonal sampling · §5

Lemma 5.1 [Variance bound]: The total variance cell of uniform laws is bounded by multiples of W2W_2 and W2,smW_{2,\mathrm{sm}}, and is o(W+1)o(W+1) along prepared graph sequences

Variance bound for sampling cells by uniform laws.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let PP be a configuration of nn points in the plane whose points carry two injective coordinates Z1Z_1, Z2Z_2 with values in a number field KK, and put t(x,y)=(Z1(y)−Z1(x))(Z2(y)−Z2(x))t(x,y) = (Z_1(y)-Z_1(x))(Z_2(y)-Z_2(x)). For each point (u,b)(u,b) of the plane, the choice Z1=u+ibZ_1 = u+ib and Z2=u−ibZ_2 = u-ib makes t(x,y)t(x,y) the squared distance ∥y−x∥2\|y-x\|^2, so a set of points yy on which t(x,⋅)t(x,\cdot) is constant lies on one circle about xx. A fiber with pinned point xx in PP is a set of points yy of PP on which t(x,⋅)t(x,\cdot) is constant.

Each place of KK and each coordinate give a multiscale hierarchy of cells on PP: the balls of the vv-adic absolute value at a finite place vv, the cells of a randomly rotated, dilated and shifted dyadic grid at an archimedean one. A large fiber BB samples a cell CC through its uniform law, which gives CC the proportion |B∩C|/|B||B\cap C|/|B|, while the whole configuration gives it |C|/n|C|/n. 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 PP 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 nγn^{\gamma} points, where γ\gamma is an exponent with 0<γ<10<\gamma<1, and for the fibers and the incoming neighborhoods of a prepared graph (defined below).

Uniform Laws and the Variance Cell

For a subset BB of PP, the uniform law νB\nu_B on BB gives each point of BB the mass 1/|B|1/|B| and every other point the mass 00, so that a subset CC of PP receives νB(C)=|B∩C|/|B|\nu_B(C) = |B\cap C|/|B|; the uniform law on PP is α=νP\alpha = \nu_P, with α(C)=|C|/n\alpha(C) = |C|/n. The uniform law πB\pi_B on distinct ordered pairs of BB gives each pair (x,y)(x,y) of distinct points of BB the mass 1/(|B|(|B|−1))1/(|B|(|B|-1))✦, and πB(C×C)\pi_B(C\times C) is the probability that such a pair lies in C×CC\times C✦; we write π=πP\pi = \pi_P.

The mixed pair probability χB\chi_B of a subset BB of PP gives a pair (x,y)(x,y) of distinct points with x∈Bx\in B the mass 1/(n(|B|−1))1/(n(|B|-1)) when y∈By\in B and 1/(n|B|)1/(n|B|) when y∉By\notin B, and every other pair the mass 00✦; χB(C×C)\chi_B(C\times C) is its total over the pairs in C×CC\times C.✦ The signed cell term of a subset CC of PP is sB(C)=πB(C×C)−2χB(C×C)+π(C×C).s_B(C) = \pi_B(C\times C) - 2\chi_B(C\times C) + \pi(C\times C).(1)✦

Let (wi,Bi)i∈I(w_i,B_i)_{i\in I} be a finite family of real weights wiw_i and subsets BiB_i of PP, and let TT be a real threshold. The variance cell VT[w,B](D)V_T[w,B](D) of a subset DD of PP is VT[w,B](D)={∑iwi(νBi(D)−α(D))2if |D|>T,12∑iwiνBi(D)2𝟏{νBi(D)≥2/|Bi|}if |D|≤T,V_T[w,B](D) = \begin{cases} \sum_{i} w_i\bigl(\nu_{B_i}(D) - \alpha(D)\bigr)^2 & \text{if } |D| > T,\\[2pt] \tfrac12\sum_{i} w_i\,\nu_{B_i}(D)^2\,\mathbf{1}\{\nu_{B_i}(D)\ge 2/|B_i|\} & \text{if } |D|\le T, \end{cases}(2)✦ written VT(D)V_T(D) when the family is fixed.

A random subset CC of PP is a measurable map from a measure space (Ω,μ)(\Omega,\mu) to the subsets of PP, these carrying the discrete σ\sigma-algebra. The pair overlap of a random subset CC of PP at distinct points xx, yy of PP is the measure L(x,y)=μ{ω:x∈C(ω),y∈C(ω)}L(x,y) = \mu\{\omega : x\in C(\omega),\ y\in C(\omega)\} of the event that both lie in CC.✦ A random subset CC of PP has additive overlap when there are a real number bb and a real function gg on PP with L(x,y)=b+g(x)+g(y)L(x,y) = b + g(x) + g(y) for all distinct xx, yy.

Cells, Masses and Scales

An ultrametric depth dd on PP is a real function on ordered pairs of points of PP, symmetric in the two points, with d(x,z)≥min⁡(d(x,y),d(y,z))d(x,z)\ge\min(d(x,y),d(y,z)) for pairwise distinct xx, yy, zz.✦ The cell Cr(x)C_r(x) of a point xx at level rr is the set made of xx and the points yy with d(x,y)≥rd(x,y)\ge r✦, and 𝒞r\mathcal{C}_r is the set of these cells.✦ A giant at level rr is a cell of 𝒞r\mathcal{C}_r with more than n/2n/2 points✦, and GrG_r is the union of the giants.✦ The transformed family 𝒯r\mathcal{T}_r is the multiset made of the cells of 𝒞r\mathcal{C}_r with at most n/2n/2 points and the complements P\CP\setminus C of the giants CC.✦ For a subset CC of PP with at least two points, the cell mass is the total length of the levels at which CC occurs in 𝒯r\mathcal{T}_r, counted with multiplicity, md(C)=∫ℝ#{occurrences of C in 𝒯r}dr,m_d(C) = \int_{\mathbb{R}} \#\{\text{occurrences of } C \text{ in } \mathcal{T}_r\}\,dr,(3)✦ and md(C)=0m_d(C) = 0 when |C|<2|C|<2. The potential Sd(x)S_d(x) of a point xx is the length of the set of levels rr at which a giant exists and xx lies outside GrG_r.✦

Each coordinate ZZ gives depths at the places of KK. At a finite place vv, the finite place depth dvd_v of distinct points xx, yy is the raw depth −log⁡|Z(x)−Z(y)|v-\log|Z(x)-Z(y)|_v.✦ The bad places of ZZ are the finite places at which the difference Z(x)−Z(y)Z(x)-Z(y) of some pair of distinct points is not a unit.✦

At an archimedean place vv, with complex embedding ιv\iota_v, a random grid enters. A phase and grid sample ω\omega consists of a phase (ξ,φ)(\xi,\varphi) and two axis sequences of reals.✦ The full sample law draws ξ\xi uniformly from (0,log⁡2](0,\log 2], φ\varphi uniformly from (0,2π](0,2\pi] and, independently of them and of each other, the two axis sequences, whose terms are independent: the term of index 00 is uniform on (0,1](0,1], and the term of index k+1k+1 is 00 or 2k2^k with probability 1/21/2 each.✦ Two points of the plane share a cell at scale m∈ℤm\in\mathbb{Z} when, on each axis, they lie in the same half-open interval of length 2m2^m of the grid offset by the sum of the terms of index 00 to max⁡(m,0)\max(m,0) of that axis sequence.✦ The hierarchy depth of zz, w∈ℂw\in\mathbb{C} is −mlog⁡2−ξ-m\log 2-\xi, where mm is the least scale at which the rotated and rescaled points e−ξeiφze^{-\xi}e^{i\varphi}z and e−ξeiφwe^{-\xi}e^{i\varphi}w share a cell.✦ The sample ω\omega is good at vv when the hierarchy depth of ιv(Z(x))\iota_v(Z(x)) and ιv(Z(y))\iota_v(Z(y)), as a function of the pair (x,y)(x,y) of distinct points of PP, is an ultrametric depth on PP.✦ The archimedean depth dv,ωd_{v,\omega} is the function on pairs of distinct points of PP that gives xx, yy the hierarchy depth of ιv(Z(x))\iota_v(Z(x)) and ιv(Z(y))\iota_v(Z(y)) when ω\omega is good at vv, and 00 otherwise.✦

With the archimedean weight σv=mult⁡(v)/[K:ℚ]\sigma_v = \operatorname{mult}(v)/[K:\mathbb{Q}], where mult⁡(v)\operatorname{mult}(v) is 11 for a real place and 22 for a complex one, the global cell mass mZ(C)m_Z(C) of a subset CC of PP for the coordinate ZZ is mZ(C)=∑v∣∞σv𝔼ωmdv,ω(C)+1[K:ℚ]∑vbadmdv(C),m_Z(C) = \sum_{v\mid\infty}\sigma_v\,\mathbb{E}_{\omega}\,m_{d_{v,\omega}}(C) + \frac{1}{[K:\mathbb{Q}]}\sum_{v\ \mathrm{bad}} m_{d_v}(C),(4)✦ Here ω\omega is drawn from the full sample law. The potential SZ(x)S_Z(x) of a point xx of PP for the coordinate ZZ is the weighted sum, with the weights of (4), of the potentials Sdv,ω(x)S_{d_{v,\omega}}(x) over the archimedean places and of the potentials Sdv(x)S_{d_v}(x) over the bad finite places.✦ The total cell mass m(C)m(C) of a subset CC of PP is mZ1(C)+mZ2(C)m_{Z_1}(C)+m_{Z_2}(C), and the total potential S*(x)S^*(x) of a point xx of PP is SZ1(x)+SZ2(x)S_{Z_1}(x)+S_{Z_2}(x). A real function ff on the subsets of PP has the total over places, coordinates, grids, levels and cells I(f)=∑C⊆Pm(C)f(C).I(f) = \sum_{C\subseteq P} m(C)\,f(C).(5)✦

The overlap scale W2W_2, the small overlap scale W2,smW_{2,\mathrm{sm}} at an exponent cc, the potential scale AA and the scale WW are W2=I(π(C×C)),W2,sm=I(π(C×C)𝟏{|C|≤n1−c}),A=∑x∈Pα(x)S*(x),W=W2+A.\begin{gathered} W_2 = I\bigl(\pi(C\times C)\bigr),\qquad W_{2,\mathrm{sm}} = I\bigl(\pi(C\times C)\,\mathbf{1}\{|C|\le n^{1-c}\}\bigr),\\ A = \sum_{x\in P}\alpha(x)\,S^*(x),\qquad W = W_2 + A. \end{gathered}(6)

Prepared Graphs

A fiber system on a finite vertex set VV, with fibers indexed by a finite set II, assigns to each fiber ee a source xex_e in VV and a target set Fe⊆VF_e\subseteq V not containing xex_e, two distinct fibers with the same source having disjoint target sets.✦ The edges of a fiber system are the pairs (xe,y)(x_e,y) with y∈Fey\in F_e, and EE denotes the set of edges.✦ The fiber weight we=|Fe|/|E|w_e = |F_e|/|E| is the mass that the uniform law qq on EE gives to the edges of ee.✦ The incoming neighbors of a vertex yy form the set N−(y)N^-(y) of vertices xx with (x,y)∈E(x,y)\in E✦, and |N−(y)|/|E||N^-(y)|/|E| is the mass qq gives to the edges ending at yy.✦ At a threshold TT, the retained family assigns to each vertex yy the retained set Ry=N−(y)R_y = N^-(y) with retained weight ry=|N−(y)|/|E|r_y = |N^-(y)|/|E| when |N−(y)|≥T|N^-(y)|\ge T, and Ry=VR_y = V with ry=0r_y = 0 otherwise.

Let n=|V|n = |V|. For a proportion λ\lambda and a set DD of vertices, the heavy count Hλ(D)H_\lambda(D) is the number of edges inside DD carried by the fibers with source in DD that keep at least the proportion λ\lambda of their targets in DD.✦ A fiber system GG on VV is a prepared graph with density θ\theta, exponents γ\gamma, cc and error η\eta when n≥2n\ge 2, (θ−η)n(n−1)≤|E|≤(θ+η/8)n(n−1)(\theta-\eta)n(n-1)\le|E|\le(\theta+\eta/8)n(n-1), every vertex has out-degree, the number of edges leaving it, plus in-degree, the number of edges ending at it, at least 2(θ−η)(n−1)2(\theta-\eta)(n-1), every fiber has more than nγn^{\gamma} targets, and every set DD of vertices has H1/log⁡n(D)≤(θ+η)|D|(|D|−1)H_{1/\log n}(D)\le(\theta+\eta)|D|(|D|-1), and H1/log⁡n(D)≤η|D|(|D|−1)H_{1/\log n}(D)\le\eta|D|(|D|-1) when |D|≤n1−c|D|\le n^{1-c}.✦

For a sequence of fiber systems GjG_j on vertex sets VjV_j, with nj=|Vj|n_j = |V_j|, injective coordinates of VjV_j in a number field KjK_j and the total IjI_j of (5) for them, the fiber variance Φj\Phi_j and the incoming variance Ψj\Psi_j are Φj=Ij(Vnj1−c[w,F]),Ψj=Ij(Vnj1−c[r,R]),\Phi_j = I_j\bigl(V_{n_j^{1-c}}[w,F]\bigr),\qquad \Psi_j = I_j\bigl(V_{n_j^{1-c}}[r,R]\bigr),(7) the first for the fiber weights and target sets of GjG_j, the second for its retained family at threshold njγn_j^{\gamma}.

The Claim

Theorem 1. Let PP be a finite set of nn points with a finite family (wi,Bi)i∈I(w_i,B_i)_{i\in I} of weights wi≥0w_i\ge 0 with ∑iwi≤1\sum_i w_i\le 1 and subsets BiB_i of PP with at least two points each. Let T≥1T\ge 1, M≥0M\ge 0, ε≥0\varepsilon\ge 0 and τ>0\tau>0 be real numbers with τn≤T\tau n\le T, with 1/(|Bi|−1)≤ε1/(|B_i|-1)\le\varepsilon for every ii and 1/(n−1)≤ε1/(n-1)\le\varepsilon, and suppose that ∑iwiνBi(x)≤Mα(x)\sum_i w_i\,\nu_{B_i}(x)\le M\alpha(x) for every point xx of PP.

(a) For every subset DD of PP, VT(D)≤∑iwisBi(D)+2ε(M+1)τπ(D×D)+4Mπ(D×D)𝟏{|D|≤T}.V_T(D)\le\sum_i w_i\,s_{B_i}(D) + \frac{2\varepsilon(M+1)}{\tau}\,\pi(D\times D) + 4M\,\pi(D\times D)\,\mathbf{1}\{|D|\le T\}.(8)✦

(b) For every random subset CC of PP on a measure space (Ω,μ)(\Omega,\mu) with additive overlap and with π(C×C)\pi(C\times C) integrable over Ω\Omega, ∫ΩVT(C)dμ≤2ε(M+1)τ∫Ωπ(C×C)dμ+4M∫Ωπ(C×C)𝟏{|C|≤T}dμ.\int_\Omega V_T(C)\,d\mu\le\frac{2\varepsilon(M+1)}{\tau}\int_\Omega\pi(C\times C)\,d\mu + 4M\int_\Omega\pi(C\times C)\,\mathbf{1}\{|C|\le T\}\,d\mu.(9)✦

(c) If n≥2n\ge 2 and Z1Z_1, Z2Z_2 are injective coordinates of PP in a number field KK, then I(VT)≤2ε(M+1)τW2+4MI(π(C×C)𝟏{|C|≤T}).I(V_T)\le\frac{2\varepsilon(M+1)}{\tau}\,W_2 + 4M\,I\bigl(\pi(C\times C)\,\mathbf{1}\{|C|\le T\}\bigr).(10)✦

(d) Let 0<γ<10<\gamma<1, c<γc<\gamma and M≥0M\ge 0. Let (Vj)(V_j) be a sequence of finite sets with nj=|Vj|→∞n_j = |V_j|\to\infty, each with injective coordinates Z1Z_1, Z2Z_2 in a number field KjK_j, with uniform law αj\alpha_j, total IjI_j, scale WjW_j and small overlap scale W2,sm,jW_{2,\mathrm{sm},j} at cc. For each jj let (wj,i,Bj,i)i(w_{j,i},B_{j,i})_i be a finite family of weights wj,i≥0w_{j,i}\ge 0 with ∑iwj,i≤1\sum_i w_{j,i}\le 1 and subsets Bj,iB_{j,i} of VjV_j such that, for all large jj, every Bj,iB_{j,i} has at least njγn_j^{\gamma} points and ∑iwj,iνBj,i≤Mαj\sum_i w_{j,i}\,\nu_{B_{j,i}}\le M\alpha_j pointwise. If W2,sm,j/(Wj+1)→0W_{2,\mathrm{sm},j}/(W_j+1)\to 0, then Ij(Vnj1−c[wj,Bj])Wj+1→0(j→∞).\frac{I_j\bigl(V_{n_j^{1-c}}[w_j,B_j]\bigr)}{W_j+1}\longrightarrow 0\qquad(j\to\infty).(11)✦

(e) Let θ>0\theta>0, 0<γ<10<\gamma<1 and c<γc<\gamma, and let GjG_j be a prepared graph on a finite set VjV_j with density θ\theta, exponents γ\gamma, cc and error ηj\eta_j, where nj=|Vj|→∞n_j = |V_j|\to\infty, 0≤ηj≤θ/20\le\eta_j\le\theta/2 and ηj→0\eta_j\to 0. Let Z1Z_1, Z2Z_2 be injective coordinates of VjV_j in a number field KjK_j such that for every fiber ee of GjG_j there is te∈Kjt_e\in K_j with t(xe,y)=tet(x_e,y) = t_e for all y∈Fey\in F_e. Then ΦjWj+1→0andΨjWj+1→0(j→∞).\frac{\Phi_j}{W_j+1}\longrightarrow 0\qquad\text{and}\qquad \frac{\Psi_j}{W_j+1}\longrightarrow 0\qquad(j\to\infty).(12)✦

In the paper, the result reads: for a finite family ℱ\mathcal{F} of probability measures ν\nu, each uniform on a set B⊆PB\subseteq P with |B|=k≥nγ|B| = k\ge n^{\gamma}, with nonnegative weights of total mass at most one and 𝔼ℱν≤Mα\mathbb{E}_{\mathcal{F}}\nu\le M\alpha pointwise, and with m=|C|m = |C|, a=α(C)a = \alpha(C) and p=ν(C)p = \nu(C), one has I(𝔼ℱ[(p−a)2𝟏{m>n1−c}+p2𝟏{m≤n1−c,p≥2/k}])≤CM(nc−γW2+W2,sm)=o(W+1)I\bigl(\mathbb{E}_{\mathcal{F}}[(p-a)^2\,\mathbf{1}\{m>n^{1-c}\} + p^2\,\mathbf{1}\{m\le n^{1-c},\ p\ge 2/k\}]\bigr) \le C_M\bigl(n^{c-\gamma}W_2 + W_{2,\mathrm{sm}}\bigr) = o(W+1), with CMC_M depending only on MM.

The library’s bound carries the explicit coefficients 2ε(M+1)/τ2\varepsilon(M+1)/\tau and 4M4M at any threshold T≥τnT\ge\tau n where the paper has CMC_M, nc−γn^{c-\gamma} and n1−cn^{1-c}, and gives the rate o(W+1)o(W+1) 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 tt 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.