Collatz-type Problems with Multiple Divisors by Keira Gunn B.Sc., McMaster University, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) August 2009 © Keira Gunn 2009 ii Abstract The Collatz Conjecture hypothesizes that if a sequence of integers beginning t with any positive integer t0 is recursively defined so that tj+1 = 2j when tj is even and tj+1 = 3tj + 1 when tj is odd, then there will be some j ∈ N such that tj = 1. I propose a similar family of problems (which I call systems) involving a set of prime divisors {p1 , ..., pk } and a multiplier m, where the sequence is recursively t t defined so that tj+1 = pj1 if tj is divisible by p1 , tj+1 = pj2 if tj is divisible by t p2 but not p1 , tj+1 = pj3 if tj is divisible by p3 but not p1 or p2 etc., and if tj is not divisible by any of the primes, then tj+1 = mtj + 1. Assuming the residues of the terms of these sequences behave randomly modulo p1 · · · pk , I propose a multiplicative expectation and data to suggest that this is a reasonable model for these systems. If the expectation is less than 1, as in the case of the Collatz problem, then I hypothesize that any sequence will eventually result in some finite cycle. As well, if my model for these systems is accurate, then I prove that the inclusion of an increasing prime q to a fixed set of prime divisors will result in an effect that gradually diminishes for the multiplicative expectation of the system. iii Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Calculating Expectation . . . . . . . . . . . . 2.1 The Expectation Formula . . . . . . . . . . 2.2 Frequencies of Divisibility . . . . . . . . . . 2.2.1 The Probability Distribution Matrix . . . . 3 3 3 4 3 Uniqueness of the Principal Eigenvector . . . . . . . . . . . . . . 7 4 Increasing Divisors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Evidence Supporting this Model 5.1 The E(S) = 1 threshold . . . . 5.2 Occurrence of Divisors . . . . . 5.3 Occurrence of Residues . . . . . 5.4 Other Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 . . . . . 29 29 32 38 46 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 iv List of Tables 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 5.17 5.18 5.19 5.20 5.21 5.22 5.23 5.24 5.25 5.26 5.27 5.28 Divergence in S(17/{2, 3, 5}) (E(S) = 1.0384) . . . . . . . . . . . Divergence in S(5/{2, 7}) (E(S) = 1.0275) . . . . . . . . . . . . . Divergence in S(9/{2, 5, 11}) (E(S) = 1.0182) . . . . . . . . . . . Divergence in S(11/{2, 3, 67}) (E(S) = 1.0043) . . . . . . . . . . Divergence in S(11/{2, 3, 59}) (E(S) = 1.0015) . . . . . . . . . . Highest Number Attained for Systems with Expectation less than 1 Expected and Actual Occurrences of Division in S(17/{2, 3, 5}) . Expected and Actual Occurrences of Division in S(5/{2, 7}) . . . Expected and Actual Occurrences of Division in S(9/{2, 5, 11}) . Expected and Actual Occurrences of Division in S(11/{2, 3, 67}) Expected and Actual Occurrences of Division in S(11/{2, 3, 59}) Expected and Actual Occurrences of Division in S(11/{2, 3, 47}) Expected and Actual Occurrences of Division in S(11/{2, 3, 53}) Expected and Actual Occurrences of Division in S(19/{2, 3, 5, 11}) Expected and Actual Occurrences of Division in S(11/{2, 3, 61}) Expected and Actual Occurrences of Division in S(23/{2, 3, 5, 7}) Expected and Actual Occurrences for Residues in S(17/{2, 3, 5}) Expected and Actual Occurrences for Residues in S(5/{2, 7}) . . Expected and Actual Occurrences for Residues in S(9/{2, 5, 11}) Expected and Actual Occurrences for Residues in S(11/{2, 3, 67}) Expected and Actual Occurrences for Residues in S(11/{2, 3, 59}) Expected and Actual Occurrences for Residues in S(11/{2, 3, 47}) Expected and Actual Occurrences for Residues in S(11/{2, 3, 53}) Expected and Actual Occurrences for Residues in S(19/{2, 3, 5, 11}) Expected and Actual Occurrences for Residues in S(11/{2, 3, 61}) Expected and Actual Occurrences for Residues in S(23/{2, 3, 5, 7}) Multiplicative Expectations for some Systems . . . . . . . . . . . Random Numbers Used in Trials . . . . . . . . . . . . . . . . . . 30 30 31 31 31 31 33 33 34 34 35 35 36 36 37 37 38 38 38 39 40 41 42 43 44 45 46 46 v Acknowledgements This work would not have been possible without the guidance and support of my supervisor, Dr. Greg Martin. As well, I would like to thank David Steinberg and Heather Hurley for helping me make it this far, and Puck Saunders for inspiration. Finally, I would like to thank Tamaki Kano for her encouragement. 1 Chapter 1 Introduction The Collatz problem, also known as the “3x+1” problem, was first posed by Lothar Collatz in 1937 [3]. The problem is defined by its very simple iterative step: if a number is even then divide by two, and if the number is odd then multiply by three then add one (hence the name “3x+1”.) The famous conjecture states that–given any starting number–if this iteration is repeatedly performed to generate a sequence of numbers, then eventually 1 will be contained in that sequence [3]. While the problem itself seems easy enough, extensive research has yielded no proof to this conjecture. However, as of January 18th of 2009 it has been verified that sequences beginning with any of the numbers up to about 20 × 258 do eventually reach 1 [5]. Probabilistically, one would expect any such sequence to decrease over time. For large numbers, the effect of the “+1” is negligible and so one only needs to investigate the effects of multiplication by 3 or division by 2. The problem is set up in such a way that division by 2 occurs immediately following any muliplication by 3 (the addition of 1 guarantees the resulting number is even) and so–assuming randomness (which will be better explained in the next chapter)– division by 2 again should occur 12 of the time, and division by 2 yet again should occur 14 of the time, etc. For large numbers, this gives a multiplicative expectation of 3 1 2 2 · 2 ···2 1 2k = ··· 3 1 1 2(1+ 2 + 4 +...) = 3 3 = . 2 2 4 This thesis makes no attempt to prove the “3x+1” conjecture, but seeks to look at a family of related problems in the hopes of gaining some insight. Each problem will be referred to as a “system”, denoted by S(m/{p1 , ..., pk }) (pi is prime, and m is coprime to pi for all i in 1, 2, ..., k), where the iterative step will include an “mx+1” action (the multiplication of m then addition of 1) followed by division by each pi until the resulting number is no longer divisible by any of the pi ’s. Clearly the resulting number after an iteration is coprime to each pi . For consistency, the starting number in a sequence will be divided by the pi ’s as many times as possible before the first iteration is performed. It is not a necessity that the number 1 is used for addition, the only requirement on the addition number is that it is coprime to each of the prime divisors. However, using 1 guarantees that the addition operation is as negligible as possible. After some analysis (which is covered in the next chapter) a multiplicative expectation can be found for each system. An expectation of greater than 1 Chapter 1. Introduction 2 suggests that sequences are gradually increasing, and so there should be many divergent sequences. An expectation of less than 1 suggests that sequences are gradually decreasing and so all sequences should eventually be contained in some finite cycle. The fifth chapter provides empirical evidence supporting these expectations and the idea that the sequences behave randomly (despite the sequences being predetermined by the initial starting point.) In addition, an interesting but expected result is proven in chapter four. That is, given a system S(m/{p1 , ..., pk }), the expection of S(m/{p1 , ..., pk , q}) converges to the expectation of S(m/{p1 , ..., pk }) as q goes to infinity. Throughout this thesis, N will be used to denote the product of p1 · · · pk . For convenience, the expression “a ≡ b” will mean a ≡ b (mod N ) unless a different modular base is specified. In addition, the term “principle eigenvector” will refer to the eigenvector corresponding to the eigenvalue λ = 1 for any probability distribution matrix. 3 Chapter 2 Calculating Expectation Assuming a random distribution of the residues, the multiplicative expectation for each system is calculated by finding the frequencies at which a sequence should be divisible by each of the divisors, and then using those frequencies in the upcoming expectation formula. 2.1 The Expectation Formula Given that a randomly selected integer is divisible by a divisor p, there is a p1n probability that it is divisible by pn+1 for any n ≥ 0. Another way of expressing this is that, if there is divisibility by p, then the probability of divisibility by p again is p1 , and the divisibility by p a third time is p12 and etc.. If we let αi be the expected frequency of divisibility by the divisor pi for the system S(m/{p1 , ..., pk }), then the expectation E(S) is E(S) = m k Y 1 n 1 ( p1i )( p1i ) pi · · · ( p1i ) pi · · · αi i=1 =m k Y 1+ p1 +...+ p1n +... αi ( p1i ) i i =m pi k Y 1 αi pi −1 i=1 i=1 pi . For the purposes of this thesis, all systems are of the form S(m/{2, p2 , ..., pk }) (see chapter 3 for an explanation). Since the multiplier must be coprime to all the divisors, addition by 1 guarantees that divisibility by 2 must occur after an 1 iteration, so α1 = 1 and α1 p1p−1 = 2. This simplifies the expectation to E(S) = m pi k 1 2 Y 1 αi p −1 i 2 i=2 pi k p i m Y 1 αi pi −1 = . 4 i=2 pi (2.1) From here it is quite simple to calculate the multiplicative expectation once the values of α2 through αk are known. 2.2 Frequencies of Divisibility Each iteration occurs on one of p − 1 coprime residues modulo p. Multiplication by m is a bijection from that set of coprime residues to itself. Addition by 1 Chapter 2. Calculating Expectation 4 will then shift exactly one of those initial p − 1 residues (the residue that is congruent to −m−1 , precisely) to the value of 0 modulo p, and will thus grant divisibility by p. Because of this, one could naı̈vely conclude that the value of each αi is simply pi1−1 . In fact, as has already been established, this holds true for the case p1 = 2. However, for larger primes there are more complicated interractions taking place between the division processes and the likelihood of resulting in any of the residues. For example, suppose the system is S(5/{2, 3}). This gives N = 6 and the residues 1 and 5. If we start with 5 (mod 6) then mt0 + 1 ≡ 2 and so division by 2 results in either 1 or 4 (mod 6) with equal probabilities of 12 . If the result is 4 then a second division takes place resulting in either 2 or 5 (mod 6) with equal probabilities of 41 . Division of 2 by 2 should again take place, giving the probability of the resulting number being congruent to 1 (mod 6) a value strictly greater than 12 . The probability of the resulting number being congruent to 5 (mod 6) is thus less than 12 . Specifically, the probabilities are not equal, which refutes the hypothesis made in the previous paragraph. If an iteration within a system S is defined to include both the “mx + 1” action and all divisions that take place (until the resulting number is no longer be divisible by any of the primes), then one method of approaching this problem is to construct the probability distribution matrix (which will be denoted by PS ) for the coprime residues modulo N after each iteration. If a is a random representative of the set {a, a + N, ..., a + M N } and PS,M,(b,a) is the probability of a being brought to b (mod N ) after one iteration, then PS,(b,a) will be the limit of PS,M,(b,a) as M goes to infinity. In the next section, all probabilities discussed will actually be the limit of probabilities of random representives of the set {a, a + N, ..., a + M N } as M → ∞. Once PS is constructed, the principal eigenvector will give the long-term expectation of the distribution of the residues. From there, the sum of the expectations of the residues that are congruent to −m−1 (mod pi ) will give the overall expectation of being divisible by pi , which is the value of αi . 2.2.1 The Probability Distribution Matrix For the system S(m/{p1 , ..., pk }), the matrix PS can be decomposed into k + 1 transitional matrices T0 , ..., Tk . The first matrix is the φ(N ) × N probability distribution matrix for the set of coprime residues modulo N into the set of all residues modulo N after the “mx + 1” action (T0 (b, a) is the probability of anything congruent to a being brought to b (mod N ) after the “mx + 1” action). For a ∈ Z∗N , a has a probability of 1 of being brought to ma + 1 in ZN , so T0 (ma + 1, a) = 1 and T0 (b, a) = 0 for all b 6≡ ma + 1. Chapter 2. Calculating Expectation 5 For the system S(5/{2, 3}), the first transitional matrix would be given by 0 0 0 1 0 0 , T0 = 0 0 0 0 1 0 where T0 gives the probabilities of the set {1, 5} being brought into the set {1, 2, 3, 4, 5, 6} (for T0 above, and T1 and T2 below, the order of the indices in T0 correspond to the order of presentation of the sets). For i ∈ {1, ..., k}, the matrix Ti is the probability distribution matrix for the action of division by pi , so Ti (b, a) is the probability of anything congruent to a being brought to b (mod N ) through division by pi . Let Ii = {a ∈ ZN |a coprime to p1 , ..., pi−1 }. If division takes place in the order the primes are listed, then division by p1 distributes Z∗N = I1 to the set I2 , division by p2 distributes I2 to I3 , etc.. Each matrix Ti need only consider the probability distribution from Ii to Ii+1 after division by pi . (For our example S(5/{2, 3}), we have I1 = {1, 2, 3, 4, 5, 6}, I2 = {1, 3, 5}, and I3 = {1, 5}) If a is coprime to pi then division by pi does not take place, so the “division by pi ” action brings a to a with probability 1. This gives Ti (a, a) = 1 and Ti (b, a) = 0 for all b 6= a. In S(5/{2, 3}), this results in columns [1, 0, 0]T , [0, 1, 0]T , [0, 0, 1]T in T1 corresponding to 1, 3, 5 respectively and columns [1, 0]T , [0, 1]T in T2 corresponding to 1, 5 respectively. If pi divides a then there is a p1i probability that division by pi will result in each of b1,s ≡ pai +s pNi for s ∈ {1, ..., pi } (the set of all numbers modulo N that are congruent to a when multiplied by pi ). Because pai ∈ Ii and pNi = R · p1 · · · pi−1 for some integer R, we have that b1,s ∈ Ii for each s. Since pNi is coprime to pi , the values of s pNi run through all residues modulo pi , thus the values b1s also run through all residues modulo pi . One of these values, say c1 = b1,s for some s is divisible by pi again. From there, the numbers b2,s ≡ cp1i + s pNi for s ∈ {1, ..., pi } will each have a probability of p12 of occuring and will all be contained in Ii . As i well, one of the values, say c2 , will be divisible by p1 . For S(5/{2, 3}), consider 2 ∈ I1 and division by 2. b1,1 = 22 + (1) 26 = 4 and b1,2 = 22 + (2) 62 = 1. So, c1 = 4. Similarly, b2,1 = 5 and b2,2 = 2. Continuing in this manner, there will be some r, s such that br,s = a (For division of 2 by 2 in S(5/{2, 3}) it is clear that r = 2). In fact, r is the order of N pi in the multiplicative group modulo M where M is the product of all primes N in {p1 , ..., pk } that divide a (so a = sM for some s coprime to M ). If d is N d d d the order of pi , then api = sM · pi satisfies both api ≡ sM (mod M ) and apdi ≡ 0 (mod M ), thus apdi ≡ sM = a (mod N ) by the Chinese Remainder N Theorem. Since, for any r < d we have apdi 6≡ sM (mod M ), the Chinese Remainder Theorem also gives that apdi 6≡ a (mod N ). By combining this and the fact that each set of bt,s ’s runs through all numbers such that bt,s pti = a, Chapter 2. Calculating Expectation 6 it is evident that r = d is the first level at which the value a recurs (that is, bd,s = a for some s). The sequence will then repeat itself in such a manner that b(t+r),s = bt,s . Thus the probability of resulting in bt,s (for those bt,s that are not divisible by pi ) is equal to 1 1 1 pir−t 1 1 1 + 1 + + + ... = . (2.2) + ... = + pti pt pr p2r pri − 1 pt+r pt+2r i i So, for any a ∈ Ii and b ∈ Ii+1 (we can use Ii+1 since we are restricted to elements in Ii that are not divisible by pi ), if r is the least positive integer such that apri ≡ a and t is the least positive integer such that bpti ≡ a then pr−t Ti (b, a) = pri −1 where t is defined, and 0 elsewhere. i Keeping with the S(5/{2, 3}) example, corresponding to 2 in T1 we have the 2−1 2−2 column [ 222 −1 , 0, 222 −1 ]T = [ 23 , 0, 13 ]T . The rest of the calculations give 1 T1 = 0 0 and T2 = 2 3 0 1 3 1 3 0 1 0 0 2 3 1 2 1 2 1 0 0 0 0 1 1 0 0 . 0 The overall probability distribution matrix, PS is then calculated by the multiplication of all the transitional matrices as follows: PS = Tk · Tk−1 · · · T1 · T0 . (2.3) For S(5/{2, 3}) this results in 1 PS = 0 1 2 1 2 1 0 0 1 0 2 3 0 1 3 0 1 0 1 3 0 2 3 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 = 12 0 2 0 0 2 3 1 3 . The principal eigenvector for PS of this system is [4, 3]T , so the long term probability distribution is [ 74 , 37 ] for the residues {1, 5}. Of 1 and 5, the only value which is congruent to −5−1 (mod 3) is 1, and so the expected probability 3 4 of divisibility by 3 is 47 . Equation (2.1) gives E(S) = 54 [( 13 ) 3−1 ] 7 ≈ 0.48747. Since the multiplicative expectation is significantly lower than 1, it is expected that this system should quickly decrease, and eventually result in finite cycles. A list of several other systems and their multiplicative expectations can be found in Table 5.27. 7 Chapter 3 Uniqueness of the Principal Eigenvector The final steps in calculating the expectation require that the eigenvector corresponding to λ = 1 is unique. Obviously, if there are multiple such eigenvectors then there is significant ambiguity in how to evaluate a2 through ak and thus E(S). This section will show that using p1 = 2 ensures that the principal eigenvector is unique. Showing this can be broken into two parts; first: any residue has a positive probability of being brought to any other residue (or itself) after a finite number of iterations and second: if this is the case, then the steady state vector is unique. The first lemma is a slightly stronger version of the latter. Proposition 3.1. Let M be a probability distribution matrix with index set I. If for any i, j ∈ I there is some r ∈ N such that (M r )(i,j) is non-zero, then there is a unique eigenvector corresponding to the eigenvalue λ = 1, and that eigenvector has positive entries. Proof. Let M be a probability distribution matrix as described in the lemma. According to Perron-Frobenius theorem, there is an eigenvector associated with the eigenvalue λ = 1, and this vector has non-negative entries [4, Chapter 2]. Let ~v be a non-negative eigenvector (whose entries sum to 1) corresponding to λ = 1; there must be some non-zero value in ~v , so suppose ~v(a) 6= 0 for some a ∈ I. According to the hypothesis, for any k ∈ I there is some s (dependent on k) such that (M s )(k,a) > 0. ~v is an eigenvector for M corresponding to λ = 1, so ~v is also an eigenvector for M s corresponding to λ = 1s = 1. We have that that M s · ~v = ~v , and thus (M s~v )(k) = ~v(k) . This gives ~v(k) = (M s~v )(k) = X i∈I (M s )(k,i)~v(i) = X (M s )(k,i)~v(i) + (M s )(k,a)~v(a) . i∈I|i6=a Both ~v and M s have only non-negative entries. This gives s ~v(k) ≥ 0 + M(k,a) ~v(a) . s M(k,a) and ~v(a) were selected to be positive, so we have ~v(k) > 0. Chapter 3. Uniqueness of the Principal Eigenvector 8 ~v(k) must be positive for any k therefore ~v has no zero entries. Now that positivity of the vector is established, uniqueness will be proven. Let ~u be an eigenvector with positive entries as described above. Suppose ~v is a second linearly independent eigenvector corresponding to λ = 1. So, any linear combination a~v + b~u is also an eigenvector corresponding to λ = 1 for a, b ∈ R. Let c = min{ ~u~vii |i ∈ I}. Consider w ~ = ~v − c~u. For each j ∈ I we have w ~ (j) = ~v(j) − min{ ~v(j) ~v(i) |i ∈ I}~u(j) ≥ ~v(j) − ~u(j) = 0. ~u(i) ~u(j) So w ~ is an eigenvector with non-negative entries. Clearly for the i that ~ v elicits the minimum of ~u(i) , we have that w ~ (i) = 0. Since ~u and ~v are linearly (i) ~ independent, w ~ 6= 0. The first part of the proof of the lemma verifies that any non-negative eigenvector must be have all positive entries, so w ~ cannot exist and thus ~v cannot exist. The eigenvector is unique. The second lemma will address the hypothesis in Proposition 3.1 that for any i, j ∈ I, there is an r such that (M r )(i,j) is positive. The proof of the following proposition will go back and forth between the systems S(m/{2, p2 , ..., pk }) and S(m/{2, p2 , ..., pk , q}). To avoid confusion, N will refer to 2p2 · · · pk . Since Z∗N q ' Z∗N × Z∗q , the coprime residues modulo N q will be written as coordinates in Z∗N × Z∗ q (written as [a, b]). Given P (the probability distribution matrix for S(m/{2, p2 , ..., pk , q})) and b. Given P̄ a, b ∈ Z∗N q , if (P k )(b,a) > 0 for some k ∈ N then we will write a (the probability distribution matrix for S(m/{2, p2 , ..., pk })) and a, b ∈ Z∗N , if (P̄ h )(b,a) > 0 for some h ∈ N then we will write a ¯ b. Lemma 3.2. Let M be a probability distribution matrix with index I, and let a, b, c ∈ I. If a b and b c then a c. Proof. It suffices to show that (P h1 +h2 )(c,a) > 0. Since a b and b c we have (P h1 )(b,a) > 0 and (P h2 )(c,b) > 0 for some h1 , h2 ∈ N. So X (P h1 +h2 )(c,a) = (P h2 P h1 )(c,a) = (P h2 )(c,d) (P h1 )(d,a) d∈I ≥ X (P h2 )(c,d) (P h1 )(d,a) = (P h2 )(c,b) (P h1 )(b,a) > 0. d=b Finally, using the notation in Chapter 2, if P = Tk+1 · · · T0 , then let P 0 = Tk · · · T0 . So, P 0 represents the probability distribution in S(m/{2, p2 , ..., pk , q}) without division by q. In other words, P 0 is the probabilityPdistribution matrix 0 for qZ∗N in S(m/{2, p2 , ..., pk }), so we have that P̄(a,b) = c∈Zq P([a,c],[b,d]) for any d ∈ Zq (this is proven later as Lemma 4.3). Specifically, if P̄(a,b) > 0 then 0 for any d ∈ Zq there is some c ∈ Zq with P([a,c],[b,d]) > 0. For the remainder of this chapter, let T = Tk+1 . Chapter 3. Uniqueness of the Principal Eigenvector 9 Lemma 3.3. If P̄(x,a) > 0 then P([x,y],[a,−m−1 ]) > 0 for any y ∈ Z∗q . 0 Proof. Let c0 ∈ Zq be such that P([x,c 0 ],[a,−m−1 ]) > 0 X X 0 P([x,y],[a,−m−1 ]) = (T P 0 )([x,y],[a,−m−1 ]) = T([x,y],[b,c]) P([b,c],[a,−m −1 ]) ∗ b∈Z∗ N c∈Zq ≥ XX 0 T([x,y],[b,c]) P([b,c],[a,−m −1 ]) b=x c=c0 0 = T([x,y],[x,c0 ]) P([b,c 0 ],[x,−m−1 ]) . P 0 includes the “mx + 1” action but has no division by q, and so for any 0 y1 , y2 ∈ Z∗N q such that P([y −1 ]) > 0 it must be true that [y1 , y2 ] is 1 ,y2 ],[x,−m 0 divisible by q; therefore c ≡ 0 (mod q). If d is the multiplicative order of q in Z∗N , then by equation (2.2), for any [x0 , y 0 ] such that [x0 q d , y 0 q d ] = [x, c0 ] we have that T([x0 ,y0 ],[x,0]) > 0. But, xq d ≡ x (mod N ) and yq d ≡ 0 (mod q) for any y ∈ Z∗q , thus T([x,y],[x,c0 ]) > 0. For any y ∈ Z∗q , P([x,y],[a,−m−1 ]) > 0. Recall an iteration is the “mx + 1” action, followed with divisions by the for primes 2, p2 , ..., pk . So, if ψ is an iteration of x, then ψ(x) = 2r1mx+1 r r p 2 ···p k 2 k some non-negative integers r1 , ..., rk (note that the result of an iteration in Z∗N is not necessarily well-defined). However, an iteration that can be applied to one residue may not be applicable to another depending on divisibilities after the “mx + 1” action. We will say an iteration ψ is valid on x if ψ(x) = 2r1mx+1 r r p22 ···pkk where ri ≥ 1 when mx + 1 is divisible by pi and ri = 0 if mx + 1 is not divisible by pi . Also, we will write ψ(x) ≡ a if a ∈ Z∗N and 2r1 pr22 · · · prkk a ≡ x. As a result, P(b,a) > 0 if and only if there is a valid iteration ψ such that ψ(a) ≡ b and a b if and only if there is a sequence Ψ of valid iterations on a such that Ψ(a) ≡ b. Lemma 3.4. Let x, a ∈ Z∗N , and b ∈ Z∗q . Let ψ1 , ..., ψs be a sequence of valid iterations on x such that ψs ◦ ... ◦ ψ1 (x) ≡ a. If there is t ∈ {1, ..., s} such that ψt ◦ ... ◦ ψ1 (b) ≡ 0 (mod q) then [a, b] [x, y] for any y ∈ Z∗q . Proof. Let t be the smallest integer such that ψt ◦ ... ◦ ψ1 (b) ≡ 0 (mod q). So, ψt−1 ◦ ... ◦ ψ1 is a valid sequence of iterations of b in S(m/{2, p1 , ..., pk , q}). Let Ψ = ψt−1 ◦ ... ◦ ψ1 . Then Ψ(b) ≡ −m−1 (mod q) must be true. Using Lemma 3.3 along with the fact that P̄(ψt Ψ(a),Ψ(a)) > 0, we have P([ψt Ψ(a),z],[Ψ(a),−m−1 ]) > 0 for any z ∈ Z∗q , in particular z = −m−1 . Thus, ψt can be amended to ψt0 in S(m/{2, p1 , ..., pk , q}) to satisfy ψt0 ◦ Ψ([a, b]) = [ψt ◦ ... ◦ ψ1 (a), −m−1 ] and be valid in S(m/{2, p2 , ..., pk , q}). t0 = t + 1 is now the smallest such integer with ψt0 ◦ ... ◦ ψ1 (b) ≡ 0 (mod q). Inductively, the same procedure as above can be applied until t0 = s. For t0 = s, choose z = y instead of z = −m−1 . As constructed, ψt0 , ..., ψs0 are valid iterations under S(m/{2, p1 , ..., pk , q}), and ψs0 ◦ ... ◦ ψt0 Ψ(a) ≡ ψs ◦ ... ◦ ψ1 (a) = x. Chapter 3. Uniqueness of the Principal Eigenvector 10 For any valid iteration ψ on [−m−1 , b], where ψ([−m−1 , b]) = [x, y], define 2ψ so that 2ψ([−m−1 , b]) = [x, 2y]. Lemma 3.5. 2ψ is a valid iteration on [−m−1 , b]. Proof. It is enough to show that P([x,2y],[−m−1 ,b]) > 0. ψ([−m−1 , b]) = [x, y] implies that 2r1 pr22 · · · prkk y ≡ mb + 1 (mod q) and 2r1 pr22 · · · prkk x ≡ m(−m−1 )+1 ≡ 0 (mod N ) for some positive integers r1 , ..., rk . If r1 > 1 then let r10 = r1 , otherwise let r10 = r1 +d2 where d2 is the multiplicative 0 order of 2 in Z∗q . Then 2r1 −1 pr22 · · · prkk x ≡ 0 ≡ m(−m−1 ) + 1 (mod N ), and 0 0 2r1 −1 pr22 · · · prkk 2y = 2r1 pr22 · · · prkk y ≡ 2r1 pr22 · · · prkk y ≡ mb + 1 (mod q) and thus P ([x, 2y], [−m−1 , b]) > 0. Proposition 3.6. Given a system S = S(m/{2, p2 , ..., pk }), let N = 2p2 · · · pk and let P be the probability distribution matrix of S for the coprime residues of N . Then, for any i, j ∈ Z∗N , there is an r ∈ N such that (P r )(i,j) is positive. Proof. Using the notation above, this proposition is equivalent to showing that b. for all a, b ∈ Z∗N , we have a The proof will proceed by induction on the number of prime divisors. First, let k = 1. We have p1 = 2 and a = b = 1. ma + 1 = 2s L for some odd L, so division by 2s will occur, resulting in L ≡ 1 ≡ b. So, a b. Suppose the statement is true for all S(m/{2, p2 , ..., pk }), and consider the system S(m/{2, p2 , ..., pk , q}). Let [a, b] ∈ Z∗N × Z∗ q. First, it will be shown that (a, b) ∈ Z∗N × Z∗q can be brought to (a, y) for any y ∈ Z∗q . By the inductive hypothesis, a ¯ −m−1 is true. So, there is some sequence of iterations ψ1 , ..., ψs−1 in S(m/{2, p2 , ..., pk }) such that ψs−1 ◦...◦ψ1 (a) = −m−1 . Let ψs (x) = mx+1 be the next iteration in the sequence, and so ψs ◦...◦ψ1 (a) ≡ x N for any x ∈ Z∗N . In particular, ψs ◦ ... ◦ ψ1 (a) ≡ a. If for some integer t ≤ s, we have ψt ◦ ... ◦ ψ1 (b) ≡ 0 (mod q), then Lemma 3.4 gives us that [a, b] [a, y] for any y ∈ Z∗q and so the first part of the proof is complete. So, suppose there is no such t. Thus, ψ1 , ..., ψs are valid iterations in S(m/{2, p1 , ..., pk , q}). If Ψ = ψs ◦ ... ◦ ψ1 , then Ψ(a, b) = (a, y) for some fixed y ∈ Z∗q . For any b ∈ Z∗q , if m1 , ..., ms are the multiplicative representations of the division modulo q that occurs in each iteration (note that this is well defined since these values are coprime to q), then we have the following: y = Ψ(b) ≡ ms (m(...m2 (m(m1 (mb + 1)) + 1)...) + 1) s s s Y X Y ≡ ms mi b + ms−i mj = Ab + B i=1 i=1 j=i for some integers A and B where A is coprime to pk+1 (since each mi and m is coprime to pk+1 ). To go forth, it is required that B 6≡ 0 (mod q). If B ≡ 0 (mod q) then ψs can be redefined so that ψs (x) = mx+1 and ψs ◦ ψs−1 ◦ ... ◦ ψ1 (a) ≡ −m−1 , N and ψs+1 ◦ ψs ◦ ... ◦ ψ1 (a) ≡ a. If and ψs+1 defined so that ψs+1 (x) = mx+1 N Chapter 3. Uniqueness of the Principal Eigenvector 11 ψs+1 ◦ ... ◦ ψ1 (b) ≡ 0 (mod q), then Lemma 3.4 gives us that [a, b] [a, y] for any y ∈ Z∗q , as desired. Otherwise, let Ψ = ψs+1 ◦ ... ◦ ψ1 . We now have y = Ψ(b) ≡ A0 b + B 0 , where B0 = s+1 X ms+1−i s+1 Y s+1 s X Y ms+1−i mj + ms+1 mj = j=i i=1 = ms+1 s X ms+1−i i=1 s Y j=i mj + ms+1 = ms+1 m s X j=i i=1 ms−i i=1 s Y mj + ms+1 j=i = ms+1 mB + ms+1 . Since B ≡ 0 (mod q), this gives B 0 ≡ ms+1 6≡ 0 (mod q), as required. If used, A0 and B 0 will be referred to as A and B respectively. If A 6≡ 1 (mod q), then let d be the multiplicative order of A in Z∗q , otherwise let d = q. If there is some t ∈ {1, ..., s} and r ∈ {1, ..., d} such that ψt ◦ ... ◦ ψ1 Ψr (b) ≡ 0 (mod q) then Lemma 3.4 gives that [a, b] [a, y] for any y ∈ Z∗q as d desired. Suppose there is no such t and r, so Ψ is a valid sequence of iterations on [a, b]. Each application of Ψ gives Ψ(x) ≡ Ax + B. If A ≡ 1 (mod q) then Ψd (b) ≡ b + dB = b + qB ≡ b (mod q). For A 6≡ 1 (mod q) we have Ψd (b) = A(...(A(Ab + B) + B)... + B) = Ad b + B d−1 X Ai i=1 = Ad b + B Ad − 1 A−1 ≡ 1b + 0 = b (mod q). (3.1) In either case, Ψd (b) ≡ b (mod q). Ψd−1 satisfies that ΨΨd−1 (b) ≡ b (mod q); therefore AΨd−1 (b) + B ≡ b (mod q) and so Ψd−1 (b) ≡ b−B (mod q). A Let Φ = (2ψs ) ◦ ψs−1 ◦ ... ◦ ψ1 Ψd−2 . By Lemma 3.5, Φ is a valid sequence of iterations on b, and Φ(b) = 2Ψd−1 (b) ≡ 2 b−B A . Now consider Ψ ◦ Φ. If for some t ∈ {1, ..., s} we have ψt ◦ ... ◦ ψ1 ◦ Φ(b) ≡ 0 (mod q) then Lemma 3.4 gives us that [a, b] [a, y] for any y ∈ Z∗q and so the first part of the proof is complete, otherwise Ψ ◦ Φ is a valid sequence of iterations in S(m/{2, p2 , ..., pk , q}) and b − B Ψ ◦ Φ(b) = A 2 + B = 2b − B. A (3.2) So [a, b] [a, 2b − B]. Let Cb = {y ∈ Z∗q |[a, b] [a, y]}. In the following manipulations of the group Cb , if any sequence of iterations results in 0 modulo q then, as has been shown, this always results in the conclusion that [a, b] [a, y] for any y ∈ Z∗q , Chapter 3. Uniqueness of the Principal Eigenvector 12 or equivalently that Cb = Z∗q . Suppose that no sequence of iterations results in 0 modulo q. Equation (3.1) shows that [a, b] [a, b] through the iterations Ψd , so b ∈ 0 Cb . Also, Φ = (2ψs ) ◦ ψs−1 ◦ ... ◦ ψ1 Ψd−1 is a valid sequence of iterations in S(m/{2, p2 , ..., pk , q}) and Φ0 (b) = 2(Ψd (b)) = 2b; therefore 2b ∈ Cb by Lemma 3.2, and similarly we have that 2r b ∈ Cb for any integer r. Specifically, 2d−1 b ∈ Cb where d is the multiplicative order of 2 in Z∗q . Equation (3.2) gives that [a, 2d−1 b] [a, 2(2d−1 b) − B] = [a, b − B], and thus ∗ b−B ∈ Cb . There is some i ∈ Zq such that b ≡ Bi (mod q), and so by repeating this procedure we can conclude that {b, b − B, b − (i − 1)B} ⊂ Cb . Applying the procedure once more gives divisibility by q and so, along with Lemma 3.4 we have [a, b] [a, y] for any y ∈ Z∗q . Thus, in all cases, we have [a, b] [a, y] for any y ∈ Z∗q . ∗ ∗ Next, consider any [x, y] in ZN × Zq . Using the induction hypothesis, there is a sequence of iterations Ψ under S(m/{2, p1 , ..., pk }) that brings a to x (mod N ). If Ψ brings b to 0 (mod q) at some point then proposition 3.4 can be invoked to show [a, b] [x, y]. If at no point Ψ brings b to 0 (mod q) then Ψ is valid under S(m/{2, p1 , ..., pk , q}) and so [a, b] [x, Ψ(b)]. Using the results just established [x, Ψ(b)] [x, y] and thus by Lemma 3.2 [a, b] [x, y]. Propositions 3.1 and 3.6 combine to form: Theorem 3.7. Let P be the probability distribution matrix for the coprime residues of N = 2p2 · · · pk in the system S(m/{2, p2 , ..., pk }). Then P has a unique positive eigenvecter corresponding to λ = 1. When p1 6= 2, problems arise from the fact that division is not guaranteed to occur within each iteration. Suppose that m 6≡ 1 (mod pi ) for each i ∈ {1, ..., k}, and let di be the multiplicative order of m in Z∗pi . If ψ(x) = mx + 1 then ψ di (x) = md x + d−1 X j=0 m≡x+ md − 1 ≡ x (mod pi ). m−1 This suggests that the ψ operation will cause any x ∈ Zpi to run a cycle of length di . There are pid−1 cycles of length di , and one cycle of length 1 (the i −1 number m−1 will return to itself after ψ). Since there are more than 2 cycles in total, there are cycles that do not include 0, and any such cycle is smaller than Z∗pi . A cycle that does not include 0 (mod pi ) will never encounter divisibility by pi . In Zp1 × ... × Zpk choose [a1 , ..., ak ] so that ai is in such a cycle for each i and clearly divisibility by any of the primes will never occur. [a1 , ..., ak ] will be part of a cycle of length lcm(d1 , ..., dk ) < φ(p1 · · · pk ) = |Z∗p1 ···pk |, and therefore not all of Z∗p1 ···pk . Any number starting in this cycle can never leave the cycle, so there is an eigenvector whose only non-zero components correspond to elements in the cycle. Chapter 3. Uniqueness of the Principal Eigenvector 13 When m ≡ 1 (mod pi ) for some i ∈ {1, ..., k}, the proof used for p1 = 2 above falls apart where equation (3.2) becomes Ψ ◦ Φ(b) = A(pi b−B ) + B = pi b − (pi − 1)B. A Using the same methods it can be shown that pi b − (pi − 1)B ∈ Cb . If pi ≡ 1 (mod q) then there is no t such that b ≡ t(pi − 1)B (mod q), and so the proof cannot be continued as before. However, if pi 6≡ 1 (mod q) then there is such a t and the proof can be concluded similarly to when pi = 2. This results in the following generalization: Theorem 3.8. Let p1 , ..., pk be primes, and m ≡ 1 (mod pi ) for some i ∈ {1, ..., k}. Let P be the probability distribution matrix for the coprime residues of N = p1 · · · pk in the system S(m/{p1 , ..., pk }). If pi 6≡ 1 (mod pj ) for all j ∈ {1, ..., k} then P has a unique positive eigenvecter corresponding to λ = 1. 14 Chapter 4 The Effect of Increasing a Divisor on Expectation A brief investigation of Table 5.27 (Multiplicative Expectations for Systems), suggests that as more divisors are added the expectation tends to decrease but if a divisor is increased then the expectation tends to increase as well. Specifically, looking at the systems S(11/{2, 3, q}) (the right-hand side of the table), it appears that as q increases the expectation is generally increasing, but does not appear to surpass the expectation of S(11/{2, 3}). This observation leads to a prediction that the expectation E(S(m/{2, p1 , ..., pk , q}) should converge to E(S(m/{2, p1 , ..., pk })) as q → ∞. In fact, this is Theorem 4.16. The key to the proof of this theorem is to show that the probability of division by q tends to 0 as q tends to infinity, and thus has minimal effect on the residues modulo N after an iteration (in this case, N = 2p2 · · · pk ). The proof will proceed by comparing the principal eigenvector of the probability distribution matrix P (S) to that of a similar, but easily controlled matrix P 0 . Let ī be the notation for the residue representative of i in ZN . Also, let P̄ be the probability distribution matrix for Z∗N into itself within the system S(m/{2, p2 , ..., pk }) and let P be the probability distribution matrix for the residue set S0 = {x ∈ ZN q |x is coprime to N } into itself within the system S(m/{2, p1 , ..., pk , q}). If Q = qZ∗N , then note that S0 = Z∗N q ∪ Q. Although the principal eigenvector for P (S) (the probability distribution matrix for Z∗N q in S) is ultimately what we are trying to analyse, the next lemma will allow us to substitute this eigenvector for that of P . Lemma 4.1. If w ~ ∈ Rφ(N q) is the principal eigenvector for P (S) and ~u ∈ φ(N )q R is the principal eigenvector for P , then w ~ (a) = ~u(a) for a ∈ Z∗N q and ~u(a) = 0 for a ∈ Q. Proof. Division by q ensures that after an iteration, no resulting number can be divisible by q. This gives P(a,b) = 0 for any b ∈ S0 when a ∈ Q. So, since ~u is a principal eigenvector for P we have X X ~u(a) = (P ~u)(a) = P(a,b) ~u(b) = (0)~u(b) = 0. b∈S0 b∈S0 Chapter 4. Increasing Divisors. . . 15 If a, b ∈ Z∗N q , then P (S)(a,b) = P(a,b) . So, for a 6∈ Q, we then have ~u(a) = (P ~u)(a) = X P(a,b) ~u(b) = b∈S0 = X P(a,b) (0) + X X P(a,b) ~u(b) b∈Z∗ Nq b∈Q P (S)(a,b) ~u(b) = X P (S)(a,b) ~u(b) = P (S)~u (a) . b∈Z∗ Nq b∈Z∗ Nq b∈Q X P(a,b) ~u(b) + The only vector in Rφ(N q) that satisfies ~u(a) = P (S)~u w. ~ Thus, we have ~u = w. ~ (a) for all a ∈ Z∗N q is Using equation (2.3) we can write P as P = Tk+1 · · · T0 for the transitional matrices T0 , ..., Tk+1 . For convenience, let T = Tk+1 . Also, let P 0 = Tk · · · T0 . Specifically, P 0 is the probability distribution matrix for S0 into itself within the system S(m/{2, p1 , ..., pk }) (notice the omission of division by q). Also, P = T P 0. Finally, let A = {a ∈ Z∗N q |ma + 1 ≡ 0 (mod q)} ⊂ Z∗N q , so A is a subset of S0 . Lemma 4.2. |A| = |Q| = φ(N ). Proof. Q = qZ∗N , so |Q| = |Z∗N | = φ(N ) is trivial. A = {a ∈ Z∗N q |ma + 1 ≡ 0 (mod q)}. By the Chinese Remainder Theorem, in Z∗N q there is a unique solution to a ≡ 0 (mod q) and a ≡ b (mod N ) for each b ∈ Z∗N , thus there are |Z∗N | = φ(N ) solutions, and so |A| = φ(N ). The first part of the proof of the theorem will be to find a principal eigenvector for the matrix P 0 . Before we begin, two more lemmas will be useful: Lemma 4.3. For any a, b ∈ S0 , X 0 P(c,a) = P̄(b̄,ā) . c∈S0 |c≡b Proof. Recall from earlier that P 0 = Tk · · · T0 . Similar to Chapter 2, let I0 = S0 and Ii = {a ∈ ZN q |a coprimePto p1 , ..., pi−1 } for i ∈ {1, ..., k}. For any a ∈ Ii and b ∈ Ii+1 let Ti(b,a) = c∈Ii+1 |c≡b Ti(c,a) . First, it will be shown that Ti(b,a) = T̄i(b̄,ā) for all i ∈ {0, ..., k}. For i = 0, the result is simple. T0(ma+1,a) = 1 and T0(c,a) = 0 for all c 6≡ ma + 1 (mod N q). If b 6≡ ma + 1 (mod N ) then c 6≡ ma + 1 (mod N q) for any c ≡ b. Also, b 6≡ mā + 1 (mod N ), so T̄0(b̄,ā) = 0. We have T0(b,a) = X c∈Ii+1 |c≡b T0(c,a) = X c∈Ii+1 |c≡b 0 = 0 = T̄0(b̄,ā) . Chapter 4. Increasing Divisors. . . 16 If b ≡ ma + 1 (mod N ) then b0 ≡ ma + 1 (mod N q) for a unique b0 ∈ S0 such that b0 ≡ b. Also, b ≡ mā + 1 (mod N ), so T̄0(b̄,ā) = 1. We have X X T0(c,a) = T0(b0 ,a) + T0(b,a) = T0(c,a) c∈Ii+1 |c≡b,c6=b0 c∈Ii+1 |c≡b X =1+ 0 = 1 = T̄0(b̄,ā) . c∈Ii+1 |c≡b When i 6= 1, the result is more involved. For a ∈ Ii and b ∈ Ii+1 suppose T̄i(b̄,ā) = 0. So, bpsi 6≡ a (mod N ) for any s ∈ Z. Thus, for any c ≡ b we have that cpsi 6≡ a (mod N q) for any s ∈ Z and so Ti(b,a) = 0. Suppose then, that T̄i(b̄,ā) 6= 0. According to equation (2.2) we have T̄i(b̄,ā) = pr−t i pri −1 where r is the least positive integer such that apri ≡ a and t is the least positive integer such that bpti ≡ a. Suppose that s is the least positive integer such that apsi ≡ a (mod N q). There is some K ∈ Z+ such that s = Kr. For each j ∈ {0, ..., K − 1}, the Chinese Remainder Theorem gives a unique solution for cj ∈ Ii+1 with cj ≡ b such that cj pjr+t ≡ a (mod N q) (and no i solution for cj pni ≡ a (mod N q) where n cannot be written as n = jr + t for Kr−(jr+t) some j). Equation (2.2) then gives Ti(cj ,a) = c 6∈ {c0 , ..., cK−1 }. We have Ti(b,a) = X Ti(c,a) = = 1 pri Ti(cj ,a) = K−1 X pjr i = j=0 pKr i −1 K−1 X j=0 c∈Ii+1 |c≡b pi−t pKr − i K−1 X pi j=0 pi−t pKr − i 1 pri ( and Ti(c,a) = 0 for all Kr−(jr+t) pi pKr −1 i = K X pjr−t i Kr − 1 p i j=1 pir−t −1 pKr i ) = = T̄i(b̄,ā) . pri − 1 pri − 1 This concludes the first part of the proof of the lemma, that Ti(b,a) = T̄i(b̄,ā) for all i ∈ {0, ..., k}. It remains to show that multiplication of these matrices maintains this summation property (with appropriate index sets). That is, that 0 = P¯0 (b̄,ā) for all a, b ∈ S0 . P(b,a) Assume the property is held for Tj−1 · · · T0 , then for any a ∈ S0 and b ∈ Ij+1 we have X (Tj · · · T0 )(b,a) = (Tj · · · T0 )(c,a) c∈Ii+1 |c≡b = X c∈Ii+1 |c≡b = X d∈Ii = X d∈Ii X Tj(c,d) (Tj−1 · · · T0 )(d,a) X d∈Ii (Tj−1 · · · T0 )(d,a) c∈Ii+1 |c≡b (Tj−1 · · · T0 )(d,a) Tj(b,d) . Tj(c,d) Chapter 4. Increasing Divisors. . . 17 From the previous result, we have that Tj(b,d) = T̄j(b̄,d) ¯ . So, X (Tj · · · T0 )(b,a) = (Tj−1 · · · T0 )(d,a) T̄j(b̄,d) ¯ d∈Ii X = X (Tj−1 · · · T0 )(d,a) T̄j(b̄,d) ¯ c∈Ii ∩ZN d∈S0 |d≡c X = c∈Ii ∩ZN X = X T̄j(b̄,c) (Tj−1 · · · T0 )(d,a) d∈S0 |d≡c T̄j(b̄,c) (Tj−1 · · · T0 )(d,a) . c∈Ii ∩ZN The induction hypothesis now gives X (Tj · · · T0 )(b,a) = T̄j(b̄,c) (T̄j−1 · · · T̄0 )(c,ā) = (T̄j+1 · · · T̄0 )(b̄,ā) . c∈Ii ∩ZN P c∈S0 |c≡b 0 = P¯0 (b̄,ā) follows from the conclusion of the induction arguP(c,a) ment. Lemma 4.4. For any a, c ∈ S0 , X 0 P(c,b) = P̄(c̄,ā) . b∈S0 |b≡a 0 Proof. As per Section 2.2.1, if a ∈ A, then P(b,a) = 0 for any b 6∈ Q. Using Lemma 4.3 we have X X X 0 0 0 P̄(c̄,ā) = P(b,a) = P(b,a) + P(b,a) b∈S0 |b≡c = X b6∈Q|b≡c b∈Q|b≡c 0 P(b,a) + X (0) = b6∈Q|b≡c b∈Q|b≡c X 0 P(b,a) . b∈Q|b≡c According to the Chinese Remainder Theorem, there is a unique b ∈ S0 such 0 = P̄(c̄,ā) when c ∈ Q and a ∈ A. that b ≡ 0 (mod q) and b ≡ c, therefore P(c,a) Consider any c ∈ Q. Section 2.2.1 also tells us that if b 6∈ A then P 0 (c, b) = 0. This combined with the previous result gives X X X 0 0 0 P(c,b) = P(c,b) + P(c,b) b∈S0 |b≡a b6∈A|b≡a b∈A|b≡a = X 0 P(c,b) b∈A|b≡a + X b6∈A|b≡a 0= X b∈A|b≡a Again, there is a unique b so that b ∈ A and b ≡ a, so we get X 0 P(c,b) = P̄(c̄,ā) . b∈S0 |b≡a 0 P(c,b) Chapter 4. Increasing Divisors. . . 18 Consider c 6∈ Q, so c ∈ Z∗N q . For any b ∈ S0 there is a unique K ∈ ZN q such that Kc ≡ b (mod N q). Suppose c0 ≡ c, and let K be such that Kc0 ≡ ma + 1 (mod N q); there are two cases. Case 1: K ≡ 2r1 pr22 · · · prkk for some sets of integers {r1 , ..., rk } with 0 ≤ ri ≤ di (di is the multiplicative order of pi in Z∗N q ) and Case 2: there are no such r1 , ..., rk . For Case 2, the operations of S(m/{2, p2 , ..., pk }) cannot bring a to c0 and 0 0 0 0 therefore P(c 0 ,a) = 0. For Case 1, a can be brought to c and the value of P (c , a) 0 0 is determined only by the sets {r1 , ..., rk }. In both cases, P (c , a) depends only on K. Since c0 ≡ c, we have c ≡ c0 + dN (mod N q) for some integer d. Let 0 a ≡ a + KdN m−1 (mod N q). Then ma0 + 1 ≡ m(a + KdN m−1 ) + 1 ≡ ma + KdN + 1 ≡ Kc0 + KdN ≡ K(c0 + dN ) ≡ Kc (mod N q). Thus there is some a0 with P 0 (c, a0 ) = P 0 (c0 , a). This gives a bijection between the values of P 0 (c0 , a) and P 0 (c, a0 ) for c0 ≡ c and a0 ≡ a. This, along with Lemma 4.3 gives X X 0 0 P(c,b) = P(b,a) = P̄(ā,c̄) . b∈S0 |b≡a b∈S0 |b≡c ~ v Define the vector u~0 by u~0 (a) = (ā) q . Then we have the following proposition, which will be the first step in the proof of the theorem mentioned at the beginning of this chapter: Proposition 4.5. u~0 is a principal eigenvector for P 0 . Proof. Consider w = P 0 u~0 . For each b ∈ S0 we have X X X 0 0 (P 0 u~0 )(b) = P(b,a) P(b,a) u~0 (a) = u~0 (a) c∈Z∗ N a∈S0 |a≡c a∈S0 X = X c∈Z∗ N a∈S0 |a≡c = 1 X ~v(c) q ∗ c∈ZN X X ~v(ā) ~v(c) 0 = P(b,a) q q c∈Z∗ N a∈S0 |a≡c X 0 P(b,a) . 0 P(b,a) a∈S0 |a≡c Lemma 4.4 gives (P 0 u~0 )(b) = 1 X 1 1 X ~v(c) P̄(b̄,c̄) = ~v(c) P̄(b̄,c) = (P̄ ~v )(b̄) . q q q ∗ ∗ c∈ZN c∈ZN Since ~v is the principal eigenvector for P̄ , this simplifies to 1 (P 0 u~0 )(b) = ~v(b̄) = u~0 (b) . q Chapter 4. Increasing Divisors. . . 19 For all b ∈ S0 we have (P 0 u~0 )(b) = u~0 (b) , so u~0 is a principal eigenvector for P 0 . The next step of the proof of the theorem is to show that for any a ∈ Z∗N , the sum of the values of ~u(b) where b ≡ a converges to ~v(a) as q increases. This will be a result of the similarity between P and P 0 , and thus their eigenvectors. Several new notations and lemmas will prove useful for the upcoming proposition. ~ we will define the function D on w ~ so that D(w) ~ = P For any real vector w, | w ~ |, where I is the index set of w. ~ (i) i∈I Lemma 4.6. For any real vectors ~u, w ~ with index set I and K ∈ R, the following are true: i. D(K w) ~ = K · D(w); ~ ii. D(~u) − D(w) ~ ≤ D(~u + w) ~ ≤ D(~u) + D(w); ~ iii. If P is a non-negative matrix with index set I whose columns sum to 1, then D(P w) ~ ≤ D(w). ~ Proof. i. is trivial, and ii. is a straightforward result of the triangle inequality. The proof of iii. is as follows: XX X X X |P(i,j) w ~ (j) | D(P w) ~ = |(P w) ~ (i) | = P(i,j) w ~j ≤ i∈I = i∈I XX P(i,j) |w ~ (j) | = i∈I j∈I i∈I j∈I j∈I X j∈I |w ~ (j) | X P(i,j) = i∈I X |w ~ (j) |(1) = D(w). ~ j∈I For P and P 0 as defined earlier, let ∆ = P 0 − P . So ∆ = P − P 0 = T P 0 − P 0 = (T − I)P 0 (T − I) will have the form of ~0 for all columns with a 6∈ Q. For a, b ∈ Q and a 6= b, we have (T − I)(a,a) = −1 and (Tq − I)(a,b) = 0. For a ∈ Q and b 6∈ Q the values of (T − I) follow the probability distributions described in Section 2.2.1: if there is no integer r such that bq r ≡ a (mod N ) then (T − I)(b,a) = 0; if there is such an r, and d is the multiplicative order of q in Z∗N then by equation (2.2), d−r we have (T − I)(b,a) = qqd −1 , where r ∈ {1, ..., d}. The sum of each column is 0. P Lemma 4.7. If w ~ is a real vector with index set Z∗N q then a∈S0 (∆w) ~ (a) = 0. Proof. X (∆w) ~ (a) = a∈S0 X X ∆(a,b) w ~ (b) = a∈S0 b∈S0 = X X b∈S0 w ~ (b) X ∆(a,b) a∈S0 w ~ (b) (0) = 0. b∈S0 Lemma 4.8. If u~0 is the principal eigenvector for P 0 , then D(∆u~0 ) = 2q . Chapter 4. Increasing Divisors. . . 20 Proof. D(∆u~0 ) = D((T − I)P 0 u~0 ) = D((T − I)u~0 ) X X X = |((T − I)u~0 )(a) | = (T − I)(a,b) u~0 (b) a∈S0 = a∈S0 X X a∈S0 (T − I)(a,b) u~0 (b) + b∈S0 X (T − I)(a,b) u~0 b . b6∈Q b∈Q From the construction of (T − I), we have (T − I)(a,b) = 0 for b 6∈ Q, so D(∆u~0 ) = X X a∈S0 = (T − I)(a,b) u~0 (b) + (0)u~0 b b6∈Q b∈Q X X X (T − I)(a,b) u~0 (b) + a∈Q b∈Q X X (T − I)(a,b) u~0 (b) . (4.1) a∈S0 \Q b∈Q ~ v For all b ∈ Q we have u~0 (b) = (qb̄) > 0. As established earlier, if a ∈ Q, then (T − I)(a,b) ≤ 0 and if a 6∈ Q then (T − I)(a,b) ≥ 0. Combining this with Lemma 4.7, we have X X X X (T − I)(a,b) u~0 (b) = (T − I)(a,b) u~0 (b) . a∈Q b∈Q a∈S0 \Q b∈Q Continuing with equation (4.1) now gives D(∆u~0 ) = 2 X X (T − I)(a,b) u~0 (b) = 2 a∈Q b∈Q =2 X X a∈Q b=a =2 X X a∈Q b=a X X (T − I)(a,b) a∈Q b∈Q ~v(b̄) q ~v(b̄) ~v(b̄) X + (T − I)(a,b) (T − I)(a,b) q q b6=a (−1) ~v(b̄) + q X b6=a (0) X ~v(b̄) ~v(b̄) =2 q q a∈Q 2 2 2 X = ~v(b̄) = (1) = . q q q ∗ a∈ZN For a system S(m/{2, p2 , ..., pk }) with N = 2p2 · · · pk , and prime q coprime to N , if w ~ is a real vector with index set Z∗N q then define the real vector w ~¯ with P ∗ ∗ index set ZN so that for any a ∈ ZN we have w ~¯(a) = b∈S0 |b≡a w ~ (b) . We then have the following two results: Lemma 4.9. P 0w ~ = P̄ w. ~¯ Chapter 4. Increasing Divisors. . . 21 Proof. P 0w ~ (a) = X = X 0 P(b,c) w ~ (c) b∈S0 |b≡a c∈S0 b∈S0 |b≡a X X (P 0 w) ~ (b) = X w ~ (c) c∈S0 0 . P(b,c) b∈S0 |b≡a Lemma 4.3 and the definition of w ~ simplify this to: X X X w ~ (c) P̄(ā,c̄) P 0w ~ (a) = w ~ (c) P̄(ā,c̄) = d∈Z∗ N c∈S0 |c≡d c∈S0 X = X d∈Z∗ N c∈S0 |c≡d X = X w ~ (c) P̄(ā,d) = X P̄(ā,d) d∈Z∗ N w ~ (c) c∈S0 |c≡d P̄(ā,d) w ~¯(d) = (P̄ w) ~¯ (a) . d∈Z∗ N Lemma 4.10. D(w) ~¯ ≤ D(w). ~ Proof. D(w) ~¯ = X a∈Z∗ N ≤ X X a∈Z∗ N b∈S0 |b≡a |w ~¯(a) | = X X |w ~ (b) | = a∈Z∗ N b∈S0 |b≡a X w ~ (b) |w ~ (b) | = D(w). ~ b∈S0 The remaining three lemmas will allow us to conclude the proof of the next proposition. Lemma 4.11. If w ~ is a positive vector such that w ~ (a) ≤ (P w) ~ (a) < 1 q for all a ∈ Z∗N then 1 X P̄ā,b + φ(N ) . q ∗ b∈ZN Proof. X 1 1 X = P(a,c) + P(a,c) q q c∈S0 c∈S0 c∈A c6∈A X X X 1 1 (1) + P(a,c) = |A| + P(a,c) . ≤ q q (P w) ~ (a) = X P(a,c) w ~ (c) ≤ c∈A c6∈A X P(a,c) c6∈A Lemma 4.2 states that |A| = φ(N ). Also, if c 6∈ A, then division by q has 0 no effect on c after the “mx + 1” action and thus P(a,c) = P(a,c) for all a ∈ S0 . Chapter 4. Increasing Divisors. . . 22 Using this, and Theorem 4.4 we have 1 X X 1 0 0 (P w) ~ (a) = φ(N ) + P(a,c) ≤ φ(N ) + P(a,c) q q c∈S0 c6∈A X X X 1 1 0 = P̄(ā,b) = φ(N ) + P(a,c) φ(N ) + q q ∗ ∗ b∈ZN c∈S0 |c≡b b∈ZN Lemma 4.12. Let M be an n-by-n probability distribution matrix with unique principal eigenvector w ~ (where the sum of the entries is 1), and {w ~i }i∈N be a sequence of vectors in Rn (whose entries sum to 1) that satisfy Mw ~i = w ~i + ~i for some ~i where D(~ i ) → 0 as i → ∞. Then, w ~i → w. ~ Proof. Let ρ(v~1 , v~2 ) = D(v~1 − v~2 ) be a metric between two vectors in Rn (the properties of a metric have been confirmed in Lemma 4.6). Define the function F : Rn → R; F (w) ~ = D((M − I)w). ~ Continuity of F under this metric is obvious. Also, F (w ~i ) = D((M − I)w ~i ) = D(~ i ). Suppose that for some constant C there is a subsequence {w~ki }i∈N ⊂ {w ~i }i∈N such that ρ(w~ki , w) ~ > C for each i ∈ N. Let G be the compact set {~x ∈ [0, 1]n |D(~x) = 1}\{~x ∈ Rn |ρ(~x, w) ~ < C}. Clearly, w~ki ∈ G for each i ∈ N and so the sequence {F (w~ki )}i∈N = {D(~ i )}i∈N is contained in F (G) Since G is compact, the set F (G) is closed and thus contains all its limits [2, Chapter 6.2]. By the hypothesis, D(~ i ) → 0 and so 0 ∈ F (G). Since w ~ is a unique principal eigenvector, it is the only solution to F (w) ~ = 0, thus w ~ ∈G must be true. But, ρ(w, ~ w) ~ = 0 < C, so w ~ 6∈ G, a contradiction. There is no such C, and therefore w ~i → w. ~ Lemma 4.13. Let X = {xj }j∈N be a sequence in R+ and let Xi be either a finite set, or a sequence that converges to 0 for any i ∈ Z+ . If X ⊂ ∪i∈Z+ Xi and sup Xi → 0 as i → 0 then xj → 0 as j → ∞. Proof. For some c ∈ R, let c > 0. Since sup Xi → 0, there are only a finite number of indices i such that x ≥ c is possible for some x ∈ Xi . Each Xi is either finite or a sequence that converges to 0, so there is at most finitely many x ∈ Xi such that x ≥ c. Since a finite union of finite sets is finite, there is at most finitely many x ∈ ∪i∈Z+ Xi such that x ≥ c, and thus at most finitely many x ∈ X such that x ≥ c. There must be some M such that xj < c for all j > M and therefore xj → 0. A few more new notations need to be introduced. First, for any real vector + w ~ with index set I, let w ~ + be the vector such that w ~ (i) =w ~ (i) when w ~ (i) > 0 + and w ~ (i) = 0 when w ~ (i) ≤ 0 for all i ∈ {1, ..., n}. Also, let w ~ − ∈ Rn be the Chapter 4. Increasing Divisors. . . 23 − − vector such that w ~ (i) = −w ~ (i) when w ~ (i) < 0 and w ~ (i) = 0 when w ~ (i) ≥ 0 for all i ∈ {i, ..., n}. Basically, w ~ + contains the positive components of w ~ and w ~− contains the negative components. Finally, let ~u be the principal eigenvector for P , and let ~δ = ~u − u~0 (the error between our desired vector ~u and the established vector u~0 ). The goal of the following proposition is to show that as q → ∞ then ~δ+ → ~δ+ . Proposition 4.14. ~ū(a) → ~v(a) as q → ∞ for all a ∈ Z∗N . Proof. Since ~u is the principal eigenvector for P we have P ~u = ~u 0 ~ P u + P ~δ = u~0 + ~δ (P 0 + ∆)u~0 + P ~δ = u~0 + ~δ P 0 u~0 + ∆u~0 + P ~δ = u~0 + ~δ. Recall that u0 is the principal eigenvector for P 0 , so P 0 u~0 = u~0 . We now have u~0 + ∆u~0 + P ~δ = u~0 + ~δ ∆u~0 + P ~δ = ~δ P ~δ = ~δ − ∆u~0 . (4.2) Equation (4.2) can be broken into its positive and negative components; −(P ~δ)− + (P ~δ)+ = − (~δ − ∆u~0 )− + (~δ − ∆u~0 )+ (P ~δ)− = (~δ − ∆u~0 )− & (P ~δ)+ = (~δ − ∆u~0 )+ . (4.3) Let ~e = [min{(P δ~+ )(b) , (P δ~− )(b) }]b∈S0 (that is, ~e is the overlap in components between (P δ~+ ) and (P δ~− )). Then P ~δ− = (P ~δ)− +~e and P ~δ+ = (P ~δ)+ +~e. Also, (~δ − ∆u~0 )− = (~δ)− − w ~ for some w ~ with |w ~ (b) | < |(∆~u)(b) | for all b ∈ S0 (and clearly, D(w) ~ < D(∆~u)). The first half of equation (4.3) becomes P ~δ− = ~δ− + ~e − w ~ 0 − − ~ ~ (P + ∆)δ = δ + ~e − w ~ 0 ~− − P δ = ~δ + ~e − w ~ − ∆~δ− . (4.4) In Z∗N , this is becomes P 0~δ− = ~δ− + ~e¯ − w ~ − ∆~δ− , and so Lemma 4.9 gives P¯0~δ− = ~δ− + ~e¯ − w ~ − ∆~δ− ~ = ~δ− + β (4.5) Chapter 4. Increasing Divisors. . . 24 ~ = ~e¯ − w for β ~¯ − ∆~δ− . Now, according to Lemma 4.6 and equation (4.4) we have D(~δ− ) ≥ D(P ~δ− ) = D(~δ− + ~e − w) ~ = D(~δ− + ~e − w) ~ − − ≥ D(~δ + ~e) − D(w) ~ = D(~δ ) + D(~e) − D(w) ~ (the last equality is true since ~δ− and ~e are both positive vectors). This results in D(~e) ≤ D(w). ~ Therefore, by Lemma 4.8 and the previous establishment that D(w) ~ ≤ D(∆~u) we have 2 D(~e) ≤ D(∆~u) = . (4.6) q Consider D(∆~δ− ). Since ~u is non-negative, it must be true that for each a ∈ S0 , we have 0 ≤ ~ua = u~0 a + ~δa , and so ~δa ≥ −u~0 a = − ~vqā . So, for each a ∈ S0 we have 0 ≤ (~δ− )a ≤ ~vqā . Similar to the proof of Lemma 4.8, it is true that D(∆~δ− ) ≤ 2q . Lemma 4.10 then gives that D(∆~δ− ) ≤ 2q . Combining these results with Lemma 4.6 we get ~ ≤ D(~e¯) + D(w D(β) ~ − ) + D(∆~δ− ) ≤ 6 . q (4.7) Let Jq = D(~δ− ) (for each respective q). For all primes q we have that 0 ≤ Jq ≤ 1, so if Y = {q|q prime}\{2, p2 , ..., pk } then we can partition Y into 1 the sets Y0 = {q ∈ Y |Jq = 0} and Yi = {q ∈ Y | i+1 < Jq ≤ 1i } for each i ∈ N. For any i > 0, consider any set Yi such that Yi has an infinite number of elements. For each q ∈ Yi , from Lemma 4.6 and equation (4.7) we have that D 1 1 ~ ~ < (i + 1)D(β) ~ ≤ 6(i + 1) . D(β) β = Jq Jq q (4.8) For each q ∈ Yi , if equation (4.5) is divided by Jq , then along with Lemma 4.12 (we are able to apply this lemma because of Theorem 3.7) and equation (4.8) we have that J1q ~δ− → ~v (recall that ~v is the principal eigenvector for P̄ ) as q → ∞, or ~δ− → Jq ~v . Next, consider the positive components of ~δ. A result of the fact that the sum of the components of both ~u and u~0 is 1 is that D(δ~− ) = D(δ~+ ), and therefore for each q ∈ Yi we have D(δ~− ) = Jq . There is also some w ~ with D(w) ~ < D(∆~u) such that the positive counterpart to equation (4.4) is ~ − ∆~δ+ . P¯0~δ+ = ~δ+ + ~e¯ − w In order to show that ~δ+ → Jq ~v for each q ∈ Yi , all that remains is to show that D(∆~δ+ ) → 0 as q → ∞. First, it will be shown that for each a ∈ A it must be true that (~δ+ )(a) → 0, otherwise the value of ~e(b) will not converge for some b ∈ Z∗N (a contradiction). Chapter 4. Increasing Divisors. . . 25 As was proved in Chapter 3, ~v , the eigenvector for P̄ is a fixed non-negative vector. Since ~δ− → Jq ~v , Lemma 4.9 gives us that for all a ∈ Z∗N we have (P 0~δ− )(a) = (P¯0~δ− )(a) → Jq (P¯0~v )(a) = Jq ~v(a) . Because P = P 0 + ∆ and D(∆~δ− ) → 0 as q → ∞, for every a ∈ Z∗N we have (P ~δ− )(a) → (P 0~δ− )(a) . If L = min{~v(a) |a ∈ Z∗N } then for large enough q ∈ Yi and for all a ∈ Z∗N we have (P ~δ− )(a) > Jq ~v(a) L ≥ . 2 2i Let R = (~δ+ )(a) for any a ∈ A. From the definition of P and P 0 it is true that P δ~+ = T P 0 δ~+ . Recall from the proof of Lemma 4.4 that since a ∈ A we 0 = P̄(b̄,ā) for b ∈ Q. By the pigeonhole principle, since the φ(N ) have P(b,a) components in any column of P̄ sum to 1, there is some c ∈ Q such that 1 P̄(c̄,ā) ≥ φ(N ) . So (P 0 δ~+ )(c) = X X 0 P(c,b) (δ~+ )(b) ≥ 0 0 P(c,b) (δ~+ )(b) = P(c,a) (δ~+ )(a) b=a∈S0 b∈S0 = P̄(c̄,ā) R ≥ R . φ(N ) According to equation (2.2), if d is the multiplicative order of q in Z∗N then d−1 for b, c ∈ Z∗N q such that qb ≡ c (mod qN ) we have T(b,c) = qqd −1 ≥ 2q . So (P δ~+ )(b) = (T P 0 δ~+ )(b) = X T(b,a) (P 0 δ~+ )(a) a∈S0 X ≥ T(b,a) (P 0 δ~+ )(a) = T(b,c) (P 0 δ~+ )(c) a=c∈S0 ≥ 2R 1 2 R = . q φ(N ) φ(N ) q ~ v ) Recall that − (qb̄ ≤ −(~δ− )(b) ≤ 0. Obviously 0 < ~v(b̄) ≤ 1, so we have 0 ≤ (~δ− )(b) ≤ 1q . Applying this to Lemma 4.11 gives us that (P ~δ− )(b) ≤ P 1 P̄(b̄,a) ). For any b such that qb ≡ c (mod N q), the ratio of a∈Z∗ q (φ(N ) + N positive components of (P ~δ) over negative components is (P ~δ+ )(b) ≥ (P ~δ− )(b) 2R 1 φ(N ) q 1 q (φ(N ) + P a∈Z∗ N P̄(b̄,a) ) = 2R . P φ(N ) φ(N ) + a∈Z∗ P̄(b̄,a) N Chapter 4. Increasing Divisors. . . 26 For all such b we have ~e(b) = min{(P δ~+ )(b) , (P δ~− )(b) } n o 2R (P δ~− )(b) , (P δ~− )(b) P ≥ min φ(N ) φ(N ) + a∈Z∗ P̄(b̄,a) N 2R (P δ~− )(b) . P = φ(N ) φ(N ) + a∈Z∗ P̄(b̄,a) (4.9) N The set described by {b ∈ S0 |qb ≡ c (mod qN )} is the same as {b ∈ S0 |b ≡ L cq }. Recall that if q ∈ Yi is large enough then (P ~δ− )(a) > 2i for all a ∈ Z∗N . Specifically, (P ~δ− ) −1 > L . From this and equation (4.9), we have −1 (cq ~e¯(cq−1 ) = X ) 2i X ~e(b) ≥ b∈S0 |b≡cq −1 = = > = b∈S0 |b≡cq −1 φ(N ) φ(N ) + 2R P φ(N ) φ(N ) + 2R P φ(N ) φ(N ) + 2R P 2R (P ~δ− )(b) P φ(N ) φ(N ) + a∈Z∗ P̄(b̄,a) N X a∈Z∗ N a∈Z∗ N a∈Z∗ N P̄(cq−1 ,a) P̄(cq−1 ,a) P̄(cq−1 ,a) (P ~δ− )(b) b∈S0 |b≡cq −1 (P ~δ− )(cq−1 ) L 2i RL . P φ(N )i φ(N ) + a∈Z∗ P̄(cq−1 ,a) N Equation (4.6) stated that D(~e¯) → 0, and since D(~e¯) ≥ ~e¯(cq−1 ) , it must be P true that ~e¯(cq−1 ) → 0. We have i, L, φ(N ), and ( a∈Z∗ P̄(cq−1 ,a) ) all positive N constants, so for any a ∈ A it must be true that (~δ+ )(a) = R → 0 as q → ∞ in Yi . Now, given that (~δ+ )(a) = R → 0, we can look at D(∆~δ+ ). X X X D(∆~δ+ ) = |(∆~δ+ )(a) | = (∆~δ+ )(b) a∈Z∗ N ≤ X a∈Z∗ N X b∈S0 |b≡a (∆~δ+ )(b) = a∈Z∗ N b∈S0 |b≡a = X (T − I)P 0~δ+ X X (T − I)P 0~δ+ (b) a∈Z∗ N b∈S0 |b≡a (b) . (4.10) b∈S0 P 0 is a non-negative matrix, and ~δ+ is a non-negative vector, so P 0~δ+ is a non-negative vector as well. (T − I) has all non-positive entries in the rows corresponding to Q, and non-negative entries in the remaining rows. Thus (T − I)(P 0~δ+ ) will have non-positive entries in components corresponding to Q and non-negative entries elsewhere. Chapter 4. Increasing Divisors. . . 27 By Lemma 4.7, the sum of the entries in (T − I)P 0~δ+ = ∆~δ+ is 0. Thus, X X (T − I)P 0~δ+ (b) . (T − I)P 0~δ+ (b) = b6∈Q b∈Q So, by splitting S0 into Q and S0 \Q, equation (4.10) becomes D(∆~δ+ ) = X (T − I)P 0~δ+ (b) + X (T − I)P 0~δ+ =2 (b) (b) X X (T − I)(b,c) (P 0~δ+ )(c) b∈Q c∈S0 b∈Q =2 (T − I)P 0~δ+ b6∈Q b∈Q =2 X X X (T − I)(b,c) (P 0~δ+ )(c) + X (T − I)(b,c) (P 0~δ+ )(c) . c6∈Q b∈Q c∈Q Recall that (T − I)(b,c) = 0 for any c 6∈ Q. Also, (T − I)(b,b) = −1 and (T − I)(b,c) = 0 when b, c ∈ Q, so D(∆~δ+ ) = 2 X X (T − I)(b,c) (P 0~δ+ )(c) + =2 (T − I)(b,c) (P 0~δ+ )(c) = 2 b∈Q c∈Q =2 X X |(−1)(P 0~δ+ )(b) | b∈Q 0 ~+ (P δ )(b) = 2 b∈Q =2 (0)(P 0~δ+ )(c) c6∈Q b∈Q c∈Q X X X X X 0 ~δ+ P(b,d) (d) b∈Q d∈S0 XX b∈Q 0 ~δ+ P(b,d) (d) + X 0 ~δ+ . P(b,d) (d) d6∈A d∈A 0 Recall from the proof of Lemma 4.4 that P(b,d) = P̄(b̄,d) ¯ for b ∈ Q and d ∈ A, 0 and P(b,d) = 0 for b ∈ Q and d 6∈ A. So D(∆~δ+ ) = 2 XX b∈Q + P̄(b̄,d) δ(d) + ¯~ X XX + + (0)~δ(d) =2 P̄(b̄,d) δ(d) . ¯~ d6∈A d∈A b∈Q d∈A + It has already been shown that ~δ(d) → 0 for each d ∈ A. Since P̄(b̄,d) ¯ is fixed for all q, this is a finite sum of values that converge to 0, and thus D(∆~δ+ ) → 0. With this established, the proof for negative components can be used to show that ~δ+ → Jq ~v as well. Therefore, for each a ∈ Z∗N X X + − ~δ¯(a) = ~δ(a) = (~δ(a) − ~δ(a) ) b∈S0 |b≡a = X b∈S0 |b≡a b∈S0 |b≡a ~δ+ − (a) X ~δ− (a) b∈S0 |b≡a = ~δ+ (a) − ~δ− (a) → Jq ~v(a) − Jq ~v(a) = 0 Chapter 4. Increasing Divisors. . . 28 ¯ From the definition of ~δ, we have ~ū(a) → ~v(a) as q ∈ Yi → ∞. ¯ If Y is written as the increasing sequence {qj }j∈N then let xj = ~δ(a) corresponding to each qj and let X = {xj }j∈N . Also, let Xi = {xj |qj ∈ Yi } for each i ∈ Z+ . We can now apply Lemma 4.13 to conclude that as q → ∞ we have ~δ¯(a) → 0 for each a ∈ Z∗ . N Proposition 4.15. As q → ∞, the values α2q , ..., αkq of S(m/{2, p2 , ..., pk , q}) converge to α2 , ..., αk of S(m/{2, p2 , ..., pk }) and αk+1q → 0. Proof. From Lemma 4.1, we Pcan use the values of ~u for the principal eigenvector of P (S). Recall that αi = a∈Z∗ |pi divides ma+1 ~u(a) . Nq First, ~u(a)P → 0 as q → ∞. Since {a ∈ Z∗N q |pk+1 divides ma + 1} = A, we have αk+1 = a∈A ~u(a) . Lemma 4.2 states that |A| = φ(N ) (constant for all q) and each ~u(a) → 0. Thus αk+1 is a finite sum of numbers that converge to 0, and thus αk+1 converges to 0. Consider αi for i ∈ {2, ..., k}. Suppose ma + 1 ≡ 0 (mod pi ) for some ∗ a ∈ ZP N , and let b ≡ a. Clearly mb + 1 ≡ 0 (mod pi ) is true. So, we have αi = a∈Z∗ |pi divides ma+1 ~v(a) and N X X X αiq = ~u(b) = ~u(b) b∈Z∗ N q |pi divides mb+1 X = a∈Z∗ N |pi a∈Z∗ N |pi divides ma+1 b∈Z∗ N q |b≡a ¯(a) . ~u divides ma+1 ¯(a) → ~v(a) . Because αi is a sum of finitely many we have ~u For each a ∈ q things, we have αiq → αi Z∗N , This brings us to our conclusion: Theorem 4.16. If p2 , ..., pk , q are prime, and m is coprime to q, 2 and each of p2 , ..., pk then E(S(m/{2, p1 , ..., pk , q}) → E(S(m/{2, p1 , ..., pk })) as q → ∞. Proof. From equation (2.1) and using the previous proposition we have the following: pi k+1 m Y 1 αiq pi −1 E(S(m/{2, p1 , ..., pk , q}) = 4 i=2 pi k = k → q p q i (0) m Y 1 αi pi −1 1 q−1 4 i=2 pi q k = p i α m Y 1 αiq pi −1 1 k+1q q−1 4 i=2 pi q p i m Y 1 αi pi −1 4 i=2 pi = E(S(m/{2, p1 , ..., pk }) 29 Chapter 5 Evidence Supporting this Model 5.1 The E(S) = 1 threshold If the calculated expectations are accurate then any system with an expectation less than 1 should have the property that all sequences eventually result in a finite cycle, and any system with expectation greather than one should have the property that some sequences should diverge. Because of this, systems with expectations near the threshold of 1 are investigated in this chapter. Table 5.27 gives the calculated expectations of several systems. For simplicity, in each case 2 is used as p1 . The 5 systems with expectations closest to 1 from below (S(11/{2, 3, 47}), S(11/{2, 3, 53}), S(19/{2, 3, 5, 11}), S(11/{2, 3, 61}), S(23/{2, 3, 5, 7})) and the 5 systems with expectations closest to 1 from above (S(17/{2, 3, 5}), S(5/{2, 7}), S(9/{2, 5, 11}), S(11/{2, 3, 67}), S(11/{2, 3, 59})) are investigated regarding divergence. 500 randomly generated numbers (see Table 5.28) were selected, and tested as the initial term for sequences in each of the 10 systems. The sequences were determined until either some term had greater than 10,000 digits, or the remainder of the sequence was cyclic. Tables 5.1 through 5.6 give the results of these tests, where a sequence is considered “divergent” if it eventually reaches a number with greater than 10,000 digits (for these sequences, it is only assumed that the resulting sequences are in fact divergent, but it has not been proven). As expected, for those systems with expectation less than 1, no such sequence was found. In each block of numbers (the random numbers were seperated into five groups of 100, each group being 8-12 digits long) the highest number attained by any “non-divergent” sequence was recorded. For these sequences, the highest number attained is approximately 2,500 digits long and so it is reasonable to assume that those sequences that attain a number of 10,000 digits are in fact “divergent”. Tables 5.1 through 5.5 suggest the fairly intuitive notion that the closer the expection is to 1 from above, the less likely it is that a sequence will diverge (however a comparison of S(17/{2, 3, 5}) and S(5/{2, 7}) seems to contradict this, which could potentially be explained by the choice of smaller divisors having a more significant effect on smaller starting numbers). A second expected trend in the data is that the larger the starting number, the more likely the Chapter 5. Evidence Supporting this Model 30 sequence is to converge. A hypothesis could be made that as t0 → ∞, the probability that the sequence beginning with t0 diverges goes to 1. Digits 8 Table 5.1: Divergence in S(17/{2, 3, 5}) (E(S) = 1.0384) Divergent Sequences (ref no.) Tally Highest No. 1, 2, 6, 8, 11, 14, 20, 29, 31, 33, 38, 39, 40, 43, 55, 61, 70, 27 < 1.8 × 1055 73, 76, 77, 79, 81, 83, 85, 86, 98, 100 9 10 11 12 3, 9, 10, 21, 23, 25, 34, 39, 41, 45, 48, 51, 52, 65, 68, 69, 71, 72, 74, 79, 85, 86, 89, 95, 96 8, 9, 10, 12, 13, 14, 15, 21, 23, 40, 45, 48, 52, 55, 58, 60, 61, 64, 67, 68, 73, 78, 87, 88, 97, 99 1, 2, 3, 6, 15, 19, 21, 23, 25, 31, 36, 41, 42, 45, 46, 47, 52, 53, 54, 57, 58, 60, 61, 63, 64, 67, 68, 70, 71, 74, 77, 80, 82, 85, 89, 92, 93, 94, 97, 98, 99, 100 1, 4, 6, 15, 17, 22, 23, 24, 26, 29, 30, 32, 35, 38, 39, 42, 43, 44, 47, 51, 58, 59, 61, 67, 68, 69, 71, 73, 75, 76, 78, 79, 84, 85, 88, 89, 90, 91, 92, 95, 97 8-12 Digits 8 25 < 2.5 × 1055 26 < 1.2 × 1083 42 < 3.0 × 1080 41 < 2.4 × 1031 161 < 1.2 × 1083 Table 5.2: Divergence in S(5/{2, 7}) (E(S) = 1.0275) Divergent Sequences (ref no.) Tally Highest No. 1, 2, 4, 5, 6, 7, 8, 11, 12, 14, 15, 16, 18, 19, 22, 27, 28, 29, 64 < 1.1 × 1047 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 50, 51, 54, 55, 56, 57, 58, 60, 63, 64, 65, 69, 70, 71, 72, 73, 74, 75, 77, 78, 79, 81, 82, 83, 84, 87, 89, 91, 94, 97 9 10 11 12 8-12 7, 10, 13, 14, 15, 19, 20, 21, 23, 24, 27, 28, 31, 33, 35, 36, 38, 41, 44, 45, 47, 48, 53, 54, 55, 57, 63, 65, 66, 68, 70, 74, 75, 77, 78, 79, 82, 83, 86, 87, 90, 91, 93, 97, 98, 99, 100 2, 3, 5, 7, 8, 10, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 38, 39, 41, 44, 45, 46, 52, 53, 54, 57, 60, 61, 62, 63, 65, 67, 68, 69, 70, 71, 73, 74, 76, 77, 79, 80, 87, 90, 91, 93, 94, 95, 98, 99 1, 3, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 22, 23, 25, 26, 28, 29, 32, 33, 34, 35, 36, 39, 40, 44, 45, 46, 47, 51, 54, 55, 58, 59, 60, 61, 63, 64, 66, 67, 68, 71, 73, 74, 76, 78, 79, 80, 81, 82, 84, 87, 88, 89, 91, 94, 96, 97, 100 24, 50, 75, 99, 1, 2, 3, 5, 6, 7, 8, 12, 13, 15, 19, 21, 22, 25, 27, 28, 29, 30, 32, 33, 35, 36, 37, 38, 40, 42, 43, 44, 45, 46, 47, 49, 51, 52, 53, 55, 56, 57, 60, 62, 64, 66, 67, 68, 69, 72, 75, 76, 78, 82, 83, 84, 85, 86, 87, 89, 91, 95, 96, 97, 98, 100 47 < 1.3 × 1041 57 < 1.3 × 1041 65 < 2.9 × 1081 62 < 2.9 × 1081 295 < 2.9 × 1081 Chapter 5. Evidence Supporting this Model Digits 8 9 10 31 Table 5.3: Divergence in S(9/{2, 5, 11}) (E(S) = 1.0182) Divergent Sequences (ref no.) Tally Highest No. 18, 23, 25, 30, 54, 55, 59, 71, 88, 91, 93, 94 12 < 5.6 × 10111 14, 23, 25, 35, 36, 39, 43, 47, 52, 69, 78, 83, 85, 86, 88, 96 16 < 9.4 × 1077 7, 12, 13, 27, 28, 32, 33, 35, 39, 40, 43, 46, 49, 58, 72, 78, 21 < 3.1 × 1071 79, 81, 84, 90, 100 11 12 8-12 1, 13, 17, 19, 26, 49, 50, 52, 53, 54, 55, 59, 62, 70, 77, 81, 84, 88, 94, 96, 98, 99 1, 5, 22, 23, 24, 27, 31, 32, 35, 59, 61, 62, 70, 71, 72, 74, 77, 81, 83, 84, 85, 86, 94, 96 22 < 3.6 × 1082 24 < 6.0 × 10 95 < 5.6 × 10111 Digits 8 9 10 11 12 8-12 Table 5.4: Divergence in S(11/{2, 3, 67}) (E(S) = 1.0043) Divergent Sequences (ref no.) Tally Highest No. 3, 9, 55, 61, 63, 79, 82 7 < 4.4 × 10101 13, 36, 61, 63, 64 5 < 1.1 × 10483 4, 17, 36, 46, 93 5 < 8.5 × 10180 16, 25, 37, 47, 95 5 < 3.3 × 10173 8, 25, 26, 28, 54, 59, 81, 86, 100 9 < 3.6 × 10246 31 < 1.1 × 10483 Digits 8 9 10 11 12 8-12 Table 5.5: Divergence in S(11/{2, 3, 59}) (E(S) = 1.0015) Divergent Sequences (ref no.) Tally Highest No. 9, 11, 17, 82, 85 5 < 7.9 × 10841 39, 85 2 < 6.0 × 10220 14, 16 2 < 4.0 × 10242 12, 48 2 < 8.9 × 101103 36, 44, 63 3 < 5.8 × 102568 14 < 5.8 × 102568 Table 5.6: Highest Number Attained for Systems with Expectation less than 1 System Expectation Highest Number S(11/{2, 3, 47}) 0.9897 < 1.8 × 10266 S(11/{2, 3, 53}) 0.9931 < 1.3 × 10446 S(19/{2, 3, 5, 11}) 0.9957 < 8.4 × 10702 S(11/{2, 3, 61}) 0.9994 < 5.4 × 101572 S(23/{2, 3, 5, 7}) 0.9994 < 1.7 × 102523 Chapter 5. Evidence Supporting this Model 5.2 32 Occurrence of Divisors Further support for the proposed eigenvector model for systems can be found in analyzing the individual iterations of each sequence. The construction of the probability distribution matrix was dependent on the notion that, if a number n is divisible by p, then there is an equal probability that np ≡ a (mod N ) for any a such that ap ≡ n (mod N ). Tables 5.7 through 5.16 specifically deal with the likelihood of np being divisible by p again. Trials were run on the 500 randomly selected numbers from table 5.28 in each of the 10 systems. Each random number had the divisors factored out until the resulting number was coprime to each of the divisors and this resulting number was used as the starting point for each sequence. From there, the system would run until until either the sequence had reached a number less than 1000, or 10000 iterations had been performed1 . After each iteration, the highest number of divisions by each division that took place were tallied. The results in Tables 5.7 through 5.16 are the percentages for the combined tallies for all 500 starting points. 1 As stated earlier, if n is divisible by p, then there is a pk−1 probability that k n is divisible by p . Thus if n is divisible by p, then there is a 1 − p1 = p−1 p probability that n is divisible by p but not p2 , and so there is a p−1 probability k p that n is divisibly by pk , but not divisible by pk+1 . The expected percentages of tables 5.7 through 5.16 were calculated accordingly. With very few exceptions, the expected and actual percentages differ by less than five hundredths of a percentage point. It would appear as though the systems are behaving as expected in this regard. 1 1000 was chosen to be large enough to avoid the fixed patterns that would occur as the terms in sequences become smaller and repetitive, but small enough to still significant room for sequences to decrease from their initial starting point. Chapter 5. Evidence Supporting this Model Table Div 21 22 23 24 25 26 27 28 29 210 211 212 213 5.7: Expected and exp % Act % 50.000 49.945 25.000 25.023 12.500 12.498 6.250 6.257 3.125 3.152 1.563 1.567 .781 .774 .391 .397 .195 .189 .098 .098 .049 .050 .024 .024 .012 .013 Actual Occurrences of Division Div exp % Act % Div 14 2 .006 .005 31 15 2 .003 .003 32 16 2 .002 .002 33 ≥17 2 .002 .002 34 35 1 5 20.542 20.539 36 2 5 4.108 4.127 37 3 5 .822 .805 38 4 5 .164 .164 39 5 5 .033 .034 310 56 .007 .007 3≥11 7 5 .001 .002 5≥8 .000 .000 33 in S(17/{2, 3, 5}) exp % Act % 36.123 36.128 12.041 11.999 4.014 4.034 1.338 1.347 .446 .457 .149 .143 .050 .051 .017 .018 .006 .005 .002 .002 .001 .001 Table 5.8: Expected and Actual Occurrences of Division in S(5/{2, 7}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.978 210 .098 .096 71 7.390 7.388 2 11 2 25.000 24.974 2 .049 .049 72 1.056 1.052 23 12.500 12.530 212 .024 .024 73 .151 .153 4 13 4 2 6.250 6.239 2 .012 .012 7 .022 .025 25 3.125 3.119 214 .006 .006 75 .003 .004 26 1.563 1.576 215 .003 .004 76 .000 .001 27 .781 .795 216 .002 .002 7≥7 .000 .000 28 .391 .397 217 .001 .001 29 .195 .197 2≥18 .001 .000 Chapter 5. Evidence Supporting this Model Table Div 21 22 23 24 25 26 27 28 29 210 211 212 213 Table Div 21 22 23 24 25 26 27 28 29 210 211 212 5.9: Expected and exp % Act % 50.000 49.930 25.000 25.050 12.500 12.515 6.250 6.230 3.125 3.141 1.563 1.565 .781 .782 .391 .394 .195 .198 .098 .095 .049 .051 .024 .023 .012 .011 34 Actual Occurrences of Division in S(9/{2, 5, 11}) Div exp % Act % Div exp % Act % 214 .006 .006 51 23.689 23.717 215 .003 .005 52 4.738 4.726 216 .002 .001 53 .948 .933 17 4 2 .001 .002 5 .190 .187 2≥18 .001 .000 55 .038 .040 56 .008 .007 111 6.8061 6.8049 57 .002 .003 2 11 .6183 .6201 58 .000 .001 113 .0562 .0561 5≥9 .000 .000 114 .0051 .0049 115 .0005 .0006 116 .0000 .0001 11≥7 .0000 .0000 5.10: Expected and Actual exp % Act % Div 50.000 49.937 213 25.000 25.050 214 12.500 12.554 215 6.250 6.227 216 3.125 3.125 2≥17 1.563 1.536 .781 .790 .391 .394 671 .195 .203 672 .098 .089 673 .049 .051 674 .024 .024 67≥5 Occurrences of Division in S(11/{2, 3, 67}) exp % Act % Div exp % Act % .012 .012 31 38.103 38.159 .006 .005 32 12.701 12.681 .003 .002 33 4.234 4.215 4 .002 .001 3 1.411 1.405 .002 .000 35 .470 .462 36 .157 .152 37 .052 .058 1.5233 1.5224 38 .017 .017 .0227 .0238 39 .006 .004 .0003 .0001 310 .002 .002 .0000 .0001 311 .001 .001 .0000 .0000 3≥12 .000 .000 Chapter 5. Evidence Supporting this Model 35 Table Div 21 22 23 24 25 26 27 28 29 210 211 212 5.11: Expected and Actual exp % Act % Div 50.000 49.984 213 25.000 25.035 214 12.500 12.457 215 6.250 6.276 216 3.125 3.130 217 1.563 1.564 218 .781 .784 2≥19 .391 .388 .195 .188 591 .098 .098 592 .049 .049 593 .024 .022 59≥4 Occurrences of Division in S(11/{2, 3, 59}) exp % Act % Div exp % Act % .012 .012 31 37.947 37.978 .006 .006 32 12.649 12.591 .003 .003 33 4.216 4.241 .002 .002 34 1.405 1.409 .001 .001 35 .468 .467 .000 .001 36 .156 .155 7 .000 .000 3 .052 .052 38 .017 .017 1.7016 1.7006 39 .006 .007 .0288 .0300 310 .002 .002 .0005 .0004 311 .001 .001 .0000 .0000 3≥12 .000 .000 Table Div 21 22 23 24 25 26 27 28 29 210 211 212 5.12: Expected and Actual exp % Act % Div 50.000 50.102 213 25.000 24.961 214 12.500 12.481 215 6.250 6.179 216 3.125 3.133 2≥17 1.563 1.568 .781 .777 .391 .393 .195 .205 471 .098 .102 472 .049 .051 473 .024 .020 47≥4 Occurrences of Division in S(11/{2, 3, 47}) exp % Act % Div exp % Act % .012 .014 31 37.981 37.981 .006 .006 32 12.660 12.639 .003 .005 33 4.220 4.216 .002 .002 34 1.407 1.429 .002 .000 35 .469 .474 36 .156 .158 37 .052 .050 38 .017 .016 2.1551 2.1576 39 .006 .005 .0459 .0436 310 .002 .002 .0010 .0007 311 .001 .001 .0000 .0000 3≥12 .000 .000 Chapter 5. Evidence Supporting this Model Table Div 21 22 23 24 25 26 27 28 29 210 211 212 5.13: Expected and Actual exp % Act % Div 50.000 49.969 213 25.000 25.136 214 12.500 12.333 215 6.250 6.241 216 3.125 3.170 217 1.563 1.594 218 .781 .772 2≥19 .391 .387 .196 .201 531 .098 .102 532 .049 .051 533 .024 .023 53≥4 36 Occurrences of Division in S(11/{2, 3, 53}) exp % Act % Div exp % Act % .012 .010 31 37.848 37.830 2 .006 .005 3 12.616 12.689 .003 .003 33 4.205 4.176 .002 .002 34 1.402 1.380 .001 .001 35 .467 .476 .000 .001 36 .156 .140 .000 .000 37 .052 .050 38 .017 .022 1.9847 1.9880 39 .006 .007 .0374 .0337 310 .002 .001 .0007 .0012 311 .001 .001 .0000 .0000 3≥12 .000 .000 Table 5.14: Expected and Actual Occurrences of Division in S(19/{2, 3, 5, 11}) Div exp % Act % Div exp % Act % Div exp % Act % 1 1 7 2 50.000 49.992 3 30.759 30.789 3 .042 .039 22 25.000 24.951 32 10.253 10.214 38 .014 .018 23 12.500 12.508 33 3.418 3.451 39 .005 .004 24 6.250 6.265 34 1.139 1.105 310 .002 .001 25 3.125 3.167 35 0.380 .391 311 .001 .001 26 1.563 1.557 36 .127 .124 3≥12 .000 .000 27 .781 .797 28 .391 .383 29 .195 .186 210 .098 .094 211 .049 .048 51 20.841 20.814 212 .024 .024 52 4.168 4.185 13 3 2 .012 .016 5 .834 .837 111 9.6997 9.6987 14 4 2 .006 .006 5 .167 .172 112 .8818 .8873 215 .003 .003 55 .033 .036 113 .0802 .0757 216 .002 .002 56 .007 .005 114 .0073 .0067 217 .001 .001 57 .001 .001 115 .0007 .0012 2≥18 .001 .000 5≥8 .000 .000 11≥6 .0001 .0000 Chapter 5. Evidence Supporting this Model Table Div 21 22 23 24 25 26 27 28 29 210 211 212 5.15: Expected and Actual exp % Act % Div 50.000 49.933 213 25.000 25.045 214 12.500 12.471 215 6.250 6.287 216 3.125 3.105 217 1.563 1.583 218 .781 .799 2≥19 .391 .387 .195 .192 611 .098 .098 612 .049 .049 613 .024 .025 61≥4 37 Occurrences of Division in S(11/{2, 3, 61}) exp % Act % Div exp % Act % .012 .014 31 38.104 38.037 .006 .006 32 12.701 12.741 .003 .003 33 4.234 4.243 4 .002 .001 3 1.411 1.424 .001 .001 35 .470 .466 .000 .001 36 .157 .167 .000 .000 37 .052 .053 38 .017 .016 1.6488 1.6454 39 .006 .006 .0270 .0299 310 .002 .001 .0004 .0009 311 .001 .001 .0000 .0000 3≥12 .000 .000 Table 5.16: Expected and Actual Occurrences of Division in S(23/{2, 3, 5, 7}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.962 31 36.069 36.044 36 .148 .145 2 2 2 25.000 24.943 3 12.023 12.058 37 .049 .047 23 12.500 12.556 33 4.008 3.994 38 .016 .016 24 6.250 6.224 34 1.336 1.350 39 .005 .004 5 5 10 2 3.125 3.125 3 .445 .441 3 .002 .003 26 1.563 1.613 3≥11 .001 .001 27 .781 .788 28 .391 .387 29 .195 .206 210 .098 .099 51 18.251 18.280 11 2 .049 .051 52 3.650 3.639 71 14.976 14.974 12 3 2 .024 .025 5 .730 .721 72 2.139 2.141 213 .012 .011 54 .146 .137 73 .306 .308 214 .006 .005 55 .029 .029 74 .044 .042 215 .003 .003 56 .006 .006 75 .006 .005 216 .002 .002 57 .001 .001 76 .001 .001 2≥17 .002 .001 5≥8 .000 .000 7≥7 .000 .000 Chapter 5. Evidence Supporting this Model 5.3 38 Occurrence of Residues Finally, the principal eigenvectors were tested. The 500 randomly generated numbers were run through the same test as the previous section; however this time the residues modulo p1 · · · pk were tallied for each system S(m/{p1 , ..., pk }) instead of the number of divisions. Again, the expected and actual percentages are significantly close, suggesting that this model is likely appropriate. Table 5.17: Expected and Actual Occurrences for Residues in S(17/{2, 3, 5}) Res exp % Act % Res exp % Act % Res exp % Act % 1 14.996 14.987 13 9.729 9.717 23 13.223 13.204 7 13.443 13.444 17 12.170 12.233 29 10.326 10.347 11 10.035 10.029 19 16.077 16.038 Table Res 1 3 5.18: Expected and Actual Occurrences for exp % Act % Res exp % Act % 15.827 15.859 5 22.302 22.302 20.144 20.161 9 10.072 10.119 Residues in S(5/{2, 7}) Res exp % Act % 11 8.633 8.622 13 23.022 22.937 Table 5.19: Expected and Actual Occurrences for Residues in S(9/{2, 5, 11}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 3.1752 3.2983 41 2.6844 3.1351 79 2.2477 2.4142 3 1.4996 1.5039 43 1.7844 1.7128 81 3.0690 3.3052 7 3.2776 3.1746 47 2.9884 2.5763 83 1.8999 2.0900 9 2.3722 2.3134 49 2.4331 2.3252 87 3.1017 2.9552 13 1.9014 2.0048 51 3.2383 2.7756 89 2.2533 2.4266 17 1.6037 1.7094 53 2.0513 1.7959 91 2.5029 2.5397 19 2.3570 2.2552 57 3.3360 3.3049 93 1.9134 1.7985 21 2.9355 2.8396 59 2.5073 2.5026 97 3.1807 3.1757 23 2.0112 2.0395 61 2.0955 2.1248 101 3.2459 3.3120 27 2.9892 3.0151 63 2.0107 1.9487 103 1.7976 2.0036 29 1.9870 2.1065 67 3.3156 3.1878 107 2.5435 3.2354 31 3.3825 3.1551 69 2.4423 2.3248 109 2.2143 1.9358 37 3.2932 3.3147 71 3.3004 3.1290 39 1.4078 1.5635 73 1.6490 1.6709 Chapter 5. Evidence Supporting this Model 39 Table 5.20: Expected and Actual Occurrences for Residues in S(11/{2, 3, 67}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 71 73 77 79 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127 131 133 .89434 .65235 .80489 .66428 .87939 .50668 .88445 .66127 .86505 .59798 .86711 .65568 .87850 .61865 .88814 .60347 .86410 .65960 .88440 .66339 .89108 .66420 .66614 .88229 .66579 .88114 .65700 .86535 .64419 .87420 .59605 .88015 .67094 .87131 .65883 .81164 .65308 .85433 .66065 .83340 .65396 .88423 .66510 .87147 .89504 .67151 .82873 .66560 .87387 .49614 .88041 .66477 .86588 .58341 .85478 .65948 .88477 .62658 .88445 .60365 .86723 .66031 .87750 .66031 .89556 .66134 .65543 .89473 .66197 .87844 .64765 .87812 .65273 .86235 .58175 .85727 .66062 .87273 .65190 .80237 .65387 .86194 .66041 .81804 .65937 .89006 .66861 .87013 137 139 143 145 149 151 155 157 161 163 167 169 173 175 179 181 185 187 191 193 197 199 203 205 209 211 215 217 221 223 227 229 233 235 239 241 245 247 251 253 257 259 263 265 .66349 .86943 .65949 .88150 .66535 .89777 .62136 .88422 .64157 .83219 .65243 .89082 .66468 .84589 .66711 .86018 .66895 .88290 .65016 .88622 .66636 .89491 .66874 .89127 .66624 .88166 .63207 .88753 .65710 .88593 .65784 .81514 .65283 .56219 .65930 .86912 .66278 .88132 .66373 .86790 .52430 .85575 .64991 .89305 .65522 .87190 .64962 .88726 .67670 .89255 .62409 .86723 .63312 .83547 .64536 .88539 .67618 .85924 .68282 .86194 .66466 .86640 .65761 .90324 .65584 .89660 .66944 .89037 .66456 .88788 .64526 .90521 .67390 .90241 .65875 .82375 .64121 .56722 .64827 .86515 .65169 .87325 .67369 .88259 .53163 .85197 .66300 .88279 269 271 275 277 281 283 287 289 293 295 299 301 305 307 311 313 317 319 323 325 329 331 337 341 343 347 349 353 355 359 361 365 367 371 373 377 379 383 385 389 391 395 397 401 .66690 .86653 .65165 .88191 .64011 .88454 .66643 .87889 .66143 .80519 .65546 .87917 .62242 .88686 .66326 .89497 .65427 .88891 .66337 .85847 .66448 .88193 .88827 .65602 .88734 .65686 .85983 .64646 .85817 .66703 .86705 .66703 .86705 .64325 .88627 .67256 .85502 .64025 .88507 .64402 .74841 .66028 .87980 .65814 .66736 .86993 .67473 .87366 .64910 .88643 .67649 .87729 .65709 .79241 .64630 .87345 .62793 .89867 .66477 .91662 .66134 .90033 .65896 .85488 .66103 .89711 .88435 .65148 .87086 .65190 .87252 .65916 .87273 .63675 .85384 .66352 .86816 .63644 .90469 .66176 .83651 .63395 .86910 .63395 .73679 .66549 .89317 .65283 Chapter 5. Evidence Supporting this Model 40 Table 5.21: Expected and Actual Occurrences for Residues in S(11/{2, 3, 59}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 .9972 .9837 121 .9582 .9631 239 .7057 .6956 5 .6822 36670 125 .7648 .7780 241 .9372 .9255 7 1.0080 1.0111 127 .9652 .9539 245 .7425 .7446 11 .7638 .7643 131 .7283 .7343 247 1.0043 1.0134 13 1.0015 1.0040 133 1.0137 .9926 251 .5760 .5769 17 .7610 .7607 137 .7623 .7662 253 .9769 .9791 19 1.0062 1.0321 139 1.0050 1.0148 257 .7495 .7637 23 .7144 .7153 143 .7595 .7417 259 .9590 .9585 25 1.0158 1.0129 145 1.0060 .9934 263 .7584 .7544 29 .7380 .7540 149 .7397 .7377 265 .9899 .9899 31 .9865 .9867 151 1.0129 1.0133 269 .7634 .7716 35 .7647 .7729 155 .7638 .7516 271 1.0188 1.0047 37 .8884 .9026 157 1.0146 1.0149 275 .7603 .7680 41 .7425 .7653 161 .7639 .7635 277 .9786 .9825 43 1.0111 .9906 163 .9978 .9962 281 .7458 .7599 47 .7518 .7630 167 .7585 .7598 283 1.0035 .9984 49 .9964 1.0067 169 1.0105 1.0100 287 .76291 .7655 53 .7623 .7569 173 .7631 .7475 289 1.0002 1.0070 55 1.0159 1.0290 175 1.0084 1.0307 293 .7663 .7766 61 .9955 1.0273 179 .7292 .7266 299 .7626 .7587 65 .6964 .6985 181 .9816 .9797 301 .9164 .9054 67 1.0066 1.0041 185 .7603 .7506 305 .6007 .5922 71 .6992 .7083 187 .8417 .8508 307 1.0013 1.0127 73 1.0157 1.0102 191 .7471 .7478 311 .7365 .7381 77 .7442 .7452 193 .9948 .9934 313 1.0009 .9864 79 1.0129 1.0055 197 .7586 .7552 317 .7544 .7515 83 .7528 .7493 199 1.0054 1.0107 319 .8821 .8723 85 .9351 .9322 203 .7655 .7717 323 .7673 .7636 89 .7601 .7601 205 .9742 .9761 325 .6327 .6103 91 .9639 .9702 209 .7282 .7243 329 .7450 .7426 95 .7546 .7558 211 1.0068 1.0145 331 .9891 .9908 97 1.0034 .9874 215 .7373 .7236 335 .7564 .7416 101 .7719 .7696 217 .9950 .9911 337 1.0066 1.0248 103 .9988 .9934 221 .7547 .7493 341 .7698 .7599 107 .6788 .6842 223 1.0201 1.0126 343 .9840 .9948 109 .9957 1.0084 227 .7487 .7712 347 .7579 .7593 113 .7388 .7527 229 1.0072 1.0114 349 .9950 .9921 115 1.0106 .9948 233 .7544 .7560 353 .7627 .7587 119 .7545 .7358 235 .9749 .9570 Chapter 5. Evidence Supporting this Model 41 Table 5.22: Expected and Actual Occurrences for Residues in S(11/{2, 3, 47}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 1.2577 1.2195 97 1.2810 1.2720 191 .9099 .9344 5 .8982 .8843 101 .9369 .9274 193 1.2006 1.2150 7 1.2362 1.2503 103 1.2695 1.2702 197 .9596 .9444 11 .9621 .9498 107 .9415 .9274 199 1.2713 1.2686 13 1.2329 1.2557 109 1.2746 1.2657 203 .9692 .9530 17 .9440 .9779 113 .9594 .9286 205 1.2084 1.2229 19 1.2801 1.2695 115 1.1846 1.2110 209 .9784 .9876 23 .9202 .9087 119 .9623 9595 211 1.2202 1.2166 25 1.2377 1.2309 121 1.2492 1.2455 215 .9299 .9227 29 .9690 .9424 125 .9554 .9462 217 1.2878 1.2675 31 1.2762 1.2810 127 1.2326 1.2361 221 .9427 .9378 35 .9396 .9401 131 .9617 .9690 223 1.2412 1.2329 37 1.2756 1.2976 133 1.2558 1.2743 227 .9576 .9575 41 .9546 .9575 137 .9535 .9774 229 1.2653 1.2743 43 1.1582 1.1603 139 1.2850 1.2738 233 .9069 .9207 49 1.2280 1.2261 143 .9227 .9161 239 .8611 .8397 53 .9591 .9849 145 1.1845 1.1879 241 1.1569 1.1680 55 1.0566 1.0568 149 .7509 .7717 245 .9733 .9541 59 .7274 .7323 151 1.2884 1.3043 247 1.2593 1.2478 61 1.2763 1.2578 155 .9473 .9378 251 .9650 .9729 65 .9665 .9618 157 1.2637 1.2734 253 1.2706 1.2862 67 1.2793 1.2593 161 .9700 .9740 257 .9721 .9582 71 .9527 .9383 163 1.2935 1.3197 259 .7876 .7902 73 1.2358 1.2507 167 .9312 .9130 263 .9667 .9769 77 .9459 .9161 169 1.2510 1.2569 265 1.2681 1.2731 79 1.2631 1.2327 173 .9185 .9360 269 .8513 .8693 83 .9491 .9537 175 1.2129 1.1917 271 1.2861 1.2808 85 1.2886 1.3172 179 .9806 .9582 275 .9436 .9523 89 .9683 .9394 181 1.2739 1.3113 277 1.2872 1.2912 91 1.2828 1.2903 185 .9668 .9772 281 .9713 .9616 95 .9471 .9274 187 1.2029 1.1922 Chapter 5. Evidence Supporting this Model 42 Table 5.23: Expected and Actual Occurrences for Residues in S(11/{2, 3, 53}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 1.0946 1.1174 109 1.0640 1.0573 215 .7910 .7956 5 .8529 .8816 113 .8436 .8667 217 1.1089 1.0867 7 1.1185 1.1534 115 .9241 .9284 221 .6670 .6662 11 .8355 .8211 119 .8550 .8582 223 1.1237 1.1283 13 1.1357 1.1318 121 1.1157 1.1136 227 .8508 .8472 17 .8516 .8456 125 .8486 .8454 229 1.1009 1.1046 19 1.1329 1.1311 127 1.1129 1.1216 233 .8320 .8351 23 .8441 .8465 131 .8043 .8084 235 1.1228 1.1260 25 1.1286 1.1075 133 .6929 .6772 239 .8333 .8491 29 .8294 .8801 137 .7497 .7567 241 1.0947 1.1152 31 1.0438 1.0401 139 1.1183 1.1271 245 .8478 .8445 35 .8337 .8199 143 .8489 .8202 247 1.0201 1.0295 37 1.1215 1.1306 145 1.1086 1.1205 251 .8569 .8825 41 .8306 .7975 149 .8526 .8607 253 1.1158 1.1134 43 1.1261 1.1603 151 1.1294 1.1134 257 .8491 .8402 47 .8502 .8218 155 .8516 .8413 259 1.1247 1.0953 49 1.1212 1.1170 157 1.1293 1.1130 263 .8545 .8570 55 1.1198 1.1117 161 .8363 .8524 269 .8353 .8453 59 .8320 .8143 163 1.0980 1.1236 271 1.1271 1.1016 61 1.1082 1.1036 167 .8455 .8376 275 .8025 .7779 65 .8655 .8993 169 1.1263 1.1181 277 1.0889 1.0719 67 1.1012 1.0636 173 .8349 .8211 281 .8075 .8093 71 .8478 .8646 175 1.1017 1.0782 283 1.1253 1.1326 73 1.0295 1.0278 179 .8611 .8758 287 .8429 .8429 77 .8547 .8884 181 1.0938 1.0988 289 1.1419 1.1352 79 1.1241 1.1530 185 .8431 .8441 293 .8085 .8198 83 .8375 .8436 187 1.0906 1.0683 295 1.1175 1.0864 85 1.0343 1.0502 191 .7842 .7713 299 .8455 .8582 89 .8582 .8532 193 1.1220 1.1248 301 1.1328 1.0962 91 1.1268 1.1455 197 .8559 .8589 305 .6380 .6320 95 .8167 .8278 199 1.1330 1.1597 307 1.0832 1.0934 97 1.0949 1.0629 203 .8039 .8205 311 .8256 .8198 101 .8569 .8805 205 1.1001 1.0901 313 1.1226 1.0828 103 1.0301 1.0241 209 .8418 .8395 317 .8208 .8120 107 .8295 .8248 211 1.0999 1.1111 Chapter 5. Evidence Supporting this Model 43 Table 5.24: Expected and Actual Occurrences for Residues in S(19/{2, 3, 5, 11}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 1.5251 1.4997 109 1.5668 1.5525 227 1.1739 1.1979 7 1.6422 1.6384 113 1.0030 .9936 229 1.6233 1.6136 13 .7413 .7301 119 1.0259 1.0419 233 1.1724 1.1852 17 1.1798 1.1703 127 .8169 .8051 239 1.0265 1.0535 19 1.5230 1.5448 131 1.1150 1.1323 241 1.5259 1.5230 23 1.3653 1.3835 133 1.0562 1.0482 247 1.5016 1.5078 29 1.0450 1.0311 137 1.3575 1.3470 251 1.2450 1.2504 31 1.6470 1.6345 139 1.3946 1.3785 257 1.3202 1.3203 37 1.6261 1.6497 149 .9985 1.0008 259 1.0662 1.0378 41 1.0905 1.0830 151 1.3710 1.3828 263 1.1982 1.1869 43 1.0200 1.0258 157 1.6138 1.6155 269 1.1376 1.1222 47 1.0847 1.1025 161 1.1712 1.1794 271 1.4354 1.4590 49 1.5560 1.5725 163 1.0558 1.0628 277 1.5000 1.4720 53 1.2980 1.2816 167 1.1470 1.1443 281 1.1423 1.1554 59 1.0816 1.1030 169 1.5699 1.5795 283 .9934 .9854 61 .8192 .8198 173 1.2794 1.2787 287 1.1773 1.2025 67 1.6027 1.6011 179 1.0872 1.0499 289 1.4086 1.4186 71 1.2476 1.2513 181 1.5894 1.5910 293 1.2922 1.2963 73 .8493 .8383 191 1.0842 1.0785 299 .8782 .8683 79 1.3377 1.3088 193 .9760 .9888 301 1.6598 1.6470 83 1.1997 1.1999 197 1.1586 1.1547 307 1.6163 1.5946 89 .9370 .9446 199 1.4372 1.4350 311 .84457 .8671 91 1.5101 1.5271 203 1.3630 1.3657 313 1.0320 1.0335 97 1.7656 1.7836 211 1.6323 1.6182 317 1.2354 1.2561 101 1.2105 1.1790 217 1.3051 1.3018 323 1.2721 1.2792 103 1.0030 1.0119 221 1.1679 1.1729 329 .9366 .9229 107 1.2888 1.2968 223 1.0452 1.0313 Chapter 5. Evidence Supporting this Model 44 Table 5.25: Expected and Actual Occurrences for Residues in S(11/{2, 3, 61}) Res Exp % Act % Res Exp % Act % Res Exp % Act % .9826 .9937 125 .7308 .7254 245 .7317 .7276 1 5 .7237 .7121 127 .9818 .9862 247 .9784 .9968 7 .9542 .9494 131 .7260 .7034 251 .7168 .7243 11 .7254 .7154 133 .9618 .9602 253 .9528 .9746 13 .9677 .9762 137 .7329 .7452 257 .7140 .7162 17 .6608 .6545 139 .9245 .9125 259 .9727 .9662 19 .9388 .9385 143 .7381 .7342 263 .7161 .7106 23 .7344 .7300 145 .8928 .8650 265 .9593 .9724 25 .9759 .9920 149 .7244 .7394 269 .7344 .7245 29 .7292 .7127 151 .9758 .9779 271 .9760 1.0096 31 .6115 .5945 155 .7362 .7383 275 .7309 .7317 35 .7179 .7288 157 .9731 .9613 277 .9436 .9489 37 .8944 .8904 161 .7091 .7204 281 .7280 .7553 41 .7263 .7346 163 .9840 .9817 283 .9417 .9301 43 .9641 .9649 167 .7339 .7461 287 .7156 .7158 47 .7093 .7003 169 .9703 .9799 289 .9764 .9802 49 .9800 1.0015 173 .5745 .5619 293 .6917 .6877 53 .7083 .7123 175 .9603 .9580 295 .8164 .8072 55 .9635 .9761 179 .6662 .6885 299 .7326 .7267 59 .6982 .6916 181 .9488 .9523 301 .9095 .8853 65 .7343 .7399 185 .7417 .7398 307 .9708 .9771 67 .9892 .9634 187 .9841 .9889 311 .7362 .7437 71 .7238 .7040 191 .7355 .7315 313 .9820 1.0148 73 .9730 .9758 193 .9539 .9519 317 .7353 .7445 77 .7266 .7217 197 .7172 .7171 319 .9684 .9707 79 .9604 .9431 199 .9814 .9914 323 .7357 .7548 83 .7204 .7191 203 .6841 .6890 325 .9538 .9480 85 .9787 1.0075 205 .9738 .9697 329 .7244 .7282 89 .6958 .6963 209 .7053 .7119 331 .9400 .9426 91 .9720 .9782 211 .9411 .9115 335 .7301 .7373 95 .7251 .7388 215 .7292 .7342 337 .9660 .9566 97 .9796 .9701 217 .9406 .9344 341 .7241 .7284 101 .7138 .7047 221 .7264 .7208 343 .9771 .9439 103 .9906 .9798 223 .8846 .9012 347 .6929 .6767 107 .5523 .5420 227 .7351 .7334 349 .9735 .9664 109 .9619 .9686 229 .9801 .9868 353 .7293 .7105 113 .7176 .7344 233 .7189 .7309 355 .9716 .9632 115 .9660 .9620 235 .9521 .9690 359 .7326 .7159 119 .7196 .7086 239 .6563 .6535 361 .9014 .8888 121 .9688 .9902 241 .9735 .9637 365 .7200 .7102 Chapter 5. Evidence Supporting this Model Table 5.26: Expected and Actual Occurrences for Residues Res Exp % Act % Res Exp % Act % Res 1 2.6144 2.6120 71 2.0251 2.0468 143 11 1.8404 1.8959 73 1.9797 1.9974 149 13 1.4270 1.4446 79 2.6497 2.6495 151 17 2.1123 2.0861 83 1.9523 1.9461 157 19 2.8056 2.8401 89 1.6456 1.6431 163 23 1.7093 1.6731 97 1.9812 1.9930 167 29 1.9745 2.0122 101 1.6172 1.5967 169 31 2.4670 2.4563 103 1.6948 1.6729 173 37 2.6621 2.6591 107 1.9392 1.9278 179 41 1.9652 1.9917 109 1.9463 1.9764 181 43 1.6622 1.6195 113 2.3006 2.3239 187 47 1.9446 1.9675 121 2.5091 2.5156 191 53 2.1960 2.1828 127 2.5957 2.5888 193 59 1.8105 1.8280 131 1.7385 1.7363 197 61 2.7395 2.7299 137 2.1670 2.1428 199 67 1.8310 1.8356 139 2.3462 2.3467 209 45 in S(23/{2, 3, 5, 7}) Exp % Act % 2.2849 2.2957 1.8478 1.8283 1.6125 1.5920 2.5821 2.5809 1.8009 1.8054 1.9100 1.9241 2.5721 2.5208 1.9537 1.9523 1.7728 1.7516 2.5073 2.4962 2.6786 2.6429 1.4267 1.4160 1.9014 1.8981 2.2110 2.2192 2.6250 2.6314 1.4635 1.5067 Chapter 5. Evidence Supporting this Model 5.4 46 Other Data Table 5.27: Multiplicative Expectations for Exp. System Exp. S(3/{2}) 0.75 S(7/{2, 3}) 0.9052 S(7/{2, 5}) 0.9642 S(5/{2}) 1.25 S(7/{2, 11, 13}) 1.1155 S(5/{2, 3}) 0.4875 S(7/{2, 11, 17}) 1.1711 S(5/{2, 7}) 1.0275 S(5/{2, 7, 11}) 0.7546 S(9/{2, 5, 11}) 1.0182 S(5/{2, 7, 13}) 0.8419 S(5/{2, 7, 17}) 0.8161 S(13/{2, 3, 5}) 1.0845 S(5/{2, 7, 19}) 0.8433 S(5/{2, 7, 23}) 0.8672 S(17/{2, 3, 5}) 1.0384 S(5/{2, 7, 29}) 0.9104 S(5/{2, 7, 31}) 0.8889 S(19/{2, 3, 5, 7}) 0.9592 S(5/{2, 11}) 0.9263 S(19/{2, 3, 5, 11}) 0.9957 S(5/{2, 11, 13}) 0.7688 S(19/{2, 3, 5, 13}) 1.0727 S(5/{2, 11, 17}) 0.7528 S(5/{2, 11, 19}) 0.7728 S(23/{2, 3, 5, 7}) 0.9994 System Table 5.28: Ref # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 8 Digits 43949058 57237679 56764175 15883987 84600232 95132796 44637620 36107037 20607915 47522486 14922351 61780436 62449056 56403365 49054505 79209560 58557997 22870850 90377252 63530478 76253611 36965090 some Systems System S(11/{2, 3}) S(11/{2, 3, 17}) S(11/{2, 3, 19}) S(11/{2, 3, 23}) S(11/{2, 3, 29}) S(11/{2, 3, 31}) S(11/{2, 3, 37}) S(11/{2, 3, 41}) S(11/{2, 3, 43}) S(11/{2, 3, 47}) S(11/{2, 3, 53}) S(11/{2, 3, 59}) S(11/{2, 3, 61}) S(11/{2, 3, 67}) Exp. 1.0724 0.9190 0.9031 0.9386 0.9550 0.9560 0.9655 0.9764 0.9784 0.9897 0.9931 1.0015 0.9994 1.0043 Random Numbers Used in Trials 9 Digits 133751076 586158240 467287522 153610815 879850007 319106125 155540012 225500149 168378689 868172695 532668526 505135326 437262560 235838395 996998889 554958197 301029038 190777717 915637919 750994542 801327918 632834019 10 Digits 5840371500 8010929594 6491108036 5112460519 3816384844 5144164697 9463631539 8732145756 7106418225 9415955883 1581869302 5161255391 6244301281 1809094426 9451185402 8412421905 4427838553 2275731771 1020544909 5777998714 9067798189 4427077306 11 Digits 12 Digits 73715876729 712999543523 65700862943 245330984447 32424170465 376587456075 25235196453 641902908204 27988963610 374651966999 44344539876 406449767634 17412421905 850409669815 95818212663 902454155507 53421525586 434796455572 83497475450 772869014214 72877304839 440895669155 52427536557 839457647004 59407854984 212155351554 64966684858 942468887962 75976255360 522605526665 32385044556 960696306908 68760991782 164544616043 21770990285 260846663823 71942394930 727488467546 96646091147 232783285421 88606118334 119182685523 43489062233 996485642968 Continued on next page Chapter 5. Evidence Supporting this Model Ref # 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 Table 8 Digits 69871636 86951880 12831035 43751076 93505056 63610815 94888397 65540012 78378689 59739450 40015342 95293656 12482142 78827104 11620667 89601089 62305013 76811310 43506413 20331551 65166217 96533896 40239278 69709832 86458215 98112183 59257126 92600807 92648824 37869455 48519847 53671261 40222947 87594039 74140492 97387056 31312821 82387746 60986366 75703401 27464042 56002467 59620331 24429582 20640797 61601423 65885530 18479921 16862945 63853750 32920424 31255973 51898294 78386625 59816001 5.28 – continued from previous page 9 Digits 10 Digits 11 Digits 12 Digits 830798472 6205175372 19949508400 936386069679 869381295 8221384230 82466529986 197309133939 310675943 3039073006 27820308836 702222289407 724983095 1746745227 52924197337 796005861184 686128038 4747053250 52184753306 375130015257 604386587 1640439652 14832623175 962790603924 751006053 9564458969 94884659950 814721677141 182648824 8825014938 16402031176 792355458282 262087183 5832623175 98749509928 392167296340 675390759 7402031176 36310525699 459387387685 680542173 3850164008 58147481356 525549978857 998599952 9809907465 87529384201 633990756471 801311587 9746448575 70286056127 702882754492 177594039 2755486969 46115225337 502854435326 298358220 4468319344 59211688700 113642900126 455822512 8326244625 55043765555 718873478963 523966005 9602039667 47828057712 233400028636 172387746 7253613363 52961778035 444829638290 150986366 4323948758 42830562320 167499645464 434138857 7759224824 33433482547 480076868136 466604856 4765644424 82043425494 340110681519 654334954 4471087299 16759224824 965025968658 871925675 9666272892 99664990344 796074080969 280220195 8820451619 47830825667 239049672077 686491243 7790157226 87385749628 185248995821 517082766 1678852156 35000320803 642977065094 558538714 4477783405 26922489097 670667848839 108479921 6227996711 41837160257 782887092972 760382807 9192069084 16790157226 879083730166 106862945 8939108714 96578198076 938945695809 153853750 8640307487 73401152795 409422465404 224776206 8280969794 53938185730 550355304119 257138152 8214771064 30657652589 998424235844 523909157 2685003584 40015471722 896000531765 760224790 3411870849 54377527460 286536289525 678769206 7031029662 75712276810 784306233136 705257537 2515103006 22943051994 805459503577 552469185 7841126466 17939108714 723335325513 461477542 2530490810 57051442205 259302577763 953606850 2696117849 34820176671 572240858908 381084412 8417214051 44305877875 307359064348 949586749 6963861911 94751725183 801595835584 159524752 7168077974 85934247800 582397680149 231172352 9000141896 80404480320 453009746412 847231251 7959393264 29591740033 602558523846 915190201 3027039028 23778547388 123159642540 100096362 3275654012 93869421791 443196548673 116935512 9214457779 80234579742 198729629455 750771551 3161184684 80249967546 133109574076 764526952 7217327664 39914302785 420494988756 162176315 3595154464 57907948208 975851612875 571873640 7436198272 28875987033 559645047754 891350242 1147391738 20253357838 515410977136 605373287 2559873971 44048322494 330171922316 570051117 8213482157 67707685526 946351270862 Continued on next page 47 Chapter 5. Evidence Supporting this Model Ref # 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 Table 8 Digits 15243879 58300482 22648956 54280381 69524752 86142611 19883833 10096362 26935512 57983973 72176315 79220456 26214538 77397933 83728243 94404206 71080953 72361065 98069338 59443377 20146328 19912499 60152951 5.28 – continued from previous page 9 Digits 10 Digits 11 Digits 576381427 5488496564 69539749448 338325266 3835191639 46386777396 429516409 4220971953 20051167073 162361065 1571213604 29455523196 885646024 2214072539 21665563720 456504794 8740009824 76595608988 686314289 7989562509 89707157378 110146328 1034763086 46520923052 223154542 3293225236 20576246183 512565683 7179026992 38117398376 358368043 4274574484 50577066032 821241591 5468789396 91518159752 102025624 2086437636 44507130106 411526687 7462942210 60920595976 393054814 8828028661 83207973300 356061060 6591305713 30015060823 969610764 6359464643 81940448689 881563360 3336703164 44930951972 249125755 9107722004 61463846750 282240337 6771746857 40474318427 623149147 1142887412 17740009824 406855912 1699530444 57577745160 892862344 9063216615 61574370638 48 12 Digits 167168041201 672503985973 316743634717 198560622730 776680397324 810831734671 903731560158 442365266447 430390789287 108175679917 463510107747 969052139615 674081019884 639703917065 573607925886 695464058943 797628332934 597366716315 213095867233 837491010327 888789117562 152573214076 606458752129 49 Bibliography [1] Robert G. Gallager, Discrete Stochastic Processes, Kluwer Academic Publishers, Norwell, Massachusetts, 3rd ed., 1996. [2] Steven G. Krantz, Real Analysis and Foundations, Chapman & Hall, 2nd ed., 2004. [3] J. C. Lagarias, The 3x+1 Problem and its Generalizations, the American Mathematics Monthly 92 (1985), no. 1, 3–23. [4] G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modelling, PH Distributions, ASA SIAM, 1st ed., 1999. [5] Toms Oliveira e Silva, (January 19, 2009). 3x+1 conjecture verification results. Retrieved July 14, 2009 from http://www.ieeta.pt/ tos/3x+1.html.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Collatz-type problems with multiple divisors
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Collatz-type problems with multiple divisors Gunn, Keira 2009
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Collatz-type problems with multiple divisors |
Creator |
Gunn, Keira |
Publisher | University of British Columbia |
Date Issued | 2009 |
Description | The Collatz Conjecture hypothesizes that if a sequence of integers beginning with any positive integer t₀ is recursively defined so that t_j₊₁ = (t_j)/2 when t_j is even and t_j₊₁ = 3(t_j)+1 when t_j is odd, then there will be some j in the set of natural numbers such that t_j = 1. I propose a similar family of problems (which I call systems) involving a set of prime divisors {p₁,...,p_k} and a multiplier m, where the sequence is recursively defined so that t_j₊₁ = (t_j)/(p₁) if t_j is divisible by p₁, t_(j₊₁) = (t_j)/(p₂) if t_j is divisible by p₂ but not p₁, t_(j+1) = (t_j)/(p₃) if t_j is divisible by p₃ but not p₁ or p₂ etc., and if t_j is not divisible by any of the primes, then t_(j₊₁) = m(t_j)₊₁. Assuming the residues of the terms of these sequences behave randomly modulo p₁...p_k, I propose a multiplicative expectation and data to suggest that this is a reasonable model for these systems. If the expectation is less than 1, as in the case of the Collatz problem, then I hypothesize that any sequence will eventually result in some finite cycle. As well, if my model for these systems is accurate, then I prove that the inclusion of an increasing prime q to a fixed set of prime divisors will result in an effect that gradually diminishes for the multiplicative expectation of the system. |
Extent | 453927 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-08-31 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0067665 |
URI | http://hdl.handle.net/2429/12614 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2009-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2009_fall_gunn_keira.pdf [ 443.29kB ]
- Metadata
- JSON: 24-1.0067665.json
- JSON-LD: 24-1.0067665-ld.json
- RDF/XML (Pretty): 24-1.0067665-rdf.xml
- RDF/JSON: 24-1.0067665-rdf.json
- Turtle: 24-1.0067665-turtle.txt
- N-Triples: 24-1.0067665-rdf-ntriples.txt
- Original Record: 24-1.0067665-source.json
- Full Text
- 24-1.0067665-fulltext.txt
- Citation
- 24-1.0067665.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0067665/manifest