[r-t] Decisions / Algorithms for generating the extent

[Richard Smith]

Don Morrison wrote:

> Am I correct in believing that for more than three bells, three
> different changes is the minimum that can ever be used to generate an
> extent?
>
> That's assuming ordinary changes, not jump changes.

Yes, that's correct.

The algorithm I just gave demonstrates that it can always be
done with three changes, and it is quite straightforward to
prove that it cannot be done with two changes when n>3.

Suppose for n>3 it can be done with two changes a and b.
Clearly the extent has to be of the form ababababab... as
two consecutive instances of the same change would
immediately be false.  This means that the touch will be
twice the order of the permutation ab.  The higest order
permutation is when you have several co-primed sized cycles.
E.g. on 7 bells, a 4 and a 3 cycle giving ab order 12 and a
24 row touch; an example being changes 145 and 7.  This
value is given by Landau's function

  http://en.wikipedia.org/wiki/Landau's_function

and it's quite easy to show that this rises more slowly than
n!.


Don Morrison wrote:

> Can it be reduced to two with jump changes?

Alexander Holroyd replied:

> I seem to remember hearing that on any number, the extent
> can be produced by 213456...n and the jump change
> 23456...n1 (Obviously the group is generated by these two,
> but I am talking about an actual extent).

This sounds highly plausible but scanning the mathematical
literature that I have to hand, this seems not to be proven.
The topic is mentioned briefly in volume 4A, chapter 7.2.1.2
of Knuth's "The Art of Computer Programming".  I've put an
early pre-print of that section here:

  <http://www.ex-parrot.com/~richard/papers/fasc2b.ps>.

Knuth quotes several relevant results [pages 21-2 in the
pre-print]:

| Nijenhuis and Wilf [Combinatorial Algorithms (1975),
| Exercise 5] noticed that all permutations can be generated
| for n = 4 if we replace a_1 a_2 a_3 ... a_n at each step
| by either a_2 a_3 ... a_n a_1 or a_2 a_1 a_3 ... a_n, and
| they wondered whether such a method exists for all n.

| Ruskey, Jiang and Weston [Discrete Applied Math. 57
| (1995), 75-83] undertook an exhaustive search in the
| sigma-tau graph for n = 5 and discovered that it has
| five essentially distinct Hamiltonian circuits.  They also
| found a Hamiltonian path for n = 6.

(The sigma-tau graph to which they refer is simply the
Cayley graph of the jump change, sigma = 234...n1, and the
ordinary change, tau = 2134...n.)

| R.C. Compton and S.G. Williamson [Linear and Multilinear
| Algebra 35 (1993), 237-293] have proved that Hamiltonian
| circuits exist for all n if the three generators, sigma,
| sigma-inverse and tau are allowed instead of just sigma
| and tau.

That all sounds to me as though it is mere conjecture that
the changes 2134...n and 234...n1 can produce an extent.

Richard