[r-t] FW: A compositional question I am hoping a change-ringing theorist could help with! (re-sending)

[Mark Davies]

Thank you Philip for the "Bucephalus" reference. I will accept this as a 
suitably classical yet virile eponym...

Anyway, this is interesting. So Mark's rows are really derived from a 
pattern in the deltas or intervals between the numbers, not the numbers 
themselves; the first derivative, if you will. It seems worth exploring 
the relationship bewteen this original pattern and the circular 
permutations in the numbers themselves which I found last time.

So, we are talking clock arithmetic here, modulus 7. The basic set of 
numbers is {1...7}, leaving the 4 in for now. The biggest difference 
between any two numbers in this set (modulo 7) is 3 or -3, equivalent to 
Mark's ascending or descending fourth. As he says, there are six 
possible deltas between numbers, ignoring 0: {-3, -2, -1, +1, +2, +3}. 
His "EIR" rows are then generated when we manage to use all six deltas 
to visit six distinct numbers, and return to the number we started with.

An example is:

    +1, +3, +2, -1, -2, -3

If we start at 1, this sequence of deltas gives us:

    1, 2, 5, 7, 6, 4, 1

This works, in that we have visited six different numbers and returned 
to the start, but doesn't match Mark's criteria exactly because we have 
included the forbidden 4. But that's fine, because, for any successful 
sequence of deltas, there is always one particular number we can pick to 
start on which then avoids the 4. You can find the correct starting 
number by identifying the one number, x, from the set {1..7} *not* 
visited by the sequence. Add (4-x) to your original starting number and 
you're away. In this case, x=3, so we add one to our original number, 
and start from 2:

    2, 3, 6, 1, 7, 5, 2

And that is a row on Mark's EIR list: rotated, it is 175236. (Notice how 
6+2 = 1 and 1-1 = 7 in this base-7 clock arithmetic).

So basically we can generate EIRs simply by finding the permutations of 
(-3, -2, -1, +1, +2, +3) which obey the two rules:

  (a) they must visit 6 different numbers;
  (b) they must end on the same number as they began.

In fact, (b) is always true, because if you add up -3, -2, -1, +1, +2, 
+3 you get 0, so the total delta is always zero. So that's easy!

And in fact this does look a lot more like changeringing, now. The 
deltas are a bit like different permuations - place notations, or 
leadhead permutations perhaps - and the individual numbers are whole 
changes, more like node numbers in terms of computer composition search 
engines. Imagine a graph with the seven numbers as nodes, and with six 
edges emanating from each node, representing the six possible deltas and 
where you end up if you apply each. I can't easily draw that in plain 
text, but here's a bit of it, showing the number 1 as a node with its 
connections:


              7   2
          (-1)|   |(+1)
               \ /
     6 - (-2) - 1 - (+2) - 3
               /
          (-3)|
              5    4 missing because it's forbidden!

The sequences of deltas we are looking for are (I think) in mathematical 
language Hamiltonian cycles of the complete graph, or in bellringing 
terms, true extents. In fact, this looks to me very much like the 
bellringing problem of getting a course of spliced Major from six 
methods with different leadhead orders. The set of deltas {-3...+3} 
corresponds to the leadhead orders (a..f) and the numbers {1..7} 
correspond to the 7 plain bob leadheads at the Major stage. Example 
methods might be Lancashire, Yorkshire, Adelaide, Ashtead, Silchester 
and London; my example sequence of deltas +1, +3, +2, -1, -2, -3 then 
corresponds to this 6-lead course:

   2345678
   3527486  Lancashire
   8674523  Adelaide
   4263857  Yorkshire
   6482735  London
   7856342  Silchester
   2345678  Ashtead

Anyway, so the next question is, how many sequences of methods (deltas) 
are there which give us a true six lead course (an EIR)?

This is pretty easy to calculate. The only reason a sequence can fail is 
if it comes back to the starting number too early (comes round too 
soon). There are only two ways this can happen:

1. If you have a delta and its inverse next to each other: -2, +2 is 
obviously bad. There are six of these bad pairs, if you count e.g. -1, 
+1 and +1, -1 separately.

2. There are also two sets of three deltas which bring you back to the 
start: (+1, +2, -3) and the reverse (-1, -2, +3). They are the only 
triplets which add up to 0, modulus 7. You can each set in any order, so 
there are a total of 6 x 2 = 12 "bad triplets".

And that's it. Logically, if you have a sequence of 6 deltas in which 
the first four bring you back to the start, well the last two must be a 
bad pair. And you can't possibly have a sequence of 5 that comes back, 
because you have one delta left over and they must all add up to 0. So 
the two cases above are enough to weed out all bad sequences.

There are 6! = 720 different sequences of 6 deltas, but taking rotations 
out of the equation we are left with 5! = 120. Let's exclude the bad 
sequences one by one:

a) There are 2x2x2x2=16 sequences with all three bad pairs:
     -1, +1, -2, +2, -3, +3
and the 8 swaps within the pairs plus the reversal
     -1, +1, -3, +3, -2, +2
and its 8 swaps.

b) There are 3x2x2x2=24 sequences with two bad pairs:
     -1, +1, -2, -3, +3, +2
with 8 swaps, plus 3 versions of this with a different pair split up.

c) There are 3x2x2x2x2=48 sequences with just one bad pair:
     -1, +1, -2, -3, +2, +3
with 8 swaps, then change over 2s and 3s for 8 more, then do the same 
again with 2 and then 3 as the bad pair together.

d) That leaves just the sequences with bad triplets but *no* bad pairs. 
There are 6x3=18 of these. If you have one bad triplet (e.g. +1,+2,-3), 
you always have the other one too, because exactly those deltas are left 
over (-1,-2,+3). You can choose the first triplet in 6 ways, i.e. any 
order, but there are only three rotations of the second triplet that 
don't generate a bad pair where the two triplets meet.

So that is a total of 16+24+48+18=106 sequences which are ruled out. 
That leaves 120-106 = 14 good ones! Exactly the number of EIRs which 
Mark found.

The question remaining is, from my circle diagram of the previous email 
it seemed obvious that two of the fourteen rows were "special". It's not 
so obvious to me why, or even if, two of the fourteen delta sequences 
are special.

However, there is still a unique property in the delta sequences that 
correspond to the special rows. Most sequences look like this:

    +1, +2, -1, -3, -2, +3

The special sequences take the form:

    1,  a,  b,  -1, -a, -b

where a and b are +-2 or +-3. In other words, a delta and its inverse 
are always at opposite ends of the sequence (viewed as a circle):

               1
           -b     a
           -a     b
              -1

There are actually only two such sequences which work:

    +1, +3, +2, -1, -3, -2
    +1, -2, -3, -1, +2, +3

Any other possibilites, e.g. +1, +2, +3, -1, -2, -3 fail because they 
break down into bad triplet in them - in this case (+3, -1, -2) = 0 and 
(-3, +1, +2) = 0.

Does this tell us anything? Hopefully some proper mathematicians will 
come back from their extended tea-drinking session and put us out of our 
misery. ;-)

MBD