OctoInform Beta

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

§4 (setting): the root augmentation (4.4): The pencil of Φ−1\Phi^{-1} borders that of Φ\Phi; where Φ\Phi is defined, it is invertible exactly when Φ\Phi has a unit value

The root augmentation detects whether a formula’s value is invertible.

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 noncommutative rational formula Φ\Phi in x1,…,xnx_1,\dots,x_n and a tuple X=(X1,…,Xn)X=(X_1,\dots,X_n) of d×dd\times d rational matrices. Evaluating Φ\Phi at XX asks at each inverse gate whether the value of the operand is invertible, and XX hits Φ\Phi when every answer is yes and the value of Φ\Phi is invertible as well. The questions at the inverse gates concern the inside of Φ\Phi; the last one concerns its root. The root augmentation is a single matrix for that last question, built from the linear pencil of Φ\Phi; it decides whether the value of Φ\Phi is invertible.

The library states the construction over any ring RR with a ring homomorphism c:ℚ→Rc\colon\mathbb{Q}\to R, at any point XX of RnR^n; tuples of d×dd\times d rational matrices are the case where RR is the matrix ring Matd(ℚ)\mathrm{Mat}_d(\mathbb{Q}).

Formulas, Values and Pencils

A rational formula Φ\Phi in nn variables is a finite tree built from the variables x1,…,xnx_1,\dots,x_n and rational constants α\alpha by addition Ψ+Θ\Psi+\Theta, multiplication ΨΘ\Psi\Theta in this order, and inversion Ψ−1\Psi^{-1}.✦ The inverse nodes of Φ\Phi are its subformulas of the form Ψ−1\Psi^{-1}, one for each inverse gate, listed in the order in which a depth-first walk from the root meets them, left operand before right.✦

The value relation at a point X=(X1,…,Xn)X=(X_1,\dots,X_n) of RnR^n is the least relation between formulas and elements of RR in which xix_i has value XiX_i, the constant α\alpha has value c(α)c(\alpha), the sum Ψ+Θ\Psi+\Theta and the product ΨΘ\Psi\Theta have values a+ba+b and abab when Ψ\Psi has value aa and Θ\Theta has value bb, and Ψ−1\Psi^{-1} has value bb when Ψ\Psi has a value aa with ab=ba=1ab=ba=1.✦ A formula Φ\Phi is defined at a point XX of RnR^n when it has a value at XX in the value relation.

A square matrix AA over RR of order qq is invertible when it has a two-sided inverse, a q×qq\times q matrix A′A' over RR with AA′=A′A=IqAA'=A'A=I_q.

An affine form λ\lambda in nn variables is an expression λ0+λ1x1+…+λnxn\lambda_0+\lambda_1x_1+\dots+\lambda_nx_n with rational coefficients λ0,…,λn\lambda_0,\dots,\lambda_n✦, and its value at XX is the element λ(X)=c(λ0)+∑i=1nc(λi)Xi\lambda(X)=c(\lambda_0)+\sum_{i=1}^{n}c(\lambda_i)\,X_i(1)✦ of RR.

The pencil of Φ\Phi is a square matrix LΦL_\Phi of affine forms, of order qΦq_\Phi, defined by recursion on Φ\Phi together with a rational column vΦv_\Phi and a rational row uΦu_\Phi of length qΦq_\Phi. The order is 22 at a leaf, qΨ+qΘq_\Psi+q_\Theta at Ψ+Θ\Psi+\Theta and at ΨΘ\Psi\Theta, and qΨ+1q_\Psi+1 at Ψ−1\Psi^{-1}✦; the pencil is Lxi=(1−xi01),Lα=(1−α01),LΨ+Θ=(LΨ00LΘ),LΨΘ=(LΨ−vΨuΘ0LΘ),LΨ−1=(LΨvΨuΨ0),\begin{aligned} L_{x_i} &= \begin{pmatrix} 1 & -x_i\\ 0 & 1 \end{pmatrix}, & L_{\alpha} &= \begin{pmatrix} 1 & -\alpha\\ 0 & 1 \end{pmatrix},\\ L_{\Psi+\Theta} &= \begin{pmatrix} L_\Psi & 0\\ 0 & L_\Theta \end{pmatrix}, & L_{\Psi\Theta} &= \begin{pmatrix} L_\Psi & -v_\Psi u_\Theta\\ 0 & L_\Theta \end{pmatrix},\\ L_{\Psi^{-1}} &= \begin{pmatrix} L_\Psi & v_\Psi\\ u_\Psi & 0 \end{pmatrix}, \end{aligned}(2)✦ and the column and row are vxi=vα=(01),uxi=uα=(10),vΨ+Θ=(vΨvΘ),uΨ+Θ=(uΨuΘ),vΨΘ=(0vΘ),uΨΘ=(uΨ0),vΨ−1=(01),uΨ−1=(0−1),\begin{aligned} v_{x_i} = v_\alpha &= \begin{pmatrix} 0\\ 1 \end{pmatrix}, & u_{x_i} = u_\alpha &= \begin{pmatrix} 1 & 0 \end{pmatrix},\\ v_{\Psi+\Theta} &= \begin{pmatrix} v_\Psi\\ v_\Theta \end{pmatrix}, & u_{\Psi+\Theta} &= \begin{pmatrix} u_\Psi & u_\Theta \end{pmatrix},\\ v_{\Psi\Theta} &= \begin{pmatrix} 0\\ v_\Theta \end{pmatrix}, & u_{\Psi\Theta} &= \begin{pmatrix} u_\Psi & 0 \end{pmatrix},\\ v_{\Psi^{-1}} &= \begin{pmatrix} 0\\ 1 \end{pmatrix}, & u_{\Psi^{-1}} &= \begin{pmatrix} 0 & -1 \end{pmatrix}, \end{aligned}(3) with zero blocks of the sizes the orders give. The value LΦ(X)L_\Phi(X) of the pencil at XX is the matrix over RR obtained by evaluating each entry at XX✦, and c(vΦ)c(v_\Phi) and c(uΦ)c(u_\Phi) are vΦv_\Phi and uΦu_\Phi with cc applied to each entry.

The Claim

Theorem 1. Let Φ\Phi be a rational formula in nn variables with inverse nodes Ψ1−1,…,Ψk−1\Psi_1^{-1},\dots,\Psi_k^{-1}, let RR be a ring with a ring homomorphism c:ℚ→Rc\colon\mathbb{Q}\to R, and let XX be a point of RnR^n. The certificate nodes of Φ\Phi are its inverse nodes followed by Φ−1\Phi^{-1}, Cert(Φ)=(Ψ1−1,…,Ψk−1,Φ−1),\mathrm{Cert}(\Phi)=\bigl(\Psi_1^{-1},\dots,\Psi_k^{-1},\ \Phi^{-1}\bigr),(4)✦ and the root augmentation of Φ\Phi is the pencil JΦ=LΦ−1J_\Phi=L_{\Phi^{-1}} of the last of them, whose value at XX is JΦ(X)=(LΦ(X)c(vΦ)c(uΦ)0).J_\Phi(X)=\begin{pmatrix} L_\Phi(X) & c(v_\Phi)\\ c(u_\Phi) & 0 \end{pmatrix}.(5)✦ If AA is a square matrix of order qq over RR with a two-sided inverse A′A', and BB and CC are q×pq\times p and p×qp\times q matrices over RR, then (ABC0)is invertible⇔CA′Bis invertible,\begin{pmatrix} A & B\\ C & 0 \end{pmatrix}\ \text{is invertible} \iff CA'B\ \text{is invertible},(6)✦ where −CA′B-CA'B is the Schur complement of AA. If Φ\Phi has value aa at XX, then JΦ(X)is invertible⇔ais a unit ofR.J_\Phi(X)\ \text{is invertible} \iff a\ \text{is a unit of}\ R.(7)✦

In the paper, the result reads: the root augmentation is the matrix JΦ=(LΦvΦuΦ0)J_\Phi=\bigl(\begin{smallmatrix} L_\Phi & v_\Phi\\ u_\Phi & 0 \end{smallmatrix}\bigr), of the block form of the pencil at an inverse gate, with no inverse gate added to Φ\Phi.

What Is Checked

The claim is stated over rational formulas in nn variables and their inverse nodes, the value relation in a ring RR with a ring homomorphism from ℚ\mathbb{Q}, affine forms and their values at a point of RnR^n, and the pencil of a formula with its order, column and row. Beyond the claim, the library proves that evaluation at a point is additive on affine forms: the zero form has value 00, and the sum λ+μ\lambda+\mu of two forms has value λ(X)+μ(X)\lambda(X)+\mu(X).