A large fiber exists when the domain outnumbers bounded fibers
ProvedYukon.MultiAnchor.exists_large_fiber_2104d33ae4e5better-codes-history
For finite types α and β and a function f : α → β, if |β| · s < |α|, some fiber of f has more than s elements. This pigeonhole lemma is used in the multi-anchor attack construction. Original contributor: saucegodbased; verified Better Codes submission 1ef57658-6336-410f-add5-9247de860f71. Extracted from Lean 4.32.2 source; only the declaration name and import context were adapted for publication. The statement and proof body are unchanged.
Preamble
import Mathlib open scoped BigOperators
Formal statement
theorem Yukon.MultiAnchor.exists_large_fiber_2104d33ae4e5 {α β : Type} [Fintype α] [Fintype β] [DecidableEq β]
(f : α → β) (sieve : Nat)
(hlarge : Fintype.card β * sieve < Fintype.card α) :
∃ y : β, sieve < (Finset.univ.filter fun x : α => f x = y).card := by sorry
Source