OctoInformBeta

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

Corollary A.4 [Three-cell smoothing]: Permutations recover the partition energy, and one polynomial represents all realized table averages of a low-degree function

Three-cell matching averages smooth uniformly.

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 three-cell average of a function on perfect matching columns fixes the numbers of matching edges of each color type. The smoothing estimates concern the part of that function orthogonal to products of a bounded number of edge incidences.

Write Finh\mathrm{Fin}\,h for the integers from 00 to h−1h-1 and Bool\mathrm{Bool} for the two-element set {false,true}\{\mathrm{false},\mathrm{true}\}. For the smoothing estimates, the vertex set is Vh=Finh×BoolV_h=\mathrm{Fin}\,h\times\mathrm{Bool}, with N=2hN=2h vertices and colors Fin3={0,1,2}\mathrm{Fin}\,3=\{0,1,2\}.✦ A matching involution MM on a finite vertex set VV is a fixed-point-free involutive permutation of VV; write ℳ(V)\mathcal M(V) for the set of matching involutions on VV.✦ Write Sym⁡(V)\operatorname{Sym}(V) for the group of permutations of VV. For M∈ℳ(V)M\in\mathcal M(V), p∈Sym⁡(V)p\in\operatorname{Sym}(V), and vertices u,v∈Vu,v\in V, relabeling by pp and the edge incidence coordinate XuvX_{uv} are given by (1). p⋅M=pMp−1,Xuv(M)=𝟏{M(u)=v}.p\cdot M=pMp^{-1}, \qquad X_{uv}(M)=\mathbf 1_{\{M(u)=v\}}.(1)

The histogram s(z)s(z) of a coloring z:V→Fin3z:V\to\mathrm{Fin}\,3 is the vector of its three cell sizes.✦ Colorings with prescribed histogram ss form the set in (2). si(z)=#{v∈V:z(v)=i},𝒵s(V)={z:V→Fin3:s(z)=s}.s_i(z)=\#\{v\in V:z(v)=i\}, \qquad \mathcal Z_s(V)=\{z:V\to\mathrm{Fin}\,3:s(z)=s\}.(2)

The unordered color pair type τ(i,j)\tau(i,j) of colors i,j∈Fin3i,j\in\mathrm{Fin}\,3 is the pair of these colors in increasing order.✦ The matching color table t(M,z)t(M,z) of a matching involution M∈ℳ(V)M\in\mathcal M(V) and a coloring z:V→Fin3z:V\to\mathrm{Fin}\,3 is the vector of unoriented edge counts in the order 00,01,02,11,12,2200,01,02,11,12,22, as in (3); diagonal endpoint counts are twice the corresponding internal-edge counts.✦ The distinct color pairs are 01,02,1201,02,12, in that order.✦ tij(M,z)=12#{v∈V:τ(z(v),z(M(v)))=ij},0≤i≤j≤2.t_{ij}(M,z)=\frac12\#\{v\in V: \tau(z(v),z(M(v)))=ij\}, \qquad 0\le i\le j\le2.(3)✦

A coloring zz of VhV_h is identified with its ordered color pairs (z(i,false),z(i,true))(z(i,\mathrm{false}),z(i,\mathrm{true})) for i∈Finhi\in\mathrm{Fin}\,h.✦ The reference table t*(z0)t^*(z_0) of a coloring z0z_0 of VhV_h is the vector counting its prescribed color pairs✦, and reference table compatibility Rz0(M,z)R_{z_0}(M,z) is the relation in (4) between a matching involution M∈ℳ(Vh)M\in\mathcal M(V_h) and a coloring z∈𝒵s(z0)(Vh)z\in\mathcal Z_{s(z_0)}(V_h). tij*(z0)=#{k∈Finh:τ(z0(k,false),z0(k,true))=ij},Rz0(M,z)⇔t(M,z)=t*(z0),z∈𝒵s(z0)(Vh).\begin{aligned} t^*_{ij}(z_0) &=\#\{k\in\mathrm{Fin}\,h: \tau(z_0(k,\mathrm{false}),z_0(k,\mathrm{true}))=ij\},\\ R_{z_0}(M,z)&\ \Longleftrightarrow\ t(M,z)=t^*(z_0), \qquad z\in\mathcal Z_{s(z_0)}(V_h). \end{aligned}(4)

For a finite relation R⊆X×ZR\subseteq X\times Z and z∈Zz\in Z, the fiber Rz={x:R(x,z)}R_z=\{x:R(x,z)\} is the set of elements of XX related to zz. For a real function gg on XX and a normalizing factor EE, the incidence matrix IRI_R of RR, normalized incidence average CR,EgC_{R,E}g, and fiber average ARgA_Rg are given by (5); a zero denominator gives value zero. The matching average 𝒜z,tf\mathcal A_{z,t}f, for a coloring zz of VV, a table tt, and a real function ff on ℳ(V)\mathcal M(V), is the fiber average over the set ℳz,t={M:t(M,z)=t}\mathcal M_{z,t}=\{M:t(M,z)=t\} of matching involutions on VV.✦ IR(z,x)=𝟏R(x,z),CR,Eg(z)=1E∑x∈XIR(z,x)g(x),ARg(z)=CR,#Rzg(z).I_R(z,x)=\mathbf 1_{R(x,z)}, \qquad C_{R,E}g(z)=\frac{1}{E}\sum_{x\in X}I_R(z,x)g(x), \qquad A_Rg(z)=C_{R,\#R_z}g(z).(5)

The table energy ℰs(t;f)\mathcal E_s(t;f) of a real matching function ff at a table tt and histogram ss is the mean squared matching average over the colorings with histogram ss, as defined in (6). ℰs(t;f)=1#𝒵s(V)∑z∈𝒵s(V)(1#ℳz,t∑M∈ℳz,tf(M))2.\mathcal E_s(t;f)= \frac{1}{\#\mathcal Z_s(V)} \sum_{z\in\mathcal Z_s(V)} \left(\frac{1}{\#\mathcal M_{z,t}} \sum_{M\in\mathcal M_{z,t}}f(M)\right)^2.(6)✦

The real matching functions on VV form the Euclidean space ℝℳ(V)\mathbb R^{\mathcal M(V)}.✦ For a nonnegative integer dd, the matching polynomial space Pd⊆ℝℳ(V)P_d\subseteq\mathbb R^{\mathcal M(V)} is the edge-product span in (7), including the empty product 11.✦ The orthogonal polynomial projection Πd\Pi_d on ℝℳ(V)\mathbb R^{\mathcal M(V)} is the orthogonal projection onto PdP_d.✦ Pd=span⁡ℝ{∏j=1kXujvj:0≤k≤d},⟨f,g⟩=∑M∈ℳ(V)f(M)g(M).P_d=\operatorname{span}_{\mathbb R} \left\{\prod_{j=1}^{k}X_{u_jv_j}:0\le k\le d\right\}, \qquad \langle f,g\rangle=\sum_{M\in\mathcal M(V)}f(M)g(M).(7)

The Claim

Theorem 1. For every K∈ℕK\in\mathbb N, there are integers d≥1d\ge1 and h0h_0 such that, whenever h≥h0h\ge h_0, z:Vh→Fin3z:V_h\to\mathrm{Fin}\,3 is a coloring with positive histogram, meaning that every color cell is nonempty, M0∈ℳ(Vh)M_0\in\mathcal M(V_h), and ff is a real matching function, the uniform permutation estimate (8) holds with t0=t(M0,z)t_0=t(M_0,z): 1#Sym⁡(Vh)∑p∈Sym⁡(Vh)(1#ℳz,t0∑M∈ℳz,t0(f−Πdf)(p⋅M))2≤N−2K1#ℳ(Vh)∑M∈ℳ(Vh)f(M)2.\frac{1}{\#\operatorname{Sym}(V_h)} \sum_{p\in\operatorname{Sym}(V_h)} \left(\frac{1}{\#\mathcal M_{z,t_0}} \sum_{M\in\mathcal M_{z,t_0}}(f-\Pi_df)(p\cdot M)\right)^2 \le N^{-2K}\frac{1}{\#\mathcal M(V_h)} \sum_{M\in\mathcal M(V_h)}f(M)^2.(8)✦

For every K∈ℕK\in\mathbb N, there also are integers d≥1d\ge1 and h0h_0 such that, whenever h≥h0h\ge h_0, the reference coloring z0z_0 has positive histogram s=s(z0)s=s(z_0), and f∈ℝℳ(Vh)f\in\mathbb R^{\mathcal M(V_h)}, the uniform table estimate (9) holds: 1#𝒵s(Vh)∑z∈𝒵s(Vh)(1#(Rz0)z∑M∈(Rz0)z(f−Πdf)(M))2≤N−2K1#ℳ(Vh)∑M∈ℳ(Vh)f(M)2.\frac{1}{\#\mathcal Z_s(V_h)} \sum_{z\in\mathcal Z_s(V_h)} \left(\frac{1}{\#(R_{z_0})_z} \sum_{M\in(R_{z_0})_z}(f-\Pi_df)(M)\right)^2 \le N^{-2K}\frac{1}{\#\mathcal M(V_h)} \sum_{M\in\mathcal M(V_h)}f(M)^2.(9)✦

Let HH be a finite set, z:H×Bool→Fin3z:H\times\mathrm{Bool}\to\mathrm{Fin}\,3 a coloring, d∈ℕd\in\mathbb N a degree, and f∈Pdf\in P_d a matching function. There is a real polynomial QQ of total degree at most dd satisfying (10) for every table tt realized by a matching under zz: 𝒜z,tf=Q(t01,t02,t12).\mathcal A_{z,t}f=Q(t_{01},t_{02},t_{12}).(10)✦

For every finite vertex set VV, coloring z:V→Fin3z:V\to\mathrm{Fin}\,3, table t∈ℕ6t\in\mathbb N^6, and real matching function ff, the permutation energy identity is (11): 1#Sym⁡(V)∑p∈Sym⁡(V)(𝒜z,t[M↦f(p⋅M)])2=ℰs(z)(t;f).\frac{1}{\#\operatorname{Sym}(V)} \sum_{p\in\operatorname{Sym}(V)} \left(\mathcal A_{z,t}[M\mapsto f(p\cdot M)]\right)^2 =\mathcal E_{s(z)}(t;f).(11)✦

In the paper, the result reads: for every real K>0K>0 there are integers d≥1d\ge1 and N0N_0 such that, for every even N≥N0N\ge N_0, positive integers a,b,ca,b,c summing to NN, and nonnegative integers x01,x02,x12x_{01},x_{02},x_{12} for which a−x01−x02a-x_{01}-x_{02}, b−x01−x12b-x_{01}-x_{12}, and c−x02−x12c-x_{02}-x_{12} are nonnegative and even, the operator T(x01,x02,x12)T_{(x_{01},x_{02},x_{12})} of uniform averaging over matchings with these intercell counts, viewed on uniform ordered partitions of these sizes, with II denoting the identity operator on real matching functions, satisfies ∥T(x01,x02,x12)(I−Πd)∥≤N−K\|T_{(x_{01},x_{02},x_{12})}(I-\Pi_d)\|\le N^{-K} uniformly in the sizes and counts, and, for each fixed partition and matching function ff, one polynomial of total degree at most dd in x01,x02,x12x_{01},x_{02},x_{12} gives all values of T(x01,x02,x12)ΠdfT_{(x_{01},x_{02},x_{12})}\Pi_df.

What Is Checked

The smoothing estimates range over natural KK and sufficiently large hh, with all three color cells nonempty on VhV_h. The energy identity allows every finite vertex set and table; the polynomial statement uses paired vertices and realized tables.