Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix A — explicit subpolynomial dimension bound

Proved
ITPIRPreproc.MatchVec.polynomial_parameter_bounds

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

asymptoticscryptographymatching-vectors

Let h≥3h\ge3h≥3, let ℓ\ellℓ be the least natural number satisfying ℓℓ≥2h\ell^\ell\ge2^hℓℓ≥2h, and let 2a2^a2a and 3b3^b3b be the least powers of 222 and 333 strictly exceeding ℓ\sqrt\ellℓ​. Put k=max⁡(2a,3b)−1k=\max(2^a,3^b)-1k=max(2a,3b)−1. For any bijective enumeration by [d][d][d] of the coordinates (I,α)(I,\alpha)(I,α) in the polynomial construction,

ℓℓ≥2h,k≥1,ℓ<2a3b,d≤21000hln⁡h.\ell^\ell\ge2^h,\qquad k\ge1,\qquad\ell<2^a3^b,\qquad d\le2^{1000\sqrt{h\ln h}}.ℓℓ≥2h,k≥1,ℓ<2a3b,d≤21000hlnh​.

The constant 1000 is a convenient absolute constant, not an optimized value. This makes the asymptotic dimension claim in Appendix A explicit for all h≥3h\ge3h≥3. It is a dimension and parameter theorem; it makes no RAM implementation claim.

Preamble
import Definitions.Def_ITPIRPreproc_MatchVec_PolynomialParameters
open ITPIRPreproc.MatchVec ITPIRPreproc.MatchVec.PolynomialConstruction
Formal statement
theorem ITPIRPreproc.MatchVec.polynomial_parameter_bounds (h d : ℕ) (hh : 3 ≤ h)
    (coords : Fin d ≃ Coordinate (wordLength h) (degree (exponent2 h) (exponent3 h))) :
    2^h ≤ (wordLength h)^(wordLength h) ∧
    1 ≤ degree (exponent2 h) (exponent3 h) ∧
    wordLength h < 2^(exponent2 h) * 3^(exponent3 h) ∧
    (d:ℝ) ≤ (2:ℝ)^(1000 * Real.sqrt ((h:ℝ)*Real.log h)) := 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