A Central Limit Theorem for Random Ordered Factorizations of Integers

Hsien-Kuei Hwang (Academia Sinica)
Svante Janson (Uppsala University)


Write an integer as finite products of ordered factors belonging to a given subset $\mathcal{P}$ of integers larger than one. A very general central limit theorem is derived for the number of ordered factors in random factorizations for any subset $\mathcal{P}$ containing at least two elements. The method of proof is very simple and relies in part on Delange’s Tauberian theorems and an interesting Tauberian technique for handling Dirichlet series associated with odd centered moments.

An erratum is available in EJP volume 18 paper 16

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 347-361

Publication Date: February 16, 2011

DOI: 10.1214/EJP.v16-858


  1. V. Baladi and B. Vallée, Euclidean algorithms are Gaussian, J. Number Theory 110 (2005), 331-386. Math. Review 2006e:11192
  2. D. W. Boyd and H. L. Montgomery, Cyclotomic partitions, in Number Theory (Banff, AB, 1988), 7-25, de Gruyter, Berlin, 1990. Math. Review 92b:11073
  3. H.-H. Chern and H.-K. Hwang, Phase changes in random m-ary search trees and generalized quicksort. Random Structures Algorithms 19 (2001), 316-358. Math. Review 2002k:68040
  4. H. Delange, Généralisation du théorème de Ikehara, Ann. Sci. Éc. Norm. Supér. 71 (1954), 213-242. Math. Review 16,921e
  5. H. Delange, Sur les moments des fonctions additives, Acta Arith. 49 (1988), 213-236. Math. Review 89h:11048
  6. M. Deléglise, M. O. Hernane and J.-L. Nicolas, Grandes valeurs et nombres champions de la fonction arithmétique de Kalmár, J. Number Theory 128 (2008), 1676-1716. Math. Review 2009d:11137
  7. P. Erdös, On some asymptotic formulas in the theory of the ``factorisatio numerorum," Ann. of Math 42 (1941) 989-993; Corrections, ibid. 44 (1943) 647-651. Math. Review 3,165b
  8. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), 216-240. Math. Review 90m:05012
  9. P. Flajolet and M. Soria, General combinatorial schemas: Gaussian limit distributions and exponential tails. Discrete Math. 114 (1993), 159-180. Math. Review 94e:05021
  10. P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, Cambridge, UK, 2009.
  11. P. Flajolet and B. Vallée, Continued fraction algorithms, functional operators, and structure constants, Theoret. Comput. Sci. 194 (1998), 1-34. Math. Review 98j:11061
  12. P. Flajolet and I. Vardi, Zeta function expansions of classical constants, unpublished manuscript; available at http://algo.inria.fr/flajolet/Publications/landau.ps
  13. E. Hille, A problem in ``factorisatio numerorum," Acta Arith. 2 (1936), 134-144.
  14. H.-K. Hwang, Théorèmes limites pour les structures combinatories et les fonctions arithmétiques, Ph. D. Thesis, École Polytechnique, 1994.
  15. H.-K. Hwang, Distribution of the number of factors in random ordered factorizations of integers, J. Number Theory 81 (2000), 61-92. Math. Review 2001k:11183
  16. L. Kalmár, A ``factorisatio numerorum" problémájáról, Mat. Fiz. Lapok 38 (1931) 1-15.
  17. A. Knopfmacher, J. Knopfmacher and R. Warlimont, Ordered factorizations for integers and arithmetical semigroups, in Advances in Number Theory (Kingston, ON, 1991), 151-165, Oxford Univ. Press, New York, 1993. Math. Review 97e:11118
  18. A. Knopfmacher and M. E. Mays, A survey of factorization counting functions, Int. J. Number Theory 1 (2005), 563-581. Math. Review 2006j:11047
  19. J. Korevaar, Tauberian Theory. A Century of Developments, Springer-Verlag, Berlin, 2004. Math. Review 2006e:11139
  20. Y.-K. Lau, Local distribution of ordered factorizations of integers, J. Number Theory 91 (2001), 312-317. Math. Review 2003e:11103
  21. P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Mess. Math. 20 (1891), 103-119.
  22. W. Narkiewicz, Number Theory, Translated from the Polish by S. Kanemitsu. World Scientific Publishing Co., Singapore; distributed by Heyden & Son, Inc., Philadelphia, PA, 1983. Math. Review 85j:11002
  23. L. A. Newberg and D. Naor, A lower bound on the number of solutions to the probed partial digest problem. Adv. in Appl. Math. 14 (1993), 172-183. Math. Review 1218242
  24. G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Second edition, Société Mathématique de France, Paris, 1995; English translation published by Cambridge University Press, 1995. Math. Review 97e:11005a
  25. B. Vallée, Dynamical analysis of a class of Euclidean algorithms, Theoret. Comput. Sci. 297 (2003), 447-486. Math. Review 2004e:11144
  26. H. S. Wilf, The Redheffer matrix of a partially ordered set, Electron. J. Combin. 11 (2004/06), Research Paper 10, 5 pp. Math. Review 2005i:05007

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.