Elementary edge transfers and ordered products
Let \(V\) be a set of vertices, \(E\) a set of directed edges, and \(s,t:E\to V\) their source and target maps. A vector over a semiring \(R\) is a function \(v:V\to R\); its coordinate at \(z\) is \(v_z\). The semiring can, for example, be \(\mathbb R\) or a polynomial ring. Fix a coefficient \(T\in R\).
One elementary transfer
For \(e\in E\), define
\[
(U_e(T)v)_z=
\begin{cases}
v_z+T v_{t(e)},&z=s(e),\\
v_z,&z\ne s(e).
\end{cases}
\]
This is SchedulePaths.step. It adds a multiple of the upper coordinate to the lower coordinate. The two summands use the input vector. If \(s(e)\ne t(e)\), the target coordinate stays unchanged.
With a finite vertex set and column-vector notation, define \(E_{xy}\) by
\[
(E_{xy}v)_z=\begin{cases}v_y,&z=x,\\0,&z\ne x.\end{cases}
\]
Then \(U_e(T)=1+T E_{s(e),t(e)}\), where \(1\) is the identity operator. For real scalars, Comparison.transfer T x y gives the same formula with the two endpoints supplied directly. The transfer properties prove monotonicity for \(T\ge0\) and injectivity when the endpoints are distinct.
The product associated with a list
Write \(\mathcal D_p(T)v\) for SchedulePaths.dispatch. Its recursion is
\[
\mathcal D_{[]}(T)v=v,\qquad
\mathcal D_{e::p}(T)v=U_e(T)\bigl(\mathcal D_p(T)v\bigr).
\]
Here \(e::p\) means the list with first entry \(e\) and tail \(p\). Thus
\[
\mathcal D_{[e_1,e_2,e_3]}(T)v
=U_{e_1}(T)\bigl(U_{e_2}(T)(U_{e_3}(T)v)\bigr).
\]
The first edge in this list supplies the outermost operator.
A chronological list \(p=[e_1,\ldots,e_r]\) processes \(e_1\) first and \(e_r\) last. Its composite is consequently \[ U_{e_r}(T)\cdots U_{e_1}(T) =\mathcal D_{p^{\mathrm{rev}}}(T), \] where \(p^{\mathrm{rev}}=[e_r,\ldots,e_1]\). Reversal converts chronological order to the source's product convention.
The alternative Comparison.idealState uses an edge sequence \((x_j,y_j)\), an initial vector \(v\), and a natural-number index:
\[
E_0=v,\qquad E_{j+1}=\tau_{x_j,y_j,T}E_j.
\]
For the first \(r\) edges of a chronological list, this gives \(E_r=\mathcal D_{p^{\mathrm{rev}}}(T)v\).
A two-edge calculation
Take distinct vertices \(x,y,z\), edges \(e:x\to y\), \(f:y\to z\), and a vector with coordinates \((a,b,c)\). Processing \(f\) and then \(e\) gives \[ (a,b,c)\xmapsto{U_f}(a,b+Tc,c) \xmapsto{U_e}(a+Tb+T^2c,b+Tc,c). \] The chronological list is \([f,e]\), and the resulting operator is \(\mathcal D_{[e,f]}=U_eU_f\). The term \(T^2c\) reaches \(x\) through the path \(x\to y\to z\).
Processing \(e\) first gives \[ (a,b,c)\xmapsto{U_e}(a+Tb,b,c) \xmapsto{U_f}(a+Tb,b+Tc,c). \] For the illustrative values \(T=2\), \((a,b,c)=(1,2,3)\), the two final vectors are \((17,8,3)\) and \((5,8,3)\), respectively. The first calculation explains how the later path expansion records the order in which contributions reach a coordinate.
Relation to the OpenAI notes
Coordinate operators and ordered products.
OpenAI notes: The notes attach a matrix 1+T E_xy to each edge and apply these matrices in chronological order. Their product is subsequently expanded into decreasing-label paths. eq:step, eq:comparison.
Lean (primary): The operator is defined on functions from the vertex type, over any semiring. Dispatch puts the head edge outside the recursively computed tail, so a chronological list must be reversed. Real monotonicity uses T >= 0; injectivity uses distinct endpoints. Concatenation is an explicit recursive identity. ReflectionSchedules:1172, ReflectionSchedules:1177, PositiveTransfer:822, PositiveTransfer:830, PositiveTransfer:843, PositiveTransfer:849, PositiveTransfer:858.
Role in the proof: The coordinate calculation explains the matrix action and the list reversal. The two-edge example records the degree-two contribution when an upper-edge transfer precedes the lower-edge transfer.
References
The local source declarations below give the construction and proof.
Lean formalization
OAI.KLInvariance.Comparison.transfer: Comparison.lean:74.
OAI.KLInvariance.Comparison.idealState: Comparison.lean:98.
OAI.KLInvariance.SchedulePaths.step: ReflectionSchedules.lean:1172.
OAI.KLInvariance.SchedulePaths.dispatch: ReflectionSchedules.lean:1177.