🔢 mathematics

A sharp 5/8 bound for an Erd\H{o}s-Sós pairwise-sums problem

Diese Arbeit löst das Erdős-Problem 865, indem sie beweist, dass die minimale Größe $f_3(N)$ , die erforderlich ist, damit eine Teilmenge von $\{1,\dots,N\}$ drei verschiedene Elemente enthält, deren paarweise Summen ebenfalls in der Menge liegen, genau $5N/8 + O(1)$ beträgt, wodurch eine scharfe Schranke etabliert wird, die mit einer bekannten Konstruktion übereinstimmt.

Ursprüngliche Autoren: Ricky Cipollini

Veröffentlicht 2026-06-30

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ricky Cipollini

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Die „Keine-Drei-Teams“-Regel

Stellen Sie sich vor, Sie organisieren eine Party mit Gästen, die von 1 bis $N$ nummeriert sind. Sie möchten so viele Leute wie möglich einladen, aber Sie haben eine sehr strenge Regel: Sie dürfen nicht drei Gäste haben (nennen wir sie Alice, Bob und Charlie), bei denen, wenn man sie paarweise kombiniert, deren „kombinierte Zahlen“ ebenfalls Gäste auf der Party sind.

Zum Beispiel: Wenn Alice die Nummer 2 hat und Bob die Nummer 3, ist ihre Summe die 5. Wenn die 5 auch auf der Party ist, gibt das ein Problem. Die Regel besagt: Sie dürfen kein Trio haben, bei dem jedes mögliche Paar (Alice+Bob, Alice+Charlie, Bob+Charlie) zu einer Zahl führt, die ebenfalls ein Gast auf der Party ist.

Mathematiker nennen dies ein „paarweise-Summen-Trio“. Die Arbeit stellt eine einfache Frage: Wie viele Menschen können Sie zu dieser Party einladen, bevor Sie versehentlich eines dieser verbotenen Trios erschaffen?

Die Antwort: Der 5/8-Schwellenwert

Die Arbeit löst ein berühmtes Rätsel (Erdős Problem 865), indem sie eine präzise Grenze beweist.

Betrachten Sie die Gesamtzahl der Gäste ( $N$ ) als eine riesige Pizza. Die Arbeit beweist, dass Sie mehr als 5/8 der Pizza (plus einen winzigen, vernachlässigbaren Krümel) einladen können, ohne ein verbotenes Trio zu erhalten.

Die untere Schranke (Die „schlechte“ Konstruktion): Die Autoren zeigen einen spezifischen Weg auf, um genau 5/8 der Gäste einzuladen, ohne die Regel zu brechen. Sie tun dies, indem sie Leute aus zwei spezifischen Pizzastücken einladen:
1. Das Stück von 1/8 bis 1/4 des Weges.
2. Das Stück von 1/2 bis zum ganz am Ende.
  Wenn Sie nur Leute aus diesen zwei Zonen auswählen, landen deren „Summen“ nie wieder auf der Gästeliste. Dies beweist, dass Sie 5/8 erreichen können.
Die obere Schranke (Der „gute“ Beweis): Die Hauptarbeit des Papers besteht darin zu beweisen, dass Sie nicht höher als 5/8 gehen können. Wenn Sie versuchen, auch nur eine einzige Person mehr als diesen 5/8-Markenpunkt einzuladen, garantiert die Mathematik, dass ein verbotenes Trio auftaucht.

Die Antwort ist also exakt 5/8. Es ist eine scharfe, präzise Linie im Sand.

Wie sie es bewiesen haben: Der „Falt“-Trick

Um zu beweisen, dass man nicht höher als 5/8 gehen kann, nutzen die Autoren einen cleveren mentalen Trick namens „Falten“.

Stellen Sie sich Ihre Gästeliste als einen langen Papierstreifen vor.

Wählen Sie einen Pivot: Wählen Sie einen bestimmten Gast (nennen wir ihn den „Pivot“), der in der Mitte steht.
Falten Sie das Papier: Stellen Sie sich vor, Sie falten den Papierstreifen so, dass die Zahlen unterhalb der Pivot-Linie mit den Zahlen oberhalb der Linie zur Deckung kommen.
- Wenn der Pivot der Gast #100 ist, faltet sich Gast #101 auf #99, #102 auf #98 und so weiter.
Die Kollision: Wenn Sie das Papier falten, landen einige Zahlen vielleicht direkt übereinander. Die Autoren analysieren, was passiert, wenn diese „gefalteten“ Zahlen miteinander interagieren.

Sie entdeckten, dass wenn Sie zu viele Gäste haben, die „gefalteten“ Zahlen eine mathematische Kollision erzeugen, die die Existenz eines verbotenen Trios erzwingt. Es ist wie der Versuch, zu viele Koffer in ein Auto zu packen; irgendwann zwingt die Geometrie des Autos zwei Koffer dazu, gegeneinander zu prallen.

Die „schlanke“ Formalisierung (Der Roboter-Check)

In der Arbeit wird erwähnt, dass ein Teil des Beweises durch ein Computerprogramm namens Lean 4 überprüft wurde.

Betrachten Sie den Beweis als eine komplexe Brücke. Die Autoren haben sie von Hand gebaut. Dann haben sie die Blaupausen einem superpräzisen Roboter (Lean) übergeben, um jede einzelne Schraube und jeden Balken zu prüfen. Der Roboter bestätigte, dass die Brücke stabil ist, ohne versteckte Risse oder Momente des Typs „Entschuldigung, ich habe einen Schritt vergessen“. Dies gibt der mathematischen Gemeinschaft zusätzliches Vertrauen, dass die 5/8-Grenze absolut korrekt ist.

Zusammenfassung

Das Problem: Wie viele Zahlen kann man von 1 bis $N$ auswählen, ohne ein spezifisches „Summen-Trio“ zu erzeugen?
Das Ergebnis: Man kann bis zu 5/8 der Zahlen auswählen. Wenn man mehr als 5/8 wählt, ist man mathematisch dazu verdammt, das Trio zu erschaffen.
Die Methode: Sie verwendeten eine „Falt“-Techn Technik, um zu zeigen, dass jeder Versuch, dieses Limit zu überschreiten, zu einem logischen Widerspruch führt.
Die Bedeutung: Dies löst ein jahrzehntealtes Problem (Erdős Problem 865) und bestätigt, dass die „5/8“-Grenze die absolut bestmögliche Antwort ist.

Technisches Resümee: Eine scharfe 5/8-Schranke für ein Erdős–Sós-Problem über paarweise Summen

Problemstellung
Die Arbeit befasst sich mit einem spezifischen Fall der Erdős–Sós-Vermutung bezüglich paarweiser Summen. Sei $f_3(N)$ die kleinste Ganzzahl, sodass jede Teilmenge $A \subseteq \{1, \dots, N\}$ mit $|A| \geq f_3(N)$ distinkte Elemente $a, b, c \in A$ enthält, die die Bedingung erfüllen, dass ihre paarweisen Summen $a+b$ , $a+c$ und $b+c$ alle in $A$ enthalten sind. Eine solche Menge wird als „paarweise-summen-tripel-frei“ bezeichnet, wenn kein solches Tripel existiert. Das zentrale Problem besteht darin, das asymptotische Verhalten von $f_3(N)$ zu bestimmen.

Vor dieser Arbeit zeigte eine Standardkonstruktion $A = [\frac{N}{8}, \frac{N}{4}] \cup [\frac{N}{2}, N]$ , dass $f_3(N) \geq \frac{5}{8}N + O(1)$ . Ziel des Papers ist es, die passende obere Schranke zu beweisen, wodurch das Erdős-Problem 865 gelöst und die exakte asymptotische Konstante etabliert wird.

Methodik
Der Beweis ist in sich abgeschlossen und stützt sich auf eine Kombination aus kombinatorischer Induktion, additiver Zahlentheorie und einer „Faltungstechnik“. Die Methodik vollzieht sich durch folgende wesentliche Schritte:

Das gefaltete additive Lemma (Lemma 2.1):
Die Autoren etablieren zunächst ein Lemma für ein „gefaltetes“ Intervall. Für eine Menge $B \subseteq \{1, \dots, m-1\}$ , bei der keine zwei distinkten Elemente zu $m$ oder zu einem anderen Element in $B$ (modulo $m$ ) summieren, begrenzt das Lemma die Größe von $B$ relativ zur Menge der „Kollisionen“ $C(B)$ . Speziell beweist es, dass $|B| - |C(B)| \leq \frac{m}{4} + 2$ . Der Beweis nutzt Reflexionssymmetrie ( $B \to -B$ ) und ein induktives Argument über $|B|$ , wobei Fälle analysiert werden, in denen die Summe der zwei kleinsten Elemente entweder in $C(B)$ liegt oder nicht.
Das Faltungs-Lemma (Lemma 3.1):
Die Autoren führen eine „Faltungsoperation“ um ein Pivot-Element $h \in A$ ein. Durch die Partitionierung der Menge $A$ in Elemente kleiner als $h$ ( $X$ ) und Elemente der Form $h+r$ mit $r < h$ ( $Y$ ), setzen sie die Größe von $A$ in Beziehung zur Struktur des Schnitts $B_h = X \cap Y$ . Das Lemma zeigt, dass, falls $A$ tripelfrei ist, die Summe der Größen $|X| + |Y|$ durch $\frac{5}{4}h - |E \setminus C(B_h)| + 1$ beschränkt ist, wobei $E$ die „Lücken“ im Intervall $[1, h-1]$ darstellt. Dieser Schritt reduziert das Problem der globalen Mengengröße effektiv auf die Analyse lokaler additiver Eigenschaften modulo $h$ .
Induktive obere Schranke (Abschnitt 4):
Das Haupttheorem wird mittels starker Induktion über $H$ (wobei $N=2H$ ) bewiesen. Der Beweis unterteilt sich in zwei Fälle basierend auf der Lücke zwischen dem größten Element in der unteren Hälfte des Intervalls und dem kleinsten Element in der oberen Hälfte:

Fall 1 ( $s \leq 4e$ ): Die Menge wird um das Pivot $h = q$ (das kleinste Element in der oberen Hälfte) gefaltet. Die Autoren zeigen, dass die Lücke zwischen dem unteren und oberen Teil von $A$ eine hinreichende Anzahl an „fehlenden“ Elementen ( $|E \setminus C(B_h)|$ ) erzwingt, um die Schranke zu erfüllen.
Fall 2 ( $s > 4e$ ): Die Menge wird um $h = p$ (das größte Element in der unteren Hälfte) gefaltet. Hier impliziert die große Lücke, dass der untere Teil der Menge spärlich besetzt ist. Die Autoren wenden das Induktionshypothese auf das untere Segment an und kombinieren dies mit dem Faltungs-Lemma, um die Schranke abzuleiten.

Wesentliche Beiträge und Ergebnisse

Scharfe obere Schranke: Das Paper beweist, dass für alle $N$ jede Teilmenge $A \subseteq [1, N]$ mit $|A| \geq \frac{5}{8}N + C$ (für eine absolute Konstante $C$ ) ein paarweise-summen-tripel enthält.
Lösung von Erdős-Problem 865: Durch die Kombination der neuen oberen Schranke mit der bestehenden Konstruktion für die untere Schranke etabliert das Paper, dass $f_3(N) = \frac{5}{8}N + O(1)$ . Dies bestätigt, dass die Konstante $5/8$ optimal ist.
Formalisierung: Die Autoren merken an, dass eine frühere konditionale Version der Reduktion von einer gröberen Schranke auf die scharfe Schranke in Lean 4/Mathlib formalisiert wurde. Diese Formalisierung verwendet keine „Sorries“ (Platzhalter) und keine zusätzlichen Axiome, wodurch die logische Korrektheit der Reduktionsschritte verifiziert wird.
Verfeinerte Vermutung: Das Paper erwähnt eine schärfere konjekturale Formel, die von Stijn Cambie vorgeschlagen wurde, welche die exakte maximale Größe für spezifische $N$ modulo 8 betrifft, wenngleich das primäre Resultat die asymptotische $5/8$ -Schranke bleibt.

Bedeutung
Das Paper beansprucht, das Erdős-Problem 865 zu lösen, indem es einen in sich geschlossenen Beweis für die scharfe $5/8$ -Schranke liefert. Seine Bedeutung liegt darin, die Lücke zwischen der bekannten Konstruktion und dem theoretischen Limit für dieses spezifische paarweise-summen-Problem zu schließen. Die Arbeit wird als vollständiger mathematischer Beweis präsentiert, ergänzt durch die zusätzliche Stringenz einer formalisierten Reduktion in Lean, was die Gültigkeit der kombinatorischen Argumente ohne Rückgriff auf unbestätigte Annahmen sicherstellt. Die Autoren geben explizit an, dass der Beweis in sich abgeschlossen ist und alle impliziten Konstanten absolut sind.