Abstract

The Somos-5 sequence is defined by $a_{0} = a_{1} = a_{2} = a_{3} = a_{4} = 1$ and $a_{m} = \frac{a_{m-1} a_{m-4} + a_{m-2} a_{m-3}}{a_{m-5}}$ for $m \geq 5$. We relate the arithmetic of the Somos-5 sequence to the elliptic curve $E : y^{2} + xy = x^{3} + x^{2} - 2x$ and use properties of Galois representations attached to $E$ to prove the density of primes $p$ dividing some term in the Somos-5 sequence is equal to $\frac{5087}{10752}$.

1. Introduction and statement of results

There are many results in number theory that relate to a determination of the primes dividing some particular sequence. For example, it is well known that if $p$ is a prime number, then $p$ divides some term of the Fibonacci sequence, defined by $F_{0} = 0$, $F_{1} = 1$, and $F_{n} = F_{n-1} + F_{n-2}$ for $n \geq 2$. Students in elementary number theory learn that a prime $p$ divides a number of the form $n^{2} + 1$ if and only if $p = 2$ or $p \equiv 1 \pmod {4}$.

In 1966, Hasse proved in 4 that if $\pi _{{\mathrm{even}}}(x)$ is the number of primes $p \leq x$ so that $p | 2^{n} + 1$ for some $n$, then

$$\begin{equation*} \lim _{x \to \infty } \frac{\pi _{{\mathrm{even}}}(x)}{\pi (x)} = \frac{17}{24}. \end{equation*}$$

Note that a prime number $p$ divides $2^{n} + 1$ if and only if $2$ has even order in $\mathbb{F}_{p}^{\times }$.

A related result is the following. The Lucas numbers are defined by $L_{0} = 2$, $L_{1} = 1$ and $L_{n} = L_{n-1} + L_{n-2}$ for $n \geq 2$. In 1985, Lagarias proved (see 9 and 10) that the density of primes dividing some Lucas number is $2/3$. Given a prime number $p$, let $Z(p)$ be the smallest integer $m$ so that $p | F_{m}$. A prime $p$ divides $L_{n}$ for some $n$ if and only if $Z(p)$ is even. In 2, Paul Cubre and the third author prove a conjecture of Bruckman and Anderson on the density of primes $p$ for which $m | Z(p)$, for an arbitrary positive integer $m$.

In the early 1980s, Michael Somos discovered integer-valued non-linear recurrence sequences. The Somos-$k$ sequence is defined by $c_{0} = c_{1} = \cdots = c_{k-1} = 1$ and

$$\begin{equation*} c_{m} = \frac{c_{m-1} c_{m-(k-1)} + c_{m-2} c_{m-(k-2)} + \cdots + c_{m-\lfloor \frac{k}{2} \rfloor } c_{m-\lceil \frac{k}{2} \rceil }}{c_{m-k}} \end{equation*}$$

for $m \geq k$. Despite the fact that division is involved in the definition of the Somos sequences, the values $c_{m}$ are integral for $4 \leq k \leq 7$. Fomin and Zelevinsky 3 show that the introduction of parameters into the recurrence results in the $c_{m}$ being Laurent polynomials in those parameters. Also, Speyer 15 gave a combinatorial interpretation of the Somos sequences in terms of the number of perfect matchings in a family of graphs.

Somos-4 and Somos-5 type sequences are also connected with the arithmetic of elliptic curves (a connection made quite explicit by A. N. W. Hone in 5, and 6). If $a_{n}$ is the $n$th term in the Somos-4 sequence, $E : y^{2} + y = x^{3} - x$ and $P = (0,0) \in E(\mathbb{Q})$, then the denominator of the $x$-coordinate of $(2n-3)P$ is equal to $a_{n}^{2}$. It follows from this that $p | a_{n}$ if and only if $(2n-3)P$ reduces to the identity in $E(\mathbb{F}_{p})$, and so a prime $p$ divides a term in the Somos-4 sequence if and only if $(0,0) \in E(\mathbb{F}_{p})$ has odd order. In 8, Rafe Jones and the third author prove that the density of primes dividing some term of the Somos-4 sequence is $\frac{11}{21}$. The goal of the present paper is to prove an analogous result for the Somos-5 sequence.

Let $\pi '(x)$ denote the number of primes $p \leq x$ so that $p$ divides some term in the Somos-5 sequence. We have the following table of data:

$x$	$\pi '(x)$	$\frac{\pi '(x)}{\pi (x)}$
$10$	$3$	$0.750000$
$10^{2}$	$12$	$0.480000$
$10^{3}$	$83$	$0.494048$
$10^{4}$	$588$	$0.478438$
$10^{5}$	$4539$	$0.473207$
$10^{6}$	$37075$	$0.472305$
$10^{7}$	$314485$	$0.473209$
$10^{8}$	$2725670$	$0.473087$
$10^{9}$	$24057711$	$0.473134$
$10^{10}$	$215298607$	$0.473129$
$10^{11}$	$1948329818$	$0.473119$

Our main result is the following.

Theorem 1.

We have

$$\begin{equation*} \lim _{x \to \infty } \frac{\pi '(x)}{\pi (x)} = \frac{5087}{10752} \approx 0.473121. \end{equation*}$$

The Somos-5 sequence is related to the coordinates of rational points on the elliptic curve $E : y^{2} + xy = x^{3} + x^{2} - 2x$. This curve has $E(\mathbb{Q}) \cong \mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}$ and generators are $P = (2,2)$ (of infinite order) and $Q = (0,0)$ (of order $2$). We have (see Lemma 3) that

$$\begin{equation*} mP + Q = \left(\frac{a_{m+2}^{2} - a_{m} a_{m+4}}{a_{m+2}^{2}}, \frac{4 a_{m} a_{m+2} a_{m+4} - a_{m}^{2} a_{m+6} - a_{m+2}^{3}}{a_{m+2}^{3}}\right). \end{equation*}$$

It follows that a prime $p$ divides a term in the Somos-5 sequence if and only if the reduction of $Q$ modulo $p$ is in $\langle P \rangle \subseteq E(\mathbb{F}_{p})$. Another way of stating this is the following: there is a $2$-isogeny $\phi : E \to E'$, where $E' : y^{2} + xy = x^{3} + x^{2} + 8x + 10$ and

$$\begin{equation*} \phi (x,y) = \left(\frac{x^{2} - 2}{x}, \frac{x^{2} y + 2x + 2y}{x^{2}}\right). \end{equation*}$$

The kernel of $\phi$ is $\{ 0, Q \}$. Letting $R = \phi (P)$ we show (see Theorem 4) that a prime $p$ of good reduction divides some term in the Somos-5 sequence if and only if the order of $P$ in $E(\mathbb{F}_{p})$ is twice that of $R$ in $E'(\mathbb{F}_{p})$.

A result of Pink (see Proposition 3.2 on page 284 of 11) shows that the $\ell$-adic valuation of the order of a point $P \pmod {p}$ can be determined from a suitable Galois representation attached to an elliptic curve. For a positive integer $k$, we let $K_{k}$ be the field obtained by adjoining to $\mathbb{Q}$ the $x$ and $y$ coordinates of all points $\beta _{k}$ with $2^{k} \beta _{k} = P$. There is a Galois representation $\rho _{E,2^{k}} : {\mathrm{Gal}}(K_{k}/\mathbb{Q}) \to {\mathrm{AGL}}_{2}(\mathbb{Z}/2^{k} \mathbb{Z})$ and we relate the power of $2$ dividing the order of $P$ in $E(\mathbb{F}_{p})$ to $\rho _{E,2^{k}}(\sigma _{p})$, where $\sigma _{p}$ is a Frobenius automorphism at $p$ in ${\mathrm{Gal}}(K_{k}/\mathbb{Q})$. Using the isogeny $\phi$ we are able to relate $\rho _{E,2^{k}}(\sigma _{p})$ and $\rho _{E',2^{k-1}}(\sigma _{p})$, obtaining a criterion that indicates when $p$ divides some term in the Somos-5 sequence. We then determine the image of $\rho _{E,2^{k}}$ for all $k$.

Once the image of $\rho _{E,2^{k}}$ is known, the problem of computing the fraction of elements in the image with the desired properties is quite a difficult one. We introduce a new and simple method for computing this fraction and apply it to prove Theorem 1.

2. Background

If $E/F$ is an elliptic curve given in the form $y^{2} + a_{1} xy + a_{3} y = x^{3} + a_{2} x^{2} + a_{4} x + a_{6}$, the set $E(F)$ has the structure of an abelian group. Specifically, if $P, Q \in E(F)$, let $R = (x,y)$ be the third point of intersection between $E$ and the line through $P$ and $Q$. We define $P+Q = (x,-y-a_{1} x - a_{3})$. The multiplication by $m$ map on an elliptic curve has degree $m^{2}$, and so if $E/\mathbb{C}$ is an elliptic curve and $\alpha \in E(\mathbb{C})$, then there are $m^{2}$ points $\beta$ so that $m \beta = \alpha$.

If $K/\mathbb{Q}$ is a finite extension, let $\mathcal{O}_K$ denote the ring of algebraic integers in $K$. A prime $p$ ramifies in $K$ if $p\mathcal{O}_K = \prod _{i=1}^{r} \mathfrak{p}_i^{e_i}$ and some $e_i > 1$, where the $\mathfrak{p}_i$ are distinct prime ideals of $\mathcal{O}_K$.

Suppose $K/\mathbb{Q}$ is Galois, $p$ is a prime number that does not ramify in $K$, and $p\mathcal{O}_K = \prod _{i=1}^{g} \mathfrak{p}_i$. For each $i$, there is a unique element $\sigma \in {\mathrm{Gal}}(K/\mathbb{Q})$ for which

$$\begin{equation*} \sigma (\alpha ) \equiv \alpha ^{p} \pmod {\mathfrak{p}_{i}} \end{equation*}$$

for all $\alpha \in \mathcal{O}_{K}$. This element is called the Artin symbol of $\mathfrak{p}_{i}$ and is denoted $\genfrac {[}{]}{}{}{K/\mathbb{Q}}{\mathfrak{p}_{i}}$. If $i \neq j$, $\left[ \frac{K/\mathbb{Q}}{\mathfrak{p}_i} \right]$ and $\left[ \frac{K/\mathbb{Q}}{\mathfrak{p}_j} \right]$ are conjugate in ${\mathrm{Gal}}(K/\mathbb{Q})$ and $\genfrac {[}{]}{}{}{K/\mathbb{Q}}{p} := \left\{ \left[ \frac{K/\mathbb{Q}}{\mathfrak{p}_i} \right] : 1 \leq i \leq g \right\}$ is a conjugacy class in ${\mathrm{Gal}}(K/\mathbb{Q})$.

The key tool we will use in the proof of Theorem 1 is the Chebotarev density theorem.

Theorem 2 (7, page 143).

If $C \subseteq {\mathrm{Gal}}(K/\mathbb{Q})$ is a conjugacy class, then

$$\begin{equation*} \lim _{x \to \infty } \frac{\# \{ p \leq x : p \text{ prime}, \genfrac {[}{]}{}{}{K/\mathbb{Q}}{p} = C \}}{\pi (x)} = \frac{|C|}{|{\mathrm{Gal}}(K/\mathbb{Q})|}. \end{equation*}$$

Roughly speaking, each element of ${\mathrm{Gal}}(K/\mathbb{Q})$ arises as $\left[ \frac{K/\mathbb{Q}}{\mathfrak{p}} \right]$ equally often.

Let $E[m] = \{ P \in E : mP = 0 \}$ be the set of points of order dividing $m$ on $E$. Then $\mathbb{Q}(E[m])/\mathbb{Q}$ is Galois and ${\mathrm{Gal}}(\mathbb{Q}(E[m])/\mathbb{Q})$ is isomorphic to a subgroup of ${\mathrm{Aut}}(E[m]) \cong {\mathrm{GL}}_{2}(\mathbb{Z}/m\mathbb{Z})$. Moreover, Proposition V.2.3 of 13 implies that if $\sigma _p$ is a Frobenius automorphism at some prime above $p$ and $\tau : {\mathrm{Gal}}(\mathbb{Q}(E[m])/\mathbb{Q}) \rightarrow {\mathrm{GL}}_{2}(\mathbb{Z}/m \mathbb{Z})$ is the usual mod $m$ Galois representation, then ${\mathrm{tr}}\nobreakspace \tau (\sigma _{p}) \equiv p+1 - \# E(\mathbb{F}_{p}) \pmod {m}$ and $\det (\tau (\sigma _{p})) \equiv p \pmod {m}$. Another useful fact is the following. If $K/\mathbb{Q}$ is a number field, $\mathfrak{p}$ is a prime ideal in $\mathcal{O}_{K}$ above $p$, $\gcd (m,p) = 1$ and $P \in E(K)[m]$ is not the identity, then $P$ does not reduce to the identity in $E(\mathcal{O}_{K}/\mathfrak{p})$. This is a consequence of Proposition VII.3.1 of 13.

We will construct Galois representations attached to elliptic curves with images in ${\mathrm{AGL}}_{2}(\mathbb{Z}/2^{k} \mathbb{Z}) \cong (\mathbb{Z}/2^{k} \mathbb{Z})^{2} \rtimes {\mathrm{GL}}_{2}(\mathbb{Z}/2^{k} \mathbb{Z})$. Elements of such a group can be thought of either as pairs $(\vec{v}, M)$, where $\vec{v}$ is a row vector, and $M \in {\mathrm{GL}}_{2}(\mathbb{Z}/2^{k} \mathbb{Z})$, or as $3 \times 3$ matrices $\begin{bmatrix} a & b & 0 \\ c & d & 0 \\ e & f & 1 \end{bmatrix}$, where $\vec{v} = \begin{bmatrix} e & f \end{bmatrix}$ and $M = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$. In the former notation, the group operation is given by

$$\begin{equation*} (\vec{v}_1, M_1)*(\vec{v}_2, M_2) = (\vec{v}_1 + \vec{v}_2M_1, M_2M_1). \end{equation*}$$

3. Connection between the Somos-5 sequence and $E$

Lemma 3.

Define $P = (2,2)$ and $Q = (0,0)$ on $E : y^{2} + xy = x^{3} + x^2 - 2x$. For all $m \geq 0$, we have the following relationship between the Somos-5 sequence and $E$:

$$\begin{align*} mP + Q = \left(\frac{a_{m+2}^2 - a_{m}a_{m+4}}{a_{m+2}^2} , \frac{4a_{m}a_{m+2}a_{m+4} - a_{m}^2 a_{m+6} - a_{m+2}^3}{a_{m+2}^3}\right). \end{align*}$$

Proof.

We will prove this by strong induction. A straightforward calculation shows that the base cases $m = 0$ and $m = 1$ are true. For simplicity’s sake, we will denote $a = a_{m}$, $b = a_{m+1}$, $c = a_{m+2}$, $d = a_{m+3}$, $e = a_{m+4}$, $f = a_{m+5}$, $g = a_{m+6}$, and $i = a_{m+8}$. Our inductive hypothesis is that

$$\begin{align*} mP + Q = \left(\frac{c^2 - ae}{c^2} , \frac{4ace - a^2g - c^3}{c^3}\right). \end{align*}$$

We will now compute $(m+2)P + Q$.

To find the $x$ and $y$ coordinates of $(m+2)P + Q$, we add $2P = (1,-1)$ to $mP+Q$. If $w$ is the slope and $v$ is the $y$-intercept, the line between $2P$ and $mP + Q$ is $y = wx + v$ with $w = \frac{ag - 4ce}{ce}$ and $v = \frac{-ag + 3ce}{ce}$. Substituting this into the equation for $E$, we find the $x$-coordinate of $2P + (mP + Q)$ to be $r_x = \frac{a^2g^2 - 7aceg + ae^3 + 9c^2e^2}{c^2e^2}$. A straightforward but lengthy inductive calculation shows that if

$$\begin{align*} F(a,c,e,g) = a^2g^2 - 7aceg + ae^3 + c^3g + 8c^2e^2, \end{align*}$$

then $F(a_n, a_{n+2}, a_{n+4}, a_{n+6}) = 0$ for all $n$. Also, $ai = cg + 8e^{2}$ holds (by Proposition 2.8 in Hone’s paper 6). Since $F(a,c,e,g)=0$, we know that $r_x - \frac{F(a,c,e,g)}{c^{2} e^{2}} = r_x$. Therefore, we know that $r_x = \frac{-cg + e^2}{e^2}$.

Denote the $y$-coordinate of $(m+2)P + Q$ as $r_y$. We compute that $r_y = \frac{g(ag - 3ce)}{e^3}$. Using that $r_{y} = r_{y} - \frac{F(a,c,e,g)}{ae^{3}}$, we find that $r_y = \frac{4ceg - c^2i - e^3}{e^3}$. Therefore, it is evident that

$$(m+2)P + Q = \left(\frac{a_{m+4}^2 - a_{m+2}a_{m+6}}{a_{m+4}^2}, \frac{4a_{m+2}a_{m+4}a_{m+6} - a_{m+2}^2a_{m+8} -a_{m+4}^3}{a_{m+4}^3}\right).$$ ■

Let $E'$ be given by $E' : y^2 + xy = x^3 + x^2 + 8x + 10$ and let $R = (1,4) \in E'(\mathbb{Q})$. We have a $2$-isogeny $\phi : E \to E'$ given by

$$\begin{equation*} \phi (x,y) = \left(\frac{x^{2} - 2}{x}, \frac{x^{2} y + 2x + 2y}{x^{2}}\right). \end{equation*}$$

The elliptic curves $E$ and $E'$ each have conductor $102 = 2 \cdot 3 \cdot 17$. The next result classifies the primes of good reduction that divide a term in the Somos-5 sequence.

Theorem 4.

If $p$ is a prime of good reduction that divides a term in the Somos-5 sequence, the order of $P = (2,2)$ in $E(\mathbb{F}_p)$ is twice the order of $R=(1,4)$ in $E'(\mathbb{F}_p)$. Otherwise, their orders are the same.

Proof.

If $p$ divides a term in our sequence, say $a_m$, we know from our previous lemma that the denominators $(m-2)P + Q$ are divisible by $p$. Therefore, modulo $p$, $(m-2)P + Q = 0$. The point $Q$ has order 2, so adding $Q$ to both sides we know that $(m-2)P = Q$. Therefore, we can deduce that $Q \in \langle P \rangle$. We have $\text{ker}(\phi ) = \{Q, 0 \}$ (see Section 3.4 of 14). Therefore, if $\phi$ is restricted to the subgroup generated by $P$, we have $|\text{ker}(\phi )| = 2$. Since