Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 8.6 — supp νₘ ⊆ [−ρₘ, ρₘ] for random regular graphs

Proved
StrongConv.supp_subset_Icc_rhoStair_of_extends_nuAdj

by dbenbenn · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

random-matricesrandom-permutationsrandom-regular-graphsstrong-convergence

Let d≥2d \ge 2d≥2 and 0≤m≤d0 \le m \le d0≤m≤d. If μ\muμ is a compactly supported distribution (Definition 4.6) that agrees on real polynomials with the mmm-th coefficient νm\nu_mνm​ of the expansion of E[trN h(AN)]\mathbf E[\mathrm{tr}_N\, h(A^N)]E[trN​h(AN)] in powers of 1/N1/N1/N (nuAdj d m), then supp⁡μ⊆[−ρm,ρm]\operatorname{supp}\mu \subseteq [-\rho_m, \rho_m]suppμ⊆[−ρm​,ρm​]. Here ρm=22d−1\rho_m = 2\sqrt{2d-1}ρm​=22d−1​ if 2m−1≤2d−12m - 1 \le \sqrt{2d-1}2m−1≤2d−1​ and ρm=2m−1+2d−12m−1\rho_m = 2m - 1 + \frac{2d-1}{2m-1}ρm​=2m−1+2m−12d−1​ otherwise. The paper's νm\nu_mνm​ are the distributions of Theorem 7.1, the unique extensions (Lemma 4.7); the statement is phrased for every extension.

Preamble
import Mathlib
import Definitions.Def_StrongConv

open Polynomial
Formal statement
namespace StrongConv

theorem supp_subset_Icc_rhoStair_of_extends_nuAdj (d : ℕ) (hd : 2 ≤ d) (m : ℕ) (hm : m ≤ d)
    (μ : smoothFun →ₗ[ℝ] ℝ) (hμ : IsCSDistribution μ)
    (hext : ∀ h : ℝ[X], μ (polyFun h) = nuAdj d m h) :
    supp μ ⊆ Set.Icc (-rhoStair d m) (rhoStair d m) := by
  sorry

end StrongConv
Source
Chen, C.-F., Garza-Vargas, J., Tropp, J. A. and van Handel, R., A new approach to strong convergence, Ann. of Math. (2) 203 (2026) 555–602, https://doi.org/10.4007/annals.2026.203.2.4 (arXiv:2405.16026v3, whose page numbers are used), p. 26, Corollary 8.6
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

What the statement asserts

Let ddd and mmm be natural numbers with d≥2d \ge 2d≥2 and m≤dm \le dm≤d (so m=0m = 0m=0 is allowed). Let μ\muμ be a real-linear functional on C∞(R)C^\infty(\mathbb R)C∞(R), the real vector space of all infinitely differentiable functions R→R\mathbb R \to \mathbb RR→R (no support or growth condition). Assume:

  1. μ\muμ is a finite-order distribution controlled on a compact interval: there are reals c>0c > 0c>0, K>0K > 0K>0 and a natural number kkk with
∣μ(f)∣  ≤  c∑j=0ksup⁡x∈[−K,K]∣f(j)(x)∣for all f∈C∞(R).|\mu(f)| \;\le\; c \sum_{j=0}^{k} \sup_{x \in [-K,K]} \bigl| f^{(j)}(x) \bigr| \qquad \text{for all } f \in C^\infty(\mathbb R).∣μ(f)∣≤cj=0∑k​x∈[−K,K]sup​​f(j)(x)​for all f∈C∞(R).
  1. μ\muμ agrees with the mmm-th asymptotic coefficient on polynomials: for every real polynomial p∈R[x]p \in \mathbb R[x]p∈R[x], viewed as the smooth function x↦p(x)x \mapsto p(x)x↦p(x),
μ(p)=am(p),\mu(p) = a_m(p),μ(p)=am​(p),

with ama_mam​ as defined below (it depends on ddd).

Then

supp⁡μ  ⊆  [−ρ(d,m),  ρ(d,m)],\operatorname{supp}\mu \;\subseteq\; \bigl[-\rho(d,m),\; \rho(d,m)\bigr],suppμ⊆[−ρ(d,m),ρ(d,m)],

a closed interval, where

ρ(d,m)={22d−1if 2m−1≤2d−1,(2m−1)+2d−12m−1if 2m−1>2d−1.\rho(d,m) = \begin{cases} 2\sqrt{2d-1} & \text{if } 2m-1 \le \sqrt{2d-1},\\[4pt] (2m-1) + \dfrac{2d-1}{2m-1} & \text{if } 2m-1 > \sqrt{2d-1}. \end{cases}ρ(d,m)=⎩⎨⎧​22d−1​(2m−1)+2m−12d−1​​if 2m−1≤2d−1​,if 2m−1>2d−1​.​

All arithmetic here is in the real numbers (2m−1=−12m-1 = -12m−1=−1 when m=0m = 0m=0, no truncation), and ⋅\sqrt{\cdot}⋅​ is the nonnegative square root. Since d≥2d \ge 2d≥2, 2d−1≥32d - 1 \ge 32d−1≥3; in the second case 2m−1>02m-1 > 02m−1>0, so the denominator is positive; and ρ(d,m)>0\rho(d,m) > 0ρ(d,m)>0 in both cases. For m=0m = 0m=0 the first case applies, giving ρ(d,0)=22d−1\rho(d,0) = 2\sqrt{2d-1}ρ(d,0)=22d−1​.

The objects, in full

Support. Say that a set A⊆RA \subseteq \mathbb RA⊆R carries μ\muμ if μ(f)=0\mu(f) = 0μ(f)=0 for every f∈C∞(R)f \in C^\infty(\mathbb R)f∈C∞(R) that vanishes identically on some open set containing AAA. supp⁡μ\operatorname{supp}\musuppμ is the intersection of all closed sets that carry μ\muμ (the whole line always carries μ\muμ, so the family is nonempty).

The random operator AσA_\sigmaAσ​. For N≥0N \ge 0N≥0 let VN={x∈CN:∑jxj=0}V_N = \{x \in \mathbb C^N : \sum_j x_j = 0\}VN​={x∈CN:∑j​xj​=0}, the orthogonal complement of the all-ones vector in CN\mathbb C^NCN (dimension N−1N-1N−1 for N≥1N \ge 1N≥1; V0={0}V_0 = \{0\}V0​={0}). For a permutation π\piπ of {1,…,N}\{1,\dots,N\}{1,…,N}, PπP_\piPπ​ is the permutation operator with Pπei=eπ(i)P_\pi e_i = e_{\pi(i)}Pπ​ei​=eπ(i)​, and SπS_\piSπ​ its restriction to VNV_NVN​. For σ=(σ1,…,σd)∈Sym(N)d\sigma = (\sigma_1,\dots,\sigma_d) \in \mathrm{Sym}(N)^dσ=(σ1​,…,σd​)∈Sym(N)d,

Aσ=∑i=1d(Sσi+Sσi∗)on VN,A_\sigma = \sum_{i=1}^{d} \bigl( S_{\sigma_i} + S_{\sigma_i}^{*} \bigr) \quad\text{on } V_N,Aσ​=i=1∑d​(Sσi​​+Sσi​∗​)on VN​,

with S∗S^{*}S∗ the adjoint within VNV_NVN​. AσA_\sigmaAσ​ is self-adjoint, and for a polynomial ppp, p(Aσ)p(A_\sigma)p(Aσ​) is the usual polynomial in AσA_\sigmaAσ​ (formally defined by the continuous functional calculus applied to z↦p(Re⁡z)z \mapsto p(\operatorname{Re} z)z↦p(Rez), which agrees with it).

The sequence Fp(N)F_p(N)Fp​(N). For a real polynomial ppp and N∈NN \in \mathbb NN∈N,

Fp(N)=1(N!)d∑σ∈Sym(N)dRe⁡Tr⁡(p(Aσ))N,F_p(N) = \frac{1}{(N!)^d} \sum_{\sigma \in \mathrm{Sym}(N)^d} \frac{\operatorname{Re}\operatorname{Tr}\bigl(p(A_\sigma)\bigr)}{N},Fp​(N)=(N!)d1​σ∈Sym(N)d∑​NReTr(p(Aσ​))​,

the average over independent uniform σ1,…,σd\sigma_1,\dots,\sigma_dσ1​,…,σd​ of the trace on VNV_NVN​ divided by NNN (not N−1N-1N−1); division by 000 gives 000, so Fp(0)=0F_p(0) = 0Fp​(0)=0.

The coefficients ai(p)a_i(p)ai​(p). Defined recursively for i=0,1,2,…i = 0, 1, 2, \dotsi=0,1,2,… by

ai(p)=lim⁡N→∞Ni(Fp(N)−∑j=0i−1aj(p)Nj),a_i(p) = \lim_{N \to \infty} N^{i} \Bigl( F_p(N) - \sum_{j=0}^{i-1} \frac{a_j(p)}{N^{j}} \Bigr),ai​(p)=N→∞lim​Ni(Fp​(N)−j=0∑i−1​Njaj​(p)​),

limits over natural numbers N→∞N \to \inftyN→∞; in particular a0(p)=lim⁡NFp(N)a_0(p) = \lim_N F_p(N)a0​(p)=limN​Fp​(N) and a1(p)=lim⁡NN (Fp(N)−a0(p))a_1(p) = \lim_N N\,(F_p(N) - a_0(p))a1​(p)=limN​N(Fp​(N)−a0​(p)). If a limit does not exist, the corresponding value is an unspecified real number (a fixed but arbitrary choice made by the formal system), not 000 and not "undefined", and later coefficients are computed from that value.

Edge cases and caveats

  • m=0m = 0m=0 is included: hypothesis 2 then says μ(p)=lim⁡NFp(N)\mu(p) = \lim_N F_p(N)μ(p)=limN​Fp​(N), and the interval is [−22d−1,22d−1][-2\sqrt{2d-1}, 2\sqrt{2d-1}][−22d−1​,22d−1​].
  • m=dm = dm=d is the largest allowed value; m>dm > dm>d is excluded by hypothesis.
  • Hypothesis 2 may be unsatisfiable. μ\muμ is linear, so hypothesis 2 forces p↦am(p)p \mapsto a_m(p)p↦am​(p) to be linear on polynomials and to obey the bound of hypothesis 1 there. If some limit in the recursion fails to exist, the values are unspecified, and whether any μ\muμ meets hypothesis 2 is not determined by the statement; when no such μ\muμ exists the statement holds vacuously.
  • μ\muμ is fixed only on polynomials. On other smooth functions it is constrained only by linearity and hypothesis 1.
  • The constant KKK of hypothesis 1 does not appear in the conclusion.
Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by dbenbenn · Nov 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me