2-adic expansions of inverse powers of 3

• August 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 \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 $-\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 $16 \cong 7 (9)$ and $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 $\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 $-\frac{1}{3^n}$ is $2\cdot 3^{n-1}$. This is actually relatively simple since a simple induction argument shows that $3^n$ always divides $4^{3^{n-1}} - 1$ and

$-\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 $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 $2\cdot 3^{n-1}$ digits, so the expansion repeats that many digits. Also, since multiplying by any power of 2 mod $3^n$ will give a unit of $\mathbb{Z} / 3^n \mathbb{Z}$, multiplying the whole fraction by that unit will still take no more than $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:

$32 = 9q + r$ has the solution $32 = 9\cdot 3 + 5$. Now, $-\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, $3-\frac{32}{9} = \ldots 00011100011._2 = -\frac{5}{9}$ which is also $\left\lfloor \frac{32}{9}\right\rfloor - \frac{32}{9}$. I am not quite sure how to relate this to the rotation, though.
• August 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 $-\dfrac{1}{3^n} \in \mathbb{Z}_2$ for any positive integer $n$. Since $\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 $-\dfrac{1}{3^n} = \ldots d_2 d_1 d_0._2$, and I want $q = \ldots d_{k+2} d_{k+1} d_k ._2$, using the division algorithm, I would have

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

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

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

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

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

Also, $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 $0 \le x < 3^n$. Next, if we divide both sides of (Equation 1) by $-2^k$, we get:

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

Since $\dfrac{1}{2^k} \in \mathbb{Z}_3$ and $x \in \mathbb{Z}, 0 \le x < 3^n$, by the 3-adic extended division algorithm, we know that $-\dfrac{r}{2^k} \in \mathbb{Z}_3$. So, from all of this, we obtain that $x \cong 2^{-k} (\mbox{mod }3^n)$. So, since $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 $\mathbb{Z} / 3^n \mathbb{Z}$ is essentially rotating the digits of the repeated pattern $k$ places to the right, which is exactly what I was trying to prove.

Edit: I am using the notation that $\mathbb{Z}_2$ is the space of 2-adic integers, not the set of congruence classes of $\mathbb{Z} / 2\mathbb{Z}$, which is $\{ \overline{0}, \overline{1} \}$.
• August 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 $p\neq q$ be primes. Then the p-adic expansion of $-\dfrac{1}{q^n}$ has a repeating pattern (beginning at the decimal point) of $q^n-q^{n-1}$ digits. To show this, first I need to show that $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 $p^{q-1} \cong 1 (\mbox{mod }q)$. Assume the property holds for all positive integers up to $n$. Then by assumption, $p^{q^n-q^{n-1}} = q^n k + 1$ for some integer $k$. Now, we have $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 $1, $\binom{q}{i} q^{i\cdot n} k^i$ is divisible by $q^{n+1}$ since $i\cdot n \ge n+1$ for any $n\ge 1$. So, $p^{q^{n+1}-q^n} \cong 1 + \binom{q}{1} q^n k (\mbox{mod } q^{n+1} )$. Since $\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 $n$.

So, $-\dfrac{1}{q^n} = -\dfrac{1}{q^n} \dfrac{p^{q^n-q^{n-1}}-1}{p^{q^n-q^{n-1}}-1}$
$= \dfrac{p^{q^n-q^{n-1}}-1}{q^n} \dfrac{1}{1-p^{q^n-q^{n-1}}}$
$= \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 $-\dfrac{1}{q^n}$ has $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 $k$ places. We have $-\dfrac{1}{q^n} = \ldots d_2 d_1 d_0._p$ ( $0\le d_i < p$ for all $i$). Again, we want $a = \ldots d_{k+2} d_{k+1} d_k._p$. Using the p-adic division algorithm, $-\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 $\mathbb{Z}_p$ is a division ring, so there exists $x \in \mathbb{Z}_p$ such that $a = x\left(-\dfrac{1}{q^n} \right)$. Plugging in for $a$ and multiplying both sides by $-q^n$ gets the equation:

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

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

Did I miss anything important? Are there any glaring holes in my argument?
• September 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 $0\le u < q^n$ of the ring $\mathbb{Z} / q^n \mathbb{Z}$, there exists a number $k\in \mathbb{Z}, 0\le k < q^n-q^{n-1}$ and a number $r\in \mathbb{Z}, 0\le r < p^k$ such that $-\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.