💻 computer science

Machine-Checked Arithmetic Bit Complexity of the Kannan-Bachem Smith Normal Form in Lean 4

This paper presents a formalization in Lean 4 of the Kannan-Bachem Smith normal form algorithm for nonsingular integer matrices, providing machine-checked proofs of correctness and establishing fixed polynomial bounds for both the arithmetic bit complexity of the computation and the size of its output.

Original authors: Junye Ji (University of Washington)

Published 2026-07-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Junye Ji (University of Washington)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master archivist in a library where every book is a giant, complex puzzle made of numbers. Sometimes, you need to rearrange the pages of these puzzles to find a hidden, simpler pattern underneath. This is the world of linear algebra, a branch of mathematics that deals with grids of numbers (called matrices) and how they can be transformed. Think of a matrix as a spreadsheet of integers. Just as you might sort a messy list of names alphabetically to find a pattern, mathematicians try to sort these number grids into a "Smith Normal Form"—a super-clean, diagonal version where the numbers get bigger and bigger as you go down the line, and each number divides the next one perfectly.

But here's the catch: while sorting the numbers is easy to describe, actually doing the math can be a nightmare. As you shuffle the rows and columns to clean things up, the numbers inside can explode in size, becoming so huge that they crash your computer or take a million years to calculate. For decades, mathematicians have known how to sort these grids (a method called the Kannan–Bachem algorithm), but they needed to be absolutely sure that the process wouldn't get stuck in an infinite loop and that the numbers wouldn't grow out of control. This paper steps into that gap, not just to say "it works," but to build a digital, unbreakable proof that it works, and to count exactly how much "computational energy" it takes to do so.

The Digital Double-Check

In this paper, Junye Ji from the University of Washington takes the Kannan–Bachem algorithm—a clever recipe for sorting integer matrices—and builds a machine-checked proof of it using a tool called Lean 4. Think of Lean 4 as a super-strict, robotic librarian who refuses to accept a math proof unless every single step is logically airtight. If you try to sneak in a "maybe" or a "it probably works," the robot slams the door. Ji didn't just write the code; they forced the robot to verify that the code always finishes, never crashes, and produces the exact right answer every time.

The goal was to prove that for any square grid of non-zero integers, this algorithm can transform it into its clean, diagonal "Smith Normal Form" while also keeping track of the exact moves made to get there. The result isn't just a "yes, it works" note; it's a complete, verified package containing the final sorted grid, the "forward" map of how to get there, and the "backward" map to get back to the original. It's like having a treasure map and a return ticket, both verified by a robot to ensure you don't get lost in the woods of giant numbers.

The "Pivot" Dance and the Shrinking Numbers

The heart of the algorithm is a dance called stabilization. Imagine you are trying to organize a messy room. You pick a specific spot on the floor (the "pivot") and try to make everything else in that row and column disappear. Sometimes, the math gets messy, and you can't make everything vanish perfectly. When that happens, the algorithm doesn't give up; it performs a special move that replaces the current pivot with a smaller number (a "proper divisor").

The paper proves a crucial fact: every time this special move happens, the number of bits (the binary "size") of the pivot strictly gets smaller. It's like a game where you are allowed to swap a heavy rock for a lighter pebble, and you can never swap a pebble for a heavier rock. Because you can't keep making things smaller forever (you eventually hit zero), the game must end. The authors proved that this "descent" is guaranteed, meaning the algorithm will never get stuck in an infinite loop.

Counting the Cost: The "Trace"

One of the most exciting parts of this work is how they counted the cost. Usually, when we say an algorithm is "fast," we might guess it takes a few seconds. But here, the authors wanted to know the exact arithmetic cost in terms of binary operations. They created a "flat trace," which is like a receipt that lists every single tiny math operation (addition, multiplication, division) the computer performed.

They proved that the total cost of this receipt grows at a polynomial rate. In plain English, this means that even if your input matrix gets huge, the time it takes to solve it won't explode into infinity; it will grow in a predictable, manageable way. They even calculated the specific "degree" of this growth. The paper reveals that the cost is bounded by a polynomial with a degree of 2,150,687 (for the work done) and 98,990 (for the size of the output).

Now, those numbers look terrifyingly huge, but the authors are very careful to explain what they mean. These aren't "sharp" exponents (like saying it takes exactly $n^2$ steps); they are conservative witnesses. Think of them as a safety margin. If you were to build a bridge, you might calculate that it needs to hold 100 tons, but you design it to hold 1,000 tons just to be safe. These massive numbers are the "1,000 tons" of the math world—guarantees that the algorithm is safe and efficient, even if the real-world performance is much better.

What Was Left Out?

It is important to know what this paper didn't do. The authors were very specific about the boundaries of their proof. They only counted the arithmetic operations (the math itself). They did not count the time it takes for the computer to load the data into memory, the time it takes to print the results, or the overhead of the programming language itself. They also didn't prove that this is the fastest possible way to sort matrices; they only proved that this specific way is safe, guaranteed to finish, and doesn't use more resources than their calculated polynomial limits.

The Final Verdict

So, what is the takeaway? This paper is a triumph of formal verification. It takes a complex, decades-old mathematical recipe and hands it over to a robot to check every single step. The robot confirms that the recipe always works, always finishes, and never creates numbers so big they break the system. It provides a "certificate" of correctness that includes the sorted matrix, the transformation maps, and a mathematically proven guarantee on how much work it took to get there.

For a curious teenager, this is like watching someone build a robot that not only solves a Rubik's Cube but also writes a legal contract proving it will never get stuck, never break the cube, and will do it within a specific number of moves, no matter how scrambled the cube starts. It turns a "maybe" in mathematics into a "definitely," verified by the strictest judge imaginable.

Technical Summary: Machine-Checked Arithmetic Bit Complexity of the Kannan–Bachem Smith Normal Form in Lean 4

Problem Statement
The paper addresses the formal verification of the Kannan–Bachem algorithm for computing the Smith Normal Form (SNF) of nonsingular square integer matrices. While the existence of the SNF is a standard result in algebra, the algorithmic challenge lies in controlling intermediate coefficient growth. Standard Gaussian elimination or GCD-based methods can produce integers with exponential bit-lengths relative to the input size. The Kannan–Bachem procedure (1979) offers a polynomial-time solution by alternating Hermite normal form phases and strictly decreasing the binary size of the active pivot upon divisibility failures. The specific problem tackled here is the machine-checked verification of this algorithm's correctness, its termination, and its arithmetic bit complexity within the Lean 4 proof assistant, including the generation of explicit certificates (transforming matrices and their inverses) and a verified cost model.

Methodology
The authors formalize the algorithm in Lean 4 using the mathlib library. The approach distinguishes between structural operations (matrix indexing, list manipulation) and arithmetic primitives (addition, multiplication, division on sign-magnitude integers).

Instrumented Execution: The algorithm is implemented as a "value-producing instrumented execution." Every arithmetic operation emits a "flat trace" of designated leaves (e.g., GCD, quotient/remainder, magnitude comparisons). These traces record the exact operands and the cost of the operation, allowing the total cost to be folded into a single value.
Self-Delimiting Codecs: Input and output matrices are encoded using verified prefix-free codecs. The output consists of five matrices: the Smith form $S$ , the unimodular multipliers $U$ and $V$ , and their inverses $U^{-1}$ and $V^{-1}$ . The encoding length is defined as the number of bits in a sign-magnitude representation, including framing bits.
Recursive Structure:
- Preparation: Ensures the leading principal minors are non-zero using Bird's division-free determinant algorithm.
- Stabilization: A recursive function stabilizeFrom that clears the first column and row. It relies on a "pivot descent" argument: if a divisibility test fails, the algorithm finds a proper divisor, ensuring the binary size of the pivot strictly decreases.
- Outer Recursion: Once the first row and column are cleared and the pivot divides the remaining block, the algorithm recurses on the lower-right $(n-1) \times (n-1)$ submatrix.
Cost Analysis: The complexity analysis is decoupled from the Lean runtime. The theorem bounds the "arithmetic cost" (sum of costs of primitive leaves) and the "output encoding length" (bits required to serialize the five matrices).

Key Contributions

Formalization of Kannan–Bachem: A complete formalization of the 1979 algorithm, including the construction of the transforming matrices $U, V$ and their inverses, which allows for bidirectional verification of the equivalence $UAV = S$.
Verified Arithmetic Cost: The paper proves that the total arithmetic cost and the output size are bounded by fixed polynomials of the input size. Unlike previous formalizations that may focus on algebraic correctness or operation counts, this work explicitly tracks bit-complexity using a "polynomial-envelope calculus."
Explicit Witnesses: The formalization produces concrete, machine-checked constants for the polynomial bounds. The degree of the cost polynomial is verified to be $d_c = 2,150,687$ and the output encoding degree is $d_o = 98,990$ . The coefficients are $C_c = 2^{d_c}$ and $C_o = 2^{d_o}$ . The authors note these are conservative witnesses derived from generic closure rules, not sharp exponents.
Trace Alignment: A rigorous proof that the instrumented execution (used for cost analysis) is definitionally equal to the pure mathematical function, ensuring the cost analysis applies directly to the algorithm's logical behavior.

Results
The main theorem (Theorem 2.1) establishes that for any nonsingular $n \times n$ integer matrix $A$ :

The algorithm terminates and returns $S, U, U^{-1}, V, V^{-1}$ .
The returned matrices satisfy the forward and reverse transformation equations ($UAV=S$, $U^{-1}SV^{-1}=A$ ) and the inverse identities.
$S$ is in Smith normal form and equals a canonical reference matrix defined in the library.
The arithmetic cost is bounded by $C_c (|encmat(A)| + 1)^{d_c}$ .
The encoded output length is bounded by $C_o (|encmat(A)| + 1)^{d_o}$ .

The termination is proven via a well-founded relation on the binary size of the active pivot ($Nat.size(|pivot|)$), which strictly decreases with every recursive descent.

Significance
The paper claims significance by providing a unified verification of an executable integer reduction algorithm, its inverse certificates, and its arithmetic cost within a single formal framework. While Coq and Isabelle developments have proven SNF existence in broader algebraic settings, this work focuses specifically on the integer square matrix case to verify the efficiency and correctness of a specific, executable implementation (Kannan–Bachem). The methodology is presented as a precedent for verifying efficient integer implementations and polynomial-time analysis, drawing a parallel to the verified LLL algorithm in Isabelle/HOL. The work demonstrates that machine-checked bit-complexity analysis, including the generation of explicit polynomial bounds with concrete coefficients, is feasible for non-trivial linear algebra algorithms.