nt.number theory - Representing numbers in a non-integer base with few (but possibly negative) nonzero digits

Background

In a recent question about Fibonacci numbers, it was claimed that

every integer can be written in the form $sum_{i=1}^6 epsilon_i F_{n_i}$ with $epsilon_i in {0,-1,1}$. The upper limit on the summation isn't a typo: every number is the sum/difference of at most 6 fibonacci's.

I believe this is false, even for larger (but still finite) values of $6$:

First of all, without loss of generality, we may assume that the representations do not repeat any Fibonacci number (i.e., the $n_i$s are distinct) and moreover, do not contain any two consecutive Fibonacci numbers (i.e., $n_i ne n_j+1$). We may arrive at such a representation by using the following simplifications repeatedly:

• If two consecutive Fibonacci numbers appear with opposite signs, simplify the expansion with the identity $F_n - F_{n-1} = F_{n-2}$.


• If two consecutive Fibonacci numbers appear with the same sign, simplify the expansion with the identity $F_n + F_{n-1} = F_{n+1}$.


• If the same Fibonacci number appears with opposite signs, simply cancel the two terms.


• If the same Fibonacci number appears with the same sign, then use the identity $F_n + F_n = F_{n-2} + F_{n-1} + F_n = F_{n-2} + F_{n+1}$ to replace them with two non-identical Fibonacci numbers.

The first three operations reduce the number of terms in the expansion and thus strictly simplify the expression (in terms of how many terms there are), but the last may need to be used several times before it "simplifies" the expression (for example, in terms of how many repeated terms there are). Nonetheless, this simplification procedure terminates, as it is impossible to get stuck in an infinite loop using the last operation alone. (Proof: we may assume that the $n_i$ are positive. Then all of the operations either reduce the number of terms, or leaves that unchanged and reduces the sum of the $n_i$.)

Now, assume we have such a representation (no identical terms, no consecutive terms) and suppose the largest Fibonacci number appearing is $F_n$. Then the next largest term (in absolute value) that may appear is $F_{n-2}$, the next largest after that $F_{n-4}$, and so on. All in all, the sum of the terms excluding $F_n$ is at most $F_{n-2} + F_{n-4} + cdots le F_{n-1}$ (proof by induction: add $F_n$ to both sides). By the triangle inequality, the sum of all the terms must be at least $F_n - F_{n-1} = F_{n-2}$. The point of this calculation is that if you want to represent a number that's less than $F_{n-2}$, you can't use terms that are $F_n$ or greater.

This leads us to our contradiction. Consider the integers between $0$ and $F_{n-2}-1$. How many possible representations are there of numbers in this range? Well, we have six terms all of which are 0 or $pm F_k$ for $klt n$ (from the above discussion), so we have at most $(2n+1)^6$ representations that could possibly fall into the range. (We're over-counting here because it won't matter and this is easier.) However, there are clearly $F_{n-2}$ different integers in the given range. Assume for contradiction that it were always possible to represent numbers as the sum/difference of at most 6 Fibonacci's. Then we would have

$$ (2n+1)^6 ge F_{n-2}. $$

Finally, because the left side grows polynomially while the right side grows exponentially, a large enough value of $n$ will produce a contradiction.

My questions

1. Is the proof above correct? (If not, and the original claim is correct, can you give me a representation of the number 5473?) Edit: Please see Michael Lugo's answer for a paper which finds the representation with the fewest nonzero digits in this "signed Fibonacci base". Please consider the following the actual question here:




2. Assuming the proof is correct, is the original claim true for other non-integer bases? What I mean is the following:

Does there exist a natural number $k$ and a real number $b>1$ such that every integer has a representation as $sum_{i=1}^k epsilon_i lfloor b^{n_i} + frac12 rfloor$? That is, does every number have a representation in "base $b$" (because $b$ is probably irrational, we round $b^n$ to the nearest integer) with at most $k$ non-zero "digits", but where the "digits" may be $pm 1$?

Note that the original claim is an instance of this: $k=6$ and $b=varphi = frac{1+sqrt 5}{2}$.

I don't think my proof works directly because I used special properties of $varphi$/the Fibonacci numbers. Is it possible to remove this reliance? In particular, the second step of the proof shows that it's not "useful" to have large Fibonacci numbers in the representation of a small number. Is the same true for every base $b$?

Note: if the digits were not allowed be negative, then my proof would go through. The main issue is whether or not $pm b^n$ for large $n$ can cancel and produce small numbers.

Thanks!