# 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?

• not significant, but any triple that zeroes $v_1,v_2,v_3$ also zeroes $-v_1,-v_2,-v_3.$ – kodlu May 7 '15 at 4:54
• Previous version of question is at mathoverflow.net/questions/205840/… – Terry Tao May 7 '15 at 6:25
• The answer to the previous question was an absolute constant independent of $n$, namely $2^8$. Of course, as pointed out in the answer below, in fact $6$ suffices. – David May 7 '15 at 12:17

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.