Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.8 (corrected): for ∣σn∣→∞|\sigma_n|\to\infty∣σn​∣→∞, convergence   ⟺  \iff⟺d□d_\squared□​-Cauchy

Proved
PermLimits.Cauchy.convergent_iff_cauchy_rectangular

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

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

Let (σn)n∈N(\sigma_n)_{n\in\mathbb N}(σn​)n∈N​ be a permutation sequence with ∣σn∣→∞|\sigma_n|\to\infty∣σn​∣→∞. Then

(σn) is convergent  ⟺  (σn) is a Cauchy sequence with respect to d□.(\sigma_n)\ \text{is convergent}\iff (\sigma_n)\ \text{is a Cauchy sequence with respect to } d_\square .(σn​) is convergent⟺(σn​) is a Cauchy sequence with respect to d□​.

Here "convergent" means that t(τ,σn)t(\tau,\sigma_n)t(τ,σn​) converges for every permutation τ\tauτ, and d□(σ,π)=d□(Zσ,Zπ)d_\square(\sigma,\pi)=d_\square(Z_\sigma,Z_\pi)d□​(σ,π)=d□​(Zσ​,Zπ​) is the rectangular distance between permutations of possibly different lengths. The theorem identifies convergence defined by pattern densities with a purely metric notion; it is the statement that the completion of (S,d□)(\mathcal S,d_\square)(S,d□​) is the space of limit permutations up to almost-everywhere equality.

Formalization Note (correction) The source states Theorem 1.8 for every permutation sequence. Without ∣σn∣→∞|\sigma_n|\to\infty∣σn​∣→∞ the implication "Cauchy ⇒\Rightarrow⇒ convergent" fails: for σ=(1,2)∈S2\sigma=(1,2)\in S_2σ=(1,2)∈S2​ and permutations τk\tau_kτk​ with ∣τk∣→∞|\tau_k|\to\infty∣τk​∣→∞ and d□(Zτk,Zσ)→0d_\square(Z_{\tau_k},Z_\sigma)\to0d□​(Zτk​​,Zσ​)→0, the sequence σ,τ1,σ,τ2,…\sigma,\tau_1,\sigma,\tau_2,\dotsσ,τ1​,σ,τ2​,… is d□d_\squared□​-Cauchy, but t(σ,σ)=1t(\sigma,\sigma)=1t(σ,σ)=1 while t(σ,τk)→t(σ,Zσ)=3/4t(\sigma,\tau_k)\to t(\sigma,Z_\sigma)=3/4t(σ,τk​)→t(σ,Zσ​)=3/4. The source's proof begins "By Claim 2.4 we may assume that ∣σn∣→∞|\sigma_n|\to\infty∣σn​∣→∞", which is valid only for the other implication; that implication is stated without the length assumption as a separate theorem. "Convergent" does not assert the existence of a limit permutation.

Preamble
import Mathlib
import Definitions.Def_PermLimits_Shared_PermDensity
import Definitions.Def_PermLimits_Cauchy_RectCauchy
open PermLimits.Shared
Formal statement
namespace PermLimits.Cauchy

open Filter

/-- **Theorem 1.8, corrected** (Hoppen et al., *Limits of permutation sequences*,
arXiv:1103.5844v2, p. 5; proof p. 18). A permutation sequence `(σ_n)` with `|σ_n| → ∞` converges
(Definition 1.2) if and only if it is a Cauchy sequence with respect to the metric `d□`.

**Formalization Note (correction).** The paper states Theorem 1.8 for every permutation sequence.
Without `|σ_n| → ∞` the "if" direction is false: for `σ = id ∈ S₂` and permutations `τ_k` with
`|τ_k| → ∞` and `d□(Z_{τ_k}, Z_σ) → 0` (which exist by Lemma 4.2), the sequence
`σ, τ₁, σ, τ₂, …` is `d□`-Cauchy, while `t(σ, σ) = 1` and `t(σ, τ_k) → t(σ, Z_σ) = 3/4`, so it
is not convergent. The paper's reduction "By Claim 2.4 we may assume that `|σ_n| → ∞`" (p. 18) is
valid only for the "only if" direction, which is stated without the length hypothesis as the
separate theorem `cauchy_of_convergent`. "Converges" is Definition 1.2 (`IsConvergent`: every
density sequence converges); it does not assert a limit permutation. `d□` on permutations of
different lengths is `d□(Z_σ, Z_π)` (`permRectDist`, Sect. 4.1, pp. 12–13). The sequence is named
`s`. -/
theorem convergent_iff_cauchy_rectangular (s : ℕ → Σ n : ℕ, Equiv.Perm (Fin n))
    (hs : Tendsto (fun n => (s n).1) atTop atTop) :
    IsConvergent s ↔ IsRectCauchy s := 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. 5, Theorem 1.8 (and the definition of a Cauchy sequence above it); proof p. 18
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 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