# Integer but not Laurent sequences

Are there any sequence given by a recurrence relation: $$x_{n+t}=P(x_t,\cdots,x_{t+n-1})$$, where $$P$$ is a positive Laurent Polynomial, satisfy:

• if $$x_0=\cdots=x_{n-1}=1$$, then the sequence is only integer;

• but does not exhibit Laurent Phenomenon ?

What if we allow $$P$$ to be a rational function?

• Great question! I assume you want $P$ to have positive coefficients, since otherwise $x_n = \dfrac{x_{n-1} + x_{n-2} - x_{n-3}}{x_{n-4}}$ is a counterexample (indeed, the general formula for $x_8$ is not a Laurent polynomial, but if $x_0 = x_1 = x_2 = x_3 = 1$, then all values $x_i$ equal $1$). – darij grinberg Feb 22 at 20:07
• @darij grinberg, thanks, I forgot the positivity – Wenze 'Sylvester' Zhang Feb 22 at 20:26

Consider $$x_{n+3} = \frac{x_n+x_{n+1}}{x_{n+2}}$$.
With $$x_1=x_2=x_3 =1$$ this gives the sequence $$1,1,1,2,1,3,1,4,1,5,...$$ but it certainly is not Laurent because for instance we have $$x_5=\frac{x_2x_3+x_3^2}{x_1+x_2}$$.
• Uhm, I wouldn't allow a $2$ in the denominator for a Laurent polynomial -- we're talking integers, right? – darij grinberg Feb 22 at 20:35
This reminds me of a question I had seen on both MO and MSE. Sequence A276175 in the OEIS is defined by $$a_n = \frac{(a_{n-1} + 1)(a_{n-2}+1)(a_{n-3} + 1)}{a_{n-4}}$$ with $$a_0 = a_1 = a_2 = a_3 = 1$$. The OEIS page conjectures it to be an integer for all $$n$$. The MSE question contains a proof the all $$a_n$$ are integer (though I haven't read the proof). In the comments of the MO question it is observed $$a_8$$ is not Laurent.
Added in edit: I offer another example which does not exhibit the Laurent phenomenon, but conjecturally is an integer sequence. Consider the sequence defined by $$b_n = \frac{(b_{n-1} + 1)(b_{n-2} + 1)(b_{n-3} + 1)(b_{n-4}+1)}{b_{n-5}}$$ where $$b_0 = b_1 = b_2 = b_3 = b_4 = 1$$. I computed and after reducing I found the denominator of $$b_{10}$$ to be $$b_0^14(b_1 + 1)b_1^8(b_2 + 1)b_2^4b_3^2b_4$$ (not a monomial). I verified this sequence to be integer up to $$n=36$$, and Kevin O'Bryant later verified up to $$n=41$$. I asked if the sequence is integer for all $$n \geq 0$$ in a separate question.