Corollary 4.22, p. 14 — f_{B^L}(α_1,…,α_ℓ) = max{t : 2^t divides α_j + 1 for all j}
ProvedBinaryExtForm.HypercubeRank.corollary_4_22binarizationdivisibilityhypercubep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the logarithmic binarization with hypercube graph , and let with . Then
Together with Corollary 4.19 this gives the explicit formula , and together with Lemma 4.20 it shows that maximizes among hypercube binarizations.
Formalization Note. The hypothesis (0 < ℓ) is added: for every qualifies, so the maximum does not exist, while . The maximum is stated with IsGreatest, not sSup, so it is asserted to exist. encodes the range.
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem corollary_4_22 {d ℓ : ℕ} (hℓ : 0 < ℓ) (α : Fin ℓ → ℕ) (hα : ∀ j, α j + 2 ≤ 2 ^ d) :
IsGreatest {t : ℕ | ∀ j, 2 ^ t ∣ α j + 1} (fB (BL d) α) := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 14, Corollary 4.22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.