🔢 mathematics

Bounds for Greedy $B_h$ -sets

Cet article établit de nouvelles bornes inférieures et supérieures non triviales pour le $k$ -ième élément de l'ensemble $B_h$ glouton, fournissant spécifiquement des estimations asymptotiques précises pour $k \ge 5$ et une borne inférieure générale pour tout $k \ge 1$ , tout en proposant une conjecture pour le comportement asymptotique exact du cinquième élément.

Auteurs originaux : Kevin O'Bryant

Publié 2026-07-09

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kevin O'Bryant

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous construisez une tour avec des blocs numérotés, mais que vous avez une règle très stricte : deux groupes différents de blocs ne peuvent pas avoir la même somme. Si vous choisissez $h$ blocs et les additionnez, cette somme doit être unique à ce groupe spécifique de blocs. Les mathématiciens appellent ces collections spéciales des ensembles $B_h$ .

Imaginez que vous voulez construire la tour la plus petite possible qui respecte cette règle. Vous commencez par le bloc 0, puis vous cherchez le nombre suivant le plus petit que vous pouvez ajouter sans briser la règle. Ensuite, vous cherchez le suivant, le plus petit après celui-là, et ainsi de suite. C'est appelé l'Algorithme Glouton (Greedy Algorithm). C'est comme jouer à un jeu où vous choisissez toujours l'article le moins cher et le plus petit disponible qui ne dépasse pas votre budget.

Le papier de Kevin O'Bryant porte sur la manière dont ces prochains blocs grandissent à mesure que la tour devient plus haute. Plus précisément, l'auteur cherche à prédire la taille des 5e, 6e, 7e et même des blocs supérieurs, selon la rigueur de la règle de "non-duplication des sommes" (représentée par le nombre $h$ ).

La Grande Découverte : Le 5e Bloc

La principale réussite de l'auteur est d'avoir enfin posé des clôtures solides autour de la taille du 5e bloc (noté $\gamma_5$ ).

Avant ce papier, nous savions que le 5e bloc se trouvait quelque part entre 0 et un très grand nombre, mais nous n'avions pas de prise précise sur lui. Ce papier prouve deux choses :

La Borne Inférieure (Le Plancher) : Le 5e bloc est certainement au moins aussi grand que $\frac{1}{8}h^4 + \frac{1}{2}h^3$ . Considérez cela comme un plancher de béton sous lequel vous ne pouvez pas creuser. Peu importe vos tentatives, le 5e bloc ne sera pas plus petit que cela.
La Borne Supérieure (Le Plafond) : Le 5e bloc est certainement plus petit qu'environ $0,467214 \times h^4$ (plus quelques termes plus petits). C'est un plafond que le bloc ne peut pas atteindre.

Ainsi, nous savons maintenant que le 5e bloc vit dans un "appartement" spécifique entre ces deux nombres.

La Vue d'Ensemble : Blocs 6 et Supérieurs

Pour le 6e bloc et tous ceux qui suivent ( $k \ge 6$ ), l'auteur ne donne pas encore une formule parfaite unique. Au lieu de cela, il fournit une recette pour calculer un "plafond" pour la taille de ces blocs.

Le papier introduit une séquence de nombres appelée $\alpha_k$ (comme $\alpha_6 = 0,382978$ , $\alpha_7 = 0,269877$ , etc.). Ces nombres agissent comme une limite décroissante. L'auteur prouve que pour n'importe quel numéro de bloc $k$ (où $k \ge 5$ ), la taille de ce bloc ne dépassera jamais :
$\alpha_k \times h^{k-1}$
plus un peu de "bruit" supplémentaire qui devient négligeable quand $h$ devient immense.

Le papier donne une formule spécifique pour calculer le $\alpha$ suivant si vous connaissez le courant, mais cette étape récursive commence spécifiquement à fonctionner pour le 7e bloc et au-delà (calculer $\alpha_{k+1}$ à partir de $\alpha_k$ nécessite $k \ge 7$ ). Pour le 6e bloc, le papier fournit une valeur constante spécifique dérivée des étapes précédentes. C'est comme une chaîne de montage mathématique : vous introduisez la limite du 6e bloc, et la machine recrache la limite du 7e, et ainsi de suite.

Ce que le Papier Ne Dit Pas (et ce qu'il écarte)

Il est très important de savoir ce que ce papier ne fait pas, car l'auteur est très prudent à ce sujet :

Il ne résout pas tout le puzzle. L'auteur déclare explicitement que, bien qu'il ait trouvé les limites du 5e bloc, il n'a pas encore trouvé la formule exacte du 5e bloc.
Il ne prétend pas que le 5e bloc est exactement $\frac{1}{3}h^4$ . L'auteur conjecture (devine basé sur des modèles) que le 5e bloc pourrait être exactement $\frac{1}{3}h^4$ pour de grandes valeurs de $h$ , mais il admet qu'il ne s'agit que d'une supposition. Il ne l'a pas prouvé.
Il ne dit pas que les blocs sont des polynômes simples. L'auteur est sceptique quant au fait que tous les blocs suivent un modèle polynomial simple et fluide pour toujours. Bien que les premiers blocs (de 0 à 4) soient connus pour être des "quasi-polynômes" (des polynômes qui changent légèrement selon le reste de la division de $h$ par un nombre), l'auteur doute que ce modèle se maintienne pour chaque bloc indéfiniment.

La "Zone Interdite"

Le papier explique également une "zone interdite" pour le bloc suivant. Si vous avez une tour de blocs, il n'y a qu'un nombre fini d'entiers que vous pouvez essayer d'ajouter sans briser les règles. Le papier calcule exactement combien de "mauvais" nombres existent que vous ne pouvez pas choisir. Il s'avère que pour n'importe quelle tour existante, il n'y a que tant de nombres "pièges" qui ruineraient la propriété $B_h$ , et ils se trouvent tous dans une plage spécifique.

Le Mystère du 6e Bloc

L'auteur inclut un tableau de nombres pour le 6e bloc ( $\gamma_6$ ) pour différentes valeurs de $h$ , calculés par ordinateur. Cependant, en regardant ces nombres, l'auteur admet : "Aucune formule n'a encore été devinée."
C'est un peu comme regarder une séquence de nombres et dire : "Nous savons ce qu'ils sont, mais nous n'avons aucune idée de la règle qui les génère." L'auteur liste même les 33 premières valeurs de $\gamma_6$ et note qu'aucune formule n'a encore été trouvée pour elles.

Les Questions Ouvertes

Le papier se termine en énumérant les mystères qui restent à résoudre :

Peut-on prouver que le 5e bloc est exactement $\frac{1}{3}h^4$ ?
Peut-on trouver des formules pour les 6e, 7e et les blocs supérieurs ?
Ces blocs sont-ils distribués uniformément d'un point de vue mathématique, ou se regroupent-ils de manière étrange ? (L'auteur note que pour le 2e bloc, ils semblent se regrouper d'une manière qui n'est pas aléatoire).
Existe-t-il un nombre spécifique (comme 33) qui ne peut jamais être la différence entre deux blocs de la tour ? (L'auteur note que pour le 2e bloc, tous les nombres de 1 à 87 apparaissent comme une différence, sauf 33, ce qui est une coïncidence étrange).

En bref, ce papier construit une clôture solide autour du 5e bloc et fournit une échelle décroissante pour tous les blocs au-dessus, mais la forme exacte de la tour et les formules secrètes des blocs supérieurs restent un mystère attendant le prochain explorateur.

Résumé technique : Bornes pour les ensembles $B_h$ gloutons

Énoncé du problème
L'article étudie le comportement asymptotique de l'algorithme glouton appliqué à la construction d'ensembles $B_h$ . Un ensemble $A$ d'entiers non négatifs est défini comme un ensemble $B_h$ si toute solution à l'équation $a_1 + \dots + a_h = b_1 + \dots + b_h$ (où $a_i, b_i \in A$ ) implique que les multiensembles $\{a_1, \dots, a_h\}$ et $\{b_1, \dots, b_h\}$ sont identiques. L'objet principal d'étude est l'ensemble $B_h$ glouton, noté $G(h) = \{\gamma_0, \gamma_1, \gamma_2, \dots\}$ , qui est construit de manière lexicographique en posant $\gamma_0 = 0, \gamma_1 = 1$ , et en définissant $\gamma_{k+1}$ comme le plus petit entier tel que $\{\gamma_0, \dots, \gamma_{k+1}\}$ demeure un ensemble $B_h$ .

Le problème central abordé consiste à déterminer le taux de croissance du $k$ -ième élément, $\gamma_k(h)$ , en fonction de $h$ pour un $k$ fixé. Alors que des formules exactes sont connues pour $k \le 4$ , le comportement pour $k \ge 5$ est resté largement inexploré au-delà de l'énumération computationnelle. L'article cherche à établir des bornes supérieures et inférieures non triviales pour $\gamma_k(h)$ , ciblant spécifiquement le cinquième élément $\gamma_5(h)$ ainsi que des bornes générales pour $k \ge 5$ .

Méthodologie
L'auteur emploie une combinaison d'analyse combinatoire, de bornage récursif et d'énumération détaillée de cas :

Bornes combinatoires : L'article utilise l'observation que le nombre de sommes $h$ -pli distinctes d'un ensemble de taille $k+1$ est $\binom{k+h}{k}$ . Puisque ces sommes doivent se situer dans l'intervalle $[h\gamma_0, h\gamma_k]$ , cela produit une borne inférieure de base sur $\gamma_k(h)$ .
La caractérisation par le "Mex" : Un lemme clé établit que $\gamma_{k+1} = \text{mex}(F^{(k)})$ , où $F^{(k)}$ est l'ensemble de tous les entiers représentables sous la forme $\frac{1}{r}\sum_{i=1}^k \gamma_i(m_i - m'_i)$ sous des contraintes spécifiques sur les multiplicités $m_i, m'_i$ . Cette caractérisation permet à l'auteur de borner $\gamma_{k+1}$ en comptant le nombre de valeurs « interdites » dans $F^{(k)}$ qui dépassent un certain seuil.
Construction de la borne inférieure ( $\gamma_5$ ) : Pour prouver la borne inférieure de $\gamma_5(h)$ , l'auteur définit un ensemble spécifique de vecteurs d'entiers $\Delta$ représentant les combinaisons de coefficients valides pour les quatre premiers éléments. En ordonnant ces vecteurs de manière lexicographique (selon un ordre spécifique de type « odomètre ») et en analysant l'image de ces vecteurs sous le produit scalaire avec $\langle \gamma_1, \gamma_2, \gamma_3, \gamma_4 \rangle$ , l'auteur démontre que leurs images forment un intervalle contigu. Cela garantit que le « mex » (le premier entier manquant) doit être au moins la valeur maximale d'un sous-ensemble spécifique de ces images.
Construction de la borne supérieure ( $\gamma_k$ ) : Pour la borne supérieure, l'auteur utilise une approche inductive. En supposant une borne $\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$ , l'auteur estime la taille de l'ensemble $F^{(k)}$ au-dessus d'un seuil $\beta_k h^k$ . En stratifiant l'ensemble $F^{(k)}$ selon les multiplicités du plus grand élément $\gamma_k$ , et en appliquant le dénombrement combinatoire « étoiles et barres », l'auteur dérive une relation de récurrence pour les coefficients $\alpha_k$ . La séquence $\alpha_k$ est construite pour être non croissante et converger vers zéro.

Contributions clés et résultats

Borne inférieure pour $\gamma_5(h)$ : L'article établit une borne inférieure non triviale pour le cinquième élément de l'ensemble $B_h$ glouton :
$\gamma_5(h) \ge \frac{1}{8}h^4 + \frac{1}{2}h^3$
Ce résultat est dérivé d'une analyse rigoureuse des sommes interdites générées par les quatre premiers éléments.
Bornes supérieures pour $\gamma_k(h)$ ( $k \ge 5$ ) : L'article fournit les premières bornes supérieures non triviales pour $\gamma_k(h)$ pour $k \ge 5$ . Plus précisément, il prouve :
$\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$
où les constantes $\alpha_k$ sont définies de manière récursive. L'article calcule explicitement :
- $\alpha_5 \approx 0,467214$
- $\alpha_6 \approx 0,382978$
- $\alpha_7 \approx 0,269877$
- Pour $k \ge 7$ , $\alpha_{k+1} = \frac{1}{2} \alpha_k + \frac{1}{2^k k!} \sum_{j=0}^{k-1} \binom{k-1}{j} \binom{k}{j} 2^j$ .
  La séquence $\alpha_k$ est montrée comme décroissant rapidement, impliquant que $\gamma_k(h)$ croît plus lentement que ce que les estimations non prouvées pourraient suggérer.
Conjecture sur $\gamma_5(h)$ : Sur la base de données computationnelles pour $h \le 47$ , l'auteur conjecture une formule asymptotique précise :
$\gamma_5(h) = \frac{1}{3}h^4 + O(h^3)$
Ceci suggère que la borne inférieure de $1/8$ n'est pas serrée, et que le véritable coefficient dominant est probablement $1/3$ .
Borne inférieure générale : L'article réitère et contextualise la borne inférieure générale $\gamma_k(h) \ge \frac{1}{k!}h^{k-1} + O(h^{k-2})$ , confirmant que l'algorithme glouton produit des ensembles avec le bon ordre de croissance pour un $k$ fixé.

Signification et revendications
L'auteur cadre la signification de ce travail dans trois domaines principaux :

Nécessité esthétique et théorique : Les ensembles $B_h$ sont des objets fondamentaux en théorie combinatoire des nombres. L'auteur soutient que comprendre la sortie de l'algorithme glouton pour ces ensembles est un problème naturel qui mérite des réponses, indépendamment de toute application immédiate.
Faisabilité de l'analyse gloutonne : L'article contraste la difficulté d'analyser l'algorithme glouton par rapport aux constructions non gloutonnes (comme la construction de Singer utilisant les corps finis). Tandis que construire un ensemble $B_{100}$ de 11 éléments via les corps finis nécessite de travailler dans $\mathbb{F}_{101}^{11}$ (ce qui est computationnellement implausible), trouver une formule pour le 10ème élément de l'ensemble $B_{100}$ glouton est décrit comme « difficile mais plausible ». Ce travail représente la première étape pour rendre une telle analyse rigoureuse pour $k \ge 5$ .
Compréhension de l'algorithme glouton : La motivation principale est de mieux comprendre l'algorithme glouton pour les ensembles $B_2$ (ensembles de Sidon), qui ont des applications concrètes dans le monde réel (ex: règles de Golomb, allocation de fréquences). Puisque l'algorithme glouton est une heuristique standard pour les problèmes additifs, établir des bornes pour les ensembles $B_h$ contribue à une compréhension plus large des stratégies gloutonnes en théorie additive des nombres.

L'article conclut en énumérant des problèmes ouverts, incluant la preuve de formules quasi-polynomiales pour $\gamma_k$ , la distribution uniforme des éléments dans les classes de congruence, et l'infimum de $s$ pour lequel la somme des puissances réciproques des ensembles $B_h$ gloutons converge. L'auteur reste modeste, notant que bien que les bornes soient non triviales, elles peuvent ne pas être serrées, et que les coefficients exacts pour $k \ge 5$ restent conjecturaux.