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

Technical Summary: The Greedy 3-Sumfree Sequence $S_{1,g,g+1}$

Problem Statement
The paper addresses the characterization of the greedy 3-sumfree sequence $S_{x,y,z}$, defined as the increasing sequence of positive integers starting with $x, y, z$ where each subsequent term is the least integer greater than the preceding term that cannot be expressed as the sum of three distinct earlier terms. Specifically, the authors investigate the sequence $S_{1,g,g+1}$ for every integer $g \ge 2$. While Bosma et al. [1] had previously established explicit descriptions for specific small cases ($g=2, 3, 4$) using the automatic theorem prover Walnut and conjectured a uniform formula for all $g \ge 2$, a general proof remained open.

Methodology
The authors employ a direct interval-sumset argument rather than relying on automated theorem proving. The methodology proceeds as follows:

1. Definition of the Candidate Set ($A_g$): The paper defines a specific set $A_g$ based on modular arithmetic. Let $m = 10g + 3$, $e = 2g + 1$, and $f = 6g + 1$. The set $A_g$ consists of the initial terms $\{1, e, f\}$ and a union of periodic intervals $I_k$ and $J_k$ for $k \ge 0$, defined as:

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     The set $A_g$ is constructed to be the union of these disjoint components.

2. Reduction to Two Propositions: The proof that $S_{1,g,g+1} = A_g$ is reduced to verifying two properties regarding the "forced" nature of integers (an integer is forced if it is the sum of three distinct elements of the set):

   • Proposition 2: Every integer $n > g + 1$ that is not in $A_g$ is forced (i.e., can be written as a sum of three distinct elements of $A_g$).
   • Proposition 3: No element within $A_g$ is forced (i.e., no element of $A_g$ can be written as a sum of three distinct elements of $A_g$).

3. Interval Arithmetic: The core of the proof involves calculating the sumsets of the defined intervals. Using elementary identities for the sumsets of intervals (e.g., $b_3[u, v] = [3u+3, 3v-3]$), the authors demonstrate that the gaps in $A_g$ are exactly covered by sums of three distinct elements from $A_g$, while sums of three elements from $A_g$ always fall into the complement of $A_g$ (specifically, a periodic complement pattern set $C$).

4. Inductive Verification: The authors use induction on $n$ to show that the greedy rule admits exactly the elements of $A_g$. If $n \notin A_g$, it is forced by elements smaller than $n$ (which are in the sequence by the inductive hypothesis), so it is excluded. If $n \in A_g$, it is not forced by elements smaller than $n$, so it is admitted.

Key Results
The paper establishes Theorem 1, which provides an exact characterization of the sequence $S_{1,g,g+1}$ for all $g \ge 2$:
An integer $z$ belongs to $S_{1,g,g+1}$ if and only if:
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{or} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

The paper further details the structure of the sequence:

• Initial Terms: The sequence begins with $1, g, g+1, \dots, 2g, 2g+1, 6g+1$.
• Eventual Periodicity: After the first $g+4$ terms, the sequence becomes periodic modulo $m = 10g + 3$.
• Period Structure: The repeating block has a length of $2g + 1$ and consists of the residues:
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

Significance and Claims
The paper claims to provide a direct proof of the conjecture formulated by Bosma, Bruin, Fokkink, Grube, Reuijl, and Tromp [1]. While the conjecture was previously verified mechanically for $2 \le g \le 10$, this work extends the result to all integers $g \ge 2$ through analytical means. The authors explicitly state that their approach yields a "direct proof" using interval-sumset arguments, contrasting with the computational methods used in prior work. The paper also provides a complete explicit description of the eventual periodicity, including both the preperiod and the repeating block, resolving the structure of the sequence entirely.