Lemma 4.21, p. 14 — f_{B^L}(α) is the number of trailing 1's of (α)_2, the largest t with 2^t | α + 1
ProvedBinaryExtForm.HypercubeRank.lemma_4_21binarizationbinary-expansionhypercubep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the logarithmic binarization and . Write for the reverse of the base-2 expansion of , so that position holds the coefficient of . Then:
- is the largest number of 's in that are not preceded by any , i.e. the length of the initial run of 's of ;
- equivalently, is the largest such that divides .
Formalization Note. Positions are indexed from , position holding bit α.testBit m. Part 1 is stated as the number of positions such that bits of are all , which is the length of the initial run of 's. Part 2 is IsGreatest {t | 2 ^ t ∣ α + 1}. The single level is the one-element family ![α].
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem lemma_4_21 {d : ℕ} (α : ℕ) (hα : α + 2 ≤ 2 ^ d) :
fB (BL d) ![α] = Set.ncard {m : ℕ | m < d ∧ ∀ m' ≤ m, α.testBit m' = true} ∧
IsGreatest {t : ℕ | 2 ^ t ∣ α + 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, Lemma 4.21 ((α)_2 defined on p. 12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.