Multiplicative partition

From Wikipedia, the free encyclopedia

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 name unordered factorization.

1 Examples
2 Application
3 Bounds on the number of partitions
4 See also
5 References
6 External links

[edit] Examples

The number 20 has four multiplicative partitions: 2 × 2 × 5, 2 × 10, 4 × 5, and 20.
3 × 3 × 3 × 3, 3 × 3 × 9, 3 × 27, 9 × 9, and 81 are the five multiplicative permutations of 81 = 3⁴. Because 81 is the fourth power of a prime, 81 has the same number (five) of multiplicative partitions as the number four has of (additive) partitions.
The number 30 has five multiplicative partitions: 2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30. In general, the number of multiplicatice partitions of a number with i distinct prime factors is the ith Bell number , B_i.

[edit] Application

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 p¹¹, p×q⁵, p²×q³, and p×q×r², 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

$k = \prod t_i$

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

$\prod p_i^{t_i-1},$

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

[edit] 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 a_n, McMahon and Oppenheim observed that its generating function ƒ(s) has the product representation

$f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}=\prod_{k=2}^{\infty}\frac{1}{1-k^{-s}}.$

The sequence of numbers a_n begins

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

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

$a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-2+o(1)},$

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

$a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-1+o(1)}.$

[edit] See also

[edit] References

Canfield, E. R.; Erdős, Paul & Pomerance, Carl (1983), “On a problem of Oppenheim concerning "factorisatio numerorum"”, Journal of Number Theory 17 (1): 1–28 .