Science, Faculty of
Mathematics, Department of
DSpace
UBCV
Simpson, Reginald M.
Doctor of Philosophy - PhD
University of British Columbia
For any cyclic group ℤ, this work studies the number of copies that appear in the invariant factor decomposition of the multiplicative group (ℤ/mℤ)⁢ˣ, denoted ℑ(m; d). The work proves the existence of a sequence of singleton and doubleton sets {fᵢ}ᵢ∞₌₁, a “universal profile” such that the natural density of numbers m where ℑ(m; d) > 0 is 1 for d in the singleton sets, 1/2 for d in the doubleton sets, and 0 for all d not found in the sets. The “universal profile” of sets is fully characterized, and can be explicitly computed based on the description given in this work, and has the property that for d₁ ∈ f ᵢ and d₂ ∈ fⱼ with i < j, d₁ divides d₂. For all d ∈ ℕ, we further determine Erdős-Kac type laws for the limiting distributions of ℑ(m; d) under appropriate scaling. These laws do not always follow the standard Erdős-Kac pattern of having normal limiting distributions, and mathematical descriptions of these non-normal distributions is given. Asymptotic formulas for the expectations of ℑ(m; d) are determined using these laws.
THE DISTRIBUTION OF THE INVARIANT FACTORSOF MULTIPLICATIVE GROUPSbyReginald M. SimpsonA THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THEREQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)May 2025© Reginald M. Simpson, 2025The following individuals certify that they have read, and recommend to the Faculty of Graduateand Postdoctoral Studies for acceptance, the dissertation entitled:The distribution of the invariant factors of multiplicative groupssubmitted by Reginald M. Simpson in partial fulfilment of the requirements forthe degree of Doctor of Philosophyin MathematicsExamining Committee:Greg Martin, Professor, Mathematics, UBCSupervisorJulia Gordon, Professor, Mathematics, UBCSupervisory Committee MemberMichael Bennett, Professor, Mathematics, UBCSupervisory Committee MemberNicholas Harvey, Professor, Computer Science, UBCUniversity ExaminerBrian Wetton, Professor, Mathematics, UBCUniversity ExaminerPaul Pollack, Professor, Mathematics, University of GeorgiaExternal ExamineriiAbstractFor any cyclic group Zd, this work studies the number of copies that appear in the invariantfactor decomposition of the multiplicative group (Z/mZ)×, denoted I(m; d). The work proves theexistence of a sequence of singleton and doubleton sets {fi}∞i=1, a “universal profile” such that thenatural density of numbers m where I(m; d) > 0 is 1 for d in the singleton sets, 1/2 for d inthe doubleton sets, and 0 for all d not found in the sets. The “universal profile” of sets is fullycharacterized, and can be explicitly computed based on the description given in this work, and hasthe property that for d1 ∈ fi and d2 ∈ fj with i < j, d1 divides d2.For all d ∈ N, we further determine Erdo˝s-Kac type laws for the limiting distributions of I(m; d)under appropriate scaling. These laws do not always follow the standard Erdo˝s-Kac pattern of hav-ing normal limiting distributions, and mathematical descriptions of these non-normal distributionsis given. Asymptotic formulas for the expectations of I(m; d) are determined using these laws.iiiLay SummaryThis work proves several original mathematical facts which formally describe the statistical distri-bution of algebraic structures which arise from the multiplication of whole numbers. A statisticallyuniversal pattern (that is, exceptions occur almost never) that arises from these structures is provento exist and is characterized.ivPrefaceThis is the original, unpublished work of the author, Reginald M. Simpson. The idea for the workwas developed in collaboration with Greg Martin, as was Lemma 2.6, but the work is otherwisethe independent work of the author. No Generative Artificial Intelligence tools were used in theprocess of researching or writing this work.A joint paper with Greg Martin based in part on this work is in preparation.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 The Universal Profile of the Invariant Factors of (Z/nZ)×. . . . . . . . . . . . . . . . . . . 11.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Limiting Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 Overview of the Proofs of the Results . . . . . . . . . . . . . . . . . . . . . . . . . . 152 From the Invariant Factors of (Z/nZ)× to Additive Functions . . . . . . . . . . . . . . . . 182.1 Relation Between Invariant Factors and Additive Functions Under General Assump-tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.2 Properties of the Universal Factor Order Sets . . . . . . . . . . . . . . . . . . . . . . 252.3 Invariant Factors of y-Typical Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 273 From Additive Functions to Probability Distributions . . . . . . . . . . . . . . . . . . . . 313.1 Concepts from Kubilius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Sums of Reciprocals of Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.3 Application of Kubilius to the Relevent Additive Functions . . . . . . . . . . . . . . 444 Probability and y-Typicality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.1 Background and Technical Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Proof of Proposition 1.26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575 Probability Distributions of the Invariant Factors . . . . . . . . . . . . . . . . . . . . . . . 605.1 Lemmas for Classifying the Distributions . . . . . . . . . . . . . . . . . . . . . . . . 605.2 φ-Sequences and Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . 66vi5.3 Proofs of Theorems 1.15 to 1.24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736 Implications of Theorems 1.15 to 1.24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 836.1 Proof of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 836.2 Individual Invariant Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846.3 Proofs of Theorems 1.8 to 1.14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897 Counting Subgroups of (Z/nZ)× . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97A Consolidated Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99B Technical Proofs Using Bertrand’s Postulate . . . . . . . . . . . . . . . . . . . . . . . . . . 103C Proofs of Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106D Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108viiList of Tables2.1 Classification of phi Subsequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26viiiAcknowledgementsI would like to thank my advisor, Greg Martin, for suggesting this topic.ixChapter 1The Universal Profile of theInvariant Factors of (Z/nZ)×.For any n ∈ N, one can study its multiplicative group (Z/nZ)×. The properties of this group aredeeply connected to many different aspects of number theory in a variety of ways. Many arithmeticfunctions can be defined in terms of this group, such as Euler’s totient function φ(n) (defined as theorder of the multiplicative group of n), the Carmichael-Lambda function λ(n) (the maximum orderof the elements of the multiplicative group of n), and the Dirichlet characters χ(n) (arithmetic liftsof the irreducible representations of the multiplicative group of n).As a finite abelian group, the multiplicative group of n can be uniquely decomposed into a directproduct of cyclic groups Zd1× . . .×ZdN for some finite N with orders d1, . . . , dN such that d1 | . . . |dN . This decomposition is called the invariant factor decomposition of the multiplicative group.Of particular note, dN , the order of the largest cyclic group in the invariant factor decompositionof n is equal to λ(n), the value of the Carmicael-Lambda function at n.In this article, we shall demonstrate that the invariant factors of (Z/nZ)× are, on a set of naturaldensity one, restricted in the orders they can have. These restricted orders are defined by a specificsequence of sets {fn}∞n=1, which we shall call in this work the sequence of universal factor ordersets.These sets have either one or two elements. The first ten such sets are as follows, with thetwo-element sets in brackets and the singletons without brackets:{fn}∞n=1 = 2, (4, 6), 12, (24, 60), 120, (360, 840), 2520, 5040, 55440, 720720, . . .Before getting to the definition of the sequence of these sets, note that in the above pattern,each successive universal factor order set contains only elements which are divisible by the previous1set. This pattern will hold, and this means the first even positive number not found in any fn is 8.The simplest result that shall be proven about these universal factor order sets is the following:Theorem 1.1. Let d1(n), . . . , dN (n) be the first N distinct invariant factors of (Z/nZ)× for anynatural number n with at least N such distinct orders of invariant factors. The natural density ofn ∈ N such that (Z/nZ)× has at least N distinct orders of invariant factors with di(n) ∈ fi fori = 1, . . . , N is 1. The natural density of n ∈ N such that (Z/nZ)× has less than N distinct ordersof invariant factors or di(n) ̸∈ fi for some i = 1, . . . , N is 0.Even when only applied to the pattern shown above, this statement has some fairly concreteimplications. The natural density of positive integers whose multiplicative group has at least oneinvariant factor of order 720720 is one, while the natural density of positive integers whose multi-plicative group has at least one invariant factor of order 8 is zero.Much more can be said than the above theorem. In particular, expectations for the countingfunction for the number of invariant factors of order d in the multiplicative group of n will be found,and for any d in any fi, the counting function of the number of invariant factors of order d has alimiting distribution following an Erdo˝s–Kac type law, but with the unusual property that some dyield non-normal distributions.To demonstrate, the next theorem that shall be shown will prove the following special case:Example. The number of invariant factors of order 720720 is on averageEn(I(m; 720720)) =140log logn+O(1).By comparison, the total number of invariant factors is on average log logn + O(1) (a directconsequence of Lemmata 2.5 and 3.6 with the well-known estimate that∑p≤n1p = log log n+O(1)[10, Theorem 2.7]). Thus “on average,” the multiplicative group of any integer has 1/40 invariantfactors of order 720720.1.1 DefinitionsTo state the next results, the shown pattern for fi in the introduction no longer suffices; a properdefinition is needed. Each fi is properly defined as sets of least common multiples of sets of primepowers. Thus we first need to define a canonical sequence of prime powers:Definition 1.2. Standard Invariant Sequences. We say the total φ-sequence q1, q2, q3, . . . is theunique infinite sequence which consists of every prime power, ordered so that the following aresatisfied:21. For all natural i < j, we have φ(qi) ≤ φ(qj).2. For all natural i < j, if φ(qi) = φ(qj), then qi < qj .We say a finite sequence q1, . . . , qn of prime powers is a φ-sequence if for any prime power q,either q = qi for some 1 ≤ i ≤ n, φ(q) < φ(q1), or φ(q) > φ(qn). Note that this requirement impliesevery finite φ-sequence is a contiguous section of the total φ-sequence.For clarity, this means the total φ-sequence is:{qn}∞n=1 = {2, 3, 4, 5, 8, 7, 9, 16, 11, 13, 17, 32, 19, 27, 25, 23, 29, . . .}.With this sequence in mind, it is now possible to define each fi:Definition 1.3. The Universal Factor Order Sets. The sequence of universal factor order sets,{fi}∞i=1 is defined so thatfi ={lcm{qj : j ≤ i}} if φ(qi) < φ(qi+1),{lcm{qj : j ≤ i}, lcm{qj : j < i or j = i+ 1}} if φ(qi) = φ(qi+1).A number d ∈ N is said to be a universal factor order if d ∈ fi for some i ∈ N, and is otherwise arare factor order.A property which is not immediately obvious but which will be proven later in the work is thefollowing:Proposition 1.4. No two doubleton sets are adjacent in the sequence of universal factor order sets.For the purpose of exposition, this property will be taken for granted in this chapter.With the definition of fi stated, we now introduce the rest of the notation necessary to state themain results of this work. This comprises a shorthand for statements like “the counting functionfor the number of invariant factors of order d in the multiplicative group of n” and other similarlyverbose aspects of the multiplicative groups.Definition 1.5. Counting Functions related to Multiplicative Groups. Let I(n; d) count the num-ber of times d appears as an invariant factor of the multiplicative group (Z/nZ)×. Let P(n; pα)count the number of times pα appears as an elementary divisor of the multiplicative group (Z/nZ)×.Let Q(n; pα) count the number of times pα or any prime power multiple of pα appears as an ele-mentary divisor of the multiplicative group (Z/nZ)×.Now that it has been defined, for the rest of the work, I(n; d) will be used instead of “thecounting function for the number of invariant factors of order d in the multiplicative group of n” in3almost all contexts. We shall also make use of the notation En(f(m)) to indicate the expectation1n∑1≤m≤n f(m).To state the general theorem, two sequences of certain special constants are needed:Definition 1.6. The mu Sequence.µi = φ(qi)−1 − φ(qi+1)−1.In this work φ is the Euler totient function where φ(n) = #(Z/nZ)×.Definition 1.7. The sigma Sequence.σ2i = φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1.The first few elements of these sequences are{µi}∞i=1 ={12, 0,14, 0,112, 0,124,140,160,148, 0,1144, 0,1180,1220,3308, . . .}and{σ2i }∞i=1 ={12,12,12,38,13,518,14,15,16,1396,15128,19,17162,110,111,677, . . .}respectively. These sequences roughly correspond to the coefficients for the mean and square rootof the variance in the asymptotic formulae for the estimates, which will be seen formally in the nextsection.1.2 ExpectationsGiven the definitions in the preceding section, it is now possible to state the first set of results,which will cover the the expectations of the form En(I(m; d) for all d ∈ N. As the statement ofthese results involve a large number of unusual constants, each special case of the second theoremwill be preceded by application to one or more specific values of d.First, consider the general case:Theorem 1.8. If d ∈ fi, thenEn(I(m; d)) = µi log logn+Od((log log n)1/2).This theorem is both true but also somewhat misleading. There are some invariant factor ordersets where the corresponding µi = 0, so the “error term” is actually the main term. In othercases, the error term can be made more precise, either being O(1) or a non-zero constant times(log logn)1/2 plus o((log logn)1/2). The first example given below will show just such a refinementof the error term:4Example. The number of invariant factors of order 5040 is on averageEn(I(m; 5040)) =140log logn+O(1).If this is compared to the total number of invariant factors of the multiplicative group (denotedI(m)) it can be shown that En(I(m)) = log log n+O(1). In other words, there is a sense in whichthe cyclic group Z5040 makes up 2.5 percent of the total number of invariant factors of order n “onaverage.”Roughly speaking, the µi sequence represents the fraction of the total number of invariant factorsand the σi scales the variance, but due to the nature of some of the distributions the variance factorσi has an impact on the expectation, or in cases where µi vanishes, becomes the expectation.The part of the theorem that generates the above example requires only the µi constants butlater theorems will require the σi as well.Theorem 1.9. If d ∈ fi and i > 1 with #fi−1 = #fi = #fi+1 = 1, thenEn(I(m; d)) = µi log logn+Od(1).Note how this theorem places a requirement on the sizes of fi−1, fi and fi+1. This will be areoccuring theme in the statement of the general theorems. Now, we show an example that isn’tcovered by the above theorem.Example. The number of invariant factors of order 2520 is on averageEn(I(m; 2520)) =124log logn−(√736π+ o(1))(log log n)1/2.Note that there is a secondary term proportional to (log logn)1/2. In the general theorem, onecan see that it depends upon σi−1 as follows:Theorem 1.10. If d ∈ fi and i > 1 with #fi−1 = 2 and #fi = #fi+1 = 1, thenEn(I(m; d)) = µi log logn−(σi−1√2π+ o(1))(log log n)1/2.Over the expectation theorems shown so far, there is a pattern where the entry from the µisequence is the coefficient of a log logn term and terms which depend on the σi sequence will be(log logn)1/2 in scale. This pattern will hold throughout the rest of the examples, but not all entrieshave terms of both forms.For instance, in the next example contains two invariant factor orders where there is no log log nscale term:5Example. The number of invariant factors of order 360 and 840 are on averageEn(I(m; 360)) =(√736π+ o(1))(log logn)1/2,andEn(I(m; 840)) =(√736π+ o(1))(log logn)1/2.As previous theorems show, the choice of which entries from µ and σ to use in the formuladepend on the index of the f set containing the invariant factor order. In the above example, theset {360, 840} is f6 and µ6 = φ(q6)−1−φ(q7)−1 = 16− 16 = 0. The above example is thus an exampleof a distribution where µi vanishes.It is also worth noting that as this term lacks a log log n term, if one were to count the fractionof invariant factors that are “on average” of the order 360 or 840 combined, one would find usingthe same heuristic applied earlier thatlimn→∞1log logn(En(I(m; 360)) +En(I(m; 840)))= 0.Thus even though these invariant factor orders comprise a non-zero amount of an integers invariantfactors “on average” they do not manage to make up a positive fraction of the total number ofinvariant factors “on average.”Now, consider the corresponding theorem for the above example:Theorem 1.11. If d ∈ fi and #fi = 2, thenEn(I(m; d)) =(σi√2π+ o(1))(log log n)1/2.It can be easily shown that #fi = 2 if and only if µi = 0. This can easily be seen fromDefinition 1.3, which states that #fi = 2 if and only if φ(qi) = φ(qi+1), and by Definition 1.6,µi = φ(qi)−1 − φ(qi+1)−1 = 0.Thus the above theorem is not really an exception to the pattern that there is a µi log log nterm, it is just the case that for all fi where #fi = 2, it holds µi log logn = 0.The next example contains a fairly complex formula for the (log log n)1/2 coefficient:Example. The number of invariant factors of order 120 and 12 are on averageEn(I(m; 120)) =112log log n−(√316π+√736π+ o(1))(log log n)1/2,andEn(I(m; 12)) =14log logn−(√14π+√316π+ o(1))(log log n)1/2,6This is an example of the most complicated of the formulas for the expectation. Why thesetwo numbers have such a complicated formula will be given explanation after considering the cor-responding theorem:Theorem 1.12. If d ∈ fi and i > 1 with #fi−1 = 2 and #fi+1 = 2, thenEn(I(m; d)) = µi log logn−(σi−1 + σi+1√2π+ o(1))(log logn)1/2.This is worth comparing with the other theorems shown so far which have a (log logn)1/2 term.Observe that in each theorem shown so far, the index for the entries of a σi chosen for the coefficientalways correspond to the index of an invariant factor order set fi where #fi = 2. Thus in a certainsense, the invariant factor order sets which are not singletons induce a (log log n)1/2 scale shift inthe mean of not only the elements of that set, but also in the means of the adjacent sets in thesequence of invariant factor order sets.This effect will be shown later to correspond to a distortion in the limiting distribution functionsthat is induced by coincidences in the values of φ(qi).Now, the next example is most common invariant factor “on average:”Example. The number of invariant factors of order 2 is on averageEn(I(m; 2)) =12log logn−(√14π+ o(1))(log logn)1/2.The “on average” fraction of invariant factors which have order two is clearly 1/2. The lasttheorem describing the behaviour of invariant factor orders which are universal factor orders onaverage is the following:Theorem 1.13. If d ∈ fi and i = 1 or #fi−1 = #fi = 1 and #fi+1 = 2, thenEn(I(m; d)) = µi log logn−(σi+1√2π+ o(1))(log log n)1/2.It will be shown later that there are no other possible arrangements of sizes of invariant factororders (it is an immediate consequence of Lemma 2.6), so these theorems characterize all possible dwhich are universal factor orders. In particular, this means there are no universal factor order setswhere two adjacent universal factor order sets in the sequence of universal factor order sets eachhave two elements.Finally, observe that this theorem is consistent with the earlier discusssion about the coefficients(log logn)1/2 terms. However, if one looks at the exact scale of the coefficients of the (log log n)1/2terms over the above theorems, it should be clear that if fi is a term where #fi = 2, then the twoinvariant factors d ∈ fi have σi√2π as coefficients, but for d ∈ fi−1 or d ∈ fi+1, (part of) the coefficient7induced is − σi√2π. Since #fi = 2, from the above discussion, this implies #fi−1 = #fi+1 = 1, so thereare two elements with positive contribution and two elements with an equal negative contribution.Finally, the case where d ̸∈ fi for any i ∈ N is considered. First, an example:Example. The number of invariant factors of order 8 is on averageEn(I(m; 8))≪r (log logn)−rfor any r > 0.This example has been chosen as it is the first d where it is nontrivial to show that there arevery few invariant factors of that order on average. 2,4, and 6 are universal factor orders, and arelatively simple argument can show that odd orders are impossible.In the general case, one can extend this to a similar statement about all the moments of thefunction counting the number of invariant factors as follows:Theorem 1.14. If for every i ∈ N, the natural number number d > 1 is such that d ̸∈ fi, then forany k ∈ N, and r > 0,En(I(m; d)k)≪d,r,k (log log n)−r.This should come across as fairly restrictive. It suggests that the multiplicative groups of thenatural numbers have rare invariant factor orders – on average – approximately never. Combinedwith Theorem 1.1, this suggests that not only are integers which have non-standard invariant factororders rare, they do not have very many rare factor orders.1.3 Limiting DistributionsThe next theorems concern limiting distributions.Theorem 1.15. Let d ∈ N. If d is a universal factor order, (d ∈ fi for some i), the limitingdistribution of I(m; d) under appropriate rescaling is fully characterized by the number of elementsin fi, fi−1, fi+1, except for the special cases where i = 1 or i = 3. If d is a rare factor order, (d ̸∈ fifor any i ∈ N), then the limiting distribution is fully characterized by this fact.For these theorems, some consistent notation for common probability distributions will be nec-essary. The following notation will be used throughout this work:8Definition 1.16.ϕ(x) = e− x22√2π(normal probability density function),Φ(x) =∫ x−∞ ϕ(t) dt (normal cumulative distribution function),ϕ+(x) = 2ϕ(x)1[0,∞)(x) (truncated right normal probability density function),Φ+(x) = max{Φ(x)− Φ(−x), 0} (truncated right normal cumulative distribution function),ϕ−(x) = ϕ+(−x) (truncated left normal probability density function),Φ−(x) = 1− Φ+(−x) (truncated left normal cumulative distribution function),ϕ(x;α) = 2ϕ(x)Φ(αx) (skew normal probability density function [1]),Φ(x;α) = Φ(x)− 2T(x, α) (skew normal cumulative distribution function [1]),where T(h, a) is Owen’s T function [12], which equals the integral of the standard bivariate normaldistribution over the region of R2 where x > h and 0 < y < ha when both h, a are non-negative,and which is even in h and odd in a.To disambiguate: in this work φ shall denote the Euler phi function and φ-sequences, while ϕand Φ denote respectively the normal density and the normal distribution functions.We shall also define this function:Definition 1.17 (The S Function). We defineS(x;σ1, σ2, σ3) = limy→−∞ limT→∞− 12π∫ T−Te−itx − e−ityite−(σ21+σ22+σ23)t2/2 erfi(σ2t√2)erfi(σ3t√2)dt.Note that this limit arises from the Fourier inversion of the characteristic function of a proba-bility distribution as described in Lemma D.5; the inner limit clearly exists due to the faster thanexponential decay of the integrand, and the outer limit exists as it yields part of the cumulativedistribution function described in the aforementioned lemma.It is also necessary to have notation for describing the probability of events over a finite numberof integers. If S(m) is any statement given in terms of m, the notation Pn(S(m)) =1n#{m ∈N : m ≤ n, S(m)}. In other words, Pn(S(m)) is the probability that an integer m in the set{1, . . . , n} satisfies S(m).As in the preceding section on expectations, this section will go through the same set of examplesin the same order. To start, observe the following:Example.limn→∞Pn(I(m; 5040)− 140 log log n( 15 log logn)1/2≤ x)= Φ(x),where Φ(x) is the standard normal distribution with characteristic function e−t2/2.9This is an Erdo˝s–Kac law for the number of invariant factors of order 5040. In turns out thiscan be generalized, using the µi and σi sequences to yield the following theorem:Theorem 1.18. If i > 1 and #fi−1 = #fi = #fi+1 = 1, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log logn)1/2≤ x)= Φ(x),where Φ(x) is the standard normal distribution with characteristic function e−t2/2.This theorem thus makes clear that for those universal factor orders d ∈ fi where fi is a sin-gleton between singletons in the sequence of universal factor order sets, an Erdo˝s–Kac type law isobtained where µi log logn approximates the expectation of I(m; d) and σ2i log logn approximatesthe variance.In the proofs for the limiting distributions, this law arises from the fact that I(m; d) can beexpressed in terms of bounded additive functions. In the above case, it will be shown that only onesuch function is needed to represent I(m; d) and as a consequence the limiting distribution is justthe limiting distribution of that additive function.However, some universal factor orders d ∈ fi have invariant factor counting functions I(m; d)which depend on multiple additive functions. In such cases, while the limiting distribution of anyone such function follows an Erdo˝s–Kac law, the joint distribution of all the additive functions onwhich I(m; d) will be shown to be either a nonsingular bivariate normal distribution or a singulartetravariate normal distribution.In such cases, while the additive functions follow a typical Erdo˝s–Kac law, the resultant invariantfactor order function has a distribution which is not a normal distributon. Consider the followingexample:Example.limn→∞Pn(I(m; 2520)− 124 log logn( 14 log logn)1/2≤ x)= Φ(x;− 1− a√1− a2),where and Φ(x;λ) is the skew normal distribution with parameter lambda. The characteristicfunction of this distribution ise−t2/2(1− i erfi(√φ(qi)−1 − φ(qi)−22σit)).In this example, one can see that I(m; 2520) is scaled in exactly the same way as if it werefollowing the usual Erdo˝s–Kac law, as {2520} = f7 and µ7 = 124 with σ27 = 14 . This will hold for allexamples and theorems in this section which concern universal factor orders.The general theorem for the above example is:10Theorem 1.19. If i > 1 and #fi−1 = 2 and #fi = #fi+1 = 1, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log logn)1/2≤ x)= Φ(x;− 1− a√1− a2),wherea =φ(qi)−2 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,and Φ(x;λ) is the skew normal distribution with parameter lambda. The characteristic function ofthis distribution ise−t2/2(1− i erfi(√φ(qi)−1 − φ(qi)−22σit)).The appearance of invariant factor counting functions I(m; d) with skew normal limiting dis-tributions occurs because the counting function can be represented in terms of the limiting jointdistribution of two additive functions, which in this case is a nonsingular bivariate normal distri-bution.In general, when {d} = fi is a singleton and i > 1, the number of additive functions necessaryto represent the invariant factor order counting functions is #fi−1 ·#fi+1.1In the case where #fi = 2, the distributions are relatively simple. Note that the µi log log nterms vanish as µi = 0 in such cases. For example:Example.limn→∞Pn(I(360; d)( 518 log logn)1/2≤ x)=Φ(x) if x ≥ 0,0 otherwise.limn→∞Pn(I(840; d)( 518 log logn)1/2≤ x)=Φ(x) if x ≥ 0,0 otherwise.Furthermore,limn→∞Pn(I(m; 360) + I(m; 840)( 518 log logn)1/2≤ x)= Φ+(x).This distribution has characteristic function e−t2/2(1 + i erfi(t/√2)).In the general case, this becomes:Theorem 1.20. If #fi = 2, then for d ∈ filimn→∞Pn(I(m; d)σi(log logn)1/2≤ x)=Φ(x) if x ≥ 0,0 otherwise.1This in turn corresponds to a statement about part of the total phi sequence.11Furthermore,limn→∞Pn( ∑d∈fi I(m; d)σi(log logn)1/2≤ x)= Φ+(x).This distribution has characteristic function e−t2/2(1 + i erfi(t/√2)).The limiting distributions of these invariant counting functions always happen to depend on thelimiting distribution of a single additive function, since each doubleton in the sequence of universalfactor order sets is isolated. As there is a slightly different relation between the invariant factororder counting function and the additive function when dealing with doubleton sets the limitingdistribution ends up being non-normal.Now, consider the situation where a singleton is surrounded by two doubletons. By the earlierargument, it will have an invariant factor order counting function which depends on four additivefunctions. The next example will concern just such a situation:Example.limn→∞Pn(I(m; 120)− 112 log logn( 13 log logn)1/2≤ x)= Φ(x)+ 2T(x;−√1 + a− b− c2 + 2b)+ 2T(x;−√1− a+ b− c2 + 2a)+ S(4x; 2√1 + a+ b+ c, 2√1 + a− b− c, 2√1− a+ b− c),wherea =φ(qi)−1 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,b =φ(qi)−2 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,c =φ(qi)−2 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 .The characteristic function of this distribution ise−t2/2(1− i erfi(√φ(qi)−1 − φ(qi)−22σit)− i erfi(√φ(qi+1)−1 − φ(qi+1)−22σit)− erfi(√φ(qi)−1 − φ(qi)−22σit)erfi(√φ(qi+1)−1 − φ(qi+1)−22σit).One can see from the above that this limiting distribution is much more complicated than theothers. However, if one looks at the characteristic function, one can see that it contains the same12sorts of terms as the previous section, but has more of them. This distribution does not have a niceshorthand name, but is sufficiently well described by its distribution function and characteristicfunction. One may informally think of it as a doubly skewed normal distribution.Now, let us consider the general theorem for distributions of this type:Theorem 1.21. If i > 3 and #fi = 1 and #fi−1 = #fi+1 = 2, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log logn)1/2≤ x)= Φ(x)+ 2T(x;−√1 + a− b− c2 + 2b)+ 2T(x;−√1− a+ b− c2 + 2a)+ S(4x; 2√1 + a+ b+ c, 2√1 + a− b− c, 2√1− a+ b− c),wherea =φ(qi)−1 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,b =φ(qi)−2 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,c =φ(qi)−2 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 .The characteristic function of this distribution ise−t2/2(1− i erfi(√φ(qi)−1 − φ(qi)−22σit)− i erfi(√φ(qi+1)−1 − φ(qi+1)−22σit)− erfi(√φ(qi)−1 − φ(qi)−22σit)erfi(√φ(qi+1)−1 − φ(qi+1)−22σit).In this case, d belongs to a singleton universal factor order set fi which is between two doubletonuniversal factor order sets in the sequence of such sets. This fairly complicated distribution arisesfrom the sum of three independent random variables that correspond to the eigenvectors of asingular tetravariate normal distribution which have nonzero eigenvalues. This tetravariate normaldistribution, in turn, originated from four additive functions on which I(m; d) depends.Note that as f3 = {12}, #f2 = #f4 = 2, it would follow that d = 12 would satisfy every conditionlisted in the theorem above except the condition that i > 3. The general theorem for i > 3 dependson a result concerning how close powers of two are to each other in the total phi sequence. Inthe case where i ≤ 3 this result does not hold, but for d ∈ f1 and d ∈ f2 neither leads to uniquedistributions2.2The former due to a numerical coincidence and the latter due to the powers of two being irrelevent to that typeof distribution13However, in the case where d = 12, a unique limiting distribution is the result. This limitingdistribution has the same expectation that would result from the general case where #fi−1 =#fi+1 = 2. This is because both distributions are the distributions of a certain sum of randomvariables. In the general case, the result concerning the closeness of of powers of two in the totalphi sequence ensures these variables are independent. In the case where d = 12 however, thesevariables are not independent. One can thus see why the expectations are the same, but thelimiting distributions differ.As d = 12 is the only universal factor order which satisfies the following theorem, there is noneed to provide an example beforehand:Theorem 1.22. If i = 3, thenlimn→∞Pn(I(m; 12)− 1/4 log log n( 12 log log n)1/2≤ x)=MnF (x),where Mn is from Definition 5.1, and F is the singular multivariate normal distribution centred atthe origin with matrix of covarianceM =1 5/8 1/2 1/85/8 1 −1/8 1/41/2 −1/8 1 3/81/8 1/4 3/8 1/2 .There is not much to say about this distribution, beyond the fact that it exists and its expectationcan be computed. It arises instead of the preceding distribution due to the occurence of a uniquecorrelation that breaks an otherwise universal symmetry.Next, the distribution function for the most common invariant factor order is given:Example.limn→∞Pn(I(m; 2)− 12 log logn( 12 log logn)1/2≤ x)= Φ(x;− 1− a√1− a2),wherea =φ(qi)−1 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,and Φ(x;λ) is the skew normal distribution with parameter lambda. The characteristic function ofthis distribution ise−t2/2(1− i erfi(√φ(qi+1)−1 − φ(qi+1)−22σit)).This is another skew normal distribution, and in fact the general theorem will give all possibleremaining limiting distributions for I(m; d):14Theorem 1.23. If i = 1 or if i > 1 and #fi−1 = #fi = 1, #fi+1 = 2, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log logn)1/2≤ x)= Φ(x;− 1− a√1− a2),wherea =φ(qi)−1 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,and Φ(x;λ) is the skew normal distribution with parameter lambda. The characteristic function ofthis distribution ise−t2/2(1− i erfi(√φ(qi+1)−1 − φ(qi+1)−22σit)).In the case where i > 1, the skew normal limiting distribution is expected, as #fi−1·#fi+1 = 2, soI(m; d) for d ∈ fi depends two additive functions with a bivariate normal limiting joint distribution.In the case where d = 2 (and i = 1) the underlying pattern in the phi sequence matches that requiredfor a bivariate normal distribution, and while there are some complications when dealing with thiscase, they happen to cancel out numerically.Finally, the limiting distribution for rare factor order sets is extremely trivial. For example:Example.Pn(I(m; 8) = 0) = 1, Pn(I(m; 8) > 0) = 0.The mass of the distribution exists entirely at the point where I(m; 8) = 0. This extends to thegeneral case, where when expressed in terms of a limiting distribution function:Theorem 1.24. For any natural number d where d is a rare factor order, thenlimn→∞Pn(I(m; d) ≤ x) =1 if x ≥ 0,0 otherwise.Note that there is no need to scale I(m; d) in any way to obtain this result. This is consistent withthe observation from the previous section that on average there are very few rare factor orders. Theproof for the behaviour of the rare factor orders arises from technical results necessary to connectthe invariant factor order functions to the additive functions. This concludes the statement of theprimary result.1.4 Overview of the Proofs of the ResultsThe rest of this introduction will now move on to providing an overview and guide to this work andthe proofs it contains. The majority of this work is concerned with proving Theorem 1.15. The15argument starts in chapter 2 with some elementary number theory to convert the problem of theinvariant factors of group structure of (Z/nZ)× into a statement about the values of a finite setof strongly additive functions on n, provided a certain technical assumption (called y-typicality) ismet. In section 3 we apply the methods from Kubilius [7] on multivariate distributions of additivefunctions to convert statements about additive functions into statements about probabilities. Inchapter 4, we prove a probabalistic statement about our technical assumption, using a mixture ofanalytic and elementary arguments, to hold for most n. In chapter 5, we combine all the aboveresults to finally prove Theorem 1.15.Theorem 1.1 follows from the above after a short argument, given in chapter 6, along withasymptotic formulas for the moments of the limiting distributions of the invariant factor orders. Inchapter 7, we show how the techniques developed in this work can be applied to solve a similar sortof problem.We now move on to a brief discussion of a few key concepts that will appear throughout thiswork in proofs and in intermediate results. These concepts should be kept in mind throughoutthe reading of this work. The first of these concepts is that of a y-typical natural number, alsosometimes called y-typicality when discussed as a property a number number has. It is definedbelow, in terms of a parameter y:Definition 1.25. For some real y ≥ 1, a number n ∈ N is said to be y-typical if1. For any two prime powers q1, q2, if φ(q1) < φ(q2) ≤ y then Q(n; q1) ≥ Q(n; q2).2. For any prime power where φ(q1) ≤ y and φ(q2) > y, it follows Q(n; q1) > Q(n; q2).The purpose of this concept is to allow a conversion from the total φ-sequence to statementsabout the number of elementary divisors and invariant factors found in the multiplicative group fornumbers which satsify the above property. The reason why this property is called y-typicality isdue to the following proposition, proved in Section 4.2:Proposition 1.26. For any real r ≥ 1, ϵ > 0 and y = y(n)≪ (log log n)1/4−ϵ with y ≥ 1,Pn(m is not y-typical)≪r y4r(log log n)randlimn→∞Pn(m is y-typical) = 1.Finally, we provide notation for the class of additive functions that are found in this work. Thestandard distinct prime factor counting function ω(n) = #{prime numbers p : p | n} is also used inthis work, and is a special case of the class of additive functions used.16Definition 1.27. For any subset S of the set of all prime natural numbers. we define ω(n;S) =#{p ∈ S : p | n} and ω(n; q, a) = ω(n; {p : p ≡ a mod q}). Furthermore, for S, T as subsets of theset of all prime numbers, define ω(n;S − T ) = ω(n;S)− ω(n;T ).17Chapter 2From the Invariant Factors of(Z/nZ)× to Additive FunctionsIn this section, we find a method for relating the values natural numbers take on certain additivefunctions to their invariant factor decomposition, providing those natural numbers satisfy the specialcondition we called y-typicality in Definition 1.25.2.1 Relation Between Invariant Factors and Additive Func-tions Under General AssumptionsRecall the various counting functions of subgroups of (Z/nZ)× from Definition 1.5. The followinglemmas express these counting functions in terms of additive functions from Definition 1.27 underno or general assumptions. All statements are proved by elementary group theory and readersfamiliar with invariant factor decompositions will find nothing unfamiliar or unexpected here.The following lemma establishes the counting function for individual elementary divisors interms of additive functions.18Lemma 2.1. We have that P(n; pα) = ω(n; {q prime : pα ∥ q − 1}) + E(n; pα) whereE(n; pα) =1 if pα = 2 and 4 ∥ n or 16 | n,2 if pα = 2 and 8 ∥ n,1 if p = 2 and α > 1 and 2α+2 ∥ n,1 if p ̸= 2 and pα+1 ∥ n,0 otherwise.Proof. First, observe by the Chinese Remainder Theorem, and some elementary group theory that(Z/nZ)× ∼=∏pα∥n(Z/(pα)Z)× ∼=( ∏2α∥nα≥2Z2α−2 × Z2)( ∏pα∥np̸=2Zpα−1 × Zp−1).Thus, by factoring into primes, we get that(Z/nZ)× ∼=( ∏2α∥nα≥2Z2α−2 × Z2)( ∏pα∥np̸=2Zpα−1)(∏p|n∏qα∥p−1Zqα).As this is a decomposition into prime factors (if excluding Z2α−2 when 4 ∥ n), we can easily seethatP(n; pα) = ω(n; {q prime: pα ∥ q − 1}) + E(n; pα)where E(n; pα) is as described above, completing the proof.From the above lemma it becomes possible to establish the counting function for all elementarydivisors whose order is divisible by a set prime power in terms of additive functions. This quantityis necessary for the computation of the invariant factors, as discussed below.Lemma 2.2. We have that Q(n; pα) = ω(n; {q prime : pα | q − 1}) + E¯(n; pα) whereE¯(n; pα) =2 if pα = 2 and 8 | n,1 if pα = 2 and 4 ∥ n,1 if p = 2 and α > 1 and 2α+2 | n,1 if p ̸= 2 and pα+1 | n,0 otherwise.19Proof. By Definition 1.5 and Lemma 2.1, we have thatQ(n; pα) =∞∑k=αP(n; pk)=∞∑k=αω(n; {q prime: pk ∥ q − 1}) +∞∑k=αE(n; pk)= ω(n; {q prime: pα | q − 1}) +∞∑k=αE(n; pk).Note that all the above sums are convergent since P(n; pk) and E(n; pk) only have finite supportfor a fixed n. We define E¯(n; pα) =∑∞k=αE(n; pk).As there can be at most one k ≥ α such that pk ∥ n, it holds by Lemma 2.1 that for p ̸= 2,∞∑k=αE(n; pα) =1 if pα+1 | n,0 otherwise.Likewise, for p = 2, α > 1, we have thatE¯(n, 2α) =1 if 2α+2 | n,0 otherwise.For pα = 2, then E¯(n; 2) = E(n; 2) + E¯(n; 4) which evaluates toE¯(n; 2) =1 if 4 ∥ n,2 if 8 | n,0 otherwise.This completes the proof.The above result can be contrasted with the equivalent result found in Definitions 2.7, 2.8,and Lemma 2.10 in [8]. In the terms of [8], for any prime p, α = (P(n; p1), . . . ,P(n; pk), . . .) isthe conjugate partition of a = (Q(n; p1), . . . ,Q(n; pk), . . .). A consequence of this that is worthmentioning but not of significant consequence to this work is that for any prime p,∏∞k=1 ZP(n;pk)pkis the p-Sylow subgroup of (Z/nZ)×.To see how the elementary divisors can be used to obtain information about the invariant factororder, consider the following example:Example. Consider the number 4849845 = 3 · 5 · 7 · 11 · 13 · 17 · 19. By its prime factorization, and20the cyclic nature of the multiplicative groups of primes, it follows(Z/4849845Z)× = Z2 × Z4 × Z6 × Z10 × Z12 × Z16 × Z18= Z16 × Z4 × Z4 × Z2 × Z2 × Z2 × Z2 ×Z9 × Z3 × Z3 ×Z5= Z720 × Z12 × Z12 × Z2 × Z2 × Z2 × Z2.In the first step, the multiplicative group is split into the cyclic groups corresponding to the mul-tiplicative groups of the prime power factorization of 4849845. In the second step, those cyclicgroups are split into rows of cyclic groups of prime powers, with each row containing prime powersfor only one prime. The primes are in ascending orders but the prime powers for each prime are indescending order. To obtain the invariant factors, the orders of each group from the second stepare multiplied columnwise, yielding one invariant factor of order 720, two invariant factors of order12 and four invariant factors of order 2.More generally, we can state this method in terms of the following lemma:Lemma 2.3. Let n be an integer, and let q1, . . . , qN be a sequence of distinct prime powers con-taining all the distinct elementary divisors of (Z/nZ)×, ordered so Q(n; qi) does not increase as iincreases. Then if for i ≤ N ,di = lcm{qj : j ≤ i},we have that(Z/nZ)× ∼=(N−1∏i=1ZQ(n;qi)−Q(n;qi+1)di)× ZQ(n;qN )dN .is the invariant factor decomposition of (Z/nZ)× (ignoring trivial groups).Proof. As the elementary divisor decomposition and the invariant factor decomposition of an abeliangroup is unique up to isomorphism, it suffices to show that the stated invariant factor decompositionabove is isomorphic to the elementary divisor decomposition.Let D = {i ∈ N : i < N,Q(n; qi) > Q(n; qi+1)}.Observe that for i ∈ D or i = N , pα | di if and only if Q(n; pα) ≥ Q(n; qi), so pα ∥ di ifand only if Q(n; pα) ≥ Q(n; qi) > Q(n; pα+1), which means pα ∥ di if and only if P(n; pα) ≥Q(n; qi)−Q(n; pα+1) > 0.Also observe that if Q(n; pα) < Q(n; qN ), we have that Q(n; pα) < Q(n; qi) for all qi, so itfollows pα is not an elementary divisor of n and neither is any multiple of pα, so Q(n; pα) = 0.Thus if Q(n; qN ) > 0, it follows pα ∥ dN if and only if Q(n; pα) > 0 and Q(n; pα+1) = 0.Furthermore, observe that if P(n; pα) > 0, there exists a qi such that pα = qi21Thus it follows,G ∼=(N−1∏i=1ZQ(n;qi)−Q(n;qi+1)di)× ZQ(n;qN )dN∼=(N−1∏i=1∏pα∥diZQ(n;qi)−Q(n;qi+1)pα)×∏pα∥dNZQ(n;qN )pα .The substitution of 1 ≤ i ≤ N − 1 for i ∈ D is justified by the fact that for i ̸∈ D, Q(n; qi) −Q(n; qi+1) = 0. HenceG ∼=(∏i∈D∏pα∥diZQ(n;qi)−Q(n;qi+1)pα)×∏pα∥dNZQ(n;qN )pα∼=(∏i∈D∏Q(n;pα)≥Q(n;qi)Q(n;qi)>Q(n;pα+1)ZQ(n;qi)−Q(n;qi+1)pα)×∏pα∥dNZQ(n;qN )pαWe can now reverse the substitution of 1 ≤ i ≤ N − 1 for i ∈ D, as the terms altered by the changeremain irrelevant, and then change the order of multiplication, leading toG ∼=( ∏P(n;pα)>0∏1≤i≤N−1Q(n;pα+1)<Q(n;qi)≤Q(n;pα)ZQ(n;qi)−Q(n;qi+1)pα)×∏pα∥dNZQ(n;qN )pα∼=( ∏P(n;pα)>0P(n;pα+1)>0ZQ(n;pα)−Q(n;pα+1)pα)×( ∏P(n;pα)>0P(n;pα+1)=0ZQ(n;pα)−Q(n;qN )pα)×∏Q(n;pα)>0Q(n;pα+1)=0ZQ(n;qN )pα .The final step above is justified by the fact that if Q(n; qN ) = 0 the final products are trivial,and if Q(n; qN ) > 0, the substitution is justified. Finally noting that Q(n; pα) = P(n; pα) ifQ(n; pα+1) = 0 gives us thatG ∼=( ∏P(n;pα)>0P(n;pα+1)>0ZP(n;pα)pα)×( ∏P(n;pα)>0P(n;pα+1)=0ZQ(n;pα)pα)∼=( ∏P(n;pα)>0P(n;pα+1)>0ZP(n;pα)pα)×( ∏P(n;pα)>0P(n;pα+1)=0ZP(n;pα)pα)∼=∏P(n;pα)>0ZP(n;pα)pα∼= (Z/nZ)×.22The last line is the product of the elementary divisors by definition. This completes the proof.Combining the above two lemmata yields the following result:Lemma 2.4. Let n ∈ N be an natural number. Let q1, . . . , qN be a list of distinct prime powerssuch that1. For any natural numbers i, j ≤ N , i < j implies Q(n; qi) ≥ Q(n; qj).2. For any prime power q where for all i ≤ N , q ̸= qi, it follows Q(n; qN ) > Q(n; q).Then there exists a finite sequence of valuesdi = lcm{qj : j ≤ i}for 1 ≤ i ≤ N where for 1 ≤ i < N ,I(n; di) = Q(n; qi)−Q(n; qi+1)and I(n; dN ) ≤ Q(n; qN ).Furthermore, the sequence d1, . . . , dN contains every invariant factor of (Z/nZ)× less than orequal to dN . If d is an invariant factor of (Z/nZ)× greater than dN , then dN | d.Proof. Let P (n) be the set of prime powers that are elementary divisors of (Z/nZ)× not found inq1, . . . , qN , and let M = N +#P (n).IfM > N , let qN+1, . . . , qM be the elements of P (n) ordered so i < j implies Q(n; qi) ≥ Q(n; qj).Note that this is possible since for any q ∈ P (n), Q(n; qN ) > Q(n; q).For 1 ≤ i ≤M , let di = lcm{qj : j ≤ i}.Then by application of Lemma 2.3, it is obtained that(Z/nZ)× ∼=( M∏i=1ZQ(n;qi)−Q(n;qi+1)di)× ZQ(n;qN )dNis the invariant factor decomposition of (Z/nZ)× (excluding trivial groups).Thus for 1 ≤ i ≤ N , it followsI(n; di) = Q(n; qi)−Q(n; qN ).If N =M , I(n; dN ) = Q(n; qN ). If N < M , I(n; dN ) = Q(n; qN )−Q(n; qN+1) ≤ Q(n; qN ).Furthermore, it is clear that d1, . . . , dM contains every invariant factor of (Z/nZ)× in increasingorder. Thus d1, . . . , dN contains every invariant factor less than or equal to dN . If d is an invariantfactor greater than dN , then there is some i > N such that di = d, and clearly dN | di = d.23Note that in the preceding lemma, it is entirely possible that I(n; di) = 0 for some or even alli ≤ N . A trivial case where this occurs is when n = 1.For the sake of completeness, it is also possible to obtain that:Lemma 2.5. Let n ∈ N be a natural number. The total number of invariant factors in n isI(n) = ω(n) + E⋆(n),where E⋆(n) is an integer between −1 and 1.Proof. Let q1, . . . , qN be the orders of the elementary divisors of (Z/nZ)×, ordered so that Q(n; qi)is non-increasing as i increases. Then by Lemma 2.3 it follows(Z/nZ)× ∼=( N∏i=1ZQ(n;qi)−Q(n;qi+1)di)× ZQ(n;qN )dNis the invariant factor decomposition of (Z/nZ)× for di = lcm{qj : j < i}. As this means I(n; di) =Q(n; qi)−Q(n; qi+1) for 1 ≤ i < N and I(n; dN ) = Q(n; qN ), it followsI(n) = Q(n; qN ) +N−1∑i=1(Q(n; qi)−Q(n; qi+1))= Q(n; q1).Consequently, by Lemma 2.2,I(n) = ω(n; {p prime: q1 | p− 1}) + E¯(n; q1).Observe that {p prime: q1 | p− 1} ⊂ {p prime: 2 | p− 1} for any prime power q1, soω(n; {p prime: q1 | p− 1}) ≤ ω(n; {p prime: 2 | p− 1}).As q1 is the first element of the non-increasing sequence of elementary divisors of n, it holdsunconditionally that Q(n; 2) ≤ Q(n; q1). Thusω(n; {p prime: 2 | p− 1}) + E¯(n; 2) ≤ ω(n; {p prime: q1 | p− 1}) + E¯(n; q1).By combining these two inequalities, it followsω(n; {p prime: 2 | p− 1}) + E¯(n; 2) ≤ ω(n; {p prime: q1 | p− 1}) + E¯(n; q1)≤ ω(n; {p prime: 2 | p− 1}) + E¯(n; q1).Hence by the definition of E¯(n; pα) given in Lemma 2.2 and the difference between ω(n) andω(n; {p prime: 2 | p− 1}) over even n,I(n) = ω(n) + E⋆(n).24It should be noted that the final inequalities in the proof of the preceding lemma constrainthe n for which the prime power q1 where Q(n; q1) is maximal can be a number not equal to2. In particular, it possible to show that for there to be a q1 ̸= 2 for some n, it is necessary(but not sufficient) that 4 ∤ n by reasoning about the values of the ω functions when q1 ̸= 2 andE¯(n; q1) ≥ E¯(n; 2) where E¯ is from Lemma 2.2.2.2 Properties of the Universal Factor Order SetsHaving now expressed the counting function for invariant factors in terms of additive functions, thestructure of the invariant factor order sets will be studied. As these sets are defined in terms of thetotal φ-sequence, this section opens with some lemmata concerning this sequence. The first suchlemma is:Lemma 2.6. If q1 < q2 are prime powers where φ(q1) = φ(q2), then q1 is a prime number.Consequently, at most two distinct prime powers can have the same totient.Proof. Let q1 = pα11 , q2 = pα22 where φ(q1) = φ(q2) and q1 ̸= q2. Observe thatφ(q1) = pα1−11 (p1 − 1) = φ(q2) = pα2−12 (p2 − 1).The first consequence of the above is that p1 = p2 imples α1 = α2 which implies q1 = q2, which,by assumption, is excluded. So p1 ̸= p2 and thus, being primes, implies (p1, p2) = 1.The second consequence of the above is that pα1−11 | p2 − 1 and pα2−12 | p1 − 1 Thus pα1−11 ≤ p2and pα2−12 ≤ p1. If α1 and α2 are both greater than 1, then this implies p1 ≤ p2 and p2 ≤ p1 butsince p1 ̸= p2 this is impossible. Thus exactly one of α1 or α2 must be 1.Let qi be the prime number and qj the other prime power. Since φ(pi) = φ(pαjj ), we obtainthat pi − 1 = pαjj − pαj−1j and thus pi = pαjj − pαj−1j + 1 < pαjj , since αj > 1. So qi < qj and thusq1 = p1 < pα2 = q2.This proves the first sentence of the lemma. The remainder of the lemma follows by the obser-vation that for any three prime powers r1, r2 < r3 where φ(r1) = φ(r2) = φ(r3), the first sentenceof the lemma implies r1 and r2 are primes with the same totient, so they must be equal.An immediate consequence of the above lemma when combined with Definition 1.3 is Proposition1.4. In the introduction, the major results are split based on the size of the invariant factor orderset one is studying and the sizes of the adjacent sets. The next few lemmata will show howcertain relationships between nearby prime powers in the total φ-sequence arise. The first is astraightforward consequence of the preceding lemma:25Lemma 2.7. All finite subsequences of the total φ-sequence of prime powers that contain exactlytwo distinct totient values and all members of the total sequence that have those totient values areof one of four types:Type (1 : 1) qi = pα1 , qi+1 = pβ2 , with φ(qi) < φ(qi+1).Type (1 : 2) qi = pα1 , qi+1 = p2, qi+2 = pβ3 , with φ(qi) < φ(qi+1) = φ(qi+2).Type (2 : 1) qi = p1, qi+1 = pα2 , qi+2 = pβ3 , with φ(qi) = φ(qi+1) < φ(qi+2).Type (2 : 2) qi = p1, qi+1 = pα2 , qi+2 = p3, qi+3 = pβ4 , with φ(qi) = φ(qi+1) < φ(qi+2) = φ(qi+3).Each type can be identified by the sizes of the invariant factor order sets as described below:Table 2.1: Classification of phi SubsequencesSubsequence Totient Values Invariant Factor Order SizesType (1 : 1) φ(qi) < φ(qi+1) #fi−i = #fi = #fi+1 = 1Type (1 : 2) φ(qi) < φ(qi+1) = φ(qi+2) i = 1 or #fi−i = #fi = 1, #fi+1 = 2Type (2 : 1) φ(qi) = φ(qi+1) < φ(qi+2) #fi−i = 2, #fi = #fi+1 = 1Type (2 : 2) φ(qi) = φ(qi+1) < φ(qi+2) = φ(qi+3) #fi−i = #fi+1 = 2, #fi = 1Proof. The four types follows trivially from Definition 1.2 and Lemma 2.6. The classification ofthe types by the sizes of the invariant factor order sets is an immediate consequence of Definition1.3.The next few lemmas will be given with proof in Appendix B, as the proofs are repetitive andinvolve Bertrand’s Postulate. These show that prime powers which share the same totient valuesmust be relatively prime with a finite number of exceptions.Lemma 2.8. If pα1 , pβ2 is a φ(1 : 1)-sequence, then p1 ̸= p2.Lemma 2.9. If pα1 , p2, pβ3 is a φ(1 : 2)-sequence other than 2, 3, 4, then all three primes are distinct.Lemma 2.10. If p1, pα2 , pβ3 is a φ(2 : 1)-sequence, then all three primes are distinct.Lemma 2.11. If p1, pα2 , p3, pβ4 is a φ(2 : 2)-sequence other than 3, 4, 5, 8, then all four primes aredistinct.It should be noted that these four lemmas demonstrate that all but two finite φ-sequencefragments with two totient values (specifically 2, 3, 4 and 3, 4, 5, 8) contain prime powers which arpairwise relatively prime.262.3 Invariant Factors of y-Typical NumbersIn this section, the concept of y-typicality will be properly defined, and the algebraic properties ofnumbers which satisfy this property will be characterized. The key idea in this subsection is that ay-typical number is one where the invariant factors of the multiplicative group of that number caneasily be represented in terms of additive functions.Before delving into this subject in detail, consider the following definition, which relates thenumbers that appear in singleton invariant factor order sets to the indexing of that set:Definition 2.12. We defineV(x) = lcm{pα : φ(pα) ≤ x} and W(y) = #{pα : φ(pα) ≤ x}.It is quite trivial to verify from Lemma 2.6 and Definitions 1.3 and 2.12 that for y ≥ 1, fW(y) ={V(y)}. This observation will be helpful to keep in mind in going through the proofs in this section.Remark. It holds that 0 ≤ logV(x)−Ψ(x)≪ log x log log x, and 0 ≤W(x)−Π(x)≪ log x.Proof of the above remark can be found in Appendix C.We now move on to describing the relationship between the sequence {fi}∞i=1, the function V(x),and arbitrary sequences of prime powers ordered by totient.Proposition 2.13. Let y ≥ 1 and q1, . . . , qN be a sequence of every prime power with totient lessthan or equal to y, ordered such that i < j implies φ(qi) ≤ φ(qj). Let i ≤ N .If φ(qi) < φ(qi+1), thenfi = {V(φ(qi))}.If φ(qi) = φ(qi+1), then{qi, qi+1} = {qi, qi+1},lcm{qj : j ≤ i} ∈ fi.Finally,fN = {V(y)}.Proof. First note that for any i ≤ N , φ(qi) = φ(qi) since both sequences are ordered by totient andcontain exactly the same elements up to N .If φ(qi) < φ(qi+1), it follows there are exactly i prime powers with totients less than or equalto φ(qi). Thus φ(qi) = φ(qi), and soV(φ(qi)) = V(φ(qi)) = lcm{r a prime power : φ(r) ≤ φ(qi)} = lcm{qj : j ≤ i}.27Thus {V(φ(qi))} = fi.If φ(qi) = φ(qi+1), then by Lemma 2.6 it follows qi, qi+1 are the only prime powers with totientequal to φ(qi). Asφ(qi) = φ(qi) = φ(qi+1) = φ(qi+1),it follows that {qi, qi+1} = {qi, qi+1}. Furthermore, since only one prime power has the minimaltotient of 1, it follows that i > 1 and φ(qi−1) < φ(qi). Thus by the previous parts of this proof,lcm{qj : j ≤ i} = lcm({qj : j ≤ i− 1}, qi)= lcm({qj : φ(qj) ≤ φ(qi−1)}, qi)= lcm(V(φ(qi−1), qi))= lcm(fi−1, qi)=lcm(fi−1, qi) if qi = qi,lcm(fi−1, qi+1) if qi = qi+1,∈ fi.For the final step, simply observe that q1, . . . , qN contains exactly all prime powers with totientless than or equal to y. Thus there are exactly N prime powers with totients less than or equal toy and thusV(y) = lcm{r a prime power : φ(r) ≤ y} = lcm{q1, . . . , qN}Hence {V(y)} = fN .This leads to the final and most important result of this section. The following proposition givesa condensed summary of all the algebraic properties a y-typical number has. The central intuitionof the following proposition is that the invariant factors of the multiplicative group of a y-typicalnumber can be represented with a simple formula that can be represented in terms of additivefunctions.Proposition 2.14. Let y ≥ 1 and n be an y-typical number.Then it follows1. There exists a sequence 2 = q1, . . . , qN of every prime power with totient less than or equal toy, ordered such that i < j implies φ(qi) ≤ φ(qj) and Q(n; qi) ≥ Q(n; qj).2. There exists a list 2 = d1, . . . , dN = V(y) that contains every invariant factor of (Z/nZ)×less than V(y), ordered such that i < j implies di | dj. Furthermore, fN = {dN}.3. If d is an invariant factor of (Z/nZ)× greater than V(y), then V(y) | d.284. For 1 ≤ i < N , if φ(qi) < φ(qi+1) then di = V(φ(qi)).5. For 1 ≤ i < N , di ∈ fi.6. Let Qi = {p : qi | p− 1}. Then for 1 ≤ i < N ,I(n; di) = Q(n; qi)−Q(n; qi+1) = ω(n;Qi −Qi+1) + E¯(n; qi)− E¯(n; qi+1),where E¯ is the function defined in Lemma 2.2. Furthermore, I(n; dN ) ≤ ω(n;QN )+E¯(n; qN ).Proof. Let P (y) = {q ∈ N : q is a prime power, φ(q) ≤ y}.Let N ∈ N be the number of elements in P (y), which is trivially finite. As n is y-typical, thereare no elements r1, r2 ∈ P (y) such that φ(r1) < φ(r2) and Q(n; r1) < Q(n; r2). Thus it is possibleto order P (y) so that φ is non-decreasing and Q is non-increasing. This proves the existence of thesequence q1, . . . , qN in property 1.Observe that as y ≥ 1 and φ(2) = 1, it follows 2 ∈ P (x), and since all other prime powers havea greater totient, q1 = 2. This completes the proof of property 1.Now observe that if q ̸∈ P (y), then φ(q) > y ≥ φ(qN ). Since n is y-typical, this implies thatQ(n; q) < Q(n; qN ).Thus n and q1, . . . , qN satisfy the conditions of Lemma 2.4 and it follows that fordi = lcm{qj : j ≤ i}for 1 ≤ i ≤ N , we have for 1 ≤ i < N thatI(n; di) = Q(n; qi)−Q(n; qi+1)and I(n; dN ) ≤ Q(n; qN ). Additionally, d1, . . . , dN contains every distinct invariant factor of(Z/nZ)× less than or equal to dN .By the definition of d1, . . . , dN , if i < j, it follows di | dj .Furthermore, we have that dN = lcm{qj : j ≤ N} = lcmP (y) = V(y) by Definition 2.12,and that {V(y)} = fN by property (1) and Proposition 2.13. Likewise, d1 = lcm{qj : j ≤ 1} =lcm{q1} = q1 = 2. This completes the proof of property 2.Observe that by Lemma 2.4, any invariant factor d of (Z/nZ)× where d > dN is such thatdN | d. Since property 2 gives that dN = V(y), property 3 follows immediately.If 1 ≤ i < N and φ(qi) < φ(qi+1), then by property 1 and Proposition 2.13,di = lcm{qj : j ≤ i}= lcm{qj : φ(qj) ≤ φ(qi)}= V(φ(qi)) ∈ fi.29This completes the proof of property 4 and part of property 5.If 1 < i < N and φ(qi) = φ(qi+1), we have by property 1 and Proposition 2.13 that di ∈ fi.This completes the proof of property 5.Let Q1, . . . , QN be the sets defined earlier. In the course of proving property 2, it was foundthatI(n; di) = Q(n; qi)−Q(n; qi+1).Thus by Lemma 2.2, we have thatI(n; di) = ω(n;Qi)− ω(n;Qi+1) + E¯(n; qi)− E¯(n; qi+1)for 1 ≤ i < N . By noting that ω(n;Qi)− ω(n;Qi+1) = ω(n;Qi −Qi+1), and thatI(n; dN ) ≤ Q(n; qN ) ≤ ω(n;QN ) + E¯(n; qN ),the proof of property 6 is completed.This concludes the examination of the algebraic properties of y-typical numbers. The study ofthe frequency of y-typical numbers (and the justification for why they are typical) can be found inChapter 4.30Chapter 3From Additive Functions toProbability Distributions3.1 Concepts from KubiliusIn this work, the notation of Kubilius [7], with slight modification for clarity, will be used to discussthe properties of additive functions. This is due to a fairly elegant result from [7] concerning jointdistributions of multiple additive functions.The following definitions encode information about the mean and variance of additive functions:Definition 3.1 (Special Functions). Let f : N→ R be any real additive function.Then we define Af , Bf , Df , and Cf , which map R→ R asAf (x) =∑p≤xf(p)p,Bf (x) =(∑p≤x|f(p)|2p)1/2,Df (x) =( ∑pα≤xf(pα)2pα)1/2,Cf (x) = max{|f(pα)| : pα ≤ x, pα is a prime power}.In cases where the additive function takes additional parameters, the corresponding A,B,D,Cfunctions will also take those parameters.It is also necessary to define the class of additive functions for which the results of Kubiliushold:31Definition 3.2 (The Class H). The class H is the set of real additive functions f for whichlimn→∞Df (n) =∞ and for which there exist an unbounded increasing function r = r(n) such thatlimn→∞log rlog n= 0 and limn→∞Df (r)Df (n)= 1For strongly additive functions, one has that limn→∞Bf (n) =∞ and limn→∞Bf (r)/Bf (n) = 1instead of Df (n).As this work is concerned with limiting distributions, it should be no surprise that the resultsfrom Kubilius that are needed here concern limiting distributions of additive functions. The firstlemma gives the limiting distribution of a one variable additive function under appropriate scaling:Lemma 3.3 (Theorem 4.1 of [7]). Let f(m) be a strongly additive function of the class H. Thenlimn→∞Pn{f(m)−Af (n)Bf (n)< x}converges to a limiting cumulative distribution function F (x) of a random variable X with variance1 if and only if there exists a nondecreasing function K(u) of unit variation such that at all pointsof continuity of K,K(u) = limn→∞1Bf (n)2∑p≤nf(p)<uBf (n)f2(p)p.The logarithm of the characteristic function of X islogφX(t) =∫ ∞−∞(eitu − 1− itu) 1u2dK(u).with the integrand being −t2/2 at u = 0.Note that the variation of a real-valued function K is given by sup∑Ni=1 |K(ui)−K(ui+1)| overall non-decreasing finite sequences of real numbers u1, . . . , uN . Unit variation indicates only thatthe variation of the function is 1. In the case of a non-decreasing function, variation simplifiesto sup |K(u1) −K(uN )| which equals limu→∞ |K(u) −K(−u)|. The particular K(u) described inLemma 3.3 is by the definition of the limit clearly bounded between 0 and 1, so a non-decreasingK(u) of unit variation has a range which either contains 0 and 1 or has them as limit points.The second lemma from Kubilius gives the joint limiting distribution of a finite number ofadditive functions under the same scaling:Lemma 3.4 (Theorem 8.1 of [7]). Let f1(m), . . . , fs(m) be strongly additive functions of the classH. ThenF (x1, . . . , xs) = limn→∞Pn{f1(m)−A1(n)B1(n)< x1, . . . ,fs(m)−As(n)Bs(n)< xs}32is the cumulative distribution function of a random vector Y which exists at each of its nonexcep-tional points if and only if (1) there exists a non-negative completely additive set function Q(E)defined for all Borel sets that do not contain the origin, (2) a constant vector Γ, and (3) a non-negative quadratic form of s variables σ(T ) with finite coefficients such that (1), (2), and (3) satisfy1. For every interval of continuity I, 0 ̸∈ I¯ of the function Q(E),limn→∞∑p≤nLn(p)∈I1p= Q(I),whereLn(p) =(f1(p)B1(n), . . . ,fs(p)Bs(n)).2.− limn→∞∑p≤n|Ln(p)|2p(1 + |Ln(p)|2)Ln(p) = Γ.3.limϵ→0+limn→∞∑p≤n|Ln(p)|<ϵ1p(T · Ln(p))2= σ(T ).Furthermore, the logarithm of the characteristic function of Y islogφY (T ) = iΓT − 12σ(T ) +∫|X|>0(eiTX − 1− iTX1 + |X|2)dQ.An exceptional point in the above statement refers to any point where any of the random vector’scomponent’s cumulative distribution function is discontinuous.In [7], the conversion from bounds in terms of Df to bounds in terms of Bf is treated as anafterthought. For the sake of clarity in this work, the relation is stated explicitly with proof:Lemma 3.5. Let f be an additive function. Then|Df (n)2 −Bf (n)2| ≪ Cf (n)2,where the implicit constant and threshold do not depend on f . Furthermore, if f is a stronglyadditive function,Bf (n)2 ≤ Df (n)2 ≤ 2Bf (n)2.33Proof. Observe thatDf (n)2 =∑pα≤nf(pα)2pα=∑p≤nf(p)2p+∑pα≤nα≥2f(pα)2pα= Bf (n)2 +O(Cf (n)2∑pα≤nα≥21pα)= Bf (n)2 +O(Cf (n)2∑p≤n∞∑α=21pα)= Bf (n)2 +O(Cf (n)2∑p≤n1p211− 1/p)= Bf (n)2 +O(Cf (n)2).For the strongly addtive case, note that Bf (n)2 ≤ Df (n)2 is trivial and since 2 ≤ p we have thatp ≤ 2(p− 1) and thusDf (n)2 =∑pα≤nf(pα)2pα=∑pα≤nf(p)2pα≤∑p≤nf(p)2p∞∑α=01pα≤∑p≤nf(p)2p11− 1/p≤∑p≤nf(p)2p− 1≤∑p≤n2f(p)2p≤ 2Bf (n)2.This completes the proof.The next lemma will be an adaptation of Lemma 4.2 and 4.3 from [7] (focusing on Cf instead ofDf or Bf ) with clarity on how certain implicit constants depend on the choice of additive function.34For the following lemmas in this section and their proofs, we defineρ(pα) =1pα(1− 1p), and Π(n) =∑pα≤n1.Note that|#{m ≤ n : pα ∥ m} − nρ(pα)| ≤ 2.The first lemma adapted is:Lemma 3.6. Let f be an additive function. Then∣∣∣∣ ∑pα≤nf(pα)pα+1∣∣∣∣≪ Cf (n),and ∣∣∣∣ ∑pα≤nf(pα)n∣∣∣∣≪ Π(n)n Cf (n),and ∣∣∣∣En(f(m))− ∑pα≤nf(pα)ρ(pα)∣∣∣∣≪ Π(n)n Cf (n)≪ Cf (n)log n ,and ∣∣∣∣En(f(m))−Af (n)∣∣∣∣≪ Cf (n),where the implicit constants for all four equations are absolute, as is the threshold for “sufficientlylarge.”Proof. In this proof, all implicit constants are absolute.We prove the first equation by noting that f(1) = 0, so∣∣∣∣ ∑pα≤nf(pα)pα+1∣∣∣∣ ≤ ∑pα≤n|f(pα)|pα+1≤ Cf (n)∑pα≤nα≥11pα+1≤ Cf (n)∑p≤n∑1≤α≤logn/ log p1pα+1≤ Cf (n)∑p≤n1p2∞∑α=01pα≤ Cf (n)∑p≤n1p211− 1/p≪ Cf (n).35The second equation is straightforward.∣∣∣∣ ∑pα≤nf(pα)n∣∣∣∣ ≤ ∑pα≤n|f(pα)|n≤ 1nCf (n)∑pα≤n1≤ Π(n)nCf (n).We prove the third equation by means of the second.En(f(m)) =1nn∑m=1f(m)=1n∑pα≤nf(pα)#{m ≤ n : pα ∥ m}=1n∑pα≤n(f(pα)nρ(pα) +O(|f(pα)|)=∑pα≤nf(pα)ρ(pα) +O( ∑pα≤n|f(pα)|n)=∑pα≤nf(pα)ρ(pα) +O(Π(n)nCf (n)).The fourth equation follows from the first and third equation.En(f(m) =∑pα≤nf(pα)ρ(pα) +O(Π(n)nCf (n))= Af (n) +∑pα≤nα≥2f(pα)pα−∑pα≤nf(pα)pα+1+O(Π(n)Cf (n)/n)= Af (n) +O(∑p≤n∞∑α=2Cf (n)pα)+O(Cf (n))= Af (n) +O(Cf (n)∑p≤n1p211− 1/p)+O(Cf (n))= Af (n) +O(Cf (n)).This completes the proof.The second lemma adapted is based on Lemma 4.4 of [7]:36Lemma 3.7. Let f1, f2 be additive functions in class H where D1(n) = Df1(n) and D2(n) =Df2(n). Furthermore, let C1(n) = Cf1(n) and C2(n) = Cf2(n). Then,1n∑m≤nf1(m)f2(m)−En(f1(m))En(f2(m)) =∑pα≤nf1(pα)f2(pα)pα+O(C1(n)C2(n))where the implicit constants are absolute, as is the threshold for “sufficiently large.”Proof. To begin, observe thatn∑m=1f1(m)f2(m) =∑pα≤nqβ≤nf1(pα)f2(qβ)#{m ≤ n : pα ∥ m, qβ ∥ m}.If pα, qβ ∥ m, it follows that so does the least common multiple, and thus#{m ≤ n : pα ∥ m, qβ ∥ m} − nlcm(pα, qβ)≪ 1where the implicit constant is clearly bounded by 1. Furthermore, if lcm(pα, qβ) > n then clearlythere are no solutions.Thus it follows that#{m ≤ n : pα ∥ m, qβ ∥ m} = #{m ≤ n : pα | m, qβ | m}−#{m ≤ n : pα+1 | m, qβ | m} −#{m ≤ n : pα | m, qβ | m}+#{m ≤ n : pα+1 | m, qβ+1 | m}.Thus, Kubilius obtains from the above that#{m ≤ n : pα ∥ m, qβ ∥ m} =nρ(pα)ρ(qβ) +O(1) if p ̸= q, pαqβ ≤ n0 if p ̸= q, pαqβ > n,0 if p = q, α ̸= β,nρ(pα) +O(1) if p = q, α = β.where the implicit constant is clearly 4.Thus it is possible to rewrite the product sum as the following composite sum,n∑m=1f1(m)f2(m) = nΣ1 +O(Σ2) + nΣ3 +O⋆(Σ4)withΣ1 =∑pαqβ≤np̸=qf1(pα)f2(qβ)ρ(pα)ρ(qβ),37andΣ2 =∑pαqβ≤np̸=q|f1(pα)f2(qβ)|,andΣ3 =∑pα≤nf1(pα)f2(pα)ρ(pα),andΣ4 =∑pα≤n|f1(pα)f2(pα)|.Again, the implicit constant here is clearly bounded by 4.1. First, we bound Σ2. As in [7, pg. 53] there exists a constant L1 such that∑pαqβ≤n1 ≤ L1n(log n)−1/3.Thus, it follows that|Σ2| ≤ C1(n)C2(n)∑pαqβ≤n1≪ n(logn)−1/3C1(n)C2(n).2. For Σ3, it follows by the same argument used to prove the first equation in Lemma 3.6 that∣∣∣∣Σ3 − ∑pα≤nf1(pα)f2(pα)pα∣∣∣∣ ≤ ∑pα≤n∣∣∣∣f1(pα)f2(pα)pα+1∣∣∣∣≤ C1(n)C2(n)∑pα≤n1pα+1≪ C1(n)C2(n),where the implicit constant and “sufficiently large” threshold are absolute.3. Observe that trivially,|Σ4| ≤∑pα≤n|f1(pα)f2(pα)| ≤∑pα≤nC1(n)C2(n) ≤ Π(n)C1(n)C2(n).384. Observe that f1(1) = f2(1) = 0, and so α, β ≥ 1 and thus it follows that∣∣∣∣ ∑pαqβ≤np=qf1(pα)f2(qβ)ρ(pα)ρ(qβ)∣∣∣∣ ≤ ∑pαqβ≤np=q|f1(pα)f2(qβ)|pαqβ≤∑pα+β≤nα,β≥1C1(n)C2(n)pα+β≤ C1(n)C2(n)∑p≤n∞∑α=1∞∑β=11pα+β≤ C1(n)C2(n)∑p≤n1p2∞∑α=01pα∞∑β=01pβ≤ C1(n)C2(n)∑p≤n1p2(11− 1/p)2≪ C1(n)C2(n),where it is clear from the convergence of the above sequence that the implicit constant andthreshold for “sufficiently large” is absolute. Thus it follows thatΣ1 =∑pαqβ≤nf1(pα)f2(qβ)ρ(pα)ρ(qβ) +O(C1(n)C2(n)).Thus we obtain thatn∑m=1f1(m)f2(m) = n∑pαqβ≤nf1(pα)f2(qβ)ρ(pα)ρ(qβ) + n∑pα≤nf1(pα)f2(pα)pα+O(nC1(n)C2(n)),with an absolute implicit constant. Now, by Lemma 3.6,(Enf1(m))(Enf2(m)) =( ∑pα≤nρ(pα)f1(pα) +O(C1(n)log n))×( ∑pα≤nρ(pα)f2(pα) +O(C2(n)log n))=∑pα,qβ≤nf1(pα)f2(qβ)ρ(pα)ρ(qβ)+O(C1(n)C2(n)(log logn)/ logn)+O(C1(n)C2(n)(log n)−2)=∑pα≤n∑qβ≤nf1(pα)f2(qβ)ρ(pα)ρ(qβ)+O(C1(n)C2(n)(log logn/ logn)).39Thus it follows that1nn∑m=1f1(m)f2(m)− (Enf1(m))(Enf2(m)) =∑pα≤nf1(pα)f2(pα)pα− Σ5 +O(C1(n)C2(n)),whereΣ5 =∑pαqβ>npα,qβ≤nf1(pα)f2(qβ)ρ(pα)ρ(qβ).By equation 3.7 of [7], it follows immediately that∑pαqβ>npα,qβ≤n1pαqβ≪ 1,and thus,|Σ5| ≤ C1(n)C2(n)∑pαqβ>npα,qβ≤n1pαqβ≪ C1(n)C2(n).Thus we obtain that1nn∑m=1f1(m)f2(m)− (Enf1(m))(Enf2(m)) =∑pα≤nf1(pα)f2(pα)pα+O(C1(n)C2(n)),thus completing the proof.This concludes the results taken from or adapted from [7].3.2 Sums of Reciprocals of PrimesTo apply the results of Kubilius to the counting functions for primes in arithmetic progressions,asymptotic formulas of the sizes of sums of reciprocals of primes in arithmetic progression areneeded. This section contains an upper bound and an asymptotic formula for reciprocals of primesin arithmetic progressions of the form p ≡ a mod q, with the dependence of all error terms on qmade explicit.The first is an upper bound which is based on the Brun–Tichmarsh inequality.Lemma 3.8. Let q, a ∈ N, with (q, a) = 1, x ∈ R with x ≥ 2q, and 0 ≤ α < log(2q). Then∑p≤xp≡a mod qlogα pp≤ 2φ(q)(logα xlog(x/q)+(1 +log qlog 2)F (x; q, α))+R(q, a, α)40whereF (x; q, α) = 1α (logα x− logα 2q) if α ̸= 0,log log x− log log(2q) if α = 0,andR(q, a, α) =( ∑p≤2qp≡a mod qlogα pp)− π(2q; q, a) logα(2q)2q.In the special case where q ≥ 2 and a is not a prime number, R(q, a, α) ≤ 2α logα qq .Proof. For shortand, let F (x) = F (x; q, α) and R = R(q, a, α). Observe that by the definition givenabove,F (x) =∫ x2qlogα−1 uudu.By the Brun–Tichmarsh inequality [9, Theorem 2],π(y; q, a) ≤ 2yφ(q) log(y/q)for all y ≥ 2q. Thus as α− log u < 0 for all u ≥ 2q,∑p≤xp≡a (mod q)logα pp=∑p≤2qp≡a mod qlogα pp+∫ x+2q+logα uudπ(u; q, a)=∑p≤2qp≡a mod qlogα pp+π(x; q, a) logα xx− π(2q; q, a) logα(2q)2q−∫ x+2q+π(u; q, a) logα−1 u(α− log u)u2du≤ 2 logα xφ(q) log(x/q)+∫ x2q2uφ(q) log u/q· logα−1 u(log u− α)u2du+R≤ 2 logα xφ(q) log(x/q)+2φ(q)∫ x2qlogα−1 u(log u− α)u log(u/q)du+R≤ 2φ(q)(logα xlog(x/q)+∫ x2qlogα−1 uu∞∑k=0( log qlog u)kdu)+R≤ 2φ(q)(logα xlog(x/q)+∫ x2qlogα−1 uu(1 +log qlog u∞∑k=0( log qlog u)k)du)+R≤ 2φ(q)(logα xlog(x/q)+∫ x2qlogα−1 uu(1 +log qlog 2)du)+R≤ 2φ(q)(logα xlog(x/q)+(1 +log qlog 2)F (x))+R.41For the special case, simply observe that since a is not prime, the only possible prime powercongruent to a modulo q in the positive sum is q + a, so R ≤ logα(q + 1)/q ≤ 2α logα q/q, with thefinal inequality holding for q ≥ 2.The second result is an asymptotic equality with bounds uniform in q based on the prime numbertheorem.Lemma 3.9. Let q, a ∈ N be relatively prime with q ≥ 2, and r ≥ 2 a real number less than orequal to the first prime number equivalent to a modulo q. Then for x ≥ r,∑p≤xp≡a mod q1p=log log xφ(q)− log log rφ(q)+O(√q log2 qφ(q)+1φ(q) log r+ exp(−c1√log r)√log r),where c1 > 0 is an absolute constant, and the implicit constant is uniform in x, q, a, and r.Furthermore, when r = 2 and q is a prime power,∑p≤xp≡a mod q1p=log log xφ(q)+O(1),and when a < q is not prime and r = q is a prime power,∑p≤xp≡a mod q1p=log log xφ(q)+O(exp(−c1√log q)√log q).Proof. We make use of the standard prime number theorem for arithmetic progressions [10, Corol-lary 11.20], which states there exists a constant c1 > 0 such thatπ(x; q, a) =li(x)φ(q)− χ(a) li(xβ)φ(q)+O(x exp(−c1√log x)),where χ is the exceptional character modulo q if it exists and identically zero otherwise, and β thecorresponding exceptional zero or 1/2 if there is no exceptional character modulo q.Thus,∑p≤xp≡a mod q1p=∫ x+r−1udπ(u; q, a)=π(x; q, a)x+∫ x+r−π(u; q, a)u2du=1φ(q)(li(x)x− χ(a) li(xβ)x+∫ xrli(u)u2du− χ(a)∫ xrli(uβ)u2du)+O(exp(−c1√log x))+O(∫ xrexp(−c1√log u)udu).42As is well known,li(x) =xlog x+O(xlog2 x),and it is clear, ∫ xr1u log2 udu ≤ 1log r.and that∫ xrexp(−c1√log u)udu = 2∫ √log r√log rv exp(−c1v) dv=2c1(exp(−c1√log r)√log r − exp(−c1√log x)√log x+∫ √log x√log re−c1v dv)≤ 2c1(exp(−c1√log r)√log r +exp(−c1√log r)c1)and that finally by [10, Corollary 11.12], there exists an absolute constant c2 > 0 such that11− β ≤q1/2(log q)2c2it follows∑p≤xp≡a mod q1p=1φ(q)(1log x− χ(a)xβ−1β log x+∫ xr1u log udu− χ(a)β∫ xruβ−2log udu+O(1log2 x)+O(∫ xr1u log2 u))+O(exp(−c1√log x)) +O(exp(−c1√log r)√log r)=1φ(q)(log log x− log log r − χ(a)β∫ xruβ−2log udu+O(1log x) +O(1log r))+O(exp(−c1√log r)√log r)=1φ(q)(log log x− log log 2 +O( 1β log 2∫ uruβ−2 du)+O(1log r))+O(exp(−c1√log r)√log r)=1φ(q)(log log x− log log 2 +O( rβ−1β(1− β) log 2)+O(1log r))+O(exp(−c1√log r)√log r)=1φ(q)(log log x− log log 2 +O(q1/2(log q)2) +O( 1log r))+O(exp(−c1√log r)√log r).Noting that 1φ(q) ≪ 1q when restricted to prime powers, the rest of the lemma follows immediately.Both of the above lemmata will be necessary in the proofs that follow.433.3 Application of Kubilius to the Relevent Additive Func-tionsIn this subsection, the techniques of Kubilius are used to explore the properties of ω(n;S) andω(n;S − T ). This will form the bridge between additive functions and probability distributions.Given that the previous section bridged invariant functions and additive functions, the cumulativeeffect at the end of this section will be the ability to obtain limiting distributions for the additivefunctions which arise in the study of invariant factors. However, this will not be quite enough toprove the primary theorem, as work will be needed to translate the multivariate distributions foundin this section into univariate distributions for the invariant factors themselves.With all that said, the study of the key additive functions using the techniques of Kubilius canbegin. Observe that as ω(n;S) is a strongly additive function, from Definition 3.1 it followsAω(x;S) = Bω(x;S)2 =∑p≤x1S(p)p.Similarly, for ω(n;S − T ),Aω(x;S − T ) = Aω(x;S)−Aω(x;T ), Bω(x;S − T )2 =∑p≤x1S△Tp.In this equation, and later on, note that △ denotes the symmetric difference between sets. Alsonote that ω(n;S−∅) = ω(n;S). These two observations will be necessary to understand the proofsthat follow.Likewise, the following definition will be used in many proofs:Definition 3.10. We shall say that a subset of the set of all primes has a Dirichlet density of d(S)provided the limitd(S) = limx→∞1log log x∑p≤x1S(p)pexists.Note that for any µ ∈ (0, 1], d(S) = µ if and only if µ log log x ∼ Aω(x;S) = Bω(x;S)2.With these preliminary observations and definitions out of the way, the first result can be stated.As the results of Kubilius primarily apply to additive functions in class H, it becomes necessary toprove that ω(n;S − T ) lies in class H.Lemma 3.11. Let S, T be subsets of the set of all primes where S△T has non-zero Dirichletdensity. Then ω(n;S − T ) is in class H.44Proof. First, observe that ω(n;S − T ) is a strongly additive function by definition.Now, observe that since S△T has non-zero Dirichlet density andBω(x;S − T ) =(∑p≤x1S△T (p)p)1/2we have that lim infx→∞Bω(x;S−T )2log log x > 0 and thuslimx→∞Bω(x;S − T ) =∞.Let r = r(n) = n1/ log logn. Trivially, limn→∞ log r/ logn = limn→∞ 1/ log log n = 0. Further-more, r(n)→∞ as log n/ log log n→∞.However, since S△T has non-zero Dirichlet density, we obtain that(Bω(r;S − T )Bω(n;S − T ))2∼ log log(n1/ log logn)log logn=log log n− log log lognlog logn∼ 1,solimn→∞Bω(r;S − T )Bω(n;S − T ) = 1.Thus ω(n;S − T ) is in class H.Trivially note that this implies ω(n;S) is in class H for any S with non-zero Dirichlet density,since ω(n;S − ∅) = ω(n;S). This leads to the following lemma:Lemma 3.12. Let q, a ∈ N be relatively prime, with q ≥ 2. Then for Q = {p : p ≡ a mod q},d(Q) = 1φ(q) , and ω(n;Q) is in class H.Proof. To obtain the Dirichlet density, observe that by Lemma 3.9,limx→∞1log log x∑p≤x1Q(p)p=1φ(q).To show ω(n;Q) is in class H, apply 3.11 to Q− ∅ = Q.While the primary tool used in our proofs will concern multivariate limiting distributions, theunivariate distributions also matter. The limiting distribution for ω(n;S − T ) can be stated asfollows:Lemma 3.13. Let S, T be subsets of the set of all primes such that ω(n;S−T ) is in class H. ThenF (x) = limn→∞Pn(ω(m;S − T )−Aω(n;S − T )Bω(n;S − T ) < x)is the cumulative distribution function of a random variable X with normal distribution, mean 0,and variance 1.45Proof. By Lemma 3.12, one can apply Lemma 3.3 to ω(n;S − T ).For u > 0, the properties of class H imply that uBω(n;S − T )→∞ as n→∞, and thusK(u) = limn→∞1Bω(n;S − T )2∑p≤nω(p;S−T )<uBω(n;S−T )ω(p;S − T )2p= limn→∞1Bω(n;S − T )2∑p≤n1S△T (p)p= limn→∞Bω(n;S − T )2Bω(n;S − T )2 = 1 if u > 0.Likewise, for u < 0, observe that uBω(n;S−T )→ −∞ as n→∞ and thus since ω(p;S−T ) ≥−1,K(u) = limn→∞1Bω(n;S − T )2∑p≤nω(p;S−T )<uBω(n;S−T )ω(p;S − T )2p= 0 if u < 0.Thus there is a K(u) meeting the criteria of Lemma 3.3 and thus we have that F (x) is thecumulative distribution function of a random variable X. By evaluating the integral, we see thatdK(u) gives weight 1 when u = 0 and weight 0 everywhere else, soφX(t) = exp(−t2/2)and thus X has a normal distribution with mean 0 and variance 1.The multivariate version of the above lemma is essential to later proofs:Lemma 3.14. Let Q1, . . . , Qs and R1, . . . , Rs be subsets of the set of all primes such that eachQi△Ri has a non-zero Dirichlet density, and all pairwise intersections of the Qi and Ri sets havea Dirichlet density (including self-intersections). ThenF (x1, . . . , xs) = limn→∞Pn{ω(m;Q1 −R1)− (d(Q1)− d(R1)) log log n(d(Q1△R1) log log n)1/2 < x1, . . .. . . ,ω(m;Qs −Rs)− (d(Qs)− d(Rs)) log log n(d(Qs△Rs) log log n)1/2 < xs}is the cumulative distribution function (with domain Rs) of a random vector X with characteristicfunctionφX(t1, . . . , ts) = exp(−σ(t1, . . . , ts)/2)46whereσ(t1, . . . , ts) =s∑i=1s∑j=1d(Qi ∩Qj) + d(Ri ∩Rj)− d(Qi ∩Rj)− d(Ri ∩Qj)(d(Qi△Ri)d(Qj△Rj))1/2 titj .Note that when i = j the summands on the right hand side of σ(t1, . . . , ts) evaluate to 1.Proof. We shall apply Lemma 3.4. First note that by assumption and Lemma 3.11 our ω functionsare in class H.For ω(m;Q1−R1), . . . , ω(m;Qs−Rs), one obtains from the mean and variance that the vectorLn(p) =(1Q1(p)− 1R1(p)Bω(n;Q1 −R1) , . . . ,1Qs(p)− 1Rs(p)Bω(n;Qs −Rs))so as d(Qi△Ri) exists for 1 ≤ i ≤ s and is non-zero it follows Bω(n;Qi−Ri)2 ∼ d(Qi△Ri) log log n,and since |1Qi(p) − 1Ri(p)| ≤ 1, it is clear that for all ϵ > 0, there exists an N ∈ N such that forn ≥ N and all primes p, |Ln(p)| < ϵ. Hence limn→∞ |Ln(p)| = 0 uniformly in p.Thus Q(E) = 0 for all intervals E ⊆ Rs whose closure does not contain the origin. This satisfies(1).Let Un(p) = (log logn)|Ln(p)|2. As Bω(n;Qi − Ri)2 ∼ d(Qi△Ri) log log n for 1 ≤ i ≤ s andthus|Ln(p)|2 =s∑i=11Qi△Ri(p)Bω(n;Qi −Ri)2 ≪slog logn.Thus one has for the vector Γ that−Γ = limn→∞∑p≤n|Ln(p)|2p(1 + |Ln(p)|2)Ln(p)= limn→∞∑p≤nUn(p)p(log logn+ Un(p))Ln(p)= limn→∞∑p≤nUn(p)p log log nLn(p)= limn→∞1log logn∑p≤nUn(p)Ln(p)p= 0.The final step can be easily seen as it is clear that the division of the sum by log log n cancels outthe growth over the sum of the reciprocals of primes up to n, Un(p) = O(s), and the componentsof the vector Ln(p) are O((log log n)−1/2).47As described above |Ln(p)| → 0 as n → ∞ uniformly in p, so for any fixed ϵ > 0 there existssome N such that for all n ≥ N and primes p, |Ln(p)| < ϵ. Thus for T = (t1, . . . , ts) ∈ Rs,σ(T ) = limϵ→0+limn→∞∑p≤n|Ln(p)|<ϵ1p(T · Ln(p))2= limn→∞∑p≤n1p(T · Ln(p))2= limn→∞∑p≤n1p( s∑i=11Qi(p)− 1Ri(p)(d(Qi△Ri) log log n)1/2 ti)2= limn→∞∑p≤n1p log log n·s∑i=1s∑j=11Qi(p)1Qj (p) + 1Ri(p)1Rj (p)− 1Qi(p)1Rj (p)− 1Ri(p)1Qj (p)(d(Qi△Ri)d(Qj△Rj))1/2 titj= limn→∞s∑i=1s∑j=11log logn∑p≤n1p1Qi∩Qj (p) + 1Ri∩Rj (p)− 1Qi∩Rj (p)− 1Ri∩Qj (p)(d(Qi△Ri)d(Qj△Rj))1/2 titj=s∑i=1s∑j=11(d(Qi△Ri)d(Qj△Rj))1/2· limn→∞1log log n∑p≤n1Qi∩Qj (p)1Ri∩Rj (p)− 1Qi∩Rj (p)− 1Ri∩Qj (p)ptitj=s∑i=1s∑j=1d(Qi ∩Qj) + d(Ri ∩Rj)− d(Qi ∩Rj)− d(Ri ∩Qj)(d(Qi△Ri)d(Qj△Rj))1/2 titj .In the case of the sum where i = j, note thatd(Qi ∩Qi) + d(Ri ∩Ri)− 2d(Qi ∩Ri) = d(Qi△Ri)so the coefficients for the terms of σ where i = j are always 1.Thus by Lemma 3.4, F (x1, . . . , xs) is the cumulative distribution function of a random vectorX and the logarithm of the characteristic function of X islogφX(t1, . . . , ts) = −12σ(t1, . . . , ts)with σ(t1, . . . , ts) as described above.As each component of the random vector X has a normal distribution by Lemma 3.13, thereare no exceptional points, which completes the proof.The results of this section will be finished with a quick statement about ω functions as randomvariables in finite probability spaces.48Lemma 3.15. For any subsets S, T of the set of all prime natural numbers it holds thatEnω(m;S − T ) = Aω(n;S − T ) +O(1),and thatEn(ω(m;S − T )2)− (Enω(m;S − T ))2 = Bω(n;S − T )2 +O(1),and furthermore thatEn((ω(m;S − T )−Aω(n;S − T ))2)≪ Bω(n;S − T )2 +Aω(n;S − T ) + 1,where the implicit constants for all three equations are absolute.Proof. First, note that for any choice of S, T , it follows 0 ≤ Cω(n;S−T ) ≤ 1. Thus by Lemma 3.6,Enω(m;S − T ) = Aω(n;S − T ) +O(Cω(n;S − T )2) = Aω(n;S − T ) +O(1),where the implicit constant is absolute. Furthermore, by Lemmata 3.7 and 3.5,En(ω(m;S − T )2)− (Enω(m;S − T ))2 = Dω(n;S − T )2 +O(Cω(n;S − T )2)= Bω(n;S − T )2 +O(Cω(n;S − T )2) = Bω(n;S − T )2 +O(1),where the implicit constant is absolute.By combining the two equations, we obtain thatEn((ω(m;S − T )−Aω(n;S − T ))2)= En(ω(m;S − T )2 − 2Aω(n;S − T )ω(m;S − T ) +Aω(n;S − T )2)= En(ω(m;S − T )2)−Aω(n;S − T )2 +O(Aω(n;S − T ))= En(ω(m;S − T )2)− (Enω(m;S − T ) +O(1))2 +O(Aω(n;S − T ))= En(ω(m;S − T )2)− (Enω(m;S − T )2 +O(Aω(n;S − T ) +Enω(m;S − T ) + 1)= En(ω(m;S − T )2)− (Enω(m;S − T ))2 +O(Aω(n;S − T ) + 1)= Bω(n;S − T )2 +O(Aω(n;S − T ) + 1).Hence,En((ω(m;S − T )−Aω(n;S − T ))2)≪ Bω(n;S − T )2 +Aω(n;S − T ) + 1.Note for now that σ(X) can be naturally seen as either a quadratic form or as an expression ofthe form XTMX where M is a symmetric matrix with entry i, j beingd(Qi ∩Qj) + d(Ri ∩Rj)− d(Qi ∩Rj)− d(Ri ∩Qj)(d(Qi△Ri)d(Qj△Rj))1/2 .49with the entries along the diagonal of M always being 1.Furthermore note that the form of φ(T ) implies that the limiting distribution is a multivariatenormal distribution.ThisM is the covariant matrix of the distribution, and each entry in the matrix is the covarianceof the vector components as random variables.For the sake of intuition, it is useful to consider the case where one examines the distribution ofω(n;Q1), . . . , ω(n;Qs) by using the above lemma and setting R1 = . . . = Rs = ∅, since ω(n;S) =ω(n;S−∅). In such a situation, since the empty set is the identity under symmetric difference, andseveral densities become zero, σ(t1, . . . , ts) simplifies toσ(t1, . . . , ts) =s∑i=1s∑j=1d(Qi ∩Qj)(d(Qi)d(Qj))1/2titj .50Chapter 4Probability and y-TypicalityIn this section, we prove Proposition 1.26. As this is a quantitative bound on the number of y-typicalnumbers, some technical work is necessary before the bulk of the proof.4.1 Background and Technical LemmasIn this subsection, the evaluation of the higher central moments of strongly additive functions isapplied, using the results found in Halberstam [5] in a modified form, to prove two critical technicallemmata.Lemma 4.1 (Theorem 1 of [5]). Let f be a strongly additive number theoretic function where |f(p)|is bounded by a constant over the primes and Bf (n)→∞. Then for any k ∈ N,limn→∞En(f(m)−Af (n)Bf (n))k=1√2π∫ ∞−∞xke−x2/2 dx = k!(k/2)!2k/2 if k is even,0 if k is odd.This is not quite the statement needed for the proofs in this section, as a certain uniformityin covergence over multiple additive functions is necessary, but a careful reading of [5] with someslight modifications yields the following result:Lemma 4.2. Let f be a strongly additive function where |f(p)| is bounded above by a constant C1over the primes, and Bf (n)→∞. Then for any k ∈ N,En(f(m)−Af (n))k = OC1,C2,k(Bf (n)k).where C2 > 0 is a lower bound on Bf (n), and the condition that n is “sufficiently large” dependsonly on C1, C2, k, and the requirement that Bf (n) > C2.51Proof. To obtain this result from [5], apply the footnote on page 47, using αn = n1/(3k) and theform of Theorem 2 with the restriction ℓ ≤ 2k. This ensures most of the proof of Theorem 2does not require Bf (n) to be large. Then note that the effect of the choice of f(p) on the implicitconstants in the error terms in [5] solely depends on C1, C2 and k; this is not explicitly stated in [5],but is clear enough for C1 and k in the proofs. The dependence on C2 is due to the appearance ofpower sums in the lower bounds. Finally, note that (4.3) of [5] is clearly Oℓ(Bf (αn)2ℓ), which canbe used in the “weaker” form of Theorem 2 used on page 46 to prove the above lemma, providedBf (n) is given a lower bound.We note that an equivalent result to the above is implied by [4] as well, though it is not providedhere. In all applications of Lemma 4.2 in this work, |f(p)| ≤ 1 for all primes p, so the dependenceon any C1 will be ommitted entirely from this point onwards.The two primary technical lemmas required for the proof of Proposition 1.26 can now begin.One way to think about the first technical lemma is that it gives an asymptotic upper bound onthe likelyhood of ω(m;Q) (where Q is the set of primes in an arithmetric progression of the formp ≡ 1 mod q) being far from its expected average value.Lemma 4.3. Let q be any prime power, δ > 0 and C > 0. Let Q = {p : q | p − 1}. Then for anyreal r and n sufficiently large so that Bω(n;Q) ≥ C for some constant C and n ≥ 2q,Pn(|ω(m;Q)− φ(q)−1 log log n| > δ log logn)≪C,r 1δ2r(φ(q) log log n)r.Proof. By Lemma 3.9,Aω(n;Q) =1φ(q)log logn+O(1).Similarly, by Lemma 3.8 and the fact that n ≥ 2q,Bω(n;Q)2 ≪ 1φ(q)log logn.Thus by Chebyshev’s inequality, a binomial expansion,Pn(|ω(m;Q)− φ(q)−1 log logn| > δ log logn)= Pn((ω(m;Q)− φ(q)−1 log logn)2r > (δ log logn)2r)≤ En(ω(m;Q)− φ(q)−1 log log)2r(δ log log n)2r≤ En(ω(m;Q)−Aω(n;Q) +O(1))2r(δ log log n)2r≤ O(∑2rk=0(2rk)(En(ω(m;Q)−Aω(n;Q)))k(δ log log n)2r).52Hence by Lemma 4.2,Pn(|ω(m;Q)− φ(q)−1 log logn| > δ log logn)≪r En(ω(m;Q)−Aω(n;Q))2r(δ log log n)2r≪C,r Bω(n;Q)2r(δ log log n)2r≪C,r (φ(q)−1 log logn)r(δ log log n)2r≪C,r 1δ2r(φ(q) log log n)r.The second technical lemma required is slightly more difficult to characterize, it places anasymptotic upper bound on the number of natural numbers n where ω(n;Q) is far above its expectedaverage value for any set of primes in arithmetic progression Q (of the form p ≡ 1 mod q) wherethe modulus of the arithmetic progression is very large.Lemma 4.4. Let 0 < λn ≤ 1 be a sequence of positive real numbers and a ∈ R be any real number.Let {q(n)k }∞k=1 be the sequence of all prime powers where φ(q(n)k ) > λ−1n , ordered so that qk+1 > qk,for all k ∈ N. Let Q(n)k = {p : q(n)k | p− 1} and Ln =(λn −maxk{φ(q(n)k )−1})−1.Then provided λn log log n≫ (log log n)ν for some ν > 0, and Ln ≪ log log n, it follows that forany real r ≥ 2 thatPn(∃k such that ω(m;Qk) + a > λn log logn)≪ν,a,r (Ln)2r + 1(log logn)r.Furthermore, when Ln ≪ (log log n)1/2−ϵ for some ϵ > 0, the above estimate holds for all real r.Proof. For shorthand in this proof, we write q(n)k and Q(n)k as qk and Qk. We first observe thatPn(∃k such that ω(m;Qk) + a > λn log log n) ≤∞∑k=1Pn(ω(m;Qk) + a > λn log logn).Thus the problem reduces to finding the upper bounds of Pn(ω(m;Qk) + a > λn log logn). Weuse g(n) to denote a function that splits the above sum into “small” and “large” prime powers.Case 1 Suppose qk < g(n) and Bω(n;Q(n)k )2 > 1/2. Since g(n) is “small” in terms of n, we havethat qk ≤ g(n) ≤ n/2 for n sufficiently large.53First, we note that by Lemma 3.9, we have thatλn log logn−Aω(n;Qk)− a = λn log log n− 1φ(qk)log logn+Oa(1)=(λn − 1φ(qk))log logn+Oa(1)≥(λn −maxk{φ(qk)−1})log log n+Oa(1)≥ L−1n log logn+Oa(1).where Ln is as defined in the text of this lemma.Likewise by Lemma 3.8, since qk ≤ n/2,Bω(n;Qk)2 ≤ 2φ(qk)(log log(n/qk)− log log 2 + 1log(n/q))− π(2q; q, a)2qk+∑p≤2qk1Qk(p)p≤ 2φ(qk)(log logn+1log 2)+2qk≪ log lognqk.As in this case, since ω(p;Qk)2 = ω(p;Qk) for all primes, we also obtain thatAω(n;Qk) = Bω(n;Qk)2 ≪ log log nqk.Observe thatPn(ω(m;Qk) + a > λn log logn) = Pn(ω(m;Qk)−Aω(n;Qk) > λn log log n−Aω(n;Qk)− a).Hence by Chebyshev’s inequality, as well as Lemma 4.2 using the lower bound on Bω(n;Qk)2of 1/2, we obtain for any r ∈ N thatPn(ω(m;Qk) + a > λn log logn) ≤En(ω(m;Qk)−Aω(n;Qk))2r(λn log log n−Aω(n;Qk)− a)2r≪r Bω(n;Qk)2r(λn log logn−Aω(n;Qk)− a)2r≪r Bω(n;Qk)2r(L−1n log log n+Oa(1))2r≪a,r L2rn(qk log log n)r.The final step is justified by the fact that Ln ≪ log log n.54Case 2 Suppose qk < g(n) and Bω(n;Qk)2 ≤ 1/2.Trivially, Pn(ω(m;Qk) = 1) ≤ 1. Let ck =∑p∈Qk1p(p−1) , which clearly converges. Observethat if Pn(ω(m;Qk) = ℓ) ≤ (Aω(n;Qk) + ck)ℓ−1 for all n ∈ N, thennPn(ω(n;Qk) = ℓ+ 1) ≤∑p≤np∈Qk∞∑α=1npαP⌊n/pα⌋(ω(m;Qk) = ℓ)≤ n(Aω(n;Qk) + ck)ℓ−1∑p≤np∈Qk1p− 1≤ n(Aω(n;Qk) + ck)ℓ−1∑p≤np∈Qk(1p+1p(p− 1))≤ n(Aω(n;Qk) + ck)ℓ.Thus by the principle of induction, Pn(ω(m;Qk) = ℓ) ≤ (Aω(n;Qk) + ck)ℓ−1 for all n, ℓ ∈ N.Observe that by the definition of Qk, 2 ̸∈ Qk and by summation over the first ten oddprimes and the error estimate∫∞381x(x−1) dx for the rest, it is clear 0 < ck < 3/10. AsAω(n;Qk) = Bω(n;Qk)2 ≤ 1/2, it is clear thatPn(ω(n;Qk) + a > λn log logn) =∑ℓ>λn log logn−aPn(ω(m;Qk) = ℓ)≤∑ℓ>λn log logn−a(Aω(n;Qk) + ck)ℓ−1≤∑ℓ>λn log logn−a(5/4)1−ℓ≤ (5/4)−λn log logn+a+1∞∑ℓ=0(5/4)−ℓ≤ 5(5/4)−λn log logn+a+2≪a 1(logn)λn log(5/4).Case 3 Suppose qk ≥ g(n), qk ≤ n/2. Observe that for λn log logn > 2 + a,Pn(ω(m;Qk) + a > λn log logn) ≤ Pn(ω(m;Qk) ≥ 2).55Thus by Lemma 3.8,Pn(ω(m;Qk) + a > λn log logn) ≤ 1n∑p1,p2∈Qkp1<p2≤nnp1p2≤∑p1,p2∈Qkp1,p2≤n1p1p2≤( ∑p∈Qkp≤n1p)2≤(2φ(qk)(log log(n/q)− log log 2 + 1log(n/q))+2q)2≤(2φ(qk)(log logn+1log 2)+2q)2≪(log lognqk)2.Case 4 Suppose 2qk > n. Then for λn log log n ≥ 1 + a,Pn(ω(m;Qk) + a > λn log logn) ≤ Pn(ω(m;Qk) > 1).But since qk > n/2, and 2 < qk, q2k > n, so ω(m;Qk) ≤ 1, so Pn(ω(m;Qk) > 1) = 0. ThusPn(ω(m;Qk) + a > λn log logn) = 0.Thus for n sufficiently large, and r ∈ N, r ≥ 2, thatPn(∃qk such that ω(m;Qk) + a > λn log logn)≪a,r∑qk<g(n)L2rn(qk log logn)r+∑qk<g(n)1(log n)λn log 2+∑g(n)≤qk≤n/2(log lognqk)2≪a,r L2rn(log log n)r+g(n)(log n)λn log 2+(log logn)2g(n).If one selects g(n) = (log log n)r+2, this becomesPn(∃qk such that ω(m;Qk) + a > λn log log n)≪a,r L2rn + 1(log log n)r+(log logn)r+2(logn)λn log 2.Since λn log logn≫ (log log n)ν , (log n)λn log(5/4) ≫ (log log n)r+2, it thus follows thatPn(∃qk such that ω(m;Qk) + a > λn log logn)≪ν,a,r L2rn + 1(log logn)r.To complete the proof, simply observe that if the above holds for integral r ≥ 2, it holds for non-integral r ≥ 2. If Ln ≪ (log log n)1/2−ϵ, then L2n/(log logn), 1/(log log n) ≤ 1 for n sufficiently largeso lower values of r produce weaker asymptotic bounds, implying the result holds for all real r.56The estimates for Case 2 are not optimal, and can be improved. The techniques of Hardy andRamanujan in [6] applied to Pn(ω(n;Qk) = ℓ+1) would provide superior estimates. However, a fulltreatment for arithemtic progressions is much more complicated, and the estimate obtained in thislemma suffices for our purposes. The estimates for Case 3 and Case 4 are a variant of a techniqueemployed by Chang and Martin in [2].With these technical results completed, the proof of Proposition 1.26 can begin.4.2 Proof of Proposition 1.26Observe that by Definition 1.25, a number m is not y-typical if and only if1. There exist two prime powers q1, q2 where φ(q1) < φ(q2) ≤ y and Q(m; q1) < Q(m; q2),2. or there exist two prime powers q1, q2 where φ(q1) ≤ y < φ(q2) and Q(m; q1) ≤ Q(m; q2).Thus it follows thatPn(m is not y-typical) = Pn(m satisfies (1)) + Pn(m satisfies (2) and not (1)).Before evaluating the two above probabilities, observe that the condition that Q(m; q1) ≤Q(m; q2) is by Lemma 2.2 equivalent toω(m; {p prime: q1 | p− 1}) ≤ ω(m; {p prime: q2 | p− 1}) + E¯(m; q2)− E¯(m; q1),and thus by the definition of E¯ given in the lemma, it follows thatω(m; {p prime: q1 | p− 1}) ≤ ω(m; {p prime: q2 | p− 1}) + 2.Let N = W(y) be the number of prime powers with totients less than or equal to y. Then byDefinition 1.2, it follows immediately that the finite sequence q1, . . . , qN is a φ-sequence containingall prime powers with totients less than or equal to y and no others.First, we find a bound for Pn(m satisfies (1)). Clearly, we have thatPn(m satisfies (1))= Pn(∃ i < j ≤ N such that φ(qi) < φ(qj) and Q(m; qi) < Q(m; qj))≤ Pn(∃ i < j ≤ N such that φ(qi) < φ(qj) and ω(m;Qi) < ω(m,Qj) + 2),where Qk = {p prime: qk | p− 1} for all integers k.57Informally, observe that this condition imples that there is at least one i such that ω(m;Qi) isfar from its average value of φ(qi)−1 log logn. Formally, let φ+(qi) and φ−(qi) be respectively thesmallest totient value greater than φ(qi) and the largest totient value less than φ(qi). Then letδ1 =13(1φ(q1)− 1φ(q2)), δN =13(1φ−(qN )− 1φ(qN ))when N > 1,δi =13min(1φ−(qi)− 1φ(qi),1φ(qi)− 1φ+(qi),)for 1 < i < N.Note that by this definition, δi ≫ φ(qi)−2 ≫ y−2. Clearly, if |ω(m;Qi) − φ(qi)−1 log logn| ≤δi log logn then there is a gap of at least size δi log logn between ω(m;Qi) and ω(m;Qj) if φ(qi) <φ(qj). Provided δi log log n ≥ 2 for 1 ≤ i ≤ N (which is guaranteed provided y−2 log logn issufficiently large), this implies ω(m;Qi) ≥ ω(m;Qj)+2. Thus it follows for n sufficiently large thatby Lemma 4.3, for any real r,Pn(m satisfies (1))≤N∑i=1Pn(|ω(m;Qi)− φ(qi)−1 log logn| > δi log logn)≪rN∑i=11(δi)2r(φ(qi) log log n)r≪r 1(log logn)rN∑i=1φ(qi)3r≪r y3r+1(log logn)r.Now, the determination of an upper bound for Pn(m satisfies (2) and not (1)) commences. LetM(y) = {q a prime power : φ(q) = φ(qN )}. If m does not satisfy (1) then since φ(qN ) is themaximal totient less than or equal to y, it follows for every prime power q with φ(q) < φ(qN ) ≤ yand u ∈M(y) that Q(m;u) ≤ Q(m; q).Thus for each m that does not satisfy (1) it follows min{Q(m;u) : u ∈M(y)} ≤ Q(m; q) for allprime powers where φ(q) ≤ y. Thus if m ∈ N satisfies (2) and not (1), it follows there exists someprime power q, with φ(q) > y such that min{Q(m;u) : u ∈M(y)} ≤ Q(m; q).Pn(m satisfies (2) and not (1))≤ Pn(∃ prime power q such that φ(q) > y and min{Q(m;u) : u ∈M(y)} ≤ Q(m; q))≤∑u∈M(y)Pn(∃ prime power q such that φ(q) > y and Q(m;u) ≤ Q(m; q)).Now, let {qi}ni=1 be the sequence of all prime powers with totient greater than y in ascending order,Qi = {p prime: qi | p−1} and Uu = {p prime: u | p−1}. Then for any C ∈ (φ(qN+1)−1, φ(qN )−1),58by Lemmata 4.3 and 4.4 that for any real r, it followsPn(m satisfies (2) and not (1))≤∑u∈M(y)Pn(∃ k ∈ N such that φ(q) > y and ω(m;Uu) ≤ ω(m;Qk) + 2)≤∑u∈M(y)Pn(ω(m;Uu) < C log log n) + Pn(∃ k ∈ N such that ω(m;Qk) + 2 > C log logn)≪r 1δ2r(φ(qN ) log log n)r+C2r0 + 1(log logn)rwhere C0 =(C − φ(qN+1)−1)−1and δ =(φ(qN )−1 − C), provided C0 ≪ (log log n)1/2−ϵ for someϵ > 0 and C ≫ (log log n)ν−1 for some ν > 0. As the range of C for any given y implies byBertrand’s Postulate that C ≍ y−1, C ≫ (log log n)ν−1 is implied by y ≪ (log logn)1−ν whichfollows trivially from y ≪ (log log n)1/4−ϵ. By selectingC =φ(qN )1/2 + φ(qN+1)(φ(qN )1/2 + φ(qN ))φ(qN+1),it followsC0 = (δφ(qN )1/2)−1 =(φ(qN )1/2 + φ(qN ))φ(qN+1)φ(qN+1)− φ(qN ) ≪ y2.Thus for any real r ≥ 0 and 1 ≤ y ≪ (log logn)1/4−ϵ,Pn(m satisfies (2) and not (1))≪r y4r(log logn)r.Combining these two results yields the statement that for r ≥ 1 and 1 ≤ y ≪ (log log n)1/4,Pn(m is not y-typical)≪r y4r(log logn)r,provided y−2 log log n is sufficiently large.Thus, for any ϵ > 0 and 1 ≤ y = y(n)≪ (log log n)1/4−ϵ,Pn(m is not y-typical)≪ (log log n)−ϵ.Thus, since Pn(m is y-typical) = 1− Pn(m is not y-typical)limn→∞Pn(m is y-typical) = limn→∞ 1 +O((log logn)−ϵ) = 1.A direct implication of the above proposition is that for any fixed y ≥ 1, the natural density ofy-typical numbers is 1.59Chapter 5Probability Distributions of theInvariant FactorsIn this section, the probability distributions of the invariant factors is characterized. The firstsubsection contains the lemmas that convert certain relevant distributions described in terms oftheir characteristic function into cumulative distribution functions, and discusses some of theirproperties. The second subsection builds on the first to provide technical lemmas needed to proveTheorem 1.15. In the final subsection, Theorem 1.15 is proven.5.1 Lemmas for Classifying the DistributionsThe key goal of this section is to find the distribution functions of maximum and minimum valuesof correlated multivariate normal distributions. The first step is to provide notation for discussingthese maximums and minimums in terms of probability distributions:Definition 5.1. For any n-dimensional multivariate probability distribution F , define two functionsMxF (x) = F (x, . . . , x),MnF (x) =n∑k=1(−1)k−1∑S∈Sn#S=kF (x⃗S),where Sn is the power set of {1, . . . , n}, and for any S ∈ Sn and x ∈ R, x⃗S ∈ R¯n is the randomvector with i-th component equal to x if i ∈ S and ∞ otherwise.As these minimums and maximums are expressable as finite sums, they behave nicely in termsof limits. In particular:60Proposition 5.2. Let F be a multivariate probability distribution over N real dimensions.If there are random variables X1, . . . , Xn that form a random vector with this distribution,MxF (x) = P (max{X1, . . . , Xn} ≤ x),MnF (x) = P (min{X1, . . . , Xn} ≤ x),are the distribution functions of the random variables max{X1, . . . , Xn} and min{X1, . . . , Xn},respectively.Furthermore, if there exists a sequence of multivariate probability distributions such thatlimn→∞Fn(x⃗) = F (x⃗) for all x⃗ ∈ RN ,thenlimn→∞MxFn(x) =MxF (x),limn→∞MnFn(x) =MnF (x).Proof. Observe that as F is the multivariate distribution function of X1, . . . , Xn,P (max{X1, . . . , Xn} ≤ x) = P (X1 ≤ x, . . . ,Xn ≤ x)= F (x, . . . , x) =MxF (x).Similarly, as F is the multivariate distribution function of X1, . . . , Xn and by application of theinclusion-exclusion principle, it followsP (min{X1, . . . , Xn} ≤ x) = P ((X1 ≤ x) ∪ . . . ∪ (Xn ≤ x))=N∑k=1∑S∈SN#S=k(−1)k−1P (Xs ≤ x : s ∈ S)=N∑k=1(−1)k−1∑S∈SN#S=kF (x⃗S) =MnF (x).For the final statement, observe thatlimn→∞MxFn(x) = limn→∞Fn(x, . . . , x) = F (x, . . . , x) =MxF (x).Likewiselimn→∞MnFn(x) = limn→∞N∑k=1(−1)k−1∑S∈SN#S=kFn(x⃗S) =N∑k=1(−1)k−1∑S∈SN#S=kF (x⃗S) =MnF (x).This completes the proof.61In the following proofs, some very routine probability theory and facts about probability dis-tributions are relegated to several lemmas in Appendix D. These will be cited in these proofs andare solely concerned with describing the characteristic functions and distribution functions of theprobability distributions of sums of independent normal variables and truncated normal variables.With this preliminary notation and the above caveat out of the way, the bivariate distributionsthat will arise in the proof of Theorems 1.15, 1.19, and 1.23 will be characterized.In the following proofs, the fact that sums of random variables whose joint distribution is amultivariate normal distribution which correspond to the eigenvectors of the covariance matrix areindependent will be used. For example, if X,Y have a joint bivariate normal distribution, and⟨1, 1⟩, ⟨1,−1⟩ are eigenvectors of the matrix of covariance, then the sums X + Y and X − Y areindependent random variables. This is formalized in Lemma D.6 While this source does not statethis explicitly, in [13, pp. 27–28] relates the standard normal multivariate distribution to arbitrarymultivariate normal distributions. In doing so, it demonstrates that these eigenvector matchingsums must be independent because they are the independent random variables of the standardnormal multivariate distribution after a change of basis.Lemma 5.3. Suppose F (x, y) is a normal bivariate distribution function with invertible covariancematrixM =[1 aa 1].Then it followsMxF (x) = Φ(x;1− a√1− a2)= Φ(x)− 2T(x,1− a√1− a2),MnF (x) = Φ(x;− 1− a√1− a2)= Φ(x) + 2T(x,1− a√1− a2).with corresponding characteristic functionsφMxF (t) = e−t2/2(1 + i erfi(√1− at2)),φMnF (t) = e−t2/2(1− i erfi(√1− at2)).Proof. Let X,Y be any random variables with a joint distribution of F . Such variables are guar-anteed to exist, as F is a distribtion function. More precisely, X,Y are such thatF (x, y) = P (X ≤ x, Y ≤ y).Recall that since the matrix M is invertible, there exists a probability density function f(x)f(x⃗) =exp− 12 x⃗⊺M−1x⃗2π√|M |62for this bivariate normal distribution [13, Definition 3.2.1, pg. 26].Observe that M has unit eigenvectors e⃗1 =1√2[1, 1] and e⃗2 =1√2[1,−1] with respective eigen-values λ1 = (1+a), λ2 = (1−a). It follows by Lemma D.6 that X+Y and X −Y are independentrandom variables as discussed earlier, and that for Fk(x) = P ((X,Y ) · e⃗k ≤ x), it holdsFk(x) = Φ(x√λk).Now, observe that P (X + Y ≤ x) = F1(x/√2) = Φ(x/√2(1 + a)) and P (X − Y ≤ x) =F2(x/√2) = Φ(x/√2(1− a)), and observe thatP (|X − Y | ≤ x) = P (−x ≤ X − Y ≤ x) = Φ+( x√2(1− a)).As |X−Y | and X+Y are independent random variables, we can obtain the probability densityfunction of 2max{X,Y } = |X − Y |+X + Y by application of Lemma D.2, we obtain thatP (2max{X,Y } ≤ x) = Φ(x2;1− a√1− a2).Thus by a simple change of variables and Proposition 5.2 we obtain the desired result for themaximum. The result regarding the characteristic function arises from the straightforward relationthat if a differentiable distribution function F (x) has corresponding characteristic function φF (t),then F (αx) is a distribution function with corresponding characteristic function φF (αt) (this canbe demonstrated by variable substitution of the integral defining the characteristic function).For the minimum, 2min{X,Y } = X+Y −|X−Y |, which allows the application of Lemma D.2and gives the result thatP (2min{X,Y } ≤ x) = Φ(x2;− 1− a√1− a2),which completes the proof after a final change of variables and Proposition 5.2. The characteristicfunction follows from the same reason as above.We shall now describe a singular four-variable distribution that arises in the proof of Theorems1.15 and 1.21.Lemma 5.4. Suppose F (x, y, z, w) is a multivariate normal distribution centred at the origin withmatrix of covarianceM =1 a b ca 1 c bb c 1 ac b a 163with the condition that 0 < c < b < a and 1− a− b+ c = 0. ThenMxF (x) = Φ(x)− 2T(x;√1 + a− b− c2 + 2b)− 2T(x;√1− a+ b− c2 + 2a)+ S(4x; 2√1 + a+ b+ c, 2√1 + a− b− c, 2√1− a+ b− c),with corresponding characteristic functionφMxF (t) = e−t2/2(1 + i erfi(√1 + a− b− ct2√2)+ i erfi(√1− a+ b− ct2√2)− erfi(√1 + a− b− ct2√2)erfi(√1− a+ b− ct2√2)),andMnF (x) = Φ(x)− 2T(x;−√1 + a− b− c2 + 2b)− 2T(x;−√1− a+ b− c2 + 2a)+ S(4x; 2√1 + a+ b+ c, 2√1 + a− b− c, 2√1− a+ b− c).with corresponding characteristic functionφMnF (t) = e−t2/2(1− i erfi(√1 + a− b− ct2√2)− i erfi(√1− a+ b− ct2√2)− erfi(√1 + a− b− ct2√2)erfi(√1− a+ b− ct2√2)).Proof. Let X,Y, Z,W be any random variables with a joint distribution of F . Such variables areguaranteed to exist as F is a distribution function. Precisely, let X,Y, Z,W be random variablessuch thatF (x, y, z, w) = P (X ≤ x, Y ≤ y, Z ≤ z,W ≤ w).First, observe that M has four unit eigenvectorse⃗1 =1/21/21/21/2 , e⃗2 =1/21/2−1/2−1/2 , e⃗3 =1/2−1/21/2−1/2 , e⃗4 =1/2−1/2−1/21/2 ,with corresponding eigenvaluesλ1 = 1 + a+ b+ c, λ2 = 1 + a− b− c, λ3 = 1− a+ b− c, λ4 = 1− a− b+ cwhere λ1 > λ2 > λ3 > λ4 = 0.64Let R = span(e⃗1, e⃗2, e⃗3). Let MR denote the matrix M restricted to this subspace with basise⃗1, e⃗2, e⃗3, with determinant |MR| = λ1λ2λ3. Note that MR is invertible and diagonal by definition.By Lemma D.6 it holds that e⃗4 · (X,Y, Z,W ) has all mass at 0, so P (X − Y −Z +W = 0) = 1.Now, observe thatX−Y −Z+W = 0 implies thatX−Y = Z−W and thus |X−Y |−|Z−W | = 0.Furthermore, since X − Y and Z −W have the same sign, it follows X − Y +Z −W has the samesign, and thus |X − Y |+ |Z −W | = |X − Y + Z −W |. Thus, with probability 1,max{X,Y, Z,W}= max{max{X,Y },max{Z,W}}= max{X + Y + |X − Y |, Z +W + |Z −W |}/2=(X + Y + Z +W + |X − Y |+ |Z −W |+ ∣∣X + Y − Z −W + |X − Y | − |Z −W |∣∣)/4=(X + Y + Z +W + |X − Y + Z −W |+ |X + Y − Z −W |)/4.Likewise, with probability 1,min{X,Y, Z,W}= min{min{X,Y },min{Z,W}}= min{X + Y − |X − Y |, Z +W − |Z −W |}/2=(X + Y + Z +W − |X − Y | − |Z −W | − ∣∣X + Y − Z −W − |X − Y |+ |Z −W |∣∣)/4=(X + Y + Z +W − |X − Y + Z −W | − |X + Y − Z −W |)/4.As e⃗1, e⃗2, e⃗3 are eigenvectors of M , and X,Y, Z,W is a multivariate normal distribution itfollows by Lemma D.6 that X + Y + Z + W , |X + Y − Z − W |, and |X − Y + Z − W | areindependent random variables. As a way to represent the max and min of the four variables as asum of these three independent random variables has been found, one can determine the distributionfunction of max{X,Y, Z,W} and min{X,Y, Z,W} by convolving the distribution function of thethree independent random variables.As Lemma D.6 implies (X,Y, Z,W ) · e⃗k are normally distributed with mean 0 and respectivevariance λk, it the follows for Fk(x) = P ((X,Y, Z,W ) · e⃗k ≤ x) thatFk(x) = Φ(x√λk).Consequently,P ((X,Y, Z,W ) · e⃗k ≤ x2) = Fk(x2) = Φ( x2√λk),P (|(X,Y, Z,W ) · e⃗k| ≤ x2) = Φ+( x2√λk).65Thus by Lemma D.5 it follows4max{X,Y, Z,W} = X + Y + Z +W + |X + Y − Z −W |+ |X − Y + Z −W |,and (X + Y +Z +W ), |X + Y −Z −W |, |X − Y +Z −W | are independent random variables withthe distributions given above, thatP (4max{X,Y, Z,W} ≤ x) = Φ(x4)− 2T(x4;√λ2λ1 + λ3)− 2T(x4;√λ3λ1 + λ2)+ S(x; 2√λ1, 2√λ2, 2√λ3).Thus by a simple change of variables, and Proposition 5.2 the desired result is obtained. The resultfor the characteristic function follows by the method described in the previous lemma.Furthermore, by the same method, since4min{X,Y, Z,W} = X + Y + Z +W − |X + Y − Z −W | − |X − Y + Z −W |,it follows thatP (4min{X,Y, Z,W} ≤ x) = Φ(x4)− 2T(x4;−√λ2λ1 + λ3)− 2T(x4;−√λ3λ1 + λ2)+ S(x; 2√λ1, 2√λ2, 2√λ3).Thus with one last change of variables, Proposition 5.2, and the application of the method for thecharacteristic function from the previous lemma, the proof is complete.The standard normal distribution, and the two distributions characterized in the lemmas inthis section fully characterize all but one probability distribtion found in Theorem 1.15. The lastdistribution is irregular and is treated as a special case by the Theorem, though it is similar to finaldistribution discussed above.5.2 φ-Sequences and Probability DistributionsRecall from chapter 2 Lemma 2.7. This lemma classifies each possible fragment of the total φ-sequence of prime powers for which the prime powers of the segment contain two adjacent φ valuesand contain all prime powers with those values.By Propositions 2.14 and 1.26 one can see that pairs of prime powers with adjacent φ values giverise to all invariant factors for y-typical numbers below a threshold determined by y. This meansthat the distribution of invariant factors which appear for a given n can be determined by the66examination of the joint distribution of additive functions ω(n;Q1−Q2) where Q1 = {p prime: p ≡1 mod q1}, Q2 = {p prime: p ≡ 1 mod q2} with q1, q2 prime powers with adjacent totient values.As Lemma 2.7 classifies what prime powers can be adjacent and what their relationship is interms of common factors, one can determine that any such joint distribution will fall into one ofa few forms. The dimension of the limiting joint distribution of ω(n;Q1 − Q2) is the productof the number of primes with the lower totient value and the number of primes with the highertotient value. This gives possible dimensions of 1,2, and 4. The first such form and the simplest ischaracterized below, in the following lemma:Lemma 5.5. Suppose φ(pα1 ) ≤ φ(pβ2 ) with p1 ̸= p2, and letQ1 = {p : p ≡ 1 (mod pα1 )}, Q2 = {p : p ≡ 1 (mod pβ2 )},with ∆1 = d(Q1) and ∆2 = d(Q2), and ∆3 = ∆1∆2. Then the limiting distribution F (x⃗) ofFn(x) = νn{ω(m;Q1 −Q2)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log logn)1/2 ≤ x}is the standard normal distribution with mean 0 and variance 1. That is to say,F (x) = Φ(x).Proof. First observe that by Lemma 3.11, ω(m;Q1 −Q2) is in class H and thus the lemma followsby Lemma 3.13.This lemma will be used to prove Theorems 1.18 and 1.20. Note that Theorem 1.20 concernsthe special case where an invariant factor arises from two prime powers with the same totient anddoes not fit the general pattern described above. The next two lemmas are very similar in formand content, and fully characterize the bivariate normal distributions that arise. The first will beused to prove Theorem 1.23:Lemma 5.6. Suppose pα1 , p2, pβ3 is a φ(1 : 2)-sequence of prime powers, and letQ1 = {p : p ≡ 1 (mod pα1 )},Q2 = {p : p ≡ 1 (mod p2)},Q3 = {p : p ≡ 1 (mod pβ3 )},with ∆1 = d(Q1), ∆2 = d(Q2), and ∆3 = ∆1∆2. Then the limiting distribution F (x⃗) ofFn(x⃗) = Pn(ω(m;Q1 −Q2)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log log n)1/2 ≤ x1,ω(m;Q1 −Q3)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log logn)1/2 ≤ x2)67is the nonsingular multivariate normal distribution with mean 0⃗ and matrix of covarianceM =[1 aa 1],with determinant 1− a2 and eigenvalue, eigenvector pairs(1 + a, [1, 1]),(1− a, [1,−1]).wherea =∆1 +∆22 − 2∆3∆1 +∆2 − 2∆3 .The probability density function of F (x⃗) isf(x⃗) =exp(−1/2x⃗⊺M−1x⃗)2π√|M | .Proof. First observe that by Lemma 3.11, ω(m;Q1 −Qi) for i = 2, 3 is in the class H and thus byLemma 3.14 we obtain the above distribution.The second lemma will be used to prove Theorem 1.19:Lemma 5.7. Suppose p1, φ(pα2 ), φ(pβ3 ) is a φ(2 : 1)-sequence, and letQ1 = {p : p ≡ 1 (mod p1)},Q2 = {p : p ≡ 1 (mod pα2 )},Q3 = {p : p ≡ 1 (mod pβ3 )},with ∆1 = d(Q1), ∆2 = d(Q3), and ∆3 = ∆1∆2. Then the limiting distribution F (x⃗) ofFn(x⃗) = Pn(ω(m;Q1 −Q3)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log log n)1/2 ≤ x1,ω(m;Q2 −Q3)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log logn)1/2 ≤ x2)is the multivariate normal distribution centred at 0 and matrix of covarianceM =[1 aa 1],with determinant 1− a2 and eigenvalue, eigenvector pairs(1 + a, [1, 1]),(1− a, [1,−1]).68wherea =∆21 +∆2 − 2∆3∆1 +∆2 − 2∆3 .The probability density function of F (x⃗) isf(x⃗) =exp(−1/2x⃗⊺M−1x⃗)2π√|M | ,Proof. First observe that by Lemma 3.11, ω(m;Qi − Q2) for i = 1, 2 is in class H and thus byLemma 3.14 we obtain the above distribution.The next lemma will be used to prove Theorem 1.21, which covers φ(2 : 2)-sequences except forthe φ-sequence 3, 4, 5, 8. It will not be used to prove Theorem 1.22 as the proof of Theorem 1.21requires that all four prime powers involved in a φ(2 : 2)-sequence be pairwise relatively prime,which is false in exactly one case by Lemma 2.11.Lemma 5.8. Suppose p1, pα2 , p3, pβ4 is a φ(2 : 2)-sequence other than 3, 4, 5, 8, and letQ1 = {p : p ≡ 1 (mod p1)},Q2 = {p : p ≡ 1 (mod pα2 )},Q3 = {p : p ≡ 1 (mod p3)},Q4 = {p : p ≡ 1 (mod pβ4 )},with ∆1 = d(Q1) and ∆2 = d(Q3), and ∆3 = ∆1∆2. Then the limiting distribution ofFn(x⃗) = Pn(ω(m;Q1 −Q3)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log log n)1/2 ≤ x1,ω(m;Q1 −Q4)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log log n)1/2 ≤ x2,ω(m;Q2 −Q3)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log log n)1/2 ≤ x3,ω(m;Q2 −Q4)− (∆1 −∆2) log log n(∆1 +∆2 − 2∆3)1/2(log log n)1/2 ≤ x4)is the singular multivariate normal distribution with mean 0⃗ and matrix of covarianceM =1 a b ca 1 c bb c 1 ac b a 1 ,with determinant 0 and eigenvalue, eigenvector pairs (in ascending order of eigenvalue)(0, [1,−1,−1, 1]), (1−a+ b− c, [1,−1,−1, 1]), (1+a− b− c, [1, 1,−1,−1]), (1+a+ b+ c, [1, 1, 1, 1])69wherea =∆1 +∆22 − 2∆3∆1 +∆2 − 2∆3 ,b =∆21 +∆2 − 2∆3∆1 +∆2 − 2∆3 ,c =∆21 +∆22 − 2∆3∆1 +∆2 − 2∆3 .Proof. First, observe that by Lemma 3.11, ω(m;Q1 − Q3), ω(m;Q1 − Q4), ω(m;Q2 − Q3), andω(m;Q2−Q4) are all elements of class H. Furthermore, the Dirichlet density of Q1, Q2, Q3, Q4 andtheir intersections and symmetric differences are all well defined and non-zero. Thus we can applyLemma 3.14 to determine the distribution of F .It is trivial to verify from the form of the matrix that that the eigenvector, eigenvalue pairs are(1 + a+ b+ c, [1, 1, 1, 1]),(1 + a− b− c, [1, 1,−1,−1]),(1− a− b+ c, [1,−1,−1, 1]),(1− a+ b− c, [1,−1, 1,−1]).Furthermore, observe that since 2, 3, 4, 5 is not a φ(2 : 2)-sequence ∆1,∆2 < 1 and thus ∆21 < ∆1and ∆22 < ∆2, which implies c < a, b. Being a φ(2 : 2)-sequence (which excludes 2, 3, 4, 5), ∆2 < ∆1and ∆1 +∆2 < 1 which implies ∆21 +∆2 < ∆1 +∆22 and thus c < b < a. Now, finally observe thatby factorization, c = (∆1 −∆2)2/(∆1 +∆2 − 2∆3) > 0. Thus 0 < c < b < a. Thus the eigenvaluescan be ordered1− a− b+ c < 1− a+ b− c < 1 + a− b− c < 1 + a+ b+ c.Now, observe that1− a− b+ c = 1 + −∆1 −∆22 + 2∆3 −∆21 −∆2 + 2∆3 +∆21 +∆22 − 2∆3∆1 +∆2 − 2∆3= 1 +−∆1 −∆2 + 2∆3∆1 +∆2 − 2∆3 = 0.Thus the eigenvalues ofM are, in order, 0, 1−a+b−c, 1+a−b−c, 1+a+b+c, and the determinantof M is 0.It should be noted that the fact that the eigenvector [1,−1,−1, 1] has an eigenvalue of 0 shouldbe expected. Observe that if you consider for any fixed n ∈ N the random variables Xn, Yn, Zn,Wnas being the component variables of Fn, so thatFn(x1, x2, x3, x4) = P (Xn ≤ x1, Yn ≤ x2, Zn ≤ x3,Wn ≤ x4),70you would obtain thatXn − Yn − Zn +Wn = ω(m;Q1 −Q3)− ω(m;Q1 −Q4)− ω(m;Q2 −Q3) + ω(m;Q2 −Q4)(1/2 log log n)1/2=ω(m;Q1)− ω(m;Q3)− ω(m;Q1) + ω(m;Q4)(1/2 log log n)1/2+−ω(m;Q2) + ω(m;Q3) + ω(m;Q2)− ω(m;Q4)(1/2 log log n)1/2= 0.So it follows that in the limit all the density falls under the subspace where X − Y − Z +W = 0.The next lemma will be used in the proof of Theorem 1.22. This lemma concerns an irregulardistribution that lacks the elegant symmetry that will make the preceding distributions easy tosimplify into an explicit distribution for the corresponding invariant factor, but the multivariatejoint distribution is still fairly nice, being a multivariate normal distribution.Lemma 5.9. LetQ1 = {p : p ≡ 1 (mod 3)},Q2 = {p : p ≡ 1 (mod 4)},Q3 = {p : p ≡ 1 (mod 5)},Q4 = {p : p ≡ 1 (mod 8)},Then the limiting distribution ofFn(x⃗) = νn{ω(m;Q1 −Q3)− 1/4 log logn(1/2 log log n)1/2≤ x1, ω(m;Q1 −Q4)− 1/4 log logn(1/2 log log n)1/2≤ x2,ω(m;Q2 −Q3)− 1/4 log logn(1/2 log log n)1/2≤ x3, ω(m;Q2 −Q4)− 1/4 log logn(1/2 log log n)1/2≤ x4}(5.1)is the singular multivariate normal distribution with mean 0⃗ and matrix of covarianceM ′ =1 5/8 1/2 1/85/8 1 −1/8 1/41/2 −1/8 1 3/81/8 1/4 3/8 1/2with determinant 0 and eigenvalue, eigenvector pairs(0, [1,−1,−1, 1]), (1/2, [1,−1/2, 0,−3/2]), (−√2/4 + 3/2, [1, 3√2 + 5,−4√2− 5,−√2− 1]),(√2/4 + 3/2, [1,−3√2 + 5, 4√2− 5,√2− 1]).71Proof. Let Q1, . . . , Q4 be as described above, and for any n ∈ N letGn(x⃗) = νn{ω(m;Q1 −Q3)− 1/4 log logn(1/2 log log n)1/2≤ x1, ω(m;Q1 −Q4)− 1/4 log logn(1/2 log log n)1/2≤ x2,ω(m;Q2 −Q3)− 1/4 log logn(1/2 log log n)1/2≤ x3, ω(m;Q2 −Q4)− 1/4 log logn1/2(log logn)1/2≤ x4}. (5.2)By Lemma 3.11, ω(m;Q1 − Q3), ω(m;Q1 − Q4), ω(m;Q2 − Q3), and ω(m;Q2 − Q4) are allelements of class H. Furthermore, the Dirichlet density of Q1, Q2, Q3, Q4 and their intersectionsand symmetric differences are all well defined and non-zero. Thus we can apply Lemma 3.14 todetermine the limiting distribution of G(x⃗) = limn→∞Gn(x⃗).Asd(Q1) =12, d(Q1 ∩Q2) = 14, d(Q1 ∩Q3) = 18, d(Q1 ∩Q4) = 18,d(Q2) =12, d(Q2 ∩Q3) = 18, d(Q2 ∩Q4) = 14, d(Q3) =14,d(Q3 ∩Q4) = 116, d(Q4) =14, d(Q1△Q3) = 12, d(Q1△Q4) = 12,d(Q2△Q3) = 12, d(Q2△Q4) = 14,it followsM =1 a b ca 1 d eb d 1 fc e f 1for a, b, c, d, e, f wherea =d(Q1 ∩Q1) + d(Q3 ∩Q4)− d(Q1 ∩Q3)− d(Q1 ∩Q4)(d(Q1△Q3)d(Q1△Q4))1/2 =1/2 + 1/16− 1/8− 1/81/2=58,b =d(Q1 ∩Q2) + d(Q3 ∩Q3)− d(Q1 ∩Q3)− d(Q2 ∩Q3)(d(Q1△Q3)d(Q2△Q3))1/2 =1/4 + 1/4− 1/8− 1/81/2=12,c =d(Q1 ∩Q2) + d(Q3 ∩Q4)− d(Q1 ∩Q4)− d(Q2 ∩Q3)(d(Q1△Q3)d(Q2△Q4))1/2 =1/4 + 1/16− 1/8− 1/81/(2√2)=√28,d =d(Q1 ∩Q2) + d(Q3 ∩Q4)− d(Q1 ∩Q3)− d(Q2 ∩Q4)(d(Q1△Q4)d(Q2△Q3))1/2 =1/4 + 1/16− 1/8− 1/41/2= −18,e =d(Q1 ∩Q2) + d(Q4 ∩Q4)− d(Q1 ∩Q4)− d(Q2 ∩Q4)(d(Q1△Q4)d(Q2△Q4))1/2 =1/4 + 1/4− 1/8− 1/41/2√2=√24,f =d(Q2 ∩Q2) + d(Q3 ∩Q4)− d(Q2 ∩Q4)− d(Q2 ∩Q3)(d(Q2△Q3)d(Q2△Q4))1/2 =1/2 + 1/16− 1/4− 1/81/2√2=3√28,72and M is the covariance matrix of the limiting distribution G(x⃗) which is a multivariate normaldistribution. Now, letFn(x⃗) = Pn(ω(m;Q1 −Q3)− 1/4 log logn(1/2 log log n)1/2≤ x1,ω(m;Q1 −Q4)− 1/4 log logn(1/2 log log n)1/2≤ x2,ω(m;Q2 −Q3)− 1/4 log logn(1/2 log log n)1/2≤ x3,ω(m;Q2 −Q4)− 1/4 log logn(1/2 log log n)1/2≤ x4).As Fn(x, y, z, w) = Gn(x, y, z,√2w) it followsF (x, y, z, w) = limn→∞Fn(x, y, z, w) = G(x, y, z,√2w),so by [13, Theorem 3.3.3] F must also be a multivariate normal distribution with matrix of covari-ance M ′ = DMD whereD =1 0 0 00 1 0 00 0 1 00 0 0 1/√2 .Trivially, it followsM ′ =1 5/8 1/2 1/85/8 1 −1/8 1/41/2 −1/8 1 3/81/8 1/4 3/8 1/2 ,with the eigenvectors and eigenvalues1 trivial to verify. This completes the proof.This concludes all the prior work needed for the proof of the invariant factor distribution theo-rems, which will begin immediately in the next section.5.3 Proofs of Theorems 1.15 to 1.24First, Theorems 1.18, 1.19, 1.21, and 1.23 will be proven in a consolidated proof.1Computed using sagemath.73Proof. In all five theorems, φ(qi) < φ(qi+1). Let y = φ(qi+1) and letIn =I(m; fi)− µi log lognσi(log logn)1/2,Xn =ω(m;Qi −Qi+1)− µi log log nσi(log log n)1/2,Yn =ω(m;Qi −Qi+2)− µi log log nσi(log log n)1/2,Zn =ω(m;Qi−1 −Qi+1)− µi log log nσi(log logn)1/2,Wn =ω(m;Qi−1 −Qi+2)− µi log log nσi(log logn)1/2.be random variables, Qj = {p prime: qj | p − 1} for all integers j, and with Zn,Wn defined onlywhen i > 1.Furthermore, for y-typical m let q1(m), . . . , qN (m) be the ordered sequence of prime powers thatexists when m is y-typical described in Proposition 2.14, and for 1 ≤ j ≤ N , letQj(m) = {p prime: qj(m) | p− 1}.It should be clear from the above definitions that to prove the five theorems, it suffices provethat Pn(In ≤ x) has the given distribution.By Lemmata 3.9 and 3.12, it is clear for any j ≤ N thatd(Qj) = φ(qj)−1d(Qj) = φ(qj)−1.Thus it follows by Proposition 2.14 for y-typical m that qj(m) ≤ y thatφ(qj)−1 = φ(qj)−1 = d(Qj).By Proposition 1.26, it followsPn(In ≤ x) = Pn(In ≤ x,m is y-typical) + Pn(In ≤ x,m is not y-typical)= Pn(In ≤ x,m is y-typical) +O(Pn(m is not y-typical))= Pn(In ≤ x,m is y-typical) +Oy(log log log nlog log n).When m is y-typical, by properties (4) and (6) of Proposition 2.14, I(m; fi) = Q(m; qi(m)) −Q(m; qi+1(m)). ThusPn(In ≤ x,m is y-typical) = Pn(Q(m; qi(m))−Q(m; qi+1(m))− µi log lognσi(log logn)1/2≤ x,m is y-typical).74Theorem 1.18 If qi, qi+1 is a type φ(1 : 1)-sequence, then since there is only one prime power inthe inverse image of the totient values, for y-typicalm it holds qi(m) = qi and qi+1(m) = qi+1.Thus by property (6) of Proposition 2.14,Pn(In ≤ x,m is y-typical)= Pn(ω(m;Qi −Qi+1) +O(1)− µi log lognσi(log log n)1/2≤ x,m is y-typical).Thus by Proposition 1.26 and Lemma 5.5,limn→∞Pn(In ≤ x,m is y-typical)= limn→∞Pn(Xn ≤ x+O(σ−1i (log log n)−1/2),m is y-typical)= limn→∞Pn(Xn ≤ x)= Φ(x).Theorem 1.23 If qi, qi+1 is contained in a type φ(1 : 2)-sequence, it follows for y-typical m thatqi(m) = qi and qi+1(m) ∈ {qi+1, qi+2} by consideration of the inverse image of their totientvalues. By property (1) of Proposition 2.14, the ordering ensuresQ(m, qi+1(m)) = max{Q(m, qi+1),Q(m, qi+2)}.Thus by property (6) of Proposition 2.14Pn(In ≤ x,m is y-typical)= Pn(min{ω(m;Qi −Qi+1) +O(1), ω(m;Qi −Qi+2) +O(1)}σi(log logn)1/2− µi log lognσi(log logn)1/2≤ x,m is y-typical)= Pn(min{ω(m;Qi −Qi+1), ω(m;Qi −Qi+2)}+O(1)σi(log logn)1/2− µi log lognσi(log logn)1/2≤ x,m is y-typical).Let Fn(x⃗) = Pn(Xn ≤ x1, Yn ≤ x2). By Lemma 5.6F (x⃗) = limn→∞Fn(x⃗)exists and is a nonsingular bivariate normal distribution centred at the origin with matrix ofcovarianceM =[1 aa 1]75wherea =d(Qi) + d(Qi+1)2 − 2d(Qi)d(Qi+1)d(Qi) + d(Qi+1)− 2d(Qi)d(Qi+1) .Thus by Propositions 1.26 and 5.2, and Lemma 5.3,limn→∞Pn(In ≤ x,m is y-typical)= limn→∞Pn(min{Xn, Yn} ≤ x+O(σ−1i (log logn)−1/2),m is y-typical)= limn→∞Pn(min{Xn, Yn} ≤ x)= limn→∞MnFn(x)=MnF (x)= Φ(x;− 1− a√1− a2).Theorem 1.19 If qi, qi+1 is contained in a type φ(2 : 1)-sequence, it follows for y-typical m thatqi(m) ∈ {qi−1, qi} and qi+1(m) = qi+1 by consideration of the inverse image of their totientvalues. By property (1) of Proposition 2.14, the ordering ensuresQ(m, qi(m)) = min{Q(m, qi−1),Q(m, qi)}.Thus by property (6) of Proposition 2.14Pn(In ≤ x,m is y-typical)= Pn(min{ω(m;Qi−1 −Qi+1) +O(1), ω(m;Qi −Qi+1) +O(1)}σi(log logn)1/2− µi log lognσi(log log n)−1/2≤ x,m is y-typical)= Pn(min{ω(m;Qi−1 −Qi+1), ω(m;Qi −Qi+1)}+O(1)σi(log logn)1/2− µi log lognσi(log log n)−1/2≤ x,m is y-typical).Let Fn(x⃗) = Pn(Zn ≤ x1, Xn ≤ x2). By Lemma 5.7F (x⃗) = limn→∞Fn(x⃗)exists and is a nonsingular bivarate normal distribution centred at the origin with matrix ofcovarianceM =[1 aa 1]76wherea =d(Qi)2 + d(Qi+1)− 2d(Qi)d(Qi+1)d(Qi) + d(Qi+1)− 2d(Qi)d(Qi+1) .Thus by Propositions 1.26 and 5.2, and Lemma 5.3,limn→∞Pn(In ≤ x,m is y-typical)= limn→∞Pn(min{Zn, Xn} ≤ x+O(σ−1i (log logn)−1/2),m is y-typical)= limn→∞Pn(min{Zn, Xn} ≤ x)= limn→∞MnFn(x)=MnF (x)= Φ(x;− 1− a√1− a2).Theorem 1.21 If qi, qi+1 is contained in a type φ(2 : 2)-sequence, qi ̸= 4, it follows for y-typicalm that qi(m) ∈ {qi−1, qi} and qi+1(m) ∈ {qi+1, qi+2} by consideration of the inverse imageof their totient values.By property (1) of Proposition 2.14, the ordering ensuresQ(m; qi(m)) = min{Q(m; qi−1),Q(m; qi)}Q(m, qi+1(m)) = max{Q(m; qi+1),Q(m; qi+2}.Thus by property (6) of Proposition 2.14Pn(In ≤ x,m is y-typical)= Pn(min{ω(m;Qi−1 −Qi+1) +O(1), ω(m;Qi−1 −Qi+2) +O(1),σi(log logn)1/2ω(m;Qi −Qi+1) +O(1), ω(m;Qi −Qi+2) +O(1)}σi(log logn)1/2− µi log log nσi(log log n)1/2≤ x,m is y-typical)= Pn(min{ω(m;Qi−1 −Qi+1), ω(m;Qi−1 −Qi+2),σi(log log n)1/2ω(m;Qi −Qi+1), ω(m;Qi −Qi+2)}σi(log logn)1/2+O(1)− µi log lognσi(log log n)1/2≤ x,m is y-typical).Let Fn(x⃗) = Pn(Zn ≤ x1,Wn ≤ x2, Xn ≤ x3, Yn ≤ x4). By Lemma 5.8F (x⃗) = limn→∞Fn(x⃗)77is a singular multivariate normal distribution centred at the origin with matrix of covarianceM =1 a b ca 1 c bb c 1 ac b a 1wherea =φ(qi)−1 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,b =φ(qi)−2 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,c =φ(qi)−2 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 .Thus by Propositions 1.26 and 5.2, and Lemma 5.4,limn→∞Pn(In ≤ x,m is y-typical)= limn→∞Pn(min{Zn,Wn, Xn, Yn} ≤ x+O(σ−1i (log logn)−1/2),m is y-typical)= limn→∞Pn(min{Zn,Wn, Xn, Yn} ≤ x)= limn→∞MnFn(x)=MnF (x)= Φ(x) +−2T(x;√1 + a− b− c2 + 2b)− 2T(x;√1 + a− b− c2 + 2a)+ S(4x; 2√1 + a+ b+ c, 2√1 + a− b− c, 2√1− a+ b− c).Theorem 1.22 If qi = 4, repeat the entire proof of the general φ(2 : 2)-sequence up to andincluding the definition of Fn, with the modification that qi = 4 instead of qi ̸= 4. Thus byLemma 5.9,F (x⃗) = limn→∞Fn(x⃗)is a singular multivariate normal distribution centred at the origin with matrix of covarianceM =1 5/8 1/2 1/85/8 1 −1/8 1/41/2 −1/8 1 3/81/8 1/4 3/8 1/2 .78Thus by Propositions 1.26 and 5.2, it followslimn→∞Pn(In ≤ x,m is y-typical)= limn→∞Pn(min{Zn,Wn, Xn, Yn} ≤ x+O(σ−1i (log logn)−1/2),m is y-typical)= limn→∞Pn(min{Zn,Wn, Xn, Yn} ≤ x)= limn→∞MnFn(x)=MnF (x).To complete the proofs, one need only convert the listed values of a, b, c in each case from densitiesto totient reciprocals and state the characteristic functions (including those described in Lemmata5.3 and 5.4), expectations and variances of the listed distributions.Next, the proof of Theorem 1.20. In this case, φ(qi) = φ(qi+1).Proof. Let y = φ(qi+2), and let d1 < d2 be the two elements of the doubleton fi.Furthermore, for y-typical m let q1(m), . . . , qN (m) be the ordered sequence of prime powers thatexists when m is y-typical, and for 1 ≤ j ≤ N , letQj(m) = {p prime: qj(m) | p− 1}.In =I(m; d1)σi(log logn)1/2Jn =I(m; d2)σi(log logn)1/2Xn =ω(m;Qi −Qi+1)σi(log log n)1/2.be random variables.Observe that by Proposition 1.26,Pn(In ≤ x) = Pn(In ≤ x,m is y-typical) + P (In ≤ x,m is not y-typical)= Pn(In ≤ x,m is y-typical) +O(P (m is not y-typical))= Pn(In ≤ x,m is y-typical) +Oy(log log log nlog logn).79Likewise,Pn(Jn ≤ x) = Pn(Jn ≤ x,m is y-typical) +Oy(log log log nlog log n),Pn(In + Jn ≤ x) = Pn(In + Jn ≤ x,m is y-typical) +Oy(log log log nlog log n),Pn(In − Jn ≤ x) = Pn(In − Jn ≤ x,m is y-typical) +Oy(log log log nlog log n).As φ(qi) = φ(qi+1), by properties 1, 2, 5, and 6 of Proposition 2.14, we have that for anyy-typical m,I(m; d1) =Q(m; qi)−Q(m; qi+1) if Q(m; qi) ≥ Q(m; qi+1),0 otherwise.andI(m; d2) =Q(m; qi+1)−Q(m; qi) if Q(m; qi+1) ≥ Q(m; qi),0 otherwise.ThusI(m; d1)− I(m; d2) = Q(m; qi)−Q(m; qi+1).Thus by Lemma 2.2 it followsPn(In − Jn ≤ x,m is y-typical) = Pn(Xn ≤ x+O(σ−1i (log logn)−1/2),m is y-typical).Thus by Proposition 1.26 and Lemma 5.5,limn→∞Pn(In − Jn ≤ x,m is y-typical) = limn→∞Pn(Xn ≤ x+O(σ−1i (log logn)−1/2),m is y-typical)= limn→∞Pn(Xn ≤ x)= Φ(x).Hencelimn→∞Pn(In ≤ Jn,m is y-typical) = 1/2 = limn→∞Pn(Jn ≤ In,m is y-typical)From earlier it is clear that for y-typical m, In ≤ Jn is equivalent to In = 0, and Jn ≤ In isequivalent to Jn = 0. Thuslimn→∞Pn(In = 0,m is y-typical) = limn→∞Pn(In ≤ Jn,m is y-typical) = 1/2,limn→∞Pn(Jn = 0,m is y-typical) = limn→∞Pn(Jn ≤ In,m is y-typical) = 1/2.80Thus for x > 0,limn→∞Pn(In ≤ x,m is y-typical)= limn→∞Pn(In = 0,m is y-typical) + Pn(0 < In ≤ x,m is y-typical)= 1/2 + limn→∞Pn(0 < In − Jn ≤ x,m is y-typical)= 1/2 + Φ(x)− 1/2 = Φ(x).Furthermore, for x > 0,limn→∞Pn(Jn ≤ x,m is y-typical)= limn→∞Pn(Jn = 0,m is y-typical) + Pn(0 < Jn ≤ x,m is y-typical)= 1/2 + limn→∞Pn(0 < Jn − In ≤ x,m is y-typical)= 1/2 + Φ(x)− 1/2 = Φ(x).Now observe that for y-typical m, In + Jn = x is equivalent to In = x or Jn = x for x > 0 andIn + Jn = 0 is equivalent to In = Jn = 0 which is equivalent to In − Jn = 0. Thus for x ≥ 0,limn→∞Pn(In + Jn ≤ x,m is y-typical)= limn→∞Pn(0 < In + Jn ≤ x,m is y-typical) + Pn(In + Jn = 0,m is y-typical)= limn→∞Pn(0 < In + Jn ≤ x,m is y-typical) + Pn(In − Jn = 0,m is y-typical)=[limn→∞Pn(0 < In ≤ x,m is y-typical) + Pn(0 < Jn ≤ x,m is y-typical)]+Φ(0)− Φ(0)= 2(Φ(x)− Φ(0)) = 2Φ(x)− 1= 2Φ(x)− Φ(x)− Φ(−x) = Φ(x)− Φ(−x).Combined with the earlier equation, it is thus clear thatlimn→∞Pn(In − Jn ≤ x) = Φ(x) + limn→∞Oy(log log log nlog log n)= Φ(x).and similarly,limn→∞Pn(In ≤ x) =Φ(x) if x ≥ 0,0 otherwise.limn→∞Pn(Jn ≤ x) =Φ(x) if x ≥ 0,0 otherwise.limn→∞Pn(In + Jn ≤ x) = Φ+(x).81The characteristic function follows from Lemma D.1. This completes the proof.Next, the proof of Theorem 1.24.Proof. Suppose d is a rare invariant order. Let y be a real number such that d ≤ V(y).By properties (2), (4), (5) of Proposition 2.14, if n is a y-typical number, and d ≤ V(y) then dmust be such that d = fi for some i, d = f′i for some i, or d is not an invariant factor of n.Thus by Proposition 1.26,Pn(I(m; d) > 0) ≤ Pn(m is not y-typical)≪y log log log nlog log n.Thus it followslimn→∞Pn(I(m; d) > 0) = 0.The formula for the rest of the distribution follows immediately.Finally, note that by the preceding theorems and Proposition 1.4, that Theorem 1.15 followsimmediately and trivially. This completes this section and the proof of all distribution theorems.82Chapter 6Implications of Theorems 1.15 to1.24This section will provide the proofs of Theorems 1.1, 1.8, 1.9, 1.10, 1.11, 1.12, 1.10, and 1.14. Thefirst subsection is a direct proof of Theorem 1.1 from the previously proven distribution theorems.The second subsection states and proves a proposition that relates the moments of the limitingdistributions of the invariant counting functions to the moments of the invariant counting functionsover finite intervals. The third subsection uses that proposition and the distribution theorems toprove the remaining theorems.6.1 Proof of Theorem 1.1Let d1(n), . . . , dN (n) be the first N distinct invariant factors of (Z/nZ)× for any natural number nwith at least N such distinct orders of invariant factors.Clearly,Pn((Z/mZ)× has at least N distinct invariant factors and di(m) ∈ fi for each i = 1, . . . N)is equal to1− Pn((Z/mZ)× has less than N distinct invariant factors or di(m) ̸∈ fi for some i = 1, . . . N).So it suffices to show thatlimn→∞Pn((Z/mZ)× has less than N distinct invariant factorsor there exists i ∈ {1, . . . , N} such that di(m) ̸∈ fi) = 083to prove the theorem.Now, notice that (Z/mZ)× has at least N distinct invariant factors and di(m) ∈ fi for alli = 1, . . . N is equivalent to stating that for 1 ≤ i ≤ N , ∑d∈fi I(m; d) > 0. Thus by negation itsuffices to prove thatlimn→∞Pn(∑d∈fiI(m; d) = 0 for some i = 1, . . . N)= 0.By Theorem 1.15, one may evaluate each possible limiting distribution and find thatlimn→∞Pn(∑d∈fiI(m; d) = 0 for some i = 1, . . . N)≤N∑i=1limn→∞Pn(∑d∈fiI(m; d) = 0)≤n∑i=10 = 0.Thus limn→∞ Pn(∑d∈fi I(m; d) = 0 for some i = 1, . . . N)= 0, completing the proof.6.2 Individual Invariant MomentsThe method for determining the limiting behaviour of the moments of the invariant factors shall bedone by a careful study of the moments of additive functions. We shall evaluate the moments byrelating them to the moments of strongly additive functions, again in the form given by Halberstam[5].Before this is done, we need a technical lemma to bridge the gap between expectations over theintegers 1, . . . , n and expectations restricted to only y-typical values.Lemma 6.1. Let y ≥ 1 and f : N → R be a function such that |f(m)| ≤ Unω(m) + Vn fornonnegative Un, Vn that depend only on n. Then for any real r ≥ 1 and s ∈ N,En(f(m)s)= En(f(m)s : m is y-typical)+Or,s,y((Usn + Vsn )/(log logn)r).Proof. Let T (y) be the set of y-typical integers and S(y) the set of y-atypical integers. Clearly,En(f(m)s) = En(f(m)s1T (y)) +En(f(m)s1S(y)).Also note that(Unω(m) + Vn)s ≤ (2max{Unω(m), Vn})s ≤ (2max{Usnω(m)s, Vn}) ≤ 2s(Usnω(m)s + V sn ).84Thus by the fact that |f(m)| ≤ Unω(m) + Vn and Proposition 1.26, for any real r ≥ 1|En(f(m)s1S(y))| ≤ En(|f(m)|s1S(y))≤ En(Un(ω(m) + Vn)s1S(y))≤ 2sEn((Usnω(m)s + V sn )1S(y))≪s UsnEn(ω(m)s1S(y)) + V snEn(1S(y))≪r,s,y UsnEn(ω(m)s1S(y)) + V sn(1(log logn)r).Similarly, using the same proposition,En(ω(m)s1S(y))≤ En(ω(m)s1S(y) : ω(m) ≤ (1 + ϵ) log log n) +En(ω(m)s : ω(m) > (1 + ϵ) log log n)≤ En(ω(m)s : ω(m) > (1 + ϵ) log log n) + ((1 + ϵ) log logn)sEn(1S(y))≤ En(ω(m)s : ω(m) > (1 + ϵ) log log n) +Or,y((1 + ϵ)s/(log log n)r−s).Finally, note that by a result of Hardy and Ramanujan [6, Lemma B] (see also [7, pp. xiii–xiv]for a brief discussion), there exist positive absolute constants c1, c2 such that for all k ≥ 1Pn(ω(m) = k) < c1(log log n+ c2)k−1(k − 1)! logn .Thus for n sufficiently large and ϵ ≥ e− 1,En(ω(m)s : ω(m) > (1 + ϵ) log log n)=∑k>(1+ϵ) log lognksPn(ω(m) = k)≤∑k>(1+ϵ) log lognksc1(log logn+ c2)k−1(k − 1)! logn≤ c1(log log n+ c2)slog n∑k>(1+ϵ) log logn(k − 1− s)!ks(k − 1)!(log logn+ c2)k−1−s(k − 1− s)! .Since n is sufficiently large, it holds kk−1−s ≤ c3 for for all k > log log n and some positive constantc3, thusEn(ω(m)s : ω(m) > (1 + ϵ) log log n)≤ c1cs3(log log n+ c2)slogn∑k>(1+ϵ) log logn(log logn+ c2)k−1−s(k − 1− s)!≪s (log log n)slog n∑k>(1+ϵ) log logn+1+s(log logn+ c2)kk!.85By the fact that k > (1 + ϵ)(log log n+ 1 + s) and the application of Stirling’s Formula, it followsEn(ω(m)s : ω(m) > (1 + ϵ) log log n)≪s (log log n)slog n(log logn+ c2)(1+ϵ) log logn+1+sΓ((1 + ϵ) log logn+ 2 + s)∞∑k=0(11 + ϵ)k≪s (log log n)slog n(log logn+ c2)(1+ϵ) log logn+1+s√(1 + ϵ) log logn+ 1 + s(((1 + ϵ) log logn+ 1 + s)/e)(1+ϵ) log logn+1+s× 11− 1/(1 + ϵ)≪s (log log n)s√(1 + ϵ) log logn+ 1 + s logn(e(log logn+ c2)(1 + ϵ) log logn+ 1 + s)(1+ϵ) log logn+1+s(1 + ϵϵ)≪s (log log n)s√(1 + ϵ) log logn+ 1 + s logn(e1 + ϵ)(1+ϵ) log logn+1+s≪s (log log n)s−1/2log n.This completes the proof, after adjusting r to compensate for s.The above lemma demonstrates that the difference in expectation when dropping y-atypicalnumbers is not significant. With that observation now complete, the moments of the expectationsover finite intervals can be stated and proven:Proposition 6.2. The moments of the finite distributions in Theorem 1.15 approach their limitingdistributions as n→∞. Specifically:1. If d ∈ fi, thenlimn→∞En(I(m; d)− µi log log nσi(log log n)1/2)k=∫ ∞−∞xk dF (x)whereµi = φ(qi)−1 + φ(qi+1)−1, and σ2i = φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1,where F (x) is the limiting distribution of Fn = Pn(In ≤ x) from Theorem 1.15. In otherwords, the limit of the moments of In is equal to the moments of the limiting distribution.2. If d ∈ fi, i > 1, and #fi−1#fi#fi+1 = 1, thenlimn→∞EnI(m; d) = µi log logn+Od(1).3. If d ∈ fi and i = 1 or #fi+1#fi−1 > 1 thenlimn→∞EnI(m; d) = µi log log n+Miσi(log logn)1/2 + o((log logn)1/2).86where Mi =∫∞−∞ x dF (x), where F (x) = limn→∞ Pn(In ≤ x).4. If d ∈ fi and #fi = 2, thenlimn→∞EnI(m; d) =1√2πσi(log log n)1/2 + o((log logn)1/2).5. If d is not a standard invariant order, then for any real r and k ∈ N, thenlimn→∞En(I(m; d)k) = 0andEn(I(m; d)k)≪d,k,r 1(log log n)r.Proof. Let d ∈ N and y ≥ 1 such that d < V(y). For each n ∈ N sufficiently large, letIn(m) =I(m; d)− µi log lognσi(log logn)1/2be a random variable on the probability space {1, . . . , n}.First, we prove the general case where where d ∈ fi. Define In(m), Fn(x), and F (x) as above.Observe by Lemma 2.5 thatI(m; d) ≤ I(m) ≤ ω(m) + 1.Thus|In(m)| ≤ σ−1i (log logn)−1/2I(m; d) +µiσi(log logn)1/2so by application of Lemma 6.1 withUn = σ−1i (log logn)−1/2 and Vn =2σi(log log n)1/2+µiσilog logn1/2and obtain that for any real r ≥ 1 and s ∈ N,EnIsn = En(Isn : m is y-typical) +Or,s,y(1/(log log n)r)after adjusting r and the implicit constant to account for the contributions of Un, Vn, and notingthat the values of µi, σi are constrained by y.For y-typical m let q1(m), . . . , qN (m) be they sequence of prime powers from Proposition 2.14with Q1(m), . . . , QN (m) the corresponding sets.Observe that Qi(m), Qi+1(m) can be at most four different pairs of sets on y-typical numbers,but all possible selections have the same values of the totient φ, so by Lemma 3.9, for any n,m ∈ N,Aω(n;Qi(m)−Qi+1(m)) = µi log log n+O(1) and Bω(n;Qi(m)−Qi+1(m))2= σ2i log logn+O(1).87Thus, by Lemma 4.2 for any k ∈ N,En(I2kn : m is y-typical) = En(ω(m;Qi(m)−Qi+1(m)) +O(1)− µi log lognσi(log logn)1/2: m is y-typical)2k≤ 4En(ω(m;Qi −Qi+1)−Aω(n;Qi −Qi+1) +O(1)Bω(n;Qi −Qi+1) +O(1))2k≪k En(ω(m;Qi −Qi+1)−Aω(n;Qi −Qi+1)Bω(n;Qi −Qi+1))2k+ 1≪k 1.Thus EnI2kn ≤ Cd,k for some constant that depends only on k and d. As Fn converges weakly toF , there exists a sequence of random variables Xn with corresponding distributions Fn such thatthe Xn converge to X almost surely, where X has the same distribution as F [3, Theorem 3.2.8].For the next, step we apply Theorem 1.6.8 from [3]. This theorem states that for any sequenceof random variables Xn which converge almost surely to X and functions g, h : R→ R where (i) gis non-negative with lim|x|→∞ g(x) =∞, (ii) lim|x|→∞ |h(x)|/g(x) = 0, and (iii) Eg(Xn) ≤ K <∞for all Xn, then it holds that limn→∞Eh(Xn) = Eh(X).Thus, for any k ∈ n, using g(x) = x2k and h(x) = xk, h, g satisfy conditions (i) and (ii), andEg(Xn) = EX2kn = EnI2kn ≤ Ck satisfies condition (iii) of Theorem 1.6.8,limn→∞EnIkn = limn→∞EXkn = Eh(Xn) = Eh(X) = EXk =∫ ∞−∞xk dF (x).In the special case where d ∈ fi and qi, qi+1 is a type φ(1 : 1) sequence, observe that by Lemma6.1 (using I(m; d) ≤ ω(m) + 2), Proposition 2.14, Lemma 3.15 and Lemma 3.9,EnI(m; d) = En(ω(m;Qi(m)−Qi+1(m)) +O(1) : m is y-typical) +Oy(1/(log log n)2)= En(ω(m;Qi −Qi+1)) +Oy(1)= Aω(n;Qi −Qi+1) +Oy(1)= µi log logn+Oy(1).The remainder of the asymptotic expectations of the counting function of the universal factororders are simply rearrangements of the general result.In the case where d is not a standard invariant order, observe by Proposition 2.14, that I(m; d) =0 for y-typical m, and thus as I(m; d) ≤ ω(m) + 2, by Lemma 6.1 it follows for any real r ≥ 1 ands ∈ N thatEnI(m; d)s = En(I(m; d)s : m is y-typical) +Or,s,y(1/(log log n)r)≪r,s,d 1/(log logn)r.This completes the proof. Note that y becomes d in the final statement because the optimal choiceof y is constrained only by d.88This completes the statement and proof of the proposition that connects expectations of thedistribution of invariant factors in the multiplicative group over {1, . . . , n} to the expectations ofthe corresponding limiting distribution. With this proven, it is now possible to begin the section onthe proofs of asymptotic formulas for the expectation theorems. One final note is that the aboveproposition could also be used to determine the asymptotics for the variances and higher momentsof the distributions in terms of the limiting distributions, where those limiting distributions haveexplicit characteristic functions, not just the expectations, as are studied in the next section.6.3 Proofs of Theorems 1.8 to 1.14From the proposition in the preceding section the proofs of Theorems 1.8 to 1.14 follow quickly.Observe thatTheorem 1.8 This is immediate from items (2) and (3) in Proposition 6.2 after including all(log log n)1/2 in the big-O error term.Theorem 1.9 This is item (2) from Proposition 6.2.Theorems 1.10, 1.12 (excluding d = 12), 1.13 Proof. Consider item (3) from Proposition 6.2,combined with Theorems 1.19, 1.21 and 1.23 for the appropriate limiting distribution. As Miis the expectation of a random variable in the appropriate limiting distribution, the evaluationof the derivative of the characteristic function at t = 0 can be done to find Mi.If this is done, the only terms which contribute a nonzero value to the derivative of thecharacteristic function are the −ie−t2/2 erfi(. . .) terms (once expanded). The square roots ofthe form√φ(qi)−1 − φ(qi)−2 only appear when φ(qi) = φ(qi−1) which means√φ(qi)−1 − φ(qi)−2 = σi−1√2.Likewise√φ(qi+1)−1 − φ(qi+1)−2 only appears when φ(qi+1) = φ(qi+2) so√φ(qi+1)−1 − φ(qi+1)−2 = σi+1√2.Taking the derivative of −ie−t2/2 erfi ( σi±12√2σi)and evaluating it at t = 0 yields−i σi±1√2πσi.Hence the expectation contribution for the −ie−t2/2 erfi ( σi±12√2σi)term is− σi±1√2πσi.89Thus by Proposition 6.2, the formulas in Theorems 1.10, 1.12, and 1.13 follow immediately,except in the case where d = 12 since there is no characteristic function for that distribution.In the case where d = 12, the underlying limiting distribution does not have an explicitcharacteristic function, so it must be handled separately.Theorem 1.11 This is item (4) from Proposition 6.2, with observation that the expectation of asum of two random variables is the sum of their expectations.Theorem 1.12 for d = 12 Proof. Consider item (3) from Proposition 6.2 and Theorems 1.9, 1.10,1.12 excluding d = 12, 1.13, and 1.11. It follows thatEn7∑i=1∑d∈fiI(m; d) =7∑i=1∑d∈fiEnI(m; d)=78log log n+(M3σ3 +√14π+√316π+ o(1))(log log n)1/2.Let y = 8. By Proposition 2.14 it follows that every y-typical number is such that everyinvariant factor not divisible by 16 is in a universal factor order set and thus must be in auniversal factor order set of index between 1 and 7. Furthermore, the total number of invariantfactors not divisible by 16 must be by property (6) of that proposition for any y-typical n ∈ N7∑i=1I(n; di) =7∑i=1Q(n; qi)−Q(n; qi+1)= Q(n; q1)−Q(n; q8) = Q(n; 2)−Q(n; 16).The last equality holds by the fact that q1 = q1 = 2 and q8 must correspond to the largesttotient value in the first eight elements of the total φ-sequence, which implies q8 = 16. Aseach universal factor order set from index 1 to 7 can have at most one representative in theinvariant factor orders for a specific y-typical n it follows by Lemma 2.27∑i=1∑d∈fiI(n; d) = Q(n; 2)−Q(n; 16) = ω(n;S − T ) +O(1),with S being the set of odd primes, T being the set of primes equal to 1 modulo 16.90Thus by Lemma 6.1 (using I(m; d) ≤ ω(m) + 2), Lemma 3.15 and Lemma 3.9,En7∑i=1∑d∈fiI(n; d) = En(ω(m;S − T ) +O(1)) +O(1/(log log n)2)= Aω(n;S − T ) +O(1)=(1− 18)log logn+O(1)=78log logn+O(1).Thus78log logn+(M3σ3 +√14π+√316π+ o(1))(log logn)1/2=78log log n+O(1),which means after cancellation and rearrangement that(M3σ3 +√14π+√316π)(log log n)1/2 = o((log log n)1/2).The only possible value of M3σ3 for which this is consistent isM3σ3 = −√14π−√316π.Given item (3) from Proposition 6.2 and the value of M3σ3 the theorem is proven..Theorem 1.14 This is item (5) from Proposition 6.2.This completes the proofs of all the results described in the introduction.91Chapter 7Counting Subgroups of (Z/nZ)×In this section, the work considers another application of the techniques developed in precedingsections to find the distribution of the invariant factors of (Z/nZ)×. The alternative applicationis the determination of the limiting distribution of the counting function of any fixed nontrivialabelian subgroup G of (Z/nZ)×.First, the counting functions of interest are defined:Definition 7.1. Let P(G; q) to be the number of elementary divisors of G with order q, Q(G; q)to be the number of elementary divisors of G with orders divisible by q, and letS(m;G) = max{a : Ga ≤ (Z/mZ)×}.To make the initial statement clear, the purpose of this section is to find a limiting distributionfunction for S(m;G) over {1, . . . , n} as n→∞ for any fixed nontrivial abelian group G. The firststep is to relate Ga being a subgroup of a multiplicative group to statements concerning Q(G; q)and Q(n; q):Lemma 7.2. Let G be an abelian finite group and n ∈ N. The statement Ga ≤ (Z/nZ)× isequivalent to the statement that for all prime powers q, aQ(G; q) ≤ Q(n; q).Proof. Clearly, by the definition of P(n; q) and P(G; q),Ga ∼=∏qZaP(G,q)q , (Z/nZ)× ∼=∏qZP(n,q)q .ThusGa ≤ (Z/nZ)× is equivalent to∏qZaP(G,q)q ≤∏qZP(n,q)q .92For any prime powers q and q′, Zq ≤ Zq′ if and only if q | q′, so by the definition of Q(n; q) andQ(G; q),Ga ≤ (Z/nZ)× is equivalent to aQ(G; q) ≤ Q(n; q) for all prime powers q.To emphasize why this is the correct equivalence, observe that if pk is the largest power of p whereP(G, pα) > 0, then for every 0 < ℓ ≤ k, the condition “aQ(G; q) ≤ Q(n; q) for all prime powers q”givesaQ(G; pk−ℓ) = aℓ∑α=0P(G; pk−α) ≤ Q(G; pk−ℓ) for every 0 < ℓ ≤ k,which by rearrangement becomesaP(G; pk−ℓ) ≤ Q(G; pk−ℓ)− aℓ−1∑α=0P(G; pk−α) for every 0 < ℓ ≤ k,which by induction on ℓ demonstrates that for any such pk, there are enough cyclic groups inthe elementary divisors of (Z/nZ)× with orders divisible by pk−ℓ to accomodate the divisors oforder pk−ℓ after accounting for the groups already “taken” by higher powers of p. Furthermore,the highest power of p where P(G; pk) > 0, pk is accomodated by the fact that aP(G; pk) =aQ(G; pk) ≤ Q(n; pk). Taken together, this completes the proof.The next stage is to use some elementary group theory to relateS(m;G) toQ(G; q) and ω(m;Q):Lemma 7.3. For any nontrivial abelian finite group G and m ∈ N, it holds thatS(m;G) =⌊minq,Q(G;q)>0Q(m; q)Q(G; q)⌋=(minq,Q(G;q)>0ω(m;Q)Q(G; q))+O(1),where Q = {p prime : q | p− 1}.Proof. By Definition 7.1 and Lemma 7.2, and the fact that for a nontrivial G there is at least oneprime power q such that Q(G, q) > 0,S(m,G) = max{a ∈ N : a ≤ Q(m, q)Q(G, q)for all prime powers q such that Q(G, q) > 0}.The rest of the lemma follows from Lemma 2.2.Just as for invariant factors the concept of a y-typical number is necessary, the following condi-tion, called G-typicality for natural numbers, will be needed to find the limiting distribution:Definition 7.4. Let G be an abelian finite group. A natural number m is considered G-typical iffor all prime powers q1, q2 where φ(q1)Q(G, q1) > φ(q2)Q(G, q2) > 0 it follows thatω(m; { prime p : q1 | p− 1})Q(G, q1)≤ ω(m; { prime p : q2 | p− 1})Q(G, q2).93As is the case with y-typical numbers, G-typical numbers are common:Proposition 7.5. Let G be an abelian finite group. Then for any real r,Pn(m is not G-typical)≪r,G 1(log logn)r,andlimn→∞Pn(m is G-typical) = 1.Proof. First, note that if G is the trivial group, all m ∈ N are trivially G-typical, which implies thelemma for trivial G. If there is only one prime power q such that Q(G; q) > 0, it is a cyclic groupwhose order is prime, so all m ∈ N are trivally G-typical, proving the lemma in this case. For therest of the proof, we assume that the number of distinct prime powers q such that Q(G; q) > 0, N ,is at least 2.Let q1, . . . , qN be the set of prime powers such thatQ(G, qi) > 0, ordered so that φ(qi)Q(G, qi) ≤φ(qj)Q(G, qj) for all i < j. Let Qi = {p prime: q | p− 1}.Let ti = (φ(qi)Q(G, qi))−1, ti+ the maximum ti strictly less than ti, and ti− the minimum tistrictly greater than ti. Then letδ1 =13(t1 − t1+), δN =13(tN− − tN)when ,δi =13min(ti− − ti, ti − ti+)for 1 < i < N.If m is not a G-typical number, there exists some qi such that ω(m;Qi)/Q(G, qi) is far fromthe value ti log logn for some n ≥ m. Thus by Lemma 4.3, for n sufficiently large, and any r ≥ 2it followsPn(m is not G-typical) ≤N∑i=1Pn(|ω(m;Qi)/Q(G; qi)− ti log logn| > δi log log n)≤N∑i=1Pn(|ω(m;Qi)− φ(qi)−1 log log n| > δiQ(G; qi) log log n)≪rN∑i=11(δiQ(G; qi))2r(log log n)r≪r,G 1(log logn)r.The rest of the lemma follows immediately.Note that the dependence on G in the above proposition is complicated. Replacing G with asequence of groups that changes with n requires substantial technical constraints on changes to94elementary divisors of G. As this section is mostly for illustrative purposes, this has not been donehere.With all this said, it is now possible to state and prove in full the theorem characterizing thelimiting distribution of the counting function S(m;G):Theorem 7.6. Let G be a nontrivial abelian finite group, µG = min{(φ(q)Q(G; q))−1 : Q(G; q) >0}, and q1, . . . , qN are the distinct elementary divisors of G such that the quantity φ(qi)Q(G; qi) =µ−1G . Let Q1, . . . , QN be the sets such that Qi = {p prime : qi | p− 1}.Then there exists a distribution function F (x) such thatlimn→∞Pn(S(m;G)− µG log logn(µG log log n)1/2≤ x)=MnH(x),where H(x1, . . . , xN ) = F (Q(G, q1)1/2x1, . . . ,Q(G, qN )1/2xN ) and F (x1, . . . , xN ) is the cumulativedistribution function of a random vector X with characteristic functionφX(t1, . . . , tN ) = exp(− 12N∑i=1N∑j=1(φ(qi)φ(qj))1/2φ(lcm(qi, qj))titj).Note that F is always a multivariate normal distribution.Proof. By Proposition 7.5,Pn(S(m;G)− µG log log n(µG log logn)1/2≤ x)= Pn(S(m;G)− µG log log n(µG log logn)1/2≤ x,m is G-typical)+Or,G((log log n)−r).When m is G-typical, by Definition 7.4 and Lemma 7.3, it follows thatS(m;G) =(minq,Q(G;q)>0ω(m;Q)Q(G; q))+O(1) =(min1≤i≤Nω(m;Qi)Q(G; qi))+O(1).Thus by definingHn(x1, . . . , xN ) = Pn( ω(m;Q1)Q(G;q1)− µG log log n(µG log logn)1/2≤ x1, . . . ,ω(m;QN )Q(G;qN )− µG log log n(µG log logn)1/2≤ xN)it follows by Definition 5.1 and Propositions 5.2 and 7.5 thatPn(S(m;G)− µG log logn(µG log logn)1/2≤ x,m is G-typical)=MnHn(x) +Or,G((log log n)−r).ThusPn(S(m;G)− µG log log n(µG log logn)1/2≤ x)=MnHn(x) +Or,G((log log n)−r).95By Lemma 3.14 we have thatlimn→∞Pn(ω(m;Q1)− φ(q1)−1 log logn(φ(q1)−1 log log n)1/2≤ x1, . . . , ω(m;QN )− φ(qN )−1 log logn(φ(qN )−1 log logn)1/2≤ xN)= F (x1, . . . , xN )where F (x1, . . . , xN ) is as defined above.Asω(m;Qi)Q(G;qi)− µG log logn(µG log log n)1/2≤ xi is equivalent to ω(m;Qi)− φ(qi)−1 log logn(φ(qi)−1 log logn)1/2≤ Q(G; qi)1/2xiit thus follows thatlimn→∞Hn(x1, . . . , xN ) = F (Q(G; q1)1/2x1, . . . ,Q(G; qN )1/2xN ) = H(x1, . . . , xN )from the definition of H(x1, . . . , xN ) above. Thuslimn→∞Pn(S(m;G)− µG log logn(µG log logn)1/2≤ x)= limn→∞MnHn(x) +Or,G((log logn)−r) =MnH(x).This completes the proof.The above theorem is fairly abstract, but in the special case where there is only one prime powerq such that Q(G; q) > 0 and q obtains the maximum value for φ(q′)Q(G; q′) among all prime powersq′ with Q(G; q′) > 0, the resulting distribution is a univariate normal distribution. One broad classof groups which will satisfy this condition are cyclic groups with squarefree order.Due to Lemma 2.6, cyclic groups in general are either univariate normal distributions or thedistribution produced by the minimum of a bivariate normal distibution in the case where thelargest value of φ(q) among the prime power divisors of the order of the group has a tie between aprime p and a higher prime power q.96Bibliography[1] A. Azzalini. A class of distributions which includes the normal ones. Scand. J. Statist.,12(2):171–178, 1985.[2] Ben Chang and Greg Martin. The smallest invariant factor of the multiplicative group. Int.J. Number Theory, 16(6):1377–1405, 2020.[3] Rick Durrett. Probability: Theory and Examples. Cambridge University Press, 2010.[4] A. Granville and K. Soundararajan. Sieving and the Erdo˝s–Kac theorem. In Equidistributionin number theory, an introduction, volume 237 of NATO Sci. Ser. II Math. Phys. Chem., pages15–27. Springer, Dordrecht, 2007.[5] H. Halberstam. On the distribution of additive number-theoretic functions. J. London Math.Soc., 30:43–53, 1955.[6] G. H. Hardy and S. Ramanujan. The normal number of prime factors of a number n [Quart.J. Math. 48 (1917), 76–92]. In Collected papers of Srinivasa Ramanujan, pages 262–275. AMSChelsea Publ., Providence, RI, 2000.[7] Jonas Kubilius. Probabalistic Methods in the Theory of Numbers, volume 11 of Translations ofMathematical Monographs. American Mathematical Society, 1964.[8] Greg Martin and Lee Troupe. The distribution of the number of subgroups of the multiplicativegroup. J. Aust. Math. Soc., 108:46–97, 2022.[9] Hugh L. Montgomery and Robert C. Vaughan. The large sieve. Mathematika, 20:119–134,1973.[10] Hugh L. Montgomery and Robert C. Vaughan. Multiplicative Number Theory I. ClassicalTheory, volume 97 of Cambridge studies in advanced mathematics. Cambridge UniversityPress, 2007.97[11] Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery. An Introduction to the Theoryof Numbers. John Wiley & Sons, Inc., 1991.[12] Donald B. Owen. Tables for computing bivariate normal probabilities. Ann. Math. Statist.,27:1075–1090, 1956.[13] Y. L. Tong. The multivariate normal distribution. Springer Series in Statistics. Springer-Verlag,New York, 1990.98Appendix AConsolidated TheoremsThe introduction section splits the theorems in this work into small pieces for the purpose offacilitating the exposition. In this section, the theorems are consolidated for ease of use when beingapplied or referenced. The cases for these theorems are named after patterns described in Lemma2.7 but those patterns are not necessary to understand these theorems.The first theorem concerns asymptotic expectations of I(m; d):Theorem A.1. For any d ∈ N, the first case and one of the following cases (except the last) appliesif d ∈ fi for some i ∈ N and the last case applies otherwise.General Case If d ∈ fi, thenEn(I(m; d)) = µi log logn+Od((log logn)1/2).Type (1 : 1) Case If d ∈ fi and i > 1 with #fi−1 = #fi = #fi+1 = 1, thenEn(I(m; d)) = µi log logn+Od(1).Type (2 : 1) Case If d ∈ fi and i > 1 with #fi−1 = 2 and #fi = #fi+1 = 1, thenEn(I(m; d)) = µi log logn−(σi−1√2π+ o(1))(log logn)1/2.Type (2) Case If d ∈ fi and #fi = 2, thenEn(I(m; d)) =(σi√2π+ o(1))(log logn)1/2.Type (2 : 2) Case If d ∈ fi and i > 1 with #fi−1 = 2 and #fi+1 = 2, thenEn(I(m; d)) = µi log log n−(σi−1 + σi+1√2π+ o(1))(log log n)1/2.99Type (1 : 2) Case If d ∈ fi and i = 1 or #fi−1 = #fi = 1 and #fi+1 = 2, thenEn(I(m; d)) = µi log logn−(σi+1√2π+ o(1))(log logn)1/2.Rare Factor Case If for every i ∈ N, the natural number number d > 1 is such that d ̸∈ fi, thenfor any k ∈ N, and r > 0,En(I(m; d)k)≪d,r,k (log logn)−r.The second theorem concerns the limiting distribution of I(m; d):Theorem A.2. Let d ∈ N. If d is a universal factor order, (d ∈ fi for some i), the limitingdistribution of I(m; d) under appropriate rescaling is fully characterized by the number of elementsin fi, fi−1, fi+1, except for the special cases where i = 1 or i = 3. If d is a rare factor order, (d ̸∈ fifor any i ∈ N), then the limiting distribution is fully characterized by this fact.Type (1 : 1) Case If i > 1 and #fi−1 = #fi = #fi+1 = 1, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log logn)1/2≤ x)= Φ(x),where Φ(x) is the standard normal distribution with characteristic function e−t2/2.Type (2 : 1) Case If i > 1 and #fi−1 = 2 and #fi = #fi+1 = 1, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log log n)1/2≤ x)= Φ(x;− 1− a√1− a2),wherea =φ(qi)−2 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,and Φ(x;λ) is the skew normal distribution with parameter lambda. The characteristic func-tion of this distribution ise−t2/2(1− i erfi(√φ(qi)−1 − φ(qi)−22σit)).Type (2) Case If #fi = 2, then for d ∈ filimn→∞Pn(I(m; d)σi(log logn)1/2≤ x)=Φ(x) if x ≥ 0,0 otherwise.Furthermore,limn→∞Pn( ∑d∈fi I(m; d)σi(log logn)1/2≤ x)= Φ+(x).This distribution has characteristic function e−t2/2(1 + i erfi(t/√2)).100Type (2 : 2) Case I If i > 3 and #fi = 1 and #fi−1 = #fi+1 = 2, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log logn)1/2≤ x)= Φ(x)+ 2T(x;−√1 + a− b− c2 + 2b)+ 2T(x;−√1− a+ b− c2 + 2a)+ S(4x; 2√1 + a+ b+ c, 2√1 + a− b− c, 2√1− a+ b− c),wherea =φ(qi)−1 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,b =φ(qi)−2 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,c =φ(qi)−2 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 .The characteristic function of this distribution ise−t2/2(1− i erfi(√φ(qi)−1 − φ(qi)−22σit)− i erfi(√φ(qi+1)−1 − φ(qi+1)−22σit)− erfi(√φ(qi)−1 − φ(qi)−22σit)erfi(√φ(qi+1)−1 − φ(qi+1)−22σit).Type (2 : 2) Case II If i = 3, thenlimn→∞Pn(I(m; 12)− 1/4 log log n( 12 log logn)1/2≤ x)=MnF (x),where Mn is from Definition 5.1, and F is the singular multivariate normal distributioncentred at the origin with matrix of covarianceM =1 5/8 1/2 1/85/8 1 −1/8 1/41/2 −1/8 1 3/81/8 1/4 3/8 1/2 .Type (1 : 2) Case If i = 1 or if i > 1 and #fi−1 = #fi = 1, #fi+1 = 2, then for d ∈ filimn→∞Pn(I(m; d)− µi log lognσi(log log n)1/2≤ x)= Φ(x;− 1− a√1− a2),101wherea =φ(qi)−1 + φ(qi+1)−2 − 2φ(qi)−1φ(qi+1)−1φ(qi)−1 + φ(qi+1)−1 − 2φ(qi)−1φ(qi+1)−1 ,and Φ(x;λ) is the skew normal distribution with parameter lambda. The characteristic func-tion of this distribution ise−t2/2(1− i erfi(√φ(qi+1)−1 − φ(qi+1)−22σit)).Rare Factor Case For any natural number d where d is a rare factor order, thenlimn→∞Pn(I(m; d) ≤ x) =1 if x ≥ 0,0 otherwise.For any d ∈ N, exactly one of the above cases applies.102Appendix BTechnical Proofs Using Bertrand’sPostulateThe following lemmas are proven here:Lemma 2.8: If pα1 , pβ2 is a φ(1 : 1)-sequence, then p1 ̸= p2.Lemma 2.9: If pα1 , p2, pβ3 is a φ(1 : 2)-sequence other than 2, 3, 4, then all three primes are distinct.Lemma 2.10: If p1, pα2 , pβ3 is a φ(2 : 1)-sequence, then all three primes are distinct.Lemma 2.11: If p1, pα2 , p3, pβ4 is a φ(2 : 2)-sequence other than 3, 4, 5, 8, then all four primes aredistinct.For these proofs, we make use of Bertrand’s Postulate [11, pg. 367], the statement that for anyreal x > 1, there exists a prime in the open interval (x, 2x).First, the proof of Lemma 2.8:Proof. We prove by contradiction. Assume p2 = p1. Then pα1 , pβ2 is a φ-sequence. Since pα+11 is thesmallest power of p1 with totient larger than φ(pα1 ), it follows from the properties of a φ-sequencethat pβ2 = pα+11 , and from a φ(1 : 1)-sequence that there is no prime p3 such that pα1 < p3 andφ(p3) ≤ φ(pα+11 ).Thus the interval (pα1 , pα1 (p1 − 1) + 1] contains no primes. If p1 ≥ 3, p1 − 1 ≥ 2, and thus theinterval (pα1 , 2pα1 ] contains no primes, which is impossible by Bertrand’s Postulate.If p1 = p2 = 2, then we can further observe that α > 1 since 2, 3 is not a φ-sequence and thatthere is no prime p4 such that φ(2α) ≤ φ(p4) ≤ φ(2α+1) and thus there are no primes in the interval(2α−1, 2α], which is impossible.103Thus, by contradiction, it follows p1 ̸= p2.Second, the proof of Lemma 2.9:Proof. From Lemma 2.6 we have that p2 ̸= p3. Trivially, as φ(pα1 ) < φ(p2), this implies p1 − 1 <p2 − 1 and thus p1 < p2. Thus the only possible equality is between p1 and p3.We prove p1 ̸= p3 by contradiction. Assume p1 = p3. Then by the properties of φ-sequences,pβ3 = pα+11 . Furthermore, p2 − 1 = φ(pα+13 ) and thus pα3 (p3 − 1) < p2.Thus there is no prime p4 such that pα1 < p4 and φ(p4) < φ(pα+13 ) = φ(pα+11 ). Thus there are noprimes in the interval (pα1 , pα1 (p1 − 1)] and thus if p1 ≥ 3, the interval (pα1 , 2pα1 ] contains no primes.If p1 = p2 = 2, then either α > 1 or 2, 3, 4 is the φ(1 : 2)-sequence in question. By assumption,we are not considering the 2, 3, 4 sequence, so it follows that α > 1. Thus we obtain that there isno prime p5 such that φ(2α) ≤ φ(p5) < φ(2α+1). Thus the interval (2α−1, 2α] contains no primes,which is impossible.Thus we determine that p1 ̸= p3 with the exception of sequence 2, 3, 4.Third, the proof of Lemma 2.10:Proof. From Lemma 2.6 we have that p1 ̸= p2. Thus the only possiblilities are that p1 = p3 orp2 = p3.First, we prove by contradiction that p1 ̸= p3. If p1 = p3 ≥ 3, the φ-sequence condition impliesthat pβ3 = p21. Furthermore, by Lemma 2.6 we have that pα2 cannot be prime. By the Type (2 : 1)condition there is no prime p such that p1 < p and φ(p) ≤ φ(p21). Thus there are no primes in theinterval (p1, p1(p1 − 1)] and thus as p1 ≥ 3, no primes in (p1, 2p1], which is impossible.In the case where p1 = p3 = 2, we observe simply that 2, 3, 4 is not a φ(2 : 1)-sequence.Second, we prove by contradiction that p2 ̸= p3. In the case where p2 = p3 ≥ 3, we get fromthe properties of the φ-sequence that pβ3 = pα+12 . By Lemma 2.6 we have that p1 < pα2 . Thus bythe φ-sequence properties, there is no prime number p such that pα2 < p and φ(p) ≤ φ(pα+12 ). Thusthe interval (pα2 , pα2 (p − 1)] contains no primes, so since p2 ≥ 3, we get that (pα2 , 2pα2 ] contains noprimes, which is impossible.In the case where p2 = p3 = 2, we note by Lemma 2.6 that α > 1 and thus 2α is not prime.Thus by the properties of the φ-sequence, p3 = 2α+1 and that there cannot be a prime p suchthat φ(2α) < φ(p) ≤ φ(2α+1). By the φ(2 : 1)-sequence properties, we also know that φ(2α+1) + 1cannot be prime. Thus there are no primes in the interval (2α−1+1, 2α+2], which is impossible.Finally, the proof of Lemma 2.11:104Proof. From Lemma 2.6 we have that p1 ̸= p2 and p3 ̸= p4. We also have trivially, that p1 < p3and p2 < p3. Thus the only possibilities are that p1 = p4 or p2 = p4.First, we prove by contradiction that p1 ̸= p4. In the case where p1 = p4 ≥ 3, we get by theφ-sequence properties that pβ4 = p21. We also note that by Lemma 2.6 that pα2 cannot be prime, soα > 1, and thus there is no prime p such that p1 < p and φ(p) < φ(p21). Thus there are no primesin the interval (p1, p1(p1 − 1)] which as p1 ≥ 3, implies that there are no primes in (p1, 2p1], whichis impossible.In the case where p1 = p4 = 2, we observe simply that 2, 3, 4 is not a φ(2 : 2)-sequence.Second, we prove by contradiction that p2 ̸= p4. In the case where p2 = p4 ≥ 3, we get by the φ-sequence properties that pβ4 = pα+12 . We also obtain by Lemma 2.6 that p1 < pα2 and φ(pα+12 ) < p3.Thus by the proper condition, there is no prime number p such that pα2 < p and φ(p) < φ(pα+12 ).Thus the interval (pα2 , pα2 (p2 − 1)] contains no primes which implies (pα2 , 2pα2 ] contains no primes,which is impossible.In the case where p2 = p4 = 2, this implies by the φ-sequence properties that p1 = 2α−1 + 1and p2 = 2α + 1, which means one of α, α − 1 is odd which implies one of p1, p2 is 0 modulo 3.Thus if we consider any φ(2 : 2)-sequence other than 3, 4, 5, 8, one of p1, p2 is not prime, which is acontradiction.105Appendix CProofs of RemarksThe following is a proof of 2.3.Proof. First, observe thatΨ(x) =∑pα≤xlog p =∑p⌊log xlog p⌋log p = log lcm{pα : pα ≤ x}.Since pα ≤ x implies φ(pα) ≤ x, we thus obtain that logV(x) ≥ Ψ(x).Furthermore, given the set S(x) = {pα : φ(pr) ≤ x < pα}, it is clear thatlogV(x)−Ψ(x) =∑pα∈S(x)log p.Finally, note that given Sr(x) = {pr : φ(pr) ≤ x < pr}, we obtain with R =⌈log xlog 2⌉thatS(x) =⋃Rr=1 Sr(x) and each Sr(x) is pairwise disjoint. ThuslogV(x)−Ψ(x) =R∑r=1∑pr∈Sr(x)log p.Observe that if pr ∈ Sr(x), then pr(1− 1/p) ≤ x ≤ pr and since (1− 1/p)1/r ≥ (1− 1/p) for allprimes, that we obtain that p − 1 ≤ x1/r ≤ p, with the first inequality being strict for r > 1. AsSr(x) ⊆ N, we thus find for x > 3 that there can be at most one element in Sr(x).106Thus for x > 3,logV(x)−Ψ(x) =R∑r=1∑pr∈Sr(x)log p≤R∑r=1log(x1/r + 1)≤R∑r=11rlog x+ 1≤ R+ log xR∑r=11r≤ R+ log x(logR+ 1)≤ log xlog 2+ 1 + log x(log(log xlog 2+ 1) + 1)≤ log x log log x+ (2 + 1log 2− log log 2) log x+ 1.Thus it follows that logV(x)−Ψ(x)≪ log x log log x.For W(x), simply observe thatW(x) =∑φ(p)≤x1=∑pα≤x1 +∑φ(pα)≤x<pα1 = Π(x) + S(x)= Π(x) +R∑r=1Sr(x)≤ Π(x) +R∑r=11 ≤ Π(x) +R = Π(x) + ⌈ log xlog 2⌉.Thus W(x)−Π(x)≪ log x.107Appendix DProbability DistributionsWe first obtain the characteristic function of the truncated normal.Lemma D.1. Suppose X is a random variable with distribution P (X ≤ x) = Φ+(x/σ), Then thecharacteristic function of X isφX(t) = e−σ2t22(1 + i erfi(σt√2)).Proof. We use a method similar to the proof given for the normal distribution in [3]. Recall thatfor a normal random variable Y with variance σ has characteristic functionφY (t) = exp(−σ2t2/2) =∫Reitσxe−x2/2√2πdx = 2∫ ∞0cos(tσx)e−x2/2√2π dxGiven the above, it follows thatφX(t) = EeitX= 2∫ ∞0eitxe−x22σ2√2πσdx= 2∫ ∞0eitσxe−x2/2√2πdx= 2∫ ∞0cos(tσx)e−x2/2√2πdx+ 2i∫ ∞0sin(tσx)e−x2/2√2πdx= exp(−σ2t2/2) + 2i∫ ∞0sin(tσx)e−x2/2√2πdx.108Now let f(t) =∫∞0sin(tx) e−x2/2√2πdx. Observe thatf ′(t) =∂∂t∫ ∞0sin(tx)e−x2/2√2πdx=∫ ∞0∂∂tsin(tx)e−x2/2√2πdx=∫ ∞0x cos(tx)e−x2/2√2πdx= −(cos(tx)e−x2/2√2π)∥∥∥∥x=∞x=0−∫ ∞0t sin(tx)e−x2/2√2πdx=1√2π− tf(t).This is a first order linear differential equation. It is trivial to verify thatf(t) = e−t2/2∫ t0ex2/2√2πdxis the solution, as it is clear that f(0) = 0.Thus, by substitution of f into the φX(t) equation, we obtain thatφX(t) = exp(−σ2t2/2) + 2if(σt)= exp(−σ2t2/2) + 2i exp(−σ2t2/2)∫ σt0ex2/2√2πdx= exp(−σ2t2/2) + 2i exp(−σ2t2/2)∫ σt/√20ex2√πdx= exp(−σ2t2/2)(1 + i erfi(σt√2)).This completes the proof.Next, we determine that the sum of a random variable with a normal distribution and a truncatednormal distribution yields a skew normal distribution as described in Definition 1.16.Lemma D.2. It holds for σ1, σ2 > 0 thatϕ(x/σ1)σ1∗ ϕ+(x/σ2)σ2=ϕ( x√σ21+σ22; σ2σ1 )√σ21 + σ22,ϕ(x/σ1)σ1∗ ϕ−(x/σ2)σ2=ϕ( x√σ21+σ22;−σ2σ1 )√σ21 + σ22.109Furthermore, if X,Y are independent random variables with P (X ≤ x) = Φ(x/σ1) and P (Y ≤x) = Φ+(x/σ2), thenP (X + Y ≤ x) = Φ( x√σ21 + σ22)− 2T( x√σ21 + σ22,σ2σ1),P (X − Y ≤ x) = Φ( x√σ21 + σ22)− 2T( x√σ21 + σ22,−σ2σ1).We also obtain that the characteristic functions of X + Y and X − Y areφX+Y (t) = e−(σ21+σ22)t2/2(1 + i erfi(σ2t√2))φX−Y (t) = e−(σ21+σ22)t2/2(1− i erfi(σ2t√2)).Proof. Let σ1, σ2 and X,Y be as described above. For brevity, let Σ =√σ21 + σ22 . Then theprobability density function of X + Y is f(x) = ϕ(x/σ1)σ1 ∗ϕ+(x/σ2)σ2, and thus,f(x) =∫ ∞−∞ϕ(x−yσ1 )σ1ϕ+(yσ2)σ2dy=∫ ∞0exp(− 12 ( (x−y)2σ21+ y2σ22))πσ1σ2dy=∫ ∞0exp(− 12σ21σ22(σ22x2 − 2σ22xy +Σ2y2))πσ1σ2dy=∫ ∞0exp(− 12σ21σ22(Σ2(y2 − 2 σ22Σ2xy + σ42Σ4x2) +σ21σ22Σ2 x2))πσ1σ2dy=√2e−x22Σ2√πΣ∫ ∞0exp(− Σ22σ21σ22(y − σ22Σ2x)2)√2π σ1σ2Σdy=√2e−x22Σ2√πΣ∫ ∞− σ2σ1Σxe−u22√2πdu=√2e−x22Σ2√πΣΦ(σ2σ1Σx)= 2ϕ( xΣ )Φ(σ2σ1Σx)Σ=ϕ( xΣ ;σ2σ1)Σ.Thus f(x) is the probability density function of a skew normal distribution and the cumulativedensity function follows immediately by integration. As the case for g(x) = ϕ(x/σ1)σ1 ∗ϕ−(x/σ2)σ2is110very similar, we will simply noteg(x) =∫ ∞−∞(ϕ(x−yσ1 )σ1ϕ+(− yσ2 )σ2dy=∫ 0−∞exp(− 12 ( (x−y)2σ21+ y2σ22))πσ1σ2dy=√2e−x22Σ2√πΣ∫ − σ2σ1Σx−∞e−u22√2πdu=ϕ( xΣ ;−σ2σ1 )Σ.The cumulative distribution functions for X+Y and X−Y follow immediately follow immediately.By the characteristic function of the normal distribution and Lemma D.1, we obtain thatφX+Y (t) = φX(t)φY (t) = e−(σ21+σ22)t2/2(1 + i erfi(σ2t√2)).For the X − Y result, note that φ−Y (t) = φY (t) and the result is immediate.Next, we describe the inversion formulas for terms that will appear in the characteristic functionsof probability distributions used in this section. The first is a well-known result about Owen’s Tfunction.Lemma D.3. For α > 0 and β, with |β| < α, we have thatlimT→∞12π∫ T−Te−itxitie−α2t2/2 erfi(βt√2)dt = −2T(xα,β√α2 − β2).Proof. Let α > 0 and 0 < β < α. Let σ1 =√α2 − β2, σ2 = β and Σ =√σ21 + σ22 = α. Note thatσ1, σ2 > 0 by definition. By the characteristic function inversion formula and Lemma D.2 we havethatΦ( xΣ)− 2T( xΣ,σ2σ1)= limT→∞12π∫ T−Te−itxite−Σ2t2/2(1 + i erfi(σ2t√2))dt.We further have by the inversion formula thatΦ( xΣ)= limT→∞12π∫ T−Te−itxite−Σ2t2/2 dt,so it thus follows that−2T( xΣ,σ2σ1)= limT→∞12π∫ T−Te−itxitie−Σ2t2/2 erfi(σ2t√2)dt.This proves the lemma for 0 < β < α.111For the other cases, from [12] we have that T(h,−a) = −T(h, a). Thus for β = 0, simplynote that T(x, 0) = 0 for all x ∈ R and erfi(0) = 0, so both sides of the equation are zero. For−α < β < 0, observe that erfi is an odd function and solimT→∞12π∫ T−Te−itxitie−α2t2/2 erfi( βt√2)dt = − limT→∞12π∫ T−Te−itxitie−α2t2/2 erfi(−βt√2)dt= 2T(xα,− β√α2 − β2)= −2T(xα,− β√α2 − β2).This completes the proof.The second inversion formula follows:Lemma D.4. Let α > 0 with β, γ such that β2 + γ2 = α2. Then12π∫ ∞−∞eixt−α2t2/2(erfi( βt√2)erfi( γt√2))dt=ϕ( xα )α(3− 2Φ( β√α2 − β2xα)− 2Φ( γ√α2 − γ2xα)).Proof. Let σ1, σ2 > 0, Σ =√σ21 + σ22 , and X,Y be independent random variables with respectivedistributions Φ+(xσ 1) and Φ+(xσ 2).112Thus we obtain that the probability distribution function of X + Y is for x ≥ 0,h(x) =ϕ+(xσ1)σ1∗ ϕ+(xσ2)σ2=∫ ∞−∞ϕ+(x−yσ1)ϕ+(yσ2)σ1σ2dy=∫ x04ϕ(x−yσ1 )ϕ(yσ2)σ1σ2dy= 4∫ x0exp(− 12σ21σ22(σ22(x− y)2 + σ1y2))2πσ1σ2dy= 4∫ x0exp(− 12σ21σ22(σ22x2 − 2σ22yx+Σ2y2))2πσ1σ2dy= 4∫ x0exp(− 12σ21σ22(Σ2(y − σ22Σ2x)2 + (σ21σ22Σ2 )x2))2πσ1σ2dy= 4e−x22Σ2√2πΣ∫ x0exp(− Σ22σ21σ22(y − σ22Σ2x)2)√2π σ1σ2Σdy= 4e−x22Σ2√2πΣ∫ ( Σσ1σ2− σ2σ1Σ )x− σ2σ1Σxe−u22√2πdy= 4ϕ( xΣ)(Φ(σ1σ2xΣ)− Φ(− σ2σ1xΣ)).For x < 0, it is obvious that h(x) = 0 as ϕ+(x) = 0 for all x < 0.Now, observe that by Lemma D.1φX+Y (t) = e−Σ2t2/2(1 + i erfi(σ1t√2)+ i erfi(σ2t√2)− erfi(σ1t√2)erfi(σ2t√2)).Thus we obtain thath(x) =12π∫ ∞−∞eixtφX+Y (t) dt=ϕ( xΣ )Σ+ϕ( xΣ )Σ(2Φ(σ1σ2xΣ)− 1) + ϕ(xΣ )Σ(2Φ(σ2σ1xΣ)− 1)− 12π∫ ∞−∞eixt−Σ2t2/2(erfi(σ1t√2)erfi(σ2t√2))dt.113Thus by combining the two equations for h(x), we obtain for x ≥ 0 that12π∫ ∞−∞eixt−Σ2t2/2(erfi(σ1t√2)erfi(σ2t√2))dt=ϕ( xΣ )Σ(1 + 2Φ(σ1σ2xΣ)− 1 + 2Φ(σ2σ1xΣ)− 1− 4Φ(σ1σ2xΣ) + 4Φ(−σ2σ1xΣ))=ϕ( xΣ )Σ(−2Φ(σ1σ2xΣ)− 2Φ(σ2σ1xΣ) + 3).Likewise, for x < 0, we obtain that12π∫ ∞−∞eixt−Σ2t2/2(erfi(σ1t√2)erfi(σ2t√2))dt=ϕ( xΣ )Σ(2Φ(σ1σ2xΣ) + 2Φ(σ2σ1xΣ)− 1)=ϕ( xΣ )Σ(−2Φ(−σ1σ2xΣ)− 2Φ(−σ2σ1xΣ) + 3).This completes the proof.Now, we characterize sums of three independent random variables where one is has a normaldistribution and the other two have truncated normal distributions.Lemma D.5. Suppose X,Y, Z are independent random variables where X with distribution func-tionsP (X ≤ x) = Φ(xσ1),P (Y ≤ x) = Φ+( xσ2),P (Z ≤ x) = Φ+( xσ3).Let Σ =√σ21 + σ22 + σ23. Then X + Y + Z and X − Y − Z have distributionsP (X + Y + Z ≤ x) = Φ( xΣ)− 2T( xΣ,σ2√σ21 + σ23)− 2T( xΣ,σ3√σ21 + σ22)+ S(x;σ1, σ2, σ3),P (X − Y − Z ≤ x) = Φ( xΣ)− 2T( xΣ,− σ2√σ21 + σ23)− 2T( xΣ,− σ3√σ21 + σ22)+ S(x;σ1, σ2, σ3).with characteristic functionsφX+Y+Z(t) = e−Σ2t22(1 + i erfi(σ2t√2)+ i erfi(σ3t√2)− erfi(σ2t√2)erfi(σ3t√2)),φX−Y−Z(t) = e−Σ2t22(1− i erfi(σ2t√2)− i erfi(σ3t√2)− erfi(σ2t√2)erfi(σ3t√2)).114Proof. We shall first observe that the respective probability density functions of X,Y, Z arefX(x) =e− x22σ21√2πσ1,fY (x) =√2e− x22σ22√πσ2if x ≥ 0,0 otherwise,fZ(x) =√2e− x22σ22√πσ2if x ≥ 0,0 otherwise.As X,Y, Z are independent, it follows thatφX+Y+Z(t) = φX(t)φY (t)φZ(t).As X is a normal variable with mean 0 and variance σ21 ,φX(t) = e−σ21t22 .For Y and Z, we apply Lemma D.1 to obtain thatφY (t) = e−σ22t22 (1 + i erfi(σ2t√2)),φZ(t) = e−σ23t22 (1 + i erfi(σ3t√2)).Thus with Σ as defined above, we obtain thatφX+Y+Z(t) = e−Σ2t22(1 + i erfi(σ2t√2)+ i erfi(σ3t√2)− erfi(σ2t√2)erfi(σ3t√2)).We can then use the inversion formula to write the distribution function H(x)−H(y) asH(x)−H(y) = limT→∞12π∫ T−Te−itx − e−ityitφX+Y+Z(t) dtThus by expanding φX+Y+Z(t), splitting the integral into four components, applying LemmaD.3 and recalling the definition of the S function, thatH(x)−H(y) = Φ( xΣ)− Φ( yΣ)− 2T( xΣ,σ2√σ21 + σ23)+ 2T( yΣ,σ2√σ21 + σ23)− 2T( xΣ,σ3√σ21 + σ22)+ 2T( yΣ,σ3√σ21 + σ22)+ S(x;σ1, σ2, σ3)− S(y;σ1, σ2, σ3).The same can be done for φX−Y−Z(t), completing the proof.115The following statement about multivariate normal distributions is well-known, but a shortproof is provided for the sake of completeness:Lemma D.6. Let X = (X1, . . . , XN ) be a random vector in RN with a multivariate normal distri-bution, mean 0⃗, and N ×N matrix of covariance Σ, and let e⃗1, . . . , e⃗N be the unit eigenvectors ofΣ with corresponding eigenvalues λ1, . . . , λN .It holds the N random variables of the form Yk = e⃗k ·X are independent normal distributions,with each Yk having mean 0 and variance λk.Proof. The proof in the case where N = 1 is trivial as Y1 = X, so the following will assume N > 1.Let ρ be an arbitrary permutation of 1, . . . , N , and letCρ =e⃗⊺ρ(1)...e⃗⊺ρ(N) ,interpreting e⃗1, . . . , e⃗N as column vectors.By [13, Theorem 3.3.3], it holds that the random vector Yρ = CρX is a multivariate normaldistribution with mean 0⃗ and matrix of covariance Dρ = CρΣC⊺ρ . As Σ is positive definite orpositive semidefinite [13, Definition 3.2.3], it thus follows by the orthogonality of the eigenvectorsthat Dρ is an N ×N diagonal matrix where (Dρ)k,k = λρ(k) for 1 ≤ k ≤ N . Observe that by thedefinition of Cρ and the N variables Yk, it holds that Yρ = (Yρ(1), . . . , Yρ(M)).By the partition of Dρ into four sub-matrices, the upper left M × M , and the lower rightN −M × N −M for some positive integer M < N , it follows by the fact that Dρ is diagonaland [13, Theorem 3.3.2] that (Yρ(1), . . . , Yρ(M)) is independent of (Yρ(M+1), . . . , Yρ(N)). Since thechoice of ρ and M is arbitrary, it is immediate that Y1, . . . , YN are a set of independent randomvariables.Finally, observe that e⃗k ·X = e⃗⊺kX, so by [13, Theorem 3.3.3] it holds Yk is a univariate normaldistribution with mean 0 and variance e⃗⊺kΣe⃗k = λk. This completes the proof.116
Thesis/Dissertation
eng
Mathematics
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Martin, Gregory George
The distribution of the invariant factors of multiplicative groups
Text