Corrected volume lower bound
ProvedLinearOptimization.polyhedron_full_dim_volume_lower_bound_nonstrictconvex-geometryellipsoid-methodlinear-optimizationtextbook-erratum
Corrected boundary-sharp form of Lemma 8.4. Let be a full-dimensional bounded polyhedron, where , the entries of and are integers, and their absolute values are bounded by the integer . Then
This keeps the constant and every hypothesis of the printed lemma, but replaces its false strict inequality by a non-strict inequality. The correction is sharp: for and , both sides equal .
Preamble
import Definitions.Def_LinearOptimization_Ellipsoid import Definitions.Def_Polyhedron open Matrix MeasureTheory
Formal statement
theorem LinearOptimization.polyhedron_full_dim_volume_lower_bound_nonstrict
{m n : ℕ} (hn : 0 < n)
(A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ) (U : ℤ)
(hA : ∀ i j, |A i j| ≤ U) (hb : ∀ i, |b i| ≤ U)
(hbdd : LinearOptimization.IsBoundedSet
(LinearOptimization.polyhedron
(A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ))))
(hfull : LinearOptimization.IsFullDimensional
(LinearOptimization.polyhedron
(A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ)))) :
ENNReal.ofReal
(((n : ℝ) ^ n * ((n : ℝ) * (U : ℝ)) ^ (n ^ 2 * (n + 1)))⁻¹) ≤
volume (LinearOptimization.polyhedron
(A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ))) := by
sorrySource
Corrected boundary-sharp form of Bertsimas and Tsitsiklis, Introduction to Linear Optimization (Athena Scientific, 1997), Lemma 8.4, p. 376 and its proof on pp. 376-377. The printed strict inequality is false at n = U = 1, P = [0,1]; the corrected statement replaces > by ≥ and leaves the hypotheses and constant unchanged.