Lemma 3.4 — eventual criticality
ProvedDenseLanguageGeneration.PatientScope.eventually_criticallanguage-generationlearning-theoryonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any indexed family of infinite positive-integer languages, fix a target index , and let enumerate injectively and completely. Then
The time may depend on the family, chosen target index and enumeration. Criticality uses containment in earlier critical languages. No target minimality, scope inclusion or eventual correctness is assumed. This stabilization result supplies the criticality input for validity of patient-scope.
Differences from the source:
- encoding: positive family indices and rounds → family index i means source index i+1; stream index t means round t+1; history at completed time t has t inputs; reason: bijections preserve the countable family and every legal causal run, including the initial time zero
Preamble
import Definitions.Def_DenseLanguageGeneration_PatientScope_criticalChain set_option autoImplicit false open ActiveLanguageGeneration.Hierarchy
Formal statement
namespace DenseLanguageGeneration.PatientScope
/-- Cai et al., STOC 2027 submission #335 (October 2026), Lemma 3.4,
printed p.10 (PDF p.12). No scope or algorithm-success hypothesis. -/
theorem eventually_critical (L : Family) (i : ℕ) (a : ℕ → ℕ+)
(ha : IsEnumeration (L i) a) :
∃ T : ℕ, ∀ t ≥ T, Critical L (history a t) i := by sorry
end DenseLanguageGeneration.PatientScope
Source
Cai, Li, Shen, Wang and Zhang, STOC 2027 submission #335 (October 2026), Lemma 3.4, printed p.10 (PDF p.12); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/335.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.