Skip to content →

Tag: mac

Seating the first few billion Knights

The odd Knight of the round table problem asks for a consistent placement of the n-th Knight in the row at an odd root of unity, compatible with the two different realizations of the algebraic closure of the field with two elements.

The first identifies the multiplicative group of its non-zero elements with the group of all odd complex roots of unity, under complex multiplication. The second uses Conway’s ‘simplicity rules’ in ONAG to define an addition and multiplication on the set of all ordinal numbers.

Here’s the seating arrangement for the first 15 knights. Conway proved that all finite ordinals smaller than $2^{2^i} $ form a subfield of $\overline{\mathbb{F}}_2 $. The first non-trivial one being $\{ 0,1,2,3 \} $ with smallest multiplicative generator $2 $, whence we place Knight 2 at $e^{2 i \pi/3} $ and as $2^2=3 $ we know where to place the third Knight.

The next subfield is made of the numbers $\{ 0,1,2,\ldots,13,14,15 \} $ and its non-zero numbers form a cyclic group of order 15. Hence we need to find the smallest generator of this group satisfying the additional property of being compatible with the earlier seating, that is, its fifth power must equal to 2. Checking the multiplication table reproduced here one verifies that the wanted generator is 4 and so we place Knight 4 at $e^{\frac{2 \pi i}{15}} $ and as all the ordinals smaller than 16 are powers of 4 this tells us where to place the Knights until we get to the 15th in the row.

In february we were able to seat the first few thousand Knights by showing by hand that 32 is the smallest ordinal such that its 15-th power is equal to 4 and using SAGE that 1051 is the smallest ordinal whose 257-th power equals 32. These calculations enabled us to seat the Knights until we get to the 65536-th in the row.

Today I managed to show that 1361923 is the smallest ordinal such that its 65537-th power equals 1051. You can verify this statement in SAGE using the method explained in the february post


sage: R.< x,y,z,t,u >=GF(2)[]

sage: S.< a,b,c,d,e > =
R.quotient((x^2+x+1,y^2+y+x,z^2+z+x*y,t^2+t+x*y*z,u^2+u+x*y*z*t))

sage: (c*e+b*e+a*b*c*d+b*c*d+a*b*d+a+1)^65537
c^2 + b*d + a + 1

(It takes a bit longer to check minimality of 1361923). That is, we have to seat Knight 1361923 at $e^{\frac{2 \pi i}{4294967295}} $ and because all the numbers smaller than 4294967296 are powers of 1361923 we have seating arrangements for the first 4294967295 Knights!

I did try the same method in february but ran into time- and memory-problems on my 2.4Ghz 2Gb MacBook. Today I upgraded from Sage 3.3 to Sage 4.6 and this version is a lot faster (using the 64-bit architecture) and also appears to be much better at memory-management. Thank you, Sage-community!

Wishing you all a lot of mathematical (and other) fun in the prime-number year 2011.

atb :: lieven.

One Comment

So, who did discover the Leech lattice?

For the better part of the 30ties, Ernst Witt (1) did hang out with the rest of the ‘Noetherknaben’, the group of young mathematicians around Emmy Noether (3) in Gottingen.

In 1934 Witt became Helmut Hasse‘s assistent in Gottingen, where he qualified as a university lecturer in 1936. By 1938 he has made enough of a name for himself to be offered a lecturer position in Hamburg and soon became an associate professor, the down-graded position held by Emil Artin (2) until he was forced to emigrate in 1937.

A former fellow student of him in Gottingen, Erna Bannow (4), had gone earlier to Hamburg to work with Artin. She continued her studies with Witt and finished her Ph.D. in 1939. In 1940 Erna Bannow and Witt married.

So, life was smiling on Ernst Witt that sunday january 28th 1940, both professionally and personally. There was just one cloud on the horizon, and a rather menacing one. He was called up by the Wehrmacht and knew he had to enter service in february. For all he knew, he was spending the last week-end with his future wife… (later in february 1940, Blaschke helped him to defer his military service by one year).

Still, he desperately wanted to finish his paper before entering the army, so he spend most of that week-end going through the final version and submitted it on monday, as the published paper shows.

In the 70ties, Witt suddenly claimed he did discover the Leech lattice $ {\Lambda} $ that sunday. Last time we have seen that the only written evidence for Witt’s claim is one sentence in his 1941-paper Eine Identität zwischen Modulformen zweiten Grades. “Bei dem Versuch, eine Form aus einer solchen Klassen wirklich anzugeben, fand ich mehr als 10 verschiedene Klassen in $ {\Gamma_{24}} $.”

But then, why didn’t Witt include more details of this sensational lattice in his paper?

Ina Kersten recalls on page 328 of Witt’s collected papers : “In his colloquium talk “Gitter und Mathieu-Gruppen” in Hamburg on January 27, 1970, Witt said that in 1938, he had found nine lattices in $ {\Gamma_{24}} $ and that later on January 28, 1940, while studying the Steiner system $ {S(5,8,24)} $, he had found two additional lattices $ {M} $ and $ {\Lambda} $ in $ {\Gamma_{24}} $. He continued saying that he had then given up the tedious investigation of $ {\Gamma_{24}} $ because of the surprisingly low contribution

$ \displaystyle | Aut(\Lambda) |^{-1} < 10^{-18} $

to the Minkowski density and that he had consented himself with a short note on page 324 in his 1941 paper.”

In the last sentence he refers to the fact that the sum of the inverse orders of the automorphism groups of all even unimodular lattices of a given dimension is a fixed rational number, the Minkowski-Siegel mass constant. In dimension 24 this constant is

$ \displaystyle \sum_{L} \frac{1}{| Aut(L) |} = \frac {1027637932586061520960267}{129477933340026851560636148613120000000} \approx 7.937 \times 10^{-15} $

That is, Witt was disappointed by the low contribution of the Leech lattice to the total constant and concluded that there might be thousands of new even 24-dimensional unimodular lattices out there, and dropped the problem.

If true, the story gets even better : not only claims Witt to have found the lattices $ {A_1^{24}=M} $ and $ {\Lambda} $, but also enough information on the Leech lattice in order to compute the order of its automorphism group $ {Aut(\Lambda)} $, aka the Conway group $ {Co_0 = .0} $ the dotto-group!

Is this possible? Well fortunately, the difficulties one encounters when trying to compute the order of the automorphism group of the Leech lattice from scratch, is one of the better documented mathematical stories around.

The books From Error-Correcting Codes through Sphere Packings to Simple Groups by Thomas Thompson, Symmetry and the monster by Mark Ronan, and Finding moonshine by Marcus du Sautoy tell the story in minute detail.

It took John Conway 12 hours on a 1968 saturday in Cambridge to compute the order of the dotto group, using the knowledge of Leech and McKay on the properties of the Leech lattice and with considerable help offered by John Thompson via telephone.

But then, John Conway is one of the fastest mathematicians the world has known. The prologue of his book On numbers and games begins with : “Just over a quarter of a century ago, for seven consecutive days I sat down and typed from 8:30 am until midnight, with just an hour for lunch, and ever since have described this book as “having been written in a week”.”

Conway may have written a book in one week, Ernst Witt did complete his entire Ph.D. in just one week! In a letter of August 1933, his sister told her parents : “He did not have a thesis topic until July 1, and the thesis was to be submitted by July 7. He did not want to have a topic assigned to him, and when he finally had the idea, he started working day and night, and eventually managed to finish in time.”

So, if someone might have beaten John Conway in fast-computing the dottos order, it may very well have been Witt. Sadly enough, there is a lot of circumstantial evidence to make Witt’s claim highly unlikely.

For starters, psychology. Would you spend your last week-end together with your wife to be before going to war performing an horrendous calculation?

Secondly, mathematical breakthroughs often arise from newly found insight. At that time, Witt was also working on his paper on root lattices “Spiegelungsgrupen and Aufzähling halbeinfacher Liescher Ringe” which he eventually submitted in january 1941. Contained in that paper is what we know as Witt’s lemma which tells us that for any integral lattice the sublattice generated by vectors of norms 1 and 2 is a direct sum of root lattices.

This leads to the trick of trying to construct unimodular lattices by starting with a direct sum of root lattices and ‘adding glue’. Although this gluing-method was introduced by Kneser as late as 1967, Witt must have been aware of it as his 16-dimensional lattice $ {D_{16}^+} $ is constructed this way.

If Witt wanted to construct new 24-dimensional even unimodular lattices in 1940, it would be natural for him to start off with direct sums of root lattices and trying to add vectors to them until he got what he was after. Now, all of the Niemeier-lattices are constructed this way, except for the Leech lattice!

I’m far from an expert on the Niemeier lattices but I would say that Witt definitely knew of the existence of $ {D_{24}^+} $, $ {E_8^3} $ and $ {A_{24}^+} $ and that it is quite likely he also constructed $ {(D_{16}E_8)^+, (D_{12}^2)^+, (A_{12}^2)^+, (D_8^3)^+} $ and possibly $ {(A_{17}E_7)^+} $ and $ {(A_{15}D_9)^+} $. I’d rate it far more likely Witt constructed another two such lattices on sunday january 28th 1940, rather than discovering the Leech lattice.

Finally, wouldn’t it be natural for him to include a remark, in his 1941 paper on root lattices, that not every even unimodular lattices can be obtained from sums of root lattices by adding glue, the Leech lattice being the minimal counter-example?

If it is true he was playing around with the Steiner systems that sunday, it would still be a pretty good story he discovered the lattices $ {(A_2^{12})^+} $ and $ {(A_1^{24})^+} $, for this would mean he discovered the Golay codes in the process!

Which brings us to our next question : who discovered the Golay code?

4 Comments

Return to LaTeX

To most mathematicians, a good LaTeX-frontend (such as TeXShop for Mac-users) is the crucial tool to get the work done. We use it to draft ideas, write papers and courses, or even to take notes during lectures.

However, after six years of blogging, my own LaTeX-routine became rusty. I rarely open a new tex-document, and when I do, I’d rather copy-paste the long preamble from an old file than to start from scratch with a minimal list of packages and definitions needed for the job at hand. The few times I put a paper on the arXiv, the resulting text resembles a blog-post more than a mathematical paper, here’s an example.

As I desperately need to get some math-writing done, I need to pull myself away from the lure of an ever-open WordPress admin browser-screen and reacquaint myself with the far more efficient LaTeX-environment.

Perhaps even my blogging will benefit from the change. Whereas I used to keep on adding to most of my tex-files in order to keep them up-to-date, I rarely edit a blog-post after hitting the ’publish’ button. If I really want to turn some of my better posts into a book, I need them in a format suitable for neverending polishing, without annoying the many RSS-feed aggregators out there.

Who better than Terry Tao to teach me a more proficient way of blogging? A few days ago, Terry announced he will soon have his 5th (!!) book out, after three years of blogging…

How does he manage to do this? Well, as far as I know, Terry blogs in LaTeX and then uses a python-script called LaTeX2WP ’a program that converts a LaTeX file into something that is ready to be cut and pasted into WordPress. This way, you can write, and preview, your post in LaTeX, then run LaTeX2WP, and post into WordPress whatever comes out.’ More importantly, one retains a pure-tex-file of the post on which one can keep on editing to get it into a (book)-publishable form, eventually.

Nice, but one can do even better, as Eric from Curious Reasoning worked out. He suggests to install two useful python-packages : WordPressLib “with this library you can control remotely a WordPress installation. Use of library is very simple, you can write a small scripts or full applications that allows you to automate publishing of articles on your blog/site powered by WordPress” and plasTeX “plasTeX is a LaTeX document processing framework written entirely in Python. It currently comes bundled with an XHTML renderer (including multiple themes), as well as a way to simply dump the document to a generic form of XML”. Installation is easy : download and extract the files somewhere, go there and issue a **sudo python setup.py install** to add the packages to your python.

Finally, get Eric’s own wplatex package and install it as explained there. WpLaTeX has all the features of LaTeX2WP and much more : one can add titles, tags and categories automatically and publish the post from the command-line without ever having to enter the taboo WordPress-admin page! Here’s what I’ve written by now in TeXShop

I’ve added the screenshot and the script will know where to find it online for the blog-version as well as on my hard-disk for the tex-version. Very handy is the iftex … fi versus ifblog … fi alternative which allows you to add pure HTML to get the desired effect, when needed. Remains only to go into Terminal and issue the command

wplpost -x http://www.neverendingbooks.org/xmlrpc.php ReturnToLatex.tex

(if your blog is on WordPress.com it even suffices to give its name, rather than this work-around for stand-alone wordpress blogs). The script asks for my username and password and will convert the tex-file and post it automatic.

5 Comments