1
$\begingroup$

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..

$\endgroup$

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.