Mathematics for Innovation, INCA-ABACO

Luca Turconi – Moxoff srl.

incontro8marzoblogNon può esserci innovazione senza ricerca, ma non si può chiedere a un ricercatore di ragionare in termini industriali. Moxoff, spinoff del Politecnico di Milano formato da ingegneri specializzati nello sviluppo e nell’applicazione industriale di modelli e algoritmi matematici, è l’anello di congiunzione capace di valorizzare i risultati della ricerca matematca trasformandoli, attraverso un costante trasferimento tecnologico e di know how, in soluzioni innovative utilizzabili in modo affidabile e veloce in ogni settore industriale: dall’industria manifatturiera ai servizi, dall’energia al medicale, dal no profit all’alimentare, fino allo sport.

Primo degli incontri del progetto INCA-ABACO. Tutti gli studenti di corsi di laurea a tema scientifico sono i benvenuti! (ma anche gli umanisti curiosi sono grandemente apprezzati)

Ulteriori informazioni su: http://www.mat.uniroma2.it/~locatell/inca-abaco/

Buon 3/14 alle 9.26.53 (PM)!

Ecco un paio di modi per approssimare il valore di \pi.

Partiamo da un classico, ma non troppo, che è detta serie di Leibniz-Gregory-Madhava (a seconda delle latitudini e delle epoche). Ovvero lo sviluppo in serie di potenze della funzione \arctan(x), per cui si ha che:

(1)   \begin{equation*} \pi = 4 \sum_{k=0}^{+\infty} \frac{(-1)^k}{2k+1}. \end{equation*}

Che possiamo calcolare e stampare con il seguente codice OCTAVE.

printf('Approssimazione n° 1\n');
N = input('Sommare fino a N = ');
piapp1 = 0;
figure(1)
for k=0:N
  piapp1 = piapp1 + 4*((-1)^k)/(2*k+1);
  subplot (211);
  hold on
  plot(k,piapp1,'*');
end
plot(0:0.1:N,pi*ones(1,length(0:0.1:N)),'k--');
ylabel('Valore approssimato di \pi');
xlabel('Numero di termini della serie');
title(sprintf('Approssimazione n° 1, N = %d',N));
hold off

Che ha una convergenza molto, molto, lenta … per vederlo servono i numeri di Eulero, ma si può comunque fare qualche esperimento con il codice (un po’ goffo sotto molti punti di vista) riportato sopra.

Possiamo scegliere un’altra via, se sappiamo che

(2)   \begin{equation*} \int \sqrt(1-t^2)dt = \frac{1}{2}\left(\sqrt{1-t^2}+\arcsin(t)\right) + C, \end{equation*}

abbiamo che

(3)   \begin{equation*} \pi = 4 \int_{0}^{1} \sqrt{1-t^2}dt. \end{equation*}

Cosa ce ne facciamo? Be’ possiamo approssimare l’integrale con la regola dei trapezi … Ovvero discretizziamo l’intervallo [0,1] in N+1 punti equispaziati \{x_k\}_{k=1}^{N+1}, ovvero fissiamo una griglia su [0,1] di ampiezza h = (1-0)/N, per cui l’approssimazione dell’integrale diventa:

(4)   \begin{equation*} \pi = 4 \int_{0}^{1} \sqrt{1-t^2}dt \approx \frac{1}{2N} \sum_{k=1}^N \left(\sqrt{1-(x_{k+1})^2}-\sqrt{1-(x_k)^2}\right). \end{equation*}

Si lo so, bisognerebbe pure sostituire quelle radici con un’approssimazione, ma facciamo finta di averlo fatto, o di averlo delegato ad OCTAVE.

printf('Approssimazione n° 2\n');
M = input('Numero dei punti in cui suddividere [0,1], M = ');
for h=1:M
  x = 0:1/h:1;
  y = sqrt(1-x.^2);
  piapp2 = 4*trapz(x,y);
  subplot (212);
  hold on
  plot(h,piapp2,'*');
end 
plot(0:0.1:M,pi*ones(1,length(0:0.1:M)),'k--');
ylabel('Valore approssimato di \pi');
xlabel('Numero di intervalli di [0,1]');
title(sprintf('Approssimazione n° 2, M = 1,...,%d',M));
hold off

Il risultato dei due codici precedenti è questo:

 

Ah già, buon piday!


Codice dell’esempio: pigreco.m.tar.gz.

L’immagine di copertina viene dall’illustrazione all’inizio degli Elementi di Euclide nella traduzione di Adelardo di Bath (fonte: Wikipedia/Wikimedia).

Numeri primi – #2

Non solo la matematica è reale, ma è l’unica realtà.
Martin Gardner

Dunque dunque, con il numero 1 avevamo messo da parte alcune dimostrazioni dell’infinità dei numeri primi. A questo punto, direi, che quel materiale ha fermentato abbastanza e possiamo aggiungere altra carne al fuoco (apprezzare la doppia metafora non coerente, con slittamento banale a vanvera).

Dopo la dimostrazione di Erdös, facciamo un salto indietro nel tempo e torniamo ad una dimostrazione in qualche modo classica, prelevata dalle idee di Pierre de Fermat. Per farlo cominciamo a dare la seguente definizione:

Def 3. Per \forall n \in \NN definiamo Numero di Fermat l’intero positivo della forma:

(1)   \begin{equation*} F_n = 2^{2^n} + 1 \end{equation*}

Aprendo una piccola cornice storica, Fermat ipotizzo che tutti i numeri di questa forma fosse primo, ma un matematico a caso, Eulero, tanto per dirne uno, osservò che:

  • Per n = 0, F_0 = 3, è primo!
  • Per n = 1, F_1 = 5, è primo!
  • Per n = 2, F_2 = 17, è primo!
  • Per n = 3, F_3 = 257, è primo!
  • Per n = 4, F_4 = 65537, è primo!
  • Per n = 5, F_5 = 4294967297, non è primo neanche per niente: F_5 = 641 \cdot 6700417

Chiusa la parentesi storica, torniamo al nostro problema ed enunciamo (e dimostriamo) il seguente teorema:

Teorema [Goldbach]. \forall n,n' \in N con n \neq n' si ha \operatorname{M.C.D.}(F_n,F_{n'})=1, ovvero due numeri diversi di Fermat sono sempre coprimi.

Dimostrazione. Proviamo in primo luogo, per induzione, che vale la relazione:

(2)   \begin{equation*} F_n = F_0 \cdot \ldots \cdot F_{n-1} + 2 \;\; \forall n \geq 1 \end{equation*}

per n = 1 abbiamo che:

    \begin{equation*} F_1 = 2^{2^1} + 1 = 5 = 2^1 + 1 + 2 = 5 . \end{equation*}

questo prova la base, supponiamo ora che sia vera la relazione per n e dimostriamolo per n+1, cioè vogliamo provare che:

    \begin{equation*} F_0 \cdot F_1 \cdot F_2 \cdot \ldots \cdot F_{n-1} \cdot F_n + 2 = F_(n+1). \end{equation*}

Per farlo poniamo:

    \begin{eqnarray*} x = F_0 \cdot F_1 \cdot F_2 \cdot \ldots \cdot F_{n-1}\\ y = F_0 \cdot F_1 * \cdot \ldots \cdot F_(n-1) \cdot F_n \end{eqnarray*}

Ci siamo dunque ridotti a provare che:  y + 2 = F_{n+1}. Osserviamo immediatamente che, per l’ipotesi induttiva si ha che:  y = x (x+2). E dunque ci siamo ridotti a mostrare che:  x (x+2) + 2 = F_{n+1}. Adesso, applicando di nuovo l’ipotesi induttiva abbiamo che:  x = F_{n - 2}, allora:

    \begin{equation*} \begin{split} x  (x+2) + 2 = & [(F_{n - 2})  ((F_{n - 2} + 2)] + 2 = \\ = & [(F_{n - 2}  F_n] + 2 =  \\ = & (F_n)^2 - 2F_n + 2 = \\ = & (2^{2^n} + 1)  (2^{2^n} + 1) - 2  (2^{2^n} + 1) + 2  =  \\ = & 2^{2^n}  2^{2^n} + 2\cdot 2^{2^n} + 1 - 2 \cdot 2^{2^n} - 2 + 2 = \\ = & 2^{2^n} \cdot 2^{2^n} + 1 = 2^{2^n + 2^n} + 1 = \\ = & 2^{2\cdot (2^n)} + 1 = \\ = & 2^{2^{n+1}} + 1 = F_{n+1} \end{split} \end{equation*}

Con questo abbiamo praticamente completato la dimostrazione, ora ci resta solo da supporre,per assurdo, che per 0 \leq i < j \exists \; a > 1 tale che a | F_i e a | F_j, per l’identità che abbiamo appena provato si ha che a deve necessariamente dividere F_0\cdot \ldots \codt F_{j-1}, sia F_j, cioè deve dividere la loro differenza, ovvero a deve dividere 2, ma questo implica che a = 2, ma questo è assurdo! I numeri di Fermat sono, chiaramente, tutti dispari.

Q.E.D.

A questo punto la dimostrazione dell’infinità dei primi è presto ottenuta:

Dimostrazione 3. Per il teorema fondamentale dell’aritmetica abbiamo che \forall n \in N esiste un primo p_n | F_n e per il teorema di Goldbach, questo p_n non divide nessun F_{n'} per n \neq n', dunque il numero dei p_n e maggiore o uguale del numero degli F_n, ma questi sono infiniti, dunque abbiamo concluso.

Q.E.D.

Proseguiamo con l’ultima dimostrazione dell’infinità dei primi di questa carrellata. Questa è a base di topologia ed è stata proposta da Harry Fürstenberg nel 1955 [1], di tutte quelle viste è l’unica che probabilmente richiede strumenti di matematica avanzata (diciamo extra-liceo):

Dimostrazione 4. Sia \ZZ l’insieme dei numeri interi, positivi, negativi e lo 0. Consideriamo gli elementi a,b \in \ZZ con b>0 e definiamo gli insiemi a due indici:

    \begin{equation*} N_{a,b} = \{ a + nb \;|\; n \in \ZZ\} \end{equation*}

Osserviamo immediatamente che N_{a,b} è una progressione aritmetica che si sviluppa in ambo i versi e che, inoltre, \forall b si ha che a \in N_{a,b}, il che dovrebbe iniziare a ricordarci l’idea di un intorno in senso topologico, infatti abbiamo che ogni insieme del tipo N_{c,d} \supset N_{a,b} contiene ancora a ed è dunque ancora un suo intorno. Inoltre ogni intorno di a contiene un intorno di a che è anche intorno di ognuno dei suoi punti. Resta solo da verificare che l’intersezione di due intorni di un medesimo a è ancora un intorno di a, ma anche questo è semplice da verificarsi, infatti dati a,b,c \in \ZZ con b,c > 0 abbiamo che:

    \begin{equation*} N_{a,b} \cap N_{a,c} = N_{a,\operatorname{m.c.m.}(b,c)} \end{equation*}

Possiamo quindi costruire su \ZZ la seguente topologia:

    \begin{equation*} \mathcal{T} = \{U \subseteq \ZZ \,|\, \exists a \in U, \; b \in \ZZ_{>0} \; N_{a,b} \subseteq U \}\cup\emptyset \end{equation*}

di cui osserviamo le due seguenti proprietà:

  1. Ogni insieme aperto U \neq \emptyset è infinito.
  2. Ogni insieme aperto U è anche chiuso, infatti:

        \begin{equation*} N_{a,b} = \ZZ \setminus \bigcup_{i=1}^{b-1}N_{a+i,b} \end{equation*}

    cioè è chiuso poiché complementare di un aperto (dell’unione di aperti …).

possiamo a questo punto concludere, infatti per il teorema fondamentale dell’aritmetica ogni intero, ad eccezione di \pm 1 e 0 ha dei fattori primi. Dunque ogni intero è contenuto in uno o più N_{0,p} con p primo. Cioè abbiamo ottenuto l’identità:

(3)   \begin{equation*} \ZZ \setminus \{1,-1\} = \bigcup_{p \text{ primo}}N_{0,p} \end{equation*}

Se l’insieme dei numeri primi fosse, per assurdo, finito l’insieme a destra dell’uguaglianza sarebbe chiuso, poiché unione finita di chiusi (proprietà 2), dunque l’insieme \{-1,1\} sarebbe aperto, ma questo contraddice la (proprietà 1). L’assurdo deriva dall’aver supposto finito l’insieme dei numeri primi.

Q.E.D.

E pure questa puntata è finita. Sto meditando su un eventuale “Numeri primi – #3“, ma ancora non ho raggiunto una decisione. Prendiamo pure questo come mezzo annuncio e salutiamoci alla prossima!

Bibliografia.

  1. Harry Fürstenberg, On the infinitude of primes., Amer. Math. Monthly 62 (5): 353 (1955). DOI:10.2307/2307043.