OctoInformBeta

OpenAI preprint, September 2026 ยท ยง4. Counting equivalence and homogeneity

Lemma 12: Exactly when every component off them receives no net flow; on the cubic grid, some component with nonzero net flow has at most half the vertices

When values on some edges extend to a flow over ๐”ฝ3\mathbb{F}_3..

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

Take a finite directed multigraph GG, a set TT of its edges and a value in ๐”ฝ3\mathbb{F}_3 prescribed on each edge of TT. The lemma asks when these values are those of a flow over ๐”ฝ3\mathbb{F}_3 on the whole of GG, and it answers through the components of the graph left when the edges of TT are deleted. On the cubic grid of side LL it also asks how small a component witnessing a failure can be taken, against the size of the grid and against the number of edges in TT.

Components and Divergence

A finite directed multigraph GG consists of a finite set VV of vertices, a finite set EE of edges and two maps from EE to VV that give each edge ee its tail eโˆ’e^- and its head e+e^+. Values lie in the field ๐”ฝ3=โ„ค/3โ„ค\mathbb{F}_3 = \mathbb{Z}/3\mathbb{Z} of integers modulo 33.โœฆ

For a set TโІET \subseteq E, the edge relation off TT is the relation on VV under which a vertex uu is related to a vertex ww when some edge eโˆ‰Te \notin T has tail uu and head ww.โœฆ Connectivity off TT is the equivalence relation on VV generated by the edge relation off TT: two vertices are connected off TT when a path of edges outside TT, each traversed in either direction, joins them.โœฆ A component CC of G\TG \setminus T, the graph GG with the edges of TT deleted, is a class of connectivity off TT, a nonempty set of vertices, and |C||C| is its number of vertices.โœฆ The component CT(v)C_T(v) of a vertex vv is the set of the vertices connected to vv off TT.โœฆ

The incidence map โˆ‚:๐”ฝ3Eโ†’๐”ฝ3V\partial \colon \mathbb{F}_3^E \to \mathbb{F}_3^V sends an edge function fโˆˆ๐”ฝ3Ef \in \mathbb{F}_3^E to its divergence โˆ‚f=โˆ‘eโˆˆEf(e)(๐Ÿe+โˆ’๐Ÿeโˆ’),\partial f = \sum_{e \in E} f(e)\,\bigl(\mathbf{1}_{e^+} - \mathbf{1}_{e^-}\bigr),(1)โœฆ where ๐Ÿvโˆˆ๐”ฝ3V\mathbf{1}_v \in \mathbb{F}_3^V is the indicator function of the vertex vv. A flow on GG is an edge function kโˆˆ๐”ฝ3Ek \in \mathbb{F}_3^E with โˆ‚k=0\partial k = 0; the flows form the kernel ker⁡โˆ‚\ker \partial, written KK on the cubic grid.

For an assignment ฯƒโˆˆ๐”ฝ3T\sigma \in \mathbb{F}_3^T of values to the edges of TT, the edge function ฯƒTโˆˆ๐”ฝ3E\sigma_T \in \mathbb{F}_3^E equals ฯƒ\sigma on TT and 00 outside TT, and ฯƒ\sigma extends to a flow when some flow kk has k(e)=ฯƒ(e)k(e) = \sigma(e) for every eโˆˆTe \in T. A charge on GG is a function bโˆˆ๐”ฝ3Vb \in \mathbb{F}_3^V on its vertices.

The Cubic Grid

A vertex of the cubic grid of side L=n+1L = n + 1, for a natural number nn, is a triple (x,y,z)(x, y, z) of integers in {0,โ€ฆ,Lโˆ’1}\{0, \dots, L-1\}; the vertex set V={0,โ€ฆ,Lโˆ’1}3V = \{0, \dots, L-1\}^3 has L3L^3 elements.โœฆ An edge of the grid is a unit segment parallel to a coordinate axis, with its lower endpoint as tail and its upper endpoint as head. An edge along xx runs from (x,y,z)(x, y, z) to (x+1,y,z)(x+1, y, z) with 0โ‰คxโ‰คLโˆ’20 \le x \le L-2โœฆ, edges along yy and zz raise the second or the third coordinate by one in the same way, and the edge set EE is the disjoint union of these three families.โœฆ The box constant is the real number c=1โˆ’2โˆ’1/3c = 1 - 2^{-1/3}.โœฆ

The Claim

Theorem 1. Let GG be a finite directed multigraph with vertex set VV and edge set EE, and let TโІET \subseteq E.

(a) An assignment ฯƒโˆˆ๐”ฝ3T\sigma \in \mathbb{F}_3^T extends to a flow if and only if โˆ‘wโˆˆCT(v)(โˆ‚ฯƒT)(w)=0for every vโˆˆV.\sum_{w \in C_T(v)} (\partial \sigma_T)(w) = 0 \quad \text{for every } v \in V.(2)โœฆ

(b) A charge bโˆˆ๐”ฝ3Vb \in \mathbb{F}_3^V is the divergence โˆ‚t\partial t of an edge function tt that vanishes on TT if and only if โˆ‘wโˆˆCT(v)b(w)=0for every vโˆˆV.\sum_{w \in C_T(v)} b(w) = 0 \quad \text{for every } v \in V.(3)โœฆ

(c) Let bโˆˆ๐”ฝ3Vb \in \mathbb{F}_3^V be a charge with โˆ‘vโˆˆVb(v)=0\sum_{v \in V} b(v) = 0, and suppose some component Cโ€ฒC' of G\TG \setminus T has โˆ‘vโˆˆCโ€ฒb(v)โ‰ 0\sum_{v \in C'} b(v) \neq 0. Then some component CC of G\TG \setminus T satisfies โˆ‘vโˆˆCb(v)โ‰ 0and2|C|โ‰ค|V|.\sum_{v \in C} b(v) \neq 0 \quad \text{and} \quad 2\,|C| \le |V|.(4)โœฆ

(d) Suppose GG is the cubic grid of side LL and an assignment ฯƒโˆˆ๐”ฝ3T\sigma \in \mathbb{F}_3^T does not extend to a flow. Then some component CC of G\TG \setminus T satisfies โˆ‘vโˆˆC(โˆ‚ฯƒT)(v)โ‰ 0,2|C|โ‰คL3,|C|โ‰ค(|T|c)3/2.\sum_{v \in C} (\partial \sigma_T)(v) \neq 0, \qquad 2\,|C| \le L^3, \qquad |C| \le \Bigl(\frac{|T|}{c}\Bigr)^{3/2}.(5)โœฆ

In the paper, the result reads: for TโІET \subseteq E and ฯƒโˆˆ๐”ฝ3T\sigma \in \mathbb{F}_3^T, some kโˆˆker⁡โˆ‚k \in \ker \partial has k|T=ฯƒk|_T = \sigma if and only if every component UU of G\TG \setminus T has RU=โˆ‘vโˆˆUโˆ‘eโˆˆT,eโˆ‹vฮตveฯƒe=0R_U = \sum_{v \in U} \sum_{e \in T,\, e \ni v} \varepsilon_{ve}\, \sigma_e = 0, with ฮตve\varepsilon_{ve} the incidence sign of the vertex vv on the edge ee, and if no such kk exists, some nonempty component UU with RUโ‰ 0R_U \neq 0 has |U|โ‰คL3/2|U| \le L^3/2 and |U|โ‰ค(|T|/c)3/2|U| \le (|T|/c)^{3/2}.

What Is Checked

The four statements are made over a finite directed multigraph with its tail and head maps, a set TT of its edges, the field ๐”ฝ3\mathbb{F}_3, connectivity off TT with the edge relation that generates it, the components of G\TG \setminus T with their vertex sets, and the incidence map โˆ‚\partial of (1); (5) is made over the cubic grid of side L=n+1L = n + 1, its vertices, its edges along the three axes with their tails and heads, and the box constant cc. About these constructions the library proves that โˆ‚\partial is linear over ๐”ฝ3\mathbb{F}_3.