Let $F_2^n$ be the set of all vectors of length $n$ with values of $0$ or $1$ and $A_n$ = $F_2^n \setminus(11\ldots1)$. Set $A_n$ contains all vectors except one with all $1$s. We can consider cosets of codimention $1$ that lies in $A_n$. For example solutions of equation $x_1+x_2=1$ is such a coset.
I am interested in this problem: find minimal set of cosets $C$, so that each $2$ vectors in $A_n$ are in one coset in $C$. I have found this solution:
$x_1=0, \ldots,x_n=0,\ x_i+x_j=1$ for all $1 \le i<j\le n$.
It contains $n+ {n\choose 2}=\frac{n(n+1)}{2}$ cosets. I need help finding better solution or proving that minimal set of cosets has size $\theta(n^2)$ so no linear solution is possible.