Corollary after Lemma 4 — separation of disjoint small hyperplanes
ProvedKarpPapadimitriou.Generator.corollary_lemma_4bit-complexityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-geometry
Let be any real point in the common flat of an affinely independent family of small hyperplanes. If another small hyperplane is disjoint from that flat, then, for the same parameter ,
The bound applies to a real point on the flat, without assuming that its coordinates are rational.
Formalization Note “Affinely independent” means the normals are linearly independent; the intersection is over exactly the listed family, including the empty family when .
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Generator_Hyperplanes
Formal statement
namespace KarpPapadimitriou.Generator
/-- Corollary after Lemma 4: the distance gap is constant on a flat disjoint from the new
hyperplane, including when the point on the flat is not rational. -/
theorem corollary_lemma_4 (n P m : ℕ) (c : Fin n → ℤ) (k : ℤ)
(H : Fin m → (Fin n → ℤ) × ℤ) (f : Fin n → ℤ) (g : ℤ)
(r : EuclideanSpace ℝ (Fin n))
(hsmall : ∀ i, SmallHyperplane P (H i).1 (H i).2)
(hsmall_new : SmallHyperplane P f g)
(hind : IndependentNormals H)
(hr : r ∈ flat H)
(hdisjoint : hyperplane f g ∩ flat H = ∅) :
(1 : ℝ) / 2 ^ ((n + 1) * tParam n P c k) ≤ hyperplaneDistance f g r := by sorry
end KarpPapadimitriou.Generator
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), p. 12, Corollary after Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.