OctoInformBeta

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

Lemma 2 [Uniform fields]: A prime pΔp_\Delta with Δ+1<pΔ<2(Δ+1)+1\Delta+1<p_\Delta<2(\Delta+1)+1, computable from Δ\Delta; products of two residues, and iterated sums and products, in the same space

Prime fields by trial division, with space-bounded sums and products.

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

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 Δ\Delta. Here the field is a prime field ℤp\mathbb{Z}_p, the prime pp found from Δ\Delta by trial division. The question is whether each step fits in the work space in which its inputs are computed: finding pp from Δ\Delta, testing a number for primality, multiplying two residues modulo pp, and adding up or multiplying out a family of residues.

Trial Division and the Chosen Prime

A test is a function qq from the natural numbers to bits. For a test qq and a bound nn, the bounded check of qq below nn is the bit that is 11 exactly when q(m)=1q(m) = 1 for every m<nm < n, and the bounded search searchn(q)\mathrm{search}_n(q) is the largest m<nm < n with q(m)=1q(m) = 1, or 00 when there is none.✦

The divisor check dp(m)d_p(m) of a number mm for a number pp is the bit that is 00 exactly when m≥2m \ge 2 and mm divides pp.✦ The trial-division test of a natural number pp is the bit τ(p)\tau(p) given by the bounded check of dpd_p below pp: τ(p)=1⇔p≥2 and dp(m)=1 for every m<p.\tau(p) = 1 \iff p \ge 2 \text{ and } d_p(m) = 1 \text{ for every } m < p.(1)✦

A number pp is accepted for Δ\Delta, written αΔ(p)=1\alpha_\Delta(p) = 1, when Δ+1<p\Delta + 1 < p and τ(p)=1\tau(p) = 1.✦ The search range for Δ\Delta is the set of numbers below 2(Δ+1)+12(\Delta + 1) + 1✦, and the search for Δ\Delta is the bounded search of αΔ\alpha_\Delta over it: sΔ=search2(Δ+1)+1(αΔ).s_\Delta = \mathrm{search}_{2(\Delta + 1) + 1}(\alpha_\Delta).(2)

A prime modulus is a prime number pp✦, and its field is the field ℤp\mathbb{Z}_p of residues modulo pp✦; a residue is written as its representative vv with 0≤v<p0 \le v < p. The chosen prime modulus for Δ\Delta is the prime pΔ=sΔp_\Delta = s_\Delta.✦

Stack Machines and Space

A read-only tape holds a word ww between a left endmarker ⊢\vdash at position 00 and a right endmarker ⊣\dashv, and a head on the tape stands at one position and reads the mark there.✦ The mark a head reads is ⊢\vdash at position 00, the letter of ww at index pp, counted from 00, at position p+1p + 1, and ⊣\dashv past the last letter.✦ A head direction is a left move LL, no move NN or a right move RR✦; a head moves one position in its direction, never to the left of ⊢\vdash and never past ⊣\dashv.✦

The inputs of a stack machine are a public input, a word over an alphabet XX, and for each jj in a set JJ 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 00✦, and an input head advance gives every head a direction, NN unless it says otherwise.✦

A stack machine MM with these inputs, stacks of bits indexed by a finite set KK and outputs in a set YY 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 YY 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 cc is the passage to the configuration obtained by consulting the table at cc 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 BB is a deterministic halting run, a sequence of steps from a configuration ss to a configuration tt at which the machine halts with an output yy, every stack holding at most BB bits at every configuration from ss to tt.✦ An execution from a store ss to a store tt is a run from the start state with store ss that halts with store tt.✦

Let II be a set of indices with space bounds SiS_i. A stack computation in space SS on inputs xix_i from stores aia_i to stores bib_i with outputs yiy_i is a stack machine whose stacks are those of the stores together with finitely many extra stacks, together with a constant cc, such that for every ii the machine on xix_i has an execution in space c(Si+1)c(S_i + 1) from aia_i, the extra stacks empty, to bib_i, the extra stacks empty again, with output yiy_i.✦ The store of a number nn has every head at home and one stack holding the binary digits of nn without leading zeros, least significant on top.✦

For public inputs xix_i and families aia_i and bib_i of numbers, bb is computable from aa in space SS, written a→Sba \xrightarrow{S} b, when there is a stack computation in space SS on the public inputs xix_i, with no argument tapes, from the store of aia_i to the store of bib_i.✦ A family is written without its index, as in a→Sτ(b)a \xrightarrow{S} \tau(b) for the family τ(bi)\tau(b_i), and a family of residues stands for the family of their representatives.

For a family bb of numbers, the index pairs below bb are the pairs (i,j)(i, j) with i∈Ii \in I and j<bij < b_i, the pair (i,j)(i, j) taking the public input xix_i and the space bound SiS_i.✦ A family uiju_{ij} on these pairs is computable from aa and the index when e→Sue \xrightarrow{S} u for every family ee on the pairs with e→Sae \xrightarrow{S} a and e→Sje \xrightarrow{S} j, where aa and jj stand for the families aia_i and jj on the pairs.

The Claim

Theorem 1. Let pp and Δ\Delta be natural numbers. The trial-division test accepts exactly the primes, τ(p)=1⇔p is prime,\tau(p) = 1 \iff p \text{ is prime},(3)✦ the search for Δ\Delta ends inside its range at an accepted number, sΔ<2(Δ+1)+1andαΔ(sΔ)=1,s_\Delta < 2(\Delta + 1) + 1 \quad\text{and}\quad \alpha_\Delta(s_\Delta) = 1,(4)✦ and the chosen prime modulus lies above Δ+1\Delta + 1 and below the end of the range: Δ+1<pΔ,\Delta + 1 < p_\Delta,(5)✦ pΔ<2(Δ+1)+1.p_\Delta < 2(\Delta + 1) + 1.(6)✦

Let xix_i be public inputs and SiS_i space bounds for the indices ii in a set II, and let aa, bb and Δ\Delta be families of numbers. If a→Sba \xrightarrow{S} b, then a→Sτ(b),a \xrightarrow{S} \tau(b),(7)✦ and if a→SΔa \xrightarrow{S} \Delta, then a→SpΔ.a \xrightarrow{S} p_\Delta.(8)✦ Let PiP_i be prime moduli with a→SPa \xrightarrow{S} P. If viv_i and wiw_i are residues in ℤPi\mathbb{Z}_{P_i} with a→Sva \xrightarrow{S} v and a→Swa \xrightarrow{S} w, then a→Svw.a \xrightarrow{S} v w.(9)✦ If a→Sba \xrightarrow{S} b and the residues uiju_{ij} in ℤPi\mathbb{Z}_{P_i}, for j<bij < b_i, form a family computable from aa and the index, then a→S∑j<biuij,a \xrightarrow{S} \sum_{j < b_i} u_{ij},(10)✦ a→S∏j<biuij.a \xrightarrow{S} \prod_{j < b_i} u_{ij}.(11)✦

In the paper, the result reads: given a time bound TT and an integer Δ≥1\Delta \ge 1 bounded by a polynomial in TT, one can construct uniformly a field FF of characteristic two with |F|>Δ|F| > \Delta, whose elements have O(Log⁡T)O(\operatorname{Log} T) bits and whose description, enumeration, arithmetic and inversion of nonzero elements need space (Log⁡T)O(1)(\operatorname{Log} T)^{O(1)}, where Log⁡T=log⁡2(T+2)\operatorname{Log} T = \log_2(T + 2). The library’s field for Δ\Delta is the prime field ℤpΔ\mathbb{Z}_{p_\Delta} in place of a field of characteristic two.

What Is Checked

The claim is stated over the trial-division test τ\tau with its divisor check, the bounded search sΔs_\Delta for accepted numbers and the chosen prime modulus pΔp_\Delta, the fields ℤp\mathbb{Z}_p of prime moduli, and computability in space SS by stack machines whose stacks hold at most c(Si+1)c(S_i + 1) bits.