On the Termination of the General XL Algorithm and Ordinary Multinomials

The XL algorithm is an algorithm for solving overdetermined systems of multivariate polynomial equations. It was initially introduced for quadratic equations -- however the algorithm works for polynomials of any degree and we will focus on the performance of XL for degree $\geq3$, where the optimal termination value of $D$ is still unknown. We prove that the XL algorithm terminates at a certain value of $D$ when the number of equations exceeds the number of variables by 1 or 2, and give strong evidence that this value is best possible. Our analysis involves some commutative algebra and proving that ordinary multinomials are strongly unimodal, and this result may be of independent interest.