Constructing the interval [0, 1) via inverse powers of 2

If $$x$$ is rational and in the interval $${[0,1)}$$, is it always possible to find constants $$a_1, a_2, ..., a_n\in\{-1, 0, 1\}$$ such that for some integer $$n\geq{1}$$, $$x = a_1\cdot2^{-1} + a_2\cdot{2^{-2}} + \cdots + a_n\cdot{2^{-n}}$$?

This question is purely out of curiosity. When I see something like this, could I think about "base $$1/2$$" (not really sure to write it out like I would binary though) or does the $$-1$$ option for a constant pose an issue? I also thought about how you can make any positive integer via a sum of powers of $$2$$ (because binary), could I use that insight to the above problem?

Additionally, would changing the above condition to $$a_1, a_2, ..., a_n\in\{0, 1\}$$ change the answer?

I was not sure if this was more of a linear algebra question thinking about the span of an infinite basis I sort of have or if this is more of a real analysis question considering the density of the rationals. Thank you for your insight.

• This is a known problem, because this is how IEEE754 represents these numbers. 1/3 is famously not representable exactly using floats, no matter the precision. Commented Jul 16 at 12:56
• @Themoonisacheese, this is closely related to IEEE754 representation, but not quite the same, because the question does not arbitrarily limit the length of the representation. It is equivalent to asking whether every rational in [0, 1) has a terminating binary representation. For any arbitrary IEEE754-style binary format, there are rationals that do have terminating binary representations, but still cannot be expressed exactly in the chosen format because it does not provide enough significant digits. Commented Jul 16 at 14:53
• There may be more than one way to do it. For example $\frac38= 1\cdot 2^{-1}+0\cdot 2^{-2}-1\cdot 2^{-3} = 0\cdot 2^{-1}+1\cdot 2^{-2}+1\cdot 2^{-3}$ Commented Jul 17 at 22:53
• I think, you will get a subset of dyadic rationals with this construction. en.wikipedia.org/wiki/Dyadic_rational Commented Jul 20 at 15:48

All the other answers are very instructive but I'm surprised that none of them provides an actual counter-example, although it is very easy to find one.

Assume that $$\frac{1}{3} = \sum_{k=1}^{n} \frac{a_k}{2^k},$$ where $$\{a_k\}$$ are whichever integers you want. Then $$2^n = 3\sum_{k=1}^{n} a_k2^{n-k}.$$ Note that $$\sum_{k=1}^{n} a_k2^{n-k}$$ is an integer. Therefore, $$3$$ must divide $$2^n$$, which is a contradiction.

• My answer explained all counterexamples, but yes, one suffices to answer their specific question. Commented Jul 16 at 15:17
• @JoshuaTilley I agree that my answer is implicitly included in yours. However, I believe that showing one explicit and simple counter-example is more persuasive than saying that who they are without a proof. Commented Jul 16 at 15:30

No it is not possible to write all rationals from $$[0,1)$$ in this way. The fractions you can write this way are of the form $$m/2^n$$ for $$m,n\ge 0$$ with $$m<2^n$$. Any fraction with denominator divisible by an odd prime whose numerator is not divisible by this prime is not expressible in this form. These are sometimes called dyadic rationals. It does not matter whether you use $$\{1,0\}$$ or $$\{0,1,-1\}$$.

• Follow-up question for @Garrett to think about: what happens if we allow $n \to \infty$, i.e., what numbers are the infinite sum of inverse powers of $2$ where the powers are some possibly infinite subset $J \subset \mathbb{Z}$. Commented Jul 16 at 3:27
• @DerekAllums Since Garrett has not posted a comment, following this answer, Garrett is not registered to this answer. This implies that Garrett will not be flagged by your <at>Garret comment. An easy remedy is for you to post a comment, directly following the posted question, that reads something like: To the Original Poster : See also the comment that I left, following the answer of Joshua Tilley. Commented Jul 16 at 4:24
• @Joshua Tilley thank you, makes sense. So the general form is $x = \displaystyle\frac{a_1\cdot{2^{n-1}} \pm a_2\cdot{2^{n-2}} \pm \cdots \pm a_n}{2^n}$, where the numerator can be at most $2^n - 1$ and there's no way to get an odd prime in the denominator. If I changed the linear combination to all inverse powers of primes, then I guess that'd work? Is there something "smaller" that would generate all of $[0, 1)$ ? Commented Jul 16 at 4:28
• Can you make that more precise? Commented Jul 16 at 4:29
• As in Derek Allum's suggestion, you can get any rational (any real in fact) using only powers of $2$ if you use infinitely many terms (or powers of any fixed $b>1$). Commented Jul 16 at 15:47

Basically, you are asking to write a rational number between zero and one in base $$2$$ notation, but in a finite way. Would that be possible?

Well, let's see what happens in base $$10$$ notation:

$$\frac{1}{2} = 0.5$$ => ok, that's finite.
$$\frac{1}{125} = 0.008$$ => ok, that's finite too.
$$\frac{1}{3} = 0.333...$$ => nok, that's not finite.

The difference is in the prime number factorisation of the denominator: if it contains any prime number different than $$2$$ or $$5$$, the notation in base $$10$$ (which is in fact $$2 \times 5$$) becomes infinite.

Imagine we would use, not only the digits $$0$$ up to $$9$$ but we also allow the usage of negative digits $$-1$$ up to $$-9$$, would that make any difference?
Well, as every negative digit $$-x$$ can be written as $$(10-x) - 10$$ where $$10-x$$ is a positive digit, you can easily see this makes no difference.

So, writing rational numbers in a finite way, the way to proposed, will only be possible if the denominator only counts one prime number, being $$2$$.

You made an interesting query in the comments: $$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$$

I was thinking of something like $$x = \lfrac{a_1}{2}+\lfrac{b_1}{3}+\lfrac{c_1}{5}+\cdots+\lfrac{a_n}{2^n}+\lfrac{b_n}{3^n}+\lfrac{c_n}{5^n}+\cdots$$. But I guess it's kind of a different question because it's now an infinite sum, which defeats the purpose of going up to some finite $$n$$

But a linear combination is finite, and you can indeed get every rational as a sum of integer linear combinations of reciprocals of prime powers! It is not completely trivial.

For example, $$\lfrac1{60} = \lfrac{-1}{2^2}+\lfrac23-\lfrac25$$. How did I get this? I simply found $$a,b,c∈ℤ$$ such that $$15a+20b+12c = 1$$.

In general, this is always possible, and here is a proof sketch. Suppose you want rational $$\lfrac{p}{q}$$. Then you need all the prime powers in the prime factorization of $$q = \prod_{i=1}^n {p_i}^{k_i}$$. You would then need to find integers $$(a_i)_{i=1}^n$$ to the equation $$p = \sum_{i=1}^n a_i\lfrac{q}{{p_i}^{k_i}}$$. We can do this one prime power at a time. Take modulo $${p_n}^{k_n}$$ to get $$p ≡ a_n \lfrac{q}{{p_n}^{k_n}} \pmod{{p_n}^{k_n}}$$. Since $$\lfrac{q}{{p_n}^{k_n}}$$ is coprime to $${p_n}^{k_n}$$, it has a multiplicative inverse mod $${p_n}^{k_n}$$, so we can find $$a_n ≡ p \big( \lfrac{q}{{p_n}^{k_n}} \big)^{-1} \pmod{{p_n}^{k_n}}$$. Then we have $$p - a_n \lfrac{q}{{p_n}^{k_n}} = \sum_{i=1}^{n-1} a_i\lfrac{q}{{p_i}^{k_i}}$$, and so we can repeat the process to get $$a_{n-1}$$ and so on.

For example, to get $$\lfrac1{60}$$ we want $$1 = a_1 \lfrac{60}{2^2} + a_2 \lfrac{60}{3} + a_3 \lfrac{60}{5} = 15 a_1 + 20 a_2 + 12 a_3$$. Mod $$5$$, we have $$1 ≡ 12 a_3$$ and so $$a_3 ≡ (12)^{-1} ≡ -2$$. Then we want $$1+2(12) = 15 a_1 + 20 a_2$$. Mod $$3$$, we have $$1 ≡ 20 a_2$$ and so $$a_2 ≡ (20)^{-1} ≡ 2$$. Thus we want $$1+2(12)-2(20) = 15 a_1$$ and we can (as guaranteed by the process) find $$a_1 = -1$$.

• Cool! I wonder if this can be related to the partial fraction expansion for rational functions? e.g. $\frac{1}{X^2 (X+1)(X+3)}$ "with $X=2$" Commented Jul 17 at 10:44
• @preferred_anon: What partial fraction expansion do you get that you think seems to be related? If you do a partial fraction expansion on what you suggested in your comment, you do not get an integer linear combination. Commented Jul 19 at 13:13
• This works great, thank you for this Commented Jul 19 at 16:44
• @Garrett: You are welcome! =) Commented Jul 21 at 5:01

There are already good answers, but just to show that your intuition could be followed to the end. This answer is not completely rigorous and it's certainly more work than just the simple counterexample that was already given, but if you assume things about binary numbers, it's quite straightforward.

This question is purely out of curiosity. When I see something like this, could I think about "base 1/2 " (not really sure to write it out like I would binary though) or does the −1 option for a constant pose an issue? I also thought about how you can make any positive integer via a sum of powers of 2 (because binary), could I use that insight to the above problem?

No need for "base-$$1/2$$", this is just base-$$2$$. Just as in base-$$10$$ you can write $$0.1337$$ which means $$1 \cdot 10^{-1} + 3 \cdot 10^{-2} + 3 \cdot 10^{-3} + 7 \cdot 10^{-4}$$, you can represent some fractions in $$[0,1)$$ as $$\sum_{i=1}^{n} b_i \cdot 2^{-i}$$. For example, $$3/8$$ in binary would be $$0.011$$.

Now you have $$\{-1,0,1\}$$ as the options for $$a_i$$ so it's not directly a binary representation. But you can define \begin{align} b_i &= \begin{cases} 1,\text { if } a_i=1, \\ 0,\text { otherwise} \end{cases} \\ c_i &= \begin{cases} 1,\text { if } a_i=-1 \\ 0,\text { otherwise} \end{cases} \end{align} In other words, $$a_i = b_i - c_i$$ where $$b_i, c_i \in \{0,1\}$$.

Now $$b=\sum_{i=1}^{n} b_i \cdot 2^{-i}$$ and $$c = \sum_{i=1}^{n} c_i \cdot 2^{-i}$$ are two numbers in $$[0,1)$$ with finite binary representations, and your $$\sum_{i=1}^{n} a_i = b - c$$.

So the question is whether for all rationals $$x \in [0,1)$$ you can find two numbers $$b$$ and $$c$$ with finite binary representations such that $$x = b - c$$. Using the same arguments or intuition you'd use in base-$$10$$, you'll know that an $$x$$ with no finite binary representation can't be written as a difference of two numbers with a finite binary representation.

Because you have three choices for the coefficients, i.e., $$\{-1,0,1\}$$, you might conjecture (especially now that your initial question has been answered in the negative) that this is more of a ternary (i.e. base $$3$$) setup.

Usually base $$3$$ is written with coefficients in $$\{0,1,2\}$$, but it can be done with the coefficients that you have specified, too. In particular, it is referred to as balanced ternary (wiki) and finds various uses in balance scale problems (among other applications). See the linked wikipage for more!

• I am not sure how to make sense of this answer. What does "this is more of a ternary setup" mean? Balanced ternary may well be interesting, but I don't see how it relates to OP's question, since they are using base 2 (in the sense that the number is constructed in terms of powers of 2). Perhaps this should be a comment? Commented Jul 16 at 14:29
• @preferred_anon Because there are three digits as coefficients. If others find it unhelpful, then I suppose they'll down-vote; if there were no answer, then I may've used a comment. It's at +2/–3 now, so it seems your wonder is shared! Commented Jul 16 at 22:10
• The main point of a ternary system, balanced or $\{0,1,2\}$ or $\{0,40,200,590\}$ is that the base is $3$. Here, the base is $2$, no matter how many choices there are for the "digits".
– JiK
Commented Jul 17 at 13:31
• @JiK Yes, the original post is about binary. Commented Jul 17 at 22:45