Approximate GCD of several univariate polynomials with small degree perturbations

We consider the following computational problem: given a family of generic univariate polynomials f≔(f0,…,fs)f≔(f0,…,fs), construct an algorithm to find polynomial perturbations u≔(u0,…,us)u≔(u0,…,us) with “small” degrees such that the greater common divisor of the family of polynomials f+uf+u has a “large” degree.In this paper, we propose an algorithm which solves this problem in polynomial time under a generic condition generalizing the normal degree sequence for the case s=1s=1.

► We study the approximate gcd of several univariate polynomials. ► We propose an algorithm which computes this gcd in polynomial time. ► The algorithm is based on the gin and minimal syzygies of these polynomials.