Résumé : Nous prouvons que pour les polynômes f, g, h ∈ Z[x] satisfaisant f = gh et f(0) ≠ 0, la norme ₂ du cofacteur h est bornée par align* h ₂ {g ₀ g} f ₁ (O (g ₀^{2.5²f}{g}))^{g ₀-1} \, align* où g ₀ est le nombre de coefficients non nuls de g (sa parcimonie). Nous obtenons également des résultats similaires pour les polynômes sur C. Ces bornes représentent une amélioration par rapport aux bornes présentées dans une version antérieure de conférence de cet article NS24. Ce résultat améliore considérablement les bornes exponentielles précédemment connues (en f) pour les polynômes généraux. Il implique en outre que, sous division exacte, l'algorithme de division polynomiale fonctionne en temps quasi-linéaire par rapport à la taille d'entrée et au nombre de termes dans le quotient h. Cela résout un problème ouvert de longue date concernant la divisibilité exacte des polynômes épars. En particulier, notre résultat démontre une séparation quadratique entre le temps d'exécution (et la taille de représentation) de la divisibilité exacte et non exacte par des polynômes épars. Notablement, avant notre travail, il n'était même pas connu si la taille de représentation du polynôme quotient pouvait être bornée par une fonction sous-quadratique de son nombre de termes, ou même par une fonction sous-quadratique de f.
Nahshon et al. (Jeu,) ont étudié cette question.