← All papers
First page of Certifying rings of integers in number fields

Certifying rings of integers in number fields

Anne Baanen, Alain Chavarri Villarello, Sander R. Dahmen

cs.LO Sep 26, 2024 · v2 math.NT
Formalizes in Lean 4 and Mathlib a certificate-checking framework for rings of integers, with SageMath generating Lean proofs for LMFDB entries.
Number fields and their rings of integers, which generalize the rational numbers and the integers, are foundational objects in number theory. There are several computer algebra systems and databases concerned with the computational aspects of these. In particular, computing the ring of integers of a given number field is one of the main tasks of computational algebraic number theory. In this paper, we describe a formalization in Lean 4 for certifying such computations. In order to accomplish this, we developed several data types amenable to computation. Moreover, many other underlying mathematical concepts and results had to be formalized, most of which are also of independent interest. These include resultants and discriminants, as well as methods for proving irreducibility of univariate polynomials over finite fields and over the rational numbers. To illustrate the feasibility of our strategy, we formally verified entries from the $\textit{Number fields}$ section of the $\textit{L-functions and modular forms database}$ (LMFDB). These concern, for several number fields, the explicitly given $\textit{integral basis}$ of the ring of integers and the $\textit{discriminant}$. To accomplish this, we wrote SageMath code that computes the corresponding certificates and outputs a Lean proof of the statement to be verified.

Computing the ring of integers of a number field is a central task in computational algebraic number theory. Results from computer algebra systems and databases such as the LMFDB are not formally verified.

Uses a certification approach. SageMath computes certificates for a given integral basis and outputs complete Lean 4 proofs, which Lean then checks. The supporting development includes computable list-based polynomials isomorphic to Mathlib polynomials and a SubalgebraBuilder for subalgebras given by explicit bases. It also formalizes resultants, discriminants, and irreducibility proofs for polynomials over finite fields and the rationals.

Integral bases were formally verified for all 142 LMFDB degree-5 number fields unramified outside 2, 3, 5 with non-monogenic rings of integers, averaging about 33 seconds each. Integral bases and discriminants were also verified for 7 such degree-3 fields.