ambient_groups

class graphcalc.additive_combinatorics.ambient_groups.FiniteAbelianGroup(moduli: Sequence[int], *, validate: bool = True)

Bases: object

Finite abelian group of the form

\[\mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}.\]

This class provides a lightweight explicit model for finite additive groups used in additive combinatorics. Group elements are represented canonically as tuples of integers, one coordinate for each cyclic factor, with all arithmetic performed coordinatewise modulo the corresponding modulus.

The main intended use is as the ambient group for graphcalc.additive_combinatorics.sets.AdditiveSet, where one wants a mathematically transparent representation of finite subsets together with exact additive operations such as sumsets, difference sets, translations, and stabilizers.

Parameters:

• moduli (sequence of int) – Positive integers specifying the cyclic factors. For example, moduli=(5,) represents \(\mathbb{Z}/5\mathbb{Z}\), while moduli=(2, 3) represents \(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}\).

• validate (bool, default=True) – Whether to validate the moduli on construction.

Notes

Elements are stored and returned in canonical reduced form. For instance, in FiniteAbelianGroup((4, 5)), the tuples (5, -1) and (1, 4) represent the same group element.

This class deliberately models only nontrivial finite products of cyclic groups, so moduli must be nonempty and all entries must be positive.

Examples

Construct the cyclic group \(\mathbb{Z}/7\mathbb{Z}\):

>>> G = FiniteAbelianGroup((7,))
>>> G.order
7
>>> G.add((3,), (6,))
(2,)

Construct a product group and perform arithmetic:

>>> G = FiniteAbelianGroup((4, 5))
>>> G.normalize((5, -1))
(1, 4)
>>> G.add((3, 4), (2, 3))
(1, 2)
>>> G.neg((1, 2))
(3, 3)

add(x: Sequence[int], y: Sequence[int]) → Tuple[int, ...]

Add two group elements.

Parameters:

• x (sequence of int) – Elements of the ambient group.

• y (sequence of int) – Elements of the ambient group.

Returns:

The sum x + y computed coordinatewise modulo the corresponding cyclic moduli.

Return type:

Element

Raises:

ValueError – If either input does not have the correct number of coordinates.

Examples

>>> G = FiniteAbelianGroup((4, 5))
>>> G.add((3, 4), (2, 3))
(1, 2)

contains(x: Sequence[int]) → bool

Test whether a tuple can be interpreted as an element of the group.

Parameters:

x (sequence of int) – Candidate element representation.

Returns:

True if x has the correct number of coordinates and therefore determines an element of the ambient group, and False otherwise.

Return type:

bool

Notes

Since element representatives are interpreted modulo the defining moduli, any integer tuple of the correct length is accepted.

elements() → Iterator[Tuple[int, ...]]

Iterate over all elements of the group.

Returns:

Iterator over the canonical representatives of all group elements in lexicographic order.

Return type:

iterator of Element

Notes

This method is suitable for small groups. For larger ambient groups, the total number of elements is order, which may be too large for exhaustive enumeration.

equal(x: Sequence[int], y: Sequence[int]) → bool

Test whether two tuples represent the same group element.

Parameters:

• x (sequence of int) – Candidate element representations.

• y (sequence of int) – Candidate element representations.

Returns:

True if x and y agree after canonical reduction modulo the defining moduli, and False otherwise.

Return type:

bool

Examples

>>> G = FiniteAbelianGroup((4, 5))
>>> G.equal((5, -1), (1, 4))
True
>>> G.equal((1, 4), (1, 3))
False

list_elements() → list[Tuple[int, ...]]

Return all group elements as a list.

Returns:

The full list of canonical representatives in lexicographic order.

Return type:

list of Element

See also

elements

Lazy iterator over all elements.

property moduli: Tuple[int, ...]

Return the cyclic moduli defining the ambient group.

Returns:

The tuple (n_1, ..., n_k) such that the group is :math: mathbb{Z}/n_1mathbb{Z} times cdots imes mathbb{Z}/n_kmathbb{Z}.

Return type:

tuple of int

neg(x: Sequence[int]) → Tuple[int, ...]

Return the additive inverse of an element.

Parameters:

x (sequence of int) – Element of the ambient group.

Returns:

The inverse -x computed coordinatewise modulo the corresponding cyclic moduli.

Return type:

Element

Raises:

ValueError – If x does not have the correct number of coordinates.

Examples

>>> G = FiniteAbelianGroup((4, 5))
>>> G.neg((1, 2))
(3, 3)

normalize(x: Sequence[int]) → Tuple[int, ...]

Return the canonical representative of a group element.

Parameters:

x (sequence of int) – Tuple-like representation of a group element.

Returns:

The coordinatewise reduced tuple, with the i-th coordinate taken modulo moduli[i].

Return type:

Element

Raises:

ValueError – If x does not have the correct number of coordinates.

Examples

>>> G = FiniteAbelianGroup((4, 5))
>>> G.normalize((5, -1))
(1, 4)

property order: int

Return the cardinality of the group.

Returns:

The product of the cyclic moduli.

Return type:

int

random_element(rng=None) → Tuple[int, ...]

Return a random group element.

Parameters:

rng (numpy.random.Generator, optional) – Random number generator to use. If omitted, a new default generator is created.

Returns:

A uniformly sampled element of the ambient group, represented in canonical coordinates.

Return type:

Element

Notes

Sampling is independent across coordinates, with the i-th coordinate chosen uniformly from {0, ..., moduli[i]-1}.

property rank: int

Return the number of cyclic factors.

Returns:

The number of coordinates in the ambient product group.

Return type:

int

Notes

This is the number of cyclic components in the chosen presentation, not a minimal generating rank invariant.

scalar_mul(m: int, x: Sequence[int]) → Tuple[int, ...]

Return the repeated sum \(m x\).

Parameters:

• m (int) – Integer scalar.

• x (sequence of int) – Element of the ambient group.

Returns:

The element obtained by coordinatewise multiplication of x by m, reduced modulo the corresponding cyclic moduli.

Return type:

Element

Raises:

ValueError – If x does not have the correct number of coordinates.

sub(x: Sequence[int], y: Sequence[int]) → Tuple[int, ...]

Subtract one group element from another.

Parameters:

• x (sequence of int) – Elements of the ambient group.

• y (sequence of int) – Elements of the ambient group.

Returns:

The difference x - y computed coordinatewise modulo the corresponding cyclic moduli.

Return type:

Element

Raises:

ValueError – If either input does not have the correct number of coordinates.

zero() → Tuple[int, ...]

Return the additive identity.

Returns:

The zero element (0, ..., 0) of the ambient group.

Return type:

Element