OctoInform Beta

OpenAI preprint, September 2026 · §4. Encoding a formula and its evaluation domain · §4

Lemma 4.1 [Affine realization of a subtree]: At a point where hh has value aa in a ring receiving ℚ\mathbb{Q}, the pencil LhL_h is invertible and uhLh−1vh=au_h L_h^{-1} v_h = a

Every rational formula is realized by an affine pencil.

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

A noncommutative rational formula hh in x1,…,xnx_1,\dots,x_n is evaluated at tuples of matrices, and more generally at points of RnR^n for a ring RR into which ℚ\mathbb{Q} maps; at a given point it may have no value, since each inverse needs an invertible operand. The item builds, by recursion over the structure of hh, a square matrix LhL_h of affine forms with a rational row uhu_h and a rational column vhv_h.

Formulas and Their Values

A rational formula in nn variables is a finite rooted tree whose leaves carry the variables x1,…,xnx_1,\dots,x_n or rational constants and whose inner vertices, the gates, are sums f+gf+g, products fgfg taken in this order, and inverses f−1f^{-1}.✦ The size |h||h| of a formula hh is its number of vertices: 11 for a variable or a constant, |f|+|g|+1|f|+|g|+1 for f+gf+g and for fgfg, and |f|+1|f|+1 for f−1f^{-1}.✦

Fix a ring RR, not necessarily commutative, a ring homomorphism c:ℚ→Rc\colon\mathbb{Q}\to R and a point X=(X1,…,Xn)∈RnX=(X_1,\dots,X_n)\in R^n. The evaluation relation at XX is the smallest relation between formulas and elements of RR in which xix_i has value XiX_i, a constant rr has value c(r)c(r), f+gf+g and fgfg have values a+ba+b and abab whenever ff and gg have values aa and bb, and f−1f^{-1} has value bb whenever ff has a value aa with ab=ba=1ab=ba=1.✦ A formula is defined at XX when it has a value there. For the ring R=Matd(K)R=\mathrm{Mat}_d(K) of d×dd\times d matrices over a field KK containing ℚ\mathbb{Q}, a point is a tuple of d×dd\times d matrices.

Affine Pencils

An affine form in nn variables is an expression α=α0+α1x1+…+αnxn\alpha=\alpha_0+\alpha_1x_1+\dots+\alpha_nx_n with rational α0,…,αn\alpha_0,\dots,\alpha_n.✦ The value of an affine form α\alpha at XX is the element α(X)=c(α0)+∑i=1nc(αi)Xi\alpha(X)=c(\alpha_0)+\sum_{i=1}^{n}c(\alpha_i)\,X_i(1)✦ of RR.

An affine pencil of order qq is a q×qq\times q matrix L=A0+∑i=1nAixiL=A_0+\sum_{i=1}^{n}A_ix_i of affine forms, with rational q×qq\times q matrices A0,…,AnA_0,\dots,A_n; its evaluation L(X)L(X) is the q×qq\times q matrix over RR whose entries are the values (1) of those of LL. For R=Matd(K)R=\mathrm{Mat}_d(K), the matrix L(X)L(X), read as a qd×qdqd\times qd matrix over KK, is A0⊗Id+∑i=1nAi⊗XiA_0\otimes I_d+\sum_{i=1}^{n}A_i\otimes X_i up to the order of the basis. A rational matrix is read over RR through cc, entry by entry.

The Pencil of a Formula

The index set IhI_h of a formula hh is the finite set built along hh: two elements for a variable or a constant, the disjoint union If⊔IgI_f\sqcup I_g for f+gf+g and for fgfg, and IfI_f with one new element for f−1f^{-1}.✦ Its cardinality is |Ih|=|h|+1.|I_h|=|h|+1.(2)✦

The row uhu_h and the column vhv_h of hh are the rational vectors indexed by IhI_h given by the recursions uxi=ur=(10),uf+g=(ufug),ufg=(uf0),uf−1=(0−1),u_{x_i}=u_r=\begin{pmatrix}1&0\end{pmatrix},\quad u_{f+g}=\begin{pmatrix}u_f&u_g\end{pmatrix},\quad u_{fg}=\begin{pmatrix}u_f&0\end{pmatrix},\quad u_{f^{-1}}=\begin{pmatrix}0&-1\end{pmatrix},(3)✦ vxi=vr=(01),vf+g=(vfvg),vfg=(0vg),vf−1=(01),v_{x_i}=v_r=\begin{pmatrix}0\\1\end{pmatrix},\quad v_{f+g}=\begin{pmatrix}v_f\\v_g\end{pmatrix},\quad v_{fg}=\begin{pmatrix}0\\v_g\end{pmatrix},\quad v_{f^{-1}}=\begin{pmatrix}0\\1\end{pmatrix},(4)✦ Here ff and gg are formulas, rr is a rational constant, and the blocks follow the decomposition of IhI_h, the new element of If−1I_{f^{-1}} last.

The pencil LhL_h of a formula hh is the affine pencil indexed by IhI_h given by the recursion Lxi=(1−xi01),Lr=(1−r01),Lf+g=(Lf00Lg),Lfg=(Lf−vfug0Lg),Lf−1=(Lfvfuf0),\begin{gathered} L_{x_i}=\begin{pmatrix}1&-x_i\\0&1\end{pmatrix},\qquad L_r=\begin{pmatrix}1&-r\\0&1\end{pmatrix},\qquad L_{f+g}=\begin{pmatrix}L_f&0\\0&L_g\end{pmatrix},\\ L_{fg}=\begin{pmatrix}L_f&-v_fu_g\\0&L_g\end{pmatrix},\qquad L_{f^{-1}}=\begin{pmatrix}L_f&v_f\\u_f&0\end{pmatrix}, \end{gathered}(5)✦ in which the rational blocks vfugv_fu_g, vfv_f and ufu_f stand for constant forms.

The Claim

Theorem 1 (Affine realization). Let RR be a ring with a ring homomorphism c:ℚ→Rc\colon\mathbb{Q}\to R, let X∈RnX\in R^n, and let hh be a rational formula in nn variables that has value aa at XX. Then Lh(X)L_h(X) has a two-sided inverse over RR, and uhLh(X)−1vh=a.u_h\,L_h(X)^{-1}\,v_h=a.(6)✦

In the paper, the result reads: for each subtree hh of a formula there are an affine pencil LhL_h of order qh=2λ(h)+ι(h)=|h|+1q_h=2\lambda(h)+\iota(h)=|h|+1, with λ(h)\lambda(h) and ι(h)\iota(h) the numbers of leaves and of inverse gates of hh, and a constant rational row uhu_h and column vhv_h of length qhq_h, such that at every tuple of matrices over every field extension of ℚ\mathbb{Q} at which hh is defined, LhL_h is invertible and h=uhLh−1vhh=u_hL_h^{-1}v_h.

What Is Checked

The claim is stated over rational formulas and their evaluation relation at a point of RnR^n, for a ring RR with a ring homomorphism c:ℚ→Rc\colon\mathbb{Q}\to R, and over the index set, the row, the column and the pencil of a formula, (3), (4) and (5), the pencil evaluated entrywise by (1).

About these constructions the library proves the count (2) and the following. Evaluation at XX follows the recursion (5): for formulas ff and gg, Lf+g(X)=(Lf(X)00Lg(X)),L_{f+g}(X)=\begin{pmatrix}L_f(X)&0\\0&L_g(X)\end{pmatrix},(7)✦ Lfg(X)=(Lf(X)−vfug0Lg(X)),L_{fg}(X)=\begin{pmatrix}L_f(X)&-v_fu_g\\0&L_g(X)\end{pmatrix},(8)✦ Lf−1(X)=(Lf(X)vfuf0).L_{f^{-1}}(X)=\begin{pmatrix}L_f(X)&v_f\\u_f&0\end{pmatrix}.(9)✦

For every a∈Ra\in R, the matrix (1−a01)\begin{pmatrix}1&-a\\0&1\end{pmatrix} over RR has a two-sided inverse, and (10)(1−a01)−1(01)=a.\begin{pmatrix}1&0\end{pmatrix}\begin{pmatrix}1&-a\\0&1\end{pmatrix}^{-1} \begin{pmatrix}0\\1\end{pmatrix}=a.(10)✦

Let (ABC0)\begin{pmatrix}A&B\\C&0\end{pmatrix} be a block matrix over RR whose block AA is square with a two-sided inverse A−1A^{-1}. It has the Schur factorization (ABC0)=(10CA−11)(A00−CA−1B)(1A−1B01),\begin{pmatrix}A&B\\C&0\end{pmatrix}=\begin{pmatrix}1&0\\CA^{-1}&1\end{pmatrix} \begin{pmatrix}A&0\\0&-CA^{-1}B\end{pmatrix}\begin{pmatrix}1&A^{-1}B\\0&1\end{pmatrix},(11)✦ and when CA−1BCA^{-1}B also has a two-sided inverse, so does the block matrix, with (0−1)(ABC0)−1(01)=(CA−1B)−1.\begin{pmatrix}0&-1\end{pmatrix}\begin{pmatrix}A&B\\C&0\end{pmatrix}^{-1} \begin{pmatrix}0\\1\end{pmatrix}=(CA^{-1}B)^{-1}.(12)✦