# A nonlinear bound
for the number of subsequence sums

Vsevolod F. Lev<EMAIL_ADDRESS>Department of Mathematics, The
University of Haifa at Oranim, Tivon 36006, Israel

###### Abstract.

We show that a finite zero-sum-free sequence $\alpha$ over an abelian group
has at least $c|\alpha|^{4/3}$ distinct subsequence sums, unless $\alpha$ is
“controlled” by a small number of its terms; here $|\alpha|$ denotes the
number of terms of $\alpha$, and $c>0$ is an absolute constant.

###### Key words and phrases:

Zero-sum-free sequences, Minimal zero-sum sequences, Subset sums, Inverse
zero-sum problems, Hilbert cube

###### 2020 Mathematics Subject Classification:

Primary 11P70; Secondary 11B13, 11B75

##  1\. Background and motivation

A classical object of study of the combinatorial number theory is the
Davenport constant of a finite abelian group, defined to be the smallest
integer $n$ such that every $n$-term sequence of group elements is guaranteed
to have a nonempty subsequence with the zero sum of its terms. According to
Olson [O69a], the problem of finding this group invariant was raised by
Davenport at the Midwestern Conference on Group Theory and Number Theory held
in the Ohio State University in April 1966, in connection with the
investigation of the class groups of the algebraic number fields. However,
this exact problem has been considered three years earlier by Rogers [Ro63]
who, in turn, refers to a personal communication with C. Sudler. Other early
papers where this or related problems are studied include [EBK67, B68, EB69,
O69b].

The precise value of the Davenport constant is still unknown in general,
despite a large number of partial results. Eggleton and Erdős [EE72, Theorem
3] have shown that if the underlying group $G$ is not cyclic, then its
Davenport constant does not exceed $(|G|+1)/2$; that is, if $\alpha$ is a
finite sequence free of nonempty zero-sum subsequences, then its length
satisfies $|\alpha|\leq|G|/2$. This was improved by Olson and White [OW77] who
proved that if $\alpha$ is free of nonempty zero-sum subsequences, then it has
at least $2|\alpha|$ distinct subsequence sums provided that the subgroup
generated by the elements of $\alpha$ is not cyclic; here the empty
subsequence with the zero sum is counted, too. Indeed, the result of Olson-
White applies to infinite and nonabelian groups as well.

Evidently, the reason for Eggleton-Erdős and Olson-White to ignore the cyclic
groups is that for these groups the Davenport constant is easily seen to be
equal to the order of the group. This simple fact suggests, nevertheless, an
interesting research avenue to explore: what is the structure of “long”
sequences free of nonempty zero-sum subsequences in the finite cyclic groups?

We introduce some basic terminology to proceed.

A finite sequence of elements of an abelian group is called _zero-sum-free_ if
all of its nonempty subsequences have a nonzero sum of their terms; the
sequence is _minimal zero-sum_ if the sum of all of its terms is zero, while
all of its nonempty proper subsequences have nonzero term sum. The two classes
of sequences are actually quite close to each other due to the observation
that removing any term from a minimal zero-sum sequence results in a zero-sum-
free sequence, and conversely, any zero-sum-free sequence can be turned into a
minimal zero-sum sequence by appending an appropriate group element to it.

Suppose that the underlying group $G$ is cyclic of finite order. Addressing
the above-mentioned problem, Gao [G00] characterized minimal zero-sum
sequences $\alpha$ of length $n:=|\alpha|>2|G|/3+O(1)$; specifically, for any
such sequence there is a generating element $g\in G$ and positive integers
$x_{1},\dotsc,x_{n}$ with $x_{1}+\dotsb+x_{n}=|G|$ such that the $n$ terms of
$\alpha$ are $x_{1}g,\dotsc,x_{n}g$. Savchev and Chen [SC07] and,
independently, Yuan [Y07] have shown that, indeed, Gao’s characterization
stays true for all zero-sum-free sequences of length $|\alpha|>|G|/2$. In [L],
these results are extended the same way the theorem of Olson-White extends the
result of Eggleton-Erdős; namely, [L, Theorem 2] shows that the assumption
$|\alpha|>|G|/2$ can be relaxed to $|\alpha|>|\Sigma(\alpha)|/2$, where
$\Sigma(\alpha)$ is the set of all subsequence sums of $\alpha$, including the
empty subsequence.

A significant further progress was made by Savchev and Chen [SC17] who have
introduced a subtle and involved argument to classify minimal zero-sum
sequences $\alpha$ in a finite cyclic group $G$, given that
$|\alpha|\geq\left\lfloor|G|/3\right\rfloor+3$. As shown in [SC17], under this
assumption there exist group elements $u\neq 0$ and $v$ satisfying a number of
conditions such that all terms or $\alpha$ are contained either in the
subgroup $\langle u\rangle$ generated by $u$, or in the coset $v+\langle
u\rangle$. We omit the (somewhat technical) exact statement of this result
referring the interested reader to [SC17] instead.

##  2\. The main result

In this section we use the notation which will not be introduced formally
until Section 3. We believe, however, that our notation is standard enough to
not cause any discomfort to the reader. Nevertheless, it may be worth
remarking that $\Sigma(\alpha)$ denotes the set of _all_ subsequence sums of
the sequence $\alpha$, including the empty subsequence, while
$\Sigma^{\scriptscriptstyle{\times}}(\alpha)$ is defined the same way, except
that the empty subsequence is ignored; say, if $\alpha$ is the sequence of
integers containing one term equal to $-3$ and two terms equal to $2$, then
$\Sigma(\alpha)=\\{-3,-1,0,1,2,4\\}$, while
$\Sigma^{\scriptscriptstyle{\times}}(\alpha)=\\{-3,-1,1,2,4\\}$. By
$\operatorname{supp}(\alpha)$ we denote the set of all terms of $\alpha$, and
by $|\alpha|$ the length (that is, the number of terms) of $\alpha$.

The aim of the present paper is to go beyond the Savchev-Chen bound
$|\alpha|\geq\left\lfloor|G|/3\right\rfloor+3$.

######  Theorem 1.

Suppose that $C\geq 2$ is an integer, and $\alpha$ is a zero-sum-free sequence
of length $n:=|\alpha|\geq(4C)^{3}$ over an abelian group. If
$|\Sigma(\alpha)|<Cn-C^{2}\sqrt{6n}$, then there are an integer
$h>n-C\sqrt{6n}$ and an element $a\in\operatorname{supp}(\alpha)$ of order
$\operatorname{ord}(a)>h+1$ such that, letting $P:=\\{a,2a,,\dotsc,ha\\}$, we
have
$\Sigma(\operatorname{supp}(\alpha))+P\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha)$.

Moreover, there is a set $X\subseteq\Sigma(\operatorname{supp}(\alpha))$ with
$0\in X$ and $|X|\leq C-1$ such that
$\Sigma(\operatorname{supp}(\alpha))\subseteq X+P-P$; in particular, each term
of $\alpha$ can be written as $x+ta$ with an element $x\in X$ and an integer
$t\in[-(h-1),h-1]$.

######  Remark 1.

The arithmetic progression $P-P=\\{-(h-1)a,\dotsc,(h-1)a\\}$ can be considered
as a “local approximation” to the subgroup $\langle a\rangle$ generated by
$a$. The assertion of the theorem remains true, but becomes weaker with $P-P$
replaced by $\langle a\rangle$.

######  Remark 2.

The translates $x+P-P$ with $x\in X$ are not guaranteed to be pairwise
disjoint, but it is immediate from the proof that the translates $x+P$ are
disjoint.

######  Remark 3.

The bound $|X|\leq C-1$ is best possible. To see this, fix a positive integer
$s$, set $C:=2^{s}+1$, choose linearly independent vectors
$e_{0},e_{1},\dotsc,e_{s}$ in a vector space over a field of characteristic
$0$, and consider the sequence $\alpha=e_{0}^{n-s}e_{1}\dotsb e_{s}$. We have

$\Sigma(\alpha)=\\{x_{1}e_{1}+\dotsb+x_{s}e_{s}+te_{0}\colon
x_{1},\dotsc,x_{s}\in\\{0,1\\},\ 0\leq t\leq n-s\\}$

whence

$|\Sigma(\alpha)|=2^{s}(n-s+1)=(C-1)n-(C-1)(s-1)<Cn-C^{2}\sqrt{6n}$

provided that $n$ is sufficiently large. On the other hand, one cannot find an
arithmetic progression $P$ and a set $X$ of size $|X|\leq C-2=2^{s}-1$ such
that $\Sigma(\operatorname{supp}(\alpha))\subseteq X+P$ since the right-hand
side is contained in a system of $|X|$ lines, each of them covering at most
two vertices of the $(s+1)$-dimensional cube $\Sigma(e_{0}e_{1}\dotsb
e_{s})=\Sigma(\operatorname{supp}(\alpha))$.

######  Remark 4.

The assumptions $n\geq(4C)^{3}$ and $|\Sigma(\alpha)|<Cn-C^{2}\sqrt{6n}$
essentially mean that our result applies to zero-sum-free sequences satisfying
$|\Sigma(\alpha)|<\frac{1}{4}|\alpha|^{4/3}$. Conjecturally, the former
assumption can be dropped or at least relaxed very significantly, and the
latter can be replaced with the weaker $|\Sigma(\alpha)|\leq Cn-(C-1)^{2}$. If
true, this is best possible as it follows by considering the sequence
$\alpha:=g_{1}^{n-C+1}g_{2}^{C-1}$, where $g_{1}$ and $g_{2}$ are independent
group elements; in this example (originating from [L99, Examples 1 and 2]) we
have $|\Sigma(\alpha)|=Cn-(C-1)^{2}+1$, while $\Sigma(\alpha)$ is not a union
of $C-1$ or less arithmetic progressions with the same difference.

Some minor adjustments of the constants can be obtained by fine-tuning our
calculations, but we prefer instead to keep the argument clean and reasonably
simple.

######  Remark 5.

Theorem 1 markedly lacks the precision of the result of Savchev and Chen, the
latter establishing a necessary and sufficient condition for $\alpha$ to be
minimal zero-sum under the assumption
$|\alpha|\geq\left\lfloor|G|/3\right\rfloor+3$, where $G$ is the underlying
group. On the other hand, Theorem 1 is not restricted to the coefficient
$C=3$, allowing $C$ to be _any_ positive integer. Also, the assumption
$|\Sigma(\alpha)|<C(1+o(1))|\alpha|$ is substantially weaker than the
assumption $|\alpha|>(C^{-1}+o(1))|G|$. Finally, our result applies to any
abelian group, not necessarily finite or cyclic. As explained in [SC17], the
extension from the finite cyclic to arbitrary abelian groups is meaningless in
the situation where $|\alpha|\geq\left\lfloor|G|/3\right\rfloor+3$; however,
it makes perfect sense in the settings of Theorem 1.

We now briefly outline the idea behind the proof.

The crucial role is played by the transfer operation introduced in Section 5.
The operation modifies a given sequence $\alpha$ so that, in particular, the
subsequence sum set $\Sigma(\alpha)$ does not increase, while the length
$|\alpha|$ either increases, or stays the same, but in the latter case the
sequence $\alpha$ becomes, loosely speaking, “more concentrated”. Moreover,
the support $\operatorname{supp}(\alpha)$ stays unchanged, and the property of
being zero-sum-free is preserved. Having applied the transfer operation
sufficiently many times, we finally reach a zero-sum-free sequence which is
stable under further applications of the operation. This resulting stable
sequence turns out to contain a term of very large multiplicity, making it
easier to analyze than a “generic” zero-sum-free sequence, and its relation to
the original sequence $\alpha$ is strong enough to read off the properties of
the latter from those of the former.

We introduce the notation used in the next section. Three basic results needed
for the proof of Theorem 1 are quoted in Section 4. In Section 5 we define the
transfer operation and study its properties. Theorem 1 is proved in the
concluding Section 6.

##  3\. Notation

From now on, by a _sequence_ we mean a finite sequence of elements of an
abelian group. Informally, a sequence is an unordered list of the group
elements, with repetitions allowed. Formally, sequences are elements of the
abelian monoid freely generated by the elements of the group. We use
multiplicative notation for the monoid operation; thus, for instance, the
“concatenation” of the sequences $\alpha_{1},\dotsc,\alpha_{k}$ is the product
sequence $\alpha_{1}\dotsb\alpha_{k}$.

Up to the order of the factors, every sequence $\alpha$ can be uniquely
written in the form $\alpha=a_{1}^{m_{1}}\dotsb a_{s}^{m_{s}}$ where $s\geq 0$
is an integer, $a_{1},\dotsc,a_{s}$ are pairwise distinct group elements, and
$m_{1},\dotsc,m_{s}$ are positive integers. The elements $a_{i}$ are called
the _terms_ of $\alpha$, and the integers $m_{i}$ are the _multiplicities_ of
the corresponding terms. Alternatively, the terms of $\alpha$ are group
elements dividing $\alpha$, and the multiplicity of a group element $a$ in
$\alpha$, denoted $\nu_{\alpha}(a)$ below, is the largest integer $m\geq 0$
such that $a^{m}\mid\alpha$.

For a nonempty sequence $\alpha$, by ${\mathsf{H}}(\alpha)$ we denote the
largest multiplicity of a term of $\alpha$: that is,
${\mathsf{H}}(\alpha)=\max\\{\nu_{\alpha}(a)\colon a\mid\alpha\\}$. More
generally, by ${\mathsf{H}}_{k}(\alpha)$ we denote the $k$th largest
multiplicity of a term of $\alpha$; thus,
${\mathsf{H}}(\alpha)={\mathsf{H}}_{1}(\alpha)$. By convention,
${\mathsf{H}}_{k}(\varnothing)=0$ for all $k\geq 1$.

The _length_ of $\alpha$ is defined by $|\alpha|:=m_{1}+\dotsb+m_{s}$. We also
let $|\alpha|_{2}:={m_{1}}^{2}+\dotsb+m_{s}^{2}$.

The set $\\{a_{1},\dotsc,a_{s}\\}$ is called the _support_ of $\alpha$ and
denoted $\operatorname{supp}(\alpha)$; therefore,
$s=|\operatorname{supp}(\alpha)|$, and for a group element $a$, we have
$a\mid\alpha$ if and only if $a\in\operatorname{supp}(\alpha)$, meaning that
$a$ is a term of $\alpha$.

_Subsequences_ of $\alpha$ are sequences $\alpha^{\prime}$ with
$\alpha^{\prime}\mid\alpha$. Writing $\alpha=a_{1}^{m_{1}}\dotsb
a_{s}^{m_{s}}$ with $s,a_{i}$, and $m_{i}$ as above, $\alpha^{\prime}$ is a
subsequence of $\alpha$ if and only if
$\alpha^{\prime}=a_{1}^{m_{1}^{\prime}}\dotsb a_{s}^{m_{s}^{\prime}}$ where
$0\leq m_{i}^{\prime}\leq m_{i}$ for all $i=1,\dotsc,s$.

We denote by $\sigma(\alpha)$ the sum of all terms of $\alpha$ with
multiplicities counted: $\sigma(\alpha)=m_{1}a_{1}+\dotsb+m_{s}a_{s}$.

The subsequence sum set of $\alpha$ is the set

$\Sigma(\alpha):=\\{\sigma(\alpha^{\prime})\colon\alpha^{\prime}\mid\alpha\\}.$

We also write

$\Sigma^{\scriptscriptstyle{\times}}(\alpha):=\\{\sigma(\alpha^{\prime})\colon\alpha^{\prime}\mid\alpha,\
\alpha^{\prime}\neq\varnothing\\};$

thus, $\Sigma^{\scriptscriptstyle{\times}}(\varnothing)=\varnothing$ and
$\Sigma(\alpha)=\Sigma^{\scriptscriptstyle{\times}}(\alpha)\cup\\{0\\}$. The
sequence $\alpha$ is _zero-sum-free_ if it does not have a nonempty zero-sum
subsequence; that is, if $0\notin\Sigma^{\scriptscriptstyle{\times}}(\alpha)$.

For subsets $A_{1},\dotsc,A_{k}$ of an abelian group, we let

$A_{1}+\dotsb+A_{k}:=\\{a_{1}+\dotsb+a_{k}\colon a_{1}\in
A_{1},\dotsc,a_{k}\in A_{k}\\}$

and

$A_{i}-A_{j}:=\\{a_{i}-a_{j}\colon a_{i}\in A_{i},\ a_{j}\in A_{j}\\}.$

The subgroup generated by a group element $g$ is denoted by $\langle
g\rangle$, and the order of $g$ by $\operatorname{ord}(g)$.

##  4\. Basic Facts

We need the following, well-known, lower-bound estimates for the size of the
subsequence sum set of a zero-sum-free sequence.

######  Lemma 1 ([SF01, Theorem 2.5]; see also [GH06, Proposition 5.3.5]).

If $\alpha$ is a finite zero-sum-free sequence over an abelian group, then

$|\Sigma(\alpha)|\geq
2|\alpha|-{\mathsf{H}}(\alpha)+1\geq|\alpha|+|\operatorname{supp}(\alpha)|.$

######  Lemma 2 ([BEN75, Proof of Lemma 1]; see also [GH06, Theorem 5.3.1]).

Suppose that $k$ is a positive integer, and
$\alpha=\alpha_{1}\dotsb\alpha_{k}$ is a factorization of a finite, zero-sum-
free sequence $\alpha$ over an abelian group. Then

$|\Sigma(\alpha)|\geq|\Sigma(\alpha_{1})|+\dotsb+|\Sigma(\alpha_{k})|-(k-1).$

######  Lemma 3 ([GHHLLP20, Theorem 1.1]).

If A is a finite, zero-sum-free _subset_ of an abelian group (so that
${\mathsf{H}}(A)=1$), then $|\Sigma(A)|\geq 1+\frac{1}{6}\,|A|^{2}$.

##  5\. The transfer operation

A simple construction presented in Section 6 after the statement of Lemma 7
shows that a zero-sum-free sequence $\alpha$ with about $C|\alpha|$
subsequence sums may fail to contain a term of multiplicity larger than,
roughly, $|\alpha|/C$. The machinery of transfer operation developed in this
section supplies a sort of a poor man’s compensation for the lack of high-
multiplicity terms.

Throughout this section, $\alpha$ is a finite sequence of elements of an
abelian group of length $n:=|\alpha|$, written as $\alpha=a_{1}^{m_{1}}\dotsc
a_{s}^{m_{s}}$ where $s\geq 2$, the terms $a_{1},\dotsc,a_{s}$ are pairwise
distinct, and the exponents $m_{1},\dotsc,m_{s}$ are positive integers.

######  Lemma 4.

Suppose that $i,j\in[1,s],\ i\neq j$, and $v<m_{j}$ is a positive integer.
Consider the sequence
$\alpha^{\prime}=a_{1}^{m_{1}^{\prime}}\dotsb\alpha_{s}^{m_{s}^{\prime}}$
defined by $m^{\prime}_{i}=m_{i}+v$, $m_{j}^{\prime}=m_{j}-v$, and
$m_{k}^{\prime}=m_{k}$ for $k\in[1,s]\setminus\\{i,j\\}$. Then
$|\alpha^{\prime}|_{2}>|\alpha|_{2}$ if and only if $v>m_{j}-m_{i}$.

###### Proof.

It suffices to notice that the inequality
$(m_{i}+v)^{2}+(m_{j}-v)^{2}>m_{i}^{2}+m_{j}^{2}$ reduces to $v>m_{j}-m_{i}$.
∎

Fix indices $i,j\in[1,s]$ with $i\neq j$ and write
$\alpha=a_{i}^{m_{i}}a_{j}^{m_{j}}\rho$ where $\rho$ is a sequence with
$a_{i},a_{j}\notin\operatorname{supp}(\rho)$. If there exist positive integers
$u\leq m_{i}+1$ and $v\leq m_{j}-1$ such that $ua_{i}=va_{j}$, and either
$u>v$, or $u=v>m_{j}-m_{i}$, then we say that the sequence
$a_{i}^{m_{i}+u}a_{j}^{m_{j}-v}\rho$ is obtained from the original sequence
$\alpha$ by the transfer operation. We also say in this case that the
(ordered) pair $(i,j)$ is _unstable_. If $u$ and $v$ with the specified
properties do not exist, then we say that $(i,j)$ is _stable_. If both $(i,j)$
and $(j,i)$ are stable pairs, then we say that the set $\\{i,j\\}$ is stable.
Finally, we say that the original sequence $\alpha$ is stable if all ordered
pairs $(i,j)$ are stable; equivalently, if all two-element subsets
$\\{i,j\\}\subseteq[1,s]$ are stable.

We remark that the inequality $v\leq m_{j}-1$ ensures that
$\operatorname{supp}(\alpha)$ is not affected by the transfer operation, while
the condition $u\leq m_{i}+1$ is needed to guarantee that the set
$\Sigma^{\scriptscriptstyle{\times}}(\alpha)$ of subsequence sums does not
increase; see Lemma 6 below.

######  Lemma 5.

Suppose that $i,j\in[1,s],\ i\neq j$.

  * (i)

If $m_{i}\geq m_{j}$, then for the pair $(i,j)$ to be unstable it is necessary
and sufficient that there exist positive integers $u\leq m_{i}+1$ and $v\leq
m_{j}-1$ such that $ua_{i}=va_{j}$ and $u\geq v$.

  * (ii)

For the pair $(j,i)$ to be unstable it is necessary and sufficient that there
exist positive integers $u\leq m_{i}-1$ and $v\leq m_{j}+1$ such that
$ua_{i}=va_{j}$ and either $u<v$, or $u=v>m_{i}-m_{j}$.

###### Proof.

The first assertion follows directly from the definition of a stable pair. The
second assertion is the definition of an unstable pair in disguise, which is
immediately seen by interchanging $i$ and $j$ and, simultaneously, $u$ and
$v$. ∎

######  Corollary 1.

Suppose that $i,j\in[1,s],\ i\neq j$, and $m_{i}\geq m_{j}$. If there exist
positive integers $u\leq m_{i}+1$ and $v\leq m_{j}-1$ such that
$ua_{i}=va_{j}$, then $\\{i,j\\}$ is unstable.

###### Proof.

Suppose that $u\leq m_{i}+1$ and $v\leq m_{j}-1$ satisfy $ua_{i}=va_{j}$. If
$u\geq v$, then $(i,j)$ is unstable by Lemma 5 (i). If $u<v$ then
$u<m_{j}-1\leq m_{i}-1$ and $(j,i)$ is unstable by Lemma 5 (ii). ∎

For $j\in[1,s]$, we write $P_{j}:=\\{0,a_{j},2a_{j},\dotsc,m_{j}a_{j}\\}$ and
$P_{j}^{\prime}:=\\{0,a_{j},2a_{j},\dotsc,(m_{j}-1)a_{j}\\}$. Notice that if
$\alpha$ is zero-sum-free, then $|P_{j}|=m_{j}$.

######  Corollary 2.

Suppose that $i,j\in[1,s],\ i\neq j$, and $m_{i}\geq m_{j}$. If $\\{i,j\\}$ is
stable, then $P_{i}\cap P_{j}^{\prime}=\\{0\\}$.

###### Proof.

If $P_{i}$ and $P_{j}^{\prime}$ share a common element $g\neq 0$, then there
exist positive integers $u\leq m_{i}$ and $v\leq m_{j}-1$ such that $g=ua_{i}$
and $g=va_{j}$. Therefore $ua_{i}=va_{j}$ and $\\{i,j\\}$ is unstable by
Corollary 1. ∎

######  Corollary 3.

Suppose that $\alpha$ is zero-sum-free, and that $i,j\in[1,s],\ i\neq j$, and
$m_{i}\geq m_{j}$. If $\\{i,j\\}$ is stable, then
$|P_{i}+P_{j}^{\prime}|=(m_{i}+1)m_{j}$ and, consequently,
$|\Sigma(\alpha)|\geq(m_{i}+1)m_{j}$.

###### Proof.

It suffices to show that all sums $ua_{i}+va_{j}$ with $u\in[0,m_{i}]$,
$v\in[0,m_{j}-1]$ are pairwise distinct. To this end, suppose that
$u^{\prime}a_{i}+v^{\prime}a_{j}=u^{\prime\prime}a_{i}+v^{\prime\prime}a_{j}$
with $u^{\prime},u^{\prime\prime}\in[0,m_{i}]$ and
$v^{\prime},v^{\prime\prime}\in[0,m_{j}-1]$. Then, letting
$u:=u^{\prime\prime}-u^{\prime}$ and $v:=v^{\prime}-v^{\prime\prime}$, we have
$ua_{i}=va_{j}$ where $|u|\leq m_{i}$ and $|v|\leq m_{j}-1$. If $u$ and $v$
are distinct from $0$, then they are of the same sign since $\alpha$ is zero-
sum-free; without loss of generality, both are positive, and then the equality
$ua_{i}=va_{j}$ contradicts Corollary 1. ∎

######  Corollary 4.

Suppose that $\alpha$ is zero-sum-free, and that $i,j\in[1,s]$, $i\neq j$,
$m_{i}={\mathsf{H}}_{1}(\alpha)$, and $m_{j}={\mathsf{H}}_{2}(\alpha)$. If
$\\{i,j\\}$ is stable, then $|\Sigma(\alpha)|-2n\geq(m_{i}-2)(m_{j}-2)-2$.

###### Proof.

Let $\rho$ be the sequence defined by
$\alpha=a_{i}^{m_{i}}a_{j}^{m_{j}-1}\rho$. By Corollary 3 and Lemmas 2 and 1,
and in view of ${\mathsf{H}}(\rho)\leq m_{j}$,

$\displaystyle|\Sigma(\alpha)|$
$\displaystyle\geq|\Sigma(a_{i}^{m_{i}}a_{j}^{m_{j}-1})|+|\Sigma(\rho)|-1$
$\displaystyle\geq|P_{i}+P_{j}^{\prime}|+(2(n-m_{i}-(m_{j}-1))-m_{j}+1)-1$
$\displaystyle=(m_{i}+1)m_{j}+2n-2m_{i}-3m_{j}+2$
$\displaystyle=m_{i}m_{j}-2m_{i}-2m_{j}+2+2n$
$\displaystyle=(m_{i}-2)(m_{j}-2)-2+2n.$

∎

######  Lemma 6.

If $\alpha^{\prime}$ is obtained from $\alpha$ by a series of subsequent
transfer operations, then

$\Sigma^{\scriptscriptstyle{\times}}(\alpha^{\prime})\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha),\
\operatorname{supp}(\alpha^{\prime})=\operatorname{supp}(\alpha),$

and

either $|\alpha^{\prime}|>|\alpha|$, or $|\alpha^{\prime}|=|\alpha|$ and
$|\alpha|_{2}<|\alpha^{\prime}|_{2}$.

###### Proof.

Without loss of generality, we assume that $\alpha^{\prime}$ is obtained from
$\alpha$ by just one transfer operation; say,
$\alpha=a_{i}^{m_{i}}a_{j}^{m_{j}}\rho$ and
$\alpha^{\prime}=a_{i}^{m_{i}+u}a_{j}^{m_{j}-v}\rho$ where $i,j\in[1,s]$,
$i\neq j$, $a_{i},a_{j}\notin\operatorname{supp}(\rho)$, $u\in[1,m_{i}+1]$,
$v\in[1,m_{j}-1]$, $ua_{i}=va_{j}$, and either $u>v$, or $u=v>m_{j}-m_{i}$. We
prove the inclusion
$\Sigma^{\scriptscriptstyle{\times}}(\alpha^{\prime})\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha)$;
the rest follows in a straightforward way from Lemma 4.

Comparing the identities

$\displaystyle\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}}a_{j}^{m_{j}}\rho)$
$\displaystyle=(\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}}a_{j}^{m_{j}})+\Sigma(\rho))\cup\Sigma^{\scriptscriptstyle{\times}}(\rho)$
and
$\displaystyle\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}+u}a_{j}^{m_{j}-v}\rho)$
$\displaystyle=(\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}+u}a_{j}^{m_{j}-v})+\Sigma(\rho))\cup\Sigma^{\scriptscriptstyle{\times}}(\rho),$

it suffices to show that
$\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}+u}a_{j}^{m_{j}-v})\subseteq\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}}a_{j}^{m_{j}})$.

Suppose thus that
$g\in\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}+u}a_{j}^{m_{j}-v})$ and
write $g=xa_{i}+ya_{j}$ where $x\in[0,m_{i}+u]$ and $y\in[0,m_{j}-v]$ are not
both equal to $0$. We show that
$g\in\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}}a_{j}^{m_{j}})$. Indeed,
the case $x\leq m_{i}$ is trivial, while if $x\geq m_{i}+1$, then
$x-u\in[0,m_{i}]$ and $y+v\in[1,m_{j}]$; consequently,
$g=(x-u)a_{i}+(y+v)a_{j}\in\Sigma^{\scriptscriptstyle{\times}}(a_{i}^{m_{i}}a_{j}^{m_{j}})$,
as wanted. ∎

If $\alpha$ and $\alpha^{\prime}$ are as in Lemma 6 and $\alpha$ is zero-sum-
free, then so is $\alpha^{\prime}$ in view of
$\Sigma^{\scriptscriptstyle{\times}}(\alpha^{\prime})\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha)$.
On the other hand, from
$|\alpha^{\prime}|\leq|\Sigma(\alpha^{\prime})|\leq|\Sigma(\alpha)|$ we
conclude that the possible lengths $|\alpha^{\prime}|$ are uniformly bounded;
therefore, in view of the second assertion of the lemma, having applied a
series of subsequent transfer operations to any given zero-sum-free sequence,
we eventually obtain a stable zero-sum-free sequence.

##  6\. Proof of Theorem 1

We start with a lemma establishing a number of relations between the length
and the largest multiplicities of the terms of a zero-sum-free sequence
$\alpha$ with a small number of subset sums; most importantly, the lemma shows
that if $\alpha$ is stable, then it has a term of very large multiplicity,
while all other terms have small multiplicities.

######  Lemma 7.

Suppose that $C\geq 2$ is an integer, and $\alpha$ is a zero-sum-free sequence
over an abelian group with $n:=|\alpha|\geq 2$. Let
$h_{1}:={\mathsf{H}}_{1}(\alpha)$ and $h_{2}:={\mathsf{H}}_{2}(\alpha)$. If
$|\Sigma(\alpha)|<Cn$, then

$\displaystyle h_{1}$ $\displaystyle>n^{2}/(6|\Sigma(\alpha)|)>n/(6C)$ (1) and
$\displaystyle h_{1}$
$\displaystyle>n-\sqrt{6h_{2}|\Sigma(\alpha)|}+h_{2}>n-\sqrt{6Cnh_{2}}+h_{2}.$
(2) If, moreover, $\alpha$ is stable, $n\geq(4C)^{3}$, and
$|\Sigma(\alpha)|<Cn-C^{2}\sqrt{6n}$, then $\displaystyle h_{2}$
$\displaystyle\leq C-1$ (3) and $\displaystyle h_{1}$
$\displaystyle>n-C\sqrt{6n}+1.$ (4)

We remark that only the last estimate of the lemma is used outside of the
lemma itself; however, we believe that the first three estimates can be useful
elsewhere, and for this reason we have included them into the statement.

Interestingly, the bound (1) is best possible save for the coefficient $1/6$.
To see this, fix integer numbers $k,s\geq 1$ and consider the sequence
$\alpha:=(g\cdot 2g\dotsb sg)^{k}$ where $g$ is a group element of
sufficiently large order. We have $n:=|\alpha|=ks$, ${\mathsf{H}}(\alpha)=k$,
and

$|\Sigma(\alpha)|=1+\frac{1}{2}s(s+1)\,k=\frac{1}{2}(s+1)n+1.$

Choosing $s:=2(C-1)$ we therefore get $|\Sigma(\alpha)|<Cn$ while
${\mathsf{H}}(\alpha)=n/s=n/(2C-2)$.

###### Proof of Lemma 7.

For an integer $k\in[1,h_{1}]$, let $A_{k}$ be the set of all terms of
$\alpha$ of multiplicity at least $k$:

$A_{k}:=\\{a\in\operatorname{supp}(\alpha)\colon\nu_{\alpha}(a)\geq k\\};$

thus, $\operatorname{supp}(\alpha)=A_{1}\supseteq A_{2}\supseteq\dotsb$.
Observing that $\alpha$ factors as $\alpha=A_{1}\dotsb A_{h_{1}}$, by Lemma 2
we get

$|\Sigma(\alpha)|\geq|\Sigma(A_{1})|+\dotsb+|\Sigma(A_{h_{1}})|-h_{1}+1.$

Since each of $A_{1},\dotsc,A_{h_{1}}$ has all its elements pairwise distinct,
Lemma 3 applies to give $|\Sigma(A_{i})|\geq\frac{1}{6}|A_{i}|^{2}+1$,
$i\in[1,h_{1}]$. Hence,

$|\Sigma(\alpha)|>\frac{1}{6}\,(|A_{1}|^{2}+\dotsb+|A_{h_{1}}|^{2})\geq\frac{1}{6h_{1}}(|A_{1}|+\dotsb+|A_{h_{1}}|)^{2}=\frac{n^{2}}{6h_{1}},$

which proves (1).

To prove (2) we notice that if $h_{2}=h_{1}$, then the first inequality of (2)
is identical to the first inequality of (1), while otherwise there is a unique
element $a\in\operatorname{supp}(\alpha)$ of multiplicity $h_{1}$, and we have
$A_{h_{2}+1}=\dotsb=A_{h_{1}}=\\{a\\}$. Therefore, in the latter case, arguing
as above,

$\displaystyle|\Sigma(\alpha)|$
$\displaystyle>\frac{1}{6}\,(|A_{1}|^{2}+\dotsb+|A_{h_{2}}|^{2})$
$\displaystyle\geq\frac{1}{6h_{2}}\,(|A_{1}|+\dotsb+|A_{h_{2}}|)^{2}$
$\displaystyle=\frac{1}{6h_{2}}\,(n-h_{1}+h_{2})^{2};$

this proves (2).

We now assume that $\alpha$ is stable and $n\geq(4C)^{3}$, and prove (3) and
(4). We notice that, in view of (2), if (3) holds true, then so does (4), and
we thus assume that (3) fails to hold; that is, $h_{2}\geq C$.

By Corollaries 4 and 3 we have

$\displaystyle|\Sigma(\alpha)|-2n$ $\displaystyle\geq(h_{1}-2)(h_{2}-2)-2$ (5)
and $\displaystyle(h_{1}+1)h_{2}$ $\displaystyle\leq|\Sigma(\alpha)|<Cn.$ (6)

Combining (1) and (6) we obtain $h_{2}<6C^{2}$, and then

$h_{1}>n-\sqrt{36C^{3}n}>\frac{1}{4}\,n$

by (2) and the assumption $n\geq(4C)^{3}$. Reusing (6), we now get $h_{2}<4C$.
On the other hand, from (5) and (2),

$|\Sigma(\alpha)|-2n\geq(n-\sqrt{6Cnh_{2}}+h_{2}-2)(h_{2}-2)-2.$ (7)

Considering $h_{2}$ as a variable ranging from $C$ to $4C$, the right-hand
side is a concave function of $h_{2}$ attaining at $h_{2}=C$ the value

$\displaystyle(n-C$ $\displaystyle\sqrt{6n}+C-2)(C-2)-2$ $\displaystyle\geq
Cn-2n-C(C-2)\sqrt{6n}-2$ $\displaystyle>Cn-C^{2}\sqrt{6n}-2n,$
$\displaystyle>|\Sigma(\alpha)|-2n$

and at $h_{2}=4C$ the value

$\displaystyle(n-2C$ $\displaystyle\sqrt{6n}+4C-2)(4C-2)-2$ $\displaystyle\geq
4Cn-8C^{2}\sqrt{6n}-2n$ $\displaystyle>Cn-2n$
$\displaystyle>|\Sigma(\alpha)|-2n.$

This shows that the right-hand side of (7) is larger than the left-hand side
for all $C\leq h_{2}\leq 4C$, a contradiction completing the proof of the
lemma. ∎

We are eventually ready to prove Theorem 1.

Suppose that $C\geq 2$ is an integer, and $\alpha$ is a zero-sum-free sequence
of length $n:=|\alpha|\geq(4C)^{3}$ satisfying
$|\Sigma(\alpha)|<Cn-C^{2}\sqrt{6n}$. We want to show that there are an
integer $n-C\sqrt{6n}<h<n$, an element $a\in\operatorname{supp}(\alpha)$ of
order $\operatorname{ord}(a)>h+1$, and a set
$X\subseteq\Sigma(\operatorname{supp}(\alpha))$ with $0\in X$ and $|X|\leq
C-1$, such that
$\Sigma(\operatorname{supp}(\alpha))+P\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha)$
and $\Sigma(\operatorname{supp}(\alpha))\subseteq X+P-P$, where
$P=\\{a,2a,\dotsc,ha\\}$.

Consider a stable sequence $\alpha^{\prime}$ obtained from $\alpha$ by a
series of transfer operations. By Lemma 6 we have
$\Sigma^{\scriptscriptstyle{\times}}(\alpha^{\prime})\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha)$,
$\operatorname{supp}(\alpha^{\prime})=\operatorname{supp}(\alpha)$, and
$n^{\prime}:=|\alpha^{\prime}|\geq n$; consequently, $\alpha^{\prime}$ is
zero-sum-free, and

$|\Sigma(\alpha^{\prime})|\leq|\Sigma(\alpha)|<Cn-C^{2}\sqrt{6n}\leq
Cn^{\prime}-C^{2}\sqrt{6n^{\prime}}.$

Notice also that $n^{\prime}\geq n\geq(4C)^{3}$. Let
$h^{\prime}:={\mathsf{H}}(\alpha^{\prime})$ be the largest multiplicity of a
term of $\alpha^{\prime}$. We define $h:=h^{\prime}-1$ and choose $a$ to be a
term of $\alpha^{\prime}$ of multiplicity
$\nu_{\alpha^{\prime}}(a)=h^{\prime}$. Thus,
$h>n^{\prime}-C\sqrt{6n^{\prime}}\geq n-C\sqrt{6n}$ by (4), and
$\operatorname{ord}(a)>h^{\prime}=h+1$ since $\alpha^{\prime}$ is zero-sum-
free.

The first assertion of the theorem is now immediate by observing that
$\alpha^{\prime}$ contains $a^{h}\cdot\operatorname{supp}(\alpha^{\prime})$ as
a subsequence, whence

$\Sigma(\operatorname{supp}(\alpha))+P=\Sigma(\operatorname{supp}(\alpha^{\prime}))+P\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha^{\prime})\subseteq\Sigma^{\scriptscriptstyle{\times}}(\alpha).$

To prove the second assertion we essentially apply the _Ruzsa covering lemma_
([Ru94], see also [TV06, Lemma 2.14]). Let $X$ be a maximal subset of
$\Sigma(\operatorname{supp}(\alpha))=\Sigma(\operatorname{supp}(\alpha^{\prime}))$
such that $0\in X$ and the translates $x+P$ with $x\in X$ are pairwise
disjoint. Then

$|X||P|=|X+P|\leq|\Sigma(\alpha^{\prime})|\leq|\Sigma(\alpha)|<Cn-C^{2}\sqrt{6n};$

in view of $|P|=h>n-C\sqrt{6n}$, this gives $|X|\leq C-1$.

On the other hand, by maximality of $X$, for any
$g\in\Sigma(\operatorname{supp}(\alpha))$ there exists $x\in X$ such that
$(x+P)\cap(g+P)\neq\varnothing$; that is, $g\in x+P-P$, showing that
$\Sigma(\operatorname{supp}(\alpha))\subseteq X+P-P$.

This completes the proof of Theorem 1.

## References

  * [B68] P.C. Baayen, A combinatorial problem for finite abelian groups. (Dutch) _Colloquium on Discrete Mathematics, Math. Centrum, Amsterdam_ (1968) 76–103, 107–108.
  * [BEN75] J. D. Bovey, P. Erdős, and I. Niven, Conditions for a zero sum modulo $n$, _Canad. Math. Bull._ 18 (1) (1975), 27–29.
  * [EB69] P. van Emde Boas, A combinatorial problem on finite abelian groups. II. _Math. Centrum Amsterdam Afd. Zuivere Wisk._ (1969), ZW-007, 60 pp.
  * [EBK67] P. van Emde Boas and D. Kruyswijk, A combinatorial problem on finite Abelian groups, _Math. Centrum Amsterdam Afd. Zuivere Wisk_ (1967), ZW-009, 27pp.
  * [EE72] R.B. Eggleton and P. Erdős, Two combinatorial problems in group theory, _Acta Arith._ 21 (1972) 111–116.
  * [G00] W.D. Gao, Zero sums in finite cyclic groups, _Integers_ 0 (2000), A12, 7 pp. (electronic).
  * [GH06] A. Geroldinger and F. Halter-Koch, _Non-unique factorizations, Algebraic, Combinatorial and Analytic Theory_ , Pure and Applied Mathematics 278 (2006), Chapman & Hall/CRC, London, Boca Raton, FL.
  * [GHHLLP20] W. Gao, M. Huang, W. Hui, Y. Li, C. Liu, and J. Peng, Sums of sets of abelian group elements, _J. Number Theory_ 208 (2020), 208–229.
  * [L99] V.F. Lev, The structure of multisets with a small number of subset sums, _Astèrisque_ 258 (1999), 179–186.
  * [L] V.F. Lev, Zero-sum-free sequences with few subsequence sums, _Submitted_.
  * [O69a] J.E. Olson, A combinatorial problem on finite Abelian groups, I, _J. Number Theory_ 1 (1969), 8–10.
  * [O69b] J.E. Olson, A combinatorial problem on finite Abelian groups, II., _J. Number Theory_ 1 (1969), 195–199.
  * [OW77] J.E. Olson and E.T. White, Sums from a sequence of group elements, _Number theory and algebra_ 215–222. Academic Press, New York, 1977.
  * [Ro63] K. Rogers, A combinatorial problem in abelian groups, _Proc. Camb. Phil. Soc._ 59 (1963), 559–562.
  * [Ru94] I. Ruzsa, Generalized arithmetical progressions and sumsets, _Acta Mathematica Hungarica_ 65 (4) (1994), 379–388.
  * [SC07] S. Savchev and F. Chen, Long zero-free sequences in finite cyclic groups, _Discrete Math._ 307 (22) (2007), 2671–2679.
  * [SC17] S. Savchev and F. Chen, An inverse problem about minimal zero-sum sequences over finite cyclic groups, _J. Number Theory_ 177 (2017), 381–427.
  * [SF01] W.W. Smith and M. Freeze, Sumsets of zerofree sequences, _Arab. J. Sci. Eng. Sect. C Theme Issues_ 26 (1) (2001), 97–105.
  * [TV06] T. Tao and V.H. Vu, _Additive Combinatorics_ , Cambridge Studies in Advanced Mathematics, 105. Cambridge University Press, Cambridge, 2006.
  * [Y07] P. Yuan, On the index of minimal zero-sum sequences over finite cyclic groups, _Journal of Combinatorial Theory, Series A_ 114 (2007), 1545–1551.