Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix A — correctness, parity separation, and dimension of the polynomial matching vectors

Proved
ITPIRPreproc.MatchVec.polynomial_matching_vectors

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

cryptographyfinite-differencesmatching-vectors

Let ℓ,a,b,m,d\ell,a,b,m,dℓ,a,b,m,d be natural numbers, put k=max⁡(2a,3b)−1k=\max(2^a,3^b)-1k=max(2a,3b)−1, and suppose k≥1k\ge1k≥1 and ℓ<2a3b\ell<2^a3^bℓ<2a3b. Choose any mmm distinct words σr∈[ℓ]ℓ\sigma_r\in[\ell]^\ellσr​∈[ℓ]ℓ and any enumeration by [d][d][d] of all pairs (I,α)(I,\alpha)(I,α) with I⊆[ℓ]I\subseteq[\ell]I⊆[ℓ], ∣I∣≤k|I|\le k∣I∣≤k, and α:I→[ℓ]\alpha:I\to[\ell]α:I→[ℓ].

Use the CRT signal and binomial-inversion coefficients from the polynomial-construction definitions, and form

ur(I,α)=c∣I∣1[σr∣I=α],vr(I,α)=1[σr∣I=α].u_r(I,\alpha)=c_{|I|}\mathbf1[\sigma_r|_I=\alpha],\qquad v_r(I,\alpha)=\mathbf1[\sigma_r|_I=\alpha].ur​(I,α)=c∣I∣​1[σr​∣I​=α],vr​(I,α)=1[σr​∣I​=α].

Then these vectors satisfy Equation (7): diagonal inner products are 111 modulo 666, and each off-diagonal inner product is 000 modulo 222 or modulo 333. The vectors vr mod 2v_r\bmod2vr​mod2 are pairwise distinct. Moreover,

d=∑t=0k(ℓt)ℓt,d=\sum_{t=0}^{k}\binom{\ell}{t}\ell^t,d=t=0∑k​(tℓ​)ℓt,

and, when ℓ≥1\ell\ge1ℓ≥1, d≤(k+1)ℓ2kd\le(k+1)\ell^{2k}d≤(k+1)ℓ2k. Terms with t>ℓt>\ellt>ℓ vanish.

This is the algebraic and combinatorial correctness part of Appendix A. It is valid for any injective indexing of row words and any enumeration of coordinates; it does not assert a uniform RAM implementation or the final subpolynomial bound in terms of hhh.

Preamble
import Definitions.Def_ITPIRPreproc_MatchVec_PolynomialConstruction
import Mathlib.Tactic
open ITPIRPreproc.MatchVec ITPIRPreproc.MatchVec.PolynomialConstruction
open Finset
Formal statement
theorem ITPIRPreproc.MatchVec.polynomial_matching_vectors (ell a b m d : ℕ)
    (hk : 1 ≤ degree a b) (hsize : ell < 2^a * 3^b)
    (rows : Fin m ↪ (Fin ell → Fin ell))
    (coords : Fin d ≃ Coordinate ell (degree a b)) :
    IsMVFamily m d
      (fun r j => leftVector (coefficient ell a b) (rows r) (coords j))
      (fun r j => rightVector (rows r) (coords j)) ∧
    d = ∑ t ∈ range (degree a b + 1), ell.choose t * ell^t ∧
    (1 ≤ ell → d ≤ (degree a b + 1) * ell^(2 * degree a b)) := by sorry
Source
Jesko Dujmovic, Zhengnan Lai, Daniel Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572, Appendix A, printed pp.36-37 (PDF pp.38-39), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/572.pdf

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