OctoInformBeta

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

Lemma 2.1: On oriented graphs with mm edges, bounded kernels with bilinear discrepancy at most δ\delta have error at most mδm\delta

Strict-square constraints admit graph counting bounds.

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

A directed graph can prescribe strict-square constraints on a family of independent uniform field elements: the difference along each directed edge must be a nonzero square. An oriented graph G=(W,E)G=(W,E) is a graph with vertex set WW and edge set E⊆W×WE\subseteq W\times W, with no loops and with at most one directed edge on each unordered pair of distinct vertices. Let WW be finite and write m=|E|m=|E|.

For a field FF, the nonzero square indicator AF:F→ℝA_F:F\to\mathbb R is the function in (1). AF(x)={1,x≠0andx=t2for some t∈F,0,otherwise.A_F(x)= \begin{cases} 1,& x\ne0\ \text{and}\ x=t^2\ \text{for some }t\in F,\\ 0,& \text{otherwise}. \end{cases}(1)✦ For an odd prime pp, write Ap=A𝔽pA_p=A_{\mathbb F_p} and let δp\delta_p be the error parameter in (2). δp=p+12p.\delta_p=\frac{\sqrt p+1}{2p}.(2)

Bounded Kernels

Let XX be a finite nonempty set. A bounded kernel A:X×X→ℝA:X\times X\to\mathbb R is a function with 0≤A(x,y)≤10\le A(x,y)\le1 for all x,y∈Xx,y\in X. For δ≥0\delta\ge0, the bilinear discrepancy condition on AA is (3), required for every pair of real functions f,g:X→ℝf,g:X\to\mathbb R with |f(x)|,|g(x)|≤1|f(x)|,|g(x)|\le1 for all x∈Xx\in X; here 𝔼\mathbb E denotes the uniform probability average. |𝔼x∈X𝔼y∈Xf(x)g(y)(A(x,y)−12)|≤δ.\left|\mathbb E_{x\in X}\mathbb E_{y\in X} f(x)g(y)\left(A(x,y)-\frac12\right)\right|\le\delta.(3) An average over XWX^W chooses the coordinates zwz_w independently and uniformly in XX; an empty edge product has value 11.

The Claim

Theorem 1. Let G=(W,E)G=(W,E) be a finite oriented graph with mm edges. Let XX be a finite nonempty set, and let A:X×X→ℝA:X\times X\to\mathbb R be a bounded kernel satisfying (3) for some δ≥0\delta\ge0. Then |𝔼z∈XW∏(u,v)∈EA(zu,zv)−2−m|≤mδ.\left|\mathbb E_{z\in X^W} \prod_{(u,v)\in E}A(z_u,z_v)-2^{-m}\right|\le m\delta.(4)✦ For an odd prime pp, the nonzero square indicator satisfies |𝔼z∈𝔽pW∏(u,v)∈EAp(zv−zu)−2−m|≤mp+12p.\left|\mathbb E_{z\in\mathbb F_p^W} \prod_{(u,v)\in E}A_p(z_v-z_u)-2^{-m}\right| \le m\frac{\sqrt p+1}{2p}.(5)✦

In the paper, the result reads: for an odd prime pp and a finite directed graph G=(W,E)G=(W,E) without loops and with at most one edge on each unordered pair, independent uniform zw∈𝔽pz_w\in\mathbb F_p satisfy |𝔼z∏(u,v)∈EAp(zv−zu)−2−m|≤mδp\left|\mathbb E_z\prod_{(u,v)\in E}A_p(z_v-z_u)-2^{-m}\right|\le m\delta_p, including the empty graph.

What Is Checked

The count in (4) is stated over finite oriented graphs and bounded real kernels on finite nonempty sets subject to (3); the count in (5) is stated over odd prime fields with the nonzero square indicator (1) and the error parameter (2).