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, Bi
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 p11, p × q5, p2 × q3 e p × q × r2, 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
do inteiro k, corresponde a uma classe de inteiros tendo exatamente k divisores, da forma
onde cada pi é 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 an, McMahon e Oppenheim observaram que sua função geradora de série de Dirichlet f(s) tem a representação do produto
A sequência de números an 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 an, da forma
mas como Canfield, Erdős & Pomerance (1983) mostraram, este limite é errôneo e o verdadeiro limite é
Ambos os limites não estão longe de ser lineares em n: eles são da forma n1−o(1). No entanto, o valor típico de an é muito menor: o valor médio de an, calculado em um intervalo x ≤ n ≤ x+N, é
um limite que tem a forma no(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 an de partições multiplicativas de algum n: o número de valores menores que N que surgem desta forma é NO(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 an: o número de valores n ≤ N tal que an divide n é O(N / log1 + 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». MathWorld (em inglês) (em inglês)