Let $C$ be a generalized arithmetic progression, i.e., given positive integers $N_1,\ldots,N_k$ and $a_0,a_1,\ldots,a_k$ then $$ C=\left\{a_0+\sum_{i=1}^n a_in_i: 0\le n_i \le N_i-1 \text{ for all }i=1,\ldots,k\right\}. $$

It is clear that, for some suitable choices of the above parameters, then the some elements of $C$ can be written in at least two ways so that $|C|<N_1\cdots N_k$. At this point, consider the sumset $2C:=\{a+b: a,b \in C\}$.

Then $$ |2C|<2^k|C|. $$ Why is it true? It should be easy to check it, but I don't see why..?

Ps. The inequality is clear for $k=1$; moreover, it holds $$ |2C|=\left|\left\{\sum_{i=1}^n a_in_i: 0\le n_i \le 2N_i-2 \text{ for all }i=1,\ldots,k\right\}\right|, $$ but we may still have some elements which is written in more than one way..


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.