The Setting
Let be a prime and the field of integers modulo . For a natural number , Lagrange interpolation recovers a polynomial of degree at most over from its values at points, and its top coefficient, the coefficient of , is then one linear combination of those values. Here the sample points are all elements of the field, and the weights depend only on and on the point.
The functions sampled come from low-degree extensions of tables indexed by -bit words. Such an extension is a polynomial function on vectors over ; restricted to the line through a point in a direction , it becomes a function of one parameter , and the question is what its top coefficient is.
Weights and Top Coefficients
For a natural number , the interpolation weight of degree at a field element is (1)✦
A function has degree at most with top coefficient if there are such that agrees at every point of with the polynomial : (2)✦ For any polynomial , denotes its coefficient of .
Word Extensions on Lines
A coordinate vector over is a sequence of elements of .✦ For coordinate vectors and , the line through in direction is the map sending to the vector with coordinates .✦
A natural number is read as a binary word, least significant digit first: its digit at place is , the case of the base- digit .✦ Fix a width . Coordinate is the augmenting coordinate, which holds when a -bit word is read as a vector. The coordinate choice factor of at place and the Boolean basis polynomial of , at a coordinate vector , are (3)
The multilinear word extension of a table of elements of indexed by -bit words is the function on coordinate vectors (4)✦ The two-word extension of a table indexed by pairs of -bit words, at coordinate vectors and , is the word extension at of the table sending to the word extension of at : (5)✦
The Claim
Theorem 1 (Top-coefficient extraction). Let be a prime. The st powers of the elements of sum to : (6)✦ Let be a natural number with . For every natural number , (7)✦ for every polynomial of degree at most , (8)✦ and for every function of degree at most with top coefficient , (9)✦ Let be a natural number, , , coordinate vectors, a natural number, a table indexed by -bit words and a table indexed by pairs of -bit words. Then there are , not depending on , such that for every (10)✦ (11)✦ (12)✦ (13)✦
In the paper, the result reads: for a field and , any distinct points of , with weights , give the coefficient of in every polynomial of degree at most as , and for every homogeneous of degree and all points and ; with the first field elements, the points and weights are enumerable in space polylogarithmic in the time bound , and the paper’s is the page’s .
Here the sample set is all of , with the weights , and the forms are the basis polynomials and the word extensions.
What Is Checked
The claim is stated over the field of integers modulo a prime , the interpolation weights , functions on of degree at most with a given top coefficient, the lines through coordinate vectors, and the Boolean basis polynomials with the word extensions and built from them.