forest_symmetric_fiber_equiv
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.
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.
uses
Fintype.equivOfCardEq,Fintype.card_subtype,neg_eq_iff_eq_negclassical 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)
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.
uses
Equiv.ofFiberEquivlet e : α ≃ α := Equiv.ofFiberEquiv fiberFor 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).
uses
Equiv.ofFiberEquiv_maprefine ⟨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.
- Classical logic is invoked via `classical` so that `Fintype.equivOfCardEq` can nonconstructively choose an arbitrary bijection between two types solely from their cardinalities being equal, making the resulting permutation noncomputable.
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.
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