OctoInformBeta

OpenAI preprint, September 2026 Β· Β§7. Typed data channels

Lemma 38: Signed walks with prescribed endpoints and parities connect two product profile triples to direct observation layers

Forbidden configurations determine channel paths.

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 graph data for two typed data channels consist of product profiles and paths with prescribed parity. The question is whether a forbidden configuration supplies all the required endpoints at once.

A pure type system specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) consists of a set SS of sorts, an arbitrary axiom relation π’œβŠ†SΓ—S\mathcal A\subseteq S\times S, and an arbitrary product-rule relation β„›βŠ†SΓ—SΓ—S\mathcal R\subseteq S\times S\times S.✦ Terms are variables, sort constants, applications MNM\,N, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ Displayed variable names stand for de Bruijn indices, with zero denoting the nearest binder; contexts are written newest first.

The typing judgement Ξ“βŠ’M:A\Gamma\vdash M:A uses the specification’s axiom and product rules together with variable introduction, weakening, abstraction, application, and conversion to a Ξ²\beta-convertible expected type having a sort. A valid context Ξ“\Gamma for PP is a finite context generated from the empty context by adjoining x:Ax:A whenever Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦

Full one-step β\beta reduction contracts (λx:A.M)N(\lambda x:A.M)\,N to the capture-avoiding substitution M[N/x]M[N/x] and is closed under every term constructor, including annotations and binder bodies.✦ The relation of β\beta convertibility is the least equivalence relation containing full one-step β\beta reduction.✦ A β\beta normal form NN is a term that admits no full one-step β\beta reduction.✦ A weakly normalizing term TT is a term from which finitely many full one-step β\beta reductions reach a normal form.✦ Write T#T^\# for the unique full normal form of TT when it exists, with a fixed fallback otherwise.✦

The normal form sort profile πΓ(T)\pi_\Gamma(T) is the set of all sorts typing T#T^\#, as in (1). πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s}.\pi_\Gamma(T)=\{s\in S\mid\Gamma\vdash T^\#:s\}.(1)✦ A feasible sort profile IβŠ†SI\subseteq S is a nonempty set equal to πΓ(T)\pi_\Gamma(T) for some valid context Ξ“\Gamma and some normal term TT.✦

The axiom profile Ax⁡(s)\operatorname{Ax}(s) and the product output profile Out⁡(I,J)\operatorname{Out}(I,J) are the sets specified in (2). Ax⁡(s)={t∈S∣(s,t)βˆˆπ’œ},Out⁡(I,J)={c∈Sβˆ£βˆƒa∈Iβˆƒb∈J(a,b,c)βˆˆβ„›}.\begin{aligned} \operatorname{Ax}(s)&=\{t\in S\mid(s,t)\in\mathcal A\},\\ \operatorname{Out}(I,J)&= \{c\in S\mid\exists a\in I\;\exists b\in J\;(a,b,c)\in\mathcal R\}. \end{aligned}(2) A feasible product profile triple (I,J,K)(I,J,K) consists of feasible sort profiles with K=Out⁡(I,J)K=\operatorname{Out}(I,J); its domain profile is II and its codomain profile is JJ.✦

Signed Profile Graphs

The primary and secondary graphs are signed directed graphs on sets of sorts. An edge has sign 00 when positive and sign 11 when negative. A signed directed walk I″ibJI\leadsto_i^b J in graph ii is a finite walk whose number of negative edges has parity b∈{0,1}b\in\{0,1\}; repeated edges are permitted, and an empty walk has parity 00.✦ The positive reachability relation in graph ii, written I″i+JI\leadsto_i^+J, relates vertices II and JJ when there is a finite, possibly empty walk from II to JJ consisting entirely of positive edges.✦ Directed reachability in a signed graph is the relation between pairs of vertices joined by a finite walk of either parity.✦

The primary graph, indexed by 11, has positive inclusion edges Iβ†’JI\to J when I,JI,J are feasible and J⊊IJ\subsetneq I. Each feasible product profile triple (I,J,K)(I,J,K) gives a negative domain edge Iβ†’KI\to K and a positive codomain edge Jβ†’KJ\to K. These are exactly its edges.

Fix a family CβŠ†π’«(S)C\subseteq\mathcal P(S) of sets of sorts. The observation layers for CC are the profiles in the family π’ͺC\mathcal O_C of (3). π’ͺC={IβŠ†Sβˆ£βˆƒs∈S{s}∈C,Ax⁡(s)β‰ βŒ€,Ax⁡(s)β€³1+I}.\mathcal O_C= \{I\subseteq S\mid\exists s\in S\; \{s\}\in C,\quad\operatorname{Ax}(s)\ne\varnothing,\quad \operatorname{Ax}(s)\leadsto_1^+ I\}.(3)✦ The secondary graph, indexed by 22, consists of positive primary edges whose endpoints belong to π’ͺC\mathcal O_C, and negative edges Iβ†’KI\to K arising from feasible product profile triples (I,J,K)(I,J,K) with I,J,K∈π’ͺCI,J,K\in\mathcal O_C.✦

A direct observation layer II is a member of π’ͺC\mathcal O_C for which some J,K∈CJ,K\in C form a feasible product profile triple (I,J,K)(I,J,K).✦ A plain observation layer II is a profile with both an even signed walk and an odd signed walk in the secondary graph to direct observation layers, which may differ.✦

A strongly connected component DD of a signed graph is the set of vertices mutually reachable with some vertex r∈Dr\in D.✦ A forbidden configuration DD for (P,C)(P,C) is a strongly connected component of the secondary graph whose vertices are all plain observation layers, which contains a negative edge, and for which there are a feasible product profile triple (I,J,K)(I,J,K) and a sort ss with J,K,{s}∈DJ,K,\{s\}\in D, a nonempty axiom profile Ax⁡(s)\operatorname{Ax}(s), and positive primary reachability Ax⁡(s)β€³1+I\operatorname{Ax}(s)\leadsto_1^+ I.

The Claim

Theorem 1. Suppose (P,C)(P,C) admits a forbidden configuration. There are a strongly connected component DD of the secondary graph, a sort s∈Ss\in S, feasible product profile triples (I,J,K)(I,J,K) and (p,n,g)(p,n,g), and direct observation layers do,ded_o,d_e satisfying (4). J,K,{s},p,g∈D,n∈π’ͺC,Ax⁡(s)β‰ βŒ€,Ax⁡(s)β€³1+I,Kβ€³21p,pβ€³21K,gβ€³20J,Kβ€³21do,Kβ€³20de,pβ€³21de.\begin{gathered} J,K,\{s\},p,g\in D,\qquad n\in\mathcal O_C,\\ \operatorname{Ax}(s)\ne\varnothing,\qquad \operatorname{Ax}(s)\leadsto_1^+ I,\\ K\leadsto_2^1p,\qquad p\leadsto_2^1K,\qquad g\leadsto_2^0J,\\ K\leadsto_2^1d_o,\qquad K\leadsto_2^0d_e,\qquad p\leadsto_2^1d_e. \end{gathered}(4)✦

What Is Checked

The statement is over arbitrary pure type system specifications and families of sort sets admitting a forbidden configuration in their secondary signed graph.