Faster -adic feasibility for certain multivariate sparse polynomials

详细信息	查看全文 | 推荐本文 |

• 作者：Martí ; n Avendañ ; o^a ; ^{mavendar@yahoo.com.ar} ; Ashraf Ibrahim^b ; ^{ibrahim@aero.tamu.edu} ; J. Maurice Rojas^a ; ^{rojas@math.tamu.edu} ; Korben Rusek^a ; ^{korben.rusek@gmail.com}
• 关键词：Feasibility ; p-adic rational ; Fewnomial ; Complexity ; Short certficate ; -completeness ; Sparse ; Trinomial ; Multivariate
• 刊名：Journal of Symbolic Computation
• 出版年：2012
• 期刊代码：140_07477171
• 类别：cp
• 出版时间：April, 2012
• 卷：47
• 期：4
• 页码：454-479
• 文件大小：456 K

摘要

We present algorithms revealing new families of polynomials admitting sub-exponential detection of -adic rational roots, relative to the sparse encoding. For instance, we prove -completeness for the case of honest -variate -nomials and, for certain special cases with exceeding the Newton polytope volume, constant-time complexity. Furthermore, using the theory of linear forms in -adic logarithms, we prove that the case of trinomials in one variable can be done in . The best previous complexity upper bounds for all these problems were or worse. Finally, we prove that detecting -adic rational roots for sparse polynomials in one variable is -hard with respect to randomized reductions. The last proof makes use of an efficient construction of primes in certain arithmetic progressions. The smallest where detecting -adic rational roots for -variate sparse polynomials is -hard appears to have been unknown.