good_slopes_three_color_fiber_bound
theoremverified
If a function is injective on each of three colors, every fiber contains at most three points.
Statement
theorem good_slopes_three_color_fiber_bound {X Y : Type*} [DecidableEq X] [DecidableEq Y] (S : Finset X) (f : X → Y) (c : X → Fin 3) (hinj : ∀ p ∈ S, ∀ q ∈ S, c p = c q → f p = f q → p = q) (t : Y) : (S.filter fun p => f p = t).card ≤ 3
- Source
- Finite counting and CRT arithmetic in the OP-1027 modulus 105 reduction.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Lean source view module on GitHub
theorem good_slopes_three_color_fiber_bound {X Y : Type*} [DecidableEq X] [DecidableEq Y] (S : Finset X) (f : X → Y) (c : X → Fin 3) (hinj : ∀ p ∈ S, ∀ q ∈ S, c p = c q → f p = f q → p = q) (t : Y) : (S.filter fun p => f p = t).card ≤ 3 := by classical have hi : Set.InjOn c (S.filter fun p => f p = t) := by intro p hp q hq heq exact hinj p (Finset.mem_filter.mp hp).1 q (Finset.mem_filter.mp hq).1 heq ((Finset.mem_filter.mp hp).2.trans (Finset.mem_filter.mp hq).2.symm) calc (S.filter fun p => f p = t).card = ((S.filter fun p => f p = t).image c).card := (Finset.card_image_of_injOn hi).symm _ ≤ (Finset.univ : Finset (Fin 3)).card := Finset.card_le_card (Finset.subset_univ _) _ = 3 := by simp