ProximityPrize.SubmissionUpper.HalfRadiusCollision.exists_dot_image_card_bound
ProvedProximityPrize.SubmissionUpper.HalfRadiusCollision.exists_dot_image_card_boundproximity-prize
A dot-product map with a lower bound on its image cardinality.
Original Proximity Prize source by GitHub contributor erdkocak; preserved in upper submission bd59768c-5fe4-466a-a8f2-e94a39ae4d4a (224323f053d0d1dfa78d7b9625194fe0133f04bc). Ported from Lean 4.32.2 to 4.33.1 with independently checked statements, full source and target kernel replay, quotient checks and transitive axiom checks. This provider publication is not a new competition submission.
Preamble
import Mathlib
import Init
import Definitions.Def_ProximityPrize_SubmissionUpper_HalfRadiusCollision_dot
namespace ProximityPrize.SubmissionUpper.HalfRadiusCollision
open scoped BigOperators
variable {F : Type} [Field F] [Fintype F] [DecidableEq F]
Formal statement
/-- Some linear functional has an image whose density is at least
`|A| / (|F| + |A| - 1)`. This is the quantitative form of the collision
argument: unlike `exists_dot_surjective_of_card_sq_lt`, it does not require the
image to be all of `F`. -/
theorem exists_dot_image_card_bound {k : ℕ} (A : Finset (Fin k → F)) :
∃ v : Fin k → F,
A.card * Fintype.card F ≤
(A.image (fun x => dot x v)).card * (Fintype.card F + A.card - 1) := by sorry
end HalfRadiusCollision
end SubmissionUpper
end ProximityPrize
Source