Thursday 12 June 2014

Feeler Gauges and Magic Circles

I recently came across Sunday Times Teaser puzzle, 777 on Brian Gladman's Puzzling In Python site:
I have half-a-dozen feeler gauges on a ring like keys on a key ring. They are attached in a certain order and by selecting a single gauge or combinations of adjacent gauges it is possible to measure from 1 to 31 thousandths of an inch (thou) inclusive in steps of 1 thou. If I remove two adjacent gauges, replace them with a single gauge and rearrange the five on the ring I can now measure from 1 to 21 thou inclusive in steps of 1 thou with these five gauges by again selecting a single gauge or combinations of adjacent gauges.

What are the thicknesses of the gauges and the order of arrangement on the ring in each case? (start with gauge of unit thickness and then its thinner neighbour for the sets).
The puzzle is based on some interesting but relatively obscure mathematics, Perfect Difference Sets, described in A Theorem in Finite Projective Geometry and Some Applications to Number Theory, James Singer, Transactions of the American Mathematical Society Vol. 43, No. 3 (May, 1938), pp. 377-385, but initially analysed by the splendidly titled Rev. Thomas P. Kirkman, A.M., F.R.S., Rector of Croft with Southworth, and Honorary Member of the Literary and Philosophical Society of Manchester, in a paper entitled On the Perfect r-Partitions of $r^2-r+1$, Transactions of the Historical Society of Lancashire and Cheshire, vol 9 (1857), pp 127-142.

The puzzle is slightly contrived, as in reality feeler gauges allow non-adjacent gauges to be combined. The restriction of using only adjacent gauges makes the puzzle equivalent to finding Perfect Difference Sets of length 5 and 6.

Perfect Difference Sets

A Perfect Difference Set (PDS)  is a set of $k+1$ residues ${a_1,...,a_{k+1}}$ modulo $n=k^2+k+1$ such that every nonzero residue can be uniquely expressed in the form $a_i - a_j$

For example, the set {0,1,4,6} is a perfect difference set for $n=3^2+3+1=13$.

A PDS can also be expressed as the sequence of gaps between successive numbers in the sorted PDS with $n=k^2+k+1$ added to the set. For the PDS {0,1,4,6} the sequence of gaps is 1,3,2,7. If the sequence is wrapped round (as in feeler gauges on a ring), sums of adjacent numbers produce all the numbers from 1 to 13. These sequences will be referred to as magic circles.






Magic Circles

The article Magic Circles, David A. James, Mathematics Magazine, Vol. 54, No. 3 (May, 1981), pp. 122-125, describes a related puzzle, where Evariste Galois challenges 18 soldiers to arrange themselves around a circular pond with circumference 307 (=$17^2+17+1$) paces so that the number of paces between any two soldiers is unique. The soldiers would of course form a PDS to achieve this.

The article describes an algorithm to construct a PDS for $p^s+1$ numbers (prime p), using Galois fields (a.k.a. finite fields), and explains the mathematics behind the algorithm. The steps are:
  1. Construct the Galois Field $GF(p^{3s})$, by finding an irreducible polynomial over GF(p) of degree $3s$.

    For s=1 this is straightforward, as a reducible polynomial of degree 3 always has a factor of degree one, so a polynomial $I(x)$ of degree 3 is irreducible if and only if $ I(x) \ne 0$ mod p for $x = 0,...,p-1$.

    For $s >  1$, finding an irreducible polynomial of degree 3s is more involved, so I cheated and pre-programed some that I obtained from the University of Victoria's Polynomial Generator
  2. Find a generator, $g$ of the related cyclic group $GF^*(p^{3s})$.

    This is best done by making random guesses. I tested guesses by brute force, checking that $g^i  \ne 1$ for $1 \leq i \leq p^{3s}/2$. Typically a generator is found in one or two guesses.

  3. Find elements of the subgroup $GF^*(p^s)$ in $GF^*(p^{3s})$

    These are the elements $g^i$ for values of $i$ that are multiples of $p^{2s}+p^s+1$ = $\frac{p^{3s}-1}{p^s-1}$
  4. Find integers $i$ that satisfy $g^i - g \in GF^*(p^s)$ .
  5. These integers, modulo $p^{2s}+p^s+1$ , together with zero, form a PDS for $p^s+1$

This algorithm will find a single PDS. Other PDS's of the same order can be found by multiplying this PDS by each number between 1 and $ p^{2s}+p^s+1$ that is coprime to $p^{2s}+p^s+1$.

Each PDS found can be be coverted to a magic circle, which can then be arranged to start with 1 followed by its smaller neighbour. Different PDS's can result in the same magic circle when this rearrangement is applied. For all the cases that I have tested, each magic circle is created by $3s$ different PDSs.

In fact, Golay, in Notes on the Representation of 1,2, ……, N by differences, J. London Math. Soc. (1972) s2-4 (4): 729-734, claims that there are $ \frac{\phi(p^{2s}+p^s+1)}{3s}$ magic circles.


Python Code

Python code is located in this folder. The folder contains:

finitefield.py -  implements Galois fields, representing polynomials $a_0+a_1x+...+a_nx^n$ by a python list $[a_0,a_1,...,a_n]$. The module contains procedures to multiply, divide, add, subtract polynomials modulo a prime and to multiply polynomials modulo an irreducible. The module also contains procedures to find an irreducible polynomial (for a limited range of $p^n$) and to find a generator of  $GF^*(p^n)$

magiccircles.py - implements the algorithm described above and uses the algorithm to solve the Sunday Times Teaser, and to generate magic circles for a range of values including $17^1+1 =18$, Evarise Galois' soldiers.  My algorithm eliminates reflections, producing $ \frac{\phi(p^{2s}+p^s+1)}{6s}$ magic circles.