On the Amount of Dependence in the Prime Factorization of a Uniform Random Integer

zbMATH Open1126.11331arXiv1305.0941MaRDI QIDQ4550232FDOQ4550232

Richard Arratia

Publication date: 21 August 2002

Abstract: How much dependence is there in the prime factorization of a random integer distributed uniformly from 1 to n? How much dependence is there in the decomposition into cycles of a random permutation of n points? What is the relation between the Poisson-Dirichlet process and the scale invariant Poisson process? These three questions have essentially the same answers, with respect to total variation distance, considering only small components, and with respect to a Wasserstein distance, considering all components. The Wasserstein distance is the expected number of changes -- insertions and deletions -- needed to change the dependent system into an independent system. In particular we show that for primes, roughly speaking, 2+o(1) changes are necessary and sufficient to convert a uniformly distributed random integer from 1 to n into a random integer prod_{p leq n} p^{Z_p} in which the multiplicity Z_p of the factor p is geometrically distributed, with all Z_p independent. The changes are, with probability tending to 1, one deletion, together with a random number of insertions, having expectation 1+o(1). The crucial tool for showing that 2+epsilon suffices is a coupling of the infinite independent model of prime multiplicities, with the scale invariant Poisson process on (0,infty). A corollary of this construction is the first metric bound on the distance to the Poisson-Dirichlet in Billingsley's 1972 weak convergence result. Our bound takes the form: there are couplings in which E sum |log P_i(n) - (log n) V_i | = O(log log n), where P_i denotes the i-th largest prime factor and V_i denotes the i-th component of the Poisson-Dirichlet process. It is reasonable to conjecture that O(1) is achievable.

Full work available at URL: https://arxiv.org/abs/1305.0941

Recommendations

• [[:Publication:4234468|Title not available (Why is that?)]]
• [[:Publication:3837815|Title not available (Why is that?)]]
• Joint Poisson distribution of prime factors in sets
• On the Asymptotic Distribution of Large Prime Factors
• [[:Publication:4410059|Title not available (Why is that?)]]

Mathematics Subject Classification ID

Distribution theory (60E99) Arithmetic functions in probabilistic number theory (11K65) Distribution of integers with specified multiplicative constraints (11N25)

Cited In (11)

• Size bias for one and all
• The magical Ewens sampling formula
• Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example
• Exploiting the Feller coupling for the Ewens sampling formula
• Dickman approximation in simulation, summations and perpetuities
• Central limit theorem for the least common multiple of a uniformly sampled \(m\)-tuple of integers
• On the dependence of the component counting process of a uniform random variable
• The Feller coupling for random derangements
• Parallel Weighted Random Sampling
• Random feedback shift registers and the limit distribution for largest cycle lengths
• Title not available (Why is that?)

This page was built for publication: On the Amount of Dependence in the Prime Factorization of a Uniform Random Integer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4550232)