Skip to content

Add sumsets and additive representation functions #232

Description

@sraaphorst

Add foundational additive-combinatorics operations over finite subsets of commutative semigroups.

Scope

Add support for:

  • The two-fold sumset
$$S + S = \{a+b : a,b\in S\}.$$
  • The restricted two-fold sumset
$$S \mathbin{\hat{+}} S = \{a+b : a,b\in S,\ a\ne b\}.$$
  • Additive representations of an element $$s$$:
$$R_S(s) = \{(a,b)\in S^2 : a+b=s\}.$$
  • The additive representation function:
$$r_S(s)=|R_S(s)|.$$

The fundamental definitions should require only a CommutativeSemigroup<A> and a finite unordered set.

For an AbelianGroup<A>, provide an optimized representation lookup using

$$b=s-a,$$

reducing exhaustive pair search from (O(|S|^2)) to expected (O(|S|)) when set membership is hash-backed.

Design notes

The representation function should be treated as the central abstraction. Its support is the two-fold sumset:

$$\textrm{supp}(r_S)=S+S.$$

Do not introduce a SidonSet<A> type in this issue.

Suggested package:

org.vorpal.kosmos.combinatorics.additive

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions