Esto se puede responder en una oración (“Usan caracteres, funciones complejas, análisis de Fourier y otros trucos ingeniosos”) o en un libro (por ejemplo, “Introducción a la teoría analítica de números” de Apostol). Trataré de decir algo útil de longitud intermedia.
También quiero elegir dos palabras en su pregunta:
- “… cómo descubren …”: el proceso de descubrir una tasa de crecimiento conjeturada para una función dada (aritmética, combinatoria u otra) es muy diferente del proceso de probar que dicha función realmente crece a la tasa anunciada. El descubrimiento se basa en datos numéricos, argumentos heurísticos (“un número menor que n es primo con probabilidad 1 / log (n)”), analogías, conjeturas astutas y ilusiones. Leí su pregunta, “cómo encuentran esas tasas asintóticas”, como preguntar acerca de la prueba real, que es lo que generalmente toma más tiempo y grava el mayor ingenio. Si realmente solo quiere saber cómo adivinan inicialmente esas tasas, hágamelo saber, esa es una pregunta muy diferente.
- “… funciones realmente feas “: no con las que estoy familiarizado. ¿Cuáles tienes en mente y qué tiene de feo?
Supongo que el primer ejemplo (tipo de juego de palabras intencionado) de una derivación tan asintótica es el Teorema del número primo que dice aproximadamente que hay n / log (n) primos hasta n. Tanto el descubrimiento de esta tasa de crecimiento como su prueba están bien documentados en Wikipedia (“Teorema de números primos”), y parece que has leído este, así que no sé si puedo agregar mucho aquí. Si el artículo de Wikipedia aún lo deja preguntándose, intente preguntar algo más específico.
Otra cosa que podríamos hacer es mirar un ejemplo relativamente elemental. Esto es bueno ya que podemos describir la prueba completa, y es malo ya que crea una falsa impresión de que estas derivaciones asintóticas se pueden hacer con manipulaciones elementales y un poco de paciencia. La mayoría de ellos no pueden.
- ¿Cuál de estos problemas matemáticos abiertos es más probable que se resuelva en los próximos 5 años: 1. Hipótesis de Riemann, 2. Conjetura de Goldbach, 3. Problema P Vs NP, 4. Conjetura de doble primo, 5. Problema de factorización prima, y por qué?
- Teoría de números: ¿encontrar los últimos tres dígitos de 2003 ^ 2002 ^ 2001?
- ¿Qué cambiaría todo en matemáticas si [matemáticas] [a + b] ^ 2 [/ matemáticas] se definiera como [matemáticas] a ^ 2 + b ^ 2 [/ matemáticas]?
- ¿Cómo multiplicar dos números que tienen un sistema base distinto de 10 sin convertirlos al sistema decimal?
- ¿Por qué se puede descomponer cada número positivo en un producto de primos?
Tomemos [math] \ tau (n) [/ math], el número de divisores de [math] n [/ math]. Formalmente esto es
[matemáticas] \ tau (n) = \ sum_ {d | n} 1 [/ matemáticas]
Una observación clave si esta función es multiplicativa (en el sentido aritmético): cuando [math] m, n [/ math] son relativamente primos, tenemos [math] \ tau (mn) = \ tau (m) \ tau ( n) [/ matemáticas]. Usando eso, puede concluir rápidamente que [matemáticas] \ tau (n) [/ matemáticas] crece más lentamente que cualquier poder positivo de [matemáticas] n [/ matemáticas]: es menor que (algún múltiplo constante de) [matemáticas] \ sqrt {n} [/ math], menor que (algún múltiplo constante de) [math] n ^ {1/100} [/ math], etc. (esto es “rápido” pero no del todo “trivial”; si usted ‘ Me pregunto cómo se hace esto, puedo elaborar).
Lo siguiente que normalmente quiere saber es el orden promedio de [math] \ tau [/ math], es decir, qué es
[matemáticas] \ sum_ {n \ leq x} \ tau (n) [/ matemáticas]?
Al conectar la definición de [math] \ tau [/ math] en esto obtenemos
[matemáticas] \ sum_ {n \ leq x} \ tau (n) = \ sum_ {d \ leq x} [x / d] [/ matemáticas]
donde [math] [z] [/ math] denota la parte entera de [math] z [/ math]. Ahora, sabemos que la suma de la serie armónica crece logarítmicamente:
[matemáticas] \ sum_ {d \ leq x} \ frac {1} {d} = \ log (x) + O (1) [/ matemáticas].
Esto da
[matemáticas] \ sum_ {n \ leq x} \ tau (n) = x \ log (x) + O (x) [/ matemáticas]
lo cual es un buen primer paso para comprender la tasa de crecimiento de la función de divisor promedio.
Una vez más, esto es algo engañoso: para muchas funciones aritméticas es realmente difícil hacer incluso ese primer paso, y ciertamente obtener mejores estimaciones es a menudo más difícil. No sé si puedo resumir esto útilmente sin escribir muchas más matemáticas en el editor de Quora de las que soy físicamente capaz.