Low complexity inverse mappings on sum-distinct elements of a power set

Abstract

Let ∪, △, ⨄ and + denote set-union, symmetric set-difference, multiset-union and real number addition, respectively. We consider low complexity inverse mappings (algorithms which return the subset of a given sum) defined on sum-distinct elements from (2 ^S , ∪), (2 ^S , △), (2 ^S , ⨄) and (S _n , +) where 2 ^S is a power set of an n-element set S and S _n ≜ {0, 1,…, 2 ⁿ − 1}. Within each of the above pair, mappings are related to generating functions of the respective sum-distinct sets. Between compatible pairs, they are related by a subset-sum property, e.g. if L ∈ 2 ^S is sum-distinct in (2 ^S , ∪), then L is sum-distinct in (2 ^S , △).

Keywords:

• Inverse mappings
• additive number theory
• sum-distinct elements
• power set

C.R.Categories:

• G.2.1