OctoInformBeta

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

§3 (setting): the base laws: Half-half mixtures of two active sets of corners with tilted signs, their moments given exactly, and the law at each point and face

Corner laws with a negative moment at one corner.

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 the counterexample to Sidorenko’s conjecture is built on 1313 points, numbered 0,…,120,\dots,12, and 2222 faces, each a triple of points: it is the bipartite graph on the points and the faces that joins each point to the faces containing it. Listed with their points v0(j)<v1(j)<v2(j)v_0(j)<v_1(j)<v_2(j), the faces j=0,…,21j=0,\dots,21 are, in 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{gathered} \{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{gathered}(1)✦ The sides of a face jj are the pairs {v0(j),v1(j)}\{v_0(j),v_1(j)\}, {v0(j),v2(j)}\{v_0(j),v_2(j)\} and {v1(j),v2(j)}\{v_1(j),v_2(j)\}, in that order, and each of the 3333 point pairs that occur as sides lies in exactly two faces.✦ A corner of HH is an edge of HH, the incidence of a point with a face; it is written κ=(j,s)\kappa=(j,s) for the face jj and the slot s∈{0,1,2}s\in\{0,1,2\} of its point vs(j)v_s(j), and there are 6666 corners.✦

In the construction of a negative kernel correlation, each pair of a point and a face carries a random activation of the corners: a random set of active corners and a random sign on every corner. The base laws are the laws of these activations. The question is how they correlate the signs on the corners of the two sides of a face that meet at a corner.

The Sets at a Corner

The left pair eκe_\kappa and the right pair fκf_\kappa of a corner κ=(j,s)\kappa=(j,s) are the two sides of the face jj that contain its point vs(j)v_s(j), the first and the second in the order of sides. The set UeU_e of corners of a point pair ee is the set of the four corners at which a point of ee meets one of the two faces containing ee: Ue={(j,s):e⊆j,vs(j)∈e}.U_e=\{(j,s) : e\subseteq j,\ v_s(j)\in e\}.(2)✦

For a corner κ\kappa, the corner union MκM_\kappa and the corner symmetric difference Γκ\Gamma_\kappa are the sets of corners Mκ=Ueκ∪Ufκ,Γκ=Ueκ△Ufκ.M_\kappa=U_{e_\kappa}\cup U_{f_\kappa},\qquad \Gamma_\kappa=U_{e_\kappa}\mathbin{\triangle}U_{f_\kappa}.(3)

The corner sign σκ\sigma_\kappa of a corner κ\kappa is the number −1-1 when κ=(0,0)\kappa=(0,0), the point 00 in the face {0,1,3}\{0,1,3\}, and 11 at every other corner.✦

Activations and Their Moments

A finite probability law pp on a finite set AA is a function p:A→[0,∞)p\colon A\to[0,\infty) with ∑a∈Ap(a)=1\sum_{a\in A}p(a)=1✦, and the expectation of a real function ff on AA under pp is 𝔼pf=∑a∈Ap(a)f(a)\mathbb{E}_p f=\sum_{a\in A}p(a)f(a).✦ The point mass δa\delta_a at an element aa of AA is the law on AA with weight 11 at aa and weight 00 elsewhere.✦ The mixture tp+(1−t)qtp+(1-t)q of two laws p,qp,q on AA, for 0≤t≤10\le t\le 1, has weight tp(x)+(1−t)q(x)tp(x)+(1-t)q(x) at xx✦, and the product p⊗qp\otimes q of laws pp on AA and qq on BB is the law on A×BA\times B with weight p(x)q(y)p(x)q(y) at (x,y)(x,y).✦

An activation of a finite set KK is a pair z=(S,η)z=(S,\eta) of a subset SS of KK, the set of active elements, and a labelling η:K→{true,false}\eta\colon K\to\{\mathrm{true},\mathrm{false}\}.✦ The Boolean sign of a label is sgn⁡(true)=1\operatorname{sgn}(\mathrm{true})=1 and sgn⁡(false)=−1\operatorname{sgn}(\mathrm{false})=-1✦, and the Boolean monomial of a subset α\alpha of KK at η\eta is the product ηα=∏i∈αsgn⁡η(i)\eta^\alpha=\prod_{i\in\alpha}\operatorname{sgn}\eta(i)✦. The activation character φα\varphi_\alpha of α\alpha is the function on activations φα(S,η)={ηαif α⊆S,0otherwise,\varphi_\alpha(S,\eta)= \begin{cases}\eta^\alpha & \text{if } \alpha\subseteq S,\\ 0 & \text{otherwise,}\end{cases}(4)✦ and the moment mp(α,β)m_p(\alpha,\beta) of a law pp on activations of KK at two subsets α\alpha and β\beta of KK is mp(α,β)=𝔼z∼pφα(z)φβ(z).m_p(\alpha,\beta)=\mathbb{E}_{z\sim p}\,\varphi_\alpha(z)\,\varphi_\beta(z).(5)✦

For a nonempty subset Γ\Gamma of KK and a real number aa with |a|≤1|a|\le 1, the tilted law τΓ,a\tau_{\Gamma,a} is the law on labellings of KK with weights τΓ,a(η)=2−|K|(1+aηΓ).\tau_{\Gamma,a}(\eta)=2^{-|K|}\bigl(1+a\,\eta^\Gamma\bigr).(6)✦ For a subset SS of KK, the branch law δS⊗τΓ,a\delta_S\otimes\tau_{\Gamma,a} is the law of the activation whose active set is SS and whose labelling is drawn from τΓ,a\tau_{\Gamma,a}.✦

The Claim

Definition 1. Let KK be a finite set, MM and Γ\Gamma subsets of KK with Γ\Gamma nonempty, and aa a real number with |a|≤1|a|\le 1. The base activation law ΛM,Γ,a\Lambda_{M,\Gamma,a} is the law on activations of KK ΛM,Γ,a=12δM⊗τΓ,a+12δΓ⊗τΓ,−a.\Lambda_{M,\Gamma,a}=\tfrac12\,\delta_M\otimes\tau_{\Gamma,a} +\tfrac12\,\delta_\Gamma\otimes\tau_{\Gamma,-a}.(7)✦ The corner law at a corner κ\kappa is the base activation law Λκ=ΛMκ,Γκ,σκ/2\Lambda_\kappa=\Lambda_{M_\kappa,\Gamma_\kappa,\sigma_\kappa/2} on activations of the 6666 corners, with MκM_\kappa and Γκ\Gamma_\kappa as in (3).✦ The pair law Πv,j\Pi_{v,j} at a point vv and a face jj is the law on activations of the corners Πv,j={Λ(j,s)if v=vs(j),δz∅if v∉j,\Pi_{v,j}= \begin{cases}\Lambda_{(j,s)} & \text{if } v=v_s(j),\\ \delta_{z_\emptyset} & \text{if } v\notin j,\end{cases}(8)✦ where z∅z_\emptyset is the empty activation, with no active corner and every label false.

In the paper, the result reads: the type sets 𝒜=I\mathcal{A}=I, ℬ=J\mathcal{B}=J and 𝒦=C\mathcal{K}=C are the points, the faces and the corners; at the corner κ\kappa of a point vv and a face jj, with pairs ee and ff, the set Mκ=Ue∪UfM_\kappa=U_e\cup U_f has seven corners and Γκ=Ue△Uf\Gamma_\kappa=U_e\mathbin{\triangle}U_f has six; for a fixed 0<θ<10<\theta<1 and one negative corner sign σ(0,0)=−1\sigma_{(0,0)}=-1, the base law takes S=MκS=M_\kappa or S=ΓκS=\Gamma_\kappa with probability 1/21/2 each, with sign biases ±σκθ\pm\sigma_\kappa\theta on the monomial ηΓκ\eta^{\Gamma_\kappa}, and S=∅S=\emptyset at pairs of types that are not incident.

The corner law Λκ\Lambda_\kappa at a corner κ\kappa is the paper’s base law at κ\kappa with θ=1/2\theta=1/2.

Theorem 1. Let κ\kappa be a corner and let α\alpha, β\beta be sets of corners; write mκm_\kappa for the moment (5) of the corner law Λκ\Lambda_\kappa, and [P][P] for 11 when PP holds and 00 otherwise. Then mκ(α,β)=12[α∪β⊆Mκ]([α=β]+σκ2[α△β=Γκ])+12[α∪β⊆Γκ]([α=β]−σκ2[α△β=Γκ]).\begin{aligned} m_\kappa(\alpha,\beta)={}&\tfrac12\,[\alpha\cup\beta\subseteq M_\kappa]\, \bigl([\alpha=\beta]+\tfrac{\sigma_\kappa}{2}\, [\alpha\mathbin{\triangle}\beta=\Gamma_\kappa]\bigr)\\ &+\tfrac12\,[\alpha\cup\beta\subseteq\Gamma_\kappa]\, \bigl([\alpha=\beta]-\tfrac{\sigma_\kappa}{2}\, [\alpha\mathbin{\triangle}\beta=\Gamma_\kappa]\bigr). \end{aligned}(9)✦ If α\alpha is nonempty, then 𝔼z∼Λκφα(z)=0.\mathbb{E}_{z\sim\Lambda_\kappa}\varphi_\alpha(z)=0.(10)✦ If α\alpha and β\beta are disjoint and not both empty, then mκ(α,β)=0.m_\kappa(\alpha,\beta)=0.(11)✦ At the sets of corners of the left and right pairs of κ\kappa, mκ(Ueκ,Ufκ)=σκ4.m_\kappa(U_{e_\kappa},U_{f_\kappa})=\frac{\sigma_\kappa}{4}.(12)✦

What Is Checked

The claim is stated over the 6666 corners of the configuration of 1313 points and 2222 faces, with the left and right pairs of each corner, the sets UeU_e, MκM_\kappa and Γκ\Gamma_\kappa and the corner sign σκ\sigma_\kappa, and over finite probability laws on activations of the corners, built from point masses, mixtures, products and tilted laws, with their characters and moments.

The library proves that the corner symmetric difference Γκ\Gamma_\kappa is nonempty at every corner κ\kappa.✦