Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
I think I can do the smallest cases. When $n=2$, no $n$ (distinct, non-zero) vectors form a linearly dependent set, so you can take all 15 non-zero elements of ${\bf F}_2^4$. When $n=3$, you are looking for the largest sum-free subset of ${\bf F}_2^6$, and that's the set of odd weight elements, of which there are 32. –  Gerry Myerson Apr 30 '12 at 23:36
5  
For $n=4$, if your set has $k$ members, there are ${k \choose 2}$ pairs which must all have distinct sums in ${\mathbb F}_2^8$, so ${k \choose 2} \le 2^8-1$, and $k \le 23$. The best solution I've been able to find so far has 17 members. –  Robert Israel May 1 '12 at 0:14
3  
Consider a matrix whose colums are a collection of vectors that do have the required property, say there are $N$. (We can assume the vectors span the full space.) Take the linear code $C$ with this check matrix. Its length is $N$. No $n$ vectors are dependent so minimal distance $D$ of $C$ is strictly greater than $n$. Moreover the dimension $K$ of $C$ is $N-2n$. The question is for which $N$ there can (still) exist $[N,N-2n, n+1]$ binary linear code. Combining this with results from coding theory should yield something. Sorry, I cannot check right now if this something will be useful. –  quid May 1 '12 at 0:41
    
@Robert: That bound should generalize to $\left(\begin{array}{c} k \\ n/2 \end{array}\right)\leq 2^{2n}-1$, no? –  Will Sawin May 1 '12 at 1:37
add comment

3 Answers 3

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)

share|improve this answer
3  
Perhaps I should add that the constants one gets with the Hamming bound is (essentially or even compltely) the one David Speyer got. (Indeed, in some sense looking at the proof of the Hamming bound, the argument is 'the same'.) –  quid May 1 '12 at 2:32
add comment

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)$.

share|improve this answer
add comment

$\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$.

share|improve this answer
1  
I take it this means we can't beat about $3.197n$, provided that $n$ is sufficiently large. We can certainly beat it for $n=2,3,4$. –  Gerry Myerson May 1 '12 at 5:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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