Choosing sets yielding large sumsets

Question

I am working on a problem which basically boils down to wanting to choose sets $A_1, \ldots, A_m$ over a group $G=(\mathbb{Z}_C,+)$, where $C$ and $m$ are constants, such that the sumsets defined with the $A_i$ in some sense are as large as possible.

More specifically, I want to figure out how to choose the $A_i \subset \mathbb{Z}_C$, s.t. the sumset $\alpha_1 A_1 + \cdots + \alpha_m A_m$ is as large as possible, and if possible covers all of $\mathbb{Z}_C$.

There are some results related to this in additive combinatorics, e.g. the Cauchy-Davenport inequality, but little of what I read is actually constructive in the sense that I want to determine the sets $A_i$.

Any ideas are very much appreciated. Thanks.

Answer 1

A nice strategy might be:

For one moment think we are in $\mathbb{Z}$

Let $d := \lceil \sqrt[n]{C} \rceil $. Take $A := {1, d, d^2 ... d^{n-1}}$. Then if we would have d copies of A, dA is containing like $ \{ 1, 2, 3, ... d ... d^{n}-1, d ^n \} $

Now factorize: $\mathbb{Z}/c\mathbb{Z}$. $A$ has some image. $dA$ covers $\mathbb{Z}/c\mathbb{Z}$. In some sence, this construction is optimal.

You might want to have $d := \lfloor \sqrt[n]{C} \rfloor $ sometimes

And I have a question. $\mathbb{Z}_c $ means $ \mathbb{Z} / c \mathbb{Z} $ in your question?

Answer 2

I have some problem with latex symbols in a comment so let'me add another answer for a short time.

Then I have no idea why just don't you choose

$A_1 = \{ 0, 1, ..., n-1 \} $

$ A_2 = \{ 0, n, ..., n*(n-1) \} $

$A_i = \{ 0*n^{i-1}, 1*n^{i-1}, ..., (n-1)*n^{i-1} \} $

$A_m = \{ 0*n^{m-1}, 1*n^{m-1}, ..., (n-1)*n^{m-1} \} $

$A_i = n^{i-1} \times A_1$

It's clearly injective to $\mathbb{Z}$ and it has only consecutive numbers. So its factorization either covers all the $\mathbb{Z} / c \mathbb{Z} $ or is a injection.

In fact, I have a solution for a case when you want to have precisely $\alpha_i$ of $A_i$ of some size $n_i$.

Maybe I didn't get your question.