The Setting
Fix and . A noncommutative rational formula in of size at most may vanish at many tuples of matrices, or be undefined there because an inverse gate meets a singular matrix. The question is whether a single explicit list of tuples of rational matrices, all of one size, catches every such formula that is not zero, in the strong sense that the formula is defined at some tuple of the list and takes an invertible value there. The theorem below says that a list , built from a cyclotomic field and an integer grid and defined in The Generator, does this.
A rational formula in variables is a finite tree built from the variables and rational constants by addition , multiplication in this order, and inversion .✦ The size of is its number of vertices: a variable or a constant has size , and each gate adds to the sizes of its operands.✦
Let be a ring receiving and let . The evaluation of formulas at is the least relation between formulas and elements of closed under the rules (1)✦ where a constant stands for its image in and the last rule applies only when has a two-sided inverse in . At a tuple the ring is , a constant standing for the scalar matrix .✦
A formula in variables is admissible if for some , some tuple and some matrix ✦, and nonzero if this holds with ✦. A list of tuples in variables consists of a dimension and a finite list of tuples in .✦ A list of tuples of dimension is a hitting list for size , written , if every admissible nonzero formula in variables with satisfies (2)✦
The Generator
For put ✦, ✦ and .✦ The cyclotomic field is the -th cyclotomic field, obtained from by adjoining a primitive -th root of unity ✦; its modulus is monic✦ of degree ✦, and is its power basis over .✦ An additive character of in a field is a group homomorphism from to the multiplicative group of ; in it is the one sending to .✦ The regular representation is the -algebra homomorphism sending each to the matrix of multiplication by in the power basis✦, and its entrywise extension is the ring homomorphism replacing every entry by its block.✦
Fix a -algebra homomorphism ✦, and let be the field of Hahn series with complex coefficients and exponents in , ordered lexicographically✦. The witness embedding of is the ring homomorphism (3)✦ where sends a complex number to the constant series.
Let be a field and . The test matrix at the point is the padded Taylor test matrix of order at with kept columns: the matrix over , with rows and columns indexed by and read in , with entries (4)✦ with an indeterminate and the coefficient of in a polynomial in .
For an additive character of in and , the Weyl monomial is the matrix over indexed by whose entry at is if and otherwise, the product of the clock matrix and the power of the cyclic shift.✦ The three-parameter lift of a matrix over indexed by is the matrix of polynomials in over (5)✦ the exponents read in . The pencil lifts are the lifts of the test matrices.✦
Over , with , a point gives the matrices , the pencil lifts evaluated at ✦, and the rational matrices of size , for ✦. The tuple at is (6)✦ For natural numbers , and , the generator output is the list of tuples of dimension made of the for running through the grid in lexicographic order, each kept only when .
The parameters of and are (7) with the least power of two greater than ✦, and the hitting list is the output at these parameters✦.
Pencils and Certificates
An affine form in variables is an expression with rational coefficients✦, and is its coefficient vector✦. In a ring receiving , its evaluation at and its homogeneous evaluation at are (8)
A pencil of order is a matrix of affine forms; its coefficient matrices collect the coefficients of its entries✦, and and are the matrices over obtained entrywise. At matrices, is the block matrix up to the order of the basis. The one pencil is the pencil of order whose single entry is the constant form .✦
The pencil of a formula is defined by recursion on through block matrices, (9) where the row and the column of a formula are the rational vectors, of length the order of , given by the recursions (10) with the blocks following those of , the new index of last. The order of is when is a variable or a constant, the sum of the orders of and when is or , and one more than the order of when .
The certificates of a formula are its inverse subformula occurrences , one for each inversion gate, listed in prefix order (a gate before its operands, a left operand before a right one), followed by .✦
Let be a field of characteristic zero with an additive character of . The certificate matrix of a pencil of order is the matrix of size over whose block at is the lift of the combination of test matrices weighted by the entries at of the coefficient matrices, (11)✦ and is the certificate determinant of ✦. The condition list of for and is the list of certificate determinants over , with , (12)✦
The Claim
Theorem 1. Let and be natural numbers with . Then (13)✦ Let moreover , and be any natural numbers with , , and , where and , are as in (7). Then (14)✦
In the paper, the result reads: every nonzero admissible formula of size at most has a defined, invertible evaluation at a tuple in .
What Is Checked
The claim is stated over rational formulas with their size and their evaluation (1) at tuples of rational matrices, admissible and nonzero formulas, lists of tuples with the hitting property (2), and the generator output , built from the cyclotomic field , its regular representation and the pencil lifts, with its instance at the parameters (7).
For , a formula with and any and , the condition list satisfies (15)✦ with the total degree. If moreover is nonzero, , and , then (16)✦
Over a field , a nonzero polynomial in variables whose total degree is less than the size of a finite set satisfies the grid form of the Schwartz-Zippel lemma, (17)✦ For a finite list of nonzero polynomials in variables, each of total degree at most , with , (18)✦ In three variables over a field of characteristic zero, with in place of , the point lies in the integer grid: (19)✦ The parameters (7) of and satisfy (20)✦
Let be a field of characteristic zero with an additive character of , a pencil of order , and a point with . Then (21)✦ For square matrices of size over at which the homogeneous evaluation of the one pencil is invertible, (22)✦ Over any -algebra , if a point has a unit as its coordinate and for a pencil of order , then (23)✦
Let be a point at which is invertible in , and a formula with an invertible value at the tuple over . Then, at the rational tuple (6), (24)✦ For with invertible in , the tuple at is a tuple of the output: (25)✦