Property of subsets of an algebraic structure
Closure with a twist is a property of
subsets of an
algebraic structure. A subset
of an algebraic structure
is said to exhibit closure with a twist if for every two elements
![{\displaystyle y_{1},y_{2}\in Y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ca8601678cc86201c9b64571de2e3ef335e5a53)
there exists an
automorphism
of
and an
element
such that
![{\displaystyle y_{1}\cdot y_{2}=\phi (y_{3})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92f495741a32abeea4eb031f80b243dea85d1ec3)
where "
" is notation for an
operation on
preserved by
.
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
. 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,
, acts on
by bit permutation:
![{\displaystyle p((c_{1},\ldots ,c_{n}))=(c_{p(1)},\ldots ,c_{p(n)}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac6d926547ac3c4fcd756b7f1efadd285f0d4a9b)
where
is an element of
and p is an element of
. Closure with a twist now means that for each element c in C, there exists some
permutation
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
![{\displaystyle \forall c\in C:\exists p_{c}\in {\text{Sym}}(n):\forall e\in C:p_{c}(e+c)\in C.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0055451727a3dec1cbe0ca7e51b50bff5e659156)
This condition can also be written as
![{\displaystyle \forall c\in C:\exists p_{c}\in {\text{Sym}}(n):p_{c}(C+c)=C.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f069303a4e0b18bc87e8460731e96b8fb5ddf1c)
Examples
- All
subgroups of
— that is, nonempty subsets of
which are
closed under addition-without-carry — are trivially cwatsets, since we can choose each permutation pc 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
![{\displaystyle F={\begin{bmatrix}0&0&0\\1&1&0\\1&0&1\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a287cc6d1cb2c6998de023a25a9654eaf03de2b)
To see that F is a cwatset using this notation, note that
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c964939526d3fcd8de35cff67540b754dadcafa6)
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d0b358b82b80d51d76a026987bea062600b568c)
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50cc03c6c88321af9d5cba4b56265632ee9fc6df)
where
and
denote
permutations of the rows and columns of the matrix, respectively, expressed in
cycle notation.
- For any
another example of a cwatset is
, which has
-by-
matrix representation
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f13bb3a996ad36f0154d9260dd232fdd318ac705)
Note that for
,
.
- An example of a nongroup cwatset with a rectangular matrix representation is
![{\displaystyle W={\begin{bmatrix}0&0&0\\1&0&0\\1&1&0\\1&1&1\\0&1&1\\0&0&1\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b2a48e0b51eca128c7cc8e70cd70c714ab119f8)
Properties
Let
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
.
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
, there exists a
such that
.
Furthermore, a GC-set H ⊆ G is a cyclic GC-set if there exists an
and a
such that
where
and
for all
.
Examples
- Any
cwatset is a GC-set, since
implies that
.
- Any
group is a GC-set, satisfying the definition with the identity automorphism.
- A non-trivial example of a GC-set is
where
.
- A nonexample showing that the definition is not trivial for subsets of
is
.
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
which divides the order of H, H contains sub-GC-sets of orders p,
,...,
. (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,
JSTOR
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]