🔢 mathematics

The least quadratic residue and integers represented by quadratic forms

Cet article établit des bornes presque optimales pour le plus petit résidu quadratique réduit non trivial modulo $n$ , construit des moduli où cette valeur est inattendument grande, et applique ces résultats pour déterminer le taux auquel les formes quadratiques binaires avec un discriminant borné représentent tous les entiers positifs jusqu'à $N$ .

Auteurs originaux : Kannan Soundararajan, João C. C. Vargas

Publié 2026-08-03

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kannan Soundararajan, João C. C. Vargas

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

La Grande Chasse aux Nombres : Trouver le Premier Carré « Bon »

Imaginez que vous êtes un détective essayant de percer un code secret. Dans le monde des mathématiques, et plus précisément dans une branche appelée la théorie des nombres, les nombres ne servent pas seulement à compter ; ils ont des personnalités et des relations cachées. L'un des casse-têtes les plus célèbres implique les « résidus quadratiques ». Considérez ces derniers comme des nombres qui peuvent être « mis au carré » pour s'insérer parfaitement dans un motif spécifique. Si vous prenez un nombre, que vous l'élevez au carré (en le multipliant par lui-même) et que vous le divisez par un modulo secret (un grand nombre $n$ ), le reste est un résidu quadratique. C'est comme trouver une clé qui s'insère parfaitement dans une serrure spécifique.

La grande question que les mathématiciens se posent depuis longtemps est la suivante : jusqu'où faut-il chercher avant de trouver la première clé qui fonctionne ? En d'autres termes, quel est le plus petit nombre que l'on doit vérifier pour trouver un carré qui fonctionne ? Ce n'est pas seulement un jeu ; comprendre ces « plus petits » nombres nous aide à comprendre comment les nombres sont distribués, ce qui est crucial pour la cryptographie (les mathématiques derrière la sécurité Internet) et pour comprendre la structure profonde de l'univers des nombres. Pendant des décennies, les mathématiciens avaient de bonnes intuitions, mais ils voulaient savoir s'il existait des serrures « sournoises » qui nécessiteraient de chercher dans une zone inattendument vaste avant de trouver une seule clé fonctionnelle.

La Grande Découverte du Papier : Les Verrous « Malchanceux »

Dans cet article, K. Soundararajan et João C. C. Vargas s'attaquent au mystère du plus petit résidu quadratique. Ils définissent un nombre spécial, appelons-le $\ell(n)$ , qui est le plus petit entier « sans facteur carré » (un nombre qui n'est divisible par aucun carré parfait comme 4, 9 ou 16) qui agit comme un résidu quadratique pour un nombre $n$ donné.

Les auteurs prouvent deux choses principales qui pourraient sembler contradictoires au premier abord, mais qui, ensemble, racontent une histoire fascinante.

1. Le Filet de Sécurité (La Borne Supérieure)
D'abord, ils prouvent que vous n'avez jamais à chercher trop loin. Peu importe la complexité de votre nombre $n$ , il existe un « plafond » mathématique sur la taille maximale que peut atteindre la première clé fonctionnelle ( $\ell(n)$ ). Ils montrent que si $n$ possède $k$ facteurs premiers différents, la plus petite clé fonctionnelle est garantie d'être plus petite qu'une formule spécifique impliquant $2^{4k}$ . C'est comme dire : « Même dans le labyrinthe le plus complexe, vous trouverez la sortie avant d'avoir fait $2^{4k}$ pas. » Cette partie est une application directe du principe des tiroirs — un tour de logique qui stipule que si vous avez plus de pigeons que de trous, au moins un trou doit contenir deux pigeons. Ici, les « pigeons » sont les nombres et les « trous » sont les motifs de restes.

2. La Surprise (La Borne Inférieure)
C'est ici que cela devient passionnant. Alors que les auteurs ont prouvé qu'il existe un plafond, ils ont également découvert que pour certains nombres spécialement conçus, la première clé fonctionnelle est beaucoup, beaucoup plus grande que ce que l'on aurait espéré.
Habituellement, si un motif apparaît environ 1 fois sur $2^k$ nombres, on s'attend à trouver une correspondance après avoir vérifié environ $2^k$ nombres. Mais les auteurs ont construit des nombres $n$ spécifiques où la première correspondance n'apparaît qu'après avoir vérifié des nombres aussi grands que $4^k$ (moins une petite correction).
Pour mettre cela en perspective : si vous cherchiez une aiguille dans une botte de foin, vous vous attendriez à la trouver après avoir fouillé quelques bottes. Ces auteurs ont construit une botte de foin si complexe que vous pourriez devoir fouiller une montagne de foin avant de trouver l'aiguille. Ils ont réussi cela en utilisant des idées issues des codes correcteurs d'erreurs (les mathématiques utilisées pour corriger les données corrompues dans les missions spatiales ou les CD), montrant que la « malchance » de ces nombres est en réalité une caractéristique délibérée et construite.

3. Le Scénario « Et Si » (L'Hypothèse de Riemann)
L'article explore également ce qui se passerait si une célèbre conjecture non prouvée, l'Hypothèse de Riemann Généralisée (HRG), était vraie. Si l'HRG est correcte, les nombres « sournois » ne sont pas tout à fait aussi terribles que les exemples construits par les auteurs. Sous cette hypothèse, la plus petite clé serait trouvée bien plus tôt, environ autour de $e^{C \log n \log \log n}$ . Cependant, comme nous ne savons pas avec certitude si l'HRG est vraie, les exemples de « pire cas » construits par les auteurs restent la meilleure preuve que nous ayons que ces nombres peuvent être étonnamment grands.

Pourquoi est-ce important ?

Les auteurs ne se sont pas contentés de trouver ces nombres complexes ; ils ont utilisé leurs découvertes pour résoudre un puzzle lié aux formes quadratiques binaires. Ce sont des expressions mathématiques de type $ax^2 + bxy + cy^2$ qui peuvent être utilisées pour générer d'autres nombres.
L'article pose la question : « Quelle doit être la taille du discriminant (un nombre spécifique définissant la forme) pour garantir que chaque entier positif jusqu'à une certaine taille $N$ puisse être représenté ? »
En utilisant leurs nouvelles bornes sur $\ell(n)$ , les auteurs montrent :

Inconditionnellement (sans supposer l'HRG) : Il existe des entiers jusqu'à $N$ qui ne peuvent pas être représentés par aucune forme quadratique ayant un discriminant inférieur à une certaine limite massive.
Conditionnellement (en supposant l'HRG) : Si l'Hypothèse de Riemann est vraie, la limite est beaucoup plus petite, ce qui signifie que nous pouvons représenter presque tous les nombres avec des formes beaucoup plus simples.

À Retenir

Cet article est une leçon magistrale sur l'équilibre entre les scénarios du « meilleur cas » et du « pire cas ». Il confirme que, bien qu'il existe une limite théorique à la difficulté de trouver un résidu quadratique, l'univers des nombres contient des « pièges » où la recherche est nettement plus longue que ce que suggère la simple probabilité. Les auteurs n'ont pas seulement deviné ; ils ont mathématiquement construit ces pièges et ont prouvé leur existence. Ils ont également montré que si la conjecture mathématique majeure (HRG) est vraie, ces pièges sont moins dangereux qu'ils n'en ont l'air, mais tant que cette conjecture n'est pas prouvée, nous devons supposer le pire.

En fin de compte, ce travail affine notre compréhension de la manière dont les nombres se cachent et se révèlent, prouvant que parfois, la plus petite clé d'une serrure est cachée dans un endroit où l'on ne penserait jamais à regarder sans une carte très ingénieuse.

Résumé Technique : Le plus petit résidu quadratique et les entiers représentés par des formes quadratiques

Énoncé du Problème
Cet article étudie $\ell(n)$ , défini comme le plus petit résidu quadratique réduit non trivial modulo $n$ . Plus précisément, $\ell(n)$ est le plus petit entier sans facteur carré $r > 1$ tel que $\gcd(r, n) = 1$ et $r \equiv x^2 \pmod n$ pour un certain entier $x$ . Les auteurs chercheent à établir des bornes pour $\ell(n)$ en fonction de la magnitude de $n$ et de son nombre de facteurs premiers, $\omega(n)$ . Un objectif secondaire est d'appliquer ces résultats pour déterminer le taux auquel des familles de formes quadratiques binaires avec un discriminant borné représentent tous les entiers positifs jusqu'à une grande borne $N$ .

Méthodologie
Les auteurs emploient une combinaison d'arguments combinatoires, de théorie analytique des nombres et de structures algébriques sur les corps finis.

Principes Combinatoires et du Pigeonnière : La borne supérieure pour $\ell(n)$ est dérivée du principe du pigeonnière. En considérant les nombres premiers dans des progressions arithmétiques et leurs valeurs de symbole de Legendre, les auteurs démontrent l'existence d'un produit de deux nombres premiers qui satisfait les conditions nécessaires de résidu quadratique.
Construction Algébrique (Bornes Inférieures) : Pour construire des modules $n$ possédant un $\ell(n)$ étonnamment grand, les auteurs utilisent une correspondance entre les nombres premiers et les polynômes irréductibles sur le corps $\mathbb{F}_2$ . Ils définissent des fonctions complètement multiplicatives $f_j: \mathbb{N} \to \{-1, 1\}$ basées sur les racines de ces polynômes dans l'adhérence algébrique de $\mathbb{F}_2$ . Un lemme clé impliquant les sommes de puissances d'éléments distincts dans $\mathbb{F}_2$ (lié aux identités de Newton) est utilisé pour prouver que si un entier sans facteur carré $r$ satisfait $f_j(r) = 1$ pour tout $j$ , alors $r$ doit être grand.
Théorie Analytique des Nombres et Estimations de Densité de Zéros : La construction de $n$ $n$ repose sur la recherche d'un ensemble de nombres premiers tels que pour tout discriminant fondamental $D$ $D$ dans un intervalle donné, au moins un nombre premier de l'ensemble est un non-résidu quadratique modulo $D$ $D$ .
- Sous l'hypothèse de la GRH : L'Hypothèse de Riemann Généralisée (GRH) est utilisée pour borner les sommes de caractères sur les nombres premiers, garantissant l'existence d'un tel ensemble de nombres premiers dont la taille est approximativement $\exp(C \log \Delta \log \log \Delta)$ .
- Inconditionnellement : Sans supposer la GRH, les auteurs utilisent des estimations de densité de zéros pour les fonctions $L$ de Dirichlet. Ils partitionnent l'ensemble des discriminants selon l'emplacement de leurs zéros (régions sans zéro) et appliquent un argument de somme pondérée impliquant une fonction de poids spécifique $w(t)$ pour établir l'existence des nombres premiers requis.
Application aux Formes Quadratiques : Les résultats sont appliqués à la représentation d'entiers par des formes quadratiques binaires $f(x,y) = ax^2 + bxy + cy^2$ . Les auteurs utilisent le fait qu'un entier $n$ est représenté par une forme de discriminant $D$ si et seulement si $D$ est un carré modulo $4n$ (pour les représentations propres).

Contributions Clés et Résultats

Bornes pour $\ell(n)$ en fonction des facteurs premiers :
- Borne Supérieure : Si $k$ est le nombre de facteurs premiers impairs de $n$ , $\ell(n) \le C k 2^{4k}$ pour une constante absolue $C$ .
- Borne Inférieure : Pour chaque $k \ge 2$ , il existe une infinité d'entiers impairs $n$ ayant exactement $k$ facteurs premiers distincts tels que $\ell(n) \ge 4^{k - C k / \log k}$ . Ce résultat est surprenant étant donné que la densité des résidus quadratiques est $\asymp 2^{-k}$ , suggérant que l'on pourrait s'attendre à ce que $\ell(n)$ soit plus proche de $2^k$ .
Bornes pour $\ell(n)$ en fonction de la magnitude de $n$ :
- Les auteurs construisent un entier sans facteur carré impair $n \le N(\Delta)$ tel que pour tout discriminant fondamental $D$ avec $1 < |D| \le \Delta$ , il existe un facteur premier $p$ de $n$ avec $\left(\frac{D}{p}\right) = -1$ .
- Inconditionnellement : $N(\Delta)$ peut être choisi comme $\exp(C \log \Delta (\log \log \Delta)^2)$ .
- Sous la GRH : $N(\Delta)$ peut être choisi comme $\exp(C \log \Delta \log \log \Delta)$ pour tout $C > 2/\log 2$ .
- Par conséquent, $\ell(n)$ peut être aussi grand que $\exp\left(c \frac{\log n}{(\log \log n)^2}\right)$ inconditionnellement, et $\exp\left(\left(\frac{\log 2}{2} + o(1)\right) \frac{\log n}{\log \log n}\right)$ sous la GRH.
Représentations par des Formes Quadratiques Binaires :
- Formes Indéfinies : Tout entier positif jusqu'à $N$ peut être représenté par une certaine forme quadratique binaire indéfinie, primitive et non dégénérée de discriminant $1 < D_f \le \Delta$ , où $\Delta = \exp\left((\log 4 + o(1)) \frac{\log N}{\log \log N}\right)$ .
- Formes Définies Positives (Conditionnel) : En supposant la GRH, tout entier positif jusqu'à $N$ peut être représenté par une forme quadratique binaire primitive, définie positive, de discriminant $|D_f| \le \Delta$ (avec le même $\Delta$ que ci-dessus).
- Limitations : Il existe un entier positif $n \le N$ qui ne peut être représenté par aucune forme quadratique binaire primitive non dégénérée avec $|D_f| \le \Delta$ si $\Delta = \exp(c \log N / (\log \log N)^2)$ . Sous la GRH, ce seuil s'améliore en $\exp((\frac{\log 2}{2} - \epsilon) \frac{\log N}{\log \log N})$ .

Signification et Revendications
L'article prétend établir des « bornes presque optimales » pour le plus petit résidu quadratique, tant en termes de la taille du module que de son nombre de facteurs premiers. La construction de modules avec un $\ell(n)$ grand est motivée par des idées issues des codes correcteurs d'erreurs et représente une avancée significative par rapport aux attentes probabilistes, montrant que $\ell(n)$ peut être nettement plus grand que l'inverse de la densité des résidus quadratiques.

Les auteurs positionnent leur travail comme une variante du problème classique de la recherche du plus petit nombre premier $p$ tel que $\chi(p) = -1$ pour un caractère quadratique primitif $\chi$ . Alors que le problème classique est bien compris sous la GRH, cet article étend la portée aux modules composés et fournit des résultats inconditionnels qui sont seulement légèrement plus faibles que les résultats conditionnels.

De plus, l'article apporte des progrès quantitatifs précis sur le problème de la couverture de tous les entiers jusqu'à $N$ en utilisant des formes quadratiques binaires avec un discriminant borné. Alors que les travaux précédents (Green et Soundararajan) traitaient de la couverture de « presque tous » les entiers, cet article traite du problème plus difficile de la couverture de « tous » les entiers, établissant des seuils explicites pour le discriminant requis pour garantir la représentation.

Enfin, les auteurs notent une connexion avec les travaux de Hanson, Vaughan et Zhang concernant le plus petit $N$ requis pour que toutes les séquences de signes de longueur $k$ apparaissent comme des vecteurs de symboles de Legendre, suggérant un contexte plus large pour les méthodes combinatoires employées.

La Grande Chasse aux Nombres : Trouver le Premier Carré « Bon »

La Grande Découverte du Papier : Les Verrous « Malchanceux »

Pourquoi est-ce important ?

À Retenir

Articles similaires