Modulo Errors

View as:

At The Diverse Faces of Arithmetic there were a pair of (early morning!) overview lectures for postgraduates. I’ve finally got around to typesetting my notes from the first, Tom Ward’s session on recurrence sequences, available as pdf via the above link. The topics included are divisibilty sequences and primitive divisors; linear recurrences; elliptic divisibility sequences; integrability/ Laurent phenomena; growth rates and Lehmer’s problem.

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.

Tomorrow, in what seems to be becoming an annual tradition, I’ll be giving a talk on cryptography at the Geometry Club. Since it’ll be a talk-and-chalk style seminar, I don’t have any slides to make available, but many of the topics I’ll be discussing have appeared earlier on this blog or everything2. In particular, I’m planning to include:

• A brief overview of public-key cryptography: my notes from last year’s talk cover technical details in the context of (EC)DLP, or there’s this friendlier article on Diffie-Hellman key exchange and man-in-the-middle attacks.
• The problems of Authentication and Mutual Authentication at a protocol level.
• The undecidability of the secrecy problem via Post’s Correspondence Problem.
• Lattice-based cryptography- which hopefully I can summarise in a later post.

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.

Yesterday I gave another postgraduate colloquium, on the basics of public key cryptography. The slideshow I used is here [pdf], although obviously it’s missing the narrative to go with it. The first part, on sharing secret colours, was lifted from the talk described here, although I discussed the discrete logarithm problem in group-theoretic terms this time.

On Friday I gave a geometry club seminar, speaking about some of the computational aspects of discrete-logarithm cryptography in general and as implemented for elliptic curves. My notes supplement rather than completely describe the talk, being heavier on the formalities and lighter on the narrative.

The topics covered are: Diffie-Hellman and one-way functions for key exchange; the generic Discrete Logarithm Problem and BSGS algorithm; scalar multiplication- addition chains, fast exponentiation, m-ary methods and windowing; group law implementations, Side-channel attacks and the Edwards form.

I’ve discussed several of these ideas elsewhere on this blog, as well as the cryptanalysis ideas I mentioned on the day but which are not in the notes. I also refered to a recent real-world example of a side-channel attack; see this story from The Register for details.

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.

The latest version of my ellnet class is ellnet2d_lowmem.spyx. It combines all the tricks I know of:

• The use of precomputed inverses for all steps, and precomputed squares/products for each step, as described by Stange,
• computation with a local vector to avoid overhead from function calls to keep the dictionary up-to-date,
• mixed block lengths as described in the previous post,
• and compilation to pyrex.

Thus it’s the fastest implementation I currently have for finding Tate pairings in SAGE (about twice as fast as accessing Stange’s PARI script from SAGE). Attach it in the normal way; example calculations are here.