Multiplikativ partition

I talteorin är en multiplikativ partition eller oordnad faktorisering av ett heltal n ett sätt att skriva n som en produkt av heltal större än 1, och behandla två produkter som ekvivalenta om de bara skiljer sig i ordningen av faktorerna. Siffran n anses själv vara en av dessa produkter. Multiplikativa partitioner parallellt nära studien av multipartite partitioner , diskuterad i Andrews (1976) , som är additiva partitioner av finita sekvenser av positiva heltal, med tillägget gjort punktvis . Även om studiet av multiplikativa partitioner har pågått sedan åtminstone 1923, verkar namnet "multiplikativ partition" ha introducerats av Hughes & Shallit (1983) . Det latinska namnet "factorisatio numerorum" hade använts tidigare. MathWorld använder termen oordnad faktorisering .

Exempel

Talet 20 har fyra multiplikativa partitioner: 2 × 2 × 5, 2 × 10, 4 × 5 och 20.
3 × 3 × 3 × 3, 3 × 3 × 9, 3 × 27, 9 × 9 och 81 är de fem multiplikativa partitionerna 81 = 3 ⁴ . Eftersom det är fjärde potensen av ett primtal har 81 samma antal (fem) multiplikativa partitioner som 4 har additiva partitioner .
Talet 30 har fem multiplikativa partitioner: 2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30.
I allmänhet är antalet multiplikativa partitioner av ett kvadratfritt tal med i- primfaktorer det ith Bell-talet , B _i .

Ansökan

Hughes & Shallit (1983) beskriver en tillämpning av multiplikativa partitioner för att klassificera heltal med ett givet antal divisorer. Till exempel tar heltalen med exakt 12 divisorer formerna p ¹¹ , p × q ⁵ , p ² × q ³ , och p × q × r ² , där p , q och r är distinkta primtal ; dessa former motsvarar de multiplikativa partitionerna 12, 2×6, 3×4 respektive 2×2×3. Mer generellt, för varje multiplikativ partition

k=\prod t_{i}

av heltal k , motsvarar en klass av heltal som har exakt k divisorer, av formen

\prod p_{i}^{t_{i}-1},

där varje p _i är ett distinkt primtal. Denna överensstämmelse följer av den multiplikativa egenskapen för divisorfunktionen .

Gränser för antalet partitioner

Oppenheim (1926) krediterar McMahon (1923) med problemet att räkna antalet multiplikativa partitioner av n ; detta problem har sedan dess studerats av andra under det latinska namnet factorisatio numerorum . Om antalet multiplikativa partitioner av n är ett _n , observerade McMahon och Oppenheim att dess Dirichlet-seriegenererande funktion f ( s ) har produktrepresentationen

f(s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}=\prod _{k=2}^{\ infty }{\frac {1}{1-k^{-s}}}.

Talföljden a _n börjar

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, ... (sekvens A001055 i OEIS ) .

Oppenheim hävdade också en övre gräns på ett _n , av formen

a_{n}\leq n\left(\exp {\frac { \log n\log \log \log n}{\log \log n}}\right)^{-2+o(1)},

men som Canfield, Erdős & Pomerance (1983) visade, är denna gräns felaktig och den sanna gränsen är

a_{n}\leq n\left(\exp {\frac {\log n\log \log \log n}{\log \log n}}\right)^{-1+o(1) }.

Båda dessa gränser är inte långt ifrån linjära i n : de har formen n ^1−o(1) . Det typiska värdet för a _n är dock mycket mindre: medelvärdet för a _n , medelvärde över ett intervall x ≤ n ≤ x + N , är

{\bar {a}}=\exp \left({\frac {4{\ sqrt {\log N}}}{{\sqrt {2e}}\log \log N}}{\bigl (}1+o(1){\bigr )}\right),

en bunden som är av formen n ^o(1) ( Luca, Mukhopadhyay & Srinivas 2008) .

Ytterligare resultat

Canfield, Erdős & Pomerance (1983) observerar, och Luca, Mukhopadhyay & Srinivas (2008) bevisar att de flesta tal inte kan uppstå som antalet a _n av multiplikativa partitioner av något n : antalet värden mindre än N som uppstår på detta sätt är N ^{O(logglogg log N / log log N )} . Dessutom Luca, Mukhopadhyay & Srinivas (2008) att de flesta värden på n inte är multiplar av ett _n : antalet värden n ≤ N så att a _n delar n är O( N / log ^{1 + o(1)} N ) .

Se även

Andrews, G. (1976), The Theory of Partitions , Addison-Wesley , kapitel 12.
Canfield, ER; Erdős, Paul ; Pomerance, Carl (1983), "On a problem of Oppenheim angående "factorisatio numerorum" ", Journal of Number Theory , 17 (1): 1–28, doi : 10.1016/0022-314X(83)90002-1 .
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 .
Knopfmacher, A.; Mays, M. (2006), "Ordered and Unordered Factorizations of Integers", Mathematica Journal , 10 : 72–89 . Som citeras av MathWorld .
Luca, Florian; Mukhopadhyay, Anirban; Srinivas, Kotyada (2008), Om Oppenheims "factorisatio numerorum"-funktion , arXiv : 0807.0986 , Bibcode : 2008arXiv0807.0986L .
MacMahon, PA (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 .
Oppenheim, A. (1926), "On an aritmetic function" , Journal of the London Mathematical Society , 1 (4): 205–211, doi : 10.1112/jlms/s1-1.4.205 , arkiverad från originalet 2013- 04-15 .

Vidare läsning

Knopfmacher, A.; Mays, ME (2005), "A survey of factorization counting functions" (PDF) , International Journal of Number Theory , 1 (4): 563–581, doi : 10.1142/S1793042105000315

externa länkar

Weisstein, Eric W. "Oordnad faktorisering" . MathWorld .