Lune

SODA2026Top-tier venue

Evasive sets, twisted varieties, and container-clique trees

Jeck Lim, Jiaxi Nie, Ji Zeng

Abstract

In the affine space Fqn\mathbb{F}_q^n over the finite field of order qq, a point set SS is said to be (d,k,r)(d,k,r)-evasive if the intersection between SS and any variety, of dimension kk and degree at most dd, has cardinality less than rr. As qq tends to infinity, the size of a (d,k,r)(d,k,r)-evasive set in Fqn\mathbb{F}_q^n is at most O(qn−k)O(q^{n-k}) by a simple averaging argument. We exhibit the existence of such evasive sets of sizes at least Ω(qn−k)\Omega(q^{n-k}) for much smaller values of rr than previously known constructions, and establish an enumerative upper bound 2O(qn−k)2^{O(q^{n-k})} for the total number of such evasive sets. The existence result is based on our study of twisted varieties. In the projective space Pn\mathbb{P}^n over an algebraically closed field, a variety VV is said to be dd-twisted if the intersection between VV and any variety of dimension n−dim⁡(V)n-\dim(V) and degree at most dd 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 Fq2\mathbb{F}_q^2 up to polylogarithmic factors.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. A Lower Bound for the n-queens ProblemMichael Simkin, Zur LuriaSODA 2022 · 4 citations

Related papers

  1. A New Lower Bound on Hadwiger-Debrunner Numbers in the PlaneChaya Keller, Shakhar SmorodinskySODA 2020 · 4 citations
  2. Halving by a Thousand Cuts or PuncturesSariel Har-Peled, Da Wei ZhengSODA 2023
  3. Stronger bounds for weak epsilon-nets in higher dimensionsNatan RubinSTOC 2021 · 1 citation
  4. Proximity Gaps for Reed-Solomon CodesEli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty et al.FOCS 2020 · 58 citations
  5. Helly-Type Theorems for Splitting Point SetsLidor Portal, Natan RubinSODA 2026
Dusk over the sea between two cliffs drawn in fine vertical lines