The Setting
The evaluator with weighted dependency paths interpolates over a finite field, and the space-bounded machine that runs it builds this field itself from a bound . Here the field is a prime field , the prime found from by trial division. The question is whether each step fits in the work space in which its inputs are computed: finding from , testing a number for primality, multiplying two residues modulo , and adding up or multiplying out a family of residues.
Trial Division and the Chosen Prime
A test is a function from the natural numbers to bits. For a test and a bound , the bounded check of below is the bit that is exactly when for every , and the bounded search is the largest with , or when there is none.✦
The divisor check of a number for a number is the bit that is exactly when and divides .✦ The trial-division test of a natural number is the bit given by the bounded check of below : (1)✦
A number is accepted for , written , when and .✦ The search range for is the set of numbers below ✦, and the search for is the bounded search of over it: (2)
A prime modulus is a prime number ✦, and its field is the field of residues modulo ✦; a residue is written as its representative with . The chosen prime modulus for is the prime .✦
Stack Machines and Space
A read-only tape holds a word between a left endmarker at position and a right endmarker , and a head on the tape stands at one position and reads the mark there.✦ The mark a head reads is at position , the letter of at index , counted from , at position , and past the last letter.✦ A head direction is a left move , no move or a right move ✦; a head moves one position in its direction, never to the left of and never past .✦
The inputs of a stack machine are a public input, a word over an alphabet , and for each in a set an argument, a word of bits; each of these read-only tapes has its own head.✦ The heads are at home when every head is at position ✦, and an input head advance gives every head a direction, unless it says otherwise.✦
A stack machine with these inputs, stacks of bits indexed by a finite set and outputs in a set consists of a finite set of states, a start state and a transition table.✦ On a state, the marks under the heads and the top of each stack, a bit or nothing for an empty stack, the table either halts with an output in or takes an action, which is a next state together with a stack change. A stack change is an input head advance together with an operation on each stack, each operation being to keep the stack, to push a bit on it or to pop its top bit. Popping an empty stack leaves it empty.✦
A store is a position for each head and a content for each stack✦, and a configuration is a state with a store.✦ A step from a configuration is the passage to the configuration obtained by consulting the table at and, unless the machine halts there, performing the action: every head moves in its direction and every stack undergoes its operation.✦ A run in space is a deterministic halting run, a sequence of steps from a configuration to a configuration at which the machine halts with an output , every stack holding at most bits at every configuration from to .✦ An execution from a store to a store is a run from the start state with store that halts with store .✦
Let be a set of indices with space bounds . A stack computation in space on inputs from stores to stores with outputs is a stack machine whose stacks are those of the stores together with finitely many extra stacks, together with a constant , such that for every the machine on has an execution in space from , the extra stacks empty, to , the extra stacks empty again, with output .✦ The store of a number has every head at home and one stack holding the binary digits of without leading zeros, least significant on top.✦
For public inputs and families and of numbers, is computable from in space , written , when there is a stack computation in space on the public inputs , with no argument tapes, from the store of to the store of .✦ A family is written without its index, as in for the family , and a family of residues stands for the family of their representatives.
For a family of numbers, the index pairs below are the pairs with and , the pair taking the public input and the space bound .✦ A family on these pairs is computable from and the index when for every family on the pairs with and , where and stand for the families and on the pairs.
The Claim
Theorem 1. Let and be natural numbers. The trial-division test accepts exactly the primes, (3)✦ the search for ends inside its range at an accepted number, (4)✦ and the chosen prime modulus lies above and below the end of the range: (5)✦ (6)✦
Let be public inputs and space bounds for the indices in a set , and let , and be families of numbers. If , then (7)✦ and if , then (8)✦ Let be prime moduli with . If and are residues in with and , then (9)✦ If and the residues in , for , form a family computable from and the index, then (10)✦ (11)✦
In the paper, the result reads: given a time bound and an integer bounded by a polynomial in , one can construct uniformly a field of characteristic two with , whose elements have bits and whose description, enumeration, arithmetic and inversion of nonzero elements need space , where . The library’s field for is the prime field in place of a field of characteristic two.
What Is Checked
The claim is stated over the trial-division test with its divisor check, the bounded search for accepted numbers and the chosen prime modulus , the fields of prime moduli, and computability in space by stack machines whose stacks hold at most bits.