Partição multiplicativa

Na teoria dos números, uma partição multiplicativa ou fatoração não ordenada de um inteiro n é uma maneira de escrever n como um produto de inteiros maiores que 1, tratando dois produtos como equivalentes se eles diferirem apenas na ordem dos fatores. O próprio número n é considerado um desses produtos. As partições multiplicativas são paralelas ao estudo das partições multipartidas, discutido em Andrews (1976), que são partições aditivas de sequências finitas de inteiros positivos, com a adição feita pontualmente. Embora o estudo das partições multiplicativas esteja em andamento desde pelo menos 1923, o nome "partição multiplicativa" parece ter sido introduzido por Hughes & Shallit (1983). O nome latino "factorisatio numerorum" foi usado anteriormente. O MathWorld usa o termo fatoração não ordenada.

Exemplos

• O número 20 tem quatro partições multiplicativas: 2 × 2 × 5, 2 × 10, 4 × 5 e 20.
• 3 × 3 × 3 × 3, 3 × 3 × 9, 3 × 27, 9 × 9 e 81 são as cinco partições multiplicativas de 81 = 34. Por ser a quarta potência de um primo, 81 tem o mesmo número (cinco) de partições multiplicativas como 4 faz de partições aditivas.
• O número 30 tem cinco partições multiplicativas: 2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30.
• Em geral, o número de partições multiplicativas de um número inteiro sem fator quadrático com i fatores primos é o i-ésimo número de Bell, B_i

Aplicação

Hughes & Shallit (1983) descrevem uma aplicação de partições multiplicativas na classificação de inteiros com um determinado número de divisores. Por exemplo, os inteiros com exatamente 12 divisores assumem as formas p¹¹, p × q⁵, p² × q³ e p × q × r², onde p, q e r são números primos distintos; essas formas correspondem às partições multiplicativas 12, 2 × 6, 3 × 4 e 2 × 2 × 3, respectivamente. Mais geralmente, para cada partição multiplicativa

$k=\prod t_{i}$

do inteiro k, corresponde a uma classe de inteiros tendo exatamente k divisores, da forma

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

onde cada p_i é um primo distinto. Essa correspondência decorre da propriedade multiplicativa da função de divisor.

Limites no número de partições

Oppenheim (1926) credita a McMahon (1923) o problema de contar o número de partições multiplicativas de n; este problema foi estudado por outros sob o nome latino de factorisatio numerorum. Se o número de partições multiplicativas de n for a_n, McMahon e Oppenheim observaram que sua função geradora de série de Dirichlet f(s) tem a representação do produto

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

A sequência de números a_n começa

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, ... (sequência A001055 na OEIS).

Oppenheim também reivindicou um limite superior em a_n, da forma

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

mas como Canfield, Erdős & Pomerance (1983) mostraram, este limite é errôneo e o verdadeiro limite é

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

Ambos os limites não estão longe de ser lineares em n: eles são da forma n^1−o(1). No entanto, o valor típico de a_n é muito menor: o valor médio de a_n, calculado em um intervalo x ≤ n ≤ x+N, é

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

um limite que tem a forma n^o(1) ((Luca, Mukhopadhyay & Srinivas 2008)).

Resultados adicionais

Canfield, Erdős & Pomerance (1983) observam, e Luca, Mukhopadhyay & Srinivas (2008) provam, que a maioria dos números não pode surgir como o número a_n de partições multiplicativas de algum n: o número de valores menores que N que surgem desta forma é N^{O(log log log N / log log N)}. Além disso, Luca, Mukhopadhyay & Srinivas (2008) mostram que a maioria dos valores de n não são múltiplos de a_n: o número de valores n ≤ N tal que a_n divide n é O(N / log^{1 + o(1)} N).

Ver também

• Divisor
• Partição (teoria dos números)

Referências

• Andrews, G. (1976), A teoria das partições (em inglês), Addison-Wesley , capítulo 12.
• Canfield, E. R.; Erdős, Paul; Pomerance, Carl (1983), «Em um problema de Oppenheim relativo a "factorisatio numerorum"», Jornal da teoria dos números (em inglês), 17 (1): 1 à 28, doi:10.1016/0022-314X(83)90002-1 .
• Hughes, John F.; Shallit, Jeffrey (1983), «Sobre o número de partições multiplicativas», American Mathematical Monthly (em inglês), 90 (7): 468 à 471, JSTOR 2975729, doi:10.2307/2975729 .
• Knopfmacher, A.; Mays, M. (2006), «Fatoração ordenada e não ordenada de inteiros», Jornal Mathematica (em inglês), 10: 72 à 89 . Citado por MathWorld.
• Luca, Florian; Mukhopadhyay, Anirban; Srinivas, Kotyada (2008), Na função "factorisatio numerorum" de Oppenheim (em inglês), Bibcode:2008arXiv0807.0986L, arXiv:0807.0986 .
• MacMahon, P. A. (1923), «Série de Dirichlet e a teoria das partições», Procedimentos da sociedade matemática de Londres (em inglês), 22: 404 à 411, doi:10.1112/plms/s2-22.1.404 .
• Oppenheim, A. (1926), «Em uma função aritmética», Jornal da sociedade matemática de Londres (em inglês), 1 (4): 205 à 211, doi:10.1112/jlms/s1-1.4.205, cópia arquivada em 15 de abril de 2013 .

Leitura adicional

• Knopfmacher, A.; Mays, M. E. (2005), «Um levantamento das funções de contagem de fatoração» (PDF), Jornal internacional de teoria dos números (em inglês), 1 (4): 563 à 581, doi:10.1142/S1793042105000315 

Ligações externas

• Weisstein, Eric W. «Fatoração não ordenada» (em inglês). MathWorld  (em inglês)