Closure with a twist

Short description: Property of subsets of an algebraic structure

Closure with a twist is a property of subsets of an algebraic structure. A subset [math]\displaystyle{ Y }[/math] of an algebraic structure [math]\displaystyle{ X }[/math] is said to exhibit closure with a twist if for every two elements

[math]\displaystyle{ y_1, y_2 \in Y }[/math]

there exists an automorphism [math]\displaystyle{ \phi }[/math] of [math]\displaystyle{ X }[/math] and an element [math]\displaystyle{ y_3 \in Y }[/math] such that

[math]\displaystyle{ y_1 \cdot y_2 = \phi(y_3) }[/math]

where "[math]\displaystyle{ \cdot }[/math]" is notation for an operation on [math]\displaystyle{ X }[/math] preserved by [math]\displaystyle{ \phi }[/math].

Two examples of algebraic structures which exhibit closure with a twist are the cwatset and the generalized cwatset, or GC-set.

Cwatset

In mathematics, a cwatset is a set of bitstrings, all of the same length, which is closed with a twist.

If each string in a cwatset, C, say, is of length n, then C will be a subset of [math]\displaystyle{ \mathbb{Z}_2^n }[/math]. Thus, two strings in C are added by adding the bits in the strings modulo 2 (that is, addition without carry, or exclusive disjunction). The symmetric group on n letters, [math]\displaystyle{ \text{Sym}(n) }[/math], acts on [math]\displaystyle{ \mathbb{Z}_2^n }[/math] by bit permutation:

[math]\displaystyle{ p((c_1, \ldots, c_n)) = (c_{p(1)}, \ldots, c_{p(n)}), }[/math]

where [math]\displaystyle{ c = (c_1, \ldots, c_n) }[/math] is an element of [math]\displaystyle{ \mathbb{Z}_2^n }[/math] and p is an element of [math]\displaystyle{ \text{Sym}(n) }[/math]. Closure with a twist now means that for each element c in C, there exists some permutation [math]\displaystyle{ p_c }[/math] such that, when you add c to an arbitrary element e in the cwatset and then apply the permutation, the result will also be an element of C. That is, denoting addition without carry by [math]\displaystyle{ + }[/math], C will be a cwatset if and only if

[math]\displaystyle{ \forall c\in C : \exists p_c\in \text{Sym}(n) : \forall e\in C : p_c(e+c) \in C. }[/math]

This condition can also be written as

[math]\displaystyle{ \forall c\in C : \exists p_c\in \text{Sym}(n) : p_c(C+c)=C. }[/math]

Examples

• All subgroups of [math]\displaystyle{ \mathbb{Z}_2^n }[/math] — that is, nonempty subsets of [math]\displaystyle{ \mathbb{Z}_2^n }[/math] which are closed under addition-without-carry — are trivially cwatsets, since we can choose each permutation p_c to be the identity permutation.
• An example of a cwatset which is not a group is

F = {000,110,101}.

To demonstrate that F is a cwatset, observe that

F + 000 = F.

F + 110 = {110,000,011}, which is F with the first two bits of each string transposed.

F + 101 = {101,011,000}, which is the same as F after exchanging the first and third bits in each string.

• A matrix representation of a cwatset is formed by writing its words as the rows of a 0-1 matrix. For instance a matrix representation of F is given by

[math]\displaystyle{ F = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}. }[/math]

To see that F is a cwatset using this notation, note that

[math]\displaystyle{ F + 000 = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} = F^{id}=F^{(2,3)_R(2,3)_C}. }[/math]

[math]\displaystyle{ F + 110 = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix} = F^{(1,2)_R(1,2)_C}=F^{(1,2,3)_R(1,2,3)_C}. }[/math]

[math]\displaystyle{ F + 101 = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix} = F^{(1,3)_R(1,3)_C}=F^{(1,3,2)_R(1,3,2)_C}. }[/math]

where [math]\displaystyle{ \pi_R }[/math] and [math]\displaystyle{ \sigma_C }[/math] denote permutations of the rows and columns of the matrix, respectively, expressed in cycle notation.

• For any [math]\displaystyle{ n \geq 3 }[/math] another example of a cwatset is [math]\displaystyle{ K_n }[/math], which has [math]\displaystyle{ n }[/math]-by-[math]\displaystyle{ n }[/math] matrix representation

[math]\displaystyle{ K_n = \begin{bmatrix} 0 & 0 & 0 & \cdots & 0 & 0 \\ 1 & 1 & 0 & \cdots & 0 & 0 \\ 1 & 0 & 1 & \cdots & 0 & 0 \\ & & & \vdots & & \\ 1 & 0 & 0 & \cdots & 1 & 0 \\ 1 & 0 & 0 & \cdots & 0 & 1 \end{bmatrix}. }[/math]

Note that for [math]\displaystyle{ n = 3 }[/math], [math]\displaystyle{ K_3=F }[/math].

• An example of a nongroup cwatset with a rectangular matrix representation is

[math]\displaystyle{ W = \begin{bmatrix} 0 & 0 & 0\\ 1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix}. }[/math]

Properties

Let [math]\displaystyle{ C \subset \mathbb{Z}_2^n }[/math] be a cwatset.

• The degree of C is equal to the exponent n.
• The order of C, denoted by |C|, is the set cardinality of C.
• There is a necessary condition on the order of a cwatset in terms of its degree, which is

analogous to Lagrange's Theorem in group theory. To wit,

Theorem. If C is a cwatset of degree n and order m, then m divides [math]\displaystyle{ 2^n! }[/math].

The divisibility condition is necessary but not sufficient. For example, there does not exist a cwatset of degree 5 and order 15.

Generalized cwatset

In mathematics, a generalized cwatset (GC-set) is an algebraic structure generalizing the notion of closure with a twist, the defining characteristic of the cwatset.

Definitions

A subset H of a group G is a GC-set if for each [math]\displaystyle{ h\in H }[/math], there exists a [math]\displaystyle{ \phi_h\in\text{Aut}(G) }[/math] such that [math]\displaystyle{ \phi_h(h) \cdot H = \phi_h(H) }[/math].

Furthermore, a GC-set H ⊆ G is a cyclic GC-set if there exists an [math]\displaystyle{ h\in H }[/math] and a [math]\displaystyle{ \phi\in\text{Aut}(G) }[/math] such that [math]\displaystyle{ H = {h_1, h_2, ...} }[/math] where [math]\displaystyle{ h_1 = h }[/math] and [math]\displaystyle{ h_n = h_1 \cdot \phi(h_{n-1}) }[/math] for all [math]\displaystyle{ n \gt 1 }[/math].

Examples

• Any cwatset is a GC-set, since [math]\displaystyle{ C + c = \pi(C) }[/math] implies that [math]\displaystyle{ \pi^{-1}(c) + C = \pi^{-1}(C) }[/math].
• Any group is a GC-set, satisfying the definition with the identity automorphism.
• A non-trivial example of a GC-set is [math]\displaystyle{ H = {0, 2} }[/math] where [math]\displaystyle{ G = Z_{10} }[/math].
• A nonexample showing that the definition is not trivial for subsets of [math]\displaystyle{ Z_2^n }[/math] is [math]\displaystyle{ H = {000, 100, 010, 001, 110} }[/math].

Properties

• A GC-set H ⊆ G always contains the identity element of G.
• The direct product of GC-sets is again a GC-set.
• A subset H ⊆ G is a GC-set if and only if it is the projection of a subgroup of Aut(G)⋉G, the semi-direct product of Aut(G) and G.
• As a consequence of the previous property, GC-sets have an analogue of Lagrange's Theorem: The order of a GC-set divides the order of Aut(G)⋉G.
• If a GC-set H has the same order as the subgroup of Aut(G)⋉G of which it is the projection then for each prime power [math]\displaystyle{ p^{q} }[/math] which divides the order of H, H contains sub-GC-sets of orders p,[math]\displaystyle{ p^{2} }[/math],...,[math]\displaystyle{ p^{q} }[/math]. (Analogue of the first Sylow Theorem)
• A GC-set is cyclic if and only if it is the projection of a cyclic subgroup of Aut(G)⋉G.

References

• Sherman, Gary J.; Wattenberg, Martin (1994), "Introducing … cwatsets!", Mathematics Magazine 67 (2): 109–117, doi:10.2307/2690684 .
• The Cwatset of a Graph, Nancy-Elizabeth Bush and Paul A. Isihara, Mathematics Magazine 74, #1 (February 2001), pp. 41–47.
• On the symmetry groups of hypergraphs of perfect cwatsets, Daniel K. Biss, Ars Combinatorica 56 (2000), pp. 271–288.
• Automorphic Subsets of the n-dimensional Cube, Gareth Jones, Mikhail Klin, and Felix Lazebnik, Beiträge zur Algebra und Geometrie 41 (2000), #2, pp. 303–323.
• Daniel C. Smith (2003)RHIT-UMJ, RHIT [1]