# linear independence of finite binary sequences

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.

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

## 1 Answer

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}$$?

• 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. – Gerhard Paseman Dec 5 '18 at 23:23