OctoInformBeta

OpenAI preprint, September 2026 · §2. An evaluator with weighted dependency paths · §2

Lemma 3 [Homogeneous lookup extensions]: Basis polynomials are a Kronecker delta on augmented dd-bit words, and the extensions are computable in space SS when the tables and vectors are

Homogeneous lookup extensions agree with their tables and are computable.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

An evaluation over a finite field looks up tables at points that are not words. A table ff on the words of dd bits, fixed below, is a function from those words to the field ℤp\mathbb{Z}_p of integers modulo a prime pp, 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 f(u)f(u) at the vector standing for each word uu. 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 ff 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 pp and a length dd. The residue z‾\bar z of an element zz of ℤp\mathbb{Z}_p is the integer in {0,…,p−1}\{0, \dots, p-1\} that represents zz. A vector is a sequence v=(v0,v1,…)v = (v_0, v_1, \dots) of elements of ℤp\mathbb{Z}_p.✦ A word of dd bits is a natural number u<2du < 2^d, read through its bits ui=⌊u/2i⌋mod⁡2u_i = \lfloor u/2^i \rfloor \bmod 2, least significant first.

The augmented word vector augd(u)\mathrm{aug}_d(u) of a natural number uu is the vector over ℤp\mathbb{Z}_p whose coordinate ii, the augmented bit coordinate of uu at ii, is augd(u)i={uiif i<d,1if i=d,0if i>d.\mathrm{aug}_d(u)_i = \begin{cases} u_i & \text{if } i < d,\\ 1 & \text{if } i = d,\\ 0 & \text{if } i > d. \end{cases}(1)✦

The coordinate choice factor of a word uu at a position ii is the linear form in a vector vv χd,u,i(v)={viif ui=1,vd−viif ui=0.\chi_{d,u,i}(v) = \begin{cases} v_i & \text{if } u_i = 1,\\ v_d - v_i & \text{if } u_i = 0. \end{cases}(2)✦ The basis polynomial Bd,uB_{d,u} of uu, a homogeneous polynomial of degree dd in v0,…,vdv_0, \dots, v_d, is Bd,u(v)=∏i=0d−1χd,u,i(v).B_{d,u}(v) = \prod_{i=0}^{d-1} \chi_{d,u,i}(v).(3)✦

The extension fˆ\hat f of a table ff, which assigns an element f(u)f(u) of ℤp\mathbb{Z}_p to each word uu of dd bits, is the function of a vector vv given by fˆ(v)=∑u=02d−1Bd,u(v)f(u).\hat f(v) = \sum_{u=0}^{2^d-1} B_{d,u}(v)\, f(u).(4)✦ The two-word extension gˆ\hat g of a table gg, which assigns an element g(u,u′)g(u,u') of ℤp\mathbb{Z}_p to each pair of words of dd bits, is the function of two vectors vv and ww given by gˆ(v,w)=∑u=02d−1∑u′=02d−1Bd,u(v)Bd,u′(w)g(u,u′).\hat g(v,w) = \sum_{u=0}^{2^d-1} \sum_{u'=0}^{2^d-1} B_{d,u}(v)\, B_{d,u'}(w)\, g(u,u').(5)✦

A vector is supplied to a machine as its packed value, the natural number whose digits in base pp, least significant first, are the residues of its first d+1d+1 coordinates: ⟨v⟩d=∑i=0dv‾ipi.\langle v \rangle_d = \sum_{i=0}^{d} \bar v_i\, p^i.(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 BB bits starts in the start state and steps to a halt with no stack ever longer than BB, the halting configuration included.✦

Let II be an index set and, for each index ii, let x(i)x(i) be a public input word, S(i)S(i) a space bound and a(i)a(i), z(i)z(i) natural numbers. The family zz is computable from aa in space SS when one stack machine and one constant cc serve every index ii: on public input x(i)x(i), with no argument tapes, the machine runs within c(S(i)+1)c\,(S(i)+1) bits per stack from a first stack holding the bits of a(i)a(i), least significant first, to a first stack holding the bits of z(i)z(i), with its heads on the left endmarkers and its other stacks empty at the start and at the end.✦ For an index set UU and a map r:U→Ir\colon U \to I, a family zz over UU is computable from a family ee over UU in space SS along rr when zz is computable from ee in space SS in the sense just defined, with the public inputs x(r(u))x(r(u)) and the space bounds S(r(u))S(r(u)).✦

The Claim

Theorem 1. Let pp be a prime and dd a natural number. For words uu and u′u' of dd bits, the basis polynomial of uu at the augmented vector of u′u' is the Kronecker delta: Bd,u(augd(u′))={1if u=u′,0if u≠u′.B_{d,u}(\mathrm{aug}_d(u')) = \begin{cases} 1 & \text{if } u = u',\\ 0 & \text{if } u \neq u'. \end{cases}(7)✦ For a table ff on words of dd bits and a word uu of dd bits, fˆ(augd(u))=f(u),\hat f(\mathrm{aug}_d(u)) = f(u),(8)✦ and for a table gg on pairs of words of dd bits and words uu, u′u' of dd bits, gˆ(augd(u),augd(u′))=g(u,u′).\hat g(\mathrm{aug}_d(u), \mathrm{aug}_d(u')) = g(u,u').(9)✦

Now let II be an index set with, for each index ii, a public input word x(i)x(i), a space bound S(i)S(i), a natural number a(i)a(i), a prime pip_i, a length d(i)d(i) and vectors v(i)v(i), w(i)w(i) over ℤpi\mathbb{Z}_{p_i}; computability below is in space SS on public input xx.

Let fif_i be a table on words of d(i)d(i) bits with values in ℤpi\mathbb{Z}_{p_i}, and fˆi\hat f_i its extension. Suppose that the packed values ⟨v(i)⟩d(i)\langle v(i) \rangle_{d(i)} are computable from aa, and that the entries of the tables are computable from their arguments: for every index set UU, every map r:U→Ir\colon U \to I and all families ee and jj over UU with j(u)<2d(r(u))j(u) < 2^{d(r(u))}, if u↦a(r(u))u \mapsto a(r(u)) and jj are computable from ee along rr, then u↦fr(u)(j(u))¯u \mapsto \overline{f_{r(u)}(j(u))} is computable from ee along rr. Then i↦fˆi(v(i))¯ is computable from a.i \mapsto \overline{\hat f_i(v(i))} \ \text{ is computable from } a.(10)✦

Let gig_i be a table on pairs of words of d(i)d(i) bits with values in ℤpi\mathbb{Z}_{p_i}, and gˆi\hat g_i its two-word extension. Suppose that the packed values of v(i)v(i) and of w(i)w(i) are computable from aa, and that the entries of the tables are computable from their arguments: for every index set UU, every map r:U→Ir\colon U \to I and all families ee, jj and j′j' over UU with j(u),j′(u)<2d(r(u))j(u), j'(u) < 2^{d(r(u))}, if u↦a(r(u))u \mapsto a(r(u)), jj and j′j' are computable from ee along rr, then u↦gr(u)(j(u),j′(u))¯u \mapsto \overline{g_{r(u)}(j(u), j'(u))} is computable from ee along rr. Then i↦gˆi(v(i),w(i))¯ is computable from a.i \mapsto \overline{\hat g_i(v(i), w(i))} \ \text{ is computable from } a.(11)✦

In the paper, the result reads: for every total f:({0,1}d)ℓ→{0,1}f\colon (\{0,1\}^d)^\ell \to \{0,1\}, with the number ℓ\ell of arguments fixed, there is a polynomial f̃\tilde f on (𝔽d+1)ℓ(\mathbb{F}^{d+1})^\ell, over the paper’s field 𝔽\mathbb{F} in the place of ℤp\mathbb{Z}_p, that agrees with ff on augmented Boolean arguments and is homogeneous of degree dd separately in every argument, and if a coordinate of ff is computable in space O(dpolylog⁡T)O(d \operatorname{polylog} T), for the simulated time TT, 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 ℤp\mathbb{Z}_p, in whatever space SS their entries and the supplied vectors are computable.

What Is Checked

The claim is stated over the field ℤp\mathbb{Z}_p of a prime pp, 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 SS by stack machines, directly and along a map of index sets.