en>David Eppstein: source

2014-05-12T00:01:53Z

source

en>SmackBot: Date maintenance tags and general fixes

2009-04-22T19:56:03Z

Date maintenance tags and general fixes

New page

{{Expert-subject|Mathematics|date=November 2008}}
'''Closure with a twist''' is a property of [[subset]]s of an [[algebraic structure]]. A subset <math>Y</math> of an algebraic structure <math>X</math> is said to exhibit '''closure with a twist''' if for every two elements

:<math> y_1, y_2 \in Y</math>

there exists an [[automorphism]] <math>\phi</math> of <math>X</math> and an [[element (mathematics)|element]] <math>y_3 \in Y</math> such that
:<math> y_1 \cdot y_2 = \phi(y_3)</math>

where "<math>\cdot</math>" is notation for an [[Operation (mathematics)|operation]] on <math>X</math> preserved by <math>\phi</math>.

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

==Cwatset==
In mathematics, a '''cwatset''' is a [[Set (mathematics)|set]] of [[bitstring]]s, all of the same length, which is '''c'''losed '''w'''ith '''a''' '''t'''wist.

If each string in a cwatset, ''C'', say, is of length ''n'', then ''C'' will be a subset of '''Z'''2''n''. Thus, two strings in ''C'' are added by adding the bits in the strings [[modular arithmetic|modulo]] 2 (that is, addition without carry, or [[exclusive disjunction]]). The symmetric group on ''n'' letters, Sym(''n''), acts on '''Z'''2''n'' by bit permutation:
:::''p''((''c''1,...,''c''n))=(''c''''p''(1),...,''c''''p''(n)),
where ''c''=(''c''1,...,''c''n) is an element of '''Z'''2''n'' 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]] ''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]]
:::<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 [[subgroup]]s of '''Z'''2''n'' — that is, nonempty subsets of '''Z'''2''n'' which are [[Closure (mathematics)|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

:::<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 [[permutation]]s 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 ''C'' <math>\subset</math> '''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 (group theory)|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''''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 (mathematics)|group]] ''G'' is a ''GC-set'' if for each ''h'' ∈ ''H'', there exists a <math>\phi_h</math> ∈ ''Aut(G)'' such that <math>\phi_h</math>''(h)'' <math>\cdot</math> ''H'' = <math>\phi_h</math>''(H)''.

Furthermore, a GC-set ''H'' ⊆ ''G'' is a ''cyclic GC-set'' if there exists an ''h'' ∈ ''H'' and a <math>\phi</math> ∈ ''Aut(G)'' such that ''H = {''<math>h_1, h_2, ...</math>''}'' where <math>h_1</math> ''= h'' and <math>h_n</math> ''='' <math>h_1</math> <math>\cdot</math> <math>\phi</math>''(''<math>h_{n-1}</math>'')'' for all ''n > 1''.

=== Examples ===

*Any [[cwatset]] is a GC-set since ''C + c = ''<math>\pi</math>''(C)'' implies that <math>\pi^{-1}</math>''(c) + C = ''<math>\pi^{-1}</math>''(C)''.
*Any [[group (mathematics)|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'' = <math>Z_{10}</math>.
*A nonexample showing that the definition is not trivial for subsets of <math>Z_2^n</math> 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 (group theory)|Lagrange's Theorem]]: The [[order (group theory)|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 (mathematics)|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 group|cyclic]] if and only if it is the projection of a [[cyclic subgroup]] of ''Aut(G)''⋉''G''.

==References==
* {{citation | doi=10.2307/2690684 | first1=Gary J. | last1=Sherman | first2=Martin | last2=Wattenberg | year=1994 | title=Introducing … cwatsets! | jstor=2690684 | journal=[[Mathematics Magazine]] | volume=67 | pages=109–117 | issue=2 }}.
* 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]

[[Category:Abstract algebra]]
{{DEFAULTSORT:Closure With A Twist}}

Binary combinatory logic - Revision history

en>David Eppstein: source

en>SmackBot: Date maintenance tags and general fixes