OctoInformBeta

OpenAI preprint, September 2026 · §3. Arithmetic and nested partitions · §3

§3 (setting): random nested grids and depths: Shifted dyadic squares under a uniform rotation and phase define the depth dd of a pair, its error Δ\Delta and its mean κ\kappa

Random nested dyadic grids and the depth of a pair.

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

Take two points zz and ww of the complex plane and look for the smallest square holding both in a random hierarchy of dyadic squares. For every integer mm a grid of squares of side 2m2^m is shifted at random, and before the grids are laid down the plane is turned by a uniform angle and contracted by e−ξe^{-\xi}, with a uniform phase ξ\xi. Minus the logarithm of the side of that smallest square, measured in the original plane, is the depth d(z,w)d(z,w) of the pair, a hierarchical counterpart of −log⁡|z−w|-\log|z-w|.

The library builds the random shifts from independent increments, defines the depth dd, its grid error Δ\Delta and the mean κ\kappa of that error, and states two almost sure facts about the squares and the depth.

Shifted Dyadic Grids

For a real ℓ>0\ell>0, the uniform law U(0,ℓ]U(0,\ell] on (0,ℓ](0,\ell] is the probability measure obtained from Lebesgue measure restricted to that interval by dividing by ℓ\ell, and the fair step of size ℓ\ell is the law on ℝ\mathbb{R} giving each of 00 and ℓ\ell probability 12\tfrac12.✦ The axis law ℙaxis\mathbb{P}_{\mathrm{axis}} is the law of a real sequence a=(an)n≥0a=(a_n)_{n\ge 0} with independent terms, a0a_0 uniform on (0,1](0,1] and ana_n a fair step of size 2n−12^{n-1} for n≥1n\ge 1: ℙaxis=U(0,1]⊗⨂n≥1(12δ0+12δ2n−1).\mathbb{P}_{\mathrm{axis}} =U(0,1]\otimes\bigotimes_{n\ge 1}\Bigl(\tfrac12\,\delta_0+\tfrac12\,\delta_{2^{n-1}}\Bigr).(1)✦ At a level m∈ℤm\in\mathbb{Z}, the offset hm(a)h_m(a) of such a sequence is the partial sum hm(a)=a0+a1+…+am(m≥0),hm(a)=a0(m<0).h_m(a)=a_0+a_1+\dots+a_m \quad (m\ge 0),\qquad h_m(a)=a_0 \quad (m<0).(2)✦ A grid sample is a pair ω=(a,b)\omega=(a,b) of real sequences, aa for the first axis and bb for the second✦, and the grid law makes the two sequences independent, each with the axis law: ℙgrid=ℙaxis⊗ℙaxis.\mathbb{P}_{\mathrm{grid}}=\mathbb{P}_{\mathrm{axis}}\otimes\mathbb{P}_{\mathrm{axis}}.(3)✦

On a line, the grid of side ℓ\ell and offset hh cuts ℝ\mathbb{R} into the intervals [h+kℓ,h+(k+1)ℓ)[h+k\ell,\,h+(k+1)\ell), k∈ℤk\in\mathbb{Z}, and a real xx lies in the one of index ⌊(x−h)/ℓ⌋\lfloor (x-h)/\ell\rfloor.✦ Two points x=(x1,x2)x=(x_1,x_2) and y=(y1,y2)y=(y_1,y_2) of ℝ2\mathbb{R}^2 share level mm under ω\omega, written x∼m,ωyx\sim_{m,\omega}y, when they lie in one square of the grid of side 2m2^m with offsets hm(a)h_m(a) and hm(b)h_m(b): ⌊x1−hm(a)2m⌋=⌊y1−hm(a)2m⌋and⌊x2−hm(b)2m⌋=⌊y2−hm(b)2m⌋.\Bigl\lfloor\frac{x_1-h_m(a)}{2^m}\Bigr\rfloor=\Bigl\lfloor\frac{y_1-h_m(a)}{2^m}\Bigr\rfloor \quad\text{and}\quad \Bigl\lfloor\frac{x_2-h_m(b)}{2^m}\Bigr\rfloor=\Bigl\lfloor\frac{y_2-h_m(b)}{2^m}\Bigr\rfloor.(4)✦ The shared level mω(x,y)m_\omega(x,y) of xx and yy under ω\omega is the least level at which they share a square: mω(x,y)=inf⁡{m∈ℤ:x∼m,ωy}.m_\omega(x,y)=\inf\{m\in\mathbb{Z} : x\sim_{m,\omega}y\}.(5)✦

Rotation and Phase

The phase law ℙphase=U(0,log⁡2]⊗U(0,2π]\mathbb{P}_{\mathrm{phase}}=U(0,\log 2]\otimes U(0,2\pi] is the law of a pair (ξ,φ)(\xi,\varphi) of independent reals, the phase ξ\xi uniform on (0,log⁡2](0,\log 2] and the angle φ\varphi uniform on (0,2π](0,2\pi].✦ A full sample is a triple (ξ,φ,ω)(\xi,\varphi,\omega) of a phase, an angle and a grid sample✦, and its law is ℙ=ℙphase⊗ℙgrid.\mathbb{P}=\mathbb{P}_{\mathrm{phase}}\otimes\mathbb{P}_{\mathrm{grid}}.(6)✦ The rotation Rξ,φR_{\xi,\varphi} of phase ξ\xi and angle φ\varphi is the map from ℂ\mathbb{C} to ℝ2\mathbb{R}^2 sending zz to the real and imaginary parts of e−ξeiφze^{-\xi}e^{i\varphi}z: Rξ,φ(z)=(Re⁡(e−ξeiφz),Im⁡(e−ξeiφz)).R_{\xi,\varphi}(z)=\bigl(\operatorname{Re}(e^{-\xi}e^{i\varphi}z),\, \operatorname{Im}(e^{-\xi}e^{i\varphi}z)\bigr).(7)✦

The Claim

Definition 1. Let ω\omega be a grid sample and x,yx,y points of ℝ2\mathbb{R}^2. The grid depth of xx and yy is dωgrid(x,y)=−mω(x,y)log⁡2.d^{\mathrm{grid}}_\omega(x,y)=-\,m_\omega(x,y)\log 2.(8)✦ Let (ξ,φ,ω)(\xi,\varphi,\omega) be a full sample and z,wz,w points of ℂ\mathbb{C}. The depth d(z,w)d(z,w) is the grid depth of the rotated points less the phase, and the grid error Δ(z,w)\Delta(z,w) is the excess of the depth over the raw depth −log⁡|z−w|-\log|z-w|: d(z,w)=dωgrid(Rξ,φ(z),Rξ,φ(w))−ξ,d(z,w)=d^{\mathrm{grid}}_\omega\bigl(R_{\xi,\varphi}(z),R_{\xi,\varphi}(w)\bigr)-\xi,(9)✦ Δ(z,w)=d(z,w)+log⁡|z−w|.\Delta(z,w)=d(z,w)+\log|z-w|.(10)✦ For reals tt and φ\varphi, the polar mean M(t,φ)M(t,\varphi) is the expected grid depth of the origin and the point et(cos⁡φ,sin⁡φ)e^{t}(\cos\varphi,\sin\varphi), plus tt, and the mean error κ\kappa is the average of M(−ξ,φ)M(-\xi,\varphi) over the phase and the angle: M(t,φ)=∫dωgrid((0,0),et(cos⁡φ,sin⁡φ))dℙgrid(ω)+t,M(t,\varphi)=\int d^{\mathrm{grid}}_\omega\bigl((0,0),\,e^{t}(\cos\varphi,\sin\varphi)\bigr)\, d\mathbb{P}_{\mathrm{grid}}(\omega)+t,(11)✦ κ=12πlog⁡2∫0log⁡2∫02πM(−ξ,φ)dφdξ.\kappa=\frac{1}{2\pi\log 2}\int_0^{\log 2}\!\!\int_0^{2\pi}M(-\xi,\varphi)\,d\varphi\,d\xi.(12)✦

In the paper, the setting reads: a random orientation, a logarithmic phase ξ\xi uniform on [0,log⁡2)[0,\log 2) and nested shifted square grids of side eξ2me^{\xi}2^m, with dj(x,y)d_j(x,y) being minus the logarithm of the smallest side shared by xx and yy and Δj=dj−ij\Delta_j=d_j-i_j, where xx and yy are vertices, ZjZ_j is the jj-th coordinate of a vertex as a complex number and jj indexes these coordinates, and djd_j, Δj\Delta_j and the raw depth ij(x,y)i_j(x,y) are the page’s dd, Δ\Delta and −log⁡|z−w|-\log|z-w| at z=Zj(x)z=Z_j(x) and w=Zj(y)w=Z_j(y).

Theorem 1. Let mm be an integer and x,yx,y points of ℝ2\mathbb{R}^2. For ℙgrid\mathbb{P}_{\mathrm{grid}}-almost every grid sample ω\omega, sharing level mm implies sharing level m+1m+1: x∼m,ωy⇒x∼m+1,ωy.x\sim_{m,\omega}y\ \Longrightarrow\ x\sim_{m+1,\omega}y.(13)✦ Let z1,z2,z3z_1,z_2,z_3 be pairwise distinct points of ℂ\mathbb{C}. For ℙ\mathbb{P}-almost every full sample, the depth satisfies the ultrametric inequality d(z1,z3)≥min⁡(d(z1,z2),d(z2,z3)).d(z_1,z_3)\ge\min\bigl(d(z_1,z_2),\,d(z_2,z_3)\bigr).(14)✦

What Is Checked

The definitions and the theorem are stated over points of ℝ2\mathbb{R}^2 for the grids and of ℂ\mathbb{C} for the depth, under the grid law ℙgrid\mathbb{P}_{\mathrm{grid}} on pairs of real sequences and the full law ℙ\mathbb{P} on phases, angles and grid samples, both built from uniform laws and fair steps.