Results 1 to 4 of 4

Math Help - 2-adic expansions of inverse powers of 3

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,880
    Thanks
    742

    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.
    Last edited by SlipEternal; August 7th 2013 at 01:14 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,880
    Thanks
    742

    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} \}.
    Last edited by SlipEternal; August 21st 2013 at 09:33 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,880
    Thanks
    742

    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<i\le n, \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<p^k, 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?
    Last edited by SlipEternal; August 23rd 2013 at 07:11 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,880
    Thanks
    742

    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.
    Last edited by SlipEternal; September 4th 2013 at 11:46 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. P-adic convergence
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 7th 2013, 10:48 AM
  2. Replies: 0
    Last Post: August 22nd 2012, 10:06 PM
  3. P-adic valuation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 8th 2010, 12:17 AM
  4. P-adic Number help please
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 10th 2010, 07:04 AM
  5. Inverse trig with powers
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 20th 2008, 07:42 AM

Search Tags


/mathhelpforum @mathhelpforum