# 2-adic expansions of inverse powers of 3

• Aug 7th 2013, 12:54 AM
SlipEternal
2-adic expansions of inverse powers of 3
I am trying to teach myself about p-adic numbers, and I came across an interesting property. Consider the following expansions:

\displaystyle \displaystyle \begin{align*}-\frac{1}{3} & = \ldots 010101._2 \\ -\frac{2}{3} & = \ldots 101010._2 \\ -\frac{1}{9} & = \ldots 000111._2 \\ -\frac{2}{9} & = \ldots 001110._2 \\ -\frac{4}{9} & = \ldots 011100._2 \\ -\frac{8}{9} & = \ldots 111000._2 \\ -\frac{7}{9} & = \ldots 110001._2 \\ -\frac{5}{9} & = \ldots 100011._2 \end{align*}

In the case of $\displaystyle -\frac{1}{3}$, the repeating pattern is two digits, and similarly for negative two-thirds. In the case of the six expansions where the denominator is nine, the six digits shown repeat to the left. I understand multiplying by powers of 2 is essentially bit shifting, so those all make sense, but $\displaystyle 16 \cong 7 (9)$ and $\displaystyle 32 \cong 5 (9)$. In other words, to get all rotations of the repeated digits, you simply multiply by all powers of 2 mod 9. This works when the denominator is 27 as well (there are 18 digits that repeat infinitely to the left, and 18 units of the local ring $\displaystyle \mathbb{Z} / 27 \mathbb{Z}$, and the operation of multiplication by 2 mod 27 does indeed rotate the 18 digits). Is there a way to prove this works when the denominator is any power of 3? I can prove that the number of repeated digits in the 2-adic expansion of $\displaystyle -\frac{1}{3^n}$ is $\displaystyle 2\cdot 3^{n-1}$. This is actually relatively simple since a simple induction argument shows that $\displaystyle 3^n$ always divides $\displaystyle 4^{3^{n-1}} - 1$ and

$\displaystyle -\frac{1}{3^n} = \frac{4^{3^{n-1}} - 1}{3^n}\frac{1}{1 - 4^{3^{n-1}}} = \frac{4^{3^{n-1}} - 1}{3^n}\sum_{i \ge 0} \left( 4^{3^{n-1}} \right)^i$

Then, since $\displaystyle 0 < \frac{4^{3^{n-1}}-1}{3^n} < 4^{3^{n-1}}$, which is a positive integer, its base-2 expansion takes at most $\displaystyle 2\cdot 3^{n-1}$ digits, so the expansion repeats that many digits. Also, since multiplying by any power of 2 mod $\displaystyle 3^n$ will give a unit of $\displaystyle \mathbb{Z} / 3^n \mathbb{Z}$, multiplying the whole fraction by that unit will still take no more than $\displaystyle 2\cdot 3^{n-1}$ digits to express in base-2, so that is still the number of repeating digits. I just don't have any idea how to show that you always get a rotation of the digits.

Edit: I am guessing the Division Algorithm might be useful. Consider the following:

$\displaystyle 32 = 9q + r$ has the solution $\displaystyle 32 = 9\cdot 3 + 5$. Now, $\displaystyle -\frac{32}{9} = \ldots 00011100000._2$ where the six digits to the left of the five zeros adjacent to the decimal point are the repeated digits. Essentially, I just bit-shifted five places to the left. Now, $\displaystyle 3-\frac{32}{9} = \ldots 00011100011._2 = -\frac{5}{9}$ which is also $\displaystyle \left\lfloor \frac{32}{9}\right\rfloor - \frac{32}{9}$. I am not quite sure how to relate this to the rotation, though.
• Aug 21st 2013, 09:16 AM
SlipEternal
Re: 2-adic expansions of inverse powers of 3
I think I might have figured it out. Would someone let me know if this proof suffices?

We know $\displaystyle -\dfrac{1}{3^n} \in \mathbb{Z}_2$ for any positive integer $\displaystyle n$. Since $\displaystyle \mathbb{Z}_2 = \varprojlim_{n\to \infty} \mathbb{Z} / 2^n \mathbb{Z}$, which is the inverse limit space, the division algorithm can be extended as follows. If the 2-adic expansion for $\displaystyle -\dfrac{1}{3^n} = \ldots d_2 d_1 d_0._2$, and I want $\displaystyle q = \ldots d_{k+2} d_{k+1} d_k ._2$, using the division algorithm, I would have

$\displaystyle -\dfrac{1}{3^n} = 2^k q + r, \qquad q \in \mathbb{Z}_2, r \in \mathbb{Z}, 0 \le r < 2^k$

Since $\displaystyle \mathbb{Z}_2$ is a division ring, we know there exists $\displaystyle x \in \mathbb{Z}_2$ such that $\displaystyle q = x\left( -\dfrac{1}{3^n} \right)$. Plugging in for $\displaystyle q$ and multiplying both sides by $\displaystyle 3^n$, we get:

$\displaystyle -1 = -2^k x + 3^n r$ (Equation 1)

Since $\displaystyle -1, -2^k,$ and $\displaystyle 3^n r$ are all integers, it must be that $\displaystyle x$ is an integer. Solving for $\displaystyle x$, we get:

$\displaystyle x = \dfrac{1+3^n r}{2^k} > 0$ for any $\displaystyle n>0$ and $\displaystyle k>0$.

Also, $\displaystyle x = \dfrac{1+3^n r}{2^k} \le \dfrac{1+3^n(2^k-1)}{2^k} = 3^n - \dfrac{3^n-1}{2^k} < 3^n - \dfrac{3^0-1}{2^k} = 3^n$

So, we have $\displaystyle 0 \le x < 3^n$. Next, if we divide both sides of (Equation 1) by $\displaystyle -2^k$, we get:

$\displaystyle \dfrac{1}{2^k} = - \dfrac{r}{2^k} 3^n + x$

Since $\displaystyle \dfrac{1}{2^k} \in \mathbb{Z}_3$ and $\displaystyle x \in \mathbb{Z}, 0 \le x < 3^n$, by the 3-adic extended division algorithm, we know that $\displaystyle -\dfrac{r}{2^k} \in \mathbb{Z}_3$. So, from all of this, we obtain that $\displaystyle x \cong 2^{-k} (\mbox{mod }3^n)$. So, since $\displaystyle q = \ldots d_{k+2} d_{k+1} d_k ._2 = x\left( -\dfrac{1}{3^n} \right)$, the multiplication by a unit of the local ring $\displaystyle \mathbb{Z} / 3^n \mathbb{Z}$ is essentially rotating the digits of the repeated pattern $\displaystyle k$ places to the right, which is exactly what I was trying to prove.

Edit: I am using the notation that $\displaystyle \mathbb{Z}_2$ is the space of 2-adic integers, not the set of congruence classes of $\displaystyle \mathbb{Z} / 2\mathbb{Z}$, which is $\displaystyle \{ \overline{0}, \overline{1} \}$.
• Aug 23rd 2013, 07:03 AM
SlipEternal
Re: 2-adic expansions of inverse powers of 3
A related question: does this property extend to higher primes? I think it does. Also if someone has a chance to check this out, can you let me know if this works, as well?

Let $\displaystyle p\neq q$ be primes. Then the p-adic expansion of $\displaystyle -\dfrac{1}{q^n}$ has a repeating pattern (beginning at the decimal point) of $\displaystyle q^n-q^{n-1}$ digits. To show this, first I need to show that $\displaystyle p^{q^n-q^{n-1}} \cong 1 (\mbox{mod } q^n)$. I will prove this by induction. It is a simple algebraic fact that $\displaystyle p^{q-1} \cong 1 (\mbox{mod }q)$. Assume the property holds for all positive integers up to $\displaystyle n$. Then by assumption, $\displaystyle p^{q^n-q^{n-1}} = q^n k + 1$ for some integer $\displaystyle k$. Now, we have $\displaystyle p^{q^{n+1}-q^n} = \left( p^{q^n-q^{n-1}} \right)^q = (q^n k + 1)^q = \sum_{i=0}^q \binom{q}{i} (q^n k)^i$. Looking at the sum term-by-term, for all $\displaystyle 1<i\le n$, $\displaystyle \binom{q}{i} q^{i\cdot n} k^i$ is divisible by $\displaystyle q^{n+1}$ since $\displaystyle i\cdot n \ge n+1$ for any $\displaystyle n\ge 1$. So, $\displaystyle p^{q^{n+1}-q^n} \cong 1 + \binom{q}{1} q^n k (\mbox{mod } q^{n+1} )$. Since $\displaystyle \binom{q}{1} q^n k = q\cdot q^n k = q^{n+1} k \cong 0 (\mbox{mod }q^{n+1})$, the property holds for all positive integers $\displaystyle n$.

So, $\displaystyle -\dfrac{1}{q^n} = -\dfrac{1}{q^n} \dfrac{p^{q^n-q^{n-1}}-1}{p^{q^n-q^{n-1}}-1}$
$\displaystyle = \dfrac{p^{q^n-q^{n-1}}-1}{q^n} \dfrac{1}{1-p^{q^n-q^{n-1}}}$
$\displaystyle = \dfrac{p^{q^n-q^{n-1}}-1}{q^n} \sum_{i\ge 0} \left( p^{q^n-q^{n-1}} \right)^i$

Hence, the p-adic expansion of $\displaystyle -\dfrac{1}{q^n}$ has $\displaystyle q^n-q^{n-1}$ repeating digits to the left of the decimal point as stated. So, assume you want to rotate the repeating pattern to the right $\displaystyle k$ places. We have $\displaystyle -\dfrac{1}{q^n} = \ldots d_2 d_1 d_0._p$ ($\displaystyle 0\le d_i < p$ for all $\displaystyle i$). Again, we want $\displaystyle a = \ldots d_{k+2} d_{k+1} d_k._p$. Using the p-adic division algorithm, $\displaystyle -\dfrac{1}{q^n} = p^k a + r, \qquad a \in \mathbb{Z}_p, r \in \mathbb{Z}, 0\le r < p^k$. Again, we know that $\displaystyle \mathbb{Z}_p$ is a division ring, so there exists $\displaystyle x \in \mathbb{Z}_p$ such that $\displaystyle a = x\left(-\dfrac{1}{q^n} \right)$. Plugging in for $\displaystyle a$ and multiplying both sides by $\displaystyle -q^n$ gets the equation:

$\displaystyle 1 = p^k x - r q^n$ (Equation 1)

And again, we discover that $\displaystyle x$ is actually an integer (not just a p-adic integer). Then, dividing both sides by $\displaystyle p^k$ we get $\displaystyle \dfrac{1}{p^k} = \left(-\dfrac{r}{p^k} \right) q^n + x$. So, $\displaystyle x \cong p^{-k} (\mbox{mod } q^n)$. So, we would like $\displaystyle 0 \le x < p^k$ so that the rotation of the digits $\displaystyle k$ places to the right corresponds to multiplying the original number by a unit of the ring $\displaystyle \mathbb{Z} / q^n \mathbb{Z}$. Solving for $\displaystyle x$ from Equation 1, we get $\displaystyle x = \dfrac{1+r q^n}{p^k}$ which is greater than zero for any positive $\displaystyle n,k$. Since $\displaystyle r<p^k$, $\displaystyle x \le \dfrac{1+(p^k-1)q^n}{p^k} = q^n - \dfrac{q^n-1}{p^k} < q^n - \dfrac{q^0-1}{p^k} = q^n$. So, as before, we have $\displaystyle 0 \le x < q^n$ as desired, and $\displaystyle p^{-k}$ is in fact a unit of the ring $\displaystyle \mathbb{Z} / q^n \mathbb{Z}$, which means so is $\displaystyle x$.

Did I miss anything important? Are there any glaring holes in my argument?
• Sep 4th 2013, 11:22 AM
SlipEternal
Re: 2-adic expansions of inverse powers of 3
I figured out where my proofs go wrong. I never prove that for every unit $\displaystyle 0\le u < q^n$ of the ring $\displaystyle \mathbb{Z} / q^n \mathbb{Z}$, there exists a number $\displaystyle k\in \mathbb{Z}, 0\le k < q^n-q^{n-1}$ and a number $\displaystyle r\in \mathbb{Z}, 0\le r < p^k$ such that $\displaystyle -\dfrac{1}{q^n} = p^k u \left(-\dfrac{1}{q^n} \right) + r$. I still think it is true, but I need to figure out how to prove it in this direction.