Modulo Errors

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.

Despite my usual resistance to applied maths, yesterday’s BICS seminar sounded worthwhile, and turned out to be very good- Keith Briggs of BT gave a talk entitled Some practical experiences of hard graph problems. Graph Theory isn’t part of our syllabus, which seems a shame, as the concepts are simple- colouring, cliques etc. - but the questions difficult.

Much of the talk discussed the validity of results on infinite graphs when applied to smaller (and hence computationally feasible) ones: in particular, obtaining good bounds on clique and chromatic numbers. Towards the end, the reduction of graph problems to the satisfiability problem in propositional logic was mentioned. Obviously, the possibility of such reductions is a defining characteristic of NP-hard problems (and one I’ve recently been studying), but it’s good to see that this is of practical merit rather than simply theoretical interest.

So, I attended my first mathematics conference last week; two days of pure mathematics talks to lure us into postgraduate study. There are very few ‘pure’ topics I wouldn’t enjoy a lecture on, and I’ve been attending my own university’s staff/postgrad colloquia series this semester simply out of mathematical curiosity and enthusiasm. But beyond this entertainment value, the Durham lectures helped confirm/deny some opinions on potential research areas, so the event was certainly worthwhile.

Michael Drischel (Nottingham) gave the first talk, on Sums of Squares, which you can find online, so I won’t discuss the content too much.

Bill Jackson (Queen Mary London) presented a talk on Rigidity of Graphs concerning combinatorics and graph theory. The first section was presented using the geometry package Cinderella with which I was working for my summer research, demonstrating its many applications. This isn’t a field I’ve studied at all, but the ideas are both accessible and interesting so the talk was one of my favourites. There were even some connections to organic chemistry, which I haven’t thought about for a long time!

Patrick Dorey (Durham) gave a talk entitled Surprises in Quantum Mechanics; sadly I doubt I can ever get to grips with this topic (I can only remember abandoning two books partly read, and both were on Quantum Physics). However (ignoring a talk on funding) the next talk managed to overcome even my general dislike of Physics- Nina Snaith (Bristol)’s talk Every moment brings a treasure: how physicists came to the rescue of number theory. This was one of the more entertaining presentations anyway, but the central result was genuinely intriguing- how random matrix theory, a topic developed in the context of mathematical physics, was able to back up conjectures related to the Riemann zeta function arrived at by traditional number theoretic approaches. The method has turned out to have applications in other areas, and even features as a plot device in the film Proof!

The first day closed with a traditional talk-and-chalk on Geometry and integrability by David Calderbank. Due to a quirk of the MMath structure, I wasn’t allowed to take our differential geometry course. So this was a topic I knew very little about; the talk itself was interesting but I don’t think the field holds much appeal for me. Playing with surfaces is fun, but I prefer my analysis to be more topological rather than heavily connected to calculus.

Some of the ideas of the previous talk were picked up in the first of day two; Michael Singer (Edinburgh) giving an outline of a popular example of an integrable systems in a talk entitled The geometry of nonlinear waves. I’m hoping to track down the Maple worksheet for this one; you really have to see the graphs (or perform experiments with canals!) to appreciate what’s going on.

The most influential talk for me was John Cremona (Nottingham)’s Explicit methods in Number Theory. This was more accurately subtitled Rational points on curves and has cemented my interest in Algebraic Number Theory. For some time I’ve been deliberating between algebraic geometry and algebraic number theory; hindered by our lack of a number theory course at Bath! Based on this talk (and fortunate discussions with John at breakfast) it seems that the aspects of the algebraic geometry course I particularly liked more naturally fall within the remit of number theory; as do the bits of computer algebra that I enjoyed.

Norbert Peyerimhoff (Durham) spoke on averaging and equidistribution problems in geometry; I think this was another talk-and-chalk but I didn’t make notes because the content didn’t really appeal (didn’t help that it got very difficult very quickly!). Similarly Cobordism and groups of formal power series by Neil Strickland (Sheffield) confirmed that algebraic topology, whilst utterly fascinating, is really really difficult. Maple users can find the talk itself at this address, a non-interactive pdf version is also available if you can’t read Maple10 (it seems that, with Maple9.5, I can’t).

The final talk, given by Farid Tari (Durham) Singularities and the imagination offered more diffgeo, and an opportunity for me to demonstrate my complete lack of spatial awareness during the ‘practical’ component where we attempted to build some surface out of a piece of paper! Again, interesting as a talk but not as a career (although Farid was a very good speaker and well suited to holding our attention at the end of a demanding two days).