Modulo Errors

Recently I’ve been looking for a better way to work with representations of graphs, as I’m faced with increasingly complicated examples of cyclotomic matrices. At the moment, I have python code that reads in lists of matrices and returns the graphviz code for their representation. This is a good way to get a quick visual insight into what’s going on, except the rendering isn’t always consistent.

For instance, working with maximal 8-vertex graphs with 4 charges in Q(√-3) there are two known forms:

But when I generate an image of all such graphs generated during the growing procedure, I also find a couple of anomalies:

Obviously, I need to know whether these are genuinely new forms (and thus new results!) or just a strange representation of the known graphs. If your abstract spatial manipulation skills are good, you might be able to rearrange them in your head; the first, for instance, is pretty easy to recognise as being of the known cubic forms. The second looks temptingly similar to the chain, but in fact is also a cube, which took me quite a bit of drawing on the board to deduce!

The problem is that although graphviz allows several plotting options - all points on a circle, energy minimised etc. - once plotted, the graphs cannot be manipulated. So I wanted to create an interactive tool that would let me move points around until I either recognised the graph in question or was reasonably certain it was something new. This would also allow me to find more aesthetically pleasing representations of known forms; graphviz circular layouts tend to obscure symmetry, for instance.

Fortunately, this provided just the motivation to look into a language I’ve been interested in for some time- Processing. This is a stripped-down interface to java emphasing graphics, and has found application in both data visualisation and mathematical art. As luck would have it, artist, author and processing expert Ira Greenberg was in Edinburgh to give a workshop on its use, so I attended that to pick up the basics: in little over an hour we had simple physics simulations going, so it really is a friendly language!

Here then is a proof-of-concept graph manipulator. At the moment the graph itself is hard-coded; it’s an unusual 8-vertex non-maximal example that occurs only in the Q(√-3) case and ultimately leads to a unique 10-vertex maximal form. I knew it was something new, but found the graphviz representations unhelpful, so wanted to see if I could obtain a better one. After playing for a bit I managed to demonstrate a vertical axis of symmetry, as follows:

But perhaps you can do better? Left click on a vertex to have it follow the mouse; set it down again with a second left click.

As a companion to my previous post, here’s the list of valid forms of a connected maximal cyclotomic graph with an entry from the ring of integers of Q(√ -7):

Uncharged Lines:

Uncharged Squares:

Uncharged Hexagons:

Uncharged Cubes:

T_2k Variants (Infinite Family):

A chain of the form

for any integer k.

Charged Triangles:

Charged Squares:

or

C_2k Variants (Infinite Family):

A chain of the form

for any integer k.

To recap: I’ve been trying to completely classify the possible matrices/graphs subject to a constraint on their eigenvalues we’re describing as cyclotomicity. This is a problem that can be posed in the ring of integers of any imaginary quadratic extension field, but for all but finitely many of them reduces to the problem in the rational-integer case which has been solved in a paper by my supervisor.

For a couple of the remaining fields, the problem is easy: there’s only a finite supply of graphs featuring a non-rational integer label, which can be found simply by running a growing process to termination. But once you move to fields with norm 2 integers, there’s enough freedom for things to get interesting: I’ve been working in the rings of integers of Q(√ -2) and Q(√ -7), where I can demonstrate an infinite family of such graphs and so the growing algorithm can never terminate. Nonetheless, in the simpler, ‘uncharged’ version of the problem, I have (proven) a complete classification in both of these fields. With a bit more work I’ve now settled the general case in Q(√ -2) and expect the logic of the argument (although not the precise results) to carry over to Q(√ -7).

That argument is essentially a lengthy case analysis; rather than get into the details I thought I’d just present the ‘zoo’ of possible graphs. The forms presented are necessary conditions (any cyclotomic graph will take one of these forms) but not sufficient (there may be non-cyclotomic graphs satisfying the form). However, no form contains no cyclotomic graphs - for a given form, including any instance of the infinite ones, I can exhibit at least one class of cyclotomic graphs.

After applying a numbering, the visual styling of an edge between two nodes i<j indicates the norm of the edge label (entry [i,j] of the matrix; take the conjugate for entry [j,i]); uncharged nodes are indicated by a point whilst [C] denotes a charged node (value of ±1 for entry [i.i] if node i is charged, otherwise zero). The precise choice of labels and charges requires some care over signs to ensure that the matrix has minimal polynomial x²-4; working with forms saves tracking such details, choosing equivalence class representatives, etc.

Then for the ring of integers of Q(√ -2) any connected maximal cyclotomic graph with a non-rational integer label must take one of the following forms:

Uncharged Squares:

Uncharged Cubes:

T_2k Variants (Infinite Family):

A chain of the form

for any integer k.

Charged Triangles:

Charged Squares:

or

C_2k Variants (Infinite Family):

A chain of the form

for any integer k.

As I said, I expect this to easily generalise to Q(√-7); the remaining fields Q(√-1) and Q(√-3) present more of a computational challenge, but meeting that challenge will hopefully be rewarded with more interesting behaviour!

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.