Η επίθεση μιας τεχνητής νοημοσύνης σε σύνολα χωρίς αριθμητικές προόδους: ένα κατάστιχο όσων βάλτωσαν

TL;DR. Ένας βοηθός τεχνητής νοημοσύνης εργάστηκε σε δύο προβλήματα για σύνολα χωρίς αριθμητικές προόδους: ένα επιχείρημα για το πρόβλημα του αθροίσματος των αντιστρόφων και ένα οιονεί πολυωνυμικό φράγμα.

Βασικά συμπεράσματα

Δύο εργασίες, και μόνο για τη μία έγινε ποτέ ισχυρισμός. Το υλικό χωρίζεται σε δύο εργασίες και αξίζει να κρατήσουμε την κατάστασή τους ξεχωριστή.
Η μείωση της πυκνότητας δεν είναι το ίδιο με την αθροισιμότητα. Το πρώτο εμπόδιο εμφανίζεται στο επίπεδο της αρχιτεκτονικής του επιχειρήματος, πριν από οποιαδήποτε ανάλυση Fourier.
Διατήρηση της δομής, και γιατί οι τρεις όροι δεν γενικεύονται. Μια προτεινόμενη θεραπεία είναι να διατηρείται η δομή.
Ευθυγράμμιση συχνοτήτων μία φορά αντί για πολλές. Η διαδοχική ευθυγράμμιση των συναρτήσεων συχνότητας είναι το σημείο όπου το πρόβλημα της συσσώρευσης δαγκώνει πιο δυνατά.

Το πιο χρήσιμο πράγμα που μπορεί να σας πει μια ημιτελής απόδειξη είναι ακριβώς πού σπάει, και η συγκεκριμένη σπάει σε περίπου δώδεκα συγκεκριμένα σημεία.

Επιτελική Σύνοψη

Η εργασία έχει δύο σκέλη. Το πρώτο αναπτύσσει ένα επιχείρημα για το πρόβλημα του αθροίσματος των αντιστρόφων. Το δεύτερο αναζητά ένα οιονεί πολυωνυμικό φράγμα για κάθε σταθερό μήκος προόδου, και αυτός ο στόχος δεν επιτυγχάνεται.

Το σημείο αναφοράς είναι το αποτέλεσμα τριών όρων των Bloom και Sisask για το άθροισμα των αντιστρόφων. Η ποιοτική φθίνουσα πορεία της πυκνότητας από μόνη της δεν παρέχει την αθροισιμότητα που χρειάζεται το επιχείρημα.

Δοκιμάστηκαν πολλές προσεγγίσεις: δομημένα περιβάλλοντα σύνολα, ταυτόχρονη ευθυγράμμιση συχνοτήτων, λήμματα αραιής καταμέτρησης, εξομάλυνση Croot-Sisask, ανύψωση και επανάληψη, γωνίες και εντροπία στην κλίμακα p = log M. Καθεμία συνάντησε ένα ρητά καταγεγραμμένο εμπόδιο.

Ο τελικός υπολογισμός έμεινε ημιτελής, χωρίς λήμμα περιορισμού ή αρχή αραιής καταμέτρησης.

Για τους ιδρυτές και τους τεχνικούς επικεφαλής, το δίδαγμα αφορά τη μέθοδο: ένα κατάστιχο επώνυμων αποτυχιών είναι πιο αξιόπιστο παραδοτέο από ένα σίγουρο προσχέδιο.

Δύο εργασίες, και μόνο για τη μία έγινε ποτέ ισχυρισμός #

Το υλικό χωρίζεται σε δύο εργασίες και αξίζει να κρατήσουμε την κατάστασή τους ξεχωριστή. Η πρώτη αναπτύσσει ένα επιχείρημα για το πρόβλημα του αθροίσματος των αντιστρόφων. Η δεύτερη αναζητά ένα οιονεί πολυωνυμικό φράγμα για κάθε σταθερό μήκος προόδου. Τα ρήματα έχουν σημασία. Η πρώτη εργασία περιγράφεται ως ανάπτυξη ενός επιχειρήματος. Η δεύτερη αναζητά απλώς ένα φράγμα. Τίποτα στα αρχεία δεν λέει ότι ο δεύτερος στόχος επετεύχθη, και θα τον αντιμετωπίζω ως επιδίωξη σε όλο το κείμενο.

Ο βοηθός δεν ξεκινά από το μηδέν. Χρησιμοποιεί το αποτέλεσμα τριών όρων των Bloom και Sisask για το άθροισμα των αντιστρόφων ως αφετηρία. Οτιδήποτε ακολουθεί είναι μια προσπάθεια να προχωρήσει πέρα από αυτή τη βάση, είτε προς μεγαλύτερες προόδους είτε προς μια ισχυρότερη ποσοτική πρόταση. Ο συμβολισμός καθορίζεται από νωρίς. Για κάθε k, το r_k(N) είναι το μεγαλύτερο μέγεθος ενός υποσυνόλου του {1, ..., N} χωρίς μη τετριμμένη πρόοδο k όρων. Ένα σύνολο A πυκνότητας α = |A|/N είναι το αντικείμενο μελέτης, και η κανονικοποιημένη συνάρτηση είναι η f = 1_A/α.

Αυτή η κανονικοποίηση καθοδηγεί τα περισσότερα από όσα ακολουθούν. Ορίζουμε μ = 1_A/α, ώστε E[μ] = 1, και θέτουμε M = α^-1. Η λογαριθμική αραιότητα είναι τότε p = log(1/α), που είναι το ίδιο με το log M. Όσο πιο αραιό είναι το σύνολο, τόσο μεγαλύτερα γίνονται τα M και p. Κάθε εμπόδιο παρακάτω είναι, με τη μία ή την άλλη μορφή, μια δήλωση για το τι συμβαίνει καθώς αυτή η αραιότητα μεγαλώνει.

Η μείωση της πυκνότητας δεν είναι το ίδιο με την αθροισιμότητα #

Το πρώτο εμπόδιο εμφανίζεται στο επίπεδο της αρχιτεκτονικής του επιχειρήματος, πριν από οποιαδήποτε ανάλυση Fourier. Το αρχείο αναφέρει ξεκάθαρα ότι η ποιοτική μείωση της πυκνότητας από μόνη της δεν παρέχει αυτή την αθροισιμότητα. Το να γνωρίζουμε ότι οι πυκνότητες συρρικνώνονται καθώς κινούμαστε μεταξύ κλιμάκων δεν είναι αρκετό. Το πρόβλημα του αθροίσματος των αντιστρόφων απαιτεί η συρρίκνωση να ποσοτικοποιηθεί αρκετά καλά ώστε να αθροίζεται.

Μια δελεαστική διέξοδος είναι μια αναδρομική σχέση. Οι σημειώσεις λένε ότι μια επαρκώς ισχυρή αναδρομική σχέση για ακραίες πυκνότητες χωρίς προόδους θα μπορούσε να αποδώσει αθροισιμότητα σε εκθετικές κλίμακες. Αυτή η πρόταση είναι διατυπωμένη με επιφύλαξη, και έτσι πρέπει να παραμείνει. Περιγράφει τι θα μπορούσε να κάνει μια υποθετική ισχυρή αναδρομή. Δεν αναφέρει ότι βρέθηκε κάποια.

Ένα δεύτερο κόστος είναι ανεξάρτητο από το πρώτο. Ο βοηθός εντοπίζει τη συσσώρευση πολλών ασθενών συσχετίσεων ως ένα επιπλέον κόστος. Κάθε μεμονωμένη συσχέτιση μπορεί να είναι αβλαβής ενώ το άθροισμά τους δεν είναι. Αυτό το θέμα επαναλαμβάνεται: ένα βήμα που είναι φθηνό μία φορά γίνεται ακριβό όταν πρέπει να επαναληφθεί.

Διατήρηση της δομής, και γιατί οι τρεις όροι δεν γενικεύονται #

Μια προτεινόμενη θεραπεία είναι να διατηρείται η δομή. Ο βοηθός προτείνει τη διατήρηση δομημένων περιβαλλόντων συνόλων (ambient sets) μέσα από διαδοχικές αυξήσεις. Η ιδέα, όπως διατυπώνεται με επιφύλαξη στην πηγή, είναι ότι δεν πρέπει να πετάτε το δομημένο σύνολο που βρήκατε σε ένα στάδιο όταν προχωράτε στο επόμενο.

Η περίπτωση των τριών όρων έχει ένα χαρακτηριστικό που στερούνται οι μεγαλύτερες πρόοδοι. Ο μηχανισμός θετικότητας που είναι χρήσιμος για προόδους τριών όρων δεν επεκτείνεται άμεσα σε μεγαλύτερες ριζωμένες καταμετρήσεις. Αυτό είναι το πρώτο από αρκετά σημεία όπου το εμπόδιο αφορά ειδικά το k μεγαλύτερο του τρία. Μια μεταγενέστερη σημείωση κάνει την ίδια παρατήρηση με γενικούς όρους: οι μεγαλύτερες πρόοδοι εισάγουν περαιτέρω εμπόδια ανώτερης τάξης.

Το αρχείο περιλαμβάνει ένα προσχέδιο τανυστικού γινομένου σχετικά με το αν οι σταθερές νόρμες ομοιομορφίας μπορούν να ελέγξουν αραιές κανονικοποιημένες συναρτήσεις. Ο βοηθός δεν ολοκληρώνει το προσχέδιο. Προτιμώ να αναφέρω αυτό παρά να υπονοήσω ότι το ερώτημα έχει λυθεί προς τη μία ή την άλλη κατεύθυνση.

Ευθυγράμμιση συχνοτήτων μία φορά αντί για πολλές #

Η διαδοχική ευθυγράμμιση των συναρτήσεων συχνότητας είναι το σημείο όπου το πρόβλημα της συσσώρευσης δαγκώνει πιο δυνατά. Αν κάθε ευθυγράμμιση κοστίζει λίγο, μια μακρά αλυσίδα από αυτές κοστίζει πολύ. Ο βοηθός προτείνει την ταυτόχρονη ευθυγράμμιση αρκετών συναρτήσεων συχνότητας, αντί της συσσώρευσης απωλειών μέσω διαδοχικής ευθυγράμμισης. Η σημείωση στο περιθώριο το θέτει ωμά: "Καμία επαναληπτική απώλεια αν ευθυγραμμιστούν όλες οι συχνότητες ταυτόχρονα." Όπως και η πρόταση που συνοψίζει, αυτή η φράση έχει επιφύλαξη, επειδή περιγράφει τι θα κέρδιζε η ταυτόχρονη ευθυγράμμιση αν δούλευε.

Η σημείωση δηλώνει στη συνέχεια τι εξακολουθεί να λείπει. Το S_h θα έπρεπε να είναι ανακτήσιμο από συχνότητες με μεγάλες συσχετίσεις, τουλάχιστον exp(-poly). Αυτό παραμένει απαίτηση, όχι αποτέλεσμα. Οι συσχετίσεις που οργανώνονται είναι εκείνες των γινομένων ζευγών f(x)f(x + h), με f = 1_A/α και α = |A|/N.

Ακόμη και αν το δεχτούμε αυτό, ο βοηθός χρειάζεται ακόμα να διατηρήσει τη σχετική συσχέτιση και να ολοκληρώσει το επιχείρημα καταμέτρησης. Έτσι, η ιδέα της ταυτόχρονης ευθυγράμμισης έχει μια ελκυστική ιδιότητα - μηδενικές επαναληπτικές απώλειες - και μια λίστα πραγμάτων που κανείς δεν έχει επαληθεύσει. Μια σχετική προσέγγιση έχει έναν αντίστοιχο περιορισμό. Η αποκοπή σπάνιων συνεκτικών κορυφών λειτουργεί για ανεξάρτητα σμήνη συχνοτήτων, αλλά η επέκταση αυτού του επιχειρήματος σε εξαρτημένα σμήνη παραμένει άλυτη.

Σπάνια κενά κομμάτια και το κόστος της προσαρμοστικής πλήρωσης #

Όταν το επιχείρημα περνά από τη λογιστική της πλευράς Fourier στην πραγματική καταμέτρηση προόδων, εμφανίζεται ένα δομικό πρόβλημα. Ο βοηθός εντοπίζει ένα εμπόδιο: τα άνω φράγματα πυκνότητας σε δομημένα κομμάτια επιτρέπουν σπάνια κενά κομμάτια. Ένα άνω φράγμα στο πόσο από το A βρίσκεται σε ένα κομμάτι δεν λέει τίποτα για το αν βρίσκεται έστω και κάτι από το A εκεί. Ένα κομμάτι που είναι σπάνιο και κενό μπορεί να κάθεται μέσα σε μια οικογένεια κομματιών που όλα ικανοποιούν το φράγμα.

Μια απάντηση είναι η προσαρμοστική πλήρωση (adaptive filling), και έρχεται με τον δικό της λογαριασμό. Η προσαρμοστική πλήρωση εισάγει περαιτέρω συνθήκες εφικτότητας τις οποίες ο βοηθός δεν έχει αποδείξει. Μια φράσσουσα συνάρτηση (majorant) είναι ένας φυσικός τρόπος για να αποκλειστούν τα σπάνια κακά κομμάτια. Το παρατιθέμενο κείμενο του βοηθού λέει ότι μια φράσσουσα σε όλα τα σπάνια άτομα είναι πιθανότατα μη ρεαλιστική. Η παρατήρηση είναι επιφυλακτική, αλλά δείχνει μακριά από την πιο άμεση λύση.

Αυτό είναι το μοτίβο που εξηγεί το υπόλοιπο αρχείο. Ένα φθηνό επιχείρημα χρειάζεται κάπου ένα κάτω φράγμα, τα διαθέσιμα εργαλεία δίνουν άνω φράγματα, και το κενό ανάμεσά τους καταλαμβάνεται από σπάνια, αραιά, κενά πράγματα.

Δανεισμός μηχανισμών αραιής καταμέτρησης, και η διαπίστωση ότι το δανεισμένο μέρος δεν αρκούσε #

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

Σχετικά με την πύκνωση (densification) των Conlon-Fox-Zhao, ο βοηθός διαπίστωσε ότι βασιζόταν σε αμφίπλευρες εκτιμήσεις γραμμικών μορφών. Αυτό έχει σημασία επειδή το πλαίσιο εδώ έχει δομή άνω φράγματος και όχι αμφίπλευρη. Μια μέθοδος χτισμένη σε αμφίπλευρο έλεγχο δεν είναι διαθέσιμη όταν είναι γνωστή μόνο η μία πλευρά.

Το λήμμα καταμέτρησης αραιών γραφημάτων των Filmus, Hatami, Hosseini και Kelman παρείχε το μοντέλο για ασύμμετρες ροπές πλέγματος και θετικά ημιορισμένη απορρύθμιση ισορροπίας. Χρησίμευσε λοιπόν ως πρότυπο, όχι ως έτοιμο θεώρημα προς άμεση εφαρμογή. Ακόμα κι έτσι, η ίδια δυσκολία επέστρεψε. Τα άνω φράγματα από μόνα τους συναντούσαν επανειλημμένα αραιές τρύπες. Μια επιπλέον πτυχή κάνει τις ροπές πλέγματος δύσκολες στην ανάγνωση: οι μεγάλες κεντραρισμένες ροπές πλέγματος θα μπορούσαν να αντανακλούν ελλείπουσα μάζα αντί για συγκέντρωση προς τα πάνω. Μια μεγάλη ροπή μοιάζει με απόδειξη συγκέντρωσης, αλλά μπορεί εξίσου να παραχθεί από μάζα που δεν βρίσκεται εκεί. Αυτή η ασάφεια είναι το πρόβλημα της αραιής τρύπας ιδωμένο από την πλευρά των ροπών.

Στη συνέχεια ο βοηθός εξέτασε μικρές απώλειες δυνάμεων ως προς το M. Δεν απέκτησε κανένα κατάλληλο θεώρημα καταμέτρησης. Αυτό είναι ένα καθαρό αρνητικό αποτέλεσμα, και στενεύει το πεδίο: ακόμη και επιτρέποντας στο επιχείρημα να χάσει μια μικρή δύναμη του M, δεν βρέθηκε κατάλληλο θεώρημα καταμέτρησης.

Η εξομάλυνση ήταν πολύ ακριβή για να εφαρμοστεί #

Η εξομάλυνση Croot-Sisask είναι μια τυπική διαδρομή για την κανονικοποίηση ενός συνόλου πριν από την καταμέτρηση. Ο βοηθός την εξέτασε και βρήκε την απαιτούμενη ακρίβεια υπερβολικά δαπανηρή στην προτεινόμενη εφαρμογή. Η μέθοδος δεν ήταν λάθος. Η τιμή της ξεπερνούσε αυτό που μπορούσε να πληρώσει το επιχείρημα.

Η ίδια οικονομική λογική διέπει και τις άλλες διαδρομές. Για τα επιχειρήματα ινών (fibre arguments), τα φράγματα ινών δεν πολλαπλασιάζονταν αυτόματα, και οι σφαίρες σταθερής νόρμας εμπόδισαν την ελπιζόμενη ισχυρή φθίνουσα πορεία πάνω από σταθερά αλφάβητα ψηφίων. Μια δομή γινομένου υποδηλώνει ότι τα φράγματα στα κομμάτια θα έπρεπε να συνδυάζονται σε ένα φράγμα στο σύνολο, και εδώ δεν συνδυάστηκαν. Η επιχειρούμενη ανύψωση (lifting) και επανάληψη πάλι έχαναν υπερβολικά πολλά ποσοτικά.

Στη συνέχεια εξετάστηκε η προσέγγιση της προσεγγιστικής δυϊκότητας των Ben-Sasson-Ron-Zewi. Ο βοηθός διαπίστωσε ότι η εξεταζόμενη επανάληψη χάνει υπερβολικά πολλά ποσοτικά. Αυτή είναι η ίδια ετυμηγορία με την απόπειρα ανύψωσης, στην οποία κατέληξε από διαφορετική κατεύθυνση, γεγονός που υποδηλώνει ότι το πρόβλημα βρίσκεται στην ίδια την επανάληψη και όχι σε κάποια μεμονωμένη κατασκευή. Θα το κρατήσω αυτό ως παρατήρηση για το μοτίβο, όχι ως αποδεδειγμένη διάγνωση.

Μία γραμμή αισιοδοξίας, και η αριθμητική που την υπονόμευσε #

Το αρχείο περιέχει μια στιγμή φαινομενικής προόδου. Το παρατιθέμενο κείμενο του βοηθού υποστηρίζει ότι οι διακυμάνσεις βαθμού γινομένων αντιμετωπίζονται με πολυωνυμική ακρίβεια, συμπεριλαμβανομένου του θαυμαστικού. Είναι ένας επιφυλακτικός ισχυρισμός, παρατιθέμενος όπως τον έγραψε ο βοηθός.

Ο βοηθός παρατήρησε στη συνέχεια το πρόβλημα με αυτόν. Τα προσημασμένα αναπτύγματα θα μπορούσαν να έχουν απόλυτη μάζα τάξης 2^p, η οποία κατακλύζει την πολυωνυμική ακρίβεια. Θυμηθείτε ότι p = log M. Η πολυωνυμική ακρίβεια ως προς το M είναι ένας μετριοπαθής στόχος, ενώ ένα προσημασμένο ανάπτυγμα με μάζα τάξης 2^p είναι εκθετικά μεγαλύτερο. Η ακρίβεια είναι πραγματική, αλλά η αλληλοαναίρεση στην οποία βασίζεται δεν μπορεί να απορροφήσει τόση μάζα.

Βρίσκω αυτή την εγγραφή την πιο διδακτική στο κατάστιχο, επειδή δείχνει τον αυτοέλεγχο να λειτουργεί. Ένας ισχυρισμός που έγινε με θαυμαστικό άνοιξε ξανά, και η αριθμητική από την οποία εξαρτιόταν βρέθηκε ελλιπής. Έτσι μοιάζει ένα έντιμο αρχείο εργασίας. Ο ενθουσιασμός και η διόρθωση βρίσκονται και τα δύο στο ίδιο έγγραφο.

Οι γωνίες και τα κουτιά δεν συναρμολογούνται σε μεγαλύτερες προόδους #

Μια διαφορετική στρατηγική ήταν να χρησιμοποιηθεί ένα ισχυρότερο γνωστό αποτέλεσμα ως σκαλοπάτι. Το οιονεί πολυωνυμικό φράγμα γωνιών (corners) είναι το σχετικό εργαλείο, αλλά οι γωνίες που προέκυψαν δεν συναρμολογούσαν αυτόματα μεγαλύτερες προόδους. Μια γωνία είναι ένα δισδιάστατο μοτίβο και μια μακρά πρόοδος είναι ένα μονοδιάστατο, και το πέρασμα ανάμεσά τους δεν είναι αυτόματο.

Η καταμέτρηση κουτιών τεσσάρων όρων παρουσιάζει μια συναφή δυσκολία. Η θετικότητα της καταμέτρησης κουτιών τεσσάρων όρων δεν έλεγχε την εξαιρετική διαγώνιό της. Μια θετική καταμέτρηση μπορεί ακόμα να κυριαρχείται από εκφυλισμένες διαμορφώσεις, και η διαγώνιος είναι εκεί όπου ζουν αυτές.

Οι σημειώσεις προσφέρουν όντως έναν πιθανό δρόμο προς τα εμπρός, προσεκτικά διατυπωμένο. Οι πλήρεις νόρμες κουτιού (box norms) προσφέρουν έναν πιθανό μηχανισμό για το αν οι άνω καταμετρήσεις από μόνες τους μπορούν να επιβάλουν κάτω καταμετρήσεις προόδων. Αυτό το ερώτημα, αν η μονόπλευρη πληροφορία μπορεί να επιβάλει ένα κάτω φράγμα, είναι εκείνο γύρω από το οποίο γυρίζει ολόκληρο το έργο. Ωστόσο, υπάρχει ένα όριο στο πόσο μακριά εκτείνεται αυτό. Οι αρνητικές κυβικές συνεισφορές εμποδίζουν μια ευθεία επέκταση σε συστήματα προόδων.

Μετάβαση στην εντροπία στην κλίμακα p = log M #

Με τις άμεσες διαδρομές καταμέτρησης μπλοκαρισμένες, η έρευνα στράφηκε προς την εντροπία στην κλίμακα p = log M, αντλώντας από τη χρήση υψηλών ροπών των Kelley-Meka. Η επιλογή της κλίμακας δεν είναι αυθαίρετη: το p = log M είναι ακριβώς η λογαριθμική αραιότητα που ορίστηκε στην αρχή.

Το παρατιθέμενο κείμενο του βοηθού προτείνει τη χρήση της εντροπίας αντί του L2 μέσω της μη αρνητικότητας και της διαχωριστικότητας συχνοτήτων (Chang). Αυτό είναι πρόταση, όχι αποτέλεσμα. Η λογική είναι ότι το μ = 1_A/α είναι μη αρνητικό, και η διαχωριστικότητα (dissociativity) της Chang δίνει δομή στην πλευρά των συχνοτήτων, οπότε η εντροπία θα μπορούσε να κάνει τη δουλειά που δεν μπορεί να κάνει μια ποσότητα L2.

Για να λειτουργήσει αυτό, ο βοηθός χρειαζόταν μια συγκεκριμένη αναλυτική είσοδο. Ο βοηθός αναζήτησε μια εκτίμηση περιορισμού Fourier ||g_hat||_q = O(1) για φραγμένη g και σταθερό q > 2, υπό κατάλληλα τοπικά άνω φράγματα. Αυτό ήταν ένας στόχος. Δεν τεκμηριώθηκε.

Το εμπόδιο εμφανίστηκε στο επόμενο βήμα. Η εξαγωγή δομής από υψηλές ροπές έχανε υπερβολικά πολλή μάζα. Οι υψηλές ροπές είναι εκεί όπου τα επιχειρήματα τύπου Kelley-Meka αποκτούν τη δύναμή τους, και εδώ ήταν επίσης εκεί όπου το επιχείρημα έχασε αυτό που έπρεπε να κρατήσει.

Ο υπολογισμός που έφτασε πιο κοντά #

Ο τελικός υπολογισμός αξίζει τη δική του ματιά, επειδή έχει τόσο μια επιτυχία όσο και μια αποτυχία. Φτάνει σε ένα πλήρες συνοριακό φράγμα υπό τις υποθέσεις συνέλιξής του. Αυτό είναι ένα πραγματικό αποτέλεσμα, διατυπωμένο ως τέτοιο, και φέρει τον προσδιορισμό "υπό τις υποθέσεις συνέλιξής του". Το φράγμα ισχύει όταν ισχύουν αυτές οι υποθέσεις.

Αλλά αποτυγχάνει να περάσει το κατώφλι του εκθέτη τρία που χρειάζεται το προτεινόμενο επιχείρημα καταμέτρησης. Το απόσπασμα του βοηθού σημειώνει ένα ασθενές φράγμα l3 από τη συνέλιξη και την αποκοπή (cap), και ότι απαιτείται ένας αυστηρά καλύτερος εκθέτης (κάτω από το 3) για την παρεμβολή. Με απλά λόγια, ο υπολογισμός προσγειώνεται ακριβώς στη λάθος πλευρά μιας γραμμής. Ένα φράγμα στον εκθέτη τρία δεν είναι αρκετό, και η παρεμβολή χρειάζεται κάτι αυστηρά καλύτερο.

Είναι δελεαστικό να διαβάσει κανείς μια τέτοια οριακή αστοχία ως "σχεδόν φτάσαμε". Θα αντιστεκόμουν σε αυτό. Το αρχείο δεν λέει πόσο απέχει ο υπολογισμός από το κατώφλι, και ένα κενό που είναι ένας μόνο εκθέτης μπορεί ακόμα να είναι ολόκληρο το πρόβλημα. Αυτό που λέει το αρχείο είναι ότι ο βοηθός άφησε τον υπολογισμό ημιτελή, χωρίς να εξαγάγει ούτε το λήμμα περιορισμού ούτε την αρχή της αραιής καταμέτρησης. Αυτά τα δύο κομμάτια που λείπουν είναι το ανοιχτό χρέος του έργου.

Τι αξίζει το κατάστιχο #

Θα ήταν εύκολο να απορρίψει κανείς αυτή την προσπάθεια ως αποτυχημένη. Νομίζω ότι αυτό διαβάζει λάθος τα στοιχεία, για έναν λόγο που ισχύει πολύ πέρα από τη θεωρία αριθμών.

Το έγγραφο είναι συγκεκριμένο. Ονομάζει το εμπόδιο σε κάθε διασταύρωση: σπάνια κενά κομμάτια, ελλείπουσα μάζα στις ροπές πλέγματος, αμφίπλευρες εκτιμήσεις στους Conlon-Fox-Zhao, εκθετική ως προς το p προσημασμένη μάζα, η εξαιρετική διαγώνιος της καταμέτρησης κουτιών τεσσάρων όρων, αρνητικές κυβικές συνεισφορές. Διακρίνει έναν αποδεδειγμένο περιορισμό από έναν ελπιζόμενο μηχανισμό. Σημειώνει την αναδρομή για την αθροισιμότητα ως κάτι που θα μπορούσε να λειτουργήσει, και τη δεύτερη εργασία ως κάτι που αναζητείται. Λέει τι δεν ολοκλήρωσε ο βοηθός.

Για έναν ιδρυτή ή έναν τεχνικό επικεφαλής που αξιολογεί έρευνα υποβοηθούμενη από τεχνητή νοημοσύνη, αυτό είναι που πρέπει να αναζητά. Ένα σύστημα που επιστρέφει ένα σίγουρο, φαινομενικά πλήρες επιχείρημα είναι δύσκολο να ελεγχθεί. Ένα σύστημα που επιστρέφει μια λίστα επώνυμων αποτυχιών, με τη μία σχεδόν επιτυχία καθαρά σημειωμένη ότι υπολείπεται ενός κατωφλίου, μπορεί να ελεγχθεί γραμμή προς γραμμή. Κάποιος μπορεί να αναλάβει το πρόβλημα του εκθέτη τρία, ή το πρόβλημα των εξαρτημένων σμηνών, και να γνωρίζει ποια είναι η θέση εκκίνησης.

Υπάρχει επίσης ένα μοτίβο που αξίζει να διατυπωθεί άμεσα. Πολλές από τις αποτυχίες είναι αποτυχίες συσσώρευσης: ασθενείς συσχετίσεις που αθροίζονται, διαδοχικές ευθυγραμμίσεις που πολλαπλασιάζονται, επανάληψη που χάνει υπερβολικά πολλά, φράγματα ινών που αποτυγχάνουν να πολλαπλασιαστούν. Μια προτεινόμενη θεραπεία στοχεύει ακριβώς αυτό, ευθυγραμμίζοντας τις συχνότητες ταυτόχρονα ώστε να μην προκύπτει επαναληπτική απώλεια. Είναι διατυπωμένη με επιφύλαξη, και η προϋπόθεσή της, η ανάκτηση του S_h από συχνότητες με μεγάλες συσχετίσεις, είναι αναπόδεικτη. Ωστόσο, είναι η πρόταση στο αρχείο που απαντά πιο άμεσα στο πιο συχνό παράπονο.

Το ανοιχτό ερώτημα που θέτει το αρχείο είναι επομένως στενό και ελέγξιμο. Μπορεί να ληφθεί ένα φράγμα αυστηρά καλύτερο από τον εκθέτη τρία υπό τις υποθέσεις συνέλιξης που ήδη δίνουν το συνοριακό φράγμα; Αν ναι, η παρεμβολή έχει κάτι με το οποίο μπορεί να δουλέψει. Αν όχι, η διαδρομή του περιορισμού Fourier και η αρχή της αραιής καταμέτρησης, κανένα από τα οποία δεν έχει εξαχθεί, είναι τα επόμενα μέρη που πρέπει να κοιτάξουμε.

Συχνές Ερωτήσεις #

Ποια ήταν τα δύο μαθηματικά προβλήματα που ερεύνησε ο βοηθός τεχνητής νοημοσύνης;

Ο βοηθός εργάστηκε σε δύο σχετικές εργασίες που αφορούν σύνολα χωρίς αριθμητικές προόδους: την ανάπτυξη ενός επιχειρήματος για το πρόβλημα του αθροίσματος των αντιστρόφων και την αναζήτηση ενός οιονεί πολυωνυμικού φράγματος για κάθε σταθερό μήκος προόδου k. Ενώ χρησιμοποίησε το αποτέλεσμα τριών όρων των Bloom και Sisask ως σημείο αναφοράς, το οιονεί πολυωνυμικό φράγμα για αυθαίρετα μήκη προόδου δεν επετεύχθη.

Γιατί τα άνω φράγματα πυκνότητας απέτυχαν να παραγάγουν το απαιτούμενο λήμμα καταμέτρησης;

Τα άνω φράγματα πυκνότητας σε δομημένα κομμάτια επιτρέπουν σπάνια κενά κομμάτια, πράγμα που σημαίνει ότι ένα άνω φράγμα στο πόσο μέρος ενός συνόλου A βρίσκεται μέσα σε ένα κομμάτι δεν εγγυάται ότι υπάρχουν στοιχεία του A εκεί. Σε πολλαπλές προσπάθειες, τα άνω φράγματα από μόνα τους συναντούσαν επανειλημμένα αραιές τρύπες, και οι μεγάλες κεντραρισμένες ροπές πλέγματος θα μπορούσαν να αντανακλούν ελλείπουσα μάζα αντί για συγκέντρωση προς τα πάνω.

Πού κόλλησε ο τελικός υπολογισμός;

Ο τελικός υπολογισμός έφτασε σε ένα πλήρες συνοριακό φράγμα υπό τις δηλωμένες υποθέσεις συνέλιξής του, αλλά παρήγαγε μόνο ένα ασθενές φράγμα l3 που απέτυχε να περάσει το κατώφλι του εκθέτη αυστηρά κάτω του τρία που απαιτείται για την παρεμβολή. Ο βοηθός άφησε τον υπολογισμό ημιτελή χωρίς να εξαγάγει ούτε το λήμμα περιορισμού Fourier ούτε την αρχή της αραιής καταμέτρησης.

Βιβλιογραφία #

Thomas F. Bloom and Olof Sisask, (2020). Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions ⧉. arXiv.
Zander Kelley and Raghu Meka, (2023). Strong Bounds for 3-Progressions ⧉. arXiv.
David Conlon, Jacob Fox, and Yufei Zhao, (2014). A relative Szemerédi theorem ⧉. Geometric and Functional Analysis.
Ernie Croot and Olof Sisask, (2010). A probabilistic technique for finding almost-periods of convolutions ⧉. Geometric and Functional Analysis.

Τελευταία αναθεώρηση 2026-11-01.

Αναδημοσίευση αυτού του άρθρου

Η επίθεση μιας τεχνητής νοημοσύνης σε σύνολα χωρίς αριθμητικές προόδους: ένα κατάστιχο όσων βάλτωσαν — Sebastien Rousseau

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

Αυτό το άρθρο διατίθεται με άδεια Creative Commons Attribution 4.0 International. Η αναδημοσίευση απαιτεί αναφορά στην κανονική διεύθυνση URL.

Η επίθεση μιας τεχνητής νοημοσύνης σε σύνολα χωρίς αριθμητικές προόδους: ένα κατάστιχο όσων βάλτωσαν — Sebastien Rousseau

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

Originally published at https://sebastienrousseau.com/el/2026-10-24-epithesi-mias-technitis-noimosynis-se-synola/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER