Visualizza il feed RSS

Titolo provvisorio...

Un (altro) problemino con le addizioni... +3

Valuta questo inserimento
di pubblicato il 27-01-2012 alle 14:37 (6375 Visite)
Ebbene sì: abbiamo il piacere di riparlare di partizioni di numeri naturali, a circa un anno di distanza da questo trittico di articoli divulgativi - che pare avere qualche merito, come riscontrato sia in termini di visite che attraverso l'insolito (e persistente) volume di feedback ricevuto via email.

L'occasione di parlare nuovamente dell'argomento (che certamente merita ben altri approfondimenti) è data da alcune recentissime pubblicazioni, le quali hanno portato un flusso di novità in questo affascinante settore dell'aritmetica. Nel corso del 2011 sono infatti stati presentati ben due distinti risultati che consentono di esprimere la funzione di partizione di un intero come somma di un numero finito di termini. Il primo di tali risultati è dovuto a Ken Ono (un giovane teorico algebrico dei numeri della Emory University, nato... nel 1968 ) ed al suo altrettanto giovane collega Jan Hendrik Bruinier di Darmstadt. Il secondo risultato, apparso pochi mesi dopo, è invece dovuto al fisico matematico Jerome Malenfant, il quale - utilizzando un approccio del tutto differente - dimostra in realtà un risultato valido per numerose funzioni generatrici, incluse quelle dei numeri di Euler, Bernoulli e Stirling.

Tutto ciò costituisce, con ogni evidenza, un notevole progresso matematico rispetto alla formula di Hardy-Ramanujan-Rademacher finora nota.

Colgo l'occasione per rispondere subito alla domanda "Chi dovrebbe leggere questo genere di articolo?". Mi piace pensare che tutti dovrebbero leggerlo, trovandovi sperabilmente - ciascuno al proprio livello - qualcosa di stimolante o interessante.
Tuttavia, vista la sede e le richieste ricevute, ho ritenuto - ancor di più del solito - di dover privilegiare il punto di vista degli studenti e dei programmatori potenzialmente interessati all'idea, ma meno abituati al formalismo della matematica discreta. L'approccio seguito qui è quello di massimizzare la chiarezza e la semplicità, a costo di indulgere pedantescamente anche sui passaggi più ovvi e banali, pur sempre entro i limiti di spazio che il mezzo ci concede: il che richiede di tollerare che ciò vada occasionalmente a scapito di eleganza, sintesi e di una certa idea di rigore formale.
Per dirla alla Martin Gardner - si parva licet magnis componere, s'intende - vorrei sentire il suono di molti "A-ha!" prodotti durante la lettura...

Prima di entrare nel merito, è dunque lecito e opportuno proporre in modo pedissequo un paio di preliminari ad usum delphini: partiamo quindi dalla definizione di numero pentagonale. Si tratta di un numero figurato poligonale generato da un numero intero positivo n secondo la seguente formula:

Formula LaTeX: (1)\ \ \ q_n\;=\;\frac{3n^2-n}{2}

Naturalmente al lettore attento non sfuggirà che abbiamo già incontrato tale formula, parlando della relazione di ricorrenza euleriana impiegata da Kreher & Stinson per il loro algoritmo!

pentagon3.gif

I primi numeri pentagonali sono: 1, 5, 12, 22, 35, 51, 70, ... (OEIS A000326). Vale anche la pena di rilevare che il numero pentagonale i-esimo è pari a 1/3 del corrispondente numero triangolare di posizione 3i-1: a quest'ultimi numeri abbiamo accennato recentissimamente (tout se tient...) parlando del triangolo di Floyd.

Non posso qui esimermi dal citare uno splendido ed elegante teorema, la cui tesi è una delle numerose congetture di monsieur Pierre de Fermat: qualsiasi numero naturale può essere espresso come somma di tre numeri triangolari oppure di cinque numeri pentagonali, e più in generale si può esprimere qualsiasi naturale sommando n numeri n-gonali. A questa congettura si riferiva Carl Friederich Gauss quando annotava nei suoi diari, nel 1796, la famosa espressione:

Formula LaTeX: \epsilon\upsilon\rho\eta\kappa\alpha \text{ num}=\Delta+\Delta+\Delta

Tale apparentemente criptica espressione, rifacendosi a sua volta al leggendario "Eureka!" di Archimede, sta ad indicare che il Princeps Mathematicorum aveva appunto dimostrato il caso della congettura relativo ai numeri triangolari: dimostrazione poi puntualmente riportata nelle sue Disquisitiones Arithmeticae pubblicate due anni dopo, nel 1798.

In questo contesto ci interessano i numeri pentagonali generalizzati, che sono ottenuti inserendo nella formula (1) valori interi relativi, quindi anche negativi.
La successione generalizzata assume pertanto il seguente aspetto: 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, ... (OEIS A001318).

Per evitare poco piacevoli acrobazie tipografiche con ardite architetture in ordini soppalcati di pedici e apici, del tutto contrarie alla leggibilità, definiamo una semplice funzione accessoria che ci fornisce direttamente l'm-esimo numero pentagonale generalizzato, per ogni m naturale:

Formula LaTeX: (2)\ \ \ q(m)\overset{\text{def}}{=}\begin{cases}\frac{3m^2  +2m}{8}&\text{per m pari}\\\frac{3m^2+4m+1}{8}&\text{per m dispari}\end{cases}

Rimarcando en passant che lo zero è considerato pari, l'uso di tale notazione arbitraria ci consente di referenziare un qualsiasi numero pentagonale generalizzato pur utilizzando unicamente valori naturali per m, per comodità di scrittura.

Ricordiamo brevemente anche la definizione di coefficiente multinomiale. Si abbiano n interi positivi (non necessariamente distinti) k1...kn, e sia n>1:

Formula LaTeX: (3)\ \ \ \begin{pmatrix}k_1+k_2+\cdots+k_n\\k_1,k_2,\dots,k  _n\end{pmatrix} \overset{\text{def}}{=}\frac{(k_1+k_2+\cdots+k_n)!  }{k_1!k_2!\dots k_n!}

La funzione delta di Kronecker è un'altra nostra vecchia conoscenza:

Formula LaTeX: (4)\ \ \ \delta(a, b)\ \overset{def}{=}\ \begin{cases}0 & \text{se } a\,\neq\,b \\ 1 & \text{se } a\,=\,b \end{cases}

Per restare al gergo informatichese, tale funzione ideata un paio di secoli fa dal geniale Leopold Kronecker si comporta come un operatore di confronto entro il costrutto condizionale di scelta (IF) presente in tutti i moderni linguaggi di programmazione che soddisfino (almeno in parte!) le condizioni di Bohm-Jacopini.

A questo punto, siamo in pratica già pronti a dare un primo sguardo - in una versione opportunamente semplificata - alla formula più recente, proposta nel maggio del 2011 da Jerome Malenfant, la quale sembra la più adatta da un punto di vista didattico.

Mi preme ricordare che Malenfant dimostra anche l'esistenza di una seconda soluzione equivalente, basata sul determinante di una matrice di Toeplitz troncata alla dimensione nxn, forse meno "human-readable" ma relativamente più efficiente dal punto di vista computazionale: la vedremo meglio in seguito.

In questa entry concentreremo invece la nostra attenzione sulla prima formula, la quale esprime, come promesso, il numero di partizioni di un numero naturale n tramite una somma finita di termini. In prima approssimazione, la scriviamo come segue:

Formula LaTeX: (5)\ \ \ P(n)\;=\; \sum_{0 \leq k_1,k_2,\ldots ,k_M \leq n}(-1)^S\left( \begin{array}{c} K \\k_1,k_2,\ldots ,k_M \end{array} \right) \delta\left({n,  \sum_{m=1}^{M} k_{m}\cdot q(m)}\right)

Dove M è il numero naturale tale che q(M) restituisce il più grande numero pentagonale generalizzato non maggiore di n, e vale inoltre:

Formula LaTeX: K = k_1+k_2+\cdots+k_M=\sum_{i=1}^{M}k_i

In estrema sintesi, "cosa fa" codesta formula?
Tale sommatoria multipla enumera le disposizioni con ripetizioni dei coefficienti in una somma di numeri pentagonali generalizzati.
Talune disposizioni - quelle che non corrispondono a partizioni del numero n dato - vengono scartate. Le disposizioni rimanenti, usate nel calcolo dei coefficienti multinomiali, generano i risultati intermedi che vengono infine sommati algebricamente per ottenere il risultato finale desiderato, ossia il numero complessivo di partizioni dell'intero n dato.

Per poter usare operativamente la formula di Malenfant "con carta e penna" occorre ora solo vedere insieme un paio di ulteriori dettagli. L'espressione S che compare all'esponente del -1, il quale a sua volta determina il segno di ciascun coefficiente multinomiale nella sommatoria, è una somma selettiva dei coefficienti ki. In particolare, partecipano a codesta somma solamente i coefficienti relativi ai numeri pentagonali generalizzati generati da un intero relativo pari, zero escluso: ±2, ±4, ±6... Nulla di particolarmente esotico, quindi.

Nella nostra notazione, a causa del comodo cambio di indice arbitrario, ciò implica soltanto che dovremo includere in tale somma tutti e soli quei coefficienti che corrispondono a posizioni successive alla prima e congruenti a 0 oppure a 3 in modulo 4, più formalmente:

Formula LaTeX: S=k_3+k_4+k_7+k_8+k_{11}+k_{12}+...

Aggiungo solamente che, a rigore, noi siamo interessati unicamente al bit meno significativo di tale risultato e potremmo parimenti voler scrivere S (mod 2) nella formula, in un contesto più formale.

In ultimo - ma certo non meno importante - resta da definire come far variare i coefficienti ki. Far variare ogni coefficiente tra zero e n sarebbe ingenuo, ingiustificato e inefficiente.
Non è infatti necessario esaminare tutto lo spazio delle possibili disposizioni con elementi ripetuti, che consta di nM elementi: sappiamo già a priori che in taluni intervalli nessuna delle disposizioni generate potrà essere una partizione del numero n dato. Dobbiamo ora quantificare meglio l'espressione lasciata vaga, per amor di sintesi, qualche riga sopra.

Sappiamo bene che una partizione di un numero naturale n può avere, al massimo, n parti:

Formula LaTeX: n\ =\ \underset{\text{n volte}}{\underbrace{1 + 1 + ... + 1}}

Ricordo qui ancora una volta che il simbolo Formula LaTeX: \left \lfloor x \right \rfloor si legge "floor di x" e rappresenta il più grande intero non maggiore di x.

Estendendo in modo esplicito la considerazione già fatta sul numero massimo di parti, applichiamo ricorsivamente il ragionamento ad alcuni esempi:

Formula LaTeX: n\;\geq\;\underset{\left \lfloor n/2 \right \rfloor}{\underbrace{2+2+\cdots+2}}

Formula LaTeX: n\;\geq\;\underset{\left \lfloor n/5 \right \rfloor}{\underbrace{5+5+\cdots+5}}

Formula LaTeX: n\;\geq\;\underset{\left \lfloor n/7 \right \rfloor}{\underbrace{7+7+\cdots+7}}

Più in generale, si avrà che - con ovvia corrispondenza degli indici - ciascun generico coefficiente è limitato all'intervallo seguente, determinato dalla parte a cui il coefficiente medesimo è associato: Formula LaTeX: k_i \in [0, \left \lfloor n/\lambda_i \right \rfloor].

In particolare, per ogni parte il cui valore supera Formula LaTeX: \left \lfloor n/2 \right \rfloor i relativi coefficienti associati saranno, al più, unitari.

Questa definizione più restrittiva dell'intervallo di variazione per ciascun singolo coefficiente consente evidentemente di migliorare l'efficienza del calcolo.
Le disposizioni con elementi ripetuti dei coefficienti così vincolati, con ovvio significato dei simboli, risultano ovviamente in numero inferiore rispetto a quanto stabilito dalla formula generale DRn(M) = nM:

Formula LaTeX: \begin{align*}\\(6)\ \ \ Dq(n, M)&=\left(\left \lfloor \frac{n}{q(1)} \right \rfloor +1\right)\cdot\left(\left \lfloor \frac{n}{q(2)} \right \rfloor +1\right)\cdots\left(\left \lfloor \frac{n}{q(M)} \right \rfloor +1\right)\\&=\prod_{m=1}^{M}\left(1+ \left \lfloor \frac{n}{q(m)}\right\rfloor\right)\end{align*}

A questo punto possiamo riscrivere l'espressione della sommatoria multipla in modo meno conciso e un po' più preciso:

Formula LaTeX: (7)\ P(n)\;=\;\sum_{k_1=0}^{\left \lfloor n/q(1) \right \rfloor}\sum_{k_2=0}^{\left \lfloor n/q(2) \right \rfloor}\sum_{k_3=0}^{\left \lfloor n/q(3) \right \rfloor}\cdots\sum_{k_M=0}^{1}(-1)^S\left( \begin{array}{c} K \\k_1, k_2,\ldots ,k_M \end{array} \right) \delta\left({n,  \sum_{m=1}^{M} k_{m}\cdot q(m)}\right)

Possiamo ora procedere, a piccoli passi, con un elementare esempio di calcolo "manuale" ponendo n = 5 e ricordando che p(5) = 7.

I numeri pentagonali generalizzati compresi tra 1 e 5 sono:
q(1) = 1, q(2) = 2, q(3) = 5.
Ovviamente si ha M=3 ed avremo quindi tre corrispondenti coefficienti ki in ciascun coefficiente multinomiale. Inoltre, l'espressione all'esponente S in questo caso coincide semplicemente, per ciascun termine della somma, col solo coefficiente k3. I limiti superiori per i coefficienti valgono rispettivamente:

Formula LaTeX: \begin{align*}\\k_1&\leq \left \lfloor \frac{n}{q(1)} \right \rfloor &\Rightarrow k_1 \leq 5\\k_2&\leq \left \lfloor \frac{n}{q(2)} \right \rfloor &\Rightarrow k_2 \leq 2\\k_3&\leq\left \lfloor \frac{n}{q(3)} \right \rfloor &\Rightarrow k_3 \leq 1\end{align*}

Le possibili disposizioni con elementi ripetuti, in totale, assommano a:

Formula LaTeX: Dq(5,3)=(5+1)\cdot(2+1)\cdot(1+1)=36

Pedantescamente, sarebbe possibile scartare a priori la combinazione nulla. Generiamo comunque tutte le disposizioni con elementi ripetuti di tali coefficienti, tenendo conto unicamente dei rispettivi vincoli superiori. Sappiamo dalla OEIS A095699 che le partizioni pentagonali del numero cinque sono solamente quattro.

Formula LaTeX: \begin{array}{|l|l|l|l|l|l|l|l|}k_1&k_2&k_3& \delta&k_1&k_2&k_3& \delta\\\hline0&0&0&&0&0&1& \bigstar \\1&0&0&&1&0&1&\\2&0&0&&2&0&1&\\3&0&0&&3&0&1&\\4&0  &0&&4&0&1&\\5&0&0&\bigstar &5&0&1&\\0&1&0&&0&1&1&\\1&1&0&&1&1&1&\\2&1&0&&2&1&  1&\\3&1&0&\bigstar &3&1&1&\\4&1&0&&4&1&1&\\5&1&0&&5&1&1&\\0&2&0&&0&2&  1&\\1&2&0&\bigstar &1&2&1&\\2&2&0&&2&2&1&\\3&2&0&&3&2&1&\\4&2&0&&4&2&  1&\\5&2&0&&5&2&1&\\\end{array}

Sono marcate con una stella le sole combinazioni di numeri pentagonali che risultano partizioni del numero 5, tali cioé che:

Formula LaTeX: 5=k_1\cdot q(1)+k_2\cdot q(2)+k_3\cdot q(3)=k_1\cdot 1+k_2\cdot 2+k_3\cdot 5

In tutti e soli i casi marcati, la delta di Kronecker nella (7) assume valore unitario, mentre vale zero altrove, di fatto eliminando dalla sommatoria i termini che non contribuiscono al totale.

La tabella è stata compilata in ordine tale da evidenziare un altro aspetto. Laddove, come in questo caso, il numero n coincide con l'M-esimo numero pentagonale generalizzato, è ovvio che tutte le disposizioni nelle quali kM è pari ad uno (tranne chiaramente quella che rappresenta la partizione di n in una singola parte) possono essere scartate a priori, dimezzando di fatto il numero totale di disposizioni con ripetizioni da generare. Tuttavia, da un punto di vista quantitativo, anche un tale dimezzamento non appare particolarmente significativo, come vedremo tra qualche riga.

Prendiamo ora in considerazione le sole combinazioni valide, e ricordando che K = k1+k2+k3:

Formula LaTeX: \begin{array}{|l|l|l|l|c|}k_1&k_2&k_3&K&(-1)^S\\\hline0&0&1&1&-1\\1&2&0&3&+1\\3&1&0&4&+1\\5&0&0&5&+1\end{array}

Si avrà quindi, con ovvi passaggi:

Formula LaTeX: P(5)=-\binom{1}{0,0,1}+\binom{3}{1,2,0}+\binom{4}{3,1,0}  +\binom{5}{5,0,0}=-1+3+4+1=7

Giunti a questo punto, spero che i miei lettori comprendano da soli che la formula (7) presa in esame riveste grande importanza dal punto di vista concettuale, ma non appare direttamente applicabile.
Per scartare del tutto l'idea di tradurre in algoritmo la procedura fin qui seguita, è sufficiente uno sguardo alla seguente tabella.

codice:
n  M  q(M) p(n)  Dq(n,M)  1  2  5  7 12 15 22 26 35 40
-------------------------------------------------------------
 1  1  1      1        2  2
 2  2  2      2        6  3  2
 3  2  2      3        8  4  2
 4  2  2      5       15  5  3
 5  3  5      7       36  6  3  2
 6  3  5     11       56  7  4  2
 7  4  7     15      128  8  4  2  2
 8  4  7     22      180  9  5  2  2
 9  4  7     30      200 10  5  2  2
10  4  7     42      396 11  6  3  2
11  4  7     56      432 12  6  3  2
12  5 12     77     1092 13  7  3  2  2
13  5 12    101     1176 14  7  3  2  2
14  5 12    135     2160 15  8  3  3  2
15  6 15    176     6144 16  8  4  3  2  2
16  6 15    231     7344 17  9  4  3  2  2
17  6 15    297     7776 18  9  4  3  2  2
18  6 15    385     9120 19 10  4  3  2  2
19  6 15    490     9600 20 10  4  3  2  2
20  6 15    627    13860 21 11  5  3  2  2
21  6 15    792    19360 22 11  5  4  2  2
22  7 22   1002    44160 23 12  5  4  2  2  2
23  7 22   1255    46080 24 12  5  4  2  2  2
24  7 22   1575    78000 25 13  5  4  3  2  2
25  7 22   1958    97344 26 13  6  4  3  2  2
26  8 26   2436   217728 27 14  6  4  3  2  2  2
27  8 26   3010   225792 28 14  6  4  3  2  2  2
28  8 26   3718   313200 29 15  6  5  3  2  2  2
29  8 26   4565   324000 30 15  6  5  3  2  2  2
30  8 26   5604   624960 31 16  7  5  3  3  2  2
31  8 26   6842   645120 32 16  7  5  3  3  2  2
32  8 26   8349   706860 33 17  7  5  3  3  2  2
33  8 26  10143   728280 34 17  7  5  3  3  2  2
34  8 26  12310   793800 35 18  7  5  3  3  2  2
35  9 35  14883  2239488 36 18  8  6  3  3  2  2  2
36  9 35  17977  3239424 37 19  8  6  4  3  2  2  2
37  9 35  21637  3326976 38 19  8  6  4  3  2  2  2
38  9 35  26015  3594240 39 20  8  6  4  3  2  2  2
39  9 35  31185  3686400 40 20  8  6  4  3  2  2  2
40 10 40  37338  8926848 41 21  9  6  4  3  2  2  2  2
41 10 40  44583  9144576 42 21  9  6  4  3  2  2  2  2
42 10 40  53174 11442816 43 22  9  7  4  3  2  2  2  2
43 10 40  63261 11708928 44 22  9  7  4  3  2  2  2  2
44 10 40  75175 18779040 45 23  9  7  4  3  3  2  2  2
45 10 40  89134 28439040 46 23 10  7  4  4  3  2  2  2
46 10 40 105558 30320640 47 24 10  7  4  4  3  2  2  2
47 10 40 124754 30965760 48 24 10  7  4  4  3  2  2  2
48 10 40 147273 41160000 49 25 10  7  5  4  3  2  2  2
49 10 40 173525 48000000 50 25 10  8  5  4  3  2  2  2
50 10 40 204226 56010240 51 26 11  8  5  4  3  2  2  2
Per essere realmente migliorativo, l'algoritmo dovrebbe operare asintoticamente in meno di Formula LaTeX: \Theta(n^{\frac{3}{2}}), mentre è facile argomentare che una versione - già ottimale rispetto all'approccio ingenuo qui illustrato - basata su generazione esaustiva delle partizioni e selezione di quelle pentagonali si attesta su Formula LaTeX: \Theta(n^2) o peggiore.

Temo tuttavia che dovremo fermarci qui, avendo ormai raggiunto il famigerato limite dei ventimila caratteri. Il seguito alla prossima puntata...

Commenti