3
$\begingroup$

The following may be well-known $-$ but not known to me:

What is the smallest possible size of a set in ${\mathbb F}_2^n$ that blocks every $2$-flat?

Here "blocks" means "have a non-empty intersection with", and $2$-flats are simply affine subspaces of dimension $2$; that is, zero-sum quadruples in ${\mathbb F}_2^n$. Passing to the complements, an equivalent restatement is:

What is the largest possible size of a set in ${\mathbb F}_2^n$ that does not contain any $2$-flat?

For $1$-flats the question becomes trivial: any set with at least two elements contains a $1$-flat.

It is readily seen that any set in ${\mathbb F}_2^n$ containing no $2$-flat has size at most $2^{n-2}$; can this bound be replaced with $c^n$, for some $c<2$? (Lower bounds of this form follow easily by considering random subsets of ${\mathbb F}_2^n$.)

There has been a number of MO posts on blocking sets, like this one; however, they do not seem to address the question above.

$\endgroup$
3
$\begingroup$

An $N$-element set contains no 2-flat iff all pairwise sums of its elements are distinct, so ${N\choose 2}\leq 2^n$, whence $N<1+2^{(n+1)/2}$.

[UPDATE] It seems that I have a construction providing $2^n$ points in $\mathbb F_2^{2n}$, confirming that $c=\sqrt2$ is optimal.

The idea is as follows. Denote $U=\mathbb F_2^n$. Assume that we have a map $\phi\colon U\to U$ such that $0\neq a+b=c+d, \; \{a,b\}\neq\{c,d\}\; \Rightarrow \; \phi(a)+\phi(b)\neq \phi(c)+\phi(d)$. Then the pairs $(a,\phi(a))\in U\oplus U$ form a required set of $2^n$ vectors, because their pairwis sums are distinct. It suffices now to find such $\phi$.

Identify $U$ with $\mathbb F_{2^n}$. THen $\phi(x)=x^3$ works. Indeed, if $0\neq a+b=c+d$ and $a^3+b^3=c^3+d^3$, then $a^2+b^2=(a+b)^2=(c+d)^2=c^2+d^2$ and $a^2+ab+b^2=\frac{a^3+b^3}{a+b}=\frac{c^3+d^3}{c+d}=c^2+cd+d^2$. Thus $ab=cd$, and the pairs $(a,b)$ and $(c,d)$ are pairs of roots of the same quadratic equation.

$\endgroup$
  • $\begingroup$ Good! Still, I wonder what are the best bounds known. The immediate probabilistic bound: consider a random set $A$ to which the elements of $\mathbb F_2^n$ are chosen independently with probability $p$, then the expected number of $2$-flats in $A$ is about $2^{3n}p^4$, while the expected size of $A$ is $2^np$; hence, for $p\approx 0.1\cdot 2^{-2n/3}$ we can destroy all $2$-flats removing not too many elements of $A$, and we are still left with, roughly, $2^np$ elements. That is, we get $c=2^{1/3}$ this way. $\endgroup$ – Seva Sep 15 '16 at 8:56
  • $\begingroup$ I've added an update with an example. $\endgroup$ – Ilya Bogdanov Sep 15 '16 at 9:22
  • $\begingroup$ Minor remark : the Croot-Lev-Pach-Ellenberg-Gijswijt method, as in dl.dropboxusercontent.com/u/15433464/f3_eng.pdf, gives a worse bound, namely $c = 4 \times 3^{-\frac{3}{4}} \simeq 1,75.$ $\endgroup$ – js21 Sep 15 '16 at 9:52

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.