Towards More Accurate Separation Bounds of Empirical Polynomials II

  • Kosaku Nagasaka
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3718)


We study the problem of bounding a polynomial which is absolutely irreducible, away from polynomials which are not absolutely irreducible. These separation bounds are useful for testing whether an empirical polynomial is absolutely irreducible or not, for the given tolerance or error bound of its coefficients. In the former paper, we studied some improvements on Kaltofen and May’s method which finds applicable separation bounds using an absolute irreducibility criterion due to Ruppert. In this paper, we study the similar improvements on the method using the criterion due to Gao and Rodrigues for sparse polynomials satisfying Newton polytope conditions, by which we are able to find more accurate separation bounds, for such bivariate polynomials. We also discuss a concept of separation bound continuations for both dense and sparse polynomials.


Frobenius Norm Block Matrice Separation Bound Index Pair Bivariate Polynomial 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Nagasaka, K.: Towards more accurate separation bounds of empirical polynomials. SIGSAM/CCA 38, 119–129 (2004)CrossRefMathSciNetGoogle Scholar
  2. 2.
    Kaltofen, E.: Effective noether irreducibility forms and applications. J. Computer and System Sciences 50, 274–295 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Nagasaka, K.: Towards certified irreducibility testing of bivariate approximate polynomials. In: Proc. ISSAC 2002, pp. 192–199 (2002)Google Scholar
  4. 4.
    Sasaki, T.: Approximate multivariate polynomial factorization based on zero-sum relations. In: Proc. ISSAC 2001, pp. 284–291 (2001)Google Scholar
  5. 5.
    Nagasaka, K.: Neighborhood irreducibility testing of multivariate polynomials. In: Proc. CASC 2003, pp. 283–292 (2003)Google Scholar
  6. 6.
    Kaltofen, E., May, J.: On approximate irreducibility of polynomials in several variables. In: Proc. ISSAC 2003, pp. 161–168 (2003)Google Scholar
  7. 7.
    Ruppert, W.M.: Reducibility of polynomials f(x,y) modulo p. J. Number Theory 77, 62–70 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Gao, S., Rodrigues, V.M.: Irreducibility of polynomials modulo p via newton polytopes. J. Number Theory 101, 32–47 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Gao, S., Kaltofen, E., May, J., Yang, Z., Zhi, L.: Approximate factorization of multivariate polynomials via differential equations. In: Proc. ISSAC 2004, pp. 167–174 (2004)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Kosaku Nagasaka
    • 1
  1. 1.Faculty of Human DevelopmentKobe UniversityJapan

Personalised recommendations