Finding lots of discrete vectors in fairly general position

Question

How many vectors can there be in $\mathbb{F}_2^{2n}$ such that no $n$ of them form a linearly dependent set? The bounds I have so far are embarrassingly far apart, though that probably means I should have thought about the question for longer before posting it.

To get an upper bound, observe that you can partition $\mathbb{F}_2^{2n}$ into $2^{n+2}$ translates of an $(n-2)$-dimensional subspace. If you choose more than $(n-1)2^{n+2}$ vectors, then $n$ of them must lie in one of those translates, and therefore in an $(n-1)$-dimensional subspace. So you definitely can't choose more than $Cn2^n$ vectors with the required property.

In the other direction, if you choose $M$ vectors randomly, then the probability that some fixed set of $n$ of them lives in an $(n-1)$-dimensional subspace is at most $n2^{-n}$ (since one of them must lie in the linear span of the others). So the expected number of problematic sets of size $n$ is at most $\binom Mn n2^{-n}$. If this is at most $M/2$, then we can get rid of a vector from each problematic set and we end up with no such sets. But for $n\binom Mn$ to be less than $2^n$ we basically need $M$ to be proportional to $n$, so this gives a lower bound of something like $2n$, which is pathetic as we could have just taken $2n$ linearly independent vectors.

I end up with a similarly pathetic bound if I try to pick vectors one by one, always avoiding the subspaces that the previous vectors require me to avoid.

I think I'm slightly more convinced by the lower bound, pathetic as it is. My rough reason is that the difficulty I run into feels pretty robust, and also that the result I prove in the upper bound is much stronger than it needs to be (since the subspace I obtain is essentially a translate of some fixed subspace). But basically I can't at the time of writing see even roughly what the bound should be.

Answer 1

Update 2: Since there seems some to be some interest in small values, in addition to asymtotic results, at the end some data that can, using the interpretation detailed below, be obtained from tables of code parameters to be found at http://www.codetables.de/

Update: the number of such vectors should be at most $(2 + \epsilon)n$ for any $\epsilon > 0$ if $n$ is large enough.

The approach is as detailed below, but instead of (or in some sense in addition to) the Hamming bound we use McEliece--Rodemich--Rumsey--Welch bound which gives $$R \le h (1/2 - \sqrt{\delta (1 - \delta)}) +o(1)$$ with notation as below. Now, since $R = 1 - 2 \delta$ and ignoring the $o(1)$ one gets that the only positive $\delta \le 0.5$ for which this holds is in fact $0.5$. (I did not 'prove' this, but the functions seems nice enough to rely on computer aid and it should also be not too hard and is likely even written somewhere that this is so; for an illustration see for example the figure on page 2 in lecture notes of Atri Ruda; the Plotkin bound illustrates the $1 - 2 \delta$, the Elias--Bassalygo bound stays below it, and MRRW would at least where it is relevant be still better/smaller; one also sees nicely that the Hamming bound only works until $0.3...$; the GV is a lower bound so not relevant here).

Thus, the ratio $n/N$ needs to approach $0.5$ (we know already it cannot go to zero), and the claim follows.

---

While there are already two nice answers, I thought I still sketch how one also could get the linear bound by the approach given in my comment.

Suppose there is a collection of $N$ such vectors. We seek an upper bound for $N$, so one can assume they generate the space as otherwise on could take add some vectors.

Now let $H$ be the matrix whose columns are these vectors. The code with this check matrix will be an $[N,N-2n]$ binary lineary code with minimal distance greater $n$.

Write $R = (N-2n)/N$ and $\delta = n/N$.

By the Hamming bound one knows that $R \le 1- h(\delta/2) + o(1)$, as $N$ tends to infinity, where $h$ is the binary entropy function. Since $R = 1 - 2 \delta $ one gets that $h(\delta/2) \le 2 \delta + o(1)$. Since the derivative of $h$ at $0$ is $+\infty$ one gets that $\delta$ needs to stay away from $0$ showing the ratio $n/N$ stays bounded away from $0$.

Moreover, 'solving' the equation for $\delta$ would yield an actual constant.

Possibly using more sophisticated bounds from coding theory could yield a better constant; I will try when I have better access to a CAS and report if I find something.

---

Some small values, up to 20 and then selcted others, the first two match those given in comments by Gerry Myerson and Robert Israel. I retrieved and typed them quickly so small errors are possible; format (n , max number of vectors); if the later is not just a number, it is to be interpreted as bounds in the obvious way. [In case somebody would now how to format this better, please let me know.]

(3,32), (4,17), (5,24), (6,24), (7,28), (8,23), (9,28), (10,31), (11,34), (12,32), (13, 35-38), (14,37),, (15,40), (16,39), (17,43-45) , (18,44-48), (19,48-50), (20,48)

(25,59-60), (30,70), (40,88-89), (50,109-110), (100, 209-211)

Answer 2

It seems to me that Robert Israel's argument generalizes. The sum of any $\frac{n}{2}$ vectors in your collection has to be distinct, in order for any $n$ to be linearly independent. From this one gets the inequality $$\binom{M}{n/2}\le 2^{2n}-1$$ which in particular implies $M\le O(n)$.

Answer 3

$\def\FF{\mathbb{F}_2}$ Indeed, the linear bound is close to right. I can show that we can't beat about $3.197 n$.

For convenience, set $m=n/2$. Fix a constant $c$ and suppose that we can find $\geq cn$ vectors for infinitely many $n$. Notice that every $m$ element subset of our $cn$ vectors must have a different sum, or we could find a relation with at most $n$ terms. So $$\binom{cn}{m} \leq 2^{2n}$$ or $$(2cm)(2cm-1) \cdots (2cm-m+1) \leq 2^{2n} m! \leq 16^m m^m (e+o(1))^{-m} .$$ $$(2c)(2c-1/m)(2c-2/m) \cdots (2c-1+1/m) \leq (16 e^{-1} (1+o(1)))^m.$$ Taking logs $$\frac{1}{m} \sum_{i=0}^{m-1} \log (2c-i/m) \leq \log 16 -1 + o(1).$$ or, sending $m \to \infty$. $$\int_{2c-1}^{2c} \log t dt \leq \log 16 - 1.$$ I get that this forces $c \leq 3.1965677$.