Lemma 4.20, p. 13 — 2^{f_B(α_1,…,α_ℓ)} divides α_j + 1 for every j
ProvedBinaryExtForm.HypercubeRank.lemma_4_20binarizationdivisibilityhypercubep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a -hypercube binarization with hypercube graph and let . Then for every ,
The number of uncrossed directions of an arbitrary hypercube binarization is thus bounded by the -adic valuations of the , which is exactly what the logarithmic binarization attains (Corollary 4.22).
Formalization Note. encodes the range . For the statement is vacuous, as on the page.
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem lemma_4_20 {d ℓ : ℕ} (B : Set (Fin (d + 1) → ℝ)) (hB : IsHypercubeBinarization d B)
(α : Fin ℓ → ℕ) (hα : ∀ j, α j + 2 ≤ 2 ^ d) :
∀ j, 2 ^ fB B α ∣ α j + 1 := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 13, Lemma 4.20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.