💬 NLP

Formalizing building-up constructions of self-dual codes through isotropic lines in Lean

This paper establishes the equivalence between Kim's and Chinburg-Zhang's constructions of binary self-dual codes, extends the latter to $q$ -ary fields where $q \equiv 1 \pmod{4}$ by leveraging the condition that $-1$ is a square to unify algebraic and geometric perspectives, and provides a Lean 4 formalization of these results to efficiently construct various optimal and MDS self-dual codes.

Original authors: Jae-Hyun Baek, Jon-Lark Kim

Published 2026-04-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jae-Hyun Baek, Jon-Lark Kim

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 an architect trying to build a perfect, self-balancing tower. In the world of mathematics, this "tower" is called a self-dual code. These are special patterns of numbers used to send messages (like emails or space signals) that can fix themselves if parts get scrambled during transmission.

The goal of this paper is to find the best, most efficient blueprints for building these towers, especially when using specific types of number systems (like counting in base 5 or base 13).

Here is the breakdown of what the authors did, using simple analogies:

1. The Two Ways to Build a Tower

The authors discovered that two famous methods for building these codes were actually the same thing, just looked at from opposite directions.

Method A (Kim's Building-Up): Imagine you have a small, stable tower. To make it bigger, you add a new floor. But you can't just throw bricks anywhere; you have to add a specific "correction beam" to keep the tower balanced. This is the Building-Up Construction.
Method B (Chinburg-Zhang's Boxed Reduction): Imagine you have a huge, complex tower. To understand it, you take off the top floor and a special corner piece. What's left is a smaller, simpler tower. This is the Boxed Reduction.

The Big Discovery: The authors proved that these two methods are mirror images. If you know how to build a tower floor-by-floor (Method A), you automatically know how to take it apart piece-by-piece (Method B). They are the same "mechanism" viewed from the top down or bottom up.

2. The Secret Ingredient: The "Magic Number"

To build these towers in the specific number systems the paper focuses on (where $q \equiv 1 \mod 4$ ), there is a secret ingredient required: a number that, when squared, equals -1.

In normal math, you can't square a number to get a negative. But in these specific "finite fields" (like a clock that only goes up to 5 or 13), such a number exists.
The Analogy: Think of this number as a magic key. Once you have this key, the geometry of the space changes. A flat, boring square grid suddenly becomes a "hyperbolic plane" (like a saddle shape). This shape allows the architects to find "isotropic lines"—special paths where the rules of distance behave differently, making it possible to build the perfect self-dual towers.

3. The New Blueprint: The "Split Boxed" Design

The authors created a new, highly organized blueprint called the "Split Boxed Construction."

Old Way: Previously, when adding a new floor to the tower, the architects had to guess a random vector (a list of numbers) that fit the balance. It was like trying to find a puzzle piece by looking in a dark room.
New Way: The authors realized that the "correction beam" isn't random at all. It follows a strict rule based on that "magic key" (the isotropic line).
The Result: They created a formula that tells you exactly where to put every single brick. No guessing. It's like having a 3D printer that knows exactly where every piece goes to ensure the tower never falls.

4. Putting It to the Test (The Applications)

The authors didn't just write theory; they built actual towers to prove it works. They used their new blueprint to construct the "best possible" towers for specific sizes:

Over GF(5): They built a 6-story tower and an 8-story tower that are perfectly balanced and as strong as mathematically possible.
Over GF(13): They built 8, 10, and 12-story towers. These are "optimal," meaning you cannot make them stronger or more efficient without breaking the rules of math.

5. The "Digital Twin" (Lean 4 Formalization)

This is perhaps the most unique part of the paper. The authors didn't just write the math on paper; they translated the entire logical argument into a computer language called Lean 4.

The Analogy: Imagine writing a recipe for a cake. Usually, you just trust the chef. But here, the authors fed the recipe into a super-strict robot chef (the Lean computer).
The Result: The robot checked every single step, every logical jump, and every definition. It confirmed that the recipe is 100% correct with zero errors. They built a "digital twin" of their mathematical proof that is guaranteed to be true.

Summary

In short, this paper says:

We found that two different ways of thinking about code construction are actually the same.
We discovered a "magic key" (a number that squares to -1) that unlocks a special geometric shape, making it easy to build perfect codes.
We created a precise, non-guessing formula to build these codes efficiently.
We used this formula to build the strongest possible codes for small sizes.
We used a computer to prove that our logic is flawless.

This work helps engineers and mathematicians design better error-correcting codes for future technology, ensuring our digital communications remain clear and secure.

1. Problem Statement

The construction and classification of self-dual codes (codes where $C = C^\perp$ ) are central problems in coding theory. While various methods exist (e.g., gluing, automorphism groups, Hadamard matrices), there is a lack of a universal, efficient construction method that applies to all lengths and fields.

Binary Case: Kim's "building-up" construction allows constructing self-dual codes of length $2n+2$ from length $2n$ . Independently, Chinburg and Zhang provided a topological/cohomological construction using Hilbert symbols and étale cohomology. However, the relationship between these two distinct approaches was not formally established.
$q$ -ary Case: Generalizing building-up constructions to finite fields $\mathbb{F}_q$ (where $q \equiv 1 \pmod 4$ ) is possible, but the correction terms added to generator matrices are often presented as arbitrary vectors with specific norm properties. A precise geometric characterization of these terms was missing.
Formalization Gap: Despite the theoretical importance of these algebraic structures, rigorous formal verification of these coding-theoretic theorems using proof assistants (like Lean) has been limited.

2. Methodology

The authors employ a multi-faceted approach combining algebraic coding theory, hyperbolic geometry, and formal verification:

Algebraic & Geometric Unification:
- The paper focuses on fields where $q \equiv 1 \pmod 4$ , ensuring $-1$ is a square in $\mathbb{F}_q$ . This allows the Euclidean plane to be decomposed into a hyperbolic plane.
- The authors introduce the concept of an isotropic line (a 1D subspace where the quadratic form vanishes) spanned by $(1, c)$ where $c^2 = -1$ .
- They demonstrate that the "correction terms" in building-up constructions are not random but are naturally organized by these isotropic lines.
Theoretical Framework:
- Binary Case: They prove that Kim's building-up construction and Chinburg-Zhang's Hilbert symbol construction are inverse operations of the same mechanism. Specifically, Chinburg-Zhang's "boxed reduction" (top-down) is the Lagrangian reduction counterpart to Kim's "building-up" (bottom-up).
- $q$ -ary Case: They generalize the "boxed" normal form to split $q$ -ary fields. They define a split boxed form where the generator matrix has a specific block structure governed by the isotropic line $(1, c)$ .
Formalization (Lean 4):
- The authors formalized the core algebraic logic in a single Lean 4 file (BuildingUpFormalization.lean).
- They utilized Mathlib's linear algebra and bilinear form libraries to define self-dual codes, Lagrangian subspaces, and orthogonality.
- The formalization covers 256 theorems with zero sorry (unproven gaps), verifying the equivalence of constructions, the existence of isotropic decompositions, and the correctness of the forward/reverse building-up steps.

3. Key Contributions

A. Theoretical Equivalence (Binary Case)

The paper establishes Theorem 3.4, proving that the Chinburg-Zhang cohomological reduction and Kim's building-up construction are the same predecessor-successor mechanism viewed from opposite directions.

Chinburg-Zhang: A top-down reduction that deletes a distinguished hyperbolic pair from a "boxed" matrix.
Kim: A bottom-up extension that adds a row based on an isotropic line decomposition.
Result: The arithmetic code is Lagrangian; the reduction removes a hyperbolic pair, forcing the remaining rows to satisfy Kim's correction formula.

B. Generalized Split Boxed Construction ( $q$ -ary Case)

The authors introduce Theorem 3.12, a "Split Boxed Form" for self-dual codes over $\mathbb{F}_q$ ( $q \equiv 1 \pmod 4$ ).

Structure: The generator matrix is organized into blocks where off-diagonal entries are multiples of the isotropic vector $(1, c)$ .
Mechanism: The construction relies on the identity $c^2 = -1$ . The correction terms in the extension formulas are explicitly determined by the inner products with the new vector $x$ and the isotropic line.
Theorem 3.13: Proves that if a self-dual code is placed in an adapted normal form with a specific isotropic last row, the self-duality condition forces the matrix to satisfy the specific "boxed" relations (orthogonality and norm constraints).

C. Formal Verification

The paper provides a complete formalization of the algebraic core in Lean 4.
It separates the self-dual/Lagrangian interface, the hyperbolic split background, and the reconstruction algorithms.
The formalization confirms that the forward construction (building up) and the reverse reconstruction (normalization) are mathematically sound up to split-isometric equivalence.

4. Results and Applications

The authors applied their split boxed construction to generate explicit, optimal self-dual codes over $\text{GF}(5)$ and $\text{GF}(13)$ . These codes meet or approach the theoretical bounds (Singleton, Griesmer).

Over $\text{GF}(5)$ :
- Constructed an optimal self-dual $[6, 3, 4]$ code.
- Constructed an optimal self-dual $[8, 4, 4]$ code (derived from the $[6,3,4]$ parent).
Over $\text{GF}(13)$ :
- Constructed an optimal self-dual $[8, 4, 5]$ code (MDS).
- Constructed an optimal self-dual $[10, 5, 6]$ code.
- Constructed an exact self-dual $[12, 6, 6]$ code.
Optimality: The constructed codes achieve the maximum possible minimum distance for their parameters, proving the efficiency of the split boxed construction in low-dimensional cases.

5. Significance

Unification of Theory: The paper bridges the gap between combinatorial coding theory (Kim's construction) and algebraic topology/number theory (Chinburg-Zhang's cohomology), showing they describe the same underlying geometric reality (Lagrangian reduction in hyperbolic spaces).
Geometric Insight: It provides a precise geometric interpretation of the "correction terms" in code construction, identifying them as components of isotropic lines in hyperbolic planes. This moves the field from heuristic vector selection to structured geometric construction.
Formalization Benchmark: The work sets a new standard for formalizing coding theory. By verifying 256 theorems in Lean, it ensures the algebraic foundations of these constructions are error-free and provides a reusable library for future research in coding theory over bilinear spaces.
Practical Utility: The "split boxed" method offers a systematic, algorithmic way to generate high-quality self-dual codes, which are crucial for quantum error correction and other applications.

In summary, this paper successfully formalizes and unifies the theory of self-dual code construction, revealing the deep geometric structure (isotropic lines in hyperbolic planes) that governs these codes, and validates the results through rigorous computer-assisted proof.