Lemma 4 — distance from a rational point to a small hyperplane
ProvedKarpPapadimitriou.Generator.lemma_4bit-complexityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-geometry
Fix dimension , coefficient exponent , objective , threshold , and the paper's parameter . Let have every reduced denominator at most . If is a small hyperplane with , then
This supplies a lower gap when the generator produces a hyperplane not containing the current rational point.
Formalization Note The report prints “” where its preceding point is ; the binder uses . The Euclidean distance is stated by the equivalent quotient formula after casting to real coordinates.
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Generator_Hyperplanes
Formal statement
namespace KarpPapadimitriou.Generator
/-- Lemma 4: a rational point outside a small hyperplane has a quantified distance gap. -/
theorem lemma_4 (n P : ℕ) (c : Fin n → ℤ) (k : ℤ)
(r : Fin n → ℚ) (f : Fin n → ℤ) (g : ℤ)
(hsmall : SmallHyperplane P f g)
(hden : ∀ i, (r i).den ≤ 2 ^ tParam n P c k)
(hout : dotQ f r ≠ (g : ℚ)) :
(1 : ℝ) / 2 ^ ((n + 1) * tParam n P c k) ≤
hyperplaneDistance f g (realPoint r) := by sorry
end KarpPapadimitriou.Generator
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), p. 12, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.