यादृच्छिक real coefficient polynomial की extreme root के complex से real होने की संभावना अधिक

• जिन यादृच्छिक polynomials के real coefficients independent uniform distribution से आते हैं, उनमें कुल real roots की संख्या लगभग 2log n/π ही होती है, लेकिन प्रयोगों में absolute value के लिहाज से सबसे बड़ी/सबसे छोटी root के real होने की probability अधिक दिखती है
• degree के हिसाब से 10^5 Monte Carlo simulations में यह probability n बढ़ने पर 1/2 के आसपास घटती दिखती है, और normal-distribution coefficients को (-1,1) पर scale करने पर भी मिलती-जुलती observation बनी रहती है
• एक उत्तर के अनुसार finite degree की extreme root वाली समस्या, random power series P(x)=a₀+a₁x+a₂x²+… की सबसे छोटी root के real होने के प्रश्न में converge करती है
• distribution के अनुसार limit value बदल सकती है: uniform distribution [-1,1] में लगभग 51%, standard normal distribution में लगभग 52%, variance 1/k! वाली normal distribution में 62%, और ±1 discrete distribution में यह 40% के शुरुआती दायरे जैसी दिखती है
• उत्तर देने वाला “1/2 पर converge करता है” वाली व्याख्या पर संदेह करता है; degree 200 और 300 की तुलना वाले 40,000 experiments में सबसे छोटी root के real होने की property सभी में बनी रही, इसलिए उसे limit के 50% से अधिक होने की संभावना मजबूत लगती है

---

समस्या की रूपरेखा: real roots कम हैं, लेकिन extreme roots real की ओर झुकी हुई हैं

• real coefficients वाले random polynomial में कुल roots में से real roots की संख्या complex roots से काफी कम होती है
  • यदि coefficients independent रूप से (-1,1) uniform distribution से आते हैं, तो degree n polynomial में real roots की संख्या asymptotically 2log n/π + o(1) होती है
  • complex roots की संख्या लगभग n - 2log n/π होती है
  • linked paper के अनुसार अन्य coefficient distributions में भी मिलते-जुलते asymptotic formulas लागू होते हैं
• यहां “largest root” और “smallest root” से मतलब क्रमशः absolute value में सबसे बड़ी root और absolute value में सबसे छोटी root है
• अगर real roots बहुत कम हैं, तो extreme root भी complex होने की उम्मीद लगती है, लेकिन प्रश्नकर्ता के experimental data में उलटी दिशा दिखती है

Monte Carlo observations और open question

• observed data का सार तीन बातों में है
  • largest root या smallest root के real होने की probability, complex होने की probability से अधिक है
  • n बढ़ने पर यह probability 1/2 के आसपास के value तक घटती दिखती है
  • हर n value के लिए 10^5 Monte Carlo simulations किए गए
• लिखा गया है कि coefficients को uniform distribution के बजाय mean 0, standard deviation 1 वाली normal distribution से लेकर (-1,1) पर scale करने पर भी वही observation और limit probability बनी रहती है
• प्रश्न दो बातों तक सीमित होता है
  • largest root और smallest root real की ओर biased क्यों हैं
  • degree n पर यह probability n→∞ होने पर 1/2 के आसपास के value पर converge करती है या नहीं
• observed bias को conditional probability के रूप में इस तरह व्यक्त किया गया है
  • P(L|R)=P(S|R)≈π/(4log n)
  • P(L|C)=P(S|C)≈π/(2nπ-4log n)

अपडेट: lower bound proof और n=1000 के अतिरिक्त प्रयोग

• linked Math StackExchange post में prove किया गया है कि largest root के real होने की probability कम से कम इस value से अधिक या बराबर है
  • (23-16√2)/6 ≈ 6.2%
• 11 मई 2024 के अपडेट में degree n=1000 polynomial पर लगभग 60,000 experiments के results जोड़े गए
  • ये n≤125 में observed graph के साथ consistent result के रूप में दिखे
  • लिखा गया है कि trials की संख्या बढ़ने पर largest root के real होने की probability घटने का trend दिखता है, और संभव है कि यह 1/2 पर converge करे

उत्तर: random power series की smallest root से संबंध

• Math StackExchange और Thurston, Selberg, and random polynomials Part II blog post के आधार पर, उचित coefficient distribution में finite degree की limit random power series की smallest root वाली समस्या में बदल जाती है
  • P(x)=a₀+a₁x+a₂x²+…
  • finite degree में smallest root के real होने की probability की limit, इस random power series की smallest root के real होने की probability बन जाती है
• कहा गया है कि Rouché theorem का उपयोग करके आसानी से दिखाया जा सकता है कि यह probability 0 से बड़ी और 1 से छोटी है
• limit value coefficient aᵢ के distribution के अनुसार बदल सकती है
  • यदि aᵢ [-1,1] uniform distribution से है, तो लगभग 51%
  • mean 0, variance 1 वाले Gaussian में लगभग 52%
  • Gaussian लेकिन variance 1/k! हो तो लगभग 62%
  • 1 और -1 की discrete distribution में यह 40% के शुरुआती दायरे जैसी दिखती है
• इसलिए “हर reasonable case में 50% से बड़ी” कहने के बजाय, यह कहना अधिक सही है कि model के अनुसार यह 50% से बड़ी या छोटी हो सकती है

real roots कम होने पर भी extreme root पर कब्जा क्यों कर सकती हैं

• कई models में roots unit disk के आसपास जमा होती हैं और angular distribution uniform होने की प्रवृत्ति रखती है; बहुत local scale पर roots के बीच repulsion पैदा होती है
• complex roots unit disk की परिधि पर फैल सकती हैं, लेकिन real roots के बीच repulsion real roots को और छोटा या और बड़ा बनाने के लिए “force” करती है—ऐसा माना जाता है
• इस नजरिए से, कुल real roots की संख्या logarithmic level पर होने पर भी smallest root या largest root हासिल करने के लिए real roots पर्याप्त संख्या में हो सकती हैं
• बचा हुआ काम यह है कि Monte Carlo से आसानी से निकाले जाने वाले values को rigorous numerical estimate में कैसे बदला जाए

Rouché theorem से rigorous estimate बनाने का idea

• uniform distribution aᵢ∈[-1,1] मानकर, low-degree polynomials के coefficient space को छोटे boxes में बांटने का तरीका सुझाया गया
  • example के तौर पर degree 100 से कम polynomials में हर aᵢ को समान लंबाई के 1000 intervals में बांटने का तरीका बताया गया
  • उत्तर में लिखा है कि परिणामस्वरूप 100^1000 polynomials बनते हैं
• Monte Carlo perspective से उम्मीद है कि अधिकतर polynomials को इन दो sets में बांटा जा सकता है
  • smallest root real है और उसकी absolute value 9/10 से कम है
  • दो smallest roots complex conjugate pair हैं और उनकी absolute value 9/10 से कम है
• दोनों मामलों में, अगर केवल उस root को शामिल करने वाली disk boundary पर |P| > (9/10)^100 दिखाया जाए, तो Rouché theorem से smallest root की प्रकृति बनी रहने की guarantee मिल सकती है
• इस approach में theoretical बाधा नहीं है, लेकिन actual computation बहुत ज्यादा हो सकता है; इसलिए degree 10 से कम और 10^10 polynomials स्तर की computation या अधिक efficient partitioning की जरूरत पड़ सकती है

1/2 convergence interpretation पर आपत्ति और additional calculations

• उत्तर देने वाला प्रश्नकर्ता की “शायद 1/2 पर converge करता है” वाली interpretation को पर्याप्त convincing नहीं मानता, और विरोध में यह आधार देता है कि अन्य natural और symmetric models 1/2 पर converge नहीं करते
• degree 500 के 1000 random polynomials generate करके smallest root की absolute value देखने पर, सभी cases में absolute value 0.91 से कम थी
  • इसे random power series तक extend करने पर |z|<0.91 disk के अंदर function change 10^-20 के scale पर या उससे भी कम होगा, ऐसा लिखा गया है
  • Rouché theorem लागू न होने के लिए smallest root या complex conjugate pair को next root से absolute value में अत्यंत close होना पड़ेगा
• बेहतर convergence rate estimate के लिए निम्न experiment सुझाया गया
  • degree 500 के 50,000 random polynomials compute करें
  • वही initial terms बनाए रखते हुए degree 1000 तक extend किए गए 50,000 polynomials compute करें
  • दोनों degrees में smallest root real है या नहीं, और degree बढ़ाने पर उसका character कितनी बार बदलता है, यह जांचें
• उत्तर देने वाले की intuition है कि degree 500 से 1000 पर जाते समय बदलाव बहुत rare होंगे
  • अगर दोनों values 51% के आसपास हों और बदलाव की rate 1% से काफी कम हो, तो यह संकेत माना जा सकता है कि limit strictly 50% से बड़ी है

वास्तविक comparison experiment: degree 200 और 300

• बड़े degree की computation में समय लगने के कारण, actual comparison degree 200 और 300 पर किया गया
• 40,000 polynomials चलाने के results:
  • degree 200 polynomials में 20,287 cases में smallest root real थी
  • जब इन्हीं polynomials को degree 300 तक extend किया गया, तो सभी cases में वही property बनी रही
• यह result संकेत देता है कि degree 200, 300, 1000 की expected values infinite degree की expected value के पहले से ही बहुत करीब हो सकती हैं
• computed value लगभग 50.7% है, और प्रश्नकर्ता की calculation भी मिलते-जुलते 50.7% level पर है; इसे limit के 1/2 से अधिक होने के पक्ष में evidence के रूप में रखा गया
• उत्तर देने वाला कहता है कि उसे “limit 50% से बड़ी है” इस पर भरोसा है, और जो कोई उसे गलत साबित करेगा उसे 100 dollars देने की बात जोड़ता है

truncated power series की तेज stabilization

• अतिरिक्त evidence के तौर पर random power series P(x)=Σaᵢxᶦ की truncated polynomial Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦ के लिए, k=1 से 1000 तक यह जांचा गया कि smallest root real है या complex, और यह कब stabilize होता है
• 200 random polynomials में stabilization starting point अधिकतर बहुत छोटा था
  • कई cases k=1 या k=2 पर ही stabilize हो गए
  • list किए गए values में maximum 22 था
• यह result भी इस judgment को support करता है कि finite degree experiments infinite degree limit के बहुत जल्दी करीब पहुंच सकते हैं

[GN⁺]

Hacker News टिप्पणियाँ

• यह सचमुच दिलचस्प है कि यह संयोग के स्तर और 1/φ के बीच है
  लिंक किए गए MSE पोस्ट में अब यह सिद्ध हो चुका है कि सबसे बड़े मूल के वास्तविक होने की संभावना कम-से-कम 6.2% है, और यह 1/φ के 1/10 से भी ज़्यादा है। मुझे अभाज्य संख्याओं और φ का संबंध स्वाभाविक लगता है। अभाज्य संख्याएँ, जैसा अक्सर गलत समझा जाता है, random नहीं होतीं; वे पिछली अभाज्य संख्याओं से recursively बनती हैं, क्योंकि वे उन “खालियों” में आती हैं जिन्हें पिछली अभाज्य संख्याओं के गुणज नहीं भर पाए। इसलिए e या φ जैसे किसी natural growth pattern के दिखने की उम्मीद की जा सकती है। यह सत्य और सुंदरता जैसे बेहद मूलभूत परिमाणों का pattern है

  • अभाज्य संख्याओं में e जिस तरह दिखता है, वह बढ़ते gap को इकट्ठा करने वाले set के आकार के average में देखा जा सकता है, जैसे (2,3,5)(7,11)(13,17)... या घटते नहीं जाने वाले gap को इकट्ठा करने वाले (2,3,5,7,11)(13,17)(19,23,29)... में
    यह अभाज्य संख्याओं की अपनी property से ज़्यादा growth की property है, और random numbers के set में और बेहतर fit बैठती है
  • सुंदर। φ हमेशा तब दिखाई देता लगता है जब कोई चीज़ बहुत सघन होकर जमा होती है

• तुरंत मेरे मन में दो सवाल आते हैं

  1. यहाँ random से क्या मतलब है? लगता है numerical experiment किया गया है; यह किसी bounded set से uniform integer coefficients लेने जैसा दिखता है, और ऐसा हो तो परिणाम काफी बदल सकते हैं
  2. क्या उन्होंने odd degree देखा, जहाँ हमेशा एक real root guaranteed होता है, या even degree देखा, या दोनों?
     मेरा इरादा इस दिलचस्प लेख को कमतर दिखाने का नहीं है
  • जैसा definition में इस्तेमाल हुआ है, distribution (-1,1) में independent uniform coefficients की distribution है
  • सही है। मूल problem statement paradoxical है। infinite set से uniformly sample नहीं लिया जा सकता। मुझे लगता है मूल पोस्ट में bounded random floating-point values इस्तेमाल किए गए थे
    लेकिन सवाल का अहम हिस्सा real numbers पर किसी भी possible distribution के बारे में पूछा जा सकता है

• अगर आप इस पर numerical experiment करना चाहते हैं, तो R में इस काम के लिए built-in support है
  plot(polyroot(runif(101,-1,1)))
  इससे 100-degree polynomial के roots visualization को देखा जा सकता है

• “मान लेते हैं कि coefficients independent हैं और (−1,1) में uniformly random हैं। वरना हर coefficient को सबसे बड़े absolute value वाले coefficient से divide करके हर coefficient को (−1,1) में scale किया जा सकता है।”
  पता नहीं मेरी intuition सही है या नहीं, लेकिन इस तरह divide करके scale करने पर सबसे बड़े coefficient को छोड़कर बाकी coefficients की distribution non-uniform distribution नहीं हो जाएगी?

  • अहम बात यह है कि polynomial को constant से multiply करने पर roots नहीं बदलते
  • सही, लेकिन किसी real number को uniform distribution से random तौर पर choose नहीं किया जा सकता। कहीं न कहीं समझौता करना ही होगा

• degree 5 या उससे ऊपर के polynomials के लिए formula नहीं है, तो real root और real + epsilon*i में फर्क कैसे करेंगे?

  • Budan’s theorem https://en.wikipedia.org/wiki/Budan%27s_theorem इस्तेमाल करके certify किया जा सकता है कि interval (r - ɛ, r + ɛ] में exactly एक real root है, या exactly 0 real roots हैं
    अगर estimate r किसी root से ɛ के भीतर है, तो exact value न होने पर भी real root और complex root में फर्क किया जा सकता है। बेशक ऐसे cases भी होते हैं जहाँ Budan’s theorem जवाब नहीं दे पाता। उदाहरण के लिए, अगर उस interval में दो या उससे ज़्यादा roots हों तो यह सबसे साफ़ तौर पर fail करता है
  • higher-degree polynomials के roots के लिए exact formula असंभव होना, ऐसे polynomials की root distribution जानने की संभावना को नहीं रोकता। सवाल किसी एक specific polynomial का नहीं बल्कि distribution का है, इसलिए Abel’s theorem कोई barrier नहीं है
    उदाहरण के लिए, अगर coefficients a_i independent identically distributed Bernoulli random variables हों और polynomial a_n x^n + ... + a_0 हो, तो degree n बड़ा (>4) होने पर भी हम confidently कह सकते हैं कि ऐसे polynomial के x = 0 पर real root होने की probability 1/2 है। लिंक किए गए सवाल में भी इसी तरह का, लेकिन अधिक sophisticated logic काम करता है
  • integer coefficients वाले polynomial के लिए सबसे बड़े root और सबसे छोटे root को coefficients के absolute values के maximum की किसी power के रूप में upper-bound किया जा सकता है। root के संभव सबसे छोटे imaginary part के लिए भी शायद ऐसा ही bound होगा
    अगर coefficients real हों, तो formula होने पर भी मदद नहीं मिलती। वही समस्या रहती है कि कोई number 0 के बराबर है या नहीं, यह तय नहीं कर सकते। उदाहरण के लिए quadratic formula में discriminant -epsilon हो सकता है; अगर epsilon 0 है तो कोई imaginary roots नहीं हैं, और 0 नहीं है तो imaginary roots हैं
  • यहाँ derivative इस्तेमाल किया जा सकता है। अगर x+iy और x-iy complex roots हैं और y बहुत छोटा है, तो x पर derivative भी छोटा होना चाहिए। y=0 होने पर double root होता है, इसलिए p'(x)=0 होता है
    इसलिए अगर p'(x) 0 से पर्याप्त दूर है, तो उसे single real root माना जा सकता है। और random coefficients में double root practically होने की संभावना नहीं लगती
  • अनुमान numerical calculation पर नहीं, reasoning पर आधारित है। उदाहरण के लिए real-valued polynomial complex conjugates के प्रति stable होता है, इसलिए अगर कोई complex root है तो उसका conjugate भी root होना ही चाहिए। इसलिए तीन अलग-अलग roots वाले polynomial में उनमें से एक root ज़रूर real होगा। ऐसी reasoning से पता लगाया जा सकता है कि root pure real है या complex
    formula की बात करें तो degree 5 या उससे ऊपर के लिए कोई general formula नहीं है। general formula केवल degree 4 या उससे नीचे के polynomials के लिए मौजूद है
    ज़ाहिर है, higher-degree polynomials की कुछ specific categories के लिए specific formula हो सकते हैं। लेकिन general degree 5 या उससे ऊपर के लिए नहीं हैं, और यह classical रूप से पहले ही prove हो चुका है

• विषय से थोड़ा हटकर, लेकिन ऐसे गणित वाले लेख पढ़ना हमेशा अच्छा लगता है
  यूनिवर्सिटी में मुझे गणित सचमुच बहुत पसंद था, और मैंने कंप्यूटर साइंस किया, लेकिन प्रोफेसरों का उत्साह हमेशा प्रेरणा देता था। और सीखना चाहता/चाहती हूँ, और गणित से समस्याएँ हल करने में हाथ आज़माना चाहता/चाहती हूँ। शायद रुझान numerical analysis की तरफ हो सकता है
  हालांकि ग्रेजुएट हुए 2 साल हो गए हैं और इस बीच ज़्यादा नहीं किया, इसलिए लगता है काफ़ी कुछ फिर से सीखना पड़ेगा। कहाँ से शुरू करना अच्छा रहेगा, या दिलचस्प topics खोजने की कोई जगह है क्या? numerical analysis नहीं है, लेकिन अंडरग्रैड के समय Project Euler की काफ़ी problems हल की थीं; क्या वैसा कुछ और भी है? कोई भी ideas स्वागतयोग्य हैं
  या फिर पहले textbook की सारी problems फिर से हल करनी चाहिए? ;-)

  • कॉलेज-लेवल गणित की कुछ समझ और जिज्ञासा रखने वाले व्यक्ति के लिए Mathematics and Its History (https://link.springer.com/book/10.1007/978-1-4419-6053-5) सचमुच मज़ेदार किताब है
    Proofs from THE BOOK (https://link.springer.com/book/10.1007/978-3-662-57265-8) भी शायद आनंद से पढ़ी जा सकेगी
  • सवाल से थोड़ा अलग है, लेकिन अगर गणित पसंद है तो The Math Sorcerer को मिस करना अफ़सोस की बात होगी: https://www.youtube.com/@TheMathSorcerer
  • स्कूल छोड़ने के 6~7 साल बाद गणित पढ़ने यूनिवर्सिटी गया था, और उस समय गणित के ग्रेड ठीक थे, लेकिन लगभग सब भूल चुका था। पहले हल की हुई exercises सारी फिर से हल करने से बेहतर कोई तरीका नहीं था, और असल में पता चला कि सब कुछ पूरी तरह भूला नहीं था। शुभकामनाएँ

• पता नहीं, शायद इसलिए कि इस तरह का गणित नहीं जानता/जानती
  मेरे दिमाग में “random” polynomial लेकर सिर्फ़ सबसे बड़े दो roots देखता/देखती हूँ। फिर दो reflections के बारे में सोचता/सोचती हूँ। एक curve के नीचे/ऊपर के आधार पर reflection और एक x-axis के आधार पर reflection। अगर वे top two roots degenerate नहीं हैं, तो reflection से मिली चार curves के combinations में से दो curves के पास maximum real root होगा, और दो curves के पास maximum imaginary root होगा, ऐसा लगता है। अगर degenerate हों तो maximum root real होगा
  इसलिए मैं शायद निष्कर्ष निकालूँगा/निकालूँगी कि (1) maximum root real होने के मामले imaginary होने के मामलों से ज़्यादा हैं, और (2) non-degenerate maximum root वाली curves, degenerate मामलों से अनंत रूप से ज़्यादा हैं, इसलिए वह “बढ़त” गायब हो जाने जितनी छोटी है
  दिख ही रहा होगा कि terminology लगभग नहीं जानता/जानती। शायद मैं यह बात miss कर रहा/रही हूँ कि random coefficients की uniformity, space में uniform distribution में नहीं बदलती। या फिर मेरी reflection किसी condition को तोड़ देती है, जैसे real coefficients वाली condition। या फिर मैं बस गलत भी हो सकता/सकती हूँ

  • reflection से आपका मतलब क्या है, ठीक से समझ नहीं आया। polynomial p(x) के graph को x-axis के सापेक्ष reflect करने का मतलब p(x) को p(-x) में बदलना है। “curve के नीचे/ऊपर के आधार पर reflect” करने का क्या मतलब है? क्या y-axis के सापेक्ष reflection? तब इसका मतलब होगा कि p(x) -p(x) में बदलता है
  • curve के नीचे/ऊपर के आधार पर reflection का क्या अर्थ है?
    combination से आपका मतलब शायद (polynomial + reflected polynomial)/2 लेना है?

• मुझे ठीक से समझ नहीं आता कि real ज़्यादा likely लगना counterintuitive क्यों है
  interval के अंदर uniformly random real coefficients के बजाय, अगर complex plane में origin-centered disk से uniformly random roots चुनकर polynomial बनाया जाए, तो real coefficient polynomial आने की संभावना लगभग नहीं होगी। उल्टा, अगर random roots real हों तो polynomial के coefficients ज़रूर real होंगे। इसलिए a priori कोई भी जवाब चौंकाने वाला नहीं है, और real ज़्यादा plausible लगना मुझे थोड़ा ज़्यादा intuitive लगता है। बेशक यह अनिवार्य नहीं है

  • degree n polynomial के n roots होते हैं। इसमें real roots और complex roots दोनों शामिल हैं। random polynomial में उनमें से लगभग log(n) real roots होते हैं, और n - log(n) non-real roots
    n बड़ा होने पर log(n), n की तुलना में बहुत छोटा होता है, इसलिए आधे से ज़्यादा मामलों में maximum root उन बहुत कम real roots में से एक हो, यह काफ़ी हैरान करने वाली बात है

• यहाँ links follow करते-करते लगता है Boris Hanin के एक जवाब ने मेरा काफ़ी समय से चला आ रहा एक सवाल हल कर दिया

• वैसे random polynomial से मतलब real coefficients है या complex coefficients, यह जानना चाहता/चाहती हूँ

  • अगर complex coefficients allow किए जाएँ, तो distribution complex plane में rotationally symmetric हो जाता है। इसलिए किसी root के real axis पर होने की संभावना, origin से गुजरने वाली किसी भी दूसरी line पर होने की संभावना से ज़्यादा नहीं होती। maximum root real होने वाले polynomials लगभग गायब हो जाएँगे
  • दिए गए question में साफ़ लिखा है कि coefficients real हैं। Experimental तौर पर लगता है uniform distribution में [-1, 1] range के random coefficients चुने गए, और किसी तरह की scaled normal distribution भी test की गई
  • question की पहली line में “real” लिखा है