OctoInformBeta

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

Lemma 4 [Top-coefficient extraction]: For degree dd with d+1<pd+1<p the weights are −up−1−d-u^{p-1-d}; along a line a+xwa+xw, word extensions have top coefficient their value at ww

Weighted sums over a prime field extract top coefficients.

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

Let pp be a prime and 𝔽p\mathbb{F}_p the field of integers modulo pp. For a natural number dd, Lagrange interpolation recovers a polynomial of degree at most dd over 𝔽p\mathbb{F}_p from its values at d+1d+1 points, and its top coefficient, the coefficient of XdX^d, is then one linear combination of those values. Here the sample points are all pp elements of the field, and the weights depend only on dd and on the point.

The functions sampled come from low-degree extensions of tables indexed by dd-bit words. Such an extension is a polynomial function on vectors over 𝔽p\mathbb{F}_p; restricted to the line through a point aa in a direction ww, it becomes a function of one parameter x∈𝔽px\in\mathbb{F}_p, and the question is what its top coefficient is.

Weights and Top Coefficients

For a natural number dd, the interpolation weight of degree dd at a field element u∈𝔽pu\in\mathbb{F}_p is ωd(u)=−up−1−d.\omega_d(u) = -u^{p-1-d}.(1)✦

A function f:𝔽p→𝔽pf\colon\mathbb{F}_p\to\mathbb{F}_p has degree at most dd with top coefficient v∈𝔽pv\in\mathbb{F}_p if there are g0,…,gd−1∈𝔽pg_0,\dots,g_{d-1}\in\mathbb{F}_p such that ff agrees at every point of 𝔽p\mathbb{F}_p with the polynomial g=vXd+∑j<dgjXjg = vX^d + \sum_{j<d} g_jX^j: f(x)=vxd+∑j<dgjxjfor every x∈𝔽p.f(x) = v\,x^d + \sum_{j<d} g_j\,x^j \qquad\text{for every } x\in\mathbb{F}_p.(2)✦ For any polynomial g∈𝔽p[X]g\in\mathbb{F}_p[X], gjg_j denotes its coefficient of XjX^j.

Word Extensions on Lines

A coordinate vector over 𝔽p\mathbb{F}_p is a sequence v=(v0,v1,v2,…)v=(v_0,v_1,v_2,\dots) of elements of 𝔽p\mathbb{F}_p.✦ For coordinate vectors aa and ww, the line through aa in direction ww is the map sending x∈𝔽px\in\mathbb{F}_p to the vector a+xwa+xw with coordinates (a+xw)i=ai+xwi(a+xw)_i = a_i + x\,w_i.✦

A natural number uu is read as a binary word, least significant digit first: its digit at place ii is ui=⌊u/2i⌋mod⁡2u_i = \lfloor u/2^i\rfloor \bmod 2, the case m=2m=2 of the base-mm digit ⌊u/mi⌋mod⁡m\lfloor u/m^i\rfloor \bmod m.✦ Fix a width dd. Coordinate dd is the augmenting coordinate, which holds 11 when a dd-bit word is read as a vector. The coordinate choice factor ci(v)c_i(v) of uu at place ii and the Boolean basis polynomial χu\chi_u of uu, at a coordinate vector vv, are ci(v)={viif ui=1,vd−viif ui=0,χu(v)=∏i=0d−1ci(v).c_i(v) = \begin{cases} v_i & \text{if } u_i = 1,\\ v_d - v_i & \text{if } u_i = 0,\end{cases} \qquad \chi_u(v) = \prod_{i=0}^{d-1} c_i(v).(3)

The multilinear word extension of a table tt of elements of 𝔽p\mathbb{F}_p indexed by dd-bit words is the function on coordinate vectors tˆ(v)=∑u=02d−1χu(v)t(u).\hat t(v) = \sum_{u=0}^{2^d-1} \chi_u(v)\,t(u).(4)✦ The two-word extension of a table qq indexed by pairs of dd-bit words, at coordinate vectors vv and ww, is the word extension at vv of the table sending uu to the word extension of q(u,⋅)q(u,\cdot) at ww: qˆ(v,w)=∑u=02d−1χu(v)∑u′=02d−1χu′(w)q(u,u′).\hat q(v,w) = \sum_{u=0}^{2^d-1} \chi_u(v) \sum_{u'=0}^{2^d-1} \chi_{u'}(w)\,q(u,u').(5)✦

The Claim

Theorem 1 (Top-coefficient extraction). Let pp be a prime. The (p−1)(p-1)st powers of the elements of 𝔽p\mathbb{F}_p sum to −1-1: ∑x∈𝔽pxp−1=−1.\sum_{x\in\mathbb{F}_p} x^{p-1} = -1.(6)✦ Let dd be a natural number with d+1<pd+1<p. For every natural number i≤di\le d, ∑x∈𝔽pωd(x)xi={1if i=d,0if i<d;\sum_{x\in\mathbb{F}_p} \omega_d(x)\,x^i = \begin{cases} 1 & \text{if } i = d,\\ 0 & \text{if } i < d;\end{cases}(7)✦ for every polynomial g∈𝔽p[X]g\in\mathbb{F}_p[X] of degree at most dd, ∑x∈𝔽pωd(x)g(x)=gd;\sum_{x\in\mathbb{F}_p} \omega_d(x)\,g(x) = g_d;(8)✦ and for every function f:𝔽p→𝔽pf\colon\mathbb{F}_p\to\mathbb{F}_p of degree at most dd with top coefficient vv, ∑x∈𝔽pωd(x)f(x)=v.\sum_{x\in\mathbb{F}_p} \omega_d(x)\,f(x) = v.(9)✦ Let dd be a natural number, aa, vv, ww coordinate vectors, uu a natural number, tt a table indexed by dd-bit words and qq a table indexed by pairs of dd-bit words. Then there are g0,…,gd−1∈𝔽pg_0,\dots,g_{d-1}\in\mathbb{F}_p, not depending on xx, such that for every x∈𝔽px\in\mathbb{F}_p χu(a+xw)=χu(w)xd+∑j<dgjxj,\chi_u(a+xw) = \chi_u(w)\,x^d + \sum_{j<d} g_j\,x^j,(10)✦ tˆ(a+xw)=tˆ(w)xd+∑j<dgjxj,\hat t(a+xw) = \hat t(w)\,x^d + \sum_{j<d} g_j\,x^j,(11)✦ qˆ(a+xv,w)=qˆ(v,w)xd+∑j<dgjxj,\hat q(a+xv,\,w) = \hat q(v,w)\,x^d + \sum_{j<d} g_j\,x^j,(12)✦ qˆ(v,a+xw)=qˆ(v,w)xd+∑j<dgjxj.\hat q(v,\,a+xw) = \hat q(v,w)\,x^d + \sum_{j<d} g_j\,x^j.(13)✦

In the paper, the result reads: for a field 𝔽\mathbb{F} and 0≤L<|𝔽|0\le L<|\mathbb{F}|, any L+1L+1 distinct points SLS_L of 𝔽\mathbb{F}, with weights ωL(s)=(∏s′∈SL,s′≠s(s−s′))−1\omega_L(s)=\bigl(\prod_{s'\in S_L,\,s'\ne s}(s-s')\bigr)^{-1}, give the coefficient of XLX^L in every polynomial PP of degree at most LL as ∑s∈SLωL(s)P(s)\sum_{s\in S_L}\omega_L(s)P(s), and ∑s∈SLωL(s)Q(a+sw)=Q(w)\sum_{s\in S_L}\omega_L(s)\,Q(a+sw)=Q(w) for every QQ homogeneous of degree LL and all points aa and ww; with SLS_L the first L+1L+1 field elements, the points and weights are enumerable in space polylogarithmic in the time bound TT, and the paper’s LL is the page’s dd.

Here the sample set is all of 𝔽p\mathbb{F}_p, with the weights ωd\omega_d, and the forms QQ are the basis polynomials and the word extensions.

What Is Checked

The claim is stated over the field 𝔽p\mathbb{F}_p of integers modulo a prime pp, the interpolation weights ωd\omega_d, functions on 𝔽p\mathbb{F}_p of degree at most dd with a given top coefficient, the lines a+xwa+xw through coordinate vectors, and the Boolean basis polynomials χu\chi_u with the word extensions tˆ\hat t and qˆ\hat q built from them.