6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @S.Carnahan how so? $\mathbb F_2$-subspaces seem different from combinatorial lines. $\endgroup$ – Will Sawin Jul 12 '14 at 5:31
  • $\begingroup$ @WillSawin My mistake. I see now that combinatorial subspaces form a strict subset of linear submanifolds. (previous comment deleted) $\endgroup$ – S. Carnahan Jul 12 '14 at 6:00
  • 2
    $\begingroup$ Google for "Szemredi's Cube Lemma". $\endgroup$ – Seva Jul 12 '14 at 6:19
8
$\begingroup$

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

$\endgroup$
0

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.