  In the area of symbolic-numerical computation within computer algebra, an
interesting question is how "close" a random input is to the "critical" ones,
like 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 R or C of such neighborhoods of the varieties of
"critical" inputs.
  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 (size of the variety) x (size
of a neighborhood of a point). It turns out that this bound is usually
asymptotically tight, including for the singular matrices, polynomials with
multiple roots, and pairs of non-coprime polynomials.
  The interesting question then is: for which varieties does this bound not
hold? We show that these are precisely those that admit a shift, that is, where
one absolutely irreducible component 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.
