If such a set $ A$ of size $ m$ exists, all its admissible pairwise sums must lie in its complement, thus $ $ \binom{m}{2} \leq 2^n-m, $ $ which gives $ $ m\leq 2^{(n+1)/2}\qquad (1)$ $ .

Since $ a+b=c$ is the same as $ a+b+c=0$ in characteristic 2, a randomly chosen set of size roughly $ 2^{n/3}$ will have a solution with some constant positive probability.

For simplicity let $ n=2k$ . Consider the nonzero elements in $ \mathbb{F}_{2^k}$ as representing the vectors in $ \mathbb{F}_2^k$ and take “vectors” of the form $ (x,1/x)$ in $ \mathbb{F}_2^n.$ Take $ $ (x,1/x)+(y,1/y)=(z,1/z)$ $ equivalently $ $ x+y+z=0,$ $ and $ $ 1/x+1/y+1/z=0$ $ as the simultaneous equations we must avoid.

By the Newton-Girard formulas we equivalently want to avoid $ $ x+y+z=0,$ $ and $ $ x^2+y^2+z^2=0$ $ but in characteristic 2 the second equation is just the equare of the first.

This seems to say, if I pick a primitive element $ \alpha$ in the subfield defined above and define $ v(i)=(\alpha^i,\alpha^{-i}+\beta)$ where $ \beta$ is a nonzero element in $ \mathbb{F}_{2^n} \setminus\mathbb{F}_{2^k}$ , the vectors $ $ \{ v(i): 0\leq 2^k-2\}$ $ form the type of set we want with $ m=2^{n/2}-1.$

Question: Is there a better construction which approaches (1).