Divisibility Sequences and

Powers of Algebraic Integers

Joseph H. Silverman

Received: November 15, 2005

Abstract. Let α be an algebraic integer and define a sequence of rational integers d_{n}(α) by the condition

d_{n}(α) = max{d ∈ ℤ : α^{n} ≡ 1 (mod d)}.

We show that d_{n}(α) is a strong divisibility sequence and that it satisfies log d_{n}(α) = o(n) provided that no power of α is in ℤ and no power of α is a unit in a quadratic field. We completely analyze some of the exceptional cases by showing that d_{n}(α) splits into subsequences satisfying second order linear recurrences. Finally, we provide numerical evidence for the conjecture that aside from the exceptional cases, d_{n}(α) = d_{1}(α) for infinitely many n, and we ask whether the set of such n has postive (lower) density.

2000 Mathematics Subject Classification: Primary: 11R04; Secondary: 11A05, 11D61 Keywords and Phrases: divisibility sequence, multiplicative group

Introduction

A sequence of positive integers {d_{n}} is called a divisibility sequence if it has the property

(1)  m|n ⟹ d_{m}|d_{n}.

Well-known examples of divisibility sequences include sequences of the form d_{n} = a^{n} − 1, the Fibonacci sequence F_{n}, and elliptic divisibility sequences D_{n}. The first two also satisfy a linear recurrence. A complete characterization of linear recurrence divisibility sequences is given in [2]. Elliptic divisibility sequences are associated to points of infinite order on elliptic curves. Thus if P ∈ E(ℚ), then the sequence D_{n} is formed by writing x(nP) = A_{n}/D_{n}^{2}, see [9].

In this paper we investigate divisibility sequences (d_{n}(α))_{n≥1} associated to algebraic integers α ∈ ℤ̄ by the rule

(2)  d_{n}(α) = max{d ∈ ℤ : α^{n} ≡ 1 (mod d)}.

(We assume throughout that α ≠ 0 and that α is not a root of unity.) It is not difficult to show that d_{n}(α) is a divisibility sequence, and indeed that it satisfies the stronger divisibility property

gcd(d_{m}(α), d_{n}(α)) = d_{gcd(m,n)}(α),

see Proposition 2.

These sequences are interesting in their own right as generalizations of the classical divisibility sequences a^{n} − 1 with a ∈ ℤ. They are also interesting as a special case of divisibility sequences attached to points of infinite order on algebraic groups (see [8, Section 6]) for which we can prove unconditional results.

We now briefly summarize the contents of this paper. We begin in Section 1 with the proof that d_{n}(α) is a strong divisibility sequence. Section 2 contains a variety of numerical examples illustrating varied behaviors of d_{n}(α) for different choices of α. In Section 3 we prove a useful result on linear dependence of Galois conjugates, and in Section 4 we combine this with a deep result of Corvaja and Zannier [5] to prove:

Theorem 1. Let α ∈ ℤ̄ and let d_{n}(α) be the associated divisibility sequence (2). Then

lim_{n→∞} \frac{log d_{n}(α)}{n} = 0

unless either some power of α is in ℤ or some power of α is a unit in a quadratic extension of ℚ.

The theorem says that aside from a few specific cases, the sequences d_{n}(α) grow slower than exponentially. One of the exceptional cases is easy to analyze. If α^{r} ∈ ℤ with |α^{r}| ≥ 2 and if no smaller power of α is in ℤ, then one easily checks that

d_{n}(α) = \begin{cases}|α^{n} − 1| & if r|n, \\ 1 & if r ∤ n. \end{cases}

In particular, d_{n}(α) contains a subsequence that grows exponentially.

In Section 5 we analyze the other exceptional case and give a complete description of d_{n}(α) for real quadratic units α = u + v\sqrt{D}. If the norm of α is 1, we prove that d_{n}(α) satisfies a fourth order linear recurrence. More precisely, we show that the subsequences d_{2n}(α) and d_{2n+1}(α) both satisfy the same second order linear recurrence, but with different starting values. If the norm of α is −1, then we prove that d_{n}(α) = 1 for all of the odd values of n. The subsequence of even terms d_{2n}(α) = d_{n}(α^{2}) satisfies a fourth order linear recurrence, since α^{2} has norm 1. The proofs of these statements involve elementary, but rather intricate, calculations.

Finally, in Section 6 we observe that except in the two exceptional cases, the sequences d_{n}(α) appear to include many small values. Theorem 1 says that log d_{n}(α) = o(n), and d_{n}(α) does contain arbitrarily large values, but experimentally one finds for example that d_{n}(α) is frequently equal to d_{1}(α). We present one such experiment in Section 6 and use it to conjecture that the set

{n ≥ 1 : d_{n}(α) = d_{1}(α)}

is infinite (generalizing a conjecture of Ailon and Rudnick [1]) and to ask whether this set in fact has positive (lower) density.

Acknowledgements. The author thanks Mike Rosen for his assistance in simplifying the proof of Proposition 3.

1. Divisibility sequences associated to algebraic integers

We begin by reminding the reader of some classical definitions.

Definition 1. A divisibility sequence is a sequence of of positive integers (d_{n})_{n≥1} with the property that

(3)  m|n ⟹ d_{m}|d_{n}.

The sequence is normalized if d_{1} = (1), which can always be arranged by replacing d_{n} by d_{n}/d_{1}. A strong divisibility sequence satisfies the more stringent requirement that

(4)  d_{gcd(m,n)} = gcd(d_{n}, d_{m})  for all m, n ∈ ℕ.

Examples of strong divisibility sequences include the Fibonacci sequence and elliptic divisibility sequences.

Our principal objects of study in this note are the sequences (d_{n}(α)) defined by (2). Our first task is to show that they are strong divisibility sequences.

Proposition 2. Let α ∈ ℤ̄ be a nonzero algebraic integer. The associated sequence (d_{n}(α))_{n≥1} defined by (2) is a strong divisibility sequence.

Proof. We begin by verifying that (d_{n}) is a divisibility sequence, i.e., it satisfies (3). Let m, n ∈ ℕ satisfy m|n and write

α^{m} − 1 = d_{m}v  and  α^{n} − 1 = d_{n}w.

By assumption, m|n, so we can use the identity

X^{N} − 1 = (X − 1)(X^{N−1} + X^{N−2} + ⋯ + X + 1)

with X = α^{m} and N = n/m to obtain

α^{n} − 1 = (α^{m} − 1)z with z ∈ ℤ̄.

Let g = gcd(d_{m}, d_{n}) and write

d_{m}x + d_{n}y = g with x, y ∈ ℤ.

We multiply through by w and substitute to obtain

gw = d_{m}xw + d_{n}yw = d_{m}xw + d_{m}vzy = d_{m}(xw + vzy).

Subtituting this in above yields (note that g|d_{m})

α^{n} − 1 = d_{n} · \frac{d_{m}}{g} · (xw + vzy).

Thus d_{n}d_{m}/g divides α^{n} − 1. But d_{n} is, by definition, the largest natural number dividing α^{n} − 1, so d_{m} = g. This shows that d_{m}|d_{n}, so (d_{n}) is a divisibility sequence.

We next show that (d_{n}) is a strong divisibility sequence, i.e., it satisfies (4). Let m, n ∈ ℕ be arbitrary and let k = gcd(m, n). Then k|m and k|n, so from above we know that d_{k}|d_{m} and d_{k}|d_{n}. Therefore d_{k}| gcd(d_{m}, d_{n}).

To prove the opposite divisibility, we write m = kM and n = kN. Then gcd(M, N) = 1, so there are polynomials A(X), B(X) ∈ ℤ[X] satisfying

A(X) · (X^{M} − 1) + B(X) · (X^{N} − 1) = X − 1.

(To see this, it is enough to observe that the resultant of \frac{X^{M} −1}{X−1} and \frac{X^{N} −1}{X−1} is 1.) Substituting X = α^{k} yields

A(α^{k}) · (α^{m} − 1) + B(α^{k}) · (α^{n} − 1) = α^{k} − 1.

As above, write α^{m} − 1 = a_{m}v and α^{n} − 1 = a_{n}w and let g = gcd(a_{m}, a_{n}). Then

g · (A(α^{k}) · \frac{d_{m}}{g} · v + B(α^{k}) · \frac{d_{n}}{g} · w) = α^{k} − 1,

where the quantity in parentheses is in ℤ̄. It follows that g ≤ d_{k}, since d_{k} is the largest natural number dividing α^{k} − 1. We have now shown that g ≤ d_{k} and d_{k}|g, which completes the proof that d_{k} = g = gcd(d_{m}, d_{n}). □

Remark 1. The fact that d_{n}(α) is a divisibility sequence follows from the [8, Proposition 8] applied to the torus obtained by restriction of scalars from ℤ[α] to ℤ of the multiplicative group 𝔾_{m}. Thus Proposition 2 strengthens [8] (for certain tori) by showing that the divisibility sequence is strong. To avoid introducing unnecessary machinery, we have been content to prove here the case that we need, but we note that it is not difficult to generalize Proposition 2 to the more general setting of commutative algebraic groups studied in [8].

2. Numerical examples

In this section we look at numerical examples that illustrate different sorts of behavior.

Example 1. The most elementary example is α ∈ ℤ with |α| > 1, which yields most classical examples a_{n} = α^{n} − 1 of divisibility sequences. However, there are many deep open problems for even this simple case. For example, are there infinitely many values of n for which a_{n}(2) is prime?

Example 2. Let α = 1 + i. The associated sequence is

(a_{n}(1 + i)) = 1, 1, 1, 5, 1, 1, 1, 15, 1, 1, 1, 65, 1, 1, 1, 255, 1, 1, 1, 1025, …

The pattern is clear and, using the fact that α^{4} = −4, it is easy to verify

a_{n} = |(−4)^{n/4} − 1| if 4|n, and otherwise a_{n} = 1.

Although very elementary, we point out that for this example we have

(5)  lim sup_{n→∞} \frac{log(a_{n})}{n} = \frac{1}{4} log(4) > 0.

Example 3. We again work in the Gaussian integers, but now we take α = 2+i. The associated sequence is

(a_{n}(2 + i)) = 1, 2, 1, 8, 1, 2, 1, 48, 1, 2, 1, 104, 1, 2, 1, 1632, 1, 2, 1, 8, 1, 2, 1, …

The pattern for α = 2+i is less regular than for α = 1+i, but the data certainly suggest that all of the odd entries are equal to 1. Unfortunately, it turns out that this is not true, since a_{27} = 109. Indeed, 914 of the first 1000 a_{n}’s with n odd are equal to 1, but some of them get quite large, for example a_{1917} = 835921. (Question: Are there infinitely many n satisfying a_{n}(2 + i) = 1?)

The a_{n} with even n seem to fluctuate more than the odd n, and in particular, many large values appear, as is apparent from the following longer list of values:

(a_{n}(2 + i)) = 1, 2, 1, 8, 1, 2, 1, 48, 1, 2, 1, 104, 1, 2, 1, 1632, 1, 2, 1, 8, 1, 2, 1, 1872,
1, 2, 109, 232, 1, 1342, 1, 3264, 1, 2, 1, 3848, 149, 2, 1, 1968, 1, 2,
1, 712, 1, 2, 1, 445536, 1, 2, 1, 424, 1, 218, 1, 1392, 1, 2, 1, 69784,
1, 2, 1, 6528, 1, 2, 1, 8, 1, 2, 1, 15168816, 1, 298, 1, 8, 1, 2, 1, …

It is not hard to see that sup a_{n} = ∞. More precisely, if p is a rational prime with p ≡ 1 (mod 4), then α^{p−1} ≡ 1 (mod p), so p|a_{p−1}. Hence there are infinitely many n such that log(a_{n}) ≥ log(n). However, this is much slower growth than (5), so we might ask whether log(a_{n})/n has a positive limsup. Table 1 lists the values of a_{n} for those n < 3000 satisfying a_{n} > a_{m} for all m < n. The table suggests that

lim sup_{n→∞} \frac{log(a_{n}(2 + i))}{n} = 0.

In Section 4 we use [5] to prove that this is indeed the case, but we note that [5] itself relies on Schmidt’s subspace theorem, so is far from elementary.

Example 4. Let α = 2 + \sqrt{3}. The associated sequence is

(a_{n}(2 + \sqrt{3} )) = 1, 2, 5, 8, 19, 30, 71, 112, 265, 418, 989, 1560, 3691, 5822,
13775, 21728, 51409, 81090, 191861, 302632, 716035, 1129438,
2672279, 4215120, 9973081, 15731042, 37220045, 58709048, …

The sequence clearly grows quite rapidly and regularly. We will show that it satisfies the linear recurrence

a_{n+4} = 4a_{n+2} − a_{n}.

In other words, if we define two subsequences using the odd and even terms, respectively,

b_{n} = a_{2n−1}  and  c_{n} = \frac{1}{2}a_{2n}  for n = 1, 2, 3, …,

Then b_{n} and c_{n} satisfy the linear recurrence, x_{n+2} = 4x_{n+1} − x_{n}, with starting values 1 and 5 for b_{n} and 1 and 4 for c_{n}. This is typical for the division

\begin{matrix}n & a_{n} & log(a_{n})/n \\ 1 & 1 & 0.0000 \\ 2 & 2 & 0.3466 \\ 4 & 8 & 0.5199 \\ 8 & 48 & 0.4839 \\ 12 & 104 & 0.3870 \\ 16 & 1632 & 0.4623 \\ 24 & 1872 & 0.3139 \\ 32 & 3264 & 0.2528 \\ 36 & 3848 & 0.2293 \\ 48 & 445536 & 0.2710 \\ 72 & 15168816 & 0.2296 \\ 96 & 2679453504 & 0.2261 \\ 144 & 4682401135776 & 0.2026 \\ 288 & 73018777396433948352 & 0.1588 \\ 576 & 16262888139288561844854144 & 0.1008 \\ 1152 & 28839207217834356759345681513216 & 0.0629 \\ 1440 & 118208444086469083866098414522688 & 0.0513 \\ 1728 & 194974704634639262404276022769124992 & 0.0470 \\ 2016 & 773127404949837686996635213979409984 & 0.0410 \\ 2160 & 54208082000209968285932117562946424303904 & 0.0434 \end{matrix}

Table 1. Growth of a_{n}(2 + i)

sequences associated to units in real quadratic fields (see Section 5). As the next example shows, nonunits appear to behave quite differently.

Example 5. Let α = 2 + 3\sqrt{3}. The associated sequence is

(a_{n}(2 + 3\sqrt{3} )) = 1, 6, 13, 24, 1, 234, 1, 48, 13, 66, 1, 34632, 1, 6, 13, 96,
1, 702, 1, 264, 13, 6, 1, 346320, 1, 6, 13, 24, 59, 2574, …

Notice the striking difference between this sequence and the sequence for 2+\sqrt{3} examined in Example 4. We will show that

log(a_{n}(2 + 3\sqrt{3} )) = o(n),

so this example resembles Example 3.

3. Linear dependence of Galois conjugates

In this section we prove an elementary result on the linear dependence of Galois conjugates. With an eye towards future applications and since the proof is no more difficult, we give a result that is more general than needed in this paper.

Proposition 3. Let K be a field with separable closure K^{s}, let X/K be a commutative algebraic group, which we write additively, and let x ∈ X(K^{s}). Suppose that for every σ ∈ G_{K^{s}/K}, the points x and x^{σ} are dependent in X. Then one of the following two conditions is true:

(a) There is an n ≥ 1 such that nx ∈ X(K).

(b) There is an n ≥ 1 such that

[K(nx) : K] = 2,  and also  Trace_{K(x)/K}(x) ∈ X(K)_{tors}.

Conversely, if either (a) or (b) is true, then x and x^{σ} are dependent for every σ ∈ G_{K^{s}/K}.

Proof. Let V = X(K^{s}) ⊗ ℚ and for any y ∈ X(K^{s}), let V_{y} be the vector subspace (over ℚ) of V generated by y and all of its Galois conjugates. Then G_{K^{s}/K} acts continuously on V_{y} and we obtain a represenation ρ_{y} : G_{K^{s}/K} → GL(V_{y}). The image is a finite subgroup of GL(V_{y}), which in general will yield information about y if dim(V_{y}) is smaller than [K(y) : K]. We have y^{σ} = ρ_{y}(σ)y in V, so there are torsion points t_{σ} ∈ X(K^{s})_{tors} so that y^{σ} = ρ_{y}(σ)y + t_{σ} in X(K^{s}). There are only finitley many distinct t_{σ}, so we can find an integer n ≥ 1 such that

(6)  (ny)^{σ} = ρ_{y}(σ)(ny)  for all σ ∈ G_{K^{s}/K}.

We start with the assumption that x and x^{σ} are dependent for all σ ∈ G_{K^{s}/K}, or equivalently, that V_{x} has dimension 1. Hence ρ_{x} : G_{K^{s}/K} → GL(V_{x}) = ℚ^{∗}, and since the image has finite order, it lies in {±1}. We consider two cases depending on this image.

First, if Image(ρ_{x}) = {1}, then (6) tells us that nx is fixed by G_{K^{s}/K}. Hence x ∈ X(K), which verifies that x satisfies (a).

Second, suppose that Image(ρ_{x}) = {±1}, and let L be the fixed field of the kernel of ρ_{x}, so [L : K] = 2. Then (6) tells us that nx is fixed by G_{K^{s}/L}, so nx ∈ X(L), and further it tells us that if σ ∉ G_{K^{s}/L}, then (nx)^{σ} = −nx. Thus nx ∉ G(K), so L = K(nx), which gives the first part of (b). For the second part, we use the fact that nx ∈ X(L) to compute

n Trace_{K(x)/K}(x) = Trace_{K(x)/K}(nx)

= \frac{[K(x) : L]}{n} Trace_{L/K}(nx) = nx + (−nx) = 0.

This shows that Trace_{K(x)/K}(x) is in X(K)_{tors}, which completes the proof that x satisfies (b)

We will not need the opposite implication, but for completeness, we sketch the proof. First, if nx ∈ X(K), then for every σ ∈ G_{K^{s}/K} we have x^{σ} = x + t_{σ} for some n-torsion point t_{s} ∈ X(K^{s})_{tors}. Hence nx^{σ} − nx = 0, so x^{σ} and x are dependent.

Next suppose that [K(nx) : K] = 2 and Trace(x) ∈ X(K)_{tors}. Let σ ∈ G_{K^{s}/K}. If σ fixes K(nx), then (nx)^{σ} −nx = 0, so (nx)^{σ} and nx are dependent. If σ does not fix K(nx), then

[K(x) : K(nx)]((nx)^{σ} + nx) = [K(x) : K(nx)] Trace_{K(nx)/K}(nx)
= Trace_{K(x)/K}(nx)
= n Trace_{K(x)/K}(x) ∈ X(K)_{tors}.

This proves that (nx)^{σ} and nx are dependent, which completes the proof of the theorem. □

We state as a corollary the special case that is needed later.

Corollary 4. Let α ∈ ℚ̄^{∗} and suppose that for every σ ∈ G_{ℚ̄/ℚ}, the elements α and α^{σ} are multiplicatively dependent. Then there is an integer n ≥ 1 so that one of the following is true.

(a) α^{n} ∈ ℚ.

(b) [ℚ(α^{n}) : ℚ] = 2 and N(α) = ±1.

Proof. Apply Proposition 3 to the multiplicative group 𝔾_{m}/ℚ and note that the torsion subgroup of 𝔾_{m}(ℚ) consists only of ±1. □

4. The growth of divisibility sequences

In this section we apply Corvaja and Zannier’s recent results [5] on generalized greatest common divisors (see also [3, 4]) to bound the growth rate of divisibility sequences (d_{n}(α)). More precisely, Theorem 5 describes precise conditions that force a divisibility sequence (d_{n}(α)) to grow slower than exponentially. We note that [5] is itself an application of Schmidt’s subspace theorem, so although the proof of the theorem is not long, it describes a deep property of divisibility sequences associated to algebraic integers.

Theorem 5. Let α ∈ ℤ̄ be a nonzero algebraic integer and let (d_{n}(α)) be the associated divisibility sequence,

d_{n}(α) = max{d ∈ ℤ : α^{n} ≡ 1 (mod d)}.

Assume that one of the following two conditions is true:

(a) [ℚ(α^{r}) : ℚ] ≥ 3 for all r ≥ 1.

(b) [ℚ(α^{r}) : ℚ] ≥ 2 for all r ≥ 1 and N_{K/ℚ}(α) ≠ ±1. Then

lim sup_{n→∞} \frac{log(d_{n}(α))}{n} = 0.

In other words, d_{n}(α) grows slower than exponentially.

Proof. To ease notation, we write d_{n} for d_{n}(α). Let K = ℚ(α), let L/ℚ be the Galois closure of K and let O_{L} be the ring of integers of L. By definition we have

α^{n} − 1 ∈ d_{n}R,

so in particular α^{n} − 1 ∈ d_{n}O_{L}. Applying an automorphism σ ∈ G_{L/ℚ}, we see that (α^{σ})^{n} − 1 ∈ d_{n}O_{L}, since d_{n} ∈ ℤ. Hence for every prime ideal 𝔭 of L we have

min{ord_{𝔭}(α^{n} − 1), ord_{𝔭}(α^{σ}^{n} − 1)} ≥ ord_{𝔭}(d_{n}).

Multiplying by an appropriate multiple of log N_{L/ℚ} 𝔭 and summing over primes yields

(7)  log gcd(α^{n} − 1, α^{σ}^{n} − 1) ≥ log d_{n},

where gcd is the generalized greatest common divisor used in [5, 8].

Suppose now that α and α^{σ} are multiplicatively independent in ℚ̄^{∗}. Then [5, Proposition] tells us that for every ϵ > 0 there is an n_{0} = n_{0}(ϵ, α, α^{σ}) with the property that

(8)  log gcd(α^{n} − 1, α^{σ}^{n} − 1) ≤ ϵn  for all n ≥ n_{0}.

Combining (7) and (8) yields the desired result.

So we are reduced to the case that for every σ ∈ G_{L/ℚ}, the elements α and α^{σ} are multiplicatively dependent. Corollary 4 says that in this case, there is an integer r with the property [ℚ(α^{r}) : ℚ] ≤ 2, which completes the proof of the theorem if α satisfies condition (a). If in addition [ℚ(α^{s}) : ℚ] ≠ 1 for all s ≥ 1, then Corollary 4 says that α has norm ±1, which proves the theorem when α satisfies condition (b). □

The theorem says that except in special cases, the sequence d_{n}(α) cannot grow too rapidly. One might ask if d_{n}(α) is frequently very small. We consider this question later in Section 6.

5. Real quadratic divisibility sequences

Theorem 5 says that d_{n}(α) grows slowly except in a few specified instances. In this section we analyze the cases that d_{n}(α) may grow rapidly. We assume throughout that α is not a root of unity.

The first case allowed by Theorem 5 is when there is an r ≥ 1 such that α^{r} ∈ ℤ. By assumption, |α^{r}| ≥ 2, so we find that

d_{rn}(α) = |α^{rn} − 1| ≥ |α^{r}|^{n} − 1 ≥ 2^{n} − 1.

Thus this “Kummer case” yields

lim sup_{n→∞} \frac{log(d_{n}(α))}{n} ≥ \frac{log 2}{r} > 0.

Further, if α^{r} is the smallest power of α that is in ℤ, then it is easy to see that d_{n}(α) = 1 if r ∤ n.

The more interesting case arises when α^{r} lies in a real quadratic extension of ℚ and has norm ±1. The following elementary identities will be useful in analyzing this case.

Lemma 6. For each n ∈ ℕ, let A_{n}, B_{n} ∈ ℚ[X, X^{−1}] be the Laurent polynomials

A_{n}(X, X^{−1}) = \frac{X^{n} + X^{−n}}{2}  and  B_{n}(X, X^{−1}) = \frac{X^{n} − X^{−n}}{2} .

Then the following identities hold in ℚ[X, X^{−1}].

\begin{aligned}(a) & A_{2n} − 1 & = 2B_{n}^{2} \\ (b) & B_{2n} & = 2A_{n}B_{n} \\ (c) & (A_{1} + 1)(A_{2n−1} − 1) & = (B_{n} + B_{n−1})^{2} \\ (d) & B_{1}B_{2n−1} & = B_{n}^{2} − B_{n−1}^{2} \end{aligned}

Proof. Substitute the definition of A_{n} and B_{n} into each of the stated identities and use elementary algebra to simplify. We illustrate with (c). First we compute

2(B_{n} + B_{n−1}) = X^{n} − X^{−n} + X^{n−1} − X^{−n+1}
= X^{n−1}(X + 1) − X^{−n}(1 + X)
= (X + 1)(X^{n−1} − X^{−n}).

Replacing X by X^{−1} introduces a minus sign into B_{n} and B_{n−1}, so

2(B_{n} + B_{n−1}) = −(X^{−1} + 1)(X^{−n+1} − X^{n}).

Now multiplying these two expressions yields

4(B_{n} + B_{n−1})^{2} = −(X + 1)(X^{−1} + 1)(X^{n−1} − X^{−n})(X^{−n+1} − X^{n})
= (X + X^{−1} + 2)(X^{2n−1} + X^{−2n+1} − 2)
= 4(A_{1} + 1)(A_{2n−1} − 1).

The other parts are similar. □

The next two propositions give a complete description of d_{n}(α) for α = u + v\sqrt{D} with u, v ∈ ℤ. The other cases of real quadratic irrationalities are handled similarly. The details are left to the reader.

Theorem 7. Let D ≥ 2 be an integer that is not a perfect square, and let α = u + v\sqrt{D} ∈ ℤ[\sqrt{D}] be the unit associated to a nontrivial positive solution (i.e., u, v > 0) of the Pell equation

u^{2} − v^{2}D = 1.

Write

α^{n} = (u + v\sqrt{D} )^{n} = u_{n} + v_{n}\sqrt{D},

so the divisibility sequence associated to α is given by

d_{n}(α) = gcd(u_{n} − 1, v_{n}).

Then

d_{n}(α) = \begin{cases}2v_{n/2} & if n is even, \\ gcd(u − 1, v)\frac{v_{(n+1)/2} + v_{(n−1)/2}}{v} & if n is odd. \end{cases}

The sequence d_{n}(α) satisfies the fourth order linear recursion

d_{n+4} = 2ud_{n+2} − d_{n}

whose characteristic polynomial is

T^{4} − 2uT^{2} + 1 = (T^{2} − (u + v\sqrt{D}))(T^{2} − (u − v\sqrt{D})).

The sequence grows exponentially,

(9)  lim_{n→∞} \frac{log d_{n}(α)}{n} = \frac{1}{2} log(α) > 0.

Theorem 8. Let D, α, u_{n}, v_{n}, d_{n}(α) be as in the statement of Theorem 7 except now we assume that

u^{2} − v^{2}D = −1.

Then

d_{n}(α) = \begin{cases}1 & if n ≡ 1 (mod 2), \\ 2v_{n/2} & if n ≡ 0 (mod 4), \\ \frac{v_{n/2+1} + v_{n/2−1}}{u} & if n ≡ 2 (mod 4), \end{cases}

In particular, the even terms d_{2n}(α) satisfy a linear recurrence and grow exponentially, but the odd terms d_{2n+1}(α) form a constant sequence.

Proof of Theorem 7. Letting ᾱ = u − v\sqrt{D}, we have the usual formulas

(10)  u_{n} = \frac{α^{n} + ᾱ^{n}}{2} and v_{n} = \frac{α^{n} − ᾱ^{n}}{2\sqrt{D}} .

The sequences (u_{n}) and (v_{n}) satisfy the recurrence

x_{n+2} = 2ux_{n+1} − x_{n}

with initial values

u_{0} = 1, u_{1} = u, v_{0} = 0, v_{1} = v.

We observe that v|v_{n} for every n ≥ 0, so if we define a reduced sequence by ṽ_{n} = v_{n}/v, then ṽ_{n} is the linear recursion sequence defined by

(11)  ṽ_{0} = 0, ṽ_{1} = 1, ṽ_{n+2} = 2uṽ_{n+1} − ṽ_{n}.

By assumption, αᾱ = 1, so we have ᾱ = α^{−1} and the identities in Lemma 6(a,b) with X = α yield

(12)  u_{2n} − 1 = d_{2n} − 1 = 2B_{n}^{2} = 2v_{n}^{2}D,
(13)  v_{2n} = \frac{B_{2n}}{\sqrt{D}} = \frac{2A_{n}B_{n}}{\sqrt{D}} = 2u_{n}v_{n},

Using these, it is easy to compute the even terms of the divisibility sequence,

d_{2n}(α) = gcd(2v_{n}^{2}D, 2u_{n}v_{n}) = 2v_{n} gcd(v_{n}D, u_{n}) = 2v_{n}.

For the last equality, we use the fact that u_{n}^{2} − Dv_{n}^{2} = 1 to conclude that u_{n} and v_{n}D are relatively prime.

Similarly, the identities in Lemma 6(c,d) with X = α give

(u + 1)(u_{2n−1} − 1) = (A_{1} + 1)(d_{2n−1} − 1)

= (B_{n} + B_{n−1})^{2} = (v_{n} + v_{n−1})^{2}D, (14)

(15)  vv_{2n−1} = \frac{B_{1}B_{2n−1}}{D} = \frac{B_{n}^{2} − B_{n−1}^{2}}{D} = v_{n}^{2} − v_{2n−1}^{2}.

These give us a somewhat complicated formula for the odd terms in the divisibility sequence,

(16)  d_{2n−1}(α) = gcd (\frac{(v_{n} + v_{n−1})^{2}D}{u + 1} , \frac{v_{n}^{2} − v_{n−1}^{2}}{v} ) .

Documenta Mathematica · Extra Volume Coates (2006) 711–727

Using the reduced sequence ṽ_{n} = v_{n}/v, we observe that

(v_{n} + v_{n−1})^{2}D = (ṽ_{n} + ṽ_{n−1})^{2}v^{2}D = (ṽ_{n} + ṽ_{n−1})^{2}(u^{2} − 1),

so we can rewrite (16) as

d_{2n−1}(α) = gcd (\frac{(ṽ_{n} + ṽ_{n−1})^{2}(u^{2} − 1)}{u + 1}, \frac{(ṽ_{n}^{2} − ṽ_{n−1}^{2})v^{2}}{v} )
= gcd ((ṽ_{n} + ṽ_{n−1})^{2}(u − 1), (ṽ_{n}^{2} − ṽ_{n−1}^{2})v)

= (ṽ_{n} + ṽ_{n−1}) gcd ((ṽ_{n} + ṽ_{n−1})(u − 1), (ṽ_{n} − ṽ_{n−1})v) . (17)

It remains to show the the gcd is equal to gcd(u − 1, v).

A first observation is that adjacent terms of the sequence (ṽ_{n}) are relatively prime, i.e., gcd(ṽ_{n}, ṽ_{n−1}) = 1, and further, they are alternately odd and even. This follows easily by induction from the initial values and recursive formula (11) satisfied by the sequence (ṽ_{n}). Hence

(18)  gcd (ṽ_{n} + ṽ_{n−1}, ṽ_{n} − ṽ_{n−1}) = 1,

since the gcd certainly divides gcd(2ṽ_{n}, 2ṽ_{n−1}) = 2, and it cannot equal 2 since ṽ_{n} + ṽ_{n−1} is odd.

It is convenient to write out explicitly the closed sum for ṽ_{n}:

ṽ_{n} = \frac{v_{n}}{v} = \frac{(u + v\sqrt{D})^{n} − (u − v\sqrt{D})^{n}}{2\sqrt{D}v}

= \frac{1}{2\sqrt{D}v} ∑_{k=0}^{n} \binom{n}{k}u^{n−k}(v\sqrt{D})^{k}(1 − (−1)^{k})

= ∑_{k=0}^{⌊(n−1)/2⌋} \binom{n}{2k + 1}u^{n−2k−1}v^{2k}D^{k}.

In particular, there are rational integers E_{n} ∈ ℤ such that

(19)  ṽ_{n} = nu^{n−1} + v^{2}DE_{n}.

We first compute (using v^{2}D = u^{2} − 1)

ṽ_{n} − ṽ_{n−1} = (nu^{n−1} + v^{2}DE_{n}) − ((n − 1)u^{n−2} + v^{2}DE_{n−1})
= nu^{n−2}(u − 1) + u^{n−2} + (u^{2} − 1)(E_{n} − E_{n−1})
≡ 1 (mod u − 1).

This proves that

(20)  gcd(u − 1, ṽ_{n} − ṽ_{n−1}) = 1.

If we could prove that gcd(ṽ_{n} + ṽ_{n−1}, v) = 1, we would be done, but unfortunately it is easy to produce examples where this fails to be true. To obtain a weaker identity that suffices, we begin with the formula

ṽ_{n} + ṽ_{n−1} = nu^{n−1} + (n − 1)u^{n−2} + v^{2}D(E_{n} + E_{n−1})

≡ u^{n−2}(n(u + 1) − 1) (mod v). (21)

Multiplying by u − 1 yields

(ṽ_{n} + ṽ_{n−1})(u − 1)
≡ u^{n−2}(n(u^{2} − 1) − (u − 1)) (mod v) from (21),
≡ u^{n−2}(nv^{2}D − (u − 1))  (mod v) since u^{2} − 1 = v^{2}D,
≡ −u^{n−2}(u − 1)  (mod v).

Hence

gcd ((ṽ_{n} + ṽ_{n−1})(u − 1), v) = gcd (−u^{n−2}(u − 1), v)

= gcd(u − 1, v), (22)

since u and v are relatively prime.

Combining the above gcd computations, we find that

gcd((ṽ_{n} + ṽ_{n−1})(u − 1), (ṽ_{n} − ṽ_{n−1})v)
= gcd ((ṽ_{n} + ṽ_{n−1})(u − 1), v)  from (18) and (20),
= gcd(u − 1, v)  from (22).

We are finally able to substitute this into (17) to obtain the formula

d_{2n−1}(α) = (ṽ_{n} + ṽ_{n−1}) gcd((ṽ_{n} + ṽ_{n−1})(u − 1), (ṽ_{n} − ṽ_{n−1})v)

= (ṽ_{n} + ṽ_{n−1}) gcd(u − 1, v)

= \frac{(v_{n} + v_{n−1}) gcd(u − 1, v)}{v},

which completes the proof of the stated formula for the odd terms in the divisibility sequence d_{n}(α).

In order to prove that d_{n}(α) satisfies a recurrence relation and to measure its exponential growth, we observe that we have proven that there are constants c_{1} and c_{2} (depending on u and v) so that

\begin{aligned}d_{2n}(α) & = c_{1}v_{n}, \\ d_{2n−1}(α) & = c_{2}(v_{n} + v_{n−1}). \end{aligned} (23)

The sequence v_{n} satisfies v_{n+2} = 2uv_{n+1}−v_{n}, so (23) implies the two recursions

d_{2n+4}(α) = 2ud_{2n+2}(α) − d_{n}(α)
d_{2n+3}(α) = 2ud_{2n+1}(α) − d_{2n−1}(α).

Thus the sequence d_{n}(α) satisfies the recursive formula x_{n+4} = 2ux_{n+2} − x_{n} whose characteristic polynomial is

T^{4} − 2uT^{2} + 1 = (T^{2} − α)(T^{2} − ᾱ),

since α+ᾱ = 2u and αᾱ = 1. Finally, since we have chosen α to satisfy |α| > 1, the limit formula (9) follows from (23) and the fact that

lim_{n→∞} \frac{log v_{n}}{n} = lim_{n→∞} \frac{log (\frac{α^{n} − α^{−n}}{2\sqrt{D}} )}{n} = log(α).

Documenta Mathematica · Extra Volume Coates (2006) 711–727

This completes the proof of Theorem 7. □

Proof of Theorem 8. Clearly we have d_{2n}(α) = d_{n}(α^{2}) directly from the definition. Let β = α^{2}. Then ββ̄ = (αᾱ)^{2} = (−1)^{2} = 1, so the divisibility sequence d_{n}(β) is of exactly the type described in Theorem 8. In order to obtain an explicit formula for d_{n}(β) = d_{2n}(α), we observe that

v_{n/2}(β) = v_{n}(α) for even n,
v_{(n±1)/2}(β) = v_{n±1}(α) for odd n,
u(β) − 1 = u_{2}(α) − 1 = u^{2} + v^{2}D − 1 = 2v^{2}D,
v(β) = v_{2}(α) = 2uv,
gcd(u(β) − 1, v(β)) = gcd(2v^{2}D, 2uv) = 2v.

(Note that here u and v are given by α = u+v\sqrt{D}.) We substitute these values into the formula for a_{n}(β) provided by Theorem 8. Thus if n is even we find that

d_{2n}(α) = d_{n}(β) = 2v_{n/2}(β) = 2v_{n}(α),

and if n is odd we obtain

d_{2n}(α) = d_{n}(β) = \frac{gcd(u(β) − 1, v(β))(v_{(n+1)/2}(β) + v_{(n−1)/2}(β))}{v(β)}

= \frac{2v(v_{n+1}(α) + v_{n−1}(α))}{2uv}

= \frac{(v_{n+1}(α) + v_{n−1}(α))}{u}

This completes the proof of the formula for the even terms in the sequence d_{n}(α). It remains to show that d_{n}(α) = 1 when n is odd.

We assume henceforth that n is odd. Then u_{n}^{2} −v_{n}^{2}D = −1, which we rewrite as

(24)  (u_{n} + 1)(u_{n} − 1) − v_{n}^{2}D = −2.

This equation shows that gcd(u_{n} −1, v_{n}) divides 2. However, it cannot equal 2, since otherwise the lefthand side of (24) would be divisible by 4. This completes the proof that d_{n}(α) = gcd(u_{n} − 1, v_{n}) = 1 when n is odd. □

6. Small entries in divisibility sequences

Theorem 5 tells us that except in a few specified cases, the sequence d_{n}(α) grows slower than exponentially, and although the values do occasionally get quite large, we find experimentally that d_{n}(α) is also often quite small. This leads us to make the following conjecture, which is the analog of a conjecture of Ailon and Rudnick [1] regarding gcd(a^{n} − 1, b^{n} − 1) for multiplicatively independent integers a and b.

\begin{matrix}n ≤ & d_{n} = 1 & d_{n} = 2 & d_{n} = 3 & d_{n} = 4 & d_{n} = 5 & d_{n} = 6 \\ 1000 & 67.30 % & 6.30 % & 3.90 % & 2.80 % & 1.10 % & 0.30 % \\ 5000 & 66.32 % & 6.10 % & 3.72 % & 2.50 % & 0.78 % & 0.32 % \\ 10000 & 65.91 % & 6.03 % & 3.66 % & 2.47 % & 0.77 % & 0.33 % \\ 15000 & 65.82 % & 5.99 % & 3.60 % & 2.42 % & 0.78 % & 0.33 % \\ 20000 & 65.59 % & 5.98 % & 3.60 % & 2.40 % & 0.76 % & 0.32 % \end{matrix}

Table 2. Frequency of {n : d_{n}(α) = k} for α^{3} − α − 1 = 0

Conjecture 9. Let α ∈ ℤ̄ be a nonzero algebraic integer and let (d_{n}(α)) be the associated divisibility sequence (2). Assume that α satisfies one of the conditions (a) or (b) in Theorem 5. Then

{n ≥ 1 : d_{n}(α) = d_{1}(α)}

is infinite.

Example 6. It is worthwhile looking at a nontrivial example numerically. Let α be root of T^{3} − T − 1. We find that the associated sequence starts

(d_{n}) = 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 4, 1, 1, 1, 1, 1, 1, 2, 1, 1, 5, 1, 3, 1, 8,
1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 9, 1, 1, 4, 1, 1, 1, 1, 1, 35, 2, 1, 1, 3, 1,
1, 1, 16, 1, 59, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 4, 1, 5, 1, 1, 1, 1, 2, 9, 1,
1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 35, 1, 4, 1, 101, …

The data appears to support Conjecture 9 that d_{n} = 1 for infinitely many values of n. From this small amount of data it is less clear how often we should expect to have, say, d_{n} = 2 or d_{n} = 3. Table 2 gives the frequency of d_{n} = k for each k = 1, 2, …, 6 and n ≤ N for various values of N. The table suggests that the set {n ∈ ℕ : d_{n} = k} is infinite, and indeed possibly that it has a positive density.

However, it is easily seen that there are some values of k for which the set is empty. For example, we claim that d_{n}(α) ≠ 7 for all n. The reason is that the smallest power of α satsifying α^{n} ≡ 1 (mod 7) is α^{48} and

α^{48} − 1 = 128800 + 226030α + 170625α^{2} = 35(3680 + 6458α + 4875α^{2}).

Thus

7|d_{n} ⟹ 48|n ⟹ 35|d_{n},

so d_{n} will never equal 7. It would be interesting to characterize the set {k ∈ ℕ : d_{n}(α) ≠ k for all n}.

Based on this and various other examples, it is tempting to make a conjecture of the following sort, although given the scanty evidence, it seems safer to phrase it as a question.

Question 1. Let α ∈ ℤ̄ be a nonzero algebraic integer and let (d_{n}(α)) be the associated divisibility sequence (2) as usual. For each k ∈ ℕ, let

S_{α}(k) = {n ∈ ℕ : d_{n}(α) = k}.

Is it true that either S_{α}(k) = ∅ or else S_{α}(k) has positive (lower) density in ℕ.

If Question 1 has an affirmative answer, it then becomes a very interesting question to describe the density of S_{α}(k) in terms of arithmetic properties of α, even for the initial nontrivial case S_{α}(d_{1}(α)).

Remark 2. The divisibility sequences d_{n}(α) studied in this paper can be defined in far more generality, for example using an element α in a ring of the form R = ℤ[T]/(F (T)) for a monic polynomial F (T) ∈ ℤ[T]. Thus d_{n}(α) is the largest rational integer d such that α^{n} − 1 is divisible by d in the ring R.

As a particular example, consider the ring R = ℤ[T]/(T^{2} − T) and element α = T + 2. The natural isomorphism

R ≅ ℤ[T]/(T) × ℤ[T]/(T − 1)

identifies α ↔ (2, 3), so d_{n}(α) = gcd(2^{n} − 1, 3^{n} − 1). Ailon and Rudnick [1] conjecture in this case that d_{n}(α) = 1 for infinitely many n, and more generally they conjecture that if a, b ∈ ℤ are multiplicatively independent, then

(25) gcd(a^{n} − 1, b^{n} − 1) = gcd(a − 1, b − 1) for infinitely many n ≥ 1.

Thus Conjecture 9 may be viewed as a generalization of Ailon and Rudnick’s conjecture, and Question 1 suggests a strengthened statement. Ailon and Rudnick prove a strong version of (25) with ℤ replaced by the polynomial ring ℂ[T]. See also [6] and [7] for analogs over 𝔽_{q}[T] and for elliptic curves and [8, Section 7] for a more general conjecture on the infinitude, although not the density, of values of divisibility sequences associated to commutative group schemes.

References

[1] N. Ailon, Z. Rudnick, Torsion points on curves and common divisors of a^{k} − 1 and b^{k} − 1, Acta Arithmetica 113 (2004), 31–38.

[2] J.P. Bézivin, A. Pethö, A.J. van der Poorten, A full characterisation of divisibility sequences, Amer. J. of Math. 112 (1990), 985–1001.

[3] Y. Bugeaud, P. Corvaja, U. Zannier, An upper bound for the G.C.D. of a^{n} − 1 and b^{n} − 1, Math. Zeit. 243 (2003), no. 1, 79–84.

[4] P. Corvaja, U. Zannier, On the greatest prime factor of (ab + 1)(ac + 1), Proc. Amer. Math. Soc. 131 (2002), 1705–1709.

[5] A lower bound for the height of a rational function at S-unit points, Monatshefte Math., 144 (2005), 203–224.

[6] J.H. Silverman, Common divisors of a^{n} − 1 and b^{n} − 1 over function fields, New York Journal of Math. (electronic) 10 (2004), 37–43.

[7] Common divisors of elliptic divisibility sequences over function fields, Manuscripta Math., 114 (2004), 432–446.

[8] Generalized greatest common divisors, Divisibility sequences, and Vojta’s conjecture for blowups Monatsch. Math., 145 (2005), 333–350.

[9] M. Ward, Memoir on elliptic divisibility sequences, Amer. J. Math. 70 (1948), 31–74.

Joseph H. Silverman Mathematics Department Box 1917 Brown University Providence RI 02912 USA jhs@math.brown.edu 728

Documenta Mathematica · Extra Volume Coates (2006)