Modulo Errors

I’m back from the Fields Institute in Toronto, where I spoke at the above workshop, on my usual topic of cyclotomic and 4-cyclotomic matrices/graphs. During the talk I described my conjecture that a graph is maximal cyclotomic if-and-only if it’s 4-cyclotomic, and after an hour at the blackboards with James McKee I now have a potential approach for proving that. So although I don’t think my talk went especially well, it’s had the desired effect!

You can find my slides here, and an audio recording may become available in the future- the conference was held in Toronto and Vancouver via videoconference (which worked well) so hopefully all the talks will be archived online.

Update 24/x/09: Audio of all talks at Fields (hence, including mine) can now be found on their website.

Having hit a bit of a wall trying to prove that a maximal cyclotomic matrix necessarily squares to 4I, I’ve been exploring related questions instead. For instance, it only took a couple of tweaks to my code to search for matrices that square to 3I instead of 4I; there turn out to be only finitely many, which isn’t particularly interesting. However, one of them is an 8 vertex cube which I recognised as ‘half’ the maximal cyclotomic graph S₁₆.

This got me thinking about the properties of graphs obtained by stitching together two graphs, and lead to an interesting construction. If M squares to nI, then by taking a second copy of its graph, negating and joining each vertex in the original to the corresponding one in the copy, you get a new matrix which squares to (n+1)I.

By iterating this process, many of the maximal cyclotomic graphs can be recovered; and since there are infinite families of maximal cyclotomic graphs, I can demonstrate infinitely many non-trivial integer matrices with all eigenvales of absolute value sqrt(n) for any integer n≥5 too.

A particularly nice example is the family of signed n-hypercubes generated by running this procedure on the ‘1-cyclotomic’ graph consisting of just a line. The picture at the top of this post is of the 5th step, and I’ve put together an animation illustrating its construction:

No mathematical reason to stop at 5, it just gets harder and harder to draw these things!

I’ve often said that trying to explain your work to others is the best way to check you understand it, and whilst preparing for this week’s talk at Cambridge (which was apparently well received!) I started to have some doubts about an algorithm I’d been using. In the end I didn’t go into enough technical detail during the talk for the issue to come up, but those concerns nagged at me during the commutes and lunchbreaks: eventually, I confirmed that there’s quite a big flaw in my proof as it stands.

For cyclotomic matrices over the rational integers, it turns out that all maximal examples satisfy the equation M²=4I. However, this is a side effect of the classification, rather than an independent result which can be used to arrive at that classification. Which is a problem, as (despite attempts to guard against it) my approach implicity assumes this condition…

Thus what I currently have is a classification not necessarily of all the maximal cyclotomic graphs, but of all the graphs whose matrix representation squares to 4I; no less substantial a piece of work, but a less significant result.

It’s still my belief that this is the full classification, but to prove that, I’ll need to demonstrate the equivalence of these two conditions (the reverse direction I already have, but that’s no help); or at least the weaker result that any cyclotomic graph with a vertex of weighted degree less than four admits a cyclotomic supermatrix, which is the hidden assumption in my existing algorithm. Suggestions welcome!

This week I’ve been at the rather swish Alan Turing building in Manchester for the MAGIC Postgraduate Conference and LMS Northern Regional Meeting.

I spoke at the former, on the subject of Integer Matrices with Constrained Eigenvalues. Here are my slides: it’s a fairly breezy 15 minute overview of the problem (which integer symmetric matrices have all eigenvalues in [-2,2]?) and its solution, covering Mahler measure, cyclotomic matrices, interlacing, and charged signed graphs. For further reading, here is the paper by McKee and Smyth (my supervisor) with their proof of the presented classification; also by Smyth is a survey on Mahler Measure of 1-variable polynomials.

In my own work I’ve generalised the idea of cyclotomicity (all eigenvalues in [-2,2]) to Hermitian matrices with algebraic integer entries from imaginary quadratic extension fields. I think I have a complete classification of these, with an alternative proof of the above rational integer case as a subcase. The results at least will hoepfully appear here at some point, although for the proofs you’ll probably have to wait for my thesis.

So it’s been over two months since a post; more attentive readers will have noticed that there was one, but now there isn’t. I’ve moved away from thinking about cryptography to generalising some number/graph theoretic results of my supervisor, concerning matrices with constrained eigenvalues. However, this creates a problem: unless I ‘blog every up and down of the research process (which could be interesting, but would slow me down!) information on here becomes decreasingly accurate or relevant as I revise my thinking on the topic. Certainly it would be premature to present firm results at the moment.

But I can at least set the stage for more technically-minded readers (a friendlier explanation/illustration will hopefully follow once I truly understand all this!). Chris has characterised all symmetric integer matrices with the property that their eigenvalues are at most 2 in modulus; under a suitable transformation of their characteristic polynomials, these give cyclotomic polynomials and thus are referred to as cyclotomic matrices. Conveniently, any submatrix of a cyclotomic matrix is itself cyclotomic, so it suffices to find maximal examples. Although there are infinite families of these matrices, there are only a few ‘types’ possible.

These types are best understood by considering not the matrix, but an associated graph, where values in the matrix determine the weights on edges and nodes of the graph. This introduces a notion of equivalence, since many matrices will correspond to the same graph or certain well-defined variations on it. Further, we can adjoin nodes and edges to the corresponding graph to try and ‘grow’ towards maximal examples.

The motivation comes from finding polynomials of small Mahler measure- whilst a cyclotomic polynomial has measure 1, all others seem to be pushed away, with the smallest known value being 1.176… The question is how to generate small examples, and these matrices provide a way: by adjoining a single extra node to a maximal cyclotomic graph, a non-cyclotomic graph/matrix is obtained and thus a non-cyclotomic polynomial. The minimal graphs with this property (non-cyclotomic, but all subgraphs cyclotomic) often correspond to polynomials with some of the smallest known Mahler measures.

But some examples are not generated in this way, which is where I’ve stepped in. There is no reason to restrict attention to integer matrices, and I’ve established which imaginary quadratic extensions of the rationals give rise to rings of integers over which suitable matrices can be found. For a couple of fields, there are very few new (non rational-integer) cyclotomic matrices, and I have a complete description of them, but in others there are again infinite families as well as occasional examples that don’t generalise.

So I explore this behaviour by growing graphs/matrices, and try to spot patterns as they emerge from the fragments. I use the university’s parallel computing cluster Eddie for brute force work in SAGE, but such is the nature of the combinatorial explosion that even this doesn’t suffice without some mathematical insight along the way, as I try to refine my growing algorithms and capture equivalence as early as possible. I’m hopefully nearing the point where all examples fit into known families, at which point I’ll need to switch into serious mathematician mode and try and prove why this should be so. But for now I need to make sure that nothing unexpected tumbles out of each batch of calculations!

On a completely unrelated note, I’ve dragged modulo errors up to date with wordpress 2.5 and switched themes; please shout if you find I’ve broken something along the way.