2012/06/30 by Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran +2
Computer Science · Engineering · Mathematics · #Arithmetic #Bivariate analysis #Difference polynomials #Discrete mathematics #Factoring #Lacunary function #Mathematics #Mathematics and Applications #Orthogonal polynomials #Polynomial and algebraic computation #Pure mathematics #Statistics #cs.CC #cs.SC #graph theory and CDMA systems
paper · pdf · doi:10.1145/2465506.2465932
published as Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (ISSAC'13), pp 141-148, ACM, 2013 · 25 pages, 1 appendix
arxiv created 2013/05/14 · openalex publication_date 2013/06/25 · arxiv updated 2013/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap theorem which allows to test whether P(X)=∑kj=1 αjXαj(1+X)βjis identically zero in polynomial time. The algorithm we obtain is more elementary than the one by Kaltofen and Koiran (ISSAC'05) since it relies on the valuation of polynomials of the previous form instead of the height of the coefficients. As a result, it can be used to find some linear factors of bivariate lacunary polynomials over a field of large finite characteristic in probabilistic polynomial time.