OctoInformBeta

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

Lemma A.3 [Dimensions outside the edge-product span]: For invariant real matching subspaces and eigenspaces of equivariant compressions, for natural numbers h,kh,k satisfying 4k<h4k<h

Lower dimension bounds outside the edge-product span.

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

Functions on perfect matchings carry the action of vertex permutations. The dimension question concerns invariant subspaces that avoid products of a bounded number of edge indicators, and eigenspaces of equivariant operators after orthogonal compression.

Fix h∈ℕh\in\mathbb N and let Vh={0,…,h−1}×{0,1}V_h=\{0,\ldots,h-1\}\times\{0,1\}, with N=2hN=2h vertices.✦ A matching involution MM on VhV_h is a permutation satisfying (1); write ℳh\mathcal M_h for the set of these involutions. M2=id⁡Vh,M(v)≠vfor every v∈Vh.M^2=\operatorname{id}_{V_h}, \qquad M(v)\ne v\quad\text{for every }v\in V_h.(1)✦

The real matching function space ℱh=ℝℳh\mathcal F_h=\mathbb R^{\mathcal M_h} is the vector space of real functions on ℳh\mathcal M_h. The Euclidean matching function space ℋh\mathcal H_h consists of the real functions on ℳh\mathcal M_h with the inner product in (2); its canonical linear identification J:ℋh→ℱhJ:\mathcal H_h\to\mathcal F_h preserves every function value. ⟨f,g⟩=∑M∈ℳhf(M)g(M),(Jf)(M)=f(M).\langle f,g\rangle =\sum_{M\in\mathcal M_h}f(M)g(M), \qquad (Jf)(M)=f(M).(2)

Write rp:ℳh→ℳhr_p:\mathcal M_h\to\mathcal M_h for the matching relabelling permutation given by conjugation by a permutation pp of VhV_h.✦ The matching function action RpR_p on ℱh\mathcal F_h is the linear map defined in (3). (Rpf)(M)=f(rp−1(M))=f(p−1Mp).(R_pf)(M)=f\bigl(r_{p^{-1}}(M)\bigr)=f(p^{-1}Mp).(3)✦

For a permutation ee of a finite set XX, the coordinate permutation isometry UeU_e of ℝX\mathbb R^X with its Euclidean inner product is the linear isometry given by Uef=f∘e−1U_e f=f\circ e^{-1}.✦ The matching relabelling isometry UpU_p on ℋh\mathcal H_h is UrpU_{r_p}.✦

Edge Products and Compression

The edge indicator x(u,v):ℳh→ℝx_{(u,v)}:\mathcal M_h\to\mathbb R of an ordered pair (u,v)∈Vh×Vh(u,v)\in V_h\times V_h is x(u,v)(M)=𝟏{M(u)=v}x_{(u,v)}(M)=\mathbf 1_{\{M(u)=v\}}.✦ For a nonnegative integer dd and a family x=(xe)e∈Ex=(x_e)_{e\in E} of real functions on a set XX, the degree-bounded span Ld(x)⊆ℝXL_d(x)\subseteq\mathbb R^X is the real linear span in (4), with the empty product equal to the constant function 11. Ld(x)=span⁡ℝ{∏i=1mxei:0≤m≤d,(e1,…,em)∈Em}.L_d(x)=\operatorname{span}_{\mathbb R} \left\{\prod_{i=1}^{m}x_{e_i}: 0\le m\le d,\ (e_1,\ldots,e_m)\in E^m\right\}.(4)✦

The edge-product span Pd⊆ℋhP_d\subseteq\mathcal H_h is the matching polynomial space defined by (5), using the family of edge indicators; let Πd\Pi_d denote orthogonal projection onto PdP_d. Pd=J−1(Ld(x)),x=(x(u,v))(u,v)∈Vh×Vh.P_d=J^{-1}\bigl(L_d(x)\bigr), \qquad x=(x_{(u,v)})_{(u,v)\in V_h\times V_h}.(5)✦

For a linear operator AA on a finite-dimensional real inner product space and a linear subspace SS, the orthogonal compression Comp⁡S(A)\operatorname{Comp}_S(A) is the operator on SS defined in (6), where ΠS\Pi_S is orthogonal projection onto SS. Comp⁡S(A)=ΠSA|S.\operatorname{Comp}_S(A)=\Pi_S A\big|_S.(6)✦

The Claim

Theorem 1. Let h,k∈ℕh,k\in\mathbb N satisfy 4k<h4k<h, and set d=(4k)2d=(4k)^2.

Let W⊆ℱhW\subseteq\mathcal F_h be a nonzero real linear subspace invariant under every RpR_p, and suppose W∩J(Pd)={0}W\cap J(P_d)=\{0\}. Then dim⁡ℝW≥(hk).\dim_{\mathbb R}W\ge\binom hk.(7)✦

Let W⊆ℋhW\subseteq\mathcal H_h be a nonzero real linear subspace invariant under every UpU_p, and suppose W⊆Pd⟂W\subseteq P_d^\perp. Then dim⁡ℝW≥(hk).\dim_{\mathbb R}W\ge\binom hk.(8)✦

Let A:ℋh→ℋhA:\mathcal H_h\to\mathcal H_h be a real linear operator commuting with every UpU_p, and let c∈ℝc\in\mathbb R be an eigenvalue of Comp⁡Pd⟂(A)\operatorname{Comp}_{P_d^\perp}(A). Then dim⁡ℝker⁡(Comp⁡Pd⟂(A)−cIPd⟂)≥(hk).\dim_{\mathbb R} \ker\!\left(\operatorname{Comp}_{P_d^\perp}(A) -cI_{P_d^\perp}\right) \ge\binom hk.(9)✦

In the paper, the result reads: for each fixed integer d≥1d\ge1 and all sufficiently large NN, every irreducible constituent of the complexification of Pd⟂P_d^\perp has dimension at least cdNd/2c_dN^{d/2}, where cd=1/(2dd!)c_d=1/(2^d d!).

What Is Checked

Bounds (7) and (8) concern invariant real matching subspaces, with disjointness from J(Pd)J(P_d) and containment in Pd⟂P_d^\perp, respectively, while (9) concerns the eigenspaces of orthogonal compressions of equivariant real linear operators.