Theorem 6.4, inequality (31) — a bound on forces a large average of the
ProvedLatticePrepro.mul_le_sum_of_sum_prod_inv_lecoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a finite set, let be an integer, and let be real numbers for and . Let be a real number with
Then
In the soundness proof of Theorem 6.4, is the set of random strings, , is the size of the list at the -th query of , and . The hypothesis is the first inequality of (31), . The conclusion is for the average list size , which is what the other two inequalities of (31) give.
Formalization Note. The paper obtains the conclusion from Jensen's inequality for the exponential and then for the logarithm. The Lean proof applies , for each , to the positive numbers and , whose product is , and sums over . The statement also covers .
Preamble
import Mathlib open Finset
Formal statement
theorem LatticePrepro.mul_le_sum_of_sum_prod_inv_le {R : Type*} [Fintype R] {q : ℕ} (lam : R → Fin q → ℝ)
(hlam : ∀ r j, 0 < lam r j) {t : ℝ} (ht : 0 < t)
(h : (∑ r, ∏ j, (lam r j)⁻¹) * t ^ q ≤ Fintype.card R) :
(Fintype.card R : ℝ) * q * t ≤ ∑ r, ∑ j, lam r j := by sorrySource
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), proof of Theorem 6.4 (\label{thm:pcp-reduction}), soundness, second and third inequalities of (31) (\label{eq:pcp-list-bound}); Lean: LatticePrepro/PCP/Inequality.lean, LatticePrepro.mul_le_sum_of_sum_prod_inv_le