Linear codes and character sums

Let V be an rn-dimensional linear subspace of Zn 2. Suppose the smallest Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology, V is a linear code of length n, rate r and distance d.) We settle two extremal problems on such spaces. First we prove a (weak form) of a conjecture by Kalai and Linial and show that the fraction of vectors in V with weight d is exponentially small. Specifically, in the interesting case of a small r, this fraction does not exceed 2 −Ω( log(1/r)+1 n). We also answer a question of Ben-Or, and show that if r> 1, then for every k, at mos