Linear codes and character sums (Q1410404)

\textit{G. Kalai} and \textit{N. Linial} [IEEE Trans. Inf. Theory 41, 1467-1472 (1995; Zbl 0831.94019)] conjectured that the size of the code with the distribution of distances near the minimal distance is exponentially small. The authors estimate the fraction of non-zero vectors of minimal weights in an \(r\cdot n\)-dimensional subspace of \(\mathbb{Z}_2^n\). Using the connection between the value distributions of character sums over \(\mathbb{Z}_2^n\) and extremal problems on linear codes the authors prove that for \(r\gg {{\log n}\over{\sqrt{n}}}\) the above fraction is exponentially small and does not exceed \(2^{-\Omega ({{r^2}\over{\log (1/r)+1}}n)}\). Let \(E\) be the affine subspace in \(\mathbb{Z}_2^n\) of dimension \(a\cdot n (a> {{1}\over{2}}, n\) is even and large) and \(L_k\) be the set of vectors in \(\mathbb{Z}_2^n\) whose Hamming weight is \(k\). The authors also answer a question of M. Ben-Or (preprint of Hebrew University, 1996) about the largest possible number of a given weight. They prove that for every \(0\leq k \leq n\) the inequality \[ |E\cap L_k |\leq C_a {{|E|}\over{\sqrt{n}}} \] is satisfied.