Lemma 3.5:
ProvedPermLimits.Cauchy.density_stepLimit_closecombinatoricsp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1permutation-limits
Let and with . Then
Densities of a permutation and of its step limit permutation agree up to , so for sequences with the two families of densities have the same limits. This is what lets the whole theory be run on .
Formalization Note is assumed, as in the source ( for a positive integer ); with it gives . The source's permutation is named ; the Lean statement calls it because is reserved notation.
Preamble
import Mathlib import Definitions.Def_PermLimits_Shared_PermDensity import Definitions.Def_PermLimits_Shared_LimitMeasure import Definitions.Def_PermLimits_Shared_StepLimit open PermLimits.Shared
Formal statement
namespace PermLimits.Cauchy
open unitInterval
/-- **Lemma 3.5** (Hoppen et al., *Limits of permutation sequences*, arXiv:1103.5844v2, p. 11).
Let `τ ∈ S_k`, `π ∈ S_n`, `k ≤ n`. Then `|t(τ, π) − t(τ, Z_π)| ≤ (1/n) · C(k, 2)` (Eq. (27)).
**Formalization Note.** The paper's permutation is called `σ`; here `π` (`σ` is reserved notation
once `unitInterval` is opened). `k ≥ 1` is the paper's standing convention that `τ ∈ S_k` for a
positive integer `k` (Definition 1.1); with `k ≤ n` it gives `n ≥ 1`, so `1/n` is a genuine
quotient. -/
theorem density_stepLimit_close {k n : ℕ} (τ : Equiv.Perm (Fin k)) (π : Equiv.Perm (Fin n))
(hk : 0 < k) (hkn : k ≤ n) :
|permDensity τ π - limitDensity τ (stepLimit π)| ≤ (1 / (n : ℝ)) * (Nat.choose k 2 : ℝ) := by sorry
end PermLimits.Cauchy
Source
Hoppen, Kohayakawa, Moreira, Ráth, Sampaio, Limits of permutation sequences, arXiv:1103.5844v2, https://arxiv.org/abs/1103.5844v2, p. 11, Lemma 3.5 (Eq. (27))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.