On music, computing and math

20/04/2012

A Pygments lexer for GAP

In case you haven’t heard of one of the most awesome LaTeX packages ever, let me introduce to you: minted. It’s a package to create listings (code snippets, preferably with highlighting, line numbering etc.), but it goes much further than the more well-known package listings. A small example:

Its awesomeness comes at a cost though, it relies heavily on an external Python program called Pygments. This is a generic tool for highlighting, regardless of output format. It can produce TeX, HTML, images, …. And it comes equipped with a load of supported languages. And if you’ve read the title you might guess what this post is about: a language that wasn’t supported yet.

For a course in computational group theory I have to write a report about an implementation in GAP, and this is absolutely impossible without the best possible syntax highlighting, right? So I have entertained myself with implementing a GAP lexer. Its implementation is available at github.com/pbelmans/gap-pygments-lexer.

I have supplied an automatic installer, as the README suggests it boils down to

git clone git://github.com/pbelmans/gap-pygments-lexer.git or download and extract the archive GitHub automatically creates at the project’s Downloads page
cd gap-pygments-lexer
sudo python setup.py install

I would like to thank Wim Thys for providing me with the names of all the built-in classes and functions, using a bit of sed magic.

If you feel inspired, there are several other languages that need an implementation:

Maple
Magma (but they are be working on it themselves apparently)
PARI/GP (this one has the most intriguing syntax of all)

29/03/2012

How to write Čech cohomology groups in LaTeX

Just like writing direct and inverse limits in TeX, the way to write Čech cohomology groups in TeX is something that doesn’t come up easily in Google unless you know what to look for (basically a list of math mode accents, but I am not the only person obstinately searching with the wrong keywords, right?).

So in text mode you write \v{C}ech, and in case you wish to write down the $n$ -th Čech cohomology group $\check{\mathrm{H}}^n(X,\mathcal{F})$ of a topological space $X$ and the sheaf $\mathcal{F}$ you use \check{\mathrm{H}}^n(X,\mathcal{F}). Notice the use of \mathrm{H} for the actual (co)homology object, you could/should do this too!

Don’t shoot the nitpicky typesetting aficionado please. And consider using a macro like \newcommand\HH{\mathrm{H}} for easier typing. And of course \newcommand\cHH{\check{\mathrm{H}}}.

Let this fact be known too.

27/03/2012

Enumerating all matrices in Jordan normal form

Introduction

For a course in noncommutative geometry / representation theory we discussed two examples of classifying orbits of matrices, more specifically Examples 1.1 and 1.2 in Noncommutative Geometry and Cayley-smooth Orders. I won’t discuss the details of the mathematics behind them, the reference should suffice.

I was intrigued by the computational aspects of the problem (the computer scientist in me pops up from time to time), and I recently gained access to a small supercomputer with a Magma installation. Not knowing the complete classification, which is given in Section 2.8 of Noncommutative Geometry and Cayley-smooth Orders under the monicker of the Gerstenhaber-Hesselink theorem (I always read the Gerstenlink-Haber theorem for some reason), I have implemented a general algorithm capable of giving you the details for all matrix rings if you are patient enough.

There are three parts involved in the classification:

studying the structure of the variety of singularities
enumerating all representatives of orbits, which are determined by Jordan normal forms
determining the dimensions of the orbits

The first part is computationally absolutely horrendous, but that could be my fault. I will discuss it if I feel compelled, but at the moment I am not happy with it. Degrees two and three are worked out in detail in the book, degree four is reasonably fast in my implementation while degree five already takes almost an hour… The results are not that uninteresting, so maybe I’ll write about them, maybe not.

Jordan normal form enumeration

The second part is what this post is about. Recall that any (complex) matrix can be conjugated with an invertible matrix to a block diagonal matrix, whose blocks are matrices with a single eigenvalue of the original on the diagonal, ones on the superdiagonal and zeroes everywhere else. For details, check Wikipedia’s Jordan normal form/Complex matrices. When trying to reproduce the diagram of Example 1.2 containing the orbit dimensions we obviously need to enumerate all possible Jordan normal forms. This is actually quite easy:

consider all partitions of $n$ , where the numbers are given in decreasing order giving all possible configurations of the eigenvalues (these correspond to the columns in the diagram)
fill in all legal superdiagonals, only considering decreasing numbers of ones for eigenvalues with the same multiplicity

The eigenvalues of the representatives are taken to be unknowns in a function field, for maximal flexibility. So the following code

n := 5;
field := FunctionField(RationalField(), n);
variables := ["x", "y", "z", "u", "v", "w"];
AssignNames(~field, variables[1 .. n]);

for partition in Partitions(n) do
  representative := DiagonalFromPartition(field, partition);
  "Enumerating the orbits with representative", representative;
  for M in EnumerateSuperdiagonals(representative, partition) do
    M, " ";
  end for;
end for;

does some initialization and will print all representatives, ordered by the structure of the eigenvalues. The code for DiagonalFromPartition is

DiagonalFromPartition := function(ring, partition)
  M := Matrix(ring, Weight(partition), Weight(partition), []);

  i := 1; j := 1;
  for multiplicity in partition do
    for k in [1 .. multiplicity] do M[j, j] := ring.i; j := j + 1; end for;
    i := i + 1;
  end for;

  return M;
end function;

while EnumerateSuperDiagonals is

EnumerateSuperdiagonals := function(matrix, partition)
  matrices := {};

  configurations := CartesianProduct([[0 .. multiplicity - 1] : multiplicity in partition]);
  for configuration in configurations do
    if IsNondecreasing(partition, configuration) then
      matrices := matrices join {ConstructJordanNormalForm(matrix, partition, configuration)};
    end if;
  end for;

  return matrices;
end function;

The filter IsNondecreasing is implemented by

IsNondecreasing := function(partition, configuration)
  maximum := Infinity();
  length := partition[1];

  for i in [1 .. #partition] do
    if partition[i] lt length then
      maximum := Infinity();
      length := partition[i];
    elif configuration[i] gt maximum then
      return false;
    else
      maximum := configuration[i];
    end if;
  end for;

  return true; 
end function;

while the actual construction as implemented in ConstructJordanNormalForm is given by

ConstructJordanNormalForm := function(matrix, partition, configuration)
  position := 1;
  for i in [1 .. #configuration] do
    for j in [0 .. configuration[i] - 1] do
      matrix[position + j, position + j + 1] := 1;
    end for;
    position := position + (partition[i]);
  end for;

  return matrix;
end function;

The output for this code (where $n=5$ ) is given in this pastebin.

The calculation of the dimensions

The third part is a bit of (symbolic) linear algebra, where you have to determine the dimension of the orbit by calculating the dimension of the stabilizer group, which is a Zariski dense subset of the centralizer of a matrix, hence suffices for giving the correct dimension. Mathematical details can be found in the text, the actual implementation is given by

OrbitDimension := function(matrix)
  field := BaseRing(matrix);
  n := Rank(field);
  ring := PolynomialRing(field, n^2);

  unknowns := Matrix(ring, n, n, [Name(ring, i) : i in [1 .. n^2]]);
  
  system := Matrix(ring, n^2, n^2, []);
  for i in [1 .. n] do
    for j in [1 .. n] do
      for k in [1 .. n^2] do
        system[(i-1)*n + j, k] := Coefficient((matrix*unknowns)[i, j], k, 1) - Coefficient((unknowns*matrix)[i, j], k, 1);
      end for;
    end for;
  end for;
  
  return n^2 - Rank(Kernel(system));
end function;

The algorithm is nothing but initializing a big system of linear equations, expressing the commutator relation $AM=MA$ where $M$ is (not necessarily) a matrix in Jordan normal form and $A$ is a matrix where every element corresponds to an unknown. By equating $AM=MA$ positionwise and obtaining a linear system of $n^2$ equations over the function field where our eigenvalues live, we can compute the rank of the kernel, which describes the dimension of the centralizing matrices.

If we slightly change the iteration of the first code example, calling OrbitDimension for each matrix, the output will be as given in this pastebin in case of $n=5$ .

What I have done is not the most relevant contribution to the world of mathematics, but in case you ever feel the urge to enumerate Jordan normal forms, I hope this will help you.

09/02/2012

A beamer theme for the University of Ghent

I have created a beamer theme for the University of Ghent (as the title already suggests), inspired by the excellent beamer theme for the University of Antwerp created by Nico Schlömer. There is already an implementation, but it doesn’t meet the style guide and it is only available out-of-the-box for the Faculty of Engineering and Architecture.

So I have decided to implement a UGent beamer theme myself, adhering to the style guide and following the philosophy set out by Nico. The implementation is available at GitHub, by means of the ugent-beamer project. I have rewritten Nico’s documentation to match my personal view on the subject of beamer themes, the result is available as a separate download. In case you wish to use the theme and you’re not that git-savvy, you can download the archive at the Downloads page. It contains all the necessary files, including the documentation.

The first two slides from the example I have supplied are

An example slide from the UGent beamer theme

A second example slide from the UGent beamer theme

Installing beamer themes can be quite a hassle if you’re not acquainted with the inner workings of MiKTeX or TeX Live, but it should be thoroughly explained in the documentation. If anything is not clear or something is wrong, please let me know. As for now, there are still several things I would like to do with the theme in the future, they are listed at the Issues page.

09/01/2012

The flaw in all Western music is related to the Riemann zeta function

In this post I will talk about an analogue between the Riemann zeta function and the tuning system used in Western music. But whereas the thing they have in common provides the necessary ingredient for proving the analyticity of the Riemann zeta function it renders all attempts of finding a “perfect tuning” futile. Don’t you think it’s remarkable what one’s mind drifts off to when studying for a number theory exam? :)

A glance of number theory

Let’s start with the Riemann zeta function, which in its most familiar form looks like
$\displaystyle\sum_{n=1}^{+\infty}\frac{1}{n^s}$ .
Introduced in 1859 by Bernhard Riemann in his paper Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse, generalizing the work of Euler and Chebyshev who considered this series for positive integers and real values respectively, it is an omnipresent object in mathematics. It’s a powerful tool in proving many facts about prime numbers (most notably the prime number theorem), but it still defies the ultimate insight in its behaviour: the location of its non-trivial zeroes. Riemann’s hypothesis states that these all have real part equal to 1/2, which would have vast consequences in number theory but so far it is still unsolved.

What is easy to prove though is its analyticity. I will give a (partial) proof now, based on Serge Lang’s Algebraic Number Theory, so that we will be able to see where the connection with musical tunings comes from. You can skip to the italic text, marked as the important part, where the conclusions necessary for the analogue are given, but I didn’t want to give these without a little background and a sketch of the proof.

Theorem The Riemann zeta function is analytically everywhere, except for a simple pole at $s=1$ .
Proof: Using Theorem 2 on page 156 from Lang’s ANT we obtain analyticity in the half-plane $\mathrm{Re}\,s>1$ . By considering the inequalities
$\displaystyle\frac{1}{s-1}\leq\int_1^{+\infty}\frac{1}{x^s}\,\mathrm{d}s\leq\zeta(s)\leq 1+\frac{1}{s-1}$
we get $1\leq(s-1)\zeta(s)\leq s$ which gives us the unique simple pole after considering the following argument. Using the alternating Riemann zeta function, also known as Dirichlet eta function
$\displaystyle\eta(s)=\zeta_2(s)=\sum_{n=1}^{+\infty}\frac{(-1)^{n-1}}{n^s}$
and applying the aforementioned Theorem 2 we get analyticity in the half-plane $\mathrm{Re}\,s>0$ for this new function. But we can write
$\displaystyle\frac{2}{2^s}\zeta_2(s)+\zeta_2(s)=\zeta(s)\quad\Longleftrightarrow\quad\zeta_2(s)=\left( 1-\frac{1}{2^{s-1}} \right)\zeta(s)$
which gives a possible analytic continuation of the Riemann zeta function to a slightly bigger half-plane, but we might get new poles.

Now define
$\displaystyle\zeta_r(s)=\frac{1}{1^s}+\frac{1}{2^s}+\dotsc+\frac{1}{(r-1)^s}-\frac{r-1}{r^s}+\frac{1}{(r+1)^s}+\dotsc$
which is a generalization of the Dirichlet eta function or alternating Riemann zeta function from before. Again by invoking Theorem 2 from Lang’s ANT we get analyticity for $\mathrm{Re}\,s>0$ , hence again
$\displaystyle\zeta(s)=\frac{\zeta_r(s)}{1-\displaystyle\frac{1}{r^{s-1}}}$
a possible analytic continuation. The only poles for $r=2$ are located at $s=1$ and $2^{s-1}=1$ or $s=2\pi\mathrm{i}n/\log 2+1$ while for $r=3$ there are located at $s=2\pi\textrm{i}/\log 3+1$ .

The important part: The linear independence over the rationals of the logarithms says that these cannot be equal, so the only possible pole is located at $s=1$ . In layman terms: if there was another pole we would see $2^m=3^n$ but as the left-hand side is even and the right-hand side is odd this equality is impossible for integral exponents.

A dive into tuning theory

Let’s shift our attention to music. Jeff Buckley sings

Well I heard there was a secret chord
That David played, and it pleased the Lord
But you don’t really care for music, do ya?
Well it goes like this
The fourth, the fifth
The minor fall and the major lift

which might seem like nonsense gibberish about ordinal numbers, but he is actually singing about musical intervals (and he actually takes the melodic steps he sings!), of which the fifth is the most important one. Without it there would be no punk music, but its importance is all encompassing: from ABBA to Bach to ZZ Top.

If you take two free intonation instruments (which means you can play all frequencies in its range, not hampered by frets, holes or keys) like for instance a violin or a trombone and let one play a constant frequency while the other is slowly sliding upwards, some frequencies will match while others won’t. Pythagoras already did this experiment and based his Pythagorean tuning on the outcome: the most pleasant sounding frequencies, apart from the octave which is a doubling of the base frequency, is the fifth which is located at 1.5 times the base frequency. I’m no psycho-acoustician so I can’t give a reasonable explanation, but somehow the human ear likes superparticular numbers. This is also related to his philosophy about the universe and numbers, with planets corresponding to harmonies etc. But I’ll try to avoid the crack-pottery :).

Performing this experiment to its full extent, or doing some calculations, you’ll get the 12 notes which constitute our musical system, and in the naive way of doing this you’ll get more nice fractions, such as 4/3, 9/8, 16/9 or 81/64. The resulting tuning is called just intonation.

But if you were to go up 7 octaves (which is the entire piano keyboard) or 12 fifths, you expect to end up on the same note. But $2^7\neq(3/2)^{12}$ , or $128\neq 129.7463\ldots$ ! This discrepancy is the root of all evil: there is no perfect tuning system. One needs to get 7 octaves equal to 12 fifths so you have to compensate in between: a fifth must be a little bit lower than you would actually like it to be.

Our current tuning system, which is called equal temperament, avoids this problem by dividing the logarithm of 2 in 12 even parts, which approximates the natural ratios. You get an extremely versatile and uniform system, all musical keys are treated equal, but the downside is a loss of natural harmonies. It only sounds good because you’re used to it, but in reality it is horrendous. A fact only known to an incrowd of musicians and you.

Morale

Not the least mathematicians have drawn analogues between the Riemann zeta function and music, stating that

“The music of the primes is a chord.”

But what makes the analyticity work for the mathematical object makes the music that might come out of it inherently out of tune.

And there are more relations between the Riemann zeta function and musical tunings, as noticed by Gene Ward Smith, as in these mailing list posts: a first one and a second one. Maybe I will delve further into this subject, drawing the parallels with Diophantine approximation more explicitly.

18/12/2011

Alternating beams for semi-quavers in Lilypond

I’ve been playing around with Lilypond for a while now, but I never really dug deep. Now I am digging deep, trying to typeset an adaption in D major of Bach’s BWV 1006(a), also known as Partita IV for violin (or lute, depending on the presence of (a)).

When writing for guitar it’s important to distinguish whether the thumb or one of the other fingers of your right hand should be used to play a note. The basic idea will be to use two voices, adding inline multiple voices whenever your index, middle and ring finger play simultaneously. Maybe when I feel like (and have more experience) I will write a short guide to writing classical guitar music in Lilypond with all its odds and ends.

Today’s post is dedicated to something I’ve been struggling with for a while. A rhythm of semiquavers, alternating between your thumb and your index/middle finger. I.e., in measure 14 of the prelude I would like to write
Alternating semiquavers in Lilypond: example

This is accomplished by wrapping the notes in each voice following the first in square brackets. I can’t find any decent reference on this in the Lilypond manual, but you basically say “beam these notes together” this way. So the code necessary to produce the example is

\relative c''
<<
  \time 3/4
  \key d \major
  { s16 [ d s d s d s d s d s d ] } \\ { d16 [ s fis s e s fis s g s e s ] } >>

Basically I’ve used two inline voices on top of eachother, fully writing out the measure in semiquavers twice but alternating between the actual notes and silent notes.

14/12/2011

Changing `\href{}{}` to produce footnotes

While preparing a document with lots of links for both online and offline viewing, I wanted the offline (i.e. printable) version to contain fulltext hyperlinks in the footnote. So whenever LaTeX comes across a \href{http://example.org}{Example website} I want it converted to something like Example website\footnote{\url{http://example.org}}. Inspired by this answer to the related TeX.SX question I came up with

\makeatletter
\newcommand\href@footnote[2]{#2\footnote{\url{#1}}}
\DeclareRobustCommand{\href}{\hyper@normalise\href@footnote}
\makeatother

This code properly handles active characters in url’s. Which is exactly what I want :).

I’m not claiming any originality here, but you might find it useful.

On music, computing and math

A Pygments lexer for GAP

How to write Čech cohomology groups in LaTeX

Enumerating all matrices in Jordan normal form

Introduction

Jordan normal form enumeration

The calculation of the dimensions

A beamer theme for the University of Ghent

The flaw in all Western music is related to the Riemann zeta function

A glance of number theory

A dive into tuning theory

Morale

Alternating beams for semi-quavers in Lilypond

Changing `\href{}{}` to produce footnotes

Categories

Blogroll (LaTeX)

Blogroll (math)

Blogroll (people)

Links

Twitter

Archives

Follow “On music, computing and math”