Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem (1.4), p. 16 — Mixing Lemma: ||F(A_0,…,A_d)| − α|A_0|⋯|A_d|/n| ≤ ρ_α(|A_0|⋯|A_d|)^{d/(d+1)}

Proved
SimplicialIso.Mixing.theorem_1_4

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

discrepancymixing-lemmap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplicial-complexspectral-theory

Theorem (1.4) (Mixing Lemma). Let XXX be a ddd-dimensional complex with a complete skeleton on nnn vertices, d≥1d\ge1d≥1, and fix α∈R\alpha\in\mathbb Rα∈R. Let

ρα=max⁡{∣μ∣  ∣  μ∈Spec⁡(αI−Δ+)∣Zd−1}=∥(αI−Δ+)∣Zd−1∥,\rho_\alpha=\max\bigl\{|\mu|\;\big|\;\mu\in\operatorname{Spec}(\alpha I-\Delta^+)\big|_{Z_{d-1}}\bigr\}=\bigl\|(\alpha I-\Delta^+)\big|_{Z_{d-1}}\bigr\|,ρα​=max{∣μ∣​μ∈Spec(αI−Δ+)​Zd−1​​}=​(αI−Δ+)​Zd−1​​​,

the largest absolute value of an eigenvalue of αI−Δ+\alpha I-\Delta^+αI−Δ+ on the (d−1)(d-1)(d−1)-cycles. For any pairwise disjoint sets of vertices A0,…,AdA_0,\dots,A_dA0​,…,Ad​ (not necessarily a partition),

∣ ∣F(A0,…,Ad)∣−α⋅∣A0∣⋯∣Ad∣n∣≤ρα⋅(∣A0∣⋯∣Ad∣)dd+1.\left|\,|F(A_0,\dots,A_d)|-\frac{\alpha\cdot|A_0|\cdots|A_d|}{n}\right|\le\rho_\alpha\cdot\bigl(|A_0|\cdots|A_d|\bigr)^{\frac d{d+1}}.​∣F(A0​,…,Ad​)∣−nα⋅∣A0​∣⋯∣Ad​∣​​≤ρα​⋅(∣A0​∣⋯∣Ad​∣)d+1d​.

Here F(A0,…,Ad)F(A_0,\dots,A_d)F(A0​,…,Ad​) is the set of ddd-cells with exactly one vertex in each AiA_iAi​. The theorem generalizes the Expander Mixing Lemma of graphs (d=1d=1d=1): the number of ddd-cells across d+1d+1d+1 disjoint vertex sets is close to its expected value α∏∣Ai∣/n\alpha\prod|A_i|/nα∏∣Ai​∣/n, with an error controlled by the spectrum of the upper Laplacian.

Formalization Note. d≥1d\ge1d≥1 is added (the Laplacians act on Ωd−1\Omega^{d-1}Ωd−1). ρα\rho_\alphaρα​ is not defined as a maximum: the statement is made for every ρ\rhoρ with ∣μ∣≤ρ|\mu|\le\rho∣μ∣≤ρ for all eigenvalues μ\muμ of αI−Δ+\alpha I-\Delta^+αI−Δ+ on Zd−1Z_{d-1}Zd−1​, which is equivalent to the statement for ρα\rho_\alphaρα​ (the maximum is such a ρ\rhoρ, and any such ρ\rhoρ is at least the maximum); an empty eigenvalue set cannot make it trivially true through a default value. The page's first expression max⁡{∣μ(n−1d−1)∣,∣μm∣}\max\{|\mu_{\binom{n-1}{d-1}}|,|\mu_m|\}max{∣μ(d−1n−1​)​∣,∣μm​∣} for ρα\rho_\alphaρα​ relies on Proposition 3.3 and equals the one used, by (4.10). No hypothesis n≥d+1n\ge d+1n≥d+1 is needed: if n≤dn\le dn≤d, some AiA_iAi​ is empty and both sides are 000. The power is Real.rpow with exponent d/(d+1)d/(d+1)d/(d+1) computed in R\mathbb RR.

Preamble
import Mathlib
import Definitions.Def_SimplicialIso_Mixing_Setting
Formal statement
namespace SimplicialIso.Mixing

open Finset
open scoped InnerProductSpace

/-- Theorem (1.4), p. 16 (the Mixing Lemma, precise form): for a `d`-complex `X` with a complete
skeleton, `α ∈ ℝ`, disjoint vertex sets `A_0, …, A_d` (not necessarily a partition), and any `ρ`
bounding the absolute value of every eigenvalue of `αI − Δ⁺` on `Z_{d-1}` (in particular
`ρ = ρ_α = ‖(αI − Δ⁺)|_{Z_{d-1}}‖`),
`| |F(A_0, …, A_d)| − α |A_0| ⋯ |A_d| / n | ≤ ρ (|A_0| ⋯ |A_d|)^{d/(d+1)}`. -/
theorem theorem_1_4 (n d : ℕ) (hd : 1 ≤ d) (X : Complex n d) (α : ℝ)
    (A : Fin (d + 1) → Finset (Fin n)) (hA : Pairwise (fun i j => Disjoint (A i) (A j))) (ρ : ℝ)
    (hρ : ∀ μ, IsCycleEigenvalue (α • LinearMap.id - upLap X) μ → |μ| ≤ ρ) :
    |((F X A).card : ℝ) - α * (∏ i, ((A i).card : ℝ)) / n| ≤
      ρ * (∏ i, ((A i).card : ℝ)) ^ ((d : ℝ) / (d + 1)) := by sorry

end SimplicialIso.Mixing
Source
Parzanchevski, Rosenthal and Tessler, Isoperimetric inequalities in simplicial complexes, arXiv:1207.0638v3, §4.3, p. 16, Theorem (1.4) (precise form of Theorem 1.4, p. 4)
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