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

Résumé technique : La séquence gourmande 3-somme libre $S_{1,g,g+1}$

Énoncé du problème
L'article traite de la caractérisation de la séquence gourmande 3-somme libre $S_{x,y,z}$, définie comme la séquence croissante d'entiers positifs commençant par $x, y, z$ où chaque terme suivant est le plus petit entier supérieur au terme précédent qui ne peut pas être exprimé comme la somme de trois termes distincts antérieurs. Plus précisément, les auteurs étudient la séquence $S_{1,g,g+1}$ pour tout entier $g \ge 2$. Bien que Bosma et al. [1] aient précédemment établi des descriptions explicites pour des cas spécifiques de petites valeurs ($g=2, 3, 4$) en utilisant le prouveur de théorèmes automatique Walnut et aient conjecturé une formule uniforme pour tout $g \ge 2$, une preuve générale restait ouverte.

Méthodologie
Les auteurs emploient un argument direct d'ensemble-somme d'intervalles plutôt que de s'appuyer sur la preuve automatique de théorèmes. La méthodologie procède comme suit :

1. Définition de l'ensemble candidat ($A_g$) : Le papier définit un ensemble spécifique $A_g$ basé sur l'arithmétique modulaire. Soit $m = 10g + 3$, $e = 2g + 1$ et $f = 6g + 1$. L'ensemble $A_g$ est constitué des termes initiaux $\{1, e, f\}$ et d'une union d'intervalles périodiques $I_k$ et $J_k$ pour $k \ge 0$, définis comme :

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     L'ensemble $A_g$ est construit pour être l'union de ces composantes disjointes.

2. Réduction à deux propositions : La preuve que $S_{1,g,g+1} = A_g$ est réduite à la vérification de deux propriétés concernant la nature « forcée » des entiers (un entier est dit forcé s'il est la somme de trois éléments distincts de l'ensemble) :

   • Proposition 2 : Tout entier $n > g + 1$ qui n'est pas dans $A_g$ est forcé (c'est-à-dire qu'il peut être écrit comme une somme de trois éléments distincts de $A_g$).
   • Proposition 3 : Aucun élément au sein de $A_g$ n'est forcé (c'est-à-dire qu'aucun élément de $A_g$ ne peut être écrit comme une somme de trois éléments distincts de $A_g$).

3. Arithmétique d'intervalles : Le cœur de la preuve implique le calcul des ensembles-sommes des intervalles. En utilisant des identités élémentaires pour les ensembles-sommes d'intervalles (par exemple, $b_3[u, v] = [3u+3, 3v-3]$), les auteurs démontrent que les lacunes dans $A_g$ sont exactement couvertes par des sommes de trois éléments distincts de $A_g$, tandis que les sommes de trois éléments de $A_g$ tombent toujours dans le complément de $A_g$ (spécifiquement, un motif de complément périodique $C$).

4. Vérification inductive : Les auteurs utilisent l'induction sur $n$ pour montrer que la règle gourmande admet exactement les éléments de $A_g$. Si $n \notin A_g$, il est forcé par des éléments plus petits que $n$ (qui sont dans la séquence par hypothèse inductive), donc il est exclu. Si $n \in A_g$, il n'est pas forcé par des éléments plus petits que $n$, donc il est admis.

Résultats clés
Le papier établit le Théorème 1, qui fournit une caractérisation exacte de la séquence $S_{1,g,g+1}$ pour tout $g \ge 2$ :
Un entier $z$ appartient à $S_{1,g,g+1}$ si et seulement si :
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{ou} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

Le papier détaille également la structure de la séquence :

• Termes initiaux : La séquence commence par $1, g, g+1, \dots, 2g, 2g+1, 6g+1$.
• Périodicité éventuelle : Après les $g+4$ premiers termes, la séquence devient périodique modulo $m = 10g + 3$.
• Structure de la période : Le bloc répétitif a une longueur de $2g + 1$ et consiste en les résidus :
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

Signification et revendications
Le papier affirme fournir une preuve directe de la conjecture formulée par Bosma, Bruin, Fokkink, Grube, Reuijl et Tromp [1]. Bien que la conjecture ait été précédemment vérifiée mécaniquement pour $2 \le g \le 10$, ce travail étend le résultat à tous les entiers $g \ge 2$ par des moyens analytiques. Les auteurs déclarent explicitement que leur approche produit une « preuve directe » utilisant des arguments d'ensemble-somme d'intervalles, contrastant avec les méthodes computationnelles utilisées dans les travaux antérieurs. Le papier fournit également une description complète de la périodicité éventuelle, incluant à la fois la pré-période et le bloc répétitif, résolvant ainsi entièrement la structure de la séquence.