A logarithmic error term for subset sums of zero-sum-free sets

Introduction

Let $G$ be a finite abelian group, written additively. For a finite sequence $T$ over $G$, let $\Sigma_0(T)$ be the set of its subsequence sums, including the empty sum. When $T$ is a set, these are its subset sums. We call $T$ zero-sum-free if none of its nonempty subsequences has sum zero. For such a sequence, put

Thus $N(T)$ counts the distinct nonempty subsequence sums. We study

The distinction between sets and sequences is essential in this definition: the elements of $S$ must be distinct.

Eggleton and Erdős introduced this invariant and proved, in particular, that

see [2]. Olson obtained a quadratic lower bound with coefficient $1/9$ [5]. Gao, Huang, Hui, Li, Liu, and Peng subsequently proved the uniform estimate $f(k)\ge k^2/6$ [3 Theorem 1.1]. Our main result approaches the coefficient in (1) with a logarithmic loss per element.

The associated zero-sum threshold is the Olson constant $\operatorname{Ol}(G)$: the smallest positive integer $t$ such that every $t$-element subset of $G$ has a nonempty zero-sum subset.

Corollary 1.2. For every finite abelian group of order $n$,

In particular, $\operatorname{Ol}(G) \le\sqrt{2n} + O(\log n)$, uniformly in $G$.

Hamidoune and Zémor proved $\operatorname{Ol}(G) \le\sqrt{2|G|} + O(|G|^{1/3}\log|G|)$ [4 Theorem 4.5]. Thus the leading constant $\sqrt{2}$ in the Olson problem is classical. Corollary 1.2 reduces the error in that estimate to logarithmic order. Theorem 1.1 controls the actual number of subset sums; a bound on the ambient group order alone does not give this conclusion.

The proof has three parts. First, for every integer $r \ge2$, if $U$ is a set and the sequence containing $2r$ copies of every element of $U$ is zero-sum-free, then $r$ copies already have at least $r|U|(|U|+1)/2$ nonempty sums. Second, we combine blocks of two and three copies to count sums in a quotient whose multiplicities are almost equal. This yields an alternative for antisymmetric zero-sum-free sets: either the set already has at least half the square of its size in nonempty subset sums, or every proper iterated sum of its symmetrization satisfies the expansion bound in Proposition 5.1. Finally, a greedy argument converts this expansion into (1.2). Its stopping rule handles tails that generate a proper subgroup.

AI tools developed by OpenAI were used in this work.

Notation and additive tools

For a sequence $T=t_1\cdots t_\ell$, write $\sigma(T)=t_1+\cdots+t_\ell$, with $\sigma(\varnothing)=0$. For a subgroup $H\le G$, let $\pi_H:G\to G/H$ be the natural quotient map. For an integer $r\ge1$ and a set $U$, the notation $U^r$ denotes the sequence in which each element of $U$ occurs $r$ times. The sumset $rX$, by contrast, denotes $X+\cdots+X$, with repetitions allowed and exactly $r$ summands. Set

A set $C$ is antisymmetric if $C\cap(-C)=\varnothing$. A zero-sum-free set becomes antisymmetric after all its elements of order two have been removed.

For $B\subseteq G$, define its translation boundary by

We use

For $1\le j<|X|$, write $j\wedge X$ for the sums of $j$ distinct elements of $X$.

The following standard estimates will be used throughout:

and

See [3 Theorem 1.1 and Lemmas 2.1–2.2]. We set $N(\varnothing)=0$.

We also use Kneser’s theorem in its multiple-summand form: if $J$ is the stabilizer of $A_1+\cdots+A_t$, then

By [1 Theorem 3.2], including its elementary two-group exception,

We recall the structural input needed only for the repeated-support lemma below. A set $X \subseteq Q$ is a Vosper set if $|X+Y| \ge\min\{|Q|-1,|X|+|Y|\}$ whenever $|Y| \ge2$. An AP-representation or a Vosper-representation of $A \subseteq G$ means a subgroup $J$ for which

and the image of $A$ in $G/J$ is, respectively, an arithmetic progression or a Vosper set. If $0 \in A$, $\langle A\rangle=G$, and $|A| \le|G|/2$, such a representation exists [1 Theorem 3.1]. Call $U$ valid if $|\Sigma_0(V)| \le|\langle V\rangle|/2$ for every nonempty $V \subseteq U$. The following consequence of [1 Proposition 4.1] handles the AP case: if $U$ is valid, antisymmetric, generates $G$, $|U|=m \ge4$, and $U^*$ has an AP-representation, then $|\Sigma_0(U)| \ge\tau_m+1$. Here $\Sigma_0$ includes the empty sum, as does the subset-sum notation in [1]. The growth and boundary estimates for the Vosper case are proved below under the four-copy zero-sum-free hypothesis used in this paper.

Finally, Olson’s boundary estimate, in the form [3 Lemma 2.7], says that if $C$ is antisymmetric, $c=|C|$, $H=\langle C\rangle$, and $|H| \ge2b$ for $b=\min\{|B|,|G\setminus B|\} \ge1$, then

In this assertion $H$ may be a proper subgroup of $G$.

Repeated supports

Proof. The four-copy assumption makes $U$ antisymmetric and valid. To see validity, suppose $Z=\Sigma_0(V)$ has size greater than $|\langle V\rangle|/2$ for some nonempty $V \subseteq U$. Then $Z+Z=\langle V\rangle$, and a representation of $-v$ by $V^2$, followed by a third copy of any $v\in V$, gives a zero-sum subsequence of $U^4$.

Write $X=U^*$, and let $H$ be the subgroup in a Vosper-representation of $X$. Put

The representation is strict, so $0 \le\delta< h$ and $Q$ is a proper generating subset of $G/H$. It is symmetric and contains zero. Consequently $u \ge3$: a symmetric generating set of size two containing zero would be the entire quotient of order two.

We first prove the kernel estimate

Let $A=U\cap H$, $a=|A|$. Since $|X\cap H|=2a+1$, $\delta\ge h-2a-1$. If $a=0$, this proves (3.2). If $a>0$, validity and (2.2) give

For odd $h$ this yields $2a \le(h-1)/2$, as required. For even $h$, equality $|\Sigma_0(A)|=h/2$ is impossible. Indeed, set $Z=\Sigma_0(A)$ and $D=\Sigma_0(A^2)=Z+Z$. The fact that $A^4$ is zero-sum-free gives $D\cap(-D)=\{0\}$, hence $|D|\le h/2$. Since $Z\subseteq D$ and $|Z|=h/2$, we obtain $Z+Z=Z$. A finite set containing zero and closed under addition is a subgroup. Thus $Z=\langle A\rangle$, contradicting validity. Therefore $2a\le h/2-1$ when $h$ is even, which again proves (3.2).

Next we show that $2X$ is $H$-periodic. For $R\in Q$, let $X_R=X\cap\pi_H^{-1}(R)$. The total number of missing points in these fibers is $\delta<h$. If $R\ne S$, then $|X_R|+|X_S|>h$, so $X_R+X_S$ fills the whole coset indexed by $R+S$. If $R\ne-R$, symmetry gives $|X_R|=|X_{-R}|>h/2$; thus $X_R+X_R$ also fills the coset indexed by $2R$. The remaining repeated-fiber sums have $R=-R$ and target the zero coset. This coset is filled by $X_R+X_{-R}$ if a non-self-inverse direction exists. Otherwise $Q\setminus\{0\}$ contains at least two self-inverse directions. At most one of their fibers has size at most $h/2$, since their total deficit is less than $h$. A fiber of size greater than $h/2$ then fills $H$ by addition to itself. Every coset of $2Q$ is therefore full in $2X$. It follows that

Let $t$ be the last integer for which $tQ \ne G/H$. Such an integer exists because $Q$ is proper, contains zero, and generates the quotient. If $t = 1$, (9) follows at once from $|X| = 2m + 1$ and (11). Suppose $t \ge2$. The Vosper property gives

For completeness, induct on $j < t$. The only alternative to $|jQ| \ge ju$ in the Vosper bound is $|jQ| = v - 1$; then $jQ + Q = G/H$, contradicting $j + 1 \le t$. At the last layer, the same bound gives $|tQ| \ge\min\{v - 1, tu\}$. If $tu > v$, then $|(t - 1)Q| + |Q| > v$ would force $tQ = G/H$, also a contradiction. This proves (12).

For $2 \le j < t$, equations (11) and (12) give $|jX| \ge j|X|$. The same holds for $j = t$ if $tu \le v - 1$. In the only other case, $tu = v$, equations (10) and (11) yield

Here $t \ge2$ and $t(h - 1)/2 - h \ge-1$. The first layer has size $2m + 1$, and the layers after $t$ are full. This proves (9). □

Proof. Put $\alpha= \max_{x \in U} \lambda_B(x)$ and $\ell= 2b - 3$. We have $1 \le\ell\le|G| - 1$. Write $\ell= 2mR + q$, where $0 \le q < 2m$. The growth estimate (9) permits us to choose pairwise disjoint sets $E_j \subseteq jU^* \setminus\{0\}$ with

Indeed, each ball contains enough nonzero points to add the next required set. Let $E$ be their union. Counting ordered differences of distinct elements of $B$ gives

On the other hand, subadditivity of the boundary gives

The last inequality follows by completing the square in $q$. Consequently

Since $m \ge4$ and $b > m(m-1)$, we may use $(1+x)^{-2} > 1-2x$ for $x>0$ to obtain the following strict bound. Integrality of $\alpha$ then gives the final assertion.

Remark. Our argument follows [1 Section 4.2]. In arXiv:1112.1929v1, the final comparison in the proof of Lemma 4.6 (p. 18) is incorrect: in our notation, the product’s $1/b$ term is $-m(m-1)/b$, as expanded above. Lemmas 3.1–3.2 establish the estimates needed here under the four-copy hypothesis without invoking [1 Lemma 4.2].

Proof. Fix $r$ and induct on $m$, replacing the ambient group by $\langle U\rangle$. For $m \le2$, $\mathrm{N}(U) \ge\tau_m$ is immediate. For $m=3$, the three one-element sums are distinct, as are the three two-element sums. There is at most one equality between the two families: two such equalities would force an element of $U$ to have order two. The total sum belongs to neither family. Hence $\mathrm{N}(U) \ge6$. Equation (5) proves (3.6) in these base cases.

Assume $m \ge4$. The set $U$ is antisymmetric. It is also valid. Indeed, if $A=\Sigma_0(V)$ had size greater than $|\langle V\rangle|/2$ for some nonempty $V \subseteq U$, then $A+A=\langle V\rangle$. A representation of $-v$ by $V^{2}$, followed by a third copy of any $v \in V$, would give a nonempty zero-sum subsequence of $U^{2r}$.

Put $B=\Sigma_0(U^r)$, $b=|B|$, and $n=|G|$. First suppose $b>n/2$. Since $U^{2r}$ is zero-sum-free, $B\cap(-B)=\{0\}$. Therefore $n=2b-1$ is odd. Let $c=\sigma(U^r)$ and $M=b-1$, so $n=2M+1$. Taking complementary subsequences gives $B=c-B$, and consequently

On every orbit of translation by $c$ not containing zero, membership in $B$ would alternate. Such an orbit has odd length, which is impossible. Thus $c$ generates $G$. On its one orbit, (3.7) determines $B$: with $g=-2c$,

Write the distinct elements of $U$ as $w_1g,\ldots,w_mg$, where $1\le w_i\le M$. If the integer sum of the weights of $U^r$ first exceeded $M$ at some prefix, that prefix weight would lie in $[M+1,2M]$, contradicting the description of $B$. Thus $r\sum_i w_i\le M$. Its residue is $M$ modulo $2M+1$, so equality holds. It follows that $\mathrm{N}(U^r)=M\ge r\tau_m$.

Now suppose $b\le n/2$. Every zero-sum-free sequence has at least its length in nonempty sums, so $b\ge rm+1\ge2m+1=|U^*|$. The representation theorem applies to $U^*$. In the AP case, validity and the input from Section 2 give $\mathrm{N}(U)\ge\tau_m$, and (2.3) finishes the proof.

In the Vosper case, the induction hypothesis gives

Also $U^4$ is zero-sum-free, since $r\ge2$. Thus Lemma 3.2 applies and supplies an $x\in U$ with $\lambda_B(x)\ge m$. For $0\le j\le r+1$, put

The increments $d_j=|B_j\setminus B_{j-1}|$ are nonincreasing: if $y\in B_{j+1}\setminus B_j$, then $y-x\in B_j\setminus B_{j-1}$. Indeed, $y$ must come from the new translate, and membership of $y-x$ in $B_{j-1}$ would imply $y\in B_j$. Since $B_r=B$ and $d_{r+1}=\lambda_B(x)$, induction yields

Quotient sums and almost full fibers

The next lemma permits zero relations at the corners of a box of multiplicities. It excludes them only when some coordinate is strictly between its two endpoints.

If $h$ is odd, $m-o\le e$ and $\sum_i((h-3)-E_i)\le e$. Hence

using $\tau_m-\tau_o\le m(m-o)$. Combining these inequalities with (18) proves the lemma. □

An expansion alternative

Proof. There is nothing to prove if $c \le100$. Suppose $rC^* \ne H$ and $|rC^*| < 2r(c - 100)$. Put $K = \operatorname{Stab}_H(rC^*)$, $h = |K|$, $A = C \cap K$, and $a = |A|$. Let $p$ count the nonzero $K$-cosets met by $C^*$. Kneser’s theorem gives

Here $p \ge2$. Indeed, $p = 0$ would imply $K = H$; and if $p = 1$, the sole nonzero quotient element is self-inverse and generates $H/K$, forcing $rC^* = H$. Antisymmetry also gives $2(c - a) \le ph$. Thus, writing

the assumed failure and (22) imply

The third inequality follows from $N(A) + 1 \le h$ and (4); the last two follow from $a > 100$ and $a^2 < 6h$.

No distinct opposite pair of external cosets can both be occupied. Otherwise its contribution to $e$ is at least $a - 1$ by Lemma 4.2, contradicting (23). There is no occupied self-inverse nonzero coset either. If one has size $L$, its elements lie in a subgroup of order $2h$, so (4) gives $L < \sqrt{12h}$. Its contribution to $e$ is $h/2 - L$, whereas $e < a$ gives

a contradiction.

We may therefore write $p = 2m$, with one occupied coset per opposite pair. If their sizes are $L_i$, then

Lemma 4.3 applies. After dropping its nonnegative $N(A)$ term, we obtain

The last inequality uses $a < h/16$ and $h > 1600$. Thus every failure of (21) gives the first alternative.

From expansion to subset sums

Proof. By complementation assume $|B| = b$. Suppose all boundaries are at most $M = d - d^2/b > 0$. Put $\rho(x) = |B \cap(B + x)|$. For $x \in rC^*$, subadditivity gives $\rho(x) \ge b - rM$, whereas

Write $x_0 = b/d = R + \theta$, with $R = \lfloor x_0 \rfloor$ and $0 \le\theta< 1$. The hypotheses imply $|rC^*| \ge2rd$ for $1 \le r \le R$ and $|(R + 1)C^*| \ge2b$. Also $t_0 = b - (R + 1)M > 0$. Integrating the level sets of $\rho$ over the consecutive intervals of length $M$, and then over $[0,t_0]$, yields

The right side, divided by $b^2$, equals

contradicting (25). □

We now prove the global estimate for antisymmetric sets. For $s\ge1$ write

Proof. Arrange $T=\{a_1,\ldots,a_r\}$ greedily, always choosing the largest boundary relative to the current prefix sumset. Let $B_j=\Sigma_0(\{a_1,\ldots,a_j\})$ and $\sigma_j=|B_j|$, with $\sigma_0=1$. Before step $i$, set $C_i=\{a_i,\ldots,a_r\}$, $c_i=r-i+1$, and $H_i=\langle C_i\rangle$. Stop before the first step for which

Before stopping, zero-sum-freeness and (2.2) imply $|G\setminus B_{i-1}|\ge\mathrm{N}(C_i)\ge2c_i-1$. Hence (2.6) gives

While $\sigma_{i-1}<c_i$, the quantity $\sigma_i+1$ increases by a factor at least $3/2$. This regime has ended by $L(r)$ steps if the process has not already stopped. Once it ends, it does not restart. Summing the lower bounds $(c_i+1)/2$ thereafter, and discarding the first $L(r)$ ideal increments, gives, for each available prefix,

For $j\le L(r)$ the right side is nonpositive, so it also covers an early stop.

If there is no stop, subtract one from (6.6) at $j=r$. Otherwise the stopping subgroup $H$ is proper in $G$. Let $v$ be the last position with $a_v\notin H$, and put $T'=\{a_{v+1},\ldots,a_r\}$, $t=r-v$. Both $v$ and $v-1$ precede the stopping position. Since $T'\subseteq H$ and $a_v\notin H$, the two parts of

lie in distinct $H$-cosets. Hence $\mathrm{N}(a_vT')=2\mathrm{N}(T')+1$, and (2.3) gives

Finally, $t^2/3-(t+1)^2/4=(t-3)^2/12-1\ge-1$. □

Proof. Use the same greedy notation, now in $G=\langle S\rangle$. Stop before the first step $i$ for which either

Give the first condition priority if both hold. Before stopping,

The first inequality follows because the prefix sumset avoids the negative nonempty tail sums. Thus (6.5) remains valid. Let $c=c_i$, $\sigma=\sigma_{i-1}$, and $b=\min\{\sigma,\lvert G\setminus B_{i-1}\rvert\}$. By Proposition 5.1 and Lemma 6.1, with $d=c-100$, the actual increment satisfies

For clarity, if $d\le0$ this is automatic. If $d>0$ and $b\le d$, (32) forces $b=\sigma$, and the right side is negative. Otherwise Lemma 6.1 applies. When $b=\sigma$, it gives the stronger $c-100-c^2/\sigma$; when $b=\lvert G\setminus B_{i-1}\rvert$, its error $d^2/b$ is at most six by (32). This proves (33) in every case.

Put $L=L(s)$. After the first $L+1$ steps, weak growth gives, for each available $i\ge L+2$,

Indeed, by step $L$ the initial multiplicative regime has ended. For $L+1\le j\le i-1$, the weak increment at step $j$ is at least $(c_j+1)/2\ge(c_i+2)/2$. Summing these $i-1-L$ increments gives the first inequality. If $L+2>s$, there are no such steps. Discard the first $L+1$ ideal increments at cost at most $s(L+1)$, and sum (33) and (34). Since

every prefix formed before stopping obeys

Its right side is nonpositive during the discarded initial steps, so an early stop is included. If the first condition in (31) occurs, apply (5) to prefix and tail. The tail contribution $c_i^2/2$ cancels the missing square in (35). If no stop occurs, use $j=s$ and subtract the empty sum.

For a stop caused only by subgroup capacity, let $H$ be the stopping subgroup, $v$ the last position outside $H$, and $T=S_{>v}$, $r=s-v$. As in Lemma 6.2,

Apply (35) at $v-1$ and (26) to $T$. For $r=0$ use $N(T)=0$ directly. Since $r+1\le s$ and $L(r)\le L(s)$ when $r\ge1$, all cases give the convenient common bound

To simplify it, use $L(s)\le\frac{5}{2}\log(s+1)+1$ and $\mathcal{H}_s\le\log(s+1)+1$. The error in (36) is at most

because $(3s-\frac{5}{2})\log(s+1)+4s-\frac{7}{2}\ge0$ for $s\ge1$. This proves (30). □

Proof of the main theorem and consequences

Proof of Theorem 1.1. Let $I$ be the set of all order-two elements in $S$, let $q=\lvert I\rvert$, and set $X=S\setminus I$, $s=k-q$. Zero-sum-freeness makes $I$ linearly independent over $\mathbb{F}_2$. Therefore

If $N(S)\ge k^2/2$ there is nothing to prove. Otherwise

since $N(S)+1<k^2/2+1\le(k+1)^2$ and $2/\log2<3$. The set $X$ is antisymmetric. Proposition 6.3 and $s^2/2\ge k^2/2-kq$ yield

If $s=0$, use $N(X)=0$ in the same estimate; its right side is then nonpositive. This also covers all small values of $k$. □

Proof of Corollary 1.2. Let $S$ be a zero-sum-free set of maximum size $k=\operatorname{Ol}(G)-1$. The case $k=0$ is immediate. Since $N(S)\le n-1$, (4) gives $k\le\sqrt{6n}$. Put $a=13\log(k+1)+116$. Theorem 1.1 implies $k^2/2-ak\le n-1$, whence

Also $k+1\le(\sqrt{6}+1)\sqrt{n+1}$. It follows that

The coefficient $\sqrt{2}$ is necessary uniformly over finite abelian groups. For $n>\tau_t$, the residues $1,2,\ldots,t$ form a zero-sum-free set in $\mathbb{Z}/n\mathbb{Z}$. Taking $n=\tau_t+1$ shows that $\operatorname{Ol}(\mathbb{Z}/n\mathbb{Z})\ge t+1$ along a sequence with $t\sim\sqrt{2n}$.

Theorem 1.1 leaves a gap of order $k\log k$ from the classical upper bound. It does not establish the following sharper possibility.

The small values must be treated separately. In particular, $f(4)=8$ and $f(7)=24$; see [2, 3].

Even an improvement of the error in Theorem 1.1 to $O(k)$ would be a further step. The present proof loses a logarithmic number of initial greedy steps and also incurs a harmonic error from reciprocal prefix sizes. Improving the error term to $O(k)$ would require a sharper treatment of these steps, or additional structural information.

Department of Mathematics, University of Mississippi, University, MS 38677, USA

Email address: [email protected]