<p>Here's a quick calculation.</p>

<p>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)} &lt; 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}} &lt; 1$$
if $c = 4k/\epsilon$ and $k&lt;\epsilon n/3$.</p>

CC BY-SA 3.0
2014-06-26T06:22:44.187Z
2016-06-09T05:23:53.340Z
2016-06-09T05:23:53.340Z
arnab
<p>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.</p>

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

<p>The goal is to make the intersection $c$ as small as possible.</p>

<p>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)$.</p>

<p>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.</p>

<pr.probability><linear-algebra><coding-theory>
Subspace-evasive set performance in the random case
BharatRam
# Subspace-evasive set performance in the random case

(Asked by: username_0 on 2014-06-26)

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.

**Tags:** pr.probability, linear-algebra, coding-theory


---

## 1 answers

### Answer by username_1 on 2014-06-26. Score: 3 | Accepted answer

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$.


---

