# How well do subspaces hit sets

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.

• 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. Jun 8 '16 at 15:37
• 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
Jun 8 '16 at 17:12
• Right, an affine subspace. Otherwise there is always an intersection... Jun 8 '16 at 17:15
• But indeed this was good thing to try, as I thought initially dependence on $1/\delta$ could be smaller than logarithmic
– relG
Jun 8 '16 at 17:20

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$.
• Nice argument. This seems to say that $S$ being an affine subspace does not help, right? Jun 17 '16 at 1:27