Univariate rational sums of squares
DOI:
https://doi.org/10.33044/revuma.2904Abstract
Given rational univariate polynomials $f$ and $g$ such that $\gcd (f,g)$ and $f/\gcd(f,g)$ are relatively prime, we show that $g$ is non-negative at all the real roots of $f$ if and only if $g$ is a sum of squares of rational polynomials modulo $f$. We complete our study by exhibiting an algorithm that produces a certificate that a polynomial $g$ is non-negative at the real roots of a non-zero polynomial $f$ when the above assumption is satisfied.
Downloads
References
S. Basu, R. Pollack and M.-F. Roy, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, 10, Springer-Verlag, Berlin, 2003. MR 1998147.
S. Chevillard, J. Harrison, M. Joldeş and Ch. Lauter, Efficient and accurate computation of upper bounds of approximation errors, Theoret. Comput. Sci. 412 (2011), no. 16, 1523–1543. MR 2798728.
F. Guo, E. L. Kaltofen and L. Zhi, Certificates of impossibility of Hilbert–Artin representations of a given degree for definite polynomials and functions, in ISSAC 2012—Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, 195–202, ACM, New York, 2012. MR 3206304.
E. Kaltofen, B. Li, Z. Yang and L. Zhi, Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars, in ISSAC '08—Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation, 155–163, ACM, New York, 2008. MR 2500392.
E. L. Kaltofen, B. Li, Z. Yang and L. Zhi, Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symbolic Comput. 47 (2012), no. 1, 1–15. MR 2854844.
E. Landau, Über die Darstellung definiter Funktionen durch Quadrate, Math. Ann. 62 (1906), no. 2, 272–285. MR 1511376.
V. Magron and M. Safey El Din, On exact Reznick, Hilbert–Artin and Putinar's representations, J. Symbolic Comput. 107 (2021), 221–250. MR 4244719.
V. Magron, M. Safey El Din and M. Schweighofer, Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials, J. Symbolic Comput. 93 (2019), 200–220. MR 3913572.
V. Magron, M. Safey El Din, M. Schweighofer and T. H. Vu, Exact SOHS decompositions of trigonometric univariate polynomials with Gaussian coefficients, in ISSAC '22—Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, 325–332, ACM, New York, 2022. https://doi.org/10.1145/3476446.3535480.
V. Magron, M. Safey El Din and T.-H. Vu, Sum of squares decompositions of polynomials over their gradient ideals with rational coefficients, https://arxiv.org/abs/2107.11825 [cs.SC], 2021.
V. Magron, H. Seidler and T. de Wolff, Exact optimization via sums of nonnegative circuits and arithmetic-geometric-mean-exponentials, in ISSAC'19—Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation, 291–298, ACM, New York, 2019. MR 4007472.
P. A. Parrilo, An explicit construction of distinguished representations of polynomials nonnegative over finite sets, IfA Technical Report AUT02-02, https://www.mit.edu/ parrilo/pubs/files/aut02-02.pdf, 2002.
H. Peyrl and P. A. Parrilo, Computing sum of squares decompositions with rational coefficients, Theoret. Comput. Sci. 409 (2008), no. 2, 269–281. MR 2474341.
Y. Pourchet, Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques, Acta Arith. 19 (1971), 89–104. MR 0289442.
M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no. 3, 969–984. MR 1254128.
C. Scheiderer, Sums of squares of polynomials with rational coefficients, J. Eur. Math. Soc. (JEMS) 18 (2016), no. 7, 1495–1513. MR 3506605.
J. von zur Gathen and J. Gerhard, Modern Computer Algebra, third edition, Cambridge University Press, Cambridge, 2013. MR 3087522.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Teresa Krick, Bernard Mourrain, Agnes Szanto
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.
