Proof of Theorem 6.3 —
ProvedMLManagesComplexity.kl_from_uniformcomputational-complexitycryptographyinformation-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
For every distribution on , with the uniform distribution and logarithms base 2,
both sides being when gives probability to some string.
This is the cross-entropy decomposition for the uniform distribution, whose entropy is ; it is the last step of the proof of Theorem 6.3.
Differences from the source:
- generalization: µ the P/poly-computable model with polynomially-bounded max-entropy of Theorem 6.3 → µ any distribution on {0,1}^n; reason: the identity uses nothing about µ (if µ misses a point both sides are +∞); the source's µ is a special case
- encoding: KL-divergence and cross-entropy (possibly infinite, p.5: "even infinite if for some x, τ(x) > µ(x) = 0") → the published
klBits/crossEntropyinEReal,⊤exactly on a support mismatch, logarithms base 2; reason: Lean convention; same values
Preamble
import Mathlib import Definitions.Def_MLManagesComplexity_lexCDF set_option autoImplicit false open AutoregressiveCompression.Main
Formal statement
namespace MLManagesComplexity
/-- **KL from uniform** (Fortnow, *How Does Machine Learning Manage Complexity?*, arXiv:2604.07233 (version of 2026-10-31, sha256 4874d83f…), Proof of Theorem 6.3, printed p.11, PDF p.12: "KL(U‖μ) =
E_{x∼U}[log(1/μ(x))] − n"). For every distribution `μ` on `{0,1}^n`, the KL divergence of the
uniform `U` from `μ` equals the cross-entropy of `U` under `μ` minus `n` (bits).
**Formalization Note** In `EReal`; when `μ` misses a point both sides are `⊤`. -/
theorem kl_from_uniform {n : ℕ} (μ : PMF (Fin n → Bool)) :
klBits (uniformFamily n) μ = crossEntropy (uniformFamily n) μ - (n : EReal) := by sorry
end MLManagesComplexity
Source
Fortnow, How Does Machine Learning Manage Complexity?, arXiv:2604.07233 (version of 2026-10-31, sha256 4874d83f…), Proof of Theorem 6.3, p.11 (PDF p.12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.