New Bounds on Quotient Polynomials with Applications to Exact Division and Divisibility Testing of Sparse Polynomials

We prove that for monic polynomials <Formula format="inline"><TexMath><?TeX f, g ∈ C[x]?></TexMath><AltText>Math 1</AltText><File name="issac24-9-inline1" type="svg"/></Formula> such that g divides f, the ℓ2-norm of the quotient f/g is bounded by <Formula format="inline"><TexMath><?TeX f ₁ · Õ( g ₀³ ²f)^ g ₀ - 1?></TexMath><AltText>Math 2</AltText><File name="issac24-9-inline2" type="svg"/></Formula>, improving upon the previously known exponential (in <Formula format="inline"><TexMath><?TeX (f)?></TexMath><AltText>Math 3</AltText><File name="issac24-9-inline3" type="svg"/></Formula>) bounds for general polynomials. This result implies that the trivial long division algorithm runs in quasi-linear time relative to the input size and number of terms of the quotient, thus solving a long-standing problem. We also bound the number of terms of f/g in some special cases. When <Formula format="inline"><TexMath><?TeX f, g ∈ Z[x]?></TexMath><AltText>Math 4</AltText><File name="issac24-9-inline4" type="svg"/></Formula> and g is a cyclotomic-free (i.e., it has no cyclotomic factors) trinomial, we prove that <Formula format="inline"><TexMath><?TeX f/g ₀≤ O( f ₀ size(f )² · log ⁶ g)?></TexMath><AltText>Math 5</AltText><File name="issac24-9-inline5" type="svg"/></Formula>. When g is a binomial with g(± 1) ≠ 0, we prove that the sparsity is at most O(‖f‖0(log ‖f‖0 + log ‖f‖∞)). Both upper bounds are polynomial in the input-size. Leveraging these results, we provide a polynomial-time algorithm for deciding whether a cyclotomic-free trinomial divides a sparse polynomial over the integers.