mercoledì 26 dicembre 2018

Un generatore di numeri primi

“Ehi, guarda, ho scoperto un generatore di numeri primi!”.

“Uhm”.

“Come uhm? Guarda:”.

P(n) = n2 + n + 41

“Uhm”.

“Ma insomma, cosa c'è che non va? P(0) fa 41, che è un numero primo”.

“Questo è vero”.

P(1) fa 43, che è ancora primo”.

“Vero anche questo”.

P(2) fa 47, P(3) fa 53, tutti primi”.

“Certo”.

“E posso andare avanti così, i numeri successivi sono 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033”.

“Molto bene”.

“Quindi sto generando numeri primi”.

“Sì, certo. Hai calcolato P(41)?”.

“Aspetta che faccio i calcoli”.

“Forse non hai bisogno di fare tutti i conti per dire se è primo o no”.

“Perché?”.

“Beh, stai sommando tre numeri: 412 + 41 + 41”.

“Oh”.

“Come vedi, 41 è un fattore comune a tutti e tre”.

“Uffa, risulta un numero composto”.

“Sì, 41 × 43. Prova anche a calcolare P(40)”.

“Questo sarà primo, dai”.

“Prova”.

“Allora: 402 + 40 + 41”.

“Che, volendo, puoi scrivere come 402 + 80 + 1”.

“E perché questa scrittura dovrebbe essere meglio?”.

“Perché è uguale a (40 + 1)2, cioè 412”.

“Oh, è composto anche questo”.

“Già”.

“Ma ci sarà un polinomio che funziona, no?”.

“Cioè un polinomio P(n) a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo?”.

“Uh, mamma mia, che pignoleria. Sì, un polinomio fatto così”.

“Certo, eccotene uno: P(n) = 2”.

“Eh? Ma no, che genera numeri primi diversi!”.

“Allora lo vuoi anche non costante”.

“Sì! Quanto sono noiosi questi Veri Matematici”.

“Capisci che bisogna esser precisi, altrimenti poi non si sa bene quello che si vuole”.

“Va bene, va bene. Esiste un polinomio così?”.

“No”.

“Ma come? Tra tutti gli infiniti polinomi che si possono costruire, non ce n'è nemmeno uno che genera solo numeri primi?”.

“Nemmeno uno”.

“Santo cielo. E perché?”.

“Immagina che ne esista uno, per esempio uno che assuma il valore 43 quando n = 1”.

“Come fa il mio”.

“Esatto: possiamo scrivere che P(1) = 43”.

“Bene”.

“Ora prova a calcolare P(1 + 43k)”.

“Cos'è k?”.

“Un qualunque numero intero”.

“Eh, ma come faccio a calcolare P(1 + 43k) se non so come sia fatto P?”.

“Allora, partiamo dall'inizio. Supponiamo che esista P, che sarà scritto in maniera molto generica in questo modo:”.

P(n) = anxn + an−1xn−1 + … + a1x + a0

“Gulp”.

“Prova a calcolare, adesso, P(1 + 43k)”.

“Vediamo, risulterà una cosa del genere:”.

P(1 + 43k) = an(1 + 43k)n + an−1(1 + 43k)n−1 + … + a1(1 + 43k) + a0

“Bene. Comincia a svolgere”.

“Stai scherzando?”.

“No, ma non devi svolgere tutto tutto. Per esempio, da tutte quelle parentesi del tipo (1 + 43k) elevate a una qualche potenza puoi estrarre il primo termine, che è 1”.

“Eh, ma poi c'è un sacco di altra roba”.

“Certo, cominciamo dal facile: ognuna di quelle parentesi genera sicuramente un 1”.

“Va bene. Ognuno di quegli 1 viene moltiplicato per un coefficiente diverso”.

“E quindi puoi cominciare a scrivere una cosa del genere:”.

P(1 + 43k) = an + an−1 + … + a1 + a0 + (altra roba)

“Non mi sembra una scrittura molto matematica, però va bene”.

“Ti ricordi quanto faceva P(1)?”.

“Abbiamo detto 43”.

“E, però, se sostituisci 1 nel tuo generico polinomio cosa ottieni?”.

“Ah, facile, ottengo an + an−1 + … + a1 + a0”.

“Benissimo. Quindi sai che an + an−1 + … + a1 + a0 = 43”.

“Ah. Ma allora posso scrivere così:”.

P(1 + 43k) = 43 + (altra roba)

“Certo. Adesso concentriamoci sull'altra roba”.

“E come facciamo? Dobbiamo svolgere tutte quelle potenze di binomio, non si finisce più”.

“Non facciamolo. Sarai d'accordo con me se ti dico che lo sviluppo di qualunque potenza del tipo (1 + 43k)n contiene un termine uguale a 1, e tanti altri termini che contengono, almeno una volta, il fattore 43?”.

“Eh, sì, giusto. Tutti i termini dopo il primo 1 contengono le varie potenze di 43k. Non ricordo bene il calcolo dei coefficienti, però”.

“Beh, non importa ai fini dei calcoli che stiamo facendo. Senza conoscere nessuna regola, puoi immaginare di dover calcolare quella potenza in questo modo:”.

(1 + 43k)n = (1 + 43k)(1 + 43k) … (1 + 43k)

“Ah, certo”.

“Quando ti calcoli tutti i prodotti, vedi che c'è un solo caso in cui fai 1×1×…×1, mentre in tutti gli altri casi almeno un termine del tipo 43k lo devi prendere”.

“Giusto, e quindi un 43 c'è sempre”.

“Ottimo. Ed ecco allora che possiamo semplificare ulteriormente il calcolo che stavamo facendo, mettendo in evidenza il fattore comune 43:”.

P(1 + 43k) = 43 + 43(altra roba ancora)

“Bene, e quindi?”.

“E quindi P(1 + 43k) è divisibile per 43”.

“E allora?”.

“E allora non è primo, dunque P(n) non può assumere valori primi per ogni valore di n”.

“Ah!”.

“Volendo essere più precisi, bisognerebbe distinguere due casi nell'espressione P(1 + 43k) = 43 + 43(altra roba ancora)”.

“Quali?”.

“Se la parentesi (altra roba ancora) fosse uguale a 0, allora il risultato sarebbe 43, che è effettivamente un numero primo”.

“Allora potrebbe succedere?”.

“Eh, questo significherebbe che P(1 + 43k) dovrebbe essere uguale a 43 per infiniti valori di k”.

“E questo non è possibile?”.

“Lo è, ma un polinomio che assume infiniti valori uguali è un polinomio costante”.

“Ah, il caso banale P(n) = 43”.

“Già. Se vuoi un polinomio non costante e in grado di generare solo numeri primi, non ce la fai. Non esiste. Naturalmente 43 è solo un esempio, puoi rifare tutta la dimostrazione sostituendo, al posto di 43, un qualsiasi numero p primo. Quindi, niente da fare: non esiste un polinomio P(n) non costante a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo”.

“Oh. Peccato”.

“Già”.

giovedì 6 dicembre 2018

Minacce aliene — Parte 4

“Bene, quindi il problema diventa: se ciascuno dei numeri da 1 a n viene colorato di rosso o di blu, qual è il minimo valore di n per ottenere una progressione aritmetica monocromatica composta da 3, oppure 4, oppure k termini?”.

“Oh, due variabili?”.

“Eh, le cose si complicano”.

“Già mi pare un ottimo risultato affermare che un valore di n che risolve il problema esiste sempre”.

“E hai ragione, questo è il primo passo notevole. Dopo aver dimostrato l’esistenza di un tale n, van der Waerden ha provato anche a stabilirne un valore minimo. Il fatto è che questo valore minimo è enorme, così grande da non poter essere espresso nelle usuali notazioni a cui siamo abituati”.

“Eh? Come è possibile? La notazione scientifica permette di esprimere numeri enormi”.

“Che però sono ridicolmente piccoli se confrontati col numero trovato da van Der Waerden”.

“Incredibile”.

“Per definire il numero ha usato una successione di funzioni, che crescono sempre più velocemente”.

“Uhm, non capisco”.

“Aspetta, partiamo dal semplice. Non avrai difficoltà a immaginare la funzione DOPPIO(x), che raddoppia il suo ingresso”.

“Stai dicendo che DOPPIO(x) = 2x?”.

“Esatto”.

“E c’è bisogno di una funzione apposita?”.

“Per calcolare il doppio, certamente no. Per capire come è fatta la nostra successione di funzioni, invece, sì. Lasciami andare avanti”.

“Ok, vai”.

“Ora definisco la funzione ESPONENTE(x), che calcola il valore di 2 elevato a esponente x”.

“Una funzione esponenziale”.

“Sì, la cosa interessante è che questa funzione è definibile a partire da DOPPIO(x)”.

“In che modo?”.

“Cosa succede se calcoli per x volte il doppio di 1?”.

“Aspetta, allora… se calcolo 1 volta il doppio di 1, ottengo 2, e fin qua è facile. Se calcolo 2 volte il doppio di 1, ottengo 2 per 2, cioè 4. Se calcolo 3 volte il doppio di 1, ottengo 2 per 2 per 2… ah! Certo, se calcolo x volte il doppio di 1, ottengo 2 elevato a x, cioè ESPONENTE(x)”.

“Quindi possiamo dire che ESPONENTE(x) = DOPPIO(DOPPIO(...DOPPIO(1))), dove la funzione DOPPIO compare x volte”.

“Bello, comincio a capire”.

“Ora facciamo un altro passo, definiamo la funzione TORRE(x)”.

“Che immagino sia fatta dall'applicazione di x volte della funzione ESPONENTE”.

“Infatti.”.

“Da dove viene il nome TORRE?”.

“Prova a calcolare TORRE(3)”.

“Vediamo, TORRE(3) = ESPONENTE(ESPONENTE(ESPONENTE(1)))”.

“Ok, quindi partiamo da ESPONENTE(1)”.

ESPONENTE(1) = DOPPIO(1), no?”.

“Certo”.

“E DOPPIO(1) = 2”.

“Giusto anche questo. Quindi TORRE(3) = ESPONENTE(ESPONENTE(2))”.

“Bene, allora adesso devo calcolare ESPONENTE(2), che è uguale a DOPPIO(DOPPIO(1)), cioè DOPPIO(2), cioè 4”.

“Infatti avevamo visto che ESPONENTE(2) calcola 2 elevato a 2, cioè 4”.

“Ah, ecco, vero. Quindi mi rimane da calcolare ESPONENTE(4)”.

“Si capisce meglio se calcoli ESPONENTE(22), applicando direttamente l’esponenziale”.

“Applicando direttamente la definizione di ESPONENTE, verrebbe 222”.

“”Una torre di potenze. Ecco perché questa funzione si chiama TORRE: calcola torri di potenze.

“Non è come fare una potenza di una potenza?”.

“Eh, no, qui non ci sono parentesi: per calcolare una torre di potenze, si parte dall'alto. Per esempio, TORRE(4) è 2222 = 224 = 216, mentre ((22)2)2, che è la cosiddetta potenza di potenza, è uguale a 28.

“Ok, ci sono”.

“Ora andiamo avanti, definiamo una nuova funzione, WOW(x). Ti anticipo che WOW non ha nessun significato se non quello di stupore, per quanto veloce cresce questa funzione”.

“Non ci posso credere”.

“Eh, in mancanza di nomi migliori… I numeri calcolati da WOW sono enormi. Naturalmente, WOW(x) è definita come TORRE(TORRE(…TORRE(1))), dove la funzione TORRE compare x volte”.

“Gulp. Chissà quanto vale WOW(4)”.

“Un numero enorme. WOW(4) = TORRE(TORRE(TORRE(TORRE(1))))”.

“Uhm, TORRE(1) è uguale a 2, fin qua è facile. Quindi mi rimane da calcolare TORRE(TORRE(TORRE(2)))”.

“Anche TORRE(2) è facile, no?”.

“Certo, è uguale a 22, cioè 4”.

“Ok, quindi ora devi calcolare TORRE(TORRE(4))”.

TORRE(4) è una torre di 2 composta da 4 elementi, cioè 2222, che è uguale a 65536”.

“Bene, ultimo passo, devi calcolare TORRE(65536)”.

“Argh”.

“O anche wow!”.

“Una torre di potenze composta da 65536 esponenti, una cosa impossibile da immaginare”.

“Esattamente”.

“E questo numero è quello trovato da van der Waerden?”.

“Oh, no, questo è ancora piccolo se confrontato con quello”.

“Cosa?”.

“Eh, sì. Per arrivare al numero trovato da van der Waerden, occorre immaginare questa successione di funzioni:”.

DOPPIO(1)
ESPONENTE(2)
TORRE(3)
WOW(4)
eccetera

“Ogni volta applichiamo tante volte la funzione precedente?”.

“Esattamente”.

“E dopo WOW che funzioni ci sono?”.

“Non sono stati definiti nomi per le funzioni successive. Sai come si fa, si definisce una regola e poi si va avanti così. Per scrivere i termini successivi si usa un nome generico, che è ACKERMANN”.

“Questo è un nome proprio, suppongo?”.

“Esatto, dal nome di chi l’ha definita. Una volta capito che a ogni passo si deve applicare la funzione precedente un certo numero di volte, possiamo definire la funzione ACKERMANN in questo modo:”.

ACKERMANN(1) = DOPPIO(1)
ACKERMANN(2) = ESPONENTE(2)
ACKERMANN(3) = TORRE(3)
ACKERMANN(4) = WOW(4)
eccetera

“Quell'eccetera fa paura”.

“Ed eccoci arrivati alla soluzione del problema proposto da van der Waerden”.

“Se ciascuno dei numeri da 1 a n viene colorato di rosso o di blu, qual è il minimo valore di n per ottenere una progressione aritmetica monocromatica composta da k termini?”.

“E la risposta è: ACKERMANN(k)”.

“Quindi, tornando al quesito iniziale, quello delle progressioni aritmetiche composte da 3 numeri dello stesso colore, siamo sicuri di trovarne se prendiamo i numeri che vanno da 1 a ACKERMANN(3), giusto?”.

“Giusto”.

“E ACKERMANN(3) è uguale a TORRE(3), cioè 16. Uhm, non avevo dimostrato che anche solo prendendo i numeri da 1 a 9 troverò sempre una progressione aritmetica monocolore?”.

“Sì, certo. La stima ACKERMANN(k) è una condizione sufficiente per essere sicuri di trovare la progressione monocolore. Non è detto che, con ulteriori studi, non si possa migliorare la stima. Anzi, un miglioramento è già stato fatto: nella dimostrazione originale di van der Waerden compare il numero ACKERMANN(k), ma successivamente, nel 1987, il matematico israeliano Sharon Shelah ha dimostrato che ci si può fermare a WOW(k)”.

“Ah, ecco. Rimane comunque un numero colossale”.

“E, per quanto riguarda il quesito iniziale, ancora più inutile: WOW(3) è uguale a 65536”.

“Se k aumenta, però, WOW(k) rimane a un livello inferiore rispetto a ACKERMANN(k), vero?”.

“Esatto. Sappi che Graham, un altro matematico che ha lavorato alla teoria di Ramsey, ha offerto un premio di 1000 dollari per chiunque sia in grado di dimostrare che, al posto di WOW(k), si può usare TORRE(k). O a chi sia in grado di dimostrare il contrario, cioè che TORRE(k) è un numero troppo basso”.

“Anche in questo campo, quindi, ci sono molti problemi aperti”.

“Già. Quella di Ramsey è una teoria affascinante, proprio perché si occupa di trovare strutture ordinate all'interno di strutture apparentemente casuali. Un articolo divulgativo di Graham e Spencer, comparso su Le Scienze nel 1990, si concludeva con questa domanda: oggi, grazie alla teoria di Ramsey, siamo in grado di riconoscere con facilità le costellazioni del cielo notturno. Quali configurazioni potremmo mai trovare in insiemi che sono ACKERMANN(9) volte più grandi?”.

“Speriamo di non trovare alieni cattivi, però”.



Questa è l'ultima parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017. La prima parte è qua, la seconda qua, la terza qua.