Aligning Information Theory and Formal Verification: A Lean Formalization of Rate-Distortion Theory
En palabras de los autores
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.
En palabras simples Resumen con IA
Este artículo crea la primera versión formal verificada por computadora de la teoría de tasa-distorsión usando el asistente de pruebas Lean. La teoría de tasa-distorsión es un marco central para la compresión con pérdida y el análisis moderno de aprendizaje automático. Los autores resolvieron problemas de alineación al traducir conceptos de teoría de la información a un entorno de asistente de pruebas. Construyeron una biblioteca reutilizable de definiciones y lemas que coincide con las convenciones de los libros de texto. Este trabajo proporciona una base para futuras pruebas asistidas por IA en teoría de la información.
Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale.
Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: Lean formalization and verification scripts: https://github.com/fubinyan/rate_distortion_lean4