Theorem 7.1 — All nine learning, compression and entropy tasks are equivalent for SIZE(n)-samplable distributions
OpenAutoregressiveCompression.Main.Supplement.theorem_7_1complexity-theorydistribution-learninginformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a finite alphabet with at least two symbols. Let be exactly the distributions generated by deterministic circuits with at most gates and output length at most , on independent uniform seed bits. The following nine polynomial-time tasks on this single size-indexed class are equivalent:
- Autoregressive distribution learning.
- Public-coin universal compression.
- Deterministic universal compression.
- Randomized universal compression, meaning Yao's effective entropy coincides with Shannon entropy on .
- Public-coin universal compression without an efficient decoder.
- Entropy estimation.
- Entropy gap testing.
- Distribution learning with evaluators.
- Distribution learning with generators.
This theorem is unconditional and is a companion to the mission goal. All uniform polynomial bounds, the Shannon-rate redundancy, and all decoder and entropy-soundness clauses are preserved by the task definitions. It is not an assertion about one fixed circuit or one fixed output length.
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
- encoding: sampler circuit size is number of gates, with output length at most n → the published fan-in-two Boolean vector circuits with gate-list size, uncharged input and output wires, and fixed one-hot symbol encoding; reason: the source fixes no gate basis; this commits to an ordinary concrete basis and does not assume a comparison or reindexing theorem
Preamble
import Mathlib import Definitions.Def_AutoregressiveCompression_Main_Supplement_Learning import Definitions.Def_AutoregressiveCompression_Main_Supplement_CircuitClass
Formal statement
namespace AutoregressiveCompression.Main.Supplement
/-- Theorem 7.1, printed p.37 / PDF p.39. All nine clauses; unconditional.
The gate size and uniform-seed law of Ccirc are concretely defined. -/
theorem theorem_7_1 {Sym : Type} [Fintype Sym] [Nontrivial Sym] :
List.TFAE [AutoregressiveLearnable (Ccirc Sym),
PublicCoinCompressible (Ccirc Sym),
DeterministicCompressible (Ccirc Sym),
RandomizedCompressible (Ccirc Sym),
PublicCoinCompressibleInefficientDecoder (Ccirc Sym),
EntropyEstimable (Ccirc Sym),
EntropyGapTestable (Ccirc Sym),
EvaluatorLearnable (Ccirc Sym),
GeneratorLearnable (Ccirc Sym)] := 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, Theorem 7.1, printed p.37 / PDF p.39