Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.6: convergent permutation sequences have limit permutations, and every limit permutation is a limit

Proved
PermLimits.Existence.limit_permutation_exists_and_realized

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1permutation-limits

Theorem 1.6 (Main result).

  1. Given a convergent permutation sequence (σn)n∈N(\sigma_n)_{n\in\mathbb N}(σn​)n∈N​ for which ∣σn∣→∞|\sigma_n|\to\infty∣σn​∣→∞, there exists a limit permutation Z∈ZZ\in\mathcal ZZ∈Z such that σn→Z\sigma_n\to Zσn​→Z.
  2. Conversely, every Z∈ZZ\in\mathcal ZZ∈Z is a limit of a convergent permutation sequence: there is a sequence (σn)n∈N(\sigma_n)_{n\in\mathbb N}(σn​)n∈N​ such that σn→Z\sigma_n\to Zσn​→Z.

Here a sequence is convergent if every pattern density t(τ,σn)t(\tau,\sigma_n)t(τ,σn​) converges, and σn→Z\sigma_n\to Zσn​→Z means ∣σn∣→∞|\sigma_n|\to\infty∣σn​∣→∞ and

lim⁡n→∞t(τ,σn)=t(τ,Z)for every permutation τ.\lim_{n\to\infty}t(\tau,\sigma_n)=t(\tau,Z)\qquad\text{for every permutation }\tau .n→∞lim​t(τ,σn​)=t(τ,Z)for every permutation τ.

The theorem identifies Z\mathcal ZZ as the space of limits of permutation sequences, the permutation analogue of the Lovász–Szegedy theorem that graphons are the limits of dense graph sequences.

Formalization Note Both parts form one conjunction. In part 2 the sequence consists of genuine permutations, each of length at least 111. σn→Z\sigma_n\to Zσn​→Z includes ∣σn∣→∞|\sigma_n|\to\infty∣σn​∣→∞ and implies that the sequence is convergent.

Preamble
import Mathlib
import Definitions.Def_PermLimits_Shared_PermDensity
import Definitions.Def_PermLimits_Shared_LimitPermutation
import Definitions.Def_PermLimits_Shared_ConvergesTo
open PermLimits.Shared
Formal statement
namespace PermLimits.Existence

open Filter unitInterval

/-- **Theorem 1.6 (Main result)** (Hoppen et al., *Limits of permutation sequences*,
arXiv:1103.5844v2, p. 4).
(i) Given a convergent permutation sequence `(σ_m)` for which `|σ_m| → ∞`, there exists a limit
permutation `Z` such that `σ_m → Z`.
(ii) Conversely, every `Z ∈ 𝒵` is a limit of a convergent permutation sequence, i.e. there is a
sequence `(σ_m)` such that `σ_m → Z`.

**Formalization Note.** The two parts are one conjunction. Convergence of the sequence
(Definition 1.2, `IsConvergent`) is the hypothesis of (i), and `σ_m → Z` (Definition 1.5,
`ConvergesTo`, which includes `|σ_m| → ∞`) its conclusion. In (ii) the sequence consists of
genuine permutations, `|σ_m| ≥ 1` (the paper's `S_n` has `n ≥ 1`); `σ_m → Z` implies that the
sequence is convergent. Sequences are named `s` (`σ` is reserved notation once `unitInterval` is
opened). -/
theorem limit_permutation_exists_and_realized :
    (∀ s : ℕ → Σ n : ℕ, Equiv.Perm (Fin n), IsConvergent s →
        Tendsto (fun m => (s m).1) atTop atTop →
        ∃ Z : I → I → ℝ, IsLimitPerm Z ∧ ConvergesTo s Z) ∧
    (∀ Z : I → I → ℝ, IsLimitPerm Z →
        ∃ s : ℕ → Σ n : ℕ, Equiv.Perm (Fin n), (∀ m, 1 ≤ (s m).1) ∧ ConvergesTo s Z) := by sorry

end PermLimits.Existence
Source
Hoppen, Kohayakawa, Moreira, Ráth, Sampaio, Limits of permutation sequences, arXiv:1103.5844v2, https://arxiv.org/abs/1103.5844v2, p. 4, Theorem 1.6
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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