Theorem 1.8 (corrected): for , convergence -Cauchy
ProvedPermLimits.Cauchy.convergent_iff_cauchy_rectangularLet be a permutation sequence with . Then
Here "convergent" means that converges for every permutation , and 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 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 the implication "Cauchy convergent" fails: for and permutations with and , the sequence is -Cauchy, but while . The source's proof begins "By Claim 2.4 we may assume that ", 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.
import Mathlib import Definitions.Def_PermLimits_Shared_PermDensity import Definitions.Def_PermLimits_Cauchy_RectCauchy open PermLimits.Shared
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.