I’m back! And rather surprisingly, I seem to have gained a lot of readers in my absence. Having not even logged on to WordPress for a few months, I have returned to see that my google reader subscription rate has doubled, and the number of people visiting the blog has increased by more than at any point since I started writing it. I’m not really sure what lesson to take from this. Probably it is just the natural result of a gradual snowballing effect: over time more people click on your site, the google rankings go up, causing more people to click on your site…
Then again it’s possible that people just prefer it when I don’t write anything! Well I’m sorry those people, but I intend to start again. Although possibly even more erratically than before.
Anyway, I will explain the terrible sequence of events which led me to abandon blog shortly, but first, a shameless Rupert Murdoch-style using of one of my products to promote another! (I would do this at the end, but am rather doubtful as to how many people actually make it to the end of my posts). Having been introduced to Vietnamese coffee by my father-in-law a while ago, I have utterly fallen in love with it, and realised that it is very difficult to find here in the UK. So I have set up a (very) small business selling it. The website is here. Try it! You won’t be disappointed.
Sorry about that. Now, this is what happened. Having struggled with the proof of a knotty mathematical problem for the better part of a year, I was advised by my supervisor to publish what I had. So I put the paper on the arXiv (an online preprint archive), not really expecting to achieve anything, but generally wanting to share the knowledge out of a spirit of altruism (and self-promotion). Within a few hours of it appearing, a certain Peter Mueller had read it, and proved the last part of the conjecture! (So there you go doubters: people do read your preprints). This was wonderful news; we invited him to be a co-author, and set about writing a final draft. I also wrote a whole long blog post about how great this was, and what it all meant. But then a couple of days later Prof. Mueller sent me some rather less good news: he had found a mistake in my work, which completely invalidated the whole thing…
Disaster! 9 months work, all for nothing! In my mind, within the space of two or three days, I had gone from being a Great Mathematician to a miserable failure…I had had no idea when attempting to embark on a career as a mathematician that it would be so emotional. Luckily I had time to delete my prematurely triumphant blog post (although it may still have appeared on google reader, with a mysterious error message), and so at least saved some face. I then realised that my time would generally be better spent actually doing mathematics rather than writing a blog about doing mathematics, and vowed to postpone any further posts until I actually had some results.
Well…good news (again)! We have now definitely proved the theorem…in fact we have gone further and proved a more general result (the new, correct paper is here). And in the process I have learnt lots of algebraic number theory and matroid theory. So I feel that I deserve to be allowed to write on my blog again. Although for now I am not even going to write anything new, just dredge up parts of that triumphant post of old (which is now rather painful to look at), in which I attempted to explain in layman’s terms what exactly it is that we have proved.
So…I explained briefly what a graph is in this post: basically just a bunch of dots (vertices) with lines (edges) joining some of them to others. To “vertex colour” a graph is to assign a colour to each of the vertices a colour, and a “proper vertex colouring” is a way of doing this so that no two vertices which are joined by an edge have the same colour. This is not just an intellectual game; it has many applications and analogies in real life. What originally motivated the study of graph colouring was the Four Colour Theorem – a very famous result in mathematics which says that, given any map – fictitious or not – it is possible to colour the countries with only four colours so that no two countries sharing a border have the same colour (if that sounds unlikely, try to draw a counterexample!). By assigning a vertex to each of the countries, and drawing an edge between two vertices when those countries share a border, this is reduced to the problem of colouring a “planar graph” – that is, a graph which can be drawn with no edges crossing each other.
Now, every graph has a “chromatic polynomial”, (see this post for a definition of a polynomial) which is a function that tells us the number of proper colourings of a graph with a given number of colours. If we input an insufficient number of colours into a graph’s chromatic polynomial to properly colour it with, the chromatic polynomial will give an output of 0, and any such number is known as a “chromatic root”. But there are some complex chromatic roots which don’t correspond to any number of colours…it is unclear what exactly these signify, and a lot of effort has been made to understand them. We can look at complex roots of polynomials from various perspectives, depending on what kind of mathematics we are in the business of doing. Personally, I have been interested in their algebraic properties: their properties as roots of polynomials, how they interact with each other, to what extent they exist in some kind of system.
I’m beginning to think that it may be too ambitious to attempt a full layman’s explanation in one blog post…but I will plough on regardless. The study of the relations between roots of polynomials in known as Galois theory, after a French mathematician who died in a duel at the age of 20, having laid the foundations for group theory, and in the process revolutionising mathematics. The Galois group of a polynomial can be thought of as the measure of to what extent the roots can be permuted amongst themselves, whilst still preserving the structure of the underlying number field. And understanding which groups appear as Galois groups of chromatic polynomials, and what relation they have to the structure of the graph, is what has motivated our work.
[A slight digression here: I find that people’s first reaction when they have mathematical research explained to them is to ask for concrete, “real-world” applications, and I have generally tried to provide them on this blog. Unfortunately at present I would be hard-pressed to think up a real-life, humanity-furthering consequence of understanding the Galois groups of graph polynomials. But as has been shown time and time again – especially in mathematics – the usefulness of a given piece of work often does not become apparent for years. In fact, given the current threat to academic funding (see Peter Cameron’s post on this), I may write my next post on “Mathematics which seemed useless but wasn’t!”]
Anyway, at this point you might be wondering why our paper concerns the Tutte polynomial rather than the chromatic polynomial. Well…the Tutte polynomial is a generalisation of the chromatic polynomial. It is a polynomial in two variables, and by substituting in certain numbers for one or both of the variables we can obtain various useful graph polynomials and other structural information. In particular, we can – to some extent – study the algebraic properties of chromatic roots by considering roots of the Tutte polynomial. The multivariate Tutte polynomial is a further generalisation of the bivariate case…it was introduced by Alan Sokal, and appears in statistical physics as the Potts-model partition function. I’m afraid I have no idea in what context (something to do with spins in a crystalline lattice?), but it is always heartening to know that one’s object of study is not a complete abstraction. In fact, there you go: real-life applications! I would imagine that crystalline lattices are probably very useful things.
To cut a long story short, we have worked out the Galois group of the multivariate Tutte polynomial of every graph. And in fact, we went further, and proved the result for matroids, which are generalisations of graphs (sort of). So to summarise: we have shown that a very general polynomial of a very general object has a very large Galois group. And it only took a year! (That is, it took me a year. I would imagine that my co-authors probably collectively put in a month or so, and yet still managed to do as much of the work as me).
For any other novice researchers reading this, here is a list of things I have learnt in the process of writing this paper which they don’t teach you at university (and which will hopefully help me to write my next paper in less than a year):
- If you think you have proved something momentous, you probably haven’t. Check all the details thoroughly, then go to bed, and check again the next morning. Read through all the literature again to make sure it isn’t already known. Check the details again. Only then should you email your supervisor. And only when he/she has checked it should you actually get excited about it/write it up/write a blog post about it/tell anyone you know.
- Don’t go dabbling in areas of mathematics you know nothing about. My original mistake was to use the Newton Polygon without knowing how it worked, or even anything about algebraic number theory. It seemed like magic! Which I now know is a sure sign something is wrong. Make sure you understand why something works before you use it.
- If you can’t understand something, try again. If you still don’t get it, don’t waste endless time screwing your brain out about it…see if someone else can help! Math Overflow is particularly useful for this sort of thing. On the other hand, don’t rely on the internet too much. I sometimes find that my first reaction when presented with something I have half-forgotten is “google!”, when it would be much more useful work it out myself.
- Don’t bother writing up “final drafts” of your work until you are absolutely sure everything is in place. You will just end up with “final final final” drafts, or a whole series of numbered files which start to get confusing. This especially applies to fiddling about with things like page-breaks and formulations in LaTeX. They will just become defunct when you add more to the paper (and anyway, as my supervisor told me, the journal editors will just change it all anyway!)
- If you get stuck, instead of sitting there bloody-mindedly refusing to budge until you work it out, just get up and do something else for a while. Often a change of scene seems to precipitate sudden revelations about things.
- Go to seminars! I am guilty of often being of the mindset: “it would be more useful to stay here and keep working on this”. Even if the subject is completely unrelated to your work, sometimes just hearing people talking about mathematics can lead to all sorts of rearrangement of synaptic connections. The worst that can happen is that you don’t understand a word of it, in which case you can ignore the speaker and continue working!
- Stop working when you are in the middle of something. This may seem like rather odd advice, but I find that if I use up all my ideas one day, it can be hard to get started the next day. I you have something definite to do, then you can get back into the mathematical mindset straight away. It’s all about keeping up momentum!
There are probably lots more…I think they should give you a manual when you start your PhD. In the absence of this, does anyone else have any research tips they’d like to share?