The Setting
An evaluation over a finite field looks up tables at points that are not words. A table on the words of bits, fixed below, is a function from those words to the field of integers modulo a prime , and the device for reading it elsewhere is a low-degree extension: a polynomial in the coordinates of a field vector that takes the value at the vector standing for each word . The question is which extension to take, and in what space it can be evaluated at a vector supplied as input when the entries of are computed by a machine rather than stored. Tables on one word and on pairs of words are treated.
Augmented Words and Their Extensions
Fix a prime and a length . The residue of an element of is the integer in that represents . A vector is a sequence of elements of .✦ A word of bits is a natural number , read through its bits , least significant first.
The augmented word vector of a natural number is the vector over whose coordinate , the augmented bit coordinate of at , is (1)✦
The coordinate choice factor of a word at a position is the linear form in a vector (2)✦ The basis polynomial of , a homogeneous polynomial of degree in , is (3)✦
The extension of a table , which assigns an element of to each word of bits, is the function of a vector given by (4)✦ The two-word extension of a table , which assigns an element of to each pair of words of bits, is the function of two vectors and given by (5)✦
A vector is supplied to a machine as its packed value, the natural number whose digits in base , least significant first, are the residues of its first coordinates: (6)✦
Space-bounded Computation by Stack Machines
The machines are stack machines. A stack machine has a finite set of states with a start state, read-only heads on a public input word and on argument tapes of bits, each tape framed by a left and a right endmarker, and finitely many stacks of bits; a configuration is a state with the positions of the heads and the contents of the stacks.✦ In a step, the transition table reads the state, the symbols or endmarkers under the heads and, for each stack, its top bit or the fact that it is empty. It then either halts with a label or moves each head one cell left, one cell right or not at all, never past an endmarker, keeps, pushes onto or pops each stack, and enters a next state. A run within bits starts in the start state and steps to a halt with no stack ever longer than , the halting configuration included.✦
Let be an index set and, for each index , let be a public input word, a space bound and , natural numbers. The family is computable from in space when one stack machine and one constant serve every index : on public input , with no argument tapes, the machine runs within bits per stack from a first stack holding the bits of , least significant first, to a first stack holding the bits of , with its heads on the left endmarkers and its other stacks empty at the start and at the end.✦ For an index set and a map , a family over is computable from a family over in space along when is computable from in space in the sense just defined, with the public inputs and the space bounds .✦
The Claim
Theorem 1. Let be a prime and a natural number. For words and of bits, the basis polynomial of at the augmented vector of is the Kronecker delta: (7)✦ For a table on words of bits and a word of bits, (8)✦ and for a table on pairs of words of bits and words , of bits, (9)✦
Now let be an index set with, for each index , a public input word , a space bound , a natural number , a prime , a length and vectors , over ; computability below is in space on public input .
Let be a table on words of bits with values in , and its extension. Suppose that the packed values are computable from , and that the entries of the tables are computable from their arguments: for every index set , every map and all families and over with , if and are computable from along , then is computable from along . Then (10)✦
Let be a table on pairs of words of bits with values in , and its two-word extension. Suppose that the packed values of and of are computable from , and that the entries of the tables are computable from their arguments: for every index set , every map and all families , and over with , if , and are computable from along , then is computable from along . Then (11)✦
In the paper, the result reads: for every total , with the number of arguments fixed, there is a polynomial on , over the paper’s field in the place of , that agrees with on augmented Boolean arguments and is homogeneous of degree separately in every argument, and if a coordinate of is computable in space , for the simulated time , its extension can be evaluated at supplied field vectors in that space with no recursive word evaluation, the same holding coordinatewise for word-valued functions.
The box answers it for tables of one and two arguments valued in , in whatever space their entries and the supplied vectors are computable.
What Is Checked
The claim is stated over the field of a prime , the augmented word vectors (1), the choice factors (2) and basis polynomials (3), the extensions (4) and (5) of tables on one and two words, the packed values (6) of supplied vectors, and computability in space by stack machines, directly and along a map of index sets.