Proof of Lemma 1 — from the value bound to and
ProvedGMRDiversity.lemma_1_arithgenetic-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parity-learningquery-complexity
Let , , , and let be a real number with
Then and . If moreover , then
With this finishes the proof of the lower bound: .
Differences from the source:
- generalization: V^π_T → any real v satisfying the display bound; reason: the paragraph uses only the display; V^π_T satisfies it
Preamble
import Mathlib
Formal statement
namespace GMRDiversity
/-- **Proof of Lemma 1: "In particular"** (Brandenberger, Doron-Arad, Mossel, *Genetic Algorithms
with Optimization Guided Operators*, STOC 2027 submission, manuscript sha256 f89f4f77…, proof of
Lemma 1, p.10): if `n ≥ 2`, `1 ≤ w ≤ n` and `v ≤ 2^{−n} + ∑_{j=1}^T 2^{min{w, j−1} − n}`, then
`v ≤ 2^{T−n}` and `v ≤ 2^{−n} + T 2^{w−n}`; and if moreover `v ≥ 2/3`, then `T ≥ n ≥ w` and
`T ≥ (5/12) 2^{n−w}`. Here `v` stands for `V^π_T`. -/
theorem lemma_1_arith (n w T : ℕ) (v : ℝ) (hn : 2 ≤ n) (hw : 1 ≤ w) (hwn : w ≤ n)
(hv : v ≤ (1 + ∑ j ∈ Finset.Icc 1 T, (2 : ℝ) ^ min w (j - 1)) / 2 ^ n) :
(v ≤ (2 : ℝ) ^ T / 2 ^ n ∧ v ≤ 1 / 2 ^ n + T * 2 ^ w / 2 ^ n) ∧
(2 / 3 ≤ v → n ≤ T ∧ w ≤ T ∧ (5 / 12 : ℝ) * 2 ^ (n - w) ≤ T) := by sorry
end GMRDiversity
Source
A. Brandenberger, I. Doron-Arad, E. Mossel, Genetic Algorithms with Optimization Guided Operators, STOC 2027 submission (manuscript sha256 f89f4f770d5d05df82f0407a81287ce4ccf618727beb5415eef3ad56c36b6cbe), proof of Lemma 1, p.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.