Prove that any 2-independent set of $\{0,1\}^n$ has size at least $n+1$

Question

Definition: Set S is called 2-independent subset of $\{0,1\}^n$ if for every two different positions $i_1, i_2 \in \{1,2, \dots , n\}$ and for every two numbers $a_1, a_2 \in \{0,1\}$ the probability $$ Pr_{x \sim U(S)}[x_{i_1} = a_1, \; x_{i_2} = a_2] = \frac{1}{4}$$ The probability is calculated over $x$ taken from uniform distribution over the set $S$.

It is easy to see that this definition is equivalent to: for every two positions every combination of bits (00, 01, 10, 11) occur in $n/4$ vectors from $S$ in this positions.

The problem is to prove lower bound on size of $S$.

Question: Prove that $|S| \ge n + 1$.

I've found a hint, that didn't help a lot:

Hint: Find a set of linearly independent vectors in $R^{|S|}$ of cardinality at least $n + 1$. Specifically, for $i \in \{1, 2, . . . , n\}$, consider the vector $\langle \chi_i (x)\rangle_{x\in S}$ where $\chi_i(x) = (−1)^{x_i}$ and vector $\langle 1,1, \dots,1 \rangle$.

Answer 1

A hint on how to use the hint:

Consider the $A$ of $n + 1$ vectors in $\Bbb R^{|S|}$, which are the vectors $\langle \chi_i(x)\rangle_{x \in S}$ for $i = 1, \dots, n$, together with the vector $\langle 1, \dots, 1\rangle$.

Try to show that

• each vector in $A$ has length $\sqrt n$;
• any two different vectors in $A$ are orthogonal to each other.

This proves that the set $A$ is linearly independent over $\Bbb R$ and hence $|S| = \operatorname{dim}(\Bbb R^{|S|}) \geq |A| = n + 1$.