OctoInformBeta

OpenAI preprint, September 2026 · §4. Small cells and fiber mass · §4

§4 (proof): small cells carry o(W+1) of the overlap: Cells of at most n1−cn^{1-c} points, along prepared graphs over number fields as n→∞n \to \infty and η→0\eta \to 0, with explicit bounds for each nn

Small cells carry o(W+1)o(W+1) of the pair overlap.

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

Write a point of the plane as u+ibu + ib and give it the two coordinates Z1=u+ibZ_1 = u + ib and Z2=u−ibZ_2 = u - ib. For points xx and yy, t(x,y)=(Z1(y)−Z1(x))(Z2(y)−Z2(x))=|y−x|2,t(x,y) = (Z_1(y) - Z_1(x))(Z_2(y) - Z_2(x)) = |y - x|^2,(1) so the points yy at which t(x,y)t(x,y) takes one value lie on one circle about the pin xx. The points of a configuration at one distance from a pin xx form a fiber with source xx, the points of the fiber are its targets, and an edge joins the source to a target.

The points are also sorted into cells, at every place of a number field KK and at every level, and each cell carries a mass; the overlap of two points is the mass of the cells holding both. The question is how much of the mean overlap of a pair of points lies in the small cells, those with at most n1−cn^{1-c} of the nn points of the configuration for a fixed exponent cc, and how the mean overlap of the two ends of a random edge compares with that of a random pair.

Fiber Systems and Prepared Graphs

A fiber system GG on a finite vertex set VV, with fibers indexed by a finite set II, assigns to each fiber ee a source xe∈Vx_e \in V 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 edge set EE of GG is the set of ordered pairs (xe,y)(x_e, y) with y∈Fey \in F_e✦, and the edge law qq of GG is the uniform probability law on EE✦. The weight of a fiber ee is we=|Fe|/|E|w_e = |F_e|/|E|, the mass that qq gives to the edges of ee.✦ The degree of a vertex xx is the number of vertices yy with (x,y)∈E(x,y) \in E plus the number of vertices yy with (y,x)∈E(y,x) \in E.✦

The size of a fiber ee in a set DD of vertices is |Fe∩D||F_e \cap D|✦, and the heavy count of DD at a proportion λ\lambda is the total size in DD of the fibers that have their source in DD and keep at least the proportion λ\lambda of their targets there: hλ(D)=∑e:xe∈D,|Fe∩D|≥λ|Fe||Fe∩D|.h_\lambda(D) = \sum_{e \,:\, x_e \in D,\ |F_e \cap D| \ge \lambda |F_e|} |F_e \cap D|.(2)✦

Write n=|V|n = |V| and λ=1/log⁡n\lambda = 1/\log n. A prepared graph with density θ\theta, exponents γ\gamma and cc and error η\eta is a fiber system GG on VV with n≥2n \ge 2 in which every vertex has degree at least 2(θ−η)(n−1)2(\theta - \eta)(n-1), every fiber has more than nγn^{\gamma} targets, and (θ−η)n(n−1)≤|E|≤(θ+η/8)n(n−1),hλ(D)≤(θ+η)|D|(|D|−1)(\theta - \eta)\, n(n-1) \le |E| \le (\theta + \eta/8)\, n(n-1), \qquad h_\lambda(D) \le (\theta + \eta)\, |D|(|D| - 1)(3)✦ for every set DD of vertices, with hλ(D)≤η|D|(|D|−1)h_\lambda(D) \le \eta\, |D|(|D| - 1) when |D|≤n1−c|D| \le n^{1-c}.

On VV, α\alpha is the uniform law✦, π\pi the uniform law on ordered pairs of distinct vertices✦ and μe\mu_e the uniform law on FeF_e✦. The mass of a set CC under a law is the sum of its values on the points of CC, so that μe(C)=|Fe∩C|/|Fe|\mu_e(C) = |F_e \cap C|/|F_e|.✦

Cell Masses and the Overlap

A cell mass on VV is a real function mm on the subsets of VV. The integral of a real function ff of subsets against mm is Im(f)=∑C⊆Vm(C)f(C),I_m(f) = \sum_{C \subseteq V} m(C)\, f(C),(4)✦ The overlap of two vertices xx and yy of VV under a cell mass mm is Lm(x,y)=∑C∋x,ym(C)L_m(x,y) = \sum_{C \ni x, y} m(C).

For a subset CC of VV, π(C×C)\pi(C \times C) is the probability that a uniform pair of distinct vertices lies in CC✦, and q(C×C)q(C \times C) the probability that an edge drawn from qq has both ends in CC✦. The small fiber slice of CC at the proportion λ\lambda adds the weighted masses weμe(C)w_e\, \mu_e(C) of the fibers whose source lies in CC and whose law gives CC mass less than λ\lambda: slλ(C)=∑e:xe∈C,μe(C)<λweμe(C).\mathrm{sl}_\lambda(C) = \sum_{e \,:\, x_e \in C,\ \mu_e(C) < \lambda} w_e\, \mu_e(C).(5)✦

Cells at the Places of a Number Field

An ultrametric depth on a finite set PP is a symmetric real function dd on pairs of points of PP such that 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 of a point xx at a level rr is the set Cr(x)C_r(x) made of xx and the points yy with d(x,y)≥rd(x,y) \ge r.✦ A cell is a giant when it holds more than half of the points of PP✦, and GrG_r is the union of the giants at level rr✦. The transformed family 𝒯r\mathcal{T}_r is the multiset of subsets of PP made of the cells at level rr that are not giants and of the complements P\CP \setminus C of the giants CC.✦ The cell mass of a subset CC of PP with at least two points is the total length of the levels at which it occurs in 𝒯r\mathcal{T}_r, md(C)=∫ℝ#{occurrences of C in 𝒯r}dr,m_d(C) = \int_{\mathbb{R}} \#\{\text{occurrences of } C \text{ in } \mathcal{T}_r\}\, dr,(6)✦ 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 there is a giant and x∉Grx \notin G_r.✦

Let ZZ be an injective map of PP into a number field KK. The depth dvd_v at a finite place vv of KK is the function with dv(x,y)=−log⁡|Z(x)−Z(y)|vd_v(x,y) = -\log|Z(x) - Z(y)|_v at distinct points and 00 on the diagonal.✦ A finite place vv is bad when Z(x)−Z(y)Z(x) - Z(y) fails to be a unit at vv for some pair of distinct points xx, yy.✦

At the archimedean places the cells come from a random dyadic grid. A grid sample ω\omega is a phase (ξ,φ)∈ℝ2(\xi, \varphi) \in \mathbb{R}^2 together with two real axis sequences, one for each axis of ℝ2\mathbb{R}^2.✦ Under the law of grid samples the phase is uniform on (0,log⁡2]×(0,2π](0, \log 2] \times (0, 2\pi], the phase and all terms of the two sequences are independent, the term of index 00 is uniform on (0,1](0, 1] and the term of index i+1i + 1 is 00 or 2i2^i with probability 1/21/2 each. At a scale k∈ℤk \in \mathbb{Z} each axis is cut into half-open intervals of length 2k2^k, one of them starting at the sum of the terms of index 00 to max⁡(k,0)\max(k, 0) of its sequence, and two points share a cell at scale kk when they lie in one interval on each axis.✦ The grid depth of two points is −klog⁡2-k \log 2 for the least scale kk at which they share a cell.✦ For a grid sample ω\omega with phase (ξ,φ)(\xi, \varphi) and complex numbers zz and ww, the hierarchy depth of zz and ww is the grid depth for ω\omega of e−ξeiφze^{-\xi} e^{i\varphi} z and e−ξeiφwe^{-\xi} e^{i\varphi} w, read as points of ℝ2\mathbb{R}^2, minus ξ\xi.✦

A grid sample ω\omega is good at an archimedean place vv of KK when the hierarchy depth of the images of the points Z(x)Z(x) under the embedding of KK at vv is ultrametric on PP.✦ The depth dv,ωd_{v,\omega} on PP at an archimedean place vv of KK for a grid sample ω\omega is, at distinct points, the hierarchy depth of the images of the points Z(x)Z(x) under the embedding of KK at vv when ω\omega is good at vv, and 00 otherwise.✦ With the weight σv=mult(v)/[K:ℚ]\sigma_v = \mathrm{mult}(v)/[K:\mathbb{Q}] of an archimedean place, where mult(v)\mathrm{mult}(v) is 11 for a real place and 22 for a complex one, the cell mass of a subset CC of PP for the coordinate ZZ is mZ(C)=∑v∣∞σv𝔼ωmdv,ω(C)+1[K:ℚ]∑v badmdv(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 \text{ bad}} m_{d_v}(C),(7)✦ the mean taken under the law of grid samples, and the potential SZ(x)S_Z(x) of a point is given by the same formula with Sd(x)S_d(x) in place of md(C)m_d(C)✦.

Two injective maps Z1Z_1 and Z2Z_2 of VV into KK give the total cell mass m*=mZ1+mZ2m^* = m_{Z_1} + m_{Z_2} and the total potential S*=SZ1+SZ2S^* = S_{Z_1} + S_{Z_2}; write I=Im*I = I_{m^*} and L*=Lm*L^* = L_{m^*}. The overlap scale W2W_2, the mean overlap 𝔼πL*\mathbb{E}_\pi L^* of a uniform pair of distinct points, the potential scale AA and the small overlap scale W2,smW_{2,\mathrm{sm}}, the part of W2W_2 carried by the small cells, are W2=I(π(C×C)),A=𝔼αS*,W2,sm=I(π(C×C)𝟏[|C|≤n1−c]),W_2 = I(\pi(C \times C)), \qquad A = \mathbb{E}_\alpha S^*, \qquad W_{2,\mathrm{sm}} = I\bigl(\pi(C \times C)\, \mathbf{1}[|C| \le n^{1-c}]\bigr),(8) and W=W2+AW = W_2 + A.

The Claim

For a density θ\theta and an error η\eta, the bounds use the error factors ε(η)=θ+ηθ−η−1,δ(η)=2−2(θ−η)θ+η/8,\varepsilon(\eta) = \frac{\theta + \eta}{\theta - \eta} - 1, \qquad \delta(\eta) = 2 - \frac{2(\theta - \eta)}{\theta + \eta/8},(9) which vanish at η=0\eta = 0, and, for τ>0\tau > 0 and real numbers HH, uu and aa, the function Rλ,η(τ,H;u,a)=(2λτ2+2λθ−η+ε(η))u+(2τθ−η+δ(η))a+4λH+32exp⁡(−H/2).R_{\lambda,\eta}(\tau, H; u, a) = \Bigl(\frac{2\lambda}{\tau^2} + \frac{2\lambda}{\theta - \eta} + \varepsilon(\eta)\Bigr) u + \Bigl(\frac{2\tau}{\theta - \eta} + \delta(\eta)\Bigr) a + 4\lambda H + 32 \exp(-H/2).(10)

Theorem 1. (i) Let GG be a prepared graph on VV, with nn vertices, density θ\theta, exponents γ\gamma and cc and error η\eta, where 0≤η<θ0 \le \eta < \theta, and let λ=1/log⁡n\lambda = 1/\log n. If mm is a cell mass on VV, bb a real number and SS a nonnegative function on VV with Lm(x,y)=b+S(x)+S(y)L_m(x,y) = b + S(x) + S(y) for all distinct vertices xx and yy, then Im(π(C×C))−δ(η)𝔼αS≤Im(q(C×C)),I_m(\pi(C \times C)) - \delta(\eta)\, \mathbb{E}_\alpha S \le I_m(q(C \times C)),(11)✦ and, when mm is moreover nonnegative, θθ−ηIm(π(C×C)𝟏[|C|≤n1−c])≤Im(slλ)+ε(η)Im(π(C×C))+δ(η)𝔼αS.\frac{\theta}{\theta - \eta}\, I_m\bigl(\pi(C \times C)\, \mathbf{1}[|C| \le n^{1-c}]\bigr) \le I_m(\mathrm{sl}_\lambda) + \varepsilon(\eta)\, I_m(\pi(C \times C)) + \delta(\eta)\, \mathbb{E}_\alpha S.(12)✦ If 0≤λ≤1/20 \le \lambda \le 1/2, Z1Z_1 and Z2Z_2 are injective maps of VV into a number field KK such that t(xe,y)t(x_e, y), as in (1), takes one value on the targets yy of each fiber ee, and τ\tau and HH are real numbers with 0<τ≤10 < \tau \le 1, τn≥2\tau n \ge 2 and H≥0H \ge 0, then W2,sm≤Rλ,η(τ,H;W2,A).W_{2,\mathrm{sm}} \le R_{\lambda,\eta}(\tau, H; W_2, A).(13)✦

(ii) Let θ>0\theta > 0 and let njn_j, ηj\eta_j, UjU_j, AjA_j and DjD_j be sequences of real numbers with nj→∞n_j \to \infty, ηj→0\eta_j \to 0 and ηj,Uj,Aj,Dj≥0\eta_j, U_j, A_j, D_j \ge 0. If for every τ∈(0,1]\tau \in (0, 1] and every H≥0H \ge 0 the bound Dj≤R1/log⁡nj,ηj(τ,H;Uj,Aj)D_j \le R_{1/\log n_j,\, \eta_j}(\tau, H; U_j, A_j) holds for all large jj, then, as j→∞j \to \infty, DjUj+Aj+1→0.\frac{D_j}{U_j + A_j + 1} \to 0.(14)✦

(iii) Let θ>0\theta > 0 and, for each jj, let GjG_j be a prepared graph on a vertex set VjV_j with density θ\theta, exponents γ\gamma and cc and error ηj≥0\eta_j \ge 0, and let Z1,jZ_{1,j} and Z2,jZ_{2,j} be injective maps of VjV_j into a number field KjK_j such that t(xe,y)t(x_e, y) takes one value on the targets yy of each fiber ee of GjG_j. If |Vj|→∞|V_j| \to \infty and ηj→0\eta_j \to 0, then the scales W2(j)W_2^{(j)}, A(j)A^{(j)} and W2,sm(j)W_{2,\mathrm{sm}}^{(j)} of Z1,jZ_{1,j} and Z2,jZ_{2,j} satisfy, as j→∞j \to \infty, W2,sm(j)W2(j)+A(j)+1→0.\frac{W_{2,\mathrm{sm}}^{(j)}}{W_2^{(j)} + A^{(j)} + 1} \to 0.(15)✦

In the paper, the result reads: W2−o(1)A≤I(q(C×C))≤B0W2W_2 - o(1)A \le I(q(C \times C)) \le B_0 W_2, its display (4.1), where B0B_0 is the constant of the upper bound, and W2,sm=o(W+1)W_{2,\mathrm{sm}} = o(W + 1), its display (4.5).

What Is Checked

The claim is stated over prepared graphs: in (11) with any cell mass whose overlap is b+S(x)+S(y)b + S(x) + S(y) off the diagonal, for a real number bb and a nonnegative function SS on VV, in (12) with any nonnegative cell mass of that kind, and in (13) and (15) with the total cell mass and the total potential of two injective maps into a number field, tt being constant on each fiber; (14) is stated over sequences of real numbers.

The library proves that the depth at each finite place of KK, and the depth at each archimedean place for every grid sample, are ultrametric depths, and that an injective map ZZ of a finite set into KK has finitely many bad places.