STABILITY OF SECOND-ORDER RECURRENCES MODULO p

© Hindawi Publishing Corp.

STABILITY OF SECOND-ORDER RECURRENCES MODULO p

LAWRENCE SOMER and WALTER CARLIP (Received 13 April 1999)

Abstract.The concept of sequencestabilitygeneralizes the idea of uniform distribution.

A sequence isp-stableif the set of residue frequencies of the sequence reduced modulo p^r is eventually constant as a function ofr. The authors identify and characterize the stability of second-order recurrences modulo odd primes.

Keywords and phrases. Lucas, Fibonacci, stability, uniform distribution, recurrence.

2000 Mathematics Subject Classification. Primary 11B39, 11B50; Secondary 11Y55, 11B37.

1. Introduction. Letw(a,b)=(w)be a second-order linear recurrence satisfying the relation

wn+2=awn+1−bwn, (1.1)

where the parametersaandband the initial termsw0andw1are all rational integers.

Ifmis a positive integer, then the sequencew(a,b)is eventually periodic when re- duced modulom. For any residued, we letνw(d,m)denote the number of times that the residuedappears in one shortest period (cycle) of the recurrencew(a,b)mod- ulom. The functionνw(d,m)is thefrequency distributionfunction of the sequence w(a,b)modulom. LetΩw(m)be the image of the frequency distribution function, i.e.,

Ωw(m)= {νw(d,m)|d∈Z}. (1.2) We are concerned here with the possible values taken on by the frequency distribution functionνw(d,m)whenm=p^r is a power of an odd prime.

In 1992, while investigating the Fibonacci sequenceu(1,−1)modulo powers of two, Eliot Jacobson [12] discovered that the frequency setsΩu(1,−1)(2^r)are eventually con- stant as a function ofr. This observation led to the definition of sequence stability.

Definition1.1. A sequence(w)isstable modulop, or simplyp-stable, if there is a positive integerNsuch thatΩw(p^r)=Ωw(p^N)for allr≥N.

Our interest in sequence stability developed naturally from earlier study of fre- quency distributions of second-order recurrence sequences. In the 1970s, an extensive investigation of second-order recurrence sequences led to the complete characteriza- tion, by Bumby [1] and Webb and Long [22], of second-order recurrence sequences for which|Ω(m)| =1. The frequency distribution function of these sequences is con- stant and they are calleduniformly distributed. Investigation of distributions for which

|Ω(m)|is small soon followed.

In 1988 and 1989, Jacobson [10, 11] recognized that, although the Fibonacci se- quenceu(1,−1)is not always uniformly distributed modulop, the setΩu(1,−1)(p)is often small. He studied modulimfor whichu(1,−1)modulomis almost uniform, i.e.,|Ω(m)| =2. Conjectures proposed at the First Meeting of the Canadian Number Theory Association in Banff (1988) spurred Andrzej Schinzel [14] to classify the sets Ωw(p)for a large class of second-order recurrences(w)and odd primespfor which

|Ω(m)| ≤4.

With the introduction of the concept of stability, the study of the frequency distribu- tions of second-order recurrence sequences modulo prime powers has become much more tractable. Once a sequence is identified asp-stable, the set of allowable frequen- cies can, in theory, be computed with a finite computation; the frequency distributions modulo arbitrary powers ofpcan then be determined. In practice, as Carlip and Jacob- son observed in [4], these computations may be arbitrarily long; the setsΩ(p^r)may be arbitrarily large and the constantN(theindex of stability) required in the definition of stability also arbitrarily large.

Stability of second-order recurrences modulo two has been extensively studied by Carlip and Jacobson in [2, 3, 4, 5], while stability modulo odd primes has been ex- amined by Carlip, Jacobson, and Somer in [6] and Carroll, Jacobson, and Somer in [9]. In recent work Carlip and Somer [7, 21] have studied the frequency distributions of second-order recurrences modulo powers of odd primes. The primary purpose of this paper is to show how the results in [7] and [21] can be applied to characterize the stability of sequences. In particular, we exhibit several classes of second-order recurrences that fail to bep-stable and provide explicit new criteria for other second- order recurrence sequences to bep-stable. In the process we extend earlier results and provide a catalogue of what is currently known about thep-stability of second-order recurrences for oddp.

2. Preliminaries and notation. We make free use of the terminology and notation of [7] and [21]. For the convenience of the reader, we provide some of the basic defi- nitions and specialized results here.

2.1. The familyᏲ(a,b). Throughout this paper, we fix a primep, usually odd, and study thep-stability of second-order recurrences from a familyᏲ(a,b)of second- order recurrencesw(a,b)=(w)that satisfy the recurrence relation

wn+2=awn+1−bwn, (2.1)

for various initial termsw0andw1.

Ifp^m(w0,w1)for somem≥1, thenp^m(wn,wn+1)for alln≥0. If(w_n)is the re- currence defined byw_n =wn/p^m, thenp(w₀,w₁)andνw(d,p^r)=νw(p^md,p^r+m) for allr≥1. Thus, we can determine the frequency distribution function of(w)from that of(w), and accordingly we restrict our attention to those recurrences for which p(w0,w1).

Definition 2.1. The family Ᏺ(a,b) consists of all second-order recurrence se- quences(w)that satisfy (2.1) andp(w0,w1).

In general, elementswn for whichp|wn behave quite differently from elements

for whichpwn. We refer to elementswnfor whichp|wnasp-singular elements of(w)and elements for whichpwnasp-regular elements of(w). Analogously, we call an integerd p-singular ifp|dandp-regular ifpd.

In addition to the constantsaand b, there are other parameters associated with the familyᏲ(a,b)and referred to asglobal parametersof the family. These include constants associated with thecharacteristic polynomial

f (x)=x²−ax+b, (2.2)

such as the rootsαandβand the discriminantD=D(a,b)=a²−4b. A number of our results require constraints onD, e.g., requiring thatDbep-regular or a quadratic residue modulop.

2.2. Stability and the stability index. As mentioned in the introduction, a sequence (w)is p-stable if there is a positive integerN such that Ωw(p^r)=Ωw(p^N)for all r≥N. In [4], Carlip and Jacobson observed that whenp=2, the integerN, thegener- ationat which stabilitybegins, may be arbitrarily large. We formalize the study of the parameterNwith the following definition.

Definition2.2. Suppose that(w)isp-stable. The smallest positive integerNsuch thatΩw(p^r)=Ω(p^N)for allr≥Nis called theindex ofp-stability, or simply theindex of stability whenpis understood. The stability index of(w)is denoted byιw(p), or simplyι(p)when(w)is understood.

2.3. Blocks of sequences. The familyᏲ(a,b)is endowed with a natural equivalence relation that preserves many important properties.

Definition 2.3. The recurrence w(a,b)is a multiple of a translation (mot) of w(a,b)modulop^rif there exist integersmandcsuch thatpcand for alln

w_n≡cwn+m (modp^r). (2.3)

The equivalence classes of the relationmot are called the p^r-blocks. If d is any integer, thenνw(d,p^r)=νw(cd,p^r), and therefore for everyn

νw(wn+m,p^r)=νw(w_n,p^r). (2.4) Thus, two sequences in the same block have the same pattern of frequencies of residues in corresponding cycles.

2.4. Periods,restricted periods,and multipliers. If the defining parameter b is p- regular, then each sequencew(a,b)is purely periodic when reduced modulop^r. We letλw(p^r)denote theperiodofw(a,b)modulop^r, i.e., the least positive integer λsuch that for alln

wn+λ≡wn (modp^r). (2.5)

Similarly,hw(p^r)denotes therestricted period ofw(a,b)modulo p^r, i.e., the least positive integerhsuch that for some integerMand for alln

wn+h≡Mwn (modp^r). (2.6)

The integerM=Mw(p^r), defined up to congruence modulop^r, is called themultiplier

of w(a,b) modulo p^r. It is well known that hw(p^r)|λw(p^r) and that Ew(p^r)= λw(p^r)/hw(p^r)is the multiplicative order in(Z/p^rZ)^∗of the multiplierMw(p^r).

2.5. Regular recurrences. In this paper, we are primarily concerned withp-regular sequences. A recurrence sequencew(a,b)isregularmodulop, or simplyp-regular, if

w0 w1

w1 w2

=w0w2−w₁²≡0 (modp). (2.7) It is evident thatp-regularity is preserved by the equivalence relationmot. Thus, if a block contains a regular recurrence, then every recurrence in that block is regular and we refer to that block as aregular block.

If p|(w0,w1), then certainly(w) is notp-regular. The second-order recurrence sequences that fail to be p-regular may be characterized as those sequences that, modulop, satisfy a recurrence relation of order one.

A straightforward argument shows that allp-regular recurrences in Ᏺ(a,b)have the same period, restricted period, and multiplier modulop^r. Consequently, these may be considered to be global parameters of the familyᏲ(a,b), and we use the notationλ(p^r),h(p^r), andM(p^r)to represent the period, restricted period, and mul- tiplier modulop^r of allp-regular recurrences inᏲ(a,b). We make frequent use of the quotientλ(p)/h(p), a global parameter that we now recognize as the multiplicative order of the multiplierM(p)corresponding to anyp-regular sequence inᏲ(a,b). For notational convenience we defines=E(p)=λ(p)/h(p).

We require Lemma 2.4, which characterizes the restricted period in terms of the characteristic roots.

Lemma2.4. Suppose thatpD(a,b)and thatαandβare the roots of the charac- teristic polynomialf (x)=x²−ax+b. LetP be a prime ideal lying overp inQ(α).

Thenh(p^r)is the least integernsuch thatαⁿ≡βⁿ (modP^r).

Proof. This follows from the standard Binet formula for the regular sequence u(a,b)(defined in Definition 2.5). See, e.g., [6, Lem. 2.1].

2.6. Some special recurrences. Three special sequences in the familyᏲ(a,b)play a prominent role in our study. These sequences,(u),(v), and(t), are characterized by their initial terms.

Definition 2.5. (a) The Lucas sequence of the first kind (LSFK), u(a,b), is the sequence inᏲ(a,b)with initial termsu0=0 andu1=1.

(b) The Lucas sequence of the second kind (LSSK),v(a,b), is the sequence inᏲ(a,b) with initial termsv0=2 andv1=a.

(c) The recurrencet(a,b), defined when p is odd,_b

p

=1, andu(a,b) has even restricted period modulop, is the recurrence inᏲ(a,b)with initial termst0=1 and t1=θ, whereθ²≡b (modp)and 0≤θ≤(p−1)/2.

If in place ofθ, in the definition oft(a,b), we use the square rootθofbmodulo psatisfying(p−1)/2≤θ≤p−1, then, by [20, pp. 534–535], the resulting sequence is amotoft(a,b)modulop. Moreover, the same paper shows that whent(a,b)is defined, it is never amotofu(a,b)or ofv(a,b)modulop.

We make frequent use of the fact that the recurrenceu(a,b)is alwaysp-regular.

It follows that λ(p^r)=λu(p^r), h(p^r)=hu(p^r), and M(p^r)≡Mu(p^r) (modp^r).

Moreover, M(p^r)≡ uh+1 (modp^r), and h(p^r) is the smallest index h such that uh≡0 (modp^r). Further, we note that the recurrencev(a,b)isp-regular if and only ifpD(a,b)and thatt(a,b)isp-regular whenevert(a,b)is defined.

We require Lemma 2.6, which relates thep-blocks containing the sequencesu(a,b) andv(a,b).

Lemma2.6. The sequencesu(a,b)andv(a,b)lie in the samep-block if and only ifh(p)is even.

Proof. Clearly,v(a,b)is amotofu(a,b)modulopif and only ifp|vmfor some positive integerm. The lemma now follows from [8, pp. 42, 47].

2.7. Nondegenerate recurrences. Given a primep, we define the global parame- tereto be the largest integer, if it exists, such that h(p^e)=h(p). Since u(a,b)is p-regular, it follows thateis uniquely determined byp^euh(p). Ifedoes not exist, thenuh(p)=0, and thep-regular sequences inᏲare calleddegenerate.

Similarly,f is the largest integer such thatλ(p^f)=λ(p). It is easy to see that ife exists, thenfalso exists andf≤e.

The parameterseandfplay a critical role in the structure theory of second-order recurrence sequences. One of the outstanding open questions in the theory is whether for the familyᏲ(1,−1), the family that contains the Fibonacci sequenceu(1,−1), there exists a primepfor whiche >1.

In this paper, the relationship betweeneandfdetermines the subsequent analysis.

If p D and ord_p2e(b)|p−1, then Theorems 2.13 and 2.10 imply thate=f. In particular, this is true whenb= ±1. On the other hand, ife≥2, then it may occur that f < eorf=e.

2.8. Distribution theorems. Our discussion of sequence stability makes use of spe- cialized results and notation concerning the frequency distributions of residues of second-order recurrences that appear in [7] and [21]. We list several of these key the- orems here.

The principle methodology of [7] and [21] requires a subtle analysis of the ratios of certain terms of a recurrencew(a,b)modulop^r. Such ratios are well defined when the denominator isp-regular and may be viewed as embedded in the localizationZp

of the integers at the ideal (p). To facilitate analysis of these ratios, we make the following definition.

Definition 2.7. If (w) is a recurrence and m and n are nonnegative integers such that p wn, then we define ρw(n,m), or simply ρ(n,m), to be the element wn+m/wn∈Zp.

We also require several special constants. We definer^∗=max(r /2,e)for use in Theorem 2.12, and, in order to handle small values ofr, we definee^∗=min(r ,e)and f^∗=min(r ,f ). Also, we recall thats=Ew(p)=λw(p)/hw(p)is the multiplicative order inZ/(p)of the multiplierMw(p).

Theorem2.8[7, Thm. 6.2]. Suppose thatw(a,b)∈Ᏺ(a,b)isp-regular,f < e, and pd. Then, for allr > f,

ν(d,p^r)=ν d,p^f

≤ν(d,p). (2.8)

Hypothesis2.9[7, Hypothesis 6.3]. There exist ap-regular recurrencew(a,b)∈ Ᏺ(a,b)and an integernsuch thatord_p2e(ρw(n,h(p^e)))|p−1.

Theorem2.10[7, Thm. 6.4]. If Hypothesis 2.9 holds, thene=f and ord_p^2e

ρw

n,h(p^e)

=s. (2.9)

Conversely, ife=fand_D

p

= −1, then Hypothesis 2.9 holds.

Theorem2.11[7, Thm. 6.5]. Letw(a,b)∈Ᏺ(a,b)be ap-regular recurrence sat- isfying the conditions of Hypothesis 2.9 and assume thatr > f. Letw(a,b)∈Ᏺ(a,b) and assume thatw(a,b)is not amot ofw(a,b)modulop. Then, for allp-regular residuesdmodulop^r,

ν(d,p^r)=ν d,p^f

≤ν(d,p). (2.10)

Theorem2.12[7, Thm. 6.7]. Letw(a,b)∈Ᏺ(a,b)be ap-regular recurrence sat- isfying the conditions of Hypothesis 2.9 and assume thatr > f. Letw(a,b)∈Ᏺ(a,b) and assume thatw(a,b)is amotofw(a,b)modulop. Choosemmaximal such that 1≤m≤eandw(a,b)is amotofw(a,b)modulop^m.

(a)Ifr ≤e+mor ife=m, then there exist at leastsdistinctp-regular residuesd modulop^r for which

νw(d,p^r)≥p^r−r∗. (2.11)

(b)If1≤m < eandr > e+m, then there exist at leastp^r−r∗−ms distinctp-regular residuesdmodulop^r for which

νw(d,p^r)≥p^m. (2.12)

Theorem2.13[7, Thm. 6.8]. Suppose thatpD(a,b)andord_p2e(b)|p−1. Then v(a,b)satisfies the conditions of Hypothesis 2.9 forn=0. In particular, Hypothesis 2.9 is true whenn=0andb= ±1.

Theorem2.14[7, Thm. 6.9]. Suppose thatw(a,b)∈Ᏺ(a,b)is a mot ofu(a,b) modulop^e∗. Suppose thatp|d. Then

ν(d,p^r)=





0 ifp^e∗d,

p^e∗−f∗s ifp^e∗|d. (2.13) The statement and proof of Theorem 3.3 use an integerγ whose definition first appeared in [7]. The parameterγplays a prominent role in the statement and proof of Theorem 2.15.

Theorem2.15[21, Thm. 6.1]. Suppose thate >1and thatw(a,b)∈Ᏺ(a,b)is a motof u(a,b)modulo p, but not a motofu(a,b)modulop^e∗. Choosemmaximal

such thatw(a,b)is amotofu(a,b)modulop^mandnminimal such thatp|wn. Ifp|dandν(d,p^r) >0, thenp^md. Furthermore,

ν(d,p^r)=











p^r−f∗ ifm < r≤min(m+f ,e),

p^m ife−m > f and min(m+f ,e) < r , p^e−f ife−m < f and min(m+f ,e) < r .

(2.14)

Ife−m=f, then

ordp^2e−2m

wn+h(p^e)/p^m

wn/p^m =p^γs (2.15)

for some integerγ satisfying0≤γ≤f, and all possibilities forγ occur. Ifγ≥1and r > e, then

ν(d,p^r)=pmin(r−f ,e−γ), (2.16) and, ifγ=0andr >2e−m, then there exists a residuedsuch thatp^mdand

ν(d,p^r)≥p^r−f−(r−2e+m)/2=p^{r−f−(r−e−f )/2}. (2.17)

3. Principal results. Throughout this section, we assume thatw(a,b)∈Ᏺ(a,b)is a nondegenerate, regular second-order recurrence. We fix a primep, assumed to be odd unless otherwise noted.

3.1. Uniform distribution. We begin with the classical result on uniform distribu- tion of second-order recurrences of Bumby [1] and Webb and Long [22]. The sequences described in this theorem areuniformly distributedmodulo all powers of the primep.

Since the frequencysis independent of the power ofp, these sequences arep-stable.

Theorem3.1(Bumby [1], Webb and Long [22]). Letw(a,b)be a second-order re- currence and p a prime, not necessarily odd. Assume that the following conditions hold:

(a) p|D;

(b) pabifp≥3;

(c) ifp=2, thena≡0 (mod 2),b≡1 (mod 2), andw0+w1≡1(mod 2);

(d) ifp≥3, thenp2w1−aw0;

(e) if p = 2 and r ≥ 2, then a≡ 2 (mod 4), b ≡ 1(mod 4), and w0+w1 ≡ 1 (mod 2);

(f) ifp=3andr≥2, thena²≡b (mod 9).

Thenw(a,b)isp-stable,ι(p)=1, andΩ(p^r)= {s}for allr≥1.

Proof. All parts of this theorem are proved in [1] and [22].

3.2. The conditione > f. To a great degree, thep-stability of regular sequences in the family Ᏺ(a,b) can be characterized by the relationship between the global parameterseand f. We recall that, in any case,e≥f. In this section, we consider those two-term recurrence sequences for whiche > f. We characterize thep-stability

of most of the sequences satisfying this condition: The only sequences omitted lie in the samep^e-block asu(a,b).

In the first theorem, we show that such recurrences arep-stable when they contain nop-singular terms.

Theorem3.2. Suppose thate > f. Ifw(a,b)isnotamotofu(a,b)modulop, then w(a,b)has nop-singular terms and isp-stable with1≤ι(p)≤f.

Proof. SinceZ/(p)is a field, it is clear that only onep-block contains sequences with p-singular terms. Sinceu(a,b)certainly has p-singular terms, it follows that w(a,b)has nop-singular terms.

On the other hand, by Theorem 2.8, ifdisp-regular andr≥f, then ν(d,p^r)=ν

d,p^f

≤ν(d,p). (3.1)

Consequently, ifr≥f, thenΩw(p^r)=Ωw(p^f), and hencew(a,b)isp-stable with ι(p)≤f.

Next, we turn to recurrences that containp-singular terms. As observed in the pre- vious proof, these sequences lie in the samep-block asu(a,b). Ifw(a,b)is in the samep-block asu(a,b), but not the samep^e-block, then there is a maximal positive integermsuch that 1≤m < e, andw(a,b)lies in the same block asu(a,b)modulo p^m. In Theorem 3.3, we characterize the stability of these sequences in terms of the relation ofmtoe−f. Note, in particular, that in (d) we exhibit a class of sequences that fail to bep-stable.

Theorem3.3. Suppose thate > f. Assume thatw(a,b)is amotofu(a,b)modulo p but not modulop^e, and choosemmaximal such thatw(a,b)is a motofu(a,b) modulop^m. Ifm=e−f, then defineγas in Theorem 2.15. Then we have the following stability criteria forw(a,b)∈Ᏺ(a,b).

(a)Ifm < e−f, thenw(a,b)isp-stable andι(p)≤m+f. (b)Ifm > e−f, thenw(a,b)isp-stable andι(p)≤e.

(c)Ifm=e−fandγ≥1, thenw(a,b)isp-stable andι(p)≤e+f−γ.

(d)Ifm=e−f andγ=0, thenw(a,b)is notp-stable.

Note. The definition and existence of the parameterγthat appears in (c) and (d) is a consequence of Theorem 2.15. The reader may consult [7] and [21] for additional details.

Proof. First, suppose thatpd. Then, by Theorem 2.8, ν(d,p^r)=ν

d,p^f

≤ν(d,p) (3.2)

whenr≥f. In particular, (3.2) holds whenr≥m+f, whenr≥e, and, sinceγ≤f, also whenr≥e+f−γ.

Next, suppose thatp|d and ν(d,p^r) >0. Sincee > f≥1, we can easily apply Theorem 2.15 to prove (a), (b), and (c).

(a) Ifm < e−f, then Theorem 2.15 implies that

ν(d,p^r)=p^m (3.3)

whenr≥m+f. Clearly, (3.2) and (3.3) yield (a).

(b) Ifm > e−f, then Theorem 2.15 implies that

ν(d,p^r)=p^e−f (3.4)

whenr≥e. Now, (3.2) and (3.4) yield (b).

(c) Ifm=e−f andγ≥1, then Theorem 2.15 implies that

ν(d,p^r)=p^e−γ (3.5)

whenr≥e+f−γ. In this case, (3.2) and (3.5) yield (c).

(d) Finally, assume thatm=e−f andγ=0. By Theorem 2.15, ifr >2e−m, then there exists a residuedsuch thatp^m|dfor which

ν(d,p^r)≥pr−f−(r−2e+m)/2. (3.6) Clearly (3.6) implies that max(Ωw(p^r))is unbounded as a function ofr, and hence w(a,b)is notp-stable.

3.3. The conditione=f. In the remainder of this paper, we consider two-term recurrence sequences for whiche=f. These sequences have a more intricate structure and are less easy to handle than those for whiche > f.

The two results in this section classify the stability of some of these sequences under the additional hypothesis that the discriminantDis not a quadratic residue modulo p. In particular, we identify onep^e-block whose sequences all fail to bep-stable and we show that those sequences that fail to bep-stable lie in a uniquep-block.

Theorem3.4. Suppose that _D

p

= −1 ande=f. Then there exists ap-regular recurrencew(a,b)that isnotp-stable. Furthermore, we have the following stability criteria forw(a,b)∈Ᏺ(a,b).

(a)Ifw(a,b)is amotofw(a,b)modulop^e, thenw(a,b)is notp-stable.

(b)Ifw(a,b)isnotamotofw(a,b)modulopand alsonotamotofu(a,b)modulo p, thenw(a,b)isp-stable with1≤ι(p)≤e.

(c)Suppose thatw(a,b)is notamot ofw(a,b)modulo p, but thatw(a,b)is a motofu(a,b)modulop. Choosemmaximal such thatm≤eandw(a,b)is amotof u(a,b)modulop^m. Thenw(a,b)isp-stable with1≤ι(p)≤e.

Proof. Since_D

p

= −1, Theorem 2.10 implies that there is a recurrencew(a,b) that satisfies Hypothesis 2.9. Suppose that r≥2e. By the definition of r^∗ given in Section 2.8, r^∗ = r /2, and r − r^∗ = r /2 ≥ (r − 1)/2. Since r > f, Theorem 2.12(a) (with ein place ofm) implies that there are at least s distinctp- regular residuesdfor whichνw(d,p^r)≥p^r−r∗≥p^(r−1)/2. In particular, max(Ωw(p^r)) is unbounded as a function ofr, and it follows thatw(a,b)is notp-stable.

(a) Assume thatw(a,b)is in the same p^e-block as w(a,b). Then we can apply Theorem 2.12(a) (withein place ofm) in the same fashion as forw(a,b)itself, and it follows thatw(a,b)is notp-stable.

(b) Assume thatw(a,b)lies in ap-block different from those that containw(a,b) andu(a,b). As in the proof of Theorem 3.2, [7, Cor. 2.17] implies thatw(a,b)has no p-singular terms. But then, by Theorem 2.11, for all residuesd,

ν(d,p^r)=ν d,p^f

≤ν(d,p) (3.7)

whenr≥f=e. It follows thatw(a,b)isp-stable with 1≤ι(p)≤e.

(c) Sincew(a,b)lies in a differentp-block thanw(a,b), Theorem 2.11 implies that for allp-regular residuesd,

ν(d,p^r)=ν d,p^f

≤ν(d,p) (3.8)

whenr≥f=e.

To handle thep-singular residues, we consider separately the cases thatm < eand m=e.

First, suppose thatm < e. Clearlym≥1, so in this case we know thate >1. There- fore, we can apply Theorem 2.15. Sincee=f, it follows thatm > e−f. As in the proof of Theorem 3.3(b), ifdisp-singular, then

ν(d,p^r)=p^e−f=1 (3.9)

when r ≥e. Thus, in this case, (3.8) and (3.9) imply that w(a,b) is p-stable with 1≤ι(p)≤e.

Now, suppose thatm=e. Then, w(a,b)is a mot of u(a,b)modulo p^e and we apply Theorem 2.14. Suppose thatr≥e. Then, by the definitions ofe^∗andf^∗given in Section 2.8,e^∗=e=f^∗, and hence, ifdisp-singular, then

ν(d,p^r)=



0 ifp^ed,

s ifp^e|d. (3.10)

In particular,ν(d,p^r)is independent ofr. Now (3.8) and (3.10) imply thatw(a,b)is p-stable with 1≤ι(p)≤e.

In Theorem 3.5, we identify familiesᏲ(a,b)with the property that everyp-regular sequence inᏲ(a,b)fails to bep-stable.

Theorem3.5. Suppose that_D

p

= −1,e=1, andh(p)=p+1. Then_b

p

= −1, and everyp-regular recurrencew(a,b)∈Ᏺ(a,b)isnotp-stable.

Furthermore, given any integerbsuch that_b p

= −1, there exist integersaandb withb≡b (modp)such that_D

p

= −1,h(p)=p+1, ande=1.

Proof. Since_D

p

= −1 andh(p)=p+1, [7, Thm. 2.14], which provides an explicit count of regularp-blocks, implies that there is only one regularp-block. Since 1=e≥ f, it follows thate=f. Consequently, Theorem 3.4 implies that this uniquep-regular p-block contains a sequence that is notp-stable. Now, Theorem 3.4(a) implies that everyp-regular sequence in Ᏺ(a,b) fails to bep-stable. Finally, D. H. Lehmer [13, p. 441] has shown that if _b

p

=1, then h(p)| p−_D

p

/2. Since, by hypothesis, h(p)=p+1, we conclude that_b

p

= −1.

Now, suppose that_b

p

= −1. By [19, Thm. 4], there exists a p-regular recurrence u(a,b)such that_D

p

= −1 andh(p)=p+1. Ife=1, we are done. Suppose instead thate >1.

Letαandβbe the characteristic roots ofu(a,b)andP a prime ideal lying overp in the algebraic number fieldQ(α,β). Since_D

p

= −1,pis unramified. Moreover, the

characteristic polynomial is irreducible overQ(α,β)/P and

α−β≡0 (modP). (3.11)

Since the Frobenius automorphism exchanges the rootsαandβ, we also obtain α^p≡β (modP) and pα^p≡pβ (modP²),

β^p≡α (modP) and pβ^p≡pα (modP²). (3.12) Sincee≥1, it follows thath(p²)=h(p)=p+1, and hence, by Lemma 2.4,

α^p+1≡β^p+1 (modP²). (3.13)

Now, consider the new sequenceu(a,b)with characteristic rootsα=α+pand β=β+pand satisfying

a=α+β=(α+p)+(β+p)=α+β+2p=a+2p≡a (modp),

b=αβ=(α+p)(β+p)=αβ+(α+β)p+p²=b+ap+p²≡b (modp). (3.14) Sincea≡a (modp)and b≡b (modp), we know that hu(a,b)(p)=p+1, and hence, by Lemma 2.4,

(α+p)^p+1−(β+p)^p+1≡0 (modP). (3.15) By the binomial theorem,

(α+p)^p+1≡α^p+1+(p+1)pα^p≡α^p+1+pα^p (modP²),

(β+p)^p+1≡β^p+1+(p+1)pβ^p≡β^p+1+pβ^p (modP²). (3.16) Thus, by (3.11), (3.12), and (3.13),

(α+p)^p+1−(β+p)^p+1≡(α^p+1+pα^p)−(β^p+1+pβ^p) (modP²)

≡pα^p−pβ^p (modP²)

≡pβ−pα (modP²)

≡p(β−α) (modP²)

≡0 (modP²).

(3.17)

Consequently, hu(a,b)(p²) > hu(a,b)(p), and hence e=1. It now follows that the sequenceu(a,b)satisfies the requirements of the theorem.

3.4. The condition ord_p^2e(b)|p−1. In this section, we consider sequences for which ordp^2e(b)|p−1 andpD. Note that, by Theorems 2.10 and 2.13, these se- quences satisfye=f. Thus, the sequences here specialize the condition of the pre- vious section; however, we replace the condition_D

p

= −1 with the less restrictive conditionpD.

Theorem3.6. Suppose that pD andordp^2e(b)|p−1. Thenv(a,b)is not p- stable. Furthermore, we have the following stability criteria forw(a,b)∈Ᏺ(a,b).

(a)Ifw(a,b)is amotofv(a,b)modulop^e, thenw(a,b)isnotp-stable.

(b)Ifw(a,b)isnotamotofv(a,b)modulopandnotamotofu(a,b)modulop, thenw(a,b)isp-stable with1≤ι(p)≤e.

(c)Suppose thatw(a,b)isnotamotofv(a,b)modulop, but thatw(a,b)is amotof u(a,b)modulop. Choosemmaximal such thatm≤eandw(a,b)is amotofu(a,b) modulop^m. Thenw(a,b)isp-stable with1≤ι(p)≤e.

Note. In particular, ifpDand b= ±1, then each sequencew(a,b)∈Ᏺ(a,b) satisfies the hypotheses of Theorem 3.6.

Proof. (a) By Theorem 2.13,v(a,b)satisfies Hypothesis 2.9 forn=0. Suppose thatr > f. Sincew(a,b)is in the samep^e-block asv(a,b), Theorem 2.12(a) implies that there are at leastsdistinctp-regular residuesdmodulop^r for which

νw(d,p^r)≥p^r−r∗. (3.18)

Clearly, this implies that max(Ωw(p^r))is unbounded as a function ofr, and hence w(a,b)is notp-stable.

(b) As in the proof of Theorem 3.2(b), sincew(a,b)lies in a differentp-block than u(a,b), the elements of w(a,b) are all p-regular. As in (a), Theorem 2.13 implies thatv(a,b)satisfies Hypothesis 2.9 forn=0. Thus, Theorem 2.11 implies that the p-regular residuesdmodulop^r satisfy

ν(d,p^r)=ν(d,p^f)≤ν(d,p) (3.19) whenr≥f=e. It follows thatw(a,b)isp-stable with 1≤ι(p)≤e, as desired.

(c) As in (b), thep-regular residuesdmodulop^r satisfy

ν(d,p^r)=ν(d,p^f)≤ν(d,p) (3.20) whenr≥f=e.

As in the proof of Theorem 3.4, to handle thep-singular residues we consider sep- arately the cases thatm < eandm=e.

Ifm < e, we know thate >1 and can apply Theorem 2.15. Sincee=f,p-singular residuesdsatisfy

ν(d,p^r)=p^e−f=1 (3.21) whenr≥e. It follows thatw(a,b)isp-stable with 1≤ι(p)≤e.

Ifm=e, we appeal to Theorem 2.14. Sincew(a,b)is amotofu(a,b)modulop^e ande=f, Theorem 2.14 implies thatp-singular residuesdsatisfy

ν(d,p^r)=



0 ifp^ed,

s ifp^e|d, (3.22)

when r ≥e. In either case, the frequency is independent of r, and it follows that w(a,b)isp-stable with 1≤ι(p)≤e.

Corollary3.7. Suppose thatpD, thatordp^2e(b)|p−1, and that_b

p

=1. Then h(p)|

p−_D

p

/2, and we have the following stability criteria forw(a,b)∈Ᏺ(a,b).

(a)Ifh(p)is odd andw(a,b)is amotofu(a,b)modulop^e, thenw(a,b)isp-stable with1≤ι(p)≤e.

(b)Ifh(p)is even andw(a,b)is amotoft(a,b)modulop, thenw(a,b)isp-stable with1≤ι(p)≤e.

(c)Ifh(p)= p−_D

p

/2ande=1, thenw(a,b)isnotp-stable if and only ifw(a,b) is amotofv(a,b)modulop.

(d)Ifh(p)= p−_D

p

/2, p−_D

p

/2is odd, ande=1, thenw(a,b)isp-stable if and only ifw(a,b)is amotofu(a,b)modulop.

(e)Ifh(p)= p−_D

p

/2, p−_D

p

/2is even, ande=1, thenw(a,b)isp-stable if and only ifw(a,b)is amotoft(a,b)modulop.

Conversely, ifδ= ±1andbis any integer such thatordp^2e(b)|p−1and_b

p

=1, then there exists an integeraand ap-regular recurrencew(a,b)such that_D

p

=δ andh(p)=

p−_D

p

/2.

Proof. The fact thath(p)| p−_D

p

/2 is proven in [13, p. 441].

(a) By Lemma 2.6,w(a,b)is not amotofv(a,b)modulop. Hence (a) follows from Theorem 3.6(c).

(b) We first note that, by definition,t(a,b)is defined whenp is odd,_b

p

=1, and h(p)is even. Moreover,t(a,b) is not amot ofu(a,b)or ofv(a,b). Therefore, (b) follows from Theorem 3.6(b).

(c), (d), (e) By [7, Thm. 2.14], the number ofp-regularp-blocks inᏲ(a,b)is

Treg(p)=

p−_D

p

h(p) =2h(p)

h(p) =2. (3.23)

One of thesep-regular blocks contains the sequencev(a,b). Sincee=1, Theorem 3.6 implies thatw(a,b)is notp-stable if and only ifw(a,b)lies in the samep-block as v(a,b), and (c) follows immediately. Ifh(p)is odd, then the otherp-regularp-block containsu(a,b), while ifh(p)is even, the otherp-regularp-block containst(a,b).

Thus (d) and (e) follow from (a) and (b), respectively.

To prove the partial converse, suppose that ordp^2e(b)|p−1,_b

p

=1, andδ= ±1.

The existence of an integer a and corresponding regular second-order recurrence w(a,b)such that_D

p

=δandh(p)= p−_D

p

/2 follows from [16, Thm. 12(i)] and [19, Thm. 4].

3.5. The conditionb= ±1. In this section, we sketch more detailed results in the case thatb= ±1. These sequences have particular historical interest. Of course, the Fibonacci sequence itself belongs to the family Ᏺ(1,−1). These are the sequences studied by Schinzel in the quintessential work [14], by Somer in [15, 17, 18, 20], and by Jacobson, Carroll, and Somer in [9].

In two theorems, dealing withb=1 andb= −1 in turn, we describe the stability of sequences that belong to the samep^e-blocks asu(a,b),v(a,b), andt(a,b). Since b = ±1, it is clear that ord_p^2e(b)|p−1. Since we also assume thatp D in this section, the theorems here specialize those in the previous section. In particular, as in the previous section, each familyᏲ(a,b)studied here satisfiese=f.

Theorem3.8. Suppose thatb=1andpD.

(a)Ifh(p)is odd andw(a,b)is amotofu(a,b)modulop^e, thenw(a,b)isp-stable

andι(p)=1. Furthermore, eitherλ(p)≡1 (mod 2)orλ(p)≡2(mod 4), and, for all r≥1,

Ω(p^r)=



{0,1} ifλ(p)≡1(mod 2),

{0,2} ifλ(p)≡2(mod 4). (3.24) (b)Ifh(p)is even andw(a,b)is amotoft(a,1)modulop^e, thenw(a,b)isp-stable andι(p)=1. Furthermore,λ(p)≡0(mod 4)andΩ(p^r)= {0,2}for allr≥1.

(c)Ifw(a,b)is amotofv(a,b)modulop^e, thenw(a,b)isnotp-stable.

Proof. (a) Sincew(a,b)is amotofu(a,b)modulop^e, [7, Cor. 2.15] implies that w(a,b)is amotofu(a,b)modulop^r for allr ≥e. Therefore,w(a,b)is amot of u(a,b)modulop^r for allr≥1. Since two sequences in the samep^r-block have the same residue frequencies, we may assume thatw(a,b)=u(a,b).

By hypothesis,h(p)is odd, so Lemma 2.6 implies thatw(a,b)is not amotofv(a,b) modulop. Thus, by Theorem 3.6(c),w(a,b)isp-stable with 1≤ι(p)≤e.

From [15, Thm. 16], we see thatλ(p)≡1 (mod 2)orλ(p)≡2 (mod 4)and

s=





2 whenλ(p)≡1(mod 2),

1 whenλ(p)≡2(mod 4). (3.25)

In the case thatλ(p)≡1(mod 2), [18, Thm. 4] shows thatΩ(p)= {0,1}. Since, as previously observed,e=f, Theorem 2.14 implies that ifr ≥e, then thep-singular residuesdsatisfy

ν(d,p^r)=





0 ifp^ed,

s=1 ifp^e|d. (3.26)

On the other hand, by Theorem 2.11, ifr≥e, then thep-regular residuesdsatisfy ν(d,p^r)=ν(d,p^f)≤ν(d,p). (3.27) Clearly, (3.26) and (3.27) imply thatΩ(p^r)= {0,1}whenr≥e=f. On the other hand, ifr ≤f, then λ(p^r)=λ(p^f)and it is clear thatν(d,p)≥ν(d,p^r). It follows that Ω(p^r)= {0,1}for allr≥1. In particular,ι(p)=1.

In the case thatλ(p)≡2(mod 4), [18, Thm. 5] shows thatΩu(p)= {0,2}. As before, Theorem 2.14 implies that ifr≥e, then thep-singular residuesdsatisfy

ν(d,p^r)=



0 ifp^ed,

s=2 ifp^e|d. (3.28)

On the other hand, thep-regular residuesdcontinue to satisfy (3.27). Moreover, the same symmetry argument used to prove [18, Thm. 5] shows that 1 cannot occur as ν(d,p^r)for ap-regular residued. It now follows from (3.28) and (3.27) thatΩ(p^r)= {0,2}whenr≥e, and, as in the previous paragraph,Ω(p^r)= {0,2}for allr≥1. Once again, we also conclude thatι(p)=1.

(b) Sincew(a,b)is amotoft(a,b)modulop^e, [7, Cor. 2.15] implies thatw(a,b)is amotoft(a,b)modulop^r for allr≥e. Thereforew(a,b)is amotoft(a,b)modulo

p^r for allr ≥1. Since two sequences in the samep^r-block have the same residue frequencies, we may assume thatw(a,b)=t(a,b).

By hypothesis,h(p)is even andw(a,b)is amotoft(a,b)modulop. Consequently, Corollary 3.7(b) implies thatw(a,b)isp-stable with 1≤ι(p)≤e.

By [18, Thm. 3(ii)], λ(p)≡0 (mod 4). By using the technique of [18, Thms. 4-6]

together with the symmetry properties oft(a,b)given in [20, Lem. 5], it is easy to see thats=2 for this sequence,Ω(p)= {0,2}, and that 1 cannot occur asν(d,p^r)for a p-regular residued. The argument can now be completed as in (a).

(c) This follows immediately from Theorem 3.6(a).

Theorem3.9. Suppose thatb= −1andpD.

(a)Ifh(p)is odd andw(a,b)is amotofu(a,b)modulop^e, thenw(a,b)isp-stable.

Furthermore,p≡1 (mod 4)and

(1) ifp=5ande=1, thenι(p)=1, andΩ(p^r)= {2,4}for allr≥1;

(2) ifp=5ande >1, thenι(p)=2, andΩ(p)= {2,4}andΩ(p^r)= {0,2,4}for allr≥2;

(3) ifp >5, thenι(p)=1, andΩ(p^r)= {0,2,4}for allr≥1.

(b)Ifh(p)is even,p≡1 (mod 4), andw(a,b)is amotoft(a,b)modulop, then w(a,b)isp-stable and1≤ι(p)≤e. Furthermore,Ω(p^r)= {0,1},{0,1,2}, or{0,2}

for allr≥1.

(c)Ifw(a,b)is amotofv(a,b)modulop^e, thenw(a,b)isnotp-stable.

Proof. (a) Sincew(a,b)is amotofu(a,b)modulop^eandu(a,b)isp-regular, [7, Cor. 2.15] implies thatw(a,b)is amotofu(a,b)for allr≥e. It follows thatw(a,b) is amotofu(a,b)for allr≥1, and we may assume thatw(a,b)=u(a,b).

By [23, Thm. 4],h(p^r)is odd if and only if bothλ(p^r)≡4 (mod 8)andE(p^r)=4. In particular, sinceh(p)is odd,s=4. Moreover, [15, Lem. 3] implies thatp≡1 (mod 4).

Now, by Euler’s criterion,₋₁

p

=1, and we can apply Corollary 3.7(a) to conclude that w(a,b)isp-stable with 1≤ι(p)≤e. Ifr≥1, the same methods used to prove [17, Thm. 9] can be used to show thatν(d,p)=2 orν(d,p)=4 whenν(d,p^r)=0.

Now, suppose thatp=5 and e=1. Thenι(5)=1, and an explicit computation shows thath(5)is odd if and only ifa≡2 (mod 5)ora≡3(mod 5). In both cases λ(5)=12 andΩ(5)= {2,4}.

Next, suppose thatp=5 ande >1, and lete^∗=min(r ,e). By Theorem 2.14, ifdis p-singular, then, for allr,

ν(d,p^r)=





0 ifp^e∗d,

s=4 ifp^e∗|d. (3.29)

In particular, whenr≥2, we obtainν(p,p^r)=0 andν(0,p^r)=4.

Since, by Lemma 2.6,u(a,b)is not amotofv(a,b), we can also apply Theorem 2.11.

Thus, forp-regular residuesd,

ν(d,p^r)=ν(d,p^f)≤ν(d,p) (3.30) whenr≥f=e. Sinceν(1,5)=2, it follows that 2∈Ω(p^r)for allr≥1. Now,Ω(p^r)= {0,2,4}when r ≥ 2. Since Ω(5)= {2,4} whenever h(5) is odd, we conclude that ι(p)=2.

Finally, suppose thatp >5. Sincep≡1(mod 4), we know thatp >7, and the result is proven in [9].

(b) As in (a), we may assume thatw(a,b)=t(a,b). Sincep≡1(mod 4), Euler’s criterion implies that₋₁

p

=1. Hence, by Corollary 3.7(b),w(a,b)is stable, with 1≤ ι(p)≤e. Using the symmetry properties fort(a,b)modulop given in [20, Lem. 5]

and employing methods similar to those used in the proofs of [17, Thms. 5, 7, and 9], we can show thatΩ(p)= {0,1},{0,1,2}, or{0,2}. Finally, ifr≤f=e, thenν(d,p)≥ ν(d,p^r). It follows thatΩ(p^r)= {0,1},{0,1,2}, or{0,2}for allr≥1.

(c) This follows immediately from Theorem 3.6(a).

References

[1] R. T. Bumby,A distribution property for linear recurrence of the second order, Proc. Amer.

Math. Soc.50(1975), 101–106. MR 51 5475. Zbl 318.10006.

[2] W. Carlip and E. Jacobson,A criterion for stability of two-term recurrence sequences mod- ulo2^k, Finite Fields Appl.2(1996), no. 4, 369–406. MR 97h:11012. Zbl 924.11007.

[3] ,On the stability of certain Lucas sequences modulo2^k, Fibonacci Quart.34(1996), no. 4, 298–305. MR 97c:11026. Zbl 866.11009.

[4] ,Unbounded stability of two-term recurrence sequences modulo2^k, Acta Arith.74 (1996), no. 4, 329–346. MR 97b:11021. Zbl 838.11009.

[5] ,Stability of two-terms recurrence sequences with even parameter, Finite Fields Appl.3(1997), no. 1, 70–83. MR 98b:11014. Zbl 905.11011.

[6] W. Carlip, E. Jacobson, and L. Somer,A criterion for stability of two-term recurrence se- quences modulo odd primes, Application of Fibonacci Numbers (G. E. Bergum et al., ed.), vol. 7, Kluwer Acad. Publ., Dordrecht, 1998, Proceedings of the 7th inter- national research conference on Fibonacci numbers and their applications, Graz, Austria, July 15–19, 1996, pp. 49–60. CMP 1 638 430. Zbl 921.11012.

[7] W. Carlip and L. Somer,Bounds for frequencies of residues of regular second order re- currences modulop^r, Number Theory in Progress (Kálmán Gy˝ory, Henryk Iwaniec, and Jerzy Urbanowicz, eds.), Walter de Gruyter, Berlin, 1999, Proceedings of the International Conference on Number Theory held in Honor of the 60th Birth- day of Andrzej Schinzel (Zakopane, Poland, 1997), pp. 691–719. CMP 1 689 539.

Zbl 990.56684.

[8] R. D. Carmichael,On the numerical factors of the arithmetic formsαⁿ±βⁿ, Ann. of Math.

(2)15(1913–1914), no. 1/4, 30–70.

[9] D. Carroll, E. Jacobson, and L. Somer,Distribution of two-term recurrence sequences mod p^e, Fibonacci Quart.32(1994), no. 3, 260–265. MR 95f:11010. Zbl 809.11011.

[10] E. Jacobson,Almost uniform distribution of the Fibonacci sequence, Fibonacci Quart.27 (1989), no. 4, 335–337. MR 90h:11015. Zbl 681.10005.

[11] ,A brief survey on distribution questions for second order linear recurrences, Num- ber Theory (Banff, AB, 1988) (Berlin), de Gruyter, 1990, pp. 249–254. MR 92e:11015.

Zbl 694.10012.

[12] ,Distribution of the Fibonacci numbers mod2^k, Fibonacci Quart.30(1992), no. 3, 211–215. MR 93f:11014. Zbl 760.11007.

[13] D. H. Lehmer,An extended theory of Lucas’ functions, Ann. of Math. (2)31(1930), no. 3, 419–448.

[14] A. Schinzel,Special Lucas sequences, including the Fibonacci sequence, modulo a prime, A Tribute to Paul Erd˝os (Cambridge), Cambridge Univ. Press, 1990, pp. 349–357.

MR 92f:11029. Zbl 716.11009.

[15] L. Somer,The divisibility properties of primary Lucas recurrences with respect to primes, Fibonacci Quart.18(1980), no. 4, 316–334. MR 82g:10023. Zbl 441.10007.

[16] ,Possible periods of primary Fibonacci-like sequences with respect to a fixed odd prime, Fibonacci Quart.20(1982), no. 4, 311–333. MR 84g:10022. Zbl 498.10010.

[17] ,Distribution of residues of certain second-order linear recurrences modulop, Ap- plications of Fibonacci Numbers (Dordrecht) (G. E. Bergum et al., ed.), vol. 3, Kluwer Acad. Publ., 1990, Proceedings of the Third International Conference on Fibonacci Numbers and their Applications held at the University of Pisa, Pisa, July 25–29, 1988, pp. 311–324. MR 92j:11019. Zbl 722.11008.

[18] ,Distribution of residues of certain second-order linear recurrences modulop–II, Fibonacci Quart.29(1991), no. 1, 72–78. MR 92k:11016. Zbl 728.11010.

[19] ,Periodicity properties ofkth order linear recurrences with irreducible character- istic polynomial over a finite field, Finite Fields, Coding Theory, and Advances in Communications and Computing (Las Vegas, NV, 1991) (New York), Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, 1993, pp. 195–207. MR 94c:11014.

Zbl 790.11013.

[20] ,Upper bounds for frequencies of elements in second-order recurrences over a finite field, Applications of Fibonacci Numbers (Dordrecht) (G. E. Bergum et al., ed.), vol. 5, Kluwer Acad. Publ., 1993, Proceedings of the Fifth International Conference on Fibonacci Numbers and their Applications held at the University of St. Andrews, St. Andrews, July 20–24, 1992, pp. 527–546. MR 95c:11021. Zbl 805.11022.

[21] L. Somer and W. Carlip,Bounds for frequencies of residues of second order recurrences modulop^r, preprint.

[22] W. A. Webb and C. T. Long,Distribution modulop^hof the general linear second order recurrence, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. (8)58 (1975), no. 2, 92–100. MR 54 7396. Zbl 325.10008.

[23] O. Wyler, On second-order recurrences, Amer. Math. Monthly 72 (1965), 500–506.

MR 35#6641. Zbl 151.02503.

Somer: Department of Mathematics, Catholic University of America, Washington, DC20064, USA

Carlip: Department of Mathematics, Duke University, Durham, North Carolina 27708, USA

Journal of Applied Mathematics and Decision Sciences

Special Issue on

Decision Support for Intermodal Transport

Call for Papers

Intermodal transport refers to the movement of goods in a single loading unit which uses successive various modes of transport (road, rail, water) without handling the goods during mode transfers. Intermodal transport has become an important policy issue, mainly because it is considered to be one of the means to lower the congestion caused by single-mode road transport and to be more environmentally friendly than the single-mode road transport. Both consider- ations have been followed by an increase in attention toward intermodal freight transportation research.

Various intermodal freight transport decision problems are in demand of mathematical models of supporting them.

As the intermodal transport system is more complex than a single-mode system, this fact offers interesting and challeng- ing opportunities to modelers in applied mathematics. This special issue aims to fill in some gaps in the research agenda of decision-making in intermodal transport.

The mathematical models may be of the optimization type or of the evaluation type to gain an insight in intermodal operations. The mathematical models aim to support deci- sions on the strategic, tactical, and operational levels. The decision-makers belong to the various players in the inter- modal transport world, namely, drayage operators, terminal operators, network operators, or intermodal operators.

Topics of relevance to this type of decision-making both in time horizon as in terms of operators are:

•

Intermodal terminal design

•

Infrastructure network configuration

•

Location of terminals

•

Cooperation between drayage companies

•

Allocation of shippers/receivers to a terminal

•

Pricing strategies

•

Capacity levels of equipment and labour

•

Operational routines and lay-out structure

•

Redistribution of load units, railcars, barges, and so forth

•

Scheduling of trips or jobs

•

Allocation of capacity to jobs

•

Loading orders

•

Selection of routing and service

Before submission authors should carefully read over the journal’s Author Guidelines, which are located at

Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking Sys- tem at

timetable:

Manuscript Due June 1, 2009 First Round of Reviews September 1, 2009 Publication Date December 1, 2009

Lead Guest Editor

Gerrit K. Janssens,

Transportation Research Institute (IMOB), Hasselt University, Agoralaan, Building D, 3590 Diepenbeek (Hasselt), Belgium;

Guest Editor

Cathy Macharis,

Department of Mathematics, Operational Research, Statistics and Information for Systems (MOSI), Transport and Logistics Research Group, Management School, Vrije Universiteit Brussel, Pleinlaan 2, 1050 Brussel, Belgium;

Hindawi Publishing Corporation http://www.hindawi.com