Optimal Representations of Gaussian and Eisenstein Integers using digit sets closed under multiplication
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909334387032064 |
|---|---|
| author | Blažek, Adam Pelantová, Edita Svobodová, Milena |
| author_facet | Blažek, Adam Pelantová, Edita Svobodová, Milena |
| contents | 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 $\mathcal{D} = \{ 0, \pm 1, \pm \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 $\mathcal{D} = \{ 0, \pm 1, \pm ω, \pm ω^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 $\mathcal{D} = \{0, \pm 1\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02418 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Representations of Gaussian and Eisenstein Integers using digit sets closed under multiplication Blažek, Adam Pelantová, Edita Svobodová, Milena Number Theory 11A63, 11R04, 68R05 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 $\mathcal{D} = \{ 0, \pm 1, \pm \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 $\mathcal{D} = \{ 0, \pm 1, \pm ω, \pm ω^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 $\mathcal{D} = \{0, \pm 1\}$. |
| title | Optimal Representations of Gaussian and Eisenstein Integers using digit sets closed under multiplication |
| topic | Number Theory 11A63, 11R04, 68R05 |
| url | https://arxiv.org/abs/2410.02418 |