# Few subsequence sums in Z_n x Z_n

 Importance: Medium ✭✭
 Author(s): Bollobas, Bela Leader, Imre
 Subject: Number Theory » Combinatorial Number Theory
 Keywords: subsequence sum zero sum
 Recomm. for undergrads: no
 Prize: none
 Posted by: mdevos on: March 10th, 2007
Conjecture   For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .

Definition: Given a sequence of elements from an additive abelian group, we call a subsequence sum any group element expressable as a sum of some nontrivial subsequence of . We say that is zero-free if is not a subsequence sum.

It is easy to see that every sequence of elements from has a nontrivial subsequence which sums to zero (actually this holds for every group of order ). Just consider the elements , , , . If these elements are distinct, we have a zero sum. Otherwise, we have for some , but then . The same argument shows that whenever , every zero-free sequence of elements of must have at least distinct subsequence sums. In other words, the sequence consisting of copies of has the fewest number of distinct subsequence sums over all zero-free sequences in of length .

In the group , a theorem of Olsen shows that every sequence of length has a nontrivial subsequence which sums to zero. However, we do not know what the minimum number of distinct subsequence sums is for a zero-free sequence of a given length. The above conjecture would appear to be the natural optimum.