AFTD Auto-Formalizing Theoretical Domains

finite_endomap_collision_charge_identity

theoremverified

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
Used by 5

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.

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

    line 11

    uses finite_endomap_missing_image_eq_nonrepresentatives

      rw [finite_endomap_missing_image_eq_nonrepresentatives α f r hr]
  2. 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}|.

    lines 12–18

    uses Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and, Finset.card_eq_sum_card_fiberwise

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

    lines 19–20

    uses finite_function_collision_head_pair_injective

      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
  4. 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.

    lines 21–23

    uses Finset.sum_congr

      rw [hfiber]
      apply Finset.sum_congr rfl
      intro e he
  5. 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.

    lines 24–28

    uses Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and, Prod.ext

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

    line 29

    uses Finset.card_image_of_injOn

      rw [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

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