무작위 실수 다항식의 최대 근이 복소수보다 실수일 가능성 더 높아

 (mathoverflow.net)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 실수 계수가 독립 균등분포인 무작위 다항식은 전체 실근 수가 대략 2log n/π에 그치지만, 실험에서는 절댓값이 가장 큰/작은 근이 실수일 확률이 더 높게 나타남
  • 차수별 10^5회 몬테카를로 시뮬레이션에서는 이 확률이 n이 커질수록 1/2 근처로 내려가며, 정규분포 계수를 (-1,1)로 스케일해도 비슷한 관찰이 유지됨
  • 한 답변은 유한 차수의 극단 근 문제가 무작위 멱급수 P(x)=a₀+a₁x+a₂x²+… 의 가장 작은 근이 실수인지 묻는 문제로 수렴한다고 봄
  • 분포에 따라 한계값은 달라질 수 있어, 균등분포 [-1,1]은 약 51%, 표준 정규분포는 약 52%, 분산 1/k! 정규분포는 62%, ±1 이산분포는 40%대 초반처럼 보임
  • 답변자는 “1/2로 수렴한다”는 해석에 회의적이며, 차수 200과 300을 비교한 4만 개 실험에서 가장 작은 근의 실수 여부가 모두 유지되어 한계가 50%보다 클 가능성을 강하게 봄

문제 설정: 실근은 적지만 극단 근은 실수 쪽으로 치우침

  • 실수 계수를 갖는 무작위 다항식에서는 전체 근 중 실근의 수가 복소근보다 훨씬 적음
    • 계수가 독립적으로 (-1,1) 균등분포를 따르면, 차수 n 다항식의 실근 수는 점근적으로 2log n/π + o(1)
    • 복소근 수는 대략 n - 2log n/π
    • 연결된 논문에 따르면 다른 계수 분포에서도 비슷한 점근식이 성립함
  • 여기서 “가장 큰 근”과 “가장 작은 근”은 각각 절댓값이 가장 큰 근과 절댓값이 가장 작은 근을 뜻함
  • 실근이 훨씬 적다면 극단 근도 복소수일 것 같지만, 질문자의 실험 데이터는 반대 방향을 보임

몬테카를로 관찰과 열린 질문

  • 관찰된 데이터의 핵심은 세 가지임
    • 가장 큰 근 또는 가장 작은 근이 실수일 확률이 복소수일 확률보다 큼
    • 이 확률은 n이 커질수록 1/2 근처의 값으로 감소하는 것처럼 보임
    • 각 n 값마다 10^5회 몬테카를로 시뮬레이션을 수행함
  • 계수를 균등분포 대신 평균 0, 표준편차 1인 정규분포에서 뽑고 (-1,1)로 스케일해도 같은 관찰과 한계 확률이 유지된다고 적음
  • 질문은 두 가지로 좁혀짐
    • 왜 가장 큰 근과 가장 작은 근이 실수 쪽으로 치우치는지
    • 차수 n에서 해당 확률이 n→∞일 때 1/2 근처의 값으로 수렴하는지
  • 관찰된 편향은 조건부 확률로 다음처럼 표현됨
    • P(L|R)=P(S|R)≈π/(4log n)
    • P(L|C)=P(S|C)≈π/(2nπ-4log n)

업데이트: 하한 증명과 n=1000 추가 실험

  • 연결된 Math StackExchange 글에서는 가장 큰 근이 실수일 확률이 적어도 다음 값 이상임이 증명됨
    • (23-16√2)/6 ≈ 6.2%
  • 2024년 5월 11일 업데이트에는 차수 n=1000 다항식에 대한 거의 60,000회 실험 결과가 추가됨
    • n≤125에서 관찰된 그래프와 일관된 결과로 나타남
    • 시행 횟수가 늘수록 가장 큰 근이 실수일 확률이 감소하는 추세를 보이며, 1/2로 수렴할 가능성이 있다고 적음

답변: 무작위 멱급수의 가장 작은 근으로 연결됨

  • Math StackExchange와 Thurston, Selberg, and random polynomials Part II 블로그 글을 근거로, 적절한 계수 분포에서는 유한 차수의 한계가 무작위 멱급수의 가장 작은 근 문제로 이어짐
    • P(x)=a₀+a₁x+a₂x²+…
    • 유한 차수에서 가장 작은 근이 실수일 확률의 한계는 이 무작위 멱급수의 가장 작은 근이 실수일 확률이 됨
  • Rouché 정리를 쓰면 이 확률이 0보다 크고 1보다 작음을 쉽게 보일 수 있다고 함
  • 한계값은 계수 aᵢ의 분포에 따라 달라질 수 있음
    • aᵢ가 [-1,1] 균등분포이면 약 51%
    • 평균 0, 분산 1인 Gaussian이면 약 52%
    • Gaussian이지만 분산이 1/k!이면 약 62%
    • 1과 -1의 이산분포이면 40%대 초반처럼 보임
  • 따라서 “합리적인 모든 경우에 50%보다 크다”기보다는, 모델에 따라 50%보다 크거나 작을 수 있음이 더 정확함

실근이 적어도 극단 근을 차지할 수 있는 이유

  • 많은 모델에서 근들은 단위원판 주변에 모이고 각도 분포는 균등해지는 경향이 있으며, 매우 국소적인 스케일에서는 근 사이 반발(repulsion) 이 생김
  • 복소근은 단위원판 둘레로 퍼질 수 있지만, 실근 사이의 반발은 실근들을 더 작거나 더 크게 만들도록 “강제”한다고 봄
  • 이 관점에서는 전체 실근 수가 로그 수준이어도, 가장 작은 근이나 가장 큰 근을 차지하기에는 충분히 많은 실근일 수 있음
  • 남는 과제는 몬테카를로로 쉽게 계산되는 값을 어떻게 엄밀한 수치 추정으로 만들지임

Rouché 정리로 엄밀한 추정을 만드는 아이디어

  • 균등분포 aᵢ∈[-1,1]를 가정하고, 낮은 차수 다항식들의 계수 공간을 작은 박스로 나누는 방식이 제안됨
    • 예시로 차수 100 미만 다항식에서 각 aᵢ를 같은 길이의 1000개 구간으로 나누는 방식이 언급됨
    • 답변에는 결과적으로 100^1000개의 다항식이 된다고 적혀 있음
  • 몬테카를로 관점에서는 대부분의 다항식을 다음 두 집합으로 나눌 수 있을 것으로 기대함
    • 가장 작은 근이 실수이고 절댓값이 9/10보다 작은 경우
    • 가장 작은 두 근이 복소켤레쌍이고 절댓값이 9/10보다 작은 경우
  • 두 경우 모두 해당 근만 포함하는 원판 경계에서 |P| > (9/10)^100을 보이면, Rouché 정리로 가장 작은 근의 성격이 유지됨을 보장할 수 있음
  • 이 방식은 이론적 장애는 없지만 실제 계산량이 너무 클 수 있어, 차수 10 미만과 10^10개 다항식 수준의 계산이나 더 효율적인 분할이 필요할 수 있음

1/2 수렴 해석에 대한 반박과 추가 계산

  • 답변자는 질문자의 “아마 1/2로 수렴한다”는 해석이 설득력 부족하다고 보며, 다른 자연스럽고 대칭적인 모델들이 1/2로 수렴하지 않는 점을 반대 근거로 듦
  • 차수 500 무작위 다항식 1000개를 생성해 가장 작은 근의 절댓값을 확인한 결과, 모든 경우에서 절댓값이 0.91보다 작음
    • 이를 무작위 멱급수로 확장하면 |z|<0.91 원판 안에서 함수 변화가 10^-20 규모이거나 더 작다고 적음
    • Rouché 정리가 적용되지 않으려면 가장 작은 근 또는 복소켤레쌍이 다음 근과 절댓값상 극도로 가까워야 함
  • 더 나은 수렴률 추정을 위해 다음 실험이 제안됨
    • 차수 500 무작위 다항식 50,000개를 계산
    • 같은 초기 항을 유지한 채 차수 1000으로 확장한 다항식 50,000개를 계산
    • 두 차수에서 가장 작은 근이 실수인지와, 차수를 늘릴 때 그 성격이 얼마나 자주 바뀌는지 확인
  • 답변자의 직관은 차수 500에서 1000으로 갈 때 바뀌는 경우가 매우 드물 것이라는 쪽임
    • 두 값이 모두 51% 근처이고 바뀌는 비율이 1%보다 훨씬 작다면, 한계가 50%보다 엄격히 크다는 신호로 볼 수 있음

실제 비교 실험: 차수 200과 300

  • 큰 차수 계산이 오래 걸려, 실제 비교는 차수 200과 300으로 진행됨
  • 40,000개 다항식 실행 결과:
    • 차수 200 다항식 중 20,287개에서 가장 작은 근이 실수였음
    • 이 다항식들을 차수 300으로 확장했을 때 모든 경우에서 같은 성질이 유지됨
  • 이 결과는 차수 200, 300, 1000의 기댓값이 무한 차수의 기댓값과 이미 매우 가까울 가능성을 시사함
  • 계산값은 약 50.7% 이며, 질문자의 계산도 비슷한 50.7% 수준이라 한계가 1/2보다 크다는 쪽의 근거로 제시됨
  • 답변자는 “한계가 50%보다 크다”고 자신하며, 자신이 틀렸음을 증명하는 사람에게 100달러를 주겠다고 덧붙임

절단 멱급수의 빠른 안정화

  • 추가 증거로 무작위 멱급수 P(x)=Σaᵢxᶦ의 절단 다항식 Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦ에 대해, k=1부터 1000까지 가장 작은 근이 실수인지 복소수인지가 언제 안정화되는지 확인함
  • 200개 무작위 다항식에서 안정화 시작점은 대부분 매우 작았음
    • 다수는 k=1 또는 k=2에서 이미 안정화됨
    • 나열된 값의 최대는 22
  • 이 결과도 유한 차수 실험이 무한 차수 한계와 빠르게 가까워질 수 있다는 판단을 뒷받침함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 우연 수준과 1/φ 사이에 있다는 게 정말 신기함
    링크된 MSE 글에서는 최대 근이 실수일 확률이 적어도 6.2%임이 이제 증명됐고, 심지어 1/φ의 1/10 이상임. 소수와 φ의 연결은 자연스럽다고 봄. 소수는 흔히 오해하듯 무작위가 아니라 이전 소수들에서 재귀적으로 생겨나며, 이전 소수의 배수들이 차지하지 못한 “간격”이기 때문임. 그래서 e나 φ 같은 어떤 자연 성장 패턴이 드러날 것을 기대할 만함. 진리와 아름다움 같은 아주 근본적인 크기의 패턴임

    • 소수에서 e가 나오는 방식은 커지는 간격만 모은 집합 크기 평균, 예를 들어 (2,3,5)(7,11)(13,17)... 또는 줄어들지 않는 간격만 모은 (2,3,5,7,11)(13,17)(19,23,29)... 같은 데서 볼 수 있음
      소수 자체의 성질이라기보다는 성장의 성질이고, 무작위 수 집합에서는 더 잘 맞음
    • 아름답다. φ는 항상 뭔가가 빽빽하게 몰릴 때 나타나는 것 같음

  • 바로 떠오르는 질문이 두 가지 있음

    1. 여기서 무작위란 무엇인가? 수치 실험을 한 듯한데, 유계 집합에서 균등한 정수 계수를 쓴 것과 비슷해 보이고, 그러면 결과가 크게 달라질 수 있음
    2. 항상 실근이 보장되는 홀수 차수를 봤는지, 짝수 차수를 봤는지, 둘 다 봤는지 궁금함
      이 재미있는 글을 깎아내리려는 건 아님
    • 정의에 쓰인 대로, 분포는 (-1,1)에서 독립인 균등 계수 분포임
    • 맞음. 원래 문제 서술은 역설적임. 무한한 집합에서 균등하게 표본을 뽑을 수는 없음. 원 글은 유계인 무작위 부동소수점을 썼다고 봄
      하지만 질문의 중요한 부분은 실수 위의 어떤 가능한 분포에 대해서도 물을 수 있음

  • 이걸로 수치 실험을 해보고 싶다면 R에 이런 용도의 내장 지원이 있음
    plot(polyroot(runif(101,-1,1)))
    이렇게 하면 100차 다항식의 근 시각화를 볼 수 있음

  • “계수가 독립이고 (−1,1)에서 균등 무작위라고 가정한다. 그렇지 않으면 각 계수를 절댓값이 가장 큰 계수로 나눠 각 계수를 (−1,1)로 스케일할 수 있기 때문이다.”
    직관이 맞는지 모르겠지만, 이렇게 나누어 스케일하면 가장 큰 계수를 제외한 나머지 계수들의 분포가 비균등 분포가 되지 않나?

    • 중요한 건 다항식에 상수를 곱해도 근은 변하지 않는다는 점임
    • 맞지만 실수 하나를 균등분포로 무작위 선택할 수는 없음. 어딘가에서는 양보해야 함

  • 5차 이상 다항식에는 공식이 없는데, 실근과 실수 + epsilon*i를 어떻게 구별하나?

    • Budan 정리 https://en.wikipedia.org/wiki/Budan%27s_theorem를 쓰면 구간 (r - ɛ, r + ɛ] 안에 실근이 정확히 하나인지, 또는 정확히 0개인지 인증할 수 있음
      추정값 r이 어떤 근에서 ɛ 이내에 있으면, 정확한 값이 없어도 실근과 복소근을 구별할 수 있음. 물론 Budan 정리가 답을 주지 못하는 경우도 있음. 예를 들어 그 구간 안에 근이 둘 이상 있으면 가장 명백하게 실패함
    • 고차 다항식의 근에 대한 정확한 공식이 불가능하다고 해서, 그런 다항식들의 근 분포를 알아낼 가능성까지 막히는 건 아님. 질문은 특정 다항식 하나가 아니라 분포에 관한 것이므로 Abel 정리가 장벽은 아님
      예를 들어 계수 a_i가 독립 동일 분포 Bernoulli 무작위 변수인 다항식 a_n x^n + ... + a_0를 생각하면, 차수 n이 크더라도(>4) 이런 다항식은 x = 0에서 실근을 가질 확률이 1/2이라고 자신 있게 말할 수 있음. 링크된 질문에서도 비슷하지만 더 정교한 논리가 작동함
    • 정수 계수 다항식이라면 가장 큰 근과 가장 작은 근을 계수 절댓값 최댓값의 어떤 거듭제곱 형태로 상계할 수 있음. 근이 가질 수 있는 가장 작은 허수부에 대해서도 비슷한 경계가 있을 것 같음
      계수가 실수라면 공식이 있어도 도움이 안 됨. 어떤 수가 0과 같은지 판별할 수 없다는 같은 문제가 있음. 예를 들어 이차 공식에서 판별식이 -epsilon일 수 있는데, epsilon이 0이면 허근이 없고 0이 아니면 허근이 있음
    • 여기서는 도함수를 쓸 수 있을 것 같음. x+iy와 x-iy가 복소근이고 y가 아주 작다면, x에서의 도함수도 작아야 함. y=0이면 이중근이므로 p'(x)=0이 됨
      따라서 p'(x)가 0에서 충분히 멀면 단일 실근이라고 볼 수 있음. 그리고 무작위 계수에서는 이중근이 사실상 일어나지 않을 것 같음
    • 추정은 수치 계산이 아니라 추론에 기반함. 예를 들어 실수값 다항식은 복소켤레에 대해 안정적이므로, 복소근이 있으면 그 켤레도 반드시 근임. 따라서 서로 다른 근이 셋인 다항식에서는 하나가 반드시 실근이어야 함. 이런 식의 추론으로 근이 순수 실수인지 복소수인지 알아낼 수 있음
      공식에 관해서는, 5차 이상에 대한 일반 공식은 없음. 일반 공식은 4차 이하 다항식에만 존재함
      물론 특정 종류의 고차 다항식에는 특정 공식이 있을 수 있음. 하지만 일반적인 5차 이상에 대해서는 없고, 이는 고전적으로 이미 증명됐음

  • 약간 주제에서 벗어나지만 이런 수학 글을 읽는 게 늘 즐거움
    대학에서 수학을 정말 좋아했고, 컴퓨터공학을 했지만 교수님들의 즐거움이 늘 자극이 됐음. 더 배우고, 수학으로 문제를 풀어보는 데 발을 담가보고 싶음. 아마 수치해석 쪽으로 기울 수도 있음
    다만 졸업한 지 2년 됐고 그동안 많이 안 해서 꽤 다시 배워야 할 듯함. 어디서 시작하면 좋을지, 재미있는 주제를 찾을 만한 곳이 있을지 궁금함. 수치해석은 아니지만 학부 때 Project Euler 문제를 꽤 풀었는데, 비슷한 게 더 있을까? 어떤 아이디어든 환영함
    아니면 먼저 교재의 모든 문제를 다시 풀어야 할까? ;-)

    • 대학 수준 수학을 어느 정도 알고 호기심이 있는 사람에게 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년 지나서 수학을 하러 대학에 갔고, 그때 수학 성적은 괜찮았지만 거의 다 잊은 상태였음. 예전에 풀었던 연습문제를 전부 다시 푸는 것보다 나은 방법은 없었고, 실제로는 완전히 잊은 게 아니라는 것도 알게 됨. 행운을 빔

  • 이런 종류의 수학을 몰라서 그런 건지 모르겠음
    내 머릿속에서는 “무작위” 다항식을 잡고 가장 큰 두 근만 봄. 그런 다음 두 번의 반사를 생각함. 곡선의 아래/위쪽을 기준으로 한 반사와 x축 기준 반사임. 그 상위 두 근이 퇴화하지 않았다면, 반사로 얻은 네 곡선의 조합 중 두 곡선은 최대 실근을 갖고, 두 곡선은 최대 허근을 갖는 것 같음. 퇴화했다면 최대 근은 실수임
    그래서 (1) 최대 근이 실수인 경우가 허수인 경우보다 많고, (2) 퇴화하지 않은 최대 근을 가진 곡선이 퇴화한 경우보다 무한히 많으므로 그 “우위”는 사라질 만큼 작다고 결론 내릴 것 같음
    용어를 거의 모른다는 건 보일 것임. 아마 무작위 계수의 균등성이 공간에서의 균등분포로 이어지지 않는다는 점을 놓친 것 같음. 아니면 내 반사가 조건 중 하나, 예를 들어 실수 계수 조건을 깨뜨릴 수도 있음. 아니면 그냥 틀렸을 수도 있고

    • 반사가 무슨 뜻인지 잘 모르겠음. 다항식 p(x)의 그래프를 x축에 대해 반사한다는 건 p(x)를 p(-x)로 바꾸는 것임. “곡선의 아래/위쪽을 기준으로 반사”한다는 건 무슨 뜻인가? y축 기준 반사인가? 그러면 p(x)가 -p(x)로 바뀐다는 뜻임
    • 곡선의 아래/위쪽을 기준으로 한 반사가 무슨 의미인가?
      조합이라는 건 아마 (다항식 + 반사된 다항식)/2를 취한다는 뜻인가?

  • 실수가 더 가능성이 높아 보인다는 점이 왜 반직관적인지 잘 모르겠음
    구간 안의 균등 무작위 실수 계수 대신, 복소평면 원점 중심의 원판에서 균등하게 무작위 근을 골라 다항식을 만든다면, 실수 계수 다항식이 나올 가능성은 거의 없음. 반대로 무작위 근이 실수라면 다항식은 반드시 실수 계수를 가짐. 따라서 사전적으로는 어느 답도 놀랍지 않고, 실수가 더 그럴듯해 보이는 쪽이 내게는 조금 더 직관적임. 물론 필연적인 건 아님

    • n차 다항식은 n개의 근을 가짐. 실근과 복소근을 모두 포함해서임. 무작위 다항식에서는 그중 대략 log(n)개가 실근이고, n - log(n)개가 비실근임
      n이 커지면 log(n)은 n에 비해 아주 작으므로, 절반이 넘는 경우에 최대 근이 그 극소수의 실근 중 하나라는 건 매우 놀라움

  • 여기 링크들을 따라가다 보니 Boris Hanin의 답변 중 하나가 한동안 갖고 있던 질문을 해결해준 것 같음

  • 그런데 무작위 다항식이라는 게 실수 계수인지 복소수 계수인지 궁금함

    • 복소수 계수를 허용하면 분포가 복소평면에서 회전 대칭이 됨. 그래서 어떤 근이 실수축에 있을 가능성은 원점을 지나는 다른 어떤 직선 위에 있을 가능성보다 크지 않음. 최대 근이 실수인 다항식은 거의 사라질 것임
    • 제시된 질문은 실수 계수라고 명시하고 있음. 실험적으로는 균등분포에서 [-1, 1] 범위의 무작위 계수를 고르고, 일종의 스케일된 정규분포도 테스트한 것으로 보임
    • 질문 첫 줄에 “real”이라고 되어 있음
답변달기