On linear combinations of units with bounded coefficients and double-base digit expansions (Q368536)

Let \(F\) be a subfield of the complex numbers, \(\Gamma\) a finitely generated subgroup of \(F^*\), and \(R\) a subring of \(F\), generated as a \(\mathbb Z\)-module by a finite set of elements of \(\Gamma\). The authors show that if for given \(n\geq I\geq2\) the equation \[ \sum_{j=1}^I u_j = n \] has a solution with \(u_j\in \Gamma\cap R\), not all equal to \(1\), then every element \(\alpha\) of \(R\) can be written as a linear combination of elements of \(\Gamma\cap R\) with non-negative integral coefficients, the maximal coefficient bounded by \(n-1\). This generalizes an old result of \textit{P. Belcher} [J. Lond. Math. Soc., II. Ser. 12, 141--148 (1976; Zbl 0321.12013)] who established this assertion in the case \(n=2\) for rings of integers of algebraic number fields. In [Proc. Camb. Philos. Soc. 55, 370--373 (1959; Zbl 0093.05003)], \textit{B. J. Birch} proved that if \(p,q\) are co-prime integers then every sufficiently large integer is a sum of distinct numbers \(p^iq^j\) with \(i,j\geq0\), hence every integer can be written in the form \[ \sum_{i,j\geq0}d_{ij}p^iq^j \] with \(d_{ij}\in\{0,\pm1\}\). The authors apply their result to provide a polynomial time algorithm to find such a representation in the case when \(|p|,|q|\geq3\) and the equation \[ \left|p^x-q^y\right|=2 \] is solvable.