|
The number of $k$-sumsets in an Abelian group
A. A. Sapozhenko, V. G. Sargsyan Lomonosov Moscow State University, 1 Leninskie gory, 119991 Moscow, Russia
Abstract:
Let $G$ be an Abelian group of order $n$. The sum of subsets $A_1,\dots,A_k$ of $G$ is defined as the collection of all sums of $k$ elements from $A_1,\dots,A_k$; i.e., $A_1+\dots+A_k=\{a_1+\dots+a_k\mid a_1\in A_1,\dots, 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+\dots+ A_k$, where $A_1=A$ and $A_2=\dots=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,\dots,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|\geq n\log^qn$ and $|A_1+\dots+A_{i-1}+ A_{i+1}+\dots+A_k|\geq n\log^qn$, where $q=- 1/8$ and $i\in\{1,\dots,k\}$. Bibliogr. 8.
Keywords:
set, characteristic function, group, progression, coset.
Received: 29.01.2018 Revised: 13.06.2018
Citation:
A. A. Sapozhenko, V. G. Sargsyan, “The number of $k$-sumsets in an Abelian group”, Diskretn. Anal. Issled. Oper., 25:4 (2018), 97–111; J. Appl. Industr. Math., 12:4 (2018), 729–737
Linking options:
https://www.mathnet.ru/eng/da911 https://www.mathnet.ru/eng/da/v25/i4/p97
|
|