Theorem 4.6 — Complement GapSVP at the source approximation factor reduces to SSLB
OpenAMRangeAvoid.Characterization.Supplement.theorem_4_6complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
For take , and put . This factor has the source asymptotic order and gives a deterministic polynomial-time many-one reduction
The input ranges over every positive dimension, every nonsingular rational basis and every positive rational threshold. YES means , while NO means . There is no integrality, fixed-dimension or threshold-normalization restriction.
Differences from the source:
- encoding: the existential factor realized in the proof as 400 ceil(sqrt(n/log₂ n)) → that proof factor for n at least two, with value 400 in dimension one and uniform positive Theta constants; reason: the printed quotient is undefined at n=1; exact one-dimensional comparison retains those instances without changing the positive-dimensional problem or the asymptotic factor
- encoding: shortest nonzero length compared with d or gamma d → existential short-vector and universal strict long-vector predicates in EuclideanSpace; reason: positive dimension and nonsingularity ensure the minimum is attained, so these are equivalent comparisons without default-valued infima
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Lattices import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement
theorem theorem_4_6 :
SqrtTheta gamma ∧ PromiseReduces (CoGapSVP gamma) SSLB := by sorry
end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Theorem 4.6, printed p.21 (PDF p.23); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf