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 Somos4 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?

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 nontrivial 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_{n1}=x_{n+2}^3x_{n1}^3x_{n+2}^2x_{n+1}^3x_{n2}+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+k1}) \mathrel{\mathop :}= F(\mathbf{x}_n),$$ as an iteration of the map $$\varphi:(x_0,\dots,x_{k1})\to (x_1,\dots,x_{k1},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 Somos4 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_{n1}x_{n+2}}{x_nx_{n+1}}+\frac{\alpha x_n^2}{x_{n1}x_{n+1}}+\frac{x_{n2}x_{n+1}}{x_{n1}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_{m1} \quad, \quad w_{2m+2}=\frac{w_{m+2}^2w_{m+1}w_{m1}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 _{m1}x _{m+1} ^2}{x _1}$$ and $$x _{2m+2}=\frac{w _{m+2}w _{m1}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. 


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 nonintegrability; 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: http://arxiv.org/abs/1206.2611 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+N1}). (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 Somos4: 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 Somos4, 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 http://arxiv.org/abs/1207.6072 with Allan Fordy we explain how to get the Lax pair and spectral curve for Somos4, starting from discrete KP. We also identify integrable systems within a particular class of cluster algebras. 


Many recurrence relations such as the Somos4 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. 

