🔢 mathematics

Euclidean Rings

This paper presents the 1989 diploma thesis on Euclidean Rings, which generalizes Lenstra's concept of exceptional sequences to k-stage Euclidean rings.

Original authors: Franz Lemmermeyer

Published 2026-08-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Franz Lemmermeyer

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

In the vast landscape of mathematics, there is a fundamental question that has puzzled scholars for centuries: how do we divide numbers when we are working with complex systems that go far beyond the simple counting numbers we use every day? In our daily lives, we rely on the Euclidean algorithm, a step-by-step method for finding the greatest common divisor of two numbers. This process works because the integers have a special property: no matter which two numbers you pick, you can always find a "remainder" that is smaller than the divisor, allowing the division to eventually stop. Mathematicians call rings of numbers that possess this property "Euclidean rings." For over a thousand years, it was known that the standard integers and a few specific extensions of them, like the Gaussian integers, behave this way. However, as mathematicians began exploring more intricate number systems—fields created by adding roots of equations to the rational numbers—it became unclear which of these exotic systems also allowed for this clean, terminating division. The question was not just about division; it was about the very structure of these number worlds. If a system is Euclidean, it behaves with a predictable order that makes solving equations and understanding prime factors much easier. If it is not, the path to a solution can become chaotic and infinite.

In 1989, Franz Lemmermeyer, then a young researcher, tackled this problem in a comprehensive study that sought to map out exactly which of these complex number fields are Euclidean and which are not. His work was not merely a list of answers but a development of new tools to test these systems. He focused on a specific measure called the "Euclidean minimum," which acts like a threshold. Imagine trying to find a spot on a map that is close enough to a town to be considered "nearby." In these number fields, the Euclidean minimum tells us the maximum distance any point in the system can be from a whole number. If this distance is small enough, the system is Euclidean; if it is too large, the division process fails to terminate. Lemmermeyer's thesis combined rigorous mathematical proofs with the power of early computer programs to calculate these distances for hundreds of different number fields, ranging from simple quadratic systems to complex cubic and quartic ones.

The core of his investigation involved testing specific families of number fields to see if they met the strict criteria for being Euclidean. He developed and refined criteria that could rule out the possibility of a Euclidean algorithm in certain fields without having to check every single number. For instance, he showed that if a number field contains certain types of prime numbers that behave in a specific way, the field cannot be Euclidean. This allowed him to eliminate vast categories of candidates quickly. He then turned his attention to the fields that remained, using computer algorithms to calculate their Euclidean minima with high precision. These programs divided the mathematical space into tiny regions, checking every point to see if a "nearby" whole number existed. If a region could not be covered, it contained an "exceptional point" where the division would fail. By tracking how these exceptional points behaved under the influence of the field's fundamental units (the building blocks of the system's structure), he could pinpoint exactly where the failures occurred.

One of the most significant achievements of this work was an almost complete classification of Euclidean real quadratic fields. These are number systems formed by adding the square root of a positive integer to the rational numbers. Lemmermeyer provided a near-complete list of these fields, identifying specific discriminants that remained open, thereby settling the majority of the debate while highlighting the few remaining cases. He also made substantial progress on cubic fields, which involve cube roots. He proved that there are no cyclic cubic fields with a specific range of discriminants (a value that measures the complexity of the field) that are Euclidean, effectively narrowing the search for such fields to a much smaller set. For fields of degree four, which are even more complex, he determined all the Euclidean examples within certain families, including those known as Dirichlet fields and bicyclic biquadratic fields. His work revealed that while Euclidean fields exist in higher degrees, they are rare and tightly constrained, though many specific examples in degrees three and four remained to be fully resolved.

The study also addressed the concept of "k-stage" Euclidean rings, a variation where the division process is allowed to take a few more steps before terminating. Lemmermeyer adapted his criteria to detect these slightly more flexible systems, finding examples in degrees two, three, four, and five. This was important because it showed that even if a field is not strictly Euclidean in the traditional sense, it might still possess a structured, predictable division process if one allows for a few extra steps. However, he also demonstrated that for many fields, even this relaxed condition does not hold. He provided concrete examples of fields where the Euclidean minimum is exactly one, yet the system fails to be Euclidean, highlighting the subtle and often counterintuitive nature of these mathematical structures.

Throughout the thesis, Lemmermeyer emphasized the interplay between theoretical proof and computational verification. While the mathematical criteria provided the framework, the computer programs were essential for handling the sheer volume of calculations required to test the boundaries of these fields. He described the algorithms used to navigate the high-dimensional spaces of these number fields, noting that the process was akin to mapping a terrain where the "height" of the land represented the difficulty of division. The results were presented in detailed tables, listing the Euclidean minima for fields with discriminants up to very large numbers. These tables serve as a reference for future mathematicians, showing exactly which fields have been solved and which remain open questions.

The work concluded with a collection of open questions, pointing the way for future research. Lemmermeyer identified specific fields where the answer was still unknown, particularly in higher degrees and more complex Galois groups, as well as several unresolved cases within degrees two, three, and four. He noted that while his methods could solve many of these, some problems seemed to require deeper insights or new mathematical tools. He also highlighted the connection between Euclidean fields and the distribution of prime numbers, suggesting that the existence of Euclidean algorithms is deeply tied to the fundamental architecture of number theory. By the end of the thesis, the landscape of Euclidean rings was far clearer than it had been before, though the mystery of which number fields allow for clean division was not entirely resolved, leaving a clear path forward for the more complex cases. The study stood as a testament to the power of combining classical mathematical reasoning with the emerging capabilities of computer science to solve problems that were once thought to be intractable.

Technical Summary: Euclidean Rings (Diploma Thesis, 1989)

Problem Statement
The central problem addressed in this work is the determination of which algebraic number fields $K$ possess a Euclidean algorithm with respect to the absolute norm (norm-Euclidean fields). While the Euclidean property implies that the ring of integers $\mathcal{O}_K$ is a Principal Ideal Domain (PID), the converse is not generally true (e.g., $\mathbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a PID but not Euclidean). The thesis seeks to classify norm-Euclidean fields across various degrees and signatures, determine their Euclidean minima $M(K)$ , and investigate the existence of $k$ -stage Euclidean algorithms (where the division chain terminates within $k$ steps). A specific focus is placed on fields where classical criteria fail, particularly those lacking totally ramified prime ideals or possessing high unit ranks.

Methodology
The work employs a combination of theoretical criteria and computational algorithms to establish bounds on the Euclidean minimum $M(K) = \sup_{x \in K} \inf_{y \in \mathcal{O}_K} |N_{K/\mathbb{Q}}(x-y)|$ .

Criteria for Non-Euclideanity:
- Totally Ramified Ideals: The author adapts and generalizes criteria by Lenstra, Cooke, and van der Linden. Specifically, criterion (1.4) is extended to intermediate fields $K$ where $L/K$ possesses totally ramified ideals, even if $L/\mathbb{Q}$ does not. This involves analyzing residue classes modulo products of ramified prime ideals to show that no element of sufficiently small norm exists in certain residue classes.
- Geometric Methods: Utilizing the "Gaussian General Measure" $M_K(x)$ (related to the sum of squares of embeddings), the work applies Lenstra's packing arguments. This involves constructing "exceptional sequences" (sequences of elements whose differences are units) to prove the existence of Euclidean algorithms (Criterion 1.15) and deriving upper bounds for $M(K)$ .
Determination of Euclidean Minima:
- Covering Algorithms: For specific fields, the author implements a method (originating with Barnes and Swinnerton-Dyer) to cover the fundamental domain of the lattice $\mathcal{O}_K$ with regions where the norm condition $|N(x-y)| < k$ is satisfied.
- Exceptional Points: The algorithm identifies "exceptional points" (points not covered by the standard residue system) and uses the action of the unit group to map these points into smaller regions. By analyzing the fixed points of unit transformations (e.g., $z = a/(u-1)$ ), the author isolates the exact location of the Euclidean minimum.
- k-Stage Analysis: The concept of $k$ -stage Euclidean rings is introduced, utilizing continued fractions of length $k$ and sets $E_k$ (generalizing Motzkin's sets) to determine if a field admits a Euclidean algorithm of bounded length.
Computational Implementation:
- Section 11 describes a recursive algorithm that subdivides the fundamental domain into hypercubes. It checks if every point in a sub-cube can be approximated by an algebraic integer within a target norm $k$ . If not, the cube is subdivided further or marked as an "exceptional set." The algorithm iteratively applies unit transformations to reduce these exceptional sets until the minimum is isolated or a contradiction is found.

Key Contributions and Results

Generalization of Criteria: The thesis provides a significant generalization of Lenstra's and van der Linden's criteria. It demonstrates that the existence of totally ramified ideals in an intermediate extension $L/K$ is sufficient to apply non-Euclidean criteria, thereby expanding the class of fields that can be ruled out as norm-Euclidean.
Classification of Specific Fields:
- Quadratic Fields: An almost complete classification of norm-Euclidean real quadratic fields is provided, confirming the list of $m$ for which $\mathbb{Q}(\sqrt{m})$ is Euclidean.
- Cubic Fields: The work determines all norm-Euclidean fields of the form $\mathbb{Q}(\sqrt[3]{m})$ and improves bounds on the discriminant for cyclic cubic fields, showing no such fields exist in the range $1572 \le d \le 2.5 \cdot 10^{11}$ .
- Bicyclic Biquadratic Fields: All norm-Euclidean imaginary bicyclic biquadratic fields are determined. Combined with van der Linden's results on cyclic fields, this completes the classification of all Galois complex quartic fields admitting a Euclidean algorithm.
- Dirichlet Fields: A partial classification of norm-Euclidean Dirichlet fields (quadratic extensions of $\mathbb{Q}(i)$ ) is presented, specifically those where the relative discriminant is divisible by $(1+i)$ .
Euclidean Minima: Precise values for $M(K)$ are computed for numerous fields, including $\mathbb{Q}(\sqrt{14})$ where $M(K) = 5/4$ , and $\mathbb{Q}(\sqrt{13})$ where the minimum is $1/3$ but not attained. The distinction between isolated and non-isolated minima is explored, with examples like $\mathbb{Q}(\sqrt{23})$ cited where the second minimum is not isolated.
k-Stage Euclidean Rings: The thesis identifies fields that are $k$ -stage Euclidean but not 1-stage (norm-Euclidean), such as certain real quadratic fields with $m=15, 26, 85$ .

Significance and Scope
The author positions this work as a comprehensive survey and computational extension of the state of the art in the late 1980s. The thesis serves as the foundation for the author's later survey article, The Euclidean algorithm in algebraic number fields.

The significance lies in:

Unification: Bringing together disparate criteria (arithmetical and geometric) into a coherent framework for testing Euclideanity.
Completeness: Providing definitive lists for specific classes of fields (e.g., imaginary bicyclic biquadratic fields) that were previously open.
Algorithmic Approach: Formalizing a computational method to determine Euclidean minima, moving beyond theoretical bounds to exact values for specific cases.

The author explicitly notes that many questions remain open, particularly for fields of higher degree and those with dihedral Galois groups. The work acknowledges that while the developed methods solve many specific cases, a general classification for arbitrary degrees remains elusive, and some open questions may require deeper theoretical insights beyond the scope of the thesis. The text also includes a German version of the thesis and a list of fields whose norm-Euclidean character was resolved by this work.

More like this