Revista de la
Unión Matemática Argentina
Univariate rational sums of squares
Teresa Krick, Bernard Mourrain, and Agnes Szanto
Volume 64, no. 2 (2022), pp. 215–237    

https://doi.org/10.33044/revuma.2904

Download PDF

Abstract

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.

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. E. Landau, Über die Darstellung definiter Funktionen durch Quadrate, Math. Ann. 62 (1906), no. 2, 272–285. MR 1511376.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no. 3, 969–984. MR 1254128.
  16. C. Scheiderer, Sums of squares of polynomials with rational coefficients, J. Eur. Math. Soc. (JEMS) 18 (2016), no. 7, 1495–1513. MR 3506605.
  17. J. von zur Gathen and J. Gerhard, Modern Computer Algebra, third edition, Cambridge University Press, Cambridge, 2013. MR 3087522.