suite de Stöhr

Imaginez une liste de nombres que l'on construit un par un. On garde 1, puis on cherche le premier entier positif qui ne s'obtient pas en additionnant un petit nombre de nombres déjà gardés. Avec h = 2, les nombres 1, 2, 4 et 7 sont retenus successivement : 3 est écarté car 1 + 2 = 3, tandis que 4 ne peut pas être obtenu avec au plus deux termes distincts de la liste précédente. La suite de Stöhr est cette liste qui avance par le plus petit trou disponible. Quand h augmente, davantage de sommes deviennent possibles et la sélection peut laisser davantage d'entiers de côté.

Une suite de Stöhr est une suite d'entiers positifs construite par récurrence gloutonne. Son premier terme est u₀ = 1. Pour chaque rang suivant, on examine les entiers positifs dans l'ordre croissant et l'on retient le premier qui n'est pas une somme d'au plus h éléments distincts déjà retenus. Ici, h désigne le nombre maximal de termes autorisés dans une représentation additive. La règle interdit donc certaines sommes, mais elle ne demande pas d'éviter les répétitions d'un même terme puisque les éléments utilisés doivent être distincts.

Le paramètre h fixe la sévérité de la construction. Pour h = 2, on exclut les entiers qui sont un terme seul ou la somme de deux termes distincts de la suite construite jusque-là. Cette règle est liée aux questions de représentations additives étudiées en théorie additive des nombres, sans suffire à elle seule pour classer la suite parmi les suites B_h. La définition décrit une procédure de sélection ; elle ne fournit pas ici de formule fermée donnant directement uₙ.

La construction repose sur quatre éléments. Le premier terme u₀ = 1 fournit le point de départ. Le paramètre h fixe le nombre maximal de termes distincts que l'on peut additionner. L'ensemble des termes déjà retenus sert de mémoire pour tester chaque candidat. Enfin, l'ordre croissant des entiers positifs impose le choix du plus petit candidat encore admissible.

Ces éléments dépendent les uns des autres : sans l'ensemble déjà construit, la règle ne permet pas de tester un entier ; sans h, elle ne permet pas de savoir quelles sommes sont interdites. L'ordre croissant transforme le critère d'admissibilité en choix unique à chaque étape. La suite est donc définie par sa règle et ses données initiales, non par son apparence ou par une formule explicite.

Prenons h = 2 et partons de la liste {1}. Les nombres examinés sont des entiers positifs, et une somme utilise au plus deux termes distincts déjà retenus.

Après 1, le candidat 2 n'est ni 1 ni une somme formée de deux termes disponibles : il est retenu. Le candidat 3 est ensuite écarté, car 1 + 2 = 3. Le candidat 4 est retenu.

Avec {1, 2, 4}, les entiers 5 et 6 sont respectivement 1 + 4 et 2 + 4. Le candidat 7 n'est ni un terme déjà présent ni une somme de deux termes distincts ; il est donc retenu.

Avec {1, 2, 4, 7}, 8 = 1 + 7 et 9 = 2 + 7, tandis que 10 ne s'écrit pas comme une somme autorisée. Le début de la suite est donc 1, 2, 4, 7, 10. Un contrôle direct confirme chaque exclusion et chaque choix.

Pour construire les premiers termes, on conserve la liste déjà obtenue et l'on teste les entiers positifs dans l'ordre. Un candidat est retenu dès qu'aucune somme autorisée ne le représente. Une liste des sommes déjà produites aide à rendre le test vérifiable.

Pour une étude additive, on choisit d'abord h selon la restriction recherchée. Avec h = 2, le contrôle porte sur les termes seuls et les paires distinctes ; une valeur plus grande élargit l'ensemble des sommes à exclure.

Pour vérifier un terme proposé, on compare ce nombre à toutes les sommes d'au plus h éléments distincts de la liste précédente. Cette vérification exhaustive est préférable à une simple comparaison avec le terme précédent, qui ne teste pas la règle additive.

Une suite de Stöhr ne se confond pas avec une suite arithmétique. Dans une suite arithmétique, la différence entre deux termes consécutifs est constante ; dans la construction de Stöhr, le terme suivant dépend des sommes formées avec tous les termes déjà retenus. Dans l'exemple h = 2, les écarts sont 1, 2, 3 puis 3 : ils ne suivent donc pas la règle d'une progression arithmétique.

Elle ne se confond pas non plus avec une suite de Sidon au sens le plus strict. La famille B_h généralise une contrainte de représentations additives, tandis que la définition donnée ici précise une construction gloutonne particulière. Le critère qui tranche est donc la règle de sélection, et non le seul fait d'observer des sommes distinctes.

Le cas h = 2 montre déjà pourquoi l'ordre des tests compte : 3 est écarté après l'apparition de 1 et 2, car 1 + 2 = 3. Il serait incorrect de tester 3 avant d'avoir retenu 2, ou de vérifier seulement les sommes de deux termes sans inclure les termes seuls.

La règle porte sur des éléments distincts déjà présents. Ainsi, 2 + 2 n'est pas une représentation autorisée lorsque h = 2, car elle réutilise le même élément ; en revanche, 1 + 2 l'est. Il faut également distinguer le nombre maximal de termes, h, du rang n du terme recherché : ils ne jouent pas le même rôle.

Le qualificatif « gloutonne » ne signifie pas que la suite est la plus dense ou la plus régulière possible. Il signifie que chaque étape choisit localement le plus petit entier admissible. Toute propriété de densité ou toute formule asymptotique demanderait des résultats supplémentaires, absents de la définition fournie.

La suite de Stöhr ouvre sur la théorie additive des nombres : l'objet central n'est plus seulement la suite elle-même, mais la manière dont ses termes produisent ou évitent des représentations par sommes. Le langage des suites B_h permet ensuite de comparer cette contrainte à d'autres problèmes de séparation additive, sans supposer qu'une construction gloutonne possède automatiquement toutes les propriétés d'une suite B_h abstraite.