This question has practical meanings in algebraic attack of stream ciphers in cryptography. It can be stated as follows:


Suppose $V$ is a $n$ dimensional vector space over the field $F\_2$, where $F\_2$ is the simplest finite field contains only $\{0,1\}$. you can take $V$ to be $F\_2^n$. $S$ be a subset of $V$. The question is, What is the minimum of the size of $S$ such that $S$ must contain some $k$ dimensional linear sub-manifold $M$ of $V$, where $k$ is a given positive integer below $n$? 


Here by a linear sub-manifold $M$ of dimension $k$, we mean that $M$ can be expressed as $M=\{x+W\}$, where $x$ is a fixed vector in $V$ and $W$ is a $k$ dimensional subspace of $V$.


It's obvious that $|S|>2^k$，since any sub-manifold of dimension $k$ contains exactly $2^k$ points but there are subsets of size $2^k$ that are not submanifolds. I think this problem must has been considered by combinatorists, but I didn't find it in any standard textbooks on combinatorics.



Subset of $F_2^n$ that must contain some subspace of dimension $k$
As noted by Seva, you're looking for Szemeredi's cube lemma, which is one of the simplest results of its kind.


Let $S\subset\mathbf{F}\_2^n$, and let $\|S\|\_{U^k}^{2^k}$ denote the number of $e\_0,e\_1,\dots,e\_k\in \mathbf{F}\_2^n$ such that
$$\{e\_0 + x\_1 e\_1 + \cdots + x\_k e\_k : x\_i\in\{0,1\}\}\subset S,$$
normalised by $2^{n(k+1)}$. In other words define
$$\|S\|\_{U^k}^{2^k} = 2^{-n(k+1)}\sum\_{e\_0,e\_1,\dots,e\_k} \prod\_{x\in\{0,1\}^k} 1\_S(e\_0 + x\_1 e\_1 +\cdots + x\_k e\_k).$$
Then $\|S\|\_{U^1} = |S|/2^n$, and by the Cauchy-Schwarz inequality we have $\|S\|\_{U^k} \leq \|S\|\_{U^{k+1}}$ for all $k$, so $\|S\|\_{U^k}^{2^k} \geq |S|^{2^k}/2^{n2^k}$. The number of $e\_0,e\_1,\dots,e\_k$ for which
$$|\{e\_0+x\_1e\_1+\cdots + x\_ke\_k: x\_i\in\{0,1\}\}|<2^k$$
is at most $k 2^{nk} 2^{k-1}$, so there must be at least one affine subspace of dimension $k$ in $S$ if
$$|S| > 2^{n(1-2^{-k}) + 1}.$$


Upper bounds will come from random examples. Include each point of $\mathbf{F}\_2^n$ in $S$ independently with probability $p$. Then any fixed $k$-dimensional affine subspace of $\mathbf{F}\_2^n$ is contained in $S$ with probability exactly $p^{2^k}$. The number of such affine subspaces is at most $2^{n(k+1)}$, so the expected number contained in $S$ is at most $2^{n(k+1)} p^{2^k}$. Taking $p\sim 2^{-n(k+1)/2^k}$, you get at least one set $S$ of size at least $2^{n(1 - (k+1)2^{-k})}$ not containing such a subspace.


So the exponent is somewhere between $1-(k+1)2^{-k}$ and $1 - 2^{-k}$. I think for $k>2$ the exact value is not known.


EDIT: One can improve the random example a little as follows. If the expected number of subspaces is $2^{n(k+1)} p^{2^k}$ then take any set with at most this many subspaces and then just remove one point from each subspace. You get a set of size $2^n p (1 - 2^{nk} p^{2^k-1})$, so it suffices to take $p\sim 2^{-nk/(2^k-1)}$, so the exponent is somewhere between $ 1-k/(2^k-1)$ and $1-2^{-k}$.


