A question on the Laurent phenomenon 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?
 A: 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: https://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+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 https://arxiv.org/abs/1207.6072 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.
A: 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.
A: 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.
A: In another answer, Gjergji Zaimi gave duplication formulas for a
generalized Somos-4 sequence $\,x(n)\,$ using its associated elliptic divisibility sequence $\,w(n).\,$
Actually, you can do it with a single sequence alone.
Let $\,a(n)\,$ be the Somos-4 sequence
which satisfies
$$ a(n)a(n-4) = a(n-1)a(n-3)+a(n-2)^2, \quad a(0)=\cdots=a(3)=1. $$
Then some possible duplication formulas are
$$ a(2n\!+\!1) = -\,a(n)^2a(n\!+\!1)a(n\!+\!4) + a(n)^2a(n\!+\!2)a(n\!+\!3)
 +2a(n\!+\!1)^3a(n\!+\!2),\\
a(2n\!+\!2) = -\,a(n)^2a(n\!+\!3)a(n\!+\!4) -2a(n\!+\!1)^3a(n\!+\!4)
 +7a(n\!+\!1)^2a(n\!+\!2)a(n\!+\!3). $$
However, there are two formulas depending on even or odd.
A similar and simpler yet more interesting example than the
$\,P(n),R(n),S(n)\,$ is the following. Let
$$ x(n+1) = +y(n)^2 - x(n)z(n), \quad x(0) = 2, \\
  y(n+1) = -x(n)^2 - y(n)z(n), \quad y(0) = 1, \\
 z(n+1) = -z(n)^2 - x(n)y(n), \quad z(0) = 1. $$
The sequence of triples $\,(x(n),y(n),z(n))\,$ are all points
on the elliptic curve
$$ x^3 + y^3 - 3z^3 = 3xyz. $$
This is closely related to an answer of mine to
MSE question 4298049
which has another example of such a recurrence and its relation to
general Somos-4 sequences.
Each of the three sequences satisfy recurrences which allow to
calculate each sequence term from the four preceding terms. For example,
(where $z0:=z(n), \dots, z4:=z(n+4)$)
$$ 0 = -(63 z1 + 98 z0^2) z4 + 26 z3^2 z1 + 372 z3 z2^2 z1 + 78 z3^2 z0^2. $$
Notice the relatively large coefficients which depend only on the invariant
$\,(x(n)^3+y(n)^3)/(z(n)^3+x(n)y(n)z(n)).\,$ There should be similar but more complicated formulas
for the other two sequences but I am unable to find them currently.
The sequences grow quickly, but there are common factors which can reduce
the growth rate. For
example, if the seed values $\,x(0),y(0),z(0)\,$ are variables, then
the total degree of $\,x(n),y(n),z(n)\,$ in these variables is $\,2^n.\,$
However, if common factors are removed, then the total degree is the
sequence A084684 with quadratic
growth rate rather than exponential.
A: This is a simpler example than my previous answer.
Define two integer sequences with initial values $\;u_1 = -2,\;
v_1 = 1\;$ and joint recursions
$$ u_{n+1} = - u_n^2 + 3u_nv_n - v_n^2, \qquad
   v_{n+1} = - u_n^2 + 4u_nv_n - v_n^2. $$
The first few terms for $\;u\;$ are $\;u_2 = 11,\; u_3 = -139\;$
and for $\;v\;$ are $\;v_2 = 13,\; v_3 = -282.\;$
Then for any four consecutive terms $\;(u_1,\;u_2,\;u_3,\;u_4)\;$
of the $\;u\;$ sequence the following equations
$$ 0 = u_1^8 - u_1^6u2 - 8u_1^4u_2^2 + 6u_1^2u_2^3 + u_2^4 + 7u_1^4u_3
-5u_1^2u_2u_3 - 2u_2^2u_3 + u_3^2,\\
   0 = 3u_1^4u_2^3 - u_1^4u_2u_3 + 9u_1^2u_2^4 - 7u_1^2u_2^2u_3 - 3u_1^2u_3^2
+3u_1^2u_4 + u_2^5 - 2u_2^3u_3 + 2u_2u_2^2 - u_2u_4 $$
are true. Similar results hold for the $\;v\;$ sequence.
The second equation is linear in $\;u_4\;$ and thus there is a rational
recursion for $\;u\;$ by itself of the form
$$ u_{n+3} = f(u_n, u_{n+1}, u_{n+2}) \qquad
 \text{ for all }\qquad n>0. $$
The Laurent phenomenon here is that the denominator of
$\;u_{n+4}\;$ is $\;(3u_1^2-u_2)^{2^n}\;$ which is $\;1\;$ for
the example given.
