OctoInformBeta

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

§3 (proof of Proposition 3.5): priors, thinning, dilution, crossed product: Gibbs priors and thinning, dilution by an inactive type, and a crossed kernel VV with tI,J(V)=tI,J(W)tI,J(W𝖳)t_{I,J}(V)=t_{I,J}(W)\,t_{I,J}(W^{\mathsf T})

A mean-one oriented kernel with moment product below one.

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 faces, each face a triple of points. Its vertex classes are the points I={0,…,12}I=\{0,\dots,12\} and the faces J={0,…,21}J=\{0,\dots,21\}, and a face jj has the points v0(j)<v1(j)<v2(j)v_0(j)<v_1(j)<v_2(j) in its slots 00, 11, 22. The 66 edges of HH are the corners: a corner k=(j,r)k=(j,r) is a face j(k)=jj(k)=j with one of its slots rr, at the point v(k)=vr(j)v(k)=v_r(j).✦ Sidorenko’s conjecture asks of HH that t(H,V)≥1t(H,V)\ge1 for every symmetric kernel V≥0V\ge0 of mean one. The 22 faces, for j=0,…,21j=0,\dots,21 in this order, are the triples {0,1,3}\{0,1,3\}, {0,1,9}\{0,1,9\}, {0,2,3}\{0,2,3\}, {0,2,9}\{0,2,9\}, {1,3,10}\{1,3,10\}, {1,7,10}\{1,7,10\}, {1,7,12}\{1,7,12\}, {1,9,12}\{1,9,12\}, {2,3,4}\{2,3,4\}, {2,4,9}\{2,4,9\}, {3,4,11}\{3,4,11\}, {3,10,11}\{3,10,11\}, {4,8,9}\{4,8,9\}, {4,8,11}\{4,8,11\}, {5,6,7}\{5,6,7\}, {5,6,11}\{5,6,11\}, {5,7,10}\{5,7,10\}, {5,10,11}\{5,10,11\}, {6,7,12}\{6,7,12\}, {6,8,11}\{6,8,11\}, {6,8,12}\{6,8,12\}, {8,9,12}\{8,9,12\}, each listed as v0(j)<v1(j)<v2(j)v_0(j)<v_1(j)<v_2(j).

The oriented kernels of this item are functions W:X×Y→[0,∞)W\colon X\times Y\to[0,\infty) on a product of two finite probability spaces; they send the points of HH to XX and the faces to YY, and need not be symmetric. The item reaches them from a construction with random types: each point and each face of HH gets a type, and each corner a random activation, a set of active corners with a sign at every corner, whose law depends on the types at the two ends of the corner. Its ingredients are exponential priors on the types, a Gibbs thinning of these laws, dilution by an inactive type, and the crossed product, which turns a kernel on X×YX\times Y into a symmetric one.

Laws on Activations

A 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✦; the expectation of a real function ff on AA under it is 𝔼pf=∑a∈Ap(a)f(a)\mathbb E_pf=\sum_{a\in A}p(a)f(a).✦

An activation of a finite set KK is a pair z=(S,η)z=(S,\eta) of a set S⊆KS\subseteq K of active elements and a vector η∈{−1,1}K\eta\in\{-1,1\}^K of Boolean signs✦, and the Boolean monomial of a set α⊆K\alpha\subseteq K is ηα=∏i∈αηi\eta_\alpha=\prod_{i\in\alpha}\eta_i.✦ The activation character φα\varphi_\alpha of a set α⊆K\alpha\subseteq K is a real function on activations of KK, and the activation moment mp(α,β)m_p(\alpha,\beta) of a probability law pp on activations of KK at sets α,β⊆K\alpha,\beta\subseteq K is a real number; they are given by φα(S,η)={ηα,α⊆S,0,otherwise,mp(α,β)=𝔼z∼pφα(z)φβ(z).\varphi_\alpha(S,\eta)=\begin{cases}\eta_\alpha,&\alpha\subseteq S,\\ 0,&\text{otherwise,}\end{cases}\qquad m_p(\alpha,\beta)=\mathbb E_{z\sim p}\,\varphi_\alpha(z)\,\varphi_\beta(z).(1) The inactive law δ⌀\delta_\varnothing is the point mass at the activation with no active element and every sign equal to −1-1.✦

For a nonempty Γ⊆K\Gamma\subseteq K and a bias τ∈[−1,1]\tau\in[-1,1], the tilted law on Γ\Gamma is the probability law on sign vectors that gives η\eta the weight (1+τηΓ)/2|K|(1+\tau\,\eta_\Gamma)/2^{|K|}.✦ The branch law κS,Γ,τ\kappa_{S,\Gamma,\tau} of a set S⊆KS\subseteq K is the law on activations that is the product of the point mass at SS and this tilted law; its active set is always SS.✦ For sets T⊆KT\subseteq K and nonempty Γ⊆K\Gamma\subseteq K and a bias τ∈[−1,1]\tau\in[-1,1], the base activation law μT,Γ,τ\mu_{T,\Gamma,\tau} with bias τ\tau is the probability law on activations of KK given by the even mixture μT,Γ,τ=12κT,Γ,τ+12κΓ,Γ,−τ.\mu_{T,\Gamma,\tau}=\tfrac12\,\kappa_{T,\Gamma,\tau}+\tfrac12\,\kappa_{\Gamma,\Gamma,-\tau}.(2)✦

Corners and Coefficients

The three 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)\} of its points, in its slots 00, 11, 22; the 33 point pairs are the pairs of points that are sides of faces.✦ A corner kk lies on the two sides of its face through v(k)v(k): its left pair L(k)L(k) is the first of them✦ and its right pair R(k)R(k) the second.✦ The corners of a point pair ee are the corners with ee as left or right pair, the four corners at the two points of ee in the two faces containing ee.✦

For a corner kk, the corner union UkU_k and the corner symmetric difference Γk\Gamma_k are the union and the symmetric difference of the set of corners of L(k)L(k) and the set of corners of R(k)R(k), and the corner sign σk\sigma_k is −1-1 at the corner (0,0)(0,0), in slot 00 of face 00, and 11 at every other corner.✦ The corner law of kk is the base activation law pk=μUk,Γk,σk/2p_k=\mu_{U_k,\Gamma_k,\sigma_k/2} on activations of the 66 corners.✦ The base pair law p0(a,b)p^0(a,b) of a point aa and a face bb is the law on activations of the 66 corners given by p0(a,b)={p(b,r),a=vr(b),δ⌀,a∉b.p^0(a,b)=\begin{cases}p_{(b,r)},&a=v_r(b),\\ \delta_\varnothing,&a\notin b.\end{cases}(3)✦

A labelling α\alpha gives each of the 33 point pairs a subset of a finite set KK; it is nonempty when no pair gets the empty set.✦ Let FF give each corner kk a real function FkF_k of two subsets of KK. The label product of FF at α\alpha is the product over the corners kk of FkF_k at the labels of L(k)L(k) and R(k)R(k)✦, and the active coefficient of FF is the sum of its label products over the nonempty labellings.✦

Let the point types form a finite set AA and the face types a finite set BB, and let p(a,b)p(a,b) be a law on activations of KK for each point type aa and face type bb. The typed coefficient of type maps 𝒂:I→A\mathbf a\colon I\to A and 𝒃:J→B\mathbf b\colon J\to B is the active coefficient of the activation moments at the corners, Cp(𝒂,𝒃)=∑α∏kmp(𝒂v(k),𝒃j(k))(α(L(k)),α(R(k))),C_p(\mathbf a,\mathbf b)=\sum_{\alpha}\prod_{k} m_{p(\mathbf a_{v(k)},\,\mathbf b_{j(k)})}\bigl(\alpha(L(k)),\alpha(R(k))\bigr),(4)✦ the sum running over the nonempty labellings. For laws π\pi on AA and ν\nu on BB, the type map law π⊗I×ν⊗J\pi^{\otimes I}\times\nu^{\otimes J} is the product of the product laws that give the points independent types drawn from π\pi and the faces independent types drawn from ν\nu.✦ The averaged coefficient C‾(π,ν,p)\bar C(\pi,\nu,p) is the expectation of Cp(𝒂,𝒃)C_p(\mathbf a,\mathbf b) under the type map law.✦

Priors and Thinning

A score system ss on the type sets AA and BB consists of real scores saps^{\mathrm p}_a for the point types aa, sbfs^{\mathrm f}_b for the face types bb, and sabs_{ab} for the pairs of types.✦ The total score 𝒬(𝒂,𝒃)\mathcal Q(\mathbf a,\mathbf b) of type maps 𝒂\mathbf a and 𝒃\mathbf b is the real number 𝒬(𝒂,𝒃)=∑i∈Is𝒂ip+∑j∈Js𝒃jf+∑ks𝒂v(k)𝒃j(k).\mathcal Q(\mathbf a,\mathbf b)=\sum_{i\in I}s^{\mathrm p}_{\mathbf a_i} +\sum_{j\in J}s^{\mathrm f}_{\mathbf b_j}+\sum_{k}s_{\mathbf a_{v(k)}\mathbf b_{j(k)}}.(5)✦

For a real function hh on a finite set AA and a real number ρ\rho, the exponential prior γh,ρ\gamma_{h,\rho} is the probability law on AA proportional to eρhe^{\rho h}, with normalizer Zh(ρ)Z_h(\rho).✦ For a score system ss on AA and BB and real numbers ρ\rho and MM, the Gibbs thinning factor of a point type aa and a face type bb is the number λab=eρ(sab−M)\lambda_{ab}=e^{\rho(s_{ab}-M)}, as in (6): γh,ρ(a)=eρh(a)Zh(ρ),Zh(ρ)=∑a∈Aeρh(a),λab=eρ(sab−M).\gamma_{h,\rho}(a)=\frac{e^{\rho h(a)}}{Z_h(\rho)},\qquad Z_h(\rho)=\sum_{a\in A}e^{\rho h(a)},\qquad \lambda_{ab}=e^{\rho(s_{ab}-M)}.(6) The thinned law of a law pp on activations by a factor λ∈[0,1]\lambda\in[0,1] is the mixture λp+(1−λ)δ⌀\lambda p+(1-\lambda)\,\delta_\varnothing of pp and the inactive law✦. For a score system ss on AA and BB, real numbers ρ\rho and MM and n∈ℕn\in\mathbb N, the Gibbs prefactor of ss is the number cn(ρ,M)=e−nρM/(Zsp(ρ)|A|Zsf(ρ)|B|)c_n(\rho,M)=e^{-n\rho M}/\bigl(Z_{s^{\mathrm p}}(\rho)^{|A|}Z_{s^{\mathrm f}}(\rho)^{|B|}\bigr).✦

Kernels and Their Moments

Let XX and YY be finite sets with probability laws π\pi and ν\nu, and WW a real function on X×YX\times Y. The kernel mean of WW is 𝔼π×νW=∑x,yπ(x)ν(y)W(x,y)\mathbb E_{\pi\times\nu}W=\sum_{x,y}\pi(x)\nu(y)W(x,y), and the bipartite moment tI,J(W)t_{I,J}(W) of WW is the homomorphism density of HH in WW with the points sent to XX and the faces to YY: tI,J(W)=𝔼∏kW(xv(k),yj(k)),x∼π⊗I,y∼ν⊗J.t_{I,J}(W)=\mathbb E\prod_{k}W\bigl(x_{v(k)},y_{j(k)}\bigr),\qquad x\sim\pi^{\otimes I},\quad y\sim\nu^{\otimes J}.(7) The transpose W𝖳(y,x)=W(x,y)W^{\mathsf T}(y,x)=W(x,y) is a function on Y×XY\times X, and its bipartite moment tI,J(W𝖳)t_{I,J}(W^{\mathsf T}) draws the points from ν\nu and the faces from π\pi. The crossed kernel of WW is the function VV on (X×Y)×(X×Y)(X\times Y)\times(X\times Y) given by V((x,y),(x′,y′))=W(x,y′)W(x′,y).V\bigl((x,y),(x',y')\bigr)=W(x,y')\,W(x',y).(8)✦

The Claim

Theorem 1. Let ss be a score system whose point types are the points and whose face types are the faces, and let ρ\rho and MM be real numbers with 0≤λab≤10\le\lambda_{ab}\le1 for every point aa and face bb. Take the exponential priors γsp,ρ\gamma_{s^{\mathrm p},\rho} on the points and γsf,ρ\gamma_{s^{\mathrm f},\rho} on the faces, and let pλ(a,b)p^\lambda(a,b) be the base pair law p0(a,b)p^0(a,b) thinned by λab\lambda_{ab}. Then C‾(γsp,ρ,γsf,ρ,pλ)=c66(ρ,M)∑𝒂:I→I∑𝒃:J→JCp0(𝒂,𝒃)eρ𝒬(𝒂,𝒃).\bar C\bigl(\gamma_{s^{\mathrm p},\rho},\gamma_{s^{\mathrm f},\rho},p^\lambda\bigr) =c_{66}(\rho,M)\sum_{\mathbf a\colon I\to I}\ \sum_{\mathbf b\colon J\to J} C_{p^0}(\mathbf a,\mathbf b)\,e^{\rho\,\mathcal Q(\mathbf a,\mathbf b)}.(9)✦

Theorem 2. Let hh and cc be real functions on a finite set AA, and let a0∈Aa_0\in A satisfy h(a)<h(a0)h(a)<h(a_0) for every a≠a0a\ne a_0 and c(a0)<0c(a_0)<0. Then there is ρ>0\rho>0 with ∑a∈Ac(a)eρh(a)<0.\sum_{a\in A}c(a)\,e^{\rho h(a)}<0.(10)✦

Theorem 3. There are probability laws π\pi on the points and ν\nu on the faces, taken as point and face types, and for every point aa and face bb a law p(a,b)p(a,b) on activations of the 66 corners with 𝔼p(a,b)φα=0\mathbb E_{p(a,b)}\varphi_\alpha=0 for every nonempty set α\alpha of corners, whose averaged coefficient is negative: C‾(π,ν,p)<0.\bar C(\pi,\nu,p)<0.(11)✦

Definition 1. The diluted law pεp_\varepsilon of a probability law pp on a finite set AA, for 0≤ε≤10\le\varepsilon\le1, is the probability law on A∪{⋆}A\cup\{\star\}, with ⋆\star a new inactive type, given by pε(⋆)=1−ε,pε(a)=εp(a)(a∈A).p_\varepsilon(\star)=1-\varepsilon,\qquad p_\varepsilon(a)=\varepsilon\,p(a)\quad(a\in A).(12)✦

Definition 2. The diluted pair law p⋆p^\star of a family of laws p(a,b)p(a,b) on activations of a finite set KK, indexed by a∈Aa\in A and b∈Bb\in B, is the family indexed by a∈A∪{⋆}a\in A\cup\{\star\} and b∈Bb\in B given by p⋆(a,b)=p(a,b)(a∈A),p⋆(⋆,b)=δ⌀.p^\star(a,b)=p(a,b)\quad(a\in A),\qquad p^\star(\star,b)=\delta_\varnothing.(13)✦

Theorem 4. Let t0<0t_0<0 and t1t_1 be real numbers. There is ε\varepsilon with 0<ε<10<\varepsilon<1 and (1+ε13t0)(1+ε22t1)<1.(1+\varepsilon^{13}t_0)(1+\varepsilon^{22}t_1)<1.(14)✦

Theorem 5. There are finite nonempty sets XX and YY, probability laws π\pi on XX and ν\nu on YY, and an oriented kernel on them: a function W:X×Y→[0,∞)W\colon X\times Y\to[0,\infty) with 𝔼π×νW=1andtI,J(W)tI,J(W𝖳)<1.\mathbb E_{\pi\times\nu}W=1\qquad\text{and}\qquad t_{I,J}(W)\,t_{I,J}(W^{\mathsf T})<1.(15)✦

Theorem 6. Let π\pi and ν\nu be probability laws on finite sets XX and YY, and WW a real function on X×YX\times Y. With the law π×ν\pi\times\nu on both sides, the crossed kernel VV of WW satisfies tI,J(V)=tI,J(W)tI,J(W𝖳).t_{I,J}(V)=t_{I,J}(W)\,t_{I,J}(W^{\mathsf T}).(16)✦

What Is Checked

The claims are stated over the incidence graph HH with its corners and their left and right pairs, probability laws on finite sets, the corner laws and base pair laws (3) on activations of the corners, the typed and averaged coefficients (4), the exponential priors and Gibbs thinning factors (6) of a score system, and the bipartite moment (7) and crossed kernel (8) of a function on X×YX\times Y. Of these constructions the library also proves that the corner symmetric difference Γk\Gamma_k is nonempty for every corner kk.✦