Na teoria dos números, um número n-suave (ou n-friável) é um inteiro cujos fatores primos são todos menores ou iguais a n. Por exemplo, um número 7-suave é um número no qual cada fator primo é no máximo 7. Portanto, 49 = 72 e 15750 = 2 × 32 × 53 × 7 são ambos 7-suaves, enquanto 11 e 702 = 2 × 33 × 13 não são 7-suaves. O termo parece ter sido cunhado por Leonard Adleman. Os números suaves são especialmente importantes na criptografia, que depende da fatoração de inteiros. Os números 2-suaves são simplesmente as potências de 2, enquanto os números 5-suaves também são conhecidos como números regulares.

Definição Um inteiro positivo é chamado de B-suave se nenhum dos seus fatores primos for maior que B. Por exemplo, 1.620 tem a fatoração prima 22 × 34 × 5; portanto, 1.620 é 5-suave porque nenhum dos seus fatores primos é maior que 5. Essa definição inclui números que não possuem alguns dos fatores primos menores; por exemplo, tanto 10 quanto 12 são 5-suaves, embora eles não possuam os fatores primos 3 e 5, respectivamente. Todos os números 5-suaves são da forma 2a × 3b × 5c, onde a, b e c são inteiros não negativos.

Os números 3-suaves também têm sido chamados de "números harmônicos", embora esse nome tenha outros significados mais amplamente usados, mais notavelmente para a soma dos recíprocos dos números naturais. Os números 5-suaves também são chamados de números regulares ou números de Hamming; os números 7-suaves também são chamados de números humildes, e às vezes chamados de altamente compostos, embora isso entre em conflito com outro significado de números altamente compostos.

Aqui, observe que o próprio B não é obrigado a aparecer entre os fatores de um número B-suave. Se o maior fator primo de um número for p, então o número é B-suave para qualquer B ≥ p. Em muitos cenários, B é primo, mas números compostos também são permitidos. Um número é B-suave se e somente se for p-suave, onde p é o maior primo menor ou igual a B.

Aplicações Uma aplicação prática importante de números suaves são os algoritmos da Transformada rápida de Fourier (FFT) (como o algoritmo FFT de Cooley-Tukey), que operam dividindo recursivamente um problema de um dado tamanho n em problemas do tamanho de seus fatores. Ao usar números B-suaves, garante-se que os casos base dessa recursão sejam primos pequenos, para os quais existem algoritmos eficientes. (Tamanhos primos grandes requerem algoritmos menos eficientes, como o algoritmo FFT de Bluestein.)

Os números 5-suaves ou números regulares desempenham um papel especial na Matemática babilônica.. Eles também são importantes na teoria musical (veja Limite (música)),. e o problema de gerar esses números de forma eficiente tem sido usado como um problema de teste para programação funcional..

Os números suaves têm uma série de aplicações em criptografia. Embora a maioria das aplicações se concentre na criptoanálise (por exemplo, os algoritmos de fatoração de inteiros mais rápidos conhecidos, como o crivo geral do corpo de números), a função hash VSH é outro exemplo de um uso construtivo da suavidade para obter um design comprovadamente seguro.

Na música, uma afinação do limite-p é o conjunto de intervalos musicais que são razões de dois números p-suaves.David Wright, Mathematics and Music. Mathematical World 28. (Providence, R.I.: American Mathematical Society, 2009), p. 137. .

Distribuição

Seja o número de inteiros y-suaves menores ou iguais a x (a função de de Bruijn).

Se o limite de suavidade B é fixo e pequeno, existe uma boa estimativa para :

onde denota a quantidade de números primos menores ou iguais a .

Caso contrário, defina o parâmetro u como u = log x / log y: isto é, x = yu. Então,

onde é a função de Dickman.

Para qualquer k, quase todos os números naturais não serão k-suaves.

Se onde é -suave e não é (ou é igual a 1), então é chamado de a parte -suave de . Sabe-se que o tamanho relativo da parte -suave de um número inteiro aleatório menor ou igual a decai muito mais lentamente do que .

Números de potência suave Além disso, m é chamado de n-potência suave (n-powersmooth no original em inglês, ou n-ultrafriável) se todas as potências de primos dividindo m satisfizerem:

Por exemplo, 720 (24 × 32 × 51) é 5-suave, mas não 5-potência suave (porque há várias potências primas maiores do que 5, por exemplo, e ). Ele é 16-potência suave, pois sua maior potência de fator primo é 24 = 16. O número também é 17-potência suave, 18-potência suave, etc.

Ao contrário dos números n-suaves, para qualquer número inteiro positivo n, há apenas uma quantidade finita de números n-potência suaves. De fato, os números n-potência suaves são exatamente os divisores positivos de “o mínimo múltiplo comum de 1, 2, 3, …, n” , por exemplo, os números 9-potência suaves (e também os 10-potência suaves) são exatamente os divisores positivos de 2520.

Números n-suaves e n-potência suaves têm aplicações na teoria dos números, como no algoritmo p − 1 de Pollard e no ECM. Freqüentemente, diz-se que tais aplicações trabalham com "números suaves", sem nenhum n especificado; isso significa que os números envolvidos devem ser n-potência suaves, para algum pequeno número não especificado n. À medida que n aumenta, o desempenho do algoritmo ou método em questão degrada-se rapidamente. Por exemplo, o algoritmo de Pohlig-Hellman para calcular logaritmos discretos tem um tempo de execução de O(n1/2) — para grupos de ordem n-suave.

Suave sobre um conjunto A Além disso, diz-se que m é suave sobre um conjunto A se houver uma fatoração de m em que os fatores sejam potências de elementos em A. Por exemplo, como 12 = 4 × 3, 12 é suave sobre os conjuntos A1 = {4, 3}, A2 = {2, 3}, e , contudo não seria suave sobre o conjunto A3 = {3, 5}, uma vez que 12 contém o fator 4 = 22, e nem 4 nem 2 estão em A3.

Observe que o conjunto A não precisa ser um conjunto de fatores primos, mas é tipicamente um subconjunto próprio dos números primos, como visto na base de fatores do método de fatoração de Dixon e no crivo quadrático. Da mesma forma, é isso que o crivo geral do corpo de números usa para construir sua noção de suavidade, sob o homomorfismo .

Ver também Número altamente composto Número áspero Número redondo Teorema de Størmer Número incomum

Notas e referências

Bibliografia G. Tenenbaum, Introduction to analytic and probabilistic number theory, (AMS, 2015) A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2008

Ligações externas

A Enciclopédia On-Line de Sequências Inteiras (OEIS) lista os números B-suaves para pequenos B''s: Números 2-suaves: A000079 (2i) Números 3-suaves: A003586 (2i3j) Números 5-suaves: A051037 (2i3j5k) Números 7-suaves: A002473 (2i3j5k7l) Números 11-suaves: A051038 (etc...) Números 13-suaves: A080197 Números 17-suaves: A080681 Números 19-suaves: A080682 Números 23-suaves: A080683

Categoria:Teoria analítica dos números Categoria:Sequências de números inteiros