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.



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

  • $\begingroup$ @Seva WOW !!! Can we understand what distribution we get when K,N are "large" ? It might be just something simple related to binomial distribution tending to normal distribution ... $\endgroup$ Feb 24 '12 at 18:09
  • $\begingroup$ I appended two lines to my answer to address this. $\endgroup$
    – Seva
    Feb 24 '12 at 19:13
  • $\begingroup$ if sum k=1...N I expect to get 1+O(1), but we get 2^K... is it correct ? $\endgroup$ Feb 24 '12 at 19:21
  • $\begingroup$ 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? $\endgroup$
    – Seva
    Feb 24 '12 at 19:57
  • $\begingroup$ 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! $\endgroup$
    – Seva
    Feb 24 '12 at 20:21

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.