Additive combinatorics and $|S \cap (S+t)| \geq K |S|$ over $\mathbb{F}_2^n$ 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?
 A: 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.
