Minimal redundant digit expansions in the Gaussian integers. (English) Zbl 1076.11005

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).
C. Heuberger and 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.


11A63 Radix representation; digital problems
11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.


Zbl 1030.11003
Full Text: DOI Numdam EuDML


[1] Heuberger, C., Prodinger, H., On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing66 (2001), 377-393. · Zbl 1030.11003
[2] Kátai, I., Szabó, J., Canonical number systems for complex integers. Acta Sci. Math. (Szeged) 37 (1975), 255-260.
[3] Knuth, D.E., Seminumerical algorithms, third ed. The Art of Computer Programming, vol. 2, Addison-Wesley, 1998. · Zbl 0895.65001
[4] Kovács, B., Pethö, A., Number systems in integral domains, especially in orders of algebraic number fields. Acta Sci. Math.(Szeged) 55 (1991), 287-299. · Zbl 0760.11002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.