Πυθαγόρειες Τριάδες: Το Πρόβλημα που Νίκησε η Υπολογιστική Ισχύς

Σαν σήμερα, το 2016, τρεις επιστήμονες της πληροφορικής ανακοίνωσαν τη μεγαλύτερη μαθηματική απόδειξη που έχει υπάρξει ποτέ: ένα αρχείο που φτάνει τα 200 terabytes, περίπου όσο όλο το ψηφιοποιημένο κείμενο που διατηρεί η Βιβλιοθήκη του Κογκρέσου των ΗΠΑ. Οι ερευνητές δημιούργησαν επίσης μια συμπιεσμένη εκδοχή 68 gigabyte της λύσης τους, η οποία θα επέτρεπε σε οποιονδήποτε —με περίπου 30.000 ώρες διαθέσιμου χρόνου επεξεργαστή— να την κατεβάσει, να την ανασυνθέσει και να την επαληθεύσει. Ωστόσο, κανένας άνθρωπος δεν θα μπορούσε να τη διαβάσει πλήρως.

Οι υποβοηθούμενες από υπολογιστή αποδείξεις που είναι υπερβολικά μεγάλες για να ελεγχθούν άμεσα από ανθρώπους έχουν γίνει πλέον συνηθισμένες, και οι μαθηματικοί είναι εξοικειωμένοι με υπολογιστές που λύνουν προβλήματα στη συνδυαστική —τη μελέτη πεπερασμένων διακριτών δομών— ελέγχοντας αμέτρητες επιμέρους περιπτώσεις. Παρ’ όλα αυτά, «200 terabytes είναι απίστευτο», δήλωσε ο μαθηματικός Ronald Graham από το Πανεπιστήμιο της Καλιφόρνιας στο Σαν Ντιέγκο. Ο προηγούμενος κάτοχος του ρεκόρ θεωρείται μια απόδειξη 13 gigabyte, που δημοσιεύτηκε το 2014.

Το πρόβλημα που απαιτούσε αυτή την απόδειξη των 200 terabytes, γνωστό ως το πρόβλημα των Πυθαγόρειων τριάδων Boolean, είχε μείνει άλυτο για δεκαετίες. Στη δεκαετία του 1980, ο Graham είχε προσφέρει βραβείο 100 δολαρίων σε όποιον το έλυνε. Το πρόβλημα ζητά αν είναι δυνατόν να χρωματιστεί κάθε θετικός ακέραιος είτε κόκκινος είτε μπλε, έτσι ώστε καμία τριάδα αριθμών a, b και c που ικανοποιούν την εξίσωση του Πυθαγόρα (a² + b² = c²) να μην έχει όλα τα στοιχεία της στο ίδιο χρώμα. Για παράδειγμα, για την τριάδα 3, 4 και 5, αν το 3 και το 5 είναι μπλε, τότε το 4 πρέπει να είναι κόκκινο.

 Σε μια εργασία που αναρτήθηκε στο arXiv (*) στις 3 Μαΐου, οι Marijn Heule, Oliver Kullmann και Victor Marek έδειξαν ότι υπάρχουν πολλοί επιτρεπτοί τρόποι να χρωματιστούν οι ακέραιοι μέχρι το 7.824 — αλλά όταν φτάνουμε στο 7.825, είναι αδύνατο όλες οι Πυθαγόρειες τριάδες να έχουν διαφορετικά χρώματα. Υπάρχουν περισσότερες από 102.300 διατάξεις χρωματισμού μέχρι το 7.825, αλλά οι ερευνητές εκμεταλλεύτηκαν συμμετρίες και τεχνικές από τη θεωρία αριθμών για να μειώσουν τις περιπτώσεις που έπρεπε να ελέγξει ο υπολογιστής σε λίγο κάτω από 1 τρισεκατομμύριο. Η ομάδα χρειάστηκε περίπου 2 ημέρες, χρησιμοποιώντας 800 επεξεργαστές παράλληλα στον υπερυπολογιστή Stampede του Πανεπιστημίου του Τέξας, για να εξετάσει όλες τις πιθανότητες. Στη συνέχεια, επαλήθευσαν την απόδειξη με ένα άλλο υπολογιστικό πρόγραμμα.

(*)Το arXiv (προφέρεται "archive", καθώς το "X" αντιπροσωπεύει το ελληνικό γράμμα "Χ") είναι ένα εξαιρετικά δημοφιλές αποθετήριο ανοικτής πρόσβασης για επιστημονικές προδημοσιεύσεις (preprints).Ανήκει και διαχειρίζεται από το Πανεπιστήμιο Cornell και αποτελεί τον "ναό" της άμεσης διακίνησης της επιστημονικής γνώσης, ειδικά στους τομείς των θετικών επιστημών.