finite_endomap_collision_charge_identity
For a finite endomap whose fibers share a tail and whose elements are determined by tail and head, the number of missing image elements is the sum, over charged unordered head pairs, of the number of different tails charging each pair.
Statement
theorem finite_endomap_collision_charge_identity (α β γ : Type) [Fintype α] [DecidableEq α] [DecidableEq β] [DecidableEq γ] (f r : α → α) (tail : α → β) (head : α → γ) (S : Finset (Sym2 γ)) (hr : ∀ x, f (r (f x)) = f x) (htail : ∀ x y, f x = f y → tail x = tail y) (hkey : Function.Injective (fun x => (tail x, head x))) (hcover : ∀ x, r (f x) ≠ x → s(head x, head (r (f x))) ∈ S) : ((Finset.univ : Finset α) \ Finset.univ.image f).card = ∑ e ∈ S, (((Finset.univ.filter fun x => r (f x) ≠ x).filter fun x => s(head x, head (r (f x))) = e).image tail).card
- Source
- Fiber-collision charge counting for the small-overlap good-center route to OP-110.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- finite_endomap_missing_image_eq_nonrepresentativesFor a finite endomap with a chosen representative from each nonempty fiber, the number of elements outside its image equals the number of…
- finite_function_collision_head_pair_injectiveGiven an injective tail-head encoding and a map whose fibers have a fixed tail, encoding each nonrepresentative by its tail and the…
- Used by 5
- digraph_oriented_arc_map_missing_dirty_budgetFor a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs…
- digraph_oriented_arc_map_twice_missing_budgetIn a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting…
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- digraph_girth_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times…
- digraph_girth_arc_map_missing_budgetFor a loopless oriented digraph of directed girth at least g, g−1 times the number of missing predecessor arc-map images is at most g…
The proof, explained
The proof first replaces the count of missing image elements with the number of non-representatives (elements x where r(f(x)) ≠ x). It then partitions these non-representatives according to the collision head pair E(x) = s(head(x), head(r(f(x)))), which lands in S by assumption. Because each fiber of f shares a tail and elements are determined by tail and head, knowing both tail(x) and E(x) uniquely determines x, making the tail map injective on each fiber of E. Consequently, each fiber's size equals the number of distinct tails charging that head pair, and summing over S yields the result.
The number of elements missing from the image of f equals the number of non-representatives, {x | r(f(x)) ≠ x}.
By finite_endomap_missing_image_eq_nonrepresentatives, the size of the complement univ \\ f(univ) is equal to the size of the set of elements not fixed by r ∘ f.
uses
finite_endomap_missing_image_eq_nonrepresentativesrw [finite_endomap_missing_image_eq_nonrepresentatives α f r hr]The number of non-representatives |N| equals the sum of the cardinalities of its fibers under the collision-edge map E over all edges in S.
We define N as the set of non-representatives {x | r(f(x)) ≠ x} and E(x) as the unordered pair of heads s(head(x), head(r(f(x)))). The coverage hypothesis hcover ensures that E maps N into S. Applying the fiberwise partition principle Finset.card_eq_sum_card_fiberwise decomposes |N| into the sum over e ∈ S of the fiber sizes |{x ∈ N | E(x) = e}|.
uses
Finset.mem_coe,Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_eq_sum_card_fiberwiselet N : Finset α := Finset.univ.filter fun x => r (f x) ≠ x let E : α → Sym2 γ := fun x => s(head x, head (r (f x))) have hmaps : Set.MapsTo E (↑N) (↑S) := by intro x hx simp only [N, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hx exact hcover x hx have hfiber := @Finset.card_eq_sum_card_fiberwise _ _ _ E N S hmaps
The joint map x ↦ (tail(x), E(x)) is injective on the set of non-representatives N.
By finite_function_collision_head_pair_injective, because f-fibers have constant tails and each element is determined by its tail and head, a non-representative x is uniquely determined by knowing both its tail and the unordered head pair E(x).
uses
finite_function_collision_head_pair_injectivehave hinj_pair : Set.InjOn (fun x => (tail x, E x)) {x | r (f x) ≠ x} := finite_function_collision_head_pair_injective α α β γ f r tail head hr htail hkey
It suffices to show that for every edge e ∈ S, the fiber {x ∈ N | E(x) = e} has the same size as its image under tail.
We rewrite the non-representative count using the fiberwise partition sum. By congruence of sums (Finset.sum_congr), it suffices to prove equality of the summands for an arbitrary e ∈ S.
uses
Finset.sum_congrrw [hfiber] apply Finset.sum_congr rfl intro e he
The map tail is injective on each fiber {x ∈ N | E(x) = e}.
If x and y belong to the fiber of e, then E(x) = e = E(y). If they also satisfy tail(x) = tail(y), then (tail(x), E(x)) = (tail(y), E(y)) by Prod.ext. By the injectivity of the joint map (hinj_pair), we conclude x = y.
uses
Finset.mem_coe,Finset.mem_filter,Finset.mem_univ,true_and,Prod.exthave hinj : Set.InjOn tail (↑(N.filter fun x => E x = e)) := by intro x hx y hy htail_eq simp only [N, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hx hy apply hinj_pair hx.1 hy.1 exact Prod.ext htail_eq (hx.2.trans hy.2.symm)
The size of each fiber equals the number of distinct tails in that fiber, completing the identity.
Since tail is injective on the fiber, Finset.card_image_of_injOn equates the cardinality of the fiber with the cardinality of its image under tail.
uses
Finset.card_image_of_injOnrw [Finset.card_image_of_injOn hinj]
finite_endomap_missing_image_eq_nonrepresentatives- For an endomap f on a finite type with a representative-selection map r on its image, the number of elements not in the image of f equals the number of non-representatives (elements x where r(f(x)) ≠ x).
Finset.mem_coe- An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the filter predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finite set Finset.univ.
true_and- The conjunction of True with any proposition p is equivalent to p.
Finset.card_eq_sum_card_fiberwise- If a function maps a finite set s into a finite set t, the cardinality of s is the sum over b ∈ t of the cardinalities of the fibers {a ∈ s | f(a) = b}.
finite_function_collision_head_pair_injective- For a function whose fibers share a tail and whose elements are determined by tail and head, mapping each non-representative x to the pair of its tail and its unordered collision head pair s(head(x), head(r(f(x)))) is injective.
Finset.sum_congr- Two sums over the same finite set are equal if their terms agree on every element of the set.
Prod.ext- Two pairs are equal if their first components are equal and their second components are equal.
Finset.card_image_of_injOn- If a function is injective on a finite set, the cardinality of its image on that set equals the cardinality of the set itself.
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 finite_endomap_collision_charge_identity (α β γ : Type) [Fintype α] [DecidableEq α] [DecidableEq β] [DecidableEq γ] (f r : α → α) (tail : α → β) (head : α → γ) (S : Finset (Sym2 γ)) (hr : ∀ x, f (r (f x)) = f x) (htail : ∀ x y, f x = f y → tail x = tail y) (hkey : Function.Injective (fun x => (tail x, head x))) (hcover : ∀ x, r (f x) ≠ x → s(head x, head (r (f x))) ∈ S) : ((Finset.univ : Finset α) \ Finset.univ.image f).card = ∑ e ∈ S, (((Finset.univ.filter fun x => r (f x) ≠ x).filter fun x => s(head x, head (r (f x))) = e).image tail).card := by rw [finite_endomap_missing_image_eq_nonrepresentatives α f r hr] let N : Finset α := Finset.univ.filter fun x => r (f x) ≠ x let E : α → Sym2 γ := fun x => s(head x, head (r (f x))) have hmaps : Set.MapsTo E (↑N) (↑S) := by intro x hx simp only [N, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hx exact hcover x hx have hfiber := @Finset.card_eq_sum_card_fiberwise _ _ _ E N S hmaps have hinj_pair : Set.InjOn (fun x => (tail x, E x)) {x | r (f x) ≠ x} := finite_function_collision_head_pair_injective α α β γ f r tail head hr htail hkey rw [hfiber] apply Finset.sum_congr rfl intro e he have hinj : Set.InjOn tail (↑(N.filter fun x => E x = e)) := by intro x hx y hy htail_eq simp only [N, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hx hy apply hinj_pair hx.1 hy.1 exact Prod.ext htail_eq (hx.2.trans hy.2.symm) rw [Finset.card_image_of_injOn hinj]