EN|RU
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:4, 729–737

Volume 25, No 4, 2018, P. 97-111

UDC 519.1
A. A. Sapozhenko and V. G. Sargsyan
The number of $k$-sumsets in an Abelian group

Abstract:
Let $G$ be an Abelian group of order $n$. The sum of subsets $A_1, \ldots , A_k$ of $G$ is defined as the collection of all sums of $k$ elements from $A_1, \ldots , A_k$; i. e., $A_1 + \cdots + A_k = {a_1 + \cdots + a_k | a_1 \in A_1, \ldots , a_k \in A_k}$. A subset representable as the sum of $k$ subsets of $G$ is a $k$-sumset. We consider the problem of the number of $k$-sumsets in an Abelian group $G$. It is obvious that each subset $A$ in $G$ is a $k$-sumset since $A$ is representable as $A = A_1 + \cdots + A_k$, where $A_1 = A$ and $A_2 = \cdots = A_k = {0}$. Thus, the number of $k$-sumsets is equal to the number of all subsets of $G$. But, if we introduce a constraint on the size of the summands $A_1, \ldots , A_k$ then the number of $k$-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of $k$-sumsets in Abelian groups are obtained provided that there exists a summand $A_i$ such that $|A_i| \ge n$ log$^{q} n$ and $|A_1 + \cdots + A_{i - 1} + A_{i+1} + \cdots + A_k| \ge n$ log$^{q} n$, where $q = -1/8$ and $i \in {1, \ldots , k}$.
Bibliogr. 8.

Keywords: set, characteristic function, group, progression, coset.

DOI: 10.17377/daio.2018.25.608

Aleksandr A. Sapozhenko 1
Vahe G. Sargsyan 1

1. Lomonosov Moscow State University,
1 Leninskie Gory, 119991 Moscow, Russia
e-mail: sapozhenko@mail.ru, vahe_sargsyan@ymail.com

Received 29 January 2018
Revised 13 June 2018

References

[1] V. G. Sargsyan, The number of differences in groups of prime order, Diskretn. Mat., 25, No. 1, 152–158, 2013 [Russian]. Translated in Discrete Math. Appl., 23, No. 2, 195–201, 2013.

[2] V. G. Sargsyan, Counting sumsets and differences in abelian group, Diskretn. Anal. Issled. Oper., 22, No. 2, 73–85, 2015 [Russian].

[3] A. Alon, Large sets in finite fields are sumsets, J. Number Theory, 126, 110–118, 2007.

[4] A. Alon, A. Granville and A. Ubis, The number of sumsets in a finite field, Bull. Lond. Math. Soc., 42, No. 5, 784–794, 2010.

[5] E. Croot and V. F. Lev, Open problems in additive combinatorics, in Additive Combinatorics, pp. 207–233, AMS, Providence, 2007 (CRM Proc. Lect. Notes, Vol. 43).

[6] B. Green, Essay submitted for Smith’s Prize, Camb. Univ., Cambridge, 2001.

[7] B. Green and I. Z. Ruzsa, Counting sumsets and sum-free sets modulo a prime, Stud. Sci. Math. Hung., 41, No. 3, 285–293, 2004.

[8] B. Green and I. Z. Ruzsa, Sum-free sets in abelian groups, Isr. J. Math., 147, 157–188, 2005.
 © Sobolev Institute of Mathematics, 2015