Mathematics > Number Theory
[Submitted on 4 May 2013]
Title:On the Amount of Dependence in the Prime Factorization of a Uniform Random Integer
View PDFAbstract: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.
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.