# Convert binary representation with digits $\{0,1\}$ into $\{-1,0,1\}$ (targetting best partial approximations)?

Consider the bit-representation of some irrational number, for instance $$\alpha=\sqrt2=\text{"1.011010100000100111100110011..."}_2 .$$ If I do the partial approximations with left $$n$$ binary digits then I'm always below the true value. It means the partial approximations $$a_n= \sum_{k=0}^n \text{dig}(k)2^{-k} \lt \alpha$$ But it is easy to see that introducing digits from $$\{-1,0,1\}$$ allows partial approximations which are nearer than the approximations before.

I fiddled a bit with the programming of such representation, but I'm unsure, whether this representations are unique. Example let "i" denote the $$-1$$-digit. If I replace the leading bitstring $$\text{"1.011"}$$ by $$\text{"1.10i"}$$ I replace the sequence of approximations $$1,1,5/4,11/8$$ by $$1,3/2,3/2,11/8$$ which gives the sequences of errors as $$\small \begin{array}{rrrr}[&0.414214,& 0.414214,& 0.164214,& 0.0392136,&...] \\\ [&0.414214,& -0.085786,& -0.085786,& 0.0392136,&...] \end{array}$$ I can now in general replace consecutive equal digits of the form $$\text{"x011..110..."}$$ by $$\text{"x100..0i0..."}$$. But it happens, that the introduction of the first $$\text{"1"}$$ concatenates with the previous $$\text{"1"}$$ and I would have to repeat the process until no more change occurs.

This throws now the problem of uniqueness:

Can I assume that this (repeated) process gives the best partial approximations to the irrational target?

Remark: I'm insure about the best tags for the question. Please feel free to improve

• Is this related to the balanced ternary numeral system? – Martin R Sep 27 '19 at 7:30
• @MartinR - I think in the balanced ternary the digits have values $-1/3^k,0,+1/3^k$ while I use here $-1/2^k,0,+1/2^k$. But I didn't think about this - perhaps it would even be better... However, I want further arrive at the expression of that rational approximations in the form $|\alpha - p/2^q|$ instead of $|\alpha - p/q|$ (... and see whether I can get some more intuition about such approximations) – Gottfried Helms Sep 27 '19 at 7:37
• Instead of thinking of this as a process where you start with the "usual" sequence and then modify it (repeatedly, as necessary) wouldn't it be possible to come up with the "correct" sequence on first attempt as follows. Let $D_m=\{\frac n{2^m}:n\in\Bbb Z\}$, so $D_0=\Bbb Z$ and $D_m=D_0/{2^m}$. Let $d_m$ be the unique element of $D_m$ closest to $\sqrt2$,($d_0=1,d_1=3/2,d_2=6/4=3/2..$). Then the "new" digit at each step is $1,0,i$ depending on whether $d_m$ is $>$ or $=$ or $<d_{m-1}$. Side: Would you get infinitely many $1$'s and $i$'s? (Increasing approximations $0,1$'s, decreasing $0,i$'s) – Mirko Sep 28 '19 at 2:21

It seems this goes towards a unique solution, which is distinguished (or "unique") by the property that no two nonzero digits can follow each other.

For the $$\sqrt2$$ I get by this a balanced binary representation as

"1.10i010100000101000i010i010i01000000i01000i000i010i001001000..."

It looks like I could use the "balanced quaternary" representation instead whose digits are obvious when grouping the above string in 2-digits:

"1.10 i0 10 10 00 00 10 10 00 i0 10 i0 10 i0 10 00 00 0i 01 00 0i 00 0i 01 0i 00 10 01 00 ..."
giving (using j for negative 2)
"1.2 j 2 2 0 0 2 2 0 j 2 j 2 j 2 0 0 i 1 0 i 0 i 1 i 0 2 1 0 ..."_{balanced4}

The "moving best-partial-approximations" occur when a truncation follow many zeros:

"1.10i010100000101000i010i010i01000000i01000i000i010i001001000..."
------------------------------------------------------------------
"1.1"
"1.10i0101"
"1.10i010100000101"
"1.10i010100000101000i010i010i01"

which means, $$w(c)=\sqrt 2 \cdot 2^c$$ for $$c\in\{1,7,29,334,... \}$$ approximate especially well to integers, each one better than all $$w(c)$$ before.

So this "indexing" by the binary representation of the number agrees with the simple numerical checks computing the fractional parts of $$w(c)$$ directly and seems to be a meaningful version of a "balanced-binary" representation with the desired property of exposing the best partial approximations as asked for in the title.