Linear independence of +/- 1 strings/vectors II Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a following quantitative statement:
What is the smallest number of triples, say f(n), in $\mathbb{Z}^{3}$ such that if the vectors $v_1,v_2,v_3$ are linearly dependent, then for some triple $(k_1,k_2,k_3)\neq 0$ we have
$$k_{1}v_{1}+k_{2}v_{2}+k_{3}v_{3}=0?$$ 
As there are exactly $2^n$ vectors and there are $N=\binom{2^n}{3}$ triples, then clearly $f(n)\leq N$. But this is very wasteful. Is there a way to significantly improve this trivial bound? Could one hope for a polynomial in $n$ number of triples? 
 A: Not just polynomial, constant: the triples $(0,1,1)$, $(0,1,-1)$, $(1,0,1)$, $(1,0,-1)$, $(1,1,0)$, $(1,-1,0)$ suffice.
Any  $v_1, v_2, v_3 \in V$, have in each coordinate  $(v_1(i),v_2(i),v_3(i))$ one of the 
$8$ values $\pm (1,1,1), \pm (1,1,-1), \pm (1,-1,1), \pm (1,-1,-1)$.
By symmetry (if necessary flipping the sign of $v_2$ or $v_3$), we may assume WLOG $(1,1,1)$ is one of these.
Then any $(k_1,k_2,k_3)$ such that $k_1 v_1 + k_2 v_2 + k_3 v_3 = 0$ satisfies
$k_1 + k_2 + k_3 = 0$.  If none of the $k_i$ are $0$, the only other
$\pm k_1 \pm k_2 \pm k_3$ that is  $0$ is $-k_1 - k_2 - k_3$.  That is,
any $v_1, v_2, v_3 \in V$ with $k_1 v_1 + k_2 v_2 + k_3 v_3$ have all 
$(v_1(i),v_2(i),v_3(i)) \in \{(1,1,1),(-1,-1,-1)\}$.  This means $v_1 = v_2 = v_3$.  These cases are captured by $(0,1,-1)$ (or $(0,1,1)$ if one of $v_2$ and $v_3$ was flipped).
If one of the $k_i$ is $0$, say $k_1$, then we can have four possible values 
$(1,1,1)$, $(-1,1,1)$, $(1,-1,-1)$, $(-1,-1,-1)$.  Any triple $v_1,v_2,v_3$ whose coordinates are in those cases has $0 + v_2 + v_3 = 0$.  So again these are covered by $(0,1,1)$ (or $(0,1,-1)$ if $v_2$ or $v_3$ was flipped), 
and similarly if $k_2 = 0$ they are covered by $(1,0,1)$ or $(1,0,-1)$, and if $k_3 = 0$ by $(1,1,0)$ or $(1,-1,0)$.
Of course it's impossible to have two of the three be $0$.  So that takes care of all cases.
