2023/08/07 by Nahshon, Ido, Shpilka, Amir · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.2308.03885
We prove that for polynomials f, g, h ∈ ℤ[x] satisfying f = gh and f(0) ≠ 0, the ℓ2-norm of the cofactor h is bounded by ‖h‖2 ≤ ‖f‖1 ⋅( \widetildeO(‖g‖03 \fracdeg (f)2√deg (g)))‖g‖0 - 1, where ‖g‖0 is the number of nonzero coefficients of g (its sparsity). We also obtain similar results for polynomials over ℂ. This result significantly improves upon previously known exponential bounds (in deg (f)) for general polynomials. It further implies that, under exact division, the polynomial division algorithm runs in quasi-linear time with respect to the input size and the number of terms in the quotient h. This resolves a long-standing open problem concerning the exact divisibility of sparse polynomials. In particular, our result demonstrates a quadratic separation between the runtime (and representation size) of exact and non-exact divisibility by sparse polynomials. Notably, prior to our work, it was not even known whether the representation size of the quotient polynomial could be bounded by a sub-quadratic function of its number of terms, specifically of deg (f).