MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is motivated by my answer to 109955. It gives a recurrence relation satisfied by a function $P(n)$ whose terms a priori are rational functions (of three variables) with complicated denominators. However, by introducing further functions $R(n)$ and $S(n)$, we can get a joint recurrence from which it is obvious that $P(n)$ is a Laurent polynomial (the "Laurent phenomenon"). (Actually in 109955 the recurrence for $P(n)$ was derived from the joint recurrence, but this is irrelevant to my question.) I am wondering whether the same technique might apply to other Laurent phenomenon recurrences, or whether it can be proved in certain cases that such an approach cannot work. One of the simplest examples of this behavior is the Somos-4 recurrence $$ f(n)f(n+4) = f(n+1)f(n+3)+f(n+2)^2, $$ with generic initial conditions $f(0)=w$, $f(1)=x$, $f(2)=y$, $f(3)=z$. Can the Laurent phenomenon be proved by introducing additional functions as in 109955?

share|cite|improve this question
For easy navigation I added links towards the earlier postings; hope you do not mind. – user9072 Jan 5 '13 at 21:43
@quid: not at all. Thanks for doing this. – Richard Stanley Jan 5 '13 at 21:49
Here is an attempt to look on this problem from another side – Alexey Ustinov Apr 5 '15 at 10:21

I would like to see a good answer to this question! What I write below is a collection ideas that I think are relevant.

Cluster algebras provide one way to generate non-trivial instances of the Laurent phenomenon, yet there seem to be many different kinds of recurrence relations which exhibit such magic, some of them highly nonlinear, such as $$x_{n+3}x_n^3x_{n-1}=x_{n+2}^3x_{n-1}^3-x_{n+2}^2x_{n+1}^3x_{n-2}+a(x_{n+1}x_n)^6.$$ Much of what I'm saying here comes from an article by A. Hone, "Laurent Polynomials and Superintegrable Maps". One can view a recurrence relation $$x_{n+k}=F(x_n,\dots,x_{n+k-1}) \mathrel{\mathop :}= F(\mathbf{x}_n),$$ as an iteration of the map $$\varphi:(x_0,\dots,x_{k-1})\to (x_1,\dots,x_{k-1},F(\mathbf{x}_0)),$$ and therefore as a discrete dynamical system, say over $\mathbb R^k$ or $\mathbb C^k$. It turns out that a lot of the combinatorial properties of the recurrent sequence are in agreement with the behavior of $\varphi$ as a discrete dynamical system.

I interpret the method that you sketch in your question about "linearising" using joint recurrences as a sort of analog of "separation of variables". Being able to use separation of variables is one of the characterizing properties of what people call integrable systems. Therefore it makes sense to look for an answer among the recurrences which give rise to discrete integrable systems (I understand there is a large literature on these).

From this perspective, it becomes evident that linearising using joint recurrences should have something to do with having "conserved quantities", i.e. expressions in the terms of the sequence that remain constant as the index varies.

With this in mind, let us look at the example of the Somos-4 sequence $$x_{n+4}x_{n}=\alpha x_{n+3}x_{n+1}+\beta x_{n+2}^2.$$ I believe the reference here is an earlier paper, "Integrality and the Laurent phenomenon for Somos 4 sequences", by C. Swart and A. Hone. Where they use the fact that the corresponding discrete dynamical system is integrable to conclude the Laurent phenomenon.

The expression $$T=\frac{x_{n-1}x_{n+2}}{x_nx_{n+1}}+\frac{\alpha x_n^2}{x_{n-1}x_{n+1}}+\frac{x_{n-2}x_{n+1}}{x_{n-1}x_n},$$ turns out to be independent of $n$. Denoting $\mathcal{I}=\alpha^2+\beta T$, the authors prove that, in fact, we have $x_n\in \mathbb Z[\alpha, \beta, \mathcal{I}, x_1^{\pm}, x_2,x_3,x_4]$.

This is done by introducing the sequence $w_n$ satisfying $w_1=1, w_2=-\sqrt{\alpha},w_3=-\beta,w_4=\mathcal{I}\sqrt{\alpha}$, as well as $$w_{2m+1}=w_m^3w_{m+2}-w_{m+1}^3w_{m-1} \quad, \quad w_{2m+2}=\frac{w_{m+2}^2w_{m+1}w_{m-1}-w_{m}^2w_{m+1}w_{m+3}}{\sqrt{\alpha}}.$$ Now the desired property follows from examining the recurrences $$x _{2m+1}=\frac{w _m ^2x_mx _{m+2}-w _{m+1}w _{m-1}x _{m+1} ^2}{x _1}$$ and $$x _{2m+2}=\frac{w _{m+2}w _{m-1}x _{m+1}x _{m+2}-w _mw _{m+1}x _m x _{m+3}}{\sqrt{\alpha}x_1}.$$

This kind of auxiliary recurrences might have not been what you had in mind, but I thought it might be relevant, and perhaps attract some expert's opinion. It would be great if the connection between discrete integrable systems and the Laurent phenomenon was better understood, and we could treat such results systematically.

share|cite|improve this answer
Interesting ! By the way does the corresponding "integrable system" have a "spectral curve" ? Lax matrix ? Separated variables often have a simple interpretation in terms of spectral curve - you can associate to each point in phase space an effective divisor on a spectral curve D_1...D_n. Spectral curve is just a plane curve so its each point have coordinates (x,y) , so you have (x_{D_1} , y_{D_1)), (x_{D_2} , y_{D_2)), ... (x_{D_n} , y_{D_n)) - these guys are "separated variables". The problem is that it rarely possible to write down them explicitly... – Alexander Chervov Jan 8 '13 at 14:51

I have not had a chance to look at Richard Stanley's recurrence 109955 in detail, but it looks very nice; I will try to understand how it works next week. I just had a quick look at an orbit of some rational initial data: the heights of the rational numbers grow very fast - the log heights grow exponentially, which indicates non-integrability; that means it is unlikely that a closed form solution for the iterates can be found. I think the log heights grow like 2^n, but looks like an interesting version of the Laurent phenomenon as all rational iterates I saw had the same prime factors in the denominator.

The idea of auxiliary functions sounds reminiscent of the way that LP algebras are defined: The idea is that rather than having a single polynomial F defining an exchange relation

x_{old} x_{new} = F (other x_j),

one needs N of them in rank N - for a recurrence, N corresponds to the order, and we would have

x_{n+N} x_n = F(x_{n+1},...,x_{n+N-1}).

(The LP algebra setup is more general: not every LP algebra gives a simple recurrence - the same can be said for cluster algebras.) Auxiliary functions F_1,...,F_N (with certain properties) are exactly what is needed for Fomin & Zelevinsky's Caterpillar Lemma to hold - one can think of auxiliary functions as being needed for the caterpillar's legs, while for a recurrence the original F lives on the segments of the caterpillar's body - which gives the Laurent property. Cluster algebras are the special case when F is a sum of two monomials, and the functions F_j are not part of the definition because their role is played by (the columns of) an exchange matrix B, which specifies the exponents in each monomial.

About the example of Somos-4: this is a special case where there is an underlying integrable system. (In the general, only a small subset of the things that have the Laurent property are "integrable" in some sense.) For Somos-4, the spectral curve is an elliptic curve, and it is possible to write down explicit formulae for the iterates in terms of theta functions. Also, as Richard Eager mentions, this is a reduction of the octahedron recurrence (or discrete Hirota, or discrete KP equation, depending on your preference). In a recent paper with Allan Fordy we explain how to get the Lax pair and spectral curve for Somos-4, starting from discrete KP. We also identify integrable systems within a particular class of cluster algebras.

share|cite|improve this answer

Many recurrence relations such as the Somos-4 sequence can be embedded into the octahedron recurrence with some periodic identifications. It would be interesting to see if the simultaneous recursions in 109955 can also be embedded into the octahedron recurrence.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.