Multiplicative partition

(Redirected from Unordered factorization)

In number theory, a multiplicative partition or unordered factorization of an integer is a way of writing 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 is itself considered one of these products. Multiplicative partitions closely parallel the study of multipartite partitions,[1] 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).[2] The Latin name "factorisatio numerorum" had been used previously. MathWorld uses the term unordered factorization.

Examples

edit
  • 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 partitions of 81 = 34. Because it is the fourth power of a prime, 81 has the same number (five) of multiplicative partitions as 4 does 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 multiplicative partitions of a squarefree number with   prime factors is the  th Bell number,  .

Application

edit

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  ,  ,  , and  , where  ,  , and   are distinct prime numbers; these forms correspond to the multiplicative partitions  ,  ,  , and   respectively. More generally, for each multiplicative partition   of the integer  , there corresponds a class of integers having exactly   divisors, of the form

 

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

Bounds on the number of partitions

edit

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

The sequence of numbers   begins

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

Oppenheim also claimed an upper bound on  , of the form[3]   but as Canfield, Erdős & Pomerance (1983) showed, this bound is erroneous and the true bound is[5]  

Both of these bounds are not far from linear in  : they are of the form  . However, the typical value of   is much smaller: the average value of  , averaged over an interval  , is   a bound that is of the form  .[6]

Additional results

edit

Canfield, Erdős & Pomerance (1983) observe, and Luca, Mukhopadhyay & Srinivas (2010) prove, that most numbers cannot arise as the number   of multiplicative partitions of some  : the number of values less than   which arise in this way is  .[5][6] Additionally, Luca et al. show that most values of   are not multiples of  : the number of values   such that   divides   is  .[6]

See also

edit

References

edit
  1. ^ Andrews, G. (1976), The Theory of Partitions, Addison-Wesley, chapter 12
  2. ^ a b Hughes, John F.; Shallit, Jeffrey (1983), "On the number of multiplicative partitions", American Mathematical Monthly, 90 (7): 468–471, doi:10.2307/2975729, JSTOR 2975729
  3. ^ a b c Oppenheim, A. (1926), "On an arithmetic function", Journal of the London Mathematical Society, 1 (4): 205–211, doi:10.1112/jlms/s1-1.4.205
  4. ^ a b MacMahon, P. A. (1923), "Dirichlet series and the theory of partitions", Proceedings of the London Mathematical Society, 22: 404–411, doi:10.1112/plms/s2-22.1.404
  5. ^ a b 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, doi:10.1016/0022-314X(83)90002-1
  6. ^ a b c Luca, Florian; Mukhopadhyay, Anirban; Srinivas, Kotyada (2010), "Some results on Oppenheim's 'factorisatio numerorum' function", Acta Arithmetica, 142 (1): 41–50, Bibcode:2010AcAri.142...41L, doi:10.4064/aa142-1-3, MR 2601047

Further reading

edit
edit