Randomly piercing algebraic sets

Abstract

We show, for example, that if one samples \[\frac{\log p}{2\log(1+(p-1)^{-1})} \cdot n^2(1 + o_{n\to \infty}(1))\] points in ${\mathbb{F}}_p^n$ at random then asymptotically almost surely this set intersects every quadratic hypersurface. We furthermore show that this is tight in that sampling $o_{n\to \infty }(n^2)$ fewer points almost surely fails to intersect some quadratic hypersurface. Our main result is a sharp threshold for the following problem: how many points in ${\mathbb{F}}_p^n$ does one need to randomly sample to almost surely intersect every algebraic set defined by at most $s$ polynomials each of degree at most $k$? As an application we improve lower bounds in the random Szemerédi theorem in ${\mathbb{F}}_p^n$, in particular obtaining a leading constant which grows as the threshold for what is considered a `dense' set in Szemerédi's theorem shrinks.

20 pages