10
$\begingroup$

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)$?

$\endgroup$
6
  • 5
    $\begingroup$ Such sets are called zero-sum free subsets and there is a large literature on them. $\endgroup$ Mar 8 at 6:10
  • 1
    $\begingroup$ There is a discussion at C15 in Guy, Unsolved Problems In Number Theory. Guy doesn't look at finite fields, but at integers modulo $n$, so the overlap is prime fields. If $p$ is prime, $k(k+1)/2<p<(k+1)(k+2)/2$, Selfridge conjectured the largest set is simply $\{\,1,2,\dots,k\,\}$, with $k$ elements. $\endgroup$ Mar 8 at 6:21
  • 8
    $\begingroup$ Note that the multiplication in the field really doesn't come into it, so as stated it's a problem about elementary abelian groups. $\endgroup$ Mar 8 at 6:27
  • 4
    $\begingroup$ @GordonRoyle zero-sum-free (with 2 dashes) would be more appropriate $\endgroup$
    – YCor
    Mar 8 at 7:17
  • 1
    $\begingroup$ @GerryMyerson: $\{-2,1,3,4,\dotsc, k\}$. $\endgroup$
    – Seva
    Mar 8 at 7:25

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ I edited to include some links. Did you really mean $1 + 0(1)$ in the Hamidoune–Zémor asymptotics? I thought the usual notation for asymptotics was $1 + O(1)$, but didn't want to edit in case it was intentional. $\endgroup$
    – LSpice
    Mar 9 at 0:08
  • 1
    $\begingroup$ @LSpice: Thanks for editing. $0(1)$ fixed. $\endgroup$
    – Seva
    Mar 9 at 7:29
  • 2
    $\begingroup$ There is also the easy case of $\left(\mathbb{Z}/2\right)^n$ where the answer is $n$ by basic linear algebra $\endgroup$
    – user49822
    Mar 9 at 9:15
  • 2
    $\begingroup$ Using a greater-than symbol with $o(1)$ on the right-hand side is an abuse of little-o notation. If you have a little o then you should use an equality sign. But even better (if I understand the introduction to the Hamidoune–Zémor paper correctly) would be to state the result as $|A| \ge \sqrt{2p} + 5 \ln p$. $\endgroup$ Mar 9 at 12:12
  • 2
    $\begingroup$ @TimothyChow: I do not think there is any abuse of notation here. One writes $f(x)\ge(1+o(1))g(x)$ to indicate that $f(x)\ge g(x)-r(x)$ where $r(x)=o(g(x))$; this seems quite clear and unambiguous to me. Would you be Ok with $f(x)\ge(1-o(1))g(x)$? $\endgroup$
    – Seva
    Mar 9 at 14:13
9
$\begingroup$

To complete Seva's answer, the article (“Subset sums modulo a prime”) of Nguyen, Szemerédi and Vu gives an asymptotic result for $p$ large enough, and this was also independently proved by Deshouillers and Prakash in “Large zero-free subsets of $\mathbb{Z}/p\mathbb{Z}$”, Integers, Procedings of Integers conference 2009 11A (2011), article 8.

The result in $\mathbb{F}_p$ for any prime $p$ is established in “An addition theorem and maximal zero-sum free sets in $\mathbb{Z}/p\mathbb{Z}$”, E. Balandraud, Israel Journal of Mathematics, 188 (2012), 405-429.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.