Irrationality and Transcendence Criteria for Infinite Series in Isabelle/HOL

Angeliki Koutsoukou-Argyraki, Wenda Li, Lawrence C. Paulson

TL;DR

This paper details the formalization of complex number theory results concerning irrationality and transcendence criteria for infinite series within the proof assistant Isabelle/HOL. The authors demonstrate the feasibility of translating cutting-edge mathematical research into a verifiable, machine-checked format, highlighting the potential of formal methods to enhance mathematical rigor and uncover subtle details in proofs.

What Problem Does This Paper Address?

The paper addresses the challenge of bridging the gap between "mainstream mathematical research" and formal verification. While proof assistants like Isabelle/HOL are powerful tools for ensuring mathematical correctness, their application to recent, unpolished research papers (as opposed to textbook material) is less explored. The authors aim to assess how receptive such research is to formalization, what challenges arise, and what insights can be gained by formalizing proofs from three specific papers on irrationality and transcendence criteria for infinite series. This involves not only translating theorems but also filling in implicit reasoning steps that are common in human-written proofs.

Methods

The core method is formalization using the Isabelle/HOL proof assistant. The authors translate theorems and their proofs from three research papers into Isabelle/HOL's formal language. This process involves:

  • Formalizing Statements: Precisely stating the theorems and their conditions in Isabelle/HOL.
  • Developing Proofs: Constructing step-by-step, machine-checkable proofs for these theorems. This often requires elaborating on implicit arguments present in the original papers, essentially "filling in the gaps."
  • Leveraging Automation: Utilizing Isabelle/HOL's automated tools, such as Sledgehammer, metis, and smt, to assist in finding proofs for complex steps.
  • Domain-Specific Tactics: Employing specialized tactics like real_asymp for handling real number asymptotics, which significantly streamlines proofs involving limits and approximations.
  • Locale Mechanism: Using Isabelle's locale mechanism to package assumptions and contexts, particularly for theorems like Roth's theorem, which are used as foundational elements without their proofs being formalized within this work.

Datasets

Not discussed in the paper. The "datasets" in this context are the mathematical theorems and proofs from the three research papers by Erdős and Straus, Hančl, and Hančl and Rucki.

Key Insights and Ideas

  • Bridging the Research Gap: Formalizing recent research papers, rather than just textbook material, is a valuable endeavor that can reveal implicit assumptions and provide a deeper understanding of the proofs.
  • The Value of Elaboration: Formalization necessitates making explicit many intermediate steps that are often glossed over in human proofs. This process can lead to more robust and understandable proofs, even if it increases their length.
  • Automation is Crucial, but Not Sufficient: While tools like Sledgehammer are invaluable for automating parts of the proof process, domain-specific tactics (like real_asymp) are essential for tackling specific mathematical domains effectively.
  • Formalization as a Debugging Tool: The formalization process can uncover subtle errors or omissions in original proofs, as seen with a slight mistake in one of the Hančl and Rucki proofs, which was resolved with author input.
  • Trusting Fundamental Results: For practical formalization of advanced mathematics, it's often necessary to assume the correctness of fundamental, well-established theorems (like Roth's theorem) whose proofs are not formalized within the current scope. This mirrors how mathematicians work in practice.

Key Results

  • Successful Formalization: The authors successfully formalized several key results on irrationality and transcendence criteria for infinite series from three research papers.
  • De Bruijn Factors: The formal proofs were significantly longer than the original informal proofs, resulting in de Bruijn factors (ratio of formal to informal proof size) of approximately 25, 21, and 13 for the Erdős-Straus, Hančl, and Hančl-Rucki papers, respectively. These higher factors are attributed to the need to explicitly formalize intermediate arguments.
  • Library Enrichment: The formalization process led to the addition of new lemmas and the modification of existing ones in the Isabelle/HOL libraries, such as detailed formalizations of infinite products and a modified ratio test for series.
  • Discovery of Minor Issues: A slight mistake was identified in one of the original proofs, which was corrected with input from the authors.

Limitations and Future Work

  • Proof of Fundamental Theorems: The formalization relies on the assumption of certain fundamental theorems (e.g., Roth's theorem) whose proofs were not formalized. The authors acknowledge that a truly bottom-up approach would require formalizing all prerequisites.
  • Automation for Specific Functions: The real_asymp tactic, while powerful, does not yet support functions like nth_prime directly, requiring special treatment or manual proofs for such cases. Future work could involve extending real_asymp to handle these functions.
  • Tedious Calculations: Some proofs, particularly those involving prime numbers and real asymptotics, still involve tedious, repetitive calculations that could benefit from further automation or optimization.
  • De Bruijn Factor Interpretation: The authors note that the precision of de Bruijn factors can be debated due to variations in text density, but they provide estimates based on line counts.

The authors express hope that their work will be useful to both experienced proof assistant users and those new to formalizing mathematical research, encouraging further exploration in this area.

Summary updated

Abstract

We give an overview of our formalizations in the proof assistant Isabelle/HOL of certain irrationality and transcendence criteria for infinite series from three different research papers: by Erdős ...
BibTeX
@inproceedings{koutsoukouargyraki2022irrationality,
  author = {Angeliki Koutsoukou-Argyraki and Wenda Li and Lawrence C. Paulson},
  title = {{Irrationality and Transcendence Criteria for Infinite Series in Isabelle/HOL}},
  booktitle = {Exp. Math},
  year = {2022},
  url = {https://openreview.net/forum?id=wIGQz3rvtSM},
}
Figure