OctoInformBeta

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

Lemma 6.3: Eventual bad declarations and finite targets in adaptive reveal schemes under conditioned Bernoulli laws

Bad coarse vertices have a joint bound.

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

A coarse exploration tests vertices of ℤ2\mathbb Z^2 using connections in finite subgraphs of the nearest-neighbor lattice ℤ3\mathbb Z^3. The test at a vertex depends on the observations already made and on a finite set of newly revealed variables. The bad events concern rejection of specified vertices during this exploration.

Fix a model MM, either bond or site percolation. A lattice bond (x,i)(x,i) joins x∈ℤ3x\in\mathbb Z^3 to its positive coordinate step x+eix+e_i, where eie_i is the iith coordinate unit vector.✦ Bond endpoint incidence relates a lattice bond (x,i)(x,i) to the pair of vertices xx and x+eix+e_i, in either order.✦ A configuration ω\omega assigns each bond, in the bond model, or each vertex, in the site model, a state in {0,1}\{0,1\}, with 11 meaning open.✦ Open lattice adjacency means nearest-neighbor adjacency with the joining bond open, or with both vertices open, respectively.✦ A vertex is available unconditionally in the bond model and precisely when it is open in the site model.✦

A lattice box BB in ℤ3\mathbb Z^3 is a coordinate interval with ordered lower and upper corners.✦ Its vertices include the boundary, and its bonds have both endpoints in the box. Write EM(B)E_M(B) for its bonds or vertices according to MM.✦ A finite lattice subgraph G=(VG,EG)G=(V_G,E_G) has finite vertex and bond sets, with both endpoints of each bond in VGV_G; write EM(G)E_M(G) for its percolation variables. The underlying simple graph of a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) is the graph with vertex set VGV_G and adjacency given by bond endpoint incidence.✦ Open connectivity $\xleftrightarrow[G]{\omega}$ is the relation on vertices of GG given by paths within GG: successive vertices share an open bond in the bond model and are adjacent open vertices in the site model.✦ A bond path of length zero connects a vertex to itself; a site path of length zero requires that vertex to be open. A connection from x∈VGx\in V_G to a target TT means a connection within GG to some vertex of T∩VGT\cap V_G.✦ A lattice box BB is contained in a finite lattice subgraph GG when both its vertices and its bonds belong to GG.✦

For a lattice center uu and coordinate radius bb, the lattice cube Λb(u)\Lambda_b(u) is the coordinate interval in (1).✦ For a coarse vertex v=(v1,v2)v=(v_1,v_2), the center cr(v)c_r(v) and the relay and surrounding cubes Bv,QvB_v,Q_v at scale rr are also specified there. Λb(u)={x∈ℤ3:|xi−ui|≤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(u)&=\{x\in\mathbb Z^3: |x_i-u_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 unit vectors ada_d equal to (0,−1),(1,0),(0,1),(−1,0)(0,-1),(1,0),(0,1),(-1,0) in that order.✦ For coarse vertices v,w∈ℤ2v,w\in\mathbb Z^2, the interface ℐv,w\mathcal I_{v,w} is the set of lattice bonds with one endpoint in QvQ_v and the other in QwQ_w.✦ The interbox variables Lv,wL_{v,w} are ℐv,w\mathcal I_{v,w} for bonds and the empty set for sites.✦ The block variables Dv,wD_{v,w}, root variables D0D_0, and processed region variables ℰ(A)\mathcal E(A) for finite A⊂ℤ2A\subset\mathbb Z^2 are the finite sets in (2). Dv,w=EM(Qv)∪Lv,w,D0=EM(Q0)∪⋃d=03L0,ad,ℰ(A)=D0∪⋃v∈AEM(Qv)∪⋃v,w∈ALv,w.\begin{aligned} D_{v,w}&=E_M(Q_v)\cup L_{v,w},\\ D_0&=E_M(Q_0)\cup\bigcup_{d=0}^3L_{0,a_d},\\ \mathcal E(A)&=D_0\cup\bigcup_{v\in A}E_M(Q_v) \cup\bigcup_{v,w\in A}L_{v,w}. \end{aligned}(2)

Scale Parameters and Conditioned Laws

For a family π=(πe)\pi=(\pi_e) of opening probabilities, ℙπ\mathbb P_\pi is the independent Bernoulli product measure on configurations.✦ Write ℙq\mathbb P_q when all parameters equal qq. A finite observation history h=(J,ξ)h=(J,\xi) consists of a finite known set JJ and a configuration ξ\xi whose values on JJ record the observations.✦ The finite pattern [ξ]J[\xi]_J consists of configurations agreeing with ξ\xi on JJ.✦ Pinning π\pi to this pattern gives the parameters πJ,ξ\pi^{J,\xi} in (3)✦; the history-conditioned law is ℙh,q=ℙqJ,ξ\mathbb P_{h,q}=\mathbb P_{q^{J,\xi}}. [ξ]J={ω:ω|J=ξ|J},πeJ,ξ={ξ(e),e∈J,πe,e∉J.[\xi]_J=\{\omega:\omega|_J=\xi|_J\},\qquad \pi^{J,\xi}_e= \begin{cases} \xi(e),&e\in J,\\ \pi_e,&e\notin J. \end{cases}(3) For configurations ξ,ω\xi,\omega and a finite set RR of percolation variables, the partial replacement ξR←ω\xi^{R\leftarrow\omega} is the configuration equal to ω\omega on RR and to ξ\xi elsewhere.✦ For a finite observation history h=(J,ξ)h=(J,\xi), the extension by observations on a finite set RR is the history h⊕(R,ω)=(J∪R,ξR←ω)h\mathbin{\oplus}(R,\omega)=(J\cup R,\xi^{R\leftarrow\omega}).✦

A quarter-face index α=(i,σ)\alpha=(i,\sigma) is a pair consisting of a coordinate ii and a choice of sign σj∈{−1,1}\sigma_j\in\{-1,1\} for each coordinate.✦ For a lattice center cc, a radius nn, and a quarter-face index α\alpha, the quarter-face Fα(c,n)F_\alpha(c,n) of Λn(c)\Lambda_n(c) is the set of lattice vertices in (4).✦ These 24 signed-coordinate quarter-faces may overlap on their boundaries. Fα(c,n)={x∈ℤ3:σi(xi−ci)=n,0≤σj(xj−cj)≤n(j≠i)}.F_\alpha(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\ (j\ne i)\}.(4) For radii a,ba,b, a lattice center cc, and a target set T⊆ℤ3T\subseteq\mathbb Z^3, the confined seed connection event 𝒮a,b(c,T)\mathcal S_{a,b}(c,T) consists of configurations with an available vertex in Λa(c)\Lambda_a(c) connected to a vertex of TT by open lattice adjacencies restricted to Λb(c)\Lambda_b(c).✦ Restricted adjacency requires both adjacent vertices to lie in this cube.✦

Admissible scale parameters consist of densities p,qp,q, error allowances δ,η,τ,γ\delta,\eta,\tau,\gamma, and integer scales m,K,R,rm,K,R,r satisfying (5). Here mm is the seed radius, KK the trial count, N=|EM(Λm(0))|N=|E_M(\Lambda_m(0))| the seed variable count, and ε\varepsilon the contour error tolerance. The difference R−mR-m is taken in the nonnegative integers. 0<p<1,q∈[0,1],p/2<q<p,δ,η,τ,γ∈(0,1),m,K,R,r∈ℕ,m>0,K>0,m<R,100(R+1)<r,ε=12(1100)7,δ+52ηδ<ε,τ<η4,γ<δ,2γτ<η4,4K(p/2)N+1<η4,1(1−p)K(8m+5)3(R−m)<η4,ℙq(𝒮m,n(c,Fα(c,n)))>1−γ(n∈{2r,2r+1,10r},c∈ℤ3,α).\begin{gathered} 0<p<1,\qquad q\in[0,1],\qquad p/2<q<p,\qquad \delta,\eta,\tau,\gamma\in(0,1),\\ m,K,R,r\in\mathbb N,\qquad m>0,\quad K>0,\quad m<R,\quad100(R+1)<r,\\ \varepsilon=\frac12\left(\frac1{100}\right)^7,\qquad \delta+\frac{52\eta}{\delta}<\varepsilon,\qquad \tau<\frac\eta4,\quad\gamma<\delta,\quad\frac{2\gamma}{\tau}<\frac\eta4,\\ \frac4{K(p/2)^{N+1}}<\frac\eta4,\qquad \frac1{(1-p)^{K(8m+5)^3}(R-m)}<\frac\eta4,\\ \mathbb P_q\bigl(\mathcal S_{m,n}(c,F_\alpha(c,n))\bigr)>1-\gamma \quad(n\in\{2r,2r+1,10r\},\ c\in\mathbb Z^3,\ \alpha). \end{gathered}(5)

The Exploration and Its Tests

A parent-chain packet t=(v,w,G)t=(v,w,G) consists of a coarse vertex vv, a parent ww, and a finite lattice graph GG containing QvQ_v and the lattice origin; write v(t)=vv(t)=v, w(t)=ww(t)=w, and Gt=GG_t=G for its components.✦ The root connection event AtA_t of a parent-chain packet t=(v,w,G)t=(v,w,G) is the event in (6) of a connection within GG from the lattice origin to the relay cube BvB_v.✦ $$A_t=\{\omega:\text{there is }y\in B_v\cap V_G \text{ with }0\xleftrightarrow[G]{\omega}y\}.$$(6) The child packet t[x]t[x] has vertex xx, parent vv, and the extended graph G′G' in (7), where VQxV_{Q_x} and EQxE_{Q_x} denote the vertex and bond sets of QxQ_x.✦ VG′=VG∪VQx,EG′=EG∪EQx∪ℐv,x.V_{G'}=V_G\cup V_{Q_x},\qquad E_{G'}=E_G\cup E_{Q_x}\cup\mathcal I_{v,x}.(7)

An exploration state ss consists of a finite history hs=(Js,ξs)h_s=(J_s,\xi_s), a finite processed set PsP_s, an ordered queue 𝒬s\mathcal Q_s of packets, and finite good and bad sets Gs,Bs⊂ℤ2G_s,B_s\subset\mathbb Z^2.✦ The visited set of an exploration state ss is the set Ps∪{v(t):t∈𝒬s}P_s\cup\{v(t):t\in\mathcal Q_s\}.✦ For an exploration state ss and a packet tt, the candidate list 𝒩s(t)\mathcal N_s(t) is the ordered list of children t[v(t)+ad]t[v(t)+a_d] whose vertices are outside the visited set of ss, in direction order.✦ For an exploration state ss with a nonempty queue headed by tt, the set of unrevealed variables is ℛs=Dv(t),w(t)\Js\mathcal R_s=D_{v(t),w(t)}\setminus J_s; when the queue is empty, ℛs=⌀\mathcal R_s=\varnothing.✦ The history after block revelation is hsω=hs⊕(ℛs,ω)h_s^\omega=h_s\mathbin{\oplus}(\mathcal R_s,\omega), with value configuration ξsω\xi_s^\omega.✦

Packet acceptance 𝒜s(t)\mathcal A_s(t) is the event in (8). 𝒜s(t)={ω:ξsω∈At and ℙhsω,q(Au)>1−δ for every u∈𝒩s(t)}.\mathcal A_s(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 N_s(t)\right\}.(8)✦ The rejection indicator is zero for an empty queue and otherwise equals one precisely outside 𝒜s(t)\mathcal A_s(t) for its head tt.✦

A single exploration step replaces the history by hsωh_s^\omega, removes the queue head tt, and adds v(t)v(t) to the processed set. On acceptance it adds v(t)v(t) to the good set and appends 𝒩s(t)\mathcal N_s(t) to the queue; on rejection it adds v(t)v(t) to the bad set. An empty queue leaves the state unchanged. Let sn(ω)s_n(\omega) be the state after nn steps from ss, using the same configuration at every step and starting with s0(ω)=ss_0(\omega)=s.✦ The eventually bad vertex event ℬs(v)\mathcal B_s(v) is defined by (9). ℬs(v)={ω:there is n≥0 with v∈Bsn(ω)}.\mathcal B_s(v)=\{\omega:\text{there is }n\ge0 \text{ with }v\in B_{s_n(\omega)}\}.(9)✦

A colored state ss is an exploration state with Ps=Gs∪BsP_s=G_s\cup B_s and Gs∩Bs=⌀G_s\cap B_s=\varnothing.✦ A valid state ss at (q,δ)(q,\delta) is an exploration state whose processed set contains the origin, whose queued vertices are distinct and unprocessed, and whose queued parents are processed, subject also to (10).✦ Js⊆ℰ(Ps),EM(Gt)⊆Js∪Dv(t),w(t),ℙhs,q(At)>1−δ(t∈𝒬s).\begin{gathered} J_s\subseteq\mathcal E(P_s),\\ E_M(G_t)\subseteq J_s\cup D_{v(t),w(t)},\qquad \mathbb P_{h_s,q}(A_t)>1-\delta\quad(t\in\mathcal Q_s). \end{gathered}(10)

Adaptive Reveal Schemes

An adaptive reveal scheme 𝒫\mathcal P on variables EE, target labels VV, and states SS assigns to each state ss a finite reveal set Rs⊂ER_s\subset E, Bernoulli parameters πs\pi_s, and either a current label vs∈Vv_s\in V or no current label. For each pattern a∈{0,1}Rsa\in\{0,1\}^{R_s} it specifies a bad indicator bs(a)b_s(a) and a next state Ts(a)T_s(a). Its parameter update is the pinning condition in (11). Write [a]Rs[a]_{R_s} for the event of agreement with aa on RsR_s.✦ The pattern weight ws(a)w_s(a) and bad outcome probability β(s)\beta(s) are also defined in (11). πTs(a)=πsRs,a,ws(a)=ℙπs([a]Rs),β(s)=∑a∈{0,1}Rs𝟏{bs(a)=1}ws(a).\begin{aligned} \pi_{T_s(a)}&=\pi_s^{R_s,a},\\ w_s(a)&=\mathbb P_{\pi_s}([a]_{R_s}),\qquad \beta(s)=\sum_{a\in\{0,1\}^{R_s}}\mathbf1_{\{b_s(a)=1\}}w_s(a). \end{aligned}(11)

The timed bad target event Hn𝒫(s,U)H_n^{\mathcal P}(s,U), for finite U⊂VU\subset V, is the configuration event defined recursively in (12). Here Ω={0,1}E\Omega=\{0,1\}^E, and a=ω|Rsa=\omega|_{R_s} in the last line. H0𝒫(s,U)={Ω,U=⌀,⌀,U≠⌀,Hn+1𝒫(s,U)={H0𝒫(s,U),if there is no current label,{ω:(v∈U⇒bs(a)=1),ω∈Hn𝒫(Ts(a),U\{v})},vs=v.\begin{aligned} H_0^{\mathcal P}(s,U)&= \begin{cases}\Omega,&U=\varnothing,\\\varnothing,&U\ne\varnothing,\end{cases}\\ H_{n+1}^{\mathcal P}(s,U)&= \begin{cases} H_0^{\mathcal P}(s,U),&\text{if there is no current label},\\ \{\omega:(v\in U\Rightarrow b_s(a)=1),\ \omega\in H_n^{\mathcal P}(T_s(a),U\setminus\{v\})\},&v_s=v. \end{cases} \end{aligned}(12)✦ The coarse exploration scheme 𝒫q,δ\mathcal P_{q,\delta} is an adaptive reveal scheme on exploration states, with reveal set ℛs\mathcal R_s, parameters from hsh_s and qq, and the queue head’s vertex as its current label, with no current label for an empty queue. The zero extension a‾\bar a of a revealed pattern aa on ℛs\mathcal R_s is the configuration equal to aa on ℛs\mathcal R_s and closed elsewhere. For the coarse exploration scheme 𝒫q,δ\mathcal P_{q,\delta} at state ss and revealed pattern aa, the bad indicator is the rejection indicator evaluated at the zero extension a‾\bar a, and the next state is the single exploration step evaluated at a‾\bar a.

The Claim

Theorem 1. Fix a bond or site model MM and admissible scale parameters as in (5). Let ss be a valid exploration state at (q,δ)(q,\delta) and let U⊂ℤ2U\subset\mathbb Z^2 be finite and deterministic. Then ℙhs,q(⋃n≥0Hn𝒫q,δ(s,U))≤ε|U|.\mathbb P_{h_s,q}\left(\bigcup_{n\ge0} H_n^{\mathcal P_{q,\delta}}(s,U)\right) \le\varepsilon^{|U|}.(13)✦ If ss is also colored and Bs=⌀B_s=\varnothing, then ℙhs,q(⋂v∈Uℬs(v))≤ε|U|.\mathbb P_{h_s,q}\left(\bigcap_{v\in U}\mathcal B_s(v)\right) \le\varepsilon^{|U|}.(14)✦ For a general adaptive reveal scheme 𝒫\mathcal P, let f≥0f\ge0 and let I⊂SI\subset S be a class of states with β(s)≤f\beta(s)\le f for every s∈Is\in I. Assume that Ts(a)∈IT_s(a)\in I whenever s∈Is\in I and ws(a)>0w_s(a)>0. For s∈Is\in I and finite deterministic U⊂VU\subset V, ℙπs(⋃n≥0Hn𝒫(s,U))≤f|U|.\mathbb P_{\pi_s}\left(\bigcup_{n\ge0}H_n^{\mathcal P}(s,U)\right) \le f^{|U|}.(15)✦

In the paper, the result reads: for every deterministic set of kk distinct coarse vertices, the probability under the paper’s conditioned Bernoulli law ℙI\mathbb P_I that all are processed and declared bad is at most fkf^k.

What Is Checked

The bounds (14) and (13) are stated over finite observation histories and valid bond or site exploration states with admissible scale parameters, with the coloring and empty initial bad set required in (14); the bound (15) is stated over adaptive reveal schemes and classes of states closed under transitions of positive pattern weight.

The graph of a child packet contains the original packet graph, the surrounding cube at the child vertex, and the lattice origin.