September 2001
This month's entry is more of a research problem than a puzzle. It was originally proposed by Thomas Schwentick.
For a given N, find upper and lower bounds on the size of the largest group G of permutations on N elements (0,1,...,N-1) such that each element g of G, when composed with the particular N-cycle (0->1->2->...->(N-1)->0), yields another N-cycle.
Terminology: a group G of permutations is a set of permutations such that the composition of any two elements of G is again in G. A cycle is written (a,b,c), meaning that (a goes to b, b goes to c, c goes to a). An N-cycle is a permutation of the form (a,b,c,...,h), which cycles through all N elements before returning to "a".
When N is a power of 2, we know that a group G of size (2**N)/(2N) exists, as exemplified here with N=8. G has 2**8/(2*8)=256/16=16 elements.
Each element g is represented here first by a row, showing in order g(0),g(1),...,g(7), followed by the more traditional cycle notation.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | (0)(1)(2)(3)(4)(5)(6)(7) | |
| 0 | 1 | 6 | 7 | 4 | 5 | 2 | 3 | (0)(1)(2,6)(3,7)(4)(5) | |
| 0 | 5 | 2 | 7 | 4 | 1 | 6 | 3 | (0)(1,5)(2)(3,7)(4)(6) | |
| 0 | 5 | 6 | 3 | 4 | 1 | 2 | 7 | (0)(1,5)(2,6)(3)(4)(7) | |
| 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 | (0,2)(1,3)(4,6)(5,7) | |
| 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | (0,2,4,6)(1,3,5,7) | |
| 2 | 7 | 0 | 5 | 6 | 3 | 4 | 1 | (0,2)(1,7)(3,5)(4,6) | |
| 2 | 7 | 4 | 1 | 6 | 3 | 0 | 5 | (0,2,4,6)(1,7,5,3) | |
| 4 | 1 | 2 | 7 | 0 | 5 | 6 | 3 | (0,4)(1)(2)(3,7)(5)(6) | |
| 4 | 1 | 6 | 3 | 0 | 5 | 2 | 7 | (0,4)(1)(2,6)(3)(5)(7) | |
| 4 | 5 | 2 | 3 | 0 | 1 | 6 | 7 | (0,4)(1,5)(2)(3)(6)(7) | |
| 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | (0,4)(1,5)(2,6)(3,7) | |
| 6 | 3 | 0 | 5 | 2 | 7 | 4 | 1 | (0,6,4,2)(1,3,5,7) | |
| 6 | 3 | 4 | 1 | 2 | 7 | 0 | 5 | (0,6)(2,4)(1,3)(5,7) | |
| 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | (0,6,4,2)(1,7,5,3) | |
| 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 | (0,6)(2,4)(1,7)(3,5) |
As an example of the group law, the composition of the fourth and fifth elements,
(0)(1,5)(2,6)(3)(4)(7) and (0,2)(1,3)(4,6)(5,7)
is (0,2,4,6)(1,7,5,3), since
(0 maps to 0 maps to 2),
(1 maps to 5 maps to 7),
(2 maps to 6 maps to 4),
(3 maps to 3 maps to 1),
(4 maps to 4 maps to 6),
(5 maps to 1 maps to 3),
(6 maps to 2 maps to 0),
(7 maps to 7 maps to 5).
As an example of the property we're looking for, the composition of the last element
(0,6)(2,4)(1,7)(3,5) with the 8-cycle (0,1,2,3,4,5,6,7) is the 8-cycle (0,7,2,5,4,3,6,1).
The generalization of this example is a "chandelier group".
We take a binary tree, with the bottom leaves representing integers 0 through N-1; with the top node representing the least significant bit (so that the left subtree represents even integers and the right subtree represents odd integers), and so on. The leaves are in the order [0,4,2,6,1,5,3,7] corresponding to reverse binary representation. Group operations are those movements of the tree such that there are an even number of transpositions at each of (3=log N) levels of the tree.
The best upper bound I know is about sqrt(N!).
Special kudos to first submitter of each successive improvement of the lower bound (starting the bidding at (2**N)/(2N)) or the upper bound (starting with any "substantial" decrease from (N!).)
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
09/06/2001 @ 8:30 AM EST
Solution:
10/01/2001 @ 10:00 AM EST
List Updated:
10/01/2001 @ 10:00 AM EST
People who answered correctly:
Vadim Alexandrov: upper bound (N/2)!2
Partial solutions have been received from:
Vladimir Sedach
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.