OctoInformBeta

OpenAI preprint, September 2026 · §6. From the block tree to the map · §6

Lemma 6.1 [Distances between poles]: Wedge distance between existing poles differs from route distance by at most twice maximum core degree, and rotation-intertwining bijections make nonroot poles surjective

Real graph distances between node poles and nonroot surjectivity.

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

Consider a rooted planar map MnM_n with n+1n+1 edges assembled recursively from an ordered tree of connected cores, where each tree node carries a route length summing core increments from the root and determines a pole vertex in MnM_n. How closely does the graph distance between the poles of two nodes match the route distance formed from their route lengths and the route length of their last common ancestor, and do the nonroot poles cover every vertex of MnM_n?

Rooted Planar Maps and Wedge Graphs

For n≥0n \ge 0, the dart set DnD_n of a map with n+1n+1 edges is the finite set {0,…,2(n+1)−1}\{0, \dots, 2(n+1)-1\}, whose elements are called darts.✦ An orbit of a permutation ss on DnD_n is an equivalence class of darts belonging to the same cycle of ss✦, and the orbit map d↦[d]sd \mapsto [d]_s on DnD_n is the map sending each dart d∈Dnd \in D_n to its ss-cycle.✦ Given an edge-reversal permutation aa, a vertex-rotation permutation ss on DnD_n, and a set AA of orbits of aa, the spanning subgraph on the orbits of ss is the simple graph in which two distinct orbits uu and vv of ss are adjacent whenever some dart d∈Dnd \in D_n satisfies [d]a∈A[d]_a \in A and {[d]s,[a(d)]s}={u,v}\{[d]_s, [a(d)]_s\} = \{u, v\}.✦

A labelled planar map (a,s)(a, s) with n+1n+1 edges is a pair of permutations of DnD_n such that aa is a fixed-point-free involution on DnD_n, the spanning subgraph formed using all orbits of aa is connected, and the number of orbits of ss plus the number of orbits of s∘as \circ a equals n+3n+3.✦ Two labelled planar maps (a,s)(a, s) and (a′,s′)(a', s') on DnD_n are isomorphic as rooted maps if there exists a permutation rr of DnD_n fixing the root dart 00 such that a′∘r=r∘aa' \circ r = r \circ a and s′∘r=r∘ss' \circ r = r \circ s.✦ A rooted planar map MnM_n with n+1n+1 edges is an equivalence class of labelled planar maps with n+1n+1 edges under the equivalence relation generated by root-preserving map isomorphisms.✦ For a rooted planar map MnM_n with a chosen representative (a,s)(a, s), the vertex-rotation permutation σMn\sigma_{M_n} of MnM_n is the permutation ss cyclically ordering the darts around each vertex✦, and the vertex set V(Mn)V(M_n) of MnM_n is the set of orbits of σMn\sigma_{M_n}.✦

For a vertex-rotation permutation pp on a finite dart set DD, the permutation wedge vertex set V(p)V(p) of pp is the set of cycle equivalence classes of DD under pp✦, with the cycle projection d↦[d]pd \mapsto [d]_p mapping each dart d∈Dd \in D to its pp-cycle.✦ Given a permutation ee on DD, the permutation wedge dart graph Γ(e,p)\Gamma(e, p) is the simple graph on V(p)V(p) in which two distinct cycles uu and vv are adjacent whenever some dart d∈Dd \in D satisfies {[d]p,[e(d)]p}={u,v}\{[d]_p, [e(d)]_p\} = \{u, v\}, and dΓ(e,p)(u,v)d_{\Gamma(e, p)}(u, v) denotes the graph distance between uu and vv in Γ(e,p)\Gamma(e, p).✦

Typed Words, Arch Matchings, and Cores

Let 𝒜\mathcal{A} denote the alphabet of typed burger-order letters, each of which is either a burger token or an order token carrying one of two boolean types (true\mathrm{true} or false\mathrm{false}).✦ Given a boolean stack stored freshest-first, typed word stack execution evaluates a word of letters in 𝒜\mathcal{A} against the stack, returning the final boolean stack upon success or failing on an illegal closure.✦

A non-crossing arch matching EE on a finite list ll of elements from a set DD is a list of ordered pairs from ll defined inductively: the empty list matches the empty list; any non-crossing arch matching EE on a list l′l' remains one when l′l' is preceded by an unmatched element aa; and given non-crossing arch matchings E1E_1 on LL and E2E_2 on RR, placing (a,b)(a, b) before the concatenation of E1E_1 and E2E_2 forms a non-crossing arch matching on the list obtained by placing aa, LL, bb, and RR in order.✦ The endpoints of a list EE of pairs in DD form the list of first and second coordinates of all pairs in EE✦, while the arch transposition product τ(E)\tau(E) is the permutation of DD equal to the identity on the empty list and defined recursively by τ(E)=τ(E′)∘(ab)\tau(E) = \tau(E') \circ (a\, b) when EE consists of (a,b)(a, b) followed by E′E', where (ab)(a\, b) swaps aa and bb.✦

Given a letter assignment w:D→𝒜w : D \to \mathcal{A} along a list ll of elements of DD, a two-stack matching certificate M=(E1,E2)M = (E_1, E_2) consists of non-crossing arch matchings E1E_1 and E2E_2 on ll whose combined endpoints form a permutation of ll, such that every pair (a,b)∈E1(a, b) \in E_1 assigns a true\mathrm{true} burger token to aa and a true\mathrm{true} order token to bb, and every pair (a,b)∈E2(a, b) \in E_2 assigns a false\mathrm{false} burger token to aa and a false\mathrm{false} order token to bb.✦ The stack matching mate permutation μ(M)\mu(M) of a two-stack matching certificate M=(E1,E2)M = (E_1, E_2) is the arch transposition product τ(E1E2)\tau(E_1 E_2) of the concatenation of E1E_1 and E2E_2.✦

For an integer N≥1N \ge 1 and a permutation aa on {0,…,N−1}\{0, \dots, N-1\}, a chord opening endpoint ii of aa is an index in {0,…,N−1}\{0, \dots, N-1\} satisfying i<a(i)i < a(i).✦ Two openers xx and yy of aa satisfy the chord crossing relation when either x<y<a(x)<a(y)x < y < a(x) < a(y) or y<x<a(y)<a(x)y < x < a(y) < a(x)✦, and the chord intersection graph of aa is the simple graph on its openers whose edges join crossing pairs.✦ A word ww of letters in 𝒜\mathcal{A} satisfies the connected core word condition if its index sequence i↦wii \mapsto w_i along (0,…,|w|−1)(0, \dots, |w|-1) admits a two-stack matching certificate MM such that 00 is an opener of μ(M)\mu(M) and every opener of μ(M)\mu(M) is reachable from 00 in the chord intersection graph of μ(M)\mu(M).✦ A connected typed core cc is a word of letters in 𝒜\mathcal{A} satisfying the connected core word condition✦, and an optional core label is either a connected typed core or an empty mark.✦

Ordered Trees of Cores, Poles, and Routes

An ordered tree of cores tt is defined inductively: it is either a leaf or a branch (c,(ti)0≤i<|c|)(c, (t_i)_{0 \le i < |c|}) formed by a connected typed core cc and a family of child ordered trees of cores indexed by the corners 0≤i<|c|0 \le i < |c| of cc.✦ A core tree node vv of an ordered tree of cores tt is a vertex of tt itself (without identifying coincident map poles): a leaf has a single node, while at a branch (c,(ti))(c, (t_i)) a node is either the branch root or a pair (i,u)(i, u) consisting of a corner index 0≤i<|c|0 \le i < |c| and a core tree node uu of tit_i.✦ A core tree dart dd of an ordered tree of cores tt is a dart of the recursively substituted word: a leaf has no darts, while at a branch (c,(ti))(c, (t_i)) a dart is either a position ii of cc or a pair (i,d′)(i, d') with 0≤i<|c|0 \le i < |c| and d′d' a core tree dart of tit_i; the set of all core tree darts of tt is denoted by 𝒟(t)\mathcal{D}(t).✦

For an ordered tree of cores tt and a dart d∈𝒟(t)d \in \mathcal{D}(t), the core tree dart label ℓt(d)∈𝒜\ell_t(d) \in \mathcal{A} of dd is the letter defined inductively: at a branch (c,(ti))(c, (t_i)), a position ii of cc carries the ii-th letter of cc, and a dart (i,d′)(i, d') in child subtree tit_i keeps its label ℓti(d′)\ell_{t_i}(d').✦ The core tree dart list Λ(t)\Lambda(t) of an ordered tree of cores tt is the list of all darts of 𝒟(t)\mathcal{D}(t) in recursive substitution order: it is empty at a leaf, and at a branch (c,(ti))(c, (t_i)) it concatenates, for i=0,…,|c|−1i = 0, \dots, |c|-1, the core dart at ii followed by the dart list Λ(ti)\Lambda(t_i) in child subtree tit_i.✦ The word w(t)w(t) of an ordered tree of cores tt is the word of letters in 𝒜\mathcal{A} defined inductively: at a leaf, w(t)w(t) is empty, while at a branch (c,(ti))(c, (t_i)) it is formed by inserting each child word w(ti)w(t_i) into cc at corner ii.✦ For any ordered tree of cores tt, the core tree stack matching M(t)=(E1(t),E2(t))M(t) = (E_1(t), E_2(t)) is the two-stack matching certificate for ℓt\ell_t along Λ(t)\Lambda(t) constructed from the empty-stack execution of w(t)w(t).✦

The core tree label sequence L(t)L(t) of an ordered tree of cores tt is the list of optional core labels in preorder: the single empty mark at a leaf, and at a branch (c,(ti))(c, (t_i)) the label cc followed by the concatenation of L(t0),…,L(t|c|−1)L(t_0), \dots, L(t_{|c|-1}).✦ For a core tree node vv of an ordered tree of cores tt, the preorder node index idxt(v)\mathrm{idx}_t(v) equals 00 at a leaf or branch root, and for a node (i,u)(i, u) in child subtree tit_i of a branch (c,(tj))(c, (t_j)) is given by (1): idxt(i,u)=1+∑j=0i−1|L(tj)|+idxti(u).\mathrm{idx}_t(i, u) = 1 + \sum_{j=0}^{i-1} |L(t_j)| + \mathrm{idx}_{t_i}(u).(1)✦ For an ordered tree of cores tt, the preorder node word bijection νt\nu_t is the bijection from the nodes of tt onto {0,…,|w(t)|}\{0, \dots, |w(t)|\} sending the root to 00 and the nonroot nodes to {1,…,|w(t)|}\{1, \dots, |w(t)|\}, obtained by indexing nodes by the preorder node index idxt\mathrm{idx}_t.✦

For an ordered tree of cores tt and a core tree node vv of tt, the node pole dart polet(v)\mathrm{pole}_t(v) is either a dart in 𝒟(t)\mathcal{D}(t) or absent: at a leaf it is absent; at a branch (c,(ti))(c, (t_i)), it equals dart 00 of cc when vv is the branch root, and for a node (i,u)(i, u) in child subtree tit_i it equals the image of poleti(u)\mathrm{pole}_{t_i}(u) in 𝒟(t)\mathcal{D}(t) if poleti(u)\mathrm{pole}_{t_i}(u) is present in tit_i, and otherwise the next corner of cc after ii under the cyclic shift.✦ Given an ordered tree of cores tt, a core tree node vv of tt, a rooted planar map MnM_n with n+1n+1 edges, and a bijection e:𝒟(t)→Dne : \mathcal{D}(t) \to D_n, the realized pole polet,Mn,e(v)\mathrm{pole}_{t, M_n, e}(v) of vv is the vertex [e(d)]σMn∈V(Mn)[e(d)]_{\sigma_{M_n}} \in V(M_n) when polet(v)=d\mathrm{pole}_t(v) = d is present, and the root vertex [0]σMn[0]_{\sigma_{M_n}} when polet(v)\mathrm{pole}_t(v) is absent.✦ The nonroot pole map πt,Mn,e:{0,…,|w(t)|−1}→V(Mn)\pi_{t, M_n, e} : \{0, \dots, |w(t)| - 1\} \to V(M_n) of an ordered tree of cores tt, a rooted planar map MnM_n with n+1n+1 edges, and a bijection e:𝒟(t)→Dne : \mathcal{D}(t) \to D_n assigns to each i∈{0,…,|w(t)|−1}i \in \{0, \dots, |w(t)| - 1\} the realized pole polet,Mn,e(νt−1(i+1))\mathrm{pole}_{t, M_n, e}(\nu_t^{-1}(i + 1)).✦

Writing δc(i)\delta_c(i) for the increment of a connected typed core cc at corner ii, the node route length Gt(v)G_t(v) of a core tree node vv of an ordered tree of cores tt is the sum of core increments along the path from the root of tt to vv given by (2): Gt(v)={0,if t is a leaf or v is the root of t,δc(i)+Gti(u),if t=(c,(tj)) and v=(i,u).G_t(v) = \begin{cases} 0, & \text{if } t \text{ is a leaf or } v \text{ is the root of } t, \\ \delta_c(i) + G_{t_i}(u), & \text{if } t = (c, (t_j)) \text{ and } v = (i, u). \end{cases}(2)✦ For two core tree nodes vv and v′v' of an ordered tree of cores tt, the common route length Gt(v,v′)G_t(v, v') is the sum of core increments along their shared root path to their last common ancestor given by (3): Gt(v,v′)={δc(i)+Gti(u,u′),if t=(c,(tk)),v=(i,u),v′=(i,u′),0,otherwise.G_t(v, v') = \begin{cases} \delta_c(i) + G_{t_i}(u, u'), & \text{if } t = (c, (t_k)),\, v = (i, u),\, v' = (i, u'), \\ 0, & \text{otherwise}. \end{cases}(3)✦ The maximum core degree Δ(t)\Delta(t) of an ordered tree of cores tt is the largest core word length in tt, equal to 00 at a leaf and to max⁡({|c|}∪{Δ(ti):0≤i<|c|})\max(\{|c|\} \cup \{\Delta(t_i) : 0 \le i < |c|\}) at a branch (c,(ti))(c, (t_i)).✦

The vertex-rotation permutation sts_t of an ordered tree of cores tt is the permutation γt∘τ(E1(t))\gamma_t \circ \tau(E_1(t)) on 𝒟(t)\mathcal{D}(t), where γt\gamma_t is the cyclic permutation of Λ(t)\Lambda(t), and the real graph distance dreal,t(a,b)d_{\mathrm{real}, t}(a, b) between two darts a,b∈𝒟(t)a, b \in \mathcal{D}(t) is the distance dΓ(μ(M(t)),st)([a]st,[b]st)d_{\Gamma(\mu(M(t)), s_t)}([a]_{s_t}, [b]_{s_t}) in the permutation wedge dart graph given by (4): st=γt∘τ(E1(t)),dreal,t(a,b)=dΓ(μ(M(t)),st)([a]st,[b]st).s_t = \gamma_t \circ \tau(E_1(t)), \qquad d_{\mathrm{real}, t}(a, b) = d_{\Gamma(\mu(M(t)), s_t)}([a]_{s_t}, [b]_{s_t}).(4)✦

The Claim

Theorem 1. Let tt be an ordered tree of cores, let vv and v′v' be two core tree nodes of tt, and suppose vv and v′v' have node pole darts a,b∈𝒟(t)a, b \in \mathcal{D}(t) satisfying polet(v)=a\mathrm{pole}_t(v) = a and polet(v′)=b\mathrm{pole}_t(v') = b. Then the real graph distance between aa and bb satisfies |dreal,t(a,b)−(Gt(v)+Gt(v′)−2Gt(v,v′))|≤2Δ(t).\bigl| d_{\mathrm{real}, t}(a, b) - \bigl(G_t(v) + G_t(v') - 2 G_t(v, v')\bigr) \bigr| \le 2 \Delta(t).(5)✦ Furthermore, if n≥0n \ge 0, MnM_n is a rooted planar map with n+1n+1 edges, and e:𝒟(t)→Dne : \mathcal{D}(t) \to D_n is a bijection satisfying σMn(e(d))=e(st(d))\sigma_{M_n}(e(d)) = e(s_t(d)) for every d∈𝒟(t)d \in \mathcal{D}(t), then the nonroot pole map πt,Mn,e\pi_{t, M_n, e} satisfies πt,Mn,e({0,…,|w(t)|−1})=V(Mn).\pi_{t, M_n, e}\bigl(\{0, \dots, |w(t)| - 1\}\bigr) = V(M_n).(6)✦

In the paper, the result reads: if w*w_* is the last common ancestor of two tree nodes ww and w′w' and Δ\Delta is the maximum offspring number, then the all-edge graph distance dnd_n on MnM_n and the pole map π\pi from tree nodes to V(Mn)V(M_n) satisfy |dn(π(w),π(w′))−(G(w)+G(w′)−2G(w*))|≤2Δ|d_n(\pi(w), \pi(w')) - (G(w) + G(w') - 2G(w_*))| \le 2\Delta, and π\pi is onto, where GG is the route length. The bound (5) expresses this comparison on an ordered tree of cores tt via the permutation wedge distance dreal,td_{\mathrm{real}, t}, the common route length Gt(⋅,⋅)G_t(\cdot, \cdot), and the maximum core degree Δ(t)\Delta(t) rather than dnd_n, G(w*)G(w_*), and Δ\Delta, while (6) restricts the pole map to nonroot tree nodes under a rotation-intertwining dart bijection.

What Is Checked

The two claims are stated over an ordered tree of cores tt, two nodes vv and v′v' of tt possessing node pole darts aa and bb, the real graph distance dreal,td_{\mathrm{real}, t} in the permutation wedge dart graph of tt, the node route length GtG_t, the common route length Gt(⋅,⋅)G_t(\cdot, \cdot), and the maximum core degree Δ(t)\Delta(t), together with a rooted planar map MnM_n with n+1n+1 edges and a bijection e:𝒟(t)→Dne : \mathcal{D}(t) \to D_n satisfying σMn(e(d))=e(st(d))\sigma_{M_n}(e(d)) = e(s_t(d)) for every dart d∈𝒟(t)d \in \mathcal{D}(t). Beyond these claims, the library also holds that for a set DD, any letter assignment w:D→𝒜w : D \to \mathcal{A} along a list ll of elements of DD whose typed stack execution from the empty stack finishes with an empty stack admits non-crossing arch matchings EE and FF on ll whose combined endpoints permute ll, with EE pairing true\mathrm{true} burgers to true\mathrm{true} orders and FF pairing false\mathrm{false} burgers to false\mathrm{false} orders.✦ It also holds for every ordered tree of cores tt that |L(t)|=|w(t)|+1|L(t)| = |w(t)| + 1✦ and that idxt(v)<|L(t)|\mathrm{idx}_t(v) < |L(t)| for every node vv of tt.✦