Minimal redundant digit expansions in the Gaussian integers (Q558126)

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.