Il crivello di Eratostene e la definizione formale di crivello

Prerequisiti:

• Definizione di numero primo
• Il Teorema di Chen: enunciato e introduzione alla dimostrazione

Nell’articolo precedente abbiamo visto che la dimostrazione del Teorema di Chen si basa sulla teoria dei crivelli. Ma che cos’è un crivello? In questo articolo lo spiegheremo basandoci sull’esempio più famoso di crivello, quello di Eratostene. Esso permette di rispondere a una semplice domanda: dato un numero intero N \geq 2, quali sono i numeri primi minori o uguali di N?

Da una proprietà dei divisori al crivello di Eratostene

Per trovare i numeri primi minori o uguali di N, è sufficiente avere un criterio per stabilire se un numero è primo o no: basterebbe infatti applicare tale criterio a tutti i numeri interi compresi tra 2 ed N e segnare man mano quali sono primi.
Ci sono diversi criteri per stabilire se un numero è primo, tutti sempre più laboriosi al crescere del numero preso in considerazione, ma quello più semplice e famoso è la seguente Proprietà:

Per capire meglio questa Proprietà, consideriamo l’enunciato equivalente che si ottiene invertendo l’implicazione:

La dimostrazione è molto semplice, ma importante. Consideriamo un numero N maggiore di 1 non primo e supponiamo per assurdo che non abbia divisori primi minori o uguali di \sqrt{N}. Allora N, non essendo primo, deve avere almeno due divisori primi p e q. Ma, per quanto ipotizzato, entrambi questi divisori sarebbero maggiori di \sqrt{N}, quindi N \geq pq \gt \sqrt{N} \sqrt{N} = N, da cui l’assurdo N \gt N. Quindi l’ipotesi iniziale deve essere falsa, cioè N deve avere almeno un divisore primo minore o uguale di \sqrt{N}.

Supponiamo ora di aver fissato un numero di partenza N e di voler trovare tutti i numeri primi minori di esso. Potremmo considerare uno alla volta tutti gli interi a partire da 2 fino a N, applicando la Proprietà C.1 a ciascuno di essi, cioè provando a dividerlo per tutti i primi minori o uguali della propria radice quadrata. Potremmo cioè applicare il seguente algoritmo:

1. Poni P := \{\}
2. Per ogni intero n compreso tra 2 ed N:
   1. Poni p := 2 e d := 1
   2. Se p \leq \sqrt{n} e d = 1:
      1. Se n è divisibile per p, poni d := p
      2. Altrimenti, poni p := \textrm{successivo elemento di }P
      3. Torna al passo b.
   3. Se d = 1, aggiungi p all’insieme P
3. Restituisci P

Possiamo visualizzare il comportamento dell’algoritmo mediante una tabella, avente come righe i numeri primi minori o uguali di \sqrt{N} e come colonne i numeri compresi tra 2 ed N (ossia gli n dell’algoritmo). Ad esempio, se N = 32 avremo la tabella seguente:

Possiamo immaginare che l’algoritmo legga la tabella colonna per colonna, da sinistra verso destra. Per ciascuna colonna, esso verifica se il numero della colonna è divisibile per il numero di ciascuna riga, fintanto che il numero della riga è minore o uguale della radice quadrata del numero della colonna. Appena trova un numero di riga che divide il numero della colonna, o quando le righe da esaminare sono finite, passa alla colonna successiva.
Se coloriamo in grigio le celle corrispondenti alle prove di divisione effettuate e mettiamo un trattino nei casi in cui c’è divisibilità, otteniamo la seguente rappresentazione:

Abbiamo ottenuto una tabella in cui, se il numero di una colonna non è primo, la colonna contiene un trattino sulla riga corrispondente al fattore primo più piccolo del numero; altrimenti, se il numero della colonna è primo, non contiene trattini.

L’idea del crivello di Eratostene consiste nell’invertire l’ordine di lettura della tabella, ossia leggerla per righe, invece che per colonne. In pratica si considerano i numeri primi uno alla volta, partendo dal 2 che è l’unico supposto noto all’inizio, e costruendo man mano gli altri; per ciascuno di essi si segnano le colonne i cui numeri sono multipli del numero primo considerato e maggiori di esso; così facendo, alla fine resteranno senza segni solo le colonne il cui numero è primo. L’algoritmo è il seguente:

1. Poni A := \{2, 3, 4, \ldots, N\}
2. Poni p := 2
3. Se p \leq \sqrt{N}:
   1. Per ogni intero n \in A maggiore di p:
      1. Se n è divisibile per p, eliminalo n da A
   2. Poni p := \textrm{successivo elemento di }A
   3. Torna al passo 3.
4. Restituisci A

Questo algoritmo può sembrare molto diverso dal precedente, ma in realtà genera esattamente la stessa tabella. Infatti, se ad esempio N = 32:

• Inizialmente p = 2, per cui l’algoritmo verifica, per ciascun elemento di A = \{2, \ldots, N\}, se esso è divisibile per 2 e maggiore di 2: in caso affermativo lo elimina dall’insieme A. Rappresentando la riga del 2, colorando in grigio le celle corrispondenti alle prove di divisione effettuate (cioè una per ciascun elemento di A) e mettendo un trattino nelle celle il cui numero di colonna risulta divisibile per 2 e maggiore di 2 (condizioni a. e i. dell’algoritmo), si ottiene:
  

  	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
  2			–		–		–		–		–		–		–		–		–		–		–		–		–		–		–

  La riga di questa tabella è praticamente identica alla prima riga della tabella precedente: l’unica differenza è che ora si sono fatti due test di divisione in più, ma i trattini sono gli stessi.
  A questo punto l’insieme A sarà ridotto ai soli numeri delle colonne che non contengono un trattino, ossia \{2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31\}.

• L’algoritmo prosegue ponendo p := 3 e passando in rassegna gli elementi del nuovo insieme A maggiori di 3, quindi solo le colonne da 4 in poi che non hanno ancora un trattino. Creando la riga del 3, colorando in grigio le celle di tali colonne e segnando ancora con i trattini le divisibilità, si ottiene:
  

  	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
  2			–		–		–		–		–		–		–		–		–		–		–		–		–		–		–
  3								–						–						–						–

  Anche questa riga è praticamente identica alla corrispondente della tabella precedente, al netto di qualche test di divisibilità in più.
  A questo punto dall’insieme A saranno stati eliminati anche i numeri di colonna che hanno un trattino sulla nuova riga, ossia 9, 15, 21 e 27, per cui l’insieme diventerà \{2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31\}.

• Infine l’algoritmo pone p := 5 (l’ultimo elemento di A minore o uguale della radice quadrata di 32) e passa in rassegna gli elementi dell’insieme A maggiori di 5, ossia 7, 11, 13, 17, 19, 23, 25, 29 e 31. Sulla riga del 5, le celle con questi numeri di colonna saranno in grigio e quelle divisibili per 5 conterranno un trattino:
  

  	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
  2			–		–		–		–		–		–		–		–		–		–		–		–		–		–		–
  3								–						–						–						–
  5																								–

  Anche quest’ultima riga coincide con la corrispondente della tabella precedente, al netto di qualche test di divisibilità in più.
  A questo punto l’insieme A diventa \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}. Ora l’elemento successivo di A è 7, che però è maggiore di \sqrt{32}, quindi il passo 3 dell’algoritmo termina e, nel passo 4, l’algoritmo restituisce l’insieme A, che a questo punto è effettivamente l’insieme dei numeri primi minori o uguali di 32. Essi corrispondono, come prima, coi numeri di colonne prive di trattini.

La definizione formale di crivello

Nel paragrafo precedente abbiamo visto il crivello di Eratostene, che è l’esempio più famoso di crivello. Ma cos’è esattamente un crivello, in termini generali?
A questo punto, conoscendo il crivello di Eratostene, si potrebbe pensare che un crivello sia un algoritmo, simile a quelli che abbiamo visto nel paragrafo precedente. In effetti, storicamente è stato proprio così. Il nome stesso crivello è sinonimo di setaccio, rappresenta cioè un attrezzo formato da un telaio con lamine perforate che lasciano passare solo oggetti di una determinata dimensione:

Utilizzando questa metafora in matematica, possiamo dire che un crivello è un test di divisibilità per un determinato insieme di numeri primi, dove gli oggetti inseriti, cioè dati in input, sono gli elementi di un certo insieme di partenza (quello che nel paragrafo precedente abbiamo indicato con A): quelli divisibili per uno dei numeri primi prescelti restano bloccati, mentre gli altri passano oltre, cioè vengono restituiti in output.
Quest’immagine, per quanto possa essere utile a livello intuitivo, in realtà ha poco a che fare con la teoria dei crivelli, ossia la teoria matematica che studia questi strumenti. Essa infatti non ha un’impostazione di tipo algoritmico, ma di tipo numerico. Dal punto di vista matematico un crivello non è definito come un algoritmo, perché ciò che conta è il risultato finale, che non dipende dall’algoritmo utilizzato. Nella teoria dei crivelli, un crivello viene inteso invece come una funzione, detta funzione di crivello, che, partendo da un insieme di numeri naturali e da alcuni parametri, fornisce il risultato voluto:

Anche se la definizione non indica quali numeri primi debba contenere l’insieme \mathcal{P}, qusi sempre esso è l’insieme di tutti i numeri primi, di solito indicato col simbolo \mathbb{P}. In tal caso, calcolare la funzione di crivello significa rispondere alla domanda: “Quanti elementi di A non sono divisibili per nessun numero primo minore di z?”. Gli studiosi di teoria dei numeri cercano di rispondere in modo approssimato a questa domanda, limitando superiormente o inferiormente la funzione di crivello.
Se \mathcal{P} non contiene tutti i numeri primi minori di z (ad esempio \mathcal{P} = \{2, 3, 7\}, senza il 5, con z = 8), la domanda diventa leggermente più complessa, perché in questo caso si cercano gli elementi di A che non sono divisibili per nessun numero primo minore di z limitatamente ai numeri primi presenti nell’insieme \mathcal{P}, invece che tutti. Per ragioni didattiche, la definizione di funzione di crivello è stata enunciata in questi termini più generali, come la si trova in molti testi, ma d’ora in poi supporremo sempre che \mathcal{P} = \mathbb{P}, dato che la difficoltà del problema non cambia rispetto al caso più generale.

Così come è espressa nella Definizione C.1, la funzione di crivello non è calcolabile facilmente; possiamo migliorare questo aspetto scrivendola in una forma puramente algebrica. Vale infatti la seguente Proprietà:

È molto semplice dimostrare che questa scrittura è equivalente alla definizione vista in precedenza, ma tale dimostrazione è importante per chiarire la notazione. La formula (1) dice in sostanza di sommare un “1” ogni volta che sono soddisfatte entrambe le condizioni:

• a \in A
• \mathrm{MCD}(a, P(z)) = 1

Cioè dobbiamo sommare un “1” per ogni elemento di A coprimo con P(z). Ma P(z) è il prodotto dei numeri primi minori di z; quindi, se un numero è coprimo con P(z), allora non può essere divisibile per nessun numero primo minore di z. Allora gli elementi che soddisfano le condizioni a \in A e \mathrm{MCD}(a, P(z)) = 1 sono proprio quelli dell’insieme \{ a \in A \mid a \textrm{ non è divisibile per nessun elemento di }\mathbb{P}\textrm{ minore di }z \}. La formula (1) ci dice che dobbiamo contare 1 per ciascuno di questi elementi e sommare il tutto, per cui alla fine otterremo il conteggio degli elementi stessi, ossia S(A, \mathbb{P}, z), secondo la Definizione C.1.

Il crivello di Eratostene come funzione di crivello

In questo articolo siamo partiti introducendo il crivello di Eratostene dal punto di vista algoritmico, ma poi abbiamo visto che in generale un crivello si può intendere come una funzione, che esprime il concetto di crivello a livello numerico/insiemistico. Allora anche il crivello di Eratostene, essendo appunto un crivello, dovrebbe essere esprimibile come funzione, oltre che come algoritmo. Questo in realtà, volendo essere rigorosi, non è vero. Il crivello di Eratostene originale (quello che abbiamo illustrato nel paragrafo precedente) non è esprimibile come funzione di crivello; se vogliamo esprimerlo in tal modo, dobbiamo modificarlo leggermente. Vediamo perché.

Riprendiamo l’esempio di N = 32. Il crivello di Eratostene, partendo dall’insieme A := \{2, 3, 4, \ldots, 32\}, restituisce l’insieme dei numeri primi minori o uguali di 32, ossia \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}. Allora, se il crivello di Eratostene fosse una funzione di crivello, dovrebbero esistere un insieme di numeri primi \mathcal{P} e un numero reale z \gt 1 tali che:

Ma, se vogliamo che il risultato non sia frutto di una coincidenza, dobbiamo assicurarci che la funzione si comporti come l’algoritmo, cioè che prenda in considerazione gli stessi insiemi per effettuare il conteggio degli elementi. Quindi dovremmo avere che:

Chiaramente \mathcal{P} e z dovrebbero essere scelti in modo che i numeri primi considerati siano 2, 3 e 5, cioè gli stessi dell’algoritmo. Una possibile scelta sarebbe, ad esempio, \mathcal{P} = \mathbb{P} e z = 6 (z = 5 non va bene perché la funzione di crivello considera i numeri primi strettamente minori di z, quindi se fosse z = 5 essa non considererebbe il 5). Con questa scelta, o con scelte equivalenti, si avrebbe però che:

L’insieme ottenuto sarebbe identico al risultato del crivello di Eratostene senza 2, 3 e 5, ossia senza i primi utilizzati nel crivello. Questa differenza dipende dal fatto che il crivello di Eratostene, per ogni primo p considerato, elimina solo i multipli di p maggiori di se stesso (v. passo a. dell’algoritmo), mentre la funzione di crivello elimina tutti i numeri divisibili per p, compreso p stesso. Quindi, se vogliamo esprimere il crivello di Eratostene come funzione di crivello, dobbiamo modificarlo in questo modo:

1. Poni A := \{2, 3, 4, \ldots, N\}
2. Poni p := 2
3. Se p \leq \sqrt{N}:
   1. Per ogni intero n \in A:
      1. Se n è divisibile per p, eliminalo da A
   2. Poni p := \textrm{primo elemento di }A
   3. Torna al passo 3.
4. Restituisci A

Rispetto a prima, nel passo a. abbiamo tolto la dicitura “maggiore di p” e nel passo b. abbiamo sostituito “successivo elemento di A” con “primo elemento di A“. Infatti, partendo da 2 che inizialmente è il primo elemento di A, ogni p preso in considerazione viene subito eliminato da A essendo divisibile per se stesso, per cui, arrivati al passo b., tale p non appartiene più ad A. Ma non ha senso parlare dell’elemento di A successivo a un elemento non più esistente; l’elemento che nel primo algoritmo era il successivo, in questo algoritmo è il nuovo primo elemento di A.

Si può dimostrare che questo algoritmo restituisce l’insieme dei numeri primi contenuti in A maggiori di \sqrt{N}. Nel caso di N = 32, restituisce l’insieme \{7, 11, 13, 17, 19, 23, 29, 31\}.

Quando si parla di crivello di Eratostene in teoria dei crivelli, ci si riferisce a quest’ultima versione, non a quella originale ideata dal matematico greco. Ciò potrebbe sembrare strano, ma bisogna considerare che la teoria dei crivelli è stata ideata molti secoli dopo; inoltre, di solito, nelle teorie si effettuano delle semplificazioni, ed è più semplice eliminare tutti i multipli di p senza distinzioni, piuttosto che eliminarli tutti con l’eccezione di p. Chiaramente c’è un’ambiguità perché entrambe le versioni sono chiamate “crivello di Eratostene”, ma generalmente risulta chiaro dal contesto a quale delle due ci si riferisce.

La funzione di crivello corrispondente alla seconda versione del crivello di Eratostene è la seguente: