Pourchet proved in 1971 that every nonnegative univariate polynomial with rational coefficients is a sum of five or fewer squares. Nonetheless, there are no known algorithms for constructing such a decomposition. The sole purpose of the present paper is to present a set of algorithms that decompose a given nonnegative polynomial into a sum of six (five under some unproven conjecture or when allowing weights) squares of polynomials. Moreover, we prove that the binary complexity can be expressed polynomially in terms of classical operations of computer algebra and algorithmic number theory.
翻译:Pourchet在1971年证明,每个具有合理系数的非负非单亚化多元体,总和为5个或更少的平方。然而,没有已知的算法来构造这种分解。本文件的唯一目的是提出一套算法,将给定的非负多元体分解成6个方形(5个在某种未证实的猜想之下,或当允许加权时)。此外,我们证明,从计算机代数和算法数字理论的典型操作来看,二元复杂度可以多元地表达出来。