One Rational Matrix Hitting Point for Noncommutative Formulas

1 Introduction

Polynomial identity testing asks whether an arithmetic expression computes the zero polynomial. We study this question for noncommuting variables when the expression is accessible through matrix evaluations. The aim is to choose the evaluation matrices before seeing the expression or any of its coefficients.

Let F\langle x_1,\ldots,x_n\rangle be the free associative polynomial algebra over a field F. A noncommutative formula is a rooted tree whose leaves are variables or scalars in F, and whose internal gates have two inputs and are labelled + or \times. The two inputs to each multiplication gate are ordered. Its size counts all gates, including the leaves. Write \mathsf{Form}_{n,s}(F) for the polynomials computed by formulas of size at most s in n variables.

For a tuple \mathbf T=(T_1,\ldots,T_n)\in\Mat_d(F)^n, the value f(\mathbf T) is the usual ordered matrix evaluation; a scalar a\in F acts as aI_d. A hitting point for a class of polynomials is one tuple on which every nonzero member of the class has nonzero matrix value. More generally, a hitting set allows several tuples and requires a nonzero value on at least one of them.

Thus a single exact matrix-evaluation query decides whether a polynomial promised to lie in \mathsf{Form}_{n,s}(F) is zero. The bit-time statement concerns construction of the rational tuple. Evaluation over an arbitrary field is understood as an exact oracle operation; no encoding or bit-cost assumption on arbitrary elements of F is needed. In particular, the singleton set \{\mathbf T_{n,s}\} gives a positive solution to the polynomial-size rational-matrix hitting-set problem for characteristic-zero formulas.

1.1 Context and scope

An acyclic algebraic branching program is a directed acyclic graph with a designated source and sink, and with affine-linear edge labels over the coefficient field. Its output is the sum of the ordered products of edge labels along source-to-sink paths; here its size is the number of vertices. Formulas admit such path representations of linear size.

Linear algebra has long played a central role in noncommutative complexity. Nisan characterized layered homogeneous algebraic branching-program complexity by ranks of coefficient matrices [13, Theorem 1]. Raz and Shpilka gave deterministic polynomial-time identity tests for noncommutative formulas and algebraic branching programs [15, Theorems 4 and 5]. These algorithms use the internal structure of the input, which is the white-box model. In the black-box model, Bogdanov and Wee gave a randomized matrix-evaluation identity test with one-sided error and running time polynomial in a supplied degree bound and the other input parameters [3, Theorem 4.2]. Forbes and Shpilka constructed deterministic quasipolynomial-size matrix hitting sets for noncommutative algebraic branching programs over sufficiently large fields [7, Corollary 4.7], and hence for formulas. Their field-size condition is automatic in characteristic zero.

Arvind, Chatterjee and Mukhopadhyay obtained quasipolynomial black-box tests over \Q for rational formulas of inversion height two [1, Theorem 1.1], and subsequently for unrestricted noncommutative rational formulas [2, Theorem 2 and Corollary 3]. Such formulas may have inverse gates, and evaluation requires each inverse operand to be invertible. A separate manuscript [14, Theorem 1.1] constructs polynomial-size rational matrix hitting lists for formulas over \Q with a nonempty rational matrix evaluation domain. Whenever such a formula is nonzero on its domain, the list contains a defined evaluation with invertible value, without a bound on inverse nesting or rational constant heights. Here the single tuple works over every characteristic-zero coefficient field for division-free formulas, whose matrix evaluations are everywhere defined.

Two recent results treat different size restrictions. Lakhani and Mukhopadhyay construct one integer matrix tuple for sparse noncommutative polynomials over every characteristic-zero field, with polynomial construction time and dimension equal to the sparsity bound, without a degree restriction [9, Theorem 2.1 and Remark 2.6]. Formula size can be much smaller than sparsity: the ordered product of k copies of x_1+x_2 has 4k-1 gates and 2^k monomials. Lakhani and Saxena obtain randomized black-box tests for homogeneous noncommutative circuits of constant depth [10, Theorem 1]. Theorem 1.1 is deterministic and imposes no depth or homogeneity restriction on a formula.

The essential quantitative assertion is that matrix dimension, rational entry length, and construction bit time are all polynomial in formula size and the number of variables. For polynomials, a finite matrix hitting set can always be combined into one tuple by taking block-diagonal sums, but the resulting dimension is the sum of the dimensions in the set. The construction here gives the polynomial bounds directly. The formula model is used to obtain a small acyclic path representation. In fact, Proposition 5.1 applies the same construction to the algebraic branching programs defined above, with matrix dimension (n-1)\binom m2+m for m vertices. Thus the path-program consequence also improves the preceding quasipolynomial hitting-set bound in characteristic zero. No bound for arbitrary shared circuits is asserted.

1.2 Proof idea

The obstacle is that a small formula may contain exponentially many words after expansion. We retain these words through a faithful encoding, and bound the necessary truncation using a small representation of the formula. We encode words by iterated integrals in one variable. For a word w=i_1\cdots i_k on \{1,\ldots,n\}, write x_w=x_{i_1}\cdots x_{i_k}, with x_\epsilon=1 for the empty word. Define

where \epsilon is the empty word and integration is interpreted by formal power series at zero. Section 2 proves that the h_w are linearly independent over every characteristic-zero field. Over \C, continuation around the distinct poles yields a triangular spanning argument in a truncated free algebra. A nonzero rational coefficient minor then transfers independence to every field in the theorem. These functions belong to the classical theory of iterated integrals and hyperlogarithms [5]. Their independence is a special case of the stronger differential-field theorem of Deneufchâtel, Duchamp, Hoang Ngoc Minh and Solomon [6, Theorem 1]; we include a direct proof for the particular kernels used here. Its triangular monodromy argument has a two-letter antecedent in Minh, Petitot and van der Hoeven [8, Section 5, Theorem 4].

If f_w denotes the coefficient of x_w in f, put h_f=\sum_w f_wh_w. Section 3 converts a size-s formula into an acyclic path representation with at most 2s states, using the standard formula-to-path construction of Nisan [13, Section 2, Lemma 1], also presented by Raz and Shpilka [15, Section 2.1, Lemma 2, Step 1]. It follows that h_f=uGv for constant vectors u,v and an invertible formal matrix G satisfying

The matrices B_i describe the formula and are used only in the proof.

The quantitative step is a uniform bound on vanishing at zero. Moura’s multiplicity estimate for rational differential systems [11], also stated in [12, Section 2, Theorem 1], bounds the order of a nonzero scalar component uGv of an m-dimensional system G'=(P/q)G, with q(0)\ne0, \deg q=n and \deg P\le n-1, by (n-1)\binom m2+m-1. Section 4 gives a self-contained formal proof of this estimate over the characteristic-zero field in use. It uses the formal Wronskian criterion [4] and the minimum order of the maximal minors of a matrix of derivative rows. This bound is independent of all coefficient values and applies beyond the particular systems arising from formulas.

Finally, Section 5 realizes the integration operators on the space of Taylor coefficients of degrees below 2ns^2. Their matrices have explicit rational entries. Linear independence makes h_f nonzero, and the order bound ensures that this finite truncation retains a nonzero coefficient. That coefficient occurs in the first column of f(\mathbf T_{n,s}).

For ns\ge2, write \pi_d(a) for the column of the first d=2ns^2 Taylor coefficients of a series a, and put e_0=\pi_d(1). Figure 1 summarizes the argument for a nonzero formula polynomial f, separating the generator from the formula-dependent objects used to prove its guarantee.

2 A faithful encoding by iterated integrals

We first encode noncommutative polynomials as power series in one variable. The encoding will preserve every nonzero polynomial; the remaining sections will bound how many Taylor coefficients are needed for a small formula.

Fix an integer n\geq 1 and a field F of characteristic zero. For i\in[n]=\{1,\ldots,n\}, define an F-linear operator on F[[z]] by

Here integration means termwise formal integration with zero constant term: expand (t+i)^{-1}=\sum_{j\geq0}(-1)^j t^j/i^{j+1} first. All denominators are nonzero in F. For a nonzero series a, let \operatorname{ord}_0 a denote the least exponent with nonzero coefficient, and put \operatorname{ord}_0 0=\infty. Then

A word w=i_1\cdots i_b on [n] has length |w|=b; the empty word is denoted by \epsilon. Define the series h_w\in\mathbb Q[[z]] recursively by

We regard these series as elements of F[[z]] through the canonical embedding \mathbb Q\hookrightarrow F. In particular, \operatorname{ord}_0 h_w\geq |w|. Over \mathbb C, they are holomorphic germs at zero: the same recursion uses ordinary integration on any disk of radius less than one. These functions are classical iterated integrals, also called hyperlogarithms; see Chen [5] for the general framework. The following independence statement is a special case of Deneufchâtel et al. [6, Theorem 1]. Their criterion in fact gives independence over F(z): no nonzero F-linear combination of 1/(z+1),\ldots,1/(z+n) is the derivative of a rational function, because such a derivative has zero residue at every pole. We give a direct proof of the constant-coefficient independence needed here. We use a triangular monodromy argument, as in the two-letter case treated by Minh, Petitot and van der Hoeven [8, Section 5, Theorem 4].

For w=i_1\cdots i_b, write x_w=x_{i_1}\cdots x_{i_b} and x_\epsilon=1. Given f=\sum_w f_w x_w\in F\langle x_1,\ldots,x_n\rangle, define

Lemma 2.1 says that the F-linear map f\mapsto h_f is injective. It is not an algebra homomorphism into F[[z]]. Instead, the ordered word x_{i_1}\cdots x_{i_b} acts by the composition \mathcal J_{i_1}\cdots\mathcal J_{i_b}, applied to 1:

For example, when n\ge2, the commutator x_1x_2-x_2x_1 gives

Thus the encoding retains word order, but cancellation can delay the first nonzero coefficient beyond the word length. We next use formula size to bound this delay uniformly.

3 From formulas to differential systems

The word functions from Section 2 turn a nonzero polynomial f=\sum_w f_wx_w into the nonzero series h_f=\sum_w f_wh_w. We now express this series as a scalar output of a differential system whose dimension is at most twice the formula size. This small system will control how late the first nonzero coefficient of h_f can occur. The underlying formula-to-path construction is due to Nisan [13, Section 2, Lemma 1]; see also Raz and Shpilka [15, Section 2.1, Lemma 2, Step 1].

This construction allows arbitrary scalar leaves and constant terms. Its size bound uses the formula tree: the child graphs represent disjoint subtrees, so each gate is counted once. The construction does not enumerate the monomials of f.

We have obtained a nonzero series h_f inside a system of dimension at most 2s, with a denominator of degree n and a regular expansion point at zero. The next section bounds its vanishing order using only these parameters, uniformly in all scalar coefficients of the formula.

4 A bound on the order of vanishing

The preceding representation turns a formula into a scalar component of a rational differential system. A multiplicity estimate of Moura [11] bounds how long such a component can vanish. We give a self-contained formal proof of the required estimate, valid directly over any field of characteristic zero.

For a nonzero series b\in F[[z]], write \operatorname{ord}_0 b for the least exponent with nonzero coefficient, and put \operatorname{ord}_0 0=+\infty. For b_1,\ldots,b_k\in F[[z]], their Wronskian is

The proof of the formal power-series Wronskian criterion by Bostan and Dumas [4, Theorem 2 and Lemmas 1–3] uses a basis with distinct orders and a Vandermonde determinant. We recall that argument, recording also the order of the Wronskian.

The bound below is the specialization of Moura’s estimate to the present degree assumptions. In its complex formulation, recalled in [12, Section 2, Theorem 1], the bound is m-1+\binom m2(\sigma-2), where \sigma is the sum of pole orders of the matrix differential form (P/q)\,dz on the projective line. The finite poles contribute at most n, and infinity contributes at most one. The case P=0 is immediate, since every solution is constant. The argument below proves the stated bound formally and follows the same derivative-row and Wronskian method.

For the formula systems of the preceding section, q(z)=\prod_{i=1}^n(z+i) and G(0)=I, so every hypothesis of Theorem 4.2 holds. Word-series independence makes uGv nonzero for a nonzero formula polynomial; the theorem bounds the number of Taylor coefficients needed to detect it. We now realize these coefficients by finite rational matrices.

5 The rational hitting point

We now turn the integration operators into finite matrices and prove Theorem 1.1. The hitting matrices depend only on the size parameters; the representation of a polynomial is used to prove that they detect it.

5.1 Taylor coefficients as a matrix space

For d\ge1 and a characteristic-zero field F, let

This identifies F[[z]]/(z^d) with the column space having ordered basis 1,z,\ldots,z^{d-1}. The operator \mathcal J_i(a)=\int_0^z a(t)/(t+i)\,dt increases vanishing order, so it induces a linear map on this quotient. Its matrix T_i\in\Mat_d(\Q) is

Indeed,

Every denominator in the nonzero case is nonzero, since r\ge1 and i\ge1. Discarding terms of degree at least d before applying \mathcal J_i does not change any retained coefficient. Thus, for every a\in F[[z]],

Let e_0=\pi_d(1). For a word w=i_1\cdots i_k, repeated application of (14) gives

The rightmost matrix acts first, exactly as in h_w=\mathcal J_{i_1}\cdots\mathcal J_{i_k}(1). For the empty word both products are identities. Consequently, for every f=\sum_w f_wx_w\in F\langle x_1,\ldots,x_n\rangle,

This identity also accounts for constant terms, since a scalar is evaluated as a scalar matrix.

5.2 Detection and construction cost

Suppose first that ns\ge2, and set d=2ns^2 in (13). Let F have characteristic zero, and let f\in\mathsf{Form}_{n,s}(F) be nonzero. By Lemma 2.1, its series h_f is nonzero. Proposition 3.2 represents this series as uGv in a system of dimension m\le2s satisfying the hypotheses of Theorem 4.2. Hence

The last inequality follows from

Therefore \pi_d(h_f)\ne0. Equation (15) supplies a nonzero first column of f(T_1,\ldots,T_n), proving detection.

When n=s=1, a formula of size at most one is a single scalar or variable leaf. The one-by-one tuple T_1=[1] detects every nonzero polynomial in this class. This gives dimension one in the remaining case.

For completeness, we give the bit cost of constructing the tuple. With d=2ns^2, put

Every nonzero entry in (13) has numerator 1 or -1 and positive denominator r i^{r-q}, of bit length at most B. These fractions are already in lowest terms. For each i, precompute i,i^2,\ldots,i^{d-1} by repeated multiplication, then form each denominator by multiplying one of these powers by r. There are O(nd^2) such integer operations on O(B)-bit integers. Schoolbook multiplication gives total bit cost O(nd^2B^2), with output length O(nd^2B). Both bounds are polynomial in n,s, and the stated entry bound in Theorem 1.1 follows by substituting d=2ns^2. The branch n=s=1 has constant output and cost. This completes the proof of Theorem 1.1.

5.3 Acyclic path programs

The formula-to-path conversion is the only step that uses the tree model. The remaining argument applies to any strictly upper triangular coefficient representation, with its number of states in place of the formula-size bound.

In particular, an acyclic path program on m vertices with scalar- or variable-labelled edges has such a representation by the scalar-edge elimination in Lemma 3.1. The same vertex bound holds for the affine-linear edge labels allowed in an algebraic branching program. To see this, order its vertices topologically and write each edge label as c_0+\sum_{i=1}^n c_i x_i. Let E_{ab} sum the coefficients c_0 over edges from a to b, and let (N_i)_{ab} sum their coefficients c_i. Both E and each N_i are strictly upper triangular. Expanding the ordered path products and putting Q=(I_m-E)^{-1} gives, for source \sigma and sink \rho,

For the empty word the right side is e_\sigma^{\mathsf T}Qe_\rho. Thus u=e_\sigma^{\mathsf T}Q, B_i=N_iQ, and v=e_\rho give the required representation without adding vertices.