Consecutive zeros in the binary representation of $\sqrt{3}$

309 Views Asked by At

$\sqrt3=1.b_1b_2...$is the binary representation of $\sqrt3$.

i.e. $\sqrt3=1+\dfrac{b_1}{2^1}+\dfrac{b_2}{2^2}+...$

Prove that at least one of the digits $b_n,b_{n+1},...,b_{2n}$ is 1.

my attempt:

Square both sides: $$\left(1+\sum_{i=1}^\infty\frac{b_i}{2^i}\right)^2=3$$ Expand and subtract $1$ from both sides $$2\sum_{i=1}^\infty\frac{b_i}{2^i}+\sum_{i=1}^\infty\frac{b_i^2}{2^{2i}}=2$$ divide both side by 2 $$\sum_{i=1}^\infty\frac{b_i}{2^i}+\sum_{i=1}^\infty\frac{b_i^2}{2^{2i+1}}=1$$ Tidy up $$\sum_{i=1}^\infty\frac{1}{2^i}\left(b_i+\frac{b_i^2}{2^{i+1}}\right)=1$$ Lemma: $\displaystyle\sum_{i=m}^\infty\frac{1}{2^i}\left(1+\frac{1}{2^{i+1}}\right)<\frac{1}{2^{m-2}}$

Proof: multiply both side by $2^{m-1}$$$\sum_{i=1}^\infty\frac{1}{2^i}+\frac{1}{2^{m+1+i}}<2$$which is trivial for any positive integer m.

Proceed the proof by contradiction: suppose $b_n,b_{n+1},...b_{2n}$ are all equal to $0$. Then the sum $\sum_{i=1}^{n-1}\frac{1}{2^i}\left(b_i+\frac{b_i^2}{2^{i+1}}\right)$ is in the form of $1-\frac{x}{2^{2n-1}}$.

But $$\sum_{i=2n+1}^\infty\frac{1}{2^i}\left(b_i+\frac{b_i^2}{2^{i+1}}\right)<\frac{1}{2^{2n-1}}$$by lemma.

Q.E.D.

Is this proof correct? I am also happy for an alternative (and hopefully shorter) solution.

1

There are 1 best solutions below

3
On BEST ANSWER

The flaw in your proof was pointed out in the comments, so let me show you my approach


Assume $\sqrt 3$ has all digits $b_i=0$ for $i\in\{n,...,2n\}$ (these are $n+1$ digits). Write

$$\sqrt 3\cdot 2^{n-1}=N + \epsilon= b_1\cdots b_{n-1}.\underbrace{0\cdots0}_{n+1}b_{2n+1}\cdots$$

where $N=b_1\cdots b_{n-1}\in\Bbb N$ is the integer part, and $\epsilon=0.b_{n}b_{n+1}\cdots\in(0,1)$ is the fractional part (which is stricly positive because of the irrationality of $\sqrt{3}$). We have $N< 1.8\cdot 2^{n-1}$ (with $1.8$ being a rough upper bound for $\sqrt 3$). Further, $\epsilon$ must have zeros as the first $n+1$ digits $b_n,...,b_{2n}$. So the largest possible value is

$$\epsilon \le 0.\underbrace{0\dots0}_{n+1}\overline 1=0.\underbrace{0\cdots 0}_n1=\frac1{2^{n+1}}$$

Now observe that

$$\underbrace{3\cdot 2^{2n-2}}_{\text{integer}}=(\sqrt 3\cdot2^{n-1})^2=N^2+2N\epsilon+\epsilon^2.$$

The left side is an integer, and so is $N^2$. Note that $0<2N\epsilon< 0.9$. And finally, since $\epsilon^2<1/2^{2n+2}<0.1$, we cannot close the gap to make the right side a whole integer too.