Large $(k;r,s;n,q)$-sets in Projective Spaces

Abstract

A $(k;r,s;n,q)$-set (short: $(r,s)$-set) of $\mathrm{PG}(n,q)$ is a set of points $X$ with $|X|=k$ such that no $s$-space contains more than $r$ points of $X$. We investigate the asymptotic size of $(r,s)$-sets for $n$ fixed and $q\to \infty$. In particular, we show the existence of $(3,2)$-sets of size $(1+o(1))q^{3/2}$ for $n=6$, $(4,2)$-sets of size $(1+o(1))q^{\frac{n-1}{2}}$, and $(9,2)$-sets of size $(1+o(1))q^2$ for $n=4$. We also generalize a bound by Rao from 1947 and show that an $(r,s)$-set has size at most $O(q^{\frac{n-e+1}{e}})$ if there exist integers $d,e\ge 2$ such that $s=d(e-1)$ and $r=de-1$.

10 pages, removed the part on random polynomials which duplicated recent work by Sudakov and Tomon