On the expressiveness of subset-sum representations

We develop a general theory for representing information as sums of element s in a subset of the basic set A of numbers of cardinality n, often referre d to as a "knapsack vector". How many numbers can be represented in this wa y depends heavily on A. The lower, resp. upper, bound for the cardinality o f the set of representable numbers is quadratic, resp. exponential, in term s of n. We give an algorithm for the construction of a knapsack vector of a ny prescribed expressiveness (that is, the cardinality of the set of repres entable numbers), provided it falls within the range possible for expressiv eness.