Closure with a twist

From Wikipedia, the free encyclopedia

 This article or section is in need of attention from an expert on the subject.

WikiProject Mathematics or the Mathematics Portal may be able to help recruit one.

If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

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 φ of X and an element y_3 \in Y such that

y_1 \cdot y_2 = \phi(y_3)

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

Two examples of algebraic structures with the property of closure with a twist are the cwatset and the GC-set.

Contents

[edit] 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 Z2n. 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, Sym(n), acts on Z2n by bit permutation:

p((c1,...,cn))=(cp(1),...,cp(n)),

where c=(c1,...,cn) is an element of Z2n and p is an element of Sym(n). Closure with a twist now means that for each element c in C, there exists some permutation pc 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

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

This condition can also be written as

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

[edit] Examples

  • All subgroups of Z2n — that is, nonempty subsets of Z2n 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
F = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}.

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

F + 000 = \begin{bmatrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} = F^{id}=F^{(2,3)_R(2,3)_C}.
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}.
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}.

where πR and σC denote permutations of the rows and columns of the matrix, respectively, expressed in cycle notation.

  • For any n \geq 3 another example of a cwatset is Kn, which has n-by-n matrix representation
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}.

Note that for n = 3, K3 = F.

  • An example of a nongroup cwatset with a rectangular matrix representation is
W = \begin{bmatrix} 0 & 0 & 0\\ 1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix}.

[edit] Properties

Let C \subset Z2n 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 2nn!

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

[edit] 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.

[edit] Definitions

A subset H of a group G is a GC-set if for each h ∈ H, there exists a φh ∈ Aut(G) such that φh(h) \cdot H = φh(H).

Furthermore, a GC-set H ⊆ G is a cyclic GC-set if there exists an h ∈ H and a φ ∈ Aut(G) such that H = {h1,h2,...} where h1 = h and hn = h1 \cdot φ(hn − 1) for all n > 1.

[edit] Examples

  • Any cwatset is a GC-set since C + c = π(C) implies that π − 1(c) + C = π − 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 = Z10.
  • A NONEXAMPLE (showing that the definition is not trivial for subsets of Z_2^n): H = {000, 100, 010, 001, 110}.

[edit] 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 pq which divides the order of H, H contains sub-GC-sets of orders p,p2,...,pq. (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.

[edit] References

  • Sherman, Gary J. & Wattenberg, Martin (1994), “Introducing … cwatsets!”, Mathematics Magazine 67 (2): 109–117 .
  • 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. Bliss, 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]