Función de partición (teoría de números)

En teoría de números , la función de partición p ( n ) representa el número de particiones posibles de un entero no negativo n . Por ejemplo, p (4) = 5 porque el entero 4 tiene las cinco particiones 1 + 1 + 1 + 1 , 1 + 1 + 2 , 1 + 3 , 2 + 2 , y 4 .

No se conoce una expresión analítica para la función de partición, pero posee expansiones asintóticas que la aproximan con precisión y relaciones de recurrencia que permiten su cálculo exacto. Crece exponencialmente con la raíz cuadrada de su argumento. La inversa multiplicativa de su función generadora es la función de Euler ; según el teorema de los números pentagonales de Euler , esta función es una suma alternada de potencias de números pentagonales de su argumento.

Srinivasa Ramanujan descubrió que la función de partición presenta patrones no triviales en la aritmética modular , conocidos actualmente como congruencias de Ramanujan . Por ejemplo, siempre que la representación decimal de n termine en el dígito 4 o 9, el número de particiones de n será divisible por 5.

Para un entero positivo n , p ( n ) es el número de formas distintas de representar n como una suma de enteros positivos. Para los fines de esta definición, el orden de los términos en la suma es irrelevante: dos sumas con los mismos términos en un orden diferente (por ejemplo, 1 + 1 + 2 y 1 + 2 + 1 ) no se consideran distintas. ^{[ a ]}

Por convención, p (0) = 1 , ya que hay una forma de representar 0 como una suma de enteros positivos (la suma vacía ). Además, p ( n ) = 0 cuando n es negativo.

Los primeros valores de la función de partición, comenzando con p (0) = 1 , son

Algunos valores exactos de p ( n ) para valores mayores de n incluyen ^{[ 1 ]}$${\displaystyle {\begin{aligned}p(100)&=190,\!569,\!292\\p(1000)&=24,\!061,\!467,\!864,\!032,\!622,\!473,\!692,\!149,\!727,\!991\approx 2.40615\times 10^{31}\\p(10000)&=36,\!167,\!251,\!325,\!\dots ,\!906,\!916,\!435,\!144\approx 3.61673\times 10^{106}\end{aligned}}}$$

La función generadora para p ( n ) viene dada por ^{[ 2 ]}$${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)x^{n}&=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right)\\&=\left(1+x+x^{2}+\cdots \right)\left(1+x^{2}+x^{4}+\cdots \right)\left(1+x^{3}+x^{6}+\cdots \right)\cdots \\&={\frac {1}{1-xx^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}-\cdots }}\\&=1{\Big /}\sum _{k=-\infty }^{\infty }(-1)^{k}x^{k(3k-1)/2}.\end{aligned}}}$$La igualdad entre los productos de la primera y la segunda línea de esta fórmula se obtiene al expandir cada factor.${\displaystyle 1/(1-x^{k})}$en la serie geométrica${\displaystyle (1+x^{k}+x^{2k}+x^{3k}+\cdots ).}$Para comprobar que el producto expandido es igual a la suma de la primera línea, aplicamos la propiedad distributiva al producto. Esto expande el producto en una suma de monomios de la forma${\displaystyle x^{a_{1}}x^{2a_{2}}x^{3a_{3}}\cdots }$para alguna secuencia de coeficientes${\displaystyle a_{i}}$, de los cuales solo un número finito puede ser distinto de cero. El exponente del término es${\textstyle n=\sum ia_{i}}$y esta suma puede interpretarse como una representación de${\displaystyle n}$como una partición en${\displaystyle a_{i}}$copias de cada número${\displaystyle i}$. Por lo tanto, el número de términos del producto que tienen exponente${\displaystyle n}$es exactamente${\displaystyle p(n)}$, lo mismo que el coeficiente de${\displaystyle x^{n}}$en la suma de la izquierda. Por lo tanto, la suma es igual al producto.

La función que aparece en el denominador en la tercera y cuarta línea de la fórmula es la función de Euler . La igualdad entre el producto de la primera línea y las fórmulas de la tercera y cuarta línea es el teorema del pentágono de Euler . Los exponentes de${\displaystyle x}$En estas líneas están los números pentagonales${\displaystyle P_{k}=k(3k-1)/2}$para${\displaystyle k\in \{0,1,-1,2,-2,\dots \}}$(generalizado un poco a partir de los números pentagonales habituales, que provienen de la misma fórmula para los valores positivos de${\displaystyle k}$). El patrón de signos positivos y negativos en la tercera línea proviene del término${\displaystyle (-1)^{k}}$en la cuarta línea: incluso elecciones de${\displaystyle k}$producen términos positivos, y las elecciones extrañas producen términos negativos.

De manera más general, la función generadora para las particiones de${\displaystyle n}$en números seleccionados de un conjunto${\displaystyle A}$de enteros positivos se pueden encontrar tomando solo aquellos términos en el primer producto para el cual${\displaystyle k\in A}$. Este resultado se debe a Leonhard Euler . ^{[ 3 ]} La formulación de la función generadora de Euler es un caso especial de una${\displaystyle q}$-El símbolo de Pochhammer es similar a la formulación de productos de muchas formas modulares , y específicamente a la función eta de Dedekind .

La misma secuencia de números pentagonales aparece en una relación de recurrencia para la función de partición: ^{[ 4 ]}$${\displaystyle {\begin{aligned}p(n)&=\sum _{k\in \mathbb {Z} \setminus \{0\}}(-1)^{k+1}p(n-k(3k-1)/2)\\&=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-p(n-22)-\cdots \end{aligned}}}$$ Como casos base,${\displaystyle p(0)}$se toma igual${\displaystyle 1}$, y${\displaystyle p(k)}$se toma como cero para valores negativos ${\displaystyle k}$Aunque la suma del lado derecho parece infinita, solo tiene un número finito de términos distintos de cero, provenientes de los valores distintos de cero de${\displaystyle k}$en el rango $${\displaystyle -{\frac {{\sqrt {24n+1}}-1}{6}}\leq k\leq {\frac {{\sqrt {24n+1}}+1}{6}}.}$$ La relación de recurrencia también puede escribirse en la forma equivalente. $${\displaystyle p(n)=\sum _{k=1}^{\infty }(-1)^{k+1}{\big (}p(n-k(3k-1)/2)+p(n-k(3k+1)/2){\big )}.}$$

Otra relación de recurrencia para${\displaystyle p(n)}$puede expresarse en términos de la función suma de divisores σ : ^{[ 5 ]}$${\displaystyle p(n)={\frac {1}{n}}\sum _{k=0}^{n-1}\sigma (n-k)p(k).}$$ Si${\displaystyle q(n)}$denota el número de particiones de${\displaystyle n}$sin partes repetidas, entonces se sigue dividiendo cada partición en sus partes pares e impares, y dividiendo las partes pares por dos, que ^{[ 6 ]}$${\displaystyle p(n)=\sum _{k=0}^{\left\lfloor n/2\right\rfloor }q(n-2k)p(k).}$$

A Srinivasa Ramanujan se le atribuye el descubrimiento de que la función de partición tiene patrones no triviales en la aritmética modular . Por ejemplo, el número de particiones es divisible por cinco siempre que la representación decimal de${\displaystyle n}$termina en el dígito 4 o 9, como lo expresa la congruencia ^{[ 7 ].}$${\displaystyle p(5k+4)\equiv 0{\pmod {5}}}$$ Por ejemplo, el número de particiones para el entero 4 es 5. Para el entero 9, el número de particiones es 30; para el 14 hay 135 particiones. Esta congruencia está implícita en la identidad más general. $${\displaystyle \sum _{k=0}^{\infty }p(5k+4)x^{k}=5~{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}},}$$ también por Ramanujan, ^{[ 8 ] [ 9 ]} donde la notación${\displaystyle (x)_{\infty }}$denota el producto definido por $${\displaystyle (x)_{\infty }=\prod _{m=1}^{\infty }(1-x^{m}).}$$Una breve demostración de este resultado se puede obtener a partir de la función generadora de la función de partición.

Ramanujan también descubrió congruencias módulo 7 y 11: ^{[ 7 ]}$${\displaystyle {\begin{aligned}p(7k+5)&\equiv 0{\pmod {7}},\\p(11k+6)&\equiv 0{\pmod {11}}.\end{aligned}}}$$ La primera proviene de la identidad de Ramanujan ^{[ 9 ]}$${\displaystyle \sum _{k=0}^{\infty }p(7k+5)x^{k}=7~{\frac {(x^{7})_{\infty }^{3}}{(x)_{\infty }^{4}}}+49x~{\frac {(x^{7})_{\infty }^{7}}{(x)_{\infty }^{8}}}.}$$

Dado que 5, 7 y 11 son primos consecutivos , uno podría pensar que habría una congruencia análoga para el siguiente primo 13,${\displaystyle p(13k+a)\equiv 0{\pmod {13}}}$para algunos a . Sin embargo, no hay congruencia de la forma${\displaystyle p(bk+a)\equiv 0{\pmod {b}}}$para cualquier primo b distinto de 5, 7 u 11. ^{[ 10 ]} En cambio, para obtener una congruencia, el argumento de${\displaystyle p}$debería tomar la forma${\displaystyle cbk+a}$para algunos${\displaystyle c>1}$En la década de 1960, AOL Atkin, de la Universidad de Illinois en Chicago, descubrió congruencias adicionales de esta forma para módulos primos pequeños. Por ejemplo: $${\displaystyle p(11^{3}\cdot 13\cdot k+237)\equiv 0{\pmod {13}}.}$$

Ken Ono ( 2000 ) demostró que existen tales congruencias para cada módulo primo mayor que 3. Posteriormente, Ahlgren y Ono (2001) demostraron que existen congruencias de partición módulo cada entero coprimo con 6. ^{[ 11 ] [ 12 ]} 

La conjetura de Newman es un problema sin resolver sobre las congruencias de la función de partición, formulada por el matemático Morris Newman en 1960. ^{[ 13 ]} La conjetura postula que, dados cualesquiera enteros r , m donde${\displaystyle 0\leq r\leq m-1}$, existen infinitos enteros no negativos n para los cuales${\displaystyle p(n)\equiv r{\pmod {m}}}$.

Existen fórmulas de aproximación que se calculan más rápidamente que la fórmula exacta indicada anteriormente.

Una expresión asintótica para p ( n ) viene dada por

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$como${\displaystyle n\to \infty }$.

Esta fórmula asintótica fue obtenida por primera vez por GH Hardy y Ramanujan en 1918 e independientemente por JV Uspensky en 1920. Considerando${\displaystyle p(1000)}$La fórmula asintótica proporciona aproximadamente${\displaystyle 2.4402\times 10^{31}}$, razonablemente cerca de la respuesta exacta dada anteriormente (1,415% mayor que el valor real).

Hardy y Ramanujan obtuvieron una expansión asintótica con esta aproximación como primer término: ^{[ 14 ]}$${\displaystyle p(n)\sim {\frac {1}{2\pi {\sqrt {2}}}}\sum _{k=1}^{v}A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\exp \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right),}$$ dónde $${\displaystyle A_{k}(n)=\sum _{0\leq h<k,\;(h,k)=1}e^{\pi i\left(s(h,k)-2nh/k\right)}.}$$ Aquí, la notación${\displaystyle (h,k)=1}$significa que la suma se toma solo sobre los valores de${\displaystyle h}$que son relativamente primordiales para${\displaystyle k}$. La función${\displaystyle s(h,k)}$es una suma de Dedekind .

El error después${\displaystyle v}$los términos son del orden del siguiente término, y${\displaystyle v}$puede considerarse del orden de${\displaystyle {\sqrt {n}}}$. Como ejemplo, Hardy y Ramanujan demostraron que${\displaystyle p(200)}$es el entero más cercano a la suma de los primeros${\displaystyle v=5}$términos de la serie. ^{[ 14 ]}

En 1937, Hans Rademacher pudo mejorar los resultados de Hardy y Ramanujan al proporcionar una expresión de serie convergente para${\displaystyle p(n)}$Es ^{[ 15 ] [ 16 ]}$${\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\sinh \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right).}$$

La demostración de la fórmula de Rademacher involucra círculos de Ford , secuencias de Farey , simetría modular y la función eta de Dedekind .

Se puede demostrar que el${\displaystyle k}$El término de la serie de Rademacher es del orden $${\displaystyle \exp \left({\frac {\pi }{k}}{\sqrt {\frac {2n}{3}}}\right),}$$ de modo que el primer término da la aproximación asintótica de Hardy-Ramanujan. Paul Erdős ( 1942 ) publicó una demostración elemental de la fórmula asintótica para ${\displaystyle p(n)}$. ^{[ 17 ] [ 18 ]}

Johansson (2012) analiza técnicas para implementar la fórmula de Hardy-Ramanujan-Rademacher de manera eficiente en una computadora , y demuestra que${\displaystyle p(n)}$se puede calcular en tiempo${\displaystyle O(n^{1/2+\varepsilon })}$para cualquier${\displaystyle \varepsilon >0}$. Esto es casi óptimo ya que coincide con el número de dígitos del resultado. ^{[ 19 ]} El valor más grande de la función de partición calculado exactamente es${\displaystyle p(10^{20})}$, que tiene algo más de 11 mil millones de dígitos. ^{[ 20 ]}

En términos más generales, es posible considerar particiones restringidas únicamente a elementos de un subconjunto A de los números naturales (por ejemplo, una restricción sobre el valor máximo de las partes), o con una restricción sobre el número de partes o la diferencia máxima entre ellas. Cada restricción particular da lugar a una función de partición asociada con propiedades específicas. A continuación se presentan algunos ejemplos comunes.

• Primeros 4096 valores de la función de partición