Let $\alpha \in \mathbb{R} $\ $\mathbb{Q}$, then I claim that there exist positive integers $m,k$ such that $2^m > k\alpha > 2^m - 1$.

I tried many elementary approaches but all of them either reformulated the problem or cycled back on itself. This area of maths is uncharted territory for me and so I don't know any advanced approaches I could use, but I am open to anything.

  • $\begingroup$ Do you want to assume also $\alpha>0$? [guess that's necessary, given $m,k$ positive integers]. $\endgroup$ – coffeemath Feb 26 '17 at 23:20
  • $\begingroup$ Yes, in fact you can assume $\alpha > 1$, since the problem for $0 < \alpha < 1$ is simple. $\endgroup$ – TCiur Feb 26 '17 at 23:34
  • $\begingroup$ @TCiur have you tried Kronecker's approximation theorem? $\endgroup$ – dezdichado Mar 24 '17 at 21:15

The claim is false; there exist $\alpha \in \mathbb{R} \setminus \mathbb{Q}$ that cannot be approximated in this way.

To see this, rewrite the desired inequality as $$\frac{k}{2^m} < \frac1\alpha < \frac{k}{2^m-1} \tag{1}$$ If the right-hand inequality holds at all, it holds when $k$ is chosen as large as it can be while the left-hand inequality holds: $k = \left\lfloor \frac{2^m}{\alpha} \right\rfloor$. In other words, an equivalent task is to find $m$ such that $$\frac1\alpha < \frac{\lfloor 2^m/\alpha \rfloor}{2^m - 1} \tag{2}$$ We'll assume that $\alpha > 1$, so that $\frac1\alpha \in (0,1)$. Suppose that the binary expansion of $\frac1\alpha$ is $0.b_1b_2b_3b_4\dots$. In that case, $k = \lfloor 2^m/\alpha \rfloor$ is the integer whose binary expansion is $b_1b_2b_3\dots b_m$, and $\frac{\lfloor 2^m/\alpha \rfloor}{2^m - 1}$ is the real number whose binary expansion repeats as follows: $$0.b_1b_2b_3\dots b_mb_1b_2b_3\dots b_mb_1b_2b_3\dots b_m \dots$$ So to rule out the possibility that $(2)$ holds for any $m$, it is sufficient to choose $\frac1\alpha$ to satisfy the following:

  1. $b_1 = b_2 = 0$.
  2. In the binary expansion of $\frac1\alpha$, we never have $b_i = b_{i+1} = 0$ for any $i>1$.

Then for any $m$, $\frac1\alpha$ and $\frac{\lfloor 2^m/\alpha \rfloor}{2^m - 1}$ agree in the first $m$ bits, but the $(m+1)$-th and $(m+2)$-th bits of $\frac{\lfloor 2^m/\alpha \rfloor}{2^m - 1}$ are both $0$ to match $b_1$ and $b_2$, whereas at least one of $b_{m+1}$ and $b_{m+2}$ is $1$. Therefore $\frac{\lfloor 2^m/\alpha \rfloor}{2^m - 1} < \frac1\alpha$ and $(2)$ does not hold.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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