# Is this Laurent phenomenon explained by invariance/periodicity?

In Chapter 4 of his Tracking the Automatic Ant, David Gale discusses three families of recursively defined sequences of numbers, all due to Dana Scott and inspired by the Somos sequences:

Sequence 1. Fix a positive integer $$k\geq 2$$. Define a sequence $$\left( a_{0},a_{1},a_{2},\ldots \right)$$ of positive rational numbers recursively by setting \begin{align*} a_{n}=1\qquad \text{for each }n and \begin{align*} a_{n}=\dfrac{a_{n-1}^{2}+a_{n-2}^{2}+\cdots +a_{n-k+1}^{2}}{a_{n-k}}\qquad \text{for each }n\geq k. \end{align*}

Sequence 2. Fix an odd positive integer $$k\geq 2$$. Define a sequence $$\left( a_{0},a_{1},a_{2},\ldots \right)$$ of positive rational numbers recursively by setting \begin{align*} a_{n}=1\qquad \text{for each }n and \begin{align*} a_{n}=\dfrac{a_{n-1}a_{n-2}+a_{n-3}a_{n-4}+\cdots +a_{n-k+2}a_{n-k+1}}{ a_{n-k}}\qquad \text{for each }n\geq k. \end{align*}

Sequence 3. Fix a positive integer $$k\geq 2$$. Define a sequence $$\left( a_{0},a_{1},a_{2},\ldots \right)$$ of positive rational numbers recursively by setting \begin{align*} a_{n}=1\qquad \text{for each }n and \begin{align*} a_{n}=\dfrac{a_{n-1}a_{n-2}+a_{n-2}a_{n-3}+\cdots +a_{n-k+2}a_{n-k+1}}{ a_{n-k}}\qquad \text{for each }n\geq k. \end{align*}

Note the difference between Sequences 2 and 3: The numerator in Sequence 2 is $$\sum\limits_{i=1}^{\left(k-1\right)/2} a_{n-2i+1} a_{n-2i}$$, whereas the numerator in Sequence 3 is $$\sum\limits_{i=1}^{k-2} a_{n-i} a_{n-i-1}$$. Thus the requirement for $$k$$ to be odd in Sequence 2.

Now, Gale claims that all three sequences have the integrality property: i.e., all their entries $$a_{0},a_{1},a_{2},\ldots$$ are integers (for all possible values of $$k$$). More interesting is the way he claims to prove this: by constructing an auxiliary sequence that turns out to be constant or periodic with a small period.

Unfortunately, he only shows this for Sequence 1. Here, the auxiliary sequence is $$\left( b_{k},b_{k+1},b_{k+2},\ldots \right)$$, defined by setting \begin{align*} b_{n}=\dfrac{a_{n}+a_{n-k}}{a_{n-1}a_{n-2}\cdots a_{n-k+1}}\qquad \text{for each }n\geq k. \end{align*} By applying the recursion of Sequence 1 once to $$n$$ and once to $$n-1$$ and subtracting, it is not hard to see that $$b_{n}=b_{n-1}$$ for each $$n\geq k+1$$ . Thus, the sequence $$\left( b_{k},b_{k+1},b_{k+2},\ldots \right)$$ is constant, and therefore all its entries $$b_{n}$$ are integers (since $$b_{k}=k$$ is an integer). However, we can solve the equation $$b_{n}=\dfrac{ a_{n}+a_{n-k}}{a_{n-1}a_{n-2}\cdots a_{n-k+1}}$$ for $$a_{n}$$, obtaining $$a_{n}=b_{n}a_{n-1}a_{n-2}\cdots a_{n-k+1}-a_{n-k}$$, and this gives a new recursive equation for the sequence $$\left( a_{0},a_{1},a_{2},\ldots \right)$$. This new recursive equation no longer involves division, and thus a straightforward strong induction suffices to show that all $$a_{n}$$ are integers (since all $$b_{n}$$ as well as the first $$k$$ entries $$a_{0},a_{1},\ldots ,a_{k-1}$$ of Sequence 1 are integers). The details of this proof can be found in Gale's book or in the Notes on mathematical problem solving I am currently writing for Math 235 at Drexel (Exercise 8.1.8).

Gale claims that similar arguments work for Sequences 2 and 3. And indeed, this proof can be adapted to Sequence 2 rather easily, by redefining the auxiliary sequence to be a sequence $$\left( b_{k+1},b_{k+2},b_{k+3},\ldots \right)$$ (starting at $$b_{k+1}$$ this time) defined by \begin{align*} b_{n}=\dfrac{a_{n}+a_{n-k-1}}{a_{n-2}a_{n-3}\cdots a_{n-k+1}}\qquad \text{ for each }n\geq k+1. \end{align*}

I am, however, struggling with adapting this line of reasoning to Sequence 3. If $$k$$ is odd, then we can set \begin{align*} b_{n}=\dfrac{a_{n}+a_{n-k+1}}{a_{n-1}a_{n-3}\cdots a_{n-k+2}}\qquad \text{ for each }n\geq k-1 \end{align*} (where the denominator is $$\prod\limits_{i=1}^{\left( k-1\right) /2}a_{n-2i+1}$$). The resulting sequence $$\left( b_{k-1},b_{k},b_{k+1},\ldots \right)$$ is not constant, but it is periodic with period $$2$$ (that is, $$b_{n}=b_{n-2}$$ for each $$n\geq k+1$$); this is still sufficient for our argument. However, this only applies to the case when $$k$$ is odd. (I have found this definition of $$b_{n}$$ in Section 7.5 of Joshua Alman, Cesar Cuenca, Jiaoyang Huang, Laurent phenomenon sequences, J. Algebr. Comb. (2016) 43:589--633, which studies a more general recursion.)

When $$k$$ is even, I see no such proof. I assume that the integrality of $$a_{0},a_{1},a_{2},\ldots$$ follows from the standard Laurent phenomenon results known nowadays (by Fomin, Zelevinsky, Lam, Pylyavskyy and others). I haven't properly checked it, as there are a few technical conditions too many, but it is certainly consistent with SageMath experiments. Alman/Cuenca/Huang do not seem to consider the $$k$$-even case in their paper.

Question. Can we prove using the above tools that the entries $$a_{0},a_{1},a_{2},\ldots$$ of Sequence 3 are integers?

Yes, we can. The argument for odd $$k$$ made in the Alman/Cuenca/Huang paper was a red herring. We can argue for arbitrary $$k \geq 2$$ as follows:
Let $$n \geq k+2$$. Then, the recursive definition of Sequence 3 yields \begin{align*} a_{n}=\dfrac{a_{n-1}a_{n-2}+a_{n-2}a_{n-3}+\cdots +a_{n-k+2}a_{n-k+1}}{a_{n-k}} \end{align*} and thus \begin{align*} a_{n} a_{n-k} = a_{n-1}a_{n-2}+a_{n-2}a_{n-3}+\cdots +a_{n-k+2}a_{n-k+1} . \end{align*} The same reasoning (applied to $$n-2$$ instead of $$n$$) yields \begin{align*} a_{n-2} a_{n-k-2} = a_{n-3}a_{n-4}+a_{n-4}a_{n-5}+\cdots +a_{n-k}a_{n-k-1} . \end{align*} Subtracting this equality from the preceding equality, we obtain \begin{align*} a_{n} a_{n-k} - a_{n-2} a_{n-k-2} &= \left(a_{n-1}a_{n-2}+a_{n-2}a_{n-3}+\cdots +a_{n-k+2}a_{n-k+1} \right) \\ & \qquad - \left(a_{n-3}a_{n-4}+a_{n-4}a_{n-5}+\cdots +a_{n-k}a_{n-k-1} \right) \\ &= a_{n-1}a_{n-2}+a_{n-2}a_{n-3} - a_{n-k+1}a_{n-k} - a_{n-k}a_{n-k-1} . \end{align*} Let us add all the terms $$a_{n-2} a_{n-k-2}, a_{n-k+1}a_{n-k}, a_{n-k}a_{n-k-1}$$ to both sides of this equality, and throw in an $$a_{n-2} a_{n-k}$$ for good measure. Thus we obtain \begin{align*} &a_{n} a_{n-k} + a_{n-k+1}a_{n-k} + a_{n-k}a_{n-k-1} + a_{n-2} a_{n-k} \\ &= a_{n-1}a_{n-2}+a_{n-2}a_{n-3} + a_{n-2} a_{n-k-2} + a_{n-2} a_{n-k} . \end{align*} Both sides of this equality can be easily factored, so the equality rewrites as \begin{align*} &a_{n-k} \left(a_{n} + a_{n-2} + a_{n-k+1} + a_{n-k-1} \right) \\ &= a_{n-2} \left(a_{n-1} + a_{n-3} + a_{n-k} + a_{n-k-2} \right). \end{align*} Dividing this equality by $$a_{n-2} a_{n-3} \cdots a_{n-k}$$, we obtain \begin{align*} \dfrac{a_{n} + a_{n-2} + a_{n-k+1} + a_{n-k-1}}{a_{n-2}a_{n-3}\cdots a_{n-k+1}} &= \dfrac{a_{n-1} + a_{n-3} + a_{n-k} + a_{n-k-2}}{a_{n-3}a_{n-4}\cdots a_{n-k}} . \end{align*} In other words, $$b_n = b_{n-1}$$, where we define a sequence $$\left(b_{k+1}, b_{k+2}, b_{k+3}, \ldots\right)$$ of rational numbers by setting $$b_m = \dfrac{a_m + a_{m-2} + a_{m-k+1} + a_{m-k-1}}{a_{m-2}a_{m-3}\cdots a_{m-k+1}}$$ for each $$m \geq k+1$$. Thus, this sequence $$\left(b_{k+1}, b_{k+2}, b_{k+3}, \ldots\right)$$ is constant (since we have shown that $$b_n = b_{n-1}$$ for each $$n \geq k+2$$). Hence, all entries $$b_m$$ of this sequence are integers (since it is easily seen that $$b_{k+1}$$ is an integer).
Now, we can solve the equality $$b_m = \dfrac{a_m + a_{m-2} + a_{m-k+1} + a_{m-k-1}}{a_{m-2}a_{m-3}\cdots a_{m-k+1}}$$ for $$a_m$$, obtaining \begin{align*} a_m = b_m a_{m-2}a_{m-3}\cdots a_{m-k+1} - \left(a_{m-2} + a_{m-k+1} + a_{m-k-1}\right) \end{align*} for each $$m \geq k+1$$. This easily yields (by strong induction on $$m$$) that all of $$a_0, a_1, a_2, \ldots$$ are integers (after you check manually that $$a_0, a_1, \ldots, a_k$$ are integers).