Abelian Spiders

This is a blog post about the thesis of my student Zoey Guo, who is graduating this year. (For a blog post on the thesis of my other student graduating this year, see this.)

Let \Phi be a finite graph. Associated to \Phi is an adjacency matrix M such that the largest eigenvalue \lambda is totally real. Let us call \Phi abelian if the extension \mathbf{Q}(\lambda^2) is abelian. For example, all the Dynkin diagrams are abelian.

Several years ago, Scott Morrison and Noah Sydner (of secret blogging seminar fame) asked the following question. Given a finite graph \Gamma, let \Gamma_n be the graph obtained by adjoining a 2-valent tree of length n to some fixed vertex v of \Gamma. Then can one classify all n for which \Gamma_n is abelian? It turns out \Gamma_n can be abelian for only finitely many n, unless the graphs \Gamma_n happen to be one of the two infinite families of Dynkin diagrams. The argument was effective, although not effectively effective. (We did, however, prove a slightly weaker theorem which was sufficient for the intended application which was effectively effective.)

What Zoey does in her thesis is consider the following generalization. Let \Gamma be a finite graph, and choose k vertices v_i of \Gamma. Now adjoin k two-valent graphs of varying lengths \underline{n} = \{n_i\} to latex v_i. Call the resulting graph a k-spider graph. The main result of her thesis is the following:

Theorem: For any \Gamma and any fixed k, only finitely many of the corresponding spiders are both abelian and not Dynkin diagrams.

What is more, the theorem is effectively effective. One key ingredient in the finiteness results for k = 1 was the fact that, for characteristic polynomials P_n(X) of the graphs \Gamma_n, one can control the factors corresponding to Chebyshev polynomials. Or, if one writes

Q_n(t) = P_n(t + t^{-1}),

one can control the cyclotomic factors of Q_n(t). This follows from a theorem of Hironaka-Gross-McMullen, who exploit results by Mann on vanishing sums for roots of unity. However, when k \ge 2, this breaks down completely. In fact, in many examples, the corresponding polynomials P_{\underline{n}}(t+t^{-1}) will be divisible by cyclotomic polynomials of arbitrarily large degree. Here’s an example which Zoey pointed out to me. Consider the disconnected graph consisting of a two copies of the Dykin diagrams A_{n-1} and a third component A_{m} for any integer m (in fact, the construction is much more general, but we will be very explicit here). Since \zeta + \zeta^{-1} for \zeta^{n} = 1 is an eigenvalue of each connected component corresponding to A_{n-1}, it will be an eigenvalue of multiplicity (at least) two of their union. Now join the three graphs by adding a vertex which is connected to the end of all three graphs; this will be the 3-spider on a point corresponding to the triple (n-1,n-1,m). By the interlacing lemma for graph eigenvalues, \zeta + \zeta^{-1} will be an eigenvalue of the resulting connected graph. So finding all the cyclotomic factors even for the explicit polynomials coming from 3-spiders on a point seems like a real pain, and so one needs a new argument to deal with roots of unity.

The proof of the theorem comes down to two key steps. First, for any sequence of spiders, all but a uniformly bounded number of eigenvalues will lie in the interval [-2,2], and all the eigenvalues will lie in some uniform interval [-M,M]. Of course, this means that the squares of the eigenvalues lie always in [0,M] for some M and mostly in [0,4]. Now imagine the largest such number \lambda^2. We know that it is algebraic, and we are assuming that it is abelian. The key quantity to control turns out to be the normalized trace of \gamma:=(\lambda^2 - 2)^2. Work of Cassels shows that, if \lambda^2 is cyclotomic, one can classify all cyclotomic integers for which the normalized trace of \gamma is small. What kind of an upper bounds do we have? Well, if the degree of \lambda is very large, then the bulk of the contribution has to come from \lambda \in [-2,2], or \lambda^2 - 2 \in [-2,2] (this is the reason why \lambda^2 - 2 occurs above — it is a Chebyshev polynomial). The worst case scenario is that all of the conjugates of \lambda^2 are near 4, which will give an estimate on the normalized trace of \gamma of 4 plus a quantity that goes to zero with the degree. However, it is hard for an algebraic number to have too many of its conjugates near any particular integer (in this case, 4). To exploit this, one can note, for example, that

3 - x - \log(4 - x) \ge 0, \quad x \in [0,4].

If we denote the conjugates of \gamma:=(\lambda^2 - 2)^2 by \sigma \gamma and suppose that this has degree n, then we deduce that

\displaystyle{3n - n \mathrm{Tr}(\gamma) - \log \left(\prod (4 - \sigma \gamma) \right) \ge O(1).}

The O(1) term (which is completely explicit) comes from the fact that finitely many of the \sigma \gamma are outside [0,4] and so one can not use the previous inequality. Let us consider the inequality. As long as \gamma \ne 4, the logarithmic factor is a norm of the algebraic integer 4 - \gamma, and hence non-negative. So we get an upper bound for the normalized trace which is now 3 plus some explicit error term which tends to zero as the degree goes to infinity. This type of idea was first used by Chris Smyth when studying the trace problem of Siegel (see this post). Now 3 is still too big to apply the results of Cassels. So one has to also exploit that (\lambda^2 - 2)^2 is not too close to 3 either (this is the where the inequality above is an equality). In fact, one ends up using not just 4 and 3 but 43 different algebraic integers which are all of the form 2 + \zeta + \zeta^{-1}, and where one uses logarithms weighted by various real constants. The precise constants and algebraic integers were optimized by simulated annealing. In the end, one gets an upper bound of the form 2.4 plus a very explicit error term, which is enough for the Cassels machine. This gives a complete answer as long as the degree of \lambda is big enough.

If \lambda has small degree, then one is also in good shape — given a bound for \lambda and a bound for the degree, there are only finitely many such algebraic integers, which is enough to prove the theorem. However, this last step — whilst effective — is not at all effectively effective. So another argument is required to make everything work in practice. Note that the degree of the polynomial defining \lambda certainly goes to infinity, but it may be irreducible reducible, and in particular divisible by many cyclotomic (Chebyshev) factors all of whose roots are in [-2,2]. Let’s explain how to overcome this issue in the case of 3-spiders coming from the trivial graph (which is typical of the general case). If you take the 3-spider with legs of length (a,b,c), then, for (a,b,c) big enough, one finds that

\displaystyle{\lambda \rightarrow \frac{3}{\sqrt{2}}}.

(The limit of the largest eigenvalues of a sequence of infinite spiders will always be an algebraic number.) Importantly, this convergence is exponential. However, it’s easy to see that any algebraic integer all of whose conjugates are uniformly bounded can not be extremely close to any fixed algebraic number, and it easy to give effective bounds to this effect. So one wins in high degree by Cassels type arguments and in low degree by the fact that the eigenvalues converge rapidly to computable algebraic numbers. One annoying issue is that the convergence requires all of the (a,b,c) to tend to infinity, so one has to inductively reduce to the case of 2-spiders with some finite list of possible c, which entails a certain amount of combinatorial explosion. However, as a complete worked example, one has the following:

Theorem: The complete list of abelian 3-spiders on a point is given by:

  1. The Dynkin diagrams A_n, D_n, E_6, E_7, E_8, \widetilde{E}_6, \widetilde{E}_7, \widetilde{E}_8, whose largest eigenvalue is of the form \zeta + \zeta^{-1},
  2. The 3-spiders (3,3,3), (2,4,4), and (2,3,7) with
    \displaystyle{\lambda^2 = \frac{5 +\sqrt{13}}{2},}
  3. The 3-spiders (3,3,7), (2,8,8), and (2,7,11) with \zeta^{13} =1 and
    \displaystyle{\lambda^2 = \zeta^{11} + \zeta^{10} + \zeta^3 + \zeta^2 + 2,}
  4. The 3-spiders (4,4,4), (3,5,5), and (3,4,9) with
    \displaystyle{\lambda^2 = 3 + \sqrt{2}.}

Now all of this is quite amusing, but you may complain that is doesn’t really have any practical application. However, as it happens, Scott Morrison asked me whether it was possible to find all abelian 2-spiders for some very explicit graph (omitted here), in order to further the classification of finite index subfactors, because the all the current non-number theoretic obstructions could not rule out this family of examples as coming from subfactors. Zoey’s method could be applied to show that every 2-spider in the corresponding family was not abelian. So Zoey’s results have already been used outside her field (see forthcoming work of Morrison and his collaborators) to complete the classification of subfactors of index between 5 and 3 + \sqrt{5}. All this, of course, while having the thesis with the best title.

This entry was posted in Mathematics and tagged , , , , , , , , . Bookmark the permalink.

4 Responses to Abelian Spiders

  1. Happily, we’ve found yet another application of Zoey’s results in the classification of subfactors, and indeed our almost finished paper on the classification up to index 3+\sqrt 5 will make two independent, and rather different uses, of this work.

    The first is the example you talk about above and that Zoey used as an illustration of the method.

    The second is even more exciting — and we haven’t yet had a chance to see if this method could help pushing the classification even further.

    The basic idea is that we have a family of graphs as follows: fix some finite graph \Gamma, and mark one vertex “x”, and name all the vertices at the maximal radius from x “Y”. We now consider adding a chain of n edges to x, and gluing on some arbitrary finite graph to Y.

    For the \Gamma we’re interested in (and possibly ‘often’) we can show by the theory of ‘connections’ that any graph in this family which is the principal graph of a subfactor must have graph norm satisfying some particular polynomial depending just on n (and not on what we glue to Y).

    Now we don’t know that this polynomial has anything to do with any particular finite graph (in fact, it’s a multiple of the minimal polynomial for the norm of a certain infinite graph) so we have to work a bit harder in places to apply Zoey’s method, but happily it all works out, and one can show that the graph norm cannot possibly be cyclotomic, thereby ruling out all graphs in the family as principal graphs of a subfactor.

  2. In the para. beginning “If \lambda has small degree, then one is also in good shape … “, I think “may be irreducible” should read “may be reducible”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s