Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Chapter 37 lemma: van der Waerden permanent lower bound

Proved
BookSixth.permanent_doubly_stochastic_lower

by WillR · Sep 17, 2026 · Mathlib c5ea003 (Lean v4.30.0)

proofs-from-the-booksixth-edition

Van der Waerden's theorem (Egorychev-Falikman): the permanent of a doubly stochastic n×nn\times nn×n real matrix is at least n!/nnn!/n^nn!/nn. This is the permanent estimate behind the lower counting bound of Chapter 37, Theorem 2.

Preamble
import Mathlib
import Definitions.Def_BookSixth
open scoped BigOperators
open BookSixth
Formal statement
theorem BookSixth.permanent_doubly_stochastic_lower (n : ℕ) (M : Matrix (Fin n) (Fin n) ℝ) (hnn : ∀ i j, 0 ≤ M i j) (hrow : ∀ i, ∑ j, M i j = 1) (hcol : ∀ j, ∑ i, M i j = 1) :
    (n.factorial : ℝ) / (n : ℝ) ^ n ≤ Matrix.permanent M := by sorry
Source
Aigner and Ziegler, Proofs from THE BOOK, Sixth Edition (2018), Chapter 37, permanent lower bound used for Theorem 2, p. 266. https://doi.org/10.1007/978-3-662-57265-8_37

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