Characterizations of border bases

This paper presents characterizations of border bases of zero-dimensional polynomial ideals that are analogous to the known characterizations of Gröbner bases. Based on a Border Division Algorithm, a variant of the usual Division Algorithm, we characterize border bases as border prebases with one of the following equivalent properties: special generation, generation of the border form ideal, confluence of the corresponding rewrite relation, reduction of S-polynomials to zero, and lifting of syzygies. The last characterization relies on a detailed study of the relative position of the border terms and their syzygy module. In particular, a border prebases is a border basis if and only if all fundamental syzygies of neighboring border terms lift; these liftings are easy to compute.