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

Technisches Resümee: Die gierige 3-sumfreie Sequenz $S_{1,g,g+1}$

Problemstellung
Die Arbeit befasst sich mit der Charakterisierung der gierigen 3-sumfreien Sequenz $S_{x,y,z}$, die als die aufsteigende Folge positiver Ganzzahlen definiert ist, die mit $x, y, z$ beginnt und wobei die jeweils nächste Zahl die kleinste Ganzahl größer als das vorangegangene Element ist, die nicht als Summe von drei verschiedenen früheren Termen dargestellt werden kann. Insbesondere untersucht die Arbeit die Sequenz $S_{1,g,g+1}$ für jede ganze Zahl $g \ge 2$. Während Bosma et al. [1] zuvor explizite Beschreibungen für spezifische kleine Fälle ($g=2, 3, 4$) unter Verwendung des automatisierten Theorembeweisers Walnut etabliert und eine einheitliche Formel für alle $g \ge 2$ vermutet hatten, blieb ein allgemeiner Beweis offen.

Methodik
Die Autoren verwenden ein direktes Intervall-Summenmengen-Argument anstatt sich auf automatisiertes Theorembeweisen zu verlassen. Die Methodik verläuft wie folgt:

1. Definition der Kandidatenmenge ($A_g$): Die Arbeit definiert eine spezifische Menge $A_g$ basierend auf modularer Arithmetik. Sei $m = 10g + 3$, $e = 2g + 1$ und $f = 6g + 1$. Die Menge $A_g$ besteht aus den Anfangstermen $\{1, e, f\}$ und einer Vereinigung periodischer Intervalle $I_k$ und $J_k$ für $k \ge 0$, definiert als:

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     Die Menge $A_g$ wird als Vereinigung dieser disjunkten Komponenten konstruiert.

2. Reduktion auf zwei Propositionen: Der Beweis, dass $S_{1,g,g+1} = A_g$ gilt, wird auf die Verifizierung zweier Eigenschaften bezüglich der „erzwungenen“ Natur von Ganzzahlen reduziert (eine Ganzzahl ist erzwungen, wenn sie die Summe von drei verschiedenen Elementen ist):

   • Proposition 2: Jede Ganzzahl $n > g + 1$, die nicht in $A_g$ liegt, ist erzwungen (d. h. sie kann als Summe von drei verschiedenen Elementen von $A_g$ geschrieben werden).
   • Proposition 3: Kein Element innerhalb von $A_g$ ist erzwungen (d. h. kein Element von $A_g$ kann als Summe von drei verschiedenen Elementen von $A_g$ geschrieben werden).

3. Intervallarithmetik: Der Kern des Beweises ist die Berechnung der Summenmengen der definierten Intervalle. Unter Verwendung elementarer Identitäten für die Summenmengen von Intervallen (z. B. $b_3[u, v] = [3u+3, 3v-3]$) zeigen die Autoren, dass die Lücken in $A_g$ exakt durch Summen von drei verschiedenen Elementen aus $A_g$ abgedeckt werden, während Summen von drei Elementen aus $A_g$ immer in das Komplement von $A_g$ fallen (speziell in ein periodisches Komplementmuster $C$).

4. Induktive Verifizierung: Die Autoren nutzen die Induktion über $n$, um zu zeigen, dass die gierige Regel genau die Elemente von $A_g$ zulässt. Wenn $n \notin A_g$, ist es durch Elemente kleiner als $n$ erzwungen (welche durch die Induktionshypothese Teil der Sequenz sind), weshalb es ausgeschlossen wird. Wenn $n \in A_g$, ist es nicht durch Elemente kleiner als $n$ erzwungen, weshalb es aufgenommen wird.

Wichtigste Ergebnisse
Die Arbeit etabliert Theorem 1, welches eine exakte Charakterisierung der Sequenz $S_{1,g,g+1}$ für alle $g \ge 2$ liefert:
Eine Ganzahl $z$ gehört zu $S_{1,g,g+1}$, wenn und nur wenn:
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{oder} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

Die Arbeit beschreibt ferner die Struktur der Sequenz im Detail:

• Anfangsterme: Die Sequenz beginnt mit $1, g, g+1, \dots, 2g, 2g+1, 6g+1$.
• Eventuelle Periodizität: Nach den ersten $g+4$ Termen wird die Sequenz periodisch modulo $m = 10g + 3$.
• Periodenstruktur: Der sich wiederholende Block hat eine Länge von $2g + 1$ und besteht aus den Residuen:
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

Bedeutung und Ansprüche
Die Arbeit beansprucht, einen direkten Beweis für die von Bosma, Bruin, Fokkink, Grube, Reuijl und Tromp [1] formulierte Vermutung zu liefern. Während die Vermutung zuvor mechanisch für $2 \le g \le 10$ verifiziert wurde, erweitert dieses Werk das Ergebnis auf alle ganzen Zahlen $g \ge 2$ durch analytische Mittel. Die Autoren geben explizit an, dass ihr Ansatz einen „direkten Beweis“ mittels Intervall-Summenmengen-Argumenten liefert, was im Gegensatz zu den computergestützten Methoden früherer Arbeiten steht. Die Arbeit bietet zudem eine vollständige explizite Beschreibung der eventuellen Periodizität, einschließlich der Vorperiode und des sich wiederholenden Blocks, wodurch die Struktur der Sequenz vollständig aufgelöst wird.