The Setting
A hitting list for noncommutative rational formulas in variables of size at most is built from a few integers computed from and and from one linear test at each point . The integers fix the dimensions: a power of two and a number of columns. The test acts on polynomials in of degree below with formal Laurent series in as coefficients. Its matrix has entries in the polynomial ring in and yields the test matrix of the construction.
The library defines the integers as functions of and , and the test and its matrices at an arbitrary point of an arbitrary field , written and .
Taylor Coordinates and Weights
Let be a field and the field of formal Laurent series in over .✦ The polynomial embedding is the ring homomorphism that fixes and sends to ; on matrices it acts entrywise.✦
For a field and a natural number , is the space of polynomials in over of degree below . The coefficient map is the linear map (1)✦ an isomorphism of onto ; through it and are identified, and the standard basis of becomes .
For a point , the Taylor coordinates at form the linear automorphism of that sends a polynomial of degree below to its coefficients in powers of : (2)✦ The reversal of is the linear automorphism that sends to the vector with ✦, and the reverse Taylor coordinates at form the automorphism (3)✦
A -linear map extends to the -linear map with the same matrix.✦ For natural numbers , the weight map with weights is the -linear map of that multiplies the -th coordinate by ; with it is .✦
The Claim
Definition 1. Let and be natural numbers. The width is (4)✦ the bound is ✦, the gap is ✦, and the exponent is (5)✦ The power of two and the truncation are (6) Then exceeds , (7)✦ is at most twice it, (8)✦ and is the least power of two above it: (9)✦ The truncation is positive, (10)✦ and (11)✦
Let be a field, and , and let and be the numbers above or any natural numbers. The test at is the -linear map of (12)✦ and it is injective: (13)✦ The Taylor test matrix has, in row and column , (14)✦ where is the coefficient of in ; its image under is the matrix of in the basis : (15)✦ The test matrix keeps the first columns of and replaces the others by zero, (16)✦ and its entries have -degree at most : (17)✦
In the paper, the result reads: with , , , the least power of two greater than and , so that , and with , the test sends to , is injective and has a matrix with entries in of -degree at most , and is with zero columns appended.
What Is Checked
The definition is stated over natural numbers and , a field with its field of formal Laurent series, and a point , and it uses the coefficient map , the Taylor coordinates and , the reversal , the extension of scalars from to , the weight map and the polynomial embedding .
Of these constructions, the library proves that the extension to of an invertible -linear map is invertible, with the extension of the inverse as its inverse✦, and that the reversal is its own inverse.