String Algebra

Given a group G of order g, let U denote the set of all ordered multi-
sets of elements of G. Elements of U are called "strings", and the 
number of components in a string q is called the "length" of q.  A 
string consisting only of t repetitions of the identity element of G is 
signified by I_t and is called a "null string".  Let V denote the subset 
of U consisting of multi-sets with exactly g components, and let A 
denote the subset of V consisting of multi-sets of exactly g DISTINCT 
components.  

For any string q of length t, and any integer d that divides t, we 
define the "contraction" C(q,d) as the ordered set of elements of G 
given by cumulative compositions of the components of q taken in t/n 
sets of n consecutive components.  For example, if q consists of 
{q1, q2, q3, q4, q5, q6} then C(q,2) is defined as {q1q2, q3q4, q5q6}.

Also for any string q and any integer k we define the "rotation" 
R(q,k) as the string consisting of the components of q all shifted k 
places to the left, wrapping the leftmost element to the rightmost 
place with each shift.  Thus, with q as above, the string R(q,2) is 
given by {q3, q4, q5, q6, q1, q2}.

The "successor" of any string q of length t is defined as the string

             S(q)  =  {C(R(q,k),t), k=0,1,..,t}

We will denote j iterations of the successor function beginning with q 
as S(q,j).

These strings of group elements have many interesting algebraic 
possibilities with various operations.  For example, given two 
strings 

        p = {p1, p2,...pj}          q = {q1, q2, ...,qk} 

of length j and k respectively, we can define a string of length k + j 
by the catenation

           p + q = {p1, p2,..., pj, q1, q2, ..., qk}

and a string of length kj by the compositional "cross product"

 p x q = {p1q1,p1q2,..,p1qk,p2q1,p2q2,..,p2qk,..,pjq1,pjq2,..,pjqk}

If k = j we also have the "interleaving" operation

             p # q  =  {p1, q1, p1, q2, ..., pk, qk}

and the "dot product" defined by

                 pq  =  {p1q1, p2q2, ..., pkqk}

These operations, together with the contraction, rotation, and 
successor functions defined above, produce a very interesting 
algebraic structure.

Return to MathPages Main Menu