Powers of Two Modulo Powers of Three

Michael Coons and Heath Winning School of Mathematical and Physical Sciences The University of Newcastle Callaghan, NSW Australia

                Michael.Coons@newcastle.edu.au
                   Heath.Winning@uon.edu.au

Abstract Since 2 is a primitive root of 3^{m} for each positive integer m, the set of points {(n, 2^{n} mod 3^{m}) : n ⩾ 0}, viewed as a subset of ℤ_{⩾0} × ℤ_{⩾0} is bi-periodic, with minimal periods φ(3^{m}) (horizontally) and 3^{m} (vertically). We show that if one considers the classes of n modulo 6, one obtains a finer structural classification. This result is presented within the context of the question of strong normality of Stoneham numbers.

1 Introduction

If m is a positive integer, it is quite clear that the set

T_{m} := {(n, 2^{n} mod 3^{m}) : n ⩾ 0},

viewed as a subset of ℤ_{⩾0} × ℤ_{⩾0} is bi-periodic. Indeed, since 2 is coprime to 3^{m} for any positive integer m, for any integers x, y ⩾ 0, we have

T_{m} ⊆ T_{m} − (φ(3^{m})x, 3^{m}y),  (1)

where φ(·) denotes the standard Euler totient function.

The periodic structure given in (1) generalizes for all powers modulo any other power. What is so surprising about this result is that this simple observation is one of the few existing structural results concerning the modular distribution of the powers of a primitive root.

In this short note, we present a small improvement on this observation. We prove that for m a positive integer, the set T_{m} is the union of six “smaller” bi-periodic subsets of ℤ_{⩾0} ×ℤ_{⩾0}. In particular, we prove the following result.

Proposition 1. For each positive integer m and each k ∈ {0, 1, 2, 3, 4, 5}, the set

L = L_{m,k} := {(6n + k, 2^{6n+k} mod 3^{m}) : n ⩾ 0}

is non-trivially bi-periodic. That is, for each m and each k there exist distinct pairs of nontrivial vectors u := u_{m,k} and v := v_{m,k} with det(u, v) ≠ 0 such that for any point P ∈ L the points P + u and are P + v are also in L.

Note that the condition det(u, v) (the determinant of the matrix with rows u and v) is nonzero ensures that the vectors u and v are not multiples of each other.

Before going on to the proof of Proposition 1, we give an example, in the form of figures, which illustrate our proposition as well as some context for our result.

To this end, note that set T_{m} has a fundamental region; the finite set

{(n, 2^{n} mod 3^{m})}_{0⩽n<φ(3^{m})},

where we identify only the residue 2^{n} mod 3^{m} in the interval [1, 3^{m}], is the ‘repeating part’ of T_{m}. For m = 7, this fundamental region is the large plot in Figure 1. Proposition 1 gives that this fundamental region of T_{m} can be separated into six pieces each having a ‘smaller’ fundamental region, but which union to give T_{m}. This is illustrated in Figure 1, where we have placed the large fundamental region next to the six smaller ones.

We now provide some context for Proposition 1. In fact, we stumbled upon this structure while studying the statistical properties of the binary expansion of a certain real number, which is considered quite ‘random’. Classifying randomness in base expansions goes back at least to Borel [7] who defined the concept of normality.

A real number ξ is called normal to the base b (or b–normal) if, for any positive integer n, each of the b^{n} blocks of length n on the alphabet {0, 1, …, b − 1} occurs in the base-b expansion of ξ with equal frequency 1/b^{n}. The canonical example of a normal number was given by Champernowne [8], who showed that the number

C_{10} := 0.12345678910111213 ⋯,

obtained by concatenating the natural numbers, is normal to the base 10. Of course, Champernowne’s number is by no means random and should fail any true test of randomness. Thus normality, while a necessary property of a random number, is not sufficient. A stronger version of normality was recently introduced by Belshaw and P. Borwein [6].

Write (ξ)_{b} := 0.a_{0}a_{1}a_{2}a_{3} ⋯, and set m_{k}(n) := #{i : a_{i} = k, i ⩽ n}. If the digits of ξ are chosen at random in the base b, the asymptotic frequency m_{k}(n)/n of each 1-string approaches 1/b with probability 1. However, the discrepancy m_{k}(n)−n/b does not approach any limit, but fluctuates. Using the law of the iterated logarithm, Belshaw and P. Borwein [6] Figure 1: The large plot is the fundamental region of T_{7} and the smaller plots from left to right, in the top and bottom row, are the points (n, 2^{n} mod 3^{7}) for n ≡ 0, 1, 2 (mod 6) and n ≡ 3, 4, 5 (mod 6), respectively.

define the real number ξ to be simply strongly normal to the base b if for each 0 ⩽ k ⩽ b − 1, one has

lim inf_{n→∞} \frac{m_{k}(n) − n/b}{\sqrt{2n log log n}} = −\frac{\sqrt{b − 1}}{b} and lim sup_{n→∞} \frac{m_{k}(n) − n/b}{\sqrt{2n log log n}} = \frac{\sqrt{b − 1}}{b}.

We say that the real number ξ is strongly normal to the base b, if it is simply strongly normal to the base b^{j} for each integer j ⩾ 1. Using this definition, Belshaw and P. Borwein [6] showed that Champernowne’s number is not simply strongly normal. Belshaw and P. Borwein also showed that almost all numbers are simply strongly normal, in terms of Lesbegue measure, though no (reasonable) number has been proven to satisfy the definition. Considering potential examples, Aragón Artacho et al. [1] conjectured that the Stoneham number α_{2,3} := ∑_{n⩾1} \frac{1}{3^{n}2^{3^{n}}} is strongly normal to the base 2. Proposition 1 is an outcome of our attack on this conjecture.

Stoneham numbers have a rich history. Stoneham [10] proved that if b is a primitive root of c^{2} for c an odd prime, then the number

α_{b,c} = ∑_{n⩾1} \frac{1}{c^{n}b^{c^{n}}}

is normal to the base b; the 2-normality of α_{2,3} follows from Stoneham’s result since 2 is a primitive root of 9. A much simpler proof of the 2-normality of α_{2,3} was given by Bailey and Misiurewicz [5]. Bailey and Crandall [4] generalized Stoneham’s result by showing that α_{b,c} is b-normal for coprime integers b, c ⩾ 2.

Instead of α_{2,3}, we considered the closely related concatenated binary number

w := 0.w_{1}w_{2}w_{3} ⋯ w_{m} ⋯

with each word, w_{m}, defined as the minimal periodic part of (1/3^{m})_{2} (the binary expansion of 1/3^{m}) for integers m ⩾ 1. Coons [9] explains the similarity between w and α_{2,3}. Coons [9] also provides a division algorithm to compute w_{m} in the desired form, and it is in the application of this algorithm that we find the orbit of the powers of 2 modulo 3^{m}. If one had enough information about this orbit, one could answer the question of strong normality surrounding both w and α_{2,3}. Proposition 1 is a step toward this goal. Remark 2. It is worth noting that strong normality is different from absolute normality. A real number is absolutely normal provided it is b-normal for all integers b ⩾ 2. The Stoneham number α_{2,3}, while conjectured strongly normal to the base 2, is not absolutely normal. Bailey and J. Borwein [3] proved that α_{2,3} is not normal to the base 6. In fact, their result is much more general than this; they showed that for coprime integers b, c ⩾ 2, the number α_{b,c} is not bc-normal. Bailey and J. Borwein [2] later generalized this by showing that α_{b,c} is not B-normal for infinitely many distinct integers B. Remark 3. Our computations suggest that w (and so also α_{2,3}) is unlikely to be strongly normal to the base 2. In fact, it seems to be ‘too good’ in some sense, but the evidence is not strong enough to be conclusive. We had hoped the results given here would provide the tools to settle this, however, Proposition 1 does not provide enough structure to make any real progress on this difficult question.

2 Proof of Proposition 1

Proof of Proposition 1. We will show that the fundamental regions of L = L_{m,k} are invariant when shifted in two different directions; that is there are small vectors (or points if you like) u and v (dependent on m and k), such that for any point P ∈ L, we have also P +u, P +v ∈ L. In other words, the fundamental region of each L exists and is smaller than that of T_{m}. In the course of our proof, we provide an explicit description of the vectors u and v.

We find it convenient to consider both periods as the horizontal component increases (i.e., moving to the right) and also to split the repeated lengths into two cases that will be assessed separately, small and large—inspiring the u-v distinction.

Case 1: the small vectors u.

First take m ⩾ 4 and r = r(k) ∈ {1, 2, 3}. Then the small period requires the addition of the vector u = (2^{r}3^{m−3}, ε3^{m−2}) , where ε takes the value +1 for k ∈ {0, 1, 2} and the value −1 for k ∈ {3, 4, 5}. We write

P + u = (6n + k + 2^{r}3^{m−3}, 2^{6n+k} + ε3^{m−2} mod 3^{m})

and look at the horizontal component

6n + k + 2^{r}3^{m−3} = 6 (n + 2^{r−1}3^{m−4}) + k = 6ℓ + k.

We show that this ℓ gives the required form in the vertical component.

Of course, this reduces to the task of confirming that there is some T ∈ ℤ such that the following rearrangement

2^{6n+k} + ε3^{m−2} mod 3^{m} = 2^{6ℓ+k} mod 3^{m} = 2^{6(n+2^{r−1}3^{m−4})+k} − 3^{m}T

can always be done. Some rearrangement gives

\frac{2^{6n}2^{k} (2^{2^{r}3^{m−3}} − 1)}{3^{m−2}} − ε = 3^{2}T.

We note that this is equivalent to a statement modulo 3^{2}, and since 2^{6} ≡ 1 (mod 3^{2}), the factor 2^{6n} will not effect the solubility; we may thus ignore it completely. We now have an equation whose solubility can proved using induction on m ⩾ 4, namely

\frac{2^{k} (2^{2^{r}3^{m−3}} − 1)}{3^{m−2}} = 3^{2}T + ε.  (2)

It is straightforward to check that the base case m = 4 follows under the following parameters depending on k:

\begin{matrix}k & 0 & 1 & 2 & 3 & 4 & 5 \\ r & 3 & 2 & 1 & 3 & 2 & 1 \\ ε & +1 & +1 & +1 & −1 & −1 & −1 \\ T & 207126 & 101 & 3 & 1657009 & 809 & 25. \end{matrix}

Now assume that (2) has a solution for a given m and note that

2^{2^{r}3^{(m+1)−3}} = (2^{2^{r}3^{m−3}})^{3} = (\frac{3^{m−2} (3^{2}T + ε)}{2^{k}} + 1)^{3} .

Then, expanding out the cube, we have

\frac{2^{k} (2^{2^{r}3^{m−2}} − 1)}{3^{m−1}} = \frac{2^{k}}{3^{m−1}} (\frac{(3^{2}T + ε)^{3} 3^{3m−6}}{2^{3k}} + \frac{(3^{2}T + ε)^{2} 3^{2m−3}}{2^{2k}} + \frac{(3^{2}T + ε) 3^{m−1}}{2^{k}} )

= \frac{(3^{2}T + ε)^{3} 3^{2m−5}}{2^{2k}} + \frac{(3^{2}T + ε)^{2} 3^{m−2}}{2^{k}} + 3^{2}T + ε.

From the induction hypothesis, we have (3^{2}T +ε)3^{m−2} = 2^{k}(2^{2^{r}3^{m−3}−1}), and so for some d ∈ ℤ, we have 3^{2}T + ε = d · 2^{k}. Thus (3^{2}T + ε)^{3} = d^{3}2^{3k} = A · 2^{2k} and (3^{2}T + ε)^{2} = d^{2}2^{2k} = B · 2^{k}, for some A, B ∈ ℤ, so that

\frac{2^{k} (2^{2^{r}3^{m−2}} − 1)}{3^{m−1}} = A · 3^{2m−5} + B · 3^{m−2} + 3^{2}T + ε = 3^{2} (A · 3^{2m−7} + B · 3^{m−4} + T ) + ε

is an integer of the desired form. Thus P + u ∈ L, which establishes the small vector case.

Case 2: the large vectors v.

For this case, we require two subcases, each following in the same spirit as the first case.

Case 2a: when k ∈ {1, 2, 4, 5}. We begin with m ⩾ 2 and take v = (2^{r}3^{m−2}, ε3^{m−1}) where the ε takes the value +1 or −1 depending on the value of k (to be described later). As in Case 1, we look at the horizontal component of

P + v = (6n + k + 2^{r}3^{m−2}, 2^{6n+k} + ε3^{m−1} mod 3^{m}) ,

which, as before, defines the quantity ℓ as

6 (n + 3^{m−3}) + k = 6ℓ + k.

Again as before, we show that this ℓ gives the required form of the vertical component.

As previously, this reduces to the task of confirming that there is some T ∈ ℤ such that the rearrangement

2^{6n+k} + ε3^{m−1} ≡ 2^{6(n+3^{m−3})+k} (mod 3^{m}) = 2^{6(n+3^{m−3})+k} + 3^{m}T,

can always be made. Rearranging, we have

\frac{2^{6n}2^{k} (2^{2^{r}3^{m−2}} − 1)}{3^{m−1}} = 3T + ε,

so that, omitting the 2^{6n} as before, this becomes

\frac{2^{k} (2^{2^{r}3^{m−2}} − 1)}{3^{m−1}} = 3T + ε.  (3)

We prove induction to show solubility. Again, it is straightforward to check that the base case m = 2 follows using the following parameters depending on k in (3);

\begin{matrix}k & 1 & 2 & 4 & 5 \\ r & 1 & 2 & 1 & 2 \\ ε & −1 & −1 & +1 & +1 \\ T & 1 & 7 & 5 & 53 \end{matrix}

Now assuming (3) has a solution for a given m, and noting that

2^{2^{r}3^{m−1}} = (2^{2^{r}3^{m−2}})^{3} = (\frac{(3T + ε) 3^{m−1}}{2^{k}} + 1)^{3} ,

we have

\frac{2^{k} (2^{2^{r}3^{m−1}} − 1)}{3^{m}} = \frac{2^{k}}{3^{m}} (\frac{(3T + ε)^{3} 3^{3m−3}}{2^{3k}} + 3\frac{(3T + ε)^{2} 3^{2m−2}}{2^{2k}} + 3\frac{(3T + ε) 3^{m−1}}{2^{k}} )

= \frac{(3T + ε)^{3} 3^{2m−3}}{2^{2k}} + \frac{(3T + ε)^{2} 3^{m−1}}{2^{k}} + 3T + ε.

The induction hypothesis gives that 2^{k} | (3T + ε), which allows us to write (3T + ε)^{3} 3^{2m−3} = C · 2^{2k}3^{2m−3} and (3T + ε)^{2} 3^{m−1} = D · 2^{k}3^{m−1} for some C, D ∈ ℤ. Thus

\frac{2^{k} (2^{2^{r}3^{m−1}} − 1)}{3^{m}} = 3 (C · 3^{2m−4} + D · 3^{m−2} + T ) + ε

is an integer of the desired form and so P + v ∈ L.

Case 2b: when k ∈ {0, 3}. We now take m ⩾ 4 and v = (2 · 3^{m−3}, ε · 2 · 3^{m−2}), where the ε takes the value +1 or −1 depending on the value of k. Then we have

P + v = (6 (n + 3^{m−4}) + k, 2^{6n+k} + ε · 2 · 3^{m−2} mod 3^{m}) ,

where we now wish to express the vertical component as

2^{6n+k} + ε · 2 · 3^{m−2} ≡ 2^{6(n+3^{m−4})+k} (mod 3^{m}).

Since gcd(2, 3) = 1, we can divide both sides by 2 and then rearrange to give

\frac{2^{6n+k−1} (2^{2·3^{m−3}} − 1)}{3^{m−2}} = 3^{2}T + ε.

Now we can remove a 2^{6(n−1)} by the same method as in Case 1, and so we have only to prove that

\frac{2^{k+5} (2^{2·3^{m−3}} − 1)}{3^{m−2}} = 3^{2}T + ε

is true for all m ⩾ 4. But this is exactly what we proved in the first case (with k = 2, 5), and so we can have P + v ∈ L.

A straightforward comparison of the r values for the various u-v pairs shows that det(u, v) ≠ 0, which completes our proof.

3 Acknowledgments

The authors thank the anonymous referee for comments that greatly improved the exposition of this paper. The research of M. Coons was supported by Australian Research Council grant DE140100223 and the research of H. Winning was supported by a Summer Research Scholarship from the Priority Research Centre for Computer-Assisted Research Mathematics and its Applications.

References

[1] Francisco J. Aragón Artacho, David H. Bailey, Jonathan M. Borwein, and Peter B. Borwein, Walking on real numbers, Math. Intelligencer 35 (1) (2013), 42–60.

[2] David H. Bailey and Jonathan M. Borwein, Nonnormality of Stoneham constants, Ramanujan J. 29 (2012), 409–422.

[3] David H. Bailey and Jonathan M. Borwein, Normal numbers and pseudorandom generators. In Computational and Analytical Mathematics, Vol. 50 of Springer Proc. Math. Stat., Springer, 2013, pp. 1–18.

[4] David H. Bailey and Richard E. Crandall, Random generators and normal numbers, Experiment. Math. 11 (2002), 527–546 (2003).

[5] David H. Bailey and Michał Misiurewicz, A strong hot spot theorem, Proc. Amer. Math. Soc. 134 (2006), 2495–2501.

[6] Adrian Belshaw and Peter Borwein, Champernowne’s number, strong normality, and the X chromosome. In Computational and Analytical Mathematics, Vol. 50 of Springer Proc. Math. Stat., Springer, 2013, pp. 29–44.

[7] E. Borel, Les probabilités denombrables et leurs applications arithmétiques, Palermo Rend. 27 (1909), 247–271.

[8] D. G. Champernowne, The construction of decimals normal in the scale of ten, J. London Math. Soc. 8 (1933), 254–260.

[9] Michael Coons, An arithmetical excursion via Stoneham numbers, J. Aust. Math. Soc. 96 (2014), 303–315.

[10] R. G. Stoneham, A general arithmetic construction of transcendental non-Liouville normal numbers from rational fractions, Acta Arith. 16 (1969/1970), 239–253.

2010 Mathematics Subject Classification: Primary 11A07 Secondary 11A63. Keywords: primitive root, strong normality, normality.

(Concerned with sequences \underline{A000079} and \underline{A000244}.)

Received May 11 2015; revised version received May 18 2015. Published in Journal of Integer Sequences, May 29 2015.

Return to Journal of Integer Sequences home page.