Multiplicative partition

In number theory, a multiplicative partition or unordered factorization of an integer n that is greater than 1 is a way of writing n as a product of integers greater than 1, treating two products as equivalent if they differ only in the ordering of the factors. The number n is itself considered one of these products. Multiplicative partitions closely parallel the study of multipartite partitions, discussed in Andrews (1976), which are additive partitions of finite sequences of positive integers, with the addition made pointwise. Although the study of multiplicative partitions has been ongoing since at least 1923, the name "multiplicative partition" appears to have been introduced by Hughes & Shallit (1983). The Latin name "factorisatio numerorum" had been used previously. MathWorld uses the term unordered factorization.



Hughes & Shallit (1983) describe an application of multiplicative partitions in classifying integers with a given number of divisors. For example, the integers with exactly 12 divisors take the forms p11, p×q5, p2×q3, and p×q×r2, where p, q, and r are distinct prime numbers; these forms correspond to the multiplicative partitions 12, 2×6, 3×4, and 2×2×3 respectively. More generally, for each multiplicative partition

of the integer k, there corresponds a class of integers having exactly k divisors, of the form

where each pi is a distinct prime. This correspondence follows from the multiplicative property of the divisor function.

Bounds on the number of partitions

Oppenheim (1926) credits McMahon (1923) with the problem of counting the number of multiplicative partitions of n; this problem has since been studied by other others under the Latin name of factorisatio numerorum. If the number of multiplicative partitions of n is an, McMahon and Oppenheim observed that its Dirichlet series generating function ƒ(s) has the product representation

The sequence of numbers an begins

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, ... (sequence A001055 in the OEIS).

Oppenheim also claimed an upper bound on an, of the form

but as Canfield, Erdős & Pomerance (1983) showed, this bound is erroneous and the true bound is

Both of these bounds are not far from linear in n: they are of the form n1o(1). However, the typical value of an is much smaller: the average value of an, averaged over an interval x  n  x+N, is

a bound that is of the form no(1) (Luca, Mukhopadhyay & Srinivas 2008).

Additional results

Canfield, Erdős & Pomerance (1983) observe, and Luca, Mukhopadhyay & Srinivas (2008) prove, that most numbers cannot arise as the number an of multiplicative partitions of some n: the number of values less than N which arise in this way is NO(log log log N / log log N). Additionally, Luca, Mukhopadhyay & Srinivas (2008) show that most values of n are not multiples of an: the number of values nN such that an divides n is O(N / log1 + o(1) N).

See also


Further reading

External links

This article is issued from Wikipedia - version of the 7/29/2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.