Archivi autore: .mau.

Informazioni su .mau.

matematto non praticante

Base Fibonacci, insieme di Shevelev e congettura di Kimberling

Se seguivate il mio vecchio blog sul Post (quando il Post aveva i blog…) sapete sicuramente della base di numerazione φ. Come in base 10 un numero come 42,5 equivale a 4×101 + 2×100 + 5×10−1, in base φ un numero come 1000.1001 equivale a φ3 + φ−1 + φ −4, che in base 10 equivale a 5. Ci sono molte rappresentazioni possibili per un numero in base φ; per convenzione si sceglie come forma canonica quella che non ha due cifre 1 consecutive (lo si può sempre fare, ricordando che $ \varphi^n + \varphi^{n+1} = \varphi^{n+2)}$).

Riguardo alla base φ, Richard Green segnala una curiosità, raccontata nel paper di Jeffrey Shallit e Ingrid Vukusic New properties of the φ-representation of integers. Consideriamo l’insieme degli interi che in base φ sono “antipalindromi”, dove cioè se c’è la cifra 1 in posizione $k$ c’è anche la cifra 1 in posizione $-k$. Per esempio, 1 è antipalindromo, perché $1_{10} = 1_{\varphi}$, e l’unica cifra 1 è in posizione 0 che è l’opposto di sé stessa; 2 non lo è, perché $2_{10} = 10,01_{\varphi}$ e anche se il numero pare simmetrico non lo è (le posizioni con 1 sono 1 e −2); 3 lo è perché $3_{10} = 100,01_{\varphi}$ e le posizioni con 1 sono la 2 e la −2. L’insieme dei numeri naturali che sono antipalindromi in base φ comincia con 1, 3, 4, 7, 8, 10, 11, 18, 19, 21, 22, 25, 26, 28, 29, 47, … e naturalmente si trova su OEIS, prendendo il nome di Vladimir Shevelev che l’ha studiato per primo nel 2010. Bene: due anni dopo Clark Kimberling si è accorto che i numeri nell’insieme di Shevelev avevano la proprietà che raddoppiando tutti gli esponenti nella sua notazione in base φ si otteneva un altro numero naturale, cosa che a prima vista non era ovvia: per esempio, 10 è $10100,0101+{\phi}$ e $10010000,00010001+{\phi}$ = 54. Allo stesso tempo, se un numero non è nell’insieme di Shevelev raddoppiando tutti gli esponenti non si ottiene un intero: per esempio 9 è $10010,0101_{\phi}$ mentre $10000100,00010001_{\phi} = (52 – \sqrt{5})_{10}$.

Bene: Shallit e Vukusic sono riusciti a dimostrare la congettura di Kinberling. La dimostrazione tra l’altro non è nemmeno troppo difficile. Hanno infatti sfruttato i numeri di Lucas (una variante dei numeri di Fibonacci, dove non si parte da {1,1} ma da {3,1} per la definizione ricorsiva) per dimostrare che i numeri antipalindromi sono tutti e soli quelli che hanno solo esponenti pari nella rappresentazione in base φ. Non so voi, ma tutto questo mi pare incredibile…

Sandra Biondo

Se mi leggete spesso, saprete che io frequento un socialino di nicchia dove saremo in meno di cento a scrivere. Come potete immaginare, ci si conosce più o meno tutti, e con molti ci si è anche visti di persona. Potete immaginare come mi sono sentito quando domenica ho saputo che Sandra Biondo era improvvisamente morta.
Come scriveva lei stessa Sandra era bolognese, ma aveva vissuto a lungo in Brasile, come collaboratrice in una missione salesiana. Nella sua vita ha fatto la traduttrice dal portoghese e l’insegnante sempre di portoghese: il Brasile le era infatti sempre rimasto nel cuore, ed è tornata molto spesso, oltre che parlarne in un suo blog. Ma Sandra ha sempre voluto aiutare i ragazzi: alcuni anni fa è stata affidataria di un diciassettenne albanese, una di quelle cose che non fanno certo tutti. Ma quella di aiutare la gente in generale è stata sempre la sua caratteristica: negli ultimi anni aveva lavorato in un CAAF, e finalmente aveva avuto un contratto a tempo indeterminato che la aveva fatta sentire più tranquilla.
Quando raccontava delle persone che incontrava al CAAF si capiva bene la sua capacità di vedere le cose positive in chiunque incontrasse: una dote rarissima che fa sentire ancora di più la sua mancanza.

Sempre corrieri

GLS
"non è ancora arrivata"
L’altra settimana ho acquistato su Amazon Marketplace. Il pacchetto è stato spedito con GLS. Primo tentativo: il pacco, spedito il 16 settembre, si è perso. Dopo un po’ rispunta (o ne è stato spedito un altro), e arriverebbe a casa mia alle 15:19 di mercoledì scorso, con “destinatario assente”. Peccato che io alle 15:19 di mercoledì scorso fossi a casa in una call, e sono certo che nessuno ha citofonato.
Poi il giorno dopo ci sarebbe stato un “Ritardo nella spedizione a causa di fattori esterni”, che avrebbe portato a “Spedizione trattenuta dal corriere”; nel pomeriggio infine “Il cliente ha richiesto un accordo di consegna che potrebbe far ritardare la spedizione”. Peccato che io non sapessi nulla di tutto questo, anche perché né GLS né Amazon si sono degnati di dire qualcosa. Quand’è che i corrieri eviteranno di prenderci per i fondelli?
(ah, io avrei anche fatto arrivare il pacchetto a un locker, se fosse stato possibile…)

Ho scritto qualcosa che non è piaciuto

sono stato zittito
Il signor Google mi ha mandato questo. Notate come la privacy sia sempre a senso unico: non posso sapere chi ha deciso che qualcosa che ho scritto in questi decenni dia fastidio a qualcuno, e non posso neppure cercare di ricavarlo sapendo quali ricerche sono bloccate.

Ma la cosa che dovrebbe preoccupare tutti noi è un’altra. Io sono tutto meno che anonimo. Se avessi scritto qualcosa ritenuto diffamante (non che io lo faccia, sono sempre molto attento a quanto scrivo) chi si fosse sentito leso avrebbe potuto farmi scrivere da un avvocato, o comunque chiedermi di eliminare quel testo. Chiaramente non ho ricevuto nessuna richiesta di questo tipo. Ripeto: la privacy èsempre a senso unico, quello dei forti.

Stanno davvero arrivando le IA “intelligenti”?

L’International Collegiate Programming Contest è una gara (ma quante ne esistono?) dove squadre di tre studenti universitari devono scrivere in cinque ore dodici programmi. Quest’anno le finali sono state a Baku, e – come Alberto Romero riporta la “squadra” di OpenAI ha scritto correttamente il codice per tutti e dodici i problemi, superando Google DeepMind che si è fermata a dieci. La cosa più incredibile è che nessuna squadra umana ha ottenuto il punteggio pieno, fermandosi al massimo a 11/12.

Fin qui la notizia, che mi sa sia passata abbastanza inosservata almeno nel resto della mia bolla. Ma la parte davvero interessante del risultato di OpenAI è il modo con cui l’ha raggiunto. Secondo Mostafa Rohaninejad di OpenAI, infatti, a parte avere avuto a disposizione lo stesso tempo dei concorrenti umani, il modello usato è stato a detta di Rohaninejad “una composizione di GPT-5 e un modello di ragionamento sperimentale che generavano soluzioni, con il modello sperimentale che sceglieva quale soluzione dare. GPT-5 ha dato undici risposte corrette, e l’ultimo (e più difficile) problema è stato risolto dal modello di ragionamento sperimentale”.

Chiaramente un resoconto sotto forma di tweet non dice molto, senza contare che a questi livelli ci sono segreti aziendali. E c’è qualcosa che non mi torna nella storia. Però qualcosa la si può dire lo stesso. Innanzitutto, GPT-5 (che poi è quello che adesso abbiamo come interfaccia quando usiamo ChatGPT) è stato usato come “utile idiota”: gli si fa sparare una serie di soluzioni, e poi ci pensa qualcun altro – nel nostro caso, qualcos’altro – a stabilire cosa può andare bene e cosa no. Questo mi pare un ottimo modo per usare un LLM: se mi consentite un paragone un po’ azzardato, è come prendere in mano un rimario quando si vuole comporre una canzone. Lì troviamo le parole possibili, ma siamo poi noi a trovare le connessioni.

La cosa più intrigante è il “modello sperimentale”, che pare essere lo stesso usato all’IMO, le olimpiadi della matematica. Non serve l’intelligenza artificiale per verificare se un risultato è corretto: lo stato dell’arte nei dimostratori automatici di correttezza dei problemi è tale da essere regolarmente usato. Insomma, fin qui non si vedrebbe nulla di nuovo, se non probabilmente un metodo per convertire il formato interno dei risultati di GPT-5 in un formato utilizzabile da questo modello. Ma cosa è successo con il famigerato “problema difficile”, quello G nell’elenco delle prove? Chi è stato a fare i nove tentativi, e soprattutto perché il “modello sperimentale” non è sempre stato usato per risolvere gli altri problemi?

La mia ipotesi è che questo modello misterioso abbia non solo la capacità di verificare la validità di una soluzione ma anche quella di modificarla. Non sto pensando agli algoritmi genetici, che probabilmente ci metterebbero troppo tempo per stabilizzarsi su una soluzione, ma a qualche regola più o meno rigida per cambiare qualche parametro e vedere come evolve la situazione. Questo spiegherebbe la necessità di avere comunque un modello generativo sottostante: il modello misterioso non potrebbe partire da zero ma dovrebbe sempre avere una base relativamente solida su cui lavorare. Se effettivamente è questa la struttura alla base del modello di OpenAI, le implicazioni sono davvero incredibili, almeno per contesti dove le modifiche possibili sono relativamente poche e facilmente definibili. Non so se si potrebbe parlare davvero di intelligenza, ma ci si avvicinerebbe molto. Voi che ne pensate?

Quizzino della domenica: Punti a coppie

767 – parità

Prendete una retta orientata e due punti su di essa; etichettate il punto di sinistra 0 e quello di destra 1, ottenendo una configurazione (0, 1). Da questa configurazione le mosse che avete a disposizione sono due. La prima mosse aggiunge due punti in modo che tra di loro non si trovi nessun punto etichettato: i due punti possono essere etichettati (0, 0) oppure (1, 1). La seconda mossa elimina due punti consecutivi (cioè senza nessun altro punto etichettato in mezzo), sempre che abbiano la stessa etichetta (0, 0) oppure (1, 1). È possibile arrivare a ottenere una configurazione (1, 0)?

la retta con alcuni punti
(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p767.html; la risposta verrà postata lì il prossimo mercoledì. Problema da Futility Closet.)

Unsong (libro)

copertinaCosa succede se quando la missione Apollo 8 sta arrivando sulla Luna sbatte contro la volta celeste, rompendola e trasformando il pianeta in un posto dove la kabbalah la fa da padrona e i GAFAM (che qui si chiamano Microprosopus, Gogmagog, Amalek, Countenance e Serpens) vendono i Nomi di Dio che fanno miracoli, mentre un Sottocomitato ONU verifica che nessuno li usi invano (cioè senza aver pagato il copyright)? Succede quello che leggerete in questo libro, nato dal blog di Alexander e poi rivisto per la versione in volume. Non è facile seguire tutti gli intrecci della storia, ed è ancora più difficile comprendere i giochi di parole: un’ottima conoscenza biblica e talmudica è sicuramente utile, e se proprio non ce la fate potete provare a chiedere aiuto sull’apposito subreddit. Altamente consigliato se volete passare un paio di mesi di piacevole – anche se a volte un po’ irritante – lettura.

(Scott Alexander, Unsong, autoprodotto 2024, pag. 652, € 19,23, ISBN 9798320962610 – come Affiliato Amazon, se acquistate il libro dal link qualche centesimo va a me)
Voto: 5/5

Quanto sono migliorati i computer!

Per pubblicizzare la crittografia RSA, o meglio per dimostrare quanto fosse difficile da decrittare, nel 1991 gli RSA Laboratories lanciarono una sfida, con alcuni numeri semiprimi (cioè prodotto di due primi) da fattorizzare. Il più piccolo, RSA-100 (quindi un numero di 100 cifre), fu decrittato in una dozzina di giorni, usando il computer MP1 MasPar che costava mezzo milione di dollari di allora (circa 1.250.000$ attuali). Quella fattorizzazoine non era comunque un problema, visto che era RSA-256 lo standard promosso all’epoca, John D. Cook ha provato a fattorizzarlo in queste settimane, con un minicomputer System 76 Meerkat, pagato 600$ nel 2022. Tempo necessario: 23 minuti.

Per i non esperti: il tempo di fattorizzazione non aumenta linearmente con la dimensione dei numeri, quindi anche questo miglioramento di un fattore più o meno 1000 non serve a molto per i numeri usati nei sistemi crittografici attuali. Inoltre per quanto ne so ci può essere stato anche un miglioramento nei programmi di fattorizzazione, anche se non così dirompente. Però l’aumento della potenza dei computer è davvero impressionante!