AFTD Auto-Formalizing Theoretical Domains

forest_symmetric_fiber_equiv

theoremverified

Any finite uniform integer law with symmetric value counts admits a permutation that negates every value.

Statement

theorem forest_symmetric_fiber_equiv (α : Type) [Fintype α] (X : α → ℤ)
    (hs : ∀ z : ℤ, (Finset.univ.filter (fun a => X a = z)).card =
      (Finset.univ.filter (fun a => X a = -z)).card) :
    ∃ e : α ≃ α, ∀ a, X (e a) = -X a
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2
  • forest_greedy_symmetric_mergeThe greedy update of two independent finite uniform symmetric integer laws with a fair tie coin has symmetric value counts.
  • forest_symmetric_one_tailFor any nonempty finite uniform symmetric integer law, the probability of being at least one is at most one half.

The proof, explained

We partition α into the fibers of X and the fibers of -X. The symmetry hypothesis implies that for each integer z, the fiber where X a = z has the same size as the fiber where -X a = z (which is the fiber where X a = -z), allowing us to choose a bijection between each pair of fibers. Gluing these fiberwise bijections together produces a permutation of α that maps every element a to an element with value -X a.

  1. For each integer z, there is a bijection between the fiber {a | X a = z} and the fiber {a | -X a = z}.

    Working classically, we note that the condition -X a = z is equivalent to X a = -z by neg_eq_iff_eq_neg. By Fintype.card_subtype, the subtype cardinalities correspond to the sizes of the filtered sub-finsets, which are equal by the symmetry hypothesis hs z. Hence, Fintype.equivOfCardEq constructs a bijection between the two fibers for each z.

    lines 5–8

    uses Fintype.equivOfCardEq, Fintype.card_subtype, neg_eq_iff_eq_neg

      classical
      let fiber (z : ℤ) : {a // X a = z} ≃ {a // -X a = z} :=
        Fintype.equivOfCardEq (by
          simpa only [Fintype.card_subtype, neg_eq_iff_eq_neg] using hs z)
  2. There is a permutation e of α obtained by gluing together the fiberwise bijections.

    Applying Equiv.ofFiberEquiv to the family of fiber bijections glues them across all fibers z into a global bijection e : α ≃ α between the domain of X and the domain of -X.

    line 9

    uses Equiv.ofFiberEquiv

      let e : α ≃ α := Equiv.ofFiberEquiv fiber
  3. For every a ∈ α, the permutation e satisfies X (e a) = -X a.

    We instantiate the existential witness with e and consider any a ∈ α. By Equiv.ofFiberEquiv_map, evaluating the target function -X on e a yields the source value X a, so -X (e a) = X a. Negating both sides gives X (e a) = -X a, which is solved by linear integer arithmetic (omega).

    lines 10–13

    uses Equiv.ofFiberEquiv_map

      refine ⟨e, ?_⟩
      intro a
      have h : -X (e a) = X a := Equiv.ofFiberEquiv_map fiber a
      omega
Fintype.card_subtype
The cardinality of a subtype {x // p x} of a finite type equals the cardinality of the filtered finset of elements satisfying p.
neg_eq_iff_eq_neg
In an additive group with an involutive negation, -a = b if and only if a = -b.
Fintype.equivOfCardEq
Any two finite types with the same cardinality are in bijection.
Equiv.ofFiberEquiv
Given two maps from finite types into a common codomain, a family of bijections between their fibers over each value glues into a global bijection between the types.
Equiv.ofFiberEquiv_map
The global bijection formed by gluing fiber bijections maps each element to one whose image under the target map equals the original element's image under the source 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

theorem forest_symmetric_fiber_equiv (α : Type) [Fintype α] (X : α → ℤ)    (hs : ∀ z : ℤ, (Finset.univ.filter (fun a => X a = z)).card =      (Finset.univ.filter (fun a => X a = -z)).card) :    ∃ e : α ≃ α, ∀ a, X (e a) = -X a := by  classical  let fiber (z : ℤ) : {a // X a = z} ≃ {a // -X a = z} :=    Fintype.equivOfCardEq (by      simpa only [Fintype.card_subtype, neg_eq_iff_eq_neg] using hs z)  let e : α ≃ α := Equiv.ofFiberEquiv fiber  refine ⟨e, ?_⟩  intro a  have h : -X (e a) = X a := Equiv.ofFiberEquiv_map fiber a  omega
See it in the graphDiscuss this resultChallenge it