Results on one-tape machines, polynomial extensions of Boolean functions, and evaluation in small space

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• An offset with few visits — Lemma 3.1. If the writable tape is cut into blocks of width b, then for some offset the capped computation of T steps passes from one block to another in at most T/b steps, and the controller after ceil(1 + T/b) visits is terminal.
• Visits as total maps on raw controllers and blocks — Lemma 4.1. The maps sel and Visit are defined on all raw controllers and blocks, computed in space O((b+1) polylog T); a run from an accepted controller stays within the cells of distance at most T; on the controller and represented block of the computation, Visit gives those after the visit.
• Local replay — Lemma 5.2. A list of raw controllers that begins with z_0 is the reference list from z_0 and given blocks if and only if, for every block separately, the replay of the visits that the list assigns to this block reproduces the listed controllers; then the replay buffers are the blocks of the reference evolution.
• Fields of characteristic two with arithmetic in small space — Lemma 1.1. For every Delta there is a field with 2^m elements, Delta < 2^m <= max(2, Delta^2), built by repeated extensions K[X]/(X^2 + X + a); its elements are listed and multiplied and inverted in space polylogarithmic in Delta.
• Lookup extensions of Boolean functions of words — Lemma 2.1. Every function from n-tuples of words of d bits to bits is the restriction, to augmented words (v, 1), of a polynomial on (F^(d+1))^n that is homogeneous of degree d in each of its n arguments; the constant function 1 of one word extends to z_*^d.
• The top coefficient as a weighted sum of values — Lemma 3.1. For L+1 distinct points with the weights w(s) = 1/prod(s - u): the sum of w(s) p(s) is the coefficient of X^L of a polynomial p of degree at most L, and the sum of w(s) Q(a + s v) is Q(v) for Q homogeneous of degree L, for all vectors a and v.
• A Boolean value from shifted arguments — Corollary 3.2. For a function f of n words and arbitrary vectors a_1, ..., a_n: the weighted sum over s_1, ..., s_n of the lookup extension at a_j + s_j (v_j, 1) is f(v_1, ..., v_n).
• An evaluator with one pool of registers — Theorem 2.1. For a system of words of d bits with base, ordinary and history rules there is a procedure Add(V, lambda, t) on a pool of max(3, r+1) registers that, for every content of the pool, adds lambda (v(V), 1) to the register t and restores all other registers; it runs in space O((d + W(V) + 1) polylog T), where W(V) is the largest weight of a dependency path and a dependency A_i of a history rule with guesses of g bits has the weight g + 1.
• A round of visits is a history rule — Lemma 2.2. For the list H_(e,j) of the controllers of an epoch through its round j and the blocks A_(e,i) at the start of the epoch: exactly one guess of the next k controllers passes the replay test of every block, and it gives H_(e,j+1).
• The weight of a dependency path — Lemma 3.1. In the system of the epochs every path from a vertex of the epoch e has a weight of at most (e+1)(k + kc + 2): a path contains at most one step of the large weight kc + 1 in each epoch.
• One-tape time in two-fifths-power space — Theorem 4.1. For a fixed deterministic machine with one writable tape and head, a fixed number of read-only heads and polylogarithmic-space access to its initial symbols: the state and the halting outcome after at most T steps are computed in space O(T^(2/5) log^C(T+2)), and in space O~((t+2)^(2/5)) without a given cap if the machine halts after t steps. Running time is unrestricted.
• Several writable tapes in square-root space — Proposition 2.3. For a fixed deterministic machine with a fixed number of writable tapes and read-only heads: the outcome after at most T steps is computed in space O(sqrt(T) log^C(T+2)).
• A lower bound for time on machines with one writable tape — Corollary 3.1. Assume the space hierarchy theorem (hypothesis (SH), not proved in the course). For every space-constructible s(n) >= n and 0 < eps < 5/2 there is a language decided in space O(s(n)) that no machine with one writable tape decides in time O(s(n)^(5/2 - eps)).

Reading order

Five lessons. The first four prove the main theorem in full, with no theorem taken from the literature: the tape is cut into blocks, a proposed list of controllers is checked block by block, and an algebraic evaluator computes the lists round by round with three registers. The fifth lesson treats several writable tapes (square-root space) and derives a lower bound for time; that last corollary uses the space hierarchy theorem as a named hypothesis. Space means bits of working storage of an algorithm described in words; machines for the algorithms are not written out.