2025/07/10 by Jeck Lim, Lim, Jeck, Jiaxi Nie +3 · 1 citation
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2507.07594
openalex publication_date 2025/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the affine space \mathbbFqn over the finite field of order q, a point set S is said to be (d,k,r)-evasive if the intersection between S and any variety, of dimension k and degree at most d, has cardinality less than r. As q tends to infinity, the size of a (d,k,r)-evasive set in \mathbbFqn is at most O(qn-k) by a simple averaging argument. We exhibit the existence of such evasive sets of sizes at least Ω(qn-k) for much smaller values of r than previously known constructions, and establish an enumerative upper bound 2^O(qn-k) for the total number of such evasive sets. The existence result is based on our study of twisted varieties. In the projective space ℙn over an algebraically closed field, a variety V is said to be d-twisted if the intersection between V and any variety, of dimension n - dim(V) and degree at most d, has dimension zero. We prove an upper bound on the smallest possible degree of twisted varieties which is best possible in a mild sense. The enumeration result includes a new technique for the container method which we believe is of independent interest. To illustrate the potential of this technique, we give a simpler proof of a result by Chen--Liu--Nie--Zeng that characterizes the maximum size of a collinear-triple-free subset in a random sampling of \mathbbFq2 up to polylogarithmic factors.