Raiz máxima de polinômio aleatório real tem maior chance de ser real do que complexa

• Polinômios aleatórios com coeficientes reais independentes e uniformes têm apenas cerca de 2log n/π raízes reais no total, mas os experimentos mostram uma probabilidade maior de a raiz de maior/menor valor absoluto ser real
• Em 10^5 simulações de Monte Carlo por grau, essa probabilidade cai em direção a 1/2 à medida que n cresce, e observações semelhantes permanecem mesmo ao escalar coeficientes de distribuição normal para (-1,1)
• Uma resposta argumenta que o problema das raízes extremas em grau finito converge para a questão de saber se a menor raiz da série de potências aleatória P(x)=a₀+a₁x+a₂x²+… é real
• Dependendo da distribuição, o valor-limite pode variar: a uniforme em [-1,1] fica em cerca de 51%, a normal padrão em cerca de 52%, a normal com variância 1/k! em 62%, e a distribuição discreta ±1 parece ficar no começo da faixa dos 40%
• O autor da resposta é cético quanto à interpretação de que “converge para 1/2” e, em 40 mil experimentos comparando os graus 200 e 300, o caráter real da menor raiz foi sempre preservado, reforçando a possibilidade de um limite acima de 50%

---

Configuração do problema: poucas raízes reais, mas raízes extremas tendem ao lado real

• Em polinômios aleatórios com coeficientes reais, o número de raízes reais é muito menor que o de raízes complexas
  • Se os coeficientes seguem independentemente a uniforme em (-1,1), o número de raízes reais de um polinômio de grau n é assintoticamente 2log n/π + o(1)
  • O número de raízes complexas é aproximadamente n - 2log n/π
  • Segundo o artigo citado, fórmulas assintóticas semelhantes valem também para outras distribuições de coeficientes
• Aqui, “maior raiz” e “menor raiz” significam, respectivamente, a raiz de maior valor absoluto e a raiz de menor valor absoluto
• Se há muito menos raízes reais, seria natural esperar que as raízes extremas também fossem complexas, mas os dados experimentais do autor da pergunta apontam na direção oposta

Observações de Monte Carlo e a questão em aberto

• Há três pontos principais nos dados observados
  • A probabilidade de a maior raiz ou a menor raiz ser real é maior que a probabilidade de ser complexa
  • Essa probabilidade parece diminuir para valores próximos de 1/2 à medida que n cresce
  • Foram executadas 10^5 simulações de Monte Carlo para cada valor de n
• O texto também diz que, ao tirar os coeficientes de uma normal com média 0 e desvio padrão 1 e escalá-los para (-1,1), a mesma observação e a mesma probabilidade-limite parecem se manter
• A pergunta se reduz a dois pontos
  • Por que a maior raiz e a menor raiz ficam enviesadas para o lado real
  • Se, no grau n, essa probabilidade converge para algum valor próximo de 1/2 quando n→∞
• O viés observado é expresso em termos de probabilidades condicionais da seguinte forma
  • P(L|R)=P(S|R)≈π/(4log n)
  • P(L|C)=P(S|C)≈π/(2nπ-4log n)

Atualização: prova de limite inferior e experimento adicional com n=1000

• Na publicação vinculada no Math StackExchange, prova-se que a probabilidade de a maior raiz ser real é pelo menos
  • (23-16√2)/6 ≈ 6.2%
• A atualização de 11 de maio de 2024 acrescenta resultados de quase 60 mil experimentos para polinômios de grau n=1000
  • Os resultados são consistentes com o gráfico observado para n≤125
  • O texto afirma que, à medida que o número de ensaios cresce, a probabilidade de a maior raiz ser real mostra tendência de queda, sugerindo possível convergência para 1/2

Resposta: ligação com a menor raiz de uma série de potências aleatória

• Com base no Math StackExchange e no post Thurston, Selberg, and random polynomials Part II, argumenta-se que, para distribuições adequadas dos coeficientes, o limite em grau finito leva ao problema da menor raiz de uma série de potências aleatória
  • P(x)=a₀+a₁x+a₂x²+…
  • O limite da probabilidade de a menor raiz ser real no caso finito torna-se a probabilidade de a menor raiz dessa série de potências aleatória ser real
• Afirma-se que, usando o teorema de Rouché, é fácil mostrar que essa probabilidade é maior que 0 e menor que 1
• O valor-limite pode variar conforme a distribuição dos coeficientes aᵢ
  • Se aᵢ seguem a uniforme em [-1,1], fica em cerca de 51%
  • Se seguem uma gaussiana de média 0 e variância 1, fica em cerca de 52%
  • Se a gaussiana tem variância 1/k!, fica em cerca de 62%
  • Se seguem a distribuição discreta em 1 e -1, parece ficar no começo da faixa dos 40%
• Portanto, mais do que dizer que “é maior que 50% em todos os casos razoáveis”, o correto é que dependendo do modelo pode ficar acima ou abaixo de 50%

Por que raízes reais ainda podem dominar as raízes extremas

• Em muitos modelos, as raízes tendem a se concentrar perto do disco unitário, com distribuição angular aproximando-se da uniforme, e em escalas muito locais aparece repulsão entre raízes
• Raízes complexas podem se espalhar ao longo da circunferência do disco unitário, mas a repulsão entre raízes reais tenderia a “forçá-las” a ficarem menores ou maiores
• Nessa perspectiva, mesmo que o número total de raízes reais seja apenas da ordem de logaritmo, ainda pode haver raízes reais suficientes para ocupar a posição de menor ou maior raiz
• O problema em aberto passa a ser como transformar um valor fácil de obter por Monte Carlo em uma estimativa numérica rigorosa

Ideia para obter estimativas rigorosas com o teorema de Rouché

• Assumindo aᵢ∈[-1,1] uniformemente, propõe-se dividir o espaço de coeficientes de polinômios de baixo grau em pequenas caixas
  • Como exemplo, menciona-se dividir cada aᵢ em 1000 intervalos de mesmo comprimento para polinômios de grau menor que 100
  • A resposta afirma que isso leva, no fim, a 100^1000 polinômios
• Sob a ótica de Monte Carlo, espera-se que a maioria dos polinômios caia em um de dois conjuntos
  • Aqueles em que a menor raiz é real e tem valor absoluto menor que 9/10
  • Aqueles em que as duas menores raízes formam um par complexo conjugado e têm valor absoluto menor que 9/10
• Em ambos os casos, se na fronteira de um disco contendo apenas essas raízes tivermos |P| > (9/10)^100, o teorema de Rouché garante que a natureza da menor raiz se preserve
• O método não tem obstáculo teórico, mas o custo computacional real pode ser grande demais, talvez exigindo cálculos com graus abaixo de 10 e cerca de 10^10 polinômios, ou então uma partição mais eficiente

Contestação da interpretação de convergência para 1/2 e cálculos adicionais

• O autor da resposta considera pouco convincente a interpretação do autor da pergunta de que “provavelmente converge para 1/2”, citando como objeção o fato de outros modelos naturais e simétricos não convergirem para 1/2
• Ao gerar 1000 polinômios aleatórios de grau 500 e verificar o valor absoluto da menor raiz, em todos os casos ele foi menor que 0.91
  • Ao estender isso para a série de potências aleatória, afirma-se que, dentro do disco |z|<0.91, a variação da função fica na escala de 10^-20 ou menor
  • Para que o teorema de Rouché deixasse de se aplicar, seria preciso que a menor raiz, ou um par complexo conjugado, estivesse extremamente perto da próxima raiz em termos de valor absoluto
• Para estimar melhor a taxa de convergência, propõe-se o seguinte experimento
  • Calcular 50.000 polinômios aleatórios de grau 500
  • Calcular 50.000 polinômios estendidos ao grau 1000 mantendo os mesmos termos iniciais
  • Verificar, em ambos os graus, se a menor raiz é real e com que frequência essa natureza muda ao aumentar o grau
• A intuição do autor da resposta é que, ao passar do grau 500 para 1000, os casos que mudam serão muito raros
  • Se os dois valores ficarem perto de 51% e a taxa de mudança for muito menor que 1%, isso pode ser visto como sinal de que o limite é estritamente maior que 50%

Experimento de comparação real: graus 200 e 300

• Como os cálculos para graus maiores demoravam, a comparação real foi feita com os graus 200 e 300
• Resultado de 40.000 polinômios:
  • Entre os polinômios de grau 200, em 20.287 casos a menor raiz era real
  • Ao estender esses mesmos polinômios ao grau 300, essa propriedade foi preservada em todos os casos
• Isso sugere que os valores esperados para os graus 200, 300 e 1000 já podem estar muito próximos do valor esperado no grau infinito
• O valor calculado é de cerca de 50,7%, e o cálculo do autor da pergunta também fica em torno de 50,7%, o que é apresentado como evidência de que o limite é maior que 1/2
• O autor da resposta afirma estar convencido de que o limite é maior que 50% e acrescenta que dará 100 dólares a quem provar que ele está errado

Estabilização rápida da série de potências truncada

• Como evidência adicional, verificou-se para a série de potências aleatória P(x)=Σaᵢxᶦ em que ponto o truncamento Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦ, para k de 1 até 1000, estabiliza a classificação da menor raiz como real ou complexa
• Em 200 polinômios aleatórios, o ponto de início da estabilização foi quase sempre muito pequeno
  • Em muitos casos, já estabilizava em k=1 ou k=2
  • O maior valor listado foi 22
• Isso também reforça a avaliação de que experimentos em grau finito podem se aproximar rapidamente do limite em grau infinito

[GN⁺]

Comentários do Hacker News

• É realmente fascinante que esteja entre o nível do acaso e 1/φ
  No post do MSE linkado, agora foi provado que a probabilidade de a maior raiz ser real é de pelo menos 6,2%, e até mais de 1/10 de 1/φ. Vejo a conexão entre os números primos e φ como algo natural. Primos não são aleatórios, como muita gente entende equivocadamente; eles surgem recursivamente a partir dos primos anteriores, pois são as “lacunas” não ocupadas pelos múltiplos dos primos anteriores. Então é razoável esperar que algum padrão natural de crescimento, como e ou φ, apareça. É um padrão de grandezas muito fundamentais, como verdade e beleza

  • A forma como e aparece nos primos pode ser vista na média do tamanho de conjuntos que reúnem apenas lacunas crescentes, por exemplo (2,3,5)(7,11)(13,17)..., ou apenas lacunas que não diminuem, como (2,3,5,7,11)(13,17)(19,23,29)...
    É menos uma propriedade dos próprios primos e mais uma propriedade do crescimento, e se ajusta ainda melhor em conjuntos de números aleatórios
  • Lindo. φ parece sempre aparecer quando alguma coisa fica densamente concentrada

• Duas perguntas me vieram imediatamente à cabeça

  1. O que significa aleatório aqui? Parece que fizeram experimentos numéricos; soa parecido com usar coeficientes inteiros uniformes em um conjunto limitado, e nesse caso o resultado pode mudar bastante
  2. Fico curioso se eles olharam para graus ímpares, em que sempre há garantia de uma raiz real, para graus pares, ou para ambos
     Não estou tentando diminuir este texto interessante
  • Como usado na definição, a distribuição é de coeficientes uniformes independentes em (-1,1)
  • Exato. A formulação original do problema é paradoxal. Não dá para amostrar uniformemente de um conjunto infinito. Imagino que o texto original tenha usado números de ponto flutuante aleatórios e limitados
    Mas a parte importante da pergunta pode ser feita para qualquer distribuição possível sobre os reais

• Se você quiser fazer experimentos numéricos com isso, o R tem suporte embutido para esse tipo de coisa
  plot(polyroot(runif(101,-1,1)))
  Isso mostra uma visualização das raízes de um polinômio de grau 100

• “Suponha que os coeficientes sejam independentes e uniformemente aleatórios em (−1,1). Caso contrário, podemos escalar cada coeficiente para (−1,1) dividindo cada um pelo coeficiente de maior valor absoluto.”
  Não sei se minha intuição está certa, mas, ao dividir e escalar assim, a distribuição dos coeficientes restantes, exceto o maior, não se torna uma distribuição não uniforme?

  • O ponto importante é que multiplicar um polinômio por uma constante não muda suas raízes
  • Sim, mas não dá para escolher aleatoriamente um número real com distribuição uniforme. Em algum lugar é preciso fazer uma concessão

• Para polinômios de grau 5 ou maior não existe fórmula; então como diferenciar uma raiz real de real + epsilon*i?

  • Usando o teorema de Budan https://en.wikipedia.org/wiki/Budan%27s_theorem, é possível certificar se há exatamente uma raiz real no intervalo (r - ɛ, r + ɛ], ou exatamente zero
    Se a estimativa r estiver a uma distância de no máximo ɛ de alguma raiz, dá para distinguir raízes reais de complexas mesmo sem o valor exato. Claro que há casos em que o teorema de Budan não dá resposta. Por exemplo, ele falha de forma mais óbvia se houver duas ou mais raízes nesse intervalo
  • O fato de não existir uma fórmula exata para raízes de polinômios de grau alto não impede a possibilidade de descobrir a distribuição das raízes desses polinômios. A pergunta é sobre uma distribuição, não sobre um polinômio específico, então o teorema de Abel não é uma barreira
    Por exemplo, se considerarmos o polinômio a_n x^n + ... + a_0, em que os coeficientes a_i são variáveis aleatórias Bernoulli independentes e identicamente distribuídas, podemos dizer com confiança que, mesmo para grau n grande (>4), esse polinômio tem probabilidade 1/2 de ter uma raiz real em x = 0. Na pergunta linkada, funciona uma lógica parecida, porém mais sofisticada
  • Se for um polinômio com coeficientes inteiros, é possível limitar superiormente a maior e a menor raiz por alguma potência do máximo dos valores absolutos dos coeficientes. Imagino que exista uma cota parecida também para a menor parte imaginária que uma raiz pode ter
    Se os coeficientes forem reais, uma fórmula nem ajuda. Há o mesmo problema de decidir se um número é igual a 0. Por exemplo, na fórmula quadrática, o discriminante pode ser -epsilon; se epsilon for 0, não há raiz imaginária, e se não for 0, há raiz imaginária
  • Parece que aqui daria para usar a derivada. Se x+iy e x-iy são raízes complexas e y é muito pequeno, então a derivada em x também deve ser pequena. Se y=0, é uma raiz dupla, então p'(x)=0
    Portanto, se p'(x) estiver suficientemente longe de 0, dá para considerá-la uma raiz real simples. E, com coeficientes aleatórios, raízes duplas praticamente não devem ocorrer
  • A estimativa se baseia em inferência, não em cálculo numérico. Por exemplo, polinômios de valor real são estáveis sob conjugação complexa, então, se houver uma raiz complexa, seu conjugado também necessariamente será raiz. Portanto, em um polinômio com três raízes distintas, uma delas necessariamente deve ser real. Com raciocínios desse tipo, é possível descobrir se uma raiz é puramente real ou complexa
    Quanto às fórmulas, não existe fórmula geral para grau 5 ou maior. Fórmulas gerais existem apenas para polinômios de grau 4 ou menor
    Claro que pode haver fórmulas específicas para certos tipos de polinômios de grau alto. Mas para polinômios gerais de grau 5 ou maior não há, e isso já foi demonstrado classicamente

• Fugindo um pouco do assunto, mas sempre gosto de ler textos de matemática como esse
  Eu gostava muito de matemática na universidade e, embora tenha feito Ciência da Computação, o entusiasmo dos professores sempre me estimulou. Quero aprender mais e me aventurar um pouco a resolver problemas com matemática. Talvez eu acabe pendendo para análise numérica
  Mas já faz 2 anos que me formei e não pratiquei muito nesse período, então acho que vou ter que reaprender bastante. Fico curioso sobre por onde seria bom começar e onde encontrar temas interessantes. Não é análise numérica, mas na graduação resolvi bastante problemas do Project Euler; existe algo parecido? Qualquer ideia é bem-vinda
  Ou será que eu deveria primeiro refazer todos os problemas dos livros-texto? ;-)

  • Para quem conhece um pouco de matemática de nível universitário e tem curiosidade, Mathematics and Its History (https://link.springer.com/book/10.1007/978-1-4419-6053-5) é um livro muito divertido
    Proofs from THE BOOK (https://link.springer.com/book/10.1007/978-3-662-57265-8) também acho que dá para aproveitar bastante
  • É um pouco diferente da pergunta, mas, se você gosta de matemática, The Math Sorcerer é difícil deixar passar: https://www.youtube.com/@TheMathSorcerer
  • Fui para a universidade estudar matemática 6 ou 7 anos depois de sair da escola; minhas notas em matemática tinham sido boas, mas eu tinha esquecido quase tudo. Não houve método melhor do que refazer todos os exercícios que eu já tinha resolvido antes, e descobri que, na prática, eu não tinha esquecido completamente. Boa sorte

• Não sei se é por eu não conhecer esse tipo de matemática
  Na minha cabeça, eu pego um polinômio “aleatório” e olho só para as duas maiores raízes. Em seguida penso em duas reflexões: uma em relação à parte de baixo/de cima da curva e outra em relação ao eixo x. Se essas duas raízes superiores não forem degeneradas, entre as quatro combinações de curvas obtidas pelas reflexões, duas parecem ter uma maior raiz real e duas uma maior raiz imaginária. Se forem degeneradas, a maior raiz é real
  Então eu concluiria que (1) há mais casos em que a maior raiz é real do que casos em que é imaginária, e (2) como há infinitamente mais curvas com maior raiz não degenerada do que casos degenerados, essa “vantagem” é pequena a ponto de desaparecer
  Dá para ver que eu praticamente não conheço a terminologia. Talvez eu esteja deixando passar que a uniformidade dos coeficientes aleatórios não leva a uma distribuição uniforme no espaço. Ou talvez minhas reflexões quebrem uma das condições, por exemplo a de coeficientes reais. Ou talvez eu esteja simplesmente errado

  • Não entendi bem o que você quer dizer com reflexão. Refletir o gráfico de um polinômio p(x) em relação ao eixo x significa trocar p(x) por p(-x). O que quer dizer “reflexão em relação à parte de baixo/de cima da curva”? É uma reflexão em relação ao eixo y? Então isso significaria trocar p(x) por -p(x)
  • O que significa uma reflexão em relação à parte de baixo/de cima da curva?
    Por combinação, talvez você queira dizer tomar (polinômio + polinômio refletido)/2?

• Não entendo muito por que parece contraintuitivo que os reais sejam mais prováveis
  Se, em vez de coeficientes reais uniformemente aleatórios em um intervalo, escolhermos raízes uniformemente aleatórias em um disco centrado na origem no plano complexo e construirmos um polinômio, a chance de obter um polinômio de coeficientes reais é praticamente nula. Por outro lado, se as raízes aleatórias forem reais, o polinômio necessariamente tem coeficientes reais. Portanto, a priori, nenhuma das respostas é surpreendente, e para mim o lado em que os reais parecem mais plausíveis é um pouco mais intuitivo. Claro que isso não é inevitável

  • Um polinômio de grau n tem n raízes, incluindo raízes reais e complexas. Em um polinômio aleatório, aproximadamente log(n) delas são reais, e n - log(n) são não reais
    Conforme n cresce, log(n) é muito pequeno em comparação com n, então é muito surpreendente que, em mais da metade dos casos, a maior raiz seja uma dessas pouquíssimas raízes reais

• Seguindo os links daqui, uma das respostas de Boris Hanin parece ter resolvido uma pergunta que eu tinha havia algum tempo

• Aliás, fico curioso se “polinômio aleatório” aqui significa com coeficientes reais ou coeficientes complexos

  • Se permitirmos coeficientes complexos, a distribuição terá simetria rotacional no plano complexo. Portanto, a chance de uma raiz estar no eixo real não é maior do que a chance de estar em qualquer outra reta que passe pela origem. Polinômios cuja maior raiz é real praticamente desapareceriam
  • A pergunta apresentada explicita que são coeficientes reais. Experimentalmente, parece que escolheram coeficientes aleatórios no intervalo [-1, 1] com distribuição uniforme e também testaram algum tipo de distribuição normal escalada
  • Na primeira linha da pergunta está escrito “real”