En teoría de números , la función de partición p ( n ) representa el número de posibles particiones de un entero n no negativo . Por ejemplo, p (4) = 5 porque el número entero 4 tiene las cinco particiones 1 + 1 + 1 + 1 , 1 + 1 + 2 , 1 + 3 , 2 + 2 y 4 .
No se conoce ninguna expresión de forma cerrada para la función de partición, pero tiene expansiones asintóticas que la aproximan con precisión y relaciones de recurrencia mediante las cuales se puede calcular con exactitud. Crece como una función exponencial de la raíz cuadrada de su argumento. El inverso multiplicativo de su función generadora es la función de Euler ; según el teorema del número pentagonal de Euler, esta función es una suma alterna de las potencias del número pentagonal de su argumento.
Srinivasa Ramanujan descubrió por primera vez que la función de partición tiene patrones no triviales en aritmética modular , ahora conocidos 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.
Definición y ejemplos
Para un número entero positivo n , p ( n ) es el número de formas distintas de representar n como una suma de números enteros positivos. A los efectos 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 no se consideran distintas.
Por convención p (0) = 1 , ya que hay una forma (la suma vacía ) de representar cero como una suma de enteros positivos. Por la misma razón, por definición, p ( n ) = 0 cuando n es negativo.
Los primeros valores de la función de partición, comenzando con p (0) = 1 , son:
- 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604,… (secuencia A000041 en la OEIS ).
Algunos valores exactos de p ( n ) para valores más grandes de n incluyen: [1]
A febrero de 2020[actualizar], el mayor número primo conocido entre los valores de p ( n ) es p (1289844341) , con 40.000 dígitos decimales. [2]
Función generadora
La función generadora de p ( n ) viene dada por [3]
La igualdad entre los productos de la primera y segunda línea de esta fórmula se obtiene expandiendo cada factor en la serie geométrica Para ver que el producto expandido es igual a la suma de la primera línea, aplique la ley distributiva al producto. Esto expande el producto en una suma de monomios de la forma para alguna secuencia de coeficientes , solo un número finito de los cuales puede ser distinto de cero. El exponente del término es, y esta suma se puede interpretar como una representación de como una partición en copias de cada número . Por lo tanto, el número de términos del producto que tienen exponente es exactamente , lo mismo que el coeficiente de en la suma de la izquierda. Por tanto, la suma es igual al producto.
La función que aparece en el denominador en la tercera y cuarta líneas 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íneas es el teorema del número pentagonal de Euler . Los exponentes deen estas líneas están los números pentagonales por (generalizado algo de los números pentagonales habituales, que provienen de la misma fórmula para los valores positivos de ). El patrón de signos positivos y negativos en la tercera línea proviene del término en la cuarta línea: incluso opciones de producen términos positivos y las elecciones extrañas producen términos negativos.
De manera más general, la función generadora de las particiones de en números seleccionados de un conjunto de enteros positivos se puede encontrar tomando solo aquellos términos en el primer producto para el cual . Este resultado se debe a Leonhard Euler . [4] La formulación de la función generadora de Euler es un caso especial de una-Símbolo de martillo pochhammer y es similar a la formulación del producto de muchas formas modulares , y específicamente a la función eta de Dedekind .
Relaciones de recurrencia
La misma secuencia de números pentagonales aparece en una relación de recurrencia para la función de partición: [5]
Como casos base, se considera igual , y se toma como cero para negativo . Aunque la suma del lado derecho parece infinita, solo tiene un número finito de términos distintos de cero, que provienen de los valores distintos de cero de en el rango
- .
Otra relación de recurrencia para se puede dar en términos de la función de suma de divisores σ : [6]
Si denota el número de particiones de sin partes repetidas, se sigue dividiendo cada partición en sus partes pares y partes impares, y dividiendo las partes pares por dos, que [7]
Congruencias
A Srinivasa Ramanujan se le atribuye el descubrimiento de que la función de partición tiene patrones no triviales en aritmética modular . Por ejemplo, el número de particiones es divisible por cinco siempre que la representación decimal determina en el dígito 4 o 9, expresado por la congruencia [8]
Por ejemplo, el número de particiones para el número entero 4 es 5. Para el número entero 9, el número de particiones es 30; para 14 hay 135 particiones. Esta congruencia está implícita en la identidad más general
también por Ramanujan, [9] [10] donde la notación denota el producto definido por
Se puede obtener una breve prueba de este resultado de la función de generación de la función de partición.
Ramanujan también descubrió las congruencias módulo 7 y 11: [8]
Vienen de la identidad de Ramanujan [10]
Dado que 5, 7 y 11 son primos consecutivos , se podría pensar que habría una congruencia análoga para el siguiente primo 13,para algunos a . Sin embargo, no hay congruencia de la formapara cualquier primo b distinto de 5, 7 u 11. [11] En cambio, para obtener una congruencia, el argumento de debería tomar la forma para algunos . En la década de 1960, AOL Atkin de la Universidad de Illinois en Chicago descubrió congruencias adicionales de esta forma para pequeños módulos primos. Por ejemplo:
Ken Ono ( 2000 ) demostró que existen tales congruencias para cada módulo primo mayor que 3. Más tarde, Ahlgren y Ono (2001) demostraron que hay congruencias de partición módulo cada coprime entero a 6. [12] [13]
Fórmulas de aproximación
Existen fórmulas de aproximación que son más rápidas de calcular que la fórmula exacta dada anteriormente.
Una expresión asintótica para p ( n ) viene dada por
- como .
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, la fórmula asintótica da aproximadamente , razonablemente cerca de la respuesta exacta dada anteriormente (1.415% más grande que el valor real).
Hardy y Ramanujan obtuvieron una expansión asintótica con esta aproximación como primer término: [14]
dónde
Aquí, la notación implica que la suma debe ocurrir solo sobre los valores de que son relativamente primos para. La funciónes una suma de Dedekind .
El error después términos es del orden del siguiente término, y puede tomarse como del orden de . Como ejemplo, Hardy y Ramanujan demostraron que es el número entero más cercano a la suma del primer 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. Es [15] [16]
La prueba de la fórmula de Rademacher involucra círculos de Ford , secuencias de Farey , simetría modular y la función eta de Dedekind .
Puede demostrarse que el El término de la serie de Rademacher es del orden
de modo que el primer término da la aproximación asintótica de Hardy-Ramanujan. Paul Erdős ( 1942 ) publicó una prueba elemental de la fórmula asintótica para. [17] [18]
Johansson (2012) analiza las técnicas para implementar la fórmula de Hardy-Ramanujan-Rademacher de manera eficiente en una computadora , quien muestra que se puede calcular a tiempo para cualquier . Esto es casi óptimo porque 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, que tiene algo más de 11 mil millones de dígitos. [20]
Referencias
- ^ Sloane, N. J. A. (ed.), "Secuencia A070177" , La enciclopedia en línea de secuencias de enteros , Fundación OEIS
- ^ Caldwell, Chris K. (2017), Los veinte primeros
- ^ Abramowitz, Milton ; Stegun, Irene (1964), Manual de funciones matemáticas con fórmulas, gráficos y tablas matemáticas , Departamento de Comercio de los Estados Unidos, Oficina Nacional de Normas, p. 825 , ISBN 0-486-61272-4
- ^ Euler, Leonhard (1753), "De partitione numerorum" , Novi Commentarii academiae scientiarum Petropolitanae (en latín), 3 : 125-169
- ^ Ewell, John A. (2004), "Recurrencias de la función de partición y sus parientes", The Rocky Mountain Journal of Mathematics , 34 (2): 619–627, doi : 10.1216 / rmjm / 1181069871 , JSTOR 44238988 , MR 2072798
- ^ Wilf, Herbert S. (1982), "¿Qué es una respuesta?", American Mathematical Monthly , 89 (5): 289-292, doi : 10.2307 / 2321713 , MR 0653502
- ^ Al, Busra; Alkan, Mustafa (2018), "Una nota sobre las relaciones entre particiones", Proc. Mediterráneo Int. Conf. Matemática pura y aplicada. y áreas relacionadas (MICOPAM 2018) , págs. 35–39
- ^ a b Hardy, GH ; Wright, EM (2008) [1938], Introducción a la teoría de los números (6ª ed.), Oxford University Press , p. 380, ISBN 978-0-19-921986-5, MR 2445243 , Zbl 1159.11001
- ^ Berndt, Bruce C .; Ono, Ken (1999), "El manuscrito inédito de Ramanujan sobre las funciones de partición y tau con pruebas y comentarios" (PDF) , The Andrews Festschrift (Maratea, 1998) , Séminaire Lotharingien de Combinatoire , 42 , art. B42c, 63, MR 1701582
- ^ a b Ono, Ken (2004), The web of modularity: aritmética de los coeficientes de formas modulares y-serie , CBMS Regional Conference Series in Mathematics, 102 , Providence, Rhode Island: American Mathematical Society , p. 87, ISBN 0-8218-3368-5, Zbl 1119.11026
- ^ Ahlgren, Scott; Boylan, Matthew (2003), "Propiedades aritméticas de la función de partición" (PDF) , Inventiones Mathematicae , 153 (3): 487–502, doi : 10.1007 / s00222-003-0295-6 , MR 2000466
- ^ Ono, Ken (2000), "Distribución de la función de partición módulo", Annals of Mathematics , 151 (1): 293–307, arXiv : math / 0008140 , doi : 10.2307 / 121118 , MR 1745012 , Zbl 0984.11050
- ^ Ahlgren, Scott; Ono, Ken (2001), "Propiedades de congruencia para la función de partición" (PDF) , Proceedings of the National Academy of Sciences , 98 (23): 12882-12884, Bibcode : 2001PNAS ... 9812882A , doi : 10.1073 / pnas. 191488598 , MR 1862931
- ^ a b Hardy, GH ; Ramanujan, S. (1918), "Fórmulas asintóticas en análisis combinatorio", Proceedings of the London Mathematical Society , Segunda serie, 17 (75-115). Reimpreso en Documentos recopilados de Srinivasa Ramanujan , Amer. Matemáticas. Soc. (2000), págs. 276-309.
- ^ Andrews, George E. (1976), La teoría de las particiones , Cambridge University Press, pág. 69, ISBN 0-521-63766-X, MR 0557013
- ^ Rademacher, Hans (1937), "Sobre la función de partición", Actas de la London Mathematical Society , segunda serie, 43 (4): 241-254, doi : 10.1112 / plms / s2-43.4.241 , MR 1575213
- ^ Erdős, P. (1942), "Sobre una demostración elemental de algunas fórmulas asintóticas en la teoría de particiones" (PDF) , Annals of Mathematics , Second Series, 43 : 437–450, doi : 10.2307 / 1968802 , MR 0006749 , Zbl 0061.07905
- ^ Nathanson, MB (2000), Métodos elementales en teoría de números , Textos de posgrado en matemáticas , 195 , Springer-Verlag , p. 456, ISBN 0-387-98912-9, Zbl 0953.11002
- ^ Johansson, Fredrik (2012), "Implementación eficiente de la fórmula de Hardy-Ramanujan-Rademacher", LMS Journal of Computation and Mathematics , 15 : 341–59, arXiv : 1205.5991 , doi : 10.1112 / S1461157012001088 , MR 2988821
- ^ Johansson, Fredrik (2 de marzo de 2014), Nuevo registro de función de partición: p (10 20 ) calculado
enlaces externos
- Primeros 4096 valores de la función de partición