An Elementary Proof of the Minimal Euclidean Function on the Gaussian Integers

Abstract

Every Euclidean domain $R$ has a minimal Euclidean function, ${\varphi }_R$. A companion paper \cite{Graves} introduced a formula to compute ${\varphi }_{\mathbb{Z}[i]}$. It is the first formula for a minimal Euclidean function for the ring of integers of a non-trivial number field. It did so by studying the geometry of the set $B_n=\left\{{\sum }_{j=0}^n{v}_j(1+i{)}^j:v_j\in \{0,\pm 1,\pm i\}\right\}$ and then applied Lenstra's result that ${\varphi }_{\mathbb{Z}[i]}^{-1}([0,n])=B_n$ to provide a short proof of ${\varphi }_{\mathbb{Z}[i]}$. Lenstra's proof requires s substantial algebra background. This paper uses the new geometry of the sets $B_n$ to prove the formula for ${\varphi }_{\mathbb{Z}[i]}$ without using Lenstra's result. The new geometric method lets us prove Lenstra's theorem using only elementary methods. We then apply the new formula to answer Pierre Samuel's open question: what is the size of ${\varphi }_{\mathbb{Z}[i]}^{-1}(n)$?. Appendices provide a table of answers and the associated SAGE code.

29 pages, 3 figures, 1 table, 1 appendix with code