Congettura

Cos’è una congettura? È una proposizione che si presume vera ma non si è in grado di dimostrare rigorosamente. Le congetture affascinano perché funzionano per tutti i tentativi che si fanno per verificarla, cioè per trovare una dimostrazione di ciò che dicono. E questa loro non dimostrabilità le avvolge di mistero. Facciamo un piccolo recap.

Assiomi o postulati

Sono delle affermazioni così elementari che non possono essere dedotte da affermazioni ancora più semplici. A volte non sembrano molto elementari però si decide di arrestare il processo deduttivo perché non porterebbe più da nessuna parte se non girare il discorso utilizzando dei sinonimi. Ad esempio Assioma I della geometria euclidea:

Tra due punti qualsiasi è possibile tracciare una e una sola retta.

Qui si potrebbe obiettare “cos’è la retta? cos’è un punto? Il mio professore di Analisi I, Ezio Stagnaro, ci fece questo esempio:

Potete sostituire alla parola “punto” la parola “scarpe” e alla parola “retta” la parola “uomo” e verificare se detto così l’assioma funziona. Se poi riuscite a far funzionare l’analogia per tutti gli altri assiomi, vi accorgerete che punti e rette non sono oggetti in sé ma possono essere istanziati nella realtà in qualunque modo questo consenta di non pervenire a contraddizioni.

Proposizioni e teoremi

A partire dai fatti elementari (assiomi) costruiamo affermazioni più complesse (“La somma degli angoli interni di un triangolo è congruente con un angolo piatto” per rimanere nella Geometria Euclidea) che fanno discedere un fatto complesso (tesi) ad un certo numero finito di premesse (ipotesi). Il processo deduttivo che porta dalle ipotesi alla tesi senza saltare passaggi è detto dimostrazione del teorema. Se un teorema ha una dimostrazione l’affermazione è vera all’interno del sistema assiomatico e non può essere negata.

… e le congetture?

Se non riusciamo a trovare la dimostrazione siamo in una terra di mezzo. La proposizione è verificata in un numero più o meno grande di casi, sembra tenere, ma siccome non si possono provare tutti gli infiniti casi, non possiamo essere certi che funzioni sempre. Questa sicurezza ce la può dare solo una dimostrazione rigorosa.

Gli attacchi che i matematici sferrano verso queste proposizioni “maledette” a volte hanno qualcosa di epico, perché sono in grado di resistere per secoli all’assalto di menti sopraffine.

Per citarne un’altra di celebre, oltre a quella di Collatz, basti la congettura di Riemann, secondo la quale gli zeri non banali della funzione Zeta di Riemann hanno tutti parte reale uguale a 1/2. Anche di questa non si è ancora trovata una dimostrazione, benché fosse uno dei problemi inseriti da David Hilbert nell’elenco dei 23 problemi ancora da risolvere alla fine del XIX secolo (il problema numero 8, per la precisione).

Non è nemmeno provato che queste proposizioni non si possono dimostrare, almeno ci si metterebbe l’anima in pace. La proverbiale “pietra sopra” ad esempio è stata messa in un caso famoso: dopo secoli di tentativi da parte di matematici più o meno bravi di fornire una dimostrazione, si è trovato che l’assioma 5 della geometria euclidea – l’assioma delle parallele – non si poteva dimostrare come se fosse un teorema ma che anzi si poteva anche negare, addirittura in due modi, originando due nuovi sistemi indpendenti: le due geometrie non euclidee, quella di Riemann e quella di Bolyai/Lobacevskij.

In generale è stato dimostrato da Kurt Gödel che questo assioma è un punto debole come un punto debole ce l’ha qualsiasi altro sistema assiomatico (teoremi di incompletezza). Quindi in questo Gödel ha messo una pietra sopra sul fatto che in ogni sistema assiomatico ci sia un’affermazione che non può essere né dimostrata né negata all’interno dello stesso sistema.

Infatti si costruisce un altro sistema con una negazione del V postulato che ad esempio generi la geometria iperbolica e anche all’interno di questa non è dimostrabile né confutabile. Lo stesso vale per la geometria ellittica.

Non c’è niente da fare. Però questo teorema ha fatto finalmente in modo che la questione si potesse considerare chiusa una volta per sempre.

Ma in questo caso invece, come disse Paul Erdős, matematico ungherese, a proposito della congettura di Collatz

“La matematica non è ancora pronta per risolvere problemi del genere”

Paul Erdős

La congettura

La congettura di Collatz afferma che la successione così definita:

	x_{n+1} = 
	\begin{cases}
	3x_n + 1, & x_n \mod 2 = 0 \\
	x_n/2 & x_n \mod 2 = 1
	\end{cases}

converge sempre a 1 per n \ge N \in \mathbb{N} . Ricordo che x_n \mod 2 = 0 vuol dire che x_n è pari e x_n \mod 2 = 1 vuol dire che x_n è dispari.

Python: la libreria matplotib

Ora per divertirmi un po’ a vedere come funziona questa successione ho utilizzato Python e la libreria matplotlib che avevo già utilizzato per lo studio dell’apprendimento delle reti neurali.

È semplice installarla come libreria stand-alone per Python 3:

$ git clone git@github.com:matplotlib/matplotlib.git
$ cd matplotlib/
$ python3 setup.py install

Sorgente Python

Dopodiché la uso in un programma che semplicemente calcola la successione e la visualizza su un grafico

!/usr/bin/python3
import matplotlib.pyplot as plt

a = input("Dimmi un numero: ")
print("Successione di Collatz a partire da a=",a)
z = int(a)
s = []
s.append(z)

while (z != 1):
   print(z,", ")
   if (z % 2 == 0):
      z /= 2
   else:
      z = 3*z + 1
      
   s.append(z)
# la congettura d Collatz afferma che si esce sempre dal ciclo

# disegna
x = range(len(s))
plt.plot(x, s, label="Successione di Collatz")
plt.xlabel('iterazioni')
plt.ylabel('successione')
plt.title('Congettura di Collatz')
plt.legend() 
plt.grid(True)
plt.show()

Ci si può divertire a vedere il comportamento di questa succcessione che sembra davvero imprevedibile per numeri che non fanno parte della successsione delle potenze di 2. Ad esempio il 103 genera questo andamento

Utilizzo il mio smartphone come hotspot wireless per connettermi a Internet con i dispositivi di casa. Stamattina ho voluto controllare quale fosse la potenza del segnale Wi-Fi perché volevo trovare la posizione ottimale dell’hotspot rispetto alla mia postazione di lavoro.

Prima mi sono studiato come accedere al dato della potenza del segnale Wi-Fiin ingresso dell’antenna (dettagli qui) e poi ho riportato questo dato in funzione del tempo in un grafico animato in modo tale da poter girar per casa e posizionarlo dove ho un segnale più forte, e non è detto che sia accanto al PC 😉

Campionamento della potenza del segnale Wi-Fi

La potenza istantanea del segnale Wi-Fi si può visualizzare con il comando

$ iwconfig wlp2s0
wlp2s0 IEEE 802.11 ESSID:"HUAWEI Y6 2019"
Mode:Managed Frequency:2.412 GHz Access Point: F2:E4:A2:93:8C:0C
Bit Rate=72.2 Mb/s Tx-Power=22 dBm
Retry short limit:7 RTS thr:off Fragment thr:off
Power Management:on
Link Quality=61/70 Signal level=-49 dBm
Rx invalid nwid:0 Rx invalid crypt:0 Rx invalid frag:0
Tx excessive retries:171 Invalid misc:9250 Missed beacon:0

Come si vede, la linea

Link Quality=61/70 Signal level=-49 dBm

contiene l’informazione desiderata. Se spegniamo l’hotspot l’output del comando è invece:

$ iwconfig wlp2s0
wlp2s0 IEEE 802.11 ESSID:off/any
Mode:Managed Access Point: Not-Associated Tx-Power=22 dBm
Retry short limit:7 RTS thr:off Fragment thr:off
Power Management:on

Quindi un modo se volete un po’ grezzo di accedere velocemente alla potenza del segnale Wi-Fi è fare il parsing dell’output di questo comando. L’idea è di lanciarlo con regolarità in modo da costruire un campione di dati da visualizzare in qualche modo in tempo reale.

Il primo programma che ho scritto è questo:

#!/usr/bin/python3
#
# Found in: https://www.calazan.com/how-to-continuously-monitor-your-wi-fis-signal-strength-in-ubuntu/
# Mutatis mutandi
#

import subprocess
import time
import argparse

parser = argparse.ArgumentParser(description='Display WLAN signal strength.')
parser.add_argument(dest='interface', nargs='?', default='wlan0',
                    help='wlan interface (default: wlan0)')
args = parser.parse_args()

print('\n---Press CTRL+Z or CTRL+C to exit---\n')

while True:
    cmd = subprocess.Popen('iwconfig %s' % args.interface, shell=True,
                           stdout=subprocess.PIPE)
                           
    for line in cmd.stdout:
        l = str(line)
        if 'Link Quality' in l:
            print (l),
        elif 'Not-Associated' in l:
            print ('No signal')
    time.sleep(1)

Aspetti importanti di questo script sono il package subprocess che consente a Python di lanciare un comando del sistema operativo, in questo caso

iwconfig wlp2s0

Il package argparser fornisce una serie di utilissime funzioni per maneggiare le linee di comando (definire i parametri di avvio, la loro obbligatorietà, i valori di default e finanche la documentazione di help).

Il package itertools fornisce il metodo count() che realizza un contatore progressivo che ci serve per etichettare i campioni di segnale, campioni che vengono prelevati con regolarità utilizzando le funzione del package time..

In sostanza il metodo subprocess.Popen() lancia il comando e il dato desiderato si trova nell’output del comando che comunque non è una stringa e va convertito per potere fare il parsing. Il parsing si utilizza quando il dato è annegato nella sporcizia, per cui ritengo questo mio metodo un metodo piuttosto sporco.

In questo embrione di programma ho il seguente ouput

—Press CTRL+Z or CTRL+C to stop.—

b' Link Quality=70/70 Signal level=-31 dBm \n'
b' Link Quality=70/70 Signal level=-31 dBm \n'
b' Link Quality=70/70 Signal level=-36 dBm \n'
b' Link Quality=70/70 Signal level=-32 dBm \n'
b' Link Quality=70/70 Signal level=-32 dBm \n'

Il dato interessante si trova in ogni riga dalla posizione 45 alla posizione 48.

Con una piccola modifica ci facciamo stampare solo il dato desiderato

–--Press CTRL+Z or CTRL+C to stop.---
-32
-32
-35
-31
-31
-35
-35
-35
-36

Visualizzazione del segnale Wi-Fi utilizzando matplotlib

Ora invece di stampare questi valori, li voglio disporre su un grafico. Utilizzo la libreria matplotlib. Il sorgente completo è il seguente

#!/usr/bin/python3
#
# Adopted for reading wifi power signal and plotting it
#
# @author: marco@betaingegneria.it
# @copyright: GPL Affero v.3
# @date 2020-09-25

import subprocess
import argparse
import matplotlib.pyplot as plt
from itertools import count
from matplotlib.animation import FuncAnimation

# init graphics stuff
plt.style.use('seaborn')

x=[] # time series
y=[] # power samples
index = count()

# init wlan signal reader
# parse line command arguments
parser = argparse.ArgumentParser(description='Display WLAN signal strength.')

# interface
parser.add_argument(dest='interface', nargs='?', default='wlp2s0',
                    help='wireless.py [interface=wlp2s0] [delta=800]')

# sampling period in ms
parser.add_argument(dest='delta', nargs='?', default='800',
                    help='wireless.py [interface=wlp2s0] [delta=800]')
                    
args = parser.parse_args()

if (int(args.delta) < 200):
    print('Please, choose a value >= 200 for delta')
    exit()

print('Close the window to exit')

def animate(i):
    """ read the wifi power in dBm and plot """
    x.append(next(index))
    
    cmd = subprocess.Popen('iwconfig %s' % args.interface, shell=True,
                       stdout=subprocess.PIPE)
                       
    for line in cmd.stdout:
        l = str(line)
        if 'Link Quality' in l:
            y.append(int(l[45:48]))
        elif 'Not-Associated' in l:
            y.append(None)

    plt.cla()
    plt.plot(x, y, '-', marker='.', label='WiFi signal strenght in dBm')
    plt.legend(loc='upper left')
    plt.tight_layout()
    
    # ring a bell every sample
    #print('\a')

ani = FuncAnimation(plt.gcf(), animate, interval=args.delta)    

plt.show()

Un po’ di parafrasi: la funzione animate() contiene il codice che legge la potenza e, eseguendo il parsing estraiamo il valore in dBm da accodare alla lista y, mentre nella lista x accodiamo i valori del contatore.

Il plot viene fatto utilizzando come skin lo stile seaborn, che comprende la griglia in negativo (bianco su grigio).

Infine ho utilizzato il metodo matplotlib.animation() che può essere configurato per un aggiornamento ogni delta millisecondi – ci sganciamo quindi dalla libreria time – , variabile che gestiamo come parametro di input.

Il risultato è questo

Se si spegne l’hotspot o si esce dal suo range di segnale non verrà plottato alcun dato.

Link utili

• matplotlib

• subprocess