🔢 mathematics

Restricted partition functions and additive complements

Cet article répond de manière positive à une question de Dai et Chen datant de 2016 en construisant des ensembles infinis d'entiers positifs qui produisent une fonction de partition restreinte à croissance polynomiale tout en garantissant que chaque entier positif possède au moins une représentation.

Auteurs originaux : Yuchen Ding

Publié 2026-06-17

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yuchen Ding

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 avez une boîte à outils géante et infinie remplie de blocs de construction spéciaux. Chaque bloc a une taille spécifique, déterminée par un nombre dans une liste appelée Ensemble A. Vous avez également un livre de règles spécial appelé Ensemble M qui vous indique combien de chaque bloc vous êtes autorisé à utiliser.

Le mathématicien de cet article, Yuchen Ding, pose une question très précise : Pouvons-nous concevoir ces deux listes (A et M) de sorte que nous puissions construire chaque nombre entier positif (1, 2, 3, etc.) en utilisant ces blocs, mais sans que le nombre de façons de les construire ne devienne incontrôlable ?

Voici une décomposition des concepts en utilisant des analogies de la vie quotidienne :

1. Les blocs de construction (Partitions restreintes)

Considérez le nombre $n$ (comme 100) comme une tour que vous voulez construire.

L'Ensemble A est votre liste de tailles de blocs disponibles (par exemple, 1, 4, 16, 256...).
L'Ensemble M est votre livre de règles pour les "multiples". Il dit : "Vous pouvez utiliser 0, 1 ou 2 du bloc de taille 4, mais peut-être 0, 5 ou 10 du bloc de taille 16."
L'Objectif : Vous voulez pouvoir construire n'importe quel nombre $n$ en utilisant ces règles.
Le Problème : Si vous avez trop de façons de construire le même nombre, les mathématiques deviennent complexes. L'auteur veut prouver que le nombre de façons de construire n'importe quelle tour ( $p$ ) croît lentement — spécifiquement, selon une "croissance polynomiale".

L'Analogie : Imaginez que vous cuisinez des biscuits.

Si vous avez 100 recettes différentes pour un biscuit aux pépites de chocolat, c'est beaucoup de travail à suivre.
La "croissance polynomiale" signifie qu'à mesure que vous essayez de préparer des fournées de plus en plus grandes, le nombre de nouvelles recettes uniques que vous découvrez n'explose pas instantanément en millions. Cela croît à un rythme gérable et prévisible.

2. Le problème de l'« Écart »

Avant cet article, les mathématiciens savaient comment créer des listes où l'on pouvait construire chaque nombre, mais où l'écart entre les tailles des blocs n'était pas énorme.

La Question : Pouvons-nous créer une liste où les blocs deviennent massivement plus grands très rapidement ? Imaginez une liste où le premier bloc est de taille 1, le suivant est de taille 100, le suivant est de taille 10 000, et le suivant est de taille 1 000 000.
L'écart entre ces nombres est si large que les mathématiques s'effondrent généralement, rendant impossible la construction de chaque nombre ou provoquant une explosion du nombre de recettes.

3. La Solution : Le « Couple Parfait »

Ding prouve que la réponse est OUI. Vous pouvez créer ces écarts massifs et tout en construisant chaque nombre avec un nombre gérable de recettes.

Il y parvient en introduisant une astuce ingénieuse impliquant des Compléments Additifs.

La Métaphore : Imaginez deux équipes, l'Équipe B et l'Équipe S.
- L'Équipe B possède des membres qui sont des puissances de 2 (1, 2, 4, 8, 16...).
- L'Équipe S est un groupe spécial de nombres qui comble les "trous" laissés par l'Équipe B.
- Ensemble, si vous prenez un membre de l'Équipe B et un membre de l'Équipe S et que vous additionnez leurs "valeurs", vous pouvez former chaque nombre sur la droite numérique. Ils sont des "compléments".

Ding utilise un résultat célèbre du mathématicien Ruzsa pour trouver une Équipe S qui est juste assez clairsemée pour être intéressante, mais assez dense pour combler les lacunes.

4. Comment fonctionne la construction

Ding crée ses deux listes magiques, A et M, basées sur ces équipes :

L'Ensemble A (Les Blocs) : Il prend les nombres de l'Équipe B et les transforme en puissances de 2 (par exemple, $2^1, 2^2, 2^4, 2^8...$ ). Cela crée les "écarts massifs" requis par la question.
L'Ensemble M (Les Règles) : Il crée des règles basées sur l'Équipe S. Les règles vous permettent de combiner de petites pièces de l'Équipe S pour former les coefficients (la partie "combien de" l'utilisation).

La Magie : Parce que l'Équipe B et l'Équipe S sont des compléments parfaits, vous pouvez toujours décomposer n'importe quel nombre en une somme qui respecte ces règles spécifiques. Parce que l'Équipe S est soigneusement choisie, le nombre de façons de faire cela ne sitte pas hors de contrôle ; il reste dans une limite "polynomiale" (un taux de croissance gérable).

5. Pourquoi cela importe (selon l'article)

Cet article répond à une question spécifique posée par Dai et Chen en 2016.

La Question : « Existe-t-il deux ensembles infinis où les blocs s'éloignent infiniment les uns des autres, et pourtant nous pouvons construire chaque nombre avec un nombre gérable de combinaisons ? »
La Réponse : Oui. Ding a construit un exemple spécifique où les écarts entre les blocs croissent si vite que le rapport de leurs logarithmes tend vers l'infini, et pourtant le système fonctionne parfaitement.

Une note sur l'ingrédient « IA »

L'auteur, Yuchen Ding, déclare ouvertement avoir utilisé un outil d'IA (ChatGPT) au cours de son processus de recherche.

Ce que l'IA a fait : Elle lui a suggéré de regarder des ensembles impliquant des puissances de 2 et l'a orienté vers un théorème spécifique de Ruzsa concernant les "séquences lacunaires" (séquences avec de grands écarts).
Ce que l'auteur a fait : L'auteur a vérifié les mathématiques, vérifié la logique, réorganisé la preuve et écrit l'article final. Il assume l'entière responsabilité de l'exactitude du travail.

Résumé

Yuchen Ding a résolu un puzzle sur la construction de nombres. Il a démontré que vous pouvez avoir un ensemble de blocs de construction espacés de manière incroyablement grande (comme une échelle dont les échelons s'éloignent de plus en plus) et un ensemble de règles pour les utiliser, de telle sorte que :

Vous puissiez construire chaque nombre entier.
Le nombre de façons de les construire ne devienne pas incontrôlable.

C'est comme prouver que vous pouvez avoir une échelle avec des échelons espacés d'un kilomètre, tout en pouvant la grimper de manière fluide et sans tomber, en utilisant un ensemble spécifique et gérable de techniques d'escalade.

Résumé Technique : Fonctions de Partitions Restreintes et Compléments Additifs

Énoncé du Problème
L'article traite d'une question spécifique de la théorie additive des nombres concernant les fonctions de partitions restreintes. Soit $\mathbb{N}$ l'ensemble des entiers positifs et $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ . Pour des sous-ensembles $A, M \subseteq \mathbb{N}$ , la fonction de partition restreinte $p(n, A, M)$ compte le nombre de représentations d'un entier $n$ sous la forme :
$n = \sum_{a \in A} m_a a$
où $m_a \in M \cup \{0\}$ pour tout $a \in A$ , et où seul un nombre fini de $m_a$ sont non nuls. La fonction $p$ est dite à croissance polynomiale s'il existe des constantes $c > 0$ et $n_0$ telles que $p(n, A, M) \leq n^c$ pour tout $n \geq n_0$ .

Le problème central, posé par Dai et Chen en 2016 (Question 1), demande s'il existe deux ensembles infinis $A = \{a_n\}_{n=1}^\infty$ et $M$ d'entiers positifs tels que :

L'ensemble $A$ est extrêmement creux, satisfaisant $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ .
$p(n, A, M) > 0$ pour tout $n$ suffisamment grand (c'est-à-dire que tout grand entier est représentable).
La fonction de partition $p(n, A, M)$ présente une croissance polynomiale.

Des travaux antérieurs d'Alon (2012) et de Dai et Chen (2016) avaient établi l'existence de tels ensembles avec une croissance polynomiale sous des conditions de sparsité moins strictes ou avec des bornes d'exposants spécifiques (par exemple, $p(n) < n^{2+o(1)}$ ), mais le cas de la sparsité super-logarithmique restait ouvert.

Méthodologie
L'auteur, Yuchen Ding, emploie une construction basée sur les compléments additifs et les développements binaires. La stratégie centrale consiste en :

Définir les Compléments Additifs : Deux ensembles $B, S \subseteq \mathbb{N}_0$ sont appelés compléments additifs complets si $B + S = \mathbb{N}_0$ .
Construire les Ensembles $A$ et $M$ : L'article construit $A$ $A$ et $M$ $M$ à partir d'une paire de compléments additifs $B$ $B$ et $S$ $S$ satisfaisant une condition de comptage spécifique. Plus précisément :
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ (sommes de sous-ensembles finis de puissances de 2 issues de $S$ ).
Application Injective : La preuve établit une application injective des représentations de $n$ comptées par $p(n, A, M)$ vers les sous-ensembles finis de l'espace produit $S \times B$ . En utilisant l'unicité des développements binaires, l'auteur montre que toute représentation de $n$ correspond à un ensemble de paires $(s, b)$ telles que $s+b \leq \log_2 n$ .
Borner la Croissance : Le nombre de ces représentations est borné par le nombre de paires $(s, b) \in S \times B$ telles que $s+b \leq N$ (où $N \approx \log_2 n$ ). Ce décompte est montré être borné par $S(N)B(N)$ . Si $B(x)S(x) \ll x$ , la croissance de la fonction de partition résultante est polynomiale.

Contributions Clés et Résultats
L'article apporte une réponse affirmative à la Question 1 de Dai et Chen à travers les résultats suivants :

Théorème 1 : Soient $B$ et $S$ des compléments additifs complets satisfaisant la condition de comptage $B(x)S(x) \ll x$ . Si $A$ et $M$ sont définis comme ci-dessus, alors $p(n, A, M) > 0$ pour tout $n \in \mathbb{N}$ et $p(n, A, M)$ possède une croissance polynomiale.
Corollaire 1 (Résolution de la Question 1) : En invoquant un résultat de Ruzsa (1972) concernant les compléments additifs de puissances de deux, l'auteur construit des ensembles spécifiques $A$ $A$ et $M$ $M$ qui satisfont les conditions du Théorème 1.
- Soit $B = \{0\} \cup \{2^k : k \geq 0\}$ .
- Soit $S$ un sous-ensemble de $\mathbb{N}$ dérivé du théorème de Ruzsa tel que $S(x) \ll x / \log x$ et $B+S = \mathbb{N}_0$ (après ajout de fin elements).
- L'ensemble $A$ résultant a des éléments $a_n = 2^{2^{n-2}}$ pour $n \geq 2$ .
- Cette construction produit $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ , satisfaisant l'exigence de sparsité extrême.
- Puisque $B(x) \ll \log x$ et $S(x) \ll x / \log x$ , le produit $B(x)S(x) \ll x$ est vérifié, assurant une croissance polynomiale de $p(n, A, M)$ .

Signification
L'article affirme répondre par l'affirmative à une question de 2016 de Dai et Chen. Il démontre qu'il est possible de construire des fonctions de partitions restreintes qui sont surjectives (représentent tous les entiers positifs) et présentent une croissance polynomiale, même lorsque l'ensemble des parties autorisées $A$ est nettement plus creux que les exemples connus précédemment (spécifiquement, satisfaisant une condition de limite où l'écart logarithmique entre les éléments consécutifs croît plus vite que n'importe quelle puissance de $\log n$ ).

Le travail généralise les résultats précédents en liant directement le taux de croissance des fonctions de partitions restreintes aux propriétés de comptage des compléments additifs. L'auteur note que la construction a été initialement explorée avec l'assistance d'une IA générative (ChatGPT), qui a suggéré la forme spécifique des ensembles et le lien avec le théorème de Ruzsa, bien que la vérification mathématique, la réorganisation et la preuve finale soient le travail indépendant de l'auteur.