On the minimum size of subset and subsequence sums in integers

Bhanja, Jagannath; Pandey, Ram Krishna

Comptes Rendus. Mathématique, Tome 360 (2022) no. G10, pp. 1099-1111.

Let $𝒜$ be a sequence of $rk$ terms which is made up of $k$ distinct integers each appearing exactly $r$ times in $𝒜$. The sum of all terms of a subsequence of $𝒜$ is called a subsequence sum of $𝒜$. For a nonnegative integer $\alpha \le rk$, let ${\Sigma }_{\alpha }\left(𝒜\right)$ be the set of all subsequence sums of $𝒜$ that correspond to the subsequences of length $\alpha$ or more. When $r=1$, we call the subsequence sums as subset sums and we write ${\Sigma }_{\alpha }\left(A\right)$ for ${\Sigma }_{\alpha }\left(𝒜\right)$. In this article, using some simple combinatorial arguments, we establish optimal lower bounds for the size of ${\Sigma }_{\alpha }\left(A\right)$ and ${\Sigma }_{\alpha }\left(𝒜\right)$. As special cases, we also obtain some already known results in this study.

Classification : 11B75, 11B13, 11B30

[1] Balandraud, Éric An addition theorem and maximal zero-sum free sets in $\mathbb{Z}/p\mathbb{Z}$, Isr. J. Math., Volume 188 (2012), pp. 405-429 | DOI | MR | Zbl

[2] Balandraud, Éric Addition theorems in ${𝔽}_p$ via the polynomial method (2017) (https://arxiv.org/abs/1702.06419)

[3] Balandraud, Éric; Girard, Benjamin; Griffiths, Simon; Hamidoune, Yahya O. Subset sums in abelian groups, Eur. J. Comb., Volume 34 (2013) no. 8, pp. 1269-1286 | DOI | MR | Zbl

[4] Bhanja, Jagannath A note on sumsets and restricted sumsets, J. Integer Seq., Volume 24 (2021) no. 4, 21.4.2, 9 pages | MR | Zbl

[5] Bhanja, Jagannath; Pandey, Ram K. Inverse problems for certain subsequence sums in integers, Discrete Math., Volume 343 (2020) no. 12, 112148, 11 pages | MR | Zbl

[6] DeVos, Matt; Goddyn, Luis; Mohar, Bojan A generalization of Kneser’s addition theorem, Adv. Math., Volume 220 (2009) no. 5, pp. 1531-1548 | DOI | MR | Zbl

[7] DeVos, Matt; Goddyn, Luis; Mohar, Bojan; Šámal, Robert A quadratic lower bound for subset sums, Acta Arith., Volume 129 (2007) no. 2, pp. 187-195 | DOI | MR | Zbl

[8] Erdős, Pál; Heilbronn, Hans A. On the addition of residue classes mod $p$, Acta Arith., Volume 9 (1964), pp. 149-159 | DOI | MR | Zbl

[9] Freeze, Michael; Gao, Weidong; Geroldinger, Alfred The critical number of finite abelian groups, J. Number Theory, Volume 129 (2009) no. 11, pp. 2766-2777 | DOI | MR | Zbl

[10] Griffiths, Simon Asymptotically tight bounds on subset sums, Acta Arith., Volume 138 (2009) no. 1, pp. 53-72 | DOI | MR | Zbl

[11] Grynkiewicz, David J. On a partition analog of the Cauchy–Davenport theorem, Acta Math. Hung., Volume 107 (2005) no. 1-2, pp. 167-181 | MR | Zbl

[12] Hamidoune, Yahya O. Adding distinct congruence classes, Comb. Probab. Comput., Volume 7 (1998) no. 1, pp. 81-87 | DOI | MR | Zbl

[13] Hamidoune, Yahya O.; Lladó, Anna S.; Serra, Oriol On complete subsets of the cyclic group, J. Comb. Theory, Ser. A, Volume 115 (2008) no. 7, pp. 1279-1285 | DOI | MR | Zbl

[14] Jiang, Xing-Wang; Li, Ya-Li On the cardinality of subsequence sums, Int. J. Number Theory, Volume 14 (2018) no. 3, pp. 661-668 | DOI | MR | Zbl

[15] Mistri, Raj K.; Pandey, Ram K. A generalization of sumsets of set of integers, J. Number Theory, Volume 143 (2014), pp. 334-356 | DOI | MR | Zbl

[16] Mistri, Raj K.; Pandey, Ram K. The direct and inverse theorems on integer subsequence sums revisited, Integers, Volume 6 (2016), #A32, 8 pages | MR | Zbl

[17] Mistri, Raj K.; Pandey, Ram K.; Prakash, Om Subsequence sums: direct and inverse problems, J. Number Theory, Volume 148 (2015), pp. 235-256 | DOI | MR | Zbl

[18] Nathanson, Melvyn B. Inverse theorems for subset sums, Trans. Am. Math. Soc., Volume 347 (1995) no. 4, pp. 1409-1418 | DOI | MR | Zbl

[19] Nathanson, Melvyn B. Additive Number Theory. Inverse problems and the geometry of sumsets, Graduate Texts in Mathematics, 165, Springer, 1996 | DOI | Zbl

[20] Olson, John E. An addition theorem modulo $p$, J. Comb. Theory, Volume 5 (1968), pp. 45-52 | DOI | MR | Zbl

[21] Peng, Jiangtao; Hui, Wanzhen; Li, Yuanlin; Sun, Fang On subset sums of zero-sum free sets of abelian groups, Int. J. Number Theory, Volume 15 (2019) no. 3, pp. 645-654 | DOI | MR | Zbl