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.