OctoInformBeta

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

Appendix A (setting): tables, conditional averages, and edge-product degree: Edge-product degree and prescribed endpoint counts for a nonnegative integer hh on N=2hN=2h vertices

Matching tables define conditional 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 matching function can be averaged subject to prescribed color-pair counts. The smoothing setting measures its dependence on individual edges through products of edge indicators, and treats the resulting averages as functions of a partition.

The Claim

Definition 1 (Matching tables and polynomial degree). For a nonnegative integer hh, the vertex set VhV_h in (1) has N=2hN=2h vertices, with Fin⁡(h)={0,…,h−1}\operatorname{Fin}(h)=\{0,\ldots,h-1\} and Boolean coordinates 0,10,1: Vh=Fin⁡(h)×{0,1},N=2h.V_h=\operatorname{Fin}(h)\times\{0,1\},\qquad N=2h.(1)✦ A pairing MM of a finite set VV is a permutation of VV satisfying M(M(v))=vM(M(v))=v and M(v)≠vM(v)\ne v for every v∈Vv\in V; write ℳ(V)\mathcal M(V) for the set of pairings.✦

For a map z:V→Bz:V\to B from a finite vertex set VV to a color set BB, its histogram is the function hist⁡(z):B→ℕ\operatorname{hist}(z):B\to\mathbb N in (2): hist⁡(z)(b)=|{v∈V:z(v)=b}|.\operatorname{hist}(z)(b)=|\{v\in V:z(v)=b\}|.(2)✦ For a finite set VV, a color set BB, and s:B→ℕs:B\to\mathbb N, the set Z(V,B;s)Z(V,B;s) of fixed-histogram colorings consists of the maps from VV to BB with histogram ss, as in (3): Z(V,B;s)={z:V→B:hist⁡(z)=s}.Z(V,B;s)=\{z:V\to B:\operatorname{hist}(z)=s\}.(3)✦ The three-color model uses C=Fin⁡(3)={0,1,2}C=\operatorname{Fin}(3)=\{0,1,2\}.

The unordered color-pair type τ(a,b)\tau(a,b) of colors a,b∈Ca,b\in C is the index of their unordered pair in the six-element set ordered 00,01,02,11,12,2200,01,02,11,12,22; exchanging aa and bb leaves this index unchanged.✦ For M∈ℳ(V)M\in\mathcal M(V) and z:V→Cz:V\to C, the matching table T(M,z)T(M,z) is the six-entry vector of edge counts in (4): T(M,z)t=12|{v∈V:τ(z(v),z(M(v)))=t}|,t∈{00,01,02,11,12,22}.T(M,z)_t=\frac12 |\{v\in V:\tau(z(v),z(M(v)))=t\}|, \qquad t\in\{00,01,02,11,12,22\}.(4)✦

A coloring of H×{0,1}H\times\{0,1\}, with HH finite, is identified with the map sending ii to the ordered pair of colors at (i,0)(i,0) and (i,1)(i,1).✦ For a finite set HH and a reference coloring f0:H×{0,1}→Cf_0:H\times\{0,1\}\to C, the reference table E0E^0 is the six-entry vector of color-pair counts in (5): Et0=|{i∈H:τ(f0(i,0),f0(i,1))=t}|.E^0_t=|\{i\in H:\tau(f_0(i,0),f_0(i,1))=t\}|.(5)✦ The matching table relation Rf0R_{f_0} between ℳ(H×{0,1})\mathcal M(H\times\{0,1\}) and Z(H×{0,1},C;hist⁡(f0))Z(H\times\{0,1\},C;\operatorname{hist}(f_0)) is the constraint in (6): Rf0(M,z)⇔T(M,z)=E0.R_{f_0}(M,z)\quad\Longleftrightarrow\quad T(M,z)=E^0.(6)✦

The color-pair count qab(z,M)q_{ab}(z,M) for a finite vertex set VV, a pairing M∈ℳ(V)M\in\mathcal M(V), a coloring z:V→Cz:V\to C, and an ordered color pair (a,b)∈C2(a,b)\in C^2 is the number of vertices v∈Vv\in V whose colors at vv and M(v)M(v) are aa and bb, respectively.✦ For a finite vertex set VV, a pairing M∈ℳ(V)M\in\mathcal M(V), and a coloring z:V→Cz:V\to C, the cross-color coordinates ci(z,M)c_i(z,M) are the color-pair counts for the distinct pairs (a0,b0)=(0,1)(a_0,b_0)=(0,1), (a1,b1)=(0,2)(a_1,b_1)=(0,2), and (a2,b2)=(1,2)(a_2,b_2)=(1,2), as in (7): qab(z,M)=∑v∈V𝟏{z(v)=a,z(M(v))=b},ci(z,M)=qaibi(z,M).q_{ab}(z,M)=\sum_{v\in V}\mathbf1_{\{z(v)=a,\ z(M(v))=b\}}, \qquad c_i(z,M)=q_{a_i b_i}(z,M).(7)✦ For a six-entry table EE of nonnegative integers, the endpoint color-count vector s(E)s(E) is the triple in (8); an internal edge contributes two endpoints of its color: s(E)=(2E00+E01+E02,E01+2E11+E12,E02+E12+2E22).s(E)=\bigl(2E_{00}+E_{01}+E_{02},\ E_{01}+2E_{11}+E_{12},\ E_{02}+E_{12}+2E_{22}\bigr).(8)✦

The predicate average 𝒜Q\mathcal A_Q associated with a condition QQ on a finite set XX is the linear functional on real functions f:X→ℝf:X\to\mathbb R in (9), with value zero when no element satisfies QQ: 𝒜Q(f)=1|{x∈X:Q(x)}|∑x∈XQ(x)f(x).\mathcal A_Q(f)=\frac{1}{|\{x\in X:Q(x)\}|} \sum_{\substack{x\in X\\Q(x)}}f(x).(9)✦ For finite sets XX and YY and a relation R⊆X×YR\subseteq X\times Y, the incidence matrix IRI_R is the matrix with entries IR(y,x)=𝟏{R(x,y)}I_R(y,x)=\mathbf1_{\{R(x,y)\}}.✦ The normalized incidence average 𝒜R,D\mathcal A_{R,D} associated with a relation R⊆X×YR\subseteq X\times Y between finite sets and a real denominator DD is the linear operator from real functions on XX to real functions on YY given by (10), with value zero when D=0D=0: 𝒜R,Df(y)=1D∑x∈XIR(y,x)f(x).\mathcal A_{R,D}f(y)=\frac{1}{D}\sum_{x\in X}I_R(y,x)f(x).(10)✦ For a relation R⊆X×YR\subseteq X\times Y between finite sets, the fiber averaging operator 𝒯R\mathcal T_R maps real functions ff on XX to real functions on YY by the normalized incidence average with denominator equal to the cardinality of Xy={x∈X:R(x,y)}X_y=\{x\in X:R(x,y)\}, as in (11): 𝒯Rf(y)=𝒜R,|Xy|f(y).\mathcal T_Rf(y)=\mathcal A_{R,|X_y|}f(y).(11)✦

The edge indicator x(u,v)x_{(u,v)} associated with u,v∈Vu,v\in V is the function on ℳ(V)\mathcal M(V) in (12): x(u,v)(M)=𝟏{M(u)=v}.x_{(u,v)}(M)=\mathbf1_{\{M(u)=v\}}.(12)✦ For a family of functions xe:X→ℝx_e:X\to\mathbb R indexed by a set ℰ\mathcal E and a nonnegative integer dd, the space Ld(x)L_d(x) of degree at most dd is the real span in (13), where the empty product is 11: Ld(x)=span⁡ℝ{∏j=1kxej:0≤k≤d,ej∈ℰ}.L_d(x)=\operatorname{span}_{\mathbb R} \left\{\prod_{j=1}^k x_{e_j}:0\le k\le d,\ e_j\in\mathcal E\right\}.(13)✦

The Euclidean matching function space ℋh\mathcal H_h is the real coordinate space indexed by ℳ(Vh)\mathcal M(V_h), with inner product ⟨u,v⟩=∑M∈ℳ(Vh)uMvM\langle u,v\rangle=\sum_{M\in\mathcal M(V_h)}u_Mv_M.✦ The coordinate identification JhJ_h from ℋh\mathcal H_h to real functions on ℳ(Vh)\mathcal M(V_h) sends uu to the matching function M↦uMM\mapsto u_M.✦ For nonnegative integers h,dh,d, the matching polynomial space Pd⊆ℋhP_d\subseteq\mathcal H_h is the real span of products of at most dd edge indicators, including the constant, expressed as vectors through JhJ_h, as specified by (14): Pd={u∈ℋh:Jhu∈Ld(x)},x=(x(a,b))(a,b)∈Vh×Vh.P_d=\{u\in\mathcal H_h:J_hu\in L_d(x)\}, \qquad x=(x_{(a,b)})_{(a,b)\in V_h\times V_h}.(14)✦ The orthogonal polynomial projection Πd\Pi_d is the map on ℋh\mathcal H_h in (15): Πdu=proj⁡Pdu.\Pi_du=\operatorname{proj}_{P_d}u.(15)✦ The low-degree function projection Πdfun\Pi_d^{\mathrm{fun}} on real matching functions on ℳ(Vh)\mathcal M(V_h) is the operator obtained from Πd\Pi_d through JhJ_h, as in (16): Πdfun=JhΠdJh−1.\Pi_d^{\mathrm{fun}}=J_h\Pi_dJ_h^{-1}.(16)✦

In the paper, the result reads: for an integer ℓ≥1\ell\ge1 and even NN, XX is the uniformly distributed set of perfect matchings on NN vertices and ZZ is the uniformly distributed set of ordered partitions with positive cell sizes s1,…,sℓs_1,\ldots,s_\ell summing to NN; an admissible table tt consists of nonnegative integers tuv=tvut_{uv}=t_{vu} satisfying 2tuu+∑v≠utuv=su2t_{uu}+\sum_{v\ne u}t_{uv}=s_u, 𝒯tf(z)\mathcal T_t f(z) is the average over matchings with table tt at zz, PdP_d is the span of products of at most dd edge indicators including the constant, and Πd\Pi_d is its orthogonal projection.

What Is Checked

The definitions concern finite vertex sets and fixed-histogram colorings; the projections act on real matching functions for nonnegative integers h,dh,d.

Theorem 1 (Endpoint realization). Let VV be a finite set, let z:V→Cz:V\to C be a coloring, and let EE be a six-entry table of nonnegative integers whose endpoint color counts satisfy hist⁡(z)=s(E)\operatorname{hist}(z)=s(E). There is a pairing M∈ℳ(V)M\in\mathcal M(V) with the cross-color counts in (17): (c0(z,M),c1(z,M),c2(z,M))=(E01,E02,E12).\bigl(c_0(z,M),c_1(z,M),c_2(z,M)\bigr) =\bigl(E_{01},E_{02},E_{12}\bigr).(17)✦