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

k = ∏ t i {\displaystyle k=\prod t_{i}}

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

∏ p i t i − 1 , {\displaystyle \prod p_{i}^{t_{i}-1},}

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

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

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

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)},}

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

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)}.}

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, é

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),}

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.0986Acessível livremente .
  • 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