Lemma 2.9 — Cauchy–Schwarz step: for a 1-bounded -invariant
ProvedLLROPI.Shamir.lemma_2_9additive-combinatoricsfinite-fieldsfourier-analysisp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and suppose is -invariant for some subspace , i.e. for every and , and -bounded, . Then
In the formal statement the right-hand side is the complex average; the inequality asserts that it is real (imaginary part ) and that its real part dominates the left-hand side.
Differences from the source:
- encoding: the inequality |E G P|² ≤ E_{x,h} P(x) conj(P(x + h)) between a real number and a complex average → the average has imaginary part 0 and |E G P|² ≤ its real part; reason: the printed ≤ asserts that the right-hand side is real; both parts are stated
Preamble
import Mathlib
Formal statement
namespace LLROPI.Shamir
open Classical in
/-- **Lemma 2.9**, p. 23 (PDF 25). For any `G, P : 𝔽_p^k → ℂ`, suppose `G` is `K`-invariant for
some subspace `K ≤ 𝔽_p^k` (`G(x + h) = G(x)` for every `x` and `h ∈ K`) and `1`-bounded
(`‖G‖_∞ ≤ 1`). Then
`|E_{x ∈ 𝔽_p^k} G(x) P(x)|² ≤ E_{x ∈ 𝔽_p^k, h ∈ K} P(x) \overline{P(x + h)}`.
Sun, Wootters, arXiv:2610.12357 (held version, sha256 f154f5ce…), Lemma 2.9, (2.6), p. 23 (PDF 25).
**Formalization Note.** The right-hand side is a complex average; the inequality asserts that it is
real (imaginary part `0`) and at least the left-hand side. Expectations are normalized sums over
`𝔽_p^k` and over the finite set of elements of `K`. -/
theorem lemma_2_9 (p : ℕ) [Fact p.Prime] (k : ℕ) (G P : (Fin k → ZMod p) → ℂ)
(K : Submodule (ZMod p) (Fin k → ZMod p))
(hinv : ∀ x, ∀ h ∈ K, G (x + h) = G x) (hbdd : ∀ x, ‖G x‖ ≤ 1) :
((∑ x : Fin k → ZMod p, ∑ h ∈ Finset.univ.filter (fun h => h ∈ K), P x * star (P (x + h))) /
((p : ℂ) ^ k * ((Finset.univ.filter (fun h => h ∈ K)).card : ℂ))).im = 0 ∧
‖(∑ x : Fin k → ZMod p, G x * P x) / (p : ℂ) ^ k‖ ^ 2 ≤
((∑ x : Fin k → ZMod p, ∑ h ∈ Finset.univ.filter (fun h => h ∈ K), P x * star (P (x + h))) /
((p : ℂ) ^ k * ((Finset.univ.filter (fun h => h ∈ K)).card : ℂ))).re := by sorry
end LLROPI.Shamir
Source
Sun, Wootters, Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection, arXiv:2610.12357 (held version, sha256 f154f5ce…), Lemma 2.9, (2.6), p. 23 (PDF 25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.