OctoInformBeta

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

Proposition 3.5 [A symmetric kernel with a strict deficit]: A finite probability space Ω\Omega and a symmetric kernel U:Ω×Ω→[0,1]U\colon\Omega\times\Omega\to[0,1] of mean μ>0\mu>0 with t(H,U)<μ66t(H,U)<\mu^{66}, HH the point-face incidence graph

A symmetric kernel that falls strictly below Sidorenko’s bound.

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

Take the 1313 points P={0,…,12}P=\{0,\dots,12\} and the 2222 faces F={0,…,21}F=\{0,\dots,21\}, each face a triple of points. Listed from face 00 to face 2121, each with its points in increasing order, the faces are (0,1,3),(0,1,9),(0,2,3),(0,2,9),(1,3,10),(1,7,10),(1,7,12),(1,9,12),(2,3,4),(2,4,9),(3,4,11),(3,10,11),(4,8,9),(4,8,11),(5,6,7),(5,6,11),(5,7,10),(5,10,11),(6,7,12),(6,8,11),(6,8,12),(8,9,12).\begin{aligned} &(0,1,3),\ (0,1,9),\ (0,2,3),\ (0,2,9),\ (1,3,10),\ (1,7,10),\ (1,7,12),\ (1,9,12),\\ &(2,3,4),\ (2,4,9),\ (3,4,11),\ (3,10,11),\ (4,8,9),\ (4,8,11),\ (5,6,7),\\ &(5,6,11),\ (5,7,10),\ (5,10,11),\ (6,7,12),\ (6,8,11),\ (6,8,12),\ (8,9,12). \end{aligned}(1)✦ The graph HH is their incidence graph: its vertex set V(H)=P⊔FV(H)=P\sqcup F has 3535 vertices, and each face is joined to its three points. A corner of HH is a pair (j,s)(j,s) of a face j∈Fj\in F and a slot s∈{0,1,2}s\in\{0,1,2\}.✦ The point v(k)∈Pv(k)\in P of a corner k=(j,s)k=(j,s) is the entry in slot ss of face jj in the table (1).✦ The 6666 corners are the edges of HH, one for each incidence between a point and a face.

The question is whether HH satisfies Sidorenko’s conjecture: whether t(H,W)≥t(K2,W)66t(H,W)\ge t(K_2,W)^{66} for every graphon WW.

Finite Laws and the Bipartite Moment

A finite probability law π\pi on a finite set AA is a function π:A→ℝ\pi\colon A\to\mathbb{R} with π(a)≥0\pi(a)\ge 0 for every a∈Aa\in A and ∑a∈Aπ(a)=1\sum_{a\in A}\pi(a)=1.✦ The expectation of a function f:A→ℝf\colon A\to\mathbb{R} under π\pi is 𝔼a∼πf(a)=∑a∈Aπ(a)f(a).\mathbb{E}_{a\sim\pi}f(a)=\sum_{a\in A}\pi(a)f(a).(2)✦

The product law ⨂i∈Ipi\bigotimes_{i\in I}p_i of finite probability laws pip_i on AA, one for each ii in a finite set II, is the finite probability law on the maps x:I→Ax\colon I\to A whose weight at xx is ∏i∈Ipi(xi)\prod_{i\in I}p_i(x_i).✦ When every pip_i is π\pi, the product law is written π⊗I\pi^{\otimes I}.

Let π\pi and ν\nu be finite probability laws on finite sets XX and YY, and let W:X×Y→ℝW\colon X\times Y\to\mathbb{R} be a bipartite kernel. The kernel mean of WW is μπ,ν(W)=𝔼x∼π𝔼y∼νW(x,y).\mu_{\pi,\nu}(W)=\mathbb{E}_{x\sim\pi}\,\mathbb{E}_{y\sim\nu}\,W(x,y).(3)✦ The bipartite moment of WW, the homomorphism density of HH in WW with the points of HH sent to XX and its faces to YY, is tπ,ν(H,W)=𝔼x∼π⊗P𝔼y∼ν⊗F∏k=(j,s)W(xv(k),yj).t_{\pi,\nu}(H,W)=\mathbb{E}_{x\sim\pi^{\otimes P}}\,\mathbb{E}_{y\sim\nu^{\otimes F}} \prod_{k=(j,s)}W\bigl(x_{v(k)},y_j\bigr).(4)

The Claim

Theorem 1. There is a symmetric counter kernel✦: a nonempty finite set Ω\Omega, a finite probability law π\pi on Ω\Omega and a function U:Ω×Ω→[0,1]U\colon\Omega\times\Omega\to[0,1] with U(x,y)=U(y,x)U(x,y)=U(y,x) for all x,y∈Ωx,y\in\Omega, whose kernel mean μ=μπ,π(U)\mu=\mu_{\pi,\pi}(U) is positive and whose bipartite moment satisfies tπ,π(H,U)<μ66.t_{\pi,\pi}(H,U)<\mu^{66}.(5)✦ For every finite probability law π\pi on a finite set AA and every function U:A×A→ℝU\colon A\times A\to\mathbb{R}, drawing all 3535 vertices of HH independently from π\pi gives the bipartite moment: 𝔼z∼π⊗V(H)∏k=(j,s)U(zv(k),zj)=tπ,π(H,U),\mathbb{E}_{z\sim\pi^{\otimes V(H)}}\prod_{k=(j,s)}U\bigl(z_{v(k)},z_j\bigr) =t_{\pi,\pi}(H,U),(6)✦ where zz assigns a point of AA to each vertex of HH, zv(k)z_{v(k)} to the point v(k)∈Pv(k)\in P and zjz_j to the face j∈Fj\in F.

In the paper, the result reads: assuming Lemma 3.1, there is a symmetric kernel U:Ω×Ω→[0,1]U\colon\Omega\times\Omega\to[0,1] on a finite probability space Ω\Omega with mean μ>0\mu>0 such that t(H,U)<μ66t(H,U)<\mu^{66}, where t(H,U)t(H,U) stands for the left side of (6) and μ\mu for μπ,π(U)\mu_{\pi,\pi}(U).

What Is Checked

The claims (5) and (6) are stated over symmetric counter kernels, over finite probability laws on finite sets with their expectations (2) and product laws, and over the kernel mean (3) and the bipartite moment (4) of the incidence graph HH of the faces (1).