Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.9, p. 22 — Spec(M⁺_k) ⊆ {1} ∪ ⋃_j [(k+1−j)/(k+2) ± (√(k+1)/(k+2))ε_k], eigenvectors near U^j_k

Proved
HighOrderWalks.TwoSided.theorem_5_9

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

high-dimensional-expanderlocal-spectral-expansionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-walkspectrum

Let XXX be a pure nnn-dimensional weighted simplicial complex that is a two-sided λ\lambdaλ-local spectral expander, with the constants εk\varepsilon_kεk​ of Theorem 5.6. Assume

εk≤12(1+2(k+1)k+1)  (0≤k≤n−2)andεn−1<12n.\varepsilon_k\le\frac{1}{2\big(1+2(k+1)\sqrt{k+1}\big)}\ \ (0\le k\le n-2)\qquad\text{and}\qquad \varepsilon_{n-1}<\frac{1}{2\sqrt n}.εk​≤2(1+2(k+1)k+1​)1​  (0≤k≤n−2)andεn−1​<2n​1​.

Then for every 0≤k≤n−10\le k\le n-10≤k≤n−1:

  1. the spectrum of the upper random walk Mk+M^+_kMk+​ on Ck(X,R)C^k(X,\mathbb R)Ck(X,R) satisfies
Spec⁡(Mk+)⊆{1}∪⋃j=0k[k+1−jk+2−k+1k+2εk, k+1−jk+2+k+1k+2εk];\operatorname{Spec}(M^+_k)\subseteq\{1\}\cup\bigcup_{j=0}^{k}\Big[\frac{k+1-j}{k+2}-\frac{\sqrt{k+1}}{k+2}\varepsilon_k,\ \frac{k+1-j}{k+2}+\frac{\sqrt{k+1}}{k+2}\varepsilon_k\Big];Spec(Mk+​)⊆{1}∪j=0⋃k​[k+2k+1−j​−k+2k+1​​εk​, k+2k+1−j​+k+2k+1​​εk​];
  1. if ϕ∈C0k(X)\phi\in C^k_0(X)ϕ∈C0k​(X) satisfies Mk+ϕ=μϕM^+_k\phi=\mu\phiMk+​ϕ=μϕ and μ\muμ lies in the jjj-th interval above, then
∥ϕ−PUkjϕ∥≤k+1 εk1−k+1 εk ∥ϕ∥,\big\|\phi-P_{U^j_k}\phi\big\|\le\frac{\sqrt{k+1}\,\varepsilon_k}{1-\sqrt{k+1}\,\varepsilon_k}\,\|\phi\| ,​ϕ−PUkj​​ϕ​≤1−k+1​εk​k+1​εk​​∥ϕ∥,

where PUkjP_{U^j_k}PUkj​​ is the weighted orthogonal projection onto the subspace UkjU^j_kUkj​ of §5.3.

So on a two-sided local spectral expander with small λ\lambdaλ the spectrum of the kkk-th order walk clusters around the k+1k+1k+1 values k+1−jk+2\frac{k+1-j}{k+2}k+2k+1−j​, and each eigenvector lies close to the corresponding space UkjU^j_kUkj​, which is built from lower-dimensional cochains. This is the structural description of high order random walks that goes beyond the second eigenvalue.

Formalization Note. Spec⁡(Mk+)\operatorname{Spec}(M^+_k)Spec(Mk+​) is the set of eigenvalues of Mk+M^+_kMk+​ on the finite-dimensional space Ck(X,R)C^k(X,\mathbb R)Ck(X,R), with Mk+M^+_kMk+​ self-adjoint for the weighted inner product; part 1 is stated for every nonzero ϕ\phiϕ supported on X(k)X(k)X(k) (Supp X (k + 1) φ) with Mk+ϕ=μϕM^+_k\phi=\mu\phiMk+​ϕ=μϕ. Requiring the support excludes functions living off the faces, which would otherwise be spurious eigenvectors with eigenvalue 000. The page leaves kkk implicit; it is quantified inside the conclusion (k+1≤nk+1\le nk+1≤n). εn−1<1/(2n)\varepsilon_{n-1}<1/(2\sqrt n)εn−1​<1/(2n​) is written as ∀ k, k + 1 = n → eps lam k < 1 / (2 * √n), avoiding natural-number subtraction. Both hypotheses on ε\varepsilonε make k+1 εk<1/2\sqrt{k+1}\,\varepsilon_k<1/2k+1​εk​<1/2, so the denominator in part 2 is positive. PUkjϕP_{U^j_k}\phiPUkj​​ϕ is any uuu with IsWProj X m (k + 1) (Usp X m k j) φ u. The constants are those printed on p. 22.

Preamble
import Mathlib
import Definitions.Def_HighOrderWalks_TwoSided_Setting
import Definitions.Def_HighOrderWalks_TwoSided_Subspaces
Formal statement
namespace HighOrderWalks.TwoSided

/-- Theorem 5.9, p. 22: let `X` be a two-sided `λ`-local spectral expander and `ε_k` as in
`eps`. If `ε_k ≤ 1/(2(1 + 2(k+1)√(k+1)))` for all `0 ≤ k ≤ n - 2` and `ε_{n-1} < 1/(2√n)`,
then for every `0 ≤ k ≤ n - 1`:
1. every eigenvalue `μ` of `M⁺_k` on `C^k(X)` is `1` or lies in
   `[(k+1-j)/(k+2) - (√(k+1)/(k+2)) ε_k, (k+1-j)/(k+2) + (√(k+1)/(k+2)) ε_k]` for some
   `0 ≤ j ≤ k`;
2. if `φ ∈ C^k_0(X)`, `M⁺_k φ = μ φ` and `μ` lies in the `j`-th interval, then
   `‖φ - P_{U^j_k} φ‖ ≤ (√(k+1) ε_k / (1 - √(k+1) ε_k)) ‖φ‖`. -/
theorem theorem_5_9 {V : Type*} [DecidableEq V] (X : Finset (Finset V)) (n : ℕ)
    (hX : HighOrderWalks.OneSided.IsPureComplex X n) (m : Finset V → ℝ) (hm : HighOrderWalks.OneSided.IsWeight X n m)
    (lam : ℝ) (hexp : TwoSidedLSE X m n lam)
    (hsmall : ∀ k : ℕ, k + 2 ≤ n →
      eps lam k ≤ 1 / (2 * (1 + 2 * ((k : ℝ) + 1) * Real.sqrt ((k : ℝ) + 1))))
    (hlast : ∀ k : ℕ, k + 1 = n → eps lam k < 1 / (2 * Real.sqrt (n : ℝ))) :
    ∀ k : ℕ, k + 1 ≤ n →
      (∀ μ : ℝ, ∀ φ : Finset V → ℝ, Supp X (k + 1) φ → φ ≠ 0 → HighOrderWalks.OneSided.upperWalk X m φ = μ • φ →
        μ = 1 ∨ ∃ j ≤ k, |μ - ((k : ℝ) + 1 - (j : ℝ)) / ((k : ℝ) + 2)| ≤
          Real.sqrt ((k : ℝ) + 1) / ((k : ℝ) + 2) * eps lam k) ∧
      (∀ j ≤ k, ∀ μ : ℝ, ∀ φ ∈ C0 X m (k + 1), HighOrderWalks.OneSided.upperWalk X m φ = μ • φ →
        |μ - ((k : ℝ) + 1 - (j : ℝ)) / ((k : ℝ) + 2)| ≤
          Real.sqrt ((k : ℝ) + 1) / ((k : ℝ) + 2) * eps lam k →
        ∀ u : Finset V → ℝ, IsWProj X m (k + 1) (Usp X m k j) φ u →
          HighOrderWalks.OneSided.nrm X m (k + 1) (φ - u) ≤
            Real.sqrt ((k : ℝ) + 1) * eps lam k / (1 - Real.sqrt ((k : ℝ) + 1) * eps lam k) *
              HighOrderWalks.OneSided.nrm X m (k + 1) φ) := by sorry

end HighOrderWalks.TwoSided
Source
Kaufman–Oppenheim, High Order Random Walks: Beyond Spectral Gap, arXiv:1707.02799v3, p. 22, Theorem 5.9
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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