Theorem 4.23, p. 14 — every d-hypercube binarization has rank at least that of the logarithmic binarization
ProvedBinaryExtForm.HypercubeRank.theorem_4_23Let be a -hypercube binarization (its vertices project bijectively onto and have the -values ), let be the logarithmic binarization , and let . Then
Here for points (Definition 4.7): the least number of convexifications of -variables that removes all points of with strictly between and .
Among all binarizations whose vertices form a -dimensional hypercube with distinct integer -values, the logarithmic binarization needs the fewest sequential convexification steps to eliminate any prescribed family of fractional -ranges.
Formalization Note. The fractional points are chosen independently for (xbar) and for (xbarL), each with ; the statement holds for every such choice, so no lemma on the independence of from the choice is needed. The range is written . No hypothesis is added to the page's; is allowed.
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
namespace BinaryExtForm.HypercubeRank
theorem theorem_4_23 {d ℓ : ℕ} (B : Set (Fin (d + 1) → ℝ)) (hB : IsHypercubeBinarization d B)
(α : Fin ℓ → ℕ) (hα : ∀ j, α j + 2 ≤ 2 ^ d)
(xbar xbarL : Fin ℓ → ℝ)
(hx : ∀ j, (α j : ℝ) < xbar j ∧ xbar j < α j + 1)
(hxL : ∀ j, (α j : ℝ) < xbarL j ∧ xbarL j < α j + 1) :
rk (BL d) xbarL ≤ rk B xbar := by sorry
end BinaryExtForm.HypercubeRank
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.