Closure with a twist

Template:Short description Closure with a twist is a property of subsets of an algebraic structure. A subset $Y$ of an algebraic structure $X$ is said to exhibit closure with a twist if for every two elements

$y_1,y_2\in Y$

there exists an automorphism $\varphi$ of $X$ and an element $y_3\in Y$ such that

$y_1\cdot y_2=\varphi (y_3)$

where "$\cdot$" is notation for an operation on $X$ preserved by $\varphi$.

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 ${\mathbb{Z}}_2^n$. 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, $\text{Sym}(n)$, acts on ${\mathbb{Z}}_2^n$ by bit permutation:

$p((c_1,\dots ,c_n))=(c_{p(1)},\dots ,c_{p(n)}),$

where $c=(c_1,\dots ,c_n)$ is an element of ${\mathbb{Z}}_2^n$ and p is an element of $\text{Sym}(n)$. Closure with a twist now means that for each element c in C, there exists some permutation $p_c$ 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 $+$, C will be a cwatset if and only if

$\mathrm{\forall }c\in C:\mathrm{\exists }{p}_c\in \text{Sym}(n):\mathrm{\forall }e\in C:p_c(e+c)\in C.$

This condition can also be written as

$\mathrm{\forall }c\in C:\mathrm{\exists }{p}_c\in \text{Sym}(n):p_c(C+c)=C.$

Examples

• All subgroups of ${\mathbb{Z}}_2^n$ — that is, nonempty subsets of ${\mathbb{Z}}_2^n$ 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

$F=\left[\begin{array}{ccc}0& 0& 0\\ 1& 1& 0\\ 1& 0& 1\end{array}\right].$

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

$F+000=\left[\begin{array}{ccc}0& 0& 0\\ 1& 1& 0\\ 1& 0& 1\end{array}\right]=F^{id}=F^{(2,3{)}_R(2,3{)}_C}.$

$F+110=\left[\begin{array}{ccc}1& 1& 0\\ 0& 0& 0\\ 0& 1& 1\end{array}\right]=F^{(1,2{)}_R(1,2{)}_C}=F^{(1,2,3{)}_R(1,2,3{)}_C}.$

$F+101=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}\right]=F^{(1,3{)}_R(1,3{)}_C}=F^{(1,3,2{)}_R(1,3,2{)}_C}.$

where ${\pi }_R$ and ${\sigma }_C$ denote permutations of the rows and columns of the matrix, respectively, expressed in cycle notation.

• For any $n\ge 3$ another example of a cwatset is $K_n$, which has $n$-by-$n$ matrix representation

$K_n=\left[\begin{array}{cccccc}0& 0& 0& \cdots & 0& 0\\ 1& 1& 0& \cdots & 0& 0\\ 1& 0& 1& \cdots & 0& 0\\ & & & ⋮& & \\ 1& 0& 0& \cdots & 1& 0\\ 1& 0& 0& \cdots & 0& 1\end{array}\right].$

Note that for $n=3$, $K_3=F$.

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

$W=\left[\begin{array}{ccc}0& 0& 0\\ 1& 0& 0\\ 1& 1& 0\\ 1& 1& 1\\ 0& 1& 1\\ 0& 0& 1\end{array}\right].$

Properties

Let $C\subset {\mathbb{Z}}_2^n$ 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 $2^n!$.

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 $h\in H$, there exists a ${\varphi }_h\in \text{Aut}(G)$ such that ${\varphi }_h(h)\cdot H={\varphi }_h(H)$.

Furthermore, a GC-set H ⊆ G is a cyclic GC-set if there exists an $h\in H$ and a $\varphi \in \text{Aut}(G)$ such that $H=h_1,h_2,...$ where $h_1=h$ and $h_n=h_1\cdot \varphi (h_{n-1})$ for all $n>1$.

Examples

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

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 $p^q$ which divides the order of H, H contains sub-GC-sets of orders p,$p^2$,...,$p^q$. (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

• Template:Citation.
• 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]