Corollary 5.2 — Eight equivalent tasks for every prefix-closed class
OpenAutoregressiveCompression.Main.Supplement.corollary_5_2complexity-theorydistribution-learninginformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a finite alphabet with at least two symbols and any size-indexed prefix-closed class . The following eight polynomial-time tasks on are all equivalent:
- Autoregressive distribution learning.
- Public-coin universal compression.
- Deterministic universal compression.
- Randomized universal compression, meaning Yao's effective entropy equals Shannon entropy.
- Public-coin universal compression without an efficient decoder.
- Entropy estimation.
- Entropy gap testing.
- Distribution learning with evaluators.
The tasks act on the class itself, rather than its padded-prefix image. All compression-rate and decoder clauses and arbitrary-law estimator soundness are retained in the published task predicates. This is a support for Theorem 7.1 and the prefix-closed separation clause of Theorem 7.3.
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
- encoding: the following conditions are equivalent → List.TFAE of every listed condition in source order; reason: TFAE expresses all pairwise equivalences, retaining every clause
Preamble
import Mathlib import Definitions.Def_AutoregressiveCompression_Main_Supplement_Learning
Formal statement
namespace AutoregressiveCompression.Main.Supplement
/-- Corollary 5.2, printed pp.21–22 / PDF pp.23–24: all eight tasks,
including evaluator learning and the full randomized/Shannon-rate contract. -/
theorem corollary_5_2 {Sym : Type} [Fintype Sym] [Nontrivial Sym] (𝒟 : DistributionClass Sym)
(hclosed : 𝒟.PrefixClosed) :
List.TFAE [AutoregressiveLearnable 𝒟,
PublicCoinCompressible 𝒟,
DeterministicCompressible 𝒟,
RandomizedCompressible 𝒟,
PublicCoinCompressibleInefficientDecoder 𝒟,
EntropyEstimable 𝒟,
EntropyGapTestable 𝒟,
EvaluatorLearnable 𝒟] := 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, Corollary 5.2, printed p.21–22 / PDF p.23–24