OctoInform Beta

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

Proposition 4.2 [Pencil certificates for the original formula tree]: A formula of size ss has at most s+1s+1 pencils of order at most 2s+12s+1, all invertible exactly where its value is a unit

Inverse-gate pencils certify where a formula is defined.

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

Let ff be a noncommutative rational formula in x1,…,xnx_1,\dots,x_n and XX a tuple of d×dd\times d matrices over a field containing ℚ\mathbb Q. The formula has a value at XX only if every inverse gate receives an invertible matrix, and XX hits ff when that value exists and is itself invertible. Proposition 4.2 reads both conditions off a short list of linear pencils of small order, one for each inverse gate of ff and one for its root, at points of any ring receiving ℚ\mathbb Q. Headed by the trivial pencil 𝟏\mathbf 1 of order one, the same list yields the condition polynomials, defined below.

Formulas and Their Evaluation

A rational formula ff in nn variables is a finite tree whose leaves are the variables x1,…,xnx_1,\dots,x_n or rational constants and whose inner vertices are sums g+hg+h, ordered products g⋅hg\cdot h and inverses g−1g^{-1} of formulas already built.✦ The size |f||f| of ff is its number of vertices.✦ The vertex of ff itself is its root, and its vertices of the form g−1g^{-1} are its inverse gates.

Let RR be a ring and c:ℚ→Rc\colon\mathbb Q\to R a ring homomorphism. The evaluation of formulas 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, a constant aa has value c(a)c(a), g+hg+h and g⋅hg\cdot h have values y+zy+z and yzyz whenever gg has value yy and hh has value zz, and g−1g^{-1} has value zz whenever gg has a value yy with yz=zy=1yz=zy=1.✦ The evaluation domain dom⁡Rf\operatorname{dom}_Rf of ff is the set of points of RnR^n at which ff has a value, and dom⁡R×f\operatorname{dom}^\times_Rf is the set of those at which ff has a value that is a unit of RR.

A rational formula ff is nonzero if, for some d>0d>0, it has a value v≠0v\neq0 at some tuple of nn rational d×dd\times d matrices, a constant aa being read as the scalar matrix aIdaI_d.✦

The list ℐ(f)\mathcal I(f) of inverse occurrences of ff is the list of its subformulas of the form g−1g^{-1}, one entry for each occurrence, defined by recursion on ff, with juxtaposition for concatenation: ℐ(xi)=ℐ(a)=(),ℐ(g+h)=ℐ(g⋅h)=ℐ(g)ℐ(h),ℐ(g−1)=(g−1)ℐ(g).\mathcal I(x_i)=\mathcal I(a)=(\,),\qquad \mathcal I(g+h)=\mathcal I(g\cdot h)=\mathcal I(g)\,\mathcal I(h),\qquad \mathcal I(g^{-1})=(g^{-1})\,\mathcal I(g).(1)✦ The certificate list 𝒞(f)\mathcal C(f) of ff is the list of formulas 𝒞(f)=ℐ(f)(f−1),\mathcal C(f)=\mathcal I(f)\,(f^{-1}),(2) The last entry f−1f^{-1} is not an inverse gate of ff; its pencil is the augmentation of ff at its root.

Pencils

An affine form in nn variables is an expression a=a0+a1x1+…+anxna=a_0+a_1x_1+\dots+a_nx_n with rational a0,…,ana_0,\dots,a_n.✦ Its coefficient vector is (a0,…,an)∈ℚn+1(a_0,\dots,a_n)\in\mathbb Q^{n+1}.✦ An affine form aa is constant when its coefficient vector is (a0,0,…,0)(a_0,0,\dots,0).✦ The value of an affine form aa at X∈RnX\in R^n is a(X)=c(a0)+∑i=1nc(ai)Xia(X)=c(a_0)+\sum_{i=1}^nc(a_i)X_i.✦

A pencil LL of order qq is a q×qq\times q matrix of affine forms, written L=A0+∑i=1nAixiL=A_0+\sum_{i=1}^nA_ix_i with coefficient matrices A0,…,An∈Matq(ℚ)A_0,\dots,A_n\in\mathrm{Mat}_q(\mathbb Q), and L(X)∈Matq(R)L(X)\in\mathrm{Mat}_q(R) is the matrix of the values of its entries at XX. At a tuple of d×dd\times d matrices, L(X)L(X) is the block matrix A0⊗Id+∑iAi⊗XiA_0\otimes I_d+\sum_iA_i\otimes X_i up to the order of the basis.

The pencil LfL_f of a rational formula ff is the pencil of order qfq_f, twice the number of leaves of ff plus the number of its inverse gates, defined by recursion on ff as a block matrix whose rational blocks enter as constant forms: Lxi=(1−xi01),La=(1−a01),Lg+h=(Lg00Lh),Lg⋅h=(Lg−vguh0Lh),Lg−1=(Lgvgug0),\begin{gathered} L_{x_i}=\begin{pmatrix}1&-x_i\\0&1\end{pmatrix},\qquad L_a=\begin{pmatrix}1&-a\\0&1\end{pmatrix},\qquad L_{g+h}=\begin{pmatrix}L_g&0\\0&L_h\end{pmatrix},\\ L_{g\cdot h}=\begin{pmatrix}L_g&-v_gu_h\\0&L_h\end{pmatrix},\qquad L_{g^{-1}}=\begin{pmatrix}L_g&v_g\\u_g&0\end{pmatrix}, \end{gathered}(3) where the row ugu_g and the column vgv_g of a formula gg are the rational vectors of length qgq_g given by the recursions uxi=ua=(10),ug+h=(uguh),ug⋅h=(ug0),ug−1=(0−1),vxi=va=(01),vg+h=(vgvh),vg⋅h=(0vh),vg−1=(01),\begin{gathered} u_{x_i}=u_a=\begin{pmatrix}1&0\end{pmatrix},\quad u_{g+h}=\begin{pmatrix}u_g&u_h\end{pmatrix},\quad u_{g\cdot h}=\begin{pmatrix}u_g&0\end{pmatrix},\quad u_{g^{-1}}=\begin{pmatrix}0&-1\end{pmatrix},\\ v_{x_i}=v_a=\begin{pmatrix}0\\1\end{pmatrix},\quad v_{g+h}=\begin{pmatrix}v_g\\v_h\end{pmatrix},\quad v_{g\cdot h}=\begin{pmatrix}0\\v_h\end{pmatrix},\quad v_{g^{-1}}=\begin{pmatrix}0\\1\end{pmatrix}, \end{gathered}(4) with the blocks following those of LL, the new index of Lg−1L_{g^{-1}} last.

For a list ℋ\mathcal H of formulas, 𝒰R(ℋ)\mathcal U_R(\mathcal H) is the set of points X∈RnX\in R^n at which Lh(X)L_h(X) is a unit of Matqh(R)\mathrm{Mat}_{q_h}(R) for every hh in ℋ\mathcal H.

The Condition Polynomials

Fix e≥0e\ge0 and put M=2e+1M=2^{e+1} and ℓ=M/2\ell=M/2. The MM-th cyclotomic field ℛ=ℚ[ξ]/(ξℓ+1)\mathcal R=\mathbb Q[\xi]/(\xi^\ell+1) is ℚ\mathbb Q with a primitive MM-th root of unity ξ\xi adjoined✦, and χ(k)=ξk\chi(k)=\xi^k is the additive character of ℤ/M\mathbb Z/M with values in ℛ\mathcal R✦.

For a point μ∈ℛ\mu\in\mathcal R and a natural number NN, the test matrix Rμ(t)R_\mu(t) is the M×MM\times M matrix over ℛ[t]\mathcal R[t], with rows and columns indexed by ℤ/M\mathbb Z/M through 0,…,M−10,\dots,M-1, of the Taylor test at μ\mu with its columns from NN on set to zero: Rμ(t)ij={∑k=0M−1tk[xi](x−μ)M−1−k[xk](x+μ)j,j<N,0,j≥N,R_\mu(t)_{ij}= \begin{cases} \displaystyle\sum_{k=0}^{M-1}t^k\,[x^i](x-\mu)^{M-1-k}\,[x^k](x+\mu)^j, & j<N,\\[6pt] 0, & j\ge N, \end{cases}(5)✦ where [xi]g[x^i]g is the coefficient of xix^i in gg. The test matrix at the point i∈{0,…,n}i\in\{0,\dots,n\} is written Ri(t)R_i(t).

The lift Q*Q^* of a matrix QQ over ℛ[t]\mathcal R[t] indexed by ℤ/M\mathbb Z/M is the matrix of polynomials over ℛ\mathcal R in the three variables t,p,rt,p,r given by Q*=∑a,b∈ℤ/Mcab(t)DaSbparb,cab(t)=1M∑j∈ℤ/Mχ(−aj)Qj,j−b(t),Q^*=\sum_{a,b\in\mathbb Z/M}c_{ab}(t)\,D^aS^b\,p^ar^b,\qquad c_{ab}(t)=\frac1M\sum_{j\in\mathbb Z/M}\chi(-aj)\,Q_{j,\,j-b}(t),(6)✦ where the Weyl monomial DaSbD^aS^b has entry χ(ai)\chi(ai) in row ii and column jj when i=j+bi=j+b and 00 otherwise, and the exponents of pp and rr are the least nonnegative representatives of aa and bb. The polynomials cab(t)c_{ab}(t) are the Fourier coefficients of QQ: the coefficients of the cyclic-diagonal Fourier transform of QQ along the Weyl monomials DaSbD^aS^b.

Given ee and NN, the condition polynomial PLP_L of a pencil L=A0+∑iAixiL=A_0+\sum_iA_ix_i of order qq is the determinant of order qMqM PL=det⁡(∑i=0nAi⊗Ri(t))*∈ℛ[t,p,r].P_L=\det\Bigl(\,\sum_{i=0}^{n}A_i\otimes R_i(t)\Bigr)^{*}\in\mathcal R[t,p,r].(7)✦

The trivial pencil 𝟏\mathbf 1 is the pencil of order one whose entry is the constant form 11: 𝟏=(1).\mathbf 1=(1).(8)✦ The condition list of a formula ff with 𝒞(f)=(h1,…,hm)\mathcal C(f)=(h_1,\dots,h_m) is (P𝟏,PLh1,…,PLhm)(P_{\mathbf 1},P_{L_{h_1}},\dots,P_{L_{h_m}}), the trivial pencil first.✦

The Claim

Theorem 1 (Proposition 4.2). Let ff be a rational formula in nn variables with certificate list 𝒞(f)=(h1,…,hm)\mathcal C(f)=(h_1,\dots,h_m), let s≥1s\ge1 and B=2s+1B=2s+1, and let RR be a ring with a ring homomorphism c:ℚ→Rc\colon\mathbb Q\to R.

  1. If |f|≤s|f|\le s, then m≤s+1,1≤qhj≤B(j=1,…,m).m\le s+1,\qquad 1\le q_{h_j}\le B\quad(j=1,\dots,m).(9)✦

  2. The pencils of the inverse occurrences of ff are invertible on its evaluation domain, dom⁡Rf⊆𝒰R(ℐ(f)),\operatorname{dom}_Rf\subseteq\mathcal U_R(\mathcal I(f)),(10)✦ and ff has a value wherever they are all invertible: 𝒰R(ℐ(f))⊆dom⁡Rf.\mathcal U_R(\mathcal I(f))\subseteq\operatorname{dom}_Rf.(11)✦

  3. The certificate pencils are all invertible at a point exactly when ff has there a value that is a unit of RR: 𝒰R(𝒞(f))=dom⁡R×f.\mathcal U_R(\mathcal C(f))=\operatorname{dom}^\times_Rf.(12)✦

  4. Suppose |f|≤s|f|\le s and ff is nonzero. Put w=n+1w=n+1 and Δ=2w3B\Delta=2w^3B, and let M=2e+1M=2^{e+1} and N=M−ΔN=M-\Delta with M>BΔM>B\Delta and N≥1N\ge1. Then, for these ee and NN, every polynomial of the condition list of ff is nonzero: P𝟏≠0,PLhj≠0(j=1,…,m).P_{\mathbf 1}\neq0,\qquad P_{L_{h_j}}\neq0\quad(j=1,\dots,m).(13)✦

In the paper, the result reads: for a formula Φ\Phi of size at most ss, with B=2s+1B=2s+1 and 𝒞Φ\mathcal C_\Phi the indexed collection of the pencils LhL_h of the inverse-node occurrences hh of Φ\Phi together with the root augmentation JΦJ_\Phi, the collection 𝒞Φ\mathcal C_\Phi contains at most s+1s+1 affine pencils over ℚ\mathbb Q, each of positive order at most BB; at every tuple of matrices of a common positive order over a field extension of ℚ\mathbb Q, all pencils in 𝒞Φ\mathcal C_\Phi are invertible if and only if the original tree Φ\Phi is defined there and its value is invertible; if Φ\Phi is admissible, that is, defined at some tuple of rational matrices of positive order, and nonzero, there is a single tuple over some field extension of ℚ\mathbb Q at which every pencil in 𝒞Φ\mathcal C_\Phi is invertible; and adding the order-one constant pencil 𝟏\mathbf 1 gives at most s+2s+2 pencils of order at most BB with this last property, Φ\Phi standing for ff and JΦJ_\Phi for Lf−1L_{f^{-1}}.

What Is Checked

The claim is stated over rational formulas in nn variables, their size and their evaluation at points of a ring receiving ℚ\mathbb Q, nonzero formulas, defined through tuples of rational matrices, the inverse occurrences and the certificate list, affine forms and the pencils LfL_f with their entrywise values, and the condition polynomials over the cyclotomic field ℛ\mathcal R, built from the coefficient matrices, the Taylor test matrices with their columns from NN on set to zero, the Weyl monomials and the lift.

The sum a+ba+b of affine forms aa and bb in nn variables is the affine form whose coefficient vector is the sum of their coefficient vectors, and the zero form is the affine form in nn variables all of whose coefficients are zero. The value of an affine form at a point is additive in the form: the zero form has value 00, and (a+b)(X)=a(X)+b(X)(a+b)(X)=a(X)+b(X) for forms aa and bb.