Additive combinatorics and $|S \cap (S+t)| \geq K |S|$ over $\mathbb{F}_2^n$

Question

I don't know much about additive combinatorics, and I am wondering if there are results concerning the size of $|S \cap (S+t)|$ where $S \subset \mathbb{F}_2^n$ and $t \in \mathbb{F}_2^n$. Especially, is it proved (or does it seem plausible) that for any $S$ there exists $t$ such that $|S \cap (S+t)|$ is big (i.e. greater than $K|S|$ for some constant $K$)? Obviously it can be impossible if $|S|$ is too small, but perhaps it holds for $S$ big enough?

Answer 1

Leading off with a few easy (trivial) observations with a view of extracting a more precise range for $|S|$ where something good might happen. Undoubtedly you knew about these arguments.

An averaging argument: shows that there exists $t\neq0$ such that $$ \left|S\cap (S+t)\right|\ge\left\lceil\frac{|S|^2-|S|}{2^n-1}\right\rceil. $$

Proof. Consider the sum $$ M(S)=\sum_{t\neq0}|S\cap (S+t)|. $$ Every point $\in S$ appears in $|S|-1$ other translates $S+t$ (with varying $t$), so $M(S)=|S|(|S|-1)$. Because some $t$ must contribute at least the average amount (and the contributions are integers), the claim follows.

The simple averaging argument is occasionally relatively tight. A recurring technique in looking for examples is to view the space $\Bbb{F}_2^n$ as a lower dimensional space over an extension field $K=\Bbb{F}_{2^m}$, $m\mid n$, and study algebraic varieties in $K^{n/m}$.

For example, for the averaging argument to force intersections with more than one element, we need $|S|> \sqrt{2^n}$. So let's assume that $n=2m$.

Example. Consider the set $S=\{(x,y)\in K^2\mid y=x^3\}.$ Then $|S|=2^m$, and $|S\cap (S+t)|\le2$ for all $t\in K^2,t\neq0$.

Proof. Basically I am claiming that the graph $y=x^3$ of the polynomial $x^3$ intersects with any of its translates in at most two points. Write $t=(t_1,t_2), t_1,t_2\in K$. If a point $P=(x,y)\in S\cap (S+t)$, then its coordinates satisfy the system of equations $$ \begin{cases}y=x^3,\\ y+t_2=(x+t_1)^3.\end{cases} $$ Here $t_1,t_2\in K$ are constants and at least one of them is non-zero. Expanding the latter equation and substituting the former into it we arrive at $$ t_2=x^2t_1+xt_2^2+t_1^3. $$ If $t_1=0$ this has no solutions because then $t_2\neq0$. If $t_1\neq0$, then this has at most two solutions $x$, but a known $x$ determines $y$ uniquely. The claim follows.

Similarly, if $n=3m$ we can expect that if $S$ is a surfaces in $K^3$ it intersects with its translates along a curve. So if $|S|\approx 2^{2n/3}$ then $S\cap (S+t)$ is of the order $O(2^{n/3})$. The same applies to higher $n/m$, but it becomes progressively more difficult (at least for me) to produce examples like above, where we get very precise information.

Of course, if $|S|>C\cdot 2^n$, then the averaging argument tells us that intersections of the approximate size $C^2\cdot 2^n\approx C\cdot |S|$ must occur. Somehow I suspect that such sets $S$ may be too large to be of interest to you.

A final note: Coding theorists and cryptographers have studied related problems. Fpr examples to thwart certain types of cryptanalysis people often want similar kind of non-linearity.