Skip to content

Add Sidon and generalized bounded-representation set laws #233

Description

@sraaphorst

Add laws and predicates for subsets with bounded additive representation multiplicity.

Scope

For a finite subset $$S$$ of a commutative semigroup, add support for determining whether $$S$$ is a Sidon set.

Using unordered additive representations, $$S$$ is Sidon when every element has at most one representation:

$$a+b=c+d \implies \{a,b\}=\{c,d\}.$$

Add support for generalized $$B_2[g]$$ sets, where every element has at most $$g$$ unordered representations as a sum of two elements of $$S$$.

Consider a later generalization to $$B_h[g]$$, where representation multiplicity is bounded for sums of $$h$$ elements.

Initial API concepts

Possible operations include:

fun <A> FiniteSet.Unordered<A>.isSidon(
    semigroup: CommutativeSemigroup<A>
): Boolean

fun <A> FiniteSet.Unordered<A>.isB2g(
    g: BigInteger,
    semigroup: CommutativeSemigroup<A>
): Boolean

The exact API should reuse the additive representation machinery rather than independently enumerating additive quadruples.

Design notes

Initially represent Sidon-ness as a law or property of a subset relative to an additive operation.

Do not introduce a dedicated SidonSet<A> refined type unless later constructions or algorithms need to preserve and exploit a proof of Sidon-ness.

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