Multiplicative partition: Difference between revisions

Revision as of 01:18, 10 February 2008

Latest revision as of 15:17, 3 March 2024

(48 intermediate revisions by 27 users not shown)

Line 1:

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 termsfactors. The number ''<math>n''</math> is itself considered one of these products. Multiplicative partitions closely parallel the study of '''multipartite partitions''', which{{r|a}} 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&nbsp;&times;&nbsp;2&nbsp;&times;&nbsp;5, 2&nbsp;&times;&nbsp;10, 4&nbsp;&times;&nbsp;5, and 20.

*3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;3, 3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;9, 3&nbsp;&times;&nbsp;27, 9&nbsp;&times;&nbsp;9, and 81 are the five multiplicative permutationspartitions of 81 = 3⁴. 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&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;5 = 2&nbsp;&times;&nbsp;15 = 6&nbsp;&times;&nbsp;5 = 3&nbsp;&times;&nbsp;10 = 30.
*In general, the number of multiplicaticemultiplicative 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''&times;''q''<supmath>p\cdot q^5</supmath>, ''p''<supmath>p^2</sup>&times;''\cdot q''<sup>^3</supmath>, and ''<math>p''&times;''\cdot q''&times;''\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&times;\cdot 6</math>, <math>3&times;\cdot 4</math>, and <math>2&times;\cdot 2&times;\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>na_n</submath>, McMahon and Oppenheim observed that its [[Dirichlet series]] generating function &fnof;<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

:1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, ... {{OEIS|id=A001055}}.

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

:{{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}}.}}

:<math>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

Oppenheim also claimed an upper bound on ''a<submath>na_n</submath>'', of the form{{r|o}}

:<math>a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-1+o(1)}.</math>

:<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 <math>n^{1-o(1)}</math>.

However, the typical value of <math>a_n</math> is much smaller: the average value of <math>a_n</math>, averaged over an interval <math>x\le n\le x+N</math>, is

<math display=block>\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 <math>n^{o(1)}</math>.{{r|lms}}

==Additional results==

{{harvtxt|Canfield|Erdős|Pomerance|1983}} observe, and {{harvtxt|Luca|Mukhopadhyay|Srinivas|2010}} prove, that most numbers cannot arise as the number <math>a_n</math> of multiplicative partitions of some <math>n</math>: the number of values less than <math>N</math> which arise in this way is <math>N^{O(\log\log\log N/\log\log N)}</math>.{{r|cep|lms}} Additionally, Luca et al. show that most values of <math>n</math> are not multiples of <math>a_n</math>: the number of values <math>n\le N</math> such that <math>a_n</math> divides <math>n</math> is <math>O(N/\log^{1+o(1)} N)</math>.{{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|firstfirst1=P.John AF.|lastlast1=MacMahonHughes|authorlinkfirst2=PercyJeffrey|last2=Shallit|authorlink2=Jeffrey Alexander MacMahonShallit|title=Dirichlet series andOn the theorynumber of multiplicative partitions|journal=[[Proceedings of the LondonAmerican Mathematical SocietyMonthly]]|year=1983|volume=2290|yearissue=19237|pages=404–411468–471|urldoi=http://plms10.oxfordjournals.org2307/cgi/reprint/s2-22/1/4042975729|jstor=2975729}}.</ref>

<ref name=lms>{{citation

*{{citation|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|url=http://jlms.oxfordjournals.org/cgi/reprint/s1-1/4/205}}.

| 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=MacMahon|authorlink=Percy Alexander MacMahon|title=Dirichlet series and the theory of partitions|journal=[[London Mathematical Society#Publications|Proceedings of the London Mathematical Society]]|volume=22|year=1923|pages=404–411}}</ref>

* "The Theory of Partitions" Chapter 12, George E. Andrews (Encyclopedia of Mathematics and its Applications, vol 2 1976 Addison -Wesley)

*<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|url=http://jlms.oxfordjournals.org/cgi/reprint/s1-1/4/205}}.</ref>

}}

==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}}

==External links==

*{{MathWorld|title=Unordered Factorization|urlname=UnorderedFactorization|mode=cs2}}

{{numtheory-stub}}

[[Category:Number theory]]

[[Category:Integer sequences]]