Shifted varieties and discrete neighborhoods around varieties

Abstract

In the area of symbolic-numerical computation within computer algebra, an interesting question is how “close” a random input is to the “critical” ones. Examples are the singular matrices in linear algebra or the polynomials with multiple roots for Newton's root-finding method. Bounds, sometimes very precise, are known for the volumes over or of such neighborhoods of the varieties of “critical” inputs; see the references below. This paper deals with the discrete version of this question: over a finite field, how many points lie in a certain type of neighborhood around a given variety? A trivial upper bound on this number is given by the product (size of the variety) ⋅ (size of a neighborhood of a point). It turns out that this bound is usually asymptotically tight, in particular for the singular matrices, polynomials with multiple roots, and pairs of non-coprime polynomials. The interesting question then is: for which varieties is this bound not asymptotically tight? We show that these are precisely those that admit a shift, that is, where one absolutely irreducible component of maximal dimension is a shift (translation by a fixed nonzero point) of another such component. Furthermore, the shift-invariant absolutely irreducible varieties are characterized as being cylinders over some base variety. Computationally, determining whether a given variety is shift-invariant turns out to be intractable, namely NP-hard even in simple cases.