Partizione di un intero

In matematica, una partizione di un intero positivo ${\displaystyle n}$ è un modo di scrivere ${\displaystyle n}$ come somma di interi positivi, senza tener conto dell'ordine degli addendi. Formalmente, una partizione di ${\displaystyle n}$ è una m-tupla di interi positivi ${\displaystyle (\lambda _{1},\lambda _{2},\dots ,\lambda _{m})}$ tali che

${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \dots \geq \lambda _{m}~~{\text{e}}~~\lambda _{1}+\lambda _{2}+\dots +\lambda _{m}=n.}$

Spesso si chiede che ${\displaystyle n}$ sia un intero positivo; talora però risulta opportuno considerare anche come unica partizione dello ${\displaystyle 0}$ la sequenza vuota.

Esempi

Le partizioni di ${\displaystyle 4}$ sono le seguenti:

1. ${\displaystyle 4}$
2. ${\displaystyle 3+1}$
3. ${\displaystyle 2+2}$
4. ${\displaystyle 2+1+1}$
5. ${\displaystyle 1+1+1+1}$

Le partizioni di ${\displaystyle 8}$ sono invece le seguenti:

1. ${\displaystyle 8}$
2. ${\displaystyle 7+1}$
3. ${\displaystyle 6+2}$
4. ${\displaystyle 6+1+1}$
5. ${\displaystyle 5+3}$
6. ${\displaystyle 5+2+1}$
7. ${\displaystyle 5+1+1+1}$
8. ${\displaystyle 4+4}$
9. ${\displaystyle 4+3+1}$
10. ${\displaystyle 4+2+2}$
11. ${\displaystyle 4+2+1+1}$
12. ${\displaystyle 4+1+1+1+1}$
13. ${\displaystyle 3+3+2}$
14. ${\displaystyle 3+3+1+1}$
15. ${\displaystyle 3+2+2+1}$
16. ${\displaystyle 3+2+1+1+1}$
17. ${\displaystyle 3+1+1+1+1+1}$
18. ${\displaystyle 2+2+2+2}$
19. ${\displaystyle 2+2+2+1+1}$
20. ${\displaystyle 2+2+1+1+1+1}$
21. ${\displaystyle 2+1+1+1+1+1+1}$
22. ${\displaystyle 1+1+1+1+1+1+1+1}$

La funzione di partizione

La funzione di partizione indica, per ogni intero positivo ${\displaystyle n}$, il numero di partizioni esistenti per ${\displaystyle n}$. Per esempio, per quanto mostrato negli esempi,

${\displaystyle p\left(4\right)=5,}$

mentre

${\displaystyle p\left(8\right)=22.}$

La funzione partizione non è né moltiplicativa né additiva e cresce più velocemente di qualsiasi polinomio in ${\displaystyle n}$ al crescere di ${\displaystyle n}$(si vedano le formule asintotiche nel seguito). Viene solitamente indicata con ${\displaystyle p(n)}$. I primi valori di ${\displaystyle p(n)}$, partendo da ${\displaystyle n=0}$, sono:

${\displaystyle 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,\ldots }$^[1]

Congruenze

Ramanujan trovò le seguenti congruenze:

${\displaystyle {\begin{aligned}p(5k+4)&\equiv 0{\bmod {5}}\\p(7k+5)&\equiv 0{\bmod {7}}\\p(11k+6)&\equiv 0{\bmod {1}}1\\\end{aligned}}}$

Si nota che 4, 5, 6 sono numeri consecutivi e 5, 7 e 11 sono primi consecutivi. Allora si potrebbe pensare che

${\displaystyle p(13k+7)\equiv 0{\bmod {1}}3}$

Questo è falso. Infatti, si può dimostrare che non ci sono altre congruenze del tipo ${\displaystyle p(bk+a)\equiv 0{\bmod {b}}}$.

Negli anni '60 A. O. L. Atkin dell'Università dell'Illinois a Chicago scoprì ulteriori congruenze, ad esempio:

${\displaystyle p((11^{3}\cdot 13)k+237)\equiv 0{\bmod {1}}3.}$

Storia

Fino agli inizi del XX secolo si credeva che non fosse possibile trovare una formula per la funzione di partizione, ma nel 1918 Ramanujan e Hardy pubblicarono una formula asintotica per la funzione di partizione:

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left(\pi {\sqrt[{}]{\frac {2n}{3}}}\right){\text{ per }}n\to \infty }$

J.V. Uspensky ritrovò la stessa formula, indipendentemente, nel 1920.

Hardy e Ramanujan trovarono un'espansione asintotica con questa approssimazione come primo termine:

${\displaystyle p(n)\sim {\frac {1}{2\pi {\sqrt {2}}}}\sum _{k=1}^{v}A_{k}(n){\sqrt {k}}{\frac {\mathrm {d} }{\mathrm {d} n}}\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)}$

Nel 1937, Hans Rademacher migliorò la formula di Hardy e Ramanujan, elaborando una serie convergente che tende a ${\displaystyle p(n)}$:

${\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }{\sqrt {k}}\;A_{k}(n)\;{\frac {\mathrm {d} }{\mathrm {d} n}}\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),}$

dove, in entrambi i casi

${\displaystyle A_{k}(n)=\sum _{0\leq m<k\;;\;(m,k)=1}\exp \left(\pi is(m,k)-2\pi i{\frac {nm}{k}}\right),}$

con la somma effettuata sui numeri naturali compresi tra ${\displaystyle 0}$ e ${\displaystyle k}$ che sono coprimi con ${\displaystyle k}$ e con ${\displaystyle s(m,k)}$ che indica la somma di Dedekind.

Nel gennaio del 2011, il matematico statunitense Ken Ono, della Emory University di Atlanta, Georgia, insieme ai suoi collaboratori ha fatto grossi progressi nella comprensione del comportamento della funzione di partizione. Estendendo alcune formule di Ramanujan, è riuscito a mostrare che i numeri di partizione hanno un comportamento di tipo frattale: apparentemente essi sono disordinati, senza alcun legame logico o alcuna congruenza, ma se analizzati a fondo si scoprono schemi ordinati con un preciso ordine di ripetizione. Inoltre, Ken Ono, insieme ai suoi collaboratori, è riuscito a ottenere una formula esplicita che permette di calcolare le partizioni ${\displaystyle p(n)}$di qualsiasi numero intero attraverso una somma di un numero finito di termini.^[2][3]