Bleg: testing algebraic integrality by computer.

Update 2: we’ve found a nice answer to our question. Maybe it will appear in the comments soon. –Scott M

Scott, Emily, and I have an ongoing project optimistically called “The Atlas of subfactors.” In the long run we’re hoping to have a site like Dror Bar-Natan and Scott’s Knot atlas with information about subfactors of small index and small fusion categories. In the short run we’re trying to automate known tests for eliminating possible fusion graphs for subfactors.

Right now we’re running into a computational bottleneck: given a number that is a ratio of two algebraic integers how can you quickly test whether it is an algebraic integer? Mathematica’s function AlgebraicIntegerQ is horribly slow, and we’re not sure if that’s because it’s poorly implemented or whether the problem is difficult. So, anyone have a good suggestion? After the jump I’ll explain what this question has to do with tensor categories (and hence subfactors which correspond to bi-oidal categories as I’ve discussed before).

To whet your appetite, here’s an example. Is , where

and where is the largest real root of

an algebraic integer? Mathematica running on Scott’s computer (using the builtin function AlgebraicIntegerQ) takes more than 5 minutes to decide that it is.

Update: Thanks to David Savitt for pointing out that both this example and an earlier one are answered instantly by MAGMA. Blegging is already working. But what’s the trick? Is it something we can teach Mathematica quickly? –Scott M

By to why we care. Suppose you have a semisimple tensor category. The tensor product turns its Grothendieck group into a ring, and the basis of simple objects gives this ring a distinguished basis of simple objects. If the tensor category has duals, then this basis also has an involution such that XX* = 1+other terms and such that XY has no 1′s in it at all for Y other than X*. We’ll call such a ring a fusion ring.

Choose your favorite simple object X. For simplicity we’ll assume that X is self-dual. Then we can build a fusion graph whose vertices are the basis of simple objects such that A and B are connected by a number of edges coming from the coefficient of B in AX. If X is a tensor generator and the tensor category has some nice positivity properties, then is the largest eigenvalue of the adjacency matrix of this graph. As such it is automatically an algebraic integer. Similarly, by considering the fusion graphs built from other objects in the category you can see that all of the dimensions must also be algebraic integers. However, the dimensions of the other simple objects can be read off from the original graph by looking at a normalized eigenvector for the adjacency matrix of the fusion graph from X corresponding to the eigenvalue .

So suppose we start with some fusion graph and we want to know if it comes from some fusion ring. One test is to compute all the dimensions of the other objects and see if they are algebraic integers. If they aren’t, then the graph can’t have come from a fusion ring

In Scott’s example above the relevant graph is:

The dimension that he mentions corresponds to the lowest vertex in the graph.

(Notice that this condition works at the decategorified level of the fusion ring. It turns out that if you want the fusion ring to come from a fusion category, then a beautiful result of Etingof, Nikshych, and Ostrik says that not only must these dimensions be algebraic integers, they need to be cyclotomic integers! Hopefully I’ll return to this in a more fleshed out post later this year.)

About these ads