CMU-CS-07-103 Computer Science Department School of Computer Science, Carnegie Mellon University
Dimensionality Restrictions on Sums Over Z^{ d}_{p} Ioannis Koutis January 2007
CMU-CS-07-103.ps
Let A be an arbitrary multi-set of vectors from Z^{ d}_{p}, 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. 9 pages
| |
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |