Typical sumsets of lattice points

Abstract

From a subset of the n-dimensional integer lattice, we independently pick two points uniformly at random. A sumset is formed by adding these two points component-wise and a sumset is called typical, if the sum falls inside this set with high probability. In this note we characterize the asymptotic size of the typical sumsets for large n, and show that the typical sumset size exhibits different behaviors when the density of the subset exceeds a certain value. We also discuss how these results connect to certain coding problems in Network Information Theory. In particular, we point out that a better understanding of the typical sumsets could improve the current analysis of lattice decoding.