Subset of $F_2^n$ that must contain some subspace of dimension $k$

Question

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.

Answer 1

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