Proof of Lemma 1 — the threshold claim
ProvedStretchDepth.threshold_claimblack-box-reductionscomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pseudorandomnessquery-complexity
Let , , and . Let be natural numbers. If , then for some ,
Applied to the critical counts , this reduces a large total of critical queries to a single round where the Critical Query bound is strong.
Differences from the source:
- generalization: the critical counts t^G_j(rho) of a run → any sequence of naturals with t 0 = 0; reason: the claim is arithmetic, and the critical counts are such a sequence (crit at 0 rounds is 0)
Preamble
import Definitions.Def_StretchDepth_crit
Formal statement
namespace StretchDepth
/-- **Threshold claim.**
Korten, *Tight Depth Lower Bounds for Stretch Amplification*, STOC 2027 submission (manuscript
sha256 32d209e2…), proof of Lemma 1, p.17: "Now, for some G, ρ and threshold τ ≥ 0, we claim that if
tG d (ρ) ≥ τ, then we must have that ℓtG j (ρ) − NtG j−1(ρ) ≥ ατ for some j."
**Formalization Note.** The claim is arithmetic: it is stated for any sequence of naturals with
`t 0 = 0`, which covers `j ↦ crit ρ G t j`. `0 < ℓ < N` holds in the page's setting. -/
theorem threshold_claim (N d : ℕ) (hd : 1 ≤ d) (ℓ τ : ℝ) (hℓ : 0 < ℓ) (hℓN : ℓ < N) (hτ : 0 ≤ τ)
(t : ℕ → ℕ) (ht0 : t 0 = 0) (htd : τ ≤ t d) :
∃ j, 1 ≤ j ∧ j ≤ d ∧ alpha N ℓ d * τ ≤ ℓ * t j - (N : ℝ) * t (j - 1) := by sorry
end StretchDepth
Source
Korten, Tight Depth Lower Bounds for Stretch Amplification, STOC 2027 submission (manuscript sha256 32d209e2…), proof of Lemma 1, p.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.