On some oscillating sums
Abstract
This paper deals with the sums S α (n)=∑ j=1 n (-1) ⌊jα⌋ where α is any real number. The interest in these sums was initiated by a problem proposed by H. D. Ruderman [Problem 6105, Am. Math. Mon. 83, 573 (1977)] and solved (among other) by D. Borwein [Solution to problem no. 6105. Am. Math. Mon. 85, 207–208 (1978)] that the series ∑ n=1 ∞ (-1) ⌊n2⌋ /n converges. It quickly turned out that the behavior of such sums is intimately connected with the simple continued fraction expansions α=[a 0 ;a 1 ,a 2 ,⋯] and β=α/2=[b 0 ;b 1 ,b 2 ,⋯]. E.g., P. Bundschuh [Arch. Math. 29, 518–523 (1977; Zbl 0365.10025)] proved that the series ∑ n=1 ∞ (-1) ⌊nα⌋ /n converges for numbers α with bounded b i of β=α/2=[b 0 ;b 1 ,b 2 ,⋯]. J. Schoissengeier [Unif. Distrib. Theory 2, 107–113 (2007; Zbl 1153.11033)] proved that the series ∑ n=1 ∞ (-1) ⌊nα⌋ /n and ∑ k=0,2∤q k ∞ (-1) k (logb k+1 )/q k converge simultaneously. Here p k q k are convergents of β=α/2=[b 0 ;b 1 ,b 2 ,⋯]. A. E. Brouwer and J. van de Lune [Math. Centrum, Amsterdam, Afd. zuivere Wisk. ZW 90/76, 16 p. (1976; Zbl 0359.10029)] have shown that S α (n)≥0 for all n if and only if the partial quotients a 2i of α=[a 0 ;a 1 ,a 2 ,⋯] are even for all i≥0. In this paper the authors study the sequence of those n for which S α (n) assumes a value for the first time, i.e., is larger/smaller than ever before, and it is denoted by t 0 =0,t 1 ,t 2 ,⋯. They show that for any irrational α the sum S α (n) is not bounded, so that the corresponding sequence t k actually is an infinite sequence. In a main result the authors prove that for every j≥1 there is an index k such that t j -t j-1 =Q k , where P k /Q k is a certain convergent of α=[a 0 ;a 1 ,a 2 ,⋯]. They also give explicit formulas for the numbers t j and the corresponding Q k . For quadratic irrational α the authors translate this into an algorithm which computes the sequence t n and S α (t n ) outputs [a 0 ;a 1 ,a 2 ,⋯]. In the final Part the authors summarize their open problems, including that t k is recurrent and the sequence sign(S(t k )) is to be purely periodic. In the Appendix the authors extend a fast algorithm in R. Fokkink, W. Fokkink and J. van de Lune [Nieuw Arch. Wiskd., IV. Ser. 12, 13–18 (1994; Zbl 0826.11061)] for the computation of S α (n) for any irrational α and for very large n in terms of β=α/2=[b 0 ;b 1 ,b 2 ,⋯]. E.g., S 2 (10 1000 )=-10, S 2 (10 10000 )=166, S π (10 10000 )=11726.
Full text
Uni o m Dis ibu ion Theo y 3(2008), no.1, 35–72
uni o m
dis ibu ion
heo y
ON SOME OSCILLATING SUMS
J. A ias de Reyna∗— J. an de Lune
ABSTRACT. This pape deals wi h a ious p ope ies ( heo e ical as well as
compu a ional) o he sums Sα(n) = Pn
j=1(−1)bjαcwhe e αis any eal numbe
(mos ly a posi i e eal quad a ic).
Communica ed by Michael D mo a
In oduc ion
This pape deals wi h he sums
Sα(n) =
n
X
j=1
(−1)bjαc
whe e αis any eal numbe . I he alue o αis clea om he con ex we will
simply w i e S(n) ins ead o Sα(n).
Appa en ly he in e es in hese sums was ini ia ed (in 1976) by an unsol ed
p oblem p oposed by H. D. Rude man [3]: P o e ha he se ies
∞
X
n=1
(−1)bn√2c
n
con e ges and es ima e i s alue. Indeed, when applying Abel-summa ion (sum-
ma ion by pa s) o his se ies ou sum (wi h α=√2) eme ges na u ally.
This ac is e lec ed in he 1978 issue o he Ame . Ma h. Mon hly, whe e
one inds a solu ion by D. Bo wein [7] (wi h an edi o ial e e ence o 11 o he
solu ions).
Many gene aliza ions we e p esen ed, one o hem being: I αis any eal
quad a ic i a ional hen he se ies P∞
n=1(−1)bnαc/nscon e ges o e e y s > 0.
Fu he solu ions may be ound in Bundschuh [6] and an de Lune [4].
2000 Ma h em a i c s S u b j e c C l a s s i i c a i o n: 11K31, 11J70.
Ke yw o ds: Exponen ial sum, con inued ac ion, quad a ic i a ional, algo i hm.
∗Suppo ed by g an MTM2006-05622.
35
J. ARIAS DE REYNA — J. VAN DE LUNE
The las ela ed publica ion seems o be Schoissengeie [17], whe e i is
p o ed ha i he egula con inued ac ion expansion o β=α/2 is
{b0;b1, b2, . . . }wi h con e gen s pk
qk hen he se ies P∞
n=1 (−1)bnαc/n con e ges
i and only i he se ies
∞
X
k= 0,2-qk
(−1)klog bk+1
qk
con e ges.
Ou sums S(n) a e also in e es ing in hemsel es as may be seen om he
ollowing example: Fo α=√2 we compu e S(n) o n= 1, 2, 3, . . . , and
keep ack o hose n o which S(n) assumes a alue o he i s ime (i.e., is
la ge /smalle han e e be o e). He e (and in he sequel) we de ine S(0) = 0.
The sequence o hese n’s ( he eco d-holde s) will be deno ed by 1, 2, 3, . . . .
We ound
→1 3 8 20 49 119 288 696 1681 4059 9800
S→ −11−2 2 −3 3 −4 4 −5 5 −6
In making ou compu a ions we obse e ha k+1 = 2 k+ k−1+ 1 o all
k≥1. He e (and in he sequel) we de ine 0= 0. Also, he sequence sign(S( k))
appea s o be pu ely pe iodic.
In his pape we will show ha simila esul s a e ue o all eal quad a ic
i a ionals.
We will see ha he beha io o ou sums is in ima ely connec ed wi h he
egula con inued ac ion expansions α={a0;a1, a2, a3, . . . }and β=α/2 =
{b0;b1, b2, b3, . . . , }. In his ein B ouwe and an de Lune [5] ha e shown
ha S(n)≥0 o all ni and only i he pa ial quo ien s a2ia e e en o all
i≥0. In Fokkink, Fokkink and an de Lune [9] we ind a desc ip ion o
a as algo i hm o he compu a ion o S(n) o ( e y) la ge nin e ms o he
egula con inued ac ion expansion o β=α/2. Fo an explici p og am we
e e o he Appendix. We jus men ion ha by means o his p og am we easily
ound ha
S√2(101000) = −10, S√2(1010000) = 166, Sπ(1010000) = 11726.
A closely ela ed (bu somewha less gene al) algo i hm is gi en in an in e -
es ing pape by O’B yan , Reznick and Se binowska [15].
I will u n ou ha he sequence (−1)bjαcexhibi s a ious symme ies. We
will de e mine hese explici ly in e ms o he con e gen s o α.
We will also show ha o any eal i a ional α he sum S(n) is no bounded,
so ha he co esponding sequence o eco d-holde s kac ually is an in ini e
sequence.
36
ON SOME OSCILLATING SUMS
In addi ion we will p o e ha o e e y j≥1 he e is an index ksuch ha
j− j−1=Qk, whe e Qkis he denomina o o a ce ain egula con inued
ac ion app oximan o α, as de ined in Sec ion 2. We will ansla e his in o
an algo i hm which (gi en su icien ly many ini ial con e gen s o α) compu es
he en i e sequence o eco d-holde s. We will also gi e explici o mulae o he
numbe s jand he co esponding Qk.
Finally we will s udy he unc ion H(α) = Λ(1 −α), whe e
Λ(α) = lim sup
n→∞
Sα(n)
log n.
I will u n ou ha his unc ion is ini e o all eal αwi h bounded pa ial
quo ien s, and, in a ce ain sense, is a modula unc ion since
H(α+ 2) = H(α), H³−1
α´=H(α).
We will also p esen a as algo i hm o he compu a ion o H(α).
In Sec ion 6 we sol e he p oblem o he o de o supn≤NSα(n) o almos
all eal α(see Theo em 29). This o de is simila o ha o supn≤NnD∗
n(jα),
whe e D∗
nis he disc epancy o he sequence {jα}. We hink ha ou p oo o
he lowe bound o (41) migh e y well be he mos s aigh o wa d.
In an Appendix we p esen a as implemen a ion o he FFL-algo i hm
(al eady implici ly desc ibed in FFL [9]) o compu e Sα(n) o any i a ional
eal α.
1. P elimina y esul s
We begin wi h some well known ac s.
Lemma
1
.
We ha e
x∈Rand n∈Z=⇒ bn+xc=n+bxc(1)
x∈R Z =⇒ bxc+b−xc=−1.(2)
α∈Rand n≥0 =⇒Sα+2(n) = Sα(n) (3)
α∈R Z =⇒S−α(n) = −Sα(n).(4)
In he sequel we will always assume ha αis eal, and ha all con inued ac-
ions a e egula . This also applies o ou p og ams (which ha e been designed
p ima ily o eal quad a ic i a ionals).
In case α=p
q, wi h (p, q) = 1, is a ional i is easily seen ha he sequence
S(n) is (1) pe iodic (and hence bounded) wi h pe iod 2qi pis odd and (2)
37
J. ARIAS DE REYNA — J. VAN DE LUNE
unbounded (o ue o de n) i pis e en. The e o e, we will es ic ou sel es
om now on o i a ional eal α. In iew o Lemma 1 we may, wi hou loss o
gene ali y, e en es ic ou sel es o 0 < α < 1.
I will u n ou ha he p ope ies o S(n) hea ily depend on he egula con-
inued ac ion expansion {a0;a1, a2, . . . }o α, in pa icula on i s con e gen s
P−2
Q−2
=0
1,P−1
Q−1
=1
0,Pj
Qj
={a0;a1, . . . , aj},(j≥0) (5)
which sa is y he ela ions
Pj+1 =aj+1Pj+Pj−1, Qj+1 =aj+1Qj+Qj−1,(j≥ −1) (6)
and
(Pj, Qj) = 1 (j≥ −2), PjQj−1−QjPj−1= (−1)j−1,(j≥ −1).(7)
I an+1 ≥2 we will also make use o median s. These a e he i educible
ac ions P/Q de ined by
P
Q=hPn+Pn−1
hQn+Qn−1
,(n≥0, h = 1,2, . . . , an+1 −1).
Fo hese ac ions we ha e PQn−PnQ= (−1)n, and we say ha Pn/Qnis he
con e gen nex o he median P/Q. No e ha αalways lies s ic ly be ween
P/Q and he con e gen nex o P/Q.
Jus o he sake o easy e e ence we s a e he ollowing known lemma (see
[11, Chap e VII, Exe cise 13]).
Lemma
2
.
I a
b<c
dwi h band d > 0and cb −ad = 1, hen e e y ac ion m
n
wi h n > 0and a
b<m
n<c
d
sa is ies n≥b+d.
Lemma
3
.
Le P
Q=hPn+1+Pn
hQn+1+Qn, wi h 0≤h < an+2, be a median o a con e gen
o α.
I 1≤m < Q +Qn+1, wi h Q-m, hen
bmαc=jmP
Qk.(8)
In pa icula his is ue o 1≤m < Q.
P o o . Suppose he asse ion o he Lemma is alse. Then we can ind an
in ege kbe ween mα and mP/Q, so ha k/m lies s ic ly be ween αand P/Q,
and is no equal o hese ex emes. (Indeed k/m 6=αsince αis i a ional and
k/m 6=P/Q since P/Q is in lowes e ms and by hypo hesis Q-m.) Since α
38
ON SOME OSCILLATING SUMS
lies be ween Pn+1/Qn+1 and P/Q, i ollows ha k/m is lying s ic ly be ween
P/Q and Pn+1/Qn+1,
Now obse e ha
P
Q−Pn+1
Qn+1
=PnQn+1 −QnPn+1
QQn+1
=−(−1)n
QQn+1
(9)
so ha , by Lemma 2, we would ha e m>Q+Qn+1, which con adic s ou
hypo hesis. ¤
Lemma
4
.
Le P
Q=hPn+1+Pn
hQn+1+Qn, wi h 0≤h < an+2, be a median o a con e gen
o α. Then
(−1)bQαc= (−1)n+P.(10)
P o o . As in he p oo o he p e ious Lemma, αlies be ween he ac ions
P/Q and Pn+1/Qn+1. By a compu a ion as in (9) we ha e
¯¯¯
P
Q−α¯¯¯<¯¯¯
P
Q−Pn+1
Qn+1 ¯¯¯=1
QQn+1
.
Fo n≥0 he wo numbe s Qand Qn+1 a e ≥1, so ha |Qα −P|< Q−1
n+1 ≤1.
I ollows ha bQαc=Pi Qα > P, and ha bQαc=P−1 i Qα < P. Bu ,
by he heo y o con inued ac ions he i s case happens when nis e en, and
he second when nis odd. Hence, (10) is ue in bo h cases. ¤
The ollowing heo em shows he undamen al connec ion be ween he sums
Sα(n) and he con e gen s o α.
P oposi ion
5
.
Le αbe any i a ional eal numbe , and Pn
Qnwi h n≥0one
o i s con e gen s. Le Qn≤m<Qn+Qn+1 and pu m=hQn+ wi h
0≤ < Qn. Then
bmαc=
hPn+b αci 6= 0,
hPni = 0 and nis e en,
hPn−1i = 0 and nis odd.
(11)
P o o . I 6= 0 hen Qn-mand Qn- . By Lemma 3 we ha e
bmαc=jmPn
Qnk=jhPn+ Pn
Qnk=hPn+j Pn
Qnk=hPn+b αc.
I = 0 hen m=hQn. Also, mα lies be ween he wo numbe s mPn/Qn
and mPn+1/Qn+1, and he dis ance be ween hese wo numbe s is
¯¯¯mPn
Qn−mPn+1
Qn+1 ¯¯¯=m
QnQn+1 ≤1.
39
J. ARIAS DE REYNA — J. VAN DE LUNE
(Fo he las inequali y obse e ha always 1 ≤Qn≤Qn+1. So QnQn+1 ≥
Qn+Qn+1 > m, unless Qn= 1. In his case Qn= 1 ≤m < 1 + Qn+1 and he
inequali y ollows.)
When nis e en we ha e
mPn
Qn
=hPn< mα < m Pn+1
Qn+1 ≤1 + hPn
and i ollows ha bmαc=hPn.
When nis odd we ha e
mPn
Qn
=hPn> mα > m Pn+1
Qn+1 ≥hPn−1.
Thus, in his case we ge bmαc=hPn−1, and he p oo o (11) is comple e. ¤
Co olla y
6
.
Le αbe any i a ional eal numbe , and Pn
Qnwi h n≥0one
o i s con e gen s. Le Qn≤m<Qn+Qn+1 and pu m=hQn+ wi h
0≤ < Qn. Then
(a)Pne en =⇒S(m) = (−1)nh+S( ).(12)
(b)Pnodd =⇒S(m) = (S(Qn)−S( )i his odd
S( )i his e en. (13)
P o o . We compu e he sum
S(m) =
m
X
j=1
(−1)bjαc=
=
h−1
X
k=0
Qn−1
X
s=1
(−1)b(kQn+s)αc+
h
X
k=1
(−1)bkQnαc+
X
s=1
(−1)b(kQn+s)αc.
Applying (11) we ge
S(m) =
h−1
X
k=0
Qn−1
X
s=1
(−1)kPn+bsαc+
h
X
k=1
(−1)kPn−[[ nis odd ]] +
X
s=1
(−1)hPn+bsαc
whe e, ollowing I e son’s no a ion, [[ X]] = 1 i he p oposi ion Xis ue, and
[[ X]] = 0 i Xis alse.
Simpli ying we ge
S(m) =
h−1
X
k=0
(−1)kPnS(Qn−1) +
h
X
k=1
(−1)kPn−[[ nis odd ]] + (−1)hPnS( ).(14)
40
ON SOME OSCILLATING SUMS
By Lemma 3 we ha e Sα(Qn−1) = SPn/Qn(Qn−1). The e o e, i Pnis e en
we ha e Sα(Qn−1) = 0 (see [5, Lemma 5.1]), so ha in his case
S(m) = (−1)nh+S( ).
I Pnis odd and he en, hen he wo sums in (14) a e equal o 0 and we ge
S(m) = S( ).
Finally, when Pnand ha e odd, he i s sum in (14) is equal o S(Qn−1),
he second is (−1)n+1, and we ge
S(m) = S(Qn−1) + (−1)n+1 −S( ) = S(Qn)−S( )
since, by Lemma 4, we ha e (−1)bQnαc= (−1)n+Pn= (−1)n+1.¤
2. Symme ies o he sequence o signs
We conside ou ypes o symme ies o he sequence o signs (−1)bjαc. Each
o hem leads o a use ul ans o ma ion o he sums S(n). In his sec ion we
de ine hese symme ies and p esen some heo ems in o de o ob ain hese
symme ies om he sequence o con e gen s o α. I should be no ed ha ou
de ini ions di e sligh ly om hose in [9].
De ini ion
7
.
The in ege n≥1will be called a poin o epe i ion (a REP,
o sho ) i
1≤k≤n=⇒(−1)bkαc= (−1)b(n+k)αc
o , equi alen ly, i bkαcand b(n+k)αcha e he same pa i y o 1≤k≤n.
No e.
The e seem o be α’s which do no yield any REP’s.
Fo example, α=√2 seems o be such a numbe .
The i s ew REP’s o α=πa e: n= 2, 7, 14, 21, 28, 35, 42, 49, 56, 226,
452, 678, 904, 1130, 1356, 1582, 1808, 2034, 2260, 2486, 2712, 2938.
Lemma
8
.
I nis a REP o α, hen
0≤k≤n=⇒Sα(n+k) = Sα(n) + Sα(k).(15)
P o o . Fo k≥1 we ha e
Sα(n+k) =
n+k
X
j=1
(−1)bjαc=
n
X
j=1
(−1)bjαc+
k
X
j=1
(−1)b(n+j)αc=
=Sα(n) + Sα(k).
As usual we de ine Sα(0) = 0, and o k= 0 he esul is i ial. ¤
41
J. ARIAS DE REYNA — J. VAN DE LUNE
De ini ion
9
.
The in ege n≥1will be called a poin o con a- epe i ion
(a CREP, o sho ) i
1≤k≤n=⇒(−1)bkαc=−(−1)b(n+k)αc
o , equi alen ly, i bkαcand b(n+k)αcha e di e en pa i ies o 1≤k≤n.
The i s ew CREP’s o α=πa e: n= 1, 3, 106, 113, 339, 565, 791, 1017,
1243, 1469, 1695, 1921, 2147, 2373, 2599, 2825, 3051, 3277, 3503, 3729.
In he same way as in Lemma 8 we p o e he ollowing
Lemma
10
.
I nis a CREP o α, hen
Sα(n+k) = Sα(n)−Sα(k),0≤k≤n. (16)
The nex Theo em p o ides REP’s and CREP’s o α. See no e a he end o
his sec ion ega ding he scope o his heo em.
P oposi ion
11
.
Le αbe any i a ional eal numbe . I h∈N,n≥0and
2hQn< Qn+Qn+1, hen
b(j+hQn)αc=hPn+bjαc,1≤j≤hQn.(17)
Thus hQnis a REP o αi hPnis e en, and a CREP i hPnis odd.
P o o . We may apply (11) wi h m=jand m=j+hQn. I j=kQn+ wi h
0≤ < Qn, hen j+hQn= (h+k)Qn+ . Thus, by (11),
bjαc=kPn+A(n, ),b(j+hQn)αc= (h+k)Pn+A(n, )
whe e A(n, ) depends only on nand and is he same in bo h cases.
This p o es (17). ¤
De ini ion
12
.
The in ege n≥2will be called an end-poin o e lec ion
(an EREF, o sho ) i
1≤k≤n/2 =⇒(−1)bkαc= (−1)b(n+1−k)αc
o , equi alen ly, i bkαcand b(n+1−k)αcha e he same pa i y o 1≤k≤n/2.
The i s ew EREF’s o α=πa e gi en by: n= 3, 5, 7, 14, 21, 28, 35, 42,
49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 331, 557, 783, 1009, 1235, 1461.
Lemma
13
.
I nis an EREF o α, hen
Sα(n+ 1 −k) = Sα(n)−Sα(k−1),(1 ≤k≤n/2).(18)
42
ON SOME OSCILLATING SUMS
P o o . Fo 2 ≤k≤n/2 we ha e
S(n) =
n
X
j=1
(−1)bjαc=
n+1−k
X
j=1
(−1)bjαc+
n+1−1
X
j=n+1−(k−1)
(−1)bjαc=
=S(n+ 1 −k) +
k−1
X
=1
(−1)b(n+1− )αc=S(n+ 1 −k) +
k−1
X
=1
(−1)b αc=
=S(n+ 1 −k) + S(k−1).
Fo k= 1 he esul is clea . ¤
De ini ion
14
.
The in ege n≥2will be called an end-poin o con a-
e lec ion (an ECREF, o sho ) i
1≤k≤n/2 =⇒(−1)bkαc=−(−1)b(n+1−k)αc
o , equi alen ly, i bkαcand b(n+1−k)αcha e di e en pa i ies o 1≤k≤n/2.
The i s ew ECREF’s o α=πa e gi en by: n= 2, 4, 6, 13, 211, 218, 225,
444, 670, 896, 1122, 1348, 1574, 1800, 2026, 2252, 2478, 2704, 2930.
Lemma
15
.
I nis an ECREF o he eal i a ional α, hen
Sα(n−k) = Sα(n) + Sα(k),0≤k≤n/2.(19)
I ollows ha Sα(n) = 0 o ne en, and Sα(n) = (−1)bn+1
2αc o nodd.
The p oo is simila o ha o Lemma 13.
P oposi ion
16
.
Le αbe any eal i a ional. I n≥ −1and 1≤h≤an+2
hen
b(Qn+hQn+1 −j)αc+bjαc=Pn+hPn+1 −1,1≤j < Qn+hQn+1.(20)
So Qn+hQn+1 −1(when ≥2) is an EREF o odd Pn+hPn+1, and an ECREF
when Pn+hPn+1 is e en.
P o o . Le P=Pn+hPn+1 and Q=Qn+hQn+1. The ac ion P
Qis a median
o 1 ≤h < an+2, whe eas P
Q=Qn+2
Pn+2 i h=an+2. In bo h cases we may apply
Lemma 3 o ge
bjαc=jjP
Qk,1≤j < Q.
Obse e ha (20) is equi alen o
jP−jP
Qk+jjP
Qk=P−1,1≤j < Q.
43
J. ARIAS DE REYNA — J. VAN DE LUNE
(3) When k= 0, we ha e J−1= [0,1), J0= [1,1 + Q1) wi h P0=a0. Thus,
P0e en implies a06= 1 and J−1∩J0=∅. So, asse ion (b) is ( acuously) ue
o k= 0. Thus, in wha ollows we may assume k≥1.
Assume k≥1, Pke en and Jk−1∩Jk6=∅. We wan o p o e ha ak= 1.
Since Pk−1is odd he e is only one eco d-holde ∈Jk−1and = 0+Qk−1
wi h 0< Qk−1. Since ∈Jkwe ge Qk≤ 0+Qk−1. The e o e (ak−1)Qk−1+
Qk−2≤ 0. Since k≥1 we ha e Qk−1≥1, and ak>1 leads o 0< Qk−1≤
(ak−1)Qk−1≤ 0which is a con adic ion.
Con e sely, i k≥1, Pkis e en and ak= 1, hen since (Pk−1, Pk) = 1 he
numbe Pk−1is odd and Pk=Pk−1+Pk−2implies ha also Pk−2is odd.
Then, by case (1) conside ed abo e, he only eco d-holde ∈Jk−1and he
eco d-holde 0∈Jk−2sa is y Qk−2< 0≤Qk−1≤Qk−2+Qk−1< , and
= 0+Qk−1. I ollows ha Qk−2+Qk−1=Qk≤ and ∈Jk.
We only need o show how many eco d-holde s a e con ained in Jkwhen Pk
is e en. They a e all he numbe s +hQk< Qk+Qk+1 = (ak+1 + 1)Qk+Qk−1
wi h h≥1 and < Qka pa icula eco d-holde . In case ak>1 his eco d-
holde is ∈Jk−1and /∈Jk. Thus Qk−1≤ < Qk. We see ha he allowed
alues o ha e 1 ≤h≤ak+1.
In case ak= 1 he only eco d-holde in Jk−1is con ained in Jkso ha
< Qk−1and i is easily seen ha he allowed alues o ha e gi en by 1 ≤h≤
ak+1 + 1.
Fo mula (28) is an easy consequence o he abo e esul s. ¤
The abo e heo ems jus i y he ollowing p ocedu e (w i en in Ma hema ica
Ve sion 5.2) in o de o ob ain he sequence o “all” eco d-holde s. We assume
ha we ha e p e iously de ined he numbe s P[n] and Q[n] o n < kMax (kMax
being an app op ia e limi ).
P og am o compu e he eco d-holde s o α
T = {0}; (* T will con ain he sequence o eco d-holde s *)
= 0 ; (* The las ob ained eco d - holde *)
Fo [n = 0, n <= kMax, n++,
I [OddQ[P[n]],
(* hen *) I [ < Q[n], = + Q[n]; T = Append[T, ]],
(* else *) While[ + Q[n] < Q[n] + Q[n + 1], + = Q[n]; T = Append[T, ]]
]
]; P in [T]
50
ON SOME OSCILLATING SUMS
4. The case o a quad a ic i a ionali y
In he case o a eal quad a ic i a ional α he numbe s Pkand Qkcan be
gi en explici ly. We did no ind he o mulas in P oposi ion 24 in he s anda d
ex books dealing wi h con inued ac ions.
P oposi ion
24
.
Le α∈Q(√d)be a eal quad a ic i a ionali y, and le kbe
he leng h o he pe iod o he egula con inued ac ion o α. Then
Pnk+j=Ajωn
1+Bjωn
2,
Qnk+j=Cjωn
1+Djωn
2,0≤j < k, n ≥n0(29)
whe e ω1and ω2a e ce ain conjuga e uni s in he ing o algeb aic in ege s in
Q(√d).
P o o . Le he con inued ac ion expansion o αbe
α={a0;a1, a2, . . . , ah, b1, b2, . . . , bk}(30)
and Pn/Qn he co esponding con e gen s. We conside he numbe βwi h
con inued ac ion {0; b1, b2, . . . , bk}. Le pn/qnbe he con e gen s o β. No e
ha p0= 0, p1= 1, q0= 1 and q1=b1.
I is well known ha he wo quad a ic i a ionals αand βgene a e he same
ield Q(α) = Q(β) = Q(√d).
Fo n≥0 and 1 ≤j≤kwe ha e
Qh+nk+j=bjQh+nk+j−1+Qh+nk+j−2.
In pa icula
Qh+nk+1 =b1Qh+nk +Qh+nk−1=q1Qh+nk +p1Qh+nk−1.
We claim ha in gene al o n≥0 and 1 ≤j≤k
Qh+nk+j=qjQh+nk +pjQh+nk−1.
We will p o e his by induc ion on he numbe j. Assuming ha we ha e p o ed
he esul o all numbe s less han j+ 1 we ha e
Qh+nk+j+1 =bj+1Qh+nk+j+Qh+nk+j−1
=bj+1(qjQh+nk +pjQh+nk−1) + qj−1Qh+nk +pj−1Qh+nk−1
= (bj+1qj+qj−1)Qh+nk + (bj+1pj+pj−1)Qh+nk−1
=qj+1Qh+nk +pj+1Qh+nk−1.
51
J. ARIAS DE REYNA — J. VAN DE LUNE
We can w i e his equa ion in ma ix o m
Qn:=
Qh+kn+k
Qh+kn+k−1
Qh+kn+k−2
. . .
Qh+kn+1
=Ω
Qh+kn
Qh+kn−1
Qh+kn−2
. . .
Qh+kn−k+1
=Ω Qn−1, n ≥0
whe e Ωis de ined by
Ω=
qkpk0. . . 0
qk−1pk−10. . . 0
.......................
q1p10. . . 0
.
The linea ans o ma ion Ωhas k−2 eigen alues equal o 0 whe eas he o he
wo a e he solu ions o he equa ion
¯¯¯¯
qk−ω pk
qk−1pk−1−ω¯¯¯¯
=ω2−(qk+pk−1)ω+ (−1)k= 0.
I s wo solu ions a e algeb aic in ege s. We call hem ω1and ω2. They a e
quad a ic i a ionals in he same ield Q(α). In o de o see his we p o e ha
he disc iminan o ωis he same as ha o β. In ac , βis he solu ion o he
quad a ic equa ion
pk+βpk−1
qk+βqk−1
=βo qk−1β2+ (qk−pk−1)β−pk= 0.
The e o e, he disc iminan o βis
∆ = (qk−pk−1)2+ 4qk−1pk= (qk−pk−1)2+ 4(qkpk−1+ (−1)k−1)
= (qk+pk−1)2−4(−1)k
which coincides wi h he disc iminan o ω.
Since ω1ω2= (−1)kand ω1and ω2a e no a ional, exac ly one o hem is in
absolu e alue la ge han 1. This one we call ω1.
Le u1and u2be he co esponding eigen ec o s. E e y ec o in he image
o Ωis a linea combina ion o hese wo ec o s. In pa icula he e exis
cons an s Aand Bsuch ha Q0=Au1+Bu2.
Then we ha e
Qn=Ωn(Au1+Bu2) = Aωn
1u1+Bωn
2u2.
Tha is, o n≥0 and 1 ≤j≤k,
Qh+kn+j=AUjωn
1+BVjωn
2
52
ON SOME OSCILLATING SUMS
whe e Ujand Vja e he coo dina es o he wo eigen ec o s. So, Ujand Vja e
conjuga e numbe s in he ield Q(α). ¤
P oposi ion
25
.
Le α∈Q(√d)be a eal quad a ic i a ionali y, and k he
leng h o he (pu e) pe iod o he con inued ac ion o α. Then he e a e na u al
numbe s b,L,Kan in ege mul iple o k, and a unc ion φsuch ha he sequence
o eco d-holde s o αsa is ies
b+nL+j− b+nL+j−1=QnK+φ(j),0≤j < L, n ≥0.(31)
Also, he e exis s a ini e sequence o signs (εj)L
j=1 such ha
εjS( b+nL+j)>0, n ≥0.(32)
Le Mbe he numbe o jsuch ha εj= 1, and m he numbe o jwi h
εj=−1. Then m+M=L, and
S( b+nL+j) = (nM +aji εj= 1
−nm +aji εj=−1.(33)
P o o . Assume ha αhas he con inued ac ion (30). Fo n≥1 he pai
(Pn, Pn+1) modulo 2 has only h ee possible alues (1,0), (0,1) and (1,1). The e-
o e, he e exis s a mul iple Ko k(Kwill be k, 2ko 3k) and c > h + 2 such
ha Pc−2≡Pc+K−2and Pc−1≡Pc+K−1. Gi en he pe iodici y o he pa ial
quo ien s o αand he ecu si e o mulas (6), we will ha e
Pc+m≡Pc+K+m,(mod 2), m ≥ −2.(34)
Wi hou loss o gene ali y we may assume ha Kis e en (i necessa y ake 2K
ins ead o K).
By P oposi ion 23 he numbe o eco d-holde s in he in e al Jndepends
only on he pa i y o Pnand he numbe s anand an+1. Since Kis a mul iple o
he pe iod ki ollows om (34) ha o n≥c he in e als Jnand Jn+Kcon ain
he same numbe o eco d-holde s. By P oposi ions 20 and 21 he cha ac e s
maximum/minimum o hese eco d-holde s will be he same since Khas been
aken e en.
The e o e, he numbe , cha ac e s and ela i e posi ions o he eco d-holde s
in he union o in e als SK
j=0 Jc+nK+jdo no depend on n.
Le b, b+1, . . . , b+L−1be he eco d-holde s con ained in SK
j=0 Jc+j. Then
he eco d-holde s con ained in SK
j=0 Jc+nK+jwill be he numbe s b+nL+jwi h
0≤j < L. The numbe s b+nL+jwi h a ixed ja e ei he all maxima o
all minima. Pu εj= 1 o a maximum and εj=−1 o a minimum. Then,
ob iously, we will ha e εjS( b+nL+j)>0.
53
J. ARIAS DE REYNA — J. VAN DE LUNE
I n≥band i he eco d-holde n∈J hen he eco d-holde n+L∈J +K.
This eco d-holde will be he only one in he gi en in e al o will ha e he same
posi ion be ween he eco d holde s in he espec i e in e als J and J +K. I
ollows ha i n− n−1=Q hen n+L− n+L−1=Q +K. Thus we can de ine
a unc ion φsuch ha
b+j+nL − b+j+nL−1=Qφ(j)+nK,0≤j < L.
Finally, le Mbe equal o he numbe o maxima in he pe iod o eco d-
holde s, and m he numbe o minima. I b+nL+jis a maximum, hen b+nL+L+j
is also a maximum and S( b+nL+L+j) = M+S( b+nL+j) since he e a e M
maxima on he pe iod o eco d-holde s. This ac , oge he wi h easoning
simila o ha o he case o minimum es ablishes ou o mula o S( b+nL+j).
¤
Co olla y
26
.
Wi h he same no a ions as in Theo em 24 and P oposi ion 25
b+nL+j=Ej+Fjωκn
1+Gjωκn
2,0≤j < L, n > n1(35)
whe e K=κk,κbeing a posi i e in ege .
P o o . Summing equa ions 31 o 0 ≤j < L we ge
b+(n+1)L−1− b+nL−1=
L−1
X
j=0
QnK+φ(j).
Fo e e y ixed jle φ(j) = ujk+ wi h 0 ≤ < k. Then nK +φ(j) =
(nκ +uj)k+ and by (29), o n≥n1, we will ha e
QnK+φ(j)=Cjωnκ+uj
1+Djωnκ+uj
2.
Thus he e exis cons an s n1,C0
jand D0
jsuch ha
b+(n+1)L−1− b+nL−1=C0
jωnκ
1+D0
jωnκ
2, n ≥n1.
Summing his o n1≤n≤N−1 we ge
b+NL−1= b+n1L−1+
N−1
X
n=n1
C0
jωnκ
1+D0
jωnκ
2.
Summing he geome ic se ies we see ha he e a e cons an s E−1,F−1and
G−1such ha
b+NL−1=E−1+F−1ωNκ
1+G−1ωNκ
2, N > n1.
54
ON SOME OSCILLATING SUMS
F om his equa ion, by induc ion, we ob ain (35). Fo example:
b+NL =E−1+F−1ωNκ
1+G−1ωNκ
2+QNK+φ(0) =
=E−1+F−1ωNκ
1+G−1ωNκ
2+C0ωNκ
1+D0ωNκ
2=E0+F0ωNκ
1+G0ωNκ
2.
¤
5. Connec ion wi h modula unc ions
The unc ions
Λ(α) = lim sup
n→∞
Sα(n)
log n, λ(α) = lim in
n→∞
Sα(n)
log n
a e ini e a he poin s α o which Sα(n) = O(log n), in pa icula a eal
quad a ic i a ionals.
We may es ic ou sel es o one o hem since S−α(n) = −Sα(n) (by (2)) so
ha
λ(α) = −Λ(−α).(36)
De ining H(α) = Λ(1 −α) we ha e
Theo em
27
.
Fo e e y eal i a ional α
H(α+ 2) = H(α), H³−1
α´=H(α).(37)
P o o . By (3) in Lemma 1 we ha e Λ(α+2) = Λ(α), so ha H(α+2) = H(α).
I is con enien o ex end he de ini ion o Sα(n). Fo any eal numbe xwe
pu
Sα(x) = X
1≤n≤x
(−1)bnαc.
I is easy o show ha wi h his de ini ion we ha e
Λ(α) = lim sup
x→∞
Sα(x)
log x, λ(α) = lim in
x→∞
Sα(x)
log x.
Now we p o e ha
α∈I, α > 1,1
α+1
β= 1 ⇒Λ(α) = −λ(β); λ(α) = −Λ(β).(38)
(He e Is ands o he se o all i a ional eal numbe s.) Assume ha α > 1 is
i a ional and ha 1
α+1
β= 1. A well known heo em by Bea y says ha bnαc
55
J. ARIAS DE REYNA — J. VAN DE LUNE
and bnβc hen o m a pa i ion o he na u al numbe s. This can be ansla ed
in o a p ope y o he sums Sα(n). In [15] we ound he p oo o
Sα(x/α) + Sβ(x/β) = O(1)
based on Bea y’s heo em.
Di iding by log xwe ge
Λ(α) = lim sup
x→+∞
Sα(x/α)
log(x/α)= lim sup
x→+∞
Sα(x/α)
log x=
= lim sup
x→+∞
O(1) −Sβ(x/β)
log x=−lim in
x→+∞
Sβ(x/β)
log(x/β)=−λ(β).
In he same way we ge
λ(α) = −Λ(β).
We can w i e he main equa ion in (38) in he o m
Λ(α) = −λ³α
α−1´, o α∈I, α > 1.(39)
Fo e e y i a ional y < 0 we ha e
H(y) = Λ(1 −y) = −λ³1−y
−y´=
=−λ³1−1
y´= Λ³1
y−1´= Λ³1 + 1
y´=H³−1
y´.
(The i s equali y is he de ini ion o H, he second an applica ion o (39) wi h
1−y > 1, he hi d an algeb aic iden i y, he ou h an applica ion o (36),
he i h an applica ion o he i s equa ion in (37), and he las one also an
applica ion o he de ini ion o H.)
Bu hen, by he symme y o his equa ion, i is ue o all y∈I.¤
Theo em
28
.
Fo αa quad a ic i a ional and wi h he same no a ions used
in Theo em 24 and P oposi ion 25 we ha e
Λ(α) = M
κlog ω1
and λ(α) = −m
κlog ω1
.(40)
P o o . I M= 0, hen he e is a mos a ini e numbe o maximum- eco d-
holde s and a cons an Csuch ha S(n)≤C o all n∈N. So Λ(α) = 0 and
equa ion (40) is ue.
When M > 0 he e a e in ini ely many maximum- eco d-holde s. So, gi en x,
he e is a eco d-holde sa is ying b+(n−1)L+j< x ≤ b+nL+j. By Co olla y 35
56
ON SOME OSCILLATING SUMS
he e is a cons an C(o he o de o |ωκ
1|) such ha b+nL+j≤C b+(n−1)L+j.
I ollows ha log x∼log b+nL+jand we ha e
Λ(α) = lim sup
x→+∞
Sα(x)
log x≤lim sup
n→∞
S( b+nL+j)
log b+nL+j
=
= lim sup
n→∞
nM +aj
log(Ej+Fjωnκ
1+Gjωnκ
2)=M
κlog ω1
.
Since his is he limi o Sα(n)/log n o a pa icula sequence, i is also less
han o equal o he lim sup = Λ(α), p o ing (40). ¤
6. The o de o he sums
O’B yan , Reznick and Se binowska wonde in [15] whe he Sα(n) =
O(log n) is he co ec ype o g ow h o Sα(n) o a quad a ic i a ional α.
They say ha i seems unlikely ha Sα(n) = O(log n) o almos all α, bu a
p oo o his is elusi e. They also ask o necessa y and su icien condi ions on α
(in e ms o i s con inued ac ion expansion) in o de o ha e Sα(n) = O(log n).
In his sec ion we will answe he i s and second o hese ques ions.
Applying Theo em 28 o a eal quad a ic i a ional α, we ha e
lim sup
n
Sα(n)/log n > lim in
nSα(n)/log n
and bo h a e ini e eal numbe s. Hence Sα(n) = O(log n) and Sα(n) = Ω(log n).
Thus, O(log n) is he co ec a e o g ow h o Sα(n) o any ixed eal quad a ic
i a ional α.
Ou Theo em 18 shows ha o any i a ional α he sum Sα(n) is no bounded.
This is abou all ha can be said in gene al. In [15] i is p o ed ha o any
posi i e unc ion ψ(n)≥1 ha inc eases o in ini y, we can ind an αwi h
|Sα(n)| ≤ ψ(n) o all n.
The e is an impo an connec ion be ween ou sums and he concep o dis-
c epancy. Gi en a sequence o eal numbe s (xj) in he in e al [0,1], i s dis-
c epancy D∗
n(xj) is de ined by
D∗
n(xj) = sup
∈[0,1)¯¯¯
#{j≤n: 0 ≤xj< }
n− ¯¯¯.
I is easy o show ha (see, o example, [15])
Sα(n) = 2n³#{j≤n:{jα/2}<1
2}
n−1
2´.
57
J. ARIAS DE REYNA — J. VAN DE LUNE
He e, as usual, {x}deno es he ac ional pa o x. So we ha e
|Sα(n)| ≤ 2nD∗
n({jα/2}).
The e is a subs an ial li e a u e on he disc epancy o he sequence {nα}
(a good su ey can be ound in [10]). Fo example, he ollowing esul is due
o Khin chine:Le ϕ(n)be a posi i e inc easing unc ion. Then
sup
n≤N
nD∗
n({jα}) = O(log N·ϕ(log log N))
o almos all α∈Ri and only i ∞
X
n=1
1
ϕ(n)<∞.
I ollows ha o almos all α∈(0,1) we ha e
sup
n≤N|Sα(n)| ≤ sup
n≤N
nD∗
n({jα/2}) = O(log N·ϕ(log log N))
when ϕ(n) is an inc easing posi i e unc ion wi h P∞
n=1 1
ϕ(n)<∞.
We a e going o ex end his esul o he ollowing
Theo em
29
.
Le ψ(x)and ϕ(x)be posi i e inc easing unc ions such ha
Z∞
1
dx
ψ(x)= +∞and Z∞
1
dx
ϕ(x)<+∞.
Then o almos all α∈(0,1) we ha e
Ω(log N·ψ(log log N)) ≤sup
n≤N|Sα(n)| ≤
≤sup
n≤N
nD∗
n({jα/2}) = O(log N·ϕ(log log N)).(41)
P o o . We only need o p o e he i s inequali y.
By P oposi ion 23 he numbe o eco d-holde s < Qn+Qn+1 is la ge han
o equal o he sum
X
0≤k≤n
Pke en
ak+1.
I ollows ha he maximum o |Sα(k)| o k < Qn+Qn+1 is, when Pnis e en,
a leas 1
2an+1. Thus, wi h m=n+ 1 we ha e (once mo e using I e son’s
no a ion)
sup
n≤Qm+Qm−1|S(n)| ≥ 1
2[[ Pm−1e en ]] am.(42)
Now we need some measu e heo y. Le E⊂[0,1] be he se o hose i a ional
numbe s α∈[0,1] o which he pa ial quo ien s a1=k1,a2=k2, . . . , a =k
58
ON SOME OSCILLATING SUMS
ake de ini e alues, and le E(k) be he subse o hese numbe s o which he
addi ional pa ial quo ien a +1 is equal o k. Then we ha e (see [1, p. 60])
|E|
3k2<|E(k)| ≤ 2|E|
k2.(43)
Fo e e y mpu Mα(m) = supn≤Qm+Qm−1|Sα(n)|. We a e going o show ha ,
gi en he se E(wi h k≥2), we ha e
|{α∈E:Mα(k+ 3) ≥L}| ≥ |E|
200L.
All numbe s in Eha e egula con inued ac ion expansions s a ing wi h
{0; k1, k2, . . . , k , . . . }.
Thus, hey sha e he same con e gen s P0/Q0, . . . , P −1/Q −1,P /Q . Since
(P −1, P ) = 1 modulo 2, hese wo numbe s can be: bo h odd (1,1), he i s
e en and he second odd (0,1), o he i s odd and he second e en (1,0) ( o
all numbe s in he se E).
Now we decompose Ein ou disjoin subse s E1,1,E1,0,E0,1, and E0,0de ined
by:
E1,1={α∈E:a +1 ≡1 (mod 2), a +2 ≡1 (mod 2)}
wi h simila de ini ions o E1,0,E0,1,E0,0.
We ha e o conside h ee cases.
Assume i s ha (P −1, P )≡(1,1) modulo 2. In his case all he numbe s
α∈E0,1sa is y
P +1 =a +1P +P −1≡P −1≡1 (mod 2)
and
P +2 =a +2P +1 +P ≡P +1 +P ≡0 (mod 2).
The e o e, by (42), o α∈E0,1we ha e
Mα( + 3) = sup
n≤Q +3+Q +2 |Sα(n)| ≥ a +3
2
so ha we ha e
{α∈E:Mα( + 3) ≥L} ⊃ [
k≥2L
E0,1(k).
He e E0,1(k) deno es he se o hose α∈E o which a +1 is e en, a +2 is odd
and a +3 =k.
59
J. ARIAS DE REYNA — J. VAN DE LUNE
Fo [j = 1, j <= m2, j++,
nonpe iodic = Append[nonpe iodic, {minima[[j]], "min"}]];
nonpe iodic = So [nonpe iodic];
nonpe iodic = Table[nonpe iodic[[j]][[2]], {j, 1, Leng h[nonpe iodic]}];
pe iod = Append[nonpe iodic, Lpe iod];
(* =================================================================== *)
(* 8. We simpli y he pe iod *)
(* Now we simpli y he pe iod {max, {max, min, max}} -> {{max, max, min}} *)
u = Leng h[Las [pe iod]]; = Leng h[pe iod] - 1;
While[( > 0) && (pe iod[[ ]] == Las [Las [pe iod]]),
pe iod = Inse [pe iod, Ro a eRigh [Las [pe iod], 1], -1];
pe iod = Dele e[pe iod, -2]; pe iod = Dele e[pe iod, -2];
u = Leng h[Las [pe iod]]; = Leng h[pe iod] - 1];
(* We simpli y he pu e pe iod {max, min, max, min} -> {max, min} *)
lp = Leng h[Las [pe iod]]; di = Di iso s[lp];
pu epe iod = Las [pe iod];
= 1; CheckValue = False;
While[CheckValue == False, CheckValue = T ue;
d = di [[ ]];
Fo [j = 1, j <= d, j++,
Fo [k = 0, k < lp/d, k++,
I [pu epe iod[[j]] != pu epe iod[[d*k + j]],
CheckValue = False]]];
++];
pe iod = Append[D op[pe iod, -1], Take[Las [pe iod], d]];
(* 9. P in he esul s o he abo e analysis *)
P in ["* α= ", α];
P in ["* Type o S-ex emes in pe iod = ", pe iod];
P in ["* Leng h o his pe iod = ", Leng h[pe iod[[1]]]];
Pe iodReco dHolde s = Table[S[α, T[[n]]], {n, 2, 1 + 2*Leng h[pe iod[[1]]]}];
(* ! We only obse ed pu e pe iods ! *)
P in ["* Regula CF(α) = ", Regula Con inuedF ac ion[α]];
P in ["* Sign sequence o S( _n) -> ", Sign[Pe iodReco dHolde s]];
P in ["* Uni s : ω1 = ", ω1," ω2 = ", ω2];
P in ["* _n o Maxima -> ", MM];
P in ["* _n o minima -> ", mm];
T = Dele e[T, 1];
P in ["* ’All’ Reco d-Holde s _n -> ", T];
(* The nex line equi es he loading o he FFL ou ine o he Appendix *)
P in ["* S( _n) -> ", Table[S[α, T[[j]]], {j, 1, Leng h[pe iod[[1]]]}]];
P in ["* κ= ", κ];
P in ["* Λ(α) = ", Λ= FullSimpli y[ M/(κ*Log[ω1])], " ≈", N[Λ]];
P in ["* λ(α) = ", λ= FullSimpli y[ - m/(κ*Log[ω1])], " ≈", N[λ]];
"Done"];
One may check he eco d-holde s o αby he ollowing simple p og am
66
ON SOME OSCILLATING SUMS
Ma hema ica Code o Gene a ing he Reco d-Holde s.
α=√2(* Fo example *)
n = 0; s = 0; sMax = 0; sMin = 0;
While[0 == 0, n += 1;
I [E enQ[Floo [n*α]], s += 1, s -= 1];
I [s > sMax, sMax = s; P in [" n= ", n, " s= ", s]; Go o[A]];
I [s < sMin, sMin = s; P in [" n= ", n, " s= ", s]];
Label[A]]
8. Some emaining open p oblems
1. In all o ou compu a ions, he sequence o he signs o Sα( n) always
u ned ou o be pu ely pe iodic.
We we e unable o p o e he consis ency o his su p ising obse a ion.
2. I seems ha he e is always a sys em o ecu ence ela ions o he eco d-
holde s n. Fo example, o α=√3 we ind ha
4n= 2 4n−1+ 4n−4+ 1
4n+1 = 4n+ 4n−1+ 1
4n+2 = 4n+1 + 2 4n+ 1
4n+3 = 4n+2 + 2 4n+ 1.
We ha e no pu sued his subjec any u he .
3. I seems ha he inhomogeneous sums Pn
j=1(−1)bjα+βcexhibi ce ain
cha ac e is ics e y simila o hose o he homogeneous sums deal wi h
in his pape . Fo example o he sums Pn
j=1(−1)bj√2 + 1
2cwe ind he
ecu ences:
2n= 2 2n−1− 2n−4
2n+1 = 3 2n+ 1.
4. The p obabilis ic dis ibu ion o he alues o Sα(n) o n= 1, 2, 3, . . .
appea s o be e y egula and s able. Is he e a Gaussian dis ibu ion
lu king in he backg ound?
5. Finally he e is he p oblem o he dis ibu ion o Sα(n) o e he esidue
classes mod m(wi h m > 2).
6. Al hough we did no s udy gene al i a ional α’s, we obse ed a ious
egula i ies o Sα(n) o α= a simple o m composed wi h he numbe e.
67
J. ARIAS DE REYNA — J. VAN DE LUNE
Fo example, α=e,e1/m ,e−1/m ,e1/m−1
e1/m+1 . I seems ha o he las o
hese he eco d-holde s a e gi en by
k=
ki 1 ≤k≤2m
2(4m −m+ 1) k−1− k−2i k= 4m 2−2m + 1, ( > 1)
2 k−1− k−2i k6= 4m 2−2m + 1, ( > 1).
9. Appendix. The FFL algo i hm
This algo i hm is implici ly con ained in [9]. I compu es he alue o Sα(n)
o any i a ional α. He e we p esen i s implemen a ion in Ma hema ica Ve sion
5.2 and p esen a p oo o i .
In he i s pa o he algo i hm, applying Lemma 1, we de e mine an i a-
ional β∈(0,1) and a sign σsuch ha o e e y na u al numbe nwe ha e
Sα(n) = σSβ(n).
S[α_, M_] := Module[{j, R, m, a, b, k},
(* ========================================================= *)
(* 1. Compu e βand σsuch ha Sα(n) = σ·Sβ(n)*)
(* ========================================================= *)
σ= 1; β=α;
I [β< 0, β= -β;σ= -σ]; (* Now β> 0 *)
β- = 2 Floo [β/2]; (* Now 0 < β< 2 *)
I [β> 1, β=2-β;σ= -σ]; (* Now 0 < β< 1 *)
In o de o compu e he alue o Sβ(n) he FFL algo i hm uses he denomi-
na o s qko he con e gen s o he numbe γ=β/2. We will ha e o compu e
hese qk o he indices ksa is ying qk−1≤n<qk. By induc ion we ind
ha qk≥Fk+1, a Fibonacci numbe . So, we compu e qk o all ksuch ha
Fk−1≤³1+√5
2´k≤n.
(* ========================================================= *)
(* 2. Compu e he necessa y q[k] o M *)
(* ========================================================= *)
β=β/2;
kMax = 1 + Ceiling[Log[2, M + 1]/Log[(1+Sq [5])/2]];
CF=Con inuedF ac ion[ β, kMax ];
68
ON SOME OSCILLATING SUMS
q[-2]=1; q[-1]=0;
Fo [ k = 0, k < kMax, k++, q[k] = CF[[k+1]]* q[k-1]+ q[k-2] ];
Finally, he algo i hm depends on wo p inciples:
(A) I qk−1≤m < qkand qk/2< m hen
Sβ(m) = Sβ(qk−m−1) + ((−1)k−1i qkis e en
0 i qkis odd.
(B) I qk−1≤m < qk,m≤qk/2, and m=hqk−1+ hen
Sβ(m) = Sβ( ) + h(0 i qk−1is e en
(−1)k−1i qk−1is odd.
Now we can supply he code o he unc ion Sα(n).
9(* ========================================================= *)
10 (* 3. The FFL- ou ine p ope *)
11 (* ========================================================= *)
12 m=M; R=0;
13 (* Th oughou he p og am we will ha e S(M)= S(m)+ R *)
14 j = kMax - 1;
15 While[ m > 0, While[q[j] > m, j--];
16 (* We ha e loca ed j wi h q[j] <= m < q[j+1] *)
17 a = q[j]; b = q[j+1];
18 I [ b - m < b/2, (* Then we apply p inciple A *)
19 R += I [ E enQ[b], (-1)^j, 0];
20 m=b-m-1,
21 (* Else we apply p inciple B *)
22 R += Floo [m/a] * I [E enQ[a], 0, (-1)^j ];
23 m = Mod[m,a] ]];
24 (* end o While. *)
25 (* Ou pu *) sigma * R ]
26 (* END o he FFL- ou ine and S[α,M] *)
We p o e he wo p inciples o he algo i hm.
(A) By Theo em 17 he numbe 2qk−1 is an ECREF o γso ha
b(2qk−j)γc+bjγc= 2pk−1,1≤j < qk.(46)
Pu j= 2n. Since γ=β/2 we ha e
b(qk−n)βc+bnβc= 2pk−1,1≤n < qk/2.
69
J. ARIAS DE REYNA — J. VAN DE LUNE
The e o e
1≤n < qk/2 =⇒(−1)bnβc=−(−1)b(qk−n)βc.
Thus qk−1 is an ECREF o βand we ha e
Sβ(qk−1−n) = Sβ(qk−1) + Sβ(n),0≤n < qk/2.
Mo eo e , we ha e
Sβ(qk−1) =
qk−1
X
j=1
(−1)bjβc=
qk−1
X
j=1
(−1)b2jγc.
By (46) we ha e (−1)b2jγc=−(−1)b2(qk−j)γc. I qkis odd we ge Sβ(qk−1) = 0,
and o qke en he en i e sum is equal o he cen al e m (−1)bqkγc. By
Lemma 4 his e m is equal o (−1)k+pk. Since qkis e en, pkis odd, and we ge
Sβ(qk−1) = (−1)k−1. W i ing m=qk−1−nwe ge
Sβ(m) = (−1)k−1+Sβ(qk−1−m), qk/2< m < qk
comple ing he p oo o (A).
(B) Now assume ha qk−1≤m≤qk/2. Le hand 0 ≤ < qk−1be such ha
m=hqk−1+ . Le jbe such ha qk−1≤j < j +qk−1≤m<qk/2 and le
2j=dqk−1+u. By applying P oposi ion 5 wice, i s o 2j+ 2qk−1and hen
o 2j, we ob ain
(−1)b(j+qk−1)βc= (−1)b(2j+2qk−1)γc= (−1)(d+2)pk−1+buγc=
= (−1)dpk−1+buγc= (−1)b2jγc= (−1)bjβc.
(This o u6= 0 and by a simila easoning o u= 0.) I ollows ha
Sβ(m) =
hqk−1+
X
j=1
(−1)bjβc=
X
j=1
(−1)bjβc+h
qk−1
X
j=1
(−1)bjβc.
As obse ed in he p oo o (A), he e ms o he sum Pqk−1
j=1 (−1)bjβccancel ( he
e m o j= 1 wi h ha o j=qk−1−1, he e m wi h j= 2 wi h ha o
j=qk−1−2, . . . ). I qk−1is odd he sum is equal o (−1)b2qk−1γc, and i qk−1
is e en i is equal o (−1)bqk−1γc+ (−1)b2qk−1γc.
By P oposi ion 5 we see ha b2qk−1γcis equal o 2pk−1when k−1 is e en, and
equal o 2pk−1−1 when k−1 is odd. Thus in each case (−1)b2qk−1γc= (−1)k−1.
So, when qk−1is odd we ha e Pqk−1
j=1 (−1)bjβc= (−1)k−1.
70
ON SOME OSCILLATING SUMS
When qk−1is e en we ha e
qk−1
X
j=1
(−1)bjβc= (−1)k−1+ (−1)bqk−1γc.
Also we ha e (−1)bqk−1γc= (−1)pk−1+k−1, and qk−1being e en, pk−1is odd.
The e o e (−1)bqk−1γc= (−1)kand (−1)bqk−1γc+ (−1)b2qk−1γc= 0. This com-
ple es he p oo o (B).
Acknowledgmen .
The au ho s would like o hank Fos e Dieckho
( Kansas Ci y, MO ) o his linguis ic assis ance in p epa ing his pape , and his
in e es in ou esul s.
REFERENCES
[1] KINTCHINE, A.YA.: Con inued ac ions, Rep in o he 1964 ansla ion,
Do e , Mineola N. Y., 1997.
[2] KRESTEN, H.: On a conjec u e o E d¨os and Sz¨usz ela ed o uni o m dis ibu-
ion mod 1, Ac a A i h. 12 (1966), 193–212.
[3] RUDERMAN, H.D.: P oblem 6105*, Ame . Ma h. Mon hly 83 (1976), 573.
[4] VAN DE LUNE, J.: On he con e gence o some “i egula ly” oscilla ing se ies,
A deling Zui e e Wiskunde, Repo ZW 86/76, Ma hema ical Cen e, Ams e -
dam, 1976.
[5] BROUWER, A.E. – VAN DE LUNE, J.: A No e on Ce ain Oscilla ing Sums,
A deling Zui e e Wiskunde, Repo ZW 90/76, Ma hema ical Cen e, Ams e -
dam, 1976.
[6] BUNDSCHUH, P.: Kon e genz unendliche Reihen und Gleich e eilung mod 1,
A ch. Ma h. 29 (1977), 518–523.
[7] BORWEIN, D.: Solu ion o p oblem no. 6105, Ame . Ma h. Mon hly 85 (1978),
207–208.
[8] BORWEIN, D. – GAWRONSKI, W.: On ce ain sequences o plus and minus
ones, Canad. J. Ma h. 30 (1978), 170–179.
[9] FOKKINK, R. – FOKKINK, W. – VAN DE LUNE, J.: Fas Compu a ion o an
Al e na ing Sum, Nieuw A chie oo Wiskunde 12 (1994), 13–18.
[10] DRMOTA, M.–TICHY, R.F.: Sequences, Disc epancies and Applica ions, Lec-
u e No es in Ma hema ics 1651, Sp inge -Ve lag, Be lin, Heidelbe g, 1997.
[11] BOURBAKI, N.: Gene al Topology, Sp inge -Ve lag, Be lin, 1998, Chap e s 5–
10.
[12] SCHOISSENGEIER, J.: The in eg al mean o disc epancy o he sequence (nα),
Mona sh. Ma h. 131 (2000), 227–234.
[13] SERBINOWSKA, M.: A case o an almos al e na ing se ies, Unpublished man-
usc ip (2003), a ailable om he au ho on eques .
71
J. ARIAS DE REYNA — J. VAN DE LUNE
[14] SCHOISSENGEIER, J. – TRIˇ
CKOVI´
C, S.B.: On he di e gence o a ce ain
se ies, J. Ma h. Anal. Appl. 324 (2006), 238–247.
[15] O’BRYANT, K. – REZNICK, B. – SERBINOWSKA, M.: Almos al e na ing
sums, Ame . Ma h. Mon hly 113 (2006), 673–688.
[16] FOSTER, J.H. – SERBINOWSKA, M.: On he Con e gence o a Class o Nea ly
Al e na ing Se ies, Canad. J. Ma h. 59 (2007), 85–108.
[17] SCHOISSENGEIER, J.: On he Con e gence o a Se ies o Bundschuh, Uni o m
Dis ibu ion Theo y 2(2007), no. 1, 107–113.
Recei ed May 21, 2008
Accep ed July 22, 2008
J. A ias de Reyna
Facul ad de Ma em´a icas
Uni e sidad de Se illa, Apdo. 1160
41080-Se illa
SPAIN
E-mail: [email p o ec ed]
J. an de Lune
Langebuo en 49
9074 CH Hallum
( o me ly a CWI, Ams e dam)
THE NETHERLANDS
E-mail: j. [email p o ec ed]
72