A Salem-Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, ein Rätsel in einer riesigen, unendlichen Stadt zu lösen, die ganz aus Gitternetzpunkten besteht. Diese Stadt ist die Welt der Mathematik, genauer gesagt eines Zweigs namens Kombinatorik, bei dem es um das Zählen, Anordnen und Finden von Mustern diskreter Objekte geht. In dieser Stadt sind die „Straßen“ einfach nur Zahlen, und die „Gebäude“ sind Punkte, an denen zwei Zahlen aufeinandertreffen, wie $(x, y)$-Koordinaten auf einer Karte.

Das vorliegende Rätsel folgt einer ganz speziellen Regel: Sie wollen das größtmögliche Viertel (eine Teilmenge von Punkten) bauen, in dem eine bestimmte Form streng verboten ist. Diese Form ist ein gleichschenkliges rechtwinkliges Dreieck. Sie kennen diese Dreiecke gut: Sie haben eine Ecke, die einen perfekten 90-Grad-Winkel bildet (wie die Ecke eines Blatt Papiers), und die beiden Seiten, die an dieser Ecke ansetzen, sind exakt gleich lang. Die Frage, die Mathematiker schon seit langem beschäftigt, lautet: Wie groß kann ein Viertel werden, bevor man versehentlich eines dieser verbotenen Dreiecke baut?

Dies ist nicht nur ein Spiel der Geometrie; es ist ein tiefgründiges Rätsel, das mit der Art und Weise verbindet, wie Zahlen funktionieren, wie sie Daten verschlüsseln und sogar, wie wir die Struktur des Universums verstehen. Wenn Sie ein riesiges Viertel ohne Dreiecke finden können, bedeutet das, dass es verborgene, komplexe Wege gibt, Zahlen anzuordnen, um einfache Muster zu vermeiden. Jahrzehntelang wussten Mathematiker, dass die Antwort irgendwo zwischen „sehr groß“ und „fast der gesamten Stadt“ lag, aber die Lücke zwischen dem kleinstmöglichen großen Viertel und dem größten möglichen war enorm. Es war, als wüsste man, dass eine Schatzkiste irgendwo in einer Wüste liegt, aber man wüsste nicht, ob sie unter einem einzelnen Sandkorn oder unter einem Berg aus Gold vergraben ist.

---

Die große Entdeckung des Papers: Ein neuer Weg, um „dreieckfreie“ Städte zu bauen

In diesem Paper haben die beiden Mathematiker Gyula Károlyi und Józef Solymosi ein massives neues Viertel gebaut, das viel größer ist, als man es zuvor für möglich gehalten hatte. Es gelang ihnen, eine Teilmenge von Punkten in einem Gitter zu konstruieren, die gleichschenklige rechtwinklige Dreiecke vermeidet, und ihre Konstruktion ist so groß, dass sie beweist, dass die Größe eines solchen Viertels mit einer Rate von etwa $n^{1.3}$ (wobei $n$ die Größe des Gitters ist) wächst.

Um zu verstehen, wie sie das geschafft haben, stellen Sie sich vor, Sie versuchen, einen Turm aus Blöcken zu bauen, haben aber eine strikte Regel: Sie dürfen die Blöcke nicht so stapeln, dass eine bestimmte „schlechte“ Form entsteht. In der Vergangenheit versuchten Mathematiker, diese Türme zu bauen, indem sie Blöke auswählten, die für sich allein genommen völlig sicher waren. Doch Károlyi und Solymosi erkannten, dass sie klüger vorgehen konnten. Sie verwendeten eine Technik, die sie „Peeling“ (Schälen) nennen, was wie ein Jenga-Spiel ist, bei dem man einen etwas wackeligen Turm haben kann, solange man die Blöcke nacheinander in einer bestimmten Reihenfolge entfernen kann, bis das Ganze sicher ist.

Die magischen Zutaten

Die Autoren verwendeten einige clevere Tricks, um dies zu erreichen:

1. Die Gaußschen Zahlen (Das „magische Gitter“): Anstatt normale Zahlen zu verwenden, nutzten sie eine spezielle Art von Zahlen, die Gaußsche ganze Zahlen genannt werden. Man kann sie sich als Punkte auf einem Gitter vorstellen, bei denen jeder Punkt eine „x“-Koordinate und eine „y“-Koordinate hat, aber sie werden als eine einzige magische Zahl behandelt. Dies ermöglichte es ihnen, ihre Blöcke auf eine Weise zu rotieren und zu verschieben, die mit normalen Zahlen nicht möglich wäre.
2. Das „übertragsfreie“ Alphabet: Wenn man Zahlen addiert, gibt es manchmal einen „Übertrag“ (wie bei $9 + 1 = 10$, wobei die 1 übertragen wird). Die Autoren fanden eine spezielle Menge von „Ziffern“ (eine kleine Gruppe von Punkten), bei denen, wenn man sie addiert, um ein Dreieck zu bilden, die Mathematik niemals in die nächste Ebene „überträgt“. Dies hält die lokalen Regeln einfach.
3. Die Peeling-Reihenfolge (Die Geheimzutat): Dies ist der innovativste Teil. Sie fanden eine Gruppe von 281 Punkten, die – wenn man sie alle gleichzeitig betrachtet – Dreiecke enthalten. Sie entdeckten jedoch eine spezifische Reihenfolge, um diese Punkte zu entfernen. Wenn man den ersten Punkt entfernt, bleiben keine Dreiecke mehr mit diesem Punkt als Ecke bestehen. Dann entfernt man den nächsten, und so weiter. Bis man fertig ist, ist die verbleibende Menge vollkommen sicher. Es ist wie ein Raum voller Menschen, in dem alle Händchen haltend in einem Kreis stehen, aber wenn man sie in einer bestimmten Reihenfolge bittet zu gehen, bricht der Kreis auseinander, bevor jemand zu Schaden kommt.

Das Ergebnis: Ein riesiger Sprung nach vorn

Unter Verwendung eines leistungsfähigen KI-Werkzeugs namens AlphaEvolve (das ihnen half, durch Millionen von Möglichkeiten zu suchen, um die perfekte Anordnung zu finden), fanden sie eine „Peeling-Reihenfolge“ für eine Menge von 281 Punkten.

Als sie ihre Methode auf ein Gitter der Größe $n$ anwandten, bewiesen sie, dass man eine dreieckfreie Teilmenge mit einer Größe von mindestens $n^{1.3178...}$ finden kann.

Um dies einzuordnen:

• Vorher war die beste bekannte untere Schranke (Lower Bound) viel kleiner (etwa $n^{1.05}$).
• Die beste bekannte obere Schranke (Upper Bound – das theoretische Limit, wie groß es maximal sein könnte) liegt bei etwa $n^2$ dividiert durch einige logarithmische Faktoren.
• Ihr Ergebnis, $n^{1.3}$, schließt eine signifikante Lücke und zeigt, dass diese dreieckfreien Viertel viel größer sein können, als bisher vermutet wurde.

Was sie nicht getan haben

Es ist wichtig anzumerken, was dieses Paper nicht behauptet. Sie haben nicht bewiesen, dass $n^{1.3}$ die absolut maximale mögliche Größe ist. Sie haben nicht das „perfekte“ Viertel gefunden, das mathematisch gesehen so groß wie möglich wäre. Sie haben auch nicht bewiesen, dass 281 die größte mögliche Anzahl von Punkten ist, die sie in ihrer spezifischen Methode verwenden könnten; sie haben lediglich eine sehr gute Zahl gefunden.

Das Paper stellt explizit fest, dass es immer noch eine „große Lücke“ zwischen ihrer neuen unteren Schranke ($n^{1.3}$) und der oberen Schranke ($n^2$) gibt. Das Rätsel ist nicht vollständig gelöst, aber sie haben definitiv ein viel größeres Stück des Puzzles gefunden als jeder andere zuvor.

Das Fazlelement

Dieses Paper ist ein Triumph der Kombination aus klassischer mathematischer Logik und moderner KI-Suche. Indem sie Zahlen als Punkte auf einem Gitter behandelten, eine spezielle „übertragsfreie“ Zone fanden und eine clevere „Peeling“-Strategie nutzten, um gefährliche Punkte nacheinander zu entfernen, haben die Autoren gezeigt, dass wir viel größere „dreieckfreie“ Städte bauen können, als wir dachten. Es ist ein lebendiges Beispiel dafür, wie eine neue Perspektive – das Problem nicht als statische Wand, sondern als dynamischen Prozess der Entfernung zu betrachten – neue Möglichkeiten in der Welt der Zahlen erschließen kann.