OctoInformBeta

OpenAI preprint, September 2026 · §3. Constructing a negative kernel correlation · §3

§3 (setting): activation laws, the kernel W_q and the coefficients C_A: The typed kernel averages products of rank kernels over a random signed set of coordinates and has mean one for r≥1r\ge 1 and odd qq

Activation laws, their matrix kernel and their 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

The graph HH of this construction is bipartite. On one side are 1313 points 0,…,120,\dots,12, on the other 2222 faces 0,…,210,\dots,21, each face a triple of points, and a point is joined to every face that contains it. Each of the 6666 edges is a corner k=(j,s)k=(j,s): the face jj together with a slot s∈{0,1,2}s\in\{0,1,2\} that names one of its points.✦ A bipartite kernel is a real function WW on X×YX\times Y, where the finite sets XX and YY carry probability laws μ\mu and λ\lambda, and a homomorphism of HH into it sends points to XX and faces to YY. Sidorenko’s conjecture for HH asserts that in every nonnegative bipartite kernel the homomorphism density of HH is at least the 6666th power of the mean of WW.

The kernels of this section live on symmetric matrices over a finite field. Each vertex of HH is mapped to a type, an element of a finite set of types, together with a family of symmetric matrices indexed by a finite set of coordinates, and for each edge a random signed set of coordinates, drawn from a law that depends on the types at its two ends, selects the coordinates at which the two families are compared. A second construction combines the moments of these laws along the corners of HH into a coefficient CAC_A.

Laws and Corners

A finite probability law pp on a finite set AA is a function p:A→ℝp\colon A\to\mathbb R with nonnegative values summing to 11.✦ The expectation of a real function ff on AA under pp is 𝔼a∼pf(a)=∑a∈Ap(a)f(a).\mathbb E_{a\sim p}f(a)=\sum_{a\in A}p(a)f(a).(1)✦ The uniform law on a nonempty finite set AA gives every point the weight 1/|A|1/|A|.✦ The product p⊗p′p\otimes p' of laws pp on AA and p′p' on A′A' is the law on A×A′A\times A' with weight p(a)p′(a′)p(a)p'(a') at (a,a′)(a,a').✦ The product law of a family of laws pip_i on AA, indexed by a finite set II, is the law on maps x:I→Ax\colon I\to A with weight ∏i∈Ipi(xi)\prod_{i\in I}p_i(x_i), under which the coordinates xix_i are independent with laws pip_i; when every pip_i is pp and II has nn elements it is written p⊗np^{\otimes n}.✦

A fixed table lists the points v0<v1<v2v_0<v_1<v_2 of each face jj in slots 0,1,20,1,2✦, and the point v(k)v(k) of a corner k=(j,s)k=(j,s) is the point in slot ss.✦ The sides of the faces are 3333 point pairs, and a second table lists the sides of each face in the order {v0,v1}\{v_0,v_1\}, {v0,v2}\{v_0,v_2\}, {v1,v2}\{v_1,v_2\}.✦ At a corner k=(j,s)k=(j,s) two sides of the face jj meet in v(k)v(k): e(k)e(k) is the earlier of them in this order✦ and f(k)f(k) the later.✦

Signed Rank Layers

Let qq be an odd prime, 𝔽q\mathbb F_q the field with qq elements, and χ\chi its quadratic character. For D≥0D\ge 0, SDS_D is the subspace of symmetric matrices in the space of D×DD\times D matrices over 𝔽q\mathbb F_q.✦ The radical rad⁡B\operatorname{rad}B of a symmetric bilinear form BB on a finite-dimensional space VV over 𝔽q\mathbb F_q is the subspace of vectors u∈Vu\in V with B(u,v)=0B(u,v)=0 for all v∈Vv\in V, and BB induces on V/rad⁡BV/\operatorname{rad}B the nondegenerate radical quotient form B‾(u‾,v‾)=B(u,v)\bar B(\bar u,\bar v)=B(u,v).✦ The discriminant sign of BB is χ(det⁡G)\chi(\det G), with GG the Gram matrix of B‾\bar B in a basis of V/rad⁡BV/\operatorname{rad}B, and it equals 11 when BB has rank zero.✦ The sign sgn⁡Z\operatorname{sgn}Z of a matrix Z∈SDZ\in S_D is the discriminant sign of the form (u,v)↦u𝖳Zv(u,v)\mapsto u^{\mathsf T}Zv on 𝔽qD\mathbb F_q^D.✦

The signed rank layer Ls,εL_{s,\varepsilon} of rank ss and sign ε\varepsilon is the set of matrices in SDS_D of rank ss and sign ε\varepsilon✦, and its layer mass is ms,ε=|Ls,ε|/|SD|m_{s,\varepsilon}=|L_{s,\varepsilon}|/|S_D|.✦ The rank kernel Ks,εK_{s,\varepsilon} is the real function on SDS_D Ks,ε(Z)=𝟏[Z∈Ls,ε]ms,ε.K_{s,\varepsilon}(Z)=\frac{\mathbf 1[Z\in L_{s,\varepsilon}]}{m_{s,\varepsilon}}.(2)✦

The Claim

Definition 1. Fix a finite set 𝒦\mathcal K of coordinates and a natural number rr. An activation is a pair (S,ξ)(S,\xi) of a subset S⊆𝒦S\subseteq\mathcal K and a sign vector ξ∈{1,−1}𝒦\xi\in\{1,-1\}^{\mathcal K}✦, and an activation law is a finite probability law on activations. For α⊆𝒦\alpha\subseteq\mathcal K write ξα=∏κ∈αξκ\xi^\alpha=\prod_{\kappa\in\alpha}\xi_\kappa✦; the activated monomial φα\varphi_\alpha is the function on activations φα(S,ξ)=𝟏[α⊆S]ξα,\varphi_\alpha(S,\xi)=\mathbf 1[\alpha\subseteq S]\,\xi^\alpha,(3)✦ and the moment function ApA_p of an activation law pp is the function on pairs of subsets of 𝒦\mathcal K Ap(α,β)=𝔼(S,ξ)∼pφα(S,ξ)φβ(S,ξ).A_p(\alpha,\beta)=\mathbb E_{(S,\xi)\sim p}\,\varphi_\alpha(S,\xi)\,\varphi_\beta(S,\xi).(4)✦ The sample kernel wS,ξw_{S,\xi} of an activation (S,ξ)(S,\xi) is the function on pairs of families x=(xκ)κ∈𝒦x=(x^\kappa)_{\kappa\in\mathcal K} and y=(yκ)κ∈𝒦y=(y^\kappa)_{\kappa\in\mathcal K} in S2rS_{2r} given by the product of rank kernels of rank rr on S2rS_{2r} wS,ξ(x,y)=∏κ∈SKr,ξκ(xκ−yκ),w_{S,\xi}(x,y)=\prod_{\kappa\in S}K_{r,\xi_\kappa}(x^\kappa-y^\kappa),(5)✦ and the activation kernel of an activation law pp is its expectation Wp(x,y)=𝔼(S,ξ)∼pwS,ξ(x,y)W_p(x,y)=\mathbb E_{(S,\xi)\sim p}\,w_{S,\xi}(x,y).✦

Let π\pi and ν\nu be laws on finite sets 𝒜\mathcal A and ℬ\mathcal B of types, and let pp assign an activation law pabp_{ab} to each pair a∈𝒜a\in\mathcal A, b∈ℬb\in\mathcal B. The typed matrix laws are π⊗u\pi\otimes u on 𝒜×S2r𝒦\mathcal A\times S_{2r}^{\mathcal K} and ν⊗u\nu\otimes u on ℬ×S2r𝒦\mathcal B\times S_{2r}^{\mathcal K}, where uu is the uniform law on S2r𝒦S_{2r}^{\mathcal K}✦, and the typed kernel is the function Wq((a,x),(b,y))=Wpab(x,y)W_q((a,x),(b,y))=W_{p_{ab}}(x,y) on their product.✦ The kernel mean of a real function WW on X×YX\times Y under laws μ\mu on XX and λ\lambda on YY is 𝔼x∼μ𝔼y∼λW(x,y)\mathbb E_{x\sim\mu}\,\mathbb E_{y\sim\lambda}\,W(x,y).✦ If r≥1r\ge 1 and qq is odd, then for all π\pi, ν\nu and pp the typed kernel has kernel mean one under the typed matrix laws, 𝔼(a,x)∼π⊗u𝔼(b,y)∼ν⊗uWq((a,x),(b,y))=1.\mathbb E_{(a,x)\sim\pi\otimes u}\,\mathbb E_{(b,y)\sim\nu\otimes u}\,W_q((a,x),(b,y))=1.(6)✦

A corner table AA assigns to each corner kk a real function AkA_k on pairs of subsets of 𝒦\mathcal K, and a labeling α\alpha assigns a subset αe⊆𝒦\alpha_e\subseteq\mathcal K to each point pair ee. The label product of AA at α\alpha is the product over the 6666 corners ΠA(α)=∏kAk(αe(k),αf(k)),\Pi_A(\alpha)=\prod_{k}A_k(\alpha_{e(k)},\alpha_{f(k)}),(7)✦ and the active coefficient of AA is the sum over the labelings by nonempty sets CA=∑α:αe≠⌀ for every eΠA(α).C_A=\sum_{\alpha:\ \alpha_e\neq\varnothing\text{ for every }e}\Pi_A(\alpha).(8)✦ For type maps aa from the points to 𝒜\mathcal A and bb from the faces to ℬ\mathcal B, the typed coefficient is the active coefficient of the corner table whose entry at k=(j,s)k=(j,s) is the moment function of the activation law at the types of v(k)v(k) and jj: Cp(a,b)=CA,Ak=Apa(v(k))b(j).C_p(a,b)=C_A,\qquad A_k=A_{p_{a(v(k))\,b(j)}}.(9)✦ The type map law is the law of independent types, π\pi at each point and ν\nu at each face, τπ,ν=π⊗13⊗ν⊗22,\tau_{\pi,\nu}=\pi^{\otimes 13}\otimes\nu^{\otimes 22},(10)✦ and the averaged coefficient is the mean of the typed coefficient under it, C‾p=𝔼(a,b)∼τπ,νCp(a,b).\bar C_p=\mathbb E_{(a,b)\sim\tau_{\pi,\nu}}\,C_p(a,b).(11)✦ The bipartite moment of a real function WW on X×YX\times Y under laws μ\mu on XX and λ\lambda on YY is the homomorphism density of HH in WW, t(H,W)=𝔼x∼μ⊗13𝔼y∼λ⊗22∏k=(j,s)W(xv(k),yj).t(H,W)=\mathbb E_{x\sim\mu^{\otimes 13}}\,\mathbb E_{y\sim\lambda^{\otimes 22}} \prod_{k=(j,s)}W(x_{v(k)},y_j).(12)✦ Here x=(xi)x=(x_i) is a family of values in XX indexed by the points ii, and y=(yj)y=(y_j) a family of values in YY indexed by the faces jj.

In the paper, the result reads: types a∈𝒜a\in\mathcal A and b∈ℬb\in\mathcal B have laws π\pi and ν\nu, an activation law at (a,b)(a,b) is the law of a set S⊆𝒦S\subseteq\mathcal K with signs ξ\xi, Wq((a,x),(b,y))=𝔼∏κ∈SKr,ξκ(xκ−yκ)W_q((a,x),(b,y))=\mathbb E\prod_{\kappa\in S}K_{r,\xi_\kappa}(x^\kappa-y^\kappa), φα(S,ξ)=𝟏[α⊆S]ξα\varphi_\alpha(S,\xi)=\mathbf 1[\alpha\subseteq S]\,\xi^\alpha, Apab(α,β)=𝔼φαφβA_{p_{ab}}(\alpha,\beta)=\mathbb E\,\varphi_\alpha\varphi_\beta with the zero-moment condition 𝔼φα=0\mathbb E\,\varphi_\alpha=0 for nonempty α\alpha, Cp(a,b)=∑α∏k=(j,s)Apa(v(k))b(j)(αe(k),αf(k))C_p(a,b)=\sum_\alpha\prod_{k=(j,s)}A_{p_{a(v(k))\,b(j)}}(\alpha_{e(k)},\alpha_{f(k)}) over the labelings α\alpha of the point pairs by nonempty sets, and t(H,W)=𝔼∏k=(j,s)W(xv(k),yj)t(H,W)=\mathbb E\prod_{k=(j,s)}W(x_{v(k)},y_j), where ApabA_{p_{ab}}, Cp(a,b)C_p(a,b) and t(H,W)t(H,W) are the paper’s AabA_{ab}, CA(a,b)C_A(a,b) and tI,J(W)t_{I,J}(W).

What Is Checked

The definitions are stated over finite probability laws on finite sets and over two pieces of fixed structure: the rank kernels (2) on symmetric 2r×2r2r\times 2r matrices over 𝔽q\mathbb F_q, built from rank and discriminant sign, and the 6666 corners of HH with their points v(k)v(k) and sides e(k)e(k), f(k)f(k).