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?

  • $\begingroup$ not significant, but any triple that zeroes $v_1,v_2,v_3$ also zeroes $-v_1,-v_2,-v_3.$ $\endgroup$ – kodlu May 7 '15 at 4:54
  • 3
    $\begingroup$ Previous version of question is at mathoverflow.net/questions/205840/… $\endgroup$ – Terry Tao May 7 '15 at 6:25
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.