On a problem about $GF(2)^n$

Question

For $A\subseteq {\mathbb F}_2^n$ let $$ Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}. $$ I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then $$ |Q(A)|\ge2^{k+1}-1. $$

I have checked using a computer that this is true when $n\le5$. Also, this is true when $k=n-1$. I run my brute-force program to check it for $n=6$ and $k=3$, but it has not finished yet. If true, this cannot be improved, because we can take $A$ to be a subset of a $(k+1)$-dimensional linear space. I do not know how to proceed.

Any hints and / or suggestions would be appreciated.

Thanks!

Answer 1

It is true that $|Q(A)|\ge 2^{k+1}-1$; this can be proved using Kneser's theorem as follows.

Let $2A:=\{a'+a''\colon a',a''\in A\}$ be the sumset of $A$; we thus want to prove that if $A\subset{\mathbb F}_2^n$ has size $|A|=2^k+1$, then $|2A|\ge 2^{k+1}$. Assuming for a contradiction that this is wrong, denote by $H$ the period (stabilizer) of $2A$: $$ H:=\{g\in {\mathbb F}_2^n\colon 2A+g=2A \}; $$ notice that this is a subgroup of (the additive group of) ${\mathbb F}_2^n$, and $2A$ is a union of cosets of $H$. If $|H|\ge 2^{k+1}$, then we are done in view of $|2A|\ge|H|$. Otherwise $|H|\le 2^k$, and since the sumset $A+H:=\{a+h\colon a\in A,\,h\in H\}$ is a union of cosets of $H$, its cardinality is divisible by $|H|$; hence, $|A+H|\ge 2^k+|H|$. Assuming now $|2A|<2^{k+1}$, by Kneser's theorem we have $$ |2A|=2|A+H|-|H| \ge 2^{k+1}+|H| > 2^{k+1}, $$ a contradiction.