On minimal expansions in redundant number systems: Algorithms and quantitative analysis (Q5945716)

The authors consider digital expansions \(n = \sum_{i=0}^l \varepsilon_i q^i\) in base \(q\geq 2\) with arbitrary integer digits \(\varepsilon_i\) and call it minimal if the valuation \(l+1 + \sum |\varepsilon_i|\) is minimal. (Minimal representations are not unique in general. However, by assuming some natural regularity assumptions one gets a reduced minimal expansion.) First it is shown that there is an easy algorithm that computes this (reduced) minimal expanision and that works almost in the same way as the usual greedy algorithm. A similar approach applies for so-called relaxed minimal expansions, where it is assumed that the valuation \(\sum |\varepsilon_i|\) is minimal. In both cases the digits in the minimal representation satisfy \(|\varepsilon_i|\leq q/2\). Next they prove an explicit formula for \(\varepsilon_i\) of the reduced minimal expansion in terms of \(n/q^i\). For example, the \(r\)-th digit in the relaxed minimal expanions for \(q=2\) is given by \[ \varepsilon_r = \left\lfloor \frac n{2^{r+2}} + \frac 56 \right\rfloor - \left\lfloor \frac n{2^{r+2}} + \frac 46 \right\rfloor -\left\lfloor \frac n{2^{r+2}} + \frac 26 \right\rfloor + \left\lfloor \frac n{2^{r+2}} + \frac 16 \right\rfloor. \] Finally the asymptotic frequencies of the digits are evaluated. It is remarkable that for even \(q\) they are not uniformly distributed. In this case \(0\) has frequency \((q+2)/(q(q+1))\), \(\pm 1,\pm 2, \ldots,\pm (q/2-1)\) have frequency \(1/q\), and \(\pm q/2\) have frequency \(1/(2(q+1))\).