Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.14 — charging previously unannounced switch losses

Proved
DenseLanguageGeneration.PatientScope.charging

by mikedeng1 · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

language-generationlearning-theoryonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let L\mathcal LL be any indexed countable family of infinite positive-integer languages, fix K=Li⋆K=L_{i_\star}K=Li⋆​​, and let aaa be any injective full enumeration of KKK. There is one finite settling time T⋆T^\starT⋆, independent of the prefix length, for which every positive integer nnn satisfies

∣{x∈K[n]:x is a previously unannounced switch loss occurring after T⋆}∣≤log⁡2n.\bigl|\{x\in K[n]: x\text{ is a previously unannounced switch loss occurring after }T^\star\}\bigr| \le \log_2 n.​{x∈K[n]:x is a previously unannounced switch loss occurring after T⋆}​≤log2​n.

A switch loss is an input outside the preceding focus; previously unannounced excludes inputs and responses strictly before that input. The settling time also has target criticality, target inclusion in scope and focus containment at all later completed times. Counts are of distinct integers in a finite prefix.

The prefix K[n]K[n]K[n] is the first nnn target integers in increasing order, exactly the source's relabeled [n][n][n]. The coefficient is one and the logarithm has base two. No positive ambient density, finite family or algorithm-success assumption is imposed.

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
  • encoding: after choosing T* in the preceding validity proof, identify K increasingly with the positive integers and count losses in [n] → there exists one settling time T* for the run; count losses directly in the finite rank prefix K[n] of the arbitrary target; reason: packages the already established time as an existential conclusion and transports the relabeled prefix back to K without ranking invalid early outputs
Preamble
import Definitions.Def_DenseLanguageGeneration_PatientScope_density

set_option autoImplicit false
open ActiveLanguageGeneration.Hierarchy
Formal statement
namespace DenseLanguageGeneration.PatientScope

/-- Cai et al., STOC 2027 submission #335 (October 2026), Lemma 3.14,
printed pp.15--16 (PDF pp.17--18). K[n] is a rank prefix of the arbitrary
true language. A single run-dependent T* works for every positive n. -/
theorem charging (L : Family) (i : ℕ) (a : ℕ → ℕ+)
    (ha : IsEnumeration (L i) a) :
    ∃ T : ℕ, SettledFrom L i a T ∧ ∀ n : ℕ, 0 < n →
      (lossCount L i a T n : ℝ) ≤ Real.logb 2 (n : ℝ) := by sorry

end DenseLanguageGeneration.PatientScope
Source
Cai, Li, Shen, Wang and Zhang, STOC 2027 submission #335 (October 2026), Lemma 3.14 and proof, printed pp.15–16 (PDF pp.17–18); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/335.pdf
Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me