finite_partition_permutation_of_fiber_card
For two maps p,b from Fin n to Fin q whose corresponding fibers have equal cardinality, there is a permutation sigma of Fin n such that p(sigma v)=b(v) for every vertex.
Statement
theorem finite_partition_permutation_of_fiber_card {n q : ℕ} (p b : Fin n → Fin q) (h : ∀ t, ((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card = ((Finset.univ : Finset (Fin n)).filter (fun v => b v = t)).card) : ∃ σ : Equiv.Perm (Fin n), ∀ v, p (σ v) = b v
- Source
- Certificate-soundness and finite averaging helpers for the OP-306 campaign on arXiv:2610.22142, Sections 3.3.1 and 3.3.2. The thirteen-vertex equivalence is a reduction, not a proof of the conjectured equality; the moment criterion supplies no unproved universal numerical hypothesis.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- wild_complete_thirteen_partition_templateFor every partition p of thirteen vertices into four labeled blocks of size at least three, there are vertex and block-label permutations…
The proof, explained
The maps b and p partition the finite set Fin n into fibers over Fin q. Because corresponding fibers have equal cardinality by assumption, there is a bijection between each fiber of b and the corresponding fiber of p. Gluing these fiberwise bijections together yields a global permutation σ of Fin n satisfying p(σ v) = b v for all v.
For each target value t ∈ Fin q, there is a bijection between the fiber {v | b v = t} and the fiber {v | p v = t}.
The hypothesis h asserts that for every t, the fibers {v | p v = t} and {v | b v = t} have equal cardinality as filtered finsets. Applying Fintype.card_subtype identifies these finset sizes with the cardinalities of the respective subtype fibers. Since any two finite types with equal cardinality admit a bijection via Fintype.equivOfCardEq, this yields a family of fiberwise bijections E(t) : {v // b v = t} ≃ {v // p v = t}.
uses
Fintype.equivOfCardEq,Fintype.card_subtypeclassical let E : ∀ t : Fin q, {v // b v = t} ≃ {v // p v = t} := fun t => Fintype.equivOfCardEq (by simpa only [Fintype.card_subtype] using (h t).symm)
There exists a permutation σ of Fin n such that p(σ v) = b v for all v.
Gluing the family of fiberwise bijections E together via Equiv.ofFiberEquiv produces an equivalence σ from Fin n to Fin n (that is, a permutation of Fin n). By Equiv.ofFiberEquiv_map, this permutation satisfies p (σ v) = b v for every v, which satisfies the existential goal.
uses
Equiv.ofFiberEquiv,Equiv.ofFiberEquiv_mapexact ⟨Equiv.ofFiberEquiv E,Equiv.ofFiberEquiv_map E⟩
Fintype.card_subtype- The cardinality of a subtype {x // P x} as a finite type equals the cardinality of the filtered finset {x | P x}.
Fintype.equivOfCardEq- Two finite types with the same cardinality are equivalent (in bijection).
Equiv.ofFiberEquiv- A family of bijections between the corresponding fibers of two maps f : α → γ and g : β → γ over all elements of γ induces a global equivalence between α and β.
Equiv.ofFiberEquiv_map- The global equivalence induced by fiberwise bijections sends each element a to an element whose image under the second map equals the image of a under the first map.
- In Lean, the theorem statement expresses fiber size using finset filtering (Finset.filter), whereas the fiber-gluing construction operates on subtypes ({v // b v = t}). The lemma Fintype.card_subtype bridges this formal distinction.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem finite_partition_permutation_of_fiber_card {n q : ℕ} (p b : Fin n → Fin q) (h : ∀ t, ((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card = ((Finset.univ : Finset (Fin n)).filter (fun v => b v = t)).card) : ∃ σ : Equiv.Perm (Fin n), ∀ v, p (σ v) = b v := by classical let E : ∀ t : Fin q, {v // b v = t} ≃ {v // p v = t} := fun t => Fintype.equivOfCardEq (by simpa only [Fintype.card_subtype] using (h t).symm) exact ⟨Equiv.ofFiberEquiv E,Equiv.ofFiberEquiv_map E⟩