Representing numbers in a non-integer base with few (but possibly negative) nonzero digits - MathOverflow

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

2010-01-17T00:48:30Z

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 $k\lt 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

~~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:
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!

Answer by Zev Chonoles for Representing numbers in a non-integer base with few (but possibly negative) nonzero digits

2010-01-17T01:36:04Z

Your proof looks right to me. As a smaller example, a number with a Zeckendorf representation with 7 terms is 609 = 377 + 144 + 55 + 21 + 8 + 3 + 1 (note that 609 = 610 - 1); I believe it is impossible to represent 609 as a sum of Fibonacci numbers as described in the result being challenged.

I haven't tried out your analysis on other bases yet.

Answer by Michael Lugo for Representing numbers in a non-integer base with few (but possibly negative) nonzero digits

2010-01-17T02:12:46Z

In a recent paper in Integers, Hannah Alpert proves that "every integer can be written uniquely as a sum of Fibonacci numbers and their additive inverses, such that every two terms of the same sign differ in index by at least 4 and every two terms of different sign differ in index by at least 3. Furthermore, there is no way to use fewer terms to write a number as a sum of Fibonacci numbers and their additive inverses." Alpert was at the Duluth REU mentioned by Kevin O'Bryant in his comment; I suspect this is the paper referred to and the result was at some point miscommunicated.

The procedure Alpert gives for finding such a representaiton gives, for example, 5473 = 6765 - 1597 + 377 - 89 + 21 - 5 + 1. I think 5473 is the smallest number which needs seven terms.

Answer by Douglas Zare for Representing numbers in a non-integer base with few (but possibly negative) nonzero digits

2010-01-17T13:42:48Z

The key idea in your proof works for other bases as well, and other numbers of digits.

Lemma: There is a bound based on $k$ and $b$ for the greatest power of $b$ which could be necessary in a representation of a real number with magnitude under $1$ as a polynomial in $b$, the magnitudes of whose coefficients add up to at most $k$.

Proof: Edit: My first proof attempt was flawed. I wanted to avoid induction in $k$. I'll try to fix this later.

Let this bound be $p(b,k)$. When you count the sums of powers of $b$ which could be used to represent a number up to $n$, you only need to consider powers of $b$ up to $\log_b(n+k) + p(b,k)$. So you get at most $(1+2 log_b(n+p))^k$ representable numbers out of $n$, and for large $n$, some numbers can't be represented.

Answer by Bjorn Poonen for Representing numbers in a non-integer base with few (but possibly negative) nonzero digits

2010-01-18T08:08:44Z

This is an answer to your "actual question" (2), building on some of the ideas in Douglas Zare's answer.

Lemma 1: Suppose that $0 < r < 1$. Let $S=\lbrace \epsilon r^i : \epsilon = \pm 1 \text{ and } i \in \mathbb{Z}_{\ge 0} \rbrace$. Fix $k \ge 1$. Let $S_k$ be the set of sums of the form $s_1+\cdots+s_k$ such that $s_i \in S$ and $|s_1|=1$ and there is no nonempty subset $I \subset \lbrace 1,\ldots,k \rbrace$ with $\sum_{i \in I} s_i = 0$. Then $0$ is not in the closure of $S_k$.

Proof: Use induction on $k$. The base case is trivial: $S_1=\lbrace -1,1\rbrace$. Now suppose $k \ge 2$. If a sequence $(x_i)$ in $S_k$ converges to $0$, then the smallest summand in the sum giving $x_i$ must tend to $0$, since a lower bound on the absolute values of the summands rules out all but finitely many elements of $S_k$, which are all nonzero. Discarding the finitely many $x_i$ for which the smallest summand is $\pm 1$ and removing the smallest summand from each remaining $x_i$ yields a sequence $(y_i)$ in $S_{k-1}$ tending to $0$, contradicting the inductive hypothesis.

Now fix $b>1$ and $k$. Let $T=\lbrace \epsilon \lfloor b^n + 1/2 \rfloor : \epsilon = \pm 1 \text{ and } n \in \mathbb{Z}_{\ge 0} \rbrace$. Let $T_k$ be the set of sums of the form $t_1+\cdots+t_k$ with $t_i \in T$.

Lemma 2: Each $t=t_1+\cdots+t_k \in T_k$ equals $u_1+\cdots+u_\ell+\delta$ for some $\ell \le k$ and some $u_i \in T$ with $u_i = O(t)$ and $\delta = O(1)$.

Proof: Examine the powers of $b$ used in the $t_i$. If any nonempty subsum (with signs) of these powers equals $0$, the corresponding $t_i$ sum to $O(1)$. If $b^n$ is the largest power that remains after removing all such subsums, divide all the remaining $t_i$ by $b^n$, and apply Lemma 1 with $r=1/b$ to see that $|t|/b^n$ is bounded away from $0$, so all these remaining $t_i$, which are $O(b^n)$, are $O(t)$.

Corollary: The number of elements of $T_k$ of absolute value less than $B$ is $O((\log B)^k)$ as $B \to \infty$.

Corollary: $T_k \ne \mathbb{Z}$.