×

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.

MSC:

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

Citations:

Zbl 1030.11003
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML

References:

[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. · Zbl 0309.12001
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.