The Setting
Fix a number of variables and a size bound . Write for the ring of rational matrices, with rows and columns indexed by .✦ A point of with hits a noncommutative rational formula, built from and rational constants by addition, multiplication and inversion, when the value of the formula at that point is defined and invertible. A hitting list for a class of nonzero formulas is a positive integer with a finite list of points of that contains, for every formula of the class, a point hitting it.
A matrix of polynomials is lifted to three parameters over the -th cyclotomic field, for a power of two fixed by and , and at each integer point of a cube the lift becomes a tuple of rational matrices through the regular representation of the field.
The Cyclotomic Field
Let be a natural number, let (1)✦ be the degree, and let ✦. The modulus is the polynomial of ✦, the -th cyclotomic polynomial: (2)✦
The cyclotomic field is the quotient of by the ideal generated by the modulus.✦ The class of is a primitive -th root of unity, and has over the power basis , indexed by : (3)✦
The regular representation is the -algebra homomorphism sending to the matrix of multiplication by in this basis: (4)✦
The additive character of with values in is built on ✦, and it is primitive: (5)✦
Write for the ring of matrices over , with rows and columns indexed by , read as . With the block dimension (6)✦ the regular representation extends entrywise to the ring homomorphism that sends a matrix of to the matrix placing the block in block row and block column : (7)✦
The Parameters
The list depends on and through the width , the bound , the gap , the exponent and the truncation , (8) where is then the least power of two greater than ✦, and through the grid size (9)✦
The Lift
Let be a field, an additive character of with values in , and a natural number, and write for the coefficient of in a polynomial . The Taylor test matrix of order at a point is the matrix over whose column takes the Taylor coefficients of at , multiplies the one of order by and makes it the coefficient of .✦ The padded Taylor test matrix has entries (10)✦ For , is the padded Taylor test matrix at the point .
The Weyl monomial , for , is the product of the clock matrix and the power of the cyclic shift.✦ The Fourier coefficients of an matrix over along these monomials are the polynomials : (11)✦
The three-parameter lift of is the matrix over with (12)✦ the exponents and read in . The pencil lifts are the lifts (12) of the padded test matrices (10) at the points : (13)✦
The Claim
Definition 1. Let , , and be natural numbers, with , , , and those of , and let be the pencil lifts (13) over , with the character of (5) and the truncation . At a point of and for , the cyclotomic lift matrix and the regular matrix are (14)✦ (15)✦ When is invertible, writing for , the tuple at the point is (16)✦ and the point yields (17)✦ The grid of side is the list of the triples of natural numbers below in lexicographic order, (18)✦ and the generator output is the list, of common dimension , of the tuples yielded in this order at the points of , a point that yields no tuple contributing nothing: (19)✦ For natural numbers and , the rational hitting list is the output at the parameters (8) and (9): (20)✦
In the paper, the result reads: with , , and , where is multiplication by in the power basis and applies entrywise, the lift of is formed over , and for each the generator computes , emits nothing if is singular, and otherwise emits .
What Is Checked
The generator (19) and the list (20) are stated over the cyclotomic field with its power basis, the regular representation and its extension , the character , the pencil lifts of the padded Taylor test matrices, and the parameters (8) and (9).
Of these constructions the library proves that the modulus is monic✦ of degree ✦ and equal to , as in (2)✦, and that is primitive, as in (5)✦.