Category: Computers

I have to admit I am still not quite happy with my typical workflow when I write my posts. The web-based text editor of WordPress (as it exists on the ETH blogs, at least) is not very convenient (or efficient), but on the other hand writing HTML in emacs, as I would like to do, doesn’t work so well because it is does not seem possible to preview the inline LaTeX formulas from emacs.

So I’ve looked for alternatives. And I was surprised to see that on Linux, it is not so easy to find a solution. There are a number of blog editors, which would be more or less satisfactory (including, of course, an emacs package…), except that most seem to take the point of view that one should type a blog post entirely, then publish it, and then make only minor corrections (if any). But I usually try to save locally what I type after each line (almost), and I consider it important to be able to such local copies for backup and reference purpose.

After trying a few programs, the only one I found to work reasonably (and that I use now) is the fairly obscure QTM. The text editor is not the best in the world (it has a search feature, but no replace), but one can save the posts to text files (which contain some very easily understandable and removable metadata), and publish them separately later on. One fairly obvious feature of the editor (which is unaccountably missing from the WordPress editor) is the possibility to insert a link — for which the target has been previously selected in a web browser — by a simple command (CTRL+U), after highlighting the words that should refer to the link. (On WordPress, the highlighting has the effect or replacing the link address in the clipboard with the linking words; this is standard X11 behavior, of course, but here this turns out to be a drawback).

Of course, the program itself does not preview the LaTeX formulas, but this can be done decently enough by sending the post as draft to the ETH blog. A bit more annoying is the fact that I don’t see how to insert pictures in the WordPress account from QTM itself, and then refer to them directly from its editor. So sometimes I write posts without pictures and add them in from WordPress later.

There’s also an apparent bug where sometimes the publishing date sent to WordPress gets wrong, and I have to manually change that. I haven’t tried to investigate deeply if I can locate it and correct in the source code.

The rather bizarre sequence in the title is the ordering of the integers from 2 to 23 which is induced by the values of the Chebotarev invariant of the group A_n. In other words, if n comes before m in this list (for instance, n=20, m=9), it means that on average, you will need to pick fewer conjugacy classes in A_n at random to obtain a set that necessarily generates it, than you need to do for A_m.

This illustrates some non-obvious property of this invariant; for instance, it is easier to “fill up” A₂₁ than A₈, despite the fact that the first has more maximal subgroups (14 against 6) and many more conjugacy classes (408 against 14) — in fact, there’s probably some money to be made by setting up betting games based on this type of observations.

The actual values of the invariants are in fact fairly close (except for the degenerate cases 2 and 3), ranging from 4.01632 or so to 4.939. It is not at all clear (to me) what the limiting behavior will be as n grows; I had first a vague guess that the sequence of invariants would grow to infinity (maybe slowly), but the data is more consistant with a convergence (or an oscillating behavior), which is what D. Zywina suggested to me for the symmetric group — where the behavior is roughly similar but the ordering is different.

I have been able to do these computations thanks to having again access to Magma; and I once more can’t help expressing my admiration for the incredible work that this team has done. (Admiration and gratitude which also apply equally to the members of the other teams working on algebraic-computation packages such as GAP, Pari/GP and Sage, even though for this particular type of computations, Magma is currently far ahead).

In previous posts (such as this old one), I’ve mentioned a few computer programs that I use fairly frequently, but one particularly interesting one was missing: SAGE, which packages together many different scientific software and libraries with a convenient interface around the Python language. The reason was that SAGE may be quite a bit more difficult to install than, for instance, GAP or Pari/GP (which it actually includes). Or at least, it was for me: my current laptop is quite nice but also quite recent, and so is Fedora 9, which is my Linux distribution. Some SAGE binary packages exist for Fedora 8, but not for Fedora 9 at the moment, and unfortunately there is a subtle packaging issue of some kind with some cryptographic routines that prevent the Fedora 8 package from working. So the current solution is to download and compile SAGE from source. But here another problem arises: the Core 2 CPU is misdetected by one of the packages involved in today’s version of SAGE (the ATLAS linear algebra package, version 3.8.1), which sees it as some kind of freaky Pentium III, and then takes forever to build.

As often where open source software is involved, the solution is not very far after a bit of search. In this case, the issue is known, as well as the workaround: commenting out two lines in one of the Atlas source files, and modifiying a third one. Once this is done, the rest of the build process worked perfectly. However, one must notice (or not forget), contrary to what I first did, that the build process of Atlas used by SAGE starts by installing and working from a pristine copy of the source code, contained in a compressed file, which will therefore erase the patched version of the delinquent code if one is not careful…

What must really be done is to create a new archive with the modified file. And in case anyone else has the same problem and finds this post, here is a copy of such an archive: it is the file $SAGE_DIR/spkg/standard/atlas-3.8.1.p3.spkg, valid for release 3.0.6 of SAGE (where $SAGE_DIR is the base directory where the SAGE files are found), and should be copied (with that name) in that location; this is a 2.8MB file.

(All this will soon be obsolete of course; within a month at most, the necessary patch will have found a permanent place on all the required software).

Now, this being done, I have started reading the documentation to actually use SAGE. Learning it is easier because of the concrete project of adapting the GAP script I have been using to compute Chebotarev invariants (at least, I find this type of manageable project is a good way to adapt to a new programming environment).

For illustration, here is the resulting SAGE program:

def chebotarev(G):
    G1=gap(G)
    g=G1.Order()._sage_()
    M=G1.ConjugacyClassesMaximalSubgroups()
    M1=[i.Representative() for i in M] # Python list
    nbM=len(M1)
    C=G1.ConjugacyClasses() # Gap list
    O=[c.Size()._sage_() for c in C] # Python list
    print O
    print "Done precomputing"

    cheb=0.0
    scheb=0.0
    ar=matrix(len(C),len(M1))
    # C is a GAP lists hence starts at 1.
    for i in range(1,len(C)+1):
        for j in range(0,len(M1)):
            #print i,j
            if C[i].Intersection(M1[j]) != gap([]):
                ar[i-1,j]=1

    for i in subsets(range(0,len(M1))):
        if len(i) != 0:
            density=0.0
            for j in range(1,len(C)+1):
                isin=True
                for x in i:
                    if ar[j-1,x]==0:
                         isin=False
                if isin==True:
                    density=density+O[j-1]
                    #if len(i)==1: print "---", i, C[j], density
            #if len(i)==1: print i, density
            cheb=cheb+(-1)^(len(i)+1)/(1-density/g)
            scheb=scheb+(-1)^(len(i))/(1-density/g)*(1-2/(1-density/g))
    return cheb, scheb

(Since this is actually Python code, remember that the indentation is significant if copying the script).

Compared with the earlier script, notice that while the “mathematical heart” of the computations are still done in GAP (the maximal subgroups and the conjugacy classes are computed in GAP from SAGE), the logic is written in the Python language. This has a number of advantages in this case: (1) it is easy to loop over all subsets of the maximal subgroups (GAP doesn’t have a command to get all subsets of a finite set; I had to implement it by interpreting subsets as bit patterns of integers, and the annoyance of this was compounded by the absence of a bitwise “and” operator in GAP…); (2) it is easy to get a real approximation instead of a rational number with enormous denominator (the Chebotarev invariants are rational numbers of this type as soon as the group is not ridiculously small); GAP doesn’t implement any floating point operations, and earlier I transferred the rationals to Pari/GP to get such real approximations… (Note that Magma does not have the two defects mentioned here, and as I said before, it is currently more efficient for some of these computations).

If you are a graduate student busy and worried writing a thesis, and in need of spiritual encouragement on this long and forking path, I’d like to suggest to tune to WBGO, the 24-hour, public, commercial-free, Jazz Radio Station from Newark, New Jersey. If Jazz is not the food of clear and insightful writing, I don’t know what is.

Until a few years ago, this valuable advice was only useful under rather stringent boundary conditions: roughly speaking, you had to be a student in the Newark or New Brunswick campuses of Rutgers University, or in Manhattan (probably; I didn’t have the opportunity to try from Columbia, for instance). However, nowadays you can access the radio stream any time on the internet, by following the link above. (The boundary condition were indeed rather strict; a minor heartbreak when moving for a postdoc to Princeton University was that, from there, barely twenty mile from New Brunswick, the radio signal did not reach my apartment or office…)

The efficiency of this musical infusion is proved not only by my own case (I was in Rutgers in 1995-98), but in a conclusive second proof by my student Florent Jouve in his acknowledgements for his recently completed thesis.

Note: if you end up following this advice, consider also contributing to the radio station, which relies on its listeners to stay on the air.

Note bis: if you use Linux, following the links to listen to WBGO may lead to difficulties with media plugins; however, the VLC program works (at least for me on a recent Fedora), with the command line

vlc http://wbgo.org/listennow/wbgo.asx &