Frames commute with pointwise linear networks

Let $R$ be a commutative ring, $\mathcal W$ a finite set of wire roles and $\Omega$ an address set. Each wire carries an array in $R^\Omega$. A gate $g=(C_g,S_g,D_g)$ consists of the following:

• a coefficient matrix $C_g\in R^{\mathcal W\times\mathcal W}$, applied pointwise at every address, $(C_g f)_w(\omega)=\sum_{w'}C_g(w,w')f_{w'}(\omega)$;
• the set $S_g$ of wires it touches, with $C_g$ the identity on rows outside $S_g$ and rows in $S_g$ reading only wires in $S_g$;
• an invertible $R$-linear frame $D_g$ of $R^\Omega$.

Fix source frames $D^{\rm in}_w$ and sink frames $D^{\rm out}_w$. The physical execution keeps, for each wire, its current frame $F_w$, starting from $F_w=D^{\rm in}_w$ on the supplied arrays $f$. Before gate $g$ it applies the edge operator $D_gF_w^{-1}$ to each touched wire, then applies $C_g$ pointwise, and sets $F_w=D_g$ on touched wires. After the last gate it applies the sink edge $D^{\rm out}_wF_w^{-1}$. The logical execution applies the gates $C_g$ pointwise to $g=(D^{\rm in})^{-1}f$. Then for every wire $w$,

so the implemented operator is $D^{\rm out}\,S_\Omega\,(D^{\rm in})^{-1}$.

This is the representation principle of §3.2 (equation (5)) of the OpenAI preprint Integer multiplication below $n\log n$. It allows a finite linear network to be run on whole arrays while each wire's array changes representation along the way. Every κ-saving construction (the OpenAI networks, Colkitt's and Jain's rounds) uses it to turn cheap edge operators into a full address interchange or butterfly layer.

Formalization Note A gate is a triple (C, S, D) in a list, applied in order. The physical state is the pair (current frames, stored arrays).