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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Sep 15, 2016 at 8:56
  • $\begingroup$ I've added an update with an example. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 15, 2016 at 9:22
  • 1
    $\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
    Commented Sep 15, 2016 at 9:52
3
$\begingroup$

These are called Sidon sets. Generally, these are sets such that all pairwise sums are disjoint, for characteristic 2 this coincides with sets not containing 2-flats. There are quite a few papers in Boolean functions literature about them, including some bounds and known values.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .