4
$\begingroup$

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.

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

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

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

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.