Weight distribution of cosets of small codes with good dual properties

The bilateral minimum distance of a binary linear code is the maximum d such that all nonzero codewords have weights between d and n - d. Let Q ⊂ {0, 1}ⁿ be a binary linear code whose dual has bilateral minimum distance at least d, where d is odd. Roughly speaking, we show that the average L_∞-distance - and consequently the L₁-distance - between the weight distribution of a random cosets of Q and the binomial distribution decays quickly as the bilateral minimum distance d of the dual of Q increases. For d = Θ(1), it decays like n^-Θ(d). On the other d = Θ(n) extreme, it decays like and e^-Θ(d). It follows that, almost all cosets of Q have weight distributions very close to the to the binomial distribution. In particular, we establish the following bounds. If the dual of Q has bilateral minimum distance at least d = 2t + 1, where t ≥ 1 is an integer, then the average L_∞-distance is at most equation. For the average L₁-distance, we conclude the bound equation, which gives nontrivial results for t ≥ 3. We given applications to the weight distribution of cosets of extended Hadamard codes and extended dual BCH codes. Our argument is based on Fourier analysis, linear programming, and polynomial approximation techniques.