🔢 mathematics

Monochromatic products in random integer sets

Cet article étudie la probabilité seuil à laquelle un sous-ensemble aléatoire d'entiers contient presque sûrement une solution monochromatique à l'équation $ab=c$ sous une 2-coloration, établissant des bornes entre $n^{-1/9-o(1)}$ et $n^{-1/11}$ et démontrant que le comportement et les techniques de preuve pour de telles équations non linéaires diffèrent substantiellement de celles des équations linéaires.

Auteurs originaux : Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

Publié 2026-01-15

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

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 ayez un sac géant de tuiles numérotées, de 1 à $n$ . Vous décidez d'en choisir une poignée au hasard pour les garder, en lançant une pièce pour chacune : pile, vous la gardez ; face, vous la jetez. La probabilité de garder une tuile est $p$ .

Imaginez maintenant un seau de peinture avec $r$ couleurs différentes. Vous voulez peindre chaque tuile de votre poignée aléatoire. La grande question est la suivante : est-il possible de les peindre de manière à éviter de créer un « produit monochromatique » ?

Un « produit monochromatique » est un trio de tuiles $(a, b, c)$ qui sont toutes de la même couleur, où $a \times b = c$ . Par exemple, si vous avez les tuiles 2, 3 et 6, et qu'elles sont toutes peintes en rouge, vous avez un « produit rouge » car $2 \times 3 = 6$ .

Ce document est une enquête mathématique de type « histoire de détectives » visant à trouver le point de bascule exact (le seuil) où il devient impossible d'éviter ces trios de couleurs identiques, peu importe la ruse utilisée pour les peindre.

Le Contexte : La Somme vs Le Produit

Les mathématiciens savent depuis longtemps que si vous avez assez de nombres, vous ne pouvez pas éviter une « somme monochromatique » (où $a + b = c$ ). C'est un résultat célèbre appelé Théorème de Schur.

Dans les années 1990, des chercheurs ont demandé : « Et si notre sac de nombres est très clairsemé ? Combien de nombres devons-nous choisir avant d'être garantis de trouver une somme ? » Ils ont trouvé la réponse : si vous choisissez des nombres avec une probabilité environ égale à $1/\sqrt{n}$ , vous êtes garanti de trouver une somme. Si vous en choisissez moins, vous pouvez généralement l'éviter.

Ce document pose la même question, mais pour les produits ( $a \times b = c$ ) plutôt que pour les sommes.

La Découverte Principale : Un Nouveau Point de Bascule

Les auteurs ont découvert que les règles pour les produits sont très différentes des règles pour les sommes.

La Règle de la « Somme » : Pour les sommes, le point de bascule est autour de $n^{-1/2}$ (1 sur la racine carrée de $n$ ).
La Règle du « Produit » : Pour les produits, le point de bascule est beaucoup plus bas. Les auteurs ont prouvé que pour qu'un ensemble aléatoire de nombres garantisse la présence d'un produit monochromatique, la probabilité de choisir un nombre doit se situer quelque part entre $n^{-1/9}$ et $n^{-1/11}$ .

L'Analogie :
Considérez le problème de la « Somme » comme une tentative de trouver une forme spécifique dans un tas de sable. Vous avez besoin d'une quantité modérée de sable pour être sûr que la forme est présente.
Le problème du « Produit » est comme la recherche d'une formation cristalline très rare. Parce que la multiplication croît très vite (2 fois 3 fait 6, mais 10 fois 10 fait 100), les « cristaux » (les triplets $a, b, c$ ) sont beaucoup plus difficiles à former. Vous avez besoin d'un tas de nombres beaucoup plus dense (une probabilité $p$ plus élevée) pour garantir que vous trouverez un produit, mais paradoxalement, la mathématique montre que le seuil est en fait plus bas en termes d'exposant car la structure de la multiplication est bien plus clairsemée et irrégulière que celle de l'addition.

Comment ils l'ont résolu : Une attaque sur deux fronts

Pour trouver ce seuil, les auteurs ont dû prouver deux choses :

1. La « Mauvaise Nouvelle » (la borne inférieure) :
Ils ont montré que si vous choisissez des nombres trop parsemés (en dessous de $n^{-1/9}$ ), vous pouvez presque toujours les peindre avec deux couleurs (disons Rouge et Bleu) de sorte qu'aucun trio Rouge et aucun trio Bleu n'existe.

La Méthode : Ils ont utilisé un « Algorithme Glouton ». Imaginez que vous peignez les nombres dans l'ordre, du plus petit au plus grand. Vous essayez de peindre un nombre en Rouge. Si peindre ce nombre en Rouge créerait un produit Rouge avec des nombres que vous avez déjà peints, vous le peignez en Bleu à la place. Si peindre ce nombre en Bleu créerait un produit Bleu, vous êtes bloqué.
Le Résultat : Ils ont prouvé que si l'ensemble est suffisamment clairsemé, ce processus de peinture glouton ne se bloque presque jamais. Vous pouvez réussir à colorer tout l'ensemble sans créer de produit monochromatique.

2. La « Bonne Nouvelle » (la borne supérieure) :
Ils ont montré que si vous choisissez des nombres suffisamment denses (au-dessus de $n^{-1/11}$ ), vous êtes garanti de trouver un produit monochromatique, peu importe la façon dont vous les peignez.

La Méthode : Au lieu d'essayer de colorer tout l'ensemble, ils ont cherché un « piège » minuscule et spécifique. Ils ont trouvé une petite collection de 15 nombres qui, s'ils apparaissent tous dans votre ensemble aléatoire, ne peuvent pas être colorés sans créer un produit monochromatique. C'est comme un puzzle mathématique qui n'a pas de solution.
Le Résultat : Ils ont prouvé que si votre probabilité $p$ est suffisamment élevée, votre ensemble aléatoire contiendra presque certainement ce « motif piège ». Une fois le piège présent, le produit monochromatique est inévitable.

Pourquoi cela importe

Ce document est significatif car il casse les codes. Pendant des décennies, les mathématiciens pensaient que les règles pour les ensembles aléatoires avec des sommes et des produits étaient similaires. Ce document montre qu'elles sont fondamentalement différentes.

Les Sommes sont régulières et prévisibles.
Les Produits sont chaotiques et irréguliers.

Les outils que les mathématiciens utilisent habituellement pour résoudre ces problèmes (qui reposent sur la régularité des sommes) ont échoué pour les produits. Les auteurs ont dû inventer de nouvelles manières plus créatives de compter les possibilités et de construire leurs « pièges ».

La variante des multi-couleurs

Le document examine également ce qui se passe si vous avez 3, 4 ou plus de couleurs.

Pour les sommes, le nombre de couleurs ne change pas beaucoup le point de bascule.
Pour les produits, le nombre de couleurs change radicalement le seuil. Plus vous avez de couleurs, plus il est difficile de forcer un produit monochromatique, et le seuil se déplace de manière significative.

Résumé

En bref, ce document nous dit que si vous choisissez aléatoirement des nombres dans une liste immense, il existe une « zone de Goldilocks » très spécifique pour la probabilité de les choisir.

Si vous en choisissez trop peu, vous pouvez esquiver le « piège du produit » en peignant avec soin.
Si vous en choisissez assez, l'univers force l'apparition d'un produit monochromatique, peu importe vos tentatives pour l'éviter.

Les auteurs ont réduit cette zone à une plage spécifique, montrant que le monde de la multiplication aléatoire est bien plus complexe et intéressant que celui de l'addition aléatoire.

Résumé Technique : Produits Monochromatiques dans les Ensembles d'Entiers Aléatoires

Énoncé du Problème
Cet article étudie le seuil de probabilité $p = p(n)$ auquel le sous-ensemble binomial $[n]_p$ (où chaque élément de $\{1, \dots, n\}$ est inclus indépendamment avec une probabilité $p$ ) possède presque sûrement (a.a.s. — almost always surely) la propriété « produit-Schur ». Un ensemble $A$ est dit $r$ -produit-Schur si tout $r$ -coloration de $A$ produit une solution monochromatique à l'équation $ab = c$ avec $a, b, c \in A$ . Bien que les seuils pour les équations linéaires (telles que le théorème de Schur pour $a+b=c$ ) soient bien compris via le théorème de Rado et les principes de transfert subséquents, le comportement des équations non linéaires comme $ab=c$ dans les ensembles aléatoires reste largement inexploré. Les auteurs visent à déterminer la densité critique $p^*$ où l'ensemble aléatoire passe de l'état où il n'est presque sûrement pas produit-Schur à l'état où il est presque sûrement produit-Schur.

Méthodologie
L'article emploie des stratégies de preuve distinctes pour la borne inférieure (l'énoncé $(0)$ ) et la borne supérieure (l'énoncé $(1)$ ), notant que les outils standards de la théorie de Ramsey aléatoire sont insuffisants pour le cadre non linéaire.

L'Énoncé $(0)$ (Borne Inférieure) :
Pour montrer que $[n]_p$ n'est pas produit-Schur pour un petit $p$ , les auteurs utilisent un algorithme de coloration gloutonne (greedy colouring algorithm). Ils tentent de partitionner l'ensemble aléatoire en deux ensembles sans produit (Rouge et Bleu) en itérant à travers les éléments par ordre croissant. Un élément reçoit une couleur s'il ne forme pas un produit monochromatique avec les éléments précédemment colorés.
- Analyse des Obstructions : L'algorithme échoue uniquement si une « configuration interdite » spécifique d'entiers existe au sein de l'ensemble aléatoire. Ces configurations impliquent des dépendances multiplicatives complexes (par exemple, $c = ab = def$, $a = xyz$, $b = uvw$).
- Argument de Comptage : Les auteurs effectuent une analyse détaillée de ces configurations interdites, en les catégorisant par nombre d'éléments distincts et répétitions. Ils appliquent la borne d'union, en exploitant les bornes de diviseurs ( $D(n) = n^{o(1)}$ ) pour montrer que pour $p \le n^{-1/9 - o(1)}$ , la probabilité qu'une telle configuration apparaisse est de $o(1)$ .
L'Énoncé $(1)$ (Borne Supérieure) :
Pour montrer que $[n]_p$ est produit-Schur pour un $p$ plus grand, les auteurs construisent un motif produit-Schur fini spécifique (un petit ensemble d'entiers qui force une solution monochromatique quelle que soit la 2-coloration).
- Construction du Motif : Ils définissent un ensemble $S_{a,b,c,d}$ contenant 14 éléments générés par les produits de quatre entiers de base. Ils prouvent, via une analyse de cas, que toute 2-coloration de cet ensemble produit une solution monochromatique à $xy=z$.
- Preuve d'Existence : Ils démontrent que si $p = \omega(n^{-1/11})$ , l'ensemble aléatoire $[n]_p$ contient a.a.s. une copie de ce motif. Ceci est réalisé en révélant l'ensemble aléatoire par étapes et en montrant que la probabilité d'échouer à trouver les entiers de base nécessaires ( $a, b, c, d$ ) et leurs produits requis est négligeable.
- Écart par rapport aux Méthodes Standards : Les auteurs notent explicitement que les principes de transfert standards et les méthodes de conteneurs d'hypergraphes (qui reposent sur la « sursaturation » — la propriété selon laquelle les ensembles denses contiennent de nombreuses solutions monochromatiques) échouent ici. Pour les produits, il existe des colorations où seule une fraction négligeable des solutions est monochromatique, rendant les preuves basées sur la sursaturation inefficaces.
Extension à $r$ Couleurs :
Pour $r \ge 3$ , les auteurs généralisent les résultats en utilisant les nombres de Schur ( $S(r)$ ) et les nombres de Schur de double somme ( $S'(r)$ ).
- Borne Inférieure : Ils construisent une coloration basée sur des intervalles mis à l'échelle par $n^{1/S'(r)}$ , évitant les sommes monochromatiques et les sommes décalées, ce qui se traduit par l'évitement des produits monochromatiques.
- Borne Supérieure : Ils utilisent l'ensemble $U_x = \{x, x^2, \dots, x^{S(r)}\}$ , qui n'est pas $r$ -produit-colorable par définition de $S(r)$ . Ils montrent que pour $p = \omega(n^{-1/S(r)^2})$ , un tel ensemble apparaît a.a.s.

Résultats Clés

Théorème 1.2 (Deux Couleurs) : Le seuil pour que $[n]_p$ $[n]_{p}$ soit produit-Schur se situe entre $n^{-1/9 - o(1)}$ $n^{- 1/9 - o (1)}$ et $n^{-1/11}$ $n^{- 1/11}$ . Plus précisément :
- Si $p \le n^{-1/9 - o(1)}$ , $[n]_p$ n'est a.a.s. pas produit-Schur.
- Si $p \ge \omega(n^{-1/11})$ , $[n]_p$ est a.a.s. produit-Schur.
Théorème 1.4 ( $r$ Couleurs) : Pour $r \ge 2$ $r \geq 2$ , le seuil $p^*_r$ $p_{r}^{*}$ satisfait :
- $p^*_r \le n^{-1/S'(r)}$ (Borne inférieure du seuil / Borne supérieure de $p$ pour la non-existence).
- $p^*_r \ge n^{-1/S(r)^2}$ (Borne supérieure du seuil / Borne inférieure de $p$ pour l'existence).
- Crucialement, contrairement aux équations linéaires où le seuil est indépendant de $r$ , le seuil pour les produits dépend du nombre de couleurs.

Signification et Revendications
L'article affirme être le premier à explorer les propriétés de Ramsey des ensembles aléatoires concernant les équations non linéaires, spécifiquement les produits monochromatiques. Ses principales contributions sont :

Établissement des Bornes de Seuil : Fournir les premières bornes non triviales pour le seuil de produit-Schur, montrant qu'il est distinct du cas linéaire ( $n^{-1/2}$ ).
Innovation Méthodologique : Démontrer que les techniques de preuve pour les propriétés de Ramsey non linéaires diffèrent substantiellement de celles pour le cas linéaire. Les auteurs soutiennent que l'absence de sursaturation dans les ensembles de produits invalide les puissants principes de transfert et les méthodes de conteneurs qui ont résolu les problèmes de type Rado linéaires, nécessitant de nouvelles approches comme l'analyse de coloration gloutonne et l'incorporation de motifs spécifiques.
Dépendance aux Couleurs : Souligner que pour les équations non linéaires, le seuil dépend du nombre de couleurs $r$ , contrastant avec l'indépendance vis-à-vis de la couleur observée dans les théorèmes de Rado linéaires.

Conjectures et Directions Futures
Les auteurs conjecturent que le véritable seuil est $n^{-1/11}$ , correspondant à leur borne supérieure. Ils suggèrent que celui-ci est déterminé par l'apparition de la configuration spécifique de taille bornée utilisée dans leur preuve. Ils reconnaissent qu'améliorer la borne inférieure ( $n^{-1/9}$ ) nécessiterait probablement de nouvelles idées au-delà d'une coloration gloutonne raffinée. Enfin, ils proposent que leurs techniques pourraient être appliquées à d'autres équations non linéaires, telles que $a^2 = bc$ ou $ab = cd$.