OctoInformBeta

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

Lemma 3.6 [Transfer to a finite simple host]: A symmetric [0,1][0,1]-valued kernel UU with t(H,U)<(𝔼U)66t(H,U)<(\mathbb{E}U)^{66} gives a graph GG on nn vertices with t(H,G)<p(G)66t(H,G)<p(G)^{66} for all large nn

A kernel counterexample yields finite graph counterexamples.

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 HH be the incidence graph of 13 points and 22 triples of them, a bipartite graph with 35 vertices and 66 edges. A finite simple graph GG whose homomorphism density t(H,G)t(H,G) lies below p(G)66p(G)^{66}, the 66th power of its edge density, is a counterexample to Sidorenko’s conjecture for HH. Suppose a symmetric kernel with values in [0,1][0,1] on a finite probability space fails the same inequality, its HH-density lying below the 66th power of its mean. The question is whether finite graphs then fail it too, and from how many vertices on.

The Graph HH

The points are 0,1,…,120,1,\dots,12, and the faces F0,…,F21F_0,\dots,F_{21} are the following three-element sets of points, in this order: {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 incidence graph HH is the simple graph on the 35 vertices formed by the 13 points and the 22 faces in which a point ii and a face jj are adjacent exactly when they are incident, i∈Fji\in F_j.

A corner k=(j,s)k=(j,s) is a pair of a face jj and a slot s∈{0,1,2}s\in\{0,1,2\}.✦ The three points of each face are listed in increasing order in the slots 0,1,20,1,2, and the point v(k)v(k) of the corner k=(j,s)k=(j,s) is the point of FjF_j in slot ss.✦ There are 66 corners, one for each edge of HH.

Densities

The homomorphism count hom⁡(F,G)\hom(F,G) of a simple graph FF in a simple graph GG, both on finite vertex sets, is the number of maps f:V(F)→V(G)f\colon V(F)\to V(G), injective or not, that send adjacent vertices to adjacent vertices.✦ The homomorphism density of FF in GG is t(F,G)=hom⁡(F,G)|V(G)||V(F)|,t(F,G)=\frac{\hom(F,G)}{|V(G)|^{|V(F)|}},(2)✦ and the edge density of GG is p(G)=2|E(G)||V(G)|2.p(G)=\frac{2|E(G)|}{|V(G)|^{2}}.(3)✦

Finite Probability Laws

A finite probability law π\pi on a finite set AA is an assignment of a weight π(a)≥0\pi(a)\ge 0 to each point aa of AA such that the weights sum to 11.✦ The expectation of a real function ff on AA 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).(4)✦

The point mass δa\delta_a at a point aa of AA is the law on AA with weight 11 at aa and 00 elsewhere.✦ For t∈[0,1]t\in[0,1], the mixture of two laws π\pi and π′\pi' on AA is the law with weights tπ(a)+(1−t)π′(a)t\,\pi(a)+(1-t)\,\pi'(a)✦; the biased coin with bias tt is the law on {0,1}\{0,1\} that mixes δ1\delta_1 and δ0\delta_0 in this way.✦ On a nonempty finite set AA, the uniform law gives every element the weight 1/|A|1/|A|.✦

The product law of finite probability laws πi\pi_i on AA, one for each index ii of a finite set II, is the law on maps x:I→Ax\colon I\to A with weights (⨂i∈Iπi)(x)=∏i∈Iπi(xi),\Bigl(\bigotimes_{i\in I}\pi_i\Bigr)(x)=\prod_{i\in I}\pi_i(x_i),(5)✦ when every πi\pi_i is π\pi it is written π⊗I\pi^{\otimes I}, or π⊗m\pi^{\otimes m} for I={0,…,m−1}I=\{0,\dots,m-1\}. The compound law of a law π\pi on AA and laws qaq_a on a finite set BB, one for each a∈Aa\in A, is the law on BB with weights ∑a∈Aπ(a)qa(b)\sum_{a\in A}\pi(a)\,q_a(b).✦

The Random Graph of a Kernel

Let π\pi and ν\nu be finite probability laws on finite sets XX and YY, and let WW be a real function on X×YX\times Y. The kernel mean of WW is 𝔼W=𝔼x∼π𝔼y∼νW(x,y),\mathbb{E}\,W=\mathbb{E}_{x\sim\pi}\,\mathbb{E}_{y\sim\nu}\,W(x,y),(6)✦ and its bipartite moment, the homomorphism density of HH in WW with points drawn by π\pi and faces by ν\nu, is t(H,W)=𝔼x∼π⊗13𝔼y∼ν⊗22∏k=(j,s)W(xv(k),yj),t(H,W)=\mathbb{E}_{x\sim\pi^{\otimes 13}}\,\mathbb{E}_{y\sim\nu^{\otimes 22}} \prod_{k=(j,s)}W\bigl(x_{v(k)},y_j\bigr),(7)✦ the product running over the 66 corners.

A symmetric counter kernel (Ω,π,U)(\Omega,\pi,U) is a nonempty finite set Ω\Omega with a finite probability law π\pi 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) such that, with π\pi on both sides, the kernel mean μ=𝔼U\mu=\mathbb{E}\,U is positive and the bipartite moment τ=t(H,U)\tau=t(H,U) is smaller than μ66\mu^{66}.✦

Fix such a kernel and a nonempty finite set VV. An edge pattern bb on VV is an assignment of a bit b{x,y}∈{0,1}b\{x,y\}\in\{0,1\} to each unordered pair {x,y}\{x,y\} of elements of VV, and the graph GbG_b of an edge pattern bb is the simple graph on VV in which distinct vertices xx and yy are adjacent exactly when b{x,y}=1b\{x,y\}=1.✦ For a labelling z:V→Ωz\colon V\to\Omega, the edge coin law at zz is the product, over the unordered pairs {x,y}\{x,y\}, of the biased coins with bias U(zx,zy)U(z_x,z_y).✦ The host law ℙU\mathbb{P}_U is the compound law of π⊗V\pi^{\otimes V} and the edge coin laws.✦ The UU-random graph on VV is GbG_b for an edge pattern bb drawn by ℙU\mathbb{P}_U.

The noninjective indicator 𝟏[f not injective]\mathbf{1}[f\text{ not injective}] of a map ff from the 35 vertices of HH to VV is 11 when ff is not injective and 00 when it is.✦

The Claim

Theorem 1. Let (Ω,π,U)(\Omega,\pi,U) be a symmetric counter kernel with kernel mean μ\mu and bipartite moment τ\tau.

  1. For every integer n≥1n\ge 1 with n>(595+66μ66)/(μ66−τ)n>(595+66\mu^{66})/(\mu^{66}-\tau) there is a simple graph GG on the vertex set {0,…,n−1}\{0,\dots,n-1\} with at least one edge and t(H,G)<p(G)66.t(H,G)<p(G)^{66}.(8)✦

  2. For every nonempty finite set VV, the UU-random graph on VV has expected HH-density 𝔼b∼ℙUt(H,Gb)≤τ+595|V|\mathbb{E}_{b\sim\mathbb{P}_U}\,t(H,G_b)\le\tau+\frac{595}{|V|}(9)✦ and expected edge density 𝔼b∼ℙUp(Gb)=(1−1|V|)μ.\mathbb{E}_{b\sim\mathbb{P}_U}\,p(G_b)=\Bigl(1-\frac{1}{|V|}\Bigr)\mu.(10)✦

  3. For every nonempty finite set VV, when a map ff from the vertices of HH to VV takes independent values, each uniform on VV, its noninjective indicator has expectation 𝔼f𝟏[f not injective]≤595|V|.\mathbb{E}_f\,\mathbf{1}[f\text{ not injective}]\le\frac{595}{|V|}.(11)✦

  4. Let now μ≥0\mu\ge 0 and τ<μ66\tau<\mu^{66} be any real numbers, and n≥1n\ge 1 an integer with n>(595+66μ66)/(μ66−τ)n>(595+66\mu^{66})/(\mu^{66}-\tau). Then τ+595n<((1−1n)μ)66.\tau+\frac{595}{n}<\Bigl(\Bigl(1-\frac{1}{n}\Bigr)\mu\Bigr)^{66}.(12)✦

In the paper, the result reads: if UU is a symmetric [0,1][0,1]-valued kernel on a finite probability space with μ=𝔼U>0\mu=\mathbb{E}\,U>0, τ=t(H,U)\tau=t(H,U) and Δ=μ66−τ>0\Delta=\mu^{66}-\tau>0, then for any integer n>(595+66μ66)/Δn>(595+66\mu^{66})/\Delta there is a finite simple graph GG on nn vertices with t(H,G)<p(G)66t(H,G)<p(G)^{66}.

What Is Checked

The claim is stated over the incidence graph HH of the 13 points and 22 faces, the homomorphism density tt and the edge density pp of finite simple graphs, a symmetric counter kernel (Ω,π,U)(\Omega,\pi,U) with its kernel mean μ\mu and bipartite moment τ\tau, the host law ℙU\mathbb{P}_U on edge patterns of a nonempty finite set VV with their graphs GbG_b, and the product of uniform laws on the maps from the vertices of HH to VV.

Of these constructions, the library proves that the point mass, the mixture, the biased coin, the product law, the compound law and the uniform law each have nonnegative weights summing to 11.