Joachim von zur Gathen
University of Bonn
For an affine variety X defined over a finite prime field F_p and some integer h, we consider the discrete h-neighborhood of the set of F_p-rational points, consisting of those points over F_p whose distance from X is not more than h, for a natural notion of "distance." There is a natural upper bound on its size. We address the question whether the neighborhood's size is close to its upper bound.
The central notion for understanding this question turns out to be the shift of a variety, which is the translation by a nonzero constant vector of the coordinates. If no absolutely irreducible component with maximal dimension of X is a shift of another component, then the answer to the question is "yes." For the opposite case, we exhibit examples where the answer is "no". When X is absolutely irreducible, the condition on shifts turns out to be necessary and sufficient. Computationally, testing the condition is coNP-complete under randomized reductions, already for simple cases.
This is joint work with Guillermo Matera.
200 University Avenue West
Waterloo, ON N2L 3G1