Closure with a twist

Closure with a twist

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

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.

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}.

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.

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 hH, there exists a φhAut(G) such that φh(h) \cdot H = φh(H).

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

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 is H = {000, 100, 010, 001, 110}.

Properties

  • A GC-set HG always contains the identity element of G.
  • The direct product of GC-sets is again a GC-set.
  • A subset HG 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.

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]

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Twist tie — A twist tie is a metal wire encased in a thin strip of paper or plastic used to tie the openings of bags such as garbage bags or bread bags. They are often included with boxes of sandwich baggies or trash bags, and are commonly available… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Media and Publishing — ▪ 2007 Introduction The Frankfurt Book Fair enjoyed a record number of exhibitors, and the distribution of free newspapers surged. TV broadcasters experimented with ways of engaging their audience via the Internet; mobile TV grew; magazine… …   Universalium

  • Metropolitan Manila Development Authority — Pangasiwaan sa Pagpapaunlad ng Kalakhang Maynila Agency overview Formed November 7, 1975 Superseding agency …   Wikipedia

  • Craniosynostosis — Classification and external resources Child with premature closure (craniosynostosis) of the lambdoid suture. Notice the swelling on the right side of the head ICD 10 …   Wikipedia

  • performing arts — arts or skills that require public performance, as acting, singing, or dancing. [1945 50] * * * ▪ 2009 Introduction Music Classical.       The last vestiges of the Cold War seemed to thaw for a moment on Feb. 26, 2008, when the unfamiliar strains …   Universalium

  • Molecular symmetry — in chemistry describes the symmetry present in molecules and the classification of molecules according to their symmetry. Molecular symmetry is a fundamental concept in chemistry, as it can predict or explain many of a molecule s chemical… …   Wikipedia

  • Economic Affairs — ▪ 2006 Introduction In 2005 rising U.S. deficits, tight monetary policies, and higher oil prices triggered by hurricane damage in the Gulf of Mexico were moderating influences on the world economy and on U.S. stock markets, but some other… …   Universalium

  • Tangle (mathematics) — In mathematics, an n tangle is a proper embedding of the disjoint union of n arcs into a 3 ball. The embedding must send the endpoints of the arcs to 2 n marked points on the ball s boundary. Two n tangles are considered equivalent if there is an …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”