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? 



Linear independence of +/- 1 strings/vectors II
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.


