Minimal redundant digit expansions in the Gaussian integers
type: Item
instance of: scholarly article
title: Minimal redundant digit expansions in the Gaussian integers
zbMATH Open document ID: 1076.11005
author: Clemens Heuberger
published in: Journal de Théorie des Nombres de Bordeaux
publication date: 2005-06-30T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/93861
review text: Let \(q\geq 2\) be an integer. There are infinitely many ways to represent a given integer \(n\in {\mathbb N}\) in the form \[ n=\sum_{j=0}^l \varepsilon_j q^j,\quad l \in {\mathbb N},\;\varepsilon_j\in {\mathbb Z}. \] In cryptography, it is sometimes interesting to find a representation with a minimal `cost' (that is, such that \(\sum_{j=0}^l| \varepsilon_j| \) is minimal). \textit{C. Heuberger} and \textit{H. Prodinger} [Computing 66, No. 4, 377--393 (2001; Zbl 1030.11003)] have shown that knowing the digits \(\eta_0,\eta_1\) of the usual \(q\)-ary expansion \(n=\sum_{j=0}^L \eta_jq^j\) (\(0\leq \eta_j<q\)) is enough to decide what digit \(\varepsilon_0\) should be taken to obtain such a minimal representation of \(n\). This provides an easy algorithm to produce a representation of minimal cost for a given integer \(n\). In the paper under review, the corresponding problem is investigated for so-called canonical number systems in the ring of Gaussian integers. The main result shows that the situation becomes very different. Indeed, given an arbitrary positive integer \(L\), the author constructs two Gaussian integers \(\alpha,\alpha'\) with the following properties: The `usual' representations of \(\alpha\) and \(\alpha'\) coincide in the first \(L\) digits, while for all pairs of strings \((\varepsilon_0,\dots \varepsilon_s)\) and \((\varepsilon'_0,\dots \varepsilon'_{s'})\) corresponding to minimal cost representations of \(\alpha\) and \(\alpha'\), respectively, we have \(\varepsilon_0 \not=\varepsilon'_0\). This proves that there is no algorithm, in the vein of the one mentioned above, for finding the minimal representation for canonical number systems in Gaussian integers.
reviewed by: Boris Adamczewski
Mathematics Subject Classification ID: 11A63
Mathematics Subject Classification ID: 11K16
zbMATH DE Number: 2184597
zbMATH Keywords: minimal redundant expansions
zbMATH Keywords: Gaussian integers
MaRDI profile type: Publication
OpenAlex ID: W2023253239
cites work: On minimal expansions in redundant number systems: Algorithms and quantitative analysis
cites work: Q4349924
cites work: Q4021419
DOI: 10.5802/JTNB.372
Recommended article: Q3836757
Recommended article: On minimal expansions in redundant number systems: Algorithms and quantitative analysis
Recommended article: Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms
Recommended article: Minimal expansions in redundant number systems and shortest paths in graphs
Recommended article: On Redundant τ-Adic Expansions and Non-adjacent Digit Sets
Recommended article: Q4246553
Recommended article: A NEW DP-MINIMAL EXPANSION OF THE INTEGERS
Recommended article: On symmetric radix representation of Gaussian integers
Recommended article: The sum of digits of Gaussian primes
Recommended article: On the distribution of digits in dyadic expansions
description: scientific article; zbMATH DE number 2184597