OctoInformBeta

OpenAI preprint, September 2026 ยท Section 2. Finite-field square constraints

Lemma 2.2: Bilinear and squared normalized L2L^2 bounds for constraints between two finite lists

Oriented square constraints have small centered kernels.

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

Square conditions couple coordinates in two finite lists, with the direction of each constrained difference prescribed separately. Let pp be an odd prime and let I,JI,J be finite index sets. Write xโˆˆ๐‘ญpIx\in\mathbf F_p^I and yโˆˆ๐‘ญpJy\in\mathbf F_p^J for the two lists.

For a field FF, the nonzero square indicator AF:Fโ†’๐‘นA_F:F\to\mathbf R is the function in (1): AF(t)={1,tโ‰ 0 and t=s2 for some sโˆˆF,0,otherwise.A_F(t)= \begin{cases} 1,&t\ne 0\text{ and }t=s^2\text{ for some }s\in F,\\ 0,&\text{otherwise}. \end{cases}(1)โœฆ Write Ap=A๐‘ญpA_p=A_{\mathbf F_p}.

An oriented set of cross pairs between II and JJ is a pair (E,d)(E,d) consisting of a set EโІIร—JE\subseteq I\times J and a function d:Iร—Jโ†’{+,โˆ’}d:I\times J\to\{+,-\} prescribing the direction at each pair. Put m=|E|m=|E|. The square-constraint kernel K:๐‘ญpIร—๐‘ญpJโ†’๐‘นK:\mathbf F_p^I\times\mathbf F_p^J\to\mathbf R and its centered kernel LL are defined by (2): K(x,y)=โˆ(i,j)โˆˆE{Ap(yjโˆ’xi),d(i,j)=+,Ap(xiโˆ’yj),d(i,j)=โˆ’,L(x,y)=K(x,y)โˆ’2โˆ’m.\begin{aligned} K(x,y)&=\prod_{(i,j)\in E} \begin{cases} A_p(y_j-x_i),&d(i,j)=+,\\ A_p(x_i-y_j),&d(i,j)=-, \end{cases}\\ L(x,y)&=K(x,y)-2^{-m}. \end{aligned}(2)โœฆ

For a finite index set SS and a real function hh on ๐‘ญpS\mathbf F_p^S, the uniform average ๐”ผzโˆˆ๐‘ญpSh(z)\mathbb E_{z\in\mathbf F_p^S}h(z) and normalized L2L^2 norm โˆฅhโˆฅ2\|h\|_2 are the real numbers given by (3): ๐”ผzโˆˆ๐‘ญpSh(z)=pโˆ’|S|โˆ‘zโˆˆ๐‘ญpSh(z),โˆฅhโˆฅ2=(๐”ผzโˆˆ๐‘ญpSh(z)2)1/2.\mathbb E_{z\in\mathbf F_p^S}h(z) =p^{-|S|}\sum_{z\in\mathbf F_p^S}h(z), \qquad \|h\|_2=\left(\mathbb E_{z\in\mathbf F_p^S}h(z)^2\right)^{1/2}.(3) For a real kernel HH on ๐‘ญpIร—๐‘ญpJ\mathbf F_p^I\times\mathbf F_p^J, write โˆฅHโˆฅop\|H\|_{\mathrm{op}} for the operator norm, with these normalized L2L^2 norms, of the map fโ†ฆ(yโ†ฆ๐”ผxH(x,y)f(x))f\mapsto\bigl(y\mapsto\mathbb E_x H(x,y)f(x)\bigr).

The Claim

Theorem 1. Let pp be an odd prime, let I,JI,J be finite index sets, and let EโІIร—JE\subseteq I\times J be a set of mm pairs with prescribed orientation dd. For real functions f:๐‘ญpIโ†’๐‘นf:\mathbf F_p^I\to\mathbf R and g:๐‘ญpJโ†’๐‘นg:\mathbf F_p^J\to\mathbf R, the centered kernel LL satisfies |๐”ผx๐”ผyf(x)L(x,y)g(y)|โ‰ค(32m)1/4pโˆ’1/8โˆฅfโˆฅ2โˆฅgโˆฅ2\left|\mathbb E_x\mathbb E_y f(x)L(x,y)g(y)\right| \le (32m)^{1/4}p^{-1/8}\|f\|_2\|g\|_2(4)โœฆ and ๐”ผy(๐”ผxf(x)L(x,y))2โ‰ค((32m)1/4pโˆ’1/8)2๐”ผxf(x)2.\mathbb E_y\left(\mathbb E_x f(x)L(x,y)\right)^2 \le \left((32m)^{1/4}p^{-1/8}\right)^2\mathbb E_x f(x)^2.(5)โœฆ

In the paper, the result reads: for an odd prime pp, finite disjoint sets I,JI,J, and a directed graph GG on IโŠ”JI\sqcup J with edge set E(G)E(G) of size mm, all edges crossing between the two lists, with arbitrary directions and at most one edge on each unordered pair, the kernel K(x,y)=โˆ(u,v)โˆˆE(G)Ap(zvโˆ’zu)K(x,y)=\prod_{(u,v)\in E(G)}A_p(z_v-z_u), where zz combines xโˆˆ๐‘ญpIx\in\mathbf F_p^I and yโˆˆ๐‘ญpJy\in\mathbf F_p^J, satisfies โˆฅKโˆ’2โˆ’mโˆฅopโ‰ค(32m)1/4pโˆ’1/8\|K-2^{-m}\|_{\mathrm{op}}\le(32m)^{1/4}p^{-1/8}, with both sides zero when m=0m=0.

What Is Checked

The estimates (4) and (5) are stated over real functions on finite coordinate powers of an odd prime field, with the square-constraint kernel formed from a finite set of cross pairs and a prescribed orientation on each pair.