OctoInformBeta

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

§6 (setting): Finite connection packets and conditional promises in a coarse lattice queue

Exploration from an all-open root.

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

The exploration concerns origin connections through cubes of ℤ3\mathbb Z^3, indexed by the coarse lattice ℤ2\mathbb Z^2. Its decisions depend on the percolation variables already observed and on conditional probabilities for cubes awaiting inspection.

Fix a bond or site model 𝖬\mathsf M and an integer scale r≥0r\geq0. The variable set E𝖬E_{\mathsf M} of the percolation model 𝖬\mathsf M is the set of lattice bonds in the bond model and the set of lattice vertices in the site model.✦ A configuration ω∈{0,1}E𝖬\omega\in\{0,1\}^{E_{\mathsf M}} assigns closed or open states, respectively.✦ A lattice bond (x,i)(x,i) has endpoints xx and x+eix+e_i, where eie_i is a positive coordinate unit vector; incidence with two vertices disregards their order.

A lattice box H=[ℓ,u]∩ℤ3H=[\ell,u]\cap\mathbb Z^3 has coordinatewise ordered corners.✦ Its vertex set is V(H)=HV(H)=H✦, and its bonds E(H)E(H) are those with both endpoints in HH.✦ For c∈ℤ3c\in\mathbb Z^3 and a nonnegative integer radius bb, the cube Λb(c)\Lambda_b(c) is the lattice box with corners c−bc-b and c+bc+b coordinatewise.✦ For a coarse vertex v=(v1,v2)v=(v_1,v_2), the center and the two associated cubes are (1). cr(v)=((20r+1)v1,(20r+1)v2,0),Bv=Λ4r(cr(v)),Qv=Λ10r(cr(v)).c_r(v)=((20r+1)v_1,(20r+1)v_2,0),\qquad B_v=\Lambda_{4r}(c_r(v)),\qquad Q_v=\Lambda_{10r}(c_r(v)).(1) The four coarse directions have outward vectors Δ0=(0,−1)\Delta_0=(0,-1), Δ1=(1,0)\Delta_1=(1,0), Δ2=(0,1)\Delta_2=(0,1) and Δ3=(−1,0)\Delta_3=(-1,0).✦

Finite Connections and Revealed Variables

A finite lattice subgraph G=(VG,EG)G=(V_G,E_G) consists of finite vertex and bond sets with both endpoints of every edge in VGV_G.✦ The underlying simple graph of a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) is the graph on VGV_G in which two vertices are adjacent when they are incident to an edge of EGE_G.✦ Open bond adjacency in a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) is the relation between two vertices that are incident to an open edge of EGE_G. Open site adjacency requires adjacent vertices to be open.✦ Write x↔Gyx\leftrightarrow_G y for connectivity by a finite open path in GG under 𝖬\mathsf M and the configuration in question.✦ A bond path may have length zero; a site path requires every vertex, including both endpoints, to be open even at length zero. A target connection o↔GTo\leftrightarrow_G T means o↔Gyo\leftrightarrow_G y for some y∈VG∩Ty\in V_G\cap T.✦

The box graph G(H)G(H) has vertex set V(H)V(H) and edge set E(H)E(H).✦ Containment H⊆GH\subseteq G means V(H)⊆VGV(H)\subseteq V_G and E(H)⊆EGE(H)\subseteq E_G.✦ The percolation variables β𝖬(G)\beta_{\mathsf M}(G) of GG are EGE_G in the bond model and VGV_G in the site model✦; write β𝖬(H)=β𝖬(G(H))\beta_{\mathsf M}(H)=\beta_{\mathsf M}(G(H)) for a box.

The interface I(v,w)I(v,w) is the set of lattice bonds with one endpoint in QvQ_v and the other in QwQ_w.✦ The interbox variables L𝖬(v,w)L_{\mathsf M}(v,w) between the cubes QvQ_v and QwQ_w form the set I(v,w)I(v,w) in the bond model and the empty set in the site model.✦ For coarse vertices v,a∈ℤ2v,a\in\mathbb Z^2 and a finite coarse set PP, the block variables J(v,a)J(v,a), root variables RR and processed region variables X(P)X(P) are the finite sets in (2). J(v,a)=β𝖬(Qv)∪L𝖬(v,a),R=β𝖬(Q0)∪⋃d=03L𝖬(0,Δd),X(P)=R∪⋃v∈Pβ𝖬(Qv)∪⋃v,w∈PL𝖬(v,w).\begin{aligned} J(v,a)&=\beta_{\mathsf M}(Q_v)\cup L_{\mathsf M}(v,a),\\ R&=\beta_{\mathsf M}(Q_0)\cup \bigcup_{d=0}^{3}L_{\mathsf M}(0,\Delta_d),\\ X(P)&=R\cup\bigcup_{v\in P}\beta_{\mathsf M}(Q_v) \cup\bigcup_{v,w\in P}L_{\mathsf M}(v,w). \end{aligned}(2)

For a finite lattice subgraph GG and coarse vertices v,xv,x with Qv⊆GQ_v\subseteq G, the graph extension F(G,v,x)F(G,v,x) is the finite lattice graph obtained by adding the box QxQ_x and its interface with QvQ_v, as specified in (3). VF(G,v,x)=VG∪V(Qx),EF(G,v,x)=EG∪E(Qx)∪I(v,x).V_{F(G,v,x)}=V_G\cup V(Q_x),\qquad E_{F(G,v,x)}=E_G\cup E(Q_x)\cup I(v,x).(3)✦

The Definition

Definition 1. A finite observation history hh for E𝖬E_{\mathsf M} is a pair as in (4), where KK is the set of recorded variables and ξ\xi is a configuration. h=(K,ξ),K⊆E𝖬 finite,ξ∈{0,1}E𝖬.h=(K,\xi),\qquad K\subseteq E_{\mathsf M}\text{ finite},\qquad \xi\in\{0,1\}^{E_{\mathsf M}}.(4)✦ For a finite set U⊆E𝖬U\subseteq E_{\mathsf M} and configurations ξ\xi and ω\omega, the partial replacement ξ[U←ω]\xi[U\leftarrow\omega] is the configuration taking the value ω(e)\omega(e) on UU and ξ(e)\xi(e) outside UU. Observing UU extends the history by (5). h⊕Uω=(K∪U,ξ[U←ω]).h\oplus_U\omega=(K\cup U,\xi[U\leftarrow\omega]).(5)✦

For opening probabilities p:E𝖬→[0,1]p:E_{\mathsf M}\to[0,1], the independent Bernoulli law μp\mu_p and the parameters php_h pinned by hh are given in (6). For constant opening probability q∈[0,1]q\in[0,1], write 𝑷q,h\mathbf P_{q,h} for the history-conditioned law in that display. μp=⨂e∈E𝖬Bernoulli⁡(p(e)),ph(e)={ξ(e),e∈K,p(e),e∉K,𝑷q,h=μqh.\mu_p=\bigotimes_{e\in E_{\mathsf M}}\operatorname{Bernoulli}(p(e)),\qquad p_h(e)=\begin{cases}\xi(e),&e\in K,\\p(e),&e\notin K,\end{cases} \qquad \mathbf P_{q,h}=\mu_{q_h}.(6)

An exploration packet at scale rr is a triple t=(v,a,G)t=(v,a,G) in (7): vv is its coarse vertex, aa its parent, and GG its finite lattice graph. t=(v,a,G),v,a∈ℤ2,Qv⊆G,0∈VG.t=(v,a,G),\qquad v,a\in\mathbb Z^2,\qquad Q_v\subseteq G,\qquad 0\in V_G.(7)✦ The packet connection event ℰ(t)\mathcal E(t) is the event in (8). ℰ(t)={ω:0↔GBv}.\mathcal E(t)=\{\omega:0\leftrightarrow_G B_v\}.(8)✦ The root packet t0t_0 and the child packet t[x]t[x] at a coarse vertex xx are (9). t0=(0,0,G(Q0)),t[x]=(x,v,F(G,v,x))for t=(v,a,G).t_0=(0,0,G(Q_0)),\qquad t[x]=(x,v,F(G,v,x)) \quad\text{for }t=(v,a,G).(9)

An exploration state ss is the tuple in (10), with history hh, processed vertices PP, an ordered packet queue 𝒬\mathcal Q, good vertices AA and bad vertices DD. s=(h,P,𝒬,A,D),P,A,D⊆ℤ2 finite,𝒬 a finite list of packets.s=(h,P,\mathcal Q,A,D),\qquad P,A,D\subseteq\mathbb Z^2\text{ finite},\qquad \mathcal Q\text{ a finite list of packets}.(10)✦ The visited set WsW_s of an exploration state ss is the set of its processed and queued coarse vertices. The unrevealed variables UsU_s of the first queued block and the history hωh^\omega after their observation are defined by (11); vtv_t and ata_t denote the vertex and parent of a packet tt, [][] denotes the empty queue, and t::𝒬′t::\mathcal Q' denotes the queue with first packet tt and remaining queue 𝒬′\mathcal Q'. Ws=P∪{vt:t∈𝒬},Us={⌀,𝒬=[],J(vt,at)\K,𝒬=t::𝒬′,hω=h⊕Usω=(Kω,ξω).\begin{aligned} W_s&=P\cup\{v_t:t\in\mathcal Q\},\\ U_s&=\begin{cases} \varnothing,&\mathcal Q=[],\\ J(v_t,a_t)\setminus K,&\mathcal Q=t::\mathcal Q', \end{cases}\\ h^\omega&=h\oplus_{U_s}\omega=(K^\omega,\xi^\omega). \end{aligned}(11) For a packet t=(v,a,G)t=(v,a,G), the candidate list Ns(t)N_s(t) in (12) consists of its unvisited neighboring children, ordered by direction. Ns(t)=[t[v+Δd]:d=0,1,2,3,v+Δd∉Ws].N_s(t)=\bigl[t[v+\Delta_d]:d=0,1,2,3,\ v+\Delta_d\notin W_s\bigr].(12)✦

For q∈[0,1]q\in[0,1], δ∈ℝ\delta\in\mathbb R, an exploration state ss, a packet tt and a configuration ω\omega, the acceptance criterion Acc⁡q,δ(s,t,ω)\operatorname{Acc}_{q,\delta}(s,t,\omega) is the condition in (13). Acc⁡q,δ(s,t,ω)⇔ξω∈ℰ(t)and 𝑷q,hω(ℰ(u))>1−δ(u∈Ns(t)).\begin{aligned} \operatorname{Acc}_{q,\delta}(s,t,\omega)\ \Longleftrightarrow\quad& \xi^\omega\in\mathcal E(t)\\ &\text{and }\mathbf P_{q,h^\omega}(\mathcal E(u))>1-\delta \quad(u\in N_s(t)). \end{aligned}(13)✦ Write 𝒬′∥Ns(t)\mathcal Q'\mathbin{\|}N_s(t) for list concatenation. The exploration successor s+s^+ after processing the first packet is (14), where v=vtv=v_t in the two nonempty queue cases. s+={(hω,P,[],A,D),𝒬=[],(hω,P∪{v},𝒬′∥Ns(t),A∪{v},D),𝒬=t::𝒬′,Acc⁡q,δ(s,t,ω),(hω,P∪{v},𝒬′,A,D∪{v}),𝒬=t::𝒬′,¬Acc⁡q,δ(s,t,ω).s^+=\begin{cases} (h^\omega,P,[],A,D),&\mathcal Q=[],\\ (h^\omega,P\cup\{v\},\mathcal Q'\mathbin{\|}N_s(t),A\cup\{v\},D), &\mathcal Q=t::\mathcal Q',\ \operatorname{Acc}_{q,\delta}(s,t,\omega),\\ (h^\omega,P\cup\{v\},\mathcal Q',A,D\cup\{v\}), &\mathcal Q=t::\mathcal Q',\ \neg\operatorname{Acc}_{q,\delta}(s,t,\omega). \end{cases}(14)✦

A valid exploration state ss at parameters q,δq,\delta is an exploration state satisfying (15), whose final condition is the pending connection promise; GtG_t denotes the graph of packet tt. 0∈P,(vt:t∈𝒬) has no repetitions,vt∉P,at∈P(t∈𝒬),K⊆X(P),β𝖬(Gt)⊆K∪J(vt,at)(t∈𝒬),𝑷q,h(ℰ(t))>1−δ(t∈𝒬).\begin{gathered} 0\in P,\qquad (v_t:t\in\mathcal Q)\text{ has no repetitions},\\ v_t\notin P,\quad a_t\in P\qquad(t\in\mathcal Q),\\ K\subseteq X(P),\\ \beta_{\mathsf M}(G_t)\subseteq K\cup J(v_t,a_t) \qquad(t\in\mathcal Q),\\ \mathbf P_{q,h}(\mathcal E(t))>1-\delta \qquad(t\in\mathcal Q). \end{gathered}(15)✦ The initial state s0s_0 is (16), where 𝟏\mathbf1 is the all-open configuration. s0=((R,𝟏),{0},[t0[Δ0],t0[Δ1],t0[Δ2],t0[Δ3]],{0},⌀).s_0=\bigl((R,\mathbf1),\{0\}, [t_0[\Delta_0],t_0[\Delta_1],t_0[\Delta_2],t_0[\Delta_3]], \{0\},\varnothing\bigr).(16)✦

What Is Checked

The setting is defined for either percolation model on ℤ3\mathbb Z^3 at every integer scale r≥0r\geq0, with q∈[0,1]q\in[0,1] and δ∈ℝ\delta\in\mathbb R, and uses finite lattice subgraphs with finite observation histories.