Skip to content →

Tag: puzzle

vacation reading (2)

Vacation is always a good time to catch up on some reading. Besides, there’s very little else you can do at night in a ski-resort… This year, I’ve taken along The Archimedes Codex: Revealing The Secrets Of The World’s Greatest Palimpsest by Reviel Netz and William Noel telling the story of the Archimedes Palimpsest.

The most remarkable of the above works is The Method, of which the palimpsest contains the only known copy. In his other works, Archimedes often proves the equality of two areas or volumes with his method of double contradiction: assuming that the first is bigger than the second leads to a contradiction, as does the assumption that the first be smaller than the second; so the two must be equal. These proofs, still considered to be rigorous and correct, used what we might now consider secondary-school geometry with rare brilliance. Later writers often criticized Archimedes for not explaining how he arrived at his results in the first place. This explanation is contained in The Method.
Essentially, the method consists in dividing the two areas or volumes in infinitely many stripes of infinitesimal width, and “weighing” the stripes of the first figure against those of the second, evaluated in terms of a finite Egyptian fraction series. He considered this method as a useful heuristic but always made sure to prove the results found in this manner using the rigorous arithmetic methods mentioned above.
He was able to solve problems that would now be treated by integral calculus, which was formally invented in the 17th century by Isaac Newton and Gottfried Leibniz, working independently. Among those problems were that of calculating the center of gravity of a solid hemisphere, the center of gravity of a frustum of a circular paraboloid, and the area of a region bounded by a parabola and one of its secant lines. Contrary to exaggerations found in some 20th century calculus textbooks, he did not use anything like Riemann sums, either in the work embodied in this palimpsest or in any of his other works. (For explicit details of the method used, see Archimedes’ use of infinitesimals.)
A problem solved exclusively in the Method is the calculation of the volume of a cylindrical wedge, a result that reappears as theorem XVII (schema XIX) of Kepler’s Stereometria.
Some pages of the Method remained unused by the author of the Palimpsest and thus they are still lost. Between them, an announced result concerned the volume of the intersection of two cylinders, a figure that Apostol and Mnatsakian have renamed n = 4 Archimedean globe (and the half of it, n = 4 Archimedean dome), whose volume relates to the n-polygonal pyramid.
In Heiberg’s time, much attention was paid to Archimedes’ brilliant use of infinitesimals to solve problems about areas, volumes, and centers of gravity. Less attention was given to the Stomachion, a problem treated in the Palimpsest that appears to deal with a children’s puzzle. Reviel Netz of Stanford University has argued that Archimedes discussed the number of ways to solve the puzzle. Modern combinatorics leads to the result that this number is 17,152. Due to the fragmentary state of the palimpsest it is unknown whether or not Archimedes came to the same result. This may have been the most sophisticated work in the field of combinatorics in Greek antiquity.

Also I hope to finish the novel Interred with their bones by Jennifer Lee Carrell (though I prefer the Dutch title, “Het Shakespeare Geheim” that is, “The Shakespeare Secret”) on a lost play by Shakespeare, and have a re-read of The music of the primes as I’ll use this book for my course starting next week.

2 Comments

quotes of the day

Some people are in urgent need of a vacation, myself included…

From the paper Transseries for beginners by G.A. Edgar, arXived today :

Well, brothers and sisters, I am here today to tell you: If you love these formulas,
you need no longer hide in the shadows! The answer to all of these woes is here.
Transseries.

In a comment over at The Everthing Seminar

Shouldn’t dwarfs on the shoulders on giants be a little less arrogant?

by Micromegas.
Well, I’d rather enter a flame war than report about it. But, for some reason I cannot comment at the EverythingSeminar, nor at the SecretBloggingSeminar. Is this my problem or something to do with wordpress.com blogs? If you encountered a similar problem and managed to solve it, please let me know.

UPDATE (febr. 2) : my comment did surface after 5 days. Greg fished it out of their spam-filter. Thanks! I’ll try to comment at wordpress.com blogs from now on by NOT linking to neverendingbooks. I hope this will satisfy their spam-filter…

11 Comments

Chinese remainders and adele classes

Oystein Ore mentions the following puzzle from Brahma-Sphuta-Siddhanta (Brahma’s Correct System) by Brahmagupta :

An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

Here’s a similar problem from “Advanced Number Theory” by Harvey Cohn (( always, i wonder how one might ‘discreetly request’ these remainders… )) :

Exercise 5 : In a game for guessing a person’s age x, one discreetly requests three remainders : r1 when x is divided by 3, r2 when x is divided by 4, and r3 when x is divided by 5. Then x=40 r1 + 45 r2 + 36 r3 modulo 60.

Clearly, these problems are all examples of the Chinese Remainder Theorem.

Chinese because one of the first such problems was posed by Sunzi [Sun Tsu] (4th century AD)
in the book Sunzi Suanjing. (( according to ChinaPage the answer is contained in the song on the left hand side. ))

There are certain things whose number is unknown.
Repeatedly divided by 3, the remainder is 2;
by 5 the remainder is 3;
and by 7 the remainder is 2.
What will be the number?

The Chinese Remainder Theorem asserts that when $N=n_1n_2 \ldots n_k $ with the $n_i $ pairwise coprime, then there is an isomorphism of abelian groups $\mathbb{Z}/N \mathbb{Z} \simeq \mathbb{Z}/n_1 \mathbb{Z} \times \mathbb{Z}/n_2 \mathbb{Z} \times \ldots \times \mathbb{Z}/n_k \mathbb{Z} $. Equivalently, given coprime numbers $n_i $ one cal always solve the system of congruence identities

$\begin{cases} x \equiv a_1~(\text{mod}~n_1) \\ x \equiv a_2~(\text{mod}~n_2) \\ \vdots \\ x \equiv a_k~(\text{mod}~n_k) \end{cases} $

and all integer solutions are congruent to each other modulo $N=n_1 n_2 \ldots n_k $.

We will need this classical result to prove that
$\mathbb{Q}/\mathbb{Z} \simeq \mathcal{A}/\mathcal{R} $
where (as last time) $\mathcal{A} $ is the additive group of all adeles and where $\mathcal{R} $ is the subgroup $\prod_p \mathbb{Z}_p $ (i’ll drop all ‘hats’ from now on, so the p-adic numbers are $\mathbb{Q}_p = \hat{\mathbb{Q}}_p $ and the p-adic integers are denoted $\mathbb{Z}_p = \hat{\mathbb{Z}}_p $).

As we will have to do calculations with p-adic numbers, it is best to have them in a canonical form using digits. A system of digits $\mathbf{D} $ of $\mathbb{Q}_p $ consists of zero and a system of representatives of units of $\mathbb{Z}_p^* $ modulo $p \mathbb{Z}_p $. The most obvious choice of digits is $\mathbf{D} = { 0,1,2,\ldots,p-1 } $ which we will use today. (( later we will use another system of digits, the Teichmuller digits using $p-1 $-th root of unities in $\mathbb{Q}_p $. )) Fixing a set of digits $\mathbf{D} $, any p-adic number $a_p \in \mathbb{Q}_p $ can be expressed uniquely in the form

$a_p = \sum_{n=deg(a_p)}^{\infty} a_p(n) p^n $ with all ‘coefficients’ $a_p(n) \in \mathbf{D} $ and $deg(a_p) $ being the lowest p-power occurring in the description of $a_p $.

Recall that an adele is an element $a = (a_2,a_3,a_5,\ldots ) \in \prod_p \mathbb{Q}_p $ such that for almost all prime numbers p $a_p \in \mathbb{Z}_p $ (that is $deg(a_p) \geq 0 $). Denote the finite set of primes p such that $deg(a_p) < 0 $ with $\mathbf{P} = { p_1,\ldots,p_k } $ and let $d_i = -deg(a_{p_i}) $. Then, with $N=p_1^{d_1}p_2^{d_2} \ldots p_k^{d_k} $ we have that $N a_{p_i} \in \mathbb{Z}_{p_i} $. Observe that for all other prime numbers $q \notin \mathbf{P} $ we have $~(N,q)=1 $ and therefore $N $ is invertible in $\mathbb{Z}_q $.

Also $N = p_i^{d_i} K_i $ with $K_i \in \mathbb{Z}_{p_i}^* $. With respect to the system of digits $\mathbf{D} = { 0,1,\ldots,p-1 } $ we have

$N a_{p_i} = \underbrace{K_i \sum_{j=0}^{d_i-1} a_{p_i}(-d_i+j) p_i^j}_{= \alpha_i} + K_i \sum_{j \geq d_i} a_{p_i}(-d_i+j)p_i^j \in \mathbb{Z}_{p_i} $

Note that $\alpha_i \in \mathbb{Z} $ and the Chinese Remainder Theorem asserts the existence of an integral solution $M \in \mathbb{Z} $ to the system of congruences

$\begin{cases} M \equiv \alpha_1~\text{modulo}~p_1^{d_1} \\
M \equiv \alpha_2~\text{modulo}~p_2^{d_2} \\
\vdots \\ M \equiv \alpha_k~\text{modulo}~p_k^{d_k} \end{cases} $

But then, for all $1 \leq i \leq k $ we have $N a_{p_i} – M = p_i^{d_i} \sum_{j=0}^{\infty} b_i(j) p^j $ (with the $b_i(j) \in \mathbf{D} $) and therefore

$a_{p_i} – \frac{M}{N} = \frac{1}{K_i} \sum_{j=0}^{\infty} b_i(j) p^j \in \mathbb{Z}_{p_i} $

But for all other primes $q \notin \mathbf{P} $ we have that $\alpha_q \in \mathbb{Z}_q $ and that $N \in \mathbb{Z}_q^* $ whence for those primes we also have that $\alpha_q – \frac{M}{N} \in \mathbb{Z}_q $.

Finally, observe that the diagonal embedding of $\mathbb{Q} $ in $\prod_p \mathbb{Q}_p $ lies entirely in the adele ring $\mathcal{A} $ as a rational number has only finitely many primes appearing in its denominator. Hence, identifying $\mathbb{Q} \subset \mathcal{A} $ via the diagonal embedding we can rephrase the above as

$a – \frac{M}{N} \in \mathcal{R} = \prod_p \mathbb{Z}_p $

That is, any adele class $\mathcal{A}/\mathcal{R} $ has as a representant a rational number. But then, $\mathcal{A}/\mathcal{R} \simeq \mathbb{Q}/\mathbb{Z} $ which will allow us to give an adelic version of the Bost-Connes algebra!

Btw. there were 301 eggs.

One Comment

sobering-up

Kea’s post reminded me to have a look at my search terms (the things people type into search engines to get redirected here). Quite a sobering experience…

Via Google Analytics I learn that 49,51% of traffic comes from Search Engines (compared to 26,17% from Referring Sites and 24,32% from direct hits) so I should take Search Terms more seriously! Above you can find the top-25.

On 1. there is neverendingbooks. Well, some people seem to remember the blog-name, but require google to remember the URL (neverendingbooks.org)…, okay, fair enough. But from then on… all search terms are iTouch related! The first ‘other’ term is puzzle m at 24. and believe me things do not improve afterwards. Here the only non-Touch related search terms in the top 100 :

  • neverendingbooks.org (40)
  • “puzzle m” (42)
  • moonshine mathematics (79)
  • necklace algebra (80)
  • “calabi-yau algebra (90)
  • “dessin d enfant” (91)
  • “lieven le bruyn” (95)
  • Mathieu group + M(13) (97)
  • 13 points 5 lines puzzle (98)
  • 15 itouch sliding puzzle (99)

the last one is really touching (sic). Is there anybody out there still interested in the mathematics, or should I turn this blog into a yaib (yet another iTouch blog) ???

4 Comments

tori & crypto : Diffie-Hellman or GCHQ?

Boris Kunyavskii arXived the paper Algebraic tori – thirty years after dedicated to the 80th anniversary of V. E. Voskresenskii. The goal is to give an overview of results of V. E. Voskresenskii on arithmetic and birational properties of algebraic tori which culminated in his monograph “Algebraic Tori” published in Russian 30 years ago. As Ive worked on this stuff a long time ago I glanced through the paper and it contains a nice summary of the work of V.E. Voskresenskii, and later of Jean-Louis Colliot-Thelene, Jean-Jacques Sansuc and David Saltman. To my surprise I also made a guest-appearance and even seem to have a conjecture (??!!). Fortunately the ‘conjecture’ turned out to be correct as was proved by Nicole Lemire and Martin Lorenz. But a much bigger surprise (at least to me) is contained in the final section of the paper where applications of (stable) rationality of certain tori are given to primality testing and public key cryptography!

In [GPS]
the authors propose to use a similar idea of compression for using tori
in an even more recent cryptographic protocol (so-called pairing-based
cryptography). It is interesting to note that the efficiency (compression factor) of the above mentioned cryptosystems heavily depends on
rationality of tori under consideration (more precisely, on an explicit
rational parameterization of the underlying variety). As the tori used
by Rubin and Silverberg are known to be stably rational, the seemingly abstract question on rationality of a given stably rational torus
is moving to the area of applied mathematics. The first challenging
problem here is to obtain an explicit rational parameterization of the
8-dimensional torus $T_{30} $ , deïfined over a finite field k and splitting over
its cyclic extension L of degree 30.

This is a particular case of a problem posed by Voskresenskii [Vo77,
Problem 5.12] 30 years ago. Let us hope that we will not have to wait
another 30 years for answering this question on a degree 30 extension.

That’s all it takes to get me seriously side-tracked… so the last couple of hours I’ve been reading up on this connection between tori and cryptography. I will spend a couple of posts on these beautiful results. The latest seems to be that, while rationality of $T_{30} $ is still unknown, one can use an explicit stable-rationality description of it to get a better bound than the XTR-system (the system corresponding to the torus $T_{6} $) which in turn is better than the LUC-system (corresponding to $T_2 $), which is turn is twice as efficient as the Diffie-Hellman key exchange system… So let us start gently with the latter one…

Whitfield Diffie (r.) and Martin Hellman (m.) published in 1976 their public key-exchange system. Take a large prime power $q=p^N $, make it public and consider the finite field $\mathbb{F}_q $ which is known to have a cyclic group of units $\mathbb{F}^*_q $ of order $q-1 $. Now, take $g $ to be an element in it of large order (preferable a generator but that isnt necessary) and also make this element public.

Now choose a random integer $a $ (your hidden secret) and compute the element $g^a \in \mathbb{F}_q $ and publicize this element. Suppose someone else published his/her element $g^b $ constructed from his/her secret integer $b $ then both you and this other person can compute from the published data and their secret numbers the element (the shared key)

$g^{ab}=(g^b)^a = (g^a)^b $

(because you know $a $ and the published $g^b $ and your correspondent knows $b $ and the published $g^a $) but nobody else can compute it from the public-available data only because discrete logarithms cannot be feasibly computed in the group $\mathbb{F}_q^* $. Hellman suggests to call this system the Diffie-Hellman-Merkl key-exchange (via this link)

The first researchers to discover and publish the concepts of PKC were Whitfield Diffie and Martin Hellman from Stanford University, and Ralph Merkle from the University of California at Berkeley. As so often happens in the scientific world, the two groups were working independently on the same problem — Diffie and Hellman on public key cryptography and Merkle on public key distribution — when they became aware of each other’s work and realized there was synergy in their approaches. In Hellman’s words: “We each had a key part of the puzzle and while it’s true one of us first said X, and another of us first said Y, and so on, it was the combination and the back and forth between us that allowed the discovery.”

And that was the full story until 1997. In December, 1997, it was revealed that researchers at the GCHQ organization did some work in the early 1970’s in the field of “non-secret encryption”. The people involved are James Ellis, Clifford Cocks and Malcolm Williamson (r.).

Here is a note by Ellis on his recollection of the history of ‘Non-secret encryption” :

Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work,
because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography
is realised by minimising the information available to potential adversaries. Thus professional cryptographers
normally work in closed communities to provide sufficient professional interaction to ensure quality while
maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests
of historical accuracy after it has been demonstrated clearly that no further benefit can be obtained from
continued secrecy.
In keeping with this tradition it is now appropriate to tell the story of the invention and development within
CESG of non-secret encryption (NSE) which was our original name for what is now called PKC. The task of writing
this paper has devolved on me because NSE was my idea and I can therefore describe these early developments from
personal experience. No techniques not already public knowledge, or specific applications of NSE will be mentioned…

The once secret notes of Williamson are also available. NON-SECRET ENCRYPTION USING A FINITE FIELD
by M J Williamson, 21 January 1974
and THOUGHTS ON CHEAPER NON-SECRET ENCRYPTION
M J Williamson, 10 August 1976
.

2 Comments

mini-sudokube

Via the Arcadian functor I learned of the existence of the Sudokube (picture on the left).

Sudokube is a variation on a Rubik’s Cube in which each face resembles one-ninth of a Sudoku grid: the numbers from one to nine. This makes solving the cube slightly more difficult than a conventional Rubik’s Cube because each number must be in the right place and the centre cubies must also be in the correct orientation.

A much more interesting Sudoku-variation of the cube was invented two weeks ago by one of my freshmen-grouptheory students and was dubbed the mini-sudokube by him. Here’s the story.

At the end of my grouptheory course I let the students write a paper to check whether they have research potential. This year the assignment was to read through the paper mini-sudokus and groups by Carlos Arcos, Gary Brookfield and Mike Krebs, and do something original with it.

Mini-Sudoku is the baby $2 \times 2 $ version of Sudoku. Below a trivial problem and its solution

Of course most of them took the safe road and explained in more detail a result of the paper. Two of them were more original. One used the mini-sudoku solutions to find solutions for 4×4 sudokus, but the most original contribution came from Ibrahim Belkadi who wanted to count all mini-sudokubes. A mini-sudokube is a cube with a mini-sudoku solution on all 6 of its sides BUT NUMBERS CARRY OVER CUBE-EDGES. That is, if we have as the mini-sudoku given by the central square below on the top-face of the cube, then on the 4 side-faces we have already one row filled in.

The problem then is to find out how many compatible solutions there are. It is pretty easy to see that top- and bottom-faces determine all squares of the cube, but clearly not all choices are permitted. For example, with the above top-face fixed there are exactly 4 solutions. Let ${ a,b } = { 1,4 } $ and ${ c,d } = { 2,3 } $ then these four solutions are given below

Putting one of these solutions (or any other) on a $4 \times 4 $-Rubik cube would make a more interesting puzzle, I think. I’ve excused Ibrahim from having to take examination on condition that he writes down what he can prove on his mini-sudokubes by that time. Looking forward to it!

One Comment

The M(13)-groupoid (2)

Conway’s puzzle M(13) involves the 13 points and 13 lines of $\mathbb{P}^2(\mathbb{F}_3) $. On all but one point numbered counters are placed holding the numbers 1,…,12 and a move involves interchanging one counter and the ‘hole’ (the unique point having no counter) and interchanging the counters on the two other points of the line determined by the first two points. In the picture on the left, the lines are respresented by dashes around the circle in between two counters and the points lying on this line are those that connect to the dash either via a direct line or directly via the circle. In the first part we saw that the group of all reachable positions in Conway’s M(13) puzzle having the hole at the top positions contains the sporadic simple Mathieu group $M_{12} $ as a subgroup. To see the reverse inclusion we have to recall the definition of the ternary Golay code named in honour of the Swiss engineer Marcel Golay who discovered in 1949 the binary Golay code that we will encounter _later on_.

The ternary Golay code $\mathcal{C}_{12} $ is a six-dimenional subspace in $\mathbb{F}_3^{\oplus 12} $ and is spanned by its codewords of weight six (the Hamming distance of $\mathcal{C}_{12} $ whence it is a two-error correcting code). There are $264 = 2 \times 132 $ weight six codewords and they can be obtained from the 132 hexads, we encountered before as the winning positions of Mathieu’s blackjack, by replacing the stars by signs + or – using the following rules. By a tet (from tetracodeword) we mean a 3×4 array having 4 +-signs indicating the row-positions of a tetracodeword. For example

$~\begin{array}{|c|ccc|} \hline & + & & \\ + & & + & \\ & & & + \\ \hline + & 0 & + & – \end{array} $ is the tet corresponding to the bottom-tetracodeword. $\begin{array}{|c|ccc|} \hline & + & & \\ & + & & \\ & + & & \\ \hline & & & \end{array} $ A col is an array having +-signs along one of the four columns. The signed hexads will now be the hexads that can be written as $\mathbb{F}_3 $ vectors as (depending on the column-distributions of the stars in the hexad indicated between brackets)

$col-col~(3^20^2)\qquad \pm(col+tet)~(31^3) \qquad tet-tet~(2^30) \qquad \pm(col+col-tet)~(2^21^2) $

For example, the hexad on the right has column-distribution $2^30 $ so its signed versions are of the form tet-tet. The two tetracodewords must have the same digit (-) at place four (so that they cancel and leave an empty column). It is then easy to determine these two tetracodewords giving the signed hexad (together with its negative, obtained by replacing the order of the two codewords)

$\begin{array}{|c|ccc|} \hline \ast & \ast & & \\ \ast & & \ast & \\ & \ast & \ast & \\ \hline – & + & 0 & – \end{array} $ signed as
$\begin{array}{|c|ccc|} \hline + & & & \\ & & & \\ & + & + & + \\ \hline 0 & – & – & – \end{array} – \begin{array}{|c|ccc|} \hline & + & & \\ + & & + & \\ & & & + \\ \hline + & 0 & + & – \end{array} = \begin{array}{|c|ccc|} \hline + & – & & \\ – & & – & \\ & + & + & \\ \hline – & + & 0 & – \end{array} $

and similarly for the other cases. As Conway&Sloane remark ‘This is one of many cases when the process is easier performed than described’.

We have an order two operation mapping a signed hexad to its negative and as these codewords span the Golay code, this determines an order two automorphism of $\mathcal{C}_{12} $. Further, forgetting about signs, we get the Steiner-system S(5,6,12) of hexads for which the automorphism group is $M_{12} $ hence the automorphism group op the ternary Golay code is $2.M_{12} $, the unique nonsplit central extension of $M_{12} $.

Right, but what is the connection between the Golay code and Conway’s M(13)-puzzle which is played with points and lines in the projective plane $\mathbb{P}^2(\mathbb{F}_3) $? There are 13 points $\mathcal{P} $ so let us consider a 13-dimensional vectorspace $X=\mathbb{F}_3^{\oplus 13} $ with basis $x_p~:~p \in \mathcal{P} $. That is a vector in X is of the form $\vec{v}=\sum_p v_px_p $ and consider the ‘usual’ scalar product $\vec{v}.\vec{w} = \sum_p v_pw_p $ on X. Next, we bring in the lines in $\mathbb{P}^2(\mathbb{F}_3) $.

For each of the 13 lines l consider the vector $\vec{l} = \sum_{p \in l} x_p $ with support the four points lying on l and let $\mathcal{C} $ be the subspace (code) of X spanned by the thirteen vectors $\vec{l} $. Vectors $\vec{c},\vec{d} \in \mathcal{C} $ satisfy the remarkable identity $\vec{c}.\vec{d} = (\sum_p c_p)(\sum_p d_p) $. Indeed, both sides are bilinear in $\vec{c},\vec{d} $ so it suffices to check teh identity for two line-vectors $\vec{l},\vec{m} $. The right hand side is then 4.4=16=1 mod 3 which equals the left hand side as two lines either intersect in one point or are equal (and hence have 4 points in common). The identity applied to $\vec{c}=\vec{d} $ gives us (note that the squares in $\mathbb{F}_3 $ are {0,1}) information about the weight (that is, the number of non-zero digits) of codewords in $\mathcal{C} $

$wt(\vec{c})~mod(3) = \sum_p c_p^2 = (\sum_p c_p)^2 \in \{ 0,1 \} $

Let $\mathcal{C}’ $ be the collection of $\vec{c} \in \mathcal{C} $ of weight zero (modulo 3) then one can verify that $\mathcal{C}’ $ is the orthogonal complement of $\mathcal{C} $ with respect to the scalar product and that the dimension of $\mathcal{C} $ is seven whereas that of $\mathcal{C}’ $ is six.
Now, let for a point p be $\mathcal{G}_p $ the restriction of

$\mathcal{C}_p = \{ c \in \mathcal{C}~|~c_p = – \sum_{q \in \mathcal{P}} c_q \} $

to the coordinates of $\mathcal{P} – \{ p \} $, then $\mathcal{G}_p $ is clearly a six dimensional code in a 12-dimensional space. A bit more work shows that $\mathcal{G}_p $ is a self-dual code with minimal weight greater or equal to six, whence it must be the ternary Golay code! Now we are nearly done. _Next time_ we will introduce a reversi-version of M(13) and use the above facts to deduce that the basic group of the Mathieu-groupoid indeed is the sporadic simple group $M_{12} $.

References

Robert L. Griess, “Twelve sporadic groups” chp. 7 ‘The ternary Golay code and $2.M_{12} $’

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

John H. Conway, Noam D. Elkies and Jeremy L. Martin, ‘The Mathieu group $M_{12} $ and its pseudogroup extension $M_{13} $’ arXiv:math.GR/0508630

Leave a Comment

Mathieu’s blackjack (1)

Mathieu’s blackjack is a two-person combinatorial game played with 12 cards of values 0,1,2,…,11. For example take from any deck the numbered cards together with the jack (value 11) and the queen (value 0) (btw. if you find this PI by all means replace the queen by a zero-valued king). Shuffle the cards and divide them into two piles of 6 cards (all of them face up on the table) : the main-pile and the other-pile. The rules of the game are

  • players alternate moves
  • a move consists of exchanging a card of the main-pile with a lower-valued card from the other-pile
  • the player whose move makes the sum of all cards in the main-pile under 21 looses the game

For example, the starting main-pile might consist of the six cards

This pile has total value 3+4+7+8+9+11=42. A move replaces one of these cards with a lowever vlued one not in the pile. So for example, replacing 8 with 5 or 1 or 2 or the queen are all valid moves. A winning move from this situation is for example replacing 8 by the queen (value 0) decreasing the value from 42 to 34

But there are otthers, such as replacing 11 by 5, 9 by 1 or 4 by 2. To win this game you need to know the secrets of the tetracode and the MINIMOG.

The tetracode is a one-error correcting code consisting of the following nine words of length four over $\mathbb{F}_3 = { 0,+,- } $

$~\begin{matrix} 0~0 0 0 & 0~+ + + & 0~- – – \\ +~0 + – & +~+ – 0 & +~- 0 + \\ -~0 – + & -~+ 0 – & -~- + 0 \end{matrix} $

The first element (which is slightly offset from the rest) is the slope s of the words, and the other three digits cyclically increase by s (in the field $\mathbb{F}_3 $). Because the Hamming-distance is 3 (the minimal number of different digits between two codewords), the tetracode can correct one error, meaning that if at most one of the four digits gets distorted by the channel one can detect and correct this. For example, if you would receive the word $+~++- $ (which is not a codeword) and if you would know that at most one digits went wrong, you can deduce that the word $+~0+- $ was sent. Thus, one can solve the 4-problem for the tetracode : correctt a tetracodeword given all 4 of its digits, one of which may be mistaken.

Another easy puzzle is the 2-problem for the tertracode : complete a tetracodeword from any 2 of its digits. For example, given the incomplete word $?~?0+ $ you can decide that the slope should be + and hence that the complete word must be $+~-0+ $.

We will use the MINIMOG here as a way to record the blackjack-position. It is a $4 \times 3 $ array where the 12 boxes correspond to the card-values by the following scheme

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

and given a blackjack-position we place a star in the corresponding box, so the above start-position (resp. after the first move) corresponds to

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

In the final row we have added elements of $\mathbb{F}_3 $ indicating wher ethe stars are placed in that column (if there is just one star, we write the row-number of the star (ordered 0,+,- from top to bottom), if there are two stars we record the row-number of the empty spot. If we would have three or no stars in a column we would record a wild-card character : ?

Observe that the final row of the start position is $-~00+ $ which is NOT a tetracodeword, whereas that of the winning position $-~0-+ $ IS a tetracodeword! This is the essence of the _Conway-Ryba winning strategy_ for Mathieu’s blackjack. There are precisely 132 winning positions forming the Steiner-system S(5,6,12). By an S(5,6,12) we mean a collection of 6-element subsets (our card-piles) from a 12-element set (the deck minus the king) having the amazing property that for EVERY 5-tuple from the 12-set there is a UNIQUE 6-element set containing this 5-tuple. Hence, there are exactly $\begin{pmatrix} 12 \\\ 5 \end{pmatrix}/6 = 132 $ elements in a Steiner S(5,6,12) system. The winning positions are exactly those MINOMOGs having 6 stars such that the final row is a tetracodeword (or can be extended to a tetracodeword replacing the wildcards ? by suitable digits) and such that the distribution of the stars over the columns is NOT (3,2,1,0) in any order.

Provided the given blackjack-position is not in this Steiner-system (and there is only a 1/7 chance that it is), the strategy is clear : remove one of the stars to get a 5-tuple and determine the unique 6-set of the Steiner-system containing this 5-tuple. If the required extra star corresponds to a value less than the removed star you have a legal and winning move (if not, repeat this for another star). Finding these winning positions means solving 2- and 4-problems for the tetracode. _Another time_ we will say more about this Steiner system and indicate the relation with the Mathieu group $M_{12} $.

References

J.H. Conway and N.J.A. Sloane, ‘The Golay codes and the Mathieu groups’, chp. 10 of “Sphere Packings, Lattices and Groups

David Joyner and Ann Casey-Luers, ‘Kittens, S(5,6,12) and Mathematical blackjack in SAGE

2 Comments

The Mathieu groupoid (1)

Conway’s puzzle M(13) is a variation on the 15-puzzle played with the 13 points in the projective plane $\mathbb{P}^2(\mathbb{F}_3) $. The desired position is given on the left where all the counters are placed at at the points having that label (the point corresponding to the hole in the drawing has label 0). A typical move consists in choosing a line in the plane going through the point where the hole is, choose one of the three remaining points on this line and interchange the counter on it for the hole while at the same time interchanging the counters on the other two points. In the drawing on the left, lines correspond to the little-strokes on the circle and edges describe which points lie on which lines. For example, if we want to move counter 5 to the hole we notice that both of them lie on the line represented by the stroke just to the right of the hole and this line contains also the two points with counters 1 and 11, so we have to replace these two counters too in making a move. Today we will describe the groupoid corresponding to this slide-puzzle so if you want to read on, it is best to play a bit with Sebastian Egner’s M(13) Java Applet to see the puzzle in action (and to use it to verify the claims made below). Clicking on a counter performs the move taking the counter to the hole.

2 Comments

The 15-puzzle groupoid (2)

In the 15-puzzle groupoid 1 we have seen that the legal positions of the classical 15-puzzle are the objects of a category in which every morphism is an isomorphism (a groupoid ). Today, we will show that there are exactly 10461394944000 objects (legal positions) in this groupoid. The crucial fact is that positions with the hole in a fixed place can be identified with the elements of the alternating group $A_{15} $, a fact first proved by William Edward Story in 1879 in a note published in the American Journal of Mathematics.

Recall from last time that the positions reachable from the initial position can be encoded as $\boxed{\tau} $ where $\tau $ is the permutation on 16 elements (the 15 numbered squares and 16 for the hole) such that $\tau(i) $ tells what number in the position lies on square $i $ of the initial position. The set of all reachable positions are the objects of our category. A morphism $\boxed{\tau} \rightarrow \boxed{\sigma} $ is a legal sequence of slide-moves starting from position $\boxed{\tau} $ and ending at position $\boxed{\sigma} $. That is,

$\boxed{\sigma} = (16,i_k)(16,i_{k-1}) \cdots (16,i_2)(16,i_1) \boxed{\tau} $

Leave a Comment