Lemma D.7 — short simultaneous cancellation
ProvedUniqueSVPHardness.ConstFactor.Supplement.lemma_D_7coding-theorycomputational-complexitylatticesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be prime, , and . If , there is a nonzero vector with
where also for .
Placed in a single fiber, this vector gives the short lattice vector of Theorem D.8.
Differences from the source:
- encoding: ‖c‖₂² → ∑_w c_w² in ℤ; reason: same quantity
- encoding: b = ⌈(T + 1) log₂ P⌉ → the natural-number ceiling of the real (T + 1) log₂ P; reason: same value
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace UniqueSVPHardness.ConstFactor.Supplement
/-- Lemma D.7 (short simultaneous cancellation). Let `P` be prime, `T ≥ 0`, and
`b = ⌈(T + 1) log₂ P⌉`. If `P ≥ 2(b + 1)`, there is a nonzero `c ∈ {−1, 0, 1}^{F_P}` with
`∑_w c_w = 0` over `ℤ`, `∑_w c_w w^j = 0` over `F_P` for `0 ≤ j ≤ T` (with `w^0 = 1`), and
`‖c‖₂² ≤ 2(b + 1)`. -/
theorem lemma_D_7 (P : ℕ) [Fact P.Prime] (T : ℕ)
(hP : 2 * (⌈((T : ℝ) + 1) * Real.logb 2 P⌉₊ + 1) ≤ P) :
∃ c : ZMod P → ℤ, c ≠ 0 ∧ (∀ w, c w = -1 ∨ c w = 0 ∨ c w = 1) ∧
∑ w, c w = 0 ∧
(∀ j ≤ T, ∑ w : ZMod P, (c w : ZMod P) * w ^ j = 0) ∧
∑ w, c w ^ 2 ≤ 2 * ((⌈((T : ℝ) + 1) * Real.logb 2 P⌉₊ : ℤ) + 1) := by sorry
end UniqueSVPHardness.ConstFactor.Supplement
Source
Sergei Kudria, Jason Luo, STOC 2027 submission #1647 (October 2026), p. 45, Lemma D.7