Contare i sottoinsiemi modulo p: funzioni generatrici e radici dell’unità

Cerca nel sito

Altri risultati..

Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Cerca nelle Categorie

Sottoinsiemi e radici dell’unità

Contare i sottoinsiemi di un insieme che producono una determinata somma modulo un numero primo [math]p[/math] sembra, almeno all’inizio, un problema combinatorio piuttosto semplice.


Quando gli elementi sono pochi, possiamo elencare tutte le combinazioni, calcolare le somme e raggrupparle in base al resto ottenuto nella divisione per [math]p[/math]. La situazione cambia rapidamente quando aumentano gli elementi: un insieme di 40 elementi possiede già [math]2^{40}[/math], cioè oltre mille miliardi di sottoinsiemi, e controllarli uno per uno diventa un’operazione impraticabile.

Esiste però un modo diverso di affrontare il problema, che permette di passare dall’enumerazione delle singole combinazioni a una rappresentazione algebrica complessiva. L’idea consiste nel tradurre ogni possibile scelta in un fattore polinomiale, costruire una funzione generatrice e utilizzare le radici complesse dell’unità per isolare le somme appartenenti a una determinata classe di resto.

Il risultato è particolarmente interessante perché mette in relazione tre argomenti che spesso vengono studiati separatamente: combinatoria, aritmetica modulare e analisi complessa.

Inoltre, il procedimento conduce direttamente alla Trasformata Discreta di Fourier, mostrando come una tecnica nata per risolvere un problema di conteggio sia legata a uno degli strumenti fondamentali dell’elaborazione digitale dei segnali e degli algoritmi numerici.

Il problema di partenza: perché l’enumerazione diretta diventa impraticabile

Consideriamo inizialmente l’insieme

[math]\displaystyle S=\{1,2,3\}[/math]

e supponiamo di voler determinare quanti sottoinsiemi hanno una somma uguale a un certo valore.

Sottoinsieme Elementi inclusi Somma
[math]\varnothing[/math] Nessuno 0
[math]\{1\}[/math] Solo 1 1
[math]\{2\}[/math] Solo 2 2
[math]\{3\}[/math] Solo 3 3
[math]\{1,2\}[/math] 1 e 2 3
[math]\{1,3\}[/math] 1 e 3 4
[math]\{2,3\}[/math] 2 e 3 5
[math]\{1,2,3\}[/math] Tutti 6

Con tre elementi abbiamo esattamente

[math]\displaystyle 2^3=8[/math]

sottoinsiemi e possiamo verificare immediatamente che quelli con somma uguale a 3 sono due, ovvero [math]\{3\}[/math] e [math]\{1,2\}[/math].

Il numero delle combinazioni cresce però in modo esponenziale rispetto alla cardinalità dell’insieme. Con 20 elementi dobbiamo considerare

[math]\displaystyle 2^{20}=1.048.576[/math]

sottoinsiemi, mentre con 50 elementi arriviamo a

[math]\displaystyle 2^{50}\approx 1,126\cdot 10^{15}.[/math]

Anche un calcolatore veloce incontrerebbe difficoltà nell’esaminare individualmente tutte queste configurazioni.

La difficoltà non dipende tanto dal calcolo delle somme, quanto dal numero di combinazioni da prendere in considerazione. Per affrontare il problema in modo più efficiente dobbiamo quindi cambiare rappresentazione: anziché costruire ogni sottoinsieme, cerchiamo un’espressione algebrica che li rappresenti tutti contemporaneamente.

👉 Sottoinsiemi con somma divisibile per un numero: combinatoria, congruenze e funzioni generatrici

Dalle scelte combinatorie alle funzioni generatrici

Le funzioni generatrici consentono di associare a una famiglia di combinazioni un polinomio i cui coefficienti contengono le informazioni che ci interessano. Nel nostro caso vogliamo che l’esponente di ogni monomio rappresenti la somma degli elementi scelti, mentre il coefficiente indichi quanti sottoinsiemi producono proprio quella somma.

Riprendiamo [math]S=\{1,2,3\}[/math]. A ogni elemento [math]a[/math] associamo il binomio

[math]\displaystyle 1+x^a.[/math]

La scelta di questo fattore deriva direttamente dal modo in cui si costruisce un sottoinsieme: possiamo escludere l’elemento [math]a[/math], contribuendo con il termine [math]1=x^0[/math], oppure includerlo, aggiungendo [math]a[/math] alla somma attraverso il termine [math]x^a[/math].

Moltiplicando i binomi relativi a tutti gli elementi otteniamo

[math]\displaystyle P(x)=(1+x)(1+x^2)(1+x^3).[/math]

Sviluppando il prodotto, prima moltiplichiamo i primi due fattori e successivamente il risultato per il terzo:

[math]\displaystyle \begin{aligned}
P(x)&=(1+x+x^2+x^3)(1+x^3)\\
&=1+x+x^2+2x^3+x^4+x^5+x^6.
\end{aligned}[/math]

Il significato dei coefficienti è ora immediato: l’esponente indica una somma raggiungibile, mentre il coefficiente specifica quanti sottoinsiemi distinti realizzano quella somma.

Ad esempio, il termine [math]2x^3[/math] indica che esistono due sottoinsiemi con somma uguale a 3, mentre il termine costante [math]1[/math] rappresenta l’unico sottoinsieme con somma zero, cioè l’insieme vuoto.

Utilizzando la notazione [math][x^s]P(x)[/math], che indica il coefficiente del monomio di grado [math]s[/math], possiamo scrivere:

[math]\displaystyle [x^3]P(x)=2.[/math]

In generale, per un insieme finito di interi non negativi

[math]\displaystyle S=\{a_1,a_2,\ldots,a_n\},[/math]

la funzione generatrice delle somme dei sottoinsiemi è

[math]\displaystyle P(x)=\prod_{a\in S}(1+x^a),[/math]

e vale la relazione

[math]\displaystyle [x^s]P(x)=
\text{numero di sottoinsiemi con somma }s.[/math]

Per approfondire la costruzione e le diverse applicazioni di questo strumento è utile anche la lettura di Funzioni Generatrici: Guida Completa con Esercizi Risolti, Fibonacci e Applicazioni, che introduce il metodo e ne presenta altri impieghi in combinatoria e nello studio delle successioni.

Nel nostro problema, tuttavia, non vogliamo necessariamente conoscere quanti sottoinsiemi producono una somma esattamente uguale a [math]s[/math]. Ci interessa sapere quanti producono una somma congrua a un certo resto [math]r[/math] modulo [math]p[/math], indipendentemente dal valore effettivo della somma. Dovremmo quindi sommare tutti i coefficienti associati agli esponenti

[math]\displaystyle s\equiv r\pmod p.[/math]

È proprio in questo passaggio che entrano in gioco le radici dell’unità.

Le radici dell’unità: una geometria che seleziona i resti

Fissiamo un intero [math]p\geq 2[/math] e consideriamo le soluzioni complesse dell’equazione

[math]\displaystyle z^p=1.[/math]

Queste soluzioni sono chiamate radici p-esime dell’unità e si dispongono regolarmente sulla circonferenza unitaria del piano complesso, formando i vertici di un poligono regolare.

La radice primitiva p-esima dell’unità può essere definita attraverso la formula di Eulero:

[math]\displaystyle \begin{aligned}
\omega &= e^{2\pi i/p} \\
&= \cos\left(\frac{2\pi}{p}\right)
+i\sin\left(\frac{2\pi}{p}\right).
\end{aligned}[/math]

Tutte le radici p-esime dell’unità sono quindi

[math]\displaystyle 1,\omega,\omega^2,\ldots,\omega^{p-1},[/math]

e soddisfano la proprietà fondamentale

[math]\displaystyle \omega^p=1.[/math]

La disposizione geometrica è importante perché consente di comprendere intuitivamente il meccanismo che utilizzeremo. Le radici sono punti equidistanti sulla circonferenza e le loro potenze ruotano progressivamente da un vertice all’altro.

Consideriamo, ad esempio, il caso [math]p=5[/math]. Le cinque radici formano un pentagono regolare inscritto nella circonferenza unitaria. La loro somma vettoriale è nulla, perché i vettori diretti verso i cinque vertici si compensano reciprocamente.

Le cinque radici quinte dell’unità sono equidistanti sulla circonferenza unitaria e la loro somma vettoriale è zero.

La proprietà geometrica si traduce in un’identità algebrica molto importante.

Per qualsiasi intero [math]m[/math], consideriamo la somma

[math]\displaystyle \begin{aligned}
S(m)&=\sum_{j=0}^{p-1}\omega^{jm}\\
&=1+\omega^m+\omega^{2m}+\cdots+\omega^{(p-1)m}.
\end{aligned}[/math]

Il risultato dipende esclusivamente dal resto di [math]m[/math] nella divisione per [math]p[/math].

Se [math]m[/math] è divisibile per [math]p[/math], allora [math]\omega^m=1[/math] e tutti gli addendi valgono uno. Otteniamo quindi

[math]\displaystyle S(m)=p.[/math]

Se invece [math]m[/math] non è divisibile per [math]p[/math], il numero [math]\omega^m[/math] è diverso da uno e possiamo applicare la formula della somma geometrica:

[math]\displaystyle \begin{aligned}
S(m)
&=\frac{1-\omega^{mp}}{1-\omega^m}\\
&=\frac{1-(\omega^p)^m}{1-\omega^m}\\
&=\frac{1-1}{1-\omega^m}=0.
\end{aligned}[/math]

Il risultato può essere riassunto nella relazione

[math]\displaystyle \boxed{
\frac{1}{p}\sum_{j=0}^{p-1}\omega^{jm}
=
\begin{cases}
1 & \text{se }m\equiv0\pmod p\\
0 & \text{se }m\not\equiv0\pmod p.
\end{cases}
}[/math]

Ti potrebbe interessare anche:  Calcolo Combinatorio: Esercizi Risolti Spiegati Passo Passo (Disposizioni, Inclusione-Esclusione)

Questa identità è conosciuta come filtro delle radici dell’unità.

Il termine filtro descrive bene ciò che accade: quando l’esponente è multiplo di [math]p[/math], tutti i contributi si sommano e producono il valore 1 dopo la divisione per [math]p[/math]; quando invece l’esponente non è divisibile per [math]p[/math], i contributi si cancellano reciprocamente e il risultato è zero.

La cancellazione non è un’approssimazione numerica, ma un’identità matematica esatta. È questa proprietà a permetterci di selezionare una classe di resto senza esaminare separatamente tutte le somme possibili.

La formula generale per contare i sottoinsiemi modulo p

Possiamo ora unire la funzione generatrice con il filtro delle radici dell’unità.

Sia

[math]\displaystyle P(x)=\sum_{s\geq0}c_sx^s[/math]

il polinomio generatore delle somme dei sottoinsiemi di un insieme finito [math]S[/math], dove [math]c_s[/math] rappresenta il numero di sottoinsiemi con somma esattamente uguale a [math]s[/math].

Vogliamo calcolare [math]N_r[/math], cioè il numero complessivo di sottoinsiemi la cui somma è congrua a [math]r[/math] modulo [math]p[/math].

Per individuare i termini desiderati utilizziamo il filtro applicato a [math]m=s-r[/math]:

[math]\displaystyle \frac{1}{p}\sum_{j=0}^{p-1}
\omega^{j(s-r)}.[/math]

Questa espressione vale uno quando [math]s-r[/math] è divisibile per [math]p[/math] e zero in tutti gli altri casi. Possiamo quindi scrivere

[math]\displaystyle N_r=
\sum_{s\geq0}c_s
\left(
\frac{1}{p}
\sum_{j=0}^{p-1}\omega^{j(s-r)}
\right).[/math]

Poiché il polinomio possiede un numero finito di termini, possiamo scambiare l’ordine delle sommatorie e raccogliere i fattori che non dipendono da [math]s[/math]:

[math]\displaystyle N_r=
\frac{1}{p}
\sum_{j=0}^{p-1}
\omega^{-jr}
\left(
\sum_{s\geq0}c_s\omega^{js}
\right).[/math]

La sommatoria interna non è altro che il polinomio [math]P(x)[/math] valutato nel punto [math]x=\omega^j[/math]. Arriviamo così alla formula generale:

[math]\displaystyle \boxed{
N_r=
\frac{1}{p}
\sum_{j=0}^{p-1}
\omega^{-jr}P(\omega^j)
}[/math]

Questa relazione permette di ricavare il numero di sottoinsiemi appartenenti a una determinata classe di resto attraverso le valutazioni del polinomio generatore nelle radici p-esime dell’unità.

Il termine corrispondente a [math]j=0[/math] merita una particolare attenzione, perché

[math]\displaystyle P(\omega^0)=P(1)=2^n.[/math]

Il valore [math]2^n[/math] rappresenta il numero totale dei sottoinsiemi dell’insieme iniziale. Gli altri termini della sommatoria introducono le correzioni necessarie per descrivere come questi sottoinsiemi si distribuiscono nelle diverse classi di resto.

La formula è valida per qualsiasi insieme finito di interi non negativi e per qualsiasi modulo [math]p\geq2[/math], non soltanto quando [math]p[/math] è primo. La primalità diventa importante nelle semplificazioni algebriche che vedremo tra poco.

Un risultato elegante: i sottoinsiemi di [math]\{1, 2, \ldots, p\}[/math] e [math]\{1, 2, \ldots, p-1\}[/math]

Consideriamo adesso un caso particolare nel quale la formula generale permette di ottenere un risultato molto più semplice.

Sia

[math]\displaystyle S_p=\{1,2,\ldots,p\},[/math]

dove [math]p[/math] è un numero primo dispari. La funzione generatrice è

[math]\displaystyle P(x)=\prod_{k=1}^{p}(1+x^k).[/math]

Per [math]j=0[/math] abbiamo immediatamente

[math]\displaystyle P(1)=2^p.[/math]

Per gli altri valori [math]j=1,2,\ldots,p-1[/math], sfruttiamo invece la proprietà

[math]\displaystyle \omega^{jp}=1.[/math]

Possiamo quindi isolare l’ultimo fattore del prodotto:

[math]\displaystyle \begin{aligned}
P(\omega^j)
&=(1+\omega^{jp})
\prod_{k=1}^{p-1}(1+\omega^{jk})\\
&=2\prod_{k=1}^{p-1}(1+\omega^{jk}).
\end{aligned}[/math]

A questo punto interviene una proprietà fondamentale dei numeri primi.

Poiché [math]p[/math] è primo e [math]j[/math] non è divisibile per [math]p[/math], il massimo comune divisore tra [math]j[/math] e [math]p[/math] è uno. Di conseguenza, moltiplicare i residui

[math]\displaystyle 1,2,\ldots,p-1[/math]

per [math]j[/math] e ridurli modulo [math]p[/math] produce una permutazione degli stessi residui non nulli.

Ad esempio, modulo 7, moltiplicando i residui per 2 otteniamo

[math]\displaystyle 2,4,6,1,3,5,[/math]

che contiene esattamente tutti i numeri da 1 a 6, anche se in un ordine diverso.

La stessa proprietà vale per qualsiasi [math]j[/math] non nullo modulo [math]p[/math]. Possiamo quindi scrivere

[math]\displaystyle \prod_{k=1}^{p-1}(1+\omega^{jk})
=
\prod_{k=1}^{p-1}(1+\omega^k).[/math]

Il prodotto a destra può essere valutato utilizzando il polinomio ciclotomico

[math]\displaystyle \Phi_p(x)=1+x+x^2+\cdots+x^{p-1},[/math]

che possiede come radici proprio

[math]\displaystyle \omega,\omega^2,\ldots,\omega^{p-1}.[/math]

La sua fattorizzazione è

[math]\displaystyle \Phi_p(x)=\prod_{k=1}^{p-1}(x-\omega^k).[/math]

Valutando entrambi i membri in [math]x=-1[/math], otteniamo

[math]\displaystyle \begin{aligned}
\Phi_p(-1)
&=\prod_{k=1}^{p-1}(-1-\omega^k)\\
&=(-1)^{p-1}
\prod_{k=1}^{p-1}(1+\omega^k).
\end{aligned}[/math]

Poiché [math]p[/math] è dispari, [math]p-1[/math] è pari e il fattore [math](-1)^{p-1}[/math] vale uno.

D’altra parte, sostituendo direttamente [math]x=-1[/math] nel polinomio ciclotomico troviamo

[math]\displaystyle \Phi_p(-1)=1-1+1-\cdots+1=1.[/math]

Ne segue che

[math]\displaystyle \prod_{k=1}^{p-1}(1+\omega^k)=1[/math]

e, di conseguenza,

[math]\displaystyle \boxed{P(\omega^j)=2}[/math]

per ogni [math]j=1,2,\ldots,p-1[/math].

Abbiamo così ricondotto tutte le valutazioni complesse necessarie a due soli valori: [math]2^p[/math] per [math]j=0[/math] e 2 per tutti gli altri indici.

Sostituendo nella formula generale otteniamo

[math]\displaystyle N_r=
\frac{1}{p}
\left(
2^p+2\sum_{j=1}^{p-1}\omega^{-jr}
\right).[/math]

Possiamo distinguere due situazioni.

Quando [math]r=0[/math], tutti i fattori [math]\omega^{-jr}[/math] valgono uno e la sommatoria contiene [math]p-1[/math] termini:

[math]\displaystyle \boxed{
N_0=\frac{2^p+2(p-1)}{p}
}[/math]

Quando [math]r\neq0[/math], utilizziamo nuovamente il filtro delle radici dell’unità. La somma di tutte le potenze da [math]j=0[/math] a [math]j=p-1[/math] è nulla, quindi

[math]\displaystyle \sum_{j=1}^{p-1}\omega^{-jr}=-1.[/math]

Otteniamo pertanto

[math]\displaystyle \boxed{
N_r=\frac{2^p-2}{p}
\qquad r\neq0.
}[/math]

Il risultato mostra che, nell’insieme [math]\{1,2,\ldots,p\}[/math], la classe di resto zero contiene esattamente due sottoinsiemi in più rispetto a ciascuna delle altre classi.

La ragione è legata alla presenza dell’elemento [math]p[/math], che non modifica la somma modulo [math]p[/math]. Ogni sottoinsieme può infatti essere considerato in due versioni: una senza l’elemento [math]p[/math] e una con l’elemento [math]p[/math]. Entrambe appartengono alla stessa classe di resto.

Possiamo verificare la stessa struttura considerando l’insieme senza l’ultimo elemento:

[math]\displaystyle T_p=\{1,2,\ldots,p-1\}.[/math]

La sua funzione generatrice è

[math]\displaystyle Q(x)=\prod_{k=1}^{p-1}(1+x^k).[/math]

Per [math]j=0[/math] abbiamo

[math]\displaystyle Q(1)=2^{p-1},[/math]

mentre per ogni [math]j\neq0[/math], grazie alla permutazione dei residui e alla valutazione del polinomio ciclotomico già dimostrata,

[math]\displaystyle Q(\omega^j)=1.[/math]

Applicando la formula generale ricaviamo

[math]\displaystyle \boxed{
N_0=\frac{2^{p-1}+p-1}{p}
}[/math]

e

[math]\displaystyle \boxed{
N_r=\frac{2^{p-1}-1}{p}
\qquad r\neq0.
}[/math]

Anche in questo caso la classe di resto zero contiene esattamente [math]p-1[/math] sottoinsiemi in più rispetto a ciascuna delle altre classi.

Esercizi svolti per applicare il metodo

Esercizio 1 – Distribuzione completa dei resti su S = {1, 2, 3, 4, 5, 6, 7}

Consideriamo l’insieme

[math]\displaystyle S_7=\{1,2,3,4,5,6,7\}[/math]

e vogliamo determinare quanti sottoinsiemi producono ciascun resto nella divisione della loro somma per 7.

Poiché [math]p=7[/math] è un numero primo dispari, possiamo utilizzare direttamente le formule appena dimostrate.

Il numero complessivo dei sottoinsiemi è

[math]\displaystyle 2^7=128.[/math]

Per il resto zero, cioè per le somme divisibili per 7, otteniamo

[math]\displaystyle \begin{aligned}
N_0
&=\frac{2^7+2(7-1)}{7}\\
&=\frac{128+12}{7}\\
&=\frac{140}{7}=20.
\end{aligned}[/math]

Per ciascuno dei sei resti non nulli utilizziamo invece

[math]\displaystyle \begin{aligned}
N_r
&=\frac{2^7-2}{7}\\
&=\frac{126}{7}=18.
\end{aligned}[/math]

La distribuzione completa è quindi:

Resto modulo 7 Numero di sottoinsiemi
0 20
1 18
2 18
3 18
4 18
5 18
6 18

Possiamo controllare la correttezza del risultato sommando i conteggi delle sette classi:

[math]\displaystyle 20+6\cdot18=128.[/math]

Il risultato coincide con il numero totale dei sottoinsiemi, confermando che tutte le combinazioni sono state conteggiate una sola volta.

Ti potrebbe interessare anche:  Esercizi risolti che utilizzano il teorema di Nicomaco

Esercizio 2 – Una collezione con elementi distinti ma valori ripetuti

Il metodo delle funzioni generatrici non richiede che gli elementi abbiano tutti valori numerici differenti. È sufficiente che gli oggetti siano distinguibili, anche quando possiedono lo stesso peso o lo stesso valore.

Consideriamo una collezione formata da tre oggetti:

[math]\displaystyle S=\{1,2,2’\},[/math]

dove [math]2[/math] e [math]2′[/math] sono due elementi distinti, entrambi associati al valore numerico 2.

Vogliamo contare i sottoinsiemi la cui somma è congrua a 3 modulo 5.

La funzione generatrice deve contenere un fattore per ogni oggetto:

[math]\displaystyle P(x)=(1+x)(1+x^2)(1+x^2).[/math]

Sviluppando il prodotto otteniamo

[math]\displaystyle \begin{aligned}
P(x)
&=(1+x)(1+2x^2+x^4)\\
&=1+x+2x^2+2x^3+x^4+x^5.
\end{aligned}[/math]

Il coefficiente di [math]x^3[/math] è 2, ma dobbiamo verificare che il filtro modulo 5 non richieda di considerare altri esponenti congrui a 3.

Poiché il grado massimo del polinomio è 5, l’unico esponente congruo a 3 modulo 5 è proprio 3.

Applicando la formula generale con

[math]\displaystyle \omega=e^{2\pi i/5}[/math]

avremmo

[math]\displaystyle N_3=\frac15\sum_{j=0}^{4}\omega^{-3j}P(\omega^j).[/math]

Il filtro seleziona il coefficiente del termine [math]x^3[/math], lasciando quindi

[math]\displaystyle \boxed{N_3=2}.[/math]

I due sottoinsiemi corrispondenti sono

[math]\displaystyle \{1,2\}
\qquad\text{e}\qquad
\{1,2’\}.[/math]

L’esempio evidenzia perché è importante distinguere gli oggetti dai loro valori numerici: se avessimo considerato i due elementi di valore 2 come un unico elemento, avremmo perso alcune combinazioni possibili.

Esercizio 3 – Imporre contemporaneamente un vincolo sulla cardinalità

Finora abbiamo contato i sottoinsiemi in base alla somma dei loro elementi, senza imporre restrizioni sul numero di elementi selezionati.

Possiamo però estendere il metodo introducendo una seconda variabile, che consenta di tenere traccia contemporaneamente della somma e della cardinalità.

Consideriamo nuovamente

[math]\displaystyle S_7=\{1,2,3,4,5,6,7\}[/math]

e vogliamo contare i sottoinsiemi che contengono esattamente tre elementi e hanno una somma divisibile per 7.

Introduciamo la funzione generatrice bivariata

[math]\displaystyle P(x,y)=\prod_{a=1}^{7}(1+yx^a).[/math]

La variabile [math]x[/math] registra la somma degli elementi selezionati, mentre [math]y[/math] registra il numero degli elementi inclusi. Ogni monomio

[math]\displaystyle y^kx^s[/math]

corrisponde quindi a un sottoinsieme di cardinalità [math]k[/math] e somma [math]s[/math].

Per selezionare esclusivamente i sottoinsiemi di cardinalità 3, consideriamo il coefficiente di [math]y^3[/math], indicato con

[math]\displaystyle [y^3]P(x,y).[/math]

Applicando il filtro delle radici settime dell’unità otteniamo

[math]\displaystyle N_{3,0}
=
\frac17\sum_{j=0}^{6}
[y^3]P(\omega^j,y).[/math]

Per [math]j=0[/math], abbiamo [math]\omega^0=1[/math] e quindi

[math]\displaystyle P(1,y)=(1+y)^7.[/math]

Il coefficiente di [math]y^3[/math] è il coefficiente binomiale

[math]\displaystyle [y^3]P(1,y)=\binom73=35.[/math]

Per gli altri valori di [math]j[/math], possiamo sfruttare nuovamente la permutazione dei residui modulo 7:

[math]\displaystyle \begin{aligned}
P(\omega^j,y)
&=(1+y)\prod_{a=1}^{6}(1+y\omega^{ja})\\
&=(1+y)\prod_{a=1}^{6}(1+y\omega^a).
\end{aligned}[/math]

Ricordando che le radici non banali sono gli zeri del polinomio

[math]\displaystyle 1+z+z^2+\cdots+z^6,[/math]

si ricava l’identità

[math]\displaystyle \prod_{a=1}^{6}(1+y\omega^a)
=
1-y+y^2-y^3+y^4-y^5+y^6.[/math]

Moltiplicando per [math]1+y[/math] otteniamo

[math]\displaystyle \begin{aligned}
P(\omega^j,y)
&=(1+y)(1-y+y^2-y^3\\
&\quad+y^4-y^5+y^6)\\
&=1+y^7.
\end{aligned}[/math]

Il coefficiente di [math]y^3[/math] è quindi nullo per tutti i valori [math]j\neq0[/math].

La sommatoria si riduce al solo contributo corrispondente a [math]j=0[/math]:

[math]\displaystyle \begin{aligned}
N_{3,0}
&=\frac17(35+0+0+0+0+0+0)\\
&=\boxed{5}.
\end{aligned}[/math]

Le cinque terne che soddisfano entrambe le condizioni sono

[math]\displaystyle \{1,2,4\},\quad
\{1,6,7\},\quad
\{2,5,7\},[/math]

[math]\displaystyle \{3,4,7\},\quad
\{3,5,6\}.[/math]

L’introduzione della seconda variabile mostra come le funzioni generatrici possano gestire più vincoli combinatori contemporaneamente, mantenendo la stessa struttura matematica utilizzata per il conteggio delle somme.

Cosa cambia quando il modulo non è un numero primo

Finora abbiamo utilizzato principalmente moduli primi, ma è importante chiarire che la primalità non è necessaria per applicare il filtro delle radici dell’unità.

La dimostrazione della formula si basa soltanto sulle proprietà delle radici [math]m[/math]-esime dell’unità e sulla somma geometrica. Di conseguenza, il filtro funziona per qualsiasi intero [math]m\geq2[/math], composto o primo che sia.

Per esempio, consideriamo

[math]\displaystyle m=4,\qquad S=\{1,2,3,4\}.[/math]

Le radici quarte dell’unità sono

[math]\displaystyle 1,\quad i,\quad -1,\quad -i,[/math]

e la funzione generatrice è

[math]\displaystyle P(x)=(1+x)(1+x^2)(1+x^3)(1+x^4).[/math]

Vogliamo contare i sottoinsiemi la cui somma è divisibile per 4. La formula generale diventa

[math]\displaystyle N_0=
\frac14\left[
P(1)+P(i)+P(-1)+P(-i)
\right].[/math]

Calcoliamo separatamente le quattro valutazioni.

Per [math]x=1[/math]:

[math]\displaystyle P(1)=2^4=16.[/math]

Per [math]x=i[/math], il fattore [math]1+i^2[/math] è nullo e quindi

[math]\displaystyle P(i)=0.[/math]

Analogamente, per [math]x=-1[/math] il fattore [math]1+(-1)[/math] si annulla:

[math]\displaystyle P(-1)=0.[/math]

Infine, anche per [math]x=-i[/math] abbiamo il fattore

[math]\displaystyle 1+(-i)^2=0,[/math]

da cui

[math]\displaystyle P(-i)=0.[/math]

Il conteggio è pertanto

[math]\displaystyle \boxed{N_0=\frac{16}{4}=4}.[/math]

La differenza rispetto al caso primo emerge quando cerchiamo di ottenere formule chiuse per gli insiemi consecutivi, sfruttando la permutazione dei residui.

Se il modulo [math]m[/math] è composto, infatti, non tutti gli indici [math]j[/math] sono coprimi con [math]m[/math]. Quando

[math]\displaystyle \gcd(j,m)\neq1,[/math]

la moltiplicazione per [math]j[/math] modulo [math]m[/math] non permuta tutte le classi di resto e non possiamo applicare automaticamente la semplificazione utilizzata nel caso primo.

Occorre quindi distinguere due proprietà: il filtro delle radici dell’unità è valido per qualsiasi modulo, mentre alcune semplificazioni algebriche richiedono che il modulo sia primo o, più in generale, che gli indici coinvolti siano coprimi con il modulo.

Gli errori più frequenti negli esercizi e nei calcoli

Quando si applica questo metodo, alcune difficoltà ricorrono con particolare frequenza. La maggior parte non riguarda calcoli complessi, ma interpretazioni scorrette della funzione generatrice o del filtro.

Errore frequente Come evitarlo
Considerare soltanto gli esponenti minori di [math]p[/math] Un resto [math]r[/math] comprende tutte le somme della forma [math]r+kp[/math], non soltanto la somma uguale a [math]r[/math].
Dimenticare il fattore [math]\omega^{-jr}[/math] Questo fattore è uguale a 1 soltanto quando [math]r=0[/math]; ometterlo negli altri casi significa calcolare il conteggio del resto zero anziché quello desiderato.
Confondere coefficiente ed esponente Nell’espressione [math]c_sx^s[/math], l’esponente rappresenta la somma, mentre il coefficiente indica il numero di sottoinsiemi che la producono.
Applicare le semplificazioni del caso primo a un modulo composto Prima di utilizzare la proprietà di permutazione dei residui occorre verificare che [math]\gcd(j,m)=1[/math].
Dimenticare l’insieme vuoto Il termine costante [math]1=x^0[/math] rappresenta sempre l’insieme vuoto, che appartiene alla classe di resto zero.
Accorpare elementi distinti con lo stesso valore Due oggetti distinti di valore [math]a[/math] richiedono due fattori [math](1+x^a)^2[/math], non un unico fattore [math](1+x^{2a})[/math].

Un’ulteriore attenzione riguarda i calcoli numerici. Se valutiamo direttamente il polinomio in radici complesse utilizzando la normale aritmetica in virgola mobile, possono comparire piccoli errori di arrotondamento, soprattutto nella parte immaginaria del risultato.

Poiché il numero di sottoinsiemi è necessariamente un intero, quando utilizziamo un’implementazione numerica dobbiamo verificare che la parte immaginaria sia trascurabile e che la parte reale sia sufficientemente vicina a un intero. Soltanto dopo questi controlli possiamo arrotondare il risultato.

Ti potrebbe interessare anche:  Equazioni Diofantee: Guida Pratica con Esercizi Risolti (Dalla Lineare all'Esponenziale)

Per ottenere risultati certificati è preferibile utilizzare l’aritmetica esatta, quando disponibile, oppure lavorare simbolicamente riducendo i polinomi modulo il polinomio ciclotomico appropriato.

Il collegamento con la Trasformata Discreta di Fourier

La formula

[math]\displaystyle N_r=
\frac1p\sum_{j=0}^{p-1}
\omega^{-jr}P(\omega^j)[/math]

ha un significato che va oltre il conteggio dei sottoinsiemi.

Osservandola dal punto di vista dell’analisi armonica, riconosciamo infatti la formula della Trasformata Discreta di Fourier inversa applicata al gruppo ciclico [math]\mathbb Z/p\mathbb Z[/math].

Per comprendere questo collegamento, consideriamo il vettore dei conteggi

[math]\displaystyle (N_0,N_1,\ldots,N_{p-1}),[/math]

che rappresenta il numero di sottoinsiemi appartenenti a ciascuna classe di resto.

Possiamo costruire una funzione che associa a ogni resto [math]r[/math] il corrispondente conteggio [math]N_r[/math]. La sua trasformata discreta di Fourier è

[math]\displaystyle \widehat N_j=
\sum_{r=0}^{p-1}N_r\omega^{jr}.[/math]

D’altra parte, ricordando che

[math]\displaystyle P(x)=\sum_{s\geq0}c_sx^s,[/math]

possiamo raggruppare i termini in base al resto degli esponenti modulo [math]p[/math]:

[math]\displaystyle \begin{aligned}
P(\omega^j)
&=\sum_{s\geq0}c_s\omega^{js}\\
&=\sum_{r=0}^{p-1}
\left(\sum_{s\equiv r\pmod p}c_s\right)
\omega^{jr}\\
&=\sum_{r=0}^{p-1}N_r\omega^{jr}.
\end{aligned}[/math]

Otteniamo quindi

[math]\displaystyle \boxed{\widehat N_j=P(\omega^j)}.[/math]

Le valutazioni del polinomio generatore nelle radici dell’unità costituiscono esattamente lo spettro di Fourier del vettore dei conteggi. La formula precedente non fa altro che ricostruire il vettore originale attraverso la trasformata inversa.

Vediamo un esempio numerico per rendere più chiaro il passaggio.

Consideriamo nuovamente

[math]\displaystyle S=\{1,2,3\}[/math]

e calcoliamo quanti sottoinsiemi producono ciascun resto modulo 3.

Dalla tabella iniziale possiamo ricavare

[math]\displaystyle (N_0,N_1,N_2)=(4,2,2).[/math]

La funzione generatrice è

[math]\displaystyle P(x)=(1+x)(1+x^2)(1+x^3).[/math]

Ponendo [math]\omega=e^{2\pi i/3}[/math], sappiamo che [math]\omega^3=1[/math] e che

[math]\displaystyle 1+\omega+\omega^2=0.[/math]

Le valutazioni del polinomio sono

[math]\displaystyle P(1)=8,[/math]

[math]\displaystyle P(\omega)=2(1+\omega)(1+\omega^2)=2,[/math]

[math]\displaystyle P(\omega^2)=2(1+\omega^2)(1+\omega)=2.[/math]

Il vettore trasformato è quindi

[math]\displaystyle (\widehat N_0,\widehat N_1,\widehat N_2)=(8,2,2).[/math]

Applicando la trasformata inversa otteniamo

[math]\displaystyle N_0=\frac{8+2+2}{3}=4,[/math]

mentre

[math]\displaystyle N_1=\frac{8+2\omega^{-1}+2\omega^{-2}}{3}=2[/math]

e, per simmetria,

[math]\displaystyle N_2=2.[/math]

Abbiamo ricostruito esattamente la distribuzione iniziale dei sottoinsiemi attraverso tre valutazioni del polinomio.

Il legame con la Fourier è particolarmente importante anche dal punto di vista computazionale. La Fast Fourier Transform (FFT) permette infatti di calcolare trasformate discrete in modo molto più rapido rispetto alla valutazione diretta quando la dimensione del problema è sufficientemente grande e sono disponibili le strutture algebriche appropriate.

Questo non significa che il metodo delle radici dell’unità sia sempre più veloce di ogni algoritmo alternativo per contare i sottoinsiemi. Per un problema con [math]n[/math] elementi e [math]p[/math] classi di resto, una valutazione diretta della formula richiede generalmente un numero di operazioni dell’ordine di [math]O(np)[/math], mentre una programmazione dinamica sulle classi di resto può raggiungere lo stesso ordine di complessità, lavorando direttamente con numeri interi.

La rappresentazione attraverso le radici dell’unità offre però un vantaggio concettuale notevole: trasforma un problema combinatorio in un problema di analisi armonica e permette di sfruttare strumenti come la DFT e la FFT quando la struttura del problema lo consente.

Quando combinatoria, algebra e Fourier si incontrano

Il conteggio dei sottoinsiemi modulo [math]p[/math] mostra come un problema apparentemente elementare possa condurre a una struttura matematica molto più ricca di quanto suggerisca la sua formulazione iniziale.

Le funzioni generatrici permettono di rappresentare tutte le possibili somme attraverso un unico polinomio, trasformando le scelte combinatorie in coefficienti da analizzare. Le radici dell’unità introducono invece un meccanismo di selezione fondato sulla cancellazione dei contributi indesiderati, consentendo di isolare esattamente le somme appartenenti a una determinata classe di resto.

La primalità del modulo non è necessaria per il funzionamento del filtro, ma diventa decisiva quando vogliamo sfruttare la permutazione dei residui e ottenere risultati algebrici particolarmente semplici, come quelli relativi agli insiemi [math]\{1,2,\ldots,p\}[/math] e [math]\{1,2,\ldots,p-1\}[/math].

Il collegamento con la Trasformata Discreta di Fourier completa il quadro, mostrando che la stessa struttura utilizzata per risolvere un problema di combinatoria additiva costituisce anche la base matematica di importanti procedure di elaborazione numerica.

È proprio questo il risultato più interessante: non abbiamo soltanto trovato una formula per contare dei sottoinsiemi, ma abbiamo riconosciuto come un problema di combinatoria, attraverso le funzioni generatrici, possa essere interpretato mediante gli strumenti dell’algebra e dell’analisi armonica.

 

📚 Per approfondire: funzioni generatrici, congruenze e teoria dei numeri

Il conteggio dei sottoinsiemi modulo p mette in relazione combinatoria, algebra e aritmetica modulare. Per approfondire gli strumenti matematici utilizzati, puoi proseguire con queste guide, dalla costruzione delle funzioni generatrici allo studio delle congruenze e delle proprietà dei numeri primi.

 

(11)

PubblicitàPubblicità