🔢 mathematics

Adjacent comparison bounds and extremal sets for Ruzsa numbers

Motivé par une conjecture de 2024, cet article établit que la différence entre deux nombres de Ruzsa consécutifs est bornée par 144, fournit des bornes non triviales pour la taille des ensembles extrémaux et calcule les valeurs exactes de ces nombres pour tous les modules jusqu'à 100.

Auteurs originaux : Yuchen Ding, Huixi Li, Junfeng Li, Wei Niu, Xiamiao Zhao

Publié 2026-06-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yuchen Ding, Huixi Li, Junfeng Li, Wei Niu, Xiamiao Zhao

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 organisiez une fête massive dans une pièce circulaire avec $m$ sièges numérotés. Vous invitez un groupe d'invités (un sous-ensemble $A$ ) à se tenir sur des sièges spécifiques. La règle de la fête est simple : chaque siège de la pièce doit être « couvert » par au moins une paire d'invités se tenant côte à côte (ou à l'opposé de la pièce) dont les numéros de sièges s'additionnent pour donner le numéro de ce siège.

Cependant, il y a un piège : vous ne voulez pas qu'un siège soit trop encombré. Si trop de paires d'invités revendiquent le même numéro de siège, cela devient chaotique.

Le Nombre de Ruzsa ( $R_m$ ) est la « limite de foule ». Il demande : Quel est le plus petit nombre $r$ tel que nous puissions organiser nos invités de sorte que chaque siège soit couvert au moins une fois, mais qu'aucun siège ne soit revendiqué par plus de $r$ paires ?

Le papier de Ding, Li, Li, Niu et Zhao est une histoire de détective visant à trouver cette limite de foule parfaite pour différentes tailles de pièces ( $m$ ) et à comprendre comment cette limite change lorsque vous ajoutez un siège supplémentaire à la pièce.

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

1. La règle du « Voisinage » (Comparaison d'adjacence)

Pendant longtemps, les mathématiciens se sont demandé : si vous avez une pièce de $m$ sièges et une pièce de $m+1$ sièges, quelle peut être la différence entre les limites de foule ?

L'ancienne supposition : Certains pensaient que la limite ne dépasserait jamais 1. (Par exemple, si une pièce de 36 sièges nécessite une limite de 6, une pièce de 37 sièges nécessiterait 5, 6 ou 7).
Le test de réalité : Les auteurs ont trouvé une faille dans les anciennes données. Pour une pièce de 36 sièges, la limite est de 6. Mais pour une pièce de 37 sièges, la limite tombe à 4. C'est un saut de 2, brisant la règle du « jamais plus de 1 ».
La nouvelle découverte : Bien que la règle du « saut de 1 » ne soit pas parfaite, les auteurs ont prouvé que le saut ne peut jamais être trop énorme. Ils ont montré que la différence entre la limite de foule de la pièce $m$ $m$ et celle de la pièce $m+1$ $m + 1$ n'est jamais supérieure à 144.
- Analogie : Imaginez que vous grimpiez un escalier dont la hauteur de marche change. Vous ne pouvez pas passer du sol au toit en une seule marche, mais vous ne pouvez pas non plus prendre une marche de 1 000 pieds de haut. Les auteurs ont prouvé que la hauteur de la marche est plafonnée à 144 pieds.

2. La taille de la « Fête Parfaite » (Ensembles extrémaux)

Le papier examine également la taille de la liste d'invités ( $|A|$ ).

L'équilibre : Si vous avez trop peu d'invités, vous ne pouvez pas couvrir tous les sièges. Si vous en avez trop, vous créez trop de chaos (un $R_m$ élevé).
La conclusion : Les auteurs ont calculé exactement combien d'invités sont nécessaires pour des pièces allant jusqu'à une taille de 100. Ils ont trouvé que pour de grandes pièces, le « point idéal » pour la taille de la liste d'invités est approximativement la racine carrée du nombre de sièges.
La limite : Ils ont prouvé que pour toute grande pièce, le nombre d'invités nécessaires pour garder le chaos sous contrôle (spécifiquement sous la limite de 192) ne dépassera jamais environ $\sqrt{191 \times \text{sièges}}$ .

3. Le « Nombre Magique » 6

L'une des découvertes les plus surprenantes est un motif dans les données.

L'observation : Lorsque la pièce devient assez grande (spécifiquement 40 sièges ou plus), la « limite de foule » ( $R_m$ ) semble se stabiliser au nombre 6.
La conjecture : Les auteurs soupçonnent que pour toute pièce de 40 sièges ou plus, vous pouvez toujours organiser les invités de sorte qu'aucun siège ne soit revendiqué plus de 6 fois. Ils ont vérifié cela pour chaque taille de pièce jusqu'à 100.
- Analogie : C'est comme découvrir que peu importe la taille de votre ville, vous n'avez jamais besoin de plus de 6 feux de signalisation à n'importe quelle intersection pour que le trafic circule de manière fluide, à condition que votre ville soit suffisamment grande.

4. Comment ils ont fait (La chasse aux certificats)

Les auteurs n'ont pas seulement deviné ; ils ont lancé une recherche informatique massive.

Le processus : Ils ont agi comme des architectes numériques. Pour chaque taille de pièce, ils ont essayé de construire une liste d'invités qui fonctionne.
Le « certificat » : S'ils trouvaient une liste où chaque siège était couvert et aucun siège n'avait plus de 6 paires, cette liste devenait un « certificat » prouvant que la limite est de 6.
La recherche : Ils ont utilisé des supercalculateurs pour tester des millions de combinaisons. Pour les plus petites pièces, ils ont prouvé qu'il était impossible de le faire avec une limite de 5, confirmant que 6 était bien le minimum.

5. Questions Ouvertes (La fête inachevée)

Le papier se termine en posant de nouvelles questions, telles que :

Le problème de l'écart : Si vous avez une pièce immense, est-il possible d'avoir un énorme vide entre les invités ? (Ils ont prouvé que l'écart ne peut pas dépasser la moitié de la taille de la pièce).
Le problème Pair/Impair : Les invités ont-ils tendance à s'asseoir sur des sièges de numéros pairs ou impairs ? (Ils ont trouvé que pour les grandes pièces, le mélange est presque parfaitement équilibré).
Le problème du « Exactement Deux » : Est-il possible d'organiser les invités de sorte qu'aucun siège ne soit revendiqué par exactement deux paires ? (Ils ont prouvé que si la liste d'invités est suffisamment petite, vous devrez avoir des sièges revendiqués par exactement deux paires).

Résumé

En bref, ce papier est une plongée profonde dans les mathématiques du compactage et de la couverture. Il répond à la question : « Comment couvrir efficacement un cercle avec des sommes de paires ? »

Ils ont corrigé une petite erreur dans les calculs précédents.
Ils ont prouvé que la « limite de foule » ne fluctue pas de manière erratique entre les tailles de pièces.
Ils ont trouvé que pour les grandes pièces, la limite se stabilise à 6.
Ils ont fourni une table massive de solutions exactes pour des pièces allant jusqu'à 100, servant de référence pour les futurs mathématiciens.

Le travail est purement théorique — il s'agit de la structure des nombres et des motifs, et non d'applications physiques comme le trafic ou la biologie, bien que la logique d'une « couverture efficace » soit un concept fondamental dans de nombreux domaines.

Résumé technique : Bornes de comparaison adjacentes et ensembles extrémaux pour les nombres de Ruzsa

Définition du problème
Soit $m$ un entier positif et $\mathbb{Z}_m$ l'anneau des classes de résidus modulo $m$ . Pour un sous-ensemble $A \subset \mathbb{Z}_m$ , soit $\sigma_A(n)$ le nombre de paires ordonnées $(a, a') \in A^2$ telles que $a + a' \equiv n \pmod m$ . Le nombre de Ruzsa $R_m$ est défini comme le plus petit entier $r$ tel qu'il existe un sous-ensemble $A \subset \mathbb{Z}_m$ satisfaisant $1 \le \sigma_A(n) \le r$ pour tout $n \in \mathbb{Z}_m$ . Ce concept est motivé par la conjecture d'Erdős-Turán sur les bases additives. Des travaux antérieurs ont établi que $R_m$ est borné par une constante absolue, avec des bornes supérieures améliorées au fil du temps de $C$ (Ruzsa) à $768$ (Tang et Chen), $5120$ (Tang et Chen) et enfin $288$ (Chen). Plus récemment, Ding et Zhao (2024) ont amélioré la borne supérieure à $R_m \le 192$ et ont conjecturé que $|R_{m+1} - R_m| \le 1$ pour tout $m$ .

Méthodologie
Les auteurs emploient une combinaison de lemmes de comparaison combinatoires, d'inégalités analytiques impliquant des fonctions de représentation et une vérification computationnelle approfondie.

Lemmes de comparaison : L'article introduit un nouveau lemme de comparaison (Lemme 3.2) établissant que $R_m \le 4R_{m+1}$ et $R_{m+1} \le 4R_m$ . Ceci est réalisé en construisant des bases additives dans $\mathbb{Z}_{m+1}$ à partir de celles dans $\mathbb{Z}_m$ (et vice versa) en utilisant des translations d'ensembles et des unions, puis en bornant les comptages de représentation des nouveaux ensembles.
Bornes analytiques : Pour estimer la taille des ensembles extrémaux $A$ (où $1 \le \sigma_A(n) \le R_m$ ), les auteurs utilisent l'inégalité de Lev-Sárközy (Lemme 2.1). En analysant l'écart moyen quadratique de $\sigma_A(n)$ par rapport à une constante $c$ , ils dérivent des inégalités quadratiques reliant la cardinalité $|A|$ à $m$ et $R_m$ .
Vérification computationnelle : Les auteurs effectuent une recherche basée sur des certificats pour déterminer les valeurs exactes de $R_m$ $R_{m}$ pour $m$ $m$ allant jusqu'à 100.
- Pour $m \le 45$ , ils vérifient l'exactitude en prouvant la non-existence d'ensembles avec des bornes de représentation inférieures aux $R_m$ revendiqués.
- Pour $m > 45$ , ils s'appuient sur une preuve de borne inférieure ( $R_m \ge 6$ ) et cherchent des ensembles satisfaisant $\max \sigma_A(n) \le 6$ .
- La recherche utilise une procédure d'optimisation heuristique impliquant la translation d'ensembles, le remplacement d'éléments et des tentatives budgétisées pour minimiser les défauts de représentation.

Contributions clés et résultats

Borne de comparaison adjacente (Théorème 1.1) : Les auteurs prouvent que pour tout entier positif $m$ , $|R_{m+1} - R_m| \le 144$ . Cela améliore la borne triviale de $186$ (dérivée de $192 - 6$) en utilisant le nouveau lemme de comparaison et la borne supérieure connue $R_m \le 192$ .
Valeurs exactes et contre-exemples : L'article fournit une table de valeurs exactes pour $R_m$ $R_{m}$ pour tous les $m$ $m$ de $2 $à$ $\overset{a}{ˋ}$ 100$.
- Le calcul révèle que $R_{37} = 4$ et $R_{39} = 5$ .
- Spécifiquement, $R_{36} = 6$ et $R_{37} = 4$ , ce qui sert de contre-exemple à la conjecture originale de Ding-Zhao ( $|R_{m+1} - R_m| \le 1$ ) pour $m=36$ .
- Les auteurs proposent une conjecture révisée : $|R_{m+1} - R_m| \le 1$ est vrai pour tout $m$ suffisamment grand.
- Ils conjecturent également que $R_m = 6$ pour tout $m \ge 40$ (Conjecture 2.3).
Bornes sur la taille de l'ensemble extrémal (Théorème 1.2) : Pour un $m$ suffisamment grand et un ensemble $A$ atteignant le nombre de Ruzsa, les auteurs dérivent des bornes non triviales pour $|A|^2$ . Soit $s = \lfloor R_m/2 \rfloor$ . La taille satisfait :
$\left( s + \frac{1}{2} - \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s - \epsilon} \right)m \le |A|^2 \le \left( s + \frac{1}{2} + \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s + \epsilon} \right)m$
En conséquence, si $R_m = 6$ , alors $|A| \le \sqrt{191m}$ .
Propriétés structurelles : L'article étudie les propriétés des ensembles $A_m$ $A_{m}$ (sous-ensembles atteignant $R_m$ $R_{m}$ ).
- Parité : La Proposition 5.5 fournit des bornes sur la proportion d'éléments pairs dans $A$ lorsque $m$ est pair. Si $R_m = 6$ , la proportion d'éléments pairs est bornée à environ $0,14$ de $1/2$ .
- Progressions arithmétiques : L'article définit $L_m$ comme la longueur maximale d'une progression arithmétique contenue dans n'importe quel $A \in A_m$ . Il est noté que $L_m \le R_m$ .
- Cardinalité de $A_m$ : La Proposition 5.6 établit des bornes asymptotiques pour le nombre de tels ensembles, $|A_m|$ , montrant que $\frac{1}{2}\log m - C \le \log |A_m| \le \sqrt{191m} \log(\dots)$ .

Signification
L'article affine la compréhension du comportement des nombres de Ruzsa, en traitant spécifiquement de la stabilité de $R_m$ sous les changements de modules adjacents. En infirmant la conjecture stricte $|R_{m+1} - R_m| \le 1$ pour de petits $m$ tout en fournissant des preuves solides de sa validité asymptotique, les auteurs clarifient l'interaction entre la structure algébrique (propriétés du module) et le hasard combinatoire. La fourniture de valeurs exactes jusqu'à $m=100$ étend considérablement les tables précédentes, et les bornes dérivées sur la taille des ensembles extrémaux offrent de nouvelles contraintes pour les recherches futures sur les bases additives dans les groupes cycliques. Le travail pose également plusieurs problèmes ouverts concernant la distribution des valeurs de représentation, la structure des ensembles extrémaux et la croissance du nombre de tels ensembles.