ProximityPrize.SubmissionUpper.HalfRadiusCollision.exists_dot_offdiag_le
ProvedProximityPrize.SubmissionUpper.HalfRadiusCollision.exists_dot_offdiag_leproximity-prize
Averaging bound for off-diagonal collisions of a finite-field dot product.
Original Proximity Prize source by GitHub contributor gpsanant; 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
lemma exists_dot_offdiag_le {k : ℕ} (A : Finset (Fin k → F)) :
∃ v : Fin k → F,
Fintype.card F *
((A.product A).filter fun xy =>
xy.1 ≠ xy.2 ∧ dot xy.1 v = dot xy.2 v).card ≤
A.card * (A.card - 1) := by sorry
end HalfRadiusCollision
end SubmissionUpper
end ProximityPrize
Source