domingo, 17 de abril de 2011

Una suma finita para calcular la función de partición



¿Una teoría que revela la naturaleza de los números?

  “Nueva teoría revela la naturaleza de los números,” 
 nos deja con la miel en los labios.  

Menos mal que Sarah C. Kavassalis, “Finite formula found for partition numbers,” The Language of Bad Physics, 20 Jan. 2011, nos aclara un poco el asunto. 

¿Qué es lo que ha hecho Ken Ono?

Muy fácil, se ha encontrado una expresión matemática con un número finito de términos para la función de partición. 

Una suma con un número finito de términos, en lugar de una serie con un número infinito de términos, como la famosa fórmula de Rademacher. 

¿Es esto un avance importante en teoría de números? 

Sí, porque la función de partición aparece en muchos problemas tanto
 de matemáticas puras como aplicadas; la nueva fórmula promete muchas aplicaciones en física estadística, mecánica cuántica, e incluso teoría de cuerdas. 


La función de partición p(n) cuenta el número de maneras de descomponer
 el número n como suma de enteros positivos (menores que n, claro) 
teniendo en cuenta que dos sumas que solo difieren en el orden
 de los sumandos se cuentan una sola vez. 

Pongamos un par de ejemplos.

 El número 4 se puede escribir de 5 formas, en concreto,
 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1, es decir, p(4)=5.

 El número 6 se puede escribir de 11 formas, en concreto, 
6 = 5 + 1 = 4 + 2 = 4 + 1 + 1 = 3 + 3 = 3 + 2 + 1 = 3 + 1 + 1 + 1 = 2 + 2 + 2 = 2 + 2 + 1 + 1 = 2 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 +1.

 Los primeros ocho valores de la función de partición aparecen en la figura
de arriba, llamada diagramas de partición de Ferrer. 

La función de partición crece bastante rápido como muestran sus primeros valores: p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11, p(7)=15, p(8)=22, p(9)=30, p(10)=42, p(11)=56, p(12)=77, p(13)=101, p(14)=135, p(15)=176, …, p(100)=190569292, …, p(1000) = 24061467864032622473692149727991, …

En el siglo XVII, Leonhard Euler obtuvo la función generatriz de la función p(n), dada por

\sum_{n=0}^\infty p(n)\,q^n = \prod_{n=1}^\infty \frac{\displaystyle 1}{\displaystyle 1 - q^n}.

 Esta fórmula permite obtener un algoritmo recursivo para calcular p(n).

 Pero “el método es lento y poco práctico para números grandes. 

En los siguientes 150 años, el método sólo se implementó con éxito
 para calcular las primeras 200 particiones de números.“

En 1918, Srinivasa Ramanujan y G.H. Hardy inventaron el “método del círculo” que permite obtener una aproximación asintótica a la función de partición. 

Ken Ono ha escrito sobre la historia de este descubrimiento 
en su recomendable artículo “The Last Words of a Genius.”

 El trabajo parte de un descubrimiento de Ramanujan,
 como muchos otros junto a Hardy. 

Para ciertos valores de n la función de partición se puede evaluar utilizando aritmética modular. 

Por ejemplo, p(5 m + 4) = 0 (mod 5), es decir, el resto de dividir p(5m+4) entre 5 es 0; de hecho  p(4)=5, p(9)=30, p(14)=135, … 

Igualmente, p(7 m + 5) = 0 (mod 7), de hecho, p(5)=7, p(12)=77, etc., 
y p(11 m + 6) = 0 (mod 11), de hecho p(6)=11, p(17)=297, etc. 

Estas fórmulas se pueden generalizar a potencias de 5, 7 y 11, así como a ciertos otros números. 

El trabajo conjunto de Ramanujan y Hardy permitió obtener la aproximación asintótica para la función de partición dada por

p(n) \sim \frac{\displaystyle \exp(\pi\sqrt{2 n/3})}{\displaystyle 4 n \sqrt{3}}, \qquad n\rightarrow\infty.

En 1937, Hans Rademacher encontró una fórmula exacta para la función
 de partición basada en una serie infinita pero convergente;
 hay varias formas de escribir esta fórmula, yo copio aquí ésta

p(n)=\frac{\displaystyle 1}{\displaystyle \pi \sqrt{2}}\sum_{q\ge 1}\sqrt{q}A_q(n)\frac{\displaystyle d}{\displaystyle dn} \frac{\displaystyle sinh(K_q\lambda_n)}{\displaystyle \lambda_n},
K_q=\frac{\displaystyle \pi}{\displaystyle q}\sqrt{\frac{2}{3}},            \lambda_n=\sqrt{n-\frac{1}{24}},          A_q(n)=\sum_{p ~\rm{mod}(q)}\omega_{pq}\exp(-2i\pi n\frac{p}{q}).

Como esta serie es convergente, para evaluarla numéricamente basta truncarla con un número suficiente de términos como para garantizar que
 su valor redondeado al entero más próximo no cambia debido al resto 
de los términos.

 De hecho, hay cotas al error que se comete que ayudan a utilizar
 esta fórmula en la práctica. 

Aún así, lidiar con una serie infinita en múltiples aplicaciones
 tiene ciertos inconvenientes.

¿Qué es lo que han logrado Ken Ono y sus colegas?

 En 2007 obtuvieron una fórmula para calcular p(n) que tiene solo 
un número finito de términos. 

En concreto la fórmula es

p(n) = \frac{\displaystyle 1}{\displaystyle 24 n -1}\sum_{Q\in\cal{Q}_n} P(\alpha_Q),

donde P(z) es una forma débil de Maass; por lo que parece demuestran
 en el nuevo artículo de 2011 que su expresión también se puede evaluar 
con un número finito de sumandos, pero mis parcos conocimientos
 en estos tópicos no me permitirán entender con detalle por qué es así. 

De hecho, la representación de esta función que presentan los autores 
en el artículo de 2007 es en forma de serie infinita, pero cuando la evalúan
 en un ejemplo concreto resulta que la convierten mágicamente 
en una expresión con un número finito de sumandos. 

En el nuevo trabajo, parece ser, han logrado demostrar que eso siempre
 es posible utilizando una expresión matemática recurrente que los autores afirman que tiene una forma “fractal” (funciones l-ádicas fractales,
 les llaman).

Espero haber aclarado un poco el asunto. 

 Los interesados en más detalles podrán ver la demostración de la nueva fórmula obtenida en 2007 por Jan Hendrik Bruinier y Ken Ono en ”An algebraic formula for the partition function,” y un trabajo posterior sobre las congruencias de Ramanujan y su relación con la nueva fórmula “fractal” en Amanda Folsom, Zachary A. Kent y Ken Ono, 
“l-adic properties of the partition function.” 

Publicado por en

No hay comentarios:

Publicar un comentario