OctoInformBeta

OpenAI preprint, September 2026 · Section 5. A weighted cancellation argument

Proposition 5.1 [Existence of a forest pair]: In colored duals; weighted pair polynomials satisfy a cycle product formula and nonvanishing under a cycle sign condition

Existing pairs admit a forest second state.

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

Proposition 5.1 concerns forests in the dual triangulation of a cubic bipartite network. Let NN and DD be finite directed networks on vertex sets UU and VV, respectively, with a common edge set EE. A directed network NN on vertex set UU with edge set EE is a network in which each edge of EE has a designated tail and head in UU.✦ The underlying simple graph of a directed network NN on UU is the graph on UU that joins distinct vertices when they are endpoints of an edge of NN.✦ A network is simple when its edges have distinct endpoints and no two edges have the same unordered endpoint pair.✦ An edge is incident to each of its endpoints✦; the star of a vertex is the set of edges incident to it.✦

For either network KK, write hKh_K and tKt_K for its head and tail maps. For a real edge vector zz and a real vertex function ff on KK, the oriented incidence matrix IKI_K, boundary operator ∂K\partial_K, and gradient operator ∇K\nabla_K are given by (1). IK(v,e)=𝟏hK(e)=v−𝟏tK(e)=v,∂Kz=IKz,(∇Kf)(e)=f(hK(e))−f(tK(e)).\begin{aligned} I_K(v,e)&=\mathbf{1}_{h_K(e)=v}-\mathbf{1}_{t_K(e)=v},\\ \partial_K z&=I_Kz, & (\nabla_K f)(e)&=f(h_K(e))-f(t_K(e)). \end{aligned}(1)

A cycle cut duality (N,D)(N,D) is a pair of networks whose underlying graphs are connected and whose real cycle and cut spaces satisfy (2). ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\ker\partial_N=\operatorname{im}\nabla_D, \qquad \ker\partial_D=\operatorname{im}\nabla_N.(2)✦

A triangle TT on an edge set SS is a cyclic list of three distinct corners and three distinct edges, covering SS, in which each edge joins its corner to the next corner.✦ Indices are taken in ℤ/3ℤ\mathbb Z/3\mathbb Z. A colored dual is a cycle cut duality with NN simple and cubic, DD simple, and a black class B⊆UB\subseteq U containing exactly one endpoint of each edge. Each u∈Uu\in U has a triangle TuT_u in DD whose edge set is the star of uu in NN. Write vu(i)v_u(i) and eu(i)e_u(i) for its corners and sides. The outgoing edge sign ϵD(e,v)\epsilon_D(e,v) is +1+1 at the tail of ee and −1-1 otherwise.✦ The triangles satisfy the orientation condition (3). (∇N𝟏{u})(eu(i))=ϵD(eu(i),vu(i)).(\nabla_N\mathbf{1}_{\{u\}})(e_u(i)) =\epsilon_D(e_u(i),v_u(i)).(3)

A triangle system TT on VV, indexed by AA, assigns three distinct ordered corners vt(i)v_t(i) to each t∈At\in A, with no two distinct triangles sharing two distinct corners.✦ Fix a black root triangle t0t_0, identified with its vertex of NN. The black triangle system consists of the triangles TtT_t indexed by AA in (4); its nonroot vertices form the set XX there. A=B\{t0},X=V\{vt0(0),vt0(1),vt0(2)}.A=B\setminus\{t_0\}, \qquad X=V\setminus\{v_{t_0}(0),v_{t_0}(1),v_{t_0}(2)\}.(4)

States and Cycle Weights

For a finite triangle system TT on VV and a subset X⊆VX\subseteq V, a state ss is a corner assignment s:A→ℤ/3ℤs:A\to\mathbb Z/3\mathbb Z for which the selected vertex map bsb_s in (5) is a bijection. bs:A→X,bs(t)=vt(s(t)).b_s:A\longrightarrow X, \qquad b_s(t)=v_t(s(t)).(5)✦ Two states r,sr,s of a triangle system TT with selected vertex set XX are partners when br(t)≠bs(t)b_r(t)\ne b_s(t) for every triangle tt of TT. Write ℛs\mathcal R_s for the set of partners of ss, and 𝒫(T,X)\mathcal P(T,X) for the set of ordered pairs P=(r,s)P=(r,s) of partners. The opposite graph QsQ_s is the simple graph on VV with one side opposite the choice of ss in each triangle, as in (6). E(Qs)={{vt(i),vt(j)}:t∈A,i≠j,i,j≠s(t)}.E(Q_s)= \bigl\{\{v_t(i),v_t(j)\}:t\in A,\ i\ne j,\ i,j\ne s(t)\bigr\}.(6)✦

The corner function hh, cyclic index increment dd, total index increment I(r,s)I(r,s), and complex phase ϕ\phi are defined in (7). For unequal indices, h(i,j)h(i,j) is the remaining corner index. h(i,j)=−(i+j),d(i,j)={0i=j,1j=i+1,−1otherwise,I(r,s)=∑t∈Ad(r(t),s(t)),ϕ(n)=i⌊n/3⌋(n∈ℤ).\begin{aligned} h(i,j)&=-(i+j), &d(i,j)&=\begin{cases} 0&i=j,\\ 1&j=i+1,\\ -1&\text{otherwise}, \end{cases}\\ I(r,s)&=\sum_{t\in A}d(r(t),s(t)), &\phi(n)&=\mathrm{i}^{\lfloor n/3\rfloor}\quad(n\in\mathbb Z). \end{aligned}(7) For a pair P=(r,s)∈𝒫(T,X)P=(r,s)\in\mathcal P(T,X), the complementary assignment hPh_P assigns the remaining corner index to each triangle, and its fixed complement class 𝒢(P)\mathcal G(P) is the set of pairs with that same assignment, as in (8). hP(t)=h(r(t),s(t)),𝒢(P)={Q∈𝒫(T,X):hQ=hP}.h_P(t)=h(r(t),s(t)), \qquad \mathcal G(P)=\{Q\in\mathcal P(T,X):h_Q=h_P\}.(8)

For a finite set FF and coefficients b(t)b(t) in a commutative ring, let ℒF(b;x)\mathcal L_F(b;x) be the product of linear factors in (9). For real corner weights a(t,i)a(t,i), that equation also defines the state weight Wa(s;x)W_a(s;x) and phased pair weight Θa(P;x)\Theta_a(P;x) as complex polynomials. ℒF(b;x)=∏t∈F(1+b(t)x),Wa(s;x)=ℒA(t↦a(t,s(t));x),Θa(P;x)=ϕ(I(r,s))Wa(s;x).\begin{aligned} \mathcal L_F(b;x)&=\prod_{t\in F}(1+b(t)x),\\ W_a(s;x)&=\mathcal L_A\bigl(t\mapsto a(t,s(t));x\bigr),\\ \Theta_a(P;x)&=\phi(I(r,s))W_a(s;x). \end{aligned}(9)

The transition permutation of a pair P=(r,s)P=(r,s) is πP=br−1∘bs\pi_P=b_r^{-1}\circ b_s.✦ The cycle class γ\gamma containing a triangle t∈At\in A is the orbit of tt under the transition permutation πP\pi_P of a pair PP.✦ Write 𝒞(P)\mathcal C(P) for the set of these classes, and FP,γ⊆AF_{P,\gamma}\subseteq A for the triangles in a class γ\gamma. The cycle increment ΔP(γ)\Delta_P(\gamma), left and right cycle weights LP,γ(x),RP,γ(x)L_{P,\gamma}(x),R_{P,\gamma}(x), and cycle slope σa,P(γ)\sigma_{a,P}(\gamma) are defined in (10). ΔP(γ)=∑t∈FP,γd(r(t),s(t)),LP,γ(x)=ℒFP,γ(t↦a(t,r(t));x),RP,γ(x)=ℒFP,γ(t↦a(t,s(t));x),σa,P(γ)=∑t∈FP,γa(t,s(t))−∑t∈FP,γa(t,r(t)).\begin{aligned} \Delta_P(\gamma)&=\sum_{t\in F_{P,\gamma}}d(r(t),s(t)),\\ L_{P,\gamma}(x)&=\mathcal L_{F_{P,\gamma}} \bigl(t\mapsto a(t,r(t));x\bigr),\\ R_{P,\gamma}(x)&=\mathcal L_{F_{P,\gamma}} \bigl(t\mapsto a(t,s(t));x\bigr),\\ \sigma_{a,P}(\gamma)&=\sum_{t\in F_{P,\gamma}}a(t,s(t)) -\sum_{t\in F_{P,\gamma}}a(t,r(t)). \end{aligned}(10) Real corner weights aa satisfy the cycle sign condition when every pair P∈𝒫(T,X)P\in\mathcal P(T,X) and every γ∈𝒞(P)\gamma\in\mathcal C(P) satisfy (11). (ΔP(γ)=−3andσa,P(γ)>0)or(ΔP(γ)=3andσa,P(γ)<0).\bigl(\Delta_P(\gamma)=-3\ \text{and}\ \sigma_{a,P}(\gamma)>0\bigr) \quad\text{or}\quad \bigl(\Delta_P(\gamma)=3\ \text{and}\ \sigma_{a,P}(\gamma)<0\bigr).(11)

A cycle CC in a simple graph GG is a cyclic list of m≥3m\geq3 distinct vertices with successive vertices adjacent.✦ An opposite cycle CC of ss is such a cycle (zi)(z_i) in QsQ_s, together with distinct triangles tit_i and corner indices ℓi,ji≠s(ti)\ell_i,j_i\ne s(t_i) satisfying vti(ℓi)=ziv_{t_i}(\ell_i)=z_i and vti(ji)=zi+1v_{t_i}(j_i)=z_{i+1}.✦ The opposite cycle increment κC(r,s)\kappa_C(r,s) of a partner r∈ℛsr\in\mathcal R_s along an opposite cycle CC of ss is the integer given in (12). The disk circulation condition for a triangle system TT with selected vertex set XX is the requirement that the membership in (12) hold for every state ss, opposite cycle CC of ss, and partner r∈ℛsr\in\mathcal R_s. κC(r,s)=∑i∈ℤ/mℤd(r(ti),h(r(ti),s(ti)))∈{−3,3}.\kappa_C(r,s)= \sum_{i\in\mathbb Z/m\mathbb Z} d\bigl(r(t_i),h(r(t_i),s(t_i))\bigr) \ \in\ \{-3,3\}.(12)

The Claim

Theorem 1. For the black triangle system associated with a colored dual and black root t0t_0, suppose that 𝒫(T,X)\mathcal P(T,X) is nonempty. Then ∃(r,s)∈𝒫(T,X)such that Qs is a forest.\exists\,(r,s)\in\mathcal P(T,X) \quad\text{such that }Q_s\text{ is a forest}.(13)✦

Let TT be a finite triangle system and XX a subset of its vertices. Suppose that pairs exist, the disk circulation condition holds, and there are real corner weights satisfying the cycle sign condition. Then ∃(r,s)∈𝒫(T,X)such that Qs is a forest.\exists\,(r,s)\in\mathcal P(T,X) \quad\text{such that }Q_s\text{ is a forest}.(14)✦

For a finite triangle system with at least one pair, let aa be real corner weights satisfying the cycle sign condition. Then ∑P∈𝒫(T,X)Θa(P;x)≠0in ℂ[x].\sum_{P\in\mathcal P(T,X)}\Theta_a(P;x)\ne0 \qquad\text{in }\mathbb C[x].(15)✦

For a pair PP in a finite triangle system, suppose that ΔP(γ)∈{−3,3}\Delta_P(\gamma)\in\{-3,3\} for every γ∈𝒞(P)\gamma\in\mathcal C(P). For any real corner weights aa, ∑Q∈𝒢(P)Θa(Q;x)=∏γ∈𝒞(P)ϕ(ΔP(γ))(RP,γ(x)−LP,γ(x)).\sum_{Q\in\mathcal G(P)}\Theta_a(Q;x) =\prod_{\gamma\in\mathcal C(P)} \phi(\Delta_P(\gamma)) \bigl(R_{P,\gamma}(x)-L_{P,\gamma}(x)\bigr).(16)✦

What Is Checked

The assertion (13) is stated over the black triangle system of a colored dual, with nonroot sets AA and XX from (4). The assertions (14) and (15) range over finite triangle systems with the stated circulation or weight conditions; (16) concerns a fixed complement class with cycle increments ±3\pm3. The selected-vertex property of a state asserts that bs(t)∈Xb_s(t)\in X for every triangle tt.✦