La plus grande racine d’un polynôme aléatoire à coefficients réels a plus de chances d’être réelle que complexe

 (mathoverflow.net)
1 points par GN⁺ 2024-05-12 | 1 commentaires | Partager sur WhatsApp
  • Un polynôme aléatoire dont les coefficients réels suivent des lois uniformes indépendantes n’a au total qu’environ 2log n/π racines réelles, mais les expériences montrent que la racine de plus grande/plus petite valeur absolue a une probabilité plus élevée d’être réelle
  • Dans des simulations de Monte-Carlo 10^5 fois pour chaque degré, cette probabilité baisse vers une valeur proche de 1/2 à mesure que n grandit, et une observation similaire se maintient même en mettant à l’échelle sur (-1,1) des coefficients gaussiens
  • Une réponse estime que le problème des racines extrêmes en degré fini converge vers la question de savoir si la plus petite racine d’une série entière aléatoire P(x)=a₀+a₁x+a₂x²+… est réelle
  • La valeur limite peut varier selon la distribution : la loi uniforme sur [-1,1] donne environ 51 %, la loi normale standard environ 52 %, une loi normale de variance 1/k! 62 %, tandis qu’une loi discrète ±1 semble se situer au début des 40 %
  • L’auteur de la réponse se montre sceptique face à l’interprétation selon laquelle « cela converge vers 1/2 » ; dans 40 000 expériences comparant les degrés 200 et 300, le caractère réel ou non de la plus petite racine s’est toujours conservé, ce qui suggère fortement que la limite pourrait être supérieure à 50 %

Mise en place du problème : peu de racines réelles, mais les racines extrêmes penchent vers le réel

  • Dans un polynôme aléatoire à coefficients réels, le nombre de racines réelles parmi toutes les racines est bien plus faible que celui des racines complexes
    • Si les coefficients suivent indépendamment une loi uniforme sur (-1,1), le nombre de racines réelles d’un polynôme de degré n est asymptotiquement 2log n/π + o(1)
    • Le nombre de racines complexes est approximativement n - 2log n/π
    • Selon l’article lié, une formule asymptotique similaire vaut aussi pour d’autres distributions des coefficients
  • Ici, « plus grande racine » et « plus petite racine » désignent respectivement la racine de plus grande valeur absolue et la racine de plus petite valeur absolue
  • Comme les racines réelles sont beaucoup moins nombreuses, on pourrait s’attendre à ce que les racines extrêmes soient elles aussi complexes, mais les données expérimentales de l’auteur de la question vont dans le sens inverse

Observations de Monte-Carlo et question ouverte

  • Les données observées se résument en trois points
    • La probabilité que la plus grande ou la plus petite racine soit réelle est supérieure à la probabilité qu’elle soit complexe
    • Cette probabilité semble décroître vers une valeur proche de 1/2 lorsque n augmente
    • Pour chaque valeur de n, 10^5 simulations de Monte-Carlo ont été réalisées
  • Il est également indiqué que la même observation et la même probabilité limite se maintiennent si, au lieu d’une loi uniforme, les coefficients sont tirés d’une loi normale de moyenne 0 et d’écart-type 1, puis mis à l’échelle sur (-1,1)
  • La question se resserre autour de deux points
    • Pourquoi la plus grande et la plus petite racine penchent vers le réel
    • Si, au degré n, cette probabilité converge vers une valeur proche de 1/2 lorsque n→∞
  • Le biais observé s’exprime sous forme de probabilités conditionnelles comme suit
    • P(L|R)=P(S|R)≈π/(4log n)
    • P(L|C)=P(S|C)≈π/(2nπ-4log n)

Mise à jour : preuve d’une borne inférieure et expérience supplémentaire pour n=1000

  • Dans le billet Math StackExchange lié, il est démontré que la probabilité que la plus grande racine soit réelle est au moins égale à
    • (23-16√2)/6 ≈ 6,2 %
  • La mise à jour du 11 mai 2024 ajoute les résultats de près de 60 000 expériences sur des polynômes de degré n=1000
    • Les résultats sont cohérents avec les graphiques observés pour n≤125
    • À mesure que le nombre d’essais augmente, la probabilité que la plus grande racine soit réelle tend à diminuer, et il est écrit qu’elle pourrait converger vers 1/2

Réponse : lien avec la plus petite racine d’une série entière aléatoire

  • En s’appuyant sur Math StackExchange et sur le billet de blog Thurston, Selberg, and random polynomials Part II, la réponse estime que, pour des distributions appropriées des coefficients, la limite en degré fini mène au problème de la plus petite racine d’une série entière aléatoire
    • P(x)=a₀+a₁x+a₂x²+…
    • La limite de la probabilité que la plus petite racine soit réelle en degré fini devient la probabilité que la plus petite racine de cette série entière aléatoire soit réelle
  • Avec le théorème de Rouché, il serait facile de montrer que cette probabilité est strictement comprise entre 0 et 1
  • La valeur limite peut dépendre de la distribution des coefficients aᵢ
    • Si les aᵢ suivent une loi uniforme sur [-1,1], elle est d’environ 51 %
    • S’ils suivent une loi gaussienne de moyenne 0 et variance 1, elle est d’environ 52 %
    • Dans le cas gaussien avec une variance 1/k!, elle est d’environ 62 %
    • Avec une loi discrète prenant les valeurs 1 et -1, elle semble se situer au début des 40 %
  • Il est donc plus juste de dire que, selon le modèle, la valeur peut être supérieure ou inférieure à 50 %, plutôt que « supérieure à 50 % dans tous les cas raisonnables »

Pourquoi les racines extrêmes peuvent être réelles malgré le faible nombre de racines réelles

  • Dans de nombreux modèles, les racines tendent à se concentrer autour du disque unité et leur distribution angulaire tend à devenir uniforme ; à une échelle très locale, une répulsion entre racines apparaît
  • Les racines complexes peuvent se répartir autour du bord du disque unité, mais la répulsion entre racines réelles « force » les racines réelles à devenir plus petites ou plus grandes
  • De ce point de vue, même si le nombre total de racines réelles n’est que logarithmique, il peut y en avoir suffisamment pour occuper la plus petite ou la plus grande racine
  • Le défi restant est de transformer en estimation numérique rigoureuse une valeur facile à calculer par Monte-Carlo

Idée pour obtenir une estimation rigoureuse avec le théorème de Rouché

  • En supposant une loi uniforme aᵢ∈[-1,1], il est proposé de découper l’espace des coefficients des polynômes de faible degré en petites boîtes
    • L’exemple mentionné consiste à diviser chaque aᵢ en 1 000 intervalles de même longueur pour des polynômes de degré inférieur à 100
    • La réponse indique qu’on obtient ainsi 100^1000 polynômes
  • Du point de vue Monte-Carlo, on peut s’attendre à classer la plupart des polynômes dans deux ensembles
    • Ceux dont la plus petite racine est réelle et de valeur absolue inférieure à 9/10
    • Ceux dont les deux plus petites racines forment une paire de conjuguées complexes et ont une valeur absolue inférieure à 9/10
  • Dans les deux cas, si l’on montre que |P| > (9/10)^100 sur le bord du disque ne contenant que ces racines, le théorème de Rouché garantit que le caractère de la plus petite racine est préservé
  • Cette méthode ne pose pas d’obstacle théorique, mais le volume de calcul réel pourrait être trop important ; il pourrait falloir se limiter à un degré inférieur à 10 avec environ 10^10 polynômes, ou trouver un découpage plus efficace

Réfutation de l’interprétation d’une convergence vers 1/2 et calculs supplémentaires

  • L’auteur de la réponse juge peu convaincante l’interprétation de l’auteur de la question selon laquelle « cela converge probablement vers 1/2 », et invoque comme contre-argument le fait que d’autres modèles naturels et symétriques ne convergent pas vers 1/2
  • Après avoir généré 1 000 polynômes aléatoires de degré 500 et vérifié la valeur absolue de leur plus petite racine, celle-ci était inférieure à 0,91 dans tous les cas
    • En prolongeant cela à une série entière aléatoire, il est écrit que la variation de la fonction dans le disque |z|<0.91 est de l’ordre de 10^-20 ou moins
    • Pour que le théorème de Rouché ne s’applique pas, il faudrait que la plus petite racine, ou la paire de conjuguées complexes, soit extrêmement proche de la racine suivante en valeur absolue
  • L’expérience suivante est proposée pour mieux estimer la vitesse de convergence
    • Calculer 50 000 polynômes aléatoires de degré 500
    • Calculer 50 000 polynômes étendus au degré 1000 tout en conservant les mêmes termes initiaux
    • Vérifier si la plus petite racine est réelle aux deux degrés, et à quelle fréquence ce caractère change lorsque le degré augmente
  • L’intuition de l’auteur de la réponse est que les changements devraient être très rares entre les degrés 500 et 1000
    • Si les deux valeurs sont proches de 51 % et que le taux de changement est bien inférieur à 1 %, cela peut être vu comme un signe que la limite est strictement supérieure à 50 %

Expérience comparative réelle : degrés 200 et 300

  • Comme les calculs sur de grands degrés prennent beaucoup de temps, la comparaison réelle a été effectuée avec les degrés 200 et 300
  • Résultat sur 40 000 polynômes :
    • Pour 20 287 polynômes de degré 200, la plus petite racine était réelle
    • Lorsque ces polynômes ont été prolongés au degré 300, cette propriété s’est conservée dans tous les cas
  • Ce résultat suggère que les valeurs attendues aux degrés 200, 300 et 1000 sont peut-être déjà très proches de la valeur attendue en degré infini
  • La valeur calculée est d’environ 50,7 %, et les calculs de l’auteur de la question sont eux aussi autour de 50,7 %, ce qui est présenté comme un argument en faveur d’une limite supérieure à 1/2
  • L’auteur de la réponse se dit convaincu que « la limite est supérieure à 50 % » et ajoute qu’il donnera 100 dollars à quiconque prouvera qu’il a tort

Stabilisation rapide des séries entières tronquées

  • Comme indice supplémentaire, pour les polynômes tronqués Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦ de la série entière aléatoire P(x)=Σaᵢxᶦ, il a été vérifié à partir de quelle valeur de k, entre 1 et 1000, le caractère réel ou complexe de la plus petite racine se stabilise
  • Sur 200 polynômes aléatoires, le point de stabilisation était le plus souvent très petit
    • Beaucoup se stabilisaient dès k=1 ou k=2
    • La valeur maximale de la liste était 22
  • Ce résultat soutient aussi l’idée que les expériences en degré fini peuvent se rapprocher rapidement de la limite en degré infini

À lire aussi

1 commentaires

 
GN⁺ 2024-05-12
Commentaires sur Hacker News

  • C’est vraiment étonnant que ce soit entre le niveau du hasard et 1/φ
    Dans le billet MSE lié, il est désormais prouvé que la probabilité que la plus grande racine soit réelle est d’au moins 6,2 %, soit même plus d’un dixième de 1/φ. Je trouve naturel le lien entre les nombres premiers et φ. Les nombres premiers ne sont pas aléatoires, contrairement à une idée reçue fréquente : ils naissent récursivement des nombres premiers précédents, car ce sont les « interstices » que les multiples des nombres premiers précédents n’ont pas occupés. On peut donc s’attendre à y voir apparaître un certain motif naturel de croissance, comme e ou φ. Un motif de grandeurs très fondamentales, comme la vérité et la beauté

    • La façon dont e apparaît dans les nombres premiers se voit dans la taille moyenne des ensembles formés uniquement d’écarts croissants, par exemple (2,3,5)(7,11)(13,17)..., ou uniquement d’écarts non décroissants, comme (2,3,5,7,11)(13,17)(19,23,29)...
      C’est davantage une propriété de la croissance qu’une propriété des nombres premiers eux-mêmes, et cela colle encore mieux avec des ensembles de nombres aléatoires
    • Magnifique. φ semble toujours apparaître quand quelque chose devient densément concentré

  • Deux questions me viennent immédiatement à l’esprit

    1. Que signifie « aléatoire » ici ? On dirait qu’ils ont fait une expérience numérique, avec quelque chose qui ressemble à des coefficients entiers uniformes dans un ensemble borné, et cela peut changer fortement le résultat
    2. Je me demande s’ils ont considéré des degrés impairs, où une racine réelle est toujours garantie, des degrés pairs, ou les deux
      Je ne cherche pas à dénigrer cet article intéressant
    • Comme indiqué dans la définition, la distribution est celle de coefficients uniformes indépendants sur (-1,1)
    • Exact. L’énoncé initial du problème est paradoxal. On ne peut pas échantillonner uniformément dans un ensemble infini. Je suppose que l’article original a utilisé des nombres à virgule flottante aléatoires bornés
      Mais la partie importante de la question peut être posée pour n’importe quelle distribution possible sur les réels

  • Si vous voulez faire des expériences numériques avec ça, R dispose d’un support intégré pour ce genre d’usage
    plot(polyroot(runif(101,-1,1)))
    Cela permet de voir une visualisation des racines d’un polynôme de degré 100

  • « On suppose que les coefficients sont indépendants et uniformément aléatoires sur (−1,1). Sinon, on peut mettre à l’échelle chaque coefficient dans (−1,1) en divisant chaque coefficient par celui de plus grande valeur absolue. »
    Je ne sais pas si mon intuition est correcte, mais avec cette division de mise à l’échelle, la distribution des coefficients autres que le plus grand ne devient-elle pas une distribution non uniforme ?

    • Le point important, c’est que multiplier un polynôme par une constante ne change pas ses racines
    • Oui, mais on ne peut pas choisir un nombre réel aléatoire selon une distribution uniforme. Il faut bien faire une concession quelque part

  • Il n’existe pas de formule pour les polynômes de degré 5 et plus ; comment distingue-t-on une racine réelle de réel + epsilon*i ?

    • Avec le théorème de Budan https://en.wikipedia.org/wiki/Budan%27s_theorem, on peut certifier qu’il y a exactement une racine réelle, ou exactement zéro, dans l’intervalle (r - ɛ, r + ɛ]
      Si l’estimation r est à moins de ɛ d’une racine, on peut distinguer une racine réelle d’une racine complexe sans connaître la valeur exacte. Bien sûr, il y a aussi des cas où le théorème de Budan ne donne pas de réponse. Par exemple, il échoue de la manière la plus évidente s’il y a deux racines ou plus dans cet intervalle
    • Le fait qu’une formule exacte pour les racines des polynômes de degré élevé soit impossible n’empêche pas de déterminer la distribution des racines de ces polynômes. La question porte sur une distribution, pas sur un polynôme particulier, donc le théorème d’Abel n’est pas un obstacle
      Par exemple, si l’on considère un polynôme a_n x^n + ... + a_0 dont les coefficients a_i sont des variables aléatoires de Bernoulli indépendantes et identiquement distribuées, on peut affirmer avec certitude que, même pour un degré n grand (>4), un tel polynôme a une racine réelle en x = 0 avec probabilité 1/2. Dans la question liée, une logique similaire, mais plus sophistiquée, est à l’œuvre
    • Pour un polynôme à coefficients entiers, on peut majorer la plus grande et la plus petite racine par une certaine puissance du maximum des valeurs absolues des coefficients. Il doit exister une borne similaire pour la plus petite partie imaginaire possible d’une racine
      Si les coefficients sont réels, même une formule n’aide pas. On rencontre le même problème : décider si un nombre est égal à 0. Par exemple, dans la formule quadratique, le discriminant peut être -epsilon ; si epsilon vaut 0, il n’y a pas de racine imaginaire, et s’il n’est pas nul, il y en a
    • Ici, on pourrait sans doute utiliser la dérivée. Si x+iy et x-iy sont des racines complexes et que y est très petit, alors la dérivée en x doit aussi être petite. Si y=0, c’est une racine double, donc p'(x)=0
      Par conséquent, si p'(x) est suffisamment éloignée de 0, on peut considérer qu’il s’agit d’une racine réelle simple. Et avec des coefficients aléatoires, les racines doubles ne devraient pratiquement jamais se produire
    • L’estimation repose sur le raisonnement, pas sur le calcul numérique. Par exemple, un polynôme à valeurs réelles est stable par conjugaison complexe : s’il a une racine complexe, son conjugué est nécessairement aussi une racine. Ainsi, dans un polynôme ayant trois racines distinctes, l’une d’elles doit forcément être réelle. Ce genre de raisonnement permet de déterminer si une racine est purement réelle ou complexe
      Pour ce qui est des formules, il n’existe pas de formule générale pour les degrés 5 et plus. Les formules générales n’existent que pour les polynômes de degré 4 ou moins
      Bien sûr, certains types particuliers de polynômes de degré élevé peuvent avoir des formules spécifiques. Mais il n’y en a pas pour les polynômes généraux de degré 5 et plus, et cela a déjà été démontré classiquement

  • C’est un peu hors sujet, mais j’aime toujours lire ce genre de textes sur les maths
    À l’université, j’aimais vraiment les maths, et même si j’ai fait de l’informatique, l’enthousiasme des profs m’a toujours stimulé. J’aimerais en apprendre davantage et mettre un pied dans la résolution de problèmes par les maths. Je pencherais peut-être vers l’analyse numérique
    Cela dit, j’ai obtenu mon diplôme il y a deux ans et je n’en ai pas beaucoup fait depuis, donc je vais sans doute devoir réapprendre pas mal de choses. Je me demande par où commencer, et où trouver des sujets intéressants. Ce n’est pas de l’analyse numérique, mais pendant ma licence j’ai résolu pas mal de problèmes Project Euler ; existe-t-il des choses similaires ? Toute idée est la bienvenue
    Ou bien faut-il d’abord que je refasse tous les exercices des manuels ? ;-)

    • Pour quelqu’un qui a quelques bases en maths de niveau universitaire et de la curiosité, Mathematics and Its History (https://link.springer.com/book/10.1007/978-1-4419-6053-5) est un livre vraiment passionnant
      Proofs from THE BOOK (https://link.springer.com/book/10.1007/978-3-662-57265-8) devrait aussi être agréable à lire
    • Ce n’est pas tout à fait la question, mais si tu aimes les maths, The Math Sorcerer vaut vraiment le détour : https://www.youtube.com/@TheMathSorcerer
    • Je suis allé à l’université pour faire des maths 6 ou 7 ans après avoir quitté l’école ; à l’époque j’avais de bonnes notes en maths, mais j’avais presque tout oublié. Il n’y avait pas de meilleure méthode que de refaire tous les exercices que j’avais déjà faits, et je me suis rendu compte qu’en réalité je n’avais pas tout oublié. Bonne chance

  • Je ne sais pas si c’est parce que je ne connais pas ce genre de maths
    Dans ma tête, je prends un polynôme « aléatoire » et je ne regarde que ses deux plus grandes racines. Ensuite, j’imagine deux réflexions : une réflexion par rapport au bas/haut de la courbe, et une réflexion par rapport à l’axe des x. Si ces deux racines du haut ne sont pas dégénérées, il me semble que parmi les quatre courbes obtenues par combinaison de ces réflexions, deux ont une racine réelle maximale et deux ont une racine imaginaire maximale. Si elles sont dégénérées, la racine maximale est réelle
    J’en conclurais donc que (1) les cas où la racine maximale est réelle sont plus nombreux que ceux où elle est imaginaire, et que (2) comme il y a infiniment plus de courbes à racine maximale non dégénérée que de cas dégénérés, cet « avantage » devient négligeable
    On voit bien que je ne maîtrise presque pas le vocabulaire. J’ai probablement manqué le fait que l’uniformité des coefficients aléatoires n’implique pas une distribution uniforme dans l’espace. Ou bien mes réflexions cassent peut-être l’une des conditions, par exemple celle des coefficients réels. Ou alors je me trompe tout simplement

    • Je ne suis pas sûr de comprendre ce que tu entends par réflexion. Réfléchir le graphe d’un polynôme p(x) par rapport à l’axe des x revient à remplacer p(x) par p(-x). Que veut dire « réflexion par rapport au bas/haut de la courbe » ? Une réflexion par rapport à l’axe des y ? Dans ce cas, cela signifie remplacer p(x) par -p(x)
    • Que signifie une réflexion par rapport au bas/haut de la courbe ?
      Par combinaison, tu veux peut-être dire prendre (polynôme + polynôme réfléchi)/2 ?

  • Je ne vois pas bien pourquoi le fait que les réelles semblent plus probables serait contre-intuitif
    Si, au lieu de coefficients réels uniformément aléatoires dans un intervalle, on choisissait des racines uniformément aléatoires dans un disque centré à l’origine du plan complexe pour construire un polynôme, la probabilité d’obtenir un polynôme à coefficients réels serait pratiquement nulle. À l’inverse, si les racines aléatoires sont réelles, le polynôme a nécessairement des coefficients réels. Donc, a priori, aucune des deux réponses n’est surprenante, et l’idée que les réelles soient plus plausibles me paraît un peu plus intuitive. Bien sûr, ce n’est pas une nécessité

    • Un polynôme de degré n a n racines, en comptant à la fois les racines réelles et complexes. Dans un polynôme aléatoire, environ log(n) d’entre elles sont réelles, et n - log(n) ne le sont pas
      Quand n grandit, log(n) est très petit par rapport à n, donc il est très surprenant que, dans plus de la moitié des cas, la racine maximale fasse partie de cette minuscule minorité de racines réelles

  • En suivant les liens ici, je crois qu’une des réponses de Boris Hanin a résolu une question que je me posais depuis un moment

  • Au fait, je me demande si, par polynôme aléatoire, on entend des coefficients réels ou complexes

    • Si l’on autorise les coefficients complexes, la distribution devient invariante par rotation dans le plan complexe. La probabilité qu’une racine donnée se trouve sur l’axe réel n’est donc pas plus grande que celle qu’elle se trouve sur n’importe quelle autre droite passant par l’origine. Les polynômes dont la racine maximale est réelle devraient presque disparaître
    • La question posée précise qu’il s’agit de coefficients réels. Expérimentalement, il semble qu’ils aient choisi des coefficients aléatoires dans [-1, 1] avec une distribution uniforme, et qu’ils aient aussi testé une sorte de loi normale mise à l’échelle
    • La première ligne de la question dit « real »