1
$\begingroup$

It is trivial that $|A_1 + \cdots + A_h| \leq |A_1|\cdots |A_h|$, where $h \geq 2$ and $A_i \subseteq \mathbb{Z}$ are nonempty finite sets and $A_1 + \cdots + A_h :=\{a_1 + \cdots + a_h : a_i \in A_i ~\text{for}~ i = 1, \ldots, h\}$. I am interested in finding those sets for which $|A_1 + \cdots + A_h|$ is exactly $|A_1|\cdots |A_h|$. I have some specific examples for the case $h = 2$.

$\endgroup$
3
  • 1
    $\begingroup$ Since addition is commutative, you will have equality in very few cases. You might ask this question elsewhere. Gerhard "Or Else Ask Something Different" Paseman, 2016.06.12. $\endgroup$ Jun 12, 2016 at 15:58
  • $\begingroup$ Yes, I am looking for and interested in knowing those examples (at least one) which will work for arbitrary $h$. $\endgroup$
    – Rajkumar
    Jun 12, 2016 at 16:13
  • 1
    $\begingroup$ Try 0,2^h. You might note that the general case reduces somewhat to the case h=2. Gerhard "Depends On The Desired Characterization" Paseman, 2016.06.12. $\endgroup$ Jun 12, 2016 at 16:26

1 Answer 1

2
$\begingroup$

Elaborating on what Gerhard Paseman points out, selecting sets $A_i = \{kh^i \mid 0 \le k < h\}$ will work.

More generally, if you define your sets inductively (and restrict to only using positive integers) so that the smallest pairwise difference in elements in $A_i$ is greater than the largest element in $A_1 + \cdots + A_{i-1}$ then it will also avoid any collisions, and have $|A_1 + \cdots + A_{i}| = |A_1| \cdots |A_i|$.

Edit to provide example:

For example, choosing $A_1 = \{0,1,4\}$ and then $A_2$ any set with elements at least $5$ apart $A_2 = \{0,7, 22, 54, 59\}$ and now $A_3$ any set with elements at least $64$ apart $A_3 = \{0, 77, 200\}$ and $A_4$ having elements at least $264$ apart, etc. You can continue at will.

$\endgroup$
1
  • $\begingroup$ @ Gerhard Paseman @ Ben Weiss Thank you. This construction is really nice. We can construct a large number of examples. $\endgroup$
    – Rajkumar
    Jun 13, 2016 at 9:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.