|
In [[number theory]], a '''multiplicative partition''' or '''unordered factorization''' of an integer ''<math>n'' that is greater than 1</math> is a way of writing ''<math>n''</math> 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 ''<math>n''</math> is itself considered one of these products. Multiplicative partitions closely parallel the study of '''multipartite partitions''', discussed in {{harvtxtr|Andrews|1976a}}, which are additive [[partitionPartition (number theory)|partitions]]s 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 {{harvtxt|Hughes|Shallit|1983}}.{{r|hs}} The Latin name "factorisatio numerorum" had been used previously. [[MathWorld]] uses the nameterm '''unordered factorization'''.
==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 permutationspartitions of 81 = 3<sup>4</sup>. Because 81it is the fourth power of a [[prime number|prime]], 81 has the same number (five) of multiplicative partitions as the4 number four hasdoes of (additive) [[partition (number theory)|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 [[Square-free integer|squarefree]] number with '''<math>i''' distinct</math> prime factors is the ith<math>i</math>th [[Bell number]] , B<submath>iB_i</submath>.
==Application==
{{harvtxt|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''<supmath>p^{11}</supmath>, ''p''×''q''<supmath>p\cdot q^5</supmath>, ''p''<supmath>p^2</sup>×''\cdot q''<sup>^3</supmath>, and ''<math>p''×''\cdot q''×''\cdot r''<sup>^2</supmath>, where ''<math>p''</math>, ''<math>q''</math>, and ''<math>r''</math> are distinct [[prime number]]s; these forms correspond to the multiplicative partitions <math>12</math>, <math>2×\cdot 6</math>, <math>3×\cdot 4</math>, and <math>2×\cdot 2×\cdot 3</math> respectively. More generally, for each multiplicative partition
:<math display=block>k = \prod t_i</math>
of the integer ''<math>k''</math>, there corresponds a class of integers having exactly ''<math>k''</math> divisors, of the form
:<math>\prod p_i^{t_i-1},</math>
where each ''p''<submath>''i''p_i</submath> is a distinct prime. This correspondence follows from the [[Multiplicative function|multiplicative]] property of the [[divisor function]].{{r|hs}}
==Bounds on the number of partitions==
{{harvtxt|Oppenheim|1926}} credits {{harvtxt|McMahonMacMahon|1923}} with the problem of counting the number of multiplicative partitions of ''<math>n''</math>;{{r|o|m}} this problem has since been studied by other others under the Latin name of ''factorisatio numerorum''. If the number of multiplicative partitions of ''<math>n''</math> is ''a''<submath>''n''a_n</submath>, McMahon and Oppenheim observed that its [[Dirichlet series]] generating function ƒ<math>f(''s'')</math> has the product representation{{r|o|m}}
:<math display=block>f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}=\prod_{k=2}^{\infty}\frac{1}{1-k^{-s}}.</math> ▼
The sequence of numbers ''a< submath> na_n</ submath> '' begins ▼▲:<math>f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}=\prod_{k=2}^{\infty}\frac{1}{1-k^{-s}}.</math>
:{{bi|left=1.6| 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, ... {{OEIS|id=A001055}}. }}▼▲The sequence of numbers ''a<sub>n</sub>'' begins
Oppenheim also claimed an upper bound on ''a< submath> na_n</ submath> '', of the form {{r|o}}▼▲:1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, ... {{OEIS|id=A001055}}.
:<math display=block>a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-2+o(1)},</math> ▼but as {{harvtxt|Canfield|Erdős|Pomerance|1983}} showed, this bound is erroneous and the true bound is {{r|cep}}▼:<math display=block>a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-1+o(1)}.</math> ▼
Both of these bounds are not far from linear in ''<math>n ''</math>: they are of the form ''n''< supmath> n^{1 −-o(1) }</ supmath>. ▼▲Oppenheim also claimed an upper bound on ''a<sub>n</sub>'', of the form
However, the typical value of ''a< submath> na_n</ submath> '' is much smaller: the average value of ''a< submath> na_n</ submath> '', averaged over an interval ''<math>x '' ≤ ''\le n '' ≤ ''\le x ''+ ''N ''</math>, is ▼▲:<math>a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-2+o(1)},</math>
:<math display=block>\bar a = \exp\left(\frac{4\sqrt{\log N}}{\sqrt{2e}\log\log N}\bigl(1+o(1)\bigr)\right),</math> ▼▲but as {{harvtxt|Canfield|Erdős|Pomerance|1983}} showed, this bound is erroneous and the true bound is
a bound that is of the form ''n''< supmath> n^{o(1) }</ supmath> .{{ harvr| Luca|Mukhopadhyay|Srinivas|2008lms}} .▼
▲:<math>a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-1+o(1)}.</math>
▲Both of these bounds are not far from linear in ''n'': they are of the form ''n''<sup>1−o(1)</sup>.
▲However, the typical value of ''a<sub>n</sub>'' is much smaller: the average value of ''a<sub>n</sub>'', averaged over an interval ''x'' ≤ ''n'' ≤ ''x''+''N'', is
▲:<math>\bar a = \exp\left(\frac{4\sqrt{\log N}}{\sqrt{2e}\log\log N}\bigl(1+o(1)\bigr)\right),</math>
▲a bound that is of the form ''n''<sup>o(1)</sup> {{harv|Luca|Mukhopadhyay|Srinivas|2008}}.
==Additional results==
{{harvtxt|Canfield|Erdős|Pomerance|1983}} observe, and {{harvtxt|Luca|Mukhopadhyay|Srinivas|20082010}} prove, that most numbers cannot arise as the number ''a<submath>na_n</submath>'' of multiplicative partitions of some ''<math>n''</math>: the number of values less than ''<math>N''</math> which arise in this way is ''N''<supmath>N^{O(\log \log \log '' N'' / \log \log '' N'')}</supmath>. Additionally, {{harvtxtr|Lucacep|Mukhopadhyay|Srinivas|2008lms}} Additionally, Luca et al. show that most values of ''<math>n''</math> are not multiples of ''a<submath>na_n</submath>'': the number of values ''<math>n'' ≤\le ''N''</math> such that ''a<submath>na_n</submath>'' divides ''<math>n''</math> is <math>O(''N'' / \log<sup>^{1 + o(1)} N)</supmath> ''N'').{{r|lms}}
==See also==
*[[partitionPartition (number theory)]]
*[[divisorDivisor]]
==References==
{{reflist|refs=
*<ref name=a>{{citation|first=G.|last=Andrews|authorlink=George E. Andrews|title=The Theory of Partitions|year=1976|publisher=Addison-Wesley}}, chapter 12 .</ref>▼*{{citation|first1=E. R.|last1=Canfield|first2=Paul|last2=Erdős|authorlink2=Paul Erdős|first3=Carl|last3=Pomerance|authorlink3=Carl Pomerance|title=On a problem of Oppenheim concerning "factorisatio numerorum"|journal=[[Journal of Number Theory]]|volume=17|year=1983|issue=1|pages=1–28}}.
*<ref name=cep>{{citation|doi=10.1016/0022-314X(83)90002-1|first1=JohnE. FR.|last1=HughesCanfield|first2=JeffreyPaul|last2=ShallitErdős|authorlink2=JeffreyPaul ShallitErdős|first3=Carl|last3=Pomerance|authorlink3=Carl Pomerance|title=On thea numberproblem of multiplicativeOppenheim partitionsconcerning 'factorisatio numerorum'|journal=[[AmericanJournal of MathematicalNumber MonthlyTheory]]|volume=17|year=1983|volume=90|issue=71|pages=468–4711–28|doi-access=10.2307/2975729free}}.</ref>
*<ref name=hs>{{citation|first1=FlorianJohn F.|last1=LucaHughes|first2=AnirbanJeffrey|last2=MukhopadhyayShallit|first3authorlink2=Kotyada|last3=SrinivasJeffrey Shallit|title=On the Oppenheim'snumber "factorisatioof numerorum"multiplicative functionpartitions|idjournal={{arxiv[[American Mathematical Monthly]]|idyear=08071983|volume=90|issue=7|pages=468–471|doi=10.0986}}2307/2975729|yearjstor=20082975729}}.</ref>
<ref name=lms>{{citation
*{{citation|first=P. A.|last=MacMahon|authorlink=Percy Alexander MacMahon|title=Dirichlet series and the theory of partitions|journal=[[Proceedings of the London Mathematical Society]]|volume=22|year=1923|pages=404–411|url=http://plms.oxfordjournals.org/cgi/reprint/s2-22/1/404}}.
| last1 = Luca | first1 = Florian
| last2 = Mukhopadhyay | first2 = Anirban
| last3 = Srinivas | first3 = Kotyada
| doi = 10.4064/aa142-1-3
| issue = 1
| journal = [[Acta Arithmetica]]
| mr = 2601047
| pages = 41–50
| title = Some results on Oppenheim's 'factorisatio numerorum' function
| volume = 142
| year = 2010| doi-access = free
| bibcode = 2010AcAri.142...41L
}}</ref>
*<ref name=m>{{citation|doi=10.1112/plms/s2-22.1.404|first=P. A.|last=OppenheimMacMahon|authorlink=Percy Alexander MacMahon|title=OnDirichlet anseries arithmeticand functionthe theory of partitions|journal=[[JournalLondon Mathematical Society#Publications|Proceedings of the London Mathematical Society]]|volume=122|issueyear=41923|pages=205–211|year=1926|url=http://jlms.oxfordjournals.org/cgi/reprint/s1-1/4/205404–411}}.</ref>
<ref name=o>{{citation|doi=10.1112/jlms/s1-1.4.205|first=A.|last=Oppenheim|title=On an arithmetic function|journal=[[Journal of the London Mathematical Society]]|volume=1|issue=4|pages=205–211|year=1926}}</ref>
▲*{{citation|first=G.|last=Andrews|authorlink=George E. Andrews|title=The Theory of Partitions|year=1976|publisher=Addison-Wesley}}, chapter 12.
}}
==Further reading==
*{{citation |first1=A. |last1=Knopfmacher |first2=M. E. |last2=Mays |year=2005 |title=A survey of factorization counting functions |journal=International Journal of Number Theory |volume=1 |issue=4 |doi=10.1142/S1793042105000315 |pages=563–581 |url=http://math.wvu.edu/~mays/Papers/apf7.pdf}}
*{{citation|first1=A.|last1=Knopfmacher|first2=M.|last2=Mays|title=Ordered and Unordered Factorizations of Integers|journal=[[Mathematica Journal]] 10, 72-89, 2006}}
==External links==
*{{MathWorld|title=Unordered Factorization|urlname=UnorderedFactorization|mode=cs2}}
{{numtheory-stub}}
[[Category:Number theory]]
[[Category:Integer sequences]]
| 