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$.
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$– Gerhard PasemanCommented 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$– RajkumarCommented 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$– Gerhard PasemanCommented Jun 12, 2016 at 16:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ @ Gerhard Paseman @ Ben Weiss Thank you. This construction is really nice. We can construct a large number of examples. $\endgroup$– RajkumarCommented Jun 13, 2016 at 9:22