Computer Science Department
School of Computer Science, Carnegie Mellon University
Dimensionality Restrictions on Sums Over Z dp
Let A be an arbitrary multi-set of vectors from Z dp, where p is any prime, and |A| ≥ p(d + 2). For any fixed j, 0 ≤ j ≤ p - 1, we show that the numbers (modulo p) of zero-sum A-subsets of cardinality kp + j for k ≥ d + 2, can be determined from the numbers (modulo p) of zero-sum A-subsets of cardinality kp + j, for 0 ≤ k ≤ d + 1. For p = 2, we show that the (necessarily odd when |A| ≥ d) number of zero-sum A-subsets is at most one less than the (necessarily even when |A| ≥ d) number of subsets summing up to any other vector. We also show a similar result for odd primes. Our main tool is the representation theory for the corresponding groups.