[r-t] Bobs only Erin Triples (was: Composition search)

Alexander Holroyd holroyd at math.ubc.ca
Sat Nov 28 20:11:24 UTC 2015

Hi Richard,

This sounds very exciting - I have meaning to do something along these 
lines for years, but have not got around to it.

But I'm a bit confused by your assertion that none of these searches even 
produced a set of mutually true blocks.  There are a bunch of sets of 
mutually true blocks for various part end groups.  For example, 
composition number 5 (by PABS) in PABS's Collection 
(http://www.ringing.info/stedman.pdf) is based on a single bobs-only 
10-part block, and about 20 years ago I came up with several sets of 
7-part block sets in which the extent is divided into an _odd_ number of 
bobs-only blocks - not joinable, alas).


On Sat, 28 Nov 2015, Richard Smith wrote:

> Philip Earis wrote:
>> I think Richard has ruled out a perfect 7-part composition, and possibly 
>> further - I'm sure he'll be able to confirm.
> As I mentioned the other day, I'm not sure I did. I looked at the rather 
> meagre notes I made when I last investigated this, and there's no indication 
> that I did eliminate it and I made several comments about it perhaps being 
> beyond the scope of a reasonable search.
> So I decided to take another look at it.  The code I wrote on Wednesday is 
> considerably better than any of the previous generations of search code I've 
> used, in a significant part because I cracked the problem of how to do 
> efficient rotation pruning in a multi-part search and in doing so came up 
> with a good way of parallelising the search.
> As I speculated on Wednesday, this is done by applying the normal one-part 
> rotation pruning algorithm to a multi-part search, and repeating for each 
> conjugate part-end group. In the case of the 7-part search, there are 120 
> conjugate part-end groups which naturally divides the search space into 120 
> roughly equal chunks.  This is much more even division than dividing by 
> search prefix, especially in the presence of rotation pruning, and there was 
> less than a factor of 2.5 difference between the largest and smallest of the 
> 120 searches.  As no communication is required between 120 search processes, 
> there's no need for multi-threading, and they can be run independently on 
> separate machines.
> Increased computer speeds have helped too.  Ten years ago, which is the last 
> time I seriously studied this, I used a single-core 800 MHz processor; now 
> even my laptop has a dual-core 1.9 GHz processor, and the machines I actually 
> used had 2.66 GHz processors.  But the clock speed (and extra core) is not 
> representative of the actual speed increase, and in fact my laptop (with an 
> 1.9 Ghz Intel i3-3227U processor) ran the code about 1.95 times as fast as 
> the machines I actually used (with a 2.66 GHz Intel P8800 processor).  This 
> is because the Ivy Bridge microarchitecture in my laptop is that much faster 
> than the Penryn microarchitecture.
> On average each of the 120 search processes took 17 minutes to complete and 
> none exceeded 40 minutes.  No blocks were found.
> I also checked all larger part-end groups. The part-end group cannot contain 
> any elements conjugate to the in-course falseness (i.e. a simple 3-cycle) 
> which severely limits the available part structures.  If a multi-part 
> bobs-only extent of Erin exists, then the number of parts
> must be one of 168, 60, 24, 21, 20, 12, 10, 8, 7, 6, 5, 4, 3, 2 or 1.  I have 
> now eliminated the 7-part and all larger options.  None even produced a set 
> of mutually true blocks.
> In fact, I think we can rule out several of these structures on Q-set 
> grounds: specifically the 168, 60, 24 and 8 part structures.  But I'd need to 
> think a bit harder about it to be certain.  The point is moot anyway.
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net

More information about the ringing-theory mailing list