The greedy 3-sumfree sequence $S_{1,g,g+1}$

Technische Samenvatting: De Greedy 3-Sumfree-sequentie $S_{1,g,g+1}$

Probleemstelling
Het artikel behandelt de karakterisering van de greedy 3-sumfree-sequentie $S_{x,y,z}$, gedefinieerd als de toenemende sequentie van positieve gehele getallen beginnend met $x, y, z$, waarbij elke daaropvolgende term het kleinste gehele getal is dat groter is dan de voorgaande term en dat niet kan worden uitgedrukt als de som van drie verschillende eerdere termen. Specifiek onderzoeken de auteurs de sequentie $S_{1,g,g+1}$ voor elk geheel getal $g \ge 2$. Hoewel Bosma et al. [1] eerder expliciete beschrijvingen hadden vastgesteld voor specifieke kleine gevallen ($g=2, 3, 4$) met behulp van de automatische theorem prover Walnut en een uniforme formule voor alle $g \ge 2$ hadden geconjectureerd, bleef een algemeen bewijs openstaan.

Methodologie
De auteurs maken gebruik van een direct interval-somverzamelingargument in plaats van te vertrouwen op automatische theorem proving. De methodologie verloopt als volgt:

1. Definitie van de Kandidaatverzameling ($A_g$): Het artikel definieert een specifieke verzameling $A_g$ op basis van modulaire rekenkunde. Laat $m = 10g + 3$, $e = 2g + 1$ en $f = 6g + 1$. De verzameling $A_g$ bestaat uit de initiële termen $\{1, e, f\}$ en een vereniging van periodieke intervallen $I_k$ en $J_k$ voor $k \ge 0$, gedefinieerd als:

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     De verzameling $A_g$ is geconstrueerd als de vereniging van deze disjuncte componenten.

2. Reductie naar Twee Proposities: Het bewijs dat $S_{1,g,g+1} = A_g$ wordt gereduceerd tot het verifiëren van twee eigenschappen met betrekking tot de "gedwongen" aard van gehele getallen (een geheel getal is gedwongen als het de som is van drie verschillende elementen):

   • Propositie 2: Elk geheel getal $n > g + 1$ dat niet in $A_g$ zit, is gedwongen (d.w.z. kan geschreven worden als een som van drie verschillende elementen van $A_g$).
   • Propositie 3: Geen enkel element binnen $A_g$ is gedwongen (d.w.z. geen enkel element van $A_g$ kan geschreven worden als een som van drie verschillende elementen van $A_g$).

3. Intervalrekenkunde: De kern van het bewijs betreft het berekenen van de somverzamelingen van de gedefinieerde intervallen. Door gebruik te maken van elementaire identiteiten voor de somverzamelingen van intervallen (bijv. $b_3[u, v] = [3u+3, 3v-3]$), tonen de auteurs aan dat de hiaten in $A_g$ exact worden gedekt door sommen van drie verschillende elementen uit $A_g$, terwijl sommen van drie elementen uit $A_g$ altijd in het complement van $A_g$ vallen (specifiek een periodiek complement patroon $C$).

4. Inductieve Verificatie: De auteurs gebruiken inductie op $n$ om aan te tonen dat de greedy-regel exact de elementen van $A_g$ toelaat. Als $n \notin A_g$, is het gedwongen door elementen kleiner dan $n$ (die in de sequentie zitten door de inductieve hypothese), waardoor het wordt uitgesloten. Als $n \in A_g$, is het niet gedwongen door elementen kleiner dan $n$, waardoor het wordt toegelaten.

Belangrijkste Resultaten
Het artikel vestigt Stelling 1, die een exacte karakterisering biedt voor de sequentie $S_{1,g,g+1}$ voor alle $g \ge 2$:
Een geheel getal $z$ behoort tot $S_{1,g,g+1}$ dan en slechts dan als:
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{of} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

Het artikel geeft verder detail over de structuur van de sequentie:

• Initiële Termen: De sequentie begint met $1, g, g+1, \dots, 2g, 2g+1, 6g+1$.
• Evenementele Periodiciteit: Na de eerste $g+4$ termen wordt de sequentie periodiek modulo $m = 10g + 3$.
• Periodieke Structuur: Het herhalende blok heeft een lengte van $2g + 1$ en bestaat uit de residuen:
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

Betekenis en Claims
Het artikel claimt een direct bewijs te leveren voor de conjectuur geformuleerd door Bosma, Bruin, Fokkink, Grube, Reuijl en Tromp [1]. Hoewel de conjectuur eerder mechanisch was geverifieerd voor $2 \le g \le 10$, breidt dit werk het resultaat uit naar alle gehele getallen $g \ge 2$ via analytische middelen. De auteurs stellen expliciet dat hun aanpak een "direct bewijs" oplevert met behulp van interval-somverzamelingargumenten, wat contrasteert met de computationele methoden die in eerder werk werden gebruikt. Het artikel biedt ook een volledige expliciete beschrijving van de evenementele periodiciteit, inclusief zowel de preperiode als het herhalende blok, waarmee de structuur van de sequentie volledig wordt opgelost.