From Wikipedia, the free encyclopedia
In number theory, a multiplicative partition or unordered factorization of an integer n {\displaystyle n} is a way of writing n {\displaystyle 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 {\displaystyle n} 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.
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 11 {\displaystyle p^{11}} , p ⋅ q 5 {\displaystyle p\cdot q^{5}} , p 2 ⋅ q 3 {\displaystyle p^{2}\cdot q^{3}} , and p ⋅ q ⋅ r 2 {\displaystyle p\cdot q\cdot r^{2}} , where p {\displaystyle p} , q {\displaystyle q} , and r {\displaystyle r} are distinct prime numbers; these forms correspond to the multiplicative partitions 12 {\displaystyle 12} , 2 ⋅ 6 {\displaystyle 2\cdot 6} , 3 ⋅ 4 {\displaystyle 3\cdot 4} , and 2 ⋅ 2 ⋅ 3 {\displaystyle 2\cdot 2\cdot 3} respectively. More generally, for each multiplicative partition k = ∏ t i {\displaystyle k=\prod t_{i}} of the integer k {\displaystyle k} , there corresponds a class of integers having exactly k {\displaystyle k} divisors, of the form
where each p i {\displaystyle p_{i}} 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 n {\displaystyle n} ;[3][4] this problem has since been studied by others under the Latin name of factorisatio numerorum. If the number of multiplicative partitions of n {\displaystyle n} is a n {\displaystyle a_{n}} , McMahon and Oppenheim observed that its Dirichlet series generating function f ( s ) {\displaystyle f(s)} has the product representation[3][4] f ( s ) = ∑ n = 1 ∞ a n n s = ∏ k = 2 ∞ 1 1 − k − s . {\displaystyle 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 {\displaystyle a_{n}} 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
A001055in the
OEIS).
Oppenheim also claimed an upper bound on a n {\displaystyle a_{n}} , of the form[3] a n ≤ n ( exp log n log log log n log log n ) − 2 + o ( 1 ) , {\displaystyle a_{n}\leq 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[5] a n ≤ n ( exp log n log log log n log log n ) − 1 + o ( 1 ) . {\displaystyle a_{n}\leq n\left(\exp {\frac {\log n\log \log \log n}{\log \log n}}\right)^{-1+o(1)}.}
Both of these bounds are not far from linear in n {\displaystyle n} : they are of the form n 1 − o ( 1 ) {\displaystyle n^{1-o(1)}} . However, the typical value of a n {\displaystyle a_{n}} is much smaller: the average value of a n {\displaystyle a_{n}} , averaged over an interval x ≤ n ≤ x + N {\displaystyle x\leq n\leq x+N} , is a ¯ = exp ( 4 log N 2 e log log N ( 1 + o ( 1 ) ) ) , {\displaystyle {\bar {a}}=\exp \left({\frac {4{\sqrt {\log N}}}{{\sqrt {2e}}\log \log N}}{\bigl (}1+o(1){\bigr )}\right),} a bound that is of the form n o ( 1 ) {\displaystyle n^{o(1)}} .[6]
Additional results[edit]Canfield, Erdős & Pomerance (1983) observe, and Luca, Mukhopadhyay & Srinivas (2010) prove, that most numbers cannot arise as the number a n {\displaystyle a_{n}} of multiplicative partitions of some n {\displaystyle n} : the number of values less than N {\displaystyle N} which arise in this way is N O ( log log log N / log log N ) {\displaystyle N^{O(\log \log \log N/\log \log N)}} .[5][6] Additionally, Luca et al. show that most values of n {\displaystyle n} are not multiples of a n {\displaystyle a_{n}} : the number of values n ≤ N {\displaystyle n\leq N} such that a n {\displaystyle a_{n}} divides n {\displaystyle n} is O ( N / log 1 + o ( 1 ) N ) {\displaystyle O(N/\log ^{1+o(1)}N)} .[6]
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4