Aligning Information Theory and Formal Verification: A Lean Formalization of Rate-Distortion Theory
In the authors' words
Large language models have recently demonstrated an ability to generate substantial mathematical proofs and formalizations, including machine-checked arguments for major open problems and classical theorems. These developments highlight a growing workflow in which AI systems search for proofs while proof assistants certify their correctness. Within information theory, however, formalized libraries remain limited, and existing formalized theorems focus almost exclusively on Shannon's foundational lossless theorems. This paper presents the first Lean formalization of core components of rate-distortion theory, a central framework for lossy compression and modern machine-learning analysis. We identify the alignment challenges that arise when translating information-theoretic definitions, such as distortion measures, typicality and achievability, into a proof-assistant setting, and we develop a reusable library of definitions and lemmas faithful to textbook conventions. Our formalization provides a foundation for future AI-assisted proofs in information theory and enables subsequent mechanized developments to build on a coherent, verified infrastructure rather than generating long proofs from scratch.
In plain words AI summary
This paper creates the first formal computer-checked version of rate-distortion theory using the Lean proof assistant. Rate-distortion theory is a core framework for lossy compression and modern machine-learning analysis. The authors solved alignment problems when translating information-theoretic concepts into a proof-assistant setting. They built a reusable library of definitions and lemmas that matches textbook conventions. This work provides a foundation for future AI-assisted proofs in information theory.
Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source.
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: Lean formalization and verification scripts: https://github.com/fubinyan/rate_distortion_lean4