Algebraic Numbers in Isabelle/HOL

René Thiemann 📧, Akihisa Yamada 📧 and Sebastiaan J. C. Joosten 📧 with contributions from Manuel Eberl 🌐

December 22, 2015

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

Based on existing libraries for matrices, factorization of rational polynomials, and Sturm's theorem, we formalized algebraic numbers in Isabelle/HOL. Our development serves as an implementation for real and complex numbers, and it admits to compute roots and completely factorize real and complex polynomials, provided that all coefficients are rational numbers. Moreover, we provide two implementations to display algebraic numbers, an injective and expensive one, or a faster but approximative version.

To this end, we mechanized several results on resultants, which also required us to prove that polynomials over a unique factorization domain form again a unique factorization domain.

BSD License

Change history

April 16, 2017

Use certified Berlekamp-Zassenhaus factorization, use subresultant algorithm for computing resultants, improved bisection algorithm

January 29, 2016

Split off Polynomial Interpolation and Polynomial Factorization

Topics

Theories of Algebraic_Numbers