OctoInformBeta

OpenAI preprint, September 2026 · §6. Adaptive exploration and the final contradiction

Lemma 6.2: Finite revelations of bond or site configurations on ℤ3\mathbb Z^3 along a coarse exploration in ℤ2\mathbb Z^2

Rare bad decisions in valid explorations.

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

An adaptive exploration processes vertices of ℤ2\mathbb Z^2 while revealing finite blocks of percolation variables on ℤ3\mathbb Z^3. A pending vertex carries a finite graph in which an open connection from the origin to a relay cube is tested.

Fix a model MM, either bond or site percolation. The cubic lattice ℤ3\mathbb Z^3 consists of integer triples.✦ Write eie_i for its coordinate unit vectors, with i∈{0,1,2}i\in\{0,1,2\}; the positive coordinate step from xx is x+eix+e_i, and nearest-neighbor vertices differ by eie_i or −ei-e_i. A lattice bond (x,i)(x,i) has endpoints xx and x+eix+e_i.✦ The variable set EME_M consists of these bonds in the bond model and of lattice vertices in the site model.✦ A configuration ω∈{0,1}EM\omega\in\{0,1\}^{E_M} assigns an open or closed state to every variable.✦

Open lattice adjacency requires the intervening bond to be open in the bond model, and both nearest-neighbor vertices to be open in the site model.✦ A vertex is available unconditionally in the bond model and precisely when it is open in the site model.✦ On any graph, open site adjacency requires adjacent open vertices; open site connectivity requires a finite path of such adjacencies and open endpoints, including for a path of length zero. A bond path of length zero connects a vertex to itself. Adjacency restricted to a region requires both vertices of each step to belong to that region.✦

A finite lattice graph GG has a finite vertex set V(G)⊂ℤ3V(G)\subset\mathbb Z^3 and a finite bond set E(G)E(G) whose endpoints belong to V(G)V(G).✦ The underlying simple graph of a finite lattice graph GG is the graph that joins two vertices when they are incident to one of the bonds of GG, in either order.✦ Open bond adjacency in GG uses an open bond of E(G)E(G), and open connectivity in GG uses finite paths in this graph under the chosen model. For o∈V(G)o\in V(G) and T⊂ℤ3T\subset\mathbb Z^3, the target connection o↔GTo\stackrel{G}{\longleftrightarrow}T means an open connection in GG to some vertex of T∩V(G)T\cap V(G).✦ Write EM(G)E_M(G) for the graph variables, namely E(G)E(G) in the bond model and V(G)V(G) in the site model.✦

For any variable set EE and parameter family 𝝅∈[0,1]E\boldsymbol\pi\in[0,1]^E, let ℙ𝝅\mathbb P_{\boldsymbol\pi} be the independent Bernoulli product measure with opening probability πe\pi_e at coordinate ee.✦ The notation ℙq\mathbb P_q denotes constant opening probability qq.

Coarse Packets

A lattice box B=[ℓ,u]B=[\ell,u] has coordinatewise ordered corners and contains the integer vertices xx satisfying ℓi≤xi≤ui\ell_i\le x_i\le u_i for every ii. The bonds of a lattice box B=[ℓ,u]B=[\ell,u] are lattice bonds whose endpoints both belong to BB. Write EM(B)E_M(B) for its bonds or vertices, according to MM.✦ A graph contains BB when it contains all these vertices and bonds.✦ The cube of coordinate radius bb centered at cc, and the coarse embedding and cubes at scale rr, are given in (1), where v=(v1,v2)v=(v_1,v_2) is a coarse lattice point: Λb(c)={x∈ℤ3:|xi−ci|≤b for every i},cr(v)=((20r+1)v1,(20r+1)v2,0),Bv=Λ4r(cr(v)),Qv=Λ10r(cr(v)).\begin{aligned} \Lambda_b(c)&=\{x\in\mathbb Z^3: |x_i-c_i|\le b\text{ for every }i\},\\ c_r(v)&=((20r+1)v_1,(20r+1)v_2,0),\\ B_v&=\Lambda_{4r}(c_r(v)),\qquad Q_v=\Lambda_{10r}(c_r(v)). \end{aligned}(1)

The four coarse directions d=0,1,2,3d=0,1,2,3 have outward steps u0=(0,−1)u_0=(0,-1), u1=(1,0)u_1=(1,0), u2=(0,1)u_2=(0,1), and u3=(−1,0)u_3=(-1,0). For coarse vertices v,w∈ℤ2v,w\in\mathbb Z^2, let I(v,w)I(v,w) be the finite set of lattice bonds with one endpoint in QvQ_v and the other in QwQ_w.✦ The interbox variables LM(v,w)L_M(v,w) equal I(v,w)I(v,w) for bonds and the empty set for sites.✦ The block variables and root variables are the finite sets in (2): WM(v,w)=EM(Qv)∪LM(v,w),WM0=EM(Q0)∪⋃d=03LM(0,ud).\begin{aligned} W_M(v,w)&=E_M(Q_v)\cup L_M(v,w),\\ W_M^0&=E_M(Q_0)\cup\bigcup_{d=0}^3 L_M(0,u_d). \end{aligned}(2) For a finite set D⊂ℤ2D\subset\mathbb Z^2, the processed region variables are XM(D)X_M(D) in (3): XM(D)=WM0∪⋃v∈DEM(Qv)∪⋃(v,w)∈D×DLM(v,w).X_M(D)=W_M^0\cup\bigcup_{v\in D}E_M(Q_v) \cup\bigcup_{(v,w)\in D\times D}L_M(v,w).(3)✦

A parent-chain packet t=(vt,pt,Gt)t=(v_t,p_t,G_t) at scale rr is a triple consisting of a coarse vertex vtv_t, a coarse parent vertex ptp_t, and a finite lattice graph GtG_t containing QvtQ_{v_t} and the origin.✦ For a parent-chain packet t=(vt,pt,Gt)t=(v_t,p_t,G_t), the root connection event AtA_t is the event defined by At={ω:0↔GtBvt}A_t=\{\omega:0\stackrel{G_t}{\longleftrightarrow}B_{v_t}\}.✦ For a coarse point xx, the child packet t[x]t[x] has vertex xx, parent vtv_t, and extended graph with vertex set V(Gt)∪V(Qx)V(G_t)\cup V(Q_x) and bond set E(Gt)∪E(Qx)∪I(vt,x)E(G_t)\cup E(Q_x)\cup I(v_t,x).✦

Scale Parameters

The seed variable count NM(m)N_M(m) is |EM(Λm(0))||E_M(\Lambda_m(0))|.✦ A quarter-face index (i,σ)(i,\sigma) is a pair consisting of a coordinate ii and a sign vector σ∈{−1,1}3\sigma\in\{-1,1\}^3.✦ The quarter-face Φi,σ(c,n)\Phi_{i,\sigma}(c,n) associated with coordinate ii and sign vector σ\sigma is the set of lattice vertices defined by (4); these 24 signed-coordinate quarter-faces may overlap on their boundaries: Φi,σ(c,n)={x∈ℤ3:σi(xi−ci)=n,0≤σj(xj−cj)≤n for j≠i}.\Phi_{i,\sigma}(c,n)= \{x\in\mathbb Z^3:\sigma_i(x_i-c_i)=n,\quad 0\le\sigma_j(x_j-c_j)\le n\text{ for }j\ne i\}.(4)✦

The confined seed connection event ℛM(c;a,b;T)\mathcal R_M(c;a,b;T) consists of configurations having an available vertex x∈Λa(c)x\in\Lambda_a(c) joined to some y∈Ty\in T by a finite path of open lattice adjacencies restricted to Λb(c)\Lambda_b(c).✦

Scale parameters for MM are densities 0<p<10<p<1 and p/2<q<pp/2<q<p, allowances δ,η,τ,γ∈(0,1)\delta,\eta,\tau,\gamma\in(0,1), and nonnegative integer scales m,K,R,rm,K,R,r with m>0m>0, K>0K>0, m<Rm<R, and 100(R+1)<r100(R+1)<r. They satisfy the budgets in (5), with fixed contour error tolerance ff, and the face connection requirement (6): f=12(1100)7,δ+52ηδ<f,τ<η4,γ<δ,2γτ<η4,4K(p/2)NM(m)+1<η4,1(1−p)K(8m+5)3(R−m)<η4.\begin{gathered} f=\frac12\left(\frac1{100}\right)^7,\qquad \delta+\frac{52\eta}{\delta}<f,\qquad \tau<\frac\eta4,\qquad \gamma<\delta,\qquad \frac{2\gamma}{\tau}<\frac\eta4,\\ \frac{4}{K(p/2)^{N_M(m)+1}}<\frac\eta4,\qquad \frac{1}{(1-p)^{K(8m+5)^3}(R-m)}<\frac\eta4. \end{gathered}(5) ℙq(ℛM(c;m,n;Φi,σ(c,n)))>1−γ{n∈{2r,2r+1,10r},c∈ℤ3,i∈{0,1,2},σ∈{−1,1}3.\mathbb P_q\bigl(\mathcal R_M(c;m,n;\Phi_{i,\sigma}(c,n))\bigr)>1-\gamma \quad \left\{ \begin{array}{l} n\in\{2r,2r+1,10r\},\\ c\in\mathbb Z^3,\quad i\in\{0,1,2\},\quad\sigma\in\{-1,1\}^3. \end{array} \right.(6)

Histories and Revelations

A finite observation history h=(J,ξ)h=(J,\xi) on EE records a finite known set JJ and a configuration ξ\xi whose values on JJ are the observations.✦ Partial replacement ρJ,ξω\rho_{J,\xi}\omega uses ξ\xi on JJ and ω\omega elsewhere; this is the configuration frozen on hh. For a finite reveal set RR, observing ω\omega gives h[R,ω]=(J∪R,ρR,ωξ)h[R,\omega]=(J\cup R,\rho_{R,\omega}\xi).✦

For an event CC, the pinned parameters 𝝅J,ξ\boldsymbol\pi^{J,\xi} and finite-coordinate conditional probability are defined in (7). The history-product law ℙhq\mathbb P_h^q uses 𝝅J,ξ\boldsymbol\pi^{J,\xi} with πe=q\pi_e=q: πeJ,ξ={ξ(e),e∈J,πe,e∉J,ℙ𝝅(C∣J)(ξ)=ℙ𝝅J,ξ(C).\pi^{J,\xi}_e= \begin{cases} \xi(e),&e\in J,\\ \pi_e,&e\notin J, \end{cases} \qquad \mathbb P_{\boldsymbol\pi}(C\mid J)(\xi) =\mathbb P_{\boldsymbol\pi^{J,\xi}}(C).(7) An event HH is determined by JJ when configurations agreeing on JJ have the same membership in HH; more generally a function is determined by JJ when its value is unchanged between such configurations.✦ The pattern [ξ]J[\xi]_J is the event {ω:ω|J=ξ|J}\{\omega:\omega|_J=\xi|_J\}.✦ The zero extension a‾\bar a of an assignment a∈{0,1}Ja\in\{0,1\}^J is the configuration on EE that agrees with aa on JJ and is closed elsewhere.✦

A coarse exploration state ss at scale rr consists of a history hs=(Js,ξs)h_s=(J_s,\xi_s) on EME_M, a finite processed set DsD_s, an ordered packet queue 𝒬s\mathcal Q_s, and finite good and bad sets of coarse vertices.✦ The visited set VsV_s of a coarse exploration state ss is the set defined by Vs=Ds∪{vt:t∈𝒬s}V_s=D_s\cup\{v_t:t\in\mathcal Q_s\}.✦ The unrevealed block RsR_s of a coarse exploration state ss is the finite set given by Rs=WM(vt,pt)\JsR_s=W_M(v_t,p_t)\setminus J_s when its queue has head tt, and by Rs=⌀R_s=\varnothing when its queue is empty.✦ The history hsωh_s^\omega of a coarse exploration state ss after block revelation at ω\omega is the finite observation history given by hsω=hs[Rs,ω]h_s^\omega=h_s[R_s,\omega]; write ξsω\xi_s^\omega for its value assignment.✦

The candidate list 𝒰s(t)\mathcal U_s(t) consists, in direction order, of the children t[vt+ud]t[v_t+u_d] whose vertices lie outside VsV_s.✦ Packet acceptance is the event 𝒜sq,δ(t)\mathcal A_s^{q,\delta}(t) in (8): 𝒜sq,δ(t)={ω:ξsω∈Atandℙhsωq(Au)>1−δ for every u∈𝒰s(t)}.\mathcal A_s^{q,\delta}(t)= \left\{\omega:\xi_s^\omega\in A_t\ \text{and}\ \mathbb P_{h_s^\omega}^q(A_u)>1-\delta \text{ for every }u\in\mathcal U_s(t)\right\}.(8)✦ The rejected packet indicator βsq,δ(ω)\beta_s^{q,\delta}(\omega) is one when the queue has head tt and ω∉𝒜sq,δ(t)\omega\notin\mathcal A_s^{q,\delta}(t), and zero otherwise.✦ The frozen packet event is Fs,t={ω:ρJs,ξsω∈At}F_{s,t}=\{\omega:\rho_{J_s,\xi_s}\omega\in A_t\}.✦

The single exploration step s⟨ω⟩s\langle\omega\rangle replaces the history by hsωh_s^\omega and, for a nonempty queue with head tt and tail TT, processes vtv_t. Acceptance appends 𝒰s(t)\mathcal U_s(t) to TT and puts vtv_t in the good set; rejection leaves queue TT and puts vtv_t in the bad set. An empty queue leaves the state unchanged.

A state ss is valid at (q,δ)(q,\delta) when the origin is processed, queued vertices are distinct and unprocessed, every queued parent is processed, and (9) holds: Js⊂XM(Ds),EM(Gt)⊂Js∪WM(vt,pt),ℙhsq(At)>1−δfor every t∈𝒬s.\begin{gathered} J_s\subset X_M(D_s),\\ E_M(G_t)\subset J_s\cup W_M(v_t,p_t),\qquad \mathbb P_{h_s}^q(A_t)>1-\delta \quad\text{for every }t\in\mathcal Q_s. \end{gathered}(9)✦

Adaptive Decisions

An adaptive reveal scheme on variables EE and states SS specifies a finite reveal set RsR_s, product parameters 𝝅s\boldsymbol\pi_s, an optional current vertex, and, for each assignment a∈{0,1}Rsa\in\{0,1\}^{R_s}, a bad decision bs(a)b_s(a) and a successor state s[a]s[a]. The successor parameters are obtained from 𝝅s\boldsymbol\pi_s by pinning RsR_s to aa. For an adaptive reveal scheme at state ss, the pattern weights ws(a)w_s(a) and bad mass 𝔟(s)\mathfrak b(s) are the probabilities and weighted sum defined in (10), with bs(a)∈{0,1}b_s(a)\in\{0,1\}: ws(a)=ℙ𝝅s([a‾]Rs),𝔟(s)=∑a∈{0,1}Rsbs(a)ws(a).w_s(a)=\mathbb P_{\boldsymbol\pi_s}([\bar a]_{R_s}),\qquad \mathfrak b(s)=\sum_{a\in\{0,1\}^{R_s}} b_s(a)w_s(a).(10)

The coarse exploration reveal scheme at (q,δ)(q,\delta) uses RsR_s and the history-product parameters of hsh_s. Its current vertex is the head vertex when the queue is nonempty, its bad decision is βsq,δ(a‾)\beta_s^{q,\delta}(\bar a), and its successor is s⟨a‾⟩s\langle\bar a\rangle. Denote its bad mass by 𝔟q,δ(s)\mathfrak b_{q,\delta}(s).

The Claim

Theorem 1. For any coarse exploration state ss, q∈[0,1]q\in[0,1], and δ∈ℝ\delta\in\mathbb R, the bad mass satisfies (11): 𝔟q,δ(s)=ℙhsq{ω:βsq,δ(ω)=1}.\mathfrak b_{q,\delta}(s)= \mathbb P_{h_s}^q\{\omega:\beta_s^{q,\delta}(\omega)=1\}.(11)✦

Take scale parameters for MM and a state ss valid at (q,δ)(q,\delta). Suppose its queue has head tt, and x=vt+udx=v_t+u_d is unvisited. The relay failure estimate is (12): ℙhsq(Fs,t∩At[x]c)≤13η.\mathbb P_{h_s}^q\bigl(F_{s,t}\cap A_{t[x]}^{\mathrm c}\bigr)\le13\eta.(12)✦ For every valid state at these scale parameters, (13) holds: 𝔟q,δ(s)≤f.\mathfrak b_{q,\delta}(s)\le f.(13)✦

Let EE be a variable set, 𝝅∈[0,1]E\boldsymbol\pi\in[0,1]^E, and J⊂EJ\subset E finite, and let ϵ\epsilon be a real number. Suppose HH is determined by JJ, CC is measurable, α>0\alpha>0, and ℙ𝝅(H∩Cc)≤ϵ\mathbb P_{\boldsymbol\pi}(H\cap C^{\mathrm c})\le\epsilon. Then the finite-coordinate conditional failure estimate is (14): ℙ𝝅{ω∈H:ℙ𝝅(C∣J)(ω)≤1−α}≤ϵα.\mathbb P_{\boldsymbol\pi} \{\omega\in H:\mathbb P_{\boldsymbol\pi}(C\mid J)(\omega)\le1-\alpha\} \le\frac\epsilon\alpha.(14)✦

In the paper, the result reads: immediately before any pending vertex of the exploration is processed, its conditional probability of being declared bad is less than ff.

What Is Checked

The statements concern finite graph packets containing the origin and their assigned cubes, valid coarse exploration states, and Bernoulli product laws with finitely many pinned coordinates.