9

What's $-\frac{1}{27}$ in $\Bbb Z_2$?

I was naively thinking take the repeating string of the standard binary representation of $3^{-n}$, put it to the left of the point and you get $-3^{-n}$ in $\Bbb Z_2$. Hey presto, it works for $-\frac13$ and $-\frac19$ so why not?

But if I take $x=\overline{000010010111101101}_2$ I can see that $x+512x=-1$, so I get $-\frac1{513}$ in $\Bbb Z_2$. It is at least a multiple of $\frac13$, but not the one I was expecting.

In general it would seem we get $\dfrac{-1}{2^{3^{n-1}}+1}$ by my naive method, which coincides for the two first cases - because $3$ and $9$ are one away from $2$ and $8$.

I should mention $3^{-n}$ have the peculiar property that one half of the repeating binary string is the inverse of the other. This problem arose while I was trying to prove that fact - feel free to prove that if you're minded to do so!

How do I correctly calculate an arbitrary rational number such as $-3^{-n}$?

it's a hire car baby
  • 9,243
  • 2
    This is a good question, at the very least because it illustrates the limitations or misguidedness of insisting on "p-adic" expansions that resemble power series. Yes, I realize that that objection does not necessarily invalidate the question, but it does (to my mind) render it less essential. E.g., $-1/3^n=1/(1-(3^n-1))=\sum_{k\ge 0}(3^n-1)^k$, a $2$-adically convergent series. – paul garrett Oct 11 '19 at 22:48
  • @paulgarrett FWIW, $3^{-n}$ (in $\Bbb Q$) have the peculiar property that one half of the repeating binary string is the inverse of the other. In other words $x \text{ XOR } x\cdot2^{3^{n-1}}\in\Bbb N$. This question arose while I was trying to prove that fact - so it was the binary strings I was interested in more than the p-adics per se. (but then I wanted to clear this up). – it's a hire car baby Oct 11 '19 at 22:51
  • 1
    Third iteration of Newton's Method for inverses with start value 1 gives $13992666605$, which multiplied with $27$ is $\equiv -1$ mod $2^{16}$. Look at the binary expansion of that number, maybe one sees something. Or use higher iterations. – Torsten Schoeneberg Oct 11 '19 at 22:54
  • Ah, well, if the specific peculiarities/coincidences are the point, then I have nothing much helpful to say, sorry. – paul garrett Oct 11 '19 at 22:56
  • 2
    I’m sorry, I don’t understand. We’re talking about infinite expansions, whether $2$-adic or real binary. What is “one half of the binary string”? – Lubin Oct 11 '19 at 23:00
  • @Lubin one half of the repeating string. If you count the ones and zeroes it goes $(4,1,2,1,1,4,1,2,1,1)$ so it repeats but the ones become zeroes. This is true for all $3^{-n}$ – it's a hire car baby Oct 11 '19 at 23:05
  • @paulgarrett your comment is still really helpful, it helped me visualise convergence and gave me a new perspective on proving it. Previously my method was to take sequences like e.g. $3,13,53,\ldots=4^n\cdot3+\frac{4^n-1}{3}$ – it's a hire car baby Oct 11 '19 at 23:10
  • Thanks @TorstenSchoeneberg I'm pretty sure this one needs $18$ binary digits. – it's a hire car baby Oct 11 '19 at 23:13
  • Maybe I misunderstand something, but I think the fact that your "naive method" works is the content of the (relatively easy) answer to https://math.stackexchange.com/q/2323324/96384, isn't it? – Torsten Schoeneberg Oct 23 '19 at 20:56
  • 1
    @TorstenSchoeneberg yes, that's right. I made a schoolboy error in my calc. However Prof Lubin then provided a fabulous proof of the conjecture in the 2nd part of the question which is very much worthy of attention in its own right to anyone interested in such things. – it's a hire car baby Oct 23 '19 at 22:01

3 Answers3

5

This probably doesn’t help a bit, but:

The period of $2$ in $\Bbb Z/(3)^\times$ is two. And $-\frac13$ has $2$-adic period two.
The period of $2$ in $\Bbb Z/(9)^\times$ is six. And $-\frac19$ has $2$-adic period six.
In general, the period of $2$ in $\Bbb Z/(3^n)^\times$ is $2\cdot3^{n-1}$. And we expect that the $2$-adic expansion of $-3^n$ should be purely periodic, period $2\cdot3^{n-1}$.

Indeed, since $3^n|(2^{2\cdot3^{n-1}}-1)$, say with quotient $q_n$, we get the results \begin{align} q_n &= \frac{2^{2\cdot3^{n-1}}-1}{3^n}\\ -\frac1{3^n}&=\frac{q_n}{1-2^{2\cdot3^{n-1}}}\,, \end{align} in which the second line says that the number of binary digits in the repeating block of the $2$-adic expansion of $3^{-n}$ is $2\cdot3^{n-1}$, and what’s in the block is the number $q_n$.

In the case of $n=3$, we get $-\frac1{27}=9709+9709\cdot2^{18}+9709\cdot2^{36}+\cdots$, and surenough, the binary expansion of $9709$ is $\quad000\>010\>010\quad111\>101\>101$. I can’t imagine how one would prove your claim.

EDIT: Addition

I think I have it. But you must check this over carefully, because to me it’s looking like magic, or at least like very devious sleight-of-hand.

To avoid multiple braces in my typing, I”m going to renumber, calling $N=n-1$, so that in my favorite example of the expansion of $-1/27$, we’ll have $N=2$.And I’ll call $$ Q_N=\frac{2^{2\cdot3^N}-1}{3^{N+1}}\,, $$ pretty much as I did above before the renumbering.

Now, what we know is that $2^{2\cdot3^N}-1\equiv0\pmod{3^{N+1}}$, so we can factor $$ \left(2^{3^N}-1\right)\left(2^{3^N}+1\right)\equiv0\pmod{3^{N+1}}\,, $$ but please note that since $3^{N+1}$ is odd, we see that the left-hand factor above is $\equiv1\pmod3$, in particular relatively prime to $3$, and thus to $3^{N+1}$ as well. Thus $3^{N+1}$ divides the right-hand factor, i.e. $3^{N+1}\mid(2^{3^N}+1)$, and once again to make typing easier for myself, I’ll call the quotient $\Omega$. Thus we have: \begin{align} \Omega&=\frac{2^{3^N}+1}{3^{N+1}}\\ 0&<\Omega<2^{3^N}\\ Q_N&=\Omega\left(2^{3^N}-1\right)\\ &=2^{3^N}(\Omega-1)+\left(2^{3^N}-\Omega\right)\\ \text{where we note }0&<2^{3^N}-\Omega<2^{3^N}\,. \end{align}

And that gives us our expression for $Q_N=2^{3^N}a+b$ with both $a$ and $b$ in the interval $\langle0,2^{3^N}\rangle$, namely $a=\Omega-1$ and $b=2^{3^N}-\Omega$. And surenough, $a+b=2^{3^N}-1$, as we desired.

Lubin
  • 62,818
  • 1
    Thanks. Much of this I have already but much less well organised - it's really helpful to see it set out so clearly. If $w=2\cdot3^{n-1}$ is the length of the periodic string then I guess $3^{-n}=(2^{(w/2)+1}+1)-2^{w/2}q+q$ is the identity we seek to prove in order to prove my claim.... Actually that's not right. I've forgotten the residue again (exactly what I did in my original question!) – it's a hire car baby Oct 12 '19 at 09:46
  • 1
    Yes, I woke up in the middle of the night, with much the same idea. I’ll try to work it out. – Lubin Oct 12 '19 at 13:44
  • Funny to hear others do the same thing! I'm always dreaming and then the answer comes to me in my sleep! Anyway, more fun stuff about these numbers. The number of times the string changes from one to zero, appears to be the binary transform of the nth Jacobsthal gap https://oeis.org/A080925 – it's a hire car baby Oct 12 '19 at 19:27
  • ...which I can't distinguish from this: https://oeis.org/A046717 – it's a hire car baby Oct 12 '19 at 19:32
  • 1
    I think I’m understanding it. But I’m at a local restaurant, tanking up. When sobriety comes, after I get home, I’ll try to write up what I know. – Lubin Oct 13 '19 at 22:00
  • It it helps you help me, I think we want that $2^{3^{n-1}}\cdot\sum_{k=0}^\infty2^{k\cdot3^{n-1}}(-1)^k$ is integer for all $n$... although I may be one power of $2$ out in that equation.... Sorry hang on, I jsut noticed you edited your answer!!! I will read now - it doesn't ping the asker when answers are updated. – it's a hire car baby Oct 14 '19 at 11:08
  • At first glance, what you say looks right. But notice that the edit says nothing about, and is not concerned with, the infinite expression. Just what the repeating part $q_n=Q_{N+1}$ might turn out to be. The relationship to the infinite expression was taken care of, I’d say, in the original posting. – Lubin Oct 14 '19 at 13:07
  • By the way, I should have pointed out as I went just what the crucial numbers were in the “standard” example $n=3$, $3^{N+1}=27$: as you probably know, $q_3=Q_2=9709$, $\Omega=19$, $a=18$, $b=493$. – Lubin Oct 14 '19 at 13:16
  • If you're willing I think I should mark the $-1/27$ part of this question as a duplicate of https://math.stackexchange.com/questions/2323324/ , then ask the "repeating" part as another question into which you transfer this as an answer. Are you okay with that? I think it's better for the site. – it's a hire car baby Oct 24 '19 at 11:27
  • I don’t mind, as long as it doesn’t involve too much work. – Lubin Oct 24 '19 at 18:05
  • If you copy and paste your "Addition:" part as an answer here: https://math.stackexchange.com/q/3407493/334732 I'll clean this one up and mark it as a duplicate. – it's a hire car baby Oct 24 '19 at 19:12
  • I’ll do it, but within a full two days. – Lubin Oct 24 '19 at 22:01
  • I did it, @samerivertwice, but the move was a considerable pain. – Lubin Oct 26 '19 at 16:20
  • sorry :( I didn't intend to cause any inconvenience. – it's a hire car baby Oct 26 '19 at 21:38
4

I am not sure what the actual question is. What should be clear is that $$ -\frac1{27}=\frac1{1-28}=\sum_{k=0}^\infty28^k=\sum_{k=0}^\infty2^{2k}(1+2+2^2)^k. $$ It is not obvious (to me, at least) what would be the last expression in the form $\sum\epsilon_k2^k$ with $\epsilon_k\in\{0,1\}$.

Note: Suppose that the sequence is definitely periodic, i.e. suppose that there exists $r\geq0$ and $\ell\geq1$ such that $$ z=\sum_{k=0}^\infty\epsilon_k2^k=\underbrace{(\epsilon_0+\cdots\epsilon_{r-1}2^{r-1})}_{:=M}+2^{r}\sum_{j=0}^\infty2^{j\ell}\underbrace{(\epsilon_r+\cdots+\epsilon_{r+\ell-1}2^{\ell-1})}_{:=N}. $$ Then $$ z=M+2^r\frac{N}{1-2^{\ell}}. $$ Thus the only rational numbers that have a definitely periodic expansion are those of the above form with $M$ and $N\in\Bbb{Z}^{>0}$.

Andrea Mori
  • 26,969
  • should that be $2^{2k}$? – it's a hire car baby Oct 11 '19 at 23:15
  • @samerivertwice, of course! Edited, thanks. – Andrea Mori Oct 11 '19 at 23:16
  • Thanks for this. Another useful perspective. Turns out I made a schoolboy error (as usual)! – it's a hire car baby Oct 11 '19 at 23:29
  • @samerivertwice, please note that I added a note explaining what are the rational numbers that have a definitely periodic 2-adic expansion. – Andrea Mori Oct 11 '19 at 23:49
  • @samerivertwice The point of Andrea's answer is that $\sum_k a_k 2^k, a_k\in {0,1}$ is just a particular kind of $2$-adic series, asking to put $-1/27=\sum_{k\ge 0} 28^k$ in that form is as pointless as asking the decimal expansion of $\sum_{k\ge 0} \frac1{k!}$. We have a sequence of integers converging to $-1/27$ : we are happy with it. – reuns Oct 12 '19 at 02:39
  • @reuns Thanks, I take on board your point. I guess I am interested in numbers whose representation is eventually periodic which is the rational subset of $\Bbb Z_2$ – it's a hire car baby Oct 14 '19 at 16:09
4

You are not correct to assume that $x+512x=-1$. You have a couple zero bits in the actual sum:

$x+512x=513x=...1111111111111\color{blue}{0}11\color{blue}{0}1$

and this is $-19$ in $2$-adics. Thereby $x=-19/513$ and when you reduce this to lowest terms you end with ... $-1/27$.

Oscar Lanzi
  • 39,403