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

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ Such sets are called zero-sum free subsets and there is a large literature on them. $\endgroup$ Commented Mar 8, 2022 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$ Commented Mar 8, 2022 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$ Commented Mar 8, 2022 at 6:27
  • 4
    $\begingroup$ @GordonRoyle zero-sum-free (with 2 dashes) would be more appropriate $\endgroup$ Commented Mar 8, 2022 at 7:17
  • 1
    $\begingroup$ @GerryMyerson: $\{-2,1,3,4,\dotsc, k\}$. $\endgroup$ Commented Mar 8, 2022 at 7:25

2 Answers 2

Reset to default
16
$\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.

Improve this answer
$\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$ Commented Mar 9, 2022 at 0:08
  • 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$ Commented Mar 9, 2022 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$ Commented Mar 9, 2022 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$ Commented Mar 9, 2022 at 14:13
  • 2
    $\begingroup$ @TimothyChow In my field, Seva's usage of $o(1)$ is perfectly standard. The statement that "$|A| > (1+o(1))\sqrt{2p}$ suffices" means: there is some function $r$ with $r = o(1)$ such that $|A| > (1+r(p))\sqrt{2p}$ suffices. $\endgroup$ Commented Mar 12, 2022 at 18:15
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.