Lemma 7.9 — Generator learnability passes to the padded random-prefix class
OpenAutoregressiveCompression.Main.Supplement.lemma_7_9complexity-theorydistribution-learninginformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any size-indexed class over a finite alphabet with at least two symbols. Write for the published padded uniformly random prefix class over . Then
with both tasks in uniform polynomial time. The conclusion learner receives only samples of the padded-prefix law; sample access to is not an added input. The empty-string branch uses the base point-mass convention. Finite-bit approximation error for random truncation is included in the requested learning tolerance. This support transfers generator learning to the class needed by the companion separation theorem.
Differences from the source:
- encoding: a fixed finite alphabet with at least two symbols and size-indexed string laws → Fintype and Nontrivial on Sym, with the published DistributionClass and PMF interfaces; reason: the standing convention of Section 4.2; arbitrary real target masses and the empty-string case are preserved
- encoding: uniform polynomial-time sample learners outputting evaluators or generators → finite Program execution and fixed polynomial bounds with explicit circuit descriptions, normalized evaluator masses, and evaluated uniform-seed generator masses; reason: Definition 4.5 made operational using the existing bit/sample interface; no task reductions are assumed and fair-bit approximation errors must fit the requested tolerance
Preamble
import Mathlib import Definitions.Def_AutoregressiveCompression_Main_Supplement_Learning
Formal statement
namespace AutoregressiveCompression.Main.Supplement
/-- Lemma 7.9, printed p.41 / PDF p.43: the conclusion learner receives
only padded-prefix samples. Length zero uses the published point-mass semantics.
Finite fair-bit approximation is included in the requested accuracy budget. -/
theorem lemma_7_9 {Sym : Type} [Fintype Sym] [Nontrivial Sym] (𝒟 : DistributionClass Sym)
(h : GeneratorLearnable 𝒟) :
GeneratorLearnable 𝒟.prefix := by sorry
end AutoregressiveCompression.Main.Supplement
Source
Shuichi Hirahara, Mikito Nanashima, STOC 2027 submission #793 (October 2026); source.pdf, SHA-256 31e908b0cf51447e89626d9dc6d947c279aec5642ec7b320ceb07ec9b1348341; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/793.pdf, Lemma 7.9, printed p.41 / PDF p.43