AFTD Auto-Formalizing Theoretical Domains

finite_partition_permutation_of_fiber_card

theoremverified

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

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.

  1. 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}.

    lines 9–11

    uses Fintype.equivOfCardEq, Fintype.card_subtype

      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)
  2. 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.

    line 12

    uses Equiv.ofFiberEquiv, Equiv.ofFiberEquiv_map

      exact ⟨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.

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

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⟩
See it in the graphDiscuss this resultChallenge it