Raízes inteiras de um polinômio

10

Que algoritmo podemos usar para encontrar todas as raízes inteiras de um polinômio com coeficientes inteiros?f(x)

Observo que Sage pode encontrar as raízes dentro de alguns segundos, mesmo quando todos os coeficientes de são muito grandes. Como é capaz de fazer isso?f(x)

ds.algorithms na.numerical-analysis user12290
fonte
11
Você está procurando um algoritmo para retornar uma raiz inteira de um determinado polinômio? Se sim, isso é indecidível e a questão está fora de tópico aqui. Você pode perguntar sobre Ciência da Computação, que tem um escopo mais amplo.
Kaveh
7
Aguente. Por que ser indecidível torna a pergunta fora de tópico? Esta é uma pergunta legítima em nível de pesquisa.
21413 Jefferson
2
Então, como Sage faz isso? Ser indecidível - mesmo sendo conhecido como indecidível - não torna o problema teoricamente desinteressante. Cientistas teóricos da computação resolvem problemas indecidíveis o tempo todo - veja, por exemplo, todas as verificações auxiliadas por computador.
Jeffε
11
Kaveh, o que você está dizendo não é verdade. O que é indecidível é a resolubilidade das equações diofantinas com muitas variáveis ​​(para que existam muitas soluções reais de maneira infinita e uma esteja procurando por uma inteira / racional). Mas essa pergunta é sobre um polinômio uni-variável , que é obviamente decidível (se for de grau , existem até raízes e pode-se verificar qual é um número inteiro). f ( x ) d df(x)f(x)dd
Mahdi Cheraghchi
11
@Pratik Você não precisa das bases de Gröbner no caso univariado.
Yuval Filmus

Respostas:

10

Supondo que os coeficientes de sejam inteiros ou racionais e que você deseja raízes inteiras, a abordagem mais simples é usar o teorema da raiz inteira ou racional. Consulte http://en.wikipedia.org/wiki/Rational_root_theorem Conforme observado pelo DW, isso pode ser problemático se o coeficiente constante for difícil de ser fatorado (consulte também /math/123018/polynomial- e raízes inteiras )f

De qualquer forma, a documentação do Sage explica claramente como eles estão fazendo a pesquisa raiz: "O próximo método, que é usado se K é um domínio integral, é tentar fatorar o polinômio. Se isso der certo, para cada grau um fator a * x + b, adicionamos -b / a como raiz (desde que esse quociente esteja realmente no anel desejado) ". Consulte http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html .

Portanto, sua pergunta se torna: como eles fatoram polinômios com coeficientes inteiros? Aparentemente, Sage está chamando a NTL para fazer isso (consulte http://www.shoup.net/ntl/doc/ZZXFactoring.txt para obter detalhes sobre NTL).

Se você quiser um método assintoticamente eficiente, consulte o método de Lenstra, Lenstra e Lovasz ( https://openaccess.leidenuniv.nl/handle/1887/3810 ).

minar
fonte
11
Obrigado pela dica útil! Fascinante. Você pode estar disposto a editar sua resposta para elaborar como transformar isso em um algoritmo e qual é o tempo de execução? O pior caso de tempo de execução é exponencial (porque pode levar um tempo subexponencial para fatorar e, em seguida, pode haver exponencialmente muitos divisores do coeficiente à esquerda e à direita)? Em caso afirmativo, existem algoritmos melhores ou é o melhor que se pode fazer? Além disso, essa abordagem não encontra apenas as raízes racionais, mas não as irracionais?
DW
Relendo a questão e vendo que você a interpreta de maneira diferente, não tenho mais certeza, mas pareceu claro para mim e para alguns comentaristas que a pergunta é sobre raízes inteiras. Você não lê dessa maneira?
minar 18/07/2013
@ Minar, você está certo. Agora que reli a pergunta, parece que sim. Eu devo ter lido a pergunta muito rapidamente. (I inicialmente interpretado a pergunta como implicando que queremos que todas as raízes de um polinômio com coeficientes inteiros, mas no re-ler a pergunta, que parece ser uma má interpretação.)
DW
2
Para um método assintoticamente e praticamente eficiente, o algoritmo mais conhecido é de van Hoeij (veja aqui ). Na verdade, NTL parece estar usando.
197 Bruno