sum_involution_zmod_two
lemmaverified
For any finite type α with decidable equality, an involution σ : α → α satisfying σ (σ x) = x for all x, and any function f : α → F 2 satisfying f (σ x) = f x for all x, the sum of f x over all x in α equals the sum of f x over all x such that σ x = x.
Statement
theorem sum_involution_zmod_two {α : Type*} [Fintype α] [DecidableEq α] (σ : α → α) (hσ : ∀ x, σ (σ x) = x) (f : α → F 2) (hf : ∀ x, f (σ x) = f x) : ∑ x, f x = ∑ x ∈ Finset.filter (fun x => σ x = x) Finset.univ, f x
- Source
- arXiv:2610.04621 Lemma 5 proof (Appendix B)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
Read back from the Lean
For any finite type α with decidable equality, any function σ : α → α such that σ (σ x) = x for all x : α, and any function f : α → F 2 such that f (σ x) = f x for all x : α, the sum of f x over all x : α equals the sum of f x over all x : α satisfying σ x = x.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Sum of a function over a finite type over F_2 reduces to fixed points of an involution. -/ theorem sum_involution_zmod_two {α : Type*} [Fintype α] [DecidableEq α] (σ : α → α) (hσ : ∀ x, σ (σ x) = x) (f : α → F 2) (hf : ∀ x, f (σ x) = f x) : ∑ x, f x = ∑ x ∈ Finset.filter (fun x => σ x = x) Finset.univ, f x := by classical have hzero : ∑ x ∈ Finset.univ.filter (fun x => σ x ≠ x), f x = 0 := by refine Finset.sum_involution (s := Finset.univ.filter (fun x => σ x ≠ x)) (f := f) (fun x _ => σ x) ?_ ?_ ?_ ?_ · intro x hx rw [hf x] exact CharTwo.add_self_eq_zero (f x) · intro x hx hfx simpa using hx · intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ rw [hσ x] exact fun h => hx h.symm · intro x hx exact hσ x have hsplit := Finset.sum_filter_add_sum_filter_not (s := Finset.univ) (p := fun x => σ x = x) (f := f) rw [← hsplit, hzero, add_zero]