{"id":132,"date":"2014-02-19T10:57:09","date_gmt":"2014-02-19T09:57:09","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=132"},"modified":"2022-10-11T12:58:53","modified_gmt":"2022-10-11T10:58:53","slug":"una-dimostrazione-piu-grande-di-tutta-wikipedia","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2014\/02\/19\/una-dimostrazione-piu-grande-di-tutta-wikipedia\/","title":{"rendered":"Una dimostrazione pi\u00f9 grande di tutta Wikipedia"},"content":{"rendered":"

Da Liverpool non sono solo arrivati i Beatles. \u00c8 notizia di questi giorni che Alexei Lisitsa e Boris Konev dell’Universit\u00e0 di Liverpool hanno pubblicato un preprint<\/a> in cui fanno un passo avanti verso la risoluzione del problema delle discrepanze di Erd\u0151s<\/b>… o meglio lo fanno fare al computer, visto che la dimostrazione occupa pi\u00f9 spazio dell’intera base dati di Wikipedia. Beh, meglio raccontare la storia dall’inizio.<\/p>\n

Ho gi\u00e0 parlato un paio di volte (qui<\/a> e qui<\/a>) del matematico Paul Erd\u0151s e delle sue eccentricit\u00e0. Una sua caratteristica – decidete voi se \u00e8 eccentrica o no – era quella di sparare congetture a raffica e vedere se lui o qualcun altro riusciva a risolverle. Il problema delle discrepanze (c’\u00e8 un qualche accenno su Wikipedia<\/a>) \u00e8 appunto una di queste congetture: come molti problemi in teoria dei numeri \u00e8 relativamente facile da esporre, molto meno da dimostrare. <\/p>\n

Erd\u0151s partiva considerando le successioni infinite di +1 e -1, se si chiedeva se potesse essercene qualcuna abbastanza “equilibrata”, oppure – come lui credeva – no. La definizione di “successione equilibrata” consisteva nel partire dalla successione, prendere una sottosuccessione qualunque – dove per sottosuccessione si intendono gli elementi di posto d<\/i>, 2d<\/i>, 3d<\/i>, …, kd<\/i> – fare la somma dei valori e non trovarsi mai troppo lontano da zero. Detto in altri termini, la somma (algebrica) dei primi k<\/i> numeri, o la somma dei primi k<\/i> numeri in posizione pari, o quella dei primi k<\/i> numeri in posizione multipla di 42 doveva essere sempre minore in valore assoluto di un certo C<\/i>. Per\u00f2, secondo Erd\u0151s, questo non era possibile: in qualunque modo si mettessero i +1 e i -1 si poteva sempre trovare una sottosuccessione la cui somma abbia valore assoluto (la discrepanza, appunto) grande a piacere. La congettura appare in un articolo del 1957, ma Erd\u0151s scrisse che ci pensava dagli anni 1930, tanto che offr\u00ec 500$ per chi l’avesse risolta. Quella di mettere una taglia su un problema era un’altra peculiarit\u00e0 di Erd\u0151s; quella era una delle cifre pi\u00f9 alte che avesse mai offerto, il che la dice lunga su quanto ritenesse complicato il problema.<\/p>\n

Qualche esempio potr\u00e0 forse far capire meglio cosa succede. Se immaginiamo una successione di tutti +1, naturalmente la discrepanza \u00e8 infinita. Quindi dobbiamo cercare per quanto possibile di avere un numero simile di +1 e di -1. Ma la successione +1 -1 +1 -1 +1 -1 ...<\/tt> non funziona mica; se prendiamo la sottosuccessione delle posizioni pari abbiamo -1 -1 -1 -1...<\/tt> che di nuovo va all’infinito ancorch\u00e9 negativo. Possiamo pensare allora a scrivere qualcosa di pi\u00f9 complicato, come +--+-++--++-+--+...<\/tt> dove per comodit\u00e0 ho scritto + invece che +1 e – anzich\u00e9 -1; questa successione \u00e8 costruita per ricorsione, aggiungendo ogni volta l’opposto di quanto gi\u00e0 presente. Non ho avuto voglia di fare i conti completi, ma gi\u00e0 cos\u00ec i primi multipli di 3 sono -+---<\/tt>, il che significa che la discrepanza di questa successione \u00e8 almeno 3. <\/p>\n

Per\u00f2 \u00e8 chiaro che non possiamo andare avanti in questo modo, facendo ipotesi e testandole una a una: occorre un approccio un po’ pi\u00f9 scientifico. In pratica quello che vorremmo dimostrare \u00e8 che, data una successione infinita<\/b> di +1 e -1, troviamo sempre delle sottosuccessioni di discrepanza grande a piacere. Ma iniziamo in piccolo: se Erd\u0151s ha ragione, dato un qualunque valore C<\/i> possiamo trovare una successione finita<\/b> abbastanza lunga la cui discrepanza \u00e8 maggiore di C<\/i>. Visto che una successione infinita ha comunque una parte iniziale finita, saremmo a posto. Proviamo allora a sporcarci un po’ le mani: costruir\u00f2 esplicitamente una successione di 11 elementi di discrepanza 1, cio\u00e8 per cui la somma di qualunque sottosuccessione \u00e8 -1, 0 oppure 1. <\/p>\n

\"[una
Costruzione di una successione di lunghezza 11 e discrepanza 1<\/figcaption><\/figure>Possiamo scegliere senza perdita di generalit\u00e0 +1 come primo elemento: con -1 si farebbe infatti lo stesso ragionamento a segni invertiti. Questo ci obbliga per\u00f2 ad avere come secondo elemento -1, perch\u00e9 altrimenti la sottosuccessione (1,2) avrebbe somma 2. Ma allora l’elemento 4 deve essere +1, perch\u00e9 altrimenti la sottosuccessione (2,4) avrebbe somma -2, e l’elemento 8 deve essere -1. Abbiamo cos\u00ec ottenuto la prima riga nella tabella qui a destra. A questo punto l’elemento 3 non pu\u00f2 essere +1, perch\u00e9 altrimenti la sottosuccessione (1,2,3,4) avrebbe somma 2; dunque \u00e8 -1, e l’elemento 6 \u00e8 +1. Siamo arrivati alla seonda riga della tabella. Il prossimo passo \u00e8 avere -1 in posizione 5 e +1 in posizione 10, poi +1 in posizione 7 e -1 in posizione 9; per la posizione 11 si pu\u00f2 infine scegliere a piacere +1 o -1. Queste due (e le due ottenute sostituendo +1 a -1 e viceversa) sono le uniche disposizioni possibili con discrepanza 1.<\/p>\n

Proviamo ora a inserire un dodicesimo elemento. Visto che quello in posizione 6 \u00e8 un +1, dovrebbe essere un -1; ma visto che le posizioni 3 e 9 hanno un -1, la sottosuccessione (3,6,9,12) avrebbe somma -2. Senza provare tutte le 4096 possibilit\u00e0 di assegnare +1 e -1, abbiamo cos\u00ec dimostrato che una successione di almeno 12 elementi ha discrepanza maggiore o uguale a 2. E poi? Ecco, qui iniziano i Veri Problemi. Mentre con la discrepanza 1 i vincoli erano cos\u00ec stretti che ho potuto fare i conti a mano, gi\u00e0 con la discrepanza 2 le possibilit\u00e0 aumentano in maniera esponenziale. Non ci sono cos\u00ec stati molti progressi in questo mezzo secolo; anche quando i pazzi di Polymath – un gruppone di matematici che si mettono tutti insieme ad attaccare un problema, ne ho parlato qui<\/a> a proposito della congettura dei primi gemelli – hanno provato a mettersi all’opera, il massimo che avevano ottenuto<\/a> era trovare una successione di lunghezza 1124 e discrepanza 2. <\/p>\n

Lisitsa e Konev hanno invece pensato di usare SAT Solver, un programma che implementa le tecniche di Soddisfacibilit\u00e0 booleana<\/a>; in altre parole hanno tradotto l’enunciato del problema in modo tale che fosse possibile definire se la risposta era “vero o falso” (per una successione finita questo \u00e8 sempre possibile, perch\u00e9 il numero di combinazioni \u00e8 finito) e hanno fatto girare il programma perch\u00e9 scrivesse i passaggi logici necessari per arrivare alla soluzione. Il risultato \u00e8 stato che hanno esplicitamente trovato una successione di lunghezza 1160 e di discrepanza 2; verificare questo fatto \u00e8 relativamente semplice. Ma soprattutto hanno fatto dimostrare al SAT Solver che non esistono successioni di lunghezza 1161 e discrepanza 2. Il piccolo guaio \u00e8 che appunto i passi formali della dimostrazione occupano 13 GB, e per fare un confronto la base dati di Wikipedia (d’accordo, questa \u00e8 compressa…) si limita ad occupare 10 GB. <\/p>\n

Questo non \u00e8 certo il primo caso di dimostrazione tendenzialmente impossibile da verificare per un essere umano; sono gi\u00e0 passati quarant’anni dalla dimostrazione del teorema dei quattro colori, che anch’essa richiede un computer per verificare tutti i casi. Questo non \u00e8 un grande problema; per verificare il risultato basta scrivere una nuova implementazione di un SAT Solver e riscrivere da capo in maniera booleana il risultato da provare. Il vero problema \u00e8 che siamo passati dall’aver dimostrato che il minimo valore \u00e8 2 all’aver dimostrato che il minimo valore \u00e8 3: considerando che la congettura afferma che non c’\u00e8 minimo valore, o se preferite dirlo in maniera na\u00eff questo valore \u00e8 infinito, capirete che non si \u00e8 fatto chiss\u00e0 quale passo. D’altra parte questo approccio non potrebbe nemmeno dimostrare mai la congettura, o se preferite confutarla, ma solo trovare valori sempre maggiori di C<\/i>. E probabilmente non riuscir\u00e0 nemmeno a fare questo: per dire, al momento gli autori hanno scoperto una successione di lunghezza 13000 e discrepanza 3, ma non sono ancora riusciti a testare successioni pi\u00f9 lunghe perch\u00e9 il SAT Solver non ce la fa… Insomma, se qualcuno vuole mettere le mani sul problema pu\u00f2 ancora farcela!<\/p>\n","protected":false},"excerpt":{"rendered":"

Il primo passo avanti nella dimostrazione di una congettura di Erd\u0151s \u00e8 stato (forse) compiuto da un dimostratore automatico di teoremi. Ma…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[53,54,55,19],"class_list":["post-132","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-congetture","tag-dimostrazioni-al-computer","tag-erdos","tag-teoria-dei-numeri"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-28","jetpack-related-posts":[{"id":2478,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/13\/una-dimostrazione-errata-e-meglio-che-nessuna-dimostrazione\/","url_meta":{"origin":132,"position":0},"title":"Una dimostrazione errata \u00e8 meglio che nessuna dimostrazione","author":".mau.","date":"13\/02\/2012","format":false,"excerpt":"Certo, in matematica una dimostrazione errata di per s\u00e9 non serve a nulla. Per\u00f2 pu\u00f2 essere un utile punto di partenza.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2626,"url":"https:\/\/xmau.com\/ilpost\/2013\/07\/12\/epidemie\/","url_meta":{"origin":132,"position":1},"title":"Epidemie","author":".mau.","date":"12\/07\/2013","format":false,"excerpt":"Un problema matematico la cui dimostrazione \u00e8 un'applicazione del concetto di monovariante.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2481,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/23\/quando-i-matematici-sbagliano\/","url_meta":{"origin":132,"position":2},"title":"Quando i matematici sbagliano","author":".mau.","date":"23\/02\/2012","format":false,"excerpt":"Perch\u00e9 preoccuparsi delle smentite in fisica? Persino in matematica una dimostrazione non \u00e8 sempre corretta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2476,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/08\/la-magia-delle-soluzioni\/","url_meta":{"origin":132,"position":3},"title":"La magia delle soluzioni","author":".mau.","date":"08\/02\/2012","format":false,"excerpt":"Spesso la soluzione di un problema matematico sembra uscire come per magia da un cappello. Ma in fin dei conti il bello della matematica \u00e8 che un problema pu\u00f2 magicamente essere visto da un altro punto di vista!","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":398,"url":"https:\/\/xmau.com\/ilpost\/2010\/07\/27\/il-teorema-di-pitagora\/","url_meta":{"origin":132,"position":4},"title":"Il teorema di Pitagora","author":".mau.","date":"27\/07\/2010","format":false,"excerpt":"Il teorema pi\u00f9 famoso della geometria merita indubbiamente una trattazione a s\u00e9.","rel":"","context":"In \"geometria\"","block_context":{"text":"geometria","link":"https:\/\/xmau.com\/ilpost\/tag\/geometria\/"},"img":{"alt_text":"[la costruzione euclidea del teorema di Pitagora]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2014\/09\/pitagora-euclide.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2636,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/11\/il-teorema-della-pizza\/","url_meta":{"origin":132,"position":5},"title":"Il teorema della pizza","author":".mau.","date":"11\/09\/2013","format":false,"excerpt":"Ecco un risultato assolutamente poco intuitivo che per\u00f2 potrebbe sempre servire nella vita quotidiana (ehm..)","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"Un taglio in quattro parti e un altro taglio in otto parti","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/09\/pizza1.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/132","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=132"}],"version-history":[{"count":9,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/132\/revisions"}],"predecessor-version":[{"id":153,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/132\/revisions\/153"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=132"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=132"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=132"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}