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?