The Minimal Euclidean Function on the Gaussian Integers

Abstract

In 1949, Motzkin proved that every Euclidean domain $R$ has a minimal Euclidean function, ${\varphi }_R$. He showed that when $R=\mathbb{Z}$, the minimal function is ${\varphi }_{\mathbb{Z}}(x)=\lfloor {\log }_2|x|\rfloor$. For over seventy years, ${\varphi }_{\mathbb{Z}}$ has been the only example of an explictly-computed minimal function in a number field. We give the first explicitly-computed minimal function in a non-trivial number field, ${\varphi }_{\mathbb{Z}[i]}$, which computes the length of the shortest possible $(1+i)$-ary expansion of any Gaussian integer. We also present an algorithm that uses ${\varphi }_{\mathbb{Z}[i]}$ to compute minimal $(1+i)$-ary expansions of Gaussian integers. We solve these problems using only elementary methods.

10 pages, 5 figures