The Counted Address

The Euclidean algorithm works on the integers because you can always divide and get a remainder smaller than the divisor. In a Euclidean domain, a Euclidean function φ assigns a “size” to each element, and the algorithm terminates because remainders shrink. But Euclidean functions aren’t unique — many different functions can make the same ring Euclidean. The minimal Euclidean function assigns the smallest possible size to each element.

For the ordinary integers, the minimal Euclidean function is the absolute value. For the Gaussian integers ℤ[i], finding the minimal Euclidean function was an open problem until 2023, when Reroup presented the first computable version. Now (arXiv:2603.13225), formulas follow for the pre-image sizes: how many Gaussian integers map to each value.

The geometric construction is the key. The Gaussian integers tile the complex plane in a square lattice, and the Euclidean function measures how “reachable” each element is via the division algorithm. Elements near the origin are reached quickly (small φ values). Elements further out require more steps. The pre-image formula counts how many lattice points sit at each “distance” in this algorithmic metric.

The result reveals the shape of the Euclidean algorithm in two dimensions. For ordinary integers, the pre-image of φ = n is just {±n} — two elements per level. For Gaussian integers, the pre-images grow in a pattern dictated by the geometry of the square lattice and the number theory of which directions allow efficient division. The count at each level encodes both the lattice symmetry and the arithmetic of ℤ[i].

Computing a minimal Euclidean function is one thing. Describing its level sets — who lives at each algorithmic distance from zero — turns computation into cartography.