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.^[1][2] Por exemplo, um número 7-suave é um número no qual cada fator primo é no máximo 7. Portanto, 49 = 7² e 15750 = 2 × 3² × 5³ × 7 são ambos 7-suaves, enquanto 11 e 702 = 2 × 3³ × 13 não são 7-suaves. O termo parece ter sido cunhado por Leonard Adleman.^[3] 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 2² × 3⁴ × 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 2^a × 3^b × 5^c, 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",^[4] 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;^[5] os números 7-suaves também são chamados de números humildes,^[6] e às vezes chamados de altamente compostos,^[7] 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.^[8] Eles também são importantes na teoria musical (veja Limite (música)),^[9] e o problema de gerar esses números de forma eficiente tem sido usado como um problema de teste para programação funcional.^[10]

Os números suaves têm uma série de aplicações em criptografia.^[11] 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.^[12]

Distribuição

Seja ${\displaystyle \Psi (x,y)}$ 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 ${\displaystyle \Psi (x,B)}$:

${\displaystyle \Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}.}$

onde ${\displaystyle \pi (B)}$ denota a quantidade de números primos menores ou iguais a ${\displaystyle B}$.

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

${\displaystyle \Psi (x,y)=x\cdot \rho (u)+O\left({\frac {x}{\log y}}\right)}$

onde ${\displaystyle \rho (u)}$ é a função de Dickman.

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

Se ${\displaystyle n=n_{1}n_{2}}$ onde ${\displaystyle n_{1}}$ é ${\displaystyle B}$-suave e ${\displaystyle n_{2}}$ não é (ou é igual a 1), então ${\displaystyle n_{1}}$ é chamado de a parte ${\displaystyle B}$-suave de ${\displaystyle n}$. Sabe-se que o tamanho relativo da parte ${\displaystyle x^{1/u}}$-suave de um número inteiro aleatório menor ou igual a ${\displaystyle x}$ decai muito mais lentamente do que ${\displaystyle \rho (u)}$.^[13]

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 ${\displaystyle p^{\nu }}$ dividindo m satisfizerem:

${\displaystyle p^{\nu }\leq n.\,}$

Por exemplo, 720 (2⁴ × 3² × 5¹) é 5-suave, mas não 5-potência suave (porque há várias potências primas maiores do que 5, por exemplo, ${\displaystyle 3^{2}=9\nleq 5}$ e ${\displaystyle 2^{4}=16\nleq 5}$). Ele é 16-potência suave, pois sua maior potência de fator primo é 2⁴ = 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” (sequência A003418 na OEIS), 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(n^1/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 A₁ = {4, 3}, A₂ = {2, 3}, e ${\displaystyle \mathbb {Z} }$, contudo não seria suave sobre o conjunto A₃ = {3, 5}, uma vez que 12 contém o fator 4 = 2², e nem 4 nem 2 estão em A₃.

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 ${\displaystyle \varphi$ :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} } .^[14]

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) ISBN 978-0821898543
• A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2008

Ligações externas

• Weisstein, Eric W. «Smooth Number». MathWorld (em inglês) 

A Enciclopédia On-Line de Sequências Inteiras (OEIS) lista os números B-suaves para pequenos Bs:

• Números 2-suaves: A000079 (2ⁱ)
• Números 3-suaves: A003586 (2ⁱ3^j)
• Números 5-suaves: A051037 (2ⁱ3^j5^k)
• Números 7-suaves: A002473 (2ⁱ3^j5^k7^l)
• 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