Akar maksimum polinomial acak berbobot real lebih mungkin real daripada kompleks

• Polinomial acak dengan koefisien real yang independen dan berdistribusi seragam hanya memiliki sekitar 2log n/π akar real secara keseluruhan, tetapi dalam eksperimen, peluang bahwa akar dengan nilai mutlak terbesar/terkecil adalah real tampak lebih tinggi
• Dalam 10^5 simulasi Monte Carlo per derajat, peluang ini turun mendekati 1/2 saat n membesar, dan pengamatan serupa tetap berlaku bahkan jika koefisien berdistribusi normal diskalakan ke (-1,1)
• Salah satu jawaban memandang bahwa masalah akar ekstrem pada derajat hingga berujung pada pertanyaan apakah akar terkecil dari deret pangkat acak P(x)=a₀+a₁x+a₂x²+… adalah real
• Bergantung pada distribusinya, nilai batas bisa berbeda: distribusi seragam [-1,1] sekitar 51%, distribusi normal standar sekitar 52%, distribusi normal dengan varians 1/k! 62%, dan distribusi diskret ±1 tampak berada di awal kisaran 40%
• Penjawab meragukan interpretasi bahwa nilainya “menuju 1/2”, dan dari 40.000 eksperimen yang membandingkan derajat 200 dan 300, ia melihat indikasi kuat bahwa batasnya bisa lebih besar dari 50%

---

Penetapan masalah: akar real sedikit, tetapi akar ekstrem condong ke real

• Pada polinomial acak dengan koefisien real, jumlah akar real di antara semua akar jauh lebih sedikit daripada akar kompleks
  • Jika koefisien mengikuti distribusi seragam independen pada (-1,1), jumlah akar real polinomial derajat n secara asimtotik adalah 2log n/π + o(1)
  • Jumlah akar kompleks kira-kira n - 2log n/π
  • Menurut makalah yang ditautkan, bentuk asimtotik serupa juga berlaku untuk distribusi koefisien lain
• Di sini, “akar terbesar” dan “akar terkecil” masing-masing berarti akar dengan nilai mutlak terbesar dan akar dengan nilai mutlak terkecil
• Jika akar real jauh lebih sedikit, akar ekstrem tampaknya juga akan kompleks, tetapi data eksperimen penanya menunjukkan arah sebaliknya

Pengamatan Monte Carlo dan pertanyaan terbuka

• Inti data yang diamati ada tiga
  • Peluang bahwa akar terbesar atau akar terkecil adalah real lebih besar daripada peluang bahwa ia kompleks
  • Peluang ini tampak menurun menuju nilai dekat 1/2 saat n membesar
  • Untuk setiap nilai n, dilakukan 10^5 simulasi Monte Carlo
• Disebutkan bahwa pengamatan dan peluang batas yang sama juga tetap berlaku jika koefisien diambil dari distribusi normal dengan rata-rata 0 dan simpangan baku 1 lalu diskalakan ke (-1,1), alih-alih distribusi seragam
• Pertanyaannya dipersempit menjadi dua
  • Mengapa akar terbesar dan akar terkecil condong ke sisi real
  • Apakah pada derajat n peluang tersebut konvergen ke nilai dekat 1/2 saat n→∞
• Bias yang teramati dapat dinyatakan sebagai peluang bersyarat berikut
  • P(L|R)=P(S|R)≈π/(4log n)
  • P(L|C)=P(S|C)≈π/(2nπ-4log n)

Pembaruan: bukti batas bawah dan eksperimen tambahan untuk n=1000

• Dalam posting Math StackExchange yang ditautkan, dibuktikan bahwa peluang akar terbesar bersifat real setidaknya sebesar nilai berikut
  • (23-16√2)/6 ≈ 6.2%
• Pembaruan 11 Mei 2024 menambahkan hasil hampir 60.000 eksperimen untuk polinomial derajat n=1000
  • Hasilnya konsisten dengan grafik yang diamati untuk n≤125
  • Disebutkan bahwa seiring bertambahnya jumlah percobaan, peluang akar terbesar bersifat real menunjukkan tren menurun, sehingga ada kemungkinan konvergen ke 1/2

Jawaban: terhubung ke akar terkecil deret pangkat acak

• Berdasarkan Math StackExchange dan tulisan blog Thurston, Selberg, and random polynomials Part II, untuk distribusi koefisien yang sesuai, limit pada derajat hingga mengarah ke masalah akar terkecil dari deret pangkat acak
  • P(x)=a₀+a₁x+a₂x²+…
  • Limit peluang bahwa akar terkecil bersifat real pada derajat hingga menjadi peluang bahwa akar terkecil dari deret pangkat acak ini adalah real
• Disebutkan bahwa dengan menggunakan teorema Rouché, mudah ditunjukkan bahwa peluang ini lebih besar dari 0 dan lebih kecil dari 1
• Nilai batas dapat berbeda tergantung distribusi koefisien aᵢ
  • Jika aᵢ berdistribusi seragam pada [-1,1], nilainya sekitar 51%
  • Jika Gaussian dengan rata-rata 0 dan varians 1, nilainya sekitar 52%
  • Jika Gaussian tetapi variansnya 1/k!, nilainya sekitar 62%
  • Jika distribusi diskretnya adalah 1 dan -1, nilainya tampak berada di awal kisaran 40%
• Jadi, alih-alih “lebih besar dari 50% untuk semua kasus yang masuk akal”, pernyataan yang lebih tepat adalah bahwa nilainya bisa lebih besar atau lebih kecil dari 50% tergantung model

Mengapa akar real yang sedikit tetap bisa menjadi akar ekstrem

• Dalam banyak model, akar-akar cenderung berkumpul di sekitar cakram satuan dan distribusi sudutnya cenderung seragam, sementara pada skala yang sangat lokal muncul tolakan (repulsion) antarakar
• Akar kompleks dapat tersebar di sekeliling lingkaran cakram satuan, tetapi tolakan antarak ar real dipandang “memaksa” akar-akar real menjadi lebih kecil atau lebih besar
• Dari sudut pandang ini, meskipun jumlah total akar real hanya berskala logaritmik, akar real tetap bisa cukup banyak untuk menempati posisi akar terkecil atau terbesar
• Tugas yang tersisa adalah bagaimana mengubah nilai yang mudah dihitung lewat Monte Carlo menjadi estimasi numerik yang ketat

Gagasan membuat estimasi ketat dengan teorema Rouché

• Dengan asumsi distribusi seragam aᵢ∈[-1,1], diusulkan cara membagi ruang koefisien polinomial derajat rendah ke dalam kotak-kotak kecil
  • Sebagai contoh, disebutkan pembagian tiap aᵢ menjadi 1000 interval dengan panjang sama untuk polinomial derajat kurang dari 100
  • Dalam jawaban tertulis bahwa hasilnya menjadi 100^1000 polinomial
• Dari sudut pandang Monte Carlo, diharapkan sebagian besar polinomial dapat dibagi ke dalam dua himpunan berikut
  • Akar terkecil bersifat real dan nilai mutlaknya kurang dari 9/10
  • Dua akar terkecil membentuk pasangan konjugat kompleks dan nilai mutlaknya kurang dari 9/10
• Dalam kedua kasus, jika pada batas cakram yang hanya memuat akar-akar tersebut berlaku |P| > (9/10)^100, maka teorema Rouché menjamin bahwa sifat akar terkecil tetap terpelihara
• Pendekatan ini tidak memiliki hambatan teoretis, tetapi beban komputasinya mungkin terlalu besar, sehingga bisa memerlukan perhitungan pada derajat kurang dari 10 dan sekitar 10^10 polinomial, atau partisi yang lebih efisien

Sanggahan terhadap interpretasi konvergensi ke 1/2 dan perhitungan tambahan

• Penjawab menganggap interpretasi penanya bahwa “mungkin konvergen ke 1/2” kurang meyakinkan, dan menggunakan fakta bahwa model lain yang alami dan simetris tidak konvergen ke 1/2 sebagai alasan penolakan
• Setelah membuat 1000 polinomial acak derajat 500 dan memeriksa nilai mutlak akar terkecil, pada semua kasus nilainya kurang dari 0.91
  • Jika ini diperluas ke deret pangkat acak, disebutkan bahwa perubahan fungsi di dalam cakram |z|<0.91 akan berskala 10^-20 atau lebih kecil
  • Agar teorema Rouché gagal diterapkan, akar terkecil atau pasangan konjugat kompleks tersebut harus sangat dekat dalam nilai mutlak dengan akar berikutnya
• Untuk memperkirakan laju konvergensi yang lebih baik, diusulkan eksperimen berikut
  • Menghitung 50.000 polinomial acak derajat 500
  • Menghitung 50.000 polinomial yang diperluas ke derajat 1000 dengan mempertahankan suku-suku awal yang sama
  • Memeriksa apakah akar terkecil bersifat real pada kedua derajat, dan seberapa sering sifat itu berubah saat derajat diperbesar
• Intuisi penjawab adalah bahwa saat berpindah dari derajat 500 ke 1000, kasus yang berubah akan sangat jarang
  • Jika kedua nilai sama-sama berada di sekitar 51% dan tingkat perubahannya jauh di bawah 1%, itu bisa dibaca sebagai sinyal bahwa batasnya secara ketat lebih besar dari 50%

Eksperimen perbandingan nyata: derajat 200 dan 300

• Karena perhitungan derajat besar memakan waktu lama, perbandingan nyata dilakukan pada derajat 200 dan 300
• Hasil untuk 40.000 polinomial:
  • Di antara polinomial derajat 200, 20.287 memiliki akar terkecil yang real
  • Ketika polinomial-polinomial ini diperluas ke derajat 300, dalam semua kasus sifat yang sama tetap bertahan
• Hasil ini menyiratkan bahwa nilai harapan untuk derajat 200, 300, dan 1000 mungkin sudah sangat dekat dengan nilai harapan pada derajat tak hingga
• Nilai yang dihitung adalah sekitar 50.7%, dan perhitungan penanya juga berada di kisaran 50,7%, sehingga ini diajukan sebagai bukti bahwa batasnya lebih besar dari 1/2
• Penjawab menyatakan yakin bahwa “batasnya lebih besar dari 50%” dan menambahkan bahwa ia akan memberi 100 dolar kepada siapa pun yang dapat membuktikan dirinya salah

Stabilisasi cepat pada deret pangkat yang dipotong

• Sebagai bukti tambahan, untuk polinomial potongan Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦ dari deret pangkat acak P(x)=Σaᵢxᶦ, diperiksa kapan status akar terkecil sebagai real atau kompleks menjadi stabil untuk k dari 1 sampai 1000
• Pada 200 polinomial acak, titik awal stabilisasi dalam kebanyakan kasus sangat kecil
  • Banyak yang sudah stabil pada k=1 atau k=2
  • Nilai maksimum dari daftar yang dicantumkan adalah 22
• Hasil ini juga mendukung penilaian bahwa eksperimen derajat hingga dapat mendekati limit derajat tak hingga dengan cepat

[GN⁺]

Pendapat di Hacker News

• Benar-benar menarik bahwa nilainya berada di antara tingkat kebetulan dan 1/φ
  Dalam tulisan MSE yang ditautkan, kini telah dibuktikan bahwa probabilitas akar terbesar bernilai real setidaknya 6,2%, bahkan lebih dari 1/10 dari 1/φ. Menurut saya, keterkaitan antara bilangan prima dan φ itu alami. Bilangan prima bukanlah acak seperti yang sering disalahpahami; bilangan prima muncul secara rekursif dari bilangan-bilangan prima sebelumnya, karena merupakan “celah” yang tidak ditempati oleh kelipatan bilangan prima sebelumnya. Jadi wajar bila kita mengharapkan munculnya semacam pola pertumbuhan alami seperti e atau φ. Ini adalah pola dari besaran yang sangat mendasar, seperti kebenaran dan keindahan

  • Cara e muncul dalam bilangan prima bisa dilihat dari rata-rata ukuran himpunan yang hanya mengumpulkan celah yang membesar, misalnya (2,3,5)(7,11)(13,17)..., atau yang hanya mengumpulkan celah yang tidak mengecil seperti (2,3,5,7,11)(13,17)(19,23,29)...
    Ini lebih merupakan sifat pertumbuhan daripada sifat bilangan prima itu sendiri, dan bahkan lebih cocok pada himpunan bilangan acak
  • Indah. φ tampaknya selalu muncul ketika sesuatu berjejal rapat

• Ada dua pertanyaan yang langsung terlintas

  1. Apa arti acak di sini? Sepertinya mereka melakukan eksperimen numerik, dan tampaknya mirip dengan menggunakan koefisien bilangan bulat yang seragam dari himpunan terbatas; jika begitu, hasilnya bisa sangat berbeda
  2. Saya penasaran apakah mereka melihat derajat ganjil, yang selalu menjamin adanya akar real, derajat genap, atau keduanya
     Saya tidak bermaksud meremehkan tulisan menarik ini
  • Sesuai definisi yang digunakan, distribusinya adalah distribusi koefisien seragam yang independen pada (-1,1)
  • Benar. Pernyataan masalah aslinya memang paradoksal. Kita tidak bisa mengambil sampel secara seragam dari himpunan tak hingga. Saya kira tulisan aslinya menggunakan bilangan floating-point acak yang terbatas
    Namun bagian penting dari pertanyaannya dapat diajukan untuk distribusi apa pun yang mungkin di atas bilangan real

• Jika ingin melakukan eksperimen numerik untuk ini, R punya dukungan bawaan untuk tujuan semacam ini
  plot(polyroot(runif(101,-1,1)))
  Dengan ini, Anda bisa melihat visualisasi akar dari polinomial derajat 100

• “Diasumsikan bahwa koefisiennya independen dan acak seragam pada (−1,1). Jika tidak, setiap koefisien dapat diskalakan ke (−1,1) dengan membaginya dengan koefisien yang nilai absolutnya paling besar.”
  Saya tidak yakin apakah intuisi saya benar, tetapi jika dibagi dan diskalakan seperti ini, bukankah distribusi koefisien selain koefisien terbesar menjadi distribusi tidak seragam?

  • Hal yang penting adalah mengalikan polinomial dengan konstanta tidak mengubah akarnya
  • Benar, tetapi kita tidak bisa memilih satu bilangan real secara acak dari distribusi seragam. Harus ada kompromi di suatu tempat

• Karena tidak ada rumus untuk polinomial derajat 5 ke atas, bagaimana membedakan akar real dari real + epsilon*i?

  • Dengan menggunakan teorema Budan https://en.wikipedia.org/wiki/Budan%27s_theorem, kita dapat memverifikasi apakah di dalam interval (r - ɛ, r + ɛ] terdapat tepat satu akar real, atau tepat nol akar real
    Jika perkiraan r berada dalam jarak ɛ dari suatu akar, kita bisa membedakan akar real dan akar kompleks tanpa mengetahui nilai persisnya. Tentu saja ada kasus ketika teorema Budan tidak memberikan jawaban. Misalnya, kegagalan paling jelas terjadi jika ada dua akar atau lebih di dalam interval tersebut
  • Fakta bahwa rumus eksak untuk akar polinomial berderajat tinggi tidak mungkin ada tidak berarti peluang untuk mengetahui distribusi akar polinomial semacam itu ikut tertutup. Pertanyaannya menyangkut distribusi, bukan satu polinomial tertentu, jadi teorema Abel bukan penghalang
    Misalnya, jika kita mempertimbangkan polinomial a_n x^n + ... + a_0 dengan koefisien a_i berupa variabel acak Bernoulli yang independen dan berdistribusi identik, kita bisa dengan yakin mengatakan bahwa meskipun derajat n besar (>4), polinomial seperti itu memiliki akar real di x = 0 dengan probabilitas 1/2. Dalam pertanyaan yang ditautkan, logika serupa tetapi lebih halus juga berlaku
  • Untuk polinomial dengan koefisien bilangan bulat, akar terbesar dan terkecil dapat dibatasi dari atas dalam bentuk suatu pangkat dari nilai maksimum absolut koefisien. Saya kira ada batas serupa juga untuk bagian imajiner terkecil yang mungkin dimiliki akar
    Jika koefisiennya real, rumus pun tidak membantu. Masalahnya sama: kita tidak bisa menentukan apakah suatu bilangan sama dengan 0. Misalnya dalam rumus kuadrat, diskriminannya bisa berupa -epsilon; jika epsilon adalah 0, tidak ada akar imajiner, dan jika tidak 0, ada akar imajiner
  • Di sini sepertinya turunan bisa digunakan. Jika x+iy dan x-iy adalah akar kompleks dan y sangat kecil, maka turunan di x juga harus kecil. Jika y=0, itu menjadi akar ganda sehingga p'(x)=0
    Karena itu, jika p'(x) cukup jauh dari 0, kita bisa menganggapnya sebagai akar real tunggal. Dan pada koefisien acak, akar ganda tampaknya praktis tidak terjadi
  • Perkiraan ini didasarkan pada penalaran, bukan perhitungan numerik. Misalnya, polinomial bernilai real stabil terhadap konjugat kompleks, sehingga jika ada akar kompleks, konjugatnya juga pasti merupakan akar. Jadi pada polinomial dengan tiga akar berbeda, salah satunya pasti akar real. Dengan penalaran semacam ini, kita bisa mengetahui apakah suatu akar murni real atau kompleks
    Mengenai rumus, tidak ada rumus umum untuk derajat 5 ke atas. Rumus umum hanya ada untuk polinomial derajat 4 ke bawah
    Tentu saja, mungkin ada rumus khusus untuk jenis polinomial berderajat tinggi tertentu. Tetapi untuk derajat 5 ke atas secara umum, tidak ada, dan ini sudah dibuktikan secara klasik

• Sedikit melenceng dari topik, tetapi saya selalu senang membaca tulisan matematika seperti ini
  Di universitas saya sangat menyukai matematika, dan meski saya mengambil ilmu komputer, antusiasme para dosen selalu menjadi dorongan. Saya ingin belajar lebih banyak dan mencoba ikut terjun memecahkan masalah dengan matematika. Mungkin saya akan cenderung ke arah analisis numerik
  Namun sudah 2 tahun sejak saya lulus dan selama itu saya tidak banyak melakukannya, jadi rasanya harus cukup banyak belajar ulang. Saya penasaran sebaiknya mulai dari mana, dan apakah ada tempat untuk menemukan topik yang menarik. Bukan analisis numerik, tetapi saat S1 saya cukup banyak mengerjakan soal Project Euler; apakah ada hal lain yang mirip? Ide apa pun diterima
  Atau sebaiknya saya menyelesaikan ulang semua soal di buku teks dulu? ;-)

  • Untuk orang yang sudah cukup mengenal matematika tingkat universitas dan punya rasa ingin tahu, Mathematics and Its History (https://link.springer.com/book/10.1007/978-1-4419-6053-5) adalah buku yang benar-benar menyenangkan
    Proofs from THE BOOK (https://link.springer.com/book/10.1007/978-3-662-57265-8) juga sepertinya bisa dinikmati
  • Sedikit berbeda dari pertanyaannya, tetapi kalau Anda menyukai matematika, The Math Sorcerer sayang untuk dilewatkan: https://www.youtube.com/@TheMathSorcerer
  • Saya pergi ke universitas untuk belajar matematika 6–7 tahun setelah meninggalkan sekolah; saat itu nilai matematika saya dulu lumayan, tetapi hampir semuanya sudah lupa. Tidak ada cara yang lebih baik daripada mengerjakan ulang semua soal latihan yang pernah saya kerjakan, dan saya juga menyadari bahwa sebenarnya saya tidak sepenuhnya lupa. Semoga berhasil

• Saya tidak tahu apakah ini karena saya tidak memahami matematika jenis ini
  Dalam bayangan saya, ambil polinomial “acak” lalu lihat hanya dua akar terbesarnya. Lalu pikirkan dua refleksi. Refleksi terhadap sisi bawah/atas kurva dan refleksi terhadap sumbu x. Jika dua akar teratas itu tidak degenerat, dari kombinasi empat kurva yang diperoleh lewat refleksi, tampaknya dua kurva memiliki akar real maksimum, dan dua kurva memiliki akar imajiner maksimum. Jika degenerat, akar maksimumnya real
  Jadi saya mungkin akan menyimpulkan bahwa (1) kasus akar maksimum real lebih banyak daripada kasus imajiner, dan (2) karena kurva dengan akar maksimum yang tidak degenerat jumlahnya tak terhingga lebih banyak daripada kasus degenerat, “keunggulan” itu cukup kecil hingga menghilang
  Terlihat jelas saya hampir tidak tahu istilahnya. Mungkin saya melewatkan bahwa keseragaman koefisien acak tidak berujung pada distribusi seragam di ruang. Atau refleksi saya mungkin melanggar salah satu syarat, misalnya syarat koefisien real. Atau mungkin saya memang keliru saja

  • Saya tidak begitu mengerti apa yang dimaksud dengan refleksi. Merefleksikan grafik polinomial p(x) terhadap sumbu x berarti mengubah p(x) menjadi p(-x). Apa maksud “refleksi terhadap sisi bawah/atas kurva”? Apakah refleksi terhadap sumbu y? Kalau begitu artinya p(x) berubah menjadi -p(x)
  • Apa maksud refleksi terhadap sisi bawah/atas kurva?
    Yang dimaksud kombinasi mungkin mengambil (polinomial + polinomial yang direfleksikan)/2?

• Saya tidak begitu paham mengapa fakta bahwa real tampak lebih mungkin itu berlawanan dengan intuisi
  Jika, alih-alih koefisien real acak seragam dalam suatu interval, kita memilih akar acak secara seragam dari cakram berpusat di titik asal pada bidang kompleks lalu membentuk polinomial, kemungkinan mendapatkan polinomial berkoefisien real nyaris nol. Sebaliknya, jika akar acaknya real, polinomialnya pasti memiliki koefisien real. Jadi secara apriori tidak ada jawaban yang mengejutkan, dan bagi saya sisi bahwa real lebih mungkin terasa sedikit lebih intuitif. Tentu saja itu bukan keniscayaan

  • Polinomial derajat n memiliki n akar. Itu mencakup akar real maupun akar kompleks. Pada polinomial acak, kira-kira log(n) di antaranya adalah akar real, dan n - log(n) adalah akar non-real
    Saat n membesar, log(n) sangat kecil dibanding n, jadi sangat mengejutkan bahwa dalam lebih dari separuh kasus, akar maksimum adalah salah satu dari segelintir akar real itu

• Saat mengikuti tautan-tautan di sini, salah satu jawaban Boris Hanin tampaknya menjawab pertanyaan yang sudah lama saya miliki

• Omong-omong, saya penasaran apakah yang dimaksud polinomial acak itu berkoefisien real atau berkoefisien kompleks

  • Jika koefisien kompleks diizinkan, distribusinya menjadi simetris rotasional di bidang kompleks. Jadi kemungkinan suatu akar berada pada sumbu real tidak lebih besar daripada kemungkinan berada pada garis lain mana pun yang melalui titik asal. Polinomial yang akar maksimumnya real nyaris akan hilang
  • Pertanyaan yang diajukan secara eksplisit menyebutkan koefisien real. Secara eksperimental, tampaknya mereka memilih koefisien acak dari rentang [-1, 1] pada distribusi seragam, dan juga menguji semacam distribusi normal yang diskalakan
  • Di baris pertama pertanyaan tertulis “real”