# How many vectors of Hamming weight L in “random” K dimensional subspace of F_2^N ? Or how good/bad is random linear block code ?

Consider linear $N$-dimensional space $F_2^N$. Consider its $K$ dimensional subspace $V \subset F_2^N$. Let us calculate $w(k,V,N)$ number of vectors in $V$ of Hamming weight $k$ in $V$.

Since there is finite number of subspaces we can calculate average: $\sum_{V} w(k,V,N)$.

Question is there something known about it ?

Coding theory motivation - is to understand how good/bad is a random linear code ? I.e. error-correcting code is precisely $V$ in $F_2^N$. Code is bad if we have many vectors of small Hamming weight.

http://en.wikipedia.org/wiki/Hamming_weight

-

You can compute the average very explicitly. For $v\in F_2^N$, let $||v||$ denote the Hamming weight of $v$. Changing the order of summation, your sum can be re-written as $$\sum_{v\colon\ ||v||=k} T(v),$$ where $T(v)$ is the number of $K$-dimensional subspaces of $F_2^N$, containing $v$. Now, if $k>0$, then $v\ne 0$, and the number of subspaces in question does not depend on $v$ and is equal to the number of $(K-1)$-dimensional subspaces of $F_2^{N-1}$, which is $$\frac{(2^{N-1}-1)(2^{N-1}-2))(2^{N-1}-4)\cdots(2^{N-1}-2^{K-2})}{(2^{K-1}-1)(2^{K-1}-2)(2^{K-1}-4)\cdots(2^{K-1}-2^{K-2})}.$$ The sum under consideration is therefore equal to the product of this fraction and the binomial coefficient $\binom Nk$ (the number of vectors $v$ of weight $k$), and the average is obtained by dividing this sum by the total number of all $K$-dimensional subspaces of $F_2^N$, which is $$\frac{(2^N-1)(2^N-2)(2^N-4)\cdots(2^N-2^{K-1})}{(2^K-1)(2^K-2)(2^K-4)\cdots(2^K-2^{K-1})}.$$ After cancellations, the average is equal to $$\frac{2^K-1}{2^N-1}\,\binom Nk = 2^{K-N}\binom Nk \, (1+o(1)),\ K\to\infty.$$
What we computed is the average (=expected) number of vectors of weight $k$ in a randomly chosen $K$-dimensional subspace. Summing over $k$, we get the total number of vectors in a random $K$-dimensional subspace, which is $2^K$. Makes sense? –  Seva Feb 24 '12 at 19:57
One more comment to interpret the result. We have shown that the proportion of vectors of weight $k$ among all vectors of a random $K$-dimensional subset is about $2^{-N}\binom Nk$, which is the proportion of vectors of weight $k$ among all vectors of $F_2^K$. In other words, lying in a $K$-dimensional subspace is independent from having weight $k$. Pretty expectable! –  Seva Feb 24 '12 at 20:21