In mathematics, closure with a twist is an algebraic condition describing a subset that maps onto itself ("closure"), not necessarily identically, but under a group automorphism (a "twist") when acted upon by one of its own elements.
Formally, a subset <math>H</math> of a group <math>G</math> is said to exhibit closure with a twist if each of its cosets is an image of <math>H</math> under some automorphism of <math>G</math>. That is, for every element <math>h \in H</math>, there exists an automorphism <math>\phi_h</math> of <math>G</math> such that:
:<math>H \cdot h = \phi_h(H)</math>
where "<math>\cdot</math>" denotes the group operation on <math>G</math>, and <math>\phi_h(H)</math> is the image of the entire subset <math>H</math> under the automorphism <math>\phi_h</math>.
("Coset" here is used loosely, as this concept is interesting when <math>H</math> is not itself a group.)
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>\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>\text{Sym}(n)</math>, acts on <math>\mathbb{Z}_2^n</math> by bit permutation:
:::<math>p((c_1, \ldots, c_n)) = (c_{p(1)}, \ldots, c_{p(n)}),</math>
where <math>c = (c_1, \ldots, c_n)</math> is an element of <math>\mathbb{Z}_2^n</math> and p is an element of <math>\text{Sym}(n)</math>. Closure with a twist now means that for each element c in C, there exists some permutation <math>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>+</math>, C will be a cwatset if and only if
:::<math>\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>\forall c\in C : \exists p_c\in \text{Sym}(n) : p_c(C+c)=C.</math>
Examples
- All subgroups of <math>\mathbb{Z}_2^n</math> — that is, nonempty subsets of <math>\mathbb{Z}_2^n</math> which are closed under addition-without-carry — are trivially cwatsets, since we can choose each permutation p<sub>c</sub> 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> 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> 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> 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> 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> \pi_R</math> and <math> \sigma_C</math> denote permutations of the rows and columns of the matrix, respectively, expressed in cycle notation.
- For any <math> n \geq 3 </math> another example of a cwatset is <math> K_n </math>, which has <math>n</math>-by-<math>n</math> matrix representation
:::<math> 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> n = 3</math>, <math>K_3=F</math>.
- An example of a nongroup cwatset with a rectangular matrix representation is
:::<math> 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>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>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>h\in H</math>, there exists a <math>\phi_h\in\text{Aut}(G)</math> such that <math>\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>h\in H</math> and a <math>\phi\in\text{Aut}(G)</math> such that <math>H = {h_1, h_2, ...}</math> where <math>h_1 = h</math> and <math>h_n = h_1 \cdot \phi(h_{n-1})</math> for all <math>n > 1</math>.
Examples
- Any cwatset is a GC-set, since <math>C + c = \pi(C)</math> implies that <math>\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>H = {0, 2}</math> where <math>G = Z_{10}</math>.
- A nonexample showing that the definition is not trivial for subsets of <math>Z_2^n</math> is <math>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>p^{q}</math> which divides the order of H, H contains sub-GC-sets of orders p,<math>p^{2}</math>,...,<math>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
- .
- 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 [http://www.rose-hulman.edu/mathjournal/archives/2003/vol4-n2/paper7/v4n2-7pd.pdf]