2024/10/03 by Blažek, Adam, Pelantová, Edita, Svobodová, Milena
#11A63 #11R04 #68R05 #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.2410.02418
We study two positional numeration systems which are known for allowing very efficient addition and multiplication of complex numbers. The first one uses the base β= \imath - 1 and the digit set D = \ 0, ± 1, ± \imath \. In this numeration system, every non-zero Gaussian integer~x has an infinite number of representations. We focus on optimal representations of~x -- i.e., representations with minimal possible number of non-zero digits. One of the optimal representations of~x has the so-called 3-non-adjacent form (3-NAF). We provide an upper bound on the number of distinct optimal representations of~x, depending on the number of non-zero digits in the 3-NAF of~x. We also characterize the Gaussian integers for which the upper bound is attained. The same questions are answered also for the second numeration system with base β= ω- 1 and digit set D = \ 0, ± 1, ± ω, ± ω2 \, where ω= exp(2π\imath / 3). In this system, every Eisenstein integer has a 2-NAF, which is optimal. This paper can be understood as an analogy to the result of Grabner and Heuberger obtained for the signed binary numeration system, using base β= 2 and digit set D = \0, ± 1\.