Σάββατο, 28 Μαΐου 2016

Η μεγαλύτερη μαθηματική απόδειξη στον κόσμο

… καταλαμβάνει χώρο 200 terabytes!
Είναι δυνατόν να χρωματίσουμε όλους τους ακέραιους αριθμούς είτε με κόκκινο είτε με μπλε χρώμα, έτσι ώστε να μην υπάρχει πυθαγόρεια τριάδα ακεραίων με το ίδιο χρώμα; Η επίλυση αυτής της εικασίας καταλαμβάνει χώρο 200 terabytes.
(πυθαγόρεια τριάδα = αριθμοί α, β, γ που ικανοποιούν τη σχέση $α^2 + β^2 = γ^2$)
Οι αριθμοί 1 έως 7824 μπορούν να χρωματιστούν είτε με μπλε χρώμα είτε με κόκκινο, έτσι ώστε να μην υπάρχει καμία πυθαγόρεια τριάδα με το ίδιο χρώμα. Το πλέγμα των 7824 τετραγώνων της εικόνας δείχνει μια τέτοια λύση (τα λευκά τετράγωνα μπορούν να πάρουν οποιοδήποτε χρώμα από τα δύο).
Όμως για τους αριθμούς 1 έως 7825 αυτό είναι αδύνατο! 

Ο Paul Erdös (1913 – 1996) ένας από τους σημαντικότερους μαθηματικούς του 20ου αιώνα, αλλά και από τους πιο εκκεντρικούς, συνήθιζε να προσφέρει χρηματικά βραβεία για τις λύσεις προβλημάτων που τον ενοχλούσαν. Δεν τον ένοιαζε ποιος θα τα λύσει, απλά ήθελε να λυθούν και σκέφτηκε πως ένα χρηματικό έπαθλο ήταν ο καλύτερος τρόπος για να επιτύχει αυτό το αποτέλεσμα. Μερικά από τα απλούστερα προβλήματά του απέφεραν μόλις ένα ή δυο δολάρια, αλλά πρόσφερε μέχρι και 10.000 δολάρια για τα προβλήματα που θεωρούσε «απελπιστικά». Το μεγαλύτερο χρηματικό έπαθλο που χρειάστηκε να καταβάλλει ποτέ ο Erdös, ήταν 1000 δολάρια. «Κάποτε με ρώτησε κάποιος τι θα γινόταν αν όλα τα προβλήματα λύνονταν διαμιάς», είπε μια φορά ο Erdös. «Θα μπορούσα να πληρώσω; Φυσικά όχι. Αλλά τι θα πάθαινε η ισχυρότερη τράπεζα αν όλοι οι πιστωτές της ζητούσαν πίσω τα λεφτά τους; Η τράπεζα σίγουρα θα χρεοκοπούσε. Ένας τραπεζικός πανικός είναι πολύ πιο πιθανός από έναν «μαθηματικό πανικό» – το να επιλυθούν δηλαδή ταυτόχρονα όλα τα προβλήματά μου».
Σε όλη του τη ζωή ο Erdös πλήρωσε τρεις ή τέσσερις χιλιάδες δολάρια γι΄αυτά τα βραβεία, αλλά πολύ περισσότερα προβλήματά του παραμένουν άλυτα. Ο στενός συνεργάτης του Ron Graham και μερικοί άλλοι φίλοι του Erdös έχουν υποσχεθεί ότι θα προσφέρουν οποιοδήποτε σημαντικό ποσό σε όποιον καταφέρει να τα επιλύσει.
«Πολλά από αυτά τα προβλήματα» έλεγε ο Graham, «έχουν παραμείνει άλυτα για πολύ καιρό και ίσως θα έπρεπε να αυξηθεί η τιμή τους.»
Ένα πρόβλημα που παρέμενε μέχρι σήμερα άλυτο, είχε τεθεί το 1980 από τους Erdös-Graham, και η λύση του προκηρύχθηκε έναντι 100 δολαρίων.  Πρόκειται για το πρόβλημα των «μπουλιανών πυθαγόρειων τριάδων» , το οποίο απαντήθηκε από τους Marijn J. H. Heule, Oliver Kullmann, και Victor W. Marek [Solving and Verifying the boolean Pythagorean]
Η διατύπωση του προβλήματος: Μπορούμε να διαχωρίσουμε το σύνολο των φυσικών αριθμών Ν={1, 2, 3, 4, …} σε δυο σύνολα, τέτοια ώστε κανένα από τα δυο να μην περιέχει πυθαγόρειες τριάδες (δηλαδή τριάδες αριθμών α, β, γ που ικανοποιούν τη σχέση α2 + β2= γ2);
Ή να το πούμε διαφορετικά: Είναι δυνατόν να χρωματίσουμε όλους τους ακέραιους αριθμούς είτε με κόκκινο είτε με μπλε χρώμα, έτσι ώστε να μην υπάρχει πυθαγόρεια τριάδα ακεραίων α, β, γ (α2 + β2 = γ2) με το ίδιο χρώμα;
Για παράδειγμα, στην πυθαγόρεια τριάδα 3, 4 και 5, αν τα 3 και 5 είναι χρώματος μπλε, τότε το 4 θα πρέπει να είναι κόκκινο.
Το πρόβλημα των πυθαγόρειων τριάδων είναι ένα από τα πολλά παρόμοια ερωτήματα στη θεωρία του Ramsey, μια περιοχή των μαθηματικών που ασχολείται με την εύρεση των δομών που πρέπει να εμφανίζονται σε μεγάλα σύνολα.
Η απόδειξη πραγματοποιήθηκε διαμέσου υπολογιστή από τους Heule et al τεστάροντας όλους τους δυνατούς χρωματισμούς των αριθμών μέχρι το 7825 και βρέθηκε ότι είναι αδύνατος ένας τέτοιου είδους διαχωρισμός.  Υπάρχουν 102300 συνδυασμοί χρωματισμού των αριθμών μέχρι τον 7825, αλλά οι ερευνητές χρησιμοποιώντας διάφορες συμμετρίες και τεχνικές μείωσαν τους συνδυασμούς σε ένα τρισεκατομμύριο. Έτσι, για την διερεύνηση απαιτήθηκαν δυο ημέρες λειτουργίας του υπερ-υπολογιστή Stampede στο Πανεπιστήμιο του Τέξας. Η απόδειξη καταλαμβάνει 200 terabytes δεδομένων, δηλαδή περίπου όσο χώρο πιάνουν όλα τα ψηφιοποιημένα κείμενα της τεράστιας Βιβλιοθήκης του Κογκρέσου των ΗΠΑ. Το προηγούμενο ρεκόρ κατείχε μια μαθηματική απόδειξη μέσω υπολογιστή (The Erdos discrepancy problem) που είχε δημοσιευθεί το 2014 και καταλάμβανε χώρο μόνο 13 gigabyte. Όμως ένα χρόνο μετά ο Terence Tao κατάφερε να λύσει το πρόβλημα με τον παραδοσιακό αναλυτικό μαθηματικό τρόπο, χωρίς υπολογιστές.
Πάντως οι μαθηματικοί  – Heule, Kullmann και Marek – που έλυσαν το πρόβλημα των πυθαγόρειων τριάδων, στην περίληψη της δημοσίευσής τους, φροντίζουν να αναφέρουν με νόημα … την αμοιβή που προσέφερε ο Ronald Graham πριν από δεκαετίες!
Ένας από τους ερευνητές, ο Kullmann, επισημαίνει ότι η απόδειξή τους – που δεν είναι απόδειξη με την κλασική έννοια του όρου στα μαθηματικά – δεν εξηγεί τι συμβαίνει από το 7825 και μετά, κι ούτε μπορεί να μας πει αν ο συγκεκριμένος αριθμός έχει κάποια ιδιαίτερη σημασία.

Δεν αποκλείεται λοιπόν στο άμεσο μέλλον να εμφανιστεί ένας Terence Tao που να καταφέρει να λύσει το πρόβλημα των μπουλιανών πυθαγόρειων τριάδων με τον παραδοσιακό μαθηματικό τρόπο και να απαιτήσει το έπαθλο των 100 δολαρίων.
πηγές:

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου