OctoInformBeta

OpenAI preprint, September 2026 · §3. Planar boundaries and finite scales

Lemma 3.1: Finite planar sets containing 00 admit anchored closed trails and codes; codes of length nn form families of size 4n4n4n4^n

Realizable boundary codes admit large edge matchings.

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

For a finite set of vertices in the planar square lattice, boundary sides separate vertices in the set from their nearest neighbors outside it. The contour question is which closed trails can be found among these sides, how to count their possible locations and directions, and how many crossed primal edges have disjoint endpoints.

Use ℤ2\mathbb Z^2 for the primal lattice, with origin 0=(0,0)0=(0,0), and label the dual vertex at x−(1/2,1/2)x-(1/2,1/2) by x∈ℤ2x\in\mathbb Z^2. The four directions form the set D={0,1,2,3}D=\{0,1,2,3\}.✦ Their outward primal steps vdv_d and dual tail and head offsets td,hdt_d,h_d are the vectors in (1). dvdtdhd0(0,−1)(0,0)(1,0)1(1,0)(1,0)(1,1)2(0,1)(1,1)(0,1)3(−1,0)(0,1)(0,0)\begin{array}{c|c|c|c} d&v_d&t_d&h_d\\ \hline 0&(0,-1)&(0,0)&(1,0)\\ 1&(1,0)&(1,0)&(1,1)\\ 2&(0,1)&(1,1)&(0,1)\\ 3&(-1,0)&(0,1)&(0,0) \end{array}(1)

The oriented boundary ∂→X\partial^{\to}X of a finite set X⊆ℤ2X\subseteq\mathbb Z^2 is the set of sides e=(x,d)∈ℤ2×De=(x,d)\in\mathbb Z^2\times D with x∈Xx\in X and x+vd∉Xx+v_d\notin X.✦ A side e=(x,d)e=(x,d) crosses the primal edge with endpoints xx and x+vdx+v_d; its dual tail t(e)t(e) and head h(e)h(e), and the displacement δd\delta_d in direction dd, are defined by (2). t(e)=x+td,h(e)=x+hd,δd=hd−td.t(e)=x+t_d,\qquad h(e)=x+h_d,\qquad \delta_d=h_d-t_d.(2)

The positive-ray crossing number ρ(a,b)\rho(a,b), for integer pairs a=(a1,a2)a=(a_1,a_2) and b=(b1,b2)b=(b_1,b_2), is the signed indicator in (3). ρ(a,b)=𝟏{a2=0,b2=1,a1>0}−𝟏{b2=0,a2=1,b1>0}.\rho(a,b)= \mathbf 1_{\{a_2=0,\ b_2=1,\ a_1>0\}} -\mathbf 1_{\{b_2=0,\ a_2=1,\ b_1>0\}}.(3)✦

For an integer m≥0m\geq0, let Im={i∈ℤ:0≤i<m}I_m=\{i\in\mathbb Z:0\leq i<m\}. For n>0n>0, the cyclic successor of i∈Ini\in I_n is i+=(i+1)mod⁡ni^+=(i+1)\bmod n.✦ An edge-simple closed boundary trail of length nn in XX is a sequence e=(ei)i∈Ine=(e_i)_{i\in I_n} of distinct members of ∂→X\partial^{\to}X with t(ei+)=h(ei)t(e_{i^+})=h(e_i) for every i∈Ini\in I_n; write 𝒯n(X)\mathcal T_n(X) for the set of these trails.

Boundary Codes

A boundary code cc of length n≥0n\geq0 is a triple (r,s,w)(r,s,w) belonging to the family specified in (4), where rr selects a horizontal anchor coordinate, ss selects its height, and ww is a direction word. The code family 𝒦n\mathcal K_n and the anchor A(c)A(c) are defined in (4), where DInD^{I_n} is the set of words indexed by InI_n. 𝒦n=I2n×{0,1}×DIn,A(c)=(r,s)for c=(r,s,w).\mathcal K_n=I_{2n}\times\{0,1\}\times D^{I_n}, \qquad A(c)=(r,s)\quad\text{for }c=(r,s,w).(4)

The padded direction word w‾\bar w associated to w∈DInw\in D^{I_n} is the direction word on the nonnegative integer indices that agrees with ww on InI_n and has value 00 thereafter.✦ The decoded dual position zk(c)z_k(c) for k≥0k\geq0 and decoded side σi(c)\sigma_i(c) for i∈Ini\in I_n are given by (5). zk(c)=A(c)+∑j=0k−1δw‾(j),σi(c)=(zi(c)−tw(i),w(i)).\begin{aligned} z_k(c)&=A(c)+\sum_{j=0}^{k-1}\delta_{\bar w(j)},\\ \sigma_i(c)&=\bigl(z_i(c)-t_{w(i)},\,w(i)\bigr). \end{aligned}(5)

A boundary code c∈𝒦nc\in\mathcal K_n is realizable if there is a finite set X⊆ℤ2X\subseteq\mathbb Z^2 for which its decoded sides σi(c)\sigma_i(c) are distinct members of ∂→X\partial^{\to}X.✦ For a decoded side σi(c)=(xi,di)\sigma_i(c)=(x_i,d_i), its inner and outer primal endpoints ai(c),bi(c)a_i(c),b_i(c) are defined by (6). ai(c)=xi,bi(c)=xi+vdi.a_i(c)=x_i,\qquad b_i(c)=x_i+v_{d_i}.(6)

Two edges with endpoint pairs (ai,bi)(a_i,b_i) and (aj,bj)(a_j,b_j) conflict when they share an endpoint.✦ A matching MM of primal edges is a set of edges with no conflicts between distinct members, using the condition in (7). i and j conflict⇔{ai,bi}∩{aj,bj}≠⌀.i\text{ and }j\text{ conflict} \quad\Longleftrightarrow\quad \{a_i,b_i\}\cap\{a_j,b_j\}\ne\varnothing.(7)✦

The Claim

Theorem 1. Let X⊆ℤ2X\subseteq\mathbb Z^2 be finite and contain 00. There exist a length n>0n>0 and a trail e∈𝒯n(X)e\in\mathcal T_n(X) with the anchoring property (8). For some i∈In,0<(t(ei))1<2n,ρ(t(ei),h(ei))≠0.\text{For some }i\in I_n,\qquad 0<\bigl(t(e_i)\bigr)_1<2n, \qquad \rho\bigl(t(e_i),h(e_i)\bigr)\ne0.(8)✦ For the same XX, there exist a length m>0m>0, a code c∈𝒦mc\in\mathcal K_m, and distinct sides fi∈∂→Xf_i\in\partial^{\to}X, indexed by ImI_m, with the decoding identity (9). σi(c)=fifor every i∈Im.\sigma_i(c)=f_i\qquad\text{for every }i\in I_m.(9)✦ For every n≥0n\geq0, the cardinality of the code family is given by (10). |𝒦n|=4n4n.|\mathcal K_n|=4n4^n.(10)✦ For every realizable code c∈𝒦nc\in\mathcal K_n, there is a set J⊆InJ\subseteq I_n satisfying (11). n≤7|J|,{ai(c),bi(c)}∩{aj(c),bj(c)}=⌀for distinct i,j∈J.\begin{gathered} n\leq7|J|,\\ \{a_i(c),b_i(c)\}\cap\{a_j(c),b_j(c)\}=\varnothing \qquad\text{for distinct }i,j\in J. \end{gathered}(11)✦

In the paper, the result reads: there are deterministic families 𝒞n\mathcal C_n of simple dual square-lattice cycles of length nn, with |𝒞n|≤2n3n|\mathcal C_n|\leq2n3^n, such that the dual edge boundary of every finite X⊆ℤ2X\subseteq\mathbb Z^2 containing 00 includes a cycle in ⋃n≥1𝒞n\bigcup_{n\geq1}\mathcal C_n, and for each candidate cycle at least n/7n/7 of its crossed primal edges can be fixed with pairwise disjoint endpoints.

What Is Checked

The statements concern the oriented boundaries of finite subsets of ℤ2\mathbb Z^2 containing 00 and the code families 𝒦n\mathcal K_n, with realizability required for the matching assertion.