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
ProvedHighOrderWalks.TwoSided.theorem_5_9Let be a pure -dimensional weighted simplicial complex that is a two-sided -local spectral expander, with the constants of Theorem 5.6. Assume
Then for every :
- the spectrum of the upper random walk on satisfies
- if satisfies and lies in the -th interval above, then
where is the weighted orthogonal projection onto the subspace of §5.3.
So on a two-sided local spectral expander with small the spectrum of the -th order walk clusters around the values , and each eigenvector lies close to the corresponding space , 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. is the set of eigenvalues of on the finite-dimensional space , with self-adjoint for the weighted inner product; part 1 is stated for every nonzero supported on (Supp X (k + 1) φ) with . Requiring the support excludes functions living off the faces, which would otherwise be spurious eigenvectors with eigenvalue . The page leaves implicit; it is quantified inside the conclusion (). is written as ∀ k, k + 1 = n → eps lam k < 1 / (2 * √n), avoiding natural-number subtraction. Both hypotheses on make , so the denominator in part 2 is positive. is any with IsWProj X m (k + 1) (Usp X m k j) φ u. The constants are those printed on p. 22.
import Mathlib import Definitions.Def_HighOrderWalks_TwoSided_Setting import Definitions.Def_HighOrderWalks_TwoSided_Subspaces
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.