Combinatorics – Maximal Subset of a Finite Field Where Sum of Any Subset is Non-Zero

additive-combinatoricsco.combinatoricsfinite-fieldsra.rings-and-algebras

Given a finite field $\mathbb{F}_q$ with $q=p^m$ where $p$ is the characteristic.
For any subset $S=\{a_1,\dots,a_n\}$ of $\mathbb{F}_q$, if any partial sum (i.e. the sum of elements in a non-empty subset of $S$) is non-zero, then we may call $S$ a good subset.

My question is what's the maximal cardinality $f(q)$ of a good subset $S$?

Or are there any (lower) bounds for $f(q)$?

Best Answer

I could trace this question down to the paper of Erdős and Heilbronn "On the addition of residue classes mod $p$" (Acta Arith. 17 (1970), 227–229), where it is shown that for a prime $p$, if $A$ is a subset of the $p$-element group with $\lvert A\rvert>6\sqrt{3p}$, then the subset sum set of $A$ is the whole group.

It seems that the first to prove that $\lvert A\rvert>c\sqrt{\lvert G\rvert}$, with an absolute constant $c$, suffices to represent $0$ in any abelian group $G$, was Szemerédi ("On a conjecture of Erdős and Heilbronn", Acta Arith. 17 (1970), 227–229).

Some tightly related problems are considered in a paper of Eggleton and Erdős "Two combinatorial problems in group theory" (Acta Arith. 21 (1972), 111–116).

Three years later, Olson ("Sums of sets of group elements", Acta Arith. 28 (1975), 147–156) proved that if $A$ is a zero-sum-free set in a finite abelian group $G$, then $\lvert A\rvert<3\sqrt{\lvert G\rvert}$.

Hamidoune and Zémor ("On zero-free subset sums", Acta Arith. 78 (1996), 143–152) showed that for the group of prime order $p$ it suffices to have $\lvert A\rvert>(1+o(1))\sqrt{2p}$.

The exact result for the prime-order groups was obtained by Nguyen, Szemerédi, and Vu ("Subset sums modulo a prime", Acta Arith. 131 (2008), no. 4, 303–316).

There were several further improvements in the general case, with the current record $\lvert A\rvert<\sqrt{6\lvert G\rvert}$ due to Gao, Huang, Hui, Li, Liu, and Peng ("Sums of sets of abelian group elements", J. Number Theory, 208 (2020), 208–229). In fact, they prove a stronger result: if $A$ is a finite zero-sum-free subset of an abelian group, then $A$ spans at least as many as $1+\lvert A\rvert^2/6$ pairwise distinct subset sums.

Two other important papers on this subject are mentioned in the answer of Le p'tit bonhomme.

Related Question