OctoInformBeta

OpenAI preprint, October 2026 · Appendix A. Uniform smoothing of matching averages

Lemma A.2 [The fourth moment]: Three nonempty color cells on 2h2h vertices, with hh a positive integer

A polynomial fourth moment for matching averages.

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

A coloring restricts perfect matchings to a prescribed table of color pair counts. The spectral quantity at issue is the trace of the square of the normalized incidence operator for this restriction.

Let hh be a positive integer and put N=2hN=2h. The vertex set is V=Fin⁡(h)×BoolV=\operatorname{Fin}(h)\times\mathrm{Bool}, where Fin⁡(h)={0,…,h−1}\operatorname{Fin}(h)=\{0,\ldots,h-1\} and Bool={false,true}\mathrm{Bool}=\{\mathrm{false},\mathrm{true}\}; the color set is C=Fin⁡(3)={0,1,2}C=\operatorname{Fin}(3)=\{0,1,2\}. A matching involution on VV is a permutation MM satisfying M2=idM^2=\mathrm{id} and Mv≠vMv\ne v for every vertex vv.✦ Write ℳ(V)\mathcal M(V) for the set of matching involutions.

The histogram sf:C→ℕs_f:C\to\mathbb N of a coloring f:V→Cf:V\to C records its color cell sizes.✦ The fixed histogram coloring set 𝒞s(V)\mathcal C_s(V) consists of the colorings with prescribed histogram ss, as in (1).✦ sf(i)=|{v∈V:f(v)=i}|,𝒞s(V)={f:V→C:sf=s}.s_f(i)=|\{v\in V:f(v)=i\}|, \qquad \mathcal C_s(V)=\{f:V\to C:s_f=s\}.(1)

For a coloring f:V→Cf:V\to C, the paired vertex coloring kf:Fin⁡(h)→C2k_f:\operatorname{Fin}(h)\to C^2 is the function of ordered color pairs given in (2). The reconstruction fk:V→Cf_k:V\to C of a paired coloring k:Fin⁡(h)→C2k:\operatorname{Fin}(h)\to C^2 is the coloring given in (2). kf(a)=(f(a,false),f(a,true)),fk(a,b)={(k(a))1,b=false,(k(a))2,b=true.\begin{aligned} k_f(a)&=(f(a,\mathrm{false}),f(a,\mathrm{true})),\\ f_k(a,b)&= \begin{cases} (k(a))_1,&b=\mathrm{false},\\ (k(a))_2,&b=\mathrm{true}. \end{cases} \end{aligned}(2)✦

The unordered color pair type τ(i,j)\tau(i,j) is the pair of colors i,ji,j arranged in increasing order, indexed by the ordered list ℐ=(00,01,02,11,12,22)\mathcal I=(00,01,02,11,12,22).✦ The reference color table t(f)t(f) of a coloring f:V→Cf:V\to C is the vector indexed by ℐ\mathcal I whose entries count the types of the paired vertex colors.✦ The matching color table tM(f)t_M(f) of a coloring f:V→Cf:V\to C and a matching involution MM on VV is the vector indexed by ℐ\mathcal I whose entries count matching edges of each type; diagonal endpoint counts are twice the internal-edge counts. t(f)u=|{a∈Fin⁡(h):τ(kf(a))=u}|,tM(f)u=12|{v∈V:τ(f(v),f(Mv))=u}|,u∈ℐ.\begin{aligned} t(f)_u &=|\{a\in\operatorname{Fin}(h):\tau(k_f(a))=u\}|,\\ t_M(f)_u &=\frac12|\{v\in V:\tau(f(v),f(Mv))=u\}|, \qquad u\in\mathcal I. \end{aligned}(3)

Fix a reference coloring f0f_0, and write s0=sf0s_0=s_{f_0} and t0=t(f0)t_0=t(f_0). Let 𝒳=ℳ(V)\mathcal X=\mathcal M(V) and 𝒵=𝒞s0(V)\mathcal Z=\mathcal C_{s_0}(V). The reference table compatibility relation PtP_t between 𝒳\mathcal X and 𝒵\mathcal Z requires the matching color table to equal t0t_0.✦ The reference table fiber size DtD_t and this relation are specified in (4). Dt=|{f:V→C:t(f)=t0}|,Pt(M,z)⇔tM(z)=t0.D_t=|\{f:V\to C:t(f)=t_0\}|, \qquad P_t(M,z)\ \Longleftrightarrow\ t_M(z)=t_0.(4)

Incidence Averages

For nonempty finite sets X,ZX,Z and a relation P⊆X×ZP\subseteq X\times Z, the incidence matrix IPI_P is the matrix with rows indexed by ZZ and columns indexed by XX whose entries are the incidence indicators in (5).✦ For a relation P⊆X×ZP\subseteq X\times Z between nonempty finite sets and elements x,y∈Xx,y\in X, the common incidence count cP(x,y)c_P(x,y) is the number of elements of ZZ incident under PP to both xx and yy, as in (5). IP(z,x)=𝟏P(x,z),cP(x,y)=|{z∈Z:P(x,z)andP(y,z)}|.I_P(z,x)=\mathbf 1_{P(x,z)}, \qquad c_P(x,y)=|\{z\in Z:P(x,z)\ \text{and}\ P(y,z)\}|.(5)

For a relation P⊆X×ZP\subseteq X\times Z between nonempty finite sets and a nonzero real normalizing factor DD, the incidence kernel KP,DK_{P,D} and normalized incidence operator BP,DB_{P,D} are real matrices indexed by X×XX\times X whose entries are given in (6). KP,D(x,y)=|Z|D2cP(x,y),BP,D(x,y)=KP,D(x,y)|X|.K_{P,D}(x,y)=\frac{|Z|}{D^2}c_P(x,y), \qquad B_{P,D}(x,y)=\frac{K_{P,D}(x,y)}{|X|}.(6)

For a real function ff on XX and a real factor E≠0E\ne0, the normalized incidence average TP,Ef:Z→ℝT_{P,E}f:Z\to\mathbb R is defined by (7); for E=0E=0 its value is zero. (TP,Ef)(z)=1E∑x∈XIP(z,x)f(x).(T_{P,E}f)(z)=\frac1E\sum_{x\in X}I_P(z,x)f(x).(7)✦ The table operators are Bt=BPt,DtB_t=B_{P_t,D_t} and Tt=TPt,EtT_t=T_{P_t,E_t}, with Et=|𝒳|Dt/|𝒵|E_t=|\mathcal X|D_t/|\mathcal Z|.

The normalized table overlap qt(σ)q_t(\sigma) of a permutation σ\sigma of VV counts colorings compatible with the reference table before and after composition with σ\sigma, with the normalization in (8). qt(σ)=|𝒵|Dt2|{f:V→C:t(f)=t0andt(f∘σ)=t0}|.q_t(\sigma)=\frac{|\mathcal Z|}{D_t^2} |\{f:V\to C:t(f)=t_0\ \text{and}\ t(f\circ\sigma)=t_0\}|.(8)

The Claim

Theorem 1. Let h>0h>0, and let the reference coloring f0:V→Cf_0:V\to C have s0(i)>0s_0(i)>0 for every color i∈Ci\in C. The table incidence operator satisfies (9). tr⁡(Bt2)≤(h+1)33.\operatorname{tr}(B_t^2)\le(h+1)^{33}.(9)✦ The uniform permutation moment satisfies (10), where 𝔖V\mathfrak S_V is the permutation group of VV. 1|𝔖V|∑σ∈𝔖Vqt(σ)2≤(h+1)33.\frac1{|\mathfrak S_V|} \sum_{\sigma\in\mathfrak S_V}q_t(\sigma)^2 \le(h+1)^{33}.(10)✦ For any relation P⊆X×ZP\subseteq X\times Z between nonempty finite sets, any real D≠0D\ne0, and any f:X→ℝf:X\to\mathbb R, the averaging energy identity is (11), with E=|X|D/|Z|E=|X|D/|Z|. 1|Z|∑z∈Z(TP,Ef)(z)2=1|X|∑x∈Xf(x)(BP,Df)(x).\frac1{|Z|}\sum_{z\in Z}(T_{P,E}f)(z)^2 =\frac1{|X|}\sum_{x\in X}f(x)(B_{P,D}f)(x).(11)✦

In the paper, the result reads: for ℓ\ell cells, with aℓ=ℓ(ℓ+1)+1a_\ell=\ell(\ell+1)+1 and bℓ=2aℓ+ℓ2b_\ell=2a_\ell+\ell^2, every admissible table tt in the appendix setting satisfies tr⁡((Tt*Tt)2)≤exp⁡(2aℓ)(N+1)bℓ\operatorname{tr}((T_t^*T_t)^2)\le \exp(2a_\ell)(N+1)^{b_\ell}.

What Is Checked

The table bounds are stated over matching involutions and colorings with the reference histogram on 2h2h vertices, with h>0h>0 and all three color cells nonempty; the energy identity is stated over arbitrary relations between nonempty finite sets and nonzero real normalizing factors.

The paired vertex coloring and reconstruction maps in (2) are inverse to one another.✦