A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 3 · Uniform identity testing for noncommutative formulas
Uniform Matrix Hitting Points in Every Positive Characteristic
expertly designed by an internal OpenAI model · released 2026-10-04
· original PDF
IntroductionPolynomial identity testing asks whether a polynomial given by arithmetic operations is zero. In the noncommutative setting, variables are evaluated on matrices: scalar substitutions would, for example, erase the nonzero commutator \(x_1x_2-x_2x_1\). The question considered here is whether one can construct a single matrix substitution, using only the characteristic, the number of variables, and a formula-size bound, that detects every nonzero formula of that size. We construct such a substitution over the prime field in every positive characteristic. Its dimension and the time needed to print all its entries are polynomially bounded. The resultFor a field \(F\), the free associative algebra \(F\langle x_1,\ldots,x_n\rangle\) has as an \(F\)-basis the finite ordered words in \(x_1,\ldots,x_n\), including the empty word \(1\); multiplication concatenates words. A noncommutative formula is a rooted tree whose leaves are variables or scalars in \(F\), and whose internal vertices are binary addition or ordered multiplication gates. Its size is the number of all vertices, including scalar leaves. Thus there are no inverse gates and no shared subexpressions. Scalars may be arbitrary elements of \(F\). When evaluating at \(d\times d\) matrices, a scalar \(a\) is interpreted as \(aI_d\). Theorem 1. There is a deterministic Turing machine and absolute positive integers \(C,k\) with the following property. Given a prime \(p\) in binary and positive integers \(n,s\) in unary, the machine outputs a positive integer \(d=O(n^3s^6)\) and a tuple \[(T_1,\ldots,T_n)\in\mathop{\mathrm{Mat}}_d(\mathbb F_p)^n.\] For every field \(F\) of characteristic \(p\) and every nonzero \(f\in F\langle x_1,\ldots,x_n\rangle\) computed by a formula of size at most \(s\), the same tuple, viewed over \(F\), satisfies \[f(T_1,\ldots,T_n)\ne0.\] Writing \(L=\lceil\log_2p\rceil\), the total running time and output length are at most \(C(n+s+L+1)^k\). All matrix entries are output densely as ordinary binary residues in \(\{0,\ldots,p-1\}\), with dimensions and separators included. Primality of \(p\) is promised. The generator receives no formula or coefficients. In particular, its guarantee is uniform over arbitrary extensions of \(\mathbb F_p\), and applies to \(p=2\) without any relation between the characteristic and the formula size. The required conclusion is matrix nonvanishing. The time to evaluate a formula over an unspecified coefficient field is separate from the bit complexity of constructing the tuple. The proof also applies to an acyclic algebraic path program: a finite directed acyclic graph with a designated source and sink, edges labelled by scalars or variables, and value equal to the sum of ordered label products over source–sink paths. Replacing the formula-size parameter by the number of vertices gives the same polynomial construction; see Corollary 9. This extension follows from the coefficient representation used in the proof. Context and the characteristic obstructionNoncommutative identity testing has distinct tests that use the internal representation and tests that only evaluate the polynomial. Nisan characterized homogeneous noncommutative branching-program complexity by ranks of coefficient matrices (Nisan 1991, Theorem 1). Raz and Shpilka gave a deterministic polynomial-time identity test for noncommutative formulas and algebraic branching programs when their descriptions are available (Raz and Shpilka 2005). Matrix evaluation also underlies randomized black-box tests; Bogdanov and Wee gave such a test for circuits with a supplied degree bound, using polynomial identities of matrix algebras (Bogdanov and Wee 2005, Theorem 4.2). For deterministic black-box testing, Forbes and Shpilka constructed quasipolynomial-size matrix hitting sets for noncommutative algebraic branching programs, under a field-cardinality hypothesis (Forbes and Shpilka 2013, Corollary 4.7). A block-diagonal sum can combine a finite hitting set into one tuple, but its dimension grows with the size of that set. Lakhani and Mukhopadhyay constructed one integer matrix tuple for sparsity-bounded polynomials over characteristic-zero fields (Lakhani and Mukhopadhyay 2026, Theorem 2.1 and Remark 2.6); their finite-field formulation also distinguishes a succinct extension-field description from its explicit coordinate cost. Sparsity is a different parameter: a formula of small size can have exponentially many words. These results provide relevant benchmarks, while the construction here is polynomial in formula size and in the binary length of the characteristic. The characteristic-zero companion (OpenAI 2026, Theorem 1.1) constructs one rational matrix tuple for formulas, with dimension at most \(2ns^2\) and polynomial bit complexity. Its proof encodes words by iterated integrals, puts the encoding of a formula into a finite differential system, and applies an order-of-vanishing bound before truncating. The representation by an acyclic path program is independent of the characteristic. The analytic-looking part of the construction is not: formal integration divides by positive integers, ordinary differentiation annihilates \(p\)th powers in characteristic \(p\), and distinct integer pole locations may coincide. Nor does reduction of a rational hitting tuple automatically preserve its guarantee at every prime. We retain the word-series and matrix-system organization, replacing the differential operator by an infinite-order multiplicative shift. The resulting order bound and the final descent to prime-field matrices are proved directly in the given characteristic. The dimension bound is larger than in the companion, but remains polynomial without any lower bound on \(p\). Proof strategyFix an arbitrary coefficient field \(F\) and introduce an indeterminate \(t\) over it. Over \(K=F(t)\), let \(\sigma\) act on formal series in \(z\) by \(\sigma(g)(z)=g(tz)\). For each letter \(i\), define the operator \(\mathcal J_i\) by requiring \(\mathcal J_i(g)\) to have zero constant term and \[(\sigma-1)\mathcal J_i(g)=\frac{z}{1-(1+t)^i z}\,g.\] On the coefficient of \(z^r\) for \(r\ge1\), this divides by \(t^r-1\), which is nonzero in every characteristic. Iteration defines a series \(h_w\) for each word \(w\), starting from \(h_\epsilon=1\) for the empty word \(\epsilon\). Section 2 proves that these series are linearly independent. A minimal-relation argument reduces the claim to a pole obstruction: a difference \(\sigma(R)-R\), with \(R\in K(z)\), cannot have just one pole in an infinite shift orbit, whereas the poles \((1+t)^{-i}\) lie in disjoint such orbits. Thus a nonzero polynomial \(f=\sum_w f_wx_w\) gives a nonzero series \(h_f=\sum_w f_wh_w\). Formula size bounds how late the first nonzero coefficient of \(h_f\) can appear. Section 3 finds a row \(u\), a column \(v\), and strictly upper triangular \(m\times m\) matrices \(B_1,\ldots,B_n\) over \(F\), with \(m\le2s\), such that \(f_w=uB_wv\); here \(B_{i_1\cdots i_\ell}=B_{i_1}\cdots B_{i_\ell}\) and \(B_\epsilon=I_m\). The finite sum \(H=\sum_w B_wh_w\) satisfies \(H(0)=I\) and \(\sigma(H)=(P/Q)H\), with \(z\)-degrees at most \(n\) and \(Q(0)=1\). Section 4 proves the reusable bound \[uHv\ne0\quad\Longrightarrow\quad \mathop{\mathrm{ord}}_z(uHv)\le n\binom m2.\] The proof adapts the determinant method for differential systems: a basis of series with distinct leading orders \(c_i\) has a shifted determinant whose leading coefficient is a Vandermonde determinant on \(t^{c_i}\). These elements remain distinct in small characteristic. Rational degree bounds then control the orders of the relevant minors. Truncating in \(z\) now gives matrices over \(\mathbb F_p(t)\) that detect all the required formulas. Section 5 removes \(t\) without choosing a large finite extension. Strict triangularity supplies one denominator clearing every evaluated word, together with a polynomial bound on the remaining \(t\)-degree. Reduction modulo a sufficiently large power \(t^E\) preserves nonvanishing. Finally, representing multiplication on \(\mathbb F_p[t]/(t^E)\) by matrices over \(\mathbb F_p\) gives the output tuple. The shift order bound is useful independently of the formula application; the last step is a general way to retain bounded-degree rational data in ordinary matrices over the base field. Independent word series from a multiplicative shiftWe first encode free polynomials by formal power series without losing any nonzero polynomial. No size bound is needed in this section. Fix a field \(F\), let \(t\) be an indeterminate over \(F\), and put \(K=F(t)\). For a second formal variable \(z\), define \[\sigma:K((z))\longrightarrow K((z)),\qquad \sigma(g)(z)=g(tz).\] This automorphism fixes \(K\) and preserves both \(K[[z]]\) and \(K(z)\), where rational functions are embedded by Laurent expansion at \(z=0\). Since \(t^r\ne1\) for every nonzero integer \(r\), coefficient comparison gives \[ K((z))^\sigma=K. \tag{1}\] In particular, this remains true when the characteristic divides \(r\). For \(1\le i\le n\), set \[ a_i=(1+t)^i,\qquad b_i(z)=\frac{z}{1-a_i z}. \tag{2}\] Given \(g\in K[[z]]\), define \(\mathcal J_i(g)\) to be the unique series \(h\in zK[[z]]\) satisfying \[ (\sigma-1)h=b_i g. \tag{3}\] Indeed, the right side has zero constant coefficient, and the coefficient of \(z^r\) in \(h\), for \(r\ge1\), is obtained by dividing the corresponding coefficient of \(b_i g\) by \(t^r-1\). Thus \(\mathcal J_i\) is \(K\)-linear and \[ \mathcal J_i\bigl(z^jK[[z]]\bigr)\subseteq z^{j+1}K[[z]]\qquad(j\ge0). \tag{4}\] The role of the transcendental parameter is already visible: all these divisions are valid in every characteristic. Let \(\{1,\ldots,n\}^*\) denote the set of finite words, including the empty word \(\epsilon\). For \(w=i_1\cdots i_\ell\), write \(x_w=x_{i_1}\cdots x_{i_\ell}\), with \(x_\epsilon=1\). Define \[ h_\epsilon=1,\qquad h_{iw}=\mathcal J_i(h_w), \tag{5}\] where \(iw\) means that \(i\) is prefixed to \(w\). Our objective is to prove that these series are linearly independent, even with rational-function coefficients. The relevant obstruction is that a rational difference cannot have an isolated pole in an infinite shift orbit. Such pole-orbit obstructions are central to rational \(q\)-summation; see Chen and Singer (Chen and Singer 2012, sec. 2.3) for a systematic residue criterion in characteristic zero. The elementary form needed here has the following proof in arbitrary characteristic. Lemma 2 (A rational difference obstruction). With \(K\), \(\sigma\), and \(b_1,\ldots,b_n\) as above, suppose \[\sum_{i=1}^n c_i b_i=\sigma(R)-R, \qquad c_i\in K,\quad R\in K(z).\] Then \(c_1=\cdots=c_n=0\). Proof. The unique finite pole of \(b_i\) is \(\alpha_i=(1+t)^{-i}\), a nonzero element of \(K\). The orbits \[\mathcal O_i=\{t^j\alpha_i:j\in\mathbb Z\}\] are infinite and pairwise disjoint. To check the latter assertion, an orbit intersection would give \((1+t)^{i-i'}=t^a\) for an integer \(a\). The order at \(t=0\) forces \(a=0\), and the order at \(t=-1\) then forces \(i=i'\). Orders of rational functions are integers; this reasoning is unchanged when the characteristic divides \(i-i'\). Suppose \(c_i\ne0\). The left side has exactly one pole on \(\mathcal O_i\). The rational function \(R\) has only finitely many poles there. If it has none, neither does \(\sigma(R)-R\). Otherwise let \(j_-\) and \(j_+\) be the smallest and largest indices of its poles in this orbit. Substitution \(z\mapsto tz\) moves each pole from index \(j\) to index \(j-1\). At index \(j_--1\), only \(\sigma(R)\) has a pole; at index \(j_+\), only \(-R\) has one. These are two distinct poles of \(\sigma(R)-R\), a contradiction. The argument does not depend on the pole orders or on cancellation at interior indices; Figure 1 illustrates precisely this point. ◻ The proof below is a shift analogue of the minimal-relation argument for differential word series in Deneufchâtel, Duchamp, Hoang Ngoc Minh, and Solomon (Deneufchâtel et al. 2011, Theorem 1). We include the argument: \(\sigma-1\) is not a derivation, and the field here may have positive characteristic. Proposition 3 (Word-series independence). For every field \(F\) and every positive integer \(n\), the series \((h_w)_{w\in\{1,\ldots,n\}^*}\) in (5) are linearly independent over \(F(t)(z)\). Proof. Suppose there is a nontrivial finite relation \[ \sum_w R_w h_w=0,\qquad R_w\in K(z). \tag{6}\] Choose one with smallest maximum occurring word length \(\ell\), then with fewest nonzero coefficients at length \(\ell\). Since \(h_\epsilon=1\), we have \(\ell\ge1\). Divide by one nonzero length-\(\ell\) coefficient to make it \(1\). Apply \(\sigma\) to (6) and subtract the original relation. By (3), the coefficient of \(h_w\) in the resulting relation is \[ \widetilde R_w=\sigma(R_w)-R_w+ \sum_{i=1}^n b_i\sigma(R_{iw}), \tag{7}\] where missing coefficients are zero. This relation has no words longer than \(\ell\), introduces no new length-\(\ell\) coefficient, and removes the normalized coefficient. If any \(\widetilde R_w\) were nonzero, one of the two minimality conditions would fail. Therefore all of them vanish. For \(|w|=\ell\), Equation (7) gives \(\sigma(R_w)=R_w\), so (1) implies \(R_w\in K\). For each \(|w|=\ell-1\), it then gives \[\sum_{i=1}^n b_i R_{iw}=\sigma(-R_w)-(-R_w).\] Lemma 2 forces every \(R_{iw}\) to vanish. Every word of length \(\ell\) occurs in exactly one such family, contradicting the choice of the original relation. ◻ For a free polynomial \(f=\sum_w f_w x_w\) over \(F\), put \[ h_f=\sum_w f_w h_w=f(\mathcal J_1,\ldots,\mathcal J_n)1. \tag{8}\] The rightmost operator acts first, so the second equality follows from the prefix convention in (5). Proposition 3 shows that \(f\ne0\) implies \(h_f\ne0\). To turn this encoding into finite matrices, we must now bound how far into \(h_f\) its first nonzero coefficient can occur. Formula size supplies that bound through a finite matrix system. From formulas to finite shift systemsThe word series of Section 2 send every nonzero polynomial \(f=\sum_w f_w x_w\) to a nonzero series \(h_f=\sum_w f_w h_w\). To bound the order of this series in terms of formula size, we first represent the word coefficients \(f_w\) by matrices of bounded dimension. We use the standard passage from formulas to path programs (Raz and Shpilka 2005, sec. 2.1, Lemma 2, Step 1) and the resulting coefficient representation (OpenAI 2026, Lemma 3.1). We give the construction over an arbitrary field, keeping track of scalar edges and the order of multiplication. An acyclic scalar/variable-labelled path program over a field \(F\) is a finite directed acyclic graph, with parallel edges allowed, whose edges are labelled by scalars in \(F\) or by variables \(x_1,\ldots,x_n\). It has designated source and sink vertices; these vertices may coincide and need not be first and last in a topological ordering. The value of a directed path is the product of its edge labels in traversal order. The value of the program is the sum of these products over all paths from the designated source to the designated sink. When the two vertices coincide, the empty path contributes \(1\). Acyclicity makes this a finite sum in \(F\langle x_1,\ldots,x_n\rangle\). Lemma 4 (Coefficient representation of a path program). Let \(F\) be a field, and let a path program with \(m\geq 1\) vertices have value \(f=\sum_w f_w x_w\). There are a row \(u\in F^{1\times m}\), a column \(v\in F^{m\times 1}\), and strictly upper triangular matrices \(B_1,\ldots,B_n\in\mathop{\mathrm{Mat}}_m(F)\) such that \[ f_w=uB_wv, \qquad B_{i_1\cdots i_\ell}=B_{i_1}\cdots B_{i_\ell}, \qquad B_\epsilon=I_m. \tag{9}\] In particular, \(B_w=0\) whenever \(|w|\geq m\). Proof. Number the vertices in a topological order, so every edge goes from a smaller index to a larger one. Matrix rows index starting vertices and columns index ending vertices. Let \((E_0)_{ab}\) be the sum of the scalar labels on edges from \(a\) to \(b\). Let \((X_i)_{ab}\) be the sum of one copy of \(1_F\) for each edge from \(a\) to \(b\) labelled \(x_i\). All these matrices are strictly upper triangular. Consequently \[S=I_m+E_0+\cdots+E_0^{m-1}\] has as its \((a,b)\) entry the sum of the values of all scalar-only paths from \(a\) to \(b\), including the empty path when \(a=b\). Write \(\mathrm{src}\) and \(\mathrm{snk}\) for the designated vertices, and let \(e_a\) denote the \(a\)th coordinate column. A path whose sequence of variable labels is \(i_1\cdots i_\ell\) decomposes uniquely into scalar-only paths separated by these variable edges. Since scalar labels are central, summing over these decompositions gives \[ f_{i_1\cdots i_\ell} =e_{\mathrm{src}}^{\mathsf T} S X_{i_1}S\cdots X_{i_\ell}S e_{\mathrm{snk}}. \tag{10}\] For the empty word the right-hand side is \(e_{\mathrm{src}}^{\mathsf T}S e_{\mathrm{snk}}\). Taking \[u=e_{\mathrm{src}}^{\mathsf T}S, \qquad B_i=X_iS, \qquad v=e_{\mathrm{snk}}\] proves (9). The product of a strictly upper triangular matrix with an upper triangular matrix is strictly upper triangular, so each \(B_i\) has this property. Any product of \(m\) such \(m\times m\) matrices is zero. ◻ Lemma 5 (Formula representation). Let \(F\) be a field, and let \(f\) be computed by a noncommutative formula of size at most \(s\), counting all vertices including scalar leaves. Then \(f\) is the value of an acyclic scalar/variable-labelled path program with at most \(2s\) vertices. Its coefficients therefore have a representation (9) with \(m\leq 2s\). Proof. Associate two vertices, an entrance and an exit, to each formula vertex. For a leaf, join its entrance to its exit by one edge labelled by the leaf’s variable or scalar. At a sum gate, join its entrance to both child entrances and both child exits to its exit, using edges labelled \(1\). At an ordered product gate, use edges labelled \(1\) from its entrance to the first child entrance, from the first child exit to the second child entrance, and from the second child exit to its exit. The child subtrees have disjoint vertices because the computation is a formula. Recursively order the vertices of each subtree with its entrance first, its first child subtree before its second, and its exit last. Every edge points forward in this ordering, so the graph is acyclic. A path through a sum gate chooses one of its two child programs; a path through a product gate traverses the two child programs in their prescribed order. Induction on the formula therefore shows that the program from the root entrance to the root exit has value \(f\). There are two program vertices per formula vertex, including each scalar leaf. The claimed coefficient representation now follows from Lemma 4. ◻ We now return to a field \(F\) of characteristic \(p\) and to \(K=F(t)\). We combine the word series with the coefficient matrices in (9) to form one invertible matrix. Strict upper triangularity makes the following sum finite. Proposition 6 (Shift system for a coefficient representation). Let \(F\) be a field of characteristic \(p\) and put \(K=F(t)\). Suppose \(u\in F^{1\times m}\), \(v\in F^{m\times 1}\), and strictly upper triangular \(B_1,\ldots,B_n\in\mathop{\mathrm{Mat}}_m(F)\) represent the coefficients of a polynomial \(f\) as in (9). With the word series from Section 2, define \[ H(z)=\sum_w B_w h_w(z). \tag{11}\] Then \(H\in\mathop{\mathrm{GL}}_m(K[[z]])\), \(H(0)=I_m\), and \[ \begin{gathered} h_f=uHv,\qquad \sigma(H)=A(z)H,\\ A(z)=I_m+\sum_{i=1}^n b_i(z)B_i=\frac{P(z)}{Q(z)}, \end{gathered} \tag{12}\] where \[ \begin{gathered} Q(z)=\prod_{i=1}^n(1-a_i z),\qquad Q(0)=1,\\ \deg_z Q\leq n,\qquad \deg_z P_{ab}\leq n \quad(1\leq a,b\leq m). \end{gathered} \tag{13}\] Here \(P\in\mathop{\mathrm{Mat}}_m(K[z])\), and \(a_i=(1+t)^i\) and \(b_i=z/(1-a_i z)\) are as in Section 2. If \(f\neq 0\), then \(uHv\neq 0\). Proof. Only words of length less than \(m\) contribute to (11), so the sum is finite. The empty word contributes \(I_m\), whereas every nonempty word series has zero constant term. Hence \(H(0)=I_m\) and \(H\) is invertible over \(K[[z]]\). The coefficient representation gives \[uHv=\sum_w (uB_wv)h_w=\sum_w f_w h_w=h_f.\] In particular, Proposition 3 gives \(uHv\neq 0\) when \(f\neq 0\). The shift fixes every \(B_i\), and the defining recursion for the word series gives \(\sigma(h_{iw})-h_{iw}=b_i h_w\). Splitting the nonempty words according to their first letter, we obtain \[\sigma(H)-H =\sum_{i=1}^n\sum_w B_iB_w b_i h_w =\left(\sum_{i=1}^n b_i B_i\right)H.\] This proves the shift equation with the displayed order of matrix factors. Finally, multiplying \(A\) by \(Q\) gives \[P(z)=Q(z)I_m+ \sum_{i=1}^n z\prod_{j\neq i}(1-a_j z)B_i.\] Each summand has degree at most \(n\), proving (13). ◻ For a size-\(s\) formula, Lemma 5 makes the system dimension at most \(2s\). The next section bounds the order of every nonzero scalar component \(uHv\) using this dimension and the degree bound in (13). An order bound for multiplicative-shift systemsA bound on the order of a nonzero scalar series produced by the formula system will make a finite truncation possible. We prove such a bound for a general rational system under a multiplicative shift. We adapt the derivative-row and minor comparison underlying Moura’s multiplicity estimate (Moura 2003), in the formal presentation of (OpenAI 2026, sec. 4, Theorem 4.2), to successive shifts. The distinct-order basis and leading-term calculation parallel the Wronskian argument of Bostan and Dumas (Bostan and Dumas 2010, Lemmas 1–3). Here the leading determinant uses distinct powers of the shift parameter, and remains nonzero in every characteristic. For a nonzero series \(h\in K[[z]]\), write \(\mathop{\mathrm{ord}}_z h\) for its least exponent with nonzero coefficient, and put \(\mathop{\mathrm{ord}}_z 0=+\infty\). Theorem 7 (Order bound). Let \(K\) be a field, let \(\tau\in K^\times\) have infinite multiplicative order, and let \(\sigma\) be the automorphism of \(K((z))\) that fixes \(K\) and sends \(z\) to \(\tau z\). Let \(m\geq 1\) and \(\nu\geq 0\) be integers. Suppose that \(H\in\mathop{\mathrm{GL}}_m(K[[z]])\) satisfies \[ \sigma(H)=A H,\qquad A=\frac{P}{Q}, \tag{14}\] where \(P\in\mathop{\mathrm{Mat}}_m(K[z])\), \(Q\in K[z]\), \(Q(0)\neq 0\), and \(Q\) and every entry of \(P\) have degree at most \(\nu\). For every constant row \(u\in K^{1\times m}\) and constant column \(v\in K^{m\times 1}\), \[ uHv\neq 0 \quad\Longrightarrow\quad \mathop{\mathrm{ord}}_z(uHv)\leq \nu\binom{m}{2}. \tag{15}\] Proof. Set \(g=uH\) and suppose that \(y=gv\neq 0\). Let \(V\subseteq K[[z]]\) be the \(K\)-linear span of the \(m\) components of \(g\), and put \(k=\dim_K V\). Then \(1\leq k\leq m\) and \(y\in V\). We first express the orders occurring in \(V\) through a determinant, and then bound that determinant using the rational system. There is a basis \(w_1,\ldots,w_k\) of \(V\) whose orders satisfy \[0\leq c_1<c_2<\cdots<c_k, \qquad c_i=\mathop{\mathrm{ord}}_z w_i.\] To construct it, choose a nonzero element of smallest order in \(V\). The coefficient functional at that order is nonzero, so its kernel has codimension one and every nonzero element of the kernel has larger order. Repeat inside this kernel, and continue until the dimension is zero. In any nonzero linear combination of the resulting basis, the first basis element with a nonzero coefficient supplies the unique lowest-order term. In particular, \[ \mathop{\mathrm{ord}}_z y\leq c_k. \tag{16}\] Consider the determinant of successive shifts, or Casoratian, \[C(w_1,\ldots,w_k) =\det\bigl(\sigma^j(w_i)\bigr)_{ \substack{0\leq j<k\\1\leq i\leq k}}.\] Write the leading term of \(w_i\) as \(\lambda_i z^{c_i}\), with \(\lambda_i\in K^\times\). After factoring \(z^{c_i}\) from column \(i\), the constant term of the determinant that remains is \[\left(\prod_{i=1}^k\lambda_i\right) \det\bigl((\tau^{c_i})^j\bigr)_{ \substack{0\leq j<k\\1\leq i\leq k}} =\left(\prod_{i=1}^k\lambda_i\right) \prod_{1\leq i<h\leq k}(\tau^{c_h}-\tau^{c_i}).\] This expression is nonzero because \(\tau\) has infinite multiplicative order. Therefore \[ \mathop{\mathrm{ord}}_z C(w_1,\ldots,w_k)=\sum_{i=1}^k c_i. \tag{17}\] Every other \(K\)-basis of \(V\) gives a Casoratian of the same order: its matrix of successive shifts is obtained by an invertible change of columns over \(K\), which is fixed by \(\sigma\). To bound this order, we compare the shifted components of \(g\) with rational rows obtained from the system. Define rational rows \[ R_0=u,\qquad R_{j+1}=\sigma(R_j)A\quad(j\geq 0). \tag{18}\] Equation (14) gives \(\sigma^j(g)=R_jH\) by induction. Each row has a presentation \[ R_j=\frac{N_j}{D_j},\qquad D_j(z)=\prod_{e=0}^{j-1}Q(\tau^e z), \tag{19}\] where \(N_j\) is a polynomial row whose entries have degree at most \(j\nu\); the empty product is \(D_0=1\). Indeed, take \(N_0=u\) and then \(N_{j+1}=\sigma(N_j)P\). Substitution by \(\tau z\) preserves polynomial degree, which proves the degree bound. Moreover, \(D_j(0)=Q(0)^j\neq 0\), so every entry of every \(R_j\) belongs to \(K[[z]]\). Let \(M\) be the \(k\times m\) matrix with rows \(R_0,\ldots,R_{k-1}\). Its product \(MH\) has rows \(g,\sigma(g),\ldots,\sigma^{k-1}(g)\). For a \(k\times m\) matrix \(X\) and a \(k\)-element subset \(J\subseteq\{1,\ldots,m\}\), let \(X_J\) denote the square matrix formed by the columns indexed by \(J\), in increasing order. A determinant \(\det((MH)_J)\) is the Casoratian of the corresponding components of \(g\). It vanishes when those components are \(K\)-linearly dependent. Otherwise they form a basis of \(V\), and (17) shows that its order is \(\sum_i c_i\). Some \(k\) components form a basis of \(V\), so at least one of these determinants is nonzero. Consequently, \[ \min_J\mathop{\mathrm{ord}}_z\det((MH)_J)=\sum_{i=1}^k c_i. \tag{20}\] Right multiplication by \(H\) preserves the minimum order of the \(k\times k\) minors. To see this directly, Cauchy–Binet expresses every minor of \(MH\) as a \(K[[z]]\)-linear combination of minors of \(M\). The minimum order therefore cannot decrease. Applying the same argument to \(M=(MH)H^{-1}\) proves the reverse inequality, since \(H^{-1}\) also has power series entries. Thus \[ \min_J\mathop{\mathrm{ord}}_z\det(M_J) =\min_J\mathop{\mathrm{ord}}_z\det((MH)_J). \tag{21}\] In particular, \(M\) has a nonzero \(k\times k\) minor. By (19), any such nonzero minor has denominator \(\prod_{j=0}^{k-1}D_j\), a unit at zero, and a nonzero polynomial numerator of degree at most \[\sum_{j=0}^{k-1}j\nu=\nu\binom{k}{2}.\] Its order is at most this degree. Combining (16), (20), and (21) gives \[\mathop{\mathrm{ord}}_z y \leq c_k \leq\sum_{i=1}^k c_i \leq\nu\binom{k}{2} \leq\nu\binom{m}{2},\] as claimed. ◻ The characteristic plays no role in the Vandermonde calculation: distinct orders \(c_i\) yield distinct powers \(\tau^{c_i}\). In the application, \(K=F(t)\) and \(\tau=t\), so this condition holds for every coefficient field \(F\). The other essential local condition is that \(H\) be invertible over \(K[[z]]\), as required to use both \(H\) and \(H^{-1}\) in (21). Truncation and construction over the prime fieldThe order bound gives a finite amount of information in the variable \(z\) that detects every nonzero formula. We first express the operators on this finite space as matrices over \(\mathbb F_p(t)\). We then retain bounded Taylor expansions in \(t\) and represent multiplication by these truncated polynomials as matrices over \(\mathbb F_p\). A common denominator bound ensures that the second truncation preserves the nonvanishing established by the first. Truncating the word operatorsFix a prime \(p\) and integers \(n,s\geq 1\), and set \[ N=1+n\binom{2s}{2}. \tag{22}\] Let \(F\) be any field of characteristic \(p\) and put \(K=F(t)\), with \(t\) an indeterminate over \(F\). Each operator \(\mathcal J_i\) raises \(z\)-order by at least one, so it induces an operator on \(K[[z]]/(z^N)\). In the ordered basis \(1,z,\ldots,z^{N-1}\), with vectors represented by coefficient columns, its matrix is \[ (U_i)_{r,q}= \begin{cases} \displaystyle\frac{(1+t)^{i(r-q-1)}}{t^r-1},&0\leq q<r<N,\\[6pt] 0,&0\leq r\leq q<N, \end{cases} \qquad 1\leq i\leq n. \tag{23}\] Indeed, the coefficient of \(z^r\) in \(b_i(z)z^q=z^{q+1}/(1-(1+t)^i z)\) is \((1+t)^{i(r-q-1)}\) for \(r>q\), and inverting \(\sigma-1\) divides that coefficient by \(t^r-1\). In particular, \(U_i\in\mathop{\mathrm{Mat}}_N(\mathbb F_p(t))\), independently of the choice of \(F\). Let \(e_0\) be the coefficient column of the constant series \(1\). The recursion \(h_{iw}=\mathcal J_i(h_w)\) gives \[ f(U_1,\ldots,U_n)e_0 =\text{the coefficient column of }h_f\bmod z^N \tag{24}\] for every \(f\in F\langle x_1,\ldots,x_n\rangle\). The order of the operators agrees with the order of matrix multiplication: the rightmost operator of a word acts first. Suppose that \(f\) is nonzero and has a formula of size at most \(s\). Word-series independence gives \(h_f\ne0\). Section 3 represents this series as \(uHv\) in a system of dimension \(m\leq2s\) with numerator and denominator degrees at most \(n\). Theorem 7 therefore gives \[\mathop{\mathrm{ord}}_z h_f\leq n\binom m2\leq n\binom{2s}{2}=N-1.\] Thus (24) is nonzero, and in particular \[ f(U_1,\ldots,U_n)\ne0. \tag{25}\] The tuple \(U\) already has the required simultaneous detection property, but its entries are rational functions. We next replace these functions by finite matrices while preserving this property. Retaining finitely many coefficients of \(t\)All denominators in (23) are nonzero at \(t=0\). Moreover, one denominator clears every polynomial evaluated at \(U\). Define \[ D(t)=\prod_{r=1}^{N-1}(t^r-1), \qquad E=1+\binom N2+n(N-1). \tag{26}\] For every \(f\in F\langle x_1,\ldots,x_n\rangle\), each entry of \(Df(U)\) is a polynomial in \(F[t]\) of degree less than \(E\). To verify this, consider a nonzero summand in the \((r,q)\) entry of a word product \(U_{i_1}\cdots U_{i_k}\). Since the matrices are strictly lower triangular, the summand follows a chain \[q=j_0<j_1<\cdots<j_k=r<N.\] Its denominator is \(\prod_{a=1}^k(t^{j_a}-1)\), which divides \(D\) because the indices \(j_a\) are distinct. Its numerator is a power of \(1+t\) whose exponent is \[\sum_{a=1}^k i_{k-a+1}(j_a-j_{a-1}-1) \leq n(r-q-k)\leq n(N-1).\] Multiplying by \(D\) therefore gives degree at most \(\deg D+n(N-1)=E-1\). For the empty word the assertion follows from \(\deg D=\binom N2\); words of length at least \(N\) give zero. Taking \(F\)-linear combinations proves the assertion for \(f\). This reasoning does not require the factors of \(D\) to be relatively prime. We use the following elementary descent statement to turn this degree bound into matrices over the coefficient field. For a field \(k\), write \[k[t]_{(t)}= \left\{\frac{a(t)}{b(t)}:a,b\in k[t],\ b(0)\ne0\right\}.\] Reduction modulo \(t^E\) defines a \(k\)-algebra map from this ring to \(k[t]/(t^E)\), since a polynomial with nonzero constant term is a unit in the quotient. Lemma 8 (Descent by a finite coefficient ring). Let \(k\) be a field, let \(n,N,E\geq1\), and let \(V_1,\ldots,V_n\in\mathop{\mathrm{Mat}}_N(k[t]_{(t)})\). Reduce their entries modulo \(t^E\), and replace each resulting entry by its matrix of multiplication on \(k[t]/(t^E)\) in the basis \(1,t,\ldots,t^{E-1}\). This produces matrices \(T_1,\ldots,T_n\in\mathop{\mathrm{Mat}}_{NE}(k)\). Let \(F/k\) be any field extension and \(f\in F\langle x_1,\ldots,x_n\rangle\). Suppose that a polynomial \(D\in F[t]\) with \(D(0)\ne0\) satisfies \[Df(V)\in\mathop{\mathrm{Mat}}_N(F[t]), \qquad \deg_t\bigl((Df(V))_{a,b}\bigr)<E \quad\text{whenever }(Df(V))_{a,b}\ne0.\] If \(f(V)\ne0\) over \(F(t)\), then \(f(T)\ne0\) over \(F\). Proof. Put \(R_F=F[t]/(t^E)\) and let \(\pi_F:F[t]_{(t)}\longrightarrow R_F\) be reduction. Since \(f(V)\ne0\), some entry of \(Df(V)\) is a nonzero polynomial of degree less than \(E\). Its reduction is nonzero. Hence \[\pi_F(D)\,f(\pi_F(V))=\pi_F(Df(V))\ne0,\] and therefore \(f(\pi_F(V))\ne0\). Multiplication on \(R_F\) gives a unital \(F\)-algebra map \[\rho_F:R_F\longrightarrow\mathop{\mathrm{Mat}}_E(F).\] It is injective: if multiplication by \(a\in R_F\) is zero, applying it to \(1\) gives \(a=0\). Replacing entries by their multiplication matrices thus gives an injective unital \(F\)-algebra map \[\rho_F^{(N)}:\mathop{\mathrm{Mat}}_N(R_F)\longrightarrow\mathop{\mathrm{Mat}}_{NE}(F).\] The maps \(\pi_F\) and \(\rho_F\) extend the corresponding maps over \(k\). Consequently \(\rho_F^{(N)}(\pi_F(V_i))\) is the matrix \(T_i\) viewed over \(F\), and \[f(T)=\rho_F^{(N)}\bigl(f(\pi_F(V))\bigr)\ne0.\] Unital \(F\)-linearity also shows that every scalar \(a\in F\) acts as \(aI_{NE}\) throughout this evaluation. ◻ Apply the construction in Lemma 8 with \(k=\mathbb F_p\) and \(V_i=U_i\), using the parameters in (22) and (26). We denote the resulting tuple by \[ T_{p,n,s}=(T_1,\ldots,T_n),\qquad d=NE. \tag{27}\] Only multiplication and reduction of functions regular at \(t=0\) enter this step. The shift automorphism is used before truncation; no shift on \(\mathbb F_p[t]/(t^E)\) is needed. The uniform algorithm and the main theoremProof of Theorem 1. We first verify the simultaneous guarantee. Fix any field \(F\) of characteristic \(p\) and any nonzero polynomial \(f\) over \(F\) computed by a formula of size at most \(s\). Equation (25) gives \(f(U)\ne0\) over \(F(t)\). The degree bound following (26) verifies the hypotheses of Lemma 8, which gives \(f(T)\ne0\). The tuple in (27) depends only on \(p,n,s\). Thus this argument applies to all choices of \(F\) and all their scalar coefficients with the same prime-field output. Here is a finite deterministic algorithm for producing that output. Compute the integers \(N,E,d\). Represent elements of \(\mathbb F_p[t]/(t^E)\) by length-\(E\) coefficient arrays, keeping each coefficient as its residue in \(\{0,\ldots,p-1\}\). For \(0\leq q<r<N\), the required denominator inverse is explicitly \[ (t^r-1)^{-1} =-\sum_{j=0}^{\lfloor(E-1)/r\rfloor}t^{rj} \pmod {t^E}. \tag{28}\] Indeed, its product with \(t^r-1\) is \(1-t^{r(\lfloor(E-1)/r\rfloor+1)}\), which is \(1\) in the quotient. Form \((1+t)^{i(r-q-1)}\) by repeated multiplication by \(1+t\), reducing modulo \(t^E\) and modulo \(p\) after every operation, and multiply it by (28). This computes the reduction of every entry in (23); the remaining entries are zero. If such an entry is \(c_0+c_1t+\cdots+c_{E-1}t^{E-1}\), its multiplication block has entry \(c_{a-b}\) in row \(a\), column \(b\) when \(0\leq b\leq a<E\), and zero when \(a<b\). Thus each block is obtained by shifts and truncations of one coefficient array. Output \(d\) and the matrices \(T_i\) densely, with these blocks in the positions prescribed by \(U_i\) and with every entry written as its ordinary binary residue. We record the cost in the Turing model. Put \(L=\lceil\log_2p\rceil\) and \(B=n+s+L+1\). The parameter formulas give \[N=O(ns^2),\qquad E=O(n^2s^4),\qquad d=O(n^3s^6),\] and in particular \(N=O(B^3)\), \(E=O(B^6)\), and \(d=O(B^9)\). All exponents used above are at most \(n(N-1)\). With schoolbook polynomial arithmetic, at most \[O\bigl((1+nN)E^2\bigr)\] residue operations suffice per entry of the \(N\)-by-\(N\) matrices, including the construction of its multiplication block. For all \(nN^2\) entries this is \(O(B^{23})\) residue operations. Elementary binary arithmetic and division with remainder implement each residue operation in a number of bit operations polynomial in \(L+1\). The dense output has bit length \[O\bigl(\log(d+1)+nd^2(L+1)\bigr)=O(B^{20}),\] including entry separators and dimensions. The algorithm stores only polynomially many bits: coefficient arrays, matrices, and loop counters all have polynomial size in \(B\). On an ordinary Turing machine, even locating every array entry by a scan of this storage adds only a polynomial factor. Integer parameter calculations and input processing also have polynomial bit cost. These explicit finite loops therefore give absolute constants \(C,k\) bounding both running time and output length by \(CB^k\), as claimed. ◻ The same construction applies to the acyclic scalar/variable-labelled path programs of Section 3. Their significance here is that their state bound is the number of graph vertices, even when different paths share subpaths. Corollary 9. There is a deterministic algorithm which, on input \((\operatorname{bin}(p),1^n,1^m)\) with \(p\) prime and \(n,m\geq1\), outputs a tuple in \(\mathop{\mathrm{Mat}}_d(\mathbb F_p)^n\) detecting every nonzero polynomial computed by an acyclic scalar/variable-labelled path program with at most \(m\) vertices, simultaneously over every field of characteristic \(p\). One may take \[N=1+n\binom m2,\qquad E=1+\binom N2+n(N-1),\qquad d=NE=O(n^3m^6).\] The running time and dense output length are polynomial in \(n+m+\lceil\log_2p\rceil\). Proof. Section 3 gives the same strictly upper triangular coefficient representation using at most \(m\) states. Thus Theorem 7 yields \(\mathop{\mathrm{ord}}_z h_f\leq n\binom m2\) for every nonzero path polynomial. With this value of \(N\), define \(U_i\) by (23) and apply Lemma 8 with \(k=\mathbb F_p\) and \(E\) as displayed above. The same degree bound and bit analysis apply. When \(m=1\), every path polynomial is constant and \(N=E=d=1\); the output consists of zero \(1\)-by-\(1\) matrices, which detect every nonzero constant. ◻
Bogdanov, Andrej, and Hoeteck Wee. 2005. “More on Noncommutative Polynomial Identity Testing.” 20th Annual IEEE Conference on Computational Complexity, 92–99. https://doi.org/10.1109/CCC.2005.13.
Bostan, Alin, and Philippe Dumas. 2010. “Wronskians and Linear Independence.” American Mathematical Monthly 117 (8): 722–27. https://doi.org/10.4169/000298910X515785.
Chen, Shaoshi, and Michael F. Singer. 2012. “Residues and Telescopers for Bivariate Rational Functions.” Advances in Applied Mathematics 49 (2): 111–33. https://doi.org/10.1016/j.aam.2012.04.003.
Deneufchâtel, Matthieu, Gérard H. E. Duchamp, Vincel Hoang Ngoc Minh, and Allan I. Solomon. 2011. “Independence of Hyperlogarithms over Function Fields via Algebraic Combinatorics.” In Algebraic Informatics, edited by Franz Winkler, vol. 6742. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-21493-6_8.
Forbes, Michael A., and Amir Shpilka. 2013. “Quasipolynomial-Time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.” 54th Annual IEEE Symposium on Foundations of Computer Science, 243–52. https://doi.org/10.1109/FOCS.2013.34.
Lakhani, Foram, and Partha Mukhopadhyay. 2026. Hitting Point for Sparse Noncommutative Polynomials. Nos. TR26-120. Electronic Colloquium on Computational Complexity. https://eccc.weizmann.ac.il/report/2026/120/revision/2/download.
Moura, Claire. 2003. “Bounds for the Vanishing Order for Solutions of a Linear Differential System.” Journal of Dynamical and Control Systems 9 (1): 73–88. https://doi.org/10.1023/A:1022155217548.
Nisan, Noam. 1991. “Lower Bounds for Non-Commutative Computation.” Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, 410–18. https://doi.org/10.1145/103418.103462.
OpenAI. 2026. One Rational Matrix Hitting Point for Noncommutative Formulas. OpenAI Math Release preprint OAI:One-Rational-Matrix-Hitting-Point-for-Noncommutative-Formulas-September-24-2026.
Raz, Ran, and Amir Shpilka. 2005. “Deterministic Polynomial Identity Testing in Non-Commutative Models.” Computational Complexity 14 (1): 1–19. https://doi.org/10.1007/s00037-005-0188-8.
|
| ||||||||
|