Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.15 — optimal one-half lower density, including validity

Proved
DenseLanguageGeneration.PatientScope.optimal_lower_density

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

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

For every indexed countable family L=(L1,L2,…)\mathcal L=(L_1,L_2,\ldots)L=(L1​,L2​,…) of infinite positive-integer languages, every target K=Li⋆K=L_{i_\star}K=Li⋆​​ and every injective full enumeration aaa of KKK, the operational patient-scope generator GLG_{\mathcal L}GL​ generates KKK in the limit without repeating a previous announcement, and

ld⁡(GL,K,a)=lim inf⁡n→∞μn(D∩K)μn(K)≥12.\operatorname{ld}(G_{\mathcal L},K,a) =\liminf_{n\to\infty}\frac{\mu_n(D\cap K)}{\mu_n(K)}\ge\frac12.ld(GL​,K,a)=n→∞liminf​μn​(K)μn​(D∩K)​≥21​.

Here DDD is computed from first announcements in the actual run, and μn\mu_nμn​ counts the ambient prefix {1,…,n}\{1,\ldots,n\}{1,…,n}. Optimality has the matching worst-case meaning: for every family L\mathcal LL, every target K=LiK=L_{i}K=Li​ in it, and every deterministic generator GGG (which may depend on L\mathcal LL),

∃a an injective full enumeration of K:ld⁡(G,K,a)≤12.\exists a\text{ an injective full enumeration of }K: \quad\operatorname{ld}(G,K,a)\le\frac12.∃a an injective full enumeration of K:ld(G,K,a)≤21​.

The family is fixed before the secret target and its run; neither is a generator argument. Quantification over all legal full streams covers adaptive adversaries because the generator is deterministic and causal. Competitors are arbitrary finite-history generators, without an additional freshness or validity restriction. The adversary's witness must enumerate every member of KKK, including integers already output by the generator. Taking the constant family Li=N+L_i=\mathbb N_+Li​=N+​ gives the single-language instance.

This is the full deterministic single-order result with its §2 optimality context. It does not assert that every patient-scope run has density exactly one half. Validity and the density guarantee are conclusions, not input assumptions.

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: optimal lower density 1/2, with the universal validity objective and deterministic upper bound stated in section 2 → one conjunction of universal validity and at-least-one-half density for patient-scope, plus, for every family, target and deterministic generator, a legal full enumeration of that target with lower density at most one half; reason: makes the source optimality quantifiers explicit; all legal full enumerations are included and no competing generator is excluded
  • encoding: real ambient-prefix liminf with a denominator that is eventually nonzero → real Filter.liminf, using zero for ratios at zero denominator; reason: K is infinite, every ratio lies in [0,1], and only finitely many initial prefixes have zero denominator
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), Theorem 3.15,
printed pp.16--17 (PDF pp.18--19), with deterministic sharpness from §2,
printed p.8 (PDF p.10). Validity and the exact half guarantee hold on every legal
run of the operational algorithm. For every family and every target in it, every
deterministic competitor (chosen after the family) faces a legal full enumeration of
that target with lower density at most one half. -/
theorem optimal_lower_density :
    (∀ (L : Family) (i : ℕ) (a : ℕ → ℕ+), IsEnumeration (L i) a →
      Generates (generator L) (L i) a ∧
      (1 / 2 : ℝ) ≤ lowerDensity (generator L) (L i) a) ∧
    (∀ (L : Family) (i : ℕ) (G : Generator ℕ+), ∃ a : ℕ → ℕ+,
      IsEnumeration (L i) a ∧ lowerDensity G (L i) a ≤ (1 / 2 : ℝ)) := by sorry

end DenseLanguageGeneration.PatientScope
Source
Cai, Li, Shen, Wang and Zhang, STOC 2027 submission #335 (October 2026), Theorem 3.15 and proof, printed pp.16–17 (PDF pp.18–19); Definitions 2.1–2.2, printed p.7 (PDF p.9); deterministic sharpness paragraph, printed p.8 (PDF p.10); 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