<p>Here's an $\Omega(\log(\frac{1}{\epsilon\cdot \delta}))$ lower bound following the discussion here with Yuval, and another one with Ross Berkowitz.
I assume for simplicity that the sampling process chooses $k$ completely random elements $v_1,\ldots,v_k$ of $F_2^n$ and outputs their span $V$.
A little extra work is needed to bound the probability that the $k$ vectors sampled are not independent, and in fact, this might be problematic when $k$ is close to $n$.
Denote $\ell\triangleq \log(1/\epsilon)$, and let $S$ be an affine subspace of co-dimension $\ell$. Let $S_0$ be the linear subspace of which $S$ is a shift.
Denote by $T\triangleq F_2^n/S_0$ the quotient space, which is a linear space of dimension $\ell$ who's elements are the cosets of $S_0$ in $F_2^n$. For each $v_i$ denote by $\bar{v}_i\in T$, the coset in which $v_i$ landed.
Denote by $T'\subset T$ the linear span of $\bar{v}_1,\ldots,\bar{v}_k$.
Assume $k\triangleq (\ell-1) + t$, we can lower bound the probability of the event $T' \subsetneq T$ by $2^{-t}$:
Condition on $\bar{v}_1,\ldots,\bar{v}_{\ell-1}$ being linearly independent - this can only decrease the probability of $T'\subsetneq T$.
Denote $T''\triangleq \mathrm{span}(\bar{v}_1,\ldots,\bar{v}_{\ell-1})$
Now, there is a probability of at least $2^{-t}$ that the rest of the $\bar{v}$'s all land in $T''$, and in such a case $T'\subsetneq T$
Now, note that $V\cap S \neq \emptyset$ is exactly equivalent to $x\in T'$ for some fixed $x\in \{0,1\}^{\ell}$ (that correspond to the what coset $S$ is of $S_0$). Furthermore, conditioned on the event $T'\subsetneq T$ $x\notin T'$ with probability at least $1/2$. Thus $V\cap S = \emptyset$ with probability at least $2^{-t}$. So we need $2^{-t}\leq \delta$ which implies $k\geq (\ell-1) + \log(1/\delta) = \log(1/\epsilon) + \log(1/\delta) -1$. </p>

CC BY-SA 3.0
2016-06-17T01:27:04.950Z
Nice argument. This seems to say that $S$ being an affine subspace does not help, right?
kodlu
CC BY-SA 3.0
2016-06-19T14:32:14.127Z
Thanks. I'm not sure I follow. It says an affine subspace is as hard to hit as any other set, and is as hard to hit by a subspace, as by a general set of pairwise independent points
relG
CC BY-SA 3.0
2016-06-16T08:08:01.257Z
2016-06-16T08:08:01.257Z
relG
<p>Let $S\subset F_2^n$ be a subset of size $\epsilon\cdot 2^n$.
Say I choose a random subspace $V$ of dimension $k$ in $F_2^n$.
I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\cap S \neq \emptyset$, with probability $\geq 1-\delta$.
As the points of $V$ are pairwise independent, one can show that $k=\log(\frac{1}{\epsilon\cdot \delta})$ suffices (See appendix C of Goldreich's "A sample of samplers").</p>

<p>I'm wondering whether smaller $k$ can suffice.
An argument for why this might be true is that a subspace should be ``better'' than a general collection of pairwise independent points, as many subsets of points in $V$ are more than pair-wise independent.</p>

CC BY-SA 3.0
2016-06-08T15:37:58.077Z
Have you tried doing the calculation for a set $S$ which is itself a subspace of codimension $\ell$? You're asking whether $k = \ell + \log (1/\delta)$ can be improved. A random subspace $V$ of codimension $n-k$ intersects $S$ if the $\ell$ defining equations of $S$ don't conflict with the $n-k$ defining equations of $V$, which leads us to believe that for some range of $\delta$ we indeed need $\ell + n-k \leq n$, that is $k \geq \ell$. Presumably $\delta$ can also be included in this kind of calculation.
Yuval Filmus
CC BY-SA 3.0
2016-06-08T17:12:52.473Z
Hi, I can get the bound $k\geq \log(1/\delta)/\ell$ from considering $S$ an \textbf{affine} subspace of co-dimension $\ell$: If $S_0$ is the linear space of co-dimension $\ell$ which $S$ is a shift, there is probability $2^{-\ell\cdot k}$ that the $k$ chosen basis vectors of $V$ are all in $S_0$, in such a case their span will not touch $S$. So we need this event to be bounded by probability $\delta$. So you get the equation $2^{-\ell\cdot k}\leq \delta$, which implies $k\geq \log(1/\delta)/\ell$
relG
CC BY-SA 3.0
2016-06-08T17:15:04.833Z
Right, an affine subspace. Otherwise there is always an intersection...
Yuval Filmus
CC BY-SA 3.0
2016-06-08T17:20:33.993Z
But indeed this was good thing to try, as I thought initially dependence on $1/\delta$ could be smaller than logarithmic
relG
<linear-algebra><sample-complexity><k-wise-independence>
How well do subspaces hit sets
relG
# How well do subspaces hit sets

(Asked by: username_0 on 2016-06-06)

Let $S\subset F\_2^n$ be a subset of size $\epsilon\cdot 2^n$.
Say I choose a random subspace $V$ of dimension $k$ in $F\_2^n$.
I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\cap S \neq \emptyset$, with probability $\geq 1-\delta$.
As the points of $V$ are pairwise independent, one can show that $k=\log(\frac{1}{\epsilon\cdot \delta})$ suffices (See appendix C of Goldreich's "A sample of samplers").

I'm wondering whether smaller $k$ can suffice.
An argument for why this might be true is that a subspace should be ``better'' than a general collection of pairwise independent points, as many subsets of points in $V$ are more than pair-wise independent.

**Tags:** linear-algebra, sample-complexity, k-wise-independence

> **Comments:**
> **username_1**: Have you tried doing the calculation for a set $S$ which is itself a subspace of codimension $\ell$? You're asking whether $k = \ell + \log (1/\delta)$ can be improved. A random subspace $V$ of codimension $n-k$ intersects $S$ if the $\ell$ defining equations of $S$ don't conflict with the $n-k$ defining equations of $V$, which leads us to believe that for some range of $\delta$ we indeed need $\ell + n-k \leq n$, that is $k \geq \ell$. Presumably $\delta$ can also be included in this kind of calculation.  
> **username_0**: Hi, I can get the bound $k\geq \log(1/\delta)/\ell$ from considering $S$ an \textbf{affine} subspace of co-dimension $\ell$: If $S_0$ is the linear space of co-dimension $\ell$ which $S$ is a shift, there is probability $2^{-\ell\cdot k}$ that the $k$ chosen basis vectors of $V$ are all in $S_0$, in such a case their span will not touch $S$. So we need this event to be bounded by probability $\delta$. So you get the equation $2^{-\ell\cdot k}\leq \delta$, which implies $k\geq \log(1/\delta)/\ell$  
> **username_1**: Right, an affine subspace. Otherwise there is always an intersection...  
> **username_0**: But indeed this was good thing to try, as I thought initially dependence on $1/\delta$ could be smaller than logarithmic  

---

## 1 answers

### Answer by username_0 on 2016-06-16. Score: 1 | Accepted answer

Here's an $\Omega(\log(\frac{1}{\epsilon\cdot \delta}))$ lower bound following the discussion here with Yuval, and another one with Ross Berkowitz.
I assume for simplicity that the sampling process chooses $k$ completely random elements $v\_1,\ldots,v\_k$ of $F\_2^n$ and outputs their span $V$.
A little extra work is needed to bound the probability that the $k$ vectors sampled are not independent, and in fact, this might be problematic when $k$ is close to $n$.
Denote $\ell\triangleq \log(1/\epsilon)$, and let $S$ be an affine subspace of co-dimension $\ell$. Let $S\_0$ be the linear subspace of which $S$ is a shift.
Denote by $T\triangleq F\_2^n/S\_0$ the quotient space, which is a linear space of dimension $\ell$ who's elements are the cosets of $S\_0$ in $F\_2^n$. For each $v\_i$ denote by $\bar{v}\_i\in T$, the coset in which $v\_i$ landed.
Denote by $T'\subset T$ the linear span of $\bar{v}\_1,\ldots,\bar{v}\_k$.
Assume $k\triangleq (\ell-1) + t$, we can lower bound the probability of the event $T' \subsetneq T$ by $2^{-t}$:
Condition on $\bar{v}\_1,\ldots,\bar{v}\_{\ell-1}$ being linearly independent - this can only decrease the probability of $T'\subsetneq T$.
Denote $T''\triangleq \mathrm{span}(\bar{v}\_1,\ldots,\bar{v}\_{\ell-1})$
Now, there is a probability of at least $2^{-t}$ that the rest of the $\bar{v}$'s all land in $T''$, and in such a case $T'\subsetneq T$
Now, note that $V\cap S \neq \emptyset$ is exactly equivalent to $x\in T'$ for some fixed $x\in \{0,1\}^{\ell}$ (that correspond to the what coset $S$ is of $S\_0$). Furthermore, conditioned on the event $T'\subsetneq T$ $x\notin T'$ with probability at least $1/2$. Thus $V\cap S = \emptyset$ with probability at least $2^{-t}$. So we need $2^{-t}\leq \delta$ which implies $k\geq (\ell-1) + \log(1/\delta) = \log(1/\epsilon) + \log(1/\delta) -1$.

> **Comments:**
> **username_2**: Nice argument. This seems to say that $S$ being an affine subspace does not help, right?  
> **username_0**: Thanks. I'm not sure I follow. It says an affine subspace is as hard to hit as any other set, and is as hard to hit by a subspace, as by a general set of pairwise independent points  

---

