On Nathanson's Triangular Number Phenomenon

Abstract

For a finite set $A\subseteq \mathbb{Z}$, the $h$-fold sumset is $hA:=\{x_1+\cdots +x_h:x_i\in A\}$. We interpret the beginning of the sequence of sumset sizes $(|hA|{)}_{h=1}^{\infty }$ in terms of the successive $L^1$-minima of a lattice (specifically, the points in ${\mathbb{Z}}^{|A|}$ whose coordinates sum to 0 and which are perpendicular to $⟨a_1,\dots ,a_{|A|}⟩$). In particular, if $h_1,h_2$ are the first and second minima, and $1\le h<h_1$, then $|hA|=\left(\genfrac{}{}{0ex}{}{h+|A|-1}{|A|-1}\right)$, while if $h_1\le h<h_2$, then $|hA|=\left(\genfrac{}{}{0ex}{}{h+|A|-1}{|A|-1}\right)-\left(\genfrac{}{}{0ex}{}{h-h_1+|A|-1}{|A|-1}\right)$. This explains the appearance of triangular numbers in the sequence of sumset sizes, an observation related to a recent experiment of Nathanson.

12 pages