Typical sumsets of linear codes

Abstract

Given two identical linear codes C with rate R over Fq of length n, we independently pick one codeword from each codebook uniformly at random. A sumset is formed by adding these two codewords entry-wise as integer vectors and a sumset is called typical, if the sum falls inside this set with high probability. In this paper we show that the asymptotic size of such typical sumsets for most codes is min22nR, 2n(R+D) where D depends solely on the alphabet size q. More generally, we completely characterize the asymptotic size of typical sumsets of two nested linear codes C1, C2 with different rates. We also provide two applications of the results, one on a computation problem over the general two-..