Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Explicit fixed-degree polynomial minwise bound

Proved
StableMSR.Recovery.polynomial_minwise

by lreyzin · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

clusteringderandomizationhashingprobability

Let qqq be a prime and m≥0m\ge0m≥0, with q≥8193q\ge8193q≥8193 and q≥4m2q\ge4m^2q≥4m2. For each coefficient vector a∈Fq8193a\in\mathbb F_q^{8193}a∈Fq8193​, define a hash on the ordered input keys 0,…,m−10,\ldots,m-10,…,m−1 by

ha(x)=val⁡ ⁣(∑i=08192aixi),h_a(x)=\operatorname{val}\!\left(\sum_{i=0}^{8192}a_i x^i\right),ha​(x)=val(i=0∑8192​ai​xi),

where val⁡\operatorname{val}val takes the representative in {0,…,q−1}\{0,\ldots,q-1\}{0,…,q−1}. Order the keys by increasing hash value, breaking ties by increasing input index. For every nonempty subset TTT and every z∈Tz\in Tz∈T, uniformly sampling the coefficient vector satisfies

Pr⁡a[z is first in T]≤32∣T∣.\Pr_a[z\text{ is first in }T]\le\frac{3}{2|T|}.aPr​[z is first in T]≤2∣T∣3​.

The probability is the number of successful coefficient vectors divided by q8193q^{8193}q8193. 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 qqq as a parameter and does not assert a prime-generation or machine-enumeration runtime.

Preamble
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
Formal statement
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
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix B, https://arxiv.org/html/2611.03547v1; an explicit constant-degree specialization of the minwise construction, with the finite-sample analysis proved directly. Related primary source: P. Indyk, A Small Approximately Min-Wise Independent Family of Hash Functions, https://people.csail.mit.edu/indyk/minwise.pdf. Degree 8192 is an explicit nonoptimized choice in this formalization, rather than a claimed optimal constant from the source.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me