sets

class graphcalc.additive_combinatorics.sets.AdditiveSet(elements: Iterable[Sequence[int]], *, group: FiniteAbelianGroup, validate: bool = True)[source]

Bases: object

Finite subset of a finite abelian ambient group.

This class represents a subset \(A \subseteq G\), where \(G = \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}\) is modeled by graphcalc.additive_combinatorics.ambient_groups.FiniteAbelianGroup.

Elements are stored canonically as reduced tuples in the ambient group, and duplicates are removed automatically. The class is intended to serve as the core object for additive-combinatorial computations such as sumsets, difference sets, translations, dilations, stabilizers, and representation functions.

Parameters:

elements (iterable of sequence of int) – Elements of the subset. Each element must have the correct coordinate length for the ambient group. Representatives are reduced modulo the ambient moduli and deduplicated.
group (FiniteAbelianGroup) – Ambient finite abelian group containing the set.
validate (bool, default=True) – Whether to validate the inputs on construction.

Notes

The empty subset is allowed.

The internal representation is canonical: if two input tuples represent the same ambient group element, they are identified. For example, in \(\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z}\), the elements (5, -1) and (1, 4) are treated as the same element.

Examples

>>> from graphcalc.additive_combinatorics.ambient_groups import FiniteAbelianGroup
>>> G = FiniteAbelianGroup((5,))
>>> A = AdditiveSet([(0,), (1,), (6,)], group=G)
>>> A.elements
((0,), (1,))
>>> A.size
2
>>> A.sumset().elements
((0,), (1,), (2,))

contains_zero() → bool[source]

Return whether the set contains the additive identity.

Returns:: True if the ambient zero element belongs to the subset, and False otherwise.
Return type:: bool

copy() → AdditiveSet[source]

Return a copy of the additive set.

Returns:: A new additive set with the same elements and ambient group.
Return type:: AdditiveSet

diffset(other: AdditiveSet | None = None) → AdditiveSet[source]

Return a difference set.

Parameters:: other (AdditiveSet or None, default=None) – Second set. If omitted, computes \(A - A\).
Returns:: The difference set \(A - B = \{a-b : a \in A,\, b \in B\}\) if other is provided, and \(A - A\) otherwise.
Return type:: AdditiveSet
Raises:: ValueError – If the ambient groups do not agree.

dilate(m: int) → AdditiveSet[source]

Return the dilate \(mA\).

Parameters:: m (int) – Integer scalar.
Returns:: The set \(mA = \{ma : a \in A\}\) formed by scalar multiplication in the ambient group.
Return type:: AdditiveSet

property elements: Tuple[Tuple[int, ...], ...]

Return the canonical elements of the set.

Returns:: The elements of the subset in sorted canonical form.
Return type:: tuple of Element

equal(other: AdditiveSet) → bool[source]

Test equality as subsets of the same ambient group.

Parameters:: other (AdditiveSet) – Another additive set.
Returns:: True if the two sets have the same ambient moduli and the same canonical elements, and False otherwise.
Return type:: bool

property group: FiniteAbelianGroup

Return the ambient finite abelian group.

Returns:: The ambient group in which the set is viewed as a subset.
Return type:: FiniteAbelianGroup

property is_empty: bool

Return whether the subset is empty.

Returns:: True if the set has no elements and False otherwise.
Return type:: bool

is_subset_of(other: AdditiveSet) → bool[source]

Return whether this set is a subset of another additive set.

Parameters:: other (AdditiveSet) – Candidate superset.
Returns:: True if every element of this set belongs to other and the ambient groups agree, and False otherwise.
Return type:: bool

k_fold_sum(k: int) → AdditiveSet[source]

Return the iterated sumset \(kA\).

Parameters:: k (int) – Number of summands.
Returns:: The set of all sums of k elements of \(A\).
Return type:: AdditiveSet
Raises:: ValueError – If k is negative.

Notes

By convention, \(0A = \{0\}\), where \(0\) is the additive identity of the ambient group.

max_sum_representation_count(other: AdditiveSet | None = None) → int[source]

Return the maximum value of the additive representation function.

Parameters:: other (AdditiveSet or None, default=None) – Second set. If omitted, computes the maximum over the self-sumset.
Returns:: The maximum number of representations of a group element as a sum of one element from each set. Returns 0 if the relevant product set is empty.
Return type:: int

negate() → AdditiveSet[source]

Return the reflected set \(-A\).

Returns:: The set \(-A = \{-a : a \in A\}\) in the same ambient group.
Return type:: AdditiveSet

representation_function(other: AdditiveSet | None = None) → dict[Tuple[int, ...], int][source]

Return the additive representation function.

Parameters:

other (AdditiveSet or None, default=None) – Second set. If omitted, computes the representation counts for \(A + A\).

Returns:

Dictionary mapping each group element \(x\) appearing in the sumset to the number of pairs with sum \(x\). That is, the returned value is the function

\[r_{A,B}(x) = |\{(a,b) \in A \times B : a+b=x\}|.\]

Return type:

dict of Element to int

Raises:

ValueError – If the ambient groups do not agree.

property size: int

Return the cardinality of the set.

Returns:: The number of distinct elements of the subset.
Return type:: int

stabilizer() → AdditiveSet[source]

Return the additive stabilizer of the set.

Returns:

The subgroup

\[\operatorname{Stab}(A) = \{g \in G : A + g = A\}.\]

Return type:

AdditiveSet

Notes

This is computed by exhaustive search over the ambient group, so it is intended for small groups.

sumset(other: AdditiveSet | None = None) → AdditiveSet[source]

Return a sumset.

Parameters:: other (AdditiveSet or None, default=None) – Second set. If omitted, computes the self-sumset \(A + A\).
Returns:: The sumset \(A + B = \{a+b : a \in A,\, b \in B\}\) if other is provided, and \(A + A\) otherwise.
Return type:: AdditiveSet
Raises:: ValueError – If the ambient groups do not agree.

translate(x: Sequence[int]) → AdditiveSet[source]

Return the translate \(A + x\).

Parameters:: x (sequence of int) – Translation element in the ambient group.
Returns:: The translated set \(A + x = \{a + x : a \in A\}\).
Return type:: AdditiveSet
Raises:: ValueError – If x does not have the correct coordinate length.