Closure with a twist

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 Z₂ⁿ. 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 Z₂ⁿ by bit permutation:

where c=(c₁,...,c_n) is an element of Z₂ⁿ 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

This condition can also be written as

Examples

All subgroups of Z₂ⁿ — that is, nonempty subsets of Z₂ⁿ which are 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

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

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

For any n ≥ 3 another example of a cwatset is K n , which has n -by- n matrix representation

Note that for n = 3 , K 3 = F .

An example of a nongroup cwatset with a rectangular matrix representation is

Properties

Let C ⊂ Z₂ⁿ 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 2ⁿ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 G is a GC-set if for each h ∈ H, there exists a ϕ h ∈ Aut(G) such that ϕ h (h) ⋅ 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 = { h 1 , h 2 , . . . } where h 1 = h and h n = h 1 ⋅ ϕ ( h n − 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 = Z 10 .

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 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 p q which divides the order of H, H contains sub-GC-sets of orders p, p 2 ,..., p q . (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.