Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.2 — majority signs of two nearly orthogonal sign vectors are nearly uncorrelated

Open
ITPIRPreproc.MatchVec.Supplement.lemma_7_2

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographymajority-constructionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1private-information-retrievalprobability

Let ddd be odd and let v,v′∈{−1,+1}dv,v'\in\{-1,+1\}^dv,v′∈{−1,+1}d be sign vectors whose integer inner product satisfies ∣⟨v,v′⟩∣≤μd|\langle v,v'\rangle|\le\mu d∣⟨v,v′⟩∣≤μd, where 0≤μ≤120\le\mu\le\tfrac120≤μ≤21​. Let rrr be uniform on {−1,+1}d\{-1,+1\}^d{−1,+1}d. Then for any b,b′∈{−1,+1}b,b'\in\{-1,+1\}b,b′∈{−1,+1},

Pr⁡[sgn⁡⟨r,v⟩=b, sgn⁡⟨r,v′⟩=b′]≤14+8μ+4d.\Pr\bigl[\operatorname{sgn}\langle r,v\rangle=b,\ \operatorname{sgn}\langle r,v'\rangle=b'\bigr]\le\frac14+8\sqrt\mu+\frac4{\sqrt d}.Pr[sgn⟨r,v⟩=b, sgn⟨r,v′⟩=b′]≤41​+8μ​+d​4​.

The two majority signs of a random sign vector with respect to nearly orthogonal directions thus behave almost like independent fair signs. This drives the overlap bound Pr⁡R←Ri[j∈S(R)]≤2/m\Pr_{R\leftarrow\mathcal R_i}[j\in S(R)]\le 2/mPrR←Ri​​[j∈S(R)]≤2/m of Claim 7.4.1.

Formalization Note The probability is the number of sign vectors rrr with 0<b⟨r,v⟩0<b\langle r,v\rangle0<b⟨r,v⟩ and 0<b′⟨r,v′⟩0<b'\langle r,v'\rangle0<b′⟨r,v′⟩ divided by 2d2^d2d. Since b=±1b=\pm1b=±1, sgn⁡x=b\operatorname{sgn}x=bsgnx=b holds exactly when 0<bx0<bx0<bx. The lemma holds for every odd ddd and every μ∈[0,1/2]\mu\in[0,1/2]μ∈[0,1/2], not only for the parameters (19), and the constants 1/41/41/4, 888, 444 are those of the paper.

Differences from the source:

  • encoding: Pr over uniform r ∈ {−1,+1}^d of sgn⟨r,v⟩ = b and sgn⟨r,v′⟩ = b′ → the number of r : Fin d → ℤˣ with 0 < b⟨r,v⟩ and 0 < b′⟨r,v′⟩, divided by 2^d; reason: b = ±1, so sgn x = b iff 0 < b x; uniform law on a finite set; same probability
Preamble
import Mathlib
import Definitions.Def_ITPIRPreproc_MatchVec_Supplement_Majority
Formal statement
namespace ITPIRPreproc.MatchVec.Supplement

/-- Lemma 7.2, printed p.25 (PDF p.27). Let `d` be odd and `v, v′ ∈ {−1,+1}^d` with
`|⟨v, v′⟩| ≤ μ d`, `0 ≤ μ ≤ 1/2`. For uniform `r ∈ {−1,+1}^d` and any `b, b′ ∈ {−1,+1}`,
`Pr[sgn⟨r, v⟩ = b, sgn⟨r, v′⟩ = b′] ≤ 1/4 + 8√μ + 4/√d`. Since `b = ±1`, the event
`sgn⟨r, v⟩ = b` is `0 < b⟨r, v⟩`; the probability is the fraction of the `2^d` sign vectors. -/
theorem lemma_7_2 (d : ℕ) (hd : Odd d) (μ : ℝ) (hμ0 : 0 ≤ μ) (hμ1 : μ ≤ 1 / 2)
    (v v' : Fin d → ℤˣ) (hvv : |((ip v v' : ℤ) : ℝ)| ≤ μ * d) (b b' : ℤˣ) :
    (((Finset.univ.filter fun r : Fin d → ℤˣ =>
        0 < (b : ℤ) * ip r v ∧ 0 < (b' : ℤ) * ip r v').card : ℝ) / (2 : ℝ) ^ d) ≤
      1 / 4 + 8 * Real.sqrt μ + 4 / Real.sqrt d := by sorry

end ITPIRPreproc.MatchVec.Supplement
Source
Jesko Dujmovic, Zhengnan Lai, Daniel Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572 (October 2026), Lemma 7.2, printed p.25 (PDF p.27)

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