Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.1 — All nine learning, compression and entropy tasks are equivalent for SIZE(n)-samplable distributions

Open
AutoregressiveCompression.Main.Supplement.theorem_7_1

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

complexity-theorydistribution-learninginformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Fix a finite alphabet Σ\SigmaΣ with at least two symbols. Let Cncirc\mathcal C^{\rm circ}_nCncirc​ be exactly the distributions generated by deterministic circuits with at most nnn gates and output length at most nnn, on independent uniform seed bits. The following nine polynomial-time tasks on this single size-indexed class are equivalent:

  1. Autoregressive distribution learning.
  2. Public-coin universal compression.
  3. Deterministic universal compression.
  4. Randomized universal compression, meaning Yao's effective entropy coincides with Shannon entropy on Ccirc\mathcal C^{\rm circ}Ccirc.
  5. Public-coin universal compression without an efficient decoder.
  6. Entropy estimation.
  7. Entropy gap testing.
  8. Distribution learning with evaluators.
  9. Distribution learning with generators.
(1)⟺(2)⟺(3)⟺(4)⟺(5)⟺(6)⟺(7)⟺(8)⟺(9).(1)\Longleftrightarrow(2)\Longleftrightarrow(3)\Longleftrightarrow(4)\Longleftrightarrow(5)\Longleftrightarrow(6)\Longleftrightarrow(7)\Longleftrightarrow(8)\Longleftrightarrow(9).(1)⟺(2)⟺(3)⟺(4)⟺(5)⟺(6)⟺(7)⟺(8)⟺(9).

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

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