Idle question: cluster algebras over finite fields and spectral gaps

Yet another great talk at the JMM:  Lauren Williams gave an introduction to cluster algebras in the Current Events section which was perfect for people, like me, who didn’t know the definition.  (The talks by Wei Ho, Sam Payne, and Mladen Bestvina were equally good, but I don’t have any idle questions about them!)

This post will be too long if I try to include the definitions myself, and I wouldn’t do as good a job of exposition as Williams did, so it’s good news that she’s arXived a survey paper which covers roughly the same ground as her talk.

Setup for idle question:  you can get a cluster algebra comes from a process called “seed mutation” — given a rational function field K = k(x_1, … x_m), a labelled seed is a pair (Q,f) where Q is a quiver on m vertices and f = (f_1, … f_m) is a labelling of the vertices of Q with rational functions in K.  For each i, there’s a seed mutation mu_i which is an involution on the labelled seeds; see Williams’s paper for the definition.

Now start with a labelled seed (Q,(x_1, … x_m)) and let T be the set of labelled seeds obtainable from the starting seed by repeated application of seed mutations mu_1, …. m_n for some n < m.  (I didn’t think carefully about the meaning of this special subset of n vertices, which are called the mutable vertices.)

It’s called T because it’s a tree, regular of degree n; each vertex is indexed by a word in the n seed mutations with no letter appearing twice in succession.

Anyway, for each vertex of T and each mutable vertex i you have a rational function f_i.  The cluster algebra is the algebra generated by all these rational functions.

The great miracle — rather, one of the great miracles — is that, by a theorem of Fomin and Zelevinsky, the f_i are all Laurent; that is, their denominators are just monomials in the original functions x_i.

We are now ready for the idle question!

Let’s take k to be a finite field F_q, and let U be (F_q^*)^m, the rational points of the m-torus over F_q.  Choose a point u = (u_1, … u_n) in (F_q^*)^m.

Then for any vertex of T, we can (thanks to the Laurent condition!) evaluate the functions (f_1, …. f_m) at u, getting an element of F_q^m.

So a random walk on the tree T, combined with evaluation at u, gives you a random walk on F_q^m.

Idle question:  Is there a spectral gap for this family of walks, independent of q?

Update:  As David Speyer explains in the comments, this finite random walk is not in general well-defined.  Let me try another phrasing which I think makes sense.

Let t be the endpoint of a length-R random walk on T; then evaluation at (1,1,..1) gives a probability distribution P_{R,N} on (Z/NZ)^m.  Let U_N be the uniform distribution on (Z/NZ)^m.  Now for each N we can ask about the limit

\Lambda_N = \lim_{R \rightarrow \infty} ||P_{R,N} - U_{N}||^{1/R}

(I don’t think it matters what norm we use.)

The idea is that the random walk on the tree should be equidistributing mod N, and the speed of convergence is governed by Λ_N.  Then we can ask

Idle question mark 2:  Is Λ_N bounded away from 1 by a constant independent of N?

This is a question in “spectral gap” style, which, if I did it right, doesn’t a priori have to do with a sequence of finite graphs.

Motivation:  this setup reminds me of a very well-known story in arithmetic groups; you have a discrete group Gamma which comes equipped with an action on an set of objects “over Z” — then reducing mod p for all p gives you a family of actions of Gamma on larger and larger finite sets, and a critical organizing question is:  do the corresponding graphs have a spectral gap?

For that matter, what happens if you, say, keep k = C and then evaluate your f_i at (1,1,… 1)?  Looking at a bigger and bigger ball in the tree you get bigger and bigger sets of elements of C^m; what do these look like?  Do they shoot off to infinity, accumulate, equidistribute…..?


Tagged , , , , , ,

10 thoughts on “Idle question: cluster algebras over finite fields and spectral gaps

  1. David Speyer says:

    I think studying dynamical systems in cluster algebras is interesting, but I think the precise question about F_q doesn’t work. Your random walk isn’t well defined: If one of the coordinates of your point in F_q^m becomes zero, then we can’t divide by it at the next step.

    For example, I took the cluster mutation (x,y) \mapsto (y, (y^2+1)/x). (This is m=2, so the tree is just a path; this is cluster type \tilde{A}_1.) We can rewrite this as studying the recursion x_{n+1} = (x_n^2+1)/x_{n-1}.

    Take q = 5 and look at the orbit of (1,1). Formally plugging into the Laurent polynomials gives 1, 1, 2, 0, 3, 4, 4, 1, 1, \ldots repeating periodically. But directly using the recursion is undefined at (3^2+1)/0; you need to look at the general Laurent formulas to resolve this 0/0 quantity.

    I have a bunch more to say about this, but need to run now.

  2. JSE says:

    Exactly! Sorry, I have been chewing on this a bit today but didn’t want to modify the post until I understood things better.

    You need to do it over Q_p, and then the Laurent condition tells you that if you start at (1,1) [or anything in Z_p^* x Z_p^*] your orbit stays in Z_p^2, at which point you can reduce mod p. But as you say, it’s not literally a dynamical system on F_p^2. Or rather, it’s not a priori a dynamical system on F_p^2. But note that in the case you write down over F_5, you are indeed tracing a deterministic process on F_p^2; it’s just that the transition rule (0,3) -> (3,4) isn’t specified directly by the cluster mutation. Are there other orbits which contain (for instance) one consecutive sequence reducing to (0,3,4), and another reducing to (0,3,1)? I don’t immediately see why not. I think this is related to the question of whether the entries of the sequence are bounded away from 0.

    The (highly preliminary) computations I’ve been doing on some rank-2 cluster algebras suggest that the bounded orbits in this case are periodic mod p^k for every k, have coordinates bounded away from 0, and have closure of Minkowski dimension 1.

    Look forward to hearing further thoughts!

  3. David Speyer says:

    “The (highly preliminary) computations I’ve been doing on some rank-2 cluster algebras suggest that the bounded orbits in this case are periodic mod p^k for every k, have coordinates bounded away from 0, and have closure of Minkowski dimension 1. ”

    Kedlaya and Propp did a bunch of computations like this in . You might want to see how your results relate to theirs.

    The example I ran is very special because there is a conserved quantity: (x_{n-1}^2+x_{n}^2+1)/(x_{n-1} x_n). So the orbits do not only have Minkowski dimension \leq 1, they have Zariski dimension \leq 1!

    My understanding (but don’t quote me!) is that there is no analogous rational conserved quantity in the “wild” rank two cases. (A rank 2 cluster algebra is given by a B-matrix of the form \left( \begin{smallmatrix} 0 & b \\ -c & 0 \end{smallmatrix} \right). Finite type is bc \leq 3, affine type is bc=4 and wild type is bc \geq 5.) It would be very interesting if the p-adic orbit closures were level sets of some sort of non-algebraic conserved quantity.

    It would also be interesting to take a look at the “Markov” cluster algebra. The recurrence in question is to start with (x,y,z) and mutate one of the three variables to produce (\frac{x^2+y^2}{z}, y, z). In this example, the tree never folds back on itself, so we could ask more interesting questions about probabilistic distribution along the orbit closures. Here again, there is a conserved quantity: (x^2+y^2+z^2)/(xyz).

    In all of the examples we’ve brought up, mutation gives us an isomorphic seed. I think I do not know how to ask the right questions if mutation keeps changing the B-matrix. For example, suppose that we start with the B-matrix \left( \begin{smallmatrix} 0 & 3 & -3 \\ -3 & 0 & 3 \\ 3 & -3 & 0 \end{smallmatrix} \right). So the first round of mutation changes the signs of two of the 3‘s and turns the third one into a 6, the next mutation changes the signs of a 3 and a 6 and creates a 15, and so forth. In this setting, I’m not sure that there is a natural question to ask about orbits or random walks. Could you provide one?

    There has been a lot of work on integrable systems and cluster algebras, which is probably relevant. Unfortunately, as far as I can tell, there is no good survey, and I’ve had to pick up a lot of the ideas as folklore. I can tell you about some of them, but it might be more fun to just think about examples like the above.

  4. JSE says:

    Is the modified version of the Idle Question ok for the last example you give?

    Also: that Kedlaya-Propp paper you cite does indeed seem very relevant (and it seems that they explicitly say they don’t know whether the stability phenomena they study occur for Fomin-Zelevinsky type sequences, but that this is a reasonable question.)

  5. JSE says:

    More relevant info: the Somos 4 sequence of integers can be obtained via mutations from a certain 4-vertex quiver:

    and, as Lauren Williams pointed out to me, it was proved by Raphael Robinson in 1992 that this sequence is periodic mod N for every N:

  6. David Speyer says:

    Somos-4 should be analyzable very explicitly. There are two obvious symmetries: If s_n solves the Somos-4 recursion, so does a b^n s_n for any nonzero a and b. There is also a conserved quantity:
    T=\frac{s_{n-1} s_{n+2}}{s_n s_{n+1}} + \frac{s_n^2}{s_{n-1} s_{n+1}} + \frac{s_{n+1}^2}{s_n s_{n+2}} + \frac{s_n s_{n+1}}{s_{n-1} s_{n+2}}.

    If you fix T and scale out by the \mathbb{G}_m^2 symmetries, what remains is a genus one curve, and mutation is translation by a point on that curve.

    This was all worked out in the language of \Theta functions by Noam Elkies. I prefer the write up of Hone and Swart, which is in more modern algebraic geometry language.

    It is my understanding, but I can’t give you a direct citation, that there are a lot of examples like this one. Namely, take any of the cluster algebras from Goncharov and Kenyon arXiv:1107.5588 . They have dimension 2n+m, an action of \mathbb{G}_m^m and n conserved quantities. The n conserved quantities can be thought of as the coefficients of curve in a toric surface. Fixing all of the conserved quantities gives (at least rationally) the Jacobian of that curve. (More or less — it might be a twist of the Jacobian or a homogeneous space for it.) There is a sequence of mutations which returns the initial quiver to itself, and gives a translation in the Jacobian. All the Gale-Robinson sequences (s_n s_{n-k} = s_{n-a} s_{n-k+a} + s_{n-b} s_{n-k+b}) should fall into this setting.

    While this is a beautiful subject, it is my understanding that it falls dramatically short of covering all the quivers where a sequence of mutations returns them to itself.

  7. David Speyer says:

    Regarding the Idle Question when the quiver doesn’t return to itself: I see two problems.

    The first problem is the one that occurs in every case: Until you prove some sort of Robbins stability, you have to ask the question p-adically and it isn’t clear that there is any finite p^k such that we get a random walk on the \mathbb{Z}/p^k points. I don’t know how to define spectral gaps in this setting, but maybe you do.

    But let me brush that problem under the rug to bring up the second problem: Since the quiver is changing at every step, you don’t have a Marov process. (1) The rule to propagate from stage n to stage n+1 is not the same as the rule to propagate from stage n-1 to n but, even worse (2) Different points in the stage n cloud will be propagating according to different rules, because they will come from different mutation histories that give different quivers.

    Now, you can still ask what the Minkowski dimension of the limit points is, and some questions about probability distributions in the limit. But it seems much less natural to me. Specific questions about the spectral gap don’t seem to make sense to me, but maybe you have a broader understanding of spectral gaps than I do.

  8. JSE says:

    My modification of the Idle Question was meant to get around those problems — does it? My understanding was that, whether there’s Robbins stability or not, and whether the quiver keeps changing or not, you still have a regular tree with (after setting all variables to 1) an m-tuple of integers at each vertex. If that’s right, then I think IQ2 makes sense even though there are no finite Markov processes in the picture. I only say it makes sense, by the way — not that it is natural!

  9. David Speyer says:

    Ah, I see. This make sense now. In the examples where the quiver does come back to itself and there is a conserved quantity, then the walk doesn’t equidistribute at all, but in the situations where there is no useful structure, I don’t know where to start.

  10. […] I have expressed amazement before about the Laurent phenomenon for cluster algebras, a theorem of Fomin and Zelevinsky which I learned about from Lauren Williams.  The paper “Birational Geometry of Cluster Algebras,”  just posted by Mark Gross, Paul Hacking, and Sean Keel, seems extremely interesting on this point.  They interpret the cluster transformations — which to an outsider look somewhat arbitrary — as elementary transforms (i.e. blow up a codim-2 thing and then blow down one of the exceptional loci thus created) on P^1-bundles on toric varieties.  And apparently the Laurent phenomenon is plainly visible from this point of view.  Very cool! […]

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 322 other followers

%d bloggers like this: