← All papers
First page of Formalization of Amicable Numbers Theory

Formalization of Amicable Numbers Theory

Zhipeng Chen, Haolun Tang, Jingyi Zhan

cs.LO Jan 12, 2026 · v1
Formalizes the theory of amicable numbers in Lean 4, including Thabit's rule, Euler's rule, and the Borho-Hoffmann method.
This paper presents a formalization of the theory of amicable numbers in the Lean~4 proof assistant. Two positive integers $m$ and $n$ are called an amicable pair if the sum of proper divisors of $m$ equals $n$ and the sum of proper divisors of $n$ equals $m$. Our formalization introduces the proper divisor sum function $\propersum(n) = σ(n) - n$, defines the concepts of amicable pairs and amicable numbers, and computationally verifies historically famous amicable pairs. Furthermore, we formalize basic structural theorems, including symmetry, non-triviality, and connections to abundant/deficient numbers. A key contribution is the complete formal proof of the classical Thābit formula (9th century), using index-shifting and the \texttt{zify} tactic. Additionally, we provide complete formal proofs of both Thābit's rule and Euler's generalized rule (1747), two fundamental theorems for generating amicable pairs. A major achievement is the first complete formalization of the Borho-Hoffmann breeding method (1986), comprising 540 lines with 33 theorems and leveraging automated algebra tactics (\texttt{zify} and \texttt{ring}) to verify complex polynomial identities. We also formalize extensions including sociable numbers (aliquot cycles), betrothed numbers (quasi-amicable pairs), parity constraint theorems, and computational search bounds for coprime pairs ($>10^{65}$). We verify the smallest sociable cycle of length 5 (Poulet's cycle) and computationally verify specific instances. The formalization comprises 2076 lines of Lean code organized into Mathlib-candidate and paper-specific modules, with 139 theorems and all necessary infrastructure for divisor sum multiplicativity and coprimality reasoning.

Amicable numbers theory, including classical generation rules by Thabit and Euler and the modern Borho-Hoffmann breeding method, lacked formal machine-checked proofs despite centuries of mathematical development.

The authors formalize amicable number theory in Lean 4 with Mathlib. Core definitions (proper divisor sum, amicable pairs) are implemented, and classical generation rules are proved: Thabit's formula using index-shifting and the zify tactic, Euler's generalized rule, and the Borho-Hoffmann breeding method (540 lines, 33 theorems). The ring and zify tactics handle complex polynomial identities. Extensions include sociable numbers, betrothed numbers, and parity constraints.

The formalization comprises 2076 lines of Lean code with 139 theorems. It includes the first complete formalization of the Borho-Hoffmann breeding method, verification of historically famous amicable pairs (220,284), Poulet's sociable cycle of length 5, and computational search bounds for coprime pairs (>10^65).