A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough dimension.

Formally, for parameters $k$ and $\epsilon > 0$, a $(k,c)$-subspace evasive set $S \in \mathbb{F}_q^n$ is such that $|S| > |\mathbb{F}_q^{n}|^{1-\epsilon}$ and $|S \cap H| < c$ for all $k$-dimensional affine subspaces $H \in \mathbb{F}_q^n$.

The goal is to make the intersection $c$ as small as possible.

It is claimed (as trivial in most references) that a random set $S \in \mathbb{F}_q^n$ of size $|\mathbb{F}_q^{n}|^{1-\epsilon}$ has (whp) intersection $c = O(k/\epsilon)$.

Is there a way of showing this? It is supposed to be a simple application of a probabilistic method, but I am stuck and clueless.


Here's a quick calculation.

For a fixed affine subspace $H$ of dimension $k$, the probability that a random point falls in $H$ is $1/q^{n-k}$. The probability that at least $c$ points in $S$ fall in $H$ is at most: $${q^{(1-\epsilon)n} \choose c} \cdot \frac{1}{q^{(n-k)c}}\leq \frac{q^{(n-\epsilon n) c}}{q^{(n-k)c}} = \frac{1}{q^{(\epsilon n -k)c}}$$ A trivial bound on the number of subspaces of dimension $k$ is $q^{n(k+1)} < q^{2kn}$. So, by the union bound, the probability that there exists a subspace $H$ containing at least $c$ points of $S$ is at most: $$q^{2nk} \cdot \frac{1}{q^{(\epsilon n -k)c}} < 1$$ if $c = 4k/\epsilon$ and $k<\epsilon n/3$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.