Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

  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!

share|improve this question

4 Answers 4

up vote 6 down vote accepted

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}$.

share|improve this answer
    
Nice argument. It seems to show that the appearance of the particular set of coefficients {+1,-1} is arbitrary; wouldn't it be more natural to state it for any finite set of coefficients? –  t3suji Jan 18 '10 at 15:06
    
Yes, I was just trying to answer the question as stated, but you are right: it does work for any finite set of integers (or even real numbers) as coefficients, and with any scheme for rounding real numbers to integers within O(1). Allowing real numbers as coefficients allows one to treat the Fibonacci case literally as a special case. –  Bjorn Poonen Jan 18 '10 at 20:24

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.

share|improve this answer
    
Thanks, Michael! It seems quite likely this is the paper in question. I think this settles the validity of the claim/proof, and so now my question #2 remains. –  aorq Jan 17 '10 at 2:25
    
I suspect the answer to your question 2 is no; it seems like the number of digits one needs should grow like the logarithm of the number you're trying to represent. –  Michael Lugo Jan 17 '10 at 2:37
    
It's definitely the author I had in mind, but I heard the result stated in a survey talk (speaker to remain unnamed!). –  Kevin O'Bryant Jan 17 '10 at 18:25
    
The original claim allows repeating a Fibonacci number multiple times. Can you still apply this result that way? –  Zsbán Ambrus Mar 13 '11 at 17:57
    
Alpert's theorem was proved earlier by Clemens Heuberger, "Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms", Periodica Mathematica Hungarica 49 (2), 2004, 65–89. –  Ira Gessel 18 hours ago

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.

share|improve this answer
    
I'm sorry, but I don't understand your proof. Where does $log_b(k-1)$ come from? How do you get that $b$ is a root of some limit polynomial? What does it matter if $b$ is a root of a polynomial "of finite degree"? –  aorq Jan 17 '10 at 17:08
    
If $b$ is a root of a polynomial, then you can find polynomials of $b$ of arbitrarily large degree and fixed total coefficient magnitude with small values. For example, suppose you are trying to express the integers up to 10. $\phi^{1000}-\phi^{999}-\phi^{998}+\phi^4 < 10$, and is of high degree. However, it's not a new value. The higher powers are removable, so that you find a lower degree polynomial $\phi^4$ with the same value. It looks like I should clean up the proof of that lemma ("fixed" not "finite"), but you need something like that lemma to use a simple counting argument. –  Douglas Zare Jan 18 '10 at 4:32
    
Thanks for the clarifications. It appears your ideas have inspired Bjorn Poonen to come up with a proof ... –  aorq Jan 18 '10 at 15:49

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.

share|improve this answer
    
In the result in question, you're allowed minus signs, so 610 - 1 is a good representation. –  aorq Jan 17 '10 at 1:49
    
Ach, you're right. –  Zev Chonoles Jan 17 '10 at 1:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.