A Somos Sequence

by David Radcliffe

Somos sequences are sequences that are defined by certain nonlinear recurrence relations. The Somos-k sequence obeys the recurrence relation

a_n a_{n-k} = \sum\limits_{i=1}^{\lfloor k/2 \rfloor} a_{n-i} a_{n-k+1}

with initial values a_n = 1 for 0 \le n \le k-1\ .

The first interesting case is k = 4:

a_n a_{n-4} = a_{n-1} a_{n-3} + (a_{n-2})^2

The first 15 terms of the Somos-4 sequence (A006720) are

1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898.

It is easy to prove by induction that a_n is always a positive rational number. It is not at all obvious that a_n is always an integer, but this is true as well. I will present a proof due to Janice Malouf and George Bergman.

Step 1: Four consecutive terms are coprime.

We first show that any four consecutive terms are pairwise coprime. The proof is by induction. It is obvious that the first four terms are pairwise coprime. Assume that a_{n-4}, a_{n-3}, a_{n-2}, a_{n-1} are pairwise coprime for some n, and let p be a a prime divisor of (the numerator of) a_n. Then p divides a_n a_{n-4}, so p also divides a_{n-1} a_{n-3} + (a_{n-2})^2. From this we conclude that

p\ |\ a_{n-2} \iff (p\ |\ a_{n-1})\ or \ (p\ |\ a_{n-3})\ .

But p cannot divide two of the terms (a_{n-3}, a_{n-2}, a_{n-1}), because we assumed that they are coprime. Therefore, p divides none of them; so (a_{n-3}, a_{n-2}, a_{n-1}, a_n) are coprime. This completes the induction step.

Step 2: Modular madness!

Direct calculation shows that (at least) the first eight terms are integers. Consider nine consecutive terms

a, b, c, d, e, f, g, h, i

and suppose that the first eight terms are integers. We will show that i is also an integer.

The recurrence yields the following equations.

ae = bd + c^2

bf = ce + d^2

cg = df + e^2

dh = eg + f^2

ei = fh + g^2

Reducing the equations modulo e yields the following equations. (The divisions are allowed because b, c, d, and e are coprime.)

bd + c^2 \equiv 0

f \equiv \dfrac{d^2}{b}

g \equiv \dfrac{df}{c} \equiv \dfrac{d^3}{bc}

h \equiv \dfrac{f^2}{d} \equiv \dfrac{d^4}{b^2d} \equiv \dfrac{d^3}{b^2}

ei \equiv \dfrac{d^5}{b^3} + \dfrac{d^6}{b^2c^2}

Step 3: A lucky factorization.

Observe that we can write the final equation as

ei \equiv \dfrac{d^5}{b^3 c^2} (c^2 + bd).

But c^2 + bd \equiv 0, so ei \equiv 0 \pmod{e}.

This implies that i is an integer.