The Setting
Fix . The hitting list for noncommutative rational formulas of size at most in variables is a finite list of tuples of square rational matrices, all of one size, given by an explicit construction over a cyclotomic field. Proposition 5.3 measures the cost of writing it down. The input is and in unary, as the word , and the output is every entry of every matrix of the list, in binary: how many steps does one Turing machine need, and how long is what it writes?
Formulas and Hitting Lists
A rational formula in variables is a finite tree built from the variables and rational constants by addition, multiplication in a fixed order and inversion✦; its size is its number of vertices.✦
Let be a ring with a ring homomorphism , and let . The evaluation of rational formulas at is the least relation between formulas and elements of in which has the value , a constant has its image in , and have the values and when and have the values and , and has the value when has a value with .✦
At a tuple of rational matrices, evaluation takes place in the ring , a constant being the scalar matrix .✦ A rational formula in variables is admissible if it has a value at some tuple in with ✦, and nonzero if it has a nonzero value at some such tuple.✦
A list of tuples in variables consists of a positive integer , its dimension, and a finite sequence of tuples in ; its length is the number of these tuples.✦ A list of tuples in variables is a hitting list for size if every admissible nonzero rational formula in variables with has a value that is an invertible matrix at some tuple of .✦
The Hitting List
The construction uses the parameters (1) Here is the truncation and the grid size.
The cyclotomic field is the quotient of by the monic polynomial of degree ✦; in it is a primitive -th root of unity, and is its power basis over .✦ The regular representation is the -algebra homomorphism sending to the matrix of multiplication by in the power basis.✦
For an matrix over with rows and columns indexed by , the matrix has in row and column the entry of , with and read in .✦ The signed entries , for read in and , are the integers (2)✦ the entries of .
For a point of a field , the padded test matrix of order at is the matrix over , with rows and columns indexed by and read in , whose first columns are given below and whose other columns are zero; its entry in row and column is, binomial coefficients out of range being zero, (3) The test matrices are , at the points , and at integers and the same formula defines integer matrices .
Let be an additive character of with values in a field . The Weyl monomial , for , is the matrix over with entry in row and column when , and otherwise.✦ The three-parameter lift of an matrix over , indexed by , is the matrix over (4)✦ with exponents the least nonnegative representatives of and ; the are its Fourier coefficient polynomials.
The pencil lifts are the lifts of the test matrices over along the character of .✦ At a point the regular matrices are (5)✦ The list is the list of tuples of dimension whose tuples are (6) taken in the lexicographic order of .
Exact Arithmetic
For and , the integer matrix has in row and column , for and , the integral lift entry (7)✦ where is the integer padded test matrix at the point with , and the exponents are least nonnegative representatives.
The division-free determinant of an integer matrix of order is if and otherwise times the top-left entry of stage of ✦, where stage is and each further stage comes from the one before by an elimination step relative to that uses only additions, subtractions and multiplications of integers.✦
Write for the matrix with its column replaced by column of . The executable list is the list of tuples of dimension that has, for each in lexicographic order with , the tuple whose -th matrix, for , has in row and column the Cramer quotient (8)
Binary Encoding
For a bit word , is its length and its reversal. A natural number with binary digits , least significant first, is encoded as , and .✦ A rational number in lowest terms with is encoded as , with the sign bit equal to exactly when ✦, and a tuple of matrices as the concatenation of the encodings of its entries, matrix by matrix and row by row.✦ A list of tuples with tuples is encoded as (9)✦
The output constant , the constant in the bound on the length of in the claim below, is the positive integer (10)✦ where is the log constant✦ and the bit constant.✦
Programs and Machines
A stack program over a set of registers, each register holding a stack of bits, is built from the instructions that do nothing, push a bit onto a register, pop the top bit of a register and move the top bit of one register onto another, the last two doing nothing on an empty register, by sequencing, by a branch that runs one of three programs depending on whether a register is empty or has top bit or , and by a loop that runs a program while a register is nonempty.✦ The running time of a run of a program, from one assignment of stacks to the registers to another, is the number of steps: one for an instruction, one more than the runs it is made of for a sequence, a branch or a pass of a loop, and one for a loop that finds its register empty.✦
A register holds a bit word when reads from the top of its stack down. For a program with an input register and an output register, means that , run from the input register holding and every other register empty, ends after steps with the output register holding and every other register empty.
Let and be sets, and let and be bit encodings of them, that is, maps from and to bit words. A map is feasible if it has a stack procedure✦: a stack program over finitely many registers, with an input and an output register, and a polynomial with natural coefficients such that every has for some and .✦
A Turing machine is deterministic, with finitely many states and one tape over the alphabet , in which is the blank, the digit symbols and stand for the bits and , and is work space; given the state and the scanned symbol, its transition function either halts or gives a new state with a head move or a symbol to write.✦ A configuration is a state, a tape and the head position✦, and time is the number of transitions. For bit words and , means that the machine , started in its initial configuration on written in the digit symbols, makes transitions and reaches a configuration with no transition, whose tape holds in the digit symbols from the head rightwards, followed by blanks.
The Claim
Theorem 1. For all natural numbers and , (11)✦ and for and every , (12)✦ (13)✦ For all and , (14)✦ and for , (15)✦ The map sending , encoded as , to the bit word is feasible, with a stack program and a polynomial for which, for all and , (16)✦ There are a stack program over finitely many registers and positive integers and such that, for all , (17)✦ For every stack program over finitely many registers, with an input and an output register, there are a Turing machine and a positive integer such that, whenever for a nonempty bit word , a bit word and a number , (18)✦ with only blanks to the left of the head at the end. There are a Turing machine and positive integers and such that, for all , (19)✦ and for every stack program over finitely many registers and all positive integers and satisfying (17), there are a Turing machine and positive integers and such that, for all , (20)✦
In the paper, the result reads: the list can be constructed and written by one deterministic Turing machine in a number of bit operations bounded by a fixed polynomial in , and its entire binary encoding has length bounded by a fixed polynomial in the same quantity.
What Is Checked
The claim is stated over rational formulas and their evaluation at rational matrices, with admissible and nonzero formulas and hitting lists; the lists and built from the parameters (1); the encoding (9) and the constant ; stack programs with their running time and feasible maps; and Turing machines over timed by their transitions.
For all and , (21)✦ and for and every , (22)✦ For every and , (23)✦ and if every coordinate of is at most an integer , every entry of satisfies (24)✦ If , then for , (25)✦ For integer matrices and of order with , Cramer’s rule reads (26)✦ and for every integer square matrix , (27)✦