Let $V_n=\{-1,1\}^n$ be the hypercube and let $C_n$ be a collection $\{x_1,...,x_n\}$ of $n$ distinct elements of $V_n.$

Question: what is the smallest number $N(n)$ of non-zero vectors with integer coefficients are needed to check that $C_n$ is linearly independent over the integers? That is, what is the smallest set of such vectors $\{v_1,...v_{N(n)}\}$ that if $C_n$ is linearly dependent over the integers then there exists some element $v_{i}$ with coordinates $(k_1,...,k_n)$ such that $k_1x_1+...+k_nx_n$ is zero.

  • 3
    $\begingroup$ Do you mean "zero" at the end? $\endgroup$ – Brendan McKay Dec 5 '12 at 8:31
  • 1
    $\begingroup$ Do you really want your collection of vectors `$\{x_1,\ldots, x_n\}$' to be unordered? $\endgroup$ – Rudi Pendavingh Dec 5 '12 at 9:29
  • 1
    $\begingroup$ Siegel's lemma will give you an estimate. $\endgroup$ – Felipe Voloch Dec 5 '12 at 16:16
  • $\begingroup$ Yes, I did mean "zero" at the end. $\endgroup$ – TOM Feb 17 '13 at 12:43

A natural idea would be to take all vectors from $[-t,t]^n$ for some $t$. The optimal value of such a $t$ is roughly $n^{n/2}$. This follows from results in this paper: https://link.springer.com/article/10.1007/s10107-011-0474-y.

Can anyone give a better upper bound than $N\le n^{n^2/2}$?

  • $\begingroup$ I would like to see a set C that is linearly dependent and yet has all 3^n quantities v*C nonzero. Here v ranges over vectors whose coordinates are -1 or 1 or 0. Gerhard "Maybe We Can Do Better" Paseman, 2018.12.05. $\endgroup$ – Gerhard Paseman Dec 5 '18 at 23:23

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.