🔢 mathematics

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

Dit artikel lost Erdős Probleem 865 op door te bewijzen dat de minimale omvang $f_3(N)$ die vereist is voor een deelverzameling van $\{1,\dots,N\}$ om drie verschillende elementen te bevatten waarvan de paarwijze sommen eveneens in de deelverzameling liggen, exact $5N/8 + O(1)$ is, waarmee een scherpe grens wordt vastgesteld die overeenkomt met een bekende constructie.

Oorspronkelijke auteurs: Ricky Cipollini

Gepubliceerd 2026-06-30

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ricky Cipollini

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Grote Visie: De "Geen Drie Teams"-regel

Stel je voor dat je een feestje organiseert met gasten genummerd van 1 tot $N$ . Je wilt zoveel mogelijk mensen uitnodigen, maar je hebt een zeer strikte regel: Je mag geen drie gasten hebben (laten we ze Alice, Bob en Charlie noemen) zodanig dat als je ze aan elkaar koppelt, hun "gecombineerde nummers" ook gasten op het feestje zijn.

Bijvoorbeeld, als Alice #2 is en Bob #3, dan is hun som #5. Als #5 ook op het feestje is, is dat een probleem. De regel luidt: Je mag geen trio hebben waarbij elke mogelijke paar (Alice+Bob, Alice+Charlie, Bob+Charlie) resulteert in een nummer dat ook een gast op het feestje is.

Wiskundigen noemen dit een "pairwise-sum triple" (paarwijze som-trio). De paper stelt een eenvoudige vraag: Wat is het maximale aantal mensen dat je kunt uitnodigen voor dit feestje voordat je per ongeluk zo'n verboden trio creëert?

Het Antwoord: De 5/8 Drempel

De paper lost een beroemde puzzel op (Erdős Probleem 865) door een precieze limiet te bewijzen.

Beschouw het totale aantal gasten ( $N$ ) als een gigantische pizza. De paper bewijst dat als je meer dan 5/8ste van de pizza uitnodigt (plus een klein, verwaarloosbaar kruimeltje), je een verboden trio niet kunt vermijden.

De Ondergrens (De "Slechte" Constructie): De auteurs laten zien dat er een specifieke manier is om precies 5/8ste van de gasten uit te nodigen zonder de regel te breken. Ze doen dit door mensen uit twee specifieke stukken van de pizza uit te nodigen:
1. Het stuk van 1/8 tot 1/4 van de weg door de pizza.
2. Het stuk van 1/2 tot het einde.
  Als je alleen mensen uit deze twee zones kiest, landen hun "sommen" nooit terug op de gastenlijst. Dit bewijst dat je tot 5/8 kunt komen.
De Bovengrens (Het "Goede" Bewijs): Het hoofdarbeid van de paper is het bewijzen dat je niet hoger dan 5/8 kunt gaan. Als je probeert zelfs maar één persoon meer uit te nodigen dan die 5/8-grens, garandeert de wiskunde dat er een verboden trio zal verschijnen.

Dus, het antwoord is exact 5/8. Het is een scherpe, precieze lijn in het zand.

Hoe Ze Het Bewezen Hadden: De "Vouw"-truc

Om te bewijzen dat je niet hoger dan 5/8 kunt gaan, gebruiken de auteurs een slim mentaal trucje genaamd "Folding" (Vouwen).

Stel je voor dat je gastenlijst een lange strook papier is.

Kies een Pivot (Draaipunt): Kies een specifieke gast (laten we ze de "Pivot" noemen) om in het midden te staan.
Vouw de Papier: Stel je voor dat je de strook papier vouwt zodat de nummers onder de Pivot-lijn uitlijnen met de nummers boven de Pivot.
- Als de Pivot gast #100 is, vouwt gast #101 op #99, #102 op #98, enzovoort.
De Botsing: Wanneer je de papier vouwt, kunnen sommige nummers bovenop elkaar terechtkomen. De auteurs analyseren wat er gebeurt wanneer deze "gevouwen" nummers met elkaar interageren.

Ze ontdekten dat als je te veel gasten hebt, de "gevouwen" nummers een wiskundige botsing veroorzaken die een verboden trio dwingt te bestaan. Het is als het proberen in te pakken van te veel koffers in een auto; uiteindelijk dwingt de geometrie van de auto twee koffers om tegen elkaar aan te botsen.

De "Lean" Formalisering (De Robot Check)

De paper vermeldt dat een deel van het bewijs is gecontroleerd door een computerprogramma genaamd Lean 4.

Beschouw het bewijs als een complexe brug. De auteurs hebben deze met de hand gebouwd. Daarna hebben ze de blauwdrukken overhandigd aan een super-precieze robot (Lean) om elke enkele bout en balk te controleren. De robot bevestigde dat de brug solide is, zonder verborgen scheuren of "sorry, ik vergat een stap" momenten. Dit geeft de wiskundige gemeenschap extra vertrouwen dat de 5/8 limiet absoluut correct is.

Samenvatting

Het Probleem: Hoeveel nummers kun je kiezen van 1 tot $N$ zonder een specifieke "som-trio" te creëren?
Het Resultaat: Je kunt tot 5/8 van de nummers kiezen. Als je meer kiest, ben je wiskundig gegarandeerd een trio aan het creëren.
De Methode: Ze gebruikten een "vouw"-techniek om aan te tonen dat elke poging om deze limiet te overschrijden een logische tegenstrijdigheid veroorzaakt.
De Betekenis: Dit lost een decennia oud probleem op (Erdős Probleem 865) en bevestigt dat de "5/8" limiet het absoluut beste mogelijke antwoord is.

Technische Samenvatting: Een scherpe 5/8 grens voor een Erdős–Sós paar-sommen probleem

Probleemstelling
Het artikel behandelt een specifiek geval van de Erdős–Sós vermoeden betreffende paar-sommen. Laat $f_3(N)$ de kleinste integer zijn waarvoor elke deelverzameling $A \subseteq \{1, \dots, N\}$ met $|A| \geq f_3(N)$ drie verschillende elementen $a, b, c \in A$ bevat die voldoen aan de voorwaarde dat hun paar-sommen $a+b$ , $a+c$ en $b+c$ allemaal binnen $A$ liggen. Een dergelijke verzameling wordt een "paar-som drie-vrije" verzameling genoemd als er geen zodanig drietal bestaat. Het centrale doel is om het asymptotische gedrag van $f_3(N)$ te bepalen.

Voorafgaand aan dit werk toonde een standaard constructie $A = [\frac{N}{8}, \frac{N}{4}] \cup [\frac{N}{2}, N]$ aan dat $f_3(N) \geq \frac{5}{8}N + O(1)$ . Het doel van het artikel is om de bijbehorende bovengrens te bewijzen, waardoor Erdős Probleem 865 wordt opgelost en de exacte asymptotische constante wordt vastgesteld.

Methodologie
Het bewijs is zelfstandig en rust op een combinatie van combinatorische inductie, additieve getaltheorie en een "vouwingstechniek" (folding technique). De methodologie verloopt via de volgende cruciale stappen:

De Gevouwen Additieve Lemma (Lemma 2.1):
De auteurs stellen eerst een lemma vast over een "gevouwen" interval. Voor een verzameling $B \subseteq \{1, \dots, m-1\}$ waarbij geen enkel paar van verschillende elementen somt tot $m$ of tot een ander element in $B$ (modulo $m$ ), begrenst de lemma de grootte van $B$ ten opzichte van de verzameling "botsingen" $C(B)$ . Specifiek bewijst het dat $|B| - |C(B)| \leq \frac{m}{4} + 2$ . Het bewijs maakt gebruik van reflectiesymmetrie ( $B \to -B$ ) en een inductief argument op $|B|$ , waarbij wordt geanalyseerd in welke gevallen de som van de twee kleinste elementen wel of niet in $C(B)$ ligt.
De Vouwingslemma (Lemma 3.1):
De auteurs introduceren een "vouwingsoperatie" rond een pivot-element $h \in A$ . Door de verzameling $A$ te partitioneren in elementen kleiner dan $h$ ( $X$ ) en elementen van de vorm $h+r$ waar $r < h$ ( $Y$ ), relateren zij de grootte van $A$ aan de structie van de doorsnede $B_h = X \cap Y$ . De lemma toont aan dat als $A$ drie-vrij is, de som van de grootten $|X| + |Y|$ begrensd wordt door $\frac{5}{4}h - |E \setminus C(B_h)| + 1$ , waarbij $E$ de "gaten" in het interval $[1, h-1]$ vertegenwoordigt. Deze stap reduceert het probleem van het begrenzen van de globale verzamelingsgrootte effectief tot het analyseren van lokale additieve eigenschappen modulo $h$ .
Inductieve Bovengrens (Sectie 4):
Het hoofdbewijs wordt geleverd via sterke inductie op $H$ (waarbij $N=2H$ ). Het bewijs splitst zich in twee gevallen gebaseerd op de kloof tussen het grootste element in het onderste deel van het interval en het kleinste element in het bovenste deel:
- Geval 1 ( $s \leq 4e$ ): De verzameling wordt gevouwen rond het pivot-element $h = q$ (het kleinste element in het bovenste deel). De auteurs tonen aan dat de kloof tussen het onderste en bovenste deel van $A$ een voldoende aantal "ontbrekende" elementen ( $|E \setminus C(B_h)|$ ) afdwingt om de grens te voldoen.
- Geval 2 ( $s > 4e$ ): De verzameling wordt gevouwen rond $h = p$ (het grootste element in het onderste deel). Hier impliceert de grote kloof dat het onderste deel van de verzameling ijl is. De auteurs passen de inductiehypothese toe op het onderste segment en combineren dit met de vouwingslemma om de grens af te leiden.

Belangrijkste Bijdragen en Resultaten

Scherpe Bovengrens: Het artikel bewijst dat voor alle $N$ , elke deelverzameling $A \subseteq [1, N]$ met $|A| \geq \frac{5}{8}N + C$ (voor een bepaalde absolute constante $C$ ) een paar-som drietal bevat.
Resolutie van Erdős Probleem 865: Door de nieuwe bovengrens te combineren met de bestaande ondergrens-constructie, stelt het artikel vast dat $f_3(N) = \frac{5}{8}N + O(1)$ . Dit bevestigt dat de constante $5/8$ optimaal is.
Formalisering: De auteurs merken op dat een eerdere conditionele versie van de reductie van een grovere grens naar de scherpe grens is geformaliseerd in Lean 4/Mathlib. Deze formalisering gebruikt geen "sorries" (placeholders) en geen toegevoegde axioma's, wat de logische geldigheid van de reductiestappen verifieert.
Verfijnd Vermoeden: Het artikel vermeldt een scherpere vermoedelijke formule voorgesteld door Stijn Cambie betreffende de exacte maximale grootte voor specifieke $N$ modulo 8, hoewel het primaire resultaat de asymptotische $5/8$ grens blijft.

Betekenis
Het artikel claimt Erdős Probleem 865 op te lossen door een zelfstandig bewijs van de scherpe $5/8$ bovengrens te leveren. De betekenis ligt in het dichten van de kloof tussen de bekende constructie en de theoretische bovengrens voor dit specifieke paar-som probleem. Het werk wordt gepresenteerd als een volledig wiskundig bewijs, met de extra strengheid van een geformaliseerde reductie in Lean, wat de geldigheid van de combinatorische argumenten garandeert zonder afhankelijkheid van ongeverifieerde aannames. De auteurs stellen expliciet dat het bewijs zelfstandig is en dat alle impliciete constanten absoluut zijn.