finite_function_collision_head_pair_injective
Given an injective tail-head encoding and a map whose fibers have a fixed tail, encoding each nonrepresentative by its tail and the unordered pair of its head with its representative head is injective.
Statement
theorem finite_function_collision_head_pair_injective (α β γ δ : Type) [DecidableEq δ] (f : α → β) (r : β → α) (tail : α → γ) (head : α → δ) (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))) : Set.InjOn (fun x => (tail x, s(head x, head (r (f x))))) {x | r (f x) ≠ x}
- Source
- Collision counting for the small-overlap route to OP-110.
- Verified
- 04 Nov 2026
- Axioms
Quot.soundpropext- Used by 6
- 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…
- finite_endomap_collision_charge_identityFor a finite endomap whose fibers share a tail and whose elements are determined by tail and head, the number of missing image elements is…
- 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
To show injectivity on the set of nonrepresentatives, assume two nonrepresentatives x and y have the same encoding. Comparing their encodings shows that their tails match and their unordered pairs of heads are equal, which leads to two cases for how the heads pair up. If the head of x matches the head of y, injectivity of the tail-head map immediately implies x = y. If instead the head of x matches the representative head of y, then x must equal the representative r (f y), forcing r (f x) = x and contradicting the assumption that x is a nonrepresentative.
Assuming two nonrepresentatives x and y have identical encodings, their tails are equal and their unordered pairs of heads are equal.
Let x and y be elements in the set {z | r(f(z)) ≠ z} of nonrepresentatives, and suppose their encodings (tail x, s(head x, head (r (f x)))) and (tail y, s(head y, head (r (f y)))) are equal. Decomposing the equality of pairs into components yields tail x = tail y and s(head x, head (r (f x))) = s(head y, head (r (f y))).
uses
Prod.mk.injEqintro x hx y hy hxy simp only [Prod.mk.injEq] at hxy obtain ⟨htail_eq, hpair_eq⟩ := hxy
The equality of the head pairs splits into two cases: either head x = head y or head x = head (r (f y)).
Two unordered pairs {a, b} and {c, d} in the symmetric square are equal if and only if either (a = c and b = d) or (a = d and b = c). Unfolding this equivalence on the head pairs yields two possibilities: either head x = head y (and head (r (f x)) = head (r (f y))), or head x = head (r (f y)) (and head (r (f x)) = head y).
uses
Sym2.eq,Sym2.rel_iffsimp only [Sym2.eq, Sym2.rel_iff] at hpair_eq rcases hpair_eq with ⟨hhead1, -⟩ | ⟨hhead1, -⟩
If head x = head y, then x = y.
Combining tail x = tail y with head x = head y gives (tail x, head x) = (tail y, head y). By the injectivity of the map z ↦ (tail z, head z), we conclude x = y.
uses
Prod.ext· have : (tail x, head x) = (tail y, head y) := Prod.ext htail_eq hhead1 exact hkey this
The alternative case head x = head (r (f y)) leads to a contradiction.
Because r (f y) is the representative of the fiber containing y, we have f (r (f y)) = f y, so the fiber-tail hypothesis htail implies tail (r (f y)) = tail y = tail x. Together with head x = head (r (f y)), this means (tail x, head x) = (tail (r (f y)), head (r (f y))), so injectivity gives x = r (f y). Applying f to both sides yields f x = f (r (f y)) = f y, from which it follows that r (f x) = r (f y) = x. This contradicts the assumption that x is a nonrepresentative (r (f x) ≠ x), which eliminates this case and completes the proof.
uses
Prod.ext· have htail_rfy : tail (r (f y)) = tail y := htail (r (f y)) y (hr y) have hkey_x_rfy : (tail x, head x) = (tail (r (f y)), head (r (f y))) := Prod.ext (htail_eq.trans htail_rfy.symm) hhead1 have hx_eq_rfy : x = r (f y) := hkey hkey_x_rfy have hfx_eq : f x = f y := by rw [hx_eq_rfy, hr y] have hrfx_eq_x : r (f x) = x := by rw [hfx_eq, ← hx_eq_rfy] exact (hx hrfx_eq_x).elim
Prod.mk.injEq- Two pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Sym2.eq- Two unordered pairs s(a, b) and s(c, d) in the symmetric square are equal if and only if (a, b) and (c, d) are related by the symmetric relation.
Sym2.rel_iff- Two pairs (a, b) and (c, d) are related in the symmetric square if and only if (a = c ∧ b = d) ∨ (a = d ∧ b = c).
Prod.ext- If two pairs have equal first components and equal second components, then the pairs are equal.
- The notation `s(a, b)` denotes the unordered pair of `a` and `b` in `Sym2 δ`, the symmetric square of `δ`.
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_function_collision_head_pair_injective (α β γ δ : Type) [DecidableEq δ] (f : α → β) (r : β → α) (tail : α → γ) (head : α → δ) (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))) : Set.InjOn (fun x => (tail x, s(head x, head (r (f x))))) {x | r (f x) ≠ x} := by intro x hx y hy hxy simp only [Prod.mk.injEq] at hxy obtain ⟨htail_eq, hpair_eq⟩ := hxy simp only [Sym2.eq, Sym2.rel_iff] at hpair_eq rcases hpair_eq with ⟨hhead1, -⟩ | ⟨hhead1, -⟩ · have : (tail x, head x) = (tail y, head y) := Prod.ext htail_eq hhead1 exact hkey this · have htail_rfy : tail (r (f y)) = tail y := htail (r (f y)) y (hr y) have hkey_x_rfy : (tail x, head x) = (tail (r (f y)), head (r (f y))) := Prod.ext (htail_eq.trans htail_rfy.symm) hhead1 have hx_eq_rfy : x = r (f y) := hkey hkey_x_rfy have hfx_eq : f x = f y := by rw [hx_eq_rfy, hr y] have hrfx_eq_x : r (f x) = x := by rw [hfx_eq, ← hx_eq_rfy] exact (hx hrfx_eq_x).elim