The Setting
A rational formula in noncommuting variables is built from the variables and rational constants by sums, products and inverses, and it is evaluated by substituting square matrices for the variables. An inverse gate that meets a singular matrix leaves the formula undefined there: has no value at any pair of scalars and has values at pairs of matrices. Black-box identity testing asks for a finite list of matrix tuples, depending only on and a size bound , at one of which every nonzero formula of size at most is defined and invertible. The question is whether a deterministic machine can write such a list in time polynomial in and .
A rational formula in variables is a tree whose leaves are variables or rational constants and whose inner vertices are sums , products in that order, and inverses , for formulas and .✦ Its size is its number of vertices: (1)✦
Let be a ring with a ring homomorphism from , and . The relation “ has the value at ” is defined by induction on : the variable has the value and a constant has its image in ; if and have the values and , then and have the values and ; if has a value and satisfies , then has the value .✦ At a tuple of rational matrices the values are taken in , with as the scalar matrices.✦
A formula is admissible if it has a value at some tuple in with .✦ A formula is nonzero if it has a nonzero value at some tuple in with .✦
A list of -tuples is a dimension together with a finite sequence of -tuples of rational matrices: (2)✦ A list of -tuples hits size if every admissible nonzero formula in variables of size at most has, at some tuple of , a value that is an invertible matrix.✦
Machines and Encodings
The tape alphabet is : is the blank, and stand for the binary digits and , and is a work symbol.✦ A Turing machine over with states is a partial transition function (3)✦ in state reading it halts if is undefined, and otherwise enters the new state and either moves its head one cell or writes the given symbol.
A configuration of is a state with a tape and a head position, and is the configuration after one transition, undefined when halts at .✦ For a number of transitions and a configuration of , the configuration reached from after transitions is defined by recursion on : (4)✦ with undefined when is.
The input on integers and is the word (5)✦ the string in the symbols of the binary digits, and is the configuration in the initial state, state , with the word on the tape from the head rightwards and blanks elsewhere.
A natural number with binary digits , least significant first, for , has the self-delimiting encoding (6)✦ A rational number in lowest terms with is encoded by a sign bit followed by its numerator and denominator: (7)✦ A tuple in is encoded by the encodings of the entries of its matrices in turn, each matrix row by row✦, and a list as in (2) by the word (8)✦ of length .
The word is written in the symbols of the binary digits.✦ A machine outputs from within transitions if there are and a configuration with (9)✦
The Explicit List
For the explicit list is built from the parameters (10)
Let be a field and the space of polynomials in over of degree below , and let be a further indeterminate. The Taylor test at a point is the linear map with (11) and its matrix is the matrix over , rows and columns indexed by , whose column is the coefficient vector of and whose columns are zero. Over , for integers and , the entry of in row and column is the integer .
Over a field with an additive character of , the Weyl monomials are the matrices , , with when and otherwise.✦ A matrix over indexed by has the Fourier coefficient polynomials ✦, and its lift is the matrix over (12)✦ with the exponents read in .
The field is the -th cyclotomic field, with the additive character of .✦ The regular representation of sends to the matrix of multiplication by in the power basis ; on , , it is the signed permutation matrix with (13)✦ The entrywise extension of replaces each entry at by the block in rows and columns .
With , let be the lift of for the points ✦, and at a point with positive integer coordinates.✦ The list runs over the grid in lexicographic order: (14)✦
The list is formed over the same grid from integer matrices. For the matrix has at the block (15)✦ with the integer Taylor matrix and exponents and subscripts read in . The division-free determinant of a integer matrix is times the top-left entry of , where and is obtained from and by one elimination stage.✦ The list has dimension and keeps, in lexicographic order, the grid points with ; there it gives the tuple whose -th matrix has at the Cramer quotient (16)
The output constant is defined through two others: (17)
The Claim
Theorem 1. There are a Turing machine over and positive integers and such that, for all integers and with , some list of -tuples of rational matrices satisfies (18)✦
In the paper, the result reads: there are a deterministic Turing machine and positive integers and such that, given and with , outputs a finite list of -tuples of rational square matrices in at most bit operations, the whole output, with signed binary numerators and positive binary denominators, has at most bits, and every nonzero admissible rational formula in variables of size at most has a defined evaluation with invertible value at some tuple of , the same list serving all such formulas whatever the bit lengths of their constants or their inverse depth, and receiving no formula, oracle, randomness or advice.
What Is Checked
The theorem (18) is stated over rational formulas with their size and values, the admissible and nonzero formulas, lists of tuples (2) and the hitting property, Turing machines (3) run as in (4) from the input (5), and output within a bound (9) in the encoding (8) built on (6) and (7).
The library proves that the modulus of is a monic polynomial✦ of degree ✦. Of the list it proves that, for all , (19)✦ and that there are a Turing machine and positive integers and with (20)✦ It also proves that a Turing machine and positive integers as in (20) give a Turing machine and positive constants as in the theorem: (21)✦