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 a/b, where

a=-293 \lambda^{11}+4624 \lambda^9-23668 \lambda^7+50302 \lambda^5-44616\lambda^3+14017 \lambda

b=131\lambda^{10} - 2033 \lambda^8 + 9974\lambda^6-18951\lambda^4+12233 \lambda^2-1475

and where \lambda is the largest real root of

1 - 58 x^2 + 175 x^4 - 186 x^6 + 84 x^8 - 16 x^{10} + x^{12},

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 \dim X 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 \dim X.

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.)

8 thoughts on “Bleg: testing algebraic integrality by computer.

  1. As a matter of curiosity, have you checked to see if how long it takes to return a “yes” for some algebraic integer is related to its degree?

  2. I think Magma knows a lot more about algebraic structures than Mathematica (and Maple), and this expertise has been engineered for quite a while now. Pari/GP, which is free software, also does it instantly, but both software are written by specialists who are usually expert programmers as well as outstanding number theorists (in particular, algebraic number theorists).

  3. It turns out that the big problem was that we needed to simplify the expressions first using Euclid’s algorithm for polynomials. Mathematica has a function that does this, but somehow RootReduce wasn’t exploiting that function. Once David Savitt pointed out that the problem was in failing to simplify well, we put in a simplifying step by hand and most of the performance gap between MAGMA and Mathematica went away.

  4. Maybe I’m missing something obvious, but your definition of fusion graph suggests that it should be directed. Is there some theorem that makes everything symmetric?

  5. What you’re missing is where I said “For simplicity we’ll assume that X is self-dual.”

    For a general fusion category you end up with a directed graph. For a subfactor you end up with a pair of undirected bipartite graphs.

Comments are closed.