Dynkin diagrams and the Mahler measure problem

Funnily enough, a few days after I wrote the previous post, I was linked to a graph theory paper where one of the first results cited, which was clearly well-known to the authors, is the following remarkable generalization of what I tried to do:

Theorem: The only connected simple graphs with spectral radius less than or equal to are the induced subgraphs of the Dynkin diagrams .

I have to admit, I really didn’t suspect that the classification result I was going after was both so simple and so interesting! Certainly there are heuristic reasons why the above classification makes sense: as I forgot to note in the previous post, there really can’t be too many vertices of degree in a graph with . But I really can’t fathom why spectral radius can be used to define the Dynkin diagrams, considering their relationship to

– simply laced Lie groups,

– binary polyhedral groups and the Platonic solids,

– quiver representations, or

– the octonions (okay, this one is stretching it a little).

Anyone know any good references?

In any case, I’d like to discuss the McKee-Smyth paper because it has some interesting ideas I’d thought about independently.

Here’s the basic idea: the adjacency matrix of a graph acts as a linear operator on the underlying vector space. The algebra spanned by is a commutative subalgebra of what’s called the adjacency algebra of , which is sort of a generalization of the incidence algebra of a poset. Studying walks on is basically equivalent to studying this algebra (or at least I’d like it to be, but walks are very “coordinate-dependent” in a way that bothers me). If has minimal polynomial , then abstractly this algebra is isomorphic to (or whatever other underlying field you want; is the place where you have eigenvalues.)

So this algebra, if we replace by , is also an algebraic extension by a root of . (To be more precise, the adjacency algebra is a representation of this abstract quotient.) This suggests an interesting idea: study algebraic numbers by studying graphs whose adjacency algebras are isomorphic to .

This is exactly the point of view taken by McKee and Smyth, who use it to study Salem numbers and Pisot numbers. Before I talk about these specifically, one general construction that lets us study (certain) algebraic numbers as graphs is pretty much as simple as you could hope for: write down the action of acting by left multiplication on the basis (where is algebraic of degree ), and take this to be the adjacency matrix of some graph; this is (some version of) the companion matrix of the minimal polynomial of .

Of course, this will only give an adjacency matrix in the case that the minimal polynomial has the form for some non-negative integers , but bear with me here. There’s actually a neat way to interpret this graph: closed walks starting from the appropriate vertex of length count the number of colored tilings of a board of size by colors of tiles of size , etc.

McKee and Smyth don’t take this approach, mostly because the graph I described is directed and has multiple edges and self-loops and apparently graph theorists don’t like those. Everything is nicer if you stick to simple graphs. So, to try to motivate their actual construction, look at the example of the cycle graph: you can use it to think about the roots of unity, but since it’s an undirected graph its eigenvalues are real, and are a “symmetrization” of those eigenvalues. (This motivation is made precise by Proposition 6 in the paper, which I am still trying to digest.)

So here’s the idea (with a technicality in the bipartite case): to study , find a simple graph with largest eigenvalue satisfying . Then the graph Salem numbers can be defined as follows: is a graph Salem number if is the only eigenvalue of greater than .

Intuitively, this is a kind of approximability condition: the number of walks on is well-approximated by the powers of its greatest eigenvalue. This is one of the reasons I think the graph-theoretic setting is the more natural setting to understand what is called the Mahler measure problem. The Mahler measure of a polynomial is the product of the absolute values of its roots with absolute value at least : again, this is a kind of approximability condition regarding walks on the corresponding graph (although there is probably a better interpretation here that I don’t understand; see the Mathworld article) and so it can be regarded as a kind of generalization of the spectral radius. The problem is to show that a certain polynomial has the smallest Mahler measure greater than one.

The trivial observation here is that the Mahler measure of a polynomial corresponding to a Salem number is just its largest eigenvalue, so classifying the graph Salem numbers is a step in the right direction towards classifying the possible Mahler measures of integer polynomials. What Smyth and McKee proved, among other things, was that, taking the above definition of a graph Salem number and turning it into the definition of the Mahler measure of a graph, the Mahler measure conjecture is true for graphs. That is to say:

Theorem: The Mahler measure of a graph is either or at least , the largest real root of .

This is a consequence of a classification result of graphs of small Mahler measure, which turn out to be mostly Salem trees.

I think that this is a great way of thinking about the conjecture. I can’t, offhand, think of a convincing “algebraic” reason that the set of Mahler measures of monic integer polynomials greater than one would have a lower bound, but thinking about Mahler measures in terms of growth rates of walks on graphs makes it all very intuitive: although I haven’t gone through the details of the paper, I’d like to think it’s essentially a more careful version of the elementary arguments I gave in the last post, and in that context it makes perfect sense that Mahler measure can’t be too small because walks on graphs can’t grow too slowly. So corresponds to some special graph that doesn’t branch too often but also that doesn’t have too many vertices.

Anyway, I’ll end with a call for help and a legitimate question:

– Is there a particularly slick way of computing the characteristic polynomials of the Dynkin diagrams other than , and how do they relate to all that other stuff? (A recursive approach to should, but I can’t really wrap my head around the type cases.)

– Should it be possible in principle to extend Smyth and McKee’s classification results to directed graphs and would this be enough to prove the full Mahler measure conjecture?