Question

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?

Answer 1

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.

Answer 2

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.