Explicit fixed-degree polynomial minwise bound
ProvedStableMSR.Recovery.polynomial_minwiseLet be a prime and , with and . For each coefficient vector , define a hash on the ordered input keys by
where takes the representative in . Order the keys by increasing hash value, breaking ties by increasing input index. For every nonempty subset and every , uniformly sampling the coefficient vector satisfies
The probability is the number of successful coefficient vectors divided by . Different vectors that produce the same order are counted separately. Thus the result supplies the finite multiset-of-orders interpretation used in the deterministic order-family argument.
This is an explicit, nonoptimized constant-degree realization of the minwise bound used in Appendix B. The proof establishes the limited-independence, moment, and tie-breaking estimates internally; it does not assume a minwise theorem. The theorem takes the prime as a parameter and does not assert a prime-generation or machine-enumeration runtime.
import Mathlib.LinearAlgebra.Lagrange import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Real.Basic import Mathlib.Data.Fintype.CardEmbedding import Mathlib.Data.Nat.Factorial.Cast import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.BigOperators.Field import Mathlib.Tactic.Linarith import Mathlib.Tactic.Positivity import Mathlib.Tactic.FieldSimp import Mathlib.Tactic.Ring import Mathlib.Order.Interval.Finset.Fin import Mathlib.Algebra.Field.ZMod import Mathlib.Data.Nat.Choose.Sum import Mathlib.Data.Nat.Choose.Bounds import Mathlib.Tactic.NormNum import Mathlib.Analysis.PSeries import Mathlib.Algebra.BigOperators.Intervals import Mathlib.Data.Finset.Lattice.Lemmas import Mathlib.Algebra.BigOperators.Group.Finset.Basic set_option autoImplicit false open scoped Classical BigOperators
namespace StableMSR.Recovery
theorem polynomial_minwise (q m : ℕ) [Fact q.Prime]
(hq : 8193 ≤ q) (hm : 4*m^2 ≤ q) :
let hash : (Fin 8193 → ZMod q) → Fin m → ℕ := fun a x =>
(∑ i : Fin 8193, a i * (x.val : ZMod q) ^ (i : ℕ)).val
∀ (T : Finset (Fin m)) (z : Fin m), z ∈ T →
(((Finset.univ : Finset (Fin 8193 → ZMod q)).filter (fun a =>
∀ y ∈ T, y ≠ z →
hash a z < hash a y ∨ (hash a z = hash a y ∧ z < y))).card : ℝ) /
(q : ℝ)^8193 ≤ 3 / (2*(T.card : ℝ)) := by sorry
end StableMSR.Recovery