Application: Bell ringing

A good reference for this section is A. White [Wh]. Since the seventeenth century, and possibly before, cathedral bells in England have been rung by permutating the order of a ``round'' of bells. The art and study of such bell ringing is referred to as campanology. Fabian Stedman provided significant contributions to bell ringing. Born in 1640 to Reverend Francis Stedman, Fabian Stedman's connections with campanology took root at the early age of 15 when he moved to London to work as an apprentice to a Master Printer. While in London Stedman joined a bell-ringing society known as the ``Society of Colledg(sic) Youths," which has since been renamed the Ancient Society of College Youths and is still in existence today. Stedman's major contributions to campanology are reflected in his efforts on Tintinnlogia and Campanalogia, the first two books published on the subject, in 1668 and 1677, respectively. Below is a glossary of a few essential terms:

• Change: the swapping of one or more disjoint pairs of adjacent bells
• Plain change: involves swapping one pair of adjacent bells only
• Cross change: involves more than one swapping pair of bells
• Round: A ordering of the bells (i.e., a permutation of $(1, 2, 3, ... , n)$)

In the beginning, change ringing concerned itself with a single row of bells whose order could be denoted by $(1, 2, 3, ... , n)$. Considering the case where $n=6$ the concepts of plain and cross changes can be understood more clearly. If we use only plain changes we can generate permutations of the bells as follows:

$$\begin{array}{cccccc} 1& 2& 3& 4& 5& 6\\ 2& 1& 3& 4& 5& 6\\ 2& 1& 4& 3& 5& 6\\ 2& 1& 4& 3& 6& 5, \end{array}$$

It should be fairly obvious on inspection that the first plain change swaps 1 and 2, the second swaps 3 and 4, and the third swaps 5 and 6. Considering the same set of six bells acted upon by a cross change, the same result is achieved in one change, as seen below:

$$\begin{array}{cccccc} 1& 2& 3& 4& 5& 6\\ 2& 1& 4& 3& 6& 5. \end{array}$$

More useful and interesting patterns can be generated by combining plain and cross changes. The plain lead on four bells is one of the most simplistic patterns and was devised sometime around 1621 by alternating consecutive cross and plain changes as seen below:

$$\begin{array}{cccc} 1& 2& 3& 4 \\ 2& 1& 4& 3 \\ 2& ... ...\\ 3& 1& 4& 2\\ 1& 3& 2& 4\\ 1& 2& 3& 4 \end{array}$$

It is easy to see that the pattern which defines the plain lead on four bells is nothing more than a cross change followed by a plain change on the middle two bells until we reach the round, which is where we started. Generating the permutations contained in the plain lead on four bells can be easily described using the notation for permutations we have developed. We begin by representing the cross change as $a=(1, 2)(3, 4)$, which swaps the first two and last two bells, and representing the plain change as $b=(2, 3)$, which swaps the middle pair. We begin with the first element, $a$. To generate the next permutation we multiply this first element by $b$. To generate the third element we simply multiply this second term, $ab$, by $a$ to get $aba$. Continuing on in this manner we multiply alternately by $a$ then $b$ to generate the set $D_4=\{a,ab,aba,(ab)^2,a(ab)^2,(ab)^3,(ab)^3a,(ab)^4\}$. This is the set of permutations in the plain lead on four bells. (It is denoted $D_4$ here for reasons which will be explained later. Since $(ab)^4$ yields the original round, we say $(ab)^4=1$ and $D_4=\{1,a,ab,aba,(ab)^2,a(ab)^2,(ab)^3,(ab)^3a\}$. Now for a more complex example. We turn our attention now to the composition which is commonly referred to as Plain Bob Minimus. Plain Bob Minimus begins at the round and ends at the round $(1, 2, 3, 4)$ and contains all possible permutations of these four bells (in a particular order, described below):

            1 2 3 4         1 3 4 2         1 4 2 3 
            2 1 4 3         3 1 2 4         4 1 3 2
            2 4 1 3         3 2 1 4         4 3 1 2
            4 2 3 1         2 3 4 1         3 4 2 1
            4 3 2 1         2 4 3 1         3 2 4 1
            3 4 1 2         4 2 1 3         2 3 1 4
            3 1 4 2         4 1 2 3         2 1 3 4
            1 3 2 4         1 4 3 2         1 2 4 3
                                            1 2 3 4

We can now describe this composition using the permutation notation as we did for the plain lead on four bells. Let $a=(1, 2)(3, 4)$ and $b=(2, 3)$ represent possible changes between rows. If we look at the first column of the Plain Bob Minimus composition, we see that it is nothing more than the plain lead on four bells. To generate the second column, we introduce a new permutation $c=(3,4)$ and we simplify our notation by letting $k=(ab)^3ac$. Multiplying through we generate the second column,

$$\{k,ka,kab,kaba,k(ab)^2,ka(ab)^2,k(ab)^3,k(ab)^3a\}.$$

Multiplying through by $k$ again, we generate the third column,

$$\{k^2,k^2a,k^2ab,k^2aba,k^2(ab)^2,k^2a(ab)^2,k^2(ab)^3,k^2(ab)^3a\}.$$

This generation of Plain Bob Minimus shows that it can be expressed as the disjoint union of ``translations'' of the plain lead on four bells! We shall explain this fact using group theory in the next chapter. Now, since we chose $a=(1, 2)(3, 4)$, $b=(2, 3)$, and $c=(3,4)$, where $b$ and $c$ are obviously by definition 2-cycle or transpositions and $a$ is the product of two such $2$-cycles or transpositions, we have shown a further result, that each permutation of ${\Bbb{Z}}_4$ can be written as a product of 2-cycles. More generally, we can state the following theorem originally due to H. Steinhaus.

Theorem 4.7.1   Let $f$ be a member of $S_n$, i.e., let $f$ be any permutation of degree $n$. Then $f$ can be written as a product of transpositions.

To sketch a proof of this theorem (following [G]) and hence prove Theorem 4.5.1 as promised, we need only to recall that: Every permutation of $S_n$ can be written uniquely (up to order) as a product of disjoint cycles (Theorem 4.4.6). proof: It is a fact that any $k$-cycle can be written as a product of $k-1$ transpositions,

$$(a_1, a_2, ... ,a_k)=(a_1, a_k)(a_1, a_{k-1}) ... (a_1, a_2).$$

(This can be proven by mathematical induction. The argument is left to the reader.) We see that since any permutation can be written in terms of cycles and any cycle can be written as product of transposition, it follows that every permutation of ${\Bbb{Z}}_n$ can be written as a product of transpositions. $\Box$