Some Inverse Results on Restricted Signed Sumset

Abstract

Let h and k be positive integers with h ≤ k, and let A = {a₀, a₁, …, a_k−1} be a finite set of k integers. The resticted h-fold signed sumset, denoted by h_±^∧A, is defined as

h_{\pm }^{\wedge }A:=\left\{\sum _{i=0}^{k-1}{\lambda }_i{a}_i:{\lambda }_i\in \{-1,0,1\}\text{for}i=0,1,\dots ,k-1\text{and}\sum _{i=0}^{k-1}\left|{\lambda }_i\right|=h\right\}.

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$h_ {\pm} ^{\wedge}A: = \left\{{\sum\limits_{i = 0}^{k - 1} {{\lambda _i}{a_i}:{\lambda _i}} \in \{{- 1,0,1} \}\,{\text{for}}\,i = 0,1, \ldots,k - 1\,{\text{and}}\,\sum\limits_{i = 0}^{k - 1} {\left| {{\lambda _i}} \right|} = h} \right\}.$$\end{document}

A direct problem associated with this sumset is finding the optimal lower bound of ∣h_±^∧A∣ when the finite set of integers A is given. An inverse problem is about to characterizing the sets A when ∣h_±^∧A∣ attains the optimal lower bound. The characterization of the underlying sets for slight deviation from the minimum size of the sumset is called an extended inverse problem. In this article, we prove direct and inverse theorems for h_±^∧A when h ∈ {2, 3, k}. We also prove extended inverse theorems and Freiman’s (3k − 4)-type results for h_±^∧A when h ∈ {2, 3, k}. We remark that there is no finite set of k ≥ 10 nonnegative integers with 0 ∈ A such that ∣3_±^∧A∣ = 6k − 10, and there is no finite set A of k ≥ 12 positive integers such that ∣3_±^∧A∣ = 6k − 7.

Keywords

Sumset / restricted signed sumset / Freiman’s 3k − 4 theorem / extended inverse theorem / 11P70 / 11B75 / 11B13

References

[1] Alon N, Nathanson MB, Ruzsa I. The polynomial method and restricted sums of congruence classes. J. Number Theory, 1996, 56(2): 404-417

[2] Bajnok B. On the minimum size of restricted sumsets in cyclic groups. Acta Math. Hungar., 2016, 148(1): 228-256

[3] Bajnok B. Additive combinatorics—A menu of research problems. Discrete Mathematics and Its Applications (Boca Raton), 2018, Boca Raton, FL, CRC Press

[4] Bajnok B, Berson C, Just H. On perfect bases in finite abelian groups. Involve, 2022, 15(3): 525-536

[5] Bajnok B, Edwards S. On two questions about restricted sumsets in finite abelian groups. Australas. J. Combin., 2017, 68: 229-244

[6] Bajnok B., Matzke R., The minimum size of signed sumsets. Electron. J. Combin., 2015, 22 (2): Paper No. 2.50, 17 pp.

[7] Bajnok B, Matzke R. On the minimum size of signed sumsets in elementary abelian groups. J. Number Theory, 2016, 159: 384-401

[8] Bajnok B., Ruzsa I., The independence number of a subset of an abelian group. Integers, 2003, 3: Paper No. A2, 23 pp.

[9] Balandraud É. An addition theorem and maximal zero-sum free sets in ℤ/pℤ. Israel J. Math., 2012, 188: 405-429

[10] Bhanja J, Komatsu T, Pandey RK. Direct and inverse problems for restricted signed sumsets in integers. Contrib. Discrete Math., 2021, 16(1): 28-46

[11] Bhanja J, Pandey RK. Direct and inverse theorems on signed sumsets of integers. J. Number Theory, 2019, 196: 340-352

[12] Bhanja J, Pandey RK. On the minimum size of subset and subsequence sums in integers. C. R. Math. Acad. Sci. Paris, 2022, 360: 1099-1111

[13] Cauchy A-L. Recherches sur les nombres. J. École Polytech., 1813, 9: 99-116

[14] Davenport H. On the addition of residue classes. J. London Math. Soc., 1935, 10(1): 30-32

[15] Daza D, Huicochea M, Martos C, Trujillo C. A Freiman-type theorem for restricted sumsets. Int. J. Number Theory, 2023, 19(10): 2309-2332

[16] Dias da Silva JA, Hamidoune YO. Cyclic spaces for Grassmann derivatives and additive theory. Bull. London Math. Soc., 1994, 26(2): 140-146

[17] Du S., Pan H., The restricted sumsets in finite abelian groups. 2024, arXiv:2403.03549

[18] Dwivedi H., Mistri R., Direct and inverse problems for subset sums with certain restrictions. Integers, 2022, 22: Paper No. A112, 13 pp.

[19] Eliahou S, Kervaire M, Plagne A. Optimally small sumsets in finite abelian groups. J. Number Theory, 2003, 101(2): 338-348

[20] Erdös P, Graham RL. Old and New Problems and Results in Combinatorial Number Theory, 1980, Geneva, L’Enseignement Mathématique, Université de Genève28

[21] Freǐman GA. On the addition of finite sets I. Izv. Vysh. Uchebn. Zaved. Mat., 1959, 13(6): 202-213

[22] Freǐman GA. Foundations of a Structural Theory of Set Addition, 1973, Providence, RI, American Mathematical Society37

[23] Freǐman GA, Low L, Pitman J. Sumsets with distinct summands and the Erdős-Heilbronn conjecture on sums of residues. Astérisque, 1999, 258: 163-172

[24] Grynkiewicz D. A step beyond Kemperman’s structure theorem. Mathematika, 2009, 55(1–2): 67-114

[25] Grynkiewicz D. Iterated sumsets and subsequence sums. J. Combin. Theory Ser. A, 2018, 160: 136-167

[26] Károlyi G. An inverse theorem for the restricted set addition in abelian groups. J. Algebra, 2005, 290(2): 557-593

[27] Kemperman JHB. On small sumsets in an abelian group. Acta Math., 1960, 103: 63-88

[28] Klopsch B, Lev VF. How long does it take to generate a group? J. Algebra, 2003, 261(1): 145-171

[29] Klopsch B, Lev VF. Generating abelian groups by addition only. Forum Math., 2009, 21(1): 23-41

[30] Lev VF. Restricted set addition in groups, I. The classical setting. J. London Math. Soc. (2), 2000, 62(1): 27-40

[31] Mohan, Bhanja J., Pandey R.K., Freiman’s (3k−4)-like results for subset and subsequence sums, 2024, arXiv.2401.08208

[32] Mohan, Mistri R., Pandey R.K., Some direct and inverse problems for the restricted signed sumset in the set of integers. Integers, 2024, 24: Paper No. A81, 36 pp.

[33] Mohan, Pandey RK. Extended inverse theorems for h-fold sumsets in integers. Contrib. Discrete Math., 2023, 18(2): 129-145

[34] Mohan, Pandey RK. Extended inverse theorems for restricted sumset in integers. Bull. Korean Math. Soc., 2024, 61(5): 1339-1367

[35] Nathanson M. Inverse theorems for subset sums. Trans. Amer. Math. Soc., 1995, 347(4): 1409-1418

[36] Nathanson M. Additive Number Theory—Inverse Problems and the Geometry of Sumsets, 1996, New York, Springer-Verlag 165

[37] Sun C, She M. Some inverse problems for restricted signed sumsets in integers. Chinese Ann. Math. Ser. A, 2024, 45(3): 259-274

[38] Tang M, Wang W. Some remarks on sumsets and restricted sumsets. Bull. Korean Math. Soc., 2019, 56(3): 667-673

[39] Tang M, Wei M. Some remarks on a conjecture of Freiman and Lev. Adv. Math. (China), 2023, 52(1): 53-61

[40] Tang M, Xing Y. Some inverse results of sumsets. Bull. Korean Math. Soc., 2021, 58(2): 305-313

[41] Wang Y, Tang M. On the Freiman–Lev conjecture. Contrib. Discrete Math., 2025, 20(1): 42-59

[42] Wang Y., Tang M., Freiman–Lev conjecture. Sci. Sin. Math., 2025, https://doi.org/10.1360/SSM-2024-0249 (in Chinese)

[43] Xing Y. The study of the cardinalities of sumsets, 2020, Wuhu, Anhui Normal University

RIGHTS & PERMISSIONS

Peking University