neverendingbooks – Page 158

Shameless Self-Promotion

Published July 18, 2007 by lievenlb

It looks like I’m off the hook and can relax (after a few months of rewriting/correcting/learning LaTeX-quirks). To all of you NeverEndingBooks readers : the bookproject has ended and will appear sometime this fall. It will be around 600 pages thick and cost just under 100$. This is about 4 times the amount NeverEndingBook-ers paid over at Lulu.com. To all (?!) those who did : treasure the two volumes, they will become (extremely rare) collectors’ items, one fine day. Here is the final cover-design :

Compare it to the covers produced two years ago by the NeverEndingBooks-design department (thanks again Jan and the rest of the crew).

The final fight was over the promotional material. The copywriters did include the captivating sentence “A Novel Approach to Difficult Cases in Mathematics and Physics”… Here’s my reply

I realize Im a difficult (some say hopeless) case, but there is little point advertising this. Here a few alternatives that may require spicing-up

“A gentle introduction to one of mathematics’ (and even physics’) hottest topics”
“A novel approach to noncommutative geometry”
“Get rid of singularities by going noncommutative!”
“The first readable text on an over-hyped topic…”
etc. etc.

I can do better if I have to, so please tell me and I’ll open up a bottle of wine.
Whatever you do, please remove the difficult cases-sentence from all material.

atb+apologies :: lieven.

UPDATE (august 1st) : if you want to order the book for your university-library, have a look at the promo flyer. All my suggestions (apart from the last one) are included…

One final comment about all of this. The project started as a bookproject with the AMS in 1999 and was abandoned (for a variety of reasons, all of them only relevant to myself) sometime early 2002.

Here’s the one thing that will hurt for some time to come. I wanted to dedicate the book to “the women in my life : my mother, Ann, Gitte&Bente”. Unfortunately, my mother will never see the book. The current dedication is :

This book is dedicated to the women in my life
Simonne Stevens (1926-2004), Ann, Gitte&Bente

10 Comments

Mathieu’s blackjack (3)

Published July 17, 2007 by lievenlb

If you only tune in now, you might want to have a look at the definition of Mathieu’s blackjack and the first part of the proof of the Conway-Ryba winning strategy involving the Steiner system S(5,6,12) and the Mathieu sporadic group $M_{12} $.

We’re trying to disprove the existence of misfits, that is, of non-hexad positions having a total value of at least 21 such that every move to a hexad would increase the total value. So far, we succeeded in showing that such a misfit must have the patern

$\begin{array}{|c|ccc|} \hline 6 & III & \ast & 9 \\ 5 & II & 7 & . \\ IV & I & 8 & . \\ \hline & & & \end{array} $

That is, a misfit must contain the 0-card (queen) and cannot contain the 10 or 11(jack) and must contain 3 of the four Romans. Now we will see that a misfit also contains precisely one of {5,6} (and consequently also exactly one card from {7,8,9}). To start, it is clear that it cannot contain BOTH 5 and 6 (then its total value can be at most 20). So we have to disprove that a misfit can miss {5,6} entirely (and so the two remaining cards (apart from the zero and the three Romans) must all belong to {7,8,9}).

Lets assume the misfit misses 5 and 6 and does not contain 9. Then, it must contain 4 (otherwise, its column-distribution would be (0,3,3,0) and it would be a hexad). There are just three such positions possible

$\begin{array}{|c|ccc|} \hline . & \ast & \ast & . \\ . & \ast & \ast & . \\ \ast & . & \ast & . \\ \hline – & – & ? & ? \end{array} $ $\begin{array}{|c|ccc|} \hline . & \ast & \ast & . \\ . & . & \ast & . \\ \ast & \ast & \ast & . \\ \hline – & + & ? & ? \end{array} $ $\begin{array}{|c|ccc|} \hline . & . & \ast & . \\ . & \ast & \ast & . \\ \ast & \ast & \ast & . \\ \hline – & 0 & ? & ? \end{array} $

Neither of these can be misfits though. In the first one, there is an 8->5 move to a hexad of smaller total value (in the second a 7->5 move and in the third a 7->6 move). Right, so the 9 card must belong to a misfit. Assume it does not contain the 4-card, then part of the misfit looks like (with either a 7- or an 8-card added)

$\begin{array}{|c|ccc|} \hline . & \ast & \ast & \ast \\ . & \ast & ? & . \\ . & \ast & ? & . \\ \hline & & & \end{array} $ contained in the unique hexad $\begin{array}{|c|ccc|} \hline \ast & \ast & \ast & \ast \\ . & \ast & & . \\ . & \ast & & . \\ \hline & & & \end{array} $

Either way the moves 7->6 or 8->6 decrease the total value, so it cannot be a misfit. Therefore, a misfit must contain both the 4- and 9-card. So it is of the form on the left below

$\begin{array}{|c|ccc|} \hline . & ? & \ast & \ast \\ . & ? & ? & . \\ \ast & ? & ? & . \\ \hline & & & \end{array} $ $\begin{array}{|c|ccc|} \hline . & . & \ast & . \\ . & \ast & \ast & \ast \\ \ast & \ast & . & . \\ \hline – & 0 & – & + \end{array} $ $\begin{array}{|c|ccc|} \hline . & . & \ast & \ast \\ . & \ast & \ast & . \\ \ast & \ast & . & . \\ \hline & & & \end{array} $

If this is a genuine misfit only the move 9->10 to a hexad is possible (the move 9->11 is not possible as all BUT ONE of {0,1,2,3,4} is contained in the misfit). Now, the only hexad containing 0,4,10 and 2 from {1,2,3} is in the middle, giving us what the misfit must look like before the move, on the right. Finally, this cannot be a misfit as the move 7->5 decreases the total value.

That is, we have proved the claim that a misfit must contain one of {5,6} and one of {7,8,9}. Right, now we can deliver the elegant finishing line of the Kahane-Ryba proof. A misfit must contain 0 and three among {1,2,3,4} (let us call the missing card s), one of $5+\epsilon $ with $0 \leq \epsilon \leq 1 $ and one of $7+\delta $ with $0 \leq \delta \leq 2 $. Then, the total value of the misfit is

$~(0+1+2+3+4-s)+(5+\epsilon)+(7+\delta)=21+(1+\delta+\epsilon-s) $

So, if this value is strictly greater than 21 (and we will see in a moment is has to be if it is at least 21) then we deduce that $s < 1 + \delta + \epsilon \leq 4 $. Therefore $1+\delta+\epsilon $ belongs to the misfit. But then the move $1+\delta \epsilon \rightarrow s $ moves the misfit to a 6-tuple with total value 21 and hence (as we see in a moment) must be a hexad and hence this is a decreasing move! So, finally, there are no misfits!

Hence, from every non-hexad pile of total value at least 21 we have a legal move to a hexad. Because the other player cannot move from an hexad to another hexad we are done with our strategy provided we can show (a) that the total value of any hexad is at least 21 and (b) that ALL 6-piles of total value 21 are hexads. As there are only 132 hexads it is easy enough to have their sum-distribution. Here it is

That is, (a) is proved by inspection and we see that there are 11 hexads of sum 21 (the light hexads in Conway-speak) and there are only 11 ways to get 21 as a sum of 6 distinct numbers from {0,1,..,11} so (b) follows. Btw. the obvious symmetry of the sum-distribution is another consequence of the duality t->11-t discussed briefly at the end of part 2.

Clearly, I’d rather have conceptual proofs for all these facts and briefly tried my hand. Luckily I did spot the following phrase on page 326 of Conway-Sloane (discussing the above distribution) :

“It will not be easy to explain all the above observations. They are certainly connected with hyperbolic geometry and with the ‘hole’ structure of the Leech lattice.”

So, I’d better leave it at this…

References

Joseph Kahane and Alexander J. Ryba, “The hexad game“

John H. Conway and N. J.A. Sloane, “Sphere packings, Lattices and Groups” chp. 11 ‘The Golay codes and the Mathieu groups’

Mathieu’s blackjack (2)

Published July 17, 2007 by lievenlb

(continued from part one). Take twelve cards and give them values 0,1,2,…,11 (for example, take the jack to have value 11 and the queen to have value 0). The hexads are 6-tuples of cards having the following properties. When we star their values by the scheme on the left below and write a 0 below a column if it has just one star at the first row or two stars on rows two and three (a + if the unique star is at the first row or two stars in the other columns, and a – if the unique star in on the second row or two stars in rows one and two) or a ? if the column has 3 or 0 stars, we get a tetracodeword where we are allowed to replace a ? by any digit. Moreover, we want that the stars are NOT distributed over the four columns such that all of the possible outcomes 0,1,2,3 appear once. For example, the card-pile { queen, 3, 4, 7, 9, jack } is an hexad as is indicated on the right below and has column-distributions (1,1,2,2).

$\begin{array}{|c|ccc|} \hline 6 & 3 & 0 & 9 \\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \\ \hline & & & \end{array} $ $\begin{array}{|c|ccc|} \hline & \ast & \ast & \ast \\ & & \ast & \\ \ast & & & \ast \\ \hline – & 0 & – & + \end{array} $

The hexads form a Steiner-system S(5,6,12), meaning that every 5-pile of cards is part of a unique hexad. The permutations on these twelve cards, having the property that they send every hexad to another hexad, form the sporadic simple group $M_{12} $, the _Mathieu group_ of order 95040. For now, we assume these facts and deduce from them the Conway-Ryba winning strategy for Mathieu’s blackjack : the hexads are exactly the winning positions and from a non-hexad pile of total value at least 21 there is always a legal (that is, total value decreasing) move to an hexad by replacing one card in the pile by a card from the complement.

It seems that the first proof of this strategy consisted in calculating the Grundy values of all 905 legal positions in Mathieu’s blackjack. Later Joseph Kahane and Alex Ryba gave a more conceptual proof, that we will try to understand.

Take a non-hexad 6-pile such that the total value of its cards is at least 21, then removing any one of the six cards gives a 5-pile and is by the Steiner-property contained in a unique hexad. Hence we get 6 different hexads replacing one card from the non-hexad pile by a card not contained in it. We claim that at least one of these operations is a legal move, meaning that the total value of the cards decreases. Let us call a counterexample a misfit and record some of its properties until we can prove its non-existence.

A misfit is a non-hexad with total value at least 21 such that all 6 hexads, obtained from it by replacing one card by a card from its complement, have greater total value

A misfit must contain the queen-card. If not, we could get an hexad replacing one misfit-card (value > 0) by the queen (value zero) so this would be a legal move. Further, the misfit cannot contain the jack-card for otherwise replacing it by a lower-valued card to obtain an hexad is a legal move.

A misfit contains at least three cards from {queen,1,2,3,4}. If not, three of these cards are the replacements of misfit-cards to get an hexad, but then at least one of the replaced cards has a greater value than the replacement, giving a legal move to an hexad.

A misfit contains more than three cards from {queen=0, 1,2,3,4}. Assume there are precisely three $\{ c_1,c_2,c_3 \} $ from this set, then the complement of the misfit in the hexad {queen,1,2,3,4,jack} consists of three elements $\{ d_1,d_2,d_3 \} $ (a misfit cannot contain the jack). The two leftmost columns of the value-scheme (left above) form the hexad {1,2,3,4,5,6} and because the Mathieu group acts 5-transitively there is an element of $M_{12} $ taking $\{ 0,1,2,3,4,11 \} \rightarrow \{ 1,2,3,4,5,6 \} $ and we may even assume that it takes $\{ c_1,c_2,c_3 \} \rightarrow \{ 4,5,6 \} $. But then, in the new value-scheme (determined by that $M_{12} $-element) the two leftmost columns of the misfit look like

$\begin{array}{|c|ccc|} \hline \ast & . & ? & ? \\ \ast & . & ? & ? \\ \ast & . & ? & ? \\ \hline ? & ? & & \end{array} $

and the column-distribution of the misfit must be either (3,0,2,1) or (3,0,1,2) (it cannot be (3,0,3,0) or (3,0,0,3) otherwise the (image of the) misfit would be an hexad). Let {i,j} be the two misfit-values in the 2-starred column. Replacing either of them to get an hexad must have the replacement lying in the second column (in order to get a valid column distribution (3,1,1,1)). Now, the second column consists of two small values (from {0,1,2,3,4}) and the large jack-value (11). So, at least one of {i,j} is replaced by a smaller valued card to get an hexad, which cannot happen by the misfit-property.

Now, if the misfit shares four cards with {queen,1,2,3,4} then it cannot contain the 10-card. Otherwise, the replacement to get an hexad of the 10-card must be the 11-card (by the misfit-property) but then there would be another hexads containing five cards from {queen,0,1,2,3,jack} which cannot happen by the Steiner-property. Right, let’s summarize what we know so far about our misfit. Its value-scheme looks like

$\begin{array}{|c|ccc|} \hline 6 & III & \ast & 9 \\ 5 & II & 7 & . \\ IV & I & 8 & . \\ \hline & & & \end{array} $ and it must contain three of the four Romans. At this point Kahane and Ryba claim that the two remaining cards (apart from the queen and the three romans) must be such that there is exactly one from {5,6} and exactly one from {7,8,9}. They argue this follows from duality where the dual pile of a card-pile $\{ x_1,x_2,\ldots,x_6 \} $ is the pile $\{ 11-x_1,11-x_2,\ldots,11-x_6 \} $. This duality acts on the hexads as the permutation $~(0,11)(1,10)(2,9)(3,8)(4,7)(5,6) \in M_{12} $. Still, it is unclear to me how they deduce from it the above claim (lines 13-15 of page 4 of their paper). I’d better have some coffee and work around this (to be continued…)

If you want to play around a bit with hexads and the blackjack game, you’d better first download SAGE (if you haven’t done so already) and then get David Joyner’s hexad.sage file and put it in a folder under your sage installation (David suggests ‘spam’ himself…). You can load the routines into sage by typing from the sage-prompt attach ‘spam/hexad.sage’. Now, you can find the hexad from a 5-pile via the command find_hexad([a1,a2,a3,a4,a5],minimog_shuffle) and you can get the winning move for a blackjack-position via blackjack_move([a1,a2,a3,a4,a5,a6],minimog_shuffle). More details are in the Joyner-Casey(Luers) paper referenced last time.

Reference

Joseph Kahane and Alexander J. Ryba, ‘The hexad game‘

neverendingbooks Posts

Shameless Self-Promotion

Mathieu’s blackjack (3)

Mathieu’s blackjack (2)