Skip to content →

Tag: games

Archimedes’ stomachion

Published February 11, 2008 by lievenlb

The Archimedes codex is a good read, especially when you are (like me) a failed archeologist. The palimpsest (Greek for ‘scraped again’) is the worlds first Kyoto-approved ‘sustainable writing’. Isn’t it great to realize that one of the few surviving texts by Archimedes only made it because some monks recycled an old medieval parchment by scraping off most of the text, cutting the pages in half, rebinding them and writing a song-book on them…

The Archimedes-text is barely visible as vertical lines running through the song-lyrics. There is a great website telling the story in all its detail.

Contrary to what the books claims I don’t think we will have to rewrite maths history. Didn’t we already know that the Greek were able to compute areas and volumes by approximating them with polygons resp. polytopes? Of course one might view this as a precursor to integral calculus… And then the claim that Archimedes invented ordinal calculus. Sure the Greek knew that there were ‘as many’ even integers than integers… No, for me the major surprise was their theory about the genesis of mathematical notation.

The Greek were pure ASCII mathematicians : they wrote their proofs out in full text. Now, here’s an interesting theory how symbols got into maths… pure laziness of the medieval monks transcribing the old works! Copying a text was a dull undertaking so instead of repeating ‘has the same ratio as’ for the 1001th time, these monks introduced abbreviations like $\Sigma $ instead… and from then on things got slightly out of hand.

Another great chapter is on the stomachion, perhaps the oldest mathematical puzzle. Just a few pages made in into the palimpsest so we do not really know what (if anything) Archimedes had to say about it, but the conjecture is that he was after the number of different ways one could make a square with the following 14 pieces

People used computers to show that the total number is $17152=2^8 \times 67 $. The 2-power is hardly surprising in view of symmetries of the square (giving $8 $) and the fact that one can flip one of the two vertical or diagonal parts in the alternative description of the square

but I sure would like to know where the factor 67 is coming from… The MAA and UCSD have some good pages related to the stomachion puzzle. Finally, the book also views the problema bovinum as an authentic Archimedes, so maybe I should stick to my promise to blog about it, after all…

One Comment

thanks for linking

Published January 11, 2008 by lievenlb

I’ve re-installed the Google analytics plugin on december 22nd, so it is harvesting data for three weeks only. Still, it is an interesting tool to gain insight in the social networking aspect of math-blogging, something I’m still very bad at…

Below the list of all blogs referring at least 10 times over this last three weeks. In brackets are the number of referrals and included are the average time Avg. they spend on this site, as well as the bounce back rate BB. It gives me the opportunity to link back to some of their posts, as a small token of gratitude. I may repeat this in the future, so please keep on linking…

Not Even Wrong (69) : Avg (1.05 min) BB (52.94%)

The most recent post of Peter is an update on the plagiarism scandal on the arXiv.

The n-category cafe (63) : Avg (2.13 min) BB (50%)

The one series I followed at the cafe lately was the Geometric Representation Theory course run by John Baez and James Dolan. They provide downloadable movies as well as notes.

Richard Borcherd’s blog (47) : Avg (1.53 min) BB (53.19%)

It is great to see that Borcherds has taken up blogging again, with a post on the uselessness of set theory.

The Arcadian functor (32) : Avg (3.45 min) BB (34.38 %)

It is clear from the low bounce-back rate and the high average time spend on this site, that Kea’s readers and mine have common interests. Often I feel that Kea and I are talking about the same topics, but that our language is so different, that it is difficult for me to spot the precise connection. I definitely should start (for myself) a translation-project of her M-theory posts.

RupertGee’s iBlog (23) : Avg (6.48 min) BB (34.7 %)

Surprisingly, and contrasting to my previous rant iTouch-people (or at least those coming here from Rupert Gee’s blog) sure take time to read the posts and look for more.

Ars Mathematica (22) : Avg (0:01 min) BB (77,2 %)

Well, the average time and bounce back rate say it all : people coming here from Ars Mathematica are not interested in longer posts…

iTouch Fans Forum (14) : Avg (2:07 min) BB (42.86 %)

Again, better statistics than I would have expected.

Vivatsgasse 7 (13) : Avg (1:51 min) BB (38.46 %)

I hope these guys haven’t completely given up on blogging as it is one of my favourites.

Sixth form mathematics (12) : Avg (1:40 min) BB (25 %)

My few old posts on LaTeXrender still draw referrals…

Strategic Boards (12) : Avg (0:01 min) BB (91.67 %)

People in strategic board games are not really in my game-posts it seems…

The Everything Seminar (11) : Avg (2:04 min) BB (72.73 %)

Greg Muller has been posting a couple of nice posts on chord diagrams, starting here.

Noncommutative Geometry (11) : Avg (3:36 min) BB (27.27 %)

Well, we are interested in the same thing viewed from different angles, so good average times and a low bounce back rate. Maybe, I should make another attempt to have cross-interaction between the two blogs.

7 Comments

IF on iTouch

Published January 3, 2008 by lievenlb

Interactive Fiction (IF) describes software simulating environments in which players use text commands to control characters and influence the environment. Works in this form can be understood as literary narratives and as computer games. In common usage, the word refers to text adventures, a type of adventure game with text-based input and output. As the text-input is minimal (most commands have 1 letter abbreviations), text-games are ideal to be played on the iTouch.

Luckily, one of the most popular IF-interfaces, Frotz, is ported to the iPhone/iTouch as iPhoneFrotz. The easiest way to install is just to install the Frotz package using Installer.app. Just install the “Community Sources” package, which contains the installer repository (which hosts Frotz as well as other games and utilities), then look for Frotz under the Games section.

A collection of 3 Zork-derivatives (although not the original Infocom titles) is also available in the “Zork Z-Code” package.

There are hundreds of Z-Code games, and no one is likely to package your favorites for easy installation by Installer.app. But the games can be downloaded and copied to the phone without too much trouble.

Z-Code games are typically have filenames ending in .z3, .z4, .z5 or .z8 (depending on version), although game files from original Infocom media end in .dat. These should be copied to the phone’s Frotz/Games folder (under /var/root/Media).

Here is a link to the The IF archive and an archive of all Z-games. Another interesting site is the Inform 7-site

Inform is a design system for interactive fiction, a new medium for writers which began with adventure games in the late 1970s and is now used for everything from literary narrative fiction through to plotless conceptual art, and plenty more adventure games too. Since its introduction in 1993, Inform has become a standard tool.
Three years in the making, Inform 7 is a radical reinvention of the way interactive fiction is designed, guided both by contemporary work in semantics and by the practical experience of some of the world’s best-known writers of IF.

In place of traditional computer programming, the design is built by writing natural English-language sentences:
– Martha is a woman in the Vineyard.
– The cask is either customs sealed, liable to tax or stolen goods.
– The prevailing wind is a direction that varies.
– The Old Ice House overlooks the Garden.
– A container is bursting if the total weight of things in it is greater than its breaking strain.
Inform’s power lie in its ability to describe: to lay down general rules about “closed doors”, or “bursting containers”, or “unmarried men liked by Martha”. At its best, expressing IF in natural language results in source text which is not only quick to write, but very often works first time, and is exceptionally readable.

Inform 7 is available for most platforms and can be downloaded here.

Leave a Comment

daddy wasn’t impressed

Published December 19, 2007 by lievenlb

A first year-first semester course on group theory has its hilarious moments. Whereas they can relate the two other pure math courses (linear algebra and analysis) _somewhat_ to what they’ve learned before, with group theory they appear to enter an entirely new and strange world. So, it is best to give them concrete examples : symmetry groups of regular polygons and Platonic solids, the symmetric group etc. One of the lesser traditional examples I like to give is Nim addition and its relation to combinatorial games.

For their first test they had (among other things) to find a winning move for the position below in the Lenstra’s turtle turning game. At each move a player must put one turtle on its back and may also turn over any single turtle to the left of it. This second turtle, unlike the first, may be turned either onto its feet or onto its back. The player wins who turns the last turtle upside-down.

So, all they needed to see was that one turtle on its feet at place n is equivalent to a Nim-heap of height n and use the fact that all elements have order two to show that any zero-move in the sum game can indeed be played by using the second-turtle alternative. (( for the curious : the answer is turning both 9 and 4 on their back ))

A week later, one of the girls asked at the start of the lecture :

Are there real-life applications of group-theory? I mean, my father asked me what I was learning at school and I told him we were playing games turning turtles. I have to say that he was not impressed at all!.

She may have had an hidden agenda to slow me down because I spend an hour talking about a lot of things ranging from codes to cryptography and from representations to elementary particles…

For test three (on group-actions) I asked them to prove (among other things) Wilson’s theorem that is

$~(p-1)! \equiv -1~\text{mod}~p $

for any prime number $p $. The hint being : take the trivial action of $S_p $ on a one-element set and use the orbit theorem. (they know the number of elements in an $S_n $-conjugacy class)

Fingers crossed, hopefully daddy approved…

One Comment

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‘

Continue readingMathieu’s blackjack (2)
Leave a Comment

Conway’s puzzle M(13)

Published June 16, 2007 by lievenlb

Recently, I’ve been playing with the idea of writing a book for the general public. Its title is still unclear to me (though an idea might be “The disposable science”, better suggestions are of course wellcome) but I’ve fixed the subtitle as “Mathematics’ puzzling fall from grace”. The book’s concept is simple : I would consider the mathematical puzzles creating an hype over the last three centuries : the 14-15 puzzle for the 19th century, Rubik’s cube for the 20th century and, of course, Sudoku for the present century.

For each puzzle, I would describe its origin, the mathematics involved and how it can be used to solve the puzzle and, finally, what the differing quality of these puzzles tells us about mathematics’ changing standing in society over the period. Needless to say, the subtitle already gives away my point of view. The final part of the book would then be more optimistic. What kind of puzzles should we promote for mathematical thinking to have a fighting chance to survive in the near future?

Continue readingConway’s puzzle M(13)
Leave a Comment

THE rationality problem

Published April 27, 2007 by lievenlb

This morning, Esther Beneish
arxived the paper The center of the generic algebra of degree p that may contain the most
significant advance in my favourite problem for over 15 years! In it she
claims to prove that the center of the generic division algebra of
degree p is stably rational for all prime values p. Let me begin by
briefly explaining what the problem is all about. Consider one n by n
matrix A which is sufficiently general, then it will have all its
eigenvalues distinct, but then it is via the Jordan normal form theorem uniquely
determined upto conjugation (that is, base change) by its
characteristic polynomial. In
other words, the conjugacy class of a sufficiently general n by n matrix
depends freely on the coefficients of the characteristic polynomial
(which are the n elementary symmetric functions in the eigenvalues of
the matrix). Now what about couples of n by n matrices (A,B) under
simultaneous conjugation (that is all couples of the form $~(g A
g^{-1}, g B g^{-1}) $ for some invertible n by n matrix g) ??? So,
does there exist a sort of Jordan normal form for couples of n by n
matrices which are sufficiently general? That is, are there a set of
invariants for such couples which determine it is freely upto
simultaneous conjugation?

For couples of 2 by 2 matrices, Claudio Procesi rediscovered an old
result due to James Sylvester saying
that this is indeed the case and that the set of invariants consists of
the five invariants Tr(A),Tr(B),Det(A),Det(B) and Tr(AB). Now, Claudio
did a lot more in his paper. He showed that if you could prove this for
couples of matrices, you can also do it for triples, quadruples even any
k-tuples of n by n matrices under simultaneous conjugation. He also
related this problem to the center of the generic division algebra of
degree n (which was introduced earlier by Shimshon Amitsur in a rather
cryptic manner and for a while he simply refused to believe Claudio’s
description of this division algebra as the one generated by two
_generic_ n by n matrices, that is matrices filled with independent
variables). Claudio also gave the description of the center of this
algebra as a field of lattice-invariants (over the symmetric group S(n)
) which was crucial in subsequent investigations. If you are interested
in the history of this problem, its connections with Brauer group
problems and invariant theory and a short description of the tricks used
in proving the results I’ll mention below, you might have a look at the
talk Centers of Generic Division Algebras, the rationality problem 1965-1990
I gave in Chicago in 1990.

The case of couples of 3 by 3 matrices was finally
settled in 1979 by Ed Formanek and a
year later he was able to solve also the case of couples of 4 by 4
matrices in a fabulous paper. In it, he used solvability of S(4) in an
essential way thereby hinting at the possibility that the problem might
no longer have an affirmative answer for larger values of n. When I read
his 4×4 paper I believed that someone able to prove such a result must
have an awesome insight in the inner workings of matrices and decided to
dedicate myself to this problem the moment I would get a permanent
job… . But even then it is a reckless thing to do. Spending all of
your time to such a difficult problem can be frustrating as there is no
guarantee you’ll ever write a paper. Sure, you can find translations of
the problem and as all good problems it will have connections with other
subjects such as moduli spaces of vectorbundles and of quiver
representations, but to do the ‘next number’ is another matter.

Fortunately, early 1990, together with
Christine Bessenrodt we were
able to do the next two ‘prime cases’ : couples of 5 by 5 and couples of
7 by 7 matrices (Katsylo and Aidan Schofield had already proved that if
you could do it for couples of k by k and l by l matrices and if k and l
were coprime then you could also do it for couples of kl by kl matrices,
so the n=6 case was already done). Or did we? Well not quite, our
methods only allowed us to prove that the center is stably rational
that is, it becomes rational by freely adjoining extra variables. There
are examples known of stably rational fields which are NOT rational, but
I guess most experts believe that in the case of matrix-invariants
stable rationality will imply rationality. After this paper both
Christine and myself decided to do other things as we believed we had
reached the limits of what the lattice-method could do and we thought a
new idea was required to go further. If today’s paper by Esther turns
out to be correct, we were wrong. The next couple of days/weeks I’ll
have a go at her paper but as my lattice-tricks are pretty rusty this
may take longer than expected. Still, I see that in a couple of weeks
there will be a meeting in
Atlanta were Esther
and all experts in the field will be present (among them David Saltman
and Jean-Louis Colliot-Thelene) so we will know one way or the other
pretty soon. I sincerely hope Esther’s proof will stand the test as she
was the only one courageous enough to devote herself entirely to the
problem, regardless of slow progress.

Leave a Comment

devilish symmetries

Published April 2, 2007 by lievenlb

In another post we introduced
Minkowski’s question-mark function, aka the devil’s straircase
and related it to
Conways game of _contorted fractions_. Side remark : over at Good Math, Bad Math Mark Chu-Carroll is running
a mini-series on numbers&games, so far there is a post on surreal numbers,
surreal arithmetic and the connection with
games but
probably this series will go on for some time.

About a year ago I had
an email-exchange with Linas Vepstas because I was
intrigued by one of his online publications linking the fractal
symmetries of the devil’s staircase to the modular group. Unfortunately,
his paper contained some inaccuracies and I’m happy some of my comments
made it into his rewrite The Minkowski question mark, GL(2,Z) and the
modular group. Still, several
mistakes remain so read this paper only modulo his own caveat

XXXX This paper is unfinished. Although this version
corrects a number of serious errors in the previous drafts, it is still
misleading and confusing in many ways. The second half, in particular
must surely contain errors and mis-statements! Caveat emptor! XXXX

For example, on page 15 of the march 24-version he claims
that the third braid group $B_3 \simeq SL_2(\mathbb{Z}) $ which
would make life, mathematics and even physics a lot easier, but
unfortunately is not true. Recall that Artin’s defining relation for the
3-string braid group is $\sigma_1 \sigma_2 \sigma_1 = \sigma_2
\sigma_1 \sigma_2 $ as can be seen because the 3-strings below can
be transformed into each other
But from this
relation it follows that $c=(\sigma_1 \sigma_2 \sigma_1)^2 $ is
a central element in $B_3 $ and it is not difficult to verify
that indeed $B_3/ \langle c \rangle \simeq PSL_2(\mathbb{Z}) $
and $B_3/ \langle c^2 \rangle \simeq SL_2(\mathbb{Z}) $ An easy
way to see that the third braid group and the modular group are quite
different is to look at their one-dimensional representations. Any
group-map $B_3 \rightarrow \mathbb{C}^_ $ is determined by
non-zero complex numbers x and y satisfying $x^2y=y^2x $ so are
parametrized by the torus $\mathbb{C}^_ $ whereas there are only
6 one-dimensional representations of $PSL_2(\mathbb{Z}) = C_2 \ast
C_3 $ (and similarly, there are only 12 one-dimensional
$SL_2(\mathbb{Z}) $-representations). Btw. for those still
interested in noncommutative geometry : $(P)SL_2(\mathbb{Z}) $
are noncommutative manifolds whereas $B_3 $ is definitely
singular, if I ever get to the definitions of all of this… Still,
there is a gem contained in Linas’ paper and here’s my reading of it :
the fractal symmetries of the devil’s staircase form a generating
sub-semigroup $C_2 \ast \mathbb{N} $ of
$GL_2(\mathbb{Z}) $ . To begin, let us recall that the
question-mark function is defined in terms of continued fraction
expressions. So, what group of symmetries may be around the corner?
Well, if $a = \langle a_0;a_1,a_2,\ldots \rangle $ is the
continued fraction of a (see this
post for details) then if we
look at the n-th approximations $\frac{p_n}{q_n} $ (that is, the
rational numbers obtained after breaking off the continued fraction at
step n) it is failrly easy to show that $\begin{bmatrix} p_n &
p_{n-1} \\ q_n & q_{n-1} \end{bmatrix} \in GL_2(\mathbb{Z}) $ and
recall (again) that this group acts on
$\mathbb{P}^1_{\mathbb{C}} $ via Moebius transformations
$\begin{bmatrix} a & b \ c & d \end{bmatrix} $ via $z
\mapsto \frac{az+b}{cz+d} $ One of the symmetries is easy to spot
(reflexion along the 1/2-axis) That is, $?(x-1) = 1 – ?(x) $ Observe that the left-hand
side transformation is given by the Moebius transformation determined by
the matrix $r = \begin{bmatrix} -1 & 1 \\ 0 & 1 \end{bmatrix} \in
GL_2(\mathbb{Z}) $ Other symmetries are harder to see as they are
_fractal symmetries_, that is they are self-symmetries but at different
scales. For example, let us blow-up the ?-function at the interval
[1/3,1/2] and compare it with the function at the interval [1/2,1]
which has the same graph, while halving the function value. More
generally, substituting the ?-function definition using continued
fraction expressions one verifies that $?(\frac{x}{x+1}) =
\frac{1}{2} ?(x) $ and this time the left-hand transformation is
determined by the matrix $g = \begin{bmatrix} 1 & 0 \\ 1 & 1
\end{bmatrix} \in GL_2(\mathbb{Z}) $ We obtain a semi-group $S
= \langle r,g \rangle $ of fractal symmetries which are induced (the
right hand sides of the above expressions) via a 2-dimensional
representation of S $S \rightarrow GL_2(\mathbb{C})~\qquad r
\mapsto \begin{bmatrix} 1 & 0 \\ 1 & -1 \end{bmatrix}~\qquad g \mapsto
\begin{bmatrix} 1 & 0 \\ 0 & \frac{1}{2} \end{bmatrix} $ acting
via left-multiplication on the two-dimensional vectorspace
$\mathbb{C}1+\mathbb{C}x $. We claim that S is the free
semi-group $C_2 \ast \mathbb{N} $. Clearly, $r^2=1 $ and
g is of infinite order, but we have to show that no expression of the
form $rg^{i_1}rg^{i_2}r \ldots rg^{i_l}r $ can be the identity
in S. We will prove this by computing its action on the continued
fraction expression of $a = \langle 0;a_0,a_1,\ldots \rangle $.
It is a pleasant exercise to show that $g. \langle 0;a_1,a_2,\ldots
\rangle = \langle 0;a_1+1,a_2,\ldots \rangle $ whence by induction
$g^n. \langle 0;a_1,a_2,\ldots \rangle = \langle 0;a_1+n,a_2,\ldots
\rangle $ Moreover, the action on r is given by $r. \langle
0;a_1,a_2,\ldots \rangle = \langle 0;1,a_1-1,a_2,\ldots \rangle $ if
$a_1 \not= 1 $ whereas $r. \langle 0;1,a_2,a_3,\ldots
\rangle = \langle 0;a_2+1,a_3,\ldots \rangle $ But then, as a
consequence we have that $g^{n-1}rg . \langle 0;a_1,a_2,\ldots
\rangle = \langle 0;n,a_1,a_2,\ldots \rangle $ and iterating this
procedure gives us finally that an expression $g^{j-1} r g^k r g^l
r \ldots g^z r g = (g^{j-1} r g)(g^{k-1} r g)(g^{l-1} r g) \ldots
(g^{z-1} r g) $ acts on $a = \langle 0;a_1,a_2,\ldots
\rangle $ by sending it to $\langle
0;j,k,l,\ldots,z,a_1,a_2,\ldots \rangle $ whence such an expression
can never act as the identity element, proving that indeed $S \simeq
C_2 \ast \mathbb{N} $. As for the second claim, recall from this
post that
$GL_2(\mathbb{Z}) $ is generated by the matrices $U =
\begin{bmatrix} 0 & -1 \ 1 & 0 \end{bmatrix}~\quad V = \begin{bmatrix}
0 & 1 \ -1 & 1 \end{bmatrix}~\quad R = \begin{bmatrix} 0 & 1 \ 1 & 0
\end{bmatrix} $ and a straightforward verification shows that
$r = RV,~\quad g = VU $ and $R = g^{-1}rg,~\quad
V=g^{-1}rgr,\quad U=rg^{-1}rg^2 $ whence, indeed, the semi-group S
generates the whole of $GL_2(\mathbb{Z}) $!

Leave a Comment

the father of all beamer talks

Published March 2, 2007 by lievenlb

Who was the first mathematician to give a slide show talk? I don’t have the
definite answer to this question, but would like to offer a strong
candidate : Hermann Minkowski gave the talk “Zur Geometrie der Zahlen” (On the
geometry of numbers) before the third ICM in 1904 in Heidelberg and even
the title page of his paper in the proceedings indicates that he did
present his talk using slides (Mit Projektionsbildern auf einer
Doppeltafel)

Seven
of these eight slides would be hard to improve using LaTeX

What concerns
us today is the worst of all slides, the seventh, where Minkowski tries
to depict his famous questionmark function $?(x) $, sometimes also called
the _devil’s staircase_

The devil’s
staircase is a fractal curve and can be viewed as a mirror (taking a
point on the horizontal axis to the point on the vertical axis through
the function value) having magical simplifying properties : – it takes
rational numbers to _dyadic numbers_, that is those of the form
$n.2^{-m}$ with $n,m \in \mathbb{Z} $. – it takes quadratic
_irrational_ numbers to rational numbers. So, iterating this
mirror-procedure, the devil’s staircase is a device solving the main
problem of Greek Mathematics : which lengths can be constructed using
ruler and compass? These _constructible numbers_ are precisely those
real numbers which become after a finite number of devil-mirrors a
dyadic number. The proofs of these facts are not very difficult but
they involve a piece of long-forgotten mathematical technology :
_continued fractions_. By repeted approximations using the
floor-function (the largest natural number less than or equal to the real
number), every positive real number can be written as

$a = a_0 +
\frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\dots}}}} $

with all $a_i $ natural numbers. So, let us just denote from now on this
continued fraction of a by the expression

$a = \langle
a_0;a_1,a_2,a_3,\dots \rangle $

Clearly, a is a rational number if
(and also if but this requires a small argument using the Euclidian
algorithm) the above description has a tail of zeroes at the end and
(slightly more difficult) $a$ is a real quadratic irrational number
(that is, an element of a quadratic extension field
$\mathbb{Q}\sqrt{n} $) if and only if the continued fraction-expression
has a periodic tail. There is a lot more to say about
continued-fraction expressions and I’ll do that in another
‘virtual-course-post’ (those prepended with a (c): sign). For the
impatient let me just say that two real numbers will lie in the same
$GL_2(\mathbb{Z}) $-orbit (under the action via Moebius-transformations)
if and only if their continued fraction expressions have the same tails
eventually (which has applications in noncommutative geometry as in the
work of Manin and Marcolli but maybe I’ll come to this in the (c):
posts).

Right, now we can define the mysterious devil-stair function
$?(x) $. If a is in the real interval $[0,1] $ and if $a \in
\mathbb{Q} $ then $a = \langle 0;a_1,a_2,\dots,a_n,0,0,\dots
\rangle $ and we define $?(a) = 2 \sum_{k=1}^{n} (-1)^k
2^{-(a_1+a_2+\dots+a_k)} $ and if a is irrational with continued
fraction expression $a = \langle 0;a_1,a_2,a_3,\dots \rangle $, then

$?(a) = 2 \sum_{k=1}^{\infty} (-1)^{k+1} 2^{-(a_1+a_2+\dots+a_k)} $

A
perhaps easier description is that with the above continued-fraction
expression, the _binary_ expansion of $?(a) $ has the following form

$?(a) = 0,0 \dots 01 \dots 1 0 \dots 0 1 \dots 1 0 \dots 0 1 \dots
1 0 \dots $

where the first batch of zeroes after the comma has length
$a_1-1 $, the first batch of ones has length $a_2 $ the next batch of
zeroes length $a_3 $ and so on.

It is a pleasant exercise to verify that
this function does indeed have the properties we claimed before. A
recent incarnation of the question mark function is in Conway’s game of
_contorted fractions_. A typical position consists of a finite number of
boxed real numbers, for example the position might be

$\boxed{\pi} + \boxed{\sqrt{2}} + \boxed{1728} +
\boxed{-\frac{1}{3}} $

The Rules of the game are : (1) Both
players L and R take turns modifying just one of the numbers such that
the denominator becomes strictly smaller (irrational numbers are
supposed to have $\infty$ as their ‘denominator’). And if the boxed
number is already an integer, then its absolute value must decrease.
(2) Left must always _decrease_ the value of the boxed number, Right
must always increase it. (3) The first player unable to move looses
the game. To decide who wins a particular game, one needs to compute
the value of a position $\boxed{x} $ according to the rules of
combinatorial game theory (see for example the marvelous series of four
books Winning Ways for your Mathematical Plays. It turns out that this CG-value is no other than $?(x)$
… And, Conway has a much improved depiction of the devil-staircase in
his book On Numbers And Games

One Comment