buchholz_pairing_equiv_two_cycle_type
Provedbuchholzcandes-rechtcycle-typeexact-matrix-completion
For each integer , the type BuchholzPairing n represents pair partitions of labelled positions as fixed-point-free involutions.
This theorem asserts that such pairings are equivalent to the subtype of permutations of Fin (2 * n) whose cycle type is exactly , i.e. disjoint cycles of length :
This is the structural reason the Buchholz pair-count constant is the usual count of fixed-point-free involutions.
Preamble
import Definitions.Def_buchholz_pairing import Mathlib.GroupTheory.Perm.Centralizer open MatrixCompletion
Formal statement
theorem buchholz_pairing_equiv_two_cycle_type (n : Nat) :
Nonempty (BuchholzPairing n ≃
{g : Equiv.Perm (Fin (2 * n)) //
g.cycleType = Multiset.replicate n 2}) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.